mlsanityData to 7 Oct 2026

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

arXiv 2109.01795 ↗First posted 4 Sep 2021cs.GT cs.CC cs.LGcited by 18

Not on the map. Why?

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.

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

Builds on

16 of 72 references.

References · 16

  1. 2018Is Q-learning Provably Efficient?cited by 485
  2. 2017Robust Adversarial Reinforcement Learningcited by 439
  3. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  4. 2018Mean Field Multi-Agent Reinforcement Learningcited by 202
  5. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  6. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  7. 2017Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Gamescited by 93
  8. 2020Game-Theoretic Multiagent Reinforcement Learningcited by 92
  9. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  10. 2019Wasserstein Robust Reinforcement Learningcited by 50
  11. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  12. 2021Modelling Behavioural Diversity for Learning in Open-Ended Gamescited by 39
4 more
  1. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
  2. 2016Learning Nash Equilibrium for General-Sum Markov Games from Batch Datacited by 20
  3. 2015Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Gamescited by 5
  4. 2020A game-theoretic approach for Generative Adversarial Networkscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 5; 2023: 2; 2024: 2; 2025: 1; 2026: 2.

18 papers.

Sort:

By area:

  1. 2022Multi-Agent Reinforcement Learning is a Sequence Modeling Problemcited by 153
  2. 2022Towards Human-Level Bimanual Dexterous Manipulation with Reinforcement Learningcited by 113
  3. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  4. 2021Multi-Agent Constrained Policy Optimisationcited by 32
  5. 2021Offline Pre-trained Multi-Agent Decision Transformer: One Big Sequence Model Tackles All SMAC Taskscited by 32
  6. 2021A Game-Theoretic Approach for Improving Generalization Ability of TSP Solverscited by 14
  7. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  8. 2021Measuring the Non-Transitivity in Chesscited by 10
  9. 2021DESTA: A Framework for Safe Reinforcement Learning with Markov Games of Interventioncited by 4
  10. 2021Online Markov Decision Processes with Non-oblivious Strategic Adversarycited by 3
  11. 2022On the Convergence of Fictitious Play: A Decomposition Approachcited by 2
  12. 2023Are Equivariant Equilibrium Approximators Beneficial?cited by 2
6 more
  1. 2024Push- and Pull-based Effective Communication in Cyber-Physical Systemscited by 1
  2. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  3. 2023Learning Strategic Value and Cooperation in Multi-Player Stochastic Games through Side Paymentscited by 0
  4. 2024Bounded Rationality Equilibrium Learning in Mean Field Gamescited by 0
  5. 2025Survey on Strategic Mining in Blockchain: A Reinforcement Learning Approachcited by 0
  6. 2026On the Geometry of Games and their Solverscited by 0