Value Directed Exploration in Multi-Armed Bandits with Structured Priors
This work addresses the challenge of balancing exploration and exploitation in multi-armed bandits for researchers and practitioners, offering an incremental improvement over existing methods like UCB and Gittins index.
The paper tackles the problem of achieving practical near-optimal finite-time performance in Bayesian multi-armed bandits by proposing an algorithm that uses value-function-driven online planning with n-step lookahead, resulting in a sub-linear performance guarantee and strong simulation results for problems with structured priors.
Multi-armed bandits are a quintessential machine learning problem requiring the balancing of exploration and exploitation. While there has been progress in developing algorithms with strong theoretical guarantees, there has been less focus on practical near-optimal finite-time performance. In this paper, we propose an algorithm for Bayesian multi-armed bandits that utilizes value-function-driven online planning techniques. Building on previous work on UCB and Gittins index, we introduce linearly-separable value functions that take both the expected return and the benefit of exploration into consideration to perform n-step lookahead. The algorithm enjoys a sub-linear performance guarantee and we present simulation results that confirm its strength in problems with structured priors. The simplicity and generality of our approach makes it a strong candidate for analyzing more complex multi-armed bandit problems.