AI & ML
Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
arXiv stat.ML0 views
arXiv:2605.30976v2 Announce Type: replace Abstract: 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(B\min\{d,\log\lvert \mathcal{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 $\widetilde{\Omega}(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}})$. We develop two phased-elimination algorithms based on $G$-optimal designs and 1-bit mean estimation. The first achieves $\widetilde{O}(dB + d\sqrt{T})$ regret, matching the lower bound up to logarithmic factors when $\lvert \mathcal{A} \rvert = \exp(\Omega(d))$, and the second incorporates a safe-arm identification and warm-start procedure to obtain $\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})$ regret, which is near-optimal in broad scaling regimes of $(\lvert \mathcal{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(\sqrt{T})$.
Source:https://arxiv.org/abs/2605.30976PreviousKernel-based guarantees for nonlinear parametric models in Bayesian optimizationNextFormalizing the Intrinsic Dimension of Objective Landscapes by a Generalized Notion of Co-dimension
Related posts
Managing frontier AI risk: From training to deployment
0OpenAI Blog
Geocoding Indian Addresses: A Validation Checklist for Civic Data
0dev.to
DaisyRose-27B: 1,200-task RL took Qwen3.8 from 5.6% to 12% on Terminal-Bench 4.1
0Hacker News
Sam Altman says his life is so weird that he’s unphased by Andrew Garfield portraying him in upcoming movie
0TechCrunch
Gemini price increases: Carbon and Argon double on 1 December 2026, Flash on 1 January 2027
0dev.to
OpenAI shuts down whisper-1 and its other transcription models on 26 February 2027: a migration checklist
0dev.to