Foundations — Dynamic programming (value - policy iteration)

This page builds every symbol the parent note uses, starting from a reader who has never seen an expectation, a policy, or a Greek letter in this context. Read it top to bottom: each brick rests on the one before it.

1. The world: states, actions, and the little robot

Picture a robot on a grid of tiles. Each tile it can stand on is a state. At each tile it can pick a move — up, down, left, right — and each move is an action.

Why sets (the curly $\mathcal{S}$, $\mathcal{A}$)? Because later we count "at most $|\mathcal{A}{|}^{|\mathcal{S}|}$ policies" — the bars $|\cdot |$ just mean "how many things are in this set". With 16 tiles and 4 moves that is $4^{16}$, a huge number; DP beats brute force over all of them.

2. Reward $r$ and the discount $\gamma$

Why do we need $\gamma$ at all — why not just add up rewards? Two reasons, one practical, one mathematical:

• Practical: a cookie today beats a cookie in a year. $\gamma <1$ encodes impatience.
• Mathematical: if the robot could wander forever, a plain sum of $-1$'s would be $-\infty$ for everyone and comparisons become meaningless. Multiplying by ${\gamma }^k$ makes the total a finite number, so states become comparable.

3. The return $G_t$ — what we actually want to maximise

The robot cares about its whole future, not one reward. Stack up the discounted rewards from time $t$ onward:

$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots$

The single most important algebraic trick on the parent page pulls the first reward off this trail:

$G_t=R_{t+1}+\gamma \underset{=G_{t+1}}{\underbrace{(R_{t+2}+\gamma R_{t+3}+\cdots )}}=R_{t+1}+\gamma G_{t+1}$

Why bother? Because the bracket is the same kind of object one step later. This "now-reward plus discounted next-return" shape is the seed of every Bellman equation. Recognise it — it is the whole topic.

4. Policy $\pi$ — the robot's rulebook

Two flavours, both used on the parent page:

• Random / stochastic: e.g. $\pi (a\mid s)=0.25$ for each of 4 moves — a full pie.
• Greedy / deterministic: one arrow gets probability $1$ — a single confident arrow.

Why probabilities and not just one arrow? Because DP starts with a guess and improves it; early on the rulebook is a fuzzy pie, and we watch it sharpen into single arrows as the robot learns.

5. Expectation $\mathbb{E}$ — averaging over uncertainty

The world may be uncertain: "move right" might slip and land elsewhere. When outcomes are random, we cannot say the return — only its average.

Why is this the right tool (and not, say, the best case or worst case)? Because a rational agent that repeats an episode many times cares about its long-run mean payoff. The expectation is the honest summary of "what you get on average" — no other single number captures that.

Concretely, for a value $x^{\prime }$ that occurs with probability $p^{\prime }$: $\mathbb{E}[\text{value}]={\sum }_{\text{outcomes}}(\text{probability of outcome})\times (\text{value of outcome}).$ Every $\sum$ (capital sigma, "add these up") in the Bellman equations is one of these probability-weighted averages spelled out.

6. The dynamics $p(s^{\prime },r\mid s,a)$

Notation care: $s^{\prime }$ (read "s-prime") just means "the next state" — the prime is a tick meaning "one step later", nothing more. DP needs $p$ because it is a model-based method: it looks up every possible next outcome and averages over them. (Later chapters like 5.1.11-Q-learning drop $p$ and sample instead — but that story starts here.)

7. The value functions $V$ and $Q$ — the payoff of a shortcut

Now we can assemble the two starring symbols.

Why keep both $V$ and $Q$? $V$ answers "how good is this tile?"; $Q$ answers "how good is this move from this tile?". To choose, you need the per-move numbers — that is why the greedy policy is $\arg {\max }_{a}Q$.

8. The operators: $\max$, $\arg \max$, $\sum$

Three symbol-machines finish the vocabulary.

Why does the optimal equation use $\max$ while the policy equation uses ${\sum }_a\pi (a\mid s)$? Because an averaging policy blends all arrows (weighted sum), but an optimal agent never blends — it always grabs the single best arrow. Averaging vs. maximising is the one line that separates the two Bellman equations on the parent page.

9. Putting it together (preview of the parent's core line)

With every symbol earned, the parent's central equation is now readable left to right, in words:

$\underset{\text{value here}}{\underbrace{V^{\pi }(s)}}=\underset{\text{average over my moves}}{\underbrace{\sum _a\pi (a\mid s)}}\underset{\text{average over the world’s outcomes}}{\underbrace{\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)}}[\underset{\text{grab now}}{\underbrace{r}}+\underset{\text{shrunk value of next tile}}{\underbrace{\gamma V^{\pi }(s^{\prime })}}]$

That is Section 3's "$R_{t+1}+\gamma G_{t+1}$" trick with the two averages ($\pi$ and $p$) written out. Swap ${\sum }_a\pi (a\mid s)$ for ${\max }_a$ and you have the optimality equation. Nothing else is new. These live formally in Bellman-equations and power 5.108-Markov-Decision-Process-(MDP).

Prerequisite map

Each source arrow is a symbol you must own before the target makes sense; every path drains into the DP node the parent page is about.

Equipment checklist

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