# Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2019.

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

- [On Differentially Private Federated Linear Contextual Bandits](https://mlsanity.com/paper/2302.13945/) (2023)
- [Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost](https://mlsanity.com/paper/2205.13170/) (2022)
- [Breaking the log(1/Delta2) Barrier: Better Batched Best Arm Identification with Adaptive Grids](https://mlsanity.com/paper/2501.17370/) (2025)

## Abstract (arXiv)

We study the problem of regret minimization for distributed bandits learning, in which M agents work collaboratively to minimize their total regret under the coordination of a central server. Our goal is to design communication protocols with near-optimal regret and little communication cost, which is measured by the total amount of transmitted data. For distributed multi-armed bandits, we propose a protocol with near-optimal regret and only O(Mlog(MK)) communication cost, where K is the number of arms. The communication cost is independent of the time horizon T, has only logarithmic dependence on the number of arms, and matches the lower bound except for a logarithmic factor. For distributed d-dimensional linear bandits, we propose a protocol that achieves near-optimal regret and has communication cost of order tildeO(Md), which has only logarithmic dependence on T.