  Thompson sampling has emerged as an effective heuristic for a broad range of
online decision problems. In its basic form, the algorithm requires computing
and sampling from a posterior distribution over models, which is tractable only
for simple special cases. This paper develops ensemble sampling, which aims to
approximate Thompson sampling while maintaining tractability even in the face
of complex models such as neural networks. Ensemble sampling dramatically
expands on the range of applications for which Thompson sampling is viable. We
establish a theoretical basis that supports the approach and present
computational results that offer further insight.
