mlsanityData to 7 Oct 2026

Neural Policy Gradient Methods: Global Optimality and Rates of Convergence

arXiv 1909.01150 ↗First posted 29 Aug 2019cs.LG math.OC stat.MLcited by 157

Not on the map. Why?

Abstract (arXiv)

Policy gradient methods with actor-critic schemes demonstrate tremendous empirical successes, especially when the actors and critics are parameterized by neural networks. However, it remains less clear whether such "neural" policy gradient methods converge to globally optimal policies and whether they even converge at all. We answer both the questions affirmatively in the overparameterized regime. In detail, we prove that neural natural policy gradient converges to a globally optimal policy at a sublinear rate. Also, we show that neural vanilla policy gradient converges sublinearly to a stationary point. Meanwhile, by relating the suboptimality of the stationary points to the representation power of neural actor and critic classes, we prove the global optimality of all stationary points under mild regularity conditions. Particularly, we show that a key to the global optimality and convergence is the "compatibility" between the actor and critic, which is ensured by sharing neural architectures and random initializations across the actor and critic. To the best of our knowledge, our analysis establishes the first global optimality and convergence guarantees for neural policy gradient methods.

Key facts. Cited by 157 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Aug 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 4; 2021: 38; 2022: 34; 2023: 27; 2024: 26; 2025: 18; 2026: 10.

157 papers.

Sort:

By area:

  1. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  3. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  4. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  5. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  6. 2022Jump-Start Reinforcement Learningcited by 102
  7. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  8. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  9. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  10. 2025What Makes a Reward Model a Good Teacher? An Optimization Perspectivecited by 70
  11. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  12. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
38 more
  1. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  2. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  3. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  4. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  5. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  6. 2024Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalizationcited by 39
  7. 2021On the Approximation of Cooperative Heterogeneous Multi-Agent Reinforcement Learning (MARL) using Mean Field Control (MFC)cited by 31
  8. 2022Finite-time analysis of single-timescale actor-criticcited by 30
  9. 2023Policy Optimization for Continuous Reinforcement Learningcited by 30
  10. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  11. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  12. 2021Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approachcited by 27
  13. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  14. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  15. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  16. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 25
  17. 2023Order Matters: Agent-by-agent Policy Optimizationcited by 24
  18. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  19. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  20. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  21. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  22. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  23. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  24. 2022Policy Optimization over General State and Action Spacescited by 21
  25. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  26. 2021Doubly Robust Off-Policy Actor-Critic: Convergence and Optimalitycited by 20
  27. 2022Convergence of Policy Gradient for Entropy Regularized MDPs with Neural Network Approximation in the Mean-Field Regimecited by 20
  28. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 19
  29. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 19
  30. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 19
  31. 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 19
  32. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
  33. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  34. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  35. 2024Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergencecited by 18
  36. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  37. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
  38. 2023PPO-Clip Attains Global Optimality: Towards Deeper Understandings of Clippingcited by 17

50 most cited of 157 All 157 (JSON)