Worked examples — Markov Decision Processes (MDP)

We use only ideas already built in the parent: a state $s$ (a situation), an action $a$ (a choice), the transition probability $P(s^{\prime }\mid s,a)$ (chance of landing in $s^{\prime }$), the reward $R$ (immediate payoff), the discount $\gamma$ (how much we shrink future rewards), the value $V^{\pi }(s)$ (expected total discounted reward from $s$ under policy $\pi$), and the action-value $Q^{\pi }(s,a)$. See 5.1.03-Policy-and-Value-Functions and 5.1.04-Bellman-Equations if any symbol feels shaky.

The scenario matrix

Every MDP exercise you'll meet is one (or a blend) of these cells. Each worked example below is tagged with the cell it covers.

Cell	What makes it tricky	Example
A. Deterministic chain	probability is always 1, pure discounting	Ex 1
B. Self-loop / terminal	infinite geometric series, $\frac{1}{1-\gamma }$	Ex 2
C. Stochastic transition	must average over outcomes	Ex 3
D. $\gamma \to 0$ (myopic)	only immediate reward matters	Ex 4
E. $\gamma \to 1$ (far-sighted)	limiting/divergence behaviour	Ex 4
F. Action choice (optimality)	$\max$ over actions, $\arg \max$ policy	Ex 5
G. Negative reward / penalty	signs must be handled carefully	Ex 6
H. Real-world word problem	translate English → tuple $(S,A,P,R,\gamma )$	Ex 7
I. Exam twist	coupled equations, solve simultaneously	Ex 8

Recall Quick self-test before diving in

What does ${\gamma }^k$ multiply? ::: The reward received $k$ steps in the future, shrinking far rewards. Why must $V^{\pi }$ appear on both sides of a Bellman equation? ::: Because value from a state includes the value of the state you move to — it is self-referential (recursive).

---

Example 1 — Deterministic chain (Cell A)

Forecast: you're 3 steps from a $+10$. Guess whether it's above or below $10$.

The figure below draws the corridor. Textual description of the figure: four rounded boxes sit in a horizontal row, left to right, labelled $s_1$, $s_2$, $s_3$ (all lavender) and $s_4$ (mint, the goal). Three coral arrows point rightward, one from each box to its neighbour, each tagged "right" — these are the deterministic actions. The rightmost coral arrow, entering $s_4$, carries the extra tag "+10 on entry" above it. Under each box its computed value is written: $V=2.5$, $V=5$, $V=10$, and "goal +10". The reward tag sits on the arrow into $s_4$, not inside $s_4$ — that is the "$+10$ on entry" detail Step 1 hinges on.

Step 1 — Write the terminal value. $s_4$ is terminal, so no future reward accumulates from it: $V^{\pi }(s_4)=0$. Why this step? A terminal state has no "after", so its ongoing value is zero. The $+10$ is collected entering it, on the previous transition (the labelled coral arrow in the figure).

Step 2 — Value of $s_3$. From $s_3$, going right lands in $s_4$ (prob 1), collecting reward $+10$: $V^{\pi }(s_3)=1\cdot [10+\gamma V^{\pi }(s_4)]=10+0.5\cdot 0=10.$ Why this step? This is the Bellman expectation equation with a single certain outcome, so the sum has one term.

Step 3 — Back up the chain. Each earlier state just discounts the next (follow the values under the boxes leftward): $V^{\pi }(s_2)=0+0.5\cdot 10=5,V^{\pi }(s_1)=0+0.5\cdot 5=\mathrm{2.5.}$ Why this step? Each step adds no reward but multiplies by $\gamma$, so being one step farther halves the value.

Verify: the $+10$ enters the return two discount factors deep (it is applied once as we leave $s_1$ into $s_2$, again from $s_2$ into $s_3$), so $V^{\pi }(s_1)$ is discounted by ${\gamma }^2$: $V^{\pi }(s_1)={\gamma }^2\cdot 10=0.5^2\cdot 10=0.25\cdot 10=2.5$. ✓ (Below $10$, as forecast.)

---

Example 2 — Self-loop terminal (Cell B)

Forecast: an infinite stream of $+10$'s, shrunk by $0.9$ each step. Bigger or smaller than $100$?

