mlsanityData to 7 Oct 2026

Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games

arXiv 2208.09855 ↗First posted 21 Aug 2022cs.GT cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

This paper proposes Mutation-Driven Multiplicative Weights Update (M2WU) for learning an equilibrium in two-player zero-sum normal-form games and proves that it exhibits the last-iterate convergence property in both full and noisy feedback settings. In the former, players observe their exact gradient vectors of the utility functions. In the latter, they only observe the noisy gradient vectors. Even the celebrated Multiplicative Weights Update (MWU) and Optimistic MWU (OMWU) algorithms may not converge to a Nash equilibrium with noisy feedback. On the contrary, M2WU exhibits the last-iterate convergence to a stationary point near a Nash equilibrium in both feedback settings. We then prove that it converges to an exact Nash equilibrium by iteratively adapting the mutation term. We empirically confirm that M2WU outperforms MWU and OMWU in exploitability and convergence rates.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 27 of its 60 references that are in the map. First posted on arXiv 21 Aug 2022.

Builds on

27 of 60 references.

References · 27

  1. 2017Training GANs with Optimismcited by 217
  2. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  3. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  4. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  5. 2017Cycles in adversarial regularized learningcited by 122
  6. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  7. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  8. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  9. 2016Learning in games with continuous action sets and unknown payoff functionscited by 78
  10. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  11. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  12. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
15 more
  1. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  2. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 59
  3. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  4. 2018Bandit learning in concave N-person gamescited by 32
  5. 2019Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descentcited by 31
  6. 2020Approximate exploitability: Learning a best response in large gamescited by 23
  7. 2021Survival of the strictest: Stable and unstable equilibria under regularized learning with partial informationcited by 22
  8. 2020Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapescited by 21
  9. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  10. 2014Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variantscited by 19
  11. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  12. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  13. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  14. 2022Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Gamescited by 8
  15. 2022Last-iterate Convergence to Trembling-hand Perfect Equilibriacited by 1

Built on by

Cited by year (2026 to 7 Oct)

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

9 papers.

  1. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  2. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 6
  3. 2025RSPO: Regularized Self-Play Alignment of Large Language Modelscited by 5
  4. 2024Corrupted Learning Dynamics in Gamescited by 4
  5. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 3
  6. 2025NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibriacited by 1
  7. 2024Decentralized Online Learning in General-Sum Stackelberg Gamescited by 0
  8. 2024Last Iterate Convergence in Monotone Mean Field Gamescited by 0
  9. 2025Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformationcited by 0