Worked examples — Exploration vs exploitation tradeoff

This page is a worked-example gym. The parent note gave you the tools — regret, epsilon-greedy, UCB, Thompson sampling. Here we swing every tool at every kind of situation, one at a time, so that when an exam or a real project throws you a weird case, you have already seen it.

Before anything, one promise: every symbol used below is either built here or was defined in the parent. Let me re-anchor the ones I lean on most, in plain words.

---

The scenario matrix

Every problem in this topic is one of these cells. The examples below each carry their cell label so you can see the whole board getting covered.

Cell	What makes it tricky	Covered by
C1 Clean two-arm, greedy trap	one unlucky early sample locks you onto the worse arm	Ex 1
C2 Zero-division / never-tried arm	$N_t(a)=0$ makes UCB's bonus infinite	Ex 2
C3 Tie in estimates	two arms with equal $Q$, bonus decides	Ex 3
C4 Limiting behaviour as $t\to \infty$	does the bonus vanish? does regret stay sublinear?	Ex 4
C5 Epsilon decay arithmetic	picking a schedule, computing explore-probability at a given step	Ex 5
C6 Thompson with Beta, degenerate prior	all-successes or all-failures posterior	Ex 6
C7 Real-world word problem	A/B testing a website button	Ex 7
C8 Exam twist: sparse-reward failure	why $ϵ$-greedy's regret bound quietly breaks	Ex 8

---

Worked Examples

Ex 1 — Cell C1 · the greedy trap

Forecast: guess now — will greedy ever escape? And roughly how many times will 10%-random exploration touch B in 1000 steps?

1. Estimates. At this point $t=3$: $Q_t(A)=\frac{1}{2}=0.5$, $Q_t(B)=\frac{0}{1}=0$. Why this step? $Q_t$ is just the running average of observed rewards up to now; that is the only knowledge the agent has.
2. Greedy pick. Greedy always takes $\arg {\max }_a{Q}_t(a)$. Since $0.5>0$, it picks A forever. Why this step? Greedy never pulls B again, so $Q_t(B)$ never updates off that one unlucky $0$ — the mistake is permanent.
3. Greedy per-step regret. Recall ${\mu }^{\star }=\max ({\mu }_A,{\mu }_B)=0.8$ is the best possible mean. Regret per step $={\mu }^{\star }-{\mu }_{a_t}=0.8-0.6=0.2$. Over $T$ steps (the whole horizon), $\text{Regret}=0.2T$ — linear, unbounded. Why this step? ${\mu }^{\star }$ is the reward we could have earned; the gap ${\mu }^{\star }-{\mu }_{a_t}$ is what greedy throws away every single step.
4. Epsilon-greedy exploration count. With $ϵ=0.1$ we act randomly $10\%$ of the time; a random pull hits B with prob $\frac{1}{2}$. Expected B-explorations in $T=1000$: $1000\times 0.1\times 0.5=50$. Why this step? These fresh samples are what let $Q_t(B)$ climb toward $0.8$ and overtake $Q_t(A)\approx 0.6$ — the trap springs open.

Verify: greedy regret at $T=1000$ is $0.2\times 1000=200$. Now the rigour on "why 50 is enough": the standard error of an average of $n$ Bernoulli samples is $\sqrt{\mu (1-\mu )/n}$. For B with $n=50$, that is $\sqrt{0.8\cdot 0.2/50}=\sqrt{0.0032}\approx 0.057$. So after $\approx 50$ pulls, $Q_t(B)$ sits within about $\pm 0.057$ of $0.8$, i.e. above $0.74$ — comfortably past $Q_t(A)\approx 0.6$. The gap to beat is $0.8-0.6=0.2$, which is more than $3$ standard errors, so overtaking is near-certain, not merely "more than one sample." ✓

---

Ex 2 — Cell C2 · the never-tried arm (zero division)

Forecast: UCB score is $Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}$ (recall $c$ is the exploration knob). What happens when you divide by zero?

1. Read the bonus for arm 3. $\sqrt{\frac{\ln 5}{0}}$ divides by zero → the bonus is $+\infty$. Why this step? An arm we know nothing about has unbounded optimism — UCB refuses to skip it.
2. The universal convention. Every UCB implementation treats "$N_t(a)=0$" as a special case: pull each arm once before applying the formula. Effectively its UCB is $+\infty$. Why this step? Without one sample there is no $Q_t(a)$ at all — the formula is undefined, so we bootstrap it.
3. So at $t=5$, arm 3 is chosen. Its infinite bonus beats any finite score from arms 1 and 2. Why this step? This is the guarantee that UCB tries every action at least once — a degenerate input handled by design, not by luck.
4. After that pull, say arm 3 returns reward $0.7$, so $Q_t(3)=0.7,N_t(3)=1$; now recompute with $t=6$: ${\text{bonus}}_3=c\sqrt{\frac{\ln 6}{1}}$, which is finite. Why this step? One droplet in the jar turns "infinite curiosity" into an ordinary, comparable score.

Verify: with $c=1$, arm-1 bonus at $t=5$ is $\sqrt{\ln 5/3}\approx 0.732$, score $\approx 1.632$ — finite. Arm 3's is $+\infty >1.632$. UCB picks arm 3. ✓

---

Ex 3 — Cell C3 · a tie in estimates

Forecast: equal values — does UCB flip a coin, or is there a rule?

1. Bonus for arm 1. $2\sqrt{\frac{\ln 50}{40}}=2\sqrt{\frac{3.912}{40}}=2\sqrt{0.0978}=2(0.3127)=0.625$. Why this step? Big $N$ → small bonus. Confident arm, low curiosity.
2. Bonus for arm 2. $2\sqrt{\frac{\ln 50}{5}}=2\sqrt{\frac{3.912}{5}}=2\sqrt{0.7824}=2(0.8845)=1.769$. Why this step? Same $\ln 50$, tiny $N=5$ → the denominator shrinks, bonus balloons.
3. Scores. UCB${}_1=0.5+0.625=1.125$; UCB${}_2=0.5+1.769=2.269$. Why this step? Equal value, unequal certainty. The under-sampled arm wins.
4. Interpretation. UCB always breaks a value-tie in favour of the arm it knows less about — "optimism in the face of uncertainty." Why this step? This is exactly the exploration pressure that prevents the greedy trap of Ex 1.

Verify: UCB${}_2-$UCB${}_1=1.769-0.625=1.144>0$, so arm 2 chosen. ✓

Read the figure below to see this: each bar is stacked — the violet lower block is the value $Q_t=0.5$ (identical for both arms), and the orange upper block is the exploration bonus. Arm 2's orange block is much taller because $N_t(2)=5$ is small, so its total UCB (the top of the stacked bar) overtops Arm 1's despite the identical violet floors. The magenta arrow points to exactly the "extra height from uncertainty" that decides the tie.

---

Ex 4 — Cell C4 · limiting behaviour as $t\to \infty$

Forecast: guess whether the bonus goes to $0$, a constant, or infinity.

1. Substitute $N_t=t/2$. Bonus $=c\sqrt{\frac{\ln t}{t/2}}=c\sqrt{\frac{2\ln t}{t}}$. Why this step? We want the growth rate, so express the bonus purely in $t$.
2. Take the limit. As $t\to \infty$, $\ln t$ grows but $t$ grows far faster, so $\frac{\ln t}{t}\to 0$, hence bonus $\to 0$. Why this step? This is the key promise of UCB: once an arm is heavily sampled, its curiosity dies out and UCB behaves like greedy on that arm.
3. Why $\ln t$ and not $t$ upstairs? If the numerator were $t$ the bonus would not vanish; $\ln t$ grows just slowly enough that total regret is $O(\ln T)$ — sublinear, matching the parent's claim. Why this step? The logarithm is the exact dial that keeps exploring "just enough, forever" without paying linear regret.
4. Contrast with fixed-$ϵ$ greedy. A constant $ϵ$ forces a fixed exploration fraction forever, so its regret stays $O(ϵT)$ — linear. Only a decaying $ϵ$ (Ex 5) or UCB reaches sublinear. Why this step? This is why "which strategy" matters — the limiting regret order is decided here.

Verify: at $t=10^6$, bonus $\approx 2\sqrt{2\ln (10^6)/10^6}=2\sqrt{2(13.8155)/10^6}=2\sqrt{2.763\times 10^{-5}}\approx 0.0105$ — near zero. ✓

---

Ex 5 — Cell C5 · epsilon-decay arithmetic

Forecast: guess which schedule is still exploring meaningfully at step 100.

1. Exponential at $t=100$. ${ϵ}_{100}=1.0\times 0.99^{100}$. Since $0.99^{100}=e^{100\ln 0.99}=e^{-1.005}=0.366$. Why this step? Multiplying by $0.99$ each step compounds; converting to $e^{\cdot }$ makes the exponent easy to reason about.
2. Harmonic at $t=100$. ${ϵ}_{100}=1.0/100=0.01$. Why this step? Direct substitution; the $1/t$ rule crushes exploration much faster by step 100.
3. Compare. Exponential $=0.366$ vs harmonic $=0.01$. The exponential schedule still explores $\sim 37\%$ of the time — far gentler early decay. Why this step? Gentle decay protects against the greedy trap when early estimates are noisy; aggressive decay commits faster.
4. Rule of thumb. Hard exploration problems → gentle (exponential or slow) decay; easy problems with clean signal → fast $1/t$ decay is fine. Why this step? The schedule is a knob trading early caution against late efficiency — the tradeoff, again, one level down.

Verify: $0.99^{100}\approx 0.3660$ and $1/100=0.01$, and $0.366>0.01$. ✓

---

Ex 6 — Cell C6 · Thompson sampling, degenerate posterior

Forecast: arm X looks perfect (4/4). Does Thompson ever explore Y again?

1. Posteriors. The update rule is $\text{Beta}(1+s_a,1+f_a)$, where $s_a$ = successes and $f_a$ = failures. Arm X: $\text{Beta}(1+4,1+0)=\text{Beta}(5,1)$. Arm Y: $\text{Beta}(1+1,1+3)=\text{Beta}(2,4)$. Why this step? Each success shifts the first parameter $\alpha$ up, each failure shifts the second parameter $\beta$ up; the posterior is our belief over $\mu$.
2. Posterior means. $\mathbb{E}[{\mu }_X]=\frac{5}{5+1}=0.833$; $\mathbb{E}[{\mu }_Y]=\frac{2}{2+4}=0.333$. Why this step? The mean is our point-guess; X currently looks much better.
3. Widths (variance). Beta variance $=\frac{\alpha \beta }{(\alpha +\beta {)}^2(\alpha +\beta +1)}$. For X: $\frac{5\cdot 1}{36\cdot 7}=0.0198$. For Y: $\frac{2\cdot 4}{36\cdot 7}=0.0317$. Y is wider (more uncertain). Why this step? Fewer effective samples on Y → broader belief.
4. Why Y still gets picked sometimes. Thompson samples ${\tilde{\mu }}_X\sim \text{Beta}(5,1)$ and ${\tilde{\mu }}_Y\sim \text{Beta}(2,4)$ each round and takes the larger. Y's wide posterior occasionally draws a high ${\tilde{\mu }}_Y>{\tilde{\mu }}_X$ — that's the exploration, and it self-throttles as Y gathers data. Why this step? No hand-set $ϵ$ or bonus — exploration falls straight out of the uncertainty. That is the elegance of probability matching.

Verify: means $5/6=0.8\overline{3}$ and $2/6=0.3\overline{3}$; variances $5/252\approx 0.01984$ and $8/252\approx 0.03175$, and $0.03175>0.01984$, so Y is wider. ✓

Read the figure below to see the exploration: the magenta curve is Arm X's posterior $\text{Beta}(5,1)$ — tall, narrow, and shoved up against $\mu =1$ (confident it's good). The orange curve is Arm Y's $\text{Beta}(2,4)$ — lower and much wider, its right tail stretching well past $\mu =0.5$. Because Thompson draws a random point under each curve and picks the arm with the larger draw, Y's fat right tail means it will occasionally out-sample X's peak — that overlap region (violet arrow) is precisely where Y gets re-explored.

---

Ex 7 — Cell C7 · real-world word problem (A/B test)

Forecast: magenta has the higher raw rate. Does UCB agree, or does equal sample size change the story?

1. Estimates. $Q_t(\text{mag})=30/200=0.15$; $Q_t(\text{ora})=24/200=0.12$. Why this step? Conversion rate is a reward mean — exactly the bandit setting, here $\mu =$ purchase probability.
2. Bonuses. Both have $N=200$, so both get the same bonus $2\sqrt{\frac{\ln 400}{200}}=2\sqrt{\frac{5.991}{200}}=2\sqrt{0.02996}=2(0.1731)=0.346$. Why this step? Equal sample sizes → equal uncertainty → the bonus cancels out in the comparison.
3. UCB scores. Magenta $=0.15+0.346=0.496$; orange $=0.12+0.346=0.466$. Why this step? With equal bonus, UCB reduces to greedy — the higher estimate wins.
4. Decision & caution. Show magenta. But note the gap $0.15-0.12=0.03$ is small vs the bonus $0.346$; the data is not yet conclusive, so UCB keeps testing both until one pulls clearly ahead — this is exactly guarding against over-fitting to a noisy early lead. Why this step? A real A/B test should not "call it" on a 30-vs-24 difference; the bonus encodes that statistical humility.

Verify: $0.496>0.466$, magenta chosen; both bonuses equal $0.346$ so they cancel and greedy order holds. ✓

---

Ex 8 — Cell C8 · exam twist, why the bound quietly breaks

Forecast: guess the odds — is uniform random exploration realistically ever going to find this?

1. Single-rollout success probability. Each step independently correct with prob $\frac{1}{10}$; twenty steps: ${\left(\frac{1}{10}\right)}^{20}=10^{-20}$. Why this step? Independent choices multiply; sparse rewards make the "target" a needle in a $10^{20}$ haystack.
2. Expected rollouts to first success. For a geometric event with per-trial success probability $p$, the mean number of trials until the first success is $1/p$. Here $1/p=10^{20}$. Why this step? This is astronomically more than any real training budget (a fast simulator doing $10^6$ rollouts a second would still need over $3$ million years) — success essentially never happens.
3. Why the $O(\log T)$ bound fails. That regret bound (with $T$ the total horizon) assumed a finite set of arms, each sampled directly and each with its own independently-estimable mean ${\mu }_a$. Here the "good arm" is a deep 20-step sequence, not a single pull-able action; uniform exploration almost never lands on it, so the estimates for the rewarding path never even begin to form. The bandit assumptions (each action independently learnable in $O(1)$ pulls) are violated, so the theorem simply does not cover this environment. Why this step? The exam trap is applying a clean theorem outside its hypotheses — always check that the assumptions actually hold.
4. The fix. Replace uniform exploration with a directed signal — an intrinsic novelty bonus $r_t=r_t^{\text{ext}}+\beta r_t^{\text{intrinsic}}$, where $r_t^{\text{ext}}$ is the environment's (sparse) reward, $r_t^{\text{intrinsic}}$ is large for unfamiliar states, and $\beta >0$ weights curiosity against real reward. This is curiosity-driven exploration: the agent is pulled toward unseen states rather than stumbling randomly. Why this step? When random exploration's success probability is $10^{-20}$, you must change what counts as interesting, not just how often you explore.

Verify: $(1/10{)}^{20}=10^{-20}$ and $1/(10^{-20})=10^{20}$; and $10^{20}/10^6=10^{14}$ seconds $\approx 3.17\times 10^6$ years, confirming "essentially never." ✓

---

Recall Self-test before you leave

Greedy's regret grows how, and why? ::: Linearly ($0.2T$ in Ex 1), because one unlucky sample locks it onto the worse arm and it never re-samples. When $N_t(a)=0$, what is UCB's bonus and what do we do? ::: $+\infty$; pull every arm once first so $Q_t$ is defined (Ex 2). Two arms tie on $Q$ — who does UCB pick? ::: The one with smaller $N_t(a)$, i.e. the less-sampled, more-uncertain arm (Ex 3). Why is $\ln t$ (not $t$) in the UCB bonus? ::: So the bonus $\to 0$ as samples grow, giving sublinear $O(\log T)$ regret instead of linear (Ex 4). What does the knob $c$ control in UCB? ::: How brave exploration is — bigger $c$ scales up the whole bonus term, smaller $c$ makes UCB act more greedily. Why does Thompson explore without any $ϵ$? ::: A wide posterior occasionally samples a high value, and it self-narrows as data arrives (Ex 6). Why does $ϵ$-greedy fail on Montezuma-style tasks? ::: Reward needs a deep sequence; uniform exploration hits it with prob $\approx 10^{-20}$, breaking the bandit assumptions (Ex 8).

Where to go next: the estimate $Q_t(a)$ used everywhere here is exactly what Q-learning learns online, built on temporal-difference updates; the bandit setup is formalised in multi-armed bandits; and when exploration must be directed by a learned objective, see policy-gradient methods.