Abstract
Softmax Policy Gradient (SPG) and Neural Replicator Dynamics (NeuRD) share nearly identical theoretical expected updates but diverge significantly in practical performance due to variance in sampled updates. This paper introduces Capped Implicit Exploration (CIX), a novel estimator that allows for a controlled interpolation between these two algorithms. By adjusting a single parameter, researchers can balance the stability of SPG with the theoretical advantages of NeuRD in non-stationary environments.
Introduction: The Stability-Optimality Tradeoff
In reinforcement learning, selecting a policy optimization algorithm often involves a choice between the industry-standard Softmax Policy Gradient (SPG) and the game-theoretically inspired Neural Replicator Dynamics (NeuRD). While SPG is renowned for its stability, NeuRD is designed to excel in non-stationary environments, such as multi-agent games.
Despite their theoretical similarities, their Monte Carlo implementations behave differently. In SPG, importance sampling weights are effectively canceled out by the policy's structure, leading to low-variance updates. NeuRD lacks this inherent cancellation, resulting in high-variance, noisy updates that often lead to unstable learning trajectories. The challenge lies in retaining NeuRD's game-theoretic properties without the crippling variance.
Methods: Capped Implicit Exploration (CIX)
The authors propose NeuRD-CIX, which leverages "Implicit Exploration" (IX) techniques typically found in bandit problems. The core of this approach is the CIX estimator, which modifies the importance sampling denominator to prevent exploding updates when action probabilities are low.
Standard importance sampling uses $1/\pi$. CIX replaces this with a capped denominator: $$\beta = \min\{1, \pi + \eta\}$$
This parameter $\eta$ serves as a mathematical bridge:
- At $\eta = 0$, the algorithm recovers the original, high-variance NeuRD.
- At $\eta \ge 1$, the update behaves similarly to the stable SPG.
- Intermediate values allow for a tunable bias-variance tradeoff.
Theorem 1 in the paper provides formal proof that CIX allows for "high-probability" regret bounds, ensuring the algorithm performs reliably across individual runs, not just on average.
Experimental Evaluation
The researchers evaluated NeuRD-CIX on two classic benchmarks: Catch (from bsuite) and Cart Pole (from OpenAI Gym). These single-agent tasks were used to determine if NeuRD-CIX could serve as a drop-in replacement for standard actor-critic architectures.
Key Results
- Reliability and Stability: As shown in the figures, NeuRD without CIX ($\eta=0$) is highly unreliable, characterized by significant variance and lower average rewards. Increasing $\eta$ consistently improves stability and performance, bringing NeuRD-CIX closer to the SPG baseline.
- The Performance Gap: In these stationary single-agent tasks, SPG generally maintained a slight performance edge over NeuRD-CIX, even at optimal $\eta$ settings. This suggests subtle differences in how unsampled actions are handled between the two approaches.
- Environment Sensitivity: The impact of the IX parameter varied by task; for instance, Cart Pole was less sensitive to changes in $\eta$ than Catch, indicating that the optimal bias-variance tradeoff is environment-dependent.
Conclusion and Future Work
This work identifies that SPG's stability is largely a result of a "lucky" mathematical cancellation of importance weights. By introducing CIX, the authors provide a mechanism to manually introduce bias to suppress variance in NeuRD.
While this study established a baseline in stationary environments, future work will explore NeuRD-CIX in complex, non-stationary multi-agent settings like Poker or StarCraft. Additionally, investigating how these dynamics interact with more complex neural architectures, such as Transformers, remains an open area of research.
Summary updated