# Distributed Linear Bandits under Communication Constraints

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 67 references that are in the map.
- First posted on arXiv 4 Nov 2022.

## Builds on (most cited first, 30 of 33)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization](https://mlsanity.com/paper/1909.13014/) (2019)
- [Federated Learning with Compression: Unified Analysis and Sharp Guarantees](https://mlsanity.com/paper/2007.01154/) (2020)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Adaptive Quantization of Model Updates for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2102.04487/) (2021)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Impact of Representation Learning in Linear Bandits](https://mlsanity.com/paper/2010.06531/) (2020)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [DAdaQuant: Doubly-adaptive quantization for communication-efficient Federated Learning](https://mlsanity.com/paper/2111.00465/) (2021)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [On Distributed Cooperative Decision-Making in Multiarmed Bandits](https://mlsanity.com/paper/1512.06888/) (2015)
- [Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradients](https://mlsanity.com/paper/1909.07588/) (2019)
- [Multi-Agent Multi-Armed Bandits with Limited Communication](https://mlsanity.com/paper/2102.08462/) (2021)
- [Communication-Efficient Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2003.06307/) (2020)
- [Towards Efficient Communications in Federated Learning: A Contemporary Survey](https://mlsanity.com/paper/2208.01200/) (2022)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [Solving Multi-Arm Bandit Using a Few Bits of Communication](https://mlsanity.com/paper/2111.06067/) (2021)
- [Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost](https://mlsanity.com/paper/2205.13170/) (2022)
- [Game of Thrones: Fully Distributed Learning for Multi-Player Bandits](https://mlsanity.com/paper/1810.11162/) (2018)
- [Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection](https://mlsanity.com/paper/2009.02003/) (2020)
- [Optimality guarantees for distributed statistical estimation](https://mlsanity.com/paper/1405.0782/) (2014)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)

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

- [The Sample-Communication Complexity Trade-off in Federated Q-Learning](https://mlsanity.com/paper/2408.16981/) (2024)
- [A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regret](https://mlsanity.com/paper/2301.08869/) (2023)
- [Federated Linear Bandits with Finite Adversarial Actions](https://mlsanity.com/paper/2311.00973/) (2023)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization](https://mlsanity.com/paper/2501.03222/) (2025)
- [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)
- [Remote Action Generation: Remote Control with Minimal Communication](https://mlsanity.com/paper/2605.01833/) (2026)

## Abstract (arXiv)

We consider distributed linear bandits where M agents learn collaboratively to minimize the overall cumulative regret incurred by all agents. Information exchange is facilitated by a central server, and both the uplink and downlink communications are carried over channels with fixed capacity, which limits the amount of information that can be transmitted in each use of the channels. We investigate the regret-communication trade-off by (i) establishing information-theoretic lower bounds on the required communications (in terms of bits) for achieving a sublinear regret order; (ii) developing an efficient algorithm that achieves the minimum sublinear regret order offered by centralized learning using the minimum order of communications dictated by the information-theoretic lower bounds. For sparse linear bandits, we show a variant of the proposed algorithm offers better regret-communication trade-off by leveraging the sparsity of the problem.