# On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 72 references that are in the map.
- First posted on arXiv 4 Sep 2021.

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

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Games](https://mlsanity.com/paper/1703.10069/) (2017)
- [Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00583/) (2020)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [Wasserstein Robust Reinforcement Learning](https://mlsanity.com/paper/1907.13196/) (2019)
- [Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity](https://mlsanity.com/paper/1908.11071/) (2019)
- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [Feature-Based Q-Learning for Two-Player Stochastic Games](https://mlsanity.com/paper/1906.00423/) (2019)
- [Learning Nash Equilibrium for General-Sum Markov Games from Batch Data](https://mlsanity.com/paper/1606.08718/) (2016)
- [Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games](https://mlsanity.com/paper/1511.00785/) (2015)
- [A game-theoretic approach for Generative Adversarial Networks](https://mlsanity.com/paper/2003.13637/) (2020)

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

- [Multi-Agent Reinforcement Learning is a Sequence Modeling Problem](https://mlsanity.com/paper/2205.14953/) (2022)
- [Towards Human-Level Bimanual Dexterous Manipulation with Reinforcement Learning](https://mlsanity.com/paper/2206.08686/) (2022)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Multi-Agent Constrained Policy Optimisation](https://mlsanity.com/paper/2110.02793/) (2021)
- [Offline Pre-trained Multi-Agent Decision Transformer: One Big Sequence Model Tackles All SMAC Tasks](https://mlsanity.com/paper/2112.02845/) (2021)
- [On the convergence of policy gradient methods to Nash equilibria in general stochastic games](https://mlsanity.com/paper/2210.08857/) (2022)
- [A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers](https://mlsanity.com/paper/2110.15105/) (2021)
- [Measuring the Non-Transitivity in Chess](https://mlsanity.com/paper/2110.11737/) (2021)
- [DESTA: A Framework for Safe Reinforcement Learning with Markov Games of Intervention](https://mlsanity.com/paper/2110.14468/) (2021)
- [Online Markov Decision Processes with Non-oblivious Strategic Adversary](https://mlsanity.com/paper/2110.03604/) (2021)
- [On the Convergence of Fictitious Play: A Decomposition Approach](https://mlsanity.com/paper/2205.01469/) (2022)
- [Are Equivariant Equilibrium Approximators Beneficial?](https://mlsanity.com/paper/2301.11481/) (2023)
- [Push- and Pull-based Effective Communication in Cyber-Physical Systems](https://mlsanity.com/paper/2401.10921/) (2024)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [Learning Strategic Value and Cooperation in Multi-Player Stochastic Games through Side Payments](https://mlsanity.com/paper/2303.05307/) (2023)
- [A Payoff-Based Policy Gradient Method in Stochastic Games with Long-Run Average Payoffs](https://mlsanity.com/paper/2405.09811/) (2024)
- [Bounded Rationality Equilibrium Learning in Mean Field Games](https://mlsanity.com/paper/2411.07099/) (2024)
- [Survey on Strategic Mining in Blockchain: A Reinforcement Learning Approach](https://mlsanity.com/paper/2502.17307/) (2025)
- [On the Geometry of Games and their Solvers](https://mlsanity.com/paper/2605.29919/) (2026)

## Abstract (arXiv)

Similar to the role of Markov decision processes in reinforcement learning, Stochastic Games (SGs) lay the foundation for the study of multi-agent reinforcement learning (MARL) and sequential agent interactions. In this paper, we derive that computing an approximate Markov Perfect Equilibrium (MPE) in a finite-state discounted Stochastic Game within the exponential precision is PPAD-complete. We adopt a function with a polynomially bounded description in the strategy space to convert the MPE computation to a fixed-point problem, even though the stochastic game may demand an exponential number of pure strategies, in the number of states, for each agent. The completeness result follows the reduction of the fixed-point problem to sc End of the Line. Our results indicate that finding an MPE in SGs is highly unlikely to be NP-hard unless NP=co-NP. Our work offers confidence for MARL research to study MPE computation on general-sum SGs and to develop fruitful algorithms as currently on zero-sum SGs.