Why is the n-step tree backup algorithm an off-policy algorithm?

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?

• Please, next time, even though the questions are related, ask them in separate posts: one question per post. – nbro May 18 '20 at 22:10

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).

• Would the convergence guarantees hold if the target policy is not greedy? The proof doesn't seem to make any such assumption. – Abhinav Gupta Oct 20 '20 at 10:02
• @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. – Dennis Soemers Oct 20 '20 at 14:35