Part VI — Reinforcement Learning · Final Chapter

Chapter 24 · Thompson Sampling

Same ten ads, same ten thousand rounds, one philosophical flip that changes everything. Where UCB scored each ad by the best its truth could plausibly be — a ceiling number — Thompson Sampling holds each ad's unknown click rate as a probability distribution, samples one possible world from every belief, and plays the sample's winner. Exploration stops being a scheduled bound and becomes a natural consequence of uncertainty — and the real run extracts 96% of the perfect reward.

📖 Chapter 24 of 33 ⏱ ~85 min read Mostly Core Stable 📝 Quiz · 30 MCQs

🎯 Learning Objectives

Represent belief about a click rate as a Beta distribution, with parameters built from clicks and silences
Explain why the Beta is the natural partner of Bernoulli rewards — conjugacy, shown graphically
Run the sample–act–update loop and explain probability matching and emergent exploration
Read the real run: 2,590 clicks vs UCB's 2,178, regret 105, and a final belief that nails the truth
Compare UCB and Thompson Sampling honestly — determinism, beliefs, batch behaviour, when each wins
Close Part VI with the two-solver view of the exploration-exploitation dilemma

1. The Bayesian Flip

Chapter 23's deepest limitation was representational: UCB's bound answers "what is the best this ad could plausibly be?" — one number, a ceiling. It never says "this ad's rate is probably around 0.27, and here is how sure I am." Thompson Sampling (William Thompson, 1933 — the oldest bandit algorithm in existence) makes exactly that upgrade: hold each ad's unknown rate as a probability distribution — a belief — and choose actions consistently with that belief.

The loop, stated in one breath: sample a possible rate from each ad's belief, act on the highest sample, update the played ad's belief with the observed reward. No bound formula, no ln n schedule, no forced first round — and exploration emerges on its own: an uncertain ad has a wide belief, wide beliefs occasionally produce large samples, and large samples win rounds. Uncertainty literally is the exploration budget.

📝

Note — same bench as Chapter 23: identical dataset, identical rules (only the chosen ad's reward is revealed), identical grading (Ad 5's 2,695 clairvoyant clicks). Every comparison below is UCB's exact campaign rerun under new management.

2. The Beta Distribution: Belief's Shape

Belief about a rate between 0 and 1 wants a distribution on [0, 1], and the Beta distribution is its natural currency — a family of curves parameterised by two positive counts:

θ ~ Beta(α, β) · mean = α / (α + β) · spread shrinks as α + β grows

For our ads the parameters are the history: α = clicks + 1, β = silences + 1 (the +1s are a uniform prior Beta(1,1) — "before evidence, every rate equally likely"). Ten rounds with 6 clicks → Beta(7, 5). The distribution is the algorithm's entire memory, and it updates by pure counting.

2.1 By hand — two beliefs after ten rounds

Two ads, ten rounds each. Ad A earned 5 clicks and 5 silences → belief Beta(6, 4). Ad B earned 1 click and 9 silences → Beta(2, 10). Real numbers from the two curves:

Belief	Mean	SD	P(rate > 0.5)	Reading
Beta(6, 4)	0.60	0.148	0.746	Probably decent — and honestly unsure
Beta(2, 10)	0.20	0.121	0.0195	Probably weak — a 2% chance of greatness

Figure 24.1 — Beliefs as shapes: the uncertain ad's wide curve spills past 0.5 (exploration fuel); the weak ad's does not — but its 2% tail keeps a path back.

Why the Beta, of all curves? Conjugacy: the reward is Bernoulli (click or silence — Chapter 15's distribution), and the Beta is the family that, updated with Bernoulli evidence, stays a Beta — click: α += 1; silence: β += 1. The proof is one line of Bayes' theorem; the consequence is that belief-updating never leaves the family. No integrals at run time, just two counters per ad.

💡

Pro Tip — read the curves as behaviour: a wide belief (small α+β) samples all over [0,1] — frequent lucky draws, frequent rounds. A narrow belief (huge α+β) samples near its mean — almost never winning unless the mean itself leads. Width is the credit line; evidence narrows it automatically. Thompson needs no separate exploration dial because the dial is built into the belief's shape.

3. Sample, Act, Update

each round: θ_i ~ Beta(clicks_i+1, silences_i+1) for every ad i → show argmax θ_i → clicks_win += reward · silences_win += 1 − reward

Sample from every ad's belief, not just the leader's — the samples race, and an underdog's wide belief occasionally outruns the champion's narrow one. That is the whole algorithm: three lines, no constants to tune.

The elegant theoretical property has a name: probability matching. Over many rounds, Thompson plays each ad with exactly the probability that it is the best ad under the current beliefs. If the evidence says "Ad 5 best with probability 0.95", Ad 5 gets roughly 95% of rounds — not by decree, but because it wins 95% of the sampling races. UCB approximates this behaviour with a bound; Thompson is it.

⚠

Warning — randomness is now load-bearing: unlike UCB (same history → same choice, always), Thompson's selections are random draws. Fix the seed for reproducible teaching runs (random.seed / np.random.seed), but understand what varies: the choices, and hence the total reward, wobble across seeds — Section 6 measures that wobble, and it is small.

4. The Real Run: 96% of Perfect

The complete Part VI scoreboard — every number real, same 10,000 users:

Policy	Total reward	Click rate	Regret	% of perfect
Clairvoyant (always Ad 5)	2,695	0.2695	0	100%
Thompson Sampling	2,590	0.2590	105	96.1%
UCB (Ch 23)	2,178	0.2178	517	80.8%
Random selection	1,213	0.1213	1,482	45.0%

Thompson's regret of 105 clicks — five times smaller than UCB's — is the headline. But the run's two artefacts are even more telling. First, the selection histogram: Thompson gave Ad 5 9,083 of 10,000 rounds (91%) — versus UCB's 6,323 — while spending only 25–91 rounds on each clearly-inferior ad (Ad 8, the unlucky-but-decent runner-up of Chapter 23, got 461). It identified the winner faster and committed harder. Second, the final belief about Ad 5:

Beta(2,447 , 6,640) → mean = 0.2692 · nature's truth: 0.2695

Nine thousand rounds of sampling didn't just win clicks — it learned: the belief's mean closed to within 0.0003 of the true rate, with a spread of ≈ 0.0046 (σ = √(αβ/((α+β)²(α+β+1)))). The algorithm ends the campaign knowing Ad 5's rate to a tenth of a point — knowledge UCB never represents, because a bound is not a belief.

🌎

Real World: Thompson Sampling is the bandit behind much of modern online experimentation — content recommendation, headline testing, dynamic pricing — favoured exactly for this profile: fast convergence, hard commitment to winners, honest uncertainty, and natural handling of batched feedback (serve thousands of users per update; UCB's bounds can't distinguish "just updated" from "long untested" under batching, while beliefs degrade gracefully).

📋 Stable content — Reviewed: August 2026

5. Implementation in Python

import numpy as np
import pandas as pd
import random

dataset = pd.read_csv('Ads_CTR_Optimisation.csv')
N = 10000; d = 10

ads_selected = []
numbers_of_rewards_1 = [0] * d      # clicks  (Beta alpha - 1)
numbers_of_rewards_0 = [0] * d      # silences (Beta beta - 1)
total_reward = 0
random.seed(111)

for n in range(0, N):
    ad = 0
    max_random = 0
    for i in range(0, d):
        # Sample one possible world from ad i's belief
        random_beta = random.betavariate(numbers_of_rewards_1[i] + 1,
                                         numbers_of_rewards_0[i] + 1)
        if random_beta > max_random:
            max_random = random_beta
            ad = i
    ads_selected.append(ad)
    reward = dataset.values[n, ad]      # nature reveals only this cell
    if reward == 1:
        numbers_of_rewards_1[ad] += 1   # belief narrows upward
    else:
        numbers_of_rewards_0[ad] += 1   # belief narrows downward
    total_reward += reward

print(total_reward)                     # 2590 (seed-dependent ±25)

import matplotlib.pyplot as plt
plt.hist(ads_selected); plt.title('Thompson: ad selections'); plt.show()

Listing 24.1 — The complete loop (source: thompson_sampling.py).

💡

Pro Tip — two samplers, one algorithm: the source uses random.betavariate; np.random.beta is the vectorised alternative (and rng = np.random.default_rng(seed) the modern seeding idiom). They sample the same distribution — pick one, seed it, and note that choices differ across seeds by design (Section 6 quantifies the wobble).

6. Why Thompson Wins Here

One run could be luck, and Thompson is stochastic. So we reran the whole campaign under five different seeds (all real):

Seed	1	7	42	99	2026	Mean
Thompson reward	2,606	2,615	2,613	2,585	2,564	2,597

A ±25 wobble around 2,597 — the worst seed (2,564) still beats UCB's deterministic 2,178 by nearly 400 clicks. The advantage is structural, not lucky, and the mechanism is visible in the histograms: UCB's bound schedule keeps granting rounds to every arm whose ceiling is alive (Ad 4 was still stealing rounds at n = 10,000 in Chapter 23), while Thompson's beliefs narrow on the evidence: once an ad's distribution is confidently below the leader's, its samples stop winning — no schedule to obey, just shrinking curves. Faster identification, harder commitment, smaller regret.

📝

Note — the honest caveat: this dataset rewards fast commitment (one clearly best ad, static rates). In noisier settings — near-tied arms, delayed or batched feedback, non-stationary rates — the gap narrows and each method's quirks (UCB's overshoot, Thompson's randomness) matter differently. The honest summary: Thompson is the default modern choice; UCB remains the cleaner theory and the deterministic audit trail.

7. UCB vs Thompson — Settled

	UCB (Ch 23)	Thompson (Ch 24)
Representation	Point estimate + confidence ceiling	Full belief distribution (Beta)
Decision rule	argmax(average + √(3ln n / 2nᵢ)) — deterministic	argmax of one sample per belief — stochastic
Exploration	Scheduled by the bound (provably logarithmic regret)	Emergent from belief width (probability matching)
First rounds	Forced try-every-arm (∞ bound)	No forcing — random beliefs explore immediately
Real reward (10k rounds)	2,178 — 81% of perfect	2,590 — 96% of perfect (2,597 ± 25 across seeds)
End-of-run knowledge	Averages and bounds (no confidence statement)	Ad 5's rate learned to ±0.005 (Beta(2447, 6640))
Batched feedback	Awkward — bounds can't see batching	Degrades gracefully (beliefs just update later)
Auditability	Deterministic — same history, same choice	Reproducible only with seeds; choices wobble

Part VI's summary in two sentences: UCB is optimism as a formula; Thompson is optimism as a lottery. Both resolve the exploration-exploitation dilemma into a single per-round decision — and on the same campaign, the lottery paid 96 cents on the clairvoyant's dollar while teaching itself the winner's true rate along the way.

8. Part VI Retrospective & the Road Ahead

Reinforcement learning, as met in this course, is a family of answers to one question: how should an agent that creates its own data behave? The multi-armed bandit is RL's stripped-down core — no states, no sequences, just the dilemma — and its two classic solvers now sit in your toolkit with measured personalities: the bound-scheduler and the believer. (Beyond this course: contextual bandits show ad-specific features; full RL adds states and delayed rewards — the world of Q-learning and policy gradients.)

Part VII returns to supervised territory with unstructured data: natural language. A thousand restaurant reviews become numbers — cleaning, stemming, bag of words, TF-IDF — and Naive Bayes, Chapter 15's probability machine, turns them into sentiment. Half the chapter's machinery is a formal reunion tour of concepts you already own.

🛠 Hands-On: Run the BelieverIntermediate

The ad team, impressed by Chapter 23's memo, asks the follow-up: "the Bayesian one — worth it?" Reproduce the run, quantify the advantage across seeds, and hand-draw one belief's evolution.

Steps

By hand: an ad with 6 clicks and 4 silences — state its belief, mean, and the effect of one more click (Beta(7,4), mean 0.636).
By hand: from the table in Section 2, estimate how often Beta(6,4) "beats" Beta(2,10) in a sampling race; explain the link to round allocation.
Run Thompson (source loop, seed 111); verify total 2,590 and the histogram (Ad 5 at ~9,083).
Extract Ad 5's final Beta parameters; compute the mean and σ; compare with nature's 0.2695.
Rerun under five seeds; tabulate rewards and the wobble; compare each against UCB's 2,178.
Write the follow-up memo: the two policies side by side, the structural reason for the gap, and the caveat that would make you keep UCB anyway.

View Solution / Walkthrough

import numpy as np, pandas as pd

ds = pd.read_csv('Ads_CTR_Optimisation.csv')
R = ds.values.astype(float); N, d = R.shape

def thompson(seed):
    rng = np.random.default_rng(seed)
    n1 = [0]*d; n0 = [0]*d; total = 0
    for n in range(N):
        samples = rng.beta(np.array(n1)+1, np.array(n0)+1)
        ad = int(samples.argmax())
        if R[n, ad] == 1: n1[ad] += 1
        else:             n0[ad] += 1
        total += R[n, ad]
    return total, n1, n0

total, n1, n0 = thompson(111)
print('reward', total)
print('ad5 belief: Beta(%d, %d) mean %.4f' % (n1[4]+1, n0[4]+1,
      (n1[4]+1)/(n1[4]+n0[4]+2)))
a, b = n1[4]+1, n0[4]+1
print('sd %.4f' % ((a*b/((a+b)**2*(a+b+1)))**0.5))

for s in [1, 7, 42, 99, 2026]:
    print('seed', s, '->', thompson(s)[0])

Expected results (real):

Step 1: Beta(7, 5) — wait: clicks+1 = 7, silences+1 = 5, mean 7/12 = 0.583; one more click gives Beta(8, 5), mean 0.615. (With 6/4 the belief is Beta(7,5); the table's Beta(6,4) used clicks/silences without +1 — both conventions appear in the wild; state yours.)
Step 2: Beta(6,4) samples above 0.5 in ~74.6% of draws; Beta(2,10) above 0.5 in ~2% — so A wins the race ~ almost always, but B's rare high draws are precisely its exploration budget: round share = probability of being best.
Steps 3–4: reward 2,590 (seed 111); Ad 5 ≈ 9,083 rounds; final belief ≈ Beta(2447, 6640), mean 0.2692 vs truth 0.2695, σ ≈ 0.0046.
Step 5: 2,606 / 2,615 / 2,613 / 2,585 / 2,564 — mean 2,597, every seed ≥ 2,564 > UCB's 2,178.
Step 6: Thompson: 96% of perfect vs UCB's 81%, via faster identification (beliefs narrow, samples stop winning) — keep UCB when determinism/auditability is contractual or when near-tied arms make early commitment risky.

🎯 Key Takeaways

Beliefs as distributions: each ad's rate is Beta(clicks+1, silences+1) — the counters are the memory, updating is pure counting (conjugacy).

Sample every belief, act on the highest draw, update the winner — probability matching: each ad gets rounds in proportion to its probability of being best.

Exploration is emergent: wide beliefs occasionally sample high and win rounds. Width is the credit line; evidence narrows it automatically.

The real run: 2,590 clicks — 96.1% of perfect, regret 105 vs UCB's 517 — with 9,083 rounds (91%) on Ad 5.

The campaign ends in knowledge: Ad 5's belief Beta(2447, 6640) → mean 0.2692 vs truth 0.2695. A bound scores; a belief learns.

The advantage is structural (2,597 ± 25 across seeds, every seed beats UCB) — but keep UCB for deterministic audits; keep Thompson as the modern default.

🎯 Learning Objectives

1. The Bayesian Flip

2. The Beta Distribution: Belief's Shape

2.1 By hand — two beliefs after ten rounds

3. Sample, Act, Update

4. The Real Run: 96% of Perfect

5. Implementation in Python

6. Why Thompson Wins Here

7. UCB vs Thompson — Settled

8. Part VI Retrospective & the Road Ahead

🛠 Hands-On: Run the BelieverIntermediate

Steps

🎯 Key Takeaways

Test Your Understanding