Learning to Reach Goals Without Reinforcement Learning
Authors: Dibya Ghosh
Abhishek Gupta
Justin Fu
Ashwin Reddy
Coline Devin
Benjamin Eysenbach
Sergey Levine
Venue:  (2020)
Keywords: Reinforcement Learning
Goal Reaching
Imitation Learning

Abstract: Imitation learning algorithms provide a simple and straightforward approach for training control policies via standard supervised learning methods. By maximizing the likelihood of good actions provided by an expert demonstrator, supervised imitation learning can produce effective policies without the algorithmic complexities and optimization challenges of reinforcement learning, at the cost of requiring an expert demonstrator -- typically a person -- to provide the demonstrations. In this paper, we ask: can we use imitation learning to train effective policies without any expert demonstrations? The key observation that makes this possible is that, in the multi-task setting, trajectories that are generated by a suboptimal policy can still serve as optimal examples for other tasks. In particular, in the setting where the tasks correspond to different goals, every trajectory is a successful demonstration for the state that it actually reaches. Informed by this observation, we propose a very simple algorithm for learning behaviors without any demonstrations, user-provided reward functions, or complex reinforcement learning methods. Our method simply maximizes the likelihood of actions the agent actually took in its own previous rollouts, conditioned on the goal being the state that it actually reached. Although related variants of this approach have been proposed previously in imitation learning settings with example demonstrations, we present the first instance of this approach as a method for learning goal-reaching policies entirely from scratch. We present a theoretical result linking self-supervised imitation learning and reinforcement learning, and empirical results showing that it performs competitively with more complex reinforcement learning methods on a range of challenging goal reaching problems.

Under review as a conference paper at ICLR 2020
LEARNING TO REACH GOALS WITHOUT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Imitation learning algorithms provide simple and straightforward approach for training control policies via standard supervised learning methods. By maximiz- ing the likelihood of good actions provided by an expert demonstrator, supervised imitation learning can produce effective policies without the algorithmic complex- ities and optimization challenges of reinforcement learning, at the cost of requiring expert demonstrator typically a person to provide the demonstrations. In this paper, we ask: can we use imitation learning to train effective policies without any expert demonstrations? The key observation that makes this possible is that, in the multi-task setting, trajectories that are generated by a suboptimal policy can still serve optimal examples for other tasks. In particular, in the setting where the tasks correspond to different goals, every trajectory is a successful demon- stration for the state that it actually reaches. Informed by this observation, we propose a very simple algorithm for learning behaviors without any demonstra- tions, user-provided reward functions, or complex reinforcement learning meth- ods. Our method simply maximizes the likelihood of actions the agent actually took in its own previous rollouts, conditioned on the goal being the state that it actually reached. Although related variants of this approach have been proposed previously imitation learning settings with example demonstrations, we present the first instance of this approach as method for learning goal-reaching policies entirely from scratch. We present a theoretical result linking self-supervised im- itation learning and reinforeement learning, and empirical results showing that it performs competitively with more complex reinforcement learning methods on a range of challenging goal reaching problems.
INTRODUCTION
Reinforcement learning (RL) algorithms hold the promise of providing broadly-applicable tool for automating control, and the combination of high-capacity deep neural network models with RL extends their applicability to settings with complex observations and that require intricate policies. However, RL with function approximation, including deep RL, presents a challenging optimization problem. Despite years of research, current deep RL. methods are far from turnkey solution: most popular methods lack convergence guarantees (Baird) 1995) Tsitsiklis
Van Roy 1997) or
require prohibitive numbers of samples (Schulman al. 2005 2015||illica Lillicrap al. 2015). Moreover, in practice, many commonly used algorithms are extremely sensitive to hyperparameters (Henderson 2018). Besides the optimization challenges, another usability challenge of RL is reward function design: although RL automatically determines how to solve the task, the task itself must be specified in a form that the RL algorithm can interpret and optimize. These challenges prompt us to consider whether there might exist general method for learning behaviors without the need for complex, deep RI. algorithms.
Imitation learning is an alternative paradigm to RL that provides simple and straightforward ap- proach for training control policies via standard supervised learning methods. By maximizing the likelihood of good actions provided by expert demonstrator, supervised imitation learning can produce effective policies without the algorithmic complexities and optimization challenges of RL. Supervised learning algorithms in deep learning have matured to the point of being robust and reli- able, and imitation learning algorithms have demonstrated success in acquiring behaviors robustly and reliably from high-dimensional sensory data such images (Rajeswaran al. 2017 Lynch

---

Under review as a conference paper at ICLR 2020
et al. 2019). The catch is that imitation learning methods require an expert demonstrator ttypiall a human-- to provide a number of demonstrations of optimal behavior. Obtaining expert demon- strations can be challenging; the large number of demonstrations required limits the scalability of such algorithms. In this paper, we ask: can we use ideas from imitation learning to train effective policies without any expert demonstrations, retaining the benefits of imitation learning, but making it possible to learn goal-directed behavior autonomously from scratch?
The key observation for making progress on this problem is that, in the multi-task setting, trajectories that are generated by a suboptimal policy can serve as optimal examples for other tasks. In particular, in the setting where the tasks correspond to reaching different goal states, every trajectory a successful demonstration for the state that it actually reaches, Similar observations have been made in prior works as well (Kaelbling, 1993] Andrychowicz et al., 2017] Nair et al. 2018 Mavrin et al.) 2019 Savinov et al. 2018). but have been used to motivate data reuse in off-policy RI. or semi- parametric methods. Our approach will leverage this idea to obtain near-optimal goal-conditioned policies without RL or reward functions.
The algorithm that we study is, at its core, very simple: at each iteration, we run our latest goal- conditioned policy, collect data, and then use this data to train policy with supervised learning. Supervision is obtained by noting that each action that is taken is a good action for reaching the states that actually occurred in future time steps along the same trajectory. This algorithm resembles imitation learning, but is self-suuprrvised. This procedure combines the benefits of goal-conditioned policies with the simplicity of supervised learning, and we theoretically show that this algorithm cor- responds to a convergent policy learning procedure. While several prior works have proposed train- ing goal-conditioned policies via imitation learning based on a superficially similar algorithm (Ding et al. 2019 Lynch et al. 2019), to our knowledge no prior work proposes a complete policy learning algorithm based on this idea that learns from scratch, without expert demonstrations. This proce- dure reaps the benefits of off-policy data re-use without the need for learning complex Q functions or value functions. Moreover, we can bootstrap our algorithm with a small number of expert demon- strations, such that it can continue to improve its behavior self supervised, without dealing with the challenges of combining imitation learning with poflpo RL.
The main contribution of our work is complete algorithm for learning policies from scratch via goal-conditioned imitation learning, and to show that this algorithm can successfully train goal- conditioned policies. Our theoretical analysis of self- self-supervised coal-conditioned imitation learning shows that this method optimizes a lower bound on the probability that the agent reaches the desired goal. Empirically, we show that proposed algorithm is able to learn goal reaching behaviors from scratch without the need for an explicit reward function or expert demonstrations.
RELATED WORK
Our work addresses the same problem statement as goal conditioned reinforcement learning (RL) (Andrychowicz et al. 2017 Held et al., 2018: Kaelbling 1993. Nair et al.) 2018), where aim to learn a policy via RL that can reach different goals. Learning goal-conditioned policies is quite challenging, especially when provided only sparse rewards. This challenge can be partially mitigated by hindsight relabeling approaches that relabel goals retroactively (Kaelbling) 1993 [Sehaul et al. 2015 Pong et al.] 2018: (Andyychowicz et al.. 2017]. However, even with relabelling, the goal- conditioned optimization problem still uses unstable off-policy RL methods. In this work, we take a different approach and leverage ideas from supervised learning and data relabeling to build off- policy goal reaching algorithms which do not require any explicit RL. This allows GCSL to inherit the benefits of supervised learning without the pitfalls of off off policy RL. While, in theory. on oo-policy algorithms might be used to solve goal reaching problem as well, their inefficient use of data makes challenging to apply these approaches to real-world settings.
Our algorithm is based on ideas from imitation learning (Billard et al. 2008 Hussein et al. 2017) via behavioral cloning (Pomerleau) 1989) but it is not an imitation learning method. While it is built on top of ideas from supervised learning, we are not trying to imitate externally provided expert demonstrations, Instead, we build an algorithm which can learn to reach goals from scratch, without explicit rewards. A related line of work (Hester et al. 2018 Brown et al. 2019) has explored how agents can leverage expert demonstrations to bootstrap the process of reinforcement learning. While GCSL is algorithm to learn geal-nea policies from scratch, it lends itself naturally
2

---

any expert Under review as a conference paper at ICLR 2020
to bootstrapping from demonstrations. As we show in Section 5.4 GCSL can easily incorporate demonstrations into off- learning and continue improving, avoiding many of the challenges described in Kumar et al. (2019b).
Recent imitation learning algorithms propose methods that are closely related to GCSL. Lynch et al. (2019) aim to learn general goal conditioned policies from "play" data collected by hu- man demonstrator, and Ding et al. (2019) perform goal-conditioned imitation learning where expert goal-directed demonstrations are relabeled for imitation learning. However, neither of these meth- ods are iterative, and both require human-provided expert demonstrations. Our method instead iteratively performs conl-condi behavioral cloning, starting from scratch. Our analysis shows that performing such iterated imitation learning on the policy's 's own sampled data actually optimizes a lower bound on the probability of successfully reaching goals, without the need for demonstrations.
The cross-entropy method (Mannor et al. 2003), self-imitation learning (Oh et al. 2018), reward- weighted regression (Peters & Schaal (007), path-integral policy improvement (Theodorou et al. 2010), rewart-adgmented maximum likelihood (Norouzi et al. 2016; Nachum et al. (016), and proportional cross-entropy method (Goschin et al.) 2013) selectively weight policies or trajectories by their performance during learning, as measured by then environment' 's reward function. While these may appear procedurally similar to GCSL, our method is fully self-supervised, as it does not require a reward function, and is applicable in the goal-conditioned setting. Additionally, our data is collected,
algorithm continues to perform well in the purely off off-policy setting, where a key difference from other algorithms (Lynch et al. [2019] Ding et al. 2019).
A few works similar to ours in spirit study the problem of learning goal-conditioned policy without external supervision. Zero-shot visual imitation uses an inverse model with forward consistency to learn from novelty seeking behavior, but lacks convergence guarantees and requires learning a complex inverse model Pathak et al. (2018). Eysenbach al., 2019) learn a policy similar to ours but do so by building connectivity graph over the visited states in order to navigate environments, which requires large memory storage and computation time that increases with the number of states.
methods (Savinov et al.) 2018
3 PRELIMINARIES
Goal Reaching We consider the goal reaching in an environment defined by the tuple (S, A, T. p(80); T, p(g)). S and A correspond to the state and action spaces respectively, T(d'ss, to the transition kernel, p(sp) to the initial state distribution, T the horizon length, and p(g) to the distribution over goal states g E S. We aim to find a time-varying goal-conditioned policy T (rlss.g g, h): S x S x [T] + ((A), where A(A) is the probability simplex over the action space A and h is the remaining horizon. We will say that a policy is optimal if it maximizes the probability the specified goal is reached at the end of the episode:
(xx gyypp) [Pr, (ST = 9)]
(1)
It is important note here that we are not considering the notion of optimality to be finding the shortest path to the goal, but merely saying that the trajectory must reach the goal at the end of T time-steps. This problem can equivalently be cast in reinforcement learning. The modified state space S = S x S x [I] contains the current state, goal, and the remaining horizon; the modified transition kernel T' ((s',g g', (hh)) (s,g, h). a) T(s' s.a) (d = d', N = - 1) appropriately handles the modified state space; and the reward function r((s, g. h)) = ((s (s= g. h = 0) depends on both the goal and the time step. Because of the special structure of this formulation, off-po RL methods can relabel an observed transition ((s, h), (s', .g. h - 1)) to that of different goal g' and different horizon h like ((x,g', hl',,, a, (8', h - 1)). A common approach is to relabel trajectories with the goal they actually reached instead of the commanded goal, and often referred to as hindsight experience replay (Andrychowicz et al. 2017 Nair et al. 2018).
Imitation Learning We consider algorithms for goal-reaching that use behavior cloning, a stan- dard method for imitation learning. In behavior cloning for conlicondi policies, expert policy provides demonstrations for reaching some target goals at the very last timestep, and we aim to find a policy that best predicts the expert actions from the observations. More formally,
3

---

Under review as a conference paper at ICLR 2020
given dataset D
{( ag. st. af. sf....].]] (s). ab. s1 ... ............ and set of stochastic, varying policies II, the behavior- policy corresponds to
TBC arg max (rr (oT
condicondi imitation learning (Lynch et al. 2019) investigate similar formalism that makes an additional assumption on the quality of the expert demonstrations: that the expert is optimal not just for reaching sT, but also optimal for reaching all the states 1.....8-1 preceding it. This corresponding policy is
TGCIL arg max (s [log no (aelss Sith, h)]
for t, h and t T. (2)
Note that Lynch et (2019) implement special case of this objective where the policy inde- pendent of the horizon. In the next section, we will discuss how repeatedly alternating between data collection and goal-conditioned imitation learning can be used learn goal-reaching policy. Perhaps surprisingly this procedure optimizes the objective in Equation I without relying on expert demonstrations.
LEARNING GOAL-CONDITIONS POLICIES WITH SELF-IMITATION
The goal-conditioned imitation learning results in prior work show that expert demonstrations can provide supervision not only for the task the expert was aiming for, but also for reaching any state along the expert's trajectory (Lynch al. 2019 Ding et al., 2019). Can we design procedure that uses coal-conditioned behavior cloning as a subroutine, that does not need any expert demonstra- tions, but that nonetheless optimizes a well-defined reward function?
In this work, we show how the idea of imitation learning with data relabeling can be re-purposed to construct learning algorithm that is able learn how to reach goals from scratch without any expert demonstrations. We shed light the reasons that imitation learning with data relabeling is so powerful, and how building an iterative algorithm out of this procedure gives rise to a method that optimizes lower bound benefits over standard RL algorithms. is important to note here that we are nor proposing an imitation learning algorithm, but an algorithm for learning how to reach goals from scratch without any expert demonstrations. We are simply leveraging ideas from imitation learning to build such goal reaching algorithm.
reinforcement learning objective, while providing number of
policy
goals
Behasioral cloning relaheled data
To (a s. B
[( dgj B) ... 0 ag,
BY
max E (xag))D log s,(aas,))
Ao
(s0 ai A)
D
Talals. C)
Figure 1;
Goal conditioned supervised learning: We can learn how to reach goals by simply sam- pling trajectories, relabeling them to be optimal in hindsight and treating them expert data, and then performing supervised learning via behavior cloning.
4.1 GOAL REACHING VIA ITERATED IMITATION LEARNING
First, consider goal conditioned imitation learning via behavioral cloning with demonstrations (Equation 2) This scheme works well given expert data D. but expert data is unavailable when we are learning to reach goals from scratch. Can we use goal conditioned behavior cloning to learn how to reach goals from scratch, without the need for any expert demonstrations?
4

---

Under review as a conference paper at ICLR 2020
To leverage behavior cloning when learning from scratch, arbitrary trajectory from a sub-optimal policy may be suboptimal for reaching the intended goal, may be optimal for reaching some other goal. In the goal-reaching formalism defined in Equation recall a policy is optimal if it maximizes the probability that the goal is reached at the last timestep of episode. This notion of optimality doesn't 't have take the direct shortest path to the goal, it simply has to eventually reach the goal. Under this notion of optimality, we can use a simple data relabeling scheme to construct an expert dataset from an arbitrary set of trajectories. Consider a trajectory т = {si, 41, $2, .2....,,........................ Sr, ar} obtained by commanding the policy To Fo(als.g g, h) to reach some goal g. Although the actions may be suboptimal for reaching the commanded goal g. they do succeed at reaching the states 84+1; 8t42,... that occur later in the observed trajectory. More precisely, for any timestep and horizon ht the action at in state 8, is likely to be a good action for reaching 8t+h in h timesteps, and thus useful supervision for me(-1s,, Si+h, h). This step of autonomous relabeling allows us to convert suboptimal trajectories into optimal goal reaching trajectories for different goals, without the need for any human intervention. To obtain concrete algorithm, we can relabel all such timesteps and horizons in trajectoryto create an expert dataset according to D,- {(st, de; S h) : t, h > 0, t h & T). Because the relabelling procedure is valid for any horizon h < T, we can relabel every such combination create (2) optimal tuples of (s, a, 9, h) from single trajectory.
the following insight: while an
This relabeled dataset can then be used to perform goal- goal-conditioned behavioral cloning to update the policy TT. While performing dataset is not immediately sufficient to reach all desired goals, we will show that this procedure does in fact optimize a lower bound on well-defined reinforcement learning objective. As described concretely in Algorithm] T the algorithm proceeds as follows: (1) Sample a goal from a target goal distribution p(g). (2) Execute the current policy I (a) s, g.h) h) for steps in the environment to collect a potentially suboptimal trajectory T. (3) Relabel the trajectory according to the previous paragraph to add (") new expert tuples (st, ae, Se+hh, h) to the training dataset. (4) Perform supervised learning on the entire dataset to update the policy (a) 8, 9, h) via maximum likelihood. We term this iterative procedure of sampling trajectories, relabelling them, and training a policy until convergence goal- conditioned supervised learning (GCSL).
iteration of goal conditioned behavioral cloning the relabeled
Algorithm Goal-Conditioned Supervised Learning (GCSL)
1: procedure GCSL
2: Initialize policy Ti (- 8,9, h) and dataset D((s, a, h))
3: for k == 3, do
4: Sample g ~ p(g) and execute गe in environment trying to reach g
5: Log trajectory = (5o, 4o, $1, ai..a........................... ST, aT)
6:
Add tuples (st, at, Sith, h) : it, 0, < T) to the dataset D Optimize the policy Th+1 + arg max,, B(s.a,g,)) [log To(a s.g. h)]
7:
8:
end for end procedure
9:
The GCSL algorithm (described above) provides us with algorithm that can learn to reach goals from the target distribution p(g) simply using iterated behavioral cloning. The resultant goal reach- ing algorithm is off- off-policy, uses low variance gradients, and is simple to implement and tune without the need for any explicit reward function engineering or demonstrations. Additionally, since this algorithm is off-policy and does require value function estimator, it is substantially easier to bootstrap from demonstrations when real demonstrations are available, as our experiments will show in Section 5.4
4.2 THFORETICAL JUSTIFICATION
While the GCSL. algorithh is simple to implement, does this algorithm actually solve a well-defined policy learning problem? In this section, we argue that GCSL. maximizes lower bound on the probability for a policy to reach commanded goals.
We start by writing the probability that policy æ conditioned on goal g produces trajectory as (Tlg)) p(so) IT (acest, g, h)T at). We define G(T) sT final state of trajec-
5

---

Under review as a conference paper at ICLR 2020
tory. Recalling Equation|] | the target goal-reaching objective wish maximize is the probability of reaching a commanded goal:
[Prg (sT =9)] E g~r(g). (xx E (g))())
[1[ øll T~<((19))
In the language of reinforcement learning, we are optimizing a multi-task problem where the reward in each task is an indicator that a goal was reached. The distribution over tasks (goals) of interest is assumed be pre-specified as p(g). the on-poliey setting, GCSL performs imitation learning on trajectories commanded by the goals that were reached by the current policy, an objective that can be written as
JGCSL (T)) = Er (ooe log π (arlst, ())
Here, Wold corresponds copy of a through which gradients do not propagate, following the notation SfShullmnn et al. (2015). Our main result, which is derived in the on-policy data collection setting, shows that optimizing (GC)L(T) optimizes a lower bound on the desired objective, ((T) (proof in Appendix B
Theorem 4.1. Let JGCSL and J be as defined above. Then, ( 2 Jocs((T) ) + C, Where C is constant that does not depend on и.
Note that to prevent ((T) and Jacsı (T)) from being zero, the probability of reaching goal under must be nonzero- scenarios where such condition does not hold, the bound remains true, albeit vacuous. The tightness of this bound can be controlled by the effective error in the GCSL objective we present this, alongside a technical amalysis the bound Appendix [B.] This indicates that in the regime with expressive policies where the loss function be minimized well, GCSL will improve the expected reward.
EXPERIMENTS
In our experimental evaluation, we aim to answer the following questions:
1. Does GCSL effectively learn cond-conditioned policies from seratch?
2. Does the performance of GCSL improve over successive iterations?
3. Can GCSL learn goal-conditioned policies from high-dimensional image observations?
4. Can GCSL incorporate demonstration data more effectively than standard RL algorithms?
5.1 EXPERIMENTAL DETAILS
We consider a number of simulated control environments: 2-D room navigation, object pushing with robotic arm, and the classic Lunar Lander game, shown in Figure The tasks allow to study the performance of our method under a variety of system dynamics, both low-dimensional state inputs and high-dimensional image observations, and in settings with both easy and difficult exploration. For each task, the target goal distribution corresponds to uniform distribution over all reachable configurations. Performance of method is quantified by the distance of the agent to the goal at the last timestep (not by the number of time-steps to the goal as is sometimes considered in goal reaching). We present full details about the environments, evaluation protocol, and hyperparameter choices in Appendix A
For the practical implementation GCSL, we parametrize the policy as neural network that takes in state, goal, and horizon as input and outputs parametrized action distribution. We find that omitting the horizon from the input to the policy still provides good results, despite the formulation suggesting that the optimal policy is most likely non-Markovian. We speculate that this is due to optimal actions changing only mildly with different horizons in our tasks. Full details about the implementation for GCSL are presented in Appendix A.1 A.1

---

Under review as a conference paper at ICLR 2020
Figure 2: Evaluation Tasks: For each of the following tasks, evaluate algorithm using low- dimensional sensory data and pixel observations: (Left) 2D Navigation, (Center) robotic pushing, and (Right) Lunar Lander.
Four Rooms: Average Final Distance
Baxyer Pasling Avarage Disliaco
Luner Lander Average Final Distance
6C24
0.14
90
Enetonment
Envioerart
Envioement Slips
Figure 3: State-based tasks: GCSL is competitive with state-of-the-arr off-policy value function RL algorithms for goal-reaching from low-dimensional sensory observations. Shaded regions denote the standard deviation across 3 random seeds (lower is better).
5.2 LEARNING GOAL-CONDITIONEL) POLICIES
We evaluate the effectiveness of GCSL for reaching goals on the domains visualized in Figure both from low-dimensional proprioception and from images. To better understand the performance of our algorithm, we compare to two families of reinforcement learning algorithms for solving goal- conditioned tasks. First, we consider off-policy temporal-differene RI. algorithmss particular TD3- HER (Eysenbach et al. 2019 Held et al. 2018), which uses hindsight experience replay to more efficiently learn goal-conditioned value functions. TD3-HER requires significantly more machinery than our simple procedure: it maintains policy, value function, a target policy, and a target value function, all which are required to prevent degradation of the learning procedure. We also com- pare with on-policy reinforcement learning algorithms such as TRPO (Schulman et al.) (015)) that cannot leverage data relabeling, but often provide more stable optimization than off-policy meth- ods. Because these methods cannot relabel data, provide epsilon-ball reward corresponding to reaching the goal. Details for the training procedure for these comparisons, along with hyperpa-
Average Distance
Savyer Pushtngg Avarage Final Distance
Lunar Lander: Average Firal Distance
1.15
103
3.
8:10
8.50
5 50090 133000 150080 20000 250000 X003
200000 400000
600000 000000 100000
100000
25300
30008
400000
Entirmeen Saga
DevEORMeT: Stipa
Dnviriment Staze
Figure 4: Image-based tasks: On three tasks with image observations, GSCL achieves similar performance to a sfatc-of-the-ar baseline, TD3, while being substantially simpler. Shaded regions denote the standard deviation across 3 random seeds (lower is better).
7

---

Under review as a conference paper at ICLR 2020
rameter and architectural choices, are presented in Appendix A.2 Videos and further details can be found at wtthttps:/// sttp://sstsssstte google. www./iociiiiiiieeei www./////ww///e/ooeoo..e/..w.eee gcsl/
We first investigate the learning performance of these algorithms from low-dimensional sensor ob- servations, as shown in Figure 3 We find that on the pushing and lunar lander domains, GCSL is able to reach a larger set of goals consistently than either RL algorithm. Although TD3 is able to fully solve the navigation task, on the other domains which require synthesis of more challenging control behavior, the algorithm makes slow, if any, learning progress. Given a limited amount of data, TRPO performs poorly as it cannot relabel or reuse data, and so cannot match the performance of the other two algorithms. When scaling these algorithms to image-based domains, which we evaluate in Figure 4 we find that GCSL is still able to learn goal-reaching behaviors on several of these tasks. albeit slower than from state. For most tasks, from both state and images, GCSL, is able to reach within 80% of the desired goals and learn at rate comparable to or better than previously proposed off- aff-policy RL. methods. This evaluation demonstrates that simple iterative self-imitation is a competitive scheme for reaching goals in challenging environments which scales favorably with dimensionality of state and complexity of behaviors.
5.3 ANALYSIS OF LEARNING PROGRESS AND LEARNED BEHAVIORS
To better understand the learning behaviors of the algorithm, we investigate how GCSL performs as we vary the quality and quantity of data, the policy class optimize over, and the relabelling technique (Figure 5). Full details for these scenarios can be found in Appendix A.4
First, consider how varying the policy class can af- fect the performance of GCSL. In Section 5.T we hy- pothesized that optimizing over Markovian policy class would be performant over maintaining a Mon-Markovian policy. We find that allowing policies be time-varying ("Time- ("Time-Varying Policy" in 5) can drastically speed up training on small domains, as these non-Markovian optimal policies can be fit more closely. However, on domains with active exploration challenges such as the Pusher, exploration using time-varying policies is inef- fective, and degrades performance.
Sawyer Pushing: Average Final Distance
0.18
0.14
Decancee
0.10
Flees Data Collection
Irantss Modil
0.04
Time Varying Poliy
200000
400006
603000 SC0000 1000000
Envroonmnt
We investigate how the quality of the data in the dataset used to train the policy affects the learned policy. We consider two variations of GCSL: one which collects data using a fixed policy ("Fixed Data Collection" in Figure 5) and another which limits the size of the dataset to be small, forcing all the data to be on-policy ("On-Policy" in Figure 5) When collecting data using a fixed policy, the learning progress of the algorithm demonstratedly decreases, which indicates that the iterative loop of collecting data and training the policy is crucial for converging to a performant solution. By foreing the data to be all on-policy, the algorithm cannot utilize the full set of expe- riences seen thus far and must discard data. Although this on-policy process remains effective on simple domains, the technique leads slower learning progress on tasks requiring more challenging control.
Figure 5: Performance across variations of GCSL (Section 5.3) for the pushing domain. Plots for other domains in Ap- pendix A.4 A.4
5.4 INITIALIZING WITH DEMONSTRATIONS
Because GCSL can perform self-imitation from arbitrary data sources, the algorithm is amenable to initialization from prior exploration or from demonstrations. In this section, we study how GCSI, performs when incorporating expert demonstratinns as initializations. Our results comparing GCSL and TD3 in this setting corroborate the existing hypothesis that off-policy value function RL algo- rithms are challenging integrate with initialization from demonstrations Kumar al. (2019a).
We consider the setting where an expert provides a set of demonstration trajectories, each for reach- ing a different goal. GCSL requires no modifications to incorporate these demonstrations - it simply adds the expert data to the initial dataset, and begins the training procedure. In contrast, multiple prior works have proposed additional algorithmic changes off-policy TD-baaed methods in-
8

---

Under review as a conference paper at ICLR 2020
corporate data from expert demonstrations (Kumar al. 2019a). We compare the performance of GCSL to one such variant of TD3-HER in incorporating expert demonstrations on the robotic push- ing environment in Figure 6 (Details in Appendix A.5) Although TD3 achieves better performance with the demonstrations than when learning from scratch, it drops in performance at the beginning of training, which means TD3 regresses from the initial behavior-cloned policy, an undesirable char- acteristic for initializing from demonstrations. In contrast, GCSL scales favorably, learns faster than from scratch, and effectively incorporates the expert demonstrations, We believe this benefit largely comes from not needing to train an explicit critic, which can be unstable when trained using highly off- off-policy data such as demonstrations (Kumar et al. 2019b).
DISCUSSION AND FUTURE WORK
In this work, we proposed GCSL, simple algorithm for learning goal-conditioned policies that uses imitation learning, while still learning autonomously from scratch. This method is exceptionally simple, relying entirely on supervised learning learn policies by relabeling its own previously collected data. This method can easily utilize off-policy data, seamlessly incorporate expert demonstra- tions when they are available, and can learn directly from image observations. Although several prior works have explored similar algorithm designs in imitation learn- ing setting (Ding et al.] 2019) Lynch et al.) 2019). to our knowledge work is the first derive complete it- erated algorithm based on this principle for learning from scratch, and the first theoretically show that this method optimizes lower bound on well-defined reinforcement learning objective.
with Average
0.12
GCS
TDS
(m)
0.00
012
Figure 6: Initializing from Demon- strations: GCSL is more amenable to initializing using expert demonstrations than value-function RL. methods.
While our proposed method is simple, scalable, and readily applicable, it does have a number of limitations. The current instantiation of this approach provides limited facilities for effective explo- ration, relying entirely on random noise during the rollouts to explore. More sophisticated explo- ration methods, such exploration bonuses (Mohamed & Rezende, 2015 Storek et al., 1995). are difficult to apply our method, since there is no explicit reward function that is used during learning. However, a promising direction for future work would to reweight the sampled rollouts based on novelty to effectively incorporate novelty-seeking exploration procedure. A further direction for future work is to study whether the simplicity and scalability of our method can make it possible to perform goal-conditioned reinforcement learning substantially larger and more varied datasets. This can in principle enable wider generalization, and realize a central goal in goal-conditioned reinforcement learning universal policies that can succeed wide range of tasks in diverse environments.
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abheel, and Wojeiech Zaremba. Hindsight experience play. In Advances in Neural Information Processing Systems, pp. 5048-5058, 2017.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Aude Billard, Sylvain Calinon, Ruediger Dillmann, and Stefan Schaal. Robot programming by demonstration. Springer handbook of robotics, pp. 1371-1394, 2008
Daniel S Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Nickum. Extrapolating beyond sub- optimal demonstrations via inverse reinforcement learning from observations. arXiv preprint arXiv: 2019.
Yiming Ding, Carlos Florensa, Mariano Phiclipp, and Pieter Abbeel. Goal conditioned imitation learning. In Advances in Neural Information Processing Systems, 2019.

---

Under review as a conference paper at ICLR 2020
Benjamin Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridg- ing planning and reinforcement learning. arXiv preprint arXiv:1906.05253, 2019.
Scott Fujimoto, David Meger, and Doina Precup. Off- Off-policy deep reinforcement learning without exploration. arXiv preprint
022900, 2018.
Sergiu Goschin, Ari Weinstein, and Michael Littman. The cross-entropy method optimizes for quantiles. In International Conference on Machine Learning, pp. 1 1193-1201, 2013.
David Held, Xinyang Geng, Carlos Florensa, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. 2018.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Thirty-Second AAAI Conference on Artificial Intel- ligence, 2018.
Todd Hester, Matej Vecerik, Olivier Pietquin, Mare Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, et al. Deep q-learning from demonstrations, In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne, Imitation learning: survey of learning methods. ACM Computing Surveys (CSUR), 50(2):21, 2017.
Leslie Pack Kaelbling. Learning to achieve goals. In International Joint Conference on Artificial Intelligence (ICCA)), pp. 1094-1098, 1993.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, ICML '02, pp. 267-2744 San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc. ISBN 1-55860- 873-7. URL acm www.:/a...................aa..aa wwtpg/iitaaiiioooooo wttpaatiii.........mmmm.m.m. wtt.eemmmmmm1.11.. 656005
Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. CoRR, abs/1906.00 19066009999 2019a.
Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off- off-policy q-learning via bootstrapping error reduction. arXiv preprint trXiv:/906.00940 2019b.
Timothy Lillicrap. Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint wrXivv1509.02977 2015.
Corey Lynch, Mohi Khansari, Ted Xiao, Vikash Kumar, Jonathan Tompson, Sergey Levine, and Pierre Sermanet. Learning latent plans from play. arXiv preprint
2019.
Shie Mannor, Reuven Y Rubinstein, and Yohai Gat. The cross entropy method for fast policy search. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 512- 519, 2003.
Borislav Mavrin, Shangtong Zhang, Hengshuai Yao, Linglong Kong, Kaiwen Wu, and Yaoliang Yu. Distributional reinforcement learning for efficient exploration. arXiv preprint arXiv:1905: 1905.06155. 2019.
Shakir Mohamed and Danilo Jimenez Rezende. Variational information maximisation for intrinsi- cally motivated reinforcement learning. In Advances in neural information processing systems, pp.
2015.
Ofir Nachum, Mohammad Norouzi, and Dale Schuurmans. Improving policy gradient by exploring under-appreciatedd rewards. arXiv preprint arXiv: I
2016.
Ashvin V Nair, Vitchyr Pong, Murtaza Dalal, Shikhar Bahl, Steven Lin, and Sergey Levine. Vi- sual reinforcement learning with imagined goals. Advances in Neural Information Processing Systems, pp. 9191-9200, 2018.
10

---

Under review as a conference paper at ICLR 2020
Mohammad Norouzi, Samy Bengio, Navdeep Jaitly, Mike Schuster, Yonghui Wu, Dale Schuurmans, et al. Reward augmented maximum likelihood for neural structured prediction. In Advances In Neural Information Processing Systems, pp. 1723-1731, 2016.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. In International Conference on Machine Learning, pp. 3875-3884, 2018.
Deepak Pathak, Parsa Mahmoudieh, Guanghao Luo, Pulkit Agrawal, Dian Chen, Yide Shentu, Evan Shelhamer, Jitendra Malik, Alexei A Efros, and Trevor Darrell. Zero-shot visual imitation. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition Workshops, pp. 2050-2053, 2018.
Jan Peters and Stefan Schaal. Reinforcement learning by seward-weighted regression for operational space control. In Proceedings of the 24th international conference Machine learning, pp. 745- 750. ACM, 2007.
Dean A Pomerleau. Alvinn: An autonomous land vehicle in a neural network. In Advances in neural information processing systems, pp. 305-313, 1989.
Vitchyr Pong. Shixiang Gu, Murtaza Dalal, and Sergey Levine. Temporal difference models: Model- free deep rl for model-based control. arXiv preprint arXiv:1802.09081, 2018.
Aravind Rajeswaran, Vikash Kumar, Abhishek Gupta, Giulia Vezzani, John Schulman, Emanuel Todorov, and Sergey Levine. Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. arXiv preprint arXiv: vrXXiv:/709 1709. 2017.
Stephane Ross, Geoffrey Gordon, and Drew Bagnell. reduction of imitation learning and struc- tured prediction to no-regret online learning. In Geoffrey Gordon, David Dunson, and Miroslav Dudk (eds.), Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 627 Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR. URLitttp://pxcceeiinng .mlr mll., press/ v15/rosslla. html
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametric topological memory for navigation. arXiv preprint 18X3000003.0653 2018.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxima- tors. In International conference on machine learning, pp. 13200, 2015.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning. volume 37 of Proceedings of Machine Learning Research, pp- 1889-1897, Lille, France, 07-09 Jul 2015. PMLR.
Jan Storck, Sepp Hochreiter, and Jürgen Schmidhuber. Reinforcement driven information acquisi- tion in non-deterministic environments. In Proceedings of the international conference on artifi- cial neural networks, Paris, volume pp. 159-164. Citeseer, 1995.
Evangelos Theodorou, Jonas Buchli, and Stefan Schaal. A generalized path integral control ap- proach to reinforcement learning. journal of machine learning research, 11NNvv)3137-31111 2010.
John N Tsitsiklis and Benjamin Van Roy. Analysis of -efporal-diffference learning with function approximation. In Advances in neural information processing systems, pp. 1075-1081, 1997.
11

---

Under review as a conference paper at ICLR 2020
A EXPERIMENTAL DETAILS
A.1 GOAL-CONDITIONED SUPERVISED LEARNING (GCSL)
GCSL iteratively performs maximum likelihood estimation using a dataset of relabelled trajectories that have been previously collected by the agent. Here we present details about the policy class, data collection procedure, and other design choices. We parametrize time-invariant policy using a neural network which takes as input state and goal, and returns probabilities for discretized grid of actions of the action space. For the state-based domains, the neural network is a feedforward network with two hidden layers of size 400 and 300 respectively. For the image-based domains, both the observation image and the goal image are first preprocessed through three convolutional layers, with kernel size 5, 3, 3 and channels 16, 32, 32 respectively. When executing in the environment, data is sampled according to exploratory policy which increases the temperature of the current policy: Tesplore (a|s, g) x (als,, g)" The replay buffer stores trajectories and relabels on the fly, with the size of the buffer subject only to memory constraints.
A.2 RL COMPARISONS
We perform experimental comparisons with TD3-HER (Fujimoto et al. 2018 Andrychowicz et al. 2017). We relabel transitions as ((s,g) g), , a. (s', .)) gets relabelled to ((s, g a, (s', .g)),, where g' with probability 0.1, g = s' with probability 0,5, and g' = for some future state in the trajectory 8, with probability 0.4. As described in Section 3 the agent receives reward of and the trajectory ends if the transition is relabelled to g' = s', and 0 otherwise. Under this formalism, the optimal Q- function, Q * (s, a. g) = (xp(-T((ss [s, 9)). where T(s,g) is the minimum expected time to go from to g. Both the Q- Q-function and the actor for TD3 are parametrized as neural networks, with the same architecture (except final layers) for state-based domains and image domains as those for GCSI..
We also compare to TRPO (Schulman et al., 2015). an on-policy RI. algorithm. Because TRPO is on-policy, we cannot relabel goals, and so we provide a surrogate e-ball indicator reward function: r(s,g) g) I(d(s,g) g) < E). where is chosen appropriately for each env environment. To maximize the data efficiency of TRPO, we performed a coarse hyperparameter sweep over the batch size for the algorithm. Just with TD3, we mimic the same neural network architecture for the parametrizations of the policies as GCSL.
A.3 TASK DESCRIPTIONS
For each environment, the goal space is identical the state space. For the image-based experi- ments, images were rendered at resolution 84 x 84 x 3.
2D Room Navigation This environment requires an agent navigate to points in environment with four rooms that connect to adjacent rooms. The state space has two dimensions, consisting of the cartesian coordinates of the agent. The agent has acceleration control, and the action space has two dimensions. The distribution of goals p(g) is uniform on the state space, and the agent starts in a fixed location in the bottom left room.
This environment requires a Sawyer manipulator to move freely moving block in an enclosed play area with dimensions 40 em 20 em. The state space is 4-dimensional, consistsing of the cartesian coordinates of the end-effector of the sawyer agent and the cartesian coordinates of the block. The Sawyer controlled via end-effector position control with a three- dimensional action space. The distribution of goals p(g) is uniform on the state space (uniform block location and uniform end-effector location), and the agent starts with the block and end-effector both in the bettom-left corner of the play area.
Robotic Pushing
Lunar Lander This environment requires a rocket to land in a specified region. The state space includes the normalized position of the rocket, the angle of the rocket, whether the legs of the rocket are touching the ground, and velocity information. Goals are sampled uniformly along the landing region, either touching the ground hovering slightly above, with zero velocity.
12

---

