🤖 machine learning

Hierarchical Successor Representation for Robust Transfer

This paper introduces the Hierarchical Successor Representation (HSR), a framework that leverages temporal abstractions and non-negative matrix factorization to overcome the policy dependence and spectral diffusion of classical successor representations, thereby enabling robust, sample-efficient transfer and efficient exploration in complex, non-stationary environments.

Original authors: Changmin Yu, Máté Lengyel

Published 2026-06-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Changmin Yu, Máté Lengyel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are learning to navigate a giant, complex building with many rooms, hallways, and doors. Your goal is to find a specific exit.

The Old Way (The "Successor Representation")
Traditionally, AI agents use a method called the "Successor Representation" (SR). Think of this like a mental map of "how long it takes to get everywhere from here."

If you are in the kitchen, the map tells you it takes 10 seconds to get to the living room, 20 to the garage, etc.
The Problem: This map is tied to how you walk. If you usually walk fast, the map says "5 seconds." If you suddenly have to walk slowly because you are carrying a heavy box (a change in "policy"), your old map becomes useless. You have to redraw the whole thing.
The "Fuzziness" Problem: In a big building, this map gets blurry. It's like a drop of ink spreading in water; it doesn't clearly show where the walls and hallways are, making it hard to understand the building's layout.

The New Way (Hierarchical Successor Representation - HSR)
The authors propose a new method called Hierarchical Successor Representation (HSR). Think of this as upgrading from a step-by-step walking guide to a strategic travel guide.

Instead of thinking about every single footstep (left foot, right foot), the agent learns "macro-moves" or Options.

Analogy: Instead of thinking "step, step, turn, step," the agent thinks, "Walk through the hallway," "Go through the door," or "Cross the bridge."
Why it's better: Even if you change your walking speed (your low-level policy), the strategy of "go through the hallway to get to the next room" stays the same. The HSR builds a map based on these stable, high-level strategies rather than fleeting foot movements. This makes the map robust; if your task changes (e.g., the goal moves to a different room), you don't need to redraw the whole map. You just look at your existing strategic map and find the new goal.

Making the Map Clear (NMF)
The authors also noticed that even with the new HSR, the map could still be a bit cluttered. To fix this, they used a mathematical tool called Non-Negative Matrix Factorization (NMF).

Analogy: Imagine taking a blurry, overlapping photo of a city and using a filter to separate it into distinct, clear building blocks.
NMF takes the HSR map and breaks it down into sparse, local pieces. Instead of a fuzzy blob covering the whole building, it identifies specific "chunks" like "the North Hallway" or "the East Wing."
The Result: The AI discovers the building's natural "bottlenecks" (the doors and hallways that connect rooms). These become the key features of the map. This makes the map not only accurate but also easy for the AI to understand and use.

What This Achieves

Super Transfer: Because the map is based on stable strategies (like "go through the door") rather than specific walking styles, the AI can instantly adapt to new goals. It's like having a map of a city that works whether you are driving a car, riding a bike, or walking.
Better Exploration: In environments where rewards are rare (like finding a hidden treasure in a huge maze), the HSR helps the AI explore more efficiently. It allows the AI to "jump" over local obstacles mentally, realizing that "if I go through this door, I can reach a whole new section of the maze," rather than getting stuck wandering in circles in one small room.

In Summary
The paper argues that by teaching AI to think in chunks of time and strategy (hierarchy) rather than single steps, and then cleaning up that thinking into clear, distinct parts (NMF), we can create AI that learns faster, adapts to new tasks instantly, and explores complex environments much more effectively. It bridges the gap between being fast (like a reflex) and being flexible (like a planner).

Technical Summary: Hierarchical Successor Representation for Robust Transfer

Problem Statement

The Successor Representation (SR) offers a framework for decoupling predictive dynamics from rewards, enabling rapid generalization across reward configurations. However, the classical SR faces two critical limitations in transfer-oriented regimes:

Policy Dependence: SRs are inherently tied to the policy used to generate them. As agents learn, encounter non-stationarities, or face new task demands, the underlying policy changes, rendering established predictive representations obsolete and requiring expensive re-learning.
Spectral Diffusion and Scalability: In topologically complex environments (e.g., multi-compartmental spaces), classical SR features suffer from "spectral diffusion." This results in dense, globally supported, and overlapping features that lack interpretability and scale poorly. Standard spectral decomposition methods (like SVD) applied to SRs often produce components that are sign-indefinite and fail to capture local transition structures effectively.

Methodology

The authors propose the Hierarchical Successor Representation (HSR) to address these limitations by incorporating temporal abstractions into predictive representations.

1. Hierarchical Successor Representation (HSR)

The core innovation is extending the classical SR formulation using the "options" framework (Sutton et al., 1999).

Temporal Abstraction: Instead of predicting state occupancy based on single-step actions, HSR aggregates dynamics over temporally extended, interpretable behavioral segments (options).
Definition: The HSR matrix $M_\mu$ is defined as the predictive state occupancy distribution with respect to a high-level policy $\mu$ . It recursively combines the action-specific SR matrices ( $M_{\bar{a}}$ ) and the expected duration of options ( $\tau$ ).
Bellman Operator: The authors derive a hierarchical Bellman operator $T$ that acts as a contraction mapping, allowing for online learning via Temporal-Difference (TD) updates similar to standard SR, but with a TD-error that accounts for the duration of options.
Expected HSR (eHSR): To further relax policy dependence, the authors advocate for an offline construction where the HSR is averaged over optimal policies from a distribution of pre-training tasks, yielding a generalized, task-agnostic basis.

2. Low-Rank Decomposition via NMF

To achieve sparsity and interpretability, the authors apply Non-Negative Matrix Factorization (NMF) to the HSR matrix, rather than the Singular Value Decomposition (SVD) typically used for spectral methods.

Rationale: Classical SRs exhibit "topological collapse" where intra-compartment states cluster tightly, making NMF ill-posed due to a lack of intra-compartment variance. In contrast, HSR dynamics are "piecewise-smooth," preserving inter-compartment differences while allowing for intra-compartment dispersion.
Outcome: This structure allows NMF to discover sparse, localized, and interpretable basis vectors that align with topological features (e.g., bottleneck states), avoiding the "ringing artifacts" and global smearing associated with orthogonal SVD bases.

Key Contributions

Robust State Representations: The HSR framework produces state features that are robust to task-induced policy changes. By reasoning at a higher level of temporal abstraction, the representation remains stable even when low-level control policies shift.
Interpretable Topological Structures: Applying NMF to HSR yields a sparse, low-rank representation that naturally identifies topological bottlenecks and compartmental structures, providing a policy-agnostic hierarchical map.
Sample-Efficient Transfer: The proposed method facilitates highly sample-efficient transfer to novel tasks in multi-compartmental environments without requiring expensive re-learning of state feature maps.
Scalable Exploration: The temporally extended predictive structure of HSR drives efficient intrinsically motivated exploration, allowing agents to overcome local diffusive barriers in large, procedurally generated environments where single-step methods fail.

Experimental Results

The authors evaluated HSR in discrete, tabular environments (specifically four-room and procedurally generated mazes) using Q-learning with linear function approximation.

Transfer Efficiency: In a four-room environment, agents using HSR row features demonstrated significantly higher transfer efficiency when switching goal locations compared to agents using standard SR (RW-SR) or one-hot encodings. While standard SR agents suffered performance degradation upon policy re-optimization, HSR agents adapted rapidly with fewer episodes.
Stability of Representation: Quantitative analysis showed that HSR matrices underwent significantly less reorganization (lower relative change in Frobenius norm) following policy changes compared to standard SR matrices.
NMF vs. SVD: In low-dimensional basis experiments, HSR features decomposed via NMF outperformed both HSR-SVD and all SR-based baselines (including SR-SVD and SR-NMF). SR-NMF failed due to feature collapse, while HSR-NMF provided a sparse code that uniformly tiled the state space.
Value Reconstruction: HSR bases consistently yielded more accurate reconstructions of optimal value functions for unseen tasks (different goal locations) compared to SR bases, suggesting a better alignment with the manifold of potential value functions.
Exploration: In sparse-reward navigation tasks within large mazes, HSR-augmented intrinsic rewards (specifically HSR-SPIE) maintained high state coverage and goal discovery rates as environment size increased, whereas standard SR-based exploration strategies degraded significantly.

Significance and Claims

The paper claims that integrating temporal abstraction into predictive representations creates a robust, interpretable state representation that bridges the gap between model-free efficiency and model-based flexibility.

Policy-Agnostic Mapping: HSR provides a hierarchical map that is less sensitive to specific reward configurations, effectively decoupling the predictive structure of the environment from the immediate task demands.
Complementarity: The authors position HSR as complementary to Generalized Policy Improvement (GPI) algorithms. While GPI focuses on composing pre-trained policies, HSR focuses on learning a generalizable representation, and combining the two yields superior transfer efficiency.
Scalability: The framework scales to large, procedurally generated environments by enabling agents to "escape" local diffusive barriers through temporally extended predictions, addressing a key bottleneck in exploration for sparse-reward tasks.

The authors note that their empirical evaluations are currently limited to discrete, tabular environments to isolate topological properties. They suggest that future work should integrate HSR into deep RL systems for continuous domains and explore the discovery of options in non-stationary environments.