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 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.
