From: Stefan B. Sigurdsson (stebbi_at_cs.washington.edu)
Date: Fri May 09 2003 - 13:06:46 PDT
Summary - Presents a comparison of three algorithms for making dynamic-programming updates in POMDP problems; the baseline "witness" algorithm, an "incremental pruning" algorithms previously presented by one of the same authors in a technical report, and (novel) generalizations on the incremental pruning algorithm that appear to improve its efficiency in most cases. Contains both analysis and empyrical evaluation.
Key ideas
- The efficiency improvements stem from a simple equality - purge(A1 + ... + An) = purge(A1 + purge(A2 + purge(... + purge(An)))). The step-wise purge is cheaper than purging after computing the entire cross sum.
- The algorithm is claimed to be asymptotically and empyrically faster than the baseline, and also easier to implement. That's impressive if true.
- I'm trying to grok the contribution of this paper; it appears to me that the IP algorithm was originally presented by the third author but (pure conjecture) not accepted for publication, and the other two authors had already presented an evaluation of the baseline algorithm. So the three of them got together and wrote up this comparison paper that may or may not have resulted in the IP algorithm becoming the new baseline.
Flaws, not-flaws
- The empyrical comparison methodology looks good to me; the comments on using the same subroutines/etc for testing the three algorithms are confidence inspiring. However, the number of subject problems is small and I have no idea whether the set is representative.
- Why don't planning papers have graphs? I don't get it - table three could lend itself to a column format. Is it because the numbers range so widely? How about normalized comparison then?
Directions
- The mention of the precision parameter is interesting. The asymptotic best/worst case analysis is future work. I don't have anything to suggest for directions beyond what the authors talk about in the paper - I just don't have good enough a grasp on this stuff yet.
Note - I normally like this kind of paper a lot, much terse mathness, but reading and understanding one can take up to a week; a full day at minimum. Didn't have that kind of time to put into this paper but it was still nice to take a brief, high-level look.
This archive was generated by hypermail 2.1.6 : Fri May 09 2003 - 13:06:46 PDT