# On the Linear convergence of Natural Policy Gradient Algorithm

arXiv: https://arxiv.org/abs/2105.01424 · HTML: https://mlsanity.com/paper/2105.01424/

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 54 references that are in the map.
- First posted on arXiv 4 May 2021.

## Builds on (most cited first, 24 of 24)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [The Information Geometry of Mirror Descent](https://mlsanity.com/paper/1310.7780/) (2013)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy](https://mlsanity.com/paper/1906.10306/) (2019)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2102.09318/) (2021)
- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [Adaptive Sampling for Best Policy Identification in Markov Decision Processes](https://mlsanity.com/paper/2009.13405/) (2020)
- [Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory](https://mlsanity.com/paper/1906.06781/) (2019)
- [Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2004.12956/) (2020)

## Built on by (most cited first, 30 of 48)

- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01050/) (2022)
- [The Role of Baselines in Policy Gradient Optimization](https://mlsanity.com/paper/2301.06276/) (2023)
- [Policy Optimization over General State and Action Spaces](https://mlsanity.com/paper/2211.16715/) (2022)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation](https://mlsanity.com/paper/2105.12540/) (2021)
- [Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2206.00833/) (2022)
- [A general class of surrogate functions for stable and efficient reinforcement learning](https://mlsanity.com/paper/2108.05828/) (2021)
- [Understanding the Effect of Stochasticity in Policy Optimization](https://mlsanity.com/paper/2110.15572/) (2021)
- [Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.11381/) (2023)
- [Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization](https://mlsanity.com/paper/2209.15382/) (2022)
- [Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation](https://mlsanity.com/paper/2106.04096/) (2021)
- [Policy Optimization for Markov Games: Unified Framework and Faster Convergence](https://mlsanity.com/paper/2206.02640/) (2022)
- [Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2206.05357/) (2022)
- [Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity](https://mlsanity.com/paper/2201.09457/) (2022)
- [Geometry and convergence of natural policy gradient methods](https://mlsanity.com/paper/2211.02105/) (2022)
- [Block Policy Mirror Descent](https://mlsanity.com/paper/2201.05756/) (2022)
- [On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spaces](https://mlsanity.com/paper/2201.12332/) (2022)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes](https://mlsanity.com/paper/2403.06806/) (2024)
- [Recurrent Natural Policy Gradient for POMDPs](https://mlsanity.com/paper/2405.18221/) (2024)
- [Understanding Stochastic Natural Gradient Variational Inference](https://mlsanity.com/paper/2406.01870/) (2024)
- [Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction](https://mlsanity.com/paper/2401.01084/) (2024)
- [Strongly-polynomial time and validation analysis of policy gradient methods](https://mlsanity.com/paper/2409.19437/) (2024)
- [Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach](https://mlsanity.com/paper/2510.20235/) (2025)

## Abstract (arXiv)

Markov Decision Processes are classically solved using Value Iteration and Policy Iteration algorithms. Recent interest in Reinforcement Learning has motivated the study of methods inspired by optimization, such as gradient ascent. Among these, a popular algorithm is the Natural Policy Gradient, which is a mirror descent variant for MDPs. This algorithm forms the basis of several popular Reinforcement Learning algorithms such as Natural actor-critic, TRPO, PPO, etc, and so is being studied with growing interest. It has been shown that Natural Policy Gradient with constant step size converges with a sublinear rate of O(1/k) to the global optimal. In this paper, we present improved finite time convergence bounds, and show that this algorithm has geometric (also known as linear) asymptotic convergence rate. We further improve this convergence result by introducing a variant of Natural Policy Gradient with adaptive step sizes. Finally, we compare different variants of policy gradient methods experimentally.