Planning with Markov Decision Processes: An AI Perspective (Synthesis Lectures on Artificial Intelligence and Machine Learning)

Markov Decision Processes (MDPs) are widely popular in Artificial Intelligence for modeling sequential decision-making scenarios with probabilistic dynamics. They are the framework of choice when designing an intelligent agent that needs to act for long periods of time in an environment where its actions could have uncertain outcomes. MDPs are actively researched in two related subareas of AI, probabilistic planning and reinforcement learning. Probabilistic planning assumes known models for the agent's goals and domain dynamics, and focuses on determining how the agent should behave to achieve its objectives. On the other hand, reinforcement learning additionally learns these models based on the feedback the agent gets from the environment. This book provides a concise introduction to the use of MDPs for solving probabilistic planning problems, with an emphasis on the algorithmic perspective. It covers the whole spectrum of the field, from the basics to state-of-the-art optimal and approximation algorithms. We first describe the theoretical foundations of MDPs and the fundamental solution techniques for them. We then discuss modern optimal algorithms based on heuristic search and the use of structured representations. A major focus of the book is on the numerous approximation schemes for MDPs that have been developed in the AI literature. These include determinization-based approaches, sampling techniques, heuristic functions, dimensionality reduction, and hierarchical representations. Finally, we briefly introduce several extensions of the standard MDP classes that model and solve even more complex planning problems. Table of Contents: Introduction / MDPs / Fundamental Algorithms / Heuristic Search Algorithms / Symbolic Algorithms / Approximation Algorithms / Advanced Notes Cover Copyright Page Title Page Dedication Contents Preface Introduction Characteristics of an MDP Connections with Different Fields Overview of this Book MDPs Markov Decision Processes: Definition Solutions of an MDP Solution Existence Expected Linear Additive Utility and the Optimality Principle Finite-Horizon MDPs Infinite-Horizon Discounted-Reward MDPs Indefinite-Horizon MDPs Stochastic Shortest-Path MDPs Definition Stochastic Shortest-Path MDPs and Other MDP Classes Factored MDPs Factored Stochastic Shortest-Path MDPs PPDDL-style Representation RDDL-style Representation Factored Representations and Solving MDPs Complexity of Solving MDPs Fundamental Algorithms A Brute-Force Algorithm Policy Evaluation Policy Evaluation by Solving a System of Equations An Iterative Approach to Policy Evaluation Policy Iteration Modified Policy Iteration Limitations of Policy Iteration Value Iteration Bellman equations The Value Iteration Algorithm Theoretical Properties Asynchronous Value Iteration Prioritization in Value Iteration Prioritized Sweeping Improved Prioritized Sweeping Focused Dynamic Programming Backward Value Iteration A Comparison of Prioritization Algorithms Partitioned Value Iteration Topological Value Iteration External Memory/Cache Efficient Algorithms Parallelization of Value Iteration Linear Programming Formulation Infinite-Horizon Discounted-Reward MDPs Bellman equations Value/Policy Iteration Prioritized and Partitioned Algorithms Finite-Horizon MDPs MDPs with Dead Ends Finite-Penalty SSP MDPs with Dead-Ends Heuristic Search Algorithms Heuristic Search and SSP MDPs FIND-and-REVISE: a Schema for Heuristic Search LAO* and Extensions LAO* ILAO* BLAO* and RLAO*: Expanding the Reverse Envelope AO*: Heuristic Search for Acyclic MDPs RTDP and Extensions RTDP LRTDP BRTDP, FRTDP, VPI-RTDP: Adding an Upper Bound Heuristics and Transition Graph Pruning Action Elimination Focused Topological Value Iteration Computing Admissible Heuristics Adapting Classical Planning Heuristics to MDPs The haodet Heuristic The hmax Heuristic Heuristic Search and Dead Ends The Case of Avoidable Dead Ends The Case of Unavoidable Dead Ends Symbolic Algorithms Algebraic Decision Diagrams The REDUCE Operator The APPLY Operator Other ADD Operators SPUDD: Value Iteration using ADDs Symbolic LAO* Other Symbolic Algorithms Other Symbolic Representations Approximations using Symbolic Approaches Approximation Algorithms Determinization-based Techniques FF-Replan FF-Hindsight RFF HMDPP Determinization-based Approximations and Dead Ends Sampling-based Techniques UCT Heuristic Search with Inadmissible Heuristics hadd hFF hGOTH Dimensionality Reduction-based Techniques ReTrASE Approximate Policy Iteration and Linear Programming FPG Hierarchical Planning Options Task Hierarchy Hierarchy of Abstract Machines Other Approaches State Abstraction in Hierarchical MDP Learning Hierarchical Knowledge Discussion Hybridized Planning A Comparison of Different Algorithms Advanced Notes MDPs with Continuous or Hybrid States Value Function Representations Heuristic Search for Hybrid MDPs Continuous Actions MDP with Concurrency and Durative Actions Durative Actions Concurrent Actions Concurrent, Durative Actions Relational MDPs Solution Representations Algorithms Generalized Stochastic Shortest Path MDPs Mathematical Properties Algorithms for GSSP MDPs SixthSense: A Heuristic for Identifying Dead Ends Other Models Issues in Probabilistic Planning The Importance of Planning Competitions The Bane of Many Conferences Summary Bibliography Authors' Biographies Index Provides a concise introduction to the use of Markov Decision Processes for solving probabilistic planning problems, with an emphasis on the algorithmic perspective. It covers the whole spectrum of the field, from the basics to state-of-the-art optimal and approximation algorithms.