mlsanityData to 14 Oct 2026

On the Global Optimum Convergence of Momentum-based Policy Gradient

arXiv 2110.10116 ↗First posted 19 Oct 2021cs.LG math.OCcited by 26

Not on the map. Why?

Abstract (arXiv)

Policy gradient (PG) methods are popular and efficient for large-scale reinforcement learning due to their relative stability and incremental nature. In recent years, the empirical success of PG methods has led to the development of a theoretical foundation for these methods. In this work, we generalize this line of research by studying the global convergence of stochastic PG methods with momentum terms, which have been demonstrated to be efficient recipes for improving PG methods. We study both the soft-max and the Fisher-non-degenerate policy parametrizations, and show that adding a momentum improves the global optimality sample complexity of vanilla PG methods by tildeO(ε-1.5) and tildeO(ε-1), respectively, where ε>0 is the target tolerance. Our work is the first one that obtains global convergence results for the momentum-based PG methods. For the generic Fisher-non-degenerate policy parametrizations, our result is the first single-loop and finite-batch PG algorithm achieving tildeO(ε-3) global optimality sample complexity. Finally, as a by-product, our methods also provide general framework for analyzing the global convergence rates of stochastic PG methods, which can be easily applied and extended to different PG estimators.

Key facts. Cited by 26 papers in the map (data through 14 Oct 2026). Builds on 38 of its 74 references that are in the map. First posted on arXiv 19 Oct 2021.

Builds on

38 of 74 references.

References · 38

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2015Continuous control with deep reinforcement learningcited by 3,407
  4. 2015Trust Region Policy Optimizationcited by 2,580
  5. 2016Neural Architecture Search with Reinforcement Learningcited by 1,499
  6. 2019On the Convergence of Adam and Beyondcited by 841
  7. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  8. 2018Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understandingcited by 304
  9. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  10. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  11. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  12. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
26 more
  1. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  2. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  3. 2020Exploration-Exploitation in Constrained MDPscited by 149
  4. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 145
  5. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
  6. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  7. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  8. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  9. 2020Sample Efficient Reinforcement Learning with REINFORCEcited by 86
  10. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  11. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  12. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  13. 2018Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselinescited by 68
  14. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  15. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 59
  16. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  17. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  18. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  19. 2020Single-Timescale Actor-Critic Provably Finds Globally Optimal Policycited by 34
  20. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 34
  21. 2020Momentum-Based Policy Gradient Methodscited by 30
  22. 2019Graph Policy Gradients for Large Scale Robot Controlcited by 28
  23. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 24
  24. 2020A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learningcited by 18
  25. 2020Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Samplingcited by 15
  26. 2017Stochastic Variance Reduction for Policy Gradient Estimationcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 6; 2024: 5; 2025: 7; 2026: 5.

26 papers.

Sort:

By area:

  1. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  2. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  3. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 30
  4. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 27
  5. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  6. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  7. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  8. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 13
  9. 2024Learning Optimal Deterministic Policies with Stochastic Policy Gradientscited by 12
  10. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  11. 2025TIC-GRPO: Provable and Efficient Optimization for Reinforcement Learning from Human Feedbackcited by 11
  12. 2023A safe exploration approach to constrained Markov decision processescited by 10
14 more
  1. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
  2. 2023Policy Gradient with Tree Expansioncited by 3
  3. 2024Flipping-based Policy for Chance-Constrained Markov Decision Processescited by 3
  4. 2024On The Global Convergence Of Online RLHF With Neural Parametrizationcited by 3
  5. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  6. 2025Finite-time Convergence Analysis of Actor-Critic with Evolving Rewardcited by 2
  7. 2025Non-Asymptotic Global Convergence of PPO-Clipcited by 2
  8. 2026Rank-1 Approximation of Inverse Fisher for Natural Policy Gradients in Deep Reinforcement Learningcited by 2
  9. 2025Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learningcited by 1
  10. 2026How Log-Barrier Helps Exploration in Policy Optimizationcited by 1
  11. 2025Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learningcited by 0
  12. 2026Variance-Reduced Policy Gradient is Nearly Minimax-Optimalcited by 0
  13. 2026Towards Understanding the Training of GFlowNets: A Theoretical Perspectivecited by 0
  14. 2026When Does Momentum Help in Reinforcement Learning with Verifiable Rewards?cited by 0