mlsanityData to 14 Oct 2026

Multi-Player Zero-Sum Markov Games with Networked Separable Interactions

arXiv 2307.09470 ↗First posted 13 Jul 2023cs.GT cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

We study a new class of Markov games, emph(multi-player) zero-sum Markov Games with Networked separable interactions (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent sequential decision-making. We define a zero-sum NMG as a model where the payoffs of the auxiliary games associated with each state are zero-sum and have some separable (i.e., polymatrix) structure across the neighbors over some interaction network. We first identify the necessary and sufficient conditions under which an MG can be presented as a zero-sum NMG, and show that the set of Markov coarse correlated equilibrium (CCE) collapses to the set of Markov Nash equilibrium (NE) in these games, in that the product of per-state marginalization of the former for all players yields the latter. Furthermore, we show that finding approximate Markov stationary CCE in infinite-horizon discounted zero-sum NMGs is textttPPAD-hard, unless the underlying network has a ``star topology''. Then, we propose fictitious-play-type dynamics, the classical learning dynamics in normal-form games, for zero-sum NMGs, and establish convergence guarantees to Markov stationary NE under a star-shaped network structure. Finally, in light of the hardness result, we focus on computing a Markov non-stationary NE and provide finite-iteration guarantees for a series of value-iteration-based algorithms. We also provide numerical experiments to corroborate our theoretical results.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 65 of its 141 references that are in the map. First posted on arXiv 13 Jul 2023.

Builds on

65 of 141 references.

References · 65

  1. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  3. 2019Emergent Tool Use From Multi-Agent Autocurriculacited by 313
  4. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  5. 2017StarCraft II: A New Challenge for Reinforcement Learningcited by 274
  6. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  7. 2017Training GANs with Optimismcited by 217
  8. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 194
  9. 2017A unified view of entropy-regularized Markov decision processescited by 182
  10. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  11. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  12. 2017Cycles in adversarial regularized learningcited by 124
38 more
  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  2. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  3. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
  4. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  5. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  6. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  7. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  8. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  9. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
  10. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  11. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  12. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  13. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 66
  14. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  15. 2020Fictitious Play for Mean Field Games: Continuous Time Analysis and Applicationscited by 62
  16. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 58
  17. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  18. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 49
  19. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 42
  20. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  21. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 36
  22. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  23. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 34
  24. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  25. 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 31
  26. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
  27. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  28. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
  29. 2020Fictitious play in zero-sum stochastic gamescited by 26
  30. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 26
  31. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  32. 2019Scalable Reinforcement Learning for Multi-Agent Networked Systemscited by 24
  33. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 24
  34. 2021Independent Learning in Stochastic Gamescited by 22
  35. 2013Graphical Models for Game Theorycited by 21
  36. 2021Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationalitycited by 21
  37. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  38. 2022Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learningcited by 20

50 most cited of 65 All 65 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

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

10 papers.

  1. 2025MAPoRL: Multi-Agent Post-Co-Training for Collaborative Large Language Models with Reinforcement Learningcited by 86
  2. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  3. 2024Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rankcited by 6
  4. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  5. 2024Generalized Individual Q-learning for Polymatrix Games with Partial Observationscited by 1
  6. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  7. 2024Risk Sensitivity in Markov Games and Multi-Agent Reinforcement Learning: A Systematic Reviewcited by 0
  8. 2024A Scalable Game Theoretic Approach for Coordination of Multiple Dynamic Systemscited by 0
  9. 2026Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Gamescited by 0
  10. 2026Learning to Reflect: Hierarchical Multi-Agent Reinforcement Learning for CSI-Free mmWave Beam-Focusingcited by 0