Interpolating Between Softmax Policy Gradient and Neural Replicator Dynamics with Capped Implicit Exploration

Dustin Morrill, Esra'a Saleh, Michael Bowling, Amy GreenwaldarXiv 2022 · DOI · arXiv

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.

Figure 3: Average reward vs. IX parameter (η) for two different environments. The orange line represents NeuRD-CIX, while the blue dashed line represents the SPG baseline. As η increases, NeuRD-CIX performance stabilizes and approaches SPG.

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

Abstract

Neural replicator dynamics (NeuRD) is an alternative to the foundational softmax policy gradient (SPG) algorithm motivated by online learning and evolutionary game theory. The NeuRD expected update is designed to be nearly identical to that of SPG, however, we show that the Monte Carlo updates differ in a substantial way: the importance correction accounting for a sampled action is nullified in the SPG update, but not in the NeuRD update. Naturally, this causes the NeuRD update to have higher variance than its SPG counterpart. Building on implicit exploration algorithms in the adversarial bandit setting, we introduce capped implicit exploration (CIX) estimates that allow us to construct NeuRD-CIX, which interpolates between this aspect of NeuRD and SPG. We show how CIX estimates can be used in a black-box reduction to construct bandit algorithms with regret bounds that hold with high probability and the benefits this entails for NeuRD-CIX in sequential decision-making settings. Our analysis reveals a bias--variance tradeoff between SPG and NeuRD, and shows how theory predicts that NeuRD-CIX will perform well more consistently than NeuRD while retaining NeuRD's advantages over SPG in non-stationary environments.
BibTeX
@misc{morrill2022interpolating,
  author = {Dustin Morrill and Esra'a Saleh and Michael Bowling and Amy Greenwald},
  title = {{Interpolating Between Softmax Policy Gradient and Neural Replicator Dynamics with Capped Implicit Exploration}},
  year = {2022},
  eprint = {2206.02036},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.02036},
}
Figure