Exercise 3.4.4
Policy iteration and value iteration: implement on a 3-state MDP
(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\).
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_evaluationin the classDynamicProgrammingSolver. The method should receive aDiscretePolicyobject and output \(\mathbf{v}\). -
(b) [programming] Find the optimal policy for this MDP via policy iteration.
Inside the class
DynamicProgrammingSolver, implementpolicy_improvementmethod, and combine it with theiterative_policy_evaluationmethod created in (a). Put everything together in thepolicy_iterationmethod. The method should return \(\pi_* : \mathcal{S} \rightarrow \mathcal{A}\) (as aDiscretePolicyobject) and \(v_* : \mathcal{S} \rightarrow \mathbb{R}\) (as an array). -
(c) [programming] Find the optimal policy for this MDP via value iteration.
For Value Iteration implement the
value_iterationmethod of theDynamicProgrammingSolver. This method should also return \(\pi_* : \mathcal{S} \rightarrow \mathcal{A}\).
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.