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

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 lower-order $\log\log$ 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.02771v1 [cs.LG] for this version)
	https://doi.org/10.48550/arXiv.2610.02771 arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Khang Luong [view email]
[v1] Fri, 2 Oct 2026 03:56:28 UTC (1,019 KB)