Langevin Monte Carlo for Contextual Bandits
We study the efficiency of Thompson sampling for contextual bandits. Existing
Thompson sampling-based algorithms need to construct a Laplace approximation
(i.e., a Gaussian distribution) of the posterior distribution, which is
inefficient to sample in high dimensional applications for general covariance
matrices. Moreover, the Gaussian approximation may not be a good surrogate for
the posterior distribution for general reward generating functions. We propose
an efficient posterior sampling algorithm, viz., Langevin Monte Carlo Thompson
Sampling (LMC-TS), that uses Markov Chain Monte Carlo (MCMC) methods to
directly sample from the posterior distribution in contextual bandits. Our
method is computationally efficient since it only needs to perform noisy
gradient descent updates without constructing the Laplace approximation of the
posterior distribution. We prove that the proposed algorithm achieves the same
sublinear regret bound as the best Thompson sampling algorithms for a special
case of contextual bandits, viz., linear contextual bandits. We conduct
experiments on both synthetic data and real-world datasets on different
contextual bandit models, which demonstrates that directly sampling from the
posterior is both computationally efficient and competitive in performance.