mlsanityData to 7 Oct 2026

Global Optimality Guarantees For Policy Gradient Methods

arXiv 1906.01786 ↗First posted 5 Jun 2019cs.LG stat.MLcited by 146

Not on the map. Why?

Abstract (arXiv)

Policy gradients methods apply to complex, poorly understood, control problems by performing stochastic gradient descent over a parameterized class of polices. Unfortunately, even for simple control problems solvable by standard dynamic programming techniques, policy gradient algorithms face non-convex optimization problems and are widely understood to converge only to a stationary point. This work identifies structural properties -- shared by several classic control problems -- that ensure the policy gradient objective function has no suboptimal stationary points despite being non-convex. When these conditions are strengthened, this objective satisfies a Polyak-lojasiewicz (gradient dominance) condition that yields convergence rates. We also provide bounds on the optimality gap of any stationary point when some of these conditions are relaxed.

Key facts. Cited by 146 papers in the map (data through 7 Oct 2026). First posted on arXiv 5 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 21; 2022: 32; 2023: 35; 2024: 27; 2025: 19; 2026: 12.

146 papers.

Sort:

By area:

  1. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  2. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  3. 2022Do Differentiable Simulators Give Better Policy Gradients?cited by 83
  4. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 67
  5. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  6. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  7. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  8. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  9. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  10. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  11. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  12. 2021Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergencescited by 40
38 more
  1. 2022Finite-time analysis of single-timescale actor-criticcited by 30
  2. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  3. 2024Regressing the Relative Future: Efficient Policy Optimization for Multi-turn RLHFcited by 29
  4. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  5. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  6. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  7. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  8. 2023Submodular Reinforcement Learningcited by 23
  9. 2022Policy Optimization over General State and Action Spacescited by 21
  10. 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 19
  11. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  12. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
  13. 2022Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learningcited by 18
  14. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  15. 2024Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergencecited by 18
  16. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
  17. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  18. 2023PPO-Clip Attains Global Optimality: Towards Deeper Understandings of Clippingcited by 17
  19. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 16
  20. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  21. 2022Understanding the Complexity Gains of Single-Task RL with a Curriculumcited by 16
  22. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  23. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 15
  24. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  25. 2021Provably Correct Optimization and Exploration with Non-linear Policiescited by 13
  26. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13
  27. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  28. 2023Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RLcited by 13
  29. 2021Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithmcited by 12
  30. 2021On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Controlcited by 12
  31. 2021A Boosting Approach to Reinforcement Learningcited by 12
  32. 2022Finite-Time Analysis of Natural Actor-Critic for POMDPscited by 12
  33. 2022A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimizationcited by 12
  34. 2022Geometry and convergence of natural policy gradient methodscited by 12
  35. 2022On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spacescited by 11
  36. 2023Fast Policy Learning for Linear Quadratic Control with Entropy Regularizationcited by 11
  37. 2024FedRLHF: A Convergence-Guaranteed Federated Framework for Privacy-Preserving and Personalized RLHFcited by 11
  38. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10

50 most cited of 146 All 146 (JSON)