Answers.Body: <blockquote>
  <p>Hence, I think we
  would in general look <strong>only up to n-steps</strong> ahead <strong>rather than
  always n-steps</strong>, since the n consecutive samples from the replay
  buffer don't guarantee that the transitions happended according to
  the current policy <span class="math-container">$\pi$</span>.</p>
  </blockquote>
  <p>This is correct in general in n-step off-policy learners: Whenever exploration chooses an action that the target policy has <span class="math-container">$0$</span> probability of selecting, then there is <em>nothing to learn</em> about the target policy from that specific choice. The best you can do is take some other estimate - in TD learning that will be a bootstrap estimate taken earlier than n steps for some state-action estimates. You don't have to do this, but a bootstrap estimate is often better than throwing away the sampled experience (in off-policy Monte Carlo control, you would indeed throw away that earlier experience, and the method can still work in practice though).</p>
  <p>It is possible to learn from time steps later than exploration, you just re-start from the new <span class="math-container">$s, a$</span> pair (and new count up to n). If this changes the estimate of <span class="math-container">$Q(s,a)$</span> so that this exploratory action is better in state <span class="math-container">$s$</span>, then the target policy will change and what was once exploratory will become part of the target policy.</p>
  <p>There is no way around this in off-policy value estimators.</p>
  <blockquote>
  <p>Doesn't this negatively affect the agent's behavior since sometimes the target is made up of only one timestep and sometimes of several?</p>
  </blockquote>
  <p>&quot;Negatively affect&quot; with respect to what?</p>
  <p>The  main reason for using n-step learning is to find a sweet spot between the bias inherent in bootstrap estimates - worse in TD(0) - and the variance inherent to fully sampled returns from long trajectories - worse in Monte Carlo or TD(1). This reason still applies when the steps that are full samples of experience can vary between <span class="math-container">$1$</span> and <span class="math-container">$n$</span>. There will usually be a value of max <span class="math-container">$n$</span> (combined with specific exploration probabilities) between 1 and the full episode length that works better than either of those extremes.</p>
  <p>It is worth noting that in the DQN &quot;rainbow&quot; paper, the authors add n-step returns, ignoring the theory regarding truncating with an early bootstrap. They simply store the discounted sum of rewards <span class="math-container">$r_{t+1}$</span> to <span class="math-container">$r_{t+n}$</span>, plus <span class="math-container">$s_{t+n}$</span> for e.g. n=4 steps ahead in the experience replay table, <em>regardless</em> of whether the agent took an exploratory action (in addtion, any of the actions might become exploratory with respect to the target policy later because the experience replay table is effectively an offline dataset). In practice this still works better than single-step updates despite the break from theory, at least for relatively low <span class="math-container">$n$</span> and <span class="math-container">$\epsilon$</span>, and the kinds of environments that DQN was developed against (Atari games).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-15T09:27:11.773Z
Answers.LastActivityDate: 2022-04-15T20:29:15.163Z
Answers.LastEditDate: 2022-04-15T20:29:15.163Z
Answers.UserDisplayName: Neil Slater
Body: <p>In the text book of <a href="https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf" rel="nofollow noreferrer">Sutton and Barto</a> on page 152 they introduce the n-step Tree Backup algorithm, where the tree-backup n-step return is defined via
  <span class="math-container">$$
  G_{t:t+n} = R_{t+1} + \gamma \sum_{a \neq A_{t+1}} \pi(a | S_{t+1})Q_{t+n-1}(S_{t+1}, a) + \gamma \pi(A_{t+1}| S_{t+1})G_{t+1, t+n}.
  $$</span></p>
  <p>Assume we have a sample of the replay buffer and its consecutive
  transitions <span class="math-container">$$ (S_{t}, A_{t}, R_{t+1}, S_{t+1}), (S_{t+1}, A_{t+1},
  R_{t+2}, S_{t+2}), ..., (S_{t+n-1}, A_{t+n-1}, R_{t+n}, S_{t+n}). $$</span>
  Since in Deep Q-Learning, the target policy <span class="math-container">$\pi$</span> is usually the greedy-policy, we have
  <span class="math-container">$$ \pi(a|S_{t+1}) = \begin{cases} 1, &amp; \text{if }  a= argmax_{a}Q(a,
  S_{t+1}) \\ 0, &amp; \text{otherwise}. \end{cases} $$</span>
  Hence, I think we
  would in general look <strong>only up to n-steps</strong> ahead <strong>rather than
  always n-steps</strong>, since the n consecutive samples from the replay
  buffer don't guarantee that the transitions happended according to
  the current policy <span class="math-container">$\pi$</span>. Doesn't this negatively affect the agent's behavior since sometimes the target is made up of only one timestep and sometimes of several?</p>
  <p>Thanks in advance for any help!</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-12T12:14:02.463Z
