Importance Sampling: Ordinary vs Weighted

Why Does This Exist?

Off-policy evaluation enables a reinforcement learning agent to estimate the value of a target policy $\pi$ using trajectory rollouts collected under a distinct, exploratory behavior policy $b$. Because state-action paths are sampled according to $b$ rather than $\pi$, their observed returns cannot simply be averaged together without adjustment; doing so would estimate $v_b$ rather than $v_\pi$.

To correct for this distributional mismatch, importance sampling reweights each trajectory's return by the likelihood ratio of the action sequence under $\pi$ versus $b$:

The mathematical dilemma arises in how to aggregate these reweighted returns:

1. Ordinary Importance Sampling (OIS) takes the simple arithmetic average of the weighted returns across $n$ episodes, dividing by $n$. While OIS is strictly unbiased ($\mathbb{E}[V^{\text{ord}}] = v_\pi$), its variance grows exponentially with the episode horizon $T-t$. In multi-step tasks, the variance of $\rho$ can be unbounded or even infinite. A single rare trajectory with a massive ratio $\rho_i$ can inflate the sample mean by thousands of units, destroying estimation accuracy.
2. Weighted Importance Sampling (WIS) divides the sum of weighted returns by the sum of importance ratios $\sum \rho_i$ rather than the raw episode count $n$. While WIS is biased for small sample sizes, this normalization converts the estimate into a convex combination of returns, guaranteeing that the estimate stays strictly bounded within the physical range of observed returns and slashing variance by orders of magnitude.

Understanding this bias-variance tradeoff is critical: in off-policy Monte Carlo learning, chasing zero bias with Ordinary IS frequently leads to non-converging algorithms, making Weighted IS the de facto standard in practice.

Think of It Like This

How It Actually Works

The Mathematical Formulation and Variance Divergence

Consider estimating the state-value function $v_\pi(s)$ of a target policy $\pi$ from $n$ independent episodes generated by behavior policy $b$, satisfying the coverage assumption: $\pi(a \mid s) > 0 \implies b(a \mid s) > 0$.

For each episode $i \in \{1, \dots, n\}$ visiting state $s$ at time step $t$, let $G_i$ represent the subsequent return, and let $\rho_i$ denote the full trajectory importance sampling ratio:

1. Ordinary Importance Sampling (OIS)

Ordinary importance sampling averages the reweighted returns directly across the $n$ trajectories:

Expectation (Unbiased)

Using the tower property and change of measure:

The bias of Ordinary Importance Sampling is strictly zero for any sample size $n \ge 1$.

Variance (Potentially Infinite)

The variance is:

Because $\rho_i$ is a product of per-step ratios $\frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}$, the second moment $\mathbb{E}_b[\rho_i^2]$ grows exponentially with trajectory length $T-t$. If there exists any transition where $\frac{\pi(a \mid s)^2}{b(a \mid s)} > 1$, the variance of $\rho_i$ diverges to infinity as $T \to \infty$. When variance is infinite, sample averages do not converge reliably under the Central Limit Theorem.

2. Weighted Importance Sampling (WIS)

Weighted importance sampling normalizes by the empirical sum of importance sampling ratios:

(If $\sum_{i=1}^n \rho_i = 0$, $V^{\text{wis}}(s)$ is defined to be $0$).

Bias (Non-Zero for Finite $n$)

When $n = 1$ and $\rho_1 > 0$:

Taking the expectation with respect to the sampling policy $b$:

With a single sample, the expectation of WIS equals the value of the behavior policy, not the target policy! Thus, WIS is biased for finite sample sizes.

Consistency (Asymptotic Convergence)

By the Strong Law of Large Numbers, as the sample count $n \to \infty$:

Therefore, the ratio of the empirical sums converges almost surely to the true value:

WIS is statistically consistent: its bias asymptotically vanishes to zero as more trajectories accumulate.

Bounded Range and Variance Reduction

Let $w_i = \frac{\rho_i}{\sum_{k=1}^n \rho_k}$. Since $\rho_i \ge 0$ and $\sum_{i=1}^n w_i = 1$, $V^{\text{wis}}(s) = \sum_{i=1}^n w_i G_i$ is a strict convex combination. Consequently:

The estimate is strictly bounded within the physical range of observed returns. Even if an extreme trajectory produces $\rho_i = 10^5$, its normalized weight $w_i \approx 1.0$, pulling the estimate toward $G_i \in [G_{\min}, G_{\max}]$ rather than blowing up to infinity.

Worked numerical example

Let an agent evaluate state $S_0$ under target policy $\pi$ using $n = 3$ off-policy trajectories collected by behavior policy $b$. Suppose true target policy value is $v_\pi(S_0) = 1.0$, and rewards are bounded such that all observed returns $G_i \in [0.0, 1.0]$.

We observe 3 trajectories:

• Trajectory 1: Return $G_1 = 1.0$, importance ratio $\rho_1 = 0.10$ (frequent under $b$, rare under $\pi$).
• Trajectory 2: Return $G_2 = 0.0$, importance ratio $\rho_2 = 0.40$ (moderate frequency under both).
• Trajectory 3: Return $G_3 = 1.0$, importance ratio $\rho_3 = 14.50$ (rare under $b$, very likely under $\pi$).

Step 1: Compute Individual Weighted Returns

