mlsanityData to 7 Oct 2026

Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes

arXiv 2102.00135 ↗First posted 30 Jan 2021cs.LG cs.AI math.OCcited by 149

Not on the map. Why?

Abstract (arXiv)

We present new policy mirror descent (PMD) methods for solving reinforcement learning (RL) problems with either strongly convex or general convex regularizers. By exploring the structural properties of these overall highly nonconvex problems we show that the PMD methods exhibit fast linear rate of convergence to the global optimality. We develop stochastic counterparts of these methods, and establish an cal O(1/ε) (resp., cal O(1/ε2)) sampling complexity for solving these RL problems with strongly (resp., general) convex regularizers using different sampling schemes, where ε denote the target accuracy. We further show that the complexity for computing the gradients of these regularizers, if necessary, can be bounded by cal O(logγ ε) [(1-γ)L/μ]1/2log (1/ε) (resp., cal O (logγ ε ) (L/ε)1/2)for problems with strongly (resp., general) convex regularizers. Here γ denotes the discounting factor. To the best of our knowledge, these complexity bounds, along with our algorithmic developments, appear to be new in both optimization and RL literature. The introduction of these convex regularizers also greatly expands the flexibility and applicability of RL models.

Key facts. Cited by 149 papers in the map (data through 7 Oct 2026). Builds on 10 of its 29 references that are in the map. First posted on arXiv 30 Jan 2021.

Builds on

10 of 29 references.

References · 10

  1. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  2. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  3. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  4. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  5. 2020Mirror Descent Policy Optimizationcited by 102
  6. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 42
  7. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  8. 2013On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operatorscited by 29
  9. 2020Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learningcited by 22
  10. 2020Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithmscited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 28; 2023: 25; 2024: 26; 2025: 23; 2026: 30.

149 papers.

Sort:

By area:

  1. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  2. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  3. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  4. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  5. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  6. 2025Efficient Online Reinforcement Learning for Diffusion Policycited by 61
  7. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  8. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  9. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  10. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  11. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  12. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
38 more
  1. 2021Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergencescited by 40
  2. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  3. 2022Mirror Learning: A Unifying Framework of Policy Optimisationcited by 31
  4. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
  5. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  6. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  7. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  8. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  9. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  10. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  11. 2023The Role of Baselines in Policy Gradient Optimizationcited by 25
  12. 2022Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Gamescited by 24
  13. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  14. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  15. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  16. 2022Policy Optimization over General State and Action Spacescited by 21
  17. 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 19
  18. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
  19. 2021Understanding the Effect of Stochasticity in Policy Optimizationcited by 18
  20. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  21. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  22. 2025One-Step Flow Policy Mirror Descentcited by 18
  23. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
  24. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  25. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  26. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  27. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 15
  28. 2021Bregman Gradient Policy Optimizationcited by 15
  29. 2022Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learningcited by 15
  30. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  31. 2023Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Setscited by 15
  32. 2022Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexitycited by 14
  33. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  34. 2022KL-Entropy-Regularized RL with a Generative Model is Minimax Optimalcited by 13
  35. 2021On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Controlcited by 12
  36. 2022Finite-Time Analysis of Natural Actor-Critic for POMDPscited by 12
  37. 2022Geometry and convergence of natural policy gradient methodscited by 12
  38. 2022On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spacescited by 11

50 most cited of 149 All 149 (JSON)