Importance Sampling for Off-Policy Methods

In Monte Carlo Prediction, we estimate $v_\pi(s)$ by averaging observed returns from episodes generated by following $\pi$ itself. In the off-policy setting, episodes are instead generated by a behavior policy $b \neq \pi$, and we want to estimate $v_\pi$ or $q_\pi$, the value functions of a different target policy $\pi$. This is exactly the scenario in On-Policy vs Off-Policy Learning: the policy generating data differs from the policy being evaluated or improved. The key mathematical fact is that returns generated under $b$ are samples from the wrong distribution. If we simply averaged them, we would be estimating $v_b$, not $v_\pi$. Importance sampling is the general statistical technique for correcting exactly this kind of distribution mismatch: given samples from distribution $b$, reweight them to estimate an expectation under distribution $\pi$. Concretely, consider a trajectory starting at state $S_t$ and following the policy for $T-t$ steps until termination:

The probability of this trajectory under a policy $\mu$ (either $\pi$ or $b$), given the shared environment dynamics $p$, is

The environment transition probabilities $p(S_{k+1}\mid S_k, A_k)$ are identical for both policies, since the environment does not change — only the policy does. This is crucial: it means the ratio of trajectory probabilities under $\pi$ versus $b$ depends only on the policies, not on unknown environment dynamics:

This quantity $\rho_{t:T-1}$ is the importance-sampling ratio. It is computable purely from the two policies' action probabilities along the observed trajectory, which is exactly the information available to the learner. The reweighting identity then follows directly from the change-of-measure formula for expectations:

So if we take episodes generated under $b$, multiply each return $G_t$ by its corresponding ratio $\rho_{t:T-1}$, and average, the result is an unbiased estimator of $v_\pi(s)$. A necessary condition underlies all of this: coverage. We require $b(a\mid s) > 0$ whenever $\pi(a\mid s) > 0$. If $\pi$ ever assigns positive probability to an action that $b$ never takes in some state, that portion of $\pi$'s behavior is simply never observed in the data, and no reweighting scheme can recover it — the ratio would involve a division by zero.

There are two standard estimators built on the ratio $\rho_{t:T-1}$, applied to episodes collected from $b$. Suppose we have collected several episodes and, for a given state $s$, we let $\mathcal{T}(s)$ be the set of all time steps at which $s$ was visited (using every-visit MC for simplicity), with corresponding returns $G_t$ and ratios $\rho_{t:T(t)-1}$, where $T(t)$ is the termination time of that episode.

Ordinary importance sampling (OIS) simply averages the reweighted returns:

This is an unbiased estimate of $v_\pi(s)$ by the identity above, but its variance can be extremely large or even unbounded, since $\rho$ is a product of ratios that can blow up.

Weighted importance sampling (WIS) instead normalizes by the sum of ratios rather than the count:

WIS is biased for finite samples (the bias vanishes asymptotically as more data arrives) but has dramatically lower variance in practice, because the denominator adapts to how much "evidence weight" the sample carries. If a trajectory has ratio 0, it is naturally down-weighted rather than allowed to contribute an unbounded value divided by a fixed count. Both estimators can be computed incrementally, one episode at a time, without storing all past returns — critical for streaming and control settings. For WIS applied to action values, the classic incremental update (used in Sutton & Barto-style off-policy MC control) processes an episode backward from termination, since ratios and returns naturally compose backward in time. ```pseudocode

# Off-policy every-visit Monte Carlo prediction with Weighted Importance Sampling

# Estimates Q ≈ q_pi using episodes generated by behavior policy b (with coverage of pi) Initialize: Q(s, a) ← arbitrary, for all s, a C(s, a) ← 0 # cumulative sum of importance weights loop forever (for each episode, generated by following b): Generate an episode: S_0, A_0, R_1, S_1, A_1, R_2, ..., S_{T-1}, A_{T-1}, R_T G ← 0 W ← 1 # importance-sampling ratio, accumulated backward for t = T-1, T-2, ..., 0: G ← γ G + R_{t+1} C(S_t, A_t) ← C(S_t, A_t) + W Q(S_t, A_t) ← Q(S_t, A_t) + (W / C(S_t, A_t)) (G - Q(S_t, A_t)) W ← W * ( pi(A_t | S_t) / b(A_t | S_t) ) if W == 0: break # ratio for all earlier steps in this episode is 0 ``` The `break` on `W == 0` is not merely an optimization: once $\pi(A_t\mid S_t) = 0$ for some visited action, the ratio for every earlier time step in that episode is exactly zero (since $\rho_{t:T-1}$ is a product including that factor), so there is nothing left to accumulate — this is why the loop can safely stop early. For ordinary importance sampling, the analogous incremental update tracks a plain running count and a running sum, since the estimator normalizes by the number of samples rather than the accumulated weight: ```pseudocode

# Off-policy every-visit Monte Carlo prediction with Ordinary Importance Sampling Initialize: Q(s, a) ← arbitrary N(s, a) ← 0 # visit count SumRG(s, a) ← 0 # running sum of weighted returns loop forever (for each episode, generated by following b): Generate an episode as above G ← 0 W ← 1 for t = T-1, T-2, ..., 0: G ← γ G + R_{t+1} N(S_t, A_t) ← N(S_t, A_t) + 1 SumRG(S_t, A_t) ← SumRG(S_t, A_t) + W G Q(S_t, A_t) ← SumRG(S_t, A_t) / N(S_t, A_t) W ← W * ( pi(A_t | S_t) / b(A_t | S_t) ) if W == 0: break ``` The diagram below traces how a single episode's ratio accumulates backward and feeds the incremental WIS update.

Time complexity. Each episode of length $T$ is processed once, backward, in $O(T)$ time: every step performs a constant number of arithmetic operations (update $G$, update $C$ or $N$, update $Q$, update $W$). Over $N$ episodes with average length $\bar T$, total time is $O(N\bar T)$, matching ordinary on-policy every-visit Monte Carlo exactly — importance sampling adds no asymptotic overhead, only a constant number of extra multiplications per step.

Space complexity. The algorithm needs $O(|\mathcal S||\mathcal A|)$ space for the tables $Q$, and $C$ (or $N$, $SumRG$), independent of the number of episodes processed, because updates are incremental rather than requiring storage of every past return. This is the same space bound as on-policy tabular Monte Carlo.

Correctness of OIS (unbiasedness). The identity

was derived directly from the environment-independent cancellation of transition probabilities in the trajectory-probability ratio. Since each sampled $(\rho, G)$ pair is drawn i.i.d. (across independent episodes) from the distribution induced by $b$, the sample average

is an unbiased estimator of this expectation by the law of large numbers / linearity of expectation — this is exactly what makes OIS unbiased for every finite $n$, not just asymptotically.

Why OIS has high (sometimes infinite) variance. The ratio $\rho_{t:T-1}$ is a product of $T-t$ independent factors $\pi(A_k|S_k)/b(A_k|S_k)$. Products of independent random ratios have variance that grows, in the worst case multiplicatively, with the number of factors. A single episode where $b$ happened to choose a low-probability-under-$b$ but relevant-under-$\pi$ action sequence can produce a ratio orders of magnitude larger than typical, dominating the average. In degenerate cases (e.g., a policy with an action of probability $\pi(a|s)/b(a|s)$ unbounded as $b(a|s)\to 0$), the variance of $\rho G$ can be literally infinite even though its mean is finite — a textbook example of a heavy-tailed estimator.

Correctness of WIS (consistency, with bias). WIS is a ratio estimator:

By the strong law of large numbers, both numerator and denominator (each divided by $n$) converge almost surely to $\mathbb{E}_b[\rho G]= v_\pi(s)\cdot \mathbb E_b[\rho]$ and $\mathbb{E}_b[\rho] = 1$ respectively (the latter because $\rho$ is itself a likelihood ratio, whose expectation under $b$ is always exactly 1). By the continuous mapping theorem, the ratio converges to $v_\pi(s)/1 = v_\pi(s)$, so WIS is a consistent estimator: its bias vanishes as $n \to \infty$, even though for any finite $n$ it is generally biased (since $\mathbb E[X/Y] \neq \mathbb E[X]/\mathbb E[Y]$ in general). In exchange, WIS's variance is bounded even when individual ratios are large, because the same large ratio that inflates the numerator also inflates the denominator, canceling out much of the fluctuation. This bias–variance trade is the central practical reason WIS is preferred in almost all applied off-policy Monte Carlo work.

Coverage as a correctness precondition. The derivation of $\rho_{t:T-1}$ implicitly assumes $b(A_k|S_k) > 0$ for every action actually taken; if in addition $\pi(a|s) > 0 \Rightarrow b(a|s) > 0$ for all $s,a$ (coverage), then every trajectory that $\pi$ could generate has nonzero probability under $b$, so no part of $\mathbb E_\pi[G_t]$ is systematically missing from the support of the sampling distribution. Without coverage, importance sampling is not merely noisy — it is definitionally unable to estimate the missing mass.

Consider a trivial one-state, two-action bandit-like episode to make the arithmetic fully transparent (state $S_0$ only, then terminate). Let $\gamma = 1$. Behavior policy $b$: $b(a_1) = 0.8,\ b(a_2) = 0.2$. Target policy $\pi$: $\pi(a_1) = 0.5,\ \pi(a_2) = 0.5$. Suppose the reward for taking $a_1$ is always $R = 2$, and for $a_2$ is always $R = 8$. We collect 4 episodes under $b$:

The true value under $\pi$ is $v_\pi = 0.5(2) + 0.5(8) = 5.0$.

OIS estimate:

WIS estimate:

Both are in the right neighborhood of the true value 5.0 with only 4 samples, but notice the sensitivity: episode 4 (the rare $a_2$ action) carries a ratio of 2.5, five times heavier than the $a_1$ episodes' 0.625. If by chance $b$ had produced two $a_2$ episodes instead of one (plausible with 20% probability per draw), OIS would jump dramatically because it still divides by a fixed count of episodes, while WIS's denominator also grows, partially absorbing the shock. This is the variance-damping mechanism made concrete: WIS self-normalizes against the very quantity that would otherwise make an unlucky sample dominate. Running the incremental WIS pseudocode step by step for this data (processing episodes 1–4 in order, updating $C$ and $Q$ after each):

The incremental computation lands exactly on the batch WIS value $5.4286$, confirming the update rule is algebraically equivalent to recomputing the ratio estimator from scratch after each episode — this equivalence is exactly why the incremental form is correct and not just a heuristic shortcut.

Importance sampling as a general statistical technique predates reinforcement learning by decades, originating in Monte Carlo integration and rare-event simulation, where researchers needed to estimate expectations under distributions that were expensive or impossible to sample directly.

Off-policy evaluation via importance sampling underlies offline reinforcement learning, where a company must estimate how a candidate policy would perform using only historical logs — critical in recommendation systems, ad placement, and healthcare treatment policy evaluation, where deploying an untested policy directly is costly or unethical. Contextual bandit platforms at large-scale internet companies (search ranking, ad auctions, content recommendation) routinely use importance-weighted estimators to A/B test new ranking policies against logged data before committing to a live rollout. In robotics and autonomous systems, importance sampling enables safe policy evaluation: engineers can estimate how an updated control policy would behave using data collected under a validated, safety-certified policy, without ever running the new policy on physical hardware. In classic reinforcement learning algorithms, importance-sampling ratios appear inside off-policy variants of TD(λ) and inside algorithms like Retrace(λ) and V-trace (used in large-scale distributed actor-learner architectures such as IMPALA), where clipped or truncated importance weights control variance while preserving asymptotic correctness. The tension this article surfaces — unbiased-but-high-variance versus consistent-but-biased — is precisely the tension that motivates truncated and clipped importance-sampling variants used throughout modern deep off-policy RL, and it is one strand of the broader instability phenomenon studied under The Deadly Triad, where off-policy learning, function approximation, and bootstrapping combine to threaten convergence guarantees.

Ask the tutor: How does the importance-sampling ratio change when using n-step returns instead of full Monte Carlo returns, and why does that matter for variance?