Bridging the gap between regret minimization and best arm identification, with application to A/B tests

Rémy Degenne, Thomas Nedelec, Clement Calauzenes, Vianney Perchet
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1988-1996, 2019.

Abstract

State of the art online learning procedures focus either on selecting the best alternative (“best arm identification”) or on minimizing the cost (the “regret”). We merge these two objectives by providing the theoretical analysis of cost minimizing algorithms that are also $\delta$-PAC (with a proven guaranteed bound on the decision time), hence fulfilling at the same time regret minimization and best arm identification. This analysis sheds light on the common observation that ill-callibrated UCB-algorithms minimize regret while still identifying quickly the best arm. We also extend these results to the non-iid case faced by many practitioners. This provides a technique to make cost versus decision time compromise when doing adaptive tests with applications ranging from website A/B testing to clinical trials.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-degenne19a, title = {Bridging the gap between regret minimization and best arm identification, with application to A/B tests}, author = {Degenne, R\'emy and Nedelec, Thomas and Calauzenes, Clement and Perchet, Vianney}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1988--1996}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/degenne19a/degenne19a.pdf}, url = {https://proceedings.mlr.press/v89/degenne19a.html}, abstract = {State of the art online learning procedures focus either on selecting the best alternative (“best arm identification”) or on minimizing the cost (the “regret”). We merge these two objectives by providing the theoretical analysis of cost minimizing algorithms that are also $\delta$-PAC (with a proven guaranteed bound on the decision time), hence fulfilling at the same time regret minimization and best arm identification. This analysis sheds light on the common observation that ill-callibrated UCB-algorithms minimize regret while still identifying quickly the best arm. We also extend these results to the non-iid case faced by many practitioners. This provides a technique to make cost versus decision time compromise when doing adaptive tests with applications ranging from website A/B testing to clinical trials.} }
Endnote
%0 Conference Paper %T Bridging the gap between regret minimization and best arm identification, with application to A/B tests %A Rémy Degenne %A Thomas Nedelec %A Clement Calauzenes %A Vianney Perchet %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-degenne19a %I PMLR %P 1988--1996 %U https://proceedings.mlr.press/v89/degenne19a.html %V 89 %X State of the art online learning procedures focus either on selecting the best alternative (“best arm identification”) or on minimizing the cost (the “regret”). We merge these two objectives by providing the theoretical analysis of cost minimizing algorithms that are also $\delta$-PAC (with a proven guaranteed bound on the decision time), hence fulfilling at the same time regret minimization and best arm identification. This analysis sheds light on the common observation that ill-callibrated UCB-algorithms minimize regret while still identifying quickly the best arm. We also extend these results to the non-iid case faced by many practitioners. This provides a technique to make cost versus decision time compromise when doing adaptive tests with applications ranging from website A/B testing to clinical trials.
APA
Degenne, R., Nedelec, T., Calauzenes, C. & Perchet, V.. (2019). Bridging the gap between regret minimization and best arm identification, with application to A/B tests. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1988-1996 Available from https://proceedings.mlr.press/v89/degenne19a.html.

Related Material