Journal of Machine Learning Research 5 (2004) 623-648 Submitted 1/04; Published 6/04

The Sample Complexity of Exploration in the Multi-Armed Bandit Problem

Shie Mannor shie@mit.edu

John N. Tsitsiklis jnt@mit.edu

Laboratory for Information and Decision Systems Massachusetts Institute of Technology Cambridge, MA 02139, USA

Editors: Kristin Bennett and Nicolò Cesa-Bianchi

Abstract

We consider the multi-armed bandit problem under the PAC (“probably approximately correct”) model. It was shown by Even-Dar et al. (2002) that given n arms, a total of O((n/ϵ^{2})log(1/δ)) trials suffices in order to find an ϵ-optimal arm with probability at least 1 − δ. We establish a matching lower bound on the expected number of trials under any sampling policy. We furthermore generalize the lower bound, and show an explicit dependence on the (unknown) statistics of the arms. We also provide a similar bound within a Bayesian setting. The case where the statistics of the arms are known but the identities of the arms are not, is also discussed. For this case, we provide a lower bound of Θ((1/ϵ^{2})(n + log(1/δ))) on the expected number of trials, as well as a sampling policy with a matching upper bound. If instead of the expected number of trials, we consider the maximum (over all sample paths) number of trials, we establish a matching upper and lower bound of the form Θ((n/ϵ^{2})log(1/δ)). Finally, we derive lower bounds on the expected regret, in the spirit of Lai and Robbins.

1. Introduction

The multi-armed bandit problem is a classical problem in decision theory. There is a number of alternative arms, each with a stochastic reward whose probability distribution is initially unknown. We try these arms in some order, which may depend on the sequence of rewards that have been observed so far. A common objective in this context is to find a policy for choosing the next arm to be tried, under which the sum of the expected rewards comes as close as possible to the ideal reward, i.e., the expected reward that would be obtained if we were to try the “best” arm at all times. One of the attractive features of the multi-armed bandit problem is that despite its simplicity, it encompasses many important decision theoretic issues, such as the tradeoff between exploration and exploitation.

The multi-armed bandit problem has been widely studied in a variety of setups. The problem was first considered in the 50’s, in the seminal work of Robbins (1952), which derives policies that asymptotically attain an average reward that converges in the limit to the reward of the best arm. The multi-armed bandit problem was later studied in discounted, Bayesian, Markovian, expected reward, and adversarial setups. See Berry and Fristedt (1985) for a review of the classical results on the multi-armed bandit problem.

\begin{matrix}c \\ ◯ \end{matrix} 2004 Shie Mannor and John Tsitsiklis.

Mannor and Tsitsiklis

Lower bounds for different variants of the multi-armed bandit have been studied by several authors. For the expected regret model, where the regret is defined as the difference between the ideal reward (if the best arm were known) and the reward under an online policy, the seminal work of Lai and Robbins (1985) provides asymptotically tight bounds in terms of the Kullback-Leibler divergence between the distributions of the rewards of the different arms. These bounds grow logarithmically with the number of steps. The adversarial multi-armed bandit problem (i.e., without any probabilistic assumptions) was considered in Auer et al. (1995, 2002b), where it was shown that the expected regret grows proportionally to the square root of the number of steps. Of related interest is the work of Kulkarni and Lugosi (2000) which shows that for any specific time t, one can choose the reward distributions so that the expected regret is linear in t.

The focus of this paper is the classical multi-armed bandit problem, but rather than looking at the expected regret, we are concerned with PAC-type bounds on the number of steps needed to identify a near-optimal arm. In particular, we are interested in the expected number of steps that are required in order to identify with high probability (at least 1 − δ) an arm whose expected reward is within ϵ from the expected reward of the best arm. This naturally abstracts the case where one must eventually commit to one specific arm, and quantifies the amount of exploration necessary. This is in contrast to most of the results for the multi-armed bandit problem, where the main aim is to maximize the expected cumulative reward while both exploring and exploiting. In Even-Dar et al. (2002), a policy, called the median elimination algorithm, was provided which requires O((n/ϵ^{2})log(1/δ)) trials, and which finds an ϵ-optimal arm with probability at least 1 − δ. A matching lower bound was also derived in Even-Dar et al. (2002), but it only applied to the case where δ > 1/n, and therefore did not capture the case where high confidence (small δ) is desired. In this paper, we derive a matching lower bound which also applies when δ > 0 is arbitrarily small.

Our main result can be viewed as a generalization of a O((1/ϵ^{2})log(1/δ))lower bound provided in Anthony and Bartlett (1999), and Chernoff (1972), for the case of two bandits. The proof in Anthony and Bartlett (1999) is based on a hypothesis interchange argument, and relies critically on the fact there are only two underlying hypotheses. Furthermore, it is limited to “nonadaptive” policies, for which the number of trials is fixed a priori. The technique we use is based on a likelihood ratio argument and a tight martingale bound, and applies to general policies.

Exploration in Multi-Armed Bandits

A different type of lower bound was derived in Auer et al. (2002b) for the expected regret in an adversarial setup. The bounds derived there can also be used to derive a lower bound for our problem, but do not appear to be tight enough to capture the log(1/δ) dependence on δ. Our work also provides fundamental lower bounds in the context of sequential analysis (see, e.g., Chernoff, 1972; Jennison et al., 1982; Siegmund, 1985). In the language of Siegmund (1985), we provide a lower bound on the expected length of a sequential sampling policy under any adaptive allocation scheme. For the case of two arms, it was shown in Siegmund (1985) (p. 148) that if one restricts to sampling policies that only take into account the empirical average rewards from the different arms, then the problems of inference and arm selection can be treated separately. As a consequence, and under this restriction, Siegmund (1985) shows that an optimal allocation cannot be much better than a uniform one. Our results are different in a number of ways. First, we consider multiple hypotheses (multiple arms). Second, we allow the allocation rule to be completely general and to depend on the whole history. Third, unlike most of the sequential analysis literature (see, e.g., Jennison et al., 1982), we do not restrict ourselves to the limiting case where the probability of error converges to zero. Finally, we consider finite time bounds, rather than asymptotic ones. We further comment that our results extend those of Jennison et al. (1982), in that we consider the case where the reward is not Gaussian.

Paper Outline

The paper is organized as follows. In Section 2, we set up our framework, and since we are mainly interested in lower bounds, we restrict to the special case where each arm is a “coin,” i.e., the rewards are Bernoulli random variables, but with unknown parameters (“biases”). In Section 3, we provide a O((n/ϵ^{2})log(1/δ)) lower bound on the expected number of trials under any policy that finds an ϵ-optimal coin with probability at least 1 − δ. In Section 4, we provide a refined lower bound that depends explicitly on the specific (though unknown) biases of the coins. This lower bound has the same log(1/δ) dependence on δ; furthermore, every coin roughly contributes a factor inversely proportional to the square difference between its bias and the bias of a best coin, but no more that 1/ϵ^{2}. In Section 5, we derive a lower bound similar to the one in Section 3, but within a Bayesian setting, under a prior distribution on the set of biases of the different coins.

In Section 6 we provide a bound on the expected regret which is similar in spirit to the bound in Lai and Robbins (1985). The constants in our bounds are slightly worse than the ones in Lai and Robbins (1985), but the different derivation, which links the PAC model to regret bounds, may be of independent interest. Our bound holds for any finite time, as opposed to the asymptotic result provided in Lai and Robbins (1985).

The case where the coin biases are known in advance, but the identities of the coins are not, is discussed in Section 7. We provide a policy that finds an ϵ-optimal coin with probability at least 1 − δ, under which the expected number of trials is O((1/ϵ^{2})(n + log(1/δ))). We show that this bound is tight up to a multiplicative constant. If instead of the expected number of trials, we consider the maximum (over all sample paths) number of trials, we establish a matching upper and lower bounds of the form Θ((n/ϵ^{2})log(1/δ)). Finally, Section 8 contains some brief concluding remarks.

2. Problem Definition

The exploration problem for multi-armed bandits is defined as follows. We are given n arms. Each arm ℓ is associated with a sequence of identically distributed Bernoulli (i.e., taking values in {0,1}) random variables X_{k}^{ℓ}, k = 1,2,..., with unknown mean p_{ℓ}. Here, X_{k}^{ℓ} corresponds to the reward obtained the kth time that arm ℓ is tried. We assume that the random variables X_{k}^{ℓ}, for ℓ = 1,...,n, k = 1,2,..., are independent, and we define p = (p_{1},...,p_{n}). Given that we restrict to the Bernoulli case, we will use in the sequel the term “coin” instead of “arm.”

A policy is a mapping that given a history, chooses a particular coin to be tried next, or selects a particular coin and stops. We allow a policy to use randomization when choosing the next coin to be tried or when making a final selection. However, we only consider policies that are guaranteed to stop with probability 1, for every possible vector p. (Otherwise, the expected number of steps would be infinite.) Given a particular policy, we let P_{p} be the corresponding probability measure (on the natural probability space for this model). This probability space captures both the randomness in the coins (according to the vector p), as well as any additional randomization carried out by the policy. We introduce the following random variables, which are well defined, except possibly on the set of measure zero where the policy does not stop. We let T_{ℓ} be the total number of times that coin ℓ is tried, and let T = T_{1}+··· +T_{n} be the total number of trials. We also let I be the coin which is selected when the policy decides to stop.

We say that a policy is (ϵ,δ)-correct if

P_{p}( p_{I} > max_{ℓ}p_{ℓ}− ϵ) ≥ 1 − δ,

for every p ∈ [0,1]^{n}. It was shown in Even-Dar et al. (2002) that there exist constants c_{1} and c_{2} such that for every n, ϵ > 0, and δ > 0, there exists an (ϵ,δ)-correct policy under which

E_{p}[T] ≤ c_{1} \frac{n}{ϵ^{2}} log \frac{c_{2}}{δ}, ∀ p ∈ [0,1]^{n}.

A matching lower bound was also established in Even-Dar et al. (2002), but only for “large” values of δ, namely, for δ > 1/n. In contrast, we aim at deriving bounds that capture the dependence of the sample-complexity on δ, as δ becomes small.

3. A Lower Bound on the Sample Complexity

We start with our central result, which can be viewed as an extension of Lemma 5.1 from Anthony and Bartlett (1999), as well as a special case of Theorem 5. We present it here because it admits a simpler proof, but also because parts of the proof will be used later. Throughout the rest of the paper, log will stand for the natural logarithm.

Theorem 1 There exist positive constants c_{1}, c_{2}, ϵ_{0}, and δ_{0}, such that for every n ≥ 2, ϵ ∈ (0,ϵ_{0}), and δ ∈ (0,δ_{0}), and for every (ϵ,δ)-correct policy, there exists some p ∈ [0,1]^{n} such that

