Off-Policy Evaluation in the Offline Setting

A common scenario in offline reinforcement learning involves training a new target policy $\pi_e$ using a static dataset $D = \{ (s_i, a_i, r_i, s'_i) \}_{i=1}^N$, which was collected under some behavior policy $\pi_b$. Before deploying $\pi_e$ in a system (which could be expensive, risky, or simply not feasible during development), an estimation of its expected performance is required. How much cumulative reward can an agent expect if it follows $\pi_e$? This question is addressed by Off-Policy Evaluation (OPE) in the offline setting.

Directly evaluating $\pi_e$ by running it isn't an option here. We must rely solely on the data $D$ generated by $\pi_b$. The fundamental challenge, as introduced earlier, is the potential distributional shift between $\pi_b$ and $\pi_e$. The states and actions encountered in the dataset $D$ might not accurately reflect those that would be encountered under $\pi_e$. Simple averaging of rewards from the dataset won't give an unbiased estimate of $\pi_e$'s performance unless $\pi_e$ happens to be identical to $\pi_b$.

Correcting for Distributional Shift with Importance Sampling

The most foundational technique for OPE is Importance Sampling (IS). The idea comes from a general statistical principle: we can estimate the expectation of a function under one distribution ($p$) using samples drawn from another distribution ($q$), provided we re-weight the samples appropriately. Specifically, if $x$ is sampled from $q(x)$, then:

$$\mathbb{E}_{x \sim p}[f(x)] = \mathbb{E}_{x \sim q}\left[ \frac{p(x)}{q(x)} f(x) \right]$$

The term $p(x)/q(x)$ is known as the importance weight or importance ratio.

In the context of RL, we want to estimate the expected total discounted return of the evaluation policy $\pi_e$, denoted $J(\pi_e)$. A trajectory (or episode) is a sequence $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \dots, s_{T-1}, a_{T-1}, r_{T-1})$. The probability of observing a specific trajectory $\tau$ under a policy $\pi$ is given by the product of the initial state probability $p(s_0)$ and the transition probabilities $p(s_{t+1}|s_t, a_t)$ and policy probabilities $\pi(a_t|s_t)$:

$$P(\tau | \pi) = p(s_0) \prod_{t=0}^{T-1} \pi(a_t|s_t) p(s_{t+1}|s_t, a_t)$$

Let $R(\tau) = \sum_{t=0}^{T-1} \gamma^t r_t$ be the total discounted return for trajectory $\tau$. We want to compute $J(\pi_e) = \mathbb{E}_{\tau \sim \pi_e}[R(\tau)]$. Using Importance Sampling, we can estimate this using trajectories sampled under the behavior policy $\pi_b$:

$$J(\pi_e) = \mathbb{E}_{\tau \sim \pi_b}\left[ \frac{P(\tau | \pi_e)}{P(\tau | \pi_b)} R(\tau) \right]$$

Notice that the environment dynamics $p(s_{t+1}|s_t, a_t)$ and initial state distribution $p(s_0)$ cancel out in the ratio:

$$\frac{P(\tau | \pi_e)}{P(\tau | \pi_b)} = \frac{p(s_0) \prod_{t=0}^{T-1} \pi_e(a_t|s_t) p(s_{t+1}|s_t, a_t)}{p(s_0) \prod_{t=0}^{T-1} \pi_b(a_t|s_t) p(s_{t+1}|s_t, a_t)} = \prod_{t=0}^{T-1} \frac{\pi_e(a_t|s_t)}{\pi_b(a_t|s_t)}$$

This product is the trajectory importance ratio, often denoted as $\rho_{\tau}$:

$$\rho_{\tau} = \prod_{t=0}^{T-1} \frac{\pi_e(a_t|s_t)}{\pi_b(a_t|s_t)}$$

Given a dataset $D$ containing $N$ trajectories $\{\tau_i\}_{i=1}^N$ collected using $\pi_b$, the standard Importance Sampling estimator for $J(\pi_e)$ is:

$$\hat{J}_{IS}(\pi_e) = \frac{1}{N} \sum_{i=1}^N \rho_{\tau_i} R(\tau_i)$$

This estimator is unbiased, meaning its expected value is equal to the true value $J(\pi_e)$, assuming we know $\pi_b$ exactly and $\pi_b(a_t|s_t) > 0$ whenever $\pi_e(a_t|s_t) > 0$.

The Variance Problem in Importance Sampling

While theoretically sound, the basic IS estimator often suffers from extremely high variance in practice. The trajectory importance ratio $\rho_{\tau}$ is a product over the length of the trajectory. If the policies $\pi_e$ and $\pi_b$ differ even slightly at each step, these differences multiply. For long trajectories (large $T$), the ratio $\rho_{\tau}$ can easily become astronomically large or vanishingly small.

Consider a trajectory of length $T=100$. If, at each step, the probability ratio $\pi_e(a_t|s_t) / \pi_b(a_t|s_t)$ is just $1.1$, the final trajectory ratio $\rho_{\tau}$ will be $(1.1)^{100} \approx 13,780$. If the ratio is $1.2$, then $\rho_{\tau} = (1.2)^{100} \approx 8.3 \times 10^7$. Conversely, if the ratio is $0.9$, $\rho_{\tau} = (0.9)^{100} \approx 2.6 \times 10^{-5}$.

This means the estimate $\hat{J}_{IS}(\pi_e)$ can be dominated by a tiny fraction of trajectories with enormous weights, making the estimate highly unreliable and unstable. A single dataset might yield a wildly different estimate than another dataset collected under the exact same conditions.

Distribution of Importance Sampling (IS) weights compared to a view of Weighted Importance Sampling (WIS) weights. High variance in basic IS often manifests as a long tail of very large weights, while WIS tends to produce more concentrated weights.

Another significant requirement for basic IS is knowing the behavior policy $\pi_b(a|s)$ precisely for all state-action pairs in the dataset. In many practical scenarios, the policy used to collect the data might be unknown, or only approximations might be available, adding another layer of potential error.

Practical OPE Methods: Addressing Variance

Several variants of IS have been developed to mitigate the variance issue, often at the cost of introducing some bias:

1. Per-Decision Importance Sampling (PDIS): Instead of calculating one ratio for the entire trajectory, PDIS calculates cumulative ratios step-by-step and applies them to the reward received at that step. The estimator looks like:

   $$\hat{J}_{PDIS}(\pi_e) = \frac{1}{N} \sum_{i=1}^N \sum_{t=0}^{T_i-1} \gamma^t \left( \prod_{k=0}^{t} \frac{\pi_e(a_{i,k}|s_{i,k})}{\pi_b(a_{i,k}|s_{i,k})} \right) r_{i,t}$$

   PDIS often exhibits lower variance than the standard IS estimator because the weights applied to earlier rewards don't involve products over the entire trajectory length.

2. Weighted Importance Sampling (WIS): This is perhaps the most common practical variant. Instead of a simple average, WIS uses the importance weights to normalize the estimate:

   $$\hat{J}_{WIS}(\pi_e) = \frac{\sum_{i=1}^N \rho_{\tau_i} R(\tau_i)}{\sum_{i=1}^N \rho_{\tau_i}}$$

   Alternatively, using per-decision weights:

   $$\hat{J}_{WPDIS}(\pi_e) = \sum_{i=1}^N \sum_{t=0}^{T_i-1} \frac{w_{i,t}}{\sum_{j=1}^N \sum_{k=0}^{T_j-1} w_{j,k}} \gamma^t r_{i,t} \quad \text{where} \quad w_{i,t} = \gamma^t \prod_{k=0}^{t} \frac{\pi_e(a_{i,k}|s_{i,k})}{\pi_b(a_{i,k}|s_{i,k})}$$

   (Note: Different normalization schemes exist for WPDIS). WIS estimators are biased (because the denominator is random), but they typically have drastically lower variance than their unweighted counterparts. In practice, the reduction in variance often outweighs the introduction of bias.

3. Doubly Robust (DR) Estimators: These methods combine a learned model of the environment's dynamics or value functions with importance sampling. They typically take the form:

   $$\hat{J}_{DR}(\pi_e) \approx \text{ModelEstimate} + \text{ISCorrection}$$

   The idea is that the estimator will be accurate if either the learned model is accurate or the importance weights are accurate (specifically, unbiased). This provides some robustness against errors in either component. A common form uses a learned Q-function $\hat{Q}(s,a)$ and value function $\hat{V}(s) = \mathbb{E}_{a \sim \pi_e}[\hat{Q}(s,a)]$:

   $$\hat{J}_{DR}(\pi_e) = \frac{1}{N} \sum_{i=1}^N \sum_{t=0}^{T_i-1} \gamma^t \left( \rho_{i,t} (r_{i,t} + \gamma \hat{V}(s'_{i,t})) - \rho_{i,t-1} \hat{Q}(s_{i,t}, a_{i,t}) \right) + \hat{V}(s_{i,0})$$

   where $\rho_{i,t} = \prod_{k=0}^t \frac{\pi_e(a_{i,k}|s_{i,k})}{\pi_b(a_{i,k}|s_{i,k})}$ and $\rho_{i,-1}=1$. While potentially offering lower variance and bias, DR estimators require fitting an additional model ($\hat{Q}$ or $\hat{V}$), adding complexity.

Limitations and Practical Steps

Despite these refinements, OPE in the offline setting remains challenging:

• Weight Clipping: A common heuristic to control extreme weights is to cap them at some maximum value. This directly reduces variance but introduces bias.
• Behavior Policy Estimation: If $\pi_b$ is unknown, it must be estimated from the data (e.g., using Maximum Likelihood Estimation). This introduces another source of error.
• Support Mismatch: The most fundamental limitation is data coverage. If $\pi_e$ takes actions in states that were never (or rarely) visited or taken by $\pi_b$ in the dataset, the corresponding importance weights $\pi_e(a|s)/\pi_b(a|s)$ will be huge or infinite. No amount of clever weighting can reliably estimate performance in regions where the dataset provides no information.

Off-policy evaluation techniques, particularly WIS and its variants, are valuable tools for getting an estimate of policy performance from offline data. However, their reliability is directly tied to the quality and coverage of the dataset and the similarity between the behavior and evaluation policies. The high variance and sensitivity of IS methods underscore the difficulties of learning purely offline and motivate the development of algorithms, discussed next, that explicitly constrain the learned policy or regularize value estimates to account for the limitations of the available data.