mlsanityData to 7 Oct 2026

On the Global Convergence Rates of Softmax Policy Gradient Methods

arXiv 2005.06392 ↗First posted 13 May 2020cs.LG stat.MLcited by 258

Not on the map. Why?

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.

Key facts. Cited by 258 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 May 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 48; 2022: 47; 2023: 37; 2024: 43; 2025: 45; 2026: 37.

258 papers.

Sort:

By area:

  1. 2024Training Language Models to Self-Correct via Reinforcement Learningcited by 405
  2. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  3. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  4. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  5. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  6. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  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. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 67
  11. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  12. 2025Efficient Online Reinforcement Learning for Diffusion Policycited by 61
38 more
  1. 2025UFT: Unifying Supervised and Reinforcement Fine-Tuningcited by 58
  2. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  3. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  4. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  5. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  6. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  7. 2025Consistent Paths Lead to Truth: Self-Rewarding Reinforcement Learning for LLM Reasoningcited by 43
  8. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  9. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  10. 2021Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergencescited by 40
  11. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  12. 2025QuestA: Expanding Reasoning Capacity in LLMs via Question Augmentationcited by 39
  13. 2025On Entropy Control in LLM-RL Algorithmscited by 39
  14. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 38
  15. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  16. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  17. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  18. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
  19. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  20. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  21. 2024Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferencescited by 27
  22. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  23. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  24. 2023Vanishing Gradients in Reinforcement Finetuning of Language Modelscited by 26
  25. 2024The Crucial Role of Samplers in Online Direct Preference Optimizationcited by 26
  26. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  27. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  28. 2023The Role of Baselines in Policy Gradient Optimizationcited by 25
  29. 2022Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Gamescited by 24
  30. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  31. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 23
  32. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  33. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  34. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  35. 2022Policy Optimization over General State and Action Spacescited by 21
  36. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 20
  37. 2022Convergence of Policy Gradient for Entropy Regularized MDPs with Neural Network Approximation in the Mean-Field Regimecited by 20
  38. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 19

50 most cited of 258 All 258 (JSON)