How bad can importance sampling be?

How bad can importance sampling be? Importance sampling is regularly used to estimate expectations or simply to reduce variance. In RL its also used to perform off-policy learning. If the approximating distribution used is poorly chosen, importance sampling can actually increase variance. In fact it’s known that the variance of the importance weights can become unbounded. Despite this being common knowledge it’s easy to be lulled into false conclusions when using importance sampling. Here’s an incredibly simple 1-d example that shows how badly wrong things can go:

Imagine that our target distribution, $P(x)$ is a zero mean 1-dimensional gaussian with unkown variance $\sigma_p$ and that our proposal distribution is ALSO a 1-dimensional zero-mean gaussian but with the wrong variance.

setup

This setting might seem like an incredibly benign one for importance sampling - the target and approximating distributions are well matched and the dimensionality is low! However, lets consider the variance of the importance weights: $W = \frac{P(x)}{Q(x)}$ :

$E_Q(W) = 1$ $E_Q(W^2) = \int dx \left(\frac{2\pi \sigma_q^2}{2 \pi \sigma_p^2} \right)} \frac{1}{\sqrt{2\pi \sigma_q^2}} e^{ -(\frac{1}{\sigma_p^2} - \frac{1}{\sigma_q^2})x^2 - \frac{x^2}{2\sigma_q^2}$

After some manipulation this gives that:

$Var(W) = \frac{\sigma_q^2}{\sigma_p \sqrt{2\sigma_q^2 - \sigma_p^2}} - 1$

which diverges as $\sigma_q \rightarrow \frac{\sigma_p}{\sqrt{2}}$ !

However, there would be nothing to stop us performing importance sampling in this case. What happens in practice if we try to estimate the normalisation of $P(x)$ (which we know to be one) when $\sigma_q$ is small enough for the variance to diverge?

Below is the estimate for the normalisation along with it’s standard deviation for $\sigma_p=1$ and $\sigma_q$ varied between $0$ and $1$ .

mean

std

You can see that when $\sigma_q$ drops below 0.7 the estimate of the normalisation is totally wrong but the empirical standard deviation continues to be quite small even when the true variance is infinite!

In this extremely simple case, we can analytically calculate the variance and see that our importance sampling estimates are bogus. Despite this, our empirical estimate of the standard deviation might lead us to believe that our calculations are fine. This type of problem is much harder to diagnose in realistic settings and I dont really have an answer as to how to avoid this in practice.