跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2605.30976 · v2

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

首次提交 2026-05-29 16:17
版本更新 2026-11-17 20:11
雷达观测 2026-11-18 11:33
arXiv ↗PDF ↗

摘要

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size BB, and during each batch the learner sends BB requested arm pulls to an agent, who then observes the corresponding BB 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 Ω(Bmin⁡{d,log⁡∣A∣})Ω(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 Ω~(Bmin⁡{d,log⁡∣A∣}+dTmin⁡{d,log⁡∣A∣})\widetildeΩ(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 GG-optimal designs and 1-bit mean estimation. The first achieves O~(dB+dT)\widetilde{O}(dB + d\sqrt{T}) regret, matching the lower bound up to logarithmic factors when ∣A∣=exp⁡(Ω(d))\lvert \mathcal{A} \rvert = \exp(Ω(d)), and the second incorporates a safe-arm identification and warm-start procedure to obtain O~(Blog⁡∣A∣+d3/2B+dTlog⁡∣A∣)\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 (∣A∣,B,d,T)(\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 Θ(T)Θ(\sqrt{T}).

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-17 20:11 · 最新观测版本

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 BB, and during each batch the learner sends BB requested arm pulls to an agent, who then observes the corresponding BB 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 Ω(Bmin⁡{d,log⁡∣A∣})Ω(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 Ω~(Bmin⁡{d,log⁡∣A∣}+dTmin⁡{d,log⁡∣A∣})\widetildeΩ(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 GG-optimal designs and 1-bit mean estimation. The first achieves O~(dB+dT)\widetilde{O}(dB + d\sqrt{T}) regret, matching the lower bound up to logarithmic factors when ∣A∣=exp⁡(Ω(d))\lvert \mathcal{A} \rvert = \exp(Ω(d)), and the second incorporates a safe-arm identification and warm-start procedure to obtain O~(Blog⁡∣A∣+d3/2B+dTlog⁡∣A∣)\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 (∣A∣,B,d,T)(\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 Θ(T)Θ(\sqrt{T}).

查看此版本解读 →查看此版本原文 ↗