Many recommender systems such as for e-commerce and news platforms aim to provide users with rankings they are likely to interact with. Off-Policy Learning (OPL) of ranking policies enables us to learn new ranking policies using only historical logged data. However, ranking settings make OPL remarkably challenging because their action spaces consist of permutations of unique items, being extremely large. Existing methods primarily use either policy- or regression-based approaches. The policy-based approach, which typically uses importance-weighted policy gradients, can suffer from high variance due to large action spaces. The regression-based approach, on the other hand, estimates the expected reward using conventional machine learning methods, avoiding variance issues but potentially suffering from severe bias. To circumvent these issues of existing methods, we propose a new OPL method for ranking, named Ranking Policy Optimization via Top-k Policy Decomposition (R-POD), which combines the policy- and regression-based approaches in an effective fashion. Specifically, R-POD decomposes a ranking policy into a first-stage policy for selecting top-k actions and a second-stage policy for choosing the bottom actions given the top-k actions. It learns the first-stage policy using a new policy gradient estimator and the second-stage policy via the regression-based approach. This method can substantially reduce variance, since it applies importance weighting only to the top-k actions. We also demonstrate that our policy-gradient estimator for the first-stage policy is unbiased under a conditional pairwise correctness condition, which only requires that the expected reward differences of pairs of rankings sharing the same top-k actions can be estimated correctly.
Figures & tables
Figure 1. R-POD leverages the concept of top- k policy decomposition in Eq. ( 6 ) to learn better ranking policies offline.
Figure 2. The R-POD algorithm mixes policy- and regression-based approaches via its hyperparameter k . When k=L , R-POD reduces to the policy-based approach, while it reduces to the regression-based approach with k=0 .
Figure 3. Comparing the test policy values (normalized by R-POD (tuning)) of the OPL methods, with varying (a) training data sizes, (b) numbers of actions, (c) temperature parameters of the logging policy, and (d) extents of interactions.
Figure 4. Histograms of hyperparameter k selected by R-POD (best) and R-POD (tuning) over 100 simulations.
Yahoo! LETOR (DCG@3)
MSLR-WEB10K (DCG@5)
Logging Policy
Logging Policy
OPL methods
uniform
random forest
uniform
random forest
Reg-based
1.660 (0.154)
1.613 (0.100)
2.318 (0.237)
2.256 (0.269)
IPS-PG
1.568 (0.090)
1.648 (0.071)
1.885 (0.060)
2.016 (0.066)
RIPS-PG
1.576 (0.092)
1.625 (0.074)
2.043 (0.041)
2.078 (0.065)
IIPS-PG
1.602 (0.047)
1.571 (0.081)
2.240 (0.077)
2.227 (0.155)
Table 1. Comparison of the OPL methods on Yahoo! LETOR (DCG@3) and MSLR-WEB10K (DCG@5). f0(x,a) in the logging policy uses constant value (uniform) or random forest regression. Values outside and inside the parenthesis are the mean and the standard deviation based on 5 random seeds, respectively.
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, 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
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.