From: Sandra B Fan (sbfan_at_cs.washington.edu)
Date: Mon Nov 17 2003 - 12:11:11 PST
Title: "SPUDD: Stochastic Planning using Decision Diagrams"
Authors: Jesse Hoey, Robert St-Aubin, Alan Hu, Craig Boutilier
One-line summary:
This paper examines the use of algebraic decision diagrams (ADDs) on
Markov decision processes.
Important ideas:
Using ADDs reduces the state space for MDPs on boolean variables. However,
there are problems with this approach, and the authors needed certain
optimizations for this approach to work well.
Flaws:
Like I said above, this works only on boolean variables. It can work on
non-booleans if you simply spilt up your variables, but that would make
the state space larger once again. Also, it would have been nice to see
their algorithm tested on a more varied set of examples.
Open questions:
The paper actually mentions a few open question on the topic. They
used a static, user-defined variable ordering, and altering SPUDD to work
with dynamic variable ordering would be more useful. Another direction is
to examine modified policy iteration, because it would possibly converge
more quickly than the method they used.
This archive was generated by hypermail 2.1.6 : Mon Nov 17 2003 - 12:11:12 PST