2
$\begingroup$

Consider some MDP with no terminal state. We can apply bootstrapping methods (like TD(0)) to learn in these cases no problem, but in policy gradient algorithms that have only a simple monte carlo update, it requires us to supply a complete trajectory (which is impossible with no terminal state).

Naturally, one might let the MDP run for 1000 periods, and then terminate as an approximation. If we feed these trajectories into a monte carlo update, I imagine that samples for time period t=1,2,...,100 would give very good estimates for the value function due to the discount factor. However, the time periods 997, 998, 999, 1000, we'd have an expected value for those trajectories far different than V(s) due to their proximity to the cutoff of 1000.

The question is this:

  1. Should we even include these later-occurring data points when we update our function approximation?

OR

  1. Is the assumption that these points become really sparse in our updates, so they won't have much effect in our training?

OR

  1. Is it usually implied that the final data reward in the trajectory is bootstrapped in these cases (i.e., we have some TD(0)-like behavior in this case)?

OR

  1. Are monte carlo updates for policy gradient algorithms even appropriate for non-terminating MDPs due to this issue?
$\endgroup$
  • 1
    $\begingroup$ It'd be better to only have one question; you can have follow-ups in separate posts. $\endgroup$ – Oliver Mason Feb 27 at 9:49
  • $\begingroup$ @OliverMason It isn't really four different questions; it's 4 hypothetical explanations that the OP has come up with to explain his own confusion, and he's asking which of them are on point. So I vote to leave it open $\endgroup$ – Dennis Soemers Mar 6 at 20:25
1
$\begingroup$

Naturally, one might let the MDP run for 1000 periods, and then terminate as an approximation. If we feed these trajectories into a monte carlo update, I imagine that samples for time period t=1,2,...,100 would give very good estimates for the value function due to the discount factor. However, the time periods 997, 998, 999, 1000, we'd have an expected value for those trajectories far different than V(s) due to their proximity to the cutoff of 1000.

I think your intuition is... partially right here, but not entirely precise. Recall that a value function $V(S)$ is generally defined as something like (omitting some unimportant details like specifying the policy):

$$V(S_i) = \mathbb{E} \left[ \sum_{t=0}^{\infty} \gamma^t R_{i+t} \right].$$

The "samples for time period $t = 1, 2, \dots, 100$ that you mention are not estimates for this full value function. They're estimates for the corresponding individual terms $R_{i+t}$. Indeed, in general, your intuition is right that the closer they are to the "starting point" $i$, the more likely they'll be to be accurate estimators. This is because larger $t$ are typically associated with larger numbers of stochastic state-transitions and stochastic decision-making, and therefore often exhibit higher variance.

  1. Should we even include these later-occurring data points when we update our function approximation?

Theoretically, you absolutely should. Suppose you have an environment where almost every reward is equal to $0$, and only after 1000 steps do you actually observe a non-zero reward. If you don't include this, you'll learn nothing! In practice, it can often be a good idea to give them less importance though. This already happens automatically by picking a discount factor $\gamma < 1$.

  1. Is it usually implied that the final data reward in the trajectory is bootstrapped in these cases (i.e., we have some TD(0)-like behavior in this case)?

OR

  1. Are monte carlo updates for policy gradient algorithms even appropriate for non-terminating MDPs due to this issue?

It would be possible to do some form of bootstrapping at the end yeah, cut off and then have a trained value function predicting what the remainder of the rewards would be. TD($\lambda$) with $\lambda$ close to $1$ would be much closer in behaviour to true MC updates than TD($0$) though. Either way, it would be technically incorrect to still call it Monte-Carlo then, it would no longer be pure Monte-Carlo. So yes, strict Monte-Carlo updates in the purest sense of the term are not really applicable to infinite episodes.

|improve this answer|||||
$\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.