Non-Asymptotic Analysis of (Sticky) Track-and-Stop
This work addresses a gap in theoretical analysis for statisticians and machine learning researchers by offering non-asymptotic guarantees for algorithms used in sequential decision-making under uncertainty, though it is incremental as it builds on existing asymptotic results.
The paper tackles the problem of providing non-asymptotic sample complexity guarantees for Track-and-Stop and Sticky Track-and-Stop algorithms in pure exploration, which previously only had asymptotic optimality results, and derives explicit bounds for these algorithms.
In pure exploration problems, a statistician sequentially collects information to answer a question about some stochastic and unknown environment. The probability of returning a wrong answer should not exceed a maximum risk parameter $δ$ and good algorithms make as few queries to the environment as possible. The Track-and-Stop algorithm is a pioneering method to solve these problems. Specifically, it is well-known that it enjoys asymptotic optimality sample complexity guarantees for $δ\to 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 settings where, for each environment, there might exist multiple correct answers (e.g., $ε$-optimal arm identification). Although both methods are optimal in the asymptotic regime, their non-asymptotic guarantees remain unknown. In this work, we fill this gap and provide non-asymptotic guarantees for both algorithms.