Thompson Sampling

Thompson Sampling (TS, probability matching) is a Bayesian exploration algorithm: maintain a posterior over each arm's mean reward; each round sample $\theta_a \sim \text{Beta}(\alpha_a + w_a, \beta_a + l_a)$ (Beta is the conjugate prior for Bernoulli rewards, $w_a$/$l_a$ being arm $a$'s cumulative wins/losses) and play the arm with the largest sample. It plays each arm with probability equal to its posterior probability of being optimal — wider (more uncertain) posteriors get explored more, yielding a natural exploration-exploitation trade-off.

a default choice for online decisions in industry (ads, recsys, experimentation platforms) for its simplicity, sample efficiency, and empirical edge over UCB; interviews often ask for the Beta posterior update and conjugacy.

UCB's confidence bound is a frequentist construction that underuses priors/reward structure; TS encodes uncertainty directly into selection probabilities via posterior sampling, achieves $O(\ln T)$ regret with strong worst-case guarantees, is more robust to non-stationary rewards, and extends naturally to contextual features (Linear/Logistic TS).

Test Your Knowledge: Practice Questions for "Thompson Sampling"

Single choice pitfall questions with instant feedback and mistake tracking.