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. edu,
gguodong.lorts jing- jiang] pang)@utss suttuus.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.coSShuaaaaaa 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 baaeid search heuristics can build a graph with better ppploratioo-explotttiii 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 Goal-relag 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 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
inttiriitinng.. 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*(s(g) (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 We will
( s(44yyr/2)) along the trajectory, i.e.,e (s/ A Ei'n" e 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)/s0))) g) Fy
(10)
To form an easy-to-hard curriculum for training Tp. during the top-down construction of the tree, at 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, (taalls.,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,220 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": "ixuRyu8Zz7M", "reviewer": "Reviewer_8yHH", "summary": "This paper addresses the problem of sequential decision making in complex, high-dimensional domains. The paper combines a learned planning policy and a learned controller to improve the performance of both. Explicit plans are used as reward shaping for the goal-conditions reinforcement learner to improve the learning rate, and the cost of the learned controller policy (“the time steps of the agent to finish a sub-task”) is used to learn a planning policy. The overall approach is compared to planning-only approaches, model-free policy learning, and a previous hybrid technique (SoRB) and the evaluation is on 3 different benchmark problems. CO-PILOT performs the best of the different techniques in both asymptotic performance and speed of learning. In some cases SoRB also has similar asymptotic performance, but requires more data and takes longer to converge to that. \n", "questions": "", "limitations": "", "rating": 6, "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": "This paper proposes an interesting idea. The core insight that “planning at even a coarse level can be used for reward shaping and substantially improves RL on long-horizon tasks with sparse reward” is not especially novel and would seem to be central insight of a considerable body of work in hierarchical abstractions for sequential decision making. However, the idea that the planner and learner provide training signals to each other is interesting and potentially novel. I am moderately predisposed to recommend this paper for acceptance, but it is hard to argue strongly for it, in that the narrative is really not clearly articulated, and the experiments could still use further improvement. \n\nMy primary concern is that the paper is sitting in a *very* crowded intersection of competing ideas, and does not really engage with the substantial literature in learning hierarchical abstractions. There are some references, so the authors seem to know about some work in hierarchical abstractions, although many more should be added, such as recent work by Konidaris (“From Skills to Symbols”, 2018) and older work such as Pineau et al (“Policy-contingent abstraction for robust robot control”, 2003), Michini and How (““Bayesian nonparametric inverse reinforcement learning”, 2012) and Surana and Srivastava (“Bayesian nonparametric inverse reinforcement learning for switched markov decision processes”, 2014). That being said, more experimental baseline comparisons are essentially, especially to hierarchical representations. \n\nAdditionally, the paper needs to more strongly articulate what is different about their approach, and what specific benefits are enabled. For instance, what if the learner were replaced with a fixed set of motion primitives? Figure 4 might suggest that the algorithm is just learning a sampling distribution, and a comparison to “Learning Sampling Distributions for Robot Motion Planning” (Ichter et al, 2018) would be appropriate, especially if learning the controller inside the planning loop really does add something. \n\nThe experimental results are ok, but a great deal of the motivation for this technique comes from high-dimensional and long-range planning problems. The Maze and Mujoco Ant-v1 are neither high-dimensional nor long-range (8 dimensions is not high dimensional). Bipedal-Walker is better, but not an especially hard planning problem. I would recommend substantially expanding the scale and dimensional of a Maze-like environment to really show the algorithm learning smart planning strategies and smart controllers.  \n\nThe paper contains some statements and assumptions about planning that are not quite right. \n- “Moreover, planning every step on the path is as difficult as the original RL and requires fine-grained discretization impractical for high-dimensional states.” — a fine-grained discretization is not necessarily required even for high-dimensional states, and random sampling techniques go a long way towards addressing this. Note that random sampling planners are not the same thing as sampling-based search heuristics. \n- “Planning only a few milestone states leaves the RL agent to solve relatively long-horizon sub-tasks.” This may be true, but those relatively long-horizon sub-tasks may be extremely easy to solve.  \n- “Although sampling-based search heuristics can build a graph with a better exploration-exploitation trade-off, they are not optimized for the RL policy, and the graph cannot be shared across tasks.” This is also not true — multi-query planning techniques such as the probabilistic roadmap are explicitly designed for re-use.\n\nI see the comment that this is a resubmission of a previous paper. I appreciate that the authors have gone to the trouble of reporting that, and the changes they made. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I could not identify a clear statement of the limitations of the paper anywhere in the paper. The word “limitation” does not appear in the paper. It is possible that the authors intended that the trade-offs between ease of learning vs complexity of planning as a function of sub-task tree depth (section 4.3, final paragraph) to be an assessment of the limitations, but this is not particularly useful, and is not a statement of the limitation of the technique — what would be more useful is analysis of the kinds of problems where the technique fails. Under what conditions is the planner unable to guide the learner, and another technique should be used? \n\nThe author checklist indicated that the authors did not discuss any potential negative societal impacts of the work. \n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 hours"}, "extra_text": {}}, {"review_id": "hudd1B2iTgI", "reviewer": "Reviewer_Fa86", "summary": "This paper presents CO-PILOT, a collaborative learning approach in which a planner, generating subtasks of varying complexity, and RL policy, learning to achieve those sub-tasks, are trained together through a curriculum of tree-structured subtasks. This simultaneous curriculum-based training helps to learn functions that can solve a variety of tasks in cluttered environments. ", "questions": "", "limitations": "", "rating": 6, "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": " The paper is well written, and most key aspects of their algorithm are neatly discussed. However, there are some concerns, and some of them can be addressed in the revised version.\n\n\n1- Related work can be improved:\n- Difference between HRL and CO-PILOT should be further explained. The main difference is that the latter introduces a tree-based curriculum for training high and low-level policies, leading to better performance than existing HRL methods.\n\n- Although I see this approach is different from imitation learning-based path planning approaches, including them in the literature would be nice. \n\n2- Methods:\n- Fig 1(b) can be described in a bit more detail in the caption.\n\n3- Results:\n- Generalization of their approach to different start and goals is not shown. For instance, in the maze, I think 100 (s,g) test pairs should be shown in the appendix to indicate how these samples were distributed, likewise for other environments. In the visuals, it seems the start and goal points were not quite distributed around the space. \n\n- Computational times of different algorithms during execution/testing should be compared, or at least they should be discussed in the paper. \n\n- Also, it is not clear why RRT* has a lower success rate than CO-PILOT. I believe the presented problems are simple enough for RRT* to solve them. Is it due to the time limit?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- Limitations of their work need to be highlighted, especially generalization to new environments and how it can be addressed. \n- Societal impacts: (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": "btcoiAWuGk1", "reviewer": "Reviewer_qKpT", "summary": "**Summary:** This paper proposes CO-PILOT that can improve performance in goal-conditioned RL settings. The main contribution of CO-PILOT is the collaborative learning between the planning and RL agents: the planning agent generates the sub-task tree providing dense feedback for the RL agent to solve a task, while the RL agent collects data and refines the cost function for the planning agent. Appealing benefits of CO-PILOT include 1) the auto-generated curriculum that helps training both the planning and RL agents, and 2) no requirements of a pre-trained policy, a heuristic for the cost function, and an accurate environment model. Empirical results show that CO-PILOT outperforms RL, planning, and mixed baselines in various domains.", "questions": "", "limitations": "", "rating": 6, "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": "**Reasons for Score:** Overall, I vote for a score of 6. While CO-PILOT provides an interesting insight (i.e., the mutual boosting between RL and planning) and shows positive evaluation results, there are several concerns and questions that I would like to clarify (please refer to Concerns and Questions below). After reading the authors' responses to my concerns, I am open to raising my score.\n\n**Strengths:**\n1. The paper is well written and motivates the main insight very well.\n2. The approach is principled. In particular, the paper introduces the interesting idea of auto-generated curriculums for the planning agent (top-down) and RL agent (bottom-up) to stable learn these policies. \n\n**Concerns and Questions:** \n1. Novelty is limited because CO-PILOT shares many similarities to the sub-goal tree method [24], except for the additional learning of the RL agent. \n2. While the result in Figure 2a show CO-PILOT outperforms the sub-goal tree baseline (SGTPG), it is unclear from the result discussion in Section 4.3 how CO-PILOT achieved this result. It will be helpful to include a discussion on what algorithmic difference resulted in better performance.\n3. Did the simultaneous learning of planning and RL agents result in a non-stationarity issue? For example, in [37], the simultaneous learning of both low and high-level policies created a non-stationary problem and they addressed the issue in an off-policy learning setting. \n4. Many planning methods have important properties, such as asymptotic optimality, probabilistic completeness, and monotone convergence (Karaman and Frazzoli, 2011). Does the planning agent in CO-PILOT also maintain these properties?\n5. One main benefit of CO-PILOT is the curriculum learning for the planning/RL agents. This benefit is also presented in the hindsight experience replay (HER) approach [3], where the goals used for replay naturally shift from simple to difficult ones. While it is not needed to compare against HER during the rebuttal period, it would be helpful to include the comparison against HER in the future. \n\n**Additional Feedback:**\n1. Similar to having $\\pi$ as a superscript in the Q-function $Q^{\\pi}$ (denoting the agent follows $\\pi$ in the future states), it will be helpful to denote the value function as $V^{\\pi}$ instead of $V$. \n2. It will be helpful to add variances in some results: Figures 2a, 2c, 4a, 4b, 4c. \n3. It will be helpful to clarify whether the results (e.g., Figure 2a) are from training or testing pairs.\n4. Figure 1 is not discussed in the introduction, so it would be better to place the figure where it is referenced (Section 3.3). Additionally, Figure 1b is not referenced in the text.   \n5. The current pdf format does not support search (i.e., ctrl + f) (tried on Linux and Mac). It was difficult to find a specific keyword in the paper, so I hope this issue is fixed. This might be not an issue with other computers. \n\n**Reference:**\nSertac Karaman and Emilio Frazzoli. Sampling-based Algorithms for Optimal Motion Planning. International Journal of Robotics Research (IJRR), 2011.\n\n**Post-Rebuttal:** Please refer to the review below. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper does not discuss any potential negative societal impacts. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "4roEj7V4S8h", "reviewer": "Reviewer_NJTw", "summary": "This paper discusses how planning and goal-conditioned RL can be combined for long-horizon planning. The method proposes to use a recursive subgoal generating policy, which is applied repeatedly at k levels to create 2^k subgoals. A lower level goal-conditioned policy attempts to reach the subgoals. The objective for the higher-level policy depends on the lower-level policy by estimating the time it takes the lower-policy to go between a state and goal. The paper shows that the method outperforms planning methods (NEXT, RRT, SGTPG), RL methods (SAC, PPO) and hybrids (SoRB, HRL). Generally the paper is well-written and communicates effectively idea that each module can assist the other in these hybrid planning/GCRL methods. However, it is not fully clear to me yet from the experiments which design decisions were important, and the method is also only evaluated on relatively simple tasks.", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes CO-PILOT, which introduces a recursive subgoal generating policy to make reaching far-away goals easier for a goal-conditioned policy. The claim is that the higher level policy assists the lower level policy by generating closer goals (standard HRL), but the lower level policy also assists the higher level policy by informing the cost function between states, which gets more accurate with a higher quality low-level policy as better data is collected.\n\nMethod: the writing is relatively clear. There is something cyclic going on that I didn’t understand in the top-down planning/algorithm 1. c is defined in terms of tau; tau is defined in terms of c_phi; c_phi is optimized … how? what is the objective? From algorithm 1 it seems like it depends on c. Is there a “grounded” cost that the whole system actually optimizes (does it come from alpha being 1 in eqn 12 so it is L2 distance)?\n\nExperiments: The experiments show that CO-PILOT outperforms all other classes of methods: planning methods (NEXT, RRT, SGTPG), RL methods (SAC, PPO) and hybrids (SoRB, HRL). In section 4.4, additional visualization on a 2D maze shows the CO-PILOT learning process, splitting a goal into subgoals and improving the policy between subgoals. However, on this task, other methods are just as good; a more helpful visualization would be to understand why other methods fail on harder tasks while CO-PILOT does not. Perhaps a similar visualization can be constructed for something like Ant (still plotting on a 2D maze by accessing the underlying state information).\n\nGenerally, the paper proposes a large system of learning a cost function, a planner/subgoal generator, and a goal-conditioned policy. It is difficult to parse from the writing and results which component matters in the end, although the experiments are relatively thorough and may have the answer already. Some questions are: if SGTPT performs similarly to CO-PILOT, does this mean the goal-conditioned reward feedback to the planner does not matter (or what is the delta between the two)? The planner incorporates L2 reward, while the maze tasks are sparse reward; what if the L2 heuristic was used for SAC as the cost instead of sparse rewards?\n\nTasks: the paper evaluates on a few different domains, but one criticism is that the domains are all either maze tasks from state (2D, 3D, 5D, and ant maze locomotion) or simple (BipedalWalker). In contrast, there exists several works now that have shown the ability to do goal-conditioned planning in visual domains, including SoRB (cited and compared in this work, but not in visual domains), [2], [4].\n\nThe related work is relatively complete in terms of discussing goal-conditioned RL and planning. I did not quite understand how c_phi is optimized but it looks a lot like dynamical distance learning [1]. Also consider discussing [2] and [3] which explore subgoal generation, especially [2] which generates subgoals by divide-and-conquer exactly like this paper does.\n\n[1] Dynamical distance learning for unsupervised and semi-supervised skill discovery. Hartikainen 2019.\n[2] Long-Horizon Visual Planning with Goal-Conditioned Hierarchical Predictors. Pertsch 2020.\n[3] Automatic Goal Generation for Reinforcement Learning Agents. Florensa 2018.\n[4] ViNG: Learning Open-World Navigation with Visual Goals. Shah 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and societal impact are not really discussed. For limitations, it would be good to see a task where CO-PILOT fails or at least struggles to solve completely.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers' appreciate the interesting ideas in this submission and the generally clear presentation, and the authors detailed responses to the reviewers' concerns. The authors are encouraged to revise their camera ready to address the feedback from the reviewers. 
Decision: Accept (Poster)