Doubly robust policy evaluation

The bias of DR is the product of the two errors. Add and subtract the true mean reward in one summand. With $I=\mathbf 1\{\pi(x)=a\}$,$$\frac{(r_a-\hat\varrho_a)I}{\hat p}+\hat\varrho_{\pi(x)}=\underbrace{\frac{(r_a-\varrho_a)I}{\hat p}}_{\varepsilon}+\varrho_{\pi(x)}+\Delta\Big(1-\frac{I}{\hat p}\Big).$$The noise $\varepsilon$ has mean zero given $(x,a)$, and $\mathbb E[I\mid x,h]=p$, so the last piece has mean $\Delta\delta$: the model error is added outside the correction and removed inside it, up to the propensity error. Hence the bias is $|\mathbb E[\Delta\delta]|$ (Theorem 1), against $|\mathbb E_x\Delta|$ for DM and $|\mathbb E_x[\varrho_{\pi(x)}\delta]|$ for IPS, which are special cases of the same formula (IPS is $\hat\varrho\equiv0$, DM drops the correction). DR is unbiased if either model is right and nearly unbiased if either is nearly right, though no estimator dominates in general. The formula also covers missing overlap: where the logger never takes $\pi(x)$, the correction never fires, $\delta=1$ whatever $\hat p$ is, and DR is the direct method there, carrying the full model error.

In the variance, the inverse-propensity factor multiplies only the squared residual. Square the same decomposition. The cross terms with $\varepsilon$ vanish, since it has conditional mean zero, and the one new ingredient is the second moment of the correction factor, with $p=p(\pi(x)\mid x)$,$$\mathbb E\Big[\Big(1-\frac I{\hat p}\Big)^2\,\Big|\,x\Big]=\delta^2+\frac{p(1-p)}{\hat p^2}=\delta^2+\frac{1-p}{p}(1-\delta)^2.$$Completing the square with the $\varrho_{\pi(x)}$ term gives, for a stationary logger, Theorem 2:$$\mathrm{Var}\,\hat V_{\rm DR}=\frac1{|S|}\Big(\mathbb E[\varepsilon^2]+\mathrm{Var}_x\big[\varrho_{\pi(x)}+\Delta\delta\big]+\mathbb E_x\Big[\frac{1-p}{p}\,\Delta^2(1-\delta)^2\Big]\Big),$$and IPS has the same expression with $\Delta$ replaced by $-\varrho_{\pi(x)}$ (my check: a simulation with three contexts and two actions matches both theorems to Monte Carlo error). In both, the inverse-propensity factor $(1-p)/p$ multiplies a squared error, $\Delta^2$ for DR and $\varrho^2_{\pi(x)}$ for IPS, so any reward model closer to the truth than zero helps. The reward-noise term is the same for both, $\mathbb E[\varepsilon^2]\approx\mathbb E_x[\sigma^2/p]$, with $\sigma^2$ the conditional variance of the reward, and no reward model can remove it. DM has neither term, so its error is typically almost all bias. Fitting both models on data separate from $S$ keeps $\Delta$ and $\delta$ fixed functions.

In evaluation, even a badly biased reward model reduces variance as a control variate. On nine UCI classification sets turned into bandits with uniform logging and known propensities, IPS and DR are unbiased, as Theorem 1 predicts, while the direct method's bias of 0.06 to 0.28 in classification error accounts for all of its rmse, and DR's rmse is below IPS's on most sets (letter 0.049 to 0.030). Under covariate shift on web-portal data, DR lowers the rmse by 13.6 percent on average, and the gain is in the variance.

For learning, DR fills in the full loss vector and any cost-sensitive learner runs on it. Impute every action's loss by its DR estimate,$$\hat l_{\rm DR}(x,a')=\hat l(x,a')+\frac{\big(l_a-\hat l(x,a)\big)\,\mathbf 1\{a'=a\}}{p(a\mid x)},$$and hand the completed vectors to a full-information learner. IPS imputation is the same with $\hat l\equiv0$, which leaves one inflated entry and $k-1$ zeros per example, so every unlogged action appears to have zero loss. The gains are much larger than in evaluation: with direct loss minimization the test error on optdigits falls from 0.644 to 0.090. This part is empirical only; the theory covers evaluating a fixed policy.

Minimizing IPS over a class picks policies whose estimates are low by chance, and a variance-sensitive bound corrects for this. Swaminathan and Joachims log $(x_i,y_i,\delta_i,p_i)$, with $\delta_i$ the loss (unrelated to the propensity error above) of the output $y_i$ the stochastic logger $h_0$ chose and $p_i=h_0(y_i\mid x_i)$, and estimate a stochastic policy's risk by clipped IPS, $\hat R^M(h)=\frac1n\sum_iu_h^i$ with $u_h^i=\delta_i\min\{M,h(y_i\mid x_i)/p_i\}$, clipped because the weights $h/p_i$ are unbounded and one small propensity can move the estimate arbitrarily. Unclipped, the estimate is unbiased for each $h$, but its variance differs by orders of magnitude across the class, large for policies that put mass where $h_0$ rarely went, so its minimizer favors policies whose estimate is low by chance. With losses in $[-1,0]$ (Step 6 says why) clipping is conservative, since $\delta\min\{M,w\}\ge\delta w$. To bound the risk uniformly, map each policy to $f_h=1+u_h/M$, a function with values in $[0,1]$, apply Maurer and Pontil's uniform empirical Bernstein inequality over that class, and multiply back by $M$ (Maurer and Pontil need $n\ge16$). The sample variance of $f_h$ is $\mathrm{Var}_h(u)/M^2$, so the variance term comes out with no $M$ in it, and $R\le R^M$ finishes the proof: with probability at least $1-\gamma$, for all $h\in H$,$$R(h)\le\hat R^M(h)+\sqrt{\frac{18\,\mathrm{Var}_h(u)\,Q_H(n,\gamma)}{n}}+\frac{15\,M\,Q_H(n,\gamma)}{n-1},$$with $\mathrm{Var}_h(u)$ the sample variance of the $u_h^i$ and $Q_H(n,\gamma)=\log\big(10\,\mathcal N_\infty(1/n,\mathcal F_H,2n)/\gamma\big)$, with $\mathcal F_H$ the class of the $f_h$. The first term is the policy's own standard deviation, which tells well-measured policies from noisy ones where Hoeffding would charge every policy $M/\sqrt n$; $M$ appears as a factor only in the order-$1/n$ range term, which without clipping is unbounded unless the propensities are bounded below. The CRM principle minimizes $\hat R^M(h)+\lambda\sqrt{\mathrm{Var}_h(u)/n}$, an upper confidence bound; $\lambda=0$ is clipped IPS.

The loss must be translated to $[-1,0]$, because the objective has to be an upper bound. With nonnegative losses, a policy that puts zero mass on every logged output has $\hat R^M=0$ and zero variance, the best possible value, though nothing is known about its risk. A risk bound that holds without full support corrects this. For losses in $[\nabla,\triangle]$,$$\mathbb E_{y\sim h(x)}\delta(x,y)\le\triangle+\mathbb E_{y\sim h_0(x)}\Big[(\delta(x,y)-\triangle)\frac{h(y\mid x)}{h_0(y\mid x)}\Big],$$since outputs $h_0$ never produces contribute at most $\triangle$ times their mass. Rescaling $\delta\mapsto(\delta-\triangle)/(\triangle-\nabla)\in[-1,0]$ then charges mass on unlogged outputs the worst loss, and the data-avoiding policy scores 0, the worst value. For the same reason $\lambda$ must stay small enough that $h_0$ itself has a negative objective, or the penalty lets the data-avoiding policy win; the experiments set $M$ to the ratio of the 90th to the 10th percentile propensity. Their follow-up (NeurIPS 2015) shows that the translation is not enough. The learner can still lower $\hat R$ by inflating the total weight $\frac1n\sum_ih(y_i\mid x_i)/p_i$, whose expectation is 1, putting mass on logged outputs whatever their loss. They call this propensity overfitting and remove it with the self-normalized estimator $\sum_i\delta_iw_i/\sum_iw_i$, whose minimizer does not change when a constant is added to the loss.

POEM makes the penalty trainable by SGD, and beats IPS minimization on every set. For softmax linear policies $h_w(y\mid x)\propto\exp(w\cdot\phi(x,y))$ the penalty $\sqrt{\mathrm{Var}_w(u)}$ is not a sum over examples; writing $\mathrm{Var}_w=\frac1{n-1}\big(\sum_i(u_w^i)^2-n\bar u_w^2\big)$ and taking tangent-line bounds at the current $w_t$, $\sqrt v\le\sqrt{v_0}+(v-v_0)/(2\sqrt{v_0})$ and $-\bar u^2\le\bar u_0^2-2\bar u_0\bar u$, gives a surrogate linear in $\sum_iu^i_w$ and $\sum_i(u^i_w)^2$, so each epoch runs AdaGrad on per-example gradients and then re-linearizes, a majorize-minimize scheme. On four multilabel sets turned into bandit feedback by a CRF logger, POEM beats IPS minimization on every set, significantly, though two of the four gains are small (Scene 1.193 to 1.168 in Hamming loss) and TMC's is large (2.808 to 2.197). Sharpening the logger toward its argmax, $w_0\mapsto\alpha w_0$, shrinks POEM's margin until, for $\alpha\ge16$, it only recovers the logger's own argmax prediction. The benefit of the variance penalty is shown only empirically, on these four sets.