Non-Asymptotic Analysis of (Sticky) Track-and-Stop

In pure exploration problems, a statistician sequentially collects information to answer a question about some stochastic and unknown environme nt. The probability of returning a wrong answer should not exceed a maximum risk p arameter δ and good algorithms make as few queries to the environment as pos sible. The Track-and-Stop algorithm is a pioneering method to solve these pro blems. Specifically, it is well-known that it enjoys asymptotic optimality sampl e complexity guarantees for δ 0 whenever the map from the environment to its correct answers is single-valued ( e.g., best-arm identification with a unique optimal arm). The Sticky Track-and-Stop algorithm extends these results to s ettings where, for each environment, there might exist multiple correct answers ( e.g., ǫ -optimal arm identification). Although both methods are optimal in the asympt otic regime, their non-asymptotic guarantees remain unknown. In this work, we fill this gap and provide non-asymptotic guarantees for both algorithms.