What happens when the probability of either one of the policies is 0 in Importance Sampling?

Question

I have a general question about the methods that use importance sampling in RL. What happens when the probability of either one of the policies is 0?

Answer 1

Background: Importance sampling is used in many off-policy RL algorithms when the data is generated with one policy, yet it is being used to update another policy. The policy generating the data is usually called the behavior policy and the policy being updated is the target policy. Since the distribution of data that is generated by the behavior policy is not necessarily the distribution of data that would be generated by the target policy, using the data from the behavior policy might lead to inaccurate estimates when updating the target policy. To mitigate this issue, it is common to introduce the importance sampling ratio $$\rho_{t:T-1}\ \dot{=}\ \prod_{k=t}^{T-1} \frac{\pi(A_k|S_k)}{b(A_k|S_k)},$$ where $\pi$ is the target policy, $b$ is the behavior policy, $t$ is the current time step, and $T$ is the terminal time step. For further questions about this derivation and how the importance sampling ratio can be used to update the target policy, see the discussion near equation 5.3 in Sutton & Barto.

(Case 1) Target Policy is 0: In the case where one of the terms $\pi(A_i|S_i)$ is $0$ in the numerator of the above importance sampling ratio, then the entire product is $0$. Intuitively, this sample should have minimal influence in updating the target policy since it has zero probability of being generated by the target policy. As an example, in weighted importance sampling (see equation 5.6), this data sample will have no effect on the estimate.

(Case 2) Behavior Policy is 0: In the case where one of the terms $b(A_i|S_i)$ is $0$, the above product would be undefined. Intuitively, if the behavior policy was used to generate the data, then the data must have a nonzero chance of being generated by the behavior policy in the first place; otherwise, we reach a contradiction that results in the undefined product. See Section 5.7 of the same reference for a discussion regarding the design of useful behavior policies to mitigate this and other issues.

Answer 2

Very simply, one of the requirements of off-policy RL to converge, is that the behavioral policy $b$ has at least the same support of the target policy $\pi$, thus: $$ \forall s \in S \forall a \in A \,\,\,\,\,\,\,s.t\,\,\,\,\, \pi(a|s)>0\Rightarrow b(a|s)>0 $$

Thus, you must have a policy that would do at least everything that your knew policy would do

In the case $\pi(a|s) = 0$, then you just don't learn anything