Timezone: »

 
Poster
Thompson Sampling and Approximate Inference
My Phan · Yasin Abbasi Yadkori · Justin Domke

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #45
in Algorithms -- Bandit Algorithms »
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.
Keywords: Bandit Algorithms · Variational Inference · Algorithms · Probabilistic Methods -> MCMC; Probabilistic Methods
[ Paper]  [ Poster] 

Author Information

My Phan (University of Massachusetts Amherst)
Yasin Abbasi Yadkori (VinAI Research/ VinTech JSC.,)
Justin Domke (University of Massachusetts, Amherst)

More from the Same Authors