mlsanityData to 14 Oct 2026

Near-Optimal No-Regret Learning in General Games

arXiv 2108.06924 ↗First posted 16 Aug 2021cs.LGcited by 85

Not on the map. Why?

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

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

17 of 55 references.

References · 17

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  3. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  4. 2017Cycles in adversarial regularized learningcited by 124
  5. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  6. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  7. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  8. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  9. 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 50
  10. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
  11. 2019Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Gamescited by 25
  12. 2020Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapescited by 21
5 more
  1. 2019Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizescited by 14
  2. 2016The Price of Anarchy in Auctionscited by 12
  3. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  4. 2018Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Gamescited by 11
  5. 2014A Counter-Example to Karlin's Strong Conjecture for Fictitious Playcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 16; 2023: 15; 2024: 21; 2025: 17; 2026: 10.

85 papers.

Sort:

By area:

  1. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  2. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  3. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  4. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  5. 2022No-Regret Learning in Time-Varying Zero-Sum Gamescited by 36
  6. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  7. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 32
  8. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  9. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 24
  10. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
  11. 2021Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Updatecited by 20
  12. 2023Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamicscited by 20
38 more
  1. 2023Is Learning in Games Good for the Learners?cited by 20
  2. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  3. 2021How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agentscited by 17
  4. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  5. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  6. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  7. 2022Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descentcited by 15
  8. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  9. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  10. 2023Regret Matching+: (In)Stability and Fast Convergence in Gamescited by 14
  11. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  12. 2022Alternating Mirror Descent for Constrained Min-Max Gamescited by 13
  13. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 13
  14. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  15. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  16. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 10
  17. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 10
  18. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 10
  19. 2025Faster Rates for No-Regret Learning in General Games via Cautious Optimismcited by 10
  20. 2024Maximizing utility in multi-agent environments by anticipating the behavior of other learnerscited by 8
  21. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  22. 2023Playing Large Games with Oracles and AI Debatecited by 6
  23. 2024Impact of Decentralized Learning on Player Utilities in Stackelberg Gamescited by 5
  24. 2024Neural Population Learning beyond Symmetric Zero-sum Gamescited by 4
  25. 2024The complexity of approximate (coarse) correlated equilibrium for incomplete information gamescited by 4
  26. 2024Corrupted Learning Dynamics in Gamescited by 4
  27. 2024No-regret learning in harmonic games: Extrapolation in the face of conflicting interestscited by 4
  28. 2026Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regretcited by 4
  29. 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 4
  30. 2026Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularizationcited by 4
  31. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  32. 2022Near-Optimal Phi-Regret Learning in Extensive-Form Gamescited by 3
  33. 2024No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processescited by 3
  34. 2024Games with Payments between Learning Agentscited by 3
  35. 2024Proximal Point Method for Online Saddle Point Problemcited by 3
  36. 2025Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Gamescited by 3
  37. 2026Constant Individual Regret in General Gamescited by 3
  38. 2023Adaptive Decision-Making with Constraints and Dependent Losses: Performance Guarantees and Applications to Online and Nonlinear Identificationcited by 2

50 most cited of 85 All 85 (JSON)