How does Thompson sampling work?

medium

Answer

$For each arm, maintain posterior over its reward.$
${\theta}_{j}$
$Randomness is 'baked in' via sampling \to automatic exploration-exploitation tradeoff.$
$Optimal frequentist regret bounds (Bayesian and worst-case).$
$Standard in online experimentation, recommender systems, contextual bandits.$
$Bayes / Beta-Bernoulli conjugate makes update O(1) per pull.$

Check yourself — multiple choice

Random
Draw ${\theta}_{j}$ from each arm's posterior, pick argmax; automatic exploration/exploitation; optimal regret bounds; standard in bandits / online experimentation
Same as UCB
Not real

Thompson sampling: sample from posterior, pick argmax; optimal regret.

#bayesian#estimation

215 interview questions in this topic.