Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits
Authors: Reda Ouhamma
Rémy Degenne
Pierre Gaillard
Vianney Perchet
Venue:  (2021)
Keywords: Multi-armed bandit
thresholding bandits

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.

Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits
Reda Ouhamma
Rémy Degenne Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL,
Univ. Lille, Inria, CNRS,
Centrale Lille, UMR 9189 CRISIAL,
F-59000 Lille, France
F-59000 Lille, France remy wet...deeneeiniia...rm
reda. ouhhamm@maml com
Pierre Gaillard
Vianney Perchet
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France pierre. www.larddiniia......mm
Crest, Ensae & Criteo Al Lab vi vianney.o pewchett@nomallesup org
Abstract
the fixed budget thresholding bandit problem, an algorithm sequentially allocates 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 large family of algorithms (containing most existing relevant ones), inspired by the Frank- Wolfe algorithm, and provide a thorough yet generic analysis their performance. This allowed us construct new explicit algorithms, for broad class of problems, whose losses are within a small constant factor the non-adaptive oracle ones. Quite interestingly, empirically greatly out-perform non-adaptive oracles, an uncommon behavior standard online learning settings, such as regret minimization. We explain this surprising phenomenon on an insightful toy problem.
observed that adaptive methods
Introduction and related work
In a stochastic multi-armed bandit problem, decision maker sequentially samples from different distributions in order optimize loss that depends on the unknown parameters of those distributions. As consequence, a tradeoff arises between gathering more samples from any possible distribution (to enhance the estimation of relevant parameters) and optimizing the allocation minimize the final loss. We can distinguish two main categories losses, focusing on "exploitation" vs "exploration" The former directly depends the whole allocation of samples and the typical example is regret min- imization (we refer to the recent monographs (7 6 34 that cover this setting almost exhaustively). The later is bit different; after the budget of samples is exhausted, the algorithms must answer 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 24
The key property of this class is that a question is asked about each distribution, and the probability of making 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, O, for simplicity); giving the wrong answer can either incur a unit cost independently from the distribution data-dependent cost (say, the distance the threshold that represents the "risk" of that distribution). A typical application of thresholding bandits crowdsourcing [7] where the
We investigate a class of pure exploration problems, called "thresholding bandit" 28 35
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

objective is to distinguish workers with positive (vs. negative) efficiency; another one is bandit binary classification [88]
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 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 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 a o-sub- Gaussian distributions; the mean of distribution k is denoted by μæ and the (variance- normalized) gap of distribution l: to the threshold 0 is denoted by A == | 2v22. The algorithm has budget of samples to (sequentially) allocate to those distributions and, based on the N&.r samples of distribution k. it must decide the sign of μgg any mistake has cost of one. We denote by EN E {0, } an indicator a wrong sign prediction of μts after exhausting the budget of T samples. The loss is then L7 = >x Ex. It is not difficult to see that the expected number of mistakes could be of order Σx= exp( Sepp-NNk.1 A..
In particular, sampling evenly across distributions (Ne,r T) gives E[L4] R= x which has an exponential decay in T. However, this uniform allocation is far from being optimal term of the exponential decay constant. Computing an (approximate) optimal fixed allocation in hindsight is not difficult: just optimize the upper-bound of E. [.4]) Since even the uniform allocation has loss decaying exponentially, the performance of an algorithm should measured not with respect to E [.p. (see (24)) but rather in terms of log (1,])//T The oracle that uses knowledge of the gaps A to optimize its fixed allocation verifies
1 lim sup log (B(L))) S T-+00 T
Σx 1/4
This unit cost framework has been investigated recently B51 with a simple yet effective algorithm called LSA (Logarihmmi--ampple Algorithm) designed exclusively for this problem; samples the distribution with the smallest current index defined as a.V,, A + log NN,,, where Âg, is the empirical estimate of A& and a is some parameter be chosen. LSA is "optimal up constant", but the constant is unfortunately in the exponential decay, as it was proved that"
1
lim lum log (B([+) 16020 Σ. 1/ for LSA. T-200 T
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 a = instead of 1/10 as suggested originally).
1.1 Contributions
We investigate the thresholding bandit problem with weighted number of errors loss. Our con- tributions are twofold: 1) a generic method 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 Frank-Wole inspired method to design bandit algorithms. We develop proof technique to obtain loss bounds for the type of algorithms that our method produces, which we apply to the thresholding bandit with losses
K
LT
ag E
Or
L
A E
(1)
1=1
where (a*)ke[k) are known costs. The class of algorithms analyze includes both LSA and APT (Anytime Parameter-free Thresholding) 355 28 We obtain precise non-asymptotic loss bounds for E[Lr]; for instance, improve the original bound of LSA by factor 4005 (and APT by factor 8). More importantly, we get a new algorithm whose expected error for the unit cost problem is within a
'See Remark 1 (35 This bound implies that LSA with the specified choice of a 0.1 needs 16000 times 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 multiplicatiie constants).
Interestingly, this class of algorithms are not driven either by the "optimism under uncertainty" principle, standard technique in multi-armed bandit nor "Explore-then-commit Successive
Elimination" 31
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 [ 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 difficult arms. In section 2.2 provide 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 the oracle.
Our second insight is corroborated by numerical simulations in Section 4 We show empirically that algorithms not only match but also surpass the optimal 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 As 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.
1.2 Additional related work
Zero-one loss Most of the literature on thresholding bandits
28 30
g
aims at minimizing the
probability of making any sign error, i.e., minimizing the loss
LJ 1(3k [K], Eg 1 max Es.
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 variant of "global loss" (i.e., essentially non-linear) that has been extensively studied in the bandit literature D 2 (29]. However, the major difference is, again, that the optimal allocation 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] [3]; 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 [4] but where the loss is always decreasing with respect to the budget allocated per resource (hence again leading to a zero loss exponentially fast).
26 7 32
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/helow some threshold). In that aspect, this problem sheds some similarities with outlier detection in multi-armed bandits [2 38 37].
3

---

2 Preliminaries
We describe here the weighted number of errors setting, in which error arm & has known cost 0Ą > O. The sum-of-gape setting will be briefly investigated in section The environment is composed of K > arms and algorithm sequentially pulls them. After pulling arm k [K], it observes a sample from a distribution Pa with mean μk, and that sample is independent of past observations. The distribution Vi is supposed o-sub-Gaussian, that is
AA E R Ex-rx [exp(A(X pa))] S exp(o²X2/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 μıs > 8 or not, where 9 is known threshold that we conveniently set to 0 (although it could be any other value, even different from arm to arm, without significant change the analysis). Let 83 E ff-1, 13 be the sign of μa 0, equal to I iff Ma 0 > O. The algorithm returns for all arms an estimated sign &g E (-1,1). The objective to minimize the expected weighted number of missclassified arms, where a mistake on arm & has known cost ag 0,
K
K Σ Ex k=1
LT
axlll&x + 8k) k=1
(3)
Note that the linear form of the loss is quite general: since Eş E (0,1), ) any separable loss Σx (Ex) the sum of a constant and Σx ag Es, for some costs aş.
We conclude this description of the problem with notations used in the design of algorithms. Let Ng. and fixtt - Σ I(i k) be the number of times the learner has pulled arm k up to round (included) and the subsequent empirical mean of arm repectively. Define further Â = L 0 // /202 and A4 = luK -ils--l/a /1/ /22?, respectively the empirical and the true (variance- normalized) gap of arm i to the threshold after t rounds.
2.1 The benchmarks: a lower bound and a non-adaptive oracle
Following the proof of (35] in slightly more generic fashion (using exponential families with one parameter instead of Bernoulli distribution), we obtain a lower bound on the performance any algorithm (see appendix A from which get Theorem
Theorem 1. (Similar to Theorem 20 in (35)) Let (Ai...., AK) be a sequence of gaps. Then for any algorithm and time horizon T 2 K, there exists instance in which all arms k [K] have Gaussian distributions with variance o² and mean in {As, -Ax} such that
E LT
1
min
age 1N24
4
N
k=1
We now deriving an optimal but unrealistic oracle, which requires prior knowledge of the gaps as input. Consider the algorithm that pulls each arm NE.T times, number fixed in advance, then returns the sign of the empirical mean jK,T. Using Hoeffding's 's inequality, the expected loss verifies:
K
E L a&P (( (p 0) < 0)
Σ
oRE Nu
(4)
We define the non-adaptive oracle as the allocation Ny which minimizes that upper bound. Its error probability has the same form the lower bound of Theorem I 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 o, a < ... S ax ax A There is set S = (ko. ko + 1,.... K} and constant Cs such that the oracle non-adaptive algorithm has NE,T 0 for k & S and NA.T = (Cs- + log(a, / / for E S (see appendix B for details). The expected loss of that non-adaptive oracle
T EAES A7 log
LTL <
Σ a4 +
Σ KES
aj exp
1 Ejes
(5)
kØS

---

The oracle is not pulling arms 1..... Ko - 1. These are the arms which are too close to the threshold (in distance weighted by ag) and thus too hard to classify to be worth trying. Giving up on those arms not something that a non-oracle algorithm can do. Figure Tigure[illnn illlstrraees on ex- ample (μx: = (-1)* (k/K)² K) = I,... 50, and T = 500) the shape of the optimal allocation (arms near the threshold should not be drawn) as well as the empirical sampling distri- butions of several algorithms that pull all arms. In Appendix
2.5
Unitorm
FWT
LSA
1.5
APT
1.0
0.5
G we illustrate how this optimal allocation evolves with the horizon T.
-1.0
-0.5
0.0
0.5
1.0
mu
Figure I: Optimal and empirical sam- pling distributions with respect to μ..
2.2 A good algorithm must pull all arms
We provide a new lower bound for the thresholding bandit with unit-cost problem, support the claim that it is not possible to avoid pulling the arms which are close to the threshold. Consider the following Gaussian bandit models (with variances I) with means
14 (e,...,, PKo )K),
14 (1KK+1 /Kot ,/x)
--= = (--,.... -E PK. . pk), H¹_ = (-MKot1..... -Ko+1; MKo+1.... pK)
where 0 < MKo+1 S .... S M.x. the value MKo+1 is large enough for the oracle to pull all arms on 14, and S (2)))
Lemma 1. [TT) S C1
Σ e -oNNN for constants co, er on f E (144, }. then Σx Nu=T
min
Kg
T + Hlog
Ko 32c; H
max ME [ e)
En
Σ
No.T
2
Co
+ log
2[UKo+1 e)2
H
where
Ko kgtt
Σk Ek=Ko+1
A? and Hlog
Ko 3xxt
log
Ek=Kot1
ΣK
A
log A
The proof is postponed to Appendix A In few words, if an algorithm has expected loss close to the loss of the non-adaptive oracle, then it must pull lincarly the arms which are close to the threshold.
3 Algorithm and upper-bound
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
i++1 E arg min (NN,,, AZ, ax) for function F: : x R., x T - 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 fmax E [T] at which min F [N NR. & 0x) was maximal. This rule is used opposed to returning the sign of all arms at time T to facilitate the analysis, which based on the observation that there is a small probability of error when all arms have high index. The time 4max should be close T: in particular, only one arm is sampled (possibly several times) between 4max and T (see Appendix C In Sec. 3.2 we provide generic analysis for index-basee algorithms satisfying the assumption below.
Assumption 1. The index function F(n, z; a) .N x R, x R + R is non-decreasing in n and and lom F(n, ny; a) = +oo for all y > 0, a >
Intuitively, algorithms that verify Assumption I prefer pulling arms that were pulled the least (smallest
n) and whose quantity of information about the sign A2 small. This class includes several
algorithms from the thresholding bandits literature: APT [8] for F(n, 2;; ax)) and LSA (35) for
F(n, z; 0x) x + log(n) (these algorithms are only defined for 0g 1). We now propose generic method for designing index-based algorithm.
5

---

Algorithm Index-based algorithm for thresholding bandit
Inputs: index function F N x R R
R; d1,..... ak : 0; and 0 E I
For t I,..., do
for all & [K] define
[-1 N
c-1
Σ 8=1
P =
Σ
and á 2 20² ( -
N
pull it arg min) P ((N NR, 1 -i
observe X₁ 14
Define mmax = m 77) [i] F(NE,1, NR. k,ei Return for each k E [K] the sign &y sign (isk, 0)
3.1 Frank-Wole for Thresholding bandits
Our strategy to minimize the expected loss is inspired by the Frank-Wolfs algorithm [15 and aims at controlling an upper-bound on the loss, such as the right hand side Inequality 4 Let's write that function (NNr)
Ek= age NN,,A,, The high-level idea is to sequentially estimate its gradient and move to the minimizer of its linear approximation.
the gaps were known, we could compute at time ++1 1 the gradient of the bound with respect to N,, V = - )R and use the Frank-War Wolfe algorithm. The algorithm would pull 4411 E arg min, "' B(N)) for u in the simplex, which simply arg [ (-ax A., 43). The gaps are however unknown. We therefore compute an estimate of the gaps AR.t, with which we form the estimated gradient
B(N)), = -a No, - cxp (ooxp-((M))) [-... log(NN, log ( NNE.t
This gives a natural choice for the index function of our algorithm a(;,:;a;)) log(n/ou ax). However, the latter is decreasing x for x E (0, which in addition to violating Assumption [ may lead to instability in the initial phase when the gaps Ds are poorly estimated by Â... We therefore propose slight modification that preserves asymptotic behavior of and we call the resulting algorithm FWT (Frank-Wold for Thresholding bandits):
log
F(n, 0x) = max(x; x. 1} log(max 1}) + log(n/az).
(FWT)
Recovering APT Using different upper-bounds B on the expected loss may lead to different algorithmms. In particular, highlight link between our Frank-Wolfe inspired method and the APT algorithm of (28), which was designed to minimize the loss
K
K Σ k=1
LT
agllf& + 5
Ex
k=1
Following our method with the choice B(N)) maxke[K] - Af results in exactly the same sampling rule as the one the APT algorithm (the recommendation rule differs slightly since we recommend the sign at fmax and not at T). Indeed, the derivative of B with respect to Ne, is nonzero (and negative) if and only if A arg min, Az (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;; ag) = x in Algorithm which then pulls 4411 arg min At. This is the sampling rule of APT.
3.2 Loss upper bound
We provide loss upper bound that is valid for all andex-baset algorithms that verify Assumption I We then give a compact summary of the analysis outline and the resulting loss bounds.
Theorem Let K 1, 01, Ml....,aK OKK > T 1, and > Let F N x x R + RR that
satisfies Assumption 1
Let C,...., Cx max; F(O, O; ax). For all j. k E [K], define

---

t (Ck) solution of the equation Sk 5 [K] and (5,0(kk) E Rt, a set and values such that for i & Sk.
F Ft, (t,tt)]aa) = Ck.
P Emmstio
n as) 2 C2) =1
Then the expected loss of Algorithm 7 is upper-bounded
1 2 ( (T--Eses jes,, (20(CK)) -jEs, (5(kk) T e...e-lalan -
E6
ag
e exe
Ejes, 1/23
Refer to Appendix D for the proof. is composed of two parts:
1. First establish that for any arm [K], with large probability, there is time Ty (C&) such that ((r,(Ck) (,,)), (a)) 2 Ck. We prove that for all j. E 7 (Ce)) has exponential tail then the fact that the algorithm pulls the minimal index to control the probability that the minimum never reaches Cg.
(Cx).saa)
2. We show that if arm's index is large, then the probability of mistake it is small.
The times (C&) of Theorem are the smallest numbers of samples such that (5(Cs) ) 2 Ty(Ck) with high enough probability. By determining those times, derive explicit bounds for algorithms that verify Assumption T particular we derive a bound for the variant APT which returns the sign at the time tmax when the minimal index was maximal.
Corollary 1. Suppose that for all k E [K], on 1. For all T E N",
T
E| E < 222.-- exxp
4 Li=1 1/43
Refer to Appendix D.3 for the proof. Since max; Es I ΣE Eg, the bound of Corollary [ also bound the zero-one loss, which factor in the exponential instead of the worse 1 1/32 constant of the original paper.
compare to the result of (28). Our result shows 1/4
LSA and FWT Theorem 2 applies to LSA and FWT with the following times:
LSA: (C(C,) = W(e A3) A3 and (2,0(C)) = Cx.
FWT: (Cx) = log(e aaa ()),)))///)) A3)/ and (5,0(C2) = C2-
where W the Lambert W function, which verifies [W(x) - (log x - log log æ)| S log(1 + 1/e) for e. Therefore, for the two algorithms, the times (Cx) are close (equal up the log log terms in W), thus their bounds are close as well. Note that LSA is only defined for aj = for all j. In contrast to LSA, our bound for FWT has the notable property that, in the regime where T 2 > A3 adaptive oracle loss bound (5) (up factor 1/4). Indeed we show that for such T
K 1 (2 + log 03 max, a, (mine e A2)
log F), recover the same exponent in the non-
T T K log
as Ai
EILETT < 2VeT
Σ A=1
ag exp
-
AZ
a
(6)
1/A3
In the same regime of large T, the bound that 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
T
i.e. 4005-times worse
16020
3 1/A3
than our bound. We finally derive bound for our newly introduced algorithm.
7

---

50-
Oracie
50
Upper-bound
40-
1SA
Numberotarss
40
30
20
10
Size of
Figure 2: [left] Comparison of the upper- bound- of Corollaries 12 and that of the optimal non- adaptive oracle of Eq. (5) (blue) when the gaps are of the form A; = (t/ %/K)2. [right] Evolution over time of the size of the optimal sets S (blue) and S (orange) that minimize the bound of Corollary 2
Corollary 2. Let S' be two sets with S S Then, for all T
C
[K] and let C' be such that C 2
max log ax RES
1T -
E Ej --
1 log a +C
FWT E[LT
Σ ag +e
Σ
as exp
Ejes1/A/
S
KES'
T
ak exp (-C log( log(I/(a;
kES
Figure 2 compares the upper-bounds Corollary (APT), Theorem 2 (see also Equation (9) in the Appendix) (I.SA), and Corollary 2 (FWT) for the particular case A (i/K)² and a; for i 1,.... K 50. See also Figure in the supplementary material for A; = i/K. We can see that while the bounds of LSA,, APT, and FWT asymptotically similar, that of FWT starts to be sigmificant for much smaller 7'. On the right, we can see the importance of the set S" in Corollary 2 the bounds first ignores all the arms, and suffers loss of I and then adds them one by one 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.
3.3 The sum-of-gaps objective
We show that our method applies for the sum-of-gaps objective case of the setting discussed previously since aş was known to the algorithm, while Aş is unknown. It serves proof of concept for the extensibility of our method. The index given by FWT in this
ΣK =k= Es This is not particular
setting is F(n, x) = 2 log (a') + log (n), where x' = max (z, 2) We can then bound the
sum-of-gaps loss using our generic analysis by proceeding similarly to Theorem (
Corollary 3. (FWT for the sum-of-gaps objective)
regime where T
2 2
1 A7 3 3 log A, max, A. log ) show that (min; A.)2
K A.E S eV exp
+ Σ 2
log
12
A
E
2
E, 1/D7
See Appendix
E for the proof and for 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.
Beating the oracle? The benefits of adaptivity.
We argue that in some situations adaptive algorithms can greatly outperform the non-adaptive oracle of Section 2. i.e.. the cost non-adaptivity can 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 observed, at the cost of learning the parameter fi. We illustrate the benefits of adaptivity in the following toy example.

---

1.0
1.4
Uniform
0.8
Ratio mean errors
1.3
Oracle
Ratio of errrrs
1.2
LSA
APT
0.4
Oracle
1.0
FWT
0.2
LSA
0.9
APT
0.0
100
300
1000
2500
3000
Time
Time
Figure 3: [left] Median (and 0.25, 0.75 empirical quantiles obtained on 500 runs) of the ratio between the eπror suffered by each algorithm and that of the optimal adaptivpte oracle (μu = (-1)f, k 1..... 100). [right] Ratio the averaged errors (over 500 runs) of each algorithm with that of the 1...., 50).
oracle (14 = (-1) (k)K)
The "optimal" non-adaptive algorithm may be worse than adaptive algorithms. Consider the following parametric problem. An arm distribution parametrized by R. and is supported on {0, x); a sample of that distribution is equal to or æ, 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 an algorithm sees only zeros for one arm, it returns any sign with probability 1/2. The error probability of non-adaptive allocation N 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
K
E L
=
N
2(T/K)+T
1=1
which is minimized with the uniform allocation: N
K for all k E [K].
adaptive procedure that sample each arm in turn, but stops sampling at 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 consequence, the number of required samples classify all correctly follows a negative binomial NB(K, 1/2). Let Z be such negative binomial random variable. The expected number of emrrs of the adaptive procedure is up KP(Z > T). It then verifies
Consider
K
K 2T72
B[L]] <P(Z> T) S - (log(()/2)T (
V2
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/2f/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 those analyzed in the paper: the distributions K arms either (11, 1) or ()-,, Since all gaps A are equal, the optimal non non-adaative oracle is also the uniform sampling. The results are illustrated on the left part of Figure 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 ①.) In particular, we believe that approach can be generalized to losses of the form LT EE=1 Max Ex) under certain regularity assumptions on f. Moreover, we focused on separable losses (hence linear wlog) analyze reflect that separability. An obvious and intriguing
and the index based algorithms 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 given number of mistakes.
The fact that adaptive algorithms can beat non-adaptive oracles has already been observed empirically for fixed confidence identification [3 I0]. 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 much more significant and remains to be explained by theoretical arguments. Currently, best theoretical bound for adaptive algorithms is still a factor 3/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-CE25
as well as the support grant, as well as from the grant "Investissements d' A'Aenirr" (LabEx Ecodec/ANR-I -LABX-0047Y" 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 part of the "Investissements d' "'avenir" program, reference ANR-19-P3IA-000 (PRAIRIE 3IA Institute).
References
[1] Agarwal, A., Foster, D. P., Hsu, D. J., Kakade, S. M., and Rakhlin, A. Stochastic convex optimization with bandit feedback. In Shawe-Taylor, J., Zemel, R. S., Bartlett, P. L., Pereira, F. and Weinberger, K. Q (eds.), Advances in Neural Information Processing Systems 24, pp. 1035-1043, Curran Associates, Inc., 2011.
[2] Agrawal, S. and Devanur, N. R. Bandits with concave rewards and convex knapsacks. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC '14 pp. 989-1006, New York, NY, USA, 2014. ACM. ISBN 978-1-45555 1-5503-2555-33
[3] Audibert, J.,Y., Bubeck, S., and Munos, R. Best arm identification multi-armed bandits. In COLT, pp. 41-53, 2010.
[4] Auer, P., Cesa-Biann Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[5] Berthet, Q and Perchet, V. Fast rates for bandit optimization with upper-confidence frank-wolfe. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30, pp. 2225-2234. 2017.
[6] Bubeck, S., Cesa-Bianchi, N., et al. Regret analysis stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
[7] Chen, X., Lin. Q., and Zhou, D. Statistical decision making for optimal budget allocation in crowd labeling. The Journal of Machine Learning Research, 16(1):1-46, 2015.
[8] Cheshire, Menard, P., and Carpentier, A. The influence of shape constraints on the threshold- ing bandit problem. In Conference Learning Theory, pp. 1228-1275. PMLR, 2020.
[9] Degenne, and Koolen, W. M. Pure exploration with multiple correct answers. arXiv preprint arXiv: 1902.03475 2019.
[10] Degenne, R., Koolen, W. M., and Ménard, Non-asymptotic pure exploration by solving games. arXiv preprint
10431, 2019.
10

---

[11] Devanur, N. R., Jain, K., Sivan, B., and Wilkens, C. A. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM), 66(1): 2019.
[12] Even-Dar, E., Mannor, S., Mansour, Y., and Mahadevan, S. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6). 2006.
[13] Fontaine, X., Berthet, Q. and Perchet, V. Regularized contextual bandits. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2144-2153. PMLR, 2019.
[14] Fontaine, X., Mannor, S., and Perchet, V. An adaptive stochastic optimization algorithm for resource allocation. In Algorithmic Learning Theory, pp. 319-363. PMLR, 2020.
[15] Frank, M. and Wolfe, P. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2)955-110, 1956.
[16] Garivier, A., Ménard, P., Rossi, L., and Menard, P. Thresholding bandit for dose-ranging: The impact of monotonicity. arXiv preprini arXiv: 171104444, 2017.
[17] Hoorfar, A. and Hassani, M. Inequalities the lambert function and hyperpower function. J. Inequal. Pure and Appl. Math, 9())5-9, 2008.
[18] Jain, L. and Jamieson, K. G. A new perspective on pool-based active classification and false- discovery control. Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Be Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[19] Jamieson, K. and Jain, L. A bandit approach to multiple testing with false discovery control. arXiv preprint arXiv: 1809.02235, 2018.
[20] Janson, S. Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters, 135:1-6, 2018
[21] Kano, H., Honda, J., Sakamaki, K., Matsuura, K., Nakamura, A., and Sugiyama, M. Good arm identification via bandit feedback. Machine Learning, 108(5):721-745, 2019.
[22] Katariya, S., Tripathy, A., and Nowak, R. Maxgap bandit: Adaptive algorithms for approximate
ranking. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox. E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[23] Katz SatzelSmmells and Scott, C. Feasible arm identification. In International Conference on Machine Learning, pp.
PMLR, 2018
[24] Kaufmann, E., Cappé. O., and Garivier, A. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1): 122, 2016.
[25] Kaufmann, E., Koolen, W., and Garivier, A. Sequential test for the lowest mean: From thompson murphy sampling. arXiv preprint arXiv:1806 00973, 2018.
[26] Koopman, B. O. The optimum distribution of effort. Journal of the Operations Research Society of America, 1(2):52-63, 1953.
[27]
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cambridge University Press, 2020.
[28] Locatelli, A., Gutzeit, M., and Carpentier, A. An optimal algorithm for the thresholding bandit problem. International Conference on Machine Learning, pp- 1690-1698. PMLR, 2016.
[29] Mannor, S., Perchet, V., and Stoltz, G. Approachability in unknown games: Online learning meets multi-objective optimization. In Conference on Learning Theory, pp. 355. PMLR, 2014.
[30] Mukherjee, S., Naveen, P., Sudarsanam, N., and Ravindran, Thresholding bandits with augmented ucb. arXiv preprint arXivv1704.02281, 2017.

---

[31] Perchet, V., Rigollet, P., Chassang, S., Snowberg, E., et al. Batched bandit problems. Annals of Statistics, 44(2):660-681, 2016.
[32] Salehi, M. A., Smith, J., Maciejewski, A. A., Siegel, H. J., Chong, E. K., Apodaca, J., Briceno, L. D., Renner, T., Shestak, V., Ladd, J., et al. bacchastic-aseee robust dynamic resource allocation for independent tasks in a heterogeneous computing system. Journal of Parallel and Distributed Computing, 97:96-111 111,11111111 2016.
[33] Simchowitz, M., Jamieson, K., and Recht, B. The simulator: Understanding adaptive sampling in the moderate-confideence regime. In Conference on Learning Theory, pp. 1794-18811 1834. PMLR, 2017.
[34] Slivkins, A. et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1-288) 2019.
[35] Tao, C., Blanco, S., Peng. J., and Zhou, Thresholding bandit with optimal aggregate regret. In Advances in Neural Information Processing Systems, pp. 1664-11673, 2019.
[36] Zhong, J., Huang, Y., and Liu, J. Asynchronous parallel empirical variance guided algorithms for the thresholding bandit problem. arXiv preprint arXiv: /00::::000055 2017.
[37] Zhu, Y., Katariya, S., and Nowak, R. Robust outlier arm identification. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1 11566-11575. PMLR, 13-18 Jul 2020.
[38] Zhuang. H., Wang, C., and Wang. Y. Identifying outlier arms in multi- aumti-armed bandit. In Proceedings of the 3/st International Conference on Neural Information Processing Systems, pp. 1p.5210-50 5210-5219, 2017.
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] is purely theoretical paper
(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]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See Appendix G
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the description of each figure.
(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] See Appendix
4. If you 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]
12

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "yX1w0TyJrOC", "reviewer": "Reviewer_9Lq4", "summary": "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. \n\nTheir main contributions are:\n-  a new proof technique for thresholded bandits\n- new upper and lower bounds\n- proof that the adaptive method can beat a non-adaptive oracle in some cases", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: their proof based on the Frank-Wolfe method for any index function that satisfies their criteria is novel. It encompasses current methods but they also provide a better algorithm (for the constant in the exponent).\n\nClarity: The paper is well written. This reviewer found a few typos (see below) but it is clear otherwise.\n Significance: the results are useful because they give a general proof method that may be applied to other algorithms. It provides a structure to construct good index functions for thee bandits based on their bounds. I think that this paper will help other build on the results provided.\n\nCritiques: the authors give an example of when adaptivity helps but they also show cases where it hurts (non-oracle algorithms cannot ignore certain arms like the oracle). This is an interesting point and a discussion about what types of problems fall into each category would have enhanced the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations but I did not find their note on social impact. Having said that, this work is mostly theoretical posing a difficulty to analyze its societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "pUU6KKBJxr", "reviewer": "Reviewer_JWse", "summary": "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:\n\n1. 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.\n2. 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.\n\nAfter rebuttal\n--------------------\nThe rebuttal looks good to me and I will keep my positive score.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Generally, I think this is a good paper with a nice literature review, presentation, and technique depth. The developed new algorithm, which aims to solve a generic goal, is found to have a better regret bound than the previous LSA algorithm when considering the goal to minimize aggregate regret. Also, it is interesting to see the new rule to decide the signs of the arms.\n\nI do have some minor comments detailed in the following:\n\nLine 36: “As as consequence” -> As a consequence\n\nLine 49: “the performances of an algorithm”: performances -> performance\n\nLemma 1: what is \\tilde{\\Delta}_k^2?\n\nLine 179: “that each depend only on the rewards”: depend -> depends\n\nAssumption 1: it is better to specify the parameters of F i.e., F(n, x; a) for clearer presentation\n\nLine 278: in the example introduced, the sign is not defined. I guess the sign should be the actual parameter x? \n\nFigure 3: In the caption of the left subfigure, it says Median, 0.25, and 0.75 empirical quantiles are presented. However, for each algorithm, only one line is presented. I am wondering which one you are referring to?  Also for the right subfigure, the ratio of the averaged errors should be at most 1, and why it appears to be greater than 1 in the figure?\n\nRegarding the experiments, I think it may be better to add one more figure presenting the performance of algorithms LSA, APT, and FWT regarding random input instances. The current one \\mu_k = (-1)^k (k/K)^2 looks artificial to me.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "2sl7auiIGwO", "reviewer": "Reviewer_ydCQ", "summary": "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. \n\nThe 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. \n\nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem studied in this paper is well-known in the community. The algorithms are not very novel according to my knowledge. However, the authors managed to get better bounds by a better analysis. Another main contribution of this paper is to make an abstraction of the existing algorithms and make a unified and thorough analysis. \n\nThe results are very close to the optimal, i.e., there are only a gap of 4 in the exponential term. \n\nThe paper is well written and well structured.\n\nThe main concern of this paper is the significance. In fact, this paper does not propose novel algorithms or mathematical techniques, but more like a deeper study and summary of existing works. But due to its quality and clarity, I tend to give a score between 6 and 7. To be more conservative in case I missed anything, I will vote a 6 for now and wait for the author responses.\n\n--------------------------------------\nAfter the rebuttal, I am raising the score from 6 to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations have been discussed in the box Main Review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers came to consensus that this paper makes a good progress on the thresholding bandit problem from the perspectives of upper and lower bounds as well as an interesting discussion on the benefit of adaptivity. I agree with these opinions and please polish the manuscript so that the minor concerns raised by the reviewers become clear in the final version.
Decision: Accept (Spotlight)