Separation of Nonergodic Uniform Convergence Rates for Regularized Learning in Games

Abstract

Convergence of Optimistic Learning in Games and the Role of Forgetfulness Online learning algorithms solve games by repeatedly updating players’ strategies. A natural hope is that the latest strategy improves at a predictable rate. This paper shows that this intuition can fail for optimistic follow-the-regularized-leader methods, including the widely used optimistic multiplicative weights algorithm. In two-player zero-sum games, the authors separate three notions of nonergodic performance: last-iterate, random-iterate, and best-iterate convergence. They prove that no instance-independent last-iterate rate exists for the broad algorithmic family and establish strong lower bounds for random iterates. Yet, a useful positive result remains; in 2 × 2 games, optimistic multiplicative weights achieve a uniform best-iterate rate. The analysis traces the slowdown to a lack of “forgetfulness”; accumulated past losses can keep the dynamics moving away from equilibrium long after they reach its neighborhood. The results suggest that practitioners should distinguish carefully between the latest strategy, a randomly selected strategy, and the best observed strategy when evaluating learning dynamics.