# Near-Optimal No-Regret Learning in General Games

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

## Key facts

- Cited by 85 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 55 references that are in the map.
- First posted on arXiv 16 Aug 2021.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [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)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Tight last-iterate convergence rates for no-regret learning in multi-player games](https://mlsanity.com/paper/2010.13724/) (2020)
- [Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games](https://mlsanity.com/paper/1905.08396/) (2019)
- [Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes](https://mlsanity.com/paper/2002.06768/) (2020)
- [Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes](https://mlsanity.com/paper/1905.04532/) (2019)
- [The Price of Anarchy in Auctions](https://mlsanity.com/paper/1607.07684/) (2016)
- [The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities](https://mlsanity.com/paper/2107.01906/) (2021)
- [Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Games](https://mlsanity.com/paper/1802.04221/) (2018)
- [A Counter-Example to Karlin's Strong Conjecture for Fictitious Play](https://mlsanity.com/paper/1412.4840/) (2014)

## Built on by (most cited first, 30 of 85)

- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning](https://mlsanity.com/paper/2407.00617/) (2024)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [Improving LLM General Preference Alignment via Optimistic Online Mirror Descent](https://mlsanity.com/paper/2502.16852/) (2025)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [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)
- [How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agents](https://mlsanity.com/paper/2112.07640/) (2021)
- [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Policy Optimization for Markov Games: Unified Framework and Faster Convergence](https://mlsanity.com/paper/2206.02640/) (2022)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Regret Matching+: (In)Stability and Fast Convergence in Games](https://mlsanity.com/paper/2305.14709/) (2023)
- [Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms](https://mlsanity.com/paper/2406.10631/) (2024)
- [Alternating Mirror Descent for Constrained Min-Max Games](https://mlsanity.com/paper/2206.04160/) (2022)
- [Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games](https://mlsanity.com/paper/2401.15240/) (2024)
- [O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2209.12430/) (2022)
- [Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization](https://mlsanity.com/paper/2204.05466/) (2022)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)
- [Multi-Player Zero-Sum Markov Games with Networked Separable Interactions](https://mlsanity.com/paper/2307.09470/) (2023)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)

## Abstract (arXiv)

We show that Optimistic Hedge -- a common variant of multiplicative-weights-updates with recency bias -- attains rm poly(log T) regret in multi-player general-sum games. In particular, when every player of the game uses Optimistic Hedge to iteratively update her strategy in response to the history of play so far, then after T rounds of interaction, each player experiences total regret that is rm poly(log T). Our bound improves, exponentially, the O(T1/2) regret attainable by standard no-regret learners in games, the O(T1/4) regret attainable by no-regret learners with recency bias (Syrgkanis et al., 2015), and the O(T1/6) bound that was recently shown for Optimistic Hedge in the special case of two-player games (Chen & Pen, 2020). A corollary of our bound is that Optimistic Hedge converges to coarse correlated equilibrium in general games at a rate of tildeOleft(frac 1Tright).