# Solving Multi-Arm Bandit Using a Few Bits of Communication

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

## Key facts

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

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

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [A Survey on Practical Applications of Multi-Armed and Contextual Bandits](https://mlsanity.com/paper/1904.10040/) (2019)
- [RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization](https://mlsanity.com/paper/1908.08200/) (2019)
- [On Distributed Quantization for Classification](https://mlsanity.com/paper/1911.00216/) (2019)
- [One-bit feedback is sufficient for upper confidence bound policies](https://mlsanity.com/paper/2012.02876/) (2020)

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

- [Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning](https://mlsanity.com/paper/2301.00944/) (2023)
- [Almost Cost-Free Communication in Federated Best Arm Identification](https://mlsanity.com/paper/2208.09215/) (2022)
- [Federated Best Arm Identification with Heterogeneous Clients](https://mlsanity.com/paper/2210.07780/) (2022)
- [Distributed Linear Bandits under Communication Constraints](https://mlsanity.com/paper/2211.02212/) (2022)
- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Rate-Constrained Remote Contextual Bandits](https://mlsanity.com/paper/2204.12620/) (2022)
- [Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2509.21940/) (2025)
- [Communication-Constrained Bandits under Additive Gaussian Noise](https://mlsanity.com/paper/2304.12680/) (2023)
- [Remote Contextual Bandits](https://mlsanity.com/paper/2202.05182/) (2022)
- [Multi-Agent Bandit Learning through Heterogeneous Action Erasure Channels](https://mlsanity.com/paper/2312.14259/) (2023)
- [Model-Free Learning for the Linear Quadratic Regulator over Rate-Limited Channels](https://mlsanity.com/paper/2401.01258/) (2024)
- [Batched Stochastic Linear Bandits with 1-Bit Communication Constraints](https://mlsanity.com/paper/2605.30976/) (2026)
- [Learning in Distributed Contextual Linear Bandits Without Sharing the Context](https://mlsanity.com/paper/2206.04180/) (2022)
- [ICQ: A Quantization Scheme for Best-Arm Identification Over Bit-Constrained Channels](https://mlsanity.com/paper/2305.00528/) (2023)
- [Does Feedback Help in Bandits with Arm Erasures?](https://mlsanity.com/paper/2504.20894/) (2025)
- [Remote Action Generation: Remote Control with Minimal Communication](https://mlsanity.com/paper/2605.01833/) (2026)

## Abstract (arXiv)

The multi-armed bandit (MAB) problem is an active learning framework that aims to select the best among a set of actions by sequentially observing rewards. Recently, it has become popular for a number of applications over wireless networks, where communication constraints can form a bottleneck. Existing works usually fail to address this issue and can become infeasible in certain applications. In this paper we address the communication problem by optimizing the communication of rewards collected by distributed agents. By providing nearly matching upper and lower bounds, we tightly characterize the number of bits needed per reward for the learner to accurately learn without suffering additional regret. In particular, we establish a generic reward quantization algorithm, QuBan, that can be applied on top of any (no-regret) MAB algorithm to form a new communication-efficient counterpart, that requires only a few (as low as 3) bits to be sent per iteration while preserving the same regret bound. Our lower bound is established via constructing hard instances from a subgaussian distribution. Our theory is further corroborated by numerically experiments.