Thompson Sampling with Approximate Inference
This addresses a practical issue for practitioners using Thompson sampling in online decision-making, but it is incremental as it builds on known limitations of approximate inference.
The paper tackled the problem of how approximate inference affects Thompson sampling in k-armed bandit problems, showing that small constant inference errors can lead to linear regret due to under- or over-exploration, but for α ≤ 0, adding forced exploration can improve regret even with large errors.
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 $α$-divergence) can lead to poor performance (linear regret) due to under-exploration (for $α<1$) or over-exploration (for $α>0$) by the approximation. While for $α> 0$ this is unavoidable, for $α\leq 0$ the regret can be improved by adding a small amount of forced exploration even when the inference error is a large constant.