Hierarchical reinforcement learning methods offer a powerful means of planning flexible behavior in complicated domains. However, learning an appropriate hierarchical decomposition of a domain into subtasks remains a substantial challenge. We present a novel algorithm for subtask discovery, based on the recently introduced multitask linearly-solvable Markov decision process (MLMDP) framework. The MLMDP can perform never-before-seen tasks by representing them as a linear combination of a previously learned basis set of tasks. In this setting, the subtask discovery problem can naturally be posed as finding an optimal low-rank approximation of the set of tasks the agent will face in a domain. We use non-negative matrix factorization to discover this minimal basis set of tasks, and show that the technique learns intuitive decompositions in a variety of domains. Our method has several qualitatively desirable features: it is not limited to learning subtasks with single goal states, instead learning distributed patterns of preferred states; it learns qualitatively different hierarchical decompositions in the same domain depending on the ensemble of tasks the agent will face; and it may be straightforwardly iterated to obtain deeper hierarchical decompositions. Hierarchical reinforcement learning methods hold the promise of faster learning in complex state spaces and better transfer across tasks, by exploiting planning at multiple levels of detail BID0 . A taxi driver, for instance, ultimately must execute a policy in the space of torques and forces applied to the steering wheel and pedals, but planning directly at this low level is beset by the curse of dimensionality. Algorithms like HAMS, MAXQ, and the options framework permit powerful forms of hierarchical abstraction, such that the taxi driver can plan at a higher level, perhaps choosing which passengers to pick up or a sequence of locations to navigate to BID19 BID3 BID13 . While these algorithms can overcome the curse of dimensionality, they require the designer to specify the set of higher level actions or subtasks available to the agent. Choosing the right subtask structure can speed up learning and improve transfer across tasks, but choosing the wrong structure can slow learning BID17 BID1 . The choice of hierarchical subtasks is thus critical, and a variety of work has sought algorithms that can automatically discover appropriate subtasks.One line of work has derived subtasks from properties of the agent's state space, attempting to identify states that the agent passes through frequently BID18 . Subtasks are then created to reach these bottleneck states (van Dijk & Polani, 2011; BID17 BID4 . In a domain of rooms, this style of analysis would typically identify doorways as the critical access points that individual skills should aim to reach (Şimşek & Barto, 2009 ). This technique can rely only on passive exploration of the agent, yielding subtasks that do not depend on the set of tasks to be performed, or it can be applied to an agent as it learns about a particular ensemble of tasks, thereby suiting the learned options to a particular task set.Another line of work converts the target MDP into a state transition graph. Graph clustering techniques can then identify connected regions, and subtasks can be placed at the borders between connected regions BID11 . In a rooms domain, these connected regions might correspond to rooms, with their borders again picking out doorways. Alternately, subtask states can be identified by their betweenness, counting the number of shortest paths that pass through each specific node (Şimşek & Barto, 2009; BID17 . Other recent work utilizes the eigenvectors of the graph laplacian to specify dense rewards for option policies that are defined over the full state space BID10 . Finally, other methods have grounded subtask discovery in the information each state reveals about the eventual goal (van Dijk & Polani, 2011) . Most of these approaches aim to learn options with a single or low number of termination states, can require high computational expense BID17 , and have not been widely used to generate multiple levels of hierarchy (but see BID24 ; BID12 ).Here we describe a novel subtask discovery algorithm based on the recently introduced Multitask linearly-solvable Markov decision process (MLMDP) framework BID14 , which learns a basis set of tasks that may be linearly combined to solve tasks that lie in the span of the basis BID21 . We show that an appropriate basis can naturally be found through non-negative matrix factorization BID8 BID3 , yielding intuitive decompositions in a variety of domains. Moreover , we show how the technique may be iterated to learn deeper hierarchies of subtasks.In line with a number of prior methods, BID17 BID12 our method operates in the batch off-line setting; with immediate application to probabilistic planning. The subtask discovery method introduced in BID10 , which also utilizes matrix factorization techniques to discover subtasks albeit from a very different theoretical foundation, is notable for its ability to operate in the online RL setting, although it is not immediately clear how the approach taken therein might achieve a deeper hierarchical architecture, or enable immediate generalization to novel tasks. We present a novel subtask discovery mechanism based on the low rank approximation of the desirability basis afforded by the LMDP framework. The new scheme reliably uncovers intuitive decompositions in a variety of sample domains. Unlike methods based on pure state abstraction, the proposed scheme is fundamentally dependent on the task ensemble, recovering different subtask representations for different task ensembles. Moreover, by leveraging the stacking procedure for hierarchical MLMDPs, the subtask discovery mechanism may be straightforwardly iterated to yield powerful hierarchical abstractions. Finally, the unusual construction allows us to analytically probe a number of natural questions inaccessible to other methods; we consider specifically a measure of the quality of a set of subtasks, and the equivalence of different sets of subtasks.A current drawback of the approach is its reliance on a discrete, tabular, state space. Scaling to high dimensional problems will require applying state function approximation schemes, as well as online estimation of Z directly from experience. These are avenues of current work. More abstractly, the method might be extended by allowing for some concept of nonlinear regularized composition allowing more complex behaviours to be expressed by the hierarchy.
We present a novel algorithm for hierarchical subtask discovery which leverages the multitask linear Markov decision process framework.
{"src": "scitldr-AIC_train", "paper_id": "ry80wMW0W"}