James Cheshire
email: james.cheshire@ovgu.de

Pierre Menard
email: pierre.menard@inria.fr

Alexandra Carpentier
email: alexandra.carpentier@ovgu.de

Jacob Abernethy

Shivani Agarwal

The Influence of Shape Constraints on the Thresholding Bandit Problem

We investigate the stochastic Thresholding Bandit problem (TBP ) under several shape constraints. On top of (i) the vanilla, unstructured TBP, we consider the case where (ii) the sequence of arm's means (µ k ) k is monotonically increasing MTBP, (iii) the case where (µ k ) k is unimodal UTBP and (iv) the case where (µ k ) k is concave CTBP. In the TBP problem the aim is to output, at the end of the sequential game, the set of arms whose means are above a given threshold. The regret is the highest gap between a misclassified arm and the threshold. In the fixed budget setting, we provide problem independent minimax rates for the expected regret in all settings, as well as associated algorithms. We prove that the minimax rates for the regret are (i) log(K)K/T for TBP, (ii) log(K)/T for MTBP, (iii) K/T for UTBP and (iv) log log K/T for CTBP, where K is the number of arms and T is the budget. These rates demonstrate that the dependence on K of the minimax regret varies significantly depending on the shape constraint. This highlights the fact that the shape constraints modify fundamentally the nature of the TBP problem to the other.

Introduction

Stochastic multi-armed bandit problems consider situations in which a learner faces multiple unknown probability distributions, or "arms", and has to sequentially sample these arms.

In this paper, we focus on the Thresholding Bandit Problem (TBP ), a Combinatorial Pure Exploration (CPE) bandit setting introduced by [START_REF] Chen | Combinatorial pure exploration of multi-armed bandits[END_REF]. The learner is presented with [K] = {1, . . . , K} arms, each following an unknown distribution ν k with unknown mean µ k . Given a budget T > 0, the learner samples the arms sequentially for a total of T times and then aims at predicting the set of arms whose mean is above a given threshold τ ∈ R. The performance of the learner is measured through the expected simple regret which in this setting is the expected maximal gap between τ and the mean of a misclassified arm. Note that our problem is in fact akin to estimating in a sequential setting a given level-set of a discrete function under shape constraints.

In this paper we will be interested only in the problem independent case, and want to characterise the minimax-order of the expected simple regret on various sets of bandit problems. In particular we study the influence of various shape constraints on the sequence Monotone constraint, MTBP. We then consider the problem where on top of assuming that the distributions are supported in [0, 1], we assume that the sequence of means (µ k ) k is monotone -this is problem MTBP . This specific instance of the TBP is introduced within the context of drug dosing in [START_REF] Garivier | Thresholding bandit for dose-ranging: The impact of monotonicity[END_REF]. In this paper, the authors provide an algorithm for the fixed confidence setting that is optimal from a problem dependent point of view. The shape constraint on the means of the arms implies that the MTBP is related to noisy binary search, i.e. inserting an element into its correct place within an ordered list when only noisy labels of the elements are observed, see [START_REF] Feige | Computing with noisy information[END_REF]. In the noiseless case, an effective approach due to the shape constraint is to conduct a binary search -and the classification of the arms can therefore be performed in just O(log(K)) steps, while K steps are needed in the noiseless TBP . It is therefore clear that MTBP is radically different from TBP , even in the noiseless case. In the noisy case, the learner has to sample many times each arm in order to get a reliable decision at each step. While a simple naive strategy, although sufficient in Xu et al. (2019), is to do noisy binary search where at each step the learner simply samples about O(T / log(K)) times each arm, there are clear hints from the literature that in the MTBP this is not going to be optimal. For the related yet different problem of noisy binary search, [START_REF] Feige | Computing with noisy information[END_REF], [START_REF] Ben | The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)[END_REF] and [START_REF] Emamjomeh-Zadeh | Deterministic and probabilistic binary search in graphs[END_REF] solve this issue by introducing a noisy binary search with corrections -see also [START_REF] Nowak | The geometry of generalized binary search[END_REF], [START_REF] Richard | Noisy binary search and its applications[END_REF]. However, all these papers consider the problem of noisy binary search in settings with more structural assumptions and where the objective is more related to a fixed confidence setting, their results are therefore not directly applicable to our setting. See the discussion under Theorem 2 for a more thorough comparison to this literature and see Appendix H for details. In this paper, we prove that the minimax-optimal order of expected simple regret in MTBP is log(K)/T . Interestingly and as highlighted in this paragraph, this rate is much smaller than the minimax rate over TBP . This reflects the fact that the monotone shape constraint makes the problem much simpler than TBP , and closer to noisy binary search. Further discussion on the comparison between the TBP and MTBP , specifically the difference coming from the monotone assumption, can be found in Appendix H and see the algorithm Explore and the associated text in Section 4 for more intuition on the link to noisy binary search. Discussion on the performance of our algorithms for the MTBP in the problem dependent regime can also be found in Appendix H.

Unimodal constraint, UTBP. We also consider the problem where on top of assuming that the distributions are supported in [0, 1], we assume that the sequence of means (µ k ) k is unimodal -this is problem UTBP . It has not been considered to the best of our knowledge. However similar problems have been studied such that identifying the best arm or minimizing the cumulative regret Combes and Proutiere (2014a,b); [START_REF] Paladino | Unimodal thompson sampling for graph-structured arms[END_REF]; Yu and Mannor (2011). [START_REF] Paladino | Unimodal thompson sampling for graph-structured arms[END_REF]; Combes and Proutiere (2014b) focus on the problem dependent regime, and are not transferable -at least to the best of our knowledge -to the problem independent setting. Yu and Mannor (2011); Combes and Proutiere (2014a) are closer to our problem as it focuses on the problem independent regime. However, they consider the X -armed setting (continuous set of arms e.g. in [0, 1]) setting and assume Hölder type regularity assumption around the maximum, which prevents jumps in the mean vector. These results therefore do not apply to our setting, where of course jumps are bound to happen as we are in the discrete setting. See the discussion under Theorem 3 for a more thorough comparison to this literature. In this paper, we prove that the minimax-optimal order of the expected simple regret in UTBP is of order K/T . This is interesting in contrast to the rate of MTBP . Monotone bandit problems are much easier than unimodal bandit problems -which can be written as a combination of a non-decreasing bandit problem, and a non-increasing bandit problem. This is however not very surprising, as finding the maximum of the unimodal bandit problem -i.e. the points where the non-increasing and non-decreasing bandit problems mergeis difficult.

Concave constraint, CTBP. Finally we consider the problem where on top of assuming that the distributions are supported in [0, 1], we assume that the sequence of means (µ k ) k is concave -this is problem CTBP . To the best of our knowledge this setting has not yet been consider in the literature. However, two related problems have been considered: the problem of estimating a concave function, and the problem of optimising a concave function -for both problems, mostly in the continuous setting, which renders a comparison with our setting delicate. The problem of estimating a concave function has been thoroughly studied in the noiseless setting, and also in the noisy setting, see e.g. [START_REF] Simchowitz | Adaptive sampling for convex regression[END_REF], where the setting of a continuous set of arms is considered, under Hölder smoothness assumptions. The problem of optimising a convex function in noise without access to its derivative -namely zeroth order noisy optimisation -has also been extensively studied. See e.g. [START_REF] Nemirovski | Problem complexity and method efficiency in optimization[END_REF][Chapter 9], and [START_REF] Wang | Stochastic zeroth-order optimization in high dimensions[END_REF]; [START_REF] Agarwal | Stochastic convex optimization with bandit feedback[END_REF]; [START_REF] Liang | On zeroth-order stochastic convex optimization via random walks[END_REF] to name a few, all of them in a continuous setting and in dimension d. The focus of this Results Unstructured TBP Monotone TBP Unimodal TBP Concave TBP

Regret K log K T log K T K T loglog K T
Table 1: Order of the minimax expected simple regret for the thresholding bandit problem, in the case of all four structural assumptions on the means of the arms considered in this paper. All results are given up to universal multiplicative constants.

literature is however very different than ours, as the main difficulty under their assumption is to obtain a good dependence in the dimension d, and in this setting logarithmic factors are not very relevant. See the discussion under Theorem 4 for a more thorough comparison to this literature.

In this paper, we prove that the minimax-optimal order of the expected simple regret in CTBP is loglog(K)/T . This is interesting in contrast to rate in the case of UTBP .

Concave bandit problems are much easier than unimodal bandit problems. Also, if we compare with MTBP , we have that concave bandit problems are also much easier than monotone bandit problems, which is perhaps surprising -in particular the fact that the dependence in K is much smaller.

Organisation of the paper Our results are summarized in Table 1. See also Appendix A for an adaptation of these results in the X -armed bandit setting. In Section 2 we define the setting and the TBP , MTBP , CTBP and UTBP problems. Minimax rates for the expected regret for all cases are given in Section 3. In Section 4 we describe algorithms attaining the minimax rates of Section 3, again for all cases. The Appendix contains the proofs for all results, as well as formulation of the upper and lower bounds leading to the minimax rates in a broader setting, transposition of some results in the fixed confidence setting, and also some additional discussions and remarks.

Problem formulation

The learner is presented with a K-armed bandit problem ν = {ν 1 , . . . , ν K }, with K ≥ 3, where ν k is the unknown distribution of arm k. Let τ ∈ R be a fixed threshold known to the learner. We aim to devise an algorithm which classifies arms as above or below threshold τ . That is, the learner aims at finding the vector

Q ∈ {-1, 1} K that encodes the true classification, i.e. Q k = 21 {µ k ≥τ } -1 with the convention Q k = 1 if arm k is above the threshold and Q k = -1 otherwise.
The fixed budget bandit sequential learning setting goes as follows: the learner has a budget T > 0 and at each round t ≤ T , the learner pulls an arm k t ∈ [1, K] and observes a sample Y t ∼ ν kt , conditionally independent from the past. After interacting with the bandit problem and expending their budget, the learner outputs a vector Q ∈ {-1, 1} K and the aim is that it matches the unknown vector Q as well as possible.

That is, the fixed budget objective of the learner following the strategy π is then to minimize the expected simple regret of this classification for Q := Qπ :

Rν ,π T = E ν max {k∈[K]: Qπ k =Q k } ∆ k ,
where ∆ k := |τ -µ k | is the gap of arm k, and where E ν is defined as the expectation on problem ν and P ν the probability. We also write for the simple regret as a random variable Rν

,π T = max {k∈[K]: Qπ k =Q k } ∆ k .
When it is clear from the context we will remove the dependence on the bandit problem ν and/or the strategy π. We now present several sets of bandit problems that correspond to our four shape constraints.

Vanilla, unstructured case TBP We assume that the distribution of all the arms ν k are supported in [0, 1]. We denote by µ k the mean or arm k. Let B := B(K) be the set of such problems.

Monotone case MTBP We denote by B m the set of bandit problems,

B m := {ν ∈ B : µ 1 ≤ µ 2 ≤ . . . ≤ µ K } ,
where the learner is given the additional information that the sequence of means (µ k ) k∈[K] is a monotonically increasing sequence.

Unimodal case UTBP We will denote by B u the set of bandit problems,

B u := {ν ∈ B : ∃k * ∈ [K]s.t.∀l ≤ k * , µ l-1 ≤ µ l and ∀l ≥ k * , µ l ≥ µ l+1 } ,
where the learner is given the additional information that the sequence of means (µ k ) k∈[K] is unimodal.

Concave case CTBP We will denote by B c the set of bandit problems,

B c := ν ∈ B : ∀1 < k < K -1, 1 2 µ k-1 + 1 2 µ k+1 ≤ µ k ,
where the learner is given the additional information that the sequence of means (µ k ) k∈[K] is concave.

Minimax expected regret

Minimax expected regret for TBP, MTBP, UTBP, CTBP

In this section we present all minimax rates on the expected regret in the case of all four shape constraints. Algorithms achieving these mini-max rates are described in Section 4.

For two positive sequences of real numbers (

a n ) n , (b n ) n , we write a n b n if there exists two universal constants 2 0 < c < C such that ca n ≤ b n ≤ Ca n .
Theorem 1 provides the minimax rate of the TBP . The proof can be found in Appendix C, i.e. Proposition 8, and Proposition 10.

Theorem 1 It holds that R * T (B) K log K T .
The algorithm Uniform described in Sections 4 (see also Appendix C) attains this rate.

It is difficult to compare this result to state of the art literature as existing papers consider almost exclusively the problem dependent regime, and often the fixed confidence setting. One can however deduce from [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF] an upper bound of order K log(K log T /δ)/T , and from [START_REF] Chen | Combinatorial multi-armed bandit with general reward functions[END_REF] a lower bound of order K/T , which are both slightly sub-optimal.

Theorem 2 provides the minimax rate of the MTBP . The proof can be found in Appendix D, i.e. Proposition 11, and Corollary 13.

Theorem 2 It holds that R * T (B m ) log K T .
The algorithm MTB described in Section 4 attains this rate.

The literature that achieves results closest to this theorem is the noisy binary search literature cited in the introduction. The results that are most comparable to ours are the ones in [START_REF] Richard | Noisy binary search and its applications[END_REF]. They consider the special case where all arms follow a Bernoulli distribution with parameter p k and p 1 < ... < p K , and the aim is to find a i such that p i is close to 1/2. In the fixed confidence setting, they prove that the naive binary search approach is not optimal and propose an involved exponential weight algorithm, as well as a random walk binary search, for solving the problem. They prove that for a fixed ε, δ > 0, the algorithm returns all arms above threshold with probability larger than 1 -δ, and tolerance ε, in an expected number of pulls less than a multiplicative constant that depends on δ in a non-specified way times log 2 (K)/ε 2 . They prove that this is optimal up to a constant depending on δ. In the paper [START_REF] Ben | The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)[END_REF] they refine the dependence on δ in a slightly different setting -where one has a fixed error probability. They prove that up to terms that are negligible with respect to log(K)/ε 2 , a lower bound in the expected stopping time is of order (1 -δ) log(K)/ε 2 . Even after a non-trivial transposition effort from their setting to ours, these results would still provide sub-optimal bounds in our setting as we consider the expected simple regret -and a sharper dependence in their δ would be absolutely necessary here in all regimes to get our results.

Theorem 3 provides the minimax rate of the UTBP . The proof can be found in Appendix E, i.e. Proposition 24, and Proposition 25.

Theorem 3 It holds that R * T (B u ) K T .
The algorithm UTB described in Section 4 attains this rate.

Most related papers consider the problem dependent setting. However the papers Yu and Mannor (2011); Combes and Proutiere (2014a) consider the problem independent regime, in the X -armed setting and in both cases under additional shape constraint assumptions inducing that the maximum is not too "peaky" and isolated. They prove that the minimax simple regret for the TOP-1 problem is of order log(T )/T . This seems to contradict our results, to which a direct corollary is that the minimax expected regret for finding a given level set of a β-Hölder, unimodal function in [0, 1] is n -β 2β+1 , see Appendix A. This might seem unintuitive when compared to their result where the rate is much faster. But is not, as the assumption that both papers make essentially imply that the set of arms that are ε-close to the arm with highest mean decays in a regular way, which implies that a binary search will provide good results in this case -unlike in our setting. Therefore their setting is closer in essence to the MTBP problem than to the TBP problem, as binary-search type methods work well there as highlighted in Combes and Proutiere (2014a). And interestingly, a direct corollary to Theorem 2 for MTB is that the minimax expected regret for finding a given level set of a β-Hölder, monotone function in [0, 1] is log(T )/T , see Appendix A, which is very much aligned with the findings in Combes and Proutiere (2014a).

Theorem 4 provides the minimax rate of the CTBP . The proof can be found in Appendix F, i.e. Proposition 26, and Proposition 27.

Theorem 4 It holds that R * T (B c ) loglog K T .
The algorithm CTB described in Section 4 attains this rate.

As stated in the introduction, the closest literature to our setting is that which concerns sequential estimation of a convex function and noisy convex zeroth order optimisation. Since this literature deals with the continuous case, let us first remark that a straightforward3 corollary of Theorem 4 is that in the case where the arms are in [0, 1] and where f is β-Hölder for some β > 0, the minimax expected regret according to our definition (but in this continuous setting) is loglog(T )/T , see Appendix A for details.

In [START_REF] Simchowitz | Adaptive sampling for convex regression[END_REF], the authors present the problem of estimating a convex function by constructing a net of points that is more refined in areas where the function varies more, i.e. by adapting a quadrature method to the noisy setting. Under an assumption on the modulus of continuity, that is essentially equivalent to assuming that the function is β-Hölder for some β > 0, the authors provide results in the fixed confidence setting.

If one inverses their bounds to go to the fixed budget setting, their results hint toward a lower bound on estimating the convex function in l ∞ norm of order log(T )/T and an upper bound of order log(T )/ √ T . The fact that the logarithmic dependency is much worse in their setting than in ours highlights that the problem of estimating entirely the convex function is more difficult than the problem of estimating a single level set. In [START_REF] Nemirovski | Problem complexity and method efficiency in optimization[END_REF][Chapter 9], and [START_REF] Wang | Stochastic zeroth-order optimization in high dimensions[END_REF]; [START_REF] Agarwal | Stochastic convex optimization with bandit feedback[END_REF]; [START_REF] Liang | On zeroth-order stochastic convex optimization via random walks[END_REF] the authors consider continuous zeroth order noisy convex optimisation, and focus mainly on reducing the exponent for the dimension d -in this setting the minimax precision for estimating the minimum of the function is conjectured to be d 3/2 poly(log(T ))/ √ T where the poly(log(T )) term is not really investigated, as the problem is already very difficult as it is. We on the other hand consider mainly d = 1 and aim at obtaining optimal logarithmic terms.

Minimax optimal algorithms

In this section we present algorithms that match minimax regret rates in Section 3 up to multiplicative constants for TBP , MTBP , UTBP and CTBP .

Unstructured case TBP

Given an unstructured problem ν ∈ B we consider the algorithm Uniform which samples uniformly across the arms. That is each arm in [K] is sampled T /K times. The learner then classifies each arm according to its sample mean, see Algorithm 6 in Appendix C.

Surprisingly the naive Uniform algorithm is optimal in the unstructured case with respect to the lower bound of Theorem 1. See the proof of Proposition 10 in Appendix C. This contrasts with the related TOP-1 bandit problem where the minimax regret rate is K/T , see [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF]; [START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF] for hints toward this. This is not very surprising as in the TOP-1 problem we are interested in finding one arm only, namely the arm with highest mean, while in our problem we search for all arms above threshold and for this we pay an additional √ log K.

Monotone case MTBP

In this section we fix a problem ν ∈ B m . We also assume, in this section, without loss of generality that τ ∈ [µ 1 , µ K ]. Indeed, we can always add two deterministic arms 0 and K + 1 with respective means µ 0 = -∞ and µ K+1 = +∞. While we assume that the distributions of the original K arms are supported in [0, 1] the addition of two such arms will not invalidate our proofs, see Appendix D.

We introduce the MTB (Monotone Thresholding Bandits) algorithm, composed of two sub-algorithms, Explore and Choose. The first, Explore, performs a random walk on the set of arms [K] seen as a binary tree, the algorithm Choose then selects, among the visited arms, the one that will be chosen as the threshold for the classification. That is, we choose an arm k which leads to the estimator Q, where Q : Q

[k] = -1 ∀k < k, Q[k] = 1 ∀k ≥ k .
Binary Tree We associate to each problem ν ∈ B m a binary tree. Precisely we consider a binary tree with nodes of the form v = {L, M, R} where {L, M, R} are indexes of arms and we note respectively v(l) = L, v(r) = R, v(m) = M . The tree is built recursively as follows: the root is root = {1, (1 + K)/2 , K}, and for a node

v = {L, M, R} with L, M, R ∈ {1, . . . , K} the left child of v is L(v) = {L, M l , M } and the right child is R(v) = {M, M r , R} with M l = (L + M )/2 and M r = (M + R)/2 as the middle index between.
The leaves of the tree will be the nodes {v = {L, M, R} :

R = L + 1}. If a node v is a leaf we set R(v) = L(v) = ∅.
We consider the tree up to maximum depth H = log 2 (K) + 1. We note P l(v) = P r(v) the parent of the two children and let |v| denote the depth of node v in the tree, with |root| = 0. We adopt the convention P (root) = root. In order to predict the right classification we want to find the arm whose mean is the one just above the threshold τ . Finding this arm is equivalent to inserting the threshold into the (sorted) list of means, which can be done with a binary search in the aforementioned binary tree. But in our setting we only have access to estimates of the means which can be very unreliable if the mean is close to the threshold. Because of this there is a high chance we will make a mistake on some step of the binary search. For this reason we must allow Explore to backtrack and this is why Explore performs a binary search with corrections. Then Choose selects among the visited arms the most promising one.

Explore algorithm We first define the following integers,

T 1 := 6 log(K) T 2 := T 3T 1 .
The algorithm Explore is then essentially a random walk on said binary tree moving one step per iteration for a total of T 1 steps. Let v 1 = root and for t < T 1 let v t denote the current node, the algorithm samples arms {v t (k) : k ∈ {l, m, r}} each T 2 times. Let the sample mean of arm v t (k) be denoted μk,t . Explore will use these estimates to decide which node to explore next. If an error is detected -i.e. the interval between left and rightmost sample mean do does not contain the threshold, then the algorithm backtracks to the parent of the current node, otherwise Explore acts as the deterministic binary search for inserting the threshold τ in the sorted list of means. More specifically, if there is an anomaly, τ ∈ [μ l,t , μr,t ], then the next node is the parent

v t+1 = P (v t ), oth- erwise if τ ∈ [μ l,t , μm,t ] the the next node is the left child v t+1 = L(v t ) and if τ ∈ [μ m,t , μr,t ] the next node is the right child v t+1 = R(v t ). If at time t, τ ∈ [μ l,t , μr,t ]
and the node v t is a leaf then v t+1 = v t . See Algorithm Explore for details.

Algorithm 1 Explore Initialization:

v 1 = root for t = 1 : T 1 do sample T 2 times each arm in v t if τ ∈ [μ l,t , μr,t ] then v t+1 = P (v t ) else if R(v t ) = L(v t ) = ∅ then v t+1 = v t else if μm,t ≤ τ ≤ μr,t then v t+1 = R(v t ) else if μl,t ≤ τ ≤ μm,t then v t+1 = L(v t ) end end
Choose algorithm Algorithm Choose takes the history of algorithm Explore, namely the sequence of empirical means (μ l,t , μm,t , μr,t ) t≤T 1 and visited nodes (v t ) t≤T 1 , as the input. In addition it takes as input a parameter ε > 0. The action of Choose is to then identify the set of arms among those sampled whose empirical means satisfy one or more of the following:

• their empirical mean is within ε of τ ,

• their empirical mean is less than τ and the empirical mean of the right hand adjacent arm is greater than τ . Here we recognize the set of arms that may lead to a classification with simple regret smaller than ε if the estimates are correct. The algorithm Choose then orders this set by ascending arm index and returns the median, see Algorithm 2.

Algorithm 2 Choose

Input: ε, (μ l,t , μm,t , μr,t ) t≤T 1 , (v t ) t≤T 1 Initialization: S 1 = [ ] for t = 1 : T 1 do S t+1 = S t if {∃k ∈ {l, m, r} : |μ k,t -τ | ≤ ε} ∨ {k = v t (r) = v t (l) + 1; μl,t + ε < τ ≤ μr,t -ε} then append v t (k)
to the list S t+1 end end order the list S T 1 +1 by ascending arm index return Median(S T 1 +1 ).

Remark 5 Note that for any time t ≤ T 1 we append at most one arm to the list S t+1 . If at time t there are multiple candidates the choice is made at random.

MTB algorithm

The algorithm first runs Explore. We fix a constant ε 0 = 2 log(48)/T 2 , and compute the parameter ε with the history of algorithm Explore,

ε =    2ε 0 if ∃(t, k) : k = v t (l) = v t (r) -1; μl,t ≤ τ ≤ μr,t max 2ε 0 , min t≤T 1 ,k∈{l,m,r} |μ k,t -µ vt(k) | else .
Then MTB runs the algorithm Choose with parameter ε. Note that ε is the smallest parameter greater than 2ε 0 such that the list S T 1 +1 is non empty. This choice will become clear in the proof of Theorem 2 in Appendix D. Morally it allows to select a majority of "good" arms (i.e that provide a low regret classification Q) in S T 1 +1 such that the median k is also a "good" arm, see Algorithm 3.

The MTB algorithm will achieve the minimax rate on expected simple regret given in Theorem 2, see the proof of Theorem 2, in Appendix D, for details.

Algorithm 3 MTB run algorithm Explore • Output: (μ l,t , μm,t , μr,t ) t≤T 1 , (v t ) t≤T 1 run algorithm Choose • Input: ε, (μ l,t , μm,t , μr,t ) t≤T 1 , (v t ) t≤T 1 • Output: arm index k return ( k, Q) : Qk = 21 {k≥ k} -1
Remark 6 (Adaptation of MTB to a non-increasing sequence, DEC-MTB) MTB is applied for a monotone non-decreasing sequence (µ k ) k , and it is easy to adapt it to a monotone non-increasing sequence (µ k ) k . In this case, we transform the label of arm i into K -i, and apply MTB to the newly labeled problem -where the mean sequence in now non-decreasing. We refer to this modification as DEC-MTB.

Unimodal case UTBP

We now turn to the algorithm for the unimodal case, UTB (Unimodal Thresholding Bandits) algorithm. This algorithm is based on the algorithm MTB, and on any black-box algorithm that is minimax-optimal for TOP-1 simple regret on B, as described in [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF].

We name such an algorithm SR; it takes no parameter and returns an arm m. Since SR is minimax optimal for the TOP-1 simple regret, we have on any problem ν ∈ B with means (µ k ) k and maximal mean µ * , that if SR is run for T times, then

E ν [µ * -µ m] ≤ c SR K T ,
where c SR > 0 is a universal constant. Note that taking MOSS from [START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF] and modifying it so that it outputs m as being sampled at random according to the proportion of times that each arm was sampled by MOSS, is minimax-optimal algorithm for the TOP-1 problem.

The idea of UTB is to start by running SR on a fraction of the budget, and take its output m. Then we run respectively MTB on {1, . . . , m}, and DEC-MTB on { m, . . . , K} on a fraction of the budget. They respectively return l, r. We then use the last fraction of the budget to sample all arms in { l, r, m, l -1, r + 1} and compute the respective empirical means μk for k being one of these arms. If l, r seem either close enough to the threshold, or seem above while the adjacent arm seems below, we predict { l, . . . , r} as the set of arms above threshold. Otherwise we return the empty set, see Algorithm 4. This intuitively makes sense as m is an estimator of the maximum k * of the mean sequence and unimodality implies that (µ k ) k≤k * is non-decreasing, and that (µ k ) k≥k * is non-increasing. So l, r are estimators of the points where the mean sequence crosses the threshold, respectively on the left and on the right of the estimator of the maximum. The last step -where we compute empirical means and check based on them if the outputs seem reasonable -is a checking step for making sure that the output of SR is not so close to threshold (or flawed), that the outputs of MTB and DEC-MTB are completely flawed.

Algorithm 4 UTB

Initialization: m = output of SR with budget T /4 , l = k output of MTB with arms {1, . . . , m}, threshold τ , budget T /8 , r = k output of DEC-MTB with arms { m, . . . , K}, threshold τ , budget T /8 , Sample m, l, r, l -1, r + 1 each T /10 times if {μ l-1 < τ < μl } ∨ {|μ l -τ | ≤ μ m -τ } ∧ {μ r < τ < μr+1 } ∨ {|μ r -τ | ≤ μ m -τ } then Ŝ = { l, . . . , r} else Ŝ = ∅ end end return Q : Qk = 21 {k∈ Ŝ} -1 4.4. Concave case CTBP
In this section, we present the CTB algorithm, which is based on several applications of MTB.

We first define the following log-sets. Consider two integers l ≤ r and the associated set {l, l + 1, . . . , r}. We write S log l,r = {l, l + 1, l + 2, l + 2 2 , . . . , (l + 2 a ) ∧ (l + r)/2 }, where a is the smallest integer such that l + 2 a ≤ r ≤ l + 2 a+1 .

Algorithm CTB proceeds in phases. At phase i an interval {l i , . . . , r i } is refined from both ends by applying MTB and DEC-MTB. Algorithm CTB makes sure that with high probability, the regret of {l i , . . . , r i }, is bounded by ε i = (7/8) i . A very important idea of CTB is that it does not apply MTB and DEC-MTB on {l i , . . . , r i } but thanks to the concavity only on the log-sets associated to {l i , . . . , r i }. I.e. we will apply MTB on S log l i ,r i and DEC-MTB on -S log -r i ,-l i . This allows us to have much shorter phases as the two log-sets contain about log(r i -l i ) arms, instead of r i -l i arms.

We now describe formally CTB. The algorithm CTB consists of two sub-routines, an iterative application of MTB and then a decision rule based on the collected samples. These routines are respectively the for loop and if statement in the CTB algorithm.

Iterative application of MTB. For M > 0 and i < M we set

δ ( M ) i = 2 i-M ε i = 1 - 1 8 i τ i = τ - 3 4 ε i , T (i) 2 ( M ) = 2 14 log log K ε 2 i log 1 δ 2 i ,
and let M be the largest integer such that 6 i≤ M T

(i) 2 ( M ) ≤ T .
In what follows we write

δ i := δ (M ) i , T (i) 2 = T (i) 2 (M ).
CTB proceeds in M phases and at each it updates a set of three arms l i ≤ m i ≤ r iwhere m i is at the middle between l i and r i . It first samples all these arms -as well as

l i -1, r i + 1 -T (i)
2 times, and these samples are used to compute empirical means μp,i for p ∈ {m, l, r, l -1, r + 1} -corresponding respectively to the arms {m i , l i , r i , l i -1, r i + 1}. It then runs respectively MTB on S log l i ,r i and DEC-MTB on -S log -r i ,-l i , both with threshold τ i and budget T (i) 2 . These routines output l i+1 , r i+1 , and we define m i+1 as the middle between these arms. Decision rule The second sub routine of CTB is a decision rule between all l i , r i , for finding the right scale, based on the arms and empirical means collected in the previous routine. It takes the l i , r i that are as close as possible to arms m i far from threshold, but that are close to threshold -and it outputs a set Ŝ. Finally CTB classifies this set as being above threshold. Set I m = {m i : μm,i ≥ τ + 2ε i }, and

I l = {l i : μl,i ≥ τ -2ε i , μl-1,i ≤ τ - ε i 4 }, and I r = {r i : μr,i ≥ τ -2ε i , μr+1,i ≤ τ - ε i 4 }.
Algorithm 5 CTB Appendix A. Adaptation to the β-Hölder continuous case

Initialization: l 0 = 1, r 0 = K, m 0 = l 0 +r 0 2 for i = 1 : M do sample arms l i , l i -1, r i , r i + 1 and m i each T (i) 2 times. l t+1 = output k of MTB with arms S log l i ,r i , threshold τ i , budget T (i) 2 r t+1 = output k of DEC-MTB with arms -S log -r i ,-l i , threshold τ i , budget T (i) 2 m i+1 = l i+1 +r i+1 2 end if I m = ∅ then Set Ŝ = ∅ else Set l = max{k ∈ I l , k ≤ min i I m } Set r = min{k ∈ I r , k ≥ max i I m } Set Ŝ = { l, . . . ,
In this section we explain how our results can be adapted in a very simple way to the case where the arms are not {1, . . . , K} but the continuous set [0, 1], and where the mean sequence (µ k ) k∈[0,1] is now a function. We assume, on top of the fact that the distributions are supported in [0, 1], that the mean function µ is β-Hölder for some constant β > 0, i.e. in the case β ≤ 1 and a constant L > 0 such that ∀x, y ∈ [0, 1], |µ x -µ y | ≤ L|x -y| β . In this case, straightforward corollaries of our results imply the minimax regret rates in Table A.

In oder to get these results, it is sufficient to divide [0, 1] in M intervals of same size and adapt the results as usually done in the non-parametric litterature (by controlling the bias). We need to choose (i) M as

T log T 1 2β+1 in TBP , (ii) M as T 1/β in MTBP , (iii) M as T 1 2β+1
in UTBP , and (iii) M as T 1/β in CTBP . Interestingly, the rates of MTBP and CTBP do not depend on β -but note that β plays a role in the multiplicative constants in front of the rate, i.e. the smaller β, the larger the constant. On the other hand the rates in TBP and UTBP depend on β. Note that this is a phenomenon specific to the 1-dimensional case. Indeed, finding the level set of a monotone and of a convex function in dimension d is typically done at a much slower rate, depending on β and d.

Our results Unstructured Monotone Unimodal

Convex

TBP MTBP UTBP CTBP K-arms K log K T log K∨1 T K T log log K∨1 T β-Hölder log T T β 2β+1 log T ∨1 T 1 T β 2β+1 log log T ∨1 T
Table 2: Order of the minimax expected regret for the thresholding bandit problem, in the case of all four structural assumptions on the means of the arms considered in this paper. All results are given up to universal multiplicative constants. The first line concerns the K-armed setting of the main paper, and the second line concerns the X -armed setting where the set of arms is [0, 1] and where the function is β-Hölder (on top of the shape constraints).

Appendix B. Extension to σ 2 -sub-Gaussian for TBP and MTBP While in the main text for simplicity we only consider distributions bounded on the [0, 1] interval all proofs relating to the TBP and MTBP given in the appendix will extend to the sub Gaussian case. The lower bound for the CTBP will also extend to the sub Gaussian case. That is we redefine the setting as follows: the learner is presented with a K-armed bandit problem ν = {ν 1 , . . . , ν K }, where ν k is the unknown distribution of arm k. Let σ 2 > 0, all arms are assumed to be σ 2 -sub-Gaussian as described in the following definition, we write µ k for the mean of arm k.

Definition 7 (σ 2 -sub-Gaussian) A distribution ν of mean µ is said to be σ 2 -sub-Gaussian if for all t ∈ R we have,

E X∼ν e t(X-µ) ≤ exp σ 2 t 2 2 .
In particular the Gaussian distributions with variance smaller than σ 2 and the distributions with absolute values bounded by σ are σ 2 -sub-Gaussian.

The only adaptation that has to be made to accomodate this case in the MTB algorithm is to define

ε 0 = 2σ 2 log(48) T 2 .
Appendix C. Proof of Theorem 1

In the proof of all results in this section, we assume that the more general sub-Gaussian assumption described in Section B is satisfied -and not necessarily that the distributions of all arms are bounded on the [0, 1] interval. We explain in the proof how the lower bound can be straightforwardly adapted to distributions supported in [0, 1].

We denote the Kullback-Leibler divergence between two Bernoulli distributions Ber(p) and Ber(q) (with the usual conventions) by

kl(p, q) = p log p q + (1 -p) log 1 -p 1 -q .
Algorithm 6 Uniform for k = 1 : K do Sample arm k a total of T K times. Compute μk the sample mean of arm k. end return

Q : Qk = -1 if μk < τ 1 if μk ≥ τ
During this section we will prove Theorem 1 by first demonstrating a lower bound on expected regret across B and then showing that the Uniform algorithm achieves said lower bound. We first prove the following proposition to establish a lower bound.

Proposition 8 For any T ≥ 1 and any strategy π, there exists a unstructured bandit problem ν ∈ B, such that Rπ,

ν T ≥ 3 4 σ 2 max 2, log(K) K 8T .
Proof Without loss of generality we can assume that τ = 0. Fix some positive real number 0 < ε < 1. And consider the family of Gaussian bandit problems indexed by an vertex of the unite hyper-cube of dimension K, id est

Q ∈ {-1, 1} K νQ = N (Q 1 ε, σ 2 ), . . . , N (Q K ε, σ 2 ) ,
and note that if we wish to consider distributions supported in [0, 1] we can consider instead τ = 1/2 and νQ = B(1/2 + Q 1 ε), . . . , B(1/2 + Q K ε) , up to minor adaptations of the constants, and to considering τ = 1/2. Note that all these bandit problems belong to the set of unstructured bandit problems, νQ ∈ B. The regret in the bandit problem νQ of the strategy π can be rewritten as follows

Rν Q ,π T = ε E Q max k 1 { Qk =Q k } = ε(1 -E Q 1 { Q=Q} ) ,
where we denote by E Q the expectation under the bandit problem νQ . We will provide a minimax lower bound on the regret by using the classic Fano inequality. We first lower bound the minimax expected regret in the problem νQ by the Bayesian regret with a uniform distribution over the bandit problems νQ , max

Q Rν Q ,π T ≥ ε   1 - 1 2 K Q E Q 1 { Q=Q}   .
(1)

Let Q k be the transformation of Q that flip the sign of the coordinate k,

Q k a = Q a If a = k, -Q a If a = k .
Thanks to the contraction and the convexity of the relative entropy, see [START_REF] Gerchinovitz | Fano's inequality for random variables[END_REF], we have kl

      1 K K k=1 E Q k 1 { Q=Q k } , 1 K K k=1 E Q 1 { Q=Q k } ≤1/K       ≤ 1 K K k=1 E Q k N k (T ) ε 2 2σ 2 ,
where N k (T ) = T t=1 1 {kt=k} denotes the number of times in total arm k is sampled. Then using a refined Pinsker inequality (see [START_REF] Gerchinovitz | Fano's inequality for random variables[END_REF]) kl(x, y) ≥ (xy) 2 max 2, log(1/y) , we obtain

1 K K k=1 E Q k 1 { Q=Q k } ≤ 1 K + 1 K K k=1 E Q k N k (T ) ε 2 2σ 2 max 2, log(K) . ( 2
)
Therefore thanks to the concavity of the square root, we can average over all the bandit problems νQ

1 2 K Q 1 K K k=1 E Q k 1 { Q=Q k } ≤ 1 K + 1 2 K Q 1 K K k=1 E Q k N k (T )
ε 2 2σ 2 max 2, log (K) .

Now it remains to remark that by symmetry

Q K k=1 E Q k 1 { Q=Q k } = Q K k=1 E Q 1 { Q=Q } = K Q E Q 1 { Q=Q} , Q K k=1 E Q k N k (T ) = Q K k=1 E Q N k (T ) = Q T .
Hence from (2) we get

1 2 K Q E Q 1 { Q=Q} ≤ 1 K + T ε 2 2Kσ 2 max 2, log(K) ,
and then from (1) we obtain max

Q Rν Q ,π T ≥ ε 1 2 - T ε 2 2Kσ 2 max 2, log(K)
.

Choosing ε = Kσ 2 max 2, log(K) /(8T ) allows us to conclude.

We next prove the following proposition to establish a upper bound on the regret of the Uniform algorithm with high probability, Proposition 9 For any unstructured bandit problem ν ∈ B, any T ≥ K, any 0 < δ < 1, Uniform satisfies

P ν R Uniform, ν T ≥ 4σ 2 K T log 2K δ ≤ δ .

Proof

During the execution of the Uniform algorithm ∀k ∈ {1, ..., K} arm k is sampled T /K times with sample mean μk . Let δ > 0 and consider the event,

ξ := ∀ k ≤ K, |μ k -µ k | ≤ 4σ 2 K T log 2K δ .
Thanks to the Hoeffding inequality and an union bound this event occurs with probability greater than 1 -δ. As under the event ξ,

μk ∈ μk - 4σ 2 K T log 2K δ , μk + 4σ 2 K T log 2K δ ,
and the returning classification is

Q : Qk = -1 if μk < τ 1 if μk ≥ τ ,
we have with probability at least 1 -δ

R T = max {k∈[K]: Qk =Q k } ∆ k ≤ 4σ 2 K T log 2K δ .
We are now able to demonstrate a bound on the expected regret of the Uniform algorithm.

Proposition 10 For any unstructured bandit problem ν ∈ B, and any

T ≥ K, Uniform satisfies RUniform, ν T ≤ 7 σ 2 log(2K)K T .
Proof By application of Theorem 9, for ε > 0 we have,

P (R T ≥ ε) ≤ 2K exp -ε 2 T 4σ 2 K .
Hence for ε 0 = 4σ 2 log(2K)K/T integrating these probabilities we obtain an upper bound on the expected simple regret

RT ≤ √ 2ε 0 + +∞ √ 2ε 0 exp -(ε 2 -ε 2 0 ) T 2σ 2 K dε ≤ √ 2ε 0 + +∞ 0 exp -ε 2 T 8σ 2 K dε = 8σ 2 log(2K)K T + 2πσ 2 K T ≤ 7 σ 2 log(2K)K T .
Setting σ = 1, Theorem 1 follows directly from a combination of Propositions 10 and 8.

Proposition 11 For any T ≥ 1 and any strategy π, there exists a structured bandit problem

ν ∈ B m , such that Rπ, ν T ≥ 1 8 σ 2 max 2, log(K) 8T .
Proof We will proceed as in the proof of Proposition 8. Fix some positive real number 0 < ε < 1. Without loss of generality we can assume that τ = ε/2. And consider the family of Gaussian bandit problems νk indexed by k ∈ {0, . . . , K}, such that for all k ∈ {0, . . . , K}, l ∈ [K],

ν k l = N (0, σ 2 ) if k < l N (ε, σ 2 ) else .
Note that if we wish to consider distributions supported in [0, 1] we can consider instead τ = 1/2 + ε/2 and

ν k l = B(1/2) if k < l B(1/2 + ε) else .
up to minor adaptations of the constants, and to considering τ = 1/2. Note that all these bandit problems belong to the set of structured bandit problems, νk ∈ B. Following the same steps as in the proof of Proposition 8 one can lower bound the maximum of the expected regrets over all the bandit problems introduced above, max

k∈[K] Rν k ,π T ≥ ε 2 1 - 1 K K k=1 E k 1 { Q=Q k } ,
where we denote by E k the expectation and by Q k the true classification in the problem νk . Thanks to the contraction and the convexity of the relative entropy we have kl

      1 K K k=1 E k 1 { Q=Q k } , 1 K K k=1 E 0 1 { Q=Q k } ≤1/K       ≤ 1 K K k=1 K l=k E k N l (T ) ε 2 2σ 2 ≤ T ε 2 2σ 2 .
Then using a refined Pinsker inequality kl(x, y) ≥ (x -y) 2 max 2, log(1/y) , we obtain

1 K K k=1 E k 1 { Q=Q k } ≤ 1 K + T ε 2 2σ 2 max 2, log(K)
.

Hence combining the last three inequalities we get max

k∈[K] Rν k ,π T ≥ ε 2 1 2 - T ε 2 2σ 2 max 2, log(K)
.

Choosing ε = σ 2 max 2, log(K) /(8T ) allows us to conclude.

We next prove the following to proposition to establish an upper bound on the simple regret of the MTB algorithm with high probability and then prove Corollary 13 to establish an upper bound on the expected regret of the MTB algorithm. For Proposition 12 we consider a more general set of problems, given ε > 0, define,

B * ,ε m := {B : (min(|µ i -τ |, ε) sign(µ i -τ )) k≤K is an increasing sequence} . Note that for all ε > 0, B m ⊂ B * ,ε
m , hence all results will hold also in the unaltered monotone setting.

Proposition 12 For any ε > ε 0 and any problem ν ∈ B * ,ε m , and any T > 6 log(K), the MTB Algorithm will achieve the following bound on simple regret,

P ν (R MTB, ν T ≥ ε) ≤ min exp - 3 log(K) 4 , 72 log(K) exp - T ε 2 216σ 2 log(K)
.

Corollary 13 For any problem ν ∈ B m and any T ≥ 12 log(K), the MTB algorithm will achieve the following bound on expected regret,

RMTB, ν T ≤ 80 σ 2 log(K) T .
The proof of Proposition 12 and Corollary 13 is structured in several steps which we will first summarise. For a level ε > 0 we define a set of "good nodes" containing "ε-good arms", those which when outputted will achieve the bound R T < 2ε. In Proposition 16 we prove these nodes form a "consecutive tree", see Definition 15. At time t we say we have a "favourable event" if all sampled empirical means are within ε of the true mean, In this case we say the algorithm makes a "good decision", see (10). In Lemma 19 we prove that on every good decision we move towards the set of good arms or remain within them. Lemma 20 then shows that provided we make enough good decisions the number of good arms in S is large. We can then bound the probability of making a high proportion of good decisions, see Lemma 21, to give an upper bound on regret. This in combination with a second upper bound, Lemma 23, will give our result.

Step 0: Definitions and Lemmas We will use the following definitions.

Definition 14 We define the subtree ST (v) of a node v recursively as follows: v ∈ ST (v) and ∀ q ∈ ST (v), L(q), R(q) ∈ ST (v) .

Definition 15 A consecutive tree U with root u root is a set of nodes such that u root ∈ U and

∀v ∈ U : v = u root , P (v) ∈ U.
with the additional condition,

root ∈ U ⇒ u root = root
where root is the root of the entire binary tree.

We define Z ε , the set of ε-good nodes, as the union of the two sets

Z ε 1 := {v : ∃k ∈ {l, m, r} : |µ v(k) -τ | ≤ ε} , (3)
Z ε 2 := {v : v(r) = v(l) + 1; µ v(l) ≤ τ ≤ µ v(r) }\Z ε 1 , (4)
that is 5) we have |Z ε | = 1 and the proposition is trivially verified. Hence we assume Z ε = Z ε 1 . Consider v ∈ Z ε , such that P (v) / ∈ Z ε , there is at least one such node. We first prove that v is unique. As v ∈ Z ε = Z ε 1 we know that ∃k ∈ {l, m, r} :

Z ε := Z ε 1 ∪ Z ε 2 . It is important to note that Z ε 2 = ∅ ⇒ |Z ε | = 1 . (5) Proposition 16 Z ε is a consecutive tree with root z ε root the unique element v ∈ Z ε , such that P (v) / ∈ Z ε . Proof If Z ε 2 = ∅ by (
µ v(k) -τ ≤ ε . ( 6
)
Now since v(l), v(r) ∈ P (v) and P (v) / ∈ Z ε , it follows that, thanks to (6),

∀k ∈ {l, r} : µ v(k) -τ > ε |µ v(m) -τ | ≤ ε .
For node q = v satisfying the same properties, assume that v(m) < q(m) without loss of generality. With this assumption we have,

v(r) ≤ v(m) ≤ q(l) ≤ q(m) ,
however, as the sequence (min

(|µ i -τ |, ε) sign(µ i -τ )) k≤K is increasing we must have |µ v(r) -τ | ≤ ε and |µ q(l) -τ | ≤ ε, a contradiction. Hence v = q,
and thus v is unique which implies ∀q ∈ Z ε : q = v, P (q) ∈ Z ε .

At time t we define w ε t as the node of maximum depth whose subtree contains both v t and an "ε-good node" belonging to Z ε . Formally, for t ≤ T 1 ,

w ε t := arg max {w:ST (w)∩Z ε =∅ & vt∈ST (w)} |w| .
Lemma 17 The node w ε t is unique and

w ε t = arg min {w:ST (w)∩Z ε =∅ & vt∈ST (w)} |v t | -|w| + (|z ε root | -|w|) + . (7)
Proof At time t consider, a node q ε t which also satisfies 7, giving

|v t | -|w ε t | + (|z ε root | -|w ε t |) + = |v t | -|q ε t | + (|z ε root | -|q ε t |) + . As v t ∈ ST (w ε t
) and v t ∈ ST (q ε t ) we can assume without loss of generality

q ε t ∈ ST (w ε t ) with |q ε t | ≥ |w ε t |. Thus, |v t | -|q ε t | ≤ |v t | -|w ε t | , and therefore, (|z ε root | -|q ε t |) + ≥ (|z ε root | -|w ε t |) + , which implies, |q ε t | ≥ |w ε t |, therefore |q ε t | = |w ε t | and as q ε t ∈ ST (w ε t ), we have q ε t = w ε t .
For t ≤ T 1 we define D ε t as the distance from v t to Z ε , it is taken as the length of the path running from v t up to w ε t and then down to an ε-good node in Z ε . Formally, we have

D ε t := |v t | -|w ε t | + (|z ε root | -|w ε t |) + .
Note the following properties of D ε t and w ε t ,

ST (v t ) ∩ Z ε = ∅ ⇒ v t = w ε t , (8)
D t = 0 ⇒ v t = w ε t And w ε t , v t ∈ Z ε . (9)
Let S ε t denote the list produced by an execution of algorithm Choose with parameter ε ≥ ε 0 . We define W ε as the set of ε-good arms

W ε := k ∈ [K] : ∆ k ≤ 3ε OR µ k-1 < τ < µ k ,
and at time t the counter G ε t , tracking the number of 3ε-good arms in S 2ε t ,

G ε t := k ∈ S 2ε t : k ∈ W 3ε . ( 10
)
Note that if k belongs to this set then we suffer at most a regret of 3ε. We define also the favorable event where the estimates the means are close to the true ones for all the arms in v t ,

ξ ε t := ∀k ∈ {l, m, r}, μk,t -µ vt(k) ≤ ε . ( 11
)
Step 2: Actions of the algorithm on all iterations After any execution of algorithm Explore and subsequent execution of algorithm Choose with parameter ε, note the following,

• for t ≤ T 1 , v t and v t+1 are separated by at most one edge, i.e.

v t+1 ∈ {L(v t ), R(v t ), P (v t )} , (12)
• for t ≤ T 1 , |S 2ε t | ≤ |S 2ε t+1 | ≤ |S 2ε t | + 1 . ( 13
)
Lemma 18 On execution of algorithm Explore and algorithm Choose with parameter ε > 0 for all t ≤ T 1 we have the following,

D ε t+1 ≤ D ε t + 1, ( 14
)
G ε t+1 ≥ G ε t . ( 15
)
Proof As the algorithm moves at most 1 step per iteration, see ( 12), for t ≤ T 1 , it holds

||v t | -|w ε t || ≥ ||v t+1 | -|w ε t || -1 .
Noting that,

D ε t = ||v t | -|w ε t || + (|z ε root | -|w ε t |) + ≥ ||v t+1 | -|w ε t || + (|z ε root | -|w ε t |) + -1 ≥ |v t+1 | -w ε t+1 + |z ε root | -|w ε t+1 | + -1 = D ε t+1 -1 ,
where the third line comes from the definition of w ε t+1 , see (7), we obtain D ε t+1 ≤ D ε t + 1. By (13) we have, for t ≤ T 1 ,

|S 2ε t | ≤ |S 2ε t+1 | ≤ |S 2ε t | + 1 , hence G ε t+1 ≥ G ε t .
Step 3: Actions of the algorithm on ξ ε t Lemma 19 On execution of algorithm Explore and algorithm Choose with parameter ε > 0 for all t ≤ T 1 , on ξ ε t , we have the following,

D ε t+1 ≤ max(D ε t -1, 0) , (16)
G ε t+1 ≥ G ε t + 1 {D ε t =0} . ( 17
)
Proof We first prove (17). Note that if the arm v t (k) is added in S 2ε t+1 then either |μ k,t -τ | ≤ 2ε or v t (k) = v t (r) = v t (l) + 1 and μl,t + ε ≤ τ ≤ μr,t . Thus, on ξ ε t , we obtain in the first case ∆ vt(k) ≤ 3ε and in the second case

v t (k) = v t (l) = v t (r) -1 and µ vt(l) + ε ≤ τ ≤ µ vt(r) -ε . In both case we have v t (k) ∈ W 3ε , hence G ε t+1 ≥ G ε t + 1. It remains to prove that, when D t = 0, an arm is effectively added in S 2ε t+1 . If D ε t = 0 then we know v t ∈ Z ε . If v t ∈ Z ε 1 then under ξ ε t there exists k ∈ {l, m, r} such that |μ k,t -τ | ≤ 2ε. Otherwise we know that v t (l) = v t (r) -1 and µ vt(l) + ε ≤ τ ≤ µ vt(r) -ε ,
which implies on ξ ε t that μl,t ≤ τ ≤ μr,t .

In both case an arm is added to S 2ε t+1 . Now we prove ( 16). Note that on the favorable event ξ ε t , we have ∀k ∈ {l, m, r},

µ vt(k) ≥ τ + ε ⇒ μk,t ≥ τ , ( 18
)
µ vt(k) ≤ τ -ε ⇒ μk,t ≤ τ . ( 19
)
We consider the following three cases: 18) and ( 19), under ξ ε t , we get τ / ∈ [μ l,t , μr,t ], and therefore v t+1 = P (v t ). Since in this case we are getting closer to the set of ε-good nodes by going up in the tree we know that w ε t = w ε t+1 . Thus thanks to Lemma 17, under ξ ε t ,

• If τ / ∈ µ vt(l) + ε, µ vt(r) -ε . From (
D ε t+1 = |v t+1 |-w ε t+1 + |z ε root | -|w ε t+1 | + = |v t |-1-|w ε t |+(|z ε root | -|w ε t |) + = D ε t -1 . • If τ ∈ µ vt(l) + ε, µ vt(r) -ε and v t / ∈ Z ε .
Note that in this case v t can not be a leaf and we just need to go down in the subtree of v t to find an ε-good node, id est w t = v t . Since v t / ∈ Z ε , without loss of generality, we can assume for example µ vt(m) > τ + ε. From ( 18) and ( 19), under ξ ε t , we then have τ ∈ [μ l,t , μr,t ] and μm,t ≥ τ . Hence algorithm Explore goes to the correct subtree, v t+1 = L(v t ). In particular we also have for this node τ ∈ µ v t+1 (l) -ε, µ vt(m) + ε , therefore it holds again w t+1 = v t+1 . Thus combining the previous remarks we obtain thanks to Lemma 17, under ξ ε t ,

D ε t+1 = (|w t+1 | -|z ε root |) + = (|w t | -|z ε root |) + -1 = D ε t -1 . • If τ ∈ µ vt(l) + ε, µ vt(r) -ε and v t ∈ Z ε .
We distinguish two cases: Z ε 2 is empty or not. In both cases we will show that, under ξ ε t , v t+1 ∈ Z ε and thus

D ε t+1 = D ε t = 0 .
Hence it remains to consider these two cases:

-If Z ε 2 = ∅.
Via the definition of Z ε 2 , see (4), and the fact Z ε 1 = ∅, v t is a leaf with µ vt(r) ≤ τ -ε and µ vt(l) ≥ τ + ε. Hence from ( 18) and ( 19) we have μl,t ≤ τ ≤ μr,t . Therefore by the action of algorithm Explore we will stay in the same node

v t+1 = v t . -Else Z ε 2 = ∅. If µ vt(m) ∈ [τ -ε, τ + ε], we have R(v t ), L(v t ), P (v t ) ∈ Z ε hence trivially v t+1 ∈ Z ε . Else we have µ vt(m) / ∈ [τ -ε, τ + ε].
Without loss of generality we assume µ vt(m) > τ + ε. This implies that µ vt(r) > τ + ε and since

v t ∈ Z ε = Z ε 1 it holds µ vt(l) ∈ [τ -ε, τ + ε].
Thus, under ξ c t we then get as previously τ ∈ [μ l,t , μr,t ] and μm,t ≥ τ . Therefore by the action of algorithm Explore we will go to the left child v t+1 = L(v t ) ∈ Z ε .

Step 4: Lower bound on G ε T 1 +1 We denote by ξε t the complement of ξ ε t .

Lemma 20 For any execution of algorithm Explore and subsequent execution of Choose with parameter ε ≥ ε 0 ,

G ε T 1 +1 ≥ 3 4 T 1 -2 T 1 t=1 1ξε t .
Proof Combining ( 16) and ( 14) from Lemma 18 and Lemma 19 respectively we have

D ε t+1 ≤ D ε t + 1ξε t -1 ξ ε t 1 {D ε t >0} = D ε t + 21ξε t -1 + 1 ξ ε t 1 {D ε t =0} .
Using this inequality with ( 17) we obtain

G ε T 1 +1 = T 1 t=1 G ε t+1 -G ε t ≥ T 1 t=1 1 ξ ε t 1 {D ε t =0} ≥ T 1 t=1 D ε t+1 -D ε t -21 ξ ε t + 1 ≥ T 1 -D ε 1 -2 T 1 t=1 1 ξt,ε ≥ 3 4 T 1 -2 T 1 t=1 1 ξt,ε ,
where we used in the last inequality the fact that D 1 ≤ log 2 (K) and that log 2 (K) ≤ T 1 /4 by definition of T 1 .

Step 5: First high probability bound on the regret Lemma 21 For all ε ≥ ε 0 , following the execution of algorithm MTB,

P(R T > 3ε) ≤ e -3 log(K)/4 . (20)
Before proving Lemma 21 we need to show that the number of times a favorable events ξ ε 0 t occurs is not to small with high probability. Precisely in the following lemma we upper bound the probability of the event

ξ ε 0 = T 1 t=1 1 ξε 0 t ≤ T 1 8 .
Lemma 22 For any execution of algorithm Explore and subsequent execution of Choose with parameter ε 0 , P( ξε 0 ) ≤ e -3 log(K)/4 .

Proof Let F t be the information available at and including time t. Thanks to the Hoeffding inequality and the choice of T 2 , we have for all k ∈ {l, m, r},

P μk,t -µ vt(k) ≥ ε 0 |F t-1 ≤ 2 exp - T 2 ε 2 0 2σ 2 ≤ 1 24 ,
hence by a union bound P( ξε 0 t |F t-1 ) ≤ 1/8. Then the Azuma-Hoeffding inequality applied to the martingale

T 1 t=1 1 ξε 0 t -P( ξε 0 t |F t-1 ) ,
with respect to the filtration (F t ) t≤T 1 allows us to conclude

P T 1 t=1 1 ξε 0 t -P( ξε 0 t |F t-1 ) ≥ T 1 4 ≤ e -2T 1 /16 ≤ e -3 log(K)/4 , (21)
where we used that T 1 = 6 log(K) .

We are now ready to prove Lemma 21.

Proof [Proof of Lemma 21] We first prove it for ε = ε 0 . Thanks to Lemma 20 on the event ξ ε 0 we have

G ε 0 T 1 +1 ≥ 3 4 T 1 -2 T 1 t=1 1 ξε 0 t ≥ T 1 2 .
But thanks to the choice of ε ≥ 2ε 0 we know that

S 2ε 0 T 1 +1 ⊂ S ε T 1 +1 .
Thus there is more than the half of the arms of S ε T 1 +1 in W 3ε 0 , since this list is at most of size T 1 . In particular this implies that k = Median(S ε (6). Therefore, on the event ξ ε 0 we have

T 1 +1 ) ∈ W 3ε 0 . Indeed W 3ε 0 is a segment in [K], see
R T ≤ 3ε 0 .
Lemma 22 allows us to conclude, for ε ≥ ε 0 ,

P(R T > 3ε) ≤ P(R T > 3ε 0 ) ≤ e -3 log(K)/4 .
Step 6: Second high probability bound on the regret Lemma 23 For all ε ≥ ε 0 , following the execution of algorithm MTB,

P(R T > 3ε) ≤ 72 log(K) exp - T ε 2 36σ 2 log(K) . ( 22
)
Proof We consider the event where all the favorable events ξ ε t occur,

ξ ε a := T 1 t=1 ξ ε t .
On this event ξ ε a thanks to Lemma 20 we have

G ε T 1 +1 ≥ 3 4 T 1 -2 T 1 t=1 1ξε t = 3 4 T 1 , hence S 2ε
T 1 +1 = ∅ is not empty. Furthermore following the same arguments of the beginning of the proof of Lemma 19 all arms in the list S 2ε

T 1 +1 = ∅ are also in W 3ε . Then noting that by construction ε = inf

ε ≥2ε 0 : S ε T 1 +1 =∅ ε , we get ε ≤ 2ε therefore S ε T 1 +1 ⊂ S 2ε T 1 +1
. Thanks to the remarks above we know that k ∈ W 3ε thus on ξ ε a , R T ≤ 3ε .

The Hoeffding inequality in combination with a union bound allows us to conclude,

P( ξε a ) ≤ T 1 t=1 E P( ξε t |F t-1 ) ≤ 72 log(K) exp - T 2 ε 2 2σ 2 (23) ≤ 72 log(K) exp - T ε 2 36σ 2 log(K) . ( 24
)
Conclusion The proof of Proposition 12 is straightforward combining Lemma 21 and Lemma 23. Thus we obtain for all ε ≥ 3ε 0 ,

P(R T ≥ ε) ≤ min exp - 3 log(K) 4 , 72 log(K) exp - T ε 2 324σ 2 log(K)
.

We can integrate the high probability upper bound obtained in Proposition 12 to prove Corollary 13.

Proof [Proof of Corollary 13.] Thanks to Proposition 12, for ε 1 = log(72 log(K)) 324σ 2 log(K)/T , we have

E[R T ] ≤ ε 0 + (ε 1 -ε 0 )e -3 log(K)/4 + +∞ ε=ε 1 72 log(K) exp - T ε 2 324σ 2 log(K) ≤ 36σ 2 log(48) log(K) T +     log(72 log(K)) K 3/4 ≤3 + √ π 2     324σ 2 log(K) T ≤ 80 σ 2 log(K) T .
Setting σ = 1 Theorem 2 follows directly from Proposition 11 and Corollary 13.

Note that all these bandit problems belong to the set of unimodal bandit problems, νk ∈ B u . Following the same steps as in the proof of Proposition 8 one can lower bound the maximum of the expected regrets over all the bandit problems introduced above, max

k∈[K] Rν k ,π T ≥ ε 2 1 - 1 K K k=1 E k 1 { Q=Q k } ,
where we denote by E k the expectation and by Q k the true classification in the problem νk . Thanks to the contraction and the convexity of the relative entropy we have kl

      1 K K k=1 E 0 1 { Q=Q k } ≤1/K , 1 K K k=1 E k 1 { Q=Q k }       ≤ 1 K K k=1 E 0 N k (T ) ε 2 2σ 2 ≤ T ε 2 2Kσ 2 .
Then using the Pinsker inequality kl(x, y) ≥ 2(x -y) 2 , we obtain

1 K K k=1 E k 1 { Q=Q k } ≤ 1 K + T ε 2 4σ 2 K .
Hence combining the last three inequalities we get max

k∈[K] Rν k ,π T ≥ ε 2 1 2 - T ε 2 4σ 2 K .
Choosing ε = 4σ 2 K/T allows us to conclude.

Proposition 25 There exists a universal constant c uni > 0 such that for any unimodal bandit problem ν ∈ B u , UTB satisfies

RCTB, ν T ≤ c uni K n .

Proof

Step 1: Definitions Write ∆ = µ * -µ m,

and ε = |μ l -µ l| ∨ |μ r -µ r| ∨ |μ m -µ m| ∨ |μ r+1 -µ r+1 | ∨ |μ l-1 -µ l-1 |.
and we write R (l) for the regret of MTB on {1, . . . , m} when played by algorithm UTB, and R (r) for the regret of DEC-MTB on { m, . . . , K} when played by algorithm UTB. Let us also write R T = R UTB,ν T for the regret associated to the outputted set Ŝ.

E (l) = {|μ l -τ | ≤ μ m -τ } ∪ {μ l-1 ≤ τ ≤ μl },
and define similarly E (r) replacing l by r. Define

E = {E (l) ∩ E (r) }.
Step 2: Bound on the regret on the events Assume without loss of generality that R (l) ≥ R (r) . By definition of the algorithm this implies under this condition that

R T = R (l) 1 {E} + (µ * -τ ) + 1 {E C } , which implies directly R T ≤ R (l) 1 {E} + (µ m -τ ) + 1{E C } + ∆. ( 25
)
Note that

E ⊂ {|µ l -τ | ≤ µ m -τ + 2ε} ∪ {µ l-1 -ε ≤ τ ≤ µ l + ε}.
And so since R (l) ≤ |µ l -τ |, we have

R (l) 1 {E} ≤ R (l) ∧ (µ m -τ ) + + 2ε. ( 26
)
Note also that on E C and under our condition R (l) ≥ R (r) , we have that

E C ∩ {R (l) ≥ R (r) } ⊂ {|µ l -τ | ≥ µ m -τ -2ε}.
And on E C ∩ {R (l) ≥ R (r) }, we have that R (l) ≥ (µ l -τ ) + -2ε, which leads to under our assumption R (l) ≥ R (r)

(µ m -τ ) + 1 {E C } ≤ R (l) ∧ (µ m -τ ) + + 2ε. ( 27
)
So we have combining ( 26) and ( 27) all cases in (25

) that if R (l) ≥ R (r) R T ≤ (R (l) ) ∧ (µ m -τ ) + + 2ε + ∆.
Considering similarly the case R (r) ≥ R (l) gives

R T ≤ (R (l) ∨ R (r) ) ∧ (µ m -τ ) + + 2ε + ∆.
Step 3: Integration of the regret Consider ε 0 = 4c SR K n . Consider the event where (µ m -τ ) + = ε ≥ ε 0 . On this event, and since the sequence of arms's means is unimodal, MTB satisfies the assumptions of Corollary 31 for ε and a set of arms {1, . . . , m}, and integrating over the tail probability between ε 0 and ε -conditional to we know that there exists an absolute constant C > 0 such that

E[R (l) ∧ ε|(µ m -τ ) + = ε] ≤ C log K + 1 n .
Similarly

E[R (r) ∧ ε|(µ m -τ ) + = ε] ≤ C log K + 1 n .
where we denote by E l the expectation and by Q l the true classification in the problem νl .

In particular we have Q l = [-1, . . . , -1, 1, . . . , 1] where the first one is at position k l .

Let k := max{j : Qj = -1} be the estimated k l and Q an other possible answer exploiting the structure of the problems

Q k = -1 if j ≤ k 1 else .
Then we have for all l ∈ [L] it holds

R l T := max k∈[K] ∆ l k 1 { Qk =Q l k } ≥ max k∈[K] ∆ l k 1 { Q k =Q l k } , indeed if k ≥ k l then R l T = ε
and since for all k the gaps are smaller than ε ≥ ∆ l k the inequality is trivially true. Else k < k l , then for all k ≤ k we have

Q k = -1 thus 1 Qk =Q l k ≥ 1 Q k =Q l k
and since Qk = Q k for all k ≥ k the inequality is verified. Now let l = arg min l∈[L]: k l > k l be an estimate for the index of the problem. Then we have max

k∈[K] ∆ l k 1 { Q k =Q l k } ≥ max k∈[K] ∆ l k 1 {Q l k =Q l k } .
Indeed using the same arguments as above, if k ≥ k l then max k∈

[K] ∆ l k 1 { Q k =Q l k } = ε. Else k < k l , then for all k, 1 { Q k =Q l k } ≥ 1 {Q l k =Q l k } . Finally, we prove that max k∈[K] ∆ l k 1 {Q l k =Q l k } ≥ ε 2 1 { l =l} , indeed, if l > l then max k∈[K] ∆ l k 1 {Q l k =Q l k } = ε and if l < l we have using k l+1 = 2k l, max k∈[K] ∆ l k 1 {Q l k =Q l k } ≥ max k∈[K] ∆ l+1 k 1 {Q l k =Q l+1 k } ≥ ε - k l k l+1 ε = ε 2 .
Combining all the previous inequalities we obtain max

l∈[L] Rν l ,π T ≥ ε 2 max l∈[L] E l 1 { l =l} ≥ ε 2   1 - 1 L l∈[L] E l 1 { l=l}   .
We can conclude as previously. Thanks to the contraction and the convexity of the relative entropy we have kl

      1 L L l=1 E l 1 { l=l} , 1 L L l=1 E 0 1 { l=l} ≤1/L       ≤ 1 L L l=1 K k=1 E l N k (T ) ε 2 2σ 2 ≤ T ε 2 2σ 2 .
Then using a refined Pinsker inequality kl(x, y) ≥ (x -y) 2 max 2, log(1/y) , we obtain

1 L L l=1 E l 1 { l=Q l } ≤ 1 L + T ε 2 2σ 2 max 2, log(L)
.

Hence combining the last three inequalities we get max (L) .

l∈[L] Rν l ,π T ≥ ε 1 2 - T ε 2 2σ 2 max 2, log
Choosing ε = σ 2 max 2, log(L) /(8T ) allows us to conclude.

Proposition 27 There exists a universal constant c conv > 0 such that for any convex bandit problem ν ∈ B c , CTB satisfies

RCTB, ν T ≤ c conv log log K ∨ 1 T .
Before going on to prove Proposition 27 we first show the following. Proof We just prove that the sequence is monotonically increasing on [p : p+q 2 ], the other case is proven similarly.

Lemma 28 Consider 1 ≤ p ≤ q ≤ K, ε > 0, τ ∈ R. Consider any 1 ≤ p < q ≤ K, such that, µ p+q 2 ≥ τ + 1 8 ε . (28)
Since (µ k ) k≤K is concave, we know that there exists k * ∈ {1, . . . , K} such that (µ k ) k≤k * is increasing and (µ k ) k≥k * is decreasing.

• If k * ∈ [p, p+q 2 ], and since (28) holds, we have that ∀k ∈ [k * , p+q 2 ], µ k -τ ≥ ε/8. This implies the result.

• If k * ∈ [p : p+q 2 ],
we have either (i) that µ k is increasing on the interval which implies the result or (ii) that µ k is decreasing on the interval. In case (ii), we know by ( 28) that ∀k ∈ [p, p+q 2 ], µ k -τ ≥ ε/8. This implies the result.

Lemma 29 Let ε > 0, τ ∈ R. For any 1 ≤ p ≤ q ≤ K, such that,

µ p ∧ µ q ≥ τ -ε , µ p+q 2 ≤ τ - 5 8 ε ,
we have that, ∀k ∈ {p, . . . , q} that µ k ≤ τ -ε.

Case 2 Consider the case where MTB outputs l i+1 such that,

|µ l i+1 -τ i | ≤ ε i /8.
From Lemma 28 we have that the sequence (µ k ) k<K is increasing on

[τ i -1 8 ε i , τ i + 1 8 ε i ] Therefore ∀k < l i+1 , µ k ≤ µ l i+1 . Hence ξ L i+1 holds.
And so we have as desired that

ξ (L) i+1 ∩ ξ i ∩ E i ⊂ {|µ l i+1 -τ i | ≤ ε i /8 OR µ l i+1 + ε i /8 < τ i < µ l i+1 -ε i /8} ∩ ξ i ∩ E i . This concludes the proof. Proposition 33 We have that for i ≤ M P ξ (A) i+1 ξ i ∩ E c i = 1. Proof On ξ i ∩ E c i , we know that m i = l i +r i 2 and µ m i ≤ τ i + 1 8 ε i = τ - 5 8 ε i , and
µ l i ∨ µ r i ≥ τ -ε i ,
and so by Lemma 29 we conclude that for any k ≤ K, µ k < τ -1 8 ε i . And so ξ (A) i+1 holds.

Corollary 34 We have that

P(ξ i+1 |ξ i ) ≥ 1 -2δ i
Proof This holds by combining Propositions 32 and Proposition 33.

Hence by Corollary 34 and for any I ≤ M we have,

P(∩ i≤I ξ i ) ≥ i≤I (1 -2δ i ) ≥ 1 -2 I i=1 δ i .
For I, i ≤ M consider the event

η I i := |μ m,i -µ m i | ∨ |μ l,i -µ l i | ∨ |μ r,i -µ r i |∨ |μ l-1,i -µ l i -1 | ∨ |μ r+1,i -µ r i +1 | ≤ 1 16 ε i ∨ ε I , (31)
which via Azuma's martingale inequality occurs with probability greater than,

1 -10 exp - 1 2 T (i) 2 ε 2 i ≥ 1 -10δ i . (32)
Proposition 35 Fix I ≤ M and assume that there exists k such that µ k > τ -1 8 ε I . On ξ I , we have that {k : µ k ≥ τ } ⊂ {l I , . . . , r I } ⊂ {k : µ k ≥ τ -ε I }.

Proof First note that under the condition µ k > τ -1 8 ε I we have that ξ Proposition 38 Fix I ≤ M , and assume that m I ∈ I m . On ξ I ∩ ∩ i≤I η I i , we have that {k :

µ k ≥ τ + 4ε i } ⊂ ∅ ⊂ { l, . . . , r} ⊂ {k : µ k ≥ τ -ε I }. Proof On ξ I ∩ ∩ i≤I η I i
we have from Proposition 37 that I m ⊂ {l I , . . . , r I ] and that l I ∈ I l , r I ∈ I r . This implies that on ξ I ∩ ∩ i≤I η I i , { l, . . . , r} ⊂ {l I , . . . , r I }. Together with Propositions 35 and 36 this implies that on ξ I ∩ ∩ i≤I η I i we have { l, . . . , r} ⊂ {k :

µ k ≥ τ -ε I }.
Moreover, on η I I , we have by the assumption of Proposition 38 that µ m I ≤ τ + 17 8 ε I . Together with Proposition 35 and 36 and Lemma 29, this implies that on ξ I ∩ η I i , ∀k ≤ K, µ k ≤ τ + 4ε I . This concludes the proof with the fact that { l, . . . , r} ⊂ {l I , . . . , r I }.

Proposition 39 Fix I ≤ M , and assume that m I ∈ I m . On ∩ i≤I ξ i ∩ ∩ i≤M η I i , we have that {k :

µ k ≥ τ + ε I } ⊂ { l, . . . , r} ⊂ {k : µ k ≥ τ -ε I }.
Proof As in the proof of Proposition 38, we have on ξ I ∩ ∩ i≤I η I i that it holds that { l, . . . , r} ⊂ {k : µ k ≥ τ -ε I }. Under the event η I I as l ∈ I l , r ∈ I r we have that,

µ l-1 < τ + ε I & µ r+1 < τ + ε I .
Moreover, on η I I , we have by the assumption of Proposition 39 that µ m I ≥ τ + 15 8 ε I . Therefore, as µ m I ∈ { l -1, . . . , r + 1} via the concavity of (µ k ) k<K we have that {k : µ k ≥ τ + ε I } ⊂ { l, . . . , r}. This concludes the proof.

Proof [Proof of Proposition 27] Let I ≤ M . Combining Propositions 38 and 39, we have on

∩ i≤I ξ i ∩ ∩ i≤M η I i that {k : µ k ≥ τ + 4ε I } ⊂ { l, . . . , r} ⊂ {k : µ k ≥ τ -ε I }. Note that P ∩ i≤I ξ i ∩ ∩ i≤M η I i ≥ 1 -10 i≤I δ i - i≤I δ i -(M -I)δ I .
We have by definition of δ i , T

(i) 2 that δ i ≤ min 1 log(K) 3/4 , 72 log log(K)δ 2 i ,
and also we have that δ i = 2 i-M so that whenever M -i ≥ log log log(K), we have that log log(K)δ 2 i ≤ δ i . And so

i≤I δ i ≤ 144δ i ,
since when M -i ≥ log log log(K), we have 72δ i ≥ 1 log(K) 3/4 . And so

P ∩ i≤I ξ i ∩ ∩ i≤M η I i ≥ 1 -164δ I -(M -I)δ I = 1 -(M -I + 164)2 I-M .
Thus for any i ∈ {0, . . . , M } we have

P R T ≥ 4 7 8 M -i ≤ (i + 164)2 -i ≤ 200 2 3 i .
This concludes the proof by summing over I for finding the expected regret, and noting that there exists a universal constant C > 0 such that 7

8 M = ε M ≤ C log log K T , by definition of M .
with error bounded by O( K log(K/δ)/T ) -where the log(K/δ) term comes from a union bound over all K arms -and prove that on this event the regret is bounded. The lower bound is slightly less classical when it comes to the bandit literature, and is close in spirit to the use of a sequential version of Fano's inequality -stating effectively that the union bound in the analysis of the event on the means is tight.

In the MTBP , however, both the algorithm MTB and its proof are far less classical. As discussed in Section 1 a naive, yet suboptimal, approach to the MTBP is a binary search. At each step we sample an arm O(T / log(K)) times and then decide to go left or right. This kind of strategy relies on making a correct decision at each step, and requires an event based analysis. The event is here that all O(log(K)) sampled arms have their empirical means that concentrate around the true means at rate log(K) log(log(K)/δ)/T -the log(log(K)/δ) term coming from the union bound. This results in a regret of order log(K) log(log(K))/T , which is strictly sub-optimal. With this in mind we consider a different algorithm that performs a 'corrective' version of the binary search, i.e. a version where the algorithm can self-correct if it realises that it made a mistake This subtle, yet fundamental difference highlights the very big gap between TBP and MTBP .

H.2. Supplementary details of the related works: TBP

Comparing TBP and MTBP thoroughly to related work is tricky since many related works are written in the fixed confidence setting. We extend the discussion here with respect to what is done in the paper.

In the problem independent regime of the TBP , current state of the art results can be deduced from the paper [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF]. A corollary to the lower bound in [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF] in the problem independent case is that for any algorithm, there exists a bandit problem where all arms have their distribution on [0, 1] and such that with probability larger than 1/2, at least one arm is missclassified and at more than a strictly positive constant times K/T from the threshold -this is also a corollary from the lower bound in [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF] for the different problem of best arm identification. Reciprocally, the state of the art upper bound in the problem independent case is a corollary to the upper bound in [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF]. In the problem independent setting, with probability larger than 1 -δ, all arms are within a strictly positive constant times K log(K log T /δ)/T from τ . As one can see, current state of the art upper and lower bounds are are far from matching in the problem independent case.

H.3. Supplementary details of the related works: MTBP

The papers [START_REF] Feige | Computing with noisy information[END_REF], [START_REF] Ben | The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)[END_REF] and [START_REF] Emamjomeh-Zadeh | Deterministic and probabilistic binary search in graphs[END_REF] introduce a noisy binary search with corrections. However in the above papers the probability of making an error during the binary search is treated as fixed. But this assumption does not hold in the setting of the MTBP . In [START_REF] Nowak | The geometry of generalized binary search[END_REF] a more generalised version of the binary search is considered with weaker assumptions on structure, however there is no contribution to classical binary search beyond that of [START_REF] Richard | Noisy binary search and its applications[END_REF]. [START_REF] Richard | Noisy binary search and its applications[END_REF] consider the special case where all arms k follows a Bernoulli distribution with parameter p k and p 1 < ... < p K , and the aim is to find a i such that p i is (1-K -1 -δ) log(K) ε 2 7 log(K) log(δ -1 ) ε 2

8

Table 3: Upper and lower bounds on the expected simple regret in the fixed budget (FB) setting and on the expected stopping time for (ε, δ)-PAC strategies in the fixed confidence (FC) setting. All results are given up to universal multiplicative constant -in the case where the sub-Gaussian parameter σ is set to 1. Left: previous state of the art bounds. Right: bounds from our paper.

Note however that it is a very mild assumption. Indeed σ comes from Definition 7.In many case, natural choices for σ are available -for instance if reward are bounded. Regarding UTB and CTB, simple extensions can be made so that they also consider the sub-Gaussian case.

I.2. Making the algorithms anytime

Although the Uniform algorithm, for simplicity, takes a known budget T it can trivially be extended to an anytime algorithm. With T unknown one can easily obtain a uniform distribution of pulls by repeatedly pulling all arms once in a batch until the "unknown" budget is expended.

In the case of the MTB Algorithm such a trivial extension is not possible. At each time step the number of times the arms in the current node are pulled is dependant upon budget T . Now note that it is possible to apply a doubling trick to our problem. I.e. first call the algorithm MTB with budget T = 6 log(K) + 1, and then until the algorithm is stopped, 4. See also [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF] for the LB. 5. Here c δ , cδ > 0 is a function of δ that is left unspecified in [START_REF] Richard | Noisy binary search and its applications[END_REF]. 6. See also [START_REF] Ben | The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)[END_REF] for the LB (1-δ) log(K) ε 2 up to terms that are negligible with respect to log(K)/ε 2 . 7. In [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF] The problem complexity H is upper bounded by K/ε 2 . Replacing H with such provides the given upper bound 8. The lower bound is well known, see [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF]. 9. And combining this with the lower bound in [START_REF] Chen | Combinatorial pure exploration of multi-armed bandits[END_REF], we get the problem independent lower bound of order K log(Kδ -1 ) ε 2 that matches our upper bound. 10. See also [START_REF] Ben | The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)[END_REF] for a LB that is essentially equivalent to this. 11. In the case where δ ≥ K -3/4 and is smaller than any universal constant strictly smaller than 1, our UB is more refined and of order log(K) ε 2 , which is order optimal.

always double the budget and call algorithm MTB from scratch. Then when the algorithm is stopped, recommend the arm recommended by the last full iteration. Note that this arm will have been selected with at least a fourth of the budget, and so Proposition 12 and Corollary 13 hold with the doubling trick and therefore without taking T as parameter, and replacing T by T /4 in the bound. Similar tricks hold also for UTB and CTB.

I.3. Computational complexity

The computational complexity of both our algorithms is very low. Algorithm Uniform is just uniform sampling, and then a computation of K empirical means and their comparison to the threshold. I.e. this is in total n operations (where by operations we mean addition or comparisons), and needs to store only K variables, i.e. the empirical means.

Algorithm MTB consists of • first running Algorithm Explore, which consists just in computing about log(K) empirical means, and taking decisions based on them. The algorithm just needs to perform n operations (where by operations we mean addition or comparisons), and needs to store only about log K variables, i.e. the empirical means and position of sampled arms. • then running Algorithm Choose which consists in scanning one time the list of sampled arms, i.e. doing about log(K) operations, and returning the median. The number of operations is therefore of order log(K) and the algorithm needs to store only about log(K) variables, i.e. the empirical means and position of relevant sampled arms. Similarly, the computational complexity of UTB and CTB is also low.

  Consider a set of bandit problems B -e.g. B u , B m , B c , B. The minimax optimal expected regret on B is then

  inclusion holds, see Corollary 34 and the definition of ξ I . Now assume {k : µ k = τ } = ∅. Let k * be as in the proof of Lemma 28. By definition of ξ I and since (µ k ) k is concave, it is clear that l I ≤ k * ≤ r I . The first inclusion then follows again by definition of ξ I . In the case where {k :µ k = τ } = ∅ the first inclusion is obvious. Proposition 36 Fix I ≤ M and assume that for all k, µ k ≤ τ -1 8 ε I . On ξ I ∩ (∩ i≤M η I i ), we have that Ŝ = ∅.Proof Under the conditions of the proposition we have that µ m i ≤ τ -1 8 ε I , for all i and this implies the result by definition of the η I i and I m .Proposition 37 Fix I ≤ M . On ξ I ∩ ∩ i≤M η I i , we have thatI m ⊂ {l I , . . . , r I },and also l I ∈ I l r I ∈ I r . Proof On ∩ i≤I η I i , we have that I m ⊂ {k : µ k ≥ τ } ∪ {l I , . . . , r I }, and so from Propositions and 35 and 36, we have on ∩ i≤I η I i ∩ ξ I , that I m ⊂ {l I , . . . , r I }. The proof that l I ∈ I l on ξ I ∩ η I I -as well as the fact that r I ∈ I r -follows immediately by combining the definition of I l -resp. I r -with Proposition 35 and 36, and the definition of η I I .

  Yichong Xu, Xi Chen, Aarti Singh, and Artur Dubrawski. Thresholding bandit problem with both duels and pulls. arXic preprint arXiv:1910.06368v1, 2019.Jia Yuan Yu and Shie Mannor. Unimodal bandits. 2011.Jie Zhong, Yijun Huang, and Ji Liu. Asynchronous parallel empirical variance guided algorithms for the thresholding bandit problem. arXic preprint arXiv:1704.04567, 2017.

		r}
	end
	end
	return Q :	Qk = 21 {k∈ Ŝ} -1

Proceedings of Machine Learning Research vol 125:1-48, 2020

In the TOP-M setting, the objective of the learner is to output the M arms with highest means. A popular version of it it is the TOP-1 problem where the aim is to find the arm that realises the maximum.

In particular, independent of T, K.

By simply discretising the space in K 1/β bins and applying the method on these bins.

Acknowledgements. The work of J. Cheshire is supported by the Deutsche Forschungsgemeinschaft (DFG) DFG -314838170, GRK 2297 MathCoRe. The work of P. Ménard is supported by the European CHISTERA project DELTA , partially supported by the SFI Sachsen-Anhalt for the project RE-BCI and by the UFA-DFH through the French-German Doktorandenkolleg CDFA 01-18. The work of A. Carpentier is partially supported by the Deutsche Forschungsgemeinschaft (DFG) Emmy Noether grant MuSyAD (CA 1488/1-1), by the DFG -314838170, GRK 2297 MathCoRe, by the DFG GRK 2433 DAEDALUS (384950143/GRK2433), by the DFG CRC 1294 'Data Assimilation', Project A03, and by the UFA-DFH through the French-German Doktorandenkolleg CDFA 01-18 and by the UFA-DFH through the French-German Doktorandenkolleg CDFA 01-18 and by the SFI Sachsen-Anhalt for the project RE-BCI.

Appendix D. Proof of Theorem 2

In the proofs of all results in this section, we assume that the more general sub-Gaussian assumption described in Section B is satisfied -and not necessarily that the distributions of all arms are bounded on the [0, 1] interval. In this case, we remind that we redefine ε 0 as in Section B. Also, we explain in the proof of the lower bound how it is possible to straightforwardly adapt the proof to the case where the distributions are supported in [0,1].

During this section we will prove Theorem 2 by first demonstrating a lower bound upon expected regret in the MTBP setting, Proposition 11. We will then go on to provide an upper bound on the regret of the MTB with high probability, Proposition 12 which will be used to finally prove Corollary 13 which provides a optimal bound for the MTB in expected regret. Setting σ = 1 Theorem 2 will then follow directly from Proposition 11 and Corollary 13.

Appendix E. Proof of Theorem 3

To prove Theorem 3 we first demonstrate, in Proposition 24, a lower bound on the expected regret of any strategy on the UTBP . We will then show, with Proposition 25, that the UTB achieves said lower bound. The proof of Theorem 3 will then follow directly. For all proofs during this section we make the assumption that arms are distributed as σ 2 -sub-Gaussian with σ = 1. Also, we explain in the proof of the lower bound how it is possible to straightforwardly adapt the proof to the case where the distributions are supported in [0, 1].

Proposition 24 For any T ≥ 1 and any strategy π, there exists an unimodal bandit problem ν ∈ B u , such that

Proof We will proceed as in the proof of Proposition 8. Fix some positive real number 0 < ε < 1. Without loss of generality we can assume that τ = ε/2. And consider the family of Gaussian bandit problems νk indexed by k ∈ {0, . . . , K}, such that for all k ∈ {0, . . . , K}, l ∈ [K],

Note that if we wish to consider distributions in [0, 1] we can consider instead τ = 1/2 + ε/2

up to minor alterations of the constants, and to considering τ = 1/2.

And so

combining this with the sub-Gaussian properties of the means which give that

where c > 0 is some absolute constant, and with the minimax optimality of SR which gives

this provides the result.

Appendix F. Proof of Theorem 4

For the proof of Proposition 27 we make the assumption that the distribution of all arms is bounded on the [0, 1] interval. In the case of the lower bound we consider σ 2 -sub-Gaussian distributions. Also, we explain in the proof of the lower bound how it is possible to straightforwardly adapt the proof to the case where the distributions are supported in [0, 1].

Proposition 26 For any T ≥ 1, K ≥ 3 and any strategy π, there exists a structured bandit problem ν ∈ B c , such that Rπ,

Proof We will proceed as in the previous proofs but with a different alternative set. Without loss of generality we can assume that τ = 0. Fix some positive real number 0 < ε < 1. And consider the family of Gaussian bandit problems νl indexed by l ∈ {0, . . . , L := log 2 (K) } defined by νl = N (µ l , 1) with

Note that if we want to consider distributions supported in [0, 1] we can consider νl = B(1/2 + µ l ) and τ = 1/2 instead of the Gaussian distributions, up to minor adaptations of the constants, and to considering τ = 1/2. Note that all these bandit problems belong to the set of convex bandit problems, νk ∈ B c . We will lower bound the maximum of the expected regrets over all the bandit problems introduced above, max

Proof

We assume ∃k ∈ {p, . . . , q} such that µ k > τ -1 8 ε and aim to prove by contradiction. Without loss of generality assume k < p+q 2 , in combination with the assumptions of Lemma 29 we have (µ k -µ p+q 2 ) > 1 2 ε. However, via the convex property (µ k -µ p+q 2 ) ≤ (µ p+q 2 -µ q ), a contradiction as it implies with the forelast equation that µ q < τ -1 8 ε.

We now define the event,

Consider the event

Proposition 30 Let i ≤ M and set

Let l i+1 be the largest arm smaller than l i+1 in S log l i ,r i . It holds that

Also for r i+1 be the smallest arm smaller than r i in -S log -r i ,l i .

Proof A straightforward corollary of Proposition 12 is as follows.

Corollary 31 Consider ε ≥ 2 log(48)6 log(K)

Then the MTB Algorithm will allow us to identify and arm k such that,

.

The result of the proposition follows by applying this corollary and noting that • in any case, |S log l i ,r i | ≤ log K so that we apply MTB on a problem that has less than log log K arms,

• that on E i , we have that (min

), the conditions of Corollary 31 are satisfied, for the set S log l i ,r i of arms. Therefore we can apply Corollary 31 to show that when running MTB (S log l i ,r i , τ i , T

2 ) we are able to identify an arm k such that setting l i+1 = k satisfies our result with probability greater than 1 -δ i .

Proposition 32 We have that for

Proof

We prove this proposition only for ξ

i+1 as the proof for ξ (R)

i+1 is similar. Consider the high probability event of Proposition 30, where we just have two possibilities for the mean of l i+1 which we summarize below.

Case 1 Consider the case where MTB outputs l i+1 such that,

where l i+1 is defined in Proposition 30. Since (µ k ) k<K is concave and since by definition of the concave grid S log l i ,r i we have that for l i+1 = l i ,

However this would imply

contradicting ξ i , hence l i = l i+1 and therefore via choice of l i+1 , l i + 1 = l i+1 . Therefore as

The property µ l i+1 ≥ τ -ε i+1 follows directly from (4), we have ξ

Appendix G. Extension of results to fixed confidence setting Fixed confidence setting. In this section we extend our results to the fixed confidence setting for the MTBP and TBP . In this case, we define δ, ε > 0, to be respectively the target confidence, and target precision of our algorithm. We say that a strategy π is (ε, δ)-PAC if it stops sampling at some stopping time T π ε,δ of its choice, and satisfies that with probability larger than 1 -δ, Rν ,π T ≤ ε. In this setting the aim is to find a (ε, δ)-PAC strategy that minimises the expected stopping time E ν [ T π ε,δ ]. The following Corollaries are an immediate consequence of our previous results, thus we omit proofs.

G.1. Lower Bounds

The following corollary is a direct extension to Proposition 8 which provides a lower bound in the unstructured case.

Corollary 40 Let ε, δ > 0. It holds that for any strategy π that stops at a stopping time T π ε,δ and that is (ε, δ)-PAC, there exists a unstructured bandit problem ν ∈ B, such that

Proof Consider the notations of the proof of Proposition 8. Assume that there exists an (ε, δ)-PAC strategy π such that for all Q ∈ {-1, 1} K , we have

From the proof of Proposition 8 it holds

And so there is a contradiction:

Combining this result with the lower bound from Theorem 2 of Chen et al. ( 2014), we obtain that for any (ε, δ)-PAC strategy, there exists a bandit problem where all arms are 1/4-sub-Gaussian and such that the expected stopping time is of higher order than

, since they prove that the expected stopping time for any (ε, δ)-PAC strategy is

, on some bandit problem.

The following corollary is a direct extension to Proposition 11 which provides a lower bound in the monotone case.

Corollary 41 Let ε, δ > 0 and K ≥ 2. It holds that for any strategy π that stops at a stopping time Tε,δ and that is (ε, δ)-PAC, there exists a unstructured bandit problem ν ∈ B m , such that

A very similar result was already obtained in Karp and Kleinberg ( 2007) , but for Bernoulli random variables in the lower bound, and without providing an explicit dependence on δ. In the paper [START_REF] Ben | The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)[END_REF], they refine this bound in the case of fixed probability of error which implies that for any strategy that (ε, δ)-PAC, there exists a structured bandit problem where all arms are 1/4-sub-Gaussian and such that the expected stopping time is of higher order than (1 -δ) log(K)/ε 2 up to terms that are negligible with respect to log(K)/ε 2 -which is essentially the same as what we have. We say that a strategy is optimal if its expected simple regret (or its expected stopping time for the fixed confidence setting) matches one of this lower bounds up to a universal constant.

G.2. Upper Bounds

The following Corollary is a direct extension to Proposition 10, which provides an upper bound on regret of the Uniform algorithm.

Corollary 42 Let ε, δ > 0. For any unstructured bandit problem ν ∈ B, Algorithm Uniform launched with parameter T := 2σ 2 K log(2K/δ)

Interestingly the stopping time can be taken here as deterministic, and this matches up to a multiplicative constant the lower bound in Corollary 40 combined with the one in [START_REF] Chen | Combinatorial pure exploration of multi-armed bandits[END_REF].

The following Corollary is a direct extension to Corollary13 which provides an upper bound on the regret of the MTB algorithm, Corollary 43 Let ε, δ > 0. For any problem ν ∈ B s , algorithm MTB launched with parameter T := 21σ 2 log(K)

Interestingly, the stopping time can be taken here as constant. For δ large enough i.e. δ ≥ K -3/4 , yet smaller than any universal constant strictly smaller than 1, this is order optimal up to a multiplicative constant -see Corollary 41. For δ smaller, this is order optimal up to a multiplicative constant that depends on δ -and it is an open question to obtain optimality in this case.

Similar results can be obtained in UTBP and CTBP .

Appendix H. Supplementary discussion concerning the TBP and MTBP H.1. Comparison of TBP and MTBP and focus on the main difference coming from the monotone structure

In the TBP , the proof of the bound of algorithm Uniform is very classical. It is, as usual in bandits, event based. We consider the event where all arms concentrate around their mean close to 1/2. In the fixed confidence setting, they prove that the naive binary search approach is not optimal and propose an involved exponential weight algorithm, as well as a random walk binary search, for solving the problem. They prove that for ε, δ > 0 fixed, then the algorithm returns all arms above threshold with probability larger than 1 -δ and tolerance ε in an expected number of pulls less than a multiplicative constant that depends on δ in a non-specified way times log 2 (K)/ε 2 . They prove that this is optimal up to a constant depending on δ. In the paper [START_REF] Ben | The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)[END_REF] they refine the dependence in δ in a slightly different setting -where one has a fixed error probability. They prove that up to terms that are negligible with respect to log(K)/ε 2 , a lower bound in the expected stopping time is of order (1 -δ) log(K)/ε 2 .

H.4. Contribution with respect to the literature

Our contributions can be summarised are as follows:

• Problem independent optimal rate for TBP We provide the first -to the best of our knowledge -upper and lower bounds in the problem independent regime for the TBPboth in the fixed confidence and fixed budget setting -as well as an associated parameter-free algorithm, Uniform. • Extension of MTBP to σ 2 -sub-Gaussian distribution The lower bound and optimal algorithm proposed in Karp and Kleinberg ( 2007) is specific to the assumption that all arms follow a Bernoulli distribution -and related literature makes even more constraining assumptions [START_REF] Feige | Computing with noisy information[END_REF]; [START_REF] Ben | The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)[END_REF]; [START_REF] Emamjomeh-Zadeh | Deterministic and probabilistic binary search in graphs[END_REF]. An extension of their algorithms-even in the fixed confidence setting -beyond this assumption is non-trivial. We propose an algorithm whose only assumption is that the arms follow a σ 2 -sub-Gaussian distribution. • MTBP in the fixed budget setting We treat in a problem independent optimal way the fixed budget setting. The algorithms proposed in Karp and Kleinberg (2007)as well as in [START_REF] Feige | Computing with noisy information[END_REF]; [START_REF] Ben | The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)[END_REF]; [START_REF] Emamjomeh-Zadeh | Deterministic and probabilistic binary search in graphs[END_REF] in a more restricted setting regarding the error distributions -operate in the fixed confidence setting. Adapting their results to a fixed budget setting is challenging, in particular since we consider the expected maximal gap as a measure of performance -see Section 2. • Simultaneous bound on all probability The MTB regret bound holds simultaneously across all probabilities. That is for all δ > 0 and after T rounds of our algorithm, we have a guarantee that with probability larger than 1 -δ, the simple regret will be bounded depending on δ. This 2014), where δ is given as a parameter to the algorithm, and where the behaviour of the algorithm is only studied on an event of probability 1 -δ, and a clear improvement with respect to [START_REF] Richard | Noisy binary search and its applications[END_REF] where the dependence in δ is not explicitly stated in the bound on regret. Our result is more general, as it allows us to get a bound on the expected simple regret for the fixed budget setting, but also to easily transform our algorithm to the fixed confidence setting.

We also refer to Table 3 for a comprehensive summary of state of the art rates, as well as of our rates.

H.5. Problem dependent regime

While not the focus of this paper we comment on the performance of our algorithms in the problem dependent regime for the TBP and MTBP . The problem dependent regime is defined as follows: for some sequence ∆ ∈ R K + we consider a sub class of problems B ∆ ⊂ B where

Similarly we can define

The mechanics of the game are then identical to those described in Section 2 with the exception that we consider a modified version the simple regret Rν ,π

that is, the probability the learner makes at least one miss classification -which is more relevant than the simple regret considered in this paper in the regime where the ∆ k are not very small, depending on T, K.

In the case of the TBP consider the class of problems B ∆ for some ∆ ∈ R K + . An upper bound on the simple regret of the order exp -c 1 K ∆ 2 i T K + c log(log(T )K) is provided from [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF], for the APT algorithm that does not take any parameterswhere c, c > 0 are universal constants. A matching lower bound is also provided in [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF], up to universal constants in the exponential. In the same setting we can upper bound the simple regret of the Uniform algorithm by k exp -c∆ 2 k T K , where c > 0 is a universal constant. Clearly the uniform algorithm under performs heavily in cases with high variance across the gaps, this should not come as a surprise.

In the case of the MTBP consider the class of problems B ∆ m for some ∆ ∈ R K + . We can construct and immediate lower bound on the simple regret of the order exp -cT min k∈[K] ∆ 2 k -where c > 0 is some universal constant -while the MTB algorithm achieves an upper bound of the order exp -c T log(K) min k∈[K] ∆ 2 k -where c > 0 is some (different) universal constant. Thus, while it is not optimal, the algorithm MTB is nevertheless quite efficient in the problem dependent setting.

Appendix I. Supplementary discussion

I.1. Parameters of the algorithms

The Uniform algorithm only takes T as a parameter, see Subsection I.2 for a discussion on how to make it anytime. The MTB algorithm takes only σ, K, T as parameters. Again, see Subsection I.2 for an anytime version. Getting rid of σ is however more tricky and is an open problem. We believe that in some pathological situations, the knowledge of σ is necessary.