Importance Sampling in Off-Policy Reinforcement Learning

Importance sampling is a technique that solves a fundamental challenge in RL: how do we learn about one policy while collecting data from a different policy? Data collection can expensive and time-consuming, so being able to reuse the data we already have to keep training a new policy is very valuable. If we had to sample new data from a policy every time we wanted to make an update for an algorithm, it might become impractical to train anything useful.

More formally, importance sampling is a method in off-policy reinforcement learning (RL), allowing for the estimation of expectations under one distribution while using samples collected from another. Off-policy learning enables the reuse of past experiences, making learning more sample-efficient and reducing the need for on-policy data collection.

In reinforcement learning, we want to maximize the expected return which is the objective function

where $\tau$ represents trajectories sampled from the policy $\pi_{\theta}$. $R(\tau)$ is the cumulative reward for trajectory $\tau$. If we’re using the data from the old policy $\pi_{old}$, our objective becomes $\mathbb{E}_{\tau \sim \pi_{old}} [R(\tau)]$ and there is no $\theta$ in the equation and so no gradient with respect to $\theta$ and learning won’t happen.

The technique we use in importance sampling where we are still using trajectories from the old distribution but want to improve the new policy by reweighing the returns. The problem is that the actions taken under the old policy may not align with the new policy and the returns may not accurately reflect the performance of the new policy. Thus, the intuition behind reweighing the returns is to give more importance to those trajectories that are more likely under the new policy and less importance to those that are less likely. This way, we can estimate the expected return of the new policy using data collected from the old policy.

The mathematical basis for this is a change of measure where we can change the probability measure from $P$ to $Q$ using the Radon-Nikodym derivative $\frac{dP}{dQ}$. This gives us the relationship:

For the above equation to hold, $P$ and $Q$ must be absolutely continuous with respect to each other. In other words, if an event has zero probability under $Q$, it must also have zero probability under $P$. What this means is that any trajectory that could be sampled under the target policy must also be possible under the behavior policy. Furthermore, the Radon-Nikodym derivative $\frac{dP}{dQ}$ must be well-defined and finite almost everywhere. This ensures that the weighting does not lead to infinite or undefined values, which could destabilize the estimation process. What this means for RL policy is that the behavior policy must have non-zero probability of taking all actions that the target policy might take in any given state and vice versa.

In the context of RL, $P$ represents the distribution of trajectories under the target policy $\pi$, while $Q$ represents the distribution under the behavior policy $\pi_b$. The Radon-Nikodym derivative $\frac{dP}{dQ}$ corresponds to the importance sampling ratio, which adjusts for the difference between the two policies.

However, there are challenges with importance sampling.

• The major issue is high variance in the estimates. The denominator of the ratio can become very small if the behavior policy assigns low probability to actions that the target policy favors. This can lead to large importance weights, which in turn can cause high variance in the estimates of expected returns.
• Weight degeneracy is another challenge where a most samples get very low weights, effectively reducing the sample size and just a few samples dominate the estimate. So, even though we have a lot of data from the behavior policy, only a small subset of it effectively contributes to the learning process and results in not actually estimating the expected return accurately.
• Importance sampling is unbiased in theory. However with high variance, the estimates can be very noisy and unreliable in practice, making it difficult to learn a stable policy. So, we do a bias-variance tradeoff to reduce variance at the cost of introducing some bias by using different techniques like normalization of weights or clipping. However, this could lead to a biased estimate of the expected return.
• Another challenge is the exploration-exploitation tradeoff. If the behavior policy does not explore certain actions or states sufficiently, the importance sampling estimates may be biased or inaccurate. So, the new policy could get locked into suboptimal behaviors because it never gets data about better actions or states.
• Importance sampling over trajectories can lead to exponentially growing variance with the length of the trajectory. This is because the importance weights are products of per-step ratios, and small discrepancies at each step can compound over time.
• Importance sampling is an estimation tool whereas reinforcement learning is a control problem. Errors can compound over time as the policy is updated iteratively. As the policy changes, the discrepancy between the behavior and target policies can increase, leading to larger importance weights and higher variance in subsequent estimates.

Importance Sampling Basics

General Probability

Let’s start with the main objective and notations. We want to compute expectations under a distribution (target) defined by $p(x)$. We have simplified the notation from abstract $P$ to concrete $p(x)$ for clarity.

We can only sample from a different distribution $q(x)$ (behavior distribution) and not $p(x)$. As long as $p(x) > 0$ implies $q(x) > 0$, we can use importance sampling to estimate the expectation:

and the importance weight or importance sampling ratio is:

So, the fundamental idea of importance sampling is to calculate expectation of $f(x)$ under $p(x)$ using change of variables to $q(x)$ and reweighing the samples by the importance weight $w(x)$.

Applying Importance Sampling to Reinforcement Learning

To do reinforcement learning, we would have collected a dataset of experience (trajectories of states, actions, rewards) using a behavior policy $\pi_b$. However, we want to train a different target policy $\pi$. The distribution of trajectories generated by the behavior policy $\pi_b$ differs from that of the target policy $\pi$.

Let us define a trajectory $\tau$ of length $T$ as the following sequence

where $S_t$ is the state at time $t$, $A_t$ is the action taken at time $t$, and $R_{t+1}$ is the reward received after taking action $A_t$ in state $S_t$.

The return $R(\tau)$ for trajectory $\tau$ is defined as the cumulative discounted reward:

where $\gamma \in [0, 1)$ is the discount factor.

In order to train our policy $\pi$, we first consider the expected return (value function) starting from an initial state $s_0$ and following policy $\pi$:

By definition, this expectation can be written as

where $P(\tau \mid s_0, \pi)$ is the probability of trajectory $\tau$ under policy $\pi$ starting from state $s_0$.

For learning in reinforcement learning, we want an objective function $J({\pi})$ which we want to maximize. So, borrowing from our returns and value function, we can write our objective function as

with the gradient given as

which comes from the likelihood ratio trick, i.e., $\nabla P(x) = P(x) \nabla \log P(x)$ which comes from the chain rule of derivatives using $\nabla \log P(x) = \frac{\nabla P(x)}{P(x)}$.

In our case , we have data collected from a behavior policy $\pi_b$ but we want to evaluate or improve a different target policy $\pi$. The distribution of trajectories generated by the behavior policy $\pi_b$ differs from that of the target policy $\pi$. Directly using samples from $\pi_b$ to estimate expectations under $\pi$ would lead to biased estimates.

Under a policy $\pi$, the probability of a trajectory $\tau$ is given by:

where $P(s_0)$ is the initial state distribution and $P(s_{t+1} | s_t, a_t)$ is the environment’s transition probability.

Now, let us look at the ratio of probabilities of the same trajectory $\tau$ under the target policy $\pi$ and the behavior policy $\pi_b$:

The transition probabilities and initial state distribution cancel out because they are the same under both policies. Thus, the discrepancy between the two policies is captured entirely by the action probabilities and not the environment dynamics.

Thus, given a behavior policy $\pi_b$ and a target policy $\pi$, the importance sampling ratio is defined as:

where:

• $s_t$ is the state at time $t$,
• $a_t$ is the action taken,
• $\pi(a_t | s_t)$ is the probability of taking action $a_t$ under the target policy,
• $\pi_b(a_t | s_t)$ is the probability of taking the same action under the behavior policy.

and for the entire trajectory, the cumulative importance weight is:

Combining the importance sampling ratio and the expected return, we can estimate the value function under the target policy $\pi$ using samples collected from the behavior policy $\pi_b$:

This equation shows that we can compute the expected return under the target policy by reweighing the returns of trajectories sampled from the behavior policy using the importance sampling ratio.

For the objective function, we can similarly write:

and the gradient becomes:

Theorem 1 : Given a behavior policy $\pi_b$ and a target policy $\pi$, importance sampling provides an unbiased estimator for the expected return under the target policy using samples from the behavior policy, provided that $\pi_b(a | s) > 0$ whenever $\pi(a | s) > 0$ for all states $s$ and actions $a$.

Proof: The proof follows directly from the definition of importance sampling. We want to estimate:

Using importance sampling, we can rewrite this expectation using samples from the behavior policy $\pi_b$:

Thus, the importance sampling estimator is unbiased. $\qquad \qquad \qquad \qquad \square$

Theorem 2 (Variance of Importance Sampling) : Let $\pi_b$ be the behavior policy and $\pi$ be the target policy. The variance of the importance sampling estimator for the expected return under the target policy is given by:

with the support condition that $\pi_b(a | s) > 0$ whenever $\pi(a | s) > 0$ for all states $s$ and actions $a$ and where $W(\tau)$ is the importance sampling ratio for trajectory $\tau$ given by:

Moreover, if $\pi \neq \pi_b$, then there exists finite-horizon MDPs with bounded rewards for which the variance grows exponentially with the trajectory length $T$.

Furthermore, if there exists $\epsilon > 0$ such that for every reachable state $s$, the per-step importance weight has second moment bounded below:

then the variance of the importance sampling estimator grows at least exponentially with the trajectory length $T$.

Proof: The variance of a random variable $X$ is defined as $\text{Var}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2$. Applying this definition to the importance sampling estimator $W(\tau) R(\tau)$, we have:

Now, let us construct a simple MDP to show that the variance can grow exponentially with the trajectory length $T$ when $\pi \neq \pi_b$. Let us consider a single state MDP bandit problem where there is only one state and two actions $a$ and $b$.

It has the following properties:

• Reward is always 1 per step and so, $R(\tau) = T$ for any trajectory $\tau$ of length $T$.
• Behaviour policy $\pi_b$ is uniformly random, i.e., $\pi_b(a) = \pi_b(b) = 0.5$.
• Target policy $\pi$ is deterministic, i.e., $\pi(a) = 1$

The support condition is satisfied since $\pi_b(a) > 0$ when $\pi_b(b) > 0$.

In this case, the importance sampling ratio for a trajectory $\tau$ of length $T$ is:

Next, let us calculate the mean:

The second moment is:

Thus, the variance is:

which grows exponentially with the trajectory length $T$.

Now, to prove the last part of the theorem, we need to show that if there exists $\epsilon > 0$ such that for every reachable state $s$, the per-step importance weight has second moment bounded below by $1 + \epsilon$, then the variance of the importance sampling estimator grows at least exponentially with the trajectory length $T$.

To analyze the growth of variance with trajectory length $T$, let us focus at the term $\mathbb{E}_{\tau \sim P(\cdot | s_0, \pi_b)} [ \left( W(\tau) R(\tau) \right)^2 ]$.

The second term $\left( \mathbb{E}_{\tau \sim P(\cdot | s_0, \pi_b)} \left[ W(\tau) R(\tau) \right] \right)^2 = v_{\pi}^{(T)}(s_0)^2$ is the squared expected return. Under bounded rewards, this term is finite and so bounded. Let $R_{max}$ be the maximum possible return, then

and so,

which means that the variance is upper bounded by a term that grows quadratically with $T$ and not exponentially.

Now, for the first term, we have

and from the definition of the importance sampling ratio

we have

For a single time step, let’s compute the expected value of the squared importance weight:

with equality if and only if $\pi(a_t | s_t) = \pi_b(a_t | s_t)$ for all actions $a_t$.

Note that $\sum_a \frac{\pi(a | s)^2}{\pi_b(a | s)} \geq \left( \sum_a \pi(a | s) \right)^2$ comes from Jensen’s inequality applied to the convex function $f(x) = \frac{1}{x}$, which states that for any set of non-negative weights $w_i$ and corresponding values $x_i$, we have:

or in terms of expectations, if $X$ is a random variable and $f = \frac{1}{x}$ is convex, then:

In our case, we can set $w_i = \pi(a_i | s)$ and $x_i = \frac{\pi_b(a_i | s)}{\pi(a_i | s)}$. Then, we have:

and

And, thus,

Now, considering the entire trajectory, let $p = \min_{s} \mathbb{E}_{a \sim \pi_b(\cdot|s)}\left[ \left(\frac{\pi(a|s)}{\pi_b(a|s)}\right)^2 \right]$. By the hypothesis of the theorem, $p \geq 1 + \epsilon > 1$. We want to show that $\mathbb{E}_{\tau \sim P(\cdot | s_0, \pi_b)} [ W(\tau)^2 ] \geq p^T$.

In a general MDP, the per-step weights $w_0, \ldots, w_{T-1}$ are not independent across time steps since the state $s_t$ depends on all previous actions. We therefore cannot factor the expectation directly. Instead, we apply the tower property (law of total expectation), conditioning on the state $s_{T-1}$ at the last step and peeling off one step at a time:

since $\mathbb{E}[w_{T-1}^2 \mid s_{T-1}] \geq p$ for every reachable state $s_{T-1}$. Applying this argument inductively over all $T$ steps gives:

To close the proof, we connect this to the variance. The second term $v_\pi(s_0)^2$ is bounded independently of $T$ since rewards are bounded. For the first term, since rewards are bounded away from zero ($R(\tau) \geq r_{\min} > 0$ for every trajectory), we have $W(\tau)^2 R(\tau)^2 \geq r_{\min}^2 W(\tau)^2$ pointwise, and therefore:

Thus:

which grows at least exponentially with $T$. $\qquad \qquad \qquad \square$

Weighted Importance Sampling (WIS)

The estimator above uses ordinary importance sampling (OIS):

where $W_i = W(\tau_i)$ and $R_i = R(\tau_i)$ for trajectories sampled from $\pi_b$ and $n$ is the number of trajectories.

Weighted importance sampling keeps the same trajectory ratios, but normalizes by the sum of weights:

Equivalently, with normalized weights $\tilde{W}_i = \frac{W_i}{\sum_{j=1}^{n} W_j}$, we can write

so the estimate is a weighted average of returns whose weights sum to $1$.

This directly addresses the variance problems discussed above. In OIS, a few trajectories with very large $W_i$ can dominate the estimate. In WIS, those trajectories still get large relative influence, but the global normalization prevents the overall scale from exploding as easily.

The tradeoff matches the earlier bias-variance discussion:

• OIS is unbiased under the support condition $\pi_b(a \mid s) > 0$ whenever $\pi(a \mid s) > 0$, but can have very high variance.
• WIS usually has lower variance, but is biased for finite $n$ because of the random denominator $\sum_i W_i$.

Suppose in OIS, one of the samples has an extremely large weight $W_k$ due to a rare trajectory that is much more likely under $\pi$ than $\pi_b$. This single sample can dominate the sum $\sum_i W_i R_i$, leading to an estimate that is highly sensitive to that one trajectory. In contrast, in WIS, while $W_k$ may still be large, the normalization by $\sum_i W_i$ ensures that the overall estimate does not become excessively large due to a single outlier. The estimate could be dominated by that trajectory, but it won’t blow up the estimate to an extreme value. This makes WIS more stable and less sensitive to extreme weights, thus reducing variance.

As $n \to \infty$, $\hat{v}_{\text{WIS}}(s_0)$ is consistent and converges to $v_\pi(s_0)$ under standard regularity conditions. In practice, WIS is often preferred when stability is more important than exact finite-sample unbiasedness.

Theorem 3 (Bias of Weighted Importance Sampling) : For a fixed sample size $N$, the self-normalized importance sampling estimator $\hat{v}_{\text{WIS}}(s_0)$ is biased for estimating $v_\pi(s_0)$, i.e., $\mathbb{E}[\hat{v}_{\text{WIS}}(s_0)] \neq v_\pi(s_0)$ in general. However, as $N \to \infty$, $\hat{v}_{\text{WIS}}(s_0)$ is consistent and converges to $v_\pi(s_0)$ under standard regularity conditions.

Proof: Write the WIS estimator as a ratio of sample averages:

To prove finite-sample bias formally, it is enough to give one counterexample where

for every fixed finite $N$.

Consider a one-step bandit MDP with two actions $a,b$ and rewards

Let the behavior and target policies be

Then

For $i=1,\ldots,N$, sample $A_i \sim \pi_b$ i.i.d. and define

Let

Then

so

Now

so $f$ is strictly concave on $[0,N]$. Since $K$ is non-degenerate for any finite $N \ge 1$, strict Jensen gives

Using $\mathbb{E}[K] = N/2$, we get

Hence, for this MDP and every fixed finite $N$, WIS is biased. Therefore, WIS is biased in general at finite sample size.

For consistency, since the trajectories $\tau_1, \ldots, \tau_N$ are drawn i.i.d. from $\pi_b$, the Strong Law of Large Numbers gives, almost surely as $N \to \infty$:

under the regularity conditions $\mathbb{E}_{\pi_b}[|WR|] < \infty$ and $\mathbb{E}_{\pi_b}[W] < \infty$. Since $\bar{B} \to 1 \neq 0$ and division is continuous, the continuous mapping theorem gives:

Thus $\hat{v}_{\text{WIS}}(s_0)$ is consistent. $\qquad \qquad \qquad \square$