Exercise 2.6.2
Bellman equation in matrix form: three-state MDP, r^π, P^π, v
(The programming parts (f) and (g) run in the code workspace, in your browser.)
Consider the MDP given in Figure 1. Actions have a \(0.9\) probability of success and with \(0.1\) probability we remain in the same state. \(R_t =0\) for all transitions that end up in \(S_0\), and \(R_t = -1\) for all other transitions. Consider a discount factor of \(\gamma = 0.9\).
Recall the Bellman equation \[\begin{align*} v_{\pi}(s) = \sum_a \pi(a|s) \Big(r(s,a) + \gamma \sum_{s'} p(s'|s,a) v_{\pi}(s') \Big). \end{align*}\]
-
(a) For \(v_i \equiv v(s_i)\), that is: \[\begin{align*} \mathbf{v} \equiv \begin{bmatrix} v(s_0) \\ v(s_1) \\ v(s_2) \end{bmatrix}. \end{align*}\] Show that the expression above can be written as the matrix system \(\mathbf{v} = \mathbf{r}^{\pi} + \gamma \mathbf{P}^{\pi} \mathbf{v}\). Show the expressions for \(r_i^{\pi}\) and \(P_{ij}^{\pi}\) of the elements of vector \(\mathbf{r}^{\pi}\), and matrix \(\mathbf{P}^{\pi}\), for the row \(i\) and column \(j\).
-
(b) Using matrix algebra, find a closed-form solution for \(\mathbf{v}\).
-
(c) For the problem above, considering the policy \(\pi\) defined as \(\pi(a_1|s) = 0.4\), and \(\pi(a_2|s) = 0.6\), \(\forall s\). Find (without using a computer) the numerical values of \(\mathbf{r}^{\pi}\) and \(\mathbf{P}^{\pi}\). Show your calculation steps.
-
(d) Give the numerical values for the reward function \(r(s,a)\) of the MDP in Figure 1. Show the steps that you used to compute the values. Fill in Table 1. Hint: Note that the reward function can also be written as \(r(s,a) = \sum_r r \sum_{s'} p(s', r|s,a)\).
Table 1: Reward function -
(e) Give the transition function \(p(s'|s,a)\) for the MDP described in Figure 1 in a tabular form, by filling in Table 2.
Table 2: Transition Function \(p(s' | s, a)\) -
(f) [programming] Using the skeleton code, create an MDP object representing Figure 1. Hint: the guide to the MDP class shows an example.
-
(g) [programming] Find the values of \(\mathbf{v}\) when considering the previously created MDP and the policy \(\pi\) defined as \(\pi(a_1|s) = 0.4\), and \(\pi(a_2|s) = 0.6\), \(\forall s\). Implement the direct matrix form solution for \(\mathbf{v}\).
To do this, implement the method
policy_evaluationin the classBellmanEquationSolver. Hint: TheBellmanEquationSolverconstructor should receive an MDP object as input. The methodpolicy_evaluationshould receive aDiscretePolicyobject, compute \(\mathbf{r}^{\pi}\) and \(\mathbf{P}^{\pi}\) as intermediate steps, and give \(\mathbf{v}\) as output.