# Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games arXiv: https://arxiv.org/abs/2208.09855 ยท HTML: https://mlsanity.com/paper/2208.09855/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Builds on 27 of its 60 references that are in the map. - First posted on arXiv 21 Aug 2022. ## Builds on (most cited first, 27 of 27) - [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) - [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019) - [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018) - [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017) - [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018) - [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018) - [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019) - [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016) - [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021) - [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018) - [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021) - [From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization](https://mlsanity.com/paper/2002.08456/) (2020) - [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020) - [Tight last-iterate convergence rates for no-regret learning in multi-player games](https://mlsanity.com/paper/2010.13724/) (2020) - [Bandit learning in concave N-person games](https://mlsanity.com/paper/1810.01925/) (2018) - [Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent](https://mlsanity.com/paper/1903.05614/) (2019) - [Approximate exploitability: Learning a best response in large games](https://mlsanity.com/paper/2004.09677/) (2020) - [Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information](https://mlsanity.com/paper/2101.04667/) (2021) - [Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes](https://mlsanity.com/paper/2002.06768/) (2020) - [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022) - [Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants](https://mlsanity.com/paper/1410.1628/) (2014) - [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) - [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022) - [The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities](https://mlsanity.com/paper/2107.01906/) (2021) - [Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games](https://mlsanity.com/paper/2206.09254/) (2022) - [Last-iterate Convergence to Trembling-hand Perfect Equilibria](https://mlsanity.com/paper/2208.08238/) (2022) ## Built on by (most cited first, 9 of 9) - [Adaptively Perturbed Mirror Descent for Learning in Games](https://mlsanity.com/paper/2305.16610/) (2023) - [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025) - [RSPO: Regularized Self-Play Alignment of Large Language Models](https://mlsanity.com/paper/2503.00030/) (2025) - [The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2604.16087/) (2026) - [Corrupted Learning Dynamics in Games](https://mlsanity.com/paper/2412.07120/) (2024) - [NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria](https://mlsanity.com/paper/2510.18183/) (2025) - [Decentralized Online Learning in General-Sum Stackelberg Games](https://mlsanity.com/paper/2405.03158/) (2024) - [Last Iterate Convergence in Monotone Mean Field Games](https://mlsanity.com/paper/2410.05127/) (2024) - [Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation](https://mlsanity.com/paper/2509.13653/) (2025) ## 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.