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

Riccardo Poiani, Martino Bernasconi & Andrea Celli · 2025

Read Non-Asymptotic Analysis of (Sticky) Track-and-Stop by Riccardo Poiani, Martino Bernasconi & Andrea Celli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22475.txt.

Introduction

Riccardo Poiani, Martino Bernasconi, and Andrea Celli present a 2025 arXiv paper on exploration algorithms that must answer questions about a random world with few samples and a strict error budget. Track-and-Stop, the classic method, is known to be sample-optimal as the allowed error shrinks to zero, and its sticky variant handles questions with several right answers.

What nobody had shown was how the pair behave at realistic, nonzero error levels. The authors supply those missing non-asymptotic guarantees for both algorithms. The bounds tell practitioners how many samples suffice long before the asymptotic story takes over.

Catalog record

CREATORRiccardo Poiani, Martino Bernasconi & Andrea Celli
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE107 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-22475

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Non-Asymptotic Analysis of (Sticky) Track-and-Stop Riccardo Poiani, Martino Bernasconi & Andrea Celli Abstract 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 δ \delta 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 \delta\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. , ϵ \epsilon -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. 1 Introduction In pure exploration problems, a statistician interacts with a set of K\in\mathbb{N} probability distributions denoted by \bm{\varphi}=\left\{\varphi_{i}\right\}_{i\in[K]} , commonly referred to as arms. Their unknown means are denoted by \bm{\mu}=\left\{\mu_{i}\right\}_{i\in[K]} , and \bm{\mu} belongs to some set \mathcal{M}\subseteq\mathbb{R}^{K} which encodes some possibly known structure among the different arms, e.g. , Lipschitzianity ( Wang et al., 2021 ) or unimodality ( Poiani et al., 2024 ) . During each step t\in\mathbb{N} , the statistician chooses an arm A_{t} , and observes a sample X_{t}\sim\varphi_{A_{t}} from the corresponding reward distribution. Given a maximum risk parameter \delta\in(0,1) , the statistician aims to answer a question about the unknown means \bm{\mu} while using as few samples as possible. Specifically, there is a known answer space \mathcal{I} and a (set-valued) answer function i^{\star}(\bm{\mu}) that maps each bandit \bm{\mu} to a subset of correct answers i^{\star}(\bm{\mu}) within \mathcal{I} . The probability of returning an answer that does not belong to i^{\star}(\bm{\mu}) should not exceed \delta . The most studied pure exploration problem is Best-Arm Identification ( Garivier & Kaufmann, 2016 , BAI,) , where the answer space is \{1,\dots,K\} and the goal is to return the unique index of the arm with the highest mean, i.e. , i^{\star}(\bm{\mu})=\operatornamewithlimits{argmax}_{k\in[K]}\mu_{k} . The pioneering work by Garivier & Kaufmann (2016) developed a tight lower bound for the unstructured BAI problem and proposed the Track-and-Stop ( TaS ) algorithm to solve it. Remarkably, the expected number of samples required by TaS to identify i^{\star}(\bm{\mu}) with high probability exactly matches the lower bound as \delta approaches 0 . In this sense, TaS is asymptotically optimal for \delta\to 0 . These results have been shown to hold even outside the BAI setting. Indeed, they extend to the more general structured partition identification problem ( Kaufmann & Koolen, 2021 ) . Here, \mathcal{M} is partitioned into a finite number |\mathcal{I}| of disjoint subsets, i.e. , \mathcal{M}=\bigcup_{i\in\mathcal{I}}\mathcal{M}_{i} , and the statistician aims to find i such that \bm{\mu}\in\mathcal{M}_{i} . In this sense, TaS turned out to be a powerful tool that can be used to solve a wide variety of problems ( i.e. , all the problems where i^{\star}(\bm{\mu}) is unique) while enjoying asymptotic optimality. If there exists multiple correct answers for a certain bandit \bm{\mu} , i.e. , i^{\star}(\bm{\mu}) is multi-valued, TaS fails to achieve optimality ( Degenne & Koolen, 2019 ) . This is the case, for instance, of the \epsilon -best arm identification problem, where multiple arms j might satisfy \mu_{j}\geq\operatornamewithlimits{argmax}_{k\in[k]}\mu_{k}-\epsilon . To solve this issue, Degenne & Koolen (2019) proposed a modification of the TaS algorithm called Sticky Track-and-Stop ( S-TaS ). S-TaS enjoys asymptotic optimality for any pure exploration problem with multiple correct answers. Due to their generality and strong theoretical guarantees, both TaS and S-TaS have become fundamental algorithms. However, as noted in several works, the analysis of TaS is asymptotic in nature and does not offer insights into its non-asymptotic behavior ( Barrier et al., 2022 ; Barrier, 2023 ; Jourdan & Degenne, 2023 ; Poiani et al., 2024 ; Russo et al., 2025 ) . Barrier (2023) suggest that this difficulty arises from instability in the sampling rule when data are scarce: the sampling rule employed by TaS can vary significantly early on, when estimated means have not yet concentrated around their expectations. The problem is even more pronounced for S-TaS . Intuitively, this is due to the fact that the algorithm is more complex, and that it samples the next arm in a TaS fashion. In this work, we address the following question: Can we characterize the non-asymptotic guarantees of TaS and S-TaS ? We answer this question by providing the first non-asymptotic bounds for both Track-and-Stop and Sticky Track-and-Stop, shedding light on their behavior in the finite-confidence setting. Our results hold for arbitrarily structured problems and correct answer correspondences. Importantly, from an empirical side, the performance of TaS has been benchmarked several times ( Degenne et al., 2019 ; Wang et al., 2021 ; Jourdan et al., 2022 ; Barrier et al., 2022 , e.g. ,) . The results have consistently shown that TaS obtains highly competitive sample complexity even in the moderate regime of \delta . Thus, the theoretical findings that we present here complement these results, showing that TaS also enjoys finite-confidence guarantees. Furthermore, since S-TaS is, to the best of the authors’ knowledge, the only algorithm in the literature that can solve arbitrary multiple answer problems, our work also provides the first finite-confidence analysis for this general class of problems . 1.1 Related Work Single-Answer Problems and TaS Since the work by Garivier & Kaufmann (2016) , which studied the unstructured bandit problem, several works have extended TaS to several structured problems ( Moulos, 2019 ; Juneja & Krishnasamy, 2019 ; Kocák & Garivier, 2020 ; Kaufmann & Koolen, 2021 ; Poiani et al., 2024 ; Kanarios et al., 2024 , e.g. ,) . In these works, the optimality analysis of TaS remained asymptotic, as they build upon the approach of Garivier & Kaufmann (2016) . Beyond TaS , several other algorithms have been proposed in the literature that achieve asymptotic optimality for best-arm identification and/or single-answer problems ( Degenne et al., 2019 ; Ménard, 2019 ; Wang et al., 2021 ; Barrier et al., 2022 ; Jourdan et al., 2022 ; Jourdan & Degenne, 2023 ) . Moreover, some of these works also establish non-asymptotic upper bounds on the expected number of samples required for their algorithm to stop ( Degenne et al., 2019 ; Barrier et al., 2022 ; Jourdan & Degenne, 2023 ; Wang et al., 2021 ) . Among these studies, the works most closely related to ours are Degenne et al. (2019) and Barrier et al. (2022) , which propose two distinct approaches that solve the aforementioned instability issue of TaS . Precisely, Degenne et al. (2019) propose an optimistic version of TaS that incorporates confidence intervals within the sampling rule. This comes at the cost of solving a significantly more challenging optimization problem in deciding the next arm to query. In particular, while TaS bases its decision rule on a maximization problem of a convex function over the simplex, its optimistic version requires solving a max-max-min problem

Read the complete text