Optimal Top-Two Method for Best Arm Identification and Fluid Analysis

Authors: agniv  bandyopadhyay
tifr  mumbai
sandeep  juneja
shubhada  agrawal
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:08:20

Abstract: Top-2 methods have become popular in solving the best arm identification (BAI) problem. The best arm, or the arm with the largest mean amongst finitely many, is identified through an algorithm that at any sequential step independently pulls the empirical best arm, with a fixed probability $\beta$, and pulls the best challenger arm otherwise. The probability of incorrect selection is guaranteed to lie below a specified $\delta>0$. Information theoretic lower bounds on sample complexity are well known for BAI problem and are matched asymptotically as $\delta\to 0$ by computationally demanding plug-in methods. The above top 2 algorithm for any $\beta\in(0, 1)$ has sample complexity within a constant of the lower bound. However, determining the optimal β that matches the lower bound has proven difficult. In this paper, we address this and propose an optimal top-2 type algorithm. We consider a function of allocations anchored at a threshold. If it exceeds the threshold then the algorithm samples the empirical best arm. Otherwise, it samples the challenger arm. We show that the proposed algorithm is optimal as $\delta\to 0$. Our analysis relies on identifying a limiting fluid dynamics of allocations that satisfy a series of ordinary differential equations pasted together and that describe the asymptotic path followed by our algorithm. We rely on the implicit function theorem to show existence and uniqueness of these fluid ode’s and to show that the proposed algorithm remains close to the ode solution.

Main paper: 
 introduction: 
 Stochastic best arm identification (BAI) problem has attracted a great deal of attention in the multi armed bandit community (see [21] , [10] , [3] for some early references in BAI). The basic problem involves a finite number of unknown probability distributions or arms that can be sampled from independently and the aim is to identify the arm with the largest mean. We consider a popular fixed confidence version of the problem where the sampling is sequential and the aim is to minimise sample complexity while guaranteeing that the probability of selecting the wrong arm is restricted to a pre-specified δ > 0. Applications are many including in healthcare and recommendation systems. [11] developed asymptotically (as δ → 0) tight lower bound on sample complexity of δ-correct algorithms for these BAI problems under the assumption that arms belong to a single parameter exponential family (SPEF). This assumption reduces a probability distribution to a single parameter and allows the analysis to better focus on certain aspects of the problem structure. We retain it for similar reasons. The sample complexity lower bounds involve solving an optimization problem that also identifies optimal proportion of allocations across arms. They also propose a track-and-stop algorithm that plugs in the empirical estimates of the distribution parameters in the lower bound and tracks the resulting approximations to optimal proportions of arms to sample. Although, this plug-in algorithm was shown to asymptotically match the lower bound, it involves repeatedly solving an optimization problem and is computationally demanding. [14] consider linear Gaussian bandits, [1] consider bandits with general distributions. Both the references propose track and stop algorithms where computation is sped up through batch processing.Substantial literature has come up on 'top-2' based, alternative faster and intuitively appealing algorithms to identify the best arm (see [25] , [26] for Bayesian approaches; [24] , [22] , [16] for frequentist approaches). The algorithms essentially proceed by identifying at each stage an empirical winner arm, that is, an arm with the largest mean, and its closest challenger. The empirical arm is pulled with probability β, and the challenger arm with the complimentary probability. In the frequentist setting, in [16] , the challenger arm is the one with the smallest 'index function'. Heuristically, this index function measures the likelihood of the challenger arm actually being the best one. The smaller the index function, more the likelihood. Further, with high probability, the index function increases with increased allocations to the corresponding arm. As is standard (see, e.g., [11] , [19] ), the algorithm is terminated when the generalized log-likelihood ratio (GLLR, given in Section 3) statistic exceeds a specified threshold. These algorithms are shown to be β optimal in the sense that they match the lower bound on sample complexity satisfied by algorithms that pull the best arm β fraction of times (see [15] for non-asymptotic analysis when β = 1/2). However, determining optimal β has been an open problem that has generated considerable activity and that we address in this paper.The key insight from index based top-2 algorithm is that once a sample is given to a challenger arm with the smallest index, its index function increases. The net effect is that as the algorithm progresses, the challenger arm indexes tend to come close to each other and move together. We build upon the above insight. Through the first order conditions associated with the lower bound problem, we identify a function g that equals zero under optimal allocation when the underlying arm distributions are known. We propose an anchored top-2 type algorithm where when g > 0, the empirical winner arm is pulled and that tends to decrease g. When g < 0, our algorithm pulls a challenger arm (arm with the smallest index function), and that typically increases g. We observe that the indexes of challenger arms that have been pulled, tend to rise up together until they catch up with arms with higher indexes. Once challenger arms associated with all the indexes have been pulled, call this the time to stability, then, since g is close to zero and indexes of all challenger arms are close together, it can be seen that the proportionate samples to the empirical winner and the remaining arms are close to the optimal proportions as per the lower bound. This continues until the GLLR statistic exceeds a threshold, roughly of order log(1/δ). The time to stability can be bounded from above by a random time with finite expectation independent of δ, while the time from stability till the GLLR statistic hits a threshold scales with log(1/δ) with a constant that matches the lower bound.Fluid model: Our other key contribution is to capture the above intuitive description through constructing an idealized fluid dynamics where g stays equal to zero once it touches zero and where the indexes that have been pulled, remain equal and rise together as the algorithm progresses. We further show that the resulting equations have an invertible Jacobian. Implicit function theorem (IFT) (see [20, Appendix A.6] for an introduction to IFT) then becomes an important tool in analyzing this idealized fluid system as it allows the arm allocations (N a : a ∈ K) to be unique functions of the overall allocation N . IFT further allows us to identify the ordinary differential equations satisfied by the derivatives N ′ a = dNa dN as the allocations N increase. The overall path till stability is constructed by pasting together the ode paths followed by arm allocations as the set of indexes that have already been pulled and are increasing together with N , meet another higher index. Once all the indexes have been pulled, our ode stabilizes so that the proportions N a /N thereafter remain constant and equal the optimal proportions as N increases. IFT further helps show that the proposed algorithm remains close to the fluid dynamics, and matches the lower bound for small δ. For completeness, in Appendix E.2, we also identify the ode paths under fluid dynamics for β top-2 algorithms. A great deal of technical analysis goes into showing that the algorithm, observed after sufficiently large amount of samples so that the sample means are close to the true means, is close to the fluid process and they both converge to the same limit.Other related literature: [22] also develop a top-2 type algorithm for a single parameter family of distributions. There algorithm decides between the empirical best and the challenger arm based on directional change in a certain index (related to the LB) when the underlying allocation proportions are perturbed. It is less directly connected to the first order conditions in the LB problem compared to our algorithm. Empirically, we observe that the our proposed algorithm has lower sample complexity, and is computationally substantially faster (Their algorithm can be sub-optimal. We discuss this in Appendix D.2). [7] consider an algorithm structurally similar to ours. They focus on the BAI fixed budget (FB) setting where the total number of samples are fixed and the aim is to allocate samples to minimise the probability of incorrect selection. Unlike the fixed confidence (FC) setting (the one that we consider), the FB setting requires optimizing the first argument of relative entropy functions that appear in the lower bound. In FC setting, the second argument is optimized ( [7] vary the first argument). Fundamentally, this is because FB is concerned with sample allocations that control the probability of the data conducting a large deviations to arrive at an incorrect conclusion, while FC is concerned with controlling sample allocations on high probability paths and gathering enough evidence to rule out the likelihood that the observed data is a result of large deviations. Furthermore, [7] prove weaker a.s. convergence results for associated indexes although not for allocations, and since they focus on FB settings, they do not provide sample complexity bounds or probabilistic false selection guarantees. Our analysis is more nuanced and structurally detailed, and we prove that the sample complexity of the proposed algorithm is asymptotically optimal. [28] study the best-k-arm identification problem in the BAI setting with fixed confidence and bring out the structural complexities that arise in lower bound analysis when k > 1. For k = 1, they develop an asymptotically optimal top-2 algorithm when arm distributions are restricted to be Gaussian. [27] consider related pure exploration problems using Frank-Wolfe algorithm. Their implementation involves solving a linear program at each iteration. [17] , [13] , [6] provide algorithms that provide finite δ sample complexity guarantees, however they are order optimal and do not match the constant in the lower bound.Finally, while fluid analysis is common in many settings including mean field analysis and games (e.g., [4] ), stochastic approximation (e.g., [5] ) and queuing theory (e.g., [8] ), to the best of our knowledge little or no work exists that arrives at it through IFT.Roadmap: In Section 2, we describe the problem and develop lower bound related analysis. The proposed algorithm and our main result, Theorem 3.1, demonstrating algorithm's efficacy are stated in Section 3 where we also develop the relevant IFT framework. Section 4 spells out the fluid dynamics associated with the algorithm. Key steps involved in proving Theorem 3.1 are outlined in Section 5. We describe the numerical experiments in Section 6. Detailed proof of all results are in the appendix.The proposed algorithm extends from SPEF to bounded random variables in a straightforward manner. While we do not provide supporting analysis (this limitation is due to space constraints), our numerical results in Appendix J suggest that our algorithm improves upon existing ones even in this setting. As is standard in the bandit literature, we also assume that samples from arm distributions are independent. Further, another limitation is the assumption of stationarity of the underlying distributions. This may be true when relatively short sampling horizons are involved. 
problem description and lower bound: 
 Distributional assumption: As mentioned earlier, we focus on arm distributions that belong to a known SPEF. Let S ⊂ R denote the open set of possible means of the SPEF under consideration. The details related to SPEF are reviewed in Appendix B.Fixed confidence BAI set-up: Consider an instance with K unknown probability distributions or arms, denoted by the mean vector µ = (µ 1 , . . . , µ K ), where each µ i ∈ S (we refer to each µ i interchangeably as a distribution as well as its mean in the SPEF context). As is standard in the BAI framework, we assume that there is a unique arm with the largest mean. Thus, without loss of generality µ 1 > max i≥2 µ i . One way to handle the case where 2 or more arms are tied for the largest mean is to look for an ϵ-best arm (an arm whose mean is within ϵ of the best arm). However, that is technically a significantly more demanding problem (see [12] ). Assuming uniqueness of the best arm and focusing on the best arm identification allows us to highlight the simple fluid dynamics underlying the proposed algorithm.Algorithm: Given an unknown bandit instance µ, we consider algorithms that sequentially generate samples -if A N denotes the arm pulled at sample N , and X N denotes the associated reward generated independently from distribution µ A N , then A N is chosen sequentially and adaptively as a function of generated (A n , X n : n = 1, 2, . . . , N -1). Further, an algorithm stops at some finite random stopping time τ and announces the best arm. δ-correct algorithm is an algorithm that, given a δ > 0, stops at time τ δ > 0 and outputs a best arm estimate k τ δ such that P(τ δ < ∞, k τ δ ̸ = 1) ≤ δ. That is, it identifies the arm with highest mean with probability at least 1 -δ. Our interest is in identifying a δ-correct algorithm that minimizes E[τ δ ]. To this end lower bounds on sample complexity of δ-correct algorithms are established using, e.g., the data processing inequality (see, e.g., [18] ). We see thatinf x {E[N 1 ]d(µ 1 , x) + E[N a ]d(µ a , x)} ≥ log(1/(2.4δ))with d(ν, x) denoting the Kullback-Leibler divergence between two distributions in S with means ν and x, and the expectation is under measure P µ associated with µ. The infimum above is solved at x ⋆ = µ1E[N1]+µaE [Na] E[N1]+E [Na] . With this, we obtain the lower bound E[τ δ ] ≥ T ⋆ (µ) log 1 2.4δ , where T ⋆ (µ) is the reciprocal of the optimal value of a max-min problem,EQUATIONwhere x 1,a = (ω 1 µ 1 + ω a µ a )/(ω 1 + ω a ) and Σ K denotes a simplex in K dimension.The popular plug-in track and stop algorithm involves solving the max-min problem (1) repeatedly for optimal weights with empirical distribution plugged in for µ above. The algorithm at each stage t, generates the next sample from an arm so that the proportion of arms sampled closely match the resulting optimal weights while ensuring an adequate, sub-linear exploration (e.g., each arm gets at least √ t samples at each stage t).Propositions 2.1 and 2.2 below are crucial for our analysis. Proposition 2.1 helps in constructing the fluid dynamics in Section 4. Proposition 2.2 provides a characterization of the unique optimal allocation ω ⋆ = (ω ⋆ a : a ∈ [K]) which motivates our algorithm's sampling strategy. Before stating the two propositions, we need some notation. Let B ⊆ [K]/{1}, andB = B ∪ {1}. Whenever B c ̸ = ∅, let N B c = (N a ≥ 0 : a ∈ B c) denote an allocation of samples to the arms in B c and we treat this as a constant in the following discussion and also in the statement of the two propositions. We define the quantity N 1,1 depending on N B c in the following way: (2) Furthermore, N B (•) and I B (•) are continuously differentiable w.r.t. N for N > N min . Proposition 2.2. Upon taking B = [K]/{1} and N = 1, N B (1), as defined in Proposition 2.1 is same as the unique allocation ω ⋆ solving the max-min problem in (1) . Further, I B (1) = T ⋆ (µ) -1 . Moreover, for every1) If B c = ∅ or a∈B c N a = 0, N 1,1 is zero. 2) Otherwise, N 1,N > 0, if B = [K]/{1}, the unique solution N B (N ) = (N a (N ) : a ∈ [K]) satisfies N a (N ) = N ω ⋆ a .Proposition 2.1 is proved by applying the Implicit function theorem (IFT). Proposition 2.2 is subsumed by [11, Theorem 5] , but we prove it using a different set of tools by applying the IFT. See Appendix D for the detailed arguments.For two vectors ν = (ν a ∈ S :a ∈ [K]) and N = (N a ∈ R ≥0 : a ∈ [K]) define the anchor function, g(ν, N ) = a∈[K]/{ ĵ} d(νmax,za)d(νa,za) -1, where ĵ = arg max a ν a , ν max = max a ν a , and z a = (N ĵ ν max + N a ν a )/(N ĵ + N a ) for all a ̸ = ĵ. Remark 2.1. It follows from Proposition 2.2 that the anchor function g(µ, ω) = 0 and all the indexes ω 1 d(µ 1 , x 1,a ) + ω a d(µ a , x 1,a ) equal to each other, uniquely identify the optimal proportion ω ⋆ solving the max-min problem (1) (see Appendix D.1 for an easier and more insightful derivation of these conditions). The algorithm proposed in Section 3 ensures that the empirical version of the anchor function g(•) quickly becomes close to zero and thereafter remains close to zero. Further, the indexes sequentially come close to each other and once they are close, they stay close through the remaining steps of the algorithm.3 Anchored Top-2 (AT2) Algorithm Notation: Some notation is needed to help state the proposed algorithm. For every arm a ∈ [K] and iteration N , N a (N ) denotes the number of times arm a has been drawn till iteration N , andN (N ) = ( N a (N ) : a ∈ [K]). Thus, N = a N a (N ). Let µ(N ) = ( µ a (N ) : a ∈ [K]) where µ a (N ) denotes the sample mean of arm a at time N , i.e., µ a (N ) =N t=1 I(A t = a) • X t / N a (N ),and îN = arg max a∈[K] µ a (N ), with an arbitrary tie breaking rule.For every pair of arms a, b, definex a,b (N ) = N a (N ) • µ a + N b (N ) • µ b N a (N ) + N b (N ) , and x a,b (N ) = N a (N ) • µ a (N ) + N b (N ) • µ b (N ) N a (N ) + N b (N ) . Let, I a,b (N ) = N a (N ) • d(µ a , x a,b (N )) + N b (N ) • d(µ b , x a,b (N )), and I a,b (N ) = N a (N ) • d ( µ a (N ), x a,b (N )) + N b (N ) • d ( µ b (N ), x a,b (N )).For a ̸ = îN , we call I îN ,a (N ), and I îN ,a (N ), respectively, actual index (or, simply index) and empirical index of arm a at iteration N , and denote them using I a (N ), and I a (N ). For notational simplicity, we hide the dependency on N whenever it doesn't cause confusion. Note that I a (N ) is a function of N îN (N ), N a (N ), µ îN (N ) and µ a (N ).Stopping Rule: As is typical in this literature, in our algorithm below, we follow a generalized log likelihood ratio (GLLR) to decide when to stop the algorithm. It is easy to check that min a∈[K]/{ î} I a (N ) denotes the GLLR, that is log of likelihood function (LF) evaluated at maximum likelihood estimator (MLE) divided by the LF evaluated at MLE of parameters restricted to alternate set with a different best arm compared to MLE (see [11, Section 3.2] for a detailed derivation). Define stopping time τ δ = inf{N | for all a ∈ [K]/{ î}, I a (N ) > β(N, δ)}, for an appropriate choice of threshold β(N, δ). After stopping at τ δ , the algorithm outputs îτ δ as the best arm. [19, Eq. 25, Section 5.1] argued that for instances in SPEF, upon choosing β(N, δ) ≈ log((K -1)/δ) + 6 log (log(N/2) + 1) + 8 log(1 + 2 log((K -1)/δ)), the GLLR based stopping rule is δ-correct for any sampling strategy including the one we propose. In our numerical experiments, we follow [11] and choose a smaller threshold, β(N, δ) = log((1 + log N )/δ).Description of the AT2 and Improved AT2 (IAT2) Algorithm: The AT2 algorithm takes in confidence parameter δ > 0 and exploration parameter α ∈ (0, 1) as inputs, and executes the following steps at iteration N :1. Let V N def. = {a ∈ [K] | N a (N -1) < N α } be the set of under-explored arms. 2. If V N ̸ = ∅, choose A N = arg min a∈[K] N a (N -1), and go to step 5.3. Else, if g( µ(N -1), N (N -1)) > 0, choose the empirically best arm i.e. A N = îN-1 , and go to step 5.Else, if g( µ(N -1), N (N -1)) ≤ 0, choose the challenger arm i.e.A N = arg min a∈[K]/{ îN-1 } I a (N -1) using some arbitrary tie breaking rule, and go to step 5. Inspired from the Improved Transportation Cost Balancing (ITCB) policy for selecting the challenger arm in [16] , Improved AT2 (IAT2) algorithm has the same input and follows the same strategy for exploration (step 1 and 2) and choosing the best arm (step 3) as AT2. IAT2 differs from AT2 only by its choice of the challenger arm in step 4, where IAT2 samples from the arm= max{T explo , T 0 }, where T explo < ∞ is a constant defined in Definition G.7 of Appendix G.4. After iteration T explo , the algorithm consecutively does exploration over a strech of atmost K iterations. Moreover, over a single such "epoch" of consecutive explorations, the algorithm explores every arm atmost once (follows from statement 1 and 3 of Proposition G.5). Note thatE µ [T 1 ] ≤ T explo + E µ [T 0 ] < ∞.3. T 2 is defined in Lemma G.11 as the iteration at which the anchor function g( µ(•), N (•)) crosses the value zero after the iteration max{M 1 , T 1 } (M 1 ≥ 1 is a constant independent of the sample paths and defined in the proof of Lemma G.11). By Lemma G.9, there exists a constant C 1 ≥ 1 independent of the sample paths, such that = max{M 2 , T 2 } + 2, where M 2 ≥ 1 is a constant chosen in the proof of Lemma G.12 and is independent of the sample paths. After iteration T 3 , whenever the algorithm picks an alternative arm a ∈ [K]/{1}, then for every other alternative arm b ∈ [K]/{1, a}, we have N b (N ) ≥ γ N a (N ), for some constant γ ∈ (0, 1) independent of the sample paths (see Lemma G.12). Note thatT 2 ≤ C 1 max{M 1 , T 1 }. As a result, E µ [T 2 ] ≤ C 1 (M 1 + E µ [T 1 ]) < ∞. After iteration T 2 ,E µ [T 3 ] ≤ M 2 + 2 + E µ [T 2 ] < ∞.5. T 4 = C 2 (T 3 + 1) for some constant C 2 ≥ 1 independent of the sample paths, defined in Lemma G.13. After iteration T 4 , all the arms a ∈[K] have N a (N ) = Θ(N ) (see Lemma G.13). Note that E µ [T 4 ] ≤ C 2 (E µ [T 3 ] + 1) < ∞.We show that, for every N ≥ T 6 , g(µ, N (N )) ≤ CN -3α/8 implies g(µ, N (N + 1)) ≤ C(N + 1) -3α/8 . By Lemma G.1, we have a constant C 1 > 0 independent of the sample path, such that,EQUATIONBy Lemma G.13, we have N a (N ) = Θ(N ) for every a ∈ [K] and N ≥ T 5 . As a result, by (15) , we have constants C 2 , C ′ 2 > 0 independent of the sample paths, such that: for all N ≥ T 5 , and Na ∈ N a (N -1), N a (N ) ,EQUATIONwhere N = ( Na : a ∈ [K]).We use the constants C 1 , C (N + 1) -(1+ 3α 8 ) < C 2 N -1 .By definition of T 6 , g( µ(•), N (•)) has opposite signs at iterations T 6 -1 and T 6 . Therefore,g( µ(T 6 ), N (T 6 )) ≤ g( µ(T 6 ), N (T 6 )) -g( µ(T 6 -1), N (T 6 -1)) ≤ g(µ, N (T 6 )) -g(µ, N (T 6 -1)) + C 1 T -3α/8 6 + C 1 (T 6 -1) -3α/8 (using (60)) ≤ g(µ, N (T 6 )) -g(µ, N (T 6 -1)) + 3C 1 T -3α/8 6(using the definition of M 41 ). .Using (60) and the above upper bound, we have,EQUATION(using (61))≤ (4C 1 + C ′ 2 )T -3α/8 6 = CT -3α/8 6. 
theoretical guarantees: 
 Proposition 3.1 below shows that the allocations made by AT2 and IAT2 algorithms converge to the optimal allocations ω ⋆ w.p. 1 in P µ . For every a ∈ [K] we define ω a (N ) = N a (N )/N , and use ω(N ) = ( ω a (N ) : a ∈ [K]) to denote the algorithm's proportion at iteration N . Proposition 3.1 (Convergence to optimal proportions). There exists a random time T stable and a constant C 1 > 0 depending on µ, α, and K, and independent of δ, such that, E µ [T stable ] < ∞, and for every N ≥ T stable and arm a ∈[K], | ω a (N ) -ω ⋆ a | ≤ C 1 N -3α 8 , and | µ a (N ) -µ a | ≤ ϵ(µ)N -3α 8 ,where ϵ(µ) is a positive constant depending only on µ and defined in Appendix B.Theorem 3.1 (Asymptotic optimality of AT2 and IAT2). Both AT2 and IAT2 are δ-correct over instances in S, and are asymptotically optimal, i.e., for both the algorithms, the corresponding stopping times satisfy, lim sup δ→0Eµ[τ δ ] log(1/δ) ≤ T ⋆ (µ), and lim sup δ→0 τ δ log(1/δ) ≤ T ⋆ (µ) a.s. in P µ . Moreover, we can find a constant C > 0 depending on the instance µ and α, such that,τ δ ≤ max{ T stable , T ⋆ (µ) • log(1/δ) + C (log(1/δ)) 1-3α/8 } a.s. in P µ .Proof idea of Theorem 3.1: We assume Proposition 3.1 and sketch the argument by which asymptotic optimality follows from it. For N ≥ T stable , and a∈ [K], from Proposition 3.1, N a (N ) ≈ ω ⋆ a N and µ a (N ) ≈ µ a . As a result, from Proposition 2.2, after T stable , I a (N ) ≈ N I [K]/{1} (1) = N T ⋆ (µ) -1 for every a ̸ = 1. Therefore, if min a̸ =1 I a (N ) crosses β(N, δ) at N = τ δ , since β(N, δ) = log(1/δ)+ O(log log(1/δ)+log log(N )), we have τ δ T ⋆ (µ) -1 ≈ δ→0 log(1/δ)+O(log log(1/δ)+log log(τ δ )), which gives lim sup δ→0 τ δ log(1/δ) ≤ T ⋆ (µ) a.s. in P µ . Detailed proof is in Appendix H.We outline the key steps of the proof of Proposition 3.1 for AT2 in Section 5, and the detailed proof is in Appendix G.2. Similar arguments hold for IAT2. Considerable technical effort goes in proving this proposition due to the noise in the empirical estimate µ(N ), resulting in noise in the anchor function and the empirical indexes. However, before presenting the proof sketch, in the next section, we first observe the algorithm's dynamics in the limiting fluid regime where this noise is zero. Several of the important proof steps for the algorithmic allocations rely on insights from the simpler fluid model. 
fluid dynamics: 
 Motivation: The fluid dynamics idealizes our algorithm's evolution through making assumptions at each iteration N that hold for the algorithm in the limit as the number of samples increase to infinity. Unlike the real setting with discrete samples, here we treat samples as a continuous object getting distributed between different arms as the sampling budget (also referred to as 'time') evolves. We denote the no. of samples allocated to an arm a ∈ [K] at some time N > 0 using N a (N ), and define the tupleN (N ) = (N a (N ) : a ∈ [K]). Note that a∈[K] N a (N ) = N . The rate N ′ a (N )at which samples get allocated to arm a at time N depends on a continuous version of the AT2 algorithm, which we refer to as the algorithm's fluid dynamics. We define the index of arm a ̸ = 1 at time N as,I a (N ) = N 1 (N ) • d(µ 1 , x 1,a (N )) + N a (N ) • d(µ a , x 1,a (N )), where x 1,a (N ) = N1(N )µ1+Na(N )µa N1(N )+Na(N ). Notice that I a (N ) defined in Section 3 is the index of arm a with respect to the algorithm's allocation N (N ), whereas in our current context, I a (N ) represents the index with respect to the fluid allocations N (N ).Description of the fluid dynamics: First we explain the fluid dynamics in words. We formally characterize the fluid allocation N (N ) via a system of ODEs in Theorem 4.1. Later in this section, we exploit the obtained ODEs to argue that, after starting the fluid dynamics from some time N 0 > 0, the allocations N (N ) reach the optimal proportions ω ⋆ = (ω ⋆ a : a ∈ [K]) by a timeatmost min a∈[K] ω ⋆ a -1 • N 0 . In other words, for N ≥ min a∈[K] ω ⋆ a -1 • N 0 , we have N a (N ) = ω ⋆ a • N for every arm a ∈ [K]irrespective of the initial allocation we had at time N 0 . For notational simplicity, we hide the dependency on N , whenever it doesn't cause any confusion. Recall the anchor function g(•) introduced in Section 2. We use g to denote g(µ, N (N )). For every subset A ⊆ [K]/{1}, we use A to denote A ∪ {1}.We start the fluid dynamics at time N 0 > 0 with some initial allocation N 0 = (N 0 a ≥ 0 : a ∈ [K]). We assume that the vector of true means µ is known. The fluid dynamics evolves according to the following steps at a given total allocation N ≥ N 0 : 1) If g > 0, then N 1 increases with N while other N a 's for a ̸ = 1 are held constant till g = 0 (g can be seen to be a monotonically decreasing function of N 1 ). With this g also increases, since g is a strictly increasing function of N a for every a ∈ B. The dynamics in this case are simple and described in Proposition E.1 of Appendix E. 4) Once, g = 0, and B = {2, . . . , K}, we show that each allocation increases linearly withN such that N ′ a = ω ⋆ a .The fluid ODEs: In Appendix E, we argue that if the fluid dynamics has g ̸ = 0 at time N 0 , then g becomes zero within a finite time by following step 1 or step 3 of the description. This is easy to observe when g > 0 at N 0 , because g is strictly decreasing in N 1 , and g → -1 as N 1 → ∞. Therefore, following step 1, g becomes 0 at some finite N . We now consider the situation where g = 0 at some N > N 0 . Setting B to the set of minimum index arms, the algorithm evolves by tracking the allocation N B (N ) = (N a (N ) : a ∈ B) defined through the system (2) in Proposition Let ∆ a = µ 1 -µ a , andh a (µ, N 1 , N a ) = f (µ, a, N ) N 2 1 ∆a (N1+Na) 2 .For notational simplicity, we denote h(µ, N 1 , N a ) by h a . Further, for each a, we denote d(µ 1 , x 1,a ) by d 1,a and d(µ a , x 1,a ) by d a,a . Recall that for given allocations (N a : a ∈ [K]), B denotes a set such that N 1 d 1,a + N a d a,a = I B (N ) for all a ∈ B, andEQUATIONTheorem 4.1 (Fluid ODEs). If at total allocation N ≥ N 0 , we have g = 0, and B is the set of minimum index arms, i.e., B = arg min a∈[K]/{1} I a (N ), then the following holds true:1. As N increases, and till I B (N ) increases to hit an index in B c ,N ′ 1 = N 1 h(B) (N 1 + a∈B N a )h(B) + d -1 B h(N ), andN ′ b = N b h(B) + d -1 b,b h(N ) (N 1 + a∈B N a )h(B) + d -1 B h(N ) , (3) for all b ∈ B. It follows that, I ′ B (N ) = I B (N )h(B)+h(N ) (N1+ a∈B Na)h(B)+d -1 B h(N ) . 2. Furthermore, for a ∈ B c , I ′ a (N ) = N ′ 1 d 1a = N1h(B)d1a (N1+ a∈B Na)h(B)+d -1 B h(N ) .3. There exists a β > 0, independent of N such thatI ′ B (N ) > β. In addition, for a ∈ B c , N ′ a = 0, I a (N ) ≤ N 0 a d(µ a , µ 1 ), thus the index is bounded from above. Thus, if B c ̸ = ∅, I B (N ) eventually catches up with another index in B c . In this way, the set B grows into {2, . . . , K}.Indexes once they meet must stay together: In Appendix F.1 we argue via contradiction that in our fluid dynamics, once a set of smallest indexes that are equal, increase and catch up with another index, their union then remains equal and increases together with N . This argument is important as it motivates the proof in our algorithm that after sufficient amount of samples, once a sub-optimal arm is pulled, its index stays close to indexes of the other arms that have been pulled.Bounding the time to reach optimal proportion: We define N ⋆ to be smallest time after N 0 at which the fluid dynamics has both B = {2, . . . , K} and g = 0. Let (N ⋆ a : a ∈ [K]) be the allocation at N ⋆ . We first argue that: there exists i ∈ [K] such that N ⋆ i = N 0 i . We have argued before that if g ̸ = 0 at N 0 , then g becomes zero by some finite time, which we call M . By definition M ≤ N ⋆ . Now if B ̸ = {2, . . . , K} at M or M = N 0 , then after time M the fluid dynamics evolve by the ODEs in (3) and N ⋆ is the time at which B becomes {2, . . . , K}, which is finite by statement 3 of Theorem 4.1. In this case i is the last element to be added to B. Otherwise if B = {2, . . . , K} at M and M > N 0 , the only way this can happen is g < 0 in [N 0 , M ). In this case, i = 1 and M = N ⋆ . Since g = 0 and B = {2, . . . , K} at time N ⋆ , Proposition 2.2 implies N ⋆ a = ω ⋆ a N ⋆ for all a. Combining our observations, we haveω ⋆ i N ⋆ = N ⋆ i = N 0 i ≤ N 0 . Hence N ⋆ ≤ N 0 ω ⋆ i ≤ (min a∈[K] ω ⋆ a ) -1 N 0 . Thus N ⋆ iswithin a constant times of N 0 . We bound T stable of Proposition 5.1 using a similar argument.Remark 4.1 (Incorporating the stopping rule into the fluid dynamics). At stopping time the idealized GLLR (which is the GLLR defined in Section 3 by replacing the estimated means with the true means) just exceeds log(1/δ). Since the idealized GLLR grows linearly with the allocated samples, the stopping time increases linearly with log(1/δ). Since the time for fluid dynamics to reach stability is independent of δ, for small δ, stability will be reached before the algorithm stops. Remark 4.2 (β-fluid dynamics). In Appendix E.2, we construct the fluid dynamics for the β-EB-TCB algorithm [16] using IFT. We prove that, for every β ∈ (0, 1), the β-fluid dynamics started at some time N 0 > 0 reach the β-optimal proportion (which is the solution to the max-min problem 1 with the added constraint ω 1 = β) by a time which is a constant times N 0 . 
sample x: 
 A N = arg min a∈[K]/{ îN-1 } (I a (N -1) + log N a (N -1)).Empirically, we see that typically IAT2 performs better than AT2 with respect to sample complexity. In the appendix, we provide pseudo-codes of AT2 and IAT2 in Algorithms 1 and 2, respectively.We now outline the proof steps for Proposition 3.1. To simplify our analysis, we analyze the AT2 algorithm after the random time T 0 defined as,T 0 = inf N ′ ≥ 1 ∀a ∈ [K] and N ≥ N ′ , | µ a (N ) -µ a | ≤ ϵ(µ) • N -3α/8 ,after which the estimates µ(N ) are converging to µ. Recall that α ∈ (0, 1) is the exploration parameter, and ϵ(µ) > 0 is a constant depending only on µ. By the definition of ϵ(µ) in Appendix B, we have µ a (N ) < µ 1 (N ) for all a ̸ = 1 and N ≥ T 0 . As a result, arm 1 becomes the empirically best arm after T 0 . In Appendix G.3, we use Chernoff's bound to prove that P µ (T 0 = n + 1) = exp(-Ω(n α/4 )), which implies E µ [T 0 ] < ∞. In the following discussion, all the results mentioned are true for both AT2 and IAT2 algorithms. Proposition 5.1 shows that the allocations made by the proposed algorithm converges to the first order condition satisfied by the optimal proportion ω ⋆ = (ω ⋆ a : a ∈ [K]) at a rate O(N -3α/8 ), where α is the exploration parameter. Proposition 5.1. There exists a random time T stable ≥ T 0 satisfying E µ [T stable ] < ∞ and a constant C 2 > 0 depending on µ, α and K, and independent of the sample paths, such that, forEQUATIONand maxEQUATIONBefore outlining the proof of Proposition 5.1, we explain how Proposition 3.1 follows from Proposition 5.1 just using the IFT.Proof idea of Proposition 3.1: If our algorithm follows optimal proportions at time N , i.e., N a (N ) = ω ⋆ a N for all a ∈ [K], RHS of (4) and ( 5) becomes zero by Proposition 2.2. Moreover, by Proposition 2.2 ω ⋆ uniquely satisfies the conditions: anchor function is zero and all alternative arms have equal index. ( 4) and (5) imply that, ω(N ) satisfies these conditions upto a perturbation of C 2 N -3α/8 after T stable . Using the IFT, we prove that the algorithm's allocation is a Lipschitz continuous function of the perturbation when it is sufficiently small. Hence, by choosing T stable large enough and using Lipschitzness, we get max a∈[K] | ω a (N ) -ω ⋆ a | = O(N -3α/8). Closeness of µ(•) to µ follows from the fact that T stable ≥ T 0 .Proof idea of Proposition 5.1: We separately outline the proofs of ( 4) and (5) in Proposition 5.1. In the following discussion, constants hidden in O(•), Ω(•) and Θ(•) notations are independent of the sample path after time T stable . To simplify our analysis, we choose T stable such that exploration stops after T stable , i.e., V N = ∅ for N ≥ T stable (see the discussion before Definition G.1 in Appendix G.1.1 for justification).Key ideas in the proof of (4): We prove (4) via induction. We prove the existence of a constant D > 0 such that at every N ≥ T stable , whenever the actual anchor value g(µ, N (N )) (we denote using g(N )) satisfies |g(N )| > DN -3α/8 , our algorithm pushes g(•) towards zero by Θ(1/N ) in the next iteration through steps 3 and 4. Whereas the interval [-C 2 N -3α/8 , C 2 N -3α/8 ] shrinks by O(N -(1+3α/8) ) from both ends. Since N -(1+3α/8) << N -1 , we choose the constant C 2 large enough such that g(•) stays in the said interval in iteration N + 1.Key ideas in the proof of (5): The following lemma forms a crucial part of the argument for proving closeness of the indexes in the non-fluid setting.Lemma 5.1. There exists a random time T good ∈ [T 0 , T stable ] such that the algorithm picks all the alternative arms in [K]/{1} atleast once between the iterations T good and T stable . Moreover, for N ≥ T good , if the algorithm picks some arm a ∈ [K]/{1} at iteration N , then it picks arm a again within a next O(N 1-3α/8 ) iterations.Proof of Lemma 5.1 (in Appendix G.1.2) is technically involved and requires proving several supplementary lemmas. Several of the key steps of this proof borrow insights from the fluid dynamics, and we outline them in Appendix F. Here we assume Lemma 5.1 and sketch the argument by which (5) follows from it for the AT2 algorithm. For any a, b ̸ = 1 and after any N ≥ T stable , I a (•) and I b (•) crosses each other before the algorithm picks both a, b atleast once. We can show that, for j = a, b and N ≥ T stable , I j (N ) and I j (N ) differ by O(N 1-3α/8 ). As a result, whenI a (•) crosses I b (•) at N + R, we have |I a (N + R) -I b (N + R)| = O((N + R) 1-3α/8 ) = O(N 1-3α/8 ) since R = O(N 1-3α/8). For j = a, b, the partial derivatives of I j (•) w.r.t. N 1 and N j are non-negative and bounded from above by max{d(µ 1 , µ j ), d(µ j , µ 1 )} = O(1). As a result,|I j (N + R) -I j (N )| = O(R) = O(N 1-3α/8 ) for j = a, b. Hence, |I a (N ) -I b (N )| ≤ |I a (N + R) -I b (N + R)| + j=a,b |I j (N + R) -I j (N )| = O(N 1-3α/8 ).Bounding T stable : In Appendix G.2, we choose T good and T stable such that T stable is the time after T good by which the algorithm picks all the sub-optimal arms atleast once. By Proposition 3.1, the algorithm approximately matches ω ⋆ after T stable . Using an argument similar to the one for bounding time to reach the optimal proportion in the fluid dynamics of Section 4, we can prove that T stable ⪅ (ω ⋆ min ) -1 T good a.s. in P µ , where ω ⋆ min = min a∈[K] ω ⋆ a (Lemma G.4, Appendix G.2.1).As we observe in the numerical results in Appendix J.4, forced exploration (step 1 of our algorithm) does not increase the observed sample complexity. We emphasize that without the forced exploration, Propositions 5.1 and 3.1 continue to hold if we can show that the proposed algorithm perform sufficient exploration over the instance. That is, after a random time T depending on the instance and satisfying E[T ] < ∞, every arm has N a (N ) = Ω( √ N ). As a result, upon proving sufficient exploration, asymptotic optimality will follow without the forced exploration step. In Appendix J.4, we see in the numerical experiments, when there is no forced exploration, AT2's sample complexity blows up over instances where multiple sub-optimal arms have equal mean. On the other hand, IAT2 performs optimally over the same instances and its sample complexity remains unaffected even when there is no forced exploration. To understand AT2's sample complexity blow up when multiple sub-optimal arms have the same mean, consider the sample paths where the best arm observes unusually small values in the first few samples. As a result, with positive probability, AT2 confuses one of the multiple sub-optimal arms with equal mean as the best arm and stay stuck sampling between those sub-optimal arms forever. However, IAT2 avoids such situation because of the exploration of every sub-optimal arm induced by the extra logarithmic term in the index. Based on these observations, we make the following conjectures: 1) AT2 performs sufficient exploration over instances where the means of all the sub-optimal arms are distinct, and 2) IAT2 performs sufficient exploration over all instances including when some of the sub-optimal arms may have equal means. 
numerical results: 
 In this section, we numerically demonstrate the dynamics followed by the algorithm AT2, and also compare its performance against the β-EB-TCB algorithm of [16] for different values of β, and TCB algorithm of [22] . We consider 4 armed Gaussian bandit with unit variance and mean vector µ = [10, 8, 7, 6.5 ]. We simulate one sample path of the AT2 without stopping rule, and plot the value of normalized indexes of the sub-optimal arms. Figure 1 demonstrates that the normalised indexes once close remain close, and hence, AT2 closely mimics the fluid path. In Figure 2 , we plot the sample complexities of the (I)AT2, (I)TCB, and β-EB-(I)TCB, for different choices of β, and observe that (I)AT2 outperforms all the other algorithms. Note that we use the same forced exploration rule and stopping rule for all algorithms. In Appendix J, we demonstrate by several examples that both the AT2 and IAT2 algorithms significantly outperform the β-EB-TCB and β-EB-ITCB of [16] when β is chosen different from the optimal β. We also illustrate that the AT2 and IAT2 algorithms have average sample complexity significantly lesser than the TCB and ITCB policies of [22] . In fact, we observe numerically, that (I)TCB doesn't quite satisfy the asymptotic optimality conditions (Figure 4 , Appendix J). Next, in Appendix J.4, we study the effect of choice of the forced exploration parameter α on the sample complexities of AT2 and IAT2. Additionally, we conduct simulations for natural extensions of these algorithms to bandits with distributions supported in [0, 1] (Appendix J.5). 
