Fast Pure Exploration via Frank-Wolfe
Authors: Po-An Wang
Ruo-Chun Tzeng
Alexandre Proutiere
Venue: NeurIPS 2021 Poster (2021)
Keywords: pure exploration
Frank-Wolfe
structured bandits

Abstract: We study the problem of active pure exploration with fixed confidence in generic stochastic bandit environments. The goal of the learner is to answer a query about the environment with a given level of certainty while minimizing her sampling budget. For this problem, instance-specific lower bounds on the expected sample complexity reveal the optimal proportions of arm draws an Oracle algorithm would apply. These proportions solve an optimization problem whose tractability strongly depends on the structural properties of the environment, but may be instrumental in the design of efficient learning algorithms. We devise Frank-Wolfe-based Sampling (FWS), a simple algorithm whose sample complexity matches the lower bounds for a wide class of pure exploration problems. The algorithm is computationally efficient as, to learn and track the optimal proportion of arm draws, it relies on a single iteration of Frank-Wolfe algorithm applied to the lower-bound optimization problem. We apply FWS to various pure exploration tasks, including best arm identification in unstructured, thresholded, linear, and Lipschitz bandits. Despite its simplicity, FWS is competitive compared to state-of-art algorithms.

Fast Pure Exploration via Frank-Wolfe
Po-An Wang
Ruo-Chun Tzeng
KTH Royal Institute Technology Stockholm, Sweden wang90kth.
KTH Royal Institute of Technology Stockholm, Sweden
retzeng@kth.c
Alexandre Proutiere EECS and Digital Futures KTH, Stockholm, Sweden alepro@kth.se
Abstract
We study the problem of active pure exploration with fixed confidence in generic stochastic bandit environments. The goal of the learner answer a query about the environment with a given level of certainty while minimizing her sampling budget. For this problem, instance-specific lower bounds on the expected sample complexity reveal the optimal proportions of arm draws Oracle algorithm would apply. These proportions solve an optimization problem whose tractability strongly depends the structural properties of the enviromment, but may be instrumental in the design of efficient learning algorithms. We devise Frank- Wolfe- Sampling (FWS), simple algorithm whose sample complexity matches the lower bounds for a wide class of pure exploration problems. The algorithm is computationally efficient as, to learn and track the optimal proportion of arm draws, it relies single iteration of Frank- Wolfe algorithm applied to the lower-bound optimization problem. We apply FWS to various pure exploration tasks, including best arm identification in unstructured, thresholded, linear, and Lipschitz bandits. Despite its simplicity, FWS is competitive compared state-of-art algorithms.
Introduction
Pure exploration in stochastic bandits 24 refers to the task of answering given question about the reward distributions of the different arms, using as few arm pulls (or samples) as possible. The task may correspond to identifying the best [13], the top-m arms [37], all e-good arms (27), set of arms whose expected rewards exceed a given threshold [26). etc. To reduce the sample complexity of such task, the learner needs leverage much as possible the information available about reward distributions, which typically comes as known structural properties of the set of their expected rewards. Exploiting particular structures (c.g., unimodal, Lipschitz, convex, linear) has been thoroughly studied in the regret minimization setting (see (6). and references therein), but less in the pure exploration framework, where most efforts have focused on linear structures
39
10 18
In this paper, we investigate a generic learning problem proposed in g and covering the aforemen- tioned pure exploration tasks with without structure. Consider K arms whose reward distribu- tions (M),-... PK) come from a one-dimensional exponential family and are of unknown means a (M), ... (K)). The parameter μa known belong A C R the of possible instances. For each fa E A, we assume that there is a unique true answer i (f4) that belongs to the finite set I of possible answer (e.g., for the best arm identification task, (H) arg max; mk). We consider pure
'Scenaiios with several correct answers require a more involved analysis, see
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

