Successor representation

Overview

An alternative to both model-free and model-based representations of a reinforcement learning environment is successor representation, which encodes an “occupancy count” for each state based on whether they predict visiting other states when following some policy.

Successor representation

The successor representation for a policy $\pi :\mathcal{S}\to \Delta (\mathcal{A})$ is defined for all $s,s^{+}\in \mathcal{S}$, where $s$ is a current state and $s^{+}$ is a future state, by

$$M^{\pi }(s^{+}|s)={\mathbb{E}}_{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^{t}1[s_t=s^{+}]|s_0=s\right],$$

where $1[s_t=s^{+}]$ is the indicator function that returns $1$ when the current state $s_t$ is $s$ and $0$ otherwise.

• Indicator fn like reward fn?

---

Recursive equations for SR

Equation: Recursive equations for SR

For any policy $\pi :\mathcal{S}\to \Delta (\mathcal{A})$, the successor representation for a current state $s$ and future state $s^{+}$ can be computed by

$$M^{\pi }(s^{+}|s)=1[s^{+}=s]+\gamma \sum _{a\in \mathcal{A}}\pi (a|s)\sum _{s^{\prime }\in \mathcal{S}}T(s^{\prime }|s,a)M^{\pi }(s^{+}|s).$$

If $\pi :\mathcal{S}\to \mathcal{A}$ is a deterministic policy, we have

$$M^{\pi }(s^{+}\mid s)=1[s^{+}=s]+\gamma \sum _{s^{\prime }\in \mathcal{S}}T(s^{\prime }|s,\pi (s))M^{\pi }(s^{+}|s^{\prime }).$$

---

Computing state value from the SR

Expressing the value of a state using SR and state reward

Let $\pi :\mathcal{S}\to \Delta (\mathcal{A})$ be a policy for acting in a Markov decision process with reward function $R:\mathcal{S}\times \mathcal{A}\times \mathcal{S}\to \mathbb{R}$, and let

$$R^{\pi }(s)=\sum _a\pi (a\mid s)\sum _{s’}T(s’\mid s,a)R(s,a,s’)$$

be the state reward function associated with $\pi$. Then the state value function can be computed as a linear combination of the successor representation and state reward function:

$$v_{\pi }(s)=\sum _{s^{+}}{M}^{\pi }(s,s^{+})R^{\pi }(s^{+}).$$

Proof adapted from @2024griffithsBayesian, p. 214. We have

$$\begin{array}{rl}{v}_{\pi }(s)& =\sum _{s^{+}}M(s^{+}\mid s)R^{\pi }(s)\\ & =\sum _{s^{+}}\left(1[s=s^{+}]+\gamma \sum _a\pi (a\mid s)\sum _{s^{\prime }}T(s^{\prime }\mid s,a)M^{\pi }(s^{+}\mid s^{\prime })\right)R^{\pi }(s^{+})\\ & =\sum _{s^{+}}1[s=s^{+}]R^{\pi }(s^{+})+\gamma \sum _a\pi (a\mid s)\sum _{s^{\prime }}T(s^{\prime }\mid s,a)\sum _{s^{+}}{M}^{\pi }(s^{+}\mid s^{\prime })R^{\pi }(s^{+})\\ & =R^{\pi }(s)+\gamma \sum _a\pi (a\mid s)\sum _{s^{\prime }}T(s^{\prime }\mid s,a)v_{\pi }(s^{\prime })\\ & =\sum _a\pi (a\mid s)\sum _{s^{\prime }}T(s^{\prime }\mid s,a)R(s,a,s^{\prime })+\gamma \sum _a\pi (a\mid s)\sum _{s^{\prime }}T(s^{\prime }\mid s,a)v_{\pi }(s^{\prime })\\ & =\sum _a\pi (a\mid s)\sum _{s^{\prime }}T(s^{\prime }\mid s,a)[R(s,a,s^{\prime })+\gamma v_{\pi }(s^{\prime })],\end{array}$$

where the fourth line expresses $v_{\pi }(s)$ as a sum of expected immediate reward and expected discounted future value

$$v_{\pi }(s)=R^{\pi }(s)+\gamma {\mathbb{E}}_{a\sim \pi ,s^{\prime }\sim T}[v_{\pi }(s^{\prime })],$$

and the final equality gives the familiar Bellman equation for state value. $\square$