Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits
Year: 2021

Abstract:
In the fixed budget thresholding bandit problem, an algorithm sequentially allocates a budgeted number of samples to different distributions. It then predicts whether the mean of each distribution is larger or lower than a given threshold. We introduce a large family of algorithms (containing most existing relevant ones), inspired by the Frank-Wolfe algorithm, and provide a thorough yet generic analysis of their performance. This allowed us to construct new explicit algorithms, for a broad class of problems, whose losses are within a small constant factor of the non-adaptive oracle ones. Quite interestingly, we observed that adaptive methods empirically greatly out-perform non-adaptive oracles, an uncommon behavior in standard online learning settings, such as regret minimization. We explain this surprising phenomenon on an insightful toy problem.

heading: 1 Introduction and related work
text: In a stochastic multi-armed bandit problem, a decision maker sequentially samples from different distributions in order to optimize a loss that depends on the unknown parameters of those distributions. As a consequence, a tradeoff arises between gathering more samples from any possible distribution (to enhance the estimation of relevant parameters) and optimizing the allocation to minimize the final loss. We can distinguish two main categories of losses, focusing on “exploitation” vs “exploration”. The former directly depends on the whole allocation of samples and the typical example is regret minimization (we refer to the recent monographs [27, 6, 34] that cover this setting almost exhaustively). The later is a bit different; after the budget of samples is exhausted, the algorithms must answer one or several “questions” (on the different distribution) and its loss is related to the number of mistakes made; the typical application being best-arm identification and variants [3, 24].
We investigate a class of pure exploration problems, called “thresholding bandit” [28, 35]. The key property of this class is that a question is asked about each distribution, and the probability of making a mistake decreases with the total information gathered on that distribution solely. The typical question the algorithm must answer is “is the mean of the distribution above or below some threshold?" (say, 0, for simplicity); giving the wrong answer can either incur a unit cost - independently from the distribution -, or a data-dependent cost (say, the distance to the threshold that represents the “risk” of that distribution). A typical application of thresholding bandits is crowdsourcing [7] where the
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
objective is to distinguish workers with positive (vs. negative) efficiency; another one is bandit binary classification [18].
Some care must be taken when designing a performance criterion for a thresholding bandit problem, since any non-stupid algorithm will eventually answer all questions correctly (hence have a 0 loss) if it has enough samples. Furthermore, if distributions are sub-Gaussian (a rather mild assumption that we are going to make), the probability of making a single mistake decreases exponentially fast with the number of samples. As a consequence, the focus must be on controlling the exponential decay constant. We illustrate that issue on the unit cost problem described as follows. There are K different σ-sub-Gaussian distributions; the mean of distribution k is denoted by µk and the (variancenormalized) gap of distribution k to the threshold 0 is denoted by ∆k := |µk|/ √ 2σ2. The algorithm has a budget of T samples to (sequentially) allocate to those distributions and, based on the Nk,T samples of distribution k, it must decide the sign of µk; any mistake has a cost of one. We denote by Ek ∈ {0, 1} an indicator of a wrong sign prediction of µk after exhausting the budget of T samples. The loss is then L1T := ∑ k Ek. It is not difficult to see that the expected number of mistakes could
be of order ∑K k=1 exp(−Nk,T∆2k) .
In particular, sampling evenly across distributions (Nk,T = T/K) gives E[L1T ] ≈ ∑ k exp(− T K∆ 2 k), which has an exponential decay in T . However, this uniform allocation is far from being optimal in term of the exponential decay constant. Computing an (approximate) optimal fixed allocation in hindsight is not difficult: just optimize the upper-bound of E[L1T ]. Since even the uniform allocation has a loss decaying exponentially, the performance of an algorithm should be measured not with respect to E[L1T ] (see [24]) but rather in terms of − log(E[L1T ])/T . The oracle that uses knowledge of the gaps ∆k to optimize its fixed allocation verifies
lim sup T→∞
1 T log(E[L1T ]) ≤ − 1∑ k 1/∆ 2 k .
This unit cost framework has been investigated recently [35] with a simple yet effective algorithm called LSA (Logarithmic-Sample Algorithm) designed exclusively for this problem; it samples the distribution with the smallest current index defined as αNk,t∆̂2k,t + logNk,t, where ∆̂k,t is the empirical estimate of ∆k and α is some parameter to be chosen. LSA is "optimal up to a constant", but the constant is unfortunately in the exponential decay, as it was proved that1
lim sup T→∞
1 T log(E[L1T ]) ≤ − 1 16020 1∑ k 1/∆ 2 k for LSA.
As we shall see, this result can be drastically improved with our more refined and general analysis (that implies choosing a totally different input parameter α = 1 instead of 1/10 as suggested originally).

heading: 1.1 Contributions
text: We investigate the thresholding bandit problem with a weighted number of errors loss. Our contributions are twofold: 1) a generic method to design algorithms, with a generic proof, showing good performance on the weighted number of errors loss. 2) new lower-bounds and counter-intuitive results for the unit cost problem.
A generic algorithm with performance guarantees We propose a Frank-Wolfe inspired method to design bandit algorithms. We develop a proof technique to obtain loss bounds for the type of algorithms that our method produces, which we apply to the thresholding bandit with losses
LT = K∑ k=1 akEk or L∆T = K∑ k=1 ∆kEk , (1)
where (ak)k∈[K] are known costs. The class of algorithms we analyze includes both LSA and APT (Anytime Parameter-free Thresholding) [35, 28]. We obtain precise non-asymptotic loss bounds for E[LT ]; for instance, we improve the original bound of LSA by a factor 4005 (and APT by a factor 8). More importantly, we get a new algorithm whose expected error for the unit cost problem is within a
1See Remark 1 [35]. This bound implies that LSA - with the specified choice of α = 0.1 needs 16000 times more samples than the oracle to achieve the same performances.
factor 4 of the oracle. We emphasize again than those “constant” factors are in the exponential (and are not mere multiplicative constants).
Interestingly, this class of algorithms are not driven either by the “optimism under uncertainty” principle, a standard technique in multi-armed bandit [4] nor “Explore-then-commit / Successive Elimination” [31, 12].
New insights on the thresholding bandit problem First, the optimal allocation provided by the oracle of [35] in the unit cost problem has a M-shape (see Figure 1) because of two concurrent phenomena. On the one hand, the arms close to the threshold should not be pulled too much because their sign is difficult (if not impossible) to identify and it is a waste of budget. On the other hand, the signs of the arms far from the threshold are quickly well estimated and therefore should not be chosen too often either. The middle arms are the ones that need to be pulled the most frequently. As T gets larger, more and more budget is allocated to difficult arms. In section 2.2, we provide a lower-bound that shows that this M shape is actually impossible to achieve for a sequential algorithm. Typically, the hollow inside of the M shape corresponds to arms whose sign cannot be well-estimated. In particular, it is not possible to distinguish arms that are very close to the threshold from the arms that are at the top of the M and should be pulled the most frequently according to the oracle.
Our second insight is corroborated by numerical simulations in Section 4. We show empirically that our algorithms not only match but also surpass the optimal non-adaptive sampling of the oracle. We conjecture that our algorithms take advantage of the chance due to noise that can move its estimate of the arm away from the threshold. In particular, when all the gaps ∆k are equal, the non-adaptive optimal allocation should be uniform, which is significantly outperformed by adaptive algorithms. This suggests that adaptivity is crucial for this problem and may inspire future research directions to the multi-armed bandit community in order to prove theoretical guarantees for such phenomena.

heading: 1.2 Additional related work
text: Zero-one loss Most of the literature on thresholding bandits [28, 30, 8] aims at minimizing the probability of making any sign error, i.e., minimizing the loss
L∗T = I{∃k ∈ [K], Ek = 1} = max k Ek. (2)
We already mentioned the algorithm APT [28], that gets an exponential decay of that loss (variants include variance estimation [36] and/or delayed feedbacks). Other algorithms exist, but based on the optimism principle [23, 30]. Unfortunately they suffer from a degraded exponential decay constant (by a factor bigger than 1000).
Another part of the literature focuses on the fixed confidence framework, where the objective is to answer some questions with some fixed probability of mistake (and obviously with a minimal sample budget). For instance, an objective could be to return any arm above some threshold as soon as possible [21, 9], or the one closest to the threshold [16], or just identifying that one arm is above that threshold [25], or even to control false discovery rates and variants [19, 18].
Global loss, dynamic allocation and outliers detection The loss considered in thresholding bandits can be seen as a variant of a “global loss” (i.e., essentially non-linear) that has been extensively studied in the bandit literature [1, 2, 29]. However, the major difference is, again, that the optimal allocation is time dependent and that the loss converges exponentially fast to zero (no matter the algorithm). Similarly, Frank Wolfe algorithms have been introduced in this setting [5, 13]; even though our algorithms share some similarities, they are intrinsically different for the same reasons.
Similarly, the problem investigated could be seen as a special case of bandit resource allocations [26, 7, 32, 11, 14] but where the loss is always decreasing with respect to the budget allocated per resource (hence again leading to a zero loss exponentially fast).
Finally the global objective of thresholding bandits is to obtain a synthetic view of how the means of distributions are spread on the real line (which ones are above/below some threshold). In that aspect, this problem sheds some similarities with outlier detection in multi-armed bandits [22, 38, 37].

heading: 2 Preliminaries
text: We describe here the weighted number of errors setting, in which an error on arm k has a known cost ak > 0. The sum-of-gaps setting will be briefly investigated in section 3.3. The environment is composed of K > 1 arms and an algorithm sequentially pulls them. After pulling arm k ∈ [K], it observes a sample from a distribution νk with mean µk, and that sample is independent of past observations. The distribution νk is supposed σ-sub-Gaussian, that is
∀λ ∈ R : EX∼νk [exp(λ(X − µk))] ≤ exp(σ2λ2/2) . The total number of rounds (and samples) T is known in advance and called the horizon. After pulling T arms, the task of the algorithm is to classify the arms depending on whether µk > θ or not, where θ is a known threshold that we conveniently set to 0 (although it could be any other value, even different from arm to arm, without significant change to the analysis). Let sk ∈ {−1, 1} be the sign of µk − θ, equal to 1 iff µk − θ > 0. The algorithm returns for all arms an estimated sign ŝk ∈ {−1, 1}. The objective is to minimize the expected weighted number of missclassified arms, where a mistake on arm k has a known cost ak > 0,
LT = K∑ k=1 akI{ŝk 6= sk} = K∑ k=1 akEk . (3)
Note that the linear form of the loss is quite general: sinceEk ∈ {0, 1}, any separable loss ∑ k fk(Ek)
is the sum of a constant and ∑ k akEk for some costs ak.
We conclude this description of the problem with notations used in the design of algorithms. Let Nk,t and µ̂k,t = 1Nk,t ∑t s=1 I{it = k}Xt be the number of times the learner has pulled arm k up to round t (included) and the subsequent empirical mean of arm k repectively. Define further ∆̂k,t = |µ̂k,t−θ|/ √ 2σ2 and ∆k = |µk−θ|/ √ 2σ2, respectively the empirical and the true (variancenormalized) gap of arm k to the threshold after t rounds.

heading: 2.1 The benchmarks: a lower bound and a non-adaptive oracle
text: Following the proof of [35] in a slightly more generic fashion (using exponential families with one parameter instead of Bernoulli distribution), we obtain a lower bound on the performance of any algorithm (see appendix A) from which we get Theorem 1. Theorem 1. (Similar to Theorem 20 in [35]) Let (∆1, . . . ,∆K) be a sequence of gaps. Then for any algorithm and time horizon T ≥ K, there exists an instance in which all arms k ∈ [K] have Gaussian distributions with variance σ2 and mean in {∆k,−∆k} such that
E[LT ] ≥ 1 4 min∑ k Nk=T K∑ k=1 ake −4Nk∆2k .
We now deriving an optimal but unrealistic oracle, which requires prior knowledge of the gaps as input. Consider the algorithm that pulls each arm Nk,T times, a number fixed in advance, then returns the sign of the empirical mean µ̂k,T . Using Hoeffding’s inequality, the expected loss verifies:
E[LT ] = K∑ k=1 akP ((µ̂k,T − θ)(µk − θ) < 0) ≤ K∑ k=1 ake −Nk,T∆2k (4)
We define the non-adaptive oracle as the allocation NT which minimizes that upper bound. Its error probability has the same form as the lower bound of Theorem 1, but has a different constant in the exponential (1 instead of 4). We can solve that minimization problem and make the error bound more explicit. To that end, suppose that the arms are ordered such that a1∆21 ≤ . . . ≤ aK∆2K . There is a set S = {k0, k0 + 1, . . . ,K} and a constant CS such that the oracle non-adaptive algorithm has Nk,T = 0 for k /∈ S and Nk,T = ( CS + log(ak∆ 2 k) ) /∆2k for k ∈ S (see appendix B for details). The expected loss of that non-adaptive oracle is
E[LT ] ≤ ∑ k/∈S ak + ∑ k∈S ak exp
−T +∑j∈S 1∆2j log ( ak∆ 2 k aj∆2j ) ∑ j∈S
1 ∆2j
 . (5)
The oracle is not pulling arms 1, . . . , k0 − 1. These are the arms which are too close to the threshold (in a distance weighted by ak) and thus too hard to classify to be worth trying. Giving up on those arms is not something that a non-oracle algorithm can do. Figure 1 illustrates on an example (µk = (−1)k(k/K)2, k = 1, . . . , 50, and T = 500) the shape of the optimal allocation (arms near the threshold should not be drawn) as well as the empirical sampling distributions of several algorithms that pull all arms. In Appendix G, we illustrate how this optimal allocation evolves with the horizon T .

heading: 2.2 A good algorithm must pull all arms
text: We provide a new lower bound for the thresholding bandit with unit-cost problem, to support the claim that it is not possible to avoid pulling the arms which are close to the threshold. Consider the following 4 Gaussian bandit models (with variances 1) with means
µ+ε = (ε, . . . , ε, µK0+1, . . . , µK) , µ ′ + = (µK0+1, . . . , µK0+1, µK0+1, . . . , µK) ,
µ−ε = (−ε, . . . ,−ε, µK0+1, . . . , µK) , µ′− = (−µK0+1, . . . ,−µK0+1, µK0+1, . . . , µK) . where 0 < ε < µK0+1 ≤ . . . ≤ µK , the value µK0+1 is large enough for the oracle to pull all arms on µ′+ and ε ≤ √ log(2)/(2T ). Lemma 1. If Eµ̃[LT ] ≤ c1 min∑ k Nk=T ∑ k e−c0Nk∆ 2 k for constants c0, c1 on µ̃ ∈ {µ′+, µ′−}, then
max µ∈{µ+ε,µ−ε}
Eµ [ K0∑ k=1 Nk,T ] ≥ 1 2(µK0+1 − ε)2 ( c0 T +H log H + log K0 32c1H ) .
where H = K0 ∆2K0+1
+ ∑K k=K0+1 1 ∆2k and H log = K0 ∆2K0+1 log 1 ∆2K0+1 + ∑K k=K0+1 1 ∆2k log 1 ∆2k .
The proof is postponed to Appendix A. In a few words, if an algorithm has an expected loss close to the loss of the non-adaptive oracle, then it must pull linearly the arms which are close to the threshold.

heading: 3 Algorithm and upper-bound
text: We introduce and analyse a new class of algorithms for the thresholding bandit problem that we call index-based algorithms. That class unifies several existing algorithms, including APT [28] and LSA [35]. An index-based algorithm pulls the minimum of K quantities, one for each arm, that each depends only on the rewards and pull counts of the respective arm (it does not change when pulling other arms). In particular, we consider algorithms for which the sampled arm is it+1 ∈ arg mink∈[K] F ( Nk,t, Nk,t∆̂ 2 k,t; ak ) for a function F : N× R+ × R∗+ → R that depends on the pull counts, the information about the sign and the weight of the arm.
After T rounds, the algorithm recommends the sign of the arms at the round tmax ∈ [T ] at which mink∈[K] F ( Nk,t, Nk,t∆̂ 2 k,t; ak ) was maximal. This rule is used as opposed to returning the sign of all arms at time T to facilitate the analysis, which is based on the observation that there is a small probability of error when all arms have high index. The time tmax should be close to T : in particular, only one arm is sampled (possibly several times) between tmax and T (see Appendix C). In Sec. 3.2, we provide a generic analysis for index-based algorithms satisfying the assumption below. Assumption 1. The index function F (n, x; a) : N× R+ × R∗+ → R is non-decreasing in n and x and limn→+∞ F (n, ny; a) = +∞ for all y > 0, a > 0.
Intuitively, algorithms that verify Assumption 1 prefer pulling arms that were pulled the least (smallest n) and whose quantity of information about the sign (n∆̂2k,n) is small. This class includes several algorithms from the thresholding bandits literature: APT [28] for F (n, x; ak) = x and LSA [35] for F (n, x; ak) = x+ log(n) (these algorithms are only defined for ak = 1). We now propose a generic method for designing an index-based algorithm.
Algorithm 1 Index-based algorithm for thresholding bandit Inputs: an index function F : N× R+ × R∗+ → R; a1, . . . , aK ∈ R∗+; σ > 0; and θ ∈ R For t = 1, . . . , T do
- for all k ∈ [K] define
Nk,t−1 = t−1∑ s=1 I{k = is}, µ̂k,t−1 = 1 Nk,t−1 t−1∑ s=1 I{k = is}Xs, and ∆̂2k,t−1 = 1 2σ2 ( µ̂k,t−1−θ )2 - pull it ∈ arg mink∈[K] F ( Nk,t−1, Nk,t−1∆̂ 2 k,t−1; ak ) .
- observe Xt ∼ νit Define tmax = maxt∈[T ] mink∈[K] F ( Nk,t, Nk,t∆̂ 2 k,t; ak ) Return for each k ∈ [K] the sign ŝk = sign(µ̂k,tmax − θ)

heading: 3.1 Frank-Wolfe for Thresholding bandits
text: Our strategy to minimize the expected loss is inspired by the Frank-Wolfe algorithm [15] and aims at controlling an upper-bound on the loss, such as the right hand side of Inequality (4). Let’s write that function as B(NT ) = ∑K k=1 ake
−Nk,T∆2k . The high-level idea is to sequentially estimate its gradient and move to the minimizer of its linear approximation. If the gaps were known, we could compute at time t+ 1 the gradient of the bound with respect to Nt,∇B(Nt) = (−ak∆2ke−Nk,t∆ 2 k)k and use the Frank-Wolfe algorithm. The algorithm would pull it+1 ∈ arg minu u>∇B(Nt) for u in the simplex, which is simply arg mink∈[K](−ak∆2ke−Nk,t∆ 2 k). The gaps are however unknown. We therefore compute an estimate of the gaps ∆̂k,t, with which we form the estimated gradient
∇̂B(Nt)k = −ak∆̂2ke−Nk,t∆̂ 2 k,t = − exp ( − ( Nk,t∆̂ 2 k,t − log(Nk,t∆̂2k,t) + log (Nk,t ak ))) .
This gives a natural choice for the index function of our algorithm F (n, x; ak) = x − log x + log(n/ak). However, the latter is decreasing in x for x ∈ (0, 1), which in addition to violating Assumption 1, may lead to instability in the initial phase when the gaps ∆k are poorly estimated by ∆̂k,n. We therefore propose a slight modification that preserves the asymptotic behavior of F and we call the resulting algorithm FWT (Frank-Wolfe for Thresholding bandits):
F (n, x; ak) = max{x, 1} − log(max{x, 1}) + log(n/ak) . (FWT)
Recovering APT Using different upper-bounds B on the expected loss may lead to different algorithms. In particular, we highlight a link between our Frank-Wolfe inspired method and the APT algorithm of [28], which was designed to minimize the loss
LT = K∑ k=1 akI{ŝk 6= sk} = K∑ k=1 akEk .
Following our method with the choice B(Nt) = maxk∈[K] e−Nk,t∆ 2 k results in exactly the same sampling rule as the one of the APT algorithm (the recommendation rule differs slightly since we recommend the sign at tmax and not at T ). Indeed, the derivative of B with respect to Nk,t is nonzero (and negative) if and only if Nk,t∆2k = arg minj Nj,t∆ 2 j (ignoring the case in which there are several argmins, for which the tie breaking can be arbitrary). This leads to the choice F (n, x; ak) = x in Algorithm 1, which then pulls it+1 = arg mink∈[K]Nk,t∆̂ 2 k. This is the sampling rule of APT.

heading: 3.2 Loss upper bound
text: We provide a loss upper bound that is valid for all index-based algorithms that verify Assumption 1. We then give a compact summary of the analysis outline and the resulting loss bounds.
Theorem 2. Let K ≥ 1, a1, . . . , aK > 0, T ≥ 1, and σ > 0. Let F : N × R × R∗+ → R that satisfies Assumption 1. Let C1, . . . , CK > maxk F (0, 0; ak). For all j, k ∈ [K], define
• tj(Ck) a solution of the equation F (t, t∆2j ; aj) = Ck, • Sk ⊆ [K] and tj,0(Ck) ∈ R+, a set and values such that for i /∈ Sk, P ( ∃n ≤ ti,0(Ck), F (n, n∆̂2n,i; ai) ≥ Ck ) = 1.
Then the expected loss of Algorithm 1 is upper-bounded as
E[LAT ] ≤ K∑ k=1 ak
e · exp − 12 ( T − ∑ j /∈Sk tj,0(Ck) ) − ∑ j∈Sk tj(Ck)∑
j∈Sk 1/∆ 2 j
+ T · e−tk(Ck)∆2k  .
Refer to Appendix D for the proof. It is composed of two parts:
1. First we establish that for any arm j ∈ [K], with large probability, there is a time τj(Ck) such that F (τj(Ck), τj(Ck)∆̂τj(Ck),j ; aj) ≥ Ck. We prove that for all j, k ∈ [K], τj(Ck) has an exponential tail then use the fact that the algorithm pulls the minimal index to control the probability that the minimum never reaches Ck.
2. We show that if an arm’s index is large, then the probability of mistake on it is small.
The times tj(Ck) of Theorem 2 are the smallest numbers of samples such that tj(Ck) ≥ τj(Ck) with high enough probability. By determining those times, we derive explicit bounds for algorithms that verify Assumption 1. In particular we derive a bound for the variant of APT which returns the sign at the time tmax when the minimal index was maximal.
Corollary 1. Suppose that for all k ∈ [K], ak = 1. For all T ∈ N∗,
E[LAPTT ] ≤ 2K √ e · T · exp ( −1
4 T∑K j=1 1/∆ 2 j
) .
Refer to Appendix D.3 for the proof. Since maxk Ek ≤ ∑ k Ek, the bound of Corollary 1 is also a bound on the zero-one loss, which we can compare to the result of [28]. Our result shows a 1/4 factor in the exponential instead of the worse 1/32 constant of the original paper.
LSA and FWT Theorem 2 applies to LSA and FWT with the following times:
• LSA: tj(Ck) = W (eCk∆2j )/∆ 2 j and tj,0(Ck) = e Ck , • FWT: tj(Ck) = log(eCkaj∆2j )/∆ 2 j and tj,0(Ck) = aje Ck−1 ,
where W is the Lambert W function, which verifies |W (x) − (log x − log log x)| ≤ log(1 + 1/e) for x ≥ e. Therefore, for the two algorithms, the times tj(Ck) are close (equal up to the log log terms in W ), thus their bounds are close as well. Note that LSA is only defined for aj = 1 for all j. In contrast to LSA, our bound for FWT has the notable property that, in the regime where
T ≥ 2 ∑K j=1
1 ∆2j
(2 + log aj∆
2 j maxi ai∆ 2 i
(mink ak∆2k) 2 − log Te ), we recover the same exponent as in the non-
adaptive oracle loss bound (5) (up to a factor 1/4). Indeed we show that for such T
E[LFWTT ] ≤ 2 √ eT K∑ k=1 ak exp −1 4 T + 2 ∑K j=1 1 ∆2j log ak∆ 2 k aj∆2j∑K j=1 1/∆ 2 j  . (6) In the same regime of large T , the bound that we obtain for LSA is of the same order, but less explicit due to the function W . The latter is still impressive since the original theorem of [35] for LSA
exhibits an exponent significantly looser, of order exp ( − 116020 T∑K j=1 1/∆ 2 j ) , i.e. 4005-times worse than our bound. We finally derive a bound for our newly introduced algorithm.
Corollary 2. Let S, S′ be two sets with S′ ⊆ S ⊆ [K] and let C ∈ R be such that C ≥ 1 + max k∈S log 1 ak∆2k . Then, for all T ≥ 1
E[LFWTT ] ≤ ∑ k/∈S′ ak + e ∑ k∈S′ ak exp − 12 (T −∑j /∈S ajeC−1) +∑j∈S 1∆2j log 1aj∆2j∑ j∈S 1/∆ 2 j + C  + T
∑ k∈S′ ak exp ( −C + log(1/(ak∆2k)) ) .
Figure 2 compares the upper-bounds of Corollary 1 (APT), Theorem 2 (see also Equation (9) in the Appendix) (LSA), and Corollary 2 (FWT) for the particular case ∆i = (i/K)2 and ai = 1, for i = 1, . . . ,K = 50. See also Figure 4 in the supplementary material for ∆i = i/K. We can see that while the bounds of LSA, APT, and FWT are asymptotically similar, that of FWT starts to be significant for much smaller T . On the right, we can see the importance of the set S′ in Corollary 2: the bounds first ignores all the arms, and suffers a loss of 1 and then adds them one by one as soon as they can be classified. The bound derived in [35] for LSA is not represented on the figures, since it is still bigger than K for the considered range of T .

heading: 3.3 The sum-of-gaps objective
text: We show that our method applies for the sum-of-gaps objective ∑K k=1 ∆kEk. This is not a particular case of the setting discussed previously since ak was known to the algorithm, while ∆k is unknown. It serves as a proof of concept for the extensibility of our method. The index given by FWT in this setting is F (n, x) = x′ − 32 log (x ′) + 32 log (n), where x ′ = max ( x, 32 ) . We can then bound the sum-of-gaps loss using our generic analysis by proceeding similarly to Theorem (2). Corollary 3. (FWT for the sum-of-gaps objective) In the regime where T ≥ 2 ∑k j=1
1 ∆2j
( 3 + 3 log
∆j maxi ∆i (mini ∆i)2 − log Te ) , we show that
E[ K∑ k=1 ∆kEk] ≤ 2 √ eT ∑ k ∆k exp −1 2 T 2 + ∑ j 3 2 1 ∆2j log ∆2k ∆2j∑ j 1/∆ 2 j  . See Appendix E for the proof and for a different bound that is valid for all times T . This can be useful for applications in which errors are more tolerated for arms that are close to the threshold.

heading: 4 Beating the oracle? The benefits of adaptivity.
text: We argue that in some situations adaptive algorithms can greatly outperform the non-adaptive oracle of Section 2.1, i.e., the cost of non-adaptivity can be much higher than the cost of learning. The algorithms in the family we considered are all adaptive in the sense that they adapt their drawing strategy as more information is observed, at the cost of learning the parameter µk. We illustrate the benefits of adaptivity in the following toy example.
The “optimal” non-adaptive algorithm may be worse than adaptive algorithms. Consider the following parametric problem. An arm distribution is parametrized by x ∈ R and is supported on {0, x}; a sample of that distribution is equal to 0 or x, each with probability 1/2. We assume that all arms have non-zero parameter and we will compute the optimal non-adaptive allocation.
We make the convention that if an algorithm sees only zeros for one arm, it returns any sign with probability 1/2. The error probability of a non-adaptive allocation NkT for arm k is half of the probability of seeing only zeros (since if anything else is observed, the arm can be classified with perfect accuracy). Hence the total error is
E [ LT ] = 1
2 K∑ k=1 1 2Nk,T ≥ K 2(T/K)+1 ,
which is minimized with the uniform allocation: Nk,T = TK for all k ∈ [K]. Consider now an adaptive procedure that sample each arm in turn, but stops sampling an arm as soon at it sees a non-zero value. We crudely prove an upper bound for its number of errors, by remarking that it is zero if the algorithm classifies all arms correctly and smaller than K otherwise. The number of samples required to perfectly classify an arm follows a geometric distribution with parameter 1/2. As a consequence, the number of required samples to classify all arms correctly follows a negative binomial NB(K, 1/2). Let Z be such a negative binomial random variable. The expected number of errors of the adaptive procedure is up to KP(Z > T ). It then verifies
E [ LT ] ≤ KP(Z > T ) ≤ Ke−(log(2)/2)TEe(log(2)/2)Z = K
2T/2
( 1 +
1√ 2
)K ,
where the value log(2)/2 is chosen for simplicity (in [0, log 2)). In the regime where T is large, this is of order 1/2T/2, which for K > 2 is much smaller than 1/2T/K for the uniform allocation.
This toy example differs drastically from more realistic situations, as one non-zero sample for an arm is sufficient to know the sign of the expectation perfectly. We therefore consider empirically more reasonable frameworks, closer to those analyzed in the paper: the distributions of K arms are either N (1, 1) or N (−1, 1). Since all gaps ∆i are equal, the optimal non-adaptive oracle is also the uniform sampling. The results are illustrated on the left part of Figure 3 and highlight the fact that all the adaptive algorithms considered (APT, LSA or FWT) drastically outperform the oracle. The right part of the figure shows the same phenomenon on another example in which the gaps are not constant. In particular, we can see that FWT and LSA have similar performance while APT (not designed for this purpose) generally suffers from a larger error. This result was corroborated by most of our experiments. We refer to Appendix G for more details.
Discussion
An interesting research direction is to consider objective functions more general than (1). In particular, we believe that our approach can be generalized to losses of the form LT = ∑K k=1 f(∆k, Ek) under certain regularity assumptions on f . Moreover, we focused on separable losses (hence linear wlog) and the index based algorithms we analyze reflect that separability. An obvious and intriguing direction for further work is to replace that assumption. One might for example want to design an algorithm that minimizes the probability of making more than a given number of mistakes.
The fact that adaptive algorithms can beat non-adaptive oracles has already been observed empirically for fixed confidence identification [33, 10], although only in cases where the non-adaptive oracle was worse only for small times and was still asymptotically optimal. The phenomenon we observe for fixed budget thresholding is much more significant and remains to be explained by theoretical arguments. Currently, the best theoretical bound for adaptive algorithms is still a factor 1/4 away in the exponent from the non-adaptive oracle bound.
Acknowledgments and Disclosure of Funding
V. Perchet acknowledges support from the French National Research Agency (ANR) under grant number #ANR-19-CE23-0026 as well as the support grant, as well as from the grant “Investissements d’Avenir” (LabEx Ecodec/ANR-11-LABX-0047)". R. Ouhamma also awknowledges support from Ecole polytechnique under the AMX funding. P. Gaillard and R. Degenne were supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d’avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute).

Review summaries:
This paper works on the problem of fixed-budget sign identification problem in stochastic bandits. Given a set of arms where each sample on an arm returns a noisy result according to this arm's unknown latent distribution, a threshold, and the limited time horizon $T$, the learner needs to adaptively sample the arms and wants to minimize the error probability of determining whether the mean rewards of the arms are above or below the threshold.   The authors did a thorough and careful analysis on the performance of a large class of algorithms as well as the lower bound of this problem. By the analysis, the authors managed to get a gap 4 in the exponential part of the upper bound and the lower bound of the error probability, outperforming the existing results.   The results in this paper help the researchers to understand the problem of online fixed-budget sign identification problem, and the new bounds are promising both in theory and in practice.

This paper studies the thresholding bandit problem with the goal which can be seen as a weighted version of aggregate regret. The main contributions of this paper are two-fold:  1. It introduces an algorithm that is inspired by the Frank-Wolfe algorithm regarding this generic goal. A corresponding upper bound is derived regarding this algorithm. 2. This paper discovers new insights on the thresholding bandit problem i.e., a good algorithm must pull all arms and the “optimal” non-adaptive algorithm may be worse than adaptive algorithms.  After rebuttal -------------------- The rebuttal looks good to me and I will keep my positive score.

The authors come up with a general way to analyze algorithms that solve the thresholded bandit problem. Given any function that trades-off less sampled arms and those close to the threshold. They show that some existing algorithms fit their framework (LSA and APT). They give new lower bounds and show that their adaptive algorithm outperforms a non-adaptive oracle that is aware of all the gaps.   Their main contributions are: -  a new proof technique for thresholded bandits - new upper and lower bounds - proof that the adaptive method can beat a non-adaptive oracle in some cases