Epsilon-greedy strategy: Question bank — AI-ML deep dive

Recall the vocabulary before you start:

Time step $t$ — the counter of how many actions the agent has taken so far. $t = 0$ is before any pull, $t = 1, 2, 3, \dots$ after each one. Anything written "per step" happens once per increment of $t$ .
$ε$ (epsilon) — the probability of ignoring your current best guess and picking a random action. A number between $0$ and $1$ . When it changes over time we write $ε_{t}$ .
$Q (a)$ — your running average of rewards seen so far for action $a$ ; your estimate of how good $a$ is.
$q_{*} (a)$ — the true average reward of $a$ , which you never see directly.
$a^{*}$ — the genuinely best action (highest $q_{*}$ ).
$k$ — how many actions (arms) exist.

Read the figure before answering anything below — it is the mental picture behind half these traps. The horizontal axis lists the three arms $a_{1}, a_{2} = a^{*}, a_{3}$ ; the vertical axis is true value $q_{*} (a)$ . The tall cyan bars are the true values ( $1, 5, 3$ ). The dashed amber line at height $5$ marks the best arm's level $q_{*} (a^{*})$ . Each double-headed amber arrow from a bar's top up to that line is the gap $Δ_{a}$ — so $a_{1}$ 's arrow spans $4$ and $a_{3}$ 's spans $2$ , while $a^{*}$ touches the line and has $Δ = 0$ . The caption formula reminds you that per-step regret $L$ is those arrow-lengths weighted by how often the policy plays each arm: a long arrow played rarely (small $ε / k$ ) still leaks a little reward every step, which is exactly why fixed- $ε$ regret never hits zero. Keep the picture in view: whenever a prompt says "regret", picture the amber arrows; whenever it says "which arm is played", picture the weights.

True or false — justify

The estimates

Q

converge to true values, but the policy keeps exploring forever with fixed

ε

True. Because

ε > 0

forces every action to be sampled infinitely often, each

Q (a) \to q_{*} (a)

; but the coin still lands "explore" a fraction

ε

of the time, so the policy never becomes purely greedy.

With fixed

ε = 0.1

the agent eventually plays the optimal arm 100% of the time.

False. Once estimates are accurate it plays

a^{*}

with probability

1 - ε + ε / k = 0.9 + 0.1/ k

, which is strictly below

1

for any finite

k

— the leftover

ε (1 - 1/ k)

is spent on worse arms forever.

Setting

ε = 0

turns epsilon-greedy into the pure greedy policy.

True. With no exploration coin, the agent always plays

ar g max_{a} Q (a)

; this is exactly greedy and can lock onto a lucky-but-wrong first sample forever.

Setting

ε = 1

makes the agent ignore its

Q

estimates entirely.

True. Every step explores uniformly at random, so the values are still learned but never used — pure exploration, worst possible reward but fastest, most uniform data collection.

Decaying

ε_{t} \to 0

automatically lets the policy converge to optimal, no matter how fast it decays.

False. It must decay slowly enough that every arm is still sampled infinitely often; the standard condition is

\sum_{t} ε_{t} = \infty

(exploration mass never runs out) together with

ε_{t} \to 0

(so exploration eventually vanishes). A schedule like

ε_{t} = 1/ t

satisfies both; a too-fast decay such as

ε_{t} = 1/ t^{2}

has

\sum_{t} ε_{t} < \infty

, meaning only finitely much total exploration, so some arm may never be adequately sampled.

Cumulative regret under fixed

ε

grows without bound.

True. Each step pays a fixed expected per-step regret

L > 0

(the constant exploration cost), so

Regret (T) \approx L T

grows roughly linearly in the number of steps

T

and never plateaus.

A larger

ε

always gives worse long-run reward.

False in general. Larger

ε

costs more after convergence, but it finds the true best arm faster; in a hard or non-stationary problem a bigger

ε

can win overall by not getting stuck.

Epsilon-greedy needs to know the true rewards

q_{*}

to run.

False. It only ever uses the observed averages

Q

; the true

q_{*}

(and hence the gaps

Δ_{a}

) appear only in our analysis of regret, never inside the algorithm.

The exploration step is uniform over all actions, including the current best.

True. On an explore step you pick uniformly from all

k

arms, so the best arm can be re-picked by luck — that is why its selection probability is

1 - ε + ε / k

, not just

1 - ε

Spot the error

"On an explore step, pick uniformly among the non-best arms." — where's the flaw?

Standard epsilon-greedy explores over all

k

arms, best included, so the best arm's probability is

1 - ε + ε / k

and each worse arm's is

ε / k

. The described "exclude-best" variant instead gives the best arm exactly

1 - ε

and each of the other

k - 1

arms

ε / (k - 1)

— a legitimate but non-standard scheme, not the default.

"I explore with probability

ε

, so the best arm is chosen with probability exactly

1 - ε

." — fix it.

You forgot that exploration can also land on the best arm. Correct probability is

1 - ε + ε / k

; the missing

ε / k

is the explore-hits-best case.

"To save time I'll only update

Q

when I exploit, not when I explore." — what breaks?

Then exploration gathers data you throw away, defeating its whole purpose. You must update

Q (a)

after every pull, exploit or explore, or estimates never improve for the arms you only reach by exploring.

"Since

Q

converges, expected per-step regret converges to

0

with fixed

ε

." — error?

Q

converging does not make

L

vanish. Even with perfect estimates the policy still throws

ε (1 - 1/ k)

of its steps at worse arms (positive gaps

Δ_{a}

), so per-step regret settles at a positive constant, not zero.

ε = 0.001

is safest because it maximises reward." — why is this a trap?

With tiny

ε

each non-greedy arm is sampled about

ε / k

per step, so you may need

100, 000

+ steps to test all arms. If your lucky first arm isn't

a^{*}

, you may never discover the truth in reasonable time.

"Regret can be negative if we get lucky early." — is that right?

No. Per-step regret is

q_{*} (a^{*}) - q_{*} (a_{t}) = Δ_{a_{t}} \geq 0

using true means; the best arm gives

0

, everything else a positive gap. Lucky observed rewards don't make the definition negative.

ε

-greedy needs

\sum_{t} ε_{t}^{2} < \infty

to converge, like a learning rate." — spot the confusion.

That square-summable condition is a step-size / learning-rate requirement (from Robbins–Monro stochastic approximation, used e.g. in SGD and the

Q

-update learning rate), not a condition on the exploration probability. For

ε

-greedy the exploration schedule only needs

\sum_{t} ε_{t} = \infty

with

ε_{t} \to 0

; imposing

\sum_{t} ε_{t}^{2} < \infty

is neither necessary nor standard here.

Why questions

Why does exploration guarantee estimates converge?

Because

ε > 0

gives every arm at least probability

ε / k

per step, so each is pulled infinitely often; by the law of large numbers its reward average

Q (a) \to q_{*} (a)

Why is greedy (

ε = 0

) dangerous even when it looks efficient?

One unlucky-good or unlucky-bad early sample can permanently bias

ar g max Q

. Without exploration the agent never revisits under-sampled arms, so it can commit to a suboptimal action forever.

Why decay

ε

instead of keeping it fixed?

Early on you need wide exploration to build trustworthy

Q

; later exploration is mostly wasted regret. Decaying

ε_{t} \to 0

shifts you from explore-heavy to exploit-heavy exactly as your estimates become reliable, and lets the policy itself converge to greedy.

Why do the two decay conditions

\sum_{t} ε_{t} = \infty

and

ε_{t} \to 0

together give a policy that converges to optimal?

The first,

\sum_{t} ε_{t} = \infty

, means the total exploration mass is infinite, so each arm keeps getting sampled forever and every

Q (a) \to q_{*} (a)

— the estimates become correct, so

ar g max Q

eventually equals

a^{*}

. The second,

ε_{t} \to 0

, means the fraction of random steps shrinks to nothing, so the residual exploration regret

ε_{t} (1 - 1/ k) \to 0

and the policy stops throwing steps at worse arms. One condition secures correct estimates; the other lets the policy act on them — together they drive both estimates and behaviour to optimal.

Why keep a floor

ε_{m i n} > 0

in a decay schedule for changing environments?

If the world drifts, an arm's true value can shift; a small permanent exploration rate keeps re-checking arms so the agent can notice and adapt instead of trusting stale estimates. (This means

ε_{t} \neq \to 0

, so the policy never fully converges — a deliberate trade for adaptability.)

Why is epsilon-greedy called "undirected" exploration compared to UCB?

It explores uniformly at random, blind to which arms are uncertain. UCB directs exploration toward under-sampled/high-uncertainty arms, so it wastes fewer pulls on arms already known to be bad.

Why does epsilon-greedy still matter for Q-Learning beyond bandits?

In full RL the same explore/exploit coin drives action choice at each state; without the

ε

term the agent can lock into a suboptimal state-action path and never sample the transitions needed to learn a better policy.

Why is a fixed

ε

described as paying a permanent cost?

Because the constant fraction

ε (1 - 1/ k)

of steps always lands on worse arms (each with gap

Δ_{a} > 0

); that steady leak of reward is the price of never fully trusting your estimates.

Edge cases

k = 1

(only one arm): what does

ε

do?

Nothing meaningful. There is only one action, so exploit and explore both pick it; selection probability is

1

regardless of

ε

, and regret is always

0

since

Δ = 0

Two arms are tied in true value: is there any regret from exploring them?

No regret from swapping between the two optimal-tied arms — their gap

Δ = 0

. Regret only comes from time spent on strictly worse arms (positive

Δ_{a}

All arms have identical

q_{*}

: what is the expected regret?

Exactly

0

for any

ε

. Every gap

Δ_{a} = 0

, so no choice is ever "wrong"; exploration is harmless but also useless here.

t = 0

with all

Q = 0

, what does the first exploit step do?

It picks an

ar g max

among ties (all equal), so it effectively chooses arbitrarily — the very first "exploit" is really a tie-break, which is why early behaviour is dominated by luck.

Non-stationary environment where the best arm changes: which

ε

setup survives?

A fixed or floored

ε > 0

, because it keeps sampling all arms and can detect the switch. A fully decayed

ε_{t} \to 0

would go blind and keep serving the now-stale champion.

If rewards are deterministic (no noise), how many pulls does each arm need?

Just one. A single observation reveals

q_{*} (a)

exactly, so large

ε

is wasteful — you'd want to explore each arm once, then exploit; this is where randomised exploration is clearly overkill.

Recall Quick self-check

Fixed $ε$ ⇒ estimates converge but policy ___ ::: never stops exploring (plays $a^{*}$ with prob $1 - ε + ε / k < 1$ ). Decaying $ε_{t} \to 0$ with $\sum_{t} ε_{t} = \infty$ ⇒ ___ ::: the policy itself converges to purely greedy / optimal. The condition $\sum_{t} ε_{t}^{2} < \infty$ belongs to ___ ::: learning-rate (step-size) schedules, not exploration schedules. Per-step regret $L$ under fixed $ε$ ⇒ ___ ::: a positive constant, so cumulative regret $Regret (T)$ grows linearly in $T$ .