الملخص
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 $(ε,δ)$-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.
الكلمات المفتاحية
الموضوع
بيانات النشر
- المجلة
- غير متاح
- وصول مفتوح
- وصول مفتوح أخضر
اقتبس هذه المقالة
APA 7
Luong, K., Son, D. T., Ta, H., Tran, H. T., & Dam, T. Q. (2026). Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback. https://omanscience.com/ar/articles/nearly-optimal-fixed-confidence-best-arm-identification-with-1-bit-feedback
MLA 9
Luong, Khang, et al. "Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback." https://omanscience.com/ar/articles/nearly-optimal-fixed-confidence-best-arm-identification-with-1-bit-feedback.
شيكاغو (المؤلف–التاريخ)
Luong, Khang, Dinh Thai Son, Hoang Ta, Hung The Tran, and Tuan Quang Dam. 2026. "Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback." https://omanscience.com/ar/articles/nearly-optimal-fixed-confidence-best-arm-identification-with-1-bit-feedback.
هارفارد
Luong, K., Son, D. T., Ta, H., Tran, H. T. and Dam, T. Q. (2026) 'Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback', Available at: https://omanscience.com/ar/articles/nearly-optimal-fixed-confidence-best-arm-identification-with-1-bit-feedback.
فانكوفر
Luong K, Son DT, Ta H, Tran HT, Dam TQ. Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback. https://omanscience.com/ar/articles/nearly-optimal-fixed-confidence-best-arm-identification-with-1-bit-feedback
IEEE
K. Luong, D. T. Son, H. Ta, H. T. Tran, and T. Q. Dam, "Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback," https://omanscience.com/ar/articles/nearly-optimal-fixed-confidence-best-arm-identification-with-1-bit-feedback.