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
Scrape LinkedIn job postings without logging in (Python + Google Sheets)
0dev.to
Same model, same defences: 7 document attacks down to 0, chat attacks barely moved
0dev.to
Skill to Create Product Videos
0Hacker News
SOML – A Config Format for Humans
0Hacker News
Egoless Mathematics in the AI Era
0Hacker News
LifeVal
0OpenAI Blog