Comments.Text: Could you please put your main question in the title? If that doesn't seem possible (or it becomes "questions about N-step Tree Backup"), it may be a clue that you should split the question up into simpler components. Generally I think that well-presented questions about RL theory are on-topic and appreciated here, and N-step tree backup doesn't have many questions so far, so it won't matter to the site if you post two or three on a similar theme.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-12T12:34:35.267Z
Comments.Text: @NeilSlater I updated the question. Thanks for pointing this out.
Comments.UserDisplayName: Peter
Tags: <reinforcement-learning><deep-rl><dqn><experience-replay><bootstrapping>
Title: Doesn't the n-step Tree Backup algorithm negatively affect the DQN-Agent by creating inconsistent look-ahead targets?
UserDisplayName: Peter
ThreadText: # Doesn't the n-step Tree Backup algorithm negatively affect the DQN-Agent by creating inconsistent look-ahead targets?
  
  (Asked by: username_0 on 2022-04-12)
  
  In the text book of [Sutton and Barto](https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf) on page 152 they introduce the n-step Tree Backup algorithm, where the tree-backup n-step return is defined via
  $$
  G\_{t:t+n} = R\_{t+1} + \gamma \sum\_{a \neq A\_{t+1}} \pi(a | S\_{t+1})Q\_{t+n-1}(S\_{t+1}, a) + \gamma \pi(A\_{t+1}| S\_{t+1})G\_{t+1, t+n}.
  $$
  
  Assume we have a sample of the replay buffer and its consecutive
  transitions $$ (S\_{t}, A\_{t}, R\_{t+1}, S\_{t+1}), (S\_{t+1}, A\_{t+1},
  R\_{t+2}, S\_{t+2}), ..., (S\_{t+n-1}, A\_{t+n-1}, R\_{t+n}, S\_{t+n}). $$
  Since in Deep Q-Learning, the target policy $\pi$ is usually the greedy-policy, we have
  $$ \pi(a|S\_{t+1}) = \begin{cases} 1, & \text{if } a= argmax\_{a}Q(a,
  S\_{t+1}) \\ 0, & \text{otherwise}. \end{cases} $$
  Hence, I think we
  would in general look **only up to n-steps** ahead **rather than
  always n-steps**, since the n consecutive samples from the replay
  buffer don't guarantee that the transitions happended according to
  the current policy $\pi$. Doesn't this negatively affect the agent's behavior since sometimes the target is made up of only one timestep and sometimes of several?
  
  Thanks in advance for any help!
  
  **Tags:** reinforcement-learning, deep-rl, dqn, experience-replay, bootstrapping
  
  > **Comments:**
  > **username_1**: Could you please put your main question in the title? If that doesn't seem possible (or it becomes "questions about N-step Tree Backup"), it may be a clue that you should split the question up into simpler components. Generally I think that well-presented questions about RL theory are on-topic and appreciated here, and N-step tree backup doesn't have many questions so far, so it won't matter to the site if you post two or three on a similar theme.  
  > **username_0**: @username_1 I updated the question. Thanks for pointing this out.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-04-15. Score: 1 | Accepted answer
  
  > Hence, I think we
  > would in general look **only up to n-steps** ahead **rather than
  > always n-steps**, since the n consecutive samples from the replay
  > buffer don't guarantee that the transitions happended according to
  > the current policy $\pi$.
  
  This is correct in general in n-step off-policy learners: Whenever exploration chooses an action that the target policy has $0$ probability of selecting, then there is *nothing to learn* about the target policy from that specific choice. The best you can do is take some other estimate - in TD learning that will be a bootstrap estimate taken earlier than n steps for some state-action estimates. You don't have to do this, but a bootstrap estimate is often better than throwing away the sampled experience (in off-policy Monte Carlo control, you would indeed throw away that earlier experience, and the method can still work in practice though).
  
  It is possible to learn from time steps later than exploration, you just re-start from the new $s, a$ pair (and new count up to n). If this changes the estimate of $Q(s,a)$ so that this exploratory action is better in state $s$, then the target policy will change and what was once exploratory will become part of the target policy.
  
  There is no way around this in off-policy value estimators.
  
  > Doesn't this negatively affect the agent's behavior since sometimes the target is made up of only one timestep and sometimes of several?
  
  "Negatively affect" with respect to what?
  
  The main reason for using n-step learning is to find a sweet spot between the bias inherent in bootstrap estimates - worse in TD(0) - and the variance inherent to fully sampled returns from long trajectories - worse in Monte Carlo or TD(1). This reason still applies when the steps that are full samples of experience can vary between $1$ and $n$. There will usually be a value of max $n$ (combined with specific exploration probabilities) between 1 and the full episode length that works better than either of those extremes.
  
  It is worth noting that in the DQN "rainbow" paper, the authors add n-step returns, ignoring the theory regarding truncating with an early bootstrap. They simply store the discounted sum of rewards $r\_{t+1}$ to $r\_{t+n}$, plus $s\_{t+n}$ for e.g. n=4 steps ahead in the experience replay table, *regardless* of whether the agent took an exploratory action (in addtion, any of the actions might become exploratory with respect to the target policy later because the experience replay table is effectively an offline dataset). In practice this still works better than single-step updates despite the break from theory, at least for relatively low $n$ and $\epsilon$, and the kinds of environments that DQN was developed against (Atari games).
  
  
  ---
  
  