Answers.Body: <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>I think your intuition is... partially right here, but not entirely precise. Recall that a value function <span class="math-container">$V(S)$</span> is generally defined as something like (omitting some unimportant details like specifying the policy):</p>
  
  <p><span class="math-container">$$V(S_i) = \mathbb{E} \left[ \sum_{t=0}^{\infty} \gamma^t R_{i+t} \right].$$</span></p>
  
  <p>The "samples for time period <span class="math-container">$t = 1, 2, \dots, 100$</span> that you mention are <strong>not</strong> estimates for this full value function. They're estimates for the corresponding individual terms <span class="math-container">$R_{i+t}$</span>. Indeed, in general, your intuition is right that the closer they are to the "starting point" <span class="math-container">$i$</span>, the more likely they'll be to be accurate estimators. This is because larger <span class="math-container">$t$</span> are typically associated with larger numbers of stochastic state-transitions and stochastic decision-making, and therefore often exhibit higher variance.</p>
  
  <blockquote>
    <ol>
    <li>Should we even include these later-occurring data points when we update our function approximation? </li>
    </ol>
  </blockquote>
  
  <p>Theoretically, you absolutely should. Suppose you have an environment where almost every reward is equal to <span class="math-container">$0$</span>, 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 <span class="math-container">$\gamma &lt; 1$</span>.</p>
  
  <blockquote>
    <ol start="3">
    <li>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)?</li>
    </ol>
    
    <p>OR</p>
    
    <ol start="4">
    <li>Are monte carlo updates for policy gradient algorithms even appropriate for non-terminating MDPs due to this issue? </li>
    </ol>
  </blockquote>
  
  <p>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(<span class="math-container">$\lambda$</span>) with <span class="math-container">$\lambda$</span> close to <span class="math-container">$1$</span> would be much closer in behaviour to true MC updates than TD(<span class="math-container">$0$</span>) 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-07T09:24:46.340Z
Answers.LastActivityDate: 2020-03-07T09:24:46.340Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>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). </p>
  
  <p>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.</p>
  
  <p>The question is this: </p>
  
  <ol>
  <li>Should we even include these later-occurring data points when we update our function approximation? </li>
  </ol>
  
  <p>OR</p>
  
  <ol start="2">
  <li>Is the assumption that these points become really sparse in our updates, so they won't have much effect in our training?</li>
  </ol>
  
  <p>OR</p>
  
  <ol start="3">
  <li>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)?</li>
  </ol>
  
  <p>OR </p>
  
  <ol start="4">
  <li>Are monte carlo updates for policy gradient algorithms even appropriate for non-terminating MDPs due to this issue? </li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-02-27T09:49:56.773Z
Comments.Text: It'd be better to only have one question; you can have follow-ups in separate posts.
Comments.UserDisplayName: Oliver Mason
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-03-06T20:25:08.733Z
Comments.Text: @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
Comments.UserDisplayName: Dennis Soemers
Tags: <deep-rl><policy-gradients><function-approximation>
Title: Monte Carlo updates on policy gradient with no terminal state
UserDisplayName: Austin Bren
ThreadText: # Monte Carlo updates on policy gradient with no terminal state
  
  (Asked by: username_0 on 2020-02-27)
  
  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
  
  2. Is the assumption that these points become really sparse in our updates, so they won't have much effect in our training?
  
  OR
  
  3. 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
  
  4. Are monte carlo updates for policy gradient algorithms even appropriate for non-terminating MDPs due to this issue?
  
  **Tags:** deep-rl, policy-gradients, function-approximation
  > **Comments:**
  > **username_1**: It'd be better to only have one question; you can have follow-ups in separate posts.  
  > **username_2**: @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  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-03-07. Score: 1
  
  > 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$.
  
  > 3. 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
  >
  > 4. 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.
  
  
  ---
  
  