{'fraction_non_alphanumeric': 0.026991010525364775, 'fraction_numerical': 0.0075891042146632335, 'mean_word_length': 4.740308569946843, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning Compositional Neural Programs for Continuous Control

We propose a novel solution to challenging sparse-reward, continuous control problems that require hierarchical planning at multiple levels of abstraction. Our solution, dubbed AlphaNPI-X, involves three separate stages of learning. First, we use off-policy reinforcement learning algorithms with experience replay to learn a set of atomic goal-conditioned policies, which can be easily repurposed for many tasks. Second, we learn self-models describing the effect of the atomic policies on the environment. Third, the self-models are harnessed to learn recursive compositional programs with multiple levels of abstraction. The key insight is that the self-models enable planning by imagination, obviating the need for interaction with the world when learning higher-level compositional programs. To accomplish the third stage of learning, we extend the AlphaNPI algorithm, which applies AlphaZero to learn recursive neural programmer-interpreters. We empirically show that AlphaNPI-X can effectively learn to tackle challenging sparse manipulation tasks, such as stacking multiple blocks, where powerful model-free baselines fail.


Introduction
Deep reinforcement learning (RL) has advanced many control domains, including dexterous object manipulation [1,4,30], agile locomotion [45] and navigation [12,17]. Despite these successes, several key challenges remain. Stuart Russell phrases one of these challenges eloquently in [37]: "Intelligent behavior over long time scales requires the ability to plan and manage activity hierarchically, at multiple levels of abstraction" and "the main missing piece of the puzzle is a method for constructing the hierarchy of abstract actions in the first place". If achieved, this capability would be "The most important step needed to reach human-level AI" [37]. This challenge is particularly daunting when temporally extended tasks are combined with sparse binary rewards. In this case the agent does not receive any feedback from the environment while having to decide on a complex course of action, and receives a non-zero reward only after having fully solved the task.
Low sample efficiency is another challenge. In the absence of demonstrations, model-free RL agents require many interactions with the environment to converge to a satisfactory policy [1]. We argue in this paper that both challenges can be addressed by learning models and compositional neural programs. In particular, planning with a learned internal model of the world reduces the amount of necessary interactions with the environment. By imagining likely future scenarios, an agent can avoid making mistakes in the real environment and instead find a sound plan before acting on the environment.
Many real-world tasks are naturally decomposed into hierarchical structures. We hypothesize that learning a variety of skills which can be reused and composed to learn more complex skills is key to tackling long-horizon sparse reward tasks in a sample efficient manner. Such compositionality, formalised by hierarchical RL (HRL), enables agents to explore in a temporally correlated manner, improving sample efficiency by reusing previously trained lower level skills. Unfortunately, prior studies in HRL typically assume that the hierarchy is given, or learn very simple forms of hierarchy in a model-free manner.
We propose a novel method, AlphaNPI-X, to learn programmatic policies which can perform hierarchical planning at multiple levels of abstraction in sparse reward continuous control problems. We first train low-level atomic policies that can be recomposed and re-purposed, represented by a single goal-conditioned neural network. We leverage off-policy reinforcement learning with hindsight experience replay [3] to train these efficiently. Next, we learn a transition model over the effects of these atomic policies, to imagine likely future scenarios, removing the need to interact with the real environment. Lastly, we learn recursive compositional programs, which combine low-level atomic policies at multiple levels of hierarchy, by planning over the learnt transition models, alleviating the need to interact with the environment. This is made possible by extending the AlphaNPI algorithm [33] which applies AlphaZero-style planning [43] in a recursive manner to learn recombinable libraries of symbolic programs.
We show that our agent can learn to successfully combine skills hierarchically to solve challenging robotic manipulation tasks through look-ahead planning, even in the absence of any further interactions with the environment and where powerful model-free baselines struggle to get off the ground. 1

Related Work
Our work is motivated by the central concern of constructing a hierarchy of abstract actions to deal with multiple challenging continuous control problems with sparse rewards. In addition, we want these actions to be reused and recomposed across different levels of hierarchy through planning with a focus on sample efficiency. This brings several research areas together, namely multitask learning, hierarchical reinforcement learning (HRL) and model-based reinforcement learning (MBRL).
As we have shown, learning continuous control from sparse binary rewards is difficult because it requires the agent to find long sequences of continuous actions from very few information. Other works tackling similar block stacking problems [21,26] have either used a very precisely tuned curriculum, auxiliary tasks or reward engineering to succeed. In contrast, we show that by relying on planning even in absence of interactions with the environment we can successfully learn from raw reward signals.
Multitask learning and the resulting transfer learning challenge have been extensively studied across a large variety of domains, ranging from supervised problems, to goal-reaching in robotics or multiagent settings [46,49]. A common requirement is to modify an agent's behaviour depending on the currently inferred task. Universal value functions [38] have been identified as a general factorized representation which is amenable to goal-conditioning agents and can be trained effectively [6], when one has access to appropriately varied tasks to train from. Hindsight Experience Replay (HER) [3] helps improve the training efficiency by allowing past experience to be relabelled retroactively and has shown great promises in variety of domains. However, using a single task conditioning vector has its limitations when addressing long horizon problems. Other works explore different ways to break long-horizon tasks into sequences of sub-goals [31,7], or leverage HER and curiosity signals to tackle similar robotic manipulation tasks [21]. In our work, we leverage HER to train low-level goal-conditioned policies, but additionally learn to combine them sequentially using a program-guided meta-controller.
The problem of learning to sequence sub-behaviours together has been well-studied in the context of HRL [44,5] and has seen consistent progress throughout the years [23,24,47,28]. Learning both which sub-behaviours could be useful and how to combine them still remains a hard problem, which is often addressed by pre-learning sub-behaviours using a variety of signals (e.g. rewards [6], demonstrations [16], state-space coverage [11,34,22,19], empowerment [14], among many others). Our work assumes we know that some sub-behaviours can be generically useful (like stacking or moving blocks [36]). We learn them using goal-conditioned policies as explained above, but we expand how these can be combined by allowing sub-behaviours to call other sub-behaviours, enabling complex hierarchies of behaviours to be discovered. We share this motivation with [25] which explores learning policies with multiple levels of hierarchy.
Our work also relates to frameworks which decompose the value function of an MDP into combination of smaller MDPs, such as MAXQ [10] or the factored MDP formulation [15], and more recent work which leverage natural language to achieve behaviour compositionality and generalisation [20,2]. As our meta-controller uses MCTS with a learned model, this also relates to advances in MBRL [29,32,39,40]. Our work extends this to the use of hierarchical programmatic skills. This closely connects to model-based HRL research area which has seen only limited attention so far [41,32,18].
Finally, our work capitalizes on recent advances in Neural Programmers Interpreters (NPI) [35], in particular AlphaNPI [33]. NPI learns a library of program embeddings that can be recombined using a core recurrent neural network that learns to interpret arbitrary programs. AlphaNPI augments NPI with AlphaZero [42,43] style MCTS search and RL applied to symbolic tasks such as Tower of Hanoi and sorting. We extend AlphaNPI to challenging continuous control domains and learn a transition model over programs instead of using the environment. Our work shares similar motivation with [48] where NPI is applied to solve different robotic tasks, but we do not require execution traces or pre-trained low-level policies.  Figure 1: Illustrative example of an execution trace for the CLEAN_AND_STACK program. This trace is not optimal as the program may be realised in fewer moves but it corresponds to one of the solutions found by AlphaNPI-X during training. Atomic program calls are shown in green and non-atomic program calls are shown in blue.

Problem Definition
In this paper, we aim to learn libraries of skills to solve a variety of tasks in continuous action domains with sparse rewards. Consider the task shown in Figure 1 where the agent's goal is to take the environment from its initial state where four blocks are randomly placed to the desired final state where blocks are in their corresponding coloured zones and stacked on top of each other. We formalize skills and their combinations as programs. An example programmatic trace for solving this task is shown where the sequence of programs are called to take the environment from the initial state to the final rewarding state. We specify two distinct types of programs: Atomic programs (shown in green) are low-level goal-conditioned policies which take actions in the environment for a fixed number of steps T . Non-atomic programs (shown in blue) are a combination of atomic and/or other non-atomic programs, allowing multiple possible levels of hierarchies in behaviour.
We base our experiments on a set of robotic tasks with continuous action space. Due to the lack of any long-horizon hierarchical multi-task benchmarks, we extended the OpenAI Gym Fetch environment [8] with tasks exhibiting such requirements. We consider a target set of tasks represented by a  Table 1: Programs library for the fetch arm environment. We obtain 20 atomic and 7 non atomic programs when considering all possible combinations when expending programs arguments. Please see Supp. Section A for a detailed explanation of all programs and Table 3 for all combinations when expending program arguments.
hierarchical library of programs, see Table 1. These tasks involve controlling a robotic arm with 7-DOF to manipulate 4 coloured blocks in the environment. Tasks vary from simple block stacking to arranging all blocks into different areas depending on their colour. Initial block positions on the table and arm positions are randomized in all tasks. We consider 20 atomic programs that correspond to operating on one block at a time as well as 7 non-atomic programs that require interacting with 2 to 4 blocks. We give the full specifications of these tasks in Sup. Table 3.
We consider a continuous action space A, a continuous state space S, an initial state distribution ρ and a transition function T : A × S → S. The state vector contains the positions, rotations, linear and angular velocities of the gripper and all blocks. More precisely, a state s t has the form s t = [X 1 its pre-condition φ i : S → {0, 1} which assesses whether the program can start and its post-condition ψ i : S → {0, 1} which corresponds to the reward function here. Each program is associated to an MDP (S, A, T , R i ) which can start only in states such that the pre-condition φ i is satisfied, and where R i is a reward function that outputs 1 when the post-condition ψ i is satisfied and 0 otherwise.
Atomic programs are represented by a goal-conditioned neural network with continuous action space. Non-atomic programs use a modified action space: we replace the original continuous action space A by a discrete action space A = {a 1 , . . . , a n , STOP} where actions a i call programs p i and the STOP action enables the current program to terminate and return the execution to its calling program. Atomic programs don't have a STOP action, they terminate after T time steps.

AlphaNPI-X
AlphaNPI-X learns to solve multiple tasks by composing programs at different levels of hierarchy. Given a one-hot encoding of a program and states from the environment, the meta-controller calls either an atomic program, a non-atomic program or the STOP action. In the next sections, we will describe how learning and inference is performed.

Training AlphaNPI-X
Learning in our system operates in three stages: first we learn the atomic programs, then we learn a transition model over their effect and finally we train the meta-controller to combine them. We provide detailed explanation of how these modules are learned below.

Learning Atomic Programs
Our atomic programs consist of two components: a) a goal-setter that, given the atomic program encoding and the current environment state, generates a goal vector representing the desired position of the blocks in the environment and b) a goal-conditioned policy that gets a "goal" as a conditioning vector, produces continuous actions and terminates after T time steps.  Figure 2: AlphaNPI-X consists of three modules: A goal setter transforms an atomic program index into a goal that is executed by a goal-conditioned policy. A self-behavioural model transforms an atomic program index and an environment state into a prediction of the environment state once the goal-conditioned policy has been rolled for T time steps to execute this program. A meta-controller plans through the behavioural model to execute non-atomic programs.

C -Meta-Controller
To execute an atomic program p i from an initial state s satisfying the pre-condition φ i , the goal-setter, Θ, computes the goal g: g = Θ(s, i). We then roll the goal-conditioned policy π atomic θ (. , g) for T time steps to achieve the goal. In this work, the goal setter module Θ is provided which translates the atomic program specification into the corresponding goal vector indicating the desired position of the blocks which is also used to compute rewards.
We parametrize our shared goal-conditioned policy using Universal Value Function Approximators (UVFAs) [38]. UVFAs estimate a value function that does not only generalise over states but also goals. To accelerate training of this goal-conditioned UVFA, we leverage the "final" goal relabeling strategy introduced in HER [3]. Past episodes of experience are relabelled retroactively with goals that are different from the goal aimed for during data collection and instead correspond to the goal achieved in the final state of the episode. The mappings from state vector to goals is simply done via extracting the blocks positions directly from the state vector s. To deal with continuous control, we arbitrarily use DDPG [27] to train the goal-conditioned policy.
More formally, we define a goal space G which is a subspace of the state space S. The goalconditioned policy π atomic θ : S × G → A takes as inputs a state s ∈ S as well as a goal g ∈ G. We define the function h : S → G that extracts the goal g from a state s. This policy is trained with the The goal setter as Θ : S × {1 . . . k} → G takes an initial state and an atomic program index and returns a goal such that f uvf a (s, Θ(s, i)) = ψ i (s). We can thus express any atomic program policy π i as π i (.) = π atomic θ (. , Θ(. , i)) , ∀i ≤ k.
We first train the policy with HER to achieve goals sampled uniformly in G from any state sampled from ρ. However, the distribution of initial states encountered by each atomic program may be very different when executing programs sequentially (as will happen when non-atomic programs are introduced). Thus, after the initial training, we continue training the policy, but with probability 0.5 we do not reset the environment between episodes, to approximate the real distribution of initial states which happens when atomic programs are chained together. Hence, the initial state s is either  sampled randomly or kept as the last state observed in the previous episode. We later show our empirical results and analysis regarding both training phases.

Learning Self-Behavioural Model
After learning a set of atomic programs we learn a transition model over their effects: Ω w : S × {1 . . . k} → S, parameterized with a neural network. As Figure 2-B shows, this module takes as input an initial state and an atomic program index and the output is the prediction of the environment state obtained when rolling the policy associated to this program for T time steps from the initial state. We use a fully connected MLP and train it by minimizing the mean-squared error to the ground-truth final states. This enables our model to make jumpy predictions over the effect of executing an atomic program during search, hence removing the need for any interactions with the environment during planning. Learning this model enables us to imagine the state of the environment following an atomic program execution and hence to avoid any further calls to atomic programs that would each have to perform many actions in the environment.

Learning the Meta-Controller
In order to compose atomic programs together into hierarchical stacks of non-atomic programs, we use a meta-controller inspired by AlphaNPI [33]. The meta-controller interprets and selects the next program to execute using neural-network guided Monte Carlo Tree Search (MCTS) [43,33], conditioned on the current program index and states from the environment (see Figure 2 for an overview of a node expansion).
We train the meta-controller using the recursive MCTS strategy introduced in AlphaNPI [33]: during search, if the selected action is non-atomic, we recursively build a new Monte Carlo tree for that program, using the same state s t . See Supp. Section B for a detailed description of the search process and pseudo-code.
In AlphaNPI [33], similar to AlphaZero, during the tree search, future scenarios were evaluated by leveraging the ground-truth environment, without any temporal abstraction. Instead in this work, we do not use the environment directly during planning, but replace it by our learnt transition model over the effects of the atomic programs, the self-behavioural model described in Section 4.1, resulting in a far more sample efficient algorithm. Besides, AlphaNPI used a hand-coded curriculum where the agent gradually learned from easy to hard programs. Instead here, we randomly sample at each iteration a program to learn from, removing the need for any supervision and hand-crafting of a curriculum. Inspired by recent work [9], we also implemented an automated curriculum strategy based on learning progress, however we found that it does not outperform random sampling (see more detailed explanations and results in Supp. Section B). is trained in two phases. During the first phase, goals and initial states are sampled uniformly. During the second phase, we do not reset the environment with probability p between two consecutive episodes to approximate the real distribution of initial states. Once the goal policy is trained, we learn a model of its behaviour. Left. Comparing performance after phase 2 for different probabilities p. Middle. Comparing performance between phase 1 and phase 2. Right. Comparing model predictions performance when trained on different number of episodes generated with the goal policy.

Inference with AlphaNPI-X
To infer with AlphaNPI-X, we compare three different inference strategies: 1) Rely only on the policy network, without planning. 2) Plan a whole trajectory using the learned transition model (i.e. self-behavioural model) and execute it fully (i.e. open-loop planning). 3) Use a receding horizon for planning inspired by Model Predictive Control (MPC) [13]. During execution, observed states can diverge from the predictions made by the self-behavioural model due to distribution shift, especially for long planning horizons, which deteriorates performance. To counter that, we do not commit to a plan for the full episode, but instead re-plan after executing any atomic program (non-atomic programs do not trigger re-planning). The comparison between these inference methods can be found in Table 2. We also provide a detailed example in Supp. Section C.

Experiments and Results
We first train the atomic policies using DDPG with HER relabelling described in Section 4.1. Initial block positions on the table as well as gripper position are randomized. Additional details regarding the experimental setup is provided in Supp. Section D. In the first phase of training, we train the agent for 100 epochs during uniform goal sampling. In the second phase we continue training for 150 epochs where we change the sampling distribution to allow no resets between episodes to mimic the desired setting where skills are sequentially executed.
We evaluate the agent performance on goals corresponding to single atomic programs as well as two multi-step sequential atomic program executions, MultiStep-Moving which requires 4 consecutive calls to MOVE_TO_ZONE and MultiStep-Stacking which requires 3 consecutive calls to STACK (see Figure 4). We observe that while the agent obtains decent performance on executing atomic programs in the first phase, the second phase is indeed crucial to ensure success of the sequential execution of the programs. We also observe that the reset probability affects the performance and p = 0.5 provides the better trade-off between the asymptotic training performance and the agent ability to execute programs sequentially. More details are included in Supp. Section E.
We then train the self-behavioural model to predict the effect of atomic programs, using three datasets respectively made of 10k, 50k and 100k episodes played with the goal-conditioned policy. As during the second phase of training, we did not reset the environment between two episodes with a probability 0.5. We trained the self-behavioural model for 500 epochs on each data set. Figure 4 shows the performance aggregated across different variations of STACK and MOVE_TO_ZONE behaviours.
To train the meta-controller, we randomly sample from the set of non-atomic programs during training. In Figure-5, we report the performance on all non-atomic tasks during the evolution of training. We also investigated the use of an automated curriculum via learning progress but observed that it does not outperform random sampling (please see Supp. Section B.3 for details). After training for 700 epochs, we evaluate the AlphaNPI-X agent on each non-atomic program in the library shown in Table 2. Our results indicate that removing planning significantly reduces performance, especially for  Table 2: We compare the performance of AlphaNPI-X in different inference settings described in Section 4.2 as well as against 2 model-free baselines. Each program is executed 100 times with randomized environment configuration. For programs with arguments, the performance is averaged over all possible argument combinations. The full list of programs is provided in Supp. Section A.
stacking 4 blocks where removing planning results in complete failure. We observe that re-planning during inference significantly helps improve the agent's performance overall.
We compare our method to two baselines to illustrate the difficulty for standard RL methods to solve tasks with sparse reward signals. First, we implemented a multitask DDPG (M-DDPG) that takes as input the environment state and a one hot encoding of a non-atomic program. At each iteration, M-DDPG selects randomly a program index and plays one episode in the environment. Second, we implemented a M-DDPG + HER agent which leverages a goal setter for non-atomic tasks described in Section 4.1. This non atomic programs goal setter is not available to AlphaNPI-X. This agent has more information than its M-DDPG counterpart. Instead of receiving a program index, it receives a goal vector representing the desired end state of the blocks. As in HER, goals are relabelled during training. We observe that M-DDPG is unable to learn any non-atomic program. It is also the case for M-DDPG + HER despite having access to the additional goal representations. This shows that standard exploration mechanisms in model-free agents such as in DDPG, where Gaussian noise is added to the actions, is very unlikely to lead to rewarding sequences and hence learning is hindered.

Conclusion
In this paper, we proposed AlphaNPI-X, a novel method for constructing a hierarchy of abstract actions in a rich object manipulation domain with sparse rewards and long horizons. Several ingredients proved critical in the design of AlphaNPI-X. First, by learning a self-behavioural model, we can leverage the power of recursive AlphaZero-style look-ahead planning across multiple levels of hierarchy, without ever interacting with the real environment. Second, planning with a receding horizon at inference time resulted in more robust performance. We also observed that our approach does not require a carefully designed curriculum commonly used in NPI so random task sampling can be simply used instead. Experimental results demonstrated that AlphaNPI-X, using an abstract imagination-based reasoning, can simultaneously solve multiple complex tasks involving dexterous object manipulation beyond the reach of model-free methods.
A limitation of our work is that similar to AlphaNPI, we pre-specified a hierarchical library of the programs to be learned. While it enables human interpretability, this requirement is still quite strong. Thus, a natural next step would be to extend our algorithm to discover these programmatic abstractions during training so that our agent can specify and learn new skills hierarchically in a fully unsupervised manner.

Broader Impact
Our paper presents a sample efficient technique for learning in sparse-reward temporally extended settings. It does not require any human demonstrations and can learn purely from sparse reward signals. Moreover, after learning low-level skills, it can learn to combine them to solve challenging new tasks without any requirement to interact with the environment. We believe this has a positive impact in making reinforcement learning techniques more accessible and applicable in settings where interacting with the environment is costly or even dangerous such as robotics. Due to the compositional nature of our method, the interpretability of the agent's policy is improved as highlevel programs explicitly indicate the intention of the agent over multiple steps of behaviour. This participates in the effort of building more interpretable and explainable reinforcement learning agents in general. Furthermore, by releasing our code and environments we believe that we help efforts in reproducible science and allow the wider community to build upon and extend our work in the future.

Supplementary material A Programs library
Our program library includes 20 atomic programs and 7 non-atomic ones. The full list of these programs can be viewed in Table 3. In the AlphaNPI paper, the program library contained only five atomic programs and 3 non-atomic programs. Thus, the branching factor in the tree search in AlphaNPI-X is on average much greater than in the AlphaNPI paper. Furthermore, in this work, these atomic programs are learned and therefore might not always execute as expected while in AlphaNPI the five atomic programs are hard-coded in the environment and thus execute successfully anytime they are called.
While in this study we removed the need for a hierarchy of programs during learning, we still defined programs levels for two purposes: (i) to control the dependencies between programs, programs of lower levels cannot call programs of higher levels; (ii) to facilitate the tree search by relying on the level balancing term L introduced in the original AlphaNPI P-UCT criterion. In this context, we defined CLEAN_TABLE and CLEAN_AND_STACK as level 2 programs, STACK_ALL_BLOCKS, MOVE_ALL_TO_ZONE and MOVE_ALL_TO_ZONE as level 1 programs. The atomic programs are defined as level 0 programs. Interestingly, the natural order learned during training (when sampling random program indices to learn from) matches this hierarchy, see Figure 11.  Here we provide the list of symbols used in our method section:

B.2 AlphaNPI
Here we provide some further details on the AlphaNPI method, which we use and extend for our meta-controller. The AlphaNPI agent uses a recursion augmented Monte Carlo Tree Search (MCTS) algorithm to learn libraries of hierarchical programs from sparse reward signals. The tree search is guided by an actor-critic network inspired from the Neural Programmers-Interpreter (NPI) architecture. A stack is used to handle programs as in a standard program execution: when a nonatomic program calls another program, the current NPI network's hidden state is saved in a stack and the next program execution starts. When it terminates, the execution goes back to the previous program and the network gets back its previous hidden state. The mechanism is also applied to MCTS itself: when the current search decides to execute another program, the current tree is saved along with the network's hidden state in the stack and a new search starts to execute the desired program.
The neural network takes as input an environment state s t and a program index i t and returns a vector of probabilities over the next programs to call, π t , as well as a prediction for the value V t . The network is composed of five modules. An encoder f enc encodes the environment state into a vector o t = f enc (s t ) and a program embedding matrix M prog contains learnable embedding for each non-atomic programs. The i-th row of the matrix contains the embedding p of the program referred by the index i such that p t = M prog (i t ). An LSTM core f lstm takes the encoded state and the program embedding as input and returns its hidden state h t . Finally, a policy head and a value head take the hidden state as input and return respectively π t and V t , see Figure 6.
The guided MCTS process is used to generate data to train the AlphaNPI neural network. A search returns a sequence of transitions (s t , i t , π mcts t , r) where π mcts t corresponds to the tree policy at time t and r is the final episode reward. The tree policy is computed from the tree nodes visit counts. (1) Figure 6: The AlphaNPI architecture, slightly modified from [33].
Note that in AlphaNPI-X, in contrast with the original AlphaNPI work, proper back-propagation through time (BPTT) over batches of trajectories is performed instead of gradient descent over batches of transitions, resulting in a more stable updates.
AlphaNPI can explore and exploit. In exploration mode, many simulations per node are performed, Dirichlet noise is added to the priors to help exploration and actions are chosen by sampling the tree policy vectors. In exploitation mode, significantly less simulations are used, no noise is added and actions are chosen by taking the argmax of the tree policy vectors. The tree is used in exploration mode to generate data for training and in exploitation mode at inference time.

B.3 Improvements over AlphaNPI
Distributed training and BPTT We improved AlphaNPI training speed and stability in distributing the algorithm. We use 10 actors in parallel. Each actor has a copy of the neural networks weights. It uses it to guide its tree searches to collect experiences. In each epoch, the experience collected by all the actors is sent to a centralized replay buffer. A learner, that has a copy of the network weights, samples batches in the buffer, computes the losses and performs gradient descent to update the network weights. When the learner is done, it sends the new weights to all the actors. We use the MPI (Message Passing Interface) paradigm through its python package MPI4py to implement the processes in parallel. Each actor uses 1 CPU.
Another improvement over the standard AlphaNPI is leveraging back-propagation through time (BPTT). The AlphaNPI agent uses an LSTM. During tree search, the LSTM states are stored inside the tree nodes. However, in the original AlphaNPI, transitions are stored independently and gradient descents are performed on batches of uncorrelated transitions. While it worked on the examples presented in the original paper, we found that implementing BPTT improves training stability.
Curriculum Learning At each training iteration, the agent selects the programs to train on. In the original AlphaNPI paper, the agents select programs following a hard-coded curriculum based on program complexity. In this work, we select programs randomly instead and thus remove the need for extra supervision. We also implemented an automated curriculum learning paradigm based on learning progress signal [9] and observed that it does not improve over random sampling. We compare both strategies in Figure 5. We detail below the learning progress based curriculum we used as a comparison.
The curriculum based on the program levels from the original AlphaNPI might be replaced by a curriculum based on learning progress. The agent focuses on programs for which its learning progress is maximum. This strategy requires less hyper-parameters and enables the agent to discover the same hierarchy implicitly. The learning progress for a program i is defined as the derivative over time of the agent performance on this program. At the beginning of each training iteration t, the agent attempts every non atomic program l times in exploitation mode. We note C i t the average performance, computed as mean reward over the l episodes, on program i at iteration t. Rewards are still assumed to be binary: 0 or 1. We compute the learning progress for program i as where the absolute derivative over time of the agent performance is approximated as the first order. Finally, we compute the probability p i t of choosing to train on the program i at iteration t as where ∈ [0, 1] is an hyperparameter and M is the total number of non atomic programs. The term * 1 M is used to balance exploration and exploitation, it ensures that the agent tries all programs with a non-zero probability.

C Example execution of the programs
Let us imagine we want to run the atomic program STACK_1_2. The state space is S = R 70 and the goal space is G = R 12 . A state s t contains all positions, angles, velocities and angular velocities of the blocks and of the robot articulations at time t. A goal g is the concatenation of desired final positions (x, y, z) for each block. Let us consider atomic program STACK_1_2 has index 0. In this case, we compute the goal corresponding to this program as g = Θ(s 0 , 0) = (x 2 0 , y 2 0 , z 2 0 +2d, x 2 0 , y 2 0 , z 2 0 , x 3 0 , y 3 0 , z 3 0 , x 4 0 , y 4 0 , z 4 0 ) where d is the block radius. This goal corresponds to positions where block 1 is stacked on block 2 and where other blocks have not been moved. The pre-condition of this program verifies in state s 0 that no other block is already on top of block 2 so that stacking is possible. If the pre-condition is verified, the goal policy is rolled for T = 50 time steps to execute this goal. When the goal policy terminates, the program post-condition is called on the final state s T and verifies for all blocks that their final position is in a sphere of radius around their expected final position described by goal g. The value we use for is the standard value used in HER [3].
We train the goal-conditioned policy π atomic θ so that it can reach goals g that corresponds to the atomic programs for any initial position, as long as the initial position verifies the atomic program precondition. Once trained, we learn its self behavioural model Ω w . This model takes an environment state and an atomic program index and predicts the environment state obtained when the goal policy has been rolled for T timesteps conditioned on goal and initial environment state. Thus, this model performs jumpy predictions, it does not capture instantaneous effects but rather global effects such as block 0 has been moved, block 1 has remained at its initial position.
When the model has been trained, we use it to learn non-atomic programs with our extended AlphaNPI. Let us imagine that we want to execute the CLEAN_AND_STACK program. This program is expected to stack, in any order, both orange blocks in the orange zone and both blue blocks in the blue zone. Its pre-condition is always true since it can be called from any initial position. Its post-condition looks at a state s and returns 1 if it finds an orange block with its center of gravity in the orange zone and with an orange block stacked in top of it. It verifies the same for the blue blocks. The post-condition returns 0 otherwise. The stacking test is performed as explained above looking at a sphere of radius around an ideal position.
A possible execution trace for this program is:  Figure 7: Illustrative example of an execution trace for the CLEAN_AND_STACK program. This trace is not optimal as the program may be realised in fewer moves but it corresponds to one of the solutions found by AlphaNPI-X during training. Atomic program calls are shown in green and non-atomic program calls are shown in blue.
In this trace, the non-atomic programs are shown in blue and the atomic programs are shown in green. Non-atomic program execution happens as in the original AlphaNPI. The execution of an atomic program happens as described before: when the atomic program is called, the current environment state is transformed into a goal vector that is realised by the goal-conditioned policy. In the trace above, the goal policy has been called 5 times with different goal vectors. We base our experiments on a set of robotic tasks with continuous action space. Due to the lack of any long-horizon hierarchical multi-task benchmarks, we extended the OpenAI Gym Fetch environment [8] with tasks exhibiting such requirements. We reused the core of the PICK AND PLACE environment and added two colored zones as well as four colored blocks that are indexed. We did not modify the environment physics. The action space is A = [−1, 1] 4 , it corresponds to continuous command dx, dy, dz, dα to the arm gripper. In this setting, the observation space is the same as the state space and contains all blocks and robot joint positions together with their linear and angular velocities. It is of dimension 70, with blocks ordered in the observations removing the need to provide their colour or index. More precisely, a state s t has the form s t = [X 1

D.3 Hyper-parameters
We provide all hyper-parameters used in our experiments for our method together with baselines.

E.1 Results of Goal Policy Training
We train the goal-conditioned policy π atomic θ in two consecutive phases. In the first phase we sample the initial states and goal-vectors randomly. During the second phase, we change the initial and goal state distributions to ensure that our goal-conditioned policy still performs well when called sequentially by the meta-controller. For initial states, with probability p we do not reset the initial state of the environment between episodes. This means that the initial state of some episodes are the final state achieved in the previous episode. To simplify this process in a distributed setting, we store the final states of all episodes in a buffer and in each episode, with probability p, we sample a state from this buffer to be our initial state in this episode. Additionally, instead of random goal-vector sampling we randomly select an atomic program p i , then given the initial state we compute the goal vector using the goal-setter. We study the impact of the reset probability p as well as the usefulness of the second phase in Figure 9.

Mean scores
After first phase After second phase Figure 9: Left We compare the goal-conditioned policy's performance on executing atomic programs STACK and MOVETOZONE as well as two multi-step sequential atomic program executions after the completion of second phase with different probabilities p. Right We compare the performance of goal-conditioned policy in the first phase compared to the second phase. While the agent achieves good performance on atomic programs, the second phase is required to be able to sequence them (as observed in performance on multi-step tasks). Also, the reset probability can affect performance on multi-step tasks. We observe that p = 0.5 gives the better trade-off between the asymptotic training performance and the agent ability to execute programs sequentially.

E.2 Results of self-behavioural model training
We represent the self-behavioural model Ω w with a 2 layer MLP that takes as input the initial environment state and the atomic program and predicts the environment state after T = 50 steps. Learning this model enables us to imagine the state of the environment following an atomic program execution and hence to avoid any further calls to atomic programs that would each have to perform many actions in the environment.
To train the model, we play N episodes with goal-conditioned policy in the environment on uniformly sampled atomic programs and record initial and final environment states in a dataset. Then, we train the model to minimize its prediction error, computed as a mean square error over this dataset. We study the impact of N in Figure 10.

E.3 Curriculum learning comparisons
We compare training the meta-controller with random program sampling compared to an automated curriculum using a learning progress signal detailed in section B.3. We observe in Figure 11 that Mean scores N=10K N=50K N=100K Figure 10: To train the self-behavioural model Ω w , we construct a dataset. We record initial and final states for N episodes of goal-conditioned policy's behaviour after training. At the beginning of each episode, an atomic program p i is randomly chosen. In this figure, we study the impact of the number of episodes N .
both random and automated curriculum gives rise to a natural hierarchy for programs. We observe that the MOVEALLTOZONE and STACKALLTOZONE are learned first. The traces generated by AlphaNPI-X after training confirms that these programs are used to execute the more complex programs CLEANANDSTACK and CLEANTABLE. Given the results shown in Figure 11 we cannot conclude that the learning progress based curriculum outperforms random sampling.  Figure 11: We represent the evolution of AlphaNPI-X performance during training and compare two curriculum strategies. Solid lines correspond to an agent trained with randomly sampled programs while dotted lines correspond to the programs selected according to a learning progress based automatic curriculum.

E.4 Sample efficiency
We compare our method's sample efficiency with other works on the Fetch environment. For training the goal-conditioned policy, 28 DDPG actors sample 100 episodes per epoch in parallel. Thus, 2800 episodes are sampled per epoch. In total, we train the agent for 250 epochs resulting in 7e 5 episodes.
To train the self-behavioural model, we show that sampling 5e 4 episodes is enough to perform well. Thus, in total we only use 7.5e 5 episodes to master all tasks. Note that training the meta-controller does not require any interaction with the environment. In comparison, in the HER original paper [3], each task alone requires around 1.6e 5 episodes to be mastered. In CURIOUS [9], training the