Answers.Body: <blockquote>
  <p>This would mean we decrease the value of this state.</p>
  </blockquote>
  <p>Yes. This update that reduces the estimate is <em>correct</em> because it adjusts for the inevitable over-estimate of value when the exploration policy selects an action that is more likely in the target policy than in the behaviour policy. This over-estimate must happen, if your agent experiences some actions with a likelihood ratio close to <span class="math-container">$0$</span>, it must also experience some actions with a likelihood ratio greater than <span class="math-container">$1$</span>. This follows because <span class="math-container">$\mathbb{E}_{\mu}[\frac{\pi(a|s)}{\mu(a|s)}] = 1$</span>*, provided the behaviour policy covers the target policy (behaviour policy has non-zero probability for all actions where the target policy has non-zero probability).</p>
  <p>Those actions with a likelihood ratio greater than <span class="math-container">$1$</span> are not actually <em>better</em> than before due to being taken off-policy, so their value used in the update will be an over-estimate.</p>
  <p>It is only in the limit of large numbers of samples that the adjusted value function will converge on a good estimate of the value function for the target policy.</p>
  <p>Basic importance sampling can have problems with increased variance due to this effect. In fact the variance can be shown to be unbound/infinite in some cases. I am not sure if it is the case in TD learning, but definitely the case in Monte Carlo with importance sampling. TD(0) does benefit from reduced variance from bootstrapping, so it probably doesn't have unbound variance. Still, it has higher variance than on-policy TD(0).</p>
  <hr />
  <p>*</p>
  <p>For any fixed state, <span class="math-container">$s$</span>,</p>
  <p><span class="math-container">$$\mathbb{E}_{\mu}[\frac{\pi(a|s)}{\mu(a|s)}] = \sum_a \mu(a|s) \frac{\pi(a|s)}{\mu(a|s)} = \sum_a \pi(a|s) = 1$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-09T09:18:14.717Z
Answers.Text: Great explanation, thank you very much. 
  So it's only when we consider multiple updates it's starting to be a correct update. 
  If we'd have only 1 or 2 it wouldn't be that good.
Answers.UserDisplayName: KoKlA
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-09T09:19:26.633Z
Answers.Text: @KoKlA Yes, although "just one or two" would also be bad in most on-policy TD(0) as well due to initial bootstrap bias. The difference with importance sampling is that you need even more samples. But the benefit is being able to separate the need for exploring from the need to learn a specific target.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-12T19:32:31.283Z
Answers.Text: I don't agree on your explanation on the overestimation, because in the tabular case, there is no such thing as overestimation, it's not like Q learning
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-12T19:43:15.347Z
Answers.Text: Say I throw a coin, and play head with P=1, then the value will be $E[Q(x)] = p(H)Q(H) + p(T)Q(T)$, and if I leave a friend that plays heads and tails with P=0.5 I get $ = E[p(x)/b(x)Q(x)] = p(H)Q(H) + p(T)Q(T)$
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-12T19:45:45.683Z
Answers.Text: thus given that he sometimes plays tail, I should not consider any of its rewards coming from them, thus, makes no sense that we should "reduce the overestimation"... instead, in my opinion, the importance sampling ratio should stay in front of the whole update, having $V = V + \pi/b[TD]$
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-12T20:35:16.117Z
Answers.Text: @AlbertoSinigaglia I don't follow your comments, and this answer is from almost 2 years ago, so I am not in the correct space to pick it up and figure out what you are saying. If you are disagreeing with D.Silver's slide, I'm willing to bet you are wrong. If it is just my explanation, perhaps I am wrong, but I cannot figure out what you are trying to say. I suggest ask a new question on the site, and give more details. Don't use "me and my friend" as examples because it is not clear what the behaviour and target policies are - use "behaviour" and "target".
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-12T22:01:34.553Z
Answers.Text: @NeilSlater you are right, maybe a different question and not using friends analogies might be better, sorry for that... let's consider then what Sutton published https://icml.cc/2012/papers/268.pdf page 4 end of first column: (given $u$ being the value function parameters) $u_{t+1} - u_{t} = \alpha\rho \psi (R - V)$, which simplified becomes $u_{t+1} - u_{t} = \alpha \frac{\nabla\pi}{b}(R-V)$... thus the value update is the regression error times the importance sampling ratio, and considering that $E[R] = E[r_t + V(s')]$ we can change it in the parenthesis which brings to my point
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-13T06:57:20.193Z
Answers.Text: @AlbertoSinigaglia Yes, this answer is about correct sampling to meet the expectation, and what would happen in *unweighted* importance sampling if you neglected to include the zero target updates. This would result in an overestimate of the maginitude of the return - the zero samples are required for the expectation and sampling to match. Please do ask another question on the site if this is not clear
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-14T10:54:42.660Z
Answers.Text: @NeilSlater done https://ai.stackexchange.com/questions/41284/correction-of-value-update-in-off-policy-td0
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-08T22:06:57.040Z
Answers.LastActivityDate: 2021-11-08T22:42:38.647Z
Answers.LastEditDate: 2021-11-08T22:42:38.647Z
Answers.UserDisplayName: Neil Slater
Body: <p>The update formula for the TD(0) off-policy learning algorithm is (taken from <a href="https://www.davidsilver.uk/wp-content/uploads/2020/03/control.pdf#page=34" rel="nofollow noreferrer">these slides</a> by D. Silver for lecture 5 of his course)</p>
  <p><span class="math-container">$$ \underbrace{V(S_t)}_{\text{New value}} \leftarrow \underbrace{V(S_t)}_{\text{Old value}} + \alpha \left( \frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)} (\underbrace{R_{t+1} + \gamma V(S_{t+1}))}_{\text{TD target}} - \underbrace{V(S_t)}_{\text{Old value}} \right) $$</span></p>
  <p>where <span class="math-container">$\frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)}$</span> is the ratio of the likelihoods that policy <span class="math-container">$\pi$</span> will take this action at this state divided by the likelihood that behavior policy <span class="math-container">$\mu$</span> takes this action at this state.</p>
  <p>What I do not understand is:</p>
  <p>Assume the behavior policy <span class="math-container">$\mu$</span> took an action that is very unlikely to happen under policy <span class="math-container">$\pi$</span>. I would assume this term goes towards <span class="math-container">$0$</span>.</p>
  <p><span class="math-container">$$  \frac{ \pi(A_t|S_t)}{\mu (A_t|S_t)}  = 0 $$</span></p>
  <p>But, if this term goes to <span class="math-container">$0$</span>, the whole equation would become the following</p>
  <p><span class="math-container">$$ V(S_t) \leftarrow V(S_t) - \alpha V(S_t) $$</span></p>
  <p>This would mean we decrease the value of this state.</p>
  <p>But this doesn't make any sense to me, if the 2 policies are very different, we gain little to no information. Therefore, I would assume the value would be unchanged instead of decreased.</p>
  <p>What is my misconception here?</p>
  
Tags: <reinforcement-learning><temporal-difference-methods><off-policy-methods><importance-sampling>
Title: How does this TD(0) off-policy value update formula work?
UserDisplayName: KoKlA
ThreadText: # How does this TD(0) off-policy value update formula work?
  
  (Asked by: username_0 on 2021-11-08)
  
  The update formula for the TD(0) off-policy learning algorithm is (taken from [these slides](https://www.davidsilver.uk/wp-content/uploads/2020/03/control.pdf#page=34) by D. Silver for lecture 5 of his course)
  
  $$ \underbrace{V(S\_t)}\_{\text{New value}} \leftarrow \underbrace{V(S\_t)}\_{\text{Old value}} + \alpha \left( \frac{ \pi(A\_t|S\_t)}{\mu (A\_t|S\_t)} (\underbrace{R\_{t+1} + \gamma V(S\_{t+1}))}\_{\text{TD target}} - \underbrace{V(S\_t)}\_{\text{Old value}} \right) $$
  
  where $\frac{ \pi(A\_t|S\_t)}{\mu (A\_t|S\_t)}$ is the ratio of the likelihoods that policy $\pi$ will take this action at this state divided by the likelihood that behavior policy $\mu$ takes this action at this state.
  
  What I do not understand is:
  
  Assume the behavior policy $\mu$ took an action that is very unlikely to happen under policy $\pi$. I would assume this term goes towards $0$.
  
  $$ \frac{ \pi(A\_t|S\_t)}{\mu (A\_t|S\_t)} = 0 $$
  
  But, if this term goes to $0$, the whole equation would become the following
  
  $$ V(S\_t) \leftarrow V(S\_t) - \alpha V(S\_t) $$
  
  This would mean we decrease the value of this state.
  
  But this doesn't make any sense to me, if the 2 policies are very different, we gain little to no information. Therefore, I would assume the value would be unchanged instead of decreased.
  
  What is my misconception here?
  
  **Tags:** reinforcement-learning, temporal-difference-methods, off-policy-methods, importance-sampling
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-11-08. Score: 2 | Accepted answer
  
  > This would mean we decrease the value of this state.
  
  Yes. This update that reduces the estimate is *correct* because it adjusts for the inevitable over-estimate of value when the exploration policy selects an action that is more likely in the target policy than in the behaviour policy. This over-estimate must happen, if your agent experiences some actions with a likelihood ratio close to $0$, it must also experience some actions with a likelihood ratio greater than $1$. This follows because $\mathbb{E}\_{\mu}[\frac{\pi(a|s)}{\mu(a|s)}] = 1$\*, provided the behaviour policy covers the target policy (behaviour policy has non-zero probability for all actions where the target policy has non-zero probability).
  
  Those actions with a likelihood ratio greater than $1$ are not actually *better* than before due to being taken off-policy, so their value used in the update will be an over-estimate.
  
  It is only in the limit of large numbers of samples that the adjusted value function will converge on a good estimate of the value function for the target policy.
  
  Basic importance sampling can have problems with increased variance due to this effect. In fact the variance can be shown to be unbound/infinite in some cases. I am not sure if it is the case in TD learning, but definitely the case in Monte Carlo with importance sampling. TD(0) does benefit from reduced variance from bootstrapping, so it probably doesn't have unbound variance. Still, it has higher variance than on-policy TD(0).
  
  ---
  
  \*
  
  For any fixed state, $s$,
  
  $$\mathbb{E}\_{\mu}[\frac{\pi(a|s)}{\mu(a|s)}] = \sum\_a \mu(a|s) \frac{\pi(a|s)}{\mu(a|s)} = \sum\_a \pi(a|s) = 1$$
  
  > **Comments:**
  > **username_0**: Great explanation, thank you very much.  So it's only when we consider multiple updates it's starting to be a correct update.  If we'd have only 1 or 2 it wouldn't be that good.  
  > **username_1**: @KoKlA Yes, although "just one or two" would also be bad in most on-policy TD(0) as well due to initial bootstrap bias. The difference with importance sampling is that you need even more samples. But the benefit is being able to separate the need for exploring from the need to learn a specific target.  
  > **username_2**: I don't agree on your explanation on the overestimation, because in the tabular case, there is no such thing as overestimation, it's not like Q learning  
  > **username_2**: Say I throw a coin, and play head with P=1, then the value will be $E[Q(x)] = p(H)Q(H) + p(T)Q(T)$, and if I leave a friend that plays heads and tails with P=0.5 I get $ = E[p(x)/b(x)Q(x)] = p(H)Q(H) + p(T)Q(T)$  
  > **username_2**: thus given that he sometimes plays tail, I should not consider any of its rewards coming from them, thus, makes no sense that we should "reduce the overestimation"... instead, in my opinion, the importance sampling ratio should stay in front of the whole update, having $V = V + \pi/b[TD]$  
  > **username_1**: @AlbertoSinigaglia I don't follow your comments, and this answer is from almost 2 years ago, so I am not in the correct space to pick it up and figure out what you are saying. If you are disagreeing with D.Silver's slide, I'm willing to bet you are wrong. If it is just my explanation, perhaps I am wrong, but I cannot figure out what you are trying to say. I suggest ask a new question on the site, and give more details. Don't use "me and my friend" as examples because it is not clear what the behaviour and target policies are - use "behaviour" and "target".  
  > **username_2**: @NeilSlater you are right, maybe a different question and not using friends analogies might be better, sorry for that... let's consider then what Sutton published https://icml.cc/2012/papers/268.pdf page 4 end of first column: (given $u$ being the value function parameters) $u_{t+1} - u_{t} = \alpha\rho \psi (R - V)$, which simplified becomes $u_{t+1} - u_{t} = \alpha \frac{\nabla\pi}{b}(R-V)$... thus the value update is the regression error times the importance sampling ratio, and considering that $E[R] = E[r_t + V(s')]$ we can change it in the parenthesis which brings to my point  
  > **username_1**: @AlbertoSinigaglia Yes, this answer is about correct sampling to meet the expectation, and what would happen in *unweighted* importance sampling if you neglected to include the zero target updates. This would result in an overestimate of the maginitude of the return - the zero samples are required for the expectation and sampling to match. Please do ask another question on the site if this is not clear  
  > **username_2**: @NeilSlater done https://ai.stackexchange.com/questions/41284/correction-of-value-update-in-off-policy-td0  
  
  ---
  
  