Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning
You are a robot and you live in a Markov decision process (MDP) with a finite or an infinite number of transitions from state-action to next states. You got brains and so you plan before you act. Luckily, your roboparents equipped you with a generative model to do some Monte-Carlo planning. The world is waiting for you and you have no time to waste. You want your planning to be efficient. Sample-efficient. Indeed, you want to exploit the possible structure of the MDP by exploring only a subset of states reachable by following near-optimal policies. You want guarantees on sample complexity that depend on a measure of the quantity of near-optimal states. You want something, that is an extension of Monte-Carlo sampling (for estimating an expectation) to problems that alternate maximization (over actions) and expectation (over next states). But you do not want to StOP with exponential running time, you want something simple to implement and computationally efficient. You want it all and you want it now. You want TrailBlazer.
This paper introduces a new Monte Carlo-based planning algorithm called TrailBlazer. The algorithm assumes the access to the generative model of the MDP, and its goal is to find the optimal value function of the root node V(s0) with as few call to the generative model as possible. The setting is discounted reward.  The algorithm works for both finite and infinite state spaces. The paper provides several theoretical guarantees: PAC consistency, a high-probability upper bound on the number of calls to the generative model for finite state spaces, and an upper bound on the expected number of calls for infinite state spaces.  Depending on the scenario, the paper either 1) improves the previous worst-case upper bounds (e.g., for finite state space and with stochastic dynamic) or 2) is the same as the previous results (deterministic dynamic; or without control — the same as Monte Carlo), or 3) provides new results (infinite state space).  The TrailBlazer algorithm alternates between two types of nodes: Avg and Max. An Avg node computes the average value of its children, which are generated according to the transition probability. So it is essentially a Monte Carlo estimator. The parameter m controls the variance of this estimator. The Max node tries to find the value of the maximizing node among its children. It does so by eliminating the children that cannot be a child with maximum value (with high probability).
This is a good paper. It introduces a new algorithm, which has a potential to be used in many applications. The algorithm not only has the basic theoretical justification (consistency), but also comes with certain guarantees that are stronger than what is already known (for finite state space with generative model and stochastic system).  The paper is generally well-written. But I think it can be revised to give more intuition as why the proposed algorithm works better than other approaches. The intuition is somehow missing. Also because of the induction on the tree, the proofs are not very straightforward. I don’t know if much can be done about it though.  I have some comments/questions:  - What is the main reason that the guarantee in Theorem 3 is only in expectation?  - The algorithm does not exploit the possible regularities of the value function, e.g., its smoothness. Is it possible to benefit from them, for example, similar to the StoSO algorithm (Valko, Carpentier, Munos, “Stochastic Simultaneous Optimistic Optimization,” ICML 2013)?  - The paper mentions that for non-vanishing action-gaps, the dimension d can be set to zero. More realistically, the action-gaps can follow a distribution over states (as introduced and analyzed by Farahmand, “Action-Gap Phenomenon in Reinforcement Learning,” NIPS 2011).  What can be said about such a case?  - Section 3.1 (Separate bias and variance) is not very clear. In particular, please expand on “In doing so, their algorithms compute … . However in our planning …”.   - Typos (The line numbers refer to the Supplementary material):  L81: worst —> worse L84: an near-optimal —> a near-optimal L220: “and an a term” L229: “an problem-dependent” L472: “i.d.d.” Appendix D: At several places, \Delta is written as Delta L504: “one need” —> “one needs”  ******* Thank you for your response.