From: Nan Li (annli_at_cs.washington.edu)
Date: Fri May 09 2003 - 10:58:10 PDT
Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable
Markov Decsion Processes / Anthony Cassandra, Michael L. Littman, Nevin L.
Zhang
This paper extends one of the authors's previous work, "incremental
pruning , an exact method to solve POMP. The theoretical and empirical
comparison to other algorithms supports their claim that IP is the most
efficient exact method for solving POMPs.
The incremental pruning algorithm is rooted on another smart algorithm,
witness algorithm. Observing that the equation for updating value
functions can be broken up into a group of simpler functions, each of
which can then be represented as a piecewise linearity and covex function
of |S| vectors. These vector functions can then be represented by some
smaller set of "witness" vectors, thus reduce the computation complexity
of updating value functions.
IP algorithm gives a further look at this perspective. The author notice
that during the process of witness algorithm, there is still some steps
that possibly have to deal with exponentially exposed space. Their
solution is straightforward yet useful. Instead of exposing the space
completely then operate on it, they use an exposing-operating(simplifying)
loop. This reminds me a well-known trick in high school: to compute
a*b/(A*B) using calculator, if a*b and/or A*B is too large, it's better do
(a/A)*(b/B).
This paper follows the perspective of the "witness algorithm" to extend
IP. Realizing the special form of the most cost calculation, the authors
customize a procedure for it to reduce even more the size of set of
witness vectors.
The improvement is proved by the authors' experiments result. The idea is
simple, yet the result is couraging. It's another success of classical
neat tricks. I haven't read the original paper (by Zhang, N.L. and Liu,
W.), but somehow I think that would be even more interesting than this
one.
So to future work, I think the first point the authors suggest is quite
necessary: to control the precision of the algorithm.
--
This archive was generated by hypermail 2.1.6 : Fri May 09 2003 - 10:58:11 PDT