From the archives

On Bayesian Upper Confidence Bounds for Bandit Problems

Historical material. Affiliations, schedules and roles on this page describe their original context.

ConferenceName:  International Conference on Artificial Intelligence and Statistics

url:  Fifteenth International Conference on Artificial Intelligence and Statistics

Edition Number:  15

Date:  April, 2012

Place:  La Palma, Canary Islands

PageStart:  592

PageEnd:  600

Authors:  Emilie KaufmannOlivier CappéAurélien Garivier

Abstract: 

Stochastic bandit problems have been analyzed from two different perspectives: a frequentist view, where the parameter is a deterministic unknown quantity, and a Bayesian approach, where the parameter is drawn from a prior distribution. We show in this paper that methods derived from this second perspective prove optimal when evaluated using the frequentist cumulated regret as a measure of performance. We give a general formulation for a class of Bayesian index policies that rely on quantiles of the posterior distribution. For binary bandits, we prove that the corresponding algorithm, termed Bayes-UCB, satisfies finite-time regret bounds that imply its asymptotic optimality. More generally, Bayes-UCB appears as an unifying framework for several variants of the UCB algorithm addressing different bandit problems (parametric multi-armed bandits, Gaussian bandits with unknown mean and variance, linear bandits). But the generality of the Bayesian approach makes it possible to address more challenging models. In particular, we show how to handle linear bandits with sparsity constraints by resorting to Gibbs sampling.

Direct link:  workshop proceedings available online

Keywords: