Thompson sampling is a multi-armed bandit method for running production experiments while reducing the cost of showing users underperforming alternatives. It assigns each arm a probability of being best, pbest(arm), then selects arms in proportion to those probabilities. Better-looking arms receive more traffic, while uncertain arms still receive measurements. section 3.0 section 3.3
This randomized probability-matching rule balances exploitation and exploration without reserving a fixed share of traffic for arbitrary random choices. Early in an experiment, uncertainty produces broad exploration; as measurements accumulate and pbest estimates become more certain, selection increasingly favors the best arm. A stopping rule can end experimentation when an arm's pbest exceeds a threshold such as 0.95. section 3.3 section 3.3.2
Bootstrap selection for click-through rate
For each arm, draw one bootstrap estimate of CTR and select the arm with the highest sampled CTR. An arm wins these sampled comparisons at roughly its probability of being best, so this procedure implements probability matching directly. A full bootstrap on every decision becomes slow as data grows; an online bootstrap maintains sampled sums and counts to make repeated selection practical. section 3.3.2
Figure 3.17 The ad selector testing multiple click models using Thompson sampling. The server chooses a click-probability model using randomized probability matching (listing 3.13)—that is, the selection with probability proportional to the probability (p_best, listing 3.16) that the model has the highest CTR. Randomized probability matching is made efficient by the online bootstrap (listing 3.15), which tracks 100 bootstrap-sampled CTRs for each click model.
The ad-selector workflow connects online bootstrap estimates, randomized arm selection, and pbest estimation for several click models. section 3.3.3
A production implementation should force initial measurement of arms until CTR resolution can detect a practically significant difference. The number of online bootstrap means trades fidelity against speed; the implementation cited uses at least 100 in practice and recomputes the slower pbest estimate less often than arm selection. On the four-arm example, Thompson sampling slightly improved mean CTR over epsilon-greedy and normally stopped much sooner. section 3.3.3 section 3.4
For contextual decisions, Thompson sampling can explore model parameters rather than actions. Build a bootstrap-trained ensemble, choose one model uniformly for each request, and take that model's highest-reward action. If seven of ten models choose one post and three choose another, the policy selects them about 70% and 30% of the time, respectively. section 5.3 section 5.3.2