E_{p}[T] ≥ c_{1} \frac{n}{ϵ^{2}} log \frac{c_{2}}{δ}.

In particular, ϵ_{0} and δ_{0} can be taken equal to 1/8 and e^{−4} /4, respectively.

Proof Let us consider a multi-armed bandit problem with n + 1 coins, which we number from 0 to n. We consider a finite set of n + 1 possible parameter vectors p, which we will refer to as “hypotheses.” Under any one of the hypotheses, coin 0 has a known bias p_{0} = (1+ϵ)/2. Under one hypothesis, denoted by H_{0}, all the coins other than zero have a bias of 1/2,

H_{0} : p_{0} = \frac{1}{2} + \frac{ϵ}{2}, p_{i} = \frac{1}{2}, for i ≠ 0,

which makes coin 0 the best coin. Furthermore, for ℓ = 1,...,n, there is a hypothesis

H_{ℓ}: p_{0} = \frac{1}{2} + \frac{ϵ}{2},  p_{ℓ} = \frac{1}{2} + ϵ,  p_{i} = \frac{1}{2}, for i ≠ 0,ℓ,

which makes coin ℓ the best coin.

We define ϵ_{0} = 1/8 and δ_{0} = e^{−4} /4. From now on, we fix some ϵ ∈ (0,ϵ_{0}) and δ ∈ (0,δ_{0}), and a policy, which we assume to be (ϵ/2,δ)-correct . If H_{0} is true, the policy must have probability at least 1−δ of eventually stopping and selecting coin 0. If H_{ℓ} is true, for some ℓ ≠ 0, the policy must have probability at least 1 − δ of eventually stopping and selecting coin ℓ. We denote by E_{ℓ} and P_{ℓ} the expectation and probability, respectively, under hypothesis H_{ℓ}.

We define t^{∗} by

t^{∗} = \frac{1}{cϵ^{2}} log \frac{1}{4δ} = \frac{1}{cϵ^{2}} log \frac{1}{θ},  (1)

where θ = 4δ, and where c is an absolute constant whose value will be specified later.^{1} Note that θ < e^{−4} and ϵ < 1/4.

Recall that T_{ℓ} stands for the number of times that coin ℓ is tried. We assume that for some coin ℓ ≠ 0, we have E_{0}[T_{ℓ}] ≤ t^{∗}. We will eventually show that under this assumption, the probability of selecting H_{0} under H_{ℓ} exceeds δ, and violates (ϵ/2,δ)-correctness. It will then follow that we must have E_{0}[T_{ℓ}] > t^{∗} for all ℓ ≠ 0. Without loss of generality, we can and will assume that the above condition holds for ℓ = 1, so that E_{0}[T_{1}] ≤ t^{∗}.

We will now introduce some special events A and C under which various random variables of interest do not deviate significantly from their expected values. We define

A = {T_{1} ≤ 4t^{∗}},

and obtain

t^{∗} ≥ E_{0}[T_{1}] ≥ 4t^{∗}P_{0}(T_{1} > 4t^{∗}) = 4t^{∗}(1 − P_{0}(T_{1} ≤ 4t^{∗})),

from which it follows that

P_{0}(A) ≥ 3/4.

We define K_{t} = X_{1}^{1}+ ··· + X_{t}^{1}, which is the number of unit rewards (“heads”) if the first coin is tried a total of t (not necessarily consecutive) times. We let C be the event defined by

C = \{ max_{1≤t≤4t^{∗}} |K_{t}− \frac{1}{2}t| < \sqrt{t^{∗}log(1/θ)}\}.

We now establish two lemmas that will be used in the sequel.

Lemma 2 We have P_{0}(C) > 3/4.

Proof We will prove a more general result:^{2} we assume that coin i has bias p_{i} under hypothesis H_{ℓ}, define K_{t}^{i} as the number of unit rewards (“heads”) if coin i is tested for t (not necessarily consecutive) times, and let

C_{i} = \{ max_{1≤t≤4t^{∗}} |K_{t}^{i}− p_{i}t| < \sqrt{t^{∗}log(1/θ)}\}.

First, note that K_{t}^{i} − p_{i}t is a P_{ℓ}-martingale (in the context of Theorem 1, p_{i} = 1/2 is the bias of coin i = 1 under hypothesis H_{0}). Using Kolmogorov’s inequality (Corollary 7.66, in p. 244 of Ross, 1983), the probability of the complement of C_{i} can be bounded as follows:

P_{ℓ}( max_{1≤t≤4t^{∗}} |K_{t}^{i}− p_{i}t| ≥ \sqrt{t^{∗}log(1/θ)}) ≤ \frac{E_{ℓ}[(K_{4t^{∗}}^{i}− 4p_{i}t^{∗})^{2}]}{t^{∗}log(1/θ)}.

Since E_{ℓ}[(K_{4t^{∗}}^{i}− 4p_{i}t^{∗})^{2}]= 4p_{i}(1 − p_{i})t^{∗}, we obtain

P_{ℓ}(C_{i}) ≥ 1 − \frac{4p_{i}(1 − p_{i})}{log(1/θ)} > \frac{3}{4},  (2)

where the last inequality follows because θ < e^{−4} and 4p_{i}(1 − p_{i}) ≤ 1. □

1. In this and subsequent proofs, and in order to avoid repeated use of truncation symbols, we treat t^{∗} as if it were

integer.

2. The proof for a general p_{i} will be useful later.

Lemma 3 If 0 ≤ x ≤ 1/\sqrt{2} and y ≥ 0, then

(1 − x)^{y} ≥ e^{−dxy},

where d = 1.78.

Proof A straightforward calculation shows that log(1 − x) + dx ≥ 0 for 0 ≤ x ≤ 1/\sqrt{2}. Therefore, y(log(1 − x) + dx) ≥ 0 for every y ≥ 0. Rearranging and exponentiating, leads to (1 − x)^{y} ≥ e^{−dxy}. □

We now let B be the event that I = 0, i.e., that the policy eventually selects coin 0. Since the policy is (ϵ/2,δ)-correct for δ < e^{−4} /4 < 1/4, we have P_{0}(B) > 3/4. We have already shown that P_{0}(A) ≥ 3/4 and P_{0}(C) > 3/4. Let S be the event that A, B, and C occur, that is S = A ∩ B ∩ C. We then have P_{0}(S) > 1/4.

Lemma 4 If E_{0}[T_{1}] ≤ t^{∗} and c ≥ 100, then P_{1}(B) > δ.

Proof We let W be the history of the process (the sequence of coins chosen at each time, and the sequence of observed coin rewards) until the policy terminates. We define the likelihood function L_{ℓ} by letting

L_{ℓ}(w) = P_{ℓ}(W = w),

for every possible history w. Note that this function can be used to define a random variable L_{ℓ}(W). We also let K be a shorthand notation for K_{T_{1}}, the total number of unit rewards (“heads”) obtained from coin 1. Given the history up to time t − 1, the coin choice at time t has the same probability distribution under either hypothesis H_{0} and H_{1}; similarly, the coin reward at time t has the same probability distribution, under either hypothesis, unless the chosen coin was coin 1. For this reason, the likelihood ratio L_{1}(W)/L_{0}(W) is given by

\frac{L_{1}(W)}{L_{0}(W)} = \frac{(\frac{1}{2} + ϵ)^{K}(\frac{1}{2} − ϵ)^{T_{1}−K}}{(\frac{1}{2})^{T_{1}}}
= (1 + 2ϵ)^{K}(1 − 2ϵ)^{K}(1 − 2ϵ)^{T_{1}−2K}
= (1 − 4ϵ^{2})^{K}(1 − 2ϵ)^{T_{1}−2K}.  (3)

We will now proceed to lower bound the terms in the right-hand side of Eq. (3) when event S occurs. If event S has occurred, then A has occurred, and we have K ≤ T_{1} ≤ 4t^{∗}, so that

(1 − 4ϵ^{2})^{K} ≥ (1 − 4ϵ^{2})^{4t^{∗}} = (1 − 4ϵ^{2})^{(4/(cϵ^{2}))log(1/θ)}
≥ e^{−(16d/c)log(1/θ)}
= θ^{16d/c}.

We have used here Lemma 3, which applies because 4ϵ^{2} < 4/4^{2} < 1/\sqrt{2}.

Similarly, if event S has occurred, then A ∩ C has occurred, which implies,

T_{1}− 2K ≤ 2\sqrt{t^{∗}log(1/θ)}= (2/ϵ\sqrt{c})log(1/θ),

where the equality above made use of the definition of t^{∗}. Therefore,

(1 − 2ϵ)^{T_{1}−2K} ≥ (1 − 2ϵ)^{(2/ϵ\sqrt{c})log(1/θ)}
≥ e^{−(4d/\sqrt{c})log(1/θ)}
= θ^{4d/\sqrt{c}}.

Substituting the above in Eq. (3), we obtain

\frac{L_{1}(W)}{L_{0}(W)}≥ θ^{(16d/c)+(4d/\sqrt{c})} .

By picking c large enough (c = 100 suffices), we obtain that L_{1}(W)/L_{0}(W)is larger than θ = 4δ whenever the event S occurs. More precisely, we have

\frac{L_{1}(W)}{L_{0}(W)}1_{S} ≥ 4δ1_{S},

where 1_{S} is the indicator function of the event S. Then,

P_{1}(B) ≥ P_{1}(S) = E_{1}[1_{S}] = E_{0}[ \frac{L_{1}(W)}{L_{0}(W)}1_{S}] ≥ E_{0}[4δ1_{S}] = 4δP_{0}(S) > δ,

where we used the fact that P_{0}(S) > 1/4. □

To summarize, we have shown that when c ≥ 100, if E_{0}[T_{1}] ≤ (1/cϵ^{2})log(1/(4δ)), then P_{1}(B) > δ. Therefore, if we have an (ϵ/2,δ)-correct policy, we must have E_{0}[T_{ℓ}] > (1/cϵ^{2})log(1/(4δ)), for every ℓ > 0. Equivalently, if we have an (ϵ,δ)-correct policy, we must have E_{0}[T] > (n/(4cϵ^{2}))log(1/(4δ)), which is of the desired form. □

4. A Lower Bound on the Sample Complexity - General Probabilities

In Theorem 1, we worked with a particular unfavorable vector p (the one corresponding to hypothesis H_{0}), under which a lot of exploration is necessary. This leaves open the possibility that for other, more favorable choices of p, less exploration might suffice. In this section, we refine Theorem 1 by developing a lower bound that explicitly depends on the actual (though unknown) vector p. Of course, for any given vector p, there is an “optimal” policy, which selects the best coin without any exploration: e.g., if p_{1} ≥ p_{ℓ} for all ℓ, the policy that immediately selects coin 1 is “optimal.” However, such a policy will not be (ϵ,δ)-correct for all possible vectors p.

