Thompson sampling

Probability matching, 1933

Thompson’s 1933 paper posed the two-armed problem as a matter of evidence — the likelihood that one unknown probability exceeds another in view of two samples — and answered it with a randomized allocation rule now called posterior probability matching: play arm k with probability equal to the posterior probability that arm k has the highest success rate. The rule commits to neither pure exploration nor pure exploitation; the allocation itself carries the uncertainty.

The sampling implementation is what makes the rule cheap to run. Computing the matching probabilities exactly requires an integral over the joint posterior; drawing one sample θ per arm and playing the argmax realizes exactly those probabilities without ever computing them. Russo, Van Roy, Kazerouni, Osband and Wen’s 2018 tutorial is the standard modern treatment of the algorithm and its variants.

Beta–Bernoulli mechanics

For binary outcomes the conjugate form is simple. Each arm keeps a Beta(α, β) posterior; under the uniform prior Beta(1, 1), α − 1 counts observed successes and β − 1 counts observed failures. To select an arm, draw θₖ ~ Beta(αₖ, βₖ) independently for each arm k and play the argmax. On a success, add 1 to the played arm’s α; on a failure, add 1 to its β.

Exploration falls out of posterior width rather than a separate schedule. An arm with two successes and two failures holds Beta(3, 3) — a wide posterior that will regularly produce the largest draw even against an established arm whose posterior has narrowed around a similar rate. As evidence accumulates, each posterior concentrates and the allocation shifts toward the better arm by degrees, not by a switch.

Allocation is not proof

Thompson sampling answers a routing question — where the next trial should go — not an evidentiary one. Because assignment probabilities move with the accumulating data, traffic allocated by Thompson does not carry the fixed, design-time propensities a clean causal contrast requires; an estimate of what an arm causes, computed over Thompson-allocated traffic, inherits the drifting allocation that produced it.

The practical consequence is a separation of jobs: the optimizer may chase the posterior, but a published causal claim should rest on assignment probabilities fixed in advance — a randomized holdout, or a uniformly rotated cell whose propensities are known constants.

How RevenueOS uses this

RevenueOS runs Thompson sampling in its live allocation loop only (Loop A). Each tenant’s arms carry independent Beta posteriors seeded with the uninformative prior α₀ = β₀ = 1. As configured in July 2026: evidence decays geometrically at γ = 0.87 per week — a half-life of ≈ 5 weeks — so old outcomes stop dominating routing; an arm needs a minimum-evidence floor of 18 effective observations before exploitation leans on its posterior; and exploration is held to a bounded budget of 0.22.

The proof contrast (Loop B) is deliberately not Thompson. Arms in the proof cell rotate uniformly, so the published claim — the arm menu causes X versus not mailing — reads against fixed, design-time propensities. RevenueOS’s pilot documentation (the 2026 minimum-n table) states this explicitly and treats the uniform-rotation contrast as a clean lower bound for the Thompson-optimized program, under the stated assumption that the optimizer does no worse than uniform rotation. Conflating the allocation loop with the proof contrast is a documented reviewer error this separation exists to prevent: the bandit routes traffic; the randomized holdout carries the proof.

Related terms

Randomized holdout · Causal lift · Anytime-valid confidence sequence