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

arXiv: https://arxiv.org/abs/2401.01084 · HTML: https://mlsanity.com/paper/2401.01084/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 39 of its 57 references that are in the map.
- First posted on arXiv 2 Jan 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 39)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Soft Actor-Critic Algorithms and Applications](https://mlsanity.com/paper/1812.05905/) (2018)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [Mirror Descent Policy Optimization](https://mlsanity.com/paper/2005.09814/) (2020)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [Momentum-Based Policy Gradient Methods](https://mlsanity.com/paper/2007.06680/) (2020)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11677/) (2023)

## Built on by (most cited first, 6 of 6)

- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025)
- [A Variance-Reduced Cubic-Regularized Newton for Policy Optimization](https://mlsanity.com/paper/2507.10120/) (2025)
- [Fast Regularized Policy Mirror Descent with One-Step TD Updates](https://mlsanity.com/paper/2609.39837/) (2026)
- [Towards Understanding the Training of GFlowNets: A Theoretical Perspective](https://mlsanity.com/paper/2610.13711/) (2026)
- [When Does Momentum Help in Reinforcement Learning with Verifiable Rewards?](https://mlsanity.com/paper/2610.20413/) (2026)

## 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.