Counterfactual Policy Evaluation

CPE answers the fundamental question: 'What would have happened if we used a different policy?' using only logged data from a previous behavior policy. This avoids costly and potentially dangerous online A/B testing. The core mechanism applies importance sampling or doubly robust estimation to reweight historical trajectories, correcting for the distribution shift between the logging policy and the target evaluation policy.

IPS is the foundational statistical technique for CPE. It reweights each observed trajectory by the ratio of the target policy's action probability to the behavior policy's action probability. Key properties:

• Unbiased when the behavior policy has full support
• High variance when the ratio is large, requiring clipping or self-normalization
• Forms the basis for advanced estimators like Doubly Robust and Weighted IPS

The Doubly Robust (DR) estimator combines IPS with a direct method reward model. It remains consistent if either the propensity model or the reward model is correctly specified, providing a crucial safety net. The DR formula:

• Starts with the direct method estimate of the value
• Adds an IPS correction term on the residuals
• Achieves lower variance than pure IPS while maintaining asymptotic unbiasedness

Beyond point estimates, CPE must quantify uncertainty to support safe policy deployment. Techniques include:

• Bootstrap confidence intervals on the estimated policy value
• Concentration inequalities like Hoeffding's or Bernstein bounds adapted for off-policy data
• Studentized statistics that account for the heavy-tailed nature of importance-weighted returns This transforms CPE from a simple estimate into a rigorous statistical test for policy improvement.

In sequential settings like reinforcement learning, the importance weight becomes a product of action probabilities across the entire trajectory. This causes exponential variance growth with horizon length. Solutions include:

• Step-wise importance sampling that reweights per-transition instead of per-trajectory
• Marginalized importance sampling that estimates state distribution ratios directly
• Stationary distribution correction for infinite-horizon average reward settings

CPE methods span a spectrum of model reliance:

• Model-Free: Pure importance sampling approaches that require no environment model but suffer from high variance
• Model-Based: Learn a transition and reward model from historical data, then simulate the target policy. Lower variance but introduces model bias
• Hybrid: Methods like MAGIC (Model And Guided Importance sampling Combining) that blend both approaches, adaptively weighting model-based and model-free estimates to minimize mean squared error

The broader family of techniques that estimate a target policy's performance using data collected from a different behavior policy. Counterfactual Policy Evaluation is a subset of OPE that specifically estimates what would have happened under an alternative policy.

• Key methods: Importance Sampling, Doubly Robust, Fitted Q-Evaluation
• Core challenge: Correcting for distribution shift between logging and target policies
• Variance control: Clipping importance weights to reduce estimator variance

A statistical re-weighting technique that corrects for the mismatch between the behavior policy that collected historical data and the evaluation policy being assessed. Each trajectory is weighted by the ratio of action probabilities under the two policies.

• Step-wise IS: Multiplies probability ratios across all timesteps in a trajectory
• Per-decision IS: Applies weights only up to the relevant decision point, reducing variance
• Weighted IS: Normalizes weights to sum to one, trading bias for lower variance

A hybrid estimator that combines importance sampling with a learned value function model to provide unbiased policy evaluation even when one component is misspecified. It blends the direct method's low variance with importance sampling's asymptotic correctness.

• Requires both a reward model and a value function approximator
• Consistent if either the propensity model or the reward model is correctly specified
• Often used as the gold standard for high-stakes counterfactual evaluation

A model-free OPE method that learns a Q-function for the evaluation policy using only historical transition data. It iteratively applies the Bellman operator to approximate the target policy's value without requiring importance weights.

• Advantage: Avoids the high variance of importance sampling in long horizons
• Limitation: Relies on function approximation quality and sufficient state coverage
• Often combined with conservative Q-learning to prevent overestimation bias

The process of identifying when the state-action distribution induced by the evaluation policy diverges significantly from the logging data distribution. Critical for determining when counterfactual estimates become unreliable.

• Density ratio estimation: Learns a classifier to distinguish logging vs. target policy data
• Effective sample size: Measures how many independent samples remain after re-weighting
• Uncertainty-aware OPE: Produces confidence intervals that widen under severe shift

Statistical hypothesis testing frameworks that determine whether one policy significantly outperforms another using only historical data. Extends counterfactual evaluation from single-policy estimation to pairwise or ranking comparisons.

• Paired estimators: Correlate estimates to reduce variance in the difference
• Multiple testing correction: Controls false discovery rate when comparing many policies
• Enables safe policy improvement without deploying inferior candidates to production