Exercises — Bellman equations

This is the Bellman expectation equation for $V^{\pi }$, so $X=V^{\pi }$.

• ${\sum }_a\pi (a\mid s)$ — average over the actions the fixed policy might pick (an expectation, not a max).
• ${\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)$ — average over where the environment might send you.
• $r$ — the reward paid on that one step.
• $\gamma X(s^{\prime })$ — discounted value of wherever you land.

The give-away that it is $V^{\pi }$ (not $V^{\ast }$) is the ${\sum }_a\pi (a\mid s)$: we are following a policy, not choosing the best.

The Discount Factor $\gamma$ is missing on the future term. Correct form: $V(s)=r+\gamma V(s^{\prime })$. Without it, an infinite stream of rewards $r=1$ sums to $\infty$.

Apply the expectation equation. Each action contributes $\pi (a\mid s)[r+\gamma V^{\pi }(\text{next})]$: $V^{\pi }(s)=0.6[2+0.9(10)]+0.4[-1+0.9(4)]$ $=0.6[11]+0.4[2.6]=6.6+1.04=\boxed{7.64}$

The optimality equation replaces the expectation by one observed sample and uses a max over next actions: $\text{target}=r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })=3+0.95(20)=3+19=\boxed{22}$ This is the bootstrapped estimate that Q-Learning chases.

$V^{\pi }$ is the policy-weighted average of the $Q$ values (this is the bridge in the parent's $Q^{\pi }$ derivation): $V^{\pi }(s^{\prime })={\sum }_{a^{\prime }}\pi (a^{\prime }\mid s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })=0.3(8)+0.7(5)=2.4+3.5=\boxed{5.9}$

The next state is $s$, so $V^{\pi }(s)$ appears on both sides: $V^{\pi }(s)=-1+0.9V^{\pi }(s)$ Move it over: $V^{\pi }(s)-0.9V^{\pi }(s)=-1\Rightarrow 0.1V^{\pi }(s)=-1$. $V^{\pi }(s)=\frac{-1}{1-0.9}=\boxed{-10}$ What it looks like: an infinite geometric sum $-1-0.9-0.9^2-\cdots =\frac{-1}{1-\gamma }$. Look at the figure — the reward stack shrinks by $\gamma$ each layer and converges.

From the parent's simplification: $0.55V^{\pi }(s_1)=-1+0.45V$ Substitute $V=-6$: $0.55V^{\pi }(s_1)=-1+0.45(-6)=-1-2.7=-3.7$ $V^{\pi }(s_1)=\frac{-3.7}{0.55}\approx \boxed{-6.727}$ Analysis: $s_1$ is slightly worse than $s_2/s_3$ because two of its four moves waste a step bouncing off a wall.

$V^{\pi }(s)={\sum }_{t=0}^{\infty }{\gamma }^t(1)=\frac{1}{1-\gamma }$ For $\gamma =0.99$: $V^{\pi }(s)=\frac{1}{0.01}=\boxed{100}$. As $\gamma \to 1$ the denominator $\to 0$, so $V^{\pi }(s)\to \infty$. That divergence is exactly why $\gamma \in [0,1)$ strictly — the boundary $\gamma =1$ breaks the infinite-horizon sum.

Step 1 — target (Bellman optimality, sampled): $\text{target}=5+0.9(12)=15.8$. Step 2 — TD error (the Bootstrapping correction): $\delta =\text{target}-Q(s,a)=15.8-10=5.8$. Step 3 — nudge toward it: $Q(s,a)\leftarrow Q(s,a)+\alpha \delta =10+0.1(5.8)=\boxed{10.58}$ This is Temporal Difference Learning in one line: move current estimate a fraction $\alpha$ toward the Bellman target.

Optimality uses the max over next actions: $Q^{\ast }(s,a)=r+\gamma {\max }_{a^{\prime }}{Q}^{\ast }(s^{\prime },a^{\prime })=4+0.8\max (7,9)=4+0.8(9)=4+7.2=\boxed{11.2}$

Two coupled equations: $V_A=0+0.5V_B,V_B=1+0.5V_A$ Substitute the first into the second: $V_B=1+0.5(0.5V_B)=1+0.25V_B$, so $0.75V_B=1$, $V_B=\frac{4}{3}\approx 1.333$. Then $V_A=0.5(\frac{4}{3})=\frac{2}{3}\approx \boxed{0.667}$, and $V_B\approx \boxed{1.333}$. This is a tiny instance of Dynamic Programming solving the Bellman system exactly.

• $V_1=2+0.5(0)=2$
• $V_2=2+0.5(2)=3$
• $V_3=2+0.5(3)=3.5$

Fixed point: $V=\frac{2}{1-0.5}=4$. The iterates $0,2,3,3.5,\dots$ climb toward $4$, halving the gap each step — this is value iteration (Dynamic Programming) converging as a contraction.

Terminal means no future value, so each action's value is just its reward. (a) $V^{\ast }(s)=\max (10,0)=\boxed{10}$ (greedy picks $g$). (b) $V^{\pi }(s)=0.5(10)+0.5(0)=\boxed{5}$ (uniform averages good and bad). (c) Gap $=10-5=\boxed{5}$. This gap is exactly what Policy Gradient Methods and value-based methods work to close by shifting probability toward $g$.

$|V^{\pi }(s)|=\left|{\sum }_{t=0}^{\infty }{\gamma }^t{R}_{t+1}\right|\le {\sum }_{t=0}^{\infty }{\gamma }^t{R}_{\max }=\frac{R_{\max }}{1-\gamma }$ $=\frac{3}{1-0.9}=\frac{3}{0.1}=\boxed{30}$ Every value function on this MDP lives inside $[-30,30]$ — a fact used to prove Bellman updates are contractions on a Markov Decision Process.

The symbol that distinguishes $V^{\ast }$ from $V^{\pi }$ ::: ${\max }_a$ (optimality) versus ${\sum }_a\pi (a\mid s)$ (expectation) Fixed-point value of a self-loop with reward $r$, discount $\gamma$ ::: $\frac{r}{1-\gamma }$ The TD target in Q-learning ::: $r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$ Value of a terminal state ::: $0$ Tightest bound on $|V^{\pi }|$ given $|R|\le R_{\max }$ ::: $\frac{R_{\max }}{1-\gamma }$