单比特反馈下,批量线性强化学习仍可近似最优。
Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
- 每批用1比特反馈,通过最优设计选择动作并估计均值。
- 理论证明批大小达√T时仍能接近无约束最优性能。
- 适合通信受限的分布式强化学习场景。
研究在批量与通信约束共存下的随机线性贝叶斯优化:时间轴被划分为大小为B的批次,每批中学习者向代理发送B个动作请求,代理观测对应奖励后仅返回1比特反馈。学习者可自定义每批的1比特量化规则,依赖历史比特但不直接依赖过往奖励。该设置填补了此前仅每轮量化或总比特预算模型之间的空白。我们建立了最小最大下界,表明即使无噪声,因1比特瓶颈,Ω(B min{d, log|A|})的遗憾不可避免;结合统计下限,得到一般性下界~Ω(B min{d, log|A|} + √(dT min{d, log|A|}))。提出两种基于G-最优设计和1比特均值估计的分阶段淘汰算法:第一种实现~O(dB + d√T)遗憾,当|A| = exp(Ω(d))时达到下界对数因子内;第二种引入安全臂识别与热启动机制,实现~O(B log|A| + d^{3/2}√B + √(dT log|A|))遗憾,在广泛参数范围内近乎最优。结果表明,每批仅需1比特反馈即可在多数尺度下逼近无约束线性贝叶斯优化的最小最大遗憾,即使批大小达Θ(√T)。
原文摘要 · Abstract (English)
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 $Ω(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Ω(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(Ω(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 $Θ(\sqrt{T})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。