CO-PILOT: COllaborative Planning and reInforcement Learning On sub-Task curriculum
Authors: Shuang Ao
Tianyi Zhou
Guodong Long
Qinghua Lu
Liming Zhu
Jing Jiang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Planning
Learning to Plan
Reinforcement Learning
Mutual Boosting
Collaborative Learning
Curriculum Learning
Sub-Tasking

Abstract: Goal-conditioned reinforcement learning (RL) usually suffers from sparse reward and inefficient exploration in long-horizon tasks. Planning can find the shortest path to a distant goal that provides dense reward/guidance but is inaccurate without a precise environment model. We show that RL and planning can collaboratively learn from each other to overcome their own drawbacks. In ''CO-PILOT'', a learnable path-planner and an RL agent produce dense feedback to train each other on a curriculum of tree-structured sub-tasks. Firstly, the planner recursively decomposes a long-horizon task to a tree of sub-tasks in a top-down manner, whose layers construct coarse-to-fine sub-task sequences as plans to complete the original task. The planning policy is trained to minimize the RL agent's cost of completing the sequence in each layer from top to bottom layers, which gradually increases the sub-tasks and thus forms an easy-to-hard curriculum for the planner.  Next, a bottom-up traversal of the tree trains the RL agent from easier sub-tasks with denser rewards on bottom layers to harder ones on top layers and collects its cost on each sub-task train the planner in the next episode. CO-PILOT repeats this mutual training for multiple episodes before switching to a new task, so the RL agent and planner are fully optimized to facilitate each other's training. We compare CO-PILOT with RL (SAC, HER, PPO), planning (RRT*, NEXT, SGT), and their combination (SoRB) on navigation and continuous control tasks. CO-PILOT significantly improves the success rate and sample efficiency.

CO-PILOT: COllaborative Planning and reInforcement Learning On sub-Task curriculum
Shuang Ao!, Tianyi Zhou Guodong Long', Qinghua Lut, Liming Zhu*, Jing Jiang'
University of Technology Sydney';
University of Washington, Seattle"; University of Maryland, College Park?; CSIRO's Data61, Australia*
shuang. @o@student. uts edu au, tianyi zheuw..hhw..... edu,
gguodong.lorts jing- jiang] (ang)@utss euttuus.eee.. au, (qinghua. lu, liming. zhu) @data61 csiro.au
Abstract
Goal-conditioned reinforcement learning (RL) usually suffers from sparse reward and inefficient exploration in long-horizon tasks. Planning can find the shortest path distant goal that provides dense reward/guidance but inaccurate without a precise environment model. We show that RL and planning can collaboratively learn from each other overcome their own drawbacks. In "CO-PILOTT", Iearnable path-plas planner and an RL agent produce dense feedback to train each other on curriculum of tree-structured sub-tasks. Firstly, the planner recursively decomposes a long-horizon task to a tree of sub-tasks in a top-down manner, whose layers construct coarse-to-fine sub-task sequences as plans complete the original task. The planning policy is trained to minimize the RL agent's 's cost of completing the sequence each layer from top to bottom layers, which gradually increases the sub-tasks and thus forms an easy-to-har Next, bottom-up traversal of the tree trains the RI. agent from easier sub-tasks with denser rewards on bottom layers to harder ones top layers and collects cost on each sub-task train the planner the next episode. CO-PILOT repeats this mutual training for multiple episodes before switching the RL agent and planner are fully optimized to facilitate each other's training. We compare CO-PILOT with RL (SAC, HER, PPO), planning (RRT*, NEXT, SGT), and their combination (SoRB) on navigation and continuous control tasks. CO-PILOT significantly improves the success rate and sample efficiency. Our code is available at https://gthhb..com http:///ituuu.coSSuuaaaaaa Saan/SSaangAA//O-PPPP
curriculum for the planner.
task,
Introduction
Although Al can surpass humans on certain tasks, humans still perform much better in making sequen- tial decisions via learning from interactions with the environment. Reinforcement learning (RL) [50] aims bridge this gap by learning optimize the trajectories agents (c.g.. controllers, robots, game players, self-driving cars, etc) to achieve the maximal return. However, in complicated long-horizon tasks, RL usually suffers from poor sample efficiency and costly data collection. Moreover, the data quality is often low due to sparse rewards when rollouts fail and cannot provide informative feedback. Model-based RL and off ofo-ppoicy RL improve the sample complexity with the price of extra biases. causing unstable and brittle optimization. Instead of reaching single goal, goal-conditioned RL [27] learns one model for any given goal input to model(s). However, it needs to be trained to reach many possible goals, and the resulted model's performance still degrades drastically for distant goals.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Instead, planning algorithms are usually more robust and effective on long- Long-horizon tasks. Given distance metric, they discretize the state space to a grid/graph and seek for the shortest collision-free free path between states using graph search such as Dijkstra's 's algorithm or A* [22]. Thereby, it only needs local policy to navigate between consecutive states on the path. However, is challenging to learn or estimate the distance accurately in complicated tasks such as mazes. Moreover, planning every step on the path is as difficult as the original RL and requires fine-grained discretization impractical for high-dimensional states. Planning only few milestone states leaves the RL agent to solve relatively long-horizon sub-tasks. Although sampling-bane baaedd search heuristics can build a graph with better ppploratioo-explotatiii adapt planning to a learned RL policy, which can provide distances estimated from its replay buffer, but the performance largely depends on the RL policy and its exploration.
trade-off, they are not optimized for the RL policy. [13]
critical insight of this paper is that planning at even a coarse level can be used for reward shaping and substantially improves RL on long-horizon tasks with sparse reward. In contrast, experiences of the RL. agent on the planned sub-tasks can improve the distance metric of planning to produce better paths/sub-tasking for the RL agent. Hence, the RL agent and path-planner can provide dense and informative feedback to train each other. Thus, combining their strengths helps to overcome the bottleneck of each one and improve their exploration efficiency.
(s.g)
(s,g)
Path Planner
Training data (Training only)
RL Agent
Training
Path Planner
Sub-tasks Tree
Groph Search
Top- Down
Bottom-up
Annd Way poants
EASY TO HARD
EASY TO Trak agent
Frat Plaveer
Geseuste
reat tuli
Apply A mach Way-ports
RL Agent
(x)
(b)
Figure (a) Mutual training between RL and planner CO-PILOT. The planner trained to recursively decompose a task (s, g) to a sub-task tree of coarse-to- fine min-cost sequences of sub-tasks. While this top-down construction forms an easy-to-has hasy-to-hard curriculum to train the planner, a bottom-up traversal of those sub-tasks forms an easy-to-hard curriculum for RL. The planned sub-tasks provides dense rewards enabling while RL's cost each sub-task is used train the planner for producing more cost-efficient suh-tasks for RI. For comparison, (b) describes how SoRB [13] combines RL with planning, which does not adopt such mutual training scheme and the sub-task curricula. In both diagrams, the brown arrows only happen in the training phase.
efficient RL,
In this paper, we propose "CO-PILOT",, a collaborative learning scheme between planning and goal-conditioned RL. As illustrated in Figure 1 (a), it trains each model under the other's s guidance along a curriculum of sub-tasks. Unlike most existing planning methods, we train a planning policy to recursively decomposes a task into two easier sub-tasks, which finally yields a tree containing coarse-to- fine trajectories of sub-goals to the final goal. The tree naturally forms a curriculum for more effective training. During the top-down tree construction, we start from training the planner to find the shortest path on a coarser graph with fewer sub-goals, which is an easier training task, and gradually request it to generate detailed paths with denser sub-goals We measure the distance by the cost of an RL agent navigating between consecutive sub-goals, so the planner is optimized to produce the most efficient path for the RL agent.
With the sub-goal tree constructed, we then train the goal-conditioned RL agent by a bottom-up curriculum, starting from easier sub-tasks with dense reward along the path and gradually enforcing the RL agent to navigate between more distant sub-goals. The sub-goals previously generated by the planner now provide an accurate reward shaping since they constitute cost-efficient paths for the RL agent. As byproduct of rollouts on the sub-tasks, the RL. policy helps to explore the environment topology and collect cost data between states to refine the distance metric for planning. Hence, the
2

---

top-down (bottom-up) curriculum training of planner (RL agent) eases the training on the original tasks and collects more informative feedback to train the RL agent (planner). CO-PILOT repeats the above procedures for episodes of mutual boosting between the two until they are fully optimized for the other. In experiments, we apply CO-PILOT to navigation and continuous control. Compared to existing RI., planning and combining them, CO-PILOT significantly improves the sample efficiency and the final success rate for long-horizon tasks.
2 Related Work
RL: Goal-conditioned RL [40, 27, 45] takes goal as an additional input to its model(s) and aims to handle different goals/tasks using the same policy. However, it requires more exploration and expensive training various possible goals, and it still easily fails to reach distant goals in practice. Goal Goalbrelag and reward shaping [3, 40, 19] have been commonly studied to mitigate these issues. Recent methods [16, 55] improve it by learning compact representation of the goal space. The goal-conditioned value function V(ggg) naturally provides an ideal distance metric for shortest path planning. [10, 54] propose train RL policy on a curriculum of environments adaptive to the RL. In CO-PILOT, we train a sub-goal tree planner to generate a sample-efficient and adaptive training curriculum that trains con-icondi to reach distant goals progressively. On the other hand, the goal-conditioned policy's ' cost on the planned paths is used to improve the planning policy.
Planning: Planning [50, 34] are more effective in addressing long-horizon tasks in practice [37, 29]. usually refers to dynamic programming that finds the optimal path between two nodes on a graph. Plamning methods in RL, e.g., value/policy iteration [33, 37J. utilize or learn an environment model to improve the RL policy. Compared to a reactive policy, an advantage of planning is that the planned trajectory provides global view of future steps. However, learning the environment model usually requires expensive exploration of state space [12, 35, 24, 391, structured and compact modeling of the environment/graph [7, 41], and accurate distance metric [13]. CO-PILOT overcomes these limitations by "learning to plan", which trains planning policy to produce sequences of sub-tasks that minimize the cost of the RL agent for completing the sequences. Specifically, we adopt recent sub-goal tree (SGT) planning [25] to generate tree-structured coarse-to-fine sequences of sub-tasks, instead of searching on a pre-built hierarchical partition tree of the state space as many hierarchical planning methods [39]. Moreover, we use the RL agent's 's time cost on the sub-tasks as the distance metric train the planner, which more accurate and adaptive. Furthermore, every-step planning is not necessary since few sub-tasks may already suffice to provide dense rewards and guidance to efficiently train the RL. agent, so the planning in CO-PILOT can be much easier. Compared to SGT and other hierarchical planning methods, the collaborative training between RL and "learning to plan" along easy-to- to-hard curricula in CO-PILOT can efficiently improve the performance of both RL and planning without heavily relying on prior knowledge.
Combine RL with Planning: A line of recent works [1, 36, 49, 46] embeds a planning model as one part of an RL agent's model and train it together with the RL policy in an end-to-end manner. [9, 15, 44] find that combining the two can help agents to reach distant goals in specific tasks. [13, 44] propose planning strategies with graph search based on the replay buffer of experiences from a given RL policy. [46] proposes use Monte-Carle -arlo tree search when planning in latent space to achieve a better op- timization on value function. These results inspire our work, but our primary difference is the mutual training between RL and planning, which does not require either a pre- pre-trained policy or strong heuris- tics about the distance metric. In CO-PILOT, both are trained from scratch and can mutually boost and guide each other's 's training via an auto- auto-generated curriculum of easy-to-hard sub-tasks. This mutual training leads to principled learning framework adaptive to vast amount of potential applications.
Hierarchical RL: Hierarchical RL (HRL) [26, 18, 38, 32] learns sequence of primeval policies, e.g., policies for lowelevel skills or casier sub-tasks, and then sequentially composes them to form high-level policy addressing complicated tasks. Another kind of HRL methods transfers the knowledge of a morphologically simpler agent to a more complex one [23, 8J. HRL for goal-reaching tasks has been studied in [13, 38]. A key challenge in HRL is how to define low-level skills or sub-goals [11, 17, 48, 2]. In CO-PILOT, we train a planning policy to automatically propose sub-tasks of increasing difficulty to train the RL agent. Therefore, RL agent starts from learning how
to reach nearby sub- and progressively improve its skills for completing long-horizon tasks.
3

---

3 CO-PILOT
3.1
Goal-conditioned Reinforcement Learning
Goal-conditioned RL or multi-goal RL learns a policy that can be adapted to different goals. Given the state space S. the action space A, and the goal space G. conditiood policy is mapping [als,, g) S x + A that outputs an action a (or probabilities Pr(a|s, g) over actions a E A) given state-goal pair (s, (8.g). An RL. agent uses π (a|s,0) 9) to interact with an environment described by Markov decision process (MDP) {S, A, G, p, 7), where p(s'|s, a) - Pr(st+1 8'1s; 8, az A the transition probability for the agent from state 8 to 8' after taking action a, r(s, alg) G + I is reward function, and y E [0, 1] is a discount factor.
a)
In each episode. the agent starts from an initial state so Po(s) and aims to reach given goal g E G. In every time step t, it takes an action a, x[a|s: g) (deterministic) or at T(a gt (stochastic), receives reward r(st, arlg), and moves to a new state S141 ~ p(s'|ss, 0z). RL aims to learn a policy maximizing the expected return (( (E.( s,0, a.g), the optimal pol-
Define the action-value function Q(s. g) & E(R]|s;
icy ' achieves the maximal alg for any feasible (s, Define the value function V(slg) A B(Rgss = 9. Eu>- alg)] EaeA A[ass, ((.(), Directly maximizing the expected return or w.r.t. x results in the vanilla policy gradient method [50], which usually samples inefficient and suffers from the high variance of R. Actor-critic methods [51] additionally
learns a model of V or Q as "critic" to the "actor" π, which performs as a baseline to effectively reduce the variance. The optimization of V or Q aims to minimize the Bellman residual
JQ= = ag. (s= axlg) r(se, (rlg) -BB, 11 [++++1]))]]
(1)
Given the critic Q, maximizing the expected return w.r.t. π reduces to minimizing
Jn g [~V(g)))) (e.))) 1B.,I-Q' (s, []]]]]
(2)
typical actor-critic algorithm alternates between minimizing Jo and Jæ. To encourage exploration, we use soft actor-critic (SAC) [20] that augments V with an entropy term (with temperature a), i.e.,
V((lg) Ee-=( (Q" alg) log ((als,)).
(3)
In order to encourage the above equation, SAC additionally optimizes V by minimizing the mean square error
Jv (..))) ([selg)- Ta (st, oelg) - a log a (a, 8t, (a))
(4)
SAC alternatively optimizes Jy, JQ and Jn (using the augmented V in Eq. (3)) defined in Eq. (1)-(4)
by using stochastic gradient decent (SGD) on batches of sampled (st, Qz. g). Although we use SAC in our experiments, CO-PILOT can work with any other RL algorithm besides SAC.
3.2 Reward Shaping for RL by Path-Planning
In various environments, an RL agent receives a nonzero reward only when reaching the e-ball B(g, e) around the goal g. i.e., r(s, g 1[s E B(g,e) e)] with 1 being the indicator, so r(s, alg) for most steps/trajectories cannot provide informative feedback to policy training. RL unstable and can easily fail with such sparse reward, especially in long-horizon tasks when g is far away from So or too difficult to reach for the
inttrriitinng.. To address this problem, reward shaping method [31] augments the environment reward with dense reward r' alg) that can be issued to more non-goal states, e.g., intrinsic motivation/curiosity that encourages effective exploration, or -nnineeen task-specific rewards. The ideal dense reward, which is, however unavailable without knowing π²", is V* (s(g). Planning methods, e.g., value iteration [52] or fitted-Q iteration [4], can approximate V (s(lg) but accurately estimating V*(ssg) (gg as challenging as the policy learning.
Path-planning and cootion-planning methods [12] usually adopt a heuristic distance or cost c(s, g) (e.g., Euclidean distance or time cost) to replace the unknown (slg). They discretize the state space into a grid/graph and find the shortest path connecting the initial state so and the goal g. In goal-conditioned RL, so and g can be any feasible states the graph, so path-plan muth-planning needs to solve the all all-- shortest path(APSP) problem [43], i.c.
min
9t41), Vsu E SSgEE E
(5)
90=
where 91-T-1 denotes a discrete sequence of sub-goals (91, 02, .2.............................. . gT between go = 80 and gr g. Planning every step for an agent is usually challenging and requires accurate e(--)) or

---

Pr environment model. But we only use planning for reward shaping, which can tolerate a small T. i.e.
T
r(s, algo.r)g = Σ
r(s, alge).
As T increases, F(s, a algo:T) becomes denser and the RL agent can receive more effective feedback for policy training. However, the quality of F(8, algo:r) also heavily depends on the cost for the agent to reach g by following the path 9o:T', since issuing reward to an inefficient/long path mislcads the policy training. Therefore, in CO-PILOT, we use a prediction model to predict c(+,)) and train the planning policy to generate 9o.7 incurring the smallest cost as in Eq. (5).
Remarks: This leads to a collaborative learning and mutual boosting scheme between RL and planning: planning produces easy sub-tasks that the RL agent can complete in a few steps and thus provide dense rewards enabling more efficient RL, while the time costs of RL agent on those sub-tasks can be used to further improve the planning policy towards producing more cost-efficient paths and better reward shaping. In addition, this scheme makes both RL and planning easier to overcome their bottlenecks: RL learns from dense rewards to complete long-horizon tasks, while relatively coarse (with small T') planning suffices to provide dense rewards so every-step planning relying on accurate modeling of MDP is not necessary. We will introduce more details next.
3.3 Curriculum for Learning to Plan Sub-task Tree
In the above scheme, planning serves RL like copilot in an aircraft to encourage more efficient training. The main advantage of a tree structure planner is to provide a global view of future milestones to the RL policy, which mainly focuses on local steps and might lack long-term sight. However, many planning algorithms are based on Bellman equation and sequentially predict the sub-goals, which may suffer from accumulated errors [42]. In addition, as the aforementioned, larger T results in easier sub-tasks for the RL agent but also increases the difficulty of planning, and vice versa. Hence, it is challenging to train both the RL and planning policy from scratch using either a small or a large T. This motivates us to seek coarse-to-fine planning that can generate multiple trajectories of sub-goals with increasing T, so the planning policy can be trained on an easy-to-hard curriculum [5, 14], i.., generating coarse-to to-fine shortest paths from small T to large T. At the same time, the RL agent also be trained on easy-to-hare curriculum of sub-tasks, i... by following the trajectories from large T to small T.
Therefore, we apply "sub-goal tree (SGT)" [25] to recursively divide a trajectory from small T to large T and produce a sub-task tree. We define a planning policy Tp(g gis 9;) as a stochastic mapping from two nearby endpoints 9i and 9j to predicted sub-goal g in the middle of g, and gj. In our scheme, we use (g 9;) to break down a task with initial state gi and goal 9j (denoted by (gt, (9.9g)) ) to two sub-tasks (gi, g) and (g, 93). Hence, we can generate a tree of sub-goals by recursively sampling sub-goals from Tp (p(999 9j) as below, which finally generates a planning trajectory 9o.r with tree structure, i.e.,
Pr(go:T 9o- Xp
So. 9T g)
9o. 90. (
Pr (9g.7 (9. TT ( s0.9).
(7)
By
where T = 2 with K being the depth of the tree. As shown in Figure 1 (a), for layer-k, k, the sub- sub-goal tree 90rr interpolates sequence of 2* sub-goals - A (of .t..:.t...................
..... 96 ..... between sp
and g. where .ز² = 9/5 in T. V E [2* - 1]. In layer=1, we have the coarsest trajectory (so: gi = 9r/2. g). In the bottom layer-K, we have the finest trajectory go.T. From top layers to bottome ones, their sub-goal trajectories naturally form coarse-to-fine sub-tasking curriculum, e.g., the planning in layer-1 1 requires the agent to accomplish two hard and layer-K's planning requires the agent to accomplish I'' much simpler and shorter-horizon sub-tasks.
sub-tasks to reach g, while
To train the planning policy T.. we apply it to produce a tree-structured go.T via Eq. (7) and evaluate the cost e (9b.2x) of the trajectory o by integrating the cost of every segment/sub-task ( s(44yyr/2)) along the trajectory, i.e.,e (s/ A Ei'n" e S We will elaborate on our option of cost function e(.,.) later in Eq. (11). The objective of T. aims minimize the total cost c(gorr) of the sub-goal tree, which sums over all trajectories' costs across the K layers,
c(gu.)) A
(st.2=).
(8)
k=
5

---

According to APSP objective in Eq. (5), the optimal planning policy T minimizes the expected cost J.p over all possible planning trajectories defined below:
Jap - go [c(gu.r)] = Puurrin [c(gu.)) (er
(9)
where 91:7-1 ~ T. denotes the recursive sampling of 91:T-1 in Eq. (7). Any policy gradient method can be used to minimize J with the gradient w.r.t. Ty computed as
V J xp E Bo
c(go.r)
V log Pr(gorr)ss (8:0)r)//09)) g) Fy
(10)
To form an easy-to-hard curriculum for training Tp. during the top-down construction of the tree, every layer-k, we train dp to only minimize the cost for layers from Eq. (8)) so the planning policy Tp starts from only producing relatively coarse sequence of a few
(instead of K in
sub-tasks for the top layers before trained to produce more detailed sub-task paths. In Line 4 of Algorithm 1, we will use J to denote c(go:r) computed up to layer-k.
Cost function of sub-tasks: As discussed in the end of Section 3.2, the cost function cgt, 9t+1) should reflect the difficulty of sub-task (gt, 9t+1) ) for the RL agent. Euclidean distance I|9: - 9t+1 ll2 is commonly used by previous aath-planning methods but is not adaptive to the evolution of the agent's s policy and environment, e.g., the difficulty of sub-task (9t,9t+1) with/without nearby obstacles can vary drastically. Instead, we use the time-cost Tg-s' spent by the agent on completing the task (g, g') to measure its difficulty, which adaptive to both the agent and environment and thus more accurate than Euclidean distance. By training the planner to produce minimum-cost sequences of sub-tasks, the planned paths are optimized for the training of RL policy. Since the time cost data is collected during the training of RL agent on the assigned sub-tasks, they are not available at the very beginning of the first episode. Therefore, we "warm start" the first top-down construction and training of the planner by Euclidean distance and consider the following cost function for the first two episodes, i.c.
c(g,, 9t+ i) = alI.gt gt 9t+ ||2 + (1 a)) (9t, I++1).
(11)
In experiments, we start from a and gradually reduce it towards 0 during the first two episodes. After that, the cost function is the time cost T(g.. 9c-1) collected in previous episode and no longer
depends on the Euclidean distance.
3.4 Mutual Training between RL and "Learning to Plan"
CO-PILOT is a mutual training
Algorithm Top- foo-Down Construction of Sub-Task Tree
scheme between the RL policy æ and
the planning policy Tp. each gen-
1: Input: (#o,g), g). planning policy Tp and its training set Dr
erating dense cost/reward structured sub-tasks to train the other.By top-down construction of sub-task tree from k = 0 to A = K, firstly trains the planning policy πp on a curriculum of generating coarse- to-fine trajectories. On each layer-k. k. it generates 2* sub-tasks through roll- outs of Tp. Given D, and the cost
tree-
2: Output: tree structured sub-goals go.r. TT
3: for k 1, ..., KK do
4: Apply any RL method to minimize Jt i.e. Jr,, in Eq, (9) computed only up to layer-k: 5: for fort= = 0, ,,...,,2--1
do 6: Generate the sub-goal of To -ot= gt o. );
7:
Add gi, .t. 1-1 into the trajectory go.r on layer-k; end for end for
8:
9:
c((,)) in Eq. (11), CO-PILOT OT updates Tp by minimizing Jr, in Eq. (9). At the very beginning of CO- PILOT, D, = 0 and the cost solely depends on the Euclidean distance. However, as we are collecting more experiences into D,, Tp will be trained towards producing the easiest sub-task trajectory for the RL agent to finish and thus increases its chance of receiving non-zero rewards. The complete proce- dures of top-down construction are given in Algorithm 1. Being updated using the most recent D,, up keeps tracking the RL agent's learning progress to produce the most cost-efficien paths for the agent. Moreover, the top-down construction naturally forms an easy-to-hard curriculum for the planning policy Tp- In Line 4 of Algorithm 1 we train Tp to produce sub-goal trajectories up to layer-k. Hence, the training of xp more smooth and less challenging than learning the optimal V or Q'.
After the top-down construction of the sub-task tree, CO-PILOT trains the RL policy π on a curricu- lum of easy-to-hard sub-tasks by bottom-up traversal of the tree from k K to k = 0. The sub- goal trajectory in each layer aims to guild the agent to complete the original task from so to At layer- k. CO-PILOT applies x sequentially to the 2 sub-tasks (as the conditioned goal). It then updates и by SAC, which alternates among the minimization of Jq. Jx and Jv in Eq. (1)-(4) to update x. V and Q.

---

Note we can replace SAC with other
Algorithm Bottom-Up Traversal of Sub-Task Tree
RL algorithms in the general frame-
work of CO-PILOT. The rollouts of on the sub-tasks not only collect
1: Input: RL policy n, sub-goal tree of go:T, Tmax:
2: Output: D,
3: Initialize: D 0
experiences to train itself but also collect tuples of (g.g', g' To.g') added
4: for A K.... 1.0 do
5: Set RL agent's 's initial state to be so < go:
to D,, which will be used to train
6: for L = ........ 2" do
Tp. It is possible that π fail on some sub-task within max steps. In this
7: Set the condition of V, Q in SAC to be gE:
8:
T + 0, B
case, we treat the actual ending state as g' in the tuple for Dr and initialize the the next sub-task from this state. The bottom-up traversal is detailed in Algorithm 2, where Line 9-13 apply reach sub-goal 9rr/2*- The bottom-up traversal forms an easy-to-hard curriculum train n, in which the sub-tasks from the bottom layers are easier so the agent by larger chance can receive non zero rewards.
9:
while T Tmax or 8 $ B(gi,c) do
10:
RL agent takes action a, (aaalls.,sh
agent moves to 8r+1 ~ p(5r+alsr, ur) and re-
ceives reward r(8r, ar lg:);
12:
4- B (st, ar r(s,, a. ).41)) end while
13:
14:
D. Dr U (40, 7),
15:
for every gradient step do
Apply gradient steps in SAC: update Q, V, क to mini- mize Jq. Ja and Jv in Eq. (1)-(4) using samples drawn from B;
17:
end for
Given a task (so. g). the curriculum
18: end for
guides the agent first to learn how to finish it by following a detailed planning path of many sub-goals. It then gradually increases the hardness by halving the number of sub-goals until recovering the original task. Therefore, it critically alleviates the sparse reward problem that usually fails considerably slows down RL on long-horizon tasks.
19:
end for
A prominent advantage and differ- ence of CO-PILOT compared to other methods that combine RL and
Algorithm CO-PILOT
1: Input: G. Po. T. Tiaxx C,
2: Output: RL agent's policy æ. planning policy mp
planning is to repeat the top-down con-
3: Initialize: æ, Tp. D, by Euclidean distance
struction and bottom-up traversal for
4: while not converge do
multiple (b in Algorithm 3) episodes
5: Sample task (so, g) with su po(s) and E G;
on each task (so.g). Thereby, the RL agent and the planning policy are fully optimized for each other's training, forming
6:
for episode 1, 2,..., do
7:
Algorithm top-down construction of sub-task tree go.r. train planning policy Tp based on Dr; Algorithm 2: bottom-up traversal of the sub-task tree ga.r, train RL policy collect D.;
adaptive curriculum without human engineering. The complete procedures of CO-PILOT are listed in Algorithm 3.
8:
9:
end for
10: end while
Experiments
We evaluate CO-PILOT three types of tasks: maze and two continuous control tasks for robotic navigation. CO-PILOT outperforms several strong baselines of RL and planning, as well as methods combining RI. and planning, on both sample efficiency and final success rate.
We build a maze environment of size 1 X 1 containing square obstacles(obstacle states) and free-to-reach states as shown in Figure 4. For each benchmark design of benchmark refer to the caption of Figure 2), We randomly sample 300 pairs of (so. g) for training and 100 pairs for test from a uniform distribution
Maze environment:
the coordinate range and remove the ones in obstacles. It takes an RL agent 2 200 steps on average moving from Sy to g. which is a long-horize -ong-horizon task. The task succeeds if the agent reaches B(g. c 0.025) without collision.
Mujoco Ant-yl: We evaluate CO-PILOT and baselines the Mujoco environment with an Ant-v1 agent (Quadruped [53]) with an 8-dim action space. As shown in Figure 2 (c), we train the agent to navigate in the maze without self-rotation and collisions to the wall. We randomly sample 50 (so. pairs for training and 10 pairs for test.
7

---

The BipedalWalkes environment [6] offers new perspective of tasks rather than maze type. The learning agent, embodied in a bipedal walker, receives positive rewards for moving forward and penalties for torque usage and angular head movements. Agents are allowed 2000 steps to reach the other side of the map. The environment producing tracks paved with stumps varying by their height parameter f4a and an independent sampled spacing parameter A, E N(n,, 0.1). We design three agents with different length of legs (as shown in figure 3) for each benchmark. Performance is evaluated periodically by sampling 10 tracks in each track distribution of fixed evaluation set of 50 distributions sampled uniformly in the parameter space. We measure the percentage of mastered tracks.
BipedalWalker:
Baselines: In the maze environment, we compare CO-PILOT with (1) three planning methods: RRT* [28] (Rapidly-explorics Random Trees), NEXT [7] (Neural iipooration-xploittationn Trees) and SGTPG [25] (Sub-Goal Tree Policy Gradient);; three model-free RI. algorithms: palued-based method SAC [21], policy-basee basee method PPO [47] (in CO-PILOT,, we use the former to train the RL policy and the latter to train the planning policy) and HER [3], which improves goal-conditioned RL's efficiency by re-labelling the visited states as pscudo goals; and (3) a RL-planning hybrid method: SoRB [13], which trains planning strategies based on the experiences of a given RL policy. For fair comparisons, we use SAC as the RL algorithm in both CO-PILOT and SoRB. In the Mujoco environment, we compare CO-PILOT with SAC, SoRB, and hierarchical RL [23]. In Bipedal Walker, we compare CO-PILOT with SAC and SoRB.
(k)
641
Figure 2: (a) Success rate on test tasks of Maze environment. We train three types of agents with different DoF (degrees of freedom): point mass (2D), rigid body (3D), and 3-link snake (5D). More details are given in Appendix B. (b) Success rate of CO-PILOT with sub-goal tree of different depth K on the same test in (a). (c) Ant-vl agent and the associated environment in Mujoco. (d) Average return of Ant-vl in (c).
4.1 Training Details and Hyperparameters
In CO-PILOT, we initialize the dataset D. with 50,000 tuples of (g.g's (T..a) with Tg.9' being the Euclidean distance. We use SAC to train the RL policy and PPO [47] train the planning policy in Line 8 of Algorithm 1, since the former encourages exploration and the latter is simple and efficient. We set a reward of (1000, 200) to each task (so.9) .) in Maze (Mujoco.BipedalWall BipedalWalker), According to Eq. (6), the reward of each sub-task in layer-k is 1/2* (1000/2* 200/2*), For planning cost, if the segment between (gt, 9t++1) trespasses any obstacle, we add a penalty of 10 to T ( (t+1))t+)))))) in Eq. (11). We linearly reduce in Eq. (11) from 0.9 to 0.1 throughout every episode. For planning policy training, we apply PPO with a trust region of E = 0.2 and use Adam optimizer [30] with a learning rate of 0.005. For RL training with SAC, we use its default hyperparameters. In both environment, we set T = 2 (ablation study of different T in Figure 2 (c)) and 6 = 5 (further increasing it does not improve the performance). We set Tmax = 25, Tmax 200 and Tmaz 2000 for Maze, Mujoco and Bipedal Walker respectively. For efficiency, in Line 5 of Algorithm 3, we instead sample mini-bace batch of 30 (Maze) or 50 (Mujoco) pairs of (so. g). The (so. g) is fixed in HipedalWalker, we randomly sample 20 tracks in each track distribution from the same 50 distributions mentioned in section 4.
4.2 Main Results
In Figure 2 (a), we compare the performance of CO-PILOT with all the baselines on the test tasks of the Maze environment. CO-PILOT achieves the highest success rate across all benchmarks and significantly outperforms SAC and SGTPG. Figure 4 (a)-(c) report how the success rate of all methods change during training as the number of interaction steps with the environment increases. We limit the total environment steps of all methods < 1.8 x 10 except for NEXT (since NEXT
8

---

requires the pre-training of RRT*). In Figure 4 (a), CO-PILOT and SGTPG perform similarly in the early training period because the cost data collected by the RL agent do not contain sufficient information to train powerful path-planner and the inaccurate Fuclidean distance dominates the cost -(.-)) Eq. (11). The performance of SoRB and SAC are similar because SoRB needs to pre-train the RL policy at first when no planning is required. SoRB surpasses SAC during the later stages. NEXT also needs to pre-train RRT* before applying self-improving training, so we do not see the change of cost and collision checks for NEXT during the earlier stages. The comparison between CO-PILOT with SAC demonstrates the significant improvement brought by the learned planner to RL. The average return on Mujoco tasks is shown in Figure 2 (d). Further- more, the percentage of mastered envi- ronments on Bipeda/Walker is shown in Figure 3. For simplicity, we de- note [23] as HRL. SoRB and HRL start later because the RL policy is under pre-training. The experimental results show that CO-PILOT achieves much better sample efficiency than all the baselines, including SoRB. The fi- nal performance is comparable with SoRB but significantly outperforms SAC and HRI HMu(Moooco)
Figure 3: Main results and comparison in BipedalWalker. The mean performance (32 seeded runs) is reported together with the standard deviation (shaded areas).
CO-PILOT with sub-task tree of different depth K: In Figure 2 (b), evaluate 5 different depths for the sub-task tree in CO-PILOT, with all the rest hyperparameters fixed. It shows a trade-off between RL and planning, i.e., deeper sub-task tree can provide denser rewards and more detailed guidance from sub-tasks, hence improving the efficiency of RL, but it also makes training the planning policy more challenging. In this experiment, the best trade-off is achieved when depth K 5.
4.3 A Close Look of Mutual Training CO-PILOT
To understand the mutual training of CO-PILOT in the experiments, in Figure 4 (d), we visualize how sub-task tree evolves over episodes in Algorithm 3, where the sub-goal paths at layer-2, 3, 4 generated in Episode- 3,5 for the same task (so. g) are reported. Each maze map contains a path from layer in an episode and the histogram above reports the time cost of RL for completing each sub-task on the path. We are particularly interested in two questions: how does planning guide RL by sub-tasking? How does RL agent's cost affect the planned paths?
Train u. using RL agent's time cost data. In Episode- 1, the sub-goal paths of all the three layers too close some obstacles or even trespass some others and thus cannot provide reliable guidance for the RL agent. The Euclidean distances between consecutive sub-tasks on a path are almost equal but the corresponding time costs shown in the histograms vary a lot, which not preferred since some sub-tasks are too hard, but some are too easy for training the RL agent. Hence, the planning policy is not fully optimized to produce cost-efficient paths for the RL agent.
In Episode-3, 3, the generated sub-goals paths become more adaptive to the environment. In all layers, we can see that the planner tends to generate longer segments for places with fewer nearby obstacles and collision risks while adding more fine-grained sub-tasks to get around the corners. This phenomenon implies that the planning policy is learning to produce better and more adaptive guidance with dense rewards. However, due to the limited number of sub-goals per layer, the paths in layer-2, 3 can still be improved if interpolating more sub-goals. Nevertheless, on the deepest layer-3, the planned path is already collision-free and thus can provide an accurate reward shaping for the RL agent.
In Episode-5, the planning paths are almost optimal, especially for the one in layer-4, which keeps distant from the obstacles of both sides in the maze. Moreover, RL agent's time costs shown in the histograms are not only much lower than those of the previous episodes but also have similar values across different sub-tasks. Hence, the planning policy is well optimized to generate cost-efficient paths for RL.
Planner guides RL by sub-tasking. In Fpisode-1, the time cost for the RL agent to finish the whole task is much higher than that in the later episodes due to the poor RL policy at the beginning.

---

0.9
0.4
0.2
1.0
cnv (teco(1e6)
Parhs
0.5
1.0
2.0
BPV stapa("inn (6))
Ave Colloin chooks
1.5
0.5
1.0 stappet
Epiodezi
Episodae3
Episodes5
Figure 4: (a) Success rate. (b) Average path length (normalized by RRT") in terms of Euclidcan distance. (c) Average collision checks (normalized RRT*) as every method increases its interaction steps with the environment. CO-PILOT achieves the best sample efficiency among methods. (d) Visualization of the sub-goal paths on layer-k
task with initial state so (red dot) and goal g (blue dot) in Maze. Each histogram reports the RL. agent's cost St4. for sub-tasks along the path. As episode increases, planning paths across all layers improved, and on each path the costs of all sub-tasks reduce towards similar value. though the Euclidean distances are still different, since the planner learned to produce more sub-tasks near complicated obstacles.
3, 1 the sub-task tree in Episode-1, 3,
In contrast, the time cost drastically decreases Episode-3 when compared to Episode-1, 1, which indicates that the RL policy is significantly improved under the guidance of planning. In Episode-5, the time cost for completing each sub-task of layer-3, further decreases when compared to the former episodes and the costs becoming more uniform across sub-tasks, implying that the RL policy learns to complete the planned sub-tasks more efficiently.
Therefore, both planning and RL are improved via the mutual training scheme in CO-PILOT and fully optimized to facilitate the training of the other. In particular, the planner learns to produce cost-efficient paths of different amounts of sub-tasks to guide RL with dense rewards. It does not depends on any pre-defined metric but is adaptive to the RL policy. Moreover, it does not need to produce step-by-step plan: the RL agent can learn efficiency under the guidance of few interpolated sub-tasks by the planner. Hence, the mutual training between the two policies overcome the bottlenecks of training each policy separately. In addition, the easy-to- tordard curricula for both planning and RL considerably improves their training efficiency.
5 Conclusion
We propose CO-PILOT, mutual learning framework hetween RI and "learning to plan" policies, which provides principal solution addressing the problems of both RL and planning when applied to long-horizon tasks. In CO-PILOT, each policy produces dense feedback on a curriculum of sub-tasks to train the other more efficiently and is optimized to assist the other's training. The planner learns to decompose a the interpolated sub-tasks, forming an easy-to-hane curriculum to train the planning policy. On the other hand, this top-down curriculum recursively builds coarse-to-fe to-fine sequences of sub-tasks. By training RL agent to complete easier sub-tasks on finer sequences bottom layers at first and then gradually moving to harder ones in top layers, the RL agent can be efficiently trained following an easy-to-hard curriculum. In experiments, CO-PILOT significantly improves the sample efficiency and success rate different types of tasks especially Hong-horizon tasks with sparse rewards.
task into few sub-tasks at first and then gradually increases
10

---

Acknowledgments
This work was supported by Australian Research Council (ARC) LP180100654 and CSTRO/DATA61 CRP Project C019309. We would like to thank NeurIPS area chairs and anonymous reviewers for their efforts reviewing this paper and their constructive comments!
References
[1] Brandon Amos, Ivan Dario Jimenez Rodriguez, Jacob Sacks, B. Boots, and Z. Kolter. Differentiable mpe for end-to-end planning and control. In NeurlPS, 2018.
[2] Jacob Andreas, D. Klein, and S. Levine. Modular multitask reinforcement learning with policy sketches. ArXiv, abs/161 1.01796, 2017.
[3] Marcin Andrychowicz. Dwight Crow, Alex Ray, J. Schneider, Rachel H Fong. P. Welinder, Bob McGrew, Josh Tobin, P. Abbeel, and W. Zaremba. Hindsight experience replay. 2017.
[4] András Antos, Csaba Szepesvári, and Rémi Munos. Fitted q-iteration in continuous action-space mdps. 10:9-16,22 2008.
[5] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. page 41-48, 2009.
[6] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym. 2016.
[7] Binghong Chen, Bo Dai, Qinjie Lin, G. Ye, H. Liu, and L. Song. Learning to plan in high dimensions via neural exploration-exploitation trees. 2020.
[8] Tao Chen, Murali, and A. Gupta. Hardware conditioned policies for multi-robot transfer learning. In NearlPS, 2018.
[9] Hao-Tien Lewis Chiang, Aleksandra Faust, Marek Fiser, and Anthony Francis. Learning navigation behaviors end-to-end with autorl. IEEE Robotics and Automation Letters, 4:2007- 2014, 2019.
[10] Michael Dennis, Natasha Jaques, Eugene Vinitsky, A. Bayen, Stuart J. Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. ArXiv, 2000/201.00206,, 2020.
[11] C. Drummond. Accelerating reinforcement learning by composing solutions of automatically identified subtasks. ArXiv, abs/1 106. 2002.
[12] M. Elbanhawi and M. Simic. Sampling-baid based robot motion planning: A review. IEEE Access, 2:56-77, 2014.
[13] Benjamin Eysenbach, R. Salakhutdinov, and S. Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In NeurlPS, 2019.
[14] Meng Fang, Tianyi Zhou, Yali Du, Lei Han, and Zhengyou Zhang. Curiculum-guidee hindsight experience replay. In Advances in Neural Information Processing Systems, volume 32, 2019.
[15] Aleksandra Faust, O. Ramírez, Marek Fiser, Kenneth Oslund, Francis, James O. Davidson, and I.. Tapia. Prm-rl: Long-range robotic navigation tasks by combining reinforcement learning and sampling-basee based planning. 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 51 3113-5120, 2018.
[16] Carlos Florensa, J. Degrave, N. Heess, Jost Tobias Springenberg, and Martin A. Riedmiller. Self-supervised learning of image embedding for continuous control. ArXiv, abs/ 11/11900.0045. 2019.
[17] R. Fox, S. Krishnan, I. Stoica, and Ken Goldberg. Multi-level discovery of deep options. ArXiv, abs/1703.0082% 2017.

---

[18] Kevin Frans, Jonathan Ho, Xi Chen, P. Abbeel, and John Schulman. Meta learning shared hierarchies. ArXiv, abs/1710.09767, 2018.
[19] Dibya Ghosh, A. Gupta, Ashwin Reddy, Justin Fu, C. Devin, Benjamin Eysenbach, and
S. Levine. Learning to reach goals via iterated supervised learning. arXiv: Learning, 2019.
[20] T. Haarnoja, Aurick Zhou, P. Abbeel, and S. Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor 2018.
[21] T. Haarnoja, Aurick Zhou, Kristian Hartikainen, G. Tucker, Schoon Ha, J. Tan, Kumar, H. Zhu, A. Gupta, P. Abbeel, and S. Levine. Soft actor-critic algorithms and applications. ArXiv, abs/18 12s.0982,05905, 2018.
[22] E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
[23] Donald Hejna, P. Abbeel, and Lerrel Pinto. Hierarchically decoupled imitation for morpho- logical transfer. ArXiv, abs/2003.01709, 2020.
[24] D. Hsu, J. Latombe, and R. Motwani. Path planning in expansive configuration spaces. 3:2719-2726 vol.3, 1997.
[25] T. Jurgenson, Or Avner, E. Groshev, and Aviv Tamar. Sub-goal trees framework for goal-based reinforcement learning. ArXiv, abs/2002.1236/ 2020.
[26] L. Kaelbling. Hierarchical learning in stochastic domains: Preliminary results. In ICML, 1993.
[27] L.. Kaelbling. Learning to achieve goals. In IJCAI, 1993.
[28]
Sertac Karaman and Emilio Frazzoli. Sampling based algorithms for optimal motion planning. The International Journal of Robotics Research, 3047)844-8994, 2011.
[29] L.
E. Kavraki, P. Svestka, J. Latombe, and M. H. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4):566-580) 1996.
[30] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.6980, 2015.
[31] Sven Koenig and Reid G. Simmons. The effect representation and knowledge on goal- directed exploration with reinforeement-eemming algorithms. Mach. Learn., 22(1-3):227-2555 January 1996.
[32] Tejas D. Kulkarni, Karthik Narasimhan, A. Saeedi, and J. Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In NIPS, 2016.
[33] M. Lau and J. Kuffner. Behavior planning for character animation. In SCA '05, 2005.
[34] S. M. LaValle. Planning Algorithms. Cambridge University Press, Cambridge, U.K., 2006.
[35] Steven M. Lavalle. Rapidly-exploring random trees: A new tool for path planning. 1998.
[36] L. Lee, Emilio Parisotto, Devendra Singh Chaplot, Xing, and R. Salakhutdinov. Gated path planning networks. In ICML, 2018.
[37] S. Levine, Y. Lee, V. Koltun, and Z. Popovic. Space-time planning with parameterized locomo- tion controllers. ACM Trans. Graph., 30:23:1 2011.
[38] Ofrr Nachum, Shixiang Gu, H. Lee, and S. Levine. Data-efficient hierarchical reinforcement learning. In NeurIPS, 2018.
[39] Karl Pertsch, Oleh Rybkin, Frederik Ebert, Chelsea Fino, Dinesh Jayaraman, and Levine. Long-horizon visual planning with goal-conditioned hierarchical predictors. ArXiv, abs/2006.13205, 2020.
12

---

[40] Vitchyr H. Pong, Shixiang Gu, Murtaza Dalal, and S. Levine. Temporal difference models: Model-free deep for model-based control. ArXiv, abs/1802.09081, 2018.
[41] Markus Rickert, O. Brock, and A. Knoll. Balancing exploration and exploitation in motion planning. 2008 IEEE International Conference Robolics and Automation, pages 2812-2817, 2008.
[42] S. Ross, G. Gordon, and J. Bagnell. A reduction of imitation learning and structured prediction no-regret online learning. 2011.
[43] Stuart Russell and Peter Norvig. Artificial Intelligence: Modern Approach. Pearson Education, 2 edition, 2003.
[44] Nikolay Savinov, A. Dosovitskiy, and V. Koltun. Semi-parametrie topological memory for navigation. ArXiv, abs/1 803.00653, 2018.
[45] Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxi- mators. pages 1312 1320, 2015.
[46] J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lock- hart, D Hassabis, and T. Graepel. Mastering atari, go, chess and shogi by planning with a learned model. 2019.
[47] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/ 707.006377, 2017.
[48] Ö. Simsek, Alicia P. Wolfe, and A. Barto. Identifying useful subgoals in reinforcement learning by local graph partitioning. In ICMI. '05, 2005.
[49] A. Srinivas, Jabri, P. Abbeel, S. Levine, and Chelsea Finn. Universal planning networks. ArXiv, abs/1804.00645, 2018.
[50] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018.
[51] Richard S. Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. NIPS'99, page 1057-1063, Cambridge, MA, USA, 1999. MIT Press.
[52] A. Tamar, S. Levine, P. Abbeel, Yi Wu, and G. Thomas. Value iteration networks. 2016.
[53] Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmalcki, Josh Merel, Andrew Lefrancq, Timothy P. Lillicrap, and Martin A. Riedmiller. Deepmind control suite. 2018.
[54] Rui Wang, Lehman, J. Clune, and K. Stanley. Paired open-ended trailblazer (poet): Endlessly generating increasingly complex and diverse learning environments and their solutions. ArXiv, abs/1901.011 00375,..55.... 2019.
[55] Y. Wu, G. Tucker, and Ofir Nachum. The laplacian in rl: Learning representations with efficient approximations. ArXiv, abs/1810/ 810.04586, 2019.
13


Reviews:
[{"review_id": "sj5fmSgjozi", "reviewer": "Reviewer_Exeq", "summary": "The paper proposes a method for hierarchical reinforcement learning where the high-level policy learns to split goal-reaching tasks into halves to form an optimal subgoal sequence of increasing level of nestedness that can be executed by the low-level policy on all levels. In this way, an effective reward shaping for low-level learning is performed aiming for increased sample efficiency.\nThe main contribution of the paper is the mutual learning of both hierarchy levels (called planner and RL policy) in a way that they provide a mutual curriculum from easy to hard tasks.\nThe low-level policy is ultimately optimized to solve the final task at once.\n\nThe strongest shortcomings are in the experimental evaluation. Both the write-up and presentation need improvements.", "questions": "", "limitations": "", "rating": 4, "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": "General:\nStrong points:\n- The hard tasks for the planner are the easy tasks for the low-level and vice versa\n- The setup of the two levels of hierarchy, in a way they create a mutual curriculum and mutually improve.\n- Algorithms are described and some ablations are performed.\n\nWeaknesses:\n- What is called a planner is actually not a planner. Planning (in the usage here as path planning) means that based on a model or other edge cost function a path is optimized over a set of possible paths (at runtime). Here the planner is just producing a single path (with increasingly finer resolution). There is not online optimization performed, it is just another RL problem where a policy is learned. So this is clearly a misnomer and confusing.\n- If a real planner would be used generalization to new environment structures, such as different mazes could be expected, which would really be interesting. In this case, it is just another way to overfit to one particular environment\n- the manual curriculum in Eq 12 is unsatisfactory and maybe not necessary.\n- Since the paper is a mainly experimental paper, the empirical evaluation needs to be solid. Here I see too strong shortcomings. There are three envs.\n1) The first is the author's own maze with a single maze layout. The illustrated path in Fig.4 is not particularly good for illustration. There should be a path from bottom-left to center-left, such that many obstacles have to be circumvented.\n2) In the  Mujoco-Ant Maze the walls are ignored and the ant cannot rotate around its center if I understand correctly. This is an utterly strong simplification and makes a comparison in this standard benchmark problematic.\n3) I don't understand why the walker is a good example of high-level planning. Is the terrain observable to the planner? Which space are the goals defined in? These details are missing and no code is provided\n- What about a task that is akin to long-term planning with sparse rewards like a multiroom with keys and doors or similar? \n\n- in the checklist point 4.3, the authors declare not to share the new asset  (namely their maze env). \n\n\nNovelty:\n- as far as I can tell the algorithm is sufficiently novel\n\nClarity and presentation:\n- the language contains many typos and grammar mistakes\n- the presentation of the algorithm and preliminaries need improvements. I suggest to remove some details which are standard, such as the SAC updates and focus on your part to make that clear\nOne part that needs improvement is the connection between Eq 5 and Eq 6. It is not clear where r(s,a|g) is coming from in Eq 6. Please be more precise.\n- The fonts and details in the graphics are way too small\n- Fig 4 needs a better trajectory example to make the point\n- consider deferring some technical details to the supplementary and explains the experiments better\n- as mentioned before: your high-level is not a planner\n\n\nDetails:\n- l126: Define the value function.... reads weird\n- l187: why nearby endpoints?\n- l201: I found the usage of the cost function c for a sequence of goals and for just one segment not ideal.\n- Eq 12: In your algorithm, you initialize the dataset with Euclidean distances for random goal pairs. Why do you then need this manual curriculum with alpha.\n- Algo2: I think a \"goal-reached\" statement is missing, as I guess the agent moves on to the next goal as soon as it achieves one. Is the success radius the same as for the final goal?\n- You write Mujoco env. but this makes no sense. Mujoco is the simulator that is used in 100s of environments. It is the \"AntMaze\" env. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "PNAhU8l6fwG", "reviewer": "Reviewer_YPXK", "summary": "The authors propose an algorithm for jointly learning a sub-goal-setting policy and a goal-reaching policy. To train a sub-goal setting policy, the authors propose to minimize the sum of cost between generated sub-goals, where the cost is determined by a model that predicts the number of steps to move between the two goals. The goal-reaching policy is trained with sparse rewards. Lastly, this time-prediction model is trained with data collected by the policy, effectively “closing the loop” between the policy and the planner. The papers compare to existing graph-based RL methods and standard RL algorithms (PPO, SAC), and find that the resulting algorithm generally outperforms prior methods on numerous navigation tasks.", "questions": "", "limitations": "", "rating": 4, "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": "The paper studies an interesting problem of combining planning with goal-conditioned RL. The method is novel and proposes a promising method to “close the loop.”\n\nThe experiments are fair, but there are additional details and comparisons that would strengthen the paper. For one, it seems that the authors did not compare to standard goal-conditioned algorithms such as HER. Adding this comparison would greatly help. Another concern is that the experiments do not describe how the prediction model is trained.\n\nAlgorithmically, it is unclear why the planning policy must be trained with a policy gradient method. Given that the cost is evaluated with a learned prediction model c, can’t the authors directly minimize Eq. 8 with back-prop?\n\nA major concern with the paper is that I found it generally difficult to follow. There were a few statements and notations in Section 3.2 that are not explained. For example, the paper says, “As T increases, r(s, a, g_{0:T}) becomes denser” and “planning provides dense rewards and sub-tasks to train the RL agent” but it is unclear why this is the case. How is planning providing “dense rewards”? Equation 6 seems to be a sum of sparse rewards, which will generally be sparse as well. Also, from Equation 6, is the policy conditioned on a sequence of goals, g_{0:T}?\n\nThere are also a number of other writing issues:\n - Section 3.4 seems redundant with the previous sections, unless I am missing something.\n - The figure font is too small and there is a lot of standard vertical white space missing between figures, text, and section headers.\n - There is a recursive dependency between Equation 11 and 12. How is this resolved?\n - “We set a reward of  1(1000,200) to each task”)\n - Equation 11 does not give a proper update rule for the prediction model c. (as indicated in line 9 of Algorithm 1\n\nOverall, although the experiments are promising, the redundancy and lack of clarity in writing make it difficult to recommend an acceptance of the paper, along with the other concerns mentioned above.\n\nEdit: I acknowledge that I have read the author's response and will maintain this score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss the limitations of the work. Adding such a discussion would help.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "NnjE6ACXcnO", "reviewer": "Reviewer_uZ3D", "summary": "Sparse rewards in goal-conditioned RL is a challenging problem. This paper addresses this problem by decomposing the original task of reaching the goal, to smaller tasks of reaching subgoals instead. To achieve that, they train (1) a recursive subgoal predictor that builds on top of the Sub-Goal Tree (SGT) formulation, and (2) a goal-conditioned Soft Actor Critic (SAC) agent that gets rewards when subgoals are met. These models are trained in tandem, and the main novelty of this paper is that each model makes the learning of the other model easier. They show in experiments that this method works well in navigation tasks, as well a control task of walker 2D. ", "questions": "", "limitations": "", "rating": 3, "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": "I like the idea and see the value it would add to the RL community. However, the mathematical and algorithmic formulation as well as the clarity of text (structure and consistency of ideas) needs *a lot of work* in order for this paper to be publication-ready. Right now, there are some theoretical points that are still unclear to me, and I think that in order to make it understandable, this work would need a (big) revision (see my detailed comments below). Moreover, I have some issues with the experimental section - see below. \n\nIn conclusion, despite my long review below, *I really do like this work*. It is novel and interesting and I think that in the future it will be a great paper(!!). However, currently the presentation and formulation of the ideas prevent it from being publication worthy.\n\nMajor concerns:\nFormulation, correctness, and readability of the paper:\n1. Starting from section 3 the textual description becomes somewhat ambiguous \\ a bit unreadable \\ not fully specified. Like I said before, I think a clear presentation of the subgoal ideas with accurate formulation would both make this shorter, more readable, and non-ambiguous. Specific points:\n(A) I think the paragraph about path-planning (section 3.2) contains some inaccurate information. First c is not used to replace V*, it is the negative of the reward function in the common RL formulation. In your case, you define a surrogate task in which c is indeed not the inverse of r, but this is your specific usage and not the general case. Second, in path planning, the setting could be seen as a goal conditioned MDP where the action space happens to be the state space. Finally, path planning doesn't have to solve the APSP problem, at least not in a sense that it needs to identify how to optimally reach between every two states at the same time (for instance, given a start and goal states all variants of RRT build a roadmap that is specific to a *specific* start and goal).\n(B) Cost function issues (starting at line 212):\n1. Please explain (formally) what is a monotonic hyperbolic function.\n2. Since your cost function depends on the travel of the RL agent between states, and your agent is stochastic, you get a stochastic cost function. The SGT formulation you rely on in this work does not support stochastic costs functions. I suspect that part of the reason (which you address in your work) is to make sure the RL agent is able to travel between two subsequent goals. I suggest you extend the policy gradient theorem of SGT-PG to a stochastic cost function (using your assumption of reset to the next subgoal). \n(C) Unclear test time behavior - you did not specify what happens during test time. I suspect that you plan subgoals and then feed them sequentially to the RL policy. But how do you handle the case where the agent doesn't reach the next subgoal? how do you decide when to advance to the next subgoal?\n(D) Equation 11, please clarify that this is the target value for the c_phi prediction. Also, what is the loss function you use to train this regression model?\n(E) Another issue with the SGT formulation, you do not differentiate between costs of different levels. For instance, consider going from s->g directly, vs. going from s->g through m as a middle point. If \\pi is able to produce the optimal path between s to g, and m is a detour (if the planner is not perfect) then both costs would be listed as costs for the subgoal segment (s, g). Moreover, you are likely to see more lower level paths from s->g than higher level ones (which biases the costs towards results towards the leaf prediction). This makes no sense to aggregate all into the same cost function. I also think that in the original SGT formulation there was a level-wise distinction between value functions. If you formulate all the value function, and define a specific learning rule I am sure it would make this point much clearer. \n\n2. Experimental section: \nAll experiments: please define the state and action spaces in each domain (since this is what \\pi_p and SAC predict), and if they have some real-world interpretation that would be helpful. Please consider adding more subgoal visualization that demonstrate that the subgoals themselves are meaningful (for the test agent) for solving the ant and walker (and not just a useful way to generate a curriculum for training the agent).\nTo further show planning subgoals in test time make sense, could you compare (1) SAC (no co-pilot at all), (2) co pilot (full), (3) SAC (co-pilot during train only, during test the agent that trained via subgoals sees the final goal only). If (2) is better than (3), it would show that subgoals planning is an important feature even in test time. \n\nScenario specific comments:\n\nPoint robot maze - I don't understand the terms you use, what are obstacles states? what does the following mean \"the design of the benchmark refer to figure 2\" (should be figure 4 right?)\nHow many train and test trajectories are you left with after rejection sampling? In your test set, are you sure you have challenging start-goal pairs (this question actually applies to all scenarios)?\n\nAnt maze - same comments as the point robot, also:\nwhat are the 8 dimensions? I assume these include the joint angles and the center of mass, and if so, does \\pi_p predict only the (x,y,z) center of mass or also the joints? one fundamental problem in many subgoal papers is the generation of accurate \\ meaningful subgoals. If you predict joint angles, how do you evaluate that the produced subgoal makes sense (not necessarily by using the proxy of how well the system acts as a whole)? If you only predict subgoals as (x,y,z) states, then this means that the subgoal generation here is not more difficult than the point robot case. It does mean that the control (SAC policy) has a harder job, and *it is* interesting that you manage to train despite the additional control difficulty. However, none of your textual description actually goes into a deep analysis of this (and I think that since this paper is very experimental, this section should be more elaborate than it is right now).\n\nWalker (not bipedal since you have 4 legs according to the figure) - \nIf I understand correctly, the contribution of this scenario is showing that co-pilot can improve dense-reward scenarios, right? but why does it make sense to do subgoal planning here (or APSP for that matter)? what are the subgoals?\nAlso the state here is very unclear - does it include the sensor readings? Does \\pi_p imagine future sensor readings? Does it make sense to do so?How does not having global information (like you had in the mazes) impact the agent (you don't know what is going to come up next)?\n\nGeneral experimental issues:\n(1) you seed co-pilot dataset with 50K tuples of data, don't you need to add an equivalent amount of data to the baselines?\n(2) Please if possible compare against MuZero, and Hierarchical Actor-Critic.\n(3) After reading Eq.6, Algorithm 2, and section 4.2 multiple times, I have to say that the details in Algorithm 2 are not clear, you can either treat every segment independently (Algo2) or not (Eq.6 and section 4.2). Please provide a clearer explanation. \n(4) Re Euclidean reward: an ablation of how much the system is impacted if the subgoals costs ($c$) remains the Euclidean distance could show how the planner depends on the SAC agent for learning. Moreover, since the state in walker is not really applicable to the Euclidean distance, how much does the system improve when the dependence on the SAC agent becomes large? \n\nMinor concerns \\ fixes:\n1. Figure 1 should contain a better textual explanation of what is in the figure.\n2. Can you clarify the sentence in the related work regarding MuZero? MuZero does not require a pre-trained policy, and the planning computation improves in tandem with the policy (much like your work...) and the value function. Improving the value function can be thus seen as improving the planner (as it is used in test time during MCTS planning only). It will also be interesting to see this as a baseline (if possible). The code was released https://github.com/google-research/google-research/tree/master/muzero\n3. Problem formulation section - minor edits: \n(1) You did not specify the random variable R_0. \n(2) As you are working with SAC, please change the notation of the MDP and policy to indicate a stochastic policy. \n(3) In your paper you assume APSP, thus it will be good to emphasize that the state space is large. I also think that implicitly you also assume a continuous action space (since you want the \"agility\" to reach a set of continuous states).\n4. Section 3.2 - what do you mean by closing the loop? you didn't describe the algorithm of how to select and train the subgoals predictors!\n5. Algorithm 2: I think you are missing either \"s_0 \\leftarrow s_\\tau \" (consider the current state s_0) or set s_0 to the next subgoal in line 17. As you say that you need to start state to match the origin-subgoal.\n6. Where do you use reward \\bar{r}? (mentioned in eq. 6) I see that the RL agent sequentially trains between subsequent subgoals.\n7. Figure 4 - what is the snake robot? it is not in the description... \n\nGeneral comment - the writing \\ grammar in this paper could be improved. It was hard reading some sentences, and required corrections were too frequent for me to send a list of edits. Of course, I do not take this into account for my acceptance decision, but in case you want to improve the manuscript, please consider improving this aspect of the paper to make it more accessible... Also, please refrain from submitting manuscripts where *the text is not interactive*, it makes reviewing even harder, and this is part of the reason I couldn't efficiently list all grammar mistakes.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "B7MHtid3CLu", "reviewer": "Reviewer_SCqH", "summary": "The paper proposes a hierarchical algorithm for goal generation in goal-conditioned RL. Specifically, SGT from Jurgenson’20 is used to hierarchically produce a tree of subgoals with a subgoal policy, and a downstream goal-conditioned RL agent is trained on these subgoals instead of just the final goal. The subgoal policy is trained with a mix of a dense and a learned reward, while the downstream policy is trained with sparse reward.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "\n—— Decision ——-\n\nThe paper proposes a novel and interesting agent for hierarchical goal-conditioned learning. However, there are numerous issues with the current version of the paper.  Major baselines such as hindsight experience replay are missing from experimental evaluation, which are known to perform better on goal-conditioned RL than vanilla methods. More importantly, the proposed method leverages Euclidean dense reward while competing methods only observe sparse reward, making the experimental evaluation inconclusive. There are also technical issues with the proposed method and clarity issues.\n\n—— Update ———\n\nAuthors' response creates numerous new questions about the method validity. In particular, it appears there are many algorithmic choices that are not specified in the paper, and are problematic in terms of technical validity. None of the issues I raised in the review are addressed. The response convinces me this paper needs an additional significant amount of work before it can be accepted.\n\n—— Review ———\n\nA major issue with the experimental evaluation is that the method is not compared to the baselines fairly. Section 3.2 explains how the method provides a dense signal to the goal-conditioned policy that would otherwise be trained with a sparse 0/1 reward. However, the proposed method in fact uses a dense Euclidean reward to train the subgoal policy shown in Eq 12. Since the method sees the dense reward, training the subgoal policy is much easier than for other approaches that only see a sparse reward. In App fig 6, an evaluation is provided where the dense reward is removed and the proposed method only sees a sparse reward. In this evaluation, the method is inferior to prior work such as SoRB. How can the proposed method address the sparse reward problem in goal-conditioned RL without using euclidean reward?\n\nThere is also a number of technical issues with the proposed method. \n1. The method does not appear to use hindsight relabeling. Hindsight relabeling (Andrychowicz’17) generally significantly improves performance of goal-conditioned agents, especially with sparse rewards, and is used uniformly in most recent work. Why is it not used?\n2. At l217, The paper uses a “monotonic hyperbolic model” to predict the navigation cost c(g, g’). What is a monotonic hyperbolic model? How is it used to predict the cost?\n3. The proposed method for training the sub-goal policy encourages is to output subgoals for which the total pairwise cost is low. However, not all robot states are actually valid e.g. in environments with obstacles or configuration space constraints (such as all environments in this paper). How does the method ensure that the subgoal policy outputs valid states? This is unclear from the paper. More generally, while the policy gradient in Eq 10 is correct, the evaluated cost c(g,g’) needs to output correct costs for all possible goals, including the invalid or the unreachable ones. How is this ensured? \n\nFinally, the paper suffers from numerous writing issues and grammatical mistakes. \n\n—— Additional Comments ——\n\n4. The neurips submission rules (https://media.neurips.cc/Conferences/NeurIPS2021/Styles/neurips_2021.pdf) clearly state that the title should be in “initial caps/lower case”, not in lower case with some letters arbitrarily capitalized.\n5. l616, “We claim that the hyperparameter used in the ablation study is the same as the original in CO-PILOT”. Is it actually the same or is this only a claim?\n\nAndrychowicz’17, Hindsight experience replay", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nLimitations and societal impact are addressed adequately.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an interesting idea, and the reviewers agreed that it has potential. Unfortunately, all reviewers agreed that the writing of the paper is not clear enough, and the comparison to baselines needs to be improved. I recommend the authors to fix these issues and resubmit.
Decision: Accept (Poster)