AI & ML
Sharp Non-Asymptotic Analysis of the Penalized Challenger in $\beta$-EB-TCI for Bernoulli Bandits
arXiv stat.ML0 views
arXiv:2610.01951v2 Announce Type: replace-cross 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 question for Bernoulli bandits through $\beta$-EB-TCI, the empirical-best top-two rule of Jourdan et al., whose challenger minimizes a Bernoulli transportation cost plus a logarithmic penalty in its pull count. We first analyze the stabilized regime, in which the empirical leader has become the true best arm and its sampling fraction stays close to $\beta$. In this regime, every suboptimal arm is sampled linearly often, and, with high probability, the stopping time is at most $T_{\beta}^{\star}(\mu)\log(1/\delta)$ plus stabilization and lower-order concentration terms, with the exact fixed-$\beta$ leading coefficient. The main remaining difficulty is therefore to control when the regime is reached. For the original rule, we obtain a non-asymptotic high-probability stopping bound on every Bernoulli instance with a unique best arm. Under a finite-mean sufficient-exploration condition, the bound yields the sharp expected sample complexity; combined with the exploration result of Jourdan et al., this covers pairwise-distinct means under their tie-breaking convention. A mild forced-exploration guard, which uses only $O(\sqrt{Kt})$ pulls up to time $t$, gives a self-contained sharp expected bound for any number of arms with a unique best arm. We also identify a limitation of proof strategies that try to handle equal suboptimal means through a single index-comparison argument.
Source:https://arxiv.org/abs/2610.01951PreviousToward Optimal Switching Regret for Multi-Armed Bandits with Oblivious AdversaryNextProperty Report Email: 5 Checks for Malformed JSON Send Responses
Related posts
Best Firefox New Tab Extensions in 2026: Comparison (Free vs Paid)
0dev.to Productivity
Why I Stopped Checking My Weather App and Put the Forecast on My New Tab
0dev.to Productivity
Remote Work Across Time Zones: The Browser Setup That Keeps You Oriented
0dev.to Productivity
What to Put on Your Browser's New Tab: The Case for Ambient Information
0dev.to Productivity
Do Influencer Discount Codes Make Supplements Cheaper or Just Look Cheaper?
0dev.to Tutorial
What Supplement 'Challenge' Videos Get Wrong About Evidence
0dev.to Tutorial