VITS : Variational Inference Thompson Sampling for contextual bandits
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.
Code (1)
Tasks
Multi-Armed BanditsThompson SamplingVariational InferenceMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits
We consider the stochastic linear contextual bandit problem with high-dimensional features. We analyze the Thompson sampling algorithm using special classes of sparsity-inducing priors (e.g., spike-and-slab) to model the…
Multi-Armed BanditsThompson SamplingVariational InferenceVocal Bursts Intensity PredictionThompson Sampling via Local Uncertainty
Thompson sampling is an efficient algorithm for sequential decision making, which exploits the posterior uncertainty to address the exploration-exploitation dilemma. There has been significant recent interest in integrat…
Decision MakingMulti-Armed BanditsSequential Decision MakingThompson Sampling+1Variational inference for the multi-armed contextual bandit
In many biomedical, science, and engineering problems, one must sequentially decide which action to take next so as to maximize rewards. One general class of algorithms for optimizing interactions with the world, while s…
Multi-Armed BanditsReinforcement LearningThompson SamplingVariational InferencePG-TS: Improved Thompson Sampling for Logistic Contextual Bandits
We address the problem of regret minimization in logistic contextual bandits, where a learner decides among sequential actions or arms given their respective contexts to maximize binary rewards. Using a fast inference pr…
Multi-Armed BanditsThompson SamplingFeel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning
Thompson Sampling has been widely used for contextual bandit problems due to the flexibility of its modeling power. However, a general theory for this class of methods in the frequentist setting is still lacking. In this…
Multi-Armed Banditsregressionreinforcement-learningReinforcement Learning+2