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.
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.
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