Worked examples — Bellman equations

This is the practice companion to Bellman equations. The parent note built the four core equations from scratch. Here we do the opposite of theory: we hunt down every kind of situation the Bellman equations can throw at you and solve one representative of each — including the weird corner cases (terminal states, $\gamma =0$, $\gamma \to 1$, a real-world word problem, and an exam trap).

If any symbol below feels unfamiliar, it was defined in the parent note; skim these prerequisites too: Markov Decision Process, Discount Factor, Bootstrapping.

Recall Quick self-test on the symbols

$S_t$ ::: the state at time step $t$; $S_0$ is the start, $S_1$ is one move later, etc. $R_{t+1}$ ::: the reward that arrives one tick after you act at time $t$. $V^{\pi }(s)$ ::: expected total discounted reward starting in $s$ and always acting by $\pi$. $Q^{\pi }(s,a)$ ::: same, but forced to take action $a$ first, then follow $\pi$. $V^{\ast }(s),Q^{\ast }(s,a)$ ::: the best possible versions — you get to pick the action that maximises value. $p(s^{\prime },r\mid s,a)$ ::: probability of landing in $s^{\prime }$ and getting reward $r$ after doing $a$ in $s$ — the world's dynamics. $\gamma$ (discount) ::: a knob in $[0,1)$ that shrinks future rewards; ${\gamma }^t$ multiplies the reward $t$ steps away.

---

The scenario matrix

Every Bellman problem is one (or a blend) of the cells below. The goal of this page is to leave no empty cell.

Cell	What makes it special	The trap it hides	Example
A. Deterministic $V^{\pi }$	one action, one outcome — no averaging	forgetting $\gamma$ still compounds	Ex 1
B. Stochastic $V^{\pi }$	policy spreads probability over actions	weighting each branch by $\pi (a\mid s)$	Ex 2
C. Terminal / zero input	$V(\text{terminal})=0$ by definition	recursion must stop there	Ex 3
D. $\gamma =0$ (degenerate)	agent is myopic, ignores the future	value collapses to one-step reward	Ex 4
E. $\gamma \to 1$ (limiting)	future weighted almost equally	sum can blow up unless it terminates	Ex 4
F. Optimality $V^{\ast }$ / $Q^{\ast }$	$\max$ replaces the policy average	using ${\sum }_a\pi$ instead of ${\max }_a$	Ex 5
G. Real-world word problem	you must build the MDP yourself	mislabelling reward vs. value	Ex 6
H. Exam twist ($Q$-update)	sample-based bootstrapping	mixing target with old estimate	Ex 7
I. Self-loop / infinite geometric	state can return to itself forever	must sum a geometric series	Ex 8

We now walk cells A → I. Each example with geometry carries its own figure; the text tells you exactly what to look at in it.

---

Ex 1 — Cell A: Deterministic chain

Forecast: guess before computing — will $V^{\pi }(s_1)$ be smaller (more negative) or larger than $-3$? Write it down.

What the figure shows: four circles $s_1,s_2,s_3,s_4$ in a row, white arrows (each labelled $r=-1$) pointing right, and under each circle the value we are about to compute. The amber circle is the terminal $s_4$ with value $0$. The cyan arrow along the bottom points left — the direction the recursion actually flows, because each value is built from the one to its right. Keep your eye on that cyan arrow as you read the steps: the numbers fill in from $s_4$ leftward.

Step 1 — Write Bellman for a deterministic move. Because there is exactly one action and one outcome, the double sum ${\sum }_a\pi (a\mid s){\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)$ collapses to a single term (here $\pi (a\mid s)=1$ for "right" and $p(s^{\prime },r\mid s,a)=1$ for the one landing spot): $V^{\pi }(s_i)=-1+0.9V^{\pi }(s_{i+1}).$ Why this step? Determinism kills all averaging, so the general Bellman equation shrinks to one clean recursive line.

Step 2 — Anchor the recursion at the terminal. $V^{\pi }(s_4)=0$ (the amber circle). Why? A terminal state has no future, so its value is exactly zero — this is the base case that stops the recursion (Cell C in disguise).

Step 3 — Unroll backwards (follow the cyan arrow in the figure, right to left): $V^{\pi }(s_3)=-1+0.9(0)=-1,$ $V^{\pi }(s_2)=-1+0.9(-1)=-1.9,$ $V^{\pi }(s_1)=-1+0.9(-1.9)=-\mathrm{2.71.}$ Why backwards? Each value depends only on the one after it, and $s_4$ is the only value we already know.

Verify: Sum the discounted rewards directly from $s_1$: three steps of $-1$ discounted by $1,0.9,0.81$: $-1+0.9(-1)+0.81(-1)=-\mathrm{2.71.}✓$ Our forecast: $-2.71>-3$ because discounting softens the two later penalties.

---

Ex 2 — Cell B: Stochastic policy (the parent's grid, finished)

What the figure shows: the four cells laid out as a 2×2 grid. From $s_1$ (top-left, cyan) the four white arrows show where each action leads — "right" to $s_2$, "down" to $s_3$, and "left"/"up" bounce off the outer wall back into $s_1$ (curved arrows). $s_4$ (amber, bottom-right) is the terminal goal. Reading the four arrows out of $s_1$ is exactly how we count which branches land where — that is where the $0.55$ and $0.45$ below come from.

Setting up the shorthand. By the symmetry of the grid the two "middle" states $s_2$ and $s_3$ have equal value; we give that shared number a short name: $V:=V^{\pi }(s_2)=V^{\pi }(s_3).$ So from here on, a lone "$V$" means exactly this shared middle-state value — nothing else. The other unknown keeps its full name $V^{\pi }(s_1)$.

Forecast: the random policy wanders and bumps walls, so should $|V^{\pi }(s_1)|$ be larger or smaller than the deterministic $-2.71$?

Step 1 — Derive the equation for $s_1$ from its four arrows. Read the figure: from $s_1$, "right" → $s_2$ (value $V$), "down" → $s_3$ (value $V$), "left" and "up" bounce off the wall and stay in $s_1$. Every step costs $-1$, each action has probability $0.25$: $V^{\pi }(s_1)=0.25[-1+0.9V]+0.25[-1+0.9V]+0.25[-1+0.9V^{\pi }(s_1)]+0.25[-1+0.9V^{\pi }(s_1)].$ Collect terms: the four $0.25\cdot (-1)$ pieces sum to $-1$; the two $V$-branches give $0.25\cdot 0.9\cdot 2=0.45$ in front of $V$; the two self-loop branches give $0.25\cdot 0.9\cdot 2=0.45$ in front of $V^{\pi }(s_1)$: $V^{\pi }(s_1)=-1+0.45V+0.45V^{\pi }(s_1).$ Move the self-term across: $V^{\pi }(s_1)-0.45V^{\pi }(s_1)=-1+0.45V$, i.e. 0.55\,V^\pi(s_1) = -1 + 0.45\,V. \tag{eq. 1} Why this step? This is where the mysterious coefficients come from: $0.55=1-0.45$ is "1 minus the discounted self-loop weight", and $0.45=2\times 0.25\times 0.9$ is "the two branches that escape to a middle state, discounted". Nothing is quoted — it is counted off the arrows.

Step 2 — Bellman for the middle state, in terms of $V$. From $s_2$ (by symmetry $s_3$ is identical): "left" returns to $s_1$ (reward $-1$), "down" reaches terminal $s_4$ with $V^{\pi }(s_4)=0$ (reward $-1$), and "right"/"up" bump walls and stay in $s_2$ (reward $-1$ each). Each action has probability $0.25$: $V=0.25[-1+0.9V^{\pi }(s_1)]+0.25[-1+0.9\cdot 0]+0.25[-1+0.9V]+0.25[-1+0.9V].$ Why this step? Every action must be enumerated — including the two wall-bumps that keep you in $s_2$ (Cell B's trap is forgetting them). Note the "down" branch uses the terminal value $0$, not $V$.

Step 3 — Simplify eq. 2. The two self-loop branches give $0.45V$; the $s_1$-branch gives $0.225V^{\pi }(s_1)$; the terminal branch contributes only its $-1$ reward: V = -1 + 0.225\,V^\pi(s_1) + 0.45\,V \;\Rightarrow\; 0.55\,V = -1 + 0.225\,V^\pi(s_1). \tag{eq. 2}

Step 4 — Solve the 2×2 linear system. From eq. 1, $V^{\pi }(s_1)=\frac{-1+0.45V}{0.55}$. Substitute into eq. 2 and solve the two lines together: $V\approx -3.846,V^{\pi }(s_1)\approx -\mathrm{4.966.}$ Why linear algebra? The Bellman expectation equation is linear in the unknown values, so a fixed policy always reduces to solving $A\mathbf{v}=\mathbf{b}$ — the trick that powers policy evaluation in Dynamic Programming.

Verify (use tolerance $\pm 0.01$ on rounded values). Plug the exact solutions into eq. 1: $0.55V^{\pi }(s_1)=-1+0.45V$ holds identically. Numerically, eq. 1: $0.55(-4.966)=-2.731$ and $-1+0.45(-3.846)=-2.731$ — match. Eq. 2: $0.55(-3.846)=-2.115$ and $-1+0.225(-4.966)=-2.117$; the tiny $0.002$ gap is pure rounding of $V^{\pi }(s_1)$ to three decimals — with the exact fractions both sides equal $-\frac{100}{47}\approx -2.1277$. $✓$ Forecast answer: $V^{\pi }(s_1)\approx -4.97$ is far more negative than $-2.71$ — random wandering and repeated wall-bumps pile up many extra penalty steps.

---

Ex 3 — Cell C: Terminal / zero degenerate input

Forecast: guess — is it $0$, or the reward you earned to arrive there?

Step 1 — Read the definition. $V^{\pi }(s_T)=\mathbb{E}[{\sum }_{t=0}^{\infty }{\gamma }^t{R}_{t+1}\mid S_0=s_T]$ — recall $S_0$ is the start state and $R_{t+1}$ is the reward that arrives one tick after acting. From a terminal state, no more rewards ever occur, so every $R_{t+1}=0$. Why this step? Value counts future reward. The reward for entering $s_T$ belongs to the previous state's equation, not to $s_T$ itself — this is the trap.

Step 2 — Conclude. $V^{\pi }(s_T)=0$ and likewise $Q^{\pi }(s_T,a)=0$ for all $a$.

Verify: In Ex 1 we used $V^{\pi }(s_4)=0$ and the direct-sum check still matched $-2.71$. If we had wrongly set $V^{\pi }(s_4)=-1$ (the arrival reward), the recursion would give $V^{\pi }(s_1)=-1+0.9(-1+0.9(-1+0.9(-1)))=-3.439$, contradicting the direct sum $-2.71$. $✓$ So $0$ is correct.

---

Ex 4 — Cells D & E: Sweeping the discount factor

What the figure shows: the curve $V=\frac{2}{1-\gamma }$ plotted against the discount $\gamma$ on the horizontal axis. Two amber dots mark our worked values ($\gamma =0\Rightarrow V=2$ and $\gamma =0.5\Rightarrow V=4$). As you slide right along the curve toward the dashed white line at $\gamma =1$, watch the curve rocket upward — that vertical blow-up is Cell E's divergence made visible.

Forecast: which $\gamma$ gives the biggest value, and does any give infinity?

Step 1 — Bellman for a self-loop. $V^{\pi }(s)=2+\gamma V^{\pi }(s)$, so $V^{\pi }(s)=\frac{2}{1-\gamma }$. Why this closed form? Solving $v=2+\gamma v$ algebraically is exact — a self-loop is the simplest possible recursion.

Step 2 — Cell D, $\gamma =0$ (myopic). $V^{\pi }(s)=\frac{2}{1-0}=2$ (left amber dot). Why? With $\gamma =0$ the future is worthless; value equals the single immediate reward. The whole $\sum {\gamma }^t$ collapses to its $t=0$ term.

Step 3 — Middle, $\gamma =0.5$. $V^{\pi }(s)=\frac{2}{0.5}=4$ (right amber dot).

Step 4 — Cell E, $\gamma \to 1$. $\frac{2}{1-\gamma }\to \infty$ (the blow-up at the dashed line). Why? Un-discounted, an endless stream of $+2$ never stops summing — exactly the divergence Mistake 1 in the parent warns about. This is why we require $\gamma <1$ for continuing tasks.

Verify: $\gamma =0.5$ geometric sum: $2{\sum }_{t=0}^{\infty }0.5^t=2\cdot \frac{1}{1-0.5}=4$. $✓$ And $\frac{2}{1-0}=2$. $✓$

---

Ex 5 — Cell F: Optimality (max, not average)

Forecast: the immediate reward favours $a_2$, but which action wins overall?

Step 1 — Compute each action's $Q^{\ast }$. With deterministic transitions the model $p(s^{\prime },r\mid s,a)$ puts probability $1$ on one $(s^{\prime },r)$ pair, so the Bellman optimality equation for $Q^{\ast }$ becomes a single term: $Q^{\ast }(s,a_1)=0+0.9(10)=9,Q^{\ast }(s,a_2)=3+0.9(4)=\mathrm{6.6.}$ Why $Q^{\ast }$ first? $V^{\ast }(s)={\max }_a{Q}^{\ast }(s,a)$ — you must know each action's value before you can maximise.

Step 2 — Take the max, not the average. $V^{\ast }(s)=\max (9,6.6)=9,{\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a)=a_1.$ Why max? Under optimality we choose; we do not blend actions with $\pi (a\mid s)$. Using the policy-average $\frac{1}{2}(9)+\frac{1}{2}(6.6)=7.8$ would be the trap — that answers "value of a coin-flip policy", not "value of playing optimally". This distinction is the engine of Q-Learning and Temporal Difference Learning.

Verify: $\max (9,6.6)=9$ and $9\ne 7.8$, confirming the greedy choice differs from the average. The larger discounted future ($0.9\times 10=9$) beats the larger immediate reward ($3$). $✓$

---

Ex 6 — Cell G: Real-world word problem

Forecast: should Full be worth more than Low, and by roughly how much?

Step 1 — Build the MDP. States: Full, Low, Dead (terminal, $V=0$). Rewards $+5$ per active hour. This is the modelling step — turning prose into the transition model $p(s^{\prime },r\mid s,a)$. Why? Bellman needs explicit transition probabilities before any arithmetic can start.

Step 2 — Bellman for Low (stochastic branch). $V^{\pi }(\text{Low})=5+0.8[0.5V^{\pi }(\text{Low})+0.5(0)].$ Solve: $V^{\pi }(\text{Low})-0.4V^{\pi }(\text{Low})=5\Rightarrow 0.6V^{\pi }(\text{Low})=5\Rightarrow V^{\pi }(\text{Low})=\frac{5}{0.6}\approx \mathrm{8.333.}$ Why include the Dead branch as $0$? The 50% death path contributes reward $5$ this hour but no future value (Cell C again).

Step 3 — Bellman for Full (deterministic to Low). $V^{\pi }(\text{Full})=5+0.8V^{\pi }(\text{Low})=5+0.8(8.333)=\mathrm{11.667.}$

Verify: Re-plug Low: $5+0.8(0.5\cdot 8.333)=5+3.333=8.333$. $✓$ And Full $=5+0.8(8.333)=11.667$. $✓$ Full is worth more than Low (11.67 vs 8.33) — sensible, since Full guarantees one safe extra hour before risk begins.

---

Ex 7 — Cell H: Exam twist (sample-based Q-update)

Forecast: the reward+future looks like $15.8$ but $\alpha =0.1$ — how far does $Q$ actually move? Guess the new value before reading on.

Step 1 — Form the TD target from Bellman optimality. The optimality equation says the true value satisfies $Q^{\ast }(s,a)=\mathbb{E}[r+\gamma {\max }_{a^{\prime }}{Q}^{\ast }(s^{\prime },a^{\prime })]$. One sampled experience $(s,a,r,s^{\prime })$ gives a single-sample estimate of that expectation, called the temporal difference target: $\text{target}=r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })=5+0.9(12)=5+10.8=\mathrm{15.8.}$ Why this is the target? We cannot average over all outcomes — we only saw one transition — so we bootstrap: we plug our current estimate of the next state's best value into the Bellman right-hand side. This is Bootstrapping in action.

