# Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 26 May 2022.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Robotics](https://mlsanity.com/paper/1602.04450/) (2016)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Stagewise Safe Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1806.07555/) (2018)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [Multi-user Communication Networks: A Coordinated Multi-armed Bandit Approach](https://mlsanity.com/paper/1808.04875/) (2018)
- [Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication](https://mlsanity.com/paper/1904.06309/) (2019)

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

- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [Distributed Linear Bandits under Communication Constraints](https://mlsanity.com/paper/2211.02212/) (2022)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)
- [Parallel Best Arm Identification in Heterogeneous Environments](https://mlsanity.com/paper/2207.08015/) (2022)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Differentially Private Kernelized Contextual Bandits](https://mlsanity.com/paper/2501.07046/) (2025)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [Batched Stochastic Linear Bandits with 1-Bit Communication Constraints](https://mlsanity.com/paper/2605.30976/) (2026)
- [Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness](https://mlsanity.com/paper/2402.13182/) (2024)
- [Multi-Agent Best Arm Identification in Stochastic Linear Bandits](https://mlsanity.com/paper/2411.13690/) (2024)
- [Service Placement in Small Cell Networks Using Distributed Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2506.22480/) (2025)
- [Differential Privacy in Kernelized Contextual Bandits via Random Projections](https://mlsanity.com/paper/2507.13639/) (2025)
- [BALLAST: Bandit-Assisted Learning for Latency-Aware Stable Timeouts in Raft](https://mlsanity.com/paper/2512.21165/) (2025)

## Abstract (arXiv)

We study distributed contextual linear bandits with stochastic contexts, where N agents act cooperatively to solve a linear bandit-optimization problem with d-dimensional features over the course of T rounds. For this problem, we derive the first ever information-theoretic lower bound Omega(dN) on the communication cost of any algorithm that performs optimally in a regret minimization setup. We then propose a distributed batch elimination version of the LinUCB algorithm, DisBE-LUCB, where the agents share information among each other through a central server. We prove that the communication cost of DisBE-LUCB matches our lower bound up to logarithmic factors. In particular, for scenarios with known context distribution, the communication cost of DisBE-LUCB is only tildeO(dN) and its regret is tildeO(√dNT), which is of the same order as that incurred by an optimal single-agent algorithm for NT rounds. We also provide similar bounds for practical settings where the context distribution can only be estimated. Therefore, our proposed algorithm is nearly minimax optimal in terms of both regret and communication cost. Finally, we propose DecBE-LUCB, a fully decentralized version of DisBE-LUCB, which operates without a central server, where agents share information with their immediate neighbors through a carefully designed consensus procedure.