mlsanityData to 7 Oct 2026

Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation

arXiv 2302.06606 ↗First posted 13 Feb 2023cs.LG cs.AI cs.GTcited by 29

Not on the map. Why?

Abstract (arXiv)

A unique challenge in Multi-Agent Reinforcement Learning (MARL) is the curse of multiagency, where the description length of the game as well as the complexity of many existing learning algorithms scale exponentially with the number of agents. While recent works successfully address this challenge under the model of tabular Markov Games, their mechanisms critically rely on the number of states being finite and small, and do not extend to practical scenarios with enormous state spaces where function approximation must be used to approximate value functions or policies. This paper presents the first line of MARL algorithms that provably resolve the curse of multiagency under function approximation. We design a new decentralized algorithm -- V-Learning with Policy Replay, which gives the first polynomial sample complexity results for learning approximate Coarse Correlated Equilibria (CCEs) of Markov Games under decentralized linear function approximation. Our algorithm always outputs Markov CCEs, and achieves an optimal rate of widetildeO(ε-2) for finding ε-optimal solutions. Also, when restricted to the tabular case, our result improves over the current best decentralized result widetildeO(ε-3) for finding Markov CCEs. We further present an alternative algorithm -- Decentralized Optimistic Policy Mirror Descent, which finds policy-class-restricted CCEs using a polynomial number of samples. In exchange for learning a weaker version of CCEs, this algorithm applies to a wider range of problems under generic function approximation, such as linear quadratic games and MARL problems with low ''marginal'' Eluder dimension.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 52 of its 77 references that are in the map. First posted on arXiv 13 Feb 2023.

Builds on

52 of 77 references.

References · 52

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  5. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  6. 2019Emergent Tool Use From Multi-Agent Autocurriculacited by 308
  7. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  8. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  10. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  11. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  12. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
38 more
  1. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  2. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  3. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  4. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  5. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  6. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  7. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  8. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  9. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  10. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  11. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  12. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  13. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  14. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  15. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  16. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 42
  17. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  18. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  19. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  20. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  21. 2020Faster Projection-free Online Learningcited by 39
  22. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 38
  23. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  24. 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
  25. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  26. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  27. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  28. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  29. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  30. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
  31. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  32. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  33. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  34. 2022Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descentcited by 15
  35. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  36. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
  37. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  38. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 10; 2024: 11; 2025: 3; 2026: 5.

29 papers.

Sort:

By area:

  1. 2025LLM Economist: Large Population Models and Mechanism Design in Multi-Agent Generative Simulacracited by 20
  2. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  3. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 11
  4. 2024Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RLcited by 9
  5. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  6. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6
  7. 2024Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Surveycited by 5
  8. 2024Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependenciescited by 5
  9. 2023Finite-sample Guarantees for Nash Q-learning with Linear Function Approximationcited by 4
  10. 2023Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learningcited by 4
  11. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  12. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
17 more
  1. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  2. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  3. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  4. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  5. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  6. 2024Differentially Private Reinforcement Learning with Self-Playcited by 1
  7. 2024Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Modelscited by 1
  8. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 1
  9. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  10. 2026Multi-agent imitation learning with function approximation: Linear Markov games and beyondcited by 1
  11. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0
  12. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Gamescited by 0
  13. 2024RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Modelcited by 0
  14. 2026Cooperative Multi-agent RL with Communication Constraintscited by 0
  15. 2026Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximationcited by 0
  16. 2026Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedbackcited by 0
  17. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0