1
$\begingroup$

I was reading the paper on Generalized Advantage Estimate. It first introduces a generalized form of policy gradient equation without involving $\gamma$ and then it says the following:

We will introduce a parameter $\gamma$ that allows us to reduce variance by downweighting rewards corresponding to delayed effects, at the cost of introducing bias. This parameter corresponds to the discount factor used in discounted formulations of MDPs, but we treat it as a variance reduction parameter in an undiscounted problem.

I know the Monte Carlo estimate of value function is given as:

$$V(s_t)=\sum_{l=t}^\infty \gamma^tr_t$$

The bootstrapped estimate of value function is given as:

$$V(s_t)=r_t+\gamma V(s_{t+1})$$

(In both equations, $\gamma$ is a discount factor.)

The bootstrapped estimate is biased because it based on $V(s_{t+1})$ which is usually a biased estimate by some estimator such as a neural network. The Monte Carlo estimate is unbiased because it contains all rewards sampled from the environment. In this case, however, because the agent might take a lot of actions over the course of an episode, it's hard to assign credit to the right action, which means that a Monte Carlo estimate will have a high variance.

Does this contradict what the paper says: "a parameter $\gamma$ that allows us to reduce variance"? Or does it simply mean the following: lower $\gamma$ gives smaller weights to distant future rewards, thus making value estimate less dependent on them, reducing variance in comparison to larger $\gamma$, which make distant future rewards contribute significantly to value estimate. So introduction/existence of $\gamma$ itself does not reduce the variance but gives way to increase or decrease the variance.

$\endgroup$
1
$\begingroup$

Bootstrapped estimate is biased because it based on $V(s_{t+1})$ which is usually a biased estimate by some estimator such as neural network.

I don't think this statement is totally correct in the context of the paper. Quoting the paper:

Taking $\gamma < 1$ introduces bias into the policy gradient estimate, regardless of the value function’s accuracy. On the other hand, $ \lambda < 1$ introduces bias only when the value function is inaccurate.

So the initial $\gamma$-discounting introduces bias regardless of the accuracy of the $V(s)$.

Same point is reiterated in the footnote on the page 3:

Note, that we have already introduced bias by using $A^{\pi,\gamma}$ in place of $A^\pi$; here we are concerned with obtaining an unbiased estimate of $g^\gamma$, which is a biased estimate of the policy gradient of the undiscounted MDP.

To summarize the above:

  1. the original MDP under consideration is undiscounted
  2. authors introduce $\gamma$-discounting to reduce variance (at cost of bias) of the PG estimate - this happens even if we had accurate $V(s)$
  3. later, authors introduce another $\lambda$-discounting which also controls bias-variance tradeoff - now due to inaccuracy in $V(s)$

As for why lower $\gamma$ reduces variance (p.2 above) - your explanation is on point: smaller $\gamma$ $\Rightarrow$ smaller weights for distant rewards $\Rightarrow$ less variance (but more bias).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.