On Bayesian index policies for sequential resource allocation
The Annals of Statistics · 2018 · Volume 46 · Issue 2
Abstract
This paper is about index policies for minimizing (frequentist) regret in a stochastic multi-armed bandit model, inspired by a Bayesian view on the problem. Our main contribution is to prove that the Bayes-UCB algorithm, which relies on quantiles of posterior distributions, is asymptotically optimal when the reward distributions belong to a one-dimensional exponential family, for a large class of prior distributions. We also show that the Bayesian literature gives new insight on what kind of exploration rates could be used in frequentist, UCB-type algorithms. Indeed, approximations of the Bayesian optimal solution or the Finite-Horizon Gittins indices provide a justification for the kl-UCB$^{+}$ and kl-UCB-H$^{+}$ algorithms, whose asymptotic optimality is also established.
Keywords
62L05, Bayesian methods, Gittins indices, Multi-armed bandit problems, upper-confidence bounds
Enable JavaScript for citation tools and additional paper interactions.