On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games
This addresses theoretical gaps in game theory and machine learning by revealing separations between convergence types, challenging conventional wisdom about their equivalence.
The paper tackles the problem of understanding different convergence criteria for learning dynamics in games, showing that Optimistic Multiplicative Weights Update achieves an O(T^{-1/6}) best-iterate convergence rate in 2×2 matrix games despite slow last-iterate convergence, and establishes a lower bound proving it lacks polynomial random-iterate convergence.
Non-ergodic convergence of learning dynamics in games is widely studied recently because of its importance in both theory and practice. Recent work (Cai et al., 2024) showed that a broad class of learning dynamics, including Optimistic Multiplicative Weights Update (OMWU), can exhibit arbitrarily slow last-iterate convergence even in simple $2 \times 2$ matrix games, despite many of these dynamics being known to converge asymptotically in the last iterate. It remains unclear, however, whether these algorithms achieve fast non-ergodic convergence under weaker criteria, such as best-iterate convergence. We show that for $2\times 2$ matrix games, OMWU achieves an $O(T^{-1/6})$ best-iterate convergence rate, in stark contrast to its slow last-iterate convergence in the same class of games. Furthermore, we establish a lower bound showing that OMWU does not achieve any polynomial random-iterate convergence rate, measured by the expected duality gaps across all iterates. This result challenges the conventional wisdom that random-iterate convergence is essentially equivalent to best-iterate convergence, with the former often used as a proxy for establishing the latter. Our analysis uncovers a new connection to dynamic regret and presents a novel two-phase approach to best-iterate convergence, which could be of independent interest.