Natural Policy Gradient

Latest papers

13 papers0 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

High-Probability Nash Regret for Decentralized Learning in Markov $α$ -Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
Sep 14, 2026S. Rasoul EtesamiPolicy Gradient Asynchronous RL
Department of Industrial and Systems Engineering Coordinated Science Laboratory University of Illinois Urbana-Champaign, Urbana, IL, USA
The Dually Flat Geometry of Planning as Inference
Sep 3, 2026Nikola Milosevic, Asaki Kataoka, Nicolas Hinrichs +2Information Geometry Natural Policy Gradient
Neural Data Science and Statistical Computing Group Max Planck Institute for Human Cognitive and Brain Sciences Leipzig, 04103 Germany · Neural Computation Unit Okinawa Institute of Science and Technology Okinawa, 904-0495 Japan
Unregularized Convergence of Single-Loop, Entropy-Regularized Natural Actor-Critic
Aug 20, 2026Zhiqiang TanPolicy Optimization Actor-Critic Methods
Department of Statistics, Rutgers University. Address: 110 Frelinghuysen Road, Piscataway, NJ 08854.
Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes
Jul 25, 2026Asha Barua, Sajad KhodadadianPolicy Gradient Markov Decision Processes
Grado Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061, USA.
Randomized Advantage Transformation (RAT): Computing Natural Policy Gradients via Direct Backpropagation
May 18, 2026Mingfei SunPolicy Gradient Natural Gradient Methods
The University of Manchester, United Kingdom.
Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions
May 13, 2026Ishaq Hamza, Zaiwei ChenPolicy Gradient Last-Iterate Convergence
IISc · Edwardson School of Industrial Engineering, Purdue University · Purdue IE
Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework
May 11, 2026Phalguni Nanda, Zaiwei ChenPolicy Gradient Reinforcement Learning
Edwardson School of Industrial Engineering, Purdue University
Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Games
Apr 1, 2026Wonseok Yang, Thinh T. DoanNatural Policy Gradient Multi-Agent Reinforcement Learning
University of Texas at Austin, Austin, TX, 78712 USA
Functional Natural Policy Gradients
Mar 30, 2026Aurelien Bibaut, Houssam Zenati, Thibaud Rahier +1Natural Policy Gradient Policy Learning
Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learning
Mar 9, 2026Swetha Ganesh, Vaneet AggarwalNatural Policy Gradient Multi-Objective Reinforcement Learning
Purdue University, USA 47907
Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterization
Mar 8, 2026Anirudh Satheesh, Pankaj Kumar Barman, Washim Uddin Mondal +1Natural Policy Gradient Constrained RL
Department of Computer Science, University of Maryland, College Park, MD 20740, USA · Indian Institute of Technology, Kanpur, Uttar Pradesh, 208016, India · Department of Electrical Engineering, Indian Institute of Technology, Kanpur, Uttar Pradesh, 208016, India +1
Beyond State-Wise Mirror Descent: Offline Policy Optimization with Parametric Policies
Feb 27, 2026Xiang Li, Yuheng Zhang, Nan JiangNatural Policy Gradient Offline RL
Nanjing University · UIUC
Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients
Mar 28, 2024Johannes Müller, Semih Çaycı, Guido MontúfarPolicy Gradient Optimization Convergence Analysis
Department of Mathematics, RWTH Aachen University, Aachen, 52062, Germany · Departments of Mathematics and Statistics & Data Science, University of California, Los Angeles, 90095, USA · Max Planck Institute for Mathematics in the Sciences, Leipzig, 04103, Germany

Sep 14, 2026J/K move · Enter open · S save

High-Probability Nash Regret for Decentralized Learning in Markov $α$ -Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

S. Rasoul Etesami

Department of Industrial and Systems Engineering Coordinated Science Laboratory University of Illinois Urbana-Champaign, Urbana, IL, USA

Policy Gradient Asynchronous RL Game Theory Natural Policy Gradient Decentralized MARL Nash Equilibrium Computation

Open paper AskPDF arXiv

We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov

α

-potential games. We develop KL-projected natural policy gradient (NPG) algorithms in two settings: an episodic setting with frozen policies during sampling and a fully online setting in which players receive a single realized cost sample per time step and update their policies asynchronously along a continuing trajectory. We establish finite-time high-probability NE regret bounds of order

\widetilde O(T^{-1/4})

and

\widetilde O(T^{-2/15})

for the episodic and fully online settings, respectively, up to fixed approximation terms. Crucially, our bounds eliminate the distribution-mismatch coefficient, which can scale prohibitively with the size of the state space, while accommodating potential approximation, estimation-oracle bias, and transition sensitivity. We further identify a state-wise potential structure that yields sharper guarantees with additive dependence on the potential approximation error

α

. We specialize the framework to independent-resource Markov congestion games (IMCGs), establish their approximate-potential and transition-sensitivity properties, and construct decentralized estimation oracles from realized costs. As an application, we introduce strategic online job scheduling on stochastic machines and obtain a scalable decentralized algorithm for learning stable dispatching policies. Overall, our results provide the first finite-time high-probability NE regret guarantees for fully online asynchronous decentralized learning in Markov

α

-potential games, remove distribution-mismatch coefficients from the regret bounds, accommodate fixed estimation-oracle bias, and provide scalable decentralized learning with finite-time guarantees for IMCGs.