# What is the difference between an on-policy distribution and state visitation frequency?

On-policy distribution is defined as follows in Sutton and Barto: On the other hand, state visitation frequency is defined as follows in Trust Region Policy Optimization:

$$\rho_{\pi}(s) = \sum_{t=0}^{T} \gamma^t P(s_t=s|\pi)$$

Question: What is the difference between an on-policy distribution and state visitation frequency?

• Where are you getting the definition of state visitation from, exactly (it's probably S&B again, but I'd like to know which chapter and section)? I am asking because the term is being defined for a purpose - also note unlike the distribution, its value can be above 1 for any given state. Dec 8, 2021 at 18:56
• Definition of state visitation is from TRPO paper. Dec 9, 2021 at 16:05
• In the TRPO paper, $\rho_{\pi}(s) = P(s_0=s) + \gamma P(s_1=s) + \gamma^2 P(s_2=s) + \dots$ and goes on forever not until $T$, at least, that's how it seems to be defined. You can find it under equation 1 and they don't call it exactly "state visitation frequency" but "(unnormalized) discounted visitation frequencies"
– nbro
Jan 29 at 13:18

1.First of all. The on-policy distribution $$\mu(s)$$ is a probability distribution. So, obviously, it is different from state visitation frequency $$\rho_\pi(s)$$, since $$\rho_\pi(s)$$ is not normalized to $$1$$. In the following discussion I'll assume that we are interested in the difference between TRPO's state visitation frequency $$\rho_\pi(s)$$ and Sutton and Barto's "time spent in a state" $$\eta(s)$$.

2. Continuing task setting. The TRPO paper you are referring to never considers episodic tasks and your expression for $$\rho_\pi(s)$$ is not present in the paper. So, first I'll derive the equality for discounted infinite sum. First, we start with basic MDP probability relations: $$\begin{array}{rcl} P(s_0 = s) & = & h(s) \\ P(s_t = s) & = & \displaystyle\sum_{\bar{s}}P(s_{t-1} = \bar{s})\displaystyle\sum_{a}\pi(a|\bar{s})p(s|\bar{s},a) \quad \text{for}\quad t \ge 1 \end{array}$$

The second equation can be derived using the law of total probability and marginalization.

Multiply the second equation by $$\gamma^t$$ and summing by $$t$$. Note that I'm summing form $$t=1$$ to infinity: $$\begin{array}{rcl} \displaystyle\sum_{t=1}^\infty \gamma^tP(s_t = s) & = & \displaystyle\sum_{t=1}^\infty \gamma^t\displaystyle\sum_{\bar{s}}P(s_{t-1} = \bar{s})\displaystyle\sum_{a}\pi(a|\bar{s})p(s|\bar{s},a)\\ & = & \gamma \displaystyle\sum_{\bar{s}}\left(\displaystyle\sum_{t=1}^\infty \gamma^{t-1}P(s_{t-1} = \bar{s})\right)\displaystyle\sum_{a}\pi(a|\bar{s})p(s|\bar{s},a) \end{array}$$ Next I'm adding the $$P(s_0=s)=h(s)$$ equation to both sides, and I'm shifting the summation bounds $$(\sum_{t=1}^\infty \alpha_{t-1} = \sum_{t=0}^\infty \alpha_{t} )$$ for the sum in curly brackets. $$\begin{array}{rcl} \displaystyle\sum_{t=0}^\infty \gamma^tP(s_t = s) & = & h(s) + \gamma \displaystyle\sum_{\bar{s}}\left(\displaystyle\sum_{t=0}^\infty \gamma^{t}P(s_t = \bar{s})\right)\displaystyle\sum_{a}\pi(a|\bar{s})p(s|\bar{s},a) \end{array}$$ The expression in curly brackets is the same as expression on the lhs and the same as $$\rho_\pi(s)$$ (for $$T=\infty$$).

$$\rho_\pi(s) = h(s) + \gamma \displaystyle\sum_{\bar{s}}\rho_\pi(\bar{s})\displaystyle\sum_{a}\pi(a|\bar{s})p(s|\bar{s},a)$$

And that is the same equation as Sutton and Barto have for $$\eta(s)$$ - the "time spent in a state $$s$$". (They do mention the $$\gamma$$ factor in the quoted text.) So one can say that TRPO's $$\rho_\pi(s)$$ is the same as Sutton and Barto's $$\eta(s)$$ - at least in case of $$T=\infty$$.

3. Episodic task setting. In the episodic task setting (which is, again, is not considered in the TRPO paper) the derivation above is almost identical. A very important detail is the caveat that is mentioned in the quoted text: the whole expression is defined for the set of non-terminal states $$s\in{\mathcal{S}}$$. (Check the definitions of $$\mathcal{S}$$ and $$\mathcal{S}^+$$ in the section 3.3). The summation over $$\bar{s}$$ is, thus, also goes over $$\mathcal{S}$$ and this justifies the "shifting of the summation bounds" step in the derivation above:

$$\displaystyle\sum_{\bar{s}\in\mathcal{S}}\left(\displaystyle\sum_{t=1}^T\gamma^{t-1}P(s_{t-1} = \bar{s})\right) \cdots = \displaystyle\sum_{\bar{s}\in\mathcal{S}}\left(\displaystyle\sum_{t=0}^T\gamma^{t}P(s_t = \bar{s})\right) \cdots$$

This works because $$s_T$$ is always the terminal state, so $$P(s_T = \bar{s}) = 0$$ and one can add this term to the sum.