Reinforcement Learning Exercise 4.1

Example 4.1 Consider the $4 \times 4$4×4 gridworld shown below.

The nonterminal states are $\mathcal S = \{1, 2, . . . , 14\}$S={1,2,...,14}. There are four actions possible in each state, $\mathcal A = \{up, down, right, left\}$A={up,down,right,left}, which deterministically cause the corresponding state transitions, except that actions that would take the agent off the grid in fact leave the state unchanged. Thus, for instance, $p(6,.1\mid 5, right) = 1$p(6,.1∣5,right)=1, $p(7,.1\mid 7, right) = 1$p(7,.1∣7,right)=1, and $p(10, r \mid 5, right) = 0$p(10,r∣5,right)=0 for all $r \in \mathcal R$r∈R. This is an undiscounted, episodic task. The reward is $-1$−1 on all transitions until the terminal state is reached. The terminal state is shaded in the figure (although it is shown in two places, it is formally one state). The expected reward function is thus $r(s, a, s0) = -1$r(s,a,s0)=−1 for all states $s$s, $s'$s′ and actions $a$a. Suppose the agent follows the equiprobable random policy (all actions equally likely). The left side of Figure 4.1 shows the sequence of value functions ${v_k}$vk​ computed by iterative policy evaluation. The final estimate is in fact $v_\pi$vπ​, which in this case gives for each state the negation of the expected number of steps from that state until termination.

Exercise 4.1 In Example 4.1, if $\pi$π is the equiprobable random policy, what is $q_\pi(11, down)$qπ​(11,down)? What is $q_\pi(7, down)$qπ​(7,down)?
Here, we can use the result of exercise 3.13 for calculation. The result of exercise 3.13 is :
$q_\pi(s,a) = \sum_{s'} \biggl \{ P_{s,s'}^a \cdot \Bigl [ R_{s,s'}^a + \gamma \cdot v_\pi(s') \Bigr ] \biggr \}$qπ​(s,a)=s′∑​{Ps,s′a​⋅[Rs,s′a​+γ⋅vπ​(s′)]}
where $P_{s, s'}^a = p(s' \mid s,a)$Ps,s′a​=p(s′∣s,a) and $R_{s,s'}^a = \mathbb E_\pi(r \mid s,a,s')$Rs,s′a​=Eπ​(r∣s,a,s′).
So,
$\begin{aligned} q_\pi(11,down) &= P_{11, 7}^{down} \cdot \Bigl [ R_{11, 7}^{down} + \gamma \cdot v_\pi(7)\Bigr ] + P_{11, 10}^{down} \cdot \Bigl [ R_{11, 10}^{down} + \gamma \cdot v_\pi(10)\Bigr ] \\ & \quad + P_{11, 11}^{down} \cdot \Bigl [ R_{11, 11}^{down} + \gamma \cdot v_\pi(11)\Bigr ] + P_{11, terminal}^{down} \cdot \Bigl [ R_{11, terminal}^{down} + \gamma \cdot v_\pi(terminal)\Bigr ] \\ &= 0+0+0+p(terminal \mid 11, down) \cdot \biggl \{ \sum_{s'} \Bigl [r\cdot p(r \mid 11, down, s') \Bigr ] + \gamma \cdot v_\pi(terminal)\biggr \} \\ &=1 \cdot \biggl \{ \Bigl [ (-1)\cdot p(-1 \mid 11, down, 7) + (-1) \cdot p(-1 \mid 11, down, 10) \\ &\quad + (-1) \cdot p(-1 \mid 11, down, 11) + 0 \cdot p(0 \mid 11, down, terminal)\Bigr ] + \gamma \cdot 0\biggr \} \\ &=1 \cdot \biggl \{ \Bigl [ (-1)\cdot 0 + (-1) \cdot 0 + (-1) \cdot 0 + 0 \cdot 1\Bigr ] + \gamma \cdot 0\biggr \} \\ &= 0 \end{aligned}$qπ​(11,down)​=P11,7down​⋅[R11,7down​+γ⋅vπ​(7)]+P11,10down​⋅[R11,10down​+γ⋅vπ​(10)]+P11,11down​⋅[R11,11down​+γ⋅vπ​(11)]+P11,terminaldown​⋅[R11,terminaldown​+γ⋅vπ​(terminal)]=0+0+0+p(terminal∣11,down)⋅{s′∑​[r⋅p(r∣11,down,s′)]+γ⋅vπ​(terminal)}=1⋅{[(−1)⋅p(−1∣11,down,7)+(−1)⋅p(−1∣11,down,10)+(−1)⋅p(−1∣11,down,11)+0⋅p(0∣11,down,terminal)]+γ⋅0}=1⋅{[(−1)⋅0+(−1)⋅0+(−1)⋅0+0⋅1]+γ⋅0}=0​
$\begin{aligned} q_\pi(7,down) &= P_{7, 3}^{down} \cdot \Bigl [ R_{7, 3}^{down} + \gamma \cdot v_\pi(3)\Bigr ] + P_{7, 6}^{down} \cdot \Bigl [ R_{7, 6}^{down} + \gamma \cdot v_\pi(6)\Bigr ] \\ & \quad + P_{7, 11}^{down} \cdot \Bigl [ R_{7, 11}^{down} + \gamma \cdot v_\pi(11)\Bigr ] + P_{7, 7}^{down} \cdot \Bigl [ R_{7, 7}^{down} + \gamma \cdot v_\pi(7)\Bigr ] \\ &= 0+0+p(7 \mid 11, down) \cdot \biggl \{ \sum_{s'} \Bigl [r\cdot p(r \mid 7, down, s') \Bigr ] + \gamma \cdot v_\pi(11)\biggr \} + 0 \\ &=1 \cdot \biggl \{ \Bigl [ (-1)\cdot p(-1 \mid 7, down, 7) + (-1) \cdot p(-1 \mid 7, down, 3) \\ &\quad + (-1) \cdot p(-1 \mid 7, down, 6) + (-1) \cdot p(-1 \mid 7, down, 11)\Bigr ] + \gamma \cdot (-14)\biggr \} \\ &=1 \cdot \biggl \{ \Bigl [ (-1)\cdot 0 + (-1) \cdot 0 + (-1) \cdot 0 + (-1) \cdot 1\Bigr ] - \gamma \cdot 14\biggr \} \\ &= -1 -\gamma \cdot 14 \end{aligned}$qπ​(7,down)​=P7,3down​⋅[R7,3down​+γ⋅vπ​(3)]+P7,6down​⋅[R7,6down​+γ⋅vπ​(6)]+P7,11down​⋅[R7,11down​+γ⋅vπ​(11)]+P7,7down​⋅[R7,7down​+γ⋅vπ​(7)]=0+0+p(7∣11,down)⋅{s′∑​[r⋅p(r∣7,down,s′)]+γ⋅vπ​(11)}+0=1⋅{[(−1)⋅p(−1∣7,down,7)+(−1)⋅p(−1∣7,down,3)+(−1)⋅p(−1∣7,down,6)+(−1)⋅p(−1∣7,down,11)]+γ⋅(−14)}=1⋅{[(−1)⋅0+(−1)⋅0+(−1)⋅0+(−1)⋅1]−γ⋅14}=−1−γ⋅14​