# On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games

arXiv: https://arxiv.org/abs/2503.02825 · HTML: https://mlsanity.com/paper/2503.02825/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 23 references that are in the map.
- First posted on arXiv 4 Mar 2025.

## Builds on (most cited first, 13 of 13)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning](https://mlsanity.com/paper/2206.15378/) (2022)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [The Consensus Game: Language Model Generation via Equilibrium Search](https://mlsanity.com/paper/2310.09139/) (2023)
- [Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities](https://mlsanity.com/paper/2205.08446/) (2022)
- [On Last-Iterate Convergence Beyond Zero-Sum Games](https://mlsanity.com/paper/2203.12056/) (2022)
- [Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games](https://mlsanity.com/paper/2202.00237/) (2022)
- [Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms](https://mlsanity.com/paper/2406.10631/) (2024)

## Built on by (most cited first, 2 of 2)

- [Optimism Without Regularization: Constant Regret in Zero-Sum Games](https://mlsanity.com/paper/2506.16736/) (2025)
- [Learning from Delayed Feedback in Games via Extra Prediction](https://mlsanity.com/paper/2509.22426/) (2025)

## Abstract (arXiv)

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 × 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× 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.