mlsanityData to 7 Oct 2026

Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model

arXiv 2208.10458 ↗First posted 22 Aug 2022cs.LG cs.GT cs.ITcited by 15

Not on the map. Why?

Abstract (arXiv)

This paper studies multi-agent reinforcement learning in Markov games, with the goal of learning Nash equilibria or coarse correlated equilibria (CCE) sample-optimally. All prior results suffer from at least one of the two obstacles: the curse of multiple agents and the barrier of long horizon, regardless of the sampling protocol in use. We take a step towards settling this problem, assuming access to a flexible sampling mechanism: the generative model. Focusing on non-stationary finite-horizon Markov games, we develop a fast learning algorithm called myalg~and an adaptive sampling scheme that leverage the optimism principle in online adversarial learning (particularly the Follow-the-Regularized-Leader (FTRL) method). Our algorithm learns an varepsilon-approximate CCE in a general-sum Markov game using widetildeObigg( fracH4 S sumi=1m Aivarepsilon2 bigg) samples, where m is the number of players, S indicates the number of states, H is the horizon, and Ai denotes the number of actions for the i-th player. This is minimax-optimal (up to log factor) when the number of players is fixed. When applied to two-player zero-sum Markov games, our algorithm provably finds an varepsilon-approximate Nash equilibrium with minimal samples. Along the way, we derive a refined regret bound for FTRL that makes explicit the role of variance-type quantities, which might be of independent interest.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 50 of its 100 references that are in the map. First posted on arXiv 22 Aug 2022.

Builds on

50 of 100 references.

References · 50

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  5. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  6. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  7. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  8. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  9. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  10. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  11. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  12. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
38 more
  1. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  2. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  3. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  4. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  5. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  6. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  7. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  8. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  9. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  10. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  11. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  12. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  13. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  14. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  15. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  16. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  17. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  18. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  19. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  20. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  21. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  22. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
  23. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  24. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  25. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  26. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  27. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  28. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  29. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
  30. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  31. 2021Independent Learning in Stochastic Gamescited by 20
  32. 2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
  33. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  34. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  35. 2020Minimax Sample Complexity for Turn-based Stochastic Gamecited by 13
  36. 2022The Complexity of Infinite-Horizon General-Sum Stochastic Gamescited by 10
  37. 2015Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Gamescited by 5
  38. 2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5

Built on by

Cited by year (2026 to 7 Oct)

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

15 papers.

Sort:

  1. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  2. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  3. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  4. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  5. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  6. 2023Finite-sample Guarantees for Nash Q-learning with Linear Function Approximationcited by 4
  7. 2024Minimax-Optimal Multi-Agent Robust Reinforcement Learningcited by 4
  8. 2023Contextual Dynamic Pricing with Strategic Buyerscited by 3
  9. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  10. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 1
  11. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0
  12. 2024RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Modelcited by 0
3 more
  1. 2025Combining Planning and Reinforcement Learning for Solving Relational Multiagent Domainscited by 0
  2. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0
  3. 2026Robust PAC Learning of Concurrent Stochastic Gamescited by 0