Unsupervised Hierarchical Skill Discovery

AI summary

Overview

Research area: Reinforcement learning (RL), specifically unsupervised skill segmentation and hierarchical structure discovery from observational data.

Technical level: Advanced. The paper assumes familiarity with reinforcement learning, optimal transport, context-free grammars, temporal action segmentation, and options frameworks.

Scope: The paper proposes HiSD (Hierarchical Skill Discovery), a framework that segments unlabelled observation trajectories into discrete skills and induces a compositional hierarchy over them using grammar-based compression, evaluated on Craftax and the full unmodified version of Minecraft.

What This Paper Is About

Most methods that break long RL trajectories into reusable "skills" or "options" depend on action labels, reward signals, or handcrafted annotations, and generally produce flat segmentations rather than deep, compositional ones. HiSD addresses this by discovering both skills and a multi-level hierarchy purely from observational data, requiring only a loose prior on the maximum number of skills. The goal is to extract reusable structure from abundant unlabelled video-like data that can later accelerate and stabilise downstream RL.

Key Contributions

1. A method that integrates temporal action segmentation (TAS) with grammar induction to perform unsupervised hierarchical structure discovery.
2. An observational feature-only pipeline suitable for unlabelled demonstrations, decoupling structure discovery from policy execution and scalably operating on observations alone.
3. Empirical validation of superior segmentation quality and abstraction depth on Craftax and the full unmodified Minecraft, using skill segmentation, reuse, and hierarchy-quality metrics.
4. A proof of concept showing that the discovered hierarchies accelerate and stabilise learning on downstream RL tasks.

Main Findings

• Segmentation on Craftax: HiSD achieves 66% (±15) average mIoU on Stone Pickaxe Static vs. 30% (±4) for OMPN and 45% (±18) for CompILE, and 59% (±2) on Stone Pickaxe Random vs. 27% (±3) for OMPN and 32% (±7) for CompILE. On Mixed Static, HiSD reaches 62% (±10) vs. 49% (±9) for OMPN and 56% (±8) for CompILE.
• Baselines win the simplest task: On Craftax WSWS Random, HiSD scores 63% (±12) average mIoU, behind OMPN at 75% (±12) and CompILE at 76% (±4). HiSD's advantage grows as task complexity and stochasticity increase.
• Segmentation on Minecraft: On the All dataset (44 skills), HiSD achieves 31% (±2) average mIoU vs. 14% (±6) for OMPN and 6% (±3) for CompILE. On the Mapped dataset (14 categories), HiSD reaches 38% (±5) vs. 14% (±6) for OMPN and 6% (±1) for CompILE.
• Hierarchy consistency: On Craftax WSWS Random, HiSD matches the ground truth exactly at 9 unique trees, while OMPN produces 499. On Stone Pickaxe Static, ground truth has 1 unique tree, HiSD 36, and OMPN 500.
• Compactness: HiSD produces smaller, more interpretable trees. On Stone Pickaxe Static, HiSD's average size is 13.44 nodes vs. 16.20 for OMPN (ground truth 9.00). On Minecraft Mapped, HiSD's average branching is 2.08 and max branching 5.40, vs. 7.88 and 43.87 for OMPN.
• Limits under high noise: In the Minecraft All setting, HiSD produces 500 unique trees (one per episode), as does OMPN; the ground truth itself contains 293 unique trees, reflecting heavy dataset noise.
• Downstream RL acceleration: On Craftax's Craft Wooden Pickaxe task, the HiSD Hierarchy agent reaches near-optimal reward within roughly 30k steps, outperforming the HiSD Skills-Only variant, while primitive-action PPO fails entirely and OMPN struggles to converge. CompILE Skills-Only reaches roughly 0.7 reward, and standard imitation learning achieves 0 reward.
• Low-data grounding: A sweep over N ∈ {10, 20, ..., 500} action-labelled episodes shows HiSD reaches 0.94 ± 0.08 mean reward by N = 250 and matches the ground truth hierarchy from N = 350 onward, with segmentation remaining fully unsupervised.
• Minecraft RL: On the Collect Log task using the Mapped dataset, the HiSD Hierarchical agent solves the task 50% of the time, better than HiSD Skills-Only, though below ground truth setups that solve it 100% of the time. Primitive-action PPO again fails.
• Graceful degradation with K: Performance is maximised when K aligns with the ground truth, but the framework degrades gracefully under over-estimation rather than collapsing.

Methodology in Plain English

HiSD treats skill discovery as a two-stage process.

First, segmentation: the method takes continuous feature vectors from unlabelled trajectories and uses ASOT, an optimal transport formulation, to assign each frame to one of K latent skill prototypes. This is solved as a regularised assignment problem that balances visual dissimilarity against a temporal regularity term (a Gromov-Wasserstein component) and a KL-divergence penalty on the aggregate skill distribution. A hardening step (argmax over the assignment) converts soft assignments into discrete skill indices. Because temporal consistency is enforced, skill labels stay constant over coherent behavioural segments rather than flickering.

Second, structure induction: contiguous frames with the same label are collapsed into single atomic symbols, removing the influence of duration. All episodes are concatenated into one corpus separated by a unique boundary token, and a modified Sequitur algorithm runs over it. Sequitur enforces digram uniqueness (no adjacent pair repeats) and rule utility (each rule is used at least twice), producing a context-free grammar where terminals are atomic skills and non-terminals are discovered subroutines. The boundary token is explicitly forbidden from appearing in any production rule, preventing the grammar from merging the end of one episode with the start of another. Parsing an episode with the resulting grammar yields a hierarchical tree.

For downstream RL, each discovered skill becomes an option. Low-level policies are trained with behavioural cloning, initiation and termination conditions are learned via positive-unlabelled classifiers on segmented observations, intermediate nodes act as composite options executing children sequentially, and a high-level agent trained with Maskable PPO selects among valid options using learned initiation sets as action masks.

Evaluation setup: Craftax produces a rendered 274×274×3 RGB image with 4 cardinal movements and 12 non-movement actions; 500 expert trajectories per task configuration are generated with an A* planner, and PCA retains 650 components capturing approximately 99% of variance. Minecraft uses 640×360 pixel observations with native keyboard and mouse control; 500 episodes of collecting two stone blocks are generated with OpenAI's pre-trained VPT models, and features come from MineCLIP's 512-dimensional embeddings. Segmentation is scored with Mean-over-Frames (MoF), F1 (overlap > 50%), and mIoU, under both per-episode and full global Hungarian alignment. Hierarchy quality is scored by unique trees, average depth, average size, and mean/max branching factors. Quantitative results average over 5 random seeds with 95% confidence intervals.

Why This Matters

Impact on research: The work shows that meaningful multi-level hierarchical structure can be recovered without action labels, rewards, or online interaction, challenging the assumption that skill and hierarchy discovery requires action supervision. It also shows that grammatical compression can serve as a practical bridge from low-level behaviour to symbolic planning, and provides evidence that such structures improve temporal credit assignment in downstream RL.

Real-world applications:

• Learning reusable task decompositions from large corpora of unlabelled video, such as gameplay footage or instructional recordings.
• Bootstrapping robotics and manipulation policies from human demonstrations where action labels are expensive or impossible to record.
• Building assistive or workflow-automation agents that must decompose messy demonstrations into reusable subroutines.
• Game AI and simulated-agent training, where long-horizon tasks like resource gathering and crafting are natural hierarchical domains.

Industry relevance: Organisations with abundant observational data but scarce labelled action data could use the segmentation stage to mine structure cheaply, then apply a small amount of action-labelled data (the sweep shows results by N = 250 episodes) to ground the hierarchy into executable policies.

Future Directions

• Integrating representation learning end-to-end, since HiSD currently operates on pre-extracted features and assumes a prior on the maximum number of skills K.
• Inferring K adaptively, for example by running HiSD with a decreasing schedule of K and using stopping criteria such as skill-label switching frequency, the number of active clusters at convergence, or the aggregate segmentation cost.
• Supporting multi-label or factored skill representations (for example via multi-label optimal transport) for settings where behaviours naturally occur concurrently, such as grasping and locomotion overlapping in robotic manipulation.
• Replacing the deterministic Sequitur with probabilistic alternatives such as PCFGs or fragment grammars, potentially augmented with learned action effects, to absorb segmentation noise and capture causal structure. The Minecraft All result of 500 unique trees for a shared task is the motivating failure case.

Target Audience

RL researchers and graduate students working on hierarchical reinforcement learning, skill discovery, and learning from demonstration; practitioners who need to derive reusable structure from unlabelled observational or video data; and robotics or game-AI engineers interested in bootstrapping options and temporal abstractions without action supervision. The paper is most valuable to readers already comfortable with optimal transport, context-free grammars, and the options framework.

Authors’ abstract

We consider the problem of unsupervised skill segmentation and hierarchical structure discovery in reinforcement learning. While recent approaches have sought to segment trajectories into reusable skills or options, most rely on action labels, rewards, or handcrafted annotations, limiting their applicability. We propose a method that segments unlabelled trajectories into skills and induces a hierarchical structure over them using a grammar-based approach. The resulting hierarchy captures both low-level behaviours and their composition into higher-level skills. We evaluate our approach in high-dimensional, pixel-based environments, including Craftax and the full, unmodified version of Minecraft. Using metrics for skill segmentation, reuse, and hierarchy quality, we find that our method consistently produces more structured and semantically meaningful hierarchies than existing baselines. Furthermore, as a proof of concept, we demonstrate that these discovered hierarchies accelerate and stabilise learning on downstream reinforcement learning tasks.