Answers.Body: <p>This question is really getting at the meaning of the discount factor in Markov decision processes. There are actually two, equivalent ways of interpreting the discount factor.</p>
  <p>The first is probably what you're familiar with: the <span class="math-container">$i^{th}$</span> step receives a reward of <span class="math-container">$\gamma^{i}r_i$</span> instead of just <span class="math-container">$r_i$</span>.</p>
  <p>The second, equivalent interpretation, is that at every step, we have a <span class="math-container">$1-\gamma$</span> chance of immediately ending the episode. Assuming we don't end the episode, we receive the full <span class="math-container">$r_i$</span> reward. This is what Sutton and Barto mean by termination. Note that under the second interpretation, we have a <span class="math-container">$\gamma^i$</span> probability of reaching the <span class="math-container">$i^{th}$</span> step, hence the connection to the first interpretation.</p>
  <p>Your definition of <span class="math-container">$\eta_{\gamma}(s)$</span> looks correct to me. Alternatively, we can write it in Sutton's, Barto's notation like
  <span class="math-container">$$\eta_{\gamma}(s) = h(s) + \sum_{\bar s}\eta(\bar s)\sum_{a}\gamma \pi(a | \bar s) p(s | \bar s, a)$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-14T16:49:37.470Z
Answers.LastActivityDate: 2021-05-14T18:23:06.917Z
Answers.LastEditDate: 2021-05-14T18:23:06.917Z
Answers.UserDisplayName: Taw
Body: <p>In <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=221" rel="nofollow noreferrer">Reinforcement Learning: An Introduction, section 9.2 (page 199)</a>, Sutton and Barto describe the on-policy distribution in episodic tasks, with <span class="math-container">$\gamma =1$</span>, as being</p>
  <p><span class="math-container">\begin{equation}
  \mu(s) = \frac{\eta(s)}{\sum_{k \in S} \eta(k)},
  \end{equation}</span></p>
  <p>where</p>
  <p><span class="math-container">\begin{equation}
  \eta(s) = h(s) + \sum_s \eta(\bar{s}) \sum_a \pi(a|\bar{s})p(s|\bar{s},a), \text{  (9.2)}
  \end{equation}</span></p>
  <p>is the number of time steps spent, on average, in state <span class="math-container">$s$</span> in a single episode.</p>
  <p>Another way to represent this is setting <span class="math-container">$\eta(s) = \sum_{t=0}^{\infty} d_{j,s}^{(t)}$</span>, the average number of visits to <span class="math-container">$s$</span> starting from <span class="math-container">$j$</span>, and <span class="math-container">$d_{j,s}^{(t)}$</span> being the probability of going from <span class="math-container">$j$</span> to <span class="math-container">$s$</span> in <span class="math-container">$t$</span> steps under policy <span class="math-container">$\pi_{\theta}$</span>. In particular, <span class="math-container">$d_{j,s}^{(1)} = d_{j,s} = \sum_{a \in A}[\pi_{\theta}(a|j)P(s|j,a)]$</span>. This formulation is obtained through pag 325 proof of the Policy Gradient Theorem (PGT) and some basic stochastic processes theory.</p>
  <p>If instead of defining <span class="math-container">$\gamma = 1$</span>, we prove PGT using any <span class="math-container">$\gamma \in (0,1)$</span>, we would get</p>
  <p><span class="math-container">\begin{equation*}
  \eta_{\gamma}(s) = \sum_{t=0}^{\infty} \gamma^t d_{j,s}^{(t)}
  \end{equation*}</span></p>
  <p>This is not anymore the average number of visits to <span class="math-container">$s$</span>. Here comes my <em>first question</em>. Would we still get a <span class="math-container">$\mu_{\gamma}$</span> on-policy distribution through the same trick done before? That is
  <span class="math-container">\begin{equation}
  \mu_{\gamma}(s) = \frac{\eta_{\gamma}(s)}{\sum_{k \in S} \eta_{\gamma}(k)},
  \end{equation}</span>
  would be the on-policy distribution?</p>
  <p>My <em>second question</em> is related and has to do with the phrase on page 199, that says that</p>
  <blockquote>
  <p>If there is discounting (<span class="math-container">$\gamma &lt;1$</span>) it should be treated as a form of termination, which can be done simply by including a factor of <span class="math-container">$\gamma$</span> in the second term of (9.2).</p>
  </blockquote>
  <p>What the authors mean by &quot;as a form of termination&quot;?</p>
  <p>As inferred by my previous question, my conclusion is that having <span class="math-container">$\gamma &lt; 1$</span> does not alter <span class="math-container">$\mu_{\gamma}$</span> being the on-policy distribution, so I don't get this last comment on page 199.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-14T00:19:07.253Z
Comments.Text: [related question](https://ai.stackexchange.com/questions/27172/why-do-we-discount-the-state-distribution)
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-14T11:20:02.470Z
Comments.Text: as far as I know (I may be wrong so I don't want to post an official answer) you are correct. By your notation $\eta_\gamma(s)$ is a discounted weighting of being in state $s$ from some initial state when following $\pi$ and your $\mu_\gamma(s)$ is still a state distribution because it has been normalised. 
  
  As for your second question, the comment is there to help you conceptualise what a discount factor does to the state distribution (though I don't think it is useful, not for me anyway).
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-14T11:21:36.473Z
Comments.Text: I like to think that we need to discount the state distribution for the same reason we discount rewards: because in the future we care less (measured by $\gamma$) about these future values. In function approximation the measure we use to assess our approximators is averaged over the state distribution, but if we care less about what happens in the future then it makes sense that we must also discount future states because we care less about these future states.
Comments.UserDisplayName: David
Tags: <reinforcement-learning><policy-gradients><sutton-barto><on-policy-methods><discount-factor>
Title: If $\gamma \in (0,1)$, what is the on-policy state distribution for episodic tasks?
UserDisplayName: Felipe Costa
ThreadText: # If $\gamma \in (0,1)$, what is the on-policy state distribution for episodic tasks?
  
  (Asked by: username_0 on 2021-05-13)
  
  In [Reinforcement Learning: An Introduction, section 9.2 (page 199)](http://incompleteideas.net/book/RLbook2020.pdf#page=221), Sutton and Barto describe the on-policy distribution in episodic tasks, with $\gamma =1$, as being
  
  \begin{equation}
  \mu(s) = \frac{\eta(s)}{\sum\_{k \in S} \eta(k)},
  \end{equation}
  
  where
  
  \begin{equation}
  \eta(s) = h(s) + \sum\_s \eta(\bar{s}) \sum\_a \pi(a|\bar{s})p(s|\bar{s},a), \text{ (9.2)}
  \end{equation}
  
  is the number of time steps spent, on average, in state $s$ in a single episode.
  
  Another way to represent this is setting $\eta(s) = \sum\_{t=0}^{\infty} d\_{j,s}^{(t)}$, the average number of visits to $s$ starting from $j$, and $d\_{j,s}^{(t)}$ being the probability of going from $j$ to $s$ in $t$ steps under policy $\pi\_{\theta}$. In particular, $d\_{j,s}^{(1)} = d\_{j,s} = \sum\_{a \in A}[\pi\_{\theta}(a|j)P(s|j,a)]$. This formulation is obtained through pag 325 proof of the Policy Gradient Theorem (PGT) and some basic stochastic processes theory.
  
  If instead of defining $\gamma = 1$, we prove PGT using any $\gamma \in (0,1)$, we would get
  
  \begin{equation\*}
  \eta\_{\gamma}(s) = \sum\_{t=0}^{\infty} \gamma^t d\_{j,s}^{(t)}
  \end{equation\*}
  
  This is not anymore the average number of visits to $s$. Here comes my *first question*. Would we still get a $\mu\_{\gamma}$ on-policy distribution through the same trick done before? That is
  \begin{equation}
  \mu\_{\gamma}(s) = \frac{\eta\_{\gamma}(s)}{\sum\_{k \in S} \eta\_{\gamma}(k)},
  \end{equation}
  would be the on-policy distribution?
  
  My *second question* is related and has to do with the phrase on page 199, that says that
  
  > If there is discounting ($\gamma <1$) it should be treated as a form of termination, which can be done simply by including a factor of $\gamma$ in the second term of (9.2).
  
  What the authors mean by "as a form of termination"?
  
  As inferred by my previous question, my conclusion is that having $\gamma < 1$ does not alter $\mu\_{\gamma}$ being the on-policy distribution, so I don't get this last comment on page 199.
  
  **Tags:** reinforcement-learning, policy-gradients, sutton-barto, on-policy-methods, discount-factor
  
  > **Comments:**
  > **username_1**: [related question](https://ai.stackexchange.com/questions/27172/why-do-we-discount-the-state-distribution)  
  > **username_1**: as far as I know (I may be wrong so I don't want to post an official answer) you are correct. By your notation $\eta_\gamma(s)$ is a discounted weighting of being in state $s$ from some initial state when following $\pi$ and your $\mu_\gamma(s)$ is still a state distribution because it has been normalised.   As for your second question, the comment is there to help you conceptualise what a discount factor does to the state distribution (though I don't think it is useful, not for me anyway).  
  > **username_1**: I like to think that we need to discount the state distribution for the same reason we discount rewards: because in the future we care less (measured by $\gamma$) about these future values. In function approximation the measure we use to assess our approximators is averaged over the state distribution, but if we care less about what happens in the future then it makes sense that we must also discount future states because we care less about these future states.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-05-14. Score: 5 | Accepted answer
  
  This question is really getting at the meaning of the discount factor in Markov decision processes. There are actually two, equivalent ways of interpreting the discount factor.
  
  The first is probably what you're familiar with: the $i^{th}$ step receives a reward of $\gamma^{i}r\_i$ instead of just $r\_i$.
  
  The second, equivalent interpretation, is that at every step, we have a $1-\gamma$ chance of immediately ending the episode. Assuming we don't end the episode, we receive the full $r\_i$ reward. This is what Sutton and Barto mean by termination. Note that under the second interpretation, we have a $\gamma^i$ probability of reaching the $i^{th}$ step, hence the connection to the first interpretation.
  
  Your definition of $\eta\_{\gamma}(s)$ looks correct to me. Alternatively, we can write it in Sutton's, Barto's notation like
  $$\eta\_{\gamma}(s) = h(s) + \sum\_{\bar s}\eta(\bar s)\sum\_{a}\gamma \pi(a | \bar s) p(s | \bar s, a)$$
  
  
  ---
  
  