Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games

Kenshi Abe, Mitsuki Sakamoto, Atsushi Iwasaki

Abstract

In this study, we consider a variant of the Follow the Regularized Leader (FTRL) dynamics in two-player zero-sum games. FTRL is guaranteed to converge to a Nash equilibrium when time-averaging the strategies, while a lot of variants suffer from the issue of limit cycling behavior, i.e., lack the last-iterate convergence guarantee. To this end, we propose mutant FTRL (M-FTRL), an algorithm that introduces mutation for the perturbation of action probabilities. We then investigate the continuous-time dynamics of M-FTRL and provide the strong convergence guarantees toward stationary points that approximate Nash equilibria under full-information feedback. Furthermore, our simulation demonstrates that M-FTRL can enjoy faster convergence rates than FTRL and optimistic FTRL under full-information feedback and surprisingly exhibits clear convergence under bandit feedback.

Introduction

In competitive multi-agent environments, such as zero-sum games, the primary objective is to reach a Nash equilibrium—a state where no player can improve their outcome by unilaterally changing their strategy. While the Follow the Regularized Leader (FTRL) algorithm is a standard approach for finding these equilibria, it typically only guarantees convergence in the average of strategies over time. In practice, the "last iterate"—the current strategy at any given step—often fails to settle, instead entering a "limit cycle" where it orbits the equilibrium indefinitely.

Recent advancements like Optimistic FTRL (O-FTRL) have addressed last-iterate convergence in specific scenarios, but these often require unique equilibria and are difficult to analyze under bandit feedback (where players only observe their own payoffs). This paper introduces Mutant FTRL (M-FTRL), which leverages a biologically inspired mutation mechanism to stabilize learning and ensure fast last-iterate convergence.

Methodology: Mutation as a Stabilizer

The core innovation of M-FTRL is the introduction of a mutation parameter ($\mu$). This mechanism perturbs action probabilities toward a reference strategy, typically a uniform distribution. Mathematically, this prevents any action probability from reaching zero and provides a "centripetal force" that pulls the learning trajectory toward the interior of the strategy space.

Evolution of dynamics from Replicator Dynamics (RD) to Replicator-Mutator Dynamics (RMD) with varying mutation rates $\mu$. Higher mutation leads to faster convergence to a stable interior point.

Replicator-Mutator Dynamics (RMD)

The authors demonstrate that in continuous time, M-FTRL with entropy regularization is equivalent to Replicator-Mutator Dynamics (RMD). As shown in Figure 1, standard dynamics (RD) often result in closed orbits or limit cycles. By increasing $\mu$, these cycles are broken, and the system is driven toward a stable stationary point.

Adaptive Reference Strategy

While mutation stabilizes the system, it naturally pulls the strategy toward an approximate equilibrium (specifically, a $2\mu$-Nash equilibrium). To achieve convergence to the true Nash equilibrium, the authors propose an adaptive reference strategy. By periodically updating the reference strategy to match the current best-performing strategy, the algorithm can iteratively refine its position until it reaches the true equilibrium.

Experimental Evaluation

The efficacy of M-FTRL was tested across several simulated environments designed to challenge standard learning algorithms:

  1. Biased Rock-Paper-Scissors (BRPS): An asymmetric payoff structure that typically induces cycling.
  2. Multiple Nash Equilibria Game (M-Eq): A game with a continuum of equilibria to test if the algorithm can stabilize at a single point.
  3. Random Utility Games: Synthetic games with action spaces of size 10 and 50 to evaluate scalability.

Key Results and Discussion

Empirical results confirm that M-FTRL provides significant advantages in both stability and speed. The algorithm achieves exponential convergence to stationary points ($O(e^{-\mu\xi t})$), outperforming both standard FTRL and O-FTRL in terms of exploitability reduction.

Convergence performance (exploitability) of M-FTRL variants against baselines in Biased Rock-Paper-Scissors (BRPS), Multiple Nash Equilibria (M-Eq), and Random Utility games.

As illustrated in Figure 4, the adaptive version of M-FTRL consistently reaches near-zero exploitability faster than baselines. Notably, in the M-Eq game, M-FTRL demonstrates robustness by always converging to the same unique stationary point, regardless of the starting position, whereas other algorithms might wander or settle on different points in the equilibrium continuum.

Perhaps most significantly, M-FTRL exhibits clear last-iterate convergence under bandit feedback. This is a major milestone, as many state-of-the-art algorithms require full-information feedback to maintain stability. By using an importance-weighted estimator for utilities, M-FTRL remains effective even when information is restricted.

Conclusion

M-FTRL offers a robust solution to the limit-cycling problem in zero-sum games. By transforming neutral stability into asymptotic stability through mutation, it ensures reliable last-iterate convergence. Future work will explore extending these dynamics to more complex structures, such as extensive-form games and multi-agent reinforcement learning (MARL) scenarios, where non-stationarity remains a critical challenge.

Summary updated

Abstract

In this study, we consider a variant of the Follow the Regularized Leader (FTRL) dynamics in two-player zero-sum games. FTRL is guaranteed to converge to a Nash equilibrium when time-averaging the strategies, while a lot of variants suffer from the issue of limit cycling behavior, i.e., lack the last-iterate convergence guarantee. To this end, we propose mutant FTRL (M-FTRL), an algorithm that introduces mutation for the perturbation of action probabilities. We then investigate the continuous-time dynamics of M-FTRL and provide the strong convergence guarantees toward stationary points that approximate Nash equilibria under full-information feedback. Furthermore, our simulation demonstrates that M-FTRL can enjoy faster convergence rates than FTRL and optimistic FTRL under full-information feedback and surprisingly exhibits clear convergence under bandit feedback.
BibTeX
@inproceedings{abe2022mutation,
  author = {Kenshi Abe and Mitsuki Sakamoto and Atsushi Iwasaki},
  title = {{Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=StZVqP8sqe5},
}
Figure