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

Question

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.

Answer 1

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 $$

give us something more general. We have

$$ \mathbb E_b[ \rho_{t:T-1} R_{t+k}] = \mathbb E_b[ \rho_{t:t+k-1} R_{t+k}] $$

This can be used to modify the n-step off policy expression so as to only include sampling when necessary and reduce the variance.