Asymptotically Optimal Quantile Pure Exploration for Infinite-Armed Bandits
Authors: Xiao-Yue Gong
Mark Sellke
Venue: NeurIPS 2023 poster (2023)
Keywords: pure exploration
multi-armed bandits
Fisher information
TL;DR: We obtain sharp bounds for the sample complexity of pure exploration bandits with infinitely many arms.

Abstract: We study pure exploration with infinitely many bandit arms generated \iid from an unknown distribution. Our goal is to efficiently select a single high quality arm whose average reward is, with probability $1-\delta$, within $\varepsilon$ of being with the top $\eta$-fraction of arms; this is a natural adaptation of the classical PAC guarantee for infinite action sets. We consider both the fixed confidence and fixed budget settings, aiming respectively for optimal \emph{expected} and \emph{fixed} sample complexity.


For fixed confidence, we give an algorithm with expected sample complexity $O\left(\frac{\log (1/\eta)\log (1/\delta)}{\eta\varepsilon^2}\right)$. This is optimal except for the $\log (1/\eta)$ factor, and the $\delta$-dependence closes a quadratic gap in the literature. For fixed budget, we show the asymptotically optimal sample complexity as $\delta\to 0$ is $c^{-1}\log(1/\delta)\big(\log\log(1/\delta)\big)^2$ to leading order; equivalently, the optimal failure probability with exactly $N$ samples decays as 
$\exp\big(-(1\pm o(1))\frac{cN}{\log^2 N}\big)$.
The value of $c$ depends explicitly on the problem parameters (including the unknown arm distribution) through a certain Fisher information distance. Even the strictly super-linear dependence on $\log(1/\delta)$ was not known and resolves a question of Grossman-Moshkovitz (FOCS 2015).

Asymptotically Optimal Quantile Pure Exploration for Infinite-Armed Bandits
Xiao- Gong Carnegie Mellon University exiaoyue@andrer, cmu. cmu. edu
Mark Sellke Harvard University msellke0fas wharvard edu
Abstract
We study pure exploration with infinitely many bandit arms generated i.i.d. from an unknown distribution. Our goal is to efficiently select a single high quality 6, within of being with the top v7-fraction of arms. For fixed confidence, we give an algorithm with expected
whose average reward is, with probability
sample complexity (1ug(1/)) (1)) log(2/v) which matches known lower bound up qe²
(1
the log(1/1) factor. In particular the 5-dependence is optimal and closes a quadratic gap. For fixed budget, we show the asymptotically optimal sample com- plexity as 5 -> is (og(1/5)) log log(1/5)) //c The value of e depends explicitly on the problem parameters (including the unknown arm distribution) through a certain Fisher information distance. Even the strictly super-linear dependence log(1/8) was not known and resolves a question of [GM20].
Introduction
In many learning problems, one faces the classical exploration versus exploitation tradeoff. A central example is the (stochastic) multi-armed bandit [LR85, BF85], where an agent presented with set of arms each of which when played gives stochastic reward from an unknown and urm-dependent distribution. The performance of a bandit algorithm most commonly determined by its regret, i.e. the difference between its average reward and the expected reward from the best arm. Multi- armed bandits and extensions have been applied many settings including medical trials [BE95], online advertising [L.CLS10] cognitive radio [AMTS1 I], and information retrieval [LPB17] Opti- mal algorithms for the multi-armed bandit, including UCB, Thompson sampling, EXP3, and various forms of mirror descent, all make a principled tradcoff between exploration and exploitation.
In this work we focus on pure exploration bandit problems, setting motivated by situations where the learning procedure consists of an initial exploration phase followed by choice of policy to deploy. This is the case in hyperparameter optimization [GM20, LJD+17 17] as well as reinforcement learning from simulated environments. As there is no longer a competing need to exploit, optimal algorithms for pure exploration differ from the more common regret setting.
Pure exploration problems were introduced in [EDMM02, MT04, EDMM06] in the probably- approximately-corees (PAC) model. Here given arms, one adaptively obtains samples until choosing one of the arms to output the goal is to ensure that with probability 1 - 8, this arm has average reward within E of the best arm, with minimum possible sample complexity depending on and 8. The early works above focused on the fixed confidence setting in which one aims to minimize the expected sample complexity. Many subsequent works have also considered the fixed budget problem where the sample complexity is uniformly bounded.
While sharp results are known for pure exploration and other bandit problems with K arms, for many applications such as advertising there are far too many arms to explore. This motivated the study of infinite-armed bandit problems in e.g. [BCZ 97, WAM08]; the pure exploration version
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

was first studied in [AAKA18]. The main contribution of our work is to obtain near- cetrmoptimal sample complexity for pure exploration problems with infinitely many arms in both the fixed confidence and fixed budget settings.
1.1 Problem Formulation
We now precisely formulate the infinite-armed pure exploration setting. Let S = {a1, 02....) be countably infinite set of stochastic handit arms indexed by i 1,2..... When an arm is sampled, it returns a {0, ]-valuedd reward with mean p.. The values p: are drawn i.i.d. from an arbitrary reservoir distribution j supported in [0. (which is unknown to the player). We define the cumulative distribution function
GT(()) PP Ip S r]
of μ4, and its (left-continuous) inverse
(p) (r: G(r) 2 p).
Finally let μ² = Gr denote the essential supremum of ja, i.e. the maximum of its support.
An algorithm A interacts with S in the following way. At each time step algorithm samples an arm is E S. and observes corresponding Bernoulli reward rg ~ Ber( )- The reward rz is independent of previous actions and feedback. Eventually at some time T. A chooses an arm a:- to output. If the time-horizon T = N is fixed, we say A has a fixed budget constraint. If E[T] < N is bounded only in expectation, we say A has a fixed confidence constraint. For n, 5 > O, we say is (n, (,, Pf if
1,2..... T the
Plp-- 2 G G (1-1)
-1) - -e] 2 -
(1.1)
and set
a G= -
to be the target quantile value. We emphasize that while is known, a may not be as it depends on the unknown μ. The definition (1.1) stems from [AAKAI8]] As brief justification for the parameter 7. note that in an infinite-armed setting the reservoir could give E-optimal arms with arbitrarily small probability. Thus it is impossible to give non-asymptotic classical (c, 5)-AAC in our setting without assumptions on μ. Taking 7) > as above ensures that a positive fraction of arms are "good enough" and will enable such guarantees. One also cannot set zero: for example if μ is supported in [0.5 e-N 0.5), the quantile value of the output arm will be essentially uniform for any N --sample algorithm.
The purpose of this paper is to give (,, PPC algorithms whose sample complexity N is mini- mal. We can now state our main results. Let us emphasize that unless explicitly stated, no assump- tions on the reservoir distribution j are made, nor does the algorithm have any prior knowledge about μs. Our main result in the fixed confidence case as follows.
Theorem 1.1. For any (n, e, 8), there exists (1) 8)-PAC algorithm with expected sample com- plexity O [log(1/8) log(1/1)
n)²
In the fixed budget setting, interest is especially in the high cegehhennfeeecee regime 5 O, where obtain the following. The following statement is a slightly informal combination of Theorems 3.1 and 3.2. We note that while the main statement requires to be given, this is not essential in several cases as discussed extensively in the Appendix. For example if a 2 Ltz then a does not need to be given.
2
Theorem 1.2 (Informal). For any fixed (n, let a = GG 77) be given and set 3 = a Then as 8 0, the optimal (n, e. 6AC algorithm under fixed budget has sample complexity
N = (co,1 + 06-) (gg(())) log log( l
Ca (arccos(1 2a) arccos(1 -1)))))
(1.2)
2
Sa
di
11(1
(1.3)
2

---

An equivalent statement is that given exactly N samples, the optimal failure probability å to have Ps 2 G1 - 17) - E decays as exp ()) Indeed once 1j and & are fixed, the question of minimizing the sample complexity N (6) (given target confidence 8) is equivalent to minimizing the failure probability 6 = 8(N) (given sample complexity N). These viewpoints are equivalent in both settings we study, and we switch between them at times.
(N)
Interestingly the value 1j makes no appearance in Theorem 1.2, so is asymptotically irrelevant for the 5 + 0 regime of fixed budget pure exploration. In fact the value arccos(1 - 2a) arccos(1 2.3) appearing in the definition of Ca.8 is the Fisher-infore inhormaifooot distance between a and / in the exponential family of Bernoulli random variables via the formula (1.3). See just below Theorem 3.1 for a brief explanation of why y does not enter the asymptotic sample complexity.
Remark 1.1. In our problemformmlation formulation above we assumed rewards are Bernoulli, i.e. lie in {0, 1}. In fact long the quality of arm is measured by its mean reward, this assumption loses no generality and is just a technical convenience: our results extend verbatim to [0, 1]-valued rewards.
Indeed any arm with [0, 1] 1--valued rewards can be transformed into a Bernoulli arm with {0, 1}- valued rewards and the same mean: simply turn reward r E [0, 1] into reward 1 with probability T, and O with probability 1 1 r. Note that this reduction (used also in Section 1.2 of [AG12]) might increase the desenncedeeendeet sample complexity of some reservoir distributions, but our results only refer to the distribution of arm means under the reservoir which is unchanged by the reduction.
1.2 Further Notation
We use the convention that algorithms collect sample per unit time until terminating, so the time t equivalently denotes the number of total samples collected so far. Denote by nie the number of samples of arm o, collected by time t. The n-th time a; is sampled, its reward is Ti, E [0, 1]. The total reward of arm up to time t is
VILL
Ri.
Σ Tin-
The corresponding average reward is Pr,e = (r(,))) Res We use C to indicate a universal Re.t" constant independent of all parameters in this paper, and (1) and (1 denote quantities tending to 0 as + оo or N + Do, with other parameters implicitly held constant. However in Section C we use e.g. Sa.e indicate an asymptotic lower bound with implicit constant factor depending on the values of a, g. which are treated as fixed. In all our uses of these notations it is n or N which is tending to infinity while other parameters are always treated as fixed.
1.3 Related Work
As discussed above, this work belongs to the area of pure exploration for multi nulti-armed bandit prob- lems. Unlike ordinary bandit problems where one aims minimize the regret compared the best arm [BCB12, Sli19], in pure exploration all that matters is the final arm selected by the algorithm. We survey several existing results below, with emphasis on the high-probability regime of small 5. See e.g. Chapter 33 of [LS20] for more detailed survey.
Pure exploration was first studied in [EDMM02, MT04, EDMM06] in the aaaaabbyaapprxiimately correct model. Here given K arms, one adaptively obtains samples until choosing one of the arms to output - the goal is to ensure that with probability 1 1-& 8, this arm has average reward within of the best arm. These works showed that the optimal fixed confidence sample complexity is θ ( log })-
Later, [BMS09] considered the simple regret of pure exploration problems, namely the regret in- curred at the final timestep. [ABM10] studied the closely related problem of identifying the best arm, obtaining nearly tight sample complexity bounds in terms of the the sum of the squared in- verse suboptimality-gapu gapss H Ener- A-2 Further upper and lower sample complexity bounds have been obtained in several works. For example [CL15, KCG16] show that for fixed confidence, the sample complexity scales as θ (H (1g(1 as + 0. The fixed budget setting, in which the number of adaptive samples is upper-bounded almost surely rather than in expectation, turns out to be more difficult. [CL16] proved that the optimal fixed budget sample complexity can be O (H (og 1o)( as 8 + 0, i.c. the fixed budget constraint may lead to additional log( (K)
3

---

factor. However it reverts to θ (H (00())))))))) when the value of H is known beforehand. Many re- cent works have studied other aspects of pure exploration, for example by incorporating structured feedback; see [JMNB 14, CGL++1,, KSJ20, KG21, TRMD21, ACD21, ZKSN22, 22J+
anfinit--armed bandits have also much received previous study, e.g. [BCZ 97. WAM08J. Since near-optimal arms may be arbitrarily rare, it is natural to instead compare with a quantile of the arm distribution. For example [CK18) aims to minimize regret relative to such a quantile.
guarantees we address in this paper were first studied in [AAKA18], for infinitely many arms in the fixed confidence setting. Their approach was to sample K x log(2/8) arms and then apply PAC algorithm for K-armed pure exploration. As discussed the beginning of Section 2, the resulting algorithm "pays twice" for the high confidence level 1 - 8 which leads to a suboptimal Ollog" (1/6)) sample complexity upper bound. Top-k extensions were also studied in [RLS19, CK CK19]; the (1/6) scaling is still present in their results.
The
Of particular note is the work [dHCMC21] which considers also both fixed budget and confidence settings and obtains somewhat similar looking results. However they restrict attention to special class of reservoir distributions with supremum achieved by an atom, which must be A-larger than the rest of the support. This structural assumption of A Aggap intrinsically reduces fixed budget sample complexity: their result (see Theorem therein) is actually better than the lower bound we show in Theorem 3.2 as there is no appearance of log (og(l/)) (i.e. log(T") in their notation).
From their fixed budget estimate, [dHCMC21] deduce (at the end of Section 1 therein) the same bound as Theorem 1.1 in their setting for the special case & = A. Our Theorem 3.2 shows that for the general reservoirs we consider, passing from fixed budget to fixed confidence is inherently suboptimal: the factors of log log(1/0) would remain, but are extraneous for fixed confidence. This underscores that Theorem 1.1 is genuinely new despite the superficial similarity with [dHCMC21], since their proof cannot work in our setting.
Finally [GM20] studied the infinite-arm pure exploration problem where a is given, also focus- ing on the - 0 asymptotics. They proposed an algorithm with fixed budget sample complexity O( log(1 (1/5) [log log(1/))) and asked whether the log log(1/6) factors are necessary. Theo- rem 3.2 shows their bound is optimal up to constant factors in terms of 5 and in fact obtains the tight constant. Interestingly [GM20] were motivated by complexity theoretic applications to amplification and derandomization, where bandit arms correspond to random seeds.
We remark that the analysis in [GM20] seems to be technically incomplete. In particular in Lemma 4.5 of (the cited, journal version of) the paper. they neglect to take a union bound over sequences (Ti,..., Tk) summing to T but only estimate the probability of each fixed sequence (Ti...., T&)) This is a serious gap since the number of such sequences is exponentially large in T. However their idea to use moving sequence of rejection thresholds
fundamentally correct. It is similar the main phase of our Algorithm 3, for which we give a fully rigorous, supermartingale-ban based analysis.
2 The Fixed Confidence Setting
Our fixed confidence algorithms proceeds in two phases. The first phase aims to estimate the target quantile value, which we recall depends on the unknown a. The second phase then aims to find a single arm which is almost as good as this estimate with high probability.
Focusing the d-dependence, a challenge with infinitely many arms is that to succeed with proba- bility 1 5, it is necessary both to sample log(1/ /5) arms to ensure a good arm is ever observed, and to sample arm ( times before outputting it as it. This is why the approach of [AAKA18] requires (log" 2 (1/8)) samples: they obtain (log(1/8)) samples each of (log(1//)) arms. How- ever in our algorithm, the first phase samples O(log(1 (1))) arms O(1) times each, while the second phase samples 0(1) arms O(log(1/ (1/)) ()) times each. This allows us to satisfy both necessary condi- tions above without paying twice for the confidence level.
2.1
The Algorithm for Fixed Confidence
We first give in Alg. I simple procedure to estimate the top quantile, allowing an e/3 error as well as an 1 error the quantile itself. Alg. obtains O [Ior([/)) samples from each of the
4

---

Algorithm 1: Output & E (G 7) G. G 3)
3.
with probability
input: arm set S (a), (2,...) and parameters 7), 7,,,, (0, (),1).
initialize: K- Clog(1/6)
79
3 for i 1. do
Collect v = Clon(1/m) samples of arm Set f: = fn: to be the average observed reward.
5 end
Let á be the k-th largest value in {pI, .......11 Px) for k 3K4 Return &
Algorithm 2: Ouiput a;- such that p:+ 2 á with probability 1 8.
input: arm set S (#1, .2,...) and parameters (1), e, 6x
for i K 1, K 2,... ..... K Clog(1/6) do
Collect C Clo((1/n0) samples of arm Set P to be the average reward.
if p; 2 à //r then
Return d₁
end
end
first K O log(1/6) arms 01...., OK. The resulting estimator à is the empirical average rewards .i,.... Pu. Its main guarantee is below.
3n quantile of the
Proposition 2.1. Fix 0 < n, E, 5 < 1. With probability at least 1 z the output à of Alg. I satisfies
à E ( -n)
3 -
G- (1 g
"
8
3
Moreover, Alg. 1 has sample complexity
log [og((1/)) (Ln)) (1/())))))))))
me²
Next Alg. 2 repeatedly chooses new arm and obtains O (10) samples. It accepts if the sample mean was at least 5. and otherwise moves on to the next arm. If Cloo(1/88) arms have been tried without success, then Alg. 2 outputs no arm, thus declaring failure. This termination condition is necessary avoid incurring huge sample complexity when Alg. I's estimate á of is inaccurate. Since typically 2(1) of arms will be good enough to usually succeed, this also preserves the 1 confidence level. We give the following more detailed restatement of Theorem 1.1.
Theorem 2.1. Apply Algorithm I followed by Algorithm 2 using the resulting value & This com- [log [log[1/)) 1/)) log(1/5)
bined algorithm has expected sample complexity O satisfies
Moreover its oulput a;-
P[pr- G - 7) -
Proposition 2.1 and Theorem 2.1 are proved in Appendix A. We note that analyzing Algorithm 2, typically the returned arm has < K + O(1nn) This is because each arm in the top 1/2 quan- has a good chance to pass the test of Algorithm 2. particular, the expected sample complexity calculation never multiplies two log(1/8) terms together. However, continuing for K + Clog(1/á) steps is important to ensure 1 5 success probability. Algorithm 2 stops after O 1/0)/n) arms instead of continuing forever in order to guard against erroncous estimates from Algorithm
Remark 2.1. Our fixed confulence algorithm, given by combining Alg. with Alg, as above, re- quires only O(1) batches in expectation. Here batched algorithm operates in small number of batched phases. the start of each phase, such an algorithm chooses b arms to sample ex- actly times each, where b, s can both depend adaptively on the previous feedback, but cannot be
5

---

changed during the current phase. Minimizing the number of required batches is often desirable, see e.g. [PRCSI6, GHRZI9]. In particular Alg. I uses single batch with 81 C'logl/nn) samples of by = (1og(1/6) arms. Then Alg. 2 can be implemented in a batched way with $2 = C Cog(l//g and a sequence of batch sizes b2 = 2 for 1 S i S log2 (Cloog( /8]). (In the latter phase, one steps after finding an arm accept.) While this construction uses O(1) batches in expectation, could be interesting to explore pure exploration with an exactly fixed number of batches, which is more analogous to the fixed budget setting.
8²
2.2 Near-Optimality in the Fixed Confidence Regime
Here we explain why the guarantee of Theorem 2.1 is nearly optimal. For comparison, recall from the important work [MT04] that @ K llgg(1/)) samples are necessary and sufficient for (c, 6-PPA
pure exploration in the K -arme bandit problem with fixed confidence. Intuitively, one expects this problem be related ours via 17 1/K. In fact the following infinite-arm analog was later shown.' It follows that the guarantee of Theorem 1.1 is optimal up to the log(1/n) factor.
Proposition 2.2 (Theorem I and Remark 2 of [AAKA18]. There exists an absolute constant e > O such that the following holds. For any 1/4 S S 3/4 and 1), 5 S 1/10 and for any pure exploration algorithm A with expected sample complexity N < clog(1/6), such that fails to be (1),,,)-PAA.
there exists a reservoir distribution ne²
Letting L log(1/0) ge"
1/n be the lower bound from Proposition 2.2, the expected sample com- plexity of our algorithm is at most (LL S OLL log L). Hence Theorem 1.1 is always nearly optimal compared to the lower bound. Prior to our work there was quadratic gap as the best upper bound for general reservoirs (Theorem 6 in [AAKA 18)) was proportional to We note also that Theorem of [dHCMC21] showed similar result to Proposition 2.2.
Fixed Budget
Our algorithm and lower bounds for the fixed budget setting are much more technical, with full details given in the Appendix. Here we carefully state the results and give outlines of the proofs.
3.1 Precise Results for Fixed Budget
We first state the results in the easier case that a is given. Theorems 3.1 and 3.2 below give rigorous statements of Theorem 1.2. As there, will write 3 for the target value when is given, since then the value plays no role.
Theorem 3.1. For any fixed 0 < 3 < a < 1, there is a sequence (An) of N N-sample algo- rithms given explicitly by Algorithm 3 such that for any T (0,1) and any sequence of reservoir distributions JaN with G-1 (1 1)) 2 a, with Ca as in (1.2):
(- log P ux [pt < 3) log" N
lim sup
2 Co.B.
(3.1)
-000
N
Conversely, the following lower bound applies for any quantile v) E (0, 1), and holds even when a known (which only makes pure exploration easier). implies that 17 is asymptotically irrelevant for fixed budget sample complexity, i.c. the sample complexity of approximating the 1) = 0.01- quantile and 77 = 0.99 quantile in fixed budget pure exploration depends only on the quantile values themselves as 5 + 0. Some intuition for this is as follows. To succeed in pure exploration, one should have sampled the eventually outputted arm at least 22 1/8) times. The main obstacle to success in the fixed budget case is that any arm we obtain many samples of might gradually degrade over time. The probability of this degradation is essentially given by small probabilities coming from Chernoff-bound type events, which dominate the prior probability that the arm is in top quantile.
[AAKKI8]] states the result more generally. Specializing to P(p: = ai and Plp = - e] 11-7 for any 1/4 & a & 3/4 recovers the statement of Proposition 2.2.

---

< 1 there exists a sequence of reservoir distributions Ju with a GpN 7) such that for any sequence of N N-sample algorithms AN,
Theorem 3.2. For any 0 <7 < 1 and 0 < B <
log(Tp px (p-- < x))) log" S Ca.B.
lim inf
(3.2)
No+00
N
Remark 3.1. As discussed the Appendix, the requirement that a be known in Theorem 3.1 is technically necessary to deal with potential discontinuity of a varies, but can be removed under mild conditions. Theorems B.I, B.2, and B.3 below we give three concrete formulations under which the guarantee (3.1) can be achieved without knowledge of a. Informal descriptions (any 1 of which suffices on its own) are:
1. pNn obeys G 1) 4
2. or is redefined as the average of G (1) for yi ranging over an interval.
3. JN ya is independent of N, and the target value
3 = 1r" for fixed & > &. (Recall p² the maximum value the support of p.)
Remark 3.2. In fact (see Theorem C.9 in the Appendix), Theorem 3.1 holds even if the algorithms
AN must outpur log N distinct arms 87, ......,, "oo N= all of which must satisfy Peş 2 8. Le. for suitable (An)Nz1
(- log Pl min
Piş < <B] -log*
jEllog N]
lim sup N-+00
Co.
N
3.2 Algorithm for Fixed Budget
Here we present Algorithm 3 for the fixed budget problem. We note that this algorithm is given as input the value of a. See Appendix C.I for first-stage algorithms which estimate a with sufficiently high accuracy and low sample complexity in the three scenarios of Remark 3.1. We use an spploreannddiscare approach: at each time, it is currently exploring some arm i, having permanently discarded arms 1,2,..., i and not yet interacted with arms i 1, + 2..... It natch-compressed" way for an increasing integer
turns out to be very convenient to operate in a bb..b..... This means that at all times, the current arm has been sampled by times for some k, and the samples between by and b are compressed into a single decision. The sequence by increases geometrically mildly large. This batch-compression turns out to be without loss of generality up to a factor 1 + in the sample complexity, and helps the analysis operate on the proper geometric time-scales.
sequence B
small rate, i.e. //b R @ for small @ once k: is
We now give precise description well pseudo-code. Let 0 Q < Φ < 02 << be suitably small constants (i.e. choose @2 sufficiently small, then @1, then g). We define by and other parameters follows:
0(a) arccos(1 - 2a) V [0,
bo Tei log (NV],
kg = flogi+e (1og') (N)/bo)]
by = [bo (1 + #1,
k ko
b bko+j [(1 + 0)
j j21
(3.3)
k
Tk a
Vog N'
k < ku
Tko+j 0(a 2g) (0(a) - ((3) e(1 02)
j2
log
The outer loop dictates the arm under consideration. While exploring arm the main phase (shown in the last for loop) consists of collecting new batch of buotij - bbg big RJ obno+j-1 samples, and rejecting the new empirical mean reward pi. 15 drops below
--1 A(a 20) - -j. (0(a) 0(3)) e(1 02)
log N
7

---

Algorithm 3: Output arm with 2 3 using N samples with high probability
input: parameters N,a, a. (3, and an infinite sequence of arms i 1, 1,..... initialize: parameters from (3.3) and 0
3 while fewer than samples have been collected do
f i ++1
Get by samples of arm i.
if Pi,bo a P then Reject arm end for
== 1,2, . Ko do Get by bk-1 samples of arm (total by).
11
if Pr.be S a o Vlg N then Reject arm i; end end
12
15
for j= 1,,.... do
Get bko+s bko+j-1 samples of arm (total bko+s). 16
if ((p,bbot )) S 0(a 20) j. (o(a) 0(8)) e(1 then log
17
end 18
Reject arm
19
20
end
21
end
Return arm i.
Let explain the point of this formula. First ignoring the function 0 for now, we see that the rejection threshold for pi. steadily decreases with k. This threshold is tuned so that when arm has been sampled say (2(N/ log N) times, we have & x log(NN)/ which results in threshold slightly larger than B. Thus an arm which survives for such a long time will be prepared for acceptance as new-optimal arm.
This strategy can be motivated as follows. The chief worry in fixed budget exploration is that arms might slowly degrade after many samples have been invested into them, which suggests a gradually decreasing rejection threshold. We designed this threshold to drop by constant divided by log(N) each time the number bą of samples doubles. This ensures that for arm to be rejected at time bg+1, the last bk+1 -b, samples must have behaved atypically (compared to their past behavior) by roughly Vbe+1 log(N) standard deviations. The probability of this rare event is roughly exp(-Cbb+41 hoo//loog"""" (N)) for some constant C' by a Chernoff bound. Therefore if all N samples are used on eventually rejected arms, the product of these rare event probabilities will be roughly exp(- log (NV) since each bk-1 counts the number of samples used on individual arm.
The of the non- non-linear function A above essential to achieve the optimal constant Ca.9 in The- orem 3.1. At a high-level, f balances the p(1 p) -)ddeeendence of optimal Chernoff bounds on the underlying probability of the Binomial random variable. If the optimal constant is not desired, then Theorem 3.1 can be simplified somewhat; the nonlinear is not needed and one can double the number of samples each step rather than multiplying by + @ for small o. The earlier for loops in Algorithm are technically important to handle small sample sizes for each given arm, before the required Chernoff bounds have kicked in asymptotically.
3.3 Analysis Algorithm
The analysis of Algorithm goes by controlling the tail distribution for the rejection time of a given arm (this time is taken to be zero if rejection ever happens). Intuitively, most worried about arms which slowly degrade, thus wasting many samples. The following lemma, proved in the Appendix by supermartingale argument, key to rigorize this idea.

---

Lemma 3. Suppose (Yd)21 are i.i.d. random variables with non-negative integer values, and B|y] S holds for some constant 2 0. Then with
M = sup II Y,
120 18151
we have P[M 2 A] A
We apply Lemma 3 in the following way. Let X, be the number of samples used by arm a, before rejection, and 1, E {0. 1 be the indicator of the event that a, is ever rejected (even if Algorithm were to continue past time N and sample arm infinite number of times). We set Y; ex 44- The bulk of the analysis thus reduces to proving that E[ < 1 for a suitable exponent c. Once this shown, Lemma 3 ensures that M is small with high probability. Since log(M) is exactly the total number of samples used on eventually-rejecte arms, if say log M S N log then the last arm 1" to be selected must have passed enough rejection thresholds to have p.+ 2 3 with sufficiently high probability.
The early behavior of Algorithm 3 and by are specifically designed so that small values of Y, con- tribute little in expectation. The tail behavior of Y, (corresponding to rejecting arm after a long time) is controlled by technical analysis involving many adjacent time-scales in Subsection C.4 of the Appendix. Interestingly this tail analysis of Y; never explicitly models the reward probability pi- This is because are able to argue that rejection requires the early and late time behaviors of arm i to differ from each other, which is unlikely since the rewards form an i.i.d. sequence.
3.4 On the Lower Bound Proof
We consider the lower bound Theorem 3.2 to be the technical highlight of this paper. In it we face the challenge of proving a very small lower bound on the failure probability of any fixed budget algo- rithm. To do rewards. The setup follows; recall B--batch-compressed algorithms as defined in Subsection 3.2.
construct online adversary with bounded probabilistic strength to distort
Definition 3.1. An adaptive randomness distorting adversary & interacts with a B-batch- compressed algorithm A in the following way. Suppose A chooses to increase the number of samples arm a, from by to b8+1- Then may restrict the set of possible outcomes of these by++1 by sam- ples. Additionally, when A oulputs an arm ar, the adversary can restrict the possible values of P:-.
We will refer to adversarial actions as declarations. Thus when A chooses batch of samples, A may declare that some property holds for the observed rewards.
As defined above, an adversary A can do anything. We will limit the power of A to make low- probability declarations. To formalize this, we charge per "bit" of probabilistic distortion, and give A deterministic "budget" for doing so. We measure this budget according to the algorithm's filtration which we refer to the "jointly Bayesian" viewpoint. One should think that the reservoir distribution μN is known to both A and A, but neither has any information probabilities p; beyond the observed rewards. Thus A and share at any time f the posterior distribution μt. In particular recalling (B.9), μ³ determines the distribution for the outcome of the next batch of bx+1 - by samples.
the true reward
Definition 3.2. Suppose that at time t, the declaration of A has probability Pt hold according to μ². Let the sum
Cost, Log(1/PP.) *St.
(3.4)
be the total cost of up to time t, and Cost the total cost of A. We say strength((A) S Cost holds for some Cost E R. if the bound Costn & Cost almost surely.
The next key lemma shows that to obtain lower bound for the failure probability of an algorithm, suffices to prevent success using a low strength A.
Lemma 4. Suppose there is randomness distorting adversary A of strength Cost whose declara- tions ensure that any algorithm A outputs i satisfying p S 3 almost surely. Then the true failure probability of A is
PHN S 3 2 Cost

---

Proof. At each step t. let the random variable E, denote the minimum possible conditional probabil-
ity of the event p.- < 3 for any algorithm (in the algorithm's 's jointly Bayesian filtration). We claim that conditioned on A's declarations holding, for any A the quantity M, = E2 II.se P. evolves as
a supermartingale in this filtration. This suffices because it implies Eu = Mo 2 [[Mr] 2 e Cost (Here T is the random number of total batches used.)
Indeed suppose we are at time / and the next batch has been declared but not sampled. (Identical arguments apply when the adversary restricts p;+ the last stage.) Let the or F, denote all information up to this point including the declaration of the next batch. Let E denote an expectation where the samples from the next batch is distributed according to ua' Let I' denote an expectation where A's 's declaration is conditioned to hold on the next batch. The dynamic programming principle implies that
E|E Fil S Ec
for any A (with equality for the optimal A). Moreover since A's declaration has μ²' p'-probabilitty P..
E|E++1
Fi]
< E [[B4+ Fil/P S PpPP.
We prove Theorem 3.2 by constructing a Bayesian adversary who slowly degrades the empirical performance of each arm ag This adversary declares for each batch of samples that the empirical Pt is Ft measurable, so E[ Fi] S Eg. This establishes the claim and ends the proof.
average reward P; (mi,e) of arm i will drop by Z (og(NT) at least once the sample size n4, 2 Ne is large. This degradation schedule ensures that the average reward of any arm is smaller than / once it has been sampled ((NN1=) times. Moreover it follows from reverse Chernoff estimates that this adversary pays O
[og cost per sample, leading to failure probability lower bound of exp(-O(N/ log" N)) from Lemma 4. As with the upper bound, sharp constants can be tracked with more work and indeed our optimal adversary uses the same function 0 as in Algorithm 3.
Conclusion Our aim in this paper was to understand the sample complexity of pure exploration with infinitely many arms. We showed that, surprisingly, the behavior of fixed confidence and fixed budget problems is provably very different. In the former setting, there is a nearly optimal algorithm which precisely balances between sampling enough distinct arms (to estimate the quantile) and obtaining enough samples of a single arm (to be output). In the latter, the optimal algorithm must repeatedly decide whether to continue with the current arm or switch to a fresh one, via a gradually decreasing sequence of rejection thresholds.
Several interesting questions remain. One is that our fixed budget analysis is tailored to the d + 0 setting, and does not apply if E, 11, 5 all tend zero comparable rates. Hence other behaviors could be present in such parameter regimes. Additionally, a key conceptual feature of infinite- armed bandits is the possibility that no "good" arms are among those sampled by the algorithm. By definition, this simply cannot happen in K-armed bandits. It would be interesting to identify a natural problem setting that interpolates between them. Finally high probability bounds on the fixed confidence sample complexity would interpolate between the two settings we studied.
References
[2] Maryam Aziz, Jesse Anderton, Kevin Jamieson, Alice Wang, Hugues Bouchard, and Javed Aslam. Identifying new podcasts with high general appeal using a pure explo- ration infinitely-armed bandit strategy. In Proceedings of the 16th ACM Conference on Recommender Systems, pages 134-144, 2022.
[AAKA18]
Maryam Aziz, Jesse Anderton, Emilie Kaufmann, and Javed Aslam. Pure exploration in infinitely- armed bandit models with fixed-confidence. In Algorithmic Learning Theory, pages 3-24. PMLR, 2018.
[ABM10] Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pages 41-53. Citeseer, 2010.
[ACD21]
Ayya Alieva, Ashok Cutkosky, and Abhimanyu Das. Robust pure exploration in linear bandits with limited budget. International Conference on Machine Learning, pages 187-195. PMLR, 2021.
10

---

[AG12]
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[AMTS1]]
Animashree Anandkumar, Nithin Michael, Ao Kevin Tang, and Ananthram Swami. Distributed algorithms for learning and cognitive medium access with logarithmic regret. IEEE Journal on Selected Areas in Communications, 29(4):731-745, 2011.
B2 Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and non- stochastic multi-armes bandit problems. Foundations and Trends@ in Machine Learn- ing, 5(1):1-12, 2012.
[BCZ+97] Donald Berry, Robert Chen, Alan Zame, David Heath, and Larry Shepp. Bandit prob- lems with infinitely many arms. Annals of Statistics, 255))2103-2116, 1997.
[BE95]
Donald A Berry and Stephen G Eick. Adaptive assignment versus balanced random- ization in clinical trials: a decision analysis. Statistics in medicine, 14(3):231-246, 1995.
[BF85]
Donald Berry and Bert Fristedt. Bandit problems: sequential allocation of experi- ments. London: Chapman and Hall, 5(71-87)7-77 1985.
[BMS09]
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In International conference Algorithmic learning theory, pages 23-37. Springer, 2009.
[CGL+17] Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, and Ruosong Wang. Nearly opti- mal sampling algorithms for combinatorial pure exploration. In Conference on Learn- ing Theory, pages 482-534. PMLR, 2017.
[CK18]
Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan, Quantile-regret minimisation in infinitely named bandits. In UAI, pages 425-434, 2018.
[CK19] Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan. PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits. In International Conference on Ma- chine Learning, pages 991-1000. PMLR, 2019.
[CL15]
Lijie Chen and Jian Li. On the optimal sample complexity for best arm identification. arXiv preprint arXiv: /5/ 1,03774, 2015.
[CL16]
Alexandra Carpentier and Andrea Locatelli. Tight (Lower) Bounds for the Fixed Bud- get Best Arm Identification Bandit Problem. In Conference on Learning Theory, pages 590-604, 2016.
[DA92] Alejandro De Acosta. Moderate deviations and associated Laplace approximations for sums of independent random vectors. Transactions of the American Mathematical Sociery, 329(()3357-377 1992.
[dHCMC21] Rianne de Heide, James Cheshire, Pierre Ménard, and Alexandra Carpentier. Ban- dits with many optimal arms. Advances in Neural Information Processing Systems, 34:22457 11222457-2246, 2021.
[EDMM02] 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.
[EDMM06] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action Elimination and Stop- ping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems. Journal of machine learning research, 7(6), 2006.
[GHRZ19] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched Multi-Armed Bandits Problem. Advances in Neural Information Processing Systems, 32, 2019.
[GM14]
Spencer Greenberg and Mehryar Mohri. Tight Lower Bound on the Probability of a Binomial Exceeding its Expectation. Statistics & Probability Letters. 86:91-98. 2014.
[GM20]
Ofer Grossman and Dana Moshkovitz. Amplification and Derandomization without Slowdown. SIAM Journal on Computing, 49(5):959-995) 2020.
[Hoe94]
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In
The collected works of Wassily Hoeffding, pages 409 426. Springer, 1994.
11

---

[JMNB14] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil UCB An Optimal Exploration Algorithm for Multi-Armes Bandits. In Conference on Learning Theory, pages 423-439. PMLR, 2014.
[KCG16) Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best- arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
[KG21] Tomás Kocák and Aurélien Garivier. Epsilon best arm identification in spectral ban- dits. In IJCAI, pages 2636-2642, 2021.
[KSJ20] Julian Katz-Samuels and Kevin Jamieson. The true sample complexity of identifying good arms. In International Conference on Artificial Intelligence and Statistics, pages 1781-1791. PMLR, 2020.
[LCLS10] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- approach personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[LJD+17] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Tal- walkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1 (88(1)6765-66))) 6616, 2017.
[LP14]
Kyle Luh and Nicholas Pippenger. Large-deviation bounds for sampling without re- placement. The American Mathematical Monthly, 121(5):44-445, 2014.
[LPB17]
David E Losada, Javier Parapar, and Alvaro Barreiro. Multi-armed bandits for ad- judicating documents in pooling-based evaluation of information retrieval systems. Information Processing & Management, (655):005-1025, 2017.
[LR85]
Tze Leung Lai and Herbert Robbins. Asymptotically efficient Adaptive Allocation Rules, Advances in Applied Mathematics, 6:4-22, 1985.
[LS20]
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[MNS16]
Amit Moscovich, Boaz Nadler, and Clifford Spiegelman. On the exact Berk-Jones statistics and their p-value calculation. Electronic Journal of Statistics, 10(2):2329- 2354, 2016.
[MT04]
Shie Mannor and John N Tsitsiklis. The Sample Complexity of Exploration in the Multi-Armed Bandit Problem. Journal of Machine Learning Research, 5(Jun):623- 648, 2004.
[MU17]
Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
[Nie20]
Frank Nielsen. An Elementary Introduction to Information Geometry. Entropy, 22(10): 100, 2020.
[PRCS16]
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched Bandit Problems. The Annals of Statistics, pages 660 080-681, 2016.
[RLS19]
Wenbo Ren, Jia Liu, and Ness B Shroff. Exploring k out of Top p Fraction of Arms in Stochastic Bandits. In The 22nd International Conference Artificial Intelligence and Statistics, pages 2820-2828. PMLR, 2019.
[Sli19]
Aleksandrs Slivkins. Introduction to Multi-Armed Bandits. Foundations and Trends in Machine Learning, 12(1-2):1-286. 2019.
[TRMD21] Parth K Thaker, Nikhil Rao. Mohit Malu, and Gautam Dasarathy. Pure Exploration in Multi-armer Bandits with Graph Side Information. wrXiv:2108.0155: 2021.
[WAM08]
Yizao Wang, Jean- Yves Audibert, and Rémi Munos. Algorithms for infinitely many- armed bandits. Advances in Neural Information Prucessing Systems, 21, 2008
[ZKSN22] Yinglun Zhu, Julian Katz-Samuels, and Robert Nowak. Near instance optimal model selection for pure exploration linear bandits. In International Conference Artificial Intelligence and Statistics, pages
PMLR, 2022.
12

---

A Proofs from Section
Algorithm 4: Output & E [G m1) G. 71 + 72) + {] with probability
input: arm S (01, (2,...) and parameters (7) 6, 6, (0, with f/2 < 7/1- initialize: K Cm 1/6)
3 for i = 1,2, K do
Collect n C (0m(1/m)) samples of arm Set p.(nn) to be the average observed reward.
end
Let á be the k-th largest value in {pI, .P......P. .p] for le [K(m )
Return á
We show the following generalization of Proposition 2.1.
Proposition A.1. Fix 0 S 71, 12, E, 8 S 1 with S m1. With probability at least 1 8 2. the output of Alg. satisfies
E G (1 m))
E 3. G (1 71 + 72) +
Moreover, Alg. 4 has sample complexity
log( 1 1/2z) (og(1/8)
Proof. The sample complexity is clear we focus the first statement. First observe that by Chernoff estimate, for each i E [K],
72
P P: psl
(A.1)
3
Applying a second Chernoff estimate (of multiplicative form, e.g. Theorem 4.5 in [MU17]) these events varies and noting that
Let ((s) be the number of E [K] such that [p; -
Kr)a 2 Cllog( (A.1) implies
Knz
8
P N(E)
<
2
1
(A.2)
6
8
We next show that with probability at least
6 4 1
à asa+ G (1 131 122)
(A.3)
With p3 the (truc) mean reward from arm a;, let
N Ki E [K] p: > 0
denote the number of the tested arms which satisfy p. > प. By definition, N, is stochastically
dominated by a Bin (K, m that
O(7) since 1/2 S mh Note 993 random variable, and 171
3m
10
1
97/2
312
7
1/1
7/1
4
9n1
7h
10
1 +
71
2071
Therefore another multiplicative Chernoff estimate implies
P No < K
37/2 111 4
)
2 (m(Kggmm) >
When both (e) < Km and N₂ < K (m 6
3xp) hold, it follows by definition that à < 0 +
Hence recalling (A.2) above, we conclude that
P
p
> 1
8 4"
13

---

establishing (A.3). The other direction is similar. With G (1 71) as usual. we set
Na Ki E [K] : p. 2 a3|-
(A.4)
This time, N, stochastically dominates Bin mi) random variable. Yet another Chernoff esti- mate yields
P P(N. Using (A.2) in the same way above, we find
K m 2 }
8 8
1
4
a 2
87
8
2
3
4
This concludes the proof.
Proof of Theorem 2.1. First we analyze the expected sample complexity. On the event that
â
L -
E G -
(A.5)
we claim that Alg. 2 terminates with probability 17/ for each a,. Indeed, if
2. G 12-''(1-3)
then termination always happens by definition. This has probability at least 1/4 2 G- (1-
by Theorem in [GM14], and the latter condition holds with probability at least 17/ by definition. follows that when (A.5) holds, the expected sample complexity of Alg. O
[ogg11/0)]
On
ne²
the other hand, (A.5) fails hold with probability less than 8. Because of the explicit termina- tion condition in Alg. 2, this yields a additional sample complexity contribution of smaller order
log(1/8) (1m6) Finally Alg. 4 has sample complexity 1/2
( log(L/n) log(1/6)
17c2
which clearly forms the dominant contribution. This completes the proof of the sample complexity bound and we now turn to proving correctness with probability - 8. First, it is easy to see that
2- It therefore suffices to show that for any fixed à satisfying (A.5), conditioned on the event p.
Alg. 4 outputs some arm with probability at least 1
5. the conditional probability that
p: 2 a e is at least 2-
We do this using Bayes' rule. pf 2 G-1(1
)), then above Theorem in [GM14] implies
P p 2 à
pp p. 2 1/4.
This event hence contributes probability at least 7 to the event pt 2 G-1(1 17). On the other hand, if pi < G- G-1(1-1-00 1)
2r then
p
e 3 p
p
p. 2
8 3
n8/8
for absolute constant C. Combining these via Bayes' rule implies the desired result.
B Lower Bound for Fixed Budget
Fixed Budget with Unknown
Before giving the proof, we give some qualitative discussion of the role of unknown a. We consider Theorem 3.2 to be definitive lower bound, since e.g. being given the value of only makes the result stronger. When a unknown, more care is required when stating the result. This is inherent and stems from the fact that the value = G (1 17) can be difficult even impossible to estimate, yet determines the constant Ca,9 in the desired rate.
possible to give an essentially matching algorithm, but
14

---

Let us illustrate the issue by a counterexample. Consider Jo defined by:
pa~uN I = =0.4] 10N
(B.1)
pPAAN Ip pp=00 0.2]
10N
Similarly define eo by:
1
paiAN 0.4]
10N
2
penAN yV - 0.3] = 2e
(B.2)
pp~AN Ip 0.2]
ION
Then nN and j.n not distinguishable using N samples, yet G (1/2) 0.4 while T (1/2)
0.3. Using non-distinguishablity it follows that the lower bound of Theorem 3.2 applies to jayy with threshold a = G (1/2) = 0.4, as opposed to the direct application using Gpv (1/2) = 0.3. It is not hard to show using monotonicity of v2(1-z)
that
1- C0.3,03--
for all e < 0.3. As result, it is information-theoretii AN if the target quantile value a is not given. The core reason is that the value Gj²²' (1/2) = 0.3 is too sensitive to the choice = 1/2 of quantile.
impossible to achieve the rate (3.1) for
Fortunately, this issue is more of an annoyance than real difficulty. It can be fixed in several ways. In Theorems B. B.2, and B.3 below give three concrete formulations under which the guarantee (3.1) can be achieved, as mentioned in the main body.
Theorem B.1. For fixed M1 12,E, there is sequence (An) of N-sample algorithms outputting a, such that the following holds for any sequence (JN) N21 of reservoir distributions. Letting
uux (r)dr (z))d
171
172
1-m
be a quantile average of px. we have
(-log Plps.
< <aN - E|) log" N > 1.
lim sup N
(B.3)
Cax.ax-E N
Theorem B.2. For fixed T, there is a sequence (AN)N21 of N-sample algorithms outputting a.- such that for any sequence of reservoir distributions μ&n satisfying
1
Ox = == (1 2
we have
(- log Ply;: < G (1 n)) - =]) logg N
lim sup
2 1.
(B.4)
N0000
oox N
e, there is a sequence (An) of N- N-sample algorithms out- putting ar- such that for any fixed reservoir distribution μ with μ² > E,
Theorem B.3. For any fixed
(- looog1Pppe
< ,² - =1) log² 2 ---
sup N 200
(B.5)
N
We emphasize that the rate (3.1) is optimal in all cases since the lower bound of Theorem 3.2 is for an easier problem. The first formulation above may be the most principled choice. The idea is that an averaged quantile depends continuously on and can in fact be estimated by applying Proposition A. for several pairs (m, 172) and computing Riemann sum. The second formulation I+e and uses monotonicity of Ca.a- on this set. (In other requires only the mild condition that a 2 2
words, if the average reward values p appearing in (B.1), (B.2) were larger than 0.5, there would be no counterexample.) The third formulation allows us to almost send 17 all the way down to 0. It uses the fact that
(e) =) S T (1-1))
for some n/ = (1, e), > O. These results show that (3.1) achievable even without knowledge of a, up to choice of technical modification to sidestep the counterexample discussed above.
15

---

Remark B.1. In fact uniformity in (a, holds in the following sense. For any sequence (ON, BNN.N of pairs with min (SN.0x, ON AN,T - aN) uniformly bounded below, there sequence (An) of N- N-sample algorithms such that for any yf E (0,1) and any sequence of reservoir distributions J. with G 17) 2 ON,
(- log Plp-- < <BN)) log" N 1.
lim sup
(B.6)
N N-+00
Ca
This can be shown identically Theorem 3.1, though we don't give the proof this generality. is useful for the reduction arguments in Theorems B.I, B.2, and B.3.
B.1 Preparation for the Proof
Here we prove Theorem 3.2. For any 3, 7, 0 >> O we construct reservoir μ = Ma.B.n. such that
lim inf (- log TP' pp- () log? N
Co,B + X(e)
(B.7)
N +000
holds for any sequence of N-sample algorithms AN, and where lim X(e) for fixed a, 8
B.2 Admissible Reservoirs and Bayesian Perspective
In proving Theorem 3.2, we will use reservoir distributions of specific form. Namely, require each j to be supported on an interval [ 7/. where
3 - < 3 < < a
In fact we define 2, explicitly (recall that 0 > is a small constant which we eventually send to 0) by
( (33) e²: ( ((a) + e²².
(B.8)
We say is ff) admissible if y has density u(dx) (x) for a Borel measurable function and satisfies for constants 0 < 00.
f(x) [S,], Vo 12, 7]
Towards proving Theorem 3.2, fix throughout this section some (2 f.J) admissible such that GN Ga) = holds, for appropriate constants (f, depending only on (n, E, oz (,77)) is easy to that this is always possible.
An admissible reservoirs gives each a; the potential to slowly degrade in observed quality over time, We remark that while it is more convenient to work with reservoirs supported away from the boundaries, i.e. in 12 7l S (0, 1), we not expect this to be essential.
roughly comparable to the uniform distribution interval. Using admissible
will be helpful throughout this section to take a Bayesian point of view. We treat an as known to Av, since Ay is in fact allowed to depend μN. Thus each time t, each ps has posterior probability distribution which we denote by Pi,t- Note that each μ4, depends only on (ni,a pr,)) and initialized at 14,0 μ. We denote by
14 (M1,ts ...
(B.9)
the sequence of posterior distributions urP.. Since arms are independent, 2² is the full time-t poste- rior of the algorithm.
B.3 Batched Algorithms and Adversaries
In pure exploration problems, it is possible to significantly simplify the structure of any algorithm the cost of a small multiplicative increase in the sample complexity. carry this out using the notion of batch-compressed algorithm.
16

---

Definition B.1. Given an increasing sequence B = (b,, b2...... of positive integers, an algorithm A is B-bbath--omppresed can only act by increasing the number of times n, that a, has been sampled from by to bk+1, so that E B holds at all times. B is g-slowly increasing if
bu+1 S1+
vk
by +
Finally if B-bauch-compressed and B is g-slowly increasing, we say that A is g-batch- compressed.
Unlike the batched algorithms studied in [PRCSI6, GHRZI9), batch-compression only important for analysis technique. Indeed the following proposition shows that it does not fundamen- tally affect pure exploration algorithms.
Proposition B.2. If B is p-slowly increasing, then for any N N-sample algorithm A, there exists an B B-batch--ommpressed [N e) algorithm A' with the same output.
Proof. We show how to simulate A using the B-batch-compressed A', assuming that the sequence of rewards for each a, fixed. Each time A samples arm i for the n, (ax + 1)-st time for ag E A, A' samples arm until n, ax+11 Then A' has all the information of AA at all times, hence can simulate the behavior and output of A. Moreover by the definition of g-slowly increasing, the sample complexity of A' is larger than that of A by at most factor (1 Q).
We will the above with @ 0 slowly N oo. Then the sample complexity increase 1 e is absorbed into the 1 + o(1) factor in Theorem 3.2. As result it suffices to establish (B.7) under the additional assumption that Ax is g-batch-compressedd
B.4 Fisher Information Distance
Determining the tight constant Ca.s requires significant care. In particular the adversary must de- crease the empirical average rewards pi,, at precise rate depending on ng, This rate turns out to involve the Fisher information distance. For a, [0, we define the Fisher information distance da b) between and to
dx
dr(a, b)
/x(1
This agrees with the more general Fisher information metric when each [0, 1] is identified with the corresponding Bernoulli distribution. We refer the reader to [Nie20] for survey on informa- tion geometry. In short, the Fisher information yields natural Riemannian metric families of probability distributions which are parametrized by smooth manifolds. However we will use only elementary properties of de.
We parametrize [0, 1] using the function 0: :0,1]] - [0, T] defined by
((a) = dr(0,a) f dr
arccos(1 - 2a).
(B.10)
Va(11 x)
In particular,
(a(a,b) b) arccos(1 2a) arccos(1 2b) 2/a -b]
and 1) The main property of that will use is the resulting differential equation
6' (a) ((aa)((-((a)))
(B.11)
In our case, 0-1 parametrizes a "constant speed" path through the space of Bernoulii variables, view- ing the Fisher information. Correspondingly, our adversary will ensure that ((p(()))) decreases linearly in log(n..).
17

---

B.5 Preliminary Lemmas from Moderate Deviations
Recall that for positive integers and b, the Beta(a, b) distribution has probability density function
(a 1)! (1-2)-01
(a 1)!(b 1)!
for [0, 1]. We now recall moderate deviations principle for the binomial distribution and central limit theorem for the beta distribution.
Lemma 4 (Theorem 2.2 in [DA92]). For any 0 < 9 < q < 1 and constant @ > there exists Dulg. 9. 0) and Mo(g. 9, 2) such that the following holds for all p E lg. For n 2 no (g. 7, Ø) sufficiently large and any Dovn S SAS
Do we have
ppp 2)n P
Bin(n,p)
Sp- - 0 S sel (-apipp te) -e))
Lemma 5 (Lemma A.1 in [MNS16]). Let fan hozn be sequence satisfying
On 7.
n
Then the Beta(n - an + 1, an 1) distribution on [0, 1] obeys a central limit theorem with mean t
and standard deviation v [an (0n/m)(1(ew//)) in the sense that for any bounded sequence (Wa)n2no
n
of real numbers and with the normal CDF,
lim ((wn) pe--oetat---o on +1 10000
(xr - (an/n))
TU (on/n)(1 (0n/n))
S Wn
In the next two lemmas, we lower bound the probability that Pi,a changes significantly when the number ni of samples for a; increases by a factor (1 + g).
Lemma 6. Assume is (. (.)m.ss.)aa admissible. Suppose that arm i's average reward Đ., after n = ns samples satisfies
pi, 13,77.
(B.12)
Then for n 2 T.2.7.1.333 sufficiently large,
f
paiiin nn [o S Pr. 2
(B.13)
3f
Proof. Let Ri, npr., be the total reward from arm i so far. The posterior distribution pa. for p takes the form
f f())dx R., 17 Ro x7) -R. fx)
xB. (1 x) Ru.
(dx(dr)
For [7 we estimate
Ri. (1 n- Ri, f(x)
Ri, (1 x) Aon--RRR Ru, So Bi. (1 x) Ri dx
(./T)
1 x Ru. (1 z)n- Rr,, fxx)dx
The right-hand side is the density of beta variable with parameters (Ri,t + 1, Rii + 1). We conclude that
paopar xx Pr.ll 2 (1/7) R...BBetanRR,.tLBB....
Pt.l]
For n sufficiently large, follows from Lemma 5 and (B.12) that
Be-BBeann- [a E b2 Pr.l] 2 1
Therefore p*.. S P... 2 J. proving (B.13).
18

---

Lemma 7. Assume is (.....FF) -aaf:f)-admissse admissible and that (B.12) holds. For Ri,s let ñ 2 satisfy i gm) I 2. Let
p: Rin++ A Ri,m
be the average reward from the (n + 1)-th through (n it)-th samples of arm i. Then as n - oc, for any sequence An (1/ n).
+1 +0 onn))
PI S 0 1- (0(pr.)) An)) 2 exp
(B.14)
2
Proof. Stochastic monotonicity implies that
Bin( p)
P
< 0- (0(fee)) - Amn)
ñ
is a decreasing function of p E [0, 1]. Combining with Lemma 6, it follows that
P' s (0($st)) An) f Bin((,,)) x)
0 (0($t))) - Am)) dss),)(r)
Cin(T,,P..)) S 002 (0(bsr)) A..)
> paue lys S pi,e] P
ñ
< (0(pec)) Am) Bin Can(M,P.... pr.e)
P
3f
n
Since 0 is smooth with smooth inverse
[2 and An (1), have
Pr, (B(P.)) An)
o, (0--) (1 + on (1)) An
0'(0-1(i..))
(1 + on (1)) An Pr.e - pr.)).
The result now follows from Lemma 4, where we absorb the factor //(3/) into the on (1).
B.6 Proof of Theorem 3.2
Recall the definition (B.8) of y and 7. We require A be B-batch-compressed for B(N, containing:
1. All positive integers at most 2
2. All positive multiples of [ at most 660,
3. Integers of the form (1 + e)d1 for 2 0.
It is easy to that B thus defined is g-slowly increasing for any 0 and N sufficiently large. We denote by (1 + e) so that [bx+1 (1 + g)6x| < (This choice indexing differs from that of Definition B. which will not be used in the sequel.)
We next construct our randomness distorting adversary A ANN, g). For each arm i, the adversary acts as follows depending on the current number of samples nh,t-
1. If n5, S 2e, then A does nothing.
2. When N2e < ns,, < N6e increases by Ne, declares that the average reward of this batch of Ne samples is at most 7 -
3. When ni,t increases from by 2 6o to bx+1:
(a) If (b(b)) > 3 holds, then A declares that
0(p, 1)) S (bp)(b)) e(1 + 10 (a, 3)
(B.15)
log N
19

---

for a constant C. = (. independent of (and N). We show this bound in several parts. Recalling (3.4), we refer to the cost of step above the contribution Cost from the corresponding declarations by A. The most important parts are Lemmas 10 and 11, which bound the cost of the main step 3a and form the dominant contribution to Cost. Note that throughout the (b) If (bx) Σ 3 holds, then A declares that
(bb++1) S B.
4. When the chooses the arm a,- to output, declares that p:- <B.
Due to step 4, the declarations made by A ensure that pi- < B. Recalling Lemma 4 and Proposi- tion B.2, it remains show the upper bound
strength(A) S (Ca.3 + C.O)N
log"(N)
analysis below, all cost upper bounds hold almost surely and we assume that all of A 's declarations hold true.
Lemma 8. The total cost from step 2 is at most C_Nt-e,for N 2 C J, 2) sufficiently large.
Proof. The probability for each such declaration by A is at least
P[Bin(NV2 77) S 7NV2 No]
(B.16)
since p; < 7 almost surely. Recall that a Bin(N22 (e 7) random variable obeys a central limit theorem centered 7N2e with standard deviation at least ((T) Therefore the probability in (B.16) is at least 1/ for N is sufficiently large depending on Hence each such declaration costs at most C, for N sufficiently large. Moreover such declarations can occur only N times because each one involves N2 samples, and the base algorithm an N-sample algorithm. This completes the proof.
Lemma 9, The total cost from step 3b is at most C.Nl-be as long N 2 C(,,7,5,..e)
Proof. It suffices to show that the cost per step 3b declaration is most C.. This follows from (B.13) and stochastic monotonicity.
Lemma 10. The total cost from step 3a is at most
N
(Ca,, + C.
log" (N)
Proof. We claim that the cost from single instance of step 3a when increasing from by to bx41 samples most
(Dtt1- b&) (Ca.3 + C.e ox())). loV)
This implies the desired result since Ay is an N-sample algorithm. Taking A (1 + 10g)d (a, 3)/ log(NN in Lemma 7, we find that the declared event has probability at least
exp (- (b++1 b1)(1 100) (1 + (x()))
exp (- [[bb+t - bb) (ca.s C.e+ C.e+ xx())
2 2lgg2(N)
log?
This implies the desired claim and completes the proof.
Lemma 11. For any a, sampled by [ times, pi(b)) S 7.
Proof.
By definition of A.
N28 + - (T N-
(b0)) <
Noc
= Ne + (1- 7)
1
N4
Noe
S
20

---

In the last step we used the fact that
(1
11-77
+
Ne
N4g
N5e
for any @ > if N is sufficiently large.
Lemma 12. For e (0,1/100) if ni, 2 NI-e and the declarations of A. hold, then Pi.e. B.
Proof. We analyze the at which the adversary forces ((f((b))) decrease. From (B.15) and (11) it follows that for k with by 2 N2-e, we have
(bb() {(7) o(1 10g)d (a, 3) log lo 88)
log N -( 2(1 + 10g)(1 8g)dr(a,
log(1 e)
< ((()) - (1 + 2).
(88)
0(3).
Here we used the fact that log(1 + 0) - and (1 + 10g) - 80) 2 for E (0, 1/100). Since increasing, this shows that Pi,. (bx) for by 2 N completing the proof.
Lemma 13. The cost from step
most C. e
Proof. First, if pi S 3 then the cost from step 4 is at most C., On the other hand if p.-.N .v >> B, then Lemma 11 implies nt+ NN S N Since the prior I supported in [y, 7). the likelihood ratio of updates from N samples is almost surely bounded by cCC N'- Therefore
panmA [xr x 2 e C.N² w---pmp "p {}]
2 C,N (B (--2)
This completes the proof.
We now combine the lemmas above to conclude Theorem 3.1 via (B.7).
Proof of Theorem 3.1. Let C², be larger constant depending on the same parameters. Then by Lemmas 8, 9, and 13, the total cost from Steps 2, 3b, 4 combines to C",' S ON(//oog N). The main cost contribution of
(Co,8 + C.e ox()))
log² N
comes from Lemma 10, and all other terms are of strictly smaller order. We have thus constructed reservoir sequence (Ju (2)) satisfying (B.7) for arbitrary @ > 0, completing the proof.
C An Optimal Algorithm with Fixed Budget
Here provide asymptotically optimal algorithm which establishes Theorems B. B.2, and B.3. In the next subsection in which we show how to reduce the other results mentioned to Theorem 3.1 (in which is given) using Proposition A.1. Our main focus will then be prove Theorem 3.1.
We will fix 0 small and construct sequence of N-sample algorithms (A(N, @)) satisfying the slightly relaxed guarantee
(- (ogg (p-- < B)) log² N
inm N0000
2 Ca.g X(e)
(C.1)
for (possibly different) function À satisfying lim X(e) 0 (for fixed a, B) Here (HN) N2 is any sequence of reservoir distributions satisfying Gpy (1 7) An elementary diagonalization argument then implies Theorem 3. Thus it suffices construct algorithms satisfying (C.1) for any desired >> 0.
21

---

C.1 Reduction to Known
We explain why Theorems B.I, B.2, and B.3 all follow from Theorem 3.1 (more precisely, the uniform statement given in Remark B.1). begin with Theorem B.I, where
1
G (x))dz.
ON
1/2
1
Let =
6 ((m1-12))
and define
n00) (J - j)m + j5z
jE [J].
is easy that of 1 m16) for all We next apply Alg. 4 on (1710, (110),)((t))) (1(+t))11800 ,',0,,',87
for 0 S S J - 1, with:
6' log 1033-1/3(1) (N3,
10 8' = (N) [N) /J.
This requires sample complexity
C(n,, 72) log log(N)
NA S
I ON\)N.
(C.2)
log(N)
Let dz be the resulting output. With probability - J8, we have for each 0 و JJ
àg E (1--(1-700) -
8 G (1- (1- 11-nn((111 (141) 3
+ 8
CC.)
3
Note that the function Gj. is increasing and [0, 1 1a-valued. Therefore if (C.3) holds for each j. then
65
1-92
G
8 + $ ] 2
J
111
112
1-m
3
j=0
Therefore the estimator
J-1
1
âΛ j
Σ
1=0
satisfies
||
m2
10Y (ox
P AA
S E/2
2 1 J8 =
1)1 172
1-m
10%
Finally, Ca,a-e I 10 for any a, [0, 1] (see (B.10)). Therefore the 8' probability above has a negligible contribution Theorem B. It follows that applying Theorem 3.1 with a 2a above and N' N NA implies Theorem B.
Tog (N) failure
We now turn to Theorem B.2, where μN is required to satisfy G (1 n) 2 1te We run Alg. with parameters
7/1 1 ?/2 log 1/3
e' log 1/3(
10N 8' Toa
The sample complexity NB again satisfies NB I o(N) exactly as in (C.2). Let â + ef be the resulting output. Then with probability least 1 (Ne
âB 2 G-1 (1 - 17) - -
and so with = 25', we have
âg - > G-1 (1
22

---

10N
Moreover, also with probability at least e (og)(N))
âg G 17 72)-
It follows that applying the algorithm of Theorem 3.1 with
(N, a, T,E) (N NB, 72, 8 25')
suffices recover Theorem B.2, since ?/2 and e' tend to 0 as N As in our discussion of 10N Theorem B.1 above, the failure probability e (ox is negligible compared to the relevant rate in Theorem B.2.
Finally, Theorem B.3 relies on the simple fact
lim G Gr - 7-0
(C.4)
Recall that f² E [0, 1] denotes the maximum value the support of μ. We run Alg. 4 on (n, 72, 8") where:
7 log (1))
7/2 m//2,
9' E1
10.8 8' (NN)
follows from Proposition A.I that the resulting output åc + _ computed using ) S o(N) samples as in the previous cases. Moreover for N sufficiently large:
O N log log(N) (og(N)
àc +
81 -
2 p
e' 3
-o((1)
(C4) 2 P
àc +
-1
2 Gp 71) 3
2
2
1&N e
(N))
Since E1 e, this means for 2 No(H, (', .....) large enough,
10
plác 2 μ²= - (8) - $)] 2 1
(N)
10. lox
Note that Alg. 4 also ensures that with probability 1
-
n¹ El
àc S n²
S H 1 - r/)
for some (1, 0. It follows that applying Theorem 3.1 with (N,a, (N N², a/
implies Theorem B.3.
C.2 The Fixed Budget Algorithm
We now present Algorithm for the fixed budget problem (recall informal discussion Sec- tion 3). Algorithm 3 studies one a; at time, moving 0;+1 if a; is rejected. Similarly to the previous section, some details are needed while n4, is small, since large deviation asymptotics may not have kicked in yet. As explained the start of the section, we choose small constant 0. In fact, we will eventually choose small constants
0 e @l
02
03
04
0s <
which all tend to 0 as - these values can be obtained by choosing @ > arbitrarily small, then e4 > sufficiently small depending Ø5. and so
0. These constants will be defined throughout the proof. More formally,
23

---

Algorithm operates in batch-compressed way, for sequence (b1, b2....) defined as follows:
bo Toi log (N)1,
Ko flogite (log' (N)/bu)]
bk 6o + e)a, k S ko
bko+ = [(1 + bko 1, j21
Tk a Vlog N'
k: S ko
Tho+J 0(a 20) - dp (a, 3) 02) log
j2
Note in particular that bkp 2 log) We denote by Pt, the empirical average reward collected by a, from its first samples.
Algorithm 5: Output arm with p: 2 8 using N samples with high probability
input: infinite sequence of arms 1,2....
2 initialize: i=0 0
while fewer than N samples have been collected do
i ++++1
Collect by samples of arm i.
if pi S. a then Reject arm end
for k= 1, 2,... do Collect by- b samples of arm for a total of by samples. if di < a e- Vlog then
10
11
Reject arm i; end end
13
14
for j = 1,2,... do
16
Collect bkots - bkotj-1 samples of arm for a total of bjo if O(p, s 0(a 20) j. dr (a.0))((10))) then
17
Ing N
end 18
Reject arm
19
20
end
21 end
Return arm i.
The role of the values by is as follows. When an arm a; reaches by samples for some 2 O, it is checked for possible rejection by comparing its empirical average reward to the threshold Algorithm rejects arm and moves to arm 0;+1 if the empirical average Pi of arm a, drops below moving threshold тк- The threshold Tę begins close to and gradually decreases until reaching by the time тę 2 ((N).
So for, our informal description of Alg. 3 also applies to the algorithm proposed in [GM20]. We now highlight two important differences. The first is that algorithm is defined more carefully during the "early" phases when an arm has been sampled at most (e( times. This is crucial for carrying out a rigorous analysis. The second difference that in the main phase, we increase the sample size for given arm in powers of 1 + e rather than powers of 2, and also move the rejection thresholds T based on the Fisher information distance via the function 0. The latter ingredients allow us to obtain the optimal constant factor.
We begin the analysis of Alg 3 by proving Lemma 3.
Proof of Lemma 3. Let M, I1ss, Y, and observe that Mf is positive supermartingale with Mo = 0. The result follows by Doob's 's maximal inequality.
D

---

We will apply Lemma 3 in the following way. Let X, be the number of samples used by arm a, before rejection, and I; {0, 1 be the indicator of the event that a, ever rejected, even Algorithm 3 were to continue past time N and sample arm an infinite number of times. We set
Y xi
With M defined from (Yi)21 as in Lemma 3, it follows that log( M) is at most the amount of time spent on eventual rejections before the first eventually accepted arm. Therefore if log( S N(1 - Ø), we conclude that the last arm to be studied was sampled at least Ne times. Since it was not rejected during that time, we can conclude this arm has pt 2 B with probability - (N), The main contribution to the failure probability of Algorithm comes from the event (M 2 A] above, for suitable A. Correspondingly, the main work will be to verify [E[ S 1 for suitable c.
Note that Y, E {0} U [1. oo) almost surely for each i. Therefore a necessary first step in showing [ S to lower bound PlY; = 0j, the probability that Algorithm 3 never rejects ag. We now give sufficient lower bound from the event p;
Proposition C.1. Let T2.... be an ii.dd. Bernoulli(p) sequence for p 2 a, and let Sy = =E/ and set
= Sx/k.
#21
Then S a holds with probability at least c(ux, e) > Thus E[A.] S - c(a. (). e).
Proof. Since the probability that S 2 a - o is increasing in it suffices to take = a and show the probability positive for any e > Assume not. Then by restarting the indexing every time Sy S k(aa- - 2) holds, we find that
lim inf Sp/n a n-+00
This contradicts the strong law of large numbers, thus completing the proof of the first assertion. The second assertion follows since if S i, then arm i will never be rejected by Algorithm 3.
o for all i where T1,--. the rewards of arm
Based on Proposition C.1 above, to show
%a.8 lox
E
I
S
(which is essentially what we want in light of Lemma 3), suffices to show that
(((
So.d -y log
1)) 1 s c(a,, Ø)-
E
(C.5)
We let 15 = 1: x; be the event that arm was rejected after exactly / steps. Since Alg 3 can only reject after by samples, we have
We use this to break the left-hand side of (C.5) into three separate parts and estimate the parts separately. The parts correspond bu, by through bkg, and b onward. The first two parts casier and handled Subsection C.3 below. The final term is the main contribution and is handled in Subsection C.4.
C.3 Analysis of Algorithm 3 in the Small and Medium Sample Phases
Proposition C.2 bounds the contribution to (C.5) from the small sample phase, i.e. the first rejection condition in line 7 of Alg 3.
Proposition C.2. For any a, there is 01 > 0 sufficiently small that with by defined above, and with sufficienlly large,
-1) 1100 s c(a, o)/4
E
lox'
25

---

Proof. It suffices to observe that for fixed and small and N sufficiently large, we have
15 e - S 201-
Proposition C.3 bounds the contribution to (C.5) from the medium sample phase, i.c, the second rejection condition in line 12 of Alg 3.
Proposition C.3. For any 2: 21 and for N sufficiently large,
ko
Son. 43 log
-1) 1 S c(a, 0)/4
Proof. The event thth requires Di,by regardless of the true reward probability pi.
Pi.be
Hence by standard Chernoff estimate,
Vlog
B S
Ranene (bx/ log N)
Since by construction by 2 @1 log N, we have
E
Xi
"0.0- o0 lox
-1)
1e
s by S0 lox" Duroo (be/ log N)
S Raroos (log N)
= N- (1)
Since kn S Ollog N), summing gives the desired conclusion.
Propositions C.2 and C.3 imply that the total contribution from rejections the small and medium sample phases is at most c(a, 2)/2. It remains to analyze the large sample phase in the following subsection.
C.4 Analysis of Algorithm 3 in the Large Sample Phase
Similarly to the previous section, the main part the analysis concerns the large sample phases bko+j for j > 1. Our goal is to precisely estimate the rejection probability at each time bku+j- Note that these estimates should not depend on the true average rewards pi-
Our approach is based on exchangeability and avoids any consideration of p.. For given value and large constant L L(e), consider the sequence of times
bko Ly bkot L+1
bkg
and the associated sequence of empirical average rewards
Di 11 Pi. 2:17
Pibbo
(C.6)
follows from the algorithm description that for 1, beats occur, we must have
Pebrotz Pibbigtse 2 da 3) -2) 02)
VISEs
(C.7)
log N
This is clear for j > I,, but it holds also for 0 S S L as for N sufficiently large,
ko L. dr 02) 2g-
Vlo N
log N
By exchangeability, conditioned the future values pi Pi the law of -ibb depends only Pi.b and is given explicitly by hypergeometrie variable. Recalling that
26

---

R = ni.ePk, is the total reward from the first Re, samples of arm i, Ro.bbo-s-r-1 has hypergeo- metric conditional law given by:
Rs Reg = k (attttt
Pr.b
P Rs, Rs,b le Dr,
(MKo 2) (MMO e-boo 13 1)
Reg (-
(C.8)
bbg +3-)) R
We will refer to this as the HyperGeon (eppereom(Doott--// bko Rko+s-e) distribution. Importantly, this distribution is independent of We exploit this below to control the probability of given sequence (pi,beo+s-2. Pibbo+t-2-11 .... pi.b of empirical average rewards. The following useful result states that hypergeometric variables automatically inherit tail bounds from the corre- sponding binomial random variables.
Lemma ([LP14, Hoe94]. Fix non-negative integers 2 B,C and let X HyperGeom (A, B, C) and Y Bin( C/A). Then for any corvex function - R.
B[f(x) S [B(())).
For any 0 < < q < and constants > 0 there exists Dolg, T, e) and No(g 7, 2) such that the following holds for all p [g. g. For n 2 no sufficiently large and Dovn S A s Ao.
Lemma 2.
HyperGeom(nn11+ + 2), np(1 + 2)) p 2
te)
Proof. The corresponding binomial result Lemma 4 is proved in Theorem 2.2 in [DA92] by upper bounding an exponential moment. The same proof applies here by Lemma 1.
It will be convenient to define restricted set of good sequences (qL, 9L-1, 90). These satisfy the key properties empirical average reward sequences (C.6) for which 1o holds. We say such a length L sequence is good if the following conditions are satisfied:
1. go E 7 (0,1) for constants < ạ depending only on e, L.
2.
max 19c, -4a - ((1/ N). f1.2
(C.9)
3. For each s L:
((go) A(a= 2g) - dr(a,,
3) d
22)
log N
$ O(a 20) - (j ()- 3) 02) S ((gr)-
log N
The third condition above necessary for 1 phootoif 1, and these together imply the first condition. Indeed for fixed g, and small E (0, 1/10) one always has
Pi.boots-1 1 Ps.bauts-1 E 20, (1)
pibbatt 1 Pibbuts
for large enough N and any j. Hence it suffices to take q 3(1-20) and - = With this choice, if
11-1-a111
Pibbegt--: Pr.be4t--441
pi.be
not good and 1, N. 1, then the second condition must be the only violated one. The fol- lowing easy lemma controls the failure probability of the second condition. Recall from (C.8) that
conditioning on Pi,brots determines the joint conditional law of the previous conditional rewards, regardless of μ.
27

---

Lemma 3. All sequences violating only the second condition (C.9) above have probability at most -Si.eebbatts log N)
even after conditioning arbitrary value for Ps,bxo+s'
Proof. The claim follows by an elementary Chernoff estimate for hypergeometric variables, which hold just as for binomial variables by Lemma 1. Indeed the assumption implies that some adjacent difference 1is -i has size (11 /log N). (Note for applying the Chernoff bound that L is a constant independent of N, and so - 2 (b.u(bbu+ss)))
We now focus upper-bounding the probability of any good sequence (qr. (qr....,,)) .0) appearing. conditionally on go-
Lemma 4. For any good sequence (gL, -L-1.L-1...... qu) and j 0.
P (pi.beett- Ps.beo-s- ps.ben-)) = (9L, 9LL.9L-1:14 -L-11...., .0)) Pi,brt+s 90
(1- (1))
S exp
- q0+1)2 -(0t))
22go yo)e t=
Proof. It suffices to show that
(- (1 (1-)
Pler = g6+1 qel S exp
240 qo)e bhots-cl9e 9(42)²
This follows by applying Lemma 2 the hypergeometric random variable
Pi.boo -bootj-e Pi,bao 18
bko Uko Rixo 1s Ruxo 15
The fact that
bkotj bkoti-e Q b O(1)
leads to the factor in the denominator of the desired result.
Lemma 5, For fixed problem parameters and N large, any good sequence (qt,..., 40) satisfies
f d.dp (a, 202) / -90)
le 2 90
(logN)
Va(1-g) and that 0 smooth on lg, क (0, 1). By Item 2 above, all qe are within (1) of each other, so the result follows from the inverse function theorem. (Notice that the factor (1 02) changed to (1 202) above.)
Proof. Recall that ('())
Lemma 6. For 1 15 m < L and any good sequence (....... .o)). we have
m- 1
(ge - m dr((,, e2 402) go qu)
Σ
log N
Proof. The result follows from Lemma and Cauchy-Schwand in the form
(ee qe+1) 2
Σ t=
Iue
ue+al)
0=
Lemma 7. For any good sequence (gL...., qu) and j 0, we have
bkotsedF(a, 3)2 go qo)
bbo+s-e(94 clge 90+1)² > O
log² N
28

---

Proof. We break the sum into parts and apply Lemma 6 to each one. We have:
L-1
m1 mn
beots- q(+1)= = bbots-LAH L+1
Σ
(qe - g8+1) )2 +
(bkotj m+1
Σ
(qt - q(+1)
t=
m==
8=0
mg (n, -9u 9u)
bko
(1 402)
(1 m)
log"
m=1
2 (1 0 02)) bko+j d'd 8)2 go 20)
log N
(1 + 0)m
For L. = I(e) ( log(e-1)) sufficiently large,
8
m
2 (1 0)
m
(1+ g)m
(1 + 2)m
(1 Ø)
(1 m)
m=
1- 0
g²
Substituting and recalling that @ < 02 completes the proof.
Combining with Lemma 4 yields the second inequality below (the first is trivial).
Corollary C.4. For any and qo, we have
ppiw (Pe.eo-s-2z Ps.bbo Ds.boots) = (gL, :l-............................. .40)
Pi.boots IP (pi.bnots-o> Pipbnots- .... pesnoots (g). (1.
qu
bk do .3) $ exp ( (-11 (ez)))
2log* N
Lemma 8. Let jo be the largest such that bko+s S N. Then for N sufficiently large.
E
X
Sa.8 vg Ing
1
pnats
<((,,))
Proof. Recall that Ca,g dr(a.9)² and observe that the number of total sequences (gL...., qo) 2
[0, 1]4+1 with bko+j+e9e E Z is most N for each j S jo. Combining Lemma and Corol- lary C.4 and noting that the latter always gives the main contribution, we find for each jo.
E
e
Su. aes
log
1.t
psots
< L+1 exp
bkot1, log" N
((Ca., - 03) - -(1 (1- ( (c.s))
(-2
@abkotts log² N
I exp
so long as @3 is chosen so that @s >> max(e, 22). In the last line we used the fact that bko 2 buo 2 log N to absorb the factor N e glog3/2 for large N. Summing over gives the
29

---

desired result, since for P1 (es)) and N sufficiently large,
03 Ing
e4tm 1 2kn log*
==1
m=1
Ing" N
24m
log
m
log² N
2e log
24
S log N
c(a,, e)/4
We now use Lemma 3 to conclude.
Proof that Algorithm 3 achieves the guarantee of Theorem 3.1. By combining Lemma 8 with the previous Propositions C.2 and C.3, it follows that
E
c
1
1.
Lemma 3 now implies that the total amount of time spent on eventually rejected arms at most ( 2) with probability
(Va.3 eg)(1- etN log? N
On this event, the output arm i satisfies ni+ 2 ęN by definition. Since was not rejected, for be the largest value such bkoth I QN have
2 3 0. Pv big li
The probability for this hold if p. S B most (2((N) Altogether we find that
(Ca.3 e5) e- R2(N)) log" N
Plp. 2 0 cxp
(C.10)
for @ arbitrarily small. This concludes the analysis of Algorithm 3 (since the last error term is negligible).
C.5 Finding Many Good Arms with Fixed Budget
In this final subsection we observe that Algorithm 3 can be modified to output many as log N distinct arms each of which satisfies the same (1) e, 6P- guarantee?, with no degradation in the asymptotic failure probability. With other parameters fixed, we denote the N-sample version of Algorithm by Ay to emphasize the dependence on N. In particular, both equals the number of steps in Ay and appears (via its logarithm) in the description of A 's individual steps.
Let Ñ = N + 1og 1. We consider a modified algorithm Ag which mimicks the behavior of AN with two changes:
1. A is Ñ sammle algorithm.
2. If an arm a; has not yet been rejected after M IN/log" [NV] samples, then À accepts a; and continues to a++1- particular, A may accept several arms instead of just one.
Theorem C.9. With probability 1 1-exp (- (Ca, 25 20--00s-oii0 (1) Ág accepts at least log(N) distinct arms all of which satisfy P; 2 B.
log" N
PI fact log N be replaced by anything (log² N) by precisely defining M and N.
30

---

The change from N to N is almost irrelevant in the actual statement of Theorem C.9 since log( 2 log(N) - ON (1). In particular, AN is N -ssmmll algorithm which outputs at least log( (N) arms with probability 1 exp (co.a Rs (1)18 It is certainly not really necessary use the value log? N
log(NN rather than (N) to describe the individual steps taken by A Ag- However introducing N streamlines the proof below by letting treat Av blackbox.
Proof. To show that all accepted arms a, satisfy p: B with sufficiently high probabilityy, it suffices to consider (C.10) with the final term replaced by e e=Rg(((/log")))))) In particular, observe that the main term does not change, even after multiplying the failure probability by O (log"/2( (the maximum possible number of arms accepted by Ag. Thus we focus showing that A outputs at least (N) arms with high probability.
Consider yet another N-sample algorithm AN which deletes each arm independently with probabil- ity 1/N and follows Ay on the set of non-deleted arms in order of increasing index. (Like AN. Av never accepts arms before time N.) We simulate AN and AN on the same reward sequences, i.e. we couple them that the f-th sample of arm a; always gives the same result for each it, We claim that in this coupling, conditioned on Ag failing accept log(N) arms within the first N samples, AN has probability (2 log to fail (i.e. output 0g with p; < () when run for N samples.
First let us assume the claim and deduce Theorem C.9. Denote by p(N) the probability for AN to fail. Note that AN has the same failure probability p(N), having in fact the same behavior as AN in distribution (as the set of deleted arms is independent of everything else). Moreover let ç (NN k) denote the probability that Ay fails accept at least le arms. The claim above implies that
p(N, log N)
= O N). p((N,1)
s CoN(N/ N)
p(N,
(Ca,8
05 ON (1))
S exp
log" N
It remains to prove the above claim. Let us say the infinite i.i.d. reward sequence (Fin)nz1 of arm a, is acceptable if Av would not reject a, within M samples, i.e. Ay will either accept a; out of samples before doing so. We take the point of view that each a, is either acceptable or not (by randomly fixing the reward sequences the start). Then with probability D(N-log(N)) the first log(N) acceptable arms are skipped by A, and the first Ñ unacceptable arms are not skipped. On this event, the first N - M 2 N samples obtained by AN, i.e. all N of its samples, are drawn from unacceptable arms. On this event, AN fails with constant probability, which establishes the claim and completes the proof.
31


Reviews:
[{"review_id": "3Imu3wda49", "reviewer": "Reviewer_xhAx", "summary": "**[Setting]** This paper studies best arm identification among countably infinite arms in both fixed confidence and fixed budget setting. The mean rewards for these arms are drawn iid from a distribution $\\mu$. Let $\\alpha$ be the $1 - \\eta$ percentile of $\\mu$. The goal is to find an arm with mean reward at least $\\alpha - \\epsilon$. Note that the algorithm knows $\\eta$ and not $\\alpha$.\n\n**[Algorithm - fixed confidence]** - In the fixed confidence setting, the authors propose an algorithm that identifies the required arm with high probability using $O(\\log(1/\\delta) \\log (1/\\eta) / \\eta \\epsilon^2)$ samples in expectation. This algorithm first tries to estimate $\\alpha$ by pulling $O(\\log (1/\\delta) / \\eta)$ arms $O(\\log(1/\\eta) / \\epsilon^2)$ times, and then uses the estimated value to find the target arm by pulling $O(1)$ arms (in expectation) $O(\\log (1 / \\eta \\delta) / \\epsilon^2)$ times.\n\n**[Guarantee - fixed confidence]** - The bound matches matches a known lower bound up to $\\log (1 / \\eta)$ factor. This is an improvement over previous works that include a $(\\log (1 / \\delta))^2$ term.\n\n**[Algorithm - fixed budget]** - The authors propose an algorithm that goes though arms in a sequence. For each arm $i$, samples are collected in batches until this arm is discarded because its mean falls ``reasonably'' below $\\alpha$. The threshold for discarding an arm keeps decreasing across batches, but always stays above $\\alpha - \\epsilon$. This ensures that arms with mean < $\\alpha - \\epsilon$ are discarded early on using few samples, but arms with mean > $\\alpha - \\epsilon$ have to increasingly pass a harder test to be retained. The last un-discarded arm is returned as the best arm.\n\n**[Guarantee - fixed confidence]** - The authors focus on the case where $\\delta \\rightarrow 0$ and derive matching lower and upper bounds showing that an optimal algorithm in the fixed budget setting needs $O(\\log (1/\\delta) (\\log \\log(1 / \\delta))^2 / c)$ samples, where $c$ is a problem dependent parameter.", "questions": "Please address points 1 and 2 under quality and points 1 and 4 under clarity in the weakness section.", "limitations": "I believe that point 2 under clarity in the weaknesses section should be addressed.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "**Originality** - The paper closes a gap (w.r.t $\\delta$) between the upper and lower bounds in the fixed confidence setting. This requires new ideas in the algorithm. It also proposes the first asymptotically optimal algorithm in the fixed budget setting.\n\n**Quality** - I must admit that I did not fully understand the results in the fixed budget setting. For the fixed confidence setting, the ideas appear technically sound to me, though I have a few questions listed later. This is a complete study in my opinion where the derived bounds are tight, and the claims are well supported with theoretical evidence.\n\n**Clarity** - The paper is positioned well with respect to other works. Most parts are very well written and organised (barring a few basic questions listed later).\n\n**Significance** - Given that the paper closes the gap between upper and lower bounds in both fixed confidence and fixed budget setting, it would be a valuable addition to the literature. It also provides a good starting point for further explorations like getting high probability bounds on the sample complexity in the fixed confidence setting.\n", "weaknesses": "**Quality** - \n\n1. As the authors have pointed out in L212-215, the derived bounds do not depend on $\\eta$ in the fixed confidence setting. However, the intuition for why this is the case is missing from the paper.\n\n2. L206 says that the case of known $\\alpha$ is the easier case. Remark 3.1 gives conditions under which one would not need $\\alpha$ in advance. However, it appears that Algorithm 3 always requires $\\alpha$ as input (see L6 for example). This must be clarified. \n\n\n**Clarity** - The paper can be made more accessible in many places:\n\n1. It is perhaps just me, but the sample complexity bounds for the fixed budget setting are a bit confusing. Isn't it true that people usually fix a budget $N$ and try to minimise the probability of error with this budget? What does the case $\\delta \\rightarrow 0$ mean then? Why is there a bound on $N$ again (which is supposed to be fixed)? \n\n2. The idea of batches in Remark 2.1 can be explained more clearly. In the worst case, Algorithm 2 does sample $O(\\log(1/\\delta))$ arms. Using batches probably ensures that only $O(1)$ arms are queried in expectation.\n\n3. The notation is confusing at several places. For example, $\\eta_1$ in L167 is undefined. L2 in Algorithm 1 uses $\\eta$ in both numerator and denominator. $\\eta_2$ in L184 should probably be explicitly defined.\n\n4. Should there be an $\\eta$ in the denominator inside the $\\log$ in L185? This will make $b_{2, i}\n = C \\log(1/\\delta) / \\eta^2$, which is different from the range of the for loop in Algorithm 2.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and insightful reviews. Here is our detailed response.\n\nQuality Questions:\n1. L212-215 are comments for the fixed budget setting (as opposed to the fixed confidence setting). Thank you for your suggestion! We have added some intuition in the paper following those comments.\nThe idea is that the main source of failure probability for the fixed budget setting is through a mechanism that does not really depend on $\\eta$. To succeed in pure exploration, one should have sampled the eventually outputted arm at least $\\Omega(\\log 1/\\delta)$ times. The main obstacle to success in the fixed budget case is that any arm we obtain many samples of might gradually degrade over time. The probability of this degradation is essentially given by small probabilities coming from Chernoff-bound type events, which dominate the prior probability that the arm is in a top quantile.\n\n2. Thank you for the question! We have added the parameter input line to Algorithm 3, and added clarification in the text at the start of Section 3.2. In particular we referenced Appendix C.1 where algorithms to compute $\\alpha$ are given in the three scenarios of Remark 3.1. These were left to the Appendix due to space constraints.\n\nClarity Questions:\n1. Thank you for the question! These two approaches of describing sample complexity bounds are just two ways to state the same thing. In our approach, we fix all the other parameters, so for each $N$ there is an optimal $\\delta=\\delta_N$ that is achievable. To describe the rate at which $\\delta_N$ tends to 0, it is equivalent to go the other direction: sending $\\delta$ to 0 and asking how large $N=N(\\delta)$ needs to be so the failure probability is at most $\\delta$. We have added some more explanation to this effect in Section 1.1 Problem Formulation:\nIndeed once $\\eta$ and $\\varepsilon$ are fixed, the question of minimizing the sample complexity $N=N(\\delta)$ (given a target confidence $\\delta$) is equivalent to minimizing the failure probability $\\delta=\\delta(N)$ (given a sample complexity $N$). These viewpoints are equivalent in both settings we study, and we switch between them at times.\n\n2. Thank you for your suggestion! We have added some clarifications to this remark, which we hope explains things more thoroughly. You are right that the intent was that O(1) batches are sampled in expectation.\nOur fixed confidence algorithm, given by combining Alg. 1 with Alg. 2 as above, requires only O(1) batches in expectation. Here a batched algorithm operates in a small number of batched phases. At the start of each phase, such an algorithm chooses b arms to sample exactly s times each, where b,s can both depend adaptively on the previous feedback, but cannot be changed during the current phase.\n\n\n3. Thank you for pointing these out! We have fixed these typos from a previous version. Basically, $\\eta_1$ and $\\eta_2$ were both within a factor 2 of $\\eta$, so they are essentially all about the same.\n\n4. Thank you! We have corrected the typo.\n"}, {"review_id": "FbE3dNXNQf", "reviewer": "Reviewer_o2AR", "summary": "This paper studies pure exploration problem in bandits with infinite arms, where the mean reward of each arm is i.i.d. according to some unknown distribution. In fixed-confidence setting, this paper proposes an algorithm that nearly matches the optimal sample complexity. In fixed-budget setting, this paper proposes an asymptotic lower bound and proposes an algorithm that nearly matches it.", "questions": "- Is that possible to build some connection with the instance-dependent fixed-budget complexity in pure exploration with finite arms?\n- Since $\\eta$ does not appear in the error probability of fixed-budget setting, can we just take $\\eta=0$?\n- Is that possible to intuitively explain why Algorithm 3 will be optimal?\n- Why does the ceiling function appear in $b_{k_0+j}$ but not in $b_k$?\n- Why will an adversary with smaller strength make the true failure probability of $\\mathcal{A}$ larger?", "limitations": "The limitations (in particular, the requirement of the knowledge of $\\alpha$) has been adequately addressed.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The fixed-confidence algorithm is nearly optimal.\n- The lower bound proof for fixed-budget setting contains novel construction of adversaries.\n- The fixed-budget algorithm is asymptotically optimal and the limitation on the knowledge of $\\alpha$ is appropriately addressed.", "weaknesses": "Is that possible to empirically evaluate the proposed algorithms, especially the fixed-budget algorithm, and compare them with previous work?\n\n### Suggestions on Writing\n- line 213, \"known\" -> \"unknown\".\n- It may be better to mention the low probability of faliure when discussing Algorithm 2.\n- It may be better to replace $\\mathbb{P}$ in equations (3.1) and (3.2) by $\\mathbb{P}_{\\mu_N}$.\n- It seems $\\hat{p}_{i, b_k}$ has a slight abuse of notation compared to the definition in Section 1.2 since $b_k$ in Algorithm 3 is not the time index from $t=1$. Maybe some clarification can be added here.\n- What does $\\partial v$ mean in the definition 3.2??", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and insightful reviews. Here is our detailed response.\n\nSuggestions:\n1. For this suggestion, we actually intended to write “known” because we are discussing the lower bound. This “known” makes pure exploration easier, hence the lower bound is stronger. We added a brief clarification of this in the paper.\n\n2. Thank you for the suggestion! We have adopted your suggestion.\n\n3. Thank you for the suggestion! We have adopted your suggestion\n\n4. Thanks, we have updated the notation.\n\n5. Thank you! We apologize for the typo (it was supposed to be $\\mathbb A$) and have fixed it.\n\n\nQuestions:\n\n1. This is an interesting question and they certainly appear similar. We believe the behavior is somewhat different at a fine-grained level. This can be seen from https://arxiv.org/abs/2303.09468, which shows that there is no complexity measure characterizing optimal pure exploration with finitely many arms. This means that the instance-optimal sample complexities for known arm distributions cannot be simultaneously achieved (with sharp constant) for an unknown arm distribution. On the other hand, our results for the fixed budget setting obtain a sharp constant, and the algorithm is agnostic to the reservoir distribution as long as N is sufficiently large. The difference seems to stem from the fact that in an infinite arm setting, one might get unlucky and end up sampling mostly bad arms. This turns out to be a steeper barrier to success than learning the target quantile (see Appendix C.1). Meanwhile for K arms, estimating the target quantile is of the same “order” of difficulty as solving the problem so they cannot be disentangled.\n\n2. The error probability holds for any fixed $\\eta>0$, but $\\delta$ must be small enough (or N large enough) depending on $\\eta$. If $\\eta$ were to shrink rapidly with $\\delta$, then the results might be different.\n\n3. Thank you for the question, and here is some intuition. The algorithm is inspired by the lower bound proof, where an adversary forces each arm to degrade in performance as it is sampled more. This “degradation schedule” is identical to the “rejection threshold schedule” in the algorithm. In the lower bound, there is clearer intuition: the adversary wants to use a constant rate of probability distortion “budget” per sample.\n\n4. Thank you! We have corrected the typo.\n\n5. The important thing is to keep in mind that an adversary is nothing more than a proof technique. A weak adversary distorts the distribution of the algorithm’s trajectory by a small amount. So if a weak adversary is able to force failure with probability 1, it is natural that this implies a large value of the true failure probability."}, {"review_id": "Y67J2kjLAZ", "reviewer": "Reviewer_326s", "summary": "This paper considers pure exploration problem in multi-armed bandits with infinite number of arms. Its goal is to return an arm with sufficiently high expected reward (within the top $\\eta$ region) with high probability (at least $1-\\delta$). A naive method could lead to a complexity upper bound of $O({\\log(1/\\eta\\delta)\\log(1/\\delta) \\over \\eta\\epsilon^2})$, where $\\epsilon$ is the error tolerance rate. The authors make some improvement, design a new learning algorithm, and show that it achieves a complexity upper bound of $O({\\log(1/\\eta)\\log(1/\\delta) \\over \\eta\\epsilon^2})$. They also consider the fixed budget case, and show that their proposed algorithm can achieve a failure probability approximately $\\exp(-N/\\log^2 N)$, where $N$ is the fixed budget. ", "questions": "Please see the above \"Weaknesses\"", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The model setting is well-motivated, and reducing one $\\log(1/\\delta)$ factor seems to be an important step in this kind of problems. \n", "weaknesses": "Here are some of my questions.\n\n1) An $(\\eta, \\epsilon, \\delta)$-PAC is defined as Eq. (1.1), i.e., $\\Pr[p_{i^*} \\ge G^{-1}(1-\\eta) -\\epsilon] \\ge 1 - \\delta$. I can understand that this is a traditional definition for $\\epsilon$-PAC in pure exploration problems, but I am still wondering what if we change this definition to be $\\Pr[p_{i^*} \\ge G^{-1}(1-\\eta - \\epsilon)] \\ge 1 - \\delta$. How would this change influence all the complexity bounds?\n\n2) In Theorem 1.2, does the $\\alpha \\ge \\eta$ mean $\\alpha \\ge G^{-1}(1-\\eta) $? Is the $c$ in equation before Eq. (1.2) the same as the $c_{\\alpha, \\beta}$ in Eq. (1.2)?\n\n3) I do not really understand why $\\eta$ does not appear (in the statement of line 75). In my opinion, a natural lower bound should be $(1-\\eta)^N$, since this is the probability that you try $N$ arms and no one satisfy the constraint that $p_i \\ge G^{-1}(1-\\eta)$. Is this hidden by the factor $c$ (or $c_{\\alpha, \\beta}$)?\n\n4) In Algorithm 1 line 2, why we are writing an $\\eta$ factor on both the numerator and the denominator?\n\n5) In Algorithm 2, each arm should be pulled for $O({\\log(1/\\eta\\delta) \\over \\epsilon^2})$ times, and try $O({\\log(1/\\delta) \\over \\eta})$ arms. This leads to a straightforward $O({\\log(1/\\eta\\delta)\\log(1/\\delta) \\over \\eta\\epsilon^2})$ complexity bound. I guess the reason that the complexity bound in Theorem 2.1 is $O({\\log(1/\\eta)\\log(1/\\delta) \\over \\eta\\epsilon^2})$ is because the expected number of tried arms (and then find one good arm to output) is about $O({1 \\over \\eta})$, but this seems not leading to the complexity bound in Theorem 2.1. Since  no proof sketch about this theorem is given in the main text, I think at least you need to explain the high-level ideas for this proof clear to make sure that the readers can understand why your theorem is true. Besides, is your complexity bound only an expected one or a high-probability one?\n\n6) In line 281, do you mean $\\log M \\le N(1-1/\\log N)$ instead of $M \\le N(1-1/\\log N)$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and insightful reviews. Here is our detailed response.\n\nWe would like to emphasize that we not only give an algorithm achieving failure probability $\\exp(-N/\\log^2 N)$, but we also show this is unimprovable in a natural asymptotic parameter regime. This lower bound is what we consider the most surprising finding of our work and seems to be very unusual; one typically expects the sample complexity to be proportional to $\\log(1/\\delta)$. We are not aware of another learning problem exhibiting the rate $\\log(1/\\delta)\\big(\\log\\log 1/\\delta\\big)^2$ we found.\n\n1. This is a good question, and we have added clarification slightly above Theorem 1.1. In short, the modified definition also leads to an unsolvable problem. Imagine 90% of arms have mean 0.5, while 10% of arms have mean $0.5-e^{-N^4}$. Then $G^{-1}(1-\\eta-\\epsilon) = 0.5$ so long as $\\eta+\\epsilon < 0.9$. So if there is only quantile slack, one needs to distinguish between the two means to solve the problem, which is information theoretically impossible. \n \n2. Thank you for pointing these out. We apologize for the typos and have corrected them. We meant to write $\\alpha ≤ G^{-1}(1-\\eta)$. The point is that we are given a target mean reward $\\alpha$, and are promised that at least $\\eta$ fraction of arms have mean reward $\\alpha$ or better.  The c should also be $c_{\\alpha,\\beta}$ as you point out.\nThe reason for $\\eta$ to be irrelevant for the fixed budget setting is that we are studying the limit of small $\\delta$, i.e. very high confidence. For any fixed $\\eta$, the bound you suggest is indeed valid and shows the failure probability is at least $\\exp(-\\eta N)$. (Corresponding to sample complexity at least $\\log(1/\\delta)/\\eta)$. \n\n3. The surprising thing is that the correct failure probability is of larger order in N, i.e. the required sample complexity is of larger order in $\\delta$. So for any fixed $(\\alpha,\\beta,\\eta)$, as $\\delta\\to 0$ the relevant constant factor $c_{\\alpha,\\beta}$ does not depend on $\\eta$. We added some further explanation of this point just above Theorem 3.2 and included some intuition in the 1-page pdf response. It is certainly interesting to get more precise bounds that allow $\\eta,\\varepsilon,\\delta$ to tend to zero simultaneously; in such cases, our lower bound $\\log(1/\\delta)(\\log\\log 1/\\delta)^2$ would always be valid.\n\n4. Thank you! We have corrected the typo.\n\n5. Thank you for the great suggestion. We have added some explanation in the paper. You are exactly correct that the expected number of arms tried in Algorithm 2 is $O(1/\\eta)$. The sample complexity actually ends up being dominated by Algorithm 1, which collects $\\log(1/\\eta)$ samples each from $\\log(1/\\delta)$ arms.\n\n6. Thank you! We have corrected the typo.\n\n\n\n"}, {"review_id": "UzqtTHlCGb", "reviewer": "Reviewer_ccFe", "summary": "This paper addresses a problem of pure exploration in the infinite-armed bandit setting : in this problem, each arm has mean reward $p_i$ drawn i.i.d. from a distribution with quantile function $G^{-1}$, and the aim is to output an arm $a_{i*}$ after sampling $N$ times an action, such that $\\mathbb{P}\\left(p_{i^*} \\geq G^{-1}(1 - \\eta) - \\epsilon\\right)\\geq 1 - \\delta$ for some given $\\eta$, $\\epsilon$, and $\\delta$. The authors first propose an algorithm for the setting where $G^{-1}(1 - \\eta)$ is unknown that is almost optimal in terms of expected sample complexity $\\mathbb{E}[N]$, and show that is satisfies the $(\\eta, \\epsilon, \\delta)$-PAC constraint and derive an upper bound on the sample complexity. In a second part of the article, they consider the fixed budget setting when $G^{-1}(1 - \\eta)$ is unknown, and propose an asymptotically optimal algorithm (i.e. an algorithm with asymptotically optimal failure rate). They derive upper bound on its failure rate, and obtain a lower bound for the failure rate of any algorithm.", "questions": "Please define explicitly the constant to use in the algorithms so that your claims hold.\n\nPlease postpone the proof of Lemma 4 to the Appendix and develop your arguments further.\n\nFor the sake of completeness, please recall the results that you are using (Chernoff bounds (A.1) and (A.2), Thm 4.5 in [MU17], Thm 1 in [GM14], etc).\n\nPlease refrain from using symbols as $\\Omega$ in the proofs, and use instead explicit numerical constants, so that the validity of your arguments is easier to assess.\n\nThere are somme remaining typos :\n- Theorem 1.2: the constant in the definition of $N$ should be $c_{\\alpha, \\beta}$\n- Algorithms 1, 2: $C$ is not defined.\n- Algorithm 3: $\\alpha$, $\\rho$, and maybe somme other parameters should be considered as input to the algorithm\n- line 167 : what is $\\eta_1$? Is it $\\eta$?\n- Algorithm 1 : why not define $K$ as $K = C\\log(1/\\delta)/\\eta$?\n- line 199: do you mean Theorem 2.1?\n- Appendix, line 474 : there is a \"with\" missing\n- Appendix, line 490 : \"qualitative\"\n- Appendix, Lemma 4: there are extra parentheses.\n- Appendix, line 621 : please define the event $E$\n\nI had trouble understanding the sentence in line 197 (I think the word therefore is misleading); could you please rephrase it?\n\nThe meaning of the number of \"batches\" is not very easy to understand. Could you please rephrase the corresponding discussions?\n\nIt would be nice to include an outline and a conclusion in this article.\n\nTheorem 2.1 and Algorithm 1 overlap, which is annoying. Please correct the layout.\n\nYou introduce constants $\\rho_1, \\rho_2$ which do not appear in Algorithm 3. Please correct that.", "limitations": "The authors have not discussed limitations of their results.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "Originality : The author consider in this paper a vary natural problem.\n\nClarity : This paper is very well written and easy to follow. The literature review is thorough and well presented, the algorithms are rather well explained. The comments on the results are interesting, and the authors manage to highlight the different aspects of the problem.\n\nQuality : This paper provides interesting theoretical results.\n\nSignificance : This article makes significant contributions to a natural problem. They improve on existing results, and close open questions in both settings by characterizing optimal sample complexity and optimal failure rate in the fixed confidence and fixed budget setting.", "weaknesses": "Results are sometimes lacking in clarity, and sometimes even in rigor. Bellow are some examples :\n\nThe algorithms make use of some undefined constant $C$ (the same holds for the constants $\\rho, \\rho_1, \\rho_2$). While I agree that the results are true for some specific constant, they are not true in general. The authors should define these constants more carefully, and propagate the numerical constants appearing in their proof instead of using symbols $\\Omega$. The authors make heavy use of these symbols  in their proof, making them harder to read, and less rigourous.\n\nI find the \"proof\" of Lemma 4 not convincing.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and insightful reviews. Here is our detailed response.\n\nThank you for all of the helpful suggestions. We have taken them carefully into account while revising the paper. \n\nTypos:\n\n1. Thank you! We have corrected the typo.\n\n2. We apologize. C is a universal constant (basically the same as writing O(), but using C emphasizes that there is no dependence on any parameters at all). We have added some explanation in the early parts of the paper.\n\n3. Thank you for the suggestion! We have added the parameter input line in Alg 3.\n\n4. Thank you! We have corrected the typo.\n\n5. We have adopted your suggestion. Thank you!\n\n6. Thank you! We have corrected the typo.\n\n7. Thank you! We have added the “with”.\n\n8. Thank you! We have corrected the typo.\n\n9. The extra parentheses were supposed to show dependence on other parameters similarly to the rest of Lemma 4. We fixed it, thank you for catching this typo.\n\n10. Thank you for the suggestion. We have written out the definition of the event E. We also changed $\\delta$ to $\\Delta_N$ in Equation (B.14) just above.\n\nOther comments:\n1. Thank you for your comment. We have rewritten the proof of Lemma 4 and included it in the 1 page pdf. Previously our point of view in the proof was “fully Bayesian” for each fixed algorithm. The proof is short and valid once understood properly, but requires some precision about which probability spaces are being used. We didn’t specify, which probably caused the confusion, and feel it would be cumbersome to do so. We now explain it by defining a value function $E_t$ and using the dynamic programming principle instead of fixing a specific algorithm. We hope it is now clearer and would be happy to provide further explanations or changes.\n\n2. Line 197: we updated the paragraph. The meaning is just that the upper and lower bounds $U,L$ always satisfy $U\\leq O(L\\log L)$, i.e. the bounds can be said to nearly match.\n\n3. Thank you for the question! We have rephrased the remark about batches, and included it in the 1-page pdf.\n\n4. Thanks! Theorem 2.1 and Algorithm 1 no longer overlap. We also made Algorithms 1,2 adjacent to mitigate these annoyances.\n\n5. We added a conclusion, thank you for the suggestion. \n\n6. $\\varrho_1$ appears in the definition of $b_0$. We updated Algorithm 3 to reference these parameters at the start.\n\n"}]

Author rebuttal:
We thank the reviewers for insightful comments and suggestions. We have adopted most of your suggestions and added clarifications in the paper. 

Please see the one-page pdf where we highlight some of the more significant modifications so far.

Meta-review: The paper studies the variant of pure exploration for multi-armed bandit --- quantile pure exploration with infinitely many arms. It shows tight results on the fixed-confidence and the fixed-budget settings. All reviewers support the paper and provide constructive comments. The authors' rebuttal addressed many of the comments. I recommend the paper to be accepted by NeurIPS'2023, and wish that the authors could incorporate all the comments from the reviewers into the final version of the paper.
Decision: Accept (poster)