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.

Sep 14, 2026

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

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.

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

Ask PDF

Sep 3, 2026

The Dually Flat Geometry of Planning as Inference

We present an alternative characterization of the occupancy measure of reinforcement learning, obtained by embedding the planning criterion into the dynamics through a resetting planning process. Its stationary measure, which we term visitation measure, is the object on which the information geometry of decision making is most naturally expressed. The achievable visitation measures form a dually flat statistical manifold whose two affine charts are the visitation probabilities and the log-policies, dual under the conditional entropy. This structure makes planning-as-inference generalize from linear rewards to nonlinear functionals of the visitation, each iterate solved by one natural-gradient step, and gives the temporal-difference error the interpretation of a marginal-utility estimate. We develop the geometry and its consequences for reinforcement learning and theoretical neuroscience.

Nikola Milosevic, Asaki Kataoka, Nicolas Hinrichs +2

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

Information Geometry Natural Policy Gradient

Ask PDF

Aug 20, 2026

Unregularized Convergence of Single-Loop, Entropy-Regularized Natural Actor-Critic

While entropy regularization is widely used to stabilize and accelerate Natural Policy Gradient methods, its ability to yield faster convergence rates for the unregularized objective remains underexplored. Existing analyses often rely on double-loop architectures and invoke a linear entropy penalty. To bridge the gap between theory and practice, we analyze a single-loop, entropy-regularized Natural Actor-Critic algorithm under compatible linear function approximation. By training an uncentered critic, our critic tracking can remain stable even as the training policy approaches determinism and the Fisher information matrix degenerates. We focus on two primary regimes for the optimization landscape: a Stochastic Regime, where we fuse coupled actor-critic updates into a joint Lyapunov recurrence, and a Deterministic Regime, where we pivot to a Policy Mirror Descent framework to circumvent the collapse of Euclidean geometry. By exploiting a positive Minimal Action Gap in the unregularized Markov decision process, we introduce an Exponential Translation mechanism that maps the regularized gap to the unregularized one up to an exponentially decaying tail. By tuning the fixed temperature, our algorithm achieves accelerated unregularized convergence rates, up to approximation-error terms:

\tilde{\mathcal{O}}(T_{total}^{-1})

in the Stochastic Regime, and

\tilde{\mathcal{O}}(T_{total}^{-2/3})

for the average iterate alongside

\tilde{\mathcal{O}}(T_{total}^{-1/3})

for the last iterate in the Deterministic Regime. Here,

T_{total}

denotes the total number of stochastic critic updates (or Monte Carlo rollouts). Furthermore, in the tabular setting, our positive-action-gap analysis yields a

\tilde{\mathcal{O}}(T_{total}^{-2/3})

average-iterate rate, surpassing the

\mathcal{O}(T_{total}^{-1/2})

worst-case statistical barrier that applies without a positive action margin.

Zhiqiang Tan

Department of Statistics, Rutgers University. Address: 110 Frelinghuysen Road, Piscataway, NJ 08854.

Policy Optimization Actor-Critic Methods Natural Policy Gradient Natural Gradient Methods Stochastic Optimization Convergence

Ask PDF

Jul 25, 2026

Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes

Natural Policy Gradient (NPG) is a well-established Reinforcement Learning algorithm that underlies widely used methods such as Trust Region Policy Optimization and Proximal Policy Optimization, both of which have demonstrated strong empirical success. In this paper, we study exact NPG in finite-horizon Markov Decision Processes with known dynamics and horizon-dependent transition kernels. We provide the first finite-time convergence guarantees for this algorithm in this setting, for which we consider both constant and increasing step size regimes. With a constant step size

η_t=η

, we prove that NPG converges sublinearly with a rate of

\mathcal{O}(H^{2}/t)

after

t

iterations, where

H

is the horizon length. We also extend this constant step size analysis to linear MDPs in an exact population-projection oracle under a full support projection distribution, recovering the same sublinear rate as in the tabular setting. Furthermore, with increasing step sizes, we prove that this algorithm achieves a linear convergence rate of

\mathcal{O}\left(\left(1-\frac{1}{\vartheta_ρ}\right)^t\right)

for a problem-dependent constant

\vartheta_ρ> 1

, and the horizon-only robust schedule of the form

η_t=η_0(H/(H-1))^t

where

η_0>0

and

H \geq 2

, attains this same geometric rate.

Asha Barua, Sajad Khodadadian

Grado Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061, USA.

Policy Gradient Markov Decision Processes Natural Gradient Methods Natural Policy Gradient Policy Gradient Methods Policy Learning

Ask PDF

May 18, 2026

Randomized Advantage Transformation (RAT): Computing Natural Policy Gradients via Direct Backpropagation

Natural policy gradients improve optimization by accounting for the geometry of distribution space, but their practical use is limited by the cost of estimating and inverting the Fisher matrix. We present Randomized Advantage Transformation (RAT), a method for estimating Tikhonov-regularized natural policy gradients via direct backpropagation. By applying the Woodbury formula, we reformulate the regularized natural policy gradients as vanilla policy gradients with a transformed advantage. RAT computes this transformation efficiently via randomized block Kaczmarz iterations on on-policy mini-batches, avoiding explicit Fisher construction, conjugate-gradient solvers, and architecture-specific approximations. We provide convergence guarantees for RAT and demonstrate empirically that it matches or exceeds established natural-gradient methods across continuous and visual control benchmarks, while remaining simple to implement and compatible with various architectures.

Mingfei Sun

The University of Manchester, United Kingdom.

Policy Gradient Natural Gradient Methods Natural Policy Gradient Policy Gradient Methods Policy Learning

Ask PDF

May 13, 2026

Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

In this paper, we establish last-iterate convergence rates for off-policy actor--critic methods in reinforcement learning. In particular, under a single-loop, single-timescale implementation and a broad class of policy updates, including approximate policy iteration and natural policy gradient methods, we prove the first

\tilde{\mathcal{O}}(ε^{-2})

sample complexity guarantee for finding an

ε

-optimal policy under minimal assumptions, namely, the existence of a policy that induces an irreducible Markov chain. This stands in stark contrast to the existing literature, where an

\tilde{\mathcal{O}}(ε^{-2})

sample complexity is achieved only through nested-loop updates and/or under strong, algorithm-dependent assumptions on the policies, such as uniform mixing and uniform exploration. Technically, to address the challenges posed by the coupled update equations arising from the single-loop implementation, as well as the potentially unbounded iterates induced by off-policy learning, our analysis is based on a coupled Lyapunov drift framework. Specifically, we establish a geometric convergence rate for the actor and an

\tilde{\mathcal{O}}(1/T)

convergence rate for the critic, and combine the two Lyapunov drift inequalities through a cross-domination property. We believe this analytical framework is of independent interest and may be applicable to other coupled iterative algorithms with unbounded

Ishaq Hamza, Zaiwei Chen

IISc · Edwardson School of Industrial Engineering, Purdue University · Purdue IE

Policy Gradient Last-Iterate Convergence Natural Policy Gradient Actor-Critic Methods Policy Learning Sample-Efficient RL+1

Ask PDF

May 11, 2026

Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework

In this work, we show that natural policy gradient, a core algorithm in reinforcement learning, admits an exact formulation as a smoothed and averaged form of policy iteration. Specifically, we introduce doubly smoothed policy iteration (DSPI), a Bellman-operator framework in which each policy is obtained by applying a regularized greedy step to a weighted average of past

Q

-functions. DSPI includes policy iteration, dual-averaged policy iteration, natural policy gradient, and more general policy dual averaging methods as special cases. Using only monotonicity and contraction of smoothed Bellman operators, we prove distribution-free global geometric convergence of DSPI. Consequently, standard natural policy gradient and policy dual averaging achieve an iteration complexity of

\mathcal{O}((1-γ)^{-1}\log((1-γ)^{-1}ε^{-1}))

for computing an

ε

-optimal policy, without modifying the MDP, adding regularization beyond the mirror map inherent in the update, or using adaptive, trajectory-dependent stepsizes. For the unregularized greedy case, corresponding to dual-averaged policy iteration, we also prove finite termination. The same Bellman-operator framework further extends to discounted MDPs with linear function approximation and stochastic shortest path problems.

Phalguni Nanda, Zaiwei Chen

Edwardson School of Industrial Engineering, Purdue University

Policy Gradient Reinforcement Learning Natural Gradient Methods Natural Policy Gradient Policy Optimization Policy Iteration+2

Ask PDF

Apr 1, 2026

Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Games

This letter studies multi-agent reinforcement learning in partially observable Markov potential games. Solving this problem is challenging due to partial observability, decentralized information, and the curse of dimensionality. First, to address the first two challenges, we leverage the common information framework, which allows agents to act based on both shared and local information. Second, to ensure tractability, we study an internal state that compresses accumulated information, preventing it from growing unboundedly over time. We then implement an internal state-based natural policy gradient method to find Nash equilibria of the Markov potential game. Our main contribution is to establish a non-asymptotic convergence bound for this method. Our theoretical bound decomposes into two interpretable components: a statistical error term that also arises in standard Markov potential games, and an approximation error capturing the use of finite-state controllers. Finally, simulations across multiple partially observable environments demonstrate that the proposed method using finite-state controllers achieves consistent improvements in performance compared to the setting where only the current observation is used.

Wonseok Yang, Thinh T. Doan

University of Texas at Austin, Austin, TX, 78712 USA

Natural Policy Gradient Multi-Agent Reinforcement Learning Policy Gradient Game Theory Partially Observable Markov Decision Processes

Ask PDF

Mar 30, 2026

Functional Natural Policy Gradients

We propose a cross-fitted debiasing device for policy learning from offline data. A key consequence of the resulting learning principle is

\sqrt N

regret even for policy classes with complexity greater than Donsker, provided a product-of-errors nuisance remainder is

O(N^{-1/2})

. The regret bound factors into a plug-in policy error factor governed by policy-class complexity and an environment nuisance factor governed by the complexity of the environment dynamics, making explicit how one may be traded against the other.

Aurelien Bibaut, Houssam Zenati, Thibaud Rahier +1

Natural Policy Gradient Policy Learning Offline RL Regret Minimization in RL Policy Gradient

Ask PDF

Mar 9, 2026

Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learning

While standard reinforcement learning optimizes a single reward signal, many applications require optimizing a nonlinear utility

f(J_1^π,\dots,J_M^π)

over multiple objectives, where each

J_m^π

denotes the expected discounted return of a distinct reward function. A common approach is concave scalarization, which captures important trade-offs such as fairness and risk sensitivity. However, nonlinear scalarization introduces a fundamental challenge for policy gradient methods: the gradient depends on

\partial f(J^π)

, while in practice only empirical return estimates

\hat J

are available. Because

f

is nonlinear, the plug-in estimator is biased (

\mathbb{E}[\partial f(\hat J)] \neq \partial f(\mathbb{E}[\hat J])

), leading to persistent gradient bias that degrades sample complexity. In this work we identify and overcome this bias barrier in concave-scalarized multi-objective reinforcement learning. We show that existing policy-gradient methods suffer an intrinsic

\widetilde{\mathcal{O}}(ε^{-4})

sample complexity due to this bias. To address this issue, we develop a Natural Policy Gradient (NPG) algorithm equipped with a multi-level Monte Carlo (MLMC) estimator that controls the bias of the scalarization gradient while maintaining low sampling cost. We prove that this approach achieves the optimal

\widetilde{\mathcal{O}}(ε^{-2})

sample complexity for computing an

ε

-optimal policy. Furthermore, we show that when the scalarization function is second-order smooth, the first-order bias cancels automatically, allowing vanilla NPG to achieve the same

\widetilde{\mathcal{O}}(ε^{-2})

rate without MLMC. Our results provide the first optimal sample complexity guarantees for concave multi-objective reinforcement learning under policy-gradient methods.

Swetha Ganesh, Vaneet Aggarwal

Purdue University, USA 47907

Natural Policy Gradient Multi-Objective Reinforcement Learning Policy Gradient Methods Policy Gradient Sample-Efficient RL

Ask PDF

Mar 8, 2026

Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterization

We study infinite-horizon Constrained Markov Decision Processes (CMDPs) with general policy parameterizations and multi-layer neural network critics. Existing theoretical analyses for constrained reinforcement learning largely rely on tabular policies or linear critics, which limits their applicability to high-dimensional and continuous control problems. We propose a primal-dual natural actor-critic algorithm that integrates neural critic estimation with natural policy gradient updates and leverages Neural Tangent Kernel (NTK) theory to control function-approximation error under Markovian sampling, without requiring access to mixing-time oracles. We establish global convergence and cumulative constraint violation rates of

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

up to approximation errors induced by the policy and critic classes. Our results provide the first such guarantees for CMDPs with general policies and multi-layer neural critics, substantially extending the theoretical foundations of actor-critic methods beyond the linear-critic regime.

Anirudh Satheesh, Pankaj Kumar Barman, Washim Uddin Mondal +1

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

Natural Policy Gradient Constrained RL Actor-Critic Methods Policy Gradient Average-Reward RL

Ask PDF

Feb 27, 2026

Beyond State-Wise Mirror Descent: Offline Policy Optimization with Parametric Policies

We investigate the theoretical aspects of offline reinforcement learning (RL) under general function approximation. While prior works (e.g., Xie et al., 2021) have established the theoretical foundations of learning a good policy from offline data via pessimism, existing algorithms that are computationally tractable (often in an oracle-efficient sense), such as PSPI, only apply to finite and small action spaces. Moreover, these algorithms rely on state-wise mirror descent and require actors to be implicitly induced from the critic functions, failing to accommodate standalone policy parameterization which is ubiquitous in practice. In this work, we address these limitations and extend the theoretical guarantees to parameterized policy classes over large or continuous action spaces. When extending mirror descent to parameterized policies, we identify contextual coupling as the core difficulty, and show how connecting mirror descent to natural policy gradient leads to novel analyses, guarantees, and algorithmic insights, including a surprising unification between offline RL and imitation learning.

Xiang Li, Yuheng Zhang, Nan Jiang

Nanjing University · UIUC

Natural Policy Gradient Offline RL Policy Gradient

Ask PDF

Mar 28, 2024

Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients

Kakade's natural policy gradient method has been studied extensively in recent years, showing linear convergence with and without regularization. We study another natural gradient method based on the Fisher information matrix of the state-action distributions which has received little attention from the theoretical side. Here, the state-action distributions follow the Fisher-Rao gradient flow inside the state-action polytope with respect to a linear potential. Therefore, we study Fisher-Rao gradient flows of linear programs more generally and show linear convergence with a rate that depends on the geometry of the linear program. Equivalently, this yields an estimate on the error induced by entropic regularization of the linear program which improves existing results. We extend these results and show sublinear convergence for perturbed Fisher-Rao gradient flows and natural gradient flows up to an approximation error. In particular, these general results cover the case of state-action natural policy gradients.

Johannes Müller, Semih Çaycı, Guido Montúfar

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

Policy Gradient Optimization Convergence Analysis Natural Gradient Methods Natural Policy Gradient Constrained Optimization Linear Programming

Ask PDF