# Efficient Solution Algorithms For Factored Mdps

Carlos Guestrin guestrin@cs.stanford.edu Computer Science Dept., Stanford University Daphne Koller koller@cs.stanford.edu Computer Science Dept., Stanford University Ronald Parr parr@cs.duke.edu Computer Science Dept., Duke University Shobha Venkataraman shobha@cs.cmu.edu Computer Science Dept., Carnegie Mellon University

## Abstract

This paper addresses the problem of planning under uncertainty in large Markov Decision Processes (MDPs). *Factored MDPs* **represent a complex state space using state variables and**
the transition model using a dynamic Bayesian network. This **representation often allows an** exponential reduction in the representation size of structured MDPs, but the complexity of exact solution algorithms for such MDPs can grow exponentially in **the representation size. In this paper,** we present two approximate solution algorithms that exploit structure in factored MDPs. Both use an approximate value function represented as a linear combination of basis functions, where each basis function involves only a small subset of the domain variables. A key contribution of this paper is that it shows how the basic operations of both algorithms can be performed efficiently in closed form, by exploiting both *additive* and *context-specific* **structure in a factored MDP. A** central element of our algorithms is a novel linear program decomposition technique, analogous to variable elimination in Bayesian networks, which reduces an exponentially large LP to a provably equivalent, polynomial-sized one. One algorithm uses approximate linear programming, and the second approximate dynamic programming. Our dynamic programming algorithm is novel in that it uses an approximation based on max-norm, a technique that **more directly minimizes the terms** that appear in error bounds for approximate MDP algorithms. **We provide experimental results**
on problems with over 1040 **states, demonstrating a promising indication of the scalability of our**
approach, and compare our algorithm to an existing state-of-the-art approach, showing, in some problems, exponential gains in computation time.

## 1. Introduction

Over the last few years, Markov Decision Processes (MDPs) **have been used as the basic** semantics for optimal planning for decision theoretic agents in stochastic environments. In the MDP framework, the system is modeled via a set of states which evolve stochastically. The main problem with this representation is that, in virtually any real-life domain, the state space is quite large. However, many large MDPs have significant internal structure, and can be modeled compactly if the structure is exploited in **the representation.**
Factored MDPs **(Boutilier, Dearden, & Goldszmidt, 2000) are one approach to representing large, structured MDPs compactly. In this framework, a state is implicitly described**
by an assignment to some set of state variables. A dynamic Bayesian network (DBN) **(Dean** & Kanazawa, 1989) can then allow a compact representation of **the transition model, by** exploiting the fact that the transition of a variable often depends only on a small number