Autonomous Extraction of a Hierarchical Structure of Tasks in
  Reinforcement Learning, A Sequential Associate Rule Mining Approach
  Reinforcement learning (RL) techniques, while often powerful, can suffer from
slow learning speeds, particularly in high dimensional spaces. Decomposition of
tasks into a hierarchical structure holds the potential to significantly speed
up learning, generalization, and transfer learning. However, the current task
decomposition techniques often rely on high-level knowledge provided by an
expert (e.g. using dynamic Bayesian networks) to extract a hierarchical task
structure; which is not necessarily available in autonomous systems. In this
paper, we propose a novel method based on Sequential Association Rule Mining
that can extract Hierarchical Structure of Tasks in Reinforcement Learning
(SARM-HSTRL) in an autonomous manner for both Markov decision processes (MDPs)
and factored MDPs. The proposed method leverages association rule mining to
discover the causal and temporal relationships among states in different
trajectories, and extracts a task hierarchy that captures these relationships
among sub-goals as termination conditions of different sub-tasks. We prove that
the extracted hierarchical policy offers a hierarchically optimal policy in
MDPs and factored MDPs. It should be noted that SARM-HSTRL extracts this
hierarchical optimal policy without having dynamic Bayesian networks in
scenarios with a single task trajectory and also with multiple tasks'
trajectories. Furthermore, it has been theoretically and empirically shown that
the extracted hierarchical task structure is consistent with trajectories and
provides the most efficient, reliable, and compact structure under appropriate
assumptions. The numerical results compare the performance of the proposed
SARM-HSTRL method with conventional HRL algorithms in terms of the accuracy in
detecting the sub-goals, the validity of the extracted hierarchies, and the
speed of learning in several testbeds.
