Ensemble Sampling
This work addresses the bottleneck of computational tractability in online decision problems for practitioners using complex models, representing an incremental improvement.
The paper tackled the problem of making Thompson sampling tractable for complex models like neural networks by developing ensemble sampling, which approximates Thompson sampling and expands its application range, supported by theoretical and computational results.
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.