On the Complexity of A/B Testing

Introduction

A/B Testing is a popular procedure used, for instance, for website optimization: two versions of a webpage, say A and B, are empirically compared by being presented to users. Each user only sees one of the two versions, and the goal is to determine which version is preferable. We assume that the users provide a real-valued index of the quality of the pages, which is modeled by probability distributions $\nu_{A}$ and $\nu_{B}$, with respective means $\mu_{A}$ and $\mu_{B}$. For example, a standard objective is to determine which webpage has the highest conversion rate (probability that a user actually becomes a customer) by receiving binary feedback from the users.

Methods for A/B Testing are often viewed as statistical tests of the hypothesis $H_{0}:(\mu_{A}\leq\mu_{B})$ against $H_{1}:(\mu_{A}>\mu_{B})$. One may consider either classical tests, based on a number of samples $n_{A}$ and $n_{B}$ from each distribution fixed before the experiment, or sequential tests, based on paired samples ($X_{s},Y_{s}$) of $\nu_{A},\nu_{B}$ and in which a randomized stopping rule determines when the experiment is to be terminated. In both of these test settings, the sampling schedule is determined in advance, which is a possible source of sub-optimality as A/B Testing algorithms could take advantage of past observations to provide a smarter choice of the page to be displayed to the next user. In the sequel, we investigate whether A/B Testing could benefit from an adaptive sampling schedule. Ignoring the possible long-term effects on users of presenting one or the other option, we consider it as a particular instance of best arm identification in a two-armed bandit model.

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, for a given bandit model $\nu$ and a given $\delta>0$, a fixed-confidence optimal strategy uses an average number of samples of order $\kappa_{C}(\nu)\log(1/\delta)$, whereas a fixed-budget optimal strategy uses approximately $t=\kappa_{B}(\nu)\log(1/\delta)$ draws in order to ensure a probability of error at most equal to $\delta$. Most of the existing performance bounds for the fixed confidence and fixed budget settings can be expressed using these complexity measures.

where $\text{KL}(\nu_{i},\nu_{j})$ denotes the Kullback-Leibler divergence between distributions $\nu_{i}$ and $\nu_{j}$. 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 first step in the attempt to similarly characterize the complexity of pure exploration, where the goal is to determine the best arms without trying to maximize the cumulated observations.

The fixed-budget setting has been studied recently by Audibert et al. (2010); Bubeck et al. (2013). In two-armed bandit problems, the algorithms introduced in these papers boil down to sampling each arm $t/2$ times—$t$ denoting the total budget—and recommending the empirical best arm. A simple upper bound on the probability of error of this strategy can be derived, and this result paired with the lower bound of Audibert et al. (2010) yields, for bounded bandit models such that $\mu_{a}\in[\alpha;1-\alpha]$ for $a\in\{1,2\}$:

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

Contents of the paper. Compared to existing results, we provide general lower bounds on $\kappa_{B}(\nu)$ and $\kappa_{C}(\nu)$ that: (i) are tighter, leading in specific parametric cases to a precise evaluation of these complexities; (ii) do not require unnecessary support assumptions; and (iii) are stated in terms of information divergences between the distributions $\nu_{1}$ and $\nu_{2}$ rather than in terms of the gap $\mu_{1}-\mu_{2}$. As can be expected, we will indeed confirm that the inverse of the squared gap $(\mu_{1}-\mu_{2})^{2}$ is the relevant measure of complexity only in the Gaussian case, and an approximation (in the spirit of Pinsker’s inequality) for sub-Gaussian distributions.

Lower bounds on the sample complexity (resp. probability of error) of algorithms using the uniform sampling strategy in the fixed-confidence (resp. fixed-budget) setting are also derived and we show that for Gaussian bandit models with different variances, there is a significant gain in using a non-uniform sampling strategy. For Bernoulli bandits however, we show that little can be gained by departing from uniform sampling, and we therefore propose close-to-optimal tests both for the batch and sequential settings. For Gaussian bandits with a known common variance the optimal algorithm uses uniform sampling. In this specific case, we propose an improved $\delta$-PAC stopping rule, illustrating its performance through numerical experiments.

Our contributions follow from two main mathematical results: Lemma 6.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. Lemma 6.2 is a tight deviation inequality for martingales with sub-Gaussian increments, in the spirit of the Law of Iterated Logarithm.

The paper is structured as follows. Section 2 presents a distribution-dependent lower bound on both $\kappa_{B}(\nu)$ and $\kappa_{C}(\nu)$ under the some identifiability assumption, as well as lower bounds for algorithms using uniform sampling. Gaussian bandit models are then studied in details in Section 3, and Bernoulli bandit models in Section 4. Section 5 includes a practical illustration of the performance of matching algorithms for Gaussian bandits, as well as a practical comparison of the fixed-confidence and fixed-budget settings. The most important elements of proof are gathered in Section 6, with the rest of the proofs in the Appendix.

Lower Bounding the Complexity

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

we make the assumption that there exists a set $\mathcal{N}$ such that for all $\nu=(\nu_{1},\nu_{2})\in\mathcal{M}$, for $a\in\{1,2\},\nu_{a}\in\mathcal{N}$ and that $\mathcal{N}$ satisfies

A class $\mathcal{M}$ of bandit models satisfying this property is called identifiable. For $\mathcal{M}$ an identifiable class of bandit models, Theorem 2.1 provides lower bounds on $\kappa_{B}(\nu)$ and $\kappa_{C}(\nu)$ for every $\nu\in\mathcal{M}$. The proof of this theorem is based on changes of distribution and detailed in Section 6.

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

In the fixed-confidence setting any algorithm that is $\delta$-PAC on $\mathcal{M}$ satisfies, when $\delta\leq 0.15$,

In particular, Theorem 2.1 implies that $\kappa_{B}(\nu)\geq 1/{c^{*}(\nu)}$ and $\kappa_{C}(\nu)\geq 1/{c_{*}(\nu)}$. Proceeding similarly, one can obtain lower bounds for the algorithms that use uniform sampling of both arms. The proof of the following result is easily adapted from that of Theorem 2.1 (cf. Section 6), using that each arm is drawn $\tau/2$ times.

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 using a uniform sampling strategy satisfies

In the fixed-confidence setting, any algorithm that is $\delta$-PAC on $\mathcal{M}$ and uses a uniform sampling strategy satisfies, for $\delta\leq 0.15$,

Obviously, one always has $I^{*}(\nu)\leq c^{*}(\nu)$ and $I_{*}(\nu)\leq c_{*}(\nu)$ suggesting that uniform sampling can be sub-optimal. It is possible to give explicit expressions for the quantities $c^{*}(\nu),c_{*}(\nu)$ and $I^{*}(\nu),I_{*}(\nu)$ for specific classes of parametric bandit models that will be considered in the rest of the paper. In the case of Gaussian bandits with known variance (see Section 3):

Hence, the lower bounds of Theorem 2.1 are equal in this case, and we provide in Section 3 matching upper bounds confirming that indeed $\kappa_{B}(\nu)=\kappa_{C}(\nu)$. In addition, the observation that $2I^{*}(\nu)\geq c^{*}(\nu)\geq I^{*}(\nu)$ implies that, except when $\sigma_{1}=\sigma_{2}$, strategies based on uniform sampling are sub-optimal.

The values of $c^{*}(\nu)$ and $c_{*}(\nu)$ can also be computed for canonical one-parameter exponential families with density with respect to some reference measure given by

For exponential family bandits the quantities $c^{*}(\nu)$ and $c_{*}(\nu)$ are not equal in general, although it can be shown that it is the case when the log-partition function $b(\theta)$ is (Fenchel) self-conjugate (e.g., for Gaussian and exponential variables). In Section 4, we will focus on the case of Bernoulli models for which $c^{*}(\nu)>c_{*}(\nu)$. By exhibiting a matching strategy in the fixed-budget case, we will show that this implies that $\kappa_{C}(\nu)>\kappa_{B}(\nu)$ in this case.

The Gaussian Case

We study in this Section the class of two-armed Gaussian bandit models with known variances defined by (1), where $\sigma_{1}$ and $\sigma_{2}$ are fixed. In this case, we observed above that the lower bounds of Theorem 2.1 are similar, because $c^{*}(\nu)=c_{*}(\nu)$. We prove in this section that indeed

by exhibiting strategies that reach these performance bounds. These strategies are based on the simple recommendation of the empirical best arm but use non-uniform sampling in cases where $\sigma_{1}$ and $\sigma_{2}$ differ. When $\sigma_{1}=\sigma_{2}$ we provide in Theorem 3.1 an improved stopping rule that is $\delta$-PAC but results in a significant reduction of the running time of fixed-confidence tests.

We consider 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 easily upper bounded as:

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

which matches the bound of Theorem 2.1 for Gaussian bandit models.

2 Fixed-Confidence Setting

We start with the simpler case $\sigma_{1}=\sigma_{2}=\sigma$, where the quantity $I_{*}(\nu)$ introduced in Theorem 2.2 coincides with $c_{*}(\nu)$, which suggests that uniform sampling could be optimal. A uniform sampling strategy is equivalent to collecting paired samples $(X_{s},Y_{s})$ from both arms. The difference $X_{s}-Y_{s}$ is Gaussian 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 the probability of error is uniformly bounded by $\delta$. Robbins (1970) proposes such a test that stops after a number of samples

Note that any elimination strategy that is $\delta$-PAC and uses a threshold function smaller than Robbins’ also matches our asymptotic lower bound, while being strictly more efficient than Robbins’ rule. For practical purpose, it is therefore interesting to exhibit smaller exploration rates $\beta(t,\delta)$ leading to a $\delta$-PAC algorithm. The probability of error of such an algorithm is upper bounded, for example for $\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. Recently, Jamieson et al. (2013) proposed an explicit confidence region inspired by the LIL. However, Lemma 1 of (Jamieson et al., 2013) cannot be used to upper bound (4) by $\delta$ and we provide in Section 6 a result derived independently (Lemma 6.2) that achieves this goal and yields the following result.

For $\delta$ small enough, the elimination strategy (3) is $\delta$-PAC with

2.2 Mismatched Variances

In the case where $\sigma_{1}\neq\sigma_{2}$, we rely on an $\alpha$-elimination strategy, described in Algorithm 1. 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)$ which ensures that, 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)$. 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 3.2.1, for which Theorem 3.1 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 5.

The Bernoulli Case

We consider in this section the class of Bernoulli bandit models defined by

In this Section, we prove that $\kappa_{C}(\nu)>\kappa_{B}(\nu)$ for Bernoulli bandit models (Proposition 4.2). To do so, we first introduce a static strategy matching the lower bound of Theorem 2.1 in the fixed-budget case (Proposition 4.1). This strategy is reminiscent of the algorithm exhibited for Gaussian bandits in Section 3 and uses parameter-dependent non uniform sampling. This strategy is not directly helpful in practice but we show that it can be closely approximated by an algorithm using the uniform sampling strategy. In the fixed-confidence setting we similarly conjecture that little can be gained from using a non-uniform sampling strategy and propose an algorithm based on a non-trivial stopping strategy that is believed to match the bound of Theorem 2.2.

Let $\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(-K^{*}(\theta_{1},\theta_{2})t)$.

This result, proved in Appendix LABEL:proof:ConcExp, shows in particular that for every $\nu\in\mathcal{M}$ there exists a consistent static strategy such that

For all $\nu\in\mathcal{M}$, $\kappa_{C}(\nu)>\kappa_{B}(\nu)$.

In the specific case of Bernoulli distributions, there is a strong incentive to use uniform sampling: the quantities $I^{*}(\nu)$ and $I_{*}(\nu)$ introduced in Theorem 2.2 appear to be very close to $c^{*}(\nu)$ and $c_{*}(\nu)$ respectively. This fact is illustrated in Figure 1, on which we represent these different quantities, that are functions of the means $\mu_{1},\mu_{2}$ of the arms, as a function of $\mu_{1}$, for two fixed values of $\mu_{2}$. Therefore, algorithms matching the bounds of Theorem 2.2 provide upper bounds on $\kappa_{B}(\nu)$ (resp. $\kappa_{C}(\nu)$) very close to $1/c^{*}(\nu)$ (resp. $1/c_{*}(\nu)$). In the fixed-budget setting, Lemma LABEL:lem:ConcExp shows that the strategy with uniform sampling that recommends the empirical best arm, satisfies $p_{t}(\nu)\leq e^{-tI^{*}(\nu)}$, and matches the bound of Theorem 2.2 (see Remark LABEL:rem:Match in Appendix LABEL:proof:ConcExp). Hence, problem-dependent optimal strategy described above can be approximated by a very simple, universal algorithm.

Similarly, finding an algorithm for the fixed-confidence setting sampling the arms uniformly and matching the bound of Theorem 2.2 is a crucial matter. This boils down to finding a good 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, such a strategy can be analyzed with the tools provided in this paper: the algorithm stopping for $t$ such that $\hat{\mu}_{1,t/2}-\hat{\mu}_{2,t/2}>\sqrt{{2\beta(t,\delta)}/{t}}$ with $\beta(t,\delta)$ as in Theorem 3.1 is $\delta$-PAC and its expected running time bounded by ${2}/{(\mu_{1}-\mu_{2})^{2}}\log\frac{1}{\delta}+o\left(\log\frac{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 Theorem 2.2. 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. The stopping rule we propose to circumvent this drawback is the following:

Numerical Experiments and Discussion

The goal of this Section is twofold: to compare results obtained in the fixed-budget and fixed-confidence settings and to illustrate the improvement resulting from the adoption of the reduced exploration rate of Theorem 3.1.

In Figure 2, we consider two bandit models: the ’easy’ one is $\mathcal{N}\left(0.5,0.25\right)\otimes\mathcal{N}\left(0,0.25\right)$, $\kappa=8$ (left) and the ’difficult’ one is $\mathcal{N}\left(0.01,0.25\right)\otimes\mathcal{N}\left(0,0.25\right)$, $\kappa=20000$ (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 on $N=10^{6}$ independent Monte Carlo replications. For comparison purposes, a plain line represents the theoretical rate $x\mapsto\exp(-x/\kappa)$ which is a straight line on the log scale.

In the fixed-confidence setting, we report results for algorithms of the form (3) with $g(t,\delta)=\sqrt{2\sigma^{2}t\beta(t,\delta)}$ 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 3.1 (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. We can visualize the gain in sample complexity achieved by smaller exploration rates, but while the rate $\log((\log(t)+1)/\delta)$ appears to guarantee the desired probability of error across all problems, the use of $\log(1/\delta)$ seems too risky, as one can see that the probability of error becomes larger than $\delta$ on difficult problems. To illustrate the gain in sample complexity when the means of the arms are known, we add in red the SPRT algorithm mentioned in the introduction 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)$.

If one compares on each problem the results for the fixed-budget setting to those for the best $\delta$-PAC algorithm (in green), one can see that to obtain the same probability of error, the fixed-confidence algorithm needs an average number of samples of order at least 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 2 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 problem under consideration.

Elements of Proof

The cornerstone of the proof of all the lower bounds given in this paper is Lemma 6.1 which relates the probabilities of the same event under two different models to the expected number of draws of each arm. Its proof, which may be found in Appendix A, encapsulates the technical aspects of the change of distributions. $N_{a}(t)$ denotes the number of draws of arm $a$ up to round $t$ and $N_{a}=N_{a}(\tau)$ is the total number of draws of arm $a$ by some algorithm $\mathcal{A}$.

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$ and the event $A=(\hat{a}=1)$ where $\hat{a}$ is the arm chosen by algorithm $\mathcal{A}$. Clearly $A\in\mathcal{F}_{\tau}.$

using that $\tau=N_{1}+N_{2}$. 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 gives the result, using moreover that for $\delta\leq 0.15$, it can be shown that $d(1-\delta,\delta)\geq\log({1}/(2\delta))$.

Inequality (7) in Lemma 6.1 applied to $A$ yields

Taking the limsup (denoted by $\overline{\lim}$) 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.

2 Proof of Theorem 3.1

Let $\beta(t,\delta)$ be of the form $\beta(t,\delta)=\log\frac{1}{\delta}+c\log\log\frac{1}{\delta}+d\log\log(et)$, for some constants $c>0$ and $d>1$. Lemma 6.2 yields

where $z:=\log\frac{1}{\delta}>0$. To upper bound the above probability by $\delta$, at least for large values of $z$ (which corresponds to small values of $\delta$), it suffices to choose the parameters $c$ and $d$ such that

For $c={d}/{2}$, the left hand side tends to ${\sqrt{e}\zeta\left(d\right)}/{(2\sqrt{2})^{d}}$ when $z$ goes to infinity, which is smaller than 1 for $d\geq 1.47$. Thus, for $\delta$ small enough, the desired inequality holds for $d={3}/{2}$ and $c={3}/{4}$, which corresponds to the exploration rate of Theorem 3.1.

Conclusion

We provide distribution-dependent lower bounds for best-arm identification in the context of two-armed bandit models. These bounds involve information-theoretic quantities that reflect the typical causes of failure, which are different from those appearing in regret analysis. For Gaussian and Bernoulli bandit models, we exhibit matching algorithms showing that these bounds are (mostly) tight, highlighting relationships between the complexities of the fixed-budget and fixed-confidence settings. Our numerical experiments illustrate the significance of using appropriate exploration rates in the context of best arm(s) identification and we believe that Lemma 6.1 can be adapted to deal with more general $K$-armed bandit scenarios.

These results suggest three practical implications for A/B testing. First, for Binary and Gaussian-like responses with matched variances it is reasonable to consider only tests—i.e., strategies using uniform sampling—rather than general sequential sampling strategies. Second, using a sequential stopping rule in this context is mostly of interest because it does not requires prior knowledge of the complexity of the problem. It should however not be expected to reduce the (average) running time of the experiment for a given probability of error. This leads to the third message regarding the utmost importance of using proper (i.e., provably $\delta$-PAC but not too conservative) exploration rates when using a sequential stopping rule.

We thank Sébastien Bubeck for fruitful discussions during the visit of the first author at Princeton University. This work was supported by the ANR-2010-COSI-002 grant of the French National Research Agency.

References

Appendix A Proof of Lemma 6.1: Changes of Distributions

Under the identifiability assumption, there exists a common measure $\lambda$ such that for all $\nu=(\nu_{1},\nu_{2})$, for all $a\in\{1,2\}$ $\nu_{a}$ has a density $f_{a}$ with respect to $\lambda$.

Let $\nu\in\mathcal{M}$ be a bandit model, and consider an alternative bandit model $\nu^{\prime}\in\mathcal{M}$. $f_{a},f_{a}^{\prime}$ are the densities of $\nu_{a},\nu_{a}^{\prime}$ respectively and 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 $A\in\mathcal{F}_{\sigma}$ (i.e. $A$ such that $A\cap(\sigma=t)\in\mathcal{F}_{t}$),