%MAB Lower Bounds
%JMLR Version
%Shie Mannor and John N. Tsitsiklis

\documentclass[twoside,11pt]{article}

\usepackage[usenames,dvipsnames]{color}

\usepackage{jmlr2e}
\usepackage[usenames,dvipsnames]{color}
\newcommand{\Exp}{{\rm I\hspace{-0.7mm}E}}
%\documentclass[12pt]{article}
\usepackage{epsf}

\jmlrheading{5}{2004}{623-648}{1/04}{6/04}{Shie Mannor and John Tsitsiklis}
\ShortHeadings{Exploration in Multi-Armed Bandits}{Mannor and
  Tsitsiklis} 
\firstpageno{623}

\newcommand{\Red}[1]{{\color{red}#1}}
\newcommand{\Blue}{\color{blue}}
\newcommand{\Green}{\color{green}}
\newcommand{\Black}{\color{black}}
\newcommand{\Magenta}{\color{Magenta}}
\newcommand{\bt}{\mbox{\boldmath $\theta$}}

\newcommand{\half}{\frac{1}{2}}
%toggle red/all black version
%\renewcommand{\Red}[1]{#1}



\def\JNT#1{{[JNT: \bf #1]}}
\def\SM#1{{\Red{#1}}}
\def\SMNEW#1{{\tt #1}}


\begin{document}

\title{The Sample Complexity of
Exploration in the \\Multi-Armed Bandit Problem}

\author{\name Shie Mannor  \email shie@mit.edu \\
\name John N.\ Tsitsiklis \email jnt@mit.edu\\
       \addr Laboratory for Information and Decision Systems\\
       Massachusetts Institute of Technology \\
       Cambridge, MA 02139, USA
}

\editor{Kristin Bennett and Nicol{\`o} Cesa-Bianchi}

\maketitle


%\end{titlepage}
%\setlength{\textwidth}{6in} \setlength{\textheight}{9in}
%\setlength{\topmargin}{-0.5in} \setlength{\oddsidemargin}{.25in}

%\begin{document}


%\renewcommand{\cite}{\shortciteA}


\newcommand{\uu}{\underline}
\newcommand{\oo}{\overline}

\newcommand{\reals}{{\rm I\!R}}
\newcommand{\PP}{{\rm I\!P}}
\newcommand{\NN}{{\rm I\!\!N}}
\newcommand{\ZZ}{{ /\!\!Z}}

\newcommand{\Ball}{{\rm I\!B}}

\newcommand{\cI}{{\cal I}}
\newcommand{\cT}{{\cal T}}
\newcommand{\cJ}{{\cal J}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cU}{{\cal U}}
\newcommand{\cH}{{\cal H}}
\newcommand{\cN}{{\cal N}}

%\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\newcommand{\mysection}[1]{\section{#1}\setcounter{equation}{0}}
% \newcommand{\mysection}[1]{\section{#1}\setcounter{equation}{0}
%                       \setcounter{figure}{0}}

%ABBREVIATIONS
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\dfn}{\stackrel{\triangle}{=}}
\newcommand{\bydef}{\stackrel{\bigtriangleup}{=}}
\newcommand{\limsupn}{\limsup_{n \rightarrow \infty}}
\newcommand{\liminfn}{\liminf_{n \rightarrow \infty}}
\newcommand{\liminft}{\liminf_{t \rightarrow \infty}}
\newcommand{\limsupt}{\limsup_{t \rightarrow \infty}}
\newcommand{\val}{{\rm v }}
\newcommand{\co}{{\rm co }}
\newcommand{\ri}{{\rm ri }}
\newcommand{\limn}{\lim_{n \rightarrow \infty}}
\newcommand{\R}[1]{\reals^{#1}}
\newcommand{\m}[1]{\mathcal{#1}}

%COMMANDS
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray}}
\newcommand{\eea}{\end{eqnarray}}
\newcommand{\beaa}{\begin{eqnarray*}}
\newcommand{\eeaa}{\end{eqnarray*}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\db}{\hspace*{\fill}{\zapf o}}
\newcommand{\cpn}[1]{\caption{\myfont #1}}
\newcommand{\bpn}{\begin{proposition}\twlsf}
\newcommand{\epn}{\db\end{proposition}}
\newcommand{\bdm}{\begin{displaymath}}
\newcommand{\edm}{\end{displaymath}}

\newcommand{\supp}{\rm{supp}}
\newcommand{\op}[1]{\mbox{op}_{#1}}
\newcommand{\argmax}{\mathop{\mbox{argmax}}}
\newcommand{\argmin}{\mathop{\mbox{argmin}}}

\renewcommand{\Pr}{\mathbf{P}}
\newcommand{\ed}{($\epsilon$,$\delta$)}
\newcommand{\qedc}{($q,\epsilon$,$\delta$)}
\newcommand{\E}{{\bf E}}
\newcommand{\qed}{\hfill{$\Box$}\par\vspace{10pt}}


%ENVIRONMENTS
\newtheorem{assumption}{Assumption}

%VARIOUS NOTATIONS

\newcommand{\boldone}{\mbox{\bf 1}}
\newcommand{\Ga}{\Gamma}
\newcommand{\GA}{\Gamma}
\newcommand{\La}{\Lambda}
\newcommand{\LA}{\Lambda}
\newcommand{\la}{\lambda}
\newcommand{\eps}{\epsilon}
\newcommand{\rate}{\frac{1}{n}\log}
\newcommand{\Rd}{\reals^d}
\newcommand{\DU}{\Delta(\cU)}
\newcommand{\bX}{\oo{X}}
\newcommand{\lip}{\langle}
\newcommand{\rip}{\rangle}
\newcommand{\rome}{\mbox{\rm e}}
\newcommand{\Pone}{P^1}
\newcommand{\Ptwo}{P^2}

\newcommand{\mA}{{\mathcal{A}}}
\newcommand{\mB}{{\mathcal{B}}}


\def\Old#1{OLD: {\tt #1}}
% \renewcommand{\cite}{\citeA}


%\par
%\noindent

\begin{abstract}
We consider the multi-armed bandit problem under the PAC (``probably approximately correct'') model. It was shown by
\cite{EDMM02} that given $n$ arms,  a total of $O\big(({n}/{\eps^2})\log ({1}/{\delta})\big)$ trials suffices
in order to find an
$\eps$-optimal arm with probability at least $1-\delta$. 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 $\Theta\big(({1}/{\eps^2})(n+ \log (1/\delta))\big)$ 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
$\Theta\big(({n}/{\eps^2})\log ({1}/{\delta})\big)$.
Finally, we derive lower bounds on the expected regret, in the spirit of Lai and Robbins.
\end{abstract}


%\thispagestyle{empty}

%\newpage
%\setcounter{page}{1}

\section{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 \cite{R52},
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 \cite{BF85} for a review of the classical results on the
multi-armed bandit problem.

 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 \cite{LR85}
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 \cite{A95,ACFS02}, 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 \cite{KulkarniLugosi00}
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-\delta$) an arm whose expected reward is within $\epsilon$ 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 \cite{EDMM02}, a
policy, called the median elimination algorithm, was provided
 which
requires $O\big((n/\epsilon^2)\log (1/\delta))$ trials, and which
finds an $\epsilon$-optimal
arm
with probability at least $1-\delta$.
A matching lower bound was also derived in \cite{EDMM02}, but it
only applied to the case where $\delta > 1/n$, and therefore did
not capture the case where high confidence (small $\delta$) is
desired. In this paper, we derive a matching lower bound which
also applies when $\delta>0$ is arbitrarily small.

Our main result can be
viewed as a generalization of a $O\big((1/\eps^2) \log(1/\delta)\big)$ lower
bound provided in \cite{anthony_bartlett99}, and \cite{Chernoff72}, for the case of two
bandits. The proof in \cite{anthony_bartlett99} 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.

A different
type of lower bound was derived in \cite{ACFS02}
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/\delta)$ dependence on
$\delta$. Our work also provides fundamental lower bounds in the
context of sequential analysis \cite[see, e.g.,][]{Chernoff72,JJT82,siegmund85}. In
the language of \cite{siegmund85}, 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 \cite{siegmund85} (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, \cite{siegmund85} 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
\cite[see, e.g.,][]{JJT82}, 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 \cite{JJT82},
in that we consider the case where the reward is not Gaussian.

\section*{Paper Outline}

The paper is organized as follows. In Section \ref{sec:probdef}, 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 \ref{sec:mainspecprob}, we
provide a
$O\big(({n}/{\eps^2})\log ({1}/{\delta})\big)$
lower bound on the expected number of trials under any policy
that finds an $\eps$-optimal coin with probability at least $1-\delta$.
In Section \ref{sec:genprob}, 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/\delta)$
dependence on $\delta$; 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/\eps^2$.
In Section \ref{sec:Bayes}, we derive a lower bound similar to the one in Section
\ref{sec:mainspecprob}, but within
a Bayesian setting, under a prior distribution on the set
of biases of the different coins.

In Section \ref{sec:regret} we provide a bound on the expected regret which is similar in spirit to the bound in
\cite{LR85}. The constants in our bounds are slightly worse than the
ones in \cite{LR85}, 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 \cite{LR85}.

The case where the coin biases are known in advance, but the
identities of the coins are not, is discussed in Section \ref{se:perms}.
We provide a policy that
finds an $\eps$-optimal coin with
probability at least $1-\delta$, under which the expected number of trials
is $O\left( (1/\eps^2) ( n + \log(1/\delta))\right)$. 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
$\Theta\big(({n}/{\eps^2})\log ({1}/{\delta})\big)$.
Finally, Section
\ref{se:con} contains some brief concluding remarks.

\section{Problem Definition}
\label{sec:probdef} The exploration problem for multi-armed
bandits is defined as follows. We are given $n$ arms. Each arm $\ell$
is associated with a sequence of identically distributed Bernoulli
(i.e., taking values in $\{0,1\}$) random variables $X^\ell_k$,
$k=1,2,\ldots$, with unknown mean $p_\ell$. Here, $X^\ell_k$ corresponds to the
reward obtained the $k$th time that arm $\ell$ is tried. We assume
that the random variables $X^\ell_k$, for $\ell=1,\ldots, n$,
$k=1,2,\ldots$, are independent, and we define
$p=(p_1,\ldots,p_n)$. Given that we restrict to the Bernoulli
case, we will use in the sequel the term ``coin'' instead of
``arm.''

A {\it 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
$\Pr_{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_\ell$ be the total number of times
that coin $\ell$ is tried, and let $T=T_1+\cdots+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 \ed-{\it
correct} if
$$\Pr_p\Big(p_I> \max_\ell p_\ell-\epsilon\Big)\geq 1-\delta,$$
for {\it every} $p\in[0,1]^n$. It was shown in \cite{EDMM02} that
there exist constants $c_1$ and $c_2$ such that for every $n$,
$\epsilon>0$, and $\delta>0$, there exists an \ed-correct policy
under which
$$\E_p[T]\leq c_1\frac{n}{\epsilon^2}\log \frac{c_2}{\delta},
\qquad \forall\ p\in [0,1]^n.$$
A matching lower bound was also
established in \cite{EDMM02}, but only for ``large'' values of
$\delta$, namely, for $\delta>1/n$. In contrast, we aim at
deriving bounds that capture the dependence of the
sample-complexity on $\delta$, as $\delta$ becomes small.



\section{A Lower Bound on the Sample Complexity}
\label{sec:mainspecprob}

We start with our central result, which can be viewed as an extension
of Lemma 5.1 from \cite{anthony_bartlett99}, as well as
a special case of
Theorem \ref{th:specificp}. 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.
\begin{theorem} \label{th:main}
There exist positive constants $c_1$, $c_2$, $\epsilon_0$, and
$\delta_0$, such that for every $n\geq 2$,
$\epsilon\in(0,\epsilon_0)$, and $\delta\in(0,\delta_0)$, and for
every \ed-correct policy, there exists
some $p\in[0,1]^n$ such that
$$\E_p[T]\geq c_1\frac{n}{\epsilon^2}\log \frac{c_2}{\delta}.$$
In particular, $\epsilon_0$ and $\delta_0$ can be taken equal to
1/8  and $e^{-4}/4$, respectively.
\end{theorem}
\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+\epsilon)/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{\epsilon}{2},\qquad p_i=\frac{1}{2}, \
{\rm for}\ i\neq 0\,,$$ which makes coin 0 the best coin.
Furthermore, for $\ell=1,\ldots,n$, there is a hypothesis
$$
H_\ell:\ p_0=\frac{1}{2}+\frac{\epsilon}{2},\qquad
p_\ell=\frac{1}{2}+\epsilon, \qquad p_i=\frac{1}{2},\ {\rm for}\
i\neq 0,\ell\,,$$ which makes coin $\ell$ the best coin.


We define $\epsilon_0=1/8$ and $\delta_0=e^{-4}/4$.
From now on, we fix
some $\eps\in(0,\eps_0)$ and $\delta\in(0,\delta_0)$, and a policy,
which we assume to be
($\epsilon/2$,$\delta$)-correct . If $H_0$ is true, the policy must
have probability at least $1-\delta$ of eventually stopping and
selecting coin 0. If $H_\ell$ is true, for some $\ell\neq 0$, the policy
must have probability at least $1-\delta$ of eventually stopping
and selecting coin $\ell$. We denote by $\E_\ell$ and $\Pr_\ell$ the
expectation and probability, respectively, under hypothesis $H_\ell$.

We define $t^*$ by
\be
\label{eq:tstardef}
t^* = \frac{1}{c\eps^2}\log\frac{1}{4\delta}
= \frac{1}{c\eps^2}\log\frac{1}{\theta}  ,
\ee
where $\theta= 4\delta$, and
where $c$ is an absolute constant whose value will be specified
later.\footnote{In this and subsequent proofs, and in order to avoid
repeated use of truncation symbols, we treat $t^*$ as if it were
integer.} Note that $\theta<e^{-4}$ and $\epsilon<1/4$.

Recall that $T_\ell$ stands for the number of times that coin
$\ell$ is tried. We assume  that for some coin $\ell\neq 0$, we have
$\E_0[T_\ell] \leq t^*$. We will eventually show that under this assumption,
the probability of selecting $H_0$
under $H_\ell$ exceeds $\delta$, and violates
($\epsilon/2$,$\delta$)-correctness. It will then follow
that we must have $\E_0[T_\ell] > t^*$ for all $\ell\neq 0$.
Without loss of generality, we can and will
assume that the above condition holds for $\ell=1$, so that $\E_0[T_1] \leq 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 \le 4 t^*\},$$
and obtain
$$t^*\geq \E_0[T_1]
\geq 4t^* \Pr_0(T_1> 4t^*)= 4t^*\big(1-\Pr_0(T_1\leq 4t^*)\big),$$
from which it follows that
$$\Pr_0 (A) \geq 3/4.$$


We define $K_t=X^1_1+\cdots+X^1_t$, 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 = \Big\{  \displaystyle{ \max_{1\le t \le
4t^*} \Big|K_t - \frac{1}{2} t\Big| < \sqrt{t^*
\log{(1/\theta)}}\Big\}.}$$

We now establish two lemmas that will be used in the sequel.
\begin{lemma}\label{le:kolmogorov}
We have $\Pr_0(C) > 3/4$.
\end{lemma}
\proof
We will prove a more general result:\footnote{The proof for a general $p_i$ will be useful
later.} we assume that coin $i$ has bias $p_i$ under hypothesis $H_\ell$,  define $K^i_t$ as the number of unit
rewards (``heads'') if coin $i$ is tested for $t$ (not necessarily consecutive) times,
and let
$$C_i = \Big\{  \displaystyle{ \max_{1\le t \le
4t^*} \Big|K^i_t - p_i t\Big| < \sqrt{t^*
\log{(1/\theta)}}\Big\}.}$$
First, note that $K^i_t - p_i t$ is a $\Pr_{\ell}$-martingale (in the context of Theorem \ref{th:main}, $p_i=1/2$ is the bias
of coin $i=1$ under hypothesis $H_0$).
Using Kolmogorov's inequality \citep[Corollary 7.66, in p.\ 244 of][]{Ross},
the probability of the complement of
$C_i$ can be bounded as follows:
$$
\Pr_{\ell} \left(\max_{1\le t \le 4t^*} \Big| K^i_t -p_i t\Big|
\ge \sqrt{t^*
\log{(1/\theta)}}\right )
\le  \frac {\E_{\ell} \big[(K^i_{4t^*} -4p_i  t^*)^2\big]}{t^*
\log{(1/\theta)}}.
$$
Since $\E_{\ell} \big[\big(K^i_{4t^*} - 4 p_i t^*)^2\big]
=   4p_i(1-p_i)t^*$, we
obtain
\be \label{eq:C_ibound}
\Pr_{\ell}(C_i) \geq  1- \frac{4 p_i(1-p_i)}{ \log{(1/\theta)}}>
\frac{3}{4},\ee
where
the last inequality follows because $\theta< e^{-4}$ and
$4p_i (1-p_i)\le1$.
\qed

\begin{lemma}
\label{le:aux}
If $0\leq x\leq 1/\sqrt{2} $ and
$y\ge 0$, then
$$
(1-x)^y \ge e^{-dxy},
$$
where $d=1.78$.
\end{lemma}
\proof A straightforward calculation shows that $\log (1-x) + dx
\ge 0 $ for $0\le x \le 1/\sqrt{2}$. Therefore, $y (\log (1-x) + dx) \ge
0$ for every $y\ge 0$. Rearranging and exponentiating, leads to
$(1-x)^y \ge e^{-dxy}$. \qed


We now let $B$ be the event that $I=0$, i.e., that the policy
eventually selects coin 0. Since the policy is
($\epsilon/2$,$\delta$)-correct for $\delta<e^{-4}/4< 1/4$, we have
$\Pr_0(B)> 3/4$. We have already shown that  $\Pr_0(A)\ge 3/4$ and
$\Pr_0(C)> 3/4$. Let $S$ be the event
that $A$, $B$, and $C$ occur, that is $S=A\cap B \cap C$. We then
have $\Pr_0 (S)> 1/4$.

\begin{lemma} If $\E_0[ T_1] \leq t^*$ and $c\ge 100$, then
$\Pr_1(B) > \delta$. \label{le:pspec}
\end{lemma}
\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_\ell$ by letting
$$L_\ell(w)=\Pr_\ell(W=w),$$
for every possible history $w$. Note that this function can be
used to define a random variable $L_\ell(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
\begin{eqnarray}
\frac{L_1(W)}{L_0(W)} & = &
\frac{(\half+\eps)^{K}(\half-\eps)^{T_1 - K}}{(\half) ^ {T_1}}
\nonumber\\ &= &(1+2\eps)^{K} (1-2\eps)^{K} (1-2\eps)^{T_1 - 2K}
\nonumber\\ & = & (1 - 4\eps^2)^{K} (1-2\eps)^{T_1 - 2K}.
\label{eq:dp1dp0}
\end{eqnarray}
We will now proceed to lower  bound the terms in the right-hand
side of Eq.~(\ref{eq:dp1dp0}) when event $S$ occurs.

If event $S$ has occurred, then $A$ has occurred, and we have $K
\le T_1 \le 4t^*$, so that
\begin{eqnarray*}
(1-4\eps^2)^K \ge (1-4\eps^2)^{4t^*} & = &
(1-4\eps^2)^{({4}/({c\eps^2}))
\log(1/\theta)} \\
& \ge & e^{-({16d}/{c}) \log(1/\theta)} \\ & = &\theta ^{16d/c}.
\end{eqnarray*}
We have used here Lemma \ref{le:aux}, which applies because
$4\epsilon^2<4/4^2<1/\sqrt{2}$.

Similarly, if event $S$ has occurred, then $A\cap C$ has occurred,
which implies,
$$T_1 -2 K\le 2 \sqrt{t^* \log(1/\theta)}=\big(2/\epsilon\sqrt{c}\big) \log(1/\theta),$$
where the equality above made use of the definition of $t^*$. Therefore,
\begin{eqnarray*}
(1-2\eps)^{T_1-2K} & \ge & (1-2\eps)^{\big(2/\epsilon\sqrt{c}\big) \log(1/\theta)}
\\ &\ge& \ e^{-(4d/\sqrt{c})\log(1/\theta)} \\
&=&\theta^{4d/\sqrt{c}}.
\end{eqnarray*}
Substituting the above in Eq.~\req{eq:dp1dp0}, we obtain
$$
\frac{L_1(W)}{L_0(W)} \ge \theta ^{({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
$\theta=4\delta$ whenever the event $S$ occurs. More precisely, we have
$$\frac{L_1(W)}{L_0(W)} 1_S \geq 4\delta 1_S,$$
where $1_S$ is the indicator function of the event $S$. Then,
$$
\Pr_1(B) \ge \Pr_1 (S) = \E_1[  1_{S}] = \E_0\left[
\frac{L_1(W)}{L_0(W)} 1_{S} \right]\geq \E_0 [4\delta 1_{S}] =
4\delta \Pr_0(S) > \delta,
$$
where we used the fact that $\Pr_0(S)>1/4$.
\qed

To summarize, we have shown that when $c\geq 100$,
if
$\E_0[T_1]\leq(1/c\epsilon^2)\log(1/(4\delta))$, then
$\Pr_1(B)>\delta$. Therefore, if we have an
$(\epsilon/2,\delta)$-correct policy, we must have
$\E_0[T_\ell]> (1/c\epsilon^2)\log(1/(4\delta))$, for every $\ell>0$.
Equivalently, if we have an $(\epsilon,\delta)$-correct policy, we
must have $\E_0[T]>(n/(4c\epsilon^2))\log(1/(4\delta))$, which is of
the desired form. \qed


\section{A Lower Bound on the Sample Complexity - General Probabilities}
\label{sec:genprob}
In Theorem \ref{th:main}, 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 \ref{th:main} 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\geq p_\ell$ for all $\ell$, the policy that
immediately selects coin 1 is ``optimal.'' However, such a policy
will not be $(\epsilon,\delta)$-correct for {\em 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\}$.
\begin{theorem} \label{th:specificp}
Fix some $\underline{p}\in (0,1/2)$. There exists a positive constant
$\delta_0$, and a positive constant $c_1$
that depends only on $\underline{p}$, such that for every
$\eps\in(0,1/2)$, every $\delta\in (0,\delta_0)$, every
$p\in[0,1/2]^n$, and  every \ed-correct policy, we have
$$
\E_p[T]\geq c_1 \left\{ \frac{(|M(p,\eps)| - 1)^+}{\eps^2} +
\sum_{\ell \in N(p,\eps)}  \frac{1}{(p_*-p_\ell)^2}\right\} \log
\frac{1}{8\delta} ,$$ where $p_*=\max_i p_i$,
\begin{equation}
\label{eq:pellp1M} M(p,\eps)   =   \Big\{  \ell: \ p_\ell > p_*
-   \eps, \ {\rm and } \   p_\ell > \mbox{$\underline{p}$},\ { \rm
and } \ p_\ell\geq  \frac{\eps + p_*}{1+\sqrt{1/2}}  \Big\}\,,
\end{equation}
and
\begin{equation}
N(p,\eps)  =  \Big\{  \ell: p_\ell \leq p_* -  \eps, \ {\rm and } \
p_\ell>\underline{p}   , \ {\rm and } \ p_\ell\geq  \frac{\eps +
p_*}{1+\sqrt{1/2}}
 \Big\} \label{eq:pellp1N} \,.
\end{equation}
In particular, $\delta_0$ can be taken equal to
$e^{-8}/8$.
\end{theorem}
\noindent {\bf Remarks:}
\begin{itemize}
\item[(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,\eps)$
contains coins that are within $\eps$ 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,\eps)$ contains coins
whose bias is more than $\eps$ 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,\eps)$.
\item[(b)]
The expression $({\eps + p_*})/({1+\sqrt{1/2}})$ in
Eqs.~(\ref{eq:pellp1M}) and (\ref{eq:pellp1N}) can be replaced by
$({\eps+p_*})/({2-\alpha})$ for any positive constant $\alpha$, by
changing some of the constants in the proof.
\item[(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 \ref{rem:c1dep}),
but does not provide any new insights.
\end{itemize}
\proof Let us fix $\delta_0=e^{-8}/8$, some $\underline{p}\in (0,1/2)$,
$\eps\in(0,1/2)$, $\delta\in(0,\delta_0)$,  an \ed-correct policy,
and some $p\in[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, \mbox{ for $i=1,\ldots,n$} \,,$$
and for $\ell=1,\ldots,n$,
$$
H_\ell: q_\ell = p_1 + \eps,\qquad   q_i=p_i,\  \mbox{for $i\neq
\ell$}.
$$
If hypothesis $H_\ell$ is true, the policy must
select coin $\ell$. We will bound from below the expected number
of times the coins in the sets $N(p,\eps)$ and $M(p,\eps)$ must be
tried, when hypothesis $H_0$ is true. As in Section
\ref{sec:mainspecprob},  we use $\E_{\ell}$ and $\Pr_{\ell}$ to
denote the expectation and probability, respectively, under the
policy being considered and under hypothesis $H_\ell$.

We define $\theta = 8 \delta$, and note that $\theta < e^{-8}$.
Let
\[
t^*_\ell = \left\{
\begin{array}{ll}
\displaystyle{ \vspace{5pt} \frac{1}{c\eps^2} \log
\frac{1}{\theta}}, & {\rm if}\ \
\ell \in M(p,\eps),\\
\displaystyle{ \frac{1}{c(p_1-p_\ell)^2} \log \frac{1}{\theta} }, \quad&
{\rm if}\ \ell \in N(p,\eps), \end{array} \right.
\]
where $c$ is a constant that only depends on $\underline{p}$, and
whose value will be chosen later. Recall that $T_\ell$ stands for the
total number of times that coin $\ell$ is tried. We define the event
$$A_\ell = \{ T_\ell \le 4 t^*_\ell \}.$$
As in the proof of Theorem \ref{th:main}, if $\E_0[T_\ell] \leq
t^*_\ell$, then $\Pr_0 (A_\ell)  \geq 3/4$.

We define
$K^\ell_t=X^\ell_1+\cdots+X^\ell_t$, which is the number of unit
rewards (``heads'') if the $\ell$-th coin is tried  a total  of $t$  (not
necessarily consecutive) times. We let $C_\ell$ be the event defined
by
$$C_\ell = \Big\{  \displaystyle{ \max_{1\le t \le
4t^*_{\ell}} |K^\ell_t - p_\ell t| < \sqrt{t^*_\ell
\log{(1/\theta)}}\Big\}.}$$
Similar to Lemma \ref{le:kolmogorov}, and since $\theta=8\delta<e^{-8}$, we have\footnote{The derivation is identical to
Lemma \ref{le:kolmogorov} except for Eq. (\ref{eq:C_ibound}), where one
should replace the assumption that $\theta < e^{-4}$ with the stricter assumption that
$\theta < e^{-8}$ used here.}
$$\Pr_0(C_\ell) > 7/8.$$


Let $B_\ell$ be the event $\{I = \ell\}$,
i.e., that the policy eventually selects  coin $\ell$, and let
$B_{\ell}^c$ be its complement. Since the policy is \ed-correct
with $\delta< \delta_0 < 1/2$, we must have
$$\Pr_0(B^c_\ell)> 1/2,\qquad \forall \ \ell\in N(p,\eps).$$
We also have $\sum_{\ell \in M(p,\eps)} \Pr_0(B_{\ell}) \leq 1$,
so that the inequality $\Pr_0(B_{\ell})>1/2$ can hold for at most
one element of $M(p,\eps)$. Equivalently, the inequality
$\Pr_0(B_{\ell}^c)\leq 1/2$ can hold for at most one element of
$M(p,\eps)$. Let
$$
M_0(p,\eps)=\Big\{ \ell \in M(p,\eps) \ {\rm
and}\  \Pr_0 (B^c_\ell) > \frac{1}{2}\Big\}.$$
It follows that $| M_0(p,\eps)| \ge \big(|M(p,\eps)| -1 \big)^+$.
%The following elementary fact will be used later.

%\begin{lemma}\label{le:logineq}
%If $b\ge 1$, $a>0$, and $a\ge y\ge0$, then
%$$
%\left(1-\frac{y}{a}\right)^b \ge 1- \frac{b}{a} \cdot y.
%$$
%\end{lemma}
%\proof
%If $b\ge 1$, then the function $\delta\mapsto (1-\delta)^b$ is convex for $\delta\in[0,1]$.
%Thus, the function $(1-\delta)^b$ is no smaller than its first order Taylor series expansion
%at $\delta=0$, which is $1-b\delta$. Letting $\delta=y/a$, we obtain the desired result.
 %\qed

The following
lemma is an analog of Lemma \ref{le:pspec}.
\begin{lemma}\label{le:51}
Suppose that $\ell \in M_0(p,\eps)\cup
N(p,\eps)$ and that
 $\E_0[T_\ell] \leq t^*_\ell$. If the constant $c$ in the definition of $t^*$ is chosen large
enough (possibly depending on $\underline{p}$), then
$\Pr_\ell(B^c_\ell) > \delta$.
\end{lemma}
\proof  Fix some $\ell \in M_0(p,\eps)\cup N(p,\eps)$.
For future reference, we note that the definitions of $M(p,\eps)$ and $N(p,\eps)$
include the condition $p_{\ell}\geq (\eps+p_*)/(1+\sqrt{1/2})$. Recalling that $p_*=p_1$, $p_{\ell}\leq 1/2$, and using
the definition $\Delta_{\ell}=p_1-p_{\ell}\geq 0$, some easy algebra leads to the conditions
\begin{equation}\label{eq:factoid}
\frac{\eps +\Delta_{\ell}}{1-p_{\ell}}\leq \frac{\eps+\Delta_{\ell}}{p_{\ell}}\leq \frac{1}{\sqrt{2}}.
\end{equation}

We define
the event  $S_\ell$ by
$$S_\ell=A_\ell\cap
B_\ell^c \cap C_\ell.$$
Since $\Pr_0(A_{\ell})\ge 3/4$,
$\Pr_0(B_{\ell}^c)> 1/2$, and $\Pr_0(C_{\ell})> 7/8$, we
have
$$\Pr_0 (S_\ell)> \frac{1}{8}, \qquad\forall \ \ell \in M_0(p,\eps) \cup
N(p,\eps).$$
As in the proof of Lemma \ref{le:pspec},
we define the likelihood function $L_\ell$ by letting
$$L_\ell(w)=\Pr_\ell(W=w),$$
for every possible history $w$, and use again $L_\ell(W)$ to
define the corresponding
 random variable.

Let $K$ be a shorthand notation for $K_{T_\ell}^{\ell}$, the total
number of  unit rewards (``heads'') obtained from coin $\ell$. We
have
\begin{eqnarray*}
\frac{L_\ell(W)}{L_0(W)} & = &
\frac{(p_1+\eps)^{K}(1-p_1-\eps)^{T_\ell - K}}{p_\ell ^
K(1-p_\ell)^{T_\ell -K}} \\
& = &\left(\frac{p_1}{p_\ell} +\frac{\eps}{p_\ell}\right)^{K}
\left(\frac{1-p_1}{1-p_\ell} -
\frac{\eps}{1-p_\ell}\right)^{T_\ell - K} \nonumber\\ & = &
\left(1 + \frac{  \eps+\Delta_\ell}{p_\ell}\right)^K
\left(1-\frac{\eps + \Delta_\ell}{1-p_\ell}\right)^{T_\ell -K},
\end{eqnarray*}
where we have used the definition $\Delta_\ell = p_1 - p_\ell$. It follows that
\begin{eqnarray}\frac{L_\ell(W)}{L_0(W)} & = & \left(1 + \frac{\eps+\Delta_\ell }{p_\ell}\right)^K\left(1 -
\frac{\eps+\Delta_\ell}{p_\ell}\right)^K \left(1 -
\frac{\eps+\Delta_\ell}{p_\ell}\right)^{-K} \left(1-\frac{
\eps+\Delta_\ell}{1-p_\ell}\right)^{T_\ell -K} \nonumber\\
& = & \left(1 - \left( \frac{\eps+\Delta_\ell}{p_\ell}\right)^2
\right)^K \left(1 - \frac{\eps+\Delta_\ell}{p_\ell}\right)^{-K}
\left(1-\frac{\eps+\Delta_\ell}{1-p_\ell}\right)^{T_\ell -K}\nonumber\\
& = & \left(1 - \left( \frac{\eps+\Delta_\ell}{p_\ell}\right)^2\right)^K
\left(1 - \frac{\eps+\Delta_\ell}{p_\ell}\right)^{-K}
\left(1-\frac{\eps+\Delta_\ell}{1-p_\ell}\right)^{K(1-p_\ell)/p_{\ell} } \nonumber\\
& & \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
 \cdot \left(1-\frac{\eps+\Delta_\ell}{1-p_\ell}\right)^{(p_{\ell}T_\ell -K)/p_\ell}
\,. \label{eq:dp1dp0again}
\end{eqnarray}

We will now proceed
to lower  bound  the right-hand side of Eq.~(\ref{eq:dp1dp0again})
for  histories under which event $S_\ell$ occurs. If event
$S_\ell$ has occurred, then $A_\ell$ has occurred, and we have $K
\le T_\ell \le 4t^*$, so that for every $\ell \in N(\eps,p)$, we
have
\begin{eqnarray*}
\left(1-\left(\frac{\eps+\Delta_\ell}{p_\ell}\right)^2\right)^K
&\ge&
\left(1-\left(\frac{\eps+\Delta_\ell}{p_\ell}\right)^2\right)^{4t^*_\ell}
\\
& = & \left(1-\left(\frac{\eps+\Delta_\ell}{p_\ell}\right)^2
\right)^{({4}/{c\Delta_\ell^2})
\log(1/\theta)} \\
& \stackrel{a}{\ge} & \exp\left\{-d\frac{4}{c}
\Big(\frac{(\eps/\Delta_\ell)+1}{p_\ell}\Big)^2
\log(1/\theta)\right\}
\\ &
\stackrel{b}{\ge}  &   \exp\left\{-d \frac{16}{c{p_\ell}^2}
\log(1/\theta)\right\} \\ & =&  \theta ^ {16\,
d/p_\ell ^2 c}.
\end{eqnarray*}
In step (a), we have used Lemma \ref{le:aux}
which applies because of Eq. (\ref{eq:factoid});
in step (b), we used
the fact  $\eps/\Delta_\ell \le 1$, which holds because
$\ell\in N(\eps,p)$.

Similarly, for $\ell \in M(\eps,p)$, we have
\begin{eqnarray*}
\left(1-\left(\frac{\eps+\Delta_\ell}{p_\ell}\right)^2\right)^K
&\ge&
\left(1-\left(\frac{\eps+\Delta_\ell}{p_\ell}\right)^2\right)^{4t^*_\ell}
\\
& = &
\left(1-\left(\frac{\eps+\Delta_\ell}{p_\ell}\right)^2\right)^{({4}/{c\eps
^2})
\log(1/\theta)} \\
& \stackrel{a}{\ge} & \exp\left\{-d \frac{4}{c}\Big(\frac{1+
(\Delta_\ell/\eps)}{p_\ell}\Big)^2
\log(1/\theta)\right\} \\ & \stackrel{b}{\ge}  &   \exp\left\{-d
\frac{16}{c{p_\ell}^2} \log(1/\theta)\right\} \\ & = & \theta
^ {16 d/p_\ell ^2 c}.
\end{eqnarray*}
In step (a), we have again used Lemma \ref{le:aux}; in step (b), we used
the fact  $\Delta_\ell/\eps \le 1$, which holds because
$\ell\in M(\eps,p)$.

We now bound the product of the second and
third terms in Eq.~(\ref{eq:dp1dp0again}).

If $b\geq 1$, then the
mapping $y\mapsto (1-y)^b$  is convex for $y\in[0,1]$. Thus,
$(1-y)^b\geq 1-by$, which implies that
$$
\left(1-\frac{\eps+\Delta_\ell}{1-p_\ell}\right)^ {(1-p_\ell) /p_{\ell}} \ge
\left(1-\frac{\eps+\Delta_\ell}{p_\ell}\right),
$$
so that the product of the second and third terms can be lower bounded by
\begin{eqnarray*}
\left(1 - \frac{\eps+\Delta_\ell}{p_\ell}\right)^{-K}
\left(1-\frac{\eps+\Delta_\ell}{1-p_\ell}\right)^{K (1-p_\ell)/p_{\ell}} \ge
\left(1 - \frac{\eps+\Delta_\ell}{p_\ell}\right)^{-K}
\left(1-\frac{\eps+\Delta_\ell}{p_\ell}\right)^{K } = 1.
\end{eqnarray*}

We still need to bound the fourth term of Eq.~(\ref{eq:dp1dp0again}).
We start with the case where $\ell \in N(p,\eps)$. We have
\begin{eqnarray}
\left(1- \frac{\eps +\Delta_\ell}{1-p_\ell} \right)^{(p_{\ell}T_\ell -K)/p_\ell}
 & \stackrel{a}\ge &\left(1- \frac{\eps
+\Delta_\ell}{1-p_\ell} \right)^{({1}/{p_\ell}) \sqrt{t^*_\ell \log (
{1}/\theta)}}
\label{eq:4thtermtstart}\\
& \stackrel{b}{=} & \left(1- \frac{\eps
+\Delta_\ell}{1-p_\ell} \right)^{({1}/{p_\ell \sqrt{c} \Delta_\ell}) \log (
{1}/\theta)} \nonumber\\
& \stackrel{c}{\ge} & \exp\left\{-\frac{d}{\sqrt{c}}\cdot \frac{\eps
+\Delta_\ell }{\Delta_\ell(1-p_\ell)p_\ell} \log
({1}/\theta)\right\} \label{eq:stageb}\\ &
\stackrel{d}{\ge}  & \exp\left\{ -\frac{2d}{\sqrt{c}(1-p_\ell)p_\ell }
\log ( {1}/\theta)\right\}\label{eq:stagec} \\
& \stackrel{e}{\ge}&   \exp\left\{ -
\frac{4d}{\sqrt{c}p_\ell } \log(1/\theta)\right\}\nonumber\\ &=&
\theta ^ { {4d }/{(p_\ell\sqrt{c})}} \nonumber\,.
\end{eqnarray}
Here, (a) holds because we
are assuming that the events $A_\ell$ and $C_\ell$ occurred;
(b) uses the definition of $t^*_\ell$ for $\ell \in N(p,\eps)$;
(c) follows from Eq.~(\ref{eq:factoid}) and Lemma \ref{le:aux};
(d) follows because $\Delta_\ell > \eps$;  and (e) holds because
$0 \le p_\ell \le 1/2$, which implies that ${1}/({1-p_\ell}) \le
2$.

Consider now the case where $\ell \in M_0(p,\eps)$.
Equation (\ref{eq:4thtermtstart}) holds for the same reasons as when $\ell \in
N(p,\eps)$. The only difference from the above calculation is in step (b), where $t^*_\ell$
should be replaced with $ (1/{c\eps^2}) \log( {1}/\theta)$.
Then, the right-hand side in Eq.~(\ref{eq:stageb}) becomes
$$
  \exp\left\{ -\frac{d}{\sqrt{c}}\cdot \frac{\eps +\Delta_\ell}{\eps (1-p_{\ell})p_{\ell}}
\log ( {1}/\theta)\right\}.
$$
For $\ell \in M_0(p,\eps)$, we have  $\Delta_\ell \le \eps$, which
implies that  $(\eps + \Delta_\ell)/{\eps} \le 2$, which then
leads to the same expression as in Eq.~(\ref{eq:stagec}). The rest
of the derivation is identical. Summarizing the above, we have
shown that if $\ell \in M_0(p,\eps) \cup N(p,\eps)$, and event
$S_{\ell}$ has occurred, then
$$
\frac{L_\ell(W)}{L_0(W)} \ge \theta ^ {({4d}/{p_\ell\sqrt{c}}) +({16 d}/{p_\ell ^2 c})} \,.
$$
For  $\ell \in M_0(p,\eps) \cup N(p,\eps)$, we have $\underline{p}<
p_\ell$. We can choose $c$ large enough so that
${L_\ell(W)}/{L_0(W)} \ge \theta = 8\delta$; the value of $c$ depends only
on the constant $\underline{p}$. Similar to the proof of
Theorem~\ref{th:main}, we have
$$\frac{L_\ell(W)}{L_0(W)} 1_{S_\ell} \geq 8\delta 1_{S_\ell},$$
where $1_{S_\ell}$ is the indicator function of the event
$S_\ell$. It follows that
$$
\Pr_\ell(B^c_\ell) \ge \Pr_\ell (S_\ell) = \E_\ell[  1_{S_\ell}] =
\E_0\left[ \frac{L_\ell(W)}{L_0(W)} 1_{S_\ell} \right]\ge \E_0
[8\delta 1_{S_\ell}] = 8\delta \Pr_0(S_\ell) >
 \delta,
$$
where the last inequality relies on the already established fact
$\Pr_0 (S_\ell) > 1/8$. \qed Since the policy is \ed-correct,
we must have $\Pr_\ell(B^c_\ell)\leq \delta$, for every $\ell$.
Lemma \ref{le:51} then implies that $\E_0[T_\ell]> t_\ell^*$
for every $\ell\in M_0(p,\eps)\cup N(p,\eps)$. We sum over all
$\ell\in M_0(p,\eps)\cup N(p,\eps)$, use the definition of
$t_\ell^*$, together with the fact $|M_0(p,\eps)|\geq
\big(|M(p,\eps)|-1\big)^+$, to conclude the proof of the theorem.
\qed
\begin{remark} {\rm 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 \leq 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.}
\label{rem:c1dep}
\end{remark}
%\begin{remark}
%{\rm
%We note that the choice of the constants in the definition of the
%events $A_\ell$ and $C_\ell$ was somewhat
%arbitrary. The specific choices made in the above proof led to
%$\delta_0 = e^{-8}/8$. In a preliminary version of this paper \cite[][]{MT03}, we used
%different constants in the definitions of  $A_\ell$ and $C_\ell$,
%and obtained a similar result
%with $\delta_0 = e^{-4}/4$. However, the choice of the events in the earlier version resulted
%in replacing the term $\big(|M(p,\eps)|-1\big)^+$ with the looser term
%$\big(|M(p,\eps)|-3\big)^+$.}
%\end{remark}


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 $\eps$
cannot be $\Theta(1/\eps^2)$ when $\max_i p_i=1$. To see this,
consider the following policy $\pi$. Try each coin $O((1/\eps)
\log(n/\delta))$ times. If one of the coins always resulted in
heads, select it. Otherwise, use some \ed-correct policy $\tilde
\pi$. It can be shown that the policy $\pi$ is \ed-correct (for
every $p\in [0,1]^n$), and that if $\max_i p_i = 1$, then $\E_p[T]
= O((n/\eps) \log(n/\delta))$.


\begin{theorem}
Fix an integer $s\geq 2$, and some $\underline{p}\in(0,1/2)$.
There exists a positive constant $c_1$ that depends only on $\underline{p}$
such that for every $\eps\in (0,2^{-(s+2)})$, every
$\delta\in(0,e^{-8}/8)$, every $p\in[0,1-2^{-s}]^n$, and  every
\ed-correct policy, we have
$$
\E_p[T]\geq \frac{c_1}{s \eta^2}  \left\{ \frac{(|M(\tilde{p},\eps
\eta)| - 1)^+}{\eps^2} + \sum_{\ell \in N(\tilde{p},\eta \eps)}
\frac{1}{(p_*-p_\ell)^2}\right\}
 \log \frac{1}{8\delta}\,,$$ where
$p_*=\max_i p_i$, $\eta=2^{s+1}/s$, $\tilde{p}$ is the vector with
components $\tilde{p}_i = 1- (1-p_i)^{ {1}/{s}}$ (for $i=1,2,\ldots,n$), and $M$ and $N$
are as defined in Theorem \ref{th:specificp}.
\end{theorem}
\proof Let us fix $s\geq 2$, $\underline{p}\in(0,1/2)$, $\eps\in
(0,2^{-(s+2)})$, and $\delta\in(0,e^{-8}/8)$. Suppose that we have
an \ed-correct policy $\pi$ whose expected time to termination is
$\E_p[T]$, whenever the vector of coin biases happens to be $p$.
We will use the policy $\pi$ to construct a new policy $\tilde
\pi$ such that
$$\Pr_{\tilde p}\Big({\tilde p}_I>\max_i {\tilde p}_i -\eta\eps\Big)\geq 1-\delta,
\qquad\forall\ {\tilde p}\in[0,(1/2)+\eta\eps]^n;$$ (we will then say that
$\tilde \pi$ is $(\eta\eps,\delta)$-correct on
$[0,(1/2)+\eta\eps]^n$). Finally, we will use the lower bounds
from Theorem~\ref{th:specificp}, applied to $\tilde\pi$, to obtain
a lower bound on the sample complexity of $\pi$.

The new policy $\tilde\pi$ is specified as follows. Run the original policy
$\pi$. Whenever $\pi$ chooses to try a certain coin $i$ once,
policy $\tilde \pi$ tries coin $i$ for $s$ consecutive times.
Policy $\tilde \pi$ then ``feeds'' $\pi$ with 0 if all $s$ trials
resulted in 0, and ``feeds" $\pi$ with 1 otherwise. If $\tilde p$ is
the true vector of coin biases faced by policy $\tilde \pi$, and
if policy $\pi$ chooses to sample coin $i$, then policy $\pi$
``sees'' an outcome which equals 1 with probability
$p_i=1-(1-\tilde p_i)^s$. Let  us define two mappings
$f,g:[0,1]\mapsto[0,1]$, which are inverses of each other, by
$$f(p_i)=1-(1-p_i)^{1/s},\qquad g(\tilde p_i)=1-(1-\tilde p_i)^s,$$
and with a slight abuse of notation, let
$f(p)=(f(p_1),\ldots,f(p_n))$, and similarly for $g(\tilde p)$.
With our construction, when policy $\tilde \pi$ is faced with a
bias vector $\tilde p$, it evolves in an identical manner as the policy $\pi$
faced with a bias vector $p=g(\tilde p)$. But under policy $\tilde
\pi$, there are $s$ trials associated with every trial under
policy $\pi$, which implies that $\tilde{T} = sT$ ($\tilde T$ is
the number of trials under policy $\tilde\pi$) and therefore
\begin{equation}\label{eq:time}
\E_{\tilde p}^{\tilde{\pi}}[\tilde T]=s\E^\pi_{g(\tilde p)}[T], \qquad\qquad
\E^{\tilde{\pi}}_{f(p)}[\tilde T]=s\E^\pi_{p}[T],
\end{equation}
where the superscript in the expectation operator indicates the policy being used.

We will now determine the ``correctness'' guarantees of policy
$\tilde \pi$. We first need some algebraic preliminaries. Let us
fix some $\tilde p\in[0,(1/2)+\eta\eps]^n$ and a corresponding
vector $p$, related by $\tilde p=f(p)$ and $p=g(\tilde p)$. Let
also $p_*=\max_i p_i$ and $\tilde p_*=\max_i\tilde p_i$. Using the
definition $\eta=2^{s+1}/s$ and the assumption $\eps<2^{-(s+2)}$, we
have $\tilde p_*\leq (1/2)+(1/2s)$, from which it follows that
$$p_*\leq 1-\left( \frac{1}{2}-\frac{1}{2s}\right)^s
=1-\frac{1}{2^s}\left(1-\frac{1}{s}\right)^s \leq
1-\frac{1}{2^s}\cdot\frac{1}{4}=1-2^{-(s+2)}.$$ The derivative
$f'$ of $f$ is monotonically increasing on $[0,1)$. Therefore,
\begin{eqnarray*}f'(p_*)&\leq& f'(1-2^{-(s+2)})
=\frac{1}{s}\left(2^{-(s+2)}\right)^{(1/s)-1}
=\frac{1}{s} 2^{-(s+2)(1-s)/s}\\
&=&\frac{1}{s} 2^{s+1-(2/s)} \leq \frac{1}{s} 2^{s+1}=\eta.
\end{eqnarray*}
Thus, the derivative of the inverse
mapping $g$ satisfies
$$g'(\tilde p_*)\geq \frac{1}{\eta},$$
which implies, using the concavity of $g$, that
$$g(\tilde p_*-\eta\eps)\leq g(\tilde p_*)-g'(\tilde p_*)\eps\eta
\leq g(\tilde p_*)-\eps.$$

Let $I$ be the coin index finally
selected by policy $\tilde \pi$ when faced with $\tilde p$, which
is the same as the index chosen by $\pi$ when faced with $p$. We
have (the superscript in the probability indicates the policy being used)
\begin{eqnarray*}
\Pr^{\tilde{\pi}}_{\tilde p} \left(\tilde p_I\leq \tilde p_*-\eta\eps\right)&=&
\Pr^{\tilde{\pi}}_{\tilde p}\left(g(\tilde p_I)\leq g(\tilde p_*-\eta\eps)\right)\\
&\leq& \Pr^{\tilde{\pi}}_{\tilde p}\left(g(\tilde p_I)\leq g(\tilde p_*)-\eps\right)\\
&=& \Pr^\pi_p\left(p_I\leq p_*-\epsilon\right)\\
&\leq& 1-\delta,
\end{eqnarray*}
where the last inequality follows because policy $\pi$ was assumed
to be \ed-correct. We have therefore established that $\tilde \pi$
is $(\eta\eps,\delta)$-correct on $[0,(1/2)+\eta\eps]^n$. We now
apply Theorem~\ref{th:specificp}, with $\eta\eps$ instead of
$\eps$. Even though that theorem is stated for a policy which is
\ed-correct for all possible $p$, the proof only requires the
policy to be \ed-correct for $p\in [0,(1/2)+\eps]^n$. This gives
a lower bound on $\E^{\tilde{\pi}}_{\tilde p}[\tilde T]$ which, using
Eq.~(\ref{eq:time}), translates to the claimed lower bound on
$\E^\pi_p[T]$. This lower bound applies whenever $p=g(\tilde p)$, for
some $\tilde p\in[0,1/2]^n$, and therefore whenever
$p\in[0,1-2^{-s}]^n$. \qed


\section{The Bayesian Setting}
\label{sec:Bayes}

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
$\Pr$, and which is the average of the measures $\Pr_p$ over the prior distribution of $p$.
We also use $\E$ to denote the expectation with respect to $\Pr$.
We then define a policy to be \ed-correct, for a
particular prior and associated measure $\Pr$, if
$$\Pr\Big(p_I> \max_i p_i-\epsilon\Big)\geq 1-\delta.$$
We then have the following result.

\begin{theorem} There exist positive constants $c_1$, $c_2$,
$\eps_0$, and $\delta_0$, such that for every $n\geq 2$ and
$\eps\in(0,\eps_0)$, there exists a
prior for the $n$-bandit problem such that for every
$\delta\in(0,\delta_0)$, and
\ed-correct policy for this prior, we have
$$\E[T]\geq c_1\frac{n}{\epsilon^2}\log \frac{c_2}{\delta}.$$
In particular, $\eps_0$ and $\delta_0$ can be taken equal to $1/8$ and $e^{-4}/12$, respectively.
\end{theorem}
\proof Let $\eps_0=1/8$ and $\delta_0=e^{-4}/12$, and let us fix $\eps\in (0,\eps_0)$ and
$\delta\in(0,\delta_0)$.
Consider the hypotheses $H_0,\ldots,H_n$,
introduced in the proof of Theorem~\ref{th:main}. Let the prior probability
of $H_0$ be $1/2$, and the
prior probability of $H_\ell$ be $1/2n$, for $\ell=1,\ldots,n$.
Fix an $(\eps/2,\delta)$-correct
policy with respect to this prior, and note that it satisfies
\be
 \E[T] \geq \frac{1}{2}\E_0[T]
  \ge \half\sum_{\ell=1}^n \E_0 [T_\ell].\label{eq:ETlowbnd}
 \ee
Since the  policy is $(\eps/2,\delta)$-correct,  we
have $\Pr(p_I > \max_\ell p_\ell -(\eps/2))\ge 1-\delta$.

As in the proof of Theorem~\ref{th:specificp},
let $B_\ell$ be  the event that the policy eventually selects coin $\ell$.
We have
$$
\half \Pr_0 (B_0) + \frac{1}{2n}\sum_{\ell=1}^n \Pr_\ell (B_\ell) \ge 1-\delta,
$$
which implies that
\be
\label{eq:PlB0sum}
\frac{1}{2n}\sum_{\ell=1}^n \Pr_\ell(B_0) \le \delta.
\ee

Let $G$ be the set of hypotheses $\ell\neq 0$ under which
the probability of selecting coin 0 is at most $3\delta$, i.e.,
$$
G = \{ \ell: 1\le \ell \le n ,\  \Pr_\ell (B_0) \leq 3\delta\}.
$$
From Eq.~(\ref{eq:PlB0sum}), we obtain
$$\frac{1}{2n}\big(n-|G|\big)3\delta<\delta,$$
which implies that $|G| > n/3$.
Following the same argument as in
the proof of Lemma \ref{le:pspec}, we obtain that there
exists a constant $c$ such that if $\delta'\in(0,e^{-4}/4)$ and
$\E_0 [T_\ell] \le (1/c\eps^2)\log(1/4\delta')$, then  $\Pr_\ell (B_0) >\delta'$.
By taking $\delta'=3 \delta$ and requiring that $\delta\in(0,e^{-4}/12)$, we see that
the inequality
$
\E_0 [T_\ell] \le (1/c\eps^2)\log (1/12 \delta)
$
implies that $\Pr_\ell (B_0) > 3\delta$ (here, $c$ is the same constant as in Lemma \ref{le:pspec}).
But for every $\ell \in G$ we have $\Pr_\ell (B_0) \le 3\delta$, and therefore
$\E_0 [T_\ell] \geq (1/c\eps^2) \log(1/12\delta)$. Then,
Eq.~(\ref{eq:ETlowbnd}) implies that
$$
\E [T] \ge \half\sum_{\ell \in G} \E_0 [T_\ell]  \ge  |G| \frac{1}{c\eps^2} \log\frac{1}{12 \delta}
\ge c_1'\frac{n}{ \eps^2} \log\frac{c_2}{\delta},
$$
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
$(\eps/2,\delta)$-correct policy satisfies  $\E[T] \ge (c_1' n / \eps^2) \log(c_2/\delta)$.
The result follows by taking a larger constant $c_1'$ (to account for having
$n+1$ and not $n$ coins, and $\eps$ instead of $\eps/2$).
\qed




\section{Regret Bounds}
\label{sec:regret}


In this section we consider lower bounds on the regret of {\em any} policy, and show that one can derive
the $\Theta(\log t)$ regret bound of
\cite{LR85} using the techniques in this paper.
The results of \cite{LR85} are asymptotic as $t\to \infty$, whereas ours deal with
finite times $t$.
Our lower bound has similar dependence in $t$ as the upper bounds given by \cite{AuerCesaBianchiFischer02}
for some natural sampling algorithms.
As in \cite{LR85} and \cite{AuerCesaBianchiFischer02}, 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.

\begin{theorem}
\label{th:regbndspecial}
There exist positive constants $c_1,c_2,c_3,c_4$, and a constant $c_5$,
such that for every
$n\geq 2$, and for every policy, there exists some $p\in[0,1]^n$ such that for all
$t\ge 1$,
\begin{equation}
\label{eq:Expectedregret}
\E_p [R_t] \geq \min \big\{c_1 t,\  c_2 n  +c_3t , \ c_4 n  (\log t - \log n + c_5   )\big\}.
\end{equation}
\end{theorem}

The inequality \req{eq:Expectedregret} 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 $\log t$, 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.~\req{eq:Expectedregret}, it will follow that the bound also holds for at least one of
the hypotheses.
Consider the same scenario as in Theorem \ref{th:main}, where we have $n+1$ coins
and $n+1$ hypotheses $H_0, H_1,\ldots, 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,\ldots,H_n$.
Similar to Theorem \ref{th:main}, we will use the notation $\E_\ell$ and $\Pr_\ell$ to denote
expectation and probability when the $\ell$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_\ell$ as the number of times coin $\ell$ is tried in the first $t$ time steps.
The expected regret when $H_0$ is true is
$$
\E_0 [R_t] = \frac{\eps}{2}\sum_{ \ell=1 }^n  \E_0 [T_\ell],
$$
and the expected regret when $H_\ell$ ($\ell=1,\ldots,n$) is true is
$$
\E_\ell [R_t] = \frac{\eps}{2} \E_\ell [T_0] + \eps \sum_{ i\neq 0,\ell}  \E_\ell [T_i],
$$
so that the expected (Bayesian) regret is
\be
\label{eq:Eregret}
\E [R_t]  =   \half\cdot \frac{\eps}{2} \sum_{\ell=1}^n \E_0 [T_\ell] +
\frac{\eps}{2}\cdot \frac{1}{2n} \sum_{\ell=1}^n \E_\ell [T_0] +
\frac{\eps}{2n} \sum_{\ell=1}^n \sum_{i\neq 0,\ell}  \E_{\ell} [T_i].
\ee

Let $D$ be the event that coin 0 is tried at least $t/2$ times, i.e.,
$$
D = \{ T_0 \ge t/2\}\,.
$$
We consider separately the two cases $\Pr_0 (D) < 3/4 $ and $\Pr_0 (D) \geq 3/4 $.
Suppose first that $\Pr_0 (D) < 3/4 $.
In that case, $\E_0[T_0] < {7}t/{8}$, so that
$\sum_{\ell=1}^n \E_0 [T_\ell] \ge t/8$.
Substituting in Eq.~(\ref{eq:Eregret}), we obtain
$\E[R_t] \geq \eps t / 32$. This gives the first term in the right-hand side of
Eq.~\req{eq:Expectedregret}, with
$c_1=\eps/32$.

We assume from now on that $\Pr_0 (D) \geq 3/4 $.
Rearranging Eq.~(\ref{eq:Eregret}), and omitting the third term, we have
$$
\E [R_t] \ge \frac{\eps}{4} \sum_{\ell=1}^n \left(
\E_0 [T_\ell] + \frac{1}{n}\E_\ell [T_0] \right).
$$
Since $\E_\ell [T_0] \ge (t/2) \Pr_\ell(D)$, we have
\begin{equation}\label{eq:rr}
\E [R_t] \ge \frac{\eps}{4} \sum_{\ell=1}^n \left(
\E_0 [T_\ell] + \frac{t}{2n}\Pr_\ell(D) \right).
\end{equation}


For every $\ell\neq 0$, let us define $\delta_{\ell}$ by
$$\E_0 [T_\ell] = \frac{1}{c\eps ^2} \log\frac{1}{4\delta_\ell}.$$
(Such a $\delta_\ell$ exists because of the monotonicity of the mapping $x\mapsto \log(1/x)$.)
Let $\delta_0=e^{-4}/4$. If $\delta_\ell< \delta_0$, we argue exactly as in Lemma \ref{le:pspec}, except that the event $B$ in that lemma is
replaced by event $D$. Since $\Pr_0(D)\ge 3/4$, the same proof applies and shows that  $\Pr_\ell (D) \geq\delta_\ell$, so that
$$\E_0 [T_\ell] + \frac{t}{2n}\Pr_\ell(D)\geq
\frac{1}{c \eps^2} \log\frac{1}{4 \delta_\ell} + \frac{t}{2n} \delta_{\ell}.$$
If on the other hand, $\delta_{\ell}\geq \delta_0$,
then
$\E_0 [T_\ell] \leq  (1/c\eps ^2) \log(1/4\delta_0)$, which implies (by the earlier analogy with Lemma \ref{le:pspec}) that
$\Pr_\ell(D)\geq \delta_0$, and
$$\E_0 [T_\ell] + \frac{t}{2n}\Pr_\ell(D)\geq
\frac{1}{c \eps^2} \log\frac{1}{4 \delta_\ell} + \frac{t}{2n} \delta_{0}.$$

Using the above bounds in Eq.~(\ref{eq:rr}), we obtain
\be
\E [R_t] \ge \frac{\eps}{4} \sum_{\ell=1}^n
\left(
\frac{1}{c \eps^2} \log\frac{1}{4 \delta_\ell} + h(\delta_\ell)\frac{t}{2n} \right),
\label{eq:regbndbeforeopt}
\ee
where $h(\delta)=\delta$ if $\delta<\delta_0$, and $h(\delta)=\delta_0$ otherwise.
We can now view the $\delta_\ell$ as free parameters, and conclude that $\E[R_t]$ is
lower bounded by the minimum of the right-hand side of Eq.~(\ref{eq:regbndbeforeopt}),
over all $\delta_{\ell}$.
When optimizing, all the $\delta_\ell$ will be set to the same value. The minimizing value
can be  $\delta_0$, in which case we have
$$
\E [R_t] \ge  \frac{n}{4c \eps} \log\frac{1}{4\delta_0} + \delta_0 \frac{\eps}{8} t .
$$
Otherwise, the minimizing value is
$\delta_\ell = n/2c t \eps^2$, in which case we have
$$
\E [R_t] \ge \left( \frac{1}{16 c \eps} + \frac{1}{4c \eps} \log(c\eps^2/2)\right) n + \frac{1}{4c\eps} n \log(1/n) + \frac{n}{4c\eps}\log t.
$$
Thus,
the theorem holds with $c_2 = (1/4c\eps) \log (1/4\delta_0)$, $c_3 = \delta_0 \eps /8$,
$c_4 = 1/4c\eps$,  and $c_5 = (1/4) +\log(c\eps^2/2)$.
\qed


\section{Permutations}
\label{se:perms}


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\in[0,1]^n$, and we are told that the true vector $p$ of coin biases is
of the form
$p=q\circ \sigma$, where $\sigma$ is an unknown permutation of
the set $\{1,\ldots,n\}$, and where $q \circ \sigma$ stands for permuting the
components of the vector $q$ according to $\sigma$, i.e.,
$(q\circ \sigma)_\ell=q_{\sigma(\ell)}$.
We say that a policy is \qedc-correct
if the coin $I$ eventually selected satisfies
$$\Pr_{q\circ\sigma}\Big(p_I> \max_\ell q_\ell
-\epsilon\Big)\geq 1-\delta,$$
for every permutation $\sigma$ of the set
$\{1,\ldots,n\}$.
We start with  a $O\left((n+\log(1/\delta))/\eps^2\right)$ 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 \ref{sec:mainspecprob} and \ref{sec:genprob}).
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 \qedc-correct policy, there is a $\Theta\big((n/\eps^2) \log(1/\delta)\big)$
lower bound on the maximum number of trials.
We note that in the median
elimination algorithm of \cite{EDMM02}, 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 \ref{sec:mainspecprob}: the lower bound in that section applies under both criteria, as does the matching upper bound from \cite{EDMM02}.

\subsection{An Upper Bound on the Expected Number of Trials}
\label{sec:permsupper}

Suppose we are given a vector $q\in[0,1]^n$, and we are told that the true vector $p$ of coin biases is
a permutation of $q$. The policy in Table
\ref{fig:findepsoptknownmax} takes as input the accuracy $\eps$,
the confidence parameter $\delta$, and the vector $q$. In fact the policy only
needs to know the bias of the best coin, which we denote by $q^* = \max_\ell q_\ell$.
The policy also uses an additional parameter $\delta'\in(0,1/2]$.

\begin{table}[h]
\begin{center}
\begin{tabular}{|p{14cm}|}
\hline
\vspace{1pt}
Input: Accuracy and confidence parameters $\eps\in(0,1)$ and $\delta\in(0,1)$; the
bias of the best coin $q^*$.  \vspace{5pt}\\
\hline
\vspace{1pt}
Parameter: $\delta' \leq 1/2$\vspace{5pt}.\\

\hline
\vspace{1pt}
0. $k=1$;\\
1. Run the median elimination algorithm to find a coin $I_k$ whose bias is within $\eps/3$\\
\hskip14pt
of $q^*$, with probability at least $1-\delta'$. \\
2. Try coin $I_k$ for $m_k=\lceil (9/2\eps^2) \log(2^k/\delta)\rceil$ times. \\
\hskip14pt
Let
$\hat{p}_k$ be the fraction of these trials that result in ``heads.''\\
3. If $\hat{p}_k \geq q^* -2\eps/3$ declare that coin $I_k$ is an
$\eps$-optimal coin and terminate.\\
4.  Set $k:=k+1$ and go back to Step 1.
\vspace{5pt}
\\
\hline
\end{tabular}
\caption{A policy for finding an $\eps$-optimal coin when the bias of the best coin is known.\label{fig:findepsoptknownmax}}
\end{center}
\end{table}


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

\begin{theorem}\label{th:perm1}
For every $\delta' \in (0,1/2]$, $\eps\in(0,1)$, and $\delta\in(0,1)$, the policy in Table \ref{fig:findepsoptknownmax} is
guaranteed to terminate after a finite number of steps, with probability 1, and is \qedc-correct.
For every permutation $\sigma$, the expected number of trials  satisfies
$$
\E_{q\circ \sigma}[T] \leq \frac{1}{\eps^2}\left(c_1n + c_2\log\frac{1}{\delta}\right),$$
for some positive constants $c_1$ and $c_2$ that depend only on $\delta'$.
\end{theorem}
\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
\begin{equation}
\Pr \big(|\hat{p}_{k}-p_{I_k}| \ge \eps/3\big)
 \le  \exp\{-2(\eps/3)^2 m_k\} \leq \frac{\delta}{2^k}. \label{eq:step3mistake}
\end{equation}

\def\texitem#1{\par\vskip3pt\noindent\hangindent 20pt
               \hbox to 20pt {\hss #1 ~}\ignorespaces}

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-\delta'\geq 1/2$ that $p_{I_k}\geq q^*-(\eps/3)$, in which case, from Eq.\ (\ref{eq:step3mistake}),
there is probability at least $1-(\delta/2^k) \ge 1/2$ that ${\hat p}_k \geq q^*-(2\eps/3)$.
Thus, $\Pr(K>k\mid K>k-1)\leq 1-\eta$, with $\eta= 1/4$.
Consequently, the probability that the policy does not terminate by the $k$th iteration, $\Pr(K>k)$,
is bounded by $(1-\eta)^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/\eps^2)\log(1/\delta')$. Then, the number of trials, $t(k)$, during the $k$th iteration
is bounded by $(cn/\eps^2)\log(1/\delta')+m_k$.
It follows that the expected total number of trials under our policy is bounded by
\begin{eqnarray*}
\sum_{k=1}^{\infty} \Pr(K\geq k) t(k)
&\leq& \frac{1}{\eps^2}
\sum_{k=1}^{\infty} (1-\eta)^{k-1}\left(cn \log(1/\delta')+(9/2)\log(2^k/\delta) + 1\right)\\
&=& \frac{1}{\eps^2}
\sum_{k=1}^{\infty} (1-\eta)^{k-1}\left( cn \log(1/\delta')+(9/2)\log(1/\delta)+(9k/2)\log 2 + 1\right)\\
&\leq&\frac{1}{\eps^2}\big(c_1n + c_2\log(1/\delta)\big),
\end{eqnarray*}
for some positive constants $c_1$ and $c_2$.

We finally argue that the policy is \qedc-correct.
For the policy to select a coin $I$ with bias  $p_I\leq q^*-\eps$, it must be that at some iteration $k$,
a coin $I_k$ with $p_{I_k}\leq q^*-\eps$ was obtained, but ${\hat p}_k$ came out larger than $q^*-2\eps/3$.
From Eq.\ (\ref{eq:step3mistake}), for any fixed $k$, the probability of this occurring is bounded
by $\delta/2^k$.
By the union bound, the probability that $p_I\leq q^*-\eps$
is bounded by  $\sum_{k=1}^\infty \delta/2^k = \delta$. \qed


\begin{remark}
{\rm
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^*-\eps$, without having to check the other coins.
A policy of this type would not work for the hypotheses considered in
the proofs of Theorems
\ref{th:main} and \ref{th:specificp}: under those hypotheses, the value of $q^*$ is not a priori known.
We note that Theorem \ref{th:perm1} disagrees with a lower bound in a
preliminary version \citep{MT03} 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~\ref{sub:path}.
}
\end{remark}


\subsection{A Lower Bound}

We now prove that the upper bound in Theorem \ref{th:perm1} is tight, within a constant.


\begin{theorem}\label{th:permlower}
There exist positive constants $c_1$, $c_2$, $\eps_0$, and $\delta_1$, such that for every $n\geq 2$ and
$\eps\in(0,\eps_0)$, there exists some $q\in[0,1]^n$, such that for every $\delta\in(0,\delta_1)$ and
every \qedc-correct policy,
there exists some permutation $\sigma$ such that
$$
\E_{q\circ \sigma}[T] \ge \frac{1}{\eps^2}\left(c_1 n + c_2 \log\frac{1}{\delta} \right).
$$
\end{theorem}
\proof
Let $\eps_0=1/4$ and let $\delta_1=\delta_0/5$, where $\delta_0$ is the same constant as in Theorem
\ref{th:specificp}. Let us
fix some $n\geq 2$ and $\eps\in(0,\eps_0)$.
We will establish the claimed lower bound for
\begin{equation}\label{eq:q}
q=(0.5+\eps,\ 0.5-\eps,\ldots,0.5-\eps),\end{equation}
and for every $\delta\in(0,\delta_1)$. In fact, it is sufficient to establish a lower bound of the form
$(c_2/\eps^2)\log(1/\delta)$ and a lower bound of the form $c_1 n/\eps^2$. We start with the former.


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

\begin{enumerate}
\item[$\Pi_1$:] We have two coins and the bias vector is either $(0.5-\eps,\ 0.5+\eps)$ or
$(0.5+\eps,\ 0.5-\eps)$. We wish to determine the best coin. This is a special case of our permutation problem, with $n=2$.
\item[$\Pi_2$:] We have a single coin whose bias is either $0.5-\eps$ or $0.5+\eps$, and we wish to determine the bias of the coin.\footnote{A lower bound for this problem was
provided in Lemma 5.1 from \cite{anthony_bartlett99}. 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.}
\item[$\Pi_3$:] We have two coins and the bias vector can be
$(0.5,\,0.5-\eps)$, $(0.5+\eps,\,0.5-\eps)$, or  $(0.5,0.5+\eps)$. We wish to determine the best coin.
\end{enumerate}


Consider a $\delta$-correct policy for problem $\Pi_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 $\Pi_1$, every trial (no matter which coin was tried)
has probability $0.5-\eps$ of being equal to 1, and under the second hypothesis has probability $0.5+\eps$
of being equal to 1. With this encoding, it is apparent that the information provided by a trial of
either coin in problem $\Pi_1$ is the same as the information provided by a trial of the single
coin in problem $\Pi_2$.
Thus, a $\delta$-correct policy for $\Pi_1$ translates to a $\delta$-correct policy for $\Pi_2$, with the same sample complexity.

In problem $\Pi_3$, note that coin 2 is the best coin if and only if its bias is equal to $0.5+\eps$
(as opposed to $0.5-\eps$). Thus, any $\delta$-correct
policy for $\Pi_2$ can be applied to the second coin in $\Pi_3$, to yield a $\delta$-correct policy for $\Pi_3$ with the same sample complexity.

We now observe that
problem $\Pi_3$ involves a set of three hypotheses, of the form considered in the proof of Theorem \ref{th:specificp},
for the case of two coins.
More specifically, in terms of the notation used in that proof, we have
$p=(0.5,0.5-\eps)$, and $N(p,\eps)=\{2\}$.
It follows that the sample complexity of any $\delta$-correct policy for $\Pi_3$ is
lower bounded by $(c_1/\eps^2)\log(1/8\delta)$, where $c_1$ is the constant in Theorem
\ref{th:specificp}.\footnote{Although Theorem \ref{th:specificp} is stated for \ed-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.}
Because of the relation between the three problems established earlier, the same lower bound applies to any $\delta$-correct policy for problem $\Pi_1$, which is the permutation problem of interest.

We have so far established a lower bound proportional to $(1/\eps^2)/\log(1/\delta)$ for problem $\Pi_1$, which is the permutation problem we are interested in, with a $q$ vector of the form (\ref{eq:q}),
for the case $n=2$. Consider now the permutation problem for
the $q$ vector in (\ref{eq:q}), 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 $\Pi_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\geq 2$.

\vspace{5pt}
\noindent
{\bf Part II:}
We now continue with the second part of the proof.
We will establish a lower bound of the form
$c_1n/\eps^2$
 for the permutation problem associated with the bias vector $q$ introduced in Eq.\ (\ref{eq:q}), to be referred to as problem $\Pi$.  The proof involves a reduction of $\Pi$ to a problem
 $\tilde \Pi$ of the form considered in the proof of Theorem
\ref{th:specificp}.

The problem $\tilde \Pi$
involves $n+1$ coins (coins $0,1,\ldots,n)$ and the following $n+2$ hypotheses:
$$
H_0':\ p_0=0.5,\qquad p_i=0.5-\eps, \
{\rm for}\ i\neq 0\,,$$
$$
H_0'':\ p_0=0.5+\eps,\qquad p_i=0.5-\eps, \
{\rm for}\ i\neq 0\,,$$
and
$$
H_\ell:\ p_0=0.5,\qquad
p_\ell=0.5+\eps, \qquad p_i=0.5-\eps,\ {\rm for}\
i\neq 0,\ell.$$
Note that the best coin is coin 0 under either hypothesis
$H_0'$ or $H_0''$, and the best coin is coin $\ell$ under $H_{\ell}$, for $\ell\geq 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 $\tilde \Pi$ is $\delta$-correct if it selects the best coin with probability at least $1-\delta$.
We will show that if we have a $(q,\eps,\delta)$-correct policy $\pi$ for $\Pi$, with  a certain sample complexity,
we can construct an $(\eps,5\delta)$-correct policy $\tilde \pi$ with a related sample complexity.
We will then apply Theorem \ref{th:specificp} to lower bound the sample complexity of $\tilde\pi$,
and finally translate to a lower bound for $\pi$.

The idea of the reduction is as follows. In problem $\tilde \Pi$, if we knew that
$H_0$ is not true, we would be left with a permutation problem with $n$ coins, to which
$\pi$ could be applied. However, if $H_0$ is true, the behavior of $\pi$ is
unpredictable. (In particular, $\pi$ might not terminate, or it might terminate with an arbitrary
decision: this is because we are only assuming that $\pi$ behaves properly when faced with the permutation problem $\Pi$.)
If $H_0$ is true, we can replace coin 1 with a coin whose bias is $0.5+\eps$,
resulting in the bias vector $q$, in which case $\pi$ is guaranteed to work properly.
But what if we replace coin 1 as above, but some $H_{\ell}$, $\ell\neq 0,1$, happens to be true?
In that case, there will be two coins with bias
$0.5+\eps$ and $\pi$ 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.

Consider the
$(q,\eps,\delta)$-correct policy $\pi$ for problem $\Pi$.
Let $t_{\pi}$ be the maximum (over all permutations $\sigma$) expected time until $\pi$ terminates when the true coin bias vector
is $q\circ\sigma$.

We define two more bias vectors that will be used below:
$$q_-=\left( 0.5-\eps,\ldots,0.5-\eps\right),$$
and
$$q_+=\left( 0.5+\eps,\ 0.5+\eps, \ 0.5-\eps,\ldots, 0.5-\eps\right).$$
Note that if $H_0$ is true in problem $\tilde \Pi$, and $\pi$ is applied to coins
$1,\ldots,n$, then $\pi$ will be faced with the bias vector $q_-$.
Also, if $H_{\ell}$,  is true in problem $\tilde\Pi$,
for some $\ell\neq 0,1$, and we modify the bias of coin 1 to $0.5+\eps$,
then policy $\pi$ will be faced with the bias vector $q_+$.

Let us note for future reference that, as in Eq.~(\ref{eq:step3mistake}), if we
sample a coin with bias  $0.5+\eps$ for $m\bydef \lceil (1/\eps^2) \log(1/\delta)\rceil$ times, the empirical mean reward is
larger than $0.5$ with probability at least $1-\delta$.
Similarly, if we
sample a coin with bias  $0.5-\eps$ for $m$ times, the empirical mean reward is
smaller than $0.5$ with probability at least $1-\delta$.
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 $\tilde\pi$ for problem $\tilde\Pi$. The policy involves two parallel processes
$\mA$ and $\mB$: 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= \lceil 18\log(1/\delta) \rceil$.

\begin{enumerate}
\item[$\mA$:] Apply policy $\pi$ to coins $1,2,\ldots,n$. If $\pi$ terminates
and selects coin $\ell$,
validate  coin $\ell$
by sampling it
$m$ times. If the empirical mean reward
is more than $0.5$, then $\mA$  terminates and
declares coin $\ell$ as the best coin.
If the empirical mean reward is less than or equal to $0.5$, then $\mA$ terminates and
declares coin 0 as the best coin.
If $\pi$ has carried out $\lceil t_{\pi}/\delta \rceil$ trials, then $\mA$
terminates and
declares coin 0 as the best coin.
\item[$\mB$:] Sample coin 1 for $m$ times. If the empirical mean reward
is more than $0.5$, then $\mB$ terminates and
declares coin 1 as the best coin.
Otherwise, replace coin 1 with
another coin whose bias is $0.5+\eps$.
Initialize a counter $N$ with  $N=0$.
\item[]Repeat $k$ times the following:
\begin{enumerate}
\item Pick a random permutation $\tau$ (uniformly over the set of permutations).
\item Run a $\tau$-permuted version of $\pi$, to be referred to as $\tau\circ\pi$;
that is, whenever $\pi$ is supposed to sample coin $i$, $\tau\circ\pi$ samples coin $\tau(i)$ instead.

\item If $\tau\circ\pi$ terminates and selects coin $1$ as the best coin, set $N:=N+1$.
\end{enumerate}
If $N>2k/3$, then $\mB$ terminates and
declares coin 0 as the best coin. Otherwise, wait until process $\mA$ terminates.
\end{enumerate}

We first address the issue of correctness of policy $\tilde\pi$.
Note that $\tilde\pi$ is guaranteed to terminate in finite time, because process $\mA$ can only run for a bounded number of steps.
We consider separately the following cases:
\begin{enumerate}
\item Process $\mA$ terminates first, $H_0$ is true. In this case the true bias vector faced by $\pi$ is
$q_-$ rather than $q$.
An error can happen only if $\pi$ terminates and the coin erroneously passes the validation test.
The probability of this occurring is at most $\delta$.
In all other cases (validation fails or the running time exceeds the time limit $\lceil t_{\pi}/\delta\rceil$), process $\mA$ correctly declares $H_0$ to be the true hypothesis.
\item Process $\mA$ terminates first, $H_\ell$ is true for some $\ell\neq 0$. Process $\mA$ does not declare the correct $H_\ell$ if one
of the following events occurs:
$\mA$ fails to select the best coin (probability at most $\delta$, since $\pi$ is $(q,\eps,\delta)$-correct); or the validation makes an error (probability at most $\delta$); or the time limit is exceeded.
By Markov's inequality, the probability that the running time $T_{\pi}$ of policy $\pi$ exceeds the time limit satisfies
$$\Pr_q(T_{\pi} \geq t_{\pi}/\delta) \le \E_q [T_{\pi}] \delta/t_{\pi}
\leq t_{\pi}\delta /t_{\pi}
= \delta.$$
So, the total the probability of errors that fall within this case is bounded by $3\delta$.
\item Process $\mB$ terminates first, $H_0$ is true.
Note that under $H_0$, process $\mB$ is faced with $n$ coins whose bias vector is $q$.
Process $\mB$ does not declare $H_0$ if one
of the following events occurs:
the initial validation of coin 1 makes an error (probability at most $\delta$);
or
in $k$ runs, the permuted versions of policy $\pi$
make at least $k/3$ errors. Each such run  has probability at most $\delta$ of making an error
(since $\pi$ is $(q,\eps,\delta)$-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\{-2 k (1/3 - \delta)^2\}$. Since $\delta<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 $ \delta+ e^{-k/8}$.
\item Process $\mB$ terminates first, $H_\ell$ is true for some $\ell> 1$.
Process $\mB$ does not declare $H_\ell$ if one
of the following events occurs:
the initial validation of coin 1 makes an error (probability at most $\delta$);
or
in $k$ runs, the permuted versions of policy $\pi$ 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+\eps$,
namely coins 1 and $\ell$, the probability
that the permuted version of $\pi$ 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\{-2 k ((2/3)-(1/2))^2\} = e^{-k/18}$. So, the total the probability of errors that fall within this case is bounded by $ \delta + e^{-k/18}$.
\item Process $\mB$ terminates first, $H_1$ is true.
Process $\mB$ fails to declare coin 1 only if an error is made in the initial validation step,
which happens with probability bounded by $\delta$.
\end{enumerate}

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

We now examine the sample complexity of policy $\tilde\pi$.
We consider two cases, depending on which hypothesis is true.
\begin{enumerate}
\item $H_0$ is true. In process $\mA$, policy $\pi$ is faced with the bias vector $q_-$
and has no termination guarantees, unless it reaches the time limit
$\lceil t_{\pi}/\delta\rceil$.
As established earlier (case 3), Process $\mB$ will terminate after the initial validation of coin 1 ($m$ trials), plus possibly $k$ runs of policy
$\pi$ (expected number of trials $kt_{\pi}$), with probability
at least $1-e^{-k/8}$. Otherwise, $\mB$ waits until $\mA$ terminates (at most $1+t_{\pi}/\delta$ time).
Multiplying everything by a factor of 2 (because the two processes alternate),
 the expected time until $\tilde \pi$ terminates is bounded by
$$
2 (m + k t_{\pi}) + 2e^{-k/8}(m+ t_{\pi}/\delta +1).$$
\item $H_\ell$ is true for some $\ell\neq 0$. In this case, process $\mA$ terminates after the validation time $m$ and the time it
takes for $\pi$ to run. Thus, the expected time until termination is bounded by
$ 2(m+1+t_{\pi})$.
 \end{enumerate}


We have constructed an $(\eps,5\delta)$-correct policy $\tilde \pi$ for problem $\tilde \Pi$.
Using the above derived time bounds, and the definitions of $k$ and $m$, the
expected number of trials, under any hypothesis $H_\ell$, is bounded from above
by
$$4m +36 \left( \log\left(\frac{1}{\delta}\right)+3\right)t_{\pi}.$$
On the other hand,
problem $\tilde\Pi$ involves hypotheses of the form considered in the proof of
Theorem \ref{th:specificp}, with $p=(0.5,\ 0.5-\eps,\ldots,0.5-\eps)$, and with
$N(p,\eps)=\{1,2,\ldots,n\}$. Thus,
the expected number of trials under some hypothesis
is bounded below by $(c_1n/\eps^2)\log(c_2/\delta)$, for some positive constants $c_1$ and $c_2$, leading to
$$c_1\frac{n}{\eps^2} \log\frac{c_2}{\delta}\leq 4m +36 \left( \log\left(\frac{1}{\delta}\right)+3\right)t_{\pi}.$$
This translates to a lower bound of the form
$t_{\pi}\geq c_2n/\eps^2$, for some new constant $c_2$, and for all $n$ larger than some $n_0$.
But for $n\leq n_0$, we can use the lower bound $(c_2/\eps^2)\log(1/\delta)$ that was derived in the first part of the proof.
\qed

\subsection{Pathwise Sample Complexity}\label{sub:path}

The sample complexity of the policy presented in Section \ref{sec:permsupper}
was measured in term of the {\em 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 {\em 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 \cite{EDMM02} is a \qedc-correct policy
whose pathwise sample complexity is of the form $(c_1n/\eps^2) \log(c_2/\delta)$.
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 \qedc-correct policy.

\begin{theorem}
There exist positive constants $c_1$, $c_2$, $\eps_0$, and $\delta_1$ such that
for every $n\geq 2$ and $\eps\in (0,\eps_0)$, there exists some $q\in[0,1]^n$, such that for every $\delta\in(0,\delta_1)$ and every $(q,\eps,\delta)$-correct policy $\pi$,  there exists some permutation $\sigma$ under which the pathwise sample complexity of $\pi$ is at least
$$ c_1 \frac{n}{\eps^2}\log\left(\frac{c_2}{\delta}\right).
$$
\end{theorem}
\proof
The proof uses a reduction similar to the one in the proof of Theorem \ref{th:permlower}.
Let $\eps_0=1/8$ and $\delta_1=\delta_0/2$, where $\delta_0=e^{-8}/8$ is the constant in
Theorem \ref{th:specificp}. Let $q$ be the same as in the proof of  Theorem \ref{th:permlower}
(cf.\ Eq. (\ref{eq:q})), and consider the associated permutation problem, referred to as problem $\Pi$.
Fix some $\delta\in(0,\delta_1)$ and
suppose that we have a \qedc-correct policy $\pi$ for problem $\Pi$ whose pathwise sample complexity
is bounded by $t_{\pi}$ for every permutation $\sigma$. Consider also the problem $\tilde\Pi$
introduced in the proof of  Theorem \ref{th:permlower}, involving the hypotheses
$H_0$, $H_1,\ldots,H_n$.
We will now use the policy $\pi$ to construct a policy $\tilde \pi$ for problem $\tilde \Pi$.

We run $\pi$  on the coins $1,2,\ldots,n$.
If $\pi$ terminates at or before time $t_\pi$ and selects some coin $\ell$, we sample coin $\ell$
for $\lceil(1/\eps^2)\log(1/\delta)\rceil$ times. If the empirical mean reward is larger
than $0.5$ we declare $H_\ell$ as the true hypothesis.
If the empirical mean reward of coin $\ell$ is less than or equal to $0.5$, or if $\pi$
does not terminate by time $t_\pi$, we declare $H_0$ as the true hypothesis.

We start by showing correctness.
Suppose first that $H_0$ is true. For the policy $\tilde\pi$ to make an incorrect decision, it must be the case that  policy $\pi$ 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 $\delta$.
Suppose instead that $H_\ell$ is true for some $\ell\geq 1$.
In this case, policy $\pi$ is guaranteed to terminate within $t_\pi$ steps.
Policy $\tilde\pi$ will make an incorrect decision if either policy $\pi$ makes an
incorrect decision (probability at most $\delta$), or if policy $\pi$ makes a correct decision
but the selected coin fails to validate (probability at most $\delta$).
It follows that policy $\tilde\pi$ is $(q,\eps,2\delta)$-correct.

The number of trials under policy $\tilde\pi$
is bounded by $t' = t_\pi+ \lceil({1}/{\eps^2})\log(1/\delta)\rceil$, under any hypothesis. On the other hand, using Theorem \ref{th:specificp},
the expected number of trials under some hypothesis is bounded below by $(c_1n/\eps^2)\log
(c_2/2\delta)$, leading to
$$c_1\frac{n}{\eps^2}\log\frac{c_2}{2\delta} \leq t_\pi +\frac{1}{\eps^2}\log\left(\frac{1}{\delta}\right).$$
this translates to a lower bound of the form $t\geq (c_1n/\eps^2)\log(c_2/\delta)$, for some new
constants $c_1$ and $c_2$.
\qed




\section{Concluding Remarks}\label{se:con}

We have provided bounds on the number of trials required to identify a near-optimal arm in a multi-armed bandit problem, with high probability. For the problem formulations studied in Sections \ref{sec:mainspecprob} and \ref{sec:Bayes}, the lower bounds match
the existing $O \big((n/\eps^2)\log({1}/{\delta})\big)$ 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 \citep[as in][]{LR85}.

\acks{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.}

\bibliography{MAB}
%\bibliographystyle{alpha}


\end{document}               % End of document.
