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

Build World Models for Interactive Simulation with NVIDIA Cosmos
0NVIDIA Developer Blog
Seeing and Imagining as One: Unified Video Generation and 4D Perception for Embodied World Modeling
0arXiv cs.RO
Shared Modular Recurrence in Contextual MDPs for Universal Morphology Control
0arXiv cs.RO
BeeTalk 群主必备:AI 群管机器人 AIGB 免费解决垃圾信息问题
0dev.to AI
I Open-Sourced a Free YouTube Shorts Factory. The Money Isn't in the Shorts.
0dev.to AI
Priced per TB/s, the H200 beats the H100 at 6 of 7 providers
0dev.to Python