1-bit 反馈下近乎最优的固定置信度最优臂识别
Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
AI 导读
arXiv 论文研究严格 1-bit 反馈约束下的固定置信度最优臂识别:每轮学习者选择臂和查询集,仅获得一个比特指示采样奖励是否属于该集合。论文基于随机化阈值查询和截断尾积分恒等式构造时间一致的 1-bit 均值估计基元,嵌入候选-挑战者算法,其中分阶段自适应截断算法获得 gap 自适应样本复杂度。
正文 · 原文
Abstract:We study fixed-confidence best-arm identification under strict 1-bit feedback constraints. At each round, the learner selects an arm and a query set, and receives only a single bit indicating whether the sampled reward belongs to that set. We consider a distribution-free finite-variance setting with arm-wise localization, where direct empirical mean estimation is no longer available and clipping becomes unavoidable. We first formulate a time-uniform 1-bit mean-estimation primitive based on randomized threshold queries and a clipped tail-integral identity. We then embed this primitive into candidate-challenger best-arm identification algorithms. A fixed-clipping algorithm gives a simple anytime $(\epsilon,\delta)$-PAC guarantee, while a phased adaptive-clipping algorithm matches the clipping level to the current resolution and yields a gap-adaptive sample complexity. We also prove a $K$-arm worst-case information-theoretic lower bound showing that the logarithmic penalty caused by finite-variance 1-bit feedback is intrinsic. This bound matches the leading dependence of the phased algorithm up to logarithmic factors.
| Comments: | To appear in Advances in Neural Information Processing Systems 39 (NeurIPS 2026, Spotlight) |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.02771 [cs.LG] |
| (or arXiv:2610.02771v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.02771 arXiv-issued DOI via DataCite |
Submission history
From: Khang Luong [view email]
[v1]
Fri, 2 Oct 2026 03:56:28 UTC (1,019 KB)
[v2]
Fri, 13 Nov 2026 04:07:10 UTC (1,019 KB)
来源:arXiv cs.AI · arxiv.org