0
$\begingroup$

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

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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 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. It has a section (3. Advantage Function Estimation) on exactly this question.

$\endgroup$
8
  • $\begingroup$ Is there any reason, why you put the index for the advantage A on the top instead of replacing the step t? $\endgroup$
    – Dave
    Commented Feb 23 at 20:07
  • $\begingroup$ 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)}$ ? $\endgroup$
    – vl_knd
    Commented Feb 24 at 11:03
  • $\begingroup$ 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? $\endgroup$
    – Dave
    Commented Feb 24 at 17:58
  • 1
    $\begingroup$ 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? $\endgroup$
    – vl_knd
    Commented Feb 24 at 19:39
  • 1
    $\begingroup$ 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! $\endgroup$
    – vl_knd
    Commented Feb 24 at 19:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .