# Communication-Constrained Bandits under Additive Gaussian Noise

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 23 references that are in the map.
- First posted on arXiv 25 Apr 2023.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization](https://mlsanity.com/paper/1908.08200/) (2019)
- [Solving Multi-Arm Bandit Using a Few Bits of Communication](https://mlsanity.com/paper/2111.06067/) (2021)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)
- [Information-constrained optimization: can adaptive processing of gradients help?](https://mlsanity.com/paper/2104.00979/) (2021)
- [Fundamental limits of over-the-air optimization: Are analog schemes optimal?](https://mlsanity.com/paper/2109.05222/) (2021)

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

- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2509.21940/) (2025)
- [Batched Stochastic Linear Bandits with 1-Bit Communication Constraints](https://mlsanity.com/paper/2605.30976/) (2026)
- [Secure Best Arm Identification in the Presence of a Copycat](https://mlsanity.com/paper/2507.18975/) (2025)

## Abstract (arXiv)

We study a distributed stochastic multi-armed bandit where a client supplies the learner with communication-constrained feedback based on the rewards for the corresponding arm pulls. In our setup, the client must encode the rewards such that the second moment of the encoded rewards is no more than P, and this encoded reward is further corrupted by additive Gaussian noise of variance σ2; the learner only has access to this corrupted reward. For this setting, we derive an information-theoretic lower bound of Omegaleft(√fracKTmathttSNR wedge1 right) on the minimax regret of any scheme, where  mathttSNR := fracPσ2, and K and T are the number of arms and time horizon, respectively. Furthermore, we propose a multi-phase bandit algorithm, mathttUE-UCB++, which matches this lower bound to a minor additive factor. mathttUE-UCB++ performs uniform exploration in its initial phases and then utilizes the em upper confidence bound (UCB) bandit algorithm in its final phase. An interesting feature of mathttUE-UCB++ is that the coarser estimates of the mean rewards formed during a uniform exploration phase help to refine the encoding protocol in the next phase, leading to more accurate mean estimates of the rewards in the subsequent phase. This positive reinforcement cycle is critical to reducing the number of uniform exploration rounds and closely matching our lower bound.