6
$\begingroup$

I was studying the off-policy policy improvement method. Then I encountered importance sampling. I completely understood the mathematics behind the calculation, but I am wondering what is the practical example of importance sampling.

For instance, in a video, it is said that we need to calculate the expected value of a biased dice, here $g(x)$, in terms of the expected value of fair dice, $f(x)$. Here is a screenshot of the video.

enter image description here

Why do we need that, when we have the probability distribution of the biased dice?

$\endgroup$
0

1 Answer 1

7
$\begingroup$

Importance sampling is typically used when the distribution of interest is difficult to sample from - e.g. it could be computationally expensive to draw samples from the distribution - or when the distribution is only known up to a multiplicative constant, such as in Bayesian statistics where it is intractable to calculate the marginal likelihood; that is

$$p(\theta|x) = \frac{p(x|\theta)p(\theta)}{p(x)} \propto p(x|\theta)p(\theta)$$

where $p(x)$ is our marginal likelihood that may be intractable and so we can't calculate the full posterior and so other methods must be used to generate samples from this distribution. When I say intractable, note that

$$p(x) = \int_{\Theta} p(x|\theta)p(\theta) d\theta$$

and so intractable here means that either a) the integral has no analytical solution or b) a numerical method for computing this integral may be too expensive to run.

In the instance of your die example, you are correct that you could calculate the theoretical expectation of the bias dice analytically and this would probably be a relatively simple calculation. However, to motivate why importance sampling may be be useful in this scenario, consider calculating the expectation using Monte Carlo methods. It would be much simpler to uniformly sample a random integer from 1-6 and calculate the importance sampling ratio $x \frac{g(x)}{f(x)}$ than it would be to draw samples from the bias dice, not least because most programming languages have built in methods to randomly sample integers.

As your question is tagged as reinforcement learning I will add why it is useful in the RL domain. One reason is that it may be our policy of interest is expensive to sample from, so instead we can just generate actions from some other simple policy whilst still learning about the policy of interest. Second, we could be interested in a policy that is deterministic (greedy) but still be able to explore, so we can have an off-policy distribution that explores much more frequently.

NB: it may not be clear how you can use importance sampling if the distribution is only known up to a constant so see this answer for an explanation.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .