Indexed Minimum Empirical Divergence for Unimodal Bandits
This work addresses a specific domain problem in bandit optimization for researchers, but it is incremental as it adapts an existing algorithm to a new structure.
The paper tackles the problem of multi-armed bandits with unimodal exponential distributions by introducing the IMED-UB algorithm, which adapts an existing method to exploit the unimodal structure and achieves competitive performance with state-of-the-art algorithms in numerical experiments.
We consider a multi-armed bandit problem specified by a set of one-dimensional family exponential distributions endowed with a unimodal structure. We introduce IMED-UB, a algorithm that optimally exploits 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 IMED-UB algorithm. Numerical experiments show that IMED-UB competes with the state-of-the-art algorithms.