Indexed Minimum Empirical Divergence for Unimodal Bandits
arXiv:2112.01452
Abstract
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.
arXiv commentNeurIPS 2021 - International Conference on Neural Information Processing Systems, Dec 2021, Virtual-only Conference, United States. arXiv admin note: substantial text overlap with arXiv:2006.16569, arXiv:2007.03224
References in corpus (5)
- Minimal Exploration in Structured Stochastic Bandits
- Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
- Streaming kernel regression with provably adaptive mean, variance, and regularization
- Structure Adaptive Algorithms for Stochastic Bandits
- Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling