Bayesian Online Model Selection

About

Online model selection in Bayesian bandits poses a fundamental challenge of exploration: For an unknown environment instance drawn from the prior distribution, how can we adaptively explore multiple bandit learners, and compete with the best one in terms of performance? We address this problem by introducing a novel Bayesian algorithm for online model selection in stochastic bandits. We establish an oracle-best guarantee of $\widetilde{\mathcal{O}} \left( d^\star M \sqrt{T} + \sqrt{MT} \right)$ on the Bayesian regret, where $M$ is the number of base learners, $d^\star$ is the regret coefficient of the optimal base learner, and $T$ is the time horizon. We further validate our algorithm through experiments across various stochastic bandit settings, demonstrating its performance is competitive with that of the best base learner.