mlsanityData to 7 Oct 2026

Efficiently Computing Nash Equilibria in Adversarial Team Markov Games

arXiv 2208.02204 ↗First posted 3 Aug 2022cs.GT cs.LG cs.MAcited by 6

Not on the map. Why?

Abstract (arXiv)

Computing Nash equilibrium policies is a central problem in multi-agent reinforcement learning that has received extensive attention both in theory and in practice. However, provable guarantees have been thus far either limited to fully competitive or cooperative scenarios or impose strong assumptions that are difficult to meet in most practical applications. In this work, we depart from those prior results by investigating infinite-horizon adversarial team Markov games, a natural and well-motivated class of games in which a team of identically-interested players -- in the absence of any explicit coordination or communication -- is competing against an adversarial player. This setting allows for a unifying treatment of zero-sum Markov games and Markov potential games, and serves as a step to model more realistic strategic interactions that feature both competing and cooperative interests. Our main contribution is the first algorithm for computing stationary ε-approximate Nash equilibria in adversarial team Markov games with computational complexity that is polynomial in all the natural parameters of the game, as well as 1/ε. The proposed algorithm is particularly natural and practical, and it is based on performing independent policy gradient steps for each player in the team, in tandem with best responses from the side of the adversary; in turn, the policy for the adversary is then obtained by solving a carefully constructed linear program. Our analysis leverages non-standard techniques to establish the KKT optimality conditions for a nonlinear program with nonconvex constraints, thereby leading to a natural interpretation of the induced Lagrange multipliers. Along the way, we significantly extend an important characterization of optimal policies in adversarial (normal-form) team games due to Von Stengel and Koller (GEB `97).

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 37 of its 102 references that are in the map. First posted on arXiv 3 Aug 2022.

Builds on

37 of 102 references.

References · 37

  1. 2015Trust Region Policy Optimizationcited by 2,503
  2. 2021Convex optimizationcited by 2,479
  3. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  6. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 228
  7. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  8. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  9. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  10. 2018Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guaranteescited by 138
  11. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 129
  12. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
25 more
  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  2. 2020Combining Deep Reinforcement Learning and Search for Imperfect-Information Gamescited by 110
  3. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  4. 2020Game-Theoretic Multiagent Reinforcement Learningcited by 92
  5. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  6. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  7. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  8. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  9. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  10. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  11. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  12. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  13. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
  14. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  15. 2020Fictitious play in zero-sum stochastic gamescited by 24
  16. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 20
  17. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  18. 2017Computational Results for Extensive-Form Adversarial Team Gamescited by 18
  19. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  20. 2022The Complexity of Infinite-Horizon General-Sum Stochastic Gamescited by 10
  21. 2016Team-maxmin equilibrium: efficiency bounds and algorithmscited by 9
  22. 2021Team Correlated Equilibria in Zero-Sum Extensive-Form Games via Tree Decompositionscited by 6
  23. 2022Convergence and Price of Anarchy Guarantees of the Softmax Policy Gradient in Markov Potential Gamescited by 6
  24. 2022A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solvingcited by 6
  25. 2022For Learning in Symmetric Teams, Local Optima are Global Nash Equilibriacited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 1; 2025: 1; 2026: 2.

6 papers.

  1. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  2. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  3. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  4. 2024Environment Complexity and Nash Equilibria in a Sequential Social Dilemmacited by 0
  5. 2025Multi-Agent Inverse Q-Learning from Demonstrationscited by 0
  6. 2026Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Informationcited by 0