exploration tasks in the fixed confidence setting where the learner wishes, for any possible μ E A, to discover i" (ft) with a certain level of confidence is defined by (i) an adaptive sampling rule dictating the sequence of arm pulls, (ii) stopping rule defining т. the round where, based on the data gathered so far, the learner decides to stop pulling arms, and (iii) decision rule specifying her answer. The goal is to devise a 5-PAC (it outputs the right answer with probability at least 1 for any μ E A) strategy minimizing the expected sample complexity [,(r].
6. for some E (0, 1). The learner's strategy
Using the same arguments as those used in 13 for classical MAB problems, we may derive a lower bound of the expected sample complexity satisfied by any 5-PAC strategy. This lower bound, whose proof can be found in Appendix [B for completeness, given by T* (H))k((, 1 - 6), where the characteristic time T" (()) is defined through the following optimization problem:
T (1)
sup inf WEY AEAB(()))
E k=1
wadkuss >x))
where E is the (K - (K-1)-dimeeett dimensionl simplex, Alt(μ) is the set of confusing parameters A such that i" (1)) # i (A), kl(a, b) is the KL divergence between two Bernoulli distributions of means a and and d(j4, )x)) denotes the KI. divergence of arm-k reward distributions under parameters μ and A solution w' (fx) of (1) can be interpreted as an optimal allocation, in the sense that pulling each arm i a proportion of round equal to w (14) (in expectation) constitutes an optimal sampling rule.
Most existing algorithms achieving an asymptotically (when å goes to 0) minimal sample complexity leverage a Track-and-Stop (TaS) framework [13]. In each round t, they plug ji(() the estimated expected arm rewards in the lower bound optimization problem ( and track the allocation w" (f)()). As already noticed in [28]. the main drawback of the Track-and- and-Stop framework is that it requires a recurrent access to an Oracle able to solve (I) (actually existing analyses usually assume that the
Oracle outputs the exact solution for any μ.) ( is a concave program but can become difficult to solve depending the underlying structure A. Indeed, for complex structures, identifying the most confusing parameters leading to the objective function inf ) Σk wyd(He, A₂) can be hard.
Contributions. 1) Instead of solving ① in each round as in the TaS framework, we propose an online iterative method to approach the optimal allocation of arm pulls. Specifically, we devise Frank-War Woln-Woofee-bsee Sampling (FWS), a computationally efficient al algorithm that just relies, in each round, on single iteration Frank-Wolfe (FW) algorithm applied to (1) instantiated at (t()..
2) For a wide class of pure exploration problems with or without structure, we derive an upper bound of the expected sample complexity of FWS for any certainty level 8, and show that this bound matches the lower bound 7 (H))k(6, 1 1- d) asymptotically as goes to O.
3) We illustrate the performance of FWS on various pure exploration problems, including best arm identification in unstructured, linear, and Lipschitz bandits. In all tested scenarios, and despite its simplicity, FWS matches the performance of the best existing algorithms.
The use of the FW algorithm has been suggested in 13 in the case of best arm identification problem in unstructured bandits. In this case, FW iterations take very simple and intuitive form (see Example 1 introduced in } The corresponding sampling rule is referred to as Best Challenger in 13,, and leads to algorithms with remarkably low sample complexity empirically- sometimes lower than that of TaS algorithms solving ① in each round. So far however, as discussed in (28), the analysis of FW-type sampling rules, and even their convergence, have eluded researchers. Towards the design of FWS algorithm, we devise a simple variant of the FW algorithm that yields a sampling rule whose sample complexity can be analyzed. We confirm the asymptotic optimality of as well as its empirical superiority, not only for the case of best arm identification in unstructured bandits as predicted by [13, but also for wide class of pure exploration problems. We believe that analysis also brings interesting solutions to the three important obstacles we needed to tackle to devise and analyze a FW-type sampling rule: (i) the objective function in (1) is not smooth; (ii) its curvature becomes infinite in general close to the boundary of Σ; and (iii) the estimate (t()) is evolving and might be far from Js.
2 Related Work
Best Arm Identification (BAT) has recently received lot of attention, either in unstructured bandit problems, see [3 33), or in problems with various kinds of structure, e.g., linear [35] 20 39 36

---

T0 18
combinatorial [2] 19, 32 spectral 122] monotone [4]. cascading [41] For BAI in unstructured bandits with fixed confidence, [3] developed the celebrated Track-and-Stoy framework leading to algorithms able to asymptotically converge towards the optimal allocation of arm draws, and in turn, to achieve the lowest sample complexity possible in the high confidence regime (as goes to O). It is possible to apply the TaS framework to specific structures, as this was proposed in [8] for linear bandits. However, for more involved structures, this might become computationally too difficult. Indeed TaS requires the learner to repeatedly solve the optimization problem (T).
The authors of 8 propose and exploit an interpretation of the lower bound optimization problem (I) as the solution of 2-players game the w-player playing the 'sup' and the X-player playing the "inf". The algorithm presented in [8] combines two zero-regret algorithms applied sequentially by the two players, and converge to an optimal allocation. Interestingly, the algorithm uses the optimism in face of uncertainty principle to remove the need of forced exploration (the w-player fed with upper-confidence bounds on her rewards). As shown later, the algorithm does not perform as well as FWS. The applicability of the framework used in remains unclear to us: in 9 and 19]. the authors claim that the framework cannot be applied to linear and combinatorial bandits, respectively.
In the author proposes solution close to ours. His algorithm, LMA (Lazy Miror Ascent), just runs in each round one iteration of a sub-gradient ascent algorithm applied to ( Fortunately, the projection step usually involved in such algorithm is simple. Numerically, as illustrated later in the paper, we found that LMA may not be as efficient as TaS or FWS. We could try to explain this by remarking that LMA has similarities with the Exponential Weights algorithm (see Appendix F in (28)) an algorithm designed for adversarial online optimization problem, and may be too conservative in stochastic setting.
As already mentioned in the introduction, FW-based algorithms for BAI in unstructured bandits have been mentioned first in [13 for their simplicity and good performance. Applying FW as if the objective function was smooth may fail at converging (28) experimentally. We believe that we manage to make, in our algorithm, the minimal modification of the FW-based algorithm so that convergence and asymptotic optimality are guaranteed. Finally note that 2 uses FW in a regret minimization problem but with a smooth objective function.
We conclude this section by mentioning existing works on the FW algorithm when applied to optimizing non-smooth functions. The proposed solutions consist by either smoothing objective function or enlarging the set of differential (this is the second approach we chose).
[1] 15 apply
FW on the randomly smoothed surrogate instead of the original non-smooth objective. However, computing the gradient at each iteration requires to query many time on the objective function, which may not be practical. [ [29] use a proximal operator replace the objective function, but as pointed out in A. the smoothing parameters of the proximal operator are not trivial to tune. Our solution close to those developed in 330 4 There, inspired by the approximate subdifferential [38], the authors propose to collect the set of the gradients in the neighborhood at each round. They show that these collection is continuous even when the objective functions is non-smooth, which allows for the use of FW. The way we deal with the non-smoothness issue is similar but simplified by the fact that the specific form of our objective function.
3 Preliminaries
We consider the pure exploration task described in the introduction. This section presents the additional assumptions made towards the design and analysis of our algorithm. These assumptions are here illustrated for the classical Best Arm Identification (BAI) task in unstructured bandits (see Example I); they will be verified for all other examples of pure exploration problems presented in Section [5] This section also provides useful properties of the lower bound optimization problem and finally describes our choice of stopping and decision rules.
3.1 Assumptions and properties of the lower bound optimization problem
The answer map it A + I allows us to decompose A into a union of non-overlapping sets: = S where S; = {14 E A (1)) = i} for all E I. The answer map is known (i.e., knowing μ is enough to output the right answer), and hence without loss of generality, can assume
3

---

that S; * 0 for all E I. Using this notation, the set of confusing parameters can be written as Alt(p) (n;
Assumption 1. For each I, S, is open set and the complementary of St is finite union of convex sets. Namely, there exists a finite collection Js of convex sets Cj s.t. A \ S = UsEAC
Example 1. The BAI task in unstructured bandits with Bernoulli rewards. For this task, we have A = (0, 1)K S, = (n E A p4 > pk: vk + i). We have: A \ S Ujea, where J, = I Z {i} is the set of arms different than i and C3 [ E :g > pi) is the convex set of parameters for which arm j is better than arm i.
{1,...; }), and for all arm i, the set of parameters for which arm i is the best arm
Now under Assumption ! T (H) supwEy F where Fu(w) minjeJr-( fy(w, ()) and for all j (m)
we can decompose the lower bound optimization problem as follows:
K
[(w,
inf XEC
wad(fus
R=1
Note that 22 is convex program (by convexity of the KL divergence), and that fy is concave function in w (as the minimum of concave functions). As a consequence, the objective function F2 is also concave, but not smooth. The following proposition summarizes insightful properties of the functions fz. j E (r) It is consequence of the envelope theorem and proved in Appendix K.2
Proposition 1. Leti E I. Tv. Define for all (w, p)) E S..
X (1) arg min XEd(CC))
wkd(pk. Ak),
(3)
where cl(C)) is the closure of Cj.- Then under Assumption X p)) unique for all (w, p.) & x S where E is the interior of E. In addition, f3 is continuously differentiable on E x S and V(w. p)) E x S
K
Vuls(,, Σ d(ss >3 1t
where ex denotes the K K-dimensional vector whose k-th coordinate is and whose other coordinates O.
A key insight from the above result is that the objective function Fj is the minimum of a finite number of continuously differentiable functions. This observation will make the use of a slightly modifed FW algorithm possible (remember that the FW algorithm is known to converge for smooth functions only). We use an additional assumption on the gradient and curvature of fy- controlled curvature is an essential ingredient when analyzing the convergence of FW-based algorithms, see e.g. [77] Define En (w E Σ ming W/ 2 7) for any 7 E (0. 1/K). Following [17,, we define (K)), the curvature constant of the concave differentiable function xb K. + R with respect to the compact set K, as
1 a² [V(x) (1)) + (2 x, Vo(=))
(xC
sup æ.sEK ac(0.1) y=
(5)
Refer to 17,, for the intuition behind this defintion and examples.
Assumption 2. For all μ A,
(i) there exists L > 0 such that Vj E Je E E, [VW < L; (ii) there exists D > 0 such that Vy (0, 1/K) and Vj e Je(ey (2.)))()))) < D
There a simple way verify whether pure exploration problem satisfies Assumption by looking the second derivative of the function y ++ d(x,, y) at the points (ux, (Ay(w, for all k. Refer to Appendix C for details.

---

Example I (cont'd d). For unstructured bandits with Bernoulli rewards, we can easily compute f, and its gradient 28 for all j + (p) and all w E E. define my(w, pu) (a tw we (u) twy
Then
,5(w, p) us if # 5 and س 14); - mysw, 14) otherwise. As a consequence:
(w, War (m) my(w. 14) + wydlly saddlyyyyluu my(w, m)), Vulj(w, (o) d (w): my(w, 11) )()((( (ي) + d(pi mj(w; p.)
(6)
For this example, we can verify that Assumption hoolds, either directly or using the tool described in Appendix C
3.2 Stopping and decision rules
Next we present the two last components of the FWS algorithm, namely the stopping and decision rules. These components are standard and borrowed from the existing literature. We need few notations. For any t 2 1, let A, denote the selected in round t. Define (&(()= = En= 1 (A, k} the number of times arm i has been selected up to round t, and by wi (t) = N (t)ft the corresponding empirical proportion of draw. When (t) > the empirical average reward of arm k up to round
denoted by jx,(t Σx= (x(ss = k)) (t)), where (x(s) is the random reward received
from pulling arm l in round
Let us denote by r, the stopping time defining when the algorithm stops exploring and has to output decision. Our decision rule is obviously to output the best empirical answer: 2, = =i" (f((T))
For the stopping rule, as in other existing algorithms, we leverage a Generalized Likelihood Ratio Test (GLRT). Our test boils down to comparing ace (I) to a threshold (t,, 8) (recall that F3 is the objective function of the lower bound optimization problem):
it 2 1: tF (w)(())()) 2 8)).
(7)
Many thresholds ((t, 6) have been proposed in the literature (21 13 18 28 For FWS and its analysis, we just need that the threshold statisfies the two following properties:
Vt 2 1, (tFp 2 ((t, = (P [ (f((t) + [m)]] S 8).
(8)
(c2(A)t
Fe c2() 0 AI ((A),,, 3(1,8) S log
The first of the above properties will naturally imply that FWS returns the true answer with probability at least 1 1- when stopping, whereas the second will be instrumental in the sample complexity analysis may depend on the set of possible instances, and on the reward distributions). In (21), the authors manage to provide, for any generic pure exploration task, single threshold satisfying (8)).))) Unless otherwise mentioned, we will use the stopping rule implementing this threshold.
(there, e1
4 The FWS Algorithm and its Sample Complexity
In the FWS algorithm, we use the FW algorithm to learn an optimal allocation w (H)). In each round, an iteration of FW updates the allocation that the FWS algorithm aims at approaching using some tracking procedure. We describe this learning and tracking procedure below.
4.1 Adapting Frank- Wolfe to the non-smooth function Fy
The FW algorithm 12 solves smooth convex programs by lincarizing, in each iteration, the objective function and moving towards a minimizer of this linear function. Compared to the projected gradient and proximal methods, FW is computationally more efficient (e.g. it avoids the projection step), and is particularly well-suited when optimizing over polyhedra [3] (which is our case here). For contemporary treatment of FW, refer to [17]. FW was suggested in [13] for BAI in unstructured bandits update the allocation to be tracked. For this BAI problem, an iteration of the FW algorithm takes an intuitive form (see also Appendix A2 in (8)):
Example I (cont' d). For BAI in unstructured bandits, the optimal allocation w (14) ) is the max- imizer of the function w + Fw(() = min, [,(,, p).. F₁. smooth at points when the mini- mum is realized at single arm j arg min, (w, 11), and there, in view of (6). its gradient is
5

---

Now in an iteration of the FW algorithm, one would follow the direction given by arg max w (FF(()) This direction is ej. if d(py my- (w) > d(j4e(1) my (7a--(w. (wwH)). and (r(()) otherwise. This is precisely what the FW-type sampling rule suggested in [3 is doing: in round (t + 1), the best challenger is defined as j" = arg ming ((), iu((), and the arm selected corresponds to the direction given by arg max w VF FCo (t),,, i.e., it is either the best challenger j* or the best empirical arm i" (j()t).
VFF(W) ((p my (w. ())) + (is
The convergence analysis of FW usually requires that the objective function is smooth, and that its curvature can be controlled. When applying FW-type algorithms to design an optimal sampling rule (a rule that converges the allocation w (1x) maximizing Fy), we face three issues: (i) F2 is not smooth; (ii) FA. has an unbounded curvature close to the boundary of Σ; (iii) l is unknown initially, so the FW iteration in round t can be applied to Fu(()) only. We discuss below how we circumvent these issues in the design of our algorithm.
ii) Non-smoothness of F'.. In view of Proposition F2 is the minimum of a finite number of smooth concave functions fj. Hence at points where two of these functions are equal in w. F₂ is not differentiable in w. The FW algorithm has been adapted to cope with non-smooth functions, 30 Typically, one constructs continuous approximations of the gradient close to non-smooth points of the functions. This construction often involves the r-subdifferential [16 2 which would be too costly to compute for Fu. Instead, we can leverage the fact Fy is the minimum of concave functions, and construct the called r-subdiffereenial subspace: for (0,1),
e.g.
Fr, (w) = cov [V. p): : Ji-mn: f. < (w((w)+)
(10)
where cov(S} denotes the convex hull of the set S. This choice greatly simplifies because it does not require to compute the gradient of f, in neighborhood of w. Since the fy are continuously differen- tiable, we can prove that w + Fr, (w. r) is a continuous (i.e. upper- and lower-hemicontimuuus)) Using the r-subdifferential subspace, the modified FW update is given as follows. Let (t) be the estimated optimizer of Fp. in round t. In round (t + 1). it is updated as:
z(t + 1) argmax min My, (a(()) (z (x),, h) (ties broken arbitrarity), x(t+1) 1) = 2. xt) + 2 ztt +).
(11)
Of course in the FWS algorithm, is unknown, and will be simply replaced by (a(t) in the above update. The way we choose the sequence of parameters {rake21 will be discussed later. Computing =t) is equivalent to solving zero-sum game, which can be further formulated as LP 40 (Chapter 20). Refer to Appendix for a detailed description of this LP.
(ii) Unbounded curvature of F₁. and (iii) unknown μu, These two issues are solved by a single trick. We impose that in the FW iterations, the update directions z(l) cover all ex, = 1,.... K sufficiently often. This ensures that the target allocation æ=(1) stays away from the boundary of Σ, which in turn allows us to control the curvature of Face) thanks to Assumption 2 This imposed constraint can be seen as a sort of forced exploration, and further implies (thanks to our tracking procedure) that each arm is played often enough. Now, with this kind of forced exploration, (t()) will concentrate around the true μ.
4.2 Algorithm
The FWS algorithm proceeds as follows. FWS maintains target allocation, denoted by x()), its empirical allocation w(t), and the empirical average rewards (u(() after round t. After an initialization phase (K rounds where each arm is selected), FWS alternates between forced exploration and FW updates. More precisely:
Forced exploration occurs at rounds where /\t/K] is an integer and at those where fu(t 1) $ A (in this case, we cannot compute the objective function). forced exploration round I, the target allocation is updated towards the center of the simplex: a+() - - 1) + (1/K, ... 1/K K). FW updates happen in other rounds. There, the target allocation is updated according to our adapted version of FW (11), where in round the unknown is replaced by fu(t 1). In the successive FW
For r E (0, 1), the r-subdiffferentil of vp K + IR. (where K. C R is compact and convex) is defined as (~)()) (4 k ((y) < v(x) + (y æ. h) + for all y K...

---

updates, we use r-subdifferential subspaces with varying parameter r. For the analysis of FWS, we will select a sequence parameters frehe21 with an appropriate decay rate.
After the target allocation is updated in round I, the algorithm tracks this allocation by selecting the arm maximizing over k the ratio (t) (t - 1). Finally, FWS, whose pseudo-code is presented below, uses the stopping and decision rules described in $32
Algorithm 1: FWS algorithm
Input: Confidence level 8, sequence {r1)21
Initialization: Sample each arm once and update w(K,, x(K) ( ..... k), and (t(K)
t 4 K
While (1 (w))) < 1(5, or - 1)
& - ++1
(v Lt/K] E or ji(t - 1) $ A) (forced exploration) z(t) f .R..... k)
Else (FW update)
2 (t) t argmax
min
(z - xx(t h) (ties broken arbitrarity)
REE heHraw--) (a((t1))))))
Update xt) + -La(t 1) + +z(1)
Sample the arm Ar t- argmax, Ix (t)//w(t( (t) (ties broken arbitrarily) Update (t) and ja(t)
Output: i" (f((t))
4.3 Sample complexity
In the following theorem, we establish the asymptotic optimality of FWS.
Theorem 1. Consider the FWS algorithm with a sequence frehez1 of strictly positive reals satisfying (i) lim;-roc 1 Ee=rr O, and (ii) lim4 tra cc. Under Assumptions I the algorithu
terminates in finite time almost surely and 5-PAC. Its sample complexity t sansfees:
limsup 8-0 log(1/8) S (Ti(H)) 1, and lim 8-+0 log(1/6) < (T).
Eg [T]
EA Pμ
The proof is given in Appendix ! We sketch the proof of the guarantees in expectation. The proof relies on classical concentration results, but more critically combines continuity arguments (developed in Appendix K to account for the varying ju((). and tools to analyze the convergence of the modified FW algorithm (reported in Appendix[] [T]
1. First using concentration inequalities and the fact that FWS includes forced exploration rounds,
we can define, for round t, a "good" event & under which (t) is very close to μ and such that
E IP, [_]]
Then, several continuity arguments have be made. In Lemma 6 (Appendix K) we show that fa + Fy. is continuous (w.r.t. the uniform convergence norm). In Theorem (Appendix
K also prove that the solution z(t 1) of the FW update 11) is continuous in μ.. The arguments
above allow us to analyze the convergence of the FW updates almost as if ju(t) was replaced by μ
provided that the event ε, occurs.
2. Now we can study under the event &,, the impact of the FW update on the target allocation. 6 (Appendix L) characterizing how (xx()) get closer The main step of proof is Theorem
to (w (f4)) in each FW update. We Then deduce That after a time Ti, Fa(y) (ax()) is a good
approximation of F (w)((()) (H1)..
3. We conclude the proof using similar arguments those in 13 According to
our stopping rule, t. > T if and only if (w)()(((t)) > Btt, Hence Eg [T] =
1r> -x P (FFt)(((() < ((t 0)] which can be approximately upper bounded by T +
>
00
PA [e + - Pn [tF (FF((((()))) < (t), The proof is concluded by remarking 9 of our stopping threshold, the last sum is close to T (14) (1g(1))) as
that in view of the property
0.
Note that proof of Theorem I accounts for the possibility in certain structures (c.g. linear) of
7

---

having multiple optimal allocations (these allocations form a convex set), We just reason in terms of the objective function (as in [18 for linear bandits).
Under the following additional assumption, we can derive non-asymptotic sample complexity upper bound for FWS. The proof of the following theorem is presented in Appendix N
Assumption 3. For any E A, there exist constants K, E > O, s.t. if || - pll S Ks then
π E (n),, You E E, j E (a) V=d(TT, >y(w, πT R.) is continuous and V Vn Xj سw ा ))))
S E, vk I.....K
Theorem 2. Consider the FWS algorithm with sequence frehe21 as in Theorem 7 Under Assump-
tions 2 and 3 the sample complexity T of the algorithm satisfies: for any μa E A, 8 E (0, 1), and
any ( 2/2 1},
I+E
(1+ (1))) ((F,(w*(H) -6e log log
(1 (1+7)c2(A)
En [T] S ()( - 6e
log
((F)(((())) Ge)
+ (K D, E, L, 0i (A), T
where Te,L is a constant such ift 2 Te,,, then Ex_ < tE and tr, > L. The constant Vi is and exponential K. The precise definition of is given in
polynomial in (A,,, 1/e) Appendix N
5
Examples and Experiments for Linear Bandits
5.1 Examples
Our framework can be applied to many pure exploration problems, including BAI in unstructured (see Example 1), linear, Lipschitz bandits. further covers threshold bandits (the problem of identifying all arms with rewards greater than threshold), linear threshold bandits, top-m bandits (where we wish to identify the best m arms), and dueling bandits. All these examples are presented in Appendix. Using numerical experiments, we show that FWS is competitive with state-of-the- algorithms for BAI in unstructured, linear, and Lipschitz bandits, see Appendices [ respectively. To the best of our knowledge, we report the first results for BAI in Lipschitz bandits. We quote some of our results for BAI linear bandits below.
When facing a new pure exploration problem, one can check whether it falls into our framework, by first directly verifying Assumption[] [T In Appendix we provide a simple sufficient condition ensuring that Assumption 2holds, and explain why all the aforementioned pure exploration problems satisfy this condition.
5.2 BAT in linear bandits
Linear bandits constitute arguably the most popular and important bandit problems with structure, and have found many applications [25] (. BAT in linear bandits has received lot of attention recently, see [2 To model linear bandits, we slightly modify our framework. The reason for this modification that the linear structure so strong that using our initial framework, the set A would be small, and we would have problems ensuring that (t) E A after some reasonable time t. Alternatively (rather than modifying the framework), we could modify the FWS algorithm so that (t) is projected onto A.
Consider a set of K arms. Arm ls is attached a d-dimensional feature vector a₁ and its average reward (ag, 14), where
Rd is unknown. Without loss of generality, assume that {as ]e([K] spans Rd We modify the definition of A as follows: A { E Rd 3k E [K] s.t.(a: - a; μ4) > 0, Vi + k). Hence a parametrizes the average rewards of the arms, but μı is not the average reward of arm k. The true answer is i" (H) argmax, (ax, p1). The lower bound optimization problem [ becomes:
supwes F (w( where (w) inf (EAR(A) 1 (1= X)
Σ w (1x A) and Alt( (X
A 3K # it (11) s.t. (,): A > 0}. e.g. 18). From there, we reproduce
framework: for Assumption I for all * it (u)), C, (H) [} E A (a, a. A) > 0); for
8

---

the functions/ fj, they are defined through:
(an:(w) - ag (4)
x)( - p
|aa0(()) - ag alll5= ) (az az=(w))
Vo-
(12)
where Vi = Eaaaaaa
the FWS algorithm for linear bandits, we use the Least-Squares Estimator (LSE) ju(t) given past observations, see [18] Appendix E for an explicit expression.
can be readily seen that this slight modification our framework does not affect the validity of Theorem 1 We just need to use the concentration inequalities derived in [8] for ji(() in the first step of its proot.
Numerical experiments. We consider the example proposed by (35], The unknown parameter 4 E1 and there d + arms, E,, ed. (os + sin (in( in Rd, where (e1,... , ea) form the standard orthonormal basis. We set d = 6 and Φ = 0.1. To assess the performance of the FWS algorithm, we compare with the following algorithms: the Lazy Track and Stop algorithm (LT) from [18]: LineGame-C (CG-C) and LineGame (Lk-C) from [9] and implemented by [34]: the XY-Adaptive algorithm (XY-A) from (35]. For information, we also run the Round Robin algorithm RR selecting each equally. For comparison, we finally compute the sample complexity lower bound (8) (equal T (v.)k(66 1)))
Except for XY-A, all algorithms implement the same stopping rule defined in 7 with threshold 8(t, 6) log( (t) + 1)/6) (this threshold was initially suggested in [13), and also used in (34] for CG-C and Lk-C). For XY-A, we use the stopping rule advocated in the corresponding papers. E for the detailed implementations.
Refer Appendix
In Table we present the sample complexity (the number of samples gathered before the algorithm stops) averaged over 1000 runs for the various algorithms and for different confidence levels 8 {0.1, 0.01, 0.001, 0.0001}. }. In Appendix E we provide detailed results, e.g. including box-plots (to show how confident we about the values displayed in Table T) as well the empirical allocations achieved under the various algorithms.
Table 1:
Sample complexity for the linear bandit benchmark example of 35 runs. Refer to Appendix for details, including box-plots.
averaged over 1000
FWS
LT
CG-C
Lk-C C
XY-A
RR
LB
8 0.1
1030
919
2498
2319
7016
5451
359
8 = 0.01
1614
1 464
3501
3431
7779
8814
920
0.001
2229
982
4324
4326
9.000
121
1 1408
8 = 0.0001
2839
2 518
5118
120
9723
15414
1881
6 Conclusion
We have developed FWS, a computationally and statistically efficient algorithm for active pure exploration in bandit problems with fixed confidence. In each round, FWS performs a single iteration of modified FW algorithm asymptotic lower bound. In the FWS algorithm, the FW iterations aim at maximizing non-smooth function. Our main contribution here to adapt the design FW so that its convergence can be analyzed even for this non-smooth function. FW-based pure exploration algorithms have been discussed in the literature, with the belief that they would perform well. We confirm this belicf, and establish the asymptotic optimality of FWS in wide class of pure exploration problems.
approach an optimal allocation arm draws predicted by the
Many interesting research directions could be investigated. Our analysis of the sample complexity in the moderate confidence regime has the advantage of being applicable to generic pure exploration problems, but may not be always tight. For bandits with specific structures, we may refine the analysis in this regime to get better upper bounds. We are also interested in investigating whether the iterative approach used in the FWS algorithm can be extended to more complex problems such as learning an optimal policy in MDPs, as well as regret minimization problems. There, instance-specine regret lower bounds and the corresponding optimal exploration process are characterized by the solution of an optimization problem, just in pure exploration problems.

---

Acknowledgments and Disclosure of Funding
The authors would like thank the anonymous reviewers whose comments helped us to improve the manuscript. R.-C Tzeng is supported by ERC Advanced Grant REBOUND (834862). A. Proutiere's research is supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. This work was also in part financially supported by Digital Futures.
10

---

References
[1] Andreas Argyriou, Marco Signoretto, and Johan Suykens. Hybrid conditional gradient- smoothing algorithms with applications sparse and low rank regularization. Regularization, Optimization, Kernels, and Support Vector Machines, 2014.
[2] Quentin Berthet and Vianney Perchet. Fast rates for bandit optimization with upper-confidence woofe- In Proc. of NeurIPS, 2017.
[3] Venkat Chandrasckaran, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky. The convex geometry of linear inverse problems. 2012.
[4] Edward Cheung and Yuying Li. Solving separable nonsmooth problems using frank-wolfe with uniform affine approximations. In Proc. of IJCAI, 2018.
[5] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proc. of AISTATS, 2011.
[6] Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. In Proc. of NeurlPS, 2017.
[7] Rémy Degenne and Wouter M Koolen. Pure exploration with multiple correct answers. In Proc. of NeurlPS, 2019.
[8] Rémy Degenne, Wouter M Koolen, and Pierre Ménard. Non-asymptotic pure exploration by solving games. In Proc. of NeurlPS, 2019.
[9] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In Proc. of ICML, 2020.
[10] Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. In Proc. of NeurIPS, 2019.
[11] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without a gradient. In Proc. of SODA, 2005.
[12] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 1956.
[13] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Proc. of COLT, 2016.
[14] Aurélien Garivier Pierre Ménard, Laurent Rossi, and Pierre Menard. Thresholding bandit for dose-ranging: The impact of monotonicity. arXiv preprint arXiv: 2017.
[15] Elad Hazan and Satyen Kale. Projection-free online learning. In Proc. of ICML,
[16] Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal. Convex analysis and minimization algo- rithms I: Fundamentals. Springer science & business media, 2013.
[17] Martin Jaggi. Revisiting frank-wolfe; Projection-free sparse convex optimization. In Proc. of ICML, 2013.
[18] Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. In Proc. of NeurIPS, 2020.
[19] Mare Jourdan, Mojmír Mutný, Johannes Kirschner, and Andreas Krause. Efficient pure explo- ration for combinatorial bandits with semi-bandit feedback. Proc. ALT, 2021.
[20] Zohar S Kaminn. Verification based solution for structured mab problems. In Proc. of NeurIPS, 2016.
[21] Emilie Kaufmann and Wouter Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. arXiv preprint arXiv:1811.11419, 2018.
11

---

[22] Tomáš Kocák and Aurélien Garivier. Best arm identification in spectral bandits. In Proc. of IJCAI, 2020.
[23] Yuko Kuroki, Junya Honda, and Masashi Sugiyama. Combinatorial pure exploration with full-bandit feedback and beyond: Solving combinatorial optimization under uncertainty with limited observation. arXiv preprint arXiv:2012.15584, 2020.
[24] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 1985.
[25] Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandi approach to personalized news article recommendation. In Proc. of WWW, 2010.
[26] Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit problem. In Proc. of ICMI., 2016.
[27] Blake Mason, Lalit Jain, Ardhendu Tripathy, and Robert Nowak. Finding all e-good arms in stochastic bandits. In Proc. of NewrlPS, 2020.
[28] Pierre Ménard. Gradient ascent for active exploration in bandit problems. arXiv, 2019.
[29] Federico Pierucci, 7aid Harchaoui, and Jérôme Malick. smoothing approach for composite conditional gradient with nonsmooth loss. PhD thesis, INRIA Grenoble, 2014.
[30] Sathya N Ravi, Maxwell D Collins, and Vikas Singh. A deterministic nonsmooth frank wolfe algorithm with coreset guarantees. Informs Journal on Optimization, 2019.
[31] Clémence Réda, Emilie Kaufmann, and Andrée Delahaye-Duriez. Top-m identification for linear bandits. In Proc. of AISTATS, 2021.
[32] Idan Rejwan and Yishay Mansour. Top-k combinatorial bandits with full-bandit feedback. In Proc. of ALT, 2020.
[33] Daniel Russo. Simple bayesian algorithms for best arm identification. In Annual Conference on Learning Theory. PMLR, 2016.
[34] Xuedong Shang. Linbai: Gamification of pure exploration for linear bandits. /attps://github com htwp//xueogg/ninn.... j1 2021. [Online; accessed 202111
[35] Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. Proc. of NeurIPS, 2014.
[36] Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification linear bandits with linear dimension dependency. In Proc. of ICML, 2018.
[37] Tengyao Wang, Nitin Viswanathan, and Sébastien Bubeck. Multiple identifications in multi- armed bandits. In Proc. of ICML, 2013.
[38] DJ White. Extension of the frank- wolfe algorithm to concave nondifferentiable objective functions. Journal of optimization theory and applications, 1993.
[39] Liyuan Xu, Junya Honda, and Masashi Sugiyama. A fully adaptive algorithm for pure explo- ration in linear bandits. In Proc. of AISTATS, 2018.
[40] Petyon Young and Shmuel Zamir. Handbook of game theory. Elsevier, 2014.
[41] Zixin Zhong, Wang Chi Cheung, and Vincent Tan. Best arm identification for cascading bandits in the fixed confidence setting. In Proc. of ICMI, 2020.
12


Reviews:
[{"review_id": "nn5uLiTemz4", "reviewer": "Reviewer_83MA", "summary": "The authors consider the active exploration problem in the fixed confidence setting for stochastic bandits. They propose a variant of the Best Challenger (BC) algorithm by [21] where the sampling rule is based on a variant of the Frank-Wolfe (FW) algorithm for non-smooth functions. They proved that this algorithm is asymptotically optimal with respect to the lower bound by [21]. They compare empirically their algorithm to various baselines such that Track-and-Stop by [21], AdaHedge versus Best-Response by [13], Lazy Mirror Ascent by [29] and Optimistic Track and Stop by [13] for the following unstructured active exploration problem: threshold bandits, best arm identification, top-m bandits and dueling bandits. They also explain how to adapt the proposed BC algorithm to two structured settings namely linear bandits and Lipschitz bandits for best arm identification. Finally, they conduct experiments in these two additional settings.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written. The proofs seem globally correct (see specific comments for some details that are not completely clear, I did not check the appendix K and N). I think the proposed work is a valuable contribution to the fixed-confidence BAI topic. In particular, I find the proposed \"fix\" of the BC algorithm very interesting.\n\nMain comments:\n-Can you elaborate on the time complexity of your algorithm and compare it to the other baselines?\nIn particular, is it much faster to solve the linear program in (11) than directly find the maximum of F_{\\mu} which can be done efficiently also (see [21]).\n-I find the name of the algorithm BC and claiming that it is based on the FW algorithm a bit miss-leading. Indeed, at each step the proposed algorithm does not pull an arm between the best arm and a certain best challenger in fact z(t) could put mass on all the arms depending on the r-sub differential. This is far enough from the original BC algorithm to justify naming it differently. Similarly, the optimizer behind the sampling is not the FW algorithm by [12] even if it is close in the spirit. Maybe using the names, e.g.,  non-smooth FW and FW algorithm would make the introduction and the abstract clearer.\n-Do you think it will possible to avoid the forced exploration? Indeed this seems a crucial point in the analysis here to bound the curvature cf assumption 2. In particular, this could be useful for the linear setting with many arms because with the force exploration you have to pull each time all the K arms.\n\nSpecific comments:\n-L168: You can also mention Carpentier et al. (2011). Upper-confidence-bound algorithms for active learning in multi-armed bandits and Tarbouriech and Lazaric (2019) Active Exploration in Markov Decision Processes, for another pure exploration problem in bandit and reinforcement learning where FW is used.\n\n-L216: maybe you should define at some point the FW algorithm at least in the appendix and highlight that you want to use it to find the optimal weights that are a minimizer of F.\n\n-L224: Is it for all w?\n\n-L237: maybe you should describe in detail the learning procedure before.\n\n-L240: and if N_k(t) = 0?\n\n-L263, Algorithm 1, while condition loop: a priori F_\\mu is only defined for \\mu in \\Delta\n\n-L298: Can you detail the overall time complexity of the proposed best challenger algorithm since it's a bit unclear because of the linear program to solve.\n\n-L344: I do not understand this sentence especially given paragraph 5.2.\n\n-L354: Can you elaborate on the dependence on the number of arms K of the bound? And does this theorem apply to linear bandits?\n\n-L1012: you need to precise that \\mu \\in \\Delta so that F_\\mu and H_{F_\\mu} are well defined.\n\n-L990: how do we know that \\pi = \\hat{\\mu}^{t-1} belongs to \\Delta in order to apply Theorem 3?\n\n-L1252: z_k(s) instead of z_k(t)\n\n-L1004, Lemma 5: why there is a s\\geq 1?\n\n-L998, (44): it seems you upper bound \\xi(\\epsilon) by 1 maybe you should let \\xi(\\epsilon) = \\min{1,\\ldots}.\n\n-L1145: with respect to which norm?\n\n-L1170: |z-x|_{\\infty} and there is no |z-x|_{\\infty}^2 below no? \n\n-L1174: min_n \\phi_n\n\n-L1195: It should be \\Delta_{t+1} and \\Delta_{t} in (49) no?\n\n-L1218: The equality is rather with x instead of w?\n\n-L1221: again it seems that the case where \\hat{\\mu}(t-1) \\notin \\Delta is not considered.\n\n-L1239: you should not rather control the norm of x(t) - x(Kq^2) here?\n\n-L1245: an inequality is missing here.\n\n-L959: w(t)\n\n-L961: can you detail the inclusion? Is it for T\\geq T(\\delta)?\n\n-L964: what is the definition of \\tilde{\\epsilon}?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is a theoretical paper without direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "l3fk8yTXE0p", "reviewer": "Reviewer_AySN", "summary": "The paper analyses Frank-Wolfe for pure exploration problems on structured bandits.  To address smoothness issues that arise from a direct application of FW to the lower-bound optimization problem, the authors compute the best-response as the solution to a saddle point problem that includes the convex hull over gradients of approximate minimizers. The main result is that the resulting algorithm is PAC and asymptotically optimal on the sample complexity. Empirically, FW outperforms state-of-the-art methods on the presented benchmarks. The authors further characterize lower order terms of the sample complexity.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The authors adequately discuss related work. FW has been applied in the context of best-arm identification before, but the novelty is to show convergence and address the non-smoothness of the lower bound. The resulting algorithm remains relatively simple, however still requires to solve a (linear) saddle point problem on each step.\n\nQuality & Clarity:\nThe paper is generally well-written and the important ideas are presented in the main paper. There is also a detailed appendix that includes several example applications. I have not checked the proofs in detail. It would be great to mention how the r-subdifferential space is used in the proof to show convergence of FW (ie summarizing Appendix L). Please also mention the choice of r_t in the main paper (l 653). Is the algorithm sensitive to the choice? What is the reason behind your choice? Does the algorithm empirically converge for r_t = 0?\n\nSignificance:\nThis paper makes an important technical contribution to the best-arm / pure-exploration literature; moreover the algorithm is relatively simple and outperforms other methods empirically. \n\nMinor: \n95: 'optimism in the face of uncertainty' is more common\n114: 'the' objective function\n\n[edit]\nI'd like to thank the authors for their detailed responses and clarifications.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation of the algorithm is that it still requires to solve a linear saddle point problem, which is more expensive than standard Frank-Wolfe. The compute complexity depends on how many near-optimal actions are in the r-subdifferential. My intuition is that at the equilibrium of (1), there can be a lot of actions in this set.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "8T7NAPj0QXT", "reviewer": "Reviewer_uPhV", "summary": "This paper studies pure exploration in generic stochastic bandit problems under fixed confidence budgets. At the core of this approach is relying on a single iteration of frank-wolf (FW) to solve a non-smooth problem. The single iteration of FW reduces the computational burden, but is challenged by the non-smoothness. The authors successfully cope with the challenge and the resultant algorithm looks theoretically sound. In addition, the numerical results are promising in certain cases, though have a similar performance with Bernoulli and Gaussian rewards.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "(+) Overall, this paper is technically sound. FW is a very good choice for such a problem since the constraint sets are in general polytopes. \n\n(-) This paper can benefit from adding more intuition, and some figures to explain the assumptions and related concepts. It is not easy from first read to gather all necessary info to understand the proposed algorithm. \n\nSuggestions and Questions:\n\ni) Is there any intuition behind Assumption 3? And is it easy to verify in practice?\n\nii) What is the run time compared with e.g., [13] and [29]?\n\nMinor: In line 339, it looks like there is a typo for the name of an algorithm from [9].", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper mainly focuses on the theoretical side. The societal impact may depend on specific applications.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper makes a definitive contribution to the active exploration MAB literature. The core idea is not completely new but the modifications and variations proposed in the paper are meaningful advances relative to state of the art best arm identification algorithms. The paper is well written. The reviewers are all in favor of accepting, the dialogue with the authors was informative and honest with several issues still left open but for well justified reasons (e.g., computational complexity considerations). I would make this a clear accept but not a top paper because of the nature of contribution being relatively technical relative to antecedent work and some of the documented computational limitations. Thanks to the reviewers and authors for well done work and the fruitful exchange.  
Decision: Accept (Poster)