Visual walkthrough — Policies and value functions

We only assume you know what a Markov Decision Process gives us: at each moment you are in a state (where you are), you pick an action (what you do), and the world hands you a reward (a number, good if positive) and drops you into the next state. That is all we need.

---

Step 1 — A reward is just a number on a timeline

WHAT. Draw time going left to right. At each tick the agent collects one number: a reward. We write the reward that arrives one step after time $t$ as $R_{t+1}$.

WHY. Before we can talk about "how good a situation is," we must agree on the raw material: a stream of numbers. Everything else is bookkeeping on top of this stream.

PICTURE. Look at the timeline below. The dot at time $t$ is "now." The red arrow is the first reward you will receive, $R_{t+1}$ — notice its subscript is $t+1$, not $t$, because the reward comes after you act.

---

Step 2 — Add up the whole future: the return $G_t$

WHAT. Sum every reward from now to the end of time. Call that sum the return $G_t$: $G_t=\underset{\text{next reward}}{\underbrace{R_{t+1}}}+\underset{\text{the one after}}{\underbrace{R_{t+2}}}+R_{t+3}+\cdots$

WHY. A single reward is short-sighted. We care about long-run success, so we add the whole tail of rewards into one number $G_t$ — the total score earned from time $t$ onward.

PICTURE. Each future reward is a bar. $G_t$ is the total height when you stack them all.

---

Step 3 — Fix the infinite pile with discounting $\gamma$

WHAT. Multiply the reward $k$ steps ahead by ${\gamma }^k$, where $\gamma$ (Greek "gamma") is a fixed number between $0$ and $1$: $G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots ={\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$

Term by term: ${\gamma }^0=1$ multiplies the nearest reward (full weight), ${\gamma }^1=\gamma$ shrinks the next one, ${\gamma }^2$ shrinks the one after that even more.

WHY THIS TOOL and not a plain sum? A plain infinite sum of rewards can blow up to infinity — then "which state is better?" has no answer. We need a geometric weight ${\gamma }^k$ because it does two jobs at once: (1) it shrinks each far-away reward so the total stays finite, and (2) ${\gamma }^k$ decaying like a geometric series is the only memoryless discount — the weight of "two steps from here" looks the same no matter where "here" is. That matches the Markov spirit of an MDP.

PICTURE. The reward bars are unchanged, but now each is scaled by a shrinking red envelope ${\gamma }^k$. The far bars almost vanish.

Edge cases of $\gamma$:

• $\gamma =0$: only $R_{t+1}$ survives — a purely greedy, one-step-ahead agent.
• $\gamma \to 1$: all rewards weigh almost equally — a far-sighted agent (needs the sum to still converge, e.g. episodes that end).

---

Step 4 — The future is uncertain: take an expectation

WHAT. The agent's policy may roll dice to pick actions, and the world may roll dice to pick next states. So $G_t$ is not one number — it is a spray of possible totals. We collapse the spray to its average, the expectation ${\mathbb{E}}_{\pi }[\cdot ]$, and define the value of a state: $V^{\pi }(s)={\mathbb{E}}_{\pi }\left[G_t\mid S_t=s\right]$

Reading the symbols: $V^{\pi }(s)$ = "value of state $s$"; the superscript $\pi$ = "assuming we act by policy $\pi$"; ${\mathbb{E}}_{\pi }$ = "average over all randomness the policy and world produce"; $\mid S_t=s$ = "given that right now we are standing in state $s$."

WHY EXPECTATION and not the max or the min? We want the value you'd earn on average if you lived this state many times under policy $\pi$. Not the luckiest run (max), not the worst (min) — the typical one. That is exactly what an average / expectation is for.

PICTURE. Many faded rollout paths fan out from state $s$; each has its own return. The red line is their average — that single average height is $V^{\pi }(s)$.

---

Step 5 — The magic peel: $G_t=R_{t+1}+\gamma G_{t+1}$

WHAT. Look again at the discounted return and factor out one $\gamma$ from everything past the first reward: $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}$

The whole tail, once you pull out one $\gamma$, is itself a return — but starting one step later. That is $G_{t+1}$.

WHY. This is the single trick the entire theory rests on. An infinite sum is scary; a "first term plus a shrunken copy of myself" is a recursion we can solve. We turn an unbounded object into a self-reference.

PICTURE. Snip off the first red bar $R_{t+1}$. What remains is the same picture shifted one step left and scaled by $\gamma$ — a smaller copy of the original stack.

---

Step 6 — Push the average through the peel

WHAT. Take ${\mathbb{E}}_{\pi }$ of both sides of the peel, conditioned on $S_t=s$: $V^{\pi }(s)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma G_{t+1}\mid S_t=s\right]$ Expectation is linear (average of a sum = sum of averages), and the average of $G_{t+1}$ given you land in $s^{\prime }$ is by definition $V^{\pi }(s^{\prime })$. So the tail's average becomes the value of wherever you land next.

