Efficient Algorithms for Extreme Bandits

Dorian Baudry, Yoan Russac, Emilie Kaufmann
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:2210-2248, 2022.

Abstract

In this paper, we contribute to the Extreme Bandits problem, a variant of Multi-Armed Bandits in which the learner seeks to collect the largest possible reward. We first study the concentration of the maximum of i.i.d random variables under mild assumptions on the tail of the rewards distributions. This analysis motivates the introduction of Quantile of Maxima (QoMax). The properties of QoMax are sufficient to build an Explore-Then-Commit (ETC) strategy, QoMax-ETC, achieving strong asymptotic guarantees despite its simplicity. We then propose and analyze a more adaptive, anytime algorithm, QoMax-SDA, which combines QoMax with a subsampling method recently introduced by Baudry et al. (2021). Both algorithms are more efficient than existing approaches in two senses: (1) they lead to better empirical performance (2) they enjoy a significant reduction of the storage and computational cost.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-baudry22a, title = { Efficient Algorithms for Extreme Bandits }, author = {Baudry, Dorian and Russac, Yoan and Kaufmann, Emilie}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {2210--2248}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/baudry22a/baudry22a.pdf}, url = {https://proceedings.mlr.press/v151/baudry22a.html}, abstract = { In this paper, we contribute to the Extreme Bandits problem, a variant of Multi-Armed Bandits in which the learner seeks to collect the largest possible reward. We first study the concentration of the maximum of i.i.d random variables under mild assumptions on the tail of the rewards distributions. This analysis motivates the introduction of Quantile of Maxima (QoMax). The properties of QoMax are sufficient to build an Explore-Then-Commit (ETC) strategy, QoMax-ETC, achieving strong asymptotic guarantees despite its simplicity. We then propose and analyze a more adaptive, anytime algorithm, QoMax-SDA, which combines QoMax with a subsampling method recently introduced by Baudry et al. (2021). Both algorithms are more efficient than existing approaches in two senses: (1) they lead to better empirical performance (2) they enjoy a significant reduction of the storage and computational cost. } }
Endnote
%0 Conference Paper %T Efficient Algorithms for Extreme Bandits %A Dorian Baudry %A Yoan Russac %A Emilie Kaufmann %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-baudry22a %I PMLR %P 2210--2248 %U https://proceedings.mlr.press/v151/baudry22a.html %V 151 %X In this paper, we contribute to the Extreme Bandits problem, a variant of Multi-Armed Bandits in which the learner seeks to collect the largest possible reward. We first study the concentration of the maximum of i.i.d random variables under mild assumptions on the tail of the rewards distributions. This analysis motivates the introduction of Quantile of Maxima (QoMax). The properties of QoMax are sufficient to build an Explore-Then-Commit (ETC) strategy, QoMax-ETC, achieving strong asymptotic guarantees despite its simplicity. We then propose and analyze a more adaptive, anytime algorithm, QoMax-SDA, which combines QoMax with a subsampling method recently introduced by Baudry et al. (2021). Both algorithms are more efficient than existing approaches in two senses: (1) they lead to better empirical performance (2) they enjoy a significant reduction of the storage and computational cost.
APA
Baudry, D., Russac, Y. & Kaufmann, E.. (2022). Efficient Algorithms for Extreme Bandits . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:2210-2248 Available from https://proceedings.mlr.press/v151/baudry22a.html.

Related Material