Article: Efficient Solution Algorithms for Factored MDPs

JAIR is pleased to announce the publication of the following article:

Guestrin, C., Koller, D., Parr, R. and Venkataraman, S. (2003)
  "Efficient Solution Algorithms for Factored MDPs", 
   Volume 19, pages 399-468.

   For quick access via your WWW browser, use this URL:
     http://www.jair.org/abstracts/guestrin03a.html

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
10^40 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. 

The article is available via:
   
 -- comp.ai.jair.papers (also see comp.ai.jair.announce)

 -- World Wide Web: The URL for our World Wide Web server is
       http://www.jair.org/
    For direct access to this article and related files try:
       http://www.jair.org/abstracts/guestrin03a.html

 -- Anonymous FTP from Carnegie-Mellon University (USA):
        ftp://ftp.cs.cmu.edu/project/jair/volume19/guestrin03a.ps
    The compressed PostScript file is named guestrin03a.ps.Z 

For more information about JAIR, visit our WWW or FTP sites, or
contact [EMAIL PROTECTED]



-- 
Steven Minton
JAIR Managing Editor