Sequential Association Rule Mining for Autonomously Extracting Hierarchical Task Structures in Reinforcement Learning

Behzad Ghazanfari, Fatemeh Afghah, Matthew E. TaylorIEEE Access 2020 · DOI

Introduction

Reinforcement Learning (RL) has achieved remarkable success in various domains, yet it remains plagued by the "curse of dimensionality" and the challenge of sparse rewards. In complex environments, an agent may wander aimlessly for millions of steps before encountering a single reward signal, making standard exploration techniques inefficient. Hierarchical Reinforcement Learning (HRL) addresses this by organizing behavior into a hierarchy of sub-tasks, allowing the agent to reason at higher levels of abstraction.

A persistent challenge in HRL is the autonomous discovery of these hierarchies. Many existing frameworks rely on human experts to define sub-goals or provide causal models, such as Dynamic Bayesian Networks (DBNs), which describe how actions influence specific state variables. This paper introduces SARM-HSTRL, a novel approach that utilizes Sequential Association Rule Mining to autonomously discover sub-goals and construct multi-level task hierarchies directly from an agent's successful experiences, eliminating the need for prior domain knowledge.

Methodology: Bridging Data Mining and Control

The SARM-HSTRL framework operates by treating the reinforcement learning process as a data generation problem. It consists of two main algorithmic phases:

1. Sequential Association Rule Mining (SARM)

The core innovation lies in treating successful RL trajectories as "transactions" in a database, similar to how market basket analysis identifies frequent itemsets in retail. In this context, a "transaction" is a sequence of states visited by the agent from start to goal.

Using the FP-growth algorithm, SARM-HSTRL identifies frequent sequences of states. Two key metrics from data mining are adapted for RL:

  • Support: The frequency with which a specific state sequence appears across all successful trajectories. High support indicates a common path or bottleneck.
  • Confidence: The reliability of the sequence. If state $A$ is frequently followed by state $B$ on the way to the goal, the rule $A \rightarrow B$ has high confidence.

States that consistently appear in high-confidence sequential rules are identified as "critical states" or sub-goals. This data-driven approach allows the agent to mathematically distinguish between random exploration noise and the essential milestones required to solve a task.

2. Hierarchical Structure of Tasks (HST) Construction

Once sub-goals are identified, the algorithm organizes them into a tree-like Hierarchical Structure of Tasks (HST). Each node in the tree represents a sub-task, and the identified critical states serve as "exits" or termination conditions. This structure allows the agent to decompose a complex, long-horizon problem into a series of shorter, more manageable sub-problems. Unlike previous methods that produce "flat" lists of bottlenecks, SARM-HSTRL naturally generates multi-level hierarchies, reflecting the nested nature of many real-world tasks.

Experimental Evaluation

The authors validated SARM-HSTRL across several challenging simulated environments, comparing its performance against standard Q-learning and existing HRL methods like Cascading Decomposition and HI-MAT.

  • Deep and Complex Mazes: In grid-world environments designed with deep (7-level) and branching (4-level) hierarchies, SARM-HSTRL demonstrated significantly faster convergence. The agent was able to identify the underlying structure of the maze and focus its learning on transitioning between rooms rather than individual grid cells.
  • Factored MDPs (Scaled Taxi Domain): In the classic Taxi problem—where an agent must pick up a passenger and drop them off at a destination—the state space is "factored" into variables like taxi coordinates and passenger status. While traditional methods like HI-MAT require a pre-defined DBN to understand these factors, SARM-HSTRL successfully identified the "pick-up" and "drop-off" events as the primary sub-goals purely through sequence analysis.

Key Insights and Results

The experimental results highlight several critical advantages of the SARM-HSTRL approach:

  1. Autonomous Discovery: The algorithm proves that optimal hierarchies can be found in Factored MDPs without expert-provided causal models. The temporal sequence of states inherently contains the necessary causal information.
  2. Robustness to Variability: Real-world tasks often have multiple valid solutions. Because SARM-HSTRL aggregates data from multiple successful trajectories, it can synthesize a robust hierarchy that accounts for different paths to the goal. This is a significant improvement over methods that rely on a single, "perfect" demonstration.
  3. Efficiency: In all testbeds, SARM-HSTRL drastically reduced the number of steps required to reach the goal. Statistical analysis (p-values $< 1 \times 10^{-5}$) confirmed that the performance gains were consistent and significant.

Conclusion

SARM-HSTRL represents a significant step toward truly autonomous reinforcement learning. By leveraging sequential association rule mining, the framework allows agents to "learn how to learn" by discovering the latent structure of their environment. While currently optimized for discrete state spaces, the authors suggest that future integration with Deep RL techniques—such as using neural networks to cluster similar states—could extend this powerful hierarchical discovery to continuous, high-dimensional domains like robotics and computer vision.

Summary updated

BibTeX
@article{ghazanfari2020sequential,
  author = {Behzad Ghazanfari and Fatemeh Afghah and Matthew E. Taylor},
  title = {{Sequential Association Rule Mining for Autonomously Extracting Hierarchical Task Structures in Reinforcement Learning}},
  journal = {IEEE Access},
  year = {2020},
  doi = {10.1109/access.2020.2965930},
}
Figure