Decision-Theoretic Planning: Structural Assumptions and Computational Leverage

Abstract

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.

References in corpus (11)

• Context-Specific Independence in Bayesian Networks
• SPUDD: Stochastic Planning using Decision Diagrams
• On the Complexity of Solving Markov Decision Problems
• Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
• Hierarchical Solution of Markov Decision Processes using Macro-actions
• Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes
• Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems
• Structured Reachability Analysis for Markov Decision Processes
• Context-Specific Approximation in Probabilistic Inference
• Correlated Action Effects in Decision Theoretic Regression
• Exploiting the Rule Structure for Decision Making within the Independent Choice Logic

Cited by in corpus (34)

• Value-Function Approximations for Partially Observable Markov Decision Processes
• SPUDD: Stochastic Planning using Decision Diagrams
• The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models
• Accelerating Reinforcement Learning through Implicit Imitation
• Efficient Solution Algorithms for Factored MDPs
• Solving POMDPs by Searching the Space of Finite Policies
• Planning under Continuous Time and Resource Uncertainty: A Challenge for AI
• Nonapproximability Results for Partially Observable Markov Decision Processes
• Inductive Policy Selection for First-Order MDPs
• Regret-based Reward Elicitation for Markov Decision Processes
• Distributed Planning in Hierarchical Factored MDPs
• Metrics for Finite Markov Decision Processes
• Metrics for Markov Decision Processes with Infinite State Spaces
• Symbolic Dynamic Programming for Discrete and Continuous State MDPs
• Practical Linear Value-approximation Techniques for First-order MDPs
• Representation Policy Iteration
• Continuous Value Function Approximation for Sequential Bidding Policies
• Value-Directed Belief State Approximation for POMDPs
• Reinforcement Learning for Agents with Many Sensors and Actuators Acting in Categorizable Environments
• Methods for computing state similarity in Markov Decision Processes
• Anytime State-Based Solution Methods for Decision Processes with non-Markovian Rewards
• Building a Stochastic Dynamic Model of Application Use
• Vector-space Analysis of Belief-state Approximation for POMDPs
• Approximate Linear Programming for First-order MDPs
• Monte-Carlo optimizations for resource allocation problems in stochastic network systems
• Planning and Acting under Uncertainty: A New Model for Spoken Dialogue Systems
• A Clustering Approach to Solving Large Stochastic Matching Problems
• On Polynomial Sized MDP Succinct Policies
• Counterexample-guided Planning
• A Prototype for Educational Planning Using Course Constraints to Simulate Student Populations
• Optimistic Simulated Exploration as an Incentive for Real Exploration
• Temporal plannability by variance of the episode length
• A compact, hierarchical Q-function decomposition
• Bridging the Gap between Reinforcement Learning and Knowledge Representation: A Logical Off- and On-Policy Framework