On the Complexity of A/B Testing

Emilie Kaufmann, Olivier Cappé, Aurélien Garivier
Proceedings of The 27th Conference on Learning Theory, PMLR 35:461-481, 2014.

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 δ-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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-kaufmann14, title = {On the Complexity of A/B Testing}, author = {Kaufmann, Emilie and Cappé, Olivier and Garivier, Aurélien}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {461--481}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/kaufmann14.pdf}, url = {https://proceedings.mlr.press/v35/kaufmann14.html}, 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 δ-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.} }
Endnote
%0 Conference Paper %T On the Complexity of A/B Testing %A Emilie Kaufmann %A Olivier Cappé %A Aurélien Garivier %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-kaufmann14 %I PMLR %P 461--481 %U https://proceedings.mlr.press/v35/kaufmann14.html %V 35 %X 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 δ-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.
RIS
TY - CPAPER TI - On the Complexity of A/B Testing AU - Emilie Kaufmann AU - Olivier Cappé AU - Aurélien Garivier BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-kaufmann14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 461 EP - 481 L1 - http://proceedings.mlr.press/v35/kaufmann14.pdf UR - https://proceedings.mlr.press/v35/kaufmann14.html AB - 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 δ-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. ER -
APA
Kaufmann, E., Cappé, O. & Garivier, A.. (2014). On the Complexity of A/B Testing. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:461-481 Available from https://proceedings.mlr.press/v35/kaufmann14.html.

Related Material