On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Mastering the game of Stratego with model-free multiagent reinforcement learningScience, 2022
- Superhuman AI for multiplayer pokerScience, 2019
- Superhuman AI for heads-up no-limit poker: Libratus beats top professionalsScience, 2018
- DeepStack: Expert-level artificial intelligence in heads-up no-limit pokerScience, 2017
- Applying Metric Regularity to Compute a Condition Measure of a Smoothing Algorithm for Matrix GamesSIAM Journal on Optimization, 2010
- Chaos in learning a simple two-person gameProceedings of the National Academy of Sciences, 2002
- On linear convergence of iterative methods for the variational inequality problemJournal of Computational and Applied Mathematics, 1995