Year: 2018

Abstract:
Exploration is a well known challenge in Reinforcement Learning. One principled way of overcoming this challenge is to find a hierarchical abstraction of the base problem and explore at these higher levels, rather than in the space of primitives. However, discovering a deep abstraction autonomously remains a largely unsolved problem, with practitioners typically hand-crafting these hierarchical control architectures. Recent work with multitask linear Markov decision processes, allows for the autonomous discovery of deep hierarchical abstractions, but operates exclusively in the offline setting. By extending this work, we develop an agent that is capable of incrementally growing a hierarchical representation, and using its experience to date to improve exploration.

text: Exploration is a well known challenge in Reinforcement Learning. One principled way of overcoming this challenge is to find a hierarchical abstraction of the base problem and explore at these higher levels, rather than in the space of primitives. However, discovering a deep abstraction autonomously remains a largely unsolved problem, with practitioners typically hand-crafting these hierarchical control architectures. Recent work with multitask linear Markov decision processes, allows for the autonomous discovery of deep hierarchical abstractions, but operates exclusively in the offline setting. By extending this work, we develop an agent that is capable of incrementally growing a hierarchical representation, and using its experience to date to improve exploration.

heading: 1 INTRODUCTION
text: The exploration-exploitation trade-off is much studied in the Reinforcement Learning (RL) literature. A central question regards how to explore efficiently in large state spaces. In this direction, a number of classical exploration ideas have emerged for problems with enumerable state spaces which could be represented in tabular format Roger (1999). In fact, approximately optimal exploration is achievable in these settings Kolter & Ng (2009). When the state space is large and neural networks are used to approximate the value function, an additional suite of techniques exist to promote exploration Stadie et al. (2015); Tang et al. (2016); Plappert et al. (2017).
An always good-in-principle idea is to first construct an abstract representation of the problem, and explore at this higher level rather than in the space of primitives. This might correspond to a person exploring a house by choosing to explore at the level of rooms, rather than exploring exclusively inch-by-inch. Intuitively, this suggests that exploring a large state space may be best conducted at different levels of granularity, corresponding to different layers of abstraction. The challenge here is that finding suitable abstractions autonomously is, in general, largely an unsolved problem, although some progress has been made in this direction Vigorito & Barto (2010); Bacon & Precup (2015). Additionally, while further layers of abstraction would enhance the agent’s ability to explore at these various scales, many architectures in the hierarchical reinforcement learning literature focus on just two layers of control, e.g., the options framework Sutton & Singh (2015); Machado et al. (2018).
Recent work using the linearly-solvable Markov decision process (LMDP) framework provides a mechanism for autonomously learning deeper control hierarchies Saxe et al. (2017). However, this method operates in the off-line setting. By incorporating ideas from incremental learning on static classification tasks, we develop an agent that is able to both build, and utilize, a hierarchical architecture fully online. Our agent operates by periodically increasing the capacity of its hierarchical representation, and allowing subsequent experience to fine-tune the new weights. In so much as an analogy to the well-known options framework is helpful, the new approach can be thought of as periodically adding a randomly initialized options policy, and allowing subsequent experience to adjust all of the available options in light of the new-found capacity.
We demonstrate that learning the hierarchical representation online is not only possible, but can actually aid exploration when coupled with a simple count-based exploration boost.

heading: 2 PRELIMINARIES
text: The LMDP framework Todorov (2006); Kappen (2005) considers a special class of MDPs for which the Bellman optimality condition becomes linear in the exponentiated cost-to-go. In this formalism, the MDP is defined as a three-tuple L = 〈S, Pπ̄, R〉, where S = [1, . . . , N ] is a set of states, and Pπ̄ : S × S → [0, 1] is the so-called passive transition probability between states. This transition probability is defined as the resultant transition probability under some reference policy π̄. And R : S → R is the expected instantaneous reward. The reference policy π̄ is typically taken to be the uniformly random policy, corresponding to the entropy-regularized RL problem Schulman et al. (2017); Haarnoja et al. (2017). Intuitively, the passive dynamics can be thought of as the diffuse process followed by the agent in the absence of a specified control.
In this setting, the action taken by the agent is a full distribution over next states a(·|s) ∈ RN , which acts to shift the passive transition probability by redistributing probability mass; making preferred transitions more likely, and disfavoured transitions less likely. A control cost is associated with this choice: actions corresponding to distributions over next states that are very different from the passive transition probability distribution are expensive, while those that are similar are cheap. In this way the problem is said to be regularized by the reference policy. Intuitively, this can be thought of as specifying an intrinsic preference for energy-efficient actions, by regularizing the controlled transition probabilities towards the reference policy. The LMDP has rewards Ri(s) for each interior state, and Rb(s) for each boundary state in the finite exit formulation. The LMDP can be solved by finding the so-called desirability function z(s) = eV (s), specified in terms of the state value function. The optimal policy can then be computed in closed form as:
a∗(s′|s) = Pπ̄(s ′|s)z(s′) G[z](s) , (1)
where the normalizing constant G[z](s) = ∑ s′ Pπ̄(s
′|s)z(s′) Todorov (2009). Intuitively, the hard maximization of standard MDP has been replaced by a soft maximization log( ∑ exp(·)), and the continuous action space enables closed form computation of the optimal policy.
While in principle any reference policy could be used (perhaps coming from an expert demonstration), entropy regularization is a common choice, and has been shown to recover more adaptive, multi-modal policies in large domains Haarnoja et al. (2017). As an illustrative example, consider a robot whose task it is to navigate around some object. Suppose that two equally valid solutions exist, corresponding to a trajectory around the obstacle to the left, and another to the right. Where a standard DQN-style agent would collapse on one path or the other, in the entropy regularized problem the optimal solution is a stochastic policy in which the agent chooses which path to take at random. Suppose that, after training, the path to the left was blocked-off by a new obstacle. While the DQN-style agent would struggle to recover from its firm commitment to the left path, the entropy-regularized agent is able to adapt easily.
It is worth noting that unlike the standard MDP formulation, the optimal policies uncovered in the LMDP formulation are stochastic. These have equivalent interpretations as being stochastic policies over deterministic actions, or as deterministic policies over stochastic actions. Explicitly, although the LMDP formalism transforms away the notion of discrete actions, the optimal solutions to LMDP problems may always be realized in terms of stochastic policies over the discrete actions of the more familiar MDP formulation.

heading: 2.1 THE MULTITASK LMDP
text: The linearity of the Bellman optimality condition implies a natural form of policy composition. Suppose that we solve two LMDPs L1 = 〈S, Pπ̄, [Ri, R1b ]〉 and L2 = 〈S, Pπ̄, [Ri, R2b ]〉, which operate in the same state and action space, but differ in their instantaneous boundary rewards, and obtain the corresponding optimal policies z1 and z2. If we then encounter a third LMDP L3 = 〈S, Pπ̄, [Ri, R3b ]〉 such that if r3b = αr1b + βr2b , then the corresponding optimal policy is immediately realizable as z3 = αz1 + βz2 Todorov (2009). Importantly, no further learning need take place.
This property was exploited in Saxe et al. (2017), to develop a powerful multitasking framework. In this setting, an agent faces a number of tasks which have the same state and action spaces, but differ
in their boundary reward functions. The multitask LMDP (MLMDP) operates by learning a set of Nt tasks each defined as an LMDP Lt = 〈S, P,R = [ri, rtb]〉, t = 1, · · · , Nt. This set of LMDPs represents an ensemble of tasks with different ultimate goals. These tasks may then be collected into a task basis (or task library). By utilizing this library of pre-learned policies, when the agent encounters a new task, it is able to immediately obtain the optimal policy by representing the policy for the new task as a weighted blend of policies from the task library. If the new task is not exactly realizable as a linear combination of tasks from the library, significant jump-start performance may nevertheless be obtained by initializing the new task as an approximate blend of library tasks Saxe et al. (2017). A particular instantiation of a set of tasks is referred to as being a task ‘module’.

heading: 2.2 THE HIERARCHICAL MLMDP
text: Hierarchical RL holds the promise of dramatically simplifying the learning problem by abstracting away the finer details of the base problem, and instead solving a consistent, but simpler, higher layer problem. By repeatedly applying this abstraction procedure, an agent may in principle overcome the curse of dimensionality which typically occurs as the size of the state and action spaces increase. Of course, this simply replaces one difficulty with another: instead of directly solving the original problem, we need to solve the new problem of how to uncover a suitable abstraction in the first place. Typically this abstraction is hand-crafted by a designer, however a number of techniques have been proposed for autonomously uncovering useful abstractions under the banner of “subtask/options discovery” Konidaris (2016); Stolle & Precup (2002); Bonarini et al. (2006).
These discovery procedures are themselves limited in that they uncover only a single layer of abstraction. It is often not at all clear how these procedure might be recursed to uncover deep representations akin to ‘options-over-options’ (but see Vigorito & Barto (2010)). Furthermore, abstractions that involve temporally extended actions often suffer from the fact that they artificially inflate the action space. This results in an exponential increase in the number of parameters to be learned, and is often crippling. However, by leveraging the compositionality of the MLMDP, a simple recursive scheme was described in Saxe et al. (2017) for constructing arbitrarily deep hierarchical abstractions. This is achieved by stacking the multitask module discussed above (Saxe et al., 2017). The stacking is realized by iteratively constructing higher order MLMDPs in which higher levels select the instantaneous reward structure that defines the current task for lower levels in a feudal-like architecture Dayan & Hinton (1993); Vezhnevets et al. (2017).
This recursive procedure is carried out by firstly augmenting the layer l state space S̃l = Sl ∪ Slt with a set of Nt terminal boundary states Slt called subtask states. Transitioning into a subtask state corresponds to a decision by the layer l MLMDP to access the next level of the hierarchy. The transitions into the subtask states are governed by a new N lt -by-N l i passive dynamics matrix P l t . In the augmented MLMDP, the full passive dynamics then become P̃ l = [P li ;P l b ;P l t ], corresponding to transitions to interior states, boundary states, and subtask states respectively. The higher layer MLMDP is then defined by specifying transitions dynamics, [P l+1i ;P l+1 b ] and reward function [r l+1 i ], such that the higher layer MLMDP is consistent with the lower layer MLMDP (Saxe et al., 2017), and solving the easier higher layer problem ultimately solves the base problem too. An example of this hierarchical scheme is shown in Fig.(1). Notice that the new subtask states form a separate bona fide LMDP Ll+1 = 〈St, [P l+1i , P l+1 b ], [R l+1 i , Rb]〉. This forms the basis for subsequent recursion.
Solving the higher layer MLMDP will yield an optimal action al+1(·|s). This action shifts the passive transition dynamics making some transitions more likely, indicating that they are desirable for the current task, and others less likely, indicating that they should be avoided for the current task. The instantaneous rewards for the lower layer are then set to be proportional to the difference between the controlled and passive dynamic, rlt ∝ al+1i (·|s)− p l+1 i (·|s).
In order to stack these modules, the subtask transition matrix P lt must be defined at each layer. It was shown in Earle et al. (2018) that a suitable P lt could be recovered autonomously by finding a low-rank approximation to the full task basis ZlRN×N at each layer. Intuitively, this exploits the fact that there is often significant additional structure in the policies that make up the task basis. By way of example, suppose that we are in a 4-rooms domain, and the task basis is comprised of a policy to get to each individual state. A low-rank approximation of this basis should uncover the fact that the polices are grouped by the room contains their goal state. Since the task basis Zl is the
Base LMDP Higher layer LMDP
Augmented LMDP
i ]
are suitably specified. The resulting construction is itself an LMDP, forming the basis for recursion (RIGHT).
exponentiated cost-to-go for the composite policies, and are therefore strictly non-negative, Earle et al. (2018) propose to utilize non-negative matrix factorization to uncover the low-rank approximation as Zl ≈ DlW l, and set P lt = αDl. This allowing for the fully autonomous discovery of deep control hierarchies. The method proceeds recursively by first constructing a task basis Zl, then finding a low rank approximation of that basis and assigning P lt = αD
l, and finally computing the transition dynamics P l+1 and reward structure Rl+1 for the abstracted MLMDP.
Howver, a key limitation of the method presented in Earle et al. (2018) is that the computation of the hierarchy happens in an off-line setting. While the method is therefore applicable to probabilistic path planning and to multitask/multiagent RL, it cannot immediately be used online.

heading: 3 LEARNING CONTROL HIERARCHIES ONLINE
text: While there are many situations in which a hierarchical representation might plausibly be computed off-line, in a paradigm such as that of life-long learning, we would like our agents to be able to construct a hierarchical representation online. This representation would constitute an abstraction of the agent’s experience thus far, and would need to be incrementally adjusted as the agent experiences more of the world and is better able to synthesis a global picture of their experience. The idea of incrementally adjusting an abstract representation of a task is highly intuitive. As people, we are often aware, not just of improving our performance on a task, but also of changing (and often simplifying) our thinking about the task as we gain more experience. Here, we will periodically increase the agent’s representational capacity by incrementally adding subtask states. This procedure is similar to a number of methods for incremental learning on static problems in which additional hidden layers are added to a standard ANN architecture.
An important question that naturally arises is that of when we should incorporate a new subtask. Intuitively, since our subtasks constitute a spacial and temporal abstraction, we should add in a new subtask only when we have seen a sufficient number of new states. Suppose we wanted to construct an abstracted MLMDP with a state space 1/k the size of the base LMDP. We would then add in a subtask for every k states the agent has seen. In practice we typically factor the state space such that |S0|= kk, which determines both the depth of the hierarchy (we will have k layers) and the
abstraction factor for each layer (each layer has 1/k the number of state of the layer below it). We refer to this notion as the ‘subtask genesis’ condition. More generally, when the multi-scale structure of the domain is known a priori, the decomposition values for each layer may be explicitly specified. For example, in a rooms domain, if we know that each room contains 25 states, then we may choose a decomposition factor of kl = 25 for the base layer.

heading: 3.1 LAYER-WISE UPDATES
text: Since we are incrementally adding states to our MDPs, we need a way of mapping the parameters from our old MDP onto our new MDP. Moreover, when a subtask is added, we need to make adjustments to both the current MDP (which has received a new subtask state) and the higher layer MDP (which has tacitly received a new interior state). Of course we will need to assume some default initialization for the new parameters here. As a guiding principle we seek to extend our MDPs in such a way as to assume as little as is possible about how the new state will integrate with the existing MDP. We do this by initializing the new state with small uniform default values, and allowing subsequent experience to shape the transition dynamics.
Updating the current MDP: the current MDP will now operate with a new subtask state N lt → N lt + 1; depicted by the blue circles in Fig.(2). To define a consistent control task we are required to update the transition dynamics P lt ∈ RN l t+1 and the state costs qltR. Thereafter, the subtask component of the agent’s task basis Zl:t, and controller z l t will also need to be extended. We assume the previous components of Pt, governing the transition probabilities into the existing subtasks, are unchanged, and only those elements depicted by the blues lines need to be specified. We then initialize the transition probabilities into the new subtask to be uniform over the interior states. The new state cost is initialized to be the mean of the existing subtask costs, qlt = 1/N lt ∑ qt(si). The new elements of the task basis and controller are initialized to one(s).
Updating the higher layer MDP: the higher layer MDP operates with a new interior state N l+1i → N l+1i + 1, again depicted by the blue circle in Fig.(2). To define a consistent control task we are required to update the transition dynamics P l+1i , P l+1 b , and the state costs q l+1 i . Similarly, the interior component of the agent’s task basis Zl+1:i , and controller z l+1 i will need to be updated. Again, we assume the previous components of Pi, Pb are unchanged, and that only those elements depicted by the blue lines in Fig.(2) need to be specified. We assume that the new task cannot transition into a boundary state, initializing the new components of P l+1b to zero. We also take the new components of P l+1i to be uniform over the interior states. We initialize the state cost to the mean of the existing interior states ql+1i = 1/N l+1 i ∑ qi(si) , and the new elements of the task basis and controller are initialized to one(s).
Essentially we have simply add a new state to our MDP, which is assumed to be loosely connected to all other states, and to have average reward. While this provides no immediate benefit, the additional representational capacity this provides to the higher layer will ultimately be utilized when these additional weights are updated.

heading: 3.2 EXPLORATION BOOSTS VIA POLICY COMPOSITION
text: Exploration with a hierarchical control architecture promises the possibility of dramatically improving exploration efficiency, since a 1-step transition in the higher layer MDP corresponds to a many-step transition in the lower layer MDP. In this way the agent is essentially diffusing via a heavy-tailed distribution; sometimes taking extended trajectories, and otherwise diffusing locally.
As discussed in Sec.(2.2), it is critical that the structure of the higher layer MDP is consistent with the lower layer MDP. In the off-line setting, this consistency requirement is achieved analytically via Eqns.(8,9) in Saxe et al. (2017). In an online setting, we need to make an initialization assumption about the transition structure. In practice it is important that we obtain a reasonable estimate for these dynamics otherwise the abstraction presented by the higher layer may be deleterious. Intuitively, operating with a poor estimate for the higher layer dynamics is equivalent to selecting, in the options framework, a poor options policy. This results in the agent having suboptimal local behaviour, until it transitions into an area in which the macro policy can be changed. In principle, we can always ensure that our estimate of the higher layer dynamics is sufficiently accurate by simply using a large enough

heading: Nt = 1 Nt = 3Nt = 2
text: buffer. Of course, this in an intrinsically limited approached. We found that in practice it is possible to achieve good performance using a much smaller buffer size, if the agent is further equipped with a count based exploration boost. Intuitively this ensures that our agent explores enough of the surrounding states early on, to obtain a reasonable sample estimate of the higher layer dynamics.
Throughout the trajectory we maintain a vector of state visits f . A composite exploration policy zlexp is constructed by computing z l exp = Z
lwl, where wl = ef−µ(f) is the baseline adjusted statefrequency count. This simple construction makes rich use of the fact that policies compose in the MLMDP setting. Specifically, while the directed behaviours of a number of policies are aligned, the agent is strongly driven to pursue those initiatives. Alternatively, when directed behaviours conflict, the exploration boost is flat, and does not bias the agent’s exploration. Said differently, the agent explores with consideration of their knowledge of the full space, not just their immediate surroundings. This approach over providing a count-based exploration boost over higher layer policies is conceptually similar to the count-based feature exploration considered in recent work Machado et al. (2018).

heading: 3.3 BALANCING DRIVERS: STRUCTURED AND UNSTRUCTURED EXPLORATION
text: A useful taxonomy for classical exploration strategies divides approaches into those that deliver undirected exploration (such as drawing states via the Boltzmann distribution), direct exploration which directly utilizes some of the agent’s experience (such as state-count based methods), and model based methods. But combining the count-based exploration boost, the higher layer policies, and the base layer controller, we demonstrate that our agent utilizes elements of all three of these conceptual approaches concurrently.
At any point in time, our agent must balance multiple (potentially conflicting) drivers. Firstly, their actions may be driven by their primary policy zbase which seeks to direct the agent to a goal state, but operates locally (missing the big picture). In the LMDP setting the optimal policy is stochastic and next-states are drawn from a Boltzmann distribution of the state-value function, scaled by the passive dynamics. Secondly, the agent’s actions may be driven by a higher layer policy zhl which also seeks to direct the agent to a goal region, but operates more globally (missing finer details). The higher layer policy is delivered by an abstracted MLMDP which models the base problem. Finally, the agent may be driven by an exploration policy zexp which rewards infrequently visited states (at the cost of achieving the stated goal). This exploration boost is tantamount to a classical state-count based
method. The compositionality of the MLMDP allows for these drivers to be employed concurrently in a natural way, by simply combining the relevant desirability functions. In practice our agent acts, at all times, under the composite policy:
zeff = α1zbase + α2zexp + α3zhl, (2)
where the αi are taken to be fixed weighting parameters. More generally, it is very likely that the agent would benefit from a dynamic update to this weighting scheme, although this is not considered in the present work. Intuitively the agent would benefit from a preference for an exploration policy early on, and for an abstracted policy later as it acquires more experience on the task.

heading: 4 RESULTS
text: There are two separate, but equally important results contained herein. The first is that the proposed method can uncover a deep hierarchical abstraction of the task ensemble in a completely online fashion. The abstractions we uncover with the online method converge to those uncovered analytically in Saxe et al. (2017), and in a batch-offline setting in Earle et al. (2018). Convergence here has a double meaning; the online method converges to the correct value estimates for the higher layer dynamics and reward structures as more samples are seen, but it also converges to the correct higher layer MLMDP structure by incrementally growing the abstracted MDP, adding states only as the
additional representation capacity is required. Once the hierarchy is in place, significant performance gains can be expected when the agent is faced with new tasks.
Secondly, we show that the process of learning the hierarchical structure online does not significantly slow down learning. In fact, it can actually improve exploration over the flat implementation! This is due to the fact that our method is incrementally growing and solving the higher layer abstractions online. In this way the agent is able to make use of a distilled form of its previous experience to efficiently traverse regions of the state space it has already explored. Mathematically, this has the effect of reducing the diffusion length between disparate regions of the state space.
In order to achieve the exploration improvements in the online setting, we further exploited the compositionality afforded by the MLMDP framework, to balance the directed behaviours of the base policy, higher layer policy, and exploration policy. The compounding effect of these drivers is disentangled in Fig.(3). Here, the agent operates in a 200-state 1D corridor. The agent begins always on the left-most end of the corridor, and explores the domain with a finite horizon of 1,000 steps. We measure the progress that the agent is able to make along the corridor under each exploration protocol. All results are averaged over 100 runs.
When the task is to reach a singleton goal state, the agent can do no better than explore each state individually. There is no implicit abstraction of the task ensemble or domain that aids learning. However this is typically not the case with real world tasks. A taxi driver seeks to drop off a passenger, and is rewarded for doing so; he is not concerned with the specific configuration of joint angles that resulted in the completion of the task. Said differently, there is a region in the parameter space in which rewards are clumped together corresponding to an abstract representation of the task. To mimic the property of tasks being represented by regions, rather than singleton states, we consider the following task setup; a simple scalable extension of the standard rooms domain. An agent operates in a corridor of 20 rooms, each of which is a 5-by-5 grid world. The rooms are connected to their left and right neighbours by a single state at the middle of the corresponding wall (see Fig.(4)). A goal room is then randomly selected and rewards are placed at 50% of its states. The agent then explores the domain until it encounters one of the rewards. At this point the remaining rewards in the goal room are removed, and a new goal room is randomly selected. The agent continues in this vein for a finite time horizon of 50,000 steps. This task is motivated by a foraging metaphor in which an animal must explore a space both hierarchically (to find the right room) and locally (to find the right state). We compare the performance of our agent equipped with a learned hierarchy against two optimistically initialized Q-learning agents: the first drawing states from a Boltzmann distribution, and the second utilizing state-count based exploration boosts.

heading: 5 CONCLUSION
text: We present a method that is able to learn deep hierarchical control architectures in a fully online way. Moreover, we demonstrate in a toy domain that the agent is able to make use of its partial experience to-date to improve learning. In order to improve sample efficiency, we introduce a new exploration paradigm in multiple exploration initiatives operate concurrently to great effect. We compare the proposed method to some standard exploration strategies in a simple tabular domain requiring significant exploration. In future work we plan to extend the method to incorporate function approximators to extend the key conceptual advancements to large state and action spaces.

Review summaries:
This work builds on the ICML paper from Saxe et al (2017) in which the compositionality property of LMDPs was exploited to solve multi-task hierarchies. The paper extends this work by proposing a method that learns incrementally such hierarchies instead of pre-defining them by design. Some experimental results illustrate the method on two toy problems, a 1D corridor and a corridor of rooms.