Timezone: »

 
Poster
Fast Asymptotically Optimal Algorithms for Non-Parametric Stochastic Bandits
Dorian Baudry · Fabien Pesquerel · Rémy Degenne · Odalric-Ambrym Maillard

Tue Dec 12 08:45 AM -- 10:45 AM (PST) @ Great Hall & Hall B1+B2 #1815
in Poster Session 1 »

We consider the problem of regret minimization in non-parametric stochastic bandits. When the rewards are known to be bounded from above, there exists asymptotically optimal algorithms, with asymptotic regret depending on an infimum of Kullback-Leibler divergences (KL). These algorithms are computationally expensive and require storing all past rewards, thus simpler but non-optimal algorithms are often used instead. We introduce several methods to approximate the infimum KL which reduce drastically the computational and memory costs of existing optimal algorithms, while keeping their regret guaranties. We apply our findings to design new variants of the MED and IMED algorithms, and demonstrate their interest with extensive numerical simulations.

Author Information

Dorian Baudry (Ecole Polytechnique)
Fabien Pesquerel (INRIA)
Rémy Degenne (Inria)
Odalric-Ambrym Maillard (INRIA Lille Nord Europe)

More from the Same Authors