Exercise 3.4.3

Dynamic programming solvers: design an MDP, matrix-form Bellman solver, VI and PI

MediumCoding

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.

    Open (a) in the code workspace →

  • (b) Implement the BellmanEquationSolver which 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.

    Open (b) in the code workspace →

  • (c) For this question you will be asked to implement the Value Iteration and Policy Iteration algorithms.

    • For Value Iteration implement the value_iteration method of the DynamicProgrammingSolver. The method should return a DiscretePolicy object 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 DiscretePolicy constructor supports an optional argument where you can pass such an array.

    Open (c) in the code workspace →