Option Discovery using Deep Skill Chaining
Authors: Akhil Bagaria
George Konidaris
Venue:  (2020)
Keywords: Hierarchical Reinforcement Learning
Reinforcement Learning
Skill Discovery
Deep Learning
Deep Reinforcement Learning

Abstract: Autonomously discovering temporally extended actions, or skills, is a longstanding goal of hierarchical reinforcement learning. We propose a new algorithm that combines skill chaining with deep neural networks to autonomously discover skills in high-dimensional, continuous domains. The resulting algorithm, deep skill chaining, constructs skills with the property that executing one enables the agent to execute another. We demonstrate that deep skill chaining significantly outperforms both non-hierarchical agents and other state-of-the-art skill discovery techniques in challenging continuous control tasks.

Published as a conference paper at ICLR 2020
OPTION DISCOVERY USING DEEP SKILL CHAINING
Akhil Bagaria
George Konidaris Department of Computer Science
Department of Computer Science
Brown University
Brown University Providence, RI, USA
Providence, RI, USA akhil waw.laagarii@bbooo... edu
gdk falkkbbown.co edu
ABSTRACT
Autonomously discovering temporally extended actions, or skills, is longstand- ing goal of hierarchical reinforcement learning. We propose new algorithm that combines skill chaining with deep neural networks to autonomously discover skills in high-dimensional, continuous domains. The resulting algorithm, deep skill chaining, constructs skills with the property that executing one enables the agent execute another. We demonstrate that deep skill chaining significantly outperforms both non-hierarchical agents and other state-of-the-ane skill discov- ery techniques in challenging continuous control tasks
INTRODUCTION
Hierarchical reinforcement learning (Barto & Mahadevan 2003) is a promising approach for solving long-horizon sequential decision making problems. Hierarchical methods lower the decision mak- ing burden on the agent through the use of problem specific action abstractions (Konidaris) 2019). While the use of temporally extended actions, or options (Sutton et al.] 1999), has been shown to accelerate learning (McGovern & Sutton, 1998), there remains the question of skill discovery: how can agents autonomously construct useful skills via interaction with the environment? While large body of work has sought to answer this question in small discrete domains, skill discovery in high-dimensional continuous spaces remains an open problem.
An early approach to skill discovery in continuous-state environments skill chaining (Konidaris & Barto 2009b), where an agent constructs a sequence of options that target a salient event in the MDP (for example, the goal state). The skills are constructed so that successful execution of each option in the chain allows the agent to execute another option, which brings it closer still to its eventual goal. While skill chaining was capable of discovering skills in continuous state spaces, could only be applied to relatively low-dimensional state-spaces with discrete actions.
We introduce a new algorithm that combines the core insights of skill chaining with recent advances in using non-linear function approximation in reinforcement learning. The new algorithm, deep skill chaining, scales to gigh-dimensional problems with continuous state and action spaces. Through series of experiments on five challenging domains in the MuloCo physics simulator (Todorov et al., 2012), we show that deep skill chaining can solve tasks that otherwise cannot be solved by non- hierarchical agents in reasonable amount of time. Furthermore, the new algorithm outperforms state-of-the-ard deep skill discovery algorithms (Bacon et al. 2017 Levy al. 2019) in these tasks.
BACKGROUND AND RELATED WORK
Sequential decision making problems can be formalized as Markov Decision Processes (MDPs). We consider goal-orice goal-oriented episodic MDPs, where denotes the state space, is the action space, R is the reward function, T is the transition function, y is the discount factor and E S is the terminating goal state (Sutton& & Barto 2018). Unlike goal-conditioned algorithms (Sutton et al. 2011 Schaul al. 2015), do not require that g be known; instead we assume access an indicator function 1, E - (0.1) 1} which the agent can query to determine if it has reached the MDP's goal.
VVideo of learned haan:///iiiiiigtteee////ottttttn
ski iniig

---

Published as a conference paper at ICLR 2020
One way to learn policy in an MDP to first learn action-value function. The action- value fune- tion (=(, at) is defined as the expected sum of discounted future rewards if the agent takes action a, from 8, and then follows policy thereafter: (" az) [r + max..+ (* a(+1 1)].
Q-learning WWatkins& & Dayan 1992 is a commonly used off-policy algorithm that uses the action- value function for control through greedy policy (ss:) = arg max,, ((s,, (z). Inspired by recent success in scaling Q-learning to high-dimensional spaces (Mnih et al.) [015]
(115|Van Van Hasselt al.) 2016]
Lillicrap al. 2015 Tesauro 1994), we learn the action-value function Q (8t,at) (z) using non-linear
function approximators parameterized by ø, by minimizing the loss L(Ø) = En ([Q Ge) }
where the Q-learning target y, is given by the following equation (Van Hasselt et al. 2016):
Vt = ra (ar ($1+1, arg max Qs (10+11)4441)
Deep Q-Learning (DQN) (Mnih et al. 2015) casts minimizing L(Ø) as a standard regression problem by using target networks (parameterized by o') and experience replay (Lin 1993).
2.1 THE OPTIONS FRAMEWORK
The options framework (Sutoon et al. 1999) models skills as options. An option o consists of three components: (a) its initiation condition, [s(s). which determines whether can be executed state (b) its termination condition, (s), which determines whether option execution must terminate in state s and (c) its closed-loop control policy, (s), which maps state s to a low level action a E A. Augmenting the set of available actions with options results in Semi-Markov Decision Process (SMDP) (Sutton et al. 1999) where the next state depends on the current state, action and time.
2.2 SKILL DISCOVERY ALGORITHMS
Skill discovery has been studied extensively in small discrete domains (MeGovern & Sutton 1998
Şimgçk & Barto| 2004;
Simşck et al., 2005 Bakker & Schmidhuber, 2004] [Schiidhuber, [991 Dietterich] 2000). Recently however, there has been a significant body of work aimed at discovering skills in continuous spaces.
Pickett & Barto 2002
Option-critic methods: Option-Criee Critic (Bacon et al., 2017) uses an end-to-end gradient based algo- rithm to learn options in high-dimensional continuous spaces. Option-Critis was a substantial step forward in skill discovery and led to family of related methods (Klissarov et al. 2017 7 Tiwari &
Thomas 2019 Riemer et al. 2018 Liu et al. 2017: Jain et al.) 2018). Proximal Policy Option Critic (PPOC) Klissarov et al. 2017 extends Option-Critic to continuous action spaces and is the version of Option-Critic that we compare against in this paper. Our method bypasses two fundamental short- comings of the Option-Critie framework: (a) unlike Option- Critiic we explicitly learn initiation sets of options and thus do not assume that all options not treat the number of skills required to solve a task as a fixed and costly hyperparameter. Instead, our algorithm fiexibly discovers as many skills it needs to solve the given problem.
executable from everywhere, and (b) do
Feudal methods: An alternative to the options framework is Feudal RL (Dayan & Hinton 1993), which creates a hierarchy in which managers learn to assign subgoals workers; workers take subgoal state as input and learn to reach it. Feudal Networks (FuN) (Vezhnevets et al., 2017) used neural networks scale the Feudal-RL framework high-dimensional continuous spaces; was extended and outperformed by HIRO (Nachum et al. 2018 in series of control tasks in the MuJoCo simulator. More recently. Hierarchical Actor-Critic (HAC) (Levy et al.. 2019) outperformed HIRO in similar suite of continuous control problems. While HIRO relies on having dense "distance- to-goal" based reward function to train both levels of their feudal hierarchy, HAC's use of Hindsight Experience Replay (HER) (Andrychowicz et al. (017)) allows it to work in the more general sparse- reward setting. Given its strong performance in continuous control problems and its ability to learn effectively in -parse-reward reward settings, we compare against HAC representative feudal method.
Learning backward from the goal: The idea of sequencing locally applicable controllers is well es- tablished in robotics and control theory in the form of pre- pre-image backchaining (Kaelbling & Lozano- Pérez 2017) and LQR- LQR-Trees (Tedrake) 2009). Such methods either require individually engineered control loops or a model of the system dynamics. Our work fits in the model-free RL setting and
2

---

Published as a conference paper at ICLR 2020
thus requires neither. More recently, reverse curriculum learning (Florensa al. 2017 also leams backward from the goal. However, they define a curriculum of start states to learn a single policy, rather than learning skills. Relay Networks (Kumar et al. 2018) segment the value function back- ward from the goal using a thresholding scheme, which makes their method reliant on the accurate estimation of the value function. By contrast, our algorithm is agnostic to errors in value estimation, which are unavoidable when using function approximation in high gigg--iiensional spaces.
Planning with learned skills: Options have been shown to empirically speed up planning in several domains (Silver & Ciosek 2012 Jinnai et al.] 2019 James et al. 2018 Francis & Ram 1993) Konidaris 2016 SSaarma et al. 2019). However, Konidaris et al. (2018) show that for resulting plans to be provably feasible, skills must be executable sequentially. While they assume that such skills are given, we show that they can be autonomously discovered high-dimensional spaces.
3 DEEP SKILL CHAINING
Deep skill chaining (DSC) is based on the intuition that it is easier to solve hung-horizon task from states in the local neighborhood of the goal. This intuition informs the first step of the algorithm: create option that initiates near the goal and reliably takes the agent to the goal. Once such an option is learned, we create another option whose goal is to take the agent to state from which it successfully execute the first option. Skills start state of the MDP lies inside the initiation set of some option. The inductive bias of creating sequentially executable skills guarantees that as long as the agent successfully executes each skill in its chain, it will solve the original task. More formally, skill chaining amounts to learning options such that the termination condition So, (5t) of an option o; is the initiation condition Io._, (8t) of the option that precedes it in its chain.
chained backward in this fashion until the
Our algorithm proceeds as follows: time the policy over options To 8, E S determines which option to execute (Section 3.2). Control is then handed over to the selected option 0,'s internal policy To, 8 E S + 0g E RIAL_ To, outputs joint torques until it either reaches its goal (3o, == Io.-1) or times out at its predetermined budget T (Section 3.1.. At this point, To chooses another option to execute. If at any point the agent reaches the goal state of the MDP or the initiation condition of a previously learned option, it creates new option target such salient event. The machinery for learning the initiation condition of this new option is described in Section 3.3 We now detail the components of our architecture and how they are learned. Readers may also refer to Figures & 7 and the pseudo-code in Appendix A.5 to gain greater intuition about our algorithm.
3.1 INTRA-OPTION POLICY
Each option o maintains its own policy To 8 ar E RIAI, which is parameterized by its own neural networks 0g. To train (s; 0o), we must define o's internal reward function. In sparse reward problems, o is given subgoal reward when it triggers 3g; otherwise it is given step penalty. In the dense reward setting, we can compute the distance to the parent option's 's initiation set classifier and use that to define o's internal reward function. We can now treat learning the intra-option policy (T.) as a standard RL problem and use an off-the-shelf algorithm to learn this policy. Since in this work solve tasks with continuous action spaces, use Deep Deterministic Policy Gradient (DDPG) Lillicrap et al. 2015) to learn option policies over real-valued actions.
3.2 POLICY OVER OPTIONS
Initially, the policy over options (FO) only possesses one option that operates over a single time step (T=1), 1). We call this option the global option (OG) since its initiation condition is true everywhere in the state space and its termination condition is true only at the goal state of the MDP (i.c. Iog (s) It's and Bug = 1.). Using oG. TO can select primitive actions. At first the agent continually calls upon oG, which uses its internal option policy Toe to output exactly one primitive action. Once og triggers the MDP's goal state N times, DSC creates its first temporally extended option, the goal option (oz), whose termination condition is also set be the goal state of the MDP, i.e, Ba, 1g.
As the agent discovers new skills, it adds them to its option repertoire and relies on To to deter- mine which option (including oG) it must execute at each state. Unlike og, learned options will be
3

---

Published as a conference paper at ICLR 2020
temporally extended, ie, they will operate over T > 1 time steps. If in state st the agent chooses to execute option ON, then o, will execute its own closed-loop control policy (for T steps) until its termination condition is met (r < T) or it has timed out at 7 T time steps. At this point, control is handed back to To, which must now choose a new option at state 8t+T-
Option selection: To select an option in state 8t, To first constructs set of admissible options given by Equation 2 To then chooses the admissible option that maximizes its option-value function, as shown in Equation 3 Since the agent must choose from discrete set of options at any time, we learn its option-value function using Deep Q-learning (DQN) (Mnih et al. 2015).
O'(ss) = [o (8)) = 1 1 (8.) = 0, Vo, E))
(2)
Ot arg max (8) (x.)
Learning the option-value function: Given SMDP transition (st, Oz, Teetr St+r), we update the value of taking option o, in state & according to SMDP Q-learning update (Bradtke & Duff, [995). Since the agent learns Q-values for different state-option pairs, it may choose to ignore learned options in favor of primitive actions in certain parts of the state-space (in the interest of maximizing its expected future sum of discounted rewards). The Q-value target for learning the weights o of the DQN is given by:
1/2 Σ 2 Te + Q0 arg max Qo(sLtz.0)). (1
(4)
Adding new options to the policy over options: Equations 2 3 and show how we can learn the option-value function and use it for selecting options. However, we must still incrementally add new skills the network during the agent's lifetime. After the agent has learned new option o's initiation set classifier I, (we will discuss how this happens in Section 3.3), it performs the following steps before can add o its option repertoire:
To initialize o's internal policy no. the parameters its DDPG (0,) are set to the parameters the global agent's 's DDPG (foa). Subsequently, their neural networks are trained independently. This provides a good starting point for optimizing To, while allowing it to learn sub-problent specific abstractions.
To begin predicting Q-values for o, we add new output node to final layer of the DQN parame- terizing To-
We must assign appropriate initial values to (s o). We follow Konidaris & Barto 2009b) and collect all the transitions that triggered 8. and the max over these Q-values optimistically initialize the new output node of our DQN This is done by setting the bias of this new node, which ensures that the Q-value predictions corresponding the other options remain unchanged.
3.3 INTTIATION SET CLASSIFIER
Central the idea of learning skills is the ability to learn the set of states from which they can be executed. First, we must learn the initiation set classifier for Og. the option used to trigger the MDP's goal state. While acting in the environment, the agent's global DDPG will trigger the goal state N times (also referred to as the gestation period of the option by Konidaris & Barto (200b) and Niekum Barto 2011), )). We collect these successful trajectories, segment the last K states from each trajectory and learn one-class classifier around the segmented states. Once initialized, it may be necessary to refine the option's 's initiation set based on its policy. We do by executing the option and collecting data to train two-class classifier. States from which option execution was successful are labeled as positive examples. States from which option execution timed out labeled as negative examples. We continue this process of refining the option's 's initiation set classifier for a fixed number of episodes, which we call the initiation period of the option.
Using the mean Q-value is equivalent to performing Monte Carlo rollouts. Instead, we follow the principle of optimism under uncertainty (Brafman & Tennenholtz 2X22
select the over the Q-values.
4

---

Published as a conference paper at ICLR 2020
At the end of the initiation period, we fix the option's initiation set classifier and add it to the list of salient events in the MDP. We then construct a new option whose termination condition is the initiation classifier of the option just learned. We continue adding to our chain of options in this fashion until a learned initiation set classifier contains the start state of the MDP.
3.4 GENERALIZING TO SKILL TREES
Our discussion so far has been focused on learning skill chains that extend from the goal to the start state of the MDP. However, such a chain is not sufficient if the agent has multiple start states or if we want the agent to learn multiple ways of solving the same problem. To permit such behavior, our algorithm can be used learn skills that organize more generally in the form of trees (Konidaris) & Barto 2009b Konidaris et al. 2012). This generalization requires some additional care while learning mitiiaiion set classifiers, the details of which can be found in Section A.I of the Appendix. To demonstrate our ability to construct such skill trees (and their usefulness), we consider a maze navigation task, E-Maze, with distinct start states in Section 4
3.5 OPTIMALITY OF DISCOVERED SOLUTIONS
Each option o's internal policy To is is given a subgoal reward only when it triggers its termination condition 3.,. As result, To is trained to find the optimal trajectory for entering its own goal region. Naively executing learned skills would thus yield a recursively optimal solution to the MDP (Barto & Mabadevan, 2003). However, since the policy over options то does not see subgoal rewards and is trained using extrinsic rewards only, it can combine learned skills and primitive actions to discover flat optimal solution n" the MDP (Barto & Mahadevan 2003). Indeed, our algorithm allows to to employ discovered skills to quickly and reliably find feasible paths to the goal, which over time can be refined into optimal solutions. It is worth noting that our ability to recover "t in the limit is in contrast to feudal methods such as HAC (Levy et al. (019) in which higher levels of the hierarchy are rewarded for choosing feasible subgoals, not optimal ones.
To summarize, our algorithm proceeds as follows: (I) Collect trajectories that trigger new option ON's 's termination condition 3og. (2) Train ok option policy Toy (3) Learn t initiation set clas- sifier Io.. (4) Add Og to the agent's 's option repertoire. (5) Create a new option 0k+1 such that
Bou+1 Top- (6) Train policy over options To. Steps 1, 3, and continue until the MDP's start
state is inside some option's 's initiation set. Continue steps 2 and 6 indefinitely.
4 EXPERIMENTS
We test our algorithm in five tasks that exhibit a strong hierarchical structure: (1) Point-Maze (Duan) eet al. (2016). (2) Four Rooms with Lock and Key, (3) Reacher (Brockman et al.) 2016). (4) Point E-Maze and (5) Ant-Maze (Duan et al. 2016 Brockman et al., 2016). Since tasks 1, and 5 appear
frequently in the literature, details of their setup can be found in Appendix A.3
Four Rooms with Lock and Key: In this task, a point agent (Duan et al. 2016) is placed in the Four Rooms environment (Sutton et al.) 1999). It must pick up the key (blue sphere in the top-right room in Figure Mc). row and then navigate to the lock (red sphere in the top-left room). The agent's state space consists of its position, orientation, linear velocity, rotational velocity and a has key indicator variable. If reaches the lock with the key in possession, its episode terminates with sparse reward of O; otherwise it gets step penalty of -1. If we wish to autonomously discover the importance of the key, (i.e, without any corresponding extrinsic rewards) a distance-base based dense reward such as that used in related work (Nachum et al. 2018) would be infeasible.
Point E-Maze: This task extends the benchmark U-shaped Point-Maze task (Duan et al. 2016) so that the agent has two possible start locations on the top and bottom rungs of the E-shaped maze respectively. We include this task to demonstrate our algorithm's 's ability to construct skill trees.
4.1 COMPARATIVE ANALYSES
We compared the performance of our algorithm to DDPG, Option-Critic and Hierarchical Actor- Critic (HAC), in the conditions most similar those in which they were originally evaluated. For
5

---

Published as a conference paper at ICLR 2020
PoAn Mawe
apon (Paa)
-203
400
1000
210
1.0
203
210
Duetiess Chili
-3003
22000
2009
-4002
-200
230
E
Eptocds
MAC
Opddn
-1.00
-102
300
-400
950
Gptscos
130
Cotscos
129
-1020
-1220
11400
-1680
-7005
-1830
-4003
-2030
Sproode InE
(b)
Figure 1: (a) Learning curves comparing deep skill chaining (DSC), flat agent (DDPG) and Option- Critic. (b) Comparison with Hierarchical Actor Critic (HAC). (c) the continuous control tasks cor- responding to the learning curves in (a) and (b). Solid lines represent median reward per episode, with error bands denoting one standard deviation. Our algorithm remains the same between (a) and (b). All curves are averaged over 20 runs, except for Ant Maze which was averaged over 5 runs.

---

Published as a conference paper at ICLR 2020
1996
-030
-088
bend pelle wittter
(a)
(b)
(c)
(d)
Figure 2: Initiation sets of options learned in the Lock and Key task. Blue sphere in top-right room represents the key, red sphere in top-left room represents the lock. Red regions represent states inside the initiation classifier of learned skills, whereas blue/gray regions represent states outside of it. Each column represents an option the top row corresponding to the initiation set when kes is false and the bottom row corresponding the initiation set when has_key is true.
instance, in the Ant-Maze task we compare against Option-Critic under dense-reward formulation of the problem while comparing to HAC under sparse-reward version the same task. As a result, show the learning curves comparing against them different plots (columns (a) and (b) in Figure reepeccivveyy) to emphasize the difference between the algorithms, the settings in which they applicable, and the way they are evaluated.
Comparison with DDPG and Option-Critic: Figure Ta) shows the results of comparing our pro- posed algorithm (DSC) with flat RL agent (DDPG) and the version of Option-Critic designed for continuous action spaces (PPOC) Deep skill chaining comfortably outperforms both base- lines. Both DSC and DDPG use the same exploration strategy in which a, TT())) The where N (O, ez). Option-Critic, on the other hand, learns stochastic policy To (8r) and thus has baked-in exploration (Sutton Barto 2018 Ch. 13). precluding the need for additive noise during action selection. We hypothesize that this difference in exploration strategies is the reason Option- Critic initially performs better than both DDPG and DSC in the Reacher and Point E-Maze tasks.
Comparison with Hierarchical Actor-Critic: We compare our algorithm to Hierarchical Actor- Critic (HAC) (Levy et al. 2019). which has recently outperformed other hierarchical reinforcement learning methods (Nachum et al. 2018 Vezhnevets al. 2017) on wide variety of tasks. P A noteworthy property of the HAC agent is that it may prematurely terminate prevent flooding its replay buffer with uninformative transitions. The length of each training episode in DSC however, is fixed and determined by the test environment. Unless the agent reaches the goal state, its episode lasts for the entirety of its episodic budget (e.g. this would be 1000 timesteps in the Point-Maze environment). Thus, to compare the two algorithms, we perform periodic test rollouts wherein all networks frozen and both algorithms have the same time budget solve the given task. Furthermore, since both DSC and HAC learn deterministic policies, we set = 0 during these test rollouts. When comparing HAC, we perform 1 test rollout after each training episode in all tasks except for Ant-Maze, where we average performance over 5 test rollouts every 10 episodes.
training episodes to
Figure [b) shows that DSC outperforms HAC in all environments except for Four Rooms with a Lock and Key. where their performance is similar, even though DSC does not use Hindsight Experience Replay (Andrychowicz al. 2017) deal with the sparse reward nature of this task.
4.2 INTERPRETING LEARNED SKILLS
Figure 2 visualizes the initiation set classifiers of options discovered by DSC in Four Rooms with a Lock and Key. Despite not getting any extrinsic reward for picking up the key, DSC discovers
*PPOC author's implementation: http://gtthhhh.ommmiiiisspPCCCC
'HAC author's implementation: htwp://tttccccoonoooeeyyyyyeeeet

---

Published as a conference paper at ICLR 2020
(a) Maze
(b) Four-Rooms
(c) Ant-Maze
(d) E-Maze
Figure 3: Solution trajectories found by deep skill chaining. Sub-figure (d) shows trajectories corresponding to the two possible initial locations in this task. Black points denote states in which To chose primitive actions, other colors denote temporally extended option executions.
the following skill chain: the options shown in Figure 2 columns (c) and (d) bring the agent to the room with the key. The option shown in column (b) then picks up the key (top row) and then takes the agent to the room with the lock (bottom row). Finally, the option in column (a) solves the overall problem by navigating to the lock with the key. Similar visualizations of learned initiation set classifiers in the E-Maze task be found in the Figure in the Appendix.
Figure 3 shows that DSC is able to learn options that induce simple, efficient policies along different segments of the state-space. Furthermore, it illustrates that in some states, the policy over options prefers primitive actions (shown in black) over learned skills. This suggests that DSC is robust to situations in which it constructs poor options is unable learn good option policy in certain portions of the state-space. In particular, Figure (d) shows how DSC constructs a skill tree to solve problem with two distinct start states. learns a common option near the goal (shown in blue), which then branches off into two different chains leading to its two different start states respectively.
DISCUSSION AND CONCLUSION
Deep skill chaining breaks complex long-horizon problems into a series of sub-problems and learns policies that solve those sub-problems. By doing so, provides significant performance boost when compared to flat learning agent in all of the tasks considered in Section
We show superior performance when compared to Option- Critti, the leading framework for option discovery in continuous domains. A significant drawback of Option-Critic is that it assumes that all options are executable from everywhere in the state-space. By contrast, deep skill chaining explicitly learns initiation set classifiers. As result, learned skills specialize in different regions of the state- space and do not have to bear the burden of learning representations for states that lie far outside of their initiation region. Furthermore, each option in the Option- Critiic architecture leverages the same anttrabbstaction to learn aption-specifis value functions and policies, while deep skill chaining permits each skill to construct its skill-specific state- aatte-abstacctinn (Konidaris & Barto (0099)). (009))) An advantage of using Option-Crite over DSC is that not confined to coal-oriented tasks and can work in tasks which require continually maximizing non-sparse rewards.
Section also shows that deep skill chaining outperforms HAC in four out of five domains, while achieving comparable performance in one. We note that even though HAC was designed work in the multi-goal setting, we test it here in the more constrained single-goal setting. Consequently, we argue that in problems which permit stationary set of target events (like the ones considered here), deep skill chaining provides a favorable alternative to HAC. Furthermore, HAC depends on Hind- sight Experience Replay (HER) to train the different layers of their hierarchy. Deep skill chaining shows the benefits of using hierarchies even in the absence of such data augmentation techniques but including them should yield additional performance benefits in sparse-reward tasks.
A drawback of deep skill chaining is that, because it builds skills backward from the goal, its per- formance in large state-spaces dependent on a good exploration algorithm. We used the naive exploration strategy of adding Gaussian noise to chosen actions (Lillicrpp et al.) 20155] Fujimoto ctt al. 2018) since the exploration question orthogonal to the ideas presented here. The lack of sophisticated exploration algorithm also explains the higher variance in performance in the Point- Maze task in Figure [ Combining effective exploration (Machado et al. 2018 Jinnai et al. 2020) with DSC's high reliability of triggering target events is promising avenue for future work.
We presented a new skill discovery algorithm that can solve high-dimensional goal-oriented tasks far more reliably than flat RL agents and other popular hierarchical methods. To knowledge,
8

---

Published as a conference paper at ICLR 2020
DSC is the first deep option discovery algorithm that does not treat the number of options fixed and costly hyperparameter. Furthermore, where other deep option discovery techniques have struggled to show consistent improvements over baseline flat agents in the single task setting (Zhang & Whiteson 2019, Smith et al. 2018 Harb et al. 2018: Klissarov et al. 2017), we unequivocally show the necessity for hierarchies for solving challenging problems.
ACKNOWLEDGEMENTS
We thank Andrew Levy, Nakul Gopalan, Sam Lobel, Theresa Barton and other members of the Brown bigAl group for their inputs. This research was supported in part by DARPA under agree- ment number 1-0124 and the ONR under the PERISCOPE MURI Contract N00014-17-1-2699. The U.S. Govern- ment is authorized reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The content solely the responsibility of the authors and does not necessarily represent the official views of DARPA, the ONR, or the AFOSR.
AFOSR Young Investigator Grant agreement number FA9550-17-
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience re- play. In Advances in Neural Information Processing Systems, pp. 5048-5058, 2017.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Thirty-Firsi AAAI Conference on Artificial Intelligence, 2017.
Bram Bakker and Jürgen Schmidhuber. Hierarchical reinforcement learning with subpolicies spe- cializing for learned subgoals. Neural Networks and Computational Intelligence, pp. 125-130. Citeseer, 2004.
Andrew G Barto and Sridhar Mahadevan. Recent advances in hicrarchical reinforcement learning. Discrete event dynamic systems, 13(1-2):41-77, 2003.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pp. 1471-1479, 2016.
Steven Bradtke and Michael Duff. Reinforcement learning methods for continuous-time markov decision problems. In Advances in neural information processing systems, pp. 393-400, 1995.
Ronen I Brafman and Moshe Temnenholtz. R-Max general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 300t1)211--33,, 2002.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint 1rXiv:1606.015400 2016.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019. URL https: //openreview wttp://oooomdddllllomooa
Peter Dayan and Geoffrey E Hinton. Feudal reinforcement learning. In Advances in neural infor- mation processing systems, pp. 271-278, 1993.
Thomas G Dietterich. Hierarchical reinforcement learning with the maxq value function decompo- sition. Journal of Artificial Intelligence Research, 13:227-303, 2000.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International Conference on Machine Learning, pp. 1329-1338, 2016.
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse riculum generation for reinforcement learning. In Conference on Robot Learning, pp. 482-495, 2017.

---

Published as a conference paper at ICLR 2020
Anthony G Francis and Ashwin Ram. The utility problem in base-based reasoning. In Case- Based Reasoning: Papers from the 1993 Workshop, pp. 160-161, 1993.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-
critic methods. In International Conference on Machine Learning, pp. 1582-1591, 2018.
Jean Harb, Pierre-Luc Bacon, Martin Klissarov, and Doina Precup. When waiting not an op-
tion: Learning options with a deliberation cost. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Arushi Jain, Khimya Khetarpal, and Doina Precup. Safe option-critic: Learning safety in the option- critic architecture. CoRR, abs/1807 007.08060, 2018. URL http://axxivvoorg/bb///B00 08060
Steven James, Benjamin Rosman, and George Konidaris. Learning to plan with portable symbols. the (CMI/UCAVAAAAS 2018 Workshop Planning and Learning, 2018.
Yuu Jinnai, David Abel, David Hershkowitz, Michael Littman, and George Konidaris. Finding options that minimize planning time. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pp. 3120-3129 Long Beach, California, USA, 09-15 Jun 2019. PMLR. Uttphtttp://prcceediii
ml press /tt////9/////// 9a. html
Yuu Jinnai, Jee Won Park, Marlos C. Machado, and George Konidaris. Exploration in reinforcement learning with deep covering options. In International Conference Learning Representations, 2020. URL
Leslie Pack Kaelbling and Tomás Lozano-Pérez. Pre-image backchaining in belief space for mobile manipulation. In Robotics Research, pp. 383-400. Springer, 2017.
Martin Klissarov, Pierre-Luc Bacon, Jean Harb, and Doina Precup. Learnings options end-to-end for continuous action tasks. Hierarchical Reinforcement Learning Workshop (NeurIPS), 2017.
George Konidaris. Constructing abstraction hierarchies using skill-symbol loop. In IJCAI: pro- ceedings of the conference, volume 2016, pp. 1648. NIH Public Access, 2016.
George Konidaris. On the necessity abstraction. Current Opinion in Behavioral Sciences, 29:
107.
George Konidaris and Andrew Barto. Efficient skill learning using abstraction selection. In Twenty- First International Joint Conference on Artificial Intelligence, 2009a.
George Konidaris and Andrew Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. In Advances in Neural Information Processing Systems, pp. 1015-1023, 2009b.
George Konidaris, Scott Kuindersma, Roderic Grupen, and Andrew Barto. Robot learning from demonstration by constructing skill trees. The International Journal of Robotics Research, 31(3): 360-375, 2012.
George Konidaris, Leslie Pack Kaelbling, and Tomas Lozano-Perez. From skills symbols: Learn ing symbolic representations for abstract high-level planning. Journal of Artificial Intelligence Research, 61:215-289, 2018.
Visak CV Kumar, Schoon Ha. and Karen Liu. Expanding motor skills using relay networks. In Conference on Robot Learning, pp. 744-756, 2018.
Andrew Levy, Robert Platt, and Kate Saenko. Hierarchical reinforcement learning with hindsight. In International Conference on Learning Representations, 2019. URI.
net/ feet/Eose Eorumoidumiiooo IyyddAAooyyyEEy
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint 1509.0000.00000 2015.
10

---

Published as a conference paper at ICLR 2020
Long-Ji Lin. Reinforcement learning for robots using neural networks. Technical report, Careegi- Mellon Univ Pittsburgh PA School of Computer Science, 1993.
Miao Liu, Marlos C Machado, Gerald Tesauro, and Murray Campbell. The eigenoption -riiiii critic frame- work. arXiv preprint arXiv: 04005, 2017.
Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray
Campbell. Eigenoption discovery through the deep successor representation. In International Conference on Learning Reprexentations, 2018.
1d=Bk82cAxR-
Amy McGovern and Richard Sutton. Macro-actions in reinforcement learning: An empirical analysis. Computer Science Department Faculty Publication Series, pp. 15, 1998.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et 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 in Neural Information Processing Systems, pp. 3303-3313, 2018.
Scott Niekum and Andrew G. Barto. Clustering via dirichlet process mixture models for portable skill discovery. In J. Shawe-Taylor, R. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 24, pp. 1818-1826. Curran Asso- ciates, Inc., 2011.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournaeea, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-leamn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2832 2011.
Mare Pickett and Andrew G Barto. Policyblocks: An algorithm for creating useful macro-actions in reinforcement learning. In ICML, volume 19, pp. 506-513, 2002.
Matthew Riemer, Miao Liu, and Gerald Tesauro. Learning abstract options. In Advances Neural Information Processing Systems, pp. 10424-10434, 2018.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxima- tors. In International conference on machine learning, pp. 1312-1320, 2015.
Jürgen Schmidhuber. Learning to generate sub-goals for action sequences. In Artificial neural networks, pp. 967-972, 1991.
Archit Sharma, Shixiang Gu, Sergey Levine. Vikash Kumar, and Karol Hausman. Dynamics-award awwre unsupervised discovery of skills. arXiv preprint arXhv:1907.01655 2019.
David Silver and Kamil Ciosek. Compositional planning using optimal option models. In JCML, 2012.
Özgür Şimşek and Andrew G Barto. Using relative novelty to identify useful temporal abstractions in reinforcement learning. In Proceedings the twenty-firs international conference on Machine learning, pp. 95. ACM, 2004.
Özgür Şimşek, Alicia P Wolfe, and Andrew G Barto. Identifying useful subgoals in reinforcement learning by local graph partitioning. In Proceedings of the 22nd international conference on Machine learning, pp. 816-823. ACM, 2005.
Matthew Smith, Herke van Hoof, and Joelle Pineau. An inference- policy gradient method for learning options. In Jemnifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4703 4712, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http: //proceed i ngs. ml nlr. press v smi th1 8a. html

---

Published as a conference paper at ICLR 2020
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard $ Sutton, Doina Precup, and Satinder P Singh. Intra-option learning about temporally abstract actions. In ICML, volume 98, pp. 556-564, 1998.
Richard S Sutton, Joseph Modayil, Michael Delp. Thomas Degris, Patrick M Pilarski, Adam White, and Doina Precup. Horde: A scalable real-time architecture for learning knowledge from unsuper- vised sensorimotor interaction. In The 10th International Conference on Autonomous Agents and Multiagent Systems- Volume 2, pp. 761-768. International Foundation for Autonomous Agents
and Multiagent Systems, 2011.
R.S. Sutton, D. Precup, and S. Singh. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1):18-2211 1999.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schul- man, Filip DeTurek, and Pieter Abbeel. exploration: study of count-based exploration for deep reinforcement learning. In Advances in neural information processing systems, pp. 2753- 2762, 2017.
Russ Tedrake. LQR-trees: Feedback motion planning on sparse randomized trees. 2009.
Gerald Tesauro. TD-Gammon, a self-teaching backgammon program, achieves master-level play. Neural computation, 6(2):215-219, 1994.
Saket Tiwari and Philip S Thomas. Natural option critic. In Proceedings the AAAI Conference on Artificial Intelligence, volume 33, pp. 5175-5182, 2019.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q- learning. Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- 3549. JMLR. org, 2017.
Learning-Volume Volume 70, pp. 3540-
Christopher JCH Watkins and Peter Dayan. Q-learning. Muchine learning, 8(3-4):279-292, 1992.
Shangtong Zhang and Shimon Whiteson. DAC: The double actor-critic architecture for learning options. In Advances in neural information processing systems, pp. To appear, 2019. URL https:/ //arx//rxxin avvii.... vv. org/ abs//////// 1904 12691
12

---

Published as a conference paper at ICLR 2020
(a)
(b)
(c)
(d)
Figure 4: An illustration of the deep skill chaining algorithm. represents the goal state, repre- sents the two start states. (a) Before the agent has discovered its first skill/option, it acts according to its global DDPG policy. Having encountered the goal state N times, the agent creates option to trigger the goal from its local neighborhood. (b) Now, when the agent enters the initiation set of the first option, it begins to learn another option trigger the first option. (c) Because the agent has two different start states, it learns two qualitatively different options to trigger the option learned in
(b). (d) Finally, the agent has learned skill tree which it can follow consistently reach the goal.
A APPENDIX
A.I
CREATING SKILL TREES
we introduced the idea of generalizing skill chains to skill trees to incorporate quali- tatively different solution trajectories. In this section, we provide some of the implementation details required to learn initiation set classifiers that organize in the form of trees.
In Section 3.4
When creating skill chains, the goal of each option trigger the initiation condition the option that precedes it in its chain (i.e, its parent option). When creating a skill tree of branching factor B, we allow at most B options to target each salient event in the MDP (i.e, the goal state and the initiation set classifiers of preexisting options). To further control the branching factor of the skill tree, we impose two more conditions on option creation:
1. Consider an option 01 which already has one child option o2 targeting it. Now suppose that we want to learn another option 03 that also targets 01. We only consider state St to be positive example training Iog if Tog (8x) = 0.
2. To prevent significant overlap between options that target the same event, we treat the pos- itive examples used to train the initiation set classifier of one as negative training examples of all its sibling options. This allows for multiple options that trigger the same target event, while encouraging them to specialize in different parts of the state-space.
In the Point F-Maze task considered in Section we learn skill tree with B = 2.
A.2 INTRA-OPTION Q-LEARNING
In principle, the methodology outlined in Section 3.2 is sufficient to learn an effective policy over options тO. However, when O is a set of Markov options (Sutton et al. 1999), which is the setting considered in this paper, we can use intra-option Q-learning (Sutton et al. 1998) to improve the sample efficiency associated with learning πo.
More specifically, given transition (se, O, Teatts St47), SMDP Q-learning treats option as a black box and uses Equation to determine the Q-value target y, for updating то. Intra-option Q-learning leverages the fact that option o is Markov to point out that all the transitions experienced during the execution of are also valid experiences for training To. As long as state $141, Vi [0, 7] is inside the initiation set the option o, we can pretend that option execution really began state $ and add the transition (St+i, O, Fttittt; St+r) to the To" replay buffer.
13

---

Published as a conference paper at ICLR 2020
Furthermore, intra-option Q-learning also provides way to improve the sample efficiency asso- ciated with learning option policies To. vo O. This can be done by making off-policy updates to each option's internal policy. In other words, regardless of which option is actually executed in the MDP, as long as a state experienced during execution inside the initiation set of some other option, we add the associated experience tuple to that (un-executed) option's replay buffer. Note that this is possible because we use an oof-pc learning algorithm (DDPG) to learn intra-option policies.
A.3 TEST ENVIRONMENTS
A description of the Four Rooms and the Point E-Maze tasks was provided in Section 4 Here describe the remaining tasks considered in this paper:
Point Maze: In this task, the same point agent as in the four rooms task must navigate around
U-shaped maze to reach its goal. The agent receives a reward of -1 for every step it lives, and sparse terminating reward of when it reaches its goal location. This is an interesting task for hierarchical agents because in order to reach the goal, the agent must first move away from it. is clear that dense distance-based reward formulation of this problem would only serve deceive non-hierarchical agents such as DDPG.
The ant (Duan al. 2016) is challenging agent to control due to its non-linear and highly unstable dynamics. In this task, the ant must now navigate around the same U-shaped maze in the Point Maze task. Getting the ant cover significant distances along the I, y plane with- out falling over, is benchmark control task itself (Brockman et al., 2016). As a result, constructing options backward from the goal could require prohibitively large traming episodes or the use of a so- phisticated exploration algorithms (Burda et al. 2019 Bellemare et al. 2016;) Tang et al. (017). To avoid conflating our results with the orthogonal investigation of effective exploration RI., we fol- low the experimental design of other ofate-of-the-art hierarchical reinforcement learning algorithms (Levy et al., 2019] Nachum et al., 2018) and sample the initial state of the ant uniformly across the maze for the first 30 episodes. For fair comparison, all baseline algorithms use this exploration strategy.
Ant Maze:
Fixed Reacher: We the Reacher task (Brockman et al. 2016) with two modifications. First, rather than randomly sampling a new goal at the start of each episode, we fix the target across all episodes. We do this because if the goal moves, following learned skill chain will no longer solve the MDP. Note that the same modification was made in the DDPG paper (Lillicrap et al.) (015)). Second, to increase the difficulty of the resulting task, we use sparse reward function rather than the dense distance-based one used in the original formulation.
Task
Number of steps per episode
Point-Maze
1000
Four Rooms with Lock and Key
5000
Point E-Maze
1500
Reacher
500
Ant-Maze
2000
Table I: Maximum number of time steps per episode in each of the experimental domains
14

---

Published as a conference paper at ICLR 2020
Paliitu
1000
(b)
(d)
Figure 5: Analysis of performance (as measured by mean cumulative reward) of DSC agent as is allowed to learn more skills in (a) Point-Maze, (b) Four Rooms with Lock and Key, (c) E-Maze and (d) Ant-Maze. Note that in general, DSC discovers many skills it needs to solve the given problem. For this experiment alone, we restrict the number of skills that the DSC agent can learn. All experiments averaged over runs. Error bars denote standard deviation. Higher is better.
Initaation
apoion_3_1 3,100.
everall Inttaaion
spcien Set
Figure 6: Initiation set classifiers learned in the Point E-Maze domain. Discovered skills organize in the form of tree with a branching factor of 2. The option on the extreme left initiates the proximity of the goal. Options learned after the goal option branch off into two separate skill chains. The chain on top extends backward the start state the top rung of the E-Maze. The chain shown in the bottom row extends backward to the start state in the bottom rung of the E-Maze.
15

---

Published as a conference paper at ICLR 2020
A.4 ABLATION STUDY
A.4.1 PERFORMANCE A FUNCTION OF NUMBER OF SKILLS
Deep skill chaining generally discovers and learns as many skills as it needs to solve given problem. In this experiment however, we restrict the number of skills DSC can learn to examine its impact on overall agent performance (as measured by cumulative reward during training). the performance the agent increases monotonically (with diminishing marginal improvements) as it is allowed to learn more skills.
shows that
A.4.2 NUMBER OF SKILLS OVER TIME
Figures 7 (a) and 7 (b) illustrate how deep skill chaining incrementally discovers options and adds it to the agent's option repertoire. Figure shows how the number of skills empirically increases over time, plateaus and has low variance between runs. Since the agent has to learn the importance of the key in the Four Rooms task, learning initiation set classifiers takes longer than in the Point-Maze task.
A.4.3 HYPERPARAMETER SENSITIVITY
In this section, analyze DSC's sensitivity to some of the hyperparameters specific the algo- rithm. In Figure we show that even under a fairly large range of values for the buffer length K and the gestation period N, DSC is able retain its strong performance.
16

---

Published as a conference paper at ICLR 2020
Gatalcaiion %
Glaiel Optior
Pollyy Ovtr Options
Poliyy Over Options
Paay XB1
Ree KD
(DO
Optians
Option DCPS
DDPG
Actionut outout
Ackly Ovapi
(a)
(b)
Agent
Point Maze
Number of Skills
20
40
60
(c)
Figure 7: (a) Initially, the policy over options can only choose the global option og as a proxy for selecting primitive actions. (b) Over time, the agent learns temporally extended skills and adds output nodes to the final layer of the DQN parameterizing то. This continues until the start state so lies inside the initiation set of learned option. (c) Empirical evaluation of how the number of skills in the agent's 's option repertoire changes over time in Point-Maze and Rooms with Lock and Key.
17

---

Published as a conference paper at ICLR 2020
DSC Four-Rooms after 750 episodes
DSC Four-Rooms after 750 episodes
Cumulation auvvlltvve Reward (x1000)
-250
-20
-750
-750
-1250
1250
-1500
1500
-1750
DDPG Baseline
-150
DDPG Baseline
10
20
30
10
15
20
DSC Poink-Maze after 300 episodes
DSC Point-Maze after 300 episodes
Curvlattvv Reward (X1000)
-50
-100
-100
-150
-150
-200
-200
-250
DDPG Baseline
-20
DDPG Baseline
10
20
30
40
10
Butfer Length (K)
Gestation Period (N)
Figure 8: Variation in DSC performance (as measured by mean cumulative reward) as function of two hyperparameters: (left) the buffer length K and (right) the gestation period N of the option. For a qualitative description of both hyperparameters, refer to Section 3.3] This experiment shows that DSC is fairly robust to most reasonable choices of these parameters. All experiments averaged over runs. Error bars denote standard deviation. Higher is better.
18

---

Published as a conference paper at ICLR 2020
A.5 ALGORITHM PSEUDO-CODE
Algorithm 1: Deep Skill Chaining
so is the start state of the MDP
(s)s) == 1 if s is a target state in the MDP, 0 otherwise
Given hyperparameter To. the time budget for discovered, temporally extended options
Global option: OG = (Jag: Nags Po0 11 T = 1)
Goal option: 0g = (To No, Pog 1
T=
Agent's s option repertoire: O {oc}
Untrained Option: ou = 0g option whose initiation classifier is yet unlearned
Policy over options: no: O2
St = S0
while not st.is terminall) do
Pick new option and execute in environment
Choose O₂ according to To(s)) using Equations and 3
Terr St+r eerecute_.ption(((
rrouudate(ss, Ot, Itat++r St+r) using Equation
Learn initiation set of new option
I/ Collect trajectories that trigger ou's 's termination region unless have finished chaining
Bo ($t+r) & (spεI, Vo; E O) then
oy learn initiation classifier( using procedure described in Section 3.3
if ou iniliaiioi classi jier is trained() then to add((r))) using procedure described in Section 3.2
O D.append(ou)
ou create_chiil..optinn(rj
end end
end
Function create child optionn (o):
Create new option whose / is the parent's I.
o² Option() // Create new option
Io- None
8, = Ioo
return o"
Function execute opt on (0:): ".* Option control loop.
to =o
T is the option's 's episodic time budget To, is the option's 's internal policy
while not So, (st) & T do
Or To, (8t; Om.))
Tt, 8141 env.step(a:)
8
t f=t+1
end
T /// duration of option execution
return Tioioo+7 S16+7
A.6 MORE DETAILS ON IMPLEMENTING OPTION REWARD FUNCTIONS
explains that to learn option's 's intra-option policy, must define its internal reward function. While most of our experiments are conducted in the sparse-reward setting, deep skill chaining be used without much modification in dense reward tasks as well. All that remains is clear description of how each option's 's internal reward function would be defined in such a setting.
Section 3.1
Consider option o, with parent option 0,-1 such that So, Io,-,. In the dense reward setting, we use the negative distance from the state to the parent option's 's initiation classifier as the reward function. Since initiation classifiers are represented using parametric classifiers, computing the dis-
19

---

Published as a conference paper at ICLR 2020
tance the classifier's decision boundary is straightforward and be done using most popular machine learning frameworks. For instance, when using scikit-learn (Pedregosa et al. 2011) this is implemented follows:
0.
if (o(())) =1
Ra (s, ( det....dciiiioo.uuutttiooo
(5)
otherwise
Where in Equation deci con.fuuctionff returns the distance in feature space between point x E R. and the decision boundary learned by the classifier Io,
A.7 LEARNING INITIATION SET CLASSIFIERS
To learn initiation set classifiers as described in Section 33 we used scikit-learn's One-Class SVM and Two-Class SVM packages (Pedregosa et al. 2011 Initiation set classifiers were learned on subset of the state variables available in the domain. For instance, in the Lock and Key domain, the initiation set classifier was learned over the y position and the has_key indicator variable. This is similar to other methods like HAC (Levy et al., 2019) which require the user to specify the dimensions of the state variable necessary achieve the overall goal of the MDP. Incorporating the entire state variable to learn initiation set classifiers or using neural networks for automatic feature extraction should be straightforward and is left future work.
A.8 HYPERPARAMETER SETTINGS
We divide the full set of hyperparameters that our algorithm depends on into two groups: those that are common to algorithms that use DDPG (Table 2), and those that are specific to skill chaining (Table 3) We did not try to optimize over the space of DDPG hyperparameters, and used ones used previous work (Liliccrpp et al. 2015 Fujimoto et al. 2018). Table 3 shows hyperparameters that chose the different tasks considered in this paper. Most of them concerned with learning initiation set classifiers, the difficulty of which varies based on domain. To determine the correct setting of these parameters, usually visualized the learned initiation set classifiers during the course training (like Figures 2 and 6 and made adjustments accordingly.
Parameter
Value
Replay buffer size Batch size
1e6
64
7
0.99
T
0.01
Number of hidden layers
2
Hidden size 1
400
Hidden size 2
300
Critic learning rate
le 3
Actor learning rate
le 4
Table 2: DDPG Hyperparameters
Parameter
Point Maze
Four Rooms
Reacher
Ant Maze
E-Maze
Gestation Period (N)
5
10
5
5
Initiation Period
10
0
1
Buffer Length (K)
20
20
20
750
20
Option Max Time Steps (T)
100
150
150
100
100
Table 3: Deep Skill Chaining Hyperparameters
20

---

Published as a conference paper at ICLR 2020
A.9
COMPUTE INFRASTRUCTURE
We used I INVIDIA Geffrce 2080 Ti, 2 NVIDIA Geforce 2070 Ti and Tesla K80s on the Google Cloud compute infrastructure perform all experiments reported in this paper.
A.10 NOTE COMPUTATION TIME
Each option is parameterized by its own neural networks, which are only updated when the agent is inside that option's s initiation set. For a given transition, this leads to at most two or three updates. In Point-Maze, updating all options on transition took 0.004 + 0.0003 more than just updating the global DDPG agent (averaged over 300 episodes using I NVIDIA 2080 GPU) a trivial amount of extra computation time.
21


Reviews:
[{"review_id": "Syx0cm0pKB", "reviewer": "AnonReviewer3", "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": "Summary\nThe authors tackle the problem of skill discovery by skill chaining. In particular, the authors claim two key contributions over the state of the art in option discovery 1) learn initiation sets 2) do not need to specify the number of options and this is also learned. Skill discovery is formalized by skill chaining; wherein the skills are chained backward from a goal state, and in a way, such that termination of an option is the initiation of the option that precedes in its chain. \n\nInteresting and useful aspects of this work are goal-based learning of where options should initiate (although clarification on goals would be crucial), the discussion of the optimality of the discovered solutions, scales up various ideas already proposed in Konidaris & Barto (2009b). \n\nSkill discovery through skill chaining, in particular, has not been extensively explored in a deep RL setting and serves as a useful contribution.\n\nDetailed comments:\nThe authors introduce DSC with an intuition based on a goal. However, it is never mentioned where this goal comes from. In sec 3, the authors describe an algorithm based on the presumed goal. It is not clear to me: the goal is at one instance defined as \\beta_{o_i} := \\mathcal{I}_{o_i - 1}, and then in the next few lines, it is said “goal state of the MDP or the initiation condition of a previously learned option”. Is it correct to say this is an algorithm (sec 3) for goal-based option discovery using DSC, where the goal is specified in the MDP? \n\nBefore going into the details of the architecture, it would be useful for the reader to have a formalism or a clear algorithm where at least the definition of what a goal constitutes here is clearly stated. \n\nIntra-option policy: It is nice to see that the option’s internal policy is not driven by the task-specific reward and has its internal reward. In the sparse reward setting: how is the subgoal reward chosen? In dense reward: what kind of distance metric is used? Please provide details.\n\nPolicy over options: The foremost option constructions seems a bit weird: is there a single goal specified which helps determine the termination condition of the global option? What would happen if there are multiple goals in the MDP? \n\nInitiation set classifier: This is an interesting approach. Although, it raises a natural question: “\t\nWe continue adding to our chain of options in this fashion until a learned initiation set classifier contains the start state of the MDP. “ What happens if this never happens, or is this process is guaranteed to converge?\n\nExperiments: Initiation set visuals are nice and interpretable. Experiments are not very convincing: authors mostly demonstrate results on control tasks that are specific to navigation and could do a more rigorous analysis by considering different tasks such as visual domains, robot manipulation tasks.  In particular, authors should compare their method and discuss other skill chaining approaches such as [1,2,3].\n\n[1] Shoeleh, Farzaneh, and Masoud Asadpour. \"Graph-based skill acquisition and transfer learning for continuous reinforcement learning domains.\" Pattern Recognition Letters 87 (2017): 104-116.\n[2] Metzen, Jan Hendrik, and Frank Kirchner. \"Incremental learning of skill collections based on intrinsic motivation.\" Frontiers in neurorobotics 7 (2013): 11.\n[3] Konidaris, George, et al. \"Robot learning from demonstration by constructing skill trees.\" The International Journal of Robotics Research 31.3 (2012): 360-375.\n\nMy primary concern is the amount of engineering that is needed to get this to work. There are multiple steps which do not seem to be sequentially dependent on the success of the previous steps (eg: global option construction needs a goal, the next options are only discovered once the global actions has been constructed, there is an initiation period and internal components of an option are all learned through multiple algorithms DQN, SMDP Q learning, DDPG). \n\nOverall:\t\t\n+Break the assumption that all options are everywhere.\n+Number of options per task is also learned and does not need to be specified a priori.\n+Chains skills in a smart way - which could be very useful for lifelong learning, but the approach, as it is, is limited by the goal of the MDP (whatever that means in this context, state or a Reward). \n+Options are driven by internal rewards\n-The heavy machinery used in the core algorithm seems to be inspired by Konandiais 2009b. It would be very useful to discuss, clarify and contrast what is novel and what is borrowed from Konandiais 2009b as is.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJxLXHtaFS", "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": "Summary of the paper\nThe authors tackle hierarchical RL and build upon the work of (Konidaris & Barto, 2009b) to derive a skill chaining algorithm with non-linear function approximations.\nDuring execution, skill chaining is an option-based algorithm, ie., a master policy (the option policy in the paper) selects one of O options and then delegates the control the corresponding sub-policy that executes primitive actions until their termination condition.\nThe learning consists of learning the master policy, here a DQN algorithm, as well as the sub-policies, each of which is a separate instance of DDPG (meaning, they do not share weights).\nThe gist of the learning algorithm, DSC, is to proceed backward. Initially the goal state is is the default termination condition.  As new options are added to the pool, their terminal condition simply correspond to the initial condition of their subsequent option, which consist in a learnt classifier that acts as indicator function during the learning phase.\n\nGeneral remarks\nThe paper is overall clear and well written. The background and related work section is informative and well structured. The experiments are sound (and all averaged over 20 different seeds-except for one). \n\nFrom a performance perspective, DSC is comparable to the state of the art most of the time, and even improving upon it on some experiments. However, I am not totally convinced that the learnt skills can be interpretable as clearly indicating different regions of the environment.\nLooking at Fig 3 and the attached video for instance, the skills oscillate and seem unstable overall.\n\nAlso, the choice of N (the number of the rollouts during the gestation period) and K (the segmentation threshold) seem to be crucial and very much application dependent. It would have been useful to plot the performance of DSC for different values of of these hyperparameters in order to show the potential “flatness” of the error surface.\n\nFinally, when the learning starts, the (only) option o_G must reach the goal state N times. Which means, the initial DDPG agent has to gather a certain amount of successful rollouts. \n\n- Isn’t that a strong condition, given that initially, hierarchical RL is meant to overcome long sequences issues in “flat” RL? \n- Could you please elaborate on the training time of DSC?\n- Given that DDPG fails at the Point E-Maze environment, how could DSC still learn new options?\n\nSuggestions for improvement\n- Page 4, in “learning the option-value function”: it is mentioned that the master policy can choose primitive actions. This part only becomes clear in Page 5 when it is mentioned that it happens through the global option.\n- Page 4, in “adding new options…”, could you please clarify how the max of the returns is set as the initial Q-value. Since its’ not tabular, how can it be “assigned”? If I understood correctly, it is regressed towards this max return value, but I can’t find it clearly expressed in the text. But then, how does it affect the rest of the Q values? \n\nMinor\n1. T represents the transition function page 1 and is then overloaded to represent time steps (page 3) without notice. \n2. page 5, paragraph 3.5: redundancy in “is is”", "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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkgp_NaFYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of learning suitable action abstractions (i.e., options or skills) that can be composed hierarchically to solve control tasks. The starting point for the paper is the (classic) observation that one skill should end where another can start. The paper then proposes a recursive algorithm for learning skills that obey this property. After finding some number of trajectories that reach the goal, the last few states of these trajectories are taken to define the initiation set for the ultimate skill and the termination set for the penultimate skill. The procedure is repeated, yielding a sequence (a \"chain\") of skills that extends from the initial state distribution to the terminal state. The fact that the number of skills is not defined apriori seems to be a strength, and the extension to trees of skills is neat.\n\nThe paper compares the proposed algorithm against state-of-the-art hierarchical baselines on five continuous control tasks of varying complexity; the proposed method outperforms baselines on 2 - 4 of the 5 tasks (depending on the setting considered).\n\nPerhaps the biggest limitation of the paper is that it ignores the exploration problem. As noted in \"Why Does Hierarchy (Sometimes) Work So Well in Reinforcement Learning?\", exploration is empirically one of the main benefits of HRL, yet the proposed method, by construction, cannot take advantage of this strength.\n\nI am leaning towards accepting this paper. While the idea is quite simple, it seems to work well empirically and, to the best of my knowledge, is novel. The simplicity should also make it a good launching point for future work in HRL. My main concern with the paper is that the poor performance of baselines on some of the tasks. For example, HIRO [Nachum 18] quickly solves AntMaze, while the baseline used in Fig 1 (HAC, which the paper claims is stronger than HIRO) gails to solve this task. I would be more confident about this paper if it added a comparison with HIRO.\n\nMinor comments:\n* \"fixed and costly hyperparameter\" -- Why is the number of skills \"costly\"?\n* \"Learning backward from the goal\" -- Two other closely related papers are Policy Search by Dynamic Programming [Bagnell 04] and \"Forward-Backward Reinforcement Learning\" [Edwards 18]\n* \"it may choose to ignore learned options\" -- Why should we expect that the optimal policy will use any skills, if it can be represented entirely using primitive actions?\n* [Jinnai 2019] -- This citation is repeated in the references.\n\n----------------- UPDATE AFTER AUTHOR RESPONSE --------------------------\nThanks for the discussion. I think this paper makes a useful contribution to the field, and would be a good ICLR paper. My reason for not voting for \"accept\" (rather than \"weak accept\") is that the experiments are not the most complex, and are all navigation-esque (reacher is effectively a point mass). Could we use this method to solve tasks of significantly greater complexity than those tackled in prior work?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "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_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the problem of autonomous skill discovery by recursively chaining skills backwards from the goal in a deep learning setting, taking the initial conditions of one skill to be the goal of the previous one. The approach is evaluated on several domains and compared against other state of the art algorithms.

This is clearly a novel and interesting paper. Two minor outstanding issues are that the domains are all related to navigation, and it would be interesting to see the approach on other domains, and that the method involves a fair bit of engineering in piecing different methods together. Regardless, this paper should be accepted.
Decision: Accept (Poster)