# Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2020.

## Built on by (most cited first, 30 of 38)

- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure](https://mlsanity.com/paper/2111.00781/) (2021)
- [Non-Stationary Representation Learning in Sequential Linear Bandits](https://mlsanity.com/paper/2201.04805/) (2022)
- [Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards](https://mlsanity.com/paper/2306.05579/) (2023)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)
- [When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Bandits](https://mlsanity.com/paper/2110.04396/) (2021)
- [Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environments](https://mlsanity.com/paper/2305.12795/) (2023)
- [Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions](https://mlsanity.com/paper/2106.04207/) (2021)
- [Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communication](https://mlsanity.com/paper/2110.07392/) (2021)
- [Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2206.02834/) (2022)
- [Collaborative Algorithms for Online Personalized Mean Estimation](https://mlsanity.com/paper/2208.11530/) (2022)
- [Cooperative Online Learning in Stochastic and Adversarial MDPs](https://mlsanity.com/paper/2201.13170/) (2022)
- [Collaborative Multi-agent Stochastic Linear Bandits](https://mlsanity.com/paper/2205.06331/) (2022)
- [Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2111.10933/) (2021)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Distributed Stochastic Bandit Learning with Delayed Context Observation](https://mlsanity.com/paper/2207.14391/) (2022)
- [Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2306.05998/) (2023)
- [Multi-Player Approaches for Dueling Bandits](https://mlsanity.com/paper/2405.16168/) (2024)
- [Cooperative Multi-Agent Constrained Stochastic Linear Bandits](https://mlsanity.com/paper/2410.17382/) (2024)
- [Heterogeneous Multi-agent Multi-armed Bandits on Stochastic Block Models](https://mlsanity.com/paper/2502.08003/) (2025)
- [Representation Learning for Context-Dependent Decision-Making](https://mlsanity.com/paper/2205.05820/) (2022)
- [Federated Learning for Heterogeneous Bandits with Unobserved Contexts](https://mlsanity.com/paper/2303.17043/) (2023)
- [Regret Lower Bounds in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2308.08046/) (2023)
- [Decentralized Blockchain-based Robust Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2402.04417/) (2024)
- [Decentralized multi-agent reinforcement learning algorithm using a cluster-synchronized laser network](https://mlsanity.com/paper/2407.09124/) (2024)
- [Multi-Agent Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2510.00602/) (2025)
- [Multi-Agent Lipschitz Bandits](https://mlsanity.com/paper/2602.16965/) (2026)
- [Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks](https://mlsanity.com/paper/2303.05445/) (2023)

## Abstract (arXiv)

We study a distributed decision-making problem in which multiple agents face the same multi-armed bandit (MAB), and each agent makes sequential choices among arms to maximize its own individual reward. The agents cooperate by sharing their estimates over a fixed communication graph. We consider an unconstrained reward model in which two or more agents can choose the same arm and collect independent rewards. And we consider a constrained reward model in which agents that choose the same arm at the same time receive no reward. We design a dynamic, consensus-based, distributed estimation algorithm for cooperative estimation of mean rewards at each arm. We leverage the estimates from this algorithm to develop two distributed algorithms: coop-UCB2 and coop-UCB2-selective-learning, for the unconstrained and constrained reward models, respectively. We show that both algorithms achieve group performance close to the performance of a centralized fusion center. Further, we investigate the influence of the communication graph structure on performance. We propose a novel graph explore-exploit index that predicts the relative performance of groups in terms of the communication graph, and we propose a novel nodal explore-exploit centrality index that predicts the relative performance of agents in terms of the agent locations in the communication graph.