conclusion: 
 We considered the best-arm identification problem under the popular top-2 framework. In the literature, top-2 framework involves sequentially identifying the empirical best arm and the most-likely challenger arm, and sampling the empirical best with probability β and the other with the complimentary probability. However, optimal β was not known. [22] recently proposed a deterministic rule for deciding between the empirical best and the challenger arm. In this paper, we have provided a most natural first order optimality condition based rule to help decide between the two. We showed that our associated algorithm is asymptotically optimal, and empirically performs better than [22] both in sample and computational complexity. Our another key contribution was to identify the underlying limiting ordinary differential equation based fluid dynamics that our algorithm tracks. This structure also provides important insights which help prove convergence of the proposed algorithm. 
 
 Appendix: Below we provide a brief outline of the topics presented in the appendices.1. Algorithm (1) and ( 2) are, respectively, the pseudocodes of the AT2 and IAT2 algorithms introduced in Section 3. 2. Appendix B: We define the single parameter exponential family (SPEF) of distributions, and prove several inequalities bounding the index function, anchor function, and the derivatives of the anchor function, which are crucial for our analysis. 3. Appendix C: We introduce a framework using which we apply the implicit function theorem for proving several properties related to the fluid dynamics and the algorithm's allocations. 4. Appendix D: We prove Propositions 2.1 and 2.2 from Section 2. 5. Appendix E: We provide the proofs of the results mentioned in Section 4, and also construct the fluid dynamics for the β-EB-TCB algorithm ( [16] ) in Appendix E.2. 6. Appendix F: We provide a heuristic argument to show that if the minimum index meets with the index of some sub-optimal arm a ̸ = 1 following the ODEs in Theorem 4.1, then arm a must be incorporated into the set of minimum index arms. We argue via contradiction to show that, if this is not the case then index of arm a becomes strictly less than the minimum index of the arms, which implies a contradiction. Several of the key steps in the proof of Lemma 5.1 are extensions of the said argument to the non-fluid setting of the algorithm with additional terms because of the noise in the estimates. 7. Appendix G: We prove Proposition 3.1, 5.1, and provide detailed proofs of all the results mentioned in Section 5. 8. Appendix H: We provide the detailed proof of Theorem 3.1. 9. Appendix I: We describe a natural extension of the proposed AT2 and IAT2 algorithms to the class of distributions with support contained in [0, 1]. We do not theoretically analyze this algorithm owing to space constraints. However we compare the proposed algorithm with existing algorithms experimentally in Appendix J.5. 10. Appendix J: We compare the performance of the proposed algorithms against existing algorithms through numerical experiments. We also illustrate how our algorithm follows the fluid dynamics as the no. of samples increase.We consider single parameter exponential family (SPEF) of distributions of the formdν θ (x) = exp(θx -b(θ))dρ(x)where ρ is a dominating measure which we assume to be degenerate, θ lies in the interior of set Θ defined below (denoted by Θ o ):EQUATIONb(θ) = log R exp(θx)dρ(x)is the log-moment generating function of the measure ρ(•).For θ, θ ∈ Θ o , the KL-divergence between the measures ν θ and ν θ is,KL(ν θ , ν θ ) = (θ -θ)b ′ (θ) -b(θ) + b( θ).The mean under ν θ is given by b ′ (θ). Let S be the image of the setΘ o under the mapping b ′ (•). Note that S is an open interval. Also, since b ′′ (•) > 0 in Θ o , b ′ (•) is strictly increasing in Θ o ,Algorithm 1: Anchored Top-Two (AT2) Algorithm Input :Confidence parameter δ > 0, exploration parameter α ∈ (0, 1) for N ≥ 1 doV N ← a ∈ [K] | N a (N -1) < N α if V N ̸ = ∅ then A N ← arg min a∈[K] N a (N -1)// Forced exploration else if g( µ(N -1), N (N -1)) > 0 thenA N ← îN-1 // Choosing leader else A N ← arg min a∈[K]/{ îN-1 } I a (N -1)// Choosing challenger Sample X N from A N and compute µ(N ) and N (N )/* Generalized Log-Likelihood Ratio (GLLR) Test */ if min a∈[K]/{ îN } I a (N ) > β(N, δ) then return îN Algorithm 2: Improved Anchored Top-Two (IAT2) Algorithm Input :Confidence parameter δ > 0, exploration parameter α ∈ (0, 1) for N ≥ 1 do V N ← a ∈ [K] | N a (N -1) < N α if V N ̸ = ∅ then A N ← arg min a∈[K] N a (N -1)// Forced exploration else if g( µ(N -1), N (N -1)) > 0 thenA N ← îN-1 // Choosing leader else A N ← arg min a∈[K]/{ îN-1 } I a (N -1) + log N a (N -1) // Choosing challenger Sample X N from A N and compute µ(N ) and N (N ) /* Generalized Log-Likelihood Ratio (GLLR) Test */ if min a∈[K]/{ îN } I a (N ) > β(N, δ) then return îNbijection between Θ o and S. This implies we can parameterize the distributions in the SPEF using their means as well.Let θ µ be the unique θ satisfying b ′ (θ) = µ for some µ ∈ S. Clearly, θ µ is a strictly increasing function of µ. This follows since b ′ (•) is strictly increasing in Θ o . Additionally, all the higher derivatives of b(•) exist in the set Θ o (see Exercise 2.2.24 in [9] ).For µ, µ ∈ S we define d(µ, µ) as,d(µ, µ) = KL(ν θµ , ν θ µ ) = (θ µ -θ µ )µ -b(θ µ ) + b(θ µ ).We define µ inf ∈ R ∪ {-∞} and µ sup ∈ R ∪ {+∞}, respectively, to be the infimum and supremum of the interval S. Then, S = (µ inf , µ sup ).Definition B.1. For µ = (µ 1 , µ 2 , . . . , µ K ) ∈ S K , define r min (µ) = min i∈[K] {min{µ i - µ inf , µ sup -µ i }}.Since S is an open interval, r min (µ) is positive for every µ ∈ S K , and can be ∞ if both µ inf and µ sup are ∞.Partial derivatives of d(µ, µ): For every pair µ, µ ∈ S, the partial derivatives of d(µ, µ) with respect to the first argument isd 1 (µ, µ) def. = ∂ ∂µ d(µ, µ) = θ µ -θ µ ,and that with respect to the second argument is,d 2 (µ, µ) def. = ∂ ∂ µ d(µ, µ) = µ -µ b ′′ (θ µ ) .Enveloping the KL-divergence: In the following discussion, we try to bound the KL-divergence d(µ, µ) from both sides using the squared distance |µ -µ| 2 after imposing some restrictions on the choice of µ, µ ∈ S. For an instance µ ∈ S K , we define the constants ∆ min (µ) and ϵ(µ) as∆ min (µ) = min i∈[K]/{1} (µ 1 -µ i ) and ϵ(µ) = min ∆ min (µ) 4 , r min (µ) 2 .We further defineH(µ) = i∈[K]/{1} [µ i -ϵ(µ), µ 1 + ϵ(µ)], σ max (µ) = max µ∈H(µ) b ′′ (θ µ ) and σ min (µ) = min µ∈H(µ) b ′′ (θ µ ).Since H(µ) ⊂ S, all distributions with mean in H(µ) have positive variance. Note that b ′′ (θ µ ) represents the variance of the distribution with mean µ. As a result, since H(µ) is a compact set, both σ max (µ) and σ min (µ) are positive constants.Hence, b(•) is σ min (µ)-strongly convex and b ′ (•) is σ max (µ)-Lipschitz on the set (b ′ ) -1 (H(µ)).Thus, using [23, Theorems 2.1.5 and 2.1.10], for every θ 1 , θ 2 ∈ (b ′ ) -1 (H(µ)), we have|b ′ (θ 1 ) -b ′ (θ 2 )| 2 2σ max (µ) ≤ b(θ 2 ) -b(θ 1 ) -b ′ (θ 1 ) • (θ 2 -θ 1 ) = d(ν θ1 , ν θ2 ) ≤ |b ′ (θ 1 ) -b ′ (θ 2 )| 2 2σ min (µ) ,and hence, for µ, µ ∈ H(µ),EQUATIONBounding the partial derivatives: We now introduce bounds on the partial derivativesEQUATIONSimilarly, since,d 2 (µ, x) = - µ -x b ′′ (θ x ) and d 2 ( µ, x) = x -µ b ′′ (θ x ) ,we have,EQUATIONFor every arm a ∈ [K], let µ a be an estimate ofµ a satisfying | µ a -µ a | ≤ ϵ(µ) and µ = ( µ a ) a∈[K] . Since ϵ(µ) ≤ ∆min(µ), the empirically best arm with respect to the estimates µ is the first arm. Also let N a be the no. of times arm a has been pulled and N = (N a ) a∈ [K] .Enveloping the anchor function: As we introduced in Section 2, the anchor function is,g( µ, N ) = a̸ =1 d( µ 1 , x 1,a ) d( µ a , x 1,a ) -1,where x 1,a = N1 µ1+Na µa. Note that µ a , x 1,a ∈ H(µ) for every a ∈ [K]/{1}. Therefore, using (6), we have,σ min (µ) σ max (µ) a̸ =1 ( µ 1 -x 1,a ) 2 ( x 1,a -µ a ) 2 -1 ≤ g( µ, N ) ≤ σ max (µ) σ min (µ) a̸ =1 ( µ 1 -x 1,a ) 2 ( x 1,a -µ a ) 2 -1, Putting x 1,a = N1 µ1+Na µa, we obtain,EQUATIONNowµ 1 -x 1,a = Na N1+Na ( µ 1 -µ a ) and x 1,a -µ a = N1 N1+Na ( µ 1 -µ a ). Using these, we can say, EQUATIONN = (N a : a ∈ [K]) is, W a ( µ, N ) = N 1 d( µ 1 , x 1,a ) + N a d( µ a , x 1,a ).Observe that, the empirical index I a (N ) and index I a (N ) introduced in Section 3 are, respectively, equivalent to the quantities W a ( µ(N ), N (N )), and W a (µ, N (N )), where µ(N ) is the empirical estimate and N (N ) is the algorithm's allocation at iteration N .Using (6) we have,1 2σ min (µ) (N 1 ( µ 1 -x 1,a ) 2 + N a ( x 1,a -µ a ) 2 ) ≤ W a ( µ, N ) ≤ 1 2σ min (µ) (N 1 ( µ 1 -x 1,a ) 2 + N a ( x 1,a -µ a ) 2 ).Putting x 1,a = N1 µ1+Na µa, we get,( µ 1 -µ a ) 2 2σ max (µ) N 1 N a N 1 + N a ≤ W a ( µ, N ) ≤ ( µ 1 -µ a ) 2 2σ min (µ) N 1 N a N 1 + N a , which implies, (µ 1 -µ a -2ϵ(µ)) 2 2σ max (µ) N 1 N a N 1 + N a ≤ W a ( µ, N ) ≤ (µ 1 -µ a + 2ϵ(µ)) 2 2σ min (µ) N 1 N a N 1 + N a .We defineEQUATIONUsing the same notation, as we used in (10) , we have,EQUATIONfor every arm a ∈ [K]/{1}.Enveloping the partial derivatives of anchor function with respect to N : While analyzing the AT2 and IAT2 algorithms, we need to show that the anchor function converges to zero at a uniform rate as no. of iteration goes to infinity. During this step, we need to bound the partial derivatives of the anchor function g(µ, N ) with respect to N . Below we evaluate the partial derivatives of g(µ, N ) with respect to N a for different arms a ∈EQUATION)where∆ a = µ 1 -µ a and f (µ, a, N ) = - ∂ ∂x d(µ 1 , x) d(µ a , x) x=x1,a = - d 2 (µ 1 , x 1,a ) d(µ a , x 1,a ) + d(µ 1 , x 1,a )d 2 (µ a , x 1,a ) (d(µ a , x 1,a )) 2 .Using ( 8), and ( 6), we have,-d 2 (µ 1 , x 1,a ) = Θ(µ 1 -x 1,a ), d 2 (µ a , x 1,a ) = Θ(x 1,a -µ a ), d(µ 1 , x 1,a ) = Θ((µ 1 -x 1,a ) 2 ), and d(µ a , x 1,a ) = Θ((x 1,a -µ a ) 2 ),where the constants hidden in Θ(•) depend only on µ and are independent of the sample path. Therefore,EQUATION)As a consequence, we have,EQUATIONC Framework for applying the Implicit function theorem (IFT)In this appendix we explain a general framework using which we later apply the Implicit function theorem for the following purposes:1. Constructing the fluid dynamics for the AT2 and β-EB-TCB algorithms in Appendix E.2. Proving convergence of the algorithm's allocations to the optimal proportions in Appendix G.2.2.We introduce the variables:N = (N a ∈ R ≥0 : a ∈ [K]), I ∈ R, η = (η a ∈ R : a ∈ [K]), and N ≥ 0. After fixing some instance µ ∈ S K (S is defined in Appendix B), we define the following functions:Φ 1 (N , η) = a∈[K]/{1} d(µ 1 , x 1,a (N 1 , N a )) d(µ a , x 1,a (N 1 , N a )) -1 -η 1 , for a ∈ [K]/{1}, Φ a (N , I, η) = N 1 d(µ 1 , x 1,a (N 1 , N a )) + N a d(µ a , x 1,a (N 1 , N a )) -I -η a ,andΦ K+1 (N , N ) = a∈[K] N a -N, where x 1,a (N 1 , N a ) = N 1 µ 1 + N a µ a N 1 + N a .For every non-empty subset B ⊆ [K]/{1}, we define the vector valued functions,Φ B (N , I, η, N ) = [ Φ 1 (N , η), (Φ a (N , I, η)) a∈B , Φ K+1 (N , N ) ] ,andΦ B (N , I, η) = [ Φ 1 (N , η), (Φ a (N , I, η)) a∈B ] .We denoteΦ [K]/{1} (•) just using Φ(•).In the definitions of Φ B (•) and Φ B (•), without loss of generality, we assume that, the functions Φ a (•) in the tuple (Φ a (•)) a∈B are enumerated in the increasing order of a ∈ B, i.e., if we haveEQUATIONΦ B = Φ 1 , Φ a1 , , Φ a2 , Φ a3 , . . . Φ a |B| .Before stating the main result of this section in Lemma C.1, we define some notation that are essential for the lemma statement. For any A ⊆ [K], we use the notation N A to denote the tuple of variables (N a : a ∈ A). For some vector valued function G depending on N , denote the Jacobian of G(•) with respect to the tuple of variables N A using ∂G ∂N A . For any non-empty B ⊆ [K]/{1}, we define B = B ∪ {1}. For every k ≥ 1, 0 k and 1 k , respectively, refers to a k-dimensional vector with entries 0 and 1. We define Z B to be the set of tuples (N , I,0 K , N ) with N ∈ R K ≥0 , I ∈ R, and N ∈ R >0 , which satisfy Φ B (N , I, 0 K , N ) = 0 |B|+2 .Lemma C.1 (Invertibility of the Jacobian). For all non-empty subset B ⊆ [K]/{1}, the following statements hold true at every tuple (N , I,0 K , N ) in the set Z B , 1. The Jacobian ∂ Φ B ∂N B is invertible at (N , I, 0 K ).2. We have1 T |B|+1 ∂ Φ B ∂N B -1 ∂ Φ B ∂I ≤ - a∈B 1 d(µ a , µ 1 ) , at (N , I, 0 K ).3. The Jacobian ∂Φ B ∂(N B ,I) defined as,EQUATION)Now we observe the following properties about the sign of the entries of the above Jacobian matrix,• We have N > 0 and Φ 1 (N , 0 K ) = 0. This implies N 1 > 0 and max a∈[K]/{1} N a > 0. As a result, using (15), we have ∂Φ1 ∂N1 < 0 and ∂Φ1 ∂Na i ≥ 0 for every i ∈ {1, 2, . . . , |B|}.• For i ∈ {2, . . . , |B| + 1}, in the i-th row, the only non-zero entries can be the first and the i-th entry. The first entry is∂Φa i ∂N1 = d(µ 1 , x 1,ai (N 1 , N ai )) ≥ 0. The i-th entry is ∂Φa i ∂Na i = d(µ ai , x 1,ai (N 1 , N ai )). Since we have N 1 > 0, using (6), we have d(µ ai , x 1,ai (N 1 , N ai )) > 0, making the i-th entry positive.Therefore, considering only the sign of the elements, the matrix in ( 16) is of the form,EQUATIONwhere the symbols ++, -and + implies that the corresponding entries are positive, negative and non-negative.We now argue that a matrix of the above structure has a rank |B| + 1. To see that, by subtracting some appropriate constant times the i-th column from the first column, we can make the entries in position i ∈ {2, 3, . . . , |B| + 1} in the first column zero. As a result of these transformations, since we are subtracting non-negative quantities from the first entry of the first column, that entry remains negative. The matrix we obtain after this sequence of transformations has a structure,EQUATION)Clearly a matrix of the above structure has a rank |B| + 1 and therefore invertible.Statement 2: Using statement 1 of Lemma C.1, if we take v = ∂ Φ B ∂N B -1 ∂ Φ B∂I , then we have,∂ Φ B ∂N B v = ∂ Φ B ∂I .Note that, the RHS of the above linear system i.e. ∂ Φ B ∂I is a |B| + 1 dimensional vector with zero in its first entry and -1 in every other entry. Using (17) , v = [v 1 , v 2 , v 3 , . . . , v |B|+1 ]T satisfies a linear system with coefficients having the following signs,(--)v 1 + (+)v 2 + (+)v 3 + (+)v 4 + . . . + (+)v |B|+1 = 0, and for i ∈ {2, . . . , |B| + 1}, (+)v 1 + (++)v i = (--),where ++, -and + represents quantities which are positive, negative and non-negative.For every i ∈ {2, . . . , |B| + 1}, we can eliminate v i from the first equation by subtracting some positive constant times the i-th equation from it. After eliminating v 2 , v 3 , . . . , v |B|+1 from the first equation following the mentioned procedure, we will be left with an equation of the form (--)v 1 = (+), implying v 1 ≤ 0. Now the i-th equation of the system, for i ∈ {2, . . . , |B| + 1} is,EQUATIONWe know that,∂Φa i-1 ∂N1 = d(µ 1 , x 1,ai-1 )and∂Φa i-1 ∂Na i-1 = d(µ ai-1 , x 1,ai-1 ), where x 1,a = N1µ1+Naµa N1+Na for every a ∈ [K]/{1}.Now putting the derivatives in ( 19), we haved(µ 1 , x 1,ai-1 )v 1 + d(µ ai-1 , x 1,ai-1 )v i = -1,which implies,v i = - 1 d(µ ai-1 , x 1,ai-1 ) - d(µ 1 , x 1,ai-1 ) d(µ ai-1 , x 1,ai-1 ) v 1 ,for every i ∈ {2, . . . , |B| + 1}.i ∈ {2, 3, . . . , |B| + 1}, we get, |B|+1 i=2 v i = - |B|+1 i=2 1 d(µ ai-1 , x 1,ai-1 ) -v 1 |B|+1 i=2 d(µ 1 , x 1,ai-1 ) d(µ ai-1 , x 1,ai-1 ) = - a∈B 1 d(µ a , x 1,a ) -v 1 a∈B d(µ 1 , x 1,a ) d(µ a , x 1,a ) ≤ - a∈B 1 d(µ a , x 1,a ) -v 1 a∈[K]/{1} d(µ 1 , x 1,a ) d(µ a , x 1,a ) (since v 1 ≤ 0) = - a∈B 1 d(µ a , x 1,a ) -v 1 ,where the last step follows from the fact that a∈[K]/{1} d(µ1,x1,a) d(µa,x1,a) = Φ 1 (N , 0 K ) + 1 = 1. Taking v 1 on the LHS, we have, |B|+1 i=1 v i ≤ - a∈B 1 d(µ a , x 1,a ).Note that the LHS of the above inequality is same as1 T v = 1 T ∂ Φ B ∂N B -1 ∂Φ K+1∂I . In the RHS, since d(µ a , x 1,a ) ≤ d(µ a , µ 1 ), we conclude the desired result.Statement 3: We have,∂Φ B ∂(N B , I) =         ∂ Φ B ∂N B ∂ Φ B ∂I ∂Φ K+1 ∂N B ∂Φ K+1 ∂I         =         ∂ Φ B ∂N B ∂ Φ B ∂I 1 T |B|+1 0        We do the following determinant preserving column operation on ∂Φ B ∂(N B ,I) ,∂Φ B ∂(N B , I) :,|B|+2 ⇐= ∂Φ B ∂(N B , I) :,|B|+2 - ∂Φ B ∂(N B , I) :,1:|B|+1 ∂ Φ B ∂N B -1 ∂ Φ B ∂I ,where , respectively, denotes the |B| + 2-th column and left∂Φ B ∂(N B ,I) :,|B|+2(|B| + 2) × (|B| + 1) submatrix of ∂Φ B ∂(N B ,I) .The above column operation gives us the matrix,         ∂ Φ B ∂N B 0 |B|+1 1 T |B|+1 -1 T |B|+1 ∂ Φ B ∂N B -1 ∂ Φ B ∂I         , which has the same determinant as ∂Φ B ∂(N B ,I) . Therefore,det ∂Φ B ∂(N B , I) =   -1 T |B|+1 ∂ Φ B ∂N B -1 ∂ Φ B ∂I   × det ∂ Φ B ∂N B .Using statement 1 and 2 of Lemma C.1, both the quantities in the above product are non-zero, making the Jacobian ∂Φ B ∂(N B ,I) invertible for every tuple in Z B .Theorem D.1 is essential for proving Propositions 2.1 and 2.2 in Section 2. Before stating Theorem D.1 we state an alternative formulation of the max-min problem 1 which we call O.O : minEQUATIONwhere N a ≥ 0 for all a, and each x 1,a = µ1N1+µaNa.The optimal value of the problem O is of the form T ⋆ (µ) log(1/(2.4δ)), where T ⋆ (µ) is the reciprocal of the optimal value of (1).If N ⋆ = (N ⋆ a : a ∈ [K]) is an optimal allocation solving O, then ω ⋆ a = N ⋆ a b∈[K] N ⋆ bis an optimal proportion solving (1). Similarly if ω ⋆ is an optimal proportion solving (1) thenN ⋆ = (N ⋆ a : a ∈ [K]) with N ⋆ a = ω ⋆ a T ⋆ (µ)is an optimal allocation solving O. Theorem D.1 implies uniqueness to the solution of O which also implies uniqueness of the solution of (1). Some notations are needed before stating Theorem D.1. Let B ⊂ [K]/1 and B = B ∪ {1}. Let ν = (ν a : a ∈ [K]) ∈ S K be some instance with ν 1 > max a̸ =1 ν a . Let (I a : a ∈ B) each be strictly positive. If B c ̸ = ∅ then let (N a ∈ R ≥0 : a ∈ B c) be the no. of samples allocated to arms in B c .We define N 1,1 as zero when a∈B c N a = 0 or B c = ∅. Otherwise, we take N 1,1 to be the uniqueEQUATIONwhere x 1,a = ν1N1+νaNa N1+Na . Note that if B c ̸ = ∅ and a∈B c N a > 0, there exists an a ∈ B c with N a > 0. As a result, the LHS of ( 21) decreases from ∞ to 0 as N 1 increases from 0 to ∞. This implies the existence of a unique N 1 > 0 solving (21) .Set N 1,2 := max a∈B I a d(ν 1 , ν a ) -1 . Theorem D.1. There exists a unique solutionEQUATIONandEQUATION)Further, N ⋆ 1 ≥ max(N 1,1 , N 1,2) and each N ⋆ a ≥ Ia d(νa,ν1) . Furthermore, The optimal solution to O is uniquely characterized by the solution above with B = {2, . . . , K} and each I a = log(1/(2.4δ)) and constraints (20) tight, that is, indexes of all the sub-optimal arms being equal to log(1/(2.4δ)). Further,N ⋆ 1 ≥ max a∈[K]\1 log(1/(2.4δ) d(ν1,νa) and each N ⋆ a ≥ log(1/(2.4δ) d(νa,ν1) .Proof: First observe that every solution N ⋆ 1 and (N ⋆ a : a ∈ B) to the system ( 22) and ( 23) must satisfyN 1 ≥ max{N 1,1 , N 1,2 } and N ⋆ a ≥ Ia d(νa,ν1) , for every a ∈ B. If B c ̸ = ∅, (22) implies, a∈B c d(ν 1 , x 1,a ) d(ν a , x 1,a ) ≤ a∈[K]/{1} d(ν 1 , x 1,a ) d(ν a , x 1,a ) = 1. If a∈B c N a = 0, then N 1 ≥ 0 = N 1,1 . Otherwise, we can find an a ∈ B c with N a > 0,I a = N ⋆ 1 d(ν 1 , x 1,a ) + N ⋆ a d(ν a , x 1,a ) = min x∈[νa,ν1] {N ⋆ 1 d(ν 1 , x) + N ⋆ a d(ν a , x)}.Note that RHS of the above inequality is upper bounded by min{N 1 and (N ⋆ a : a ∈ B). For everyN 1 ≥ N 1,2 and a ∈ B, as N a increases from 0 to ∞, N 1 d(ν 1 , x 1,a ) + N a d(ν a , x 1,a ) increases monotonically from 0 to N 1 d(ν 1 , ν a ). Note that N 1 d(ν 1 , ν a ) ≥ N 1,2 d(ν 1 , ν a ) ≥ I a (by the definition of N 1,2). As a result, we can find a unique N a for which N 1 d(ν 1 , x 1,a ) + N a d(ν a , x 1,a ) = I a . For every a ∈ B, we call that unique N a as N a (N 1 ). Observe that, since I a > 0, N a (N 1 ) is strictly decreasing in N 1 , and ifI a = 0, then N a (N 1 ) = 0. Also, if a = arg max b∈B I b d(ν1,ν b ) , then N a (N 1,2 ) = ∞ and lim N1→∞ N a (N 1 ) = Ia d(νa,ν1) . We now consider the allocation where every arm a ∈ B has N a (N 1 ) samples, and consider the function,h(N 1 ) = a∈[K]/{1} d(ν 1 , x 1,a ) d(ν a , x 1,a ).Observe that, for all a ∈ B, d(ν1,x1,a) d(νa,x1,a) is strictly decreasing for N 1 ≥ N 1,2 . Also if B c is non-empty,decreases to 0 as N 1 → ∞. Therefore, if we can show that h(max{N 1,1 , N 2,1 }) ≥ 1, then we can find a unique N ⋆ 1 ≥ max{N 1,1 , N 1,2 } at which h(N ⋆ 1 ) = 1, and can take N ⋆ a = N a (N ⋆ 1 )for every a ∈ B. Following this, to prove uniqueness, it is sufficient to show h(max{N1,1 , N 1,2 }) ≥ 1. If N 1,2 ≥ N 1,1 , then some a ∈ B has N a (N 1,2 ) = ∞. As a result, we have h(N 1,2 ) = ∞ ≥ 1. Otherwise, if N 1,1 ≥ N 1,2 > 0, then by definition of N 1,1 , we have h(N 1,1 ) ≥ a∈B c d(ν 1 , x 1,a ) d(ν a , x 1,a ) = 1.Hence we finish proving the first part of Theorem D.1.To see the necessity of the stated optimality conditions for O observe that we cannot haveN ⋆ 1 = 0 or N ⋆ a = 0 as that implies that the index W a (N ⋆ 1 , N ⋆ a ) is zero. Further, if W a (N ⋆ 1 , N ⋆ a ) > log(1/(2.4δ)), the objective improves by reducing N ⋆ a . Thus the constraints (20) must be tight. To see the tightness of ( 20) again note that the derivative of W a (N 1 , N a ) with respect to N 1 and N a , respectively, equals d(µ 1 , x 1,a ) and d(µ a , x 1,a ). Now, perturbing N 1 by a tiny ϵ and adjusting each N a byd(µ1,x1,a) d(µa,x1,a) ϵ maintains the value of W a (N ⋆ 1 , N ⋆ a ). Thus, at optimal N ⋆ , necessity of tightness of inequalities in (20) follows. This condition can also be seen through the Lagrangian (see [2] ).The fact that these three criteria uniquely specify the optimal solution follows from our analysis above. Since the convex problem O has a solution, the uniqueness of the solution above satisfying the necessary conditions implies that this uniquely solves O.To prove Propositions 2.1 and 2.2, we need to use the Implicit function theorem. For that, we define the following functions,J 1 (N ) = g(µ, N ) = a̸ =1 d(µ 1 , x 1,a (N 1 , N a )) d(µ a , x 1,a (N 1 , N a )) -1, ∀ a ∈ [K]/{1} J a (N , I) = N 1 d(µ 1 , x 1,a (N 1 , N a )) + N a d(µ a , x 1,a (N 1 , N a )) -I, J K+1 (N , N ) = a∈[K] N a -N, where N = (N a ∈ R ≥0 : a ∈ [K]), I ∈ R, N ∈ R + , and, for every a ∈ [K]/{1}, x 1,a (N 1 , N a ) = N1µ1+Naµa N1+Na.Using these functions, for every non-empty B ⊆ [K]/{1}, we define the vector valued functionJ B (N , I, N ) = [J 1 (N ), (J a (N , I)) a∈B , J K+1 (N , N )] . We call J [K]/{1} (•) as J (•). Recall that B denotes B ∪ {1}.For every m ≥ 1, we use the notation 0 m to denote a m-dimensional vector with all entries set to zero. Observe that, for everyB ⊆ [K]/{1}, J B (N , I, N ) = Φ B (N , I, 0 K , N ), where the function Φ B (•) is defined in Appendix C.Lemma D.1 is essential for proving Proposition 2.1.Lemma D.1. For every N > 0 and non-empty For every non-empty subset B ⊆ [K]/{1}, we define the function J B (•) to be the first |B| + 1 components of the vector valued function J B (•), or in other words,B ⊆ [K]/{1}, if N = ( Na ∈ R ≥0 : a ∈ [K]) satisfies a∈B c Na < N ,J B (•) = [ J 1 (•) , (J a (•)) a∈B ] .Observe that J B (•) depends only on the tuple N and I, and doesn't depend on N . Also for every tuple(N , I) ∈ R K ≥0 , J B (N , I) = Φ B (N , I, 0 K ), where Φ B is defined in Appendix C.We now proceed on proving Propositions 2.1 and 2.2.Proof of Proposition 2.1: Observe that, for every non-empty B ⊆ [K]/{1}, solving the system (2) is equivalent to solving for the pairN B , I B in J B ((N B , N B c ), I B , N ) = 0.For every I ≥ 0, by Theorem D.1, there is a uniqueN B = (N a ∈ R ≥0 : a ∈ B) for which, J B ((N B , N B c ), I) = 0 |B|+1. We denote that solution using N B (I) (we supress the dependence on N B c for cleaner presentation, and also because we will be treating N B c like a constant in the rest of the proof). Since, J B (N , I) = Φ B (N , I, 0 K ), by the Implicit function theorem and using statement 1 of Lemma C.1, the function I → N B (I) is continuously differentiable. Also, we haveN ′ B (I) = - ∂ J B ∂N B -1 ∂ J B ∂I = - ∂ Φ B ∂N B -1 ∂ Φ B ∂I ,where the right most quantity is evaluated at the tuple ((N B (I), N B c ), I, 0 K ). Moreover, using statement 2 of Lemma C.1, we have,a∈B N ′ a (I) = 1 T |B|+1 N ′ B (I) = -1 T |B|+1 ∂ Φ B ∂N B -1 ∂ Φ B ∂I ≥ a∈B 1 d(µ a , µ 1 )> 0As a result, the function a∈B N a (I) is strictly increasing in I with a derivative atleast Now we show that the K-variable convex optimization problem O defined in (20) can be reduced to a single variable convex optimization problem involving only N 1 . To see this, observe that O is equivalent to the problemO 1 min a∈[K] N a s.t. ∀a ̸ = 1, W a (N 1 , N a ) = N 1 d(µ 1 , x 1,a ) + N a d(µ a , x 1,a ) = log(1/(2.4δ))wherex 1,a = N 1 µ 1 + N a µ a N 1 + N a , and ∀a ∈ [K], N a ≥ 0.This follows from the proof of Theorem D.1.We first make some observations about O 1 .1. Upon fixing some N 1 > 0, N a → W a (N 1 , N a ) is strictly increasing for every a ̸ = 1. Moreover, we haveW a (N 1 , 0) = 0 and lim Na→∞ W a (N 1 , N a ) = N 1 d(µ 1 , µ a ).As a result, every feasible solution of O 1 must satisfyN 1 d(µ 1 , µ a ) > log(1/(2.4δ)) for every a ̸ = 1, which implies N 1 > log(1/(2.4δ)) min a̸ =1 d(µ1,µa) .2. Using the preceding observation, for every a ̸ = 1 and N 1 > log(1/(2.4δ)) min a̸ =1 d(µ1,µa) , we can find a unique N a such that W a (N 1 , N a ) = log(1/(2.4δ)). We use Na (N 1 ) to denote that unique N a as a function of N 1 . Using the Implicit function theorem, it is easy to prove that the function N 1 → Na (N 1 ) is differentiable for every N 1 > log(1/(2.4δ)) min a̸ =1 d(µ1,µa) with the derivative beingN ′ a (N 1 ) = - d(µ 1 , z a (N 1 )) d(µ a , z a (N 1 )) where z a (N 1 ) = N 1 µ 1 + Na (N 1 )µ a N 1 + Na (N 1 ).It follows that O 1 is equivalent to the single variable optimization problem:O 2 min f (N 1 ) def. = N 1 + a̸ =1 Na (N 1 ) s.t. N 1 > log(1/(2.4δ)) min a̸ =1 d(µ 1 , µ a ). Further,f ′ (N 1 ) = 1 + a̸ =1 N ′ a (N 1 ) = 1 - a̸ =1 d(µ 1 , z a (N 1 )) d(µ a , z a (N 1 )) ,which is exactly negative of the anchor function defined in Section 2 w.r.t. the allocation where arm 1 gets N 1 samples and every sub-optimal arm a ̸ = 1 gets Na (N 1 ) samples. Furthermore, f ′ (N 1 ) is strictly increasing in N 1 and increases from -∞ to 1 as N 1 increases from log(1/(2.4δ)) min a̸ =1 d(µ1,µa) to ∞. As a result, O 2 is a convex problem w.r.t. N 1 and the optimal N 1 solving O 2 is uniquely identified by the condition:a̸ =1 d(µ 1 , z a (N 1 )) d(µ a , z a (N 1 )) -1 = 0,which is equivalent to saying that the anchor function g must be zero when evaluated at the allocation where the first arm gets N 1 samples and every arm a ̸ = 1 gets Na (N 1 ) samples. Figure 3 shows an illustrative plot of O 2 's objective f (N 1 ).This observation also implies that the unique β which makes the β-EB-TCB(I) policy in [16] asymptotically optimal is uniquely identified by the first order conditions: 1) the anchor function g must be zero and 2) indexes of the sub-optimal arms must be equal. Hence allocations made by every asymptotically optimal sampling policy must converge to these first order conditions. Both the fluid dynamics in Section 4 and Proposition 5.1 in Section 5, respectively, show that the sampling policies of (I)AT2 algorithm converges to these first order conditions in a fluid model and in the proposed algorithms.D.2 Sub-optimality of TCB(I) [22] implicitly assumes that the optimal proportion is uniquely identified by the condition that indexes of every sub-optimal arm under the proportion are equal. Note that the optimal proportion is a K dimensional vector and the conditions mentioned in [22, Lemma 2, statement 2] has K -1 equations (K -2 equations to maintain equality of K -1 indexes and one more equation to make sure that all the entries in the K-dimensional vector add up to 1). Moreover, in Appendix D.1, changing the variables of the problem O 2 to capture proportion of samples allocated to every arm, it is not hard to prove that for every value of w 1 ∈ (0, 1), we can get a unique proportion (w 1 , w 2 , . . . , w K ) such that a∈[K] w a = 1 and index of all sub-optimal arms under the proportion are equal. By the argument in Appendix D.1, the unique optimal proportion out of these infinite no. of proportions satisfying equality of the indexes, is uniquely identified by the necessary and sufficient condition that the anchor function g(•) evaluated at that proportion must be zero. Without this condition, the allocation cannot be optimal. In the numerical experiments of Appendix J.2, we see that the anchor function doesn't always converge to zero for the TCB(I) algorithm. As a result, allocations made by TCB(I) can be sub-optimal.Proof of Theorem 4.1: We first prove all the steps of Theorem 4.1 except for showing the existence of β > 0 and independent of N such that I ′ b (N ) > β. That requires intermediate lemmas and is done separately.First suppose that B contains a singleton index b. Define N 1 (N ) and N b (N ) using IFT through the equationsa̸ =1 d(µ 1 , x 1,a ) d(µ a , x 1,a ) -1 = 0 (24)and a N a = N. For each a, letting x ′ 1,a denote the derivative of x 1,a with respect toEQUATIONand each x ′ 1,a = Na∆a (N1+Na) 2 . Differentiating (24) with respect to N , observing thatN ′ b = 1 -N ′ 1 , we get N ′ 1 a̸ =1 h a N a = N 1 h b (1 -N ′ 1 ).N ′ 1 = N 1 h b a̸ =1 h a N a + N 1 h b as stipulated. Also N ′ b = a̸ =1 haNa a̸ =1 haNa+N1h b .Now consider the case where g = 0, and we have set B ⊂ [K]/1 of indices where the indexes are equal, they are higher for the remaining set. Cardinality of B is at least 2. We want to argue that as N increases, and the equality of indexes in B is maintained along with g = 0, then the tied indexes will increase with N .We have for b, a ∈ BEQUATIONFurthermore, g = 0, i.e.,EQUATION)Keeping a particular b ∈ B fixed, differentiating with respect to N , (since for each a, by definition ofx 1,a , N 1 d ′ (µ 1 , x 1,a ) + N a d ′ (µ a , x 1,a ) = 0) we see from (26) that N ′ 1 d(µ 1 , x 1,b ) + N b ′ d(µ b , x 1,b ) = N ′ 1 d(µ 1 , x 1,a ) + N a ′ d(µ a , x 1,a ).Using (26) again in the above equality,EQUATIONThen from (27) , we have thatEQUATION(Recall that for each a, x ′ 1,a denotes the derivative of x 1,a with respect to N 1 and x ′ 1,a denotes the derivative of x 1,a with respect to N a .) Plugging ( 28) and ( 25) in (29), multiplying each term by N 2 1 , we see thatN ′ 1 is a ratio of N 1 N ′ b d b,b h B with h(N ) + N b d b,b h B .Then,N ′ b = N ′ 1 h(N )d -1 b,b + N b h B N 1 h B .In particular, since, Let x( a) be such thatEQUATIONd(µ 1 , x( a)) = (K -1) -1 d(µ a , x( a)). It is guaranteed to exist since the ratio d(µ a , x)/d(µ 1 , x) ∈ (0, ∞) is monotonic in x.Next, letd a = µ 1 -x a x a -µ a and d( a) = µ 1 -x( a)x( a) -µ a .Since K ≥ 2, we have x( a) ≥ x a , and d( a) ≤ d a .Lemma E.1. Suppose that g = 0. Then,EQUATION)Lemma E.2. Suppose that g = 0. Then, 1. there exist constants H and D such that h a ≤ H for all a, and d -1 a,a ≤ D for all a.2. Further, there exists an a such that N a > αN for some α > 0 and the corresponding h a is bounded from below by a positive constant. Lemma E.3. Suppose that g = 0, and for B ⊂ [K]/1 the indexes are all equal and are strictly higher for the remaining set. Then there exists a constant β > 0 such thatN ′ 1 d(µ 1 , x 1,a ) + N ′ a d(µ a , x 1,a ) = I ′ B (N ) > β.Proof of Lemma (E.1): Since g = 0, it follows that for each a ∈[K] \ 1, d 1,a d a,a ≤ 1.Thus, x 1,a ≥ x a . This in turn implies that for each a, N 1 ≥ N a d -1 a . The above follows from substituting for x 1,a in the inequality x 1,a ≥ x a , and from the definition of d a . Moreover, since g = 0, it also follows that for each a ̸ = 1, x(( a) ≥ x 1,a , implyingN 1 d(( a)) ≤ N a .Then,N 1   1 + a̸ =1 d a   ≥ N and N 1 (1 + d( a)) ≤ N,and the result follows.Proof of Lemma (E.2): Recall the definitions of h a and f (µ, a, N ) from Section 4.Since, g = 0 implies that x 1,a ≥ x a for all a, it follows thatd a,a = d(µ a , x 1,a ) ≥ d(µ a , x a ). In particular, for all a d -1 a,a ≤ D for D = max a d(µ a , x a ) -1 .Further, d ′ (µ a , x 1,a ) is continuous in x 1,a and is bounded from above by sup xa≤x1,a≤µ1 d ′ (µ a , x 1,a ). Similarly, -d ′ (µ 1 , x 1,a ) is bounded from above by sup xa≤x1,a≤µ1 -d ′ (µ 1 , x 1,a ). This implies that f (µ, a, N ) is bounded from above by a positive constant and hence so is h a .To see part 2, observe from definition of x(ã) that x 1,ã ≤ x(ã). It follows thatN a ≥ N 1 d -1 a . Therefore, N a ≥ N d -1 a (1 + a̸ =1 d a ) -1 . (31) Again, x 1, a ≤ x( a). Therefore, d a, a = d(µ a , x 1, a ) ≤ d(µ a , x( a)) and d 1, a = d(µ 1 , x 1, a ) ≥ d(µ 1 , x( a)).Further, d ′ (µ a , x 1, a ) is continuous in x 1, a and is bounded from below byinf x a ≤x 1, a ≤x( a) d ′ (µ a , x 1, a ). Similarly, -d ′ (µ 1 , x 1, a ) is bounded from below by inf x a ≤x 1, a ≤x( a) -d ′ (µ 1 , x 1, a ).Thus, f (µ, a) is bounded from below. Further, since eachN a ≤ d a N 1 , N 2 1 /(N 1 + N a ) 2 ≥ (1 + d a ) -2 ,hence, h a is bounded from below by a positive constant.Proof of Lemma (E.3): Recall from (31) thatEQUATIONAlso, recall the definition of f (µ, a, N ) and h a from Section 4.Because of (30) and (32), and since N a ≤ N , we see that f (µ, a) is bounded from below by a positive constant, and the same is true for h a .If a ∈ B, recall that h B = a∈B h a d -1 a,a . Thus, h B is greater than a constant times N . This ensures that N ′ a is bounded from below by a positive constant. Since d a, a is also bounded from below by a positive constant, we conclude that there exists a β > 0 such that I ′ B (N ) > β.If a / ∈ B, then recalling that h(N ) = a∈B c /1 h a N a , we conclude that N ′ a is bounded from below by a positive constant. This implies that as N increases by a positive fraction, so does each N a for a ∈ B. This in turn ensures that then h B is thereafter bounded from below by a positive constant. In particular, after some delay we have I ′ B (N ) > β for some β > 0.E.1 Fluid dynamics starting at g < 0 Proposition E.1 provides us the ODEs by which the fluid allocations evolve in step 3 of the description of fluid dynamics when g < 0.Proposition E.1. Now consider the case where g < 0 at total allocations N , and B again denotes the set of arms whose indexes have the minimum value. Then, till I B (N ) increases with N to either hit an index in B c , or for g to equal zero, whichever is earlier,I ′ B (N ) = a∈B d -1a,a -1 , and for First we argue that N i1 < Ni1 . Suppose this is not true, then g < 0 implies that for N 1 fixed, there exists an arm a so that N a < Na , else if each N a ≥ Na then since g increases with N a , we would have g ≥ 0. This contradiction implies that index for arm a is < ÎB (N ). It follows that the index corresponding to i 1 is < ÎB (N ). Since the index increases with N i1 , it follows that N i1 < Ni1 . Thus, initially N increases due to increase in N i1 . Let B = {i 1 }. Suppose, iteratively that B = {i 1 , . . . , i j-1 }, denotes the smallest indexes that are equal and increase with N and g < 0. Proof follows by observing that the derivative of each index a ∈ B satisfies the relation N ′ a d a,a = I ′ B (N ). Further, a∈B N ′ a = 1. Thus, as N increases, each N a (N ), a ∈ B increases, so that g increases. Since all indexes corresponding to B c are constant, as N increases, either g = 0 first or another index I j becomes equal toEQUATIONI B (N ).For every β ∈ (0, 1) and allocation N = (N a ∈ R ≥0 : a ∈ [K]), we define the β-anchor function as,g(N ; β) = β - N 1 a∈[K] N a .Note that, if g(N ; β) = 0, then β-fraction of the total no. of samples in the allocation N is allocated to the first arm. The fluid dynamics for the β-EB-TCB algorithm (see [16] ) can be constructed similarly to that of the Anchored Top Two algorithm, by replacing the anchor function g(µ, N ) with the β-anchor function g(N ; β) in Section 4. First we fix some I ≥ 0 and N 1 ≥ N 1,2 . Note that for every a ∈ B, as N a increases from0 to ∞, N 1 d(µ 1 , x 1,a ) + N a d(µ a , x 1,a ) increases monotonically from 0 to N 1 d(µ 1 , µ a ). Since N 1 ≥ N 1,2 ≥ I d(µ1,µa) , we have N 1 d(µ 1 , µ a ) ≥ I.This implies, for a given N 1 , there is a unique value of N a for which N 1 d(µ 1 , x 1,a ) + N a d(µ a , x 1,a ) = I. We call this value N a (N 1 ) for every a ∈ B.Observe that N 1 → N a (N 1 ) is a strictly decreasing function of N 1 , and if N 1 = N 1,2 , then there exists an a ∈ B for whichN a (N 1,2 ) = ∞. On the other hand, if N 1 → ∞, N a (N 1 ) → I d(µa,µ1) for every a ∈ B.For every N 1 , we consider the functionh(N 1 ; β) = β - N 1 N 1 + a∈B N a (N 1 ) + a∈B c N a .Note that h(N 1 ; β) is the value of g(N ; β), when the tuple N has N a = N a (N 1 ) for every a ∈ B.Note that N 1 → h(N 1 ; β) is strictly decreasing for N 1 ≥ N 1,2 . Moreover, as N 1 → ∞, h(N 1 ; β) → β -1 < 0.In the rest of the argument, we show that h(max{N 1,1 , N 1,2 }; β) ≥ 0. After we prove this, we can find a unique N 1 for which h(N 1 ; β) = 0. Using this, we take N a = N a (N 1 ) for every a ∈ B to obtain our unique tuple N B . Now we consider two cases.Case 1:If N 1,1 ≥ N 1,2 , then at N 1 = N 1,1 , N 1,1 = β a∈B c N a ≤ β(N 1,1 + a∈[K]/{1} N a ).As a result,N 1,1 N 1,1 + a∈B c N a + a∈B N a (N 1,1 ) ≤ β, which implies h(N 1,1 ; β) ≥ 0. Case 2: If N 1,2 ≥ N 1,1, then, as we argued before, there exists an a ∈ B for whichN a (N 1,2 ) = ∞. As a result, N 1,2 N 1,2 + a∈B c N a + a∈B N a (N 1,2 ) = 0 implying h(N 1,2 ; β) = β > 0.Proposition E.2 stated below is crucial for constructing the fluid dynamics of the β-EB-TCB policy and is analogous to Proposition 2.1 used for constructing the fluid dynamics of the anchored top-two algorithm.Proposition E.2. For every non-emptyB ⊆ [K]/{1}, tuple N B c = (N a ∈ R ≥0 : a ∈ B c), and With the above modification, if we can find a constant γ > 0 such that,N ≥ 1 1-β a∈B c N a ,1 T |B|+1 ∂ Φ B ∂N B -1 ∂ Φ B∂I ≤ -γ < 0 for every tuple in Z B , then statements 2 and 3 of Lemma C.1 also hold true for this modified Φ B . As a result, Proposition E.2 follows using Lemma E.4 by the same argument used for proving Proposition 2.1 using Theorem D.1.In the rest of the proof we argue the existence of such a constant γ > 0.Let v = (v a : a ∈ B) ∈ R |B|+1 be the solution to the system ∂ Φ B ∂N B v = ∂ Φ B ∂I .We have∂Φ1 ∂N B v = ∂Φ1 ∂I , and N 1 = β a∈[K]N a , which after some algebraic manipulation implies,EQUATION(33) further implies,1 T |B|+1 v = |B|+1 i=1 v i = v 1 β .Therefore proving that v 1 is upper bounded by a negative constant is sufficient for proving the desired result.For every a ∈ B, we haveEQUATIONwhere x 1,a = N1µ1+Naµa. We use d 1,a and d a,a , respectively, to denote d(µ 1 , x 1,a ) and d(µ a , x 1,a ).For every a ∈ B, we can eliminate v a for (33) using (34). After this procedure, we get,EQUATIONSince .EQUATIONWe now show the fluid ODEs in the following proposition.Proposition E.3 (Fluid ODEs for β-EB-TCB). Let us assume the algorithm starts from a state N (N 0 ) = (N 0 a : a ∈ [K]) with a∈[K] N 0 a = N 0 , N 0 1 = βN 0 and N 0 > 0. Let B ⊆ [K]/{1}2. The index I B (N ) of the arms in B evolves by the following ODE,EQUATION)3. There exists a constant c > 0 such that, I ′ B ≥ c. On the other hand, indexes of the arms in B c remains upper bounded by N 0 a d(µ a , µ 1 ).Proof. Statement 1: N ′ 1 = β follows directly from the fact that g β = 0. By definition of B, we haveEQUATIONfor every a, b ∈ [K]. Taking derivative on both sides, we get,N ′ 1 d 1,a + N ′ a d a,a = N ′ 1 d 1,b + N ′ b d b,b ,which implies,EQUATIONUsing (38), we haved 1,b -d 1,a = N a d a,a -N b d b,b N 1 .Using the above expression in (39), we get,N ′ a = N a d a,a -N b d b,b N 1 d a,a N ′ 1 + d b,b d a,a N ′ b .Since N ′ 1 = β and N 1 = βN (which follows from g β = 0), the above equation implies,N ′ a = N a d a,a -N b d b,b N d a,a + d b,b d a,a N ′ b .Adding both sides for a ∈ B, we get,1 -β = a∈B N ′ a = a∈B N a d a,a -N b d b,b N d a,a + d b,b N ′ b a∈B d -1 a,a = a∈B N a N - N b N d b,b d -1 B + N ′ b d b,b d -1 B ,which impliesN ′ b = ((1 -β)N -a∈B N a )d B + N b d b,b N d b,b .Statement 2: We knowI ′ B = N ′ 1 d 1,b + N ′ b d b,b for every b ∈ B.Putting in the derivatives from (36), we obtain, Note that N 1 = βN . As a result, using (6), d a,a = Θ(1) for every a ∈ [K]/{1}. This implies, we can find a constant c 1 > 0 such that d B ≥ c 1 . On the other hand, using (12), we have,I ′ B = βd 1,b + 1 -β -a∈B N a N d B + N b d b,b N = 1 -β -a∈B N a N d B + βN d 1,b + N b d b,b N = 1 -β -a∈B N a N d B + I B N . (since N 1 =I B = Θ N 1 N a N 1 + N afor every a ∈ B. Since N 1 = βN and N a ≤ N , we haveI B = Θ(N a ).Adding for all a ∈ B, we get I B = Θ( a∈B N a ). Therefore, I B ≥ c 2 a∈B N a , for some constant c 2 > 0.Now using (37),I ′ B = 1 -β -a∈B N a N d B + I B N ≥ c 1 × 1 -β -a∈B N a N + c 2 × a∈B N a N ≥ min{c 1 , c 2 } × (1 -β).Taking c = min{c 1 , c 2 } > 0, we have the desired result.a ∈ B c , note that x 1,a = arg min x∈[µa,µ1] N 1 d(µ 1 , x) + N 0 a d(µ a , x) and I a = N 1 d(µ 1 , x 1,a ) + N 0 a d(µ a , x 1,a). As a result, putting x = µ 1 , we have I a ≤ N 0 a d(µ a , µ 1 ).Reaching β-optimal proportions: By statement 3 of Proposition E.3, the indexes of the arms in B increase at a linear rate, whereas the indexes of the arms in B c stay bounded above by a constant.As a result, by some finite time, I B crosses the index of some arm in a ∈ B c , after which B gets updated to B ∪ {a}. The same process then continues with the updated B. In this way, eventually B = [K]/{1} and the fluid dynamics reaches the β-optimal proportion ω ⋆ (β) = (ω ⋆ a (β) : a ∈ [K]) (β-optimal proportion is the solution to the max-min problem (1) with the added constraint ω 1 = β) where,N 1 N = ω ⋆ 1 (β) = β and N a N = ω ⋆ a (β) for every a ∈ [K]/{1}.Applying the same argument as used to bound the time to reach optimal proportions in Section 4, if the fluid dynamics start at some time N 0 with state N (N 0 ) = (N a (N 0 ) : a ∈ [K]), then it reaches stability by a time atmostN 0 min a∈[K] ω ⋆ a (β) .In the fluid dynamics described in Theorem 4.1, once the indexes meet thereafter they move up together by construction. It turns out that I ′ B (N ) is positive. Below we give a heuristic argument that in our fluid dynamics, once a set of smallest indexes that are equal, increase and catch up with another index, their union then remains equal and increases together with N . This argument provides important insights which help us later to prove that after after a random time of finite expectation, if our algorithm picks a suboptimal arm, then it picks that arm again in a periodic manner, which helps us prove closeness of indexes w.r.t. the algorithmic allocations (see Lemma 5.1). Differentiating g = 0 with respect to N , we see that, Consider the probability vector (p a : a ∈ [K]/{1}) where,EQUATIONp a = f (µ, a, N ) Na∆a (N1+Na) 2 b̸ =1 f (µ, b, N ) N b ∆ b (N1+N b ) 2 .Note that p a > 0 for every a ∈ [K]/{1}. We have from (40) thatN ′ 1 N 1 = a∈C N ′ a N a p a (41) Letting b = arg max a∈C N ′ a (N )Na(N ) (where N ′ a (N ) is the derivative in (3) of Theorem 4.1, upon putting B = C), we haveEQUATIONwhere the strict inequality in (1) follows from the fact that D = B ∪ {b} -C ̸ = ∅, causing a∈C p a < 1. We now argue that D must be empty. Suppose instead that D ̸ = ∅ and a ∈ D. Because all indexes in B are equal at time N , we have,N 1 d(µ 1 , x 1,a ) + N a d(µ a , x 1,a ) = N 1 d(µ 1 , x 1,b ) + N b d(µ b , x 1,b ) at N. Observe that for any arm d ∈ [K]/{1}, derivative of its index with respect to N equals N ′ 1 d(µ 1 , x 1,d ) + N ′ d d(µ d , x 1,d ) (since, by definition of x 1,d , N 1 d 2 (µ 1 , x 1,d ) + N d d 2 (µ d , x 1,d ) = 0). Since arm a gets no sample in [N, N + ∆N ], we have N ′ a = 0, which implies I ′ a = N ′ 1 d(µ 1 , x 1,a ) in [N, N + ∆N ].EQUATIONWe now argue that N ′ 1 d(µ 1 , x 1,a ) is strictly less than (43) at N . As a result, if ∆N > 0 is picked sufficiently small, index of b, which is the minimum index, outruns index of a in [N, N + ∆N ].EQUATIONWe want show that this is strictly negative. We consider two cases, EQUATION)Since the two indexes are equal at this point, we haveN 1 (d(µ 1 , x 1,a ) -d(µ 1 , x 1,b )) = N b d(µ b , x 1,b ) -N a d(µ a , x 1,a ).Substituting this in (45), the latter equalsN ′ b • 1 N b (N b d(µ b , x 1,b ) -N a d(µ a , x 1,a )) -d(µ b , x 1,b ) ≤ -N ′ b • N a N b d(µ a , x 1,a ) < 0.We thus have our contradiction. Therefore, indexes of the arms in B ∪ {b} move together.We consider the situation where the algorithm picks some arm a ∈ [K]/{1} at iteration N and doesn't pick a for the next R(N ) ≥ 1 iterations. For better readability, we denote R(N ) using R. In the following argument, we try to bound R from above using N . We can prove that N j (N ) = Θ(N ) for every j ∈ [K] and N ≥ T good (see Remark G.1 in Appendix G.2). As a result, R is atmost O(N ) for N ≥ T good . Below, we improve the upper bound to O(N 1-3α/8 ) by a refined analysis.Let us define ∆ N j (N, t) = N j (N + t) -N j (N ) for every j ∈ [K] and N, t ≥ 1. By our choice of T good , we have |g(µ,N (N ))| = O(N -3α/8 ) for N ≥ T good (see Remark G.1 in Appendix G.2).By applying mean value theorem on g(•) for N ≥ T good , we have,EQUATIONwhere (p j (N, t) : j ∈ [K]/{1}) is a probability distribution over the set [K]/{1}, depending on N and t (this distribution is not important to the discussion and is spelt out at Appendix G.6). Taking b t = arg max a̸ =1 ∆ Na(N,t) Na(N ) , and using (46), we obtain,EQUATIONObserve that ( 46) and (47), respectively, resembles (41) and (42) from Appendix F.1, except for a O(N 1-3α/8 ) term due to the noise in µ.Applying the mean value theorem, we can bound the difference between the empirical indexes of arm a and b t at iteration N + t by,EQUATION) Now if d( µ 1 , x 1,a ) -d( µ 1 , x 1,bt ) < 0, (48) implies, I a (N + t) -I bt (N + t) ≤ -∆ N bt (N, t) • d( µ bt , x 1,bt ) + O(N 1-3α/8 ).Otherwise, if d( µ 1 , x 1,a ) -d( µ 1 , x 1,bt ) ≥ 0, using (47) we haveEQUATIONNote that (48) resembles (45) in Appendix F.1. Since I a (N -1) ≤ I bt (N -1), we can prove using the mean value theorem that I a (N ) ≤ I bt (N ) + O(N 1-3α/8 ). Now expanding the empirical indexes, we getN 1 (N ) • d( µ 1 , x 1,a ) + N a (N ) • d( µ a , x 1,a ) ≤ N 1 (N ) • d( µ 1 , x 1,a ) + N bt (N ) • d( µ bt , x 1,bt ) + O(N 1-3α/8 ).Now dividing both sides by N bt (N ) and using the fact that N bt (N ) = Θ(N ), we haveN 1 (N ) N bt (N ) (d( µ 1 , x 1,a ) -d( µ 1 , x 1,bt )) -d( µ bt , x 1,bt ) ≤ - N a (N ) N bt (N ) d( µ a , x 1,a ) + O(N -3α/8 ).Using the above inequality in (49), we have,EQUATIONwhenever d( µ 1 , x 1,a ) -d( µ 1 , x 1,bt ) ≥ 0.Since N j (N ) = Θ(N ) and µ j (N ) ≈ µ j for all j ∈ [K] and N ≥ T good , the coefficient of ∆ N bt (N, t) in ( 49) and (50) are -Θ(1). As a result, we can find a constant C 3 > 0, such that, for t ≤ R and N ≥ T good ,EQUATIONApplying the mean value theorem and using the fact that t can be atmost O(N ), we can prove that, (51) implies,I a (N + t -1) -I bt (N + t -1) ≤ -C 3 ∆ N b (N, t) + O(N 1-3α/8 ).As a result, we have a constant C 4 > 0 such that,EQUATIONUsing (47), we can choose T good suitably, and find constants D 1 , D 2 > 0, such that, wheneverN ≥ T good , R ≥ D 1 N 1-3α/8 =⇒ ∆ N b R (N, R) ≥ D 2 R (see Lemma G.15 of Appendix G.6).We consider the case whereR ≥ max D 1 , 2C4 C3D2 × N 1-3α/8 . Since R ≥ D 1 N 1-3α/8 , we have ∆ N b R (N, R) ≥ D 2 R ≥ D 2 × 2C 4 C 3 D 2 N 1-3α/8 = 2C 4 C 3 N 1-3α/8 .For notational simplicity, we use b to denote b R . We consider the iteration N + S where arm b was selected for the last time before iteration N + R. Then by definition of b R and S, and using the above inequality, we have (using (53))EQUATION≤ -C 3 × 2C 4 C 3 N 1-3α/8 + C 4 N 1-3α/8 = -C 4 N 1-3α/8 .The above inequality implies, the AT2 algorithm pulls arm b at iteration N + S, even thoughI a (N + S -1) ≤ I b (N + S -1) -C 4 N 1-3α/8 ,which is contradicting the algorithm's description. Hence we must haveR ≤ max D 1 , 2C 4 C 3 D 2 × N 1-3α/8 = O(N 1-3α/8).In the following sections, unless otherwise stated, the proof of the mentioned results for AT2 (1) and IAT2 (2) algorithms follow a similar argument. Also, the constants introduced while stating the results in the following sections might be different for the two algorithms.While using the O(•), Θ(•) and Ω(•) notations, we imply that the hidden constants can depend on the choice of algorithm among AT2 and IAT2, instance µ, exploration factor α ∈ (0, 1) and no. of arms K, and are independent of the sample path.In this section, our agenda is to prove the convergence of the allocations of AT2 and IAT2 algorithms to the optimality conditions mentioned in Proposition 2.2. For ease of presentation we state the conditions uniquely characterizing the optimal proportion ω ⋆ below according to Proposition 2.2:EQUATIONa∈[K] ω ⋆ a = 1.Recall that for every a ∈ [K] and iteration N , ω a (N ) = Na(N ) N denotes the proportion of samples allocated by the algorithm to arm a. Let ω(N ) = ( ω a (N ) : a ∈ [K]).Recall the anchor function g(µ, N (•)) and index I a (•) for every alternative arm a ∈ [K]/{1}. In Section 5, we defined the normalized index H a (•) of every arm a ∈ [K]/{1} at iteration N as H a (N ) = 1 N I a (N ). In the next two sections, we prove,EQUATIONand maxEQUATIONa.s. in P µ as N → ∞. Moreover, we show that, after a random time of finite expectation, both the convergences in ( 55) and ( 56) happen at a uniform rate over all sample paths. We prove these convergence results in Proposition G. To prove Proposition G.1, G.2, and later Proposition G.4, we need to prove several technical properties related to exploration and the allocations made by the algorithms. The detailed technical results related to exploration are in Appendix G.4 and those related to the algorithmic allocations are in Appendix G.5. The arguments in Appendix G.1.1, G.1.2, and G.2 are self-contained, and we refer the reader to the related technical results whenever necessary. For ease of exposition, we provide below a brief summary of the statements proven in Appendix G.4 and G.5.We summarize below the results proven in Appendix G.4 and G.5 as events happening between the non-decreasing sequence of random times T 0 , T 1 , T 2 , T 3 , and T 4 , which are defined in Appendix G.5.1. T 0 def. = min{N ′ ≥ 1 | ∀N ≥ N ′ , max a∈[K] | µ a (N ) -µ a | ≤ ϵ(µ)N -3α/8}, where ϵ(µ) > 0 (defined in Appendix B), is a constant depending on the instance µ. By definition, we have ϵ(µ) ≤ 1 4 min a̸ =1 (µ 1 -µ a ). As a result, the first arm becomes the empirically best arm and stays that way forever after iteration T 0 . In Lemma G.7 of Appendix G.3, we prove that E µ [T 0 ] < ∞, which implies T 0 < ∞ a.s. in P µ .The following lemma bounds the fluctuation of g( µ, N ) around g(µ, N ) due to the noise in the estimate µ of µ. We need this lemma later for proving convergence of the anchor function g to zero in Proposition G.1.Lemma G.1 (Bounding the noise in g). For every N ≥ T 2 (where T 2 is the random time defined in Lemma G.11 and satisfiesE µ [T 2 ] < ∞), we have, |g( µ(N ), N (N )) -g(µ, N (N ))| = O(N -3α/8 ).Proof. Using mean value theorem for function of several variables, we have,|g( µ(N ), N (N )) -g(µ, N (N ))| ≤ K a=1 ∂g ∂µ a ( μ, N (N )) • | µ a (N ) -µ a |,where μa lies between µ a and µ a (N ) for every a ∈ [K].We definex1,a = N 1 (N )μ 1 + N a (N )μ a N 1 (N ) + N a (N ) , for every a ∈ [K]/{1}. Note that, ∂g ∂µ 1 ( μ, N (N )) = a̸ =1 d 1 (μ 1 , x1,a ) d(μ a , x1,a ) -f ( μ, a, N ) • N 1 N 1 + N a, and, By (6) , for N > T 2 , we have,EQUATIONd(μ a , x1,a ) = Θ (x 1,a -μa ) 2 = Θ N 1 (N ) 2 ( N 1 (N ) + N a (N )) 2 .By Corollary G.1 from Appendix G.5, we haveN 1 (N ) = Ω(N ) for N > T 2 . As a result, d(μ a , x1,a ) = Θ(1) for N > T 2 .Moreover, for N > T 2 , we have: 6)). As a result, for N > T 2 , all the partial derivatives in (57) are O(1). Therefore, for N > T 2 ,EQUATIONEQUATIONand hence completing the proof.Halting of exploration: By Lemma G.13, for N ≥ T 4 , every arm a ∈ [K] has N a (N ) = Θ(N ).As a result, we can find a constant λ ∈ (0, 1) such that N a (N ) ≥ λN for every a ∈ [K] and N ≥ T 4 . We choose M 3 large enough such that, for every N ≥ M 3 , λ(N -1) > N α . Then we have min a∈[K]/{1} N a (N -1) > N α for every N ≥ max{M 3 , T 4 + 1}. As a result, the algorithm doesn't do any exploration after iteration max{M 3 , T 4 + 1}. With this, we define the following random time, Definition G.1. We define T 5 = max{M 3 , T 4 + 1}.Note that E µ [T 5 ] < ∞, since, E µ [T 4 ] < ∞.We restate Proposition G.1 below,There exists constants M 4 ≥ 1 and C > 0 independent of the sample paths, such that, if T 6 denotes the iteration at which g( µ(•), N (•)) crosses the value zero after iteration max{M 4 , T 5 }, then for N ≥ T 6 we have,EQUATION)Moreover, the random timeT 6 satisfies E µ [T 6 ] < ∞.Proof. We prove the proposition via an inductive argument consisting of two main steps, 1. Initialization: We start with a choice of the constants C > 0 and M 4 ≥ 1 and show that g(µ, N (•)) satisfies ( 59) at iteration T 6 .Lemma G.2 is a detailed version of Lemma 5.1 mentioned in Section 5, and is essential for proving closeness of the indexes under the allocations made by AT2 and IAT2 algorithms. Recall that T 6 is the random time defined in Proposition G.1 and satisfies E µ [T 6 ] < ∞. Lemma G.2. For both AT2 and IAT2 algorithms, there exists constants M 5 ≥ 1 and C 1 > 0 independent of the sample paths, such that, for every N ≥ max{M 5 , T 6 }, if the algorithm picks an arm a ∈ [K]/{1} at iteration N , then it again picks arm a within the next ⌈C 1 N 1-3α/8 ⌉ iterations.Proof of Lemma G.2 is in Appendix G.6, and requires proving several technical lemmas. Some of those supporting lemmas involve arguments similar to the ones used for proving closeness of the indexes while the algorithm operates under an idealized fluid model (discussed in Section 4). In the rest of this section, we use Lemma G.2 to prove closeness of indexes for alternative arms in Proposition G.2. Definition G.2. We define the random time T 7 = max{M 5 , T 6 }.Note that Proof. Proof of this lemma uses mean value theorem. For any arm a ∈ [K]/{1}, upon expanding the indexes,E µ [T 7 ] < ∞, since E µ [T 6 ] < ∞. Definition G.EQUATIONwhere N 1 , N a , µ 1 , µ a , and x 1,a are evaluated at N . Since N 1 , N a ≤ N , the difference (64) is bounded above by,|I a (N ) -I a (N )| ≤ N • (|d( µ 1 , x 1,a ) -d(µ 1 , x 1,a )| + |d( µ a , x 1,a ) -d(µ a , x 1,a )|) .Now considering the first term in the RHS, and applying mean value theorem, we get|d( µ 1 , x 1,a ) -d(µ 1 , x 1,a )| = d 1 (μ 1 , x1,a ) + d 2 (μ 1 , x1,a ) • N 1 N 1 + N a • | µ 1 -µ 1 | + d 2 (μ 1 , x1,a ) • N a N 1 + N a • | µ a -µ a |,where μ1 , μa , respectively, lie between µ 1 , µ 1 , and µ a , µ a , and x1,a = N1 μ1+ Na μa N1+ Na. Using ( 7) and ( 8), all the partial derivatives in the above upper bound are O(1) for N ≥ T 0 . Therefore,EQUATION)Following a similar procedure, we can argue using ( 7) and ( 8), that the partial derivatives of d( µ j , x 1,j ) with respect to µ 1 and µ j are O(1) in magnitude. As a result, using the mean value theorem,EQUATIONTherefore, we have,|I a (N ) -I a (N )| = O(N 1-3α/8 ),for N ≥ T 0 and completing the proof.Proof of Proposition G.2:We have E µ [T 7,M ] ≤ M + E µ [T 7 ] < ∞. By Lemma G.13, N a (N ) = Θ(N ) for N ≥ T 7,M .Hence, by the definition of T 8,M , there exists a constant C ′ > 0 independent of M , such that, for everyM ≥ 1, T 8,M ≤ C ′ T 7,M . As a result, E µ [T 8,M ] ≤ C ′ E µ [T 7,M ] < ∞.Note that T 7,1 = T 7 . Also, for everyM ≥ 1, T 8,M ≥ T 8,1 = T 8 (T 8 is defined in Definition G.4).It is sufficient to prove the proposition for every N ≥ T 8 .We now argue for the algorithms AT2 and IAT2 separately. O (N + τ a,b (N )) 1-3α/8 = O N + O(N 1-3α/8 ) 1-3α/8 = O(N 1-3α/8 ).Therefore,|I a (N )-I b (N )| ≤ |I a (N + τ a,b (N )) -I a (N )| + |I b (N + τ a,b (N )) -I b (N )| + O(N 1-3α/8 ). By Lemma G.3, we know |I a (N ) -I b (N )| ≤ |I a (N ) -I b (N )| + O(N 1-3α/8). Therefore, the above inequality implies,EQUATION)Using mean value theorem, for j ∈ {a, b}, we have,EQUATIONwhereNi ∈ N i (N ), N i (N + τ a,b (N )) for i = 1, a, b.We know,∂I j ∂N 1 ( N1 , Nj ) = d(µ 1 , x1,j ) and ∂I j ∂N j ( N1 , Nj ) = d(µ j , x1,j ),where x1,j = N1µ1+ Nj µj N1+ Nj. Note that both the partial derivatives above are bounded from above by max{d(µ 1 , µ a ), d(µ a , µ 1 )}, and therefore O(1). As a result, since τ a,b (N ) = O(N 1-3α/8 ), we have,EQUATIONUsing ( 69) in (67), we get|I a (N ) -I b (N )| = O(N 1-3α/8), for N ≥ T 8 .IAT2: First we define the modified empirical index of every alternative arm a ∈ [K]/{1} using the notationI (m) a (N ) as, I (m) a (N ) = I a (N ) + log( N a (N )).We define the time τ Now N + τ (m)a,b (N ) must be earlier than the iteration after N by which the algorithm has picked both a and b atleast once. Using the same argument as AT2, by Lemma G.2, we have τ(m) a,b (N ) = O(N 1-3α/8). Also, following the same steps as AT2, by replacing the empirical index I with the modified empirical index I (m) for every alternative arm, we obtain,|I a (N ) -I b (N )| ≤ |I a (N + τ (m) a,b (N )) -I a (N )| + |I b (N + τ (m) a,b (N )) -I b (N )| + O(N 1-3α/8 ).Using the mean value theorem, since the parital derivatives of I a and I b with respect to N 1 , N a and N b are O(1), we have|I j (N + τ (m) a,b (N )) -I j (N )| ≤ O τ (m) a,b (N ) = O(N 1-3α/8 ) for j = a, b.From the last two observations, we conclude|I a (N ) -I b (N )| ≤ O(N 1-3α/8 ) for N ≥ T 8 .In this appendix we prove a slightly detailed version of Proposition 3.1 from Section 3. In Proposition 3.1, we argue that the proportion of samples allocated by the algorithm converges to the optimal proportions for the instance, a.s. in P µ , as the no. of samples grows to ∞.For every M ≥ 1, we use T 7,M and T 8,M as defined in Definition G.3 in Appendix G.1.2. Recall that T 7 = T 7,1 and T 8 = T 8,1 . By Proposition G.3, we have E µ [T 8,M ] < ∞, and T 8,M ≥ T 8 for every M ≥ 1.Recall that ω ⋆ is the unique optimal allocation according to Proposition 2.2, and ω(N ) = ( ω a (N ) :a ∈ [K]) with ω a (N ) = Na(N ) Nis the algorithms allocation at iteration N . We now state a slightly detailed version of Proposition 3.1 from Section 3, Proposition G.4. There exists constants C 1 > 0 and M 6 ≥ 1 depending on µ, α, and K such that, for every N ≥ T 8,M6 and a ∈ [K], we have| ω a (N ) -ω ⋆ a | ≤ C 1 N -3α/8 and | µ a (N ) -µ a | ≤ ϵ(µ)N -3α/8 ,where ϵ(µ) is a constant depending only on µ and defined in Appendix B.Detailed proof of Proposition G.4 is in Appendix G.2.2 and relies on using IFT.Below we define the random times T good and T stable , which are mentioned in the statements of Proposition 3.1, 5.1, and Lemma 5.1 from the main body of the paper. Definition G.5 (T stable and T good ). We define T good = T 7,M6 and T stable = T 8,M6 , where Before proving Proposition G.4 in Appendix G.2.2, we find a tighter upper bound on the time to reach optimal proportion T stable in the following Appendix G.2.1. While doing this, we identify a similarity between the time to reach stabilty in fluid dynamics and that for the algorithm.M 6 ≥ 1 is introduced in Proposition G.Lemma G.4 gives an upper bound on the time to reach stability for the algorithmic allocations. We define ω ⋆ min = min a∈[K]/{1} ω ⋆ a .According to the discussion in Section 4, if the fluid dynamics has state N (T good ) at time T good , then it hits all the indexes and reaches stability by a time atmostT good ω ⋆ min .In Lemma G.4, we argue that, the algorithm also approximately reaches the optimal proportion ω ⋆ by atmost ≈T good ω ⋆ min iterations.Lemma G.4. For every M ≥ M 6 (M 6 is a constant defined in the statement of Proposition G.4),T 8,M ≤ T 7,M + 1 ω ⋆ min -C 1 M -3α/8 , which implies T stable ≤ T good + 1 ω ⋆ min -C 1 M -3α/8 6.Moreover, we have lim supM →∞ T 8,M T 7,M ≤ 1 ω ⋆ min a.s. in P µ .Proof. From Proposition G.4, it follows that, for every M ≥ M 6 and N ≥ T 8,M ≥ T 8,M6 , we have,EQUATIONSince T 8,M is the first iteration after T 7,M by which every alternative arm has been picked atleast once, we have some arm a ∈ [K]/{1} such that,N a (T 8,M ) = N a (T 7,M ) + 1 ≤ T 7,M + 1.Now by (70), we haveN a (T 8,M ) ≥ (ω ⋆ a -C 1 T -3α/8 8,M )T 8,M ≥ (ω ⋆ min -C 1 M -3α/8 )T 8,M .Combining the last two observation, we have,T 8,M ≤ T 7,M + 1 ω ⋆ min -C 1 M -3α/8 a.s. in P µ for every M ≥ M 6 . Since T 8,M , T 7,M → ∞ as M → ∞ a.s. in P µ , we have, lim sup M →∞ T 8,M T 7,M ≤ 1 ω ⋆ min a.s. in P µ .By Proposition G.1 and G.3, there exists a constant C > 0 independent of the sample paths, such thatω(N ) = ( ω a (N )) a∈[K] satisfies, |g(µ, ω(N ))| = a∈[K]/{1} d(µ 1 , x 1,a (N )) d(µ a , x 1,a (N )) -1 ≤ CN -3α/8, andEQUATIONfor all N ≥ T 8 a.s. in P µ .Proof of Proposition G.4 relies on using the implicit function theorem. Before proving the proposition, we describe below the framework over which we apply the implicit function theorem. We define the following functions,EQUATIONΨ K+1 (ω) = a∈[K] ω a -1, where ω = (ω a ) a∈[K] ∈ R K ≥0 , η = (η a ) a∈[K] ∈ R K , I ∈ R, and for every a ∈ [K]/{1}, x 1,a (ω 1 , ω a ) = ω1µ1+ωaµa ω1+ωa and W a (ω 1 , ω a ) = ω 1 d(µ 1 , x 1,a (ω 1 , ω a )) + ω a d(µ a , x 1,a (ω 1 , ω a )).Using the functions defined above, we define the vector valued function Ψ (ω, I, η) as follows,Ψ (ω, I, η) = ( Ψ 1 (ω, η), Ψ 2 (ω, I, η), Ψ 3 (ω, I, η), . . . , Ψ K (ω, I, η), Ψ K+1 (ω) ) . Ψ maps tuples of the form (ω, I, η) ∈ R K ≥0 × R × R K to R K+1 . Its easy to observe that for every ω = (ω a : a ∈ [K]) ∈ R K ≥0 satisfying a∈[K] ω a = 1, and I ∈ R, there is a unique η ∈ R K for which Ψ (ω, I, η) = 0 K+1 . We refer to the quantity max a∈[K] |η a | as the violation caused by the pair (ω, I) to the optimality conditions in (54). By (54), all the alternative arms in [K]/{1} have equal normalized index under the optimal allocation ω ⋆ . LetI ⋆ = W a (ω ⋆ 1 , ω ⋆ a ) for every a ∈ [K]/{1}. Then Proposition 2.2 implies (ω ⋆ , I ⋆ ) is the unique tuple satisfying Ψ (ω ⋆ , I ⋆ , 0 K ) = 0 K+1 .To prove Proposition G.4 we need the two technical lemmas: Lemma G.5 and G.6. Let us define∥x∥ ∞ = max a∈[K] |x a | for every x ∈ R K .Lemma G.5 shows that, the set of allocations satisfying the optimality conditions in (54) upto a maximum violation of r > 0 shrinks to ω ⋆ as r decreases to zero. In Lemma G.6, we use Lemma G.5 and IFT to argue that if the perturbation vector η satisfies ∥η∥ ∞ ≤ η max , where η max > 0 is a constant depending only on µ, then there is a unique pair (ω, I) satisfying Ψ (ω, I, η) = 0 K+1 . Moreover, the function mapping a perturbation vector η ∈ [-η max , η max ] K to the unique pair (ω, I) solving Ψ (ω, I, η) = 0 K+1 is Lipschitz continuous.It is now easy to see Proposition G.4 follows from Lemma G.5 and G. 6 . By (71), the violation caused by the algorithmic allocation ω(N ) to the optimality conditions in (54) converges to zero uniformly at a rate O(N -3α/8 ). We wait for sufficiently many iterations such that, the violation becomes smaller than η max . Then using Lipschitzness of the allocation as a function of perturbation (proven in Lemma G.6), we have∥ ω(N ) -ω ⋆ ∥ ∞ = O(N -3α/8).Lemma G.5. For every r ≥ 0, we define the quantity,EQUATION∃ η ∈ [-r, r] K such that Ψ (ω, I, η) = 0 K+1 .The following statements are true about the mapping r → dist(ω ⋆ , r),1. dist(ω ⋆ , 0) = 0, 2. dist(ω ⋆ , r) is non-decreasing in r, and 3. lim r→0 dist(ω ⋆ , r) = 0.Proof. Statement 1: Statement 1 follows directly from the fact that (ω ⋆ , I ⋆ ) is the unique tuple satisfying Ψ (ω ⋆ , I ⋆ , 0 K ) = 0 K+1 , as proven in Proposition 2.2.Statement 2: Follows directly from the definition of dist(ω ⋆ , r).Statement 3: By statement 2, lim r→0 dist(ω ⋆ , r) exists and is non-negative. We consider a contradiction to statement 3 and assume that lim r→0 dist(ω ⋆ , r) = d > 0.Since r → dist(ω ⋆ , r) is non-decreasing, we can construct a decreasing sequence {r n } n≥1 such that, for every n ≥ 1, r n > 0, dist(ω ⋆ , r n ) ≥ d, and lim n→∞ r n = 0. As a result, using the definition of dist(ω ⋆ , r), we have a sequence of tuplesEQUATIONlim inf n→∞ max {∥ω n -ω ⋆ ∥ ∞ , |I n -I ⋆ |} ≥ d.Since Ψ K+1 (ω n ) = 0 for every n ≥ 1, the whole sequence (ω n ) n≥1 lies in the set   (ω 1 , ω 2 , . . . , ω K ) ∈ R K ≥0 i∈[K] ω i = 1    ,which is compact with respect to the norm ∥•∥ ∞ .Let for every n ≥ 1 and a ∈ [K], ω a,n and η a,n be, respectively, the a-th component of the vectors ω n and η n . For every n ≥ 1 and a ∈ [K]/{1}, we haveI n = W a (ω 1,n , ω a,n ) -η a,n . Since W a (•, •) always lies in the interval [0, d(µ 1 , µ a ) + d(µ a , µ 1 )] and |η a,n | ≤ r n , we have -r n ≤ I n ≤ d(µ 1 , µ a ) + d(µ a , µ 1 ) + r n for every n ≥ 1.By our assumption, we already have r n → 0, which also implies, the sequence r n is bounded from above. As a result, I n is also bounded. Therefore, we can have a convergent subsequence{(ω n k , I n k )} k≥1 , with limits ω n k → ω ′ and I n k → I ′ in the ∥•∥ ∞ -norm.For every k ≥ 1, we have Ψ (ω n k , I n k , η n k ) = 0 K+1 . As a result, using the continuity of Ψ (•) with respect to its arguments, we have Ψ (ω ′ , I ′ , 0 K ) = 0 K+1 , implying ω ′ is an optimal allocation for the instance µ.Hence, our assumptionlim inf n→∞ max{∥ω n -ω ⋆ ∥ ∞ , |I n -I ⋆ |} ≥ d implies max{∥ω ′ - ω ⋆ ∥ ∞ , |I ′ -I ⋆ |} ≥ d > 0, which further implies ω ′ ̸ = ω ⋆ .As a result, the instance µ has two distinct optimal allocations ω ′ and ω ⋆ , which contradicts Proposition 2.2.Lemma G.6. There exists η max > 0 depending only on the instance µ, such that the following statements are true, 1. For every η ∈ [-η max , η max ] K , there exists a unique tuple (ω, I) ∈ R K ≥0 ×R which satisfies, Ψ (ω, I, η) = 0 K+1 . 2. For every η ∈ [-η max , η max ] K , we call the unique tuple mentioned in statement 1 as (ω(η), I(η)). Then the function(ω, I) : [-η max , η max ] K → R K ≥0 × Ris L-Lipschitz, for some L > 0 depending on the instance µ.Proof. By Proposition 2.2, we know that the optimal allocation ω ⋆ is the unique allocation satisfying,Ψ (ω ⋆ , I ⋆ , 0 K ) = 0 K+1for some I ⋆ > 0. Note that Ψ (ω, I, η) = Φ(ω, I, η, 1) for every tuple (ω, I, η), where Φ is the function defined in Appendix C. By statement 3 of Lemma C.1, the Jacobian ∂Ψ ∂(ω,I) of the function Ψ (ω, I, η) is invertible at the tuple (ω ⋆ , I ⋆ , 0 K ).Therefore, applying the Implicit function theorem, we can find δ 0 , δ 1 > 0, and continuously differentiable functions(ω(•), I(•)) : (-δ 0 , δ 0 ) K → R K ≥0 × R, such that, 1. ω(0 K ) = ω ⋆ , I(0 K ) = I ⋆ , and 2. for every η ∈ (-δ 0 , δ 0 ) K , (ω(η), I(η)) is the unique tuple in R K ≥0 × R to satisfy, max ∥ω(η) -ω ⋆ ∥ ∞ , |I(η) -I ⋆ | ≤ δ 1 and Ψ (ω(η), I(η), η) = 0 K+1 .By statement 3 of Lemma G.5, we can find aδ 2 > 0 such that, dist(ω ⋆ , r) < δ 1 for r ∈ [0, δ 2 ]. We define η max = min δ0 2 , δ 2 . By the definition of dist(ω ⋆ , •), for every η ∈ [-η max , η max ] K , if a tuple (ω, I) satisfies Ψ (ω, I, η) = 0 K+1 , then it also satisfies max{∥ω -ω ⋆ ∥ ∞ , |I -I ⋆ |} < δ 1 .On the other hand, by IFT, since η max < δ 0 , (ω(η), I(η)) is the only such tuple possible. Therefore, for every η ∈ [-η max , η max ] K , (ω(η), I(η)) is the unique element in R K ≥0 × R such that Ψ (ω(η), I(η), η) = 0 K+1 . This proves the first statement of Lemma G.6.Since ω(•), I(•) is continuously differentiable in (-δ 0 , δ 0 ) K , every component of this mapping must be L-Lipschitz for some L > 0 in -δ0 2 , δ0 the maximum of the ∥•∥ 1 -norm of the gradients of different components of (ω(•), I(•)) over the set -δ0 2 , δ0 2 K . Since the gradients are all continuous, their ∥•∥ 1 -norm must be bounded in a compact set like -δ0 2 , δ0 2 K , and hence L < ∞. Therefore, the second part of Lemma G.6 follows from our assumption η max ≤ δ0 2 .We now proceed on proving Proposition G.4.Proof of Proposition G.4: Recall that in Section 5, for every a ∈ [K]/{1}, we defined the normalized index asH a (N ) = Ia(N ) N . Taking H(N ) = H 2 (N ) = I2(N ) N , let η(N ) be the unique η ∈ R K to satisfy, Ψ ( ω(N ), H(N ), η) = 0 K+1 . Note that for every a ∈ [K]/{1}, we have W a ( ω 1 (N ), ω a (N )) = H a (N ). As a result, by (71), we have ∥ η(N )∥ ∞ ≤ CN -3α/8 for all N ≥ T 8 . Now we pick M 6 ≥ 1 large enough, such that, CM -3α/8 6 < η max ,where η max is introduced in Lemma G.6. We define T stable = T 8,M6 . Note that T stable ≥ T 6 ≥ T 0 . As a result, by the definition of T 0 in Appendix G.3, we have max a∈[K] | µ a (N )-µ a | ≤ ϵ(µ)N -3α/8 for every N ≥ T stable . Now, by (71), for N ≥ T stable , the allocations ω(N ) satisfies, Ψ ( ω(N ), H(N ), η(N )) = 0 K+1 with ∥ η(N )∥ ∞ ≤ CN -3α/8 ≤ CM -3α/8 6 < η max .As a result, by Lemma G.6, we haveω a (N ) = ω a ( η(N )) for every a ∈ [K],andN ≥ T stable ,where ω a (•) is the a-th component of the vector valued function ω(•) introduced in Lemma G. 6 .By Lemma G.6, for every a∈ [K], ω a (•) is L-Lipschitz in [-η max , η max ] K equipped with ∥•∥ ∞ - norm.As a result, for N ≥ T stable , we have, maxa∈[K] | ω a (N ) -ω ⋆ a | = max a∈[K] |ω a ( η(N )) -ω a (0 K )| ≤ L∥ η(N ) -0 K ∥ ∞ = L∥ η(N )∥ ∞ ≤ LCN -3α/8 .Taking C 1 = LC, we have the desired result.In Section 5, we introduced the random time T 0 as,T 0 = min N ′ ≥ 1 ∀N ≥ N ′ , max a∈[K] | µ a (N ) -µ a | ≤ ϵ(µ)N -3α/8 ,where ϵ(µ) is a positive constant defined in Appendix B and depends only on the instance µ. Lemma G.7. The random time T 0 satisfies E µ [T 0 ] < ∞ and hence T 0 < ∞ a.s. in P µ .Proof. To avoid notational clutter, let P = P µ and ϵ = ϵ(µ). Then for any N ,P(T 0 = N + 1) ≤ P ∃a ∈ [K], | µ a (N ) -µ a | > ϵN -3α/8 ≤ a∈[K] P | µ a (N ) -µ a | > ϵN -3α/8 ≤ a∈[K] N t=(N α -C1)+ P |μ a,t -µ a | > ϵN -3α/8 ,where μa,t denotes the empirical mean of t i.i.d. samples drawn from the a-th arm, and the last step follows from statement 2 of Proposition G.5, which says N a (N ) ≥ N α -C 1 for some constant C 1 > 0.Using Chernoff's bound (like in the proof of Lemma 19 of [11] ), we have,P |μ a,t -µ a | > ϵN -3α/8 ≤ P μa,t > µ a + ϵN -3α/8 + P μa,t < µ a -ϵN -3α/8 ≤ exp -t • d(µ a + ϵN -3α/8 , µ a ) + exp -t • d(µ a -ϵN -3α/8 , µ a ) ≤ 2 exp -t • min d(µ a + ϵN -3α/8 , µ a ), d(µ a -ϵN -3α/8 , µ a )Using ( 6), we have a constant C 2 > 0 depending on the instance µ and such that,min d(µ a + ϵN -3α/8 , µ a ), d(µ a -ϵN -3α/8 , µ a ) ≥ ϵ 2 C 2 N -3α 4 .Therefore, we have,P |μ a,t -µ a | > ϵN -3α/8 ≤ 2 exp -tϵ 2 C 2 N -3α 4 .Therefore,P(T 0 = N + 1) ≤ i∈[K] N t=(N α -C1)+ 2 exp -tϵ 2 C 2 N -3α 4 ≤ i∈[K] N t=N α -C1 2 exp -tϵ 2 C 2 N -3α 4 ≤ 2 i∈[K] exp -ϵ 2 C 2 (N α -C 1 )N -3α 4 • N t=N α -C1 exp -ϵ 2 C 2 N -3α 4 (t -N α + C 1 ) ≤ 2KN exp -ϵ 2 C 2 (N α -C 1 )N -3α 4 = 2KN exp(-Ω(N α 4 )),where the constant hidden in Ω(•) depends only on µ. Using the obtained upper bound,E[T 0 ] = P(T 0 = 1) + N ≥1(N + 1)P(T 0 = N + 1)EQUATION)).Note that the series on the RHS is convergent for any α ∈ (0, 1). Therefore E µ [T 0 ] < ∞.In the following discussion, the set of iterations in which the algorithm does exploration is defined as all iterations N where min a∈[K] N a (N -1) < N α (which is equivalent to having V N ̸ = ∅, where V N denotes the set of starved arms at iteration N , and is defined in Section 3). We define the epoch of exploration at some arbitrary iteration as follows, Definition G.6. If the algorithm does exploration at iteration N , the epoch of exploration at N is the maximum no. of consecutive iterations including N in which the algorithm has done exploration. More precisely, if N 1 and N 2 are, respectively, defined as,N 1 = max {t ≤ N | t -1 is not an exploration} and N 2 = min {t ≥ N | t + 1 is not an exploration} then the epoch of exploration at iteration N is N 2 -N 1 + 1.Proposition G.5. The following statements are true:1. For every iteration which is an exploration, the epoch of exploration at that iteration is upper bounded by a constant depending on K and α. We denote this constant using T epoch .2. There exists a constant C depending on K and α such that , over every sample path, we have mina∈[K] N a (N ) ≥ N α -C.As a result, N a (N ) = Ω(N α ) for every arm a ∈ [K].3. There exists a M depending on K and α such that, every epoch of exploration starting after iteration M has length atmost K, and every arm can get pulled atmost once in that epoch. We call the constant M as M explo .4. If an epoch of exploration starts from some N ≥ M explo , then the next epoch of exploration doesn't start before another Θ(N 1-α ) iterations.Let N ≥ M explo be such that, N is an exploration. Define the following sequence, N 0 = N , and for k ≥ 1,N k = min N > N k-1 N k is the begining of an epoch of exploration .Then N k = N +Ω(k 1/α ). In other words, for any N ≥ M explo , the k-th epoch of exploration after iteration N starts after N + Ω(k 1/α ) iterations.6. For any N ≥ M explo + T epoch + 1 and T ≥ 1, the no. of epochs of exploration intersecting with the set of iterations {N, N + 1, N + 2, . . . , N + T } is O(T α ).Proof. Statement 1: Let the algorithm does exploration at iteration N . We can always choose N in such a way that, iteration N -1 was not an exploration, by choosing N to be the iteration at which an epoch begins. If the epoch of exploration starting at iteration N continues till iteration N + t, i.e., the iterations N, N + 1, . . . , N + t are exploration, then,EQUATION≥ mina∈[K] N a (N -1) + t K ≥ min a∈[K] N a (N -2) + t K (2) ≥ (N -1) α + t K ,where (1) follows from the fact that, min a∈[N ] N a (•) increments by atleast 1 over every K consecutive iterations in an epoch of exploration, and (2) from the fact that iteration N -1 is not an exploration.From the above inequality, we have,t K ≤ (N + t) α -(N -1) α . Note that, N → (N + t) α -(N -1) α is decreasing in N . Hence RHS ≤ (1 + t) α ≤ 1 + t α ≤ 2t α (since t ≥ 1). Therefore, we have, t K ≤ 2t α implying t ≤ (2K) 1/(1-α) .Therefore every epoch of exploration is atmost (2K) N a (N ) ≥ mina∈[K] N a (N 1 -1) + N -N 1 + 1 K for every N ∈ [N 1 : N 2 ].Using this, we have,N α -min a∈[K] N a (N ) ≤ max N ∈[N1:N2] N α -min a∈[K] N a (N 1 -1) - N -N 1 + 1 K .Since iteration N 1 -1 is not an exploration, we havemin a∈[K] N a (N 1 -1) ≥ min a∈[K] N a (N 1 -2) ≥ (N 1 -1) α .Using this, the upper bound becomes,max N ∈[N1:N2] N α -(N 1 -1) α - N -N 1 + 1 K ≤ max N ∈[N1:N2] (N -N 1 + 1) α - N -N 1 + 1 K ≤ max z∈[0,Tepoch] (z + 1) α - 1 + z K = C,where C depends only on K and α.Hence we get, min N a (T + K -1) -mina∈[K] N a (N ) ≥ N α -C = Ω(N α ).a∈[K]N a (T -1) ≥ 1.Since iteration T -1 is not an exploration, we have N a (T -1) ≥ N a (T -2) ≥ (T -1) α . Similarly, since iteration T + K is an exploration, min a∈[K] N a (T + K -1) < (T + K) α . Using these two observations, we have,1 ≤ (T + K) α -(T -1) α ≤ (T -1) α × 1 + K + 1 T -1 α -1 ≤ α(K + 1)(T -1) -(1-α) .Therefore, T ≤ (α(K + 1)) 1/(1-α) + 1.Let M explo = (α(K + 1)) 1/(1-α) + 2. Then from the above argument, if T ≥ M explo , the epoch of exploration starting at T will last for at most K iterations.Let us assume that, the epoch begining from some T i ≥ M explo lasts till iteration T f . Therefore, we have, mina∈[K]N a (T f -1) < T α f and mina∈[K] N a (T i -2) ≥ (T i -1) α .Using this,min a∈[K] N a (T f -1) -min a∈[K] N a (T i -2) ≤ T α f -(T i -1) α ≤ α(T i -1) -(1-α) (T f -T i + 1).We argued earlier that T f -T i ≤ K. We also have,T i -1 ≥ M explo -1 ≥ (α(K + 1)) 1/(1-α) + 1.Using this observations, we get min a∈[K] N a (T f -1) -min a∈[K] N a (T i -2) ≤ α(K + 1) ((α(K + 1)) 1/(1-α) + 1) 1-α < 1. Since min a∈[K] N a (T f ) ≤ min a∈[K] N a (T f -1)+1 and min a∈[K] N a (T i -2) ≤ min a∈[K] N a (T i - 1), we obtain, min a∈[K] N a (T f ) -min a∈[K] N a (T i -1) < 2, implying min a∈[K] N a (T f ) -min a∈[K] N a (T i -1) ≤ 1,N a (N + T -1) -min a∈[K]N a (N -1) ≥ 1.Since iteration N -1 is not an exploration, we have,min a∈[K] N a (N -1) ≥ min a∈[K] N a (N -2) ≥ (N -1) α . Since iteration N + T is an exploration, we have min a∈[K] N a (N + T -1) < (N + T ) α .Using these in the above inequality, we obtain,1 ≤ (N + T ) α -(N -1) α ≤ α(N -1) -(1-α) (T + 1), which implies T ≥ 1 α (N -1) 1-α -1 = Θ(N 1-α ).Statement 5: Using statement 4, we can have a constant C 1 such that,N k ≥ N k-1 + C 1 N 1-α k-1 ,for k ≥ 1, where N 0 = 1. We now inductively argue that, there exists some constant C 2 independent of k and N such that, N k ≥ N + C 2 k 1/α for k ≥ 1.• For k = 1, we choose C 2 ≤ 1.• Now for some k ≥ 2, if N k-1 ≥ N + C 2 (k -1) 1/α , we have, N k ≥ N k-1 + C 1 N 1-α k-1 ≥ N + C 2 (k -1) 1/α + C 1 (N + C 2 (k -1) 1/α ) 1-α ≥ N + C 2 k 1/α + C 1 (N + C 2 (k -1) 1/α ) 1-α -C 2 (k 1/α -(k -1) 1/α ) ≥ N + C 2 k 1/α + C 1 (N + C 2 (k -1) 1/α ) 1-α - C 2 α k 1 α -1 . Upon choosing C 2 ≤ αC1 2 1 α -1 1/α, since we already have k ≥ 2, we obtainC 1 (N + C 2 (k -1) 1/α ) 1-α ≥ C 1 C 2 k 2 1/α 1-α = C -α 2 αC 1 2 1 α -1 C 2 α k 1/α ≥ C 2 α k 1/α . Therefore, N k ≥ N + C 2 k 1 α .Proof. Using (10) , for N ≥ T 1 , we have,EQUATIONWe now consider two situations separately, Case I: g µ(N ), N (N ) > 0: We know that, there is a constant D 1 > 0, such that,g µ(N + t), N (N + t) ≤ D 1 N + t N 1 (N + t) -1 2 -1,for every t ≥ 1. Now for t < U , the algorithm selects an alternative arm from [K]/{1} only while exploring. Therefore, using statement 6 of Proposition G.5, we have a constant c 1 > 0 such that, N 1 (N + t) ≥ t -c 1 t α . Hence,g µ(N + t), N (N + t) ≤ D 1 N + t t -c 1 t α -1 2 -1 = D 1 N + c 1 t α t -c 1 t α 2 -1 for t < U.Since g µ(N + U -1), N (N + U -1) ≥ 0, RHS of the above inequality is non-negative at t = U -1. After some algebraic manipulation, this implies,U -1 -c 1 (1 + D 1/2 1 )(U -1) α ≤ D 1/2 1 N,Since LHS of the above inequality is linear in U , we can find a constant C 11 such that U ≤ C 11 N .Case II: g µ(N ), N (N ) < 0: Using (72), we have a constant D 2 such that,g µ(N + t), N (N + t) ≥ D 2 N + t N 1 (N + t) -1 2 -1for all t ≥ 1. Now for t < U , the algorithm pulls arm 1 only for exploration. As a result, using statement 6 of Proposition G.5, we have, a constant c 1 > 0 such that N 1 (N + t) ≤ N + c 1 t α . Using this,g µ(N + t), N (N + t) ≥ D 2 N + t N + c 1 t α -1 2 -1 ≥ D 2 t -c 1 t α N + c 1 t α 2 -1,for t < U . Since g( µ(N + U -1), N (N + U -1)) ≤ 0, the RHS of the above inequality is not positive at t = U -1. After some algebraic manipulation, this implies,U -1 -c 1 (1 + D -1/2 2 )(U -1) α ≤ D -1/2 2 N.Again the LHS of the above inequality is linear in U . As a result, we can find a constant C 12 such that, U ≤ C 12 N .Lemma G.10. There exists constants γ 1 , γ 2 ∈ (0, 1) independent of the sample path, such that, for N ≥ T 1 , whenever g µ(N ), N (N ) and g µ(N + 1), N (N + 1) have opposite signs, we have, 1. N 1 (N ) ≥ γ 1 N , and2. max a∈[K]/{1} N a (N ) ≥ γ 2 N .Proof. For N ≥ T 1 , we have constants D 1 , D 2 > 0 such that,D 1 N N 1 (N ) -1 2 -1 ≤ g µ(N ), N (N ) ≤ D 2 N N 1 (N ) -1 2 -1We consider only the situation where g µ(N ), N (N ) ≥ 0 and g µ(N + 1), N (N + 1) ≤ 0.Extending this to the other case follows similar argument.From g( µ(N + 1), N (N + 1)) ≤ 0, we have,EQUATIONSince N 1 (N ) ≥ 1 (for exploration), we haveN 1 (N + 1) ≤ N 1 (N ) + 1 ≤ 2 N 1 (N ). Therefore, using (73) we get N 1 (N ) ≥ 1 2 (1 + D -1/2 1) -1 N and we can takeγ 1 = 1 2 (1 + D -1/2 1 ) -1 .Similarly from, g( µ(N ), N (N )) ≥ 0, we have,EQUATIONUsing (74), we have,EQUATION2 ) -1 N . This further impliesEQUATION2 ) -1 N.Hence we can takeEQUATION2 ) -1 . Lemma G.11. There exists constants M 1 ≥ 1, d max ∈ [1, ∞) and d min ∈ (0, 1] independent of the sample path, such that, if T 2 is the time at which g crosses zero after the iteration max{M 1 , T 1 }, then, for N > T 2 , we have:d min ≤ a̸ =1 d( µ 1 (N ), x 1,a (N )) d( µ a (N ), x 1,a (N )) ≤ d max .Moreover, we haveE µ [T 2 ] < ∞.Proof. Let,D( µ(N ), N (N )) = a̸ =1 d( µ 1 (N ), x 1,a (N )) d( µ a (N ), x 1,a (N )) .Also for every M ≥ 1, we define T 1,M = max{M, T 1 } and T 2,M as the iteration at which g crosses zero for the first time after the iteration T 1,M , i.e., Otherwise if g( µ(N ), N (N )) > 0 for some N > T 2,M , let T = max{ t ≤ N | g( µ(t), N (t)) ≤ 0 } i.e. the time before iteration N when g has crossed the level zero. As a result, T ≥ T 2,M (by definition of T 2,M ), and by Lemma G.10, N 1 (T ) ≥ γ 1 T for some γ 1 ∈ (0, 1). Let S = N -T . During iterations T +1, . . . , T +S, since g is positive, the algorithm pulls alternative arms in [K]/{1} only for exploration. As a result, using statement 6 of Proposition G.5, we haveN 1 (T + S) ≥ N 1 (T ) + S -c 1 S α ≥ γ 1 T + S -c 1 S αfor some c 1 > 0. Using (72), we have a constant D 2 > 0 such that,D( µ(T + S), N (T + S)) ≤ D 2 T + S γ 1 T + S -c 1 S α -1 2 = D 2 (1 -γ 1 )T + c 1 S α γ 1 T + S -c 1 S α 2 .We take M 11 = -2 γ1 min S≥0 (S -c 1 S α ). It is easy to observe that for T ≥ M 11 and S ≥ 0, the function of T, S in the RHS is bounded above. Therefore, we take,d max = max 1, max T ≥M11,S≥0 D 2 (1 -γ 1 )T + c 1 S α γ 1 T + S -c 1 S α 2 < ∞.Hence, if M ≥ M 11 , we have g( µ(N ), N (N )) ≤ d max for every N > T 2,M .Existence of d min : If g( µ(N ), N (N )) ≥ 0, we have 1 has the trivial lower bound. Otherwise, if g( µ(N ), N (N )) < 0, we define T = max{ t ≤ N | g( µ(t), N (t)) ≥ 0 } and S = N -T . As a result, T ≥ T 2,M (by definition of T 2,M ). By Lemma G.10, we have N 1 (T ) ≤ (1 -γ 2 )N for some γ 2 ∈ (0, 1). Also, the algorithm pulls the first arm only for exploration during the iterations T + 1, T + 2, . . . , T + S, since g is negative. Therefore, using statement 6 of Proposition G.5, we have, N 1 (T + S) ≤ N 1 (T ) + c 1 S α ≤ (1 -γ 2 )T + c 1 S α . By (72), we have D 1 > 0 such that,D( µ(T + S), N (T + S)) ≥ D 1 T + S (1 -γ 2 )T + c 1 S α -1 2 = D 1 γ 2 T + S -c 1 S α (1 -γ 2 )T + c 1 S α 2 .Let M 12 = -2 γ2 min S≥0 (S -c 1 S α ). The function of T, S in the RHS is bounded below by a positive constant for T ≥ M 12 and S ≥ 0. Let,d min = min 1, min T ≥M12, S≥0 D 1 γ 2 T + S -c 1 S α (1 -γ 2 )T + c 1 S α 2 > 0.Then for M ≥ M 12 , we have g( µ(N ), N (N )) ≥ d min > 0 for every N > T 2,M . Now, upon taking M 1 = max{M 11 , M 12 }, and T 2 = T 2,M1 , the lemma follows. By Lemma G.9, we have a constantC 1 > 0 such that, T 2 ≤ C 1 max{M 1 , T 1 }. As a result, E µ [T 2 ] ≤ C 1 (M 1 + E µ [T 1 ]) < ∞.Using a technique similar to the one used in the proof of Lemma G.10 using (72), Lemma G.11 implies the following corollary. We define the random time T 2 as the one introduced in Lemma G.11. Corollary G.1. There exists constants β 1 , β 2 ∈ (0, 1) independent of the sample paths, such that, for every N > T 2 , 1. N 1 (N ) ≥ β 1 N , and2. max a∈[K]/{1} N a (N ) ≥ β 2 N .Lemma G.12. There exists constants γ > 0 and M 2 ≥ 1 independent of the sample path, such that, for N > max{M 2 , T 2 } + 1, if the algorithm pulls some arm a ∈ [K]/{1}, then for every alternate arm b ∈ [K]/{1, a}, N b (N ) ≥ γ N a (N ).Proof. We consider two separate cases.Case I: Iteration N is an exploration: Then we have a constant C 1 (introduced in statement 2 of Proposition G.5) such that,EQUATIONWe also haveN a (N ) ≥ N α -C 1 . Now let M 2 ≥ 2 be chosen such that, M α 2 > 3C 1 + 2. As a result, for N ≥ max{M 2 , T 2 } we have, N a (N ) ≥ N α -C 1 ≥ 2(1 + C 1 ). This together with (75) implies, N b (N ) ≥ 1 2 N a (N ).Case II: Iteration N is not an exploration: We consider the AT2 (1) and IAT2 (2) algorithms separately.Case II.I AT2 Algorithm: If iteration N is not an exploration, we have, I a (N -1) ≤ I b (N -1). Using (11) , for N ≥ max{M 2 , T 2 }, we have constants C 2 and C 3 such that,EQUATIONAs a result, we have,EQUATION≤ 2C 3 β 1 C 2 N b (N -1) ≤ 2C 3 β 1 C 2 N b (N ),where, for (1), we first note that N > T 2 + 1. As a result, using Corollary (G.1), N 1 (N -1) ≥ β 1 (N -1) (β 1 ∈ (0, 1) is the constant introduced in Corollary G.1), and on the other hand N 1 (N -1) + N b (N -1) ≤ 2(N -1). Hence, we getEQUATION, we have the desired result for AT2 algorithm.Case II.II IAT2 Algorithm: In this case, we have,log( N a (N -1)) + I a (N -1) ≤ log( N b (N -1)) + I b (N -1).Using (11) , we have constants C 2 and C 3 such that,C 2 N 1 (N -1) • N a (N -1) N 1 (N -1) + N a (N -1) ≤ log( N a (N -1)) + I a (N -1) ≤ I b (N -1) + log( N b (N -1)) ≤ C 3 N 1 (N -1) • N b (N -1) N 1 (N -1) + N b (N -1) + 1 e N b (N -1).As a result, using the same arguments used for the AT2 algorithm in Case II.I, we can conclude,EQUATIONC2 C3 + 1 e -1, we have the desired result for IAT2 algorithm.Definition G.9. We define the random time T 3 = max{M 2 , T 2 } + 2, where M 2 is the constant introduced in Lemma G.12, and T 2 is the random time defined in Lemma G.11. Definition G.10. We define the random time T 4 as T 4 = 1 β2 (T 3 + 1), where β 2 ∈ (0, 1) is the constant introduced in Corollary G.1.E µ [T 3 ] < ∞, since E µ [T 2 ] < ∞. For the same reason, by Definition G.10, T 4 satisfies E µ [T 4 ] < ∞ since E µ [T 3 ] < ∞. Lemma G.13 (Sufficient sampling). For every N ≥ T 4 , we have N a (N ) = Θ(N ) for every a ∈ [K].Proof. For a = 1 and every N ≥ T 4 , we have N 1 (N ) = Θ(N ) by Corollary G.1.Otherwise for a ̸ = 1 and every N ≥ T 4 , we defineA ′ N = arg max b∈[K]/{1} N b (N ). By Corollary G.1, N A ′ N (N ) ≥ β 2 N ≥ β 2 T 4 = T 3 + 1. Therefore, arm A ′N must have been pulled by the algorithm somewhere between iterations T 3 and N . Let us define the time N ′ to be the last time before N when A ′ N was pulled. Then N ′ ≥ T 3 > max{M 2 , T 2 } + 1. As a result, using Lemma G.12, we have,N a (N ′ ) ≥ γ N A ′ N (N ′ ) (i) = γ N A ′ N (N ),where (i) follows by definition of N ′ . Since N ≥ N ′ , we have N a (N ) ≥ N a (N ′ ). As a result, we obtain, for every a ∈ [K]/{1} and N ≥ T 4 ,N a (N ) ≥ γ N A ′ N (N ) = γ max b∈[K]/{1} N b (N ) ≥ γβ 2 N,where β 2 ∈ (0, 1) is the constant mentioned in Corollary G.1. Hence we have N a (N ) = Ω(N ) for N ≥ T 4 and the lemma follows.In this appendix, we prove Lemma G.2 from Appendix G.1.2. For improved clarity, we reiterate Lemma G.2 from Appendix G.1.2.Statement of Lemma G.2. For both AT2 and IAT2 algorithms, there exists constants M 5 ≥ 1 and C 1 > 0 independent of the sample paths, such that for every N ≥ max{M 5 , T 6 }, if the algorithm picks an arm a ∈ [K]/{1} at iteration N , then it again picks arm a within the next ⌈C 1 N 1-3α/8 ⌉ iterations.For every arm a ∈ [K], iteration N ≥ 1 and R ≥ 1, we define the following quantities,EQUATIONτ (N, R) = max{ t ≤ N + R | A t = b(N, R) }.For proving Lemma G.2, we need the three technical lemmas: Lemma G.14, G.15 and G.16.Lemma G.14. For N ≥ T 6 (T 6 is the random time defined in the statement of Proposition G.1 and it satisfies E µ [T 6 ] < ∞), we have,EQUATIONProof. In the proof, for readability, we use b to denote b(N, R). Also, for every arm a ∈ [K], we use ∆ N a to denote ∆ N a (N, R).By Proposition G.1, we have a constant C > 0 independent of the sample paths, such that forN ≥ T 6 , g(µ, N (N + R)) -g(µ, N (N )) ≤ 2CN -3α/8 .Therefore, applying the mean value theorem, we have,∂g ∂N 1 (µ, N )∆ N 1 + a∈[K]/{1} ∂g ∂N a (µ, N )∆ N a ≤ 2CN -3α/8 , where N = ( Na ) a∈[K] , with Na ∈ N a (N ), N a (N + R) for every a ∈ [K].Now expanding the partial derivatives of g with respect to N a 's for a ∈ [K], we getEQUATIONwhere, f (µ, a, N ) were defined in (13) of Appendix B.Lettingpj = f (µ, j, N ) Nj ∆j ( N1+ Nj ) 2 a̸ =1 f (µ, a, N ) Na∆a ( N1+ Na) 2for every arm j ∈ [K]/{1}, we have,EQUATIONWe know from (14EQUATION. As a result,N -1 1   a̸ =1 f (µ, a, N ) Na ∆ a ( N1 + Na ) 2   -1 = Θ N 2 1 a∈[K]/{1} N 2 aBy Lemma G.13, we have Na ≥ N a = Θ(N ) and N1 ≤ N + R for N ≥ T 6 . As a result, we get,N -1 1   a̸ =1 f (µ, a, N) Na ∆ a ( N1 + Na ) 2   -1 = O (1 + RN -1 ) 2 .Putting this in (78), we obtain∆ N 1 N1 - a̸ =1 pa ∆ N a Na = O N -3α/8 (1 + RN -1 ) 2 , which further implies, ∆ N 1 N1 ≤ a̸ =1 pa ∆ N a Na + O N -3α/8 (1 + RN -1 ) 2 ≤ a̸ =1 pa ∆ N a N a + O N -3α/8 (1 + RN -1 ) 2 (since N a ≥ Na ). Let b = arg max a̸ =1 ∆ NaNa . The above inequality implies,∆ N 1 N1 ≤ ∆ N b N b + O N -3α/8 (1 + RN -1 ) 2 .Now multiplying both sides by N1 /∆ N b , we get,∆ N 1 ∆ N b ≤ N1 N b + O ∆ N b -1 N1 N -3α/8 (1 + RN -1 ) 2 ≤ N1 N b + O ∆ N b -1 N 1-3α/8 (1 + RN -1 ) 3 (since N1 ≤ N + R).(76) follows from the above inequality upon observing that, N1 ≤ N 1 + R and N b = Ω(N ) (by Lemma G.13).Lemma G.15. There exists constants M 51 ≥ 1, D 1 , D 2 > 0 independent of the sample paths such that, for N ≥ max{M 51 , T 6 }, we have ⌈D 1 N 1-3α/8 ⌉ < N , and for all R ∈{⌈D 1 N 1-3α/8 ⌉, ⌈D 1 N 1-3α/8 ⌉ + 1, . . . , N }, we have ∆ N b(N,R) (N, R) ≥ D 2 R.Proof. To simplify notation, we adopt b to denote b(N, R) and, for every arm j ∈ [K], we use ∆ N j to denote ∆ N j (N, R).By (76) of Lemma G.14, there exists a constant D 3 > 0 independent of the sample paths, such that, for all N ≥ T 6 and R ∈ {1, 2, . . . , N },∆ N 1 ≤ ∆ N b × N 1 N b + D 3 1 + ∆ N -1 b N 1-3α/8 (we have RN -1 ≤ 1) ≤ N 1 N b + D 3 ∆ N b + D 3 N 1-3α/8Since N 1 (N ) and N b (N ) are both Θ(N ) (by Lemma G.13), we have a constant D 4 > 0 such that,N1(N ) N b (N ) + D 3 ≤ D 4 for every N ≥ T 6 .Using this in the above inequality, we get,EQUATIONWe take D 1 = 2D 3 and M 51 ≥ 1 to be the smallest number such that, every N ≥ M 51 satisfiesEQUATION)By definition of b, we have,N a N b ∆ N b ≥ ∆ N a for every a ∈ [K]/{1}.Again, since N a (N ) = Θ(N ) for every a ∈ [K] (by Lemma G.13), there exists a constant D 5 > 0 independent of the sample paths such that,D 5 ∆ N b ≥ ∆ N a for every a ∈ [K]/{1, b}.As a result,R = a∈[K]/{1,b} ∆ N a + ∆ N 1 + ∆ N b ≤ (K -2)D 5 ∆ N b + D 4 ∆ N b + R 2 + ∆ N b (using (80)) ≤ (1 + (K -2)D 5 + D 4 )∆ N b + R 2 , =⇒ ∆ N b ≥ 1 2(1 + (K -2)D 5 + D 4 ) R. Now taking D 2 = 1 2(1+(K-2)D5+D4) > 0, we have the desired conclusion. Lemma G.16. For AT2 (1) and IAT2 (2) algorithms, there exists constants C 3 , C 4 > 0 independent of the sample paths, such that, for N ≥ T 6 and R ∈ {1, 2, . . . , N }, if the algorithm pulls some arm a ∈ [K]/{1} at iteration N and doesn't pull a for the next R iterations, then,EQUATIONEQUATIONwhere for every alternative arm j ∈ [K]/{1},I (m) j (N ) = I j (N ) + log( N j (N ))is the modified empirical index of that arm at iteration N Proof. For cleaner presentation, we use b to denote b(N, R). We also use µ j , x 1,j , ∆ N j and N j , respectively, to denote µ j (N ), x 1,j (N ), ∆ N j (N, R) and N j (N ) for every arm j ∈ [K], whenever it doesn't cause confusion. Using the multivariate mean value theorem, we have,EQUATIONwhere ∆ µ j = µ j (N + R) -µ j (N ) for j = 1, a, b, and ( N , μ) = ( N1 , Na , Nb , μ1 , μa , μb ) such that, for j = 1, a, b, μj lies between µ j (N ) and µ j (N + R), and Nj lies in N j (N ), N j (N + R) .Note that there is no contribution on the RHS in (83) due to N a , because N a (•) doesn't change during iterations N + 1, N + 2, . . . , N + R, owing to our assumption that the algorithm doesn't pull arm a during the mentioned iterations.First we consider the partial derivatives of S j,b with respect to µ 1 , µ j and µ b in (83). We have Therefore, the contribution in the RHS of (83) due to the noisiness in the empirical means µ 1 , µ a , µ b is bounded above by,EQUATIONEQUATIONwhere Using Lemma G.13, N j (N ) and N j (N + R) are both Θ(N ) for all j = 1, a, b and N ≥ T 6 , since R ≤ N . As a result, using ( 7), (8), we have,EQUATION∂ 2 S a,b ∂N j ∂N k (N ′ , µ ′ ) = O(N -1 )for every j, k ∈ {1, a, b}, and tuple  and µ ′ i lying between μi and µ i , for every i = 1, a, b.(N ′ , µ ′ ) = (N ′ 1 , N ′ a , N ′ b , µ ′ 1 , µ ′ a , µ ′ b ) having N ′ i ∈ N i (N ), N i (N + R)Therefore, applying the mean value theorem, we get,∂S a,b ∂N 1 ( N , μ) = d( µ 1 , x 1,a ) -d( µ 1 , x 1,b ) + O   j=1,a,b |μ j -µ j |   + O   N -1 j=1,b ∆ N j   = d( µ 1 , x 1,a ) -d( µ 1 , x 1,b ) + O N -3α/8 + RN -1 .Similarly, considering the partial derivative with respect to N b ,∂S a,b ∂N b ( N , μ) = -d( µ b , x 1,b ) + O N -3α/8 + RN -1 .Therefore, adding the contributions of the noise in ( µ j ) j=1,a,b , (92) can be further upper bounded by,EQUATIONNow, we find an upper bound to Sa,b ( N (N ), µ(N )). Since the algorithm pulls arm a and doesn't pull arm b at iteration N , we must haveI (m) a (N -1) ≤ I (m) b (N -1) = I (m) b (N ).Therefore,EQUATIONEQUATION= O(N 1-3α/8 ),where (1) follows from the fact that N a (N ) = Θ(N ) for N ≥ T 6 , and (2) follows using the arguments used while bounding I a (N ) -I a (N -1) in (86).Putting this in (93), we get,EQUATIONNow there can be two cases.Case I d( µ 1 , x 1,a ) -d( µ 1 , x 1,b ) < 0 : Then, using the same argument as was used for Case I of AT2 algorithm, we get (82).Case II d( µ 1 , x 1,a )-d( µ 1 , x 1,b ) ≥ 0 : Using (76) of Lemma G.12, the RHS in (95) is upper bounded by,∆ N b N 1 N b (d( µ 1 , x 1,a ) -d( µ 1 , x 1,b )) -d( µ b , x 1,b ) + O N 1-3α/8 + N -3α/8 + RN -1 R .Using (94), we haveI (m) a (N ) ≤ I (m) b (N ) + O N 1-3α/8 , which implies, I a (N ) ≤ I b (N ) + log N b N a + O(N 1-3α/8 ) (1) = I b (N ) + O(N 1-3α/8 ),where (1) follows from the fact that N a (N ) and N b (N ) are both Θ(N ), causing log Na(N ) N b (N ) = O(1) for N ≥ T 6 . Note that the above inequality is same as (90) obtained in Case II of AT2. Now (82) follows using exactly the same argument as in the Case II of AT2 after (90).For every a ∈ [K]/{1}, N ≥ T 6 and R ∈ {1, 2, . . . , N }, we have,EQUATIONwhere: + O N -3α/8 + RN -1 R ,where C 3 , C 5 > 0 are constants independent of the sample paths.Proof of Lemma G.2: We prove the proposition for the AT2 algorithm. The proof for IAT2 algorithm follows the exact same argument by replacing I with I (m) .In the proof, we argue via contradiction. We show that, there exists constants M 5 ≥ 1 and C 1 > 0 independent of the sample paths, such that for N ≥ max{M 5 , T 6 }, if the algorithm pulls some arm a ∈ [K]/{1} at iteration N and doesn't pull it for the next R(N ) def.= ⌈C 1 N 1-3α/8 ⌉ iterations, then at iteration τ (N, R(N )), the algorithm pulls arm b(N, R(N )), even though arm a has empirical index strictly less than that of arm b(N, R(N )).Using Corollary G.2, there exists constants C 3 , C 5 , C 6 > 0 independent of the sample paths, such that, for N ≥ T + C 5 R(N -3α/8 + RN -1 ).(100)We defineC 1 = max D 1 , 2C 4 D 2 C 3 + 1,where D 1 and D 2 are the constants introduced in Lemma G.15. Let M 52 ≥ 1 to be the smallest number such that, every N ≥ M 52 satisfies ⌈C 1 N 1-3α/8 ⌉ < N . Since EQUATION≤ -C 4 N 1-α/8 + C 5 (C 1 + 1)(C 1 + 2)N 1-3α/8 × N -3α/8 Now we make the following observations about t max,δ , 1. Note that N T ⋆ (µ) -C 2 N 1-3α/8 increases linearly in N and β(N, δ) is O(log log(N ) + log(1/δ)), for a fixed δ > 0. Hence, t max,δ is finite for every δ > 0.2. We have β(N, δ) ≥ log(1/δ) and N T ⋆ (µ) -C 2 N 1-3α/8 < N T ⋆ (µ) . As a result, t max,δ is atleast the iteration at which N T ⋆ (µ) exceeds log(1/δ), which is atleast T ⋆ (µ) log(1/δ). This implies t max,δ ≥ T ⋆ (µ) log(1/δ). As a result, t max,δ → ∞ as δ → 0. Since τ δ ≤ max{T stable , 1 + t max,δ }, we can find a constant C > 0 such that τ δ ≤ max T stable , T ⋆ (µ) log(1/δ) + C(log(1/δ)) 1-3α/8 . Hence Theorem 3.1 stands proved.We describe a natural extension of AT2 and IAT2 algorithms to bandit instances from a non-parametric family. We conduct experiments to compare the proposed algorithm with the existing ones. We consider the class of distributions having their supports contained in [0, 1], which we denote by F [0,1] . This is similar to the assumptions made in [16] . Some definitions are in order. We use µ(G) to denote the mean of distribution G ∈ F [0,1] .For every F ∈ F [0,1] and x ∈ [0, 1], we define KL + inf and KL - inf as: KL The lines with the markers in the figures represent the average number of samples generated before stopping, averaged over 4, 000 independent simulations, while the shaded regions denote 2 standard deviations around the mean. We also report the average sample complexity and the standard deviation of the average sample complexity for AT2, IAT2, TCB, and ITCB, across 4, 000 independent simulations.In both these simulations, we observe that AT2 and IAT2, respectively, have about 5% lower sample complexity compared to TCB and ITCB. In Figure 8 and Figure 9 , we plot the sample complexities of the three algorithms -AT2, 0.5-EB-TCB, and TCB -as a function of δ, for the Gaussian and Bernoulli bandits considered in Experiment 2 above. All the algorithms use the same forced exploration and stopping rules. We observe that AT2 consistently outperforms both the previously known algorithms, and the gap in performance increases as we reduce δ. Experiment 4 (SC as a function of number of arms). We plot the number of samples needed by the three algorithms, as a function of number of arms in the bandit instance. δ is set to 0.001 in this experiment.For scalability, in this experiment, we consider a simple Gaussian bandit (well-separated means) with all arms having a unit variance. Arm 1 is optimal with mean 10. To study the effect of number of arms on sample complexity, we choose all the other arms to be same with mean 8. Thus, the bandit instances have Gaussian arms with unit variance, and means µ = [10, 8, . . . ].As in the earlier experiments, for fair comparison, all the algorithms are implemented with the same forced exploration and stopping rules. Results are presented in Figure 10 . We observe that the sample complexity increases linearly with number of arms for the three algorithms. In this experiment, the performance of TCB and AT2 looks comparable, with TCB requiring slightly more number of samples. However, the gap in their performance is expected to increase for smaller values of δ. In this section, we provide a numerical evaluation of the impact of forced exploration on the performance of AT2 and IAT2. Our experiments suggest that unlike IAT2, AT2 needs forced exploration. On instances where the second and third best arms have equal means, AT2 might see some bad samples from the best arm in the beginning. As a result, without forced exploration, it will sample the second and the third best arms forever. However, we see that AT2 performs sufficient exploration for instances having all arms with different means. Note that similar observations were made in [16] for β-EB-TCB.Experiment 6: To see the above mentioned behavior of AT2, we study the performance of AT2 and IAT2 on the following two bandit instances. Intuitively, it might appear that forced exploration could significantly increase the sample complexity of AT2 and IAT2. However, in Figure 11 , we see that IAT2's performance remains unaffected and AT2 performs at least as well as IAT2 with moderate amount of forced exploration on the first instance, where the gap between the means is small.Figure 12 shows that without forced exploration, AT2's sample complexity blows up on the instance with equal sub-optimal arm means. We see that on this instance, IAT2 performs significantly better than AT2. Furthermore, IAT2's sample complexity remains almost unaffected with respect to the amount of forced exploration done. K equipped with ∥•∥ ∞ -norm. We can take L to be 


Decision: This is a very nice paper that I read in detail and decided to accept together with the strong recommendation from the reviewers. It is the first paper that provides a fully adaptive choice of the proportion $\beta$ in top two algorithms. This is an important advancement. Furthermore, the new techniques that involve the notion of anchor function and the use of the theory of ODEs and the implicit function theorem to demonstrate the asymptotic optimality of the proposed algorithm may pave the way for further theoretical advancements in the area of fixed-confidence BAI.

Reviews: review: paper_summary: paper_summary: The paper is about fixed confidence bandit best arm identification. The authors study the top-two family of algorithms. Those algorithms identify at each time step a leader and a challenger arm, and sample one of those two arms: typical top-two algorithms in the literature sample the leader with a fixed probability $\beta$ chosen in advance. A top-two algorithm that uses a fixed $\beta$ cannot have optimal expected sample complexity for all problems, since the optimal proportion of samples for the best arm might not be $\beta$. In order to derive an asymptotically optimal top-two algorithm, the authors introduce an adaptative choice of $\beta$, and study its dynamic through the study of a continuous time fluid dynamic.
strength_weakness: strength_weakness: - The analysis is very asymptotic. It uses that after a while, the forced exploration of steps 1 and 2 in the algorithm ensures that all means are well estimated. That implicitly requires that $\delta$ should be small enough that the stopping condition is not attained before that time. Most of the literature on top-two algorithms is also asymptotic so that is not very surprising, but there are also non-asymptotic results (for fixed $\beta$): see [Jourdan & Degenne, Non-asymptotic analysis of a ucb-based top two algorithm].

