# The complexity of approximate (coarse) correlated equilibrium for incomplete information games

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 69 references that are in the map.
- First posted on arXiv 4 Jun 2024.

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

- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1811.00164/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [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)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions](https://mlsanity.com/paper/1910.10906/) (2019)
- [Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2104.01520/) (2021)
- [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)
- [Inapproximability of Nash Equilibrium](https://mlsanity.com/paper/1405.3322/) (2014)
- [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)
- [The Complexity of Infinite-Horizon General-Sum Stochastic Games](https://mlsanity.com/paper/2204.04186/) (2022)
- [From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces](https://mlsanity.com/paper/2310.19786/) (2023)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)
- [On the Complexity of Equilibrium Computation in First-Price Auctions](https://mlsanity.com/paper/2103.03238/) (2021)
- [Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/1910.12450/) (2019)
- [Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules](https://mlsanity.com/paper/2303.16388/) (2023)
- [Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy](https://mlsanity.com/paper/2304.05005/) (2023)
- [Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash](https://mlsanity.com/paper/1504.02411/) (2015)
- [Computational Hardness of the Hylland-Zeckhauser Scheme](https://mlsanity.com/paper/2107.05746/) (2021)
- [Near-Optimal Phi-Regret Learning in Extensive-Form Games](https://mlsanity.com/paper/2208.09747/) (2022)
- [The Complexity of Fairness through Equilibrium](https://mlsanity.com/paper/1312.6249/) (2013)
- [Public Goods Games in Directed Networks](https://mlsanity.com/paper/2106.00718/) (2021)
- [On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games](https://mlsanity.com/paper/2311.14869/) (2023)

## Built on by (most cited first, 4 of 4)

- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [Barriers to Welfare Maximization with No-Regret Learning](https://mlsanity.com/paper/2411.01720/) (2024)
- [Computational Lower Bounds for Regret Minimization in Normal-Form Games](https://mlsanity.com/paper/2411.01721/) (2024)
- [Explore Reinforced: Equilibrium Approximation with Reinforcement Learning](https://mlsanity.com/paper/2412.02016/) (2024)

## Abstract (arXiv)

We study the iteration complexity of decentralized learning of approximate correlated equilibria in incomplete information games. On the negative side, we prove that in mathitextensive-mathitform mathitgames, assuming mathsfPPAD notsubset mathsfTIME(n^mathsfpolylog(n)), any polynomial-time learning algorithms must take at least 2^log21-o(1)(|I|) iterations to converge to the set of ε-approximate correlated equilibrium, where |I| is the number of nodes in the game and ε > 0 is an absolute constant. This nearly matches, up to the o(1) term, the algorithms of [PR'24, DDFG'24] for learning ε-approximate correlated equilibrium, and resolves an open question of Anagnostides, Kalavasis, Sandholm, and Zampetakis [AKSZ'24]. Our lower bound holds even for the easier solution concept of ε-approximate mathitcoarse correlated equilibrium On the positive side, we give uncoupled dynamics that reach ε-approximate correlated equilibria of a mathitBayesian mathitgame in polylogarithmic iterations, without any dependence of the number of types. This demonstrates a separation between Bayesian games and extensive-form games.