mlsanityData to 7 Oct 2026

Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction

arXiv 2401.01084 ↗First posted 2 Jan 2024cs.LG math.OCcited by 4

Not on the map. Why?

Abstract (arXiv)

Natural policy gradient (NPG) and its variants are widely-used policy search methods in reinforcement learning. Inspired by prior work, a new NPG variant coined NPG-HM is developed in this paper, which utilizes the Hessian-aided momentum technique for variance reduction, while the sub-problem is solved via the stochastic gradient descent method. It is shown that NPG-HM can achieve the global last iterate ε-optimality with a sample complexity of O(ε-2), which is the best known result for natural policy gradient type methods under the generic Fisher non-degenerate policy parameterizations. The convergence analysis is built upon a relaxed weak gradient dominance property tailored for NPG under the compatible function approximation framework, as well as a neat way to decompose the error when handling the sub-problem. Moreover, numerical experiments on Mujoco-based environments demonstrate the superior performance of NPG-HM over other state-of-the-art policy gradient methods.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 39 of its 57 references that are in the map. First posted on arXiv 2 Jan 2024.

Builds on

39 of 57 references.

References · 39

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2016OpenAI Gymcited by 1,684
  4. 2018Soft Actor-Critic Algorithms and Applicationscited by 1,179
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  7. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  8. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  9. 2021Reinforcement learning based recommender systems: A surveycited by 187
  10. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  11. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  12. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
27 more
  1. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 117
  2. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  3. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  4. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  5. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  6. 2020Mirror Descent Policy Optimizationcited by 102
  7. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  8. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  9. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  10. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  11. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 58
  12. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  13. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  14. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  15. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  16. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  17. 2020Momentum-Based Policy Gradient Methodscited by 28
  18. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  19. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 22
  20. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 19
  21. 2019Smoothing Policies and Safe Policy Gradientscited by 18
  22. 2020A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learningcited by 17
  23. 2020Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Samplingcited by 15
  24. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 15
  25. 2022Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexitycited by 14
  26. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 11
  27. 2022Decentralized Natural Policy Gradient with Variance Reduction for Collaborative Multi-Agent Reinforcement Learningcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  2. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  3. 2025A Variance-Reduced Cubic-Regularized Newton for Policy Optimizationcited by 0
  4. 2026Fast Regularized Policy Mirror Descent with One-Step TD Updatescited by 0