🤖 machine learning

The Terminal Representation in Reinforcement Learning

This paper introduces the Terminal Representation (TR), a novel, lower-dimensional alternative to the Successor and Default Representations in reinforcement learning that captures reward-weighted trajectories without requiring eigendecomposition or symmetric transition assumptions, thereby offering a computationally efficient foundation for tasks like option discovery and transfer learning.

Original authors: Amir Esterhuysen, Anders Jonsson

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Amir Esterhuysen, Anders Jonsson

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 teaching a robot to navigate a maze. The robot's goal is to get from the start to the exit as quickly as possible, but the maze is huge, and it doesn't know the layout yet. To learn efficiently, the robot needs a "mental map" that helps it understand not just where it is, but where it can go and how good those places are.

This paper introduces a new, smarter way for robots to build these mental maps. The authors call it the Terminal Representation (TR).

Here is the breakdown of how it works, using simple analogies:

1. The Old Ways: The "Future Map" and the "Reward Map"

Before this new method, researchers used two main tools:

The Successor Representation (SR): Think of this as a map that only cares about traffic. It tells the robot, "If you stand here, you are likely to visit these other spots later." It ignores whether those spots are good or bad; it just tracks movement patterns.
The Default Representation (DR): This is a more advanced map. It combines traffic with rewards. It tells the robot, "If you stand here, you will likely visit these spots, and here is how much 'goodness' (reward) you will get from them."

The Problem with the Old Ways:
To use the DR effectively for complex tasks (like finding shortcuts or adapting to new goals), the robot had to perform a massive, slow mathematical calculation called eigendecomposition.

The Analogy: Imagine you have a library of books (the map), but to find the most important story, you have to read every single book, cross-reference every page, and write a summary before you can use the information. It's accurate, but it takes a long time and requires a lot of brainpower. Also, this method only works well if the traffic flows equally in both directions (like a two-way street), which isn't true in many real-world mazes.

2. The New Way: The Terminal Representation (TR)

The authors propose the Terminal Representation (TR). It is like a "Destination Guide."

Instead of mapping every single step the robot might take, the TR focuses specifically on where the robot ends up (the "terminal" or goal states) and how valuable those endings are.

Why is it better? Three Key Superpowers:

It's Smaller and Faster (Compactness):
- Analogy: The old maps were like a giant atlas showing every street in the world. The TR is like a simple list of bus stops and their destinations. Because it only cares about the "end of the line" (the goals), it takes up much less memory and is faster to learn.
It Works Immediately (No Extra Math):
- Analogy: With the old DR, you had to do the "library reading" (eigendecomposition) before you could use the map. With the TR, the information is already written on the cover. You can grab the map and use it instantly to solve problems like "How do I get to the exit?" or "How do I shape my rewards?" without doing any heavy calculations first.
It Handles One-Way Streets (Asymmetry):
- Analogy: The old methods assumed that if you can go from Point A to Point B, you can easily go back from B to A. But in real life (and in many mazes), some paths are one-way. The TR doesn't care about this symmetry; it works perfectly fine even if the flow of traffic is chaotic or one-directional.

3. What Can You Do With It?

The paper shows that the TR isn't just a theoretical idea; it works in practice for four main tasks:

Discovering Shortcuts (Option Discovery): It helps the robot figure out long-term strategies (like "run to the corner, then turn left") without needing the slow math calculations of the old methods.
Teaching by Hints (Reward Shaping): If the robot is stuck, the TR can give it little hints (extra rewards) to guide it toward the goal, just as well as the complex old methods.
Exploring New Areas: It helps the robot explore the maze more efficiently by knowing which areas lead to the most interesting destinations.
Learning New Tasks Quickly (Transfer Learning): If you change the location of the goal in the maze, the TR allows the robot to adapt instantly because it already understands the "flow" of the environment toward different endpoints.

The Big Secret

The paper reveals a fascinating secret: The TR actually contains the exact same "smart knowledge" that the old, complex DR method tries to extract through heavy math. The TR just presents this knowledge in a format that is ready to use immediately.

In Summary:
The authors built a new tool for robots to understand their world. It is smaller, faster, and more flexible than previous tools. It skips the heavy math homework and gives the robot a direct, clear guide to its goals, allowing it to learn and adapt much more efficiently.

Technical Summary: The Terminal Representation in Reinforcement Learning

Problem Statement

In Reinforcement Learning (RL), representation learning is critical for spatio-temporal abstraction. Two established approaches are the Successor Representation (SR) and the Default Representation (DR). The SR encodes states based on future visitation trajectories, capturing transition dynamics independent of rewards. The DR extends this by weighting these trajectories with rewards, thereby integrating credit-assignment structure.

However, both representations face limitations when applied to downstream tasks such as option discovery, reward shaping, and transfer learning:

Computational Overhead: Utilizing the DR or SR for these tasks typically requires eigendecomposition (or power iteration) to extract eigenvectors. This imposes a computational cost of $O((S^+)^2)$ or higher per query and assumes symmetric (reversible) transition dynamics, a condition often violated in practical RL environments where policies are directional.
Dimensionality: The SR and DR are defined over the full state space ( $S^+ \times S^+$ ), which can be large and inefficient to store and learn.
Indirect Knowledge: While the DR encodes reward-weighted trajectories, it does not explicitly isolate the reachability and desirability of terminal states in a format directly usable without further spectral analysis.

Methodology: The Terminal Representation (TR)

The authors propose the Terminal Representation (TR), a structurally distinct formulation designed to encode reward-weighted trajectories specifically regarding terminal states.

Theoretical Foundation

The TR is derived within the framework of Linearly-Solvable Markov Decision Processes (LMDPs). In an LMDP, the optimal value function $v(s)$ can be transformed into an exponentiated value $z(s) = e^{v(s)/\lambda}$ , satisfying the linear equation:
$z(s) = e^{R(s)/\lambda} \sum_{s'} P_\mu(s'|s)z(s')$
where $P_\mu$ is a default policy and $\lambda$ is a temperature parameter.

By decomposing the state space into non-terminal states ( $S$ ) and terminal states ( $T$ ), the authors derive the TR matrix $M$ as:
$M = (I_S - D_S)^{-1} D_T$
where $D_S = R_S P_S$ represents non-terminal dynamics and $D_T = R_S P_T$ represents transitions from non-terminal to terminal states. Here, $R_S$ and $R_T$ are diagonal matrices of exponentiated rewards.

The TR allows for zero-shot recovery of the optimal exponentiated values $z$ for any configuration of terminal rewards $y$ (where $y(\tau) = e^{R(\tau)/\lambda}$ ) via the linear relation:
$z = M y$

Learning Algorithms

The paper establishes the convergence of two learning algorithms for $M$ :

Dynamic Programming (Model-Based): An iterative update rule $M_{k+1} = D_T + D_S M_k$ is proven to converge to the true TR.
Sample-Based (Model-Free): A temporal difference (TD) style update rule is derived for online learning:
$\hat{M}(s_t) \leftarrow (1 - \alpha_t)\hat{M}(s_t) + \alpha_t e^{r_t/\lambda} \hat{M}^+(s_{t+1})$
where $\hat{M}^+$ is an extended mapping that handles transitions into terminal states. Theorem 4.2 proves this converges to $M$ under standard stochastic approximation conditions.

Key Theoretical Properties

Dimensionality: The TR is an $S \times T$ matrix. Since the number of terminal states $T$ is often much smaller than the total state space $S^+$ , the TR is significantly more compact than the $S^+ \times S^+$ DR.
Direct Usability (No Eigendecomposition): The columns of the TR correspond directly to the information typically extracted via eigenvectors of the DR. Theorem 7.1 demonstrates that the top eigenvector of the DR is structurally composed of a TR column (specifically the column corresponding to the most desirable terminal state) and a geometric series. Thus, the TR captures the same underlying structural knowledge without requiring eigendecomposition.
Handling Asymmetry: Unlike eigenvector-based approaches which rely on the reversibility of transition dynamics (symmetry) to guarantee real eigenvalues, the TR is inherently asymmetric and well-defined under arbitrary, non-reversible dynamics.
Compositionality: The TR supports zero-shot compositionality. If a new task is a linear combination of base tasks with different terminal rewards, the optimal value function can be recovered by linearly combining the corresponding columns of the TR, bypassing the need to relearn base value functions.
Reward Equivalence: The authors prove that LMDPs with transition-dependent or state-action-dependent rewards can be mapped to equivalent LMDPs with state-dependent rewards, ensuring the TR theory applies broadly across different reward formulations.

Experimental Results

The authors evaluate the TR against the SR and DR across four downstream applications in grid-world environments (Four Rooms, RiverSwim, SixArms):

Option Discovery: In the "covering eigenoptions" task, the TR is used to generate options by directly extracting columns (avoiding eigenvector computation). Variants using the column of the highest-reward terminal state or all columns achieved competitive performance with the DR-based RACE and SR-based CEO methods, often reaching higher average rewards by pushing agents directly toward desirable goals.
Reward Shaping: Using the TR to construct potential-based shaping rewards ( $\hat{r}_t = 1 - M(s_{t+1}, \tau)$ ) yielded performance identical to the DR and superior to the SR. This confirms the TR's ability to capture the necessary structural information for efficient navigation without eigendecomposition.
Count-Based Exploration: Using the norm of the TR as an exploration bonus in RiverSwim and SixArms environments resulted in performance near-identical to the DR and significantly better than the SR.
Transfer Learning: When terminal rewards changed between tasks, the TR was used to transfer knowledge. It performed similarly to Default Features (DF) (the policy-independent DR variant) and outperformed Successor Features (SF) across various base policy configurations, achieving this without an explicit feature learning step.

Significance and Claims

The paper claims that the Terminal Representation offers a viable, computationally efficient alternative to the SR and DR. Its primary significance lies in:

Efficiency: It reduces the dimensionality of the representation and eliminates the need for expensive eigendecomposition, reducing query complexity from $O((S^+)^2)$ to $O(1)$ for column extraction.
Robustness: It functions correctly under non-symmetric (non-reversible) transition dynamics, a common scenario in RL where eigenvector methods may fail or yield complex eigenvalues.
Direct Applicability: It encodes terminal state knowledge explicitly, allowing for direct use in reward shaping, option discovery, and transfer learning without intermediate spectral analysis.

The authors maintain a modest stance, noting that while the TR is competitive with the DR, it is not fundamentally superior in all semantic aspects; rather, it provides a more compact and computationally tractable mechanism to access the same underlying structural knowledge regarding terminal states. Future work is suggested to extend the TR to high-dimensional environments via function approximation and to handle settings without explicitly defined terminal states.