Divide-and-Conquer Monte Carlo Tree Search
Authors: Giambattista Parascandolo
Lars Holger Buesing
Josh Merel
Leonard Hasenclever
John Aslanides
Jessica B Hamrick
Nicolas Heess
Alexander Neitz
Theophane Weber
Venue:  (2021)
Keywords: MCTS
planning
goal-directed planning
divide and conquer

Abstract: Standard planners for sequential decision making (including Monte Carlo planning, tree search, dynamic programming, etc.) are constrained by an implicit sequential planning assumption: The order in which a plan is constructed is the same in which it is executed.
We consider alternatives to this assumption for the class of goal-directed Reinforcement Learning (RL) problems.
Instead of an environment transition model, we assume an imperfect, goal-directed policy.
This low-level policy can be improved by a plan, consisting of an appropriate sequence of sub-goals that guide it from the start to the goal state. We propose a planning algorithm, Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS), for approximating the optimal plan by means of proposing intermediate sub-goals which hierarchically partition the initial tasks into simpler ones that are then solved independently and recursively. The algorithm critically makes use of a learned sub-goal proposal for finding appropriate partitions trees of new tasks based on prior experience.
Different strategies for learning sub-goal proposals give rise to different planning strategies that strictly generalize sequential planning.
We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds as well as in challenging continuous control environments.

Under review as a conference paper at ICLR 2021
DIVIDE-AND-CONQUER MONTE CARLO TREE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Standard planners for sequential decision making (including Monte Carlo planning, tree search, dynamic programming, etc.) are constrained by implicit sequential planning assumption: The order in which a plan constructed is the same which it is executed. We consider alternatives to this assumption for the class of goal goal-directed Reinforcement Learning (RL) problems. Instead of an environment transition model, assume imperfect, goal-directed policy. This low-level policy can be improved by a plan, consisting of an appropriate sequence sub- goals that guide from the start to the goal state. We propose a planning algorithm, Hivide-and-Conquee Monte Carlo Tree Search (DC-MCTS), for approximating the optimal plan by means of proposing intermediate sub-goals which hierarchically partition the initial tasks into simpler ones that are then solved independently and recursively. The algorithm critically makes use of learned sub-goal proposal for finding appropriate partition trees of new tasks based on prior experience. Different strategies for learning sub-goal proposals give rise to different planning strategies that strictly generalize sequential planning. We show that this algorithmic flexibility wrt. planning order leads to improved results navigation tasks in grid-workds as well in challenging continuous control environments.
INTRODUCTION
This is the first sentence of this paper, but was not the first one we wrote. In fact, the entire introduction section was actually one of the last sections to be added to this manuscript. The discrepancy between the order of inception of ideas and the order of their presentation this paper probably does not come as surprise to the reader. Nonetheless, it serves as point for reflection that central to the rest of this work, and that can be summarized as "the order which we construct plan does not have to coincide with the order in which we execute it".
Most standard planners for sequential decision making problems-iincldding Monte Carlo planning, Monte Carlo Tree Search (MCTS) and dynamic programming- a baked-in sequential planning assumption (Bertsekas et al.) 1995 Browne et al.) 2012). These methods begin at either the initial or final state and then plan actions sequentially forward or backwards in time. However, this sequential approach faces two main challenges. (i) The transition model used for planning needs to be reliable over long horizons, which is often difficult achieve when it has to be inferred from data. (ii) Credit assignment to each individual action is difficult: In planning problem spanning a horizon of 100 steps, assign credit the first action, we have to compute the optimal cost-to-go for the remaining problem with a horizon of 99 steps, which is only slightly easier than solving the original problem.
Traverse & Selcct
Expand
Backup & Update
OR--nde
A ANDetode
Figure 1: Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS).

---

Under review as a conference paper at ICLR 2021
To overcome these two fundamental challenges, here we consider alternatives to the basic assumptions of sequential planners. We focus on goal-directed decision making problems where an agent should reach a goal state from start state. Instead of transition and reward model of the environment, we assume a given goal-directed policy (the "low-level" policy) and the associated value oracle that returns its success probability on any given task[] In general, low-level policy will not be not optimal, e.g. it might be too "myopic" to reliably reach goal states that are far away from its current state. We now seek to improve the low-level policy via a suitable sequence of sub-goals that guide from the start to the final goal, thus maximizing the overall task success probability. This formulation of planning as finding good sub-goal sequences, makes learning of explicit environment models unnecessary, as they are replaced by low-level policies and their value functions.
The sub- sub-goal planning problem can still be solved by a conventional sequential planner that begins by searching for the first sub-goal to reach from the start state, then planning the next sub-goal in sequence, and so on. Indeed, this is the approach taken in most hierarchical RI. settings based on options sub-goals (e.g. Dayan & Hinton 1993; Sutton et al., 1999: Vezhnevets al. 2017). However, the credit assignment problem mentioned above persists, as assessing if the first sub-goal is useful still requires evaluating the success probability of the remaining plan. Instead, it could be substantially easier to reason about the utility of a sub-goal "in the middle" of the plan, as this breaks the long-horizon problem into two aub-problems with much shorter horizons: how to get to the sub-goal and how to get from there to the final goal. Based on this intuition, we propose the Sonde--nd-Conquue MCTS (DC-MCTS) planner that searches for sub-goals to split the original task into two independent sub-tasks of comparable complexity and then recursively solves these, thereby drastically facilitating credit assignment. To search the space of intermediate sub-goals efficiently, DC-MCTS uses a heuristic for proposing promising sub-goals that is learned from previous search results and agent experience.
Humans can plan efficiently over long horizons to solve complex tasks, such as theorem proving or navigation, and some plans even span over decades (e.g. economic measures): these situations, planning sequentially in terms of next steps such as what arm to move, or what phone call to make- - will cover a tiny proportion of the horizon, neglecting the long uncertainty beyond the last planned step. The algorithm put forward in this paper is step in the direction of efficient planners that tackle long horizons by recursively and parallelly splitting them into many smaller and smaller sub-problems. In Section [ we formulate planning in terms of sub-goals instead of primitive actions. In Section as our main contribution, we propose the novel Divide-and-Ce and-Conquer Monte Carlo Tree Search algorithm for this planning problem. In Section we position DC-MCTS within the literature of related work. In Section 5 we show that it outperforms sequential planners both on grid world and continuous control navigation tasks. demonstrating the utility of constructing plans in a flexible order that can be different from their execution order.
2 IMPROVING GOAL-DDRECCED POLICIES WITH PLANNING
Let S and A be finite sets of states and actions. We consider a multi-task setting, where for each episode the agent has to solve new task consisting of new Markov Decision Process (MDP) M over S and A. Each M has a single start state 8o and a special absorbing state S also termed the goal state. If the agent transitions into 8xc at any time it receives reward of and the episode terminates; otherwise the reward is O. We assume that the agent observes the start and goal states (50, 8x0) the beginning of each episode, as well as an encoding vector CM E Rd. This vector provides the agent with additional information about the MDP M of the current episode and will be key to transfer learning across tasks the multi-task setting. A stochastic, goal goal-directed policy æ is a mapping from S x S x Id into distributions over A, where π [[]ss, S CM) denotes the probability of taking action a in state 8 in order to get to goal 8 For a fixed goal 8:0: we can interpret m as a regular policy, here denoted as Naw mapping states to action probabilities. We denote the value of न in state s for goal 8 as (= 850 s50 (M); we assume no discounting 7 = 1. Under the above definition of the reward, the value is equal to the success probability of π on the task, i.e. the absorption probability of the stochastic process starting in so defined by running Tsa:
1T (so: So0 (cm) = P(s E Teu (cM),
As we will observe in Section 5 in practice both the low-level policy and value can be learned. Approximat- ing the value oracle with learned value function was sufficient for DC-MCTS to plan successfully.
2

---

Under review as a conference paper at ICLR 2021
where Th is the trajectory generated by running T. from state su To keep the notation compact, we will omit the explicit dependence on C. and abbreviate tasks with pairs of states in S x S.
2.1 PLANNING OVER SUB-GOAL SEQUENCES
Assume a given goal-directed policy म, which we also refer to as the low-level policy. If I is not already optimal, we can potentially improve it by planning: If π has a low probability of directly reaching Seo from the initial state 80. i.e. v" (80, $oo) Rs O we will try to find a plan consisting of sequence of intermediate sub-goals such that they guide и from the start 8g to the goal state Sec.
Concretely, let S* = - St be the set of sequences over S, and let lor be the length of a sequence S*. We define for convenience S = S (Ø), where @ is the empty sequence representing no sub-goal. We refer to a as plan for task (so, 3 ) if 0j = and a a| Soo, i.c. if the first and last elements of a are equal to 50 and soc, respectively. S0S* S:o denotes the set of plans for this task.
To execute a plan a, we construct a policy Ta by conditioning the low-level policy и on each of the sub-goals in order: Starting with n 1, we feed sub-goal xx+1 to n, i.e we run To if xx+1 is reached, we will execute To Kan4z and so on. We now wish to do open-loop plamning, i.e. find the plan with the highest success probability P(* TTT of reaching & However, this success probability depends on the transition kernels of the underlying MDPs, which might not be known. We can instead define planning as maximizing the following lower bound of the success probability, that can be expressed in terms of the low-level value v".
Proposition 1 (Lower bound of success probability). The success probability P(s E ) N L(o) of a plan a is bounded from below by L(ar) == I1 (o., i.e. the product of the success probabilities of π on the sub-tasks defined by (1+1)
The straight-forward proof is given in Appendix A.I Intuitively, L(a) is a lower bound for the success of To. as neglects the probability of "aceidentally" (due to stochasticity of the policy or transitions) running into the goal Soc before having executed the full plan. We summarize:
Definition 1 -Open-Loop Goal-Directed Planning). Given a goal gore-directed policy тт and its corre- sponding value oracle v", we define planning as maximizing L(a) over E &syS* sec. i.e. the set of plans for task (sp, )cc). We define the high-level (HL) value v" (Su, Sxc) == -max, L(r) as the maximum value of the planning objective.
Note the difference between the low-level value nx and the high-level e². v= (s, is the probability of the agent directly reaching s' from s following æ,, whereas v" (sss s') the probability reaching s' from under the optimal plan, which likely includes intermediate sub-goals. In particular, v² 2 v".
2.2 AND/OR SEARCH TREE REPRESENTATION
In the following we cast the planning problem into a representation amenable to efficient search. To this end, we use the natural compositionality of plans: We can concatenate a plan a for the task (s, s and plan ē for the task (s',"") into plan a ā for the task se). Conversely, we can decompose any given plan a for task (so, Sco) by splitting it at any sub-goal s E a into o = of o o", where of is the "left" sub-plan for task (so, s), and o" is the "right" sub-plan for task (s, s Trivially, the planning objective and the optimal high-level value factorize wrt. to this decomposition:
L(o' o o00) = L(o')((o") v" u"(so, 920)
max v'(so, 8) v" (8, sES
This allows us to recursively reformulate planning as:
arg max Argg)xx(o')) (
arg arg max L(07)) TT,EAS 500
arg max #ES
(1)
The above equations are the Bellman equations and the Bellman optimality equations for the classical single pair shortest path problem in graphs, where edge weights are given by - loog v" (s, s'). We can represent this planning problem by an AND/OR search tree (Nilsson, N. J. 1980) with alternating levels of OR and AND nodes. An OR node, also termed an action node, is labeled by a task
We assume MDPs with multiple absorbing states such that this probability is not trivially equal to for most policies, e.g. uniform policy. In experiments, we used a finite episode length.
3

---

Under review as a conference paper at ICLR 2021
ss) E ES> x S; the root of the search tree is an OR node labeled by the original task (su, S A terminal OR node (s.s") has a value v (s, s") attached to it, which reflects the success probability of π., for completing the sub-task (s, s"). Each non-terminal OR node has S] + 1 AND nodes as children. Each of these is labeled by a triple (s, ,")) for s' E S, which correspond to inserting a sub-goal s' into the overall plan, not inserting one in case of 8 Ø. Every AND node (s, ,"", or conjunction node, has two OR children, the "left" sub-task (s, s') and the "right" sub-task s").
In this representation, plans are induced by solution trees. A solution tree Ta is sub-tree of the complete ANDIOR search tree, with the properties that (i) the root (50, 8x0) E Ta, (ii) each OR node in T has at most one child in To and (iii) each AND node in To as two children in T. The plan and its objective L(a) can be computed from To by depth-first first traversal of To. The correspondence of sub-trees to plans is many-to-one, as Ta. in addition to the plan itself, contains the order in which the plan was constructed. Figure 6 in Section 5.3 shows an example for search and solution tree. Below we will discuss how to construct a favourable search order heuristic.
BEST-FIRST AND/OR PLANNING
The planning problem from Definition 1 can be solved exactly by formulating as shortest path problem from So to Soo on fully connected graph with vertex set with non-negative edge weights given by log vn and applying classical Sin- gle Source or All Pairs Shortest Path (SSSP) / APSP) planner. This approach is appropriate if one wants to solve all goal-directed tasks in a sin- gle MDP. Here, focus however the multi- task setting described above, where the agent is given new MDP with single task (so: 8 every episode. In this case, solving the SSSP/ APSP prob- lem is not feasible: Tabulating all graphs weights
Algorithm 1 Divide-and- MCTS
Global low-lovel value oracle
Global high level value function
Global policy prior
Global search tree T
procedure TRAVERSE(OR node (s, If (x. 6") g T then T < EXPAND(TT (e. (x..(".""))))) d²))
2:
3:
4:
return max( (1" (s,s"), "(s,s"))
b hootstrap
5:
s SELECT(s, e"))
b. OR node
6
if a = 2 or max-depth reached then
G v" (e, 8")
8:
else
D. AND node
9:
Gin + TRAVERSE(s, s')
10:
Griche +- TRAVERSE(S' 2"))
- -log (s, s') would require | evaluations of vn (s, 8') for all pairs (8, 5"). In practice, approxi- mate evaluations of v" could be implemented by e.g. actually running the policy π, or by calls to powerful function approximator, both of which are often too costly to exhaustively evaluate for large state-spaces S. Instead, we tailor an algorithm for approximate planning to the multi-task setting, which we call Divide-and-Conee DC-MCTS critically makes use of two learned search heuristics that transfer knowledge from previ- ously encountered MDPs / tasks to new problem instance: (i) a distribution p(s'|s, (s, s"), called the policy prior, for proposing promising intermediate sub-goals s' for task (s, s,); and (ii) a learned approximation e to the high-level value v" for bootstrap evaluation of partial plans. In the following we present DC-MCTS and discuss design choices and training for the two search heuristics.
11:
N BACKUP
12:
G Giatt Gright
13:
threshold the return
14:
#/ UPDATT
15:
V(a, t- ("(s,"")N(ss (aaas""GGG((NN G)((Ns,=""H))
N(s,8") + N(s,"")+1 +1
17: return G
MCTS (DC-MCTS). To evaluate v" as sparsely as possible,
3.1 DIVIDE-AND-CONQUUS MONTE CARLO TREE SEARCH
The input to the DC-MCTS planner is an MDP encoding CM. a task (s0: 800) as well as planning budget. i.c. a maximum number B e N of nM oracle evaluations. At each stage, DC-MCTS maintains a (partial) AND/OR search tree T whose root is the OR node (So. soo) corresponding to the original task. Every OR node (s, s") E 'T maintains an estimate V(s, s") R 8² (s, 8") of its high-level value. DC-MCTS searches for plan by iteratively constructing the search tree T with TRAVERSE until the budget is exhausted, see Algorithm] [ During each traversal, if a leaf node of T is reached, is expanded, followed by a recursive bottom-up backup to update the value estimates V of all OR nodes visited in this traversal. After this search phase, the currently best plan is extracted from T by EXTRACTPLAN (essentially depth-first traversal, see Algorithm in the Appendix). In the following we briefly describe the main methods of the search. We illustrate DC-MCTS in Figure I
TRAVERSE and SELECT T is traversed from the root (So, $oo) to find promising node to expand. At an OR node (s, s"), SELECT chooses one of its children s' E S to traverse into, including s = 2 for not inserting any further sub-goals into this branch. We implemented SELECT by the pUCT
4

---

Under review as a conference paper at ICLR 2021
Rosin
2011 rule, which consists of picking the next node s' E S based maximizing the following
score:
s"s,s"
Vss,s)) - ( s") c cc-p(sssss"") 1+ N(s, 8' s'8)"
(2)
where (ss, s'), (Ns, s"") are the visit counts of the OR node (s, s'), AND node (s, s', s")s respec- tively. The first term is the exploitation component, guiding the search to sub-goals that currently look promising, i.e. have high estimated value. The second term the exploration term favoring nodes with low visit counts. Crucially, it is explicitly scaled by the policy prior p(s' (s, s.) to guide exploration. At an AND node (s, s"), TRAVERSE traverses into both the left (s, 8') and right child (s', s") " As the two sub sub-problems
solved independently. computation from there can be carried out in parallel. All nodes visited in a single traversal form a solution tree To with plan ø.
EXPAND If a leaf OR node (8,8") is reached during the traversal and its depth is smaller than a given maximum depth, it expanded by evaluating the high- and low-level values v(8, ((),s"), v (s, The initial value of the node is defined as max of both values, as by definition v* 2 v", i.c. further planning should only increase the success probability on sub-task. We also evaluate the policy prior p(s'ls, (s, s") ") for all s', yielding the proposal distribution over sub-goals used in SELECT. Each node expansion costs one unit of budget B.
BACKUP and UPDATE We define the return G2 of the traversal tree To as follows. Let refinement Ta of To be solution tree such that To C T thus representing plan ot that has all sub-goals of a with additional inserted sub-goals. G₂ is now defined as the value of the objective L(a+) )) of the optimal refinement of Ta, i.e. it reflects how well one could do on task (80.8% by starting from the plan a and refining it. It can be computed by a simple back-up on the tree To that uses the bootstrap value v v² the leafs. As v² (s0, 2 G. Z L(rr) and Go- v² (so, 850) for the optimal plan o², we can use G. to update the value estimate V. Like in other MCTS variants, we employ a running average operation (line 15-16 in TRAVERSE).
3.2 DESIGNING AND TRAINING SEARCH HEURISTICS
Search results and experience from previous tasks can improve DC-MCTS on new problems via adapting the search heuristics, i.e. the policy prior p and the approximate value function v as follows.
Bootstrap Value Function We parametrize v(s, s' s'(cM) Re v" (s, s'(cm) as a neural network that takes as inputs the current task consisting of (s, s') and the MDP encoding cM- A straight-forward approach to train v is to regress it towards the non- non-parametric value estimates V computed by DC- MCTS on previous problem instances. However, initial results indicated that this leads to being overly optimistic, an observation also made in Kaelbling (1993). We therefore used more conservative training targets, that are computed by backing the low-level values ox up the solution tree To of the plan a return by DC-MCTS. Details can be found in Appendix B.T
Best- first search guided by policy prior p can be understood as policy improvement of p as described in (Silver et al. (2016). Therefore, a dtraight-forwan way of training p is to distill the search results back into into the policy prior, e.g. by behavioral cloning. When applying this to DC-MCTS in our setting, we found empirically that this yielded very slow improvement when starting from an untrained, uniform prior p. This is due to plans with non-zero success probability L > 0 being very sparse in St, equivalent to the sparse reward setting in regular MDPs To address this issue, we propose to apply Hindsight Experience Replay (HER, Andrychowicc et al. (017)) Instead of training p exclusively on search results, we additionally execute plans o in the environment and collect the resulting trajectories, i.e. the sequence of visited states, T (So, $1 .1..... ST). HER then proceeds with hindsight relabeling, i.e. taking The as an approximately optimal plan for the "fictional" task (so; ST) that is likely different from the actual task (8p, 8. In standard HER, these fictitious expert demonstrations are used for imitation learning of goal goal-directed policies, thereby cireumventing the sparse reward problem. We can apply HER to train p in our setting by extracting any ordered triplet (St,, St,; St,) from -h and use it as supervised learning targets for p. This is a sensible procedure, as p would then learn to predict optimal sub-goals st for sub-tasks (s", 8% under the assumption that the data was generated by oracle producing optimal plans T o² We have considerable freedom choosing which triplets to extract from data and use as supervision with HER. In our experiments we use a temporally bulanced parsing, which creates triplets (s,, 81+2/2, 81+2)
Policy Prior
It is possible to traverse into single node at the time, we descrihe several heuristics in Appendix A.3
5

---

Under review as a conference paper at ICLR 2021
such that the resulting policy prior should then preferentially propose sub-goals "in the middle" of the task. In Appendix A.4 we discuss this aspect in more detail, and present alternative parsers.
3.3 ALGORITHMIC COMPLEXITY OF DC-MCTS
Denoting an optimal plan as o². the complexity of DC-MCTS with optimal search policy prior S)). This could potentially be reduced ([lg([o**) when using progressive widening Coulom (2007); Chaslot et al. for fewer evaluations of and perfect parallelization of tree traversals across multiple workers; for details see Appendix A.5
p ==p -
4 RELATED WORK
Goal-directed multi-task learning is an important special case of general RL and has been extensively studied. Universal value functions (Schaul et al. (015)) have been established as compact representa-
tion for this setting (Kulkarni et | [016 Andrychowicz et al. 2017 Ghosh et al.] 2018 Dhiman (et al. 2018). This allows to use sub-goals as means for planning, as done in several works such as Kaelbling & Lozano-Péree (2017); Gao al. (2017); (Savinov al. (2018); [Stein et al. (20T8); Nasiriany et af. (2019). all of which rely on forward sequential planning. Gabor et al. (2019) use MCTS for traditional sequential planning based on heuristies, sub-goals and macro-actions. Zhang et al. (2018) apply traditional graph planners to find abstract sub-goal sequences. We extend this line of work by showing that the abstraction of sub-goals affords more general search strategies than sequential planning. Work concurrent to ours has independently investigated sequeniall sub-goals planning: Jurgenson et al. (2019) propose a top-down policy gradient approach that learns to predict sub-goals in a hierarchical way. Nasiriany et al. (2019) propose gradient-base search jointly over a fixed number of sub-goals for continuous goal spaces. In contrast, DC-MCTS is able to dynamically determine the complexity of the optimal plan.
The proposed DC-MCTS planner is a MCTS (Browne et al. 2012) variant, inspired by recent advances in best-first or guided search, such as AlphaZero (Silver et al. 2018). It can also be understood as heuristic, guided version of the classic Floyd- Warshall algonthmm which exhaustively computes all shortest paths. In the special case of planar graphs, small sub-goal sets, also known as vertex separators, can be constructed that favourably partition the remaining graph, leading to linear time ASAP algorithms (Henzinger et al. T997). The heuristic sub-goal proposer p that guides DC-MCTS can be loosely understood as a probabilistic version of vertex separator, Nowak- Vila al. (016)) also consider neural networks that mimic andeoquud algorithms similar the sub-goal proposals used here. However, while we do policy improvement for the proposals using search and HER, the networks in Nowak Vila al.] (2016) are purely trained by policy gradient methods.
Decomposing tasks into sub-problems has been formalized as pseudo trees (Freuder Quinn 1985 and AND/OR graphs (Nilsson, N. J. 1980). The latter have been used especially in the context of optimization (aarrosa et 20.2 Jégou & Terrioux [2003 Dechter Mateescu 2004: Marinescu
Dechter 2004). Our approach is related to work on using AND/OR trees for sub-gou tob-goal ordering in the context of logic inference (Ledeniov & Markovitch 1998). While DC-MCTS is closely related to the AO algorithm (Nilsson, N. 19800, which the generalization of the heuristic A search to AND/OR search graphs. interesting differences exist: AO" assumes a fixed search heuristic, which is required be lower bound the cost-to-go. In contrast, we employ learned value functions and policy priors that are not required to be exact bounds. Relaxing this assumption, thereby violating the principle of "optimism in the face of uncertainty". necessitates explicit exploration incentives in the SELECT method. Alternatives for searching AND/OR spaces include nrombrr search, recently applied chemical synthesis planning (Kishimoto et al. 2019). Very recent work concurrent to ours has focused on relevant research directions: Wang et al. (2020) introduce LA-MCTS as 'meta-ala algorrthh for black-box optimization, and Chen et al. (2020) propose Retro", neural-based A *-liee algorithm for molecule synthesis that is also based on AND/OR trees.
EXPERIMENTS
We evaluate the proposed DC-MCTS algorithm on navigation in wrid-world mazes as well as on a challenging continuous control version of the same problem, comparing it to standard sequential MCTS (in sub-goal space) based on the fraction of "solved" mazes by executing their plans. The MCTS baseline was implemented by restricting the DC-MCTS algorithm to only expand the "right"

---

Under review as a conference paper at ICLR 2021
Legend:
sp/start
wall
empty
pls" 18,8s)
sub-goals
Figure 2: Left: Two grid-world maze examples for wall density d = 0.75 and 0.95. In light blue, the distribution over sub-goals induced by the policy prior p that guides the DC-MCTS planner. Right group: The first sub-goal, i.. at depth the solution tree, approximately splits problem half. Next, two sub-goals at depth 1. Last, the final plan with the depth of each sub-goal shown. See supplementary material for full animations.
sub- sub-problem in line 10 of Algorithm [ the value Glett for the "left" sub-problem is computed in line 7, i.c. using the low-level value v² This forces MCTS to plan forward and sequentially, as each next step needs be reachable from the previous state, as evaluated v All remaining parameters and design choice were the same for both planners except where explicitly mentioned otherwise.
5.1 GRID-
GRID-WORLDD WORLD MAZES
Each task consists of new, procedurally generated maze 21 21 grid with start and goal locations (8p, $oc) E (1...., 21}2 2 see Figure Task difficulty was controlled by the density of walls d (under connectedness constraint), where the easiest setting d 0.0 corresponds and the most difficult one d 1.0 implies so-called perfect or singly-connected mazes. The task embedding сM was given as the maze layout and (so, 860) encoded together 21 categorical variables with categories each (empty, wall, start and goal location). The underlying MDPs have primitive actions: up. down, left, right and NOOP For sake of simplicity, we first tested
walls
feature map of 21 x
our proposed approach by hard-coding a low-level policy T as well as its value oracle == in the following way. If in state and conditioned on goal s', and if is adjacent s', TQ successfully reaches with probability in one step, i.e. y (s, s') 1; otherwise y (s, s') = 0. If xD. is nevertheless executed, the agent moves to random empty tile adjacent to s. Therefore, x0 is the "most myopic" goal-directed policy that can still navigate everywhere.
For each maze, MCTS and DC-MCTS were given search budget of 200 calls to the low-level value oracle T We implemented the search heuristics, i.e. policy prior and high-level value function v, as convolutional neural networks (CNNs) which operate on input CMi details for the network architectures are given in Appendix
B.3 With untrained networks, both planners were unable to solve the task (<2% success probability), shown in Figure 3 This illustrates that a search budget of 200 evaluations of oT is insufficient for unguided planners find a feasible path in most mazes. This is consistent with standard exhaustive SSSP APSP graph planners requiring 21 > 10a > 200 evaluations for optimal planning in the worst
these tasks.
Next, we trained both search heuristics v and as detailed in Section 3.2
In particular, the sub-goal
proposal p was also trained on hindsight-relabeled experience data, where for DC-MCTS used the temporally balanced parser and for MCTS the corresponding left-fire first parser (see Appendix (A.4). Training of the heuristics greatly improved the performance of both planners. 3 learning
7

---

Under review as a conference paper at ICLR 2021
curves for mazes with wall density d 0.75, mean and std over 20 different hyperparameters. DC-MCTS exhibits substantially improved performance compared to MCTS, and when compared at equal performance levels, DC-MCTS requires 5 to 10-times fewer training episodes than MCTS. An example of a learned sub-goal proposal for DC-MCTS is visualized in F (further examples given in the Appendix in Figure R). Probability mass concentrates promising sub-goals that are far from both start and goal, approximately partitioning the task into equally hard sub-tasks.
Next, we investigated the performance of both MCTS and DC-MCTS in challenging continuous control environments with non-trivial low-level policies. We embedded the grid- world mazes into a physical 3D environment simulated by MuJoCo Todorov MuJoCoTTodoro et al. 2012), rendering each grid- rridwwordd cell as 4m cell in physical space. The agent is embodied by a quadruped "ant" body; for illustration see Figure 4 For the low-level policy n"' we pre-trained goal-directed neural network controller that gets as inputs proprioceptive features (e.g. some joint angles and velocities) of the ant body well as a 3D-vector pointing from its current position to a target
1.0
0.8-
0.6
0.44
0.2-
DC-MCTS
MCTS
0.0
0.0
0.2
0.4
0.6
0.8
1.
training epsisodes
1e5
Figure 3: Grid-world mazes.
position. T was trained to navigate to targets randomly placed less than 1.5 away in open
area (no walls), using MPO (Abdolmaleki et al. 2018). See Appendix [.44 for more details. If unobstructed, x/h can walk straight line towards its current goal. However, this policy receives no visual input and thus can only avoid walls when guided with appropriate sub-goals. To establish an interface between the low-level TH and the planners, we used another CNN to approximate the low-level value oracle v" (so. 800 IcM): It was trained to predict whether nrh will succeed in solving the navigation tasks (sq. S,0), CM- Its input the corresponding discrete grid-world representation CM of the maze (21 x 21 feature map of categoricals as described above, details in Appendix). Note that this setting is still challenging: In initial experiments we verified that a model-free baseline (also based on MPO, without HER) with access to state abstraction and low-level controller, only solved about 10% of the mazes after 100 million episodes due to the extremely sparse rewards.
5.2 CONTINUOUS CONTROL MAZES
We applied MCTS and DC-MCTS to this problem to find symbolic plans consisting of sub-goals in {1....,21}? 2112. The high-level heuristics and were trained for 65k episodes, exactly as in Section 5.1 except using "== instead of u.. We again observed that MCCS outperforms by wide mar- gin the MCTS planner: Figure 5 shows performance of both (with fully trained search heuristics) as a function of the search budget for the most difficult mazes with wall density d = 1.0. Performance of DC-MCTS with the MuJoCo low-level con- troller was comparable that with the hard-coded low-level policy from the grid-world experiment (with same wall density), showing that the abstraction planning over low-level sub-goals successfully isolates high-level planning from low-level execu- tion. We did not manage successfully train the MCTS planner on MuJoCo navigation.
Figure 4: The 'ant', i.c. the agent, should navigate to the green target.
DC-MCTS
This was likely due to HER, which we found in ablation studies- - essential for training DC-MCTS on both settings and MCTS on the grid-world problem, but not appropriate for MCTS on MuloCo navigation: Left-first parsing for HER consistently biased the MCTS search prior p to propose next sub-goals too close to the previous sub-goal. This lead the MCTS planner to "micro-mer "micro-manage" the low-level policy, in particular long corridors that x" can solve by itself. DC-MCTS, by recursively partitioning, found an appropriate length scale of sub-goals, leading to drastically improved performance.
0.4
MCTS
solveed
0.3
0.2
0.1
0.5
1.0
1.5
2.0
l0 Search budget
Figure 5: Fraction of solved mazes vs. planning budget.
8

---

Under review as a conference paper at ICLR 2021
5.3 VISUALIZING MCTS AND DC-MCTS
To further illustrate the difference between DC-MCTS and MCTS planning we can look at an example search tree from each method in Figure 6 Light blue nodes part of the final plan: note how in the case of DC-MCTS, the plan is distributed across a sub-tree within the search tree, while for the standard MCTS the plan is a chain. The first "actionable' sub-goal, i.c. the first sub-goal for the low-level policy, is the left-most leaf in DC-MCTS and the first dark node from the root for MCTS.
Divide-and-Conqueer MCTS
Figure 6: Only colored nodes are part of the final plan: sub-tree for DC-MCTS, chain for MCTS.
6 DISCUSSION
To enable guided, divide-and-conee con-ucr style planning, made a few strong assumptions. Sub-goat based planning requires a universal value function oracle of the low-level policy, which often will have to be approximated from data. Overly optimistic approximations can be exploited by the planner, leading to "delusional" plans (Little & Thiébaux, 2007). Joint learning of the high and low-level components can potentially address this issue. In sub-goal planning, at least in its current naive implementation, the "action space" for the planner is the whole state space of the underlying MDPs. Therefore, the search space will have a large branching factor in large state spaces. A solution to this problem likely lies in using learned state abstractions for sub-goal specifications, which is fundamental open research questions. We also implicitly assumed that low-level skills afforded by the low-level policy need to be "universal", i.e. if there are states that it cannot reach, amount of high level search will lead to successful planning outcomes.
In spite of these assumptions and open challenges, we showed that non-sequential sub- goal planning has fundamental advantages over the standard approach search over primitive actions: (i) Abstrac- tion and dynamic allocation: Sub-goals automatically support temporal abstraction as the high-level planner does not need to specify the exact time horizon required to achieve a sub-goal. Plans are generated from coarse to fine, and additional planning is dynamically allocated to those parts of the plan that require more compute. (ii) Closed & open-loop: The approach combines advantages of both open- and closed loop planning: The closed-loop low-level policies can recover from failures or unexpected transitions in stochastic environments, while at the same time the high-level planner can avoid costly closed-loop planning. (iii) Long horizon credit assignment: Sub-goal abstractions open new algorithmic possibilities for planning as exemplified by DC-MCTS - that can facilitate credit assignment and therefore reduce planning complexity. (iv) Parallelization: Like other divide-and and-anndnnnn coonuuen algorithms, DC-MCTS lends itself to parallel execution by leveraging problem decomposition made explicit by the independence of the "left" and "right" sub- nub-problems of an AND node. (v) Reuse of cuched search: DC-MCTS is highly amenable to transposition tables, by caching and reusing values for sub-problems solved other branches of the search tree. (vi) Generality: DC-MCTS is strictly more general than both forward and backward goal- goal-directed planning, both of which can be seen as special cases.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Abbas Abdolmalcki, Jost Tobias Springenberg. Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum a posteriori policy optimisation. In International Conference on Learning Representations, 2018.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight Experience Replay. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 5048 5058..508.600 2017.
Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995.
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions Computational Intelligence and Al in games, 4(1): 43, 2012.
GMJB Chaslot, Mark Winands, and Bruno Bouzy Progressive strategies for monte-carlo tree search. In Proceedings of the 10th Joint Conference on Information Sciences (JCIS 2007).
Binghong Chen, Chengtao Li, Hanjun Dai, and Le Song. Retro": Learning retrosynthetic planning with neural guided a* search. In The 37th International Conference on Machine Learning (ICML 2020), 2020.
Rémi Coulom. Computing "clo ratings" of move patterns in the game of go. ICGA journal, 30(4): 198-208, 2007.
Peter Dayan and Geoffrey E Hinton. Feudal reinforcement learning. In Advances in neural information processing systems, pp. 271-278, 1993.
leamiin
Rina Dechter and Robert Mateescu. Mixtures of cetemmnistic-probablliii networks and their AND/OR search space. In Proceedings of the 20th conference on Uncertainty in artificial intelli- gence, pp. 120-129. AUAI Press, 2004.
Vikas Dhiman, Shurjo Banerjee, Jeffrey Siskind, and Jason J Corso. Hlydd-Washan Reinforcement Learning Learning from Past Experiences to Reach New Goals. arXiv preprint arXiv: /8X9.0/80 2018.
Eugene C Freuder and Michael J Quinn. Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems. In IJCAI, volume 85, pp. 1076-1078. Citeseer, 1985.
Thomas Gabor, Jan Peter, Thomy Phan, Christian Meyer, and Claudia I. Linhoff--Popiet Subgoal- based temporal abstraction in Monte-Carlo tree search. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 5562-5568. AAAI Press, 2019.
Wei Gao, David Hsu, Wee Sun Lee, Shengmei Shen, and Karthikk Subramanian. Intention-nee -ett: Integrating planning and deep learning for goal-directed autonomous navigation. arXiv preprins 17Xiv:1710.05627, 2017.
Dibya Ghosh, Abhishck Gupta, and Sergey Levine. Learning Actionable Representations with Goal-Conditionel Policies. arXiv preprint arXiv:1811.07819. 2018.
Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzaler Tobias Pfaff, Theophane Weber, Lars Buesing, and Peter W Battaglia. Combining Q-l.earning and Search with Amortized Value Estimates. ICLR, 2020.
Monika R Henzinger, Philip Klein, Satish Rao, and Sairam Subramanian. Faster shortest-pate algorithms for planar graphs. journal of computer and system sciences. 55(1):3-33, 1997.
Philippe Jégou and Cyril Terrioux. Hybrid backtracking bounded by tree-decomposstion of constraint networks. Artificial Intelligence, 146(1):43-75, 2003.
10

---

Under review as a conference paper at ICLR 2021
Tom Jurgenson, Edward Groshev, and Aviv Tamar. Sub-Goal Trees Framework for Goal-Directed Trajectory Prediction and Optimization. arXiv preprint arXiv:1906005329. 2019.
Leslie Pack Kaelbling. Learning to achieve goals. In IJAI, pp. 1094-1099. Citeseer, 1993.
Leslie Pack Kaelbling and Tomás Lozano-Pérez, Learning composable models of parameterized skills. In 2017 IEEE International Conference Robotics and Automation (ICRA), pp. 886-893.
IEEE, 2017.
Akihiro Kishimoto, Beat Buesser, Bei Chen, and Adi Botea. Depth-First Proof-Number Search with Heuristic Edge Cost and Application to Chemical Synthesis Planning. In Advances in Neural Information Processing Systems, pp. 7224-7234, 2019.
Tejas Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation. In Advances in Neural Information Processing Systems 29, pp. 3675-368 Curran Associates, Inc., 2016.
Javier Larrosa, Pedro Meseguer, and Marti Sánchez. Pseudo-tree search with soft constraints. In ECAL, pp. 131-135, 2002.
Oleg Ledeniov and Shaul Markovitch. The divide-and-conque subgoal-ordering algorithm for speeding up logic inference. Journal of Artificial Intelligence Research, 9:37-97, 1998.
lain Little and Sylvie Thićbaux. Probabilistic planning vs. replanning. In ICAPS Workshop on IPC: Past, Present and Future. Citeseer, 2007.
Radu Marinescu and Rina Dechter. ANDIOR tree search for constraint optimization. In Proc. of the 6th International Workshop on Preferences and Soft Constraints. Citeseer, 2004.
Josh Merel, Arun Ahuja, Vu Pham, Saran Tunyasuvunakool, Siqi Liu, Dhruva Tirumala, Nico- las Heess, and Greg Wayne. Hierarchical visuomotor control of humanoids. In International Conference on Learning Representations, 2019.
Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with Goal-Conditioned Policies. In Advances in Neural Information Processing Systems, pp. 14814-14825, 2019.
Nilsson, N. J. Principles of Artificial Intelligence. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1980. ISBN 0-934613-10-9,
Alex Nowak-Villa David Folqué, and Joan Bruna. Divide and Conquer Networks. arXiv preprint arXiv:1611.024011 2016.
Christopher D Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 2133):203-330, 2011.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametric topological memory for navigation. arXiv preprint arXiv::8033 00653, 2018.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International Conference on Machine Learning, pp. 1312-1320, 2015.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwiesser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game Go with deep neural networks and tree search. nature, 529(7587):484, 2016.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play Science, 362(6419) 2018. ISSN 8036-8075 doi: 10. 22111//////nn...oo aar6440 URL htttp::/sccienceeeeeseee www.:neee...iiinnnnceence org/ azgg/cooteee//222 http:////o..aaaaoooo///////////a
641 9//140/1000
Gregory J Stein, Christopher Bradley, and Nicholas Roy. Learning over Subgoals for Efficient Navigation of Structured, Unknown Environments, In Conference on Robot Learning, pp. 213- 222, 2018.
11

---

Under review as a conference paper at ICLR 2021
Richard S Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181-211 1999.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 TEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, IEEE, 2012.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volune 70, pp. 3540-3549. JMLR. org, 2017.
Linnan Wang, Rodrigo Fonseca, and Yuandong Tian. Learning search space partition for black-box optimization using monte carlo tree search. NeurIPS, 2020.
Amy Zhang, Adam Lerer, Sainbayar Sukhbaatar, Rob Fergus, and Arthur Szlam. Composable planning with attributes. arXiv preprint 10X:::8833000122 2018.
12

---

Under review as a conference paper at ICLR 2021
A ADDITIONAL DETAILS FOR DC-MCTS
A.1 PROOF OF PROPOSITION
Proof. The performance of No on the task (so, Soo) is defined the probability that its trajectory The from initial state 50 gets absorbed in the state Soc. i.. P( E Tag ). We can bound the latter
from below in the following way. Let a (m)) with dg Su and om Scc With
(Ao...., 02) S Th
we denote the event that visits all states do. ........ in order:
P( oi) C 50
(Aoov P=1
Nov lov E ) A (1r-1 <)))
where tę is the arrival time of To at oi and we define to = O. Obviously, the event (oo, (oo...., Fm) S Th is subset of the event 8oa Th and therefore
P( am) E TTe S P(s E -xt
(3)
Using the chain rule of probability we can write the Ihs as:
P((oo.... am
[IP((1r E T A (ti-1 < <4i (o.....,..-i) S =%
sg
s=1
We now use the definition of no: After reaching di-1 and before reaching ds Ta is defined by just executing To, starting from the state 0=-1:
Pl( 0m) S To
II P E Joi (000 .... oi-i) S CT T i=1
now make use of the fact that the o, E are states of the underlying MDP that make the future independent from the past: Having reached 0;-1 at 4i-1, all events from there on (e.g. reaching oj for j 2 i) are independent from all event before 4-1- We can therefore write:
P((oo....,,00 S T = II
(a. E Top
1=1 m
II 0r (ai-1,
(4)
Putting together equation and equation 4 yields the proposition.
A.2 ADDITIONAL ALGORITHMIC DETAILS
After the search phase, in which DC-MCTS builds the search tree T, it returns estimate of the best plan o" and the corresponding lower bound T(@*) by calling the EXTRACTPLAN procedure on the root node (so. s. Algorithm gives details on this procedure.
A.3 DESCENDING INTO ONE NODE AT THE TIME DURING SEARCH
Instead of descending into both nodes during the TRAVERSE step of Algorithm I is possible to choose only one the two sub-problems to expand further. This can be especially useful if parallel
Forward planning is equissient ling only the right
Backward planning equivsient espanciing only sub-problam
Divide Conquer middle back
HF
Figure 7: Divide and Conquer Tree Search is strictly more general than both forward and backward search.
13

---

Under review as a conference paper at ICLR 2021
Algorithm 2 additional Divide-And-Cond MCTS procedures
Global low-level value oracle o²
Global high-level value function v
Global policy prior p Global search tree
1: procedure EXTRACTPLAN(OR node (s, ))
8' arg max; V(8, 8) ((š,
D choose best sub-goal Dr no more splitting
if 8 = then
return Ø U² (s,
else
T1. G. f EXTRACTPLAN(S.5) Tr, G. t EXTRACTPLAN(S,
extract "left" sub-plan > extract "right" sub-plan
return of or, Gi G,
computation is not an option, or if there are specific needs e.g. illustrated by the following three heuristics. These can be used to decide when to traverse into the left sub-problem (s, s') or the right sub- bub-problem (s', s"). Note that both nodes have a corresponding current estimate for their value V, coming either from the bootstrap evaluation of e or further refined from previous traversals.
Preferentially descend into the left node encourages more accurate evaluation of the near future, which is more relevant to the current choices of the agent. This makes sense when the right node can be further examined later, or there is uncertainty about the future that makes it sub-optimal to design a detailed plan at the moment.
Preferentially descend into the node with lower value, following the principle that a chain (plan) only as good as its weakest link (sub-problem). This heuristic effectively greedily optimizes for the overall value of the plan.
Use 2-way UCT on the values of the nodes, which acts similarly to the previous greedy heuristic, but also takes into account the confidence over the value estimates given by the visit counts.
The rest of the algorithm can remain unchanged, and during the BACKUP phase the current value estimate V of the sibling sub-problem can be used.
A.4 PARSERS FOR HINDSIGHT EXPERIENCE REPLAY
Given task (5o, ). the policy prior p defines distribution over binary partition trees of the task via recursive application (until the terminal symbol & closes branch). A sample To from this distribution implies plan described above; but furthermore also contains the order in which the task was partitioned. Therefore, p not only implies a distribution over plans, but also search order: Trees with high probability under p will be discovered earlier in the search with DC-MCTS. For generating training targets for supervised training of p, we need to parse given sequence The (su, ....... ST) into binary tree. Therefore, when applying HER we are free to choose any deterministic or probabilistic parser that generates solution tree T, from re-labeled HER data = As mentioned in the main text, the particular choice of HER-parser will shape the search strategy defined by p. Possible choices for the parsers include:
1. Left-first parsing creates triplets (st, S1+1, S.). The resulting policy prior will then prefer- entially propose sub-goals close to the start state, mimicking standard forward planning. Analogously right-first parsing results in approximate backward planning:
2. Temporally balanced parsing creates triplets (st, S $142). The resulting policy prior will then preferentially propose sub-goals "in the middle" of the task. This is the one we used in our experiments:
3. Weight-balanced parsing creates triplets ss, such that v(s, s') v(s's." or o (s, s') se oF (s''s"" The resulting policy prior will attempt to propose sub-goals such that the resulting sub-tasks are equally difficult.
14

---

Under review as a conference paper at ICLR 2021
A.5 DETAILS ON ALGORIHTIIC COMPLEXITY
Let C.r denote the cost of evaluating the low-level value e" any sub sub-problem (s, We assume Cy" to be independent of (s, s') which holds if e.g. o" is a fixed size neural network. Denote the cost of evaluating the policy prior p on a sub-goal (s,s', with cp. Expanding new OR node in the search tree incurs a cost of c for evaluating p for all children. Assuming the computational cost of tree traversals is negligible, the total cost of running DC-MCTS for N node expansions is thus .N- - (|S]c,, + 2c,-), ). The number of expansions to find the optimal (or a sufficiently good) plan strongly depends on the quality of the policy prior (similar A" search), making an analysis of the complexity of DC-MCTS challenging for arbitrary p. However, if p' is the optimal policy prior- i.e. p" (s' s, s") 1 if E O² in the optimal plan a* for s")) and 0 otherwise DC-MCTS will construct o² in the minimal number of step N = |o- therefore incurring cost of |o" + 2e,=). ). The dependency on |S] for the policy prior can be further reduced in principle down to a constant using techniques from the literature on MCTS for continuous or large discrete action spaces (c.g. progressive widening Coulom (2007); Chaslot et al.). We can compare this to the cost of unguided, standard SSSP planners, which is |87=c low-level value function for all pairs of states (s, s.). Therefore, DC-MCTS can be significantly more cost efficient than conventional SSSP planners if a good policy prior can be learned and the cost of evaluating Cp 2 Cpp is at least comparable to that of evaluating v". Under the assumption p p", MCTS and DC-MCTS have the same sample complexity. However MCTS represents the solution as one path of length |o"| in the search tree, whereas DC-MCTS presents it as a sub-tree with lo nodes Therefore. if computation can be carried out in parallel (e.g. by batching independent sub-problems at the same level of the sub-tree), the time complexity of DC-MCTS could be drastically reduced compared MCTS, in the best case (perfect parallelism and balanced binary solution tree) from O(lo")) to (log((o")))
they need to query the
B TRAINING DETAILS
B.I DETAILS FOR TRAINING THE VALUE FUNCTION
In order to train the value network v, that is used for bootstrapping in DC-MCTS, we can regress it towards targets computed from previous search results or environment experiences. A first obvious option is to use as regression target the Monte Carlo return (i.e. if the goal was reached, and if it was not) from executing the DC-MCTS plans in the environment. This appears to be sensible target, as the return is an unbiased estimator of the success probability P(*x E TTer of the plan. Although this approach was used in Silver et al. (2016). its downside is that gathering environment experience is often very costly and only yields little information, i.c. one binary variable per episode. Furthermore no other information from the generated search tree T except for the best plan is used. Therefore, a lot of valuable information might be discarded, in particular in situations where good sub- uub-plan for particular sub- -oboproblem was found, but the overall plan nevertheless failed.
This shortcoming could be remedied by using as regression targets the non- aon-amametric value estimates Vss, 8") for all OR nodes (s,8") in the DC-MCTS tree at the end of the search. With this approach, a learning signal could still be obtained from successful sub-plans of an overall failed plan. However, we empirically found in our experiments that this lead to drastically over-optimistic value estimates, for the following reason. By standard policy improvement arguments, regressing toward V leads to a bootstrap value function that converges v². In the definition of the optimal value of o*sss") max,/ v² (s. s') 20 (s', s"), we implicitly allow for infinite recursion depth for solving sub- sub-problems. However, in practice, we often used quite shallow trees (depth 10), so that bootstrapping with approximations of v" is too optimistic, as this assumes unbounded planning budget. A principled solution for this could be to condition the value function for bootstrapping on the amount of remaining search budget, either in terms of remaining tree depth node expansions.
Instead of the cumbersome, explicitly resource-aware value function, we found the following to work well. After planning with DC-MCTS, we extract the plan 5* with EXTRACTPLAN from the search tree T. As can be seen from Algorithm 2 the procedure computes the return G.. for all OR nodes in the solution tree Ta.. For training & chose these returns Gg. for all OR nodes in the solution tree as regression targets. This combines the favourable aspects of both methods described above. In particular, this value estimate contains bootstrapping and therefore did not lead to
15

---

Under review as a conference paper at ICLR 2021
Table Architectures of the neural networks used in the experiment section for the high-level value and prior. For each convolutional layer we report kernel size, number of filters and stride. LN stands for Layer normalization, FC for fully connected,, All convolutions are preceded by pixel zero padding.
Torso
Value head
3, 64, stride
Policy head
swish, LN
3 x 3, 64, stride =
3 x 3, 64, stride =
3 x 3, 64, stride swish, LN
swish, LN
swish, LN
3, 64, stride
3, 64, stride
3, 64, stride
swish, LN
swish, LN
swish, LN
3 x 3, 64, stride =
x 3, 64, stride =
3 3, 64, stride
swish, LN
swish, LN
swish, LN
Flatten
Flatten
3, 64, stride
FC: N₂ = sigmoid
FC: N₁, = #classes
swish, LN
softmax
3 x 3, 64, stride =
swish, LN
overly overly-optimistic bootstraps. Furthermore, all successfully solved sub- pooblloolem given a learning signal. As regression loss we chose cross-entropy.
B.2 DETAILS FOR TRAINING THE POLICY PRIOR
The prior network is trained to match the distribution of the values of the AND nodes, also with cross-entropy loss. Note that did not visit counts targets for the prior network done in AlphaGo and AlphaZero for example (Silver et al.) 2016 2018 since for small search budgets visit counts tend be noisy and require significant fine-tuning avoid collapse (Hamrick al. 2020).
B.3 NEURAL NETWORKS ARCHITECTURES FOR GRID- WORLD EXPERIMENTS
The shared torso of the prior and value network used in the experiments is 6-layer CNN with kernels of size 64 filters per layer, Layer Normalization after every convolutional layer, swish (cit) as activation function, zero-padding of 1, and strides [1, 1, 2, 1, 1, 2] to increase the size of the receptive field.
The two heads for the prior and value networks follow the pattern described above, but with three layers only instead of six, and fixed strides of 1. The prior head ends with a linear layer and softmax, in order to obtain distribution over sub-goals The value head ends with a linear layer and sigmoid that predicts a single value, i.e. the probability of reaching the goal from the start state we further split the problem into sub-problems.
We did not heavily optimize networks syper-parametent After running a random search over sypee-paraamters for the fixed architecture described above, the following were chosen to run the experiments in Figure The replay buffer has a maximum size of 2048. The prior and value networks are trained on batches of size 128 new experiences are collected. Networks are trained using Adam with a learning rate of 1e-3, the boltzmann temperature of the softmax for the prior network set to 0.003. For simplicity, temporal binary search trees). UCB constants are sampled uniformly between and 7, as these values observed to give robust results.
used HER with the time-basee rebalancing (i.e. turning experiences into
16

---

Under review as a conference paper at ICLR 2021
B.4 LOW-LEVEL CONTROLLER TRAINING DETAILS
For physies-based experiments using MuJoCo (Todorov et 2012), we trained a low-level policy first and then trained the planning agent to reuse the low-level motor skills afforded by this body and pretrained policy. The low-level policy, was trained control the quadruped ("ant") body go to randomly placed target in an open area (a ggo-to-targe' task, essentially the same as the task used to train the humanoid in Merel et al. 2019 which available at at|dm_come __ontro//lccomotion) The task amounts to the environment providing an instruction corresponding to target position that the agent is rewarded for moving to (i.c, a sparse reward when within a region the target). When the target obtained, new target is generated that is short distance away (<1.5m). What this means is that policy trained on this task should be capable of producing short, direct, goal-directed locomotion behaviors in open field. And test time, the presence of obstacles will catastrophically confuse the trained low-level policy. The policy architecture, consisting a shallow MLP for the actor and critic, trained solve this task using MPO Abdolmaleki et al.) (2018). More specifically, the actor and critic had respectively 2 and 3 hidden layers, 256 units each and elu activation function. The policy was trained a high level of performance using a distributed. replay-based off-policy training setup involving 64 actors. In order to reuse the low-level policy in the context of mazes, we can replace the environment- provided instruction with a message sent by high-level policy (i.e., the planning agent). For the planning agent that interfaces with the low-level policy, the action space of the high-level policy will, by construction, correspond the instruction to the low-level policy.
B.5 PSEUDOCODE
We summarize the training procedure for DC-MCTS in the following pseudo-code.
def train_
replay_buffer []
for episode in n_episodes:
start, goal
reset
sub goals de mets plan goal) list of sub-goals
replay_buffer. add (sub_goals)
state start
while episode.. not_overt
(sub_ggoaal3
action low_level (state, jub_goals(0)) (0))
state env sterssseppfoo (acticn)
Misited_states.apendd
if state sns guo_goals(0] sub_goat s. pop (0)
Rebalance list of visited states to dinary search tree bst states bst from wwwerfrroosrrreeeeeeerreeeeeeeee states (visived states)
replay replay_buffer... add (pst_states) Sindsight Experience Replay
if replay_buffer..cn_amm..l.
17

---

Under review as a conference paper at ICLR 2021
C
MORE SOLVED MAZES
In Figure g we show more mazes as solved by the trained Divide and Conquer MCTS.
Figure 8: Solved mazes with Divide and Conquer MCTS. = start, goal, wall,
walkable. Overlapping numbers are due to the agent back bocktrracking while refining finer sub goals.
C.1 SUPPLEMENTARY MATERIAL AND VIDEOS
Additional material, including videos of several grid-world mazes as solved by the algorithm and of MuloCo low-level policy solving mazes by following DC-MCTS plans, be found in the supplementary material.
18


Reviews:
[{"review_id": "wputW7cxDk0", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n\nDetailed Comments\n  - 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.\n\n  - 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.\n\n  - 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.\n  \n  - 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.\n\n  - 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.\n\n  - 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?\n\n  - 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.\n\n  - 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.\n  \n  - 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.\n\n  - 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?\n\n  - 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.\n  \n\nMinor points\n  - n doesn't seem to be defined in Section 2.1.\n\nUPDATE: 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).", "extra_scores": {}, "extra_text": {}}, {"review_id": "nDT2RLPb7h8", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n---\n\nThis 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.\n\nStrong Points\n---\n\n1) Interesting problem setting, way of modelling the problem, and proposed algorithm. Technically sound as far as I can tell.\n2) Solid and clear writing.\n3) Interesting results.\n\nWeak Points\n---\n\nThe 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?\". \n\nPersonally 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.\n\nOverall Recommendation\n---\n\nI recommend accept. The strong points are clear, and the weak points are quite minor.\n\nQuestions for Authors\n---\n\nWould 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.\n\nMinor Comments\n---\n\n- Final paragraph of Section 1, when listing all the subsequent sections, skips Section 4.\n- \"where \\varnothing is them empty\" --> \"where \\varnothing is the empty\" (second paragraph 2.1)\n- \"MPDs\" --> \"MDPs\" (third paragraph 2.1)\n- Even though it's fairly obvious already, I guess I'd prefer \"maximizing\" rather than \"optimizing\", to be 100% explicit\n- 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.\n- \"MDP wit a\" --> \"MDP with a\" (first paragraph Section 3)\n- \"free to chose\" --> \"free to choose\" (A.4)\n- \"procudre\" --> \"procedure\" (B.5)", "extra_scores": {}, "extra_text": {}}, {"review_id": "GrfDJG61jzJ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nThe 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.\n\nTo 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.\n\nIn 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.\n\n\n@article{wang2020learning,\n  title={Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search},\n  author={Wang, Linnan and Fonseca, Rodrigo and Tian, Yuandong},\n  journal={arXiv preprint arXiv:2007.00708},\n  year={2020}\n}\n\n\n@inproceedings{chen2020retro,\n  title={Retro*: Learning Retrosynthetic Planning with Neural Guided A* Search},\n  author={Chen, Binghong and Li, Chengtao and Dai, Hanjun and Song, Le},\n  booktitle={The 37th International Conference on Machine Learning (ICML 2020)},\n  year={2020}\n}\n\n@article{karaman2011sampling,\n  title={Sampling-based algorithms for optimal motion planning},\n  author={Karaman, Sertac and Frazzoli, Emilio},\n  journal={The international journal of robotics research},\n  volume={30},\n  number={7},\n  pages={846--894},\n  year={2011},\n  publisher={Sage Publications Sage UK: London, England}\n}\n\nUpdate after rebuttal:\nThanks 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.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "E0a6xLrNSgb", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "summary:\nThis 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.\n\n\n\npros:\n- It is interesting to perform planning for sequential-decision making problems in a non-sequential manner via a divide-and-conquer approach.\n\n\ncons:\n- 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.\n\n- 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.\n\n\n\ncomments and questions:\n- 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.\n\n- 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.\n\n- (page 7) Did the model-free baseline in the initial experiments use HER? or was it trained only with the actually experienced samples?\n\n- 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?\n\n- It seems DC-MCTS is relevant to path planning algorithms. Then, for example, could DC-MCTS be compared with the RRT family?\n\n- Above section 3.2: (line 17-18 in TRAVERSE) -> (line 15-16 in TRAVERSE) ?\n\n\n[1] Eysenbach et al., Search on the Replay Buffer: Bridging Planning and Reinforcement Learning, NeurIPS 2019\n[2] Nasiriany et al., Planning with Goal-Conditioned Policies, NeurIPS 2019\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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