Lecture notes for \Analysis of Algorithms": Markov decision processes
Thomas Dueholm Hansen · 2013
We give an introduction to innite-horizon Markov decision processes (MDPs) with nite sets of states and actions. We focus primarily on discounted MDPs for which we present Shapley’s (1953) value iteration algorithm and Howard’s (1960) policy iteration algorithm. We also give a short introduction to discounted turn-based stochastic games, a 2-player generalization of MDPs. Finally, we give a short introduction to two alternative criteria for optimality: average cost and total cost.