On Minimizing Regret in Fixed-Confidence $\varepsilon$-Best Arm Identification

This paper studies the $\varepsilon$-best arm identification problem ($\varepsilon$-BAI) for $K$-armed bandits under the fixed-confidence setting. Departing from the usual objective of identifying the best arm with minimal sample complexity, we focus on minimizing the cumulative regret of identifying an $\varepsilon$-best arm. We consider the usual asymptotic regime in which the error probability $\delta$ of identifying an $\varepsilon$-best arm vanishes. In this setting, we show a novel instance dependent lower bound. In particular, we show that any family of $(\varepsilon,\delta)$-PAC algorithms must incur an expected cumulative regret up to the stopping time that scales as $\log(1/\delta)$, with an instance-dependent constant $C(\mu)$. This is proved using a novel regret-aware change-of-measure technique that allocates information given a budget on the regret. To achieve this lower bound, we devise an algorithm, \algname, that achieves the same scaling in $\delta$, i.e., $\log (1/\delta)$, but with a different constant, which we call $C^\*(\mu)$. KL-UCB+Greedy has two main benefits: (i) it is computationally efficient as $C^\*(\mu)$ admits a closed-form expression; (ii) in broad classes of reward distributions such as Gaussian distributions, $C^\*( \mu) = C( \mu)$, demonstrating asymptotic optimality of KL-UCB+Greedy within these classes. As auxiliary results, we also derive lower bounds on the sample complexity of any family of $(\varepsilon,\delta)$-algorithms as $\delta$ vanishes and show that the sample complexity of KL-UCB+Greedy closely matches that of the lower bound on the sample complexity.