C-Planning: An Automatic Curriculum for Learning Goal-Reaching Tasks
Authors: Tianjun Zhang
Benjamin Eysenbach
Ruslan Salakhutdinov
Sergey Levine
Joseph E. Gonzalez
Venue: ICLR 2022 Poster (2022)
Keywords: reinforcement learning
planning
variational inference
curriculum learning
waypoints
subgoals

Abstract: Goal-conditioned reinforcement learning (RL) has shown great success recently at solving a wide range of tasks(e.g., navigation, robotic manipulation). However, learning to reach distant goals remains a central challenge to the field, and the task is particularly hard without any offline data, expert demonstrations, and reward shaping. In this paper, we propose to solve the distant goal-reaching task by using search at training time to generate a curriculum of intermediate states.  Specifically, we introduce the algorithm Classifier-Planning (C-Planning) by framing the learning of the goal-conditioned policies as variational inference. C-Planning naturally follows expectation maximization (EM): the E-step corresponds to planning an optimal sequence of waypoints using graph search, while the M-step aims to learn a goal-conditioned policy to reach those waypoints. One essential difficulty of designing such an algorithm is accurately modeling the distribution over way-points to sample from. In C-Planning, we propose to sample the waypoints using contrastive methods to learn a value function. Unlike prior methods that combine goal-conditioned RL with graph search, ours performs search only during training and not testing, significantly decreasing the compute costs of deploying the learned policy.  Empirically,  we demonstrate that our method not only improves the sample efficiency of prior methods but also successfully solves temporally extended navigation and manipulation tasks,  where prior goal-conditioned RL methods (including those based on graph search) fail to solve.

Published as a conference paper at ICLR 2022
C-PLANNING: AN AUTOMATIC CURRICULUM FOR LEARNING GOAL-REACHING TASKS
Tianjun Zhang*
Benjamin Eysenbach"
UC Berkeley t cianjunzbeerkeleyy.eo
Carnegie Mellon University
beysenba@c: easeenaaass..... cmu .dd:
Ruslan Salakhutdinov Cameegi Mellon University
Sergey Levine UC Berkeley
Joseph E. Gonzalez
UC Berkeley
ABSTRACT
Goal-conditioned reinforcement learning (RL) can solve tasks in wide range domains, including navigation and manipulation, but learning to reach distant goals remains central challenge to the field. Learning to reach such goals is par- ticularly hard without any offline data, expert demonstrations, and reward shap- ing. In this paper, we propose an algorithm to solve the distant goal-reaching task by using planning at training time to automatically generate a curriculum intermediate states. Our algorithm, Classifier-Plann learning of the goal-conditioned policies as expectation maximization: the E-step corresponds planning sequence of waypoints using graph planning, while the M-step aims to learn a goal-conditioned policy to reach those waypoints. Un- like prior methods that combine goal-conditioned RL with graph search, ours per- forms planning only during training and not testing, significantly decreasing the compute costs of deploying the learned policy. Empirically, we demonstrate that our method is more sample efficient that prior methods. Moreover, it is able to solve very long horizons manipulation and navigation tasks, tasks that prior goal- conditioned methods and methods based on graph search fail to solve.
(C-Planning), frames the
INTRODUCTION
Whereas typical RI. methods maximize the accumulated reward, goal-conditioned RL methods learn to reach any goal. Arguably, many tasks are more easily defined as goal-reaching problems than as reward maximizing problems. While many goal-conditioned RL algorithms learn policies that can reach nearby goals, learning to reach distant goals remains challenging problem. Some prior methods approach this problem by performing search or optimization over subgoals at test time. However, these test-time planning methods either rely graph search (Eysenbach Savinov et al. 2018), which scales poorly with dimensionality (Hsu et al., (2066), or continuous optimization over subgoals (Nasiriany et al. 2019). which expensive and can result in model exploitation.
al., 2019;
In this paper, we take different tack and instead use planning at training time automatically generate a curriculum. When training the agent to reach one goal, our method first determines some intermediate waypoints enroute to that goal. Then, commands the agent reach those waypoints before navigating to the final destination. Collecting data in this manner improves the quality of data, allowing the agent to learn reach distant goals. Importantly, our method does not perform planning at test time, decreasing the computational demands for deploying the learned agent.
Our curriculum does not require manual engineering or prior knowledge of the tasks. Rather, the cur- riculum emerges automatically when we use expectation maximization (EM) to maximize lower bound on the probability of reaching the goal. The M-step corresponds to a prior method for goal- conditioned RL, while the E-step corresponds to graph planning. Thus, EM presents marriage between previous goal-conditioned RL algorithms and graph-planning methods.
"Equal contribution.

---

Published as a conference paper at ICLR 2022
Figure I: C-Planning is an algorithm for goal-conditiones RL that uses an automatic curriculum of waypoints to learn policies that solve complex tasks. In this manipulation task, the goal requires moving the green puck to the green dot and the red puck to the red dot. Our method learns to solve this task, manipulating multiple objects in sequence, without requiring any reward functions, manual distance functions, or human demonstrations.
The main contribution of this work is a goal-conditioned RL algorithm, C-Planning, that excels at reaching distant goals. Our method uses automatic curriculum of subgoals to accelerate training. The automatic waypoint sampling ends up generating a curriculum of waypoints, points that are reachable by the current policy but also lead to the goal. We show that our curriculum emerges from applying variational inference to the goal-reaching problem. Unlike prior work, our method does not require graph search optimization at test-time. Empirically, C-Planning not only matches but sur- passes the performance of these prior search-based methods, suggesting that it is not just amortizing the cost of graph search. We empirically evaluate C-Planning on remporally-extended 2D navigation tasks and complex 18D robotic manipulation tasks. C-Planning improves the sample efficiency of prior goal-conditioned RL algorithms and manages solve more difficult manipulations tasks such as rearranging multiple objects in sequence (see Fig. Fig. To the best of our knowledge, no prior method has learned tasks of such difficulty without requiring additional assumptions.
RELATED WORK
The problem of learning to achieve goals has long history, both in the control community Lyapunov (1992) and the RL community (Kaclbling] 1993). Many prior papers approach goal-conditioned RL as reward-driven multi-task learning problem, assuming access to a goal-conditioned reward func- tion. One unique feature of coal-conditioned RI, compared to other multi-task RL settings, is that it can also be approached using reward- free methods, such as goal-conee conditiond behavior cloning (Ding) et al. 2019 Gupta et al. 2020 Lynch et al. 2020; (Savinov et al. 2018) and RL methods that employ hindsight relabeling (Eysenbach et al. 2020; Kaelbling 1993] Lin et al. 2019) [ccrreekker Isbell] 2020). While goal-conditioned behavior cloning methods simple to implement and have shown excellent results on a number of real-world settings (Meng et al., 2020 Shah et al. (2020), they are not guaranteed recover the optimal policy without additional assumptions (e.g., determinism, on- line data collection). While both methods excel at certain control tasks, both often struggle to solve tasks with longer horizons.
To solve longer-horizon tasks, prior work has combined goal-conditioned RL with graph search, noting that goal-conditioned value functions can be interpreted as dynamical distances (Eysenbach) et al. 2018, Huang et al. 2019 Nasiriany et al. 2019 Savinov et al. 2018). These prior methods typically proceed in two phases: the first phase learns a goal-conditioned policy, and the second phase combines that policy with graph search. While these methods have demonstrated excellent results on a number of challenging control tasks, including real-world robotic navigation (Meng et al. 20200] (Shah et al., (220)) the stage- wise approach has few limitations. First, the post- hoc use of graph search means that graph search cannot improve the underlying goal-conditioned policy. It is well known that the performance of RL algorithms is highly dependent on the quality of the collected data (Kakade & Langford| 2002 Kumar et al., 2020 Levine et al.] 2020). By integrating planning into the learning of the underlying goal-cond policy,
method will improve the quality of the data used to train that policy. A second limitation of these prior methods is the cost of deployment: choosing actions using graph search requires least ((V)) queries to a neural network]" In contrast, our method performs planning at training time rather than test time, so the cost of deployment complexity of training. it significantly decreases the latency at deployment. Our method is similar to RIS (Chane-Same Sane-SSneee et al. (021), which also performs planning during training instead of deployment. Our method differs from RIS in how planning is used: whereas RIS modify the objective, our method
(1). While this design decision does increase the computational
While computing all pairwise distances requires (( time, only [V] edges change at each time step.
The cost of computing the remaining edges be amortized across time.
2

---

Published as a conference paper at ICLR 2022
uses planning to modify the data. This difference not only unifies the objectives for RL and graph planning. but also significantly improves the performance of the algorithm. a subtle distinction that avoids favoring the learned policy and unifies the objectives for RL and graph planning. We demonstrate the importance of this difference in our experiments.
Effectively solving goal-conditioned RL problems requires performing good exploration. In the goal-conditioned setting, the quality of exploration depends on how goals are sampled, a problem studied in many prior methods (Bysenbach et al. 20018; Florensa al., 2017: 2018 Pitis et al.) 2020 Pong et al., 2020; Ren et al., 2019 Zhang et al. 2020, 2021). These methods craft objectives that try to optimize for learning progress, and the resulting algorithms achieve good results across a range of environments, Our method differs from these methods in that the method for optimizing the soal-conditioned policy and the method for sampling waypoints are jointly optimized using the same objective. We demonstrate the importance of this difference in our experiments.
Our approaches can also be viewed as one Hierarchical RL. (Dietterich, 2000; Levy et al. 2017 Vezhnevets et al., 2017) method with the distance function specified by the classifier. However, one important difference between C-Planning and many other HRL methods is that our approach doesn't require training high-level policy for generating subgoals for the lower-level policy to reach (Gupta et al., 2020 Levy et al., 2017 Nachum et al. 2018). Comparing with approaches try to build graph/tree for planning (Eysenbach et al.) [2019] Huang et al. (019 Nasiriany et al. 2019) our approach doesn't 't require any planning at deployment, saves a lot of computation time.
Our method builds on the idea that reinforcement learning be cast inference problems (Attias 2003 Levine 2018 Rawlik et al. [013] Theodorou et al. 2010): Todorov] [2007] [Ziebart] (011)). The observation that variational inference for certain problems corresponds to graph planning is closely
related to Attias (2003). Our work extends this inferential perspective to hierarchical models.
3 PRELIMINARIES
We introduce the goal-conditioned RL problem and a recent goal-conditioned RL algorithm, C- learning, upon which our method builds.
Goal-Conditioned RL. We focus on controlled Markov processes defined by states st E S and actions az. The initial state is sampled so Po(()) and subsequent states are sampled 8141 ~ p(8:41 (8, az). Our aim to navigate to the goal states, 8g E S, which are sampled from 8, ~ (gg) We define policy T(a 82, 8g) conditioned on both the current state and the goal. The objective is to maximize the probability (density) of reaching the goal in the future.
To derive our method, or any other goal-conditioned RL algorithm, we must make modeling assumption about when we would like the agent to reach the goal. This modeling assumption is only used to derive the algorithm. not for evaluation. Formally, let A E N+ be a random integer indicating when we reach the goal. The user specifies a prior p(A). Most prior work (implicitly) -)) 7). The geometric distribution is ubiquitous because it is easy to incorporate into temporal difference learning. Despite its wide usage, it may not reflect the prior belief on when the agent will solve the task or when the episode will terminate. Thus, while it is natural to use geometric distribution, other choices of distributions can also be consdiered. Prior work has also considered non- non- gen--eemmtric distributions (Fedus et al. 2019). In this paper, we use the negative binomial distribution, p( A) = NEGBINOM(p = Y. 2). Given a prior p(A), we define the distribution over future states as
uses the geometric distribution, p( () = GEOM(1
Pp(A)
x(- x(>-))))
(sLt s $t a.) = EA(a)
PA (S
Si+ st. an)
where PA (SL+ St, az) is the probability density of reaching state 81+4 exactly A steps in the future when sampling actions from .T at 8,)) For example, the 7-discounted state occupancy
measure (Ho & Ermon 2016 Nachum et al. 2019) can be written as PG Our objective for
=(11-8))
goal-reaching is to maximize the probability of reaching the desired goal:
x((1-,g)) (NaeBBnox((p11100=)))) (st+ = =8g]
max (pp,)
(2)
C-Learning, Our method builds upon a prior method for goal-conditioned RL, C-Learning (Ey- senbach et al. 2020). C-Learning learns classifier for predicting whether state 8, comes from
3

---

Published as a conference paper at ICLR 2022
future state density a(11100) (814 814 81, at)) marginal state density: Pp(A]
m(11,8)) Pp(A) (s (sL- =8+)
x(11-,9)) PP(A)
(51+ = sc+ Sc. az) p(st, az) ds, dag.
The Bayes-optimal classifier can be written in terms of these two distributions:
a(-1-185) PGROM
(8,
Co 88)
x(-1-1a)
(8g 8) PGROM ($g)
x(-1-18a) (())))))ss,)
PGEOM
In C-Learning, this classifier acts as value function for training the policy. Our method will use this classifier not only to update the policy, but also sample waypoints.
C-PLANNING: GOAL-CONDTIONND RL WITH PLANNING
We now present our method, C-Planning. The main idea behind our method is decompose the objective of Eq. 2 into sequence of easier goal-reaching problems. Intuitively, if want sub- optimal agent to navigate from some initial state 8p to a distant goal state 8g. having the agent try to reach that state again and again will likely prove futile.
Instead, we can command sequence of goals, like trail of breadcrumbs leading to the goal 8g- To select these waypoints, will command the policy reach those states it would visit if it were successful reaching 8y. Sampling subgoals in this way can case the difficulty of training the agent.
At high-level algorithm summary, our method consists of two steps: using waypoing sampling to collect experience and performing standard goal-conditioned RL using the collected experience. The main challenge is the first step. as modeling the distribution over waypoints is difficult. In Sec. 1. we solve analytically for waypoint distribution, and then propose a simple practical method sample from this distribution in Sec. 4.2
4.1 PLANNING AND VARIATIONAL INFERENCE
To formally derive our method for waypoint sampling, we cast the problem of goal-reaching latent variable problem. We assume that the agent starts state 8n and ends at state 8g. but the intermediate states that the agent will visit are unknown latent variables. This problem resembles standard latent variable modeling problems (c.g., VAE), where the intermediate state serves the role of the inferred representation. We can thus derive evidence lower bound on the likelihood of reaching the desired goal:
Lemma 1. The objective L, defined below, is lower bound on the goal-reaching objective (Eq. 2
+(-1-1g) log log (81+ = sy 80) 2 Egtawleg op) log Piaam
x(11-90) ($14 = s...) ) + log Peiooss (s.. sn)
-(-1--9))
-log q(s.. Sg. (g. A ((sw Sg. so)).
See Appendix A. for the proof. The lower bound, L, depends on two quantities: the goal- conditioned policy and inferred distribution waypoints, 7(8w Sp. 8g). This bound holds for any choice of q(sw 80, 8y), and we can optimize this lower bound with respect to this way- point distribution. We can see more intuition behind the negative binomial distribution here. With the negative binomial distribution, we can decompose hard problem into a sequence of easier RL problems. Each of these easier (goal-conditioned) RL problems uses geometric distributions, and the sum of geometric random variables is negative binomial distribution.
We will perform expectation maximization (Dempster et al. 1977) optimize the lower bound, alternating between estimating waypoint distribution and optimizing the goal-conditioned policy using this waypoint distribution. We now describe these two steps in detail.
Sp. Sp. sy). The three terms in the lower bound indicate that the sampled waypoint should reachable from the initial state, the goal state should be reachable from the sampled waypoint, and that the waypoint distribution should have
E-Step. The E-step estimates the waypoint distribution, q(sw
4

---

Published as a conference paper at ICLR 2022
high entropy. These first two terms resemble shortest pate planning, where distances measured using log probabilities. Importantly, reachability is defined in terms of the capabilities the current policy. We can analytically solve for the waypoint distribution:
Lemma 2. The waypoint distribution that optimizes our lower bound (Lemma) 7 satisfies:
(' 8y. 80)
PGEOM
(8g
8w PGEM
(sw
88))
J
PGEOM
(8g) s'y MuGGGo (ellse))) (s' 80)dd''
See Appendix A.I for full derivation. In general, accurately estimating the distribution, q", is challenging. However, in the next section, we develop a simple algorithm that only requires learning classifier instead of generative model.
M-step. The M-step optimizes the lower bound with respect to the goal-conditioned policy. We can ignore the log ( 80, 80,8g) 8g) term, which does not depend the policy. The remaining two terms look like goal-conditioned RI. objectives, with a subtle but important difference in how the trajectories are sampled. When collecting data, standard goal-conditioned RL algorithm initially samples a goal and then collects a trajectory where the policy attempts to reach that goal. Our method collects data in a different manner. The agent samples a goal, then samples an intermediate waypoint that should lead to that goal. The agent attempts to reach the waypoint before attempting to reach the goal. After the trajectory has been collected, the policy updates are the same as a standard goal-conditioned RL algorithm.
Two mental models. The algorithm sketch we have presented, which will be fleshed out in the subsequent section, can be interpreted in two ways. One interpretation is that the method per- forms a soft version graph planning during exploration, using a distance function of d(8), 82) =
x(-1-,82 (8t+ 82 s1). From this perspective, the method is similar to prior work that per- forms graph search during test-time (Eysenbach et al., 2019:; Savinov et al. 2018). However, our method will perform planning training time. Extensive ablations in Sec. 3 show that our method outperforms alternative approaches that only perform search during test-time.
log PGMOM
The second interpretation focuses the task of reaching the goal from different initial states. The choice of waypoint distribution, and the policy's 's success at reaching those waypoints, determines the initial state distribution for this task. Intuitively, the best initial state distribution is one that sometimes starts the agent at the true initial state 8g, sometimes starts the agent at the final state 8g- and sometimes starts the agent in between. In fact, prior work has formally shown that the optimal initial state distribution is the marginal state distribution of the optimal policy (Kakade & Langford 2002). Under somewhat strong assumptions/ this is precisely what our waypoint sampling achieves. We refer the reader for the discussion and experiments in Appendix. A
4.2 A PRACTICAL IMPLEMENTATION
We describe how we implement the policy updates (M-step) and waypoint sampling (E-step)- For policy updates, we simply apply C-learning (Eysenbach et al.) (020)_ The main challenge is waypoint sampling, which requires sampling a potentially high-dimensional waypoint distribution. While prior work (Florensa et al. 2018) has approached such problems by fitting high-capacity gen- erative models, our approach avoids such generative models and instead use importance sampling.
Let b(.) be the background distribution taking be the replay buffer. Our algorithm corresponds to the following two-step procedure. First, we sample a batch of waypoints from the buffer. Then, we sample one waypoint from within that batch using the normalized importance weights, g(s 16.80)
b(w))
We can estimate these importance weights using the classifier learned by C-learning (Eq. 3 Lemma 3. We can write the importance weights terms of this value function
s( w
Sy. So)
Co(Sw, Co Sw)
Z(so. 8y),
(4)
b(sw)
1 1 Ca sq) Co( sw)
where Z(So, 8y) normalizing constant.
"The assumptions are that (1) the policy always reaches the commanded waypoint, and that (2) that the <(-lee) reflect the probability that the optimal policy reach some state.
goal-reaching probabilities Po
5

---

Published as a conference paper at ICLR 2022
Algorithm C-Planning performs plan- ning in data collection, modifies C-learning by L5 - L6 7. The update for the policy and classifier (L9) is the same.
Algorithm C-Planning samples the intermediate way- points, then command the agent to reach them.
1: Ry number of waypoints agent has reached in episode
2: function CPLANNING(11g C, ky)
1: D 1-+0 0, Ng. Ed
3: it = 0 or d(st, 8w) S ed) and ng S N, then
2: for 0 S i S N do
4: Bg f- T2g +
3: Set n2 if new episode
5:
Sample M waypoints s ~ Buffer(s... Compute distances for each candidate waypoint:
4: #0 ~ po( 8q ~ Po (1))
6:
5:
(F S0) Sws ng & CPLANNING(H C,
log C[F=0)aw: C(F=1|Awsst) + log C(F=0 ep.ea))
C(F=1 "0.
6:
T (1 mmmpp pT
80; Sw)
7:
Sw x SOFIMAX(d
7:
8: else
T2 p~p (T Sws 8g)) D (T} + + (LLARNING(D,,,.))
9: Set 8g
8:
10:
return Bw, R2
9:
See Appendix /A.3 for full derivation. Since we will eventually normalize these importance weights (over Sw)) we do not need to estimate ((so, 8y)) We call our complete algorithm C-Planning, and summarize it in Alg. [ Note that our algorithm requires changing only a single line of pseudocode; during data collection, we command the agent to the intermediate waypoint 8w instead of the final goal $g. The sampling procedure in Alg. 2 is scalable and easy to implement.
The core idea of our method is to sample waypoints enroute to the goal. Of course, at some point must command the agent to directly reach the goal. We introduce a hyperparameter ny to indicate how many times resample the intermediate waypoint before commanding the agent reach the goal. This parameter is not the planning horizon, which is always set to 2.
5 EXPERIMENTS
Our experiments study whether C-Planning can compete with prior goal-conditioned RL methods both on benchmark tasks and on tasks designed to pose a significant planning and exploration chal- lenge. Our first experiments use these tasks compare C-Planning prior methods for goal- conditioned RL. We then study the importance of few design decisions through ablation exper- iments.The benefits of C-Planning, compared with prior methods, are especially pronounced on these tasks. To provide more intuition for why C-Planning outperforms prior goal-conditioned RL methods, we plot the gradient norm for the actor and critic, finding that C-Planning enjoys larger norm gradients for the critic and smaller variance of the gradient for the actor. Ablation experiments study the number of waypoints used in training. We measure the inference time of choosing actions, finding that C-Planning is up to 4.7x faster than prior methods that perform search at test time. F
Environments. We investigate environments of various difficulty (visualize in in Fig. 2 The first set of environments is taken from the Metaworld suite (Yu et al., 2020), common benchmark for goal-conditioned RL. These tasks are challenging because of the manipulation skills required to push and reorient objects. While prior goal- coul-conditioned RL methods do solve some of these tasks (e.g., Push and Reach), they stand at the edge of the capabilities of current methods. The second set of environments, 2D navigation mazes, are designed to stress-test the planning capabilities of different methods. Successfully solving these tasks requires reasoning over long horizons of up to 50 steps. These are challenging because, unlike many benchmarks, they require non non-greedy ex- ploration: greedy strategies get stuck in local optima. Our final set of environments combine the challenges of these environments. We extend the tasks in Metaworld to involve sequential manip- ulation of multiple objects, similar to the tasks in prior work (Singh et al., 2020). For example, the Obstacl eellee-Deee re-Drawer-Ci ose task require the robotic arm to manipulate multiple objects in sequence, first pushing an object and then opening drawer. These tasks are difficult because the agent is given no demonstrations, no reward shaping, and no manually specified distance metrics.
Baselines.
We will compare C-Planning to number of baselines. C-Learning is a recent goal- conditioned RL method that does not perform planning. C-Learning performs the same gradient
*Out code is available attpppps//ggaaaao.coo/raaannnnap

---

Published as a conference paper at ICLR 2022
Chhaningg
Cleamby
%
Se1DiG warting
Tal-Wel
Teach
0200
3 0.19
0.25
020-
0.335
6,75
035
0300
010
0075
R122
0050
02
041
86
6.3
166
0.0
82
04
86
5.3
Obsrarc Draver Choe
107
Parh-ee
0.20
1.20
1626
Be32
0.2
0.0
035
0200
5.00
D315-
0.50
2.8
3.0
Oivicenent
200
Stare
Figure 3: Comparison of goal-conditioned RL methods: We compare C-Planning to prior goal-conditioned RL algorithms various tasks: (top) benchmark manipulation tasks from Metaworld, (middle) 2D maze nav- igation, and (bottom) robot manipulation tasks that require long horizon planning. For cach task, we record the Euclidean distance to the goal, taking the minimum distance within episode. All but the easiest task (Reach), C-Planning outperforms all prior methods, including those that perform planning. Only C-Planning is able to solve the most challenging navigation and manipulation tasks.
updates as C-Planning, and only differs in how experience is collected. Comparing to C-Learning will allow us to identify the marginal contribution of our curriculum of waypoints. The second baseline is SoRB (Eysenbach et al. 2019), a goal-conditioned RL method that performs search at test-time, rather than training time. While SoRB was originally implemented using Q-learning, we find that version based C-learning worked substantially better, so we use this stronger baseline in our experiments. Comparing against SoRB will allow us to study the tradeoff's between performing planning during training versus testing. Because SoRB performs search at testing, it is considerably more expensive to deploy in terms of computing. Thus, even matching the performance of SoRB, without incurring the computational costs of deployment would be useful result. The third baseline an ablation of our method designed to resemble RIS (Chane-Sane et al.) 2021). Like C-Planning, RIS performs planning during training and not testing, but the planning used differently from C-Planning. Whereas C-Planning uses planning to collect data, leaving the gradient updates unchanged, RIS modifies the RL objective to include an additional term that resembles behavior cloning. Our comparison with RIS thus allows us to study how our method for using the sampled waypoints compares alternative methods learn from those same sampled waypoints.
5.1 COMPARISON WITH PRIOR GOAL- COAL-CONDITIONED RL METHODS
To compare C-Planning to prior goal-conditioned RL algorithms, we start with three tasks from the MetaWorld suite: Reach, Push, methods on the easiest task (Reach), we see a noticeable improvement over prior methods on the more challenging Push and Push-Wall tasks, tasks that require reasoning over longer horizons to solve. This observation suggests that that the waypoint sampling performed by C-Planning might be especially beneficial for solving tasks that require planning over long horizons.
While C-Planning learns slightly slower than prior
To test the planning capabilities of C-Planning, we design a series of 2D navigation mazes. While the underlying locomotion motions are simple, these tasks post challenges for planning and are designed so that a greedy planning algorithm would fail. On all three mazes, C-Planning learns faster than all baselines and achieves a lower asymptotic distance to the goal, as compared to the baselines. On the most challenging maze, Maze-1ixi1 1, only our method is able to make any learning progress. Of particular note is the comparison with SoRB, which uses the same underlying goal-conditioned RL algorithm as C-Planning, but differs in that performs search at testing, rather than training. While SoRB performs better than C-learning, which does not perform planning, SoRB consistently
7

---

Published as a conference paper at ICLR 2022
6113
0.30
833
0315
6150
632%
0650
03
02
1.6
00
82
04 3.
Crvieement
Dentemmanttee Stare
Figure 4: Planning at Training Versus Testing: ablate the number intermediate waypoints to reach the goal, and compare against a variant of our method that performs planning during both training and testing ("C-Planning SoRB"). This variant does not improve performance, indicating that the feedforward policy learned by C-Planning has already "internalized" these planning capabilities.
performs worse than C-Planning. This observation suggests that C-Planning is not just amortizing the cost of performing search. Rather, these results suggest that incorporating planning into training produce significantly larger gains than incorporating planning into the deployed policy.
As the last set experiments, study higher dimensional tasks that require long-range planning. We design three environ- H
ments: Obstacle-Drawerr-lloe dbstaclle-rraer-cclee and Push-Two.
Dbstacle-Drawer--ee
These tasks have fairly large dimension (15 to 18) and require sequential manipulation of multiple objects. C-Planning outperforms baselines on all three tasks. While C-learning makes some learning progress, SoRB (which modifies C-leaming with search at test time) does not improve the results. RIS, which also samples waypoints during training but those waypoints differently, does not make any learning progress these tasks. Taken together, these results suggest that waypoint sampling (as performed by C-Planning) can significantly aid in the solving of complex manipulation tasks, but only if that waypoint sampling is performed during training. Moreover, the comparison with RIS suggests that those waypoints should used to collect new data, rather than to augment the policy learning objective. To the best of our knowledge, C-Plamning the first method to learn manipulation behavior of this complexity without additional assumptions (such as dense rewards or demonstrations).
red poir part
pair and saah poon pais
pair and woohh groengnonnn
ISI Past-Wall faoit
puih
10 Obestaile Drawer Whoeer---ee sbjer to ned location
rnd lerin localic (gen)
Visualization of the 2D nav- igation maze environments (top row) and robotics ma- nipulation tasks (bottom row).
Figure 2: Euvironments:
5.2 WHY DOES C-PLANNING WORK?
We ran many additional experiments to understand why C-Planning works well. To start, run ablation experiments to answer two questions: (/) Although C-Planning only applies planning at training time, does additionally performing planning test time further improve performance? (2) How many times should we resample the waypoint before directing the agent to the goal?
F shows the results of ablation experiments. C-Planning performs the same test-time with and without SoRB-base B-ased planning, suggesting that our training-time planning procedure already makes the policy sufficiently capable of reaching distant goals, such that it does not benefit from additional test-time planning. Fig. also shows that C-Planning is relatively robust to ng. the number of waypoints used before directing the agent to the goal. For all choices of this hyperparameter, C- Planning still manages to solve all the tasks.
Gradient analysis. We provide an empirical observation why C-Planning is better than vanilla goal-conditioned RL methods. We hypothesize that, by introducing waypoints, C-Planning pro- vides a better learning signal, increasing the gradient norm for training the critic and decreasing the variance of the gradient for the policy. Prior work has theoretically analyzed the importance of gradient norms for RL (Agarwal et al.) (02T)) and we will provide some empirical evidence for the importance of controlling gradient norms. In addition, variance reduction has also long been
8

---

Published as a conference paper at ICLR 2022
Computation Cost for Test Time Search
0.202
C-lanniigg
5o6B (1)
Sunt
0433
(1.)
05.0
340
040
500
0.00
Pust-Wall
Push-Twn
Figure 6: Gradient Analysis and Computation Cost: (Left)) Mean and standard deviation the gradient norm for the actor and critic networks. C-Planning has larger critic gradient norm than C-L.eariing C- Planning shows a smaller variance comparing to C-Learning. (Right) Computation cost in latency C-Planning and SoRB with various number of waypoints.
core problem in RL (Anschel et al. 2017 Greensmith et al. 2004) and smaller variance will help stabilize the RL algorithm. In Fig. 6 we plot the norm of the gradient (mean and variance) of both C-Planning and C-Learning using the Maze- environment, finding that our method increases the norm of the critic norm and decreases the variance of the actor gradient norm.
Test-time latency. One important advantage of C- Planning is that it enables direct execution test time, does not require any online planning. At test time, we directly the agent's goal the final goal state with- out commanding any intermediate states. This makes C-Planning considerably different from previous plan- ning methods, such as SoRB (Eysenbach et al., (2019). Not only does our method achieve a higher return, but it does so with significantly less computing at deployment. We measure the execution time at evaluation time for C- Planning and SoRB with various number of waypoints Fig. 6 C-Planning
early training
end of training
Inaectiry
qual
waypoine
Intial state
Figure 5: Waypoint sampling: (Left) Early in training, the agent samples waypoints closer to the initial state. (Right) At convergence, waypoints dis- tributed along states visited by the opti- mal policy, predicted by theory.
1.74x faster than planning over four waypoints and 4.71 x faster than planning over 16 waypoints in Push-Wai Wall environment.
Visualizing the training dynamics. To further gain in- tuition into the mechanics of our method, we visualize how the distribution over waypoints changes during training of the 2D navigation of the four rooms environment. Fig. shows the sampled waypoints. The value functions (i.e., future state classifiers) are randomly initialized the start of training, so the waypoints sampled are roughly uniform over the state space. As training progresses. the distribution over waypoints converges to the states that an optimal policy would visit enroute to the goal. While we have only shown one goal here, our method trains the policy for reaching all goals. This set of experiments provides intuition of how C-Planning works as the distribution of waypoints shrinks from a uniform distribution to the single path connecting start state and goal state. This visualization is aligned with theory (Eq, 2), which says that the distribution of waypoints should resemble the states visited by the optimal policy.
CONCLUSION
In this paper, we introduced C-Planning, method for incorporating planning into the training of coal-conditioned agents. The method enables the automatic generation of a curriculum over inter- mediate waypoints. Unlike prior methods, our approach avoids the computational complexity of per- forming search at test time. C-Planning is simple to implement top of existing goal-conditioned RI. algorithms and achieves state-of-the-art results on a range navigation and manipulation tasks.
Our work suggests few directions for future work. First, C-Planning samples waypoint that cor- respond to the optimal state distribution, which proovably optimal in some settings (Kakade & Langford 2002). How might similar ideas be applied to reward-driven tasks? Second, while this paper studied sought to learn agents for reaching distant goals, we assumed that those distant goals provided as part of the task definition. conl-condi algorithms that propose their distant goals, while already studied in some prior work (Florensa et al., 2018; Pong et al. 2020). remains an important direction for future work.

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGEMENTS
This material supported by the Fannie and John Hertz Foundation and the NSF GRFP (DGE1745016). In addition, this research is also supported by NSF CISE Expeditions Award CCF- 1730628. UC Berkeley research is also supported by gifts from Alibaba, Amazon Web Services, Ant Financial, CapitalOne, Ericsson, Facebook, Futurewei, Google, Intel, Microsoft, Nvidia, Sco- tiabank, Splunk and VMware.
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay, arXiv preprint 10t.iv:707.014444 2017.
Oron Anschel, Nir Baram, and Nahum Shimkin. Averaged-dqu: Variance reduction and stabilization for deep reinforcement learning. In International conference on machine learning, pp. 176-185. PMLR, 2017.
Hagai Attias. Planning by probabilistic inference. In International Workshop Artificial Intelli- gence and Statistics, pp. 9-16. PMLR, 2003.
Elliot Chane-Sane, Cordelia Schmid, and Ivan Laptev. Goal-conditioned reinforcement learning with imagined subgoals. In International Conference Machine Learning, pp. 1430-1440.
PMLR, 2021.
Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series (Methodological), 39(1): 1-22, 1977.
Thomas G Dietterich. Hierarchical reinforcement learning with the maxq value function decompo- sition. Journal of artificial intelligence research, 13:227-303, 2000.
Yiming Ding, Carlos Florensa, Picter Abbeel, and Mariano Phiclipp. Goal-conditioned imitation
learning. Advances in Neural Information Processing Systems, 22:15324-13355 2019.
Benjamin Eysenbach, Shixiang Gu, Julian Ibarz, and Sergey Levine. Leave trace: Learning to reset for safe and autonomous reinforcement learning. In International Conference on Learning Representations, 2018
Benjamin Bysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search the replay buffer: Bridg- ing planning and reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. C-learning: Learning achieve goals via recursive classification. In International Conference on Learning Representations, 2020.
William Fedus, Carles Gelada, Yoshua Bengio, Mare G Bellemare, and Hugo Larochelle. Hyper- bolic discounting and learning over multiple horizons. arXiv preprint arXiv:1902.06880 06860. 2019.
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse cur- riculum generation for reinforcement learning. In Conference on robot learning, pp. 482 PMLR, 2017.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In International conference machine learning, pp. 1515-1528. PMLR, 2018.
Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. Journal of Machine Learning Research, 5(9), 2004.
10

---

Published as a conference paper at ICLR 2022
Abhishek Gupta, Vikash Kumar, Corey Lynch, Sergey Levine, and Karol Hausman. Relay policy learning: Solving long- long-horizon tasks via imitation and reinforcement learning. Conference on Robot Learning, pp. 1025-1033 PMLR, 2020.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29:4565 4573, 2016.
David Hsu, Jean-Claude Latombe, and Hanna Kurnaawati. On the probabilistic foundations of probabilistic roadmap planning. The International Journal of Robotics Research, 25(7):627-643, 2006.
Zhiao Huang, Fangchen Liu, and Hao Su. Mapping state space using landmarks for universal goal reaching, arXiv preprint arXiv:1908.0555), 2019.
Leslie Pack Kaelbling. Learning to achieve goals. In IJCAI, pp. 1094-1099. Citeseer, 1993.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedback in reinforcement learning via distribution correction. Advances in Neural Information Processing Systems, 33, 2020.
Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprint arXiv: 0099,,999, 2018
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives open problems. arXiv preprint arXiv:2005.01643, 2020.
Andrew Levy. George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierarchies with hindsight. arXiv preprint arXiv:1712.0000
2017.
Xingyu Lin, Harjatin Singh Baweja, and David Held. Reinforcement learning without ground-truth state. arXiv preprint arXiv: /90:::905.000 078607 2019.
Aleksandr Mikhailovich Lyapunov. The general problem of the stability motion. journal of control, 55(3):531-534 1992.
International
Corey Lynch, Mohi Khansari, Ted Xiao, Vikash Kumar, Jonathan Tompson, Sergey Levine, and Pierre Sermanet. Learning latent plans from play. In Conference on Robot Learning, pp. 1113- 1132. PMLR, 2020.
Xiangyun Meng, Nathan Ratliff, Yu Xiang, and Dieter Fox. Scaling local control to large-scale topological navigation. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 672-678. IEEE, 2020.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 31:3303-3313, 2018.
Ofrr Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of dis- counted stationary distribution corrections. Advances Neural Information Processing Systems, 32:2318-2333 2019.
Soroush Nasiriany, Vitchyr Pong, Steven Lin, and Sergey Levine. Planning with goal-conditioned policies. Advances in Neural Information Processing Systems, 32:14843-14854 2019.
Silviu Pitis. Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba. Maximum entropy gain exploration for long horizon multi-goal reinforcement learning. In International Conference on Machine Learning, pp. 7750-7761. PMLR, 2020.
Vitchyr Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew-fit: State-covering supervieed reinforcement learning. In International Conference on Machine Learning, pp. 7783-7792. PMLR, 2020.
11

---

Published as a conference paper at ICLR 2022
Konrad Rawlik, Mare Toussaint, and Sethu Vijayakumar. On stochastic optimal control and rein- forcement learning by approximate inference. In Twenty-thing international joint conference on artificial intelligence, 2013.
Zhizhou Ren, Kefan Dong, Yuan Zhou, Qiang Liu, and Jian Peng. Exploration via hindsight goal generation. Advances in Neural Information Processing Systems, 32: 12881315113 2019.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametric topological memory for navigation. In International Conference on Learning Representations, 2018.
Yannick Schroecker and Charles Isbell. Universal value density estimation for imitation learning and goal-conditioned reinforcement learning. arXiv preprint arXiv:2002.06477, 2020.
Dhruv Shah, Benjamin Eysenbach, Gregory Kahn, Nicholas Rhinehart, and Sergey Levine Ving: Learning world navigation with visual goals. arXiv preprint arXiv:2012.09812, 2020.
Avi Singh, Albert Yu, Jonathan Yang. Jesse Zhang, Aviral Kumar, and Sergey Levine. Cog: Connecting new skills to past experience with offline reinforcement learning. arXiv preprint arXiv:2010. 14500, 2020.
Evangelos Theodorou, Jonas Buchli, and Stefan Schaal. A generalized path integral control ap- proach to reinforcement learning. The Journal of Machine Learning Research, 11:3137-3181, 2010.
Emanuel Todorov. Linearly-solvable markov decision problems. In Advances in neural information processing systems, pp. 1369-1376, 2007.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International Conference Machine Learning, pp. 3540-3549, PMLR, 2017.
Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Conference Robot Learning, pp. 1094-1 1100. PMLR, 2020.
Tianjun Zhang. Huazhe Xu, Xiaolong Wang. Yi Wu, Kurt Keutzer, Joseph E Gonzalez, and Yuan- dong Tian. Bebold: Exploration beyond the boundary of explored regions. arXiv preprint arXiv:20/2.0862) 2020.
Tianjun Zhang, Paria Rashidinejad, Jiantao Jiao, Yuandong Tian, Joseph Gonzalez, and Stuart Russell. Made: Exploration via maximizing deviation from explored regions. arXiv preprint arXiv:2106. 10268, 2021.
Brian D Ziebart. Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegie Mellon University, 2010.
12

---

Published as a conference paper at ICLR 2022
A PROOFS AND ADDITIONAL ANALYSIS
A. DERIVING THE LOWER BOUND (PROOF OF LEMMA I
We first formulate the sampling procedure on starting states so, waypoints sw. goals 5y and the cor- responding time horizon variable & and 82. Then we derive a lower bound on the target log density We then show that optimizing the lower bound through an EM procedure is equivalent to breaking the goal-reaching task into a sequence of easier sub-problems. Finally, we wrapped up this section with a practical algorithm.
of Eq. 2
Data Generation Process. The generative model for which inference corresponds to our planning procedure can be formulated as follows. The episode starts by sampling an initial state so ~ (s0). Then it samples geometric random variable t ~ Geom -) and roll out the policy :(a | s.) for exactly t steps, starting from state Su- We define Sw to be the state where we end up (i.e.,
Sw A St,). Thus, Sw is sampled Sw PGEOM random variable 122 ~ Geom - 7) and roll out the policy T(a 8, 8, for exactly t steps, starting
<=((l>>>) (s so). We then sample another geometric
from state Sw. We define Sy to be the state where we end up (i.e., $9 - st,+12). Thus, sy is sampled
aithie (0++ sw.). Note that the time index of the final state sg is a sample from a negative binomial distribution: 1, 122 d T(-1-18g) of Sg as 8g PNegBinom (sc+ P 8o).
89 ~ PGeam
NB = 1 - 7, n = 2). We can equivalently express the sampling
Inference process. Under the formulation of the data generation process above, we then aim to answer the following question in the inference procedure: what intermediate states would a policy visit if it eventually reached the goal state sn? Formally, we will estimate distribution (s" So: 8g) = p(s
Su, Sg).
We learn q(
so, sy) by optimizing evidence lower bound on main objective (Eq.
(111,99)
log PNEGBINOM ($L+ = Sy 1 su)
(5)
r(11-19))))))))))))))))))) ($t+ = Sg sw PoUOM (sw ss
x(11-10)
log
PGEOM
(6)
log
((-1119)) (8L+ 8g 8w P PGEOM
x(11-15)) (sw 80)
a(sw 8g. su)
dow
(Sww 88g 80)
/ g(sw sg. so) (log x(-1-80) (st+ = 8g sw)+
PGEoM
(8)
x(-1:100) (sw | |u)) log g(sw sg.. 80)) dsw
log PoEOM
(9)
A L(T. g(sw su)).
(10)
Note that Sy conditionally independent of so given sw. so the ( Sg sw) terms on the RHS need not be conditioned on so. The evidence lower bound, L, depends on two quantities: the goal-conditioned policy and the distribution over waypoints. The objective for the goal-conditioned policy is to maximize the probabilities of reaching the waypoint and reaching the final state. The objective for the waypoint distribution is to select waypoints 8, that satisfy two important properties: the current policy should have a high probability of successfully navigating from the initial state to the waypoint and from the waypoint to the final goal. Note that the optimal choice for the waypoint distribution automatically depends the current capabilities of the coal-conditioned" policy.
Before optimizing the lower bound, we introduce a subtle modification to the lower bound:
A / q(sw Sg. $g: so) (log x(-1:;00) PGEoM (s =8g sw)+
C2(T, g(sw Sg. su)) so))
(11)
=())-=)) (sw so) - log g(sw $gg. so)) dsw. log PGBOM
(12)
The difference, highlighted in orange, is that the probability of reaching the waypoint is computed for a goal-conditioned policy that is commanded to reach that waypoint, rather than the final goal. We show that this new objective is also an evidence lower bound on the same geal-reaching objective
13

---

Published as a conference paper at ICLR 2022
(Eq. but modified such that the sequence of commanded goals is treated as an additional latent variable.
Assume that the initial state so and the goal state 8g given. As before, want to find policy that maximizes the probability reaching sg. However, we now consider jointly optimizing over both the policy and the sequence of goals we command for that policy. We use se denote the goal commanded at time t. We can write this optimization problem as follows:
(1:0e) logp" (-I-s(())))) maXX F(T, S6 (1)00)
(8L+ kgg 80).
(13)
Applying Jensen's inequality, we obtain a lower bound that looks similar to before:
F(z, ((T,) (1:00)) 2 (o
log PoEOM
(stt = Sy (w) + log T(-1-s?!
(Sw (0) log g(w (g.
PoEOM
(14)
ff log PGOM
(st+ = Sy sw) + log PeEMM
(sw 50) log g(sw
1sg: 80)
(15)
In the second line, we introduce tyr as the time when the waypoint is reached. This allows us to clarify that the probability of reaching the waypoint only depends on the commanded goals through time tw. se (1ita) This lower bound holds for any choice of the commanded waypoints, st. (11o0) Directly optimizing for the sequence of waypoints is challenging for two reasons. First, it requires estimating the probability of commanding one goal but reaching any other state. Second, we command goal when trying reach different goal, then the goal conditioned policy may learn to associate the commanded goal with the desired outcome. For both these reasons, we choose not optimize the lower bound with respect to the commanded goals, but rather manually specify the commanded goals as follows:
(1:tw) Swi $ +1000) 8g.
(16)
Thus, we have recovered the objective in Eq. 12 As our lower bound holds for any choice of commanded waypoint, also holds for this choice.
A.2 THE OPTIMAL WAYPOINT DISTRIBUTION (PROOF OF LEMMA
This section proves Lemma
Proof. Recall that our goal is to solve the following maximization problem:
[log x(-1--5)) (st+ 8g (w) log PUEOM
x(1--.=)) (swr |su) log ((sw I 18g, $00]
max E Bu(swlesioo) g(8ulag.*0)
PoEoM
(17)
Note that the waypoint distribution must integrate one. The Lagrangian be written
E (egsswlsp.e))
[oogettis PGEOM
x(-1 (se+ = 8g 8w) + log PGEM (set))
=(():-am) (8mr 88) log g(sw (gg 80) + (18)
(f a( so, 8y gys 1),
(19)
where À is Lagrange multiplier. We then take the derivative with respect to ((ww 8gg 80):
d
q(sw | so. (0. sq)
x(-1-sa)
+ logPeEow (s1+ = 8g sw.)+
(20)
dg(sw 80. 88)
(sw w 50, 8g)
r(-1-19))
log PG (sw (0) log g(s 1gg s0)
(21)
- 1 + log PGLOM
T(.1.19) (stt = Sy (w) log PGEOM
[(11 (sw)))) ss)
(22)
log q(
sy. so) + X.
(23)
We then set this derivative equal to zero and solve for g(sw 8g. 80):
g(su Sg. Sp) A
-(-1:-0)) e PGEON
(st+ Sg Sur )
=(-1:sw))
(sw w so).
14

---

Published as a conference paper at ICLR 2022
C P[S.]
Start: S
Goal: S
Waypoints: S
AT sw>
x [sw,
52
S
Without Planning
With Planning
Sut
Vanilla training for a goal- conditioned policy
[a] S, sampled at early training
[bl s, sampled at middle of training
[c] 5, sampled at end stage training
waypoints distribution p(sw). Goal- conditioned RL directly commands the agent to the final goal. C-planning first samples an intermediate way- point &w from p( directs the agent that waypoint, and then commands the final goal after the agent has reached the waypoint. Note that the p(sw) is proportional to the state density of the current policy, so the high probability region will expand from starting state so to the goal state sg. as the agent explores the environment.
Figure 7: C-Planning Curriculum: Illustration of planning
Finally, we determine the value of À such that g( | so. Sy) integrates to one. We can then express the optimal waypoint distribution follows:
x(-1-1)) (sg Sw alll:sw) (sw 100)
PGEOM
9" (sw Sg. su)
f PGEOM
=(11-1)))
(8g 8 (ellrre (8% 80 so)ds's
A.3 ESTIMATING IMPORTANCE WEIGHTS (PROOF OF LEMMA 3
This section proves Lemma
Proof. Define the normalizing constant as follows
b(8g)
Z(50: sy) =
x(-l:)))) PGEOM
(sg 8 PEEME at-h. (s 8 so)
Substituting Z (s0, 6g) into the RHS Eq. and simplifying the result, we show that equals LHS of Eq. 4
Co Co 8g)
C0(80,800
Z(80, $z)
(24)
- -Colsw: sy) 1- Co(so. Sw)
Co(Su: 8q)
Colso: sw)
b(s,)
= 1 Col(sw 8g) 1 - Co(so, sw)
xt-nne) (sg | 8/ x[(1-100)) (s'n so bo)dd''
(25)
a(1118)) PGEOM
(st- = 8g (w) ((.1.30) (s++ 8w 80)
PGEOM b(sw)
blogg]
blogt
J PGEOO (8g 8/m PEEEM
(s/, (s))
(26)
PGEOM (8c- 8g 8w PGEOS x(-1-,8w) (m) (8t+ 8w 180) 1 I PGBOM
(27)
x(-1-180) (sg
s/y Me
(((-11.5w) (s/ 30) ((sm))
g(Sw 80: 8g)
(28)
b(sw)
B ADDITIONAL EXPERIMENTS
B. AN ORACLE EXPERIMENT
15

---

Published as a conference paper at ICLR 2022
C-Planning
C-Planning Optimal
C-Leaminn
Push-Woll
0.225
0.250
Subset Min Distance
0.225
0.175
0.200
0.150
0.175
0.125
Suboet
0.150
0.100
0.125
0.075
0.100
0.050
1.0
Environment Steps
Environment Steps
Figure 8: Oracle experiment with the optimal generative model: Goal-conditioned RI. learns the task much faster we can sample the waypoints from the expert policy's 's marginal state distrihution (C-Planning Optimal). Compared planning with optimal state density distribution, planning using learned classifier (C-Planning) shows comparable performance.
We run an experiment to confirm the well- known result (Kakade & Langford (002) that the optimal initial state distribution for learn- ing task is the state distribution of that task's optimal policy. Intuitively, if we could sample exactly from the state distribution of the op- timal policy, then an RL agent could learn to reach goals more quickly. This as it resembles behavioral cloning of the opti- mal policy. In this oracle experiment, is as- sumed we are given the access to optimal policy. We achieve this by following the sam- pling procedure from Algorithm. [ but replace the classifier C with that learned from the op- timal policy C" We then perform RL to reach waypoints and then the final goal. Results in Fig. X show that using the optimal policy as the initial state distribution results in faster learning than using the original state distribution. We also visualize the state density distribution of the optimal policy to provide more qualitative intuition on how the algorithm works. Please refer Appendix B.2 for more details.
Goal
Goal
surprising
Start
Optimal stata distributio Push
@a Optinal state disrrbutto for PushWall
Figure 9: (Left)An agent must navigate from the start state to the goal state. The heatmap vi- sualizes the marginal state distribution of the op- timal policy.
In addition, we are also interested in measuring how well does planning through a learned model (C- Planning) performs we don't have access to the optimal generative model. Results Fig. | also show that C-Planning achieves performance comparable to planning via optimal generative model the Push and the Push- Wall environment.
B.2 VISUALIZATION OF STATE DENSITY MAP OF OPTIMAL POLICY
We conduct this experiment visualized the original initial state distribution, the state distribution of an optimal policy, and the goal state. To conduct this experiment, we apply state-of-the-art goal-conditioned RL algorithm (C-learning) in the two settings with different initial state distributions. For fair evaluation, we evaluate the policies learned in both settings using the original initial state distribution. The results shown in Fig. 8 (right) show that starting from the optimal initial state distribution results in 2.4x faster learning.
2D navigation task shown in Fig. (left), where have also
B.3 A ABLATIONS TO HER, SKEWFIT AND SoRB (C-PLANNING)
We perform additional experiments, comparing C- C-Planning with HER (Andrychowicz al. 2017; SkewFit (Pong et al., 2020) and SoRB (Eysenbach et al. 2019) on C-Planning, HER barely works only simple experiments (e.g., Reach) but fails harder ones. Similar results also been
16

---

Published as a conference paper at ICLR 2022
Push
Push- Wall
Reach
0.25
Suluu Cisunce
0.00
0.225
Sulocd Mig distannee
0:25
0.175
1220-
0.200
00255
0.375
0.15
0.150
0.100
0.125
0.05-
0.00
0.0
0.2
0.4
0.6
0.6
3.0
0.200
0.0
0.2
0.4
0.6
0.8
3.0
0.09
Enveonmmatt Stops
Envitommnn Stops
146
Enstrommen Steds
105
Figure 10: Ablation with HER, SkewFit and SoRB: Comparison of C-Planning more baselines like HER, SkewFit and SoRB. HER only shows good performance on easy task like Reach but fails on harder ones. SkewFit shows little better performance in Reach task but is little worse in Push and Push- Wall. Additional ablation study on SoRB shows small benefits are gained by adding SoRB at test time.
Push-Wall.
Nowning
Menning Nor2
Parniing Rond)
20-
0.22
30
0.2
2.6
Figure 11: Ablation on the Planning Horizon and Experiments on Ant-Maze: (left) Albation study of the planning horion, A Larger planning horizon will sometimes help the performance of tasks, the improvement not consistent. (right) Experiments on small scale Ant-Maze. RIS manage reach the goal quickly in Ant- Small environment but fails in the Ant-Mid.
observed in the C-Learning (Eysenbach et al. 2020) paper. We implement version of SkewFit algorithm on top of our framework. The only change it did is SkewFit samples swaypoints according to the inverse of state density model. We see that SkewFit has better performance in Reach task but fails in Push Wall task. We also compare C-Planning with SoRB(C-Planning) which does SoRB at test time. Results show that SoRB performs as well as C-Planning at test time.
B.4 ABLATIONS ON PLANNING HORIZON
We perform an ablation study on the planning horizon (number of waypoints used when doing sampling). We implement this in a way of iterative planning: take horizon of 4 for example, we first planning the middle point Sw2 via starting point and goal of (sg. sy); then planning $w1 via starting point and goal (Su, $w2). Results show that planning for a more fine-grained fashion (larger number of waypoints) is not always helping. In the Fig. left, in Reach task, planning over more waypoints helps but it decreases the performance in Push task. Note that here the number of waypoints is used for planning, while in Fig. 4 the number of waypoints is how many waypoints to reach before changing to the final goal. These two are different quantities.
B.5 ADDITIONAL. EXPERIMENTS ON ANT-MAZE
We performance an additional experiments in the Ant-Maze environment. We design a very simple environment: command the ant to a specific goal position with short (Ant-Small) or a long (Ant- Mid) distance. The distance between starting point and goal is 2.5 and 7.5 repectively for Ant-Small and Ant-Mid. The only two modifications we did comparing to the original RIS (Chane-San 2021) is change the maximum time horizon to 300 (RIS uses max time steps of 600) and reset the agent to a fixed area (RIS resets the position of the agent uniformly). In Fig. IT right, RIS achieves better performance in Ant-Small environment while fails in Ant-Mid environment. Note that C- C-Planning doesn't 't use any termination function and reward function while RIS heavily relies on them.
al,,
17

---

Published as a conference paper at ICLR 2022
We also study the performance of RIS under these design choices. We mainly concerned with two settings: random initialize the agent's posi- tion versus fixed initialize the agent's position and choosing termination threshold of 1.0 versus 0.5. In Fig. [2 we can clearly see the results that using a slightly different thresh- old factor for termination will greatly affect the performance of RIS: us- ing 1.0, the agent almost fails to learn any policy; while using 0.5, the agent is learning very fast. This shows that RIS is very sensitive to the choice of this termination func- tion. It again proves the benefit of C-Planning since we don't rely on any reward function and termination function.
Art.Mid
Subset Min Distance
4
3
0.0
0.5
1.0
15
2.0
2.5
Environmant
1e5
Figure 12: Ablations design components of RIS: We study design factors that might affect the performance of RIS. Different threshold on termination function (1.0 versus 0.5) affecting the performance of RIS significantly.
C EXPERIMENTAL DETAILS
In this section, We provide the essential hyperparameters for reproducing our experiments in this section. We also introduce the hyperparameters used in baselines and provide detailed description of environmental design.
C.I IMPLEMENTATION DETAILS
We introduce the hyperparameters used in C-Planning. Note that in C-Learning, only classifier on (st, St+, a.) is needed. In C-Planning, in order to sample waypoints from the distribution, ad- ditional classifier on (st, 8++ is needed. We also introduce two hyperparameters: Maximum Steps Reaching Goal (N, in Alg D forces the agent to change the intermediate goal if the original goal hasn't been reached for some steps; Distance Threshold Reaching Goal (c, in Alg for determing whether goal reached not. The rest are the standard hyperparameters for SAC algorithm and we list here for reference.
Table 1: Hyperparameters used for C-Planning in all the environments in MetaWorid.
Hyperparameter Value
Actor Ir
0.0003
Action-Staa State Critic Ir
0.0003
State Critic Ir
0,00003
Actor Network Size
(256, 256, 256)
Critic Network Size
(256, 256, 256)
Maximum Steps Reaching Goal
20
Distance Threshold Reaching Goal
0.05
Actor Loss Weight
1.0
Critic Loss Weight
0.5
Discount
0.99
Target Update Tau
0.005
Target Update Period
Number Waypoints
Goal Relabel Next
0.3
Goal Relabel Future
Note that slightly different hyperparameters for 2D maze environment and list below, all the other hyperparameters remains the same. Note that we follow the goal relabeling changes by C-Learning (Eysenbach et al. 2020).
18

---

Published as a conference paper at ICLR 2022
Table 2: Hyperparameters used for C-Planning in all the environments in 2D navigation maze.
Hyperparameter Value
Distance Threshold Reaching Goal
1.0
Number Waypoints
Goal Relabel Next
0.5
Goal Relabel Future
0.0
C.2 ENVIRONMENTS
We follow the envioronment design of (Eysenbach et al., 2020) with only one noticeable difference: in the original environments of C-Learning, for the ease of training. the author set the initial position of objects to be relatively near the arm so the arm can easily push the object, getting a better learning signal. We intentionally set the initial state of object be far away from the arm. This significantly increase the diffuculty of learning. We'll release these environment with the code.
Table 3: Max number of time steps used for each environment.
Max Time Steps
Spiral 9x9
200
Spiral 11x11
200
Maze 11x11
200
Sawyer Push
50
Sawyer Reach
50
Sawyer Push-Wall
50
150
Obstacle- Obstacle-Drawer-O00 Drawwer-Open
150
Sawyer Push-Two
150
C.3 BASELINES
We also provide the hyperparameters associated with the baselines. The two baselines we care about: C-Learning and RIS. We summarize their hyperparameters in the table:
Table Hyperparameters used for C-Learnng in all the environments in MetaWorld.
Hyperparameter Value
Actor Ir
0.0003
Action-State Critic Ir
0.0003
Actor Network Size
(256, 256, 256) (256, 256, 256)
Critic Network Size
Actor Loss Weight
1.0
Critic Loss Weight
0.5
Discount
0.99
Target Update Tau
0.005
Target Update Period
Goal Relabel Next
0.3
Goal Relabel Future
0.2
D VISUALIZATION OF THE LEARNED POLICY
In order to more intuitively visualize the behavior of the learned policy and emphasize the impor- tance of the difficulty of the learning task, we plot the visualization of our learned policy for several snap shots in episode for environment of Push-Two and Mbostacle-Draerr-- that our method successfully guide the agent to learn the behavior push the green object first, the push the object; And first open the drawer then push the object to the desired location. We would
We see
19

---

Published as a conference paper at ICLR 2022
Table Hyperparameters used for RIS in all the environments in Meta World.
Hyperparameter Value
epsilon
0,0001
Replay Buffer Goals
0.5
Distance Threshold
0.05
Alpha
0.1
Lambda
0.1
H Ir
0.0001
Q Ir
0.001
Pi
0.0001
Encoder Ir
0.0001
Figure 13: Visualization of the trained policy for the Push-Two environment. Our method suc- cessfully trains the agent to manipulate the two object in the sequential manner without any offline data, expert demonstration and reward shaping. Prior baselines all fail to demonstrate such behavior.
like to emphasize that prior baselines all fail demonstrate such behavior without any offline data, expert demonstration and reward shaping. The successfully learning of such behavior enables the robot to do more complex tasks without any human intervention.
20

---

Published as a conference paper at ICLR 2022
Figure 14: Visualization of the trained policy for the Obstacle Serllle-DDaee---ee Open environment. Our method successfully trains the agent to first close the drawer and then push the object to the desired location. We emphasize that such behavior is hard to obtain and most of the prior methods only manage to close the drawer.
21


Reviews:
[{"review_id": "l-2wnDvgrYf", "reviewer": "Reviewer_1xhY", "summary": "", "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": "Main concerns\n1. Missing important baselines\\\nThe experiment is missing an important baseline: [Huang et al., 2019]. In section 2, authors claim that [Huang et al., 2019] does not perform planning in train time and does not improve the underlying goal-conditioned policy. However, this is not true. [Huang et al., 2019] also improves the quality of the data used to train the policy by improving the exploration in training. Specifically, [Huang et al., 2019] periodically populates the landmarks using the farthest-point-sampling to explore the frontier of the explored state space.\nAnother important baseline to consider is the goal-relabeling methods because they also provide additional learning signals from the states visited during training for GCRL. It would be very helpful to demonstrate that the proposed method is a better way to provide additional learning signals to GCRL than the alternatives.\n\n2. More intuition on “iterative” waypoint sampling\\\nTo my understanding, the optimal way point $s_w$ that minimizes the proposed objective is the midpoint between current $s$ and the goal state $s_g$ regardless of the choice of $n_g$. However, this is not really the optimal choice for the GCRL. The better waypoints would be (arguably) the equally-spaced $n_g$ points on the route from initial state to the goal state. If authors can share the philosophy behind this specific design choice, it would be very helpful for the reader.\n\n3. The choice of prior\\\nAuthors proposed to choose a specific prior model: negative binomial distribution with $p=1-\\gamma$ and $n=2$. It seems this assumption is necessary for the decomposition of Eq.(2) into Eq.(4), but the specific design choice could be justified/explained better. Also, it is counter-intuitive in that the pdf of negative binomial distribution is bell-shaped. It means the agent receives a *smaller reward* if it achieves the goal “too early”. \n\nMinor concerns\n\n4. Searching at training time\\\nIt may be controversial whether C-planning performs (implicit) searching in train time. The C-planning queries the distance between several pairs of states, but it does not perform any path finding\n\n5. RIS is not learning at all\\\nIn figure 4, the performance of RIS is consistently the worst among the compared methods and seems RIS is not learning at all even in the easiest task. Is this expected? It is unclear whether the RIS is correctly reproduced and the hyperparameters are appropriately tuned.\n\n6. Performing the test-time search\\\nIt seems natural to me to consider also performing the waypoint sampling in test-time similar to training. In figure 5, authors instead implemented the C-Planning + SoRB. Is there a reason that C-planning cannot perform test-time waypoint sampling? If possible, does performing test-time search improve the performance?\n\nQuestions/suggestions\n\n- Q: in line 7 of Algorithm 1: What’s the difference between $\\tau_1$ and $\\tau_2$? Why do you need those two?\n- Gradient analysis: it would be great if authors can provide at least an intuitive explanation of why increasing  the norm of critic norm and decreasing the variance of the actor gradient norm is helpful for learning in the paper for the readers\n\n[1] Mapping state space using landmarks for universal goal reaching. Huang et al., 2019.\n\n[2] Hindsight experience replay. Andrychowicz et al., 2017\n", "summary_of_the_paper": "This work extends the previous work, C-learning, by using search at training time to generate a curriculum of intermediate states enroute to the goal state. The main idea is to decompose the goal reaching problem into a sequence of easier tasks of reaching the reachable intermediate states. Authors prove that under the negative binomial prior with $n=2$, the goal-reaching RL objective is lower-bounded by the sum of two goal-reaching objectives: reaching waypoint $s_w$ from the initial state $s_0$ and reaching the goal state $s_g$ from the way point $s_w$. In practice, authors proposed to uniformly sample the way points from the replay buffer and apply importance sampling afterwards to avoid the challenge of sampling high-dimensional waypoint states. The experiment was conducted on various goal-conditioned RL tasks on 2D mazes and the robotics manipulation tasks. The C-planning method outperforms the compared baselines on challenging tasks. Authors also conducted various ablation studies justifying several design choices made in the proposed method and demonstrating the light deployment-time computation cost of the proposed method.", "summary_of_the_review": "The paper presents a non-trivial extension of the previous work and presents an interesting viewpoint of formulating implicit train-time searching as variational inference. The paper is clearly written and easy to follow. However, I found that the experiment section is relatively weak and the presented results are less convincing. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "f_yUsruAENC", "reviewer": "Reviewer_rAmA", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strength:\n\n Robust, solid and strong theoretical development of an EM algorithm to learn long-horizon goal conditional policies that learn in a curriculum manner.\n Clear experiments.\n Clear language and well explained paper.\n\nSome questions :\n\nWhy the negative binomial distribution assume a n = 2 (sentence before  to equation 1) Why the number of failures is 2? Or in other terms, why the planning horizon is always 2? Because of intermediate goal and goal?  Its assuming that need to do 2 steps at least? \nThe criticism about other papers using a Geometric distribution seems not adequate. The interpretation of Geometric distribution in this other papers seems similar to a NegBinomail(1- lambda, n). Sg should be passed to the Algorithm 2 - C-Planning.\n\nWeakness:\n \nExperiments:\n    1. Why experiments do not contained the same as RIS? Just for completeness to show that you do better than RIS on their experiments.\n     2. Why you don't consider to compare to the Skew-fit algorithm? Even if its different there some similarity on the curriculum learning with distribution that keep being modified?", "summary_of_the_paper": "The paper presents an goal conditioned algorithm that uses an Expectation Maximization  framework. The E step is a \"graph search\", and the M step is a previous developed goal reaching RL algorithm. There is an automatic curriculum learning mechanism that comes from using variational inference. The goal-conditioned policy optimization and the method for sampling waypoints are jointly optimized using the same objective.", "summary_of_the_review": "\n\nThis is valuable progress on the field of learning goal conditioned policies. curriculum learning have been a challenge and this work shows a clear advance and solid theoretical connection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NR8AbitdGH4", "reviewer": "Reviewer_gSmz", "summary": "", "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": "Strength:\n\n1. The method nicely combines the C-learning with SoRB-like search methods. If my understanding is correct, we can regard this approach as a single-step waypoint search based on the learned universal value functions. Such an approach benefits from the fruitful goal-conditioned value function learning and can make progress in sparse-reward settings. At the same time, waypoint selection allows the agent to do structural exploration as suggested by \"Why Does Hierarchy (Sometimes) Work So Well in Reinforcement Learning?\" and get a better value estimation by expanding the expectation of values. According to my understanding, it is still hard to know if or why only searching waypoints during exploration should be better than searching the whole path (like in SoRB) and if we need to use the sampled waypoints to help us accelerate the bellman-equation update. However, I think the idea is already enough to serve as a strong competitor for goal-reaching tasks.\n2. The method provides theoretical insights by modeling waypoint selection as an EM algorithm. At the same time, it shows good experiment results are good. I agree that the Obstacle-Drawer-Close task is pretty challenging. Success in such an environment is appealing. \n\nWeakness:\n\n1. My major concern is about the evaluation and the lack of link to the hierarchical RL methods. Many hierarchical RL methods exploit the way of combining a subgoal proposal network with a goal-condition function as C-Planning does. For example, the HIRO and HAC algorithms. In fact, we can also view LEAP, SoRB as kind of hierarchical RL algorithms in which high-level policies are model-based search methods. C-Planning employs a replay-buffer search based on the learned value function to propose subgoals. Though it is much simpler than previous approaches, the authors should at least provide a discussion about the relationship and the differences. I would also suggest authors conduct experiments on some classical environments such as AntMaze and AntPush to help researchers to position this work in literature.\n\nMinor:\n\n1. In Alg 1. line 7, there should be small bugs. There is no reason to concatenate the trajectory with itself.\n2. I am a little confused by the performance of SoRB. Its performance decrease when it runs longer in Spiral 11x11. What's the reason behind it? I also do not understand why it can not solve this task. The simple maze environment should be very friendly to the graph-based search method.\n3. The word CURRICULUM in the title is confusing. Do I miss any part that shows the proposed way-points are curriculum? I think curriculum refers to a process from the simple one to the hard one, but I don't understand why C-planning is a curriculum.", "summary_of_the_paper": "This paper proposes C-Planning, a method that generates subgoals for distant goal-reaching tasks. The method is built upon the C-learning method, which learns a goal-condition policy together with a function that can estimate the connectivity between two states. The method then leverages an EM-like algorithm to propose waypoints by selecting a subgoal from replay buffer according to the distribution between the sum of state-to-waypoint distance and waypoint-to-goal distance. The authors apply this approach to both maze domain and challenging meta-world tasks and show improved performance.", "summary_of_the_review": "This paper proposes a nice framework to combine goal-conditioned RL and waypoint selection. The method is neat and effective. Though the connection with the HRL is unclear from the paper, the advantages outweigh the flaws. I tend to accept the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MV0HV356fy", "reviewer": "Reviewer_qxwP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n- The presented method steps on C-Learning, but I also find it manages to introduce sufficient theoretical and practical novelty. This is primarily expressed in the waypoint idea (coined C-planning), which is very nicely motivated through the probabilistic framework. The proposed ELBO reformulation of the objective in Lemma 1 appears natural and sound to me.\n- Using the classifier of C-learning to define the approximate posterior over waypoints through importance sampling is a nice conceptual trick. The outputs of the classifier are a proxy for the future state distribution, needed to evaluate the \"likelihood\" (waypoint-to-goal) and \"prior\" (start-to-waypoint) for the reweighting, so I find the usage very fitting, assuming the classifier really captures the distributions in question.\n- The considered environments are sufficiently complex, albeit simulated. The proposed algorithm seems to perform well in all of them and outperforms the baselines, including C-learning and a baseline that incorporates planning during test time, which is nice to see.\n- The E step of the developed EM algorithm (MC-estimation of the ELBO w.r.t. samples from the waypoint distribution) seems rather generic, and can probably be combined with approximate control algorithms other than C-learning (the M step), as long as they subscribe to the VI / probabilistic view on control.\n\n## Weaknesses\n- The ELBO (and respective PGM) in Lemma 1 is derived under the goal-conditioned policy, but later in Lemma 2, when the approximate posterior over waypoints is defined, and for pretty much all later derivations in the paper we see a goal-conditioned policy used for the waypoint-to-goal term (\"likelihood\" in the PGM for the ELBO), and a waypoint-conditioned policy for the start-to-waypoint term (\"prior\" in the PGM for the ELBO). This seems discrepant with the ELBO derivation. I checked Appendix A.1, and it hints at that, promising a proof of why this would be OK, but I did not manage to find it. I am setting my correctness score to 3 because of this issue, until it is clarified.\n- I think further clarity about the exact conditional inputs fed into the C-learning classifier are necessary, preferably in the main body of the paper. E.g. appendix E.1 mentions a secondary classifier is needed, leaving the control input out (which I imagine is necessary for e.g. the weights in Lemma 3, etc.). Given that the classifier (critic) introduced in C-Learning is a proxy for the assumed distribution over future reachable states, I think this is important. In general, spelling out exactly which distributions are approximated through the classifier (and for which policies) would make the paper more self-contained.\n- It was hard for me to glean from the paper why exactly RIS [2] (which adds planning to the objective directly) fails in comparison to C-planning (in which planning is expressed through the waypoint selection when collecting experience, i.e. it's reflected in the empirical of collected data). Section 2 mentions this is because \"(C-planning) avoids favoring the learned policy\", can you please elaborate? I think this is an important distinction.\n\n## Further remarks & questions\n- In Algorithm 1, line 7 currently says that two rollouts are added to the data set, both start-to-waypoint under the current policy. Shouldn't one of them be waypoint-to-goal, to match the second term in the ELBO, or am I misinterpreting? Also, it might be good to specify the conditioning of the policy at this point, for clarity.\n- Looking at Algorithm 1, the same policy and classifier appear in every loop iteration, for different episodes. Are their parameters kept in-between episodes, or do they get reset? Also, does C-learning run to convergence for every episode? Would be good if this is specified somewhere.\n- The assumed NegBinom model on the assumed distribution of episode lengths seems like a choice out of convenience. Judging by the appendix, it's equivalent to concatenating two rollouts with geometric-distributed length, which then fit the C-Learning assumption. Was there any other motivation behind it, and did you consider alternatives?\n- The link to code advertised in the paper did not work for me (I only see the paper title on the page, no videos either).\n- The title of section 4 is currently at the bottom of page 3.\n- I think the caption of Figure 4 does not reflect the order of the figures.\n- In section 5, Results, it says C-planning performs worse on Push, but if I am reading figure 4 correctly it should be Reach.\n\n## References\n[1] Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. C-learning: Learning to achieve goals via recursive classification. ICLR, 2020.\n\n[2] Elliot Chane-Sane, Cordelia Schmid, and Ivan Laptev. Goal-conditioned reinforcement learning with imagined subgoals. ICML, pp. 1430–1440. PMLR, 2021.\n", "summary_of_the_paper": "The paper presents a method for goal-conditioned RL, tailored to solving tasks with distant goals (compared to the current SotA in goal-conditioned RL). For that, a prior approach called C-Learning [1] (a VI-flavored reformulation of approximate control for goal-reaching tasks) is extended with a scheme for experience collection (collecting on-policy rollouts), which is akin to search / planning in the sense that the overall start-to-goal reaching task is broken up into collecting start-to-waypoint and waypoint-to-goal trajectories. It is argued that breaking up the problem, and respectively introducing a posterior distribution over waypoints, enables solving long-distance reaching tasks & makes for more efficient and stable goal-conditioned RL (intermediate tasks are easier to learn from, better quality of the data, waypoints easier to reach, etc.). An additional benefit is that there is no need for search during test time (faster evaluation of the policy). The claims are empirically validated on a number of relatively complex, simulated tasks (2D maze navigation, Metaworld robot arm manipulation). The method compares favorably to the considered baselines.\n\n**Technical details**\n\nIn technical terms, the scheme starts with the assumptions in C-learning, casting the goal-reaching objective as maximizing the prob. of the goal state under the distribution over reachable future states under policy (aligned with the VI view on optimal control). From there, a latent variable for intermediate waypoints is introduced, which leads to the formulation of an ELBO for the goal-reaching objective of C-Learning. Optimizing the ELBO is done via EM: in the E step an approximate posterior distribution over the waypoint $q(s_w)$ is implicitly defined via importance-sampling (proposal is the previously-collected empirical over states), cleverly utilizing the outputs of the classifier of C-learning for the importance weights. The waypoints sampled from $q(s_w)$ then guide the sampling of on-policy rollouts (start-to-waypoint, waypoint-to-goal) that reflect the two relevant terms in the ELBO (waypoint-to-goal corresponds to the \"likelihood / reconstruction\" term, start-to-waypoint to the \"prior\" part of the KL term). Conveniently, the two terms in the ELBO can be equated to two C-learning objectives, so the C-learning algorithm can be used as a black-box on the collected rollouts (this represents the M step of EM, maximizing w.r.t. the policy & classifier parameters in expectation over the rollouts from the E step).\n", "summary_of_the_review": "I find the proposed method to be a nice step-up from existing prior work, both theoretically and in terms of performance. The proposed incorporation of planning (in terms of waypoints) appears well-justified, and seems to enable solutions to a variety of goal-reaching tasks that are not trivial. Heuristics also seem to be mostly avoided, which is appreciated.\n\nI would recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers appreciate the suggested EM approach to goal-conditioned long-horizon reinforcement learning, and the technical contributions of the paper. While there is a mix in ratings, even the most critical reviewers feels that the paper has clear merits and is acceptable, and there are two solid acceptance recommendations. Overall, the papers significantly meets the standards of an ICLR paper acceptance.
Decision: Accept (Poster)