Learning High-level Representations from Demonstrations
Peter Vrancx Haitham Bou-Ammar
PROWLER.io
{garrett, peter, haitham} @prowler.io

arXiv:1802.06604v3 [cs.AI] 28 Feb 2018

Garrett Andersen

Abstract
Hierarchical learning (HL) is key to solving complex sequential decision problems with long horizons and sparse rewards. It allows learning agents
to break-up large problems into smaller, more manageable subtasks. A common approach to HL, is
to provide the agent with a number of high-level
skills that solve small parts of the overall problem.
A major open question, however, is how to identify a suitable set of reusable skills. We propose
a principled approach that uses human demonstrations to infer a set of subgoals based on changes
in the demonstration dynamics. Using these subgoals, we decompose the learning problem into an
abstract high-level representation and a set of lowlevel subtasks. The abstract description captures
the overall problem structure, while subtasks capture desired skills. We demonstrate that we can
jointly optimize over both levels of learning. We
show that the resulting method significantly outperforms previous baselines on two challenging problems: the Atari 2600 game Montezuma’s Revenge,
and a simulated robotics problem moving the ant
robot through a maze.

1

Introduction

The options framework by [Sutton et al., 1999] has emerged
as the standard to tackle temporal abstractions. Previous
work has shown that the use of options can improve learning efficiency in both planning and on-line learning settings
[Mann et al., 2015; Fruit and Lazaric, 2017]. A key question, however, is how to identify a set of suitable options
for a given problem. Ideally, options should encode reusable
skills that can be combined into policies for solving a wide
range of related problems. A number of authors have recently investigated the problem of finding a suitable set of
options in high-dimensional settings [Vezhnevets et al., 2017;
Bacon et al., 2017; Kulkarni et al., 2016].
Most option-learning approaches rely on heuristics to identify good options. This can mean solving similar problems
and identifying reusable sub-policies [Konidaris and Barto,
2009], identifying key states in problem transition graphs

[McGovern and Barto, 2001; Şimşek et al., 2005], or manually decomposing the problem into a set of subproblems
[Kulkarni et al., 2016]. The issue with these methods is that
they first design a set of options and then attempt to solve
the problem using these options. This requires manual option
design or means that they cannot guarantee that the set of options can efficiently solve the target problem. In contrast, we
propose a top-down approach that first learns the structure of
the problem and then defines the set of options necessary for
solving it. We achieve this by using a small set of human
demonstrations to identify an abstract representation of the
problem.
Our method results in a set of options that can efficiently
solve the overall problem. The option policies themselves can
be learned using basic learners that are not able to solve the
complete problem. We also reduce the problem of learning
a policy over options to a small discrete problem that can be
efficiently solved using basic approaches such as tabular Qlearning. These improvements mean that our method reaches
human-level performance with significantly fewer samples
than previous state-of-the-art methods. We demonstrate such
a reduction in sample complexity on two challenging problems, where current techniques fail. Namely, we show that
our method significantly outperforms state-of-the-art on the
Atari 2600 game of Montezuma’s Revenge and on a simulated ant robot in a maze.

2
2.1

Background
Reinforcement Learning

We assume the standard reinforcement learning setting [Sutton and Barto, 2018] described by an MDP M =
(S, A, p, r, γ), where S is the (possible infinite) set of states, A
the set of (discrete) actions; p : S × A × S → [0, 1] is the transition function that specifies the system dynamics p(s0 |s, a),
denoting the probability of transitioning to state s0 upon taking action a in s; r : S × A → R is the reward function, and
γ a discount factor.
A policy is a probabilistic mapping from states to actions. For a policy π, and MDP transition probabilities
p, let the matrix pπ denote the
induced
P dynamics of the
0
Markov chain: pπ (s, s0 ) =
a∈A π(s, a)p(s |s, a), and
rπ the reward expected for each state under π: rπ (s) =
P
a∈A π(s, a)r(s, a). The value of a policy π denotes the ex-

pected sum ofP
discounted rewards starting from a given state:
∞
v π (s) = Eπ [ k=0 γ k Rt+k+1 | St = s], where we use St
and Rt to denote the state visited and reward received at time
t, respectively. The goal of a reinforcement learner is to identify a policy π ∗ that maximizes the expected discounted reward starting from any state s: π ∗ = arg maxπ v π (s), ∀s ∈
S.

where {Pk }K
k=1 is the Markov transition matrix, and Pk ∈
K
[0, 1] is its k th row. We assume that the continuous latent
state xt ∈ Rd1 follows conditionally linear dynamics, where
the discrete state zt determines the linear dynamical system
used at time t:

2.2

with vt ∼ N (0, Qzt+1 ), for matrices Ak , Qk both ∈ Rd1
and vectors bk ∈ Rd1 for k = 1, 2, . . . , K. Hence, to determine yt ∈ Rd2 we can assume:

The Options Framework

We model high-level skills using the options framework [Sutton et al., 1999]. An option o is a temporally extended action
defined by three components: π o , the option policy that is executed to select actions when the option is invoked, Io , the
initiation set consisting of the states where the option can
be started, and β o (s) → [0, 1], the termination condition,
which returns the probability that the option will terminate
upon reaching state s.
Subgoal Options: We are particularly interested in a special class of options called subgoal options [Precup, 2000],
where the distribution over termination states (referred to as
the subgoal) is independent of the distribution over starting
states from which they are executed. An example of a subgoal option is navigating to a goal location; regardless of the
starting state, activating the option results in the same target
termination condition.
Abstract subgoal options [Konidaris et al., 2014] model
the more general case where executing an option leads to a
subgoal for a subset of the state variables (called the mask),
leaving the rest unchanged. For example, moving a robot’s
arm to a target position will not change the location of the
robot itself. In other words, the state vector is partitioned into
two parts s = [a, b], such that executing o leaves the agent
in s0 = [a, b0 ], where P (b0 ) is independent of the distribution
over starting states.

3

Identifying Subgoals from Demonstration

In this section we describe the approach that we use to build
high-level representations which can be used to guide behavior in large environments with sparse rewards. There are
many existing techniques that have used demonstrations to
bootstrap learning [Schaal, 1997; Ng et al., 2000] with some
success. Rather than directly following demonstrations, the
aim in our framework is to identify a small set of subgoals
which can be used to guide the agent intrinsically. This leads
to learning more robust policies than those obtained by trying to infer policies directly from the demonstrations. In the
following section we introduce our approach for identifying
subgoals.

3.1

Probabilistic Modeling of Trajectories

Our model first maps a continuous set of y1 , . . . , yT observations, to a set of continuous latent states x1 , . . . , xT . Such a
mapping can be achieved using a feature extraction, such as a
convolutional neural network or a variational auto-encoder in
case of image trajectories. We now attempt to detect discrete
switches in the trajectories, by assuming the existence of a
latent state zt ∈ {1, . . . , K} that evolves according to some
Markovian dynamics:
zt+1 |zt , {Pk }K
k=1 ∼ Pzt ,

xt+1 = Azt+1 xt + bzt+1 + vt ,

yt = fzt (xt ) + wt , wt ∼ N (0, Szt ),
for some nonlinear function fzt , e.g., a deconvolutional network. For the linear setting, we can easily specialize the
above definition of yt to:
yt = Czt xt + dzt + wt ,
for Ck ∈ Rd2 ×d1 and dk ∈ Rd2 . As such, the system of
parameters of our model comprise the discrete Markov transition matrix and the library of linear dynamical systems, as
well as the parameters of the nonlinear functions which we
write as:
n
oK
(f )
θ=
Pk , Ak , Qk , bk , θk
.
k=1

3.2

State Space Factorization

Extracting linear dynamics from trajectories may not be feasible in cases where the trajectories are provided only as a
sequence of image observations, i.e. it is very difficult to detect switches in a sequence of images by only reasoning about
their pixels. In this work, we do not focus on the problem of
visual feature extraction, but rather rely on the manually designed set of features also used in [Kulkarni et al., 2016].
Recent work has demonstrated that the Transition State Clustering algorithm we use is quite robust and can be combined
with various pretrained feature extraction pipelines [Murali et
al., 2016].
With extracted features, it is generally possible identify a
factored problem representation. This means that for a set
of high-level features, only a subset will change at any given
time. For instance, robots can first move to a goal before commencing movement of their arms to pick up an object. They
do not move their arms and change their position at the same
time. We utilize this observation to reduce the dimensionality
of subgoal identification, by splitting features into subsets and
detecting subgoals separately within each of these subsets.
This has the additional advantage that the learned subgoals
now become abstract subgoals in the context of the original
problem. This means that we can learn a policy to achieve a
subgoal without affecting the status of unrelated subgoals. In
the next section, we exploit this fact to decompose the learning problem.
More formally, we use the feature trajectories to identify
the set of feature factors F , where each factor f ∈ F represents a set of features that covary. For example, in our Montezuma’s Revenge experiments we extract the agent’s x and y
position, and whether the key has been obtained (these are the
features which are most relevant for determining the agent’s

reward), which leads to two identified factors: the agent’s
(x, y) position, and the status of the key. In the next section
we introduce the method we use to identify subgoals.

3.3

Transition State Clustering

The problem discussed in Section 3.1 is one of detecting
switches in linear dynamical systems. In this paper, we instantiate a solver by relying on the Transition State Clustering (TSC) algorithm [Krishnan et al., 2017]. This algorithm
segments a set of trajectories by first identifying the switchpoints (and corresponding switch-times) corresponding to the
changes in linear dynamics within each trajectory, and then
clustering the switch-points from the entire set of trajectories.
As mentioned in the previous section, we identify the set of
abstract subgoals represented in the demonstrations by running TSC separately for each factor. We slightly modify TSC
by adding one step: for each switch-time discovered by the
first step of TSC, add the switch-time to the other factors in
the same trajectory (with corresponding switch-points). For
example, in Montezuma’s revenge we would add transitions
corresponding to the agent’s last position before obtaining the
key. This modification ensures that the abstract subgoal property holds for the set of discovered subgoals, i.e. that it is
possible to achieve the subgoals without affecting the status
of unrelated subgoals.

4

Problem Decomposition

Our goal in this section is to decompose the MDP into a
set of simpler MDPs. To achieve this, we first define a toplevel abstract MDP [Marthi, 2007]. This abstract description
captures the overall problem structure and uses an abstracted
state space that considers subgoals rather than atomic states.
The actions of the abstract MDP are options that achieve one
of the subgoals. Since we have constrained our subgoals to be
abstract subgoals, we can assume that it is possible to learn
options to achieve each subgoal, without changing state variables that do not relate to the subgoal (i.e. are not in the same
factor). Based on the abstract MDP description, we then define a set of low-level base MDPs. Each of these MDPs describes the learning problem for one of the option policies
used by the abstract MDP. We can then learn a solution in
the abstract MDP to find the sequence of options necessary to
solve the problem, and solve each of the low-level MDPs to
find the option policies.

4.1

Abstract MDP

To define the abstract MDPnwe start from the
o set of subgoals
from Section 3.3: Hf = hf1 , . . . , hf|Hf | , ∀f ∈ F from
demonstration trajectories. The abstract MDP µ describes
the problem using an abstracted state space and temporally
extended actions. We use the subgoals to define the abstract
MDP µ = (Sµ , Aµ , rµ , pµ , γ) as follows:
• The state space of the MDP is the product space of the
abstract subgoals for each of the factors: S µ = Hf1 ×
... × Hfn .
• The action space consists of a set of abstract subgoal
options. One option for each subgoal identified; Aµ =

{ohi | hi ∈ Hf , f ∈ F }. Each option oh is defined
as the tuple oh = (β oh , π oh , Ioh ). The termination function β oh is I{h}, the indicator function for the subgoal h.
The option policy π oh is learned as described below. The
initiation set Ioh is the entire abstract MDP state space
S µ except I{h} (we cannot initiate the option to achieve
subgoal h in states where that subgoal has already been
achieved).
• The reward rµ (sµ , o, sµ 0 ) that the meta-controller observes from executing an option o at starting time t in
abstract state sµ and terminating after T steps in abstract
state sµ 0 , is the expected cumulative discounted environmental reward observed during the execution of o in the
PT
original MDP: rµ (sµ , o, sµ 0 ) = Eπo [ k=0 γ k Rt+k ].

4.2

Base MDPs

For each subgoal option oh defined in the abstract MDP, we
consider a distinct base MDP M oh = (S, A, roh , p, γ). These
MDPs use the same state space S, action space A and transition function p as the original MDP, but replace the reward
function r with a new intrinsic reward roh that defines the
option learning task.
A simple reward function to learn the subgoal options is
the indicator function for the subgoal h. However, this would
lead to a very sparse reward signal, so we use a more informative potential based [Ng et al., 1999] reward signal for each
option, roh (s, a, s0 ), which provides a reward based on the reduction in distance to the goal state plus a large bonus when
the goal state is achieved. This goal-based reward in combination with a discount γ ∈ (0, 1) is sufficient to define
a learning problem where the optimal policy is to reach the
subgoal as quickly as possible.
Other literature has proposed using some combination of
intrinsic and environmental reward when training controllers
for options [Kulkarni et al., 2016]. We do not do this because
one of the primary benefits of learning options is that they
can be reused when solving different tasks within the same
environment, which could involve a different environmental
reward function.

4.3

Integrated architecture

Overall, our goal is to maximize expected reward over
both the meta-policy π µ and the set option policies Ω =
{π oh , ∀oh ∈ Aµ }. Let ξ(oh , s, t) be the event that option
oh is initiated in state s at time t. Then the complete optimization problem is:
" T
#
X
max
max Eπµ ,Ω
γ t Rt | ξ(oh , s, t)
µ
π

Ω

t=0

As mentioned in the previous section, optimizing the intrinsic reward leads to option policies which reach their corresponding subgoals as quickly as possible. Therefore, if the
environmental reward signal only occurs when a subgoal is
reached, then the joint optimization of the meta and low-level
controllers will lead to optimal behavior in the underlying
MDP.
While it is possible so solve each of the MDPs defined
above in isolation and then solve the abstract MDP, this would

result in a very inefficient learning method. In practice, we
consider a setup where both the abstract MDP and base MDPs
are solved jointly. We use the call-and-return option model;
when an option is invoked, the agent chooses low-level actions according to the corresponding option policy until the
option terminates, and another option can be chosen. In our
setting, an option terminates only when its abstract subgoal
is reached (determined by a distance threshold), the option
times out (executes a certain number of steps without achieving its subgoal), or the episode ends (as determined by the
agent’s environment).
Training proceeds as follows: the meta-controller chooses
an option oh to execute from its current abstract state sµ . Actions are then chosen using the policy of option oh , which
is updated with observed transitions (s, a, s0 , roh ). When a
terminal condition is reached, we update the meta-controller
policy with transition (sµ , oh , sµ 0 , rµ (sµ , oh , sµ 0 )), where sµ 0
is the terminal abstract state. See Algorithm 1 for a complete
description of our approach. We note that our approach is
actually agnostic to the learning algorithm used to solve the
base MDPs. In the following section we show that the decomposition allows us to use low-level controllers that are unable
to solve to original full MDP M.
Algorithm 1: Jointly training meta-controller and options
Input : Abstract state space and set of untrained options
while Training is not over do
choose option oh according to π µ ;
t = 0, rµ = 0, sµ = starting abstract state;
while Option or episode not terminal do
choose action a according to π oh ;
observe transition (s, a, s0 , roh , r);
update π oh with (s, a, s0 , roh );
rµ = rµ + γ t r ;
t = t + 1;
sµ 0 = terminal abstract state;
update π µ with (sµ , oh , sµ 0 , rµ );
if episode terminal then
reset environment;

5

Experiments

We evaluate our approach in 2 challenging settings: an Atari
2600 game and a simulated robotics problem.1 In order to
demonstrate the flexibility of the approach, we vary the methods used to solve the low-level skill learning problems; we
use DQN in the Atari domain and PPO in the robotics domain. We show that our problem decomposition allows our
reinforcement learner to efficiently solve the problem, even
though they the basic algorithms are not able to solve the
complete problem. Moreover, we show that the approach significantly outperforms state-of-the-art baselines in terms of
sample complexity and final performance.
1
Videos of the results of training are available at: https://
sites.google.com/view/learningrepresentations

