Timezone: »

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

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
in Poster Session 1 »

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.

Keywords: Bandits · Online Learning

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