Sparse Skill Coding: Learning Behavioral Hierarchies with Sparse Codes
Authors: Sophia Sanborn
Michael Chang
Sergey Levine
Thomas Griffiths
Venue:  (2020)
Keywords: hierarchical reinforcement learning
unsupervised learning
compression

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.

Under review as a conference paper at ICLR 2020
SPARSE SKILL CODING: LEARNING BEHAVIORAL HIERARCHIES WITH SPARSE CODES
Anonymous authors Paper under double-blind review
ABSTRACT
Many approaches to hierarchical reinforcement learning aim to identify sub-goat structure in tasks. We consider an alternative perspective based on identifying behavioral -repetee action sequences that can be compressed to yield a compact code of action trajectories. We present method for iteratively com- pressing action trajectories to learn nested behavioral hicrarchies of arbitrary depth, with actions of arbitrary length. The learned temporally extended actions provide action primitives that can participate in deeper hierarchies the agent learns. We demonstrate the relevance of this approach for tasks with non-trivial hierar- chical structure and show that the approach can be used to accelerate learning in recursively more complex tasks through transfer.
INTRODUCTION
Despite the many successes of deep reinforcement learning (RL) in recent years (Mnih et al. 2015 Schulman et al. 2017 Silver al. 2016; Levine 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 hand- designed using domain knowledge can provide substantial training benefits (Sutton et al., [999] Barto & Mahadevan 2003). However, 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 facili- tating 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-constrainee Energy limited, computation expensive, and solutions to problems must be computed in real-time. Across cortical areas, a common strategy for dealing with these constraints to reduce computational complexity by storing representations that efficiently encode the statistics of the domain. This idea originated as the efficient coding hypothe- sis (Barlow] [961), and has been empirically corroborated in sensory and motor systems (Barlow)
1961 Olshausen & Field 1996. Hromádka et al. 2008 Poo & Isaacson 2000
2009 Vinje & Gallant
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 task distribution. This is a novel formulation of the classic notion of "chunking" from cognitive psychology (Chase & Simon 1973; Simon 199I). which motivated early work on hierarchical reinforcement learning (Korf) 1985 (Stole & 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 efficiint code for a sequence of actions compresses the sequence into 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 provides the building blocks for solving related problems using 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 consequence, this approach subsumes several distinct

---

Under review as a conference paper at ICLR 2020
objectives for hierarchy learning proposed in the literature; efficient code of behavior required by 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 minimum-length program that can generate the data-that is, finding program with minimum Kolmogorov complexity (Kolmogoroy 1965). The Kolmogorov complexity be approximated. Drawing inspiration from this idea, we propose relatively simple approach for approximating
sequence not finitely computable and can thus only
codes of sequences of actions through iterative convolutional sparse coding and compression, with structure similar to classic string compression methods such as the Nevill- devill-Manning algorithm (Nevill-Manning 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.
sunimum-description-leen
Witten 1997). With this method,
2 PRELIMINARIES
Reinforcement learning: We consider a task as finite horizon Markov decision process, consisting of set of states S, a set of actions A, transition function p (S S' 8, A, a) that defines how actions move an agent between states, and reward function r (S: = A, = a, St+1 8t+1) that defines the reward the agent receives by taking action a in state s and ending up in state 8141- The objective is to find the policy π SS- A the expected cumulative reward
E
Σ r (S, = s, a, S,41
)4t1)
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 linear combination of filters W with coefficients s plus additive Gaussian noise E:
Sparse coding: Sparse coding (Olshausen & Field 1996
23 Σ Wyst +e 5=1
(I)
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:
112
22
min 10.5
Σ
||=
Σ EW,s
+ +A Σ ||s,slla
with the 11 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
Σ j=1
W
*
+
Σ ||5 1
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 AM E M is that which can describe data sample completely using the fewest number of bits,
2

---

Under review as a conference paper at ICLR 2020
M = arg min M(x, M)
MEM
where Lax, .M) is the codelength assignment function defining the theoretical code length required to describe (a, M) uniquely. Underlying the MDL is the idea that a model that is able to (losslessly) compress data must do by capturing its structure and regularities. We use sparse coding to approximate this objective.
3 SPARSE SKILL CODING
We propose method, sparse skill coding (SSC), for discovering hierarchically nested codes for action sequences using a variant of convolutional sparse coding. Given trajectory E Z' consisting of timesteps of discrete actions, wish to find minimal set of multi-step actions that encodes this trajectory. We represent trajectories as binary matrices 7 E [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) advance. We propose an alternative method that can discover potentially perrachhccallynnsteer 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 The dictionary element which has the highest explained variance is then selected and assigned integer code n + 1. The dimension of the matrix T' is increased to mm+1xx, All 2-step time windows that yielded an active coefficient on this dictionary element are then replaced with 1-step one hot vector encoding the dictionary element's s integer code n + 1. The length of the trajectory is thus decreased by the number occurrences of that dictionary element repeated for the new matrix 7-+1xt-w for iterations. this manner, dictionary elements can be discovered that contain previously compressed sequences.
We denote this compression procedure with the function [TT, a). This process
Algorithm 1:
Sparse Skill Coding
Input: Batch of trajectories encoded binary matrices T [0. Output: Dictionary K high-level actions Dr
for k = 1 to K do
min,,s Em ||T EE=
W3 + +xE [1885
S. arg max E
De = W
T₁ = [TT, D2)
endfor
return DK
The result of this process is a set of (potentially nested) high-level actions that capture the statistical structure 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.
RELATED WORK
Early work in hierarchical reinforcement learning demonstrated that well-designed sab-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 (200)). 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 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.

---

Under review as a conference paper at ICLR 2020
2017 Eysenbach et al.; 2018 Gregor et al. 2016; Achiam al. 2018), or by finding bottlenecks 2018 Co-Reyes et al. 2018), after which these temporally extended actions combined with high-level policy to learn on downstream tasks.
in demonstrations (Kipf et al.
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 [998) could learn nested behavior, in practice because the number of contexts grows exponentally 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., (016), 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.
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 behav- ioral motifs than hierarchical RI. methods that learn to identify sub-goals?
Can an agent transfer these temporally extended actions to learn more quickly on 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 build nested hierarchy, and such 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 Sec- tion 1.1.1 and the classic four rooms domain. We compare with an option-critic baseline (Bacon ct al. 2011 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 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 M is adapted from a game developed to teach children how to program. For each level in the game, there exists compact, hierarchical program that generates the solution. In the original game, the objective is to find the shortest program that solves the level. Whereas Sanbomn al. 2018) used the Lightbot domain 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 all of the lights
4

---

Under review as a conference paper at ICLR 2020
(blue tiles) using five basic actions: walk, jump, right, left, and light (which turns the light). This domain presents a challenging sparse reward task: the agent receives a positive reward of only if 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.) (017) in the Lightbot and Four Rooms domain. In environments with nested hierarchical structure, such as Lightbot domain, compressible sequential structure emerges in the agent's s action sequences. This structure can be compactly encoded with a short, hierarchical code. 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 compressed with run-length encoding scheme, but lack the nested structure that requires hierarchical compression schemes.
ICDO
Egpinstte
100
200
Timesteps
ndi
Action trajectory
Compresse action trajectory
Figure 2: Hierarchical structure the trajectories of a PPO agent in the Lighthot domain.
Exiioote
100
T
Timodeps
Ub
Bove
Lab
Nith
Action trajectory
Figure 3: Convergence action trajectories in the four rooms domain. Converged trajectories do not contain the hierarchically nested structure present in the Lightbot domain.
5.1.3 RESULTS
An expert policy was obtained with PPO on the Lightbot puzzle in Figure under a shaped reward structure. where +10 reward received for every light turned on, and -I 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 maximum episode length of 100 timesteps. batch of
5

---

Under review as a conference paper at ICLR 2020
1,000 trajectories generated from the converged policy and encoded with sparse skill coding for 8 iterations, yielding a set nested hierarchical actions. The action space of a new agent was augmented with these 8 actions and its policy trained 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-critie.
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 highly redundant and fail capture the nested structure inherent in the task. Sparse skill coding learns separable skills that reflect the structure of the environment.
Game Map
optioo
option
option
option
skill O
skill
skill
skill
option
option
skill
skill
co
Option-Critic
Sparse Skill Coding
Figure 4: Normalized cumulative terminations per state for options learned via option-critie (left) and skills learned via sparse skill coding (right).
5.2 EXPERIMENT LEARNING SKILLS CONTINUAL TRANSFER
motivation for learning high-level cmmporally-extendde 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 primitives for building even higher-level motifs for even more complex domains. The decision to add high- level 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.
are interested understanding the implications that the iterative encapsulation of higher and higher-level actions have as the agent faces 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 has encountered.
In the quantitative results that follow, not as interested in the asymptotic performance of SSC compared to standard approaches for continual transfer much as we are in the speed at which SSC adapts as well the compositional structure of the trajectories that SSC learns.
5.2. TASKS
We consider two domains, the Tower of Hanoi puzzle (Figure and Fractal Lightbot (Figure
These domains are organized into two levels each as follows:
Level
Tower of Hanoi
Fractal Lighthot
2 disks
I cross
3 disks
crosses

---

Under review as a conference paper at ICLR 2020
For level 1, we initialize SSC agent with weights from PPO agent trained on level 0 and with an augmented action space created from encoding trajectories from the PPO agent trained on level O. We also compare with PPO and option-critic agents that were (1) trained from scratch and (2) transferred from the previous level O)
The Tower of Hanoi is 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 another by moving each disk one a time, with the restriction that the player cannot place larger disk on top of smaller one. One of the notable properties of this task is fractal resembling the Sierpinski triangle. Due to cyclic nature,
Tower of Hanoi:
that the graph of its state space the optimal solution to the task is recursive algorithm, which requires 2 moves. We note that recursive structure of this tasks can be exploited by an agent transferring learning across tasks of increasing complexity, as the solutions to the n step problem are contained within the solutions to the n++ step problem.
We model each Tower of Hanoi puzzle sparse reward reinforcement learning problem in which from the environment for every action taken and a reward 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.
the agent receives a reward
Tadio Stite
Figure 5: (Left) The Tower of Hanoi. (Right) State space for the three disk problem.
Fractal Lightbot: Fractal Lightbot is an adaptation of the Lightbot puzzles built on top of the Minigrid environment Sndevalier-Boisvedd 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 's observations are 9x9 images showing overhead views of the portion of the environment that is directly in front the agent, which changes as the agent moves around. Unlike the original Lightbot game, we removed the possibility of tiles multiple heights, and the agent able to turn on the light when occluded.
front of rather than on top the light tile so that is not
We also model each Fractal Lightbot puzzle as a sparse reward reinforcement learning problem in which the agent receives reward of 0 from the environment for every action taken and reward of 100 for successfully transferring the tower of disks. addition, the agent incurs a cognitive cost of -1 for every action taken. On each episode, the agent is initialized in random location and direction.
Figure Lighthot puzzles that grow in a fractal manner. left: level 0, right: level 1

---

Under review as a conference paper at ICLR 2020
Figure 7: Transfer learning in the Tower of Hanoi. Each line averages over different random seeds. Error bars show 95% confidence intervals.
Figure 8: Transfer learning in Fractal Lightbot. Each line averages over 3 different random seeds. Error bars show 95% confidence intervals.
5.2.2 RESULTS
Figure 7 compares SSC with our baselines on transferring from level 0 (2 disks) to level (3 disks) for Tower of Hanoi, and
SSC with our baselines transferring from level 0 (1 cross) to level (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.
DISCUSSION
Our 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.
REFERENCES
Joshua Achiam. Harrison Edwards, Dario Amodei, and Pieter Abbeel. Variational option discovery algorithms. arXiv preprint arXiv: 1807. 10299, 2018.
8

---

Under review as a conference paper at ICLR 2020
John Robert Anderson. The adaptive character of thought. Psychology Press, 1990.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Association for the Advancement of Artificial Intelligence, pp. 1726-1734, 2017.
Horace Barlow. Possible principles underlying the transformations of sensory messages. Rosenblith W (ed.), Sensory Communication, chapter 13, pp. 217-234. MIT press, 1961.
Andrew G Barto and Sridhar Mahadevan. Recent advances in hierarchical reinforcement learning. Discrete Event Dynamic Systems, 13(4):341-379, 2003.
William G Chase and Herbert A Simon. Perception chess. Cognitive psychology, 4(1):55-81) 81, 1973.
Maxime Chevalier-Boisvery Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. hittps://githii thu... scom/max mwcb/ haw.eb/yymmmmngggiii. 2018.
John Co-Reyes, YuXuan Liu, Abhishek Gupta, Benjamin Eysenbach, Pieter Abbeel, and Sergey Levine. Self-consistent trajectory autoencoder: Hierarchical reinforcement learning with trajectory embeddings. arXiv preprint urXiv::8000 02813, 2018.
Thomas M Cover and Joy Thomas. Elements of information theory. John Wiley & Sons, 2012.
Peter Dayan and Geoffrey Hinton. Feudal reinforcement learning. In Advances in neural information processing systems, pp. 271-278, 1993.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint arXhv:1802.06076 2018
Tamar Flash and Binyamin Hochner. Motor primitives in vertebrates and invertebrates. Current opinion in neurobiology, 15(6):660-666 2005.
Carlos Florensa, Yan Duan, and Pieter Abbeel. Stochastic neural networks for hierarchical reinforce- ment learning. arXiv preprint vrXiv:1704.03012 2017.
Roy Fox, Sanjay Krishnan, Ion Stoica, and Ken Goldberg. Multi-level discovery of deep options. arXiv preprint 1XXXv:/703.08220 2017.
Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta learning shared hierarchies. arXiv preprint arXiv:1710.09667, 2017.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint 1:Xiv:661.007500 2016.
Jean Harb, Pierre-Luc Bacon, Martin Klissarov, and Doina Precup. When waiting is not an option: Learning options with deliberation cost. arXiv preprint arXiv:1709.04577 2017.
Tomáš Hromádka, Michael R DeWeese, and Anthony M Zador. Sparse representation of sounds in the unanesthetized auditory cortex. PLoS biology, 6(1):e16, 2008.
Thomas Kipf, Yujia Li, Hanjun Dai, Vinicius Zambaldi, Edward Grefenstette, Pushmeet Kohli, and Peter Battaglia. Compositional imitation learning: Explaining and executing task at time. arXiv preprint arXiv: 18/2.0/482 2018.
Andrei N Kolmogorov. Three approaches to the quantitative definition ofinformation'. Problems of information transmission, 1()):177, 1965.
George Konidaris and Andrew G Barto. Building portable options: Skill transfer in reinforcement
learning. In International Joint Conference on Artificial Intelligence, volume 7, pp. 895-9999999 900, 2007.
Richard Korf. Macro-operators: weak method for learning. Artificial intelligence, 26(1):35-77, 1985.
Tejas D Kulkarni, Karthik Narasimhan, Ardavan Sacedi, and Josh Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In Advances in neural information processing systems, pp. 3675-3683, 2016.

---

Under review as a conference paper at ICLR 2020
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):133--1373, 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In Advances Neural Information Processing Systems, pp. 3303-3313, 2018.
Craig G Devill-Manning and lan H Witten. Identifying hierarchical structure in sequences: A linear-time algorithm. Journal of Artificial Intelligence Research, 7:67-82, 1997.
Bruno A Olshausen and David J Field. Emergence of simple-cell receptive field properties by learning sparse code for natural images. Nature, 381 (6583))6 1996.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. arXiv preprint arXiv: (0.611.1100 1.01855, 2016.
Ronald Parr and Stuart Russell. Reinforcement learning with hierarchies of machines. In Advances in neural information processing systems, pp. 1043-1049, 1998.
Cindy Poo and Jeffiy S Isaacson. Odor representations in olfactory cortex:sparse coding, global inhibition, and oscillations. Neuron, 62(6))850-861, 2009.
Sophia Sanborn, David Bourgin, Michael Chang, and Thomas Griffiths. Representational efficiency outweighs action efficiency in human program induction. In Proceedings of the Annual Meeting of the Cognitive Science Society, 2018.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.064777 2017.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwwesser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and search. nature, 529(7587):484, 2016.
Herbert A Simon. The architecture of complexity. In Facets of systems science, pp. 457-476. Springer, 1991.
Richard Socher, Cliff C Lin, Chris Manning, and Andrew Y Ng. Parsing natural scenes and natural language with recursive neural networks. In Proceedings of the 28th international conference on machine learning (ICMI.//)), /), pp. 129-136, 2011.
Alec Solway, Carlos Diuk, Natalia Córdova, Debbie Yee, Andrew G Barto, Yael Niv, and Matthew M Botvinick. Optimal behavioral hierarchy. PLoS computational biology, 1003)e,, 2014.
Martin Stolle and Doina Precup. Learning options reinforcement learning. International Symposium abstraction. reformulation, and approximation, pp. 212-223 Springer, 2002.
Richard S Sutton, Doina Precup. and Satinder Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2)1811-11,, 1999.
Chen Tessler, Shahar Givony, Tom Zahavy, Daniel J Mankowitz, and Shie Mannor. A deep hierar- chical approach to lifelong learning in minecraft. In Thirty-First AAAI Conference Artificial Intelligence, 2017.
William Vinje and Jack L Gallant. Sparse coding and decorrelation in primary visual cortex during natural vision. Science, 28735466 2000.
10

---

Under review as a conference paper at ICLR 2020
A DETAILS FOR EXPERIMENT 2
A.1 AGENT DETAILS
Observations for an m-disk, 3-peg Hanoi task are represented with m vectors encoding the location of each disk. Each action is parameterized as source.per -eee,,,e,,.. target-pp -ee which automatically moves the topmost disk on the source.per on top of the topmost disk of the target.peg Observations are encoded with a 3-layer fully-connected network with a hidden dimension of 256 units and ReLU activations at each layer. The last layer produces the action distribution.
Tower of Hanoi:
Fractal Lighthot: Observations for the Fractal Lightbot task are encoded with a 3-layer CNN with hidden dimensions of 16, 32, and 64 to encode the image observations, with kernels of size (2, 2), stride of 1, and fully-connected output layers of 256 dimensions, with ReLU activations at every layer. The last layer produces the action distribution.
A.2 TRAINING DETAILS
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 We compare with the following baselines:
A PPO agent trained on level from scratch.
A PPO agent trained on level with weights initialized from training a PPO agent on level
0.
An option-critie agent trained on level from scratch.
An option-critic agent trained on level with weights initialized from training an option- critic agent on level O.
SSC is trained using PPO. Because the environments are all sparse reward environments, we collect the minimum amount of whole episodes whose aggregate number transitions is greater than or equal 4096 before doing every gradient update. For PPO decay penalty le-5. Option critic was initialized with 4 options.
clip ratio of 0.1 and weight
The hyperparameters for each agent to converge were found using informal search:
For Fractal Lightbot, we used a learning rate decay of 0.99 every 100 updates. For Tower of Hanoi, we used learning rate decay of 0.95 every 100 updates.
We did not transitions. For training PPO and option critic from scratch on level I in Fractal Lightbot, we trained for 3,000,000 transitions because this the amount needed for the agents to converge.
fixed horizon for the episodes and trained all models for 1,000,000
When transferring from level 0 to level 1, we found that initializing the agents from the last checkpoint from level had a difficult time exploring the new level because (1) the environ- ment has sparse rewards and (2) the weights were optimized for level 0 only. Therefore, we initialize all agents from a checkpoint saved one-third the way through training before the return curve plateaus. For every task this point occurred after the agent has trained on about 4000 episodes, so used the checkpoint 4000 episodes as a standard.
11


Reviews:
[{"review_id": "rye7qxJAKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper discusses identifying motifs for aiding in the solving of cognitive tasks when using Reinforcement Learning. The idea seems quite novel, but the presentation seems to be more complicated than it needs to be for the idea. For example the introduction is quite hard to parse and when you get down to it, the ideas don’t seem that complex.\n\nThe discussion of the technique seems to be lacking in detail. I would be hard-pushed to reproduce the work from the material presented.\n\nFigure 2 is complex and lacks enough discussion in the text.\n\nFigure 3 is likewise complex and is not mentioned at all in the text.\n\nFigure 4 needs more discussion.\n\nThe results presented are quite minimal and don’t fully explore and evaluate the approach taken.\n\nSpecific issues:\n- Page 2: broken citation: “state space [cite], “\n\n- “Lightbot: The Lightbot domain … a positive reward of only if it successfully turns off all lights.” - this seems to be the opposite of all previous statements which talked about Turing lights on.\n\n- “We also model each Fractal Lightbot puzzle … and a reward of 100 for successfully transferring the tower of disks.” - this sounds more like the reward for the tower.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlAblT6YB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe 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.\n\nIn 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.  \n\nBut 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.\n\nIn 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. \n\nSummary: A good idea, but not well described, with strong assumptions not discussed, and with low-quality experimental results. \n\nSome other minor remarks:\nThe 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. \n\nEquation 2 versus Equation 3: What is the difference?\ns 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. \nArticulation between sparse coding and MDL not clear (since sparse coding is directly a way to minimize the MDL). MDL never used after that.\nsection 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 ?\n[cite] appears in the introduction\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HklhbwPTYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to propose a new way of discovering a specific type of temporal abstraction, the pattern of actions. To achieve this goal, it applies the sparse coding method to discover an efficient encoding of the action sequences generated by the agent's interaction with the environment. The filters/dictionaries discovered by the method then represent certain patterns of actions.\n\nIn general, I think it proposes an interesting view of the temporal abstraction. Although this kind of temporal abstraction is only valid in the certain types of environment (For example, as it only represents certain patterns of action sequence, it suffers from non-optimality in stochastic environment where no fixed action sequence would be optimal for solving the problem), the paper, especially the experiment part, clearly tells its readers in what situation can we expect it to perform well. In this sense, I think it provides some scientific insights that benefit my understanding.\n\nHowever, there are many places in the paper making me confused. Therefore I can not fully understand the paper and can not accept it. My concerns are:\n\n1. Equations 1, 2, and 3 are loosey-goosey. For example, there is no definition of x_i, is it a vector or a scalar? Similarly, there is no definition of W and s.\n2. paragraph 3 in section 3 is extremely hard to understand. For example, the first sentence: \"At all stages, the size of the dictionary elements is set to 2-timesteps\". Where does the \"2-timesteps\" come? I have no idea what it is talking about.\n3. in the algorithm, T_i is not defined.\n4. in the experiment part, figure 4 only provides the termination of options/skills but doesn't provide corresponding policies/action sequence, which makes me hard to evaluate the result.\n5. figure 7 and 8 seems to be contradicted with the paper's claim. And the author didn't give a reasonable explanation.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an interesting idea of identifying repeated action sequences, or behavioral motifs, in the context of hierarchical reinforcement learning, using sparsity/compression.  While this is a fresh and useful idea, it appears that the paper requires more work, both in terms of presentation/clarity and in terms of stronger empirical results.

Decision: Reject