5
$\begingroup$

On-policy distribution is defined as follows in Sutton and Barto:

enter image description here

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Dec 8, 2021 at 18:56
  • 1
    $\begingroup$ Definition of state visitation is from TRPO paper. $\endgroup$
    – user529295
    Dec 9, 2021 at 16:05
  • $\begingroup$ 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" $\endgroup$
    – nbro
    Jan 29, 2023 at 13:18

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .