Epsilon-greedy strategy: Visual walkthrough — AI-ML deep dive

We are inside a multi-armed bandit problem: several levers, each pays out coins, and you don't know which lever is best. Let's start there.

Step 1 — What a bandit even is

WHAT. Picture $k$ slot machines (we say "arms"). Pulling arm number $i$ spits out a random number of coins. We call one number of coins a reward, written $r$ .

WHY start here. Every symbol later ( $Q$ , $q_{*}$ , $ε$ ) is a statement about rewards. If reward is fuzzy, everything downstream is fuzzy. So we nail it first.

PICTURE. Below: three arms. Each has a hidden coin-cloud — the spread of rewards it could give. The dashed vertical line is the arm's true average payout.

In the figure the true values are $q_{*} (a_{1}) = 1$ , $q_{*} (a_{2}) = 5$ , $q_{*} (a_{3}) = 3$ . Arm $a_{2}$ is best. You cannot see these dashed lines. You only see coins.

Step 2 — Guessing the true value: the estimate $Q$

WHAT. Since you can't see $q_{*} (a)$ , you estimate it: pull arm $a$ a bunch of times, average what came out. That running average is $Q (a)$ .

WHY average. If each pull is a noisy sample of the same hidden mean, averaging cancels the noise — this is the same idea as why more samples give steadier estimates. One coin lies; a hundred coins tell the truth.

PICTURE. Watch $Q (a_{2})$ (the estimate, orange) bounce around wildly with 2 pulls, then settle onto the true dashed line as pulls pile up.

Key fact, straight from the picture: as $n_{a}$ grows, $Q (a) \to q_{*} (a)$ . But only for arms you actually keep pulling. An arm you abandon freezes its $Q$ at a bad guess. Hold that thought.

Step 3 — Why pure greedy walks into a trap

WHAT. The "greedy" rule: always pull whichever arm has the biggest $Q$ right now. $ar g max_{a} Q (a)$ means "the arm $a$ that maximises $Q$ " — it returns the arm, not the value.

WHY it fails. Suppose your very first pulls were unlucky on the truly-best arm and lucky on a mediocre arm. Greedy locks onto the mediocre arm, never pulls the good one again, so its frozen $Q$ never gets corrected. You are trapped.

PICTURE. Two timelines. Top (greedy): a lucky early sample on $a_{1}$ makes $Q (a_{1})$ look best, greedy stays on $a_{1}$ forever, $a_{2}$ (truly best) is abandoned with a stale low estimate — red X. Bottom (what we want): keep sampling $a_{2}$ , its estimate climbs to the truth.

The fix must force every arm to keep getting pulled. Enter $ε$ .

Step 4 — The biased coin: introducing $ε$

WHAT. Before each pull, flip a biased coin. With probability $ε$ we ignore all our estimates and pick an arm uniformly at random (explore). With probability $1 - ε$ we do the greedy thing (exploit).

WHY a coin. We want mostly smart choices but a guaranteed trickle of random tries so no arm is ever fully abandoned. A biased coin is the simplest gadget that mixes "mostly A, sometimes B" in a controllable ratio.

PICTURE. A probability bar of total length 1, split into a big $1 - ε$ "exploit" chunk and a thin $ε$ "explore" chunk. The explore chunk is then sliced into $k$ equal slivers — one per arm.

Step 5 — The probability of picking any one arm

WHAT. Let's compute the exact chance a given arm gets pulled on this step. There are only two ways an arm gets chosen, and they can't both happen on the same flip:

We explored (chance $ε$ ) and the random draw landed on this arm (chance $\frac{1}{k}$ ). Combined: $ε \cdot \frac{1}{k}$ .
We exploited (chance $1 - ε$ ) and this arm is the current estimated-best.

WHY multiply then add. "Explore AND land here" → the two conditions must both hold → multiply. "Exploit-path OR explore-path" → mutually exclusive routes to the same arm → add. That is all the probability we use.

PICTURE. A tree: root splits into explore ( $ε$ ) and exploit ( $1 - ε$ ); explore fans into $k$ equal twigs each worth $ε / k$ ; exploit points at the single best-looking arm. The chosen arm collects contributions from the twigs it touches.

Because every arm keeps its $ε / k$ trickle forever, $n_{a} \to \infty$ for all $a$ , so by Step 2 every $Q (a) \to q_{*} (a)$ . The estimates become correct.

Step 6 — What converges, and what does NOT

WHAT. Once estimates are correct, the estimated-best arm equals the truly-best arm $a^{*}$ . Plug $a = a^{*}$ into Step 5's formula: its indicator is now $1$ , so

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

WHY this is not 1. Even with perfect knowledge, on every explore-flip we might randomly pick a bad arm. That thin $ε$ sliver never closes. So the estimates converge, but the policy never becomes perfect — it keeps making the same small mistake forever.

PICTURE. Two curves vs. time. The estimate error $∣ Q - q_{*} ∣$ (violet) sinks to zero. The policy's chance of the optimal arm (magenta) rises and then flatlines at $(1 - ε) + ε / k$ — a permanent ceiling below 1, drawn as a dashed orange line.

For our 3-arm example with $ε = 0.1$ , $k = 3$ : $Pr [a_{t} = a^{*}] = 0.9 + \frac{0.1}{3} = 0.9 \overline{3} \approx 0.933.$ So even a perfect $ε$ -greedy learner pulls the best arm only 93.3% of the time. This gap is the topic of exploration vs exploitation, and the reason UCB and Thompson sampling exist.

Step 7 — The permanent price: expected regret

WHAT. Each time you pull a worse arm $a$ , you forfeit some reward compared to the best arm. That shortfall is the gap $Δ_{a} = q_{*} (a^{*}) - q_{*} (a)$ . The average shortfall per step, once estimates are good, is

$L = \sum_{a \neq = a^{*}} ε / k Pr [a_{t} = a] \cdot how much worse Δ_{a} .$

WHY it never hits zero. Each suboptimal arm keeps its $ε / k$ pull-rate forever (Step 5), and each such pull costs $Δ_{a} > 0$ . Fixed $ε$ ⇒ permanent, non-zero cost.

PICTURE. Bars for $a_{1}, a_{3}$ : bar height = $Δ_{a}$ , bar width = $ε / k$ ; the coloured area of each bar is its per-step regret. Their total area is $L$ .

Plugging numbers ( $Δ_{1} = 4$ , $Δ_{3} = 2$ , each with prob $0.1/3 = 0.033 \overline{3}$ ): $L = 0.033 \overline{3} \times 4 + 0.033 \overline{3} \times 2 = 0.1 \overline{3} + 0.0 \overline{6} = 0.2.$ Over 1000 steps that's a cumulative regret of ≈200 reward — the tax you pay to never be trapped. To lower it you must decay $ε \to 0$ (next step), which is exactly the tuning Q-learning agents do.

Step 8 — The degenerate and edge cases

WHAT. Let's stress-test the formula at its extremes so no scenario surprises you.

Case	$ε$	What happens	From the formula
Pure greedy	$0$	Can get trapped (Step 3); $Pr [a^{*}]$ is $0$ or $1$ depending on luck	$Pr [a] = 1 [a = ar g max Q]$
Pure random	$1$	Ignores learning; every arm equally likely	$Pr [a] = \frac{1}{k}$
One arm ( $k = 1$ )	any	Nothing to explore; forced choice	$Pr [a] = (1 - ε) + ε = 1$
Tie in $Q$	any	$ar g max$ picks one (implementation's choice) — break ties randomly!	exploit mass goes to the chosen one
Decaying	$ε_{t} \to 0$	Policy does converge to greedy, regret $\to 0$	ceiling $(1 - ε_{t}) + ε_{t} / k \to 1$

WHY decay fixes the ceiling. As $ε_{t} \to 0$ , the explore sliver $ε_{t} / k \to 0$ and $(1 - ε_{t}) \to 1$ , so $Pr [a_{t} = a^{*}] \to 1$ : the ceiling rises to the top. The rule is $ε_{t} = max (ε_{m i n}, ε_{0} γ^{t}),$ with $ε_{0} = 1$ (explore hard early), $γ$ near $0.999$ (slow fade), and a floor $ε_{m i n}$ kept small-but-positive if the world can change (non-stationary settings).

PICTURE. Three $ε$ -vs-time curves: fixed $0.1$ (flat), pure decay to $0$ (drops through the floor), and floored decay (levels off at $ε_{m i n}$ ).

The one-picture summary

Everything at once: the biased coin splits each step into explore/exploit; exploit picks the tall $Q$ bar; explore sprinkles $ε / k$ onto every bar; the estimates climb to the true dashed lines; and the leftover $ε$ -sliver on bad arms is the permanent regret area.

Recall Feynman retelling — say it back in plain words

We've got a row of slot machines and no idea which one is best. Each machine has a true average payout we can never see (Step 1), so we guess it by averaging the coins we've collected from it (Step 2). Trouble: if we always chase our current-best guess, one lucky early spin can fool us and we quit trying the real winner forever (Step 3). Cure: before every spin we flip a lopsided coin — nine times in ten do the smart thing, one time in ten pick a machine at random (Step 4). That random trickle guarantees every machine keeps getting sampled, so every guess eventually snaps onto its true value. Working out the exact chance of picking a machine is just "explore-and-land-here plus exploit-if-it-looks-best" (Step 5). The happy news: our guesses become correct. The catch: because that one-in-ten random flip never stops, we still pick a dud sometimes, so we're right only 93.3% of the time — and each dud pull costs us the gap between it and the best, adding up to a steady, unavoidable "regret tax" (Steps 6–7). Push $ε$ to zero over time and that tax fades to nothing (Step 8). That's $ε$ -greedy, whole.

Recall

Why is $Pr [a_{t} = a^{*}] = (1 - ε) + ε / k$ and not just $1 - ε$ ? ::: Because on an explore-flip you can still randomly land on the best arm; that adds an extra $ε / k$ on top of the exploit mass. With $ε = 0.1, k = 3$ , how often does a perfect learner pick the best arm? ::: $0.9 + 0.1/3 = 0.933$ , i.e. 93.3%. What single change makes the policy (not just the estimates) converge to optimal? ::: Decay $ε \to 0$ over time. Why does fixed- $ε$ regret never reach zero? ::: Every suboptimal arm keeps a permanent $ε / k$ pull-rate, and each such pull costs $Δ_{a} > 0$ .