Step 2 — Move a fraction $\alpha$ toward the target (do NOT jump all the way). $Q(s,a)\leftarrow Q(s,a)+\alpha [\text{target}-Q(s,a)]=10+0.1(15.8-10)=10+0.1(5.8)=\mathrm{10.58.}$ Why not set $Q$ straight to $15.8$? The target is one noisy sample; $\alpha =0.1$ blends new evidence with the old estimate so learning is stable. The trap the matrix warns about is over-writing the old value entirely — mixing target with estimate is the whole point of the update.

Verify: TD error $=15.8-10=5.8$; update $=0.1\times 5.8=0.58$; new $Q=10+0.58=10.58$. Also $5+0.9\cdot 12=15.8$. $✓$

---

Ex 8 — Cell I: Self-loop with escape (infinite geometric series)

Forecast: with $\gamma =1$ this looks dangerous — will it diverge like Ex 4's Cell E, or does the guaranteed escape save us? Guess yes/no first.

Step 1 — Write Bellman with a self-reference. The state appears on both sides because one branch loops back: $V^{\pi }(s)=0.7[-1+\gamma V^{\pi }(s)]+0.3[+10+\gamma \cdot 0],\gamma =1.$ So $V^{\pi }(s)=0.7[-1+V^{\pi }(s)]+0.3(10)$. Why does $\gamma =1$ not blow up here? Because with prob $0.3$ per step the episode terminates, so the expected number of loops is finite (a geometric distribution) — Cell E's divergence only happens when nothing ever stops. The escape probability is our safety valve.

Step 2 — Solve the linear equation. $V^{\pi }(s)=-0.7+0.7V^{\pi }(s)+3\Rightarrow V^{\pi }(s)-0.7V^{\pi }(s)=2.3\Rightarrow 0.3V^{\pi }(s)=2.3\Rightarrow V^{\pi }(s)=\frac{2.3}{0.3}\approx \mathrm{7.667.}$

Step 3 — See the hidden geometric series. Equivalently, the expected number of loop steps before escaping is $\frac{0.7}{0.3}$ (a geometric mean-number-of-failures), each costing $-1$, and finally you collect $+10$ on exit: $V^{\pi }(s)=-\frac{0.7}{0.3}+10=-2.333+10=\mathrm{7.667.}$ Why this matches: summing ${\sum }_{k\ge 0}0.7^k$ weighted rewards is exactly what solving the self-referential Bellman line does for you — the algebra is the geometric series.

Verify: Both methods give $\frac{23}{3}\approx 7.667$: Bellman $\frac{2.3}{0.3}=\frac{23}{3}$, and escape-count $-\frac{7}{3}+10=\frac{23}{3}$. $✓$

---

Recall Which Bellman operator do you use for a

fixed policy vs. the optimal value? Fixed policy $V^{\pi }$ ::: expectation, ${\sum }_a\pi (a\mid s)(\cdots )$ — linear, solvable by linear algebra. Optimal $V^{\ast }$ ::: maximum, ${\max }_a(\cdots )$ — non-linear, solved by value/policy iteration.

Related deep dives worth chaining next: Policy Gradient Methods (when you optimise the policy directly instead of via values) and the Hinglish walkthrough.