Title: SPARSE SKILL CODING: LEARNING BEHAVIORAL HIERARCHIES WITH SPARSE CODES

Abstract: Many approaches to hierarchical reinforcement learning aim to identify sub-goal structure in tasks. We consider an alternative perspective based on identifying behavioral 'motifs'-repeated action sequences that can be compressed to yield a compact code of action trajectories. We present a method for iteratively compressing action trajectories to learn nested behavioral hierarchies of arbitrary depth, with actions of arbitrary length. The learned temporally extended actions provide new action primitives that can participate in deeper hierarchies as the agent learns. We demonstrate the relevance of this approach for tasks with non-trivial hierarchical structure and show that the approach can be used to accelerate learning in recursively more complex tasks through transfer.

1. INTRODUCTION:

Despite the many successes of deep reinforcement learning (RL) in recent years (Mnih et al., 2015; Schulman et al., 2017; Silver et al., 2016; Levine et al., 2016) , long-term credit assignment and search complexity remain fundamental challenges. One of the primary strategies for managing this complexity has been to incorporate hierarchical, temporally-extended actions. Hierarchies handdesigned using domain knowledge can provide substantial training benefits (Sutton et al., 1999; Barto & Mahadevan, 2003) . However, a major challenge in hierarchical reinforcement learning is to develop general methods for discovering useful hierarchical representations without relying on domain expertise.

Many objectives for the hierarchy learning problem have been proposed, with notable focus on facilitating transfer to downstream tasks and facilitating efficient exploration of the state space (Eysenbach et al., 2018; Frans et al., 2017; Solway et al., 2014) . We pose the hierarchy learning problem as follows: given a distribution of tasks, what determines the optimal set of representations for action sequences? We approach this question by considering the problem faced by human decision-makers. Humans are fundamentally resource-constrained. Energy is limited, computation is expensive, and solutions to problems must be computed in real-time. Across cortical areas, a common strategy for dealing with these constraints is to reduce computational complexity by storing representations that efficiently encode the statistics of the domain. This idea originated as the efficient coding hypothesis (Barlow, 1961) , and has been empirically corroborated in sensory and motor systems (Barlow, 1961; Olshausen & Field, 1996; Hromádka et al., 2008; Poo & Isaacson, 2009; Vinje & Gallant, 2000) .

We extend the efficient coding hypothesis to the problem of representation learning for planning, and propose a method for discovering temporally extended actions by learning an efficient code of the behavior required by a task distribution. This is a novel formulation of the classic notion of "chunking" from cognitive psychology (Chase & Simon, 1973; Simon, 1991) , which motivated early work on hierarchical reinforcement learning (Korf, 1985; Stolle & Precup, 2002) , and aligns with empirical neuroscience results suggesting that organisms represent their motor output in terms of a sparse efficient code of high-level "motor primitives" (Flash & Hochner, 2005 ). An efficient code for a sequence of actions compresses the sequence into a minimum-length description that factorizes the input distribution (Cover & Thomas, 2012) . The benefit of using such a code in the context of decision making is that it provides the building blocks for solving related problems using a minimal set of decision points, delineated by a minimal set of skills that capture the statistics of the behavior required by the task distribution. As a consequence, this approach subsumes several distinct objectives for hierarchy learning proposed in the literature; an efficient code of behavior required by a problem space reduces the number of decision points required (Harb et al., 2017) , facilitates transfer to tasks drawn from the same distribution (Solway et al., 2014) , facilitates efficient exploration of the state space [cite], and decomposes a task into a natural set of sub-tasks (Bacon et al., 2017; Fox et al., 2017) .

The problem of finding a compact code for sequential data with long-range dependencies and nested hierarchical structure is equivalent to the problem of finding a minimum-length program that can generate the data-that is, finding a program with minimum Kolmogorov complexity (Kolmogorov, 1965) . The Kolmogorov complexity of a sequence is not finitely computable and can thus only be approximated. Drawing inspiration from this idea, we propose a relatively simple approach for approximating minimum-description-length codes of sequences of actions through iterative convolutional sparse coding and compression, with structure similar to classic string compression methods such as the Nevill-Manning algorithm (Nevill-Manning & Witten, 1997) . With this method, we are able to extract compact, hierarchically nested representations of action trajectories, with temporally extended actions of arbitrary lengths. We incorporate this method into the RL problem by equipping the agent with the capacity to compress its behavior and augment its action space with the learned representations after each task it faces.

2. PRELIMINARIES:

Reinforcement learning: We consider a task as a finite horizon Markov decision process, consisting of a set of states S, a set of actions A, a transition function p (S t+1 = s |S t = s, A t = a) that defines how actions move an agent between states, and a reward function r (S t = s, A t = a, S t+1 = s t+1 ) that defines the reward the agent receives by taking action a in state s and ending up in state s t+1 . The objective is to find the policy π : S → A the expected cumulative reward

E π T t=1 r (S t = s, A t = a, S t+1 = s t+1 ) .

Sparse coding: Sparse coding (Olshausen & Field, 1996) is an unsupervised algorithm for learning a dictionary that reconstructs a signal using a minimal set of non-zero coefficients on the dictionary. The sparse coding model assumes that a signal X is generated as a linear combination of filters W with coefficients s plus additive Gaussian noise :

EQUATION

The objective is to reconstruct the input with minimal distortion while using the minimal number of non-zero coefficients. The filters and coefficients are jointly optimized:

min w,s m i=1 ||x i - n j=1 W j s i,j || 2 2 + λ i,j ||s i,j || 1 (2)

with the l1 norm imposing a penalty on the number on non-zero activations, and λ modulating the trade-off between the accuracy and sparsity of the representations. To learn sparse codes for time series data, one can augment the basic sparse coding model by replacing scalar-valued coefficients with vector-valued coefficients and matrix multiplication by convolution, which allows basis functions to appear at all possible shifts in the signal:

min w,s m i=1 ||x i - n j=1 W j * s i,j || 2 2 + λ i,j ||s i,j || 1 (3)

We use this convolutional formulation of the sparse coding model to encode trajectories of actions generated by an RL agent. We note the similarity between the sparsity constraint and the Minimum Description Length (MDL) principle, which states that the best model M ∈ M is that which can describe a data sample x completely using the fewest number of bits,

M = arg min M ∈ M L(x, M )

where L(x, M ) is the codelength assignment function defining the theoretical code length required to describe (x, M ) uniquely. Underlying the MDL is the idea that a model that is able to (losslessly) compress data must do so by capturing its structure and regularities. We use sparse coding to approximate this objective.

3. SPARSE SKILL CODING:

We propose a method, sparse skill coding (SSC), for discovering hierarchically nested codes for action sequences using a variant of convolutional sparse coding. Given a trajectory τ ∈ Z t consisting of t timesteps of n discrete actions, we wish to find a minimal set of multi-step actions that encodes this trajectory. We represent trajectories as binary matrices T n×t ∈ [0, 1], where actions are one-hot encoded.

The standard sparse coding model learns a single layer code and requires fixing the size of the dictionary elements (the length of the actions) in advance. We propose an alternative method that can discover potentially hierarchically-nested dictionary elements of arbitrary length with an iterative coding and compression process.

At all stages, the size of the dictionary elements is set to 2-timesteps. A dictionary and sparse code is found for the batch of trajectories, by minimizing equation 2. The dictionary element a which has the highest explained variance is then selected and assigned an integer code n + 1. The dimension of the matrix T is increased to T n+1×t . All 2-step time windows that yielded an active coefficient on this dictionary element are then replaced with a 1-step one hot vector encoding the dictionary element's integer code n + 1. The length of the trajectory is thus decreased by the number of occurrences of that dictionary element w. We denote this compression procedure with the function Γ(T, a). This process is repeated for the new matrix T n+1×t-w , for k iterations. In this manner, dictionary elements can be discovered that contain previously compressed sequences.

Algorithm 1: Sparse Skill Coding Input: Batch of m trajectories encoded as binary matrices

T n×t ∈ [0, 1] Output: Dictionary of K high-level actions D K for k = 1 to K do min w,s m i=1 ||T i - n j=1 W j * s i,j || 2 2 + λ i,j ||s i,j || 1 s ω = arg max m i s D k = W ω T k = Γ(T, D k ) endfor return D K

The result of this process is a set of (potentially nested) high-level actions that capture the statistical structure of trajectories generated on a task. An agent's action space can then be augmented to include these high-level actions, which can facilitate transfer to tasks drawn from the same distribution.

4. RELATED WORK:

Early work in hierarchical reinforcement learning demonstrated that well-designed sub-goals or high-level actions can significantly speed the discovery of shortest-path solutions (Sutton et al., 1999; Barto & Mahadevan, 2003; Dayan & Hinton, 1993) and facilitate transfer to related tasks (Konidaris & Barto, 2007) . Later work demonstrated the advantages of incorporating pre-defined sub-goals into deep reinforcement learning (Kulkarni et al., 2016) or pre-learned skills (Tessler et al., 2017) , but left open the question of how to discover these sub-goals or skills automatically.

Recent work have attempted to discover these temporally extended actions by optimizing for reusable behaviors shared across tasks (Frans et al., 2017) , maximizing diversity in exploration (Florensa et al., 2017; Eysenbach et al., 2018; Gregor et al., 2016; Achiam et al., 2018) , or by finding bottlenecks in demonstrations (Kipf et al., 2018; Co-Reyes et al., 2018) , after which these temporally extended actions are combined with a high-level policy to learn on downstream tasks. However, in contexts in which bottleneck states are less apparent, approaches for end-to-end learning of temporally extended actions and policies, such as options (Bacon et al., 2017; Harb et al., 2017) frequently degenerate to learning either single-step options or only a single option for the entire trajectory. On the other hand, approaches that mitigate this degeneracy by fixing the horizon length of each sub-policy (Nachum et al., 2018; Frans et al., 2017) . Furthermore, while in theory methods such as options (Sutton et al., 1999) or hierarchies of abstract machines (Parr & Russell, 1998 ) could learn nested behavior, in practice because the number of contexts grows exponentially with depth, most approaches focus on learning two-level hierarchies, with the exception of (Fox et al., 2017) which proposes a method for learning deeper nested hierarchies, but with a fixed number of options available at each depth.

Nested structure is characteristic of problems in natural language processing (Socher et al., 2011) or program induction (Parisotto et al., 2016) , but approaches in these fields usually have access to additional top-down supervision on tree structure. Our method discovers variable-length temporally extended actions in a bottom-up fashion from demonstration , and we show that our method is able to nest temporally extended actions and transfer to recursively structured environments where bottlenecks are not that clearly apparent.

5. EXPERIMENTS AND RESULTS:

In our experiments, we ask the following questions:

• Can sparse skill coding learn temporally extended actions that reflect the nested hierarchy of a task? • Do the temporally extended actions learned from sparse skill coding better capture behavioral motifs than hierarchical RL methods that learn to identify sub-goals? • Can an agent transfer these temporally extended actions to learn more quickly on a series of recursively more complex environments?

We find that in contrast to those learned in subgoal-based hierarchical approaches, the temporally extended actions learned from sparse skill coding reflect commonly repeated patterns of behavior that can be used to build a nested hierarchy, and such a nested hierarchy enables the agent to continually transfer to recursively more complex environments.

To evaluate our approach, we consider the Lightbot domain (explained in further detail in Section 5.1.1) and the classic four rooms domain. We compare with an option-critic baseline (Bacon et al., 2017) trained with proximal policy optimization (Schulman et al., 2017) .

5.1. EXPERIMENT 1: LEARNING SPARSE SKILLS FROM DEMONSTRATION:

To understand the properties of representations learned with this method, we first present a qualitative analysis of the representations learned by sparse skill coding performed on trajectories generated by an expert policy, and contrast these learned representations with those learned via option-critic (Bacon et al., 2017) on the same task.

5.1.1. TASKS:

We compare the abstractions learned by sparse skill coding and option-critic on a task that highlights the relevance of identifying behavioral "motifs" over subgoal states.

Lightbot: The Lightbot domain (Figure 1 ) is adapted from a game developed to teach children how to program. For each level in the game, there exists a compact, hierarchical program that generates the solution. In the original game, the objective is to find the shortest program that solves the level. Whereas Sanborn et al. (2018) used the Lightbot domain to study hierarchical learning in humans, we adapt the Lightbot game as a novel domain for hierarchical RL methods: the agent begins in a random location and direction in the room and must navigate the room to turn on all of the lights (blue tiles) using five basic actions: walk, jump, right, left, and light (which turns on the light). This domain presents a challenging sparse reward task: the agent receives a positive reward of only if it successfully turns off all lights.

Figure 1 : The Lightbot domain.

5.1.2. SUB-GOALS VS. MOTIFS:

The repeated patterns in the solutions for Lightbot puzzles serve to test whether methods that discover nested hierarchical structure, such as ours, are able to learn re-usable temporally extended-actions that better reflect the structure of the environment than methods that chain together subtrajectories between sub-goals. Figure 2 visualizes the action sequences generated while optimizing a policy with proximal policy optimization (PPO) (Schulman et al., 2017) in the Lightbot and Four Rooms domain.

In environments with nested hierarchical structure, such as the Lightbot domain, compressible sequential structure emerges in the agent's action sequences. This structure can be compactly encoded with a short, hierarchical code. In domains more conducive to sub-goal approaches, such as Four Rooms, behavioral motifs are less apparent; solutions chain together sequences of repeated actions (e.g. [right, right, right], [down, down, down]). Such sequences could be compressed with a run-length encoding scheme, but lack the nested structure that requires hierarchical compression schemes. 

5.1.3. RESULTS:

An expert policy was obtained with PPO on the Lightbot puzzle in Figure 4 under a shaped reward structure, where +10 reward was received for every light turned on, and -1 for every other action.

The policy was trained to convergence with a learning rate of 10 -5 for 10,000 episodes, with a gradient update every 100 episodes and a maximum episode length of 100 timesteps. A batch of 1,000 trajectories was generated from the converged policy and encoded with sparse skill coding for 8 iterations, yielding a set of 8 nested hierarchical actions. The action space of a new agent was augmented with these 8 actions and its policy was trained to convergence.

We compare the skills learned with sparse skill coding to options learned with option-critic (Bacon et al., 2017) trained with PPO. The same hyperparameters were used for both algorithms, with the addition of a deliberation cost (Harb et al., 2017) of 0.05 for option-critic.

Figure 4 shows the normalized cumulative terminations per state for each option and skill learned by these two methods in the Lightbot domain. Options learned with option-critic show some specialization, but are highly redundant and fail to capture the nested structure inherent in the task. Sparse skill coding learns separable skills that reflect the structure of the environment.

Figure 4 : Normalized cumulative terminations per state for options learned via option-critic (left) and skills learned via sparse skill coding (right).

5.2. EXPERIMENT 2: LEARNING SKILLS FOR CONTINUAL TRANSFER:

A motivation for learning high-level temporally-extended actions in the first place is that it reduces the cognitive cost of choosing a series of actions to the cognitive cost of choosing only one action. Therefore, the potential benefit of discovering behavioral motifs as high-level actions is that such high-level actions not only could be re-used in various related contexts, but could serve as primitives for building even higher-level motifs for even more complex domains. The decision to add a highlevel action to the agent's repertoire of skills pays upfront the cognitive cost of taking that particular series of primitive actions, such that the agent need not pay such a cost when invoking the high-level action for future learning.

We are interested in understanding the implications that the iterative encapsulation of higher and higher-level actions have as the agent faces a task more complex than tasks it has trained on previously.

Environments that exhibit a recursive or fractal structure, such as the Tower of Hanoi, offer a natural suite of tasks that grow rapidly in complexity from the perspective taking primitive actions, but whose solutions are straightforward if sub-solutions to easier problems may be re-used. Many real-world problems have many nested layers of complexity and such fractal environments boils such nested structure into its purest form, allowing us to take a first step towards understanding how an intelligent agent may re-use primitive sub-solutions to enable learning on more complex versions of problems it has encountered.

In the quantitative results that follow, we are not as interested in the asymptotic performance of SSC compared to standard approaches for continual transfer as much as we are in the speed at which SSC adapts as well as the compositional structure of the trajectories that SSC learns.

We consider two domains, the Tower of Hanoi puzzle (Figure 5 ) and Fractal Lightbot (Figure 6 ).

These domains are organized into two levels each as follows:

Level Tower of Hanoi Fractal Lightbot 0 2 disks 1 cross 1 3 disks 2 crosses

For level 1, we initialize an SSC agent with weights from a PPO agent trained on level 0 and with an augmented action space created from encoding trajectories from the PPO agent trained on level 0. We also compare with PPO and option-critic agents that were (1) trained from scratch and (2) transferred from the previous level 0.

Tower of Hanoi: The Tower of Hanoi is a classic puzzle that has been extensively studied in cognitive psychology and planning (Anderson, 1990) . In the Tower of Hanoi, the player must move a stack of n disks from one peg to another by moving each disk one at a time, with the restriction that the player cannot place a larger disk on top of a smaller one. One of the notable properties of this task is that the graph of its state space is a fractal resembling the Sierpinski triangle. Due to its cyclic nature, the optimal solution to the task is a recursive algorithm, which requires 2 n-1 moves. We note that the recursive structure of this tasks can be exploited by an agent transferring its learning across tasks of increasing complexity, as the solutions to the n step problem are contained within the solutions to the n+1 step problem.

We model each Tower of Hanoi puzzle as a sparse reward reinforcement learning problem in which the agent receives a reward of 0 from the environment for every action taken and a reward of 10 for successfully transferring the tower of disks. In addition, the agent incurs a cognitive cost of -1 for every action taken. On each episode, the tower of disks is initialized on a random peg. Fractal Lightbot: Fractal Lightbot is an adaptation of the Lightbot puzzles built on top of the Minigrid environment (Chevalier-Boisvert et al., 2018) , which permits the use of images as state representations. The dimensions of the observations are fixed as the complexity of the puzzles increases; the agent's observations are 9x9 images showing overhead views of the portion of the environment that is directly in front of the agent, which changes as the agent moves around. Unlike the original Lightbot game, we removed the possibility of tiles at multiple heights, and the agent is able to turn on the light when it is in front of rather than on top of the light tile so that it is not occluded.

We also model each Fractal Lightbot puzzle as a sparse reward reinforcement learning problem in which the agent receives a reward of 0 from the environment for every action taken and a reward of 100 for successfully transferring the tower of disks. In addition, the agent incurs a cognitive cost of -1 for every action taken. On each episode, the agent is initialized in a random location and direction. 

Figure 7 compares SSC with our baselines on transferring from level 0 (2 disks) to level 1 (3 disks) for Tower of Hanoi, and Figure 8 compares SSC with our baselines on transferring from level 0 (1 cross) to level 1 (2 crosses) for Fractal Lightbot. We observe that SSC performs much better than option critic. SSC transfer slightly slower than PPO, possibly because exploring with long high-level actions potentially is more costly.

:

DISCUSSIONOur goal is (1) to understand how to design an algorithm that can discover nested behavioral hierarchies of arbitrary depth, with actions of arbitrary length and (2) understand how reducing the cognitive cost of choosing actions with high-level actions affect transfer. Sparse skill coding is our method for studying these questions. As our method is a bottom-up method for learning nested hierarchies of temporally extended actions, we are able to avoid the computational complexity that make learning nested hierarchies of more than two levels difficult. We have also shown the distinction between hierarchies characterized by subgoals and hierarchies characterized by recurring motifs. We hope this paper motivates future work in learning nested behavioral hierarchies.

Figures and Tables:

Figure 2: Hierarchical structure in the trajectories of a PPO agent in the Lightbot domain.

Figure 3: Convergence of action trajectories in the four rooms domain. Converged trajectories do not contain the hierarchically nested structure present in the Lightbot domain.

Figure 5: (Left) The Tower of Hanoi. (Right) State space for the three disk problem.

Figure 6: Lightbot puzzles that grow in a fractal manner. left: level 0, right: level 1

Figure 8: Transfer learning in Fractal Lightbot. Each line averages over 3 different random seeds. Error bars show 95% confidence intervals.

Peer review (iclr2020):
The paper proposes a method that aims at encoding trajectories (described as a sequence of actions) into a set of discrete codes with a hierarchical structure. The principle of the algorithm (as far as the article allows me to understand) is to apply multiple iterations of classical sparse coding over the trajectories. The experimental section on simple (deterministic) tasks shows that the SSC method is able to extract interesting options, which can then be used to learn faster on some close domains. In terms of positioning, I find the idea of the paper interesting (i.e encoding trajectories through discrete symbols) since it uses sparse coding approaches which, as far as I know, are not classical in the RL domain. This type of approach can give us both a meaningful insight about the *nature* of the learned policy (as it is the case in the paper that compresses expert trajectories), and can also become a manner to constraint an RL algorithm to force it to exhibit behaviors that could seem more natural to humans. But the way it is done in this article is disappointing. First of all, the article is badly written, and I am still not sure to fully understand how the algorithm exactly works. Indeed, many notations are not well defined (see at the end of the review), and it makes the algorithm 1 difficult to catch. Then, the authors consider that trajectories are represented as sequences of actions (using one-hot encoding) and do not discuss this hard choice: representing trajectories as a sequence of actions usually rely on the assumption that both the environment is deterministic, and the initial state is always the same. Is it the case in this paper? If it is, it clearly restricts the applicability of the technique. If it is not, then I don*t see how it could work well... As far as I understand, all experimental environments are deterministic. So the algorithm description would clearly need to be rewritten, and the authors have to discuss the assumptions they are doing mainly: deterministic environments and also the fact that the *options* can only be extracted once a first policy has be learned (or by using expert traces) which limits its applicability. In terms of experiments, the assumption made is that we have access to a set of *good* trajectories (which is easy in the proposed environments, but may be difficult in the real-life). It is compared to the option-critic architecture which simultaneously learns the options and the policy and I think that the comparison is somehow unfair. Since SSC is more a *sequence compression* algorithm, I would prefer to compare with existing sequence compression algorithms like hierarchical recurrent neural networks for instance. The results are illustrated in very simple environments and the article would gain by using more complex ones (for instance the Atari grand challenge dataset could be used for such a study). So it is difficult to understand if the approach as it is is really interesting and efficient for general RL purposes. Summary: A good idea, but not well described, with strong assumptions not discussed, and with low-quality experimental results. Some other minor remarks: The introduction is a little bit messy and does not well allow one to understand the focus on the paper, mixing some notions of neuroscience with classical reinforcement learning aspects, the connection between the two domains being not trivial. Equation 2 versus Equation 3: What is the difference? s notation appears in 2.1 and 2.2 while it corresponds to different things. The variables are not defined and we don*t know in which domain they rely on. Articulation between sparse coding and MDL not clear (since sparse coding is directly a way to minimize the MDL). MDL never used after that. section 3, paragraph 3: I do not understand what is described here. The description has to be rewritten to allow the readers to understand the algorithm e.g *the size of the dictionary elements is set to 2-timesteps. * ? *The dictionary element a which has the highest explained variance is then selected and assigned an integer code n + 1 * Variance on what ? what is T_i ? [cite] appears in the introduction