Exploration vs exploitation tradeoff: Foundations

Before we can read a single formula on the parent page, we need to build every symbol from the ground up. This page is a dictionary you can trust: nothing appears here that we haven't first drawn a picture for. We start with the story, then the vocabulary, then the numbers.

The story every symbol lives inside

Imagine a row of slot machines. Each machine has a lever ("arm") you can pull, and each pull spits out some reward — a number, maybe a coin, maybe nothing. You do not know which machine is generous. The only way to find out is to pull levers and watch.

This is the Multi-Armed Bandit — the simplest possible world in which the exploration/exploitation dilemma exists. Everything else on the parent page is a tool for playing this game well.

Figure s01 — the row of arms. Three slot machines stand side by side, each drawn in its own colour (arm 1 burnt orange, arm 2 teal, arm 3 plum). Above each lever is a " $r ?$ " mark: pulling that lever produces an unknown reward. This is the whole world we play in — refer back to it whenever a symbol names something in this picture.

Figure — Exploration vs exploitation tradeoff

Building the symbols, one at a time

Each block below gives a symbol: plain words → the picture → why the topic needs it. They are ordered so each one only uses symbols already defined above it.

$a$ and the action set $A$

$K$ — the number of actions

$t$ and $T$ — step now vs. total steps

$r$ and $r_{t}$ — the reward, and the reward at step $t$

$a_{t}$ and $a_{i}$ — which action was chosen at a given step

$μ_{a}$ — the true average reward of arm $a$

Figure s02 — one arm's payout cloud. The teal curve is the spread of rewards a single arm can produce; the plum dashed line marks its true mean $μ_{a}$ (the balance point of the cloud). The orange dots are a handful of actually observed rewards $r_{i}$ , and the orange dotted line is their average — our estimate $Q_{t} (a)$ , which wobbles near, but rarely exactly on, the true mean.

$p (r ∣ a)$ — the reward distribution of arm $a$

$σ$ — how wide an arm's payout cloud is

$N_{t} (a)$ — how many times we've pulled arm $a$

$\overset{μ}{^}_{a}$ and $Q_{t} (a)$ — our estimate of an arm's value

Definition The hat means "our guess"

Plain words: $\overset{μ}{^}_{a}$ (mu with a hat) is our best current guess of $μ_{a}$ , computed from the rewards we've actually seen. The parent also writes this as $Q_{t} (a)$ — the estimated value of action $a$ at time $t$ . Same idea, two names.
How it's computed: average the rewards you got from arm $a$ : $Q_{t} (a) = \frac{1}{N _{t} ( a )} \sum_{i : a_{i} = a} r_{i} (when N_{t} (a) \geq 1)$ The notation $i : a_{i} = a$ under the sum means "add up over every past round $i$ where the arm chosen was $a$ " — this is exactly where the symbol $a_{i}$ earns its keep.
Picture: the orange dotted line in Figure s02 — a wobbly estimate of the true centre, drawn from just a handful of dots.
Why we need it: $\overset{μ}{^}_{a}$ is all the agent has. The gap between $\overset{μ}{^}_{a}$ and $μ_{a}$ is exactly what exploration shrinks. The $Q$ name connects to Q-Learning, where the same "estimated action value" idea drives a full learning algorithm.

$μ^{}$ and $a^{}$ — the best arm and its value

$E [\cdot]$ — the expected value (average outcome)

Regret — the running score of our mistakes

Now every symbol in the parent's headline formula is defined, so we can finally read it:

Figure s03 — two shapes of regret. The orange curve is a straight ramp: a strategy that never corrects its mistakes keeps paying the same reward gap on every step, so its total regret grows in proportion to $T$ . The teal curve bends flat: a balanced strategy stops adding much regret once it has identified the best arm, so its total grows only like $lo g T$ . The gap between the two curves is the value of being clever about exploration.

Reading the $O (\cdot)$ notation

$ϵ$ , $c$ , $β$ — the tuning knobs

$s$ and $π (a ∣ s)$ — the "situation" and the policy

Definition

$s$ = "the situation the agent is in"

Plain words: $s$ (the state) describes what the world looks like right now when the agent must choose. In a full RL problem the state might be the board position in a game or a robot's sensor readings.
In the bandit setting: there is only one state — you always face the same row of machines, nothing about the situation changes between pulls. So $s$ is a constant and can be dropped; that is why bandit formulas often shrink $π (a ∣ s)$ down to just $π (a)$ .
Picture: a single fixed backdrop (the same slot-machine hall of Figure s01, every round) versus, in richer problems, a changing scene.
Why we mention it: the parent page writes $π (a ∣ s)$ so the notation matches full RL, where the state matters. Knowing $s$ collapses to one value here keeps the bandit formulas honest and un-mysterious.

Two connected ideas you'll reuse

Recall Where the estimate

$Q_{t} (a)$ comes from (link to TD learning) The running average $Q_{t} (a)$ can be updated one reward at a time instead of re-summing everything. That incremental update is the seed of Temporal-Difference Learning — same "nudge your estimate toward the new evidence" spirit.

Recall Why too much exploitation resembles overfitting

Locking onto an arm after tiny evidence is like overfitting: you've trusted noise as if it were signal. Exploration plays the role of regularization — it keeps you humble about small samples.

The prerequisite map

Read it top-down: naming choices ( $a$ out of $A$ ) and rewards lets us estimate arm values; estimates plus true means define regret; counts and the spread $σ$ create uncertainty (standard error $σ / N$ ) and exploration bonuses; regret and bonuses together frame the tradeoff, which the three named strategies then resolve.

Equipment checklist

Test yourself — cover the right side and answer each before revealing.

What does the subscript in

r_{t}

mean?

The reward that occurred on step $t$ ; subscripts are address labels, not multiplication.

What is the difference between

a

and the set

A

a

is one chosen arm;

A

is the whole menu of arms it is picked from, and

∣ A ∣ = K

counts them.

What is the difference between

a

and

a_{t}

a

names a possible choice;

a_{t}

is the arm actually chosen on round $t$ (e.g.

a_{4} = 2

means arm 2 was pulled on round 4).

What is the difference between

μ_{a}

and

\overset{μ}{^}_{a}

(i.e.

Q_{t} (a)

μ_{a}

is the hidden true average of arm

a

;

\overset{μ}{^}_{a}

is our estimate built from observed rewards.

What does

σ

measure?

The spread (standard deviation) of an arm's payouts around its mean — the width of its reward cloud.

What happens to

Q_{t} (a)

when

N_{t} (a) = 0

It is undefined (division by zero); we handle it with an initial value

Q_{0} (a)

or by pulling each arm once first.

What does

∣ A ∣

mean in this topic?

The number of available actions,

K

— a count of the action set, not absolute value.

Difference between

max_{a} μ_{a}

and

ar g max_{a} μ_{a}

max

gives the largest value

μ^{*}

;

ar g max

gives which arm

a^{*}

achieves it.

How does the count

N_{t} (a)

translate into uncertainty?

The standard error of the estimate is

σ / N_{t} (a)

, so the wobble shrinks like

1/ N_{t} (a)

— a big count means a small wobble.

Regret (T)

a fixed number or an expectation, and why?

An expectation — actions and rewards are random, so we average over all runs; linearity of expectation lets us write

\sum_{t} E [r_{t}]

Why is

O (lo g T)

regret better than

O (T)

O (lo g T)

grows far slower than a straight line, meaning we stop making mistakes once we've learned the best arm.

What does

ϵ

control in epsilon-greedy?

The probability of exploring (choosing randomly) instead of exploiting the best current estimate.

What is the state

s

in a plain bandit?

There is only one, unchanging state, so

s

is constant and

π (a ∣ s)

collapses to

π (a)

What does

π (a ∣ s)

represent?

The policy — the probability of choosing action

a

in situation

s

; the shared output of every strategy.