On the Optimal Sample Complexity for Best Arm Identification

arXiv:1511.03774v3 [cs.LG] 23 Aug 2016

Lijie Chen
Jian Li
Institute for Interdisciplinary Information Sciences (IIIS), Tsinghua University
Abstract
We study the best arm identification (Best-1-Arm) problem, which is defined as follows.
We are given n stochastic bandit arms. The ith arm has a reward distribution Di with an
unknown mean µi . Upon each play of the ith arm, we can get a reward, sampled i.i.d. from
Di . We would like to identify the arm with the largest mean with probability at least 1 − δ,
using as few samples as possible. We provide a nontrivial algorithm for Best-1-Arm, which
improves upon several prior upper bounds on the same problem. We also study an important
special case where there are only two arms, which we call the Sign-ξ problem. We provide a
new lower bound of Sign-ξ, simplifying and significantly extending a classical result by Farrell
in 1964, with a completely new proof. Using the new lower bound for Sign-ξ, we obtain the
first lower bound for Best-1-Arm that goes beyond the classic Mannor-Tsitsiklis lower bound,
by an interesting reduction from Sign-ξ to Best-1-Arm. We propose an interesting conjecture
concerning the optimal sample complexity of Best-1-Arm from the perspective of instance-wise
optimality.

1

Introduction

The stochastic multi-armed bandit is a paradigmatic model for capturing the exploration-exploitation
tradeoff in many decision-making problems in stochastic environments. While the most studied
goal is to maximize the cumulative rewards (or minimize the cumulative regret) obtained by the
forecaster (see e.g., [8, 5]), the pure exploration multi-armed bandit problems, in which the exploration phase and exploitation phase are separate, have also attracted significant attentions, due
to their applications in several domains such as medical trials [29, 2, 10], communication network
[2], crowdsourcing [30, 7]. In a pure exploration problem, the forecaster first performs a pureexploration phase, by (adaptively) drawing samples from the stochastic arms, to infer the optimal
(or near optimal) solution, then keeps exploiting this solution. In this paper, we study the best
arm identification (Best-1-Arm) problem, which is the most basic pure exploration problem in
stochastic multi-armed bandits.
Definition 1.1. Best-1-Arm: We are given n arms A1 , . . . , An . The ith arm Ai has a reward
distribution Di with an unknown mean µi ∈ [0, 1]. We assume that all reward distributions have
1-sub-Gaussian tails (see Definition A.1), which is a standard assumption in the stochastic multiarmed bandit literature. Upon each play of Ai , we can get a reward value sampled i.i.d. from Di .
Our goal is to identify the arm with largest mean using as few samples as possible. We assume
here that the largest mean is strictly larger than the second largest (i.e., µ[1] > µ[2] ) to ensure the
uniqueness of the solution, where µ[i] denotes the ith largest mean.
We also study the following sequential testing problem, named Sign-ξ, which is important for
understanding Best-1-Arm.
1

Definition 1.2. Sign-ξ: ξ is a fixed constant. We are given a single arm with unknown mean
µ 6= ξ. The goal is to decide whether µ > ξ or µ < ξ. Here, the gap of the problem is define to be
∆ = |µ − ξ|. Again, we assume that the distribution of the arm is 1-sub-Gaussian.
In fact, Sign-ξ can be viewed as a special case of Best-1-Arm where there are only two arms
and we know the mean of one arm. Hence, a thorough understanding of the sample complexity of
Sign-ξ is very useful for deriving tight sample complexity bounds for Best-1-Arm.
Definition 1.3. For a fixed value δ ∈ (0, 1), we say that an algorithm A for Best-1-Arm (or
Sign-ξ) is δ-correct, if given any Best-1-Arm(or Sign-ξ) instance, A returns the correct answer
with probability at least 1 − δ.
We say that an algorithm A for Best-1-Arm is an (ε, δ)-PAC algorithm, if given any Best-1Arm instance and any confidence level δ > 0, A returns an ε-optimal arm with probability at least
1 − δ. Here we say an arm Ai is ε-optimal if µ[1] − µi ≤ ε.
The studies of both problems have a long history dating back to 1950s [3, 28, 15]. We first
discuss the Sign-ξ problem. It is well known that for any δ-correct algorithm (for constant δ) A
that can distinguish two Gaussian arms with means ξ + ∆ and ξ − ∆ (the values of ξ and ∆ are
known beforehand), the expected number of samples required by A is Ω(∆−2 ), which is optimal
(e.g., [11]). This can be seen as a lower bound for Sign-ξ as well. However, a tighter lower bound
of Sign-ξ was in fact provided by Farrell in 1964 [15]. He showed that for any δ-correct A for
Sign-ξ (where the reward distribution is in the exponential family), it holds that
lim sup
∆→0

TA [∆]
−2
∆ ln ln ∆−1

> 0,

(1)

where TA [∆] is the expected number of samples taken by A on an instance with gap ∆. Farrell’s result crucially relies on the Law of Iterated Logarithm (LIL), which roughly states that
√
P
lim supt ti=1 Xi / 2t log log t = 1 almost surely where Xi ∼ N (0, 1) for all i. Comparing with the

Ω(∆−2 ) lower bound, the extra ln ln ∆−1 factor is caused by the fact that we do not known the gap
−1
∆ beforehand. The above result implies that ∆−2
[2] ln ln ∆[2] is also a lower bound for Best-1-Arm
(for two arms).
Bechhofer [3] formulated the Best-1-Arm problem for Gaussians in 1954. The early advances
are summarized in the monograph [4]. The last decade has witnessed a resurgence of interest in the
Best-1-Arm problem and its optimal sample complexity
P [12, 16, 23, 19]. [27] showed that for any
n
−2
−1 samples in expectation for
δ-correct algorithm for Best-1-Arm, it requires Ω
i=2 ∆[i] ln δ
any instance. We note that the Mannor-Tsitsiklis lower bound is an instance-wise lower bound, i.e.,
any Best-1-Arm
the stated number of samples. The current best known bound
 instance requires 
P
n
−1
−2
−1
, due to Karnin et al. [24]. Jamieson et al. [20] obtained
ln ln ∆[i] + ln δ
is O
i=2 ∆[i]
a UCB-type algorithm (called lil’UCB), which achieves the same sample complexity and is also
efficient in practice. We refer the above bound as the KKS bound. See Table 1 for more previous
upper bounds.
−1
Given Farrell’s ∆−2
[2] ln ln ∆[2] lower bound, it is very attempting to believe that the KKS upper
bound is optimal, (which matches the lower bound for two arms). Both [20] and [21] explicitly
referred the KKS bound as “optimal”, and [20] stated that “The procedure cannot be improved in
the sense that the number of samples required to identify the best arm is within a constant factor of
2

Source
Even-Dar et al. [12]
Gabillon et al. [16]
Jamieson et al. [19]
kalyanakrishnan et al. [23]
Jamieson et al. [19]
Karnin et al.[24], Jamieson et al.[20]
This paper (Thm 2.5)
This paper (clustered instances) Thm B.22

Sample Complexity


Pn
−2
ln δ −1 + ln n + ln ∆−1
i=2 ∆[i]
[i]


Pn
Pn
−2
−2
−1
∆
∆
ln
δ
+
ln
i=2 [i]
i=2
[i]



Pn
Pn
−2
−2
−1
ln δ + ln ln
i=2 ∆[i]
j=2 ∆[j]


Pn
Pn
−2
ln δ −1 + ln i=2 ∆−2
i=2 ∆[i]
[i]


Pn
Pn
−2
−1
ln δ −1 · ln ln δ −1 · i=2 ∆−2
+
∆
ln
∆
[i]
[i]

 i=2 [i]
Pn
−2
−1
−1
∆
ln
δ
+
ln
ln
∆
i=2 [i]
[i]


Pn
−1
−1
−2
−1
ln
δ
+
ln
ln
min(n,
∆
)
+ ∆−2
∆
i=2 [i]
[i]
[2] ln ln ∆[2]
Pn
−2
−1
−1
+ ∆−2
i=2 ∆[i] ln δ
[2] ln ln ∆[2]

Table 1: Sample complexity upper bounds. We omit the big-O notations. The definition of clustered
instances can be found in the supplementary material (Section B.4)
.

a lower bound based on the law of the iterated logarithm (LIL)”. However, as we will demonstrate,
none of the existing lower and upper bounds are optimal and the problem is more complicated
(and rich) than we expected. The KKS bound is tight only for two arms (or O(1) arms) and in the
worst case sense (not instance optimal in the sense of [14, 1]).

1.1

Our Contributions

We need some notations to state our results formally. Let {µ[1] , µ[2] , . . . , µ[n] } be the means of the
n arms, sorted in the nondecreasing order (ties are broken in an arbitrary but consistent manner).
We use A[i] to denote the arm with mean µ[i] . In the Best-1-Arm problem, we define the gap
for the arm A[i] to be ∆[i] = µ[1] − µ[i] , which is an important quantity to measure the sample
complexity. We use A to denote an algorithm and TA (I) to be the expected number of total arm
pulls (i.e., samples) by A on the instance I.
1.1.1

Upper Bounds

First, we consider the upper bounds for the Best-1-Arm problem with n arms. We provide a novel
algorithm which strictly improves the KKS bound, implying that it is not optimal. In particular,
for any δ < 0.1, our algorithm is δ-correct for Best-1-Arm and it needs at most


