HIERARCHICAL SUBTASK DISCOVERY WITH NON-NEGATIVE MATRIX FACTORIZATION
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.
The present paper extends a previous work by Saxe et al (2017) that considered multitask learning in RL and proposed a hierarchical learner based on concurrent execution of many actions in parallel. That framework made heavy use of the framework of linearly solvable Markov decision process (LMDP) proposed by Todorov, which allows for closed form solutions of the control due to the linearity of the Bellman optimality equations. The simple form of the solutions allow them to be composed naturally, and to form deep hierarchies through iteration. The framework is restricted to domains where the transitions are fixed but the rewards may change between tasks.  A key role is played in the formalism by the so-called ‘free dynamics’ that serves to regularize the action selected. 
The present paper goes beyond Saxe et al. in several ways. First, it renders the process of deep hierarchy formation automatic, by letting the algorithm determine the new passive dynamics at each stage, as well as the subtasks themselves. The process of subtask discovery is done via non-negative matrix factorization, whereby the matrix of desirability functions, determined by the solution of the LMDPs with exponentiated reward. Since the matrix is non-negative, the authors propose a non-negative factorization into a product of non-negative low rank matrices that capture its structure at a more abstract level of detail. A family of optimization criteria for this process are suggested, based on a subclass if Bregman divergences. Interestingly, the subtasks discovered correspond to distributions over states, rather than single states as in many previous approaches. The authors present several demonstrations of the intuitive decomposition achieved. A nice feature of the present framework is that a fully autonomous scheme (given some assumed parameter values) is demonstrated for constructing the full hierarchical decomposition.  
I found this to be an interesting approach to hierarchical multitask learning, augmenting a previous approach with several steps leading to increased autonomy, an essential agent for any learning agent. Both the intuition behind the construction and the application to test problem reveal novel insight. The utilization on the analytic framework of LMDP facilitates understanding and efficient algorithms. 
I would appreciate the authors’ clarification of several issues. First, the LMDP does not seem to be completely general, so I would appreciate a description of the limitations of this framework. The description of the elbow-joint behavior around eq. (4) was not clear to me, please expand. The authors do not state any direct or indirect extensions – please do so. Please specify how many free parameters the algorithm requires, and what is a reasonable way to select them. Finally, it would be instructive to understand where the algorithm may fail.