On the Complexity of Best Arm Identification in Multi-Armed Bandit Models

Introduction

In order to identify $\mathcal{S}^{*}_{m}$, the agent must use a strategy defining which arms to sample from, when to stop sampling, and which set $\hat{S}_{m}$ to choose. More precisely, its strategy consists in a triple $\mathcal{A}=((A_{t}),\tau,\hat{S}_{m})$ in which :

the sampling rule determines, based on past observations, which arm $A_{t}$ is chosen at time $t$; in other words, $A_{t}$ is $\mathcal{F}_{t-1}$-measurable, with $\mathcal{F}_{t}=\sigma(A_{1},Z_{1},\dots,A_{t},Z_{t})$;

the recommendation rule provides the arm selection and is a $\mathcal{F}_{\tau}$-measurable random subset $\hat{S}_{m}$ of $\{1,\dots,K\}$ of size $m$.

In order to unify and compare these approaches, we define the complexity $\kappa_{C}(\nu)$ (resp. $\kappa_{B}(\nu)$) of best-arm identification in the fixed-confidence (resp. fixed-budget) setting as follows:

Heuristically, on the one hand for a given bandit model $\nu$, and a small value of $\delta$, a fixed-confidence optimal strategy needs an average number of samples of order $\kappa_{C}(\nu)\log\frac{1}{\delta}$ to identify the $m$ best arms with probability at least $1-\delta$. On the other hand, for large values of $t$ the probability of error of a fixed-budget optimal strategy is of order $\exp(-\kappa_{B}(\nu)t)$, which means that a budget of approximately $t=\kappa_{B}(\nu)\log\frac{1}{\delta}$ draws is required to ensure a probability of error of order $\delta$. Most of the existing performance bounds for the fixed confidence and fixed budget settings can indeed be expressed using these complexity measures.

In this paper, we aim at evaluating and comparing these two complexities. To achieve this, two ingredients are needed: a lower bound on the sample complexity of any $\delta$-PAC algorithm (resp. on the failure probability of any consistent algorithm) and a $\delta$-PAC (resp. consistent) strategy whose sample complexity (resp. failure probability) attains the lower bound (often referred to as a ’matching’ strategy). We present below new lower bounds on $\kappa_{C}(\nu)$ and $\kappa_{B}(\nu)$ that feature information-theoretic quantities as well as strategies that match these lower bounds in two-armed bandit models.

A particular class of algorithms will be considered in the following: those using a uniform sampling strategy, that sample the arms in a round-robin fashion. Whereas it is well known that when $K>2$ uniform sampling is not desirable, it will prove efficient in some examples of two-armed bandits. This specific setting, relevant in practical applications discussed in Section 3, is studied in greater details along the paper. In this case, an algorithm using uniform sampling can be regarded as a statistical test of the hypothesis $H_{0}:(\mu_{1}\leq\mu_{2})$ against $H_{1}:(\mu_{1}>\mu_{2})$ based on paired samples ($X_{s},Y_{s}$) of $\nu_{1},\nu_{2}$; namely a test based on a fixed number of samples in the fixed-budget setting, and, a sequential test in the fixed-confidence setting, in which a (random) stopping rule determines when the experiment is to be terminated.

where $\text{KL}(\nu_{i},\nu_{j})$ denotes the Kullback-Leibler divergence between distributions $\nu_{i}$ and $\nu_{j}$. This bound was later generalized by Burnetas and Katehakis 1996 to distributions that depend on several parameters. Since then, non-asymptotic analyses of efficient algorithms matching this bound have been proposed. Optimal algorithms include the KL-UCB algorithm of Cappé et al. 2013—a variant of UCB1 (Auer et al. 2002) using informational upper bounds, Thompson Sampling (Kaufmann et al. 2012b; Agrawal and Goyal 2013), the DMED algorithm (Honda and Takemura 2011) and Bayes-UCB (Kaufmann et al. 2012a). This paper is a contribution towards similarly characterizing the complexity of pure exploration, where the goal is to determine the best arms without trying to maximize the cumulative observations.

Bubeck et al. 2011 show that in the fixed-budget setting, when $m=1$, any sampling strategy designed to minimize regret performs poorly with respect to the simple regret $r_{t}:=\mu^{*}-\mu_{\hat{S}_{1}}$, which is closely related to the probability $p_{t}(\nu)$ of recommending the wrong arm. Therefore, good strategies for best-arm identification need to be quite different from regret-minimizing strategies. We will show below that the complexities $\kappa_{B}(\nu)$ and $\kappa_{C}(\nu)$ of best-arm identification also involve information terms, but these are different from the Kullback-Leibler divergence featured in Lai and Robbins’ lower bound on the regret.

The problem of best-arm identification has been studied since the 1950s under the name ‘ranking and identification problems’. The first advances on this topic are summarized in the monograph by Bechhofer et al. 1968 who consider the fixed-confidence setting and strategies based on uniform sampling. In the fixed confidence setting, Paulson 1964 first introduces a sampling strategy based on eliminations for single best arm identification: the arms are successively discarded, the remaining arms being sampled uniformly. This idea was later used for example by Jennison et al. 1982; Maron and Moore 1997 and by Even-Dar et al. 2006 in the context of bounded bandit models, in which each arm $\nu_{a}$ is a probability distribution on $$.$m$best arms identification with$m>1$ was considered for example by Heidrich-Meisner and Igel 2009, in the context of reinforcement learning. Kalyanakrishnan et al. 2012 later proposed an algorithm that is no longer based on eliminations, called LUCB (for Lower and Upper Confidence Bounds) and still designed for bounded bandit models. Bounded distributions are in fact particular examples of distributions with subgaussian tails, to which the proposed algorithms can be easily generalized. A relevant quantity introduced in the analysis of algorithms for bounded (or subgaussian) bandit models is the ‘complexity term’

Recent works have focused on obtaining upper bounds on the number of samples whose dependency in terms of the squared-gaps $\Delta_{a}$ (for subgaussian arms) is optimal when the $\Delta_{a}$’s go to zero, and $\delta$ remains fixed. Karnin et al. 2013 and Jamieson et al. 2014 exhibit $\delta$-PAC algorithms for which there exists a constant $C$ such that, with high probability, the number of samples used satisfies

and Jamieson et al. 2014 show that the dependency in $\Delta_{a}^{-2}\log(\log(\Delta_{a}^{-1}))$ is optimal when $\Delta_{a}$ goes to zero. However, the constant $C_{0}$ is large and does not lead to improved upper bounds on the complexity term $\kappa_{C}(\nu)$.

For $m=1$, the work of Mannor and Tsitsiklis 2004 provides a lower bound on $\kappa_{C}(\nu)$ in the case of Bernoulli bandit models, under the following $\epsilon$-relaxation sometimes considered in the literature. For some tolerance parameter $\epsilon\geq 0$ the agent has to ensure that $\hat{S}_{m}$ is included in the set of $(\epsilon,m)$ optimal arms $\mathcal{S}^{*}_{m,\epsilon}=\{a:\mu_{a}\geq\mu_{[m]}-\epsilon\}$ with probability at least $1-\delta$. This relaxation has to be considered, for example, when $\mu_{[m]}=\mu_{[m+1]}$, but has never been considered in the literature for the fixed-budget setting. In this paper, we focus on the case $\epsilon=0$ that allows for a comparison between the fixed-confidence and fixed-budget settings. Mannor and Tsitsiklis 2004 show that if an algorithm is $\delta$-PAC, then in the bandit model $\nu=(\mathcal{B}(\mu_{1}),\dots,\mathcal{B}(\mu_{K}))$ such that $\forall a$, $\mu_{a}\in[0,\alpha]$ for some $\alpha\in(0,1)$, there exists two sets $\mathcal{G}_{\alpha}(\nu)\subset\mathcal{S}_{1}^{*}$ and $\mathcal{H}_{\alpha}(\nu)\subset\{1,\dots,K\}\backslash\mathcal{S}_{1}^{*}$ and a positive constant $C_{\alpha}$ such that

The fixed-budget setting has been studied by Audibert et al. 2010; Bubeck et al. 2011 for single best-arm identification in bounded bandit models. For multiple arm identification ($m>1$), still in bounded bandit models, Bubeck et al. 2013b introduce the SAR (for Successive Accepts and Rejects) algorithm. An upper bound on the failure probability of the SAR algorithm yields $\kappa_{B}(\nu)\leq 8\log(K)H\left(\nu\right)$.

For $m=1$, Audibert et al. 2010 prove an asymptotic lower bound on the probability of error for Bernoulli bandit models. They state that for every algorithm and every bandit problem $\nu$ such that $\forall a$, $\mu_{1}\in[\alpha,1-\alpha]$, there exists a permutation of the arms $\nu^{\prime}$ such that

Gabillon et al. 2012 propose the UGapE algorithm for $m$ best-arm identification for $m>1$. By changing only one parameter in some confidence regions, this algorithm can be adapted either to the fixed-budget or to the fixed-confidence setting. However, a careful inspection shows that UGapE cannot be used in the fixed-budget setting without the knowledge of the complexity term $H(\nu)$. This drawback is shared by other algorithms designed for the fixed-budget setting, like the UCB-E algorithm of Audibert et al. 2010 or the KL-LUCB-E algorithm of Kaufmann and Kalyanakrishnan 2013.

2 Content of the Paper

The gap between lower and upper bounds known so far does not permit to identify exactly the complexity terms $\kappa_{B}(\nu)$ and $\kappa_{C}(\nu)$ defined in (1). Not only do they involve imprecise multiplicative constants but by analogy with the Lai and Robbins’ bound for the expected regret, the quantities $H(\nu),H_{2}(\nu)$ presented above are only expected to be relevant in the Gaussian case.

The improvements of this paper mainly concern the fixed-confidence setting, which will be considered in the next three Sections. We first propose in Section 2 a distribution-dependent lower bound on $\kappa_{C}(\nu)$ that holds for $m>1$ and for general classes of bandit models (Theorem 4). This information-theoretic lower bound permits to interpret the quantity $H(\nu)$ defined in (2) as a subgaussian approximation.

Theorem 6 in Section 3 proposes a tighter lower bound on $\kappa_{C}(\nu)$ for general classes of two-armed bandit models, as well as a lower bound on the sample complexity of $\delta$-PAC algorithms using uniform sampling. In Section 4 we propose, for Gaussian bandits with known—but possibly different—variances, an algorithm exactly matching this bound. We also consider the case of Bernoulli distributed arms, for which we show that uniform sampling is nearly optimal in most cases. We propose a new algorithm using uniform sampling and a non-trivial stopping strategy that is close to matching the lower bound.

Section 5 gathers our contributions to the fixed-budget setting. For two-armed bandits, Theorem 12 provides a lower bound on $\kappa_{B}(\nu)$ that is in general different from the lower bound obtained for $\kappa_{C}(\nu)$ in the fixed-confidence setting. Then we propose matching algorithms for the fixed-budget setting that allow for a comparison between the two settings. For Gaussian bandits, we show that $\kappa_{C}(\nu)=\kappa_{B}(\nu)$, whereas for Bernoulli bandits $\kappa_{C}(\nu)>\kappa_{B}(\nu)$, proving that the two complexities are not necessarily equal. As a first step towards a lower bound on $\kappa_{B}(\nu)$ when $m>1$, we also give in Section 5 new lower bounds on the probability of error $p_{t}(\nu)$ of any consistent algorithm, for Gaussian bandit models.

Section 6 contains numerical experiments that illustrate the performance of matching algorithms for Gaussian and Bernoulli two-armed bandits, comparing the fixed-confidence and fixed-budget settings.

Our contributions follow from two main mathematical results of more general interest. Lemma 1 provides a general relation between the expected number of draws and Kullback-Leibler divergences of the arms’ distributions, which is the key element to derive the lower bounds (it also permits, for example, to derive Lai and Robbin’s lower bound on the regret in a few lines). Lemma 7 is a tight deviation inequality for martingales with sub-Gaussian increments, in the spirit of the Law of Iterated Logarithm, that permits here to derive efficient matching algorithms for two-armed bandits.

Generic Lower Bound in the Fixed-Confidence Setting

Introducing the Kullback-Leibler divergence of any two probability distributions $p$ and $q$:

we make the assumption that there exists a set $\mathcal{P}$ of probability measures such that for all $\nu=(\nu_{1},\dots,\nu_{K})\in\mathcal{M}_{m}$, for $a\in\{1,\dots,K\},\nu_{a}\in\mathcal{P}$ and that $\mathcal{P}$ satisfies

A class $\mathcal{M}_{m}$ of bandit models satisfying this property is called identifiable.

All the distribution-dependent lower bounds derived in the bandit literature (Lai and Robbins 1985; Mannor and Tsitsiklis 2004; Audibert et al. 2010, e.g.,) rely on changes of distribution, and so do ours. A change of distribution relates the probabilities of the same event under two different bandit models $\nu$ and $\nu^{\prime}$. The following lemma provides a new, synthetic, inequality from which lower bounds are directly derived. This result, proved in Appendix A, encapsulates the technical aspects of the change of distribution. The main ingredient in its proof is a lower bound on the expected log-likelihood ratio of the observations under two different bandit models which is of interest on its own and is stated as Lemma 19 in Appendix A. To illustrate the interest of Lemma 1 even beyond the pure exploration framework, we give in Appendix B a new, simple proof of Burnetas and Katehakis 1996’s generalization of Lai and Robbins’ lower bound in the regret minimization framework based on Lemma 1.

Let $N_{a}(t)=\sum_{s=1}^{t}\mathds{1}_{\{A_{s}=a\}}$ be the number of draws of arm $a$ between the instants 1 and $t$ and $N_{a}=N_{a}(\tau)$ be the total number of draws of arm $a$ by some algorithm $\mathcal{A}=((A_{t}),\tau,\hat{S}_{m})$.

Let $\nu$ and $\nu^{\prime}$ be two bandit models with $K$ arms such that for all $a$, the distributions $\nu_{a}$ and $\nu_{a}^{\prime}$ are mutually absolutely continuous. For any almost-surely finite stopping time $\sigma$ with respect to $(\mathcal{F}_{t})$,

where $d(x,y):=x\log(x/y)+(1-x)\log((1-x)/(1-y))$ is the binary relative entropy, with the convention that $d(0,0)=d(1,1)=0$.

This result can be considered as a generalization of Pinsker’s inequality to bandit models: in combination with the inequality $d(p,q)\geq 2(p-q)^{2}$, it yields:

However, it is important in this paper not to use this weaker form of the statement, as we will consider events $\mathcal{E}$ of probability very close to $0$ or $1$. In this regime, we will make use of the following inequality:

We now propose a non-asymptotic lower bound on the expected number of samples needed to identify the $m$ best arms in the fixed confidence setting, which straightforwardly yields a lower bound on $\kappa_{C}(\nu)$.

Theorem 4 holds for an identifiable class of bandit models of the form:

such that the set of probability measures $\mathcal{P}$ satisfies Assumption 3 below.

For all $p,q\in\mathcal{P}^{2}$ such that $p\neq q$, for all $\alpha>0$,

These continuity conditions are reminiscent of the assumptions of Lai and Robbins 1985; they include families of parametric bandits continuously parameterized by their means (e.g., Bernoulli, Poisson, exponential distributions).

Let $\nu\in\mathcal{M}_{m}$, where $\mathcal{M}_{m}$ is defined by (4), and assume that $\mathcal{P}$ satisfies Assumption 3; any algorithm that is $\delta$-PAC on $\mathcal{M}_{m}$ satisfies, for $\delta\leq 0.15$,

Proof. Without loss of generality, one may assume that the arms are ordered such that $\mu_{1}\geq\dots\geq\mu_{K}$. Thus $\mathcal{S}^{*}_{m}=\{1,...,m\}$. Let $\mathcal{A}=((A_{t}),\tau,\hat{S}_{m})$ be a $\delta$-PAC algorithm and fix $\alpha>0$. For all $a\in\{1,\dots,K\}$, from Assumption 3 there exists an alternative model

in which the only arm modified is arm $a$, and $\nu_{a}^{\prime}$ is such that:

where the last inequality follows from (3). From the definition of the alternative model, one obtains for $a\in\{1,\dots,m\}$ or $b\in\{m+1,\dots,K\}$ respectively, for every $\alpha>0$,

This inequality can be made tighter for values of $\delta$ that are sufficiently close to zero, for which the right-hand-side can then be made arbitrarily close to $\log(1/\delta)$.

Lemma 1 can also be used to improve the result of Mannor and Tsitsiklis 2004 that holds for $m=1$ under the $\epsilon$-relaxation described before. Combining the changes of distribution of this paper with Lemma 1 yields, for every $\epsilon>0$ and $\delta\leq 0.15$,

where $|\mathcal{X}|$ denotes the cardinal of the set $\mathcal{X}$ and $\mathcal{B}(\mu)$ the Bernoulli distribution of mean $\mu$.

2 Bounds on the Complexity for Exponential Bandit Models

Theorem 4 yields the following lower bound on the complexity term:

Thus, one may want to obtain strategies whose sample complexity can be proved to be of the same magnitude. The only algorithm that has been analyzed so far with an information-theoretic perspective is the KL-LUCB algorithm of Kaufmann and Kalyanakrishnan 2013, designed for exponential bandit models: that is

where $\nu_{\theta}$ belongs to a canonical one-parameter exponential family. This means that there exists a twice differentiable strictly convex function $b$ such that $\nu_{\theta}$ has a density with respect to some reference measure given by

Distributions from a canonical one-parameter exponential family can be parameterized either by their natural parameter $\theta$ or by their mean. Indeed $\dot{b}(\theta)=\mu(\theta)$, the mean of the distribution $\nu_{\theta}$ and $\ddot{b}(\theta)=\text{Var}[\nu_{\theta}]>0$. The mapping $\theta\mapsto\mu(\theta)$ is strictly increasing, and the means are ordered in the same way as the natural parameters. Exponential families include in particular Bernoulli distributions, or Gaussian distributions with common variances (see Cappé et al. 2013 for more details about exponential families).

Improved Lower Bounds for Two-Armed Bandits

Two armed-bandits are of particular interest as they offer a theoretical framework for sequential A/B Testing. A/B Testing is a popular procedure used, for instance, for website optimization: two versions of a web page, say A and B, are empirically compared by being presented to users. Each user is shown only one version $A_{t}\in\{1,2\}$ and provides a real-valued index of the quality of the page, $Z_{t}$, which is modeled as a sample of a probability distribution $\nu_{1}$ or $\nu_{2}$. For example, a standard objective is to determine which web page has the highest conversion rate (probability that a user actually becomes a customer) by receiving binary feedback from the users. In standard A/B Testing algorithms, the two versions are presented equally often. It is thus of particular interest to investigate whether uniform sampling is optimal or not.

Let $\mathcal{M}$ be an identifiable class of two-armed bandit models and let $\mathbf{\nu}=(\nu_{1},\nu_{2})\in\mathcal{M}$ be such that $\mu_{1}>\mu_{2}$. Any algorithm that is $\delta$-PAC on $\mathcal{M}$ satisfies, for all $\delta\in)0,1]$,

Moreover, any $\delta$-PAC algorithm using a uniform sampling strategy satisfies,

Obviously, one has $I_{*}(\nu)\leq c_{*}(\nu)$. Theorem 6 implies in particular that $\kappa_{C}(\nu)\geq 1/{c_{*}(\nu)}$. It is possible to give explicit expressions for the quantities $c_{*}(\nu)$ and $I_{*}(\nu)$ for important classes of parametric bandit models that will be considered in the next section.

The class of Gaussian bandits with known variances $\sigma_{1}^{2}$ and $\sigma_{2}^{2}$, further considered in Section 4.1, is

The observation that, when the variances are different $c_{*}(\nu)>I_{*}(\nu)$, will be shown to imply that strategies based on uniform sampling are sub-optimal (by a factor $1\leq 2(\sigma_{1}^{2}+\sigma_{2}^{2})/(\sigma_{1}+\sigma_{2})^{2}\leq 2$).

The more general class of two-armed exponential bandit models, further considered in Section 4.2, is

where $\nu_{\theta_{a}}$ has density $f_{\theta_{a}}$ given by (5). There

Appendix C provides further useful properties of these quantities and in particular Figure 7 illustrates the property that for two-armed exponential bandit models, the lower bound on $\kappa_{C}(\nu)$ provided by Theorem 6,

is indeed always tighter than the lower bound of Theorem 4,

Interestingly, the changes of distribution used to derive the two results are not the same. On the one hand, for inequality (11), the changes of distribution involved modify a single arm at a time: one of the arms is moved just below (or just above) the other (see Figure 2, left). This is the idea also used, for example, to obtain the lower bound of Lai and Robbins 1985 on the cumulative regret. On the other hand, for inequality (10), both arms are modified at the same time: they are moved close to the common intermediate value $\theta_{*}$ but with a reversed ordering (see Figure 2, right).

We now give the proof of Theorem 6, in order to show how easily it follows from Lemma 1.

Proof of Theorem 6. Without loss of generality, one may assume that the bandit model $\nu=(\nu_{1},\nu_{2})$ is such that the best arm is $a^{*}=1$. Consider any alternative bandit model $\nu^{\prime}=(\nu_{1}^{\prime},\nu_{2}^{\prime})$ in which $a^{*}=2$. Let $\mathcal{E}$ be the event $\mathcal{E}=(\hat{\mathcal{S}}_{1}=1)$, which belongs to $\mathcal{F}_{\tau}.$

Using moreover that $\tau=N_{1}+N_{2}$, one has

The result follows by optimizing over the possible model $\nu^{\prime}$ satisfying $\mu_{1}^{\prime}<\mu_{2}^{\prime}$ to make the right hand side of the inequality as large as possible. More precisely, for every $\alpha>0$, from the definition of $c_{*}(\nu)$, there exists $\nu^{\prime}_{\alpha}=(\nu_{1}^{\prime},\nu_{2}^{\prime})$ for which

Matching Algorithms for Two-Armed Bandits

For specific instances of two-armed bandit models, we now present algorithms with performance guarantees that closely match the lower bounds of Theorem 6. For Gaussian bandits with known (and possibly different) variances, we describe in Section 4.1 an algorithm termed $\alpha$-Elimination that is optimal and thus makes it possible to determine the complexity $\kappa_{C}(\nu)$. For Bernoulli bandit models, we present in Section 4.2 the SGLRT algorithm that uses uniform sampling and is close to optimal.

We focus here on the class of two-armed Gaussian bandit models with known variances presented in (8), where $\sigma_{1}$ and $\sigma_{2}$ are fixed. We prove that

by exhibiting a strategy that reaches the performance bound of Theorem 6. This strategy uses non-uniform sampling in case where $\sigma_{1}$ and $\sigma_{2}$ differ. When $\sigma_{1}=\sigma_{2}$, we provide in Theorem 8 an improved stopping rule that is $\delta$-PAC and results in a significant reduction of the expected number of samples used.

The $\alpha$-Elimination algorithm introduced in this Section can also be used in more general two-armed bandit models, where the distribution $\nu_{a}$ is $\sigma_{a}^{2}$-subgaussian. This means that the probability distribution $\nu_{a}$ satisfies

This covers in particular the cases of bounded distributions with support in $$(that are$1/4$-subgaussian). In these more general cases, the algorithm enjoys the same theoretical properties: it is$\delta$-PAC and its sample complexity is bounded as in Theorem 9 below.

We start with the simpler case $\sigma_{1}=\sigma_{2}=\sigma$. Thus, the quantity $I_{*}(\nu)$ introduced in Theorem 6 coincides with $c_{*}(\nu)$, which suggests that uniform sampling could be optimal. A uniform sampling strategy equivalently collects paired samples $(X_{s},Y_{s})$ from both arms. The difference $X_{s}-Y_{s}$ is normally distributed with mean $\mu=\mu_{1}-\mu_{2}$ and a $\delta$-PAC algorithm is equivalent to a sequential test of $H_{0}:(\mu<0)$ versus $H_{1}:(\mu>0)$ such that both type I and type II error probabilities are bounded by $\delta$. Robbins 1970 proposes the stopping rule

The recommendation rule chooses the empirically best arm at time $\tau$. This procedure can be seen as an elimination strategy, in the sense of Jennison et al. 1982. The authors of this paper derive a lower bound on the sample complexity of any $\delta$-PAC elimination strategy (whereas our lower bound applies to any $\delta$-PAC algorithm) which is matched by Robbins’ algorithm: the above stopping rule $\tau$ satisfies

This value coincide with the lower bound on $\kappa_{C}(\nu)$ of Theorem 6 in the case of two-armed Gaussian distributions with similar known variance $\sigma^{2}$. This proves that in this case, Robbins’ rule (14) is not only optimal among the class of elimination strategies, but also among the class of $\delta$-PAC algorithm.

Any $\delta$-PAC elimination strategy that uses a threshold function (or exploration rate) $\beta(t,\delta)$ smaller than Robbins’ also matches our asymptotic lower bound, while stopping earlier than the latter. From a practical point of view, it is therefore interesting to exhibit smaller exploration rates that preserve the $\delta$-PAC property. The failure probability of such an algorithm is upper bounded, for example when $\mu_{1}<\mu_{2}$, by

where $S_{k}$ is a sum of $k$ i.i.d. variables of distribution $\mathcal{N}\left(0,1\right)$. Robbins 1970 obtains a non-explicit confidence region of risk at most $\delta$ by choosing $\beta(2k,\delta)=\log\left({\log(k)}/{\delta}\right)+o(\log\log(k))$. The dependency in $k$ is in some sense optimal, because the Law of Iterated Logarithm (LIL) states that $\limsup_{k\rightarrow\infty}{S_{k}}/\sqrt{2k\log\log(k)}=1$ almost surely. In this paper, we propose a new deviation inequality for a martingale with sub-Gaussian increments, stated as Lemma 7, that permits to build an explicit confidence region reminiscent of the LIL. A related result was recently derived independently by Jamieson et al. 2014.

Lemma 7 allows to prove Theorem 8 below, as detailed in Appendix E, where we also provide a proof of Lemma 7.

the elimination strategy is $\delta$-PAC.

We refer to Section 6 for numerical simulations that illustrate the significant savings (in the average number of samples needed to reach a decision) resulting from the use of the less conservative exploration rate allowed by Theorem 8.

1.2 Mismatched Variances

In the case where $\sigma_{1}\neq\sigma_{2}$, we rely on the $\alpha$-Elimination strategy, described in Algorithm 1 below. For $a=1,2$, $\hat{\mu}_{a}(t)$ denotes the empirical mean of the samples gathered from arm $a$ up to time $t$. The algorithm is based on a non-uniform sampling strategy governed by the parameter $\alpha\in(0,1)$, that maintains the proportion of draws of arm 1 close to $\alpha$. At the end of every round $t$, $N_{1}(t)=\lceil\alpha t\rceil$, $N_{2}(t)=t-\lceil\alpha t\rceil$ and $\hat{\mu}_{1}(t)-\hat{\mu}_{2}(t)\sim\mathcal{N}\left(\mu_{1}-\mu_{2},\sigma_{t}^{2}(\alpha)\right)$ (where $\sigma_{t}^{2}(\alpha)$ is defined at line 6 of Algorithm 1). The sampling schedule used here is thus deterministic.

If $\alpha=\sigma_{1}/(\sigma_{1}+\sigma_{2})$, the $\alpha$-elimination strategy using the exploration rate $\beta(t,\delta)=\log\frac{t}{\delta}+2\log\log(6t)$ is $\delta$-PAC on $\mathcal{M}$ and satisfies, for every $\nu\in\mathcal{M}$, for every $\epsilon>0$,

When $\sigma_{1}=\sigma_{2}$, $1/2$-elimination reduces, up to rounding effects, to the elimination procedure described in Section 4.1.1, for which Theorem 8 suggests an exploration rate of order $\log(\log(t)/\delta)$. As the feasibility of this exploration rate when $\sigma_{1}\neq\sigma_{2}$ is yet to be established, we focus on Gaussian bandits with equal variances in the numerical experiments of Section 6.

2 Bernoulli Bandit Models

We consider in this section the class of Bernoulli bandit models

where each arm can be alternatively parameterized by the natural parameter of the exponential family, $\theta_{a}=\log({\mu_{a}}/{(1-\mu_{a})})$. Observing that in this particular case little can be gained by departing from uniform sampling, we consider the SGLRT algorithm (to be defined below) that uses uniform sampling together with a stopping rule that is not based on the mere difference of the empirical means.

When the arms are sampled uniformly, finding an algorithm that matches the bound of (7) boils down to determining a proper stopping rule. In all the algorithms studied so far, the stopping rule was based on the difference of the empirical means of the arms. For Bernoulli arms the 1/2-Elimination procedure described in Algorithm 1 can be used, as each distribution $\nu_{a}$ is bounded and therefore 1/4-subgaussian. More precisely, with $\beta(t,\delta)$ as in Theorem 8, the algorithm stopping at the first time $t$ such that

has its sample complexity bounded by ${2}/{(\mu_{1}-\mu_{2})^{2}}\log({1}/{\delta})+o\left(\log({1}/{\delta})\right)$. Yet, Pinsker’s inequality implies that $I_{*}(\mu_{1},\mu_{2})>(\mu_{1}-\mu_{2})^{2}/2$ and this algorithm is thus not optimal with respect to the bound (7) of Theorem 6. The approximation $I_{*}(\mu_{1},\mu_{2})=(\mu_{1}-\mu_{2})^{2}/(8\mu_{1}(1-\mu_{1}))+o\left((\mu_{1}-\mu_{2})^{2}\right)$ suggests that the loss with respect to the optimal error exponent is particularly significant when both means are close to 0 or 1.

To circumvent this drawback, we propose the SGLRT (for Sequential Generalized Likelihood Ratio Test) stopping rule, described in Algorithm 2. The appearance of $I_{*}$ in the stopping criterion of Algorithm 2 is a consequence of the observation that it is related to the generalized likelihood ratio statistic for testing the equality of two Bernoulli proportions. To test $H_{0}:(\mu_{1}=\mu_{2})$ against $H_{1}:(\mu_{1}\neq\mu_{2})$ based on $t/2$ paired samples of the arms $W_{s}=(X_{s},Y_{s})$, the Generalized Likelihood Ratio Test (GLRT) rejects $H_{0}$ when

where $L(W_{1},\dots,W_{t/2};\mu_{1},\mu_{2})$ denotes the likelihood of the observations given parameters $\mu_{1}$ and $\mu_{2}$. It can be checked that the ratio that appears in the last display is equal to $\exp(-tI_{*}(\hat{\mu}_{1,t/2},\hat{\mu}_{2,t/2}))$. This equality is a consequence of the rewriting

where $H(x)=-x\log(x)-(1-x)\log(1-x)$ denotes the binary entropy function. Hence, Algorithm (2) can be interpreted as a sequential version of the GLRT with (varying) threshold $z_{t,\delta}=\exp(-\beta(t,\delta))$.

For this exploration rate, we were able to obtain the following asymptotic guarantee on the stopping time $\tau$ of Algorithm 2:

(see Lemma 26 in Appendix F for the proof of this result). By analogy with the result of Theorem 8 we conjecture that the analysis of Kaufmann and Kalyanakrishnan 2013—on which the result of Lemma 11 is based—is too conservative and that the use of an exploration rate of order $\log(\log(t)/\delta)$ should also lead to a $\delta$-PAC algorithm. This conjecture is supported by the numerical experiments reported in Section 6 below. Besides, for this choice of exploration rate, Lemma 26 also shows that

The Fixed-Budget Setting

In this section, we focus on the fixed-budget setting and we provide new upper and lower bounds on the complexity term $\kappa_{B}(\nu)$.

For two-armed bandits, we obtain in Theorem 12 lower bounds analogous to those of Theorem 6 in the fixed-confidence setting. We present matching algorithms for Gaussian and Bernoulli bandits. This allows for a comparison between the fixed-budget and fixed-confidence setting in these specific cases. More specifically, we show that $\kappa_{B}(\nu)=\kappa_{C}(\nu)$ for Gaussian bandit models, whereas $\kappa_{C}(\nu)>\kappa_{B}(\nu)$ for Bernoulli bandit models.

When $K>2$ and $m\geq 1$, we present a first step towards obtaining more general results, by providing lower bounds on the probability of error $p_{t}(\nu)$ for Gaussian bandits with equal variances.

We present here an asymptotic lower bound on $p_{t}(\nu)$ that directly yields a lower bound on $\kappa_{B}(\nu)$. Moreover, we provide a lower bound on the failure probability of consistent algorithms using uniform sampling. The proof of Theorem 12 bears similarities with that of Theorem 6, and we provide it in Appendix G.1. However, it is important to note that the informational quantities $c^{*}(\nu)$ and $I^{*}(\nu)$ defined in Theorem 12 are in general different from the quantities $c_{*}(\nu)$ and $I_{*}(\nu)$ previously defined for the fixed-confidence setting (see Theorem 6). Appendix C contains a few additional elements of comparison between these quantities in the case of one-parameter exponential families of distributions.

Let $\mathbf{\nu}=(\nu_{1},\nu_{2})$ be a two-armed bandit model such that $\mu_{1}>\mu_{2}$. In the fixed-budget setting, any consistent algorithm satisfies

Moreover, any consistent algorithm using a uniform sampling strategy satisfies

Gaussian distributions. As the Kullback-Leibler divergence between two Gaussian distributions—(9)—is symmetric with respect to the means when the variances are held fixed, it holds that $c^{*}(\nu)=c_{*}(\nu)$. To find a matching algorithm, we introduce the simple family of static strategies that draw $n_{1}$ samples from arm 1 followed by $n_{2}=t-n_{1}$ samples of arm 2, and then choose arm 1 if $\hat{\mu}_{1,n_{1}}>\hat{\mu}_{2,n_{2}}$, where $\hat{\mu}_{i,n_{i}}$ denotes the empirical mean of the $n_{i}$ samples from arm $i$. Assume for instance that $\mu_{1}>\mu_{2}$. Since $\hat{\mu}_{1,n_{1}}-\hat{\mu}_{2,n_{2}}-\mu_{1}+\mu_{2}\sim\mathcal{N}\left(0,{\sigma_{1}^{2}}/{n_{1}}+{\sigma_{2}^{2}}/{n_{2}}\right)$, the probability of error of such a strategy is upper bounded by

The right hand side is minimized when $n_{1}/(n_{1}+n_{2})={\sigma_{1}}/{(\sigma_{1}+\sigma_{2})}$, and the static strategy drawing $n_{1}=\left\lceil\sigma_{1}t/(\sigma_{1}+\sigma_{2})\right\rceil$ times arm 1 is such that

This shows in particular that for Gaussian distributions the two complexities are equal:

Exponential families. For exponential family bandit models, it can be observed that

Consider a two-armed exponential bandit model and $\alpha(\theta_{1},\theta_{2})$ be defined by

For all $t$, the static strategy that allocates $\left\lceil\alpha(\theta_{1},\theta_{2})t\right\rceil$ samples to arm 1, and recommends the empirical best arm, satisfies $p_{t}(\nu)\leq\exp(-tK^{*}(\theta_{1},\theta_{2}))$.

Theorem 13, whose proof can be found in Appendix G.2, shows in particular that for every exponential family bandit model there exists a consistent static strategy such that

For two-armed Bernoulli bandit models, $\kappa_{C}(\nu)>\kappa_{B}(\nu)$.

However, Lemma 27 shows that the strategy that uses uniform sampling and recommends the empirical best-arm satisfies $p_{t}(\nu)\leq\exp(-I^{*}(\nu)t)$, and matches the bound (17) of Theorem 12 (see Remark 28 in Appendix G.2). The fact that, just as in the fixed-confidence setting $I^{*}(\nu)$ is very close to $c^{*}(\nu)$ shows that the problem-dependent optimal strategy described above can be approximated by a very simple, universal algorithm that samples the arms uniformly. Figure 3 represents the different informational functions $c_{*},I_{*},c^{*}$ and $I^{*}$ when the mean $\mu_{1}$ varies, for two fixed values of $\mu_{2}$. It can be observed that $c^{*}(\nu)$ and $c_{*}(\nu)$ are almost indistinguishable from $I^{*}(\nu)$ and $I_{*}(\nu)$, respectively, while there is a gap between $c^{*}(\nu)$ and $c_{*}(\nu)$.

2 Lower Bound on pt​(ν)p_{t}(\nu) in More General Cases

Let $\nu$ and $\nu^{\prime}$ be two bandit models such that $\mathcal{S}_{m}^{*}(\nu)\neq\mathcal{S}_{m}^{*}(\nu^{\prime})$. Then

Let $\nu$ be a Gaussian bandit model such that $\mu_{1}>\mu_{2}\geq\dots\geq\mu_{K}$ and let

There exists a bandit model $\nu^{[a]}$, $a\in\{2,\dots,K\}$, (see Figure 4) which satisfies $H^{\prime}(\nu^{[a]})\leq H^{\prime}(\nu)$ and is such that

This result is to be compared to the lower bound of Audibert et al. 2010. While Theorem 16 does not really provide a lower bound on $\kappa_{B}(\nu)$, the complexity term $H(\nu)$ is close to the quantity that appears in Theorem 4 for the fixed-confidence setting (in the Gaussian case), which improves over the term $H_{2}(\nu)=\max_{i:\mu_{[i]}<\mu_{}}{i}{(\mu_{}-\mu_{[i]})^{-2}}$ featured in Theorem 4 of Audibert et al. 2010.

For $m>1$, building on the same ideas, Theorem 17 provides a first lower bound, which we believe leaves room for improvement.

Let $\nu$ be such that $\mu_{1}>\dots\mu_{m}>\mu_{m+1}>\dots>\mu_{K}$ and let

There exists $a\in\{1,\dots,m\}$ and $b\in\{m+1,\dots K\}$ such that the bandit model $\nu^{[a,b]}$ described on Figure 4 satisfies $H(\nu^{[a,b]})<H(\nu)$ and is such that

The proofs of Theorem 16 and Theorem 17 are very similar. For this reason, we provide in Appendix G.3 only the latter. Introducing the gaps $\Delta_{a}$ defined in (2), the precise definition of the modified problems $\nu^{[a]}$ and $\nu^{[a,b]}$ in the statement of the two results is:

Numerical Experiments

In this section, we focus on two-armed models and provide experimental experiments designed to compare the fixed-budget and fixed-confidence settings (in the Gaussian and Bernoulli cases) and to illustrate the improvement resulting from the adoption of the reduced exploration rate of Theorem 8.

In Figure 5, we consider two Gaussian bandit models with known common variance: the ‘easy’ one is $\{\mathcal{N}\left(0.5,0.25\right),\mathcal{N}\left(0,0.25\right)\}$, corresponding to $\kappa_{C}=\kappa_{B}=\kappa=8$, on the left; and the ‘difficult’ one is $\{\mathcal{N}\left(0.01,0.25\right),\mathcal{N}\left(0,0.25\right)\}$, that is $\kappa=2\times 10^{4}$, on the right. In the fixed-budget setting, stars (’*’) report the probability of error $p_{n}(\nu)$ as a function of $n$. In the fixed-confidence setting, we plot both the empirical probability of error by circles (’O’) and the specified maximal error probability $\delta$ by crosses (’X’) as a function of the empirical average of the running times. Note the logarithmic scale used for the probabilities on the y-axis. All results are averaged over $N=10^{6}$ independent Monte Carlo replications. For comparison purposes, a plain line represents the theoretical rate $t\mapsto\exp(-t(1/\kappa))$ which is a straight line on the log scale.

In the fixed-confidence setting, we report results for elimination algorithms of the form (14) for three different exploration rates $\beta(t,\delta)$. The exploration rate we consider are: the provably-PAC rate of Robbins’ algorithm $\log({t}/{\delta})$ (large blue symbols), the conjectured optimal exploration rate $\log({(\log(t)+1)}/{\delta})$, almost provably $\delta$-PAC according to Theorem 8 (bold green symbols), and the rate $\log({1}/{\delta})$, which would be appropriate if we were to perform the stopping test only at a single pre-specified time (orange symbols). For each algorithm, the log probability of error is approximately a linear function of the number of samples, with a slope close to $-1/\kappa$, where $\kappa$ is the complexity. A first observation is that the ’traditional’ rate of $\log({t}/{\delta})$ is much too conservative, with running times for the difficult problem (right plot) which are about three times longer than those of other methods for comparable error rates. As expected, the rate $\log((\log(t)+1)/\delta)$ significantly reduces the running times while maintaining proper control of the probability of failure, with empirical error rates (’O’ symbols) below the corresponding confidence parameters $\delta$ (represented by ’X’ symbols). Conversely, the use of the non-sequential testing threshold $\log(1/\delta)$ seems too risky, as one can observe that the empirical probability of error may be larger than $\delta$ on difficult problems. To illustrate the gain in sample complexity resulting from the knowledge of the means, we also represented in red the performance of the SPRT algorithm mentioned in the introduction of Section 5 along with the theoretical relation between the probability of error and the expected number of samples, materialized as a dashed line. The SPRT stops for $t$ such that $|(\mu_{1}-\mu_{2})(S_{1,t/2}-S_{2,t/2})|>\log(1/\delta)$.

Robbins’ algorithm is $\delta$-PAC and matches the complexity (which is illustrated by the slope of the measures), though in practice the use of the exploration rate $\log((\log(t)+1)/\delta)$ leads to huge gain in terms of number of samples used. It is important to keep in mind that running times play the same role as error exponents and hence the threefold increase of average running times observed on the rightmost plot of Figure 5 when using $\beta(t,\delta)=\log({t}/{\delta})$ is really prohibitive.

On Figure 6, we compare on two Bernoulli bandit models the performance of the SGLRT algorithm described in Section 4.2 (Algorithm 2) using two different exploration rates, $\log(1/\delta)$ and $\log((\log(t)+1)/\delta)$, to the 1/2-elimination stopping rule (Algorithm 1) that stops when the difference of empirical means exceeds the threshold $\sqrt{2\beta(t,\delta)/t}$ (for the same exploration rates). Plain lines also materialize the theoretical optimal rate $t\mapsto\exp(-t/\kappa_{C}(\nu))$ and the rate attained by the 1/2-Elimination algorithm $t\mapsto\exp(-t/\kappa^{\prime})$, where $\kappa^{\prime}=2/(\mu_{1}-\mu_{2})^{2}$. On the bandit model $0.51-0.5$ (right) these two rates are very close and SGLRT mostly coincides with Elimination, but on the bandit model $0.2-0.1$ (left) the practical gain of the use of a more sophisticated stopping strategy is well illustrated. Besides, our experiments show that SGLRT using $\log((\log(t)+1)/\delta)$ is $\delta$-PAC on both the (relatively) easy and difficult problems we consider, unlike the other algorithms considered.

If one compares the results for the fixed-budget setting (in purple) to those for the best $\delta$-PAC algorithm (or conjectured $\delta$-PAC for SGLRT in the Bernoulli case), in green, one can observe that to obtain the same probability of error, the fixed-confidence algorithm usually needs an average number of samples that is about twice larger than the deterministic number of samples required by the fixed-budget setting algorithm. This remark should be related to the fact that a $\delta$-PAC algorithm is designed to be uniformly good across all problems, whereas consistency is a weak requirement in the fixed-budget setting: any strategy that draws both arm infinitely often and recommends the empirical best is consistent. Figure 5 also shows that when the values of $\mu_{1}$ and $\mu_{2}$ are unknown, the sequential version of the test is no more preferable to its batch counterpart and can even become much worse if the exploration rate $\beta(t,\delta)$ is chosen too conservatively. This observation should be mitigated by the fact that the sequential (or fixed-confidence) approach is adaptive with respect to the difficulty of the problem whereas it is impossible to predict the efficiency of a batch (or fixed-budget) experiment without some prior knowledge regarding the difficulty of the problem under consideration.

Conclusion

Our aim with this paper has been to provide a framework for evaluating, in a principled way, the performance of fixed-confidence and fixed-budget algorithms designed to identify the best arm(s) in stochastic environments.

For two-armed bandits, we obtained rather complete results, identifying the complexity of both settings in important parametric families of distributions. In doing so, we observed that standard testing strategies based on uniform sampling are optimal or close to optimal for Gaussian distributions with matched variance or Bernoulli distributions but can be improved (by non-uniform sampling) for Gaussian distributions with distinct variances. This latter observation can certainly be generalized to other models, starting with the case of Gaussian distributions whose variances are a priori unknown. In the case of Bernoulli distributions, we have also shown that fixed-confidence algorithms that use the difference of the empirical means as a stopping criterion are bound to be sub-optimal. Finally, we have shown, through the comparison of the complexities $\kappa_{C}(\nu)$ and $\kappa_{B}(\nu)$, that the behavior observed when testing fully specified alternatives where fixed confidence (or sequential) algorithms may be ‘faster on average’ than the fixed budget (or batch) ones is not true anymore when the parameters of the models are unknown.

For models with more than two arms, we obtained the first generic (i.e. not based on the sub-Gaussian tail assumption) distribution-dependent lower bound on the complexity of $m$ best-arms identification in the fixed-confidence setting (Theorem 4). Currently available performance bounds for algorithms performing $m$ best-arms identification—those of Kaufmann and Kalyanakrishnan 2013 notably—show a small gap with this result and it is certainly of interest to investigate whether those analyses and/or the bound of Theorem 4 may be improved to bridge the gap. For the fixed-budget setting we made only a small step towards the understanding of the complexity of $m$ best-arms identification and our results can certainly be greatly improved.

Appendix A Changes of Distributions

Let $\nu$ and $\nu^{\prime}$ be two bandit models such that for all $a\in\{1,K\}$ the distributions $\nu_{a}$ and $\nu_{a}^{\prime}$ are mutually absolutely continuous. For each $a$, there exists a measure $\lambda_{a}$ such that $\nu_{a}$ and $\nu^{\prime}_{a}$ have a density $f_{a}$ and $f^{\prime}_{a}$ respectively with respect to $\lambda_{a}$. One can introduce the log-likelihood ratio of the observations up to time $t$ under an algorithm $\mathcal{A}$:

Let $\sigma$ be any stopping time with respect to $\mathcal{F}_{t}$. For every event $\mathcal{E}\in\mathcal{F}_{\sigma}$ (i.e., $\mathcal{E}$ such that $\mathcal{E}\cap(\sigma=t)\in\mathcal{F}_{t}$),

To prove Lemma 1, we state a first inequality on the expected log-likelihood ratio in Lemma 19, which is of independent interest.

Let $\sigma$ be any almost surely finite stopping time with respect to $\mathcal{F}_{t}$. For every event $\mathcal{E}\in\mathcal{F}_{\sigma}$,

Lemma 1 easily follows: introducing $(Y_{a,s})$, the sequence of i.i.d. samples successively observed from arm $a$, the log-likelihood ratio $L_{t}$ can be rewritten

Wald’s Lemma (see e.g., Siegmund 1985) applied to $L_{\sigma}=\sum_{a=1}^{K}\sum_{s=1}^{N_{a}(\sigma)}\log\left(\frac{f_{a}(Y_{a,s})}{f^{\prime}_{a}(Y_{a,s})}\right)$ yields

Combining this equality with the inequality in Lemma 19 completes the proof.

Proof of Lemma 19. Let $\sigma$ be a stopping time with respect to $(\mathcal{F}_{t})$.

A.2 Proof of Lemma 15

The proof bears strong similarities with that of Lemma 1, but an extra ingredient is needed: Lemma 4 of Bubeck et al. 2013a, that provides a lower bound on the sum of type I and type II probabilities of error in a statistical test.

Let $\rho_{0}$,$\rho_{1}$ be two probability distributions supported on some set $\mathcal{X}$, with $\rho_{1}$ absolutely continuous with respect to $\rho_{0}$. Then for any measurable function $\phi:\mathcal{X}\rightarrow\{0,1\}$, one has

Let $\nu$ and $\nu^{\prime}$ be two bandit models that do not have the same set of optimal arms. We denote by $\mathcal{S}_{1},\dots,\mathcal{S}_{M}$ the $M={K\choose m}$ subsets of $m$, ordered so that $\mathcal{S}_{1}$ (resp. $\mathcal{S}_{2}$) is the set of $m$ best arms in problem $\nu$ (resp. $\nu^{\prime}$). One has

A.3 Proof of Lemma 18

The result for $n=1$ follows from the following calculation:

Observing that on the event $(A_{n+1}=a)$, $L_{n+1}(Z_{1},\dots,Z_{n},z)=L_{n}(Z_{1},\dots,Z_{n})+\log\frac{f_{a}(z)}{f^{\prime}_{a}(z)}$ leads to:

Hence, the statement is true for all $n$, and we have shown that for every $\mathcal{E}\in\mathcal{F}_{n}$,

Let $\sigma$ be a stopping time w.r.t. $(\mathcal{F}_{n})$ and $\mathcal{E}\in\mathcal{F}_{\sigma}$.

Appendix B A Short Proof of Burnetas and Katehakis’ Lower Bound on the Regret

In the regret minimization framework, briefly described in the Introduction, a bandit algorithm only consists in a sampling rule (there is no stopping rule nor recommendation rule). The arms must be chosen sequentially so as to minimize the regret, that is strongly related to the number of draws of the sub-optimal arms (using the notation $\mu^{*}=\mu_{}$):

The lower bound given by Lai and Robbins 1985 on the regret holds for families of distributions parameterized by a (single) real parameter. Their result has been generalized by Burnetas and Katehakis 1996 to larger classes of parametric distributions. The version we give here deals with identifiable classes of the form $\mathcal{M}=(\mathcal{P})^{K}$, where $\mathcal{P}$ is a set of probability measures satisfying

Let $\mathcal{M}$ be an identifiable class of bandit models. Consider a bandit algorithm such that for all $\nu\in\mathcal{M}$ having a unique optimal arm, for all $\alpha\in(0,1]$, $R_{T}(\nu)=o(T^{\alpha})$. Then, for all $\nu\in\mathcal{M}$,

Clearly, $\mathcal{E}_{T}\in\mathcal{F}_{T}$. From Lemma 1, applied to the stopping time $\sigma=T$ a.s.,

The event $\mathcal{E}_{T}$ is not very likely to hold under the model $\nu$, in which the optimal arm should be drawn of order $T-C\log(T)$ times, whereas it is very likely to happen under $\nu^{\prime}$, in which arm 1 is sub-optimal and thus only drawn little. More precisely, Markov inequality yields

From the formulation (20), every algorithm that is uniformly efficient in the above sense satisfies

Figure 7 displays the geometric constructions corresponding to the complexity terms of Theorems 4 and 6, respectively. As seen on the picture, the convexity of the function $\theta\mapsto K(\theta_{i},\theta)$, for any value of $\theta_{i}$, implies that

It is well known that in exponential families, the Kullback-Leibler divergence between distributions parameterized by their natural parameter, $\theta$, may be related to the Bregman divergence associated with the log-partition function $b$:

From this representation, its is straightforward to show that

$\theta^{*}$ corresponds to the dual parameter $\mu^{*}:=\dot{b}(\theta^{*})=(b(\theta_{2})-b(\theta_{1}))/(\theta_{2}-\theta_{1})$,

Indexing the distributions in the exponential family by their mean $\mu=\dot{b}(\theta)$ rather than their natural parameter $\theta$ and using the dual representation

where $b^{\star}(\mu):=\sup_{\theta}(\theta\mu-b(\theta))$ is the Fenchel conjugate of $b$, similarly yields

$\theta_{*}=\dot{b}^{\star}(\mu_{*})=(b^{\star}(\mu_{2})-b^{\star}(\mu_{1}))/(\mu_{2}-\mu_{1})$;

Appendix D Proof of Theorem 9

by an union bound and Chernoff bound applied to $d_{t}-(\mu_{1}-\mu_{2})\sim\mathcal{N}\left(0,\sigma^{2}_{t}(\alpha)\right)$. The choice of $\beta(t,\delta)$ mentioned above ensures that the series in the right hand side is upper bounded by $\delta$, which shows the algorithm is $\delta$-PAC:

To upper bound the expected sample complexity, we start by upper bounding the probability that $\tau$ exceeds some deterministic time $T$:

The last inequality follows from Chernoff bound and holds for $T$ such that $(\mu_{1}-\mu_{2})>\sqrt{2\sigma^{2}_{T}(\alpha)\beta(T,\delta)}.$ Now, for $\gamma\in(0,1)$ we introduce

This quantity is well defined as $\sigma^{2}_{t}(\alpha)\beta(t,\delta)$ goes to zero when $t$ goes to infinity. Then,

The following Lemma, whose proof can be found below, helps us bound this last quantity.

For every $\beta,\eta>0$ and $s\in[1,e/2]$, the following implication is true:

Applying Lemma 22 with $\eta=\delta$, $s=1+r$ and $\beta={(1-{\gamma})^{3}(\mu_{1}-\mu_{2})^{2}}/{(2(\sigma_{1}+\sigma_{2})^{2})}$ leads to

Now for $\epsilon>0$ fixed, choosing $r$ and $\gamma$ small enough leads to

where $\mathcal{C}$ is a constant independent of $\delta$. It can be noted that $\mathcal{C}(\mu_{1},\mu_{2},\sigma_{1},\sigma_{2},\epsilon)$ goes to infinity when $\epsilon$ goes to zero, but for a fixed $\epsilon>0$,

Proof of Lemma 22. Lemma 22 easily follows from the fact that for $\eta>0$ and $s\in[1,e/2]$,

Indeed, it suffices to apply this statement to $x=x\beta$ and $\eta=\eta\beta^{s}$. The mapping $x\mapsto e^{x}-x^{s}/\eta$ is increasing when $x\geq s$. As $x_{0}\geq s$, it suffices to prove that $x_{0}$ defined above satisfies $e^{x_{0}}\geq x_{0}^{s}/\eta$.

where we use that for all $y$, $\log(y)\leq\frac{1}{e}y$. Then, using that $s\geq 1$,

For $s\leq\frac{e}{2}$, $\log(s)+\log(2)\leq 1$, hence

which is equivalent to $e^{x_{0}}\geq\frac{x_{0}^{s}}{\eta}$ and concludes the proof.

Appendix E A Refined Exploration Rate for α\alpha-Elimination

According to (15), to prove Theorem 8 it is enough to show that for

if $S_{t}=\sum_{s=1}^{t}X_{s}$ is a sum of i.i.d $\mathcal{N}\left(0,1\right)$ random variables, one has

Let $z=\log(1/\delta)$. Using Lemma 7, one can write, choosing $x=z+3\log z$ and $\beta=3/2$,

It can be shown numerically that for $z\geq 2.03$,

Thus for $\delta\leq\exp(-2.03)\leq 0.1$, inequality (24) holds.

E.2 Proof of Lemma 7.

We start by stating three technical lemmas, whose proofs are partly omitted.

For every $\eta>0$, every positive integer $k$, and every integer $t$ such that $(1+\eta)^{k-1}\leq t\leq(1+\eta)^{k}$,

Let $t$ be such that $(1+\eta)^{k-1}\leq t\leq(1+\eta)^{k}$. Then,

We use that $\eta\leq e-1$ to obtain the last inequality since this condition implies

For $k\geq 1$, let $z_{k}=x+\beta\log\left(k\log(1+\eta)\right)$ and $\lambda_{k}=\sigma^{-1}\sqrt{2z_{k}A(\eta)/(1+\eta)^{k-1/2}}$.

Lemma 25 shows that for every $t\in T_{k}$,

One chooses $\eta^{2}=8/x$ for $x$ such that $x\geq\frac{8}{(e-1)^{2}}$ (which ensures $\eta\leq e-1$). Using Lemma 24, one obtains that $\exp(-A(\eta)x)\leq\sqrt{e}\exp(-x)$. Moreover,

using the lower bound on $A(\eta)$ given in Lemma 24 and the fact that $A(\eta)$ is upper bounded by 1.

Appendix F Bernoulli Bandit Models

Assume that $\mu_{1}<\mu_{2}$. Recall the KL-LUCB algorithm of Kaufmann and Kalyanakrishnan 2013. For two-armed bandit models, this algorithm samples the arms uniformly and builds for both arms a confidence interval based on KL-divergence $\mathcal{I}_{a}(t)=[l_{a,t/2},u_{a,t/2}]$, with

Additionally, as mentioned before, $I_{*}(x,y)$ is very close to the quantity $d_{*}(x,y)$ and one has more precisely $I_{*}(x,y)<d_{*}(x,y)$. Using all this, we can upper bound the probability of error of Algorithm 2 in the following way.

F.2 An Asymptotic Bound for the Stopping Time

Consider a strategy that uses uniform sampling and a stopping rule of the form

where $f$ is a continuous function such that $f(\mu_{1},\mu_{2})\neq 0$ and $g(t)=o(t^{r})$ for all $r>0$. Then for all $\epsilon>0$,

We can use Lemma 22 to bound the right term in the right hand side, which shows that there exists a constant $C(\epsilon,\mu_{1},\mu_{2})$ independent of $\delta$ such that

Appendix G Upper and Lower Bounds in the Fixed-Budget Setting

Without loss of generality, assume that the bandit model $\nu=(\nu_{1},\nu_{2})$ is such that $a^{*}=1$. Consider any alternative bandit model $\nu^{\prime}=(\nu_{1}^{\prime},\nu_{2}^{\prime})$ in which $a^{*}=2$. Let $\mathcal{A}$ be a consistent algorithm such that $\tau=t$ and consider the event $A=(\hat{\mathcal{S}}_{1}=1)$. Clearly $A\in\mathcal{F}_{t}=\mathcal{F}_{\tau}.$

Lemma 1 applied to the stopping time $\sigma=t$ a.s. and the event $A$ gives

Taking the limsup and letting $\epsilon$ go to zero, one can show that

Optimizing over the possible model $\nu^{\prime}$ satisfying $\mu_{1}^{\prime}<\mu_{2}^{\prime}$ to make the right hand side of the inequality as small as possible gives the result.

G.2 An Optimal Static Strategy for Exponential Families

Bounding the probability of error of a static strategy using $n_{1}$ samples from arm 1 and $n_{2}$ samples from arm 2 relies on the following lemma.

The function $\alpha\mapsto g_{\alpha}(\theta_{1},\theta_{2})$, can be maximized analytically, and the value $\alpha^{*}$ that realizes the maximum is given by

When $\mu_{1}>\mu_{2}$, applying Lemma 27 with $n_{1}=n_{2}=t/2$ yields

which shows that the strategy using uniform sampling and recommending the empirical best arm matches the lower bound (17) in Theorem 12.

For every $\lambda>0$, multiplying by $\lambda$, taking the exponential of the two sides and using Markov’s inequality (this technique is often referred to as Chernoff’s method), one gets

Using that $b^{\prime}(x)=\mu(x)$, we can compute the derivative of $G$ and see that this function as a unique minimum in $\lambda^{*}$ given by

using that $\theta\mapsto\mu(\theta)$ is one-to-one. One can also show that

G.3 Proof of Theorem 17

These two cases are very similar, and the idea is to propose an easier alternative model in which we change only arm $a$ and $b$, the arms that are less drawn among the set of good and the set of bad arms. Assume that we are in Case 1. We introduce $\nu^{[a,b]}$ a Gaussian bandit model such that:

In $\nu^{[a,b]}$ good arm $a$ becomes a bad arm and bad arm $b$ becomes a good arm. One can easily check (or convince oneself with Figure 4) that $H(\nu^{[a,b]})\leq H(\nu)$ and as already explained, $\nu$ and $\nu^{[a,b]}$ do not share their optimal arms. Thus Lemma 15 yields