# Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 68 references that are in the map.
- First posted on arXiv 22 Mar 2023.

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

- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [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)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [Scalable Evaluation of Multi-Agent Reinforcement Learning with Melting Pot](https://mlsanity.com/paper/2107.06857/) (2021)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [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)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions](https://mlsanity.com/paper/1303.3055/) (2013)
- [On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function](https://mlsanity.com/paper/2102.02049/) (2021)
- [Inapproximability of Nash Equilibrium](https://mlsanity.com/paper/1405.3322/) (2014)
- [Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits](https://mlsanity.com/paper/2203.06803/) (2022)
- [Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games](https://mlsanity.com/paper/2206.01588/) (2022)
- [The Complexity of Infinite-Horizon General-Sum Stochastic Games](https://mlsanity.com/paper/2204.04186/) (2022)
- [Learning Equilibria of Games via Payoff Queries](https://mlsanity.com/paper/1302.3116/) (2013)
- [Query Complexity of Approximate Nash Equilibria](https://mlsanity.com/paper/1306.6686/) (2013)
- [On the Communication Complexity of Approximate Nash Equilibria](https://mlsanity.com/paper/1302.3793/) (2013)
- [Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games](https://mlsanity.com/paper/1511.00785/) (2015)

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

- [Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games](https://mlsanity.com/paper/2401.15240/) (2024)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [Efficient Inverse Multiagent Learning](https://mlsanity.com/paper/2502.14160/) (2025)
- [Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2312.04905/) (2023)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [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)
- [Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedback](https://mlsanity.com/paper/2603.28281/) (2026)
- [Once-for-All: Scalable Simultaneous Forecasting via Equilibrium State Estimation](https://mlsanity.com/paper/2606.13285/) (2026)
- [Normal-Form Correlation in Markov Games](https://mlsanity.com/paper/2610.03621/) (2026)

## Abstract (arXiv)

We consider the problem of decentralized multi-agent reinforcement learning in Markov games. A fundamental question is whether there exist algorithms that, when adopted by all agents and run independently in a decentralized fashion, lead to no-regret for each player, analogous to celebrated convergence results in normal-form games. While recent work has shown that such algorithms exist for restricted settings (notably, when regret is defined with respect to deviations to Markovian policies), the question of whether independent no-regret learning can be achieved in the standard Markov game framework was open. We provide a decisive negative resolution this problem, both from a computational and statistical perspective. We show that: - Under the widely-believed assumption that PPAD-hard problems cannot be solved in polynomial time, there is no polynomial-time algorithm that attains no-regret in general-sum Markov games when executed independently by all players, even when the game is known to the algorithm designer and the number of players is a small constant. - When the game is unknown, no algorithm, regardless of computational efficiency, can achieve no-regret without observing a number of episodes that is exponential in the number of players. Perhaps surprisingly, our lower bounds hold even for seemingly easier setting in which all agents are controlled by a a centralized algorithm. They are proven via lower bounds for a simpler problem we refer to as SparseCCE, in which the goal is to compute a coarse correlated equilibrium that is sparse in the sense that it can be represented as a mixture of a small number of product policies. The crux of our approach is a novel application of aggregation techniques from online learning, whereby we show that any algorithm for the SparseCCE problem can be used to compute approximate Nash equilibria for non-zero sum normal-form games.