Non-Asymptotic Analysis of (Sticky) Track-and-Stop
Authors: Riccardo Poiani
Martino Bernasconi
Andrea Celli
Venue: ICLR 2026 Oral (2026)
Keywords: Multi-Armed Bandit Theory
Pure Exploration
Fixed-Confidence
Primary area: learning theory
TL;DR: We derive non-asymptotic guarantees for the Track-and-Stop and Sticky Track-and-Stop algorithms.

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 $\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.

Published as a conference paper at ICLR 2026
NON-ASYMPTOTE ANALYSIS OF (STICKY) TRACK- AND-STOP
Riccardo Poiani, Martino Bernasconi & Andrea Celli
Bocconi University Milan, Italy
rriccardo.poian wtw.aaaimmattnno.beeeeeee htt.thi...brmascc.....eeeeeeeee.
ABSTRACT
In pure exploration problems, a statistician sequentially collects information to an- swer 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 the environment as possible. The Track- and-Stop algorithm is pioneering method to solve these problems. Specifically, it is well-known that it enjoys asymptotic optimality sample complexity guaran- tees for 5 + 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-Suu algorithm extends these results to settings where, for each environment, there might exist multiple correct answers (c.g., 6-optimal arm iden- tification). Although both methods 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.
INTRODUCTION
In pure exploration problems, a statistician interacts with a set of K E N probability distributions denoted by &p [ejk' commonly referred to arms. Their unknown means denoted by μ = {ni}ıe|K and belongs to some set M S R. which encodes some possibly known structure among the different arms, e.g., Lipschitzianity (Wang et al., 2021) or unimodality (Poiani al., 2024). During each step & N, the statistician chooses arm At, and observes sample X₂ :AA. from the corresponding reward distribution. Given maximum risk parameter 8 = (0, 1), the statistician aims to answer question about the unknown means μe while using as few samples as possible. Specifically, there is a known answer space I and a (set-valued) answer function i (1)) that maps each bandit ş subset of correct answers i (11) within I. The probability of returning an answer that does not belong to i* (J)) should not exceed 6.
The most studied pure exploration problem is Best-Arm Identification (BAI, Garivier & Kaufmann, 2016), where the answer space is (1..... K) and the goal is to return the unique index of the arm with the highest mean, i.e., i (44) = argmax#е[K] μ4.- The pioncering work by Garivier & Kaufmann (2016) developed tight lower bound for the unstructured BAI problem and proposed the (TAS) algorithm to solve it. Remarkably, the expected number of samples required by TAS to identify i (Ju) with high probability exactly matches the lower bound as å approaches 0. In this sense, TAS is asymptotically optimal for ö + 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, M is partitioned into finite number [Z] of disjoint subsets, i.e. M = UsezM,, and the statistician aims to find i such that μ E .,,. In this sense, TAS turned to be powerful tool that be used to solve wide variety of problems (i.e., all the problems where i* (14) is unique) while enjoying asymptotic optimality. there exists multiple correct answers for certain bandit μ. i.e., (1) is multi-valued, TAS fails to achieve optimality (Degenne & Koolen, 2019). This is the case, for instance, of the e-best arm identification problem, where multiple arms j might satisfy H2 2 argmax A c. To solve this issue, Degenne & Koolen (2019) proposed modification of the TAS algorithm called Sticky Track-and (S-

---

Published as a conference paper at ICLR 2026
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 fun- damental 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 S-TAS. Intuitively, this is due to the fact that the algorithm is more complex, and that it samples the next arm in TAS fashion.
In this work, we address the following question:
Can we characterize the non-asymplotic 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-Stopp shedding light on their behavior in the finite-confidenc 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 (e.g., Degenne et al., 2019; Wang et al., 2021; Jourdan et al., 2022; Barrier et al., 2022). The results have consistently shown that TAS obtains highly competitive sample complexity even in the moderate regime of d. 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- lnite-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 stud- ied the unstructured bandit problem, several works have extended TAS to several structured prob- lems (e.g.. Moulos, 2019; Juneja Koolen, 2021; Poiani et al., 2024; Kanarios et al., 2024). 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 optimal- ity for best-arm identification and/or single-answe 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 afore- mentioned instability issue of TAS. Precisely, Degenne et al. (2019) propose optimistic version of TAS that incorporates confidence intervals within the sampling rule. This comes at the cost of solving 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 max-max-min problem which, in general, does not admit efficient oracles. Barrier et al. (2022), instead, stabilizes the sampling rule by "skewing" its behavior toward uniform exploration when the amount of data collected is scarce. This modi- fication, however, can lead to a decrease in the empirical performance w.r.t. the original version. Indeed, Barrier et al. (2022) show that the original version of TAS achieves better results in all in- stances in which the algorithms were compared. Hence, given these remarks, it remains important to understand whether finite confidence guarantees can be obtained for the original version of TAS. In this sense, note that both the analyses of Degenne et al. (2019) and Barrier et al. (2022) rely on specific properties of the algorithms they introduce, which makes them different from the original framework of Garivier & Kaufmann (2016). To the best of our knowledge. work is the first to provide non non-asyna asymmtotttiic guarantees for the original TAS algorithm without requiring any substantial modifications to it.
Krishnasamy, 2019; Kocák & Garivier, 2020; Kaufmann &
2

---

Published as a conference paper at ICLR 2026
Multiple-Answer Problems and S-TAS When there multiple correct answers, S-TAS (De- genne & Koolen, 2019) offers a solution to pure exploration problems while enjoying asymptotic optimality. However, the best of our knowledge, there is no variant of S-TAS that achieves finite- confidence guarantees in arbitrary multiple-answer problems. More broadly, we are not aware of any algorithm providing finte-confiience guarantees for general multiple-answer problems. Prior work has largely focused on specific subclasses of pure exploration problems. Among these, the most studied one e-best arm identification (e.g.. Even-Dar al., 2002; Kalyanakrishnan et al., 2012; Karmin et al., 2013; Kocák & Garivier, 2021; Jourdan et al., 2023; Jin et al., 2024). Nonetheless, none of these studies can be applied to the general pure exploration setting of Degenne & Koolen (2019).
BACKGROUND
We focus on bandit problems &p { |E]K] with K E N arms, where 9i is a probability distribu- tion with mean Pk- We denote by μ = {1K [KE[K] the vector of the means of the distributions. As usual in the literature (see e.g., Garivier & Kaufmann (2016); Degenne et al. (2019)), distributions that belong to a canonical exponential family' It is well known that such distributions are fully characterized by their means. For convenience, we will refer to a bandit model o directly by its vector of means μ.. We denote by é C R an open set that defines the possible means of the distributions. We consider the general case where μ E M O This allows to include in our analysis also structured settings such as Lipschitz (Wang et al., 2021) or unimodal bandits (Poiani et al., 2024). Indeed, since M is any subset of OK it can directly encode the constraints imposed by these structures. Moreover, we assume finite answer space I, along with access to set-valued function i : M = I, which maps each model μ E M to the set of all the answers that are correct for the bandit instance J..
focus on
At each step t E N. the learner chooses an action A: E [K] and observes a sample X, ~ AA Let F, (A,, X1, ...... Xe) up to time t. Then, a pure exploration algorithm receives as input a confidence level 8 E (0, 1), and implements the following procedures: (i) Fi-1 measurabbl sampling rule which selects the action A, E [K] based on the past observations, (ii) a stopping rule Ta which is a stopping time w.r.t. (Fi)ten and controls the end of the data acquisition phase, and (iii) Fr, -measurable recom- mendation rule i,y E I that denotes the guess of the statistician for a correct answer for J.. A pure exploration algorithm is ò-correct on M if satisfies P Pu(ārg & i" (H)) S for all μ E M. The goal is building algorithms which are d-correct and that minimize the expected stopping time, i.e. En [78] = ELE(K] F (Ta))) where N&(()) the number of samples collected for arm k [K] up to time t. In the following, we denote by (t) the vector
be the o-fiel generated by the interactions with the bandit model
Additional Notation For a given set X. we denote by cl(x) its closure. Furthermore, for all i E I, we denote by -i = {X E M: : (A)).. In words, -i represents the set of bandit models for which i is not correct answer. Without loss of generality, we assume that for all exists i E (1)) such that μa & cl(-i).² Furthermore, for distributions with means p and q, we write d(p, q) to denote their KI. divergence. Moreover, for distribution with mean p. we denote by Up the corresponding natural parameter within the exponential family. For n E N, An denotes the n- dimensional simplex. Finally, consider two topological spaces X' and Y, and consider set-valued function F: : X = y that maps each x E X to F(x) S D. We say that F is upper hemicontinuous, if for all x E X' and any open set V C y such that F(x) C V. there exists a neighbourhood U of such that, for all x' eú, F(x') is subset of y (Aubin, 1999).
M, there
Lower Bound for Single-Answer Problems Let us focus on the case where i (14) is unique for all μ E M. Lower bounds for these problems can be derived following the arguments presented
I 'These include Gaussian with known variance and Bernoulli distributions. See Cappé et al. (2013).
For completeness, we show in Appendix A how to encode these structures through M.
' is easy to verify from the lower bounds that, whenever this assumption is not satisfied, one obtains infinite sample complexity. This requirement is usually implicitly satisfied in the literature, e.g. argmax (K) pe is unique over M in best-arm identification problems (Degenne & Koolen, 2019), and the different sets M, are open and disjoint in the partition identification problem (Wang et al., 2021).
3

---

Published as a conference paper at ICLR 2026
in Garivier & Kaufmann (2016). Specifically, for any 8-correct algorithm, it holds that Ey(Ta]
2
(H)) log(1/(2.46)) (see Appendix B for a formal statement), where:
(n) sup max inf WEAK PE AE kE[K]
sup inf Σ RE[K]
wxd(ues Ax)
(1)
WEAR (E-iT())
Σ
wadkuun Ax)).
(2)
Th (1)) can be interpreted max-min game where the max player plays sampling strategy w to quickly identify the correct answer i' (1), and the min-player chooses a confounding instance À E . where the correct answer changes (Degenne et al., 2019). The convex set of weights that attains the argmax in (+) are denoted by w (14) and takes the name of oracle weights. Here, convexity simply follows from the fact T (1+) -1 is a supremum over functions that are linear in w. We note that we provided two expressions for (M)
Equation (1) is the one that most frequently appears in the literature (e.g., Garivier Kaufmann (2016)). Equation (2) is a rewriting that allows to generalize the expression of (1) to bandit models jts that fall outside M, as i (J4) is formally defined only for μ E M.. This is important from an algorithmic perspective as it allows us to generalize the definition of oracle weights to models that are not in M. Furthermore, we shall see, it will also play an important role in our analysis. Finally, since the problem is single-answer, then for all μ M the argmax over the different answers is attained only at i i" (1z).
Lower Bound for Multiple-Answer Problems Lower bounds for multiple-answer problems were established by Degenne & Koolen (2019). Specifically, the authors shows that, for any d-correct Ey [7a] algorithm and any μ E M, it holds that lim inf log(1/8) (formal statement in Appendix B):
2 (H)), where T (m) is given by
T (1)
sup max inf WEAN (E) AE-1
Σ kE[K]
wad(wwk As)
(3)
sup max inf WEAK IEI XETİ
Σ
wid(us AR)-
(4)
KE[K]
We have introduced two expressions for (m) one that only applies to models within M (Equation (3)), and another that extends the definition to models outside M (Equation (4)).
While these results closely resemble those of single-answer problems, few differences need to be highlighted. First, this lower bound only holds in the asymptotic regime of 8 +
Second, the argmax in (H)) over the different answers can be attained at multiple points. Specifically, let ir(1)) be the set of answers that attain the argmax, ie., (F(() argmax SUPWEAK inf i Exe(Ky wgd(us, As). Then, while for single answer problems (((())] = [(*())] = for all μ E M, in multiple answer problems it can happen that (i(()) 1. Since it plays crucial role in our results, we emphasize that the correspon- dence E (p()) is upper hemicontinuous (Theorem 4 of Degenne & Koolen (2019)). Fi- nally, we mention that the oracle weights (H) are no longer convex set when (()( > 1. Instead, we have that w²(H)) = Useritn (m) wn (1, -i), where each element w (1,, mi) = argmax inf ExE[K] Wyd(uu, 2x) is convex set.
Track-and-Stop Track-and-Stop (TAS, Garivier & Kaufmann, 2016) works as follows. After first phase where each arm k E [K] is pulled once, TAS computes, at each round f, the empirical or- acle weights (t) E w (fu(t), where (t) N₂ - 1(A, = k),x, denotes the empirical estimate of μ4 at time t. Then, TAS applies a tracking procedure on (w)t) to select the next action. Specifically, the C-Tracking procedure projects each (t) onto A = A 1]a according to the fo norm. This projection takes the name of forced exploration, it ensures that N₁ (t) Z vt for all E [K] for E, R t-12 The next action is selected as Ac+1 E argmax Σ'= Wu (s) NN, where each (s)) denotes the projection of wss). Regarding the stopping and recommendation rules, TAS halts as soon as max;ez inf ΣkE[k] Nu (t) A&) 2 B.,s. and recommends
an index that attains the argmax in the stopping rule. By calibrating the threshold Br, (typically,
Indeed, we observe that an empirical estimate of ya might not belong to M.
4

---

Published as a conference paper at ICLR 2026
B1,5 log(1/6)+ K log(t); see e.g., Kaufmann & Koolen (2021) for complete expression of $1,6) one can prove that those stopping and recommendation rules yield 5-correctness (both for single and multiple-answer problems) when paired with any sampling rule." $ TAS enjoys asymptotic optimality E,,Ta - ( However, this does not hold guarantees whenever [() = 1, í.e., lim supsoo [og[1
for (1) > 1 (Degenne & Koolen, 2019). The reason is that its sampling rule ensures that the em- pirical pull strategy (tt/tt converges (on good event) to the convex hull of the oracle weights, i.e, wnf (p)) (t) wil - 0. When [ 1, this convex hull coincides with w (H), and this leads to optimality, However, this is not generally true in the context of multiple-answer problems.
Sticky Track-and-Stop To solve this issue, Degenne & Koolen (2019) proposed the Sticky Track- and-Stop (S-TAS) algorithm. The stopping and recommendation rules are the same used by TAS. As for the sampling rule, S-TAS defines a confidence region C2 around p(t), i.e., C2 = {A E M : ExElK| (t()) 2x) I 8K log(t)) ) computes set I, of candidate answers follows: 4 UxEc, if (2). Then, S-TAS selects an answer it E Z, according to some pre-specified total order over I, and it computes (t) E w ('((()), -4)) for the selected answer it Finally, it selects the next action A, by applying the C-Tracking sampling rule over the sequence {t) The main idea behind S-TAS is that, due to the
of μ4 B (F)),, the set will eventually collapse (under good event) to if (J)) for sufficiently large L. Then, since in is chosen according to a pre-specified total order over I, & will be fixed to some 1 E if (p()). and the C-Tracking sampling rule will ensure that infwew (j,. -x) [tt/t w|l - 0. As shown by Degenne & Koolen (2019), this property leads asymptotic optimality both in single and multiple-answer problems.
NON-ASYMPTOTIC ANALYSIS FOR TRACK-
First, we present two assumptions that we will use in our analysis. Assumption
Arms), Arms belongs to a o2-uub sub-Gaussian exponential i.e.,
for all μ. p¹ θ, it holds d(u,, n²) Assumption (Bounded parameters). There exists jamins [rmas] C
(m-n²)²
20
② such that M C [Ammin [mmx]]
Both Assumptions 1 and 2 are mild requirements that have been frequently adopted in the literature; see e.g., Degenne et al. (2019; 2020); Jourdan et al. (2021); Poiani et al. (2024). Assumption is used primarily for concentration arguments. Assumption 2 implies that, for any two distributions p and q within [mminn [max] it holds that d(p, q) I. L and | vyyl S D, for some constants and D. These two properties are the main reason for introducing Assumption in our analysis.?
Before introducing our result, we make minor modification to the TAS algorithm that allows for a simpler analysis. Specifically, instead of computing (() E w (f((()), computes w() e w" (i)))), where jū(t) denotes the orthogonal projection of ju(t) onto [Mminn Mmax] |K This modifi- cation is only required to ensure that d((px (t), "welllbehaver" whenever is small. Such projection has already been adopted in sampling rules for algorithms that provide unite-confidence guarantees, see, e.g., the regret minimization approach presented in Degenne et al. (2019). More formally, its purpose is ensuring that (t), A) is bounded for all steps and any [Mmmnn [max]] We note that this modification is only needed to handle pathological cases that might arises when dealing with arbitrary canonical exponential families and is not needed, e.g., when the family of distributions is Gaussian. Later in this section, we discuss how to drop the projection step and how this affects the resulting guarantees. We are now ready to state our confiidnnee result for TAS.
Theorem 1 (Non-Asymptotic Bound for TAS). Lei (-) be single-valued. and suppose that As- sumption I and Assumption 2 hold. Then, the expected stopping time of TAS satisfies Fxl[Ta) S 2eK 10K* + To( where To (ō) is given by
( inf {t E N Rr,5 S -g(()))
(5)
'For completeness, we report a formal statement and a proof in Lemma 10.
"Sec Lemma 6 and Theorem 7 in Degenne et al. (2019).
7 We refer the interested reader to Appendix C for further details.
'Note that, since M is know by definition, are Mmin and Pmax- In other words, this kind of modification does require additional knowledge of the problem.
5

---

Published as a conference paper at ICLR 2026
where g(t) 64o log log(K) (oog (t) + 16 Dy D log(t).
Theorem provides the finite-confidem bound on the performance of TAS. First, we note that the upper bound is expressed independent terms are artifact of the analysis and their origin is detailed in the proof sketch provided below. The last and more important term, (o))), is function of 6, which essentially captures how quickly the quantity maxęer infxe-i EmE[A] NA (t)d(((a Au)) is approaching the stopping threshold Br,6- Indeed, IT (1² g(t) is essentially lower bound (under good event) on the aforementioned optimization problem: when this quantity exceeds 31,5. TAS stops. In other words, (o) measures how fast TAS is gathering information
sum of three terms, i.e., 2eK, 10K* and To(ő). The first two 8-
discriminate (H() from all the other candidate answers. By re-arranging the condition in Equation (5), i.e, Be. + g(t) S tT (m)-1 we can see that the r.h.s. grows linearly in t. while the lhs.s. is growing sub-linearly with a rate of (log(1/0) /8) + ($/4). This ensures that (ō) is finite and that Theorem 1 recovers the asymptotic optimality of TAS whenever 5 + O. Finally, although (ō) is defined somehow implicitly, in Appendix G we derive further upper bound that highlights that the scaling T (og(1))) up to polylogarithmic factors and constant terms.
Proof Sketch As we discussed, the original analysis of TAS is asymptotic in nature. In contrast, we follow a different path which is inspired by finite-confidence analysis in the lit- erature, e.g., Degenne et al. (2019); Jourdan & Degenne (2023). In particular, we con- duct the analysis under a sequence of good events (Er)e. Specifically, we consider & Vss E [[V],]] ΣxE(K] Na(s)d((u(())))))) (4) 8K (ogg(s)) This sequence of events has two de-
sirable properties. First, one can show that CESPAAEE I 2eK (see Lemma 9). Second, as we discuss below, there exists a time I such that for all 2 T, & implies stopping, namely & S (Te S t}. Using these two properties one obtains that Eu S T + 2eK (see Lemma 1). In the remainder of the proof, ment mentioned earlier. Before doing that, we introduce some additional notation. Recall that (s) argmax maxtez infxe- à EkE[K] (x Then, denote by I any answer that attains the argmax when paired with (s).
will show how T = (6( + 10K* satisfies the require-
Now, the key idea is analyzing the stopping rule of TAS and, in particular, lower bound- ing maxiez inf xe - Eke(ky (f) Ax) to obtain (T) g().. To this end, as we shall see, the crucial step is approximating (up to a sublinear in / factor) the max-min prob- lem of the stopping rule with what TAS uses in the sampling rule in each round s 2 vt. i.e. infxe i. ΣkEjK] (e(s)d((Me (s), Xx). Further comments on this are provided right after the proof sketch. Now, for any Z 10K 10 TAS has not stopped at time I, then the following holds:
Be,5 inf
Σ
Nu(t)d(Ak,.)) A4)
(Stopping Rule)
XE (14 kE(K]
inf XE at (1)
Σ Ax())d((e,Aat) kE[K]
(E + C-Tracking)
inf de kE[K]
Σ
wx(s)d(Hps -x) -O(VV)
Here, C-tracking ensures that (()) se Ex_1 (s)), and under the event & we have ((), R d(pp.-). :). In the last step. we have used that if i, (1) then the claim is trivial, and if de * (p)), then, P E -d.. We observe that this argument explicitly relies on the fact that
(p)) is single-valued." Now, we analyze the information accumulated by TAS by lower bound- ing Di infxe-i, EnERR (x)d Ax). Using the definition of & and the fact that (s) e
Here, plugged in Br,8 log(1/8) + K log(t).
This requirement is due to some technical step that is used at the end of the proof. "Tis is important to be noted, otherwise it might seems that TAS achieves asymptotically optimal results even in problems with multiple correct answers.

---

Published as a conference paper at ICLR 2026
[mmnn Mmax]
we have that
inf XE
Σ (a(s)d(pu,)e) kE[K]
Σ inf $2VE
Σ kE[K]
wh (x)
AE
#=1
We have reached our goal of lower bounding the stopping rule of TAS with its sampling rule. Using the definition of ig and w(s, this allows for the following inequalities:
Σ 22VE
inf Σ AE kE[K]
(e())d(fe(()), Ax)
E
sup max inf
E ke(K]
(s)
22v8 WEAR EET AETI
Σ Σ inf
wtd((in(s)
(for E w (p))
XE (1)) kE[K]
22vi
(1 Vl ()- (3/2),
(By E.)
where the second step holds for any w² E (1) and the last one requires an algebraic step that requires 2 10K Intuitively, however, this last step is still using the fact that d(ūx ()) s d(px:)) under the good event. Chaining together all the terms within the O(-) yields the desired result.
The proof idea As anticipated above, the main idea is approximating up to a sub-linear in factor, the condition used in the stopping rule with the quantity Enevt infxe i, ΣxE[K] [ (s) (s), As), which is what TAS uses in its sampling rule. Once this is done, can use the definition of (s)) and i, to introduce the optimal weights w for the underlying unknown problem and the infimum over -i* (1x). Importantly, we observe that the generalization of w" that we provided in Equation (2) played a crucial role. Finally, by upper-bounding the difference between the desired quantity as it allows to recover the asymptotic optimality.
; A&) and d(pk, As), we introduce (z) which
Removing the projection step We discuss how to obtain finite-confidence guarantees for a version TAS that does not use projection in the sampling rule, i.e., exactly the version of TAS by Garivier & Kaufmann (2016). Before that, we make a remark on Assumption 2. Let μ E M and let F2 min Mmin |, |Ptk - /mmxx) } and F min Fk. Then, since θ is open interval and since [pmin Mmax] is closed, it follows that F; > 0 Ak E [K], and thus F > 0. That being said, the simplest way to analyze TAS without projection follows by noticing that there exists a time TM E N such that, for all > TM, on &,, it holds that (ss) E [pmin Mmax] for all 2 vt (see Lemma 3 in Appendix E). TM depends only M and its distance F from the interval [Mmin- Mmma]; precisely:
TM = max { 10K- inf NEN:
64 K log(n)
VVn - S F JJ
(6)
This allows us analyze the stopping time under a good event in the same way that we did above. Indeed, it sufficient that (sf)(s),)) well-behaves only at steps & 2 vi. Thus, the only difference with respect to Theorem would be the additional term TM in the upper bound of [Tx].
NON-ASYMPTOTIC ANALYSIS FOR STICKY TRACK-AND-STOR
In this section, we present the finite-confidence analysis of S-TAS. As for TAS, we will rely on Assumptions 1 and 2. Furthermore, for reasons similar those discussed above, we consider slightly modified version of S-TAS that incorporates a projection into its sampling rule. Specifically, the algorithm computes (s) E wn (ï(s), -i... 13 The following theorem summarizes our result.
This is needed upper hound (s)) Av.) d(Fx, Az). Indeed, ((jia(s). Xa) d(ps; Ax) S (Mpe(H) Dry (8) - Mal & (8) - s&l since (*()), ) X E [Mmin [mmaa..
Using the same argument that we discussed in Section 3, it is possible to analyze the version of S-TAS that does use projection. The sample complexity results differ only by the additional term TM-
7

---

Published as a conference paper at ICLR 2026
Theorem 2 ASym-osypii Bound for Sticky-TAS). Suppose that Assumption I and Assumption
hold. Let En > be any number such that, for all yt 1l 1ll S Cus, it holds that i (p(p) S ir(u) U (I) it (u)), and let T2 E IN be defined follows:
TN - max { 10K*, inf nEN:
64Ko² (og())
S Seu
Vn K2 -2K
Then, it holds that [u([T]] <eeK + +1K* + To), where (8( is given by
To( = inf [tf(te e N: 3e.8 - (t Tw) T (p)) g(t))
where g(t) 80o (og()k log (t) 320 D Kt3/2 lt3//
Theorem 2 provides a finite-confidence bound for S-TAS in multiple-answer problems. As one can notice, the result is similar in nature to what we presented for TAS in Theorem 1. In particular, the expression of (ō) is similar to that of TAS, and, for the same reasons outlined in Section 3, this allows us to recover the asymptotic optimality guarantees of Degenne & Koolen (2019) whenever The main difference between Theorem and Theorem 2 is the presence of an additional problem-dependent constant TT,T*((4) -1 within the expression of To( As our proof will reveal, Th is the time that is needed by S-TAS (under the good event) to distinguish (p) U (I \ i (p)) from i (Jn) \ ii (M)) In other words, from that point on, under &,, all the candidate models jı' within the confidence region C, satisfy if (14) S is (1) U (I \ i" ((())) for all s 2 Vl. Indeed, whenever I > T2 it will be possible to link the stopping rule to T (1) (with some sub-linear terms) as we did for TAS. 15
5 - 0.
Finally, we comment on the nature of Tne In particular, the existence of C/. > 0 is guaranteed by the upper hemicontinuity of the set-valued function i (1)). Our claim holds for any 'u that satisfies Vy' : 1111-- 111l S Cy = iF (1²) ) S iz (14) U (I \ i" (u)), and, consequently, the tightest bound obtained for the largest possible Eμc- To conclude, we observe that the definition of e₁, is intrinsic to the definition of the task at hand, i.e., (w)). Once the task is fixed, it might be possible to obtain more explicit characterization of this quantity. Consider, for instance, the relevant case of an e- best arm identification problem. Here, it holds that (p( argmax P4 (see, e.g., Garivier & Kaufmann, 2021; Jourdan et al., 2023). Let A = min;gir(u) M. 14 where μe, is the value of any optimal arm. Then, whenever 6μ < Ap. we have that (x(2)) S (p)) Hence, Theorem 2 holds, for instance, with En- = 22
Now, we present a proof sketch of the result.
Proof Sketch As we did for TAS, the analysis is carried out under a sequence of good events {E which are exactly the ones that we considered when proving Theorem 1. As above, we will show that for T = 10K" + Tō(5) and & 2 T, we have that & S {TA S 1). As a consequence, [Ts] < 2eK + 10K* + (d). To do this, the main idea is lower bounding the condition used in the stopping rule with what S-TAS uses in the sampling rule. First, we state an intermediate result, which is consequence of (i) the forced exploration of S-TAS, (ii) the definition of the region C of candidate models, and (iii) the upper hemicontinuity of the set-valued function i Specifically, in Lemma 4 we prove that, Vt 2 T, on &,, it holds that:
(r(x)) S (F( U (I ( (H)) Vs 2 and μt E C.,
Indeed, by upper hemicontinuity, models μe' similar to ss have answers in i ( which are "close" to the ones in if (H)), and models in C, shrink toward μ due to the forced exploration of the algorithm.
We now analyze the amount of information that is gathered by S-TAS under the good event &,. Let I 2 10A"1 and let T = max max{[va KT,,T,Y Denote by E I, the answer that is selected from ir (1)) by the pre-specified total order over Z. Then, for 2 10K44 if S-TAS has not stopped at t, we have
As we did for TAS, in Appendix G provide an explicit upper bound on T8(8).
It is interesting to note that in our proof we are not using I. = ir (H). iee. that S-TAS has actually "sticked" to answer in ir (14).. Instead, it is sufficient that I, excludes answers in i" (1)) that are not within (
8

---

Published as a conference paper at ICLR 2026
that:
61,6 2
inf Σ (al)) - Ö(VE)
(8)
XE
8=1
kE[K]
2
inf XE
Σ wa(s)d(uus Ö(VI). -VV))
(9)
KE[K]
where the first step is due to concentration and C-Tracking, and the second one uses Equation (7). Indeed, for 2 T. either i, (and in this case the claim is trivial), or i, & 1. In this second case, from Equation (7) we have that is & i* (1)) and, therefore, j E -lg- Now, by concentration arguments (i.e., d(v (8), -) d(wx, 1)), and using the definition of (s)) we have that:
Σ inf Σ ==
wr(+)d(uus Ax) 2
Σ inf
Σ kE(K]
- -O(V)
AE the
XE ==
kE(K]
max inf
Σ kE(K]
wxd(fi((), Ac) -
wEAK AE
The next step is crucial for relating the amount of gathered information to T (p) Let pe E C. be such that is E is()'(s)). From concentration arguments and the definition of ju' us)s,, we have that:
Σ max inf
Σ kE(K
(s)(
Σ
max inf Σ WE UEA XE KE(K]
(x) - -(VE12
WE Ax AE T.
max max inf wEAR TET XE
Σ kE[K]
Ak) (V
inf XEm
Σ kE[K]
wid(( As) ō -
for any w" (H, m).. The first step follows by observing that d(x (s). can be upper-bounded by ds). and -s). = d(p'(s), since (s(s) E C. by definition. Then, the proof is simply concluded by noticing that:
Σ inf Σ 8=
wid(oL(s).Aa
R
inf Σ
wid(ue, Ax) -
AE kE[K]
XE
==7
kE|K]
=(T
where the first step follows from concentration arguments and the fact that pe (s) E C.. Rearrenging all the terms yields the desired result.
The proof idea As for TAS, the general idea is approximating with sub-linear terms the stopping rule with "'i=zinfxxe- EEE[K] wx (s)d(((()))) Aa), that is what S-TAS uses in its sampling rule. Now, there are two key differences with respect to Theorem 1. First, reach such objective need to consider sufficiently large timesteps, i.e., 2 T. The issue is that when is small, the S-TAS sampling rule has no control over the selected answers i, (apart from a generic total order over 2). This does not allow easily switch from - to -i. i.e., the step from Equation (8) to Equation (9). Second, once we have obtained E infxe-i, ΣxE(K) wa (s)d((pxss) A&). ). this does not allow us to directly introduce (H( and - as we did for TAS. An intermediate step is necessary. This requires studying the difference between d(ps (s), and d(rd (s), The reason is that i, is an answer that attains the argmax only when paired with a model pt' (s) E C, such that E i (p(((s)) (s)).

---

Published as a conference paper at ICLR 2026
S-TAS in single-answer problems Whenever (4) is single-valued, the dependency on Tμ can be removed as the step from Equation (8) and Equation (9) follows directly from the fact that [x)) 1 (as we did for TAS). Thus, one would obtain result identical to Theorem (i.e, the same bound up to constant multiplicative terms). Nonetheless, we actually note that the two proofs are still different, and the reason is the different sampling rules adopted by the two algorithms. Specifically, in S-TAS is is an answer in if (
(s)) for some p (s) E C. and ((s) E w (*(((s), ri.). On the other hand, TAS directly uses (s) w" (i((s) -is) for E ip(((s)))
On the behavior of S-TAS It is interesting to observe that our proof differs significantly from the one of asymptotic optimality by Degenne & Koolen (2019). Beyond the obvious distinction also note that the proof of Theorem 2 does not rely on
(i.e., our analysis is non-asymptotic), what N (t)/t converges to, nor does exploit the convexity of the set w(,, which instead were key components in the analysis of Degenne & Koolen (2019). Instead, only reason in terms of "information" " collected by S- S-TAS by analyzing values of functions of the form Eve(K] Wxd(-,)).
5 CONCLUSION
This work provided the first conieeconfiieece characterization of the performance of Track-and-Stur and Sticky Track-and-Stop. two general algorithms that able solve optimally a large spectrum of pure exploration settings. Overall, we solve two open problems in the literature. First, Theorem sheds light on the finite-confidence guarantees of TAS, thus providing theoretical support on why the algorithm usually enjoys good performance in practice. Secondly, Theorem 2 provides the first finite-confidence guarantees for the general multiple-answer setting. To conclude, we note that our results (Theorem and Theorem 2) have simple and natural proofs, and they both recover the asymptotic optimality whenever goes to O.
Several questions remain open. For instance. is it possible to improve the lnite-confidence analysis of Sticky Track-and-S Stop by removing the presence of the problem constant Tμ, We conjecture that this would require to slightly modify the sampling rule. Indeed, by selecting answers i, more strategically than using any total order over I might lead to stronger finite-confidence results and, eventually, more competitive performance. Furthermore, there remains a gap between lower and upper bounds in the finite-confidence regime (Degenne et al., 2019; Wang et al., 2021; Barrier et al., 2022: Jourdan & Degenne, 2023; Jourdan et al., 2023). Future work should focus on analyzing in greater details the finite-confidencs regime of general pure exploration problems. Here, one could draw inspiration from the works of Simchowitz al. (2017); Al Marjani et al. (2022); Poiani et al. (2024), where the authors shed some light on the challenges in developing lower bounds and algorithms that enjoy tight dependencies not only in log(1/o), but also in other parameters of the instance (e.g., K). Finally, Poiani et al. (2025) recently extended TAS and S-TAS to problems where the set of correct answers is possibly infinite. However, their algorithm only attains asymptotic optimality, and our analysis cannot be straightforwardly extended to this setting. Future works, should focus on closing this gap. Here, it relevant to mention the recent work of Osogami et al. (2025), where the authors proposed an algorithm that enjoys finite confidence guarantees in specific infinite answer problem, ie., that of estimating, up to an accuracy e, the value of the optimal arm.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
Work supported by the Cariplo CRYPTONOMEX grant and by an ERC grant (Project 101 165466 -L---STERR..
REPRODUCIBILITY STATEMENT
The nature of this work is theoretical. We precisely stated and discussed the assumptions that are required to derive our result in the main text (see Assumptions and 2), and we further discussed the assumptions in Appendix C. In the main text, provided proof sketches for both Theorem and Theorem 2, and we included complete proofs in Appendix D and Appendix F.
REFERENCES
Aymen AI Marjani, Tomas Kocak, and Aurélien Garivier. On the complexity of all e-best arms identification. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 317-332. Springer, 2022.
Jean-Pierre Aubin. Ser-Valued Analysis. Birkhäuser Boston, 1999.
Antoine Barrier. Contributions to a Theory of Pure Exploration in Sequential Statistics. PhD thesis, Ecole normale supérieure de lyon-ENS LYON, 2023.
Antoine Barrier, Aurélien Garivier, and Tomás Kocák. A non-asymptotic approach to best-arm identification for gaussian bandits. In International Conference Artificial Intelligence and Statistics, pp. 10078-10109. PMLR, 2022.
Olivier Cappé, Aurélien Garivier Odalric-Ambry Maillard, Rémi Munos, and Gilles Stoltz. Kullback-leible upper confidence bounds for optimal sequential allocation. The Annals of Statis- fics, pp. 1516-1541, 2013.
2013.
Rémy Degenne and Wouter M Koolen. Pure exploration with multiple correct answers. Advances in Neural Information Processing Systems, 32, 2019.
Rémy Degenne, Wouter Koolen, and Pierre Ménard. Non-asymptotic pure exploration by solving games. Advances in Neural Information Processing Systems, 32, 2019.
Rémy Degenne, Han Shao, and Wouter Koolen. Structure adaptive algorithms for stochastic bandits. In International Conference on Machine Learning, pp. 2443-2452, PMLR, 2020.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour, Pac bounds for multi-armed bandit and markov decision processes. In Computational Learning Theory: 15th Annual Conference on Compu- tational Learning Theory, COLT 2002 Sydney, Australia, July 8-10, 2002 Proceedings 15, pp- 255-270. Springer, 2002.
Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pp. 998-1027. PMLR, 2016.
Aurélien Garivier and Emilie Kaufmann. Non-asymptotic sequential tests for overlapping hy- potheses and application to near optimal arm identification in bandit models, 2021. URL https: //araaaavvvvv//vv//////ee. org/ wttg/aa//////oooooooooo///aaalb/ aws//90ss 03495.
Tianyuan Jin, Yu Yang, Jing Tang, Xiaokui Xiao, and Pan Xu. Optimal batched best arm identifica- tion. Advances in Neural Information Processing Systems, 37:134947-1149900 2024.
Mare Jourdan and Rémy Degenne. asmpasympio analysis of ucb-based top two algorithm. Advances in Neural Information Processing Systems, 36:68980-69020, 2023.

---

Published as a conference paper at ICLR 2026
Mare Jourdan, Mojmir Mutný, Johannes Kirschner, and Andreas Krause. Efficient pure exploration for combinatorial bandits with semi-bant bandit feedback. In Algorithmic Learning Theory, pp. 805- 849. PMLR, 2021.
Marc Jourdan, Rémy Degenne, Dorian Baudry, Rianne de Heide, and Emilie Kaufmann, Top two al- gorithms revisited. Advances in Neural Information Processing Systems, 15:26791-26800 2022.
Mare Jourdan, Rémy Degenne, and Emilie Kaufmann. An c-best-arm identification algorithm for fixed-confidence and beyond. Advances Neural Information Processing Systems, 36: 16578 16649, 2023.
Sandeep Juneja and Subhashini Krishnasamy. Sample complexity of partition identification using multi-armed bandits. In Conference on Learning Theory, pp. 1824-1852. PMLR, 2019.
Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. ICML, volume 12, pp. 655-662, 2012.
Kellen Kanarios, Qining Zhang, and Lei Ying. Cost aware best arm identification. arXiv preprint arXiv:2402.167/10 2024.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in armei bandits. In International conference on machine learning, pp. 1738-1246. PMLR, 2013.
Emilie Kaufmann and Wouter M Koolen. Mixture martingales revisited with applications to se- quential tests and confidence intervals. Journal of Machine Learning Research, 22(246):1-44, 2021.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identifi- cation in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
Tomáš Kocák and Aurélien Garivier. Best arm identification in spectral bandits. arXiv preprint arXiv:2005.0984 2020.
Tomás Kocák and Aurélien Garivier. Epsilon best arm identification in spectral bandits. In IJCAI, pp. 2636-2642. 2021.
Pierre Ménard. Gradient ascent for active exploration bandit problems. arXiv preprint 1wXi::105..0815. 2019.
Vrettos Moulos. Optimal best markovian arm identification with fixed confidence. Advances in Neural Information Processing Systems, 32, 2019.
Takayuki Osogami, Junya Honda, and Junpei Komiyama. Optimal estimation of the best mean in multi-armed bandits. The Thirty-ninth Annual Conference Neural Information Processing Systems, 2025.
Riccardo Poiani, Mare Jourdan, Emilie Kaufmann, and Rémy Degenne. Best-arm identification in unimodal bandits. arXiv preprint arXiv:2411.01898, 2024.
Riccardo Poiani, Martino Bernasconi, and Andrea Celli. Pure exploration with infinite answers. arXiv preprint arXiv:2505.224777 2025.
Alessio Russo, Yichen Song, and Aldo Pacchiano. Pure exploration with feedback graphs. arXiv preprint arXiv:2503.0782. 2025.
Max Simchowitz, Kevin Jamieson, and Benjamin Recht. sampling in the moderate-confidence regime. Conference on Learning Theory, pp. 1794-185 PMLR, 2017.
The simulator: Understanding adaptive
Po-An Wang, Ruo-Chun Tzeng, and Alexandre Proutiere. Fast pure exploration via frank-wolfe. Advances in Neural Information Processing Systems, 34:5810-5821, 2021.
12

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
1.1 Related Work
2 Background
3
Non-Asymptotic Analysis For Track-and-Stop
4
Non-Asymptotic Analysis For Sticky Track-and-Stop
5 Conclusion
10
Structured Bandits
14
Lower Bound
14
B.1 Single-Answer Problems
14
B.2 Multiple-Answer Problems
14
C On the Assumptions
15
Non-Asymptotic Bound for -rdsk-a
16
Simple Fix without Using Projections
20
F
Non-Asymptotic Bound For Sticky Track-and-Sto
20
G An Explicit Bound
26
G.1 An explicit bound for TAS
27
G.2 An explicit bound for S-TAS
29
H Auxiliary Tools
29
H.1 Technical Tools
29
H.2 Cumulative Tracking
29
H.3 Properties of Canonical Exponential Families
30
H.4 Concentration Results
30
H.5 5-Correctness
30
13

---

Published as a conference paper at ICLR 2026
A STRUCTURED BANDITS
For completeness, we now show that how to encode known structure such as Lipschitzianity and unimodality through M.
We first focus on the the best-arm identification problem in Lipshitz bandit with finite arms, i.e., the same setting studied in (Wang et al., 2021). This structure can be formalized as follows:
M {a4 [mminn Mmax]" Di s.t. p4 p4,, Vk, k', |p perl S
||ax ag. )
where 1 > 0 is a known constant, E I2 are the known feature vectors for the arms, and [pmin: y [maax] are the boundary parameters that we introduced in Assumption
Next, we consider the unimodal setting of Poiani et al. (2024). In this case, we have that:
M ff E [Mmin: |max]* 3i E
[ 14 14+1 2 ... 2 A p4 14-1 1 ... p1).
In other words, each bandit is characterized by an unknown index such that, the arms' mean will consistently decrease both after and before i.
This reasoning can also be extended other structures such as the dueling bandit formulation of Wang et al. (2021).
B LOWER BOUND
B. SINGLE-ANSWER PROBLEMS
In this section, we provide a formal statement of the lower bound for single-answer problems.
The following result follows the same arguments of Theorem in Garivier & Kaufmann (2016). Since we provide two different expressions for T' (p),, we also report a proof for completeness.
Proposition (Lower Bound for Single-Answer Problems Garivier Kaufmann (2016)), Suppose that li* (|+) = 1 for all E M. Let 5 < 0.15. For any μa E .M and any 8-correct algorithm, it holds that [T[ 2 T (H) log(L/(2.48)).
Proof. Let μ M and À (1). Then, from change of distribution arguments (i.e., Lemma in Kaufmann et al. (2016)) and the d-correctness of the algorithm, we have that:
Σ АE[K]
Ex(NN(Ta)dd((p Ax) log(1/(2.46)).
Applying this result for all A (K) and since u & cl( -i- (14), we have that:
log(1/(2.46)) v inf
Σ
E, (N An)
XE (p)
KE(K]
En((N((T))
=ENITT8 inf
d( d(p Ax)
Ae (1) kE[K]
[T([T
< [Ts
sup inf
wad(uu An)
weAx AE (
kE[A]
ETs sup max inf Σ
wad(uss Au),
wEAx TEZ XE
RE(K]
where, the last step follows from the fact that, for all # (*))). / -i, and, hence infxe-i EeeRK wid(ue, AR) = O. The proof then follows by the definition of T*)) together with the fact that supwedk infxe-((()) ΣnE[K] wed(ue, Xx) > 0 since μ & cl(ja).
B.2 MULTIPLE-ANSWER PROBLEMS
In this section, we formally state the lower bound for multiple answer problems.
14

---

Published as a conference paper at ICLR 2026
Proposition 2 (Lower Bound for Multiple-Ansynn Answer Problems Degenne & Koolen (2019)). Let I be a finite set and let μa E M. Then, it holds that:
E T6
lim inf 6
2 T (H),
(10)
log (1/8)
where T (pe) is given by:
(w)
sup max inf Σ kE(K)
wod(uee Aa)
(11)
WEAK TEL (10) AE
sup max inf wid((uk An).
(12)
WEAK HEI
kE[K]
Proof. The proof is exactly as in Theorem in Degenne & Koolen (2019). Specifically, in that paper, the result stated with the expression of T (1)) given in Equation (11). Equation (12) follows by noticing that, for all & i* (H)), then E -i, and, hence, inf
EkEjk wad(/4k Ax) = O. L
C ON THE ASSUMPTIONS
In this section, we further discuss our assumptions. As mentioned in the main text, Assumption is mild requirement that is only needed for concentration arguments. Thus, in the following, we focus on Assumption 2. As our proofs show, Assumption 2 only needed bound differences of infimum of optimization problems which involve KL divergences. Specifically, it is employed only to control differences in KL for functions of the form:
Σ Whl (d((sdd AnA) - d(1kk Aw))))
(13)
where X, is the minimizer of inf wad(ph, A&) for some -.. Therefore, our results holds for any family M of bandits for which it is possible to upper bound (in a Lipschitz fashion w.r.. μ1) functions of the form of Equation (13).
At this point, we remark on the following aspects.
Degenne et (2019) originally provided the aforementioned intuitive relaxation of Assumption and we invite the interested reader to check their Appendix F for further details.
Degenne et al. (2019) also shows that for Gaussian setting on unbounded domains, Equation (13) can actually be bounded in Lipschitz fashion. Hence, when dealing with Gaussian distributions, we can actually operate on unbounded domains (i.e., we can remove Assumption 2).
Finally, conclude by noticing that there exist works that have provided finite-confidence guaran- tees outside of Assumption 2. In particular:
Jourdan & Degenne (2023) derived finite-confidence results for an optimistic variant of the Top- Two Algorithm without using Assumption 2. Nonetheless, the authors are restricting their analysis to Gaussian distributions, and, as we discussed above, our analysis can easily be generalized to cover this scenario.
Barrier et al. (2022) also provides Unite-confidence analysis outside of Assumption Nonethe- less, their -on-tsympt bounds feature extra factor
1
exp( (-mmm
Wmin (11)z
where Wmin (14) minke[k] wi (p). We note that Wmin can be lower-bounded using the minimum gap for Gaussian distributions (see the comment below Theorem 5 in Barrier et al. (2022)), and thus it is not an issue for Gaussian best-arm identification problems, as it can become arbitrary large only for instances which for which the sample complexity lower bound well tends to Nonetheless, this is not the case for Bernoulli bandits. Indeed, consider best-arm identification problem in Bernouli bandit scenario over arms. Suppose that μ (x, 0.9). It is easy to see that W1 + as x + 0. Therefore, without Assumption 2, that finite-confidence guarantees can become vacuous outside of the Gaussian setting.
15

---

Published as a conference paper at ICLR 2026
Finally, Wang al. (2021) also provided finite-confidence guarantees outside of Assumption 2; nonetheless, additional assumptions are needed order to obtain the results. We refer the inter- ested reader to Assumption 1-3 in Wang et al. (2021) for the technical requirements. Here, we only note that their finite-coffidence analysis depend on assumptions that involve the gradients of the lower bound as function of w. Importantly, the main purpose of their assumptions is the same as ours, i.c., bounding functions of the form of (13). This is evident from Lemma 14 in Wang et al. (2021).
D NON-ASYMPTOTIC BOUND FOR TRACK-AND-STOP
In this section, we analyze the version of TAS that makes use of projection within the sampling rule. Specifically, w(s) E w (ū(t), where (t()) denotes the orthogonal projection of p(t) onto [Pmin: Mmaxx KK Before delving into the analysis, we note that it holds, due to the convexity of d(,,)) (see, e.g., Cappé al. (2013)), we have that:
(t), A) 2 At),, Ak E [K] E [Mmmnn Mmax] d(A. (x) 2 ((.. Ak [K],A [pmin Mmax]
(14)
(15)
Now, we start by upper bounding the expectation of Ta using an arbitrary good-event which implies stopping. The following result is standard in pure exploration works (see, e.g.. Degenne et al. (2019)) and the proof is reported for completeness.
Lemma 1 (Expectation Upper Bound). Consider a sequence of events {Ee)123 such that, there exists (6) and for 2 (ō) it holds that & S {To S t}. Then, it holds that:
Eg(Ts] S To(o) (ET)
Proof. It holds that:
400
400
En [T]
E PA(To > < 10K* To(d) +
Σ
Pa(To > 5 To()) +
Σ (E)).
t=3+To(0)
In our analysis, we will make use of the following good event:
& = vs [[VE].]]
Σ Nu(s)d((A(s), Pk) s 8K log(s) KE[K]
Indeed, it can be shown with probabilistic arguments that Σta PEf 2eK (Lemma 9). In the following, we compact the notation and we define f(t) == 8K log(t). The function f(t) can be understood as exploration function.
Next, the following lemma is the key result behind our analysis.
Lemma 2 (Learning the Equilibrium (TAS)). Let t 2 10K4. If TAS has not stopped at t, on & it holds that:
Be. t 1-vi-
(m) (m)- (T
Σ ha(1)
1=1
where:
DV200K5(1)L
h1(1) <
IK2In(K)V K2
h2(t)
DV20²f(1)
ha(t) <
+ K2 R2
t
((1202(11) ha(t) <
883322 +Kttln(t).
t
16

---

Published as a conference paper at ICLR 2026
Proof. Let define (t) follows.
1 t
h1(t) =
inf (H)
Σ
Na(t)d(puk Ar)
inf XE (pL) kE]K]
Σ (a)t)d((((())))))
kE[K]
If TAS has not stopped at E N, then we have that:
1 max inf
Σ
(o())d((a(()AN))
(Stopping Rule)
EEI AE
kE[K]
2
inf i XE- (11)
Σ Aa)
kE(K]
1 inf XE (1)
E Na(t)d(uu)Aa) htr)
(Definition of h1 (t))
kE(K]
Next, we upper bound (t) on the good event &
(t) -
inf dE i (p)
Σ Na(t)d(uA, AR)
inf Σ (2)t)a((a(())
DE (P) KE(A]
KEIRT
$ Σ (t( sup (d(Hk,)) A) - -d(A((t)A)) AEM
KE[K]
Σ
(1(() sup (Upe +NlAK ix((1) AEM
(Lemma 8)
KE[K]
D
$ t
Σ
Na(t)luX - Ax((t)
(Assumption 2)
KE[K]
D
Σ (o(d)2222d(())))..m
(Assumption 1)
kE|K]
D
202 f(t)
Σ (o(t)
(On & Lemma 9)
t
(t)
KELK
F(1
(By concavity of v-)
We continue with a lower bound on & infxe (M) Ene(K] Nu(t)d(us, Au). Let (w) be the sequence of empirical oracle weights selected by TAS, ie., w(s) w (A(t)). Then, we have that:
inf (E)
Na(()d(usss))) Au)
inf Σ
wn (s)dd((u,, Au) - h2((),
(M-
kE[K] where (t) is given by:
kE[K] a=1
h2(() = xE (())
1 inf
Σ KE[R]
Σ wk (s) No(l) d(as Aa)
$ 1 KI(KKWW++
inf (E-L-(1)
Σ kE[K]
d(pu, Ax)
(Lemma 7)
LK IIK)
(Assumption 2)
Then, we lower bound definition:
inf infxe-v(1) ΣtEPK Eis Wk (x)dd)( )t)). To this end, we recall that, by
((s) argmax max inf WEAK iEI XE
Σ wnd(px(s), Xx).
kE(K]
17

---

Published as a conference paper at ICLR 2026
Let us denote by i, answer that attains the argmax when paired with (s)). Then, we have that:
inf Σ t (E-i"(M) kc[K]] s=1
wn(s)d(14n:
Ax)
2 t
inf XE (1)
Σ kc(K]
we (s)d(((k An)
s=l
inf XE
Σ
wk(s)d((Hs) AE)
t
kEIK]
inl wn(+)d((ux: An)
s2vl
kE[K]
Σ s2vt
inf XE
Σ kE[K]
(K())d((n(s)),)) Ax) - ht)(),
t
where the second inequality follows from the fact that (i) if is (H) then the claim
is trivial, and (ii) if is * i (H), then, / E -i (since (1) is single-valued) and inf xe- ERE(K] wx(s)d(uue Ax) O. Finally, the last step follows from the definition of hs(t),
that
ha(1) = Σ
inf XE =2
Σ wn(s)d((((s))))) Av) 7 Σ inf Σ AE $ZVE
wr (r(s)d(us, Ax)
kc(K]
RE(K]
$ Σ
wx((s sup (d(fae)), Ax) dluks Ax))
XEM
#2 12vike([)
()((s) sup (ppu(s) (A)) mml AEM
(Lemma 8)
#2 KE[K]
Σ
Σ
(A))) ML
(Assumption 2 and ju(s) [pmins Mmax
<2vikE[A]
D
Σ
Σ
(Assumption 1)
<2]kk[[]]
D
Σ
Σ
(Equation (14))
$2 KEEK]]
D D22022(() f(t)
Σ Σ wa(s) Nx(s)
(Lemma 9)
t
20 f(L)
KIn(K) + + K2 V2+
(Lemma 7)
We now have analyze inzriin EkEjK we (s))(((s(s) (s), 2a). Specifically, we have that:
Σ inf Σ
wn(s)d(fa(s),
1
Σ sup max inf Σ (s())d((u((s) Ax)
XE the
WEAK JE(M] AE RE(A)
2V
kE[K]
s2v8
1 Σ inf (E)
Σ (s)( A6)
t
s2Vl
KE|K]
1
inf XE-I' (H)
Σ
wid(pk h1(t)
t
s2vi
kE[K]
t -- Vt 1 T -1 -ha(())
(Def. of T (u)
18

---

Published as a conference paper at ICLR 2026
where the first step follows from the definition of the sampling rule of TAS, in the second one have chosen any w E w" (Ht), and the third one by definition ht(t), that is:
(t) Σ inf
Σ RE[K]
wid(js A1))
Σ =2vB
inf Σ ke[R]
wEd((ix(s); Ax)
(p)
de (M))
=2v1
Now, we conclude the proof by giving an upper bound on ha(().
1 ha(t) - 7
Σ
wh sup (d(pes Aa) d(āix(s), (x))
AEM
#2
Σ
E
w sup (Unr - MAn DAL ixx(s) XEM
(Lemma 8)
1
s2vikEK
D
Σ
whluE (s((s)
(Assumption 2)
VEEK
D
82V7
D Σ
max kE(K]
(202d((n(($),,..
(Assumption 1)
$2Vi
D 202 S(L)
max kE[K]
(Lemma 9)
(x)+)
82v8
D D0220210
(Lemma 7 and I 10K*)
V8 + K2 -K
$2vl
202202 [(L)
(Concavity of V: and f 2 10K
V K2 2K
22VE
DV 20 f(t)
/883/2 + 8KtIn(t)
(Integral test and algebraic manipulations)
which concludes the proof.
Proof of Theorem I. Let t 2 10K'4 Then, for t > 10K + (8). by Lemma 2, have that & (To S t}. Lemma and Lemma 9, then conclude the proof. To this end, it is sufficient to note that T (H) Ein h(t)t + +++151 g(t)." Indeed, using t > 10a and simple algebraic arguments,
have that:
the (1) S 4o 4o Ktlog(t) < 4o Do. log( ( (1)
tha(t) log()) < DLK log logK)og(KK) 2t log
thy(t) < 4o log" (t) [K log K + 4v K2 K2 S 40DLy log (tg (t) (10K² log(K) vt))
tha(t) 16a /V (og DL log
log K) / (t).
Combining these inequalities, obtain:
(t) < 62n log(K) (t) + D Kt3/2 log(t).
16ehe requirement of 2 10K* is essentially needed to guarantee that the denominators those steps are always positive.
IIn the relevant regime where D, J, T (n)
19

---

Published as a conference paper at ICLR 2026
Thus, since from Lemma 2 we know that, for t such that:
T (M) Vl + Σ (h+(1) 1
implies stopping on the good event, we also have that, TAS guaranteed to stop whenever:
T" (H) + T (p)g(()) st. t.
Rearranging the terms give the desired expression of To(o).
E A SIMPLE FIX WITHOUT USING PROJECTIONS
In this section, we discuss what happens when TAS is not using projections the sampling rule.
The key idea is that there exists time TM such that, for subsequent steps then the empirical mean always lies within the interval [uminn [max] Before that, we make a remark on Assumption 2.
Specifically. fix any μ .M and let Fg min Mmmin [0g Mmax | and F = min Fk- As we discussed in Section 3, F > 0 holds to the fact that θ is an open interval and [Mmin Mmax] is closed and contained O
The following lemma shows the existence of such TM-
Lemma (Empirical Means Lies a Good Region). Under Assumption and Assumption 2, there exists time TM N such that, for all 2 TM. on Es, it holds that ju(s) E [Maiinn Mmaxx for all 2 Vt. Specifically,
64K log(n)
S sFl]
TM max 10K inf n nEN:
VVn+ K2 2K
Proof. Let I be such that, for a T. V 2K, i.e. T 2 10K Then, let t 2 T. Let F& = min(lax Uminl: | - Pmaxl] } and F = minkelK] Pr. Then, we have that if [(((t) wlloo I F, holds that (a())= E [mmmnn |max]. As discussed above, from Assumption 2, F > 0.
Now, on E,, for any s 2 Vt, we have that:
1 (xs))l s
max
(f (s),
(Assumption 1)
kE[K]
f0²
max kE[K]
(Lemma 9)
Nx(s)
20 f())
(Lemma 7)
+ K2 2K
4a 4021(1)
(s M V and t > T)
VL+ K2 -K
FF F}}
Then, letting TM max T. T, inf mEN:
f02
concludes the proof.
VV
Then, one can exploit Lemma to obtain result that is analogous one of Theorem just adding TM to the finite-confidence upper bound on Em[rs]. Indeed, Lemma 2 holds as-is by analyzing any t such that > TM.
F NON-ASYMPTOTE BOUND FOR STICKY TRACK-AND-STE
In this section, derive finite-confidence bounds for Sticky Track-and-Sten We start with the following result, which shows the existence finite time after which (under the good event) the answer chosen by S-TAS follows within "good set",, Le. ir (u) U (I (1)).
20

---

Published as a conference paper at ICLR 2026
Lemma 4 (Good Answers the Good Event). Let T4 be defined as follows
64Ko² OAKo2Log(1) VVn+ K2 2K
= max 10K inf n MEN.
S cH {
where c O is a problem dependent constant. Then, for all 2 T, on Et, it holds that is iF(M) (p)) all 2 vt.
Proof. We recall that μ = (f( is upper hemicontinuous (Theorem 4 in Degenne & Koolen (2019)). This implies that there exists en such that, for all μ' || 1'o I Eu. it holds that ir(x') (r( U (I \ (u)).
Now, consider T defined as follows:
7= = inf TENN Vn+ K2 2K > 0 o).
that is 7 10K*, Then, for all t and all 2 Vt, it holds that v + K2 - -2K > Consider 2 T, and let introduce, for all μe, μ³ M, ch(,,, infXER* [de(k)(d(Mess Mb)+ d(Ak,H4)) Now, on & and for s 2 vt, we have that:
Nu(s)d((u((s). S 8K log(s).
[K]
Furthermore, by definition, for all p' E C.. we also have that:
Σ
Ne(s)d((((()) s 8K log(s).
kE[K]
As consequence, by applying Lemma 7, it holds that:
ch(p, (Vs+ K2 (3 2k) s Σ
Ns(s) (d(px(s) + d(pu(s), S 16K log(s).
KE
Fort 2 T. and using the definition of ch, this leads to:
1
16K loglo
S ch(
802
s K 2K
which leads to:
32Ko2log(s
|| - 1'llo0 S
on E. 2 Vt, p¹ E C..
Vs+K2 -2K"
Thus, for 2 max (T. (T.int inf n E,,,
64Ko² log(n)
S &u } it holds that:
VVR+K=-2K
|| 1'1lo S cu on E, Vs Vt,p' C..
Now, since is E I, = Up iF(n') and || 1|p-~b' ooo S Ex for all μí' E C., it follows (by definition of ex) that, on E,, for 2 Vt,i, ir(u) U (I (*))), thus concluding the proof.
Next, the following result is the key lemma that provides lower bound, under the good event E,, on the information gathered by S-TAS.
18 The lower bound on ch(,)) )) follows from using the uub-gaussianity of the arms to lower bound the diver- gences d with the difference in and solving the resulting inf problem over R
21

---

Published as a conference paper at ICLR 2026
Lemma 5 (Learning the Equilibrium (S- (S-TAS)). Ler t 2 10K* and let T as in Lemma 4. Define T max [VE]. Then, for S-TAS, on &t, holds that:
Brd -- T
T (1)
Σ h()
where
h1(1)= - D Dv202K1 f(t)t
LK (K> K2
h2(t) -
ha(t) DV Dv200((1))
KIn(K) K
D DV222f(11)
hz(t)= <
86/2-8Ktl1(
2D 22022221 /202((t) f(t)
hs(t)= - 1
813/2 8Ktln(t).
Proof. Let ta (1) be defined as follows:
h (t) max inf Σ
No(t)d(un,As)
- max inf TEz kE[K]
Σ Aa)
FE KE[A]
If Sticky Track-and-Stop has not stopped at / E N, then, it holds that:
Br,6
inf AETi kE[K]
Σ (a)t)d(Aa()))))) Ax)
(Stopping Rule)
max inf REL XE kE[K]
Σ
(v) (1)
(Definition of h (1))
Next, we upper bound h2 under the good event Eμ-
ht(t)
Σ
(t(() sup (d(mu, A1) - d(fiatt, Ax))
t
RE(K]
AEM
Σ
(t) sup (d(pu, d(Au(t), Ax))
KE[K]
XEM
Σ
(4(1) sup (Uns Pb PNO (4( XEM
(Lemma 8)
KE(K]
Σ
Nu(t)lu (xx(t))
(Assumption 2)
KE[K]
D
Σ
No(t) (o
(Assumption 1)
&E[K]
202 f(t)
Σ Na(t)
(Lemma 9)
N&(t)
KE[K]
D D-2o0Kf(1)t
(Concavity of V-)
22

---

Published as a conference paper at ICLR 2026
Next, we continue by analyzing max infxe-i keeK (t(t)d((x(t)) At). Let {w(s)) be the sequence empirical oracle weights computed by Sticky Track-and-Stop To this end, let (t) be defined as follows:
[un(s) Na(t))
h2(t) = max inf VEI Xe
Σ
d(px, An).
kE[K] 1==1
Then, by definition of (t),,, we have that:
inf
E
max inf Σ Σ (x(()d(pa(()A)))
(x(s)d(uu 2x) h2((t)
AE-i kE[K]
XE-i kE[K]
Next, we upper bound h2))).
h2(t)= S 1 max inf
E KI(()Vt+ x2d(uuxAH))
(Lemma 7)
t WE XE-i
kE[K]
LK3 LK*
(Assumption 2)
Next, we focus on } maxxe inf xe- Ei=1 Exe[K] (x(s)d(us, Ax). Let E I be such that, given the subset of answers (p), then, the pre-specified total order over I selects t. Furthermore, let Tμ be in Lemma and let T max (Tu,: [v]]] Then, it holds that:
inf Σ wn(s)d((k,Aa) kE[K
inf Σ wa(s)d((Ri))) As) kE|K]
inf kE[K]
wx(s)d(uss>d Xx)
inf wk (s) X
where in the last step, we have used the fact that, (i) if E ip()), then i, on the good event E, and (ii) if & iF(H), then i, & (H) due to the definition of T. Then, in this case, we have that μ E mi, and infxe a, wx(s)d((u AR) Next, we have that:
inf Σ wx(())d(H) XE-L
Σ inf Σ (M) hs((),
XE
kE[K]
kE[K]
where hy (t) is given by:
h2(t) Σ inf
Σ (s) Σ inf AE-i,
Σ (x(s)d(Hk,
Ne E-i T
RE(K]
==
RE(K)
Inddeed in that case, E Cs, and, consequently, tr(p) E I,, Since the algorithm selects answers according total order, cannot select any answer in ( which
23

---

Published as a conference paper at ICLR 2026
Now, we have that:
1 hz(t) - Σ
(s(ss) sup (d((a((), Ax) - -(px: Ax)) XEM
== kE]K]
D
we(s))Ae(s) - Mal
(Lemma 8, Assumption 2, def. of (s))
== k
Σ
w (0)
(Assumption 1)
== 7 KE(K)
D 12220 f(t)
Σ E wH(S) Nu(s)
(Lemma 9)
s=
D 20220
(KIn(K) + + K2 K2 VL+K3)
(Lemma 7)
Now, continue by analyzing
Σ inf Σ (s) An). T
t AE
kE|K]
Specifically, by definition i, and ((s,, we have that:
inf XE kE[K]
Σ (x(s)d((e())) Ax)
Σ
max inf Σ wed((ie(s) Ax)
WEAK x XE
kE[K]
max inf Σ wEAR AE KE[K]
(n)( Ax) hh)
where (s)) E M is such that i, E i and ha(() is given by:
h4(t)
Σ
max inf
Σ
wn)(H(((s),
1 Σ
max inf Σ wx)((u(()))1))
wEAR de
wEAK XE d, kE(K]
==
kE[K]
==T
24

---

Published as a conference paper at ICLR 2026
Now, upper bound (t))).
1 ha(t)= - -
max WEAn
inf XEmis
Σ kE[K]
inf
Σ
(e)
1
AE-i
==7
kE(K]
Σ kE[K]
wk sup (d(()(()) Aa) - dd) (x))))
max WEAx
AEM
max WEAK
Σ kE[K]
we sup (V)(()) - (x,))1((6)) - (x)
(Lemma 8)
DEM
max WEAN kE[K]
E
walph(() [sx(s)
(Assumption 2)
max WEAK ==8
Σ
wKV 20² 14
(Assumption 1)
kE(K]
DV 20 f(t)
Σ
max
Σ
why Nx(s)
(A((s) E C.)
WEAK
s=f
kE[K]
DV/20² f(t)
(Lemma 7)
Vs+ + K2 2K
DV 202 f(t) f(t)
(Concavity of v-)
Vs+ K - 2K
D 20220ff0 f(t)
883/2 + 8KtIn(I)
(Integral test and algebraic manipulations)
Next, it remains to analyze +.' wax infxe-i, ExE[K] (x)( Let w w" (1s, -)). Then, we have that:
max inf Σ WE WE XE
wrd(ch(s) (s),
max max inf Σ (nd(sh((s), Ax) ET WEAR AE KE(K]
kc(K]
inf Σ wEd(H((s), XC-1
t
kE[K]
inf Σ t= AE
wid(ues (15()
kE[K]
t t- T
t T -11)-1--s((0 kss(),
25

---

Published as a conference paper at ICLR 2026
where the first step follows from the fact that is E (x(('(()) and the last third one from the definition of (t), that is:
(t) =
inf XE-
Σ KE(K]
wtd(ks,
1
Σ
inf AE-I KE(K]
Σ
(Ed(((((s)Aa)
w sup (d(ps: Ax) - d(((((s), Ax))
= kE[K]
NEM
Σ [K]
w sup (Umz - Mac - -
(Lemma 8)
XEM
WE - (1)
(Assumption 2)
K
μ - μ (s)
s=1
D
μ xx + +1(((s) ps)
==T
2Dv 20²1(1) J(L)
1
max kE(K]
(Lemma 9, Assumption 1, ())) C.)
t
/ N (s)
2D 2Dv20' 200 f(t)
1
(Lemma 7)
t
K2 2K
2D 2Dv260 (202
1
(Concavity of v-)
t
Vs KK- 2K
2D 2
813/2 8K(ln(1),
(Integral test and algebraic manipulations)
t.
which concludes the proof.
We are now ready to prove Theorem 2.
Proof of Theorem 2. Let t 2 K2. Then, for t Z 10K + (8))). by Lemma 5, we have & S (Ta S t). Lemma 1 and Lemma then conclude the proof. To this end, it is sufficient to note that T* (*H)) Σ h(t)++ v 1 S gt).." 20 Here, we followed the same algebraic steps that we presented for the proof of Theorem 1.
G AN EXPLICIT BOUND
One concern with the implicit definition of (6) in Theorems and is whether they yield practi- cally useful rates. In this appendix. we demonstrate that they do. By carefully bounding To()), we show that can be upper- bounded by clean and explicit expression of the form
(T* (H)) log(1/5) T (n) log log(1/8)).
These bounds are nearly tight: they match the asymptotic lower bound up to polylogarithmic factors and additive moblem--ependen constants. Furthermore, they are also useful in understanding the theoretical guarantees of the algorithms in the regime where T*(H)) - +oc (Le, a BAI problem,
In the relevant regime where D, o, T (n)
26

---

Published as a conference paper at ICLR 2026
these the hard instances where the mean of the second best arm approaches the one of the optimal arm).
This section is structured follows. First, in Appendix G.1 we present the result of TAS, then in Appendix G.2 we present the result for S-TAS.
G. AN EXPLICIT BOUND FOR TAS
For TAS, we show the following upper-bound on To()).
Proposition 3. Consider any th E (0,112)), 72 E (0, 1/4) and let (m)) and A2(12) be defined as follows:
(n)) = 66o 66o log log.DLK>og((K)TTM
A2(12) = 16 (GoDyKT" (M)
m
1/2
Furthermore, consider any o, E (0, 1) such that a + < and ler An a) and Az(n, 7) be defined as follows:
0.70--12
a)) = Ai(n)) (0.5 (0.5+ m))i(m))
033-1
+ ( m2)
0.25
A2(12.7) = A2(12)
?
Then, holds that:
(o())= T (M) (og) (1/0) (K)) log (oolloggg/))))) +1 an) + A2(12,7)
(16)
a -
Before proving the proposition, we comment on the result.
Proposition 3 provides an upper bound on (6) that holds for all 7), 72, a, > 0 such that 1) < 1/2. 122 < 1/4 and a+ < Hence, the tightest bound is achieved while minimizing Equation (16) over this domain. Some comments are in order.
Asymptotic Regime of 0 First, whenever and r that goes progressively to 0, yielding to To(8) se (H) 1). This shows how our result retrieves asymptotic optimality together with the dependency on minor order terms of 5.
one can pick any valid m. d2 together with
log(log(1// (1/))+++
1' we can easily evaluate the moderate regime of 6 in difficult instances where T (14) + ao (e.g., the case of best-arm identification where the gap between optimal arm and the second best one tends to 0). In this case, 0.75
Asymptotic Regime of T TH) + +00 Second, by picking =
one obtains a rate of the form O (A1(7)) U.5
0.5
+ Ag(2)) 1+
0.26
To further understand the
dependencies in relevant quantities, let first analyze the first term, that is:
inf A A1 (0
0.8-7
inf A1(1)..-a
nE
inf nE
"
A
0.5-
inf n
27

---

Published as a conference paper at ICLR 2026
where in the last step we introduced A1 = 66x DLK log(K)T (4). Let L1 log(4A1). Then, for sufficiently large (*))), we have that 4L1 E (0, 2) Hence, we obtain that:
A1 "
(4A, o
inf (0(
(4 -
2
= (1
log log(4AA (.A, I1)
22, -
444 -
-(4A)1)) exp
2h.1 - -1
E O (Af log((A)))
where, in the forth step, we have used that for T (μ)) sufficiently large 4L1 - 2 2 2L1 + 222o Following similar reasoning for the term with A2, have that:
inf A2(1) S (Ag log(
where A2 16 1GrDVKT
Hence, we have that:
0.78 0.25-12
inf mE00.1/2)mmE00.//8
A1(m) F.5-m + A2
2 max {A} log((1))2,
(oggAA))) log(A2)*)
For ('))) + 0o, A log( A2) the dominant term, thus providing the relevant dependencies in term of L, K and T (p).
We now conclude this section with a proof Proposition
Proof of Proposition 3. From Theorem 1, we have that:
To(o) = inf { t L N: Bus s (t Vt 1)T (1) -
where g(t) is given by:
g(t) 64o LoooDDKK"og(HAA log(K) (0) + 16D Kt3/2 log(t).
Using log(t)= < t together with the definition of Be,s i.e., Equation (25), it follows that (0) can be upper-bounded by:2!
inf (LEN Ao(5) - A. A2(1))(0.7377 $1),
(l) where, for brevity, have shortened (H) log(1/5) (m) log(log(1/6) + 1) with An(d). Note that since 771 < 1/2 and 7/2 < 1/4, the upper bound still well-defined and finite.
Next, by applying Young's inequality (Lemma 6), follows:22
further upper-bound this expression as
inf {I I Ao( + at + Ái(m, + + A S 1
Solving for yields the desired result.
Here, for simplicity, we incorporated the Vi - term and the K log log(t) component of 8r,5 within the
log(t)) term.
For the A₁ term, apply Lemma with 0.5+n 1.t.:....a..aa.............1----
7). Similarly, for the Ag term, 2.75+ -00
28

---

Published as a conference paper at ICLR 2026
G.2 AN EXPLICIT BOUND FOR S-TAS
Following the same reasoning that we presented above, it is possible to derive the following explicit expression of Tō) for S-TAS.
Proposition 4. Consider any 1n E (0.1/2), 72 E (0, 1/4) and let A1(m) and A2(12) be defined as follows:
A1(1))= DoDDLK2log(AA tlgg (t)
A2(12) = 32TDVKT(
M11
1/2
Furthermore, consider any a,7 (0, 1) such that a + < and let Å (n1, a) and A2(n, 7) be defined as follows:
0.5+-1
0.76--12
Ai a) = (i))) (0.5 + (m))((n)
A2 7) = A2(12) (0.75 + A2()1
0.20
a
7
Then, holds that:
To(8) S (N) + (T)) T T* ( (loggg/oo/////00 11 a) + )2(12)
1 a
(17)
Proof. The proof is identical to the one of Proposition 3. The main difference is only in the presence of T* ( that is due additional complexity that affects S-TAS.
Proposition 4 provides the explicit expression of (8) compared to its implicit version that is pre- sented in Theorem 2. Here, comments that are analogous to those that we presented for Proposition hold.
H AUXILIARY TOOLS
H.1 TECHNICAL TOOLS
Lemma 6 (Young's 's Inequality). Let 2 0, b 2 0 and consider integers p,g > 1 such that + 1/2
1. Furthermore, let 0. Then, it holds that:
ab S Ea
ba
qea/p
H.2 CUMULATIVE TRACKING
The following lemma summarizes the main properties of the C-Tracking procedure.
Lemma 7 (C-Tracking). Let (w(t)} be an arbitrary sequence of elements that belongs to K- dimensional simplex. Consider the C-Tracking applied on a sequence (w(t)), and let us denote by ()) the loo projection of (() onto Ag AK O (ea, 1] and e, (K² + () 11/2222 /2, For all E N, holds that:
No(t) 2 Vt K2 2K
(18)
- -Kln(K) K2 N2(t) Σ wK(s) < KVttk K2
(19)
wh(s) S Kln(K) + 4 K² V 1+ K2
Σ Σ 4= KE[K] (Na(t)
(20)
Proof. Equation (18) is due to Lemma 7 in Garivier Kaufmann (2016) and it is due to the forced exploration of the C-Tracking procedure (i.e., the projection onto A
29

---

Published as a conference paper at ICLR 2026
Now, from Theorem 6 in Degenne al. (2020), have that:
In(K) S (a(1) Σ (x(s) 1
(21)
However, from Lemma 7 in Garivier & Kaufmann (2016), we also have that:
max Σ (n(s) in (n) KVL+K2 RE(K]
(22)
Combining this result with Equation (21) leads to Equation (19). Finally, from Lemma Degenne et al. (2020), we have that:
(s)s) KE(K] (x((1)
S K In(K))+ +VKK
Combining these results with Equation (22) leads to Equation (20), thus concluding the proof.
H.3 PROPERTIES OF CANONICAL EXPONENTIAL FAMILIES
The following lemma reports standard properties one-dimensional canonical exponential families.
Lemma 8 (KL Difference in Exponentialy Families). For three distributions in canonical expo- nential family with means a, b, it holds that:
d(a, b) d(a, + d(c,b) (vb - ve)(c- a)
(23)
d(c, b) - d(a, S (ve - 1c) a)
(24)
where V() denotes the natural parameter of the distribution with mean (-).
Proof. For a proof, see, e.g., Lemma E.6 in Poiani al. (2024).
H.4 CONCENTRATION RESULTS
Lemma (Good Event). Consider {Et} such that
& = Vs E [[V],.]] Σ
Nu(s)d(Rn(s), pk) S 8K log(s) kE[K]
It holds that Etss Pp (Ef) < 2cK.
Proof. The statement is direct corollary of standard concentration arguments (see Lemma 6 in Degenne et al. (2019)).
H.5 5-CORRECTNESS
For simplicity of exposition, consider the following choice of the threshold 35,5:
Be,5 log (
+ K
Klog log
4 4loog
+1 )1) + 6K log(log(t) + 3).
+1++1
(25)
This threshold has been shown to yield 8-correct algorithms for Gaussian distributions Ménard (2019). At a cost of more involved expression, one can adopt the threshold proposed in Kaufmann & Koolen (2021) to analyze the stopping time in generic canonical exponential families.
We now prove for completeness that this choice of Bt,s combined with the stopping and recommen- dation rules leads to 8-correct algorithm for any sampling rule. Note that the above result holds for both the cases when it (I1) is both single and multiple-valuse
Lemma 10 (Correctness). For any sampling rule and p E M, it holds that Puliro & it (²)))) < 6.
30

---

Published as a conference paper at ICLR 2026
Proof.
With probabilistic arguments, we have that:
Pu(Oro $ (1)) I F2, 32 VEN,EEi(AA
inf XE
Σ Na(t)d((a(t))))) An) Peo KE[R]
S P
3t :EN: Σ mL) 2 Brb KE(K]
6,
where the first step follows from the definition of the stopping and recommendation rules, the second one from the fact that μa -ÿ for all j & i" (JL), and the third one from Proposition 1 in Ménard (2019).
31


Reviews:
[{"review_id": "Hc9M1OPmnR", "reviewer": "Reviewer_41vV", "summary": "This paper studies the non-asymptotic behavior of the Track and Stop algorithm, along with its variant, Sticky Track and Stop, which handles cases with multiple correct answers. This is a heavily theoretical paper. While Track and Stop has been around for several years and its empirical performance has been repeatedly validated showing it to be a strong and hard-to-beat baseline, its non-asymptotic analysis has been known to be challenging. This paper serves as a strong addition to the field, with its primary contribution being the non-asymptotic analysis for both the standard algorithm and its 'Sticky' variant.", "questions": "For the 'Sticky' variant, which addresses multiple correct answers, a comparison to the findings in \"Revisiting simple regret: Fast rates for returning a good arm\" (ICML 2023) would be insightful. That work, though in a fixed-budget setting, discovered that the identification speed can be significantly faster (potentially at a $1/M$ rate, where $M$ is the number of good arms). It would be interesting for the authors to discuss whether a similar, weaker, or analogous result is possible in the fixed-confidence setting. This is currently difficult to determine, as the complexity bounds for Sticky Track and Stop in this paper are not expressed in an explicit form that allows for an easy comparison.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written, with a clear structure, strong motivation, and a thorough discussion of related work. Overall, it is very easy to follow.\n2. The theoretical result is a welcome addition to this field, as a non-asymptotic analysis for Track and Stop has been long-missing.", "weaknesses": "I did not find any obvious weaknesses. However, due to time constraints, I was unable to review the proof details thoroughly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tvr0WAiZJe", "reviewer": "Reviewer_Lf7R", "summary": "This paper studies the non-asymptotic performance of the Track-and-Stop (TaS) and Sticky-Track-and-Stop (S-TaS) algorithms for best-arm identification. The authors derive upper bounds on the expected number of arm pulls required for both algorithms, using a carefully constructed sequence of events leading to stopping. The main contribution lies in providing finite-time performance guarantees for these two algorithms, complementing their known asymptotic optimality results.\n\nThe paper should be rejected due to two main issues:\n(1) insufficient contextualization with respect to closely related work, and\n(2) a lack of motivation for analyzing the vanilla versions of the algorithms rather than their improved variants.\n\n**Main argumentation**\nWhile the paper is technically sound and written with care, it does not clearly articulate what new insight is gained from analyzing the vanilla (S-)TaS algorithms, given that closely related works already provide non-asymptotic analyzes for more stable variants. Without a stronger justification of novelty or comparison with those results, the contribution remains poor.", "questions": "- Why is it valuable to analyze the vanilla Track-and-Stop, given that stabilized variants (Degenne et al., Barrier et al.) already offer non-asymptotic guarantees and often perform better empirically?\n- What are the “general multiple-answer problems” mentioned, and why can’t previous approaches be extended to handle them?\n- In what scenarios would one prefer using TaS or S-TaS over the existing improved variants?\n- Have you evaluated whether your non-asymptotic bounds align with the empirical stopping times observed in practice?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 1, "strengths": "- The paper is well written and clearly structured.\n- The assumptions are well motivated, and the mathematical arguments are rigorous and accompanied by clear intuition.\n- The work contributes to a deeper understanding of the stopping behavior of TaS-type algorithms in finite-sample regimes.", "weaknesses": "- *Relation to Degenne et al. (2019) and Barrier et al. (2022) is underdeveloped*\n\nBoth works introduce algorithmic variants of Track-and-Stop that address its early-phase instability and already provide non-asymptotic analyses.\nThe paper does not sufficiently motivate why analyzing the vanilla TaS (and S-TaS) provides new insight beyond those results.\n\nThe authors claim that the work of Degenne et al. (2019) requires to solve a “more challenging optimization problem,” but do not specify what distinguishes their setting or why this difference matters here.\n\nThe discussion of Barrier et al. (2022) is minimal. The paper should clarify in what sense its bounds differ from or improve upon theirs.\n\n- The results are said to complement the observed empirical good performance of TaS, yet no empirical evaluation is provided to assess the tightness or practical relevance of the derived bounds.\n\n- The introduction of S-TaS as a solution to \"general multiple-answer problems\" is insufficiently motivated. It is unclear what new problem instances this algorithm targets or why these instances are practically or theoretically important.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NAKTLG5QOo", "reviewer": "Reviewer_mo2G", "summary": "The paper revisits the popular pure-exploration algorithms, track-and-stop and sticky track-and-stop. These algorithms are known to have optimal performance in the asymptotic regime, i.e., when the error probability $\\delta \\to 0$. In this work, the authors analyze these classical algorithm in the finite time-regime and provide non-asymptotic bounds on expected stopping time of these algorithms as a function of $\\delta$ and $T^{\\star}(\\mu)$, the problem specific hardness.", "questions": "From the expression of $T_0(\\delta)$, it seems that $T^{\\star}(\\mu) \\log(1/\\delta)$ becomes the dominant term only for very small values of $\\delta = \\mathcal{O}(e^{-K})$. For values larger than this, the term $KT^{\\star}(\\mu) \\log(\\log(1/\\delta))$ is dominant. This implies that the optimality still holds for only sufficiently small $\\delta$. I agree that it common in non-asymptotic analyses to have a threshold only beyond which the results. However, $\\delta = \\mathcal{O}(e^{-K})$ this choice seems really small for any practical purpose. Ofcourse, this also not because of any leading constants as I have just denoted the order. Can the authors elaborate more on this?\n\nHow large would you typically expect $T_{\\mu}$ to be, or equivalently how small would $\\epsilon_{\\mu}$ be? Is there some structure on $\\mathcal{M}$ that would allow us to have more explicit bounds on $\\epsilon_{\\mu}$? This might help shed light on the sub-optimality of the current bounds.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides non-asymptotic bounds for these popular pure exploration algorithms, thereby addressing a gap in our understanding of the finite-time performance of these algorithms. \n\nThe analysis seems rigorous and is clearly explained. Overall, the paper is good and I like it.", "weaknesses": "I don't see any obvjous weakness in the paper, but I have questions as outlined in the next section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CRXe1xLBpe", "reviewer": "Reviewer_pnVY", "summary": "The paper presents a non-asymptotic analysis of the performance of the track-and-stop and sticky track-and-stop algorithms for pure exploration tasks under fixed confidence. The results are non-asymptotic, meaning they hold for confidence levels that do not necessarily converge to zero. The main results are given in Theorems 1 and 2, where the sample complexity upper bounds are stated in an implicit form. More explicit expressions are provided in Appendix G.", "questions": "•\tI find it hard to believe that no assumption on the mapping $i^\\star$ is required. Is the analysis valid for any function, even without regularity assumptions? Does the characteristic time $T^\\star(\\mu)$ become infinite when regularity is absent?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "•\tThe problem of pure exploration in moderate-confidence regimes is notoriously challenging and worth investigating—see “The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime” by Simchowitz et al., COLT 2017, for relevant discussions (this paper should likely be cited and discussed). Deriving guarantees in this regime is non-trivial, and this appears to be what the authors have successfully achieved here.\n•\tThe upper bounds, although implicit, seem to be more interpretable and user-friendly than those derived in existing works such as Degenne et al. (2019).", "weaknesses": "•\tThere is no comparison with existing results in moderate-confidence regimes (e.g., Degenne et al., 2019). This is an important drawback—the paper focuses on the track-and-stop algorithm, but it remains important to compare its performance with other approaches.\n•\tThere is no numerical experiments! How should we know whether the new upper bounds are reasonable?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)