Bootstrapped Thompson Sampling and Deep Exploration

By Ian Osband, Benjamin Van Roy. 2015

114 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Deep Exploration via Bootstrapped DQN (2016, background): “In general it may be necessary to maintain some more rigorous notion of “prior”, potentially through the use of artiﬁcial prior data to maintain diversity [15].”
Randomized Prior Functions for Deep Reinforcement Learning (2018, neutral): “Gaussian noise or bootstrap sampling [50]).”
Bao: Making Learned Query Optimization Practical (2020, methodology): “date beliefs given experience [12,25, 62]. We use an alternative setup which lets us get the benets of Thompson sampling without explicitly dening how to update the posterior belief, as described in [51]. Thompson sampling has also been applied to cloud workload management [40] and SLA conformance [”
Automatic Bridge Bidding Using Deep Reinforcement Learning (2016, background): “Previous research on exploration in reinforcement learning proposes the use of a sampling technique such as “Thompson sampling” to enhance the exploration performance [18], [19].”
Risk versus Uncertainty in Deep Learning: Bayes, Bootstrap and the Dangers of Dropout (2016, methodology): “For certain choices of sampling/perturbations this process is precisely equivalent to Bayesian inference [25, 23].”
A Contextual Bandit Bake-off (2018, unknown): “Our evaluation considers online implementations of Bootstrap Thompson sampling (Agar-wal et al., 2014; Eckles and Kaptein, 2014; Osband and Van Roy, 2015), the Cover approach of Agarwal et al. (2014), (cid:15) -greedy (Langford and Zhang, 2008), RegCB (Foster et al., 2018, which includes LinUCB as…”