Thompson Sampling and Approximate Inference
We study the effects of approximate inference on the performance of Thompson sampling in the $k$-armed bandit problems. Thompson sampling is a successful algorithm for online decision-making but requires posterior inference, which often must be approximated in practice. We show that even small constant inference error (in $\alpha$-divergence) can lead to poor performance (linear regret) due to under-exploration (for $\alpha<1$) or over-exploration (for $\alpha>0$) by the approximation. While for $\alpha > 0$ this is unavoidable, for $\alpha \leq 0$ the regret can be improved by adding a small amount of forced exploration even when the inference error is a large constant.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingThompson SamplingSimilar Papers 제목 키워드 기반
Thompson Sampling with Approximate Inference
We study the effects of approximate inference on the performance of Thompson sampling in the $k$-armed bandit problems. Thompson sampling is a successful algorithm for online decision-making but requires posterior infere…
Decision MakingThompson SamplingVITS : 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 i…
Multi-Armed BanditsThompson SamplingVariational InferenceThompson 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+1Thompson 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 PredictionDeep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling
Recent advances in deep reinforcement learning have made significant strides in performance on applications such as Go and Atari games. However, developing practical methods to balance exploration and exploitation in com…
Decision MakingDeep Reinforcement LearningMulti-Armed Banditsreinforcement-learning+4