My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
Papers

Daphne Koller Publications

Efficient Solution Algorithms for Factored MDPs (2003)

by C.E. Guestrin, D. Koller, R. Parr, and S. Venkataraman


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.

Download Information

C.E. Guestrin, D. Koller, R. Parr, and S. Venkataraman (2003). "Efficient Solution Algorithms for Factored MDPs." Journal of Artificial Intelligence Research, 19, 399-468. IJCAI/JAIR Best Paper Award, 2007. pdf

Bibtex citation

@article{Guestrin+al:JAIR03,
  author =       "C.E. Guestrin and D. Koller and R. Parr and S. Venkataraman",
  title =        "Efficient Solution Algorithms for Factored {MDP}s",
  journal =      "Journal of Artificial Intelligence Research",
  volume =       "19",
  pages =        "399--468",
  year =         "2003",
  note = {IJCAI/JAIR Best Paper Award, 2007}
}

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal