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
Cilium 1.20.0 Requires BTF Flag in Linux Kernel, Raspberry Pi OS Kernel Incompatible Without It
0dev.to
YC Labs and Olam Labs ran 50 AI agents in a Minecraft civilization experiment
0dev.to
Lavoro su piattaforma e algoritmi: cosa cambia con la direttiva europea per chi progetta il software
0dev.to
LifeVal Benchmark Targets Everyday Personal Assistant Tasks Shaped by ChatGPT User Feedback
0dev.to
Oracle files to sell $20B in new stock, bonds to finance AI buildout
0Hacker News
7.9% to 48.1%: LLM rewrote Qwen weights, no training
0dev.to