Top Two Algorithms Revisited
Authors: Marc Jourdan
Rémy Degenne
Dorian Baudry
Rianne de Heide
Emilie Kaufmann
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-armed bandits
Best-arm identification
Bounded distribution
Top Two algorithm
Thompson Sampling

Abstract: Top two algorithms arose as an adaptation of Thompson sampling to best arm identification in multi-armed bandit models for parametric families of arms. They select the next arm to sample from by randomizing among two candidate arms, a leader and a challenger. Despite their good empirical performance, theoretical guarantees for fixed-confidence best arm identification have only been obtained when the arms are Gaussian with known variances. In this paper, we provide a general analysis of top-two methods, which identifies desirable properties of the leader, the challenger, and the (possibly non-parametric) distributions of the arms. As a result, we obtain theoretically supported top-two algorithms for best arm identification with bounded distributions. Our proof method demonstrates in particular that the sampling step used to select the leader inherited from Thompson sampling can be replaced by other choices, like selecting the empirical best arm.

Top Two Algorithms Revisited
Marc Jourdan'
Rémy Degenne' remy, d inria.fr
marc. marc. jourdan inriaanniiiiii......mm fr
Dorian Baudry' dorian, harrilanbauddyeniia...a
Rianne Heide² de. heide@vu.nl
Emilie Kaufmann'
emi www.ekaafaaannnnnmmmmmm iataamiiiilllei...
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9198-CRISAAL, F-59000 Lille, France Vrije Universiteit Amsterdam
Abstract
Top Two algorithms arose as an adaptation of Thompson sampling to best arm identification in multi-armed bandit models [38], for parametric families of arms. They select the next arm to sample from by randomizing among two candidate arms, leader and challenger. Despite their good empirical performance, theoretical guarantees for fixed-confidence best arm identification have only been obtained when the arms Gaussian with known variances. In this paper, provide a general analysis of Top Two methods, which identifies desirable properties the leader, the challenger, and the (possibly non-parametric) distributions of the arms. As a result, we obtain theoretically supported Top Two algorithms for best identification with bounded distributions. Our proof method demonstrates in particular that the sampling step used to select the leader inherited from Thompson sampling can be replaced by other choices, like selecting the empirical best arm.
Introduction
Finding the distribution that has the largest mean by sequentially collecting samples from pool of candidate distributions ("arms") has been extensively studied in the multi-armed bandit [6. 24) and ranking and selection [21] literature. While existing approaches often rely on parametric assumptions for the distributions, we are interested in (near) optimal and computationally efficient strategies when the distributions belong to an arbitrary class F of distributions.
For applications to online marketing such A/B testing [30, 37] assuming Bernoulli Gaussian arms fine, but more sophisticated distributions arise other fields such as agriculture. In Section consider crop-management problem: group of farmers wants to identify the best planting date for a rainfed crop. The reward (crop yield) can be modeled as a complex distribution with multiple modes, but upper bounded by known yield potential. Therefore, sequentially identifying the best planting date calls for efficient best arm identification algorithms for the class of bounded distributions with known range.
To tackle this problem, we build Top Two algorithms [38, 35,39], originally proposed for specific parametric families. We propose a generic analysis this type of algorithms, which puts forward new possibilities for the choice of leader and challenger used by the algorithm. In particular, this work leads to the first asymptotically 3-optimal strategies for bounded distributions.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Setting and related work
bandit problem is described by finite number of probability distributions (K many), called arms. Let Ax be the K K-dimensional probability simplex and P(R) the set of probability distributions over R.. Let C ((RR) be a known family of distributions to which the arms to. We will refer to tuples of distributions in JK with bold letters, e.g. F = (Fi...., FK) FK where F; is the edf of arm i. We suppose that all distributions in J have finite first moment and we denote the mean of F E F by m(F).. We denote by I = {m(F) F F} the set of possible means for the arms.
The goal of a best arm identification (BAI) algorithm is to identify an arm with highest mean in the set of available arms, i.e. arm which belongs to the set i" (F) arg m mi m((F). At each time n E N. the algorithm interacts with the environment (the set of arms) by (1) choosing an arm In based on previous observations, (2) observing sample Xn, ~ Fi,, and (3) deciding whether to stop and return an arm i, or to continue. We study the fixed confidence identification setting, in which we require algorithms to make mistakes with probability less than a given 5 E (0, To compare such algorithms we consider their sample complexity Ts. which is stopping time counting the number of rounds before the algorithm terminates. The goal is then to minimize [[[T]] among the class of 6-correct algorithms.
Definition 1. An algorithm is 8-correct on JKK if PF (Ts < +00, lrg & (F)) S for all F e FK
In order to be 8-correct on JkK an algorithm has to be able to distinguish problems in FK with different best arms. This intuition is formalized by the lower bound provided in Lemma The characteristic time defined in the lower bound depends on two functions K and K mapping P(R) x R to R,, obtained by minimizing Kullback-Leible divergence (KL) over F.
Kit (F, u) == inf(KL(F, G)
G F, Ex~c[X] [X] > u},
K (F) ::a)==inf[ff) (=inf(KT(FF.)) G GEF, Ex~o(X] < u)
Lemma 1 (From [16, 3]). Any algorithm which is d-correct on JKK verifies, for any F E FK, EF(Ts] 2 T (F) log (1/(2.48))
where (F)-1 = supweex min :
infwez { Kut (Fir, u) + w;K u)).
We say that an algorithm is asymptotically optimal if its sample complexity matches that lower bound, that is if lim lim sup Er [7a]/ log (1/8) S (F).
related, weaker notion of (asymptotic) optimality is (asymptotic) 3-optimality [39]. An algorithm called asymptotically 8-optimal if it satisfies lim BF[rs]/ log (1/0) < (F),,, for the complexity term
T3
sup min inf (Fe,, + w; (F,, WEAR ii WEI
An asymptotically 8-optimal algorithm is asymptotically minimizing the sample complexity among algorithms which allocate 3 fraction of samples to the best arm and (F) min T (F). As was first shown by [38] when FF is an exponential family, an asymptotically 3-optimal algorithm with 8 1/2 also has an expected sample complexity which asymptotically optimal, up to a multiplicative factor 2. That is, (F) < (F).
We denote by wt (F)) and w (F) the allocations realizing the argmax in the definition of (FF and TV (F), respectively. We will show that for common choices of F these allocations are unique when there is unique best arm.
Distribution classes
The characteristic time T (F) depends on the class of distributions F, known to the algorithm in advance, to which F belongs to. For example, all arms could have Bernoulli distributions. We strive to provide an analysis which could easily be applied to many classes F, but specialize results to main cases:
1. distributions with bounded support, F = (F E P(R) (F) S [0, B for B 0,
A stronger definition of d-correctness has also been studied by requiring the algorithm stop almost surely.

---

2. single parameter exponential families (SPEF) of sub-exponential distributions.
Given a distribution p(0) with cumulant generating function y, defined on an interval Zg. the SPEF defined by p()) is the set of distributions P(A) with density with respect to p(0) given by (P 4P:o (a) eAx- For example, Gaussian distributions with known variance form SPEF, as do Bernoulli distributions with means in (0, 1). We consider SPEF of sub-exponential distributions to have a concentration property for the empirical mean estimator.
Related work The first Best Arm Identification (BAI) algorithms [14, 27, 15, 23] were proposed and analyzed for bounded rewards, but their sample complexity scales with a sum of inverse gaps between the means of arms instead of the quantity T (F) prescribed by the lower bound. Asymptoti- cally optimal BAI algorithm were first designed when the arms belong to the same single-paramett exponential family. In this context, two families of asymptotically optimal algorithms have emerged. baacking-based algorithms solve the optimization problem provided by the lower bound in every round, and track the corresponding allocation [16]. The gamification approach views the characteristic time as a min- max game between the learner and the nature, and apply a saddle-point algorithm to solve it sequentially at lower computational cost [13].
Some Bayesian algorithms arose as another computationally appealing alternative to Track-and- Stop. Russo notably proposed the Top Two Probability Sampling (TTPS) and Top Two Thompson Sampling (TTTS) algorithms [38], that may be seen as counterparts of the popular Thompson Sampling algorithm for regret minimization [41]. Other Bayesian flavored Top Two algorithms have been proposed, Top Two Expected Improvement (TTEI, [35]) and Top Two Transportation Cost (T3C, [39I. All these algorithms sample either leader with fixed probability 33 or a challenger with probability 1- - B. TTTS, TTEI and T3C were proved to be asymptotically B-optimal for Gaussian bandits and perform well in practice even against asymptotically optimal algorithms [35, 39]. This motivates our investigation of Top Two algorithms to tackle bounded distributions, which led us to propose new generic analysis of this kind of algorithms of independent interest. We prove the asymptotic 8-optimality of several Top Two instances for bounded bandit models, some of which depart from their original Bayesian motivation as they don't need a sampler. An asymptotically optimal algorithm for a non-parametric class of distribution has been proposed by [3] for heavy-tailed rewards. It relies on the computationally prohibitive Track-and-Stop approach, and an adaptation to bounded distributions is mentioned, yet without an explicit calibration of the stopping rule.
1.2 Contributions
We present the first -eeeddccnfieence analysis of Top Two algorithms for distribution classes other than Gaussian, including the non-pat non-parametric setting of bounded distributions. In Section 2, we introduce several variants of Top Two algorithms, including new ones which choose the empirical best arm as leader instead of relying on (Thompson) sampling and/or use some penalization in the previously proposed Transportation Cost challenger.
For the class of bounded distributions, we propose in Section 3 a calibration of the stopping rule and a concrete instantiation of the Top Two algorithms, based on Dirichlet sampler for the randomized variants. We prove in Theorem that those algorithms are asymptotically 3-optimal. This optimality can also be shown for deterministic instances in the case of sub-exponential single parameter exponential families (Appendix H). Our generic analysis, sketched in Section 4, provides insight on what properties the leader and challenger in a Top Two algorithm should have in order to reach asymptotic B-optimality. We show that the algorithm should ensure that all arms are explored sufficiently, and explain how to guarantee that the sampling proportions reach their optimal values once the sufficient exploration condition holds.
Finally, in Section 5 we report results from numerical experiments on challenging non-parametric task using real-world data from a crop- monggemngge problem for various members of the Top Two family of algorithms. Most of them perform significantly better than the baselines.
2 Generic Top Two algorithms
Let E FK such that [F) 1 and μ4, := :==m(F))) E I for all E [K]. As for most BAT algorithms, each arm is pulled once for the initialization. At time + 1. the o-algebra Fn :=
3

---

11,1,1,11,, ' II, Xn.J. Un+1), called history, encompasses all the information available to the agent and the internal randomization denoted by (U)) which is independent of everything else. For all -e-measurable sets A, we denote by 1P [| == P[A Fu] its probability. For an arm denote its number of pulls by Nu,; := EE( 1 (I+ = i), its empirical distribution by
- Fn. == No.t N., Ene(n) xx.., Il (1, = i) and its empirical mean by Mx,i == ml FR
Stopping and recommendation rules Our Top Two algorithms rely on the same stopping rule, which can be expressed using the (empirical) transportation cost between arm i and arm j. defined as
Wr, (i.j) inf [Nn, (F (F,,, + Ku 2
=EI
In particular, using the definition of K it can be noted that Wn (1, = 0 if pn,i S Pn.j- Given a threshold function c(n, 5), the stopping rule
= inf N min W (in: > (n,
j#in
and the recommendation rule is i, = arg max; Pn,s. Up to the choice of threshold, this stopping rule coincides with the GLR-based stopping rule proposed when F exponential family [16] and by [3] for heavy-tailed distributions with an upper bound on a non-centered moment. For a general class F the stopping rule can be calibrated to ensure d-correctness under any sampling rule if the threshold such that the following time-uniform concentration inequality holds for all E JK:
PF (3n, 3i * (F):
Nu, (Fn,i: M4) + Nn. (F) ( (Fn.) (e) > c(n, 8)) 88. (3)
Lemma 2 in the next section gives an explicit threshold for the class of bounded distribution. For SPEF, we can use generic stopping thresholds derived in [29].
Choice of the leader (two propositions):
1: Input: /
EB -B E arg max; 1n-1,
2: Choose a leader Bn E [K]
TS Sample 9 II,-1 then set B
3: U U(10 1])
arg [ 0:
4: if U < 5 then
5:
I, =, By
Choice of the challenger (three propositions):
TC C,CC E arg min wn-1 j)
6: else
7:
Choose a challenger Cn E [K] (B,)
TCI C E arg argminn4,. W. (Bn, 1) log Nn-1.5
8:
T, = Cn
9: end if
RS repeat / II until
10: Output: next arm to sample I
CRS E arg max 0 전 Bn
Figure 1: Generic 3-Top Two sampling rule
Figure 2: Choices of leader and challenger (uni- form tic-breaking).
Sampling rule The sampling rule of a Top Two algorithm is shown in Figure 1. The method chooses first arm B, called leader which is then sampled with probability B. If B,, is not sampled, then second arm C, called challenger is chosen and sampled. Our analysis isolates properties that those two choices should fulfill in order for the Top Two algorithm to be asymptotically 3-optimal.
The practical implementation of Top Two method then requires subroutines for B,, and C,, Two possibilities for the leader and three possibilities for the challenger are presented in Figure 2. Our analysis will apply to any combination of those and we will refer to the algorithms obtained by [[[eader)-
for example 3-EB-TCI or 3-TS-TC.
We have two flavors of leaders and challengers: deterministic and randomized. The deterministic choices (EB, for Empirical Best, leader, TC and TCI challengers) rely on the empirical Transportation Costs (TC) W, W,, (i.j) used in the stopping rule: the TC and TCI challengers are the arms which minimize the transportation cost from the leader (up to penalization for TCI, hence TC Improved). The randomized choices (TS leader and RS challenger) rely on a sampler, denoted by II,- II, generates i.i.d. vectors f (01..... .e.....,0)) E I which are interpreted as possible means for the arms, under a distribution which depends on observations gathered in the first n rounds. The TS leader is the best arm in the sampled vector, which is inspired by Thompson Sampling. The RS (for re-Sampling) challenger is obtained by performing repeated calls to the sampler until the best arm the sampled vector is not B,, then taking the best arm.

---

Randomized instances The samplers suggested by prior work all have a Bayesian flavor. For SPEF bandits, they use II, II,,1
II,, where II, the posterior distribution on the mean of arm i after n rounds (given some prior distribution). With this choice of sampler, B-TS-RS coincides with the TTTS algorithm [38], while 3-TS-TC coincides with the T3C algorithm [39]. TTTS and T3C were only proved to be asymptotically 3-optimal for Gaussian bandits with improper priors, whereas a by-product of the general analysis that we propose in this work permits to establish the necessary properties on the sampler for it to hold for more general distributions. Moreover, we extend these algorithms to bounded distributions by virtue of Dirichlet sampling and also analyze their sampler-free counterparts. As will be apparent in our analysis, the crucial property needed from the sampler in a Top Two algorithm using the RS challenger is that for all arms i, such that p4 > Pj+ Fo-11, (0) 0.) exp( Wn, (i.)))
Deterministic instances Under the RS challenger, the probability to obtain as a challenger arm j is proportional to the probability that Po- (0; Ps.,) ). Therefore, if IT, is good sampler satisfying the above property, the TC challenger can be seen as replacing the randomization in the RS challenger by computation of the mode of the distribution of CRS. This was the motivation behind T3C [39] as Gaussian transportation costs have a simple closed form expression while re-sampling becomes more and more costly when the posterior distributions are concentrated. While asymptotic analysis holds for deterministic algorithms, the empirical performance of fully deterministic algorithms might suffer from unlucky draws. In Section 5, we show that 3-EB-TC is indeed the least robust of all our instances. To cope for this pitfall, explicit or implicit exploration mechanisms can be added. Inspired by IMED [20]. the TCI challenger fosters exploration by penalizing over-sampled challengers. Randomization and forced exploration are two other examples of implicit and explicit exploration mechanisms.
3 Asymptotically B-optimal algorithms for bounded distributions
For bounded distribution, Lemma provides a calibration of the stopping rule. Its proof, given in Appendix 1, relies on martingale construction proposed by [5].
Lemma 2. The stopping rule (2) with threshold
c(n, 8) = log (1/6) + log (1 n/2) + log( - -))
(4)
is 8-correct the family of bounded distributions.
Transportation costs Both the stopping rule and the TC and TCI challengers of the sampling rule require the computation of W,, (f, defined in (1). For paggle-prramter exponential families, this can be done easily since K are KL divergences and the transportation cost has closed form expression [16, 38). However, for bounded distributions, computing X is more challenging and we rely on the dual formulation first obtained by [18] (see Theorem 3):
sup Σ 14 = i) (1 (1-1 Xt,i T
Kn,tKiitt (Fn.az))
xE(U.1] rE(m)
The minimization in can be computed using a zero-order optimization algorithm (e.g. Brent's method [10]). The same optimizer can be used compute the minimization in [0, B) featured in (.(..)) J). By nesting those optimizations of univariate functions on a bounded interval, the computa- tion of W,, (i, in the stopping rule dominates the computational cost of our Top Tow algorithms (except the RS challenger). Our experiments suggest that using (2) is twice as computationally expen- sive the LUCB-based stopping rule, which mild price to pay for the improvement in terms of empirical stopping time. Algorithms for paramaraettric distributions are bound to be computationally more expensive than their counterpart in SPEF, where sufficient statistic can summarize F,.-
Sampler The TS leader and RS challenger require a sampler. Our proposed sampler for bounded distributions in [0, B] has product form: 11, = 1l,, X ... 1l, where II, leverages Hn, := (Xi.i...., XN....) which is the history of samples from arm collected in the first n rounds. Let Fn,s denote the empirical edf of Hn,s augmented by the known bounds on the support, (0, B}. For
5

---

each arm i. In, outputs a random re-weighting of Fn,s. Coneretely, letting w = (wi...., +2) be drawn from a Dirichlet distribution Dir(1 (I. a call to the sampler I,, returns
Σ Wt, + BwN...+1
rE|N...
This sampler is inspired by that used the Non Parametric Thompson Sampling (NPTS) algorithm proposed by [36] for regret minimization in bounded bandits, with the notable difference that we have to add both 0 and in the support, while NPTS only adds the upper bound B. We will see that this is only necessary to ensure that the re-sampling procedure stops. Therefore, the TS leader could use sampler II,, based directly on Hn.i.
Theorem 1. Combining the stopping rule (2) with threshold (4) and a Top Two algorithm with 3 E (0, 1), instantiated with any pair of leader/challenger
in Figure 2, yields d-correct algo- rithm which asymptotically B-optimal for all F E FK with pe E B)K and Amin (F) :=
mingz jug 1- MF,] > 0.
Theorem gives the asymptotic 3-optimality for six algorithms (Figure 2). Choosing our favorite Top Two instances therefore requires further empirical and computational considerations. Computing the EB leader has a constant computational cost, while the TS leader computationally costly for large time n since it requires to sample from Dirichlet distribution with Nn.; + 2 parameters for each arm i. On the challenger side, the RS challenger computationally very expensive for large time n as the sampler becomes concentrated around the true mean vector. On the contrary, by leveraging computations done in the stopping rule (2), the TC and TCI challengers can be computed in constant time. Based on these computational considerations, the most appealing Top Two algorithm for bounded distribution appears to be the fully deterministic 3-EB-TC. But experiments performed in Section 5 reveal its lack of robustness, and for bounded distributions the best trade-off between robustness and computational complexity is 3-EB-TCI. More generally, 3-TS-TC can also be good choice provided that we have access to efficient sampler.
Distinct means Restricting to instances such that Amin (F) > 0 (which implies [i*( |-| 1) is an uncommon assumption in BAI. However, known Top Two algorithms [38, 35, 39] only have guarantees on those instances. Our generic analysis reveals that it solely used to prove sufficient exploration, characterized by (7) (Appendix C.3). Experiments highlights that all our Top Two algorithms except 3-EB-TC BCC perform well on instances where [i*( = 1 and Amin (F) = (Figure 4(b)). Proving theoretical guarantees in this situation is an interesting problem for future work (see Appendix D.3 for a discussion).
Sample complexity analysis
In this section, we sketch the proof of Theorem 1, which follows from the generic sample complexity analysis of Top Two algorithms presented in Appendix C. Our proof strategy the same as that first introduced by [35] for the analysis of TTEI and also used by [39] for TTTS and T3C. It consists in upper bounding the expectation of the convergence time, defined as
Nn.
T = inf [ 2
1 Vn 2 T, max <E[K]
w
S
(5)
n
for small enough. Indeed, we prove in Appendix C.5 that for any sampling rule
Er [x[ra]
3eo (F)= > 0, Ve E (F)), [P(T)]
+
lim limsup 8-+0 log (1/8) < 7 (F).
(6)
This implication only leverages the expression of the stopping rule and the threshold. It was previously established for Gaussian bandits by [35] and we extend this property to bounded distributions and SPEF of sub-exponential distributions. Up to technicalities (Kinf continuity and second order terms), this implication shown by using that if r3 2 n, then
log (1/6) =5-+ cnn, 8) 2 min W (In. RNITy (F) j7
To upper bound the expected convergence time, as prior work we first establish sufficient exploration:
NN1 s.t. [F[NN] < +00, Vn N No.
min Nn. 2 Vn/K.
(7)
K

---

By generalizing [39] which considered Gaussian, we identify two generic properties for the leader and the challenger under which (7) hold (Appendix C.3), provided that we assume A 0.
We proceed similarly to prove convergence by identifying in Appendix C desired properties for the leader and challenger, which are satisfied by all our leaders and challengers for bounded distributions (Appendix D). We sketch these conditions below. Let 1" be the unique element of i' (F).
The requirements on the leader and the challenger to ensure Ex GT < +oo become apparent when looking at generic properties of Top Two algorithms. Under any Top Two algorithm, the probability select arm at round n, inn
IP ((n-1) Ln i]. can be written
Vn,i = 3IP (n--)) (n)
3)
(m-11) Ba = (n = -]
(8)
j
We let Vn, = Ele(n) Ve,s. For the leader, we can prove using (8) that
V n.
M
VM E N,
Σ Pit- [Be i*)
This suggests that good leader should satisfy that there exists N₂ with Ep [N2] +o0 s.t.
Vn 2 N2, BB #1) gn).
where g(n) =+o0 onn a)) for some > O. For the challenger, noticing that
vM e N. Vi
nnd
M 1 1 Σ P(c-n)
Σ P i|B, i*],
n
suggests that good challenger should satisfy that there exists N3 with EF [Na] < +00 s.t.
Vnni 2 w + = [p = i =] h(n),
Vn 2 N3. Vi +i,
(10)
where ((1) +o0 an for some a > 0. Then, Cesaro's theorem further yields
V
NN s.t. Er[N]] +00, Vn 2 No. max
w
SE.
KE(K]
Using that (N,,, - //,))/ /0..s///r / are sub-Gaussianl random variables, we obtain EF < +00.
We now explain why (9) and (10) are satisfied for the leaders and challengers in Figure when F is the class of bounded distributions. This follows from concentration properties. Using the fact that /n F..; Fl is sub-Gaussian, which follows for the -roretzk--Kiefe-WWon [31], the continuity of the mean operator m on F and the sufficient exploration property (7), we establish that for all a > 0, there exists random variable N₂, with finite expectation such that
inequality
Vn 2 Na. max [| - Felloo S a and max An.t - usl a iE[K]
(11)
(E(K]
Deterministic instances Recall that B E arg max Pr.i. Choosing a in (11) smaller than half the gap between the best and second best arm (which is possible as |i*(F) = 1) yields that for all N.. BER 1² This proves (9) with (nn) O. Using continuity and convexity properties of Ki we then establish that there exists that for 2 Na and for all i + i",
and problem-dependent constant CF such
Vn
1 1 (Wan(t) min W., Wi(("",))) Cr. j
9 w +
n
This implies that ming W,, Wn, hence P. ICT = il B = 8*] = 0 for 2 No. Therefore, (10) holds with h(n) 0. A similar argument holds for Ct11
7

---

Randomized instances Let an+11. == PO-1I (i E arg jE[K] 0j) be the probability that arm à the best arm in a sampled model at round n. Since
nn [ # i*] S (K 1) an S (K 1)
(0; 2 0.-),
671
ifi
an upper bound on PI- 00 2 0z-] is sufficient to prove (9). We show in Lemma 64 that this can be obtained by leveraging upper bound on the Boundary Crossing Probability (BCP) of the Dirichlet sampler, Po-1ı, [0; 2 u| for a fixed threshold u E (0, B). An upper bound on the BCP can be obtained using the work of [36] and is given in Theorem 5 for the sake of completeness. Putting things together yields that, for all n1,
PoWIL [0: 2 5
inf [(Vn.. + (F u) + (Na,5 + 2) (F wi]] (uE[O.B]
where f(x) = (1+ +2) Using again continuity and concentration (11), we conclude that (9) holds with ((n = (K 1)f ((V++2) DF), where Dr > 0 is problem dependent constant.
For the challenger, we first observe that
P PIn|C 2+1 = Bu+1 = =1- 1- an+1i
Ont1,
Po- 00 2 0,-]
maX Pe-1I, (0 2 0.1
Further upper bounding this quantity to prove (10) requires lower bound on Po- 00 2 0,-] which can again be obtained using lower bound on the BCP. In Appendix G.3 we provide a tight lower bound on Fe-II, [0, 2 0r1 featuring the K functions. It permits to prove that (10) holds with -log(h(n))/rn too ČF o(1) where ÖF is problem dependent constant.
The above derivations all use the concentration property (11), which requires the sufficient exploration property (7). For our deterministic challengers, sufficient exploration is obtained by noticing that (,, can be upper and lower bounded by linear functions of the number of samples. Proving sufficient exploration is more challenging for a randomized challenger, and existing proofs were exploiting the symmetry of the Gaussian posterior. In our analysis we show that a coarse lower bound on the BCP is sufficient obtain (11), and prove such lower bound for the Dirichlet sampler:
[o=
[0, 2 u| 2 (1 (1-u/By B) and P 10; S u/ Z (u/B)"+1
These lower bounds ensure that any arm has some (small) probability of being the challenger thanks to re-sampling. Without adding {0, B} to Hn.i. those probabilities could be equal to zero.
Our analysis is easily amenable to tackle different families of distributions F. This requires continuity and convexity properties for the corresponding Kint functions, an appropriate concentration result and further upper and lower bounds the BCP of the sampler if one wish to analyze randomized algo- rithms. As an illustration, we show asymptotic 8-optimality of the 3-EB-TC, 3-EB-TCI algorithms for SPEF with sub-exponential distributions, see Appendix H.
5 Experiments
We assess the empirical performance of our Top Two algorithms on the DSSAT real-world data and on Bernoulli instances in the moderate regime (ō = 0.01). The stopping rule (2) is used with the threshold c(n, 6) defined in (4). As Top Two sampling rules, we present results for 3-EB-TC, 3-EB- TCI, 3-TS-TC and B-TS-TCI with B 0.5. Additional experiments are available in Appendix 1.2: on the RS challenger whose computational cost prevent it to be evaluated with (4) and on larger sets of arms (up to K 1000).
As benchmarks for the sampling rule, we use KL-LUCB with Bernoulli divergence [28] (whose theoretical guarantees extend to any distribution bounded in [0, I).. "fixed" sampling which is an oracle playing with proportions w² (FF) and uniform sampling. We also propose a heuristic adaptation of the DKM algorithm [13] (which is asymptotically optimal for SPEF) to tackle bounded distributions, which we denote by -DMM, and uses foreed exploration instead of optimism. Inspired by the regret minimization algorithm KCn [4], we propose its LUCB variant [27], named LUCB. The upper/lower confidence indices are obtained by inverting of A i.e.
Vi + in. Un+ = max {u E [Mn,i, B] Nn, (Fn,s. u) & c(n, 5)}
Intli = min { {u E (n.,, Na.s, Kin [ (Fn..,, u) & c(n, 8)}
8

---

LUCB-based algorithms [27] use their own stopping rule, namely they stop when Lu+1,i. 2 maxjyi, Un+1.j. For Bernoulli distributions, Kint-LUCB recovers KL-LUCB. While being asymp- totically optimal for heavy-tailed distributions [3] with adequate stopping threshold, the Track- and-Stop algorithm is computationally intractable for bounded distributions requires compute w" (Fx) at each time n (or on a geometric grid). We hence omit it from our experiments.
Crop-management problem We benchmark our algorithms on the DSSAT simulator' [22]. Each arm corresponds to choice of planting date and fixed soil conditions (details in Appendix 1). To illustrate the problem's 's difficulty we represent an empirical estimate (independent of the runs of our al algorithms) of the yield distributions in Figure 3(b). Since the gaps between means are small, the identification problem hard. Moreover, Kinf computations for non-parametric distributions are costlier than Bernoulli ones (see Appendix I),,, we only present the results for 100 runs.
Arm
Arm
0000000'
Amm
Amm
50x10
111
00x10
111
111
5.00x10*
T59TC
MIHELUCC
Read
Unifers
0.00
1.00
Figure 3: Empirical stopping time (a) on scaled DSSAT instances with their density and mean (b). Lower bound is T* (F) (1)) "stars" equal means.
In Figure 3, B------BBLLL 3-TS-TC and 3-TS-TCI slightly outperform -DK -KK and the fixed (oracle)
sampling rule. Moreover, Kinr-LUCB performs significantly worse than uniform sampling. Due the small number of runs, we don't 't observe large outliers for 3-EB-TC (see Appendix 1.2). KI.LLUB performs times worse than -LCBB hence omit it from Figure 3.
Bernoulli instances Next we assess the performance on 1000 random Bernuuli instances with K 10 such that μ4, = 0.6 and μ4; ((0.2, 0.5l) for all + where enforee that A Ain 2 0.01. We also study the instance (0.5, 0.45, 0.45), in which Amin 0, and perform 1000 runs.
5.0x10
1.00x10'
4.0x10
x10
3.0x10
5.00x10
2.0x10'
2.50x10'
1.0x10
69 TC
68
15
Knd bcM
Ri UBC
Usitm
66/C
68
15
1593
GIEORM No. LUC
Fand
Figure 4: Empirical stopping time on Bernoulli (a) random instances with K and (b) instance (0.5, 0.45, 0.45).
In Figure 4(a), we see that 3-EB-TCI, 3-TS-TC TCC and 3-TS-TCI outperform other algorithms. While this gain is slim compared to KKM, the empirical stopping time is twice (resp. three times) as large for KL-LUCB (resp. uniform sampling). Even when Amin 0, Figure 4(b) hints that their empirical performance might be preserved. Figure confirms the lack of robustness of 3-EB-TC.
PDSSAT is Open-Source project maintained by the DSSAT Foundation, https://dssat.net.

---

which is prone to large outliers. For the symmetric instance in Figure 4(b), uniform sampling outperforms KL-LUCB and perform on par with the "fixed" sampling.
6 Perspectives
We provided general analysis of Top Two algorithms, including new variants using the EB leader and TCI challenger, and proved their asymptotic 3-optimality on the non non- parametric class of bounded distributions. On experiments on distributions coming from a real world application, several Top Two variants (in particular 3-TS-TC and 3-EB-TCI) proved more effective than all baselines. Furthermore, 3-EB-TCI is computationally not costlier than computing the stopping rule.
As in previous work on Top Two methods result only characterizes the asymptotic performance of the algorithms, and obtaining bounds on the sample complexity for any that would reflect their good empirical performance is most pressing open question. Our work also hints what is needed to obtain non-asymptotic guarantees: the only variant for which the empirical behavior does not reflect the asymptotic bound is 3-EB-TC, which is also the most greedy variant. Algorithms using a sampler naturally explore, and the penalized version 3-EB-TCI successfully corrects the shortcomings of 3-EB-TC by penalizing over-sampling Quantifying the amount of exploration required by Top Two algorithms should also allow the removal of the hypothesis Amin > O from Theorem 1.
Finally, Top Two algorithms are promising algorithms tackle the setting of fixed budget identifica- tion, in which the algorithms have to stop at a given time and should then make as few mistakes as possible. As their sampling rule is anytime (i.e. independent of 8), Top Two algorithms might also have theoretical guarantees for BAI in the fixed-budget setting or even the anytime one, in which guarantees on the error probability should be given at all time.
Acknowledgments and Disclosure of Funding
Experiments presented this paper were carried out using the Grid'500N testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www. www.ridd0000.ii... This work has been partially supported by the THIA ANR program "AI PhD @ Lille". : The authors acknowledge the funding of the French Na- tional Research Agency under the project BOLD (ANR-19 WWN--19-CE23-0026-00 and the Dutch Research Council (NWO) Rubicon grant number 019.202EN.Cm .004.
References
[1] S. Agrawal and N. Goyal. Analysis of Thompson Sampling for the multi-armed bandit problem. Proceedings of the 25th Conference On Learning Theory, 2012.
[2] Agrawal and N. Goyal. Further Optimal Regret Bounds for Thompson Sampling. In Proceedings of the 16th Conference on Artificial Intelligence and Statistics, 2013.
[3] S. Agrawal, S. Juneja, and P. W. Glynn. Optimal 6-correct best-arm selection for heavy-tailed distributions. In Algorithmic Learning Theory (ALT), 2020.
[4] S. Agrawal, S. K. Juneja, and W. M. Koolen. Regret minimization in heavy-tailed bandits. In Conference on Learning Theory, pages 26-62. PMLR, 2021.
[5] S. Agrawal, W. M. Koolen, and Juneja. Optimal best-arm identification methods for tail-risk measures. Advances in Neural Information Processing Systems, 34, 2021.
[6] J.-Y. Audibert, S. Bubeck, and R. Munos. Best Arm Identification Multi- armed Bandits, In Proceedings of the 23rd Conference on Learning Theory, 2010.
[7] D. Baudry, R. Gautron, F. Kaufmann, and O. Maillard. Optimal thompson sampling strategies for support-aware evar bandits. Proceedings of the 38th International Conference on Machine Learning, 2021.
10

---

[8] D. Baudry, P. Saux, and O. Maillard. From optimality to robustness: Dirichlet sampling strate- gies in stochastic bandits. In Advances in Neural Information Processing Systems (NeurIPS). 2021.
[9] C. Berge. Topological Spaces:
including treatment of multi-valled functions, finttionn, vector spaces, and convexity. Courier Corporation, 1997.
[10] R. P. Brent. Algorithms for minimization without derivatives. Courier Corporation, 2013.
[11] O. Cappé, A. Garivier, O.-A. Maillard, R. Munos, and G. Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 41(3)1511615511, 2013.
[12] R. Degenne and W. M. Koolen. Pure exploration with multiple correct answers. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[13] R. Degenne, W. M. Koolen, and P. Ménard. Non-asymptotic pure exploration by solving games. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
[14] E. Even- S. Mannor, and Y. Mansour. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Leamingg Problems. Journal of Machine Learning Research, 7:1079-1105, 2006.
[15] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence. In Advances in Neural Information Processing Systems, 2012.
[16] A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In Proceedings of the 29th Conference On Learning Theory, 2016.
[17] A. Garivier, H. Hadiji, P. Menard, and G. Stoltz. Kl-ucb-switch: optimal regret bounds for stochastic bandits from both a distribution-depeedentt and a distribution free viewpoints. arXiv preprint arXiv:1805.00 818805550711 2018.
[18] Honda and A. Takemura. An Asymptotically Optimal Bandit Algorithm for Bounded Support Models. In Proceedings of the 23rd Conference on Learning Theory, 2010.
[19] J. Honda and A. Takemura. An asymptotically optimal policy for finite support models in the multiarmed bandit problem. Machine Learning, 85(3):361-391, 2011.
[20] J. Honda and A. Takemura, Non-asymptotic analysis of a new bandit algorithm for semi- bounded rewards. Journal of Machine Learning Research, 16:3721-3756. 2015.
[21] L. Hong, W. Fan, and Luo. Review on ranking and selection: new perspective. Frontiers of Engineering Management, 8:321-343, 2021.
[22] G. Hoogenboom, C. Porter, K. Boote, V. Shelia, Wilkens, U. Singh, J. White, S. Asseng, J. Lizaso. L. Moreno, et al. The dssat crop modeling ecosystem. Advances in crop modelling for a sustainable agriculture, pages 173-216. 2019.
[23] K. Jamieson, M. Malloy, R. Nowak, and Bubeck. liI'UCB: an Optimal Exploration Algorithm for Multi-Armed Bandits. In Proceedings of the 27th Conference Learning Theory, 2014.
[24] K. G. Jamieson and R. D. Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In CISS, pages 1-6. IEEE, 2014.
[25] M. Jourdan and R. Degenne. Choosing answers in s-best-answer identification for linear bandits. In Proceedings of the 39th International Conference on Machine Learning, volume 162, 2022.
[26] M. Jourdan, M. Mutný, J. Kirschner, and A. Krause. Efficient pure exploration for combinatorial bandits with semi-bandit feedback. In Algorithmic Learning Theory (ALT), 2021.
[27] S. Kalyanakrishnan, A. Tewari, P. Auer, and Stone. PAC subset selection in stochastic multi-armed bandits. In International Conference on Machine Learning (ICML), 2012.

---

[28] E. Kaufmann and S. Kalyanakrishnan. Information complexity in bandit subset selection. In Proceeding of the 26th Conference On Learning Theory. 2013.
[29] E. Kaufmann and M. Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22(246):1-44, 2021.
[30] E. Kaufmann, O. Cappé, and A. Garivier. On the Complexity of A/B Testing. In Proceedings of the 27th Conference On Learning Theory, 2014.
[31] P. Massart. The tight constant in the dworerzky--ieefe-wwoofooo inequality. Annals of Probabil- ity, 18, 1990.
[32] Ménard and A. Garivier. minimax and asymptotically optimal algorithm for stochastic bandits. In International Conference on Algorithmic Learning Theory, pages 223-237. PMLR, 2017.
[33] A. Mukherjee and A. Tajer. Sprt-based efficient best arm identification in stochastic bandits. 2022.
[34] E. Posner. Random coding strategies for minimum entropy. IEEE Transactions Information Theory, 21(4):388-33) -311, 1975.
[35] C. Qin, D. Klabjan, and D. Russo. Improving the expected improvement algorithm. In Advances in Neural Information Processing Systems 30 (NIPS), 2017.
[36] C. Riou and Honda. Bandit algorithms based on thompson sampling for bounded reward distributions. In Algorithmic Learning Theory (ALT), 2020.
[37] Y. Russac, C. Katsimerou, D. Bohle, O. Cappé, A. Garivier, and W. M. Koolen. A/b/n testing with control in the presence of subpopulations. In Advances Neural Information Processing Systems (NeurIPS), 2021.
[38] D. Russo. Simple Bayesian algorithms for best arm identification. In Proceedings of the 29th Conference on Learning Theory (COLT), 2016.
[39] X. Shang, R. de Heide, E. Kaufmann, P. Ménard, and M. Valko. Fixed-confidence guarantees for bayesian best-arm identification. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[40] R. K. Sundaram et al. A first course in optimization theory. Cambridge university press, 1996.
[41] W. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25:285-294 1933.
[42] R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018
[43] Z. Wang, S. Yang, and W. You. Optimality conditions and algorithms for top-k arm identification. arXiv preprint arXiv:2205. 12086, 2022.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In the supplementary material.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or a URL)? [Yes] See Appendix I.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix I.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] We are using an internal cluster. As giving more details would break anonymity, we will include them in the camera-ready version.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix I.
(b) Did you mention the license of the assets? [Yes] See Appendix I.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
No new assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] Open source data agricultural production.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Idem.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "uJ5tS2CgQ3h", "reviewer": "Reviewer_166Y", "summary": "The authors improve the top-two sampling algorithm, commonly used as bayesian BAI strategies. The authors present asymptotic optimality of the BAI strategy for nonparametric bandits with bounded support, which previous work has not shown.", "questions": "None. ", "limitations": "Although the contribution is significant, I feel that the results presented are not so surprising, given the context of existing research.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This study generalizes Top Two strategies, a well-known Bayesian BAI strategies. This contribution is very important. In recent years, the Top Two strategy has attracted much attention due to its ease of use, and the authors' results reinforce its advantages. In particular, the results for bounded nonparametric distributions are interesting and also contribute to a whole bandit study. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "qZrzk-giwzB", "reviewer": "Reviewer_KZTG", "summary": "This paper analyzes several top-two algorithms for more general distributions, including those from single parameter exponential families and non-parametric bounded distributions.", "questions": "1. What does I in TCI refer to? What is the difference between challengers TCI and TC(I)?\n\n2. It seems that algorithms using RS as the challenger is not included in the experiments. Is the reason that running RS could be time-consuming? I guess due to the randomness, algorithms using RS might perform even better than others included in the experiments. For Gaussian, we have good approximations of RS. Is it possible to come up with approximations of RS for general distributions studied in the paper?\n", "limitations": "The conclusion section describes some open problems and future directions. I think the contributions of the paper can be improved if the analysis of some top-two algorithms could be generalized to cover the case Delta_min = 0. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In terms of theoretical contributions, the analysis in this paper extends the previous analysis for Gaussian distributions. Although the paper introduces several algorithms, I am not sure they are novel. In my opinion, it is well-known that other leaders, e.g., the empirical best arm also work for top-two algorithms as well as the theoretical analysis. Indeed, when the leader is the empirical best arm, the analysis becomes easier than that for the leader chosen by Thompson sampling (TS). In terms of empirical results, it is also known that the randomness in TS or resampling helps exploration, while top-two algorithms directly using the posterior quantities might be less efficient since they can be inaccurate due to the random and unlucky observations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bM750cfG1AG", "reviewer": "Reviewer_yFSX", "summary": "This paper provides an in-depth analysis of “Top-Two” style algorithms for the pure-exploration multi-armed bandit problem under bounded distributions. The authors consider a variety of methods to choose the leader and challenger which recover many of the well known algorithms already in the literature - such as TTTS and T3C. They provide a general theory for analyzing the sample complexity of top-two algorithms and also provide some experiments.\n", "questions": "I was a bit surprised that KL-LUCB was worse than uniform in Figure 4b. Can you shine some light on this? \n", "limitations": "None.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nFor bounded distributions, this paper provides a general purpose methodology to derive asymptotically-optimal algorithms which do not require computationally expensive track and stop style forced exploration. From that perspective, I think this work is useful for practitioners - indeed most practical use cases are bounded distributions, and sub-Gaussian approximations can be woefully sub-optimal.\n\nI thought the paper was well written and thorough.\n\nWeaknesses:\nSince this paper is providing such a thorough investigation of Top-Two style algorithms, I would have liked to see some more experiments with a larger set of arms. For example on some of the instances that have been benchmarked in previous literature, i.e. Jamieson, Kevin, and Robert Nowak. \"Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting.\" 2014 48th Annual Conference on Information Sciences and Systems (CISS). IEEE, 2014.\n\nMy second comment is about the lack of finite-time non-asymptotic guarantees. I think at this point, there is plenty of literature in the asymptotic setting. The authors address this limitation so I do not really hold this against them.\n\nFinally - just to really point out novelty, I think the authors can better indicate what aspects of their analysis are novel in comparison to past works.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A--hl_nPa6", "reviewer": "Reviewer_dAwE", "summary": "This paper investigates Top Two algorithms, which are a series of algorithms aiming to find the best arm in the multi-armed bandit problems with fixed confidence. The main contribution of this work is two-fold: 1) It demonstrates the first Top Two method with theoretical guarantee ($\\beta$-optimality) when the input arms have bounded rewards; 2) It also offers a generic analysis that defines desirable characteristics a Top Two algorithm need to satisfy in order to have theoretical guarantee.", "questions": "With the exception of the following errors and concerns, I believe this work to be solid and one that could expand the possibilities for Top Two algorithms.\n\nLine 32: \"... which the arms belong.\": belong -> belong to\n\nLine 44: The definition of $\\delta$-correctness seems to me that it misses the scenario when an algorithm could run in infinite time.\n\nLine 47: $\\mathcal{P}(\\mathbb{R})$ is not defined in the previous sections\n\nLine 50: $\\Delta_k$ is not defined in the previous sections, which makes me hard to understand the definition of $T^{*}(\\textbf{F})$. Besides, it would be preferable if the author(s) could briefly explain Lemma 1 afterward because it is essential to comprehending the work.\n\nLine 56: Should it be $T^*(\\mathbf{F}) = \\min_{\\beta \\in (0,1)} T_{\\beta}^*(\\mathbf{F})$ ?\n\nLine 64: \"... to which $\\mathbf{F}$ belongs.\": belongs -> belongs to", "limitations": "N/A since there isn't any negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n* This is the first Top Two algorithm in bandit fields which has theoretical guarantee on the problems with input arms having bounded rewards, which is novel.\n* The analysis approach can be extended to more general reward distributions as long as the algorithm has the properties proposed in the paper.\n* Experiment results using real-world dataset are presented to demonstrate the superior empirical performance of the proposed algorithms against the baselines.\n\nWeaknesses\n\n* The proof can only be applied when the input instance has only one best arm. It is an interesting direction to see if this assumption could be removed.\n* I think the presentation could be a little bit better, for example, some definitions or lemmas are lacking explanations before they are introduced.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept