Solving Compositional Reinforcement Learning Problems via Task Reduction
Authors: Yunfei Li
Yilin Wu
Huazhe Xu
Xiaolong Wang
Yi Wu
Venue: ICLR 2021 Poster (2021)
Keywords: compositional task
sparse reward
reinforcement learning
task reduction
imitation learning

Abstract: We propose a novel learning paradigm, Self-Imitation via Reduction (SIR), for solving compositional reinforcement learning problems. SIR is based on two core ideas: task reduction and self-imitation. Task reduction tackles a hard-to-solve task by actively reducing it to an easier task whose solution is known by the RL agent. Once the original hard task is successfully solved by task reduction, the agent naturally obtains a self-generated solution trajectory to imitate. By continuously collecting and imitating such demonstrations, the agent is able to progressively expand the solved subspace in the entire task space. Experiment results show that SIR can significantly accelerate and improve learning on a variety of challenging sparse-reward continuous-control problems with compositional structures. Code and videos are available at https://sites.google.com/view/sir-compositional.

Published as a conference paper at ICLR 2021
SOLVING COMPOSITIONAL REINFORCEMENT LEARN- ING PROBLEMS VIA TASK REDUCTION
Yunfei Li Yilin Wu², Huazhe Xu², Xiaolong Wang", Yi Wul
Institute for Interdisciplinary Information Sciences, Tsinghua University
2 Shanghai Qi Zhi Institute," UC Berkeley, 4 UCSD
# 1liyf20@mml @m i 1s. t tsinghua. edu. cn, ijxwuyi gma iileilaaa com
ABSTRACT
We propose novel learning paradigm, Self-Imitation via Reduction (SIR), for solving compositional reinforcement learning problems. SIR is based on two core ideas: task reduction and self-imitation. Task reduction tackles hard-to-solve task by actively reducing it to an easier task whose solution is known by the RL agent. Once the original hard task is successfully solved by task reduction, the agent naturally obtains a self-generated solution trajectory to imitate. By continuously collecting and imitating such demonstrations, the agent is able progressively expand the solved subspace in the entire task space. Experiment results show that SIR can significantly accelerate and improve learning variety of challenging sparse-reward continuous-contre problems with compositional structures. Code and videos are available at jihttps:/ //ss:///sieee google. con./ view/ sir- compositions tioaa
INTRODUCTION
large part of everyday human activities involves sequential tasks that have compositional structure, i.e. complex tasks which are built up in systematic way from simpler tasks (Singh 1991). Even in some very simple scenarios such as lifting an object, opening door, sitting down, or driving car, we usually decompose an activity into multiple steps and take multiple physical actions to finish each of the steps in our mind. Building an intelligent agent that can solve a wide range of compositional decision making problems such remains a long- standin challenge in AI.
Deep reinforcement learning (RL) has recently shown promising capabilities for solving complex decision making problems. But most approaches for these compositional challenges either rely carefully designed reward function (Warde-Farley et al. 2019) Yu et al. 2019: Li et al. 2020 OpenAl ett al. 2019), which is typically subtle derive and requires strong domain knowledge, or utilize hierarchical policy structure (Kulkarni et al., 2016 [acon et al.) 2017 Nachum et al. 2018 Lynch al. 2019 (Bagaria& & Konidaris] 2020), which typically assumes a set of low-level policies for skills and high-level policy for choosing the next skill to use. Although the policy hierarchy introduces structural inductive bias into RL, effective low-level skills can be non-trivial obtain and the bi-level policy structure often causes additional optimization difficulties in practice.
In this paper, we propose a novel RL paradigm, Self-Lmitation via Reduction (SIR), which (1) naturally works on sewrse-reward problems with compositional structures, and (2) does not impose any structural requirement on policy representation. SIR has two critical components, task reduction and imitation learning. Task reduction leverages the compositionalityy in parameterized lask space and tackles an unsolved hard task by actively "simplifying" to an easier one whose solution known already. When hard task is successfully accomplished via task reduction, we can further run imitation learning on the obtained solution trajectories to significantly accelerate training.
Fig. I iillustrates task reduction in pushing scenario with elongated box (brown) and cubic box (blue). Consider pushing the cubic box to the goal position (red). The difficulty comes with the wall on the table which contains small door in the middle. When the door is clear (Fig. Ta), the task is easy and straightforward to solve. However, when the door is blocked by the elongated box (Fig. [Iig.Ib). the task becomes significantly harder: the robot needs clear the door before it start pushing the

---

Published as a conference paper at ICLR 2021
(a) An easy task, which can be completed by a straighht- forward push the blue cubic box.
(b) hard task, where straightforward push fails since elongated box blocks the door.
start
fallure
hard task
reduce
salve
easy task
hard task
reduce
easy task
(c) Task reduction: solve a hard task by reducing it to an easier one.
Figure 1: An example use case of task reduction, the key technique of our approach. The task is to push the blue box to the red position.
cubic box. Such a compositional strategy non-trivial to discover by directly running standard RL. By contrast, this solution is much easier derive via task reduction: starting from an initial state with the door blocked (Fig. [b). the agent can first imagine a simplified task that has the same goal but starts from a different initial state with a clear door (Fig. Tap: ; then the agent can convert this simplified task by physically perturbing the elongate box to reach the desired initial state (Fig. Ic); finally, a straightforward push completes the solution to the original hard task (Fig. lbp.
Notably, by running imitation learning on the composite reduction trajectories, we effectively incor- porate the inductive bias of compositionality into the learned policy without the need of explicitly specifying any low-level skills or options, which significantly simplifies policy optimization. More- over, although task reduction only performs I-step planning from planning perspective, SIR still retains the capability of learning arbitrarily complex policy by alternating between imitation and reduction: as more tasks are solved, these learned tasks can recursively further serve as new reduction targets for unsolved ones in the task space, while the policy gradually generalizes to increasingly harder tasks by imitating solution trajectories with growing complexity.
We implement SIR by jointly learning goal-conditioned policy and universal value function (Schaul et al. 2013), so that task reduction can be accomplished via state search over the value function and policy execution with different goals. Empirical results show that SIR significantly accelerate and improve policy learning on challenging spurse-rewand continuous-control problems, including robotics pushing, stacking and maze navigation, with both object-based and visual state space.
RELATED WORK
is perhaps the most popular approach for solving compositional RL problems, which assumes a low-level policy for primitive skills and a high-level policy for sequentially proposing subgoals. Such bi-level policy structure reduces the planning horizon for each policy but raises optimization challenges. For example, many HRL works require pretraining low-level skills (Singh 1991 Kulkarni al. 2016 Florensa al. 2017 Riedmiller et al. 2018 Haarnoja et al.) 2018a) or non-trivial algorithmic modifications to learn both modules jointly (ayan & Hinton 1993) Silver & Ciosek, 2012, Bacon et al., 2017; Vezhnevets et al. 2017 Nachum et al. [2018). On the contrary, our paradigm works with any policy architecture of enough representation power by imitating composite trajectories. Notably, such an idea of exploiting regularities on behavior instead of constraints on policy structures can be traced back to the "Hierarchies of Muchines" model 1998 (Parr Russell 1998).
Hierarchical RL (HRL) Barto & Mahadevan 2003)
Our approach is also related to the options framework (Sutton et al., 1999 Precup 2000), which explicitly decomposes complex task into a sequence of temporal abstractions, i.c., options. The options framework also assumes hierarchical representation with inter-option controller and discrete set of reusable intra-option policies, which are typically non con-tiivial to obtain (Konidaris & Barto 2009 Konidaris et al. 2012 Bagaria & Konidaris 20200) Wulfmeier al. 2020). SIR implicitly reuses previously learned "skills" via task reduction and distills all the composite strategies into a single policy. Besides, there are other works tackling different problems with conceptually similar
2

---

Published as a conference paper at ICLR 2021
composition techniques. Probabilistic policy reuse Germandez-Rebolle & Veloso 2006 Fernández Rebollo et al. 2010) executes a discrete set of previously learned policies for structural exploration. Fang et (2019) consider dynamic goal setting without manipulable objects and compose agent trajectory and a goal trajectory that collide as supervision. Dhiman et al. (2018) transfer previous knowledge new goals in tabular cases by constraining value functions. Task reduction produces an expanding solved task space, which is conceptually related to life-long learning (Tessler et al., 2017) and open-ended learning (Wang et al., 2019).
Evidently, many recent advances have shown that with generic architectures, e.g., convolution (Le Cun et al. 1995) and self-attention (Vaswani al. 2017), simply training on massive data yields surprisingly y intelligent agents for image generation (Chen et al., [2020), language modeling (Brown
al. 2020), dialogue (Adiwardana et al. 2020) and gaming (Schrittwieser et al., 2019 Baker et al..
2020p. Hence, we suggest building intelligent RI agents via similar principle, i.e., design a diverse task spectrum and then perform supervised learning on complex strategies.
The technical foundation of SIR is to use universal value function and goal conditioned pol- icy (Kaelbling 1993 Schaul et al. 2013), which has been successfully applied in various domains, including tackling sparse rewards (Andrychowicz et al. (017)) visual navigation (Zhu et al. (017))
planning Srinivas et al.) 2018), imitation learning (Ding et al. 2019) and continuous control (Nair ct al. 2018). Besides, task reduction requires state-space search/ wwwpcchhlpannggg..em over approximate value
function. Similar ideas of approximate state search have been also explored (Pathak et al. 2018
Eysenbach et al.] 2019 Nasiriany al. 2019 Ren al.) 2019 Nair & Finn 2020). SIR accelerates
learning by imitating its own behavior, which is typically called self-imitation (Oh et al. 2018 Ding
al. 2019 Lynch et al. 2019) or self-supervision (Nair et 2018 2019 Pong
2019 Ghosh
ct al.
2019). In this paper, we use techniques similar to Rajeswaran et al. (2018) 8)
and Oh et al. (2018).
but general, SIR does not rely on any particular imitation learning algorithm.
There are also related works on compositional problems of orthogonal interests, such as learning to smoothly compose skills (Lee et al. 2019). composing skills via embedding arithmetic (Sahni et al.,
2017. Devin et al. 2019), composing skills in real-time (Peng et al.) 2019), following instructions (An-
dreas et al. 2017 Jiang et al. 2019) and manually constructing flerative-refinement strategies to
address supervised learning tasks (Nguyen et al. 2017 [jelm et al. 2016 Chang et al. 2019))
Conceptually, our method is also related to curriculum learning (CL). Many automatic CL meth- ods (Graves et al., [017 Florensa et al.] [0088] Matiisen et al.] 2019 Portelas et al. 2019 Racaniere jet al. (020) also assume a task space and explicitly construct task curricula from easy cases to hard ones over the space. In our paradigm, task reduction reduces hard task to a simpler solved task, so the reduction trace over the solved tasks can be viewed as an implicit task curriculum. Such a phenomenon of an implicitly ever-expanding solved subspace has been also reported in other works for tackling goal-conditioned RL problems (Warde-Farke et al.] 2019 Lynch et al.) 2019). Despite the conceptual similarity, there are major differences between SIR and CL. SIR assumes a given task sampler and primarily focuses on efficiently finding a policy to a given task via task decomposition. By contrast, CL focuses on task generation and typically treats policy learning as a black box. We also show in the experiment section that SIR is complementary to CL training and can solve a challenging sparse-reward stacking task (Sec. 5.2) that was unsolved by curriculum learning alone. We remark that it is also possible to extend SIR to full CL. method and leave it as future work.
PRELIMINARY AND NOTATIONS
We consider a multi-task reinforcement learning setting over a parameterized task space T. Each task T T is represented as a goal-conditioned Markov Decision Process (MDP). T = (S, ST, 9r, r(s, a; gr), P(s'|s [s, a; (r)), where S is the state space, A is the action space. ST, gr E are the initial state and the goal to reach, r(s, o; 9r) is the reward function of task T, and P(s") s, 0; (T) is the transition probability. Particularly, we consider sparse reward setting, i.e., r(s, a; gT) = 1 [d((s, 9T) < o). where the agent only receives a non-zero reward when the goal is achieved w.r.t. some distance metric d(.,). We assume that the state space and the action space are shared across tasks, and different tasks share the same physical dynamics (i.e., Gr only influences the termination condition of the transition probability P). task T is determined by its initial state ST and goal gr. We also assume a task sampler C, which samples training tasks from T. C can be simply uniform sampler or something more intelligent. For evaluation, we are interested in the most
3

---

Published as a conference paper at ICLR 2021
challenging tasks in T. The learning agent is represented stochastic policy aa(als, gr) condition- ing on state and goal ør and parameterized by 8. We aim to find the optimal parameter 8 such that policy To- maximizes the expected accumulative reward across every task T T with a discounted factor y i.e., 0* = arg max; EE I>x " d4; (rig)) where de ~ To To(a 8t, pr) Correspondingly, we also learn universal value function Vi (st, 9r) for state 8, and goal gr parameterized by 1 w.r.t. ma- The subscript 0 in Ty and v in V will be omitted for simplicity in the following content.
4
METHOD
4.1 TASK REDUCTION
The core idea of task reduction is to convert a hard-to-solve task A E T to some task B E T that the agent has learned to solve, so that the original task can be accomplished via composing two simpler tasks, i.c., (1) reducing task A to B and (2) solving the reduced task B. More formally, for task A with initial state S and goal 9A that the current policy π cannot solve, we want to find reduction target B with imitial state and goal 9n such that (1) the task to reach state from $ is easy, and (2) B has the same goal as (i.e., JB = 9A) and solving task B is easy. natural measure of how easy task is under ı is to evaluate the universal value function V(.). Hence, task reduction aims to find the best target state si. which is the initial state of some task B, such that
8B arg max (8) + (($.99A) = arg max 88,A en
en
where @ is some composition operator and V(SA, sB, 9A) denotes the composite value w.r.t particular target state 8B. There are multiple choices for @ including minimum value, average or product (due to 0/1 sparse rewards). Empirically, taking the product of two values leads to the best practical performance. Thus, we assume (SS SB 9A) = V(SA, sB) V(s 9A) )) in this paper.
With the optimal target state si obtained, the agent can perform task reduction by executing the from the initial state SA. If this policy execution leads to some successful state s'n (i.e., within a threshold to s) the agent can continue executing (a s 9A) from state s'B towards the ultimate goal 9A- Note that it may not always be possible to apply task reduction successfully since either of these two policy executions can be failure. There are two causes of failure: (i) the approximation error of the value function; (ii) task A is merely too hard for the current policy. For cause (i), the error is intrinsic and cannot be even realized until we actually execute the policy the environment; while for cause (ii), we are able to improve sample efficiency by only performing task reduction when it is likely to succeed, e.g., when V (SA. 3) gA) exceeds some threshold o.
policy π A. A. $T))
4.2 SELF-IMITATION
Once task reduction is successfully applied to a hard task A via a target state si.. we obtain two trajectories, one for reducing A to B with final state s'g. and the other for the reduced task B starting at s'zz. Concatenating these two trajectories yields a successful demonstration for the original task A. Therefore, by continuously collecting successful trajectories produced by task reduction, perform imitation learning on these self defffmsttotrronnss Suppose demonstration dataset is denoted by Dil (ss a. We utilize a weighted imitation learning objective (Oh et al. 2018) as follows:
(d D'l) = E E ()ED [log<(a|s.g))mml g)+],
where A(s, ((s,g)) 9)+ denotes the clipped advantage. i.e., max(0, R - V(s, g)). Self-imitation allows the agent to more efficiently solve harder tasks by explicitly using past experiences on easy tasks.
4.3 SIR: SELF-IMITATION VIA REDUCTION
We present SIR by combining deep RL and self-imitation on reduction demonstrations, SIR is compatible with both off off-policy and on-policy RL. We use soft actor-critic (Haarnoja et al. 20 8b) with hindsight experience replay (Andrychowiez et al., 2017) (SAC) and proximal policy gradient (PPO) (Schulman et al., 2017) respectively in this paper. In general, an RL algorithm trains an actor and critic with rollout data Dr from the environment or the replay buffer by optimizing algorithm-specific actor loss T,actor (0; Dri) and critic loss T,rrttic (v); Drl).
4

---

Published as a conference paper at ICLR 2021
For policy learning, since reduction demonstrations D are largely off-policy, it is straightforward to incorporate D in the off-policy setting: we can simply aggregate the demonstrations into the experience replay and jointly optimize the self-imitation loss and the policy learning loss by
I, I (0; D" :D")= I.adtor (0:D"! Dr' U D (0; Dri U D").
While in the on-policy setting, we only perform imitation on demonstrations. Since the size of Dil is typically much smaller than Drt, we utilize the following per-instanc loss to prevent overfit on D
(0; Dr D || [ potto (0; Drl) + (0;
I (0;
D U D
For critic learning, since the objective is consistent with both data sources, we can simply optimize Loritio (uh: D U ) The proposed algorithm is summarized in Algo.
4.4 IMPLEMENTATION AND EXTENSIONS
We primarily consider object-based state space, where goal state is determined by whether an object reaches some desired location. We also extend our method to image input by learn- ing a low- www-dimensional latent representation (Higgins) et al.) 2017b) and then perform task reduction over the latent states (see Sec. (.3). We do not consider strong pastial-obeervabilitt (Pinto al. 2018) in this paper and leave it as future work.
Task Space:
Algorithm 1: Self-Imitation via Reduction
initialize Ta. Vy: Dr +- D 0: repeat
trajectory by ma in task A from
C:
Dr +- Dr + {T}; if is a failure then
find target state s'g w.r.t Eq. Q 9A) > then T' f- trajectory by reduction; i' is a success then D (
Reduction-Target Target Search: In implementation, we simply perform a random search to find the top-2 candidates for s in Eq. ① and try both of them. We also use the cross-entropy method (De Boer et al. 2005) for efficient planning over the latent space with image input (Sec. 5.3 Alternative planning methods can be also applied, such as Bayesian opti- mization (Snock et al. 2012; (Swersky et al.) 2014). gradient descent (Srinivas et al. 2018). or learn- ing neural planner (Wang et al. 201 8 Nair et al. 2019). We emphasize that the reduction search is performed completely the learned value function, which does not require any environment interactions.
if enough new data collected then
0 f- 0 VVV,, (0; Dri Dill); + vVVV (w²; D UD!));
until enough iterations; return TT. Ve:
Particularly in the object-centric state space, an extremely effective strategy for reducing the search space is to constrain the target 8 to differ from the current state 8A by just a few objects (e.g.. I object in our applications). Due the compositionality over objects, the agent can still learn arbitrarily complex behavior recursively throughout the training. When performing task reduction in training, SIR explicitly resets the initial state and goal of the current task, which a very common setting in curriculum learning and coal-conditioned policy learning. It is possible to avoid resets by archiving solutions to solved tasks approximate a reduction trajectory. We leave it as future work.
Estimating Ø: We use a static for SAC. For PPO. we empirically observe that, as training proceeds, the output scale of the learned value function keeps increasing. Hence, we maintain an online estimate for a. i.e., a running average of the composite values over all the selected reduction targets.
Imitation Learning: Note that there can be multiple feasible reduction targets for particular task. Hence, the self-demoonstrations can be highly multi-modal. This issue is out of the scope of this paper but it can be possibly addressed through some recent advances in imitation learning (Ho & Ermon 2016 Guo et al. 2019 Lynch et al., 2019)).
5
EXPERIMENTS
We compare SIR with baselines without task reduction. Experiments are presented 3 different environments simulated in MuloCo Todorov al. 2012) engine: robotic-hand pushing scenario
5

---

Published as a conference paper at ICLR 2021
with wall opening (denoted by "Push"), robotic-gripper stacking scenario (denoted by "Stack"), and a 2D particle-basee maze scenario with a much larger environment space (denoted by "Maze") form continuously parameterized
All of the scenarios allow random initial and goal states task space. All of the problems are fully-observable with 0/1 sparse rewards and are able to restart from given state when performing task reduction. All the training results repeated over random seeds. We empirically notice that SAC has superior performance in robotics tasks but takes significantly longer wall-clock time than PPO in the maze navigation tasks (see Fig. [7 in Appx. (C) Hence, we use SAC in Push and Stack while PPO in Maze for RL training in all the algorithms if not otherwise stated. We remark that we also additionally report SAC results for simplified Maze task in Appx. (see Fig. [8). We primarily consider state-based observations and additionally explore the extension image input in Maze scenario. More details and results can be found in the appendices.
5.1 Push SCENARIO
Hard
Rand.
SAC only
0.406
0.771
SAC TR
0.764
0.772
(a) state
(b) reduction
(c) reduced task (d) composite
Table I: Task Reduction (TR)
Figure 2: Heatmap of learned value function. (a) current state; (b) value for moving the elongated box elsewhere; (c) value for moving the cubic box to goal w.r.t. different elong. box pos.; (d) composite value for different reduction targets: moving elong. box away from door yields high values for task reduction.
as a test-time planner. We evaluate the success rates on test tasks when additional TR steps are allowed in the execu- tion of the SAC-trained policy.
1.0
1.0
As shown in Fig. (Sec. 1. tthre are two objects on the table, cubic box (blue) and an elongated box (brown). The robot needs to push a specified object goal location (red). The table sep- arated into two connected regions by fixed wall with an open door in the middle. The initial ob- ject positions, goal location, robot hand location, and which object to push are randomly reset per episode.
0.8
0.8
avg succ
0.6
hard succ.
0.4
0.4
SAC
02
0.0
00-
samples
1c7
samples
167
Figure 3: Avg. success rate w.r.t. samples over current task distribution (left) and in hard cases (right) in the Push scenario.
Learned Value Function: We retrieve a par- tially trained value function during learning and illustrate how task reduction is performed over it in Fig. Consider a hard task shown in Fig. 2a where the door is blocked by the elongated box and the agent needs to move the cubic box to the goal on the other side. A possible search space is the easier tasks with the position of the elongated box perturbed. We demonstrate the learned values for moving the elongated box different goal positions in Fig. [2b] where we observe consistently lower values for faraway goals. Similarly, Fig. 2c visualizes the values for all possible reduced tasks, i.c.. moving the cubic box to the goal with the elongated box placed in different places. We can observe higher values when the elongated box away from the door. Fig. 2d shows the composite values w.r.t. different target states, where the reduction search is actually performed. We can clearly see two modes on both sides of the door.
Task Reduction as a Planner: Task reduction can serve as test-time planner by searching for reduction target that possibly yields higher composite value than direct policy execution. We use half-trained policy and value function by SAC and test fixed set of 1000 random tasks. Since random sampling rarely produces hard cases, also evaluate in 1000 hard tasks where the elongated box blocks the door and separates the cubic box and goal. The results are in Table. [ where task reduction effectively boosts performances in hard cases, which require effective planning.
Performances: SIR is compared with three different baselines: SAC; SAC with self-imitation learning (SIL), which does not run task reduction and only imitates past successful trajectories directly generated by policy execution; SAC with a dense reward (DS), i..., potential- baasd distance reward from object to the goal. We evaluate the average success rate the entire task distribution

---

Published as a conference paper at ICLR 2021
Figure 4: SIR-learned strategy for stacking boxes in the Stack scenario. The yellow spot in the air the goal, which requires a yellow box to be stacked reach it.
awg. succ. rafe
harl suCc rate
# Box
2
3
SAC 0.96=0.01
0.94
0.25
SCC
0.4
SIL
0.89=0.06
0.96++0.03
0.28=0002
DS
0.93=
0.67
0.27=0.01
0.2
2
2
SIR
0.96
0.98
0.89-10.03
samples
107
samples
Figure 5: Training results in the Stack sce- nario with at most boxes. We evaluate suc- cess rate across training curriculum (left) and in hard cases, i.e., stacking 3 boxes (right).
Table 2: Average success rate and standard devia-
tion of different algorithms for stacking different number of boxes evaluated the same training samples.
as well as the hard-case success rate (i.e., with blocked door) in Fig. where SIR achieves the best overall performances, particularly in hard cases. We emphasize that for SIR, we include all the discarded samples due to failed task reductions in the plots. Since the only difference between SIR and SIL is the use of task reduction, our improvement over SIL suggests that task reduction is effective for those compositional challenges while burdened with minimal overall overhead.
5.2
Stack SCENARIO
Next, we consider a substantially more challenging task in a similar environment to Push: there is robotics gripper and at most cubic boxes with different colors on the table. The goal is stack a tower using these boxes such that specified cubic box remains stable at a desired goal position even with gripper fingers left apart. Therefore, if the goal is the air, the agent must learn to first stack non-target boxes in the bottom, to which there are even multiple valid solutions, before it can finally put the target box on the top. See Fig. 4 for an example of stacking the yellow box towards the goal position (i.e, the yellow spot in the air). Each episode starts with a random number of boxes with random initial locations and a colored goal that is viable to reach via stacking.
This task is extremely challenging, so we (1) introduce an auxiliary training task, pick-and-place, whose goal is simply relocating specified box to the goal position, and (2) carefully design a training curriculum for all methods by gradually decreasing the ratio of pick-and-place tasks from 70% to 30% throughout the training. For evaluation, a task considered as a hard case all the 3 boxes are required to be stacked together.
We show the training curves as well as the hard-case success rate for SIR and other methods in Fig. 5 SIR significantly outperforms all the baselines, especially in the hard cases, i.e., stacking all the boxes. Table. iillstrrates the detailed success rate of different methods for stacking 1, and 3 boxes. SIR reliably solves all the cases while other methods without task reduction struggle to discover the desired compositional strategy to solve the hardest cases. Fig. [ visualizes a successful trajectory by SIR for stacking boxes from scratch, where the goal is stack the yellow box reach the goal spot in the air. Interestingly, the agent even reliably discovers non-trivial strategy: it first puts the yellow box on the top of the green box form a tower of two stories, and then picks these two boxes jointly, and finally places this tower top of the blue box to finish the task.
5.3 Maze SCENARIO
In this scenario. we focus navigation problem with particle-basee based agent in large 2D maze, named "4- "4-Room maze". The maze is separated into 4 connected rooms by three fixed walls and each wall has open door in the middle. There are 4 objects in the maze, including elongated boxes
7

---

Published as a conference paper at ICLR 2021
Figure 6: SIR-learned strategy for a hard case in the 4-Room maze scenario. The agent(green) is tasked move the blue box to the target(red), All three doors blocked by elongated boxes, so the agent needs to clear them before pushing the blue box towards the target.
0.5
1.0
0.6
0.4
0.8
0.2
avg.
SiR
0.1
0.0
SR
02
Samples
1cB
Samples
1cB
samples
Figure 7: Results in 4-Room maze. Left: suc- cess rate in the training task distribution; Right: success evaluated only in the hard cases.
Figure 8: Navigation in U-Wall maze with im- age input. Left: task visualization; Right: avg. training success rates w.r.t. samples.
(brown) and cubic box (blue). The task for the agent (green) to move a specified object to a goal position (red). We consider case hard when (i) the agent needs move the cubic box a different room, and (ii) at least one door is blocked by the elongated boxes.
Figure 6 visualizes a particularly challenging situation: the agent needs move the cubic box the goal but all three doors are precisely blocked by the elongated boxes. To solve this task, the agent must perturb all the elongated boxes to clear the doors before moving the cubic box. As is shown in Fig. 6 the agent trained by SIR successfully learns this non-trivial strategy and finishes the task.
We adopt PPO for training here and compare SIR baselines in terms of average success rate over both the training task distribution and the hard tasks only. The results are shown in Fig. 7 SIR outperforms both PPO and SII. baselines with a clear margin, especially when evaluated on hard cases. Note that although SII. learns slightly more efficiently at the beginning of training, it gets stuck later and does not make sufficient progress towards the most challenging cases requiring complex compositional strategies to solve.
Extension to visual domain:
We consider extending SIR to the setting of image input by first pre- training 3-VAE (Higgins et al. 2017a) to project the high-dimensional image to low-dimensional latent vector and then perform task reduction over the latent space. We train the 3- VAE using random samples from the environment and apply the cross-entropy method (CEM) (De Boer et al.) 2005) to search for the reduction targets. We experiment in a sparse-reward variant of the U- Wall maze task adapted from Nasiriany al.) (2019), where the agent (blue) needs navigate the goal (green) by turning around the wall (boundary plotted in black). Task visualization and training results are shown Fig. where SIR still achieves the best performance compared with PPO and SIL.
We also compare SIR with two baselines with hierarchical policy structures, i... an off- off-policy HRL algorithm HIRO (Nachum et al. 2018) and an option discovery algorithm DSC (Bagaria & Konidaris 2020). Since these two HRL baselines are both based on off- off-policy learning, we use SAC our training algorithm in SIR for a fair comparison. In addition, since both
Comparison with HRL:
6.4
0.2
1860
0.0
0.2
0.4
0.6
0.6
1.
samples
(b) Box pushing in 3-Room maze, fixed goal Figure 9: Comparison of HRL baselines and SIR in the fixed-goal Maze scenarios.
(a) U U-Shape maze, tixed goal
8

---

Published as a conference paper at ICLR 2021
two baselines also assume fixed goal position, experiment in two fixed-goal Maze scenarios. We first conduct a sanity check a simple U-Shape maze without any boxes (Fig. 9a), where the agent (yellow) is expected propel itself towards the goal (red). Then experiment in 3-Room maze (Fig. (b). which is a simplified version of the previously described 4-Room maze. The results Although HIRO and DSC learn solve the easy U-shape maze, they hardly make any progress in the more difficult 3-Room maze, which requires non-trivial compositional strategy. Note that DSC is extremely slow in 3-Room maze, so we terminate it after 5 days of training. In contrast, even without any policy hierarchies, SIR learns significantly faster in both two scenarios.
shown in Fig. g
Comparison with automatic curriculum learning: As discussed at the end of Sec. 2 SIR implicitly con- structs a task curriculum by first solving easy tasks and then reducing a hard task to a solved one. Hence, we also conduct experiments with curriculum learn- ing (CL) methods. We compare SIR using a uniform task sampler with standard PPO learning with Goal- GAN (Florensa et al.) 2018), automatic CL ap- proach, as well as a manually designed training cur- riculum, which gradually increases the distance be- tween the goal and the start position. Since GoalGAN assumes fixed initial position for the agent while only specifies the goal position, we consider the un- modified navigation problem used in FFloeesa et al.) (2018) for fair comparison. The results are shown in Fig. 10 Even with uniform task sampler, SIR significantly outperforms the CL baselines that do not leverage the task reduction technique. We want to remark that GoalGAN eventually solves the task with 106 samples since it takes large number of samples to train an effective GAN for task sampling. By contrast, SIR directly works with uniform task sampler and implicitly learns from easy hard in much lightweight fashion. Finally, we emphasize that SIR is also complementary to curriculum learning methods. As we previously show in Sec. 5.2 combining SIR and manually-designee training curriculum solves challenging stacking problem, which is unsolved by solely running curriculum learning.
0.8
0.6
SiR
Manual CL
GoalGAN
20000
40000
60000
80000
100000
samples
Figure 10: Comparison with curriculum learning methods in the U-Shape maze (fixe goal). We consider SIR with uniform task sampler and standard PPO with GoalGAN and manually designed curriculum.
6 CONCLUSION
This paper presents a novel learning paradigm SIR for solving complex RL problems. SIR utilizes task reduction to leverage compositional structure in the task space and performs imitation learning to effectively tackle successively more challenging tasks. We show that an RL agent trained by SIR can efficiently learn sophisticated strategies in challenging sparse-reward continuous-conte Task reduction suggests a simple but effective way, i.e., supervised learning on composite trajectories with a generic policy representation, to incorporate inductive bias into policy learning, which, we hope, could bring valuable insights to the community towards wider range of challenges.
problems.
ACKNOWLEDGMENTS
Co-author Wang was supported, in part, by gifts from Qualcomm and TuSimple.
REFERENCES
Daniel Adiwardana, Minh- Minh-Thang Luong, David R So, Jamie Hall, Noah Fiedel, Romal Thoppilan, Zi Yang, Apoorv Kulshreshtha, Gaurav Nemade, Yifeng Lu, et al. Towards a human-likk open- domain chatbot. arXiv preprint a7X1922001.09977 2020.
Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In Proceedings of the 34th International Conference on Machine Learning-Volure Volume 70, pp. 166-175. JMLR. org, 2017.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Advances in neural information processing systems, pp. 0058-5058, 2017.

---

Published as a conference paper at ICLR 2021
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critte architecture. In Thirty-Fire First AAAI Conference on Artificial Intelligence, 2017.
Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. International Conference on Learning Representations, 2020.
Andrew G Barto and Sridhar Mahadevan. Recent advances in hierarchical reinforcement learning. Discrete event dynamic systems, 13(1-2):41-7, 2003,
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. arXiv preprint arXiv:2005. 14 4615, 2020.
Michael Chang, Abhishek Gupta, Sergey Levine, and Thomas L. Griffiths, Automatically composing representation transformations as means for generalization. In International Conference on Learning Representations, 2019.
Mark Chen, Alec Radford, Rewon Child, Jeff Wu, Heewoo Jun, Prafulla Dhariwal, David Luan, and Ilya Sutskever. Generative pretraining from pixels. Proceedings of the 37th International Conference Machine Learning, 2020.
Peter Dayan and Geoffrey E Hinton. Feudal reinforcement learin. Advances in neural information processing systems, pp. 271-27716 1993.
Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Y Rubinstein. A tutorial on the cross-entropy method. Annals of operations research, 134(1):19-67, 2005.
Coline Devin, Daniel Geng, Pieter Abbeel, Trevor Darrell, and Sergey Levine Compositional plan vectors. In Advances in Neural Information Processing Systems, pp- 14963-14974, 2019.
Vikas Dhiman, Shurjo Banerjee, Jeffrey Mark Siskind, and Jason J. Corso. Floyd-warshall reinforce- ment learning learning from past experiences to reach new goals. CoRR, 0abo//8809.993/ 2018. URL http:://axiii. org/ abs/ 1809. 09318
Yiming Ding, Carlos Florensa, Pieter Abbeel, and Mariano Phielipp. Goal-conditioned imitation learning. In Advances in Neural Information Processing Systems, pp. 15298-15309, 2019.
Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In Advances in Neural Information Processing Systems, pp. 15231, 2019.
Meng Fang, Cheng Zhou, Bei Shi, Boqing Gong, Weitao Xi, Tianzhou Wang, Jia Xu, and Tong Zhang. DHER: Hindsight experience replay for dynamic goals. In International Conference on Learning Representationss, 2019.
Fernando Fernóndez-Rebolloo and Manuela M. Veloso. Probabilistic policy reuse in reinforcement learning agent. In Hideyuki Nakashima, Michael P. Wellman, Gerhard Weiss, and Peter Stone (eds.), 5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006), Hakodate, Japan, May 8-12, 2006, pp. 720-727. ACM, 2006.
Fernando Femmández-Rebollo, Javier García, and Manuela M. Veloso. Probabilistic policy reuse for inter-task transfer learning. Robotics Auton. Syst. 58(7)8866 871, 2010.
Carlos Florensa, Yan Duan, and Pieter Abbeel. Stochastic neural networks for hierarchical reinforce- ment learning. International Conference Learning Representations, 2017.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In International Conference on Machine Learning, pp. 1515-1528, 2018.
10

---

Published as a conference paper at ICLR 2021
Dibya Ghosh, Abhishek Gupta, Justin Fu, Ashwin Reddy, Coline Devine, Benjamin Eysenbach, and Sergey Levine. Learning to reach goals without reinforcement learning. arXiv preprint arXiv:1912.06088, 2019.
Alex Graves, Mare G Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. In Proceedings of the 34th International Conference on Machine LeanningVoolume
Volume 70. pp. 1311-1320. JMLR. org. 2017.
Yijie Guo, Jongwook Choi, Marein Moczulski, Samy Bengio, Mohammad Norouzi, and Honglak Lee. Efficient exploration with self-imitation learning via trajectory-condiiione policy, arXiv preprint
2019.
Tuomas Haarnoja, Vitchyr Pong, Aurick Zhou, Murtaza Dalal, Pieter Abbeel, and Sergey Levine. Composable deep reinforcement learning for robotic manipulation. In 2018 IEEE International Conference on Robolics and Automation (ICRA), pp. 6244-6251. IEEE, 2018a.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, pp. 1856-1865, 2018b.
Irina Higgins, Loie Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. In 5th International Conference on Learning Representutions, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.ner, 2017a.
Irina Higgins, Arka Pal, Andrei Rusu, Loic Matthey, Christopher Burgess, Alexander Pritzel, Matthew Botvinick, Charles Blundell, and Alexander Lerchner. Darla: Improving zero-shot transfer in reinforcement learning. In Proceedings of the 34th International Conference Machine Learning- Volume 70. pp. 1480-1490, 2017b.
Devon Hjelm, Russ R Salakhutdinov, Kyunghyun Cho, Nebojsa Jojic, Vince Calhoun, and Junyoung Chung. Iterative refinement of the approximate posterior for directed belief networks. In Advances in Neural Information Processing Systems, pp. 4691-4699, 2016.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in neural information processing systems, pp. 4573, 2016.
Yiding Jiang, Shixiang Shane Gu, Kevin P Murphy, and Chelsea Finn. Language as an abstraction for hicrarchical deep reinforeement learning. In Advances in Neural Information Processing Systems, pp. 9414-9426, 2019.
Leslie Pack Kaelbling. Hierarchical learning in stochastic domains: Preliminary results. In Pro- ceedings of the tenth international conference on machine learning, volume 951, pp. 167-173, 1993.
George Dimitri Konidaris and Andrew G. Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. Yoshua Bengio, Dale Schuurmans, John D. Lafferty, Christopher K. I. Williams, and Aron Culotta (eds.), Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, pp. 1015 1023. Curran Associates, Inc., 2009.
George Dimitri Konidaris, Scott Kuindersma, Roderic A. Grupen, and Andrew G. Barto. Robot learning from demonstration by constructing skill trees. Int. J. Robotics Res., 31(3):360-375, 2012.
Tejas Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In Advances in neural information processing systems, pp. 3675-3683, 2016.
Yann LeCun, Yoshua Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, (10): 1995.
11

---

Published as a conference paper at ICLR 2021
Youngwoon Lee, Shao-Hua Sun, Sriram Somasundaram, Edward Hu, and Joseph J. Lim. Composing complex skills by learning transition policies with proximity reward induction. In International Conference Learning Representations, 2019.
Richard Li, Allan Jabri, Trevor Darrell, and Pulkit Agrawal. Towards practical multi -bject manipula- tion using relational reinforcement learning. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2020.
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, 2019.
Tambet Matüsenn, Avital Oliver, Taco Cohen, and John Schulman. Teacher-student curriculum learning. IEEE transactions on neural networks and learning systems, 2019.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In Advances in Neural Information Processing Systems, pp. 3303-3313, 2018.
Ashvin Nair, Shikhar Bahl, Alexander Khazatsky, Vitchyr Pong, Glen Berseth, and Sergey Levine. Contextual imagined goals for self-supervised robotic learning. Conference on Robot Learning. 2019.
Ashvin V Nair, Vitchyr Pong, Murtaza Dalal, Shikhar Bahl, Steven Lin, and Sergey Levine. Visual reinforcement learning with imagined goals. In Advances in Neural Information Processing Systems, pp. 9191-9200 2018.
Suraj Nair and Chelsea Finn. Hierarchical foresight: Self-supervised learning of long-horizon tasks via visual subgoal generation. International Conference on Learning Representations, 2020. URL hhtpps://ppereviee..tt net fow.mmidd-Hlgg2222e2.
Soroush Nasiriany, Vitchyr Pong. Steven Lin, and Sergey Levine. Planning with goal-conditioned policies. In Advances in Neural Information Processing Systems, pp. 14814-14825, 2019.
Anh Nguyen, Jeff Clune, Yoshua Bengio, Alexey Dosovitskiy, and Jason Yosinski. Plug play generative networks: Conditional iterative generation of images in latent space. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4467 6667-447.5 2017.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. In International Conference on Machine Learning, pp. 3878-3888808 -387,,877488 2018
C Berner OpenAI, Greg Brockman, Brooke Chan, Vicki Cheung, P Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota with large scale deep reinforcement learning. arXiv preprint 1rXiv:1912.0668) 2019.
Ronald Parr and Stuart Russell. Reinforcement learning with hierarchies of machines. In Advances in neural information processing systems, pp. 1043-1049, 1998.
Deepak Pathak, Parsa Mahmoudich, 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 on Computer Vision and Puttern Recognition Workshops, pp. 2050-2055 2018
Xue Bin Peng, Michael Chang, Grace Zhang, Pieter Abbeel, and Sergey Levine. Mcp: Learning composable hierarchical control with multiplicative compositional policies. In Advances in Neural Information Processing Systems, pp. 3681 3681-3692, 2019.
Lerrel Pinto, Marcin Andrychowicz, Peter Welinder, Wojeiech Zaremba, and Pieter Abbeel. Asym- metric actor critic for image-basee robot learning. Proceedings of Robotics: Science and Systems, 2018.
Vitchyr H Pong. Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew-fit: State-covering sele-super reinforcement learnin. arXiv preprint arXiv: 1903: 03699, 2019.
12

---

Published as a conference paper at ICLR 2021
Rémy Portelas, Cédric Colas, Katja Hofmann, and Pierre- Yves Oudeyer. Teacher algorithms for curriculum learning of deep RL in continuously parameterized environments. arXiv preprint arXiv:1910.07224, 2019.
Doina Precup. Temporal abstraction in reinforcement learning, 2000.
Sebastien Racaniere, Andrew Lampinen, Adam Santoro, David Reichert, Vlad Firoiu, and Timothy Lillicrap. Automated curriculum generation through setter-solver interactions. In International Conference on Learning Representations, 2020.
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. In Proceedings of Robotics: Science and Systems (RSS), 2018.
Zhizhou Ren, Kefan Dong, Yuan Zhou, Qiang Liu, and Jian Peng. Exploration via hindsight goal generation. In Advances in Neural Information Processing Systems, pp. 13464-13474, 2019.
Martin Riedmiller, Roland Hafner, Thomas Lampe, Michael Neunert, Jonas Degrave, Tom Wiele, Vlad Mnih, Nicolas Heess, and Jost Tobias Springenberg. Learning by playing solving sparse reward tasks from scratch. In International Conference on Machine Learning, pp. 4344 4353, 2018.
Himanshu Sahni, Saurabh Kumar, Farhan Tejani, and Charles Isbell. Learning to compose skills. arXiv preprint 1711. 2017.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International conference machine learning, pp. 1312-1320 2015.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. arXiv preprint arXiv:1911.0226 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707006777 2017.
David Silver and Kamil Ciosek. Compositional planning using optimal option models. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1267- 1274, 2012.
Satinder P Singh. Transfer of learning across compositions of sequential tasks. In Machine Learning Proceedingg 1991, pp. 348-352, Elsevier, 1991.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical Bayesian optimization of machine learning algorithms. In Advances in neural information processing systems, pp. 2951-2959, 2012.
Aravind Srinivas, Allan Jabri, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Universal plan- ning networks: Learning generalizable representations for visuomotor control. In International Conference on Machine Learning, pp. 4732-4741, 2018
Richard S. Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artif. Intell., 112(1-2):811-111 1999. doi: 000100665000443722/90000333
Kevin Swersky, Jasper Snock, and Ryan Prescott Adams. Freeze-thaw Bayesian optimization. arXiv preprint arXiv:1406.3896, 2014.
Chen Tessler, Shahar Givony, Tom Zahavy, Daniel J. Mankowitz, and Shie Mannor. A deep hierarchi- cal approach to lifelong learning in minecraft. In Satinder P. Singh and Shaul Markovitch (eds.), Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco. California, USA, pp. 1553-1561. AAAI Press, 2017.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033 IEEE, 2012.
13

---

Published as a conference paper at ICLR 2021
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- Learning-Volume Volume 70, pp. 3540-3549.
JMLR. org, 2017.
Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O Stanley. Poet: open-ended coevolution of environments and their optimized solutions. Proceedings of the Genetic and Evolutionary Computation Conference, pp. 142-151, 2019.
Tongzhou Wang. Yi Wu, Dave Moore, and Stuart J Russell. Meta-learning MCMC proposals. In Advances in Neural Information Processing Systems, pp. 4146-4156, 2018.
David Warde-Farley, Tom Van de Wiele, Tejas Kulkarni, Catalin Ionescu, Steven Hansen, and Volodymyr Mnih. Unsupervised control through non-parametric discriminative rewards. In International Conference on Learning Representations, 2019.
Markus Wulfmeier, Dushyant Rao, Roland Hafner, Thomas Lampe, Abbas Abdolmaleki, Tim Hertweck, Michael Neunert, Dhruva Tirumala, Noah Y. Siegel, Nicolas Heess, and Martin A. Riedmiller. Data-efficient hindsight off- aff-policy option learning. CoRR, abs/2007.15588 2020.
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 on Robot Learning (CoRL), 2019.
Yuke 7hu, Roozbeh Mottaghi, Fric Kolve, Joseph Lim, Abhinav Gupta, Fei-Fei, and Ali Farhadi. Target-driven visual navigation in indoor scenes using deep reinforcement learning. In 2017 IEEE international conference on robotics and automation (ICRA), pp. 3357-3364. IEEE, 2017.
14

---

Published as a conference paper at ICLR 2021
A ENVIRONMENT DETAILS
A.1 PUSH SCENARIO
The robot is placed beside a 50cm x 70cm table with an elongated box and cubic box on it. The initial position of the two boxes, the projection of the initial gripper position onto the table plane, and the goal position are sampled from a 30cm 30cm square on the table. The gripper is initialized at fixed height above the table.
Observation space The observation vector a concatenation of state, achieved goal and desired goal. State consists of the position and velocity of the gripper, the cubic box and the elongated box, as well as the state and velocity of the gripper fingers. Desired goal vector consists of a position coordinate and one-hot vector indicating the identity of the target object. Achieved goal contains the current position of the target object and its corresponding one-hot index vector.
Action space The action 4-dimensional, with the first 3 elements indicating the desired position shift of the end-effector and the last element controlling the gripper fingers (locked in this scenario).
Hard configuration Our training distribution is mixture of easy and hard cases. In easy cases, positions of the gripper, the boxes and the goal are all uniformly sampled. The index of the target object also uniformly sampled from total number of objects. In hard cases, the position of the gripper, the position of the cubic box, and the target object index are still uniformly sampled, but the elongated box is initialized at a fixed location that blocks the door open of the wall. The goal is on the opposite side of the wall if the target object is the cubic box.
A.2 STACK SCENARIO
The physical setup of this scenario is much the same as that in Push scenario, except that there is no wall on the table. At the beginning of each episode, the number of boxes on the table, the goal position and the target object index sampled from a designed task curriculum. As explained in the main paper, there are two types of tasks, stacking and pick-and-ples -paace in the curriculum, and the type of task is also reset in each episode.
The (x, y) coordinate of the goal is uniformly sampled from 30cm x 30cm square on the table, while goal height 9= initialized depending on the type of task of the current episode: for pick-and-placee tasks, 9= ~ table height + U(0, 0.45) and for stacking tasks, I= = table height N box height, where E Maaz] denotes the number of boxes.
Observation space The observation vector shares the same structure with Push scenario, but includes another one-hot vector indicating the type of the task.
Action space The action vector is the same as that in Push scenario.
Hard case configuration
The hard cases are most interested in stacking Nmax boxes so that the target box reaches the goal position with the gripper fingers left apart.
A.3 MAZE SCENARIO
This scenario deals with 2D maze. The agent (green) can only apply force to itself in the directions parallel to the floor plane. The position of the agent and the goal are both uniformly sampled from the collision-free space in the maze.
Observation space The structure of observation space is generally the same the Push scenario except that the state and velocity of gripper fingers are not included in the state vector since there is no gripper in Maze scenarios. In U-Shape Maze, the one-hot target object indicator is omitted since there is no object except the agent itself. For experiments in the visual domain, RGB images of shape 48 48 directly used as observations.
15

---

Published as a conference paper at ICLR 2021
<34
(a) reduction
(b) reduced task
(c) ①
product
(d)
+ min
(e)
avg
Figure 11: Heatmap of value function with different composition operators. (a) value for moving elongated box elsewhere, (b) value for moving cubic box to goal w.r.t different elongated box position, (c) composite value with product operator, (d) composite value with min operator, (e)
composite value with average operator.
Action space
The action a 2-dimensional vector representing the force applied to the agent.
Hard case configuration There is manually designed hard case for U-Shape Maze and U-Wall Maze. In hard cases of 4-Room maze, a random number of elongated boxes block the doors on. The goal is forced initialize in different room from that the cubic box is in. For hard cases of 3-Room Maze, each elongated box blocks a door. More precisely, the rooms that elongated boxes are in are determined by the agent's position: if the agent is in the leftmost room, the elongated boxes are placed to the left of each door; if the agent is in the middle room, the elongated boxes are also placed the middle room and each blocks door; if the agent the rightmost room, the elongated boxes are placed to the right of each door.
Fixed goal location In the fixed goal version of 3-Room maze, the goal is located at the same spot the rightmost room for each episode. In U-Shape Maze, the goal is always at the end of the maze.
B TRAINING DETAILS
Composition operator As is mentioned Sec. 4.1 there are multiple choices for the composition operator given two values (Eq. (]. In addition to the one used in SIR, i.e., product operator, we also visualize the composite values derived by other operators, including minimum (i.e., "min", taking the smaller value of the two) and average (i.e., take the mean value) in Fig.
Besides, note that due to value approximation error, even if the reward is 0/1, the output of learned value function may perfectly lie between and 1. So, in order to apply the "product" operator well in practice, we normalize the value functions before they are actually composed. Specifically, the composite values are computed follow:
V(SA, min, V(SA, SB,)
V(SA,8n, @ product)
max, V( 8B,) min, ((SA,
V(sg, gA) miny V(s ( 9A)
max, ((B 94) min, V V(SB, 9A)
V(SA, min)
minn(V sp, V ((nn
V8AA,88,i00 @ avg) 8(, + V(3n,,gA)
2
Empirically, the "product" operator is the best among all candidates, since it most clearly demonstrates two higu-value modes on both sides of the door and low composite values the door.
Estimating When combining SIR with SAC baseline. the output of value function converges to stable range after the initial warm-up phase (see Fig. [2a). Therefore it suffices to use a static high threshold (set to 0.9 in Push scenario with mixed task sampler and I in all other cases) to
16

---

Published as a conference paper at ICLR 2021
lue success meen value
smouthed value fell meer value value
(a) STR + SAC
(b) SIR PPO
Figure 12: Values of all the reduction targets with different baseline algorithms. Green: successful targets; Orange: failed targets; Red (in the right plot): running average of values.
discard reduction targets in the initial value overestimation phase and static low threshold o to filter out reduction targets with low values that are not likely to succeed. When training SIR with PPO baseline, We empirically observe that the scale of value function keeps increasing as training proceeds, therefore a static filtering threshold is not appropriate here. Hence we maintain an online estimation of the filtering threshold by keeping a running average of composite values of all the selected reduction targets, As is shown Fig. 12b the successful reduction targets typically have higher values than average.
Designed task curriculum in Stack scenario The initial positions of all the boxes are generated follows: select M (0 < M < N 1) boxes from the total N boxes, and stack them under the goal, then initialize other boxes randomly over a square on the table. The ratio of stacking and pick-and-place tasks adapted according to the agent's learning progress. We keep 70% chance of sampling pick-and-place tasks until the agent achieves success rate of 0.8 when evaluating on pick-and-place tasks, then gradually decrease the ratio 30%. Note that such task curriculum is applied for all the experimented algorithms in Stack scenario.
Baseline implementation We utilize prioritized experience replay when working with off- off-policy RL algorithms. Two separate replay buffers Dr Dil prepared for rollouts generated by direct policy execution and composite task reduction. We compute priority as p p= Ir + yV - Ql for each instance when storing transitions into the buffers. When sampling from Dr U Dit each element can be sampled with probability proportional to p The replay buffers maintain a fixed finite number of samples and data are flushed following the first-in-first-out manner.
As for on-policy baselines, data in Dr are discarded after every iteration. D' keeps track of a recent history of task reduction demonstration. As the training proceeds, we get better policies and new demonstrations with higher quality. Some stale demonstrations may not be beneficial anymore (c.g.. early accidental successes by random exploration). However, the advantage clipping scheme in Eq. 2 may not effectively eliminate undesired stale data: in the sparse reward setting, since all the demonstrations are successful trajectories, the advantage will be hardly negative Thus, we maintain the dataset Di as buffer which keeps every trajectory for a fixed number of iterations after it was generated.
Network architecture In Push scenario, simply use MLPs with 256 hidden units per layer to map the input observations to actions or values.
In Stack and Maze scenario, since there are more objects in observations, we adopt an attention- based feature extractor to get representation invariant to the number of objects. The original observation vector can be rewritten as [Oself: 01, 02, .... ). where Osel/ contains the state of the agent (robot or particle) and the position of the desired goal, o, < < S N) represents the state of each object. We then apply MLP to get observation embeddings ((Osetf). of objects is then computed by attending f((self) over g(o.):
< < N). The attention embedding
Σ w:g(o:), w; softmax(f g ((o:)), ) S i N.
(3)
TToough, it be negative in theory due discounted factor.
17

---

Published as a conference paper at ICLR 2021
Push
Stack
Push
Maze
#workers
32
32
#minibatches
32
32
replay buffer size
le5
le5
7
0.99
0.99
batch size
256
256
#opt epochs
10
10
y
0.98
0.98
learning rate
3e-4
3e-4
learning rate
3e-4
3e-4
#workers
32
64
o
0.7
0.5
#steps per iter
2048
8192
total timesteps
1.5e7
1e8 (3 boxes)
demo reuse
8
2.5e7 (2 boxes)
total timesteps
5e7
3c8
Table 3: Hyperparameters for SAC-based experi-
Table 4: Hyperparameters for PPO-
ments in different scenarios.
based experiments in different scenarios.
Pure RL
SIL
DS
SIR
Push Unif.
0.853
0.952
0.891
0.938
Push Mixed 30%
0.523
0.930
0.900
0.942
Stack (at most 2 boxes)
0.965
0,966
0.908
0.980
Stack (at most 3 boxes)
0.721
0.722
0.711
0.895
4-Room maze
0.649
0.576
0.645
0.695
Table 5: Final average success rate over the training task distribution.
Finally is concatenated with f(sst))) and fed into another MI.P to produce actions values.
Hyperparameters We summarize hyperparameters of off-policy and on-policy algorithms in each scenario in Table andd Table
C
MORE RESULTS
Success rate statistics The success rates over the training task distribution and on hard cases evaluated the end of training for all the experimented algorithms are listed in Table [ and Table All the numbers are averaged over 3 random seeds. The proposed SIR generally achieves the best result across the board.
Particularly in Stack scenario with 3 boxes, we provide more detailed hard-case success rates from all kinds of initial configurations for stacking 3 boxes (explained in Sec. B Table. 7 Although all the algorithms succeed from the initial states with 2 boxes already stacked by simply stacking the target box on top of the existing tower, only SIR can solve more compositional situations with box stacked in the beginning, which require strategic manipulation of other non-target boxes before finishing the tasks.
Additional results in Push scenario In addition the results presented in the main paper, which is trained on a mixture of 30% hard cases and 70% uniformly sampled cases, we also show the training curves with uniform task sampler Fig. 13 Furthermore, we repeat these experiments
Pure RL
SIL
DS
SIR
Push Unif.
0.449
0.816
0.598
0.939
Push Mixed 30%
0.568
0.979
0.975
0.983
Stack (at most 2 boxes)
0.927
0.954
0.759
0.988
Stack (at most 3 boxes)
0.270
0.294
0.275
0.846
4-Room maze
0.331
0.274
0.512
0.427
Table 6: Final hard-case success rate.
18

---

Published as a conference paper at ICLR 2021
Pure RI.
SIL.
DS
SIR
boxes stacked
0,851
0.899
0.889
0.972
box stacked
0.000
0.000
0.000
0.911
From scratch
0.000
0.000
0.000
0.716
Table 7: Hard-case success rate in Stack scenario evaluated in all kinds of initial configurations for stacking 3 boxes in the task curriculum.
1.0
1.0
1.0
1.0
0.8
haard SuCC rate
0.8
0.8
0.6
avg. SUCC.
0.6%
0.4
0.4
0.4
SAC
SIL
0.
D5
0.5
1.0
1.0
0.5
100
0.5
1.0
samples
187
samples
1e7
samples
167
samples
167
(a) Mixed sampler with 30% hard cases.
(b) Uniform sampler.
Figure 13: Training results of SAC-based algorithms in the Push scenario with 2 different task samplers. In each case, we show avg. success rate w.r.t. samples over current task distribution (left) and in hard cases (right).
with PPO-based algorithms as shown Fig. 14 SIR achieves generally the best result compared with other baselines in all the settings, especially in hard cases which require compositional policies. also illustrates that SIR is agnostic to baseline RL algorithms.
Additional results Stack scenario Stack scenario, we also provide results trained with maximum of two boxes. SIR is compared with other three baselines in Fig. [6 Our method is significantly more sample efficient especially when learning to stack.
Additional results Maze scenario We empirically find that SAC runs a magnitude slower in wall-clock time than PPO in n-Room muze as shown in Figure 17, therefore use PPO-based algorithms in 4-Room maze experiments in the main paper. The result with SAC-based algorithms in 3- Room maze scenario is shown in Figure 18 SIR still outperforms SAC and SIL baselines in terms of average success rate over both the training task distribution and the hard tasks only.
We also include the DS reward explained in Push scenario baseline for comparison in Figure 19 Interestingly, DS surpasses all other methods when evaluated in hard cases only in the later training phase since discovers how to navigate around the walls and push the blocking box away the same time and remembers this policy.
Episode length We are also interested SIR-learned policy can efficiently solve tasks besides the success rate reported in the main paper. Hence test trained policies with different algorithms
10-
0.8
0.8
avg. SucC. rate
0.8
hard SUCC.
0.6
PPD
PPD
Sin
Sin
0.2
0.2
6.0
6.
samples
samples
samples
1n7
samples
(a) Mixed sampler with
cases.
(b) Uniform sampler.
Figure 14: Training results of PPO-based algorithms in the Push scenario with 2 different task samplers. In each case, we show avg. success rate w.r.t. samples over current task distribution (left) and in hard cases (right).
19

---

Published as a conference paper at ICLR 2021
Figure 13: SIR-learned strategy for hard case in the Stack scenario with 2 boxes. The agent aims to stack the blue box towards the blue spot which two-stories high.
1.0
1.0
succ.
0.6
0.4
SAC
0.2
DS
1.5
2.0
samples
1e7
samples
Figure 16: Training results the Stack scenario with a maximum of 2 boxes. We evaluate success rate across training currieulum (left) and in hard cases, i.e., stacking boxes (right).
on a fixed set of 500 hard tasks in each scenario and report the average length of successful episodes in Table Push and Maze scenarios, these hard tasks are directly sampled from corresponding hard case configurations, while in Stack scenario, we only sample the most difficult subset of hard case configurations, i.e. stacking from scratch. SIR achieves comparable mean successful episode length with other algorithms in Push and Maze scenarios, and is significantly more effective in Stack scenario where all other methods fail or struggle to solve.
Pure RL
SIL
DS
SIR
Push Unif.
23.67
21.88
22.78
22.73
Push Mixed 30%
20.95
20.64
20.23
20.16
Stack (2 boxes from scratch)
24.21
27.00
30.54
19.16
Stack (3 boxes from scratch)
N/A
N/A
N/A
39.72
4-Room maze
57.43
54.94
60.40
58.54
Table 8: Mean length of successful episodes of trained policy evaluated the same training iterations.
0.8
SucceSs rate
0.5
0.6
avg. succ. rate
0.4
02
0.4
0.2
SAC
SIR
0.0
Figure 17: Comparison between SAC and PPO in terms of wall-clock time in 3-Room maze scenario. The x-axis is measured in seconds.
samples
167
samples
Figure 18: Results of SAC-based algorithms
3-Room maze.
20

---

Published as a conference paper at ICLR 2021
6.5
avg. SUCC. rate
0.6
0.4
hard succ.
6.3
MP
0.0
samples
1el
samples
105
Figure 19: Complete training results of PPO-based algorithms in 4-Room maze.
21


Reviews:
[{"review_id": "szHrlzWnrBO", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary \nThis paper proposes a new method that combines task reduction and self-imitation learning for goal-based reinforcement learning problems. The idea is to decompose a hard task into two subtasks (subgoals) such that the solution to one of them is already known. Self-imitation learning is used to quickly learn to reproduce such successful trajectories. The experimental result shows that the proposed method outperforms the baseline SAC + HER and SAC + SIL as well as hierarchical architectures such as HIRO and DSC.\n\n## Pros\n* The idea is interesting and novel.\n* The empirical results are good.\n\n## Cons\n* Limited to (a subset of) goal-based RL problems.\n\n# Novelty\nThe proposed idea of decomposing a task into two easy tasks is novel and interesting. It would be worth citing and discussing a relevant prior work [1], which also proposes such a decomposition for goal-based RL. \n\n# Quality\n* The empirical results are good. Specifically, it is interesting that the proposed method outperforms hierarchical RL methods without being explicitly hierarchical.\n* At the same time, the proposed method seems very specific to a subset of goal-based RL problems, where searching the goal space is computationally tractable. \n* Though I appreciate the extension to visual domains using $\\beta$-VAE to remedy the aforementioned limitation, the U-Wall maze doesn’t seem like visually complex, and the result (Figure 8) is not very strong. Either showing much better results on Figure 8 or showing results on complex visual domains would strengthen the claim. \n* It would be more convincing and interesting to show that the proposed method can do deeper planning by applying task reduction recursively.\n\n# Clarity\n* The paper is easy to follow, and the figures are well-presented.  \n* What is the rationale behind $V(s_a, s_b, g_a) = V(s_a, s_b) * V(s_b, g_a)$? This seems quite specific to “goal-reaching” 1-or-0 reward structures. Do you have an idea how to generalize this to more general reward structures? \n* In Algorithm 1, do you generate a new trajectory to get $\\tau’$? If this is the case, is this taken into account as the number of steps (x-axis) in the learning curves? Otherwise, they are not fair comparisons. \n* Just to check if they are apples-to-apples comparisons, do you use HER across all methods (yours and baselines)?\nIt would be good to mention that this paper considers goal-based RL problems early in the paper (in abstract or introduction). \n\n[1] Floyd-Warshall Reinforcement Learning: Learning from Past Experiences to Reach New Goals, Vikas Dhiman et al.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "lqMvAFdXO2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#######################################################################\n\nSummary:\n\nIn this paper the authors propose a method for solving compositional tasks in the RL setting. The method (Self-Imitation via Reduction), is a 2-step method in which the agent first reduces the target task into two simpler tasks, and then solves the full task using as a demonstration the composite task uncovered in step-1.\n\n#######################################################################\n\nReasons for score:\n\nI am currently voting for a rejection based on what seem to be two key omissions from the paper:\n\n1. The way in which the set of 'library' tasks is selected, and\n2. A measure of how expensive this offline component of the algorithm is\n\nThe experimental comparisons could also have been stronger.\n\n#######################################################################\nPros:\n\n1. I think the paper is reasonable well written. I found just a few typos, and I think the key conceptual ideas are reasonably easy to follow. \n\n2. The 2-step implementation of some sort of \"policy reduction\" followed by an imitation learning step would seem to be a good in principle idea that merits further exploration\n\n#######################################################################\n\nCons:\n\n1. In Sec 3 the authors talk explicitly about a multi-task RL learning setting, and indeed a central part of the method is a search step over interim states $s_\\beta$ , but I do not see explicitly how this set is constructed. This is of course a critical consideration for a number of reasons:\n\n(1)  If this set of tasks is large, then you are likely to find a good $s_\\beta$, but the search space increases (as does the memory footprint)\n\n(2) If this set is small (and perhaps curated), then the subsequent result is weak (if the agent need only search over a small handful of interim tasks which already include moving the elongated box say, then of course the subsequent learning is rapid). \n\n2. The experimental results would be more compelling if comparisons were made to methods that similarly had some access to interim policies. The comparisons to SAC for example are valid in that they provide a lower bound, but there is additional information available to SIR. Similar it is unclear what the comparison to SAC with a dense rewards shows exactly.\n\n3. The authors mention that the method is extensible even though \"... tasks reduction only performs 1-step planning... SIR still retains the capability of learning an arbitrarily complex policy by alternating between imitation and reduction: as more tasks are solved, these learned tasks can recursive further serve as new reductions...\" - this is a nice idea, but I saw no evidence of this implementation in the paper.\n\n#######################################################################\n\nQuestions during rebuttal period:\n\nPlease address the concerns above. Also, you have some comparison with hierarchical policy algorithms in 9.a/b - is it possible to extend these to the other domains?\n\n#######################################################################\n\nSome general comments:\n\n- I think the results for these multi-step methods are often easier to digest and understand if the phases are presented separately:\n    - Phase 1, reduction:\n        - for each experiment, which task reduction was uncovered by the agent?\n        - as you know, in many cases there are multiple valid reductions, which does your algorithm find and why?\n        - since your reduction phase is 1-step and greedy, in which situations might it not work so well\n        - etc.\n    - Phase 2, imitation:\n        - comparison to other methods\n        - effect of parameter choices\n        - etc.\n- A little more justification for you particular experimental comparisons can be helpful. It seems like there are a few potential avenues you might have liked to explore:\n    - comparison to an information impoverished baseline (like SAC)\n    - comparison to different task distributions\n    - comparison to other subtask methods\n    - etc.", "extra_scores": {}, "extra_text": {}}, {"review_id": "R8XdVWbPadl", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The submission proposes an intuitive curriculum learning method which focuses on sparse reward tasks in RL and uses universal value function approximators. \nIt has 3 explicit steps: \n1. identifying a state to decompose the one task into two \n2. solve these new tasks \n3. solve the complete task by imitating the trajectories from both subtasks.\n \nOn the positive side, the paper is overall clearly written and easy to follow for most parts and performs commensurate or better to baselines on a set of simulated manipulation and locomotion domains.\n\nOn the negative side, the method often only performs commensurate or close to the baselines while introducing significant added complexity and additional hyperparameters. The stacking task, which demonstrates the strongest benefit for SIR, requires strong domain knowledge as the search for intermediate states is highly constrained.  Constraining the search for intermediate states to positions with blocks under the required stacking position is significant domain knowledge unavailable to the other methods. The minimum requirement for a fairer comparison would be to include a version of SIR without this constraint. \n\nMore generally, aspects regarding the specifics of the space in which we search for intermediate states and the baselines remain unclear (e.g. in terms of the search space since according to the appendix the space for states and goals is not the same and e.g. for stacking other constraints exist).\n\nThe final problem regarding the evaluation is that while presenting essentially a curriculum learning method, the paper does not compare against other work in curriculum learning as baseline (e.g. [1,2]).\n\nOther questions remain such as the surprising statement that off-policy SAC underperforms on-policy PPO on the navigation task. Statements that are counter to intuition and existing comparisons between SAC and PPO should be supported with experimental results.\n\nOverall, the introduced method follows a valuable direction for curriculum learning in RL but the submission demonstrates significant weaknesses regarding fair evaluation.\n\n[1] Florensa, Carlos, et al. Automatic goal generation  for reinforcement learning agents. In International Conference on Machine Learning 2018\n[2] Racaniere, Sebastien et al. Automated curriculum generation through setter-solver interactions. In International Conference on Learning Representations 2020.\n\n\n(Disclaimer: I have reviewed a previously submitted version of this work and a big share of critical points remains the same between both reviews including domain knowledge unavailable to baselines and comparison to other curriculum learning methods.)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QPRiuFPuULK", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents Self Imitation via Reduction (SIR) an approach to learning long-horizon tasks by successively reducing it to easy to solve tasks, generating solutions to these easier tasks and self-imitation on successful task solutions. This is done by training a goal-conditioned policy together with a universal value function. When given a task that cannot be solved via the current policy, SIR searches for an intermediate state that divides the task into two easily solvable sub-tasks; this search is carried out by maximising the (composed) value of the sub-trajectories under the current policy. The policy is then executed for these sub-tasks in sequence; success in both these sub-tasks means a solution for the full task is now found. This solution is used as a demonstration that the policy can use for self-imitation via an advantage weighted behavioural cloning objective. This is combined with the policy loss of standard actor-critic algorithms such as SAC and PPO in both the off-policy and on-policy settings respectively and shows significant performance improvements compared to baselines on several long-horizon tasks such as robotic pushing, stacking 3 blocks and a multi-room maze task. \n\nA few points:\n1. This approach tackles an important problem of effectively learning policies for long-horizon tasks taking advantage of compositional structure of sub-problems. It nicely combines several ideas from prior work such as self-imitation and universal value functions to present a method that is conceptual simple but performs well empirically on complex tasks.\n2. SIR seems quite related to the two-level architecture in standard hierarchical RL approaches — the planner for task reduction is the top level and the low level being the policy. There is a few key difference though: SIR uses this structure primarily for learning and over time the knowledge in this bi-level structure is distilled into the low level policy. It would be interesting if this is discussed a bit further in the paper.\n3. Unlike traditional sub-goal selection methods which recursively decompose the problem into sub-problems, SIR does a single reduction step to decompose the task into two sub-tasks. This works well under the assumption that the goal-conditioned policy has sufficient representational capacity to capture the variety of tasks in the environment. Is it possible to extend the current approach to a recursive decomposition for harder tasks?\n4. The paper is very well written. There is a clear motivation, contributions and a thorough overview of the related work in this area. The discussions are well structured and together with the appendix a lot of detail is provided on the experiments and methods.\n5. A crucial component of the proposed approach is the search for possible reductions. In the proposed approach this is highly structured and limited to very few dimensions of the actual observation space (e.g. only considering object translations in the pushing task, only considering moving unstacked blocks in the stacking task). This provides a key advantage to SIR compared to baselines as it significantly reduces the branching factor of search and consequently can lead to many successful reductions early on during training. This somewhat reduces the strength of the proposed results. As an additional baseline, it would be good to see the performance achieved by SIR when search is not structured and allowed to explore all dimensions of the state space. Does this reduce the performance and/or learning speed of SIR?\n6. The paper presents initial results on a vision-based task where a VAE representation is used as state. What is the dimensionality of this representation? As mentioned above, this can have a significant impact on the learning performance (while CEM should do better compared to random search it is not clear if this can mitigate the issue by itself).\n7. Another key limitation of the proposed approach is the reliance on arbitrary resets which is not feasible in the real world. While this is briefly discussed in the paper it is not clear how this can be mitigated easily. A more detailed discussion would be useful.\n\nOverall, the approach is quite nice and the initial results are encouraging. I would suggest a weak accept.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a method for solving challenging sparse reward problems by performing task reduction followed by self-imitation learning from solution trajectories to the reduced tasks.  The core innovation seems to me to be the uses of the reduction search, which is essentially a form of recursive subgoal selection, but where the subgoals are sure to be achievable as assessed by leveraging the learned value function.  This idea seems rather general, though its use is strongly facilitated in this paper by definition of the space (i.e. that object target is the space, is pre-specified; there is only one, rather limited result on a pixel-based task). 

Note: Another submission to this conference also explores a quite similar idea to the task reduction proposed in this paper -- see "Divide-and-Conquer Monte Carlo Tree Search".  The breaking down of the problem into sub-problems using the value function is similar, but the details of how the papers proceed from there is quite distinct.

This is a difficult meta-review decision due to the fairly mixed reviews, coupled with limited engagement in the discussion phase.  Two reviewers felt the paper was solid and could be accepted (R1 and R2 with scores 7 and 6 respectively).  R3 gave a borderline review that leaned towards reject (score 5).  R3 replied to the initial author response, which provided helpful feedback to the authors. Ultimately, in my assessment, the authors did a fairly thorough job of addressing some of the points raised by R3, including by adding an additional comparison even where they didn't agree with the reviewer. R4 assigned the paper the lowest score of 3.  The authors provided a lengthy reply to this review asserting that the review may have reflected misunderstanding of paper details, but the reviewer did not respond to the authors.    

Two core issues raised about this paper relate to the definition of the space for subgoals and the limited difficulty of the tasks. However, this method does not claim to be entirely ignorant of the task space so I don't see the fact that they do include some domain knowledge in designing the goal space to be totally undermining of the method.  They focus on the complementary issue of how to break down difficult problems into sub-problems.  While it would be considerably more impressive if the goal space were learned, I think this harder version of the problem remains a fundamental and deep problem within AI, so it seems to me too much to ask of the present paper (especially given that it was not the stated focus of the paper).  And while the tasks explored in the paper are a little contrived (some repetitive motifs and designed with a relatively small search space over subtasks), these problems do have some complex structure.  Compared to many works in this field, I applaud the authors for engaging with problems with both long-horizon task structure as well as complex high-DoF continuous control component.

While I agree with some of the concerns raised, my overall assessment is that I find the contributions sufficiently innovative and substantial to justify acceptance.  The authors proposed a specific innovation and evaluated that innovation.  Insofar as their innovation is somewhat general, I don't think this paper can be the last word on how well it compares with the diverse approaches it could be set against.  And while the experiments are not definitive, I do think they do constitute a fairly ambitious initial validation of the core idea.  

Decision: Accept (Poster)