Timezone: »

Indexed Minimum Empirical Divergence for Unimodal Bandits
Hassan SABER · Pierre Ménard · Odalric-Ambrym Maillard

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @ None #None

We consider a stochastic multi-armed bandit problem specified by a set of one-dimensional family exponential distributions endowed with a unimodal structure. The unimodal structure is of practical relevance for several applications. We introduce IMED-UB, an algorithm that exploits provably optimally the unimodal-structure, by adapting to this setting the Indexed Minimum Empirical Divergence (IMED) algorithm introduced by Honda and Takemura (2015). Owing to our proof technique, we are able to provide a concise finite-time analysis of the IMED-UB algorithm, that is simple and yet yields asymptotic optimality. We finally provide numerical experiments showing that IMED-UB competes favorably with the recently introduced state-of-the-art algorithms.

Author Information

Hassan SABER (Inria Lille - Nord Europe)
Pierre Ménard (Magdeburg University)
Odalric-Ambrym Maillard (INRIA Lille Nord Europe)

More from the Same Authors