Xn
Xn
−1
−2
−1
−2
−1
+
ln
ln
∆
O ∆−2
ln
δ
+
∆
)
ln
ln
min(n,
∆
∆
[2]
[2]
[i]
[i]
[i]
i=2

i=2

samples in expectation. We can see that the improvement over KKS bound is mainly due to the
third term. At first glance, the ln ln n factor may seem to be an artifact of either our algorithm or
analysis. However, it turns
to be a fundamental quantity in the Best-1-Arm problem, since
Pn out
−2
we can also prove a Ω( i=2 ∆[i] ln ln n) lower bound (Theorem 3.1). Moreover, the first two terms
in our upper bounds are also necessary (first term due to the lower bound by [15], second term due
to the lower bound by [27]).
Theorem 2.5 has a few interesting consequences we would like to point out. For example, it is
−1
not possible to construct a class of infinite instances that requires Ω(n∆−2
[2] ln ln ∆[2] ) samples unless
−1
= O(ln ln n). This is somewhat surprising: Consider a very basic family of instances in
ln ln ∆[2]

3

this class: there are n− 1 arms with mean 0.5 and 1 arm with mean 0.5 + ∆. The Mannor-Tsitsiklis
lower bound Ω n∆−2 for this instance (even when ∆ is known) is in fact a directed sum-type result:
roughly speaking, in order to solve Best-1-Arm, we essentially need to solve n − 1 independent
copies of Sign-ξ with gap ∆. However, our upper bound in Theorem 2.5 indicates that the role of
∆[2] is different from the others ∆[i] s. Hence, if we want to go beyond Mannor-Tsitsiklis, 1 Best1-Arm can not be thought as n independent copies of Sign-ξ. In fact, from the analysis of the
algorithm, we can see that the first term and the rest come from very different procedures: the first
term is used for “estimating” the gap distribution and the rest for “verifying” and “eliminating”
suboptimal arms.


Pn
−2
−1
−1
ln
δ
+
∆
ln
ln
∆
Our algorithm can achieve an even better upper bound O ∆−2
i=2 [i]
[2]
[2]

for a special but important class of instances, which we call clustered instances. 2 See Section B.4.
Note that this bound is almost instance optimal, since it matches the Mannor-Tsitsiklis instance−1
wise lower bound plus the 2-arm lower bound ∆−2
[2] ln ln ∆[2] . In fact, the aforementioned instances
(n − 1 arms with mean 0.5 and 1 arm with mean 0.5 + ∆) are clustered instances. Even for such
basic instances, a tight bound is not known so far! After a careful examination, we find that all
previous algorithms are suboptimal on the very basic examples, while our algorithm can achieve
the optimal bound O(∆−2 ln ln ∆−1 + n∆−2 ln δ−1 ).
By slightly modifying our algorithm, we can easily obtain an (ε, δ)-PAC algorithm for Best1-Arm, which improves several prior works. See the supplementary material for the detailed
information.
Technical Novelty of Our Algorithm: Now, we provide a high level idea of our algorithm. Our
algorithm is inspired by the elegant ExpGapElim algorithm in [24]. In order to highlight the technical
novelty of our algorithm, we provide here a very brief introduction to the ExpGapElim algorithm
which runs in round. In the rth round of ExpGapElim, we first try to identify an εr -optimal arm
Ar (where εr = O(2−r )), using the classical PAC algorithm in [13]. Then, using the empirical
mean of Ar as a threshold, the algorithm tries to eliminate those arms with smaller means. In fact,
comparing with the previous elimination-based algorithms, such as [12, 13, 6], ExpGapElim seems
to be the most aggressive one, which is the main reason that ExpGapElim improves on the previous
results. However, we show that ExpGapElim may be over-aggressive, and we may benefit from
delaying the elimination for some rounds, if we cannot eliminate a substantial number of arms in
this round. To exploit this fact, we develop a procedure called FractionTest, which, roughly speaking,
can inform us about the gap distribution and decide whether or not we should do elimination in
this round.
1.1.2

Lower Bounds

Lower bound of Sign-ξ: First we briefly discuss our lower bound for the Sign-ξ problem, which
plays a crucial role in the lower bound reduction for Best-1-Arm.
We first emphasize that Farrell’s lower bound (1) is not an instance-wise lower bound.3 In
particular, the lim sup in (1) merely asserts that the existence of infinite number of instances that
require ∆−2 ln ln ∆−2 samples (as ∆ → 0), which is not enough for our purpose (our reduction for
Best-1-Arm requires a stronger quantitative lower bound). Moreover, we note that it is impossible
1

In other words, we want the lower bound to reflect the hardness caused by not knowing ∆i s.
n
We say the instances is clustered if the cardinality of the set {⌊ln ∆−1
[i] ⌋}i=2 is bounded by a constant. See
Theorem B.22 for more details. P
3
To the contrary, the bound i ∆−2
ln δ −1 [27] is an instance-wise lower bound.
[i]
2

4

to obtain an Ω(∆−2 ln ln ∆−2 ) lower bound for every instance, since we can design an algorithm
that uses o(∆−2 ln ln ∆−2 ) samples for infinite number of instances (see the supplementary material
Section G).
Comparing to Farrell’s lower bound, ours is a quantitative one. Let the target lower bound be
F (∆) = c∆−2 ln ln ∆−1 , where c is a small universal constant. For simplicity, assume that all the
reward distributions are Gaussian with σ = 1. Let TA (∆) = max(TA (Aξ+∆ ), TA (Aξ−∆ )), in which
Aξ+∆ and Aξ−∆ denote the arms with means ξ + ∆ and ξ − ∆, respectively. For an algorithm A,
if TA (∆) ≥ F (∆), we say ∆ is a “slow point” (or A is slow at ∆), otherwise, it is a “fast point”. 4
Roughly speaking, our lower bound asserts that for any δ-correct algorithm for Sign-ξ, there must
be slow points in almost all intervals [e−i , e−i+1 ), i ∈ Z+ . The precise statement and the proof can
be found in supplementary material (Theorem D.1 in Section D).
Our proof is very different from, and much simpler than the complicated proof in [15]. Furthermore, we note that [15] assumes the reward distributions are from the exponential family, while our
proof only utilizes the KL divergence between different reward distributions, which is more general
and applies to non-exponential family as well.
Lower bound for Best-1-Arm: Now, we discuss our new lower bound for Best-1-Arm. Note
that our current knowledge
(in particular the lower 
bounds of Farrell and Mannor-Tsitsiklis) does
P
n
−1
−2
−2
−1 + ∆
ln ln ∆[2] algorithm for Best-1-Arm. If such a result
not rule out an O
i=2 ∆[i] ln δ
[2]
exists,
P it is clearly avery satisfying answer. However, we show it is impossible by by presenting an
n
−2
Ω
i=2 ∆[i] ln ln n lower bound.
P
−1
This is the first lower bound that surpasses Ω( ni=2 ∆−2
[i] ln δ ) [27, 25] for general Best-1Arm. The proof of the theorem is also interesting in its own right. We provide a nontrivial reduction
from the Sign-ξ problem to the Best-1-Arm problem, and utilize our previous lower bound for
Sign-ξ to obtain the desired lower bound for Best-1-Arm. More concretely, we construct a class of
instances for Best-1-Arm, and show that if there is an algorithm A that can solve those instances
faster than the target lower bound, we can construct an algorithm B (calling A as a subroutine) to
solve a nontrivial proportion of a class of Sign-ξ instances faster than ∆−2 ln ln ∆−1 time, which
leads to a contradiction to our lower bound on Sign-ξ. Note that the old lower bound in [15] cannot
be used here since it does not preclude the existence of such an algorithm B for Sign-ξ.
On Instance Optimality: Instance optimality ([14, 1]) is arguably the strongest possible notion
of optimality. Loosely speaking, an algorithm A is instance optimal if the running time of A on
instance I is at most O(L(I)), where L(I) is the lower bound required to solve the instance for
any algorithm. We propose an intriguing conjecture concerning the instance optimality of Best-1Arm. The conjecture concerns the sample complexity of every Best-1-Arm instance, and provides
a concrete formula for it. Interestingly, the formula involves an entropy-like term, which we call
gap entropy. The new ln ln n factor appearing in both our new upper and lower bounds is in fact a
tight bound of the gap entropy. The proofs of our new results also provide strong evidence for the
conjecture. The details can be found in the supplementary material.

1.2

Other Related Work

P
−1
Best-1-Arm: Kaufmann et al. [25] provided an Ω( ni=2 ∆−2
[i] ln δ ) lower bound for Best-1Arm, with a better constant factor than in [27]. Garivier and Kaufmann [18] obtained a complete
4
We sometimes mention the sample complexity of an algorithm and its running time interchangeably, since for
all of our algorithms the running time is at most a constant times the number of samples. Hence, sometimes when
we informally speak that an algorithm must be “slow”, which also means it requires many samples.

5

resolution of the asymptotic sample complexity of Best-1-Arm in the regime where δ → 0 (treating
∆i s as fixed). However, our work focus on the regime where all ∆i s, and δ are variables that can
approach to 0. In fact, when we allow ∆i to approach to 0 and maintain δ fixed, their lower bound
is not tight. 5
Sign-ξ and A/B testing: The Sign-ξ problem is closely related to the A/B testing problem in
the literature, in which we have two arms with unknown means and the goal is to decide which
one is larger. It is easy to see that a lower bound for Sign-ξ is also a lower bound for the the A/B
testing problem. Kaufmann et al. [25] studied the optimal sample complexity for the A/B testing
problem. However, their focus is on the limiting behavior of the sample complexity when δ → 0,
while we are interested in the case where the gap ∆ approaches to zero but δ is a constant (in their
case, the ln ln ∆−1 factor is absorbed by the O(ln δ−1 ) factor).
Best-k-Arm: One natural generalization of Best-1-Arm is the Best-k-Arm problem, which
asks for the top-k arms instead of just the top-1. The Best-k-Arm problem has also been studied
extensively for the last few years [22, 16, 17, 23, 6, 26, 30, 25]. Most lower and upper bounds
for Best-k-Arm are variants of those for Best-1-Arm, and the bounds also depend on the gap
parameters. But in this case, the gaps are typically defined to be the distance to µ[k] or µ[k+1] . Chen
et al. [10] and Chen et al. [9] study the combinatorial pure exploration problem, which generalizes
the cardinality constraint in Best-k-Arm to more general combinatorial constraints.
PAC learning: The worst case sample complexity of Best-1-Arm in the PAC setting is also well
studied. There is a matching lower and upper bounds obtained by Ω(n ln δ−1 /ε2 ) in [12, 13, 27].
The worst case sample complexity for Best-k-Arm in the PAC setting has also been well studied
by many authors during the last few years [22, 23, 30, 7].

2

An Improved Upper Bound for Best-1-Arm

In this section, we present our new algorithm, which achieves the improved upper bound in Theorem 2.5. Due to space constraint, all proofs and some details are deferred to the supplementary
material. Our final algorithm builds on several useful components.
1. Uniform Sampling: The first building block is the simple uniform sampling algorithm. Given
two parameters ε, δ and a set of arms S, it takes from each arm a ∈ S 2ε−2 ln(2 · δ−1 ) samples. Let
µ̂[a] be the empirical mean of arm a. We denote the algorithm as UniformSample(S, ε, δ). We have
the following lemma which is a simple consequence of Hoeffding’s inequality.


Lemma 2.1. For each arm a ∈ S, we have that Pr |µ[a] − µ̂[a] | ≥ ε ≤ δ.

2. Median Elimination: We need the median elimination algorithm developed in [13], which is
a classic (ε, δ)-PAC algorithm for Best-1-Arm. The algorithm takes parameters ε, δ > 0 and a
set S of arms, and returns an ε-optimal arm with probability 1 − δ. The algorithm runs in rounds.
In each round, it samples every remaining arm a uniform number of times, and then discard half
of the arms with lowest empirical mean (thus the name median elimination). It outputs the final
arm that survives. We denote the procedure by MedianElim(S, ε, δ). We use this algorithm in a
black-box manner and its performance is summarized in the following lemma.
5
∗
Their lower bound is of the form
· ln δ −1 for instance I (see [18] for the definition of T ∗ ). In fact, we can
P T (I)
−2
see T ∗ (I) is upper bounded by O( n
∆
)
by existing upper bounds. When δ is some constant, by our new lower
i=2
[i]
Pn
−2
−1
bound Theorem 3.1, Ω( i=2 ∆[i] ln δ ) is not tight.

6

Lemma 2.2. Let µ[1] be the maximum mean value. MedianElim(S, ε, δ) returns an ε-optimal
arm (i.e., with mean at least µ[1] − ε) with probability at least 1 − δ, using a budget of at most
O(|S| log(1/δ)/ε2 ) samples.
3. Fraction test: FractionTest is a simple estimation procedure, which can be used to gain some
information about the distribution of the arms. It plays a key role in the final algorithm. The
algorithm takes six parameters (S, cl , cr , δ, t, ε), where S is the set of arms, δ is the confidence level,
cl < cr are real numbers called range parameters, t ∈ (0, 1) is the threshold, and ε is a small
positive constant. Typically, cl and cr are very close. The goal of the algorithm, roughly speaking,
is to distinguish whether there are still many arms in S which have small means (w.r.t. cr ) or the
majority of arms already have large means (w.r.t. cl ).
The algorithm runs in ln(2 · δ−1 )(ε/3)−2 /2 iterations. In each iteration, it samples an arm ai
uniformly from S, and takes O(ln ε−1 (cr −cl )−2 ) independent samples from ai . Then, we maintain a
counter cnt which is initially 0, and counts the fraction of iterations in which the empirical mean of
ai is smaller than (cl + cr )/2. If the fraction is larger than t, the algorithm returns True. Otherwise,
it returns False.
For ease of notation, we define S ≥c := {µ[a] ≥ c | a ∈ S}, i.e., all arms in S with means at least
c. Similarly, we can define S >c , S ≤c and S <c .
Lemma 2.3. Suppose ε < 0.1 and t ∈ (ε, 1 − ε). With probability 1 − δ, the following hold:

• If FractionTest outputs True, then |S >cr | < (1 − t + ε)|S| (or equivalently |S ≤cr | > (t − ε)|S|).
• If FractionTest outputs False, then |S <cl | < (t + ε)|S| (or equivalently |S ≥cl | > (1 − t − ε)|S|).

Moreover, the number of samples taken by the algorithm is O(ln δ−1 ε−2 ∆−2 ln ε−1 ), in which ∆ =
cr − cl . If ε is a fixed constant, then the number of samples is simply O(ln δ−1 ∆−2 ).

4. Eliminating arms: The last ingredient is an elimination procedure, which can be used to
eliminate most arms below a given threshold. The procedure takes four parameters (S, cl , cr , δ) as
input, where S is a set of arms, cl < cr are the range parameters, and δ is the confidence level.
It outputs a subset of S and guarantees that upon termination, most of the remaining arms have
means at least cl with probability 1 − δ.
Now, we describe the procedure Elimination which runs in iterations. It maintains the current set
Sr of arms, which is initially S. In each iteration, it first applies FractionTest(Sr , cl , cm , δr , 0.075, 0.025)
on Sr , where cm = (cr + cr )/2. If FractionTest returns True, which means that there are at least 5%
fraction of arms with means smaller than cm in Sr , we sample all arms in Sr uniformly by calling
UniformSample(Sr , (cr − cm )/2, δr ) where δr = δ/(10 · 2r ), and retain those with empirical means at
least (cm + cr )/2. If FractionTest returns False (meaning that 90% arms have means at least cl ) the
algorithm terminates and returns the remaining arms. The guarantee of Elimination is summarized
in the following lemma.
Lemma 2.4. Suppose δ < 0.1. Let S ′ = Elimination(S, cl , cr , δ). Let A1 be the best arm among S,
with mean µ[A1 ] ≥ cr . Then with probability at least 1 − δ, the following statements hold
1. A1 ∈ S ′

(the best arm survives);

2. |S ′≤cl | < 0.1|S ′ |

(only a small fraction of arms have means less than cl );

3. The number of samples is O(|S| ln δ−1 ∆−2 ), in which ∆ = cr − cl .
7

Our Final Algorithm DistrBasedElim: Now, everything is ready to describe our algorithm
DistrBasedElim for Best-1-Arm. We provide a high level description here. All detailed parameters
can be found in Algorithm 1. The algorithm runs in rounds. It maintains the current set Sr of
arms. Initially, S1 is the set of all arms S. In round r, the algorithm tries to eliminate a set of
suboptimal arms, while makes sure the best arm is not eliminated. First, it applies the MedianElim
procedure to find an εr /4-optimal arm, where εr = 2−r . Suppose it is ar . Then, we take a number
of samples from ar to estimate its mean (denote the empirical mean by µ̂[ar ] ). Unlike previous
algorithms in [12, 24], which eliminates either a fixed fraction of arms or those arms with mean
much less than ar , we use a FractionTest to see whether there are many arms with mean much less
than ar . If it returns True, we apply the Elimination procedure to eliminate those arms (for the
purpose of analysis, we need to use MedianElim again, but with a tighter confidence level, to find
an εr /4-optimal arm br ). If it returns False, the algorithm decides that it is not judicious to do
elimination in this round (since we need to spend a lot of samples, but only discard very few arms,
which is wasteful), and simply sets Sr+1 to be Sr , and then proceeds to the next round.
Algorithm 1: DistrBasedElim(S, δ)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

h←1
S1 ← S
for r = 1 to +∞ do
if |Sr | = 1 then
Return the only arm in Sr
εr ← 2−r
δr ← δ/50r 2
ar ← MedianElim(Sr , εr /4, 0.01).
µ̂[ar ] ← UniformSample({ar }, εr /4, δr )
if FractionTest(Sr , µ̂[ar ] − 1.5εr , µ̂[ar ] − 1.25εr , δr , 0.4, 0.1) then
δh ← δ/50h2
br ← MedianElim(Sr , εr /4, δh )
µ̂[br ] ← UniformSample({br }, εr /4, δh )
Sr+1 ← Elimination(Sr , µ̂[br ] − 0.5εr , µ̂[br ] − 0.25εr , δh )
h←h+1
else
Sr+1 ← Sr

Theorem
δ < 0.1, there is a δ-correct algorithm for Best-1-Arm
which needs at

 2.5. For any P
Pn
n
−1
−2
−2
−1
−2
−1
most O ∆[2] ln ln ∆[2] + i=2 ∆[i] ln δ + i=2 ∆[i] ln ln min(n, ∆[i] ) samples in expectation.

It is not difficult to verify that DistrBasedElim returns the best arm with probability at least
1 − δ. However, the analysis of the running time of our algorithm is much more challenging. The
rough idea is to consider the number of arms in each interval U s = {a | 2−s ≤ ∆[a] < 2−s+1 } and
see how it changes in very round. When we execute Elimination in round r, we can eliminate a
substantial fraction or arms in U 1 , . . . , U r . However, there are still some remaining and we need
to keep track of them over the ensuing rounds. For that purpose, we need to carefully choose a
potential function to amortize the costs over different iterations.


Pn
−2
−1
−1 for
ln
δ
∆
+
ln
ln
∆
Our algorithm can achieve an even better upper bound O ∆−2
i=2 [i]
[2]
[2]
8

clustered instances. Furthermore, by slightly modifying the algorithm, we can obtain an improved
(ε, δ)-PAC algorithm for Best-1-Arm. See the supplementary material.

3

A New Lower Bound for Best-1-Arm

In this section, we provide a sketch proof of the following new lower bound for Best-1-Arm. From
now on, δ is a fixed constant such that 0 < δ < 0.005. Throughout this section, we assume the
distributions of all the arms are Gaussian with variance 1.
Theorem 3.1. There exist constants c, c1 > 0 and N ∈ N such that, for any δ < 0.005 and
anyPδ-correct algorithm A, and any n ≥ N , there existsPan n arms instance I such that TA [I] ≥
n
−1
−2
−2
c1
c · ni=2 ∆−2
i=2 ∆[i] ln ln n.
[i] ln ln n. Furthermore, ∆[2] ln ln ∆[2] < ln n ·
P
The second statement of the theorem says that ni=2 ∆−2
[i] ln ln n dominates the 2-arm lower

−1
bound ∆−2
[2] ln ln ∆[2] (so that the theorem is not vacant). In order to prove Theorem 3.1, we need a
new lower bound for Sign-ξ to serve as the basis for our reduction to Best-1-Arm. Let A′ denote
an algorithm for Sign-ξ, Aµ be an arm with mean µ (i.e., with distribution N (µ, 1)), and we define
TA′ (∆) = max(TA′ (Aξ+∆ ), TA′ (Aξ−∆ )). Then we have the following new lower bound for Sign-ξ.
The proof is deferred to the supplementary material (Section D).

Lemma 3.2. For any δ′ -correct algorithm A′ for Sign-ξ with δ′ ≤ 0.01, there exist constants
N0 ∈ N and c1 > 0 such that for all N ≥ N0 , |{TA′ (∆) < c1 · ∆−2 ln N | ∆ = 2−i , i ∈ [0, N ]}| ≤
0.1(N − 1).
Proof of Theorem 3.1. (sketch) Without loss of generality, we can assume N0 in Lemma 3.2 is an
even integer, and N0 > 10 such that 2 · 4N0 ≥ 43 · 4N0 + N0 + 2. Let N = 2 · 4N0 . For every n ≥ N , we
pick the largest even integer m such that 2 · 4m ≤ n. Consider the following Best-1-Arm instance
Iinit with n arms: (1) There is a single arm P
with mean ξ. (2) For each k ∈ [0, m], there are 4m−k
−k
k
arms with mean ξ − 2 . (3) There are n − m
k=0 4 − 1 arms with mean ξ − 2.
Now we define a class of Best-1-Arm instances {IS } where each S ⊆ {0, 1, . . . , m}. Each IS
is formed as follows: for every k ∈ S, we add one more arm with mean ξ − 2−k to Iinit ; finally
we remove |S| arms with mean ξ − 2 (by our choice of m there are enough such arms to remove).
Obviously, there are still n arms in every instance IS .
For a Best-1-Arm instance I, let n(I) be the number of arms in I, and ∆[i] (I) be the gap ∆[i]
Pn(I)
according to I. We denote H(I) = i=2 ∆[i] (I)−2 . Now we claim that for any δ-correct algorithm
A for Best-1-Arm, there must exist an instance IS such that TAperm (IS ) > c · H(IS ) · ln m =
Ω(H(IS ) ln ln n), for some universal constant c > 0, where Aperm first randomly permutes the arms
and then simulates A.
Suppose for contradiction that there exists a δ-correct A such that TAperm (IS ) ≤ c · H(IS ) · ln m
for all S. Let U = {IS | |S| = m/2}, V = {IS | |S| = m/2 + 1} be two sets of Best-1-Arm
instances. Notice that |U | = |V | = m+1
m/2 (since m is even).
Fix S ∈ U . Consider the problem Sign-ξ, in which the given instance is a single arm A with
unknown mean µ, and we would like to decide whether µ > ξ or µ < ξ. Now, we construct an
algorithm AS for Sign-ξ. First consider the following two algorithms for Sign-ξ, which call Aperm
as a subprocedure. (1) A1S : We first create a Best-1-Arm instance instance Inew by replacing one
arm with mean ξ − 2 in IS with A. Then run Aperm on Inew . We output µ > ξ if Aperm selects A
as the best arm. Otherwise, we output µ < ξ. (2) A2S : We first construct an artificial arm Anew

9

with mean 2ξ − µ from A. 6 Create a Best-1-Arm instance Inew by replacing one arm with mean
ξ − 2 in IS with Anew . Then run Aperm on Inew . We output µ < ξ if Aperm selects Anew as the best
arm. Otherwise, we output µ > ξ. AS simulates A1S and A2S simultaneously: Each time it takes a
sample from the input arm, and feeds it to both A1S and A2S . If A1S (A2S resp.) terminates first, it
returns the output of A1S (A2S resp.). It is not hard to see that AS is 2δ-correct for Sign-ξ.
Now we analyze the expected total number of samples taken by AS on arm A with mean µ and
gap ∆ = |ξ − µ| = 2−k . Suppose k ∈
/ S. A key observation is the following: if µ < ξ, then the
instance constructed in A1S is exactly IS∪{k} ; otherwise µ > ξ, since 2ξ−(ξ+∆) = ξ−∆ = ξ−2−k , the
instance constructed in A2S is exactly IS∪{k} . Hence, TAS (A) ≤ min(TA1 (A), TA2 (A)) ≤ akS∪{k} · 4k ,
S
S
where akS is so defined that akS · 4k is the expected number of samples taken from an arm with gap
2−k by Aperm (IS ).
Moreover, since TAperm (IS ) ≤ c · H(IS ) · ln m for all S, we can show that for any S, there are at
k
most 0.1 fraction of elements in {akS }m
k=0 satisfying aS ≥ c1 · ln m (letting c = c1 /30 will suffice).
k
Intuitively, this implies TAS (A) ≤ c1 4 ln m from for ∆ = 2−k , k ∈ [0, m]. Indeed, by a careful
counting argument, we can show that there exists an S ∈ U such that {TAS (∆) < c1 · ∆−2 ln m |
∆ = 2−i , i ∈ [0, m]} ≥ 0.4(m + 1), which is a contradiction to Lemma 3.2.

4

Concluding Remarks

The most interesting open problem from this paper is to obtain an almost instance optimal algorithm for Best-1-Arm, in particular to prove (or disprove) Conjecture E.4. Note that for the
clustered instances, and the instances where the gap entropy is Ω(ln ln n), we already have such
an algorithm. Our techniques may be helpful for obtaining better bounds for the Best-k-Arm
problem, or even the combinatorial pure exploration problem. In an ongoing work, we already have
some partial results on applying some of the ideas in this paper to obtain improved upper and lower
bounds for Best-k-Arm.

6

That is, whenever the algorithm pulls Anew , we pull A to get a reward r, and return 2ξ − r as the reward for
Anew . Note although we do not know µ, Anew is clearly an arm with mean 2ξ − µ.

10

References
[1] P. Afshani, J. Barbay, and T. M. Chan. Instance-optimal geometric algorithms. In FOCS, 2009.
[2] J.-Y. Audibert and S. Bubeck. Best arm identification in multi-armed bandits. In COLT, 2010.
[3] R. E. Bechhofer. A single-sample multiple decision procedure for ranking means of normal populations
with known variances. The Annals of Mathematical Statistics, pages 16–39, 1954.
[4] R. E. Bechhofer, J. Kiefer, and M. Sobel. Sequential identification and ranking procedures: with special
reference to Koopman-Darmois populations, volume 3. University of Chicago Press, 1968.
[5] S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit
problems. arXiv preprint arXiv:1204.5721, 2012.
[6] S. Bubeck, T. Wang, and N. Viswanathan. Multiple identifications in multi-armed bandits. arXiv
preprint arXiv:1205.3181, 2012.
[7] W. Cao, J. Li, Y. Tao, and Z. Li. On top-k selection in multi-armed bandits and hidden bipartite
graphs. In NIPS, pages 1036–1044, 2015.
[8] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[9] L. Chen, A. Gupta, and J. Li. Pure exploration of multi-armed bandit under matroid constraints. In
COLT, 2016.
[10] S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen. Combinatorial pure exploration of multi-armed
bandits. In NIPS, pages 379–387, 2014.
[11] H. Chernoff. Sequential Analysis and Optimal Design. SIAM, 1972.
[12] E. Even-Dar, S. Mannor, and Y. Mansour. Pac bounds for multi-armed bandit and markov decision
processes. In COLT, pages 255–270. Springer, 2002.
[13] E. Even-Dar, S. Mannor, and Y. Mansour. Action elimination and stopping conditions for the multiarmed bandit and reinforcement learning problems. JMLR, 7:1079–1105, 2006.
[14] R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. JCSS, 2003.
[15] R. Farrell. Asymptotic behavior of expected sample size in certain one sided tests. The Annals of
Mathematical Statistics, pages 36–72, 1964.
[16] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best arm identification: A unified approach to fixed
budget and fixed confidence. In NIPS, pages 3212–3220, 2012.
[17] V. Gabillon, M. Ghavamzadeh, A. Lazaric, and S. Bubeck. Multi-bandit best arm identification. In
NIPS, pages 2222–2230, 2011.
[18] A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In COLT, arXiv
preprint arXiv:1602.04589, 2016.
[19] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. On Finding the Largest Mean Among Many. ArXiv
preprint arXiv:1306.3917, 2013.
[20] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. lil’ucb: An optimal exploration algorithm for
multi-armed bandits. COLT, 2014.
[21] K. Jamieson and R. Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed
confidence setting. In CISS, pages 1–6. IEEE, 2014.
[22] S. Kalyanakrishnan and P. Stone. Efficient selection of multiple bandit arms: Theory and practice. In
ICML), pages 511–518, 2010.
[23] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone. Pac subset selection in stochastic multi-armed
bandits. In ICML, pages 655–662, 2012.
[24] Z. Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. In ICML,
pages 1238–1246, 2013.

