Decision-Theoretic Planning: Structural Assumptions and Computational Leverage

By Craig Boutilier, Thomas L. Dean, Steve Hanks. 1999

Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these areas often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory. This paper presents an overview and synthesis of MDP-related methods, showing how they provide a unifying framework for modeling many classes of planning problems studied in AI. It also describes structural properties of MDPs that, when exhibited by particular classes of problems, can be exploited in the construction of optimal or approximately optimal policies or plans. Planning problems commonly possess structure in the reward and value functions used to describe performance criteria, in the functions used to describe state transitions and observations, and in the relationships among features used to describe states, actions, rewards, and observations. Specialized representations, and algorithms employing these representations, can achieve computational leverage by exploiting these various forms of structure. Certain AI techniques -- in particular those based on the use of structured, intensional representations -- can be viewed in this way. This paper surveys several types of representations for both classical and decision-theoretic planning problems, and planning algorithms that exploit these representations in a number of different ways to ease the computational burden of constructing policies or plans. It focuses primarily on abstraction, aggregation and decomposition techniques based on AI-style representations.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition (1999, methodology): “Hence, recent research has focused on methods that can exploit structure within the planning problem to work more efficiently ( Boutilier, Dean, & Hanks, 1999 ).”
Optimal and Approximate Q-value Functions for Decentralized POMDPs (2008, background): “Intuitively, a Dec-POMDP models a number of agents that inhabit a particular environment, which is considered at discrete time steps, also referred to as stages (Boutilier et al., 1999) or (decision) epochs (Puterman, 1994).”
Efficient Solution Algorithms for Factored MDPs (2003, methodology): “The most closely related work to ours is a line of research that began with the work of Boutilier et al. (1995). In particular, the approximate Apricodd algorithm of Hoey et al. (1999), which uses analytic decision diagrams (ADDs) to represent the value function is a strong alternative approach for ”
Metrics for Finite Markov Decision Processes (2004, methodology): “The formulation of our metrics is based on the notion of bisimulation for MDPs, with an aim towards solving discounted infinite horizon reinforcement learning tasks.”
Neural Predictive Belief Representations (2018, background): “It is to be expected that compact representations of POMDPs make it easier to learn and represent models (Boutilier et al., 1999).”
Bisimulation Metrics for Continuous Markov Decision Processes (2011, background): “Markov decision processes (MDPs) offer a popular mathematical tool for planning and learning in the presence of uncertainty [7].”
Exploiting Structure and Agent-Centric Rewards to Promote Coordination in Large Multiagent Systems (2014, methodology): “Agents optimizing their individual rewards, rj within the FA-FMDP structure, will simultaneously be acting to optimize the system-level objective R [4, 7, 22].”
Practical solution techniques for first-order MDPs (2009, methodology): “In this article, we propose one such approach that translates an expressive subset of the PPDDL representation to a first-order MDP (FOMDP) specification and then derives a domain-independent policy without grounding at any intermediate step.”
Anytime Point-Based Approximations for Large POMDPs (2006, unknown): “…Observable Markov Decision Process (POMDP) ( ¨Astrom, 1965; Sondik, 1971; Monahan, 1982; White, 1991; Lovejoy, 1991b; Kaelbling, Littman, & Cassan-dra, 1998; Boutilier, Dean, & Hanks, 1999) has emerged as possibly the most general representation for (single-agent) planning under uncertainty.”
Discovering Hierarchy in Reinforcement Learning with HEXQ (2002, unknown): “Many researchers have either ignored where decompositions come from or pointed to the desirability of automating this task (Boutilier et al., 1999; Hauskrecht et al., 1998; Dean & Lin, 1995).”
Algorithm-Directed Exploration for Model-Based Reinforcement Learning in Factored MDPs (2002, unknown): “Of these approaches, the factored MDP representation developed by Koller and Parr has proven to be particularly convenient [17, 18, 12].”
A unifying framework for computational reinforcement learning theory (2009, background): “Factored-state representations [Boutilier et al. 1999] are compact representations of MDPs that avoid explicitly enumerating all states when defining an MDP.”
Statistical Relational Artificial Intelligence: Logic, Probability, and Computation (2016, background): “Decisiontheoretic planning [Boutilier et al., 1999] generalized state-based planning under uncertainty to include features.”
Deep Reactive Policies for Planning in Stochastic Nonlinear Domains (2019, background): “We are particularly concerned with continuous state-action MDPs (CSA-MDPs) with exogenous events.”