Answers.Body: <p><strong>1.First of all</strong>. The on-policy distribution <span class="math-container">$\mu(s)$</span> is a probability distribution. So, obviously, it is different from state visitation frequency <span class="math-container">$\rho_\pi(s)$</span>, since <span class="math-container">$\rho_\pi(s)$</span> is not normalized to <span class="math-container">$1$</span>. In the following discussion I'll assume that we are interested in the difference between TRPO's state visitation frequency <span class="math-container">$\rho_\pi(s)$</span> and Sutton and Barto's &quot;time spent in a state&quot; <span class="math-container">$\eta(s)$</span>.</p>
  <p><strong>2. Continuing task setting.</strong> The TRPO paper you are referring to never considers episodic tasks and your expression for <span class="math-container">$\rho_\pi(s)$</span> 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:
  <span class="math-container">$$ \begin{array}{rcl}
  P(s_0 = s) &amp; = &amp; h(s) \\
  P(s_t = s) &amp; = &amp; \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}$$</span></p>
  <p>The second equation can be derived using the <a href="https://en.wikipedia.org/wiki/Law_of_total_probability" rel="nofollow noreferrer">law of total probability</a> and <a href="https://en.wikipedia.org/wiki/Marginal_distribution" rel="nofollow noreferrer">marginalization</a>.</p>
  <p>Multiply the second equation by <span class="math-container">$\gamma^t$</span> and summing by <span class="math-container">$t$</span>. Note that I'm summing form <span class="math-container">$t=1$</span> to infinity:
  <span class="math-container">$$ \begin{array}{rcl}
  \displaystyle\sum_{t=1}^\infty \gamma^tP(s_t = s) &amp; = &amp; \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)\\
   &amp; = &amp; \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}$$</span>
  Next I'm adding the <span class="math-container">$P(s_0=s)=h(s)$</span> equation to both sides, and I'm shifting the summation bounds <span class="math-container">$(\sum_{t=1}^\infty \alpha_{t-1} = \sum_{t=0}^\infty \alpha_{t} )$</span> for the sum in curly brackets.
  <span class="math-container">$$ \begin{array}{rcl}
  \displaystyle\sum_{t=0}^\infty \gamma^tP(s_t = s) &amp; = &amp; 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}$$</span>
  The expression in curly brackets is the same as expression on the lhs and the same as <span class="math-container">$\rho_\pi(s)$</span> (for <span class="math-container">$T=\infty$</span>).</p>
  <p><span class="math-container">$$\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)
  $$</span></p>
  <p>And that is the same equation as Sutton and Barto have for <span class="math-container">$\eta(s)$</span> - the &quot;time spent in a state <span class="math-container">$s$</span>&quot;. (They do mention the <span class="math-container">$\gamma$</span> factor in the quoted text.) So one can say that TRPO's <span class="math-container">$\rho_\pi(s)$</span> is the same as Sutton and Barto's <span class="math-container">$\eta(s)$</span> - at least in case of <span class="math-container">$T=\infty$</span>.</p>
  <p><strong>3. Episodic task setting.</strong> In the episodic task setting (which is, again, is <em>not</em> 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 <span class="math-container">$s\in{\mathcal{S}}$</span>. (Check the definitions of <span class="math-container">$\mathcal{S}$</span> and <span class="math-container">$\mathcal{S}^+$</span> in the section 3.3). The summation over <span class="math-container">$\bar{s}$</span> is, thus, also goes over <span class="math-container">$\mathcal{S}$</span> and this justifies the &quot;shifting of the summation bounds&quot; step in the derivation above:</p>
  <p><span class="math-container">$$ \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$$</span></p>
  <p>This works because <span class="math-container">$s_T$</span> is always the terminal state, so <span class="math-container">$P(s_T = \bar{s}) = 0$</span> and one can add this term to the sum.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-29T18:42:20.503Z
Answers.LastActivityDate: 2023-01-30T09:37:24.480Z
Answers.LastEditDate: 2023-01-30T09:37:24.480Z
Answers.UserDisplayName: Kostya
Body: <p>On-policy distribution is defined as follows in Sutton and Barto:</p>
  <p><a href="https://i.sstatic.net/lf1Q3.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lf1Q3.png" alt="enter image description here" /></a></p>
  <p>On the other hand, state visitation frequency is defined as follows in <a href="https://arxiv.org/pdf/1502.05477.pdf" rel="nofollow noreferrer">Trust Region Policy Optimization</a>:</p>
  <p><span class="math-container">$$\rho_{\pi}(s) = \sum_{t=0}^{T} \gamma^t P(s_t=s|\pi)$$</span></p>
  <p><strong>Question:</strong> What is the difference between an on-policy distribution and state visitation frequency?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-08T18:56:44.827Z
Comments.Text: 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.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-09T16:05:30.273Z
Comments.Text: Definition of state visitation is from TRPO paper.
Comments.UserDisplayName: user529295
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-01-29T13:18:01.957Z
Comments.Text: 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"
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><comparison><sutton-barto><trust-region-policy-optimization><on-policy-distribution>
Title: What is the difference between an on-policy distribution and state visitation frequency?
UserDisplayName: user529295
ThreadText: # What is the difference between an on-policy distribution and state visitation frequency?
  
  (Asked by: username_0 on 2021-12-08)
  
  On-policy distribution is defined as follows in Sutton and Barto:
  
  [![enter image description here](https://i.sstatic.net/lf1Q3.png)](https://i.sstatic.net/lf1Q3.png)
  
  On the other hand, state visitation frequency is defined as follows in [Trust Region Policy Optimization](https://arxiv.org/pdf/1502.05477.pdf):
  
  $$\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?
  
  **Tags:** reinforcement-learning, comparison, sutton-barto, trust-region-policy-optimization, on-policy-distribution
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: Definition of state visitation is from TRPO paper.  
  > **username_2**: 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"  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2023-01-29. Score: 2
  
  **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](https://en.wikipedia.org/wiki/Law_of_total_probability) and [marginalization](https://en.wikipedia.org/wiki/Marginal_distribution).
  
  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.
  
  
  ---
  
  