# How can the importance-sampling ratio be different than zero?

In the book "Reinforcement Learning: An Introduction" (2018) Sutton and Barto define at page 102 the importance-sampling-ration 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 behaviour policy $$b$$.

One page before however 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 formular give something else than zero, except for the case where policy $$b$$ takes a path that $$\pi$$ would have taken as well? Because if any selected action of $$b$$ is different from $$\pi$$'s choice than the whole numerator is zero and thus the whole result.

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$$).

• 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. – F.M.F. Jan 9 at 21:22
• @F.M.F. Oh wow you're right, it's not... Q-learning seems so much simpler to explain and conceptually understand though, I'd always start with that first. – Dennis Soemers Jan 10 at 8:10
• Ah yes, right. @F.M.F. see the edit to my answer please, an important correction and an extra paragraph of another advantage that importance sampling may have due to that correction. – Dennis Soemers Jan 10 at 8:41