Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

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 $\text{or}$ total bit budgets only. We establish a minimax lower bound showing that $\Omega (B\min \{d,\log |\mathcal{A}|\})$ 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 $\tilde{\Omega }(B\min \{d,\log |\mathcal{A}|\}+\sqrt{dT\min \{d,\log |\mathcal{A}|\}})$. We develop two phased‑elimination algorithms based on $G$-optimal designs and 1‑bit mean estimation. The first achieves $\tilde{O}(dB+d\sqrt{T})$ regret, matching the lower bound up to logarithmic factors when $|\mathcal{A}|=\exp (\Omega (d))$, and the second incorporates a safe‑arm identification and warm‑start procedure to obtain $\tilde{O}(B\log |\mathcal{A}|+d^{3/2}\sqrt{B}+\sqrt{dT\log |\mathcal{A}|})$ regret, which is near‑optimal in broad scaling regimes of $(|\mathcal{A}|,B,d,T)$. Together, our results demonstrate that a single bit of feedback per batch suffices to preserve nearly order‑optimal regret across a wide range of settings, even in the case of large batch sizes such as $\Theta (\sqrt{T})$.