Answers.Body: <p>As for your first two questions: there is indeed a behaviour and a target policy, which can be different. In the example image of the <span class="math-container">$3$</span>-step tree-backup update in the beginning of the section you mention, the actions <span class="math-container">$A_t$</span>, <span class="math-container">$A_{t+1}$</span>, and <span class="math-container">$A_{t+2}$</span> are assumed to be selected according to some behaviour policy, whereas a (different) target policy is used to determine weights for the different leaf nodes.</p>
  
  <hr>
  
  <p>As for your third question, in the case where our target policy is greedy, lots of terms will indeed have <span class="math-container">$0$</span> weights and therefore entirely drop out. However, this is <strong>not</strong> always going to fall down to the same return as <span class="math-container">$n$</span>-step Sarsa returns; that would not be correct, because (<span class="math-container">$n$</span>-step) Sarsa is an on-policy algorithm. </p>
  
  <p>In the case where the target policy is a greedy policy, the return will depend very much on how many actions happened to get selected by the behaviour policy which the greedy target policy also would have "agreed" with. If the behaviour policy already happened to have made a "mistake" (selected an action that the greedy policy wouldn't have selected) for <span class="math-container">$A_{t+1}$</span>, you'll end up with a standard <span class="math-container">$1$</span>-step <span class="math-container">$Q$</span>-learning update. If the behaviour policy only made a "mistake" with the action <span class="math-container">$A_{t+2}$</span> (and agreed with the target policy on <span class="math-container">$A_{t+1}$</span>), you'll get something that kind of looks like a "<span class="math-container">$2$</span>-step <span class="math-container">$Q$</span>-learning update" (informally here, because <span class="math-container">$n$</span>-step <span class="math-container">$Q$</span>-learning isn't really a thing). Etc.</p>
  
  <p>You can see that this is the case by closely inspecting Equation 7.16 from the book:</p>
  
  <p><span class="math-container">$$G_{t:t+n} \doteq R_{t+1} + \gamma \color{blue}{\sum_{a \neq A_{t+1}} \pi (a \mid S_{t+1}) Q_{t + n - 1}(S_{t+1}, a)} + \gamma \color{red}{\pi (A_{t + 1} \mid S_{t + 1}) G_{t + 1 : t + n}}.$$</span></p>
  
  <ol>
  <li>Suppose that the target policy <span class="math-container">$\pi$</span> is greedy, and the behaviour policy already selected action <span class="math-container">$A_{t+1}$</span> differently from what <span class="math-container">$\pi$</span> would have selected (meaning that <span class="math-container">$\pi(A_{t+1} \mid S_{t+1}) = 0$</span>). Then we know that the <span class="math-container">$\color{red}{\text{red}}$</span> part of the equation will evaluate to <span class="math-container">$0$</span>. In the <span class="math-container">$\color{blue}{\text{blue sum}}$</span>, the <span class="math-container">$\pi(a \mid S_{t+1})$</span> term will only evaluate to <span class="math-container">$1$</span> for <span class="math-container">$a = \arg\max_a Q_{t+n-1}(S_{t+1}, a)$</span> (because that is the action <span class="math-container">$a$</span> to which the greedy target policy would assign a probability of <span class="math-container">$1$</span>), and <span class="math-container">$0$</span> again for all other elements of the sum. So, in this example situation, we end up using the return <span class="math-container">$G_{t:t+n} = R_{t+1} + \gamma \max_a Q_{t+n-1}(S_{t+1}, a)$</span>. This is exactly the return also used by the standard <span class="math-container">$1$</span>-step <span class="math-container">$Q$</span>-learning update rule.</li>
  <li>Now suppose that the behaviour policy and a greedy target policy happened to "agree" with each other on <span class="math-container">$A_{t + 1}$</span>, but disagree again on <span class="math-container">$A_{t + 2}$</span>. In this case, the entire <span class="math-container">$\color{blue}{\text{blue sum}}$</span> for <span class="math-container">$G_{t:t+n}$</span> will evaluate to <span class="math-container">$0$</span>, but the <span class="math-container">$\pi(A_{t+1} \mid S_{t+1})$</span> in the <span class="math-container">$\color{red}{\text{red part}}$</span> will evaluate to <span class="math-container">$1$</span>. Then, "inside" the recursive <span class="math-container">$\color{red}{G_{t+1:t+n}}$</span>, we'll get a very similar situation to the example above, with a single non-zero term in the blue sum and a red part that evaluates to <span class="math-container">$0$</span>. In this case, the total return will be <span class="math-container">$G_{t:t+n} = R_{t + 1} + \gamma R_{t + 2} + \gamma^2 \max_a Q_{t + n - 1}(S_{t + 2}, a)$</span>. Note that this is different from a <span class="math-container">$2$</span>-step Sarsa return. <span class="math-container">$2$</span>-step Sarsa would use a return with <span class="math-container">$\gamma^2 Q_{t+n-1}(S_{t+2}, A_{t+2})$</span> at the end (where <span class="math-container">$A_{t+2}$</span> is sampled according to the behaviour policy), rather than that term involving <span class="math-container">$\max_a$</span>.</li>
  </ol>
  
  <p>What you essentially end up getting in these cases is returns similar to those of <span class="math-container">$n$</span>-step Sarsa, but they automatically get truncated as soon as there is disagreement between the behaviour policy and a greedy target policy (all subsequent reward observations get replaced by a single bootstrapping value estimate instead).</p>
  
  <hr>
  
  <p>In the examples above, I assumed completely greedy target policies, since that is what you appeared to be most interested in in your question (and is probably also the most common use-case of off-policy learning). <strong>Note that a target policy does not have to be greedy</strong>. You can also have non-greedy target policies if you like, and then the returns will obviously change quite a bit from the discussion above (fewer <span class="math-container">$\pi(S, A)$</span> terms would evaluate to <span class="math-container">$0$</span>, there'd be more non-zero terms).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-20T10:02:35.297Z
Answers.Text: Would the convergence guarantees hold if the target policy is not greedy? The proof doesn't seem to make any such assumption.
Answers.UserDisplayName: backpropper
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-20T14:35:30.570Z
Answers.Text: @AbhinavGupta Ermm yeah I think so. Convergence proofs and that kind of stuff is not 100% my specialty... but yeah, if I recall correctly the only assumptions are generally about stuff like that you have sufficient exploration (always keep exploring, but rate of exploration decreasing over time) and that sort of stuff. There definitely can be convergence for non-greedy policies.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-29T02:30:17.493Z
Answers.Text: Your formula $G_{t:t+n} = R_{t + 1} + \gamma R_{t + 2} + \gamma^2 \max_a Q_{t + n - 1}(S_{t + 2}, a)$ seems to suggest this is $n$-step Q-learinng. Could you please elaborate their similarities and differences? $n$-step Q-learning should use importance sampling. Your formula does not. How can they be both unbiased.
Answers.UserDisplayName: doraemon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-14T20:11:58.527Z
Answers.LastActivityDate: 2018-12-14T20:11:58.527Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>In reinforcement learning book from Sutton &amp; Barto (2018 edition), specifically in section 7.5 of the book, they present an n-step off-policy algorithm that doesn't require importance sampling called <em>n-step tree backup algorithm</em>. </p>
  
  <p>In other algorithms, the return in the update consisted of rewards along the way and the estimated value(s) of the node(s) at the bottom, but, in tree backup update, a return consists of things mentioned before plus the estimated values of the actions that weren't picked during these n steps, all weighted by the probability of taking the action from the previous step.  </p>
  
  <p>I have a few questions about things in this algorithm that are unclear to me.</p>
  
  <ol>
  <li><p><em>Why is this algorithm considered an off-policy algorithm?</em> As far as I could notice, only a single target policy is mentioned and there is no talk about behaviour policy generating actions to take.</p></li>
  <li><p><em>In control we want our target policy to be deterministic, greedy policy, so how do we exactly generate actions to take in this case since behaviour policy isn't used?</em> If we generate actions from the greedy policy, we won't explore, so we won't learn the optimal policy. What am I missing here?</p></li>
  <li><p>If I understood something wrong and we are actually using behaviour policy, I don't understand how would the update work in the case where our target policy is greedy. The return consists of estimates taken from actions that weren't picked, but, because our policy is greedy, the probabilities used in calculating those estimates would be 0, so the total estimate of those actions would be 0 as well. The only non 0 probability in our target policy is the one of the greedy action (which is the probability of 1), so the entire return would fall down to n-step SARSA return. <em>So, basically, how are we allowed to do this update in this case, why is this return allowed to replace the one with importance sampling?</em></p></li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-18T22:10:44.690Z
Comments.Text: Please, next time, even though the questions are related, ask them in separate posts: one question per post.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><off-policy-methods>
Title: Why is the n-step tree backup algorithm an off-policy algorithm?
UserDisplayName: Brale
ThreadText: # Why is the n-step tree backup algorithm an off-policy algorithm?
  
  (Asked by: username_0 on 2018-12-13)
  
  In reinforcement learning book from Sutton & Barto (2018 edition), specifically in section 7.5 of the book, they present an n-step off-policy algorithm that doesn't require importance sampling called *n-step tree backup algorithm*.
  
  In other algorithms, the return in the update consisted of rewards along the way and the estimated value(s) of the node(s) at the bottom, but, in tree backup update, a return consists of things mentioned before plus the estimated values of the actions that weren't picked during these n steps, all weighted by the probability of taking the action from the previous step.
  
  I have a few questions about things in this algorithm that are unclear to me.
  
  1. *Why is this algorithm considered an off-policy algorithm?* As far as I could notice, only a single target policy is mentioned and there is no talk about behaviour policy generating actions to take.
  2. *In control we want our target policy to be deterministic, greedy policy, so how do we exactly generate actions to take in this case since behaviour policy isn't used?* If we generate actions from the greedy policy, we won't explore, so we won't learn the optimal policy. What am I missing here?
  3. If I understood something wrong and we are actually using behaviour policy, I don't understand how would the update work in the case where our target policy is greedy. The return consists of estimates taken from actions that weren't picked, but, because our policy is greedy, the probabilities used in calculating those estimates would be 0, so the total estimate of those actions would be 0 as well. The only non 0 probability in our target policy is the one of the greedy action (which is the probability of 1), so the entire return would fall down to n-step SARSA return. *So, basically, how are we allowed to do this update in this case, why is this return allowed to replace the one with importance sampling?*
  
  **Tags:** reinforcement-learning, off-policy-methods
  
  > **Comments:**
  > **username_1**: Please, next time, even though the questions are related, ask them in separate posts: one question per post.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2018-12-14. Score: 6 | Accepted answer
  
  As for your first two questions: there is indeed a behaviour and a target policy, which can be different. In the example image of the $3$-step tree-backup update in the beginning of the section you mention, the actions $A\_t$, $A\_{t+1}$, and $A\_{t+2}$ are assumed to be selected according to some behaviour policy, whereas a (different) target policy is used to determine weights for the different leaf nodes.
  
  ---
  
  As for your third question, in the case where our target policy is greedy, lots of terms will indeed have $0$ weights and therefore entirely drop out. However, this is **not** always going to fall down to the same return as $n$-step Sarsa returns; that would not be correct, because ($n$-step) Sarsa is an on-policy algorithm.
  
  In the case where the target policy is a greedy policy, the return will depend very much on how many actions happened to get selected by the behaviour policy which the greedy target policy also would have "agreed" with. If the behaviour policy already happened to have made a "mistake" (selected an action that the greedy policy wouldn't have selected) for $A\_{t+1}$, you'll end up with a standard $1$-step $Q$-learning update. If the behaviour policy only made a "mistake" with the action $A\_{t+2}$ (and agreed with the target policy on $A\_{t+1}$), you'll get something that kind of looks like a "$2$-step $Q$-learning update" (informally here, because $n$-step $Q$-learning isn't really a thing). Etc.
  
  You can see that this is the case by closely inspecting Equation 7.16 from the book:
  
  $$G\_{t:t+n} \doteq R\_{t+1} + \gamma \color{blue}{\sum\_{a \neq A\_{t+1}} \pi (a \mid S\_{t+1}) Q\_{t + n - 1}(S\_{t+1}, a)} + \gamma \color{red}{\pi (A\_{t + 1} \mid S\_{t + 1}) G\_{t + 1 : t + n}}.$$
  
  1. Suppose that the target policy $\pi$ is greedy, and the behaviour policy already selected action $A\_{t+1}$ differently from what $\pi$ would have selected (meaning that $\pi(A\_{t+1} \mid S\_{t+1}) = 0$). Then we know that the $\color{red}{\text{red}}$ part of the equation will evaluate to $0$. In the $\color{blue}{\text{blue sum}}$, the $\pi(a \mid S\_{t+1})$ term will only evaluate to $1$ for $a = \arg\max\_a Q\_{t+n-1}(S\_{t+1}, a)$ (because that is the action $a$ to which the greedy target policy would assign a probability of $1$), and $0$ again for all other elements of the sum. So, in this example situation, we end up using the return $G\_{t:t+n} = R\_{t+1} + \gamma \max\_a Q\_{t+n-1}(S\_{t+1}, a)$. This is exactly the return also used by the standard $1$-step $Q$-learning update rule.
  2. Now suppose that the behaviour policy and a greedy target policy happened to "agree" with each other on $A\_{t + 1}$, but disagree again on $A\_{t + 2}$. In this case, the entire $\color{blue}{\text{blue sum}}$ for $G\_{t:t+n}$ will evaluate to $0$, but the $\pi(A\_{t+1} \mid S\_{t+1})$ in the $\color{red}{\text{red part}}$ will evaluate to $1$. Then, "inside" the recursive $\color{red}{G\_{t+1:t+n}}$, we'll get a very similar situation to the example above, with a single non-zero term in the blue sum and a red part that evaluates to $0$. In this case, the total return will be $G\_{t:t+n} = R\_{t + 1} + \gamma R\_{t + 2} + \gamma^2 \max\_a Q\_{t + n - 1}(S\_{t + 2}, a)$. Note that this is different from a $2$-step Sarsa return. $2$-step Sarsa would use a return with $\gamma^2 Q\_{t+n-1}(S\_{t+2}, A\_{t+2})$ at the end (where $A\_{t+2}$ is sampled according to the behaviour policy), rather than that term involving $\max\_a$.
  
  What you essentially end up getting in these cases is returns similar to those of $n$-step Sarsa, but they automatically get truncated as soon as there is disagreement between the behaviour policy and a greedy target policy (all subsequent reward observations get replaced by a single bootstrapping value estimate instead).
  
  ---
  
  In the examples above, I assumed completely greedy target policies, since that is what you appeared to be most interested in in your question (and is probably also the most common use-case of off-policy learning). **Note that a target policy does not have to be greedy**. You can also have non-greedy target policies if you like, and then the returns will obviously change quite a bit from the discussion above (fewer $\pi(S, A)$ terms would evaluate to $0$, there'd be more non-zero terms).
  
  > **Comments:**
  > **username_3**: Would the convergence guarantees hold if the target policy is not greedy? The proof doesn't seem to make any such assumption.  
  > **username_2**: @AbhinavGupta Ermm yeah I think so. Convergence proofs and that kind of stuff is not 100% my specialty... but yeah, if I recall correctly the only assumptions are generally about stuff like that you have sufficient exploration (always keep exploring, but rate of exploration decreasing over time) and that sort of stuff. There definitely can be convergence for non-greedy policies.  
  > **username_4**: Your formula $G_{t:t+n} = R_{t + 1} + \gamma R_{t + 2} + \gamma^2 \max_a Q_{t + n - 1}(S_{t + 2}, a)$ seems to suggest this is $n$-step Q-learinng. Could you please elaborate their similarities and differences? $n$-step Q-learning should use importance sampling. Your formula does not. How can they be both unbiased.  
  
  ---
  
  