Epsilon-greedy strategy: Exercises — AI-ML deep dive

This page is a self-test. Each problem has a hidden solution — try it first, then reveal. Everything here builds on the parent note, and touches 5.1.01-Multi-armed-Bandits, 5.2.04-Exploration-vs-Exploitation and 6.3.02-Q-Learning.

The picture below is epsilon-greedy in one glance: the biased coin at the top, its two outcomes (exploit vs. explore), and where each branch's arrow lands among the $k$ arms. Trace the blue arrow (exploit → the tall estimated-best bar) and the pale-yellow arrows (explore → any bar, uniformly). Keep this diagram in mind for every probability we compute.

Two facts we reuse constantly. Keep them in view:

The next figure animates the incremental-average update as a staircase: each reward nudges the running guess $Q$ toward the sample, and the nudges shrink as $1/ n$ . This is exactly the update you will hand-compute in Exercise 2.1 — watch the blue dots climb toward the pink true-mean line.

Level 1 — Recognition

Exercise 1.1 (L1)

State, in plain words, what the two branches of the epsilon-greedy rule do, and give the probability of each branch when $ε = 0.1$ .

Recall Solution 1.1

Exploit branch (probability $1 - ε = 0.9$ ): pick the arm with the highest current estimate $Q (a)$ .
Explore branch (probability $ε = 0.1$ ): pick an arm uniformly at random, ignoring the estimates.

With $ε = 0.1$ : exploit $90%$ of the time, explore $10%$ of the time. (This is exactly the coin at the top of the first figure.)

Exercise 1.2 (L1)

A 4-armed bandit uses $ε = 0.2$ . Arm $a_{3}$ is currently the estimated best. What is $Pr [a_{3} chosen]$ ? What is $Pr [a_{1} chosen]$ (a non-best arm)?

Recall Solution 1.2

Here $k = 4$ , so the explore branch lands on any specific arm with probability $ε / k = 0.2/4 = 0.05$ .

Best arm $a_{3}$ : $(1 - ε) + \frac{ε}{k} = 0.8 + 0.05 = 0.85$ .
Non-best arm $a_{1}$ : $\frac{ε}{k} = 0.05$ .

Sanity check: probabilities sum to $0.85 + 0.05 + 0.05 + 0.05 = 1.0$ . ✓ (These are exact here — no rounding — because $0.05$ terminates in decimal. Contrast Exercise 2.2 where $1/3$ does not, so the digits are truncated.)

Exercise 1.3 (L1)

True or false: "With a fixed $ε = 0.1$ , the policy eventually always picks the best arm." Explain.

Recall Solution 1.3

False. Even after the estimates are perfect, the explore branch fires with probability $ε = 0.1$ forever. The best arm is chosen with probability $0.9 + 0.1/ k < 1$ , never $1$ . Only a decaying $ε \to 0$ makes the policy converge to pure greedy. (The estimates $Q$ converge either way — that is a different statement, drawn side-by-side in the third figure below.)

The two timelines below make this concrete side by side: left, the estimate $Q$ climbs and locks onto the true value (converges); right, the probability of picking the best arm rises but flattens at $(1 - ε) + ε / k$ , a dashed ceiling strictly below $1$ (does not converge to greedy).

Level 2 — Application

Exercise 2.1 (L2)

An arm has been pulled 3 times giving rewards $2, 4, 6$ . Compute $Q_{3}$ using the incremental average, showing every intermediate step. Start from $Q_{0} = 0$ .

Recall Solution 2.1

Use $Q_{n} = Q_{n - 1} + \frac{1}{n} (r_{n} - Q_{n - 1})$ .

$n = 1$ : $Q_{1} = 0 + \frac{1}{1} (2 - 0) = 2$ .
$n = 2$ : $Q_{2} = 2 + \frac{1}{2} (4 - 2) = 2 + 1 = 3$ .
$n = 3$ : $Q_{3} = 3 + \frac{1}{3} (6 - 3) = 3 + 1 = 4$ .

Check against the plain mean: $(2 + 4 + 6) /3 = 12/3 = 4$ . ✓ The incremental formula gives the same answer without storing all past rewards. This is the staircase in the second figure — each step's vertical jump is $\frac{1}{n} (r_{n} - Q_{n - 1})$ , getting smaller as $n$ grows.

Exercise 2.2 (L2)

A 3-armed bandit with $ε = 0.1$ . Estimates are $Q (a_{1}) = 1.1, Q (a_{2}) = 4.8, Q (a_{3}) = 2.9$ . Give the probability of selecting each arm on the next step.

Recall Solution 2.2

Estimated best is $a_{2}$ (highest $Q$ ). Here $k = 3$ , so $ε / k = 0.1/3 = 0.0333 \dots$

$Pr [a_{2}] = 0.9 + 0.0333 = 0.9333$
$Pr [a_{1}] = 0.0333 = 0.0333$
$Pr [a_{3}] = 0.0333 = 0.0333$

On the " $\approx$ " here: $1/3$ has no finite decimal, so $0.9333$ and $0.0333$ are truncated — the true values are $28/30$ and $1/30$ . If you add the truncated decimals you get $0.9333 + 0.0333 + 0.0333 = 0.9999$ , off by $1 0^{- 4}$ ; add the exact fractions and they sum to $28/30 + 1/30 + 1/30 = 30/30 = 1$ exactly. Always sum the fractions when checking normalization, never the rounded digits. ✓

Exercise 2.3 (L2)

With $ε = 0.1$ and $k = 3$ , over $1000$ steps roughly how many times is each non-best arm chosen through exploration alone?

Recall Solution 2.3

Each step, a specific non-best arm is chosen by exploration with probability $ε / k = 0.1/3 = 0.0333$ . Over $1000$ steps: $0.0333 \times 1000 \approx 33 times .$ (The best arm also gets these ~33 explore-visits plus ~900 exploit-visits.) The word "roughly" is honest: this is an expected count; the actual number is random and fluctuates by about $\pm 1000 \cdot \frac{1}{30} \cdot \frac{29}{30} \approx \pm 5.7$ (standard deviation of a binomial). So "33" really means "33 give or take a handful."

Level 3 — Analysis

Exercise 3.1 (L3)

Same 3-armed bandit: $q_{*} (a_{1}) = 1.0, q_{*} (a_{2}) = 5.0 (optimal), q_{*} (a_{3}) = 3.0$ , $ε = 0.1$ . Assume estimates have converged so $a_{2}$ is the estimated best. Compute the expected regret per step.

Recall Solution 3.1

Regret gap for each suboptimal arm: $Δ_{i} = q_{*} (a^{*}) - q_{*} (a_{i})$ .

$Δ_{1} = 5.0 - 1.0 = 4.0$ , with $Pr [a_{1}] = ε / k = 0.0333$ .
$Δ_{3} = 5.0 - 3.0 = 2.0$ , with $Pr [a_{3}] = 0.0333$ .

Expected regret per step: $L = \sum_{a \neq = a^{*}} Pr [a] \cdot Δ_{a} = 0.0333 \times 4.0 + 0.0333 \times 2.0.$ $L = 0.1333 + 0.0667 = 0.2 per step .$ Over $1000$ steps, cumulative regret $\approx 200$ . This never drops to $0$ for fixed $ε$ — it is the permanent cost of exploration.

Exercise 3.2 (L3)

For the same bandit, by how much does the expected regret per step change if we cut $ε$ from $0.1$ to $0.01$ ? Compute both and the ratio.

Recall Solution 3.2

Regret scales linearly with $ε$ because every suboptimal selection probability is $ε / k$ . Let $S = \sum_{a \neq = a^{*}} \frac{Δ _{a}}{k} = \frac{4.0 + 2.0}{3} = 2.0$ . Then $L (ε) = ε \cdot S$ .

$L (0.1) = 0.1 \times 2.0 = 0.2$ .
$L (0.01) = 0.01 \times 2.0 = 0.02$ .
Ratio $= 0.2/0.02 = 10 \times$ smaller.

The catch (analysis): regret dropped $10 \times$ , but each arm now gets explored $10 \times$ less often, so the estimates take $10 \times$ longer to become reliable. This is the exploration–exploitation dial in one number.

The figure below plots that linear relationship. The yellow line is $L (ε) = ε \cdot S$ ; the two marked points are the answers to this exercise — read off how the blue dot ( $ε = 0.1$ , $L = 0.2$ ) sits ten times higher than the pink dot ( $ε = 0.01$ , $L = 0.02$ ). Because the graph is a straight line through the origin, "cut $ε$ by $10 \times$ " always means "cut steady-state regret by $10 \times$ ."

Exercise 3.3 (L3)

Optimistic init vs. exploration: two arms, true means $q_{*} (a_{1}) = 1, q_{*} (a_{2}) = 2$ . A pure greedy agent ( $ε = 0$ ) initializes $Q_{0} (a_{1}) = Q_{0} (a_{2}) = 0$ , pulls $a_{1}$ first (tie broken to $a_{1}$ ), sees reward $1$ . Show it may get stuck on the wrong arm, and explain why $ε > 0$ would rescue it.

Recall Solution 3.3

After pulling $a_{1}$ once: $Q (a_{1}) = 1$ , $Q (a_{2}) = 0$ . Greedy now always picks $a_{1}$ (its estimate is higher). It never pulls $a_{2}$ , so $Q (a_{2})$ stays $0$ forever and the agent never learns that $q_{*} (a_{2}) = 2 > 1$ . It is stuck on the suboptimal arm.

With $ε > 0$ : the explore branch pulls $a_{2}$ with probability $ε /2$ each step, so eventually $Q (a_{2}) \to 2$ , overtakes $Q (a_{1})$ , and the agent switches. Exploration is what unsticks the greedy trap.

Level 4 — Synthesis

Exercise 4.1 (L4)

Decaying schedule. Use $ε_{t} = max (ε_{m i n}, ε_{0} γ^{t})$ with $ε_{0} = 1.0, γ = 0.99, ε_{m i n} = 0.01$ . Find the step $t$ at which the decaying term $ε_{0} γ^{t}$ first drops to or below $ε_{m i n}$ (i.e. the floor kicks in).

Recall Solution 4.1

We want the smallest $t$ with $ε_{0} γ^{t} \leq ε_{m i n}$ , i.e. $0.9 9^{t} \leq 0.01$ .

Why take $ln$ of both sides? The unknown $t$ is stuck in the exponent. The natural log is the tool that pulls an exponent down into a plain coefficient, because $ln (0.9 9^{t}) = t ln 0.99$ . That converts an awkward exponential inequality into a linear one in $t$ that we can just divide. And $ln$ is a strictly increasing function, so applying it to both sides keeps the inequality direction ( $x \leq y \Rightarrow ln x \leq ln y$ ): $t ln 0.99 \leq ln 0.01.$ Now the crucial sign step: $ln 0.99$ is a negative number (since $0.99 < 1$ ). Dividing an inequality by a negative number flips the direction, so: $t \geq \frac{l n 0.01}{l n 0.99} = \frac{- 4.6052}{- 0.01005} \approx 458.2.$ The smallest integer satisfying this is $t = 459$ — from then on $ε_{t}$ is pinned at $ε_{m i n} = 0.01$ .

Design reading: ~460 steps of aggressive early exploration, then a permanent $1%$ trickle to stay robust to a changing (non-stationary) environment.

Exercise 4.2 (L4)

Connecting to UCB/Thompson. In one sentence each, contrast how epsilon-greedy, UCB, and Thompson sampling decide which arm to explore, then argue why epsilon-greedy wastes exploration budget.

Recall Solution 4.2

Epsilon-greedy: explores by picking uniformly at random — no regard for uncertainty.
UCB: explores the arm with the largest optimistic bound $Q (a) + c ln t / n_{a}$ — deliberately targets arms it is most uncertain about.
Thompson: samples a plausible value from each arm's posterior and picks the max — probability-matched exploration.

Waste argument: epsilon-greedy spends the same $ε / k$ on an obviously terrible arm as on a promising, uncertain one. UCB and Thompson concentrate exploration where it is informative, so they achieve lower regret. Epsilon-greedy's flat regret $ε \cdot S$ per step is the price of that indiscriminate coin flip.

The schematic below shows this visually: three arms drawn with their uncertainty (the pale error bars). Epsilon-greedy's flat uniform arrows waste equal weight on the clearly-bad left arm; UCB's arrow points at the tallest optimistic bar (widest uncertainty on top of its estimate); Thompson draws a sample (the pink dots) from each arm's spread and picks whichever sample is highest — so its exploration automatically favors arms that could plausibly be best.

Exercise 4.3 (L4)

Q-learning link. In 6.3.02-Q-Learning with 7.1.05-Experience-Replay, epsilon-greedy is the behavior policy. Explain why we still want $ε > 0$ during training even though the target we compute is $max_{a} Q (s, a)$ (greedy).

Recall Solution 4.3

The target uses greedy $max_{a} Q$ because we want to learn the value of acting optimally. But if the behavior that collects data were also greedy, the replay buffer would fill with only the currently-favored actions, and states/actions the agent wrongly thinks are bad would never be visited — the same "stuck" trap as Exercise 3.3, now over a whole state space. A behavior $ε > 0$ keeps the buffer diverse, so the greedy target is estimated over the full action set. (This split — greedy target, exploratory behavior — is off-policy learning.)

Level 5 — Mastery

Exercise 5.1 (L5)

Full closed form. A $k$ -armed bandit with converged estimates uses fixed $ε$ . Let the gaps be $Δ_{i}$ for the $k - 1$ suboptimal arms. Derive the expected regret per step in closed form, then evaluate for $k = 5$ , $ε = 0.2$ , gaps ${1, 2, 2, 3}$ .

Recall Solution 5.1

Derivation. Once estimates are correct, the exploit branch always picks the optimal arm $a^{*}$ , so it contributes zero regret. Regret only comes from the explore branch, which lands on any specific arm with probability $ε / k$ . A suboptimal arm $a_{i}$ costs $Δ_{i} = q_{*} (a^{*}) - q_{*} (a_{i})$ each time it is chosen. Multiply probability by cost and sum over the $k - 1$ suboptimal arms: $L = \sum_{i \neq = a^{*}} Pr [a_{i}] \cdot Δ_{i} = \sum_{i \neq = a^{*}} \frac{ε}{k} Δ_{i} = \frac{ε}{k} \sum_{i \neq = a^{*}} Δ_{i} .$ The $ε / k$ factors out because every suboptimal arm shares the same explore probability — this is why regret is exactly linear in $ε$ .

Evaluate. Plug in $\sum_{i} Δ_{i} = 1 + 2 + 2 + 3 = 8$ and $ε / k = 0.2/5 = 0.04$ : $L = 0.04 \times 8 = 0.32 per step .$ Over $10, 000$ steps: cumulative regret $\approx 0.32 \times 10, 000 = 3200$ .

Exercise 5.2 (L5)

Optimal fixed $ε$ is a trade-off with a real minimum. Suppose (toy model) the regret per step has two competing parts: exploration cost $ε \cdot S$ (as above) plus a "slow-learning" penalty $c / ε$ that shrinks as you explore more. With $S = 2.0$ and $c = 0.5$ , find the $ε$ that minimizes total per-step cost $f (ε) = S ε + c / ε$ .

Recall Solution 5.2

Why a derivative? We want the bottom of a U-shaped cost curve — the $ε$ where cost stops falling and starts rising. At that flat bottom the slope (derivative) is exactly zero, so we compute $f^{'} (ε)$ and set it to $0$ .

Step 1 — differentiate. Write $f (ε) = S ε + c ε^{- 1}$ . Term by term: $\frac{d}{d ε} (S ε) = S$ , and $\frac{d}{d ε} (c ε^{- 1}) = - c ε^{- 2}$ . So $f^{'} (ε) = S - \frac{c}{ε ^{2}} .$

Step 2 — set to zero and solve for $ε$ .

\;\Rightarrow\; \varepsilon^2 = \frac{c}{S} \;\Rightarrow\; \varepsilon^\star = \sqrt{\frac{c}{S}}$$ (we take the positive root since $\varepsilon>0$). **Step 3 — confirm it is a minimum, not a maximum.** Take the second derivative: $$f''(\varepsilon) = \frac{d}{d\varepsilon}\!\left(-c\,\varepsilon^{-2}\right) = 2c\,\varepsilon^{-3} = \frac{2c}{\varepsilon^3}.$$ With $c>0$ and $\varepsilon>0$ this is **positive**, so the curve is concave-up (a valley) — the critical point is genuinely a **minimum**. ✓ **Step 4 — plug in numbers.** $\varepsilon^\star = \sqrt{0.5/2.0} = \sqrt{0.25} = \mathbf{0.5}$, and the minimum cost is $f(0.5) = 2.0(0.5) + 0.5/0.5 = 1.0 + 1.0 = \mathbf{2.0}$. **Reading:** too small $\varepsilon$ → the $c/\varepsilon$ penalty (slow learning) blows up; too large → the $S\varepsilon$ term (wasteful pulls) blows up. The sweet spot balances them.

Exercise 5.3 (L5)

Convergence of the selection probability. For fixed $ε$ and $k$ arms, once estimates are correct, write $lim_{t \to \infty} Pr [a_{t} = a^{*}]$ and prove it is strictly between $1 - ε$ and $1$ for any $0 < ε < 1$ , $k \geq 2$ .

Recall Solution 5.3

$lim_{t \to \infty} Pr [a_{t} = a^{*}] = (1 - ε) + \frac{ε}{k} .$

Greater than $1 - ε$ : the extra term $ε / k > 0$ (since $ε > 0$ , $k$ finite), so the limit exceeds $1 - ε$ .
Less than $1$ : $(1 - ε) + ε / k = 1 - ε (1 - 1/ k) = 1 - ε \frac{k - 1}{k}$ . For $k \geq 2$ and $ε > 0$ , the subtracted term $ε \frac{k - 1}{k} > 0$ , so the value is strictly below $1$ .

Hence $1 - ε < Pr [a_{t} = a^{*}] < 1$ . The best arm is favored but never certain — the exact statement of "fixed $ε$ explores forever."

Recall Self-test checklist

Fixed epsilon: does the policy converge to greedy? ::: No — only estimates converge; policy keeps exploring at rate $ε$ . Probability a non-best arm is chosen? ::: $ε / k$ . Probability the estimated-best arm is chosen? ::: $(1 - ε) + ε / k$ . Steady-state regret per step? ::: $\frac{ε}{k} \sum_{i \neq = a^{*}} Δ_{i}$ . Why can pure greedy get stuck? ::: It stops pulling an arm after one bad sample, so that arm's estimate never corrects. Condition for decaying $ε$ to still guarantee convergence? ::: Each arm pulled infinitely often, e.g. $\sum_{t} ε_{t} = \infty$ .