Visual walkthrough — Markov Decision Processes (MDP)

---

Step 1 — Standing on a state

WHAT. Picture a little world made of a handful of places you can be. Each place is a state, written $s$. Think of squares on a board. Right now you are standing on one of them.

WHY. Before we can ask "how good is it here?", we need a "here". A state $s$ is just a labelled dot: it holds everything you need to know to decide your next move (that is the memoryless Markov property from the parent note — the dot remembers nothing about how you arrived).

PICTURE. Below, three states $s_1,s_2,s_3$ sit in a line. The orange dot is where you are now. That is all $s$ means: a location.

---

Step 2 — Acting, and the coin the world flips

WHAT. From your dot you pick an action $a$ — say "go right" — out of the whole set of allowed actions. But the world may be shaky: pushing "right" might land you where you aimed most of the time, and slip some of the time.

WHY. We need a rule for what happens after you act. That rule is the transition probability $P(s^{\prime }\mid s,a)$: read it as "the chance of landing on dot $s^{\prime }$, given I was on dot $s$ and pushed $a$". The bar $\mid$ means "given". These chances over all possible $s^{\prime }$ add to $1$ — you always land somewhere.

PICTURE. From $s_2$, action "right" splits into arrows: a fat teal arrow (0.8, most likely) to $s_3$ and a thin plum arrow (0.2, slip) staying at $s_2$. The arrow thickness is the probability.

---

Step 3 — Reward: painting the arrows with numbers

WHAT. Each arrow (each transition) hands you a number the instant you cross it: the reward $R(s,a,s^{\prime })$. Good things are big positive numbers; bad things are negative.

WHY. Goals must be turned into numbers or a machine cannot chase them. $R$ is how the world says "that was good / that was bad" — immediately, on the arrow itself, not later.

PICTURE. Same branches as before, now each arrow carries a tag. The arrow into the goal $s_3$ is painted $+10$; the slip-arrow is painted $0$.

---

Step 4 — The return: adding up a whole future

WHAT. One reward is not enough — you live a whole sequence. Follow a strategy and you get a chain: $s_0\stackrel{a_0}{\to }{s}_1\stackrel{a_1}{\to }{s}_2\stackrel{a_2}{\to }\cdots$ The total haul from time $t$ onward is the return $G_t$.

WHY. "How good is here?" cannot mean "the next reward only" — a step that pays $0$ now but opens the door to $+10$ later is great. So we must sum the whole future. Each term $R_{t+1},R_{t+2},\dots$ is just Step 3's reward at successive ticks: $R_{t+k+1}=R(S_{t+k},A_{t+k},S_{t+k+1})$. But a naive infinite sum $R_{t+1}+R_{t+2}+\cdots$ can blow up to infinity, and it treats a reward 1000 steps away as equal to one right now. Both are bad.

PICTURE. A timeline of rewards $R_{t+1},R_{t+2},\dots$ as bars. The undiscounted bars are all equal height (dangerous); we are about to shrink the far ones.

---

Step 5 — Why the discount $\gamma$, and why this tool

WHAT. Introduce the discount factor $\gamma \in [0,1)$. Multiply a reward $k$ steps ahead by ${\gamma }^k$ before adding it: $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}$

WHY this tool and not another? We needed a shrinker with two properties: (1) it fades smoothly with distance so "later = worth a little less", and (2) it tames the infinite sum. Geometric shrinking ${\gamma }^k$ does both. Let ==$R_{\max }$== be an upper bound on the size of any single reward — that is, $|R(s,a,s^{\prime })|\le R_{\max }$ for every transition. Then every $R_{t+k+1}\le R_{\max }$, so $G_t\le {\sum }_{k=0}^{\infty }{\gamma }^k{R}_{\max }=\frac{R_{\max }}{1-\gamma }$ because a geometric series with ratio $\gamma <1$ converges. No other simple weighting gives you the beautiful self-reference we exploit in the next step.

PICTURE. The same reward bars, now each multiplied by its faded factor $1,\gamma ,{\gamma }^2,\dots$ — the tower of shrinking bars whose total area is finite.

---

Step 6 — The value function: averaging over all futures

WHAT. The world flips coins ($P$), so the return $G_t$ is random — different rolls give different totals. The state-value function $V^{\pi }(s)$ is the average return you would collect, starting at $s$ and always obeying strategy $\pi$: $V^{\pi }(s)={\mathbb{E}}_{\pi }\left[G_t\mid S_t=s\right]$

WHY expectation ($\mathbb{E}$)? Because you cannot pin down a single future — Step 2 gave you branches. The honest answer to "how good is here?" is the probability-weighted average over every branch. That is exactly what $\mathbb{E}$ (expected value) computes: sum of (chance $\times$ outcome). The condition "$S_t=s$" (using $S_t$ from Step 1) says "given that at tick $t$ the dot we actually stand on is $s$".

PICTURE. A tree fanning out of $s$: many possible reward-chains, each labelled with its probability. $V^{\pi }(s)$ is the balance point — the weighted average of all the chain totals.

---

Step 7 — The self-reference trick (the heart of Bellman)

WHAT. Split the return into "the very next reward" plus "everything after": $G_t=R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\cdots )=R_{t+1}+\gamma G_{t+1}$ The bracket is itself a return, just starting one step later.

WHY. This is the crucial observation. Take the average (under $\pi$, as defined in Step 6) of both sides. The average of $G_{t+1}$, given you land on some $s^{\prime }$ (i.e. given $S_{t+1}=s^{\prime }$), is by definition $V^{\pi }(s^{\prime })$ again — the same function, one step downstream. Value is defined in terms of value. That circularity is not a bug; it is the equation we can solve.

$V^{\pi }(s)={\mathbb{E}}_{\pi }\left[\underset{\text{one step}}{\underbrace{R_{t+1}}}+\gamma \underset{\text{value of where I land}}{\underbrace{V^{\pi }(S_{t+1})}}|S_t=s\right]$

PICTURE. A single dot $s$ with one short arrow to a "cloud" $s^{\prime }$; inside the cloud sits a tiny copy of the whole tree — value pointing at value. The recursion, drawn.

---

Step 8 — Unfolding the average into the Bellman equation

WHAT. Now write the expectation explicitly using the pieces from Steps 2–3. Under a deterministic policy you take action $a=\pi (s)$. The world then picks $s^{\prime }$ with chance $P(s^{\prime }\mid s,\pi (s))$. Averaging = summing (chance $\times$ payoff) over every branch $s^{\prime }$ in the state space $S$:

$V^{\pi }(s)={\sum }_{s^{\prime }\in S}\underset{\text{branch chance}}{\underbrace{P(s^{\prime }\mid s,\pi (s))}}[\underset{\text{reward on the arrow}}{\underbrace{R(s,\pi (s),s^{\prime })}}+\gamma \underset{\text{value where I land}}{\underbrace{V^{\pi }(s^{\prime })}}]$

WHY. This is Step 7's abstract ${\mathbb{E}}_{\pi }$ turned into arithmetic you can actually run: one term per branch (the symbol $S$ under the sum is the state space from Step 1 — we range $s^{\prime }$ over every dot on the board), each term = (how likely) $\times$ (reward now + discounted value later). That is the Bellman Expectation Equation.

PICTURE. The full annotated diagram: state $s$ on the left, arrows fanning to each $s^{\prime }$, each arrow tagged with $P$ and $R$, and each landing dot tagged $\gamma V^{\pi }(s^{\prime })$ — the equation laid over the geometry.

Worked check (a fully specified line world). To exercise the equation we now fix a complete reward function on our three-state line — stated here in full so every number is defined on this page:

Apply the boxed equation at $s=s_2$, summing over the two branches $s^{\prime }\in \{s_3,s_2\}$: $V^{\pi }(s_2)=\underset{P(s_3\mid \cdot )}{\underbrace{0.8}}[\underset{R\to s_3}{\underbrace{10}}+0.9\cdot 100]+\underset{P(s_2\mid \cdot )}{\underbrace{0.2}}[\underset{R\text{slip}}{\underbrace{0}}+0.9V^{\pi }(s_2)]$ $V^{\pi }(s_2)=0.8(10+90)+0.18V^{\pi }(s_2)=80+0.18V^{\pi }(s_2)$ $0.82V^{\pi }(s_2)=80\Rightarrow V^{\pi }(s_2)=\frac{80}{0.82}\approx 97.56$ (The reward on the winning arrow is now inside the bracket, matching Step 3's picture exactly.)

---

Step 9 — From "follow $\pi$" to "do the best thing" (optimality)

WHAT. So far $\pi$ was fixed. What if at each state we choose the best action instead? First we need a way to score a single action. The action-value function $Q^{\ast }(s,a)$ answers "if I take action $a$ right now in state $s$, then act optimally forever after, what is my expected return?" It is built from exactly the same pieces: $Q^{\ast }(s,a)={\sum }_{s^{\prime }\in S}P(s^{\prime }\mid s,a)[R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$ Because the best you can do from a state is to take its best-scoring action, the optimal state-value is just the biggest $Q^{\ast }$ available: $V^{\ast }(s)={\max }_{a\in A}{Q}^{\ast }(s,a)={\max }_{a\in A}{\sum }_{s^{\prime }\in S}P(s^{\prime }\mid s,a)[R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime })]$

WHY the $\max$ and not a sum? Because the optimal agent is not averaging its own choices — it picks the single best one. The world still averages (that inner $\sum$ over $s^{\prime }$ stays), but over your own action $a$ (ranging over the whole menu $A$ from Step 2) you take the maximum. That one swap — ${\sum }_{\text{over }\pi }\to {\max }_a$ — turns "evaluate a strategy" into "find the best strategy".

PICTURE. From $s_1$ two action-branches: safe $a_1$ (value 55) and risky $a_2$ (value 60). A spotlight highlights the larger — the $\max$ chooses $a_2$.

Worked check (a fully specified choice, all numbers defined here). Consider a fresh state $s_1$ with exactly two actions, whose transitions and rewards we state in full:

Plug each action into $Q^{\ast }(s_1,a)={\sum }_{s^{\prime }}P(s^{\prime }\mid s_1,a)[R+\gamma V^{\ast }(s^{\prime })]$: $Q^{\ast }(s_1,a_1)=1\cdot [5+1\cdot 50]=55$ $Q^{\ast }(s_1,a_2)=0.5[20+1\cdot 80]+0.5[-10+1\cdot 30]=0.5(100)+0.5(20)=60$ Since $60>55$, the $\max$ picks $a_2$: $V^{\ast }(s_1)=60$ and ${\pi }^{\ast }(s_1)=a_2$. See 5.4.01-Q-Learning for how machines learn these $Q^{\ast }$ values without knowing $P$.

---

The one-picture summary

Everything above collapses into a single backup diagram: you stand on $s$, the world fans you to next-states $s^{\prime }$ (ranging over the state space $S$) weighted by $P$, each arrow pays $R$, each landing dot carries $\gamma V^{\pi }(s^{\prime })$, and $V^{\pi }(s)$ is the weighted average of all of it (or the max over your own actions, for $V^{\ast }$).

Recall Feynman retelling — say it back in plain words

Imagine standing on a square. You ask: "How good is standing here?" The answer can't just be the next payout, because a boring square that leads to a jackpot is secretly wonderful. So the value of here is: the reward you'll grab on your very next step, plus a slightly-shrunk copy of the value of wherever you land next. But the world is shaky — you might slip — so you don't get one clean next-square; you get several possible ones, each with a chance. So you take a weighted average: for every place you might land, multiply "how likely" by "reward there + shrunk value there", and add them up. That single sentence, drawn as arrows fanning out of a dot, is the Bellman equation. And if instead of blindly following a fixed strategy you get to choose the best action, you swap "average over my choice" for "pick my best choice" — a max — and you've written the optimality equation. Same picture, one word changed.

Recall Quick self-test

Why must $V^{\pi }(s)$ use an expectation ${\mathbb{E}}_{\pi }$ and not a plain sum of rewards? ::: Because transitions are random ($P(s^{\prime }\mid s,a)$ has branches), so the return is a random quantity; ${\mathbb{E}}_{\pi }$ averages over all possible futures weighted by their probabilities, under policy $\pi$. What single change turns the Bellman expectation equation into the Bellman optimality equation? ::: Replace the policy's chosen action with a ${\max }_a$ over all actions in $A$ — you pick the best action instead of following $\pi$. In $G_t={\sum }_k{\gamma }^k{R}_{t+k+1}$, why does the sum stay finite? ::: With $0\le \gamma <1$ and rewards bounded by $R_{\max }$, the geometric series converges to at most $R_{\max }/(1-\gamma )$. What does $\gamma =0$ do to the agent's behaviour? ::: It makes the agent totally short-sighted — only the immediate reward $R_{t+1}$ counts; all future rewards are multiplied by $0$. What is the difference between bare $S$ and $S_t$? ::: Bare $S$ is the state space — the whole set of dots; $S_t$ is the single random state the agent occupies at time $t$.

---

Prerequisites & neighbours: Markov-Chains (the memoryless dynamics behind $P$), Dynamic-Programming (how the recursion gets solved), 5.1.01-Reinforcement-Learning-Problem-Formulation, 5.2.01-Dynamic-Programming-inRL, 5.3.01-Monte-Carlo-Methods, 5.3.02-Temporal-Difference-Learning.