Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games
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.