Answers.Body: <p>Lets notice, that <span class="math-container">$\hat{A}=\delta_t$</span> is a unbiased estimate of <span class="math-container">$A$</span> in a sense, that
  <span class="math-container">$$
  E_{s_{t+1}}[r_t + \gamma V(s_{t+1}) - V(s_t)] = E_{s_{t+1}}[Q(a_t, s_t) - V(s_t)] = A(a_t, s_t)
  $$</span>
  Here we abuse the fact, that <span class="math-container">$V(s)$</span> is known, but in reality we know only its approximation, so the bias of estimator will be correlated to error of estimation of <span class="math-container">$V$</span> by  <span class="math-container">$V_\theta(s)$</span>. By increasing the trajectory we can minimise the impact of <span class="math-container">$V_\theta(s_{t+1})$</span>, lets write
  <span class="math-container">\begin{equation}
   \begin{aligned}
  &amp;\hat{A}_t^{(1)}:=\delta^V_t&amp; =r_t + \gamma V(s_{t+1}) - V(s_t) \\
  &amp;\hat{A}_t^{(2)}:=\delta^V_t + \gamma\delta^V_{t+1}&amp;=r_t + \gamma r_t + \gamma^2V(s_{t+2}) - V(s_t)\\
  &amp;\hat{A}_t^{(3)}:=\delta^V_t + \gamma\delta^V_{t+1}+\gamma^2\delta^V_{t+2}&amp;=r_t + \gamma r_t + \gamma^2r_{t+2}+\gamma^3V(s_{t+3}) - V(s_t)\\
  &amp;...&amp;\\
  &amp;\hat{A}_t^{(\infty)} := \sum_{i=0}^{\infty} \gamma^i\delta_{t+i}^{V}
   \end{aligned}
  \end{equation}</span></p>
  <p>The longer the traction, the smaller the term <span class="math-container">$\gamma^i$</span> at <span class="math-container">$V(s_{t+i})$</span>, therefore the approximation of advantage function is less biased.</p>
  <p>It is not perfect, since the variance is increasing with longer path, e.g. <span class="math-container">$\hat{A}^{(1)}_t$</span> has low variance and high bias, and <span class="math-container">$\hat{A}^{(\infty)}_t$</span> has low bias, but high variance. The tradeoff can be introduced by taking some <span class="math-container">$i &lt; \infty$</span> and estimating the A by <span class="math-container">$\hat{A}^{(i)}_t$</span>. But choice of <span class="math-container">$i$</span> is not evident. By analogy of generalisation for TD(<span class="math-container">$\lambda$</span>), described in <a href="https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf" rel="nofollow noreferrer">Sutton's book, chapter
  12.8</a> the other way to introduce the trade-off between bias and variance is to take a weighted sum. In practical case of course the infinite trajectories are not accessible. So the trajectories of length T are taken into account, which results exactly in
  <span class="math-container">$$
  \hat{A}_t = \sum_{i=0}^{T-(t+1)} (\gamma \lambda)^i \delta^{V_\theta}_{t + i}
  $$</span>
  Where <span class="math-container">$\lambda$</span> introduces the trade off between bias and variance of advantage function estimation.</p>
  <p>For further detailed reading I would highly recommend looking at the other <a href="https://arxiv.org/abs/1506.02438" rel="nofollow noreferrer">article by J. Schulman</a>. It has a section (3. Advantage Function Estimation) on exactly this question.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-23T20:07:18.607Z
Answers.Text: Is there any reason, why you put the index for the advantage A on the top instead of replacing the step `t`?
Answers.UserDisplayName: Dave
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-24T11:03:36.740Z
Answers.Text: Im not sure I understand exactly what do you mean. Are you referring to $\hat{A}^{(i)}_t$ notation? And the question is why I didn't write it as $\hat{A}_{(i)}$ ?
Answers.UserDisplayName: vl_knd
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-24T17:58:43.377Z
Answers.Text: Sorry: yes exactly. Because otherwise, given a trajectory, I would need to calculate: $\hat{A}^{(1)}_{0}$, $\hat{A}^{(1)}_{1}$, $\hat{A}^{(2)}_{2}$ and so on... Then I need to repeat the same process again for $\hat{A}^{(2)}_{t}$. It shouldn't be: $\hat{A}_{0}$, $\hat{A}_{1}$, $\hat{A}_{2}$ ... instead?
Answers.UserDisplayName: Dave
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-24T19:39:26.120Z
Answers.Text: I think I see where the misunderstanding is coming from! So each of $\hat{A}^{(j)}_i$ is an estimate of advantage function, so you would have to pick one to use in specific case. You would compute only $\hat{A}^{(1)}_t$ for example, for all the $t$ in the trajectory. However there is a bias-variance tradeoff - longer trace gives less bias, but high variance ( The estimate is accurate, but takes a lot of data to converge ) and shorter trace - gives low variance, but high bias ( It converges very fast, but is not very accurate ). So the question is - which length you should choose?
Answers.UserDisplayName: vl_knd
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-24T19:46:09.673Z
Answers.Text: To answer this question $\hat{A}_t$ is proposed. If you look at the formula, it uses all the trajectory information ( like $\hat{A}^{(T)}_t$ ), so it supposed to have high variance and low bias. However, there is an extra parameter $\lambda$ that added to control that trade-off. Notice, that if $\lambda$ is very small, then $(\gamma \lambda)^i \delta^{V_\theta}_{t + i}$ becomes small very fast with increasing $i$ and the information from the end of the trajectory is not used! This all to say, that $\hat{A}_t$ is actually a different estimator from $\hat{A}_t^{(i)}$. Hope it helps!
Answers.UserDisplayName: vl_knd
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-26T08:34:12.213Z
Answers.Text: If I understood right (I'm still not really sure), it is exactly the same as $TD(\lambda)$. It is correct? I mean, the same concept, not the same algorithm. That means, if $\lambda = 0$ is one case and if $\lambda = \infty$ then it is another case
Answers.UserDisplayName: Dave
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-26T08:55:38.060Z
Answers.Text: It looks to me, that $\lambda \in [0, 1]$, so you can't have $\lambda = \infty$. Yes its the same as $\text{TD}(\lambda)$, but its $\hat{A}(\lambda)$ :) So for different $\lambda$ you will have different estimates of advantage function.
Answers.UserDisplayName: vl_knd
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-26T09:13:17.307Z
Answers.Text: You are right: $\lambda \in [0, 1]$, I mistook meaning for $\lambda = 1$ you get the MC in $\infty$ case. Thank you very much for your patience and explanations!
Answers.UserDisplayName: Dave
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-03T17:43:36.193Z
Answers.LastActivityDate: 2024-02-18T10:24:47.730Z
Answers.LastEditDate: 2024-02-18T10:24:47.730Z
Answers.UserDisplayName: vl_knd
Body: <p>So I've been looking at this formula for advantage estimate</p>
  <p><span class="math-container">\begin{equation}
  \begin{aligned}
  &amp; \hat{A}_t = \delta_t + (\gamma \lambda)\delta_{t+1} + ... +  (\gamma \lambda)^{T-t+1}\delta_{T-1}\\
  &amp;\text{where}\ \delta_t = r_t +\gamma V(s_{t+1}) - V(s_t)
  \end{aligned}
  \end{equation}</span>
  where <span class="math-container">$r_t$</span> is the reward at time <span class="math-container">$t$</span> and <span class="math-container">$V(s_t)$</span> is the estimated value of <span class="math-container">$s_t$</span> and <span class="math-container">$\gamma$</span> is future discount. Why is <span class="math-container">$\delta_t$</span> useful? As in why is it useful to calculate reward from time <span class="math-container">$t$</span> from the discounted estimated reward from that time onward of <span class="math-container">$s_t$</span> and subtract the value estimate of <span class="math-container">$s_t$</span></p>
  <p><a href="https://arxiv.org/pdf/1707.06347.pdf" rel="nofollow noreferrer">Original PPO Paper</a></p>
  
Tags: <reinforcement-learning><papers><proximal-policy-optimization>
Title: PPO advantage estimate - Why does advantage estimate have $r_t+\gamma V(s_{t+1})-V(s_t)$
UserDisplayName: user8714896
ThreadText: # PPO advantage estimate - Why does advantage estimate have $r_t+\gamma V(s_{t+1})-V(s_t)$
  
  (Asked by: username_0 on 2022-01-30)
  
  So I've been looking at this formula for advantage estimate
  
  \begin{equation}
  \begin{aligned}
  & \hat{A}\_t = \delta\_t + (\gamma \lambda)\delta\_{t+1} + ... + (\gamma \lambda)^{T-t+1}\delta\_{T-1}\\
  &\text{where}\ \delta\_t = r\_t +\gamma V(s\_{t+1}) - V(s\_t)
  \end{aligned}
  \end{equation}
  where $r\_t$ is the reward at time $t$ and $V(s\_t)$ is the estimated value of $s\_t$ and $\gamma$ is future discount. Why is $\delta\_t$ useful? As in why is it useful to calculate reward from time $t$ from the discounted estimated reward from that time onward of $s\_t$ and subtract the value estimate of $s\_t$
  
  [Original PPO Paper](https://arxiv.org/pdf/1707.06347.pdf)
  
  **Tags:** reinforcement-learning, papers, proximal-policy-optimization
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-02-03. Score: 3 | Accepted answer
  
  Lets notice, that $\hat{A}=\delta\_t$ is a unbiased estimate of $A$ in a sense, that
  $$
  E\_{s\_{t+1}}[r\_t + \gamma V(s\_{t+1}) - V(s\_t)] = E\_{s\_{t+1}}[Q(a\_t, s\_t) - V(s\_t)] = A(a\_t, s\_t)
  $$
  Here we abuse the fact, that $V(s)$ is known, but in reality we know only its approximation, so the bias of estimator will be correlated to error of estimation of $V$ by $V\_\theta(s)$. By increasing the trajectory we can minimise the impact of $V\_\theta(s\_{t+1})$, lets write
  \begin{equation}
  \begin{aligned}
  &\hat{A}\_t^{(1)}:=\delta^V\_t& =r\_t + \gamma V(s\_{t+1}) - V(s\_t) \\
  &\hat{A}\_t^{(2)}:=\delta^V\_t + \gamma\delta^V\_{t+1}&=r\_t + \gamma r\_t + \gamma^2V(s\_{t+2}) - V(s\_t)\\
  &\hat{A}\_t^{(3)}:=\delta^V\_t + \gamma\delta^V\_{t+1}+\gamma^2\delta^V\_{t+2}&=r\_t + \gamma r\_t + \gamma^2r\_{t+2}+\gamma^3V(s\_{t+3}) - V(s\_t)\\
  &...&\\
  &\hat{A}\_t^{(\infty)} := \sum\_{i=0}^{\infty} \gamma^i\delta\_{t+i}^{V}
  \end{aligned}
  \end{equation}
  
  The longer the traction, the smaller the term $\gamma^i$ at $V(s\_{t+i})$, therefore the approximation of advantage function is less biased.
  
  It is not perfect, since the variance is increasing with longer path, e.g. $\hat{A}^{(1)}\_t$ has low variance and high bias, and $\hat{A}^{(\infty)}\_t$ has low bias, but high variance. The tradeoff can be introduced by taking some $i < \infty$ and estimating the A by $\hat{A}^{(i)}\_t$. But choice of $i$ is not evident. By analogy of generalisation for TD($\lambda$), described in [Sutton's book, chapter
  12.8](https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf) the other way to introduce the trade-off between bias and variance is to take a weighted sum. In practical case of course the infinite trajectories are not accessible. So the trajectories of length T are taken into account, which results exactly in
  $$
  \hat{A}\_t = \sum\_{i=0}^{T-(t+1)} (\gamma \lambda)^i \delta^{V\_\theta}\_{t + i}
  $$
  Where $\lambda$ introduces the trade off between bias and variance of advantage function estimation.
  
  For further detailed reading I would highly recommend looking at the other [article by J. Schulman](https://arxiv.org/abs/1506.02438). It has a section (3. Advantage Function Estimation) on exactly this question.
  
  > **Comments:**
  > **username_2**: Is there any reason, why you put the index for the advantage A on the top instead of replacing the step `t`?  
  > **username_1**: Im not sure I understand exactly what do you mean. Are you referring to $\hat{A}^{(i)}_t$ notation? And the question is why I didn't write it as $\hat{A}_{(i)}$ ?  
  > **username_2**: Sorry: yes exactly. Because otherwise, given a trajectory, I would need to calculate: $\hat{A}^{(1)}_{0}$, $\hat{A}^{(1)}_{1}$, $\hat{A}^{(2)}_{2}$ and so on... Then I need to repeat the same process again for $\hat{A}^{(2)}_{t}$. It shouldn't be: $\hat{A}_{0}$, $\hat{A}_{1}$, $\hat{A}_{2}$ ... instead?  
  > **username_1**: I think I see where the misunderstanding is coming from! So each of $\hat{A}^{(j)}_i$ is an estimate of advantage function, so you would have to pick one to use in specific case. You would compute only $\hat{A}^{(1)}_t$ for example, for all the $t$ in the trajectory. However there is a bias-variance tradeoff - longer trace gives less bias, but high variance ( The estimate is accurate, but takes a lot of data to converge ) and shorter trace - gives low variance, but high bias ( It converges very fast, but is not very accurate ). So the question is - which length you should choose?  
  > **username_1**: To answer this question $\hat{A}_t$ is proposed. If you look at the formula, it uses all the trajectory information ( like $\hat{A}^{(T)}_t$ ), so it supposed to have high variance and low bias. However, there is an extra parameter $\lambda$ that added to control that trade-off. Notice, that if $\lambda$ is very small, then $(\gamma \lambda)^i \delta^{V_\theta}_{t + i}$ becomes small very fast with increasing $i$ and the information from the end of the trajectory is not used! This all to say, that $\hat{A}_t$ is actually a different estimator from $\hat{A}_t^{(i)}$. Hope it helps!  
  > **username_2**: If I understood right (I'm still not really sure), it is exactly the same as $TD(\lambda)$. It is correct? I mean, the same concept, not the same algorithm. That means, if $\lambda = 0$ is one case and if $\lambda = \infty$ then it is another case  
  > **username_1**: It looks to me, that $\lambda \in [0, 1]$, so you can't have $\lambda = \infty$. Yes its the same as $\text{TD}(\lambda)$, but its $\hat{A}(\lambda)$ :) So for different $\lambda$ you will have different estimates of advantage function.  
  > **username_2**: You are right: $\lambda \in [0, 1]$, I mistook meaning for $\lambda = 1$ you get the MC in $\infty$ case. Thank you very much for your patience and explanations!  
  
  ---
  
  