4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – F.M.F. Jan 9 at 21:22
  • 2
    $\begingroup$ @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. $\endgroup$ – Dennis Soemers Jan 10 at 8:10
  • 2
    $\begingroup$ 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. $\endgroup$ – Dennis Soemers Jan 10 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.