Off-Policy Evaluation: Estimating a Policy's Value Without Ever Running It

TL;DR

Before deploying a new policy, you often need to know how good it will be — but running it live to find out can be expensive, slow, or risky, and the offline RL techniques covered in a companion article face the exact same evaluation problem once training is done: how do you know the resulting policy is actually good, without deploying it? Off-Policy Evaluation (OPE) estimates a target policy’s expected return using only data collected under a different behavior policy. Importance sampling reweights logged trajectories by how likely the target policy would have been to produce them; per-decision importance sampling reduces variance by reweighting reward-by-reward rather than whole-trajectory-by-trajectory; and doubly robust estimation combines importance sampling with a learned value model so that even if one of the two is wrong, the estimate stays unbiased. Used to safely evaluate candidate policies before deployment in recommendation, healthcare, and any domain where live A/B testing a bad policy is costly.

Evaluating a Policy You Never Ran

graph LR
    A[Logged Data Under Behavior Policy] --> B[Importance Sampling]
    A --> C[Doubly Robust: IS + Learned Value Model]
    B --> D[Estimated Value of Target Policy]
    C --> D

    style D fill:#6366f1,color:#fff

Problem Statement

You have logged data — states, actions, rewards — collected while running a known behavior policy π_b. You have a new target policy π_e you’d like to evaluate, but you cannot run it live yet, whether for cost, safety, or speed reasons. The naive approach (just average the logged rewards) is wrong, because that data reflects π_b’s choices, not π_e’s — OPE is the family of techniques for correcting for that mismatch statistically.

Importance Sampling: Reweighting by Policy Ratio

The core idea: reweight each logged trajectory by how much more (or less) likely the target policy would have been to take the same sequence of actions, compared to the behavior policy that actually generated the data.

def importance_sampling_estimate(trajectories, target_policy, behavior_policy, gamma=0.99):
    estimates = []
    for trajectory in trajectories:
        importance_weight = 1.0
        discounted_return = 0.0
        for t, (state, action, reward) in enumerate(trajectory):
            importance_weight *= target_policy.prob(action, state) / behavior_policy.prob(action, state)
            discounted_return += (gamma ** t) * reward
        estimates.append(importance_weight * discounted_return)
    return np.mean(estimates)

This estimator is unbiased — in expectation, it exactly recovers the target policy’s true value — but the importance weight is a product of per-step ratios across an entire trajectory, which can explode or vanish over long horizons, producing enormous variance that makes the estimate practically useless despite being technically unbiased.

Per-Decision Importance Sampling: Cutting Variance

Per-decision importance sampling (Precup, Sutton, Singh, 2000) notices that a reward at time t only depends on actions up to time t, not on the whole rest of the trajectory — so it only needs to be reweighted by the importance ratio accumulated up to that point, not the full-trajectory product:

def per_decision_is_estimate(trajectories, target_policy, behavior_policy, gamma=0.99):
    estimates = []
    for trajectory in trajectories:
        cumulative_weight = 1.0
        estimate = 0.0
        for t, (state, action, reward) in enumerate(trajectory):
            cumulative_weight *= target_policy.prob(action, state) / behavior_policy.prob(action, state)
            estimate += (gamma ** t) * cumulative_weight * reward   # weight only up to time t, per reward
        estimates.append(estimate)
    return np.mean(estimates)

This removes unnecessary variance contributed by importance ratios from after a given reward was received — ratios that couldn’t possibly have affected that specific reward — while remaining just as unbiased as the plain trajectory-level estimator.

Doubly Robust Estimation: Combining Importance Sampling With a Learned Model

Both estimators above rely entirely on the importance weights being accurate, which requires the behavior policy’s action probabilities to be known precisely — often not the case in practice. Doubly robust estimation (Jiang & Li, 2016; Thomas & Brunskill, 2016) combines importance sampling with a separately learned value-function model, structured so the estimate stays unbiased if either the importance weights or the value model is correct — not requiring both:

def doubly_robust_estimate(trajectories, target_policy, behavior_policy, learned_value_fn, gamma=0.99):
    estimates = []
    for trajectory in trajectories:
        model_based_estimate = learned_value_fn.estimate_return(trajectory[0].state, target_policy)
        correction = 0.0
        cumulative_weight = 1.0

        for t, (state, action, reward) in enumerate(trajectory):
            cumulative_weight *= target_policy.prob(action, state) / behavior_policy.prob(action, state)
            # Correct the model's prediction using the actual observed reward, weighted by importance ratio
            td_residual = reward + gamma * learned_value_fn.v(next_state=trajectory[t+1].state if t+1 < len(trajectory) else None) \
                          - learned_value_fn.q(state, action)
            correction += (gamma ** t) * cumulative_weight * td_residual

        estimates.append(model_based_estimate + correction)
    return np.mean(estimates)

The “doubly robust” property is the key practical payoff: if the learned value model is a poor approximation but the importance weights are accurate, the correction term fixes the model’s bias; if the importance weights are noisy or biased but the value model is good, the model-based estimate dominates and the correction term contributes little error — the estimator only fails if both components are simultaneously wrong.

Comparison Table

Applications

• Recommendation systems — evaluating a candidate ranking policy against historical logged interaction data before committing to a live A/B test.
• Healthcare treatment policy evaluation — estimating how a new treatment policy would have performed on historical patient data, where live testing on real patients raises obvious ethical concerns.
• Offline RL model selection — the offline RL techniques covered in a companion article need exactly this kind of evaluation to select among candidate trained policies without deploying each one to check.
• Safe policy deployment gating — using OPE as an automated gate that a new policy must clear (a high-confidence lower bound on estimated value) before it’s allowed into a live experiment at all.

Key Learnings

1. Off-policy evaluation and offline RL are two sides of the same underlying problem — offline RL trains a policy from fixed data, and OPE evaluates one, but both are fundamentally about extracting reliable information from data generated by a different policy than the one you actually care about.
2. Unbiasedness and usability are different properties, and plain importance sampling’s failure mode is a textbook example of the gap. An estimator can be perfectly unbiased in theory and still be practically useless due to variance that grows with trajectory length.
3. Doubly robust estimation is a genuinely elegant piece of statistics, not just an incremental variance-reduction trick. Needing only one of two independent components to be correct — rather than needing a single estimator to be right — is a materially stronger reliability guarantee than either importance sampling or pure model-based evaluation offers alone.

References

• Precup, D., Sutton, R., Singh, S. (2000). Eligibility Traces for Off-Policy Policy Evaluation. ICML.
• Jiang, N., Li, L. (2016). Doubly Robust Off-policy Value Evaluation for Reinforcement Learning.
• Thomas, P., Brunskill, E. (2016). Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning.