Exploration vs exploitation tradeoff: Visual walkthrough

This page rebuilds the central result of the parent topic from absolute zero: why pure exploiting and pure exploring both cost you the same (bad) way, and why balancing them wins. We do it entirely in pictures — one figure per step. Nothing is assumed. If you have never seen a single symbol below, you will still follow from line one.

Related vault stops if you want more: 5.2.03-Multi-Armed-Bandits, 5.1.06-Temporal-Difference-Learning, 5.1.08-Q-Learning, 5.3.05-Curiosity-Driven-Exploration.

Step 1 — The world: a row of slot machines

WHAT. We label the machines $a = 1, 2, \dots, K$ . The letter $a$ just names an action (which lever). $K$ is how many levers exist.

WHY. This is the simplest possible world where the tradeoff already appears. No walls, no maps, no time-travel — just "which lever?" If we can't explain the tradeoff here, we can't explain it anywhere.

PICTURE. Below, three machines. Each has a hidden true average payout $μ_{a}$ (the Greek letter "mu", read "mew" — it just means "the long-run average reward of machine $a$ "). The tallest hidden bar is the best machine. You cannot see these bars yet — they are the secret.

Figure — Exploration vs exploitation tradeoff

Step 2 — The dream: if a genie told you the best machine

WHAT. Define the best average as $μ^{*} = max_{a} μ_{a} .$

Reading it term by term:

$max_{a}$ ::: "take the largest value as $a$ ranges over all machines."
$μ_{a}$ ::: the average of machine $a$ (from Step 1).
$μ^{*}$ ::: the star marks the champion's average — the biggest of all the $μ_{a}$ .

The genie's total haul over $T$ rounds (where $T$ is just "how many pulls we get") is $best total = T \cdot μ^{*} .$ $T \cdot μ^{*}$ means " $T$ rounds, each worth $μ^{*}$ ."

WHY $max$ and not something fancier? We want a yardstick — the unbeatable score. The largest average is by definition the most reward-per-pull, so pulling it every time is optimal. We use $max$ because "the best" literally means "the maximum."

PICTURE. The green line is the genie's steadily climbing treasure, slope $μ^{*}$ .

Step 3 — Reality: you must guess from noisy pulls

WHAT. Let $r_{t}$ be the reward you actually receive at round $t$ (the subscript $t$ = "at time step $t$ "). Your estimate of a machine's average is the ordinary average of its past rewards: $\overset{μ}{^}_{a} = \frac{1}{N _{t} ( a )} \sum_{i : a_{i} = a} r_{i} .$

Term by term:

$\overset{μ}{^}_{a}$ ::: the little hat means "my guess of $μ_{a}$ ", not the truth.
$N_{t} (a)$ ::: how many times I have pulled machine $a$ up to now.
$\sum_{i : a_{i} = a} r_{i}$ ::: add up every reward I got on the rounds where I chose $a$ .
dividing by $N_{t} (a)$ ::: turns that sum into an average.

WHY an average? Averaging is the cheapest honest summary of "how good has this machine felt so far." With few pulls it's a shaky guess; with many pulls it settles near the truth $μ_{a}$ . That shakiness is the whole story of the next steps.

PICTURE. Two machines, each dotted rewards; the running average (a line) wobbles a lot early, then calms down as pulls pile up.

Step 4 — Regret: measuring the price of not knowing

WHAT. $Regret (T) = genie’s total T \cdot μ^{*} - your expected total t = 1 \sum T E [r_{t}] = \sum_{t = 1}^{T} (μ^{*} - μ_{a_{t}}) .$

Term by term:

$T \cdot μ^{*}$ ::: the dream total from Step 2.
$E [r_{t}]$ ::: "expected" (average) reward you get at round $t$ ; the $E$ is just "on average." It equals $μ_{a_{t}}$ because pulling machine $a_{t}$ pays $μ_{a_{t}}$ on average.
$μ^{*} - μ_{a_{t}}$ ::: the per-round shortfall. Zero if you pulled the champion, positive otherwise.

WHY define regret at all? Because "how much reward did I get" depends on the machines' scale; "how much did I miss" is a clean, comparable number that is zero for the genie and grows only when you err. It turns "was my strategy good?" into "did my regret stay small?"

PICTURE. The green genie line and your lower orange line; the shaded gap between them is the regret, growing each round you pick a worse machine.

Step 5 — Pure exploitation fails: one bad sample, permanent damage

WHAT. Concretely (parent's Example 1): true $μ_{A} = 0.6$ , $μ_{B} = 0.8$ , so $μ^{*} = 0.8$ and $B$ is best. Early samples give $\overset{μ}{^}_{A} = 0.5$ , $\overset{μ}{^}_{B} = 0.0$ (one unlucky loss). Greedy sees $\overset{μ}{^}_{A} > \overset{μ}{^}_{B}$ , locks onto $A$ forever. Each round it loses $μ^{*} - μ_{A} = 0.8 - 0.6 = 0.2,$ so after $T$ rounds: $Regret (T) = 0.2 T = O (T) .$ The symbol $O (T)$ ("big-O of $T$ ") means "grows in proportion to $T$ " — a straight, ever-rising line. That's the worst kind: it never stops bleeding.

WHY it fails. Greedy trusts $\overset{μ}{^}$ as if it were $μ$ . With $N_{t} (B) = 1$ , that trust is unearned. No mechanism ever forces a re-pull of $B$ , so the false low estimate is frozen in.

PICTURE. $B$ 's single unlucky pull, greedy's decision to quit $B$ , and the resulting straight-line regret climbing forever.

Step 6 — Pure exploration also fails: knowledge you never use

WHAT. With $K$ machines chosen uniformly, your average per-round reward is the plain average of all the $μ_{a}$ , call it $\overset{μ}{ˉ} = \frac{1}{K} \sum_{a} μ_{a}$ . The per-round shortfall is the fixed positive number $μ^{*} - \overset{μ}{ˉ}$ , so $Regret (T) = (μ^{*} - \overset{μ}{ˉ}) T = O (T) .$ Again a straight rising line — same failure mode as greedy, opposite cause.

WHY it fails. Good estimates are worthless if the policy ignores them. Exploration answers "which is best?" but never cashes in the answer.

PICTURE. Accurate estimates (bars matching the true hidden bars) sitting next to a regret line that still climbs linearly — the tragedy of unused knowledge.

Recall

Why do both extremes give $O (T)$ regret? ::: Greedy commits before it knows (may commit to a loser); random knows but never commits. Either way a fixed positive shortfall repeats every round → straight line.

Step 7 — The balance: explore early, exploit later → sublinear regret

WHAT. Good strategies (like UCB and Thompson sampling from the parent) achieve $Regret (T) = O (lo g T) .$ Here $lo g T$ (natural logarithm of $T$ ) grows far slower than $T$ : doubling $T$ adds only a constant to $lo g T$ . So regret per round $\to 0$ . That is the technical meaning of "the tradeoff, solved well."

WHY $lo g T$ appears. Statistically, ruling out a wrong machine with confidence takes about $lo g T$ mistaken pulls (you need your confidence bound to shrink like $lo g t / N_{t} (a)$ — the exploration bonus in the parent's UCB rule). After that, you exploit. Sum the finitely-many exploratory errors and you get $lo g T$ , not $T$ .

PICTURE. Three curves on one plot: greedy (straight, steep), random (straight), balanced (bends flat like $lo g T$ ). The balanced curve is the whole point of the chapter.

Step 8 — Edge & degenerate cases (so you never hit a surprise)

Case A — Two machines are tied ( $μ_{A} = μ_{B} = μ^{*}$ ). Then picking either costs zero regret. There is nothing to lose by exploring between them; the tradeoff dissolves. Regret can be $0$ .

Case B — Only one machine ( $K = 1$ ). No choice, no exploration needed, $μ_{a_{t}} = μ^{*}$ always ⇒ $Regret (T) = 0$ . The tradeoff needs at least two competing options to exist.

Case C — All zero rewards. Every $μ_{a} = 0$ , so $μ^{*} = 0$ and regret is $0$ no matter what you do — but you also learn nothing useful. (This is the sparse-reward wall from the parent's Montezuma example; see 5.3.05-Curiosity-Driven-Exploration.)

Case D — $ϵ = 0$ vs $ϵ = 1$ . $ϵ$ is the exploration probability in $ϵ$ -greedy. $ϵ = 0$ is pure greedy (Step 5, $O (T)$ ). $ϵ = 1$ is pure random (Step 6, $O (T)$ ). Both endpoints of the dial are bad; the sweet spot is a small, decaying $ϵ$ so exploration fades as confidence grows (mirrors Step 7).

PICTURE. Regret as $ϵ$ sweeps from $0$ to $1$ : a U-shape (or bowl) — high at both ends, low in the middle — with the decaying- $ϵ$ strategy sitting at the bottom.

The one-picture summary

Everything above, compressed: the genie's line, greedy's linear bleed, random's linear bleed, and the balanced $lo g T$ curve that bends flat — with the shaded regret gaps labelled.

Recall Feynman retelling — say it back in plain words

There's a row of slot machines and one of them pays best on average, but you don't know which. A make-believe genie who knew the best machine would just pull it every time and rack up the highest possible score. Regret is simply how far behind that genie you fall — it's zero for the genie and grows every time you pull a worse machine. If you're stubborn and always pull whatever looks best from your tiny handful of tries, one unlucky early pull can make you quit the actually-best machine forever — your regret climbs in a straight line. If instead you pull totally at random, you learn which machine is best but never bother to use that knowledge — your regret also climbs in a straight line. The clever move is to explore a lot early (when you're unsure), then, as your confidence grows, gradually shift to almost always pulling the champion. Because the exploring you still need shrinks over time, your extra losses shrink too, and your regret curve bends flat — it grows like $lo g T$ , which is much, much slower than $T$ . Corner cases: with one machine or tied machines there's nothing to lose; with all-zero rewards there's nothing to learn; and the exploration dial is bad at both extremes, best in a decaying middle.

Recall

One-line takeaway ::: Pure exploit and pure explore both give $O (T)$ regret; balancing them (explore early, exploit later) gives sublinear $O (lo g T)$ regret.

Next: see how these ideas power learned value estimates in 5.1.08-Q-Learning and policy-based methods in 5.1.11-Policy-Gradient-Methods; and note the kinship with over-committing to noisy data in 4.5.07-Overfitting-and-Regularization.