2022/03/21 by Dorian Baudry, Baudry, Dorian, Yoan Russac +3 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Algorithm #Commit #Computer science #Econometrics #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Mathematical optimization #Mathematics #Maxima #Quantile #Reduction (mathematics) #Simplicity #cs.LG
paper · pdf · doi:10.48550/arxiv.2203.10883
published in arXiv (Cornell University) (Cornell University) · Proceedings of the 25 th International Conference on Artificial Intelligence and Statistics (AISTATS) 2022
arxiv created 2022/03/21 · openalex publication_date 2022/03/21 · arxiv updated 2022/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this paper, we contribute to the Extreme Bandit 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 aspects (1) they lead to better empirical performance (2) they enjoy a significant reduction of the memory and time complexities.