Optimal Top-Two Method for Best Arm Identification and Fluid Analysis
Authors: Agniv Bandyopadhyay
Sandeep Kumar Juneja
Shubhada Agrawal
Venue: NeurIPS 2024 poster (2024)
Keywords: Stochastic multi-armed bandits
best-arm identification
sequential learning
ranking and selection
Primary area: bandits

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.

Optimal Top-Two Method for Best Arm Identification and Fluid Analysis
Agniv Bandyopadhyay TIFR Mumbai, India
Sandeep Juneja Ashoka University, India sandeep. june janeea200000maalll com
agniv. Saadwbbaddyoadhyyyytif.. res..rrrreeeeee.. in
Shubhada Agrawal
Georgia Institute of Technology, USA sagrawa13620gatech. edu
Abstract
Top-2 methods have become popular in solving the hest arm identification (BAI) problem. The best arm, the 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 3. and pulls the best challenger arm otherwise. The probability of incorrect selection is guaranteed to lie below specified 8
Information theoretic lower bounds on sample complexity are well known for BAI problem and are matched asymptotically as - 0 by computationally demanding plug-in methods. The above top algorithm for any 3 E (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 function of allocations anchored a threshold. If 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 - 0. Our analysis relies identifying a limiting fluid dynamics of allocations that satisfy series ordinary differential equations pasted together and that describe the asymptotic path followed by algorithm. We rely the implicit function theorem show existence and uniqueness of these fluid ode's s and to show that the proposed algorithm remains close to the ode solution.
Introduction
Stochastic best arm identification (BAI) problem has attracted great deal of attention in the multi armed bandit community (see (21). [0O] 3 for some early references in BAI). The basic problem 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 pre-specified 8 > O. Applications many including in healthcare and recommendation systems.
involves a finite number of unknown probability distributions
II developed asymptotically (as 8 0) tight lower bound on sample complexity of 8-correct algorithms for these BAI problems under the assumption that arms belong to single parameter exponential family (SPEF). This assumption reduces probability distribution to single parameter and allows the analysis to better focus 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 rack-and-stop
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 computationally demanding. [14] consider linear Gaussian bandits, [ 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 algo- rithms identify the best arm (see 225, 26 for Bayesian approaches; (24] 22 [66] 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 8, and the challenger arm with the complimentary probability. In the frequentist setting, in [66, 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, c.g., M. 19), the algorithm is terminated when the generalized ligllikeldhood ratio (GLLR, given in Section 3 statistic exceeds specified threshold. These algorithms are shown to be 3 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 -aymmtottiiic analysis when 3 = 1/2). However, determining optimal 3 has been an open problem that has generated considerable activity and that we address in this paper.
Contributions Algorithm:
The key insight from index based top-2 algorithm is that once a sample given to 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 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 < O, 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 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 the optimal proportions as per the lower bound. This continues until the GLLR statistic exceeds a threshold, roughly of order log(1/8), The time to stability can be bounded from above by random time with finite expectation independent of ó, while the time from stability till the GLLR statistic hits a threshold scales with 1og(1/8) with a constant that matches the lower bound.
Fluid model: Our other key contribution is to capture the above intuitive description through constructing an idcalized 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 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 allows the arm allocations (N, overall allocation N. IFT further allows us to identify the ordinary differential equations satisfied by the derivatives No = dN₂ aN* as the allocations N increase. The overall path till stability is constructed by pasting together the ode paths followed by arm allocations the set of indexes that have already been pulled and are increasing together with N, meet another higher index. Once all the indexes have ode stabilizes that the proportions N./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 8. For completeness, in Appendix E.2 we also identify the ode paths under fluid dynamics for 3 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.
K) to be unique functions of the
been pulled,
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
2

---

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 BAT 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 A >> 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 linear program each iteration. [17. 13, 6 provide algorithms that provide finite 0 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., 44, stochastic approximation (e.g.. (55) and queuing theory (e.g.. [
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
also develop the relevant IFT framework. Section[4sspe associated with the algorithm. Key steps involved in proving Theorem 3.I are outlined in Section S We describe the numerical experiments in Section 6
out the fluid dynamics
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 Jusggst 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 the assumption of stationarity of the underlying distributions. This may be true when relatively short sampling horizons are involved.
Key limitations:
2 Problem description and lower bound
Distributional assumption: As mentioned earlier, we focus arm distributions that belong to known SPEF. Let S c 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 μ (JI,.... ((K))..)())) where each μ4 E 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 unique arm with the largest mean. Thus, without loss of generality μ1 > max Mi One way to handle the case where 2 or more arms are tied for the largest mean is to look for e-best arm (an arm whose mean is within e of the best arm). However, that is technically a significantly more demanding problem (see [2) ). 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 AN denotes the arm pulled at sample N, and X, denotes the associated reward generated independently from distribution AA then A is chosen sequentially and adaptively as a function of generated (An, X,, n = 1,2,..., N - -1). Further, an algorithm stops at some finite random stopping time and announces the best arm. 8 5-correct algorithm is an algorithm that, given 6 > 0.
3

---

stops at time 76 > 0 and outputs a best arm estimate ky, such that P(Ts < oc, k7, 1) S 8. That is, it identifies the arm with highest mean with probability least 1 - 8. Our interest is in identifying a d-correct algorithm that minimizes [[(T)) To this end lower bounds on sample complexity of d-correct algorithms are established using, e.g., the data processing inequality (see, e.g., [18). We see that
inf, [E[Ni]d(M), x) + E[Na]d((pa x)} log(1/(2.45)
with d(u,, 2:) denoting the Dollback--eebbles divergence between two distributions in S with means and x; and the expectation under measure P,, associated with μ.. The infimum above is solved at xx + With this, we obtain the lower bound E[rs] 2 (p) log 2 where T* (p)
+ENN]+
the reciprocal of the optimal value of max-min problem,
(T))
max [K]]EE
min (wid(p1, + wad(Ha rl,)), azl
(1)
where 21,a (W1/11 + WaHa)/(wy + Wa) and ΣK denotes 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 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 (c.g., each arm gets at least vt 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 w' (wa E [K]) which motivates our algorithm's ''s sampling strategy. Before stating the two propositions, we need some notation. Let B S [K][[1) and 7 = B U (1). Whenever Bº * 0, let Ng (Na 2 0: E B") denote allocation of samples to the arms in B" and treat this as a constant in the following discussion and also in the statement of the two propositions. We define the quantity N1,1 depending on Ng in the following way: If = or Eae N₂ = 0, for the given
N zero. 2) Otherwise, Ni,1 is the value of N1 at which ELEB' d(pi. [(..)
allocation Ng. To see existence of such NI.1, observe that whenever B" A and E.En' No > O, the function N1 E.EB" d(p1.f1.u) ((.a) is continuous and it monotonically decreases from oo to 0 as N1 increases from 0 to C0. Hence, a unique N1 exists where this function equals 1. We define the quantity Nmin = N1,1 + + Na.
Proposition 2.1. For every positive N satisfying N > Nuinn there is a unique set of variables (N( = -NN a E B) and (N(N) satisfying the following conditions
d(a1. = 1, where Fi.a Eapl d(Ha..i,a) and, for every a B, Ni(N) di + Na(N) d((aa, = IB(N).
MI(N)),+N, (N) EnE[K] No(N) N, N..N)-N.(M)
) (2)
Furthermore, N-C-) and [b(+) are continuously differentiable w.E.t N for N Nmin.
Proposition 2.2. Upon taking B = [K]/1} and = = B,),,, as defined in Proposition 2.7 is same the unique allocation w solving the max-min problem in ( Further, [1) = =T"
Moreover, for every N >> 0, if B [1)(1, the unique solution N (N)) = (Na(N) (N):: : a [K]
satisfies N (N) Nw..
Proposition 2.1 is proved by applying the Implicit function theorem (IFT). Proposition 2.2 is subsumed
by M Theorem 5], but we prove it using different of tools by applying the IFT. See Appendix D for the detailed arguments.
For two vectors
(Vo ESS. S: [K]) and N (Na E R20 d( M(Mansssta)
[K]) define the anchor
function, g(V, NN = EeE[KI/D)
- 1, where = arg max, Vas V'nax = max, Va. and
d(varia)
2n = Umxx + (aVa)/(NN + No) for all +
Remark 2.1. It follows from Proposition 2.2 that the anchor function g(n, w) = 0 and all the indexes wi d(ju, .1,a) ) + wad(pa, .1.a) equal to each other, uniquely identify the optimal proportion w' solving the max-min problem (see Appendix D.I for easier and more insightful derivation

---

of these conditions). The algorithm proposed in Section ensures that the empirical version of the anchor function g(-) quickly becomes close to zero and thereafter remains close 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 [K] and iteration N, (NV)) denotes the number of times arm a has been drawn till iteration N, and
(NN) (N) a E [K])- Thus, N E. (N). Let (T(N
(N) [K]) where
Ha (N) denotes the sample mean of arm a at time N, i.e. (NV = I(4, = a) N.)N,(N).
and ix arg [K] Pa (N), with an arbitrary tie breaking rule.
For every pair of arms a, b, define
(N) Na(N) Ma No(N). 146
and (a.( Na(N) (N) - N6(N) (N6 Na(N) + No(N)
Na(N) + No(N)
Let, (N)(N) = No(N) d (ia (NV),
+ No(N) d(us (N)), and Ia,((N) = Na(N). (NN) ( For âN. we call la (N), and Iaw (NV, respectively, actual index (or, simply index) and empirical index of arm at iteration N, and denote them using (NV), ) and Ia (N). For notational simplicity, we hide the dependency on N whenever doesn't I cause confusion. Note that Ig (N) is a function of ix (N), Na(N), Pby (NV and 7u (N).
Stopping Rule:
As is typical in this literature, in our algorithm below, follow general- ized log likelihood ratio (GLLR) to decide when to stop the algorithm. It is easy to check that min Zu (.V) denotes the GLLR, that is log of likelihood function (LF) evaluated at max- imum likelihood estimator (MLE) divided by the LF evaluated at MLE of parameters restricted to alternate set with different best arm compared to MLE (see [II] Section 3.21 for de- tailed derivation). Define stopping time Ta = inn([N] for all E [K]/(i), In(NN > B(N,))) for an appropriate choice of threshold 8(N, 5). After stopping
Ts. the algorithm outputs i.; as the best arm. 119 Eq. 25, Section 5.1] argued that for instances in SPEF, upon choosing 3(N,8) 8) s log((K 1)/0) + +6 6log [log(N/2) + 1) + logg(1 + 2 log( - 1)/6)), the GLLR based stopping rule is 8-correct for any sampling strategy including the one we propose. In our numerical experiments, follow [II and choose smaller threshold, 3(N 6) log( (1 log N)/
Description of the AT2 and Improved AT2 (IAT2) Algorithm: The AT2 algorithm takes in confidence parameter 8 >> 0 and exploration parameter E (0,1) inputs, and executes the following steps at itcration N:
Let VN
def. {a [K] Na - 1) < No) be the set of under-explored arms.
VN # 0. choose An = arg min Na 1), and go to step
3. Else, if g(ā(N - 1), N(N - 1)) > 0, choose the empirically best arm i.e. Ay = i and to step 5.
4. Else, if g(Ā(N 1), N(N 1)) < 0, choose the challenger arm i.e. An arg min min/u[K///fwwi IN - 1) using some arbitrary tie breaking rule, and go to step 5.
Sample XN from An and update (i(N) and (NV) using XN. AN.
6. If min (jk/////// Ia (N) > B(N, 6), terminate and return i..
Inspired from the Improved Transportation Cost Balancing (ITCB) policy for selecting the challenger
arm in [6]. Improved AT2 (IAT2) algorithm has the same input and follows the same strategy
for exploration (step 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 Av =
arg minnaa////(xx-i (I.(N 1) + log (N 1)).
5

---

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 and respectively.
3.1 Theoretical guarantees
Proposition 3.1 below shows that the allocations made by AT2 and IAT2 algorithms converge to the optimal allocations wi w.p. I in PpA- For every [K] we define (,, (NN/N, and use (NN) = (NV) : a E [K] to denote the algorithm's 's proportion at iteration N.
Proposition 3.1 (Convergence to optimal proportions). There exists a random time Tstable and
constant C > 0 depending on μs, a, and K, and independent of 5, such that, E stabblel] < oc, and for every N 2 Tstuble and arm a E [K].
[aa - wil C, and [P,(N) Maal= c(u)N
where e(p)) is positive constant depending only on μ.. and defined in Appendix B
Theorem 3.1 (Asymptotic optimality of AT2 and IAT2). Both AT2 and IAT2 are 8-correct over instances in S, and are asymptotically optimal, i.e., for both the algorithms, the corresponding stopping times satisfy, lim sup&-D0 [og(1/8) < (p)),,, and lim sups-10 Tog(1/8} S (T) a.s. in P,.- Moreover, we can find constant C > depending on the instance μ and such that,
Eu(ra]
To S max{ Tstables T (p) 1og(1/6) + (log(1/5)) 1-3/88 } a.s. in Pp.
Proof idea of Theorem 3.11 We assume Proposition 3.1 and sketch the argument by which asymptotic
optimality follows from For N 2 Tstables and a E [K], from Proposition 3.1 (N) = w N and
for every a & 1. Therefore, if min [N(N] crosses 3(N, 5) at N = To. since ( 0)= = log (1)) (m)
No (N) Pa. As a result, from Proposition 2.2 after Tstable. Ia (N) 2 N [px (okl//11((11 (1)
Olog log(1 (1/ 11))++00lgggg log log(N)) N)). we have Tς T (Ju) R8-s0 log( [ /5) (060)+0(1lg)) log (1g(1 (155) + +lo log (T) ))
which gives lim sups-0 log(1/5) S (n) a.s. F,.. Detailed proof is in Appendix
We outline the key steps of the proof of Proposition 3.1 for AT2 in Section and the detailed proof is in Appendix G.2 Similar arguments hold for IAT2. Considerable technical effort goes in proving this proposition due the noise in the empirical estimate (>) 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.
4 Fluid dynamics
Motivation: The fluid dynamics idealizes our algorithm's 's evolution through making assumptions 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 [K] at some time N > 0 using N, N, (NV, and define the tuple N(N) = (N)) a E [K]). Note that Eas(k] NNaNN) = N. The rate N (N) at which samples get allocated to arm a at time N depends on continuous version of the AT2 algorithm. which we refer to as the algorithm's fluid dynamics. We define the index of arm of at time N as, +N (NN),, (NV) = (NV d(p1, L1.a (N)) + N..N)) dd,aa, where 21,a(N) = (N)+NNN Notice that (NV defined in Section D is the index of arm with respect to the algorithm's 's allocation N(N), whereas in our current context, I, (N) represents the index with respect to the fluid allocations (N).
Description of the fluid dynamics: First we explain the fluid dynamics in words. We formally characterize the fluid allocation ((N) via 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, the allocations ((N) reach the optimal proportions w' (wt a E [K]) by time

---

atmost (minge Ki wā) -No. In other words, for N 2 [m]]
w.) NN. we have (NV)
wa N for every arm E [K] irrespective of the initial allocation we had at time No.
For notational simplicity, we hide the dependency on N, whenever doesn't 't cause any confusion.
Recall the anchor function g(-) introduced in Section 2
We use g to denote g(u, N (N)). For every
subset A S [K]/(1), we use A to denote A U (1).
We start the fluid dynamics time No 0 with some initial allocation No (No > 0: E [K])- We assume that the vector of true means 14 is known. The fluid dynamics evolves according to the following steps
given total allocation N 2 Nº: 1) g > then Ni increases with N while other No 's for a + 1 are held constant till g = 0 (g can be seen to be a monotonically decreasing function of N1). 2) If = let B denote the set of minimum indexes. Thus, (N) are equal for all a B (the equal value is denoted by I (N)) and Ia (N) > (N) for all a E B". Then, as N increases, allocations N1 and (Na a B) increase such that g remains equal to zero, while the indexes in remain equal. In Proposition 2.1 we characterize and prove existence of such allocations, which the fluid dynamics will track. Later we observe that, LB increases atleast at linear rate and indexes of arms in B stay bounded from above by constant. 3) If g O, let B be the set of minimum index arms and Ig be the index of arms in B. In this situation, (Na a E B) increase with N keeping index of the arms in B equal, while N1 and (N, : E B²) are unchanged. With this g also increases, since g is a strietly increasing function of N, for every E B. The dynamics in this case are simple and described in Proposition E. of Appendix D 4) Once, g = 0, and B .2.....K' K}. we show that each allocation increases linearly with N such that No¹ wa-
The fluid ODEs: In Appendix we argue that if the fluid dynamics has g * 0 at time No, then g becomes zero within a finite time by following step I or step of the description. This is easy to observe when g > O at Nº,, because g is strictly decreasing in N1, and g + -1 as N2 + oc. Therefore, following step 1. 9 becomes 0 at some finite N. We now consider the situation where g 0 at some N > N Setting B to the set of minimum index arms, the algorithm evolves by tracking the allocation (NV = (N (N) a E B) defined through the system (2) in Proposition 2.1 By Proposition 2.1 N (NV) () is continuously differentiable w.r.t. N. Applying IFT to (2), we obtain the ODEs via which the allocations and the indexes evolve and present them in Theorem 4.1
Some definitions: Let f1, a, N) = 8z
dips.x)
H(,, a, N) is strictly positive because 1==raaa
a(Ham))
d(pr.)) is strictly decreasing with x for E (Mar M1). a(paw)
fuu,a, NN,=. For notational simplicity, we denote lu(je, N1, Na) by ha- Further, for each a, we denote d(ui, .1,a) by dı,a and d(Ha, by da Recall that for given allocations (Na : [K]), B denotes set such that N N1d1a Nadua
Let A. M1 - Has and (1,, NN,,NN),
N
(N) for all a E B, and Nidi. + NNadaa > [nN) for all a E B". Let h(B) = EaEn had
I(N)= = Ene Na.a. and da = (EaE drrd)=
Theorem 4.1 (Fluid ODEs). If at total allocation N 2 No, we have g = 0, and B is the set of minimum index arms, i.e., B = arg min Ia(N), then the following holds true;
1. As N increases, and till Ig (NN) increases hit index in B",
N1h(B) N1= (Ni + E N.)A(B) +f) and N₂-- = (Ni + EMER Na)M(B) ((N)
Noh +
(3)
for all b E B. It follows that, I'r = (N+ No) A(N)'
(N
Furthermore, for a E B", I,,N== Nídia (N1 (N+ N. Nd) ANNN)
Nrh(B)dn
3. There exists B > O, independent of N such that (N) > 3. In addition, for E B.N. - -0 Ia(N) S N2d(Ma, p1). thus the index is bounded from above. Thus, Bf + 0, (B(N) eventually catches up with another index in B In this way, the set B grows into ( KK.
7

---

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 be smallest time after No at which the fluid dynamics has both B = {2..... and = 0. Let (No a E [K]) be the allocation No. We first argue that: there exists i [K] such that N; No We have argued before that g + O at No, then becomes zero by some finite time, which we call M. By definition M < N
Now if B + {2, ..... K} M or M No, 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 is the last element to be added to B. Otherwise B (2..... K} at M and
M > No, the only way this can happen is g < 0 in [No. M). In this case, i = and M = N Since g = O and B = (2...., K} at time N Proposition 2.2 i.pimes N w N for all a. Combining our observations, we have N = NT = Nº < No. Hence N Thus N* is within a constant times of No. We bound Tstable of Proposition 5.1 using a similar argument.
(min.e[K] - No.
Remark 4.1 (Incorporating the stopping rule into the fluid dynamics). At stopping time the idealized GLLR (which is the GL.RR 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 independent of 8, for small ö, stability will be reached before the algorithm stops.
Remark 4.2 (3-fluid dynamics). In Appendix H.2 we construct the fluid dynamics for the 3-EB- TCB algorithm [16] using IFT. We prove that, for every 3 E (0, 1). the 3-fluid dynamics started at some time No > 0 reach the 3-optimal proportion (which is the solution to the max-min problem with the added constraint W1 = (3) by a time which is a constant times No
5 Convergence of algorithmic allocations to the optimal proportions
We now outline the proof steps for Proposition 3.1 To simplify our analysis, we analyze the AT2 algorithm after the random time To defined as,
To = inf { NN' 2 1 Va E [K] and N 2 N', (NaNN - Mal S -33a//8
after which the estimates (NN are converging to μ. Recall that E (0,1) is the exploration parameter, and E(p1) > 0 is a constant depending only on μ.. By the definition of e(H)) in Appendix
B we have Ta (N) < 14 (N) for all of 1 and N 2 To. As result, arm 1 becomes the empirically best arm after Tg- In Appendix G.3 we use Chernoff's bound to prove that P (To = n + 1) exp(-Q(na/4) ), which implies E,, [T)] < cc. In the following discussion, all the results mentioned true for both AT2 and IAT2 algorithms.
Proposition 5.I shows that the allocations made by the proposed algorithm converges to the first order condition satisfied by the optimal proportion wt (W, : a E [K]) at rate O(N -3a/8),, where is the exploration parameter.
Proposition 5.1. There exists a random time T sstablc. 2 To satisfying En [taasstable < co and constant C2 > O depending on p. a and K, and independent of the sample paths, such that, for N 2 Tatable
2( (..1(,())))) -1 s C2N 30/8
19(,, ((N,((N)) = Σ 11 d(Hay I2,a (N))
(4)
and
max O.
(Na(N) Io(N) S C2N1-3a/8
(5)
Before outlining the proof of Proposition 5.1 we explain how Proposition 3.1 follows from Proposi- tion 5.1 just using the IFT.
8

---

Proof idea of Proposition 3.1; If our algorithm follows optimal proportions at time N, i.e. (N) = w N for all a E [K], RHS of (4) and (5) becomes zero by Proposition 2.2 Moreover, by Proposition 2.2 w uniquely satisfies the conditions: anchor function is zero and all alternative arms have equal 5 imply that, (NN) satisfies these conditions upto a perturbation of C2N after T Tsubble. Using the IFT, we prove that the algorithm's allocation is Lipschitz continuous function of the perturbation when it is sufficiently small. Hence, by choosing Tstable large enough and using Lipschitzness, we get ma We (N) - will = O (N)- Closeness of (i(-) to la follows from the fact that Tatable 2 To-
index. 44 and
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()), .2()) and (-)) notations are independent of the sample path after time stable-- To simplify our amalysis, we choose T stable such that exploration stops after T Ttaalee i.e., VN for N 2 Tauble (see the discussion before Definition G.1 in Appendix G.I.I for justification).
Key ideas in the proof of (4) We prove 44 via induction. We prove the existence of a constant
D> > such that at every N 2 Tstable, whenever the actual anchor value g(u, N (N)) (we denote
using g(N) satisfies gg( [N) > DN-3a/8, our algorithm pushes g(-) towards zero by (1/NN) in the next iteration through steps and 4. Whereas the interval [-C2N -3a/8 N2 shrinks by O(N-(1+3a/8) from both ends. Since N-(1-3a/8)) << N-1, we choose the constant C2 large enough such that (-) 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 random time T good E (To Tstable) such that the algorithm picks all the alternative arms in [1] atleast once between the iterations Toood and Tstable- Moreover, for N 2 goood. if the algorithm picks some arm E [K]/[]} at iteration N, then it picks arm again within a next O(N1-30))) 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 # I and after any N 2 Tatable- I-(-) and Is(-) crosses each other before the algorithm picks both a, b atleast once. We can show that, for j = a, and N 2 Tstable. (N) and (N) differ by O(N1 (NNl)a//)). As a result, when I.(.) crosses Ix(-) at N + R. we have (N + R2) - I&(N + R2] = O((N + 12)2-30/8) = O(N1-30/8) since R = O(N1-33/88) For j = a, b, the partial derivatives of I,(-) w.r.t Ni and Nú are non-negative and bounded from above by max(d((1, (5), d(py,
0(1). As result, [N + R) [N() = O(R) -3//)) for j = a, b. Hence, [Ta Ic(N) s [Na(N + R) - LNN + R)] - E==as + R) - [,() = O(N
30/8). 13x/88.
we choose Tyood and Tstable such that Tatable is the time after T good by which the algorithm picks all the sub- sub-optimal arms atleast once. By Proposition 3.1 the algorithm approximately matches w" after Tatable- 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 Tstable 2 ) good a.s. in TP u. where w min w. (Lemma G.4 Appendix 1. p.
Bounding Tetable: In Appendix G.2
Role of forced exploration in analysis: As we observe in the numerical results in Appendix J.4 forced exploration (step of our algorithm) does not increase the observed sample complexity. We emphasize that without the forced exploration. Propositions [5.] and 3.] 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 [R[7] < 00, every arm has Na (N) = .((N). As a result, upon proving sufficient exploration, asymptotic optimality will follow without the forced exploration step.
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
In Appendix J.4
9

---

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 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 ---B--TB algorithm of [16] for different values of B, and TCB algorithm of [22]. We consider 4 armed Gaussian bandit with unit variance and mean vector J = [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 demmontteesss 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)A22, (I)TCB, and B-EB- (-)BC,, for different choices of B, and observe that (I) outperforms all the other algorithms. Note that we use the same forced exploration rule and stopping rule for all algorithms. In Appendix we demonstrate by several examples that both
AT2 Index Values
Sample Complexity
2.0
25
IBCB
Number of Samples
-22
Dete-EB-CC
Bela
Va
155
1.0
0.5
300
600
520
0.5
0.6
6.7
Time
Beta
Figure Normalised index on sample path.
Figure 2: Sample complexity comparison.
the AT2 and IAT2 algorithms significantly outperform the 3 E-BBBCC and ITCB of [1 when is chosen different from the optimal B. 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 D.. Next, in Appendix [.4] we study the effect of choice of the forced exploration parameter on the sample complexities AT2 and IAT2. Additionally, we conduct simulations for natural extensions of these algorithms bandits with distributions supported in [0, 1] (Appendix J.5)
7 Conclusion
We considered the best-arm identification problem under the popular top-2 framework. In the litera- ture, top-2 framework involves sequentially identifying the empirical best arm and the most-likely challenger arm, and sampling the empirical best with probability 3 and the other with the complimen- tary probability. However, optimal .3 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.
10

---

Acknowledgments: We thank Arun Suggala and Karthikeyan Shanmugam from Google Research Bangalore for initial discussions on this project. The second and the third author initiated this work while visiting Google Research in Bangalore.
References
[1] Shubhada Agrawal, Sandeep Juneja, and Peter Glynn. Optimal 8-correct best-arm selection for heavy-tailed distributions. In Algorithmic Learning Theory, pages 61-110. PMLR, 2020.
[2] Shubhada Agrawal, Sandeep Juneja, Karthikeyan Shanmugam, and Arun Sai Suggala. Optimal best-arm identification in bandits with access to offline data. arXiv preprint 00X942330.000048 2023.
[3] Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In Conference on Learning Theory, pages 41-53, 2010.
[4] Alain Bensoussan, Jens Frehse, Phillip Yam, et al. Mean field games and mean field type control theory, volume 101. Springer, 2013.
[5] Vivek S Borkar. Stochastic approximation: a dynamicall systems viewpoint, volume 48. Springer, 2009.
[6] Lijie Chen, Jian Li, and Mingda Qiao. Towards instance optimal bounds for best arm identifica- tion. In Conference on Learning Theory, pages 535-592. PMLR, 2017.
[7] Ye Chen and Ilya O Ryzhov. Balancing optimal large deviations in sequential selection. Management Science, 69(6):345--3477 2023.
[8] Jim G Dai. On positive harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. The Annals of Applied Probability, (1)):49777, 1995.
[9] Amir Dembo and Ofer Zeitouni. Large deviations techniques and applications, volume 38. Springer Science & Business Media, 2009.
[10] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
[1]] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
[12] Aurélien Garivier and Emilie Kaufmann. Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models. Sequential Analysis, 40(1):61-96) 2021.
[13] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil'uch: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439. PMLR, 2014.
[14] Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. In Advances in Neural Information Processing Systems, volume 33, pages 10007-10017, 2020.
[15] Mare Jourdan and Rémy Degenne. Non-asymptotic analysis of ueb-based top algorithm. In Advances in Neural Information Processing Systems, volume 36, pages 68980-69020, 2023.
[16] Marc Jourdan, Rémy Degenne, Dorian Baudry, Rianne de Heide, and Emilie Kaufmann. Top two algorithms revisited, Advances Neural Information Processing Systems, 35:26791-26803, 2022.
[17] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armn armed bandits. In ICML, volume 12, pages 655-662, 2012.
[18] Emilie Kaufmann. Contributions to the Optimal Solution of Several Bandit Problems. PhD thesis, Université de Lille, 2020.

---

[19] Emilie Kaufmann and Wouter M. Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22(246):1-44, 2021.
[20] David G. Luenberger and Yinyu Ye. Linear and Nonlinear Programming. Springer US, 2008.
[21] Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623-66) 6244648,, 2004.
[22] Arpan Mukherjee and Ali Tajer. Best arm identification stochastic bandits: Beyond 8 optimality, arXiv preprint arXiv:2301.03785 2023.
[23] Yurii Nesterov al. Lectures on convex optimization, volume 137. Springer, 2018.
[24] Chao Qin, Diego Klabjan, and Daniel Russo. Improving the expected improvement algorithm.
In Advances in Neural Information Processing Systems, volume 30, 2017.
[25] Daniel Russo. Simple bayesian algorithms for best arm identification. In Conference Learning Theory, pages 1417-1418. PMLR, 2016.
[26] Xuedong Shang, Rianne Heide, Pierre Menard, Emilie Kaufmann, and Michal Valko. Fixed- confidence guarantees for bayesian best-arm identification. In International Conference Artificial Intelligence and Statistics, pages 1823-1832. PMLR, 2020.
[27] Po-An Wang, Ruo-Chun Tzeng, and Alexandre Proutiere. Fast pure exploration via frank-wolff Advances Neural Information Processing Systems, 34:5810 10-5821, 2021.
[28] Wei You, Chao Qin, Zihao Wang, and Shuoguang Yang. Information-directed selection for top-two algorithms. In Proceedings of Thirty Sixth Conference Leurning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2850-2851. PMLR, 12-15 Jul 2023.
12

---

Appendix
A Outline
Below we provide brief outline of the topics presented in the appendices.
1. Algorithm and are, respectively, the pseudocodes of the AT2 and IAT2 algorithms introduced
in Section 3
2. Appendix We define the single parameter exponential family (SPEF) of distributions, and prove several inequalities bounding the index function, anchor function, and the derivatives anchor function, which are crucial for our analysis.
3. Appendix C
We introduce framework using which apply the implicit function theorem for proving several properties related the fluid dynamics and the algorithm's allocations.
Appendix D
We prove Propositions 2.1 and from Section [
Appendix D
We provide the proof's of the results mentioned in Section 4 and also construct the
fluid dynamics for the 3-EB-TCB algorithm ((16) in Appendix E.2
We provide a heuristic argument to show that if the minimum index meets with the index of some sub-optimal incorporated into the set of minimum index arms. We argue via contradiction to show that, if this not the case then index of arm 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 I are extensions of the said argument the non-fluid setting of the algorithm with additional terms because the noise in the estimates.
Appendix[I F
a A 1 following the ODEs in Theorem 4.1 then arm must be
7. Appendix G
We prove Proposition 3.1 5.1 and provide detailed proofs of all the results
mentioned in Section
Appendix H
We provide the detailed proof of Theorem 3.1
Appendix T We describe natural extension of the proposed AT2 and IAT2 algorithms the class of distributions with support contained in [o, 1]. We do not theoretically analyze this algorithm owing space constraints. However compare the proposed algorithm with existing algorithms experimentally in Appendix
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.
Algorithm 1: Anchored Top-Two (AT2) Algorithm
Input: Confidence parameter 8 > 0, exploration parameter (0,1)
for N 2 do
VN + E [K] NaV - 1) < No)
VN + then
L AN + arg min Na(N - 1)
// Forced exploration
else if g ( N(N 1)) > then
L AN - iN-1
// Choosing leader
else
[ AN + arg min ae[]//ie I.(N - 1)
// Choosing challenger
Sample XN from AN and compute (NN and N(N)
Generalized Lig-Likeihhod Ratio (GLLR) Test if' min ae/]/// Ia (N) > B(N, 5) then
10
return iN
13

---

Algorithm 2: Improved Anchored Top-Two (IAT2) Algorithm
Input: Confidence parameter 5 0, exploration parameter (0, 1)
for N 2 1 do
Vv + {a E [K] NNVN - 1) < Na)
VN * then
L AN - arg minae[K] Na(N - 1)
// Forced exploration
else if 9 ( N(N 1)) > then
AN - iN-1
// Choosing leader
else
AN - arg a Ia(N - 1) + log N.(N - 1) // Choosing challenger
Sample XN from AN and compute ((N) and N(N)
/+ Generalized Log- Lo-LLikklihoor Ratio (GLLR) Test min (e]T((( (NV= > B(N, 6) then
10
11
return iN
B
Single parameter exponential family of distributions
We consider single parameter exponential family (SPEF) of distributions of the form
dug(#) exp(Ox b(0))dp(x))
where p is dominating measure which assume be degenerate, 0 lies in the interior of set O defined below (denoted by 0%):
θ - (0) exp(Ox))d((x) < =o))
and
b(0) = log (Le exp((xx)d((x))
the log-moment generating function of the measure p(-).
For 0, (), the KL-divergence between the measures vy and Vy is.
K (Le
0)b b(0) 6(0).
The mean under Ne given by (0))). Let S be the image the set Oo under the mapping B((.). Note that S is open interval. Also, since b²(-) 0 in 6º D'(.) is strictly increasing in O and is bijection between O and S. This implies we can parameterize the distributions in the SPEF using their means well.
Let On the unique 0 satisfying ('(0) μ for some E S. Clearly, 0,, is a strictly increasing
function of μ.. This follows since b((-) strictly increasing in 6". Additionally, all the higher derivatives b(.) exist in the set t (see Exercise 2.2.24 in (9).
For p. Ti E S we define du, (1) as.
d(u, M KL(va,, (0,, - b(0w) b(0z))
We define Minf E R 1 and Msup
R {+oo}, respectively, be the infimum and supremum of the interval S. Then, = (Hint P.up).
Definition B.1. For μ (M1, M2, ... pk) SK define Tmin minge k) {min Minf, Maup 44 }
14

---

Since S is an open interval, (p) is positive for every j SK and can be oo if both Pint and Msup are 20.
Partial derivatives of d(1,, M)): For every pair μ4, Jr E S, the partial derivatives of d( (1) with respect to the first argument is
def. 8
di (14, M
d( 11) = 0₂ 0p-
and that with respect to the second argument is,
d2(u, def. Tu
p --1 1" (0z)
Enveloping the Kl--divergence: the following discussion, we try to bound the KL--divergence d(p, (4) from both sides using the squared distance | Tu|² after imposing some restrictions on the
choice of pt, jr S. For an instance μ E S*K, we define the constants Amin and <fp)) as
min (11 ps) and ((L) min { TE[K1/f1}
Amia (m) mmin(p))
Amin (1))
2
We further define
H(pp)
[M4 144-ci c(p). c(N)), (E(R)/(1
U
max (pe)
max (²(0,) and (p) min (²(),). NEH())
mEH())
Since H(p) C S, all distributions with mean in H(s) have positive variance. Note that (0,,,) represents the variance of the distribution with mean Jr. As result, since H(μ) is compact set, both mmax (H) and J (H) are positive constants.
Hence, b(-) is min (1) -strongly convex and 6'(-) is max ( Lii-sssshhtt the set (6) (H(())). Thus, using 23 Theorems 2.1.5 and 2. 2.1.10), for every 01, 02 E (HH(()), we have
66 (0(0)) - 202)) 20 (14)
16 (0() ((2))1
S b(02) b(0,) (0.) (02 - 01) = d(ve, voz) s
20 (14)
and hence, for n E H(1))
1
11 Fz
S d(p,
(6)
20 20 (p)
20 (1))
Bounding the partial derivatives: We now introduce bounds the partial derivatives di and d2
introduced earlier. Consider μl, 2, J E H ((u) such that μ > Tt, and x [ū, u1.. Recall
di (1(,,)) O2 Oz and x) - (0.. 0z).
Since (() = (b)) we have,
J1 x mmax (1a)
< di (1,, x)) < x0
x 7t
and
2 di (7, x))
2
(7)
Tmin (14)
mmax (11)
Jmin (11)
Similarly, since,
dz(u,z) P-2 x v'(0,)
and d2( (0,)))
we have,
11 2 d2( max (11)
and
I 1t
< dz x) 5
I P
(8)
miin (14)
miin (41
m (4))
15

---

B.1 Enveloping the anchor and index functions under noisy estimates of the rewards
For every arm a E [K]. let Pa be an estimate of Ha satisfying 7i uul I c(p) and jı (Pa) Since E(m) Amin( the empirically best arm with respect to the estimates is the first arm. Also 4
let Na be the no. of times arm a has been pulled and (Na)ae(K)-
Enveloping the anchor function: As we introduced in Section 2 the anchor function is.
Σ ((,i), d(ja,, 31.
s ii, N)
a#1
where F1,a
Ni Ni Naje Ni+N.
Note that Ma T1.0 E H((p) for every E [K]/0), Therefore, using 60.
we have,
Om) (14)
(111 F1,a)
0 maxx (1)
(11 F1,a) )² 1,
S N)
mmx (1)
F1,, pal )2
mmin
(T1,a Pa )a
ax
Putting 11a
Nj +Noia
we obtain,
N1 N1
Omin (14)
N2
mmxx (14)
N2
a
S N)
1,
(9)
maxx
N?
min
N?
az
0
Now já1 F1.a
N. Ni+Na
(in Tha) and 31,a 15
Ni+No (Mn
N
Ma)) Using these, can say,
N2
N) θ
1,
(10)
N
whenever 174 - Mal I ((4) for all a E [K]. The constants hidden in the O(-) depends only on f and obviously the choice of the SPEF family.
Enveloping the index: Following the definition of empirical index I-(-) in Section 3 we define the index of any alternative arm [K]/(1} with respect to the estimates (7a [K]) and allocation N (Na : : E [K]) is,
(F, N)
Nid(ān, T1,)) + Nad(Taa T1,a).
Observe that, the empirical index I, (N) and index Ia introduced in Section 3 are, respectively, equivalent to the quantities W. (īNN,, (N)), and Wa(,, (NV), where (*(N) is the empirical estimate and ((N) is the algorithm's allocation at iteration N.
Using 66) we have,
(Ni T1,a)² 22 Na( (oa3)) S W,
20min((1) (Ni Ti,a)²
20 (1a)
No 13)
Putting $1,a
Nj NNooj we get, N.+NN
(i1 ) N.
W. & (M Taa² N₂ S W.(F.N)
which implies,
20 max (1)
N1 + No
20 (1) Ni + N.a
(p) Ma 2²(
NINa
(w) Mo + 22(H))² N,
20 max (10)
N1 + No
(4)
N + N
We define 4 (4) maxac[K]/(1) 4n Since E(p) S Amin (HO), we have,
(2)2 N1N.
(Amax (w) + 2E(H)))
N1
W.(ū,N) <
(II)
8amax (n) Ni + N₂
20 (1)
Ni + No
16

---

and Using the same notation, we used in [O0,, we have,
N Ni No.
Wa(,.N) @
(12)
for every arm [K]/[1].
Enveloping the partial derivatives of anchor function with respect to N: While analyzing the AT2 and LAT2 algorithms, we need to show that the anchor function converges to zero 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 evaluate the partial derivatives of g N) with respect to Na for different arms a E [
0g (1, N) - -EMm, N) N N.
ON1
(Ni + N₂)
a#1
0g èN.
N14. (Ni + N₂)
Va + 1,
(M, N) = f(,, a, N)
(13)
where 4a = u1 - Ma and
8 (d(
d2,011
d(H1 21, 21,a)d2(HH.) D1,a) (d(Ha:I1.0))
f(u,a, N) = dr d(Haa)2) 2=
+
v1.)
Using 8 and
we have,
da(H11 = O(u1 - x1,a); de(Pa, = O 101110-110 pa), d(HI)T11)) O((MI x1,,)) and d(Has @ pa)3),
where the constants hidden in O(-) depend only on and are independent of the sample path. Therefore.
f(1,0, 0, N) =
#1 11a
(P1
x1.0)
(Ii,a - Ma)2
(I1,a
14
Na
No
1
(14)
N1
N1
As consequence, we have,
0g
(n, N) = -
Σ
N
and
0N
N3
0g
No N?
Va + 1, ON,
N) A
(15)
C 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 3-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 (Na E Rz0 [K]), Ie R. =
(oo R a
[K]), and N 2 0. After fixing some instance μ SK (S is defined in Appendix B). we define the
17

---

following functions:
21, (N1, 711
(N, E
(E(K)(() (NN1
for a E [K]/[1}, (N
= N1d(11, (N1, N.)) Nad(Ma, - 7a.
and PK+1(N,N) = Σ
No -,-N,
KEIK]
where
N191 NaPe
F1 (N1, Na)
N1 + No
For every non-ymply subset _ [1]] we define the vector valued functions,
t BB N) = [ n)), ($.(N, I, 1)) $ (N,NI. = [ m)) I,(N,,I
(x+1(N, N)), and
denote kI/(1} (:) just using (b-).
In the definitions of Pg (-) and Φx((), without loss of generality, we assume that, the functions & (.) in the tuple ($ (-))))))))) D)EB are enumerated in the increasing order of B, i.e, have
B = {ai, 02. a| with 1 < < <02 <... < a then,
ΦB
11
Por: Loz
pay
agy
& pk+1];
and
きB 1
Pai
Paz
Bays
aimi
we define some notation that are essential for the lemma statement. For any A [K]. we use the notation NA to denote the tuple of variables (Na a E A). For some vector valued function G depending on N, denote the Jacobian of G(-) with aG respect to the tuple of variables NA using BN
Before stating the main result of this section in Lemma C.1
For any non-empty B S [K]/[1}, define B = B For every k > 1. O2 and 1g- respectively, refers to a k-dimensional vector with entries 0 and 1. We define ZB to be the set of tuples (N, 1,, N) with N E IRK I E R, and N Eso. which satisfy
$ N. 0
Lemma C.1 (Invertibilityy of the Jacobian). For all non-empty subset B S [K)/(1) the following statements hold true at every tuple (N, 1, 0K, in the set Zg,
1. The Jacobian 0e a. oN
invertible (N,1.0 1.0).
2. We have
04B a B
04 B
1 1BI+1
Σ n
0I
d(pay p1
al (N,1,0K)
3. The Jacobian
84 NN.
defined as,
04
84
UN
0 ((N B
x4x++1
04x+1
ON
01
is invertible at (, OK,
18

---

Proof.
Statement 1: The Jacobian 8 T
is equivalent to,
00, JNi
00,
00,
00,
DNa1
NNa2
2Na [8]
0041 aN1
D0a1
00
040
DNa1
NNag
NNa
(16)
0N
B
84
84 8Na1
84
84 a
8N1
NNa2
aNa
Now we observe the following properties about the sign of the entries of the above Jacobian matrix,
We have N 0 and Φ (N, 0x) = 0. This implies Ni 0 and maxaε[K]/[1) No. > As 2 0 for every i E (1, |B)..
result, using 15 we have 0th UN.
< O and B4
UN,,
For E f2.....
1}. in the i-th row, the only non-zero entries can be the first and the i-th entry. The first entry 00,; ON1 d(p1, #1,a, (N,, 2 The i-th entry is ON., d(pa, 2,,a, (NN1, Since we have N1 O, using (6. have d(pa L1 (N1, Na,)) > 0.
06.;
making the i-th entry positive.
Therefore, considering only the sign of the elements, the matrix in
16 is of the form,
+
0
+
0
+
0
(17)
++]
where the symbols ++, and + implies that the corresponding entries are positive, negative and non-negative.
We now argue that 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 E {2. 3, ... B }} in the first column zero. As result of these transformations, since we are subtracting non- negativee quantities from the first entry the first column, that entry remains negative. The matrix we obtain after this sequence of transformations has structure.
+
0
0
000
++
0
0
++
0
(18)
:
+++
Clearly matrix of the above structure has rank [B] + 1 and therefore invertible.
Statement 2: Using statement of Lemma
C.1
if we take
00
00
then we have,
UN
0Φ
0Φ
0 13
01
Note that, the RHS of the above linear system iee. its first entry and -1 in every other entry. Using 17 v = [U1, 02 +11 satisfies linear system with coefficients having the following signs,
90 g is B + dimensional vector with zero in ef
(--) u= + (+) + (+)ss + (+) +... (+) 0, and
19

---

for i (2, +1, (+)e1 + +++) (--).
where ++, and + represents quantities which are positive, negative and non-negative.
For every f2..... [B] + l}. we can eliminate v; from the first equation by subtracting some positive constant times the i-th equation from it. After eliminating v2, 03,.... B|+ from the first equation following the mentioned procedure, we will be left with an equation of the form (--)i1 = (+), implying in - 0.
Now the i-th equation of the system, for E (2..... 13 is.
0 a
11 +
Ui =
(19)
ON1
NNa.1
We know that, BN1 for every [K]/[1}.
0
and 08a.11
d ; F1,a
Nin1-NNo where 21,4
8Na,-1
No+No
Now putting the derivatives in T9 we have
d(11, + d( M,
which implies,
d1 U1
1/ 17
d(Ia: 1 11
for every E (2,....,IBI +1.
Now adding both sides for i E (2, B + 1}, we get,
|
B1+1
|8
d(11, 11,0
Σ
Σ
1;
(1,
1:
11
2
2=
1=
d(p1, T1,a)
Σ
dl
d(pa; F1,a)
01
d(pa; 31,a)
aEB
aEB
d(p1)
d(wa; Fi,a)
V1
d(po 21,a)
(since vı 50
aEB
(E(K)/(1
d(pas 21,a)
U1
aEB
where the last step follows from the fact that EeE(K](() U1 on the LHS, we have,
d(g.)1a) a(paaatia))
(N, 0k) +1 Taking
|B++1
Σ 0 S
Σ aE
d(pa: 21,a)
Note that the LHS of the above inequality same 1 since ((Ha; d(pa; p1), conclude the desired result.
1
00x 81
In the RHS,
8N
Statement 3: We have,
f aN
n 8T
3 ONN, n
06g 01
0 B O(N p.
0 .NN
06 k++1 81
17
20

---

We do the following determinant preserving column operation on a(N ml))'
04 B
d
0
U( B: I)
D B 1)
1)
aN
01
b. BB42
:|B1++
11: B|+1
where
a and
] (((Ng.))
respectively, denotes the [B] 2-th column and left
(1N :1IB|+2
:1:
(IB) + 2) (B + 1) submatrix of 00 (N
The above column operation gives us the matrix,
84
0 B|+1
8N
1 [B
-17 BI+1
86 UN
04 31
which has the same determinant as
D4 n (NN 1)
Therefore,
O 0(N B 1)
a n aN
FΦ n aI
det
B8I+1
det
UN
Using statement and 2 of Lemma C.I both the quantities in the above product are non-zero, making 8 invertible for every tuple in ZB. a(Ng..)
the Jacobian
D Proofs from Section 2
Theorem D.I 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 which call O.
min Σ
a= No
Va # 1, W..N,,Na) Nid(p1, Nad(pa, log 2.45
(20)
where N. 2 0 for all and each F1,a P1 No.No
N,+N,
The optimal value of the problem O is of the form T (M)) log(1/(2.46)), where T* is the
ciprocal of the optimal value of 1 If N = (N; : E [K]) is an optimal allocation solving O, then w Ebeto NE is optimal proportion solving (1.. Similarly if wt is optimal proportion solving then N (N: Theorem D.I implies uniqueness to the solution of which also implies uniqueness of the solution of (
Nº
[K]) with N w " (1a) is optimal allocation solving O.
Some notations are needed before stating Theorem D.I Let C K1/1 and B = B (1). Let -= (Ma [K]) SK be some instance with v maxaş11 Ma. Let (To a E B) each be strictly positive. If B" + 0 then let (N, E E20 : a B") be the no. of samples allocated arms in B" We define N1, as zero when EnEB' N₂
B G. Otherwise, we take N1, to the unique
Ni 0 that solves,
d(v1, d(va, T1.))
(21)
aEB
where Fi,a = 2y N No, Note that D + and EBEB' N₂ > 0, there exists an B with N N, > As result, the LHS of (T)) decreases from oo N₁ increases from 0 to co. This implies the existence of unique N1 0 solving (1).
21

---

Set N1,2 == m Lad(v1,Pa)'1
Theorem D.I. There exists unique solution Ni 2 and (N₂ 2 0: E B) satisfying
d(vi, 1 0 where Fi.e
VINT + Va
(22)
NI N
and Nid(v1,21, + Nº dVa, la
Va E B.
(23)
Further, Ni 2 ma 21 and each N 2 a(vay'))
Furthermore, The optimal solution to uniquely characterized by the solution above with B {2...., K} and each Ia log(1/(2.48) and constraints (20) tight, that is, indexes of all the
sub-optimal arms being equal to lo.(4)(..46).. Further, N max.e KJ d(vr
log(1/(2.66) and each
(02(1/(2.48)
N
d(Pa,Pi)
Proof: First observe that every solution Ní and (Ng E B) to the system satisfy N1 2 max 11, 21 and Nº 2 alv..ey.. for every B.
22 and
23
must
La
If B
* 0.
22 implies.
Σ d(v1,I1,a) BEB
d(v1, d(va, F1,a)
= 1.
d(va 21,a)
eE(K/((1
If E Na = O, then N1 0 = N1.1 Otherwise, we can find an E B with N₂ > O. d(vs.ss.a)
strictly decreasing in N1. As a result, by the definition of Ni,1 we have making ELEB [(v.))ia) Ni 2 NI,1.
Now, for every a E B, we have
la Nid(v1, (1,a) + Nid(vas11.a)
min (Nid(v1,z)) + Nad(va, zE|Pa,0]]
Note that RHS of the above inequality is upper bounded by (in(NN Ma), N (u, As result, for every a B, Na J(Pape)) and Nt 2 Ia This further implies, Ni 2 T.p.
max.cB TP(.p.) N1.2-
Now prove existence of unique Nf and (Nr
B). For every N₁ Ni,2 and E B, as Na increases from 0 to co, N1d(v,,II.)) + Nad(vo; 21,a) increases monotonically from 0 to Nid(p1, va). Note that Nj Nfd(Fi,P,) 2 (2,2d(v1,
La (by the definition of N1.2). As result, La- For every E B, we call that unique N₂ as (NN).. Observe that, since Ia > (N1) strictly decreasing in N1.
we can find unique N₂ for which Nid(p1, #1,a) + NN NNd(va.,
and if La- 0, then (NN1 0. Also, if arg maN "())
Jn then (N(12) oc and
lim oo (N1) MP)
La
We now consider the allocation where every arm E B has No (N1) samples, and consider the function,
((11,110)
h(N1)
Σ
d(va, x1,a)
Observe that, for all E B, d(v1,11a) is strictly decreasing for N₁ 2 Ni.2. Also if B is non-empty, d(Paiiia))
then every term d(p)=a1.)) d(va,ai,a) with N. > is strictly decreasing in N1. As a result, the overall function N1 - ((NN)) is strictly decreasing.
Moreover, as Ni increases to oo, (N1) converges to T for every a E B. Hence, h(N1) decreases to 0 as N1 xo. Therefore, if we can show that h (max (Ni,,, N2.13) > 1, then we can find a unique No 2 max(NN, 2 at which h I(N+)) 1, and can take N = Na(N)) for every 2 1.
La
E B. Following this, to prove uniqueness, it is sufficient show
22

---

If N1.2 2 N1.1, then some a E B has N. (N = co. As result, we have h(N12) = 0o 2
Otherwise, N1,1 2 Ni. 0, then by definition of NI,1, have
d( I(,)) =1 vi.a)
1(N1,1)
aER
Hence finish proving the first part of Theorem D.1
To see the necessity of the stated optimality conditions for O observe that we cannot have N = 0 or Nº = as that implies that the index Wa (Nt, N2 is zero. Further, if W (Nj, N2) > log (2..45)) the objective improves by reducing Na. Thus the constraints (20) must be tight. To see the tightness of (20) again note that the derivative of W, (Ni, N.) with respect to N1 and N.. respectively, equals (1, and dl ((a, T1,a).
Now, perturbing N1 by tiny с and adjusting each Na by d(m.
d( maintains the value of
Wa Wa 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 solution, the uniqueness of the solution above satisfying
the necessary conditions implies that this uniquely solves O.
To prove Propositions the following functions,
2.1 and 2.2 we need to use the Implicit function theorem. For that, we define
(1,1, 1,
J((N) s),,N) Σ
2i oo Na))
Y [1/[1}}
J, = Nid(H1, V1,a (NN,,,,,,,NN,,,, Na)) 2I
(N+,(N,N) Σ No N,
aE[K]
where N = (N, E R20: No N.+N.
a :
E.. and, for every a E [K]/(1}, (1,,,N1,
Using these functions, for every non-empty B C [K]/[1}, we define the vector valued function JB(N, [J1(N), ((NN,,)))BB. JK+1(NN
We call ((K(/()()) J(.). Recall that B denotes B U (1). For every 2 1, zero. Observe that, for every B C [K][1], JnN, = 4 & 0x, N), where the function p-)() is defined in Appendix C
the notation 0m to denote m-dimensional vector with all entries set to
Lemma D.I essential for proving Proposition 2.1
Lemma D.1. For every N > O and non-empty B C [K/(1), N (Ña E B220 a E [K]) satisfies Enen No < N, and Jn I,N) 0 -i then, the Jacobian of Jn(.) with respect to the arguments (N I) is invertible at (Ñ, N)..
Proof. We have JB JJ I, 4 T, Ok, N), for every tuple N, I,N, and non-empty B C [1] As result, Lemma D.1 follows from statement 3 of Lemma C.1
For every non-empty subset B C [K]/(1), define the function Jn(.) to be the first [B] + components of the vector valued function J.(+), or in other words,
jB(-) [J1(-), (Ja()))BB).
Observe that J.)(.) depends only on the tuple N and I, and doesn't depend on N. Also for every tuple (N, RK JB (N LB(N, Ox), where &g is defined in Appendix C
23

---

We now proceed on proving Propositions 2.1 and 2.2
Proof of Proposition 2.1
Observe that, for every non-empty B C [K] /[1), solving the system 2
equivalent to solving for the pair Ng. IB JB((NE N [B. .N) =
For every I 2 0, by Theorem D.1 there is a unique NB = (Na E R2o a E B) for which,
Bi+1- We denote that solution using (f) (we supress the dependence on Ng g for cleaner presentation, and also because we will be treating ge like constant in
J B: N n²), ),
rest of the proof). Since, JB(N,1) @B J, 0x), by the Implicit function theorem and using statement Lemma C.I the function + (1(() continuously differentiable. Also, we have
-1
JJB OND
0J
(
aI
(NNB
01
where the right most quantity is evaluated the tplle ((N) NF 1,0k). Moreover, using statement 2 of Lemma C. we have,
a B ON B
8 B 01
Σ (. aE I3
T N --1
Σ d(y 11)
As result, the function Enen NI) is strictly increasing in I with a derivative atleast for
EeEB T[a.A)]. Also, for 7 = O, the unique solution is (1 N1 and Na) every a E B. As a result, as I increases from O to co, EuSD (I) increases from N11 to oo monotonically. Hence, for every N Nn + EmEBe No. we can find unique ÍB for which EeEB Na(TB) + ELEE" N₂ N. Therefore (IB[B), TB becomes the unique tuple to satisfy, JB((N nr),, In, N). 0
Proof of Proposition 2.2; Recall that solving O in 20 is equivalent to solving ( With this observation Proposition 2.2 follows directly from the definition of (1), (1) and the second statement of Theorem D.I
D.1 Single variable formulation of the lower bound problem and intuition behind the anchor function
Now we show that the K-variable convex optimization problem defined in 20) can be reduced to single variable convex optimization problem involving only N1. To see this, observe that O is equivalent to the problem
min
Na
KE(K]
s.t.
Va + 1, WN Na) = Nıd(U1, + Nad(Ha, 21,a) = log(1/(2.46))
N1 + NaHa and Va E [K], N₂ 20. 0.
where 3i,a
N1 + No
This follows from the proof of Theorem D.I We first make some observations about O
1. Upon fixing some N1 > 0, Na Wa Na) is strictly increasing for every a + Moreover, we have
W. 0) = 0 and
lim W.(NI, N.)) = Nid(pi,Ha), No
As a result, every feasible solution of O must satisfy Nid(ui,Po) > log(11(2.46)) for log(1/(2.18) 16))
every a * 1, which implies N₁ > min d(p)).))

---

2. Using the preceding observation, for every a # and Ni unique Na such that Wa (N .Na) = (2g.1/(2.46). We use (a(NN) to denote that unique No function of Ni. Using the Implicit function theorem, it is easy to prove that the function N1 - Na (N:) is differentiable for every Ni minagi d(pi,pa) being
minagt d(pt.a.)' we can find
log(1/(2.48)
log(1/(2.46))
with the derivative
d(u,, Za (N1)) d(us Za [NNa) (N1))
N1/1 + (N
(NN)
where (N(1)
N1 + No(N1)
follows that O equivalent the single variable optimization problem:
O2 min S(N) del.
Ni + Σ (N(N))
a+1
log(1/(2.45)
s.t. N1 >
min d(H11 Ha)
Pict of fiW:)
Lower bound
Og abjective:
No. of samples arms Ni.
Figure 3: Illustrative plot of O₂ objective f(N,)
Further,
((N)) 14 Σ (N))
af
2( Ma
which is exactly negative of the anchor function defined in Section w.r.t. the allocation where arm I gets Nj samples and every sub-optimal arm gets N.(Ni) samples. Furthermore, f'(N1, is log(1/(2.46)) strictly increasing in N₁ and increases from -o to 1 as N₁ increases from min. d(H.,P.) .P... to cc. As result, O, is convex problem w.r.t. N₁ and the optimal N₃ solving O is uniquely identified by the condition:
Σ d(11, (N1)) azl
d(pa, (NN))
which is equivalent to saying that the anchor function must be zero when evaluated at the allocation where the first arm gets N₂ samples and every arm gets (NN1)) samples. Figure 3 shows illustrative plot of O 's objective (NV).
This observation also implies that the unique 3 which makes the 3-EB-TCB() policy in [66 asymptotically optimal is uniquely identified by the first order conditions: 1) the anchor function must be zero and 2) indexes of the sub-optimal arms must be equal. Hence allocations made by every
25

---

asymptotically optimal sampling policy must converge to these first order conditions. Both the fluid dynamics in Section and Proposition Section 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 equations (K 2 equations
maintain equality of K indexes and one more equation to make sure that all the entries in the K -ddimensional vector add up 1). Moreover, in Appendix D.I changing the variables of the problem O2 to capture proportion of samples allocated to every arm, it is not hard to prove that for every value of W1 (0, we can get unique proportion (Wi, ................................ WK) such that Eee[k] w and index of all sub-optimal arms under the proportion are equal. By the argument in Appendix [.I] the unique optimal proportion out of these infinite no. proportions satisfying equality of the indexes, 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 D.2, always converge to zero for the TCB(I) algorithm. As a result, allocations made by TCB(I) can be sub-optimal.
that the anchor function doesn't 't
E Proofs from Section
Proof of Theorem 4.1; We first prove all the steps of Theorem 4.1 except for showing the existence
of 3 > 0 and independent N such that (2NN) 3. That requires intermediate lemmas and done separately.
First suppose that contains singleton index b. Define (NV and N&(N) using IFT through the equations
Σ d(,)) ag31 d(pas (1,a)
(24)
and Σ. No N. For each a, letting L1,0 denote the derivative of 31,a with respect to N1, Ti,6 denote the derivative of 1 with respect to No. It easy check that
N1 N.
1
(25)
and each L get
N.4, (Ni NN.
Differentiating
24 with respect to N. observing that N₁ N1,
N2
Na (1 (1)1)) ND).
ap
It follows that
Nihn Easi Na + Nihs
N
Easi N. as stipulated. Also N₂ = Enge NoNo+Nihh
Now consider the case where g O. and 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 B is maintained along with 0, then the tied indexes will increase with N.
We have for b, E B
Nıd(u1, x1,) + Nod(us, 21,0) Nid(ui, 21,a) + Nod(Harziool
(26)
26

---

Furthermore, g = 0, i.e.,
d(pi F1,a) 1.
(27)
d(Ha, L1,0)
Keeping particular b E B fixed, differentiating with respect to N, (since for each a, by definition of T1,0s Nid (1,) + Nad' Nad" F1.a) 0) we see from (26) that
Nid(1, F1.b) + No' d(dd(u. x1,)) Nid(,,, - Na d'a T1.a)-
Using 26 again in the above equality,
d(ps: F1,6) No. Nº N Nid(Ha, (1 (Nad(Ma; x1,a) Nod(ub, Ni
(28)
d(pa, v1,a)
Then from we have that
N Σ Ml,
E NN 0.
(29)
aEB
(Recall that for each a, Li denotes the derivative of 1 with respect to N1 and Ti denotes the derivative of 21,a with respect to Na.)
Plugging 28 and 25 in 29
multiplying each term by N we see that Ní is ratio of
N₂ Nida,hh
with
M(N) + Noda,ohn-
Then,
MNN) + NohB
N2 N
N1hB
In particular, since, Σ. No and expression for (N.).. Since (N) > index is non-decreasing in N. Furthermore.
B follow. Statement 3 of Theorem 4.1 follows from 3
lim (N) = Nad(Ha: +00
To prove the existence of 3>> O and independent of N such that IÇ(N) > B, we need Lemmas E. (E.2) and (E.3). In Lemma E.3 we argue that the indexes in set B grow linearly with the number of samples. Since index for arm a E B are bounded, eventually indexes in set B catch-up with other indexes.
Some notation first. Observe that d(p1, x) d(Pa..)) x)) is continuous and strictly decreasing function of z E [Me. p1]. It equals d(p1, Ma) for I Pa and -d(Ha, M1) for æ #11 Let va (Pa. #1) be such that
d(u1, xa) = d(Has xa).
Furthermore, let
ā = arg max d(u), x1a)
d(pa: xl
Let :() be such that
d(pı,=(ā)) (K 1) d(pa, (a)).
It is guaranteed to exist since the ratio d( x)) (0, oa) is monotonic in
Next, let
dg 11 Fa
d(ā) = #1 x
and
Io Ha
x( Pa
Since K > 2, we have xr@) Ia. and d(ā) s dz.
27

---

Lemma E.1. Suppose that g = 0. Then,
Σ da a#1
N N (1 +(a)) N.
(30)
Lemma E.2. Suppose that g = 0. Then,
1. there exist constants H and D such that ha S H for all and d S fooor all a.
2. Further, there exists an à such that N& aN for some and the corresponding ha is bounded from below by positive constant.
Lemma E.3. Suppose that 9 O, and for B C [KK]1 the indexes are all equal and are strictly higher for the remaining set. Then there exists constant B > 0 such that
N1d x1,a) + Nod(pa; F1,a) (N) > 8
Proof of Lemma
F.1 Since = 0, follows that for each a E [K] \ 1,
d1.
S
du
Thus, 21,a 2 Fa. This in turn implies that for each G,
Ni Nod
The above follows from substituting for Tı,a in the inequality I1,a 2 To, and from the definition of da Moreover, since g = 0, it also follows that for each a + 1, <(ā)) 21,a. implying
N Nid((T)) S No.
Then,
N1
1+ Σ du 2N
aF1
and
N1 d(ā)) SN
and the result follows.
Proof of Lemma E.2 Recall the definitions of h2 and f(u, a. NN) from Section 4
Since, 9 implies that F1,a 2 Fa for all a, it follows that da d(faa, 2 Ia). In particular, for all
0,0 <D
for D max, d(pas =1
Further, d' (1(as x1,a) continuous in F1,a and bounded from above by sup San.a Sun d' d'(ua T1,a). Similarly, (111, bounded from above by sup,, San, Sum -d' (mi, a))) This implies that f(u, N) is bounded from above by positive constant and hence so is ha.
To part 2, observe from definition of æ(ū) that 21,a I xx(a). It follows that
N₂ 2 21d_2. Therefore,
N₂ 2 Nd. (1 + Σ da)-1
(31)
Again, F1,5 S x(a). Therefore, da "1pa, S x(pz, and d1a d(n1, x()).
28

---

Further, d' (Haa,T1,)) is continuous in 21,a and is bounded from below by
inf d' (J(aa, Di,a).
Similarly, -d" (J11, (1,)) bounded from below by inl inf -d' (111
Thus, [1,, a) is bounded from below. Further, since each N₂ S N1, NP/(NG + Na)² (1 + da) hence, hy is bounded from below by positive constant.
Proof of Lemma E.3 Recall from
31 that
N: 2 Nd (1+ Σ dd)
(32)
Also, recall the definition of (H,, N) and ha from Section
that f1,, a) is bounded from below by Because of 130 and 32p. and since Na S N, positive constant, and the same is true for ha-
i E B, recall that hg = E.EB bad Thus, hg is greater than constant times N. This ensures that N is bounded from below by positive constant. Since da is also bounded from below by positive constant, we conclude that there exists a 3 > 0 such that (N) > B.
a & B, then recalling that =(N)=Eest by a positive constant. This implies that as N increases by a positive fraction, so does each N₂ for E B. This in turn ensures that then hB is thereafter bounded from below by positive constant. In particular, after some delay we have (N) > B for some 3 > 0.
Na. we conclude that NZ is bounded from below
E.1 Fluid dynamics starting at y <
Proposition E. provides the ODEs by which the fluid allocations evolve in step 3 of the description of fluid dynamics when < O.
Proposition E.1. Now consider the case where g g< total allocations N, and B again denotes the set of arms whose indexes have the minimum value. Then, till 1 (NN) increases with N to either hit an index in B", or for g to equal zero, whichever earlier, (N) (EaE daal)= and for
B, N₁ d=a (Eaen dz.b)) -1 In particular, T (N) and each (Na. B), increasing functions of N.
Proof. Let i denote the corresponding minimum index. Recall that w" (w a E [K]) denote the optimal proportions to the lower bound problem. Consider Ñ. wh N₁. Recall that at these samples, indexes at this allocation.
wi
O and all the indexes are equal. Let denote the corresponding value of the
First we argue that N₁,- < <N.--
Suppose this is not true, then g < implics that for N₁ fixed, there exists an arm a so that N₂ < N.. else each N₂ 2 N₂ then since increases with N., we would have 2 0. This contradiction implies that index for arm a < T (NN. It follows that the index corresponding to in is < (N). Since the index increases with N₁, it follows that N;, < Ñ,
Thus, initially N increases due to increase in Nr,- Let B {iz}. Suppose, iteratively that B (ir...., ,1--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 B satisfies the relation Na T/ (N). Further, Σ.sB N' 1.
Thus, as N increases, each N₂ (NN, a E increases, so that 9 increases. Since all indexes corre- sponding to B" are constant, as N increases, either first or another index T, becomes equal to I INNN).
29

---

E.2 Fluid dynamics of the 5-EB-TCB algorithm (166)
For every 3 E (0,1) and allocation N (Na Rz0:0 [K]), we define the f-anchor function as,
N1
g (N;
Ene(K] Na
Note that, if ((NN; () = O, then 8-fraction of the total no, of samples in the allocation is allocated to the first arm. The fluid dynamics for the 3-EB-TCB algorithm (see (16) can be constructed similarly to that of the Anchored Top Two algorithm, by replacing the anchor function g(u, NN with the 3-anchor function (NN; B) in Section
Existence of fluid dynamics: Recall that, for every B S [K]/[1}, B denotes the set U [
Lemma E.4 and Proposition E.2 are essential for constructing the fluid behavior for 3-EB-TCB algorithm.
Lemma E.4. Given non-empry B [K]/[1}, some tuple N (Na E R20 E B) and
I 1 there is a unique uple Ng (Na E R20 : E B) which satisfies,
Ni B Σ Na. and aE|K]
every E B, Nıd(p1, Nad(pa,
where T1,a NoPt
N1+Na
Moreover, if we define N1,1 = E Na and N1 minae d(ui.Pa) then N1 2
11 N1.)
Proof. Proof of this lemma follows argument similar to the proof of Theorem D.I
First fix some 2 0 and N₂ N1.2- Note that for every E B, N₂ increases from O to co, N1d(H1, F1,a) + Nad(Ha, a1,a) increases monotonically from O to Nid(H Ma). Since Ni 2 N1,2 2 Au..p.. we have Nid(ui, ) 2 I. This implies, for given Ni, there is a unique value of Na for which N1d(p1, + Nad(pa: Ti,a) I. We call this value (N(N,) for every a E B.
Observe that N1 + N.(N)) is strictly decreasing function of Ni, and if Ni Ni.,, then there exists an E B for which (NV12) On the other hand, if N1 + (N1) > T...pp) for every a E B.
For every N1, we consider the function
N N ΣBEB (Ni) EnEB N.
h(NG;)
Note that h(N1; 33 is the value of g(N: 3), when the tuple N has N₂, N. (N;) for every B. Note that N₁ > hNNN: (3) is strictly decreasing for N₁ N1.2. Moreover, as Ni + co, h(N1; B) + 3-1 1 < 0. In the rest of the argument, we show that ((max(N1,1. N1,2) B) 2 0. After prove this, we can find a unique N, for which ((N:;8) = 0. Using this, we take N, = (N,, for every B obtain our unique tuple N B-
Now we consider two cases.
Case 1: If N1,1 2 N1., then at N1 = N1.1
N1, = Σ No & B(N1.+ Σ No).
oE (E/K)(()
As result,
N1.
NI,1 EneT N₂ + EnER NN(NN..) SB,
30

---

which implies h(N1,11 8) 2 0.
Case 2: If N1, 2 N1,1, then, as we argued before, there exists an a E B for which Na(N1,2) = co. As result,
N1. N1. + Eeen Na + EnED (N(11,2
=0
implying 33 0.
Proposition E.2 stated below is crucial for constructing the fluid dynamics of the 3-EB-TCB policy and is analogous Proposition 2.1 used for constructing the fluid dynamics of the anchored top-two algorithm.
Proposition F.2. For every non-emply B S [K]/(1) tuple NB (Na R20 B¹), and N 2 1-3 EneT Na. there exists unique tuple N3 = (Na E Rzo a B) and IB for
which,
N1 SN,
EN No = = N,
aE[K]
for every a E B,
Nid(uas vi,a) + Nad(Ha, = In, and
where Fi. NiØi + Nofo for every eververy E [K]/01}
N1 + Na
If we denote that tuple by N (N) and (NNN,, then the functions N - Ln( are continuously differentiable with respect N.
Proof. Proof of Proposition E.2 follows by argument similar to the one used in the proof of Proposition 2.1, by using Lemma instead of Theorem D.I] Observe that the B-anchor function g(N: is strictly decreasing in Ni and strictly increasing in Na. when Nı > 0. As result, statement of Lemma C.I in Appendix C Cholds true upon having.
iN n) g(N: 3) TJo
and defining the set 3g using the modified function B.
With the above modification, we can find a constant 7 > such that, 1
84 p. 8N
0 01
-Y < 0 for every tuple in Zg. then statements 2 and 3 of Lemma C.I also hold true for this modified FB. As a result, Proposition E.2 follows using Lemma E.4 by the same argument used for proving Proposition 2.T using Theorem D.I
In the rest of the proof we argue the existence such a constant 7 >
Let (va
B)
R
B1+1 be the solution to the system
04
04p
2N B
01
34, v We have aN,
05, of and N1 3 >n EnE(x] No. which after some algebraic manipulation implies,
( Ui Σ
0. [B]
vo
(33)
BEB
33 further implies,
Σ
V1 B
B =
Therefore proving that vi upper bounded by negative constant sufficient for proving the desired result.
31

---

For every E B, we have
dd. 0 ON, B 01
1;
which implies
Vi v1d(p1, + vad(pas x1,)) 1,
(34)
where 21,a
N1 + + We use a and aa respectively, denote ((11,T11, and di F1,0). Ni NN
For every E B, we can eliminate for 33 using 34
After this procedure, we get,
EaEB B da,a
-1 =
3 - Enen daya
EnEB da,a
1 Eaf1 dia Ja.a
ELEB da,a
(since d1 S d(p1,Ho))
(35)
3 1+ Eayl
diun.n.)
daya
Since N1 = 3 Ea No. using (6) we have da,a = {1) for all E [K]][1}, where the constant
hidden in (.)) is independent of N. As result, by 35 U1 [11). Hence conclude the proof.
Constructing the fluid ODEs: Without loss of generality, assume that the fluid dynamics starts from a state N where (NN; () = O. Otherwise,
1. If (N; B) > the algorithm gives samples arm 1 till (NN; () 0.
2. If gN: : 3) < 0, the 3-EB-TCB algorithm follows the dynamics in Proposition E.1 and finite amount of time.
reaches (NN; :)
Following Proposition E.2. the algorithm tracks the allocation N [g(NN at a given time N, where B denotes the of minmumm index arms. We now determine the ODEs by which the state of the algorithm evolves.
To simplify the notations, E [K]. we use Na, N2, In, and l'.. respectively, to denote N, NaNN), NY (nN) and I' (N). For every B,, we use Ia to denote (NV.. Also for every E [K]/(1), we adopt the notation d and aa respectively, for the quantities d(u,, and d(pa, II,a),, where 21,a Ni NoPa
g3 shorthand for gNN(NN; () at given time N. For every
No
For every non-empty B S [1] we define the quantity.
dn
Σ aE da
We now show the fluid ODEs in the following proposition.
Proposition E.3 (Fluid ODEs for 3-EB-TCB). Let assume the algorithm slarts from state (NN)) (No a E [K]) with EeE[K] No = No, No BNN and No > 0. Let B C [K]((1) be the set of arms having minimum index al given time N > No, The following statements hold true about the allocation (NN = (N.(N) : B) made by 3-EB-TCB algorithm.
1. The allocation N(N) (N. a E [K]] evolves by the following system of ODEs,
Ni B, and
for every be B, Ng ((1 (1-3)N-- EnEB Na)dg + Nodo.
(36)
N Nd
32

---

2. The index IB (N) of the arms in B evolves by the following ODE,
I'B = (1 (1-3 ELEB No
IB
dB +
(37)
N
N
3. There exists constant 0 such that, I'B On the other hand, indexes of the arms in B remains upper bounded by No Nod(pa: P1).
Proof. Statement 1: N1 = 3 follows directly from the fact that ga = 0.
By definition of B, have
Nidia + Nada,a = Nid1. . + Nod6,6
(38)
for every a, b E [K]. Taking derivative on both sides, we get,
Nid + Noda,a Níd1, Nyda,br
which implies,
d1 - d1 d1, Ni + da
do,b N₁- da.a
Nº
(39)
Using
38
we have
Nada, Noda,6 N1
d1bb d1,a
Using the above expression in 39 we get,
N Nada, Nodb, N' + do,b No- Nida,
du.a
Since N2- 3 and N1 3N (which follows from g3 0), the above equation implies,
N Nada, Nodb.b + da.a
do No-
Nda.
Adding both sides for a E B, we get,
Nadaa NodobE Nda.
1-3 Σ No
do, Σ d=1
EneR No
Nb
do + Nydan
N
N
which implies
No ((1 - 3)N Eaen Na)dg + Nodo.
Nd
Statement We know
1B3 = N,drb + Nydo, for every b E B.
Putting in the derivatives from (36.. we obtain,
11-3- EneB No
dg + Ngda,
1/2 = 3db,b +
N
N
Σ EaEB Na
BNd1 + Nods,b
1 - 3
dB +
N
N
ΣmEB Na
1B
11
dp +
(since N1 BN and I3 Tg for every b E B)
N
N
33

---

Statement For the following argument, the constants hidden in (()).(()) and (?()) are indepen- dent of N.
Note that N1 3N. As result, using 6). da,a (1) for every [K/[1}. This implies, can find a constant C1 > O such that dø 2 C1. On the other hand, using (2). we have,
Na
IB = θ Ni +
for every a E B. Since N1 = BN and N₂ - N, we have
B ((N)).
Adding for all B, we get LB - No). Therefore, LB 02 ELED No. for some constant C2 > 0.
Now using
37
I'3 (1-3- EaEB Na
IB N
dB
N
EnEB Na
EeEB Na N
4 1 1- B-
02
N
2 min c2) (1 ()- 3).
Taking min(ei, 02) > 0, we have the desired result.
Now for arms a E B", note that T1,a arg mingelva.mi) (N1d(11; + Nod(Ha:))) and Io = N1d(p1,411a) + N2 21,a).
As result, putting æ = μr,, we have S (i)
Reaching 8-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 stay bounded above by constant. As result, by some finite time, /g crosses the index of some arm in E B", after which B gets updated to {a}. The same process then continues with the updated B. In this way, eventually
B [K]/{}} and the fluid dynamics reaches the 8-optimal proportion w"(3) (B) E [K]) (8-optimal proportion the solution to the max-min problem ( with the added constraint W1 = 3) where,
N1 N
N. N
w1 B and
(B) for every [K]/(1}.
Applying the same argument as used to bound the time to reach optimal proportions Section 4 the fluid dynamics start at some time No with state ((N²) (Na(N9)= a E [K]), then it reaches stability by time atmost min.elk] (9)
No
Intuitions based on fluid dynamics applied to algorithmic behavior
F.1 Indexes once they meet do not separate
In the fluid dynamics described in Theorem 4.1 once the indexes meet thereafter they move up together by construction. It turns out that l'g (N) is positive. Below give heuristic argument that in our fluid dynamics, once a set 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, algorithm picks suboptimal arm, then it picks that again in periodic manner, which helps us prove closeness of indexes w.r.t. the algorithmic allocations (see Lemma 5.1 Differentiating g 0 with respect N, we see that,
N. (N N.Y²
N14. (
N Σ f4u, a, N)
Σ IN.fHH,,NN
(40)
N.)
34

---

Inductively, suppose that set B of indexes are moving up together and they run into another index b time N. Upon assuming contradiction, we can have neighbourhood [AV, N + AN] where the algorithm only allocates a subset C' C (b and doesn ' allocate to arms in D = [U - C + 0. Then the allocations follow the ODEs in (3) of Theorem 4.1 with B C, in the interval [N, N + ANJ.
Consider the probability vector (Pa E [K]/[1}) where,
a,, N) Pu Edz1 f(u, 6,
N.
(Ni+N.))
N. A. (N1+No)²
Note that Pa > for every a E [K]/(1}. We have from 40 that
N N1
N
Σ
Nu
Pa
(41)
Letting b = arg max.ec
(N)) N.(N)
(where (NV is the derivative in (3 of Theorem 4.1 upon putting
B C), we have
N1
Ni
Σ
Pa
N
N
(
No
Ng
(42)
aEC
where the strict inequality in (1) follows from the fact that D B ( Eoec Pa < 1.
# 0, causing
We now argue that D must be empty. Suppose instead that D + 0 and a E D. Because all indexes in B are equal at time N, we have, N₁ Nid((1 Z1,a) + N. Nod F1.a) _Nd((11 I1.6) + Nod(ps. 21,))
at N. Observe that for any arm E [K]/[1], derivative N Nid(p1, (1,a) Njd(pa, F1,a) (since, by definition of æ1 N1d2(H1, F1,a) Nadz (Ma, v1,a) 0).
its index with respect to N equals
Since arm a gets no sample in [N, N + ANJ, we have N = 0, which implies
14 = Nid(u,, in [N,N AN].
By our previous discussion
1 Nid(u 11,8) + Nyd(us. 21,)).
(43)
We now argue that Nid(u, v1.a) is strictly less than (43) at N. As result, if AN 0 is picked sufficiently small, index of b, which is the minimum index, outruns index of a in [N, N + AN]. Consider the difference
Nid(115111)) - Nid(u1, 1.0) - Njd(os = (1(41,71,))) d(41 - Nyd(us, 21,8). (44)
We want show that this is strictly negative. We consider two cases, Case I: If d((11,21,0) d( x1,6) 0, it follows trivially.
Case II: If d(p1, d(u1, x1,6) > 0, since N2 > O, using (42 we can upper bound (44 by
N1 N₂
N%
(d(u), M(11 d(pb, 21,))
(45)
Since the two indexes are equal at this point, we have
Ni (d((n, a(m1, Nod(us, Nad(Ha)Z1..)
Substituting this in (45). the latter equals
N% ( (o Nod(p x1,)) d(ps =1,))) -N,
No ((pa 0.
No
We thus have contradiction. Therefore, indexes of the arms in B {b) move together.
35

---

F.2 Proof sketch of Lemma 5.1
We consider the situation where the algorithm picks some amm a [K][[1} at iteration N and doesn't 't pick for the next R(N) 2 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) = ( for every E [K] and N 2 T good (see Remark G.1 in Appendix G.2 As result, R is atmost ((N)
for N 2 T good. Below, we improve the upper bound to O(N 3078 by refined analysis.
Let us define (N, Ñ + (NV for every j E [K] and N, 1. By our choice of T goodd we have [ N(V)) - O(N-3a/5 38/8) for N 2 gooo (see Remark G.1 in Appendix G.2
By applying mean value theorem on g(-) for N good, we have,
(N,( (1NN)
E ( AN, O(N- for every S R, 5t1.a
(46)
(N)
where (N,(N,) j [K]/(1)) probability distribution over the set [K]/[1, depending on N and (this distribution is not important to the discussion and is spelt out at Appendix G.6 Taking
AN, (N.a) and using (66.. we obtain,
be = arg max
N.(NN)
(N, (N.4)
Ni(N) + +((11-80/8) for every t S R. (N)
(47)
Observe that (46) and (47 respectively, resembles (41 and 42) from Appendix FT 0(N1-30/8) term due to the noise in ju.
except for
Applying the mean value theorem, we can bound the difference between the empirical indexes arm and b, at iteration N + by,
IN + 1) Is, (N+1) (M+)))A((N,)) (d(Ti, + O(N-- )).
d(ji1,
AN,,
(48)
Now d(F1, F1,)) ( T1dd.) < implies,
INNN + (N
(N,1). (N,t)-d(ps, O
Otherwise, if d( T1,a) (1,6,, 2 O, using 447 we have
IN + - (N +t)
(N) (((P1,Z1,)) - d(īi, T1,))) d(Abr d(Abb )loo)) + + (49) (N)
S (N,
Note that (48 resembles (55) in Appendix F.I Since In(N -1) S IN we can prove
using the mean value theorem that (N < Io, (N) + -(N1-30/5)) Now expanding the empirical indexes, we get
(N) 31.) + N.(N) d(Par s Ni(N) d(. No, (N) d(Fbr F1,6o)
+ +
Now dividing both sides by No, (N) and using the fact that (o) O(N), we have
(1(N) (d(Ti,) d(īi, F1 d(ūb, Fibi)) d(Tia F1 33/8).
N.(NN
No. (N)
(N)
36

---

Using the above inequality in 49 we have,
(N) d(Pa (..) + O(N1-
(N + - Io, (N +0) - (N.0)
No. (N)
(NA,, N N)
(N)
S (N,
d(Ha. F1.a)
(N)
+ -
(since AN, (N, S R (50)
whenever d(íi, F1,a) - d(p 21,b,) 2
Since (N) (N) and J (N) ~ My for all j [K] and N 2 T goood the coefficient of AN. (N,t) in (49) and 50 are - (1). As result, we can find constant C3 > 0, such that, for t t R and N
good
IN + (N++) < C,AN((, O(N1-3a/8)
(51)
Applying the mean value theorem and using the fact that can be atmost O(N), we can prove that, (1) implies,
(N +1-1) 1) - Iz, (N -) S +N
As result, we have a constant C+ > 0 such that,
(N +1 - Is, (N + 1) < CCANN(N, + C -30/8
(52)
Using (47) we can choose T good suitably, and find constants D1, D2 > O, such that, whenever N good.
R -
AN NN, R) D2R (see Lemma G.15 of Appendix G.6
We consider the case where R 2 max
2C, } D1, CsDa
x 13/88
Since R 2 D1N1-3a/8 we have
2C4 N-133//8 2C4 N1-3a/8
A N (N, R) D2R2 x
C2D2
C3
For notational simplicity, we use b to denote bR. We consider the iteration N + S where arm b was selected for the last time before iteration N + R. Then by definition of 6R and S, and using the above inequality, we have
2C
AÑ;(NSS) AÑ, R)
N 1--3/88
(53)
C3
Also, since AÑ.(N.)) = AÑ, and for every j # 1 AÑ,(N,)) Z AN, we conclude by. Therefore,
IN + - INNN + S 1)
In(N - 1) Ing (N -S
(using 52
S - CCAN (N,S) C4N1-3a/8
(since b bs)
(N, + C 33/88
20, N2-3a/8 + CcN1133/8
(using 53
S CC3
C3
The above inequality implies, the AT2 algorithm pulls arm at iteration N + S, even though IN S 1) INN 1) C1N1-3a/8
which is contradicting the algorithm's 's description. Hence we must have
2C' 11-30/8 0(N1-30/8).
R < max D1, CzD2
37

---

G Algorithmic allocations: non fluid behaviour
In the following sections, unless otherwise stated, the proof of the mentioned results for AT2 and IAT2 (2) algorithms follow 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 (2(-) notations, we imply that the hidden constants can depend on the choice of algorithm among AT2 and IAT2, instance μa, exploration factor (0, 1) and no. of arms K, and are independent of the sample path.
G.1 Convergence of algorithmic allocations to the optimality conditions
In this section, our agenda to prove the convergence of the allocations of AT2 and IAT2 algorithms to the optimality conditions mentioned in Proposition [.2 For ease of presentation we state the conditions uniquely characterizing the optimal proportion wt below according Proposition 2.2
di = and Va + 1, wi wid(u, x + wad(Wa; xi,a) I" (n)
Σ 1221
(Maa
(54)
will + Wal
where
Tia
and
Σ aE|K]
W =
wi + w/
Recall that for every E [K] and iteration N, (N) (N) denotes the proportion of samples allocated by the algorithm to arm a. Let (NN = (No(NN a [K]).
N
Recall the anchor function g q N-)) and index Ia(-) for every alternative arm a E [K]/[1). In Section 5) we defined the normalized index H-(-) of every a [K)/(1 iteration N as (a(N) N (NV).. In the next two sections, we prove,
1
21 21,a - d(par 21, (N)
([,,)(NN)
O,
(55)
and
max HA (N) H2(N)] - (
(56)
a.s. in Pu as N 20. Moreover, we show that, after random time of finite expectation, both the convergences in (55) and (56) happen at uniform rate over all sample paths. We prove these convergence results Proposition G. and G.2 below.
Proposition G.1 (Convergence of g to zero). There exists constants M4 2 1 and C independent of the sample paths, such that, if is defined as the iteration at which g g (-)) crosses the value after iteration max max Mb) (I;s is random time satisfying E, [Tb] < oo and defined in Definition G.1 of Appendix G.I.I. then N 2 Ts we have,
((,,N(NN) S 3o.8
Moreover, the random time To satisfies [T]] < <0.
Proposition G.2 (Closeness of the indexes). There exists random time Ts. (defined in Desinition G.4 of Appendix 1.1.2 satisfying Ty [Ts] < oc, such that, for N 2 Ts. every pair of alternative arms a, b E [K] [T) has,
[a(N) - 1000-(()) (NN) O(N1-3a/8).
Proof Proposition 5.1: By the definition of TstaMe Definition G.5 Appendix G.2
we have
T Tatable To, Tg. where To and T3 are the random times mentioned, respectively, in Proposition G.
38

---

and G.2 As result, Proposition 5.1 follows trivially from Proposition G. and G.2
Proof of Proposition G.1 is in Appendix G.I.1 We prove a detailed version of Proposition G.2 as
Proposition G.3
in Appendix G.1.2 Both these results are crucial later for proving the convergence of
the algorithmic proportions ((N)
(w (N) a E [K]] to the optimal proportions w = (w] E
[K]
Proposition 3.1 from Section
We prove detailed version of Proposition 3.1 Proposition
in Appendix
G.2
To prove Proposition G.I G.2 and later Proposition G.4 need to prove several technical properties related to exploration and the allocations made by the algorithms. The detailed technical results in Appendix G.4 and those related to the algorithmic allocations are in Appendix G.5 The arguments in Appendix G.I.1 G.1.2 and G.2 are self-contained, and we refer the reader the related technical results whenever necessary. For ease of exposition, provide below brief summary of the statements proven in Appendix G.4 and G.5
related exploration
Summary of technical results in Appendix G.4 and G.S
We summarize below the results proven in Appendix G.4 and G.5 as events happening between the non-decreasing sequence of random times To, Tı, 72, T3, and 74, which are defined in Appendix
pal S c(pu)N-3055) where e(m) > 0 (defined in Appendix B. is constant depending on the instance μ.. By definition, we have <(ps) S. 1 mingz11 (11 (a). As result, the first arm becomes the empirically best arm and stays that way forever after iteration To. In Lemma G.7 of Appendix G.3 we prove that E (Ta) < oc, which implies To < 00 a.s. IP..
To def. (N' 1 AA > N', max PP (N)
T def. max max (Texplo: Jo where Texplo < do is constant defined in Definition G.7 of Appendix G.4 After iteration Tesplo the algorithm consecutively does exploration a strech of atmost K Ieeattions Moreover, over a single such "epoch" consecutive explorations, the algorithm explores every arm atmost once (follows from statement and of Proposition G.5). Note that F, [Ti] < Texplo + [To]To < 0o.
T2 is defined in Lemma 1.11 as the iteration at which the anchor function g g( :) N()) crosses
the value zero after the iteration max (M, Ti (M1 2 1 is a constant independent of the sample paths and defined in the proof of Lemma G. By Lemma G.9 there exists a constant C1 2 independent of the sample paths, such that T2 S C1 max max[M, (i) As result, [T,]]]] S
C + F TTi) < oc. After iteration T2, the empirical anchor function g N()) remains bounded inside an interval of the form [-(1 dmin); dmax 1}. where d dmin (0. and
dmax E 00) are constants independent of the sample paths (see Lemma G.11j. Exploiting
this, we argue that both (N) and (K]/2( (N) become (NN) after iteration T2 (see
Corollary G.I..
4. T3 def. max{Ma, T2) 2, where M2 2 1 is constant chosen in the proof of Lemma G.12 and is independent of the sample paths. After iteration 73. whenever the algorithm picks an alternative arm E [K] (1)] then for every other alternative arm b [K][[1, a). we have No(N) 2 7N (N), for some constant y E (0, 1) independent of the sample paths (see Lemma G.12p. Note that E,, [Ty] I M2 + 2 + [Tb]
5. T4 = C2 (T's + 1) for some constant C2 2 independent of the sample paths, defined in Lemma [K] have (NV ((N) (see Lemma G.13). Note
G.13 After iteration TT, all the arms
that E,,, [Ta] < C2 (E + +1) co.
G.1.1
Convergence of the anchor function to zero
The following lemma bounds the fluctuation of g N) around g(u, N) due the noise in the estimate ÿ of μ. We need this lemma later for proving convergence of the anchor function g to zero in Proposition G.I
39

---

Lemma G.1 (Bounding the noise in g). For every N 2 T2 (where T2 is the random time defined in
Lemma G.11 and satisfies En oo), we have,
(N) N(N) g(u, N(n,N(NN) (N)) O(N
Proof. Using mean value theorem for function of several variables, we have,
K
Ög app
((((())N(()) - s(p, ((N)) -
(i. ((N)) [Ma(NN - Mal
where Pa lies between Ma and Pi (N) for every [K].
We define
(INN + (N) (NNN+ + (NNN)
for every E [K]/{1}.
Note that,
0g (p. N(N)) = Σ
di (1(11 f(A, a, Ñ) N1 + No
Ñ1
and,
d(Pa, 21,a)
azl
0g (i. [(N))
d(ji, 21, (1a; M(i a, N)
N.
Ya # 1,
(57)
0pca
(d(jaa;
Ni + No
(0,))) d(Ba.:11.a (d(pa.01,0))
where f(j,a, a, N)
+
and recall that d1 (-.-) and dz(:,)), respectively, denote the partial derivatives of d(-,-) with respect to its first and second argument.
By (6) for > T2, we have,
(N)2
d(pa, (1,)) ((01,- - -(a)))-A)))) ((N (N()2
By Corollary G.1 from Appendix G.5 we have Ni(N) = S((N) for N > Tp. As result, d(par 11))) [T] for N > T2.
Moreover, for > Ty, we have: Id (1))
=
|d1 (Pay 21,a)1 = 0(1) (using
|d (ūr, f1,a)l O(1), (d2(Aa 21.a) = O(1) (using (8) and ((P1,$1.0) 0(1) (using 6
As result, for T2, all the partial derivatives in (57) are O(1). Therefore, for N T2.
((()(),N(N)) - s(p, N(N)) = o
Σ nE[K]
[a(NN Tall -O(N-3a0
(58)
and hence completing the proof.
Halting of exploration: By Lemma G.13 for N > T4, every arm E [K] has
As result, can find constant N 2 T4. We choose M3 large enough such that, for every N 2 M3. X(N - 1) > Na, Then we have minla{(]1((1) (N - 1) > No for every N > max max T2 + 1}. As a result, the algorithm doesn't do any exploration after iteration max Ma, T4 + 1). With this, we define the following random time,
(0, 1) such that N.(N) 2 XN for every
[K] and
Definition G.I. We define T3 max ( (Ma, T4 1}.
Note that [Ts) < co, since, F,, TT] < co.
We restate Proposition below.
40

---

Statement of Proposition G.1 There exists constants M1 2 1 and C > O independent of the sample paths, such that, Ts denotes the iteration at which g( (()) crosses the value after iteration max Ma, Ts}, then for N 2 To we have,
g(n,, ((N) - CC
(59)
Moreover, the random time T6 satisfies E [To oc.
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 and M1 and show that g NT)) satisfies (59) at iteration Tg.
2. Induction: We show that, for every N 2 To. ((())((N))
1 CN-30/8 30/8 implies
A(, 1)){ s C(N + 1)-3a//
By Lemma G.1 we have a constant C₁ > 0 independent of the sample path, such that,
[(ā((N) N()) - N(N)) C.N-30/8 for N 2 Ts.
(60)
By Lemma G.13 have (N) ((N) for every [K] and N 2 Tg. As result, by (15 have constants C2, O2 > 0 independent of the sample paths, such that: for all N 2 To. and Na
No 1), (NV)
CCN-1 I 0g
(H, Ñ) S -C2N and
0N1
0g
for a E [K]/(1}, CN' 2 ON, (N, 2 C2N
(61)
where N (Na : a a [K]).
We use the constants C1, C2, and C as defined above in the rest of our proof.
Initialization: We choose C 4C1 C22 and M1 max(Mn M12, M13, Mu), where M41, M42, M43, Mas are defined as,
1. Ma1 2 1 is the smallest number such that, for every N 2 M41 we have 20,N NC 30/8 (N - 1
2. Ma2 2 1 is the smallest number such that, for every N > M12 we have C(N 1) 133//8
(C1 C2 -3a/88
3. M13 > 1 the smallest number such that, for every N 2 M13 have C(N 13-30/8 >
C2,N - and
4. M4r > is the smallest number such that, for every N > Mas we have 3Ca (N
1)-(1+ 4)) < N
By definition of To. g(ū(-), (N)) has opposite signs at iterations To 1 and Tg. Therefore,
((T(T)) < ((((TT), (T -i N -1) - 1))
((m.)(
C.I 3a/8
CC 1) 30/8
(using 60
(TH,)((TT) A1, N(T 1))
+3CTT 30/8
(using the definition of Ma1).
(62)
41

---

Let E [K] be the arm pulled at iteration Ts. Applying the mean value theorem we can find Na between NT, 1) and Na (T)) can take N₂ (T(T)) for all # a, and define the tuple = (No)e(k)) such that, 622 is bounded by.
0g ON,
(u, N)
+ +3C,To 30/S
Using 60 and the above upper bound, we have.
g(v, (N(TT)
- ((1,, N(T6)) ((ū(T6). ((6))) + (TA N(TT))
Og
S CITE 3a/8
+
(m, Ñ)
+ +3C 3a/8
NNa
4C, To 30/8
+ChTE (using (6T))
- (4C1 + C2)TE
3a/8 = CT 38/8
Note that at given iteration N the algorithm only see (T)NNNN(N) By 60 for N Te, ( N) and ( N) may have different signs only when (( CiN 30/8 Based on this, we consider two cases.
Induction:
Case I: Iø(n, ((N)) S N- We assume a E [K] to the arm pulled in iteration N 1. Using the mean value theorem, we can find No [a Na (N + 1) can take No (N) for all b * a, and define the tuple Ñ = (No)bE(x)) such that,
104n N(N +1)) < p0n, ((N))(N))))))))) +
0g ON
(1, NT)
CIN-3a/8 C.N- +CN S (CI + NNC 3a/8
where (1) follows from
Note that N 2 To 2 M4 2 M12 By the definition of M42, we have
Jol, Ñ(N 11)| s (C1+ + C2N 30/8 < +4C1 + 30/8 C(N + 1) 300/8 for every N 2 To-
Case H:: 11(1,, [NN) > C/N-30/8, this case (N), (NN)) and g(v, N(N)) have the
same sign. Let a has been sampled from in iteration N + 1. Using the mean value theorem, we have N₂ E NN),,, (N + 1)). can take N₂ = (N) for all * a, and define the tuple Ñ (No))e[K)> such that,
Iu N(N + 1)) O(N.NNNN + Og
ON, (u, ().
(63)
We first consider the case when (Me. N N(N) > 0. After the algorithm ((N(N),NNNN) > 0, pulls the first arm. As a result, by (6 and 63). (()) decreases in iteration N atmost by CGN-1 and atleast by C2N-1. Now there can be two possibilities:
1. If g(u, N(N + 1)) < O, we must have g(u, N(N + 1)) > -C Since
N 2 To 2 2 M43. we have
> C% N-N by the definition of M43. As result,
(N + +1) - - C(N + 111-3//3 3a/8
42

---

2. If g(u, NN + 1)) 2 0, then g(H, N(). has moved towards zero by atleast C2N-1. Whereas, by iteration N + 1, the interval CN -3a/8 CN has reduced from both ends by
3Cx
CN-3a/8 C(N 1) 1)/8
Since N 2 To 2 M4 2 M11. by the definition of M4s. we have 3Ca (N + 11 ))) C2N 8
for every N 2 To. As result, N 1.
ensure g(u, N(N + & C(N 1) 1)-3a/t iteration
In the other case, when sv, N(N) < O, the algorithm sees ( N(N) < 0, and hence pulls some arm a [K][[]]. As a result, by 66) and (63) g(p, N.) increases in iteration N + atmost by C2N and atleast by C2N-1 Then we apply the same argument as for the case g(M, (NN) O, but by reversing the signs. Therefore, the inductive statement holds true for this case as well. Hence (59) stands proved.
TB has finite expectation: By Lemma G.9 can have constant C3 > 0. such that To < C3 (M, T3J. As a result, since E [7g
oo, we have [Te] S CM + (T(TT)) oo.
G.1.2 Closeness of the indexes
Lemma G.2 is 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 Tg is the random time defined in Proposition G.1 and satisfies Ex [To] < co.
Lemma G.2. For both AT2 and IAT2 algorithms, there exists constants Ms 2 and C₁ > independent of the sample paths, such that, for every N max[Ms, To if the algorithm picks an arm E [K] iteration N, then it again picks arm a within the next [C,N1-3a/5 iterations.
Proof of Lemma G.2 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- max Ms. To).
Note that [T]] co, since [T
Definition G.3. For every M 2 1, define T7,M max M, Tr}, and T8, as the smallest iteration after T7,M by which all the alternative arms [K](11 have been picked atleast once by the algorithm.
Below state detailed version of Proposition G.2
Proposition G.3. For every M. 2 1, we have [T M] < oo and Ex(Tss < co. Moreover, for every M 2 1 and N 2 T8.M. every pair of arms a, b [K][1}} satisfy,
[a(N) 1-() O(N -30/88
where the constant hidden in OC-) is independent of M and the sample path after T7. Definition G.4. We define Tg TT.1, where Ts,1 defined according Proposition G.3
By the defintion Tg above, Proposition G.2 follows trivially from Proposition G.3
The following lemma helps us to bound the deviation of the empirical index I, (N) from the index Ia (N) due the noise in the estimates μ., for every alternative arm [K]/(1).
Lemma G.3. For E [1]((1} and N 2 To. we have,
I_ (N) - Ia (N) = O(N1-30//)
Proof. Proof of this lemma uses mean value theorem. For any [K][11}, upon expanding the indexes,
(N) [,N) < Ñ, |d(T,, Fr.a) 2(H1.11,0) No |d(P,, Fi,a) ) d(pa; #1,a): (64)
43

---

where N1. 11. Pa. and 3i,a are evaluated at N. Since No S N, the difference (64 is bounded above by.
(N) [a(N) N. (11(71, d(u1, x1,a)) [d(Pa; F1,a) - d(paa 01,a)))
Now considering the first term in the RHS, and applying mean value theorem, we get
N1
F1.a) (1,101100)) = di (e², F1,a) + d2(ii,, 11,a)
1741 141
Ni No
No
01(01,01,a))
1ita
Mal:
N1 + Na
where Aa. respectively, lie between 11, M1, and Pas Pas and ii,a Nola Using (8) all the partial derivatives in the above upper bound are O(1) for N 2 To- Therefore,
and
No+No
[d a1) - (011,,1,00 = O (174 - 1 + lita Pal) ONN
(65)
Following a similar procedure, we can argue using 7 and (8), that the partial derivatives of (ī F1.5) with respect to Ai and μi are (1) in magnitude. As result, using the mean value theorem,
a((aaTT1.0) - d(Ha, F1,a)l = O(N
(66)
Therefore, have,
(N) Ia()] = 1(N--33/88)
for N 2 To and completing the proof.
Proof Proposition G.2 We have E, [77,M] S M + [T,[TT] < oc. By Lemma G.13
(N)
(NN for N 2 M..M- Hence, by the definition of T. there exists constant C" > U independent of M, such that, for every M 2 1, T8.M S C'T7,M M. .. As a result, E, [T..M] I C²E, [Tr,M] < co.
Note that 7 = 77. Also, for every M 2 1, Ts.M 2 Ts.1 = Ts (T's is defined in Definition G.4 is sufficient to prove the proposition for every N 2 Tg.
We now argue for the algorithms AT2 and IAT2 separately.
AT2: We consider any two alternative arms b E [K]/(1), and define the time (a, as,
(N) min { = IN +t) (N +t) and (N) IaN) have opposite signs
Note that N + Ta. (N) must be before the iteration after N by which the algorithm has picked both and atleast once. By the definition of T; and Tg, for every N 2 Ts, alternative arms in [K] /1)
has been sampled from atleast once between iterations T7 and N. Therefore, by Lemma G.2 we
have (NN = O(N1 3o/8).
Since I, (N) (NN) and (N + Ta,b(NN) - IN + (o,((N) have opposite signs, we have,
(NV - [NN) < (I) - Ix(N)) - (I + +ab(NN) - Io(N + T (N)))
< Ia(N + (.,) Io(N)) + II(N + Fo,) Io(N)]
< [N(N + (a.((N) - IN(N) + |4ON + Ta,o(NN) - Io(N)
O(NN -53///)
where the last step follows from Lemma G.3
Now,
0 O(N + Faa)(N)) -Bm//) = o ((N (N++O(N1-3011)) 1-3a/8) = =O(NV-30/1)
44

---

Therefore,
v LaV + Fo,(((M) - La(NN) (66N + Fa.((N)) 16(N) ((N1-30/5)
By Lemma G.3 we know
[T((N) Io(N) S [I,(N) Is(N) O(N2-3a/t). Therefore, the
above inequality implies,
(TN) - [
- (N) - I2(N) + O(N1-30/8)
(N + Ta,b((N) [.N]] + |T(N + Fab(NN) To(N)
O(N1-30/8)
(67)
Using mean value theorem, for j E {a, b), we have,
01, ON;
(M.Ns)) Tab(NN)
(N + Ta,(NN) - 1(NN -
Σ
(68)
iE(1:]
where N, Nc(N), No(N To,b(N))) for 1,
We know,
01, (,1, = d(H1. and ON, 0N1
01, (g,, = (1.);
where 21 M Note that both the partial derivatives above bounded from above by
N1+N,
max (d(M), d( )1)), and therefore O(1). As result, since (a, = O(N1-3a/8) we have,
INN + Tab(NN) - 1(NN S O(N2-30/8) for = b.
(69)
Using
669
in 667
get
[laNN) - [[N) O(N25)0/5) for N 2 Ts.
IAT2: First we define the modified empirical index of every alternative arm a E [K]/(1) using the notation [(m) (N) as,
(N) Ia(N) + log(
We define the time Ta,b (N) as,
(m))
(m)) Ta.b (N) min t 1
Immi (N +) - -I(ma) (N t) and
I((m) (N) I((m) (N) have opposite signs }
Note that, for every E [K]/(1), mm) (N) differs from (N) by atmost log(N) (N) and (N) differs from (N) by atmost ONN1-30/3 for N 2 To. Therefore,
[I(m))
(NV) = 1 133/88 for N 2 To and every a E [K]/[1]. (N) (N)
Now N + (m) (N) must be earlier than the iteration after N by which the algorithm has picked Ta.6
both and b atleast once. Using the same argument AT2, by Lemma G.2 we have Ta,5 (N) (NV) O(N1-3a/8). Also, following the same steps as AT2, by replacing the empirical index I with the modified empirical index [(m) for every alternative arm, we obtain,
(m)) (N)) - (N)) + 16(N+TT (m) (N)) [oNN + O(N' -3a/88). (.N [(V) < [N + -T,
45

---

Using the mean value theorem, since the parital derivatives of la and Io with respect to N1, No and No are (1), we have
[N + (m)) (N)) (N)) 1 & (Fa7 - for j - a,
From the last observations, we conclude
[NN - (((N) s O(N2-3a/t) for N2 Ts.
G.2 Convergence of algorithm to optimal proportions
In this appendix we prove slightly detailed version of Proposition 3.1 from Section 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 u. as the no. of samples grows oc.
For every M 2 1, we use T7,M and Ts, as defined in Definition G.3 in Appendix G.1.2 Recall that
T7 17,1 and T's 1s, By Proposition G.3 we have E,, [Ts. cc, and T3.M M.M T for every M 1 1.
Recall that w" is the unique optimal allocation according to Proposition 2.2 and (NV (Wa (NV)
E [K]) with (.(NN (N) is the algorithms allocation at iteration N. We now state slightly
detailed version of Proposition 3. from Section 3
Proposition G.4. There exists constants C1 and M& depending on μa, a, and K such that, for every N 2 Ts.Mo and a E [K]. we have
(a( - will S 3a/88 and (aa Hal S e(u) 3a/8
where e(fx) is constant depending only on ia and defined in Appendix
Detailed proof of Proposition G.4 in Appendix G.2.2 and relies on using IFT.
Below we define the random times T good and T sstables which are mentioned in the statements of Proposition 3.1.3 5.I and Lemma 5.1 from the main body of the paper.
Definition G.5 (T (Tstable and T goodd) We define T good T7,Ma and Tstable Ts,Ma- where Mg 2
is introduced in Proposition G.4
Remark G.1. Note that, by definition, Toood 2 T4, To- As result, by Proposition G. and Lemma
G.13 ((,,N(()) = =ON and N,,NN = O(N) every j E [K] and 2 T goood-
Proof Lemma 5.I By the definition T7,M; Tg.M Appendix G.1.2 and since
T Toood = TT.Ma, Tstable Ma, every alternative arm in [K] gets picked atleast once between the iterations Toood and Tstable The other part of the statement of Lemma 5.1 follows from Lemma
G.2 because Tgood 2 T7.
Before proving Proposition G.4 in Appendix G.2.2 we find tighter upper bound on the time to
reach optimal proportion T Tstable the following Appendix G.2.1 I While doing this, we identify similarity between the time to reach stabilty in fluid dynamics and that for the algorithm.
G.2.1 Bounding time to reach stability
Lemma G.4 G.4gives an upper bound on the time to reach stability for the algorithmic allocations. We define min min,e[K]/(L) w
According to the discussion in Section if the fluid dynamics has state N(T good) at time T good, then
hits all the indexes and reaches stability by time atmost
Tgend whtn
In Lemma G.4 we argue that, the
algorithm also approximately reaches the optimal proportion w by atmost
good iterations.
46

---

Lemma G.4. For every M 2 Ms (M& is constant defined in the statement of Proposition G.4
T7.M +1
Ts.M S
CIM -3/88"
Winn
which implies
T good +
staalle
W C₁ M -a/8""
Moreover, we have
T8.M
1
lim sup
a.s. in IP m.
M-+00
T7.M
W
Proof. From Proposition G.4 it follows that, for every M 2 MB and N 2 T8,M 2 To,Mo: we have,
max aE(R]
W (N) will S CNN 33/8
(70)
Since Ta.M is the first iteration after T7.M by which every alternative arm has been picked atleast once, we have some arm a E [K]/(1} such that,
(T = Na(T7,M)+1 +1 S T7,M + 1.
Now by 70 we have
33/8 T. (T 2 (w, - CITS,M 3a-33/88 ITs.M 2 (witnn CC.M CI.M-3a//8
Combining the last two observation, we have,
T7.M
Ts.M S
a.s. P. C₁ C-M- CcM--ay 30/8
w min
for every M 2 Mg. Since T T7,M - 00 M in jus have,
T8.M M T7,M
lim sup
<
a.s. in P.
w
G.2.2 Proving Proposition G.4
By Proposition G. and G.3 there exists a constant C independent the sample paths, such that (NN) (wo (NV) [eE[K] satisfies,
d(H1, F1,a (N))
10(H,5(N)) =
-1 - CN -3/88
and
dE(K]/(1 d(Has 21, (N))
[TaNN) I(NN)
< CN- 30/8
(71)
for all N 2 T3 a.s. in F.
Proof Proposition Gelrel on using the implicit function theorem. Before proving the proposition, describe below the framework over which apply the implicit function theorem. We define the following functions,
d(p1, (1, wa)) 4 (w,,) g(u,w) - 111 Σ
7/
di (Wi, Wa))
affl
for a E [K]/[1} (a I, n.)) [x+1(w)
Wa(wi, I na.
and
Σ Wa 1,
ac[K]
47

---

where w = (Wa)nE(K) E R E [K]/[]}, B1,a(ur, wa) 2e tw wad(/as (Tlaaa:1,aa (oa1((11,w))
= (aa)e(()) E R I E R, and for every and Wa(wi, wid(H1, Fi wal)
Ha
Using the functions defined above, we define the vector valued function L (w,, 17) as follows, T (w. T.n) 1h (w: n), V2(w, n), Va(w, I,m),
VK (w, 1, n,,. (
y maps tuples of the form (w, (w.1.n) E RK x R R
to
RK+1
Its easy to observe that for every w = (wa E [K) E R satisfying Exe(k [k] Wa = 1, and I E R.
there is unique 77 RK for which (w, I, n) 0 We refer the quantity max.e[K] |aal as the violation caused by the pair (w, I) the optimality conditions in 54).
By (54), all the alternative arms in [K](11} have equal normalized index under the optimal allocation w Let
wx) for every E (1). Then Proposition 2.2 implies (w² I*) is the unique tuple satisfying
V (w 1" (k) = 0K++-
To prove Proposition G.4 we need the two technical lemmas: Lemma
G.5 and G.6
Let us define
| 30
ma [a for every E T
Lemma G.5 shows that, the set allocations satisfying the optimality conditions in (54) upto maximum violation of > 0 shrinks to w as decreases to zero. In Lemma G.6 we use Lemma
G.5 and IFT to argue that if the perturbation vector v) satisfies || S 7/max where 7/max > is constant depending only μ4, then there is unique pair (we, I) satisfying L (w. 0k+1- Moreover, the function mapping a perturbation vector E 1-mmax Mmax to the unique pair (w,
solving 58 (w, n) 0x+1 is Lipschitz continuous.
By (1).. the violation caused by the algorithmic allocation w (N) to the optimality conditions in (54) converges to zero
now easy to see Proposition G.4 follows from Lemma G.5 and G.6
uniformly at rate -3N-))/8) We wait for sufficiently many iterations such that, the violation becomes smaller than 7maxx. Then using Lipschitzness of the allocation as function of perturbation (proven in Lemma G.6,. we have ( lloo O(N -3x/8).
Lemma G.5. For every r 2 O, we define the quantity.
dist(w" ,)) max { max w' 1loo |I r W R I R, and
3 n E [-r,r] such that IwwIIn) 0k+1 }
The following statements are true about the mapping r + dist(w" ,r),
1. (ist(w",,)) 00
2. dist(w",r) is non-decreasing r, and
3. lim,-40 dist r)
Proof. Statement 1: Statement 1 follows directly from the fact that (") is the unique tuple satisfying (w"" 0*) = 0 as proven in Proposition 2.2
Statement 2: Follows directly from the definition of dist(w" rr).
Statement 3: By statement 2, lim dist(w" r) exists and is non-negative. We consider contra- diction to statement and assume that lim,- dist(w",, ,)) = > 0.
Since + dist(w",r) r) is non-decre,,ing, we can construct decreasing sequence (r, h2 such that, for every n 2 Tn O, (ttw""rra) 2 d, and lim, In 0. As a result, using the definition of dist(w"", r), we have sequence of tuples ((wn, In, mn) such that,
for every 2 1, || Tn.
(( Ln mn) 0K+1s and
48

---

lim inf max [|ww, - wwll loo 11 r 2 d. 727000
Since (K+)(w,)) O for every 2 1, the whole sequence (w,, (11) lies in the set
(wI. wk) R
Σ KE|K]
wi =
which is compact with respect to the norm 11-1|0.
Let for every n 2 1 and a E [K], wa.n and Na,n be, respectively, the a-th component of the vectors wn and 7h. For every n 2 and [K]/[1}, we have In Wa (Wi,n ) na.n. Since Wa(::) always lies in the interval [0, d( (a) + d(Ha, [I]] and MM,,l Tas we have
In I d(ui, Ma) + d(Has M1) + Tn for every n 2 1.
By our assumption, we already have + O, which also implies, the sequence Tn is bounded from above. As result, In also bounded. Therefore, we can have convergent subsequence {Wwne In J221, with limits Wne + w and In + I' in the -norm
For every k 1, have T (W In Mng 0x+11 As result, using the continuity of (+) with respect to its arguments, we have (w'' 0x) = 0x+1, implying w/ is an optimal allocation for the instance μr.
Hence, our assumption lim in max [[ww, w I In r0} 2 d implies max ||w| w' || lo - 2 d >> O, which further implies w' * w². As result, the instance za has two distinct optimal allocations w' and w", which contradicts Proposition 2.2
Lemma G.6. There exists Tmmax 0 depending only on the instance μs, such that the following statements are true,
1. For every 17 [-aaa Tmnxx] jK there exists unique tuple (w. 1) R 1R which satisfies, (w, 0k+1-
2. For every n [-Tpaxx Muax " we call the unique tuple mentioned statement as ( (n), I(n)). Then the function
I): Mmax Mmmx K + R
R
is L-Lipschitz, for some L
> 0 depending on the instance μ..
Proof. By Proposition 2.2 we know that the optimal allocation wh is the unique allocation satisfying,
(w 7" (x)) 0K+1
for some I* O. Note that & w m) (w, I, I,n, 1) for every tuple (w,Inn) m)), where & is the 84 function defined in Appendix C By statement of Lemma C.1 the Jacobian J[.. of the function (w, I, 17) invertible the tuple (=,,~",00'"
Therefore, applying the Implicit function theorem, we can find 8,, 81 > O, and continuously differen- tiable functions
(w (.II(() (-8o, + Rk 20
x
such that,
w(k)) w², ((0x) I*, and
2. for every (-ôo, k (w)()) ((n)) is the unique tuple in R x IR to satisfy,
max (w)(() w [[m) } < 81 and (w(m).I(m))) m) 0K+1
49

---

(N(N) By statement 3 of Lemma G.5 we can find 82 > 0 such that, dist(w".. < 81 for r E [0, 62). We define Mmax min 6u
j-
2
By the definition of dist(w",,) for every 7 E [- 1-Mmaxx Mmax jk if a tuple (w,I) satisfies (w, 17) 0 KK+1 then also satisfies max w w 1l00 r*1 ò1.
On the other hand, by IFT, since Mmax < do. (w) (n)),(m)) (m)) is the only such tuple possible. There- fore, for every 7 [-Tmaxx> Tmnax! (w)),, ((n) is the unique element in R 22 x R such that L (w)(), v7) = 0K+1- This proves the first statement of Lemma G.6
Since (-), I()) continuously differentiable in (-00, every component of this mapping must be L-Lipschitz for some L 0 in | -- du equipped with -nomm. We can take L to be the maximum of the [|-Ilı-norm of the gradients of different components of (w7,,, over the set Since the gradients are all continuous, their ||-|| -norm must be bounded in compact
60 do
60 5o1 K and hence oo. Therefore, the second part of Lemma follows from
set like 2,
assumption 7/max 2
We now proceed on proving Proposition G.4
Proof' of Proposition G.4; Recall that in Section 5 for every a E [K][[]], we defined the normalized index (N) LaTN
Taking H(N) = H2(N) = N let ()) be the unique E IR K to satisfy, v (NN)), ((N), = 0k+1-
Note that for every a [K] (1), we have Wa(Wi(N): (a) Ha As a result, by 71 we
have [[V I CNN for all N Ts.
Now we pick Mg 2 1 large enough, such that,
CM 3a/8
Ammax
where 7max is introduced in Lemma G.6
We define Tstable Mo. Note that 7 Tttalte 2 TB 2 To-
As result, by the definition of To in Appendix G.3 we have max [No(N) Mal --n/) for every N Tstable-
-3a/8
Now, by 71 for N 2 Tstable the allocations (NN) satisfies, & H(N) ((N)) 0x+1 with
[ & CN-33//8 < CM. 3a/8 < Mmaax.
As result, by Lemma G.6. we have
(NN = (ū()) for every a E [K], and 2 Tatables
where ( (.) is the a-th component of the vector valued function w() introduced in Lemma G.6
By Lemma G.6 for every a E [K]. (.(+) is L-Lipschitz in [-mmaxx Thaax]* K equipped with |1 norm. As a result, for N 2 T Tetable. we have,
max (N) wil = max [Ta (T)))) - W. (0k)l - LI( - 1K K
KE(K]
= [|] S LCNN-3/
Taking C1 = LC', we have the desired result.
G.3 To has finite expectation
In Section 5 we introduced the random time To as,
To min
N'
v 2 N', max [E(K]
[T. pal S ( 33/8
where E(π1) is positive constant defined in Appendix
B and depends only the instance μ.
50

---

Lemma G.7. The random time To satisfies E [To] < oo and hence To < 0o a.s. in Pa
Proof. To avoid notational clutter, let IP 1P and e(px). Then for any N,
P(To N 1) S P 3a E [K], (Na pa eNN33//8
< Σ
(Paa Mal > EN-33//8
aE[K]
Σ
E
P (lio. Mal > cN-3a/8)
aE|K] (NN-
where Pa,t denotes the empirical mean of l i.id. samples drawn from the a-th arm, and the last step follows from statement 2 of Proposition G.5 which says (a(N) 2 No C₁ for some constant C1 > O.
Using Chernoff's bound (like in the proof of Lemma 19 of [11). have,
(lia.t Mal > eN eNN-8a/8) I P (Matt > Ma + eN eNN Sa/8)) + P (Must < Ma cN-33//8
I exp (-t-d(ua ENN (ao) + exp (-t. d(Ha- eN -3/88 (Ha))
(-t. -tnminn min d(Ha eN -NN-Naafe 3a/8 Ha), d(faa cN ,nam))
< 2 exp
Using 66. we have a constant C2 > O depending on the instance μa and such that,
min (dlie + eN-33/8 ; d(jaa eN - [m) 2 2C2N
Therefore, have,
P (las Gol > eN 30/88) S 2exp (-12CGN-
Therefore,
P(To = N <
Σ
Σ
2exp -122-22- 2)
KE[K]
t=(Na C1
2exp
-teeC2N :)
(E[K]
< Σ exp
12202(N2 -
-C) CNN- +)
Σ exp 1-2C2N--p Na ((=NN++Ci)
iE[K]
< 2KN exp
(-eCC(N - C-NN- #)
2K 2KNexp(-S((N))
where the constant hidden in !()) depends only μ. Using the obtained upper bound,
ETTo] = PTo = 1) Σ (N + I)P N +
N21
< 1+ Σ 2KN(N + 1) exp(((((Nv))
NZ1
Note that the series the RHS is convergent for any (0, Therefore [x[TT]]
51

---

G.4 Properties of exploration
In the following discussion, the set of iterations which the algorithm does exploration is defined as all iterations N where minge(K] [K] Na (N - 1) Na (which is equivalent to having VN * 0, where Vv denotes the set of starved arms at iteration N, and is defined in Section 3 We detine the epoch of exploration at some arbitrary iteration as follows,
Definition G.6. If the algorithm does exploration 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 N1 and N2 are, respectively, defined as,
N1 max {t N 1 not an exploration) N2 min (t 2 N t +++1 is not an exploration)
and
then the epoch of exploration at iteration N is N₂ N1 +
Proposition G.5. The following statements are true:
1. For every iteration which is exploration, the epoch of exploration that iteration is upper bounded by a constant depending on K and a. We denote this constant using Tepoch-
2. There exists a constant C depending on and a such that, over every sample path, we have
No(N) 2 N KE|K]
min
As result, Na( ((N") for every amm a E [K].
3. There exists M depending on K and a such that, every epoch of exploration starting after iteration M has length atmost K, and every arm can gel pulled atmost once that epoch. We call the constant M as M Mespio-
4. If an epock of exploration starts from some N 2 Mesplos then the next epoch of exploration doesn't start before another (NN-aa iterations.
5. Let Ñ 2 Magto be such that, N is exploration. Define the following sequence, No N. and for k 21,
N% = min
N N
Nş is the begining of an epoch of exploration
Then N₁ = Ñ -S2K2//a) In other words, any N 2 Mespio the k-th epoch of exploration after iteration N starts after N - 1/a) iterations.
6. For any N 2 Mesplo + Tepech + 1 and T 2 1, the no. epochs of exploration intersecting with the set of iterations (N, 1, + N, +T} is O(1a).
Proof. Statement 1: Let the algorithm does exploration at iteration N. We can always choose N in such a way that, iteration N was not an exploration, by choosing N to be the iteration which an epoch begins. If the epoch of exploration starting at iteration N continues till iteration N + t, i.e. the iterations N, N + I...., N + are exploration, then,
(1)
(N +tt
NN + t - 1) aE[K]
min
min N. 1) aE[K]
( 2 (N
min No (N 2) K](K]
1)aa + K'
K
where (I) follows from the fact that, min N.)-) increments by atleast over every consecutive
iterations in an epoch of exploration, and (2) from the fact that iteration N is not exploration.
From the above inequality, we have,
S (N +t)a (N 1)a.
52

---

Note that, .N + (N +t - (N- 1)"h is decreasing in N. Hence RHS & (1+t)² S 11+t" I 2t
(since 2 1). Therefore, we have,
S 26 implying
- (2K)
K
Therefore every epoch of exploration is atmost (2K)//10)) iterations long.
denote the set { 1, 2, :... We consider only those iterations where minkg]]]] (N - 1) < No. By statement 1, if we consider N1 S N < N2 such that, N1, N1 + +1, explorations and N1 1, N2 + are not explorations, then we must have, N2- N2 < Tpoch. As result, we have,
Statement 2: In the following discussion use [ for pair of integers
N2 - 1, N2 are all
No min (N(NN S [E[R]
max (N" min Na(N)). NE(NINN
aE(K]
Now, the slowest rate which min (NV can grow while iterations N E {N1, N1 .... 12 1, N₂) } is if the algorithm pulls the K arms consecutively in those iterations. Therefore, we have,
N N1 +1 K
min (o(N) 2 [E[K]
min No 1) aE[K]
for every N E [M N2).
Using this, we have,
Na min Na -1) N - No +11 1)
No min (N)
S
max NE(N):NN]
aE[K]
Since iteration N₁ is not exploration, we have
min
(N
min No(N1 2) 2 (N1 1)a.
<E[K]
aE
Using this, the upper bound becomes,
(N- - -N N1 +
(N (N- N1 +1) N - N1 +1
max Ne[N1:Na]
max Ne[MiNN
K
K
(=+1)² 1+2
max =eaaT
= =c,
K
where depends only on K and a.
Hence we get,
min Na(N) 2 - aE(K)
=
Statement 3: If the epoch of exploration starts from T' and continues for more than K iterations, note that min (-) gets incremented by atleast during the iterations T, T + 1, T K. As result, we have,
(T (TTK-- 1) min [
min
NT -1 2 1. aE[K]
Since iteration T - is not an exploration, we have Ñ. - 1) -2) (T (T-1) 1) Similarly, since iteration T' + K is an exploration, min (T + 1) (TT<<<+)))))) Using these two observations, we have,
<
K +1 (1+
-1) < a(K -1)
1 < (T+ -T+ -T 1)at & (T- (T-1)a
53

---

Therefore,
I (a(K+ +1) +1
Let Mexplo = (a(K + 1))1/(1-a) + 2. Then from the above argument, if > Mexplo the epoch of exploration starting will last for most K iterations.
Let us assume that, the epoch begining from some T, 2 Mexplo lasts till iteration Ty. Therefore, we have,
min NTTyy 1) < Tj [E[R]
and min (T. 2) 2 (T: 1) aE(K]
Using this, min (T min N₂ (T; 2) - Tj - (T; -) S a(T; - 1) -T; + <E(K]
aE(R]
We argued earlier that T, T, S K. We also have, T, 12 Mesplo - - (a(K + 1)) +1. Using this observations, we get
a(K +
min (T, - min (T; 2) s (la(K 1))1/(1-a) 1)1-a < aE[K]
aE[K]
Since [(] 1), we obtain,
Na(Ty) [ NT -)) +)+1 +1 and min (T(T.-2) S min Na
min (TTT) - min (T; 1) < 2, aE[K]
aE(K]
implying min (TyT)) m Ñ. (T: - 1) < 1, which is possible only if every arm is pulled most once iterations T,, T; ++1,, Ty - 1, Ty-
Statement 4: Let an epoch of exploration starts from N > Mesplo and the next epoch starts from N T for some 2 1. The epoch starting from N continues till atmost min + K, N ++7 T 2} by statement 3. Moreover in that epoch, every arm gets pulled atmost once and min N. increments by Therefore,
min (N + min No(N - 1) 2 1. K
K
Since iteration N 1 not an exploration, we have, minge[K] Na 2 min No(N 22) 2 (N - 1) Since iteration N + T is exploration, have min (N +T (N +T) Using these in the above inequality, we obtain,
(N T (N - 1)a a(N - 11 (T
which implies T 2 1 (N
Statement 5: Using statement
have constant C₁ such that,
N₂ 2 N + C k-11
for l: 2 1, where No = 1. We now inductively argue that, there exists some constant C2 independent of k and N such that, N₂ 2 N Cyki/a for k 2 1.
For k
choose C2 S 1.
Now for some h 2 2, if Nx-1 2 N C2(k 1) we have,
N₂ 2 N + CNNI 2 N + +2(k 1)) + Ci + C2(k- - 1)2///1-a
2 N + 1/a + (CI(N + C2(k +C(k 1olk-11 1)1 C2(h1//a (k: 11))/aa)
2 N + 1/ + CG C2(k 1)1/a)1-a C2 k. 1-11
+2(k
54

---

1/a
Upon choosing C2
aCCi
since we already have 2, we obtain
Ci(N + C2( 111//1100 2 Ci
C2
k
2
1/0
1-a
=
C2
2
aC1
C2
a
bl/a
C2 k1/a
Therefore, N₂ N C2ka.
Therefore, choosing C2 min { (1 a01 11
(1
we have N₂ 2 N C2kd for k 1.
2 2
Statement 6: If N 2 M Mexplo + T spoch + 1 and T 2 1, every epoch of explorations intersecting N + T 1, + +T has length atmost K (by statement 3).
with the iterations {NV . 1, Hence, every such epoch must have started the first such epoch has started and the sequence (N+))22 be defined similar to statement 5. Then No 2 N - K and N₂ 2 No + C2k 2 N K + C2k ha Now, if the k-th epoch starting after No intersects with the iterations (N, N + +1,
after iteration N - K. Let No be the time when
T 1, N + +T, then,
(T + K) C2
N+T N K Czke, which implies,
S
O(T)).
Definition G.7. We define the constant T Txpplo Mesplo + Tepoch + 1, where the constants Mesplo and Tepoch are defined in Proposition G.5
Lemma G.8. For N 2 Tesplo and T 2 1. the no of times an arm a E [K] is pulled for exploration by the algorithm during iterations N. N + 1, .... N +T 1, N + T is O
G.5 for N > T Teppl and T > 1, every epoch of exploration intersecting with the set of iterations N, such epoch, every arm is pulled atmost once. As result, no. of times an arm is pulled during the N T upper bounded by the no. of epoch of iterations intersecting with the set (N. 1, .... N + 1, N + T}. The later quantity is O(T") by statement 6 of Proposition G.5l Hence the lemma stands proved.
Proof. By statement 3 of Proposition
N 22
N + 7" of length atmost K. every
iterations N, N +
G.5 Technical lemmas related to algorithmic allocations
In this appendix prove several properties about the anchor function (g) and the algorithmic allocations ((N) (Na (N) a E [K]). We exploit the results proven in Appendix and G.4 to prove that the following properties hold after random time of finite expectation,
if the algorithm has * 0 at some iteration N, then g crosses the value zero withing an (NN iterations, where the constant hidden in O()) is independent of the sample paths (in Lemma G.9). and
[K] has N₂ (N) (NN) samples (in Lemma G.13
every arm
Each of the properties stated above are used extensively in the proofs of Proposition G. and G.2
Definition G.8. We define the random time Ti max max Tesplo} (where Tesplo and To are defined, respectively, Appendix G.4 and G.3).
Note that [Ti] E, [To]
Texplo < Co.
We can have g far from the value zero at iteration Ti. y will still be finite at Ti because of exploration. Lemma bounds the no. of iterations the algorithm takes to reach the value zero.
55

---

Lemma G.9 (Upper bound to the time to reach g 0). If ( ((())) & 0 at iteration N Tú, and
U = min [t>0]
( + t), N(N +1) and (U(N).N(N) have opposite signs
then there exists a constant C1 > 0 independent of the sample paths such that S CNN.
Proof. Using 10p for N 2 Tí, we have,
Σ NN)2 a#1 (N)22
Na(NN
g ((N)) =
- -1 θ
Σ
a#1
1) :) )) 1
N
-1. (72)
(NN
We now consider two situations separately,
Case I: (U(N). > 0: We know that, there is constant D1 > 0, such that,
N+t N1(N +t) -1 1,
(N(N+)) s Dr
for every 2 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 constant > 0 such that, (NV + t) 2 t c1t% Hence,
9 [ + 1), N(N s Di N+
(
( ciaa 1) 2 -1 -1 Di
2 N ( (1
(7- ci - fort U.
Since
U N 1)) 2 0, RHS of the above inequality is non-negative at
t= U - After some algebraic manipulation, this implics,
U- (1 + )U 1)a s D//2N,
Since LHS of the above inequality is linear in U, we can find constant Cn such that U S CnN.
Case II: 9 (M(N), N(V)) O: Using (72), we have constant D: such that,
-1) -1 -
+ NI + [
NON Z D2
for all t. 2 1. Now for 1 <.U. the algorithm pulls arm only for exploration. As result, using statement 6 of Proposition G.5 we have, constant 0j > O such that (N + s N ttt. Using this,
9 (i(N (M(N+ + N -N) 2 D2
N+1 -1 N
-1 -12 -1
[ 1- c N + ci
D2
1,
N + ctta N
for U. Since (V + U 1), N(N + - 1)) S 0. the RHS of the above inequality is not positive at t = U - 1. After some algebraic manipulation, this implies,
U-1 c1 + D, 1/2)(U 1)a < D 1/2N.
Again the LHS of the above inequality is linear in U. As a result, we can find a constant C12 such that, U C12N.
We take C max(C11, C12) and have U S C,N.
56

---

Lemma G.10
G.11 and G.12 are necessary for proving Lemma G.13 which says (N) ((N)
for every arm a [ after random time of finite expectation. This property is essential for proving Proposition G. and G.2 stated earlier.
Lemma G.10. There exists constants "/1, 72 (0,1) independent of the sample path, such that, for N 2 Tú, whenever (M(N,,N()) and (iIN + 1),N(N + +1) have opposite signs, we have,
1. (N(N 2 NN, and
2. (XX/(())((1) Na(N) N.
Proof. For N 2 Ti, we have constants D1. D2 such that,
N -1) 1) -1 (NN
S ( s D2
N
-1) -1
D1
N1
We consider only the situation where 9 (M(N). N()) and (M(N + +1,, 1), + 11) so. Extending this to the other case follows similar argument.
From g(N(N N(N + 1)) S 0, we have,
N+1
D1
-1 -1 O, which implies
NNN+11
ÑI(N + 1) 2 (1 1/3-/3
(73)
Since (N) (for exploration), we have (N +1) S (N) + < 2N (N). Therefore,
using 73
get (NN 2 {1 - and we can take
{ D1 1/2
Similarly from, (()(NN), ((N)) 2 O, we have,
-1)
1)
2
N
D2
1 12 O, which implies
Ni(N)
Ñi(N) 51 D5 1/2-
(74)
Using 74 have, EMELKIA Na(N) 2 (1 + 1 This further implies
Na(N) 2 K (1 1//2/
-N. -
max at aε(K]/(1)
Hence we can take 72 R- D )
Lemma G.11. There exists constants Mi 2 1, dmar E [1, 20) and dmin E (0, 1] independent of the sample path, such that, T2 is the time at which crosses zero after the iteration max{ M1, T.). then, for N > Ty. we have:
(N), (1.) ddmax.
dmin
(N),
Moreover, we have [T]] < 0c.
Proof. Let,
dNV) Z1. (N))
D(N(N, Σ
(N), (N,,,11,,0
57

---

Also for every M 2 1, we define Ti.M max and T2.M as the iteration at which crosses zero for the first time after the iteration Ti, i.e.
T2,M
def.
min { N { TIM
g(((NN TT. 1), ((N 1)) and
g(ū(TT.M) N (T) are of opposite signs
Existence of dmax: If (( (N)) < O. then (NT ((N) is bounded above trivially by 1.
Otherwise if (T)(N), (N)) > 0 for some N > Tr let T = max S N
(Ta(t), N()) <
0) } i.e. the time before iteration N when 9 has crossed the level zero. a result, T 2 T2,5 (by definition of T2, and by Lemma G.10 (T) 2 7 for some " E (0, 1). Let S = N - -7. During iterations 7'+1, 1,... , SS 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 have
(T + 2 (T) + S - c1S0 2 AT + S S
for some ci O. Using 72 we have constant D2 > 0 such that,
= D2 7 c -1) -
T+S
2
( (1-
2
D + N(T S)) - D2
7I + - c1
We take M11 = 2 min - -1S"). It is easy to observe that for T 2 M11 and 2 0, the function T, S in the RHS is bounded above. Therefore, we take,
+ 5 D2 (1 ( M2,18820
dmax max 1, max
00.
Hence, if M 2 Mn1 we have (( S dmax for every N > T2.M-
Existence of : If (() 2 have 1 has the trivial lower bound. Otherwise, if ( (NV) < O, we define T = max{ S N g (t)) 2 } and S S N T. As result, T 2 T2.M (by definition of T2,M). By Lemma G.10 we have (T) < (1 -0)-2) for some 12 (0, 1). Also, the algorithm pulls the first arm only for exploration during the iterations
T 1,7 + 2, .......... ,T T S, since g is negative. Therefore, using statement 6 of Proposition G.5 we
have, N1 (T' S) < (T) + S I (1 (2 + S1Sa By 72
we have D1 0 such that,
(T + S), (T + S) 2 D
T+S
-1)
S - 2 2 = Di
(1 To) + 0
(1- + +
Let M12 2 minszo Sa). The function of T, in the RHS is bounded below by positive
72 constant for T' 2 M12 and S 0. Let.
c, 2 (1 (11-72) S )
)3 >0. O.
dmin = min
1
min
Dj
T2M2. $20
Then for M 2 M12, we have (()(NN, ((N)) 2 dmin 0 for every N >> T2.M-
Now, upon taking M₁ = max max(M M12), and Tg = T2,,, the lemma follows. By Lemma G.9, have constant C₁ such that, Ta C₁ Ma, As result, [x] < CTM + [Ti)) co.
Using a technique similar to the one used in the proof of Lemma G.10 using (22) Lemma G.I implies the following corollary. We define the random time T2 as the one introduced in Lemma G.Il
Corollary G.1. There exists constants 31, f2 E (0, 1) independent of the sample paths, such that, for every N: > Tb.
58

---

1. M(N) 2 S1N, and
2. maX Na(N) 2 82N.
Lemma G.12. There exists constants & > and M2 2 independent of the sample path, such that, for N > [M, T2) + 1, if the algorithm pulls some arm E [K]/ then for every alternate arm b aK)/(L,a, (N(N)= 2 (N).
Proof. We consider two separate cases.
Case I: Iteration N is an exploration: Then we have a constant C (introduced in statement 2 of Proposition G.5 such that,
No)N) 2 No C1 2 No - C N₂(N) - C1-
(75)
We also have (N(N) 2 No -1. Now let M₂ 2 be chosen such that, M2 3C1 + 2. As result, for N 2 max [2, ]2 we have, (N(N) 2 N - 11 2 implies, (NVN) 2 (NN..
This together with 75
Case II: Iteration N is not an exploration: We consider the AT2 and IAT2 algorithms separately.
Case ILII AT2 Algorithm: If iiterttion N not an exploration, we have, I,(N - 1) < 4NN 1). Using |1 for N max M2, T2}, we have constants C2 and C3 such that,
C2 (N 1) (N - 1)
(N - 1) N. -1) S INNN- 1)
ÑI(N 1) No(N-1 1) Ni - -1 + NoNN -1)
SIN( 1) C3
As result, have,
Os Ni 1) N. - NoNN 1) 2 2C3 No(N 1)
2Cs No(N),
Na(N 1) Co NI 1) + No 1)
3,C2
3,C₂
where, for (I), we first note that N T2 1. As result, using Corollary G..
(N
(N 1) (B1 E (0,1) is the constant introduced in Corollary G.1 and on the other hand NI - 1) No(N 1) 2(N - 1). Hence, get
31C₂ AC2NNNN NN - 31C₂ (Na (N) -1).
No)N)= 2
2C3
2Cs
Again using statement of Proposition M > 3C1 + 2). As result,
G.5 Na(N) 2 No C1 2 Mn C1 2 2 (since
3,C2 N.(N).
N.(N) Z
4C3s
Taking y = min [1 B.Ca
we have the desired result for AT2 algorithm.
2 4C3
Case IIIII IAT2 Algorithm: In this case, have,
log(Na 1)) (N 1) S No 1)) +I -1).
Using
we have constants C2 and C3 such that,
NI(N - 1) (N 1)
C2 Ni 1) + NoNN - ON 11) IN -1)
Ñi(N - 1) No(N 1) 1 - - 1).
< LNN 1) + logoog( - -1) Co
+
Ni 1) NNNNNNNN1111 -(N-))
59

---

As result, using the same arguments used for the AT2 algorithm in Case II.I, we can conclude,
31
C3
:)
-1
No(N)
Na(N),
4
2
for > max T2)
Now taking y = min
1 81 2 1
C2 Ca - ((=-))"' we have the desired result for IAT2 algorithm.
Definition G.9. We define the random time Z3 = max { M2, 12} + 2, where M2 is the constant introduced in Lemma LemmaG.12) and T₂ the random time defined in Lemma G.11
Definition G.10. We define the random time T4 as T4 32 (T3 + 1), where B2 (0, 1) is the constant introduced in Corollary G.I
Note that Ex [Ta] < oc, since [T]] < co. For the same reason, by Definition G.10 T4 satisfies E [Ta] < since E, < oo.
Lemma G.13 (Sufficient sampling). For every N 2 T4, we have Na(N) ((N) for every E [
Proof. For 1 and every N 2 T4, we have NNN = (N) Corollary G.1
Otherwise for + 1 and every N > T4, we define A'N arg maxbe[K]/\1) No(N). By Corollary
G.I
NA, 2 B2N 2 8T4, = T3+1 +1
Therefore, arm A'y must have been pulled by the algorithm somewhere between iterations T3 and N. Let us define the time N' be the last time before N when A'y was pulled. Then N' 2 T3 > max ( M2, T2) + 1. As result, using Lemma G.12 we have,
Na(N') 2 NNAA (N')
NN (N),
where (i) follows by definition of N'. Since N 2 N', we have Ña(N) 2 Na(N'. As a result, we obtain, for every [K] and N T4.
Ña(N) 2 7 NA (N) =
No(N) 2 782N,
max [E](((1
where 32 (0, 1) is the constant mentioned in Corollary G.1 Hence have Na S2N) for
N 2 T4 and the lemma follows.
G.6 Proving Lemma G.2
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 M3 2 1 and C > 0 independent of the sample paths, such that for every N max Ma To}, if the algorithu picks iterations.
E [1] iteration N, then again picks a within the next [C N1-3a/8
For every arm E [K]. iteration N 2 1 and R 2 1, we define the following quantities,
AN.(N, R) N. + R) Na(N),
AÑ,(N, R)
6(N, R) arg max JE[K]/(1}
and
(N))
T(N, R)
max ts + R
A, 6(N, }.
For proving Lemma G.2 need the three technical lemmas: Lemma G.14 15 and G.16
60

---

Lemma G.14. For N 2 To (Is is the random time defined in the statement of Proposition G.1 and satisfies E [To] oc), we have,
AÑ (N, R) & (NN AN (N, R) (N) + +0 LOOORNN'LL (N,
R)) 10001133/8(11 (1
12)
(76)
Proof. In the proof, for readability, we b to denote b(N, R). Also, for every arm [K], use ANa to denote ANa AN,,). R).
0 independent of the sample paths, such that for By Proposition G.1 we have constant C
N To.
g(u, + R)) س(H. N(N))
< 2CN-3a/8.
Therefore, applying the mean value theorem, we have,
0g (M, NN +
Oy ON (E(K]/(1)
E
(M, NY
S 2CC
NN1
where N (Na)ae(K) with Nº E Na(N), N. +R) for every [K].
Now expanding the partial derivatives of with respect to Na 's for a E [K], we get
f(u, a, N) N.4.
f(u,a, N) N.
AM
Σ
Σ
2CN 2CN-3a//8
330/8
(N1+ + N.)²
(N1 No)²
RE aE(K1/(1)
(77)
where, f(u, a, .N were defined in 13 of Appendix B
Letting
S( Ñ)
N,
(N++N,1²
P3 Enyi l'1, Ñ)
R.4.
(NI+N.)²
for every arm j E [K][[1), we have,
AN
AN
N.4.
Pa
2CN 30/8 x N:1
Σ
a(
(78)
N1
No
(N: + Na)²
a
(E(K)/(1)
2
We know from (14) of Appendix
that f(u, a, N),NN
(1
No Nr.
As result,
N.
Σ aH, Ñ) N.4.
N
=
(Ni + Na)²
EEEjK//(a)
N2
a#1
By Lemma G.13
have No. 2 No =O(N) and Ñ NN= for N 2 Tg. As result,, get,
-1
Eflma, N.A.
Ñ
O ((1 RN)
(Ni + NNa)²
ax1
Putting this in
78
we obtain
AN
AÑ
ON RN n2).
0
N
N
af11
61

---

which further implies,
AN
AN
Σ
Pa
+0
N
(1+ RN 1)2)
N1
Na
AN.
+ +0
(N-3a/8 1))
(since N₂ 2,20 N.).
Pa
Na
of1
Let b = arg mlX
AN Na
The above inequality implies,
AN
ANo
+0 N (1 RN RN-
N1
No.
Now multiplying both sides by / /N,, we get,
AN
N
ANb -1 N N- (1+ 12
+0
ANb
Nb
N
+ +
AN
N1-3a/88 (1+ (1N (since N₂ S R).
No
76 follows from the above inequality upon observing that, N1 S N1 + R and Ño = ((N) (by
Lemma G.13).
O
Lemma G.15. There exists constants Ms1 2 D1, D2 O independent of the sample paths such that, for N 2 max M51, Ts}, we have [D,N1-30/81 < N, and for all R E
{[D,Nl-Saffe N1-3/88 +
+1...., ..... N), we have ANUN.RY (N, 2 D2R.
Proof. simplify notation, we adopt denote b(N, R) and, for every arm j E [K], we use AN, to denote AN,NN,R) R).
By (76) of Lemma G.14 there exists constant D3 independent of the sample paths, such that, for all 2 Ta and 18 E (1,2....,N) N).
Ni
+ D3 [1 AÑ, I -w/))/
AN S AÑD
(we have RN 1)
No
Ni
+ D3
ANo D2N 30/8
No
Since (N) and (N) are both ((N) (by Lemma G.13. we have a constant D₃ such that, (N) + D3 S D4 for every N Tg. Using this in the above inequality, we get,
No(N)
AÑ, < D,4Ñ, + 30/8
(79)
We take Dj 2D3 and Mst 2 to be the smallest number such that, every N > Mş1 satisfies [D, < N.
Now if N 2 max( Ms1. To} and E NID,N -3x/87, [D,N1-30/87 +1, ..., N). from 79 we get,
AÑ, D,AÑ, + D-N11-3018
R
< D,AN, + 2
(80)
By definition of b, have,
Ñ
AÑD > AÑ, for every a e [K]/(1).
No
62

---

Again, since N. = (N) for every E [K] (by Lemma G.13, there exists a constant D3 > 0 independent of the sample paths such that,
D&AÑ, 2 AÑ, for every a E [K]/(1,b) b).
As result,
R=
E AÑ. + AÑ + AÑ.
aE[K]/[1,0)
R
(K 2)D; D44N, +
AÑ, (using (80))
R
< (1+ (K -2)Ds + DD))NN
2
AÑo 2 2(1 + (K - D5 + DA) R.
Now taking D2 2(1+(K 2)D > 0, we have the desired conclusion.
Lemma G.16. For AT2 7 and IAT2
2 algorithms, there exists constants C3: C4 > 0 independent
of the sample paths, such that, for N 2 Ts and R E (1,2..... .N). if the algorithm pulls some arm E [1] at iteration N and doesn't pull a for the next R iterations, then,
AT2: (N + R) IN + RR S - -C94NuNNNO (N, R) + C,N1-3a/8
+0 C0((N-30)) + RN-1) Rt).
(81)
IAT2: (N + R) [(m) (LN.R)
(N + R) ~ - CGAN (N, + C4N1-30//8
+ +0 ( ((N- + -RN-1)
(82)
where for every alternative arm j E [K]/[1},
T (N) I,(N) log( (N))
is the modified empirical index of that iteration N
Proof. For cleaner presentation, we use 6 to denote 6(N, R). We also use üj T1.5. AN, and Ny. respectively, to denote (N), (N), AN,(N, R) and Ny(N) for every arm j E [K], whenever it doesn't cause confusion.
AT2 Algorithm: Let
(N, ((N) IN(N) INNN
denote the the difference between the empirical indexes of the two arms and at iteration N. Note that (a, μ4) depends only on the uple of variables (Ni, Na, No. No, Wi Pa. (i)). In the following argument, we apply mean value theorem over Sa,5 and the empirical indexes I, and Ig, treating them functions of N1, N.. No. f4, Pa, and jáb-
Using the multivariate mean value theorem, we have,
OS..b Opt
Sa + R), M(N +
Σ
(N A))
j=L,a,b
0Sa.b
(N, pi) AÑ, 0Sa.b
(N, (i) AÑ.. (83)
ON1
ONg
where Aū; = (N + (N) for 1, a, b, and (Ñ, p1) (Ni, No, No. Pi, Pas such
that, for j = 1, a, b. üu lies between Ti (N) and Tyy (N + R), and Ñ, lies N,(N), N, + R)
Note that there is contribution the RHS in 88 due to N.. because No (-) doesn't 't change during
63

---

iterations N + 1, + + + R, owing to our assumption that the algorithm doesn't 't pull arm during the mentioned iterations. First we consider the partial derivatives of S3.6 with respect to /1, and μab 83 We have
0Sa. (N. ( N1 (d1, - d1 (11,
0u1
where $i +,01+8,04 for j a, N1-N,
Since R S N, we have for j a, b, Nr S N, + = ((N) (by Lemma G.13). As a result, using of Appendix B both dj (f1, 21)a) and d1 (p1, (1) are (1). Using this, ((N).
85a. (Ñ pt) is
dur
Similarly,
aS..b [Ñ, (t) Nadı (Ma: a)) and 0S.. (Ñ, (t) -Nadi (jis, 21,6))
0pa
8pb
Using the same argument as for the partial derivative of Sa.b with respect to Hl, we have aSa2 (N. ( O(N) for both j = a.b.
Bp5
Therefore, the contribution in the RHS of (83) due the noisiness in the empirical means Mıi Has Pb is bounded above by,
0S.,b (Ñ. 1
OS..
Σ L
Σ
(N pi)
147
Opg
j=1.a.b
O(N) ((/8))
= O(N1-301/1
(84)
where (I) follows since for N 2 To and
1, a, b, A O(N 33/83))) Now considering the partial derivative of Sa,b(-) with respect to N1, we get
aS..6 ON,
(N. (t) d( - ((11,
Using Lemma G.13
(N) and N₂ (N + R) are both ((N) for all j 1, and N Ts. since R < N. As a result, using we have,
S2,b @u,āNe
SS.. @N,ONk
(N', w') O(1), and
(N', n²) O(N-L)
for every j, E (1,a,b) b}. and tuple (N', 1²) = (Ni, N₂, No 14, Mla 1h) having Nj E
(.NN,, + R)] and ut lying between f4 and T., for every = 1, a,
Therefore, applying the mean value theorem, we get,
0Sab ON;
(
3(01, ((,1,, +0
Σ 1 Tigl
+0
N-1 Σ AN, j=b
EN
j=1,bbb
d(ū, d(ū di F1 +
3a/8 N
N
RNN RN--1)
Similarly, considering the partial derivative with respect No.
aS.b ON,
(Ñ. -d( TI,6) 0 (N-3//8 + RN-1)
64

---

Now, using all these upper bounds in the RHS of (33). we obtain
(a R), ii(N + R)) Sa, (N,(NN()) (T(
$ AÑ (d(711, a1,)) - d 31,b)) AN, d(Ms, F1,6)
0 N /1 + R(N R(N-30/8 + RNN RN-1)).
(85)
Since arm a was pulled iteration N, we have IN 1) - (NV 1). Also since arm b was not pulled in iteration N, its empirical index remains unchanged, iee [N 1) (NN. Combining these two observations, we have Ia (N - 1) S (N)..
As result,
(NV),
(N) (N)
(Ia(N) IN(N - 1)) + (Ia(N - 1) Is(N))
S [NV) - IN 1)
I(N) Ia(N -1) +0)N+N (using Lemma G.3
S d(ua: p1) + -
= O(NN
(86)
where the last step follows from the fact that, the partial derivatives of Ia(-) with respect to N d(ja 21.a (N)) I d(pa: (11). As a result, since arm was pulled in iteration N, the increment IaNN= - [nNN - 1) in (-) is upper bounded by d(Ha;Hi).
Therefore (85) implies,
(N + R) + R)) & AÑT (d(Ti,, - d(P11.11.0)) - AÑo d(Tb. T1,0) -30/8
+ Sa,(N( ((N) + +0 (NN-30// + RNN') R
AÑT (d( T1,a) - d( 21,6)) AÑo c(isb; F2,6)
+ /NL-30/8 (N-3a/8 RN-1) R).
(87)
Now we consider two possibilities:
Case ((ū1,ār,o) d(ūi, T1,)) < <0: In this case, by (5).. So,t R R)) upper
bounded by,
AÑ, d(Ts, T)) + O (N1-30/88 + +ON++NNN Sa-8/// + RN RN- It).
By Lemma G.13 and 6 since both No (NV and (NN are ((N), we have T1,b) O As
a result, [81 follows.
Case II d(Ti, T1,a) - d(ū R. 2 0: this case, the RHS of 88 can rewritten as,
AÑ
AÑD
(d(ī), "1,a) ((71,,T10)) d(Go F1,0 +0 ( (NI-Ba//8+ (N- -a/8 + RN-1) R
ANo
(88)
Using
76 in Lemma
G.14
the upper bound becomes
AN,
(d(īi,, Ti,a) - -d(Ti1, d(Db, T1.))
+ 0 11 31/30/8 (1 RN- + +NN-NNNO (N-30/8 + R.N-1) R
NJ
= -NÑo
(d(7z1) Fr,) - - d(ā1,. F1,5)) - d(ps. T1.)
No
+ +0 (N2-3a/8 + ( (N-3a/8 + RN-1) R²)
(since R S N).
(89)
65

---

By 86 we have,
I((N) S Is(N) + -
(90)
Expanding the empirical index terms, we get,
Nıd(ii, Nad(Fa Fi,a) I (1d("1,3116)) + Nod(pb; (1,6) + O(N1-3a/5)
By Lemma G.13 we have Nr - (NN). As a result, upon dividing both sides of the above inequality by N& and after some re-arrangement of terms, obtain,
Ni
(d d(āi,, ((TT,,TIM))
(i -3a/8..
No
No
Using the above inequality in (89
we get the upper bound,
-AN
d( #1.a) +0 30/8 + (N- 30/8 + RN-1) R
(91)
No
Ny de x) = (1)) Therefore (81)
By Lemma G.13 and 66, have,
follows.
No.
IAT2 Algorithm: The proof of (82) for IAT2 is very similar the proof of (81) for AT2. We first consider the difference of the modified empirical indexes between the two arms and b,
$t (N(N),
(N) -I (N).
Following a similar procedure as the AT2 algorithm, we apply the mean value theorem to obtain,
as(m) a
5(mm)
(N(N + R). R)) a
((m))
((N)..(())
Σ
(Ñ,
Ajo
a.b
0pl
j=Labb
@s(m) a.b
a5(m) a.b
(N. (b) AN
(Ñ, AN..
(92)
ON1
ON,
where A7G (N + R) (N), and
(Ñ, (a) (N,, No. Pr, Bas (b)). such that, Ay lies N2)N), N,, NN RR) for every 1, a,
between (N) and 2r (N + Rt), and Ñ₂ E
The contribution to 92) due to noise in j is - by the same argument proved (84) for AT2.
Now we consider the partial derivatives of 5((m) with respect to N1, No, No. Following the same steps as used for AT2 algorithm, we have,
a.b
(N, (t)
JS.. N. (b) d( - ((Ti,, + O(N 3a/8 + RN-1), and O(N-8a//
ON,
ON1
as(m)
ON, (N,
a.b
JSa.
(Ñ)
1
S - -d(ūi, T1,b) + O(N 3a/8 O(N-8
RN-1).
ON,
No
As result, the contribution to 92 due to Ni and No is.
as(m)
@5(m) (N, jz) AÑ,
a.b
(Ñ (
AÑ,
a.b
ON,
ON,
AÑ, d(As. Z.,s) O ((N-Baaf + RN-1) n.)
< AÑ,
(d(,,, d(
66

---

Therefore, adding the contributions of the noise in (f1))=11.,bb 922 can be further upper bounded by.
sum 0.6 (N + R), i + R)) S (N (T)
AÑ (d(ff), T1,a) d(p ((,,1,,1.))) x1,b)) AN: d( F1,0)
+0 |N1-3a/ + (N-30/8 RN- R).
(93)
Now, we find an upper bound to s(,5 ((N), Since the algorithm pulls arm and doesn't t pull arm b at iteration N, we must have
(N -1-1) S 1m (N -1 I (N). (N
Therefore,
STTT (NV( ((NN) = I - I/m² (NV) (NV)
(I(m) (N) I (N - -1) + (I (N - 1) IZm (N))
I(m - II 1)
Ña(N)
In(N) - II(N 1) + log
No(N -1
①1 INNN- - - O(N1-3a/8)
(94)
where (1) follows from the fact that N₂ (N) = (ONN) for 2 To. and (2) follows using the arguments used while bounding (N) - [N in 86
Putting this in 933 get,
s(m)) b.6 (N + R), PIN + R)) S AÑ1 (d( 21,a) - d(F1, x1,6) - AÑo d( 21,6)
+0 +0 1N R(N- 3a/8 + RN-1))
(95)
Now there can two cases.
Case I d(Aī, Z1,a) d(u 21,)) 0: Then, using the same argument as was used for Case of AT2 algorithm, we get (82).
Case II d(Ti,, T1,a) - d(Ai, F1,6) 2 0: Using 776 Lemma G.12 the RHS in (55 is upper bounded by.
Nj No.
AÑ,
(d(Ti, TI.a) (("1.TT1,)) - d(īs, F10e T..)
+0 (N1-30/88 - (N-3a/ 30//8 RN--) R)
Using 94
we have
(N) s I (N) + (NL-38//))
which implies.
IN) S INNN + log
NO N₂
+ O(N1-33/58
1 I,(N) + 03N1-3/88
where (1) follows from the fact that N₂ (N) and (N) are both O(N). causing log [.(N)
= 0(1)
N₂(N)
for N 2 Te- Note that the above inequality same as (90) obtained in Case of AT2, Now 82
follows using exactly the same argument as in the Case II of AT2 after (90).
67

---

For every E [ N 2 Ta and R E (1,2, NN, we have,
IN + R) (N + R 1)
[N + R) (N + R - 1)1 + O((N R)1-30/5)
[LN + R) (N R - O
(3)
max(d(H1, Ma), d(Ha, p1)3 O(N2- O(N2-3a//))
(96)
where: (1) follows by Lemma G.3 (2) follows since R S N; and (3) follows from the fact that (-)-) can increment by atmost max ( Pa); d(ja, [1)} one iteration.
Since, at every iteration N 2 1 and for every arm, the modified empirical index differ from the empirical index by atmost loV(N), we have,
(mm) (N + R. I(m² (N + R 1--1) 1)
In + R) - (N + R - 1) + log(NN + R)
IN + R) - (N (N R - 1)1 O(log((o)))))
O(v1 30/8) ((lg((N)) 1(N/-)0/8), (97)
where (i) follows because R S N.
Using 96 and (77.. the following corollary follows from Lemma G.16
Corollary G.2. For AT2 7 and IAT2 ( algorithms, for N > To and R E .1.2....,N. N}. }. if the algorithm pulls some arm a E [K](11} at iteration N and doesn't pull a for the next R iterations, then,
AT2:
(N + 1) (N s -C3AN6NN. (N, C-
+0 ( R).
RN
(98)
IAT2: Z(m)(N + R I((m
ToN 1) - CN R) + -C-N1-30/8
+0 +0((N-a//3 RN-1) R).
(99)
where C3, C5 > O 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 Z(m)
In the proof, argue via contradiction. We show that, there exists constants M, > and Ci > 0 independent the sample paths, such that for N max (M,, To J. if the algorithm pulls some arm E [K][(1) } at iteration N and doesn't pull for the next R(N) def. N1- iterations, then iteration r(N,)(N)) the algorithm pulls arm 6(N, R(N),, even though arm has empirical index strictly less than that of arm b(N, R(N)).
Using Corollary G.2 there exists constants Cg Cs Co > 0 independent of the sample paths, such that, for N T3 and R 2,, ..,, N).
I NN + R - 1) IM (N R 1) S - -C3 (N, R) CAN1-3a
+CG 30/8 +RN-1).
(100)
We define
C = max {
20, Di, D₂C3
+
68

---

where D1 and D2 are the constants introduced in Lemma G.15 Let M52 2 1 to be the smallest
number such that, every N Ma² satisfies (CI.N-3000 N. Since C₁ > D1, by the defimition of M51 in the proof of Lemma G.15, we have M52 > M51.
Now let R(N)- = 38/87. Then by Lemma G.15 for N 2 max{M52 Toh, since R(N) >
[D -3//88, we have,
2C4 N1-3a/8
(N,, R(N)) 2 D2R(N) 2 C3
(101)
Since arm b(N, R) not pulled between the iterations T(N, R) and N R, we have AÑUN.RY (N,1) AN R) for all & E (T(NN - N, <(N, R) - 11, As result, by definition of b(N,R) R) we have,
R..
(N,, N) and ANN (N, R(N)) = ANNON. (N, R(N)) - N).
b(N, R(N))
In the rest of the proof, we denote b(N, R(N)) and ((N)) - N, respectively, using b(N) and (N))
Therefore, using Corollary G.2, we have, for N 2 Ms2, Ts).
(N + (xN) 1) - (N + (NN) 1)
+ C1N-- + CSTO(N) (N 3N/3 + +T((NN- < C,
1 IA (1)
2Cs N 130/88 + +GN 13//8 CgR(N) x (N -3//8 +R(N)N-1
C's x
C3
C4N1 -a/8 + C + +)( + 2) 33/88 x N 3a/8
-C4 N N1-3//8
(102)
where: (1) follows using 1101 and To (N) < R(N), (2) follows since R(N) S (CI + 1)N55 and (3) follows by letting Co = Cs(C1 + 1) +2).
We now take M1s 2 1 to be large enough, such that, CaM 3a/8 < C.. Let M3 = max,Ms2, Mra Then (12) implies, for N 2 max(M5, }e and R(N)= = N1 (3/133/87 if the algorithm picks some arm a [[[1]] iteration N and doesn't pick for the next R(N) iterations, then, iteration N +++x(N) ), the algorithm picks arm b( N), even though, I. (N (N) -0) 1 (N (N+ Thus we arrive at a contradiction.
H Proof of Theorem 3.1
By Proposition 3.1 we know that, for every E [K] and N 2 Tatabee
30/8 (N)) - w/ < -
Recall the functions (..-.) defined in Appendix G.2.2 Note that for every allocation w (Wa)aE(K), and a E [K]/ we have,
aWa Ww), (1,1,, and owr
aW. Ow's
wa) d(pa, 211 (1,1 Wa)),
where I1,a (w), wi po tWafa
As result, for every a E [K]/[1}, the partial derivatives of Wa (W), wa) with respect to W1 and Wa are both O()). Therefore, using the mean value theorem, for every [K]/[1} and N > T Tatabee we have,
W (To, (N), (N)) Wa (w] wi)l = 0888..
(103)
69

---

Define the normalized index of every amm as
(NV) Ha(N) = N
(a(21(().
Also by 54
Wa (w), = 1 =T (1)) for every alternative arm E [K]/(1}.
Therefore (033)
gives us,
Ha(N) - T" (M) = (LN-88/8), for a E [K]/[1} and N 2 Tstable
(104)
By Lemma G.3 also know,
[T(N) (H)(N) [Ia(N) [.NN) O(N1-33/8).
(105)
Combining (104) and 105), get
[2, NT (1) S [I,(N) - NH.(N)) N - (1)
O(N1-3a/8)
for every a E [K]/11) Hence, we can find a constant C2 > 0, independent of the sample paths, such that,
Ia(N) 2 (*)) - -C2---30/88
for every N 2 Tttabl and a E [K][[1} As result, for N 2 Tstables we have,
N C2N1-3a/8
min aE (E(K)/(1
In(N) 2
(106)
(p)
The threshold function 3(N, 8) deciding stopping condition satisfies, log(1/8) < 6) < log(1/8) + C3 log log(1/6) + C4 log log(N) + Cs
for constants C3, C4, C3 > For every O, we define the deterministic quantity,
N
C2N1 3(N,6) }
m
min
N
Totabie
(107)
(*)
Now we make the following observations about fmax,66
1. Note that T*(a) C2N1-30/8 increases linearly in N and ((N,8) is Ollog log(N) log(1/6)), for fixed 8 > O. Hence, m is finite for every 8 0.
N
2. We have 3(N,0) 2 log(1/5) and N atleast the iteration at which T-( exceeds log(1/6), which is atleast (H) log(1/8). This implies faax (p) log (18)) As result, 6max.5 as 6 0.
C2N1133// < [T) As a result, 4max, is (")
N
3. If Ta > Tatatle then min.e (NV exceed B(N, 8) before the lower bound of minae[K]/(U) (N) in (106) exceeds ((N, 8). As a result, To S fmax,5 whenever Ta 2 T Tstable. This gives us the upper bound,
< max Tatailt 1maax a.s. in PH
(108)
We have [Tstaate < oc, which also implies Tatable < oo a.s. Pp,, Now using 108).
we get,
E [8]]
1 [T stable] tmax.8
tmax
simsup 8-40
limsup 8-10
lim sup
log (1/5)
log(1 (1/6)
8-40 log(1/5)
70

---

Similarly, we have,
Tstable + +max,8
6max.6 log(1/8)
sup 6-+0
lim sup 5-+0
lim 6-+0
a.s. in P.
log(1/6)
log(1/6)
Therefore to prove asymptotic optimality, is sufficient to prove lim sups-0
fmax
S (T))).
log[1/0]
Let 8max.,6 = 6
Note that sups (1/6
lim sups-0 Tog(785)
By definition of
6max,ó, we have
Smax.6 (1)
1-
2 (s 8) log(1/0) C3 log log(1/0) + C4 log log (axx) + Cs.
After some rearrangement of terms, upon dividing both sides by log (16)), get,
8
(1
C2s
max,6
30//8
CCs max,6 log log( s maxx66)
(H) log
log log (1/6)
-ssmaxxs)
+ C3
log(1/6)
By Observation 2, Smax,5 6max.6 as d O.
As a result, the above inequality implies,
Smax,
lim sup
1.
(#)
5-+ 1og(1/0)
We already argued that lim sups-10 log(1/8)
fmax,
T (H). As a result, we have constant C. > 0, such
/8)
that m S Cs 1og(1/8) for all By 108 we have:
maxx6 -1 C2(tmaxx. 1)¹ 13188 S B( 1, 1,
(H)
which implies,
m S T (p) log(1/6) O (log (oggoo/118) =
Putting 6mxx S Co log(1/6) in the above inequality,
mmax, S T (1)) log(1/5) + O (log(116))) 23///)
(109)
Since To I max 1 + tm we can find a constant C 0 such that max (T (H) (og(1/8) + ((1)(()))))1-3a/}) Hence Theorem 3.1 stands proved.
I Extending the proposed algorithm to distributions with bounded support
We describe a natural extension of AT2 and IAT2 algorithms bandit instances from a non- porrmmrrtt 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 Fio.1)- This is similar the assumptions made in [16]. Some definitions are in order. We use ((G) to denote the mean of distribution G Fio.1]
For every F E F10.11 and x E [0, 1], we define KL and KL as:
KL (F, = inf{ KL(F, G) ((G) > x and KL (F,x) = inf KL(F,G) ((G) < x
At iteration N of the algorithm, let (N) be the empirical distribution the samples collected from some arm E [K]. F(N) (Fa (N) : E [K]), (N) be the total no. of samples collected from
till and ((V) (N) : a [K]). Let (NN ((F)(N)) and êN arg ma (NV..
We now define:
T ia (N) arg min
Now (N) KL (F. (N), + Na KL (F(N)(()(
zE
71

---

At every iteration, we compute the empirical index of every arm + iN as: Na(N) KL
(N)
min =E(0.1)
{
New (N)
and the anchor function as,
KL (F (N), (N))
9 ((F(N), = Σ
1.
KL ( (Pa
(N), A (N))
atiN
The AT2 and IAT2 algorithm for the class Flo.1), respectively, follows the same steps as in and with the anchor and index functions defined as above.
We experimentally demonstrate the performance of the proposed algorithms in Appendix 0.5
J Experiments
J.1 Dynamics of the algorithms
Experiment 1 (Gaussian and Bernoulli bandits with well-separated arms): In the main text (Figure T.. we presented the evolution of normalized indexes for the sub-optimal arms for AT2, when without the stopping rule. Numerically, observe similar plots for normalized indexes for the other algorithms: 0.5-EB-TCH (proposed in [16] with 3 = 0.5), and TCB (proposed in (22]). Hence, do not report them. However, do observe differences in the evolution of the anchor function value across these algorithms. We present this in two different settings in the current section.
Interestingly, as per our implementations, we observe that only AT2 satisfies the asymptotic optimality conditions, maintaining the anchor function close to 0, addition to maintaining the equality of the normalized indexes.
In this section, we consider the following two examples:
1. Gaussian bandit. In the first setup (Figure 4 we consider a 4 armed Gaussian bandit with unit variance and mean vector f [10, 6.5). This is the same setting in Section 6 from the main text.
2. Bernoulli bandit. In the second setup (Figure 5) we consider a Bernoulli bandit with means # [0.91, 0.73, 0.64, 0.59].
In Figures 4 and 5 we plot the evolution of anchor function value for the three algorithms in the two settings, without implementing the stopping rule. The solid lines in the figure represent the average of anchor function over 4, 000 independent runs. The shaded bands around the sold lines (almost invisible in these figures), represent 2 standard deviation bands around the mean.
We observe that only AT2 maintains the anchor function value close to O. Our experiments suggest that that TCB algorithm, as per our implementation, doesn't t satisfy the asymptotic optimality conditions.
J.2 Sample complexity comparison
In Section i the main text, we compared the sample complexities (SC) of the three algorithms well-sepane selaasep Gaussian bandit (Figure[). In this section, we compare the SC of all the algorithms, as function of different parameters. We consider harder Gaussian well as Bernoulli bandit instances (with means close to each other), presented below.
1. Gaussian bandit. A 4 armed Gaussian bandit with unit variance and mean vector f (7.25, 7.05, 7, 7.1] so that the means are closer together.
2. Bernoulli bandit. As second example, we consider 4-armed Bernoulli bandit with close-by by means: μ = [0.99, 0.96, 0.95, 0.97].
Experiment (SC as function of 3): this experiment, we compare SC (l)AT2, (I)CBB, 3-EB- (I)CBB algorithms, for 3 [0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8). on the Gaussian instance (Figure 6) and the Bernoulli instance (Figure 7 described above. The error probability in both these experiments is set to 0.001. All the algorithms use the same forced exploration rule and stopping rules.
72

---

Anchor function va
Anchor function value
2.0
102
15
0.
250
750
1000
300
1200
1530 2000
2300
Figure 4: Anchor function value for easy Gaussian bandit (Exp.1), 1), averaged over 4,000 sample paths.
Figure 5: Anchor function value for easy Bernoulli bandit (Exp.1) 1), averaged over 4,000 sample paths.
The lines with the markers in the figures represent the average number samples generated before stopping, averaged over 4, 000 independent simulations, while the shaded regions denote 2 standard deviations around 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 TCB and ITCB.
Sample Complexity
3000
Bea ESTIC
2750
Algorithm AT2
Avg.
Dev.
2013.0
17.85
IAT2
1925.9
2500
0.5-EB-TCB
2084.84
17.74
Number
0.5-EB-TCBI
1987.92
16.33
2250
TCB
2109.82
17.82
ITCB
2041.03
16.55
2000
Beta
Figure 6: Sample complexity (SC) Gaussian bandit from Exp. 2, averaged over 4, 000 independent sample paths. = 0.001
Sample Complexity
8000
IRT2
TTES
7000
Algorithm
Avg. SC
Std. Dev.
AT2
4735.09
50.4
TAT2
4412.16
27.36
T.B-B--TBB
4735.65
45.44
Number
6000
0.5-EB-TCB TCBI
4426.59
27.27
TCB
4972.07
49.64
ITCB
4681.63
28.52
5000
6.4
0.5
Figure 7: Sample complexity (SC) on Bernoiulli bandit from Exp. 2, averaged over 4, 000 independent sample paths. 5 0.001
73

---

Experiment 3 (SC as function of 8): In Figure 8 and Figure 9 three algorithms AT2, 0.B-EB-TCB. and TCB as 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 5.
we plot the sample complexities of the
Sample Complexity
Sample Complexity
12503
530
ToR 0.5-aa-cc
Number of Samples
Number Samples
1503
5003
230
130
18
1/de ta
1/delta
Figure 8: Sample complexity of Gaussian bandit Figure 9: Sample complexity for Bernoulli bandit (Exp.3), averaged over 4,000 sample paths.
(Exp.3), averaged over 4,000 sample paths.
Experiment 4 (SC function of number of arms). We plot the number of samples needed by the three algorithms, as a function number of arms in the bandit instance. 5 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 unit variance. Arm 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
# = S...)......
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 I0, 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 increase for smaller values of 6.
Sample Complexity
AT2
BLS-Mt--TC
Number Samples
500
300
100
40
66
50
(number ars)
Figure 10: Sample complexity on Gaussian bandit (Exp.4), averaged over 4, 000 independent sample paths.
J.3 Runtime comparison
Experiment 5: this experiment, we compare the run-time of (I)A22 and (I)TCB algorithms on
4 armed Gaussian bandit with means μ [10, 9.4, 7, 6.5] and unit variance, averaged over longer
74

---

100,000 simulations. 8 is set to 0.001, and the four algorithms use the same forced exploration and stopping rules.
Table represents the average run-time of the two algorithms. We observe that TCB and ITCB take roughly two times more computational time compared AT2 and IAT2, respectively.
Algorithm
Avg. Sample Complexity
Std. Dev.
Avg. Run Time (microsec.)
Run Time Std. Dev.
AT2
90.53
0.2
129.76
32.34
LAT2
90.63
0.2
310.76
55,88
TCB
96.55
0.21
501.22
82.60
ITCB
96.69
0.21
845.19
145.97
Table 1: Runtime of (I)AT2 and (I)TCB on Gaussian bandit with μ = [10, 9.4, 7, 6.5] and unit variances (Exp.6). Results reported are for 100, 000 independent runs of each algorithm.
J.4 Effect of forced-exploration parameter a on sample complexity
In this section, we provide numerical evaluation of the impact of forced exploration 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 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 16 for 3-EB-TCB.
Experiment 6: To see the above mentioned behavior of AT2, we study the performance of AT2 and IAT2 the following two bandit instances.
1. A 4 armed Gaussian bandit with unit variance and mean vector fa [7.25, 7.05, 7, 7.1,, that the means are close together, yet all different.
2. A 4 armed Gaussian bandit with unit variance and mean vector μ [7.25, 7, 7]. so that the three suboptimal arms have equal means.
Intuitively, it might appear that forced exploration could significantly increase the sample complexity of AT2 and IAT2. However, in Figure [1] we see that IAT2's 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 the amount of forced exploration done.
Sample Complexity
Sample Complexity
1AT2
5 30x20
AT2
Number Samples
Number Samples
5 60x20
40xid
20x10
0.0
6.4
06
0.5
0.2
5.4
08
Explaration exponent (a phs)
Exploration exponent (alpha)
Figure 11: Sample complexity of Gaussian bandit with means μ = [7.25, 7.05, 7, 7.1], as function of (Exp.6)
Figure 12: Sample complexity of Gaussian bandit with means j = [7.25, 7, 7, 7]. as function of (Exp.6)
75

---

J.5 Experiments for bandits with bounded-support distributions
In this section, we experimentally demonstrate the performance of natural extension of AT2 to non non-parametric setting of bandits with arms having distributions supported in [o, 1] (see Appendix | for the modified AT2). This is the setting considered in, for example, [[6].
Experiment 7: Consider a 4-armed handit with the following arm distributions:
[1t 1), B2ta 6), Bota(1, 1.5), and Bcta(1, 7).
Here, the arms have means
/ [0.6, 0.25, 0.4, 0.125]
While we do not provide the analysis of the algorithm for this setting, numerically we observe that in this non-pan con-aaamctticc setting. extension of AT2 to this setting outperforms 3-EB-TCB and corresponding natural extension of TCB to this setting.
Sample Complexity
Sample Complexity
TCB
Number of Samples
Bita mnB Beta-EB-rCC
of Samples
250
225
200
1/delts
Figure 13: Sample complexity (Exp.6), averaged Figure 14: Sample complexity (Exp.6), averaged over 4,000 sample paths. We 6 0.001.
over 4,000 sample paths.
Reproducibility: Our code is implemented in Julia 1.7.1, and the plots are generated with the Plots. j1 package. Other dependencies are listed in the Readme md file, which also includes instructions to reproduce the figures and tables presented here. We build upon the publicly available code for [16]. Our experiments are conducted on institutional cluster computing facility having an Intel Xeon Gold 6130 2. GHz CPU with 32 cores.
76

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The optimality of the proposed algorithm is proven in Theorem 3.1 We also
demonstrate the dynamics of the algorithm, as proposed in Theorem 4.1 via numerical simulations.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitations of the results presented in this paper due model assumptions such that independence, considering bandit instances from an SPEF, etc. the end of Section
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We include all the assumptions made in the statements of the results. We provide all the formal proofs in Appendix, and refer to them. All the theo- rems/lemmaa/prrpositton are numbered and referenced appropriately.
4. Experimental Result Reproducibility
Question: Does paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our key contribution is new algorithm with its theoretical guarantees. We perform numerical simulations to support the theoretical results. We include all the imple- mentation details with the choices for different parameters in our numerical experiments discussion in the Appendix[]
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We include the code with scripts for reproducing the numerical results.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We include the choices of all the parameters in each simulation.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: We include mean and standard deviations our experiments, along with the assumptions made (independence of different runs of same simulation).
77

---

8. Experiments Compute Resourees
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: We use an institutional computing facility for our experiments (see, end of Appendix [
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect. with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The results of this work are theoretical in nature. We appropriately reference all existing works the best of our knowledge. We include justifications for all the results, and implementation details for reproducing the simulation results of this work.
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The main contributions of this work are theoretical in nature. While we propose a new algorithm, there are no harmful societal impacts or consequences of this research.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We numerical simulations. We do not any publicly available datasets for our experiments.
Licenses for existing assets
Question: Are the creators original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Please see paragraph on Reproducibility in Appendix
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not release any new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowd sourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
78

---

Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
79


Reviews:
[{"review_id": "386oFe3Umn", "reviewer": "Reviewer_4f2z", "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.", "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?\n\n- 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": "The limitations are adequately addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The method proposed is the first fully adaptive choice of the proportion $\\beta$ that ensures asymptotic optimality for all single parameter asymptotic families. Another optimal method was already proposed in [28], but only for Gaussian distributions.\n\n- The fluid dynamic model is particularly interesting: it gives a good intuition of why the dynamic for $\\beta$ converges to the right proportions. It is also a very original approach to the study of bandit identification algorithms.\n\n- The authors propose a full algorithm (leader and challenger choice as well as the new adaptive proportions $\\beta$), but the new adaptive proportions could presumably be used with other choices for the leader and challenger, and could become a generic tool for asymptotically optimal top-two algorithms.\n\n- The paper is clear and explains the idea behing the new method very well.", "weaknesses": "- 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].\n\n- 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.\nI did not find the value of $\\alpha$ used in the experiments and the effect of that parameter was not studied experimentally.\n\n- 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.\n\nRemarks and typos:\n\n- A remark about this review: the paper including the appendix is 75 pages long, hence I could not check every proof.\n\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestions and provide our responses below.\n\nWe first address the weaknesses.\n  \n**[Asymptotic results of the paper]** We thank the reviewer for pointing us to the recent reference [Jourdan and Degenne, '23]. We respond to it in **(3)** of the global rebuttal. \n  \n**[Experiments involving exploration parameter** $\\alpha$ **]** This is an extremely important point. We address it empirically in **(1)** of the global rebuttal and have added the experimental details in the revision. \n\n**[Extending the analysis to other problems]** Our analysis can be used for proving asymptotic $\\beta$-optimality of the $\\beta$-EB-TC (I) algorithms in [16] by using the anchor function $g=\\beta-\\frac{N_1}{\\sum_{a\\in[K]}N_a}$ (see Appendix E.2). We also expect it to work for best $k$-arm selection as in [28]. In general, many algorithms in the bandit setting rely on keeping indexes close to each other. Our fluid approach may be useful while analyzing these settings.  \n\nWe now update to $\\beta$-EB-TC (I) from [16] in the revision. \n\n**Response to questions:** \n\n**[Use of forced exploration in analysis]** We need forced exploration **only to prove**: The estimated means converge to the actual means at rate $O(N^{-3\\alpha/8})$ ($\\alpha$ being the exploration parameter) after a random time $T_0$ of finite expectation independent of $\\delta$. Our analysis will work if we can prove a sufficient exploration lemma (like in [16] showing $\\Omega(\\sqrt{N})$ exploration of every arm for the $\\beta$-EB-TC (I) policies) for the proposed algorithms, and asymptotic optimality will follow. \n\n**[Bounding the time to reach optimal proportion]** The argument in Section 4 to bound the time to reach optimal proportion implies that: The fluid dynamics reach optimal proportion at time $N_a^0/\\omega_a^\\star$ where $a$ is the sub-optimal arm whose index is met last by the fluid dynamics, which will give us an upper bound $N^0/\\omega_a^\\star$. If the worst arm (which also has minimum optimal proportion) has the largest no. of samples to begin with (i.e. largest value of $N_a^0$), then the worst arm has largest index throughout the fluid dynamics. As a result, the arm with minimum optimal proportion is hit last, giving us the upper bound $N_K^0/\\omega_{\\min}^\\star$. Since the worst arm has maximum no. of initial samples, $N_K^0$ can be arbitrarily close to $N^0$, giving us the tight upper bound $N^0/\\omega_{\\min}^\\star$. The above argument gives us a tight upper bound for the time to reach optimal proportions for the fluid dynamics. Since the algorithm closely tracks the fluid dynamics after a random time $T_0$ of finite expectation, similar worst case bounds hold for the algorithm as well. \n\nNote that for $\\delta$ large (say 5%), the algorithm may reach its stopping time before the largest index is hit. In that case, even in the worst case as above the upper bound $N^0/\\omega_{\\min}^\\star$ may be loose.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g8B2WetUU0", "reviewer": "Reviewer_Aqmy", "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.", "questions": "1. possible typos: \"There\" -> \"Their\" in line 88?\n2. What is $a$ in the equation at the end of page 3?\n3. Why the threshold for function $g(\\cdot)$ in the algorithm is 0? Is it possible or trivial to change to other thresholds?\n4. Why the stopping condition is ignored as mention in line 249 for the fluid dynamics?", "limitations": "See weakness.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper discusses an important question which is to find the optimal $\\beta$ in the Top-Two algorithm and shows a sound solution (AT2 algorithm) to solve this problem.\n2. The contributions are solid and they novelly use the fluid dynamics to describe the behaviors of the proposed algorithms.\n3. The tools for proving the upper bound of the sample complexity of the proposed algorithms are also novel enough.", "weaknesses": "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.\n2. The experiments lack some more explanations to discuss the meanings behind.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestions and provide our responses below.\n\nWe first address the weaknesses pointed out.\n\n**[Dynamics of the ODEs]** We illustrate the evolution of anchor function and indexes in the fluid dynamics in Figure 2 of the pdf attached with the global response. In the figure, we can see that, the fluid dynamics start at an allocation with positive value of the anchor function. After that, as $N_1$ increases, the anchor function decreases and becomes zero nearly at time $50$. After that, the fluid dynamics keeps on maintaining the anchor at zero and gives samples to the first arm and minimum index arms. We can observe in the plot that all the indexes are hit eventually and the black index, corresponding to the worst arm, is the last index to be hit. Moreover, after the last index is hit, the fluid dynamics follows the optimal proportions. \n\n**[Intuition behind steps of the algorithm]** The intuition behind the algorithms is derived from the first order conditions in the lower bound optimization problem and is discussed in **(2)** of the global response. We have added this to the revision. We had provided some intuitions in the earlier draft in the introduction in the lines 54-70. \n\n**[Explanation of the experiments]** Owing to space constraints, we restricted our discussion in Section 6 of the main body to: (1) Illustrating that the algorithm closely mimics the fluid path, and (2) Comparing the proposed algorithm with the existing $\\beta$-EB-TC(I) [16] and (I)TCB [21] policies. We provide the detailed experiments in Appendix J. \n\nWe were a little concise in our attempt to explain the underlying intuitions governing the algorithm. With the addition of Fig 2 in the pdf attached to global rebuttal and the associated discussion, we now explain the intuitions better. \n\n**Response to the questions:**\n\n**[Keeping the anchor at threshold zero]** By Proposition 2.1, the optimal proportion is uniquely identified by the first order conditions: the anchor $g=0$ and indexes of sub-optimal arms are equal. If we modify the threshold of the anchor function to some value other than zero, then the algorithm will converge to some allocation which won't be optimal. As a result, the proposed algorithms will suffer a higher sample complexity if we don't use the threshold zero, and will not be assymptotically optimal. In  **(2)** of the global rebuttal, we explain the intuitive reason behind choosing the specific threshold zero for the anchor function based on the first order conditions.\n\n**[Ignoring stopping condition in the fluid dynamics]** The stopping time condition was ignored to keep the discussion simple. It is easy to incorporate it. We simply keep track of the idealized GLLR (where the means are known) and stop when it exceeds the threshold $\\beta(N,\\delta)$ defined in line 200. The fluid dynamics may stop before the system reaches stability. We have added this comment to the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ppnjdO5CEb", "reviewer": "Reviewer_jbje", "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.", "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": "NA", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "\"Top-2\" approaches for best arm identification are powerful and increasingly popular, so this paper's focus is an important area of study. Posing the problem in terms of fluid dynamics could potentially be a powerful way of modeling the problem.", "weaknesses": "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). \n\nThe presentation of this paper needs to be significantly improved before it is ready for publication.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestions and provide our responses below. \n\nWe first address the weaknesses pointed out.\n\n In the revision we have attempted to improve the exposition, including the mathematical presentation.  We would appreciate further specific suggestions that you may have to improve the presentation. \n\n**[About Proposition 2.1 statement]**  It will be really helpful \nif the reviewer specifies the parts of Proposition 2.1 statement that are not understandable. We explained the notations and quantities involved in the statement of Proposition 2.1 in the discussion before the proposition. As Reviewer Uo1U pointed out in the first weakness, the only mild confusion in the proposition statement was the meaning of $x_{1,a}$ in the new space of allocations $\\mathbf{N}$. We now clarify it in the revision. \n\n\n**[Unexplained concepts]**\n\n- **Implicit function theorem (IFT):** This is a classical result in real analysis and is widely used in optimization theory. We now add a reference [Luenberger and Ye, Linear and non-linear programming] to the revision.\n\n- **Generalized log likelihood ratio (GLLR):** The GLLR test is a standard result in the best arm identification literature.  While defining the stopping rule in Section 3, we referred to [13, Section 3.2] for a detailed derivation of the GLLR test. We couldn't provide this derivation in the main body of our paper due to space constraints.\n\n\n**Response to the question:**\n\n**[Pulling both leader and challenger]** This algorithm essentially a stratified version of $\\beta$-EB-TC policy in [16] with $\\beta=1/2$ (see, e.g., [Paul Glasserman, Monte Carlo methods in financial engineering] for use of stratified sampling in simulation). By modifying the anchor function to $g=1/2-\\frac{N_1}{\\sum_{a\\in[K]}N_a}$, our analysis in Appendix E.2 implies that the proposed strategy will converge to the $\\beta$-optimal proportion with $\\beta=1/2$. The proposed strategy won't be asymptotically optimal if the optimal $\\beta$ (which is same as the optimal value of $\\omega_1$ in the min-max problem in Eq. (1)) is different from $1/2$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Yxpm16ih4N", "reviewer": "Reviewer_Uo1U", "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.", "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. \n\nAlong 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": "NA.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "The use of the theory of ODEs and the implicit function theorem to demonstrate the asymptotic optimality of the proposed algorithm is the novel aspect of this paper. To the best of my knowledge, such an approach to the demonstration of asymptotic optimality does not exist in the literature on fixed-confidence BAI. Furthermore, while the concept of *anchor function* appearing in the paper has its roots in Garivier and Kaufmann's paper on BAI, a careful analysis of its behaviour using the theory of ODE to demonstrate asymptotic optimality of the proposed algorithm is impressive. \n\n(I must acknowledge, though, that I was unable to go through the extensive and detailed appendix due to paucity of time.)", "weaknesses": "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.\n\n1. 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.\n\nSome minor comments:\n\n2. \"alocation\" in line 160 --> \"allocation\".\n\n3. $f(\\boldsymbol{\\mu}, a, N)$ in line 291 --> $f(\\boldsymbol{\\mu}, a, \\boldsymbol{N})$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestions and provide our responses below.\n\nThe typos have been corrected in the revision. Thanks. \n\n**Response to the questions:**\n\n**[Intuitive reason of using the anchor function]** The proposed algorithms are motivated by the first order conditions which uniquely identify the optimal proportion (see Proposition 2.1). In **(2)** of the global rebuttal we explained the intuition behind the algorithm, choice of the particular anchor function and setting it at threshold zero. Also see our response \"Intuition behind the steps of the algorithm\" to Reviewer Aqmy.\n\n**[Sub optimality of (I)TCB [21]]** [21] implicitly assumes that having all indexes equal and the proportion weights summing to 1 uniquely identifies the optimal allocation ([21, Lemma 2]). This uniqueness is true with the constraint $w_1=\\beta$ as in [Russo, Simple Bayesian Algorithms for Best Arm Identification]. However, simply having all indexes equal and sum of the weights equal to one ([21, Lemma 2]) imposes K-1 conditions on K variables allows one degree of freedom, which is optimized at $g=0$.  See the discussion at **(2)** in the global rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bLsrGP4CP2", "reviewer": "Reviewer_mata", "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.", "questions": "1. Line 634-637: What about a Bernoulli distribution with mean zero?\n2. 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?\n3. 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": "The main contributions of this work are theoretical in nature. I don't foresee any direct negative social impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a novel method for determining the optimal $\\beta$ in Top-2 algorithms, which has been a popular problem in the field. Empirical results demonstrate that the proposed method offers improved sample complexity and computational efficiency compared to existing approaches.\n2. The analysis leverages fluid dynamics and the implicit function theorem to establish the algorithm's optimality, marking a unique and intriguing contribution to the field of bandit problems.", "weaknesses": "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestions and provide our responses below. \n\nWe first address the weaknesses.\n\n**[Use of forced exploration in analysis and experiments]** We address this weakness in **(1)** of the global rebuttal and in our rebuttal to Reviewer 4f2z at \"Use of foced exploration in analysis\".  We used the same forced exploration rule and stopping rule for all algorithms. We have added this detail to the experiments section of the revision.\n\n\n**[Non-asymptotic results]** We address this weakness at **(3)** in the global rebuttal. \n\n**Response to the questions:**\n\n**[Bernoulli distribution with mean zero]** If we consider the SPEF generated by some non-degenerate Bernoulli distribution, then all members in that SPEF will also be non-degenerate, i.e., they will have their mean in the open interval $(0,1)$. Note that Bernoulli with mean zero is a degenerate distribution and therefore cannot be a part of that SPEF. For a Bernoulli SPEF, $\\mathcal{H}(\\mu)$ in lines 634-637 is only defined for instances having their mean in $(0,1)$. Also by construction, $\\mathcal{H}(\\mu)$ is compact and a subset of $(0,1)$. As a result all distributions in $\\mathcal{H}(\\mu)$ are non-degenrate and, as argued in lines 635-637, the minimum variance of such distributions is positive.\n\n**[Alternate definition of** $\\delta$-**correctness]** The suggested definition $\\mathbb{P}(\\tau_\\delta<\\infty)=1$ and $\\mathbb{P}(k_{\\tau_\\delta}\\neq 1)\\leq \\delta$ of $\\delta$-correctness is subsumed in the definition $\\mathbb{P}(\\tau_\\delta<\\infty,k_{\\tau_\\delta}\\neq 1)\\leq \\delta$ in lines 143-144. The non-asymptotic bound in Theorem 3.1 implies that the AT2 and IAT2 algorithms satisfy $\\mathbb{P}(\\tau_\\delta<\\infty)=1$ and $\\mathbb{P}(k_{\\tau_\\delta}\\neq 1)\\leq \\delta$.  \n\n\n**[About sub-optimality of (I)TCB in [21]]** As we mentioned in our response \"Sub-optimality of (I)TCB [21]\" in our rebuttal to Reviewer Uo1U, (I)TCB may not be asymptotically optimal since it does not reinforce $g=0$ condition. Our experiments, as per our implementation, also demonstrate this (Figures 3, 4), where we see only AT2 satisfies the optimality conditions ($g=0$).\n\n\n**[Computational complexity of AT2 and IAT2]**\n\n- **Per iteration computation:** If we consider that every $KL$-divergence computation takes only a constant amount of time independent of the instance $\\mu$ and the no. of arms $K$, then every iteration of the AT2 and IAT2 algorithms require only $O(K)$ time to execute. We have mentioned this in the revision.\n\n- **Overall expected computational complexity:** Since getting a non-asymptotic bound of $\\tau_\\delta$ is challenging in this setting, we do not have a overall bound of the expected computational complexity (see **(3)** of global rebuttal on non-asymptotic bounds over sample complexity). However, experiment 4 in Appendix J.2 shows that, the expected sample complexity of the proposed algorithms increases linearly as a function of the no. of arms.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Here we address questions/weaknesses raised by more than 1 reviewer. The manuscript will be updated as per our reponses.

**1) Conjectures on sufficient exploration and numerical experiments supporting them:** As reviewer 4f2z rightly pointed out, AT2 needs forced exploration. Otherwise, for instances where the second and third best arms have equal means, AT2 might see some bad samples from the best arm in the beginning. After that, AT2 will sample forever from the second and third best arms. Following Reviewer 4f2z's comment, we **conjecture** that: AT2 will do sufficient exploration for instances having all arms with different means. Intuitively, it might appear that force exploration significantly increases the sample complexity of AT2 and IAT2. However, in the experiments, we see IAT2's performance remains unaffected and AT2 performs atleast as well as IAT2 with moderate amount of forced exploration even for instances where gap between the means is small (see Figure 1.a of the attached pdf). We further conjecture that IAT2 performs sufficient exploration for all instances, including those where multiple sub-optimal arms have equal means. In Figure 1.b of the attached pdf, we consider a four armed instance where the three sub-optimal arms have equal mean. We observe that without forced exploration, AT2's sample complexity blows up, and IAT2 performs significantly better than AT2. Furthermore, IAT2's sample complexity remains almost unaffected w.r.t. the amount of forced exploration done. Proving sufficient exploration for the proposed algorithms appears to be technically challenging and the proofs are likely to be lengthier.  


**2) Intuition behind the choice of anchor function and algorithm:** Statement 2 of Proposition 2.1 implies: The optimal proportion solving the min-max problem in Eq.1 is uniquely identified by the first order conditions: (1) Anchor function $g=\sum_{a\neq 1}\frac{d(\mu_1,x_{1,a})}{d(\mu_a,x_{1,a})}-1$ evaluated at the proportion is zero, and (2) Index of all the sub-optimal arms are equal. The proposed algorithms (AT2 and IAT2) chase these first order conditions. At every iteration, the sampling strategy of AT2 and IAT2 pushes the anchor function $g$ towards zero. Once the anchor function becomes approximately zero, the proposed algorithms attempts to maintain equality of the indexes by choosing the minimum index arm as challenger (see Section 5 for detailed arguments). Thus the proposed algorithms converge to the first order conditions (see Proposition 5.1), which also implies convergence to the optimal proportion (see Proposition 3.1), and hence, asymptotic optimality follows (see Theorem 3.1). We made an attempt to explain these intuitions in the "contributions" section of the introduction. 

Below we provide a simplier argument to support the appearance of the anchor function $g$ in the first order conditions. The lower bound problem of sample complexity for a chosen confidence level $\delta$ can be alternatively expressed as solution to the problem $\mathbf{O}$ defined in Eq. 20 of Appendix D. Note that $\mathbf{O}$ is an optimization problem over $K$ variables. We reduce this to a single variable optimization problem with $N_1$ being the only free variable. In Theorem D.1 we prove that the index constraints are tight at the optimal solution of $\mathbf{O}$ i.e. $W_a(N_1,N_a)=\log(1/(2.4\delta))$.  So, we can restrict to allocations where index of the sub-optimal arms are $\log(1/(2.4\delta))$. Fixing some $N_1\geq 0$, let $\bar{N}_a(N_1)$ be the *unique* value of $N_a$ at which $W_a(N_1,N_a)=\log(1/(2.4\delta))$. We take $\bar{N}_a(N_1)=\infty$ if no such $N_a$ exists.  

Thus $\mathbf{O}$ is equivalent to the single variable optimization problem of minimizing $f(N_1)=N_1+\sum_{a\neq 1}\bar{N}_a(N_1)$ over $N_1\geq 0$. Each $\bar{N}_a(N_1)$ is strictly decreasing and differentiable with derivative $-\frac{d(\mu_1,x_a(N_1))}{d(\mu_a,x_a(N_1))}$ where $x_a=\frac{N_1 \mu_1+\bar{N}_a(N_1) \mu_a}{N_1+\bar{N}_a(N_1)}$.  

Hence $f^\prime(N_1)=1-\sum_{a\neq 1}\frac{d(\mu_1,x_a(N_1))}{d(\mu_a,x_a(N_1))}$, which is exactly the negative of the anchor $g(\cdot)$ at the allocation $N_1$ and, $N_a=\bar{N}_a(N_1)$ for $a\neq 1$. Through differentiation it can be seen that $f(N_1)$ is strictly convex w.r.t. $N_1$ and attains its unique minimum when $g=0$. The (I)TCB algorithm's sampling strategy can be sub-optimal. We discuss this further in response to reviewer Uo1U. 

**3) Getting non-asymptotic upper bounds:** Proving non-asymptotic  upper bounds to sample complexity which asymptotically matches the lower bound is a challenging research direction in the best arm identification literature.  In Theorem 2.1, we prove an almost sure non-asymptotic upper bound of the stopping time $\tau_\delta$, where we hide the order of dependence of the instance dependent constants. Understanding exact dependence of these constants requires more technically involved arguments.  [Jourdan and Degenne, Non-Asymptotic Analysis of UCB-based Top Two Algorithm] provides a non-asymptotic analysis of a $\beta$-Top two policy, which uses UCB leader and is asymptotically $\beta$-optimal over the family of Gaussian instances with fixed variance. Their upper bound also holds for sub-Gaussian instances. Moreover, their upper bound asymptotically grows like $2T^{\star}_{1/2}(\mu)\log(1/\delta)$ for $\beta=1/2$ and doesn't match the lower bound. We expect that, their approach of choosing the UCB-based leader and  constructing concentration events over the empirical mean and the indexes can be extended for proving non-asymptotic upper bounds for the AT2 and IAT2 algorithms over a Gaussian family, but again we may have a higher constant compared to the lower bound.

Meta-review: 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.
Decision: Accept (poster)