mlsanityData to 14 Oct 2026

A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence

arXiv 2301.13139 ↗First posted 30 Jan 2023stat.ML cs.LG math.OCcited by 30

Not on the map. Why?

Abstract (arXiv)

Modern policy optimization methods in reinforcement learning, such as TRPO and PPO, owe their success to the use of parameterized policies. However, while theoretical guarantees have been established for this class of algorithms, especially in the tabular setting, the use of general parameterization schemes remains mostly unjustified. In this work, we introduce a novel framework for policy optimization based on mirror descent that naturally accommodates general parameterizations. The policy class induced by our scheme recovers known classes, e.g., softmax, and generates new ones depending on the choice of mirror map. Using our framework, we obtain the first result that guarantees linear convergence for a policy-gradient-based method involving general parameterization. To demonstrate the ability of our framework to accommodate general parameterization schemes, we provide its sample complexity when using shallow neural networks, show that it represents an improvement upon the previous best results, and empirically validate the effectiveness of our theoretical claims on classic control tasks.

Key facts. Cited by 30 papers in the map (data through 14 Oct 2026). Builds on 69 of its 124 references that are in the map. First posted on arXiv 30 Jan 2023.

Builds on

69 of 124 references.

References · 69

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  5. 2015Trust Region Policy Optimizationcited by 2,580
  6. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  7. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  8. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  9. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,103
  10. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 883
  11. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  12. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
38 more
  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  4. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  5. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  6. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  7. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 286
  8. 2019A Theory of Regularized Markov Decision Processescited by 286
  9. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  10. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  11. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  12. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  13. 2017A unified view of entropy-regularized Markov decision processescited by 182
  14. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  15. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  16. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  17. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  18. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  19. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  20. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  21. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
  22. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  23. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  24. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  25. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  26. 2020Mirror Descent Policy Optimizationcited by 106
  27. 2022Discovered Policy Optimisationcited by 104
  28. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  29. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  30. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  31. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  32. 2013Projection onto the probability simplex: An efficient algorithm with a simple proof, and an applicationcited by 67
  33. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  34. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 52
  35. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  36. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  37. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  38. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39

50 most cited of 69 All 69 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 9; 2025: 9; 2026: 8.

30 papers.

Sort:

By area:

  1. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 18
  2. 2024Elementary Analysis of Policy Gradient Methodscited by 18
  3. 2024Entropy annealing for policy mirror descent in continuous time and spacecited by 12
  4. 2025Distributionally Robust Reinforcement Learning with Human Feedbackcited by 12
  5. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reductioncited by 6
  6. 2024Policy Mirror Descent with Lookaheadcited by 6
  7. 2023On the Second-Order Convergence of Biased Policy Gradient Algorithmscited by 5
  8. 2024Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradientscited by 5
  9. 2024Functional Acceleration for Policy Mirror Descentcited by 3
  10. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  11. 2023On the Linear Convergence of Policy Gradient under Hadamard Parameterizationcited by 2
  12. 2024Enhancing Policy Gradient with the Polyak Step-Size Adaptioncited by 2
18 more
  1. 2024Dual Approximation Policy Optimizationcited by 2
  2. 2025Convergence of Policy Mirror Descent Beyond Compatible Function Approximationcited by 2
  3. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  4. 2023Sample Complexity of Neural Policy Mirror Descent for Policy Optimization on Low-Dimensional Manifoldscited by 1
  5. 2024Learning mirror maps in policy mirror descentcited by 1
  6. 2025Mirror Descent Actor Critic via Bounded Advantage Learningcited by 1
  7. 2025Ordering-based Conditions for Global Convergence of Policy Gradient Methodscited by 1
  8. 2025Monotone and Conservative Policy Iteration Beyond the Tabular Casecited by 1
  9. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learningcited by 1
  10. 2025On the Effect of Regularization in Policy Mirror Descentcited by 1
  11. 2026Actor-Accelerated Policy Dual Averaging for Reinforcement Learning in Continuous Action Spacescited by 1
  12. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  13. 2026Approximation of Log-Partition Function in Policy Mirror Descent Induces Implicit Regularization for LLM Post-Trainingcited by 0
  14. 2026Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Frameworkcited by 0
  15. 2026Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPscited by 0
  16. 2026An analysis of Mirror-Descent Soft Actor-Criticcited by 0
  17. 2026Fast Regularized Policy Mirror Descent with One-Step TD Updatescited by 0
  18. 2026Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPscited by 0