arXiv：cs.LG（机器学习，全量分类）· Nam Nguyen, Tuan Quang Dam·· 14 小时前AI 评分31
β-EB-TCI 中惩罚挑战者的锐利非渐近分析：Bernoulli 多臂老虎机
Sharp Non-Asymptotic Analysis of the Penalized Challenger in $\beta$-EB-TCI for Bernoulli Bandits
AI 导读
研究针对 Bernoulli 多臂老虎机中 β-EB-TCI 算法的锐利非渐近行为，证明当经验领先臂成为真实最优臂且采样比例接近 β 后，停止时间为 T_β^★(μ)log(1/δ) 加上低阶集中项，且该阶段每个挑战者被线性采样。
正文
Abstract:Top-two algorithms are simple and effective for fixed-confidence best-arm identification, but their sharp non-asymptotic behavior is still not well understood. We study this problem for Bernoulli bandits through $\beta$-EB-TCI, the empirical-best top-two rule of Jourdan et al., whose challenger is chosen using a Bernoulli transportation cost with a logarithmic count penalty. We prove that, after the empirical leader has become the true best arm and its sampling fraction stays close to $\beta$, the stopping time is $T_{\beta}^{\star}(\mu)\log(1/\delta)$ up to lower-order concentration terms. We also show that, in this regime, every challenger is sampled linearly often. Thus, for the original algorithm without forced exploration, the main remaining difficulty is to control when the empirical leader becomes permanently correct. These results imply a non-asymptotic high-probability bound for all Bernoulli instances with a unique best arm. If the algorithm satisfies a finite-mean sufficient-exploration condition, the bound further yields the sharp expected sample complexity. In particular, this gives the sharp expectation result for the unguarded Bernoulli rule when all arm means are pairwise distinct, using the sufficient-exploration result of Jourdan et al. Finally, if we add a mild forced-exploration rule that contributes only $O(\sqrt{Kt})$ pulls up to time $t$, we obtain a self-contained expected sample-complexity theorem for any number of arms under the unique-best-arm assumption. We also identify a limitation of proof strategies that try to handle equal suboptimal means through a single index-comparison argument.
| Subjects: | Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.01951 [cs.LG] |
| (or arXiv:2610.01951v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.01951 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Nguyen Nam [view email]
[v1]
Thu, 1 Oct 2026 16:11:58 UTC (186 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org