mlsanityData to 14 Oct 2026

Fast Convergence of Softmax Policy Mirror Ascent

arXiv 2411.12042 ↗First posted 18 Nov 2024cs.LG cs.AI cs.ROcited by 2

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Natural policy gradient (NPG) is a common policy optimization algorithm and can be viewed as mirror ascent in the space of probabilities. Recently, Vaswani et al. [2021] introduced a policy gradient method that corresponds to mirror ascent in the dual space of logits. We refine this algorithm, removing its need for a normalization across actions and analyze the resulting method (referred to as SPMA). For tabular MDPs, we prove that SPMA with a constant step-size matches the linear convergence of NPG and achieves a faster convergence than constant step-size (accelerated) softmax policy gradient. To handle large state-action spaces, we extend SPMA to use a log-linear policy parameterization. Unlike that for NPG, generalizing SPMA to the linear function approximation (FA) setting does not require compatible function approximation. Unlike MDPO, a practical generalization of NPG, SPMA with linear FA only requires solving convex softmax classification problems. We prove that SPMA achieves linear convergence to the neighbourhood of the optimal value function. We extend SPMA to handle non-linear FA and evaluate its empirical performance on the MuJoCo and Atari benchmarks. Our results demonstrate that SPMA consistently achieves similar or better performance compared to MDPO, PPO and TRPO.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 31 of its 49 references that are in the map. First posted on arXiv 18 Nov 2024.

Builds on

31 of 49 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs21 May
  2. 2024Elementary Analysis of Policy Gradient Methods4 Apr

Other references · 29

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  4. 2016OpenAI Gymcited by 1,736
  5. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  6. 2014Convex Optimization: Algorithms and Complexitycited by 575
  7. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  8. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
  9. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  10. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  11. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  12. 2020Mirror Descent Policy Optimizationcited by 106
17 more
  1. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 52
  2. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 48
  3. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  4. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  5. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  6. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 43
  7. 2022Mirror Learning: A Unifying Framework of Policy Optimisationcited by 31
  8. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  9. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  10. 2021A general class of surrogate functions for stable and efficient reinforcement learningcited by 18
  11. 2021Understanding the Effect of Stochasticity in Policy Optimizationcited by 18
  12. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 18
  13. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  14. 2021Optimization Issues in KL-Constrained Approximate Policy Iterationcited by 10
  15. 2023Target-based Surrogates for Stochastic Optimizationcited by 4
  16. 2023Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learningcited by 4
  17. 2023Decision-Aware Actor-Critic with Function Approximation and Theoretical Guaranteescited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Fastercited by 3
  2. 2026Fine-Tuning on Self-Generated and Reward-Weighted Data: Learning Dynamics, Convergence Rates, and Benefits of Off-Policynesscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Global Convergence of Natural Policy Gradient with Hessian-aided Momentum Variance Reduction
  2. 2026Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes
  3. 2026Beyond Softmax and Entropy: Convergence Rates of Policy Gradients with f-SoftArgmax Parameterization & Coupled Regularization
  4. 2024Learning mirror maps in policy mirror descent
  5. 2024Fast Stochastic Policy Gradient: Negative Momentum for Reinforcement Learning
  6. 2024Performance of NPG in Countable State-Space Average-Cost RL
  7. 2026Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework
  8. 2026Soft Deterministic Policy Gradient with Gaussian Smoothing