Successor Representation

The core innovation of the successor representation is its factorization of the value function V(s). It separates the problem into two components:

• Successor Matrix M(s, s'): A reward-independent model predicting the expected discounted future occupancy of state s' starting from state s. This is defined as M(s, s') = E[∑_{t=0}^{∞} γ^t I(s_t = s') | s_0 = s], where γ is the discount factor.
• State-Reward Vector R(s'): The expected immediate reward for being in each state. The value is then computed as V(s) = ∑_{s'} M(s, s') R(s'). This separation allows the agent to rapidly re-evaluate policies if rewards change, without relearning the dynamics.

Because the successor matrix M is independent of the reward function, it enables powerful transfer learning. Once an agent has learned M for a given policy in an environment, it can instantly compute the value function for any new reward function R' using the same matrix: V'(s) = M(s, ·) · R'.

• This is critical for corrective action planning, where the 'cost' of an error defines a new, often sparse, reward signal. The agent can immediately re-plan without additional environment interaction.
• This property makes SR highly sample-efficient for multi-task learning and rapid adaptation to new goals or constraints.

The successor representation formalizes the concept of temporal proximity between states. The entry M(s, s') represents how 'close' state s' is in the agent's future, discounted by time.

• It provides a predictive map of the environment under a given policy.
• This map can be seen as a generalization of adjacency in a graph, weighted by the policy and discounting. States that are frequently visited soon after one another have high mutual SR values.
• This structure is foundational for model-based planning without a full transition model, as it directly encodes long-term consequences.

The successor matrix can be eigen-decomposed, revealing the underlying temporal structure of the environment. This decomposition enables very fast planning computations.

• The SR can be expressed as M = (I - γ T)^{-1}, where T is the transition matrix under the policy.
• Using this formulation, computing the new value for a changed reward reduces to a simple linear equation solve or matrix-vector multiplication, bypassing iterative dynamic programming.
• This makes it highly suitable for real-time re-planning in agents that must adjust their execution path after detecting an error.

The successor representation occupies a unique middle ground between model-free and model-based reinforcement learning.

• Like model-free methods: It can be learned directly from experience (via TD learning) without explicitly modeling transition probabilities T(s'|s,a).
• Like model-based methods: It supports flexible prediction and rapid re-evaluation when goals/rewards change, a key feature for planning.
• This hybrid nature is ideal for autonomous agents that need the sample efficiency of model-free learning but the flexible re-planning capability of a model to correct errors.

A powerful extension is successor features, which generalize the SR to linear function approximation and feature spaces.

• Instead of a matrix over states M(s, s'), successor features ψ(s) are vectors where each component corresponds to the expected discounted future occupancy of a feature (e.g., 'has key', 'near door').
• The value is then V(s) = ψ(s) · w, where w is a weight vector representing the reward associated with each feature.
• This allows for generalization across both states and tasks in high-dimensional spaces, making it practical for complex environments where agents must formulate corrective plans based on abstract features.

The foundational mathematical framework for modeling sequential decision-making. An MDP is defined by a tuple (S, A, P, R, γ), where:

• S is a set of states.
• A is a set of actions.
• P(s' | s, a) is the state transition probability function.
• R(s, a, s') is the reward function.
• γ is a discount factor. The successor representation is derived directly from the transition dynamics P of an MDP, encoding the expected future occupancy of states under a given policy.

A core family of algorithms for learning value functions in reinforcement learning. TD methods update estimates based on the difference between consecutive predictions (the TD error). The successor representation can be learned efficiently using TD algorithms, as its update rule is a form of TD learning where the "reward" is a state-indicator vector. This allows agents to learn long-term predictions without requiring model-based planning from scratch at each step.

An RL paradigm where the agent learns an explicit model of the environment's dynamics (transition function P) and reward function (R). The successor representation sits between model-based and model-free approaches. It is model-free in that it learns a predictive representation directly from experience, but it is model-like because this representation (the successor matrix) can be rapidly recombined with new reward functions for flexible planning, a key advantage of model-based methods.

A set of intrinsic options (temporally extended actions) derived from the eigenvectors of the successor representation's graph Laplacian. Eigenoptions provide a mathematical framework for discovering proto-skills that facilitate exploration. They correspond to directions of slowest mixing in the state space, guiding an agent to cover the environment efficiently. This demonstrates how the SR's representation of state relationships can be decomposed to drive autonomous skill discovery for corrective navigation.

A direct generalization of the successor representation for continuous state spaces or linear function approximation. Successor features ψ(s, a) represent the expected discounted sum of feature vectors (φ) following a state-action pair. The value function can then be computed as a simple linear product: Q(s, a) = ψ(s, a) · w, where w is a weight vector for the features. This decoupling enables generalized policy improvement—rapid adaptation to new reward functions (new w) without relearning the dynamics.

A formalism within the Horde architecture for learning many predictive questions ("questions") about the future in parallel. A GVF asks: "What is the expected discounted sum of some cumulant (signal) if I follow a certain policy?" The successor representation is a specific, foundational GVF where the cumulant is a state-indicator signal. This framework positions the SR as a building block within a scalable ecosystem of predictive knowledge that an agent can maintain for comprehensive world modeling and planning.