mlsanityData to 7 Oct 2026

Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms

arXiv 2406.10631 ↗First posted 15 Jun 2024cs.GT cs.LG math.OCcited by 14

Not on the map. Why?

Abstract (arXiv)

Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games, both in theory and practice. Particularly popular algorithms include optimistic multiplicative weights update (OMWU) and optimistic gradient-descent-ascent (OGDA). While both algorithms enjoy O(1/T) ergodic convergence to Nash equilibrium in two-player zero-sum games, OMWU offers several advantages including logarithmic dependence on the size of the payoff matrix and widetildeO(1/T) convergence to coarse correlated equilibria even in general-sum games. However, in terms of last-iterate convergence in two-player zero-sum games, an increasingly popular topic in this area, OGDA guarantees that the duality gap shrinks at a rate of O(1/√T), while the best existing last-iterate convergence for OMWU depends on some game-dependent constant that could be arbitrarily large. This begs the question: is this potentially slow last-iterate convergence an inherent disadvantage of OMWU, or is the current analysis too loose? Somewhat surprisingly, we show that the former is true. More generally, we prove that a broad class of algorithms that do not forget the past quickly all suffer the same issue: for any arbitrarily small δ>0, there exists a 2× 2 matrix game such that the algorithm admits a constant duality gap even after 1/δ rounds. This class of algorithms includes OMWU and other standard optimistic follow-the-regularized-leader algorithms.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 24 of its 37 references that are in the map. First posted on arXiv 15 Jun 2024.

Builds on

24 of 37 references.

References · 24

  1. 2023Nash Learning from Human Feedbackcited by 220
  2. 2017Training GANs with Optimismcited by 217
  3. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  4. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  5. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  6. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 129
  7. 2017Cycles in adversarial regularized learningcited by 122
  8. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  9. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  10. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  11. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  12. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
12 more
  1. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 56
  2. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  3. 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 49
  4. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  5. 2017Selling to a No-Regret Buyercited by 43
  6. 2021Online Learning with Optimism and Delaycited by 33
  7. 2022Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalitiescited by 33
  8. 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 30
  9. 2021Last-iterate Convergence in Extensive-Form Gamescited by 27
  10. 2019Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Gamescited by 24
  11. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  12. 2024Strategically-Robust Learning Algorithms for Bidding in First-Price Auctionscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 9; 2026: 4.

14 papers.

Sort:

By area:

  1. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 9
  2. 2024COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferencescited by 8
  3. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 6
  4. 2025Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Gamescited by 3
  5. 2026Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedbackcited by 3
  6. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 3
  7. 2025On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Gamescited by 2
  8. 2025Optimism Without Regularization: Constant Regret in Zero-Sum Gamescited by 2
  9. 2025Convergence of Regret Matching in Potential Games and Constrained Optimizationcited by 2
  10. 2025Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Banditscited by 1
  11. 2025Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformationcited by 0
  12. 2025Unregularized Linear Convergence in Zero-Sum Game from Preference Feedbackcited by 0
2 more
  1. 2026Asymptotic Universal Alignment: A New Alignment Framework via Test-Time Scalingcited by 0
  2. 2026Last-Iterate Convergence of Optimistic Multiplicative Weight Updatecited by 0