Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors propose an novel planning algorithm that treats each iteration in the divide-and-conquer algorithm as an MDP decision step and perform Monte-Carlo tree search (MCTS) on top of it. Experiments on both discrete and continuous planning task demonstrate the effectiveness of the proposed algorithm over existing MCTS planners.

The idea is interesting and novel in the sense that for existing methods in planning, in each step we expand the search tree outward by a step size, but not split the search space in half and work on each subproblem. From this aspect, two highly related papers are worth discussing/comparing to in the paper in order to better position the current work. In LA-MCTS\cite{wang2020learning}, each node also represents a split of the search space. The difference is that their work is on black-box optimization and they return a single point instead of a plan. For goal-directed planning, spliting the original problem into subproblems create an AND/OR tree search space. To tackle this, Retro*\cite{chen2020retro} proposes a neural version of the A* algorithm on AND/OR trees (AO* algorithm). Although they are tasking a different problem, their retrosynthesis task can also be seen as a goal-based problem where the goal is the molecule they want to synthesize.

The methodology is presented with good writing and organization. I am able to understand the approach clearly but with the following question. If (at the beginning) the policy prior is not trained well, it is possible that the prior keep proposing subgoals that are on the same plan which is suboptimal. Therefore many samples will be wasted. Is the exploration mechanism in PUCT able to handle this? Or the PUCT is going to `explore' (be trapped) inside the same plan again and again and not able to propose an near-optimal plan.

To evaluate the proposed algorithm, the authors conduct experiments on both discrete and continuous grid worlds and compare the performance with MCTS. The analysis of both experiments are comprehensive. However, my concern on this part is that the evluation is not convincing since there is only one baseline which is MCTS, which itself is not the best planner for goal-directed planning. For planning baselines, consider adding 2D A* (discrete case) or RRT* \cite{karaman2011sampling} (continuous case). Or the authors can compare with hierarchical RL methods. To improve the paper (but might not neccessary), I suggest the authors to replace the continuous grid world with other control tasks such as robot arm control. Currently the two experiments are too alike.

In general, I think the paper presents an novel approach which is promising and potentially beneficial to other areas in machine learning. However the current paper is not ready for publication in its current form due to the reasons listed above. I would consider raising my score if the authors address my concerns in the revision.


@article{wang2020learning,
  title={Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search},
  author={Wang, Linnan and Fonseca, Rodrigo and Tian, Yuandong},
  journal={arXiv preprint arXiv:2007.00708},
  year={2020}
}


@inproceedings{chen2020retro,
  title={Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search},
  author={Chen, Binghong and Li, Chengtao and Dai, Hanjun and Song, Le},
  booktitle={The 37th International Conference on Machine Learning (ICML 2020)},
  year={2020}
}

@article{karaman2011sampling,
  title={Sampling-based algorithms for optimal motion planning},
  author={Karaman, Sertac and Frazzoli, Emilio},
  journal={The international journal of robotics research},
  volume={30},
  number={7},
  pages={846--894},
  year={2011},
  publisher={Sage Publications Sage UK: London, England}
}

Update after rebuttal:
Thanks for the response! The authors resolve my concerns except for the baselines. I agree that MCTS is the most relevant baseline, but the authors should also include stronger baselines as well. Obviously, MCTS is far from the best performing algorithm on grid world navigation tasks. I encourage the authors to either adding stronger baselines or switch to another task where MCTS is the dominant algorithm. I still think the current evaluations are not adequate to publish in a top-tier conference. Therefore I will keep my score unchanged.


review_title: Borderline paper

final_score: rating: 7: Good paper, accept
review_content: Summary: The paper tackles the problem of multi-task navigation, where the agent sees a different goal-directed (navigation) task at the start of each episode. The paper is reasonably well-written and easy to understand although the text might benefit from an illustrated example. The primary contributions of the paper are algorithmic. The DC-MCTS algorithm seems quite interesting and novel, as far as I can tell, although some of the assumptions (e.g., "task embedding") may reduce applicability. The experiments are a bit thin in their current form which makes it difficult to compare the proposed algorithm to the rather large body of literature in classical planning and robot navigation. With additional empirical analysis, this could be a nice addition to the literature on integrating learning and planning for control in navigation tasks. I look forward to reading the other reviews and the author response.


Detailed Comments
  - The paper tackles the problem of navigation tasks in MDPs, where the a new task is received on every episode (multi-task). The only reward is for reaching the desired goal state. The problem setup assumes that a low-level (naive) goal-directed policy and its value function is available along with a global (optimal) value function. The algorithm leverages this policy in conjunction with a high-level planner to decompose the large navigation task (on which the low-level policy is likely to fail) into smaller sub-tasks. This is done via a sequence of good sub-goal states, recursively broken down roughly in half at each level of the tree. This continues until the sequence of navigation task are "simple" enough for the low-level policy to tackle consecutively. The overall result is a higher probability of successful navigation to the goal compared to a "vanilla" MCTS performing sequential planning.

  - If I've understood correctly, it seems this approach are that the approach does not require a simulator or environment dynamics to construct the search tree. (Right?) Rather, it leverages components (p, \pi, v^\pi) learned or estimated offline from prior experience in different but related navigation tasks. This has the advantage of compressing knowledge about the environment and task into a relatively compact parametric form. However, the experiments suggest that the algorithm is extremely sensitive to noise or error in the learned components. A careful empirical study of the algorithm's sensitivity to the error in these components will likely be required. More on this later.

  - The algorithmic contributions and the intuitions of this paper seem novel to me although I didn't search the classical planning or robotics literature in too much depth. The Related Work section seems relatively complete to me but I'm eager to see if other reviewers can identify relevant related work.
  
  - Overall, I think the paper could be made easier to understand with a running multi-task example illustrating the core concepts (episode, sequence, plan, trajectory, search tree, solution tree, value functions and policy). Maybe Figure 1 can be expanded and introduced earlier in the paper? Also, it might help to define the given "new MDP" more formally. While this is intuitively clear in the domains considered, I think a more formal description would be better.

  - The main contributions of this paper are algorithmic. Specifically, the proposed algorithm DC-MCTS combines learned components and online planning to efficiently decompose a large search space into sufficiently small ones, so that the given "low-level" components (\pi and v^\pi) can be utilized. The key idea is to decompose the search for a high-probability path between the start and goal states into two (roughly equal "sized") sub-problems by introducing a "sub-goal" (another state) between the original pair as a path constraint. A sequence of such sub-goals book-ended by the start and goal states is a "plan". This seems to be the core idea and is quite simple so I'm surprised it hasn't been explored before in the classical planning literature. As the paper notes, there are strong similarities to classical planning algorithms (AO^*). My own search didn't turn up much so I'd be curious to see what the other reviewers find.

  - I don't think I fully understand the implications of the task embedding (c_M) on the problem setup. Does it imply that DC-MCTS can only tackle fully observable problems? What happens if c_M has error (e.g., learned embedding)? More generally, I'm looking to understand the practicality of the task embedding requirement compared with the more traditional navigation problem setups considered in the deep RL and robotics literature (e.g., https://openreview.net/pdf?id=SJMGPrcle). How would DC-MCTS work if restricted to raw local inputs and prevented from seeing the full maze (via c_M) or received a noisy task embedding?

  - Does DC-MCTS (and the baseline MCTS variant) return a full plan (list of sub-goals) for the given "problem" (state pair at the root) which is then executed by the low-level policy in the environment? I was expecting it to follow the typical anytime planning approach in MCTS where search and behavior are interleaved for each decision in the actual environment. Appendix B.5 suggests that the full plan may be used but maybe B.5 is just an efficient way to get training data for HER and p? Please clarify and consider including these details in the illustration.

  - The experiments are performed in two domains: a grid world and a continuous MuJoCo task. DC-MCTS seems substantially better than the corresponding MCTS in the same search space. The search budget is measured in the number of calls to the oracle value function which allows the two methods to be compared. This section feels a bit under-developed at the moment. The experiments seem to be at a preliminary stage. Although DC-MCTS seems better than the sequential MCTS (in the same search space), the absence of strong baselines on these problems makes these results difficult to interpret. The problem is exacerbated since the baseline seems to be performing very poorly in the MuJoCu domain. Please consider including additional baselines from classical planning / deep RL / robotics (e.g., AO^* variants, Gabor 2019, https://openreview.net/pdf?id=SJMGPrcle). Currently, it's a bit hard to place DC-MCTS in the large body of empirical literature on this subject. Also, when comparing these baselines, I think including additional profiling information (wall-clock runtime, memory usage, etc.) would help the reader get a better understanding of the algorithm's practical performance.
  
  - The empirical results show that both MCTS algorithms are extremely sensitive to the quality of the global value functions. How sensitive is the overall performance to the choice of the low-level policy? Please consider including additional experiments and analysis of this sensitivity and perhaps additional domains as well. Without these details, it's difficult for the reader to understand the requirements on the learned components and evaluate the algorithm's performance, which is a bit unfortunate as the algorithm is nice. Also, please consider releasing the source code as MCTS experiments can be difficult to reproduce, especially when combined with offline learning setups.

  - Why is the search budget fixed at 200? How do the methods perform with additional computational budget or memory (more nodes expanded at each level)? Would the baseline MCTS perform better given additional resources?

  - Overall, I think the algorithmic ideas and intuition presented in this paper are interesting. The problem setup and DC-MCTS seems to be novel (as far as I can tell) although classical planning and robotics has long investigated similar problems so I could have easily missed something. The implications of the problem setup (e.g., task embedding) are a bit unclear to me. Also, the experimental section is currently a bit thin and doesn't provide much insight into the empirical performance and robustness of the search algorithm against strong baselines and in different computational settings. I look forward to reading the other reviews and the author response.
  

Minor points
  - n doesn't seem to be defined in Section 2.1.

UPDATE: I thank the authors for their detailed feedback. The authors have addressed a number of concerns and I've increased my score to accept. I continue to think that the empirical section could be easily improved with additional domains, sensitivity to noise, etc. and a careful running example (Fig 1 unfortunately isn't). However, the current draft seems sufficient for publication due to the interesting algorithm (which is novel, as far as I can tell).
review_title: Interesting approach to a well-studied problem but hard to evaluate overall contribution. Needs better experiments.

final_score: rating: 5: Marginally below acceptance threshold
review_content: summary:
This paper proposes Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS), a planning algorithm for goal-directed decision-making problems, which makes a plan of the trajectory via recursive hierarchical partitioning. DC-MCTS assumes a (suboptimal) goal-directed low-level policy and its oracle value function. Then, it formulates the given planning problem as finding a sequence of sub-goal states and applies the divide-and-conquer strategy, i.e. split the original task into two sub-tasks (defined as initial state and goal state) and recursively solve them. Unlike the standard MCTS, the decision making of DC-MCTS operates not on the action space but on the state space of the problem, and the decision is made non-sequential way. Experimental results show that DC-MCTS outperforms the MCTS baseline that expands only the right sub-problem.



pros:
- It is interesting to perform planning for sequential-decision making problems in a non-sequential manner via a divide-and-conquer approach.


cons:
- The assumption that goal-conditioned policy and its value is required seems to be too strong, which may limit the generality of the proposed method.

- In the experiments, the baseline algorithm seems to be weak. For example, it would have been nice if it could be compared with other recent methods that combine goal-conditioned RL and planning (e.g. [1], [2]) if applicable. Also, PUCT-like planning algorithms that operate in usual action space could also be a good baseline, where the policy prior can also be trained with HER.



comments and questions:
- It seems to be unfair that the training strategy for the heuristics is different for DC-MCTS and the MCTS baseline. It would be great to see the performance of MCTS that uses the same heuristics training strategy as DC-MCTS.

- The DC-MCTS can be seen as treating 'state space' as 'action space', which implies that it has a much larger branching factor than the traditional action-selecting MCTS since the number of states is typically much larger than the number of actions. Then, why should DC-MCTS be preferred over planning algorithms that operate in usual action spaces? It would be great to see a comparison with the PUCT baseline that works in the original action spaces, where the prior policy and value function is trained using HER.

- (page 7) Did the model-free baseline in the initial experiments use HER? or was it trained only with the actually experienced samples?

- In Figure 2, why the solved ratio did not converge to 1? What kind of behavior can we observe qualitatively when the algorithm fails to solve?

- It seems DC-MCTS is relevant to path planning algorithms. Then, for example, could DC-MCTS be compared with the RRT family?

- Above section 3.2: (line 17-18 in TRAVERSE) -> (line 15-16 in TRAVERSE) ?


[1] Eysenbach et al., Search on the Replay Buffer: Bridging Planning and Reinforcement Learning, NeurIPS 2019
[2] Nasiriany et al., Planning with Goal-Conditioned Policies, NeurIPS 2019

review_title: interesting idea but weak experiments

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary
---

This paper proposes Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for for goal-directed planning problems (i.e. problems where reaching a specific goal state is the objective, like traversing a maze with specified start and goal positions). The assumed setting is one where transition and reward models of the environment are not (necessarily) available, but a low-level goal-directed policy that can attempt to navigate from a given start to a given goal position, as well as value oracle that can return the success probability of the low-level policy on any given task, are available. Planning problems are modelled as AND/OR search trees, where OR nodes are labelled by a start state s and a goal state s'', and AND nodes are labelled by triples (s, s', s''). An OR node has children for every possible state, such that traversing to a child indicates the insertion of the corresponding state as an additional subgoal in between s and s', plus one extra child to indicate the choice of returning the current plan without inserting any additional subgoals. AND nodes have two children; one OR node for the first half (s, s') of the plan, and a second OR node for the second half (s', s'') of the plan. The MCTS can construct a plan by inserting subgoals such that they become easier to solve for the low-level policy by searching this tree.

Strong Points
---

1) Interesting problem setting, way of modelling the problem, and proposed algorithm. Technically sound as far as I can tell.
2) Solid and clear writing.
3) Interesting results.

Weak Points
---

The second paragraph of the Introduction describes two fundamental challenges in sequential planning; (i) assumption of reliable transition model existing, and (ii) credit assignment problem over long time horizons. Then the next paragraph basically starts out (I'm paraphrasing and probably slightly exaggerating here) that we overcome these challenges by changing our assumptions to include that we are already given a goal-directed low-level policy and a value oracle. This may leave the reader wondering "well what if I don't have them?", or "are there practical scenarios where these assumptions are realistic?". 

Personally I don't necessarily believe that all research has to immediately have examples of practical applicability readily available, it can still be interesting without it... but in this case, I think it shouldn't be too difficult to actually provide some example situation where these assumptions hold, and including that could make the introduction a bit more convincing. Maybe it's just me, but in particular also the word "oracle" in "value oracle" keeps me scared and wondering for a long time if we're really going to end up needing a hard, ground-truth oracle (unrealistic assumption), only to finally figure out much later in the paper that it's okay for this to just be approximated.

Overall Recommendation
---

I recommend accept. The strong points are clear, and the weak points are quite minor.

Questions for Authors
---

Would it be possible to clarify in more detail how the standard MCTS baseline can be implemented in terms of the Algorithm 1 pseudocode? In Section 5 it's very briefly mentioned that the only changing is restricting DC-MCTS to only expand the "right" sub-problem in line 11 (which I assume should actually refer to lines 9-10). But then G_{left} has no value, and G_{left} is also still required in line 12. Intuitively I think I get the point, that only being allowed to look at the right half of AND nodes forces the algorithm to construct plans again in the same order in which they get executed, and probably by thinking about it more deeply I could figure out how to reconstruct the correct implementation, but either way I feel like it's not super obvious so may be worth clarifying in slightly more detail.

Minor Comments
---

- Final paragraph of Section 1, when listing all the subsequent sections, skips Section 4.
- "where \varnothing is them empty" --> "where \varnothing is the empty" (second paragraph 2.1)
- "MPDs" --> "MDPs" (third paragraph 2.1)
- Even though it's fairly obvious already, I guess I'd prefer "maximizing" rather than "optimizing", to be 100% explicit
- At the end of Section 2: "Figure 5 in Appendix 5.3".... but there is no appendix 5.3 and Figure 5 is not in an appendix.
- "MDP wit a" --> "MDP with a" (first paragraph Section 3)
- "free to chose" --> "free to choose" (A.4)
- "procudre" --> "procedure" (B.5)
review_title: Solid paper, just some small points where clarification may be useful

Meta-review: This paper proposes an MCTS approach to goal-conditioned planning, where the search generates high-level sequences of subgoals for low-level policies. This top-level planner is basically a search-based implementation of SSST for potential gain in computational requirements with the help from the advanced search techniques behind PUCT that combines MCTS and prior information. 

Reviewers generally agreed that this is an interesting and novel approach to planning and reinforcement learning. However, reviewers generally expressed that the experiments fall short to convince readers that this technique has greater impact and potential for a wider range of applications, other than GridWorld-like environments. Authors are encouraged to provide a more extensive set of experiments, adding more variety to the domains and ablation studies such as the impact of incorrect prior on the overall search performance. 

Decision: Reject