Exercises — Policies and value functions

• Policy $\pi$ ::: a rule that turns a state $s$ into an action (or a probability over actions), written $\pi (a\mid s)$.
• State value $V^{\pi }(s)$ ::: expected discounted total reward if you start in $s$ and act by $\pi$ forever.
• Action value $Q^{\pi }(s,a)$ ::: same idea, but you force the first action to be $a$, then follow $\pi$.

(a) policy — it assigns a probability to an action given a state. (b) action-value — it scores a (state, action) pair. (c) state-value — it scores a state alone. (d) policy — a deterministic rule from state to action.

It is a weighted average of the $Q$-values, where the weights are the policy probabilities $\pi (a\mid s)$. Since ${\sum }_a\pi (a\mid s)=1$, the weights are a valid probability distribution — so $V^{\pi }(s)$ can never exceed the best $Q$ or fall below the worst $Q$ in that state.

WHAT: every step gives the same $c=3$. WHY the geometric shortcut: identical rewards discounted by a constant factor form a geometric series — exactly the teal bars in the figure above, but with $c=3$. $V^{\pi }(s)=\frac{c}{1-\gamma }=\frac{3}{1-0.8}=\frac{3}{0.2}=15.$

Bellman equation (only one next state, itself): $V^{\pi }(s_2)=2+0.9V^{\pi }(s_2).$ WHY: immediate reward $2$, then discounted value of landing back in $s_2$. Solve: $V^{\pi }(s_2)-0.9V^{\pi }(s_2)=2\Rightarrow 0.1V^{\pi }(s_2)=2\Rightarrow V^{\pi }(s_2)=20.$ (Matches the geometric shortcut $2/(1-0.9)=20$ — the orange ceiling from the figure with $c=2$.)

Only one next state, so the sum collapses to one term: $Q^{\pi }(s_1,a_1)=r+\gamma V^{\pi }(s_2)=1+0.9\cdot 20=1+18=19.$

From 2.2 we already have $V^{\pi }(s_2)=20$. Bellman equation for $s_1$: $V^{\pi }(s_1)=1+0.9[0.5V^{\pi }(s_1)+0.5V^{\pi }(s_2)].$ WHY term by term:

• The leading $1$ is the immediate reward collected on this step from $s_1$ — undiscounted, because you get it now.
• The factor $0.9=\gamma$ multiplies the whole future, because everything after this step is one step away.
• Inside the bracket is the expectation over next states: with probability $0.5$ you land back in $s_1$ (contributing $V^{\pi }(s_1)$) and with probability $0.5$ you reach $s_2$ (contributing $V^{\pi }(s_2)$). We average because the next state is random.

Plug $V^{\pi }(s_2)=20$: $V^{\pi }(s_1)=1+0.9[0.5V^{\pi }(s_1)+10]=1+0.45V^{\pi }(s_1)+9.$ $V^{\pi }(s_1)-0.45V^{\pi }(s_1)=10\Rightarrow 0.55V^{\pi }(s_1)=10\Rightarrow V^{\pi }(s_1)=\frac{10}{0.55}\approx \mathrm{18.18.}$ Interpretation: $s_1<s_2$ because you might loop back into the lower-reward state before escaping.

First, a fixed number, then a coupled system of two equations. The action value of $a_1$ is not self-referential — it lands in $s_2$ whose value we already know — so we compute it once as a constant: $Q^{\pi }(s_1,a_1)=1+0.9\cdot 20=19.$ The genuine coupling is between the two unknowns $V^{\pi }(s_1)$ and $Q^{\pi }(s_1,a_2)$, giving a linear system of two equations in two unknowns: $\text{(i)}{V}^{\pi }(s_1)=0.8\cdot 19+0.2Q^{\pi }(s_1,a_2)=15.2+0.2Q^{\pi }(s_1,a_2),$ $\text{(ii)}{Q}^{\pi }(s_1,a_2)=0.5+0.9V^{\pi }(s_1).$ Substitute (i) into (ii): $Q^{\pi }(s_1,a_2)=0.5+0.9(15.2+0.2Q^{\pi }(s_1,a_2))=0.5+13.68+0.18Q^{\pi }(s_1,a_2).$ $0.82Q^{\pi }(s_1,a_2)=14.18\Rightarrow Q^{\pi }(s_1,a_2)\approx \mathrm{17.29.}$ Since $19>17.29$, action $a_1$ is better — consistent with $\pi$ favouring it (80%).

(a) Weighted average: $V^{\pi }(s)=0.5\cdot 6+0.3\cdot 10+0.2\cdot 2=3+3+0.4=\mathrm{6.4.}$ (b) Greedy picks the max $Q$: ${\max }_a{Q}^{\pi }(s,a)=10$ (action $b$). (c) Improvement $=10-6.4=3.6$. WHY it improved: moving probability off the worse actions ($a,c$) onto the best action ($b$) can only raise the average — this is the seed idea of the policy improvement theorem.

Substitute $Q^{\ast }$ into $V^{\ast }={\max }_a{Q}^{\ast }$: $V^{\ast }(s)={\max }_a{\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma V^{\ast }(s^{\prime })].$ The optimal policy is greedy with respect to $Q^{\ast }$. To keep the policy-as-distribution formalism used everywhere else on this page, we write it as a distribution that puts all its mass on the maximizing action(s): ${\pi }^{\ast }(a\mid s)=\{\begin{array}{ll}1& \text{if }a\in \arg {\max }_{a^{\prime }}{Q}^{\ast }(s,a^{\prime })\\ 0& \text{otherwise.}\end{array}$ (If several actions tie for the max, any split of the probability among them is also optimal.) WHY: if you always take a highest-$Q^{\ast }$ action, you are, by definition, achieving the max in the equation above at every state — that is what "optimal" means. This is the fixed point that value iteration and Q-learning chase.

Lower bound: every reward $R_{t+k+1}\ge 0$ and every weight (${\gamma }^k$, plus the probabilities inside the average) is $\ge 0$, so the expected sum is $\ge 0$. Upper bound: replace each future reward $R_{t+k+1}$ by its ceiling $R_{\max }$: $V^{\pi }(s)={\mathbb{E}}_{\pi }\left[{\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}\right]\le {\sum }_{k=0}^{\infty }{\gamma }^k{R}_{\max }=R_{\max }{\sum }_{k=0}^{\infty }{\gamma }^k=\frac{R_{\max }}{1-\gamma }.$ WHY the swap is legal: replacing each random reward by a value at least as large can only increase the sum, and the expectation ${\mathbb{E}}_{\pi }$ preserves inequalities (averaging bigger numbers gives a bigger average). Once every reward is the constant $R_{\max }$, there is nothing random left, so ${\mathbb{E}}_{\pi }$ drops away and we get the geometric series from the figure — finite precisely because $0\le \gamma <1$. Number: $\frac{2}{1-0.9}=\frac{2}{0.1}=20$. (Consistent with the $s_2$ self-loop capping exactly at $20$ when reward is always $2$.)

Write $V(p)=19p+17.29(1-p)=17.29+(19-17.29)p=17.29+1.71p$, for $p\in [0,1]$. The coefficient $1.71>0$, so $V(p)$ is increasing in $p$; its maximum on $[0,1]$ is at $p=1$: $V_{\max }=19p+17.29(1-p){|}_{p=1}=19.$ Interpretation: the value-maximizing (optimal) policy puts all its probability on the higher-$Q$ action $a_1$ — i.e. ${\pi }^{\ast }(a_1\mid s)=1$, matching the greedy distribution from Exercise 4.2. This is exactly why deterministic greedy policies are enough to be optimal in a finite MDP.