Aggregating Optimistic Planning Trees for Solving Markov Decision Processes
This paper addresses the problem of online planning in Markov decision processes using a randomized simulator, under a budget constraint. We propose a new algorithm which is based on the construction of a forest of planning trees, where each tree corresponds to a random realization of the stochastic environment. The trees are constructed using a "safe" optimistic planning strategy combining the optimistic principle (in order to explore the most promising part of the search space first) with a safety principle (which guarantees a certain amount of uniform exploration). In the decision-making step of the algorithm, the individual trees are aggregated and an immediate action is recommended. We provide a finite-sample analysis and discuss the trade-off between the principles of optimism and safety. We also report numerical results on a benchmark problem. Our algorithm performs as well as state-of-the-art optimistic planning algorithms, and better than a related algorithm which additionally assumes the knowledge of all transition distributions.
---Response to Author Response--- Thank you 
      for the clarifications. I hope the authors will consider the following 
      points: - I'm glad the authors plan to add more comparative 
      results, as they are much needed, but I still see no reason not to compare 
      to UCT. I appreciate the value of comparing to algorithms with similar 
      theoretical properties, but that does not preclude also comparing to the 
      current go-to algorithm in this problem setting. If ASOP does better than 
      UCT in one or more examples, then that is compelling evidence for ASOP's 
      practical applicability as well as its theoretical desirability. If UCT 
      does better then we get a sense of the magnitude of the practical cost of 
      ASOP's desirable guarantees (and can compare that to other algorithms that 
      make similar promises). Neither outcome diminishes ASOP's contribution and 
      either way the paper creates more knowledge for very little extra effort 
      or page space. - I appreciate the clarification of the 
      relationship between the regret bounds for ASOP and UCT; I hope future 
      versions of this paper will make a similar direct comparison. - I 
      may be missing something, but I'm not sure I see why it would be difficult 
      to apply Coquelin and Munos' algorithms to your planning problem. 
      "Modified UCT" is essentially just UCT except the exploration bonus is 
      smaller in deeper nodes and it enjoys a singly exponential regret bound 
      with high probability. In any case, the point is just that the paper makes 
      prominent mention of UCT's unfortunate worst case bound, but does not 
      clearly situate ASOP amongst other algorithms in this setting that also 
      improve upon UCT's worst case behavior (even those that are explicitly 
      cited!). - I now understand better what was meant by "good 
      approximation to the MDP." For me personally, the S3 tree being a good 
      approximation to the MDP suggests that the tree is a close approximation 
      to the MDP model. It sounds like the real point is that the *value 
      function* if the tree is a close approximation to the value function of 
      the MDP. I think it would not be difficult to make this wording more 
      clear/specific in the paper. - The clarification regarding the 
      best-first expansions helps, and I hope similar clarity will be added to 
      the paper. I personally would find it informative to see an empirical 
      comparison to ASOP with only breadth-first expansions as an illustration 
      of the relative importance of the "optimism" in the algorithm, but if the 
      role of the best-first expansions is clarified in the text, I don't think 
      it would be critical to add this. ---Summary of paper--- 
      The paper presents an online planning algorithm for large MDPs. 
      The main idea is to sample several determinations of the system in the 
      form of roll-out trees where each state/action pair has only one sampled 
      successor. A combination of breadth-first and best-first search is used to 
      explore the deterministic trees, and then they are recombined to create a 
      stochastic model from which a policy can be calculated. The algorithm is 
      proven to be consistent (as the number of trees and number of nodes in 
      each tree both approach infinity, the value at the root can be arbitrarily 
      approximated with high probability). The algorithm is empirically compared 
      to an planning algorithm that requires a full transition model and 
      performs well in comparison. ---Quality--- The analysis 
      provided is, as far as I can tell, correct. I am intrigued by the overall 
      approach, and particularly like the intuition that the S3 trees are 
      "off-policy Monte Carlo" samples. My main concern is with the evaluation 
      of the algorithm. The strengths and weaknesses of this algorithm in 
      comparison to existing approaches to this problem are not very well 
      explored. The shortcomings of UCT are given as primary motivators 
      for this work, and yet ASOP is not empirically compared to UCT (or to 
      "Modified UCT," the algorithm given in [4] with a singly exponential 
      regret bound with high probability). Also, the regret analysis given here 
      is in terms of the simple regret, but the worst case analysis in [4] is 
      not, making it difficult to compare the two to get a sense of the extent 
      of the improvement (if any) in the bounds. The regret in [4] is related to 
      the number of visits to sub-optimal leaves, and, because it is performing 
      breadth-first search, it seems straightforward to force ASOP to visit 
      exponentially many sub-optimal leaves. So, it is not clear whether this 
      algorithm's theoretical performance guarantees represent an improvement 
      over existing algorithms. The empirical comparison to OP-MDP seems 
      strange, since it is not even intended for the same problem setting. The 
      fact that OP-MDP requires a full transition model seems to limit the 
      experiment to smallish MDPs, which is counter to the point of ASOP, isn't 
      it? The argument seems to be implied that, because OP-MDP requires access 
      to the transition dynamics, it should have an advantage but, having never 
      heard of it before, I have no idea what kind of performance to expect from 
      OP-MDP nor what to make of the fact that ASOP does better. I can't even 
      tell if either algorithm is doing objectively well, since I don't know 
      what optimal performance would look like in this problem. In all, I did 
      not feel this was an effective or informative empirical demonstration. 
      The authors should correct me if I am wrong, but it didn't seem 
      like the optimistic part of the algorithm actually played any role in the 
      regret bound. Presumably, then, this part of the algorithm is there to 
      improve empirical performance? If that is the case, it seems like it 
      should be better evaluated. How much do the best-first expansions really 
      help performance? Is it possible for them to hurt performance? Are there 
      another expansion strategy one could consider combining with breadth-first 
      search? In the conclusions section it is suggested that ASOP 
      should perform best when single-successor trees are good approximations to 
      the original MDP, but I don't see much indication of this in the theory or 
      the experiments. Conceptually, when I think about the extreme case of a 
      deterministic environment, it seems like ASOP would either waste its time 
      creating multiple identical trees or, if it determinism is known a priori, 
      only create one tree but simply perform simultaneous breadth-first and 
      best-first search, which in a lot of cases has done much worse than Monte 
      Carlo tree search algorithms. So I think it would help to have some more 
      justification of this statement. ---Clarity--- For the 
      most part I found the paper to be clear, and the ideas accessible. I 
      appreciate that the high level idea was well-laid out before diving into 
      the details, and that each component of the framework was placed clearly 
      in context in the larger algorithm. I also found the proofs to be mostly 
      easy to follow with a good mix of intuitive and formal argument (though 
      there were some parts that tripped me up, listed below). - Eq. 1 
      would be more clear if it was "d = …" - The proof of Lemma 2 ends 
      in "< \epsilon", but should be "= \epsilon", so the lemma statement 
      should be "<= \epsilon" (adjustments also needed in later statements). 
      - Shouldn't the exponent in Eq. 3 be ceil[log(\epsilon/4(1 - 
      \gamma))(log \gamma)^{-1}] + 1? I'm not sure where some of those -1s came 
      from. - Figure 3 is never discussed. What are we meant to learn 
      from it? There are also several type-os and grammatical mistakes 
      throughout, so the authors should be sure to take some more 
      editing/polishing passes. ---Originality--- The 
      algorithm's conceptual connections to existing work are clearly laid out. 
      I believe the algorithm and its analysis to be novel, and the general 
      approach seems interesting. ---Significance--- The 
      presented algorithm does seem like a new approach to online planning in 
      large domains. It's possible that this approach will turn out to yield 
      significant advances in the state of the art. However, at the end of this 
      paper, I did not feel I had a sense of where this algorithm fits in with 
      existing techniques. It's not that I think every paper needs to be a horse 
      race ending with "Our algorithm is better than that other algorithm." I do 
      think that a new approach, even if it does not immediately compete with 
      existing methods, might still be interesting and valuable to have in the 
      literature. However, there has to be some indication of what that approach 
      brings to the table that is not already there, some indication of what 
      promise it may hold. In this paper, ASOP is presented largely as a novel 
      algorithm in a vacuum, without any comparative analysis (whether 
      theoretical, empirical, or even intuitive). In my opinion that 
      substantially hurts the potential impact of the 
      work.