11

[25] E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best arm identification in multi-armed
bandit models. arXiv preprint arXiv:1407.4443, 2014.
[26] E. Kaufmann and S. Kalyanakrishnan. Information complexity in bandit subset selection. In COLT,
2013.
[27] S. Mannor and J. N. Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem.
JMLR, 5:623–648, 2004.
[28] E. Paulson. A sequential procedure for selecting the population with the largest mean from k normal
populations. The Annals of Mathematical Statistics, pages 174–180, 1964.
[29] H. Robbins. Some aspects of the sequential design of experiments. In Herbert Robbins Selected Papers,
pages 169–177. Springer, 1985.
[30] Y. Zhou, X. Chen, and J. Li. Optimal pac multiple arm identification with applications to crowdsourcing.
In ICML, pages 217–225, 2014.

12

Supplementary Material for “On the Optimal Sample Complexity
for Best Arm Identification”
The supplementary material is organized as follows:
1. (Section A) We provide some preliminary knowledge for our later developments.
2. (Section B) We provide all details of our new algorithm DistrBasedElim and the proof of Theorem 2.5. In Section B.4, we define the clustered instances and show our algorithm is almost
instance optimal for such instances. In Section B.5, we slightly modify the algorithm and obtain
an improved (ε, δ)-PAC algorithm for Best-1-Arm.
3. (Section C) We provide the detailed proof of Theorem 3.1, our new lower bound for Best-1-Arm.
4. (Section D) We provide our new lower bound for Sign-ξ, which is the basis of our lower bound
reduction in Section C.
5. (Section E) We propose to investigate Best-1-Arm from the perspective of instance optimality,
and propose a conjecture concerning the fundamental sample complexity for every instance of
Best-1-Arm. We also discuss how our new results are related with the conjecture and why we
think the conjecture is likely to be true.
6. (Section F) This section contains some missing technical proofs from Section B.
7. (Section G) We present a class of δ-correct algorithms for Sign-ξ which needs o(∆−2 ln ln ∆−1 )
samples for infinite instances. It is useful in discussing the instance optimality in Section E.
8. (Section H) We provide a transformation that turns an algorithm with only conditional expected
sample complexity upper bound to one with asymptotically the same unconditional expected
sample complexity upper bound, under mild conditions.

A

Preliminaries

Definition A.1. Let R > 0, we say a distribution D on R has R-sub-Gaussian tail (or D is R-subGaussian) if for the random variable X drawn from D and any t ∈ R, we have that E[exp(tX −
tE[X])] ≤ exp(R2 t2 /2).
It is well known that the family of R-sub-Gaussian distributions contains all distributions with
support on [0, R] as well as many unbounded distributions such as Gaussian distributions with variance R2 . Then we recall a standard concentration inequality for R-sub-Gaussian random variables.
Lemma A.2. (Hoeffding’s inequality) Let X1 , . . . , Xn be n i.i.d. random variables drawn from an
R-sub Gaussian distribution D. Let µ = Ex∼D [x]. Then for any ε > 0, we have that
#
"


n
nε2
1X
Xi − µ ≥ ε ≤ 2 exp − 2 .
Pr
n
2R
i=1

13

For simplicity of exposition, we assume all reward distributions are 1-sub-Gaussian in the paper.
Suppose A is an algorithm for Best-1-Arm(or Sign-ξ). Let the given instance be I. Let E be
an event and PrA,I [E] be the probability that the event E happens when running A on instance I.
When A is clear from the context, we omit the subscript A and simply write PrI [E]. Similarly, if X
is a random variable, we use EA,I [X] to denote the expectation of X when running A on instance I.
Sometimes, A takes an additional confidence parameter δ, and we write Aδ to denote the algorithm
A with the fixed confidence parameter δ.
Let τi be the random variable that denotes the number of pulls from arm i (when the algorithm
P
and the problem instance are clear from the context) and EI [τi ] be its expectation. Let τ = ni=1 τi
be the total number of samples taken by A.
The Kullback-Leibler (KL) divergence of any two distributions p and q is defined to be


Z
dp
(x) dp(x) if q ≪ p
KL(p, q) = log
dq
where q ≪ p means that dp(x) = 0 whenever dq(x) = 0. For any two real numbers x, y ∈ (0, 1), let
H(x, y) = x log(x/y) + (1 − x) log((1 − x)/(1 − y)) be the relative entropy function.
Many lower bounds in the bandit literature rely on certain “changes of distributions” argument.
The following version (Lemma 1 in [25]) is crucial to us.
Lemma A.3. (Change of distribution) [25] We use an algorithm A for a bandit problem with n
arms. 7 Let I (with arm distributions {Di }i∈[n] ) and I ′ (with arm distributions {Di′ }i∈[n] ) be two
instances. Let E be an event, 8 such that 0 < PrA,I (E) < 1. Then, we have
n
X
i=1

EI [τi ]KL(Di , Di′ ) ≥ H(PrA,I (E), PrA,I ′ (E)).

N (µ, σ 2 ) denotes the Gaussian distribution with mean µ and standard deviation σ. We also need
the following well known fact about the KL divergence between two Gaussian distributions.
Lemma A.4.
KL(N (µ1 , σ 2 ), N (µ2 , σ 2 )) =

B

(µ1 − µ2 )2
.
2σ 2

An Improved Upper Bound for Best-1-Arm

In this section we prove Theorem 2.5 by presenting an algorithm for Best-1-Arm. Our final
algorithm builds on several useful components.

B.1

Useful Building Blocks

1. Uniform Sampling: The first building block is the simple uniform sampling algorithm.
7

We make no assumption on the behavior of A in this lemma. For example, A may even output incorrect answers
with high probability.
8
More rigorously, E should be in the σ-algebra Fτ where τ is a stopping time with respect to the filtration {Ft }t≥0 .

14

Algorithm 2: UniformSample(S, ε, δ)
Data: Arm set S, approximation level ε, confidence level δ.
Result: For each arm a, output the empirical mean µ̂[a] .
1

For each arm a ∈ S, sample it 2ε−2 ln(2 · δ−1 ) times. Let µ̂[a] be the empirical mean.

We have the following Lemma for Algorithm 2, which is a simple consequence of Lemma A.2.


Lemma B.1. For each arm a ∈ S, we have that Pr |µ[a] − µ̂[a] | ≥ ε ≤ δ.

2. Median Elimination: We need the MedianElim algorithm in [13], which is a classic (ε, δ)-PAC
algorithm for Best-1-Arm. The algorithm takes parameters ε, δ > 0 and a set S of n arms, and
returns an ε-optimal arm with probability 1 − δ. The algorithm runs in rounds. In each round, it
samples every remaining arm a uniform number of times, and then discard half of the arms with
lowest empirical mean (thus the name median elimination). It outputs the final arm that survives.
We denote the procedure by MedianElim(S, ε, δ). We use this algorithm in a black-box manner and
its performance is summarized in the following lemma.
Lemma B.2. Let µ[1] be the maximum mean value. MedianElim(S, ε, δ) returns an arm with mean
at least µ[1] − ε with probability at least 1 − δ, using a budget of at most O(|S| log(1/δ)/ε2 ) pulls.
3. Fraction test: FractionTest is an estimation procedure, which can be used to gain some
information about the distribution of the arms. The algorithm takes six parameters (S, cl , cr , δ, t, ε),
where S is the set of arms, δ is the confidence level, cl < cr are real numbers called range parameters,
and t ∈ (0, 1) is the threshold, and ε is a small positive constant. Typically, cl and cr are very
close. The goal of the algorithm, roughly speaking, is to distinguish whether there are still many
arms in S which have small means (w.r.t. cr ) or the majority of arms already have large means.
The precise guarantee the algorithm can achieve can be found in Lemma B.3.
The algorithm runs in ln(2 · δ−1 )(ε/3)−2 /2 iterations. In each iteration, it samples an arm ai
uniformly from S, and takes O(ln ε−1 (cr − cl )−2 ) independent samples from ai . Then, we look at
the fraction of iterations in which the empirical mean of ai is smaller than (cl +cr )/2. If the fraction
is larger than t, the algorithm returns True. Otherwise, it returns False.
For ease of notation, we define S ≥c := {µ[a] ≥ c | a ∈ S}, i.e., all arms in S with means at least
c. Similarly, we can define S >c , S ≤c and S <c .
Lemma B.3. Suppose ε < 0.1 and t ∈ (ε, 1 − ε). With probability 1 − δ, the following hold:
• If FractionTest outputs True, then |S >cr | < (1 − t + ε)|S| (or equivalently |S ≤cr | > (t − ε)|S|).
• If FractionTest outputs False, then |S <cl | < (t + ε)|S| (or equivalently |S ≥cl | > (1 − t − ε)|S|).
Moreover, the number of samples taken by the algorithm is O(ln δ−1 ε−2 ∆−2 ln ε−1 ), in which ∆ =
cr − cl . If ε is a fixed constant, then the number of samples is simply O(ln δ−1 ∆−2 ).
The proof can be found in Section F.
4. Eliminating arms: The final ingredient is an elimination procedure, which can be used to
eliminate most arms below a given threshold. The procedure takes four parameters (S, cl , cr , δ) as
input, where S is a set of arms, cl < cr are the range parameters, and δ is the confidence level.
It outputs a subset of S and guarantees that upon termination, most of the remaining arms have
means at least cl with probability 1 − δ.
15

Algorithm 3: FractionTest(S, cl , cr , δ, t, ε)
Data: Arm set S, range parameters cl , cr , confidence level δ, threshold t, approximate
parameter ε.
1
2
3
4
5
6
7
8
9
10

cnt ← 0
tot ← ln(2 · δ−1 )(ε/3)−2 /2
for i = 1 to tot do
Pick a random arm ai ∈ S uniformly.
µ̂[ai ] ← UniformSample({ai }, (cr − cl )/2, ε/3)
if µ̂[ai ] < (cl + cr )/2 then cnt ← cnt + 1
if cnt/tot > t then
Return True
else
Return False

Algorithm 4: Elimination(S, cl , cr , δ)
Data: Arm set S, range parameters cl , cr , confidence level δ.
Result: A set of arms after elimination.
1 S1 ← S
2 cm ← (cl + cr )/2
3 for r = 1 to +∞ do
4
δr = δ/(10 · 2r )
5
if FractionTest(Sr , cl , cm , δr , 0.075, 0.025) then
6
UniformSample(Sr , (cr − cm )/2, δr )
n
o
7
Sr+1 ← a ∈ Sr | µ̂[a] > (cm + cr )/2

8

9

else
Return Sr

Now, we describe the procedure Elimination which runs in iterations. It maintains the current set
Sr of arms, which is initially S. In each iteration, it first applies FractionTest(Sr , cl , cm , δr , 0.075, 0.025)
on Sr , where cm = (cr + cr )/2. If FractionTest returns True, which means that there are at least
5% fraction of arms with small means in Sr , we sample all arms in Sr uniformly by calling UniformSample(Sr , (cr − cm )/2, δr ) where δr = δ/(10 · 2r ), and retain those with empirical means at
least (cm + cr )/2. If FractionTest returns False (meaning that 90% arms have means at least cl ) the
algorithm terminates and returns the remaining arms. The guarantee of Elimination is summarized
in the following lemma. The proof can be found in Section F.
Lemma B.4. Suppose δ < 0.1. Let S ′ = Elimination(S, cl , cr , δ). Let A1 be the best arm among S,
with mean µ[A1 ] ≥ cr . Then with probability at least 1 − δ, the following statements hold
1. A1 ∈ S ′

(the best arm survives);

2. |S ′≤cl | < 0.1|S ′ |

(only a small fraction of arms have means less than cl );
16

Algorithm 5: DistrBasedElim(S, δ)
Data: Arm set S, confidence level δ.
Result: The best arm.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

h←1
S1 ← S
for r = 1 to +∞ do
if |Sr | = 1 then
Return the only arm in Sr
εr ← 2−r
δr ← δ/50r 2
ar ← MedianElim(Sr , εr /4, 0.01).
µ̂[ar ] ← UniformSample({ar }, εr /4, δr )
if FractionTest(Sr , µ̂[ar ] − 1.5εr , µ̂[ar ] − 1.25εr , δr , 0.4, 0.1) then
δh ← δ/50h2
br ← MedianElim(Sr , εr /4, δh )
µ̂[br ] ← UniformSample({br }, εr /4, δh )
Sr+1 ← Elimination(Sr , µ̂[br ] − 0.5εr , µ̂[br ] − 0.25εr , δh )
h←h+1
else
Sr+1 ← Sr

3. The number of samples is O(|S| ln δ−1 ∆−2 ), in which ∆ = cr − cl .

B.2

Our Algorithm

Now, everything is ready to describe our algorithm DistrBasedElim for Best-1-Arm. We provide
a high level description here. All detailed parameters can be found in Algorithm 5. The algorithm
runs in rounds. It maintains the current set Sr of arms. Initially, S1 is the set of all arms S. In
round r, the algorithm tries to eliminate a set of suboptimal arms, while makes sure the best arm
is not eliminated. First, it applies the MedianElim procedure to find an εr /4-optimal arm, where
εr = 2−r . Suppose it is ar . Then, we take a number of samples from ar to estimate its mean (denote
the empirical mean by µ̂[ar ] ). Unlike previous algorithms in [12, 24], which eliminates either a fixed
fraction of arms or those arms with mean much less than ar , we use a FractionTest to see whether
there are many arms with mean much less than ar . If it returns True, we apply the Elimination
procedure to eliminate those arms (for the purpose of analysis, we need to use MedianElim again,
but with a tighter confidence level, to find an εr /4-optimal arm br ). If it returns False, the algorithm
decides that it is not judicious to do elimination in this round (since we need to spend a lot of
samples, but only discard very few arms, which is wasteful), and simply sets Sr+1 to be Sr , and
then proceeds to the next round.
We devote the rest of the section to prove that Algorithm 5 indeed solves the Best-1-Arm
problem and achieves the sample complexity stated in Theorem 2.5. To simplify the argument, we
first describe some event we will condition on for the rest of the proof, and show the algorithm
indeed finds the best arm under the condition.

17

Lemma B.5. Let EG denote the event that all procedure calls in line 9, 10, 12, 13, 14 return
correctly for all rounds. EG happens with probability at least 1 − δ. Moreover, conditioning on EG ,
the algorithm outputs the correct answer.
Proof. By Lemma B.1, Lemma B.3 and Lemma B.4, we can simply bound the total error probability
with a union bound over all procedure calls in all rounds:
+∞
X

2δr +

r=1

+∞
X
h=1

3δh ≤ δ · 5

+∞
X
i=1

1/50i2 ≤ δ.

To prove the correctness, it suffices to show that the best arm A1 is never eliminated in line 14.
Conditioning on event EG , for all r, we have µ[br ] ≤ µ[A1] and |µ̂[br ] − µ[br ] | < εr /4, thus µ̂[br ] <
µ[A1 ] + εr /4. Clearly, this means µ[A1 ] ≥ µ̂[br ] − 0.25εr . Then by Lemma B.4, we know that A1 has
survived round r.
Note that the correctness of MedianElim (line 8) is not included in event EG .

B.3

Analysis of the running time

We use A to denote Algorithm 5. Let
T (δ, I) =

n
X
i=2



−1
−1
−1
)
+ ∆−2
ln
δ
+
ln
ln
min(n,
∆
∆−2
[2] ln ln ∆[2]
[i]
[i]

be the target upper bound we want to prove. We need to prove EAδ ,I [τ | EG ] = O(T (δ, I)) for
δ < 0.1. In the rest of the proof, we condition on the event EG , unless state otherwise. Let A1
denote the best arm.
We need some additional notations. First, for all s ∈ N, define the sets of arms U s , U ≥s and
≤s
U as:
s
+∞
[
[
r
≤s
s
−s
−s+1
≥s
Ur
U , U =
U = {a | 2 ≤ ∆[a] < 2
}, U =
r=s

Note that the best arm is not in any of the above set. Let εs =
the following equivalent definitions for U ≥s and U ≤s :
U ≥s = {a | µ[A1 ] − 2εs < µ[a] < µ[A1 ] },

r=1

2−s .

It is also convenient to use

U ≤s = {a | µ[a] ≤ µ[A1 ] − εs }

Let maxs be the maximum s such that U s is not empty.
We start with a lemma which concerns the ranges of µ̂[ar ] and µ̂[br ] .
Lemma B.6. Conditioning on EG , the following statements hold:
1. For any round r, µ̂[ar ] < µ[A1 ] + εr /4. In addition, if MedianElim (line 8) returns an εr /4approximation correctly in that round, we also have µ̂[ar ] > µ[A1] − 2εr /4.
2. For any round r, if br exists (the algorithm enters line 12), then µ̂[br ] < µ[A1 ] + εr /4 and
µ̂[br ] > µ[A1 ] − 2εr /4.

18

Proof. Conditioning on EG , we have that |µ̂[ar ] − µ[ar ] | < εr /4. Clearly µ[ar ] ≤ µ[A1 ] . Hence,
µ̂[ar ] < µ[A1 ] + εr /4. If ar is an εr /4-approximation of A1 , we have µ[ar ] ≥ µ[A1 ] − εr /4. Then, we
can see µ̂[ar ] > µ[A1 ] − 2εr /4. Note that conditioning on EG , br is always an εr /4-approximation of
A1 . Hence the second claim follows exactly in the same way.
Then we give an upper bound of h (updated in line 15). Note that h indicates how many times
we pass the FractionTest and execute Elimination (line 14). Indeed, in the following analysis, we
only need an upper bound of h during the first maxs rounds. We introduce the definition first.
Definition B.7. Given an instance I, conditioning on EG , we denote the maximum value of h
during the first maxs rounds as hI . It is easy to see that hI ≤ maxs .
Lemma B.8. hI = O(ln n) for any instance I.
Proof. Suppose we enter line 12 at round r. By Lemma B.6, we have µ̂[ar ] < µ[A1 ] + εr /4 and
µ̂[br ] > µ[A1 ] − 2εr /4. Hence µ̂[br ] > µ̂[ar ] − 0.75εr .
By Lemma B.3, we know there is at least 0.3 fraction of arms in Sr with means ≤ µ̂[ar ] − 1.25εr .
But by Lemma B.4, we know that after executing line 14, there are at most 0.1 fraction of arms in
Sr with means ≤ µ̂[br ] − 0.5εr . By noting that µ̂[br ] − 0.5εr > µ̂[ar ] − 1.25εr . we can see that |Sr |
drops by at least a constant fraction whenever we enter line 14. Therefore, h can increase by 1 for
at most O(ln n) times.
Remark B.9. Conditioning on EG , for all round r ≤ maxs , we can see h ≤ r. Thus, h ≤
min(hI , r), and ln δh−1 = O(ln δ−1 + ln[min(hI , r)]).
Now, we describe some behaviors of MedianElim and Elimination before we analyze the sample
complexity.
Lemma B.10. If FractionTest (line 10) outputs True, we know that there are > 0.3 fraction of
arms with means ≤ µ[A1 ] − εr in Sr . In other words, |U ≤r ∩ Sr | > 0.3|Sr |. Moreover, we have that
|U ≤r ∩ Sr+1 | ≤ 0.1|Sr+1 | (i.e., we can eliminate a significant portion in this round).
Proof. By Lemma B.6, we can see that µ̂[ar ] < µ[A1] + εr /4, µ̂[br ] > µ[A1 ] − 2εr /4. Now consider the
parameters for FractionTest. Let cr = µ̂[ar ] − 1.25εr . Then we have that cr < µ[A1 ] − εr .
By Lemma B.3, when FractionTest outputs True, we know that there are > (0.4 − 0.1) = 0.3
fraction of arms with means ≤ cr ≤ µ[A1 ] − εr in Sr . Clearly, µ[a] ≤ µ[A1 ] − εr is equivalent to
a ∈ U ≤r for an arm a.
Now consider the parameters for Elimination. Let cl = µ̂[br ] − 0.5εr . Then cl > µ[A1 ] − εr . We
also note that µ[a] ≤ µ[A1 ] − εr is equivalent to a ∈ U ≤r for an arm a. Then by Lemma B.4, after
≤cl
| ≤ 0.1|Sr+1 |.
the elimination, we have |U ≤r ∩ Sr+1 | ≤ |Sr+1
Lemma B.11. Consider a round r. Suppose MedianElim (line 8) returns a correct εr /4-approximation
ar . Then, the following statements hold:
1. If FractionTest (line 10) outputs True, we know there are > 0.3 fraction of arms with means
≤ µ[A1 ] − εr in Sr . In other words, |U ≤r ∩ Sr | > 0.3|Sr |. Moreover, we have that |U ≤r ∩ Sr+1 | ≤
0.1|Sr+1 |.
2. If it outputs False, we know there are at least 0.5 fraction of arms with means at least µ[A1] − 2εr
in Sr . In other words, |U ≥r ∩ Sr | + 1 > 0.5|Sr |.
19

Proof. Since MedianElim (line 8) returns the correctly, by Lemma B.6, µ̂[ar ] > µ[A1] − 2εr /4 and
µ̂[ar ] < µ[A1 ] + εr /4. Now consider the parameters for FractionTest, let cl = µ̂[ar ] − 1.5εr and
cr = µ̂[ar ] − 1.25εr , It is easy to see that cl > µ[A1 ] − 2εr , and cr < µ[A1] − εr .
The first claim just follows from Lemma B.10 (note that Lemma B.10 does not require the
output of MedianElim (line 8) being correct).
By Lemma B.3, if FractionTest outputs False, we know there are at least (1 − 0.4 − 0.1) = 0.5
fraction of arms with means ≥ cl > µ[A1 ] − 2εr in Sr . For an arm a, µ[a] > µ[A1 ] − 2εr is equivalent
to a ∈ U ≥r or a is the best arm A1 itself.
We also need the following lemma describing the behavior of the algorithm when r > maxs .
Lemma B.12. For each round r > maxs , the algorithm terminates if MedianElim returns an
εr /4-approximation correctly, which happens with probability at least 0.99.
Proof. If we already have |Sr | = 1 at the beginning of round r, then there is nothing to prove since
it halts immediately. So we can assume |Sr | > 1.
Suppose in round r, MedianElim returns a correct εr /4-approximation. Conditioning on EG ,
FractionTest must output True. Since if it outputs False, then by Lemma B.11, |U ≥r ∩ Sr | + 1 >
0.5|Sr |. But U ≥r = ∅ from r > maxs . So 1 > 0.5|Sr |, which implies |Sr | = 1, rendering a
contradiction.
Then, by Lemma B.11, |U ≤r ∩ Sr+1 | ≤ 0.1|Sr+1 |, which is equivalent to the fact that |U ≥r+1 ∩
Sr+1 | + 1 ≥ 0.9|Sr+1 |. Note that |U ≥r+1 ∩ Sr+1 | = 0 as U ≥r+1 = ∅. So it holds that 1 ≥ 0.9|Sr+1 |,
or equivalently |Sr+1 | = 1. Thus it terminates right after round r.
Finally, as MedianElim returns correctly an εr /4-approximation with probability at least 0.99,
the proof is completed.
We analyze the expected number of samples used for each subprocedure separately. We first
consider FractionTest (line 10) and UniformSample (line 9, 13) and prove the following simple lemma.
Lemma B.13. Conditioning on event EG , the expected number of samples incurred by FractionTest
(line 10) and UniformSample (line 9, 13) is


−1
−1
))
.
(ln
δ
+
ln
ln
∆
O ∆−2
[2]
[2]

Proof. By Lemma B.12, for any round r > maxs , the algorithm halts w.p. at least 0.99. So we can
bound the expectation of samples incurred by FractionTest and UniformSample by:
max
Xs
r=1

c4 · ln δr−1 ε−2
r +

+∞
X

r=maxs +1

c4 · (0.01)r−maxs −1 ln δr−1 ε−2
r

Here, c4 is a constant large enough such that in round r the number of samples taken by FractionTest
and UniformSample together is bounded by c4 · ln δr−1 ε−2
r . It is not hard to see the first sum is
dominated by the last term while the second sum is dominated by the first. So the bound is
−1 + ln ln ∆−1 )) since max is Θ(ln ∆−1 ).
O(∆−2
s
[2]
[2]
[2] (ln δ
Next, we analyze MedianElim (line 8, 12) and Elimination (line 14). In the following, we only
consider samples due to these two procedures.

20

Lemma B.14. Conditioning on event EG , the expected number of samples incurred by MedianElim
(line 8, 12) and Elimination (line 14) is
!
n
X
−1
−1
−2
∆[i] (ln δ + ln[min(hI , ln ∆[i] )]) .
O
i=2

We devote the rest of the section to the proof of Lemma B.14, which is more involved. We first
need a lemma which provides an upper bound on the number of samples for one round.
Lemma B.15. Let c3 be a sufficiently large constant. The number of samples in round r ≤ maxs
can be bounded by
(
if FractionTest outputs False.
c3 · |Sr |ε−2
r
−2
−1
c3 · |Sr |εr (ln δ + ln[min(hI , r)])
if FractionTest outputs True.
If r > maxs , the number of samples can be bounded by
−1
c3 · |Sr |ε−2
+ ln(hI + r − maxs )).
r (ln δ

Proof. Note that conditioning on event EG , Elimination always returns correctly. Let c3 be a
constant such that MedianElim(Sr , εr /4, 0.01) takes no more than c3 /3 · |Sr |ε−2
samples, and
r
MedianElim(Sr , εr /4, δh ) and Elimination(Sr , µ̂[ar ] − 1.5εr , µ̂[ar ] − 1.25εr , δh ) both take no more than
−1 + ln[min(h , r)]) samples conditioning on E . The later one is due to the fact
c3 /3 · |S|ε−2
I
G
r (ln δ
−1
that ln δh = O(ln δ−1 + ln[min(hI , r)]) for r ≤ maxs . If r > maxs , we have h ≤ hI + r − maxs ,
then the bounds follow from a simple calculation.
Proof of Lemma B.14. We prove the lemma inductively. Let T (r, Nsma ) denote the maximum expected total number of samples the algorithm takes at and after round r, when |Sr ∩U ≤r−1 | ≤ Nsma .
In other words, it is an upper bound of the expected number of samples we will take further, provided that we are at the beginning of round r and there are at most Nsma “small” arms left. By
definition, T (1, 0) is the final upper bound for the total expected number of samples taken by the
algorithm.
Let c1 = 4c3 , c2 = 60c3 . 9 For ease of notation, we let ls = ln(min(hI , s)).
We first consider the case where r = maxs + 1 and prove the following bound of T (r, Nsma ):
T (r, Nsma ) ≤ (ln δ−1 + ln hI )c1 · Nsma · ε−2
r .

(2)

Clearly there is nothing to prove for the base case Nsma = 0. So we consider Nsma ≥ 1. Now,
suppose the first round after r in which MedianElim (line 8) returns correctly an εr /4-approximation
′
is r ′ ≥ r. Clearly, this happens with probability at most 0.01r −r (all rounds in between fail). By
Lemma B.12, the algorithm terminates after round r ′ . Moreover, we have |U ≥r ∩ Sr | = 0 since
U ≥r = ∅. So Sr consists of the single best arm A1 and Nsma arms in U ≤r−1 . By Lemma B.15, the
number of samples is bounded by
′

r
X
i=r

c3 (ln δ−1 + ln[hI + i − maxs ])(1 + Nsma )ε−2
i .

9

Although these constants are chosen somewhat arbitrarily, they need to satisfy certain relations (will be clear
from the proof) and it is necessary to make them explicit.

21

Hence, we can bound T (r, Nsma ) as follows:
T (r, Nsma ) ≤

+∞
X

′

r ′ −r

(0.01)

r ′ =r

≤2c3 Nsma
≤3c3 Nsma

+∞
X

r ′ =r
+∞
X

r ′ =r

·

r
X
i=r


c3 ln δ−1 + ln[hI + i − maxs ])(1 + Nsma )ε−2
i
′

r ′ −r

(0.01)

·

r
X
i=r

(ln δ−1 + ln[hI + i − maxs ])ε−2
i

′

(0.01)r −r · (ln δ−1 + ln[hI + r ′ − maxs ])ε−2
r′

≤4c3 Nsma (ln δ−1 + ln hI )ε−2
r .
Now, we analyze the more challenging case where r ≤ maxs . For ease of notation, we let
Cr,s = (ln δ

−1

+ ls )

s
X

ε−2
i .

i=r

When r > s, we let Cr,s = 0. We also define
Pr = c2 ·

+∞
X
s=r

Cr,s |U s | + Cr,maxs

!

.

Pr can be viewed as a potential function. Notice that when r > maxs , we have Pr = 0. We are
going to show inductively that
T (r, Nsma ) ≤ (ln δ−1 + lr ) · c1 · Nsma · ε−2
r + Pr .

(3)

We note that (2) is in fact consistent with (3) (when r > maxs , we have Pr = 0 and lr = ln hI ).
The induction hypothesis assumes that the inequality holds for r + 1 and all Nsma . We need
to prove that it also holds for r and all Nsma . Now we are at round r. Conditioning on event EG ,
there are three cases we need to consider. We state the following lemmas, each analyzes one case,
which together imply our time bound. Their proofs are not difficult but somewhat tedious. So we
defer them to Section F.
Lemma B.16. Suppose that MedianElim (line 8) returns an εr /4-approximation of the best arm
A1 , and FractionTest outputs True. The expected number of samples taken at and after round r is
bounded by
(ln δ−1 + lr )c3 Nsma ε−2
r + Pr .
Lemma B.17. Suppose that MedianElim (line 8) returns an εr /4-approximation of the best arm
A1 , and FractionTest outputs False. The expected number of samples taken at and after round r is
bounded by Pr .
Lemma B.18. Suppose that MedianElim (line 8) returns an arm which is not an εr /4-approximation
of the best arm A1 . The expected number of samples taken at and after round r is bounded by
(ln δ−1 + lr )(c3 + 5c1 )Nsma ε−2
r + Pr .

22

Note that the bound in Lemma B.18 is larger than we need to prove (in particular, the constant
is larger). So, we need to combine three cases together as follows:
Recall that MedianElim (line 8) returns correctly an εr /4-approximation with probability p
(p ≥ 0.99). By Lemma B.16, Lemma B.17 and Lemma B.18, we have that
−2
T (r, Nsma ) ≤ (ln δ−1 + lr )(p · (c3 · Nsma · ε−2
r ) + (1 − p) · (c3 + 5c1 ) · Nsma εr ) + Pr

≤ (ln δ−1 + lr )((c3 + 0.05c1 ) · Nsma · ε−2
r ) + Pr

≤ (ln δ

−1

+ lr )c1 ·

Nsma · ε−2
r

+ Pr

(c3 + (1 − p) · 5c1 ≤ c3 + 0.05c1 )
(c3 + 0.05c1 ≤ c1 )

This finishes the proof of (3). Hence, the number of samples is bounded by T (1, 0) ≤ P1 . Note
that C1,s ≤ 2(ln δ−1 + ls )ε−2
s for any s. By a simple calculation of P1 , we can see that the overall
sample complexity for MedianElim and Elimination is
!
n
X
−1
+ ln[min(hI , ln ∆−1
∆−2
T (1, 0) ≤ P1 = O
[i] )]) .
[i] (ln δ
i=2

This finally completes the proof of Lemma B.14.
Putting Lemma B.14 and Lemma B.13 together, we have the following corollary.
Corollary B.19. With probability 1 − δ, Algorithm 5 returns the correct answer for Best-1-Arm
and take at most O(T ) sample in expectation, where
T =

n
X

−1
−2
−1
+ ln[min(hI , ln ∆−1
∆−2
[i] )]) + ∆[2] ln ln ∆[2] .
[i] (ln δ

i=2

The time bound in Theorem 2.5 is an immediate consequence of the above corollary and
Lemma B.8, which asserts hI = O(ln n).
However, there is one subtlety: we only provide a bound on the running time conditioning on EG
(i.e., E[TA | EG ]). With probability at most δ (when the event EG fails), we do not have any bound
on the running time (or the number of samples) of the algorithm (the algorithm may not terminate).
So strictly speaking, the overall expected running time of DistrBasedElim is not bounded. In fact,
several previous algorithms in the literature [13, 24, 16] have the same problem. However, it is
possible to transform such an algorithm A to another A′ which succeeds with probability 1 − δ and
whose overall expected running time is bounded as E[TA′ ] = O(E[TA | EG ]). We are not aware such
a transformation in the literature and we provide one in Section H.

B.4

Almost Instance Optimal Bound for Clustered Instances

Recall U s = {a | 2−s ≤ ∆[a] < 2−s+1 }.
Definition B.20. We say an instance I is clustered if |{U i 6= ∅ | 1 ≤ i ≤ maxs }| is bounded by a
constant.
In this case, we can obtain an almost instance optimal algorithm for such instances. For this
purpose, we only need to establish a tighter bound on hI .
Lemma B.21. hI ≤ 2 · |{U i 6= ∅ | 1 ≤ i ≤ maxs }|.
23

Source
Even-Dar et al. [12]
Gabillon et al. [16]
Kalyanakrishnan et al. [23]
Karnin et al. [24]
This paper (Thm B.24)

Sample Complexity
nε−2 · ln δ −1

Pn
Pn
−1
∆−2
+ ln i=2 ∆−2
i,ε ln δ
i,ε 
Pi=2
P
n
n
−1
∆−2
+ ln i=2 ∆−2
i,ε ln δ
 i,ε
Pi=2
n
∆−2
ln δ −1 + ln ln ∆−1
i,ε
i,ε
i=2

Pn
−2
−1
−1
−1
+ ln ln min(n, ∆i,ε
) + ∆−2
2,ε ln ln ∆2,ε
i=2 ∆i,ε ln δ

Table 2: Sample complexity upper bounds for (ε, δ)-PAC algorithms. Here, ∆i,ε = max(∆[i] , ε)
′

Proof. Let s be an index such that U s is not empty. Let s′ be the largest index < s such that U s is
not empty. If such index does not exist, let s′ = 0. We show that during rounds s′ +1, s′ +2, . . . , s−1,
we can only call Elimination (or equivalently, increase h) once.
Suppose otherwise, we call Elimination in round r and r ′ such that s′ < r < r ′ < s. We further
assume that there is no other call to Elimination between round r and r ′ . Then clearly Sr′ = Sr+1 .
Now by Lemma B.10, we have |U ≤r ∩ Sr+1 | ≤ 0.1|Sr+1 |, but this means |Ur′ ∩ Sr′ | ≤ 0.1|Sr′ |,
as Ur′ = U ≤r and Sr′ = Sr+1 . Again by Lemma B.10, this contradicts the fact that on round r ′ ,
FractionTest outputs true.
As U maxs is not empty, we can partition the rounds 1, 2, . . . , maxs into at most 2 · |{U i 6= ∅ |
1 ≤ i ≤ maxs }| groups. Each group is either a single round which corresponds to a non-empty set
′
U s , or the rounds between two rounds corresponding to two adjacent non-empty sets U s and U s .
Therefore, h can increase at most by 1 in each group, which concludes the proof.
The following theorem is an immediate consequence of the above lemma and Corollary B.19.
Theorem B.22. There is an δ-correct algorithm for clustered instances, with expected sample
complexity

Xn
−1
−2
−1
T (δ, I) = O
ln
ln
∆
ln
δ
+
∆
∆−2
[2] .
[2]
[i]
i=2

Example B.23. Consider a very simple yet important instance where there are n − 1 arms with
mean 0.5, and a single arm with mean 0.5 + ∆. In fact, a careful examination of all previous algorithms (including [20, 24]) shows that they all require Ω n∆−2 (ln δ−1 + ln ln ∆−1 ) samples even
in this particular instance. However, our algorithm only requires O n∆−2 ln δ−1 + ∆−2 ln ln ∆−1
samples. Our bound is almost instance optimal, since the first term matches the instance-wise lower
bound n∆−2 ln δ−1 . This is the best bound for such instances we can hope for.

B.5

An Improved PAC Algorithm

Finally, we discuss how to convert our algorithm to an (ε, δ)-PAC algorithm for Best-1-Arm. Our
result improves several previous PAC algorithm, which we summarize in Table 2.
Theorem B.24. For any ε < 0.5 and δ < 0.1, there exists an (ε, δ)-PAC algorithm for Best-1Arm, with expected sample complexity
!
n
X
−2
−1
−1
−2
−1
T (δ, I) = O
∆i,ε (ln δ + ln ln min(n, ∆i,ε )) + ∆2,ε ln ln ∆2,ε ,
i=2

where ∆i,ε = max(∆[i] , ε).
24

Proof. Given parameters ε, δ, we run DistrBasedElim with confidence δ/2 only for the first ⌈ln ε−1 ⌉
rounds. After that, we invoke MedianElim with confidence δ/2 to find an ε-optimal arm among
S⌈log2 ε−1 ⌉ . Clearly we are correct with probability at least 1 − δ. The analysis for the sample
complexity is exactly the same as the original DistrBasedElim.

C

A New Lower bound for Best-1-Arm

In this section, we provide a new lower bound for Best-1-Arm. In particular, we prove Theorem 3.1. From now on, δ is a fixed constant such that 0 < δ < 0.005. We use [0, N ] to denote the
set of integers {0, 1, . . . , N }. Throughout this section, we assume the distributions of all the arms
are Gaussian with variance 1.
Our proof for Theorem 3.1 consists of two ingredients. The first one is a non-trivial lower bound
for Sign-ξ, which we state here but defer its proof to the next section. The second one is a novel
reduction from Sign-ξ to Best-1-Arm, which turns the lower bound for Sign-ξ into the desired
lower bound for Best-1-Arm.
For stating the lower bound for Sign-ξ we introduce some notations first. Let A′ denote an
algorithm for Sign-ξ, Aµ be an arm with mean µ (i.e., with distribution N (µ, 1)), and we define
TA′ (∆) = max(TA′ (Aξ+∆ ), TA′ (Aξ−∆ )). Then we have the following lower bound for Sign-ξ. The
proof is deferred to Section D.
Lemma C.1. For any δ′ -correct algorithm A′ for Sign-ξ with δ′ ≤ 0.01, there exist constants
N0 ∈ N and c1 > 0 such that for all N ≥ N0 :
|{TA′ (∆) < c1 · ∆−2 ln N | ∆ = 2−i , i ∈ [0, N ]}| ≤ 0.1(N + 1).
For an algorithm A for Best-1-Arm, let Aperm be the algorithm which first randomly permutes
the input arms, then runs A. More precisely, given an arm instance I with n arms, Aperm first
chooses a random permutation π on n elements in I uniformly, then simulates A on the instance
π ◦ I and returns what A returns. It is not difficult to see that the running time of Aperm only
depends on the set {Di } of reward distributions of the instance, not their particular order.
Clearly, if A is a δ-correct algorithm for any instance of Best-1-Arm, so is Aperm . Furthermore,
we have the following simple lemma, which says we only need to prove a lower bound for Aperm .
Lemma C.2. For any instance I, there exists a permutation π such that TA (π ◦ I) ≥ TAperm (I).
Proof. By the definition of Aperm , we can see that
TAperm (I) =

1
n!

X

π∈Sym(n)

TA (π ◦ I),

where Sym(n) is the set of all n! permutations of {1, . . . , n}.
Now we prove theorem 3.1. The high-level idea is to construct some “balanced” instances for
Best-1-Arm, and show that if an algorithm A is “fast” on those instances, we can construct a fast
algorithm for Sign-ξ, which leads to a contradiction to Lemma C.1.

25

Proof of Theorem 3.1. In this proof, we assume all distributions are Gaussian random variables
with σ = 1. Without loss of generality, we can assume N0 in Lemma C.1 is an even integer, and
N0 > 10. So we have 2 · 4N0 ≥ 43 · 4N0 + N0 + 2. Let N = 2 · 4N0 .
For
the largest even integer m such that 2 · 4m ≤ n. Clearly m ≥ N0 > 10
Pmeveryk n ≥ N , we pick
and k=0 4 + m + 2 ≤ 34 · 4m + m + 2 ≤ 2 · 4m . Also, by the choice of m, we have 2 · 4m+2 > n,
hence 4m > n8 .
Consider the following Best-1-Arm instance Iinit with n arms:
1. There is a single arm with mean ξ.
2. For each integer k ∈ [0, m], there are 4m−k arms with mean ξ − 2−k .
P
k
3. There are n − m
k=0 4 − 1 arms with mean ξ − 2.

For a Best-1-Arm instance I, let n(I) be the number of arms in I, and ∆[i] (I) be the gap ∆[i]
Pn(I)
according to I. We denote H(I) = i=2 ∆[i] (I)−2 .
Now we define a class of Best-1-Arm instances {IS } where each S ⊆ {0, 1, . . . , m}. Each IS
is formed as follows: for every k ∈ S, we add one more arm with mean ξ − 2−k to Iinit ; finally
we remove |S| arms with mean ξ − 2 (by our choice of m there are enough such arms to remove).
Obviously, there are still n arms in every instance IS .
Let c be a universal constant to be specified later (in particular c does not dependent on n).
Now we claim that for any δ-correct algorithm A for Best-1-Arm, there must exist an instance IS
such that
TAperm (IS ) > c · H(IS ) · ln m = Ω(H(IS ) ln ln n).

Suppose for contradiction that there exists a δ-correct A such that TAperm (IS ) ≤ c · H(IS ) · ln m
for all S.
Let U = {IS | |S| = m/2},
 V = {IS | |S| = m/2 + 1} be two sets of Best-1-Arm instances.
Notice that |U | = |V | = m+1
m/2 (since m is even).
Fix S ∈ U . Consider the problem Sign-ξ, in which the given instance is a single arm A with
unknown mean µ, and we would like to decide whether µ > ξ or µ < ξ. Consider the following two
algorithms for Sign-ξ, which call Aperm as a subprocedure.
1. A1S : We first create a Best-1-Arm instance instance Inew by replacing one arm with mean ξ − 2
in IS with A. Then run Aperm on Inew . We output µ > ξ if Aperm selects A as the best arm.
Otherwise, we output µ < ξ.
2. A2S : We first construct an artificial arm Anew with mean 2ξ − µ from A 10 , and create a Best1-Arm instance Inew by replacing one arm with mean ξ − 2 in IS with Anew . Then run Aperm
on Inew . We output µ < ξ if Aperm selects Anew as the best arm. Otherwise, we output µ > ξ.
Since Aperm is δ-correct for Best-1-Arm, A1S and A2S are both δ-correct for Sign-ξ.
Now, consider the algorithm AS for Sign-ξ which runs as follows: It simulates A1S and A2S
simultaneously. Each time it takes a sample from the input arm, and feeds it to both A1S and A2S .
If A1S (A2S resp.) terminates first, it returns the output of A1S (A2S resp.). In case of a tie, it returns
the output of A1S .
10

That is, whenever the algorithm pulls Anew , we pull A to get a reward r, and return 2ξ − r as the reward for
Anew . Note although we do not know µ, Anew is clearly an arm with mean 2ξ − µ.

26

First, we can see that if both A1S and A2S are correct, then AS must be correct. Therefore, AS
is 2δ-correct for Sign-ξ.
Then we are going to show that there exists some particular S such that the algorithm AS runs
too fast for way too many points in {∆ = 2−i }i∈[0,m] for Sign-ξ hence rendering a contradiction
to Lemma C.1.
For a Best-1-Arm instance IS and an integer k ∈ [0, m], we use NSk to denote the number of
arms with gap 2−k . Let akS · 4k be the expected number of samples taken from an arm with gap
2−k by Aperm . Then we have that
m
X
k=0

NSk (4k · akS ) ≤ TAperm (IS ) ≤ c · H(IS ) · ln m.

Since 4m−k ≤ NSk ≤ 4m−k + 1, we can see that
H(IS ) =

m
X
k=0

NSk · 4k + (n −

m
X

4k − 1 − |S|) · 2−2 ≤ 2

m
X

≤ c · H(IS ) · ln m ≤ c 2

m
X

k=0

4m +

k=0

1
· n.
4

Thus we have that
m
X
k=0

m−k

4

k

akS )

(4 ·

≤

m
X

NSk (4k

k=0

Simplifying it a bit and noting that
m
X
k=0

which is equivalent to

m
X
k=0

n
8

· akS )

k=0

1
4 + n
4
m

!

· ln m.

< 4m , we get that

4m · akS ≤ c · 2(m + 2)4m ln m,

akS ≤ 2c · (m + 2) ln m ≤ 3c · (m + 1) ln m.

The last inequality holds since m ≥ N0 > 10.
P
c1
k
Now we set c = 30
, in which c1 is the constant in Lemma C.1. Since m
k=0 aS ≤ 3c·(m+1) ln m =
c1
k m
10 ·(m+1)·ln m, we can see for any S, there are at most 0.1 fraction of elements in {aS }k=0 satisfying
akS ≥ c1 · ln m.
Then for S ∈ U , let badS = {k 6∈ S ∧ akS∪{k} ≥ c1 ln m | k ∈ [0, m]}. We have that
X

S∈U

|badS | ≤

m
XX

S∈V k=0

1{akS ≥ c1 ln m} ≤

m+1
m+1
|V | =
|U |.
10
10

By an averaging argument, there exists S ∈ U such that |badS | ≤ m+1
10 . We will show for that
particular S, the algorithm AS for Sign-ξ contradicts Lemma C.1.
Now we analyze the expected total number of samples taken by AS on arm A with mean µ and
gap ∆ = |ξ − µ| = 2−k . Suppose k ∈
/ S. A key observation is the following: if µ < ξ, then the
1
instance constructed in AS is exactly IS∪{k} ; otherwise µ > ξ, since 2ξ − (ξ + ∆) = ξ − ∆ = ξ − 2−k ,
the instance constructed in A2S is exactly IS∪{k} (the order of arms in the constructed instance
27

and IS∪{k} may differ, but as Aperm randomly permutes the arms beforehand, it does not matter).
Hence, either TA1 (A) = akS∪{k} · 4k or TA2 (A) = akS∪{k} · 4k . Since AS terminates as soon as either
S
S
one of them terminate, we clearly have TAS (A) ≤ min(TA1 (A), TA2 (A)) ≤ akS∪{k} · 4k for arm A
S
S
with gap 2−k when k 6∈ S.
So for all k ∈ [0, m] \ (S ∪ badS ), we can see TAS (2−k ) ≤ akS∩{k} · 4k < c1 · 4k ln m. But this
implies that
|[0, m] \ (S ∪ badS )|
{TAS (∆) < c1 · ∆−2 ln m | ∆ = 2−i , i ∈ [0, m]}
≥
≥ 0.4,
m+1
m+1
which contradicts Lemma C.1. So there must exist IS such that TAperm (IS ) > c · H(IS ) · ln m.
P
By Lemma C.2, there exists a permutation π on IS such that TA (π ◦ IS ) ≥ 2c ni=2 ∆−2
i ln ln n.
This finishes the first part of the theorem.
−1
To see that ∆−2
2 ln ln ∆2 is not the dominating term, simply notice that
−1
∆−2
2 ln ln ∆2

m

n

k=0

i=2

1 X k k
2 · ln 4 X −2
∆i ln ln n.
= 4 ln(m · ln 2) ≤ 4 ln m ≤
NS · 4 ln m ≤
m
ln n
m

m

This proves the second statement of the theorem.

D

A New Lower Bound for Sign-ξ

In this section, we prove a new lower bound of Sign-ξ (Theorem D.1), from which Lemma C.1
follows easily.
We introduce some notations first. Recall that the distributions of all the arms are Gaussian
with variance 1. Fix an algorithm A for Sign-ξ, for a random event E, let PrA,Aµ [E] (recall that
Aµ denotes an arm with mean µ) denote the probability that E happens if we run A on arm Aµ .
For notational simplicity, when A is clear from the context, we abbreviate it as Prµ [E]. Similarly,
we write Eµ [X] as a short hand notation for EA,Aµ [X], which denotes the expectation of random
variable X when running A on arm Aµ .
We use 1{expr} to denote the indicator function which equals 1 when expr is true and 0
otherwise, and we define F (∆) = ∆−2 · ln ln ∆−1 , which is the wanted lower bound for Sign-ξ.
Finally, for an integer N ∈ N, a δ-correct algorithm A for Sign-ξ, and a function g : R → R, define
N
X

1 There exists some ∆ ∈ [e−i , e−i+1 ) such that: TA (∆) < g(∆) .
C(A, g, N ) =
i=1

Intuitively, it is the number of intervals [e−i , e−i+1 ) among the first N intervals that contains a fast
point with respect to g.
Theorem D.1. For any γ > 0, we have a constant c1 > 0 (which depends on γ) such that for any
0 < δ < 0.01,
C(A′ , c1 F, N )
= 0.
lim
sup
N →+∞ A′ is δ-correct
Nγ
In other words, the fraction of the intervals containing fast points with respect to Ω(F ) can be
smaller than any inverse polynomial.
28

Before proving Lemma D.1, we show it implies Lemma C.1 as desired. We restate Lemma C.1
here for convenience.
Lemma C.1 (restated) For any δ′ -correct algorithm A′ for Sign-ξ with δ′ ≤ 0.01, there exist
constants N0 ∈ N and c1 > 0 such that for all N ≥ N0 :
|{TA′ (∆) < c1 · ∆−2 ln N | ∆ = 2−i , i ∈ [0, N ]}| ≤ 0.1(N + 1).

Proof of Lemma C.1. Let γ = 1/2. Applying Lemma D.1, we can see that there exist an integer
M0 and a constant c2 such that, for any integer M ≥ M0 , it holds that
√
C(A′ , c2 F, M ) ≤ 0.05 · M ,
for any δ′ -correct algorithm A′ for Sign-ξ.
Then for any N ≥ M0 / ln 2, we can see that
|{TA′ (∆) < c2 · F (∆) | ∆ = 2−i , i ∈ [0, N ]}| ≤ C(A′ , c2 · F, ⌈ln 2 · N ⌉) · 2 ≤ 0.1 ·

√

N,

−i −i+1 ) can contain at most 2 values of the form ∆ = 2−k .
since e⌈ln 2·N ⌉ ≥ 2N , and
√ each interval [e , e
−i
For ∆ = 2 (i ≥ N), we have that F (∆) = ∆−2 ln ln ∆−1 = ∆−2 ln i ≥ ∆−2 ln N/2. Therefore, by letting c1 = c2 /2, we can bound the cardinality of the set as follows

|{TA′ (∆) < c1 · ∆−2 ln N | ∆ = 2−i , i ∈ [0, N ]}|
√
√
≤ N + |{TA′ (∆) < c1 · ∆−2 ln N | ∆ = 2−i , i ∈ [ N , N ]}|
√
√
≤ N + |{TA′ (∆) < c2 · F (∆) | ∆ = 2−i , i ∈ [ N , N ]}|
√
≤1.1 · N .
This completes the proof of the lemma.

D.1

Proof for Theorem D.1

The rest of this section is devoted to prove Theorem D.1. From now on, 0 < δ < 0.01 is a fixed
constant. We first show a simple but convenient lemma based on Lemma A.3.
Lemma D.2. Let I1 (with reward distribution D1 ) and I2 (with reward distribution D2 ) be two
instances of Sign-ξ. Let E be a random event and τ be the total number of samples taken by A.
Suppose PrD1 [E] ≥ 21 . Then, we have
PrD2 [E] ≥


1
exp −2ED1 [τ ]KL(D1 , D2 ) .
4

Proof. Applying Lemma A.3, we have that

ED1 [τ ] · KL(D1 , D2 ) ≥ H(PrD1 [E], PrD2 [E]) ≥ H






1
1
1
, PrD2 [E] ≥ · ln
.
2
2
4 PrD2 [E](1 − PrD2 [E])

Hence, we can see that 4 PrD2 [E](1− PrD2 [E]) ≥ exp(−2ED1 [τ ]·KL(D1 , D2 )), from which the lemma
follows easily.
29

From now on, suppose A is a δ-correct algorithm for Sign-ξ. We define two events:
EU = [A outputs “µ > ξ”],
E(∆) = EU ∧ [d∆−2 ≤ τ ≤ 5TA (∆)],
where τ is the number of samples taken by A and d is a universal constant to be specified later.
The following lemma is a key tool, which can be used to partition the event EU into several disjoint
parts.
Lemma D.3. For any ∆ > 0 and d < H(0.2, 0.01)/2, we have that
1
Prξ+∆ [E(∆)] = PrA,Aξ+∆ [E(∆)] ≥ .
2
Proof. First, we can see that Prξ+∆ [EU ] ≥ 1 − δ ≥ 0.99 since A is δ-correct and “µ > ξ” is the right
answer.
Now, we claim Prξ+∆ [τ < d∆−2 ] < 0.25. Suppose to the contrary that Prξ+∆ [τ < d∆−2 ] ≥ 0.25.
We can see that Prξ+∆ [EU ∧ τ < d∆−2 ] ≥ 0.25 − δ > 0.2.
Consider the following algorithm A′ : A′ simulates A for d∆−2 steps. If A halts, A′ outputs what
A outputs, otherwise A′ outputs nothing.
Let EV be the event that A′ outputs µ > ξ. Clearly, we have PrA′ ,ξ+∆ [EV ] > 0.2. On the other
hand, PrA′ ,ξ−∆ [EV ] < δ, since A is a δ-correct algorithm. So by Lemma A.3, we have that
EA′ ,ξ+∆ [τ ]KL(N (ξ + ∆, σ), N (ξ − ∆, σ)) = EA′ ,ξ+∆ [τ ]2∆2 ≥ H(0.2, δ) ≥ H(0.2, 0.01).
Since d∆−2 ≥ EA′ ,ξ+∆ [τ ], we have d ≥ H(0.2, 0.01)/2. But this contradicts the condition of the
lemma. Hence, we must have Prξ+∆ [τ < d∆−2 ] < 0.25.
Finally, we can see that
Prξ+∆ [E(∆)] ≥ Prξ+∆ [EU ] − Prξ+∆ [τ < d∆−2 ] − Prξ+∆ [τ > 5TA (∆)]
≥ 1 − 0.01 − 0.25 − Prξ+∆ [τ > 5EA,ξ+∆ [τ ]]

≥ 1 − 0.01 − 0.25 − 0.2 ≥ 0.5

where the first inequality follows from the union bound and the second from Markov inequality.
Lemma D.4. For any δ-correct algorithm A, and any finite sequence {∆i }ni=1 such that
1. the events {E(∆i )} are disjoint,

11

and 0 < ∆i+1 < ∆i for all 1 ≤ i ≤ n − 1;

2. there exists a constant c > 0 such that TA (∆i ) ≤ c · F (∆i ) for all 1 ≤ i ≤ n,
it must hold that:

n
X
i=1

11

exp{−2c · F (∆i ) · ∆2i } ≤ 4δ.

More concretely, the intervals [d∆−2
i , 5TA (∆i )] are disjoint.

30

P
Proof. Suppose for contradiction that ni=1 exp{−2c · F (∆i ) · ∆2i } > 4δ.
Let α = 51 ∆n . By Lemma A.4, we can see that KL(N (ξ + ∆i , σ), N (ξ − α, σ)) =
1
2
2
2 (1.2∆i ) ≤ ∆i . By Lemma D.2, we have:
Prξ−α [EU ] ≥

n
X
i=1

Prξ−α [E(∆i )] ≥

n

n

i=1

i=1

1
(∆i + α)2
2σ2

≤

1X
1X
exp{−2Eξ+∆i [τ ] ∆2i } ≥
exp{−2c · F (∆i ) · ∆2i } > δ.
4
4

Note that we need Lemma D.3(1) (i.e., Prξ+∆i [E(∆i )] ≥ 1/2 ) in order to apply Lemma D.2 for the
second inequality. The above inequality means that A outputs a wrong answer for instance ξ − α
with probability > δ, which contradicts that A is δ-correct.
Now, we try to utilize Lemma D.4 on a carefully constructed sequence {∆i }. The construction
of the sequence {∆i } requires quite a bit calculation. To facilitate the calculation, we provide a
sufficient condition for the disjointness of the sequence, as follows.
Lemma D.5. A is any δ-correct algorithm for Sign-ξ. c > 0 is a universal constant. The sequence
{∆i }N
i=0 satisfies the following properties:
1. 1/e > ∆1 > ∆2 > . . . > ∆N ≥ α > 0.
2. For all i ∈ [N ], we have that TA (∆i ) ≤ c · F (∆i ).
3. Let Li = ln ∆−1
i . We have Li+1 − Li >

1
2

ln ln ln α−1 + c1 , in which c1 =

ln c+ln 5−ln d
.
2

Then, the events {E(∆1 ), E(∆2 ), . . . , E(∆N )} are disjoint.
Proof. We only need to show the intervals for each E(∆i ) are disjoint. In fact, it suffices to show
it holds for two adjacent events E(∆i ) and E(∆i+1 ). Since 5TA (∆i ) ≤ 5c · F (∆i ), we only need to
show 5c · F (∆i ) < d∆−2
i+1 , which is equivalent to
ln c + ln 5 + 2Li + ln ln Li < ln d + 2Li+1 .
By simple manipulation, this is further equivalent to Li+1 − Li > (ln c + ln 5 − ln d + ln ln Li )/2.
Since α ≤ ∆i , we have ln ln ln α−1 ≥ ln ln Li , which concludes the proof.
Now, everything is ready to prove Theorem D.1.
Proof of Theorem D.1. Suppose for contradiction, for any c1 > 0, the limit is not zero. This is
equivalent to
lim sup
N →+∞ A′

C(A′ , c1 F, N )
> 0.
Nγ
is δ−correct
sup

(4)

We claim that for c1 = γ4 , the above can lead to a contradiction.
First, we can see that (4) is equivalent to the existence of an infinite increasing sequence {Ni }i
and a positive number β > 0 such that
C(A′ , c1 F, Ni )
> β,
Niγ
is δ−correct
sup

A′

31

for all i.

Consider some large enough Ni in the above sequence. The above formula implies that there
exists a δ-correct algorithm A such that C(A, c1 F, Ni ) ≥ βNiγ .
We maintain a set S, which is initially empty. For each 2 ≤ j ≤ Ni , if there exists ∆ ∈
[e−j , e−j+1 ) such that TA (∆) ≤ c1 F (∆), then we add one such ∆ into the set S. We have |S| ≥
C(A, c1 F, Ni ) − 1 ≥ βNiγ − 1 (−1 comes from that j starts from 2). Let


ln c1 + ln 5 − ln d + ln ln Ni
+1 .
b=
2
We keep only the 1st, (1 + b)th, (1 + 2b)th, . . . elements in S, and remove the rest. With a slight
|S|
abuse of notation, rename the elements in S by {∆i }i=1 , sorted in decreasing order.
It is not difficult to see that 1e > ∆1 > ∆2 > . . . > ∆|S| ≥ e−Ni > 0. By the way we choose the
elements, for 1 ≤ i < |S|, we have
−1
ln ∆−1
i+1 − ln ∆i >

ln c1 + ln 5 − ln d 1
+ ln ln N.
2
2

Recall that we also have TA (∆i ) ≤ c1 F (∆i ) for all i. Hence, we can apply Lemma D.5 and conclude
that all events {E(∆i )} are disjoint.
We have |S| ≥ (βNiγ − 1)/b, for large enough Ni (we can choose such Ni since {Ni } approaches
to infinity), it implies |S| ≥ βNiγ / ln ln Ni . Then, we can get
|S|
X
j=1

exp{−2c1 · F (∆j ) ·

∆−2
j }

=

|S|
X
j=1

=

|S|
X
j=1

exp{−γ · ln ln ∆−1
j /2}
−γ/2

−γ/2
(ln ∆−1
≥ |S| · Ni
j )
−γ/2

≥βNiγ / ln ln Ni · Ni

γ/2

= βNi

/ ln ln Ni .

The inequality in the second line holds since ∆j ≥ e−Ni for all j ∈ [|S|]. Since γ > 0, we can choose
γ/2
Ni large enough such that βNi / ln ln Ni > 4δ, which renders a contradiction to Lemma D.4.
Remark D.6. It would be transparent from our proof why the ln ln ∆−1 term is essential: The main
reason is that ∆ is not known beforehand (if ∆ is known, Sign-ξ can be solved in O(∆−2 ln δ−1 )
time). Intuitively, an algorithm has to “guess” and “verify” (in some sense) the true ∆ value.
As a result, if the algorithm is “lucky” in allocating the time for verifying the right guess of ∆,
it may stop earlier and thus be faster than F (∆) for some ∆s. But as we will demonstrate, if
an algorithm stops earlier on larger ∆, it would hurt the accuracy for smaller ∆, and there is no
way to be always lucky. This is the only factor accounting for the ln ln ∆−1 . While Farrell’s proof
attributes the ln ln ∆−1 factor to the Law of Iterative Logarithm (see also [20]), our proof shows
that the ln ln ∆−1 factor exists due to algorithmic reasons, which is a new perspective.

E

On Almost Instance Optimality

Instance optimality ([14, 1]) is the strongest possible notion of optimality in the theoretical computer
science literature. Loosely speaking, an algorithm A is instance optimal if the running time of A
32

on instance I is at most O(L(I)), where L(I) is the lower bound required to solve the instance for
any algorithm.
Let us first consider Sign-ξ (the two arms case). As we mentioned, Farrell’s lower bound (1) is
not an instance-wise lower bound. On the other hand, it is impossible to obtain an Ω(∆−2 ln ln ∆−2 )
lower bound for every instance, since we can design an algorithm that uses o(∆−2 ln ln ∆−2 ) samples
for infinite number of instances. We provide a detailed discussion in Section G. Combining this
two fact, we can see that it is impossible to obtain an instance optimal algorithm even for Sign-ξ.
Hence, it appears to be more hopeless to consider instance optimality for Best-1-Arm. However,
based on our current understanding, we suspect that the two arms case is the only obstruction
for an instance optimal algorithm, and modulo a ∆−2
[2] ln ln ∆[2] additive term, we may be able to
achieve instance optimality for Best-1-Arm.
We propose an intriguing conjecture concerning the instance optimality of Best-1-Arm. The
conjecture provides an explicit formula for the sample complexity. Interestingly, the formula involves an entropy term, which we call the gap entropy, which has not appeared in the bandit literature, to the best of our knowledge. We assume that all reward distributions are Gaussian with
variance 1. In order to state the conjecture formally, we need to define what is an instance-wise
lower bound. Our definition is inspired by that in [1].
Definition E.1. (Order-Oblivious Instance-wise Lower Bound) Suppose L(I, δ) is a function which
maps a Best-1-Arm instance I with n arms, and confidence parameter δ to a number. We say
L(I, δ) is an instance-wise lower bound for I if
L(I, δ) ≤

inf

A:A is δ-correct

1
·
n!

X

π∈Sym(n)

TA (π ◦ I).

Now, we define the entropy term.
Definition E.2. (Gap Entropy) Given a Best-1-Arm instance I, let
X
and
Gi = {u ∈ [2, n] | 2−i ≤ ∆[u] < 2−i+1 }, Hi =
∆−2
[u] ,

pi = H i /

u∈Gi

X

Hj .

j

We can view {pi } as a discrete probability distribution. We define the following quantity as the gap
entropy for the instance I
X
Ent(I) =
pi log p−1
i .
Gi 6=∅

Note that it is exactly the Shannon entropy for the distribution defined by {pi }.
Remark E.3. We choose to partition the arms based on the powers of 2. There is nothing special
about 2 and replacing it by any other constant only changes Ent(I) by a constant factor.
P
Now, we formally state our conjecture. Let H(I) = ni=2 ∆−2
[i] .

Conjecture E.4. For any Best-1-Arm instance I and confidence δ ∈ (0, c) (c is a universal small
constant), let

L(I, δ) = Θ H(I)(ln δ−1 + Ent(I)) .
L(I, δ) is an instance-wise lower bound for I.

33

Moreover, there is a δ-correct algorithm for Best-1-Arm with sample complexity


−1
ln
ln
∆
O L(I, δ) + ∆−2
[2] .
[2]

−1
In other words, modulo the ∆−2
[2] ln ln ∆[2] additive term, the algorithm is instance optimal. We call
such an algorithm an almost instance optimal algorithm.

The conjectured sample complexity consists of two terms, one matching an instance-wise lower
−1
12 Hence, a
bound L(I, δ) and the other matching the optimal bound ∆−2
[2] ln ln ∆[2] for Sign-ξ.
resolution of the conjecture would provide a complete understanding of the sample complexity of
Best-1-Arm.
In fact, our proofs of Theorem 3.1 and Theorem 2.5 provide strong evidences for Conjecture E.4
and we briefly discuss the connections
Pn below.
−1
First, the third additive term i=2 ∆−2
[i] ln ln min(n, ∆[i] ) in Theorem 2.5 might appear to be
an artifact of the algorithm or the analysis at first glance. However, in light of Conjecture E.4, it is
a natural upper bound of H(I)Ent(I), as shown in the following proposition. On one extreme, the
maximum value Ent(I) can get is O(ln ln n). This can be achieved by instances in which there are
log n nonempty groups Gi and they have almost the same weight Hi . On the other extreme where
there is only a constant number of nonempty groups (i.e., the instance is clustered), Ent(I) = O(1),
and our algorithm can achieve almost instance optimality in this case. The proof of the proposition
is somewhat tedious and we defer it to the end of this section.
Proposition E.5. For any instance I, H(I)Ent(I) is upper bounded by
!
n
X
−1
∆−2
O
[i] (1 + ln ln min(n, ∆[i] )) .
i=2

In particular, Ent(I) = O(ln ln n). Moreover, for any clustered instance I, we have Ent(I) = O(1).
Besides the fact that our algorithm can achieve optimal results for both extreme cases, we have
more reasons to believe why Ent(I) should enter the picture.
Gap Entropy Ent(I): First, we motivate Ent from the algorithmic side. Consider an eliminationbased algorithms (such as [24] or our algorithm). We must ensure that the best arm is not eliminated
in any round. Recall that in the r-th round, we want to eliminate arms with gap ∆r = Θ(2−r ),
−1
which is done by obtaining an approximation of the best arm, then take O(∆−2
r ln δr ) samples
from each arm and eliminate the arms with smaller empirical means. Roughly speaking,
we need to
P
assign the failure probability δr carefully to each round (by union bound, we need r δr ≤ δ). The
algorithm in [24] use δr = O(δ · r −2 ). and our algorithm uses a better way to assign δr , based on the
information we collected P
using FractionTest. However, if one can assign δr s P
optimally (i.e., minimize
P
−1
−1
r Hr ln δr subject to
P r δr ≤ δ), one could achieve the entropy bound r Hr · (ln δ + Ent(I))
(by letting δr = δHr / i Hi ). Of course, this does not lead to an algorithm directly, as we do not
know Hi s in advance.
We also have strong evidence from our lower bound result. In fact, it is possible to extend
Theorem 3.1 in the following way. 13 We can use different Iinit (e.g. choosing a different number
12

From our previous discussion, we know it is impossible to obtain an instance optimal algorithm for 2-arm
instances, and the bound ∆−2
ln ln ∆−1
is not improvable.
[2]
[2]
13
We omit the details in this version.

34

of arms with gap 2−k for each k) and show there is a similar instance IS such that A requires at
least Ω(H(IS ) · Ent(IS )) samples. Even this does not prove an lower bound for every instance, it
strongly suggests Ω(H(I) · Ent(I)) is the right lower bound.
Now, we provide a proof of Proposition E.5.
Proof of Proposition E.5. In the following the base of log is 2. Let m denote the maximum index
i such that Gi is non-empty, and Si = |Gi |. Clearly, 4i−1 Si ≤ Hi ≤ 4i Si .
We first prove the second claim, which is straightforward. By definition, in a clustered instance,
the number of non-empty Gi is bounded by a constant C, hence the corresponding entropy is
bounded by a constant.
For the first claim, we make use of the non-negativity
of KL divergence . We construct another
P
probability
distribution
q.
Recall
that
KL(p,
q)
=
(p
log
qi−1 − pi log p−1
i
i ) ≥ 0, which implies that
P
−1
Ent(I) ≤
pi log qi .
Now, we partition all the arms into blocks. The t-th block Bt is the union of a consecutive
segment of Glt , Glt +1 , . . . , Grt . The blocks are constructed one by one starting from the first block
B1 . The t-th block Bt is
as follows: let lt = rt−1 + 1 (if t = 1, then lt = 1), and rt
Pconstructed P
be the first k such that ki=lt Si ≥ 12 · m
i=lt Si . We terminate w hen rt = m. Suppose there are h
blocks in total. Clearly h = O(log n).
Now, we define the probabilityPdistribution q.PFor eachPi such that Gi belongs
Ph to−2Bt , we let
h
rt
6
i−rt −1 ≤ 6 ·
−2
2
that m
q
=
·
t
≤ 1. In
qi = π62 · t−2 · 2i−rt −1 . NoteP
i=lt
i=1 i
t=1
t=1 t
π2
π2
m
addition, we let qm+1 = 1 − i=1 qi . Hence, q is a well defined distribution over [1, m + 1].
P
2
−1 14
Let C = log π6 . So now we only need provide an upper bound for m
i=1 Hi log qi .
m
X

Hi log qi−1 =

h X
rt
X
t=1 i=lt

i=1

Hi (2 log t + (rt − i + 1) + C).

(5)

Now, consider the following quantity U .
U=

h X
rt
X
t=1 i=lt

Hi (C + 1 +

i−1
X
j=1

4j−i+1 (i − j + 1) + 2 log t).

P
−1
of
We claim that m
i=1 Hi log qi ≤ U . We first see that the proposition

P Pis an easy consequence
Pi−1
rt
h
j−i+1
the claim. Since j=1 4
(i − j + 1) = O(1), we have U = O
i=lt Hi (1 + log t)) . Note
t=1
Pm
that t ≤ min(h,
by O( i=1 Hi (1 + log min(log n, i))), which is

P i). So U can be further bounded
n
−1
−2
exactly O
i=2 ∆[i] (1 + ln ln min(n, ∆[i] )) . Now, the only remaining task is to prove the claim.
14

For empty groups, we adopt the convention 0 log 0 = 0.

35

We first see that
rt
h X
X
t=1 i=lt

≥
≥
≥

rt
h X
X



Hi C + 1 +

i−1
X
j=1



4j−i+1 (i − j + 1) + 2 log t

Hi (C + 1 + 2 log t) +

m
X

t=1 i=lt

k=i+1

h X
rt
X

m
X

Hi (C + 1 + 2 log t) +

t=1 i=lt

h X
rt
X
t=1 i=lt

k=i+1

Hi (C + 1 + 2 log t) + 4i ·

!

Hk · 4i−k+1 (k − i + 1)

!

Sk 4k−1 · 4i−k+1 (k − i + 1)

m
X

k=i+1

!

Sk (k − i + 1)

(6)

P
For each i such that lt ≤ i < rt , by the construction of the blocks, we have Si ≤ m
j=rt Sj . So
Pm
Pm
i
i
i
we have 4
k=rt Sk (rt − i + 1) ≥ 4 Si (rt − i + 1) ≥ Hi (rt − i + 1). Hence,
k=rt Sk (k − i + 1) ≥ 4
each term in (6) is no less than the corresponding term in (5). (It is trivially true for i = rt ). This
concludes the proof.

F
F.1

Missing Proofs in Section B
Proof for Lemma B.3

Lemma B.3 (restated) Suppose ε < 0.1 and t ∈ (ε, 1 − ε). With probability 1 − δ, the following
hold:
• If FractionTest outputs True, then |S >cr | < (1 − t + ε)|S| (or equivalently |S ≤cr | > (t − ε)|S|).
• If FractionTest outputs False, then |S <cl | < (t + ε)|S| (or equivalently |S ≥cl | > (1 − t − ε)|S|).
Moreover the number of samples taken by the algorithm is O(ln δ−1 ε−2 ∆−2 ln ε−1 ), in which ∆ =
cr − cl .
Proof of Lemma B.3. Let Sa = S <cl , Sb = S >cr , Na = |Sa |, Nb = |Sb |, N = |S|. For each iteration
i and the arm ai in line 4, by Lemma B.1, we have Pr[|µ̂[ai ] − µ[ai ] | ≥ (cr − cl )/2] ≤ ε/3. Hence, if
r
r
µ[ai ] < cl , then Pr[µ̂[ai ] < cl +c
if µ[ai ] > cr , then Pr[µ̂[ai ] < cl +c
2 ] ≥ 1 − ε/3. Similarly,
2 ] ≤ ε/3.

r
. Clearly Xi s are i.i.d. From the
Let Xi be the indicator Boolean variable 1 µ̂[ai ] < cl +c
2
Ptot
algorithm, we can see that cnt = i=1 Xi . Let E = E[Xi ]. Let Ê = cnt/tot, which is the empirical
value of E. By Chernoff bound, we can easily get that Pr[|E − Ê| ≥ ε/3] ≤ δ.
In the rest of the proof, we condition on the event that |E − Ê| < ε/3, which happens with
probability at least 1 − δ. Suppose Ê > t. Then we have E > t − ε/3. It is also easy to see that:

X 
cl + cr
E ·N =
Pr µ̂[a] <
≤ (N − Nb ) · 1 + (ε/3)Nb = N − (1 − ε/3)Nb ,
2
a∈S

36

as ε < 0.1,

1
1−ε/3

Nb ≤

< (1 + 2ε/3). So, we have proved the first claim:

(1 − E)N
(1 − t + ε/3)N
≤
< (1 − t + ε/3)(1 + 2ε/3)N ≤ (1 − t + ε)N.
1 − ε/3
1 − ε/3

The second claim is completely symmetric. Suppose Ê ≤ t. Then we have E ≤ t + ε/3. We
also have E · N ≥ Na (1 − ε/3). So,
Na ≤

E·N
(t + ε/3)N
≤
< (t + ε/3)(1 + 2ε/3)N ≤ (t + ε)N.
1 − ε/3
1 − ε/3

Finally, the upper bound for the number of samples can be verified by a direct calculation.

F.2

Proof for Lemma B.4

Lemma B.4 (restated) Suppose δ < 0.1. Let S ′ = Elimination(S, cl , cr , δ). Let A1 be the best arm
among S, with mean µ[A1 ] ≥ cr . Then with probability at least 1 − δ, the following statements hold
1. A1 ∈ S ′

(the best arm survives);

2. |S ′≤cl | < 0.1|S ′ |

(only a small fraction of arms have means less than cl );

3. The number of samples is O(|S| ln δ−1 ∆−2 ), in which ∆ = cr − cl .
Note that with probability at most δ, there is no guarantee for any of the above statements.
Before proving Lemma B.4, we first describe two events (which happen with high probability)
that we condition on, in order to simplify the argument.
Lemma F.1. With probability at least 1 − δ/2, it holds that in all round r, FractionTest outputs
m
correctly, and |µ̂[A1 ] − µ[A1 ] | < cr −c
2 .
Proof. Fix a round r. FractionTest outputs incorrectly with probability at most δr . By Theorem B.1,
m
Pr(|µ̂[A1 ] − µ[A1 ] | ≥ cr −c
2 ) ≤ δr .
P
P+∞
r
The lemma follows from a simple union bound over all rounds: 2 +∞
r=1 δr ≤ 2δ
r=1 0.1/2 ≤
δ/2.
Lemma F.2. Let Nr = |Sr≤cm |. Then with probability at least 1 − δ/2, for all rounds r in which
Algorithm 4 does not terminate, Nr+1 ≤ 14 Nr .
m
Proof. Suppose a ∈ Sr≤cm . By Theorem B.1, we have that Pr[|µ̂[a] − µ[a] | ≥ cr −c
2 ] ≤ δr . So
cm +cr
Pr[µ̂[a] > 2 ] ≤ δr . Then, we can see that E[Nr+1 ] ≤ δr Nr . By Markov inequality, we can see
Nr
that Pr(Nr+1 > 14 Nr ) ≤ δ1rN
= 4δr .
4 r
P
P+∞
r
Again, the lemma follows by a simple union bound: +∞
r=1 4δr ≤ 4δ
r=1 0.1/2 ≤ δ/2.

Proof of Lemma B.4. With probability at least 1−δ, both statements in Lemma F.1 and Lemma F.2
hold. Let that event be EG . Now we prove Lemma B.4 under the condition that EG holds. Now we
prove all the claims one by one.
Consider the first claim. Note that for all r, conditioning on EG , we have that |µ̂[A1 ] − µ[A1 ] | <
cr −cm
cr −cm
= cm2+cr . Hence, A1 survives all rounds and A1 ∈ S ′ .
2 , or equivalently µ̂[A1 ] > cr −
2
37

For the second claim, we note that, conditioning on event EG , FractionTest always outputs correctly. Suppose the algorithm terminates at round r, which means FractionTest(Sr , cl , cm , δr , 0.075, 0.025)
outputs False. By Lemma B.3, we have |Sr<cl | < (0.075 + 0.025)|Sr | = 0.1|Sr |. Since S ′ = Sr , the
claim clearly follows.
Now, we prove the last claim. Again we condition on EG . Suppose the algorithm does not terminate at round r, which means FractionTest(Sr , cl , cm , δr , 0.075, 0.025) outputs True. By Lemma B.3,
we know Nr = |Sr≤cm | > (0.075 − 0.025)|Sr | = 0.05|Sr |. Then, we have that
3
|Sr+1 | ≤ |Sr | − (|Nr | − |Nr+1 |) ≤ |Sr | − |Nr | ≤ 0.99|Sr |.
4
′
Suppose the algorithm terminates at round r . Let c1 be a large enough constant (so that
c1 ln δr ∆−2 |Sr | is an upper bound for the samples taken by UniformSample in round r and c1 ln δr ∆−2
is an upper bound for the samples taken by FractionTest in round r). Then, the number of samples
is bounded by:
′

′

r
X
r=1

c1 (∆

−2

ln δr |Sr | + ∆

−2

ln δr ) ≤ 2c1 |S|∆

−2

≤ 2c1 |S|∆

−2

≤ 2c1 |S|∆

−2

r
X
(ln δ−1 + r ln 2 + ln 10) · 0.99r−1
r=1
′

r
X
(ln δ−1 (r + 1) + ln 10) · 0.99r−1
r=1

ln δ

−1

+∞
+∞
X
X
r−1
ln 10 · 0.99r−1
(r + 1) · 0.99
+
r=1


≤ 2c1 |S|∆−2 ln δ−1 · 10100 + 100 · ln 10

r=1

!

So the number of samples is O(|S| ln δ−1 ∆−2 ), which concludes the proof of the lemma.

F.3

Proofs for Lemma B.16, Lemma B.17 and Lemma B.18

For convenience, we let
Sr=r = U r ∩ Sr , Sr>r = U ≥r+1 ∩ Sr , Ncur = |Sr=r |, Nbig = |Sr>r |.
Then we have |Sr | = Ncur + Nbig + Nsma + 1. Also, recall that ls = ln(min(hI , s)).
In order to prove these three lemmas, we need an important inequality for Pr . If r ≤ maxs , we
have:
!
+∞
X
s
−1
Pr − Pr+1 = c2 ·
(ln δ−1 + ls ) · ε−2
+ lmaxs ) · ε−2
r |U | + (ln δ
r
≥ c2 ·

≥ c2 ·

s=r
−2
εr (ln δ−1
−1
ε−2
r (ln δ

+ lr )(|U ≥r | + 1)

+ lr )(Ncur + Nbig + 1).

(7)

Lemma B.16 (restated) When MedianElim (line 8) returns an εr /4-approximation of the best arm
A1 , and FractionTest outputs True. The expected number of samples taken at and after round r is
bounded by
−1
ε−2
+ lr )c3 Nsma + Pr .
r (ln δ
38

Proof of Lemma B.16. Since by Lemma B.11, we have |U ≤r ∩ Sr+1 | ≤ 0.1|Sr+1 |, which means
|U ≥r+1 ∩ Sr+1 | + 1 ≥ 0.9|Sr+1 |. So, we have that
|U ≤r ∩ Sr+1 | ≤

1
1
(|U ≥r+1 ∩ Sr+1 | + 1) ≤ (Nbig + 1).
9
9

Therefore, we can see the number of samples is bounded by:


1
−2
−1
c3 · |Sr |εr (ln δ + lr ) + T r + 1, (Nbig + 1) ,
9
where the first additive term is the number of samples in this round, and is bounded by Lemma B.15.
By the induction hypothesis, we have:


1
T r + 1, (Nbig + 1)
9
1
≤(ln δ−1 + lr+1 ) · c1 · (Nbig + 1) · ε−2
r+1 + Pr+1
9
1
−1
≤(ln δ−1 + lr+1 ) · c1 · (Nbig + 1) · ε−2
+ lr )(Nbig + Ncur + 1)ε−2
(By (7))
r
r+1 + Pr − c2 · (ln δ
9


5
5
≤(ln δ−1 + lr ) · ε−2
c1 Nbig + c1 − c2 Ncur − c2 Nbig − c2 + Pr
r
9
9
Therefore, we can bound the expected number of samples by:


5
5
−2
−1
εr (ln δ + lr ) c3 · |Sr | + c1 Nbig + c1 − c2 Ncur − c2 Nbig − c2 + Pr
9
9


5
5
−2
−1
≤εr (ln δ + lr ) (c3 − c2 )Ncur + (c3 + c1 − c2 )Nbig + c3 Nsma + c1 + c3 − c2 + Pr
9
9
−1
≤ε−2
+ lr )c3 Nsma + Pr
r (ln δ

( 59 c1 + c3 − c2 < 0 , c3 + 59 c1 − c2 < 0)

In the first inequality, we use the fact that |Sr | = Ncur + Nbig + Nsma + 1.
Lemma B.17 (restated) When MedianElim (line 8) returns an εr /4-approximation of the best arm
A1 , and FractionTest outputs False. The expected number of samples taken at and after round r is
bounded by Pr .
Proof of Lemma B.17. By Lemma B.11, we can see |U ≥r ∩ Sr | + 1 = Ncur + Nbig + 1 > 0.5|Sr |. So
Nsma < 0.5|Sr |, thus
Ncur + Nbig + 1 ≥ Nsma .
We can see that the total number of samples is bounded by:
−1
+ lr )c3 · |Sr |ε−2
c3 · |Sr |ε−2
r + T (r + 1, Nsma + Ncur ).
r + T (r + 1, Nsma + Ncur ) ≤ (ln δ

39

(8)

In the above, the first term is due to the number of samples in this round by Lemma B.15. The
second term is an upper bound for the number of samples starting at round r + 1. Since we do not
eliminate any arm in this case, we have |U ≤r ∩ Sr+1 | ≤ Nsma + Ncur .
From the induction hypothesis, we have:
T (r + 1, Nsma + Ncur )
≤(ln δ−1 + lr+1 ) · c1 · (Nsma + Ncur ) · ε−2
r+1 + Pr+1

−1
≤(ln δ−1 + lr ) · c1 · 5(Nsma + Ncur ) · ε−2
+ lr )(Nbig + Ncur + 1)ε−2
r + Pr − c2 · (ln δ
r

(By (7))

≤(ln δ−1 + lr )(5c1 Nsma + 5c1 Ncur − c2 Ncur − c2 Nbig − c2 )ε−2
r + Pr

Plugging it into the bound, we have the following bound for the expected number of samples:
−1
(ln δ−1 + lr )c3 · |Sr |ε−2
+ lr )(5c1 Nsma + 5c1 Ncur − c2 Ncur − c2 Nbig − c2 ) · ε−2
r + (ln δ
r + Pr

≤(ln δ−1 + lr )((5c1 + c3 )Ncur + c3 Nbig + c3 + (5c1 + c3 )Nsma − c2 (Ncur + Nbig + 1)) · ε−2
r + Pr

≤(ln δ−1 + lr )(c3 Nbig + c3 + (5c1 + c3 )Ncur − (c2 − 5c1 − c3 )(Ncur + Nbig + 1)) · ε−2
r + Pr

≤Pr

(c2 − 5c1 − c3 > 5c1 + c3 > c3 )

In the second inequality, we use the fact that (5c1 + c3 )Nsma ≤ (5c1 + c3 )(Ncur + Nbig + 1) due to
(8).
Lemma B.18 (restated) When MedianElim (line 8) returns an arm which is not an εr /4-approximation
of the best arm A1 . The expected number of samples taken at and after round r is bounded by
≤ (ln δ−1 + lr )(c3 + 5c1 ) · Nsma ε−2
r + Pr .

Proof of Lemma B.18. In this case, we can simply bound it by:
−1
c3 · |Sr |ε−2
+ lr ) + T (r + 1, Nsma + Ncur ).
r (ln δ

The first term is still due to the number of samples in this round by Lemma B.15. The second term
is an upper bound for the samples taken starting at round r + 1, since |U ≤r ∩ Sr+1 | ≤ Nsma + Ncur
in any case. Then, we have that
−1
c3 · |Sr |ε−2
+ lr ) + T (r + 1, Nsma + Ncur )
r (ln δ

−2
−2
≤(ln δ−1 + lr )(c3 (Nsma + Ncur + Nbig + 1)ε−2
r + 5c1 (Nsma + Ncur )εr − c2 εr (Nbig + Ncur + 1)) + Pr
(By (7))

≤(ln δ−1 + lr )((c3 + 5c1 − c2 )Ncur + (c3 − c2 )Nbig + (c3 + 5c1 )Nsma + c3 − c2 )ε−2
r + Pr
Since c3 + 5c1 − c2 ≤ 0 and c3 − c2 ≤ 0, we have the following bound for the expected number
of samples:
(ln δ−1 + lr )(c3 + 5c1 ) · Nsma ε−2
r + Pr

40

G

More About Sign-ξ

In this section, we present a class of δ-correct algorithms for Sign-ξ which needs o(∆−2 ln ln ∆−1 )
samples for infinite number of instances. In particular, we show the following stronger result.
Theorem G.1. For any function T on (0, 1] such that lim sup∆→+0 T (∆)∆2 = +∞ and for any
fixed constant δ > 0, there exists a δ-correct algorithm A for Sign-ξ, such that
lim inf
∆→+0

TA (∆)
= 0.
T (∆)

Now, we begin our description of the algorithm, which is in fact a simple variant of the ExpGapElim algorithm in [24]. Our algorithm takes an infinite sequence S = {Λi }+∞
i=1 as input, which
we call the reference sequence.
Definition G.2. We say an infinite sequence S = {Λi }+∞
i=1 is a reference sequence if the following
statements hold:
1. 0 < Λi < 1, for all i.
2. There exists a constant 0 < c < 1 such that for all i, Λi+1 ≤ c · Λi .
Our algorithm TestSign takes a confidence level δ and the reference sequence {Λi } as input. It
runs in rounds. In the rth round, the algorithm takes a number of samples (the actual number
depends on r, and can be found in Algorithm 6) from the arm and let µ
br be the empirical mean. If
µ
br ∈ ξ ± Λr /2, we decide that the gap ∆ is smaller than the reference gap Λr and we should proceed
to the next round with a smaller reference gap. If µ
br is larger than ξ + Λr /2, we decide µ > ξ. If
r
µ
b is smaller than ξ − Λr /2, we decide µ < ξ. The pseudocode can be found in algorithm 6.
Algorithm 6: TestSign(A, δ, {Λi })
Data: The single arm A with unknown mean µ 6= ξ, confidence level δ, the reference
sequence {Λi }.
Result: Whether µ > ξ or µ < ξ.

1
2
3
4
5
6
7
8
9
10

for r = 1 to +∞ do
εr = Λr /2
δr = δ/10r 2
Pull A for tr = 2 ln(2/δr )/ε2r times. Let µ
br denote its average reward.
r
if µ
b > ξ + εr then
Return µ > ξ
if µ
br < ξ − εr then
Return µ < ξ

The algorithm can achieve the following guarantee. The proof is somewhat similar to the
analysis of the ExpGapElim algorithm in [24] (in fact, simpler since there is only one arm).
Lemma G.3. Fix a confidence level δ > 0 and an arbitrary reference sequence S = {Λi }∞
i=1 .
Suppose that the given instance has a gap ∆. Let κ be the smallest i such that Λi ≤ ∆. With
probability at least 1− δ, TestSign determines whether µ > ξ or µ < ξ correctly and uses O((ln δ−1 +
ln κ)Λ−2
κ ) samples in total.
41

Proof. For any round r, by Hoeffding’s inequality (Lemma A.2), we have that
Pr (|b
µr − µ| ≥ εr ) ≤ 2 exp(−ε2r /2 · tr ) = δr .
(9)
P+∞
P+∞
Then, by a union bound, with probability 1 − i=1 δr = 1 − δ · i=1 1/10r 2 ≥ 1 − δ, we have
|b
µr − µ| < εr for all r. Denote this event by E. Then we prove that conditioning on E, Algorithm 6
is correct.
Let k be the round the algorithm returns the answer. By the definition of κ, we know that
Λκ ≤ ∆. Then on round κ, we have |b
µκ − µ| < Λκ /2 ≤ ∆/2. Thus, |b
µκ − ξ| ≥ |µ − ξ| − |b
µκ − µ| >
∆/2 ≥ εr . Therefore, we can see that k ≤ κ, which shows that the algorithm terminates on or
before round κ. On round k, if we have µ
bk > ξ + εr , we must have µ > ξ since |b
µk − µ| < εr . The
case µ
bk < ξ − εr is completely symmetric, which proves the correctness.
Now, we analyze the number of samples. It is easy to see that the total number of samples is
at most:
κ
κ
X
X
8 ln(2/δr )/Λ2r .
tr =
r=1

r=1

By the definition of the reference sequence, Λr ≥ cr−κ Λκ for 1 ≤ r ≤ κ. Hence, we have that
κ
X

8(ln δ

−1

+ ln 20 +

ln r)/Λ2r

r=1

≤

Λ−2
κ

κ
X

c2(κ−r) · 8(ln δ−1 + ln 20 + ln r)

r=1
−1

= O (ln δ

This finishes the proof of the theorem.

+ ln κ)Λ−2
κ



Finally, we prove Theorem G.1.
Proof of Theorem G.1. First, we can easily construct a reference sequence {Λi } such that
1. 0 < Λi < 1 and Λi+1 ≤ Λi /2 for all i.
for all i (this is possible since lim sup∆→+0 T (∆)/∆−2 = +∞).
2. T (Λi ) ≥ i · Λ−2
i
With this reference sequence, we can see that with probability 1 − δ, the algorithm outputs the
correct answer and runs in O(ln δ−1 +ln κ)Λ−2
κ time. However, there is a subtlety here: the expected
running time is not bounded since we do not have a bound with probability δ (when the good event
E in Lemma G.3 does not happen). In Theorem H.5, we provide a general transformation that
can produce a δ-correct algorithm whose expected running time is O(ln δ−1 + ln κ)Λ−2
κ . Let the
algorithm be A.
For any fixed δ, we can see that
C(ln δ−1 + ln i)Λ−2
TA (Λi )
i
= 0,
≤ lim
i→+∞ T (Λi )
i→+∞
iΛ−2
i
lim

where C is some large constant. This implies that lim inf ∆→+0 TA (∆)/T (∆) = 0.
Remark G.4. If we use the reference sequence {Λi = e−i }, we have an δ-correct algorithm for
Sign-ξ, and it takes O(∆−2 (ln δ−1 + ln ln ∆−1 )) samples in expectation on instance with gap ∆.
Remark G.5. Recall Farrell’s (worse case) lower bound (1) is Ω(∆−2 ln ln ∆−1 ). Together with
Theorem G.1, they imply that it is impossible to obtain an instance optimal algorithm for Sign-ξ.
42

δ-correct Algorithms and Parallel Simulation

H

In Corollary B.19, we show that our algorithm can output the correct answer with probability at
least 1− δ, and the conditional expected running time is upper bounded. However, with probability
δ, there is no guarantee on its behavior (e.g., it could potentially run forever). 15 Hence, the
expected running time may be unbounded. It is preferable to have an algorithm with a bounded
expected running time, and being correct with probability at least 1 − δ. In this section, we provide
such a transformation that given an algorithm for the former kind, produces one of the later (the
time bound only increases by a constant factor).
Now, we formally define the two kinds of algorithms.
Definition H.1. Let A be an algorithm for some problem P. A takes an additional input δ as the
confidence level. Let I be the set of all valid instances for P. We write Aδ to denote the algorithm
A with a fixed confidence level δ.
1. We call A an expected-T -time δ-correct algorithm iff there exists δ0 ∈ (0, 1) such that for any
δ ∈ (0, δ0 ) and instance I ∈ I:
TAδ [I] ≤ T (δ, I)

and

Pr[Aδ returns the correct answer on I] ≥ 1 − δ.

2. We call A a weakly expected-T -time δ-correct algorithm iff there exists δ0 ∈ (0, 1) such that
for any δ ∈ (0, δ0 ) and instance I ∈ I, there exists an event E that
PrAδ ,I [E] ≥ 1−δ∧EAδ ,I [τ | E] ≤ T (δ, I) and Pr[Aδ returns the correct answer on I | E] = 1.
We call the above event E a good event.
We need a mild assumption on the running times for our general transformation.
Definition H.2. We say a function T : (0, 1) × I → R is a reasonable time bound, if there exists
0 < δ0 < 1 such that for all 0 < δ′ < δ < δ0 and I ∈ I we have that
T (δ′ , I) ≤

ln δ′−1
T (δ, I).
ln δ−1

Remark H.3. The running times of most previous algorithms are of the form α(I) + β(I) ln δ−1 ,
where α and β only depend on I (e.g., see Table 1). Such running time bounds are obviously
reasonable.
Suppose A is a weakly expected-T -time δ-correct algorithm. Our strategy to produce a expectedO(T )-time δ-correct algorithm is to simulate many copies of A with different confidence levels. Now
we formally define the parallel simulation method. Suppose we have a class of algorithms {Ai }
(possibly infinite) for the same problem P. We want to construct a new algorithm B for problem P
which simulates {Ai } in a parallel fashion. The details of the construction are specified as follows.
15

Many previous algorithms for pure exploration multi-armed bandits belong to this kind, such as [13, 24, 16].
Some previous work has noticed the issue as well, but we are not aware of a systematic way to deal with it. For
example, [23] stated that “However, their (i.e., [13]) elimination algorithm could incur high sample complexity on
the δ-fraction of the runs on which mistakes are made—we think it unlikely that elimination algorithms can yield an
expected sample complexity bound smaller than ... ”.

43

Definition H.4. (Parallel Simulation) The new algorithm B simulates Ai with rate ri ∈ N+ , for
all i. More specifically, B runs in rounds. In the r-th round, B simulates each algorithm Ai such
that ri divides r (i.e., ri |r) for one step. If there are more than one such algorithms, B simulates
them in the increasing order of their indices. If any such Ai requires a sample, B takes a fresh
sample and feeds it to Ai .
B terminates whenever any Ai terminates and B outputs what Ai outputs. We denote this new
algorithm as B = SIM({Ai }, {ri }).
Now we prove the main result of this section.
Theorem H.5. Suppose T is a reasonable time bound. If A is a weakly expected-T -time δ-correct
algorithm for the problem P, then there exists an algorithm B which is expected-O(T )-time δ-correct.
Moreover, B can be constructed explicitly from A.
Proof. The construction of B is very simple: Let Bδ = SIM({Ai }, {ri }), in which Ai = Aδ/2i (that
is algorithm A with confidence parameter δ/2i ) and ri = 2i .
Now we prove B is an expected-O(T )-time δ-correct algorithm for problem P. Suppose the
given instance is I. Let Ei be a good event for Ai on instance I.
First, by a simpleP
union bound, we can see that the probability that Bδ outputs the correct
i
answer is at least 1 − +∞
i=1 δ/2 = 1 − δ (Bδ returns the correct answer if all Ai returns the correct
answer).
Now, assume δ < δ0′ = min(0.1, δ0 ). Let us analyze the running time of Bδ on instance I.
For ease of argument, we can think that B executes in a slight different way. B does not
terminate the same way as before, but keeps simulating all algorithms until all of them terminate
(or run forever). The output of B is still the same as the Ai that terminates first, and the running
time of B is determined by the first terminated Ai .
Partition this probability space into disjoint events {Fi }, in which Fi is the event that all events
Ej with j < i do not happen, and Ei happens. Note that {Fi } is indeed a partition of the probability
space (Pr[∪i Fi ] = 1). This is simply because limi→+∞ Pr[Ei ] ≥ limi→+∞ 1 − δ/2i = 1.
Let τ be the running time of B. Since each Ai uses its own independent samples, we have that
EAi ,I [τ | Fi ] = EAi ,I [τ | Ei ] ≤ T (δ/2i , I).
Moreover, for Ai to run one step, for any j 6= i, Aj runs at most 2i−j steps. Thus, the running time
for Bδ conditioning on Fi is bounded by:
EBδ ,I [τ | Fi ] ≤ T (δ/2i , I) ·

+∞
X
j=1

2i−j ≤ T (δ/2i , I) · 2i .

Furthermore, by the independence of different Ai s, we note that
Pr[Fi ] ≤

i−1
Y

k=1

δ/2k ≤ δi−1 .

44

Now, we can bound the expected running time of B as follows:
EBδ ,I [τ ] =
≤

+∞
X

i=1
+∞
X

Pr[Fi ] · EA′δ ,I [τ | Fi ]
δi−1 · T (δ/2i , I) · 2i .

i=1
+∞
X

≤2

≤2
≤2

i=1
+∞
X

i=1
+∞
X
i=1

(2δ)i−1 · T (δ, I)



ln δ−1 + i ln 2
ln δ−1



.

(2δ)i−1 (1 + i) · T (δ, I).
(0.2)i−1 (1 + i) · T (δ, I).

≤ 6T (δ, I).
In the second inequality, we use the fact that T is a reasonable time bound. To summarize, we can
see that B is an expected-O(T )-time δ-correct algorithm.

45

