Successor Representations

The core innovation is factoring the value function V(s) = M(s, ·) · r(·), where:

• M(s, s') is the successor map: the expected discounted future occupancy of state s' starting from s.
• r(s') is the immediate reward function.

This allows an agent to recompute optimal behavior instantly when rewards change, by simply applying the new reward vector to the pre-computed successor map, without re-learning the environment's dynamics.

Because the successor map M is a function of the environment's transition dynamics and policy—but not the reward—it can be reused across tasks within the same environment.

Key implications:

• Rapid Task Adaptation: Learn one map for a maze, then solve new reward configurations (e.g., changing goal locations) with simple linear algebra.
• Generalization to Novel Rewards: The agent can evaluate the value of arbitrary, unseen reward functions, enabling zero-shot performance on new objectives.
• Skill Composition: Different policies (skills) have different successor maps; combining them can solve complex, hierarchical tasks.

Successor representations are learned via a modified Temporal Difference (TD) update. Instead of learning a scalar value V(s), the agent learns a vector of expected future occupancies for all states (or state features).

The TD target for the successor map M(s) is: M(s) ← φ(s) + γ * M(s'), where φ(s) is the state's feature vector. This converges to the expected discounted sum of future features, a more general form of the successor representation. This provides a solid theoretical bridge between model-free and model-based RL.

Successor representations occupy a unique middle ground in the RL spectrum:

• Model-Free Aspect: They are learned directly from experience via TD, without explicitly modeling transition probabilities P(s'|s,a).
• Model-Based Benefit: The successor map M implicitly encodes long-term transition dynamics under the current policy, enabling flexible prediction akin to a model.

This hybrid nature offers the sample efficiency of model-free methods with the flexibility and transfer capability typically associated with model-based planning.

In large or continuous state spaces, a successor feature ψ(s) is learned instead of a full state occupancy map. ψ(s) represents the expected discounted sum of a feature vector φ(s_t) observed in the future.

The value is then: V(s) = ψ(s) · w, where w is a weight vector mapping features to reward.

Advantages:

• Enables generalization across similar states via shared features.
• Transfer of w: If a new task's reward is a linear combination of the same features, only the weight vector w needs to be relearned, not ψ(s).

Successor representations are not just an algorithmic tool; they provide a compelling model for hippocampal place cell activity in the brain. Research suggests the firing patterns of certain neurons correspond not to a single location, but to a predictive map of future locations.

In robotics and AI:

• Navigation: Learn a successor map for an office floorplan; instantly re-plan when a 'coffee' reward is added to a new room.
• Continual Learning: The decoupling allows the dynamics model (M) to be updated slowly from general experience, while reward preferences can change rapidly.

The core strength of SRs is enabling rapid transfer when reward functions change. By separating the successor map (expected future state occupancy) from immediate rewards, an agent can recompute optimal values instantly for new reward configurations without re-learning dynamics.

• Key Mechanism: The value function V(s) is computed as the dot product of the successor representation M(s, s') and the reward function R(s').
• Use Case: An agent trained to navigate a maze for one goal location can immediately re-plan for a new goal by simply updating R(s'), leveraging its pre-computed successor map M.
• Contrast with Model-Free RL: Standard Q-learning would require extensive new experience to adapt, while SRs offer one-shot adaptation.

SRs provide a computational model for hippocampal place cells and cognitive maps in neuroscience. Evidence suggests the mammalian hippocampus encodes successor representations, predicting an animal's future location.

• Biological Analogy: Place cells that fire for an animal's current location also show firing for future states along common trajectories, matching the predictive nature of SRs.
• Theoretical Link: This supports the theory that the hippocampus acts as a predictive map, not just a static spatial map, enabling flexible navigation and planning.
• Implication: SRs bridge reinforcement learning theory with neuroscience, explaining how brains might perform efficient latent learning and revaluation.

SRs can drive exploration by quantifying state novelty or empowerment. The uncertainty or change in the successor map itself can be used as an intrinsic reward.

• Count-Based Exploration: The learning progress of the SR matrix can signal rarely visited states.
• Empowerment: SRs can measure an agent's potential to reach diverse future states (its options), which can be maximized to learn skills.
• Algorithm Example: Successor Features (an extension for continuous features) combined with Generalized Policy Improvement allows an agent to rapidly compose behaviors to achieve novel goals.

Successor Features (SFs) generalize SRs from discrete states to continuous feature spaces. This enables the learning of Universal Value Function Approximators (UVFAs).

• Mechanism: Instead of a matrix M(s, s'), SFs ψ(s) represent expected accumulation of state features φ(s). The value is V(s) = ψ(s) · w, where w are reward weights.
• Application: Allows a single policy to achieve multiple goals defined by linear reward functions in the feature space. Changing goals only requires updating the weight vector w.
• Scale: This is foundational for multi-task reinforcement learning and goal-conditioned policies in complex environments.

While not a full dynamics model, the SR provides a one-step model of multi-step outcomes. This can be used for efficient, limited-horizon planning without full state-transition simulation.

• Planning Shortcut: The SR M(s, s') encapsulates the long-term consequences of being in state s, under a given policy. Planning can involve evaluating outcomes over this compressed representation.
• Hybrid Approach: Algorithms like Successor Representation Actor-Critic combine the fast value computation of SRs with model-free policy optimization.
• Benefit: Offers some sample efficiency advantages of model-based RL without the complexity and potential instability of learning a full transition model T(s'|s,a).

SRs are naturally linked to the Options Framework for temporal abstraction. The SR of an option captures the long-term state visitation distribution induced by executing that option.

• Skill Representation: The SR for an option's policy serves as a portable representation of that skill's consequences.
• Skill Composition: New options can be created by combining or sequencing existing options, with their composite SRs approximated from the components.
• Use Case: In hierarchical RL, learning SRs for sub-policies (options) enables rapid planning and value estimation at a higher, more abstract level.

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 the discount factor. Successor representations decompose the standard value function within this framework, separating the expected future state occupancy (governed by P) from the immediate reward (R).

A class of RL algorithms where an agent learns an explicit model of the environment's dynamics (the transition function P and often the reward function R). This model is then used for planning or policy improvement. Successor representations occupy a middle ground: they are not a full dynamics model but encode long-term state visitation expectations, enabling flexible re-evaluation when rewards change without re-learning the world's dynamics. This makes them more sample-efficient than pure model-free methods and more adaptable than some rigid model-based approaches.

The direct generalization of successor representations to environments where rewards are linear functions of a known feature vector. Formally, if the reward function is R(s, a, s') = φ(s, a, s')ᵀw, where φ are features and w are weights, then the successor feature ψ^π(s, a) represents the expected discounted sum of future features. The value function is simply Q^π(s, a) = ψ^π(s, a)ᵀw. This decoupling allows for zero-shot generalization to new tasks (new weight vectors w) if the features φ are shared, a powerful mechanism for transfer learning.

A distance function between states that measures behavioral equivalence. Two states are bisimilar if they share the same immediate reward and lead to equivalent future state distributions under any action. The bisimulation metric quantifies how close states are to being bisimilar. Successor representations are closely linked to this concept: the successor representation matrix itself can be used to derive a bisimulation metric. States with similar rows in this matrix will have similar long-term futures and are therefore behaviorally similar, providing a theoretically grounded method for state abstraction.

A formalism for temporal abstraction in RL. An option is a triple (I, π, β):

• I: The initiation set of states where the option can start.
• π: The option's internal policy.
• β: The termination condition (probability of stopping in a state). Successor representations naturally extend to the options framework. The option-conditional successor representation predicts state occupancy under a specific option's policy. This allows for planning and value estimation over temporally extended actions, bridging low-level control with high-level task decomposition.

An online control method that repeatedly solves a finite-horizon optimization problem. At each timestep, MPC:

1. Uses a dynamics model to predict future states over a horizon.
2. Optimizes a sequence of actions to maximize predicted reward.
3. Executes only the first action before replanning. While MPC typically uses a learned or analytical forward model, successor representations offer an alternative. By encoding long-term state predictions, they can be used for implicit planning over longer horizons than typical MPC, trading off the exactness of short-term rollouts for efficient long-horizon value estimation.