From the archives

On the Complexity of A/B Testing

Historical material. Affiliations, schedules and roles on this page describe their original context.

ConferenceName:  Conference On Learning Theory

url:  2014 Conference on Learning Theory

Edition Number:  27

Date:  June, 2014

Place:  Barcelona, Spain

PageStart:  461

PageEnd:  481

Authors:  Emilie KaufmannOlivier CappéAurélien Garivier

Abstract: 

A/B testing refers to the task of determining the best option among two alternatives that yield random outcomes. We provide distribution-dependent lower bounds for the performance of A/B testing that improve over the results currently available both in the fixed-confidence (or delta-PAC) and fixed-budget settings. When the distribution of the outcomes are Gaussian, we prove that the complexity of the fixed-confidence and fixed-budget settings are equivalent, and that uniform sampling of both alternatives is optimal only in the case of equal variances. In the common variance case, we also provide a stopping rule that terminates faster than existing fixed-confidence algorithms. In the case of Bernoulli distributions, we show that the complexity of fixed-budget setting is smaller than that of fixed-confidence setting and that uniform sampling of both alternatives - though not optimal - is advisable in practice when combined with an appropriate stopping criterion.

Direct link:  free access on JMLR W&CP 35

Arxiv Number:  1405.3224

Hal Number:  00990254

Keywords: