Identifying Selections for Unsupervised Subtask Discovery

Yiwen Qiu, Yujia Zheng, Kun Zhang

When we tackle a complex project—like moving to a new city—we don’t think about every individual muscle twitch. We think in subtasks: pack the boxes, load the truck, drive to the destination. For AI agents, learning these "skills" or "options" is the holy grail of efficiency. However, most AI models struggle to figure out where one subtask ends and another begins without a human holding their hand.

A new paper from researchers at Carnegie Mellon University and MBZUAI, titled Identifying Selections for Unsupervised Subtask Discovery, introduces a clever causal perspective to this problem. By treating subtasks as "selection mechanisms," they’ve developed a way to discover reusable skills that actually help robots generalize to brand-new tasks.

TL;DR

This paper argues that subtasks are best modeled as selection variables—causal switches that determine which actions are relevant to a specific goal. By using a novel Sequential Non-negative Matrix Factorization (seq-NMF) method, the authors can discover these subtasks from raw data without supervision, significantly improving how well imitation learning agents perform on complex, multi-stage robotic tasks.

What Problem Does This Paper Address?

In Reinforcement Learning (RL) and Imitation Learning (IL), "long-horizon" tasks (tasks that take a long time and many steps) are notoriously difficult. Breaking them into subtasks helps, but unsupervised subtask discovery—finding these pieces without being told what they are—is a major challenge.

Comparison of causal models for subtasks: (a) Confounders, (b) Selections, and (c) Intermediates.

The authors point out a fundamental flaw in existing methods: most models treat subtasks as simple hidden states, "confounders" (external factors that influence both state and action), or intermediates. This overlooks the true nature of human behavior. When we perform a subtask, we are essentially selecting a specific policy. The subtask isn't just a label; it’s the reason we chose action A over action B in state S.

Methods

The paper’s contribution is two-fold: a new causal theory and a new algorithm.

  1. Causal Selection Theory: The authors prove that subgoals act as "selection variables." In causal terms, if you know the subgoal ($g_t$), the current state ($s_t$) and action ($a_t$) become dependent ($s_t \not\perp a_t | g_t$). They provide a theoretical framework to identify these selections using conditional independence tests.
  2. seq-NMF (Sequential Non-negative Matrix Factorization): To actually find these selections in data, they adapt NMF—a classic technique for breaking a large dataset into its constituent parts.
The seq-NMF method maps state-action trajectories to a sequence of subgoal selections.

Unlike standard NMF, seq-NMF looks for temporally extended patterns. It decomposes a trajectory into:

  • $O$ (Options): A dictionary of behavior patterns (the subtasks).
  • $H$ (H-matrix): A binary indicator matrix that tells the agent which subtask to "select" at any given time.

By optimizing these together with specific "sparsity" and "distinctness" penalties, the model learns a concise set of unique, reusable skills.

Datasets

The authors validated their approach on three distinct types of data:

  • Synthetic Color Dataset: A simple sequence of colors used to verify the causal theory and the accuracy of the discovery algorithm.
  • Driving Dataset: A simulated environment where a car must follow different paths. This tested the model's ability to find "crossing points" where subtasks change.
  • Kitchen Environment (D4RL): A complex, high-dimensional robotic benchmark. The robot must perform sequences of tasks like opening a microwave, moving a kettle, and flipping a light switch. This was used to test how well the discovered subtasks transfer to new, unseen task combinations.

Key Insights and Ideas

  • Subtasks as Filters: The "aha moment" here is viewing a subtask as a selection mechanism. It’s not just a hidden variable; it’s a causal "collider" that explains the relationship between what a robot sees and what it does.
  • Disentangling Discovery from Policy: By using seq-NMF, the authors separate the discovery of subtasks from the learning of the policy. This makes the training process much more stable than "end-to-end" methods that try to learn everything at once.
  • Generalization through Re-composition: The results show that if you learn "how to open a microwave" in one task, the agent can immediately use that skill in a completely different sequence of events, which is the essence of hierarchical intelligence.

Key Results

  • Causal Verification: The researchers used statistical tests (P-values) to confirm that subgoals in their datasets indeed behave like selection variables, validating their theoretical starting point.
  • Superior Generalization: In the Kitchen environment, the seq-NMF method outperformed state-of-the-art baselines like H-AIRL and Option-GAIL.
  • Zero-Shot Adaptation: When faced with a new task composed of 5 subtasks (one more than seen during training), the agent using seq-NMF subtasks maintained high performance, while baseline methods saw significant drops in success.

Limitations and Future Work

While powerful, the method currently assumes that subtasks are the only hidden factor. In the real world, "confounders" (like weather or lighting) and "selections" (the agent's goals) often exist simultaneously. The authors acknowledge that their current theory doesn't yet handle these mixed scenarios.

Future work aims to expand this causal framework to account for more complex environmental shifts and to see if these discovered subtasks can be used to help robots learn entirely through their own exploration, rather than relying on expert demonstrations.

Summary updated

Abstract

When solving long-horizon tasks, it is intriguing to decompose the high-level task into subtasks. Decomposing experiences into reusable subtasks can improve data efficiency, accelerate policy generalization, and in general provide promising solutions to multi-task reinforcement learning and imitation learning problems. However, the concept of subtasks is not sufficiently understood and modeled yet, and existing works often overlook the true structure of the data generation process: subtasks are the results of a *selection* mechanism on actions, rather than possible underlying confounders or intermediates. Specifically, we provide a theory to identify, and experiments to verify the existence of selection variables in such data. These selections serve as subgoals that indicate subtasks and guide policy. In light of this idea, we develop a sequential non-negative matrix factorization (seq- NMF) method to learn these subgoals and extract meaningful behavior patterns as subtasks. Our empirical results on a challenging Kitchen environment demonstrate that the learned subtasks effectively enhance the generalization to new tasks in multi-task imitation learning scenarios. The codes are provided at this [*link*](https://anonymous.4open.science/r/Identifying\_Selections\_for\_Unsupervised\_Subtask\_Discovery/README.md).
BibTeX
@inproceedings{qiu2024identifying,
  author = {Yiwen Qiu and Yujia Zheng and Kun Zhang},
  title = {{Identifying Selections for Unsupervised Subtask Discovery}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=hH4bPkOhhh},
}
Figure