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

This page assumes you have seen none of the notation in the parent note. We build every symbol, one at a time, each from the picture it stands for, so that when you re-read the parent note every squiggle already means something.

The story before the symbols

You sit in front of several buttons. Press a button, a coin-machine spits out some reward (money, points, dopamine). Each button has its own hidden average payout. You cannot see the averages — you can only see what came out this press. Your job: over many presses, collect as much as possible.

That is the whole setting. Every symbol below is just a careful name for one piece of this picture. This setting is the multi-armed bandit problem.

Symbol 1 — an action $a$ , and the set of all of them $A$

The picture: one button in the row above. Pressing it is taking the action.

Read this aloud: " $A$ is the set containing $a_{1}$ , $a_{2}$ , up to $a_{k}$ ." The curly braces ${}$ always mean "the set of things listed inside."

Why the topic needs it. Epsilon-greedy has to choose among options. You can't talk about choosing until you've named the pile of things to choose from.

Symbol 2 — how many actions, $k$ (and $∣ A ∣$ )

The vertical bars $∣ A ∣$ mean "the size of the set $A$ " — count its members. So $∣ A ∣ = k$ . Same idea, two notations.

Why the topic needs it. When epsilon-greedy explores "at random," it picks one out of $k$ buttons with equal chance. That equal chance is $\frac{1}{k}$ , and you can't write $\frac{1}{k}$ without $k$ .

Symbol 3 — reward $r$ , and the true average $q_{*} (a)$

But one press is noisy — the same button gives different $r$ each time. What we really care about is the button's long-run average.

The picture: each button has a secret dial set to its true average. In the figure above those secret dials are the shaded bars — you the player never see them.

Why the topic needs it. "Best button" means the one with the highest $q_{*}$ . Exploration only matters because $q_{*}$ is hidden from us.

Symbol 4 — our estimate $Q (a)$ and $Q_{t} (a)$

We can't see $q_{*} (a)$ . So we keep our own running guess.

Two Q's, remember the difference:

Which Q is the hidden truth we can never see?

q_{*} (a)

(little q, with a star)

Which Q is the guess we build from data?

Q (a)

(big Q, no star)

The subscript $t$ in $Q_{t} (a)$ just tags time: $Q_{t} (a)$ = our guess after $t$ presses total. As time $t$ grows, the guess improves. So $Q (a)$ and $Q_{t} (a)$ are the same notebook — we write the bare $Q (a)$ when the moment in time doesn't matter, and add the $t$ (as $Q_{t} (a)$ ) exactly when we need to point at "the guess at that particular turn."

The figure below shows exactly this improvement. Read it as one story: the green dots are the raw rewards $r$ you saw press by press for a single button (they scatter wildly — one press tells you little). The purple curve is $Q_{t} (a)$ , the running average of all green dots seen so far; watch it wobble a lot early (few samples) then steady. The red dashed line is the hidden truth $q_{*} (a) = 5$ you never see. The whole point of the picture: as the press-count $n_{a}$ grows left-to-right, the purple $Q_{t}$ crawls onto the red $q_{*}$ . That is the definition of $Q_{t} (a)$ in action — a guess made of averaged rewards, tightening toward the dial with time.

Why the topic needs it. Epsilon-greedy's "exploit" move is "press the button with the biggest $Q$ ." So $Q$ is the thing the whole strategy stares at.

Symbol 5 — the average that builds $Q$

How do we turn observed rewards into $Q_{t} (a)$ ? Just average them.

Unpacking the new marks:

$n_{a}$ = the count of how many times button $a$ was pressed up to time $t$ (" $n$ for number, subscript $a$ = for that button").
$\sum_{i = 1}^{n_{a}}$ = the summation sign. The big Greek $Σ$ (sigma) says "add up." The $i = 1$ underneath and $n_{a}$ on top say "let $i$ walk from 1 to $n_{a}$ ." So $\sum_{i = 1}^{n_{a}} r_{i}$ means $r_{1} + r_{2} + \dots + r_{n_{a}}$ .
Multiplying the total by $\frac{1}{n _{a}}$ divides by how many there were → that's the average.

(Whenever the exact turn doesn't matter we'll drop the $t$ and just write $Q (a)$ — same quantity.)

Why the topic needs it. This averaging is why trying an action more often makes its $Q$ trustworthy — the engine behind "explore to learn." And it forces us to say what happens on step zero, before any data exists.

Symbol 6 — argmax, picking the winner (and breaking ties)

Break the word: max = the biggest value; arg = "argument," i.e. which input produced it. So argmax = "which button gives the max."

The little $a \in A$ underneath reads "for $a$ ranging over the set $A$ " — check every button.
Picture: line up the bars of $Q_{t}$ ; argmax is your finger pointing at the tallest bar.

Why the topic needs it. "Exploit = pick current best" is literally "press $ar g max_{a} Q_{t} (a)$ " — and without a tie rule, step one (all-zero $Q$ ) has no defined answer.

Symbol 7 — probability $Pr [\cdot]$ and the parameter $ε$

The picture: a biased coin. It lands "explore" a fraction $ε$ of the time and "exploit" the remaining fraction $1 - ε$ .

Worked example The two boundary cases — the edges of the

$[0, 1]$ range Because $ε$ is allowed to be any value in $[0, 1]$ , it's worth seeing what happens at the two extreme ends, since each turns epsilon-greedy into a completely different (and usually bad) algorithm:

$ε = 0$ — pure greedy. The explore slice vanishes; every turn you press $ar g max_{a} Q_{t} (a)$ . You never try a button you dismissed early, so a truly-best button you were unlucky with on turn one can stay hidden forever. Maximum earning, zero learning.
$ε = 1$ — pure random. The exploit slice vanishes; every turn is a blind dart at the pie, each button with chance $\frac{1}{k}$ , and your carefully-built $Q_{t}$ is ignored. You learn everything but earn nothing better than chance.

Every useful setting is strictly between these edges — enough exploration to learn, enough exploitation to cash in. That balance is the whole subject of Exploration vs Exploitation.

Why the topic needs it. $ε$ is the knob epsilon-greedy is named after. Everything — regret, convergence, tuning — is a story about this one number.

Symbol 8 — the indicator $1 [\cdot]$ and the gap $Δ_{a}$

Example: $1 [a^{*} = ar g max_{a} Q_{t} (a)]$ is $1$ exactly when our current-best guess happens to be the truly-best button, else $0$ . It's the tidy way to say "count this term only when it applies."

Why the topic needs it. The policy formula must say "add the exploit-probability only for the one button that is currently best, and add nothing for the rest." The indicator is exactly that switch: it flips the $(1 - ε)$ term on for the argmax button and off for every other button, letting us write the whole rule as one clean line instead of a two-way if/else.

Picture: the height difference between the best dial and button $a$ 's dial. For the best button itself $Δ_{a^{*}} = 0$ (no regret). For a bad button, a tall gap.

Why the topic needs it. Regret — the running cost of exploring — is built by multiplying each button's gap $Δ_{a}$ by how often you press it. No $Δ$ , no way to measure the price of learning.

Gluing it all together — the policy $π_{t} (a)$

Now that every symbol exists, we can write the whole algorithm in one line. A policy $π_{t} (a)$ (Greek pi, no relation to $3.14$ ) is simply the probability that the epsilon-greedy rule presses button $a$ on turn $t$ .

Before the formula, one tiny housekeeping symbol. Inside the argmax we need a name for "some button we're scanning over," and we already used $a$ for the button in question — so we use a fresh letter $b$ purely as a dummy scanning index: $b$ just walks over all buttons in $A$ so we can find the tallest $Q_{t}$ . It stands for no particular button; it's a loop variable, and once the scan finds the winner, $b$ is done.

Reading the coin from Symbol 7 and the argmax from Symbol 6:

Read it left to right using the symbols you now own:

Explore branch $ε \cdot \frac{1}{k}$ : with probability $ε$ (Symbol 7) we ignore the notebook and throw a dart at the $k$ -slice pie (Symbol 2), landing on button $a$ with chance $\frac{1}{k}$ . Every button gets at least this slice — that's the guarantee that no button is ever abandoned.
Exploit branch $(1 - ε) \cdot 1 [a = ar g max_{b \in A} Q_{t} (b)]$ : with the leftover probability $1 - ε$ we press the current-best button (Symbol 6). The scan-index $b$ ranges over all buttons to locate the top $Q_{t}$ ; the indicator $1$ (Symbol 8) is a switch: it is $1$ only for the argmax button and $0$ for everyone else, so this whole term is $0$ for non-best buttons and $1 - ε$ for the best one.

Two sanity checks a novice can run:

The best button (when it is also the estimated best) gets $π_{t} (a^{*}) = ε \frac{1}{k} + (1 - ε)$ — most of the pie, but never all of it.
Any other button gets just $π_{t} (a) = ε \frac{1}{k}$ — a thin but non-zero slice, forever.

And the slices add up to a whole pie: one best button at $(1 - ε) + \frac{ε}{k}$ plus $(k - 1)$ others each at $\frac{ε}{k}$ sums to exactly $1$ . That is the parent note's action-selection formula — now every piece of it is a symbol you defined.

How the pieces feed the topic

The map below is just the reading order of this page, drawn as arrows. Trace it top to bottom: the top boxes are raw setup, arrows point from a symbol to whatever symbol uses it, and everything funnels into the final policy box. Read each arrow as "feeds into."

Walking the arrows in words: buttons ( $A$ ) give you both a count $k$ and, per press, a reward $r$ . Rewards do two jobs — they define the hidden truth $q_{*}$ , and they get averaged into the estimate $Q$ . The estimate feeds argmax (who's currently best). Argmax plus the explore rate $ε$ glue into the one-line policy $π$ . Finally the policy and the hidden truth together produce the gap/regret $Δ$ . Every box is a symbol you met above; the topic sits where all arrows meet.

Where these symbols go next

The same $Q$ and averaging reappear in Q-Learning, where $Q$ depends on both a state and an action.
The explore-vs-exploit tension is the whole subject of Exploration vs Exploitation.
Smarter answers to the same bandit picture are UCB and Thompson Sampling — they replace the blind coin with a cleverer choice.
Averaging rewards toward a hidden target echoes Stochastic Gradient Descent, and the "keep old experiences" idea grows into Experience Replay.

Equipment checklist

Cover the right side; can you answer each before reading on?

What does

A = {a_{1}, \dots, a_{k}}

stand for?

The set of all

k

actions (buttons) you may choose from.

What is

k

The number of available actions;

k = ∣ A ∣

Difference between

q_{*} (a)

and

Q (a)

q_{*} (a)

is the true hidden average reward;

Q (a)

is our data-built guess of it.

What does the subscript

t

Q_{t} (a)

add?

It tags the moment in time — the guess after $t$ presses; same notebook as

Q (a)

How is

Q_{t} (a)

computed from rewards?

Average the observed rewards:

Q_{t} (a) = \frac{1}{n _{a}} \sum_{i = 1}^{n_{a}} r_{i}

What breaks when

n_{a} = 0

, and how do we fix it?

The average divides by zero (undefined); fix by initializing

Q_{0} (a)

(zero or optimistic) before any press.

What does

\sum_{i = 1}^{n_{a}} r_{i}

mean?

Add the rewards

r_{1}

through

r_{n_{a}}

together.

What does

ar g max_{a} Q_{t} (a)

return — a value or an action?

An action: the button owning the largest

Q_{t}

How do you break an argmax tie?

Pick uniformly at random among the tied top buttons (or lowest-index by convention).

What is

ε

and its range?

The exploration rate, a probability in

[0, 1]

What does

ε = 0

do, and what does

ε = 1

do?

ε = 0

is pure greedy (never explores);

ε = 1

is pure random (ignores

Q_{t}

Why is the exploit probability

1 - ε

The two coin outcomes must sum to 1, so exploit gets the leftover.

What is the dummy index

b

ar g max_{b} Q_{t} (b)

A scanning loop variable ranging over all buttons to find the tallest

Q_{t}

; not any particular button.

What does the one-line policy

π_{t} (a)

equal?

ε \frac{1}{k} + (1 - ε) 1 [a = ar g max_{b \in A} Q_{t} (b)]

What is the chance of picking any one button while exploring?

\frac{1}{k}

(uniform over

k

buttons).

What does

1 [condition]

equal?

1

if the condition is true,

0

otherwise.

What is

Δ_{a}

and when is it zero?

Δ_{a} = q_{*} (a^{*}) - q_{*} (a)

, the reward lost by choosing

a

; it is

0

for the best action

a^{*}