Decision-Theoretic Planning: Structural Assumptions and Computational Leverage

Analysis

Why This Paper Matters

This paper is a landmark survey that bridges multiple research communities—AI planning, decision analysis, operations research, control theory, and economics—by showing that Markov decision processes (MDPs) provide a unifying formalism for sequential decision making under uncertainty. At a time when each field had developed its own specialized models and algorithms, Boutilier, Dean, and Hanks synthesized these perspectives into a coherent framework, highlighting common structural assumptions that can be exploited for computational gain.

The paper's significance lies in its systematic cataloging of structural properties—such as additive reward functions, factored state spaces, and hierarchical decompositions—and the corresponding algorithmic techniques (abstraction, aggregation, decomposition) that leverage them. This taxonomy has guided subsequent research in reinforcement learning, hierarchical planning, and approximate dynamic programming, making it a highly cited reference (1333 citations) that continues to shape how practitioners design scalable planning algorithms.

Technical Contributions

• Unifying Framework: Demonstrates that many planning problems from diverse fields can be modeled as MDPs, enabling cross-fertilization of techniques.
• Structural Properties: Identifies key structural dimensions: reward/value function structure (e.g., additive, multiplicative), transition/observation function structure (e.g., deterministic, stochastic, factored), and feature relationships (e.g., independence, conditional independence).
• Algorithmic Leverage: Surveys techniques that exploit structure:
  • Abstraction: Reducing state space by ignoring irrelevant details (e.g., state aggregation, temporal abstraction).
  • Aggregation: Grouping states with similar value or transition behavior to reduce complexity.
  • Decomposition: Breaking problems into subproblems (e.g., hierarchical MDPs, factored MDPs).
• Intensional Representations: Highlights the use of structured representations (e.g., decision trees, Bayesian networks, influence diagrams) to compactly represent value functions, policies, and transition models.
• Approximation Methods: Covers techniques for computing approximately optimal policies when exact solutions are intractable, such as value function approximation and bounded-optimal planning.

Results

As a survey paper, no new experimental results are presented. However, the paper synthesizes findings from numerous prior works, demonstrating that structured representations can reduce the computational complexity of policy construction from exponential in the number of state variables to polynomial in many cases. For example, it shows how factored MDPs with additive reward functions can be solved using dynamic programming on decision trees, achieving significant speedups over flat state-space methods.

Significance

The paper has had a lasting impact on AI planning and reinforcement learning. It popularized the use of structured representations (e.g., decision diagrams, Bayesian networks) for MDPs, directly influencing later work on factored MDPs, relational MDPs, and hierarchical reinforcement learning. Its taxonomy of structural assumptions and algorithmic leverage points remains a standard reference for researchers designing scalable decision-making systems. The paper also helped bridge the gap between AI planning and control theory, fostering interdisciplinary approaches to sequential decision making.