Exercise 3.1.1

Policy evaluation: q_π and an added state in the 4x4 gridworld

MediumWritten

Consider the \(4 \times 4\) gridworld as shown in Figure 1, which can be formalized as a Markov decision process \((\mathcal{S}, \mathcal{A}, p, r, \gamma)\). The nonterminal states are \(\mathcal{S} = \{1,2,...,14\}\). There are four actions possible in each state, \(\mathcal{A} = \{\texttt{up}, \texttt{down}, \texttt{right}, \texttt{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|5, \texttt{right}) = 1\), \(p(7, -1 | 7, \texttt{right})=1\), and \(p(10,r|5, \texttt{right}) = 0\) for all rewards \(r\). This is an undiscounted, episodic task. The reward is \(-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,s') = -1\) for all states \(s,s' \in \mathcal{S}\) and actions \(a \in \mathcal{A}\).

ex4.1.png
Figure 1: \(4 \times 4\) gridworld MDP.
  • (a) If \(\pi\) is the equiprobable random policy, what is \(q_{\pi}(11, \texttt{down})\)? What is \(q_{\pi}(7, \texttt{down})\)?

  • (b) For policy evaluation, the value function \(v_k\) as \(k \rightarrow \infty\) can be seen in Figure 2. Suppose a new state \(15\) is added to the gridworld just below state \(13\), and its actions, \(\texttt{left}, \texttt{up}, \texttt{right}\), and \(\texttt{down}\), take the agent to states \(12,13,14,\) and \(15\), respectively. Assume that the transitions from the original states are unchanged. What, then, is \(v_{\pi}(15)\) for the equiprobable random policy? Now suppose the dynamics of state \(13\) are also changed, such that action down from state \(13\) takes the agent to the new state \(15\). What is \(v_{\pi}(15)\) for the equiprobable random policy in this case?

    figex9.png
    Figure 2: On the left is the value of each state after running iterative policy evaluation with the number of iterations \(k \rightarrow \infty\). On the right is the greedy policy corresponding to the value function.

Source: Sutton & Barto (2018), Reinforcement Learning: An Introduction, 2nd ed., Exercises 4.1 and 4.2; Example 4.1. The gridworld of Example 4.1 is redrawn from the book. Figure 4.1 is redrawn with recomputed values. Licensed CC BY-NC-ND 2.0.