- the algorithm AT2 uses forced exploration, which could hurt in practice: if the parameter $\alpha$ is set too high, the algorithm will explore some bad arms too much. On the other hand if it is set too low, the algorithm can get stuck sampling sub-optimal arms. Indeed, if $\alpha$ is zero the algorithm is close EB-TC from [16] which can have horrible practical performance, and the new algorithms will likely get stuck in the same way: if there is one good arm and two bad arms with equal means but the good arm gets low empirical mean at the beginning, the algorithm will sample the two bad arms forever (see [16]). IAT2 should not suffer from the same issue, thanks to its added exploration mechanism.
I did not find the value of $\alpha$ used in the experiments and the effect of that parameter was not studied experimentally.

- The analysis is very involved and might be hard to reuse or extend in other contexts. In particular, it uses a lot the particular shape of the optimality conditions for the sampling proportions. It is not clear if the right properties to use the same kind of technique will hold in other settings like structured bandits. This is more an open problem than a weakness of the paper.

Remarks and typos:

- A remark about this review: the paper including the appendix is 75 pages long, hence I could not check every proof.

- An algorithm $\beta$-EB-TCB is mentionned repeatedly, supposedly coming from [16]. There is no algorihtm called $\beta$-EB-TCB in [16]. Is it $\beta$-EB-TC? Likewise, $\beta$-EB-ITCB does not exist in that paper: is it $\beta$-EB-TCI?
questions: questions: - The algorithm uses forced exploration to ensure that every arm is sampled some minimal amount (steps 1 and 2, lines 206 and 207). Suppose that instead, we use some variant of top-two without forced exploration, with the adaptive $\beta$ that you propose, and prove that it naturally explores (we prove a "sufficient exploration" lemma as in [16]]). That is not possible with AT2 without forced exploration unless all arms have different means since it uses greedy leader and challenger, but it could be possible with IAT2. Would the analysis still apply? Or is the forced exploration also used for something else in the analysis?

- The upper bound on the time needed to reach proportions close to the optimal proportions depends on the inverse of the minimal optimal proportion over the arms (line 262, line 321). That upper bound can be very large if the minimum is close to 0, which can happen if there is a very bad arm. Can this be avoided?
limitations: limitations: The limitations are adequately addressed.
paper_summary: paper_summary: This paper focuses on best arm identification (BAI) under the fixed confidence setting. It assumes the underlying distributions are from the single parameter exponential function. It discusses the problem of how to find the optimal $\beta$ for Top-Two type of algorithm for BAI, where $\beta$ denotes the probability of pulling the empirical best arm at each step. It proposes two algorithms, called Anchored Top-2 (AT2) algorithm and an improved version called Improved AT2 (IAT2) algorithm. It shows that both of the algorithms reaches the optimal sample complexity when $\delta \to 0$. A key idea the authors propose is to identift the underlying fluid dynamics using the ODEs tracked by the proposed algorithms. This idea helps to prove the convergence of the algorithms. It also does simulations to show the index values for each arm at different time steps for AT2 and compares the sample complexity of AT2 with other popular Top-Two algorithm.
strength_weakness: strength_weakness: 1. The paper is rather technical and lacks some intuitive explanations of different parts. It would be nice to include a picture to desribe the actual behavior of the paths captured by the ODEs if possible. Or just provide more intuitions for the steps of the algorithms.
2. The experiments lack some more explanations to discuss the meanings behind.
questions: questions: 1. possible typos: "There" -> "Their" in line 88?
2. What is $a$ in the equation at the end of page 3?
3. Why the threshold for function $g(\cdot)$ in the algorithm is 0? Is it possible or trivial to change to other thresholds?
4. Why the stopping condition is ignored as mention in line 249 for the fluid dynamics?
limitations: limitations: See weakness.
paper_summary: paper_summary: This paper considers the problem of identifying an optimal "top-2" algorithm for the best arm identification problem in the bandits framework. The question of how to allocate pulls between incumbents and challengers is considered. An algorithm for achieving the best balance is described.
strength_weakness: strength_weakness: I found the paper to be generally very hard to follow. The language is awkward in many places. I do not find that the introduction makes it clear how the paper's contributions are achieved. Explanations are very math-heavy and hard to follow and I find the theoretical results (e.g., Proposition 2.1) are not understandable. The paper also references many concepts without explaining them well (e.g., IFT, GLLR, ITCB). 

