Successor Representation

The successor matrix encodes the expected discounted future occupancy of every state j given a start in state i under a fixed policy. Unlike a value function, this map is reward-independent, meaning it captures the agent's pure temporal dynamics. The expected number of visits to each future state is weighted by a discount factor γ, creating a diffusion-like model of navigation. This allows the agent to plan efficiently by simply re-weighting the SR with a new reward function, without re-learning the environment's transition structure.

The SR cleanly factorizes the value function into two distinct components: the successor matrix M and the reward vector R. Formally, V(s) = Σ M(s, s') × R(s'). This separation explains why an agent can rapidly re-evaluate goals—the heavy lifting of learning state transitions is done once, and only the reward weights need updating. This factorization provides a direct window into the agent's temporal credit assignment, showing exactly which future states contribute to current value.

The successor matrix can be learned via a temporal difference (TD) update rule analogous to TD learning for values. The error signal is the difference between a one-step sample of the successor features and the current estimate. This bootstrapping mechanism allows the agent to incrementally build its predictive map from sequential experience. The learning process itself is interpretable: the SR error at each step reveals where the agent's internal model of state transitions is inconsistent with reality.

The SR originated as a computational model of hippocampal place cells and grid cells. It explains why place cell firing fields skew toward goals and why grid cells exhibit a multi-scale metric of space. The SR predicts that neurons in the hippocampus encode not just current location but a predictive representation of imminent states. This biological grounding makes the SR a compelling bridge between machine learning and cognitive science, offering a normative explanation for neural replay during rest and planning.

Extending the SR to high-dimensional state spaces, successor features (SF) replace discrete states with learned feature vectors φ(s). The agent learns to predict the expected discounted sum of future features rather than raw state occupancies. This enables zero-shot task transfer: given a new reward function defined as a linear weighting of features, the agent can compute the optimal value function instantly without any new learning. This provides a formal explanation for how agents generalize across related tasks.

The eigenvectors of the successor matrix reveal the slowest mixing modes of the environment's transition dynamics. These principal components correspond to large-scale spatial or abstract partitions of the state space, effectively performing a spectral clustering of the agent's world. The eigenvalues encode the temporal persistence of each mode. This decomposition provides a mathematically rigorous explanation of how an agent implicitly discovers hierarchical structure and bottleneck states purely from its predictive model of the future.