Abstract:  This  paper  explores the application of algebraic decision
diagrams   (ADDs)   to   compute  policies  factored  Markov  decision
processes.  The  conjecture  being  made  is  that  in many real-world
applications,  ADDs  can  lead  to  a  decrease  in  state  space  and
computational effort compared to classical state enumeration or matrix
representation.

Most important ideas:

*  Decision  trees  for  formulae expressed in disjunctive form can be
hard  to  solve  because their size grows exponentially due to subtree
duplication.  For  such  problems, symbolic dynamic programming in the
form  of  ADDs  are  preferable  because  they  offer  a  more compact
representation by not requiring full state enumeration.

*  A  dynamic  programming algorithm is given that iterates (improves)
the  value function by taking and ADD for the current step and the MDP
representation  to  compute  the  ADD structure for the next iteration
step. This way duplicate computation is avoided.

Largest flaws:

* In the debut of the paper, the authors mention that the measurements
section  will  show  that  in  practice,  the  theoretically  possible
exponentially  bad  behavior  tends to not appear; however, the end of
the  paper  appeals  to  reader's faith: "The examples used here [...]
were  not  designed  with  any  structure in mind which could be taken
advantage  of  by  an ADD representation". The actual examples are not
real-world problems but rather a few chosen artificial ones.

*  The  authors gloss over the blowup that can result when using k-ary
variables,  which I believe can be quite significant. Also the related
issue of analyzing ordering of variables is not touched.

Open questions:

A  hybrid algorithm that switches intelligently between ADDs, BDDs and
matrix representations depending on the structure of the problem could
nicely exploit the best of all algorithms.


Cheers,

Andrei