mlsanityData to 14 Oct 2026

Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation

arXiv 2305.06446 ↗First posted 10 May 2023cs.LG cs.AI cs.MAcited by 9

Not on the map. Why?

Abstract (arXiv)

We study multi-agent reinforcement learning in the setting of episodic Markov decision processes, where multiple agents cooperate via communication through a central server. We propose a provably efficient algorithm based on value iteration that enable asynchronous communication while ensuring the advantage of cooperation with low communication overhead. With linear function approximation, we prove that our algorithm enjoys an tildeO(d3/2H2√K) regret with tildeO(dHM2) communication complexity, where d is the feature dimension, H is the horizon length, M is the total number of agents, and K is the total number of episodes. We also provide a lower bound showing that a minimal Omega(dM) communication complexity is required to improve the performance through collaboration.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 53 of its 85 references that are in the map. First posted on arXiv 10 May 2023.

Builds on

53 of 85 references.

References · 53

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  2. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,103
  3. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 942
  4. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 883
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  6. 2017StarCraft II: A New Challenge for Reinforcement Learningcited by 274
  7. 2018Distributed Prioritized Experience Replaycited by 269
  8. 2018Human-level performance in first-person multiplayer games with population-based deep reinforcement learningcited by 264
  9. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  10. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  11. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  12. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 194
38 more
  1. 2019A Survey on Distributed Machine Learningcited by 188
  2. 2021Trust Region Policy Optimisation in Multi-Agent Reinforcement Learningcited by 186
  3. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  4. 2020Acme: A Research Framework for Distributed Reinforcement Learningcited by 146
  5. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  6. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  7. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  8. 2020Differentially-Private Federated Linear Banditscited by 83
  9. 2015Massively Parallel Methods for Deep Reinforcement Learningcited by 82
  10. 2021Federated Reinforcement Learning: Techniques, Applications, and Open Challengescited by 81
  11. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  12. 2019Lifelong Federated Reinforcement Learning: A Learning Architecture for Navigation in Cloud Robotic Systemscited by 78
  13. 2020Towards Playing Full MOBA Games with Deep Reinforcement Learningcited by 78
  14. 2022Federated Reinforcement Learning with Environment Heterogeneitycited by 63
  15. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  16. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  17. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 54
  18. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  19. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  20. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  21. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  22. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  23. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  24. 2019Federated Deep Reinforcement Learningcited by 35
  25. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  26. 2017Efficient Parallel Methods for Deep Reinforcement Learningcited by 32
  27. 2021Asynchronous Upper Confidence Bound Algorithms for Federated Linear Banditscited by 31
  28. 2020When Deep Reinforcement Learning Meets Federated Learning: Intelligent Multi-Timescale Resource Management for Multi-access Edge Computing in 5G Ultra Dense Networkcited by 30
  29. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  30. 2022A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Banditscited by 28
  31. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  32. 2022Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learningcited by 27
  33. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  34. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  35. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  36. 2022Learn to Match with No Regret: Reinforcement Learning in Markov Matching Marketscited by 16
  37. 2022Distributed Contextual Linear Bandits with Minimax Optimal Communication Costcited by 13
  38. 2021DeepMTL Pro: Deep Learning Based MultipleTransmitter Localization and Power Estimationcited by 10

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

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

9 papers.

  1. 2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learningcited by 9
  2. 2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scalecited by 8
  3. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  4. 2024Policy Optimization finds Nash Equilibrium in Regularized General-Sum LQ Gamescited by 2
  5. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  6. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1
  7. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 1
  8. 2025Concurrent Learning with Aggregated States via Randomized Least Squares Value Iterationcited by 0
  9. 2026Cooperative Multi-agent RL with Communication Constraintscited by 0