mlsanityData to 7 Oct 2026

Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization

arXiv 2007.06558 ↗First posted 13 Jul 2020stat.ML cs.IT cs.LGcited by 170

Not on the map. Why?

Abstract (arXiv)

Natural policy gradient (NPG) methods are among the most widely used policy optimization algorithms in contemporary reinforcement learning. This class of methods is often applied in conjunction with entropy regularization -- an algorithmic scheme that encourages exploration -- and is closely related to soft policy iteration and trust region policy optimization. Despite the empirical success, the theoretical underpinnings for NPG methods remain limited even for the tabular setting. This paper develops textitnon-asymptotic convergence guarantees for entropy-regularized NPG methods under softmax parameterization, focusing on discounted Markov decision processes (MDPs). Assuming access to exact policy evaluation, we demonstrate that the algorithm converges linearly -- or even quadratically once it enters a local region around the optimal policy -- when computing optimal value functions of the regularized MDP. Moreover, the algorithm is provably stable vis-`a-vis inexactness of policy evaluation. Our convergence results accommodate a wide range of learning rates, and shed light upon the role of entropy regularization in enabling fast convergence.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 32; 2022: 35; 2023: 36; 2024: 32; 2025: 18; 2026: 17.

170 papers.

Sort:

By area:

  1. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  2. 2024DPO Meets PPO: Reinforced Token Optimization for RLHFcited by 126
  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. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  7. 2025ReinFlow: Fine-tuning Flow Matching Policy with Online Reinforcement Learningcited by 83
  8. 2024Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHFcited by 73
  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. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
38 more
  1. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  2. 2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 46
  3. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  4. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  5. 2022Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guaranteescited by 42
  6. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  7. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  8. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  9. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  10. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  11. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
  12. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  13. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  14. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  15. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  16. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  17. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  18. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  19. 2023When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learningcited by 26
  20. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  21. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  22. 2023The Role of Baselines in Policy Gradient Optimizationcited by 25
  23. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learningcited by 25
  24. 2022Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Gamescited by 24
  25. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  26. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  27. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  28. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  29. 2022Policy Optimization over General State and Action Spacescited by 21
  30. 2023Recent Developments in Machine Learning Methods for Stochastic Control and Gamescited by 19
  31. 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 19
  32. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  33. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
  34. 2021Understanding the Effect of Stochasticity in Policy Optimizationcited by 18
  35. 2022Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learningcited by 18
  36. 2024Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergencecited by 18
  37. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
  38. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17

50 most cited of 170 All 170 (JSON)