Answers.Body: <p>Good question. I think this part of the book is not well explained.</p>
  <p>Off-policy evaluation of <span class="math-container">$V$</span> by itself doesn't make sense, IMO.</p>
  <p>I think there are two cases here</p>
  <ol>
  <li><p>is if <span class="math-container">$\pi$</span> is deterministic, as we probably want in the case of &quot;control&quot;, i.e. we will determine <span class="math-container">$\pi$</span> to be deterministic and in every state choose the action that most likely to maximize the rewards/returns.
  In that case, then evaluating <span class="math-container">$V$</span> from a different distribution might not be so useful, as <span class="math-container">$W$</span> becomes <span class="math-container">$0$</span> with high likelihood. I don't see any sense in it.</p>
  </li>
  <li><p>if <span class="math-container">$\pi$</span> is not deterministic. And it's a good question why would we want to evaluate <span class="math-container">$V_\pi$</span> from <span class="math-container">$V_b$</span>, instead of just evaluating it from <span class="math-container">$V_\pi$</span> directly.</p>
  </li>
  </ol>
  <p>So, IMO, off-policy evaluation of <span class="math-container">$V_\pi$</span> doesn't make any sense.</p>
  <p>However, I think the goal here is actually the <strong>control algorithm</strong> given in the book (using <span class="math-container">$q(s,a)$</span>, p. 111 of the book [133 of the pdf]). The idea here is to use some arbitrary behavior/exploratory policy and, while it runs, update (&quot;control&quot;) the policy <span class="math-container">$\pi$</span>. In there, you use the update rule for <span class="math-container">$W$</span>, which uses the idea of importance sampling - i.e. how to update the expected value of <span class="math-container">$\pi$</span> based on <span class="math-container">$b$</span>. But there it ACTUALLY makes sense.</p>
  <p>So, I suspect the evaluation was given by itself just so the reader can better understand how to do the evaluation, though it really doesn't make sense outside the control algorithm.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-05T22:08:19.520Z
Answers.Text: You're using the symbol $W$ here, but you're not defining it. I suggest that you define it to make your answer clearer.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-25T19:17:29.457Z
Answers.Text: $W$ (as well as $V$, $\pi$ and other symbols) is defined in the book (for example in the page 111 as mentioned later). But yes, the answer writeup could be improved to make that more clear, especially since $W$ is only introduced *after* Section 5.5 the asker is referring to.
Answers.UserDisplayName: user118967
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-08T10:03:11.990Z
Answers.LastActivityDate: 2020-11-05T22:08:00.130Z
Answers.LastEditDate: 2020-11-05T22:08:00.130Z
Answers.UserDisplayName: Maverick Meerkat
Answers.Body: <p>You're correct, when the target policy <span class="math-container">$\pi$</span> is deterministic, the importance sampling ratio will be <span class="math-container">$\geq 1$</span> along the trajectory where the behaviour policy <span class="math-container">$b$</span> happened to have taken the same actions that <span class="math-container">$\pi$</span> would have taken, and turns to <span class="math-container">$0$</span> as soon as <span class="math-container">$b$</span> makes one "mistake" (selects an action that <span class="math-container">$\pi$</span> would not have selected).</p>
  
  <p>Before importance sampling is introduced in the book, I believe the only off-policy method you will have seen is one-step <span class="math-container">$Q$</span>-learning, which can only propagate observations back along exactly one step. With the importance sampling ratio, you can often do a bit better. You're right, there is a risk that it turns to <span class="math-container">$0$</span> rather quickly (especially when <span class="math-container">$\pi$</span> and <span class="math-container">$b$</span> are very different from each other), at which point it essentially "truncates" your trajectory and ignores all subsequent experience... but that still can be better than one-step, there is a chance that the ratio will remain <span class="math-container">$1$</span> for at least a few steps. It will occasionally still only permit <span class="math-container">$1$</span>-step returns, but also sometimes <span class="math-container">$2$</span>-step returns, sometimes <span class="math-container">$3$</span>-step returns, etc., which is often better than only having <span class="math-container">$1$</span>-step returns.</p>
  
  <p>Whenever the importance sampling ratio is not <span class="math-container">$0$</span>, it can also give more emphasis to the observations resulting from trajectories that would be common under <span class="math-container">$\pi$</span>, but are uncommon under <span class="math-container">$b$</span>. Such trajectories will have a ratio <span class="math-container">$&gt; 1$</span>. Emphasizing such trajectories more can be beneficial, because they don't get experienced often under <span class="math-container">$b$</span>, so without the extra emphasis it can be difficult to properly learn what would have happened under <span class="math-container">$\pi$</span>.</p>
  
  <hr>
  
  <p>Of course, it is also worth noting that your quote says (emphasis mine):</p>
  
  <blockquote>
    <p>The target policy <span class="math-container">$\pi$</span> [...] <strong>may</strong> be deterministic [...]</p>
  </blockquote>
  
  <p>It says that <span class="math-container">$\pi$</span> <strong>may</strong> be deterministic (and in practice it very often is, because we very often take <span class="math-container">$\pi$</span> to be the greedy policy)... but sometimes it won't be. The entire approach using the importance sampling ratio is well-defined also for cases where we choose <span class="math-container">$\pi$</span> <strong>not</strong> to be deterministic. In such situations, we'll often be able to propagate observations over significantly longer trajectories (although there is also a risk of excessive variance and/or numeric instability when <span class="math-container">$b$</span> selects actions that are highly unlikely according to <span class="math-container">$b$</span>, but highly likely according to <span class="math-container">$\pi$</span>).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-29T23:57:00.750Z
Answers.Text: "It will [...] sometimes permit k-step (k is a small integer) returns [...] which is often better than only having 1-step returns." Only a tiny fraction of states will occur within k steps from the terminal state. So most state values will be never updated. Thus, unless I missed something, this off-policy MC control algorithm won't work at all - except in some hand-picked problems (e.g., where the entire trajectory is extremely short).
Answers.UserDisplayName: max
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-30T10:47:41.883Z
Answers.Text: @max If you want to very strictly only talk about Monte-Carlo control, I guess you're right. As soon as you move to algorithms that involve bootstrapping (like Q-learning), this situation improves though.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-25T20:44:26.600Z
Answers.Text: I suspect this answer is not correct (even if we discount the statement that $Q$-learning is mentioned before off-policy Monte Carlo). It is based on the idea that some steps will be useful until $b$ takes a step differently from one acceptable to $\pi$, but off-policy Monte Carlo estimation works on entire trajectories at once. So even if some $k$ first steps agree with $\pi$, the whole trajectory will still have weight $0$ if the $(k+1)$-th step does not, and no information from any part of the trajectory will be used.
Answers.UserDisplayName: user118967
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-26T10:28:02.363Z
Answers.Text: @user118967 Ah, I see you're right that apparently $Q$-learning is indeed introduced later in the book. Anyway, apart from that, no my answer is correct. Note 2 things: (1) while importance sampling here happens to be introduced in the chapter on MC methods, the definition of the IS ratio is not unique to MC chapters, and carries over into later chapters.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-26T10:28:59.587Z
Answers.Text: (2) Even for MC methods, the IS ratio $\rho_{t:T-1}$ is not computed over the full trajectory. It's computed with $t$ as starting point when estimating the value for a state encountered at $t$. So, indeed for states $s_t$ that were encountered near the beginning of the trajectory, the ratio  will be very likely to be $0$, and it's very unlikely to have effective learning. But for states $s_t$ that were encountered closer towards the end of a trajectory, it is more likely to get non-zero ratios and effective learning.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-26T21:01:48.973Z
Answers.Text: @DennisSoemers Yes, I think the IS ratio becomes relevant in later chapters, but the original question was meant for the MC section of the book. This is important, because for first-time readers, using IS with MC will make no sense (as Maverick Meerkat's answer suggests).
Answers.UserDisplayName: user118967
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-26T21:04:32.977Z
Answers.Text: As for your point (2), sure, for time steps near the end of the episode it will be more likely that behavioral policy agrees with the target policy, _but_ the point of the original question is: why use IS and offline policy estimation at all, if it only works for trajectories that the target policy could generate anyway? Sure, it will work on the cases you mentioned, but just using the target policy would be simpler _and_ also work just as well.
Answers.UserDisplayName: user118967
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-26T21:06:10.317Z
Answers.Text: So I believe the best answer to the original question would be: "yes, the book messed up, it presents off-policy MC estimation as useful when it actually is not useful. They were just introducing a concept that is useful only in later chapters", as opposed to "off-policy MC estimation is useful in such and such cases".
Answers.UserDisplayName: user118967
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-27T10:03:20.777Z
Answers.Text: @user118967 That's not how I read the original question at all. As far as I can see, the OP is just trying to verify that their understanding was correct / they weren't missing some important detail. They're not asking about the practical usefulness. I'd also note it's not always possible to "just use the target policy". For example, if you were previously using a non-RL system (e.g., to serve ads or whatever), you have already collected relevant data from that older system (policy). You can train or evaluate offline, off-policy on this existing data.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-28T19:51:01.373Z
Answers.Text: @DennisSoemers, these are good points, thanks. I appreciate the point about a target policy not being available for generating episodes. In this case, I would encourage you to edit the answer to improve two points, the main one being that in MC, learning is not done step-by-step, but episode-by-episode, and the secondary one being the comment about $Q$-learning coming before MC.
Answers.UserDisplayName: user118967
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-09T21:22:19.217Z
Answers.Text: Just wanted to mention that one-step Q-Learning is not before the introduction of importance-sampling (if anyone searches for it). At least not in the 2018 version.
Answers.UserDisplayName: F.M.F.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-10T08:10:46.833Z
Answers.Text: @F.M.F. You're right. Q-learning seems so much simpler to explain and conceptually understand though, I'd always start with that first.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-09T17:58:58.743Z
Answers.LastActivityDate: 2019-01-10T08:40:51.960Z
Answers.LastEditDate: 2019-01-10T08:40:51.960Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>In the book <a href="http://incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">Reinforcement Learning: An Introduction (2nd edition)</a> Sutton and Barto define at <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=126" rel="nofollow noreferrer">page 104 (p. 126 of the pdf), equation (5.3),</a> the importance sampling ratio, <span class="math-container">$\rho _{t:T-1}$</span>, as follows:</p>
  <p><span class="math-container">$$\rho _{t:T-1}=\prod_{k=t}^{T-1}\frac{\pi(A_k|S_k)}{b(A_k|S_k)}$$</span></p>
  <p>for a target policy <span class="math-container">$\pi$</span> and a behavior policy <span class="math-container">$b$</span>.</p>
  <p>However, on page 103, they state:</p>
  <blockquote>
  <p>The target policy <span class="math-container">$\pi$</span> [...] may be deterministic [...].</p>
  </blockquote>
  <p>When <span class="math-container">$\pi$</span> is deterministic and greedy it gives <span class="math-container">$1$</span> for the greedy action and 0 for all other possible actions.</p>
  <p>So, how can the above formula give something else than zero, except for the case where policy <span class="math-container">$b$</span> takes a path that <span class="math-container">$\pi$</span> would have taken as well? If any selected action of <span class="math-container">$b$</span> is different from <span class="math-container">$\pi$</span>'s choice, then the whole numerator is zero and thus the whole result.</p>
  
Tags: <reinforcement-learning><off-policy-methods><sutton-barto><importance-sampling>
Title: How can the importance sampling ratio be different than zero when the target policy is deterministic?
UserDisplayName: F.M.F.
ThreadText: # How can the importance sampling ratio be different than zero when the target policy is deterministic?
  
  (Asked by: username_0 on 2019-01-09)
  
  In the book [Reinforcement Learning: An Introduction (2nd edition)](http://incompleteideas.net/book/RLbook2020.pdf) Sutton and Barto define at [page 104 (p. 126 of the pdf), equation (5.3),](http://incompleteideas.net/book/RLbook2020.pdf#page=126) the importance sampling ratio, $\rho \_{t:T-1}$, as follows:
  
  $$\rho \_{t:T-1}=\prod\_{k=t}^{T-1}\frac{\pi(A\_k|S\_k)}{b(A\_k|S\_k)}$$
  
  for a target policy $\pi$ and a behavior policy $b$.
  
  However, on page 103, they state:
  
  > The target policy $\pi$ [...] may be deterministic [...].
  
  When $\pi$ is deterministic and greedy it gives $1$ for the greedy action and 0 for all other possible actions.
  
  So, how can the above formula give something else than zero, except for the case where policy $b$ takes a path that $\pi$ would have taken as well? If any selected action of $b$ is different from $\pi$'s choice, then the whole numerator is zero and thus the whole result.
  
  **Tags:** reinforcement-learning, off-policy-methods, sutton-barto, importance-sampling
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2019-01-09. Score: 5 | Accepted answer
  
  You're correct, when the target policy $\pi$ is deterministic, the importance sampling ratio will be $\geq 1$ along the trajectory where the behaviour policy $b$ happened to have taken the same actions that $\pi$ would have taken, and turns to $0$ as soon as $b$ makes one "mistake" (selects an action that $\pi$ would not have selected).
  
  Before importance sampling is introduced in the book, I believe the only off-policy method you will have seen is one-step $Q$-learning, which can only propagate observations back along exactly one step. With the importance sampling ratio, you can often do a bit better. You're right, there is a risk that it turns to $0$ rather quickly (especially when $\pi$ and $b$ are very different from each other), at which point it essentially "truncates" your trajectory and ignores all subsequent experience... but that still can be better than one-step, there is a chance that the ratio will remain $1$ for at least a few steps. It will occasionally still only permit $1$-step returns, but also sometimes $2$-step returns, sometimes $3$-step returns, etc., which is often better than only having $1$-step returns.
  
  Whenever the importance sampling ratio is not $0$, it can also give more emphasis to the observations resulting from trajectories that would be common under $\pi$, but are uncommon under $b$. Such trajectories will have a ratio $> 1$. Emphasizing such trajectories more can be beneficial, because they don't get experienced often under $b$, so without the extra emphasis it can be difficult to properly learn what would have happened under $\pi$.
  
  ---
  
  Of course, it is also worth noting that your quote says (emphasis mine):
  
  > The target policy $\pi$ [...] **may** be deterministic [...]
  
  It says that $\pi$ **may** be deterministic (and in practice it very often is, because we very often take $\pi$ to be the greedy policy)... but sometimes it won't be. The entire approach using the importance sampling ratio is well-defined also for cases where we choose $\pi$ **not** to be deterministic. In such situations, we'll often be able to propagate observations over significantly longer trajectories (although there is also a risk of excessive variance and/or numeric instability when $b$ selects actions that are highly unlikely according to $b$, but highly likely according to $\pi$).
  
  > **Comments:**
  > **username_0**: Just wanted to mention that one-step Q-Learning is not before the introduction of importance-sampling (if anyone searches for it). At least not in the 2018 version.  
  > **username_4**: @F.M.F. You're right. Q-learning seems so much simpler to explain and conceptually understand though, I'd always start with that first.  
  > **username_3**: I suspect this answer is not correct (even if we discount the statement that $Q$-learning is mentioned before off-policy Monte Carlo). It is based on the idea that some steps will be useful until $b$ takes a step differently from one acceptable to $\pi$, but off-policy Monte Carlo estimation works on entire trajectories at once. So even if some $k$ first steps agree with $\pi$, the whole trajectory will still have weight $0$ if the $(k+1)$-th step does not, and no information from any part of the trajectory will be used.  
  > **username_4**: @user118967 Ah, I see you're right that apparently $Q$-learning is indeed introduced later in the book. Anyway, apart from that, no my answer is correct. Note 2 things: (1) while importance sampling here happens to be introduced in the chapter on MC methods, the definition of the IS ratio is not unique to MC chapters, and carries over into later chapters.  
  > **username_4**: (2) Even for MC methods, the IS ratio $\rho_{t:T-1}$ is not computed over the full trajectory. It's computed with $t$ as starting point when estimating the value for a state encountered at $t$. So, indeed for states $s_t$ that were encountered near the beginning of the trajectory, the ratio  will be very likely to be $0$, and it's very unlikely to have effective learning. But for states $s_t$ that were encountered closer towards the end of a trajectory, it is more likely to get non-zero ratios and effective learning.  
  > **username_3**: @DennisSoemers Yes, I think the IS ratio becomes relevant in later chapters, but the original question was meant for the MC section of the book. This is important, because for first-time readers, using IS with MC will make no sense (as Maverick Meerkat's answer suggests).  
  > **username_3**: As for your point (2), sure, for time steps near the end of the episode it will be more likely that behavioral policy agrees with the target policy, _but_ the point of the original question is: why use IS and offline policy estimation at all, if it only works for trajectories that the target policy could generate anyway? Sure, it will work on the cases you mentioned, but just using the target policy would be simpler _and_ also work just as well.  
  > **username_3**: So I believe the best answer to the original question would be: "yes, the book messed up, it presents off-policy MC estimation as useful when it actually is not useful. They were just introducing a concept that is useful only in later chapters", as opposed to "off-policy MC estimation is useful in such and such cases".  
  > **username_4**: @user118967 That's not how I read the original question at all. As far as I can see, the OP is just trying to verify that their understanding was correct / they weren't missing some important detail. They're not asking about the practical usefulness. I'd also note it's not always possible to "just use the target policy". For example, if you were previously using a non-RL system (e.g., to serve ads or whatever), you have already collected relevant data from that older system (policy). You can train or evaluate offline, off-policy on this existing data.  
  > **username_3**: @DennisSoemers, these are good points, thanks. I appreciate the point about a target policy not being available for generating episodes. In this case, I would encourage you to edit the answer to improve two points, the main one being that in MC, learning is not done step-by-step, but episode-by-episode, and the secondary one being the comment about $Q$-learning coming before MC.  
  > **username_5**: "It will [...] sometimes permit k-step (k is a small integer) returns [...] which is often better than only having 1-step returns." Only a tiny fraction of states will occur within k steps from the terminal state. So most state values will be never updated. Thus, unless I missed something, this off-policy MC control algorithm won't work at all - except in some hand-picked problems (e.g., where the entire trajectory is extremely short).  
  > **username_4**: @max If you want to very strictly only talk about Monte-Carlo control, I guess you're right. As soon as you move to algorithms that involve bootstrapping (like Q-learning), this situation improves though.  
  
  ---
  
  ### Answer by username_1 on 2019-12-08. Score: 1
  
  Good question. I think this part of the book is not well explained.
  
  Off-policy evaluation of $V$ by itself doesn't make sense, IMO.
  
  I think there are two cases here
  
  1. is if $\pi$ is deterministic, as we probably want in the case of "control", i.e. we will determine $\pi$ to be deterministic and in every state choose the action that most likely to maximize the rewards/returns.
     In that case, then evaluating $V$ from a different distribution might not be so useful, as $W$ becomes $0$ with high likelihood. I don't see any sense in it.
  2. if $\pi$ is not deterministic. And it's a good question why would we want to evaluate $V\_\pi$ from $V\_b$, instead of just evaluating it from $V\_\pi$ directly.
  
  So, IMO, off-policy evaluation of $V\_\pi$ doesn't make any sense.
  
  However, I think the goal here is actually the **control algorithm** given in the book (using $q(s,a)$, p. 111 of the book [133 of the pdf]). The idea here is to use some arbitrary behavior/exploratory policy and, while it runs, update ("control") the policy $\pi$. In there, you use the update rule for $W$, which uses the idea of importance sampling - i.e. how to update the expected value of $\pi$ based on $b$. But there it ACTUALLY makes sense.
  
  So, I suspect the evaluation was given by itself just so the reader can better understand how to do the evaluation, though it really doesn't make sense outside the control algorithm.
  
  > **Comments:**
  > **username_2**: You're using the symbol $W$ here, but you're not defining it. I suggest that you define it to make your answer clearer.  
  > **username_3**: $W$ (as well as $V$, $\pi$ and other symbols) is defined in the book (for example in the page 111 as mentioned later). But yes, the answer writeup could be improved to make that more clear, especially since $W$ is only introduced *after* Section 5.5 the asker is referring to.  
  
  ---
  
  