mlsanityData to 7 Oct 2026

Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximation

arXiv 2103.04972 ↗First posted 8 Mar 2021cs.LG cs.MA stat.MLcited by 23

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning in cooperative multi-agent settings has recently advanced significantly in its scope, with applications in cooperative estimation for advertising, dynamic treatment regimes, distributed control, and federated learning. In this paper, we discuss the problem of cooperative multi-agent RL with function approximation, where a group of agents communicates with each other to jointly solve an episodic MDP. We demonstrate that via careful message-passing and cooperative value iteration, it is possible to achieve near-optimal no-regret learning even with a fixed constant communication budget. Next, we demonstrate that even in heterogeneous cooperative settings, it is possible to achieve Pareto-optimal no-regret learning with limited communication. Our work generalizes several ideas from the multi-agent contextual and multi-armed bandit literature to MDPs and reinforcement learning.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 30 of its 79 references that are in the map. First posted on arXiv 8 Mar 2021.

Builds on

30 of 79 references.

References · 30

  1. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  2. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 866
  3. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2019Federated Machine Learning: Concept and Applicationscited by 409
  6. 2017On Kernelized Multi-armed Banditscited by 348
  7. 2018Distributed Prioritized Experience Replaycited by 260
  8. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  9. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 189
  10. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  11. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  12. 2018A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizationscited by 98
18 more
  1. 2016Multi-Objective Deep Reinforcement Learningcited by 81
  2. 2015Massively Parallel Methods for Deep Reinforcement Learningcited by 80
  3. 2019Lifelong Federated Reinforcement Learning: A Learning Architecture for Navigation in Cloud Robotic Systemscited by 77
  4. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  5. 2016Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithmscited by 48
  6. 2017Multi-Task Learning for Contextual Banditscited by 47
  7. 2013Distributed Exploration in Multi-Armed Banditscited by 46
  8. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  9. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  10. 2015On Distributed Cooperative Decision-Making in Multiarmed Banditscited by 33
  11. 2017Efficient Parallel Methods for Deep Reinforcement Learningcited by 32
  12. 2020Kernel Methods for Cooperative Multi-Agent Contextual Banditscited by 21
  13. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  14. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  15. 2020No-regret Algorithms for Multi-task Bayesian Optimizationcited by 18
  16. 2020Distributed Reinforcement Learning for Cooperative Multi-Robot Object Manipulationcited by 7
  17. 2019On Multi-Agent Learning in Team Sports Gamescited by 6
  18. 2018Decentralized Cooperative Stochastic Banditscited by 2

Built on by

Cited by year (2026 to 7 Oct)

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

23 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. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  3. 2021Provably Efficient Multi-Task Reinforcement Learning with Model Transfercited by 16
  4. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  5. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  6. 2021Adaptive Methods for Aggregated Domain Generalizationcited by 6
  7. 2021Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communicationcited by 5
  8. 2023Finite-sample Guarantees for Nash Q-learning with Linear Function Approximationcited by 4
  9. 2023Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learningcited by 4
  10. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  11. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  12. 2024Scalable spectral representations for multi-agent reinforcement learning in network MDPscited by 3
11 more
  1. 2022One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learningcited by 2
  2. 2023Communication-Efficient Collaborative Regret Minimization in Multi-Armed Banditscited by 2
  3. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  4. 2023Graph Exploration for Effective Multi-agent Q-Learningcited by 1
  5. 2023Scaling Distributed Multi-task Reinforcement Learning with Experience Sharingcited by 1
  6. 2023Communication-Efficient Federated Non-Linear Bandit Optimizationcited by 1
  7. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  8. 2025Concurrent Learning with Aggregated States via Randomized Least Squares Value Iterationcited by 0
  9. 2025The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportabilitycited by 0
  10. 2026Cooperative Multi-agent RL with Communication Constraintscited by 0
  11. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0