Off-policy evaluation estimates the value of a target policy using data generated by another policy. The core mathematical issue is distribution mismatch.
Importance sampling
Likelihood ratios convert behavior-policy trajectories into target-policy expectations when support is adequate.
Definition. For trajectory \(\tau\), behavior policy \(b\), and target policy \(\pi\), the trajectory importance ratio is \[ \rho(\tau)=\prod_{t=0}^{T-1}\frac{\pi(A_t\mid S_t)}{b(A_t\mid S_t)}. \] The ordinary importance-sampling estimator averages \(\rho(\tau_i)G(\tau_i)\).
Proposition. If \(b(a\mid s)>0\) whenever \(\pi(a\mid s)>0\), then \(\mathbb E_b\{\rho(\tau)G(\tau)\}=\mathbb E_\pi G(\tau)\).
Proof. The trajectory density under a policy factors into initial distribution, transition probabilities, and policy probabilities. The ratio \(\rho\) cancels the behavior policy factors and replaces them by target policy factors. Integrating under the behavior trajectory law therefore equals integration under the target trajectory law.
Variance and horizon
Importance ratios can have variance exponential in horizon.
Remark. Even when unbiased, ordinary trajectory importance sampling may be unusable for long horizons because it multiplies many random ratios. Per-decision ratios and marginalized density ratios reduce variance by exploiting temporal structure.
Doubly robust evaluation
Doubly robust estimators combine a model-based value estimate with importance correction.
Definition. A typical finite-horizon doubly robust estimator recursively combines estimated \(q\)- and \(v\)-functions with importance-weighted TD errors: \[ \hat V_{\mathrm{DR}}=\hat v_0(S_0)+\sum_{t=0}^{T-1}\rho_{0:t}\{R_{t+1}+\hat v_{t+1}(S_{t+1})-\hat q_t(S_t,A_t)\}. \]
Proposition. If either the importance ratios are correct or the \(q,v\) model is correct in the required conditional-expectation sense, the doubly robust estimator is unbiased.
Proof. When ratios are correct, each correction term has the target-policy expectation of the corresponding TD residual, so the telescoping sum recovers the target value. When the model is correct, each TD residual has conditional mean zero under the target dynamics, so the correction terms vanish in expectation and the initial model value is correct.
Coverage and overlap
No estimator can recover target-policy value from actions never taken by the behavior policy.
Definition. The support or overlap condition is \(\pi(a\mid s)>0\Rightarrow b(a\mid s)>0\) on the state-action region relevant to the target policy.
Remark. Failure of overlap is not a technical nuisance; it is nonidentifiability. The data contain no information about target actions absent under the behavior policy.
Change of measure on trajectories
Let behavior policy \(\mu\) generate data and target policy \(\pi\) be absolutely continuous with respect to \(\mu\). Define \[ \rho_t=\frac{\pi(A_t\mid S_t)}{\mu(A_t\mid S_t)}, \qquad W_t=\prod_{k=0}^{t}\rho_k. \] For any integrable function of history through time \(t\), \[ E_\mu\{W_tf(H_t,A_t)\}=E_\pi f(H_t,A_t). \] The dynamics cancel in the trajectory likelihood ratio.
Proposition (per-decision importance sampling). \[ J(\pi) =E_\mu\sum_{t\ge0}\gamma^tW_tR_t. \] The estimator is unbiased when support holds and expectations are finite.
Its variance can grow exponentially with horizon because \(W_t\) is a product. Self-normalization lowers variance but introduces finite-sample bias. Clipping weights makes the bias explicit: \[ |E[(W_t-\min\{W_t,c\})R_t]| \le R_{\max}E[(W_t-c)_+]. \]
Marginal density ratios
Discounted occupancy ratios \[ w(s,a)=\frac{d_\rho^\pi(s,a)}{d_\rho^\mu(s,a)} \] avoid full trajectory products: \[ J(\pi)=\frac1{1-\gamma}E_{d^\mu}\{w(S,A)r(S,A)\}. \] They satisfy a moment equation derived from discounted flow. For every test function \(f\), \[ E_{d^\mu}\left[ w(S,A)\{f(S)-\gamma E_\pi[f(S')\mid S,A]\} \right] =(1-\gamma)E_\rho f(S). \] Dual or minimax methods estimate \(w\) from this equation.
Doubly robust evaluation
Theorem (one-step doubly robust identity). Let \(q(s,a)\) be any function, \(v_q(s)=E_\pi\{q(s,A)\mid s\}\), and let \(w=d^\pi/d^\mu\). Then \[ J(\pi) =E_\rho v_q(S_0) +\frac1{1-\gamma}E_{d^\mu}\left[ w(S,A)\{R+\gamma v_q(S')-q(S,A)\} \right]. \] The identity remains valid if \(q=Q^\pi\) even with misspecified \(w\), or if \(w\) is correct even with misspecified \(q\).
Proof. If \(w\) is correct, change measure to \(d^\pi\). The discounted flow identity telescopes \[ E_\rho v_q+\frac1{1-\gamma}E_{d^\pi} \{\gamma v_q(S')-q(S,A)\}=0, \] because \(E_\pi(q\mid S)=v_q(S)\); the reward term leaves \(J(\pi)\). If \(q=Q^\pi\), the conditional Bellman residual has mean zero given \((S,A)\), so any integrable weight contributes zero.
Semiparametric inference and overlap
The doubly robust score is an influence-function representation. With cross-fitting and nuisance rates whose product is \(o_p(n^{-1/2})\), it can yield root-\(n\) normal inference under iid trajectories or suitable mixing. No estimator can overcome absent overlap: if \(d^\pi\) charges a state-action region unseen under \(\mu\), target value is not nonparametrically identified. Near violations appear as large efficiency bounds and unstable weights.