Fast Convergence of Softmax Policy Mirror Ascent

Reza Asad, Reza Babanezhad Harikandeh, Issam H. Laradji, Nicolas Le Roux, Sharan Vaswani

Abstract

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.

Introduction: Bridging the Theory-Practice Gap

In Reinforcement Learning (RL), a significant gap exists between theoretically grounded algorithms and practical implementations. Theoretically robust methods like Natural Policy Gradient (NPG) offer linear convergence—reaching optimal policies exponentially fast—but are notoriously difficult to implement with neural networks due to the requirement of "compatible function approximation." Conversely, popular practical methods like Proximal Policy Optimization (PPO) and Trust Region Policy Optimization (TRPO) lack strong theoretical guarantees in deep learning settings, with much of their success attributed to specific implementation details rather than underlying mathematical principles.

This research introduces Softmax Policy Mirror Ascent (SPMA), a refined algorithm designed to be both mathematically principled and robust enough for high-dimensional tasks.

Methodology: Mirror Ascent in Logit Space

The core innovation of SPMA is the application of Mirror Ascent in the "dual space" of logits rather than the space of probabilities.

The Logit Space and Mirror Maps

SPMA utilizes a log-sum-exp mirror map, effectively performing optimization in the space of raw scores (logits) before they are passed through a softmax function. This approach is naturally more robust; while updates in probability space can easily overshoot, logit-space updates are more stable. Unlike previous logit-based methods, SPMA removes the need for explicit normalization across actions, simplifying implementation and increasing stability.

Reframing as Convex Classification

When extending to function approximation (FA), SPMA transforms the policy update into a convex softmax classification problem. This is a significant advantage over competitors like Mirror Descent Policy Optimization (MDPO), which often rely on non-convex surrogates. By reframing the update as a weighted multi-class classification problem, SPMA can leverage standard Stochastic Gradient Descent (SGD) techniques from supervised learning.

Empirical Evaluation

The authors evaluated SPMA against industry standards (MDPO, PPO, and TRPO) across two major benchmarks: Atari 2600 for discrete actions and MuJoCo for continuous control.

Atari 2600 Benchmarks

In high-dimensional discrete action tasks, SPMA demonstrated superior or competitive performance. It consistently matched or surpassed MDPO and significantly outperformed PPO and TRPO variants across games like BeamRider, DemonAttack, Alien, and Amidar.

Performance of SPMA vs baselines on four Atari 2600 games over 10 million timesteps.

MuJoCo Continuous Control

On robotics tasks such as Hopper, Walker2d, and Ant, SPMA matched or exceeded the performance of MDPO and PPO. While a highly fine-tuned "TRPO-constrained" variant performed slightly better in specific instances, SPMA remained more computationally efficient and simpler to implement due to its convex update structure.

Performance of SPMA vs baselines on four MuJoCo continuous control tasks.

Key Insights and Results

  • Linear Convergence: SPMA matches the linear convergence rate of NPG in tabular settings without requiring compatible function approximation.
  • Robustness: Empirical tests showed SPMA is significantly less sensitive to step-size ($\eta$) choices compared to standard Softmax Policy Gradient (SPG).
  • Efficiency: By using an inner loop of 5–15 SGD iterations to solve the classification-style update, SPMA achieves high sample efficiency and stability.

Limitations and Future Work

While robust, SPMA currently requires manual tuning for the "outer-loop" step-size. Future research could explore adaptive step-size techniques to automate this process. Additionally, as an on-policy algorithm, SPMA requires fresh data for every update. Developing an off-policy variant to reuse historical data would further enhance its sample efficiency for real-world applications.

Summary updated

Abstract

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.
BibTeX
@inproceedings{asad2025fast,
  author = {Reza Asad and Reza Babanezhad Harikandeh and Issam H. Laradji and Nicolas Le Roux and Sharan Vaswani},
  title = {{Fast Convergence of Softmax Policy Mirror Ascent}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=VCJ8NfVrcO},
}
Figure