We start with a lower bound that applies when all coin biases p_{i} lie in the range [0,1/2]. We will later use a reduction technique to extend the result to a generic range of biases. In the rest of the paper, we use the notational convention (x)^{+} = max{0,x}.

Theorem 5 Fix some \underline{p} ∈ (0,1/2). There exists a positive constant δ_{0}, and a positive constant c_{1} that depends only on \underline{p}, such that for every ϵ ∈ (0,1/2), every δ ∈ (0,δ_{0}), every p ∈ [0,1/2]^{n}, and every (ϵ,δ)-correct policy, we have

E_{p}[T] ≥ c_{1}\{ \frac{(|M(p,ϵ)| − 1)^{+}}{ϵ^{2}} + ∑_{ℓ∈N(p,ϵ)} \frac{1}{(p_{∗}− p_{ℓ})^{2}} \} log \frac{1}{8δ},

where p_{∗} = max_{i}p_{i},

M(p,ϵ) = \{ℓ: p_{ℓ} > p_{∗}− ϵ, andp_{ℓ} > \underline{p}, andp_{ℓ} ≥ \frac{ϵ + p_{∗}}{1 + \sqrt{1/2}} \} ,  (4)

and

N(p,ϵ) = \{ℓ: p_{ℓ} ≤ p_{∗}− ϵ, andp_{ℓ} > \underline{p}, andp_{ℓ} ≥ \frac{ϵ + p_{∗}}{1 + \sqrt{1/2}} \} .  (5)

In particular, δ_{0} can be taken equal to e^{−8} /8.

Remarks:

(a) The lower bound involves two sets of coins whose biases are not too far from the best bias p_{∗}. The first set M(p,ϵ) contains coins that are within ϵ from the best and would therefore be legitimate selections. In the presence of multiple such coins, a certain amount of exploration is needed to obtain the required confidence that none of these coins is significantly better than the others. The second set N(p,ϵ) contains coins whose bias is more than ϵ away from p_{∗}; they come into the lower bound because again some exploration is needed in order to obtain the required confidence that none of these coins is significantly better than the best coin in M(p,ϵ).

(b) The expression (ϵ + p_{∗} )/(1 + \sqrt{1/2} ) in Eqs. (4) and (5) can be replaced by (ϵ + p_{∗} )/(2 − α ) for any positive constant α, by changing some of the constants in the proof.

(c) This result actually provides a family of lower bounds, one for every possible choice of \underline{p}. A tighter bound can be obtained by optimizing the choice of \underline{p}, while also taking into account the dependence of the constant c_{1} on \underline{p}. This is not hard (the dependence of c_{1} on \underline{p} is described in Remark 7), but does not provide any new insights.

Proof Let us fix δ_{0} = e^{−8} /8, some \underline{p} ∈ (0,1/2), ϵ ∈ (0,1/2), δ ∈ (0,δ_{0}), an (ϵ,δ)-correct policy, and some p ∈ [0,1/2]^{n}. Without loss of generality, we assume that p_{∗} = p_{1}. Let us denote the true (unknown) bias of each coin by q_{i}. We consider the following hypotheses:

H_{0} : q_{i} = p_{i}, for i = 1,...,n ,

and for ℓ = 1,...,n,

H_{ℓ}: q_{ℓ} = p_{1}+ ϵ, q_{i} = p_{i}, for i ≠ ℓ.

If hypothesis H_{ℓ} is true, the policy must select coin ℓ. We will bound from below the expected number of times the coins in the sets N(p,ϵ) and M(p,ϵ) must be tried, when hypothesis H_{0} is true. As in Section 3, we use E_{ℓ} and P_{ℓ} to denote the expectation and probability, respectively, under the policy being considered and under hypothesis H_{ℓ}.

We define θ = 8δ, and note that θ < e^{−8} . Let

