# Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 45 references that are in the map.
- First posted on arXiv 11 Nov 2021.

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

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [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)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [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)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [Communication complexity of approximate Nash equilibria](https://mlsanity.com/paper/1608.06580/) (2016)

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

- [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)
- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games](https://mlsanity.com/paper/2401.15240/) (2024)
- [Calibration Error for Decision Making](https://mlsanity.com/paper/2404.13503/) (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)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [Maximizing utility in multi-agent environments by anticipating the behavior of other learners](https://mlsanity.com/paper/2407.04889/) (2024)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [Playing Large Games with Oracles and AI Debate](https://mlsanity.com/paper/2312.04792/) (2023)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [Corrupted Learning Dynamics in Games](https://mlsanity.com/paper/2412.07120/) (2024)
- [Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret](https://mlsanity.com/paper/2602.06348/) (2026)
- [Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization](https://mlsanity.com/paper/2608.04149/) (2026)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Near-Optimal Phi-Regret Learning in Extensive-Form Games](https://mlsanity.com/paper/2208.09747/) (2022)
- [Proximal Point Method for Online Saddle Point Problem](https://mlsanity.com/paper/2407.04591/) (2024)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [Computational Intractability of Strategizing against Online Learners](https://mlsanity.com/paper/2503.04202/) (2025)

## Abstract (arXiv)

Recently, Daskalakis, Fishelson, and Golowich (DFG) (NeurIPS`21) showed that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player is O(textrmpolylog(T)) after T repetitions of the game. We extend their result from external regret to internal regret and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium at the rate of tildeO(T-1). This substantially improves over the prior best rate of convergence for correlated equilibria of O(T-3/4) due to Chen and Peng (NeurIPS`20), and it is optimal -- within the no-regret framework -- up to polylogarithmic factors in T. To obtain these results, we develop new techniques for establishing higher-order smoothness for learning dynamics involving fixed point operations. Specifically, we establish that the no-internal-regret learning dynamics of Stoltz and Lugosi (Mach Learn`05) are equivalently simulated by no-external-regret dynamics on a combinatorial space. This allows us to trade the computation of the stationary distribution on a polynomial-sized Markov chain for a (much more well-behaved) linear transformation on an exponential-sized set, enabling us to leverage similar techniques as DFG to near-optimally bound the internal regret. Moreover, we establish an O(textrmpolylog(T)) no-swap-regret bound for the classic algorithm of Blum and Mansour (BM) (JMLR`07). We do so by introducing a technique based on the Cauchy Integral Formula that circumvents the more limited combinatorial arguments of DFG. In addition to shedding clarity on the near-optimal regret guarantees of BM, our arguments provide insights into the various ways in which the techniques by DFG can be extended and leveraged in the analysis of more involved learning algorithms.