PaperlayerView exact revision on arXiv

Source-linked AI summary

Recommendation Ranking Off-Policy Evaluation under Ranking-Dependent Examination via Examination-Relevance Decomposition

Riki Okamura, Toshiharu Sugawara

arXiv:2609.35034v1cs.IRcs.LG

TL;DR

When examination depends on the broader ranking, existing estimators such as IIPS can be biased. The paper proposes examination-relevance-decomposed estimators, and reports that ED-DR has the lowest MSE among compared estimators with large samples, especially under ranking-dependent examination.

  • Problem

    IIPS can be biased when examination depends on the broader ranking, because its item-only click assumption then fails.

    Source: §1 · p. 2, §3 · p. 4

  • Method

    LE-IIPS corrects IIPS using policy examination-probability ratios, and ED-DR extends it to a doubly robust framework based on decomposing clicks into examination and relevance.

    Source: §1 · p. 2

  • Results

    With large samples, ED-DR achieves the lowest MSE among compared estimators, especially when examination depends on ranking.

    Source: §1 · p. 2, §6 · p. 12

  • Takeaways & Limitations

    ED-DR is unbiased when examination probabilities are correctly estimated, or under ranking-independent examination.

    Source: §1 · p. 2

    Identifying examination requires the same item to appear at multiple positions with positive probability, a condition not met by deterministic policies.

    Source: §4.1 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

Ranking OPE avoids the risks and costs of online experiments, but click logs do not reveal whether an unclicked item was examined. The paper proposes examination-relevance estimators to address bias when examination depends on the broader ranking.

1 Introduction

  • OPE estimates evaluation-policy value from deployed-policy logs, avoiding the user-experience risks and operational costs of online experiments..Source: §1 · p. 1
  • Click logs cannot distinguish unexamined items from examined non-clicks, and ranking-dependent examination can bias existing ranking OPE estimators.The cited examples include IIPS, RIPS, cascade DR, and AIPS.Source: §1 · pp. 1–2
  • LE-IIPS corrects IIPS bias using policy examination-probability ratios, and ED-DR extends it to a doubly robust framework.The estimators are based on decomposing clicks into examination and relevance.Source: §1 · p. 2
  • With large samples, ED-DR achieves the lowest MSE among compared estimators, especially when examination depends on ranking, but underperforms with small samples and cascade behavior.Under cascade behavior, its relative MSE is higher than RIPS and cascade DR.Source: §1 · p. 2

2 Related Work

Prior work develops general OPE estimators, ranking-specific reward assumptions, and click models, while click decomposition has mainly supported learning rather than policy evaluation. This study embeds examination and relevance decomposition in OPE.

2 Related Work

  • DM can be biased by inaccurate reward predictions, IPS is unbiased under common support but can have high variance, and DR combines them to control bias and variance.Source: §2 · p. 2
  • Ranking OPE methods use per-position rewards: IIPS assumes only the presented item matters, while RIPS and cascade DR allow higher-ranked items to affect rewards.AIPS adaptively selects behavior assumptions by context.Source: §2 · p. 2
  • Click models distinguish examination from relevance: PBM makes examination position-dependent, cascade examination stops at the first relevant item, and DBN models post-click satisfaction.Source: §2 · p. 2
  • ULTR uses inverse examination weighting to learn rankings, whereas this study estimates target-policy value through off-policy evaluation.Source: §2 · p. 3
  • Unbiased recommender learning corrects feedback-selection bias, and Saito et al. [22] use click decomposition for unobserved relevance, but these works do not evaluate policy performance.Source: §2 · p. 3
  • Unlike prior OPE work, which does not explicitly model examination and relevance as random variables, this study embeds click decomposition into OPE estimators.Source: §2 · p. 3

3 Preliminaries

The section formalizes ranking OPE using logged contexts, rankings, and position-level clicks, then reviews IIPS and the conditions needed for its validity. IIPS becomes biased when clicks depend on more than the item at the current position.

3 Preliminaries

  • The logged dataset records contexts, rankings chosen by the logging policy, and binary clicks at each position; qk(x, a) is expected click probability.Source: §3 · p. 3
  • The target value uses provider-chosen position weights, while estimator accuracy is measured by MSE, decomposed into squared bias and variance.Equal weights yield total clicks, while logarithmic weights yield DCG.Source: §3 · p. 3
  • IIPS assumes each position's expected click depends only on the item shown there and reweights by the ratio of evaluation to logging marginal item-position probabilities.The marginal common-support condition requires logging-policy support wherever the evaluation policy assigns positive probability.Source: §3 · pp. 3–4
  • When examination depends on the full ranking, expected clicks can depend on other items, violating IIPS's independence assumption and causing bias.Source: §3 · p. 4

4 Proposed Method

The method decomposes clicks into examination and relevance to address ranking-dependent examination, then uses examination-probability ratios and a doubly robust estimator. Its analysis specifies when the estimators are unbiased and how prediction accuracy and sample size affect variance and MSE.

4.1 Click Models

  • The click model writes each click as examination times relevance; IIPS is unbiased when examination is ranking-independent but biased when it depends on the full ranking.Examination may depend on context and the full ranking, while relevance depends on context and the item at that position.Source: §4.1 · p. 4
  • Identifying examination requires the same item to appear at multiple positions with positive probability; deterministic policies do not provide this support.The examination–relevance scaling ambiguity is harmless for policy value, but the decomposition is unidentifiable when (A2) fails.Source: §4.1 · p. 4

4.2 Proposed Estimators

  • LE-IIPS corrects IIPS bias under ranking-dependent examination using examination-probability ratios between evaluation and logging policies.Under PBM and contextual PBM, LE-IIPS coincides with IIPS.Source: §4.2 · p. 5
  • ED-DR uses non-clicked observations and pools relevance data across positions, improving estimation for rare item-position pairs.It decomposes expected clicks into examination and relevance rather than directly regressing expected clicks.Source: §4.2 · p. 5

4.3 Theoretical Analysis

  • LE-IIPS is unbiased when its examination probabilities are correctly estimated, under the stated assumptions.Source: §4.3 · p. 6
  • ED-DR is unbiased with correct examination probabilities regardless of relevance accuracy, or under ranking-independent examination even when both estimates are inaccurate.These conditions correspond to correct examination estimates or examination satisfying (E1) or (E2).Source: §4.3 · p. 6
  • ED-DR has lower variance when its relevance and examination estimates reduce residual error; negatively correlated prediction and target terms can instead raise variance.Under ranking-independent examination, its variance is lower than IIPS's when the prediction error for D is no greater than the variance of D.Source: §4.3 · p. 7
  • ED-DR has lower MSE than IIPS above a sample-size threshold, and that threshold shrinks as IIPS bias grows.Source: §4.3 · p. 7

5 Experiments

Synthetic experiments test the estimators across sample sizes, examination structures, model-estimation errors, DBN user behavior, and logging-policy temperatures. ED-DR performs best in several large-sample settings, but its relative performance depends on assumptions and data conditions.

5.1 Experimental Setup

  • Experiments use synthetic data to test theoretical behavior and robustness when assumptions such as (A1) and (A2) do not hold.The default setup uses Plackett–Luce logging and an ϵ-greedy evaluation policy; estimators are assessed by relative MSE, squared bias, and variance.Source: §5 · p. 7, §5.1 · p. 8

5.2 Results

  • Except for oracle estimators, ED-DR consistently achieves the lowest relative MSE, with degradation under violated assumptions appearing as increased bias rather than variance.This is the overall result across the reported experiments.Source: §5.2 · p. 8

Effect of the sample size.

  • At large sample sizes under ranking-dependent examination, ED-DR outperforms IIPS; at small sizes, IIPS dominates because its variance is lower.Under (E1), IIPS is unbiased and performs comparably to the other estimators, while ED-DR matches IIPS despite using estimated parameters.Source: Effect of the sample size · p. 8

Effect of decay exponent

  • As λ increases, examination at lower positions decreases and estimation error falls for most estimators; ED-DR has the lowest relative MSE, with a slight edge over DR-IIPS at λ = 2.The comparison varies λ across 0.5, 1.0, and 2.0 under (E3).Source: Effect of decay exponent · p. 9, Figure 2 · p. 9

Effect of errors in the examination and relevance estimates.

  • ED-DR bias stays zero when relevance estimates are corrupted under (E3) or examination estimates under ranking-independent (E2), but grows with examination-estimation error under (E3).In the latter case, ED-DR matches oracle LE-IIPS given the same corrupted examination estimate.Source: Effect of errors in the examination… · p. 10, Figure 3 · p. 10

Effect of misspecified examination probabilities.

Under DBN.

  • As DBN departure probability ρ grows, ED-DR bias increases while variance stays constant, and it remains superior to IIPS unless ρ approaches 1.At ρ = 1, RIPS and cascade DR outperform ED-DR in relative MSE because their variance drops significantly.Source: Under DBN · p. 11, Figure 5 · p. 11

Effect of logging policy temperature τ0.

  • At small logging temperatures, all weight-based estimators have exploding variance while DM remains stable but biased; at larger temperatures, ED-DR has the lowest relative MSE.At small τ0, the logging policy becomes deterministic and e_k and r become unidentifiable, causing importance weights to diverge.Source: Effect of logging policy temperature τ0 · p. 12, Figure 6 · p. 12

6 Conclusion

The conclusion presents LE-IIPS and ED-DR as estimators built on decomposing clicks into examination and relevance. It summarizes ED-DR’s unbiasedness conditions and its large-sample advantage, while identifying settings where performance falls behind.

6 Conclusion

  • LE-IIPS corrects IIPS bias and ED-DR extends it to a doubly robust estimator by decomposing clicks into examination and relevance.The decomposition addresses the ambiguity between unexamined items and examined non-clicks.Source: §6 · p. 12
  • ED-DR is unbiased with accurately estimated examination probabilities or ranking-independent examination, and beats IIPS beyond n* under ranking-dependent examination.Experiments report its lowest MSE for large samples, but worse performance under small samples, nearly deterministic policies, or strong DBN departure dynamics.Source: §6 · p. 12
  • Future work would select or average assumed examination structures by context and extend click decomposition to sequential examination for cascade models and DBN.Source: §6 · p. 12

A.2 Auxiliary Lemmas

This appendix section introduces two lemmas used repeatedly in the subsequent proofs.

A.2 Auxiliary Lemmas

  • Two auxiliary lemmas are introduced for repeated use in the proofs.Source: §A.2 · p. 13

A.3 Proof of Proposition 1 and Eq. (8)

This subsection is labeled as the proof of Eq. (8).

A.3 Proof of Proposition 1 and Eq. (8)

  • The subsection identifies its content as the proof of Eq. (8).Source: §A.3 · p. 14

A.4 Proof of Proposition 2 and Corollaries 2.1 and 2.2

The appendix contains proofs of Corollaries 2.1 and 2.2, Propositions 4 and 5, and a derivation of the IIPS bias in Eq. (13).

A.4 Proof of Proposition 2 and Corollaries 2.1 and 2.2

A.5 Proofs of Propositions 3 and 4

A.6 Derivation of Eq. (13) and Proof of Proposition 5

  • The appendix derives the bias of IIPS in Eq. (13) and proves Proposition 5.Source: §A.6 · p. 18
Loading 2609.35034v1…