What is the intuition behind importance sampling for off-policy value evaluation?

Question

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.

Answer 1

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 behavior policy as $b$ and the target policy as $\pi$, following the convention in Sutton and Barto's RL book.)

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

Answer 3

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 provides nice intuition on why the weighting is unbiased .