From: Sumit Sanghai (sanghai_at_cs.washington.edu)
Date: Fri May 09 2003 - 10:48:31 PDT
A Simple, Fast, Exact Method for Partially Observable Markov Decision
Processes
-- A. Cassandra, M. Littman, N. Zhang
Summary : The paper presents an improved algorithm for finding an optimal
solution in a discounted POMDP framework.
Ideas : THe 2 main ideas in this paper are the "purge" method for
filtering out vectors which do not have any witness and the incremental
pruning for computing this while taking the cross sum of n vector spaces.
The authors prove that purge(A+B+C+...) = purge (A + purge(B + purge
(C....))). And thus one does not have to do complete enumeration.
Flaws : The experiments were unsatisfying as they were only able to show
that in some cases, pruning did better than the previous algorithms. In
fact, purge need not be used if the problem isn't too complex itself.
The authors need to provide some better experiments to prove there point
(though they explain that it can be difficult to measure the exact gain).
Future Work : The paper does a best case/worst case analysis and shows that
incremental pruning does better in the best case scenario. The authors
mention that they need to do a better analysis and give better bounds for
the worst case scenario.
This archive was generated by hypermail 2.1.6 : Fri May 09 2003 - 10:48:32 PDT