mlsanityData to 7 Oct 2026

When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?

arXiv 2110.04184 ↗First posted 8 Oct 2021cs.LG cs.GT stat.MLcited by 63

Not on the map. Why?

Abstract (arXiv)

Multi-agent reinforcement learning has made substantial empirical progresses in solving games with a large number of players. However, theoretically, the best known sample complexity for finding a Nash equilibrium in general-sum games scales exponentially in the number of players due to the size of the joint action space, and there is a matching exponential lower bound. This paper investigates what learning goals admit better sample complexities in the setting of m-player general-sum Markov games with H steps, S states, and Ai actions per player. First, we design algorithms for learning an ε-Coarse Correlated Equilibrium (CCE) in widetildeO(H5Smaxi≤ m Ai / ε2) episodes, and an ε-Correlated Equilibrium (CE) in widetildeO(H6Smaxi≤ m Ai2 / ε2) episodes. This is the first line of results for learning CCE and CE with sample complexities polynomial in maxi≤ m Ai. Our algorithm for learning CE integrates an adversarial bandit subroutine which minimizes a weighted swap regret, along with several novel designs in the outer loop. Second, we consider the important special case of Markov Potential Games, and design an algorithm that learns an ε-approximate Nash equilibrium within widetildeO(Ssumi≤ m Ai / ε3) episodes (when only highlighting the dependence on S, Ai, and ε), which only depends linearly in sumi≤ m Ai and significantly improves over existing efficient algorithm in the ε dependence. Overall, our results shed light on what equilibria or structural assumptions on the game may enable sample-efficient learning with many players.

Key facts. Cited by 63 papers in the map (data through 7 Oct 2026). Builds on 33 of its 64 references that are in the map. First posted on arXiv 8 Oct 2021.

Builds on

33 of 64 references.

References · 33

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  2. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2019Emergent Tool Use From Multi-Agent Autocurriculacited by 308
  6. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  7. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  8. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  9. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  10. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  11. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  12. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
21 more
  1. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  2. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  3. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  4. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  5. 2016Display Advertising with Real-Time Bidding (RTB) and Behavioural Targetingcited by 42
  6. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  7. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  8. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  9. 2017Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaoscited by 29
  10. 2021Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibriumcited by 22
  11. 2021Building a Foundation for Data-Driven, Interpretable, and Robust Policy Design using the AI Economistcited by 22
  12. 2016Learning Nash Equilibrium for General-Sum Markov Games from Batch Datacited by 20
  13. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 20
  14. 2021Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Gamescited by 14
  15. 2016Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphscited by 9
  16. 2013Learning Equilibria of Games via Payoff Queriescited by 8
  17. 2013Query Complexity of Approximate Nash Equilibriacited by 6
  18. 2013The Query Complexity of Correlated Equilibriacited by 5
  19. 2015Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Gamescited by 5
  20. 2013Query Complexity of Correlated Equilibriumcited by 4
  21. 2013Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queriescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 16; 2023: 17; 2024: 15; 2025: 3; 2026: 7.

63 papers.

Sort:

By area:

  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  2. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  3. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  4. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  5. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  6. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  7. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  8. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  9. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  10. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  11. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  12. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
38 more
  1. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  2. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  3. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  4. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  5. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  6. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  7. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  8. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
  9. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
  10. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  11. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  12. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  13. 2024A Comprehensive Survey on Inverse Constrained Reinforcement Learning: Definitions, Progress and Challengescited by 10
  14. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  15. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9
  16. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  17. 2022Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Gamescited by 7
  18. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  19. 2023Provably Learning Nash Policies in Constrained Markov Potential Gamescited by 7
  20. 2022Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chainscited by 6
  21. 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
  22. 2023Markov α-Potential Gamescited by 6
  23. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
  24. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  25. 2024MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Gamescited by 5
  26. 2021Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Gamescited by 4
  27. 2023Finite-sample Guarantees for Nash Q-learning with Linear Function Approximationcited by 4
  28. 2024Minimax-Optimal Multi-Agent Robust Reinforcement Learningcited by 4
  29. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  30. 2025The Oversight Game: Learning to Cooperatively Balance an AI Agent's Safety and Autonomycited by 3
  31. 2026Offline Two-Player Zero-Sum Markov Games with KL Regularizationcited by 3
  32. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 2
  33. 2024Policy Optimization finds Nash Equilibrium in Regularized General-Sum LQ Gamescited by 2
  34. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  35. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  36. 2024Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Gamescited by 1
  37. 2024TrafficGamer: Reliable and Flexible Traffic Simulation for Safety-Critical Scenarios with Game-Theoretic Oraclescited by 1
  38. 2024Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Modelscited by 1

50 most cited of 63 All 63 (JSON)