跳到正文
arXiv cs.AI· Khang Luong, Dinh Thai Son, Hoang Ta, Hung The Tran, Tuan Quang Dam·· 4 小时前AI 评分36

1-bit 反馈下近乎最优的固定置信度最优臂识别

Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback

AI 导读

arXiv 论文研究严格 1-bit 反馈约束下的固定置信度最优臂识别:每轮学习者选择臂和查询集,仅获得一个比特指示采样奖励是否属于该集合。论文基于随机化阈值查询和截断尾积分恒等式构造时间一致的 1-bit 均值估计基元,嵌入候选-挑战者算法,其中分阶段自适应截断算法获得 gap 自适应样本复杂度。

正文 · 原文

View PDF HTML (experimental)

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