From: Daniel Lowd (lowd_at_cs.washington.edu)
Date: Sun Nov 16 2003 - 22:25:49 PST
"SPUDD: Stochastic Planning using Decision Diagrams," Hoey, et al.
This paper presented a modified algorithm for solving Markov decision
processes (MDPs), using algebraic decision diagrams (ADDs).
Its main contribution is a detailed explanation of how to use ADDs to
solve factored MDPs more efficiently. ADDs can potentially represent
conditional probability tables more efficiently than decision trees, and
they achieved better results on some datasets supporting the
effectiveness of this optimization. Their explanation included a
time-space tradeoff feature that allowed the algorithm to be adapted to
the amount of processing power and memory available. Also significant was
the introduction of a new dataset for use in testing MDP algorithms.
The biggest weakness of this paper was perhaps unavoidable: it was really,
really dry. I had trouble keeping track of exactly what the algorithm was
doing and how it was accomplishing that with all the V^i's, Q^i's, and
X_i's, all mixed together in a strange data structure like a decision tree
but much harder to visualize.
What additional optimizations would be effective remains an open question.
More optimizations would make even larger MDP problems tractable.
Furthermore, how does this approach perform on other datasets? It did
very well on the factory dataset, but that's just one set of problems.
Perhaps there are other optimization techniques that are more effective on
other sorts of MDPS?
This archive was generated by hypermail 2.1.6 : Sun Nov 16 2003 - 22:25:51 PST