Exercises — Markov Decision Processes (MDP)

(a). The Markov property says the next state depends only on the current state and action, not the full history. Statement (b) is stronger (it says the next state is independent of the current one — false in general). Statement (c) is about rewards, not the Markov property, and rewards can be any real number.

• $S$ ::: situations (states)
• $A$ ::: decisions (actions)
• $P$ ::: randomness of the next situation (transition probability)
• $R$ ::: immediate payoff (reward)
• $\gamma$ ::: how much future matters (discount factor)

Here $R_{\max }$ is just "the constant per-step reward" — a single fixed number, not a function of the state. With $\gamma =1$ the return is $R_{\max }+R_{\max }+\cdots =\infty$. The geometric bound $\frac{R_{\max }}{1-\gamma }$ divides by $1-\gamma =0$, so the sum does not converge. We need $\gamma <1$ so far-away rewards shrink to zero and the total is finite. (Finite-horizon or episodic tasks can use $\gamma =1$ because the sum has finitely many terms.)

$s_4$ is an absorbing state (see the definition callout): it self-loops giving $+10$ forever — the episode does not end, so it is not "terminal". That endless stream is why we get a geometric series: $V^{\pi }(s_4)=10+0.9V^{\pi }(s_4)$ $0.1V^{\pi }(s_4)=10\Rightarrow V^{\pi }(s_4)=100.$ Equivalently $10(1+0.9+0.9^2+\cdots )=\frac{10}{1-0.9}=100$.

Every step earns reward $0$ until the goal, so each state just discounts the state to its right: $V^{\pi }(s_3)=0+0.9\times 100=90$ $V^{\pi }(s_2)=0+0.9\times 90=81$ $V^{\pi }(s_1)=0+0.9\times 81=72.9$ Check the intuition: $s_1$ is 3 steps from goal, so $V^{\pi }(s_1)={\gamma }^3\cdot 100=0.9^3\cdot 100=72.9$. ✓

Split the expectation over the two branches (the red arrow is the 0.8 branch that reaches the goal). Note the 0.2 branch is a self-loop back into $s_3$, so it carries a $\gamma V^{\pi }(s_3)$ term: $V^{\pi }(s_3)=0.8[0+0.9\cdot 100]+0.2[0+0.9V^{\pi }(s_3)]$ $V^{\pi }(s_3)=72+0.18V^{\pi }(s_3)$ $0.82V^{\pi }(s_3)=72\Rightarrow V^{\pi }(s_3)=\frac{72}{0.82}\approx \mathrm{87.8.}$ Lower than the deterministic $90$ because the $0.2$ self-loop delays reaching the goal.

Compute each action-value $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+80)+0.5(-10+30)=0.5\cdot 100+0.5\cdot 20=60$ Since $60>55$, ${\pi }^{\ast }(s_1)=a_2$, winning by $60-55=5$. The red arrow marks the higher expected branch that tips the decision.

Set $Q^{\ast }(s_1,a_2)<Q^{\ast }(s_1,a_1)$: $0.5(20+80)+0.5(r+30)<55$ $50+0.5r+15<55$ $0.5r<-10\Rightarrow r<-20.$ So once the bad outcome is worse than $-20$ (strictly), safe wins. At exactly $r=-20$ both give $55$ — a tie, and either is optimal.

At the goal, $V^{\pi }(s_4)=\frac{10}{1-\gamma }$. For $\gamma =0.9$ that is $100$; for $\gamma =0.99$ it is $\frac{10}{0.01}=1000$. Meanwhile $V^{\pi }(s_1)={\gamma }^3{V}^{\pi }(s_4)$, so the ratio is ${\gamma }^3$: it rises from $0.9^3=0.729$ to $0.99^3\approx 0.970$. A larger $\gamma$ discounts the 3-step distance less, so far-away states keep almost the full goal value.

Write both Bellman equations (deterministic transitions): $V(A)=1+0.5V(B),V(B)=3+0.5V(A).$ Substitute the second into the first: $V(A)=1+0.5(3+0.5V(A))=1+1.5+0.25V(A)$ $0.75V(A)=2.5\Rightarrow V(A)=\frac{2.5}{0.75}=\frac{10}{3}\approx \mathrm{3.333.}$ Then $V(B)=3+0.5\cdot \frac{10}{3}=3+\frac{5}{3}=\frac{14}{3}\approx 4.667$. Sanity check: the reward stream from $A$ is $1,3,1,3,\dots$ discounted by $0.5$: $1+0.5\cdot 3+0.25\cdot 1+\cdots$ which sums to $\frac{10}{3}$. ✓

Looping value from $A$ is $V(A)=\frac{10}{3}\approx 3.333$ (from 4.1). Leaving: $Q(A,\text{leave})=4+0.5\cdot V(T)=4+0=4$. Since $4>3.333$, leaving is better — the one-shot $+4$ beats the discounted loop. To make looping preferred you'd raise the loop rewards or lower the exit reward; e.g. exit reward $+3$ gives $Q=3<3.333$ and looping wins.

Each self-loop is a geometric stream: choosing $a_i$ forever gives $\frac{r_i}{1-\gamma }$. The Bellman optimality equation is $V^{\ast }(s)=\max \{r_1+\gamma V^{\ast }(s),r_2+\gamma V^{\ast }(s)\}.$ Why we can pull $\gamma V^{\ast }(s)$ out of the $\max$: both branches share the identical term $\gamma V^{\ast }(s)$ (same state $s$, same value). Adding the same constant $c$ to two numbers never changes which one is larger, so $\max (x+c,y+c)=\max (x,y)+c$. Here $c=\gamma V^{\ast }(s)$, giving $V^{\ast }(s)=\max (r_1,r_2)+\gamma V^{\ast }(s).$ Solving: $V^{\ast }(s)=\frac{\max (r_1,r_2)}{1-\gamma }$, and ${\pi }^{\ast }(s)=\arg {\max }_i{r}_i$. The optimal policy just commits to the better constant reward forever.

Substitute $a=\pi (s)$ directly into the definition of $Q^{\pi }$: $Q^{\pi }(s,\pi (s))={\sum }_{s^{\prime }}P(s^{\prime }\mid s,\pi (s))[R(s,\pi (s),s^{\prime })+\gamma V^{\pi }(s^{\prime })].$ The right-hand side is character-for-character the definition of $V^{\pi }(s)$. Hence $V^{\pi }(s)=Q^{\pi }(s,\pi (s))$. In words: the value of a state is exactly the value of taking the action your policy prescribes there, then continuing under $\pi$.

With $V_0\equiv 0$, only immediate rewards survive one sweep:

• $V_1(s_1)=0+0.9\cdot 0=0$
• $V_1(s_2)=0+0.9\cdot 0=0$
• $V_1(s_3)=0+0.9\cdot 0=0$
• $V_1(s_4)=10+0.9\cdot 0=10$ Only $s_4$ (the absorbing goal, which has a non-zero immediate reward) has a non-zero estimate. Reward information "spreads backward" one step per sweep — after enough sweeps it reaches $s_1$. This is exactly how 5.4.01-Q-Learning and value iteration propagate value; see 5.1.04-Bellman-Equations.