Answers.Body: <p>It's a subtle issue.</p>
  
  <p>If you look at the A3C algorithm in the <a href="https://arxiv.org/abs/1602.01783" rel="nofollow noreferrer">original paper</a> (p.4 and appendix S3 for pseudo-code), their actor-critic algorithm (same algorithm both episodic and continuing problems) is off by a factor of gamma relative to the actor-critic pseudo-code for episodic problems in the Sutton and Barto book (p.332 of January 2019 edition of <a href="http://incompleteideas.net/book/the-book.html" rel="nofollow noreferrer">http://incompleteideas.net/book/the-book.html</a>).  The Sutton and Barto book has the extra "first" gamma as labeled in your picture. So, either the book or the A3C paper is wrong?  Not really.</p>
  
  <p>The key is on p. 199 of the Sutton and Barto book:</p>
  
  <blockquote>
    <p>If there is discounting (gamma &lt; 1) it
    should be treated as a form of termination, which can be done simply by including
    a factor of in the second term of (9.2).</p>
  </blockquote>
  
  <p>The subtle issue is that there are two interpretations to the discounting factor gamma:</p>
  
  <ol>
  <li>A multiplicative factor that puts less weight on distant future rewards.</li>
  <li>A probability, 1 - gamma, that a simulated trajectory spuriously terminates, at any time step.  This interpretation only makes sense for episodic cases, and not continuing cases.</li>
  </ol>
  
  <p>Literal implementations:</p>
  
  <ol>
  <li>Just multiply the future rewards and related quantities (V or Q) in the future by gamma.</li>
  <li>Simulate some trajectories and randomly terminate (1 - gamma) of them at each time step.  Terminated trajectories give no immediate or future rewards.</li>
  </ol>
  
  <p>The two interpretations of gamma are valid.  But choosing one or the other means you are tackling a different problem.  The math is slightly different and you end up with an extra gamma multiplying <span class="math-container">$G \nabla\ln\pi(a|s)$</span> with the second interpretation.  </p>
  
  <p>For example, if you are at step t=2 and gamma = 0.9, the algorithm for the second interpretation is that the policy gradient is <span class="math-container">$\gamma^2 G \nabla\ln\pi(a|s)$</span> or <span class="math-container">$0.81 G \nabla\ln\pi(a|s)$</span>.  This term has 19% less gradient power than the t=0 term for the simple reason that 19% of simulated trajectories have died off by t=2.  </p>
  
  <p>With the first interpretation of gamma, there is no such 19% decay. The policy gradient is just <span class="math-container">$G \nabla\ln\pi(a|s)$</span> at t=2.  But gamma is still present within <span class="math-container">$G$</span> to discount the future rewards.</p>
  
  <p>You can choose whichever interpretation of gamma, but you have to be mindful of the consequences to the algorithm.  I personally prefer to stick with interpretation 1 just because it's simpler.  So I use the algorithm in the A3C paper, not the Sutton and Barto book.  </p>
  
  <p>Your question was about the REINFORCE algorithm, but I have been discussing actor-critic.  You have the exact same issue related to the two gamma interpretations and the extra gamma in REINFORCE.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-22T00:48:13.163Z
Answers.LastActivityDate: 2019-01-22T00:57:07.377Z
Answers.LastEditDate: 2019-01-22T00:57:07.377Z
Answers.UserDisplayName: toto2
Answers.Body: <p>Neil's answer already provides some intuition as to why the pseudocode (with the extra $\gamma^t$ term) is correct.</p>
  
  <p>I'd just like to additionally clarify that you do not seem to be misunderstanding anything, <strong>Equation (13.6) in the book is indeed different from the pseudocode</strong>. </p>
  
  <p>Now, I don't have the edition of the book that you mentioned right here, but I do have a later draft from March 22, 2018, and the text on this particular topic seems to be similar. In this edition:</p>
  
  <ul>
  <li>Near the end of page 326, it is explicitly mentioned that they'll assume $\gamma = 1$ in their proof for the Policy Gradient Theorem.</li>
  <li>That proof eventually leads to the same Equation (13.6) on page 329.</li>
  <li>Immediately below the pseudocode, on page 330, they actually briefly address the difference between the Equation and the pseudocode, saying that that difference is due to the assumption of $\gamma = 1$ in the proof.</li>
  <li>Right below that, in <em>Exercise 13.2</em>, they give some hints as for what you should be looking at if you'd like to derive the modified proof for the case where $\gamma &lt; 1$.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-22T19:19:27.853Z
Answers.Text: Thanks. The explanation of your third point was missing on the 2017 draft.
Answers.UserDisplayName: Diego Orellana
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-22T19:22:46.473Z
Answers.Text: @DiegoOrellana I can't find a link to the March 22 draft anymore, there appears to be an even later draft (can't find a date mentioned) [here](https://drive.google.com/file/d/1xeUDVGWGUUv1-ccUMAZHJLej2C7aAFWY/view). This version actually has a fancy cover, so it might even be a final version rather than a draft. If the link does get broken in the future, I suspect a new link will be made available [here](http://incompleteideas.net/book/the-book-2nd.html).
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-22T19:11:14.863Z
Answers.LastActivityDate: 2018-08-22T19:11:14.863Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>I would like to follow up on @toto2's answer about the first interpretation of gamma. (I'm a new user and can't post a comment.)</p>
  <p>Does it make sense to include <span class="math-container">$\gamma$</span> in the  return and the state and action value functions without considering it as part of the MDP? (interpretation 2).</p>
  <p>If one derives the policy gradient with respect to the discounted return as the objective, then the discounted state distribution arises (the one corresponding to interpretation 2), not the original one. <a href="https://proceedings.neurips.cc/paper/1999/file/464d828b85b0bed98e80ade0a5c43b0f-Paper.pdf" rel="nofollow noreferrer">Proof here.</a></p>
  <p>This seems to mean that you can't have interpretation 1 without interpretation 2.</p>
  <p>I would be happy to discuss this further.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-06T06:59:51.633Z
Answers.Text: To follow up with a question, instead of adding as an answer, you should ask a new question on the site. You can link toto2's answer in that question (but please add a brief summary including the key 2 interpretations as a quote).
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-06T15:07:05.077Z
Answers.Text: This does not provide an answer to the question. Once you have sufficient [reputation](https://ai.stackexchange.com/help/whats-reputation) you will be able to [comment on any post](https://ai.stackexchange.com/help/privileges/comment); instead, [provide answers that don't require clarification from the asker](https://meta.stackexchange.com/questions/214173/why-do-i-need-50-reputation-to-comment-what-can-i-do-instead). - [From Review](/review/late-answers/21597)
Answers.UserDisplayName: Rob
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-06T17:19:28.533Z
Answers.Text: Sure. It's [here](https://ai.stackexchange.com/questions/36234/what-is-the-correct-interpretation-of-the-discount-factor-in-mdps).
Answers.UserDisplayName: Skander
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-06T00:43:09.983Z
Answers.LastActivityDate: 2022-07-06T00:43:09.983Z
Answers.UserDisplayName: Skander
Answers.Body: <p>The discount factor does appear twice, and this is correct.</p>
  <p>This is because the function you are trying to maximise in REINFORCE for an episodic problem (by taking the gradient) is the expected return from a given (distribution of) start state:</p>
  <p><span class="math-container">$$J(\theta) = \mathbb{E}_{\pi(\theta)}[G_t|S_t = s_0, t=0]$$</span></p>
  <p>Therefore, during the episode, when you sample the returns <span class="math-container">$G_1$</span>, <span class="math-container">$G_2$</span> etc, these will be less relevant to the problem you are solving, reduced by the discount factor a second time as you noted. At the extreme with an episodic problem and <span class="math-container">$\gamma = 0$</span> then REINFORCE will only find an optimal policy for the first action.</p>
  <p>In continuing problems, you would use different formulations for <span class="math-container">$J(\theta)$</span>, and these do not lead to the extra factor of <span class="math-container">$\gamma^t$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-22T18:58:48.497Z
Answers.LastActivityDate: 2021-04-06T13:46:53.037Z
Answers.LastEditDate: 2021-04-06T13:46:53.037Z
Answers.UserDisplayName: Neil Slater
Body: <p>I was reading the book <a href="http://incompleteideas.net/book/bookdraft2017nov5.pdf" rel="noreferrer">Reinforcement Learning: An Introduction by Richard S. Sutton and Andrew G. Barto</a> (complete draft, November 5, 2017). </p>
  
  <p>On page 271, the pseudo-code for the episodic Monte-Carlo Policy-Gradient Method is presented. Looking at this pseudo-code I can't understand why it seems that the discount rate appears 2 times, once in the update state and a second time inside the return. [See the figure below] </p>
  
  <p><a href="https://i.sstatic.net/dxDnP.png" rel="noreferrer"><img src="https://i.sstatic.net/dxDnP.png" alt="enter image description here"></a></p>
  
  <p>It seems that the return for the steps after step 1 are just a truncation of the return of the first step. Also, if you look just one page above in the book you find an equation with just 1 discount rate (the one inside the return.) </p>
  
  <p>Why then does the pseudo-code seem to be different? My guess is that I am misunderstanding something: </p>
  
  <p><span class="math-container">$$
  {\mathbf{\theta}}_{t+1} ~\dot{=}~\mathbf{\theta}_t + \alpha G_t \frac{{\nabla}_{\mathbf{\theta}} \pi \left(A_t \middle| S_t, \mathbf{\theta}_{t} \right)}{\pi \left(A_t \middle| S_t, \mathbf{\theta}_{t} \right)}.
  \tag{13.6}
  $$</span></p>
  
Tags: <reinforcement-learning><algorithm><sutton-barto><reinforce>
Title: Why does the discount rate in the REINFORCE algorithm appear twice?
UserDisplayName: Diego Orellana
ThreadText: # Why does the discount rate in the REINFORCE algorithm appear twice?
  
  (Asked by: username_0 on 2018-08-22)
  
  I was reading the book [Reinforcement Learning: An Introduction by Richard S. Sutton and Andrew G. Barto](http://incompleteideas.net/book/bookdraft2017nov5.pdf) (complete draft, November 5, 2017).
  
  On page 271, the pseudo-code for the episodic Monte-Carlo Policy-Gradient Method is presented. Looking at this pseudo-code I can't understand why it seems that the discount rate appears 2 times, once in the update state and a second time inside the return. [See the figure below]
  
  [![enter image description here](https://i.sstatic.net/dxDnP.png)](https://i.sstatic.net/dxDnP.png)
  
  It seems that the return for the steps after step 1 are just a truncation of the return of the first step. Also, if you look just one page above in the book you find an equation with just 1 discount rate (the one inside the return.)
  
  Why then does the pseudo-code seem to be different? My guess is that I am misunderstanding something:
  
  $$
  {\mathbf{\theta}}\_{t+1} ~\dot{=}~\mathbf{\theta}\_t + \alpha G\_t \frac{{\nabla}\_{\mathbf{\theta}} \pi \left(A\_t \middle| S\_t, \mathbf{\theta}\_{t} \right)}{\pi \left(A\_t \middle| S\_t, \mathbf{\theta}\_{t} \right)}.
  \tag{13.6}
  $$
  
  **Tags:** reinforcement-learning, algorithm, sutton-barto, reinforce
  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_4 on 2018-08-22. Score: 10 | Accepted answer
  
  The discount factor does appear twice, and this is correct.
  
  This is because the function you are trying to maximise in REINFORCE for an episodic problem (by taking the gradient) is the expected return from a given (distribution of) start state:
  
  $$J(\theta) = \mathbb{E}\_{\pi(\theta)}[G\_t|S\_t = s\_0, t=0]$$
  
  Therefore, during the episode, when you sample the returns $G\_1$, $G\_2$ etc, these will be less relevant to the problem you are solving, reduced by the discount factor a second time as you noted. At the extreme with an episodic problem and $\gamma = 0$ then REINFORCE will only find an optimal policy for the first action.
  
  In continuing problems, you would use different formulations for $J(\theta)$, and these do not lead to the extra factor of $\gamma^t$.
  
  
  ---
  
  ### Answer by username_2 on 2018-08-22. Score: 7
  
  username_4's answer already provides some intuition as to why the pseudocode (with the extra $\gamma^t$ term) is correct.
  
  I'd just like to additionally clarify that you do not seem to be misunderstanding anything, **Equation (13.6) in the book is indeed different from the pseudocode**.
  
  Now, I don't have the edition of the book that you mentioned right here, but I do have a later draft from March 22, 2018, and the text on this particular topic seems to be similar. In this edition:
  
  * Near the end of page 326, it is explicitly mentioned that they'll assume $\gamma = 1$ in their proof for the Policy Gradient Theorem.
  * That proof eventually leads to the same Equation (13.6) on page 329.
  * Immediately below the pseudocode, on page 330, they actually briefly address the difference between the Equation and the pseudocode, saying that that difference is due to the assumption of $\gamma = 1$ in the proof.
  * Right below that, in *Exercise 13.2*, they give some hints as for what you should be looking at if you'd like to derive the modified proof for the case where $\gamma < 1$.
  
  > **Comments:**
  > **username_0**: Thanks. The explanation of your third point was missing on the 2017 draft.  
  > **username_2**: @username_0 I can't find a link to the March 22 draft anymore, there appears to be an even later draft (can't find a date mentioned) [here](https://drive.google.com/file/d/1xeUDVGWGUUv1-ccUMAZHJLej2C7aAFWY/view). This version actually has a fancy cover, so it might even be a final version rather than a draft. If the link does get broken in the future, I suspect a new link will be made available [here](http://incompleteideas.net/book/the-book-2nd.html).  
  
  ---
  
  ### Answer by username_1 on 2019-01-22. Score: 3
  
  It's a subtle issue.
  
  If you look at the A3C algorithm in the [original paper](https://arxiv.org/abs/1602.01783) (p.4 and appendix S3 for pseudo-code), their actor-critic algorithm (same algorithm both episodic and continuing problems) is off by a factor of gamma relative to the actor-critic pseudo-code for episodic problems in the Sutton and Barto book (p.332 of January 2019 edition of <http://incompleteideas.net/book/the-book.html>). The Sutton and Barto book has the extra "first" gamma as labeled in your picture. So, either the book or the A3C paper is wrong? Not really.
  
  The key is on p. 199 of the Sutton and Barto book:
  
  > 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 in the second term of (9.2).
  
  The subtle issue is that there are two interpretations to the discounting factor gamma:
  
  1. A multiplicative factor that puts less weight on distant future rewards.
  2. A probability, 1 - gamma, that a simulated trajectory spuriously terminates, at any time step. This interpretation only makes sense for episodic cases, and not continuing cases.
  
  Literal implementations:
  
  1. Just multiply the future rewards and related quantities (V or Q) in the future by gamma.
  2. Simulate some trajectories and randomly terminate (1 - gamma) of them at each time step. Terminated trajectories give no immediate or future rewards.
  
  The two interpretations of gamma are valid. But choosing one or the other means you are tackling a different problem. The math is slightly different and you end up with an extra gamma multiplying $G \nabla\ln\pi(a|s)$ with the second interpretation.
  
  For example, if you are at step t=2 and gamma = 0.9, the algorithm for the second interpretation is that the policy gradient is $\gamma^2 G \nabla\ln\pi(a|s)$ or $0.81 G \nabla\ln\pi(a|s)$. This term has 19% less gradient power than the t=0 term for the simple reason that 19% of simulated trajectories have died off by t=2.
  
  With the first interpretation of gamma, there is no such 19% decay. The policy gradient is just $G \nabla\ln\pi(a|s)$ at t=2. But gamma is still present within $G$ to discount the future rewards.
  
  You can choose whichever interpretation of gamma, but you have to be mindful of the consequences to the algorithm. I personally prefer to stick with interpretation 1 just because it's simpler. So I use the algorithm in the A3C paper, not the Sutton and Barto book.
  
  Your question was about the REINFORCE algorithm, but I have been discussing actor-critic. You have the exact same issue related to the two gamma interpretations and the extra gamma in REINFORCE.
  
  
  ---
  
  ### Answer by username_3 on 2022-07-06. Score: 0
  
  I would like to follow up on @username_1's answer about the first interpretation of gamma. (I'm a new user and can't post a comment.)
  
  Does it make sense to include $\gamma$ in the return and the state and action value functions without considering it as part of the MDP? (interpretation 2).
  
  If one derives the policy gradient with respect to the discounted return as the objective, then the discounted state distribution arises (the one corresponding to interpretation 2), not the original one. [Proof here.](https://proceedings.neurips.cc/paper/1999/file/464d828b85b0bed98e80ade0a5c43b0f-Paper.pdf)
  
  This seems to mean that you can't have interpretation 1 without interpretation 2.
  
  I would be happy to discuss this further.
  
  > **Comments:**
  > **username_4**: To follow up with a question, instead of adding as an answer, you should ask a new question on the site. You can link username_1's answer in that question (but please add a brief summary including the key 2 interpretations as a quote).  
  > **username_5**: This does not provide an answer to the question. Once you have sufficient [reputation](https://ai.stackexchange.com/help/whats-reputation) you will be able to [comment on any post](https://ai.stackexchange.com/help/privileges/comment); instead, [provide answers that don't require clarification from the asker](https://meta.stackexchange.com/questions/214173/why-do-i-need-50-reputation-to-comment-what-can-i-do-instead). - [From Review](/review/late-answers/21597)  
  > **username_3**: Sure. It's [here](https://ai.stackexchange.com/questions/36234/what-is-the-correct-interpretation-of-the-discount-factor-in-mdps).  
  
  ---
  
  