# Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 42 references that are in the map.
- First posted on arXiv 18 Oct 2023.

## Builds on (most cited first, 13 of 13)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Sample Efficient Actor-Critic with Experience Replay](https://mlsanity.com/paper/1611.01224/) (2016)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- [A Dynamical Systems Perspective on Nesterov Acceleration](https://mlsanity.com/paper/1905.07436/) (2019)
- [The Role of Baselines in Policy Gradient Optimization](https://mlsanity.com/paper/2301.06276/) (2023)
- [Understanding the Effect of Stochasticity in Policy Optimization](https://mlsanity.com/paper/2110.15572/) (2021)
- [Accelerated Methods for α-Weakly-Quasi-Convex Problems](https://mlsanity.com/paper/1710.00797/) (2017)
- [A Note on Nesterov's Accelerated Method in Nonconvex Optimization: a Weak Estimate Sequence Approach](https://mlsanity.com/paper/2006.08548/) (2020)

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

- [Fast Convergence of Softmax Policy Mirror Ascent](https://mlsanity.com/paper/2411.12042/) (2024)
- [Stabilizing Policy Gradient Methods via Reward Profiling](https://mlsanity.com/paper/2511.16629/) (2025)
- [Consensus Based Stochastic Control](https://mlsanity.com/paper/2501.17801/) (2025)
- [When Does Momentum Help in Reinforcement Learning with Verifiable Rewards?](https://mlsanity.com/paper/2610.20413/) (2026)

## Abstract (arXiv)

Various acceleration approaches for Policy Gradient (PG) have been analyzed within the realm of Reinforcement Learning (RL). However, the theoretical understanding of the widely used momentum-based acceleration method on PG remains largely open. In response to this gap, we adapt the celebrated Nesterov's accelerated gradient (NAG) method to policy optimization in RL, termed textitAccelerated Policy Gradient (APG). To demonstrate the potential of APG in achieving fast convergence, we formally prove that with the true gradient and under the softmax policy parametrization, APG converges to an optimal policy at rates: (i) tildeO(1/t2) with constant step sizes; (ii) O(e-ct) with exponentially-growing step sizes. To the best of our knowledge, this is the first characterization of the convergence rates of NAG in the context of RL. Notably, our analysis relies on one interesting finding: Regardless of the parameter initialization, APG ends up entering a locally nearly-concave regime, where APG can significantly benefit from the momentum, within finite iterations. Through numerical validation and experiments on the Atari 2600 benchmarks, we confirm that APG exhibits a tildeO(1/t2) rate with constant step sizes and a linear convergence rate with exponentially-growing step sizes, significantly improving convergence over the standard PG.