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.


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .