Meta-Thompson Sampling

Abstract

Efficient exploration in bandits is a fundamental online learning problem. We propose a variant of Thompson sampling that learns to explore better as it interacts with bandit instances drawn from an unknown prior. The algorithm meta-learns the prior and thus we call it MetaTS. We propose several efficient implementations of MetaTS and analyze it in Gaussian bandits. Our analysis shows the benefit of meta-learning and is of a broader interest, because we derive a novel prior-dependent Bayes regret bound for Thompson sampling. Our theory is complemented by empirical evaluation, which shows that MetaTS quickly adapts to the unknown prior.

arXiv commentProceedings of the 38th International Conference on Machine Learning

References in corpus (11)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Algorithms for multi-armed bandit problems
• Online Clustering of Bandits
• Sequential Transfer in Multi-armed Bandit with Finite Set of Models
• Meta-learning of Sequential Strategies
• Meta Dynamic Pricing: Transfer Learning Across Experiments
• Information-Theoretic Confidence Bounds for Reinforcement Learning
• Empirical Bayes Regret Minimization
• Policy Gradient Optimization of Thompson Sampling Policies
• Meta-learning with Stochastic Linear Bandits
• Differentiable Linear Bandit Algorithm

Cited by in corpus (4)

• Bayesian decision-making under misspecified priors with applications to meta-learning
• Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models
• Hierarchical Bayesian Bandits
• Metalearning Linear Bandits by Prior Update