WHY. We want an equation in terms of $V^{\pi }$ only — no leftover $G$. Linearity of expectation lets us split, and the definition from Step 4 lets us re-fold $\mathbb{E}[G_{t+1}]$ back into a $V^{\pi }$. The recursion becomes a recursion on values.

PICTURE. A one-step lookahead fan: from $s$, an averaged immediate reward, then an arrow into a next state $s^{\prime }$ whose value $V^{\pi }(s^{\prime })$ is a smaller copy of the same object.

---

Step 7 — Name the two dice explicitly: the Bellman expectation equation

WHAT. "Average over randomness" hides two separate dice. Spell them out: $V^{\pi }(s)={\sum }_a\underset{\text{dice 1: which action}}{\underbrace{\pi (a\mid s)}}{\sum }_{s^{\prime },r}\underset{\text{dice 2: world’s response}}{\underbrace{p(s^{\prime },r\mid s,a)}}[\underset{\text{reward now}}{\underbrace{r}}+\underset{\text{discounted future}}{\underbrace{\gamma V^{\pi }(s^{\prime })}}]$

Term by term:

• ${\sum }_a\pi (a\mid s)$ — average over each action $a$, weighted by how likely the policy is to choose it.
• ${\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)$ — average over each next-state-and-reward pair the world might produce after that action.
• $r$ — the reward collected on this transition (this is $R_{t+1}$ realised).
• $\gamma V^{\pi }(s^{\prime })$ — the value of the state you landed in, discounted once.

WHY. A number you can compute needs the dice written as explicit sums over probabilities, not an abstract $\mathbb{E}$. Splitting into "policy dice then world dice" mirrors the actual order of events: you choose, then the world responds.

PICTURE. A two-layer tree: root $s$ → policy branches (one per action, thickness = probability) → world branches (one per outcome, thickness = probability) → each leaf pays $r+\gamma V^{\pi }(s^{\prime })$.

---

Step 8 — Watch the recursion actually solve itself (worked, from the parent)

WHAT. Use the parent's 2-state example. One action, $\gamma =0.9$. From $s_1$: reward $+1$, then stay with prob $0.5$ or move to $s_2$ with prob $0.5$. From $s_2$: reward $+2$, stay forever.

Write the boxed equation once per state: $V^{\pi }(s_2)=2+0.9V^{\pi }(s_2)\Rightarrow 0.1V^{\pi }(s_2)=2\Rightarrow V^{\pi }(s_2)=20$ $V^{\pi }(s_1)=1+0.9[0.5V^{\pi }(s_1)+0.5\cdot 20]\Rightarrow 0.55V^{\pi }(s_1)=10\Rightarrow V^{\pi }(s_1)=\frac{10}{0.55}\approx 18.18$

WHY. $s_2$ is a self-loop, so its equation has only itself — solve it first (the geometric-series limit from Step 3). Feed that number into $s_1$'s equation. The recursion collapses to plain algebra.

PICTURE. The two-node MDP with the self-loops drawn, red-highlighting the $s_2$ self-loop that we solve first.

---

The one-picture summary

The whole derivation on one canvas: reward stream → discounted return $G_t$ → average into $V^{\pi }(s)$ → peel one step → Bellman recursion. Follow the red arrow around the loop: the value of now equals the reward you get now plus a discounted copy of the value of next.

Recall Feynman retelling (say it out loud)

Imagine standing on a square. The world will pay you a number to leave, then drop you on a new square, over and over. Add up all those payments, but trust far-off payments a little less each time — that shrinking is the discount $\gamma$, and it's what keeps the total from being infinite. Since your dice-rolling strategy and the world are both random, you don't want one lucky total; you want the average total. That average, starting from a square, is the square's value. Now the trick: your average total = the average of (first payment) + (a slightly-shrunk average total of the next square). That's it — the value of where you are is the reward you get plus a discounted echo of the value of where you'll be. Written with the two dice spelled out (which action, then which outcome), that echo is the Bellman expectation equation.

Recall Quick self-quiz

Why must $\gamma <1$? ::: So the geometric series $1+\gamma +{\gamma }^2+\cdots =\frac{1}{1-\gamma }$ converges and the return stays finite. What does the "peel" $G_t=R_{t+1}+\gamma G_{t+1}$ buy us? ::: It turns an infinite sum into a self-reference, giving the recursive Bellman equation. Why an expectation and not a max? ::: We want the average return under policy $\pi$, not the best-case outcome. In the 2-state example, why solve $V^{\pi }(s_2)$ first? ::: Its Bellman equation references only itself (self-loop), so it's a single equation in one unknown.