  In this paper, we introduce and analyze a variant of the Thompson sampling
(TS) algorithm for contextual bandits. At each round, traditional TS requires
samples from the current posterior distribution, which is usually intractable.
To circumvent this issue, approximate inference techniques can be used and
provide samples with distribution close to the posteriors. However, current
approximate techniques yield to either poor estimation (Laplace approximation)
or can be computationally expensive (MCMC methods, Ensemble sampling...). In
this paper, we propose a new algorithm, Varational Inference Thompson sampling
VITS, based on Gaussian Variational Inference. This scheme provides powerful
posterior approximations which are easy to sample from, and is computationally
efficient, making it an ideal choice for TS. In addition, we show that VITS
achieves a sub-linear regret bound of the same order in the dimension and
number of round as traditional TS for linear contextual bandit. Finally, we
demonstrate experimentally the effectiveness of VITS on both synthetic and real
world datasets.

Machine Learning;Machine Learning