Technical Summary: Unsupervised Hierarchical Skill Discovery (HiSD)

Problem Statement

The paper addresses the challenge of unsupervised skill segmentation and hierarchical structure discovery in reinforcement learning (RL). While human planning operates hierarchically—reasoning in terms of goals and sub-tasks rather than primitive actions—current RL agents in high-dimensional environments (e.g., Minecraft) struggle to learn such structures efficiently.

Existing approaches to skill discovery typically rely on strong supervision, such as:

• Action labels: Requiring access to the specific actions taken by an agent.
• Reward signals: Relying on dense or sparse reward structures to define skill boundaries.
• Handcrafted annotations: Demanding human expertise to define task decompositions (e.g., Hierarchical Task Networks).

These dependencies limit scalability, particularly when dealing with abundant unlabelled video data where actions, rewards, or ground-truth segmentations are unavailable. Furthermore, many existing methods produce "flat" segmentations rather than deep, compositional hierarchies necessary for complex long-horizon tasks.

Methodology: Hierarchical Skill Discovery (HiSD)

The authors propose HiSD, a fully unsupervised framework that extracts reusable, multi-level skill hierarchies purely from observational data (raw pixel or feature sequences). The method decouples structure discovery from policy execution and operates in two distinct stages:

1. Unsupervised Skill Identification (Segmentation)

The first stage converts continuous observation trajectories into discrete sequences of latent skills.

• Input: Unlabelled observation trajectories $T = (X_1, \dots, X_n)$, where $X$ represents feature vectors (e.g., PCA-reduced pixels or CLIP embeddings).
• Algorithm: The framework utilizes Temporal Action Segmentation (TAS) via the ASOT (Unbalanced Optimal Transport) approach.
• Mechanism: ASOT formulates segmentation as an optimal transport problem. It minimizes a regularized objective that balances:
  • Visual Matching Cost: Dissimilarity between observation features and latent skill prototypes.
  • Temporal Regularity: Enforced via a Gromov-Wasserstein (GW) component that penalizes rapid label switching within a temporal radius, ensuring local smoothness.
  • Marginal Penalty: A KL-divergence term that allows for unbalanced skill distributions (handling cases where some skills are rare).
• Output: A sequence of discrete skill indices $z_{1:n}$ representing atomic behavioral units.

2. Symbolic Abstraction and Grammar Induction (Structure Discovery)

The second stage induces a hierarchical structure over the discrete skill sequences.

• Corpus Construction: Contiguous frames sharing the same skill label are collapsed into single atomic symbols. All episode sequences are concatenated into a unified corpus, separated by a unique boundary token $\phi$.
• Algorithm: A modified Sequitur algorithm is applied to the corpus. Sequitur is a linear-time grammar induction algorithm that infers hierarchical structure by identifying recurring patterns.
• Constraints:
  • Digram Uniqueness: No pair of adjacent symbols appears more than once; repetitions are replaced by new non-terminal rules.
  • Rule Utility: Rules must be used at least twice to be retained.
  • Boundary Protection: The boundary token $\phi$ is forbidden from appearing in production rules, ensuring that learned subroutines capture intra-episode behaviors rather than merging the end of one episode with the start of another.
• Output: A Context-Free Grammar (CFG) $G$ where terminal nodes are atomic skills and internal nodes represent discovered subroutines (e.g., "Collect Wood" + "Make Workbench").

Key Contributions

1. Unsupervised Framework: Introduction of HiSD, which integrates temporal action segmentation with grammar induction to discover multi-level hierarchies without action labels, rewards, or manual annotations.
2. Observational-Only Pipeline: A method suitable for unlabelled demonstrations, decoupling structure discovery from policy execution and enabling scalability to large-scale video data.
3. Empirical Validation: Demonstration of superior segmentation quality and abstraction depth compared to baselines (CompILE, OMPN) in complex domains.
4. Downstream Utility: A proof of concept showing that discovered hierarchies accelerate and stabilize learning in downstream RL tasks, even when only a small number of action-labeled demonstrations are available for policy grounding.

Experimental Results

The authors evaluated HiSD on two domains: Craftax (a fully observable, deterministic 2D environment) and Minecraft (a partially observable, stochastic, high-dimensional environment).

Baselines

Comparisons were made against CompILE and OMPN, which were provided with ground-truth sub-task orderings and action labels to ensure they operated under their most favorable conditions. HiSD required only the maximum number of skills $K$ as a prior.

Skill Segmentation Performance

• Metrics: Mean-over-Frames (MoF), F1 Score, and mean Intersection-over-Union (mIoU).
• Findings: HiSD consistently outperformed baselines, particularly in tasks with higher complexity, stochasticity, and longer horizons.
  • In Craftax, HiSD achieved higher mIoU scores, correctly grouping perceptually distinct but semantically equivalent behaviors (e.g., approaching wood from different angles) into single skill clusters.
  • In Minecraft, despite perceptual aliasing (e.g., walking toward wood vs. stone looking identical in first-person view), HiSD's temporal consistency prior allowed for coherent segmentation where baselines failed.

Hierarchy Quality

• Metrics: Unique Trees (consistency), Average Depth, Tree Size, and Branching Factors.
• Findings:
  • HiSD produced more consistent decompositions across episodes (fewer unique trees) compared to OMPN, which often generated a unique hierarchy for every episode.
  • HiSD hierarchies were generally smaller and more interpretable, with lower branching factors, indicating better identification of intermediate subroutines.
  • In the noisy "All" Minecraft task, HiSD struggled to find a single consistent structure due to environmental stochasticity, but performed significantly better in the "Mapped" (semantically grouped) task.

Downstream RL Deployment

The authors demonstrated the utility of the discovered hierarchies by training high-level agents using Maskable Proximal Policy Optimization (PPO) with the discovered skills as options.

• Efficiency: Agents using HiSD hierarchies reached near-optimal rewards significantly faster (e.g., within ~30k steps in Craftax) compared to primitive-action PPO (which failed) and flat skill agents.
• Data Efficiency: The hierarchical agents achieved high performance with as few as 250 action-labeled demonstrations for policy grounding, despite the initial skill discovery being fully unsupervised.

Significance and Claims

The paper claims that HiSD offers a scalable path toward generalist agents capable of learning from abundant, unlabelled data. By bridging state-of-the-art temporal action segmentation with grammar-based compression, the method induces multi-level hierarchies directly from raw observational trajectories.

The authors emphasize that:

• Structure can be recovered purely from temporal coherence and visual similarity, without needing action supervision.
• The resulting hierarchies are semantically meaningful and reusable, providing necessary inductive biases for temporal credit assignment in downstream RL.
• The approach lowers the barrier to training capable agents by removing the need for dense supervision and action labels, facilitating better human-AI interaction through transparent, interpretable structures.

The work is presented as a proof of concept, acknowledging limitations such as the deterministic nature of the grammar induction (which struggles with high noise) and the reliance on a fixed prior for the number of skills $K$. However, the results suggest that unsupervised structure discovery is a viable and effective strategy for complex, high-dimensional reinforcement learning environments.