Bayesian Online Model Selection
This addresses the exploration challenge in Bayesian bandits for researchers and practitioners, though it is incremental as it builds on existing model selection frameworks.
The paper tackles the problem of online model selection in Bayesian bandits by introducing a new algorithm that adaptively explores multiple bandit learners to compete with the best one in hindsight, achieving a Bayesian regret bound of O(d*M√T + √(MT)) and demonstrating competitive empirical performance.
Online model selection in Bayesian bandits raises a fundamental exploration challenge: When an environment instance is sampled from a prior distribution, how can we design an adaptive strategy that explores multiple bandit learners and competes with the best one in hindsight? We address this problem by introducing a new Bayesian algorithm for online model selection in stochastic bandits. We prove an oracle-style guarantee of $O\left( d^* M \sqrt{T} + \sqrt{(MT)} \right)$ on the Bayesian regret, where $M$ is the number of base learners, $d^*$ is the regret coefficient of the optimal base learner, and $T$ is the time horizon. We also validate our method empirically across a range of stochastic bandit settings, demonstrating performance that is competitive with the best base learner. Additionally, we study the effect of sharing data among base learners and its role in mitigating prior mis-specification.