TL;DR
This paper introduces Softmax Policy Mirror Ascent (SPMA), a novel policy gradient algorithm that achieves faster convergence than existing methods in both tabular and function approximation settings. SPMA offers strong theoretical guarantees and competitive empirical performance, bridging the gap between theoretical advancements and practical applications in reinforcement learning.
What Problem Does This Paper Address?
Reinforcement learning (RL) relies heavily on policy gradient (PG) methods to learn optimal policies. While theoretical research has shown global convergence for PG methods in simplified settings, these algorithms are often not practical. Conversely, widely used deep RL algorithms like TRPO and PPO have limited theoretical analysis, especially in realistic function approximation settings. This creates a significant gap between theoretically sound methods and those used in practice. This paper aims to bridge this gap by developing a PG algorithm that is both theoretically principled and empirically effective.
Methods
The core contribution is the Softmax Policy Mirror Ascent (SPMA) algorithm. SPMA is derived from mirror ascent, a powerful optimization technique, but applied in the dual space of logits rather than probabilities, which is a key departure from standard Natural Policy Gradient (NPG). This allows SPMA to avoid the need for action normalization and leads to a more direct update of probabilities.
Key aspects of the method include:
- Mirror Ascent in Logit Space: SPMA uses a log-sum-exp mirror map, which is crucial for its theoretical properties and practical performance.
- Tabular Setting: For small state-action spaces, SPMA is proven to achieve linear convergence, matching NPG and outperforming standard softmax policy gradient (SPG).
- Function Approximation (FA): SPMA is extended to handle large state-action spaces using function approximation (e.g., linear models, neural networks). This extension does not require compatible function approximation, making it more practical than some NPG extensions. It also only requires solving convex softmax classification problems, unlike some other methods.
- Projected Mirror Ascent: For FA, SPMA employs projected mirror ascent to stay within the feasible set of policies defined by the function approximator.
Datasets
The paper evaluates SPMA on standard benchmarks:
- Atari 2600 games: Used for evaluating performance with CNN-based actor networks.
- MuJoCo environments: Used for evaluating performance with MLP-based actor networks in continuous control tasks.
- Tabular MDPs: Specifically, CliffWorld and FrozenLake, used to validate theoretical results in simpler settings.
Key Insights and Ideas
- Logit Space is Key: Applying mirror ascent in the logit space, rather than the probability space, is a critical insight that unlocks faster convergence and avoids common pitfalls like action normalization.
- Bridging Theory and Practice: SPMA successfully bridges the gap between theoretical guarantees and practical performance, a long-standing challenge in RL.
- No Compatible Function Approximation Needed: The extension of SPMA to function approximation is more practical because it bypasses the need for compatible function approximation, a requirement for some NPG variants.
- Convexity is Sufficient: For linear function approximation, SPMA only requires solving convex optimization problems, which are generally easier to handle than non-convex ones.
Key Results
- Tabular MDPs: SPMA achieves linear convergence, matching NPG and outperforming SPG.
- Function Approximation: SPMA demonstrates competitive or superior empirical performance compared to MDPO, PPO, and TRPO on Atari and MuJoCo benchmarks.
- On Atari games, SPMA matches or surpasses MDPO and outperforms PPO and TRPO.
- On MuJoCo tasks, SPMA outperforms PPO and achieves similar or better results than MDPO.
- Theoretical Guarantees: SPMA is proven to achieve linear convergence rates in both tabular and function approximation settings, even with inexact advantage estimates.
Limitations and Future Work
- Hyperparameter Tuning: The paper acknowledges that hyperparameter tuning, particularly for the step-size, can be computationally expensive (e.g., grid searches). Future work aims to develop techniques for adaptive step-size tuning.
- Off-Policy Variant: The authors plan to develop and analyze an off-policy variant of SPMA.
- Exploration: While the theoretical analysis assumes full support of the initial state distribution, practical exploration strategies might be needed in some scenarios.
- Terminal States: The empirical verification of $C_t$ being non-zero excludes certain terminal states in FrozenLake. The authors suggest that theorems could be modified to exclude such states.
Summary updated