Importance Sampling and its Limitations

Importance Sampling (IS) emerges as a fundamental statistical technique for evaluating a new policy $\pi_e$ using only data collected by a potentially different behavior policy $\pi_b$. The core idea is elegant: re-weight the returns observed in the offline dataset to correct for the mismatch between the policies. If a trajectory was more likely under the evaluation policy $\pi_e$ than under the behavior policy $\pi_b$, its return should be weighted more heavily, and vice versa.

The Mechanics of Importance Sampling

Imagine you have a dataset $\mathcal{D} = \{ \tau_1, \tau_2, ..., \tau_N \}$ consisting of $N$ trajectories, where each trajectory $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, ..., s_T, a_T, r_T)$ was generated by following the behavior policy $\pi_b$. Our goal is to estimate the expected return of the evaluation policy $\pi_e$, denoted as $J(\pi_e) = \mathbb{E}_{\tau \sim \pi_e} [R(\tau)]$, where $R(\tau) = \sum_{t=0}^{T} \gamma^t r_t$ is the cumulative discounted reward of trajectory $\tau$.

Importance Sampling allows us to estimate this expectation using samples from $\pi_b$ by multiplying the return of each trajectory $R(\tau_i)$ by an "importance ratio" that quantifies the relative probability of that trajectory occurring under $\pi_e$ versus $\pi_b$.

Mathematical Formulation

For a given trajectory $\tau$, the probability of observing that sequence of states and actions under a policy $\pi$ (assuming deterministic environment transitions for simplicity, though it extends to stochastic ones) is: $P(\tau | \pi) = p(s_0) \prod_{t=0}^{T} \pi(a_t | s_t) p(s_{t+1} | s_t, a_t)$ The importance ratio for the entire trajectory is the ratio of these probabilities under $\pi_e$ and $\pi_b$: $\rho_{0:T}(\tau) = \frac{P(\tau | \pi_e)}{P(\tau | \pi_b)} = \frac{p(s_0) \prod_{t=0}^{T} \pi_e(a_t | s_t) p(s_{t+1} | s_t, a_t)}{p(s_0) \prod_{t=0}^{T} \pi_b(a_t | s_t) p(s_{t+1} | s_t, a_t)} = \prod_{t=0}^{T} \frac{\pi_e(a_t | s_t)}{\pi_b(a_t | s_t)}$ Let $\rho_t = \frac{\pi_e(a_t | s_t)}{\pi_b(a_t | s_t)}$ be the per-step importance ratio. Then the full trajectory ratio is $\rho_{0:T} = \prod_{t=0}^{T} \rho_t$.

The standard (or "ordinary") Importance Sampling estimator for $J(\pi_e)$ using $N$ trajectories from $\pi_b$ is: $\hat{J}_{IS}(\pi_e) = \frac{1}{N} \sum_{i=1}^{N} \rho_{0:T}^{(i)} R(\tau_i)$ This estimator is unbiased, meaning $\mathbb{E}[\hat{J}_{IS}(\pi_e)] = J(\pi_e)$, which is theoretically appealing. However, its practical utility in offline RL is severely limited by several factors, primarily its potentially enormous variance.

The Variance Problem: The Achilles' Heel of IS

The unbiasedness of the IS estimator comes at a steep price: variance. The variance of $\hat{J}_{IS}(\pi_e)$ depends on the second moment of the weighted returns, specifically involving $\mathbb{E}_{\tau \sim \pi_b}[(\rho_{0:T}(\tau))^2 R(\tau)^2]$. The critical term here is the squared trajectory importance ratio, $(\rho_{0:T})^2$.

Consider the structure of $\rho_{0:T} = \prod_{t=0}^{T} \rho_t$. This is a product of potentially many per-step ratios.

• If $\pi_e$ and $\pi_b$ differ even moderately at several steps, the product $\rho_{0:T}$ can become extremely large or vanishingly small.
• Crucially, the variance often grows exponentially with the trajectory length $T$. Even small differences in per-step probabilities compound multiplicatively, leading to weights that can vary over many orders of magnitude.
• A few trajectories with exceptionally large importance ratios $\rho_{0:T}^{(i)}$ can dominate the sum in the estimator, making the estimate highly unstable and unreliable, especially with a finite dataset size $N$.

This exponential increase in variance with the horizon length is a major barrier to applying basic IS effectively in typical RL problems, which often involve long sequences of decisions.

As the horizon length increases, the distribution of importance weights tends to become heavily skewed, with many weights close to zero and a few extremely large weights, leading to high variance in the IS estimate. (Illustration).

Sensitivity to Behavior Policy and Lack of Support

The variance problem is exacerbated by the nature of the behavior policy $\pi_b$ and its relationship to the evaluation policy $\pi_e$.

• Small Probabilities in $\pi_b$: If the behavior policy assigns a very small probability $\pi_b(a_t | s_t)$ to an action $a_t$ that the evaluation policy $\pi_e$ takes with non-trivial probability $\pi_e(a_t | s_t)$, the corresponding per-step ratio $\rho_t$ will be very large. This single large ratio can inflate the trajectory ratio $\rho_{0:T}$ dramatically.
• Lack of Overlap (Support): The IS estimator fundamentally breaks down if there exists a state-action pair $(s, a)$ such that $\pi_e(a|s) > 0$ but $\pi_b(a|s) = 0$. If the evaluation policy could potentially take an action that was never taken (or had zero probability of being taken) by the behavior policy in that state within the dataset, the importance ratio becomes infinite ($\frac{>0}{0}$), and the expectation is undefined. This is a direct consequence of distributional shift – the offline data might simply not contain information about actions the evaluation policy would take.

Requirement of Known Behavior Policy

"A practical limitation is that standard IS requires explicit knowledge of the probabilities $\pi_b(a_t | s_t)$ for all state-action pairs encountered in the dataset. In many scenarios where offline data is collected (e.g., logs from a deployed system, human demonstrations), the exact policy that generated the data is unknown. One might try to estimate $\pi_b$ from the data (e.g., using behavior cloning), but this introduces another layer of approximation and potential error into the OPE process, potentially biasing the IS estimate."

Mitigation Attempts: WIS and PDIS

Several variants of IS have been proposed to mitigate the variance issue, although none solve it completely:

1. Weighted Importance Sampling (WIS): Instead of a simple average, WIS normalizes the weighted returns by the sum of the weights: $\hat{J}_{WIS}(\pi_e) = \frac{\sum_{i=1}^{N} \rho_{0:T}^{(i)} R(\tau_i)}{\sum_{i=1}^{N} \rho_{0:T}^{(i)}}$ WIS is a biased estimator (the expectation is not exactly $J(\pi_e)$ for finite $N$, though it's consistent), but it often exhibits significantly lower variance than ordinary IS, especially when weights vary greatly. It effectively down-weights the influence of outlier trajectories with huge ratios.

2. Per-Decision Importance Sampling (PDIS): PDIS aims to reduce variance by applying importance correction only up to the time step of interest when estimating state or state-action values. For estimating the expected return, a common form looks at discounted importance ratios: $\hat{J}_{PDIS}(\pi_e) = \frac{1}{N} \sum_{i=1}^{N} \sum_{t=0}^{T} \gamma^t \rho_{0:t}^{(i)} r_t^{(i)}$ While potentially offering variance reduction in certain settings compared to standard IS, PDIS still suffers from the compounding product of ratios.

These variants can be helpful, but they do not fundamentally eliminate the exponential variance growth associated with long horizons or significant differences between $\pi_e$ and $\pi_b$.

In summary, while Importance Sampling provides a theoretically grounded way to perform Off-Policy Evaluation, its extreme variance and sensitivity to policy mismatch and data coverage make it often unreliable for practical Offline RL. These limitations highlight the significant challenge posed by distributional shift and motivate the development of alternative OPE methods and offline learning algorithms, such as the policy constraint and value regularization techniques we will discuss next, which explicitly aim to mitigate the problems caused by evaluating actions or states poorly represented in the offline dataset.