Chapter 4: Dynamic Programming

Algorithm Implementation

• Value Iteration and Policy Iteration for Russell and Norvig’s 4x3 grid world. This notebook discusses the implementation of the algorithms.
• Value Iteration and Policy Iteration for the L-maze. This notebook investigates the behavior of the algorithms.

Convergence

• Compare the convergence of Policy Evaluation using different versions of the L-maze.

Model and Algorithm Implementation (from scratch)

• Modeling Tic-Tac-Toe as an MDP and applying Value Iteration. This notebook defines the MDP from scratch and applies value iteration to find the optimal policy to play the game.

Linear Programming

• Policy evaluation for a 2-State MDP as a linear program in Excel.
• Solve MDPs using Linear Programming with the R package MarkovDP.

Exercise

• Use Dynamic Programming Methods to Solve the Teleport Maze

License

© 2025 Michael Hahsler. All code and documents in this repository are provided under the Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) License.