On Bayesian Upper Confidence Bounds for Bandit Problems

Emilie Kaufmann, Olivier Cappé, Aurélien GarivierAISTATS 2012 · OpenReview

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 a random variable. This paper introduces Bayes-UCB, an algorithm that bridges these perspectives by using posterior quantiles as confidence indices. We demonstrate that Bayes-UCB achieves theoretical optimality and superior empirical performance across various bandit scenarios, including complex sparse linear models.

Introduction

The multi-armed bandit (MAB) problem is a fundamental framework for decision-making under uncertainty, requiring a balance between exploration and exploitation. Traditionally, the field has been divided into frequentist and Bayesian approaches. Frequentists aim to minimize regret relative to fixed but unknown parameters using algorithms like Upper Confidence Bound (UCB). Bayesians optimize average performance over a prior distribution, often leading to complex solutions like Gittins indices.

This paper asks whether one can utilize Bayesian posterior distributions to construct a simple, UCB-like algorithm that satisfies frequentist optimality. The resulting algorithm, Bayes-UCB, maintains the computational simplicity of UCB while leveraging the refined uncertainty estimation of Bayesian updates.

The Bayes-UCB Algorithm

Bayes-UCB operates by maintaining a posterior distribution for each arm's mean reward. At each time step $t$, the algorithm:

  1. Calculates a quantile $q_j(t)$ of the current posterior distribution for each arm $j$.
  2. Sets the quantile level to $1 - \alpha_t$, where $\alpha_t \approx 1/t$. This ensures that as data accumulates, the algorithm explores the extreme right tail of the posterior.
  3. Selects the arm with the highest quantile.

This framework is highly adaptable. For Bernoulli rewards, it utilizes Beta distributions; for Gaussian rewards with unknown parameters, it employs Student-t distributions. In high-dimensional settings like linear bandits, it uses multivariate Gaussians or sparsity-inducing priors.

Empirical Evaluation

The authors evaluate Bayes-UCB using synthetic simulations common in the MAB literature. In two-armed Bernoulli bandit scenarios, Bayes-UCB consistently matches or exceeds the performance of state-of-the-art frequentist algorithms like KL-UCB and significantly outperforms standard UCB variants.

Regret comparison for Bernoulli bandits. Bayes-UCB shows competitive performance against KL-UCB and outperforms standard UCB.

Leveraging Structural Information: Sparse Linear Bandits

A key advantage of Bayes-UCB is its ability to incorporate structural knowledge through the choice of prior. In sparse linear bandits, where only a subset of features is relevant to the reward, frequentist UCB methods often struggle to exploit this sparsity effectively. Bayes-UCB naturally addresses this by employing a "spike-and-slab" prior. While calculating quantiles in this setting requires Markov Chain Monte Carlo (MCMC) methods like Gibbs sampling, the empirical gains are substantial.

Regret in sparse linear bandits. Using a sparse 'spike-and-slab' prior allows Bayes-UCB to significantly outperform standard Gaussian priors by leveraging structural information.

Key Insights and Results

  • The "Magic" Quantile: Setting the quantile level to $1 - 1/t$ is critical for matching asymptotic frequentist regret lower bounds.
  • Unifying Framework: Bayes-UCB serves as a template; by varying the prior, one can recover or improve upon several specialized UCB variants.
  • Asymptotic Optimality: The paper provides a finite-time analysis for Bernoulli rewards, proving that Bayes-UCB reaches the theoretical lower bound for regret established by Lai and Robbins.

Conclusion

Bayes-UCB provides a powerful bridge between Bayesian and frequentist bandit analysis. It offers the refined uncertainty modeling of Bayesian methods with the rigorous regret guarantees of frequentist algorithms. While computational complexity can increase for non-conjugate models, its ability to effectively leverage structural information like sparsity makes it a versatile tool for modern machine learning applications. Future work includes extending formal optimality proofs to the general exponential family and exploring the impact of prior misspecification.

Summary updated

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 parame...
BibTeX
@inproceedings{kaufmann2012bayesian,
  author = {Emilie Kaufmann and Olivier Cappé and Aurélien Garivier},
  title = {{On Bayesian Upper Confidence Bounds for Bandit Problems}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=6a4cpAHnvU},
}
Figure