From: Jessica Kristan Miller (jessica_at_cs.washington.edu)
Date: Mon Nov 17 2003 - 11:04:07 PST
Paper Reviewed: SPUDD: Stochastic Planning using Decision Diagrams
Paper Author: Hoey, St-Aubin, Hu, Boutilier
Reviewed By: Jessica Miller
Summary:
This paper explores the use of algebraic decision diagrams (ADDs) to
represent value functions and policies in Markov Decision Problems (MDPs).
Two Important Most Ideas:
(1) Undoubtedly the most important idea is using ADDs to represent value
functions in MDPs. This representation is extremely compact because it
takes advantage of regularities in the action and reward networks. Large
MDPs that could previously not be solved using classical dynamic
programming may be able to be solved using this new more compact
representation.
(2) Another important aspect of this paper is that the authors introduce a
value iteration algorithm that uses the ADD representation for value
functions. With this algorithm the authors are able to compare the
success of their alternative representation with others. The authors also
introduce several possible optimizations to this algorithm that can be
made.
Largest Flaw in the Paper:
The authors themselves openly admit that one of the largest "drawbacks" of
this representation is the fact that all of the variables must be boolean
values. The way the authors deal with non-boolean variables of finite
domain is by splitting the variables up into some number of boolean
values. This takes care of the problem, but increases the state space.
Two Open Research Questions:
(1) The authors suggest two ideas for open research. They admit that more
research in variable reordering may result in a more efficient algorithm.
The authors also suggest implementing other dynamic programming algorithms
(e.g. policy iteration) using the ADD representation. This may give more
insight to the usefulness of the ADD representation as well as introduce
more optimizations and observations that can be used when choosing ADDs as
the value function representation.
(2) Another open research topic that is not mentioned in the paper is the
applicability and success of using this algorithm and representation to
solve "real world" problems instead of variants of the factory problem.
This archive was generated by hypermail 2.1.6 : Mon Nov 17 2003 - 11:04:08 PST