# When to Call Your Neighbor? Strategic Communication in Cooperative Stochastic Bandits

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

## Key facts

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

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

- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [Cooperative Multi-Agent Bandits with Heavy Tails](https://mlsanity.com/paper/2008.06244/) (2020)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)
- [Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits](https://mlsanity.com/paper/1907.03346/) (2019)
- [Bayesian Algorithms for Decentralized Stochastic Bandits](https://mlsanity.com/paper/2010.10569/) (2020)
- [Heterogeneous Stochastic Interactions for Multiple Agents in a Multi-armed Bandit Problem](https://mlsanity.com/paper/1905.08731/) (2019)
- [Distributed Learning: Sequential Decision Making in Resource-Constrained Environments](https://mlsanity.com/paper/2004.06171/) (2020)

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

- [Non-Stationary Representation Learning in Sequential Linear Bandits](https://mlsanity.com/paper/2201.04805/) (2022)
- [Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communication](https://mlsanity.com/paper/2110.07392/) (2021)
- [Communication-Efficient Collaborative Best Arm Identification](https://mlsanity.com/paper/2208.09029/) (2022)
- [Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits](https://mlsanity.com/paper/2305.18784/) (2023)
- [Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits](https://mlsanity.com/paper/2301.11442/) (2023)
- [Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs](https://mlsanity.com/paper/2308.04314/) (2023)
- [Learning with Limited Shared Information in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2502.15338/) (2025)
- [Pay to Learn, Share to Earn: Incentivized Federated Multi-Player Bandits](https://mlsanity.com/paper/2610.06062/) (2026)

## Abstract (arXiv)

In cooperative bandits, a framework that captures essential features of collective sequential decision making, agents can minimize group regret, and thereby improve performance, by leveraging shared information. However, sharing information can be costly, which motivates developing policies that minimize group regret while also reducing the number of messages communicated by agents. Existing cooperative bandit algorithms obtain optimal performance when agents share information with their neighbors at textitevery time step, i.e., full communication. This requires Theta(T) number of messages, where T is the time horizon of the decision making process. We propose textitComEx, a novel cost-effective communication protocol in which the group achieves the same order of performance as full communication while communicating only O(log T) number of messages. Our key step is developing a method to identify and only communicate the information crucial to achieving optimal performance. Further we propose novel algorithms for several benchmark cooperative bandit frameworks and show that our algorithms obtain textitstate-of-the-art performance while consistently incurring a significantly smaller communication cost than existing algorithms.