Skip to Main content Skip to Navigation
Conference papers

Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits

Reda Ouhamma 1, 2, 3 Rémy Degenne 1, 2, 3 Pierre Gaillard 4 Vianney Perchet 5 
3 Scool - Scool
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
4 Thoth - Apprentissage de modèles à partir de données massives
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann
Abstract : In the fixed budget thresholding bandit problem, an algorithm sequentially allocates a budgeted number of samples to different distributions. It then predicts whether the mean of each distribution is larger or lower than a given threshold. We introduce a large family of algorithms (containing most existing relevant ones), inspired by the Frank-Wolfe algorithm, and provide a thorough yet generic analysis of their performance. This allowed us to construct new explicit algorithms, for a broad class of problems, whose losses are within a small constant factor of the non-adaptive oracle ones. Quite interestingly, we observed that adaptive methods empirically greatly out-perform non-adaptive oracles, an uncommon behavior in standard online learning settings, such as regret minimization. We explain this surprising phenomenon on an insightful toy problem.
Document type :
Conference papers
Complete list of metadata
Contributor : reda ouhamma Connect in order to contact the contributor
Submitted on : Monday, October 4, 2021 - 1:39:48 PM
Last modification on : Wednesday, September 7, 2022 - 8:14:05 AM
Long-term archiving on: : Wednesday, January 5, 2022 - 6:06:36 PM


Files produced by the author(s)


  • HAL Id : hal-03363014, version 1


Reda Ouhamma, Rémy Degenne, Pierre Gaillard, Vianney Perchet. Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits. NeurIPS 2021 - 35th International Conference on Neural Information Processing Systems, Dec 2021, Virtual, Canada. pp.1-25. ⟨hal-03363014⟩



Record views


Files downloads