Under review as a conference paper at ICLR 2020
A.4 ABLATIONS
In Section 5.3 we analyzed the performance of the following variants of GCSL (Figure
1. Inverse Model This model relabels only states and goals that are one step apart: {[St, at, St+h. h) i 0, h = 1}
2. On-Policy Only the most recent 10000 transitions are stored and trained on.
3. Fixed Data Collection Data collected according to uniform policy over actions.
4. Time- Time-Varying Policy Policies are are conditioned on the remaining horizon. Alongside the state and goal, the policy gets reverse temperature encoding of the remaining horizon as input.
Four Rooms: Average Sucoess Ratio
Sawyer Pushing Average
Linder Average D'stenne
1.3
0.4
MCAL Data Collccion
+800 (009)
190300
18000
100000
15005
20000
Figure 7: Performance across variations of GCSL (Section 5.3) for all three experimental domains.
A.S INITIALIZING WITH DEMONSTRATIONS
We train expert policy for robotic pushing using TRPO with shaped dense reward function, and collect a dataset of 200 trajectories, each corresponding to a different goal. To train GCSL using these demonstrations, we simply populate the replay buffer with these trajectories the beginning of training, and optimize the GCSL objective using these trajectories to warm-start the algorithm. Initializing a value function method using demonstrates requires significantly more attention: we perform the following procedure. First, we perform goal-conditioned behavior cloning to learn an initial policy тBC. Next, we collect 200 new trajectories in the environment using a uniform data collection scheme. Using this dataset of 400 trajectories, perform policy evaluation learn Q using policy evaluation via bootstrapping. Having trained such an estimate of the Q- function, initialize the policy and Q-function to these estimates, and run the appropriate value function RL algorithm.
TBC to
B PROOF OF THEOREM 4.
We will assume discrete state space in this proof, and denote trajectory as {so, ao...., -T, ).). Let the notation G(T) = sT denote the final state of a trajectory, which represents the goal that the trajectory reached. As there can be multiple paths goal, we let Ty = (r G(T) g} denote the set of trajectories that reach a particular goal g. We abbrevi- a policy's 's traeectory distribution as T([lg) p(so) I (a, (ss, goal-reaching objective we wish to optimize is the probability of reaching a commanded goal,
az). The target
((x) ( [9()) =-]]
The distribution over tasks (goals) assumed to be pre-specified p(g). GCSL optimizes the fol- lowing objective, where the lig-likel of the actions conditioned on the goals actually reached by the policy, G(r):
JOCSL (Eaw,,(rutt(lll))
Σ log TT (aols 9(7))
13

---

Under review as a conference paper at ICLR 2020
Here, using notation from Schulman et al. (2015), Told is copy of the policy through which gradients do not propagate. To analyze how this objective relates to [TT), we first analyze the relationship between (T)) and surrogate objective, given by
(T) = Eggpp(e)
Σ TET
Toda(T)))oog((() (
As (T) and (TT) have the same gradient for all n, the differ by some r-independent constant C1, i.. [TT) = (T) + C1.
We can now lower-bound the surrogate objective via the following:
Jaur (T) Eggp((s)
Σ
Told (T(g) ((1l))))))
rETu
Egrp(e)
Σ 1(g(T) = m/ logg(((9))))
-Erls p(g) Σ log 1og
gl
Σ log ((((()))
(p(0) = =gl
9
Σ logg(+1((7)) ((g) P E log क( ((T)) (7))) *
9
Σ log llgg((((((T) Σ plo)
g
B (Faa(Tla)) [log (T))()))
The final line goal-relabeling objective: we train the policy reach goals reached g'. The inequality holds since log (T) is always negative. The inequality is loose by a term related to the probability of not reaching the commanded goal.
Since the initial state and transition probabilities do not depend on the policy, we can simplify log (T()(TT) as (by absorbing non rddependent terms into Cz):
T
E, (ota( T (T[G(T))) (x
log Σ
log (anlss,, + log T (88411(18)) at)
En log n (a (a))) + +C²
JoCSL (T) C2.
Combining this result with the bound on the expected return completes the proof, namely that (Tx) JGCSL(M) + C1 + Cz. Note that in order for J(TT) and JeasI (T) be degenerate, the probability of reaching goal under oold must be non-zero. This assumption is reasonable, and matches the assumptions on "exploratory data-collection" and full-support policies that are required by Q-learning and policy gradient convergence guarantees.
B.1 QUANTIFYING THE QUALITY OF THE APPROXIMATION
We now seek to better understand the gap introduced by Equation in the analysis above. We define P Prate (G(T) # 9) to be the probability of failure under Wold and p(g). We overload the notation Total (T) Eg (T (g))), and additionally define Parong (r) and Pright (Te conditional distribution of trajectories under Wold given that it did reach and did the commanded goal respectively.
14

---

Under review as a conference paper at ICLR 2020
In the following section, we show that the gap can be controlled by the probability of making mistake, Praz (9(T) # g). and Drv (Pwrong (T), Prigh(7) (T)), a measure of the difference between the distribution of trajectories that must be relabelled and those not.
We rewrite Equation as follows:
Jsurr (TT Σ log logg((((((T))
Σ p(g)TTua(T(g)) ( -
_ E1og ( Σ (Tdd)) +
Bi [ Paoia (9(T) # 9)) E Br-ppne (T) [lgg((((((7))
Define D be the Radon-Nikodym derivative of Perong( (T) wrt Told(T)
Browsat [log (T]((() - Pasia (G(()= # g)) Ma (Dlogm(TI91))
=(1 (1- --Pra Pruis (9(7) # g) B)) log T (T]
+ Paota (G(T) A 9)) Er-ToIa [[1 D) log (T][(T))]
Relevant Gap
The first term affine with respect to the GCSL loss, so the second term is the error we seek to understand.
|Relevant Gapl
= Prucs (g(T) # g) Eronoo [1 D) log x (F[
< Pruce (9(T) g) ||1 D P (log क (T(
= =2P ( (g(T) + D)v (()[oo((T(())))))) Perong (T)) B Broxata (log π (T|g(TT))
2P (g(T) * g)( Pa (9( * gr) (Priha(T) Perony (T)) Dlgga
The inequality is maintained because of the nonpositivity of 1og=(7), and the final step holds be- cause (T) is a mixture of Porong (T) and (T). This derivation shows that the gap between Jsurr and JGosL (up to affine consideration) can be controlled by 1) the probability of reaching the wrong goal and 2) the divergence between the conditional distribution of good trajectories and those which must be relabelled. As either term goes to O, the bound becomes tight.
We now show that sufficiently optimizing the GCSL objective causes the probability of reaching the wrong goal to be bounded close O, and thus bounds the gap close
Suppose we collect trajectories from policy Tdata- Mimicking the notation from before, we define Tadata
1yyp()) datt (T [g)]- For convenience, we define x Taata (ay/st, g) x Sria, Taata (G) = g))(<>(T)= = 8t) to be the conditional distribution of actions for given state given that the goal is reached at the end of the trajectory. If this conditional distribution is not defined, let mdata (at (s).)) be uniform, that Tuata (a, (8: g) is well-defined for all states, goals, and timesteps.
Lemma B.1. Consider an environment with deterministic dynamics in which all goals are reachable in T timesteps, and a behavior policy vaato which is exploratory: (auta(a,) st, >> 0f all (a, s, g) (for example pyillon-greed exploration). Suppose the GCSL objective is sufficiently optimized, so that for all 8,9 g S, and time-steps E (1...., T), Dry (T(ae)st, g), Taata (ae)st, 9)) S
Then, the probability of making a mistake (G(T) + g) can be bounded above by eT
Proof. We show the result through a coupling argument, similar to Schulman et (0015) Kakade
& Langford 2 Ross et al. (201)). Because Drv (I (aelst,, g), Taata (0e| g)) < we can define (1 co-upee policy pair (T,, (dtta), which takes differing actions with probability By union bound over all timesteps, the probability that मे and Tigto take any different actions throughout the trajectory is bounded by él', and under assumptions of deterministic dynamics, take the same trajectory with probability 1 cT. Under assumption of deterministic dynamics and all goals being reachable from the initial state distribution in T timesteps, the policy æ Tatto (ay ss, g) satisfies P P=:... (9(7) A g) 0. Because Tdata reaches the goal with probability 1, this implies that must also reach the goal with probability at least 1 eT. Thus, Px (G(T) # g) S eT.
n
15

---

Under review as a conference paper at ICLR 2020
C EXAMPLE TRAJECTORIES
Figure 8 below shows parts of the state along trajectories produced by GCSL. In Lunar Lander, this state is captured by the rocket's position, and in 2D Room Navigation the agent's position. While these trajectories do not always take the shortest path to the goal, they do often take fairly direct paths the goal from the initial position avoiding very roundabout trajectories.
Figure 8: Examples of trajectories generated by GCSL for the Lunar Lander and 2D Room environ- ments. Stars indicate the goal state.
16


Reviews:
[{"review_id": "S1xCmqT0tB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method to learn to reach goals in an RL environment. The method is based on principles of imitation learning. For instance, beginning with an arbitrary policy that samples a sequence of state-action pairs, in the next iteration, the algorithm treats the previous policy as an expert by relabeling its ending state as a goal. The paper shows that the method is theoretically sound and effective empirically for goal-achieving tasks. \n\nThe paper is relatively clear and experiments are okay. I would then recommend it is on the positive side of the borderline.\n\nComments:\n* The method is interesting but is still an \"RL\" method. So it is really learning to reach the goal via \"RL\". Note that in the method, the algorithm is not doing effective exploration but just randomly explore until you collect sufficient data to solve for a new goal. \n* If you formulate the problem better, you can see that it actually has a reward: add an initial state s0; for each g sampled from p(g), transition s0 to an MDP with goal g. You can now do the usual RL algorithm in this new MDP. I would think you can also do model-based learning -- give the model a good representation and then use the policies to learn the dynamics. It may worth to compare your algorithm with these natural baselines.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xKkYT3tS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work presents the goal-conditioned supervised learning algorithm (GCSL), which learns goal conditioned policies using only behavioral-cloning of the agent's own actions.  The intuition behind the algorithm is the goal of an observed trajectory can be identified after the fact, by simply looking at the states reached during that trajectory.  GCSL treats each executed action as a sample from the expert policy conditioned on each of the states reached after that action is taken.  Given a distribution over goal states, GCSL alternates between executing its current goal-conditioned policy on randomly selected goals, and learning to imitate the generated actions conditioned on the states they actually reached.  Experimental results demonstrate superior performance against a base (non-goal conditioned) RL algorithm (TRPO), and against another approach to learning goal-conditioned polices (TD3-HER), on a relatively diverse set of control problems.\n\nA major issue is that the proof of the main theoretical result appears to be wrong.  As there don't appear to be any constraints placed on the policy pi_old, it would seem that the surrogate loss would collapse to 0 for any policy pi if pi_old is such that the target goal is never reached (the probability of any trajectory t reaching g is 0 under pi_old(t|g)).  It seems to be the case that the quality of the GCSL loss depends on the relationship between pi_old and the goal distribution p(g).  The fact that the theoretical results are incorrect does not mean that the algorithm, or the general approach do not have value, but it does highlight the fact that this approach may only be effective for a specific class of problems similar to the experimental domains.\n\nWhile not a flaw in the work itself, it should be made clear in the text that the notion of optimality for the learning tasks considered in this work (i.e. achieving the goal by the end of episode), avoids one of the apparent limitations of the algorithm.  A randomly generated trajectory is itself optimal for any state that it reaches, if we define optimality as simply reaching a state.  Such a trajectory may not be the most efficient way of reaching that state however, so the relabelling process would seem to be prone to learning policies that achieve the conditioned goals, but not doing so in an efficient manner.  It isn't clear how well this approach would work for tasks where the efficiency, in terms of the time required to reach the objective, is a key part of the evaluation.  Again, this is not a flaw in the work itself, and it is possible that the algorithm will be effective in such tasks, perhaps because the likelihood of an action resulting in a given state is higher if that action brings us closer to this state.  It might be useful to conduct some additional experiments where evaluation is based on the time required to solve a task, rather than just the accuracy of the final state.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1e5iMfpYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper claims to do imitation learning without expert demonstration using trajectories that are generated by suboptimal policies from other tasks.\n\nThe point of having an expert demonstrator is to help narrow the search for an optimal policy.  By taking the expert demonstration knowledge out of learning, to me, this is not retaining the benefit of imitation learning.  Thus, the paper is not about imitation learning, but rather about an optimization method that reuses data generated from multiple tasks.   Reusing trajectory data generated from multiple tasks to learn a policy of another task is not a novel idea.  If we could save all of the data regardless of whether if an optimal policy generates them or not, why not use them?  Less useful data may still contain useful information.  The better question is how to use them to learn policy efficiently.  If the motivation is to use trajectories from suboptimal policies from other tasks without expert knowledge, then I fail to see the motivation and the novelty of this paper. \n\nThe paper claims that the methodology self-supervises each action taken, judging how good it is for reaching a goal in the future without learning Q-values.  However, this was not realized.  The methodology gathers all trajectories that reach a goal into a set, and use behaviour cloning on the data of the set to learn a policy.  The sampled trajectories in the set could be suboptimal for reaching a goal, and there’s little evidence that optimizing J_GCSL(\\pi) will learn an optimal policy based on these data.  Optimizing objective J_GCSL(\\pi) also does not take the long term effect of actions into account.  The gathering of trajectories and identifying the trajectory as goal-reaching is already a costly step, where no learning happens.  RL, on the other hand, would gather the data incrementally, learn, and act right away.  Also, it seems that the algorithm would require human knowledge to discern a trajectory as goal-reaching or not, which is contrary to self-supervision.  ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present an algorithm that utilizes ideas from imitation learning to improve on goal-conditioned policy learning methods that rely on RL, such as hindsight experience replay.  Several issues of clarity and the correctness of the main theoretical result were addressed during the rebuttal period in way that satisfied the reviewers with respect to their concerns in these areas.  However, after discussion, the reviewers still felt that there were some fundamental issues with the paper, namely that the applicability of this method to more general RL problems (complex reward functions rather than signle state goals, time ) is unclear.  The basic idea seems interesting, but it needs further development, and non-trivial modifications, to be broadly applicable as an approach to problems that RL is typically used on.  Thus, I recommend rejection of the paper at this time.
Decision: Reject