Bandits with many optimal arms
Authors: Rianne de Heide
James Cheshire
Pierre MENARD
Alexandra Carpentier
Venue: NeurIPS 2021 Poster (2021)
Keywords: Infinitely-Armed Bandit Models
Cumulative Regret
Best-Arm Identification

Abstract: We consider a stochastic bandit problem with a possibly infinite number of arms. We write $p^*$ for the proportion of optimal arms and $\Delta$ for the minimal mean-gap between optimal and sub-optimal arms. We characterize the optimal learning rates both in the cumulative regret setting, and in the best-arm identification setting in terms of the problem parameters $T$ (the budget), $p^*$ and $\Delta$. For the objective of minimizing the cumulative regret, we provide a lower bound of order $\Omega(\log(T)/(p^*\Delta))$ and a UCB-style algorithm with matching upper bound up to a factor of $\log(1/\Delta)$. Our algorithm needs $p^*$ to calibrate its parameters, and we prove that this knowledge is necessary, since adapting to $p^*$ in this setting is impossible. For best-arm identification we also provide a lower bound of order $\Omega(\exp(-cT\Delta^2p^*))$ on the probability of outputting a sub-optimal arm where $c>0$ is an absolute constant. We also provide an elimination algorithm with an upper bound matching the lower bound up to a factor of order $\log(T)$ in the exponential, and that does not need $p^*$ or $\Delta$ as parameter. Our results apply directly to the three related problems of competing against the $j$-th best arm, identifying an $\epsilon$ good arm, and finding an arm with mean larger than a quantile of a known order.

Bandits with many optimal arms
Rianne de Heide
James Cheshire
INRIA Lille and CWI Amsterdam de hei reide@cwi.nd ml
Otto von Guericke University Magdeburg james cheshiresovgu.de
Pierre Ménard
Alexandra Carpentier
Otto von Guericke University Magdeburg eierre.menardooguu..e
University of Potsdam
carpentier@uni -ottrrduuu--ptttaamm.. de
Abstract
We consider stochastic bandit problem with possibly infinite number of arms. We write p" for the proportion of optimal arms and A for the minimal mean- -ap between optimal and sub-optimal arms. We characterize the optimal learning rates both in the cumulative regret setting, and in the best-arm identification setting in terms of the problem parameters I' (the budget), p and A. For the objective of min- imizing the cumulative regret, we provide lower bound of order ((log((') and UCB-style algorithm with matching upper bound up to a factor of log (1/A). Our algorithm needs p" to calibrate its parameters, and we prove that this knowl- edge is necessary, since adapting to p in this setting impossible. For best-arm identification we also provide lower bound of order ((xxp( cppppcTTppp" on the probability of outputting a sub-optimal arm where > is an absolute constant. We also provide an elimination algorithm with an upper bound matching the lower bound up to factor of order log(T) the exponential, and that does not need p' A parameter. Our results apply directly to the three related problems of competing against the j-th best arm, identifying an e good arm, and finding an arm with mean larger than quantile of known order.
A))
Introduction
In the classical stochastic multi-armed bandit model [37] for recent survey a learner interacts with an environment in several rounds. At each round, the learner chooses an arm to play, and receives random reward from the associated probability distribution. Popular settings are respectively the fixed budget cumulative regret setting [41]. and best-arm identification setting [18, 7, 1J. the first setting, the learner is interested in maximizing the sum of rewards gathered cumulative regret and the best-arm identification setting, the learner is asked at the end of the game output guess for the arm with the largest mean reward, and is interested in the quality of this guess typically measured by the probability error in the guess.
minimizing the
In most of the papers that concern this topic, it is assumed (i) that there is single optimal arm, i.e arm with highest mean, and (ii) that the number of arms is bounded and small when compared to the time horizon, i.e. the number of rounds where the player is allowed to choose arm. However in many realistic applications, is not the case, for example image classification, mining of resources, personalized medicine, hy perpparraeeeer tuning (see [5] for more examples). And while it is clear that all generality, the task of the learnr becomes unsolvable the number of arms too large, it intuitively makes sense that if the proportion of optimal arms is also large, this should help the learner.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this paper, we lift both assumptions summarised in (i) and (ii) and study both the cumulative regret and best-arm identification setting. See Section 1.3 for literature related this that we will discuss later. We will focus on the problem dependent setting and will aim at characterising optimal learning rates depending on the proportion of optimal arms, and on the minimal gap between the mean of an optimal arm and the mean of a sub-optimal arm.
1.1 Setting
We consider setting with (potentially infinite) set of arms A, which we call the reservoir. Each arm a E A is associated with a probability distribution Va. which we assume to be supported on [o, 1]. and we denote its mean by Pa- Write μ m Ha for the highest mean',, Maub Su /u- Pe for the second highest mean, and = AAsub for the associated minimal gap. We will focus throughout this paper the where A O.
We further assume that there exists a partition A = A" Agut such that each arm a E A" optimal, i.c. Ma = μ², and each arm E Asub is sub-optimal, i.e. Pa S Maub- We assume that the agent can pick arms uniformly at random from the reservoir AP, and this arm belongs either to the set A' with probability p², i.c. there is proportion p" of optimal arms in the reservoir; or it belongs to the set Asub with probability 1 - p", i.c. there a proportion 1 - p" of sub optimal arms the reservoir.
The learner interacts with the enviromment in several rounds t = ........ T, where we fix the time horizon T. At each round S T, the learner chooses an arm a, by either picking new arm from the reservoir A or playing past arm, and gets reward Y; Vu(t)- The arm choice depends only on the past observations, the past arm choices, and possibly some exogenous randomness. The rewards for each arm are i..d. random variables with mean Na unknown to the learner.
Cumulative regret setting. The first setting study is that of minimizing the cumulative regret. This setting enforces the actions get better estimate of the reward distributions, and exploitative actions to maximize the total return and minimise the associated cumulative regret. The cumulative regret is the difference between the sum of expected rewards the learner would have obtained by only choosing the arm with the highest mean reward, and the sum of expected rewards she actually collected:
trade-off:: the learner needs to balance exploratory
R(T)= Σ P (a(())
Best-arm identification setting arm with the highest mean reward. At the end of T rounds, the agents selects an arm âr and aims at minimising the probability of outputting an arm with sub-optimal mean:
the second setting we study, we are interested in identifying an
e(T) = P(âr & A*).
closely related popular measure of error is the simple regret, which not discussed in this paper.
Equivalent settings Firstly, our setting is directly applicable to the problem of competing against the j-th best arm, where we assume w.l.o.g. the arms to be ordered according to their means. Indeed our setting translates to this we replace p* by j/K and by the gap between the j/2-th and the j + 1-th best arm, i.c. A |,,/2 M.+1/. Secondly, our setting is directly applicable identifying an good arm, and thirdly, our setting is directly applicable to finding any arm in the reservoir with mean larger than the quantile of a known order see the discussion in Section 1.3.
that of
1.2 Contributions
We characterise the optimal learning rates both for the cumulative regret setting, and for best-arm identification, for our problem described above. We characterise the optimal learning rates in terms of the problem parameters 7,p", and A.
pr, In order to describe our results, let us write for A > 0² E 10; B A. for the set of bandit problems whose reservoir distribution is such that p* 2 p² and such that 1 -Mautl 2 A.
assume that is attained for some arm(s).
"nn case of infinite A, one can obviously not sample from a uniform distribution. Our analysis extends to general distributions on A.

---

Cumulative regret We provide an algorithm, that takes p" as a parameter, that is such that (see Theorem 1)
ER(T) O log T Lolloo((// (1/4)
p" A
Conversely, we prove in Theorem that for p* < 1/4 and Á S 1/4, and for any algorithm, there exists problem in B A.p7 such that
log T px
ER(T) 2
These two bounds match up to multiplicative factor of order log(1/A), They highlight the intuitive fact that should pay the number of arms in the rate only relative to the number of optimal arms i.. only through p*. Indeed, the probability picking an optimal arm in the reservoir when sampling uniformly at random being p", if we sample about 1/p" arms at random from the reservoir, will have sampled one optimal arm with constant probability - so that 1/p" plays the same role as the number of arms.
Having said that, there is main conceptual difficulty in order to get rate that tight in terms of its dependence in T. If we sample only 1/p" arms from the reservoir, the probability of having no optimal arms in the chosen set of arms also constant - so that the regret linear in T. is therefore essential to sample more arms. In order to have logarithmic regret in T, we need sample at least about log T/p² arms from the reservoir - which case at least one of them is optimal with (log r)² as
probability polynomially decaying with T. But if we do this, we get regret of order there are about log T/p" sub-optimal arms whenever p* is not too close to 1. This is much larger than the bound that we have, where the dependence on ' is only log 1', In order to achieve this bound, we need to take into account the fact that when sampling log T/pp arms from the reservoir, there is typically not just 1, but log T optimal arms with high probability and leverage this fact both in our algorithm and the associated proof. We describe this in more detail in Section 2.1.
y A
Best-arm identification
We provide algorithm that does not take p" as a parameter, such that,
(T) S o ( Log(TT) exp ( TA²P" Iog(T)
where e is some universal constant. Conversely, we prove that for pr 1/4 and A 1/4, and for where 0
any algorithm, there exists problem in B such that e(T) 2 (eexp(-cTA'pp 1icTTAppp is some universal constant. These two bounds match in order up to factor of order log(T) in the exponential, it is an open question here whether this term is necessary or not.
These bounds highlight the intuitive fact that we should pay the number of arms in the rate only relative to the number of optimal arms i.e. only through p" As in the cumulative regret setting, we sample about 1/p" arms at random from the reservoir, we will have sampled one optimal arm with constant probability so that 1/p" plays the same role as the number of arms.
As in the cumulative regret setting, there is again a main conceptual difficulty in order to get a rate that is tight in terms of its dependence in T. If we sample only 1/p" arms from the reservoir, the probability of having no optimal arms in the chosen arms is also a constant - which is way smaller than the targeted best-arm identification probability. In order have at least one optimal arm in the set of arms picked from the reservoir with probability that decays exponentially with A²? the number of arms that have to be sampled should be larger than T But if we do this, we get an upper bound on the probability of error that is of constant order which is much larger than the bound that we have, In order to obtain our upper bound, we need to take into account the fact that when sampling T arms from the reservoir, there is typically not just 1, but p T optimal arms with high probability and leverage this fact both in our algorithm and the associated proof. We describe this in more detail in Section 3.
Adaptation to n²: diverging pictures for cumulative regret and best-arm identification The algorithm for cumulative regret takes (a lower bound on) p* as parameter, but the algorithm for best-arm identification does not take anything related to p* or as a parameter. And so, while our algorithm for best-arm identification is adaptive to p* and A, our cumulative regret algorithm is
3

---

adaptive to A but not p". In Section 2.3 we prove that it is not just a weakness of our analysis. but that is impossible to adapt to p² when it comes to the cumulative regret. The phenomenon of adaptation to the problem hyper-parameters being possible for best-arm identification but not for cumulative regret, was observed earlier: In the X-rmmed bandit setting [40] show it is impossible to adapt to smoothness and [24] further classifies the cost of adaptation in this case. [44] explore the cost of adaptation to p" for the problem independent case where the number of arms is large.
1.3 Related work
Finite and small number of arms. The regret-minimization setting, introduced by [41], has been well-studied for finite-armed bandit models. Algorithmss for this problem fall into several categories: algorithms based on upper-confidence bounds (UCB) for the unknown arm means [30, 3, 2, 111, algorithms that exploit posterior distribution on the means, such as Thompson Sampling [42, 34], and many more such as explore-then-commii [20] and phased-elimination [19]. Logarithmic instance- cetance-dependen lower bounds have already been obtained in the seminal paper by [36], and were generalized later, e.g. by [10], see [21] for an overview and simple proofs. In the setting where the number of arms |A| is finite and not too large- much smaller than T a classical problem dependent upper bound on the expected cumulative regret is
8 AEAAIA |
Σ
8lgg
Ma + +22
S
log A
+ 2|/auul--
(1)
The bound in the RHS is tight if all sub-optimal arms have the same gap A. Moreover, this regret bound asymptotically matches the lower bound by [10] up to a multiplicative constant. In the case where there are infinitely many sub-optimal arms, the other hand, this upper bound is infinite, even when the proportion of optimal arms p" is large and where one would hope for better performances.
The fixed-budger best-arm identification setting was introduced by [7, 1] and has been widely studied. is well-known that algorithms that are optimal for cumulative-regret minimization cannot yield optimal performance for best-arm identification [8, 33]. Write H = Emedrs' (u--Ma)² S LAngal
A
The bound in the RHS is tight if all sub-optimal arms have gap A. It is proven by [1] that given H, there exists an algorithm such that the probability of misidentifying an optimal arm is of order exp(-cT H), where e > O is some universal constant. In the case where there is a single optimal amm this bound provably optimal [12] when H is known. However, in the case where there are infinitely many sub-optimal arms this upper bound is larger than 1 and thus vacuous, even when the proportion of optimal arms p" is large and where one would hope for better performances.
Importantly, our results in both settings extend to finite bandits. Furthermore we do not need infinite A for our results to be near optimal. In the finite setting with K arms and p* K optimal arms the problem is strictly harder than one with 1 arms and single optimal arm. Indeed, the latter problem p would correspond to one where the learner receives, as additional information, a partition of the set of K arms in p' groups, where one of the groups contains all optimal arms, and the others are only composed of sub-optimal arms. One can then see that we match the classical UB and LB for the finite bandit problem, up to ())( terms.
Large to infinite number of arms. The setting with an infinite number of arms and sometimes also many optimal arms has been studied in different settings.
A setting that is very related to ours is the infinitely arme- setting where distribution is assumed on the reservoir called the reservoir distribution. At each round, the learner can pull previously queried arm, new arm that is sampled according to the reservoir distribution. A classical assumption on the reservoir is that the proportion of Å-near optimal arms is of larger order than - for any A. This setting been studied for both cumulative regret minimization [5, 43, 6. 17] and for best-arm identification [13, 4, 15]. A classical strategy is to select a subset of arms from the reservoir, large enough so that it contains a near optimal arm with high probability, and to use classical bandit strategies on these arms. The minimax order of magnitude of the cumulative regret is then /T (a) and for the simple regret it is T 1/2 v 1/a
3 In the case where A is finite otherwise the quantity below is infinite.

---

Related results have also be obtained in the setting where the number of arms is finite, but large- i.e. K > 7 and under related assumptions on the frequency of near-optimal arms [44]. While our setting is extremely related to this setting, the assumption about the frequency of near-optimal arms differs in the above literature from the assumption we make in this paper: Their bounds are not dependent upon A they assume Vk E [K], juk E [0, 1J, and instead focus on achieving semi adaptivity in regards to an unknown a², where a* : inf : K/|S.| < T.). In the context of our setting 7 would act upper bound on 1/p". They propose an algorithm with user defined parameter 3 that has no guarantees on regret for 3 < a. And while our assumption is more restrictive, we also expect to obtain much smaller optimal rates. Our results differ from this stream of literature in the same way that, in the classical MAB, problem dependent results from problem independent results.
Another setting takes a regularity assumption on the reservoir distribution around μ² - that is, the proportion of arms in the reservoir whose gap is of order greater than Á is bounded above by a function of Å, typically Á", where a is the regularity coefficient. For best-arm identification adaptivity is possible without knowledge of a and [13] provide algorithms for the simple regret with LB matching up to (T) terms. In the case of cumulative regret [43] and [6] again provide near optimal results but in the case of known assumption on the reservoir distribution, their results are also considerably weaker than our own. For best-arm identification they identify sub optimal arm whose distance to the optimal arm is bounded polynomially with T. For cumulative regret the regret is bounded polynomially with T. These bounds are in both cases much larger than our bounds which essentially reflects that their assumption are weaker.
While the above literature considers weaker
Closer to our setting are the works [15] and [4], where they try to find any arm in the reservoir with a mean larger than the quantile of a known order (with respect to the reservoir distribution) with high probability. This can be seen as the fixed confidence version of our setting for best-arm identification where the order of the quantiles is our known proportion of optimal arms p* and the gap A is the difference between the first and the second quantile of order p". Preciscly, [4] provide an algorithm that can find an arm above the quantile of order p" with probability at least less than Ha.p log(1/5) samples average, where H HAp 11/pp A?) is the problem dependent constant. The fixed confidence result of [4] translates, in the fixed budget setting, into an upper bound on the probability of error e(T)) of order exp(-cv A2) where e > 0 is some universal constant which is much larger than our bound for large T. Similarly, [16] consider the regrel with respect to a fixed quantile of order pa of the distribution of the means in the reservoir which is again quite related to the regret in our setting. They obtain an algorithm with a bound on cumulative regret of order R(T) S (11/p" + (T/pp" TT)( for any A > in this sense, this analysis is problem independent.
8 in
Also closely related is the paper [32] which deals with identifying an good arm in the case where there are many such E good arms, with high probability. Again this can be seen as a fixed confidence version of our setting, with the proportion of good arms being equivalent to our p². However, the focus of their results differs considerably to our own. Specifically, in our setting, Theorem 2 of [32] provides an upper bound on the expectation of stopping time for epsilon good arm identification, of the order H log(H) where H. s 1/(p" A?) (1g) but this bound does not hold in high probability. which would be necessary if one wished to directly compare their results ours. Indeed for the stopping time of their algorithm to be bounded in high probability one would need to pay a log(1) (1/)22 term, corresponding to exp( (ep(-v/A2 A?p+tT) in our setting, see Remark 4 in [32] and page 15 in the appendix of the full version [31]. The focus of [32] is instead to get more complete gap dependent bounds, considering also the gaps within the epsilon good arms but as mentioned their results cannot be applied directly to our setting and, as they point out, extending their approach to include high probability guarantees would be strictly sub optimal compared to our results.
We can also view the most-biased coin problem studied by [14] and [27] as a particular instance of our setting where all optimal arms are distributed according to a Bernoulli distribution Ber(u²) ) and any sub-optimal arm is distributed according to the same Bernoulli distribution Ber ()r(w))). The goal is then to identify an optimal arm with high probability with as few samples as possible. Precisely, [27] prove that they can find an optimal arm with probability at least 5 with log (og(1/pp//) ) log(1/5) p'
samples in expectation when /²; p and p" are unknown to the agent and with log(1/8)
p A= samples
p² is known. It is also worth mentioning the problem of p² estimation for the biased coin problem.
5

---

For unknown p" and A, [39] describe, in the fixed confidence setting, the optimal learning rate for estimating p", up to additive error E, of the order 전'AT (16))
The translation of the result from [27] to the fixed budget setting is much closer to our result, as would provide a bound of order exp(-cTp' A² /lgg(1 log(1/(p" A²))) where > 0 is some universal constant. This is very similar to our bound, but there is a main difference: we do not assume that there are just two possible distribution for the arms as [27] the set Asub of sub-optimal arms might contain arms of diverse means, all being at a gap more than from Jr". This makes the problem significantly more difficult in particular regarding the adaptation to p* since in our setting, it is impossible to estimate the minimal gap A, see Section 5, In fact, extending to a more general reservoir is an open question of interest left at the end of the above paper.
Otherwise, there are some other formulations of the infinitely-mand armed bandit problem that are quite popular, but very different from our setting, and that we mention here for completeness. Many works are devoted to the setting where there is some topologiaal relation between the index of the arms, and the mean of the arms [35, 9, 23]. This setting is often referred to as the X' - -rmmed bandit setting, and not related to our work as we do not make such topological assumptions. Finally, a paper in which the setting is close to ours, but where the goal is very different, is the one by [28]. The authors consider a partition of the (infinite) space S2 of K-armed bandit models v = (V),-.., ,K)), and want to identify for given bandit model E Q the correct partition component it belongs to.
Fixed confidence to fixed budget setting In the fixed confidence setting for best-arm identification, given some 5 > O, one aims to bound the expected number of samples one needs to correctly identify an optimal arm with probability greater than
With our best-arm identification upper bound (Theorem 4) in mind, we can essentially translate our result to the fixed confidence setting by
considering exp
Tp' and solving for T. This leads to a upper bound on the number Tog(L/AA)
of samples Elimination needs to be d-approximately correct of: loe(3 () (og( (o(())))(())
The papers [27] and [4] both deal with seltings very related to our own but from the fixed confidence perspective. [4] deals with quantile estimation and as highlighted above their results can be applied to our setting but with significantly worse bound on probability of error of order exp(vTp²*A) In [27] the problem of best-arm identification is tackled directly but with strong restriction on the reservoir distribution, they consider the case were all sub optimal arms are identically distributed.
p=1a
Pair matching An additional setting that can be seen in the context of our problem is that of pair matching. Here the learner is presented with finite graph of nodes, N. The set of nodes N is partitioned into 2 or more communities. The general idea is that nodes in the same community are more likely to be connected by an edge than those in separate communities. A simple and well studied situation is where the graph is generated according to a stochastic block model (SBM), see [25]. In this setting the probability of an edge forming between two nodes of the same community is p and the probability of an edge forming between two nodes of differing communities is q. with p > g. Much of the literature then concerned with identifying communities given complete access the graph, see [38] and references therein. Of more relation to our specific setting is the paper [22]. Here the learner does not immediately observe the complete graph but instead able to sequentially query whether two nodes are connected up to a budget T. Their objective is then to minimise their sampling regret, the number of times they query and edge between 2 nodes of differing communities. The problem can be viewed as bandit problem where each pair of vertices represents an arm following a bernoulli distribution of mean p or q. In our setting the minimal proportion p" would then be the proportion of pairs which belong to the same community and the gap A p- q. The fundamental difference is that each arm can only be pulled once, making the problem significantly harder, however, the learner can exploit the SBM structure to their advantage. Assuming the case with exactly two equally sized communities with T < ? in [22] they show it is possible to attain a sub linear regret of the order T A A (p+g)T" The significant worsening of their rate, in comparison to our own, is due to the fact one cannot sample an arm more than once, which significantly changes the flavour of their algorithms.

---

2
Cumulative regret
first present an algorithm and prove an upper bound on its cumulative regret, and then we present lower bound that shows match the regret bound up poly-log terms in A. Lastly, we provide theorem to the effect that adaptation to the proportion of optimal arms pz is not possible in this setting.
2.1 Upper bound
We present Sampling-UCB UCB for cumulative regret minimization. This algorithm is an Upper Con- fidence Bound (UCB) type algorithm [37]. We first sample
L of arms large enough such that with high probability (of order - 1 1/T) there is a proportion of order p* optimal arms. Then we build upper confidence bound on the empirical mean of each sampled arm, see (2), where m is the empirical mean of arm a at time t and Ná the number of times arm a was pulled until time t. At time we pull the arm a C with the highest upper confidence bound U:. The complete procedure is detailed in Algorithm 1. Notably, we do not tune the upper confidence bounds such that they are exceeded with probability less than 1/T, as for finite-armed bandits. In that setting, a common choice to have bonuses the form T /2 (T)((T)) see [37]. Instead we use an exploration function that does not depend on T, such that the upper confidence bounds are exceeded with probability smaller than a fixed constant, see (2). Thus we only pay a constant regret of order log(1/A) on the set of sampled arms L. This is made possible by leveraging the fact that we know that there is proportion of order p" optimal arms.
Input: 7 E (0, L 1 Initialize: Pick L. with [&] L, arms from the reservoir A. Sample each once.
for t= +++1+11 to T do
Compute for each arm E C the quantity
22 7)- log( 2/) + 2 log(N
U
Ha +
(2)
2N
Play a4 arg MAX UT
end
Algorithm 1: Sampling UCB
We prove the following regret bound for Sampling-UGH UCB in Appendix A.
Theorem 1. For T 2 2, 7 C. (0, 1) and L = [1log(T)((>>>²)] the expected cumulative regret of
Sampling-UCB upper bounded as follows:
(og(() log log(1/A)
ER(T): S 50
see the end of the proof for precise bound, i.e. (3).
Note that this bound matches the lower bound of Theorem 2 of Section 2.2, for T large enough and up to a (1/(l multiplicative factor. Also, L can calibrated with a lower bound on p* instead of p". but this lower bound will appear in the rate instead of p².
samples L arms uniformly at random from the reservoir. What we mean by this is that each arm is pulled at random from A independently from the other pulled arms. In other words, by doing this, we potentially artificially create several independent copies of the same arm which might seem counter-intuitive, but formally not a problem. What this anyway implies is that the case |A| < L is not a problem with this idea of independent copics, we can pull more arms from the reservoir than the number [AA] of arms.
Remark 1. Algorithm Sampling-Bn
Remark Our algorithm reminiscent of that [26], which, as our own, uses a UCB which does not depend on the time horizon, but only the number of times an arm has been pulled. However, they do so for different reasons, namely to adapt to the infinite time horizon of the fixed confidence setting.

---

2.2 Lower bound
We can prove an equivalent of the [36] lower bound for finite armed bandits for our setting. The following theorem is proved in Appendix A.
Theorem 2. Consider A E (0, 1/4) and p" E (0, 1/4/. For any bandit algorithm, there exists bandit problem in B p.p" such that
1 max (log (A2T/66))) VT)
ER(T) 2 min
60
D²A
Note that we consider the gap A and the proportion of optimal arms p= as fixed and large in comparison, ie. A > VI/T, then our lower bound is order log (og(T)) (TT)(G /p" A). This the problem- dependent regime that we consider in this paper. On the contrary. if A ~ VI/T then our lower bound is of order VT. This is rather the problem independent regime studied by [16]. We make a parallel between the lower bound in our setting and the one for finite-armed bandits. Indeed, if we consider that the proxy for the number of arms |A| ~ 1/p" which implies that there |A] ~ 1 optimal arm, then we recover the problem-dependent lower bound of order [A] log())/ |A| sub-optimal arms with gap A.
(T)/ A, if there
2.3 Impossibility of adapting to
The following theorem shows that in the setting of minimizing the cumulative regret, it is impossible to adapt to the proportion of optimal arms p². The theorem is proved in Appendix A.
Theorem 3. Let p" S 2/2 and such that T A that for all bandit problems in B D we have,
clog(T)) 1²
For any bandit algorithm such
cTog(T)
ER(T) S
D²A
one has that Vg" S 4p" there exists a problem in Ba.q" such that
ER(T) > VTA
Remark 3. The Sampling-Ut algorithm takes defined parameter (which can be taken as a universal constant) and L, which should be calibrated depending on (a lower bound on) p². While this is necessary, it important to not that none of the parameters requires knowledge of A.
3 Best-arm identification
We present our Elimination algorithm for best-arm identification, together with an upper bound on the probability of outputting sub nub-optimal arm; next we prove lower bound, which matched by our upper bound up to a 1/ log(T) factor in the exponential.
3.1 Upper bound
As its name suggests, the Elimination algorithm (summarized in Algorithm 2) works by successive elimination of arms - through the update at round of set A, although with twist. We begin by sampling approximately T arms at the first round, Namely, we first select a set A₁ of [A1 = / log T' arms taken at random from the reservoir, for some constant c O. Then each round we use a T/ log T fraction of our budget to sample the arms in our set. And so round i we sample each arm in the set A, a number of 4, = |aT/([A) T. We then eliminate half of the arms based on the arms' empirical means namely, we just keep the ||A://2] V arms A; that have highest empirical means and introduce an additional number of arms sampled from the reservoir distribution - namely ||A.//4| - such that the final size of our arm set reduced by 3. At the end of the budget, we have one arm remaining due the choices of ē which is the arm that we return. Note that Remark applies here too so that it is not problem [A] smaller than the number of arms required by the algorithm. Theorem is proved in Appendix B.

---

Input: 8
while < log T/ē do
Sample each arm A, a number 1, [T/[|A log log of times and compute their empirical means (fi(()))aEA)
Put in A 1 1 [|Ai]/2] arms that have highest empirical means (f4(()) and add top of that [|A:1/4] new arms taken at random from the reservoir i i
end
Return any år in A,
Algorithm 2: Elimination
Theorem 4. Set c = log(4/3). Elimination satisfies
P(ār E A 2 1- log exp -6 A2p"T log T
where c 0/ 19900
Remark 4. Elimination works by discarding many sub-optimal arms and few optimal in each round, so that at the end, when just one arm remains, it is optimal with high probability. A key clement is that Elimination on adds fresh arms from the reservoir cach round. This our algorithm is adaptive to p", A, as ensured by Theorem 4. Whenever the arms in A, are pulled less than about A times, there is no guarantee on what happens when half of the arms are eliminated. Therefore, we have to make sure that when the algorithm arrives at round i such that t, 2 A 2, the proportion of optimal arms of larger order than p" with high enough probability. This is ensured by adding the fresh arms added from the reservoir. Note that for some arm distributions, we do not need to add fresh arms and the algorithm would function also by just halving at each step the number of arms. Indeed, in the case where all arms follow Bernoulli distribution, in terms of preserving the proportion of optimal arms, one can prove that halving the set arms according to the empirical means is no worse than random halving of the set. Thus, in this case, with high probability we increase the proportion of optimal arms at each step, without diminishing it. This is however specific to the case of Bernoulli distributions and some other parametric families, and it is an open question whether this would be true in general.
ensure that
Remark The successive halving strategy our algorithm for best-arm identification is based on was first introduced by [29], however, without the trick of adding fresh arms, as they didn't 't need to be adaptive to p".
3.2 Lower bound
The following Theorem provides a lower bound on the probability of error for best arm identification in our setting. The proof of Theorem
be found in Appendix B.
Theorem S. Consider A E 1/4) and p* E [0, 1/4). For any bandit algorithm, there exists bandit problem in B spp such that
2
e ( 2 exp -Tp"
32
In proving the above theorem we essentially show that agent cannot accurately distinguish between two cases: 1 = and μ = A. That is, we consider two reservoirs Ro and R, where μĄ = and أi + A. Using coupling argument we bound the KL divergence between the distribution of samples collected on Rg and R,. The results then follows by application of Bretagnolle- Huber's inequality.
4 Experiments
conduct a preliminary set of experiments to test the performance of our algorithms. Specifically, for cumulative regret compare our Sampling-UCa to the QRMI algorithm by [16] and the

---

SR algorithm by Zhu and Nowak [44]. For simple regret we compare our Elimination to the BUCB algorithm by [32]. In both cases our performance appears comparable to the literature. See Appendix D for details.
5 Conclusion and open questions
Classifying optimal learning rates on the continuous armed bandit problems with proportion of optimal arms and general reservoir distribution has been a question of interest in the literature for some time, see [27]. Recent papers - [4] and [44], while focused on slightly different setting, have considerably weaker results when applied to our setting. Therefore, we believe our results mark significant improvement in the state of the art. An extension of our results would be to remove the log(1/A) discrepancy between UB and LB for cumulative regret. However, this appears non-trio con-trivial and in particular struggle to see how UCB based strategy would achieve this tighter bound in the case of the cumulative regret. Another possibility for further work is an expansion of our setting. Consider the arm reservoir A partitioned into K possible distributions, each with associated probability Pk- Let = arg [ Pe and take gaps (Ax) = (H4 [ One could then consider more detailed bounds, dependent on the sequence ((Px, Ax) as opposed to just p* and
the smallest gap. The main difficulty here would be to deal with the case where some P& are much smaller than the proportion p" corresponding to the optimal arm.
Acknowledgements The work of J. Cheshire is supported by the Deutsche Forschungsgemeinn schaft (DFG) GRK 2297 MathCoRe. The work P. Ménard is supported by the SFI Sachsen-Anhalt for the project RE-BCI. The work of A. Carpentier is partially supported by the Deutsche Forschungs- gemeinschaft (DFG) Emmy Noether grant MuSyAD (CA 1488/1-1), by the DFG 3148381 70, GRK 2297 MathCoRe, by the FG DFG. by the DFG CRC 1294 'Data Assimilation' Project A03, by the Forschungsgruppe FOR 5381 ..Mathematische Statistik im Informationszeiiaater SSatissis- che Effizienz und rechentechnische Durchführbarkeit" Project 02, by the Agence Nationale de la Recherche (ANR) and the DFG on the French-Germas PRCI ANR ASCAI CA 1488/4-1 " "Aktive und Batch Segmenticrung, Clustering und Scriation: Grundlagen der KI" and by the UFA DFH through the Trench-German Doktorandenkolleg CDFA 01-18 and by the SFI Sachsen Annalt for the project RE-BCI.
References
[1] Jean- Yves Audibert and Sébastien Bubeck. Best arm identification in aumti-armed bandits. In COLT-23th Conference on Learning Theory-2010, pages 13-p, 2010.
[2] Peter Auer and Ronald Ortner. Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, 61(1-2):55-65, 2010.
[3] Peter Auer, Nicolo Cesa- -Baanch,,, and Paul Fischer. Finite- analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235 256, 2002.
[4] Maryam Aziz, Jesse Anderton, Emilie Kaufmann, and Javed Aslam. Pure exploration in infinitely-amme armed bandit models with fixed-confidence. In Algorithmic Learning Theory, pages 3-24, 2018
[5] Donald A Berry, Robert W Chen, Alan Zame, David C Heath, and Larry A Shepp. Bandit problems with infinitely many arms. The Annals of Statistics, pages 2103-2116, 1997.
[6] Thomas Bonald and Alexandre Proutiere. Two-target algorithms for infinite-armed bandits with bernoulli rewards. Advances in Neural Information Processing Systems, 26:2184-2192, 2013.
[7] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In International conference on Algorithmic learning theory, pages 23-37. Springer, 2009.
[8] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in iireel and continuous-armed bandits. Theoretical Computer Science, 1832--9183221888 201
10

---

[9] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5), 2011.
[10] Apostolos N Burnetas and Michael N Katchakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122-142, 1996.
[11] Olivier Cappé, Aurélien Garivier, Odalrie-Ambrym Maillard, Rémi Munos, Gilles Stoltz, et al. Kullback Icibler upper confidence bounds for optimal scquential allocation. The Anmals of Statistics, 41(3):1516 1541, 2013.
[12] Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference on Learning Theory, pages 590-604, 2016.
[13] Alexandra Carpentier and Michal Valko. Simple regret for infinitely many armed bandits. In International Conference on Machine Learning, pages 1133-1141, 2015.
[14] Karthekeyan Chandrasekaran and Richard Karp. Finding a most biased coin with fewest flips. In Conference on Learning Theory, pages 394 407, 2014.
[15] Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan. Pac identification of a bandit arm relative to reward quantile. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31, 2017.
[16] Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan. Quantile-regrel minimisation in in- finitely many-armed bandits. In UAI, 2018
[17] Yahel David and Nahum Shimkin. Infinitely many-armed bandits with unknown value dis- tribution. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pages 307-322. Springer, 2014.
[18) Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. In International Conference on Computational Learning Theory, pages 255-270. Springer, 2002.
[19] Eyal Even Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(Jun):009--111 2006.
[20] Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-commil strategies. Advances in Neural Information Processing Systems, 29:784 792, 2016.
[21] Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The truc shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-399, 2019.
[22] Christophe Giraud, Yann Issartel, Luc Lehéricy, and Matthieu Lerasle, Pair matching: When bandits meet stochastic block model. stat, 1050: 17, 2019.
[23] Jean-Bastien Grill, Michal Valko, and Rémi Munos. Black-box optimization of noisy functions with unknown smoothness. Advances in Neural Information Processing Systems, 28:667-675, 2015.
[24] Hédi Hadiji. Polynomial cost of adaptation for x-armed bandits. In Advances in Neural Information Processing Systems, pages 1029-1038, 2019.
[25] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 109) 137, 1983.
[26] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil' ucb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439. PMLR, 2014.
[27] Kevin G Jamieson, Daniel Haas, and Benjamin Recht. The power of adaptivity in identifying statistical alternatives. In Advances Neural Information Processing Systems, pages 775-783, 2016.
11

---

[28] Sandeep Juneja and Subhashini Krishnasamy. Sample complexity of partition identification using multi armed bandits. In Conference on Learning Theory, pages 1824-1852. PMLR, 2019.
[29] Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-1246, 1246. PMLR, 2013.
[30] Michael N Katehakis and Herbert Robbins. Sequential choice from several populations. Pro- ceedings of the National Academy of Sciences of the United States of America, 92(19)88584, 1995.
[31] Julian Katz-Samuels and Kevin Jamieson. The true sample complexity of identifying good arms, arXiv preprint arXiv: 190.069906. 2019.
[32] Julian Katz-Samuels and Kevin Jamieson. The true sample complexity identifying good arms. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1781-1791. PMLR, 26-28 Aug 2020.
[33] Emilie Kaufmann and Aurélien Garivier. Learning the distribution with largest mean: two bandit frameworks. ESAIM: Proceedings and surveys, 60: 60:114-131, 2017.
[34] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory, pages 199-213. Springer, 2012.
[35] Robert Kleinberg, Aleksandıs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces, In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 681 181-690, 2008.
[36] Tze Leung Lai and Herbert Robbins. Asymplotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4-22, 1985
[37] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[38] Can M Le, Elizaveta Levina, and Roman Vershynin. Concentration random graphs and appli- cation to community delection. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 2925-29442 World Scientific, 2018.
[39] Jasper C.H. Lee and Paul Valiant. Uncertainty about uncertainty: Optimal adaptive algorithms for estimating mixtures of unknown coins ACM-SIAM, 2021.
[40] Andrea Locatelli and Alexandra Carpentier. Adaptivity to smoothness in x-armed bandits. 31st Annual Conference Learning Theory, 75:1-30, 2018.
[41] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):227-535 1952.
[42] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933.
[43] Yizao Wang, Jean-Y Audibert, and Rémi Munos. Algorithms for infinitely many-armed bandits. Advances in Neural Information Processing Systems, 21:1729-1736 2008
[44] Yinglun Zhu and Robert Nowak. On regret with multiple best arms. In Advances in Neural Information Processing Systems, 2020.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes]. [No] or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
12

---

Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Ys]]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes] In the theorem statements.
(b) Did you include complete proofs of all theoretical results? [Yes] In the appendices.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you's 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvais, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "gKVTk1ud3O2", "reviewer": "Reviewer_C1hU", "summary": "Authors consider the stochastic bandit setting considering a possibly infinite number of arms. They call p* the fraction of optimal arms and investigate both the cumulative regret minimization and the best-arm identification problems. For both problems they provide a lower bound and a solution matching the upper bound (up to log factors).", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Authors consider the stochastic bandit setting considering a possibly infinite number of arms. They call p* the fraction of optimal arms and investigate both the cumulative regret minimization and the best-arm identification problems.\n\nIf compared to existing works, they consider a more general setting and the obtained results are stronger than the ones obtained in the existing simpler frameworks.\n\nFor the first problem they provide a lower bound argument and an algorithm matching the bound up to multiplicative log factor of order 1/\\Delta. The algorithm requires the knowledge of p* as input parameter, this seems to be a limitation, however authors shown that knowing such a parameter is strongly necessary.\n\nSimilarly, for the best-arm identification setting they provide a lower bound and an upper bound to the probability of choosing a suboptimal arm. The upper-bound matches the lower one up to a log factor in the exponential. The proposed algorithm does not require the knowedge of p* as it was for the regret-minimization solution.\n\nI would like to know which challenges/technical difficulties have been solved in the proofs if compared to existing works.\nSecondly, I wonder if there are connections with the combinatorial bandit problem.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "fjcRB1ey2qo", "reviewer": "Reviewer_wUpn", "summary": "This paper considers infinitely many armed bandit problems where the significant portion is optimal. In particular, p* fraction of the arms are optimal. \nThis paper considered two objectives (total reward optimization and best arm identification). For the first objective, the paper proposes a version of UCB algorithm with a slightly smaller confidence bound (sampling UCB, alg 1) that matches lower bound up to O(log(1/Delta)), whereas for the second objective the paper proposes a version of elimination (Elimination, alg 2) that matches lower bound up to O(log Delta^{-2}).\n\nThis paper is mainly theoretical and the assumption of many optimal arms is more restrictive than the existing literature of many-armed bandit problem (without empirical justification). I think the algorithms proposed in this paper is novel and the paper is marginally above the acceptance threshold as it is of theoretical interest of the readers. Having derived corresponding lower bounds based on change-of-measure discussion is also nice.\nThere can be some space for improvement on the structure of the paper. It spends 5+2/3 pages before the main results. As a result, results of the simulation are not presented during the main paper.\n\nAfter the discussion period:\nI would not change my rating strongly (will keep WA). I think the paper is above the threshold.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "* Major comments:\n\n** Total reward maximization\n\nSampling UCB (Algorithm 1) first draws C log T/p* arms and apply a version of UCB algorithm with slightly smaller confidence bound (sqrt(log Ni/Ni)). Such a confidence bound sometimes yields UCB value of U_i(t) < \\mu_i. However, given there are p* fraction of arms, there is at least one optimal arm with U_i(t) >= \\mu_i. This trick reduces an O(log T) factor compared with standard UCB.\n- Can you briefly discuss where the log(1/Delta) gap between upper and lower bounds? The lower bound looks reasonable given it took log T/Delta**2 to identify the optimality of arm and 1/p rate of finding the optimal arm.\n\n** Best-arm identification\nElimination (Algorithm 2) first draws T/2 arms and then at each epoch it discards the lower half of them and adds some new arms of the same order. The algorithm is aimed to draw some optimal arm tilde(O)(pDelta^2T) times and adopts a polynomially decreasing size of epochs. The algorithm is different from successive rejection and is interesting.\n\n** Comparison with other algorithms \nCan you compare the results here with similar work? For example, what kind of bounds can we obtain when we apply [39]?\n\n** Simulation results:\nIt would be great if you briefly discuss the other algorithms in simulations. \n\n* Minor comments:\n\n- The paper may rename algorithm 2 as it not only eliminates some of the arms but also adds new ones at each epoch.\n- Can you motivate the problem setting (a many-armed bandit with p* fraction of optimal arms)? \n- Some of the equations referred in the main papers only appear in the supplemenatry materials. For example, Eq. (3).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "EQ_tsvKtDC8", "reviewer": "Reviewer_Y2aD", "summary": "The paper studies multi-armed bandits when there are a large number of arms, but when a constant\nfraction of the arms are optimal. The paper studies methods for cumulative regret in the fixed\nhorizon setting and best arm identfication (BAI) in the fixed budget setting. In the former, they\ndescribe an UCB-style algorithm which knows this constant fraction (p*) and bound its regret; they\ncomplement this with a lower bound and an impossibility result which states that p* is necessary. In\nthe latter, the describe a successsive halving style algorithm and show that it nearly matches a\nlower bound.\n\nWhile I do have some reservations about the set up and the motivation, my overall perspective is\nquite positive. The main results (theorems 1, 2, 4, 5) build on known techniques, but there is\nalso a reasonable amount of new ideas. While I did not have time to check the proofs, the proof\nintuitions make sense and the results are believable. The paper is also well-written.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- In my opinion, the main shortcoming of the paper is that the setting lacks practical motivation.\n  This, in and of itself is not a problem (e.g. K-armed bandits are rarely used in their simplest\n  form in practice, but the intuitions and proof ideas have been used to study richer feedback\n  models, such as linear, X-armed, and GP bandits which are used in practice). Unfortunately, I\n  don't see a natural extension of this setting to richer feedback models. It would be helpful, if\n  the authors can discuss how their setting and ideas can be enhanced in future work which might\n  consider more practical settings, either using such richer feedback models or otherwise. \n    - The motivating example the authors use in lines 30-33 is that there might be many arms in\n      image classification, personalized medicine, or hyperparameter tuning. But the arms in these\n      applications can be featurized, and the usual approach for tackling such a large number of\n      arms is to use a richer feedback model so that the regret bounds scale with the complexity\n      of the model and not the number of arms. It is also unreasonable to assume that a constant\n      fraction of arms in these applications will be exactly optimal (usually there will be several\n      good arms, but their means may not be the same), let alone that p* will be known ahead\n      of time.\n\n- Please comment on extending Algorithm 1 to the any-time setting? It appears that sampling of the\n  initial pool can be handled by slowly admitting more arms after several rounds, but I am not sure\n  if the confidence intervals would still work. \n\n- The UCB used by the authors in (2) is reminiscent of the UCB used in the following paper and is\n  probably worth citing.\n    Jamieson et al, \"lil’ UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits\"\n\n- Can you explain the proof intuition in Theorem 3?\n\n- Have you explored other conditions, besides the constant p* fraction, under which Algorithm 2 (or\n  any other sensible algorithm) will return a ``good'' arm?\n    - For instance, there are several arms, but you only need to find an \\epsilon optimal arm or\n      an arm whose mean is in some top percentile. \n\n- The successive halving strategy that the authors have used for the BAI setting was first\n  introduced by Karnin et al, \"Almost Optimal Exploration in Multi-Armed Bandits\" and should be\n  cited.\n\n\n-------------------------------\n\nPost-rebuttal: Based on the authors' reply, I have increased my score to 8. While I am less convinced about the practical motivation given by the authors and the results for the cumulative regret problem, I think the results for BAI are potentially interesting and the abstraction could be useful for some follow up work. While the proofs fundamentally build on well-known techniques, they also use some new ideas.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers are positive about this paper. The reviewers agree that the paper shows interesting new ideas in the results (especially ones for best arm identification). The reviewers also raise concerns about practical motivations and the presentation structure of the paper. I think the paper can benefit from improving in these directions.
Decision: Accept (Poster)