In reinforcement learning and contextual bandits, we often want to answer a counterfactual question: How would a new policy perform if we deployed it right now? To answer this without risking real-world failure, we turn to Off-Policy Evaluation (OPE), using historical data logs collected by an older system.
Traditionally, OPE relies on a mechanism called Importance Sampling (IS). If the historical "behavior policy" ($\pi_b$) selected an action $a$ in state $s$ with a known probability $\pi_b(a|s)$, we can reweight the observed rewards by the ratio of the new policy's probability to the old policy's probability: $\frac{\pi_e(a|s)}{\pi_b(a|s)}$.
But what happens when the system that collected the data is a black box, a legacy heuristic, or a human expert? In these settings, the true action probabilities—known as propensity scores—are completely unknown. As noted by Langford et al. and Precup et al., real-world logs are frequently stripped of these probabilities due to storage constraints, privacy boundaries, or sheer system complexity, rendering standard importance sampling mathematically undefined.
To unlock the value of these "opaque" logs, a major research direction focuses on evaluating and learning policies when the behavior policy is entirely unknown.
The Statistical Penalty of Opaque Logs
When the logging policy is hidden, we lose a vital piece of information. Zhu et al. quantified this loss by proving a fundamental statistical gap between the known and unknown behavior policy regimes.
When $\pi_b$ is explicitly known, the difficulty of evaluation depends primarily on how well the historical data covers the actions the evaluation policy wants to take. However, when $\pi_b$ is unknown, any estimator incurs an explicit performance penalty proportional to the support size (the number of active actions) of the target policy. Intuitively, because we do not know the baseline probability of unchosen actions, we must spend statistical power implicitly reconstructing the boundaries of what the behavior policy might have done.
Strategy 1: Policy Estimation and the Calibration Paradox
The most intuitive way to bypass an unknown behavior policy is to estimate it. By treating the historical state-action pairs $(s, a)$ as training data, we can fit a supervised learning model $\hat{\pi}_b(a|s)$ and plug it directly into our importance weights.
However, this approach introduces a fascinating statistical paradox. You might assume that the more accurately $\hat{\pi}_b$ mirrors the true underlying policy, the better your evaluation will be. Raghu et al. demonstrated that this is not the case: calibration matters far more than raw accuracy. If a deep neural network predicts action probabilities with high accuracy but poor calibration (meaning its confidence doesn't match real-world frequencies), the resulting OPE estimates suffer from massive variance. Surprisingly, simpler, well-calibrated models like $k$-nearest neighbors often yield significantly more reliable evaluations.
Even more counterintuitively, estimating the behavior policy can sometimes be better than using the true logging policy, even if the true policy is known. Liu et al. introduced Maximum Likelihood Inverse Propensity Scoring (MLIPS), demonstrating that substituting a known logging policy with an empirically estimated "surrogate" policy actually reduces evaluation variance.
Why does this happen? The true policy dictates the expected distribution of data, but a finite dataset inevitably contains random sampling chatter. An estimated policy captures the actual empirical frequencies present in the log, effectively canceling out accidental sample variance.
True Policy π_b (Expectation) ──> Contains random sampling chatter in finite logs
│
Estimated Policy \hat{π}_b ──> Captures actual empirical frequencies (Lower Variance)
Strategy 2: Behavior-Agnostic Evaluation
Rather than trying to reconstruct the missing propensity scores, a parallel track of research seeks to eliminate them from the equations entirely. These are known as behavior-agnostic estimators.
Instead of reweighting individual, step-by-step transitions (which causes variance to explode over long horizons), modern behavior-agnostic methods focus on estimating the stationary distribution corrections—the global ratio of how often the target policy visits a state versus how often the historical data contains that state.
The breakthrough framework DualDICE, developed by Dai et al., achieves this by leveraging Fenchel duality. By reframing the distribution-matching problem into a minimax optimization objective, the authors proved that the optimization can be solved using only samples from the dataset, completely bypassing the need to know or estimate $\pi_b(a|s)$.
Building on this duality perspective, Uehara et al. introduced Minimax Weight Learning (MWL) and Minimax Q-Function Learning (MQL). These methods treat policy evaluation as a game between a discriminator trying to find discrepancies between the target distribution and the dataset, and a weight-generator trying to minimize those discrepancies.
Similarly, Mousavi 0003 et al. framed off-policy estimation as a fixed-point problem of a "backward flow" operator. By solving this operator in a Reproducing Kernel Hilbert Space (RKHS), the evaluation remains robust even if the underlying data was generated by a mixture of completely unknown, non-stationary actors.
Summary
Evaluating a new strategy using logs from an opaque system initially seems impossible because we lack the denominator for our importance weights. The field has resolved this challenge through two distinct insights:
- Empirical Smoothing: If we choose to estimate the behavior policy, optimizing for calibration rather than accuracy allows us to filter out the random noise inherent in finite logs.
- Duality and Optimization: By shifting our focus from step-by-step action probabilities to global state-distribution corrections, we can reframe OPE as a minimax optimization problem that naturally cancels out the need for propensity scores entirely.
Key Foundational Work
Off-policy Learning with Options and Recognizers (2005) — contributed 1 concept elements to this direction.
Exploration scavenging (2008) — contributed 1 concept elements to this direction.