Exercise 2.6.2

Bellman equation in matrix form: three-state MDP, r^π, P^π, v

Reinforcement Learning › Exercises › Lecture 2 · The RL Problem and Finite MDPs › 2.6 Bellman equation in matrix form
EasyWrittenCoding

(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\).

diagram
Figure 1: Diagram of a simple MDP.

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
    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
    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.

    Open (f) in the code workspace →

  • (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_evaluation in the class BellmanEquationSolver. Hint: The BellmanEquationSolver constructor should receive an MDP object as input. The method policy_evaluation should receive a DiscretePolicy object, compute \(\mathbf{r}^{\pi}\) and \(\mathbf{P}^{\pi}\) as intermediate steps, and give \(\mathbf{v}\) as output.

    Open (g) in the code workspace →