From: Tyler Robison (trobison_at_cs.washington.edu)
Date: Wed Nov 19 2003 - 01:58:36 PST
Symbolic Heuristic Search for Factored Markov Decision Processes
Zhengzhu Feng and Eric A. Hansen
This paper describes an improvement on SPUDD by using symbolic
reachability analysis (giving consideration only to states that we can
reach) and dealing with sets of states instead of individual states (and
so avoiding undesirable exponential blow-up).
Important Ideas:
Although the techniques presented in this paper are not new, they
are shown to be effective when applied to MDPs. The results of either
flavor of LAO* are impressive when compared with SPUDD, especially for
large state spaces. Also, the paper shows the problem cast as a search,
and emphasizes the importance of a strong admissible heuristic.
Flaws:
As I inevitably point out in all these papers, the experiments
aren't quite convincing enough, and we aren't told enough about them; it
is difficult to be impressed by a table of numbers alone. Also, it would
be helpful to see more experiments designed as 'extreme cases' of some
problem or situation, and see how well the technique deals with these.
Research Ideas:
First and foremost, more and more varied experimentation would
make a stronger case for the approach of this paper, and at the same time
provide better insight into its strengths, weaknesses and uses.
Also, as mentioned in the paper, even though it is itself an
improvement on an existing system, it too could be further investigated,
tweaked and improved. As this paper itself demonstrates, new performance
gains need not result from new innovations.
This archive was generated by hypermail 2.1.6 : Wed Nov 19 2003 - 01:58:37 PST