DESPOT: Online POMDP Planning with Regularization
POMDPs provide a principled framework for planning under uncertainty, but are computationally intractable, due to the "curse of dimensionality" and the "curse of history". This paper presents an online POMDP algorithm that alleviates these difficulties by focusing the search on a set of randomly sampled scenarios. A Determinized Sparse Partially Observable Tree (DESPOT) compactly captures the execution of all policies on these scenarios. Our Regularized DESPOT (R-DESPOT) algorithm searches the DESPOT for a policy, while optimally balancing the size of the policy and its estimated value obtained under the sampled scenarios. We give an output-sensitive performance bound for all policies derived from a DESPOT, and show that R-DESPOT works well if a small optimal policy exists. We also give an anytime algorithm that approximates R-DESPOT. Experiments show strong results, compared with two of the fastest online POMDP algorithms. Source code along with experimental settings are available at http://bigbird.comp. nus.edu.sg/pmwiki/farm/appl/.
---Response to Author Response--- Thank you 
      for the clarifications. Just a couple of points: - While I do 
      agree that characterizing the class of problems that have small optimal 
      policy trees would be interesting, I think the paper could do a better job 
      of describing the approach's strengths and weaknesses, even without fully 
      answering this theoretical question. The authors must surely have some 
      intuitive examples of problems where this algorithm should do very well, 
      and problems on which it should do poorly. Sharing this intuition would 
      significantly strengthen the paper in my opinion. - Relatedly, 
      whether DESPOT is better at exploiting certain kinds of prior information 
      was only part of my question. It is also important to address whether 
      DESPOT *requires* prior knowledge to do well. From that perspective I 
      don't think empirical comparison is difficult; you can simple try out 
      DESPOT with an uninformed default policy (e.g. uniform random). If it does 
      well, it would alleviate concern about the need for a good default policy. 
      It if does poorly, it will be illustrative of problems for which DESPOT 
      would not be a good choice. Either way it would increase the knowledge 
      transmitted by the paper without requiring much additional effort or 
      space. ---Summary of paper--- The paper presents an online 
      POMDP planning algorithm that uses both classical search methods and Monte 
      Carlo sampling to select an action. The main idea of the algorithm is to 
      pre-sample random events (a la PEGASUS) in the roll-out tree, and then 
      compute a good policy for the determinized future (values at the leaves 
      are estimated using Monte Carlo samples of a default policy). The policy 
      search is regularized to prefer "smaller policies" (policies that fall 
      back on the default policy after a small number of steps) and the 
      determinized tree can be pruned using a heuristic branch-and-bound 
      algorithm to reduce the computational cost of finding a policy. 
      Performance bounds are given in terms of the number of samples, depth of 
      the tree, *and* the size of the optimal policy on the tree. Experiments 
      show the algorithm performs well in several large POMDPs in comparison to 
      contemporary competing methods. ---Quality--- As far as I 
      can tell the analysis is technically correct. The bounds derived give 
      insight into the algorithm's properties (though it's not clear how much 
      purchase the bounds have once the DESPOT is approximated) and for the most 
      part match the intuitions given. The main thing I would have liked 
      to see in this paper is more of a discussion of the strengths and 
      weaknesses of this approach, particularly in comparison to the UCT-like 
      approach (POMCP). The introduction claims that R-DESPOT has better 
      worst-case behavior, but this is only the case if the optimal policy tree 
      is "small." I think the paper would be much stronger if it contained more 
      discussion of what the implications of a "small" policy are. In what types 
      of problems is this likely to be the case and when is it catastrophically 
      not the case? I am most concerned that this may depend heavily on the 
      choice of default policy (because a "small" policy is one that mostly 
      defers to the default policy), meaning that for this method to perform 
      well, one must already have a high quality policy available. I think that 
      trying to exploit the existence of a simple optimal policy is sensible, 
      but it's not clear to me that this is a good way to think about simple 
      policies -- it would help to have a better idea of what the assumption 
      means in terms of the problems it does/does not encompass. 
      Relatedly, and perhaps more importantly, it's not clear to me that 
      the experiments are really a fair comparison. R-DESPOT is given a 
      domain-specific default policy in each experiment. While I can tell that 
      the authors have tried to keep these policies intuitive and simple to 
      specify, they nevertheless seem to constitute prior knowledge that is not 
      supplied to the other methods. It is hard, therefore, to tell how much of 
      the performance gap is due to the method, and how much is due to the 
      choice of default policy. I don't necessarily think this fatally 
      undermines the results. I think it would be reasonable, for instance, to 
      claim that R-DESPOT can exploit prior knowledge that other methods can't, 
      or that would be a challenge to encode for other methods. If that is the 
      claim, however, it needs to be stated explicitly and justified at least in 
      intuition. Even if it is difficult to supply comparable prior knowledge to 
      the other methods, I would have at least liked to have seen the 
      performance of R-DESPOT with a uniform random default policy, even if it 
      performed poorly, since this would be informative about whether R-DESPOT 
      is appropriate for a problem in which I do not have an informed default 
      policy. ---Clarity--- I found this paper to be clear and 
      very readable. I also found the mathematics in the supplementary materials 
      to be refreshingly well-presented and easy to follow. A small 
      suggestion: at first I found the paragraph at the end of Section 3 to be a 
      bit out of place. Once in Section 4 I quickly realized that it was meant 
      to foreshadow the R-DESPOT algorithm. This could be clarified with a 
      simple "We will make use of this idea in the next section in order to 
      develop a more practical algorithm" or similar. Type-o near bottom 
      of p. 1: behavoior ---Originality--- Though the method 
      presented here makes use of several existing ideas, it combines them in a 
      novel and interesting way. I felt the method was well-contextualized in 
      the relevant literature. ---Significance--- The problem of 
      planning efficiently in high-dimensional partially observable worlds is 
      both important and challenging. The algorithm presented here is rooted in 
      theoretical performance bounds and performs well empirically. Though I do 
      still have questions regarding the need for prior knowledge, in some 
      domains prior knowledge is available. The main potential for impact that I 
      see is that the algorithm represents a seemingly viable alternative 
      approach to UCT-like algorithms (as well as a different style of analysis) 
      that may serve as inspiration for further algorithmic developments in this 
      area.