When humans interact with the world, we rarely think in terms of low-level muscle contractions or millisecond-by-millisecond adjustments. Instead, we operate within a hierarchy of reusable behaviors: "open the door," "make coffee," or "take a step." For artificial agents, robots, and smart environments, discovering these high-level temporal abstractions—often called skills, macros, or behavioral primitives—is a fundamental challenge.
Historically, identifying these skills required manual task decomposition or semantic labeling. When researchers attempted to automate this process using standard optimization objectives like maximum likelihood estimation, they ran into an "underspecification" problem. Without explicit constraints, an objective function cannot distinguish between a highly useful multi-step skill and a degenerate solution, such as breaking behavior down into single, isolated actions or treating an entire, un-reusable trajectory as a single skill.
A powerful insight has emerged to resolve this challenge: reusable behavioral patterns are statistical redundancies within a stream of data. By framing skill discovery as a sequence compression problem, we can leverage information theory to automatically extract meaningful, variable-length behavioral vocabularies without requiring human labels or predefined semantic knowledge.
The Core Intuition: Redundancy as a Proxy for Habit
To understand why compression uncovers meaningful behavior, imagine recording every sensor event in a smart home or every joint angle of a robot over a month. If the agent acts completely randomly, the resulting sequence of data will have maximum entropy and will be virtually incompressible. However, structured behavior is inherently repetitive.
When a human resident makes breakfast, a specific sequence of sensor triggers repeats morning after morning. When a robot successfully navigates a maze, certain sequences of motor primitives are executed repeatedly. In the language of information theory, these recurring sub-routines represent information redundancy.
Compression algorithms are designed explicitly to find and eliminate this redundancy. If we can find a compact representation that minimizes the total description length of a behavioral dataset, the components of that compressed representation will naturally correspond to the agent's core behavioral primitives.
Algorithmic Approaches to Behavioral Tokenization
How do we practically convert a sequence of actions into a compressed vocabulary? Researchers have adapted two main families of compression techniques to solve this problem: dictionary-based greedy algorithms and optimization-based objectives.
1. Dictionary-Based and Tokenization Algorithms
One direct approach treats an agent's trajectory exactly like a text corpus. In natural language processing, algorithms like Byte Pair Encoding (BPE) build a vocabulary by iteratively merging the most frequent pairs of adjacent tokens into a single new token.
Ruijie Zheng et al. applied this exact intuition to robotics in their framework, PRISE, detailed in PRISE: LLM-Style Sequence Compression for Learning Temporal Action Abstractions in Control. By discretizing continuous robot actions and applying BPE, the authors showed that iteratively merging frequent action primitives automatically extracts reusable, variable-length behavioral motifs from raw demonstration data.
Similarly, classic text compression algorithms like Lempel-Ziv-Welch (LZW) have been repurposed to discover behavioral "macros." In A Compression-Inspired Framework for Macro Discovery, Francisco M. Garcia et al. demonstrated that using LZW to find recurring patterns in action trajectories allows reinforcement learning agents to discover high-reward macro-actions, significantly accelerating learning in new, related tasks.
This dictionary-building approach is highly versatile. It has been used by Lucas Langer et al. to discover environment-specific structural regularities for Predictive State Representations, by Tianshu Wang et al. to segment continuous human gestures into a discrete "lexicon" of primitive movements, and by Sook-Ling Chua et al. to segment raw smart-home sensor streams into distinct human activities without prior labeling.
2. Optimization via the Minimum Description Length (MDL) Principle
Instead of greedily merging tokens, we can frame skill discovery as a global optimization problem governed by the Minimum Description Length (MDL) principle. The MDL principle states that the best statistical model for a set of data is the one that minimizes the sum of:
- The length of the model (the size and complexity of our skill library).
- The length of the data encoded using that model (the trajectories compressed using those skills).
This creates a mathematical elegant mathematical "tie-breaker" for skill discovery. If an agent's skill library contains thousands of highly specific, long-horizon trajectories, the model complexity is too high. If the library only contains basic, single-step actions, the compressed data length remains too long because frequent sequences must be written out fully every time.
[ Too Granular ] [ Optimal Balance (MDL) ] [ Too Specific ]
Skill Library: Skill Library: Skill Library:
- Step - Walk Forward (5 steps) - Entire Trajectory A
- Turn Around - Entire Trajectory B
Data Encoding Length: Data Encoding Length: Data Encoding Length:
High (Must repeat 'step') Low (Compressed via primitives) Minimal
Model Complexity: Model Complexity: Model Complexity:
Low Moderate Extremely High
By minimizing the total description length, the system is forced to find the optimal balance: a compact set of highly reusable, multi-step primitives.
In Learning Options via Compression, Yiding Jiang et al. introduced LOVE (Learning Options Via comprEssion), demonstrating that incorporating a compression objective prevents reinforcement learning models from collapsing into degenerate solutions, forcing them instead to isolate common, reusable temporal structures.
This principle scales across domains. Haotian Fu et al. utilized the MDL objective in their framework, LAST, to balance skill library complexity with data representation in language-guided robot demonstrations. Decades earlier, G. Michael Youngblood et al. proved the foundational nature of this concept by applying MDL to inhabitant behavior streams, automating smart-home decision-making hierarchies without requiring any initial semantic knowledge of the human actions.
Why It Works: The Power of Semantic-Free Abstraction
The unifying strength of compression-based skill discovery is that it is entirely semantic-free. The algorithms do not need to understand what "cooking," "walking," or "opening a door" means. They merely observe the mathematical structure of the action sequences.
By focusing purely on information redundancy and description length, these frameworks bypass the need for expensive human annotation and avoid the biases of human engineers who might design sub-optimal skill boundaries. Whether applied to a robot learning manipulation from pixels, an agent discovering macros in a grid world, or a smart home predicting its resident's next move, compression transforms the messy problem of behavioral abstraction into a clean, objective optimization of information flow.
Key Foundational Work
Unsupervised Analysis of Human Gestures (2001) — contributed 2 concept elements to this direction.
Automation Intelligence for the Smart Environment (2005) — contributed 1 concept elements to this direction.