Learning to Optimize Via Posterior Sampling

Abstract

This paper considers the use of a simple posterior sampling algorithm to balance between exploration and exploitation when learning to optimize actions such as in multi-armed bandit problems. The algorithm, also known as Thompson Sampling, offers significant advantages over the popular upper confidence bound (UCB) approach, and can be applied to problems with finite or infinite action spaces and complicated relationships among action rewards. We make two theoretical contributions. The first establishes a connection between posterior sampling and UCB algorithms. This result lets us convert regret bounds developed for UCB algorithms into Bayesian regret bounds for posterior sampling. Our second theoretical contribution is a Bayesian regret bound for posterior sampling that applies broadly and can be specialized to many model classes. This bound depends on a new notion we refer to as the eluder dimension, which measures the degree of dependence among action rewards. Compared to UCB algorithm Bayesian regret bounds for specific model classes, our general bound matches the best available for linear models and is stronger than the best available for generalized linear models. Further, our analysis provides insight into performance advantages of posterior sampling, which are highlighted through simulation results that demonstrate performance surpassing recently proposed UCB algorithms.

References in corpus (7)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Further Optimal Regret Bounds for Thompson Sampling
• Stochastic simultaneous optimistic optimization
• Multi-Armed Bandits in Metric Spaces
• Thompson Sampling: An Asymptotically Optimal Finite Time Analysis
• Generalized Thompson Sampling for Contextual Bandits
• Thompson Sampling for Complex Bandit Problems

Cited by in corpus (10)

• Thompson Sampling for Contextual Bandits with Linear Payoffs
• (More) Efficient Reinforcement Learning via Posterior Sampling
• An Information-Theoretic Analysis of Thompson Sampling
• Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
• Model-based Reinforcement Learning and the Eluder Dimension
• Latent Bandits Revisited
• Exploiting correlation and budget constraints in Bayesian multi-armed bandit optimization
• Thompson Sampling with a Mixture Prior
• Non-Stationary Latent Bandits
• Exploiting Structure of Uncertainty for Efficient Matroid Semi-Bandits