Part VI — Reinforcement Learning

Chapter 23 · RL Foundations & the Multi-Armed Bandit (UCB)

Every model so far studied a static table. Part VI's data fights back: you choose an ad, the world answers with a click or silence, and the next choice inherits the consequences. The founding dilemma — explore the unknown or exploit the proven — gets its classic setting (ten ads, ten thousand rounds), its honest baseline (random selection), and its first solver: Upper Confidence Bound, optimism in the face of uncertainty, every term built by hand and every number real.

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

🎯 Learning Objectives

Define the reinforcement learning frame — agent, actions, rewards — and how it differs from every preceding part
State the exploration-exploitation dilemma and define regret precisely
Build the UCB formula term by term, and explain the confidence bound's origin and shrinkage
Read the real 10,000-round run: total reward, selection histogram, and the endgame bound race
Implement the algorithm exactly as the source, including the forced first round and the 1e400 trick
Characterise UCB's personality — deterministic optimism — and its limits, setting up Thompson Sampling

1. When Data Fights Back

In twenty-two chapters, the data never answered back. A model studied the table; the table sat still. Reinforcement learning breaks that contract: an agent takes an action, the environment returns a reward, and the agent's next action is chosen with the accumulated rewards in hand. The data is no longer a photograph — it is a conversation, and every reply costs a round you can never spend twice.

The running problem is the classic one: a website has 10 ad variants and 10,000 user visits. Each visit shows one ad; each shown ad either collects a click (reward 1) or doesn't (reward 0). Which ad should each round show? The catch that makes this Part's signature: you only ever observe the reward of the ad you chose — the nine ads not shown keep their answer forever. No train/test split can fix that; there is no full table to study, only the history your own policy created.

📝

Note — the simulation's secret: the dataset, Ads_CTR_Optimisation.csv, is a full 10,000 × 10 log of every ad's would-be outcome for every user (1 = that user would click that ad). Nature's answers exist in the file; the algorithm is allowed to read only the cell for the ad it actually shows. Ground truth lurks in the unselected cells — which is exactly how we can grade the policy afterwards. Best ad by nature's truth: Ad 5, click rate 0.2695 (2,695 clicks), ahead of Ad 8 (0.209) and Ad 1 (0.170).

2. The Dilemma: Explore or Exploit

Ten ads, unknown click rates: this is the multi-armed bandit — slot machines ("one-armed bandits") with unknown payouts, and the casino question: which arms to pull? Every strategy lives on a spectrum between two failures:

Pure exploration — try everything equally (random selection). We ran it for real: 10,000 rounds of uniform random choice earned 1,213 clicks (rate 0.121). Fair, honest, and terrible: it keeps paying the discovery cost forever, never concentrating on what it learned.
Pure exploitation — pick the current best guess and never let go. Lock onto whichever ad looked good in the first few rounds and a lucky-but-mediocre ad steals the whole campaign. Ad 1's early rounds could easily have crowned it; its true rate is 0.170 — you would forfeit ~1,000 clicks without ever noticing.

The measure of the tension is regret: the gap between your total reward and what a clairvoyant (always showing Ad 5) would have earned — 2,695 clicks here. Random selection's regret: 2,695 − 1,213 = 1,482. The art of the bandit is making regret grow as slowly as possible — each strategy is judged not by its clicks but by how few it left on the table.

Figure 23.1 — The dilemma as a spectrum: both endpoints fail; UCB lives on the profitable side of the middle.

3. UCB: Optimism in the Face of Uncertainty

The idea in one sentence: score each ad by the best its truth could plausibly be, and show the highest-scoring ad. "Plausibly" is a confidence bound (Hoeffding's inequality, stated without proof): with high probability, an ad's true rate lies within √(3·ln n / (2·n_i)) of its observed average — where n is the total rounds so far and n_i the rounds given to ad i. The UCB1 algorithm (Auer et al., 2002):

show argmax_i [ x̄_i + √( 3·ln n / (2·n_i) ) ]

x̄_i — exploitation: the ad's observed average reward. Proven ads earn their seat.
the square root — exploration: the uncertainty bonus. It shrinks as the ad is played (n_i grows) but grows as time passes (ln n rises) — so an under-tried ad's bonus quietly inflates until it gets another turn.
Never-played ads get bound = ∞ (the source's 1e400): round 1 shows ad 1, round 2 shows ad 2 … round 10 shows ad 10 — ten forced trials, then the bounds take over. The real run's first twelve selections: ads 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, then 1 and 2 again — the under-sampled leaders of the early lottery.

And the formula's punchline, straight from the real run's final state (round 10,000 — both numbers real):

Ad 5: n_i = 6,323 → 0.2649 + 0.0467 = 0.3116
Ad 4: n_i = 345 → 0.1101 + 0.2001 = 0.3103

Even at round ten thousand, Ad 4 — a mediocre ad (true rate 0.11) that UCB has correctly starved — sits one bound-width from stealing the next round. Exploration never stops; it just becomes cheaper. That 0.0013 gap is the algorithm breathing.

💡

Pro Tip — why "optimism" is the right word: assuming every ad is as good as its confidence bound allows is systematically hopeful — and provably safe: the only ads that lose rounds are those whose observed average can no longer keep their bound competitive. Pessimism (scoring by lower bounds) would starve every insufficiently-tried ad and never recover.

4. The Real Run: 10,000 Rounds

The complete scoreboard, all real, same 10,000 users:

Policy	Total reward	Click rate	Regret (vs 2,695)	Strategy
Clairvoyant (always Ad 5)	2,695	0.2695	0	Unknowable — the grading line
UCB	2,178	0.2178	517	Optimistic bounds; ~81% of perfect
Random selection	1,213	0.1213	1,482	Uniform exploration forever

Read the middle row the RL way: UCB earned 1.79× the random baseline and captured 81% of the unknowable maximum. Its regret of 517 clicks is the price of discovering which ad was best — rounds spent on ads 1–10 while their bounds were still fat — and it is a price random selection pays three times over, forever.

🌎

Real World: this is the actual mathematics of production ad-serving, headline testing and dynamic pricing — any system that must learn from its own live choices. The A/B test you run for two weeks and then pick a winner? A bandit algorithm is that same experiment run continuously, with the losing variants phased out as the evidence accumulates instead of at an arbitrary deadline.

📋 Stable content — Reviewed: August 2026

5. Implementation in Python

import numpy as np
import pandas as pd
import math

dataset = pd.read_csv('Ads_CTR_Optimisation.csv')
N = 10000                                # rounds (users)
d = 10                                   # actions (ads)

ads_selected = []
numbers_of_selections = [0] * d          # n_i per ad
sums_of_rewards = [0] * d               # total clicks per ad
total_reward = 0

for n in range(0, N):
    ad = 0
    max_upper_bound = 0
    for i in range(0, d):
        if numbers_of_selections[i] > 0:
            average_reward = sums_of_rewards[i] / numbers_of_selections[i]
            delta_i = math.sqrt(3/2 * math.log(n + 1) / numbers_of_selections[i])
            upper_bound = average_reward + delta_i
        else:
            upper_bound = 1e400          # infinity: try every arm once first
        if upper_bound > max_upper_bound:
            max_upper_bound = upper_bound
            ad = i
    ads_selected.append(ad)
    numbers_of_selections[ad] += 1
    reward = dataset.values[n, ad]       # nature reveals ONLY this cell
    sums_of_rewards[ad] += reward
    total_reward += reward

print(total_reward)                      # 2178

import matplotlib.pyplot as plt
plt.hist(ads_selected)                   # the selection histogram
plt.title('UCB Ad Selections'); plt.show()

Listing 23.1 — UCB1 exactly as the source (upper_confidence_bound.py).

💡

Pro Tip — read the loop as the RL frame: the inner scan is the policy (argmax over bounds), the single cell read is the environment's reply, and the two updated lists are the learned state. Cost: O(N·d) — trivial here, and the per-round work stays O(d) in production, which is why this family scales to live traffic.

6. Reading the Histogram

The algorithm's autobiography — how many of the 10,000 rounds each ad received (all real):

Ad	1	2	3	4	5	6	7	8	9	10
Rounds	705	387	186	345	6,323	150	292	1,170	256	186

Three readings:

The winner took 63% of the campaign — 6,323 rounds on Ad 5, its observed rate (0.2649) already hugging nature's 0.2695. But not 100%: the residual 3,677 rounds are not waste, they are the ongoing lease payments that keep the bound race (Section 3) honest.
Ad 8's 1,170 rounds are a story of bad luck. Nature's second-best (0.209), it must have drawn a mediocre early sample; its bound kept it in the race long after weaker rivals retired. The histogram is not just "who was best" — it is "who was unluckily ambiguous".
The floor is exactly 150+. No ad starves below the forced ten — every arm keeps its shrinking credit line. Compare a pure-exploit histogram: one bar at 10,000, nine at ~5, and no way back.

7. UCB's Personality & Limits

Strengths	Limitations
Provably near-optimal regret (logarithmic in n)	Deterministic — identical history, identical choices; no sense of how confident, only a bound
Simple, parameter-free (the bound is derived, not tuned)	The 3/2 constant is a worst-case bound — conservative in practice
O(d) per round — production-friendly	Struggles with delayed rewards and non-stationary worlds (yesterday's best ad may retire)
The forced first round guarantees no arm is silently ignored	Exploration is scheduled, not sampled — can feel mechanical in adaptive environments

Keep the deepest line for the next chapter: UCB's bound answers "what is the best this ad could plausibly be?" — a number. It never forms a belief about the ad's rate, never represents "probably around 0.27, and I'm fairly sure." That is a probability distribution's job, and it is exactly what the Bayesian flip provides.

8. The Road Ahead: the Bayesian Flip

Part VI continues with Thompson Sampling — same bandit, same dataset, same dilemma, opposite philosophy. Where UCB asks "what's the most each ad could be?" and plays the highest ceiling, Thompson asks "what do I believe each ad's rate is?" — holds that belief as a probability distribution (a Beta, updated with every click and silence), samples one possible world from each ad's belief, and plays the sample's winner. Exploration stops being a scheduled bound and becomes a natural consequence of uncertainty. On this very dataset it will edge out UCB — and explaining why is the next chapter's business.

🛠 Hands-On: Run the CampaignIntermediate

The ad team wants evidence that "the fancy algorithm" beats their rotating-banner plan before switching. Reproduce the baseline, the run, the histogram — and the bound race that shows the algorithm is still awake at round 10,000.

Steps

Compute nature's truth: per-ad click rates over all 10,000 rows; identify the best ad and the perfect-foresight reward.
Run random selection for 10,000 rounds; report total reward and regret.
Run UCB (the source algorithm); verify total reward 2,178 and regret 517; plot the histogram.
Print the first 12 selections; explain the pattern and the 1e400 mechanism behind it.
From the final state, recompute by hand the UCB bounds for Ad 5 (n=6,323, avg 0.2649) and Ad 4 (n=345, avg 0.1101) at n = 10,000; verify against the run.
Write the memo: random vs UCB vs clairvoyant, what the 3,677 non-Ad-5 rounds bought, and the one-sentence recommendation.

View Solution / Walkthrough

import numpy as np, pandas as pd, math, random

ds = pd.read_csv('Ads_CTR_Optimisation.csv')
R = ds.values.astype(float); N, d = R.shape
print('per-ad CTR:', R.mean(axis=0).round(4))    # ad5 = 0.2695 best

random.seed(111)
sel = [random.randrange(d) for _ in range(N)]
print('random:', sum(R[i, sel[i]] for i in range(N)))   # ~1213

ads, n_sel, s_rew, total = [], [0]*d, [0]*d, 0
for n in range(N):
    best, ad = 0, 0
    for i in range(d):
        ub = (s_rew[i]/n_sel[i] + math.sqrt(1.5*math.log(n+1)/n_sel[i])
              if n_sel[i] else 1e400)
        if ub > best: best, ad = ub, i
    ads.append(ad); n_sel[ad] += 1
    s_rew[ad] += R[n, ad]; total += R[n, ad]
print('UCB:', total, n_sel)                      # 2178; ad5 6323

# Step 5: the endgame race, by hand
for i in [4, 3]:
    avg = s_rew[i]/n_sel[i]
    print('ad%d: %.4f + %.4f = %.4f' % (i+1, avg,
          math.sqrt(1.5*math.log(N)/n_sel[i]),
          avg + math.sqrt(1.5*math.log(N)/n_sel[i])))

Expected results (real):

Step 1: Ad 5 best at 0.2695 → perfect reward 2,695; Ad 8 second (0.2091); Ad 1 third (0.1703).
Step 2: random ≈ 1,213; regret ≈ 1,482 (seed-dependent wobble of a few dozen).
Step 3: UCB = 2,178; regret 517; counts 705/387/186/345/6323/150/292/1170/256/186.
Step 4: ads 1…10 in order, then repeats — untried arms carry bound ∞ (the 1e400 sentinel), so round 11+ revisits the earliest, least-informed arms.
Step 5: Ad 5: 0.2649 + 0.0467 = 0.3116; Ad 4: 0.1101 + 0.2001 = 0.3103 — a live race at round ten thousand.
Step 6: random 1,213 / UCB 2,178 / clairvoyant 2,695; the 3,677 other rounds bought the continuing proof that no challenger's ceiling beats Ad 5's average; recommend UCB (or better — Thompson, next chapter) over rotation.

🎯 Key Takeaways

RL's contract: act, observe only the chosen action's reward, choose again. You can never study the full table — only the history your policy wrote.

The dilemma: pure explore (random, 1,213) pays discovery forever; pure exploit locks onto early luck. Regret — clicks left vs the clairvoyant — is the judge.

UCB plays argmax(average + √(3ln n / 2nᵢ)): exploit the proven, but every under-tried ad keeps a shrinking credit line — optimism, provably safe.

The real run: UCB 2,178 vs random 1,213 (1.79×), 81% of the 2,695 maximum, regret 517 — the fair price of finding the best ad.

The histogram is autobiography: Ad 5 took 63% of rounds, Ad 8's 1,170 rounds are unluckily-ambiguous history, and no arm starves below the forced ten.

At round 10,000 the bound race was 0.3116 vs 0.3103 — exploration never stops, it just gets cheaper. UCB bounds a ceiling; beliefs need distributions (Thompson, next).