# On the Global Convergence Rates of Softmax Policy Gradient Methods

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

## Key facts

- Cited by 264 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2020.

## Built on by (most cited first, 30 of 264)

- [Training Language Models to Self-Correct via Reinforcement Learning](https://mlsanity.com/paper/2409.12917/) (2024)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [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)
- [Efficient Online Reinforcement Learning for Diffusion Policy](https://mlsanity.com/paper/2502.00361/) (2025)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [UFT: Unifying Supervised and Reinforcement Fine-Tuning](https://mlsanity.com/paper/2505.16984/) (2025)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Softmax Policy Gradient Methods Can Take Exponential Time to Converge](https://mlsanity.com/paper/2102.11270/) (2021)
- [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)
- [Consistent Paths Lead to Truth: Self-Rewarding Reinforcement Learning for LLM Reasoning](https://mlsanity.com/paper/2506.08745/) (2025)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [QuestA: Expanding Reasoning Capacity in LLMs via Question Augmentation](https://mlsanity.com/paper/2507.13266/) (2025)
- [Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergences](https://mlsanity.com/paper/2107.08285/) (2021)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [MADE: Exploration via Maximizing Deviation from Explored Regions](https://mlsanity.com/paper/2106.10268/) (2021)
- [PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2308.02585/) (2023)
- [On Entropy Control in LLM-RL Algorithms](https://mlsanity.com/paper/2509.03493/) (2025)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2307.08875/) (2023)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization](https://mlsanity.com/paper/2110.08923/) (2021)

## Abstract (arXiv)

We make three contributions toward better understanding policy gradient methods in the tabular setting. First, we show that with the true gradient, policy gradient with a softmax parametrization converges at a O(1/t) rate, with constants depending on the problem and initialization. This result significantly expands the recent asymptotic convergence results. The analysis relies on two findings: that the softmax policy gradient satisfies a Lojasiewicz inequality, and the minimum probability of an optimal action during optimization can be bounded in terms of its initial value. Second, we analyze entropy regularized policy gradient and show that it enjoys a significantly faster linear convergence rate O(e-c · t) toward softmax optimal policy (c > 0). This result resolves an open question in the recent literature. Finally, combining the above two results and additional new Omega(1/t) lower bound results, we explain how entropy regularization improves policy optimization, even with the true gradient, from the perspective of convergence rate. The separation of rates is further explained using the notion of non-uniform Lojasiewicz degree. These results provide a theoretical understanding of the impact of entropy and corroborate existing empirical studies.