mlsanityData to 7 Oct 2026

On the Convergence Rates of Policy Gradient Methods

arXiv 2201.07443 ↗First posted 19 Jan 2022math.OC cs.LGcited by 115

Not on the map. Why?

Abstract (arXiv)

We consider infinite-horizon discounted Markov decision problems with finite state and action spaces and study the convergence rates of the projected policy gradient method and a general class of policy mirror descent methods, all with direct parametrization in the policy space. First, we develop a theory of weak gradient-mapping dominance and use it to prove sharper sublinear convergence rate of the projected policy gradient method. Then we show that with geometrically increasing step sizes, a general class of policy mirror descent methods, including the natural policy gradient method and a projected Q-descent method, all enjoy a linear rate of convergence without relying on entropy or other strongly convex regularization. Finally, we also analyze the convergence rate of an inexact policy mirror descent method and estimate its sample complexity under a simple generative model.

Key facts. Cited by 115 papers in the map (data through 7 Oct 2026). Builds on 21 of its 51 references that are in the map. First posted on arXiv 19 Jan 2022.

Builds on

21 of 51 references.

References · 21

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2021Convex optimizationcited by 2,479
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  5. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  6. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  7. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  8. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  9. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  10. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  11. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  12. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
9 more
  1. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 74
  2. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  3. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  4. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 51
  5. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  6. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  7. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  8. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
  9. 2016Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methodscited by 35

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 16; 2023: 25; 2024: 33; 2025: 21; 2026: 20.

115 papers.

Sort:

By area:

  1. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 67
  2. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  3. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  4. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  5. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
  6. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  7. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  8. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  9. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  10. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  11. 2022Policy Optimization over General State and Action Spacescited by 21
  12. 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 19
38 more
  1. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  2. 2024Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergencecited by 18
  3. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  4. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  5. 2024Elementary Analysis of Policy Gradient Methodscited by 17
  6. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  7. 2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 16
  8. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 15
  9. 2022Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexitycited by 14
  10. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  11. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  12. 2022Geometry and convergence of natural policy gradient methodscited by 12
  13. 2023Policy Mirror Descent Inherently Explores Action Spacecited by 11
  14. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  15. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  16. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  17. 2023Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methodscited by 9
  18. 2023Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularizationcited by 8
  19. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  20. 2023Fractal Landscapes in Policy Optimizationcited by 8
  21. 2024Understanding Stochastic Natural Gradient Variational Inferencecited by 8
  22. 2024Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPscited by 7
  23. 2024Operator World Models for Reinforcement Learningcited by 7
  24. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
  25. 2023Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimizationcited by 6
  26. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processescited by 6
  27. 2024Policy Mirror Descent with Lookaheadcited by 6
  28. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
  29. 2024On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learningcited by 6
  30. 2024Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradientscited by 5
  31. 2024Strongly-polynomial time and validation analysis of policy gradient methodscited by 5
  32. 2024Enhancing Safety in Reinforcement Learning with Human Feedback via Rectified Policy Optimizationcited by 5
  33. 2023Policy Gradient Converges to the Globally Optimal Policy for Nearly Linear-Quadratic Regulatorscited by 4
  34. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 4
  35. 2022An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithmscited by 3
  36. 2023Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theoremscited by 3
  37. 2023Decision-Aware Actor-Critic with Function Approximation and Theoretical Guaranteescited by 3
  38. 2024Approximate Global Convergence of Independent Learning in Multi-Agent Systemscited by 3

50 most cited of 115 All 115 (JSON)