From: Lincoln Ritter (lritter_at_cs.washington.edu)
Date: Mon Nov 17 2003 - 08:23:30 PST
SPUDD: Stochastic Planning Using Decision Diagrams
Hoey, et. al.
reviewed by Lincoln Ritter
The use of algebraic decision diagrams can be used to capture the
regularities of value functions in MDPs and thus utilization of these
diagrams can lead to significant reductions in the number of nodes
needed to represent these functions during value iteration.
The ability to represent MDP's using a data structure that reduces the
storage and computation of redundant data seems quite valuable given
that state space is generally exponential in the number of features.
Indeed, the evidence provided suggests that in certain problem domains
the advantages of using the tehcniques presented in this paper can
make the difference between tractability and intractability.
Perhaps it is my naivete in this field, (this will sound harsher than
i mean it to) but, though the utility of this work is undeniable, I
fail to see how this work provides any particularly new insights. The
authors acknowledge that BDD's and ADD's have been used to represent
branching processes for quite some time and it is for precisely for
their ability to concisely represent complex large functions that they
have been so successfully used in other fields. Perhaps this explains
somewhat the generally uninspired tone of the paper and its rather
poor writing.
A clear possibility for future work is to explicitly investigate the
effects of the "turning knob" described in the optimizations section.
Since the advantages of using ADDs are only realized with problem
having highly regular value functions, perhaps it might be interesting
to investigate methods by which the regularity of value functions
might be predicted. So, is there a "reuglarity score" that we can
give to a problem based on its description to aid in the picking of
an appropriate solution method.
This archive was generated by hypermail 2.1.6 : Mon Nov 17 2003 - 08:23:31 PST