Off-policy evaluation (OPE) of ranking policies is challenging be- cause selecting and ordering multiple items from a candidate set makes the number of possible rankings grow combinatorially with the number of candidates and the ranking length. Consequently, Inverse Propensity Scoring (IPS), whose importance weight is the full-ranking probability ratio under the evaluation and logging policies, can have excessive variance. Independent IPS (IIPS) and Reward Interaction IPS (RIPS) reduce variance by imposing fixed assumptions on how users browse rankings, but may introduce bias when those assumptions mismatch actual behavior. Adaptive Inverse Propensity Scoring (AIPS) addresses this trade-off by adap- tively marginalizing importance weights over the actions that affect each position-wise reward. It attains minimum variance within a class of unbiased IPS-based estimators when the true user be- havior model is observed. However, its estimation accuracy may still degrade for longer rankings, and AIPS does not use a reward model for residual correction. We propose Adaptive Doubly Robust (ADR), which combines adaptive importance weighting with re- ward regression through a control-variate correction. We establish its unbiasedness when the true user behavior model is observed and characterize a sufficient condition under which it reduces vari- ance relative to AIPS. Across synthetic experiments with 10,000 simulations per condition, ADR improves mean squared error over AIPS and conventional ranking OPE estimators across a range of logged-data sizes and ranking lengths.
Figures & tables
Figure 1. MSE against data size (left) and ranking length (right). Two line charts compare the MSE of six off-policy estimators as data size and ranking length vary.
n
Bias 2
Variance
AIPS
ADR
AIPS
ADR
1,000
0.986
0.0959
2.279
2.369
2,000
0.898
0.0307
1.444
1.375
4,000
0.987
0.0232
0.850
0.754
8,000
1.053
0.0212
0.459
0.381
16,000
1.099
0.0131
0.266
0.206
Table 1. Bias–variance decomposition of AIPS and ADR across all conditions.
Figure 2. MSE, squared bias, and variance against data size (top) and ranking length (bottom). Six line charts show MSE, squared bias, and variance for six estimators as data size and ranking length change.
Metric
Estimator
n=1 k
n=2 k
n=4 k
n=8 k
n=16 k
n=32 k
MSE
IPS
45.160
22.051
12.053
5.491
2.713
1.423
IIPS
7.841
7.865
7.923
7.874
7.843
7.837
RIPS
4.826
3.145
2.435
1.974
1.766
1.695
AIPS
3.266
2.342
1.837
1.513
1.365
1.356
ADR
2.465
1.406
0.777
0.403
0.219
0.105
ADR (oracle)
0.816
0.552
0.316
0.175
0.091
0.045
Appendix
Table 3. MSE, squared bias, and variance of all estimators in the data-size experiment.
Metric
Estimator
L=4
L=6
L=8
L=10
L=12
L=14
MSE
IPS
0.039
0.548
5.493
54.177
387.848
796.968
IIPS
2.354
4.852
7.873
10.611
14.032
18.040
RIPS
0.635
1.137
1.974
4.414
14.069
52.874
AIPS
0.169
0.690
1.510
3.239
6.115
10.581
ADR
0.016
0.087
0.402
1.444
3.498
6.645
ADR (oracle)
0.00574
0.032
0.175
0.551
1.328
2.586
Appendix
Table 4. MSE, squared bias, and variance of all estimators in the ranking-length experiment.
Figure 3. Comparison of reward-model information. The left and right panels show MSE against data size and ranking length, respectively. Two line charts compare ADR using a learned reward model, a marginalized true reward model, and a true reward model conditional on latent user behavior.
n
ADR
Marginal true q
Latent true q
1,000
2.465
1.399
0.816
32,000
0.105
0.072
0.045
Appendix
Table 5. MSE of ADR with different reward models at representative data sizes.
L
ADR
Marginal true q
Latent true q
4
0.0156
0.00732
0.00574
14
6.645
4.660
2.586
Appendix
Table 6. MSE of ADR with different reward models at representative ranking lengths.
Figure 4. Effect of self-normalization on AIPS and ADR. The top and bottom rows report MSE, squared bias, and variance against data size and ranking length, respectively. Six line charts compare MSE, squared bias, and variance of raw and self-normalized AIPS and ADR estimators.
Condition
Estimator
MSE
Bias 2
Variance
n=32,000
AIPS (raw)
1.505
1.195
0.310
AIPS (self-normalized)
1.356
1.205
0.151
ADR (raw)
0.114
0.00491
0.109
ADR (self-normalized)
0.105
0.00554
0.0998
L=14
AIPS (raw)
314.774
1.049
313.725
AIPS (self-normalized)
10.581
4.038
6.543
Appendix
Table 7. MSE, squared bias, and variance before and after self-normalization at representative conditions.
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
Off-policy evaluation (OPE) is essential for assessing ranking and recommendation systems without costly online interventions. Self-Normalised Inverse Propensity Scoring (SNIPS) is a standard tool for variance reduction in OPE, leveraging a multiplicative control variate. Recent advances in off-policy learning suggest that additive control variates (baseline corrections) may offer superior performance, yet theoretical guarantees for evaluation are lacking. This paper provides a definitive answer: we prove that β⋆-IPS, an estimator with an optimal additive baseline, asymptotically dominates SNIPS in Mean Squared Error. By analytically decomposing the variance gap, we show that SNIPS is asymptotically equivalent to using a specific -- but generally sub-optimal -- additive baseline. Our results theoretically justify shifting from self-normalisation to optimal baseline corrections for both ranking and recommendation.
Olivier Jeunen, Shashank Gupta
aampe Antwerp, Belgium · Microsoft AI Bangalore, India
Off-policy evaluation, which estimates evaluation policy performance from logged data, is key for recommender ranking policies. However, logged clicks cannot distinguish unexamined items from examined non-clicks, causing bias in existing estimators when the assumed examination structures fail. We propose two estimators based on the decomposition of clicks into examination and relevance. First, the latent-examination independent inverse propensity score (LE-IIPS) estimator corrects the IIPS bias using policy examination probability ratios. Second, the examination-decomposed doubly robust (ED-DR) estimator extends LE-IIPS to a doubly robust framework. ED-DR is unbiased if the examination probabilities are correct regardless of relevance accuracy, or under ranking-independent examination, even if both model estimates are inaccurate. Experiments show that ED-DR achieves a lower MSE than existing methods with large sample sizes, especially when the examination depends on ranking. We also highlight its limitations under small samples or cascade user behavior conditions.
Riki Okamura, Toshiharu Sugawara
Department of Computer Science and Communications Engineering, Waseda University, Tokyo, Japan