# The Complexity of Markov Equilibrium in Stochastic Games

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 76 references that are in the map.
- First posted on arXiv 8 Apr 2022.

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policies](https://mlsanity.com/paper/2004.13332/) (2020)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets](https://mlsanity.com/paper/2202.07511/) (2022)
- [Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity](https://mlsanity.com/paper/1908.11071/) (2019)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [When is Offline Two-Player Zero-Sum Markov Game Solvable?](https://mlsanity.com/paper/2201.03522/) (2022)
- [On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games](https://mlsanity.com/paper/2109.01795/) (2021)
- [Inapproximability of Nash Equilibrium](https://mlsanity.com/paper/1405.3322/) (2014)
- [Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash](https://mlsanity.com/paper/1504.02411/) (2015)
- [Unique End of Potential Line](https://mlsanity.com/paper/1811.03841/) (2018)

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

- [Multi-agent Reinforcement Learning: A Comprehensive Survey](https://mlsanity.com/paper/2312.10256/) (2023)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Sample-Efficient Reinforcement Learning of Partially Observable Markov Games](https://mlsanity.com/paper/2206.01315/) (2022)
- [Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2302.03673/) (2023)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [Offline Learning in Markov Games with General Function Approximation](https://mlsanity.com/paper/2302.02571/) (2023)
- [Policy Optimization for Markov Games: Unified Framework and Faster Convergence](https://mlsanity.com/paper/2206.02640/) (2022)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [On the convergence of policy gradient methods to Nash equilibria in general stochastic games](https://mlsanity.com/paper/2210.08857/) (2022)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Performative Reinforcement Learning in Gradually Shifting Environments](https://mlsanity.com/paper/2402.09838/) (2024)
- [Optimal Attack and Defense for Reinforcement Learning](https://mlsanity.com/paper/2312.00198/) (2023)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)
- [Multi-Player Zero-Sum Markov Games with Networked Separable Interactions](https://mlsanity.com/paper/2307.09470/) (2023)
- [When is Mean-Field Reinforcement Learning Tractable and Relevant?](https://mlsanity.com/paper/2402.05757/) (2024)
- [Efficiently Computing Nash Equilibria in Adversarial Team Markov Games](https://mlsanity.com/paper/2208.02204/) (2022)
- [A Reduction-based Framework for Sequential Decision Making with Delayed Feedback](https://mlsanity.com/paper/2302.01477/) (2023)
- [Settling Decentralized Multi-Agent Coordinated Exploration by Novelty Sharing](https://mlsanity.com/paper/2402.02097/) (2024)
- [Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank](https://mlsanity.com/paper/2410.01101/) (2024)
- [Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem](https://mlsanity.com/paper/2410.05673/) (2024)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [Tractable Equilibrium Computation in Markov Games through Risk Aversion](https://mlsanity.com/paper/2406.14156/) (2024)
- [A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2306.07465/) (2023)
- [Posterior Sampling for Competitive RL: Function Approximation and Partial Observation](https://mlsanity.com/paper/2310.19861/) (2023)
- [Refined Sample Complexity for Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2402.07082/) (2024)
- [Representation Learning For Efficient Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2406.02890/) (2024)
- [Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.16600/) (2024)

## Abstract (arXiv)

We show that computing approximate stationary Markov coarse correlated equilibria (CCE) in general-sum stochastic games is computationally intractable, even when there are two players, the game is turn-based, the discount factor is an absolute constant, and the approximation is an absolute constant. Our intractability results stand in sharp contrast to normal-form games where exact CCEs are efficiently computable. A fortiori, our results imply that there are no efficient algorithms for learning stationary Markov CCE policies in multi-agent reinforcement learning (MARL), even when the interaction is two-player and turn-based, and both the discount factor and the desired approximation of the learned policies is an absolute constant. In turn, these results stand in sharp contrast to single-agent reinforcement learning (RL) where near-optimal stationary Markov policies can be efficiently learned. Complementing our intractability results for stationary Markov CCEs, we provide a decentralized algorithm (assuming shared randomness among players) for learning a nonstationary Markov CCE policy with polynomial time and sample complexity in all problem parameters. Previous work for learning Markov CCE policies all required exponential time and sample complexity in the number of players.