Scalable Thompson Sampling via Optimal Transport
This work addresses the scalability problem for practitioners using Thompson sampling in sequential decision-making with complex models, though it appears incremental as it builds on existing distribution optimization methods.
The paper tackles the intractability of exact posterior distributions in Thompson sampling for complex models like neural networks by using distribution optimization techniques and Wasserstein gradient flows to approximate the posterior efficiently, resulting in superior performance demonstrated through extensive experiments on synthetic and large-scale real data.
Thompson sampling (TS) is a class of algorithms for sequential decision-making, which requires maintaining a posterior distribution over a model. However, calculating exact posterior distributions is intractable for all but the simplest models. Consequently, efficient computation of an approximate posterior distribution is a crucial problem for scalable TS with complex models, such as neural networks. In this paper, we use distribution optimization techniques to approximate the posterior distribution, solved via Wasserstein gradient flows. Based on the framework, a principled particle-optimization algorithm is developed for TS to approximate the posterior efficiently. Our approach is scalable and does not make explicit distribution assumptions on posterior approximations. Extensive experiments on both synthetic data and real large-scale data demonstrate the superior performance of the proposed methods.