Answers.Body: <p>Recall that our goal is to be able to accurately estimate the true value of each state by computing a sample average over returns starting from that state:
  <span class="math-container">$$v_{q}(s) \doteq \mathbb{E}_{q}\left[G_{t} | S_{t}=s\right] \approx \frac{1}{n} \sum_{i=1}^{n} Return_i $$</span>
  where <span class="math-container">$Return_i$</span> is the return obtained from the <span class="math-container">$i^{th}$</span> trajectory.</p>
  
  <p>The problem is that the <span class="math-container">$\approx $</span> does not hold, since in off-policy learning, we got those returns by following the behavior policy, <span class="math-container">$p$</span>, and not the target policy, <span class="math-container">$q$</span>. </p>
  
  <p>To address that, we have to correct each return in the sample average by multiplying by the importance sampling ratio. </p>
  
  <p><span class="math-container">$$v_{q}(s) \doteq \mathbb{E}_{q}\left[G_{t} | S_{t}=s\right] \approx \frac{1}{n} \sum_{i=1}^{n} \rho_i Return_i$$</span></p>
  
  <p>where the importance sampling ratio is : <span class="math-container">$\rho=\frac{\mathbb{P}(\text { trajectory under } q)}{\mathbb{P}(\text { trajectory under } p)}$</span></p>
  
  <p>What this multiplication does is that it increases the importance of returns that were more likely to be seen under the target policy <span class="math-container">$q$</span> and it decreases those that were less likely. So, at the end, in expectation, it would be as if the returns were averaged following <span class="math-container">$q$</span>. </p>
  
  <p>(A side note: To avoid the risks of mixing <span class="math-container">$p$</span> and <span class="math-container">$q$</span>, it might be a good idea to denote/think of the <strong>b</strong>ehavior policy as <span class="math-container">$b$</span> and the target policy as <span class="math-container">$\pi$</span>, following the convention in Sutton and Barto's RL book.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-22T12:50:53.870Z
Answers.LastActivityDate: 2020-05-23T00:18:37.807Z
Answers.LastEditDate: 2020-05-23T00:18:37.807Z
Answers.UserDisplayName: user5093249
Answers.Body: <p>Let's fix some notation: we're collecting data from behavior policy <span class="math-container">$\pi_0$</span> and we want to evaluate a policy <span class="math-container">$\pi$</span>.
  Of course, if we had plenty of data from policy <span class="math-container">$\pi$</span> that would be the best way to evaluate <span class="math-container">$\pi$</span> as we just take the empirical average (without any importance sampling) and CLT gives us confidence intervals that shrink at <span class="math-container">$\frac{1}{\sqrt n}$</span> rates.</p>
  <p>However, collecting data from <span class="math-container">$\pi$</span> is often time-consuming and costly: you may need to productionize it at a company, and if <span class="math-container">$\pi$</span> were dangerous, some damage could be done during rollouts. So how can we make the best use of our data from any policies, not necessarily <span class="math-container">$\pi$</span>, to evaluate <span class="math-container">$\pi$</span>? This is the question of off-policy evaluation, and you're right that IS is one approach.</p>
  <p>This picture from a <a href="https://www.youtube.com/watch?v=lzA5K4im2no&amp;ab_channel=CriteoLabs" rel="nofollow noreferrer">great talk by Thorsten</a> provides nice intuition on why the weighting is unbiased <a href="https://i.sstatic.net/h770z.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/h770z.jpg" alt="enter image description here" /></a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-26T05:33:05.963Z
Answers.LastActivityDate: 2020-11-26T05:33:05.963Z
Answers.UserDisplayName: kaiwenw
Answers.Body: <blockquote>
    <p>In the application of importance sampling to RL, is the expectation of the function <span class="math-container">$f$</span> equivalent to the value of the trajectories, which is represented by the trajectories <span class="math-container">$x$</span>? </p>
  </blockquote>
  
  <p>I believe what you are asking here is if when using importance sampling in the off-policy RL setting that we set <span class="math-container">$f(x)$</span> from the general importance sampling formula to be our returns - the answer to this is yes. As always we are interested in calculating our expected returns. </p>
  
  <blockquote>
    <p>How would the trajectories from the distribution <span class="math-container">$q$</span> be better than that
    of <span class="math-container">$p$</span>? I know from the equation how it is better but it is hard to
    understand intuitively why this could be so.</p>
  </blockquote>
  
  <p>I think here you got your <span class="math-container">$p$</span> and <span class="math-container">$q$</span> the wrong way around as we are using samples from <span class="math-container">$p$</span> to approximate our policy <span class="math-container">$q$</span>. We typically will use importance sampling to generate samples from a <em>different</em> policy to our target policy for a few reasons - one reason might be that our target policy is hard to sample from whereas sampling from our behaviour policy <span class="math-container">$p$</span> might be relatively easy to sample from. Another reason is that we generally want to learn an optimal policy, but this could be difficult to learn if we don't explore enough. So we can follow some other policy that will explore sufficiently and still learn about our optimal target policy through the importance sampling ratio.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-22T11:16:45.160Z
Answers.LastActivityDate: 2020-05-23T00:16:38.650Z
Answers.LastEditDate: 2020-05-23T00:16:38.650Z
Answers.UserDisplayName: David
Body: <p>The technique for off-policy value evaluation comes from importance sampling, which states that </p>
  
  <p><span class="math-container">$$E_{x \sim q}[f(x)] \approx \frac{1}{n}\sum_{i=1}^n f(x_i)\frac{q(x_i)}{p(x_i)},$$</span> where <span class="math-container">$x_i$</span> is sampled from <span class="math-container">$p$</span>.  </p>
  
  <p>In the application of importance sampling to RL, is the expectation of the function <span class="math-container">$f$</span> equivalent to the value of the trajectories, which is represented by the trajectories <span class="math-container">$x$</span>? </p>
  
  <p>The distributions <span class="math-container">$p$</span> represent the probability of sampling trajectories from the behavior policy and the distribution <span class="math-container">$q$</span> represents the probability of sampling trajectories from the target policy <span class="math-container">$q$</span>?</p>
  
  <p>How would the trajectories from distribution <span class="math-container">$q$</span> be better than that of <span class="math-container">$p$</span>? I know from the equation how it is better, but it is hard to understand intuitively why this could be so.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-22T11:04:18.680Z
Comments.Text: could you also elaborate on this sentence - 'is it correct to equate the expectation of the function  is equivalent to the value of the trajectories, which is represented by the trajectories ' please? I'm not quite sure what you mean.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-22T11:06:57.413Z
Comments.Text: Sorry i didn't explain it that well. I wanted to know how the terms in importance sampling are being applied in the off policy evaluation RL context.
Comments.UserDisplayName: calveeen
Tags: <reinforcement-learning><off-policy-methods><importance-sampling>
Title: What is the intuition behind importance sampling for off-policy value evaluation?
UserDisplayName: calveeen
ThreadText: # What is the intuition behind importance sampling for off-policy value evaluation?
  
  (Asked by: username_0 on 2020-05-22)
  
  The technique for off-policy value evaluation comes from importance sampling, which states that
  
  $$E\_{x \sim q}[f(x)] \approx \frac{1}{n}\sum\_{i=1}^n f(x\_i)\frac{q(x\_i)}{p(x\_i)},$$ where $x\_i$ is sampled from $p$.
  
  In the application of importance sampling to RL, is the expectation of the function $f$ equivalent to the value of the trajectories, which is represented by the trajectories $x$?
  
  The distributions $p$ represent the probability of sampling trajectories from the behavior policy and the distribution $q$ represents the probability of sampling trajectories from the target policy $q$?
  
  How would the trajectories from distribution $q$ be better than that of $p$? I know from the equation how it is better, but it is hard to understand intuitively why this could be so.
  
  **Tags:** reinforcement-learning, off-policy-methods, importance-sampling
  > **Comments:**
  > **username_1**: could you also elaborate on this sentence - 'is it correct to equate the expectation of the function  is equivalent to the value of the trajectories, which is represented by the trajectories ' please? I'm not quite sure what you mean.  
  > **username_0**: Sorry i didn't explain it that well. I wanted to know how the terms in importance sampling are being applied in the off policy evaluation RL context.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2020-05-22. Score: 4
  
  Recall that our goal is to be able to accurately estimate the true value of each state by computing a sample average over returns starting from that state:
  $$v\_{q}(s) \doteq \mathbb{E}\_{q}\left[G\_{t} | S\_{t}=s\right] \approx \frac{1}{n} \sum\_{i=1}^{n} Return\_i $$
  where $Return\_i$ is the return obtained from the $i^{th}$ trajectory.
  
  The problem is that the $\approx $ does not hold, since in off-policy learning, we got those returns by following the behavior policy, $p$, and not the target policy, $q$.
  
  To address that, we have to correct each return in the sample average by multiplying by the importance sampling ratio.
  
  $$v\_{q}(s) \doteq \mathbb{E}\_{q}\left[G\_{t} | S\_{t}=s\right] \approx \frac{1}{n} \sum\_{i=1}^{n} \rho\_i Return\_i$$
  
  where the importance sampling ratio is : $\rho=\frac{\mathbb{P}(\text { trajectory under } q)}{\mathbb{P}(\text { trajectory under } p)}$
  
  What this multiplication does is that it increases the importance of returns that were more likely to be seen under the target policy $q$ and it decreases those that were less likely. So, at the end, in expectation, it would be as if the returns were averaged following $q$.
  
  (A side note: To avoid the risks of mixing $p$ and $q$, it might be a good idea to denote/think of the **b**ehavior policy as $b$ and the target policy as $\pi$, following the convention in Sutton and Barto's RL book.)
  
  
  ---
  
  ### Answer by username_3 on 2020-11-26. Score: 2
  
  Let's fix some notation: we're collecting data from behavior policy $\pi\_0$ and we want to evaluate a policy $\pi$.
  Of course, if we had plenty of data from policy $\pi$ that would be the best way to evaluate $\pi$ as we just take the empirical average (without any importance sampling) and CLT gives us confidence intervals that shrink at $\frac{1}{\sqrt n}$ rates.
  
  However, collecting data from $\pi$ is often time-consuming and costly: you may need to productionize it at a company, and if $\pi$ were dangerous, some damage could be done during rollouts. So how can we make the best use of our data from any policies, not necessarily $\pi$, to evaluate $\pi$? This is the question of off-policy evaluation, and you're right that IS is one approach.
  
  This picture from a [great talk by Thorsten](https://www.youtube.com/watch?v=lzA5K4im2no&ab_channel=CriteoLabs) provides nice intuition on why the weighting is unbiased [![enter image description here](https://i.sstatic.net/h770z.jpg)](https://i.sstatic.net/h770z.jpg).
  
  
  ---
  
  ### Answer by username_1 on 2020-05-22. Score: 2
  
  > In the application of importance sampling to RL, is the expectation of the function $f$ equivalent to the value of the trajectories, which is represented by the trajectories $x$?
  
  I believe what you are asking here is if when using importance sampling in the off-policy RL setting that we set $f(x)$ from the general importance sampling formula to be our returns - the answer to this is yes. As always we are interested in calculating our expected returns.
  
  > How would the trajectories from the distribution $q$ be better than that
  > of $p$? I know from the equation how it is better but it is hard to
  > understand intuitively why this could be so.
  
  I think here you got your $p$ and $q$ the wrong way around as we are using samples from $p$ to approximate our policy $q$. We typically will use importance sampling to generate samples from a *different* policy to our target policy for a few reasons - one reason might be that our target policy is hard to sample from whereas sampling from our behaviour policy $p$ might be relatively easy to sample from. Another reason is that we generally want to learn an optimal policy, but this could be difficult to learn if we don't explore enough. So we can follow some other policy that will explore sufficiently and still learn about our optimal target policy through the importance sampling ratio.
  
  
  ---
  
  