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)-dimeeet 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 (t(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 (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": "v5m4DmQ08qM", "reviewer": "Reviewer_8vBR", "summary": "The paper studies pure exploration in the fixed confidence setting for generic stochastic bandits. They develop a new algorithm based on Frank-Wolfe, give conditions under which it matches the lower bound (asymptotically as delta goes to 0), and empirically evaluate it. ", "questions": "", "limitations": "", "rating": 6, "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 argues that most prior work solves the optimization problem (1) at each round, which can be computationally expensive. To address this, they give an algorithm that just takes one step of Frank-Wolfe at each round instead.\n\nI found the assumptions 2 and 3 difficult to interpret. I think it would be useful to give more explanation in the main text on when these conditions hold, especially assumption 2. Given that prior work (e.g., [9]) has already solved this problem in such a generic setting, it would be useful to understand how restrictive assumption 2 is to compare to prior work. Are these assumptions strong enough to make the sample complexity result substantially weaker than prior work? Or are these assumptions relatively benign?\n\nThe authors say in lines 100-106 that the work of [29] is quite similar to the current work, except that LMA does worse empirically. Is this the only advantage of the current paper, superior empirical performance? I think it is important to distinguish the current paper from prior work more clearly so that the contribution is clear.\n\nThe authors write in line 56 that inner optimization problem in (1) can be hard. This was a bit unclear to me. Do they mean it is NP-hard or just intensive? Could examples be provided?\n\nBuilding on this, if the main advantage of the current work is being computationally lightweight, it would be useful to demonstrate this in experiments or examples of settings that are difficult for prior algorithms. Are there settings where the proposed algorithm does well, but existing algorithms do not scale to them? Essentially, are there problems that the current algorithm solves, but prior algorithms do not?\n\n\nAfter the rebuttal: thank you for the helpful clarification. I increased my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I forsee no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ok_761rmzm3", "reviewer": "Reviewer_ABte", "summary": "This paper studies the pure exploration problem for stochastic bandits. In particular, the authors focus on the fixed-confidence setting. The main contributions of the paper are the following:\n\n- First, the authors propose a variant of the BC algorithm by Garivier and Kaufmann, 2016, where the sampling rule is based on a Frank-Wolfe-type algorithm adapted to non-smooth functions. \n- Second, the authors show that the proposed algorithm is asymptotically optimal (in the sense that it matches the lower bound derived by Garivier and Kaufmann, 2016). \n- Experimental illustration is given on various scenarios including both structured (like linear BAI and BAI for Lipschitz bandits) and unstructured BAI. All the experiments are against several existing baselines (though probably better to add some more past and recent baselines as mentioned in the 'Limitations and Societal Impact' section).\n", "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": "Clarity: The paper is well written and the delivered message is clear. \n\nQuality: I did not check the all the proofs in detail (54 pages is quite long honestly), but they seem to be sound in general. Proof-related questions are listed in the 'Limitations And Societal Impact' section. \n\nOriginality and significance: This paper proposed a variant of BC with a modified FW (adapted to non-smooth functions) that achieves the asymptotic optimality in a wide range of pure exploration scenarios. For me it is an interesting result and valuable contribution to the BAI community (at least for fixed-confidence BAI), since it has a wide range of practical usage thanks to FW and in the mean while avoids the $\\beta$-tuning issue for top-two algorithms. The technical novelty is also generally sound (please see below for some technical comments).\n\nSome technique-related comments:\n- Line 240: What if $N_k(t) = 0$?\n- Line 990: How do we know that $\\pi = \\hat{\\mu}^{t-1}\\in \\Lambda$?\n- Line 1012: $\\mu$ needs to be in $\\Lambda$ right?\n- Proposition 3: $F$ is Lipschitz with respect to which norm?\n- Line 1171: Are you sure about the last inequality $||z-x||_{\\infty}^2$?\n- Line 1252: $z_k(t)$ -> $z_k(s)$.\n- Line 1277: It seems that $\\Psi$ is exponential in the number of arms $K$? Could it be a problem when dealing with many arms?\n\nOverall, I vote for accept for this paper. Please see the next section for major questions and minor comments.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal Impact: not applicable\n\nMajor questions:\n- I think it could be helpful to compare the time complexity of the FW update against its counterpart in other algorithms (for example, you can compare the average execution time of different sampling rules), as in my opinion this is one important reason why we are interested in FW here. \n- I am quite curious about the forced exploration phase, do you think it is possible to get rid of it?\n\nMinor comments:\n- What is LT-H?\n- It would probably be better to include LinGapE (Xu et al., 2018) and RAGE (Fiez et al., 2019) as well in the experiments for linear BAI.\n- Probably better to also include top two algorithms (Russo, 2016; Qin et al., 2019; Shang et al., 2020) in the experiments (in particular for unstructured bandits).\n- It would probably be better to place the acronyms (like T-D, D-C, etc) directly into the plot captions.\n", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "LR9oqaHHL0", "reviewer": "Reviewer_2Czm", "summary": "This paper studies the best arm identification problem in the fixed confidence setting. Frank Wolfe algorithm is employed to solve the minimax problem for the optimal arm allocation. They establish the asymptotic optimality of their methods in a wide class of pure exploration settings. The sample complexity is empirically confirmed in the numerical simulations.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Concern on the originality :\nThe lower bound of MAB pure exploration is proved in  [21], and most existing papers solve a lower bound optimization which is introduced in equation (1) at each round t. Such algorithms achieves the asymptotically optimal, but solving (1) at every round is  computationally inefficient.\nIn this paper, instead of solving (1) in each round as in [21], they propose an online iterative method to converge the optimal allocation of arm pulls \\omega^*.\nThis concept is already discussed in the work of [39], which performs an online lazy mirror ascent to solve a lower bound optimization (1). Their method can avoid computing (1) at every round since it is sufficient to compute at each steps only a subgradient to maximize the concave but not smooth objective function over the simplex.\n\nThe addition by this paper is to connect FW-algorithms with pure exploration problems for solving non-smooth functions. There is a surprising work of [42] that can be applied to solving non-smooth objective functions; this enables us to leverage the analysis of the Frank-Wolfe algorithm in pure exploration bandit problems.\n\nTo sum-up, it is not so clear that this paper’s contribution is significant. The drawback of the computational issue of [21] is already discussed in [39]. Best Challenger type algorithm is also not new, which was already introduced in [21].  Analysis for  non-smooth objective function by FW-algorithms is given by [42]. This paper combines those existing work’s ideas but it is not really clear which part is the novel developed and what is the difficulty to  leverage them. \n\n[21] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Proc. of COLT, 2016.\n\n[39] Pierre Ménard. Gradient ascent for active exploration in bandit problems. arXiv, 2019.\n\n[42] Sathya N Ravi, Maxwell D Collins, and Vikas Singh. A deterministic nonsmooth frank wolfe algorithm with coreset guarantees. Informs Journal on Optimization, 2019.\n\n============\nThank you for your feedback,  my concern is clearly addressed by author's response.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper is well-written and self-contained. However, it would be great if the authors clarify the main challenges in more detail.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6,7 hours"}, "extra_text": {}}, {"review_id": "Hs3G6LGBqtt", "reviewer": "Reviewer_5onQ", "summary": "The authors propose a new framework for structured (and unstructured) pure exploration problems. They propose a new algorithm based on modified FW where the motivation comes from the BC algorithm from the TaS paper that can be interpreted as an FW step. They show the asymptotic optimality of the algorithm and provide a finite-time analysis. The empirical results on various bandit problems show the superiority of the proposed framework.\n ", "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": "high originality, mediocre quality (see my comments on experiments below), clarity is good, and the significance is above bar.\n\n* The main contribution is very clear: they provide a new framework and recipe for solving generic pure exploration problems. I think the authors did a nice job of interpreting best challenger from Garivier & Kauffman as a frank-wolfe step and find a way to do it right.\n* I feel the experiments are quite biased in that the baseline methods are missing a few popular algorithms including RAGE, LinGapE, and ALBA.  For the unstructured problem, lil ucb and LUCB are missing. Thus, I am not  convinced about its performance. \n* I was excited to read the abstract that we take only one step in each iteration since that would mean the computational complexity is much improved. However, it seems to require solving the linear program. Could the authors discuss the time complexity of the algorithm? For pure exploration problems, It seems to be worse than TaS.\n* Please add a discussion on the significance of Theorem 2 in the main content of the paper. I guess the first term looks fine, but how should readers take \\Psi() and T_{\\epsilon,L}? Does the authors think the exponential dependence on K should be improvable? \n\nminor points\n* L136: \"close the boundary\" => close to the boundeary?\n* L151-152: \"the optimism-in-front-of-uncertainty \": I've seen it called 'optimism in the face of uncertainty' more frequently.\n* L680: did you mean [21] rather than [29] here? there are other places like L698.\n* Okay, I am struggling with finding the precise definition of $\\Lambda$​. So, $\\Lambda$​ is the set of possible instances for which there is only a unique best arm? Then, it is not a convex set? I ask this to understand the if statement in Algorithm 1 that has $\\hat \\mu(t-1) \\not \\in \\Lambda$​​ . I could guess but I would appreciate if the definition of $\\Lambda$ is more explicit.\n* Assumption 3: is \\forall symbol missing in front of $\\pi \\in \\mathcal{S}_{i^*(\\mu)}$?\n* L290: con() was defined as con{}.\n\n----\n(after rebuttal)\nI am mostly satisfied with the rebuttal. I now remember that lil'ucb was evaluated in \"Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting\" and was empirically shown to be worse than LUCB in practical regimes anyways. But it would be great to have that remark in the final version.\n\nFor Assumption 3, I understand it now. I rephrase and expand the sentence to make it easier to read. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see a negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "no concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has initially received mixed reviews, with some reviewers expressing concerns about the significance of the contribution. These concerns were sufficiently addressed by the authors' response, and, after a short discussion, all reviewers agreed that the paper is strong enough for publication at the conference. I concur with this assessment and recommend that this paper be accepted.
Decision: Accept (Poster)