mlsanityData to 14 Oct 2026

On the Linear convergence of Natural Policy Gradient Algorithm

arXiv 2105.01424 ↗First posted 4 May 2021cs.LGcited by 48

Not on the map. Why?

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.

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

24 of 54 references.

References · 24

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2019A Theory of Regularized Markov Decision Processescited by 286
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  5. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  6. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  7. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  8. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  9. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  10. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  11. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  12. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
12 more
  1. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  2. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  3. 2013The Information Geometry of Mirror Descentcited by 54
  4. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  5. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 43
  6. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  7. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  8. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  9. 2013Improved and Generalized Upper Bounds on the Complexity of Policy Iterationcited by 21
  10. 2020Adaptive Sampling for Best Policy Identification in Markov Decision Processescited by 20
  11. 2019Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theorycited by 17
  12. 2020Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithmscited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 18; 2023: 6; 2024: 9; 2025: 7; 2026: 1.

48 papers.

Sort:

By area:

  1. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  2. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 110
  3. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  4. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  5. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  6. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 32
  7. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 30
  8. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 26
  9. 2023The Role of Baselines in Policy Gradient Optimizationcited by 25
  10. 2022Policy Optimization over General State and Action Spacescited by 23
  11. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  12. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
36 more
  1. 2021A general class of surrogate functions for stable and efficient reinforcement learningcited by 18
  2. 2021Understanding the Effect of Stochasticity in Policy Optimizationcited by 18
  3. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 18
  4. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  5. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 16
  6. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  7. 2022Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learningcited by 15
  8. 2022Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexitycited by 14
  9. 2022Geometry and convergence of natural policy gradient methodscited by 12
  10. 2022Block Policy Mirror Descentcited by 11
  11. 2022On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spacescited by 11
  12. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  13. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processescited by 9
  14. 2024Recurrent Natural Policy Gradient for POMDPscited by 8
  15. 2024Understanding Stochastic Natural Gradient Variational Inferencecited by 8
  16. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 6
  17. 2024Strongly-polynomial time and validation analysis of policy gradient methodscited by 5
  18. 2025Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approachcited by 5
  19. 2022Algorithm for Constrained Markov Decision Process with Linear Convergencecited by 4
  20. 2024Maximum Entropy On-Policy Actor-Critic via Entropy Advantage Estimationcited by 4
  21. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  22. 2021Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learningcited by 2
  23. 2022Accelerating Primal-dual Methods for Regularized Markov Decision Processescited by 2
  24. 2023On the Linear Convergence of Policy Gradient under Hadamard Parameterizationcited by 2
  25. 2023Global Convergence of Policy Gradient Methods in Reinforcement Learning, Games and Controlcited by 2
  26. 2024Dual Approximation Policy Optimizationcited by 2
  27. 2024Fast Convergence of Softmax Policy Mirror Ascentcited by 2
  28. 2025Convergence of Policy Mirror Descent Beyond Compatible Function Approximationcited by 2
  29. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  30. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  31. 2022On the Convergence of Policy in Unregularized Policy Mirror Descentcited by 1
  32. 2022Coordinate Ascent for Off-Policy RL with Global Convergence Guaranteescited by 1
  33. 2025Ordering-based Conditions for Global Convergence of Policy Gradient Methodscited by 1
  34. 2023Acceleration in Policy Optimizationcited by 0
  35. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0
  36. 2026Fast Regularized Policy Mirror Descent with One-Step TD Updatescited by 0