Thompson Sampling

Epsilon-greedy handles exploration with a blunt, fixed rule: some fixed percentage of the time, ignore what you have learned and try something at random. Thompson sampling replaces that blunt rule with something that automatically explores more when you are uncertain and less as you become confident, without any separate exploration-rate knob to hand-tune. It does this by keeping, for each option, not just a single best-guess number for its true value, but an entire probability distribution over what that true value plausibly is — and then choosing which option to try by literally drawing one random sample from each option's distribution and picking whichever sample happens to come out highest.

Why sampling from uncertainty is the trick

An option tried only twice has a wide, spread-out distribution over its plausible true value — it might genuinely be great, or genuinely be bad, and the distribution reflects that honestly. An option tried a thousand times has a narrow, tightly peaked distribution centered on its now well-known true value. When you draw one random sample from each option's distribution, a wide, uncertain distribution has real odds of producing a surprisingly high sample purely by chance, even if its center is currently unimpressive — which is exactly the mechanism that gives under-tried options a fair shot at being picked. A narrow, confident distribution's samples cluster tightly around its true center, so a confidently mediocre option rarely wins the draw. Exploration and exploitation are not two separate steps here; sampling from uncertainty produces both at once, automatically weighted by how much is actually known about each option.

Worked example: two signals with a beta distribution

Suppose a signal's daily outcome is treated as a coin flip — profitable day or not — and its true win probability is unknown. Signal A has been tried 4 times, winning 3: its uncertainty is captured with a Beta(4, 2) distribution, mean $4/(4+2) \approx 0.67$, but still fairly wide given only 4 trials. Signal B has been tried 40 times, winning 24: Beta(25, 17), mean $25/42 \approx 0.60$, much narrower given 10x the data. Even though A's mean beats B's, Thompson sampling does not simply pick A outright — it draws one random sample from each distribution. A's wide draw might land anywhere from roughly 0.3 to 0.95; B's narrow draw almost always lands close to 0.60. A usually still wins, but B has genuine odds whenever A's draw lands low — and every round both distributions narrow further with new data, so confidence grows exactly as fast as the evidence justifies.

The updater above shows exactly this mechanic: a beta-shaped prior over a win probability narrows as more coin-flip-like outcomes come in. Thompson sampling runs one of these updaters per arm and draws a sample from each current posterior every round — the narrowing you see here is precisely why exploration tapers off automatically as data accumulates, with no separate schedule to design.

What this means in practice

Thompson sampling is the standard choice over epsilon-greedy whenever the cost of "wasted" exploration is high and a smarter, uncertainty-aware allocation pays for itself — allocating live trading capital across several new strategies, or choosing which order-routing algorithm to try, both fit this shape well. It requires choosing a probability model for each option's payoff (a Beta distribution for win/loss outcomes, a Gaussian for continuous returns), which is a real modeling choice epsilon-greedy avoids by not needing one at all.