# Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 57 references that are in the map.
- First posted on arXiv 29 May 2026.

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

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits](https://mlsanity.com/paper/2207.03106/) (2022)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes](https://mlsanity.com/paper/2110.11665/) (2021)
- [Delayed Feedback in Generalised Linear Bandits Revisited](https://mlsanity.com/paper/2207.10786/) (2022)
- [Differentially Private Stochastic Linear Bandits: (Almost) for Free](https://mlsanity.com/paper/2207.03445/) (2022)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [Solving Multi-Arm Bandit Using a Few Bits of Communication](https://mlsanity.com/paper/2111.06067/) (2021)
- [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)
- [Delayed Feedback in Kernel Bandits](https://mlsanity.com/paper/2302.00392/) (2023)
- [Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits](https://mlsanity.com/paper/2110.08057/) (2021)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)
- [Distributed Linear Bandits under Communication Constraints](https://mlsanity.com/paper/2211.02212/) (2022)
- [Optimal Batched Linear Bandits](https://mlsanity.com/paper/2406.04137/) (2024)
- [Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification](https://mlsanity.com/paper/2410.07533/) (2024)
- [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)

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

- [Memory--Batch Tradeoffs in Lipschitz Bandits](https://mlsanity.com/paper/2608.07922/) (2026)

## Abstract (arXiv)

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size B, and during each batch the learner sends B requested arm pulls to an agent, who then observes the corresponding B rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only or total bit budgets only. We establish a minimax lower bound showing that Omega(Bmind,loglvert A rvert) regret is unavoidable due to the 1-bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of widetildeOmega(Bmind,loglvert A rvert + √dT mind,loglvert A rvert). We develop two phased-elimination algorithms based on G-optimal designs and 1-bit mean estimation. The first achieves widetildeO(dB + d√T) regret, matching the lower bound up to logarithmic factors when lvert A rvert = exp(Omega(d)), and the second incorporates a safe-arm identification and warm-start procedure to obtain widetildeO(Bloglvert A rvert + d3/2√B + √dTloglvert A rvert) regret, which is near-optimal in broad scaling regimes of (lvert A rvert, B, d, T). Together, our results demonstrate that a single bit of feedback per batch suffices to nearly match the minimax regret of unconstrained linear bandits in broad scaling regimes, even for batch sizes as large as Theta(√T).