Single-Agent Policy Tree Search With Guarantees
We introduce two novel tree search algorithms that use a policy to guide search. The first algorithm is a best-first enumeration that uses a cost function that allows us to prove an upper bound on the number of nodes to be expanded before reaching a goal state. We show that this best-first algorithm is particularly well suited for "needle-in-a-haystack" problems. The second algorithm is based on sampling and we prove an upper bound on the expected number of nodes it expands before reaching a set of goal states. We show that this algorithm is better suited for problems where many paths lead to a goal. We validate these tree search algorithms on 1,000 computer-generated levels of Sokoban, where the policy used to guide the search comes from a neural network trained using A3C. Our results show that the policy tree search algorithms we introduce are competitive with a state-of-the-art domain-independent planner that uses heuristic search.
The paper presents two planning algorithms based on tree search. The novelty of these algorithms is the use of a policy based criterion instead of a standard heuristic to guide the search. The first algorithm (LevinTS) uses a cost function d(n)/\pi(n) which ensures nodes are expanded in a best-first order. This allows the authors to derive an upper bound to the number of expansions performed before to reach a target node. The second algorithm (LubyTS) is a randomized algorithm based on the sampling of trajectories. Using a specific restarting strategy, the authors derived an upper-bound to the expected number of expansions before reaching a target state. Both the algorithms are analyzed under the assumption of a deterministic environment.  Comments ------------ The paper is overall well written and easy to follow for the part concerning the algorithms. What is less clear to me is the context and motivations.   - This paper is about planning given a baseline policy. The main issue I see here is that if the provided policy has zero or small probability of reaching the goal, the algorithms will fail. In the case of non-zero (small) probability, LevinTS is still able to find an optimal solution but with a very large number of node expansions (see Thm 3). I suppose that this is the reason why you pre-trained the policy using RL in the experiments (this allows overcoming the issue). This is a strong weakness of the proposed approach. Model-based algorithms (LevinTS is model-based) for planning do not have such requirements. On the other hand, if the goal is to refine a policy at the end of some optimization procedure I understand the choice of using a policy-guided heuristic.   - Concerning LubyTS it is hard to quantify the meaning of the bound in Thm. 6 (the easy part is to see when it fails, as mentioned before). There are other approaches based on generative models with guarantees, e.g., (Grill, Valko, Munos. Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning, NIPS 2016). How do you perform compared to them?  - Your setting is very specific: you need to know the model or/and have access to a generative model (for expanding or generating trajectories),  the problem should be episodic and the reward should be given just at the end of a task (i.e., reaching the target goal). Can you extend this approach to more general settings?   - In this paper, you perform planning offline since you use a model-based approach (e.g., generative model). Is it possible to remove the assumption of the knowledge of the model?  In that case, you would have to interact with the environment trying to minimize the number of times a "bad" state is visited. Since the expansion of a node can be seen as an exploratory step, this approach seems to be related to the exploration-exploitation dilemma. Bounding the number of expansions does not correspond to having small regret in general settings. Can you integrate a concept related to the long-term performance in the search strategy? This is what is often done in MCTS.  All the proposed approaches have weaknesses that are partially acknowledged by the authors. A few points in the paper can be discussed in more details and clarified but I believe it is a nice contribution overall.  -------- after feedback I thank you for the feedback. In particular, I appreciated the way you addressed the zero probability issue. I think that this is a relevant aspect of the proposed approaches and should be addressed in the paper. Another topic should be added to the paper is the comparison with Trailblazer and other MCTS algorithms. Despite that, I personally believe that the main limitation is the assumption of deterministic transitions. While the approach can be extended to stochastic (known) models I would like to know how the theoretical results become.