Step 2: Compute Ordinary Importance Sampling (OIS)

Divide by the fixed trajectory count $n = 3$:

Notice the pathology: every individual return was at most $1.0$, yet Ordinary IS estimates $V(S_0) \approx 4.867$—a value nearly five times larger than the physical environment maximum!

Step 3: Compute Weighted Importance Sampling (WIS)

First compute the sum of weights:

Divide by the sum of weights:

The WIS estimate $0.973$ sits comfortably within $[0.0, 1.0]$ and closely matches the true target value $v_\pi(S_0) = 1.0$.

Step 4: Examine the Finite-Sample Edge Case ($n = 1$)

If we had stopped after observing only Trajectory 1 ($G_1 = 1.0, \rho_1 = 0.10$):

• OIS: $V^{\text{ord}} = \frac{0.10 \times 1.0}{1} = 0.10$ (scales down return based on low $\rho_1$).
• WIS: $V^{\text{wis}} = \frac{0.10 \times 1.0}{0.10} = 1.00 = G_1$ (matches behavior policy return, revealing its finite-sample bias).

Code

1import random2from typing import List, Tuple3
4def compare_ordinary_vs_weighted_is(5    n_trials: int = 1000,6    trajectories_per_trial: int = 25,7    horizon: int = 3,8    p_target: float = 0.85,9    p_behavior: float = 0.50,10    seed: int = 42,11) -> Tuple[float, float, float, float, float]:12    """13    Simulates off-policy evaluation comparing Ordinary and Weighted IS over repeated trials.14    15    Environment:16        At each step, action a=1 or a=0 is selected.17        Return G = 1.0 if all actions in the horizon equal 1, otherwise G = 0.0.18    19    Returns:20        (true_value, ois_mean, ois_variance, wis_mean, wis_variance)21    """22    random.seed(seed)23    24    # Ground truth expected return under target policy:25    # Trajectory gives reward 1.0 iff action 1 is selected at all time steps26    true_value: float = p_target ** horizon  # 0.85^3 = 0.61412527    28    ois_estimates: List[float] = []29    wis_estimates: List[float] = []30    31    for _ in range(n_trials):32        ratios: List[float] = []33        returns: List[float] = []34        35        for _ in range(trajectories_per_trial):36            # Sample trajectory under behavior policy b37            actions = [1 if random.random() < p_behavior else 0 for _ in range(horizon)]38            39            # Compute trajectory importance ratio: prod(pi(a) / b(a))40            rho = 1.041            for a in actions:42                p_pi = p_target if a == 1 else (1.0 - p_target)43                p_b = p_behavior if a == 1 else (1.0 - p_behavior)44                rho *= (p_pi / p_b)45                46            ret = 1.0 if all(a == 1 for a in actions) else 0.047            ratios.append(rho)48            returns.append(ret)49            50        # Ordinary Importance Sampling: arithmetic mean of rho_i * G_i51        ois_estimate = sum(r * g for r, g in zip(ratios, returns)) / len(ratios)52        ois_estimates.append(ois_estimate)53        54        # Weighted Importance Sampling: self-normalized by sum(rho_i)55        sum_rho = sum(ratios)56        wis_estimate = sum(r * g for r, g in zip(ratios, returns)) / sum_rho if sum_rho > 0 else 0.057        wis_estimates.append(wis_estimate)58        59    mean_ois = sum(ois_estimates) / n_trials60    var_ois = sum((x - mean_ois) ** 2 for x in ois_estimates) / n_trials61    62    mean_wis = sum(wis_estimates) / n_trials63    var_wis = sum((x - mean_wis) ** 2 for x in wis_estimates) / n_trials64    65    return true_value, mean_ois, var_ois, mean_wis, var_wis66
67# Execute 1,000 trial Monte Carlo simulation68true_v, m_ois, v_ois, m_wis, v_wis = compare_ordinary_vs_weighted_is()69
70print(f"Ground Truth V^pi:     {true_v:.4f}")71# -> Ground Truth V^pi:     0.614172
73print(f"Ordinary IS Mean:      {m_ois:.4f} (Variance: {v_ois:.4f})")74# -> Ordinary IS Mean:      0.6110 (Variance: 0.1117)75
76print(f"Weighted IS Mean:      {m_wis:.4f} (Variance: {v_wis:.4f})")77# -> Weighted IS Mean:      0.5640 (Variance: 0.0362)

Watch Out For

The Quick Version

• Ordinary Importance Sampling computes $V(s) = \frac{1}{n} \sum \rho_i G_i$, which is strictly unbiased but suffers from massive or infinite variance due to unbounded trajectory likelihood products.
• Weighted Importance Sampling computes $V(s) = \frac{\sum \rho_i G_i}{\sum \rho_i}$, normalizing by total ratio weights to form a convex combination strictly bounded within $[\min G_i, \max G_i]$.
• Bias-Variance Tradeoff: WIS is biased for finite samples (collapsing to the behavior policy return $v_b$ when $n=1$), but it is statistically consistent and converges to $v_\pi$ as $n \to \infty$.
• Practical Standard: Because the slight initial bias of WIS vanishes quickly while cutting variance by orders of magnitude, Weighted IS is universally preferred over Ordinary IS in production reinforcement learning.

What to Read Next

• Off-Policy Importance Sampling
• Monte Carlo Control
• Q-Learning