Bootstrapped Thompson Sampling and Deep Exploration

Abstract

This technical note presents a new approach to carrying out the kind of exploration achieved by Thompson sampling, but without explicitly maintaining or sampling from posterior distributions. The approach is based on a bootstrap technique that uses a combination of observed and artificially generated data. The latter serves to induce a prior distribution which, as we will demonstrate, is critical to effective exploration. We explain how the approach can be applied to multi-armed bandit and reinforcement learning problems and how it relates to Thompson sampling. The approach is particularly well-suited for contexts in which exploration is coupled with deep learning, since in these settings, maintaining or generating samples from a posterior distribution becomes computationally infeasible.

References in corpus (4)

• Further Optimal Regret Bounds for Thompson Sampling
• Generalization and Exploration via Randomized Value Functions
• Model-based Reinforcement Learning and the Eluder Dimension
• Thompson sampling with the online bootstrap

Cited by in corpus (27)

• Deep Exploration via Bootstrapped DQN
• Bao: Learning to Steer Query Optimizers
• Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain
• Generalization and Exploration via Randomized Value Functions
• A Contextual Bandit Bake-off
• Neural Thompson Sampling
• A Practical Method for Solving Contextual Bandit Problems Using Decision Trees
• Thompson Sampling for Dynamic Pricing
• Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
• New Insights into Bootstrapping for Bandits
• Exploration by Distributional Reinforcement Learning
• PG-TS: Improved Thompson Sampling for Logistic Contextual Bandits
• Variational Deep Q Network
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime
• Perturbed-History Exploration in Stochastic Linear Bandits
• Risk Aware and Multi-Objective Decision Making with Distributional Monte Carlo Tree Search
• Residual Bootstrap Exploration for Bandit Algorithms
• Differentiable Linear Bandit Algorithm
• Old Dog Learns New Tricks: Randomized UCB for Bandit Problems
• Improving the Diversity of Bootstrapped DQN by Replacing Priors With Noise
• Epistemic Neural Networks
• Debiasing Samples from Online Learning Using Bootstrap
• State-Aware Variational Thompson Sampling for Deep Q-Networks
• CORe: Capitalizing On Rewards in Bandit Exploration
• Angrier Birds: Bayesian reinforcement learning
• Interpretable Few-Shot Learning via Linear Distillation
• Knowledge is reward: Learning optimal exploration by predictive reward cashing