Common approaches to Reinforcement Learning (RL) are seriously challenged by large-scale applications involving huge state spaces and sparse delayed reward feedback. Hierarchical Reinforcement Learning (HRL) methods attempt to address this scalability issue by learning action selection policies at multiple levels of temporal abstraction. Abstraction can be had by identifying a relatively small set of states that are likely to be useful as subgoals, in concert with the learning of corresponding skill policies to achieve those subgoals. Many approaches to subgoal discovery in HRL depend on the analysis of a model of the environment, but the need to learn such a model introduces its own problems of scale. Once subgoals are identified, skills may be learned through intrinsic motivation, introducing an internal reward signal marking subgoal attainment. In this paper, we present a novel modelfree method for subgoal discovery using incremental unsupervised learning over a small memory of the most recent experiences (trajectories) of the agent. When combined with an intrinsic motivation learning mechanism, this method learns both subgoals and skills, based on experiences in the environment. Thus, we offer an original approach to HRL that does not require the acquisition of a model of the environment, suitable for large-scale applications. We demonstrate the efficiency of our method on two RL problems with sparse delayed feedback: a variant of the rooms environment and the first screen of the ATARI 2600 Montezuma's Revenge game.
The reinforcement learning problem suffers from serious
scaling issues. Hierarchical Reinforcement Learning (HRL)
is an important computational approach intended to tackle
problems of scale by learning to operate over different levels
of temporal abstraction
A number of approaches to HRL have been suggested. One approach focuses on action sequences, subpolicies, or “options” that appear repeatedly during the learning of a set of tasks. Such frequently reused subpolicies can be abstracted into skills that can be treated as individual actions at a higher level of abstraction. A somewhat different approach to temporal abstraction involves identifying a set of states that make for useful subgoals. This introduces a major open problem in HRL: that of subgoal discovery.
A variety of researchers have proposed approaches
to identifying useful subpolicies and reifying them as
skills
Once useful subgoals are discovered, an HRL agent
should be able to learn the skills to attain those subgoals
through the use of intrinsic motivation — artificially
rewarding the agent for attaining selected subgoals. The nature
and origin of “good” intrinsic reward functions is an open
question in reinforcement learning, however, and a number
of approaches have been proposed.
Recently,
It is important to note that model-free HRL, which does
not require a model of the environment, still often requires
the learning of useful internal representations of states.
When learning the value function using a nonlinear
function approximator, such as a deep neural network,
relevant features of states must be extracted in order to
support generalization at scale. A number of methods have
been explored for learning such internal representations
during model-free reinforcement learning
In this paper, we seek to address major open problems in the integration of internal representation learning, temporal abstraction, automatic subgoal discovery, and intrinsic motivation learning, all within the model-free HRL framework. We propose and implement efficient and general methods for subgoal discovery using unsupervised learning and anomaly (outlier) detection. These methods do not require information beyond that which is typically collected by the agent during model-free reinforcement learning, such as a small memory of recent experiences (agent trajectories). Our methods are fundamentally constrained in three ways, by design. First, we remain faithful to a model-free reinforcement learning framework, eschewing any approach that requires the learning or use of an environment model. Second, we are devoted to integrating subgoal discovery with intrinsic motivation learning. Specifically, we conjecture that intrinsic motivation learning can increase appropriate state space coverage, supporting more efficient subgoal discovery. Lastly, we focus on subgoal discovery algorithms that are likely to scale to large reinforcement learning tasks. The result is a unified model-free HRL algorithm that incorporates the learning of useful internal representations of states, automatic subgoal discovery, intrinsic motivation learning of skills, and the learning of subgoal selection by a “metacontroller”. We demonstrate the effectiveness of this algorithm by applying it to a variant of the rooms task (illustrated in Figure 2(a)), as well as the initial screen of the ATARI 2600 game called Montezuma’s Revenge (illustrated in Figure 3(a)).
The Reinforcement Learning (RL) problem is learning
through interaction with an environment
Q(s; a; w) 2i :
In Hierarchical Reinforcement Learning (HRL), a central
goal is to support the learning of representations at multiple
levels of abstraction. As a simple example, consider the task
of navigation in the 4-room environment with a key and a
lock in Figure 2(a). This is a variant of the rooms task
Our intuition, shared with other researchers, is that hierarchies of abstraction will be critical for successfully solving problems of this kind. To be successful, the agent should represent knowledge at multiple levels of spatial and temporal abstraction. Appropriate abstraction can be had by identifying a relatively small set of states that are likely to be useful as subgoals and jointly learning the corresponding skills of achieving these subgoals, using intrinsic motivation.
In this section, we introduce a unified method for modelfree HRL. The major components of our framework, and the information flow between them, are sketched in Figure 1. Before describing the unified method, we introduce the various components of our framework.
Inspired by
Y
Q(s; g; W ) ; (1) where G = Ptt0+=Tt t0 trt0 is the accumulated external reward (return) between the selection of consecutive subgoals. The target value for the expected return at the time that the meta-controller selected subgoal g is Y = G + maxg0 Q(s0; g0; W ). The controller improves its subpolicy, (ajs; g), by learning its value function, q(s; g; a; w), over the set of recorded transition experiences. The controller updates its value function approximator parameters, w, so as to minimize its loss function:
Li(w) , E(s;g;a;r~;s0) D1 y q(s; g; a; w) 2 ; (2) where y = r~ + max0a q(s0; g; a0; w) is the target expected intrinsic return value. Intrinsic motivation learning is the core idea behind the learning of value functions in the meta-controller and the controller. In some tasks with sparse delayed feedback, a standard RL agent cannot effectively explore the state space so as to have a sufficient number of rewarding experiences to learn how to maximize rewards. In contrast, the intrinsic critic in our HRL framework can send much more regular feedback to the controller, since it is based on attaining subgoals, rather than ultimate goals. As an example, our implementation typically awards an intrinsic reward of +1 when the agent attains the current subgoal, g, and 1 for any other state transition. Successfully solving a difficult task not only depends on such an intrinsic motivation learning mechanism, but also on the meta-controller’s ability to learn how to choose the right subgoal for any given state, s, from a set of candidate subgoals. Indeed, identifying a good set of candidate subgoals is an additional prerequisite for success, and it is discussed next.
The performance of the meta-controller/controller framework depends critically on selecting good candidate subgoals for the meta-controller to consider.
What is a subgoal? In our framework, a subgoal is a state, or a set of related states, that satisfies at least one of these conditions: 1. It is close (in terms of actions) to a rewarding state. For example, in the rooms task in Figure 2(a), the key and lock are rewarding states. 2. It represents a set of states, at least some of which tend to be along a state transition path to a rewarding state. For example, in the rooms task, the red room should be visited to move from the purple room to the blue room in order to pick up the key. Thus any state in the red room is a reasonably good subgoal for an agent currently in the purple room. Similarly, the states in the blue room are all reasonably good subgoals for an agent currently in the red room. The doorways between rooms can also be considered as good subgoals, since entering these states allows for the transition to a set of states that may be closer to rewarding states.
Our strategy involves leveraging the set of recent transition experiences that must be recorded for value function learning, regardless. Unsupervised learning methods applied to sets of experiences can be used to identify sets of states that may be good subgoal candidates. We focus specifically on two kinds of analysis that can be performed on the set of transition experiences. We hypothesize that good subgoals might be found by (1) attending to the states associated with anomalous transition experiences and (2) clustering experiences based on a similarity measure and collecting the set of associated states into a potential subgoal. Thus, our proposed method merges anomaly (outlier) detection with the K-means clustering of experiences.
Anomaly Detection The anomaly (outlier) detection process identifies states associated with experiences that differ significantly from the others. In the context of subgoal discovery, a relevant anomalous experience would be one that includes a substantial positive reward in an environment in which reward is sparse. We propose that the states associated with these experiences make for good candidate subgoals. For example, in the rooms task, transitions that arrive at the key or the lock are quite dissimilar to most transitions, due to the large positive reward that is received at that point.
Since the goal of RL is maximizing accumulated
(discounted) reward, these anomalous experiences, involving
large rewards, are ideal as subgoal candidates. (Experiences
involving large negative rewards are also anomalous, but
make for poor subgoals. As long as these sorts of
anomalies do not greatly outnumber others, we expect that the
meta-controller can efficiently learn to avoid poor subgoal
choices.) Large changes in state features can also be marked
as anomalous. In some computer games, like Montezuma’s
Revenge, each screen represents a room, and the screen
changes quickly when the agent moves from one room to
another. This produces a large distance between two
consecutive states. Such a transition can be recognized simply
by the large instantaneous change in state features,
marking the associated states as reasonable candidate subgoals.
There is a large literature on anomaly detection
K-Means Clustering The idea behind using a clustering algorithm is “spatial” state space abstraction and dimensionality reduction with regard to the internal representations of states. If a collection of transition experiences are very similar to each other, this might suggest that the associated states are all roughly equally good as subgoals. Thus, rather than considering all of those states, the learning process might be made faster by considering a representative state (or smaller set of states), such as the centroid of a cluster, as a subgoal. Furthermore, using a simple clustering technique like Kmeans clustering to find a small number of centroids in the space of experiences is likely to produce centroid subgoals that are dissimilar from each other. Since rewards are sparse, this dissimilarity will be dominated by state features. For example, in the rooms task, the centroids of K-means clusters, with K = 4, lie close to the geometric center of each room, with the states within each room coming to belong to the corresponding subgoal’s cluster. In this way, the clustering of transition experiences can approximately produce a coarser representation of state space, in this case replacing the fine grained “grid square location” with the coarser “room location”.
These conceptual components can be unified into a single model-free HRL framework. The major components of this framework, and the information flow between these components, are schematically displayed in Figure 1. At time t, the meta-controller observes the state, s = st, from the environment and chooses a subgoal, g = gt, either from the discovered subgoals or from a random set of states (to promote exploration). The controller receives an input tuple, (s; g), and is expected to learn to implement a subpolicy, (ajs; g), that solves the subtask of reaching from s to g. The controller selects an action, a, based on its policy, in our case directly derived from its value function, q(s; g; a; w). After one step, the environment updates the state to s0 and sends a reward r. The transition experience (s; g; a; r~; s0) is then stored in the experience memory for the controller, D1. If the internal critic detects that the resulting state, s0, is the current goal, g, the experience (st; g; G; st0 ) is stored in the meta-controller experience memory, D2, where st is the state that prompted the selection of the current subgoal, and st0 = st+T is the state when the meta-controller assigns the next subgoal, g0 = gt0 . The experience memory sets are typically used to train the value function approximators for the meta-controller and the controller by sampling a random minibatch of recent experiences. The subgoal discovery mechanism exploits the underlying structure in the experience memory sets using unsupervised anomaly detection and experience clustering. A detailed description of this process is outlined in Algorithm 1.
Algorithm 1 Unified Model-Free HRL Algorithm Initialize discovered subgoals set G ; Initialize experience memories D, D1 and D2 Initialize parameters w and W randomly Inputs: learning rate , exploration rate Choose Phase I or Phase II for episode = 1; : : : ; M do
Initialize state s0 2 S, s s0 Initialize episode return G 0 if Phase I of learning then
Choose a subgoal g randomly form S else if Phase II of learning then
g EPSILON-GREEDY(Q(s; G; W); ) end if
repeat for each step t = 1; : : : ; T compute q(s; g; a; w) a EPSILON-GREEDY(q(s; g; A; w); ) Take action a, observe s0 and external reward r Compute intrinsic reward r~ from internal critic Store (s; g; a; r~; s0) to D1 Store (s; a; r; s0) to D Sample J1 D1 and compute rL Update w; w w rL if Phase II of learning then
Sample J2 D2 and compute rL
Update W; W W rL end if s s0; G G + r
Decay exploration rate until s is terminal or subgoal g is attained Store (s0; g; G; s0) to D2 if Phase I of training then
Run Unsupervised Subgoal Discovery end if end for ====================================
for each e = (s; a; r; s0) stored in D do if experience e is an outlier (anomaly) then
Store s0 to the subgoals set G
Remove e from D end if end for Fit a K-means Clustering Algorithm on D using previous centroids as initial points Store the updated centroids to the subgoals set G
We conducted simulation experiments in order to investigate the ability of our unsupervised subgoal discovery method to discover useful subgoals, as well as the efficiency of our unified model-free hierarchical reinforcement learning framework. The simulations were conducted in two environments with sparse delayed feedback: a variant of the rooms task, shown in Figure 2(a), and the “Montezumas Revenge” game, shown in Figure 3(a).
In these simulations, learning occurred in two phases. In Phase I of learning, the controller learned how to navigate in the state space, from any arbitrary state to any other state, using intrinsic motivation learning. The agent’s trajectories, (s; a; r; s0), during this pretraining phase were stored in D, and our unsupervised subgoal discovery method extracted the structure of D by performing K-means clustering and anomaly detection. The discovered subgoals were stored in G. In Phase II of learning, the meta-controller learned meta-policies over G, and the controller had opportunities to refine its ability to navigate from any arbitrary state, s, to any assigned subgoal, g 2 G. We separated the learning process into phases for two reasons: (1) to focus on the knowledge extracted from game environments using our approach to unsupervised subgoal discovery during intrinsic motivation learning; (2) to avoid complications that arise in meta-controller learning when the set of subgoals, G, is not fixed. Integrating these phases into a uniform and incremental HRL process is a central apsect of our future work.
Consider the task of navigation in the 4-room environment
with a key and a lock, as shown in Figure 2(a). This task
was inspired by the rooms environment introduced by
We first examined the unsupervised subgoal discovery algorithm over the course of a random walk. The agent was allowed to explore the 4-room environment for 10,000 episodes. Each episode ended either when the task was completed or after reaching a maximum time step limit of 200. The agent’s experiences, e = (s; a; r; s0), were collected in an experience memory, D. The stream of external rewards for each transition was used to detect anomalous subgoals (Figure 2(c)). We applied a heuristic anomaly detection method for the streaming rewards that was able to differentiate between the rare large positive rewards and the regular small ones. These peaks, as shown in Figure 2(c), corresponded to the experiences in which the key was reached (r = +10) or the experience of reaching the lock after obtaining the key.
We also applied a K-means clustering algorithm to the experience memory. (See Algorithm 1.) The centroids of the 50 40 n ru30 t e R e20 d o s ip10 E 0 (a) Our Unified Model-Free HRL Method
Regular RL 40000 60000 Training steps
(e) 0 20000 80000 100000 0 20000 80000 100000 K-means clusters (with K = 4) are plotted in Figure 2(b). We found these centroids to roughly correspond to the centers of the rooms. (We experimented with K = 8 and saw equally useful clusters, with each room containing two cluster centroids. We will investigate methods for choosing K in future work.) The clusters, along with the anomalous states, were collected into the set of subgoals.
Phase I learning consisted of 100,000 episodes. Value function approximators were implemented as multi-layer artificial neural networks augmented to encourage the learn40000 60000 Training steps (d) Our Unified Model-Free HRL Method
Regular RL
40000 60000
Training steps
(f)
ing of sparse internal representations of states
Phase II learning involved training both the metacontroller and the controller, together, using the discovered subgoals, G. (See Algorithm 1.) The subgoal set regularly came to contain a total of 6 subgoals: 2 anomalous ones and 4 centroids. The system was trained for 100,000 episodes. The meta-controller’s value function approximation network consisted of two layers. The first layer, was a one-hot encoding of the conjunction of the current subgoal and the state, computed by converting the state to the index of the corresponding subgoal. This was connected directly to the output layer. The average return, over 10 consecutive episodes, is shown in Figure 2(e). The agent very quickly converged on the optimal policies and collected the maximum reward (+50). The high exploration rate, = 0:2, caused high stochasticity, but the meta-controller and controller could robustly solve the task on more than 90% of the episodes very early in training. After about 40,000 episodes, the success rate was 100%, as shown in Figure 2(f).
We compared the learning efficiency of our unified HRL
method with the performance resulting from training a value
approximation network with a regular, non-hierarchical, RL
algorithm, TD SARSA
It is worth noting that this task involves a partially observable Markov decision process (POMDP), because information about whether or not the agent has the key is not visible in the state. This hidden state information poses a serious problem for standard RL algorithms, but our HRL agent was able to overcome this obstacle. Through Phase II learning, the hidden information became implicit in the selected subgoal, with the meta-controller changing the current subgoal once the key is obtained. In this way, our HRL framework is able to succeed in task environments that are effectively outside of the scope of standard RL approaches.
We applied our HRL approach to the first room of the game Montezuma’s Revenge. (See Figure 3(a).) The game is wellknown as a challenge for RL agents because it requires solving many subtasks while avoiding traps. Having only sparse delayed reward feedback to drive learning makes this RL problem extremely difficult. The agent should learn to navigate the man in red to the key by: (1) climbing the middle ladder (2) climbing the bottom right ladder (3) climbing the bottom left ladder (4) moving to the key. After picking up the key (r = +100), the agent should return back, reversing the previous action sequence, and attempt to reach the door (r = +300) and exit the room. The moving skull at the bottom of the screen, which ends an episode upon contact, makes obtaining the key extremely difficult. The episode also ends unsuccessfully if the man falls off of a platform.
DeepMind’s Deep Q-Learning (DQN) algorithm
In this problem, the agent requires the skills arising from
intrinsic motivation learning in order to explore the
environment in a more efficient way
We used a variant of the DQN deep Convolutional Neural Network (CNN) architecture (Figure 3(b)) for approximation of the controller’s value function, q(s; g; a; w). The input to the controller network consisted of four consecutive frames of size 84 84, encoding the state, s, and an additional frame binary mask encoding the subgoal, g. The concatenated state and subgoal frames were passed to the network, and the controller then selected one of 18 different joystick actions based on a policy derived from q(s; g; a; w).
During intrinsic motivation learning, the recent
experiences were saved in an experience memory, D, with a size
of 106. In order to support comparison to previously
published results, we used the same learning parameters of
DeepMind’s DQN
Our Unified Model-Free HRL Method
DeepMind DQN Algorithm
Our Unified Model-Free HRL Method
DeepMind DQN Algorithm
(e)
0
500000
2000000
2500000
0
500000
2000000
2500000
of = 0:99. During Phase I learning, we trained the
network for a total of 2:5 106 time steps. The exploration
probability parameter, , decreased from 1:0 to 0:1 in the
first million steps and remained fixed after that. After
every 100; 000 time steps, we applied our unsupervised
subgoal discovery method to the contents of the experience
memory in order to find new subgoals, both anomalies and
centroids, using K-means clustering with K = 10. As
shown in Figure 3(d), the unsupervised learning algorithm
managed to discover the location of the key and the doors
in this way. It also identified useful objects such as
ladders, platforms, and the rope. In Phase II, we trained the
meta-controller and the controller jointly. We used an
architecture based on the DQN CNN
We have proposed and demonstrated a novel model-free HRL method for subgoal discovery using unsupervised learning over a small memory of the most recent experiences (trajectories) of the agent. When combined with an intrinsic motivation learning mechanism, this method learns subgoals and skills together, based on experiences in the environment. Thus, we offer an HRL approach that does not require a model of the environment, making it suitable for larger-scale applications.
We acknowledge the valuable comments of the anonymous reviewers of this paper. The computations are conducted on the MERCED cluster at UC Merced, which was funded by National Science Foundation Grant No. ACI-1429783.