mlsanityData to 14 Oct 2026

Approximate Global Convergence of Independent Learning in Multi-Agent Systems

arXiv 2405.19811 ↗First posted 30 May 2024cs.LG cs.MAcited by 3

Not on the map. Why?

Abstract (arXiv)

Independent learning (IL), despite being a popular approach in practice to achieve scalability in large-scale multi-agent systems, usually lacks global convergence guarantees. In this paper, we study two representative algorithms, independent Q-learning and independent natural actor-critic, within value-based and policy-based frameworks, and provide the first finite-sample analysis for approximate global convergence. The results imply a sample complexity of tildeO(ε-2) up to an error term that captures the dependence among agents and characterizes the fundamental limit of IL in achieving global convergence. To establish the result, we develop a novel approach for analyzing IL by constructing a separable Markov decision process (MDP) for convergence analysis and then bounding the gap due to model difference between the separable MDP and the original one. Moreover, we conduct numerical experiments using a synthetic MDP and an electric vehicle charging example to verify our theoretical findings and to demonstrate the practical applicability of IL.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 18 of its 70 references that are in the map. First posted on arXiv 30 May 2024.

Builds on

18 of 70 references.

References · 18

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  2. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 194
  3. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  4. 2020Game-Theoretic Multiagent Reinforcement Learningcited by 94
  5. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  6. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  7. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  8. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  9. 2021Multi-Agent Reinforcement Learning for Active Voltage Control on Power Distribution Networkscited by 54
  10. 2020Multi-agent Reinforcement Learning for Networked System Controlcited by 53
  11. 2020Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Rewardcited by 50
  12. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
6 more
  1. 2020Multi-Agent Reinforcement Learning in Stochastic Networked Systemscited by 32
  2. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  3. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  4. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  5. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  6. 2022An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithmscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 1.

3 papers.

  1. 2024Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rankcited by 6
  2. 2025Structured Cooperative Multi-Agent Reinforcement Learning: a Bayesian Network Perspectivecited by 0
  3. 2026Decentralized Safe Multi-Agent Reinforcement Learning via Predictive Shieldingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games
  2. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Players
  3. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
  4. 2024On the Convergence of Single-Timescale Actor-Critic
  5. 2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale
  6. 2026Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics
  7. 2025Emergent Coordination and Phase Structure in Independent Multi-Agent Reinforcement Learning
  8. 2026Provably Convergent Actor-Critic for MARL through Risk-aversion