# Elementary Analysis of Policy Gradient Methods

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

## Key facts

- Cited by 18 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 9 of its 32 references that are in the map.
- First posted on arXiv 4 Apr 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, 9 of 9)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Softmax Policy Gradient Methods Can Take Exponential Time to Converge](https://mlsanity.com/paper/2102.11270/) (2021)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence](https://mlsanity.com/paper/2301.13139/) (2023)
- [Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.11381/) (2023)
- [On the Convergence of Projected Policy Gradient for Any Constant Step Sizes](https://mlsanity.com/paper/2311.01104/) (2023)

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

- [Improving Multi-Step Reasoning Abilities of Large Language Models with Direct Advantage Policy Optimization](https://mlsanity.com/paper/2412.18279/) (2024)
- [Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs](https://mlsanity.com/paper/2405.13136/) (2024)
- [On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning](https://mlsanity.com/paper/2410.04108/) (2024)
- [Proximal Point Nash Learning from Human Feedback](https://mlsanity.com/paper/2505.19731/) (2025)
- [On the Convergence of Single-Timescale Actor-Critic](https://mlsanity.com/paper/2410.08868/) (2024)
- [Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster](https://mlsanity.com/paper/2503.00229/) (2025)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Fast Convergence of Softmax Policy Mirror Ascent](https://mlsanity.com/paper/2411.12042/) (2024)
- [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025)
- [Optimal Rates of Convergence for Entropy Regularization in Discounted Markov Decision Processes](https://mlsanity.com/paper/2406.04163/) (2024)
- [Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead](https://mlsanity.com/paper/2506.07054/) (2025)
- [Sampling Complexity of TD and PPO in RKHS](https://mlsanity.com/paper/2509.24991/) (2025)
- [When Errors Can Be Beneficial: A Categorization of Imperfect Rewards for Policy Gradient](https://mlsanity.com/paper/2604.25872/) (2026)
- [Convergence of Steepest Descent and Adam under Non-Uniform Smoothness](https://mlsanity.com/paper/2605.30648/) (2026)
- [Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum](https://mlsanity.com/paper/2602.01505/) (2026)
- [Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes](https://mlsanity.com/paper/2607.22982/) (2026)
- [Fine-Tuning on Self-Generated and Reward-Weighted Data: Learning Dynamics, Convergence Rates, and Benefits of Off-Policyness](https://mlsanity.com/paper/2609.36945/) (2026)
- [Fast Regularized Policy Mirror Descent with One-Step TD Updates](https://mlsanity.com/paper/2609.39837/) (2026)

## Abstract (arXiv)

Projected policy gradient under the simplex parameterization, policy gradient and natural policy gradient under the softmax parameterization, are fundamental algorithms in reinforcement learning. There have been a flurry of recent activities in studying these algorithms from the theoretical aspect. Despite this, their convergence behavior is still not fully understood, even given the access to exact policy evaluations. In this paper, we focus on the discounted MDP setting and conduct a systematic study of the aforementioned policy optimization methods. Several novel results are presented, including 1) global linear convergence of projected policy gradient for any constant step size, 2) sublinear convergence of softmax policy gradient for any constant step size, 3) global linear convergence of softmax natural policy gradient for any constant step size, 4) global linear convergence of entropy regularized softmax policy gradient for a wider range of constant step sizes than existing result, 5) tight local linear convergence rate of entropy regularized natural policy gradient, and 6) a new and concise local quadratic convergence rate of soft policy iteration without the assumption on the stationary distribution under the optimal policy. New and elementary analysis techniques have been developed to establish these results.