Answers.Body: <p>If you want to maximize the expected reward
  <span class="math-container">\begin{align*} 
  \mathbb{E}\bigg[\sum_{t=1}^nr_t \bigg]
  \end{align*}</span>
  and are using a score function based gradient estimator (as opposed to a SAC/DDPG style update), you have the unbiased gradient estimator
  <span class="math-container">\begin{align*} 
  \sum_{i=1}^n \sum_{k=i}^n r_k\nabla_{\theta}\log\pi(a_t) \tag{1}
  \end{align*}</span>
  Then, you can add discounting as a variance reduction technique; the gradient estimator
  <span class="math-container">\begin{align*} 
  \sum_{i=1}^n \sum_{k=i}^n \gamma^{k-i}r_k\nabla_{\theta}\log\pi(a_t) \tag{2}
  \end{align*}</span>
  will have a lower variance than Eq. (1) (see <a href="https://stats.stackexchange.com/a/428157/257864">this answer</a>).</p>
  <p>If you want to maximize the discounted expected reward
  <span class="math-container">\begin{align*} 
  \mathbb{E}\bigg[\sum_{t=1}^n \gamma^{t-1}r_t \bigg]
  \end{align*}</span>
  you get the unbiased gradient estimator
  <span class="math-container">\begin{align*} 
  \sum_{i=1}^n \sum_{k=i}^n \gamma^{k-1}r_k\nabla_{\theta}\log\pi(a_t) \tag{3}
  \end{align*}</span>
  So in Sutton and Barto they are essentially presenting the formulation Eq. (3). The difference between (2) and (3) is the factor of <span class="math-container">$\gamma^{i-1}$</span> which is what I was confused about in the question.</p>
  <p>Thus in summary, the formulation (2) is an biased estimator of the expected reward; whereas (3) is an unbiased estimator of the expected discounted reward.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-15T18:55:35.823Z
Answers.LastActivityDate: 2022-02-15T18:55:35.823Z
Answers.UserDisplayName: Taw
Answers.Body: <p>I believe you will find the answer in the paper <a href="https://arxiv.org/abs/1506.02438" rel="nofollow noreferrer">High-Dimensional Continuous Control Using Generalized Advantage Estimation</a>, which is the basis for the advantage function used in the PPO paper that you referenced.</p>
  <p>From the paper, the estimate of the advantage function is defined as:
  <span class="math-container">\begin{align*}
  \hat{A}_{t}^{GAE(\gamma,\lambda)} = \sum_{l=0}^{\infty}(\gamma\lambda)^{l}\delta_{t+1}^{V}
  \end{align*}</span>
  where <span class="math-container">$\delta_{t}^{V}$</span>, the TD residual of <span class="math-container">$V$</span>, is defined as:
  <span class="math-container">\begin{align*}
  \delta_{t}^{V} = r_{t}+\gamma V(s_{t+1})-V(s_{t})
  \end{align*}</span>
  where <span class="math-container">$V$</span> is an approximate of the value function.</p>
  <p>If you look closely at these two equations you will see that the discount <span class="math-container">$\gamma$</span> is applied twice.</p>
  <p>I never went through the code of the whole OpenAI implementation of PPO, but if I am not mistaken the implementation of the above equations can be found <a href="https://github.com/openai/baselines/blob/ea25b9e8b234e6ee1bca43083f8f3cf974143998/baselines/ppo2/runner.py#L63-L64" rel="nofollow noreferrer">here in ppo2/runner.py</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-25T15:32:13.607Z
Answers.Text: This does not answer the question. I am familiar with GAE and the equations you give are consistent with the PPO paper. The question is whether or not it is supposed to be $\gamma^{t-1}\hat A_t$ (which is what Sutton and Barto give and what I would expect accordingly to theory); or whether it should be just $\hat A_t$, which is what is present in the PPO paper, PPO code, and GAE paper.
Answers.UserDisplayName: Taw
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-25T17:32:17.893Z
Answers.Text: Apologies for not being clear in my answer. From my understanding of the GAE and PPO implementation, the discount factor is there twice like in S&B, it is just not applied in the same order.
Answers.UserDisplayName: Lars
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-26T07:47:11.567Z
Answers.Text: You have given the definition of $\hat A_t$. I agree with the definition. The question is whether the gradient of the (log probability) should use the coefficient $\hat A_t$ or $\gamma^{t-1} \hat A_t$.
Answers.UserDisplayName: Taw
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-26T10:59:50.867Z
Answers.Text: No, I don't believe that $\gamma$ should be applied to the gradient in $\hat{A}_{t}\frac{\nabla_{\theta}\pi(a_t \, | \, s_t, \theta)}{\pi(a_t \, | \,s_t, \theta_{\rm old})}$ for the reason that it is applied in the calculation of the estimate of the advantage and in the calculation of $\delta^{V}_{t}$ .
Answers.UserDisplayName: Lars
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-25T15:14:31.250Z
Answers.LastActivityDate: 2022-01-25T15:14:31.250Z
Answers.UserDisplayName: Lars
Body: <p>As discussed in <a href="https://ai.stackexchange.com/q/7680/2444">this question</a>, the policy gradient algorithms given in <a href="http://incompleteideas.net/book/bookdraft2017nov5.pdf" rel="nofollow noreferrer">Reinforcement Learning: An Introduction</a> use the gradient
  <span class="math-container">\begin{align*} 
  \gamma^t \hat A_t \nabla_{\theta} \log \pi(a_t \, | \, s_t, \theta)
  \end{align*}</span>
  where <span class="math-container">$\hat A_t$</span> is the advantage estimate for step <span class="math-container">$t$</span>. For example, <span class="math-container">$\hat A_t = r_t + \gamma V(s_{t+1}) - V(s_t)$</span> in the one-step actor-critic algorithm given in section 13.5.</p>
  <p>In the answers to the linked question, it is claimed that the extra discounting is &quot;correct&quot;, which implies that it should be included.</p>
  <p>If I look in the literature to a seminal paper such as <a href="https://arxiv.org/abs/1707.06347" rel="nofollow noreferrer">Proximal Policy Optimization Algorithms</a> by OpenAI, they do not include the extra discounting factor, i.e. they use a gradient defined as
  <span class="math-container">\begin{align*} 
  \hat A_t \dfrac{\nabla_{\theta}\pi(a_t \, | \, s_t, \theta)}{\pi(a_t \, | \,s_t, \theta_{\rm old})}
  \end{align*}</span>
  which does not include the discounting factor (of course, it's dealing with the off-policy case, but I don't see how that would make a difference in terms of the discounting). <a href="https://github.com/openai/baselines/tree/master/baselines/ppo2" rel="nofollow noreferrer">OpenAI's implementation of PPO</a> also does not include the extra discounting factor.</p>
  <p>So, how am I supposed to interpret this discrepancy? I agree that the extra discounting factor should be present, from a theoretical standpoint. Then, why is it not in the OpenAI code or paper?</p>
  
Tags: <reinforcement-learning><policy-gradients><proximal-policy-optimization><sutton-barto><discount-factor>
Title: Why does OpenAI's PPO algorithm not follow the discounting method used in Sutton & Barto?
UserDisplayName: Taw
ThreadText: # Why does OpenAI's PPO algorithm not follow the discounting method used in Sutton & Barto?
  
  (Asked by: username_0 on 2022-01-25)
  
  As discussed in [this question](https://ai.stackexchange.com/q/7680/2444), the policy gradient algorithms given in [Reinforcement Learning: An Introduction](http://incompleteideas.net/book/bookdraft2017nov5.pdf) use the gradient
  \begin{align\*}
  \gamma^t \hat A\_t \nabla\_{\theta} \log \pi(a\_t \, | \, s\_t, \theta)
  \end{align\*}
  where $\hat A\_t$ is the advantage estimate for step $t$. For example, $\hat A\_t = r\_t + \gamma V(s\_{t+1}) - V(s\_t)$ in the one-step actor-critic algorithm given in section 13.5.
  
  In the answers to the linked question, it is claimed that the extra discounting is "correct", which implies that it should be included.
  
  If I look in the literature to a seminal paper such as [Proximal Policy Optimization Algorithms](https://arxiv.org/abs/1707.06347) by OpenAI, they do not include the extra discounting factor, i.e. they use a gradient defined as
  \begin{align\*}
  \hat A\_t \dfrac{\nabla\_{\theta}\pi(a\_t \, | \, s\_t, \theta)}{\pi(a\_t \, | \,s\_t, \theta\_{\rm old})}
  \end{align\*}
  which does not include the discounting factor (of course, it's dealing with the off-policy case, but I don't see how that would make a difference in terms of the discounting). [OpenAI's implementation of PPO](https://github.com/openai/baselines/tree/master/baselines/ppo2) also does not include the extra discounting factor.
  
  So, how am I supposed to interpret this discrepancy? I agree that the extra discounting factor should be present, from a theoretical standpoint. Then, why is it not in the OpenAI code or paper?
  
  **Tags:** reinforcement-learning, policy-gradients, proximal-policy-optimization, sutton-barto, discount-factor
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2022-02-15. Score: 0
  
  If you want to maximize the expected reward
  \begin{align\*}
  \mathbb{E}\bigg[\sum\_{t=1}^nr\_t \bigg]
  \end{align\*}
  and are using a score function based gradient estimator (as opposed to a SAC/DDPG style update), you have the unbiased gradient estimator
  \begin{align\*}
  \sum\_{i=1}^n \sum\_{k=i}^n r\_k\nabla\_{\theta}\log\pi(a\_t) \tag{1}
  \end{align\*}
  Then, you can add discounting as a variance reduction technique; the gradient estimator
  \begin{align\*}
  \sum\_{i=1}^n \sum\_{k=i}^n \gamma^{k-i}r\_k\nabla\_{\theta}\log\pi(a\_t) \tag{2}
  \end{align\*}
  will have a lower variance than Eq. (1) (see [this answer](https://stats.stackexchange.com/a/428157/257864)).
  
  If you want to maximize the discounted expected reward
  \begin{align\*}
  \mathbb{E}\bigg[\sum\_{t=1}^n \gamma^{t-1}r\_t \bigg]
  \end{align\*}
  you get the unbiased gradient estimator
  \begin{align\*}
  \sum\_{i=1}^n \sum\_{k=i}^n \gamma^{k-1}r\_k\nabla\_{\theta}\log\pi(a\_t) \tag{3}
  \end{align\*}
  So in Sutton and Barto they are essentially presenting the formulation Eq. (3). The difference between (2) and (3) is the factor of $\gamma^{i-1}$ which is what I was confused about in the question.
  
  Thus in summary, the formulation (2) is an biased estimator of the expected reward; whereas (3) is an unbiased estimator of the expected discounted reward.
  
  
  ---
  
  ### Answer by username_1 on 2022-01-25. Score: -1
  
  I believe you will find the answer in the paper [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://arxiv.org/abs/1506.02438), which is the basis for the advantage function used in the PPO paper that you referenced.
  
  From the paper, the estimate of the advantage function is defined as:
  \begin{align\*}
  \hat{A}\_{t}^{GAE(\gamma,\lambda)} = \sum\_{l=0}^{\infty}(\gamma\lambda)^{l}\delta\_{t+1}^{V}
  \end{align\*}
  where $\delta\_{t}^{V}$, the TD residual of $V$, is defined as:
  \begin{align\*}
  \delta\_{t}^{V} = r\_{t}+\gamma V(s\_{t+1})-V(s\_{t})
  \end{align\*}
  where $V$ is an approximate of the value function.
  
  If you look closely at these two equations you will see that the discount $\gamma$ is applied twice.
  
  I never went through the code of the whole OpenAI implementation of PPO, but if I am not mistaken the implementation of the above equations can be found [here in ppo2/runner.py](https://github.com/openai/baselines/blob/ea25b9e8b234e6ee1bca43083f8f3cf974143998/baselines/ppo2/runner.py#L63-L64).
  
  > **Comments:**
  > **username_0**: This does not answer the question. I am familiar with GAE and the equations you give are consistent with the PPO paper. The question is whether or not it is supposed to be $\gamma^{t-1}\hat A_t$ (which is what Sutton and Barto give and what I would expect accordingly to theory); or whether it should be just $\hat A_t$, which is what is present in the PPO paper, PPO code, and GAE paper.  
  > **username_1**: Apologies for not being clear in my answer. From my understanding of the GAE and PPO implementation, the discount factor is there twice like in S&B, it is just not applied in the same order.  
  > **username_0**: You have given the definition of $\hat A_t$. I agree with the definition. The question is whether the gradient of the (log probability) should use the coefficient $\hat A_t$ or $\gamma^{t-1} \hat A_t$.  
  > **username_1**: No, I don't believe that $\gamma$ should be applied to the gradient in $\hat{A}_{t}\frac{\nabla_{\theta}\pi(a_t \, | \, s_t, \theta)}{\pi(a_t \, | \,s_t, \theta_{\rm old})}$ for the reason that it is applied in the calculation of the estimate of the advantage and in the calculation of $\delta^{V}_{t}$ .  
  
  ---
  
  