Dealing with Unknown Variances in Best-Arm Identification

Marc Jourdan, Degenne Rémy, Kaufmann Emilie
Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:776-849, 2023.

Abstract

The problem of identifying the best arm among a collection of items having Gaussian rewards distribution is well understood when the variances are known. Despite its practical relevance for many applications, few works studied it for unknown variances. In this paper we introduce and analyze two approaches to deal with unknown variances, either by plugging in the empirical variance or by adapting the transportation costs. In order to calibrate our two stopping rules, we derive new time-uniform concentration inequalities, which are of independent interest. Then, we illustrate the theoretical and empirical performances of our two sampling rule wrappers on Track-and-Stop and on a Top Two algorithm. Moreover, by quantifying the impact on the sample complexity of not knowing the variances, we reveal that it is rather small.

Cite this Paper

BibTeX
@InProceedings{pmlr-v201-jourdan23a, title = {Dealing with Unknown Variances in Best-Arm Identification}, author = {Jourdan, Marc and R{\'e}my, Degenne and Emilie, Kaufmann}, booktitle = {Proceedings of The 34th International Conference on Algorithmic Learning Theory}, pages = {776--849}, year = {2023}, editor = {Agrawal, Shipra and Orabona, Francesco}, volume = {201}, series = {Proceedings of Machine Learning Research}, month = {20 Feb--23 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v201/jourdan23a/jourdan23a.pdf}, url = {https://proceedings.mlr.press/v201/jourdan23a.html}, abstract = {The problem of identifying the best arm among a collection of items having Gaussian rewards distribution is well understood when the variances are known. Despite its practical relevance for many applications, few works studied it for unknown variances. In this paper we introduce and analyze two approaches to deal with unknown variances, either by plugging in the empirical variance or by adapting the transportation costs. In order to calibrate our two stopping rules, we derive new time-uniform concentration inequalities, which are of independent interest. Then, we illustrate the theoretical and empirical performances of our two sampling rule wrappers on Track-and-Stop and on a Top Two algorithm. Moreover, by quantifying the impact on the sample complexity of not knowing the variances, we reveal that it is rather small.} }
Endnote
%0 Conference Paper %T Dealing with Unknown Variances in Best-Arm Identification %A Marc Jourdan %A Degenne Rémy %A Kaufmann Emilie %B Proceedings of The 34th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Shipra Agrawal %E Francesco Orabona %F pmlr-v201-jourdan23a %I PMLR %P 776--849 %U https://proceedings.mlr.press/v201/jourdan23a.html %V 201 %X The problem of identifying the best arm among a collection of items having Gaussian rewards distribution is well understood when the variances are known. Despite its practical relevance for many applications, few works studied it for unknown variances. In this paper we introduce and analyze two approaches to deal with unknown variances, either by plugging in the empirical variance or by adapting the transportation costs. In order to calibrate our two stopping rules, we derive new time-uniform concentration inequalities, which are of independent interest. Then, we illustrate the theoretical and empirical performances of our two sampling rule wrappers on Track-and-Stop and on a Top Two algorithm. Moreover, by quantifying the impact on the sample complexity of not knowing the variances, we reveal that it is rather small.
APA
Jourdan, M., Rémy, D. & Emilie, K.. (2023). Dealing with Unknown Variances in Best-Arm Identification. Proceedings of The 34th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 201:776-849 Available from https://proceedings.mlr.press/v201/jourdan23a.html.

Related Material