The presentation of this paper needs to be significantly improved before it is ready for publication.
questions: questions: If we were to pull both of the top-2 arms instead of randomizing between them, how different would the sample complexity be?
limitations: limitations: NA
paper_summary: paper_summary: The paper investigates the problem of fixed-confidence BAI in stochastic multi-armed bandits. Simply stated, the problem entails finding the best arm (the arm with the largest mean reward) as quickly as possible, subject to an upper bound on the error probability. There exist a plethora fo works that investigate this problem, derive problem instance-dependent lower bounds on the asymptotic growth rate of the expected stopping time, and devise algorithms that achieve the asymptotic lower bound; here, the asymptotics is one of vanishing error probabilities. One class of efficiently implementable algorithms for this problem that has gained significant attention in the recent years is that of top-2 sampling algorithms. The basic premise on which such algorithms function is to pull the empirical best arm at any given time with a certain constant probability, say $\beta$, and to pull the empirically second-best arm (or the challenger arm) with the remaining probability. Despite its elegance and ease of implementability, the aforementioned $\beta$-top-2 sampling algorithm an algorithm falls short of achieving the instance-dependent lower bound. The key to achieving the lower bound, as it turns out, is to set $\beta=\beta^*$, where $\beta^*$ depends on the underlying problem instance and is therefore unknown to the algorithm. While several attempts to learn the value of $\beta^*$ as part of the algorithm have taken place in the recent past, the current work accomplishes the same objective elegantly, using the theory of ODEs. Notably, the paper proposes an algorithm for BAI, and analyses the fluid dynamics (ODE) corresponding to a continuous version of the same. Implicit function theorem is used to demonstrate the existence and uniqueness of the solutions to the ODE, and to further demonstrate that the arm allocations under the algorithm closely follows the trajectory coming from the ODE. It is then argued that the limiting solution of the ODE (and hence the asymptotic arm allocations under the algorithm) matches with the optimum allocations corresponding to the underlying instance, thereby proving the asymptotic optimality of the proposed algorithm.
strength_weakness: strength_weakness: The writing of the paper can be slightly improved. While the authors have done a commendable job in explaining the intuition behind their detailed proofs, I have some minor suggestions that might possibly improve the readability of the paper.

1. In the paragraphs leading up to Proposition 2.1, the authors introduce the notation $x\_{1,a}=\dfrac{\omega\_1 \ x\_1 + \omega\_a \ x\_a}{\omega\_1 + \omega\_a}$. Shortly thereafter, the authors use the phrase "define $N\_{1,1}$ as the value of $N\_1$ at which $\sum\_{a \neq 1} \dfrac{d(\mu\_1, x\_{1,a})}{d(\mu\_1, x\_{1,a})}=1$ for a given allocation $\boldsymbol{N}\_{\bar{B}^c}$", without stating the (new) definition of $x\_{1,a}$. The actual definition of $x\_{1,a}$ only appears later, in the first part of Proposition 2.1. I suggest that the authors move the definition of $x\_{1,a}$ to an earlier paragraph if possible.

Some minor comments:

2. "alocation" in line 160 --> "allocation".

3. $f(\boldsymbol{\mu}, a, N)$ in line 291 --> $f(\boldsymbol{\mu}, a, \boldsymbol{N})$.
questions: questions: Can the authors explain what role the anchor function $g$ plays at a higher level. It seems almost unintuitive that this function, together with the empirical means and allocations, should dictate the sampling of the best empirical arm or challenger arm at any given time (items 3,4 in lines 208-211), in order to match with the optimal allocations in the long run. For a contextual comparison, in the TCB and ITCB algorithms of [21], the place of the anchor function is taken by the empirical problem complexity. Given that the empirical terms are expected to be close to their true values in the long run, the empirical problem complexity is likely to be close to the true complexity. It is then intuitive to expect that any sampling rule that is based on the empirical problem complexity, is likely to lead to sampling the arms according to the optimal allocation in the long run. 

Along these/similar lines, can the authors provide a high-level intuition for why looking at the anchor function and its long-term behaviour is pivotally connected to learning the optimal $\beta$ and thereby matching the arm selection frequencies with the optimal allocation?
limitations: limitations: NA.
paper_summary: paper_summary: This paper considers the top-2 algorithm for identifying the best arm in multi-armed bandits. The authors introduce a new approach for determining the optimal $\beta$ for sampling the empirical best and best challenger arms. This novel method relies on a function of allocations anchored at a threshold, which is simple in concept.
strength_weakness: strength_weakness: 1. One weakness of the paper is the use of the forced exploration stage in the AT2 algorithm (Line 1-2), which ensures that all the arm means are estimated with sufficient accuracy. It is not clear whether this is crucial for the effectiveness of the algorithm or simply for the ease of theoretical proof. Indeed, forced exploration might harm the empirical performance of BAI but significantly simplifies the asymptotic theoretical analysis.
2. The second weakness of the paper is that all the analyses are asymptotic, although I understand that achieving non-asymptotic results might be challenging for the top-2 algorithm.
questions: questions: 1. Line 634-637: What about a Bernoulli distribution with mean zero?
2. Line 144: Another widely used definition for a $\delta$-correct algorithm is $\mathbb{P}\left(\tau_\delta<\infty\right) = 1$ and $\mathbb{P}\left( k_{\tau_\delta} \neq 1\right) \leq \delta$. Are there any concerns with this definition?
3. It is surprising that TCB does not satisfy the asymptotic optimality conditions. Have you verified the correctness of the implementation? Additionally, did you use the same forced exploration rule and stopping rule for all algorithms in the numerical results? Finally, I suggest including a theoretical analysis of the computational complexity for the proposed algorithm.
limitations: limitations: The main contributions of this work are theoretical in nature. I don't foresee any direct negative social impact.

Comments: title: Response to Authors' Rebuttal
comment: Thank you for increasing the score. We very much appreciate your comment that exposition and mathematical presentation needs to be improved. We are tweaking the exposition at a few places of the paper to improve the presentation. We illustrate the changes below through an updated version of Proposition 2.1:    

Proposition 2.1 is crucial for constructing the fluid dynamics. Proposition 2.2 provides a set of conditions which uniquely identify the optimal allocation $\omega^\star$. We define the quantity $N_{\min}=N_{1,1}+\sum_{a\in\bar{B}^c}N_a$. 


**Proposition 2.1:** For every positive $N$ satisfying $N\geq N_{\min}$, there is a unique set of variables $N_{\bar{B}}(N)=\left(N_a(N)\geq 0:a\in\bar{B}\right)$ and $I_B(N)$ satisfying the following conditions: 

$\sum_{a\neq 1}\frac{d(\mu_1,x_{1,a})}{d(\mu_a,x_{1,a})}=1$ where $x_{1,a}=\frac{N_1(N)\cdot\mu_1+N_a(N)\cdot \mu_a}{N_1(N)+N_a(N)}$ and 

$N_1(N)\cdot d(\mu_1,x_{1,a})+N_a(N)\cdot d(\mu_a,x_{1,a})=I_B(N)$ for every $a\in B$.   

Furthermore, $N_{\bar{B}}(\cdot)$  and $I_B(\cdot)$ are continuously differentiable w.r.t. $N$ for every $N>N_{\min}$. 


**Proposition 2.2:** Upon taking $B=[K]/{1}$ and $N=1$, $N_{\bar{B}}(1)$, as defined in Proposition 2.1, is same as the unique optimal allocation $\omega^\star$ solving the max-min problem in Eq.(1), and we also have $I_B(1)=T^\star(\mu)^{-1}$. Moreover, for every $N>0$, the unique solution $N_{\bar{B}}(N)=(N_a(N):a\in[K])$ satisfies $N_a(N)=N\omega_a^\star$.


**[Providing references]** We have added references to the IFT in the revision. About the GLLR, we referred to the discussion in [13, Section 3.2] in Section 3 of the submitted version of our paper. Furthermore, in the revision, we have made a section in the appendix explaining the intuition behind GLLR.
Thank you for your response. After reading the rebuttal, I would like to maintain my original rating.
Thanks again for your suggestions. These will improve the paper's presentation.
I thank the authors for their detailed and insightful response. All my questions have been fully addressed. I will maintain my current score.
Thanks to the authors for addressing my questions and weaknesses. I think adding the specifications and explanations to the experiments and question 2 would make the paper more intuitive to understand. I intend to keep my score and good luck for the submission.
Thanks for your response. In general, as a non-expert in the area, I found this paper quite inaccessible. I believe that improving the exposition and mathematical presentation will help a lot, as will adding definitions or at least references for IFT, GLLR, etc. 

In terms of Proposition 2.1 specifically, it is stated that it characterizes the unique optimal allocation, but it is very hard or me to connect this to the wall of math in the proposition. I don't think saying "The following statements are true" and then listing a sequence of technicality true statements is the clearest way to express a theorem. I would find more verbal explanation very helpful. 

Given that the authors have expressed a commitment to strengthening the exposition, and that other more expert reviewers seem to feel positively about the work, I am happy to increase my score from 3 to 5.