# Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communication

arXiv: https://arxiv.org/abs/2110.07392 · HTML: https://mlsanity.com/paper/2110.07392/

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.10800/) (2020)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [ROMA: Multi-Agent Reinforcement Learning with Emergent Roles](https://mlsanity.com/paper/2003.08039/) (2020)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [Decentralized Q-Learning for Stochastic Teams and Games](https://mlsanity.com/paper/1506.07924/) (2015)
- [Cooperative Multi-Agent Bandits with Heavy Tails](https://mlsanity.com/paper/2008.06244/) (2020)
- [Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2103.04972/) (2021)
- [When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Bandits](https://mlsanity.com/paper/2110.04396/) (2021)
- [MARL with General Utilities via Decentralized Shadow Reward Actor-Critic](https://mlsanity.com/paper/2106.00543/) (2021)
- [Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems](https://mlsanity.com/paper/2001.10122/) (2020)

## Built on by (most cited first, 5 of 5)

- [LEED: A Highly Efficient and Scalable LLM-Empowered Expert Demonstrations Framework for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.14680/) (2025)
- [Cooperative Online Learning in Stochastic and Adversarial MDPs](https://mlsanity.com/paper/2201.13170/) (2022)
- [Graph Exploration for Effective Multi-agent Q-Learning](https://mlsanity.com/paper/2304.09547/) (2023)
- [Multi-Agent Probabilistic Ensembles with Trajectory Sampling for Connected Autonomous Vehicles](https://mlsanity.com/paper/2312.13910/) (2023)
- [Multi-agent Uncertainty-Aware Pessimistic Model-Based Reinforcement Learning for Connected Autonomous Vehicles](https://mlsanity.com/paper/2503.20462/) (2025)

## 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.