Poster
Thompson Sampling and Approximate Inference
My Phan · Yasin Abbasi Yadkori · Justin Domke
East Exhibition Hall B, C #45
Keywords: [ Bandit Algorithms ] [ Algorithms ] [ Variational Inference ] [ Probabilistic Methods -> MCMC; Probabilistic Methods ]
[
Abstract
]
Abstract:
We study the effects of approximate inference on the performance of Thompson sampling in the -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 -divergence) can lead to poor performance (linear regret) due to under-exploration (for ) or over-exploration (for ) by the approximation. While for this is unavoidable, for the regret can be improved by adding a small amount of forced exploration even when the inference error is a large constant.
Live content is unavailable. Log in and register to view live content