Markov Decision Processes: Concepts and Algorithms
Martijn van Otterlo, Marco Wiering, M.A. Wiering, M. van Otterlo · 2012
Situated in between supervised learning and unsupervised learning, the paradigm of reinforcement learning deals with learning in sequential decision making problems in which there is limited feedback. This text introduces the intuitions and concepts behind Markov decision processes and two classes of algorithms for computing optimal behaviors: reinforcement learning and dynamic programming. First the formal framework of Markov decision process is defined, accompanied by the definition of value functions and policies. The main part of this text deals with introducing foundational classes of algorithms for learning optimal behaviors, based on various definitions of optimality with respect to the goal of learning sequential decisions. Additionally, it surveys efficient extensions of the foundational algorithms, differing mainly in the way feedback given by the environment is used to speed up learning, and in the way they concentrate on relevant parts of the problem. For both model-based and model-free settings these efficient extensions have shown useful in scaling up to larger problems. MARKOV DECISION PROCESSES (MDP) (Puterman, 1994) are an intuitive and fundamental formalism for decision-theoretic planning (DTP) (Boutilier et al., 1999; Boutilier,