Timezone: »

 
Spotlight
Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits
Reda Ouhamma · Odalric-Ambrym Maillard · Vianney Perchet

@

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 methodsempirically 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.

Author Information

Reda Ouhamma (Université de Lille)
Odalric-Ambrym Maillard (INRIA Lille Nord Europe)
Vianney Perchet (ENSAE & Criteo AI Lab)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors