← 研踪 PaperTrailarXiv: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
摘要
We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size , and during each batch the learner sends requested arm pulls to an agent, who then observes the corresponding 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 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 . We develop two phased-elimination algorithms based on -optimal designs and 1-bit mean estimation. The first achieves regret, matching the lower bound up to logarithmic factors when , and the second incorporates a safe-arm identification and warm-start procedure to obtain regret, which is near-optimal in broad scaling regimes of . 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 .
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 , and during each batch the learner sends requested arm pulls to an agent, who then observes the corresponding 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 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 . We develop two phased-elimination algorithms based on -optimal designs and 1-bit mean estimation. The first achieves regret, matching the lower bound up to logarithmic factors when , and the second incorporates a safe-arm identification and warm-start procedure to obtain regret, which is near-optimal in broad scaling regimes of . 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 .
查看此版本解读 →查看此版本原文 ↗