t_{ℓ}^{∗} = \{ \begin{matrix}\frac{1}{cϵ^{2}} log \frac{1}{θ}, & if ℓ ∈ M(p,ϵ), \\ \frac{1}{c(p_{1}− p_{ℓ})^{2}} log \frac{1}{θ}, & if ℓ ∈ N(p,ϵ), \end{matrix}

where c is a constant that only depends on \underline{p}, and whose value will be chosen later. Recall that T_{ℓ} stands for the total number of times that coin ℓ is tried. We define the event

A_{ℓ} = {T_{ℓ} ≤ 4t_{ℓ}^{∗}}.

As in the proof of Theorem 1, if E_{0}[T_{ℓ}] ≤ t_{ℓ}^{∗}, then P_{0}(A_{ℓ}) ≥ 3/4.

We define K_{t}^{ℓ} = X_{1}^{ℓ}+ ··· + X_{t}^{ℓ}, which is the number of unit rewards (“heads”) if the ℓ-th coin is tried a total of t (not necessarily consecutive) times. We let C_{ℓ} be the event defined by

C_{ℓ} = \{ max_{1≤t≤4t_{ℓ}^{∗}} |K_{t}^{ℓ}− p_{ℓ}t| < \sqrt{t_{ℓ}^{∗}log(1/θ)}\}.

Similar to Lemma 2, and since θ = 8δ < e^{−8} , we have^{3}

P_{0}(C_{ℓ}) > 7/8.

Let B_{ℓ} be the event {I = ℓ}, i.e., that the policy eventually selects coin ℓ, and let B_{ℓ}^{c} be its complement. Since the policy is (ϵ,δ)-correct with δ < δ_{0} < 1/2, we must have

P_{0}(B_{ℓ}^{c}) > 1/2, ∀ ℓ ∈ N(p,ϵ).

We also have ∑_{ℓ∈M(p,ϵ)}P_{0}(B_{ℓ}) ≤ 1, so that the inequality P_{0}(B_{ℓ}) > 1/2 can hold for at most one element of M(p,ϵ). Equivalently, the inequality P_{0}(B_{ℓ}^{c}) ≤ 1/2 can hold for at most one element of M(p,ϵ). Let

M_{0}(p,ϵ) = \{ℓ ∈ M(p,ϵ) andP_{0}(B_{ℓ}^{c}) > \frac{1}{2}\}.

It follows that |M_{0}(p,ϵ)| ≥ (|M(p,ϵ)| − 1)^{+} .

The following lemma is an analog of Lemma 4.

Lemma 6 Suppose that ℓ ∈ M_{0}(p,ϵ)∪N(p,ϵ) and that E_{0}[T_{ℓ}] ≤ t_{ℓ}^{∗}. If the constant c in the definition of t^{∗} is chosen large enough (possibly depending on \underline{p}), then P_{ℓ}(B_{ℓ}^{c}) > δ.

Proof Fix some ℓ ∈ M_{0}(p,ϵ) ∪ N(p,ϵ). For future reference, we note that the definitions of M(p,ϵ) and N(p,ϵ) include the condition p_{ℓ}≥ (ϵ+p_{∗})/(1+\sqrt{1/2}). Recalling that p_{∗} = p_{1}, p_{ℓ}≤ 1/2, and using the definition Δ_{ℓ} = p_{1}− p_{ℓ} ≥ 0, some easy algebra leads to the conditions

\frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ≤ \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ≤ \frac{1}{\sqrt{2}}.  (6)

We define the event S_{ℓ} by

S_{ℓ} = A_{ℓ}∩ B_{ℓ}^{c}∩ C_{ℓ}.

Since P_{0}(A_{ℓ}) ≥ 3/4, P_{0}(B_{ℓ}^{c}) > 1/2, and P_{0}(C_{ℓ}) > 7/8, we have

P_{0}(S_{ℓ}) > \frac{1}{8}, ∀ ℓ ∈ M_{0}(p,ϵ) ∪ N(p,ϵ).

3. The derivation is identical to Lemma 2 except for Eq. (2), where one should replace the assumption that θ < e^{−4}

with the stricter assumption that θ < e^{−8} used here.

As in the proof of Lemma 4, we define the likelihood function L_{ℓ} by letting

L_{ℓ}(w) = P_{ℓ}(W = w),

for every possible history w, and use again L_{ℓ}(W) to define the corresponding random variable.

Let K be a shorthand notation for K_{T_{ℓ}}^{ℓ}, the total number of unit rewards (“heads”) obtained from coin ℓ. We have

\frac{L_{ℓ}(W)}{L_{0}(W)} = \frac{(p_{1}+ ϵ)^{K}(1 − p_{1}− ϵ)^{T_{ℓ}−K}}{p_{ℓ}^{K}(1 − p_{ℓ})^{T_{ℓ}−K}}
= ( \frac{p_{1}}{p_{ℓ}} + \frac{ϵ}{p_{ℓ}}) ^{K}( \frac{1 − p_{1}}{1 − p_{ℓ}} − \frac{ϵ}{1 − p_{ℓ}} ) ^{T_{ℓ}−K}
= ( 1 + \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{K}( 1 − \frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ) ^{T_{ℓ}−K},

where we have used the definition Δ_{ℓ} = p_{1}− p_{ℓ}. It follows that

\frac{L_{ℓ}(W)}{L_{0}(W)} = ( 1 + \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{K}( 1 − \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{K}( 1 − \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{−K} ( 1 − \frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ) ^{T_{ℓ}−K}

= ( 1 − ( \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{2}) ^{K}( 1 − \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{−K} ( 1 − \frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ) ^{T_{ℓ}−K}

= ( 1 − ( \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{2}) ^{K}( 1 − \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{−K} ( 1 − \frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ) ^{K(1−p_{ℓ})/p_{ℓ}}

·( 1 − \frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ) ^{(p_{ℓ}T_{ℓ}−K)/p_{ℓ}} . (7)

We will now proceed to lower bound the right-hand side of Eq. (7) for histories under which event S_{ℓ} occurs. If event S_{ℓ} has occurred, then A_{ℓ} has occurred, and we have K ≤ T_{ℓ} ≤ 4t^{∗}, so that for every ℓ ∈ N(ϵ,p), we have

( 1 − ( \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{2}) ^{K} ≥ ( 1 − ( \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{2}) ^{4t_{ℓ}^{∗}}

= ( 1 − ( \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{2}) ^{(4/cΔ_{ℓ}^{2})log(1/θ)}
≥^{a} exp\{ −d \frac{4}{c}( \frac{(ϵ/Δ_{ℓ}) + 1}{p_{ℓ}} )^{2}log(1/θ)\}
≥^{b} exp\{ −d \frac{16}{cp_{ℓ}^{2}} log(1/θ)\}
= θ^{16d/p_{ℓ}^{2}c}.

In step (a), we have used Lemma 3 which applies because of Eq. (6); in step (b), we used the fact ϵ/Δ_{ℓ} ≤ 1, which holds because ℓ ∈ N(ϵ,p).

Similarly, for ℓ ∈ M(ϵ,p), we have

( 1 − ( \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{2}) ^{K} ≥ ( 1 − ( \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{2}) ^{4t_{ℓ}^{∗}}

= ( 1 − ( \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{2}) ^{(4/cϵ^{2})log(1/θ)}
≥^{a} exp\{ −d \frac{4}{c}( \frac{1 + (Δ_{ℓ}/ϵ)}{p_{ℓ}} )^{2}log(1/θ)\}
≥^{b} exp\{ −d \frac{16}{cp_{ℓ}^{2}} log(1/θ)\}
= θ^{16d/p_{ℓ}^{2}c}.

In step (a), we have again used Lemma 3; in step (b), we used the fact Δ_{ℓ}/ϵ ≤ 1, which holds because ℓ ∈ M(ϵ,p).

We now bound the product of the second and third terms in Eq. (7).

If b ≥ 1, then the mapping y ↦ (1 − y)^{b} is convex for y ∈ [0,1]. Thus, (1 − y)^{b} ≥ 1 − by, which implies that

( 1 − \frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ) ^{(1−p_{ℓ})/p_{ℓ}} ≥ ( 1 − \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ,

so that the product of the second and third terms can be lower bounded by

( 1 − \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{−K} ( 1 − \frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ) ^{K(1−p_{ℓ})/p_{ℓ}} ≥ ( 1 − \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{−K} ( 1 − \frac{ϵ + Δ_{ℓ}}{p_{ℓ}} ) ^{K} = 1.

We still need to bound the fourth term of Eq. (7). We start with the case where ℓ ∈ N(p,ϵ). We have

( 1 − \frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ) ^{(p_{ℓ}T_{ℓ}−K)/p_{ℓ}} ≥^{a} ( 1 − \frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ) ^{(1/p_{ℓ})\sqrt{t_{ℓ}^{∗}log(1/θ)}}  (8)
=^{b} ( 1 − \frac{ϵ + Δ_{ℓ}}{1 − p_{ℓ}} ) ^{(1/p_{ℓ}\sqrt{c}Δ_{ℓ})log(1/θ)}
≥^{c} exp\{ −\frac{d}{\sqrt{c}} · \frac{ϵ + Δ_{ℓ}}{Δ_{ℓ}(1 − p_{ℓ})p_{ℓ}} log(1/θ)\}  (9)
≥^{d} exp\{ −\frac{2d}{\sqrt{c}(1 − p_{ℓ})p_{ℓ}} log(1/θ)\}  (10)
≥^{e} exp\{ −\frac{4d}{\sqrt{c}p_{ℓ}} log(1/θ)\}
= θ^{4d/(p_{ℓ}\sqrt{c})}.

Here, (a) holds because we are assuming that the events A_{ℓ} and C_{ℓ} occurred; (b) uses the definition of t_{ℓ}^{∗} for ℓ ∈ N(p,ϵ); (c) follows from Eq. (6) and Lemma 3; (d) follows because Δ_{ℓ} > ϵ; and (e) holds because 0 ≤ p_{ℓ} ≤ 1/2, which implies that 1/(1 − p_{ℓ} ) ≤ 2.

Consider now the case where ℓ ∈ M_{0}(p,ϵ). Equation (8) holds for the same reasons as when ℓ ∈ N(p,ϵ). The only difference from the above calculation is in step (b), where t_{ℓ}^{∗} should be replaced with (1/cϵ^{2})log(1/θ). Then, the right-hand side in Eq. (9) becomes

exp\{ −\frac{d}{\sqrt{c}} · \frac{ϵ + Δ_{ℓ}}{ϵ(1 − p_{ℓ})p_{ℓ}} log(1/θ)\} .

For ℓ ∈ M_{0}(p,ϵ), we have Δ_{ℓ} ≤ ϵ, which implies that (ϵ + Δ_{ℓ})/ϵ ≤ 2, which then leads to the same expression as in Eq. (10). The rest of the derivation is identical. Summarizing the above, we have shown that if ℓ ∈ M_{0}(p,ϵ) ∪ N(p,ϵ), and event S_{ℓ} has occurred, then

\frac{L_{ℓ}(W)}{L_{0}(W)}≥ θ^{(4d/p_{ℓ}\sqrt{c})+(16d/p_{ℓ}^{2}c)} .

For ℓ ∈ M_{0}(p,ϵ) ∪ N(p,ϵ), we have \underline{p} < p_{ℓ}. We can choose c large enough so that L_{ℓ}(W)/L_{0}(W)≥ θ = 8δ; the value of c depends only on the constant \underline{p}. Similar to the proof of Theorem 1, we have

\frac{L_{ℓ}(W)}{L_{0}(W)}1_{S_{ℓ}} ≥ 8δ1_{S_{ℓ}},

where 1_{S_{ℓ}} is the indicator function of the event S_{ℓ}. It follows that

P_{ℓ}(B_{ℓ}^{c}) ≥ P_{ℓ}(S_{ℓ}) = E_{ℓ}[1_{S_{ℓ}}] = E_{0}[ \frac{L_{ℓ}(W)}{L_{0}(W)}1_{S_{ℓ}}] ≥ E_{0}[8δ1_{S_{ℓ}}] = 8δP_{0}(S_{ℓ}) > δ,

where the last inequality relies on the already established fact P_{0}(S_{ℓ}) > 1/8. □

Since the policy is (ϵ,δ)-correct, we must have P_{ℓ}(B_{ℓ}^{c}) ≤ δ, for every ℓ. Lemma 6 then implies that E_{0}[T_{ℓ}] > t_{ℓ}^{∗} for every ℓ ∈ M_{0}(p,ϵ) ∪ N(p,ϵ). We sum over all ℓ ∈ M_{0}(p,ϵ) ∪ N(p,ϵ), use the definition of t_{ℓ}^{∗}, together with the fact |M_{0}(p,ϵ)| ≥ (|M(p,ϵ)| − 1)^{+} , to conclude the proof of the theorem. □

Remark 7 A close examination of the proof reveals that the dependence of c_{1} on \underline{p} is captured by a requirement of the form c_{1} ≤ c_{2}\underline{p}^{2}, for some absolute constant c_{2}. This suggests that there is a tradeoff in the choice of \underline{p}. By choosing a large \underline{p}, the constant c_{1} is made larger, but the sets M and N become smaller, and vice versa.

The preceding result may give the impression that the sample complexity is high only when the p_{i} are bounded by 1/2. The next result shows that similar lower bounds hold (with a different constant) whenever the p_{i} can be assumed to be bounded away from 1. However, the lower bound becomes weaker (i.e., the constant c_{1} is smaller) when the upper bound on the p_{i} approaches 1. In fact, the dependence of a lower bound on ϵ cannot be Θ(1/ϵ^{2}) when max_{i}p_{i} = 1. To see this, consider the following policy π. Try each coin O((1/ϵ)log(n/δ)) times. If one of the coins always resulted in heads, select it. Otherwise, use some (ϵ,δ)-correct policy π̃. It can be shown that the policy π is (ϵ,δ)-correct (for every p ∈ [0,1]^{n}), and that if max_{i}p_{i} = 1, then E_{p}[T] = O((n/ϵ)log(n/δ)).

Theorem 8 Fix an integer s ≥ 2, and some \underline{p} ∈ (0,1/2). There exists a positive constant c_{1} that depends only on \underline{p} such that for every ϵ ∈ (0,2^{−(s+2)} ), every δ ∈ (0,e^{−8} /8), every p ∈ [0,1 − 2^{−s}]^{n}, and every (ϵ,δ)-correct policy, we have

E_{p}[T] ≥ \frac{c_{1}}{sη^{2}} \{ \frac{(|M(p̃,ϵη)| − 1)^{+}}{ϵ^{2}} + ∑_{ℓ∈N(p̃,ηϵ)} \frac{1}{(p_{∗}− p_{ℓ})^{2}} \} log \frac{1}{8δ} ,

where p_{∗} = max_{i}p_{i}, η = 2^{s+1} /s, p̃ is the vector with components p̃_{i} = 1 − (1 − p_{i})^{1/s} (for i = 1,2,...,n), and M and N are as defined in Theorem 5.

Proof Let us fix s ≥ 2, \underline{p} ∈ (0,1/2), ϵ ∈ (0,2^{−(s+2)} ), and δ ∈ (0,e^{−8} /8). Suppose that we have an (ϵ,δ)-correct policy π whose expected time to termination is E_{p}[T], whenever the vector of coin biases happens to be p. We will use the policy π to construct a new policy π̃ such that

Pp̃( p̃_{I} > max_{i}p̃_{i} − ηϵ) ≥ 1 − δ, ∀ p̃∈ [0,(1/2) + ηϵ]^{n};

(we will then say that π̃ is (ηϵ,δ)-correct on [0,(1/2)+ηϵ]^{n}). Finally, we will use the lower bounds from Theorem 5, applied to π̃, to obtain a lower bound on the sample complexity of π.

The new policy π̃ is specified as follows. Run the original policy π. Whenever π chooses to try a certain coin i once, policy π̃ tries coin i for s consecutive times. Policy π̃ then “feeds” π with 0 if all s trials resulted in 0, and “feeds” π with 1 otherwise. If p̃is the true vector of coin biases faced by policy π̃, and if policy π chooses to sample coin i, then policy π “sees” an outcome which equals 1 with probability p_{i} = 1 − (1 − p̃_{i})^{s}. Let us define two mappings f,g : [0,1] ↦ [0,1], which are inverses of each other, by

f(p_{i}) = 1 − (1 − p_{i})^{1/s}, g(p̃_{i}) = 1 − (1 − p̃_{i})^{s},

and with a slight abuse of notation, let f(p) = (f(p_{1}),...,f(p_{n})), and similarly for g(p̃). With our construction, when policy π̃ is faced with a bias vector p̃, it evolves in an identical manner as the policy π faced with a bias vector p = g(p̃). But under policy π̃, there are s trials associated with every trial under policy π, which implies that T̃= sT (T̃ is the number of trials under policy π̃) and therefore

Eπ̃ ; p̃[T̃] = sE_{g(p̃)}^{π}[T],  Eπ̃ ; f(p)[T̃] = sE_{p}^{π}[T],  (11)

where the superscript in the expectation operator indicates the policy being used.

We will now determine the “correctness” guarantees of policy π̃. We first need some algebraic preliminaries. Let us fix some p̃∈ [0,(1/2)+ηϵ]^{n} and a corresponding vector p, related by p̃= f(p) and p = g(p̃). Let also p_{∗} = max_{i}p_{i} and p̃_{∗} = max_{i} p̃_{i}. Using the definition η = 2^{s+1} /s and the assumption ϵ < 2^{−(s+2)} , we have p̃_{∗} ≤ (1/2) + (1/2s), from which it follows that

p_{∗} ≤ 1 − ( \frac{1}{2} − \frac{1}{2s}) ^{s} = 1 − \frac{1}{2^{s}} ( 1 − \frac{1}{s}) ^{s} ≤ 1 − \frac{1}{2^{s}} · \frac{1}{4} = 1 − 2^{−(s+2)} .

The derivative f′of f is monotonically increasing on [0,1). Therefore,

f′(p_{∗}) ≤ f′(1 − 2^{−(s+2)} ) = \frac{1}{s} ( 2^{−(s+2)} )^{(1/s)−1} = \frac{1}{s}2^{−(s+2)(1−s)/s}
= \frac{1}{s}2^{s+1−(2/s)} ≤ \frac{1}{s}2^{s+1} = η.

Thus, the derivative of the inverse mapping g satisfies

g′(p̃_{∗}) ≥ \frac{1}{η},

which implies, using the concavity of g, that

g(p̃_{∗} − ηϵ) ≤ g(p̃_{∗}) − g′(p̃_{∗})ϵη ≤ g(p̃_{∗}) − ϵ.

Let I be the coin index finally selected by policy π̃ when faced with p̃, which is the same as the index chosen by π when faced with p. We have (the superscript in the probability indicates the policy being used)

Pπ̃ ; p̃(p̃_{I} ≤ p̃_{∗} − ηϵ) = Pπ̃ ; p̃(g(p̃_{I}) ≤ g(p̃_{∗} − ηϵ))
≤ Pπ̃ ; p̃(g(p̃_{I}) ≤ g(p̃_{∗}) − ϵ)
= P_{p}^{π}(p_{I} ≤ p_{∗}− ϵ)
≤ 1 − δ,

where the last inequality follows because policy π was assumed to be (ϵ,δ)-correct. We have therefore established that π̃ is (ηϵ,δ)-correct on [0,(1/2) + ηϵ]^{n}. We now apply Theorem 5, with ηϵ instead of ϵ. Even though that theorem is stated for a policy which is (ϵ,δ)-correct for all possible p, the proof only requires the policy to be (ϵ,δ)-correct for p ∈ [0,(1/2) + ϵ]^{n}. This gives a lower bound on Eπ̃ ; p̃[T̃] which, using Eq. (11), translates to the claimed lower bound on E_{p}^{π}[T]. This lower bound applies whenever p = g(p̃), for some p̃∈ [0,1/2]^{n}, and therefore whenever p ∈ [0,1−2^{−s}]^{n}. □

5. The Bayesian Setting

There is another variant of the problem which is of interest. In this variant, the parameters p_{i} associated with each arm are not unknown constants, but random variables described by a given prior. In this case, there is a single underlying probability measure which we denote by P, and which is the average of the measures P_{p} over the prior distribution of p. We also use E to denote the expectation with respect to P. We then define a policy to be (ϵ,δ)-correct, for a particular prior and associated measure P, if

P( p_{I} > max_{i}p_{i}− ϵ) ≥ 1 − δ.

We then have the following result.

Theorem 9 There exist positive constants c_{1}, c_{2}, ϵ_{0}, and δ_{0}, such that for every n ≥ 2 and ϵ ∈ (0,ϵ_{0}), there exists a prior for the n-bandit problem such that for every δ ∈ (0,δ_{0}), and (ϵ,δ)-correct policy for this prior, we have

E[T] ≥ c_{1} \frac{n}{ϵ^{2}} log \frac{c_{2}}{δ}.

In particular, ϵ_{0} and δ_{0} can be taken equal to 1/8 and e^{−4} /12, respectively.

Proof Let ϵ_{0} = 1/8 and δ_{0} = e^{−4} /12, and let us fix ϵ ∈ (0,ϵ_{0}) and δ ∈ (0,δ_{0}). Consider the hypotheses H_{0},...,H_{n}, introduced in the proof of Theorem 1. Let the prior probability of H_{0} be 1/2, and the prior probability of H_{ℓ} be 1/2n, for ℓ = 1,...,n. Fix an (ϵ/2,δ)-correct policy with respect to this prior, and note that it satisfies

E[T] ≥ \frac{1}{2}E_{0}[T] ≥ \frac{1}{2} ∑_{ℓ=1}^{n} E_{0}[T_{ℓ}].  (12)

Since the policy is (ϵ/2,δ)-correct, we have P(p_{I} > max_{ℓ}p_{ℓ}− (ϵ/2)) ≥ 1 − δ.

As in the proof of Theorem 5, let B_{ℓ} be the event that the policy eventually selects coin ℓ. We have

\frac{1}{2}P_{0}(B_{0}) + \frac{1}{2n} ∑_{ℓ=1}^{n} P_{ℓ}(B_{ℓ}) ≥ 1 − δ,

which implies that

\frac{1}{2n} ∑_{ℓ=1}^{n} P_{ℓ}(B_{0}) ≤ δ.  (13)

Let G be the set of hypotheses ℓ ≠ 0 under which the probability of selecting coin 0 is at most 3δ, i.e.,

G = {ℓ: 1 ≤ ℓ ≤ n, P_{ℓ}(B_{0}) ≤ 3δ}.

From Eq. (13), we obtain

\frac{1}{2n}(n − |G|)3δ < δ,

which implies that |G| > n/3. Following the same argument as in the proof of Lemma 4, we obtain that there exists a constant c such that if δ′∈ (0,e^{−4} /4) and E_{0}[T_{ℓ}] ≤ (1/cϵ^{2})log(1/4δ′), then P_{ℓ}(B_{0}) > δ′. By taking δ′= 3δ and requiring that δ ∈ (0,e^{−4} /12), we see that the inequality E_{0}[T_{ℓ}] ≤ (1/cϵ^{2})log(1/12δ) implies that P_{ℓ}(B_{0}) > 3δ (here, c is the same constant as in Lemma 4). But for every ℓ ∈ G we have P_{ℓ}(B_{0}) ≤ 3δ, and therefore E_{0}[T_{ℓ}] ≥ (1/cϵ^{2})log(1/12δ). Then, Eq. (12) implies that

E[T] ≥ \frac{1}{2} ∑_{ℓ∈G}E_{0}[T_{ℓ}] ≥ |G|\frac{1}{cϵ^{2}} log \frac{1}{12δ} ≥ c′_{1} \frac{n}{ϵ^{2}} log \frac{c_{2}}{δ},

where we have used the fact |G| > n/3 in the last inequality.

To conclude, we have shown that there exists constants c′_{1} and c_{2} and a prior for a problem with n + 1 coins, such that any (ϵ/2,δ)-correct policy satisfies E[T] ≥ (c′_{1}n/ϵ^{2})log(c_{2}/δ). The result follows by taking a larger constant c′_{1} (to account for having n + 1 and not n coins, and ϵ instead of ϵ/2). □

6. Regret Bounds

In this section we consider lower bounds on the regret of any policy, and show that one can derive the Θ(logt) regret bound of Lai and Robbins (1985) using the techniques in this paper. The results of Lai and Robbins (1985) are asymptotic as t → ∞, whereas ours deal with finite times t. Our lower bound has similar dependence in t as the upper bounds given by Auer et al. (2002a) for some natural sampling algorithms. As in Lai and Robbins (1985) and Auer et al. (2002a), we also show that when t is large, the regret depends linearly on the number of coins.

Given a policy, let S_{t} be the total number of unit rewards (“heads”) obtained in the first t time steps. The regret by time t is denoted by R_{t}, and is defined by

R_{t} = t max_{i}p_{i}− S_{t}.

Note that the regret is a random variable that depends on the results of the coin tosses as well as of the randomization carried out by the policy.

Theorem 10 There exist positive constants c_{1},c_{2},c_{3},c_{4}, and a constant c_{5}, such that for every n ≥ 2, and for every policy, there exists some p ∈ [0,1]^{n} such that for all t ≥ 1,

E_{p}[R_{t}] ≥ min{c_{1}t, c_{2}n + c_{3}t, c_{4}n(logt − logn + c_{5})}.  (14)

The inequality (14) suggests that there are essentially two regimes for the expected regret. When n is large compared to t, the expected regret is linear in t. When t is large compared to n, the regret behaves like logt, but depends linearly on n.

Proof We will prove a stronger result, by considering the regret in a Bayesian setting. By proving that the expectation with respect to the prior is lower bounded by the right-hand side in Eq. (14), it will follow that the bound also holds for at least one of the hypotheses. Consider the same scenario as in Theorem 1, where we have n+1 coins and n+1 hypotheses H_{0},H_{1},...,H_{n}. The prior assigns a probability of 1/2 to H_{0}, and a probability of 1/2n to each of the hypotheses H_{1},H_{2},...,H_{n}. Similar to Theorem 1, we will use the notation E_{ℓ} and P_{ℓ} to denote expectation and probability when the ℓth hypothesis is true, and E to denote expectation with respect to the prior.

Let us fix t for the rest of the proof. We define T_{ℓ} as the number of times coin ℓ is tried in the first t time steps. The expected regret when H_{0} is true is

E_{0}[R_{t}] = \frac{ϵ}{2} ∑_{ℓ=1}^{n} E_{0}[T_{ℓ}],

and the expected regret when H_{ℓ} (ℓ = 1,...,n) is true is

E_{ℓ}[R_{t}] = \frac{ϵ}{2}E_{ℓ}[T_{0}] + ϵ ∑_{i≠0,ℓ} E_{ℓ}[T_{i}],

so that the expected (Bayesian) regret is

E[R_{t}] = \frac{1}{2} · \frac{ϵ}{2} ∑_{ℓ=1}^{n} E_{0}[T_{ℓ}] + \frac{ϵ}{2} · \frac{1}{2n} ∑_{ℓ=1}^{n} E_{ℓ}[T_{0}] + \frac{ϵ}{2n} ∑_{ℓ=1}^{n} ∑_{i≠0,ℓ} E_{ℓ}[T_{i}].  (15)

Let D be the event that coin 0 is tried at least t/2 times, i.e.,

D = {T_{0} ≥ t/2}.

We consider separately the two cases P_{0}(D) < 3/4 and P_{0}(D) ≥ 3/4. Suppose first that P_{0}(D) < 3/4. In that case, E_{0}[T_{0}] < 7t/8, so that ∑ _{ℓ=1}^{n} E_{0}[T_{ℓ}] ≥ t/8. Substituting in Eq. (15), we obtain E[R_{t}] ≥ ϵt/32. This gives the first term in the right-hand side of Eq. (14), with c_{1} = ϵ/32.

We assume from now on that P_{0}(D) ≥ 3/4. Rearranging Eq. (15), and omitting the third term, we have

E[R_{t}] ≥ \frac{ϵ}{4} ∑_{ℓ=1}^{n} ( E_{0}[T_{ℓ}] + \frac{1}{n}E_{ℓ}[T_{0}]).

Since E_{ℓ}[T_{0}] ≥ (t/2)P_{ℓ}(D), we have

E[R_{t}] ≥ \frac{ϵ}{4} ∑_{ℓ=1}^{n} ( E_{0}[T_{ℓ}] + \frac{t}{2n}P_{ℓ}(D)).  (16)

For every ℓ ≠ 0, let us define δ_{ℓ} by

E_{0}[T_{ℓ}] = \frac{1}{cϵ^{2}} log \frac{1}{4δ_{ℓ}}.

(Such a δ_{ℓ} exists because of the monotonicity of the mapping x ↦ log(1/x).) Let δ_{0} = e^{−4} /4. If δ_{ℓ}< δ_{0}, we argue exactly as in Lemma 4, except that the event B in that lemma is replaced by event D. Since P_{0}(D) ≥ 3/4, the same proof applies and shows that P_{ℓ}(D) ≥ δ_{ℓ}, so that

E_{0}[T_{ℓ}] + \frac{t}{2n}P_{ℓ}(D) ≥ \frac{1}{cϵ^{2}} log \frac{1}{4δ_{ℓ}} + \frac{t}{2n}δ_{ℓ}.

If on the other hand, δ_{ℓ} ≥ δ_{0}, then E_{0}[T_{ℓ}] ≤ (1/cϵ^{2})log(1/4δ_{0}), which implies (by the earlier analogy with Lemma 4) that P_{ℓ}(D) ≥ δ_{0}, and

E_{0}[T_{ℓ}] + \frac{t}{2n}P_{ℓ}(D) ≥ \frac{1}{cϵ^{2}} log \frac{1}{4δ_{ℓ}} + \frac{t}{2n}δ_{0}.

Using the above bounds in Eq. (16), we obtain

E[R_{t}] ≥ \frac{ϵ}{4} ∑_{ℓ=1}^{n} ( \frac{1}{cϵ^{2}} log \frac{1}{4δ_{ℓ}} + h(δ_{ℓ})\frac{t}{2n}) ,  (17)

where h(δ) = δ if δ < δ_{0}, and h(δ) = δ_{0} otherwise. We can now view the δ_{ℓ} as free parameters, and conclude that E[R_{t}] is lower bounded by the minimum of the right-hand side of Eq. (17), over all δ_{ℓ}. When optimizing, all the δ_{ℓ} will be set to the same value. The minimizing value can be δ_{0}, in which case we have

E[R_{t}] ≥ \frac{n}{4cϵ}log \frac{1}{4δ_{0}} + δ_{0} \frac{ϵ}{8}t.

Otherwise, the minimizing value is δ_{ℓ} = n/2ctϵ^{2}, in which case we have

E[R_{t}] ≥ ( \frac{1}{16cϵ}+ \frac{1}{4cϵ}log(cϵ^{2}/2)) n + \frac{1}{4cϵ}nlog(1/n) + \frac{n}{4cϵ}logt.

Thus, the theorem holds with c_{2} = (1/4cϵ)log(1/4δ_{0}), c_{3} = δ_{0}ϵ/8, c_{4} = 1/4cϵ, and c_{5} = (1/4) + log(cϵ^{2}/2). □

7. Permutations

We now consider the case where the coin biases p_{i} are known up to a permutation. More specifically, we are given a vector q ∈ [0,1]^{n}, and we are told that the true vector p of coin biases is of the form p = q ∘ σ, where σ is an unknown permutation of the set {1,...,n}, and where q ∘ σ stands for permuting the components of the vector q according to σ, i.e., (q ∘ σ)_{ℓ} = q_{σ(ℓ)}. We say that a policy is (q,ϵ,δ)-correct if the coin I eventually selected satisfies

P_{q∘σ}( p_{I} > max_{ℓ}q_{ℓ}− ϵ) ≥ 1 − δ,

for every permutation σ of the set {1,...,n}. We start with a O((n + log(1/δ))/ϵ^{2}) upper bound on the expected number of trials, which is significantly smaller than the bound obtained when the coin biases are completely unknown (cf. Sections 3 and 4). We also provide a lower bound which is within a constant factor of our upper bound.

We then consider a different measure of sample complexity: instead of the expected number of trials, we consider the maximum (over all sample paths) number of trials. We show that for every (q,ϵ,δ)-correct policy, there is a Θ((n/ϵ^{2})log(1/δ)) lower bound on the maximum number of trials. We note that in the median elimination algorithm of Even-Dar et al. (2002), the length of all sample paths is the same and within a constant factor from our lower bound. Hence our bound is again tight.

We therefore see that for the permutation case, the sample complexity depends critically on whether our criterion involves the expected or maximum number of trials. This is in contrast to the general case considered in Section 3: the lower bound in that section applies under both criteria, as does the matching upper bound from Even-Dar et al. (2002).

7.1 An Upper Bound on the Expected Number of Trials

Suppose we are given a vector q ∈ [0,1]^{n}, and we are told that the true vector p of coin biases is a permutation of q. The policy in Table 1 takes as input the accuracy ϵ, the confidence parameter δ, and the vector q. In fact the policy only needs to know the bias of the best coin, which we denote by q^{∗} = max_{ℓ}q_{ℓ}. The policy also uses an additional parameter δ′∈ (0,1/2].

The following theorem establishes the correctness of the policy, and provides an upper bound on the expected number of trials.

Theorem 11 For every δ′∈ (0,1/2], ϵ ∈ (0,1), and δ ∈ (0,1), the policy in Table 1 is guaranteed to terminate after a finite number of steps, with probability 1, and is (q,ϵ,δ)-correct. For every permutation σ, the expected number of trials satisfies

E_{q∘σ}[T] ≤ \frac{1}{ϵ^{2}} ( c_{1}n + c_{2}log \frac{1}{δ}) ,

for some positive constants c_{1} and c_{2} that depend only on δ′.

Proof We start with a useful calculation. Suppose that at iteration k, the median elimination algorithm selects a coin I_{k} whose true bias is p_{I_{k}}. Then, using the Hoeffding inequality, we have

P(|p̂_{k}− p_{I_{k}}| ≥ ϵ/3) ≤ exp\{−2(ϵ/3)^{2}m_{k}\} ≤ \frac{δ}{2^{k}}.  (18)

Input: Accuracy and confidence parameters ϵ ∈ (0,1) and δ ∈ (0,1); the bias of the best coin q^{∗}.

Parameter: δ′≤ 1/2.

0. k = 1;

1. Run the median elimination algorithm to find a coin I_{k} whose bias is within ϵ/3 of q^{∗}, with probability at least 1 − δ′.

2. Try coin I_{k} for m_{k} = ⌈(9/2ϵ^{2})log(2^{k}/δ)⌉ times.

Let p̂_{k} be the fraction of these trials that result in “heads.”

3. If p̂_{k} ≥ q^{∗}− 2ϵ/3 declare that coin I_{k} is an ϵ-optimal coin and terminate.

4. Set k:= k + 1 and go back to Step 1.

Table 1: A policy for finding an ϵ-optimal coin when the bias of the best coin is known.

Let K be the number of iterations until the policy terminates. Given that K > k − 1 (i.e., the policy did not terminate in the first k − 1 iterations), there is probability at least 1 − δ′≥ 1/2 that p_{I_{k}} ≥ q^{∗} − (ϵ/3), in which case, from Eq. (18), there is probability at least 1 − (δ/2^{k}) ≥ 1/2 that p̂_{k} ≥ q^{∗}−(2ϵ/3). Thus, P(K > k | K > k −1) ≤ 1−η, with η = 1/4. Consequently, the probability that the policy does not terminate by the kth iteration, P(K > k), is bounded by (1 − η)^{k}. Thus, the probability that the policy never terminates is bounded above by (3/4)^{k} for all k, and is therefore 0.

We now bound the expected number of trials. Let c be such that the number of trials in one execution of the median elimination algorithm is bounded by (cn/ϵ^{2})log(1/δ′). Then, the number of trials, t(k), during the kth iteration is bounded by (cn/ϵ^{2})log(1/δ′) + m_{k}. It follows that the expected total number of trials under our policy is bounded by

∑_{k=1}^{∞} P(K ≥ k)t(k) ≤ \frac{1}{ϵ^{2}} ∑_{k=1}^{∞}(1 − η)^{k−1} ( cnlog(1/δ′) + (9/2)log(2^{k}/δ) + 1)
= \frac{1}{ϵ^{2}} ∑_{k=1}^{∞}(1 − η)^{k−1} (cnlog(1/δ′) + (9/2)log(1/δ) + (9k/2)log2 + 1)
≤ \frac{1}{ϵ^{2}}(c_{1}n + c_{2}log(1/δ)),

for some positive constants c_{1} and c_{2}.

We finally argue that the policy is (q,ϵ,δ)-correct. For the policy to select a coin I with bias p_{I} ≤ q^{∗} − ϵ, it must be that at some iteration k, a coin I_{k} with p_{I_{k}} ≤ q^{∗} − ϵ was obtained, but p̂_{k} came out larger than q^{∗}− 2ϵ/3. From Eq. (18), for any fixed k, the probability of this occurring is bounded by δ/2^{k}. By the union bound, the probability that p_{I} ≤ q^{∗}−ϵ is bounded by ∑ _{k=1}^{∞} δ/2^{k}= δ. □

Remark 12 The knowledge of q^{∗} turns out to be significant: it enables the policy to terminate as soon as there is high confidence that a coin has been found whose bias is larger than q^{∗} − ϵ, without having to check the other coins. A policy of this type would not work for the hypotheses considered in the proofs of Theorems 1 and 5: under those hypotheses, the value of q^{∗} is not a priori known. We note that Theorem 11 disagrees with a lower bound in a preliminary version (Mannor and Tsitsiklis, 2003) of this paper. It turns out that the latter lower bound is only valid under an additional restriction on the set of policies, which will be the subject of Section 7.3.

7.2 A Lower Bound

We now prove that the upper bound in Theorem 11 is tight, within a constant.

Theorem 13 There exist positive constants c_{1}, c_{2}, ϵ_{0}, and δ_{1}, such that for every n ≥ 2 and ϵ ∈ (0,ϵ_{0}), there exists some q ∈ [0,1]^{n}, such that for every δ ∈ (0,δ_{1}) and every (q,ϵ,δ)-correct policy, there exists some permutation σ such that

E_{q∘σ}[T] ≥ \frac{1}{ϵ^{2}} ( c_{1}n + c_{2}log \frac{1}{δ}) .

Proof Let ϵ_{0} = 1/4 and let δ_{1} = δ_{0}/5, where δ_{0} is the same constant as in Theorem 5. Let us fix some n ≥ 2 and ϵ ∈ (0,ϵ_{0}). We will establish the claimed lower bound for

q = (0.5 + ϵ, 0.5 − ϵ,...,0.5 − ϵ),  (19)

and for every δ ∈ (0,δ_{1}). In fact, it is sufficient to establish a lower bound of the form (c_{2}/ϵ^{2})log(1/δ) and a lower bound of the form c_{1}n/ϵ^{2}. We start with the former.

Part I. Let us consider the following three hypothesis testing problems. For each problem, we are interested in a δ-correct policy, i.e., a policy whose probability of error is less than δ under any hypothesis. We will show that a δ-correct policy for the first problem can be used to construct a δ-correct policy for the third problem, with the same sample complexity, and then apply Theorem 5 to obtain a lower bound.

Π_{1}: We have two coins and the bias vector is either (0.5 − ϵ, 0.5 + ϵ) or (0.5 + ϵ, 0.5 − ϵ). We wish to determine the best coin. This is a special case of our permutation problem, with n = 2.

Π_{2}: We have a single coin whose bias is either 0.5 − ϵ or 0.5 + ϵ, and we wish to determine the bias of the coin.^{4}

Π_{3}: We have two coins and the bias vector can be (0.5, 0.5−ϵ), (0.5+ϵ, 0.5−ϵ), or (0.5,0.5+ϵ). We wish to determine the best coin.

Consider a δ-correct policy for problem Π_{1} except that the coin outcomes are encoded as follows. Whenever coin 1 is tried, record the outcome unchanged; whenever coin 2 is tried, record the opposite of the outcome (i.e., record a 0 outcome as a 1, and vice versa). Under the first hypothesis in problem Π_{1}, every trial (no matter which coin was tried) has probability 0.5−ϵ of being equal to 1, and under the second hypothesis has probability 0.5 + ϵ of being equal to 1. With this encoding, it is apparent that the information provided by a trial of either coin in problem Π_{1} is the same as the information provided by a trial of the single coin in problem Π_{2}. Thus, a δ-correct policy for Π_{1} translates to a δ-correct policy for Π_{2}, with the same sample complexity.

4. A lower bound for this problem was provided in Lemma 5.1 from Anthony and Bartlett (1999). However, that bound

is only established for policies with an a priori fixed number of trials, whereas our policies allow the number of trials

to be determined adaptively, based on observed outcomes.

In problem Π_{3}, note that coin 2 is the best coin if and only if its bias is equal to 0.5 + ϵ (as opposed to 0.5 − ϵ). Thus, any δ-correct policy for Π_{2} can be applied to the second coin in Π_{3}, to yield a δ-correct policy for Π_{3} with the same sample complexity.

We now observe that problem Π_{3} involves a set of three hypotheses, of the form considered in the proof of Theorem 5, for the case of two coins. More specifically, in terms of the notation used in that proof, we have p = (0.5,0.5 − ϵ), and N(p,ϵ) = {2}. It follows that the sample complexity of any δ-correct policy for Π_{3} is lower bounded by (c_{1}/ϵ^{2})log(1/8δ), where c_{1} is the constant in Theorem 5.^{5} Because of the relation between the three problems established earlier, the same lower bound applies to any δ-correct policy for problem Π_{1}, which is the permutation problem of interest.

We have so far established a lower bound proportional to (1/ϵ^{2})/log(1/δ) for problem Π_{1}, which is the permutation problem we are interested in, with a q vector of the form (19), for the case n = 2. Consider now the permutation problem for the q vector in (19), but for general n. If we are given the information that the best coin can only be one of the first two coins, we obtain problem Π_{1}. In the absence of this side-information, the permutation problem cannot be any easier. This shows that the same lower bound holds for every n ≥ 2.

Part II: We now continue with the second part of the proof. We will establish a lower bound of the form c_{1}n/ϵ^{2} for the permutation problem associated with the bias vector q introduced in Eq. (19), to be referred to as problem Π. The proof involves a reduction of Π to a problem Π̃ of the form considered in the proof of Theorem 5.

The problem Π̃ involves n + 1 coins (coins 0,1,...,n) and the following n + 2 hypotheses:

H′_{0}: p_{0} = 0.5, p_{i} = 0.5 − ϵ, for i ≠ 0,
H′′_{0}: p_{0} = 0.5 + ϵ, p_{i} = 0.5 − ϵ, for i ≠ 0,

and

H_{ℓ}: p_{0} = 0.5,  p_{ℓ} = 0.5 + ϵ,  p_{i} = 0.5 − ϵ, for i ≠ 0,ℓ.

Note that the best coin is coin 0 under either hypothesis H′_{0} or H′′_{0}, and the best coin is coin ℓ under H_{ℓ}, for ℓ ≥ 1. This leads us to define H_{0} as the hypothesis that either H′_{0} or H′′_{0}is true.

We say that a policy for Π̃ is δ-correct if it selects the best coin with probability at least 1 − δ. We will show that if we have a (q,ϵ,δ)-correct policy π for Π, with a certain sample complexity, we can construct an (ϵ,5δ)-correct policy π̃ with a related sample complexity. We will then apply Theorem 5 to lower bound the sample complexity of π̃, and finally translate to a lower bound for π.

The idea of the reduction is as follows. In problem Π̃, if we knew that H_{0} is not true, we would be left with a permutation problem with n coins, to which π could be applied. However, if H_{0} is true, the behavior of π is unpredictable. (In particular, π might not terminate, or it might terminate with an arbitrary decision: this is because we are only assuming that π behaves properly when faced with the permutation problem Π.) If H_{0} is true, we can replace coin 1 with a coin whose bias is 0.5 + ϵ, resulting in the bias vector q, in which case π is guaranteed to work properly. But what if we replace coin 1 as above, but some H_{ℓ}, ℓ ≠ 0,1, happens to be true? In that case, there will be two coins with bias 0.5 + ϵ and π may misbehave. The solution is to run two processes in parallel, one with and one without this modification, in which case one of the two will have certain performance guarantees that we can exploit.

5. Although Theorem 5 is stated for (ϵ,δ)-correct policies, it is clear from the proof that the lower bound applies to any

policy that has the desired behavior under all of the hypotheses considered in the proof.

Consider the (q,ϵ,δ)-correct policy π for problem Π. Let t_{π} be the maximum (over all permutations σ) expected time until π terminates when the true coin bias vector is q ∘ σ.

We define two more bias vectors that will be used below:

q_{−} = (0.5 − ϵ,...,0.5 − ϵ) ,

and

q_{+} = (0.5 + ϵ, 0.5 + ϵ, 0.5 − ϵ,...,0.5 − ϵ) .

Note that if H_{0} is true in problem Π̃, and π is applied to coins 1,...,n, then π will be faced with the bias vector q_{−}. Also, if H_{ℓ}, is true in problem Π̃, for some ℓ ≠ 0,1, and we modify the bias of coin 1 to 0.5 + ϵ, then policy π will be faced with the bias vector q_{+} .

Let us note for future reference that, as in Eq. (18), if we sample a coin with bias 0.5 + ϵ for m =^{△} ⌈(1/ϵ^{2})log(1/δ)⌉ times, the empirical mean reward is larger than 0.5 with probability at least 1 − δ. Similarly, if we sample a coin with bias 0.5 − ϵ for m times, the empirical mean reward is smaller than 0.5 with probability at least 1 − δ. Sampling a specific coin that many times, and comparing the empirical mean to 0.5, will be referred to as “validating” the coin.

We now describe policy π̃ for problem Π̃. The policy involves two parallel processes A and B: it alternates between the two processes, and each process samples one coin in each one of its turns. The processes continue to sample the coins alternately until one of them terminates and declares one of the coins as the best coin (or equivalently selects a hypothesis). The parameter k below is set to k = ⌈18log(1/δ)⌉.

A: Apply policy π to coins 1,2,...,n. If π terminates and selects coin ℓ, validate coin ℓ by sampling it m times. If the empirical mean reward is more than 0.5, then A terminates and declares coin ℓ as the best coin. If the empirical mean reward is less than or equal to 0.5, then A terminates and declares coin 0 as the best coin. If π has carried out ⌈t_{π}/δ⌉ trials, then A terminates and declares coin 0 as the best coin.

B: Sample coin 1 for m times. If the empirical mean reward is more than 0.5, then B terminates and declares coin 1 as the best coin. Otherwise, replace coin 1 with another coin whose bias is 0.5 + ϵ. Initialize a counter N with N = 0.

Repeat k times the following:

(a) Pick a random permutation τ (uniformly over the set of permutations).

(b) Run a τ-permuted version of π, to be referred to as τ∘π; that is, whenever π is supposed to sample coin i, τ ∘ π samples coin τ(i) instead.

(c) If τ ∘ π terminates and selects coin 1 as the best coin, set N := N + 1.

If N > 2k/3, then B terminates and declares coin 0 as the best coin. Otherwise, wait until process A terminates.

We first address the issue of correctness of policy π̃. Note that π̃ is guaranteed to terminate in finite time, because process A can only run for a bounded number of steps. We consider separately the following cases:

1. Process A terminates first, H_{0} is true. In this case the true bias vector faced by π is q_{−} rather than q. An error can happen only if π terminates and the coin erroneously passes the validation test. The probability of this occurring is at most δ. In all other cases (validation fails or the running time exceeds the time limit ⌈t_{π}/δ⌉), process A correctly declares H_{0} to be the true hypothesis.

2. Process A terminates first, H_{ℓ} is true for some ℓ ≠ 0. Process A does not declare the correct H_{ℓ} if one of the following events occurs: A fails to select the best coin (probability at most δ, since π is (q,ϵ,δ)-correct); or the validation makes an error (probability at most δ); or the time limit is exceeded. By Markov’s inequality, the probability that the running time T_{π} of policy π exceeds the time limit satisfies

P_{q}(T_{π} ≥ t_{π}/δ) ≤ E_{q}[T_{π}]δ/t_{π} ≤ t_{π}δ/t_{π} = δ.

So, the total the probability of errors that fall within this case is bounded by 3δ.

3. Process B terminates first, H_{0} is true. Note that under H_{0}, process B is faced with n coins whose bias vector is q. Process B does not declare H_{0} if one of the following events occurs: the initial validation of coin 1 makes an error (probability at most δ); or in k runs, the permuted versions of policy π make at least k/3 errors. Each such run has probability at most δ of making an error (since π is (q,ϵ,δ)-correct), independently for each run (because we use a random permutation before each run). Using Hoeffding’s inequality, the probability of at least k/3 errors is bounded by exp{−2k(1/3 − δ)^{2}}. Since δ < 1/12, this probability is at most e^{−k/8}. So, the total the probability of errors that fall within this case is bounded by δ + e^{−k/8}.

4. Process B terminates first, H_{ℓ} is true for some ℓ > 1. Process B does not declare H_{ℓ} if one of the following events occurs: the initial validation of coin 1 makes an error (probability at most δ); or in k runs, the permuted versions of policy π select coin 1 for N > 2k/3 times. Since in each of the k runs the policy is faced with the bias vector q_{+} , there are no guarantees on its behavior. However, since we use a random permutation before each run, and since there are two coins with bias 0.5 + ϵ, namely coins 1 and ℓ, the probability that the permuted version of π selects coin 1 at any given run is bounded by 1/2. Using Hoeffding’s inequality, the probability of selecting coin 1 more than 2k/3 times is bounded by exp{−2k((2/3) − (1/2))^{2}} = e^{−k/18}. So, the total the probability of errors that fall within this case is bounded by δ + e^{−k/18}.

5. Process B terminates first, H_{1} is true. Process B fails to declare coin 1 only if an error is made in the initial validation step, which happens with probability bounded by δ.

To conclude, using the union bound, when H_{0} is true, the probability of error is bounded by 2δ + e^{−k/8} ; when H_{1} is true, it is bounded by 4δ; and when H_{ℓ}, ℓ > 1 is true, it is bounded by 4δ + e^{−k/18}. Since k = 18log(1/δ), we see that the probability of error, under any hypothesis, is bounded by 5δ.

We now examine the sample complexity of policy π̃. We consider two cases, depending on which hypothesis is true.

1. H_{0} is true. In process A, policy π is faced with the bias vector q_{−} and has no termination guarantees, unless it reaches the time limit ⌈t_{π}/δ⌉. As established earlier (case 3), Process B will terminate after the initial validation of coin 1 (m trials), plus possibly k runs of policy π (expected number of trials kt_{π}), with probability at least 1 − e^{−k/8}. Otherwise, B waits until A terminates (at most 1 + t_{π}/δ time). Multiplying everything by a factor of 2 (because the two processes alternate), the expected time until π̃ terminates is bounded by

2(m + kt_{π}) + 2e^{−k/8}(m + t_{π}/δ + 1).

2. H_{ℓ} is true for some ℓ ≠ 0. In this case, process A terminates after the validation time m and the time it takes for π to run. Thus, the expected time until termination is bounded by 2(m + 1 + t_{π}).

We have constructed an (ϵ,5δ)-correct policy π̃ for problem Π̃. Using the above derived time bounds, and the definitions of k and m, the expected number of trials, under any hypothesis H_{ℓ}, is bounded from above by

4m + 36( log( \frac{1}{δ}) + 3) t_{π}.

On the other hand, problem Π̃ involves hypotheses of the form considered in the proof of Theorem 5, with p = (0.5, 0.5 − ϵ,...,0.5 − ϵ), and with N(p,ϵ) = {1,2,...,n}. Thus, the expected number of trials under some hypothesis is bounded below by (c_{1}n/ϵ^{2})log(c_{2}/δ), for some positive constants c_{1} and c_{2}, leading to

c_{1} \frac{n}{ϵ^{2}} log \frac{c_{2}}{δ} ≤ 4m + 36( log( \frac{1}{δ}) + 3) t_{π}.

This translates to a lower bound of the form t_{π} ≥ c_{2}n/ϵ^{2}, for some new constant c_{2}, and for all n larger than some n_{0}. But for n ≤ n_{0}, we can use the lower bound (c_{2}/ϵ^{2})log(1/δ) that was derived in the first part of the proof. □

7.3 Pathwise Sample Complexity

The sample complexity of the policy presented in Section 7.1 was measured in term of the expected number of trials. Suppose, however, that we are interested in a policy for which the number of trials is always low. Let us say that a policy has a pathwise sample complexity of t, if the policy terminates after at most t trials, with probability 1. We note that the median elimination algorithm of Even-Dar et al. (2002) is a (q,ϵ,δ)-correct policy whose pathwise sample complexity is of the form (c_{1}n/ϵ^{2})log(c_{2}/δ). In this section, we show that at least for a certain q, there is a matching lower bound on the pathwise sample complexity of any (q,ϵ,δ)-correct policy.

Theorem 14 There exist positive constants c_{1}, c_{2}, ϵ_{0}, and δ_{1} such that for every n ≥ 2 and ϵ ∈ (0,ϵ_{0}), there exists some q ∈ [0,1]^{n}, such that for every δ ∈ (0,δ_{1}) and every (q,ϵ,δ)-correct policy π, there exists some permutation σ under which the pathwise sample complexity of π is at least

c_{1} \frac{n}{ϵ^{2}} log( \frac{c_{2}}{δ}) .

Proof The proof uses a reduction similar to the one in the proof of Theorem 13. Let ϵ_{0} = 1/8 and δ_{1} = δ_{0}/2, where δ_{0} = e^{−8} /8 is the constant in Theorem 5. Let q be the same as in the proof of Theorem 13 (cf. Eq. (19)), and consider the associated permutation problem, referred to as problem Π. Fix some δ ∈ (0,δ_{1}) and suppose that we have a (q,ϵ,δ)-correct policy π for problem Π whose pathwise sample complexity is bounded by t_{π} for every permutation σ. Consider also the problem Π̃ introduced in the proof of Theorem 13, involving the hypotheses H_{0}, H_{1},...,H_{n}. We will now use the policy π to construct a policy π̃ for problem Π̃.

We run π on the coins 1,2,...,n. If π terminates at or before time t_{π} and selects some coin ℓ, we sample coin ℓ for ⌈(1/ϵ^{2})log(1/δ)⌉ times. If the empirical mean reward is larger than 0.5 we declare H_{ℓ} as the true hypothesis. If the empirical mean reward of coin ℓ is less than or equal to 0.5, or if π does not terminate by time t_{π}, we declare H_{0} as the true hypothesis.

We start by showing correctness. Suppose first that H_{0} is true. For the policy π̃ to make an incorrect decision, it must be the case that policy π selected some coin and the empirical mean reward of this coin was larger than 1/2; using Hoeffding’s inequality, the probability of this event is bounded by δ. Suppose instead that H_{ℓ} is true for some ℓ ≥ 1. In this case, policy π is guaranteed to terminate within t_{π} steps. Policy π̃ will make an incorrect decision if either policy π makes an incorrect decision (probability at most δ), or if policy π makes a correct decision but the selected coin fails to validate (probability at most δ). It follows that policy π̃ is (q,ϵ,2δ)-correct.

The number of trials under policy π̃ is bounded by t′= t_{π} + ⌈(1/ϵ^{2})log(1/δ)⌉, under any hypothesis. On the other hand, using Theorem 5, the expected number of trials under some hypothesis is bounded below by (c_{1}n/ϵ^{2})log(c_{2}/2δ), leading to

c_{1} \frac{n}{ϵ^{2}} log \frac{c_{2}}{2δ} ≤ t_{π} + \frac{1}{ϵ^{2}} log( \frac{1}{δ}) .

this translates to a lower bound of the form t ≥ (c_{1}n/ϵ^{2})log(c_{2}/δ), for some new constants c_{1} and c_{2}. □

8. Concluding Remarks

We have provided bounds on the number of trials required to identify a near-optimal arm in a multiarmed bandit problem, with high probability. For the problem formulations studied in Sections 3 and 5, the lower bounds match the existing O((n/ϵ^{2})log(1/δ)) upper bounds. For the case where the values of the biases are known but the identities of the coins are not, we provided two different tight bounds, depending on the particular criterion being used (expected versus maximum number of trials). Our results have been derived under the assumption of Bernoulli rewards. Clearly, the lower bounds also apply to more general problem formulations, as long as they include Bernoulli rewards as a special case. It would be of some interest to derive similar lower bounds for other special cases of reward distributions. It is reasonable to expect that essentially the same results will carry over, as long as the Kullback-Leibler divergence between the reward distributions associated with different arms is finite (as in Lai and Robbins, 1985).

Acknowledgments

We would like to thank Susan Murphy and David Siegmund for pointing out some relevant references from the sequential analysis literature. We thank two anonymous reviewers for their comments. This research was supported by the MIT-Merrill Lynch partnership, the ARO under grant DAAD10-00-1-0466, and the National Science Foundation under grant ECS-0312921.

References

M. Anthony and P. L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.

P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235–256, 2002a.

P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proc. 36th Annual Symposium on Foundations of Computer Science, pages 322–331. IEEE Computer Society Press, 1995.

P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The non-stochastic multi-armed bandit problem. SIAM Journal on Computing, 32:48–77, 2002b.

D.A. Berry and B. Fristedt. Bandit Problems. Chapman and Hall, 1985.

H. Chernoff. Sequential Analysis and Optimal Design. Society for Industrial & Applied Mathematics, 1972.

E. Even-Dar, S. Mannor, and Y. Mansour. PAC bounds for multi-armed bandit and Markov decision processes. In J. Kivinen and R. H. Sloan, editors, Fifteenth Annual Conference on Computational Learning Theory, pages 255–270. Springer, 2002.

C. Jennison, I. M. Johnstone, and B. W. Turnbull. Asymptotically optimal procedures for sequential adaptive selection of the best of several normal means. In S. S. Gupta and J. Berger, editors, Statistical decision theory and related topics III, volume 3, pages 55–86. Academic Press, 1982.

S. R. Kulkarni and G. Lugosi. Finite-time lower bounds for the two-armed bandit problem. IEEE Trans. Aut. Control, 45(4):711–714, 2000.

T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4–22, 1985.

S. Mannor and J.N. Tsitsiklis. Lower bounds on the sample complexity of exploration in the multiarmed bandit problem. In B. Schölkopf and M. K. Warmuth, editors, Sixteenth Annual Conference on Computational Learning Theory, pages 418–432. Springer, 2003.

H. Robbins. Some aspects of sequential design of experiments. Bulletin of the American Mathematical Society, 55:527–535, 1952.

S. M. Ross. Stochastic Processes. Wiley, 1983.

D. Siegmund. Sequential analysis: Tests and Confidence Intervals. Springer Verlag, 1985.