Exercise 3.4.4

Policy iteration and value iteration: implement on a 3-state MDP

MediumCoding

(The programming parts (a)–(c) 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) [programming] Find the values of \(\mathbf{v}\) when considering the policy \(\pi\) defined as \(\pi(a_1|s) = 0.4\), and \(\pi(a_2|s) = 0.6\), \(\forall s\). Implement the DP iterative method for policy evaluation. To do this, implement the iterative_policy_evaluation in the class DynamicProgrammingSolver. The method should receive a DiscretePolicy object and output \(\mathbf{v}\).

    Open (a) in the code workspace →

  • (b) [programming] Find the optimal policy for this MDP via policy iteration.

    Inside the class DynamicProgrammingSolver, implement policy_improvement method, and combine it with the iterative_policy_evaluation method created in (a). Put everything together in the policy_iteration method. The method should return \(\pi_* : \mathcal{S} \rightarrow \mathcal{A}\) (as a DiscretePolicy object) and \(v_* : \mathcal{S} \rightarrow \mathbb{R}\) (as an array).

    Open (b) in the code workspace →

  • (c) [programming] Find the optimal policy for this MDP via value iteration.

    For Value Iteration implement the value_iteration method of the DynamicProgrammingSolver. This method should also return \(\pi_* : \mathcal{S} \rightarrow \mathcal{A}\).

    Open (c) in the code workspace →

Implementation detail: The pseudocode implementation of Value Iteration and Policy Iteration implements the policy as an array, mapping states to actions. You can keep this convention. The DiscretePolicy constructor supports an optional argument where you can pass such an array.