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

Derive the Beta posterior: prior $\text{Beta}(\alpha, \beta)$ + Bernoulli observations → $\text{Beta}(\alpha + w, \beta + l)$?

Numerical: prior $\text{Beta}(1,1)$; arm1 has 8 wins/2 losses, arm2 3 wins/7 losses — write both posteriors and argue which arm the next sample favors.

TS vs UCB regret: why does TS often perform better in practice?

How does TS degrade under non-stationary rewards, and what fixes exist?

The probability-matching property: play probability equals posterior probability of optimality — what does it imply for exploration?