Epsilon-greedy strategy: Worked examples — AI-ML deep dive

This is a deep-dive companion to Epsilon-greedy strategy. The parent note built the idea: flip a biased coin, exploit most of the time, explore sometimes. Here we grind through every kind of situation that idea can produce — every value of $ε$ , every degenerate input, the limits, and the traps an exam loves.

Before a single number: let us re-anchor every symbol we will use over and over, so no symbol appears un-earned.

Definition Every symbol, in plain words

$k$ = how many actions (arms) exist. If there are 3 slot machines, $k = 3$ .
$ε$ ("epsilon") = the probability of exploring, a number between $0$ and $1$ . $ε = 0.1$ means "explore 10 out of every 100 turns on average".
$Q (a)$ = ==our current running-average guess of the reward of action $a$ ==. It is a guess, not the truth.
$q_{*} (a)$ = the true (hidden) mean reward of action $a$ . We never see this directly; $Q (a)$ chases it.
$a^{*}$ = the optimal action: the single arm whose true reward $q_{*}$ is the highest of all. It is what we wish we always picked.
$Δ_{a}$ ("delta") = the ==reward gap of arm $a$ == $= q_{*} (a^{*}) - q_{*} (a)$ : how much reward we lose each time we pick $a$ instead of the best arm. For the best arm itself $Δ_{a^{*}} = 0$ .
$L$ = the expected per-step regret: the average reward we throw away on a single turn, $L = \sum_{a} Pr [pick a] Δ_{a}$ .
$T$ = the time horizon: the total number of turns (steps) we play. Cumulative regret over the whole run is $L \cdot T$ when $L$ is constant.

The single formula that generates every answer on this page:

The scenario matrix

Every situation epsilon-greedy can throw at you falls into one of these cells. The examples below are labelled with the cell they cover, and together they fill the whole grid.

Cell	Case class	What is special	Example
A	Ordinary fixed $ε$	$0 < ε < 1$ , estimates converged	Ex 1
B	Degenerate $ε = 0$	Pure greedy, no exploration	Ex 2
C	Degenerate $ε = 1$	Pure random, no exploitation	Ex 3
D	Single action $k = 1$	Nothing to explore	Ex 4
E	Tie in $Q$ -values	$ar g max$ ambiguous	Ex 5
F	Running-average update	Incremental $Q$ formula, step by step	Ex 6
G	Limiting behaviour	$t \to \infty$ , cumulative regret grows without bound	Ex 7
H	Decaying $ε$ schedule	$ε_{t} \to 0$ , policy becomes greedy	Ex 8
I	Real-world word problem	Translate a story into $k, ε, Δ$	Ex 9
J	Exam twist	"Solve for $ε$ given a target regret"	Ex 10

The figure below turns the "two doors" idea into a picture — study it before Example 1, because every example that follows is just re-counting these two coloured stacks.

Look at the chart: the blue block is the exploit door and sits only on the best arm $a_{2}$ ; the thin orange slivers are the explore door and appear on every arm equally. The best arm's total bar (blue + orange) rises above the dashed $1 - ε$ line — that little orange cap is exactly the $ε / k$ bonus explored in Example 1.

Worked examples

Explore door for the best arm. Explore happens with $ε = 0.2$ ; a uniform pick among $k = 4$ hits $a_{2}$ with $\frac{1}{4}$ . So this door contributes $0.2/4 = 0.05$ . This is the orange cap on the $a_{2}$ bar in the figure above. Why this step? We must count the explore path separately because even the best arm can be chosen by luck during exploration.
Exploit door for the best arm. Exploit happens with $1 - ε = 0.8$ , and since $a_{2}$ is estimated-best, this whole $0.8$ flows to it — the blue block in the figure. Why this step? The exploit door opens only for the current $ar g max$ ; here that is $a_{2}$ .
Add the doors. $Pr [a_{2}] = 0.8 + 0.05 = 0.85$ .
Each other arm. No exploit door (they are not the max), only explore: $Pr = 0.2/4 = 0.05$ each — the lone orange slivers.

Verify: total probability must be $1$ . $0.85 + 3 \times 0.05 = 0.85 + 0.15 = 1.0$ . ✓ Also $0.85 > 0.8$ — the best arm beats $1 - ε$ because exploration occasionally helps it too.

Find the estimated-best. $ar g max Q = a_{1}$ (value $2.0$ , others $0$ ). Why this step? Pure greedy always picks the current $ar g max$ , nothing else.
Check the explore door. With $ε = 0$ , $Pr [explore] = 0$ . That door is nailed shut. Why this step? Every alternative arm can only be reached by exploration; with none, they are unreachable.
Consequence. $Q (a_{2})$ and $Q (a_{3})$ stay stuck at $0$ forever; the agent replays $a_{1}$ every step.

Verify: $Pr [a_{2}] = (1 - ε) \cdot 1 [a_{2} = ar g max] + ε / k = 1 \cdot 0 + 0 = 0$ . The truly-best arm $a^{*}$ has probability exactly $0$ . This is the failure the whole strategy exists to prevent.

Kill the exploit door. $1 - ε = 0$ , so exploitation never happens. Every arm is chosen purely by the uniform explore pick $1/ k = 1/5 = 0.2$ . Why this step? With $ε = 1$ the $ar g max$ is irrelevant; $Q$ -values do not influence the choice.
Best-arm probability. $Pr [a^{*}] = 0.2$ , same as everyone. Why this step? Since the choice is now purely uniform, the best arm is just one of the $k$ equally-likely options — no exploit bonus can lift it.
Expected regret per step. $L = \sum_{a} \frac{1}{5} Δ_{a} = \frac{1}{5} (0 + 1 + 2 + 3 + 4) = \frac{10}{5} = 2.0$ . Why this step? Regret is the average lost reward, so weight each gap $Δ_{a}$ by its pick probability $0.2$ .

Verify: all probabilities sum to $5 \times 0.2 = 1.0$ ✓. Regret $2.0$ is the largest this bandit can produce — pure random is the worst exploiter, confirming exploration alone is not the goal.

Exploit door. With $1 - ε = 0.7$ we exploit; the only arm is the $ar g max$ , so it gets $0.7$ . Why this step? The exploit door always flows to the $ar g max$ ; with a single arm, that arm is trivially the maximum, so it collects the entire $1 - ε$ .
Explore door. With $ε = 0.3$ we explore, then uniform over $k = 1$ arms gives $1/1 = 1$ . So this door contributes $0.3 \times 1 = 0.3$ . Why this step? "Uniform random over one option" always returns that option — explore is not wasted, it just re-selects the same arm.
Add. $Pr = 0.7 + 0.3 = 1.0$ .

Verify: $ε / k = 0.3/1 = 0.3$ , and $(1 - ε) + ε / k = 0.7 + 0.3 = 1$ . With one arm the strategy is a no-op — a good sanity boundary.

Split the exploit door across the tie. Exploit probability $1 - ε = 0.9$ is shared equally by the two tied arms: each gets $0.9/2 = 0.45$ . Why this step? $ar g max$ returns a set here; a uniform tie-break shares the exploit mass.
Add $a_{1}$ 's explore door. $ε / k = 0.1/3 \approx 0.0333$ . Why this step? Exploration still visits every arm uniformly regardless of the tie, so $a_{1}$ collects its usual $ε / k$ on top of its half-share of the exploit door.
Total for $a_{1}$ . $0.45 + 0.0333 = 0.4833$ .

Verify: by symmetry $Pr [a_{1}] = Pr [a_{2}] = 0.4833$ , and $Pr [a_{3}] = 0.1/3 = 0.0333$ . Sum $= 2 (0.4833) + 0.0333 = 0.9667 + 0.0333 = 1.0$ ✓.

The incremental update (why it exists: it avoids storing every past reward): $Q_{n} = Q_{n - 1} + \frac{1}{n} (r_{n} - Q_{n - 1})$ Here $\frac{1}{n}$ is the step size, and $(r_{n} - Q_{n - 1})$ is the prediction error (how surprised we were).

Pull 1. $Q_{1} = 0 + \frac{1}{1} (1.2 - 0) = 1.2$ . Why this step? First reward becomes the estimate outright.
Pull 2. $Q_{2} = 1.2 + \frac{1}{2} (0.8 - 1.2) = 1.2 - 0.2 = 1.0$ . Why? Reward was below our guess, so the error is negative and $Q$ drops.
Pull 3. $Q_{3} = 1.0 + \frac{1}{3} (2.0 - 1.0) = 1.0 + 0.3333 = 1.3333$ .
Pull 4. $Q_{4} = 1.3333 + \frac{1}{4} (1.0 - 1.3333) = 1.3333 - 0.0833 = 1.25$ .

Verify: plain average $= (1.2 + 0.8 + 2.0 + 1.0) /4 = 5.0/4 = 1.25$ . ✓ The incremental rule reproduces the batch mean exactly — the same idea that powers 3.4.07-Stochastic-Gradient-Descent and value updates in 6.3.02-Q-Learning.

Suboptimal pick probabilities. Each non-best arm has $Pr = ε / k = 0.1/3 = 0.03333$ . Why this step? Once estimates converge, the exploit door flows entirely to $a^{*}$ , so every other arm is reachable only through the explore door's uniform $ε / k$ — that is exactly the probability that costs us regret.
Per-step regret. $L = 0.03333 \times 4.0 + 0.03333 \times 2.0 = 0.13333 + 0.06667 = 0.2$ . Why this step? Only suboptimal arms cost regret; weight each gap $Δ_{a}$ by its pick probability.
Cumulative over $T$ . Because $ε$ is fixed, $L$ is constant, so total regret $= L \cdot T = 0.2 \times 5000 = 1000$ . Why this step? A constant per-step loss added $T$ times grows linearly and never flattens.

Verify: $L = 0.2$ per step, cumulative $= 1000$ at $T = 5000$ . Linear (not bounded) regret is the signature weakness of fixed- $ε$ — the motivation for 5.1.09-Upper-Confidence-Bound and 5.1.10-Thompson-Sampling, which achieve sublinear regret.

Raw decay at $t = 100$ . $ε_{0} γ^{100} = 1.0 \times 0.9 9^{100}$ . Since $ln (0.99) \approx - 0.01005$ , $0.9 9^{100} \approx e^{- 1.005} \approx 0.3660$ . Why this step? Repeated multiplication by $γ$ is exponential decay; logs turn the power into a product we can estimate.
Compare to floor. $0.3660 > 0.01$ , so the $max$ returns the raw decay: $ε_{100} = 0.3660$ — floor not yet active. Why this step? The schedule takes whichever is larger, the decaying value or the floor $ε_{m i n}$ ; here the decay still dominates, so the floor has no effect yet.
When does the floor bite? Solve $γ^{t} = ε_{m i n}$ : $t = \frac{ln ε _{m i n}}{ln γ} = \frac{ln 0.01}{ln 0.99} = \frac{- 4.6052}{- 0.01005} \approx 458.2$ . Why this step? Set raw decay equal to the floor; beyond this $t$ the $max$ picks $ε_{m i n}$ .

Verify: $ε_{100} \approx 0.366$ ✓; floor engages at $t \approx 458$ . After that the policy explores only $1%$ , nearly greedy — and if $ε_{m i n}$ were $0$ the policy would converge to pure greedy, the only regime with vanishing regret. Trace this on the figure below.

In the figure the grey dashed curve is the raw exponential decay $ε_{0} γ^{t}$ ; the solid blue line is the actual $ε_{t}$ the agent uses, which hugs the decay until it flattens onto the red dotted floor. The orange dot marks $t = 100$ (still high, $\approx 0.37$ ); the green dot marks where decay meets the floor at $t \approx 458$ — exactly the value we solved for in step 3.

Explore visitors. A fraction $ε = 0.08$ of $T = 10, 000 = 800$ visitors are in explore mode. Why this step? Since estimates have converged, exploitation always shows C; exploration is the only channel that shows any non-C banner.
Split explore uniformly. Each arm gets $800/4 = 200$ explore visitors, including C itself. Why this step? The explore door picks uniformly over all $k = 4$ arms, so the 800 explore visitors divide equally — no arm is favoured during exploration, not even the best one.
Non-C total. The three non-C arms get $3 \times 200 = 600$ explore visitors. (C also gets $200$ explore + all $9200$ exploit visitors.) Why this step? "Non-best shown" = explore visitors that landed on the other three arms.
Banner A specifically. $ε / k \times T = 0.08/4 \times 10000 = 0.02 \times 10000 = 200$ . Why this step? Banner A is never the estimated-best, so it is reached only through the explore door with probability $ε / k$ ; multiply by the $T$ visitors to get a count.

Verify: non-C $= 600$ , banner A $= 200$ . Check totals: C exploit $9200$ + C explore $200 = 9400$ shown C; $9400 + 600 = 10000$ ✓. Under $800$ visitors touched non-best banners — the unavoidable cost of learning, echoing 5.2.04-Exploration-vs-Exploitation.

Write per-step regret. Only the suboptimal arm costs regret, with pick probability $ε / k = ε /2$ . So $L = \frac{ε}{2} \times 3.0 = 1.5 ε$ . Why this step? With $k = 2$ there is exactly one bad arm, reached only by exploration at rate $ε / k$ ; its gap $Δ = 3.0$ turns that probability into regret.
Set the budget. Require $1.5 ε \leq 0.05$ . Why this step? The boss's cap is a ceiling on $L$ ; we translate the requirement directly into an inequality on $ε$ .
Solve. $ε \leq 0.05/1.5 = 0.03333$ . Why this step? Divide both sides by the coefficient $1.5$ to isolate $ε$ ; the largest allowed value is the equality case $ε = 0.03333$ .

Verify: plug $ε = 0.03333$ back: $L = 1.5 \times 0.03333 = 0.05$ exactly ✓. So $ε_{m a x} \approx 0.0333$ — matching the boss's ceiling on the nose.

Recall

Recall Every cell in one line

Fixed $ε$ , $k$ arms — best-arm pick probability? ::: $(1 - ε) + ε / k$ $ε = 0$ and first sample was unlucky — does it recover? ::: No; the truly-best arm has probability $0$ forever (Cell B). $ε = 1$ on $k$ arms — probability of any specific arm? ::: $1/ k$ (pure random, Cell C). Single arm $k = 1$ — effect of $ε$ ? ::: None; probability is $1$ regardless (Cell D). Two-way tie in $Q$ , uniform break, $ε$ -greedy — exploit mass per tied arm? ::: $(1 - ε) /2$ (Cell E). Why does cumulative regret grow linearly for fixed $ε$ ? ::: Per-step regret $L$ is a positive constant; adding it $T$ times gives $L \cdot T$ (Cell G). To make the policy converge to pure greedy, what must $ε_{t}$ do? ::: Decay to $0$ over time (Cell H).