On Elimination Strategies for Bandit Fixed-Confidence Identification
Authors: Andrea Tirinzoni
Rémy Degenne
Venue: NeurIPS 2022 Accept (2022)

Abstract: Elimination algorithms for bandit identification, which prune the plausible correct answers sequentially until only one remains, are computationally convenient since they reduce the problem size over time. However, existing elimination strategies are often not fully adaptive (they update their sampling rule infrequently) and are not easy to extend to combinatorial settings, where the set of answers is exponentially large in the problem dimension. On the other hand, most existing fully-adaptive strategies to tackle general identification problems are computationally demanding since they repeatedly test the correctness of every answer, without ever reducing the problem size. We show that adaptive methods can be modified to use elimination in both their stopping and sampling rules, hence obtaining the best of these two worlds: the algorithms (1) remain fully adaptive, (2) suffer a sample complexity that is never worse of their non-elimination counterpart, and (3) provably eliminate certain wrong answers early. We confirm these benefits experimentally, where elimination improves significantly the computational complexity of adaptive methods on common tasks like best-arm identification in linear bandits.

On Elimination Strategies for Bandit Fixed-Confidence Identification
Andrea Tirinzoni*
Meta Al Paris, France t tirinzoni crnizoniifb.... w@fi. com
Rémy Degenne
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRISIAL, F-59000 Lille, France remy. degenne@inria.fr
Abstract
Elimination algorithms for bandit identification, which prune the plausible correct answers sequentially until only remains, computationally convenient since they reduce the problem size over time. However, existing climination strategies are often not fully adaptive (they update their sampling rule infrequently) and are not easy to extend to combinatorial settings, where the set of answers is exponentially large in the problem dimension. On the other hand, most existing fully-adaptinn strategies to tackle general identification problems are computationally demanding since they repeatedly test the correctness of every answer, without ever reducing the problem size. We show that adaptive methods can be modified to use elimination both their stopping and sampling rules, hence obtaining the best of these worlds: the algorithms (1) remain fully adaptive, (2) suffer sample complexity that never worse of their non-elimination counterpart, and (3) provably eliminate certain wrong answers early. We confirm these benefits experimentally, where elim- ination improves significantly the computational complexity of adaptive methods on common tasks like best-arm identification in linear bandits.
1 Introduction
The multi-armed bandit is sequential decision-making task which is now extensively studied (see, e.g., [1] for a recent review). this problem, an algorithm interacts with its environment by sequentially "pulling" one among K e N arms and observing sample from a corresponding distribution. Among the possible objectives, we focus on fixed-confidere identification 2 3 4 S).
In this setting, the algorithm successively collects samples until decides stop and return answer to given query about the distributions. Its task is to return the correct answer with at most a given probability of error 6, and its secondary goal is do while stopping as early possible. This problem is called ffxeedconfiidnce" as opposed to "fixed-budge"" where the goal to minimize the 10
error probability with at most given number of samples 6
The most studied query is best arm identification (BAI), where the aim is to return the arm whose distribution has highest mean. A variant is Top-m identification (II. where the goal is to find the m arms with highest means. While these are the most common, other queries have been studied, including thresholding bandits (9) minimum threshold [12), and multiple correct answers [3]
Work done while Inria Lille.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Algorithms for on adaptive sampling and those based on elimination. Adaptive algorithms [e.g.. their sampling strategy at each round and typically stop when they can simultaneously assess the correctness of every answer. They often enjoy strong theoretical guarantees. For instance, some of have been shown to be optimal as 5 - O. However, since they repeatedly test the correctness of every answer. they are often computationally demanding. Elimination-
identification can be generally divided into two classes: those based
14 update
them 4
13 16 [7]
strategies [e.g..2 18 1o 20 21 maintain set of "active" answers (those that are still likely to be the correct one) and stop when only one remains. They typically update their sampling rules and/or the active answers infrequently. This, together with the fact that eliminations reduce the problem size over time, makes them more computationally efficient but also yields large sample complexity in practice. Moreover, while adaptive algorithms for general identification problems (i.c., with arbitrary queries) exist 4 15 177. elimination-bass strategies are not easy to design at such a level of generality. In particular, they not easy to extend to structured combinatorial problems (such as Top-m), where the number of answers is exponential in the problem dimension
In this paper, we design a novel elimination rule for general identification problems which we call selective elimination. It can be easily combined with existing adaptive strategies, both in their stopping and sampling rules, making them achieve the best properties of the two classes mentioned above. In particular, we prove that (1) selective elimination never suffers worse sample complexity than the original algorithm, and hence remain asymptotically optimal whenever the base algorithm is; (2) It provably discards some answers much earlier than the stopping time; (3) It improves the computational complexity of the original algorithm when some answers are eliminated early. Experimentally, we compare several existing algorithms for three identification problems (BAI, Top-m, and thresholding bandits) two bandit structures (linear and unstructured). We find that, coherently across all experiments, existing adaptive strategies achieve significant gains in computation time and, smaller extent, in sample complexity when combined with selective elimination.
1.1 Bandit fixed-confidence identification
An algorithm interacts with environment composed of K 1 arms. At each time / E N, the algorithm picks arm hy and observes X Vkk,, where Vkk is the distribution of arm ky At time t, the algorithm stops and returns an answer from a finite set I. Formally, let F, be the o-algebra generated by the observations up to time (. An identification algorithm is composed of
1. Sampling rule: the sequence (kx)) where k, is -
2. Stopping rule: stopping time 7 with respect to (Fi)Len and a random variable i E I, i... the answer returned when stopping at time T.
Note that, while it is common to decouple and i, we group them to emphasize that the time at which an algorithm stops depends strongly on the answer plans on returning.
We assume that the arm distributions depend on some unknown parameter 0 E M, where M S Rd the set of possible parameters, and write v%: (0) for k [K] to make this dependence explicit. For simplicity, we shall use 0 to refer to the bandit problem (vs, (O))k{]) This assumption allows us to include linear bandits in our analysis. We let i* .M- - I be the function, known the algorithm, which returns the unique correct answer for each problem. The algorithm is correct on 0 if = (0).
Definition 1.1 (Ó-correct algorithm). An algorithm is said to be 8-correct on M C R for all 0 E M, T < +o0 almost surely and Po # (0)) < 8.
We want to design algorithms that, given value 8, are 8-correct on M and have minimal expected sample complexity Eg [r] for all 0 E M. A lower bound on Eg[T] was proved in 4. In order to present it we introduce the concept of alternative set to an answer E I: A(i) set of parameters for which the correct answer is not i. Let us denote by KL (0, A) the Kullback- Leibler (KL) divergence between the distribution of arm & under @ and A. Then the lower bound states that for any algorithm that is 8-correct on M and any problem 0 E M.
{} M (A) * i}. the
E+[7] 2 (og(1((244))/HHH()) with H' (0) == max inf
Σ WLKKL,O,A). RE(K
(I)
WEAN XEA(S (0))
An elimination strategy for specitic unstructured combinatorial problems has been introduced in 22

---

Example: in Gaussian linear bandits While our results apply to general queries, we illustrate
all statements of this paper on the widely-studied task of BAI in Gaussian linear bandits [T9 14 23
16 [4]. In this setting, each arm & E [K] has a Gaussian distribution N (yu (0). 1) with mean pa (0)
6x 0, linear function of the unknown parameter 0 E IR (and M = IRd) and of known arm features
Φx E Rdd The set of answers is I = [K] and the correct answer is i (0) = arg ma[k 01 0.
Finally, for x Rd and Rdxd, we define ||æ||A == vx T Ar. For w E RK let Vu :
Eks wn O With this notation, we have ΣkE(K] w (L, A) = 2/10- - -
1.2 Log-likelihood ratio stopping rules
Most existing adaptive algorithms use a log-likelihood ratio (LLR) test in order to decide when to stop. Informally, they check whether sufficient information has been collected to confidently discard at once all answers except onc. Since such LLR tests are crucial for the design of our general elimination rules, we now describe their principle.
Given two parameters 0, x E M, the LLR of observations [ = (X X between models dF's
0 and is (0,, >) == log de, (x) = E'_ log d'a be the maximum likelihood estimator of from observations. In Gaussian linear bandits, we have Lo( 1 Alli,, + (0- A) (0, 0) where NY := E.=1 (k, - k). See Appendix C for more details. (0, 2) is closely related to Σ N KL& (6, A), a quantity that appears frequently in our results. Indeed, the difference between these quantities is martingale, which is a lower order term compared to them. The LLR stopping rule was introduced to the bandit literature in 4.. At each step / E N. the algorithm computes the infimum LLR to the alternative set of in (0r) and stops if it exceeds threshold, i.c., if
dP, (X++). Let 0g == arg M log PP (x)
inf Lo(O.. A) 2 BL,5
(2)
where the function Be,8 can vary, notably based on the shape of the alternative sets. The recommenda- tion rule is then = (0.). Informally, the algorithm stops if it has enough information exclude all points \ for which the answer not i* (ft). This stopping rule enforces 8-correctness, provided that the sampling rule ensures r < +oo a.s. and that Be,s is properly chosen. The most popular choice is to ensure a concentration property of (2 0). For example, if for all 6, Br,6 guarantees that
TP t 2 I, (0,, 0) 2 31,6) S 8,
LLR stopping with that threshold returns a wrong answer with probability at most 8. Such concen- tration bounds can be found in [25 26 for linear and unstructured bandits, respectively. This LLR stopping rule is used in many algorithms 4 [4 15
24 17 Some of them have been proven to be asymptotically optimal: their sample complexity upper bound matches the lower bound (I when 5 - 0. However, improvements are still possible: their sample complexity for moderate may not be optimal and their computational complexity may be reduced, as we will see.
16
2 Elimination stopping rules for adaptive algorithms
We show how to modify the stopping rule of adaptive algorithms using LLR stopping to perform elimination. We assume that the alternatives sets A(i) can be decomposed into a union of sets which we refer to as alternative pieces (or simply pieces), with the property that computing the infimum L.RR over these sets is computationally easy.
Assumption 2.1. For all E I, there exist pieces (Ap(1)))EP()) where P(i) is finite set of piece indexes, such that A(1) = UpEP(y Ap(1) and inf infxes,() (f,, X) can be efficiently computed for all E P()) and t > 0.
LinGapE 14 does not use LLR stopping explicitly, but its stopping rule is equivalent to it. We write it as: stop if for all points inside a confidence region a gap is small cnough, that if all those points do not belong to the alternative of i (0:). The contrapositive of that statement is exactly LLR stopping.
3

---

This assumption is satisfied in many problems of interest, including BAI, Top-m identification, and thresholding bandits (see Appendix BB. Indeed, in all applications we consider in this paper, the sets of Assumption 2. are half-spaces. In our linear BAI example, the piece indexes are simply arms. For i,J E [K] we can define (i) = {> E M x > of A). Then, A(i) = Uze (1)). Moreover, the infimum LLR (and the corresponding minimizer) can be computed closed form as [c.g..20 inf (1) Lo(Be, A) = max (8 (Ø. - Φy). / - dyl
Elimination stopping The main idea is that it is not necessary to exclude all Ap(1) for E P(i) at the same time, as LLR stopping (2) does in order to know that the algorithm can stop and return answer Instead, each piece can be pruned as soon as we have enough information to do so.
Definition 2.2. A set C Rdd is said to be eliminated at time if, for all À E S, (., A) 2 Be,8.
From the concentration property 3 we obtain that the probability that 0 E S and S is eliminated is less than 5. LLR stopping interrupts the algorithm when the alternative set A(i (()))))) can be eliminated. In elimination stopping, we eliminate smaller sets gradually, instead of the whole alternative at once. Formally, let us define, for all i E I,
Pi( Br,6) = P(P())) inf T,((0, A) < Br,6 xEA,(()
as the subset of pieces for answer i E I whose infimum LLR at time is below a threshold 31,6. That is, the indexes of pieces that are not eliminated at time t. Moreover, we define, for all i E I, a set of active pieces PetP(() (i) which is initialized as Po (i) = Pii) (all piece indexes).
Our selective elimination rule updates, at each time t, only the active pieces of the empirical answer ir (0.). That is, for = i* (0t), it sets
(() = P:- P
(5)
while it sets (1) =- P (i) for all i + (0..). One might be wondering why not updating all answers at each round. The main reason is computational: as we better discuss at the end of this section, checking LLR stopping requires one minimization for each piece p E P(i* (ft)). while selective elimination requires only one for each active piece p E PP- (i (0.)). Thus, the latter becomes increasingly more computationally efficient as pieces are eliminated. For completeness, also analyze the variant, that we call full elimination, which updates the active pieces according to (5) for all answers i I at each round. While establish slightly better theoretical guarantees for this rule, it is computationally demanding and, as we shall see in our experiments, it does not significantly improve sample complexity w.r.t. selective elimination, which remains our recommended choice.
Let elim = inf Pe (i*(() = 0} and eilelim infez1 {t 3i E I Pit 0} be the stopping times of selective and full climination, respectively. Intuitively, these two rules stop when one of the updated answers has all its pieces eliminated (and return that answer). We show that, as far as Re,5 is chosen ensure concentration of Ó, O, those two stopping rules are d-correct.
Lemma 2.3 (6-correctness). Suppose that 3t,5 guarantees (3) and that the algorithm verifies that, whenever stops, there exists ig E I such that P.t (ix) = 6 and = ig. Then, Po # i*)) S 8.
All proofs for this section are in Appendix D If an algorithm verifies the conditions of Lemma 2.3 and has a sampling rule that makes it stop almost surely, then it d-correct. Interestingly, we can prove a stronger result than ò-correctness: under the same sampling rule, the elimination stopping rules never trigger later than the LLR one almost surely. In other words, any algorithm equipped with elimination stopping suffers a sample complexity that is never worse than the one of the same algorithm equipped with L.R stopping. Let Thr := infezı (t inf XEx((=(0)) (0 A) 2 Br,8).
Theorem 2.4. For any sampling rule, almost surely Tr.elin S Tx.eii S Tik
The proof of this theorem is very simple: if Tue t, then t all pieces Appi" A&)))(()) for p E (())
can be eliminated, hence Ts.elim I t. The proof that Tr.lii I Ts.elim follows from the observation
'Under Assumption 2.1 LLR stopping is written as min infxEA,()) (., A) 2 BL, for = '" (0.). which implies that all alternative pieces of answer discarded at once.

---

that full elimination always has less active pieces than selective elimination. Note that all three stopping rules must use the same threshold Br to be comparable. Although simple, Theorem [24 has an important implication: we can take any existing algorithm that uses LLR stopping, equip with elimination stopping instead, and obtain new strategy that is never worse terms of sample complexity and for which the original theoretical results on the stopping time still hold.
Finally, it important to note that, while defining the elimination rule in the general form (5) allows us unify many settings, storing/iterating over all sets (i) would be intractable in problems with large number of answers (e.g., top-m identification or thresholding bandits, where the latter exponential in K). Fortunately, show in Appendix B that this is needed and efficient implementations exist for these problems that take only polynomial time and memory.
2.1 Elimination time of alternative pieces
We now show that elimination stopping indeed discard certain alternative pieces much earlier that the stopping time. While all results so far hold for any distribution and bandit structure, in the remaining we focus Gaussian linear bandits. Other distribution classes beyond Gaussians could be used with minor modifications (see Appendix CC22 but the Gaussian case simplifies the exposition. Since most existing adaptive sampling rules target the optimal proportions from the lower bound of [4, we unify them under the following assumption.
Assumption 2.5. Consider the concentration events
Ei = (= V St: (). B01118
A sampling rule is said have low information regret there exists a problem-ddppnndnt funncett function R(0, t) which is sub-linear in t such that for each time t where E, holds,
inf
Nº KI. KEIK
Σ
tH (6) R(0,t).
XEA (O))
The left-hand side of (7) can be understood as the information collected by the sampling rule at time t discriminate with all its alternatives. Therefore, Assumption 2ssumpiionn25freqquire requires that information to be comparable (up to low-order term Ri t)) with the maximal one from the lower bound. In Appendix we show that this satisfied by both Track-and-Stop 4 and the approach in [15].
Let Hp(w, 0) == infxex,(e ΣME[K] wh KL (0, A), the information that sampling with proportions brings to discriminate 9 from the alternative piece (O)) Note that (0) = max minppe Hp(w, 0). For 2 O, let (2) = fw E <Ak
inf infxeM( (0)) Σn w KL, X) 2 (0) - <} be the set of e-optimal proportions.
Theorem 2.6 (Piece elimination). The stopping time of any sampling rule having low information regret, combined with LLR stopping, satisfies E[T] < E 2, where i is the first integer such that
t> ==(BB.o+VBB
R(B,t) ((O.,))/HHOO))
(8)
When the same sampling rule is combined with elimination stopping, let Tp be the time at which p E Pi* (0)) is eliminated. Then, B[Tz] I min 8) + 2, where tp is the first integer such that
(VBr. + v 111)
2 max
minweR Hp 0) G(B,
with G(O,t) = 0 for full elimination and G(O.t) 43 + for selective elimination. H0
First, the bound we obtain on the elimination time of pieces in (() is not worse than the bound we obtain on the stopping time of LLR stopping. Second, with elimination stopping, such eliminations can actually happen much sooner. Intuitively, sampling rules with low information regret play arms with proportions that are close to the optimal ones. If all of such "good" proportions provide large information for eliminating some piece p E P(i (0)), then p is eliminated much sooner than the actual stopping time (which requires eliminating the worst-case piece in the same set).
5

---

While both elimination rules are provably efficient, with full elimination enjoying slighly better guarantees] selective elimination provably never worsens (and possibly improves) the computa- tional complexity over L.R stopping. In all applications we consider, implementing LLR stopping requires one minimization for each of the same alternative pieces we use for elimination stopping. Therefore, the total number of minimizations required by LLR stopping is Σ (P(i+(0))) versus Eist ( (f.)) for selective elimination. The second is never larger since Ts.elim S Tur by Theorem 2.4 and (i & (())) for all and much smaller if eliminations happen early, as we shall verify in experiments. In our linear BAI example we need to perform (K - minimizations at each step, one for each sub-optimal arm, in order to implement LLR stopping. On the other hand, we need only /P: (i' (8.)) minimizations with selective elimination, one for each active sub-optimal arm, while full elimination takes ΣiE(K] (i) to update all the sets.
Note that Theorem does not provide a better bound on [[[r] for elimination stopping than for LLR stopping. In fact, when evaluating the bound on E[rp] for the worst-case piece in p P(ii we recover the one on E[r]. This is intuitive since the sampling rule is playing proportions that try to eliminate all alternative pieces once. The following result formalizes this intuition.
Theorem 2.7. Suppose that we can write Br,6 log 1
x + E(4,6) with lims E(I, ((1,0)//og((1))) O.
Then for any sampling rule that satisfies Assumption 2.5
E|mie]= S B[Tetim] + f(0,0).
with lims- f(0,6)/ 1og(1/6) = 0. Here Telim can stand for either full or selective elimination.
See Appendix D.4 for f. This result shows that when the sampling rule is tailored to the LLR stopping rule, the expected LLR and elimination stopping times differ by at most low-order (in log( 1
terms. As 5 + 0 the two expected stopping times converge to the same value H (0) log 1/8).
which is the seymptotically-opimna sample complexity prescribed by the lower bound (I).
We showed that, for both elimination rules, some pieces of the alternative are discarded sooner than the stopping time, and that the overall sample complexity of the method can only improve over LLR stopping. However, since the sampling rule of the algorithm was not changed, elimination does not change the computational cost of each sampling step, only the cost of checking the stopping rule.
2.2 An example
We compare LLR and elimination stopping on a simple example so as to better quantify the elimination times of Theorem 2.6 and their computational impact (see Appendix H.1 for full diseussion).
Consider BAI a Gaussian linear bandit instance with unit vari- ance, d = 2, and arbitrary number of arms K > 3 (see Figure Db. The arm features are Φ1 = (1,0)², Φ2 = (0, 1)² and, for all i = 3,..., K, Φ; (a;, b²2² with a;, by arbitrary values in (-1,0) such that ||0,112= = 1. The true parameter is 0 = (1, 11,1-4 1-E)", possibly very small value. Arm I is optimal with mean n1 (0) = I, while arm 2 is sub-optimal with mean (0) = e. For all other arms = 3, ... K, (0) S O.
Hu
(M*
288
for E E (0, 1/2)
81
du
Let E Ax be any allocation. Recall that BAI each piece index is simply an arm, and P(it(())
P(1)= = [2..... K). Let k E P(1) be any sub-optimal arm. The distance to the k-th alternative piece Ha 0) can be computed in closed form as Ha (w, 0) = ((0) )x ) / - de ..) The optimal allocation is
(o)) 2 1/32
w- arg max_, min; Hu(w, 0) 1//2,1/2,0.....0
Figure 1: Example of BAI in- stance with == 2 and K = 5.
The intuition why this example is interesting is as follows. Any correct strategy is required discriminate between arm 1 and 2 (i.e., to figure out that arm 1 is optimal), which requires roughly 0(1/E²) samples from both. An optimal strategy plays these two arms nearly with the same proportions. Since Φ1 and Φ2 form the canonical basis of IR2, the samples collected by this strategy are informative for estimating the
$ Note that G(O, t) for selective elimination contributes only finite (in 8) sample complexity.

---

mean reward of every arm, even those than are not played. Then, since arms ...... K have at least sub-optimality gap of I, an elimination- baasatdio---ddddddddeed strategy discards them with number of samples not scaling with 1/62. This means that non-elimination strategy runs for ((1/e²) steps over the original problem with K arms, while an elimination- basse one quickly reduces the problem to one with only 2 arms. The main impact is computational: since most algorithms need to compute some statistics for each active arm at each round (e.g., closest alternatives, confidence intervals, etc.), the computational complexity of non-climination algorithm is at least O(K/s²), while the one of an elimination-basse variant is roughly O(K + 1/="). ) a potentially very large improvement.
We now quantify the elimination times and computational complexity on this example. Since such quantities depend on the specific sampling rule, we do for an oracle strategy that samples according to w Similar results can be derived for any low information regret sampling rule (see Appendix [
Proposition 2.8. For any K 2 3 and E (0, 1/2), for any 8 (0, 1), the oracle strategy combined with LLR stopping satisfies on the example instance
(og((1/))
E 2 Ω
E2
On the same instance, for the oracle strategy with elimination at stopping and a threshold Br,5 log(L/6) + (loo(()), the expected elimination time of any piece (i.e., arm) k 2 3
E E(Tx] - ((log(1/8))
for full elimination,
E [x] < Ō [og((1/)) +
1 E2
for selective elimination.
Moreover. the expected per-round computation time of the oracle strategy with LLR stopping is (2(K). while it is at most ((?²²²) full elimination and O(K=² + K/ log(1/8)) for selective elimination.
3 Elimination at sampling
We show how to adapt sampling rules in order to accommodate piece elimination. There are two reasons for doing this: first, adapting the sampling to ignore pieces that have been discarded could reduce the sample complexity; second, the amount of computations needed to update the sampling strategy often proportional to the number of pieces and decreasing can reduce the overall time.
We start from an algorithm using LLR stopping, for which we change the stopping rule as above. The sampling strategies that we can adapt are those that aggregate information from each alternative piece. For example, in linear BAI methods that mimic the lower bound allocation ① like Track-and-Stop 4 LinGame [6), or FWS [17], and even LinGapE [4, all compute distances or closest points to each piece in the decomposition {} I Φ A o (0-(0.))) *..
A}. Eliminating pieces at sampling simply means omitting from such computations the arms that were deemed sub-optimal. Algorithm [ shows how Track-and-Sie
4 can be modified to incorporate elimination at sampling and stopping.
Algorithm 1 Track-and- 4
vanilla (left) and with selective elimination (right)
while not stopped do
while not stopped do Set P. (i" (('(())) = Pi-1 (it()))
for E (0)) do
b stopping
for E P (0.)) do
D stopping
Lp.t = inf xnfx (f,, A)
Lp.: = inl (c L.(
if Lp,: > Br, delete p from pett (i*())
end for
end for
if vP E (()) : Ly,, > Br, then STOP wy = arg max,, min (E Hp(w, 0.) if 3k Nº < vl pull k241 = arg min, Nt else pull ke+1 arg min, twf)
if (I""(((")))) = @ then STOP
wi = arg max min " Hw, 0.) ir N/ < vt pull ke41 arg min, No. else pull ket1 = arg m - twf)
Update perp (i" (ô.) (Algorithm
end while
end while
Similarly to elimination stopping, the idea to maintain sets of active pieces at sampling (i) for each E I. Note that these are different from the ones introduced in Section for the stopping
7

---

rule. The set is updated at each step like we did for the stopping sets, but with a different threshold 0g,5 (see Appendix E for details). Additionally, we reset it very infrequently at steps t (1% )22. where to 2 2. Formally, let us define the helper sets P(
(i) as Po Pomp (i) P(t) and
(1) n (e Pemp(() (i) = (((()
if $ 16 b20
otherwise,
where Pt was defined in 4.. Let t, = Eo' be the time step at which the j-th reset is performed
and j(() == [log2 logr, L] be the index of the last reset before I. We define P.mm(()) (i) = P:mppp (i) n (i) is the intersection of all active pieces from the second- reset up to t,
pamp (1), such that Pr
-1 ie., P. (i) - - (t; (,,6). Since the resets are very infrequent, this definition only drops small number of rounds from the intersection (less than vt. The detailed procedure to update these sets is summarized in Algorithm 3 As before, we can instantiate both selective and full elimination.
The reason for the resets is two-fold. First, they ensure that the algorithm stops almost surely as required by Definition I.I In fact, without resets, might happen with some small (less than ō) probability that pieces containing the true parameter are eliminated, in which case the sampling rule could diverge. Second, they guarantee that the thresholds () used in P. Pamp (i) are within constant factor of each other. This is crucial to relate the LLR of active pieces at different times.
3.1 Properties
We consider counterpart of Assumption 2.3 for sampling rules combined with piece elimination. Assumption 3.1. There exists a sub-linear (in t) problem-ddpendent funncint R(O, t) such that, for each time where Ee (defined in Equation 6 holds,
min (F-
max Σ min WEAK (E
()_(00)-R(000) t).
Intuitively, the sampling rule maximizes the information for discriminating 0 with all its alternatives from the sequence of active pieces (P=mP (i))) We prove in Appendix F that the algorithms for which we proved Assumption 2.5 also satisfy Assumption 3.1 when their sampling rules are combined with either full or selective elimination.
Theorem 3.2. Consider a sampling rule that verifies Assumption 3.1 and uses either full or selective elimination with the sets P.mpp Then, Assumption 2.5 holds well. Moreover, when using the same elimination rule at stopping, such a sampling rule verifies Theorem 2.6 i.e., it enjoys the same guarantees as without elimination sampling.
The proof is in Appendix E Theorem 3.2 shows that for an algorithm using elimination at sampling and stopping, we get bounds on the times at which pieces of A(i are discarded from the stopping rule which are not worse than those we obtained for the same algorithm without elimination at sampling. This result is non-trivial. We know that the sampling rule collects information to discriminate with its closest alternatives, and eliminating a piece cannot make the resulting "optimal" proportions worse at this task. However, it could make them worse at discriminating 0 with alternatives that are not the closest. This would imply that the climination times for certain pieces could actually increase w.r.t. not eliminating sampling. Theorem 3.2 guarantees that this does not happen: eliminating pieces at sampling cannot worsen our guarantees. We shall see in our experiments that eliminating pieces in both the sampling and stopping rules often yields improved sample complexity.
4 Experiments
Our experiments aim at addressing the following questions: (I) how do existing adaptive strategies behave when combined with elimination stopping and (when possible) at sampling? How do they compare with native elimination- based methods? (2) What is the difference between selective and full elimination? (3) How do LLR and elimination stopping compare a function of 8:
Our code is available at httttttss//gtthu /tte http://hhhhooooooooooeeet/aoaaaa

---

LinEapE LinGame FWS Oracle
50
Stopping (se)
Stopping ssamplinng (sel)
Fart or enappt ng Steve
LinCapE Lincame FWIS Oracle
Stopoing ()a
of activv
Stopoing sampling (full)
10x10"
16
3020
4092
6000
15
7ime
Tine
Figure 2: Experiments on linear instances with K = 50, d d= 10, averaged over 100 runs, with the right plot showing standard deviations. (left) How different adaptive algorithms eliminate arms in BAI when using elimination stopping. (middle) LinGame on BAI when combined with full and selective climination rules, either only stopping both at stopping and at sampling. (right) Ratio between the L.R and elimination stopping times of different algorithms as a function of (1)(1
We ran experiments on two bandit structures: linear (where d < K) and unstructured (where K and the arms the canonical basis of IR... For each of them, we considered 3 pure exploration problems: BAI, Top-m, and online sign identification (OSI) [9] also called thresholding bandits. All experiments use 8 0.01 and are averaged over 100 runs.
We combined adaptive algorithms which are natively based on L.R. stopping with our elimination stopping rules and, whenever possible, we extended their sampling rule to use elimination. The selected baselines are the following. For linear BAI LinGapE. [4), LinGame [16],
-oole
Sampling (FWS) [17], Lazy Track-and-Stop (TaS) (24), XY-Adaptive [19] and RAGE (20] (the latter
two are natively elimination based). For linear Top-m, m-LinGapE (28) MisLid (29], FWS, Lazy Tase and LinGIFA 288. For linear OSI, Lin LinGame, FWS, and Lazy TaS. For unstructured instances linear algorithms are still applicable, and we further implemented LUCB M. UGapE (8), and the Racing algorithm [18] for BAI and Top-m. We also tested an "oracle" sampling rule which uses the optimal proportions from the lower bound. Due to space constraints, we present only the results linear structures. Those unstructured problems can be found in Appendix G The first experiments use randomly generated instances with K = 50 arms and dimension
10.
Comparison of elimination times. We analyze how different adaptive algorithms eliminate pieces when combined with selective elimination at stopping. To this purpose we focus on BAI, where the sets of pieces can be conveniently reduced to a set of active arms, those that are still likely to be the optimal one. Figure 2 left) shows how the set of active arms evolves over time for the adaptive baselines. Notably, many arms eliminated very quickly, with most baselines able to halve the set of active arms in the first 3000 steps. The problem size is quickly reduced over time. As we shall see in the last experiment, this will yield significant computational gains. We further note that the "oracle" " strategy, which plays fixed proportions, seems the slowest at climinating arms. The reason is that the optimal proportions from the lower bound focus discriminating the "hardest" arms, while the extra randomization in adaptive rules might indeed eliminate certain "easier" arms sooner.
Full versus selective elimination. We combine the different algorithms with full and selective elimination, both at sampling and stopping. Due to space constrains, Figure 2 results only for LinGame (see Appendix G for the others). We note that full elimination seems faster at discarding arms in earlier steps, as we would expect theoretically. However, it never stops earlier than its selective counterpart. Moreover, its computational overhead is not advantageous. Overall, we concluded that our selective climination rule is the best choice and we shall thus focus on it in the remaining. Finally, remark that combining the sampling rule with climination (no matter of what type) seems to discard arms faster in later steps, and could eventually make the algorithm stop sooner.
middle) shows the
LLR versus elimination stopping. We now compare LLR and elimination stopping as a function of 6. We know from theory that both stopping rules allow to achieve asymptotic optimality. Hence for asymptotically optimal sampling rules the resulting stopping times with LLR and elimination should tend to the same quantity as 8 - 0. Figure 2 right), where we report the ratio between the LLR stopping time and the elimination one for different algorithms, confirms that this is the case. Some algorithms (LinGapE and FWS) seem to benefit less from elimination stopping than the others,
? "Lazy TaS, while analyzed only for BAI, can be applied to any problem since it is variant of Track-and-Stopp
'LinGapE was originally proposed only for BAI in [14, but its extension to OSI is trivial.

---

No elimination (LLR)
Elim. stopping
Elim. stopping sampling
Algorithm
Samples
Time
Samples
Time
Samples
Time
LinGapE
33.19 + 8.7
0.23
33.11 + 8.7
0.2
29.89
8.6
0.18(-22%)
LinGame
45.34 = 14.2
0.23
43.67 = 13.4
0.21
32.49 8.1
0.18(-22%)
FWS
42.26 = 60.1
0.73
42.25 = 60.1
0.7
32.62 + 18.0
0.45(
BAI
Lazy TaS
76.33 + 0.15
71.08 + 65.8
0.13
64.48 + 81.8
0.12( 20%)
Oracle
56.36 + 9.1
0.05
55.36
+ 9.3
0.02
XY-Adaptive
87.08 + 29.1
0.44
RAGE
106.87 = 30.7
0.02
Top-m (m. = 5))
m-LinGapP
63.69 + 11.1
0.56
63.48 + 11.0
0.41
59.57 + 9.4
0.24(-57%)
MisLid
87.77 + 20.4
0.55
85.95 20.5
0.4
69.58 + 16.0
0.25(-55%)
FWS
78.28 =
3.0
78.23 65.0
2.85
77.79 + 65.0
(.97(-67%
Lazy Tas
161.43 96.9
0.57
159.86 96.9
0.43
146.06 + 82.6
0.36 36%)
Oracle
102.45 -: 16.1
0.2
101.53
16.4
0.08
LinGIFA
58.31 + 10.8
2.46
58.31 = 10.8
2.33
LinGapE
17.31 1 2.3
0.22
17.29 2.2
0.19
14.71 2.0
0.17(-239)
LinGame
23.77
0.25
23.05
3.9
0.21
14.87
2.0
0.19( 0.19(-24%)
OSI
FWS
15.26
0.83
15.24
0.81
14.99
2.1
0.56(-3296
Lazy Tas
35.11 = 10.2
0.32
33.98
9.7
0.3
23.51 - 5.6
0.24(-25%0
Oracle
29.1 = 4.8
0.06
28.65 - 5.0
0.03
Table Experiments on linear instances with K 50, 20. The "Time" columns report average times per iteration in milliseconds. The percentage in the last column is the change w.r.t. the time without elimination. Each entry reports the mean across 100 runs plus/minus standard deviation (which is omitted for compute times due to space constraints). Algorithms for which the third column missing cannot be combined with elimination at sampling, while algorithms for which the first two columns are missing are natively elimination-base based. Samples are scaled down by factor 10
i.e. they achieve smaller ratios of stopping times. We believe this to be consequence of their mostly "greedy" nature, while the extra randomization of the other algorithms might help in this aspect.
Sample complexities and computation times. We finally compare our baselines in all three exploration tasks, in terms of sample complexity and computation time. For this experiment, we selected larger linear instance with K 50 and d = 20, randomly generated (see the protocol in Appendix G). From the results in Table we highlight three points. (1) The computation times of all adaptive algorithms decrease when using selective elimination stopping instead of LLR and further decrease when also using elimination at sampling. In the case of Top-m (i.e., the hardest combinatorial problem), most adaptive algorithms become at least twice faster with elimination stopping and sampling instead LLR. (2) Elimination at sampling improves the sample complexity of all algorithms. (3) For BAI, the natively elimination-basee algorithm RAGE, which updates its strategy infrequently, the fastest in terms of computation time but the slowest in terms of samples. Adaptive algorithms using elimination achieve times that within order of magnitude of those of RAGE, while outperforming it in terms of sample complexity by factor 2 to 3.
Conclusion
We proposed selective elimination rule, which successively prunes the pieces of the empirical answer, that can be easily combined with existing adaptive algorithms for general identification problems. We proved that it reduces their computational complexity, it never worsens their sample complexity guarantees, and it provably discards certain answers early. Our experiments on different pure exploration problems and bandit structures show that existing adaptive algorithms often benefit from a reduced sample complexity when combined with selective elimination, while achieving significant gains in computation time. Moreover, they show that selective elimination is overall better (in terms of samples vs time) than its full variant which repeatedly updates the pieces of all answers.
Interesting directions for future work include investigating whether better guarantees on the stopping time can derived for algorithms combined with elimination as compared to their L.R counterparts, and designing adaptive algorithms which are specifically tailored for climination.
10

---

References
[1] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[2] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. In International Conference on Computational Learning Theory, pages 255-270. Springer, 2002.
[3] Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE, 2014.
[4] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027, 2016.
[5] Lijie Chen and Jian Li. On the optimal sample complexity for best arm identification. arXiv preprint arXiv: 1.03774, 2015.
[6] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armes bandits problems. In International conference on Algorithmic learning theory, pages 23-37. Springer, 2009.
[7] Lean-Yves Audihert, Séhastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pages 41-53. Citeseer, 2010.
[8] Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In NIPS-Tiwent--Sine Annual Conference on Neural Information Processing Systems, 2012.
[9] Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference on Learning Theory, pages 590-604, PMLR. 2016.
[10] Yasin Abbasi Yadkori, Peter Bartlett, Victor Gabillon, Alan Malek, and Michal Valko. Best of both worlds: Stochastic & adversarial best-arm identification. In Conference on Learning Theory, pages 918-949. PMLR, 2018.
[11] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. In ICML, volume 12, pages 655-662, 2012.
[12] Emilie Kaufmann, Wouter Koolen, and Aurélien Garivier. Sequential test for the lowest mean: From thompson to murphy sampling. arXiv preprint arXiv: (t0:://8000055 2018.
[13] Rémy Degenne and Wouter M Koolen. Pure exploration with multiple correct answers. arXiv preprint arXiv: 2019.
[14] Liyuan Xu, Junya Honda, and Masashi Sugiyama. A fully adaptive algorithm for pure explo- ration in linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 851. PMLR, 2018
[15) Rémy Degenne, Wouter M Koolen, and Pierre Ménard. Non-asymptotic pure exploration by solving games. In Advances in Neural Information Processing Systems, pages 14492-14501, 2019.
[16] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432- 2442. PMLR, 2020.
[17] Po-An Wang, Ruo-Chun Tzeng, and Alexandre Prouticre. Fast pure exploration via frank- wolfe.
In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
[18] Emilie Kaufmann and Shivaram Kalyanakrishnan. Information complexity in bandit subset selection. In Conference Learning Theory, pages 228-251. PMLR, 2013.

---

[19] Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. Advances Neural Information Processing Systems, 27:828-836. 2014.
[20] Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. In Advances in Neural Information Processing Systems, volume 32, 2019.
[21] Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification linear bandits with linear dimension dependency. In International Conference Machine Learning, pages 4877-4886. PMLR, 2018.
[22] Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. Advances in neural information processing systems, 27:379- 387, 2014.
[23] Mohammadi Zaki, Avi Mohan, and Aditya Gopalan. Explicit best arm identification in linear bandits using no-regret learners. arXiv preprint arXiv:2006. 2020.
[24] Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. arXiv preprint arXiv:2006.16000 16073, 2020.
[25] Yasin Abbasi-Yadkorf Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
[26] Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pages 975-999, PMLR, 2014.
[27] Reda Ouhamma, Rémy Degenne, Pierre Gaillard, and Vianney Perchet. Online Sign Identi- fication:
Minimization of the Number of Errors in Thresholding Bandits. In NeurlPS 2021 35th International Conference on Neural Information Processing Systems, NeurlPS 2021
35th International Conference on Neural Information Processing Systems, pages 1 1-25, Virtual,
Canada, December 2021.
[28] Clémence Réda, Emilie Kaufmann, and Andrée Delahaye-Duriee Top-m identification for linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 1108-1116. PMLR, 2021.
[29] Clémence Réda, Andrea Tirinzoni, and Rémy Degenne. Dealing with misspecification in fixed- confidence linear top-m identification. 35th Conference on Neural Information Processing Systems, Virtual, 2021.
[30] Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. Advances in Neural Information Processing Systems, 13:1417-1427, 2020.
[31] Emilie Kaufmaan, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
12

---

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


Reviews:
[{"review_id": "es8mff7YTwC", "reviewer": "Reviewer_FuX3", "summary": " The authors propose a new algorithm design principle for elimination algorithms in the fixed-confidence, best-arm-identification setting with parametric distributions that modifies the usual stopping rule of track-and-stop-style algorithms (adaptive in their terminology).\n\nRoughly, under an assumption that the parameter space of each alternative for each arm i (i.e. the parameters that would result in any arm other than i being the best) can be decomposed into a small subset of pieces that are easy to optimize over, the authors propose elimination of individual pieces. In contrast, the typical track-and-stop algorithm will continue until all pieces except for those belonging to a single action can be eliminated. This procedure can reduce the cost of checking the stopping rule, and is shown to have the same guarantees (correctness and asymptotic efficiency).\n\nThe authors then present sampling rule that also takes into account pieces that have been eliminated and show that, under a technical assumption, the new sampling rule does not degrade the sample complexity. Improved performance in both sample complexity and time complexity is shows experimentally.\n\n", "questions": "Can you provide some justification for your assumptions?Are there special cases when you can provably show an improved sample complexity?", "limitations": "I think a closer discussion about the assumptions is needed. Societal impact was not addressed, but I don't think it's necessary.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "While the writing was generally high quality, I found the overall presentation confusing and the theoretical results a bit underwhelming (though I didn't read the appendix, so it is possible the technical difficulties were larger than I thought).\n\nFirst, I found the main ideas difficult to understand and had to work through section 2 a few times. I think the presentation could be improved if the section was restructured to highlight a cartoon of the original track-and-stop and introduce your new ideas an modifications. It wasn't immediately clear to me if your procedure would produce an action elimination algorithm or an adaptive algorithm. Beginning with the explanation that you are in the parametric setting and are modifying track and stop would help.\n\nI also wish that the elimination sampling algorithm was presented more clearly, perhaps with pseudo-code (at least for your favorite instantiation of an adaptive algorithm). \n\nIt might be good to give a bit more intuition about what \"adaptive sampling\" and \"elimination\" algorithms do and their differences, especially since there are several well known algorithms (e.g. LUCB, TS variant)) that don't fit into your two classes. Specifically, I found your \"repeatedly test the correctness of every answer\" confusing, and it would be probably clearer to describe how elimination algorithms work in phases/epochs. I might go so far at to argue that \"adaptive\" is a confusing choice, as elimination algorithms also change their sampling distributions as data are collected (albeit usually through eliminating actions). Perhaps phased / non-phased would be a clearer distinction.\n\nAnother very import distinction is that \"elimination algorithms\" are generally non-parametric, needing only some way to get finite-sample confidence intervals on the target parameters, whereas \"adaptive\" methods require strong parametric assumptions.\n\nI wish there was theory showing improvement in the sample complexity, and I wish there was a discussion about the assumptions (specifically, an argument about why they should be necessary).\n\nOther feedback:\nline 137: bad grammar\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XRMEIweoL0", "reviewer": "Reviewer_rbgz", "summary": "The paper considers the problem of finding (or identifying) the correct answer to a specific question in a bandit scenario. Examples are what is the arm with the highest mean (best arm identification), or which arms have a mean larger than some specific value (thresholding bandits)? For this purpose, they revisit the algorithmic approaches based on log-likelihood ratio stopping, which are theoretically quite appealing but are oftentimes computationally expensive. Roughly speaking, these approaches stop as soon as there is an answer such that the alternatives to these answers are not plausible enough (measured in terms of minimal distance of log-likelihood ratio). Under the assumption that the underlying bandit problem scenario allows a decomposition of the possible alternative sets into smaller subsets (called pieces), the authors suggest two stopping criteria that have provably a smaller stopping time than the log-likelihood approach provided all are using the same sampling strategy. These stopping criteria are combining the log-likelihood ratio stopping approach with the non-adaptive elimination-based approaches by excluding pieces as soon as these are ``redundant’’ for the decision making. The authors show that for a couple of Gaussian linear bandit problems the assumption above is satisfied and the minimizer of the log-likelihood ratio can be efficiently computed on the corresponding pieces. Moreover, a bound in expectation on the resulting stopping times are shown, when the stopping criteria are combined with an efficient sampling rule.\nInspired by the suggested stopping criteria the authors derive a sampling strategy that is specifically tailored towards an early stopping of the former. The suggested approaches are investigated in an experimental study on synthetic data.", "questions": "- Are there bandit settings where it is not possible to decompose the alternative set into meaningful pieces? If yes, these should be mentioned in the paper.\n \n- Of course, one might ask why the full elimination approach is considered at all, if it has such a high runtime, while the sampling complexity in the experiments is not significantly different compared to the LLR approach. In this way, the authors could save some space, which could be used to discuss other relevant things, e.g., describe how to apply the methods to other bandit settings than Gaussian linear bandits.\n\n\n\n", "limitations": "I would have appreciated if the authors would give a remark regarding a direct comparison of the actual stopping times, i.e. in which case it is possible and in which it is not. I think only for Theorem 2.6 it is. \n\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n## Quite interesting topic\nThe underlying problem setting of general identification in bandits is a relevant theoretical problem scenario covering a range of practical applications and has already been investigated by a couple of several authors. The underlying research question of whether the fully adaptive approaches can be adapted such that they are computationally more efficient such as the non-adaptive elimination strategies is of utmost relevance for practical applications. The key challenge is of course to maintain the appealing theoretical properties of the fully adaptive approaches.\n\n## Soundness\nOverall, most of the results are sound as well as their proofs. I haven’t checked all proofs in every last detail but had a thorough look at the proofs of core results, which were fine as far as I can tell.\n\n## Quality of writing/presentation\nIn general, the paper is well written. Although it is a rather technical paper the notation is well thought out.\n\n# Weaknesses\n\n## Modest theoretical contribution\nAlthough the paper contains a fairly extensive appendix of proofs of the theoretical results, these are largely based on prior work and no groundbreaking new ideas come in, as far as I can tell. Therefore, I think the theoretical contribution of this paper is okay, but not significant.\n\n\n## Vague description of eliminating at sampling \nThe part about the suggested sampling strategy can be improved regarding its clarity. To be more precise, I would have appreciated if the eliminating at sampling approach would have been presented in form of a pseudo-code instead of a rather vague verbal description.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VE4H2fQ_bSv", "reviewer": "Reviewer_gFGn", "summary": "This work bridges the gap between elimination algorithms and fully adaptive algorithms for identification problems in bandits. One the one hand, the main strength and weakness of elimination algorithms are their high computational efficiency and large sample complexities, respectively. One the other hand, fully adaptive algorithms enjoy stronger sample complexity guarantees while being computationally inefficient. In this paper are designed fully adaptive algorithms that perform elimination. These algorithms are shown to get the best of both worlds, both theoretically and empirically.\n", "questions": "- In practice how does one modify an existing algorithm (say e.g. Track-and-Stop) to incorporate any of the elimination steps suggested in this work?\n- Writing the infimum LLR in closed form is very illustrative. Are there settings where the quantities in the theorems are closed form? If so, would it be possible to add some more explicit statements?\n- Are there original algorithms and new elimination counterparts of these for which the computational complexity can be computed? The claimed improvement on computational complexity feels very empirical, instead of being theoretically characterized.\n", "limitations": "I did not really find a clear statement about the limitations of the work. The authors state that the potential negative societal impacts of their work is N/A. This work is mainly theoretical, but it might still be valuable to mention how bandit algorithms are applied to the world and e.g. what could go wrong if the suggested algorithms are used.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The framework has a broad range of applications: it covers among others the problems of gaussian bandits, top-k, thresholding identification for linear and unstructured bandits.\n- On this general setup, this work successfully tackles the problem of designing strategies that are both fully adaptive and performing elimination.\n- The experiments support the theoretical claims.\n\nWeaknesses: \n- This paper could benefit from a better presentation: \n- It would be nice to highlight a pseudo-code of the algorithm designed.\n- It takes a long time to get to the main theoretical results.\n- The theorems are hard to parse without examples/instantiations.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Q4kDJ2BlE5n", "reviewer": "Reviewer_W482", "summary": "The paper proposes elimination rules that can be easily combined with existing fixed-confidence algorithms for pure exploration, both for sampling and stopping strategies. The benefits are improved performance in the nonasymptotic regime. The authors show a result that the elimination stopping results in eliminating pieces no later than the standard LLR stopping.", "questions": "Theorem 2.6. I understand that with elimination stopping it is never worse, but it is not clear if it makes a meaningful difference. I was not able to pin down on exactly how (9) can be strictly better than (8). I don't have a good sense on whether $H^*(\\theta)$ is related to $\\min_{...} H_p(\\omega,\\theta)$ in (9). I'd like to hear from the authors on this. Without a careful comparison, I cannot say for sure that it is meaningful. To make a stronger argument, I would find a specific instance where (8) can be orderwise larger than (9) to showcase the real difference.\n\nThe explanation of reset times in Section 3.1 was not clear at all to me. What is the role of the resetting? It would  be beneficial if we have a protocol/pseudocode description of what we expect from existing algorithms and what we do for eliminating the pieces, side by side. Also, please provide a specific example algorithm where you show how elimination pieces at sampling can be combined.\n\nHow existing elimination strategies are not easy to extend to combinatorial settings: I think Successive Accept and Reject (SAR) was applied to combinatorial pure exploration in Chen et al., Combinatorial Pure Exploration of Multi-Armed Bandits, 2014. I would be surprised if one cannot apply SE/SAR style algorithms for the problem that the authors' are concerend?\n\nI will adjust the score based on the feedback.\n\nminor comments\n\n* I would have one displayed equation or table or figure that compares LLR, full elimination, selective elimination like next to each other.\n* In the end of section 3.1, “the reason for having different sets of active pieces for stopping and sampling is that it allows us to derive guarantees on expected stopping times. If one is only interested in high-probability results, it is possible to use the same set for both components.” ⇒ this is not immediately clear.\n* Section 3.1's description can be improved. It would also be beneficial if we have a protocol/pseudocode description of what we expect from existing algorithms and what we do for eliminating the pieces, side by side.\n  * Actually, it'd be better if there is a specific example algorithm where you show how elimination pieces at sampling is applied.\n* It would be great if we know what stp and smp stands for in notations.\n* definition of $\\tilde{\\mathcal{P}}\\_t^{smp}$ : for the first line, did you mean to use $\\alpha_{t,\\delta}$ where $t$ is actually the most recent reset time j(t)? The current definition seems like it always computes $\\overline{\\mathcal P}\\_t(i; \\alpha\\_{t,\\delta})$ all the time anyways.\n  * I also did not understand the purpose of this the reset times. why are we doing resets? is it because we will be discarding samples?\n  * for reset times, are we using just the samples from the last block of time steps to compute $\\overline{\\mathcal P}$ or using entire samples ?\n* Line 726, an union ⇒  a union \n* Line 738, we the following ⇒ the following \n\n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength is that the proposed strategy leads to improved empirical performance. The weakness is that the theory does not seem to be strong, at least in the current form.\n\nThe contribution is clear, but the details can be explained better. So, I would say that clarity is below expectation. Originality, quality, and significance is all mediocre (just around the bar).\n\nMy main complaint is that there is no 'provable' improvement of the proposed methods in mathematical analysis. I do not mean the proof for 'not worse', but a proof like 'a strictly upper bound can be achieved and it can make an orderwise difference in some cases'. Empirical evaluation shows that the empirical performance improvement can be better, but in my opinion, it is rather a minor improvement.\n\n----\n(after rebuttal) I have changed the score as the authors have addressed the concern.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept