From: Danny Wyatt (danny_at_cs.washington.edu)
Date: Mon Nov 17 2003 - 09:06:08 PST
SPUDD: Stochastic Planning using Decision Diagrams
Jesse Hoey, Robert St-Aubin, Alan Hu, Craig Boutilier
Summary:
The authors present an algorithm for using Algebraic Decision Diagrams
to factor states in an MDP.
Important Ideas:
Extant ideas for optimizing decision trees and representations of sets
of variables that take advantage of certain aspects of a problem's
structure can be applied to MDP's that have similar structure.
Similarly to the previous paper, the authors note that highly optimized
algorithms exist for ADD's and could be of use to MDP problems
"compiled" into ADD representations. And even though they play down
their order of magnitude speed-ups over SPI as too dependent on
"implementation details" I wonder if they aren't attributable to the use
of such highly optimized algorithms from another domain.
Flaws:
The authors cede that, in some cases, iterations of their algorithm will
need an exponential blow-up in the number of variables. Optimizations
that use less space repeat computations and thus need more time. A
balance between time and space optimization has to be struck, and even
then a problem that introduces a single entirely unrelated variable
doubles the algorithm's running time. I would like to see a more
consideration of all the trade-offs involved.
Open Questions:
Returning to the "implementation details" that cloud the results, why is
their algorithm so much faster? And though they at once discourage a
comparison of running times they also say that they did not use existing
ADD variable reordering schemes in order to allow for more accurate
comparisons. What else, in addition to variable reordering, from the
domain of highly optimized ADD algorithms could benefit ADD-represented
MDP's?
This archive was generated by hypermail 2.1.6 : Mon Nov 17 2003 - 09:05:34 PST