PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Doubly Robust Off-Policy Evaluation for Ranking Policies under Diverse User Behavior

Kosuke Iguchi, Ren Kishimoto

arXiv:2608.29600v1cs.LGcs.IR

TL;DR

Ranking-policy OPE suffers from high-variance full-ranking weights and bias from mismatched fixed browsing assumptions. ADR combines adaptive importance weighting with reward-model residual correction, is unbiased under the observed true behavior model, and achieves lower MSE than AIPS and conventional estimators across synthetic settings.

  • Problem

    Ranking-policy OPE must handle combinatorial ranking actions, where full-ranking IPS can have excessive variance and fixed browsing assumptions can introduce bias when user behavior varies.

  • Method

    ADR combines AIPS’s adaptive importance weighting with a reward-model residual correction through a control-variate construction.

  • Results

    ADR achieves lower MSE than AIPS and existing estimators across logged-data sizes and ranking lengths in synthetic experiments.

  • Takeaways & Limitations

    Adaptive weighting plus reward-model correction improves ranking OPE accuracy across the tested synthetic data sizes and ranking lengths.

  • Takeaways & Limitations

    ADR’s learned reward model is less accurate than its oracle reward model, and validation on real logs is needed because the experiments use only synthetic data.

Abstract

from arXiv · show

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.

1 Introduction

Ranking-policy OPE avoids costly online deployment but faces high variance because rankings form a combinatorial action space. ADR combines AIPS’s adaptive weighting with reward-model residual correction to improve this trade-off.

  • OPE estimates a new ranking policy’s value from logged data, avoiding costly online experiments that could damage user satisfaction.
  • Ranking-policy action spaces grow combinatorially with candidate-item count and ranking length, making full-ranking IPS weights high variance.
  • IIPS and RIPS reduce variance through fixed browsing assumptions, but misspecification can introduce bias under heterogeneous user behavior.
  • ADR combines AIPS’s adaptive importance weighting with a reward-model residual correction as a control-variate estimator.
  • The paper establishes ADR’s unbiasedness under the true user behavior model and reports lower MSE than AIPS and existing estimators across data sizes and ranking lengths.

2 Preliminaries

The preliminaries define ranking-policy OPE, IPS and doubly robust estimation, then motivate adaptive weighting for context-dependent user behavior. AIPS uses the actions relevant to each reward, but remains limited by large action sets and lacks reward-model correction.

  • Off-Policy Evaluation of Ranking Policies: Ranking-policy OPE estimates an evaluation policy’s value from logged contexts, ranking actions, and position-wise rewards under logging and evaluation policies.
  • Off-Policy Evaluation of Ranking Policies: Position weights α_l determine the policy-value metric; setting α_l = 1/log2(l + 1) yields Discounted Cumulative Gain.
  • Off-Policy Evaluation of Ranking Policies: IPS reweights logged rankings by evaluation-to-logging probabilities and is unbiased under common support, but full-ranking weights can have extremely high variance.
  • Off-Policy Evaluation of Ranking Policies: Doubly robust estimation uses a reward-model baseline and importance weighting of residual error to improve the bias–variance trade-off.
  • Off-Policy Evaluation of Ranking Policies: IIPS uses position-wise actions, RIPS uses the prefix a_1:l, and fixed structural assumptions can introduce bias under heterogeneous user behavior.
  • Adaptive IPS: AIPS adapts its weight to the context-dependent actions affecting each position-wise reward and is unbiased when the behavior model is observed.
  • Adaptive IPS: AIPS can remain difficult to estimate accurately with many unique actions and does not use a reward model as a control variate.

3 Our Approach

ADR combines AIPS’s adaptive importance weighting with a reward-model residual correction. Under observed true user behavior and common support, it is unbiased, with a sufficient condition for variance no larger than AIPS.

  • Estimator: ADR combines adaptive importance weighting with a reward-model residual correction for ranking-policy OPE.
  • Estimator: The reward-model prediction is evaluated under the evaluation policy, while the adaptive weight corrects its observed residual error.
  • Estimator: ADR treats the user behavior model as observed and assumes the reward model is given independently of the logged data.
  • Theory: ADR is unbiased when logged observations are i.i.d., the true user behavior model is observed, and common support holds, regardless of reward-model accuracy.
  • Theory: ADR has no larger variance than AIPS when the weighted reward-model error is no larger than the corresponding weighted expected-reward variation.
  • Theory: If the reward model equals the conditional expected reward everywhere, the variance-reduction condition always holds.

4 Experiments

Across synthetic experiments, ADR achieved the lowest MSE among non-oracle estimators as logged-data size and ranking length varied. Its improvements over AIPS reflected reductions in squared bias and variance, although learned reward models remained less accurate than the oracle.

  • Effect of data size: ADR achieved the lowest MSE among non-oracle estimators at every tested data size.Its MSE decreased from 2.465 at n=1,000 to 0.105 at n=32,000 and remained below AIPS.
  • Effect of data size: ADR reduced squared bias at every data size and had lower variance than AIPS for n≥2,000.At n=32,000, ADR reduced squared bias from 1.205 to 0.00554 and variance from 0.151 to 0.100.
  • Effect of ranking length: At L=14, IPS variance reached 796.278, while IIPS and RIPS retained substantial squared bias despite lower variance.IIPS had variance 0.00558 and squared bias 18.035; RIPS had variance 50.291 and squared bias 2.583.
  • Effect of ranking length: ADR achieved the lowest MSE for every ranking length, with improvements over AIPS of 90.8% at L=4 and 37.2% at L=14.At L=14, ADR’s MSE was 6.645 versus 10.581 for AIPS, while squared bias and variance also decreased.
  • Reward-model comparison: ADR (oracle) achieved lower MSE than ADR with a learned reward model in both experiments.The gap suggests that improving reward prediction could further improve ADR’s estimation accuracy.

5 Conclusion

The paper concludes that ADR combines adaptive importance weighting with reward-model residual correction for ranking OPE. It is unbiased under the true user behavior model, achieves lower MSE in synthetic experiments, and still requires validation on real logs.

  • ADR combines adaptive importance weighting with reward-model residual correction for ranking OPE.
  • ADR is unbiased under the true user behavior model and has a sufficient condition for variance reduction.
  • Synthetic experiments show lower MSE than existing estimators, but validation on real logs is needed.

A.1 Proof Setup

The proof setup derives ADR’s expectation and compares its variance with AIPS using adaptive weights and reward-model residuals. The variance condition concerns weighted sums across positions because positions share the same ranking.

  • The proof expands ADR as a reward-model prediction plus an adaptively weighted observed residual.
  • ADR’s unbiasedness does not depend on reward-model predictive accuracy because the baseline prediction cancels within the residual correction.
  • The variance comparison uses the law of total variance to contrast ADR with AIPS.
  • The sufficient condition compares variation in the importance-weighted reward-model error with variation in the importance-weighted expected reward.
  • Because positions share a ranking, the variance-reduction condition is evaluated for the weighted sum rather than position by position.

B.1 Experimental Details

The experiments use a synthetic ranking OPE environment with context-dependent user behavior, learned behavior and reward models, and repeated simulations across data sizes and ranking lengths. ADR is compared with conventional estimators and an oracle reward-model variant.

  • Environment: The synthetic environment samples five-dimensional normal contexts and provides three candidate items at each position.Rankings may be longer than the number of candidate items because policies allow repeated items.
  • Environment: Context-dependent user behavior is generated from action–reward interaction matrices specifying which ranking items affect each position-wise reward.
  • Model estimation: Practical AIPS and ADR learn user behavior models with UBTree and use two-fold cross-fitting.The estimated model selects among six candidate interaction structures.
  • Model estimation: ADR learns a separate reward regressor for each position using context and the full ranking, with out-of-fold predictions from two-fold cross-fitting.
  • Estimator comparison: ADR and AIPS share estimated behavior models and self-normalized weights, while ADR (oracle) uses the simulator’s true conditional expected reward.The oracle estimator is not implementable and serves as a reference for ideal reward-model information.
  • Evaluation protocol: Each condition uses 10,000 simulations, with MSE evaluated against the simulator’s on-policy reference value and 95% percentile confidence bands.

B.2 Bias–Variance Decomposition of All Estimators

The experiments decompose estimator error into MSE, squared bias, and variance across data sizes and ranking lengths. ADR improves on AIPS and conventional estimators by reducing both error components, including for long rankings.

  • The experiments report MSE, squared bias, and variance across data size and ranking length.
  • At n=32,000, ADR reduces AIPS squared bias from 1.205 to 0.006 and variance from 0.151 to 0.100.Both reductions contribute to ADR’s lower MSE in the data-size experiment.
  • At L=14, ADR reduces AIPS squared bias from 4.038 to 1.024 and variance from 6.543 to 5.620.ADR achieves the smallest MSE among all non-oracle estimators at every ranking length.

B.3 Comparison of Reward-Model Information

This comparison separates improvements from learning an observable-information reward model from gains requiring each sample’s latent realized user behavior. The latter information is unavailable in ordinary logged data.

  • ADR, marginal-true-q ADR, and latent-true-q ADR share the estimated behavior model and self-normalized weights but differ in reward-model information.The comparison isolates how reward-model information affects estimation accuracy.
  • Marginal true q averages expected reward over possible user behaviors given observable context and action, without using realized c_i.It represents the ideal reward-model target available from observable logged information.
  • Latent true q conditions reward prediction on each sample’s realized c_i, which is unavailable in ordinary logged data and yields zero reward-model error.It is therefore a stronger oracle reference than marginal true q.
  • Marginal true q reduces MSE relative to learned q by 31.4% at n=32,000 and 29.9% at L=14.This quantifies the improvement possible from an ideal reward model within observable information.
  • Latent true q further reduces MSE relative to marginal true q by 37.5% at n=32,000 and 44.5% at L=14.This additional gain reflects access to each sample’s unobserved realized c_i rather than merely perfect population-target prediction.

B.4 Effect of Self-Normalization

The experiments apply self-normalization to limit domination by extreme importance weights, especially for long rankings. This lowers MSE by trading increased finite-sample bias for substantially lower variance.

  • The theoretical analysis uses unnormalized weights, whereas the main experiments self-normalize AIPS and ADR under the same practical conditions.Self-normalization limits the influence of extremely large weights in long rankings.
  • Self-normalization generally loses exact finite-sample unbiasedness, so the main-text theoretical guarantees do not directly apply.It creates a bias–variance trade-off by reducing the influence of extreme weights.
  • At n=32,000, self-normalization reduces AIPS variance by 51.3% and ADR variance by 8.1%, improving MSE by 9.9% and 7.2%, respectively.Squared bias increases slightly for both estimators in this data-size condition.
  • At L=14, self-normalization reduces AIPS variance by 97.9% and ADR variance by 95.6%, improving MSE by 96.6% and 94.8%, respectively.The variance reductions outweigh increases in squared bias, making self-normalization particularly effective for long rankings.
Loading 2608.29600v1…