An $\varepsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond
This work addresses the challenge of efficient arm identification in bandit problems for researchers and practitioners, but it is incremental as it extends the Top Two framework to approximate identification.
The authors tackled the problem of identifying an approximately best arm in stochastic bandits with a new algorithm called EB-TCε, which is the first Top Two algorithm analyzed for this task and works in both fixed-confidence and fixed-budget settings without modification. They proved asymptotic optimality in expected sample complexity and demonstrated favorable performance in simulations compared to existing methods.
We propose EB-TC$\varepsilon$, a novel sampling rule for $\varepsilon$-best arm identification in stochastic bandits. It is the first instance of Top Two algorithm analyzed for approximate best arm identification. EB-TC$\varepsilon$ is an *anytime* sampling rule that can therefore be employed without modification for fixed confidence or fixed budget identification (without prior knowledge of the budget). We provide three types of theoretical guarantees for EB-TC$\varepsilon$. First, we prove bounds on its expected sample complexity in the fixed confidence setting, notably showing its asymptotic optimality in combination with an adaptive tuning of its exploration parameter. We complement these findings with upper bounds on its probability of error at any time and for any error parameter, which further yield upper bounds on its simple regret at any time. Finally, we show through numerical simulations that EB-TC$\varepsilon$ performs favorably compared to existing algorithms, in different settings.