Step 1 — Set up the self-referential equation. The self-loop means the "next state" is $s_3$ again: $V^{\pi }(s_3)=10+0.9V^{\pi }(s_3).$ Why this step? When a state loops to itself, its own value appears on both sides — this is the recursive heart of Bellman.

Step 2 — Solve algebraically. $V^{\pi }(s_3)-0.9V^{\pi }(s_3)=10\Rightarrow 0.1V^{\pi }(s_3)=10\Rightarrow V^{\pi }(s_3)=100.$ Why this step? This is exactly the geometric-series sum ${\sum }_{k=0}^{\infty }0.9^k\cdot 10=\frac{10}{1-0.9}=100$. The algebra and the series agree.

Step 3 — Back-substitute. The corridor $s_1\to s_2\to s_3$ needs two $0$-reward steps to reach the paying state $s_3$: $V^{\pi }(s_2)=0.9\cdot 100=90,V^{\pi }(s_1)=0.9\cdot 90=81.$

Verify: $V^{\pi }(s_1)={\gamma }^2{V}^{\pi }(s_3)=0.81\cdot 100=81$. ✓ (Equals $100$ at the goal — the "keeps paying" version, unlike Ex 1's one-shot $+10$.)

---

Example 3 — Stochastic transition (Cell C)

Forecast: slipping wastes time. Higher or lower than the no-slip value of $90$?

Step 1 — Average over both outcomes. The Bellman sum now has two terms weighted by probability: $V^{\pi }(s_2)=0.8[0+0.9\cdot 100]+0.2[0+0.9V^{\pi }(s_2)].$ Why this step? Stochastic transitions mean expectation = probability-weighted average of "reward + discounted next value" across every reachable $s^{\prime }$.

Step 2 — Collect the $V^{\pi }(s_2)$ terms. $V^{\pi }(s_2)=72+0.18V^{\pi }(s_2)\Rightarrow 0.82V^{\pi }(s_2)=72\Rightarrow V^{\pi }(s_2)=\frac{72}{0.82}\approx \mathrm{87.80.}$ Why this step? Same self-reference trick as Ex 2: the slip probability puts $V^{\pi }(s_2)$ on both sides.

Verify: $87.80<90$. ✓ Slipping strictly lowers value — uncertainty is costly.

---

Example 4 — Discount extremes (Cells D & E)

Forecast: myopic sees only "now". Far-sighted sees a huge future. Guess both magnitudes.

Step 1 — $\gamma =0$. $V^{\pi }(s_0)=4+0\cdot V^{\pi }(s_0)=4.$ Why this step? With $\gamma =0$ the future term vanishes entirely — the agent is completely short-sighted and values only the immediate reward.

Step 2 — $\gamma =0.99$. $V^{\pi }(s_0)=\frac{4}{1-0.99}=\frac{4}{0.01}=400.$ Why this step? The geometric bound $\frac{R}{1-\gamma }$ blows up as $\gamma$ approaches $1$ — a patient agent counts far rewards almost fully.

Step 3 — The limit $\gamma \to 1$. ${\lim }_{\gamma \to 1^{-}}\frac{4}{1-\gamma }=+\infty .$ Why this step? At exactly $\gamma =1$ an infinite stream of positive rewards diverges — this is precisely why the parent required $\gamma \in [0,1)$, strictly below $1$, for infinite-horizon tasks.

Verify: $\gamma =0\Rightarrow 4$; $\gamma =0.99\Rightarrow 400$; and the series diverges at $1$. ✓ All three consistent with $V^{\pi }(s_0)=\frac{4}{1-\gamma }$ (which gives $4$ at $\gamma =0$ too).

---

Example 5 — Action choice & optimal policy (Cell F)

Forecast: the risky action's average outcome — above or below the safe $55$?

Textual description of the figure: $s_1$ (lavender box) sits on the left. Three arrows leave it. A mint arrow labelled "a1 safe +5" goes up-right to $s_2$ (mint box) — this is the deterministic safe action. A butter (pale-yellow) arrow labelled "a2 0.5 +20" goes right to $s_3$ (butter box), and a coral arrow labelled "a2 0.5 -10" goes down-right to $s_4$ (coral box) — these two are the two random branches of the single risky action $a_2$, each tagged with its probability and reward. Beside each destination box its given optimal value is printed: $V^{\ast }=50$ at $s_2$, $V^{\ast }=80$ at $s_3$, $V^{\ast }=30$ at $s_4$. A summary caption near $s_1$ reads "Q(a1)=55, Q(a2)=60, pick a2".

Step 1 — $Q^{\ast }$ for the safe action. $Q^{\ast }(s_1,a_1)=5+1\cdot 50=55.$ Why this step? $Q^{\ast }(s,a)$ = immediate reward + discounted optimal future value $V^{\ast }$ of where you land (safe action lands in $s_2$ for sure, following the mint arrow).

Step 2 — $Q^{\ast }$ for the risky action (average two branches). $Q^{\ast }(s_1,a_2)=0.5(20+80)+0.5(-10+30)=0.5\cdot 100+0.5\cdot 20=60.$ Why this step? Expectation over the stochastic outcomes (butter and coral arrows); note the $-10$ penalty is handled just like any reward, keeping its sign.

Step 3 — Take the max (Bellman optimality). $V^{\ast }(s_1)=\max (55,60)=60,{\pi }^{\ast }(s_1)=\arg {\max }_a{Q}^{\ast }(s_1,a)=a_2.$ Why this step? The optimal value picks the best value ($\max$); the optimal policy picks the action achieving it ($\arg \max$).

Verify: $60>55$, so risky wins. ✓ The good branch ($+100$) outweighs the bad ($+20$) on average.

---

Example 6 — Negative rewards (Cell G)

Forecast: the pit repeats its penalty. How negative does that get?

Step 1 — Value of the pit (self-loop, negative). The pit has only one action (fall forever), so its optimal value is forced: $V^{\ast }(s_p)=-8+0.5V^{\ast }(s_p)\Rightarrow 0.5V^{\ast }(s_p)=-8\Rightarrow V^{\ast }(s_p)=-16.$ Why this step? Same $\frac{R}{1-\gamma }$ machinery — negative $R$ just gives a negative value; the algebra is identical.

Step 2 — Q-values. $Q^{\ast }(s_1,\text{down})=0+0.5\cdot (-16)=-8,$ $Q^{\ast }(s_1,\text{up})=6+0.5\cdot 0=6.$ Why this step? "Down" earns nothing on the transition then inherits the pit's value $V^{\ast }(s_p)$; "up" collects $+6$ into a terminal ($V^{\ast }(s_g)=0$).

Step 3 — Optimal choice. ${\pi }^{\ast }(s_1)=\arg {\max }_a(Q^{\ast }(s_1,\text{down}),Q^{\ast }(s_1,\text{up}))=\text{up},V^{\ast }(s_1)=\max (-8,6)=6.$

Verify: $V^{\ast }(s_p)=\frac{-8}{1-0.5}=-16$ ✓, and $6>-8$ ✓ — avoid the pit.

---

Example 7 — Real-world word problem (Cell H)

Forecast: cleaning pays but risks death; recharging is safe but idle. Which wins?

Step 1 — Identify the tuple $(S,A,P,R,\gamma )$ formally.

• $S=\{\text{High},\text{Low},\text{Dead}\}$.
• $A=\{\text{clean},\text{recharge}\}$.
• Transition function $P(s^{\prime }\mid s,a)$:
  • $P(\text{Dead}\mid \text{Low},\text{clean})=0.3$, $P(\text{Low}\mid \text{Low},\text{clean})=0.7$,
  • $P(\text{High}\mid \text{Low},\text{recharge})=1$.
• Reward function $R(s,a,s^{\prime })$ (payoff on the specific transition):
  • $R(\text{Low},\text{clean},\text{Low})=+3$, $R(\text{Low},\text{clean},\text{Dead})=-5$,
  • $R(\text{Low},\text{recharge},\text{High})=0$.
• $\gamma =0.9$; and the given terminal values $V^{\ast }(\text{High})=10$, $V^{\ast }(\text{Dead})=0$.

Why this step? Every word problem must first be pinned to the full tuple — especially writing $R(s,a,s^{\prime })$ with all three arguments so each English payoff maps to a specific transition — before any equation is legal. This mirrors 5.1.01-Reinforcement-Learning-Problem-Formulation.

Step 2 — $Q^{\ast }$ for "recharge". $Q^{\ast }(\text{Low,recharge})=0+0.9\cdot V^{\ast }(\text{High})=0+0.9\cdot 10=9.$ Why this step? Recharge is deterministic (prob 1) into terminal High, so the Bellman sum has a single term: immediate $0$ plus discounted terminal value $V^{\ast }(\text{High})$.

Step 3 — $Q^{\ast }$ for "clean" (Dead is terminal, $V^{\ast }(\text{Dead})=0$; clean can loop back to Low, so its value recurs): $Q^{\ast }(\text{Low,clean})=0.7[3+0.9V^{\ast }(\text{Low})]+0.3[-5+0.9\cdot 0].$ Assume the optimal action in Low is "clean" so $V^{\ast }(\text{Low})=Q^{\ast }(\text{Low,clean})=x$: $x=0.7(3+0.9x)+0.3(-5)=2.1+0.63x-1.5=0.6+0.63x.$ $x-0.63x=0.6\Rightarrow 0.37x=0.6\Rightarrow x\approx \mathrm{1.6216.}$ Why this step? Clean can loop back to Low, so its own value appears on both sides — solve the fixed-point equation exactly as in the self-loop examples.

Step 4 — Compare. $Q^{\ast }(\text{Low,recharge})=9>1.62=Q^{\ast }(\text{Low,clean})$, so ${\pi }^{\ast }(\text{Low})=\text{recharge}$. Why this step? The optimal policy in a state is the $\arg \max$ over its actions' Q-values; recharge has the higher Q, so it is chosen (and the "clean" assumption made in Step 3 turns out sub-optimal — that is fine, we compared both).

Verify: solving $0.37x=0.6$ gives $x\approx 1.6216$ ✓; and $9>1.6216$ ✓ — recharge, the death risk sinks cleaning.

---

Example 8 — Exam twist: coupled equations (Cell I)

Forecast: the values feed each other in a loop. Two unknowns, two equations.

Step 1 — Write both Bellman equations. $V^{\pi }(s_A)=2+0.5V^{\pi }(s_B),V^{\pi }(s_B)=1+0.5V^{\pi }(s_A).$ Why this step? Each state's value depends on the other's value — a coupled linear system, exactly what 5.2.01-Dynamic-Programming-inRL solves iteratively.

Step 2 — Substitute. Put the expression for $V^{\pi }(s_B)$ into the first equation to eliminate one unknown: $V^{\pi }(s_A)=2+0.5(1+0.5V^{\pi }(s_A))=2+0.5+0.25V^{\pi }(s_A)=2.5+0.25V^{\pi }(s_A).$ $0.75V^{\pi }(s_A)=2.5\Rightarrow V^{\pi }(s_A)=\frac{2.5}{0.75}=\frac{10}{3}\approx \mathrm{3.3333.}$ Why this step? Substitution collapses two equations into one equation in a single unknown, which we can then solve by ordinary algebra.

Step 3 — Recover $V^{\pi }(s_B)$. $V^{\pi }(s_B)=1+0.5\cdot \frac{10}{3}=1+\frac{5}{3}=\frac{8}{3}\approx \mathrm{2.6667.}$ Why this step? Back-substitution once one unknown is known.

Verify: plug back: $V^{\pi }(s_A)=2+0.5\cdot \frac{8}{3}=2+\frac{4}{3}=\frac{10}{3}$ ✓ and $V^{\pi }(s_B)=1+0.5\cdot \frac{10}{3}=\frac{8}{3}$ ✓. Both equations satisfied simultaneously.

---

Recall Which cell was hardest for you?

Cell G (negative self-loop) answer ::: $V^{\ast }=\frac{-8}{1-0.5}=-16$; sign flows straight through the geometric sum. Cell I (coupled) answer ::: $V^{\pi }(s_A)=\frac{10}{3},V^{\pi }(s_B)=\frac{8}{3}$; substitute then solve.