Sharp Non-Asymptotic Analysis of the Penalized Challenger in β-EB-TCI for Bernoulli Bandits
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 β-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 β, the stopping time is Tβ⋆(μ)log(1/δ) 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(√(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.
Related
- Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping
- Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits
- Serrin-type overdetermination in scaling limits: Sharp existence and asymptotic behavior of quasi-linear Schrödinger energy ground states
- Integral of Scalar Curvature: Sharp Asymptotic Bounds and Rigidity
- A sharp asymptotic bound for odd cycles in planar graphs
BibTeX
@misc{nguyen2026sharp,
title = {{Sharp Non-Asymptotic Analysis of the Penalized Challenger in $β$-EB-TCI for Bernoulli Bandits}},
author = {Nam Nguyen and Tuan Quang Dam},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01951},
eprint = {2610.01951},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01951},
}
RIS
TY - UNPB
TI - Sharp Non-Asymptotic Analysis of the Penalized Challenger in β-EB-TCI for Bernoulli Bandits
AU - Nam Nguyen
AU - Tuan Quang Dam
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01951
UR - https://arxiv.org/abs/2610.01951
AB - 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 β-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 β, the stopping time is T_β^⋆(μ)log(1/δ) 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(√(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.
ER -