Autonomous Extracting a Hierarchical Structure of Tasks in Reinforcement Learning and Multi-task Reinforcement Learning

Behzad Ghazanfari, Matthew E. TaylorarXiv 2017 · OpenReview

TL;DR

This paper introduces ARM-HSTRL, a novel method that autonomously extracts hierarchical task structures from successful reinforcement learning (RL) trajectories. By leveraging association rule mining, it identifies sub-goals and their temporal relationships, significantly improving learning efficiency and enabling better transfer learning in multi-task RL scenarios.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents often struggle with high-dimensional state spaces, leading to slow learning. A key challenge is the lack of explicit knowledge about how to break down complex tasks into smaller, manageable sub-goals and understand the relationships between them. While hierarchical RL (HRL) offers a solution by decomposing tasks, existing methods often rely on human experts to define these hierarchies or require significant prior knowledge about the task structure. This paper aims to address this gap by proposing an autonomous method to discover these task hierarchies directly from observed successful agent behavior. This is particularly relevant for multi-task RL (MTRL) and transfer learning (TL), where understanding task structure is crucial for efficient knowledge transfer.

Methods

The core of the proposed method, ARM-HSTRL, combines two main components:

  1. Association Rule Mining (ARM): This technique is adapted from data mining to discover relationships between states in successful RL trajectories. Each successful trajectory is treated as a "transaction," and states within these trajectories are considered "items." ARM is used to find "association rules" of the form $A \rightarrow B$, where $A$ and $B$ are sets of states (sub-goals). These rules represent temporal and structural relationships, indicating that if states in $A$ are visited, states in $B$ are likely to follow. The method uses frequent itemset generation (specifically, the FP-growth algorithm) and rule generation, with thresholds for minimum support (minsup) and minimum confidence (minconf) to filter out trivial or spurious rules.
  2. Hierarchical Structure Tree (HST) Construction: Once association rules are extracted, they are converted into a hierarchical structure. This is achieved by building a tree where nodes represent sub-goals. The algorithm iteratively constructs this tree by processing the association rules, creating branches and nodes based on the discovered relationships. The temporal aspect (time of visiting states) is also considered to infer the order of sub-goals. This HST effectively represents the task decomposition and the sequence of sub-goals required to achieve a larger goal.

The method is designed to be autonomous, requiring only successful trajectories as input, and does not need pre-defined action models or task structures.

Datasets

The paper does not explicitly mention using pre-existing benchmark datasets. Instead, it evaluates its method on two custom "testbeds" designed to represent mazes of varying sizes and complexity. These testbeds are used to generate the successful trajectories from which ARM-HSTRL extracts hierarchical structures. The experiments involve different maze sizes (e.g., 22x22, 26x26) and varying numbers of sub-goals per task (e.g., 5 or 7).

Key Insights and Ideas

  • Leveraging Data Mining for RL Structure: The paper ingeniously applies association rule mining, a technique from data mining, to discover hidden structures in RL. This demonstrates the power of cross-domain inspiration in AI research.
  • Autonomous Hierarchy Discovery: The ability to automatically extract task hierarchies without human intervention is a significant step towards more general and adaptable RL agents. This reduces the reliance on expert knowledge, which is often a bottleneck.
  • Sub-goals as Signatures: The paper proposes that the sequence of sub-goals within a task can act as a unique "signature" for that task. This insight is crucial for distinguishing between different tasks in MTRL and for effective knowledge transfer.
  • Handling Task Differences in MTRL: By autonomously extracting hierarchical structures, ARM-HSTRL can better capture and handle diverse task differences (e.g., varying transition functions and reward functions) in MTRL, making it more robust than methods relying on shared value functions.
  • Efficiency Gains: The hierarchical decomposition directly leads to a significant reduction in the number of steps required to reach goals, as demonstrated in the experimental results.

Key Results

The paper presents experimental results in both Hierarchical Reinforcement Learning (HRL) and Multi-Task Reinforcement Learning (MTRL) settings.

  • HRL: In experiments on maze environments, ARM-HSTRL consistently outperformed standard Q-learning in terms of learning speed (fewer steps to reach goals) and reward accumulation. For instance, in one experiment, ARM-HSTRL achieved significantly fewer steps to goal compared to Q-learning, with p-values much smaller than 0.00001, indicating a statistically significant improvement.
  • MTRL: In a more complex MTRL scenario with different tasks having distinct transition and reward functions, ARM-HSTRL demonstrated its ability to learn and manage multiple tasks. While Q-learning struggled to learn across these varied tasks, ARM-HSTRL showed promising results in navigating and learning from these diverse environments. The paper highlights that the extracted hierarchical structure provides an abstraction that allows the agent to reuse and generalize knowledge.

Limitations and Future Work

  • Minsup Threshold Sensitivity: The paper acknowledges that the choice of the minsup threshold can impact the extracted hierarchy. If minsup is too low, it might lead to an overly complex or spurious hierarchy. Conversely, if it's too high, important sub-goals might be missed. The authors suggest that clustering adjacent sub-goals can be a solution for scenarios where many states are visited frequently.
  • Computational Complexity of FP-growth: While FP-growth is generally efficient, the paper notes that in the worst-case scenario, the FP-tree size can be equivalent to the data size. However, they argue that for RL tasks, the number of sub-goals is typically much smaller than the state space, making FP-growth practical.
  • Future Work: The authors suggest that the method can be extended to factored MDPs by treating state variables as items. They also imply that the extracted hierarchical structure can serve as a foundation for more robust and higher-level knowledge transfer in MTRL and TL, going beyond simple value function sharing. Further exploration into how to best utilize this extracted structure for transfer learning is a natural next step.

Summary updated

Abstract

Reinforcement learning (RL), while often powerful, can suffer from slow learning speeds, particularly in high dimensional spaces. The autonomous decomposition of tasks and use of hierarchical methods hold the potential to significantly speed up learning in such domains. This paper proposes a novel practical method that can autonomously decompose tasks, by leveraging association rule mining, which discovers hidden relationship among entities in data mining. We introduce a novel method called ARM-HSTRL (Association Rule Mining to extract Hierarchical Structure of Tasks in Reinforcement Learning). It extracts temporal and structural relationships of sub-goals in RL, and multi-task RL. In particular,it finds sub-goals and relationship among them. It is shown the significant efficiency and performance of the proposed method in two main topics of RL.
BibTeX
@misc{ghazanfari2017autonomous,
  author = {Behzad Ghazanfari and Matthew E. Taylor},
  title = {{Autonomous Extracting a Hierarchical Structure of Tasks in Reinforcement Learning and Multi-task Reinforcement Learning}},
  year = {2017},
  eprint = {1709.04579},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.04579},
}
Figure