Answers.Body: <p>The match only holds in expectation. To see this first note that the reward <span class="math-container">$R_{t+1}$</span> is obtained on taking action <span class="math-container">$A_t$</span> and thus
  <span class="math-container">$$
  \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] 
  $$</span>
  Then recall that in general for importance sampling
  <span class="math-container">$$
  \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]
  $$</span>
  Now suppose <span class="math-container">$\pi$</span> is the greedy policy and with <span class="math-container">$a= argmax_x Q_t(S_{t+1},x)$</span> we have
  <span class="math-container">$$
  \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)
  $$</span>
  However, we also trivially have
  <span class="math-container">$$
  \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)
  $$</span></p>
  <p>Thus, in expectation we have the sampling of <span class="math-container">$Q_t(S_{t+1},a)$</span> and <span class="math-container">$Q_t(S_{t+1},a)\frac{\delta_{a,A_{t+1}}}{b(a|S_{t+1})}$</span> under policy <span class="math-container">$b$</span> give the same result.
  Thus we thus we see that in the special case of <span class="math-container">$n=1$</span> we in fact do not need to sample at all. Note that sampling unnecessarily we increase variance.</p>
  <p>Furthemore, causality and the fact that
  <span class="math-container">$$
  \mathbb E_b [ \frac{\pi(A_k|S_k)}{b(A_k|S_k)}] = 1
  $$</span></p>
  <p>give us something more general. We have</p>
  <p><span class="math-container">$$
  \mathbb E_b[ \rho_{t:T-1} R_{t+k}]  = 
  \mathbb E_b[ \rho_{t:t+k-1} R_{t+k}] 
  $$</span></p>
  <p>This can be used to modify the n-step off policy expression so as to only include sampling when necessary and reduce the variance.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-04T00:00:03.427Z
Answers.LastActivityDate: 2023-02-05T19:24:06.187Z
Answers.LastEditDate: 2023-02-05T19:24:06.187Z
Answers.UserDisplayName: Borun Chowdhury
Body: <p>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?</p>
  <p>Concretely, in Sutton and Barto (edition 2) the expression for n-step off policy learning is given in equation 7.11 as</p>
  <p><span class="math-container">$$
  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)]
  $$</span>
  where
  <span class="math-container">$$
  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)}
  $$</span>
  Here <span class="math-container">$\pi$</span> is the target policy and <span class="math-container">$b$</span> is the policy being followed.</p>
  <p>If I take n=1 above I get
  <span class="math-container">$$
  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)]
  $$</span>
  If the target policy is the greedy policy then we will further get
  <span class="math-container">$$
  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)]
  $$</span>
  where <span class="math-container">$a = \text{argmax}_{a'} Q_t(S_{t+1},a')$</span></p>
  <p>Nevertheless, the Q-Learning update given in equation 6.8 is</p>
  <p><span class="math-container">$$
  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)]
  $$</span></p>
  <p>How do I reconcile these two expressions? Indeed, looking at David Silver's lecture <a href="https://www.davidsilver.uk/wp-content/uploads/2020/03/control.pdf#page=34" rel="nofollow noreferrer">notes</a> it even seems that the n=1 limit of the n-step off policy expression doesn't match that either.</p>
  
Tags: <reinforcement-learning><q-learning><sutton-barto><temporal-difference-methods>
Title: How can I get Q-Learning (1 step off policy) update from n-step off policy learning update?
UserDisplayName: Borun Chowdhury
ThreadText: # How can I get Q-Learning (1 step off policy) update from n-step off policy learning update?
  
  (Asked by: username_0 on 2023-01-02)
  
  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](https://www.davidsilver.uk/wp-content/uploads/2020/03/control.pdf#page=34) it even seems that the n=1 limit of the n-step off policy expression doesn't match that either.
  
  **Tags:** reinforcement-learning, q-learning, sutton-barto, temporal-difference-methods
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2023-01-04. Score: 0 | Accepted answer
  
  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.
  
  
  ---
  
  