Exercise 3.4.3
Dynamic programming solvers: design an MDP, matrix-form Bellman solver, VI and PI
The parts (a)–(c) run in the code workspace, in your browser. It has classes to define an MDP and a policy (MDP, DiscretePolicy), a BellmanEquationSolver and a DynamicProgrammingSolver; both solvers take an MDP in their constructor.
-
(a) Design your own MDP. You can design a MDP directly as in Exercise 2.6.2 or derive one from a practical problem. Note that we only consider MDPs with finite state and action spaces. Provide a diagram of the MDP.
-
(b) Implement the
BellmanEquationSolverwhich should provide a method that takes in a stochastic policy \(\pi(a|s)\) and returns the associated value function \(v_{\pi}:\mathcal{S} \rightarrow \mathbb{R}\). You can create your own class or simple define the value function as an array mapping each action to a value. The value function should be computed in exact form using the matrix formulation as shown in Exercise 2.6.2. -
(c) For this question you will be asked to implement the Value Iteration and Policy Iteration algorithms.
For Value Iteration implement the
value_iterationmethod of theDynamicProgrammingSolver. The method should return aDiscretePolicyobject which encapsulates the optimal deterministic policy \(\pi_* : \mathcal{S} \rightarrow \mathcal{A}\).For Policy Iteration you need to implement the policy evaluation and policy improvement step of the algorithm. This method should also return \(\pi_* : \mathcal{S} \rightarrow \mathcal{A}\).
Implementation detail: The pseudocode implements of Value Iteration and Policy Iteration implements the policy as an array, mapping states to actions. You can keep this convention. The
DiscretePolicyconstructor supports an optional argument where you can pass such an array.