Thompson Sampling (RecSys)
A recommender that always shows whatever currently looks best never finds out that something else was better. Thompson sampling fixes that by letting chance do the exploring, in proportion to how uncertain the system actually is.
Sampling from belief, not from a score
Each candidate carries a distribution over its reward rather than a single estimate — for click-or-no-click, a Beta distribution updated by the successes and failures seen so far. At request time the policy draws one sample from each candidate's distribution and shows the item whose sample came out highest. An item with many impressions has a tight distribution and samples near its true rate; a fresh item has a wide one and occasionally wins outright. Exploration is therefore not a tunable extra — it falls out of the posterior's width and shrinks on its own as evidence arrives.
Why it suits recommendation
It survives the two conditions that strain UCB-style optimism in production: feedback is delayed and batched, and thousands of requests are served between model updates. Because the policy is randomised, identical requests get different slates and the logs retain each action's propensity — exactly what inverse propensity scoring and off-policy evaluation need to reuse that traffic later. It is the standard first answer to new-item cold start on a live surface.
What goes wrong
The posterior is only as honest as the reward model behind it. A mis-specified prior over-explores a catalogue of millions, and non-stationary demand needs discounting or the policy stays convinced of last month's winners.
Thompson sampling keeps a posterior distribution over each candidate's reward — a Beta distribution for click data — draws one sample per candidate at request time, and shows whichever sample is highest. Uncertain items win occasionally, so exploration is governed by the posterior's width rather than a tuned parameter. It tolerates delayed, batched feedback, and because the policy is randomised it logs the propensities that off-policy evaluation later requires.
Suppose you have five slot machines and no idea which pays out best. One approach: write down your honest hunch about each one as a range rather than a number — “somewhere between poor and excellent” for the ones you have barely tried. Then pick a number at random from each range and play whichever came out highest.
Thompson sampling is that trick, used to decide what to recommend. Things the software is unsure about get shown now and then, simply because their range is wide enough to win the draw. The more it learns about something, the narrower the range, and the less it gambles. That is how a brand-new item ever gets a chance.