mlsanityData to 7 Oct 2026

On Linear Convergence of Policy Gradient Methods for Finite MDPs

arXiv 2007.11120 ↗First posted 21 Jul 2020cs.LG math.OC stat.MLcited by 51

Not on the map. Why?

Abstract (arXiv)

We revisit the finite time analysis of policy gradient methods in the one of the simplest settings: finite state and action MDPs with a policy class consisting of all stochastic policies and with exact gradient evaluations. There has been some recent work viewing this setting as an instance of smooth non-linear optimization problems and showing sub-linear convergence rates with small step-sizes. Here, we take a different perspective based on connections with policy iteration and show that many variants of policy gradient methods succeed with large step-sizes and attain a linear rate of convergence.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). First posted on arXiv 21 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 11; 2023: 18; 2024: 13; 2025: 5; 2026: 2.

51 papers.

Sort:

By area:

  1. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  2. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 67
  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. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 38
  6. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  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. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  10. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  11. 2024Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergencecited by 18
  12. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
38 more
  1. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  2. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 15
  3. 2021Adaptive Discretization in Online Reinforcement Learningcited by 12
  4. 2022Geometry and convergence of natural policy gradient methodscited by 12
  5. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  6. 2023Efficient Exploration via Epistemic-Risk-Seeking Policy Optimizationcited by 10
  7. 2023Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methodscited by 9
  8. 2022Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulatorcited by 8
  9. 2022On the convex formulations of robust Markov decision processescited by 8
  10. 2023Provably Convergent Policy Optimization via Metric-aware Trust Region Methodscited by 6
  11. 2024Policy Mirror Descent with Lookaheadcited by 6
  12. 2024On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learningcited by 6
  13. 2021Dr Jekyll and Mr Hyde: the Strange Case of Off-Policy Policy Updatescited by 5
  14. 2023On the Second-Order Convergence of Biased Policy Gradient Algorithmscited by 5
  15. 2024Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradientscited by 5
  16. 2023Policy Gradient Converges to the Globally Optimal Policy for Nearly Linear-Quadratic Regulatorscited by 4
  17. 2024The Definitive Guide to Policy Gradients in Deep Reinforcement Learning: Theory, Algorithms and Implementationscited by 4
  18. 2024RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasonercited by 4
  19. 2023Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theoremscited by 3
  20. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  21. 2024Functional Acceleration for Policy Mirror Descentcited by 3
  22. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  23. 2022Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimizationcited by 2
  24. 2023Matryoshka Policy Gradient for Entropy-Regularized RL: Convergence and Global Optimalitycited by 2
  25. 2023On the Linear Convergence of Policy Gradient under Hadamard Parameterizationcited by 2
  26. 2024Mollification Effects of Policy Gradient Methodscited by 2
  27. 2024Solving Multi-Model MDPs by Coordinate Ascent and Dynamic Programmingcited by 2
  28. 2024Fast Convergence of Softmax Policy Mirror Ascentcited by 2
  29. 2025Convergence of Policy Mirror Descent Beyond Compatible Function Approximationcited by 2
  30. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  31. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  32. 2023Resilient Constrained Reinforcement Learningcited by 1
  33. 2024Dual Approximation Policy Optimizationcited by 1
  34. 2026Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluationcited by 1
  35. 2023Acceleration in Policy Optimizationcited by 0
  36. 2023Global Convergence of Policy Gradient Methods in Reinforcement Learning, Games and Controlcited by 0
  37. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0
  38. 2025Imitate Optimal Policy: Prevail and Induce Action Collapse in Policy Gradientcited by 0

50 most cited of 51 All 51 (JSON)