Sharp Non-Asymptotic Analysis of the Penalized Challenger in $\beta$-EB-TCI for Bernoulli Bandits
This paper studies fixed-confidence best-arm identification for Bernoulli bandits using the top-two $\beta$-EB-TCI rule, where the challenger is selected by a penalized Bernoulli GLR index. Its core contribution is a sharp non-asymptotic analysis: once the true best arm becomes the permanent leader and its sampling fraction stays near $\beta$, the stopping time is $T_\beta^\star(\mu)\log(1/\delta)$ up to lower-order terms. The paper also identifies exactly where the analysis stalls for the unguarded rule when suboptimal means are tied, and closes the gap with a mild $O(\sqrt{Kt})$ exploration guard.
The paper delivers a strong, technically careful contribution: the first sharp non-asymptotic leading-coefficient bound for the exact penalized Bernoulli EB-TCI challenger. The decomposition into a stabilized-regime analysis (Theorem 5.2) and a separate entry-time analysis (Sections 5–6) is conceptually clean. However, the sharpest expected bound is ultimately obtained only for a guarded variant or for a specific tie-breaking convention; the unguarded deterministic rule with tied suboptimal means is left unresolved, which limits the unconditional punch of the result.
The stabilized-regime machinery is solid. Theorem 4.2 establishes a time-uniform empirical-to-population pairwise Bernoulli GLR bound under adaptive sampling, and Proposition 4.1 approximates the discrete penalized allocation benchmark by the continuous characteristic time up to an $O(1)$ discretization error. Together these yield Theorem 5.2, which shows that in the stabilized regime the stopping time has leading term $T_\beta^\star(\mu)\log(1/\delta)$ and every suboptimal arm is sampled linearly often. The exploration guard in Algorithm 1 is simple, deterministic, and adds only $O(\sqrt{Kt})$ pulls, yielding a self-contained expected bound (Theorem 6.7). The experiments support the theory: mean stopping times track the threshold-crossing predictor $t_{\mathrm{pred}}$ within roughly 1.5–4% relative error.
The conditional nature of the main bound is a significant structural limitation. Theorem 5.2 assumes a stabilization time $t_U$ is given; the remaining Sections 5–6 bound this time, but the unguarded high-probability bound (Corollary 6.3) contains a term polynomial in $1/\eta$, whose tail is too heavy to integrate into an expected stopping-time bound. The authors are explicit about this: the expected bound for the unguarded algorithm with deterministic tie-breaking remains incomplete when several suboptimal arms share the same mean. Proposition 6.8 shows that a single pointwise penalized-index comparison cannot force the challenger count to grow fast enough, but this is a proof-technique limitation, not an algorithmic impossibility, leaving the expected bound in limbo. Additionally, the analysis is heavily Bernoulli-specific (relying on exact KL structure and pooled-mean formulas), andextensions to general bounded rewards would require rebuilding the GLR concentration arguments.
The comparisons to prior work are fair and accurate. The authors correctly distinguish their setting from Jourdan et al. (2022), who proved asymptotic $\beta$-optimality for bounded rewards but not sharp non-asymptotic bounds, and from Jourdan and Degenne (2023), who gave the first non-asymptotic top-two expected bound but for a Gaussian UCB-based rule. Both distinctions are verified by the cited abstracts. The experimental section is diagnostic rather than comprehensive: only three small instances ($K\in\{4,5\}$) are tested, with 200 replications each, and no head-to-head comparison with Track-and-Stop or LUCB is performed. However, the experiments do convincingly validate that observed stopping times closely follow the $T_\beta^\star(\mu)\log(1/\delta)$ predictor, and that removing the logarithmic penalty severely hurts performance on equal-mean suboptimal arms.
The algorithm and stopping threshold are specified in full detail (Algorithm 1, Equation 3.1), and the exploration guard is deterministic and easy to implement. The paper states that a supplementary code package is available, but no public URL, repository link, or formal artifact appendix is provided in the text itself. Reproduction from scratch is therefore possible in principle—all hyperparameters and the allocation benchmark are explicit—but independent verification would be significantly easier with released code and data. The Bernoulli-specific concentration bounds (Appendix D) and population calculus (Appendix C) are carefully written and could, in principle, be checked step by step.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.