Skip to yearly menu bar Skip to main content


Fast Asymptotically Optimal Algorithms for Non-Parametric Stochastic Bandits

Dorian Baudry · Fabien Pesquerel · Rémy Degenne · Odalric-Ambrym Maillard

Great Hall & Hall B1+B2 (level 1) #1815
[ ]
[ Paper [ Poster [ OpenReview
Tue 12 Dec 8:45 a.m. PST — 10:45 a.m. PST


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.

Chat is not available.