From: Tyler Robison (trobison_at_cs.washington.edu)
Date: Mon Nov 17 2003 - 09:18:40 PST
eSPUDD: Stochastic Planning using Decision Diagrams
Jesse Hoey et al
Summary:
The authors present a method to solve MDPs by using ADDs, which in many
(though not all)
cases massively reduces the computational time required.
Important Ideas:
One of the more important aspects of the paper is the significant
way in which the graph
size is reduced when using SPUDD instead of the SPI algorithm. The size
of the graph is of
course extremely important in terms of trying to solve the problem, and if
the figures in the results
section are typical, this method can very substantially reduce graph size.
The optimizations presented are also of importance, as the drive
behind this algorithm is
primarily it's speed. Of particular interest is their use of a 'tuning
knob' to allow fine-tuning of the
optimization.
Flaws:
The flaw that sticks out most in my mind is the limited nature of
their tests; we are given
sets of data from FACTORY examples, and then on the EXPON problem to
collect data on the
worst-case scenario. It is very nice to see that they show us both sides
of the algorithm (where
it has significant gains, and where it does terribly), but it would also
have been helpful to see the
algorithm on more, and more varied, problems (since the FACTORY problems
are all similar).
Another problem, though not an unforgivable one, is the limitation
of ADDs that they can
only represent binary variables. Being able to represent k-ary variables
by using many boolean
variables is a decent solution, but I wonder how much performance will
suffer in extreme cases of
k-ary variables for large k values. Also, it states in the conclusion
that conceptually ADD should
be able to deal with multi-valued variables, yet the authors do not modify
it to do so; we are just told
that it should be fine.
Research Questions:
Seeing the algorithm's performance on more varied tests could help
shed light on its
actual usefulness. The EXPON test to illustrate the worst-case scenario
was helpful, and it would be
more helpful still to see various tests intended to test and highlight
strengths and weaknesses of the
algorithm (using a 1000-ary variable, for example).
Another potentially helpful set of experiments would compare SPUDD
against more
algorithms than just SPI; we can only get a limited view of it's
usefulness when it is tested on
only a few problems, and only against one other algorithm.
This archive was generated by hypermail 2.1.6 : Mon Nov 17 2003 - 09:18:41 PST