mlsanityData to 7 Oct 2026

On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning

arXiv 2110.05707 ↗First posted 12 Oct 2021cs.LG cs.AI cs.MAcited by 35

Not on the map. Why?

Abstract (arXiv)

Multi-agent reinforcement learning (MARL) algorithms often suffer from an exponential sample complexity dependence on the number of agents, a phenomenon known as the curse of multiagents. In this paper, we address this challenge by investigating sample-efficient model-free algorithms in decentralized MARL, and aim to improve existing algorithms along this line. For learning (coarse) correlated equilibria in general-sum Markov games, we propose stage-based V-learning algorithms that significantly simplify the algorithmic design and analysis of recent works, and circumvent a rather complicated no-weighted-regret bandit subroutine. For learning Nash equilibria in Markov potential games, we propose an independent policy gradient algorithm with a decentralized momentum-based variance reduction technique. All our algorithms are decentralized in that each agent can make decisions based on only its local information. Neither communication nor centralized coordination is required during learning, leading to a natural generalization to a large number of agents. We also provide numerical simulations to corroborate our theoretical findings.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). Builds on 44 of its 116 references that are in the map. First posted on arXiv 12 Oct 2021.

Builds on

44 of 116 references.

References · 44

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  3. 2018QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 697
  4. 2016Learning to Communicate with Deep Multi-Agent Reinforcement Learningcited by 561
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  6. 2018Is Q-learning Provably Efficient?cited by 485
  7. 2019QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learningcited by 372
  8. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  9. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  10. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  11. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  12. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 189
32 more
  1. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  2. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  5. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  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. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  10. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  11. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  12. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  13. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  14. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  15. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  16. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  17. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  18. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  19. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  20. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 34
  21. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  22. 2021Learning in Nonzero-Sum Stochastic Games with Potentialscited by 25
  23. 2014Concurrent bandits and cognitive radio networkscited by 23
  24. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  25. 2018Learning Parametric Closed-Loop Policies for Markov Potential Gamescited by 20
  26. 2018Cooperative and Distributed Reinforcement Learning of Drones for Field Coveragecited by 20
  27. 2019Learning to Collaborate in Markov Decision Processescited by 14
  28. 2020Information State Embedding in Partially Observable Cooperative Multi-Agent Reinforcement Learningcited by 13
  29. 2021Online Learning for Cooperative Multi-Player Multi-Armed Banditscited by 12
  30. 2014Policy Iteration for Decentralized Control of Markov Decision Processescited by 10
  31. 2019Online Planning for Decentralized Stochastic Control with Partial History Sharingcited by 5
  32. 2020Reinforcement Learning in Decentralized Stochastic Control Systems with Partial History Sharingcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 8; 2023: 14; 2024: 9; 2025: 1; 2026: 2.

35 papers.

Sort:

By area:

  1. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  2. 2024Multi-Agent Reinforcement Learning for Autonomous Driving: A Surveycited by 30
  3. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  4. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  5. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  6. 2022Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Pathcited by 16
  7. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  8. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  9. 2023Dealing With Non-stationarity in Decentralized Cooperative Multi-Agent Deep Reinforcement Learning via Multi-Timescale Learningcited by 12
  10. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  11. 2022Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularizationcited by 10
  12. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
23 more
  1. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  2. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  3. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  4. 2023Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communicationcited by 8
  5. 2023Provably Learning Nash Policies in Constrained Markov Potential Gamescited by 7
  6. 2024Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Surveycited by 5
  7. 2025Independent Learning in Performative Markov Potential Gamescited by 5
  8. 2023Swapped goal-conditioned offline reinforcement learningcited by 3
  9. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  10. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  11. 2026Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regretcited by 3
  12. 2024Independent RL for Cooperative-Competitive Agents: A Mean-Field Perspectivecited by 2
  13. 2024Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to K-Level Stochastic Optimizationscited by 2
  14. 2022WILD-SCAV: Benchmarking FPS Gaming AI on Unity3D-based Environmentscited by 1
  15. 2022How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Gamescited by 1
  16. 2023Curiosity-driven Exploration in Sparse-reward Multi-agent Reinforcement Learningcited by 1
  17. 2024Differentially Private Reinforcement Learning with Self-Playcited by 1
  18. 2026Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptationcited by 1
  19. 2023Prioritized offline Goal-swapping Experience Replaycited by 0
  20. 2023Learning Strategic Value and Cooperation in Multi-Player Stochastic Games through Side Paymentscited by 0
  21. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0
  22. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Gamescited by 0
  23. 2024RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Modelcited by 0