# How can I get Q-Learning (1 step off policy) update from n-step off policy learning update?

In Sutton and Barto we have expressions for Q-Learning and n-step Off policy learning. The former ought to be the 1-step limit of the latter but I cannot see it working out that way. What am I missing?

Concretely, in Sutton and Barto (edition 2) the expression for n-step off policy learning is given in equation 7.11 as

$$Q_{t+n}(S_t,A_t) = Q_{t+n-1}(S_t,A_t) + \alpha \rho_{t+1:t+n} [G_{t:t+n}-Q_{t+n-1}(S_t,A_t)]$$ where $$G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^n Q_{t+n-1}(S_{t+n},A_{t+n}) \\ \rho_{t:h} = \prod_{k=t}^{min(h,T-1)} \frac{\pi(A_k|S_k)}{b(A_k|S_k)}$$ Here $$\pi$$ is the target policy and $$b$$ is the policy being followed.

If I take n=1 above I get $$Q_{t+1}(S_t,A_t) = Q_{t}(S_t,A_t) + \alpha \frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})} [R_{t+1} + \gamma Q_t(S_{t+1},A_{t+1})-Q_{t}(S_t,A_t)]$$ If the target policy is the greedy policy then we will further get $$Q_{t+1}(S_t,A_t) = Q_{t}(S_t,A_t) + \alpha \frac{1}{b(a|S_{t+1})} [R_{t+1} + \gamma Q_t(S_{t+1},a)-Q_{t}(S_t,A_t)]$$ where $$a = \text{argmax}_{a'} Q_t(S_{t+1},a')$$

Nevertheless, the Q-Learning update given in equation 6.8 is

$$Q_{t+1}(S_t,A_t) = Q_{t}(S_t,A_t) + \alpha [R_{t+1} + \gamma \max_a Q_t(S_{t+1},a)-Q_{t}(S_t,A_t)]$$

How do I reconcile these two expressions? Indeed, looking at David Silver's lecture notes it even seems that the n=1 limit of the n-step off policy expression doesn't match that either.

The match only holds in expectation. To see this first note that the reward $$R_{t+1}$$ is obtained on taking action $$A_t$$ and thus $$\mathbb E_b [R_{t+1} \frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}|S_t,A_t] = \mathbb E_b [R_{t+1}|S_t,A_t] \mathbb E_b [\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}|S_t,A_t] \\ = \mathbb E_b [R_{t+1}|S_t,A_t]$$ Then recall that in general for importance sampling $$\mathbb E_b [Q_t(S_{t+1},A_{t+1})\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}|S_t,A_t] = \mathbb E_\pi [Q_t(S_{t+1},A_{t+1})|S_t,A_t]$$ Now suppose $$\pi$$ is the greedy policy and with $$a= argmax_x Q_t(S_{t+1},x)$$ we have $$\mathbb E_b [Q_t(S_{t+1},A_{t+1})\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}|S_t,A_t] \\ = \mathbb E_b [Q_t(S_{t+1},a)\frac{\delta_{a,A_{t+1}}}{b(A_{t+1}|S_{t+1})}|S_t,A_t]\\ = \sum_{S_{t+1}} Q_t(S_{t+1},a) ~p(S_{t+1}|S_t,A_t)$$ However, we also trivially have $$\mathbb E_b [Q_t(S_{t+1},a)|S_t,A_t] \\ = \sum_{S_{t+1}} Q_t(S_{t+1},a) ~p(S_{t+1}|S_t,A_t)$$
Thus, in expectation we have the sampling of $$Q_t(S_{t+1},a)$$ and $$Q_t(S_{t+1},a)\frac{\delta_{a,A_{t+1}}}{b(a|S_{t+1})}$$ under policy $$b$$ give the same result. Thus we thus we see that in the special case of $$n=1$$ we in fact do not need to sample at all. Note that sampling unnecessarily we increase variance.
Furthemore, causality and the fact that $$\mathbb E_b [ \frac{\pi(A_k|S_k)}{b(A_k|S_k)}] = 1$$
$$\mathbb E_b[ \rho_{t:T-1} R_{t+k}] = \mathbb E_b[ \rho_{t:t+k-1} R_{t+k}]$$