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 the field of algorithmic game theory and multi-agent reinforcement learning, finding a Nash Equilibrium (NE)—a state where no player can improve their outcome by unilaterally changing their strategy—is a fundamental objective. The standard approach for solving these games is the Follow the Regularized Leader (FTRL) algorithm. While FTRL is highly effective at finding the NE when strategies are averaged over time, it frequently fails to achieve last-iterate convergence. Instead of settling on the equilibrium, the actual strategies often enter a "limit cycle," orbiting the equilibrium indefinitely without ever reaching it.
To address this, researchers have introduced Mutant Follow the Regularized Leader (M-FTRL). By incorporating a mutation mechanism inspired by evolutionary biology, M-FTRL ensures that the final strategy produced by the algorithm reliably converges to a (near) Nash Equilibrium at an exponential rate, even in challenging environments like those with bandit feedback.
The M-FTRL Framework
Mutation as a Stabilizing Force
The core innovation of M-FTRL is the addition of a "mutation" term to the standard FTRL update rule. This concept is borrowed from Replicator-Mutator Dynamics (RMD) in evolutionary biology, where mutation maintains genetic diversity within a population. In the context of optimization, this mutation acts as a form of "friction" or damping. It introduces a small perturbation that pushes the strategy toward a fixed reference strategy (typically a uniform distribution), preventing the oscillatory behavior common in minimax optimization.
Continuous-Time Analysis
The authors demonstrate that M-FTRL with entropy regularization is mathematically equivalent to RMD. By applying Lyapunov stability theory, the paper proves that this system naturally gravitates toward a unique stationary point. Unlike many no-regret algorithms that converge at sub-linear rates (such as $1/\sqrt{t}$), M-FTRL achieves exponential convergence ($e^{-t}$) to this stationary point under continuous-time dynamics.
Solving the Approximation Gap
A fixed mutation parameter $\mu$ typically leads the algorithm to a $2\mu$-Nash Equilibrium—an approximation of the true equilibrium. To bridge this gap, the authors propose Adaptive M-FTRL. In this version, the reference strategy is periodically updated to match the current strategy. This "zooming" effect allows the algorithm to refine its search and converge precisely to the true Nash Equilibrium of the original game.
Experimental Methodology
The effectiveness of M-FTRL was evaluated using several benchmark game structures:
- Biased Rock-Paper-Scissors (BRPS): A modified version of the classic game designed to induce aggressive cycling in standard algorithms.
- M-Eq: A normal-form game specifically constructed to feature multiple Nash Equilibria, testing the algorithm's ability to handle non-unique solutions.
- Random Utility Games: Large-scale games with action spaces of 10 and 50 to evaluate scalability and general performance across diverse payoff matrices.
Key Insights and Results
Breaking the Continuum
In many zero-sum games, equilibria exist as a "continuum" or a connected set of points. Standard algorithms often drift aimlessly along these lines. M-FTRL effectively "dissolves" these continua into isolated, stable stationary points, making the convergence process significantly more predictable and stable.
Superior Convergence Rates
Simulations revealed that M-FTRL converges to the Nash Equilibrium substantially faster than both standard FTRL and the state-of-the-art Optimistic FTRL (O-FTRL). Furthermore, in games with multiple equilibria, M-FTRL consistently identifies a unique stationary point regardless of the initial starting conditions, whereas O-FTRL's final state is often highly sensitive to initialization.
Robustness Under Bandit Feedback
One of the most significant findings is M-FTRL's performance under bandit feedback, where agents only observe the reward for the specific action they took rather than the entire payoff table. While O-FTRL trajectories often become chaotic and fail to converge in bandit settings, M-FTRL maintains clear last-iterate convergence. The authors provide an unbiased estimator that enables this stability even with limited information.
Conclusion and Future Work
M-FTRL represents a significant step forward in achieving last-iterate convergence for zero-sum games. By bridging the gap between online learning and evolutionary game theory, the algorithm provides a robust framework that is both theoretically sound and empirically superior in speed and stability.
While the current research focuses on two-player, zero-sum, normal-form games, the success of mutation-driven stability suggests promising applications in more complex environments. Future work will explore extending M-FTRL to multi-player games, Markov games, and extensive-form games (such as Poker), where high-dimensional strategy spaces present even greater challenges for convergence.
Summary updated