We study off-policy evaluation (OPE) in contextual bandits with data collected from multiple logging policies. Inverse propensity scoring (IPS) is a standard approach to OPE and extends naturally to the multi-logger setting. However, as highlighted by Agarwal et al. [2017], neither balanced nor weighted IPS consistently outperforms the other in this setting. We resolve this dilemma by deriving an optimal IPS estimator with sample-dependent weights that minimize variance subject to unbiasedness. Using a variational calculus approach, we obtain closed-form optimal weights, yielding an estimator that is unbiased and achieves asymptotically optimal variance within a generalized weighted-IPS estimator class. Instead of a reward model, the estimator needs only a K×K matrix and a K-vector of moments, where K is the number of logging policies, and we quantify how much efficiency this costs relative to the semiparametric oracle. Experiments on benchmark datasets show that our estimator generally improves on existing multi-logger IPS methods. We also extend our estimator to a doubly robust form by incorporating a conditional reward estimator. We compare the resulting DR extension with the semiparametrically efficient DR estimator of Kallus et al. [2021], both theoretically and empirically. We show that the two estimators achieve the same asymptotic variance when the conditional reward estimator is consistent, while our estimator can retain semiparametric efficiency under certain forms of reward misspecification. Empirically, the proposed DR estimator often achieves lower estimation error than the existing DR baseline.
Figures & tables
Dataset Name
OptDigits
SatImage
PenDigits
Letter
#Classes ( l )
10
6
10
26
#Samples
5620
6435
10992
20000
Table 1: Dataset Statistics
Appendix figures & tables15 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 1: Relative-RMSEs ( 5.1 ), computed over M=200 independent experiments, across datasets and estimators when the logging policies are known . Our proposed estimator J^oIPS is implemented with Z=5 -fold cross-fitting. The x -axis denotes the stratum-size ratio ( n1/n2 ) on a logarithmic scale, while the y -axis shows Relative-RMSE, also on a logarithmic scale. Lower values indicate better performance. Shaded bands show 95% paired percentile-bootstrap intervals (§ 5 ).
Figure 2: Relative-RMSEs ( 5.1 ), computed over M=200 independent experiments, across datasets and estimators when the logging policies are estimated . Shaded bands show 95% paired percentile-bootstrap intervals (§ 5 ). Where bands are not visible, they are narrower than the markers.
n1/n2
Dataset
IPS
bIPS
wIPS
oIPS
DR-bIPS
DR-oIPS
10−1
Letter
1.365e-6 0.021194
2.426e-7 0.013643
4.199e-9 0.012154
2.064e-7 0.009162
9.958e-8 0.012274
2.174e-7 0.008961
OptDigits
9.845e-6 0.036553
6.086e-6 0.025019
1.955e-6 0.015421
6.030e-8 0.007236
3.771e-6 0.020381
1.661e-8 0.008195
PenDigits
3.306e-6 0.024435
1.867e-6 0.016799
4.806e-7 0.011213
1.850e-7 0.006118
1.739e-6 0.013490
3.690e-7 0.006194
SatImage
1.315e-7 0.023837
1.240e-7 0.018533
1.246e-7 0.015773
9.588e-8 0.010424
2.831e-7 0.014409
1.638e-7 0.010491
1
Letter
2.891e-9 0.016254
1.825e-8 0.005653
2.700e-8 0.005392
6.420e-9 0.004901
2.165e-8 0.004846
1.414e-8 0.004680
OptDigits
3.120e-6 0.026398
5.313e-8 0.009119
7.139e-8 0.007522
5.952e-9 0.004654
1.070e-9 0.005835
2.516e-8 0.004749
Appendix
Table 2: Squared bias (top) and empirical standard deviation (bottom) of each estimator over M=200 trials at three representative stratum-size ratios, with known logging policies ( η=0.95 , K=2 ).
Figure 3: Relative-RMSEs, computed over M=200 independent experiments, are reported across different datasets and estimators under the setting where the logging policies are estimated . Shaded bands show 95% paired percentile-bootstrap intervals (§ 5 ). Where bands are not visible, they are narrower than the markers.
Figure 4: Rel-RMSE across five heterogeneous logging policies where they are known. Lower is better. Error bars show 95% paired percentile-bootstrap intervals (§ 5 ).
Figure 5: Rel-RMSE across five heterogeneous logging policies where they are estimated. Lower is better. Error bars show 95% paired percentile-bootstrap intervals (§ 5 ). Where error bars are not visible, they are shorter than the markers.
Figure 6: Rel-RMSE across three heterogeneous logging policies where they are known. Lower is better. Error bars show 95% paired percentile-bootstrap intervals (§ 5 ).
Figure 7: Rel-RMSE across three heterogeneous logging policies where they are estimated. Lower is better. Error bars show 95% paired percentile-bootstrap intervals (§ 5 ). Where error bars are not visible, they are shorter than the markers.
Figure 8: Mixture η=0.80 . Relative-RMSEs, computed over M=200 independent experiments, are reported across different datasets and estimators under the setting where the logging policies are known . Shaded bands show 95% paired percentile-bootstrap intervals (§ 5 ).
Figure 9: Mixture η=0.80 . Relative-RMSEs, computed over M=200 independent experiments, are reported across different datasets and estimators under the setting where the logging policies are estimated . Shaded bands show 95% paired percentile-bootstrap intervals (§ 5 ). Where bands are not visible, they are narrower than the markers.
Figure 10: Mixture η=0.65 . Relative-RMSEs, computed over M=200 independent experiments, are reported across different datasets and estimators under the setting where the logging policies are known . Shaded bands show 95% paired percentile-bootstrap intervals (§ 5 ).
Figure 11: Mixture η=0.65 . Relative-RMSEs, computed over M=200 independent experiments, are reported across different datasets and estimators under the setting where the logging policies are estimated . Shaded bands show 95% paired percentile-bootstrap intervals (§ 5 ). Where bands are not visible, they are narrower than the markers.
Estimator
K=10 Loggers
K=100 Loggers
Rel-RMSE
Time (ms)
Rel-RMSE
Time (ms)
Naive IPS ( J^IPS )
0.0113
0.16±0.02
0.0104
0.18±0.02
Balanced IPS ( J^bIPS )
0.0133
0.13±0.02
0.0087
0.51±0.01
Weighted IPS ( J^wIPS )
0.0122
2.16±0.03
0.0075
15.49±0.43
Optimal IPS ( J^oIPS )
0.0045
2.52±0.05
0.0045
20.06±0.13
Appendix
Table 3: Comparison of Relative RMSE and wall-clock Time (in milliseconds) on the Letter dataset with N=20,000 . We compare settings with K=10 and K=100 logging policies. Our method achieves the lowest error while maintaining a runtime comparable to the existing Weighted IPS baseline.
Estimator
N=104
N=105
N=106
IPS
13.0 (9.71, 16.2)
3.92 (2.88, 4.84)
1.40 (0.941, 1.79)
bIPS
6.14 (4.32, 7.94)
2.15 (1.53, 2.72)
0.729 (0.555, 0.904)
wIPS
3.83 (2.77, 4.82)
1.85 (1.23, 2.43)
0.544 (0.370, 0.718)
oIPS
2.70 (1.89, 3.43)
0.775 (0.570, 0.948)
0.199 (0.144, 0.251)
Appendix
Table 4: Relative-RMSE ( ×10−3 ) in the large- N synthetic experiment. Parentheses show 95% bootstrap CIs.
N
IPS
bIPS
wIPS
oIPS
Peak memory (MiB)
104
0.178
0.161
4.626
6.000
124.652
105
0.994
1.220
15.372
25.435
164.668
106
18.053
23.462
162.890
346.201
584.516
Appendix
Table 5: Mean runtime of each estimator in milliseconds, and the largest peak resident memory over 20 seeds. Memory is measured for a single process that generates the data and runs all four estimators.
Off-policy evaluation (OPE) for contextual bandit policies becomes challenging when action-level importance weighting incurs excessive variance. Doubly robust (DR) estimation remains unbiased under common support but retains these high-variance action-level weights. A prior estimator, Off-policy evaluation with Conjunct Effect Model (OffCEM), replaces them with more stable cluster-level weights, at the cost of relying on local correctness of the reward model. In this paper, we show that, under the assumptions required by DR and OffCEM, there exists an unbiased family of estimators that interpolates between OffCEM and DR. Building on this result, we propose the Variance Optimal-CEM (VOCEM) estimator, which selects the interpolation coefficient to minimize variance. We derive the population-optimal coefficient in closed form and show that the resulting estimator has variance no larger than either endpoint, OffCEM or DR. Experiments in controlled synthetic settings and on two large-action benchmarks show that VOCEM improves upon both endpoints in all 23 evaluated conditions, exhibiting greater stability and empirical robustness.
Nicolò Felicioni, Michael Benigni, Maurizio Ferrari Dacrema +1
Off-Policy Evaluation (OPE) is an important practical problem in algorithmic ranking systems, where the goal is to estimate the expected performance of a new ranking policy using only offline logged data collected under a different, logging policy. Existing estimators, such as the ranking-wise and position-wise inverse propensity score (IPS) estimators, require the data collection policy to be sufficiently stochastic and suffer from severe bias when the logging policy is fully deterministic. In this paper, we propose novel estimators, Click-based Inverse Propensity Score (CIPS), exploiting the intrinsic stochasticity of user click behavior to address this challenge. Unlike existing methods that rely on the stochasticity of the logging policy, our approach uses click probability as a new form of importance weighting, enabling low-bias OPE even under deterministic logging policies where existing methods incur substantial bias. We provide theoretical analyses of the bias and variance properties of the proposed estimators and show, through synthetic and real-world experiments, that our estimators achieve significantly lower bias compared to strong baselines, for a range of experimental settings with completely deterministic logging policies.
Koichi Tanaka, Kazuki Kawamura, Takanori Muroi +6
Keio University · Sony Group Corporation · Yale University +1
We study off-policy evaluation in the setting of contextual bandits, where we aim to evaluate a new policy using historical data that consists of contexts, actions and received rewards. This historical data typically does not faithfully represent action distribution of the new policy accurately. A common approach, inverse probability weighting (IPW), adjusts for these discrepancies in action distributions. However, this method often suffers from high variance due to the probability being in the denominator. The doubly robust (DR) estimator reduces variance through modeling reward but does not directly address variance from IPW. In this work, we address the limitation of IPW by proposing a Nonparametric Weighting (NW) approach that constructs weights using a nonparametric model. Our NW approach achieves low bias like IPW but typically exhibits significantly lower variance. To further reduce variance, we incorporate reward predictions -- similar to the DR technique -- resulting in the Model-assisted Nonparametric Weighting (MNW) approach. The MNW approach yields accurate value estimates by explicitly modeling and mitigating bias from reward modeling, without aiming to guarantee the standard doubly robust property. Extensive empirical comparisons show that our approaches consistently outperform existing techniques, achieving lower variance in value estimation while maintaining low bias.
Rong J. B. Zhu
Institute of Science and Technology for Brain-inspired Intelligence, Fudan University