From: Lillie Kittredge (kittredl_at_u.washington.edu)
Date: Mon Nov 17 2003 - 00:20:22 PST
SPUDD: Stochastic Planning using Decision Diagrams
by Hoey et. al.
Summary:
Continuing research in finding ways to solve MDPs without enumerating the state space, the
authors derive a new algorithm from a previous policy iteration algorithm, and show the
potential gains.
Main ideas:
- Algebraic decision diagrams (ADDs) can provide a useful representation of MDPs for a
modified value iteration algorithm, SPUDD (stochastic planning using decision diagrams). Most
of the paper is devoted to describing how the ADD representation is generated, optimized, and
then used in the algorithm.
- ADD is good because it "captures some regularities in system dynamics, reward, and value".
That is, it can avoid some redundancy by noticing patterns in what it needs to represent. This is
compared to tree-structured representations, which are rife with redundancy.
Major flaws:
- Failure to proofread abstract.
- They seem reluctant to compare themselves to the algorithm they based their work upon:
"[SPUDD and SPI] do not lend themselves easily to comparisons of running times, since
implementation details cloud the results; so running times will not be discussed further here".
They pull a similar trick in choosing what to graph-- their worst-case and best-case graphs are
very impressive, but are, on closer inspection, not against SPI but against flat value iteration.
Open questions:
- As this algorithm has not, by the authors' admission, been tested extensively on realistic
domains, what happens if it is?
- Is value iteration really the way to go in solving MDPs? Might there be another algorithm that
doesn't require this complex a method for representing a MDP?
This archive was generated by hypermail 2.1.6 : Mon Nov 17 2003 - 00:20:23 PST