On the Complexity of A/B Testing - IMT - Institut Mines-Télécom Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

On the Complexity of A/B Testing

Résumé

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.
Fichier principal
Vignette du fichier
kaufmann14.pdf (342.25 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00990254 , version 1 (13-05-2014)
hal-00990254 , version 2 (16-02-2015)

Licence

Paternité

Identifiants

Citer

Emilie Kaufmann, Olivier Cappé, Aurélien Garivier. On the Complexity of A/B Testing. Conference on Learning Theory, Jun 2014, Barcelona, Spain. pp.461-481. ⟨hal-00990254v2⟩
459 Consultations
204 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More