5.1

Montezuma’s Revenge

We first demonstrate our algorithm on the first room within
the Atari 2600 game Montezuma’s Revenge (the environment
is reset whenever the agent opens one of the doors). We
obtained the 10 demonstration trajectories shown in Figure
1. As mentioned in Section 3.2, we use a manually defined
feature extractor to determine the position of the agent and
whether the key was present in the frame. This resulted in
the identification of two factors: one being the (x, y) position
of the agent and one being the status of the key. We run the
TSC algorithm using 10 copies of each of these trajectories to
obtain the position abstract subgoals shown in Figure 1, plus
a key-status abstract subgoal which is not shown.
As discussed in the previous section, we used these discovered abstract subgoals to define low-level controllers and then
jointly learn policies for these low-level controllers along
with the meta-controller policy. In practice, these subgoals
result in the low-level controllers learning to move the agent
to specific locations and to pickup the key.
We use independent Deep Q-Networks (DQNs) [Mnih et
al., 2015] to learn policies for achieving each abstract subgoal2 and tabular Q-learning to train the meta-controller (a
key benefit of our approach is that it leads to very simple and
efficient learning at the meta level). Each option has its own
replay buffer; the agent allocates experiences to the replay
buffer of the option that is currently executing. Additionally,
if the agent enters a terminal state for an option other than the
one it is currently executing, the cumulative experience since
the previous terminal state is added to that option’s replay
buffer.
In Figure 2 we compare our method against basic DQN,
and the hierarchical Deep Q-learning approach proposed by
Kulkarni et al. [Kulkarni et al., 2016]. Kulkarni et al. used
a pretraining step that trains the low-level controllers for 2.5
million steps before moving to the full problem. We show
results for their algorithm both with and without this phase.3
Our approach significantly outperforms these baselines and
attains human-level performance in 2 million training steps.

5.2

Ant Robot in a Maze

The second environment we consider is an ant robot in a
maze, shown in Figure 3. The robot is simulated using the
Roboschool4 physics simulator, and has 8 and 28 dimensional
continuous state and action spaces, respectively. The goal of
the robot is to navigate to the end of the maze shown in Figure 3, which returns an environmental reward of 1. The minimum number of actions required to reach the goal is approximately 1200. While recently proposed algorithms such as
Proximal Policy Optimization (PPO) [Schulman et al., 2017]
have made great progress in basic locomotion tasks, empirical evaluations show that they fail in more complex naviga2
It seems desirable to share features between the networks in
some way, however we found the performance of independent networks to be vastly superior. Other work which uses shared features
also experienced difficulty with training.
3
https://github.com/mrkulk/
hierarchical-deep-RL
4
https://github.com/openai/roboschool

Montezuma Reward Per Episode
Average Reward per Episode

400
350

Subgoal Discovery + Q-learning Meta
Kulkarni Pretrain
Kulkarni No Pretrain
Demonstrations
DQN

300
250
200
150
100
50
0
0

Figure 1: The first room of Montezuma’s Revenge with demonstration trajectories and discovered position abstract subgoals (red dots).
Not shown is the abstract subgoal for obtaining the key.

tion tasks [Duan et al., 2016]. A fundamental issue is that
the algorithms are trained using a potential-based reward signal and a relative state-space, which have difficulty capturing
the hierarchical nature of navigating a maze. Our method can
utilize these algorithms to train the option policies, while still
managing the hierarchical aspect of the task with the metacontroller.
We generated 15 demonstration trajectories (also shown in
Figure 3) by training a sequence of low-level controllers with
predefined subgoals. From the trajectories we identified one
factor which was the (x, y) position of the robot. We ran TSC
to obtain two additional subgoals to the original goal, shown
in Figure 3. The meta-controller was trained using tabular
Q-learning and the low-level controllers were trained using
PPO, with independent policy networks for each option.
In addition to demonstrating learning from scratch, we also
show the effect of injecting prior knowledge into the metalearning process. We consider 2 cases. First, we assume
that the high-level structure of the problem is completely
known (i.e. we know the sequence of subgoals that need to
be achieved). In this case, the meta-controller is fixed and
there is no learning at the meta-level. This setting similar to
the problem considered in the Policy Sketches approach [Andreas et al., 2016]. In the second case, we initialize the metalearner using the demonstration trajectories. We use probabilistic policy-reuse [Fernández and Veloso, 2006] for the
meta-controller, which works by copying the high-level action that was observed in the demonstrations at each subgoal
with some probability.
We compare the resulting four approaches: basic PPO, our
method, our method with probabilistic policy-reuse, and a
fixed meta-controller with the discovered subgoals. Each algorithm had access to the original goal, and all algorithms
besides PPO additionally used the same discovered subgoals.
Figure 4 shows the results of our experiments. Our method
was able to solve the maze, even though basic PPO was never
able to. Additionally, adding probabilistic policy-reuse to our
method significantly increases the learning speed.

1

2

Steps

3

4

5
1e6

Figure 2: Simulation results for the first room of Montezuma’s Revenge. The maximum reward that can be obtained from a single
episode is 400; 100 for obtaining the key and 300 for opening a door.
We compare our method against the performance of the demonstrations, basic DQN, and the Kulkarni approach with and without the
pretraining phase. Our approach significantly outperforms the baselines, achieving human-level performance in 2 million training steps.

Hyperparameter Settings: For both environments, we used
γ = 0.99. For the meta-controllers of both environments,
we used random action probability  = 0.1, and learning
rate 0.2. For probabilistic policy reuse, we linearly decayed
the probability of copying the demonstrations from 0.9 to 0
over 5 million steps. For the Montezuma low level DQNs
we used the OpenAI baselines5 implementation with default
settings except for learning rate 0.001, target network update
frequency 10,000 steps, size of each replay buffer 200,000
steps, and a linearly decayed  from 1 to 0.1 over 75,000 steps
independently for each controller. For the ant robot low-level
controllers, we used the OpenAI baselines implementation of
PPO with the default settings except for independent learning rates for each controller that were linearly decayed from
1 to 0.1 over 2 million steps. We determined that a subgoal
was reached if the agent’s distance was less than 6 and 0.5
for Montezuma and ant, respectively. In both domains, the
low-level controllers time out after 1000 steps.

6

Discussion and related work

Hierarchical approaches have a long history within the reinforcement learning literature. Many approaches have been
proposed to decompose difficult learning problems into a set
of smaller subproblems, see e.g. [Wiering and Schmidhuber, 1997; Precup, 2000; Dietterich, 2000]. In this section we
mainly focus on the options framework as proposed in [Precup, 2000], in particular we look at approaches that combine
high dimensional inputs and hierarchies.
Several papers have recently tried to combine deep reinforcement learning and hierarchical learning. These works
typically focus on integrating temporally extended actions
5

https://github.com/openai/baselines

Ant Maze Reward Per Episode

1.0

Reward Per Episode

0.8
0.6
0.4
Subgoal Discovery + Q-learning Meta
Subgoal Discovery + Fixed Meta
PPO
Subgoal Discovery + Policy-Reuse Meta

0.2
0.0

Figure 3: The ant maze simulation environment with demonstration
trajectories and discovered subgoals (blue dots). The robot’s starting
location is the bottom right of the maze and its goal is to navigate to
the bottom left of the maze to the goal region (red circle).

with deep networks architectures. Kulkarni et al. [Kulkarni et al., 2016] extend the basic DQN algorithm [Mnih et
al., 2015] with a set of heuristic, predefined options. They
show that the resulting method is able to solve the first room
of Montezuma’s Revenge. A key issue with this approach is
that it does not provide a clear way to determine a suitable set
of options. Moreover, it requires a separate pretraining phase
to first learn the option policies before being able to solve the
main problem. In our Montezuma experiments, we provide
the performance of this method as a baseline.
Other methods attempt to learn both options and the policy
over options at the same time. Bacon et al. [Bacon et al.,
2017] introduce the end-to-end Option-Critic architecture.
They formulate a policy gradient method capable of learning the option policies, option terminations and policy-overoptions. A key issue with these and other option-learning
approaches is that they tend to degenerate to trivial solutions that either use a single option policy to solve the entire
problem, or use only primitive actions (i.e. they either never
switch options or switch options on every step). While these
methods are able to the learning problem, they fail to identify meaningful subgoals that lead to useful abstractions and
reusable options. FeUdal Networks [Vezhnevets et al., 2017]
attempt to solve this issue by decoupling the option learning
from the higher-level learning. They propose a 2-level hierarchical network approach where the Manager network sets
goals and intrinsic rewards for the lower level Worker network. The authors demonstrate that the approach is able to
learn meaningful subgoals in the first room of Montezuma’s
Revenge.
Superficially, all the approaches above consider a highlevel/low-level architecture, similar to our meta-level controller choosing sub-goals for the base-level controllers. Our
approach has a number of key advantages, however. First, we
operate in top-down fashion by identifying meaningful subgoals from human demonstrations. This means that we do not
rely on predefined options, but rather can identify the set of
options necessary to solve the problem. Additionally, we can
ensure that these are meaningful options that do not degenerate into trivial solutions. Second, unlike the end-to-end deep

0

1

2

3

4

5

Training Steps

6

7

8
1e7

Figure 4: Simulation results for the ant maze domain. We compared
our subgoal discovery method combined with a Q-learning metacontroller, a probabilistic policy-reuse meta-controller, and a fixed
meta-controller, against PPO. The fixed meta-controller learns the
fastest because it only needs to learn the low-level policies. Probabilistic policy-reuse interpolates between Q-learning and the fixed
meta-controller. The Q-learning and policy-reuse meta-controllers
have worse maximum performance than the fixed meta-controller
because they use  = 0.1 at the meta-level.

hierarchical approaches, our meta-level controller learns on
an abstract level that decouples the low-level representations
(e.g. pixels) from the high-level problem structure. This has
the advantage that the meta-controller does not need to work
with high-dimensional inputs, but can operate on a simplified,
symbolic level. This allows a more efficient solution to the
overall learning problem. Moreover, it means the high-level
controller becomes agnostic to the low-level algorithms used
to solve the base MDPs. Finally, as shown in the Roboschool
experiments, we can combine the low-level skill learning with
various amounts of prior knowledge about the overall problem structure. While not required for successful learning, any
knowledge injected into the process can significantly speed
up learning.

7

Conclusion

In this paper, we proposed a method to use demonstrations in
order to decompose complex learning problems into a set of
simpler subtasks. We achieve this by identifying a set of subgoals and relations between them, and then learn a set of options to solve each of the identified subproblems. We empirically demonstrate that our method significantly increases the
learning speed over previous approaches on two challenging
problems: the Atari 2600 game Montezuma’s Revenge and
a simulated robotics problem moving the ant robot through a
maze.

References
[Andreas et al., 2016] Jacob Andreas, Dan Klein, and
Sergey Levine.
Modular Multitask Reinforcement

Learning with Policy Sketches.
arXiv preprint
arXiv:1611.01796, 2016.
[Bacon et al., 2017] Pierre-Luc Bacon, Jean Harb, and
Doina Precup. The Option-Critic Architecture. In AAAI,
pages 1726–1734, 2017.
[Dietterich, 2000] Thomas G Dietterich. Hierarchical Reinforcement Learning with the MAXQ Value Function
Decomposition. J. Artif. Intell. Res.(JAIR), 13:227–303,
2000.
[Duan et al., 2016] Yan Duan, Xi Chen, Rein Houthooft,
John Schulman, and Pieter Abbeel. Benchmarking deep
reinforcement learning for continuous control. In International Conference on Machine Learning, pages 1329–
1338, 2016.
[Fernández and Veloso, 2006] Fernando Fernández and
Manuela Veloso. Probabilistic Policy Reuse in a Reinforcement Learning Agent. In AAMAS, pages 720–727.
ACM, 2006.
[Fruit and Lazaric, 2017] Ronan Fruit and Alessandro
Lazaric. Exploration–Exploitation in MDPs with Options.
arXiv preprint arXiv:1703.08667, 2017.
[Konidaris and Barto, 2009] G.D. Konidaris and A.G. Barto.
Skill Discovery in Continuous Reinforcement Learning
Domains using Skill Chaining. In NIPS, pages 1015–1023,
2009.
[Konidaris et al., 2014] George Konidaris, Leslie Pack Kaelbling, and Tomas Lozano-Perez. Constructing Symbolic
Representations for High-level Planning. In AAAI, pages
1932–1938, 2014.
[Krishnan et al., 2017] Sanjay Krishnan, Animesh Garg,
Sachin Patil, Colin Lea, Gregory Hager, Pieter Abbeel,
and Ken Goldberg. Transition State Clustering: Unsupervised Surgical Trajectory Segmentation for Robot Learning. The International Journal of Robotics Research,
36(13-14):1595–1618, 2017.
[Kulkarni et al., 2016] Tejas
D
Kulkarni,
Karthik
Narasimhan, Ardavan Saeedi, and Josh Tenenbaum.
Hierarchical Deep Reinforcement Learning: Integrating
Temporal Abstraction and Intrinsic Motivation. In NIPS,
pages 3675–3683, 2016.
[Mann et al., 2015] Timothy Arthur Mann, Shie Mannor,
and Doina Precup. Approximate value iteration with
temporally extended actions. J. Artif. Intell. Res.(JAIR),
53:375–438, 2015.
[Marthi, 2007] Bhaskara Marthi. Automatic Shaping and
Decomposition of Reward Functions. In ICML, pages
601–608. ACM, 2007.
[McGovern and Barto, 2001] Amy McGovern and Andrew G Barto. Automatic Discovery of Subgoals in
Reinforcement Learning using Diverse Density. Computer Science Department Faculty Publication Series,
page 8, 2001.
[Mnih et al., 2015] Volodymyr Mnih, Koray Kavukcuoglu,
David Silver, Andrei A Rusu, Joel Veness, Marc 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–
533, 2015.
[Murali et al., 2016] Adithyavairavan Murali, Animesh
Garg, Sanjay Krishnan, Florian T Pokorny, Pieter Abbeel,
Trevor Darrell, and Ken Goldberg. TSC-DL: Unsupervised Trajectory Segmentation of Multi-Modal Surgical
Demonstrations with Deep Learning. In ICRA, pages
4150–4157. IEEE, 2016.
[Ng et al., 1999] Andrew Y Ng, Daishi Harada, and Stuart
Russell. Policy Invariance under Reward Transformations:
Theory and Application to Reward Shaping. In ICML, volume 99, pages 278–287, 1999.
[Ng et al., 2000] Andrew Y Ng, Stuart J Russell, et al. Algorithms for Inverse Reinforcement Learning. In ICML,
pages 663–670, 2000.
[Precup, 2000] D. Precup. Temporal Abstraction in Reinforcement Learning. PhD thesis, Department of Computer
Science, University of Massachusetts Amherst, 2000.
[Schaal, 1997] Stefan Schaal. Learning from Demonstration.
In NIPS, pages 1040–1046, 1997.
[Schulman et al., 2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy Optimization Algorithms. arXiv preprint
arXiv:1707.06347, 2017.
[Şimşek et al., 2005] Özgür Şimşek, Alicia P Wolfe, and Andrew G Barto. Identifying useful subgoals in reinforcement learning by local graph partitioning. In ICML, pages
816–823. ACM, 2005.
[Sutton and Barto, 2018] Richard S Sutton and Andrew G
Barto. Introduction to reinforcement learning (second edition), volume 135. MIT Press Cambridge, 2018.
[Sutton et al., 1999] R.S. Sutton, D. Precup, and S.P. Singh.
Between MDPs and semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning. Artificial
Intelligence, 112(1-2):181–211, 1999.
[Vezhnevets et al., 2017] Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal Networks for Hierarchical Reinforcement Learning. arXiv
preprint arXiv:1703.01161, 2017.
[Wiering and Schmidhuber, 1997] Marco Wiering and
Jürgen Schmidhuber. Hq-learning. Adaptive Behavior,
6(2):219–246, 1997.

