On Bayesian index policies for sequential resource allocation

2016/01/06 by Emilie Kaufmann, Kaufmann, Emilie · 1 citation
Mathematics · #FOS: Computer and information sciences #Machine Learning (stat.ML) #stat.ML

paper · pdf · doi:10.48550/arxiv.1601.01190

Annals of Statistics, Institute of Mathematical Statistics, A Paraître

arxiv created 2017/11/06 · arxiv updated 2017/11/07

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.

Cited by

• Situational-Constrained Sequential Resources Allocation via Reinforcement Learning

Related

• Online Algorithms for the Multi-Armed Bandit Problem with Markovian Rewards
• Bayesian Design Principles for Frequentist Sequential Learning
• A Note on KL-UCB+ Policy for the Stochastic Bandit
• UCB algorithms for multi-armed bandits: Precise regret and adaptive inference
• Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits