# One More Step Towards Reality: Cooperative Bandits with Imperfect Communication

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

## Key facts

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

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

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Misspecified Linear Bandits](https://mlsanity.com/paper/1704.06880/) (2017)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [Multi-Armed Bandits with Correlated Arms](https://mlsanity.com/paper/1911.03959/) (2019)
- [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)
- [Best Arm Identification for Contaminated Bandits](https://mlsanity.com/paper/1802.09514/) (2018)
- [Online Distributed Optimization on Dynamic Networks](https://mlsanity.com/paper/1412.7215/) (2014)
- [A Dynamic Observation Strategy for Multi-agent Multi-armed Bandit Problem](https://mlsanity.com/paper/2004.03793/) (2020)
- [Heterogeneous Stochastic Interactions for Multiple Agents in a Multi-armed Bandit Problem](https://mlsanity.com/paper/1905.08731/) (2019)
- [Heterogeneous Explore-Exploit Strategies on Multi-Star Networks](https://mlsanity.com/paper/2009.01339/) (2020)
- [Distributed Learning: Sequential Decision Making in Resource-Constrained Environments](https://mlsanity.com/paper/2004.06171/) (2020)
- [Distributed Bandits: Probabilistic Communication on d-regular Graphs](https://mlsanity.com/paper/2011.07720/) (2020)

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

- [Non-Stationary Representation Learning in Sequential Linear Bandits](https://mlsanity.com/paper/2201.04805/) (2022)
- [Distributed Bandits with Heterogeneous Agents](https://mlsanity.com/paper/2201.09353/) (2022)
- [On-Demand Communication for Asynchronous Multi-Agent Bandits](https://mlsanity.com/paper/2302.07446/) (2023)
- [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)
- [Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs](https://mlsanity.com/paper/2308.04314/) (2023)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits](https://mlsanity.com/paper/2212.06279/) (2022)
- [Multi-Player Approaches for Dueling Bandits](https://mlsanity.com/paper/2405.16168/) (2024)
- [QuACK: A Multipurpose Queuing Algorithm for Cooperative k-Armed Bandits](https://mlsanity.com/paper/2410.23867/) (2024)
- [Differentially-Private Collaborative Online Personalized Mean Estimation](https://mlsanity.com/paper/2411.07094/) (2024)
- [Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Bandits](https://mlsanity.com/paper/2601.11924/) (2026)
- [Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks](https://mlsanity.com/paper/2303.05445/) (2023)
- [Adversarial Attacks on Cooperative Multi-agent Bandits](https://mlsanity.com/paper/2311.01698/) (2023)
- [Distributed No-Regret Learning for Multi-Stage Systems with End-to-End Bandit Feedback](https://mlsanity.com/paper/2404.04509/) (2024)

## Abstract (arXiv)

The cooperative bandit problem is increasingly becoming relevant due to its applications in large-scale decision-making. However, most research for this problem focuses exclusively on the setting with perfect communication, whereas in most real-world distributed settings, communication is often over stochastic networks, with arbitrary corruptions and delays. In this paper, we study cooperative bandit learning under three typical real-world communication scenarios, namely, (a) message-passing over stochastic time-varying networks, (b) instantaneous reward-sharing over a network with random delays, and (c) message-passing with adversarially corrupted rewards, including byzantine communication. For each of these environments, we propose decentralized algorithms that achieve competitive performance, along with near-optimal guarantees on the incurred group regret as well. Furthermore, in the setting with perfect communication, we present an improved delayed-update algorithm that outperforms the existing state-of-the-art on various network topologies. Finally, we present tight network-dependent minimax lower bounds on the group regret. Our proposed algorithms are straightforward to implement and obtain competitive empirical performance.