mlsanityData to 7 Oct 2026

Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communication

arXiv 2110.07392 ↗First posted 14 Oct 2021cs.LG cs.MA math.OCcited by 5

Not on the map. Why?

Abstract (arXiv)

A challenge in reinforcement learning (RL) is minimizing the cost of sampling associated with exploration. Distributed exploration reduces sampling complexity in multi-agent RL (MARL). We investigate the benefits to performance in MARL when exploration is fully decentralized. Specifically, we consider a class of online, episodic, tabular Q-learning problems under time-varying reward and transition dynamics, in which agents can communicate in a decentralized manner.We show that group performance, as measured by the bound on regret, can be significantly improved through communication when each agent uses a decentralized message-passing protocol, even when limited to sending information up to its γ-hop neighbors. We prove regret and sample complexity bounds that depend on the number of agents, communication network structure and γ. We show that incorporating more agents and more information sharing into the group learning scheme speeds up convergence to the optimal policy. Numerical simulations illustrate our results and validate our theoretical claims.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 20 of its 29 references that are in the map. First posted on arXiv 14 Oct 2021.

Builds on

20 of 29 references.

References · 20

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  2. 2017Counterfactual Multi-Agent Policy Gradientscited by 733
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2013The Complexity of Decentralized Control of Markov Decision Processescited by 225
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  6. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  7. 2020Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 197
  8. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 189
  9. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  10. 2020ROMA: Multi-Agent Reinforcement Learning with Emergent Rolescited by 135
  11. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  12. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
8 more
  1. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  2. 2020Distributed Cooperative Decision Making in Multi-agent Multi-armed Banditscited by 38
  3. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 34
  4. 2020Cooperative Multi-Agent Bandits with Heavy Tailscited by 31
  5. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  6. 2021When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Banditscited by 7
  7. 2021MARL with General Utilities via Decentralized Shadow Reward Actor-Criticcited by 5
  8. 2020Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systemscited by 4

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2; 2024: 0; 2025: 2.

5 papers.

  1. 2025LEED: A Highly Efficient and Scalable LLM-Empowered Expert Demonstrations Framework for Multi-Agent Reinforcement Learningcited by 6
  2. 2022Cooperative Online Learning in Stochastic and Adversarial MDPscited by 4
  3. 2023Graph Exploration for Effective Multi-agent Q-Learningcited by 1
  4. 2023Multi-Agent Probabilistic Ensembles with Trajectory Sampling for Connected Autonomous Vehiclescited by 1
  5. 2025Multi-agent Uncertainty-Aware Pessimistic Model-Based Reinforcement Learning for Connected Autonomous Vehiclescited by 0