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

arXiv: https://arxiv.org/abs/2505.22475 · HTML: https://mlsanity.com/paper/2505.22475/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 32 references that are in the map.
- First posted on arXiv 28 May 2025.

## Builds on (most cited first, 20 of 20)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Structure Adaptive Algorithms for Stochastic Bandits](https://mlsanity.com/paper/2007.00969/) (2020)
- [Gradient Ascent for Active Exploration in Bandit Problems](https://mlsanity.com/paper/1905.08165/) (2019)
- [Sample complexity of partition identification using multi-armed bandits](https://mlsanity.com/paper/1811.05654/) (2018)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Optimal Best Markovian Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1912.00636/) (2019)
- [Best Arm Identification in Spectral Bandits](https://mlsanity.com/paper/2005.09841/) (2020)
- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [Optimal Batched Best Arm Identification](https://mlsanity.com/paper/2310.14129/) (2023)
- [A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits](https://mlsanity.com/paper/2105.12978/) (2021)
- [On the complexity of All varepsilon-Best Arms Identification](https://mlsanity.com/paper/2202.06280/) (2022)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)

## Built on by (most cited first, 1 of 1)

- [Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning](https://mlsanity.com/paper/2607.17201/) (2026)

## Abstract (arXiv)

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 δ→ 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.