# Barriers to Welfare Maximization with No-Regret Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 69 references that are in the map.
- First posted on arXiv 4 Nov 2024.

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

- [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)
- [Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning](https://mlsanity.com/paper/2206.15378/) (2022)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Econometrics for Learning Agents](https://mlsanity.com/paper/1505.00720/) (2015)
- [Faster Rates for Convex-Concave Games](https://mlsanity.com/paper/1805.06792/) (2018)
- [Auctions Between Regret-Minimizing Agents](https://mlsanity.com/paper/2110.11855/) (2021)
- [End-to-End Learning and Intervention in Games](https://mlsanity.com/paper/2010.13834/) (2020)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Alternating Mirror Descent for Constrained Min-Max Games](https://mlsanity.com/paper/2206.04160/) (2022)
- [Coordinating the Crowd: Inducing Desirable Equilibria in Non-Cooperative Systems](https://mlsanity.com/paper/1901.10923/) (2019)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)
- [Inducing Equilibria via Incentives: Simultaneous Design-and-Play Ensures Global Convergence](https://mlsanity.com/paper/2110.01212/) (2021)
- [Inducing Equilibria in Networked Public Goods Games through Network Structure Modification](https://mlsanity.com/paper/2002.10627/) (2020)
- [Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation](https://mlsanity.com/paper/2203.07181/) (2022)
- [Equilibrium Finding in Normal-Form Games Via Greedy Regret Minimization](https://mlsanity.com/paper/2204.04826/) (2022)
- [Query Complexity of Correlated Equilibrium](https://mlsanity.com/paper/1306.2437/) (2013)
- [Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard](https://mlsanity.com/paper/1504.06314/) (2015)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [Lower Bounds for the Query Complexity of Equilibria in Lipschitz Games](https://mlsanity.com/paper/2107.03898/) (2021)

## Abstract (arXiv)

A celebrated result in the interface of online learning and game theory guarantees that the repeated interaction of no-regret players leads to a coarse correlated equilibrium (CCE) -- a natural game-theoretic solution concept. Despite the rich history of this foundational problem and the tremendous interest it has received in recent years, a basic question still remains open: how many iterations are needed for no-regret players to approximate an equilibrium? In this paper, we establish the first computational lower bounds for that problem in two-player (general-sum) games under the constraint that the CCE reached approximates the optimal social welfare (or some other natural objective). From a technical standpoint, our approach revolves around proving lower bounds for computing a near-optimal T-sparse CCE -- a mixture of T product distributions, thereby circumscribing the iteration complexity of no-regret learning even in the centralized model of computation. Our proof proceeds by extending a classical reduction of Gilboa and Zemel [1989] for optimal Nash to sparse (approximate) CCE. In particular, we show that the inapproximability of maximum clique precludes attaining any non-trivial sparsity in polynomial time. Moreover, we strengthen our hardness results to apply in the low-precision regime as well via the planted clique conjecture.