# Doubly-Robust Estimation for Correcting Position-Bias
in Click Feedback for Unbiased Learning to Rank

Harrie Oosterhuis  Radboud UniversityNijmegenThe Netherlands
<EMAIL_ADDRESS>
###### Abstract.

Clicks on rankings suffer from position-bias: generally items on lower ranks
are less likely to be examined – and thus clicked – by users, in spite of
their actual preferences between items. The prevalent approach to unbiased
click-based learning-to-rank (LTR) is based on counterfactual inverse-
propensity-scoring (IPS) estimation. In contrast with general reinforcement
learning, counterfactual doubly-robust (DR) estimation has not been applied to
click-based LTR in previous literature.

In this paper, we introduce a novel DR estimator that is the first DR approach
specifically designed for position-bias. The difficulty with position-bias is
that the treatment – user examination – is not directly observable in click
data. As a solution, our estimator uses the expected treatment per rank,
instead of the actual treatment that existing DR estimators use. Our novel DR
estimator has more robust unbiasedness conditions than the existing IPS
approach, and in addition, provides enormous decreases in variance: our
experimental results indicate it requires several orders of magnitude fewer
datapoints to converge at optimal performance. For the unbiased LTR field, our
DR estimator contributes both increases in state-of-the-art performance and
the most robust theoretical guarantees of all known LTR estimators.

Unbiased Learning to Rank; Counterfactual Learning; Position Bias

††journal: TOIS††journalyear: 2023††journalvolume: 0††journalnumber:
0††article: 0††publicationmonth: 0††doi: 10.1145/3569453††copyright: CC††ccs:
Information systems Learning to rank

##  1\. Introduction

The basis of recommender systems and search engines are ranking models that
aim to provide users with rankings that meet their preferences or help in
their search task (Liu, 2009). The performance of a ranking model is vitally
important to the quality of the user experience with a search or
recommendation system. Accordingly, the field of learning-to-rank (LTR)
concerns methods that optimize ranking models (Liu, 2009); click-based LTR
uses logged user interactions to supervise its optimization (Joachims, 2002).
However, clicks are biased indicators of user preference (Joachims et al.,
2017a; Radlinski et al., 2008) because there are many factors beside user
preference that influence click behavior. Most importantly, the rank at which
an item is displayed is known to have an enormous effect on whether it will be
clicked or not (Craswell et al., 2008). Generally, users do not consider all
the items that are presented in a ranking, and instead, are more likely to
examine items at the top of the ranking. Consequently, lower-ranked items are
less likely to be clicked by users, regardless of whether users actually
prefer these items (Joachims et al., 2017b). Therefore, clicks can be more
reflective of where an item was displayed during the gathering of data than
whether users prefer it. This form of bias is referred to as _position-bias_
(Wang et al., 2018a; Craswell et al., 2008; Agarwal et al., 2019c); it is
extremely prevalent in user clicks on rankings. Correspondingly, this has lead
to the introduction of unbiased LTR: methods for click-based optimization that
mitigate the effects of position-bias. Wang et al. (2016) and Joachims et al.
(2017b) proposed using IPS estimators (Horvitz and Thompson, 1952) to correct
for position-bias. By treating the examination probabilities as propensities,
IPS can estimate ranking metrics unbiasedly w.r.t. position-bias. This has
lead to the inception of the unbiased LTR field, in which IPS estimation has
remained the basis for most state-of-the-art methods (Oosterhuis and de Rijke,
2020, 2021a; Agarwal et al., 2019a, b; Vardasbi et al., 2020b). However,
variance is a large issue with IPS-based LTR and remains an obstacle for its
adoption in real-world applications (Oosterhuis and de Rijke, 2021a).

Outside of LTR, DR estimators are a widely used alternative for IPS estimation
(Kang et al., 2007; Robins et al., 1994), for instance, for optimization in
contextual bandit problems (Dudík et al., 2014). The DR estimator combines an
IPS estimate with the predictions of a regression model, such that it is
unbiased when per treatment either: the estimated propensity or the regression
model is accurate (Kang et al., 2007). Additionally, the DR estimator can also
bring large decreases in variance if the regression model is adequately
accurate (Dudík et al., 2014). Unfortunately, existing DR estimators are not
directly applicable to the unbiased LTR problem, since the treatment variable
– that indicates whether an item was examined or not – cannot be observed in
the data. This is the characteristic problem of position-biased clicks: when
an item is not clicked, we cannot determine whether the user chose not to
interact or the user did not examine it in the first place. Consequently, the
unbiased LTR field has not progressed beyond the usage of IPS estimation.

Our main contribution is the first DR estimator that is specifically designed
to perform unbiased LTR from position-biased click data. Instead of using the
actual treatment: user examination, which is unobservable in click data, our
novel estimator uses the expectation of treatment per rank to construct a
covariate instead. Similar to DR estimators for other tasks, it combines the
preference predictions of a regression model with IPS estimation. Unlike IPS
estimators which are only unbiased with accurate knowledge of the logging
policy, our DR estimator requires _either_ the correct logging policy
propensity _or_ an accurate regression estimate per item. As a result, our DR
estimator has less strict requirements for unbiasedness than IPS estimation.
Moreover, it can also provide enormous decreases in variance compared to IPS:
our experimental results indicate that the DR estimator requires several
orders of magnitude fewer datapoints to converge at optimal performance. In
all tested top-5 ranking scenarios, it needs less than $10^{6}$ logged
interactions to reach the performance that IPS reaches at $10^{9}$ logged
interactions. Additionally, when compared to other state-of-the-art methods DR
also provides better performance across all tested scenarios. Therefore, the
introduction of DR estimation for unbiased LTR contributes the first unbiased
LTR estimator that is provenly more robust than IPS, while also improving
state-of-the-art performance on benchmark unbiased LTR datasets.

###  1.1. Structure of the Paper

The remained of this work is structured as follows:

Section 2 discusses relevant existing work on click-based and unbiased LTR and
earlier methods that have applied DR estimation to clicks. Then Section 3
explains our LTR problem setting by describing our assumptions about user
behavior, how click data is logged and our LTR goal. Our background section is
divided in two parts: Section 4 provides background on counterfactual
estimation methods in general, not specific to LTR. These generic methods are
introduced so that we can later contrast them with LTR specific methods and
illustrate the adaptations that are required to deal with position-bias
specifically. Subsequently, Section 5 describes the existing IPS method that
is specifically designed for LTR and position-bias. Furthermore, it discusses
existing regression loss estimation and earlier DR estimation methods that
have been applied to clicks.

Our novel methods, the novel DR estimator designed to correct position-bias
and a novel cross-entropy loss estimator, are introduced in Section 6. Then
Section 7 details the experiments that were performed to evaluate our novel
method, the results of these experiments are presented and discussed in
Section 8. Finally, Section 9 provides a conclusion of this work, followed by
the appendices that provide extended proofs for the theoretical claims of the
work.

##  2\. Related Work

This section provides a brief overview of the existing literature in the
unbiased LTR field, in addition, relevant work on dealing with position-biased
clicks and existing methods that apply DR estimation to click data outside of
the LTR field are also discussed.

Optimizing ranking models based on click-data is a well-established concept
(Joachims, 2002). Early methods took an online dueling-bandit approach (Yue
and Joachims, 2009; Schuth et al., 2016) and later an online pairwise approach
(Oosterhuis and de Rijke, 2018). The first LTR method with theoretical
guarantees of unbiasedness was introduced by Wang et al. (2016) and then
generalized by Joachims et al. (2017b). They assume the probability that a
user examines an item only depends on the rank at which it is displayed and
that clicks only occur on examined items (Wang et al., 2018a; Craswell et al.,
2008). Then using counterfactual IPS estimation they correct for the selection
bias imposed by the examination probabilities. The introduction of this
approach launched the unbiased LTR field: Agarwal et al. (2019a) expanded the
approach for optimizing neural networks. Oosterhuis and de Rijke (2020)
generalized the approach to also correct for the _item-selection-bias_ in
top-$k$ ranking settings by basing the propensities on a stochastic logging
policy. Agarwal et al. (2019b) showed that user behavior shows an additional
_trust-bias_ : increased incorrect clicks at higher ranks (Joachims et al.,
2017a), Vardasbi et al. (2020b) extended the IPS estimator with affine
corrections to correct for this trust-bias. Singh and Joachims (2019) use IPS
to optimize for a fair distribution of exposure over items. Jagerman et al.
(2020) consider safe model deployments by bounding model performance.
Oosterhuis and de Rijke (2021a) introduced a generalization of the top-$k$ and
affine estimators that considers the possibility that the logging policy is
updated during the gathering of data. Wang et al. (2021) proposed a ratio-
propensity-scoring (RPS) estimator that weights pairs of clicked and non-
clicked items by their ratio between the propensities. RPS is an extension of
IPS that introduces bias but also reduces variance.

In contrast with the rest of the field, recent work has proposed some methods
that do not rely on IPS to the field. Zhuang et al. (2021) and Yan et al.
(2022) fit predictive models to observed click data that explicitly factorizes
relevance and bias factors, while they report promising real-world results,
their methods do not provide strong theoretical guarantees w.r.t.
unbiasedness. Ovaisi et al. (2020) propose an adaptation of Heckman’s two-
stage method. Besides these exceptions and to the best of our knowledge, all
methods in the unbiased LTR field are based on IPS.

Interestingly, methods for dealing with position-biased clicks have also been
developed outside of the unbiased LTR field. Komiyama et al. (2015) and Lagrée
et al. (2016) propose bandit algorithms that use similar IPS estimators for
serving ads in multiple on-screen positions at once. Furthermore, Li et al.
(2018) also propose IPS estimators for the unbiased click-based evaluation of
ranking models. This further evidences the widespread usage of IPS estimation
for correcting position-biased clicks.

Nevertheless, there is previous work that has applied DR estimators to
position-biased clicks: Saito (2020) proposed a DR estimator for post-click
conversions that estimates how users treat an item after clicking it. Kiyohara
et al. (2022) designed a DR estimator for policy-evaluation under cascading
click behavior (Vardasbi et al., 2020a). Lastly, Yuan et al. (2020) introduced
a DR estimator for click-through-rate (CTR) prediction on advertisements
placements. Section 5.3 will discuss these methods in a bit more depth, and
how they differ from the prevalent IPS approach to unbiased LTR and our
proposed DR estimator. Important for our current discussion is that each of
these methods tackles a different problem setting than the LTR problem setting
in this work. Moreover, the latter two DR estimators use corrections based on
action propensities, similar to generic counterfactual estimation, and in
stark contrast with the examination propensities of unbiased LTR. Finally,
these works focus on policy evaluation instead of LTR, thus it appears that
the effectiveness of DR for ranking model optimization is currently still
unknown to the field.

##  3\. Problem Definition

This section describes the assumptions underlying the theory of this paper and
details our exact problem setting. Specifically, it introduces the assumed
mathematical model by which clicks are generated, the metric we aim to
optimize, and notation to describe logged data.

###  3.1. User Behavior Assumptions

This paper assumes that the probability of a click depends on the user
preference w.r.t. item $d$ and the position (also called rank)
$k\in\\{1,2,\ldots,K\\}$ at which $d$ is displayed. Let $R_{d}=P(R=1\mid d)$
be the probability that a user prefers item $d$ and for each $k$ let
$\alpha_{k}\in[0,1]$ and $\beta_{k}\in[0,1]$ such that
$\alpha_{k}+\beta_{k}\in[0,1]$, the probability of $d$ receiving a click
$C\in\\{0,1\\}$ when displayed at position $k$ is:

(1) $\displaystyle P(C=1\mid d,k)$ $\displaystyle=\alpha_{k}P(R=1\mid
d)+\beta_{k}=\alpha_{k}R_{d}+\beta_{k}.$

This assumption has been derived (Vardasbi et al., 2020b) from a more
interpretable user-model proposed by Agarwal et al. (2019b). Their model is
based on the examination assumption (Richardson et al., 2007): users first
examine an item before they interact with it, i.e. let $O\in\\{0,1\\}$
indicate examination then $O=0\rightarrow C=0$. Additionally, they also
incorporate the concept of trust-bias: users are more likely to click against
their preferences on higher ranks because of their _trust_ in the ranking
model. This can be modelled by having the probability of a click conditioned
on examination vary over $k$:

(2) $\begin{split}\epsilon_{k}^{+}&=P(C=1\mid R=1,O=1,k),\\\
\epsilon_{k}^{-}&=P(C=1\mid R=0,O=1,k).\end{split}$

The proposed user model results in the following click probability:

(3) $P(C=1\mid d,k)=P(O=1\mid
k)(\epsilon_{k}^{+}R_{d}+\epsilon_{k}^{-}(1-R_{d})),$

by comparing Eq. 1 and 3 we see that:

(4) $\alpha_{k}=P(O=1\mid
k)(\epsilon_{k}^{+}-\epsilon_{k}^{-}),\qquad\beta_{k}=P(O=1\mid
k)\epsilon_{k}^{-}.$

Agarwal et al. (2019b) provide empirical results that suggest this user-model
is more accurate than the previous model that ignores the trust-bias effect:
$\forall k,\;\;\beta_{k}=0$ (Wang et al., 2016; Joachims et al., 2017b; Wang
et al., 2018a). Since the assumption in Eq. 1 is true in both models, our work
is applicable to most settings in earlier unbiased LTR work (Wang et al.,
2016; Joachims et al., 2017b; Agarwal et al., 2019b; Vardasbi et al., 2020b;
Oosterhuis and de Rijke, 2020; Singh and Joachims, 2019; Jagerman et al.,
2020; Oosterhuis and de Rijke, 2021a; Ovaisi et al., 2020; Wang et al., 2021).

###  3.2. Definition of the LTR Goal

The goal of our ranking task is to maximize the probability that a user will
click on something they prefer. Let $\pi$ be the ranking policy to optimize,
with $\pi(k\mid d)$ indicating the probability that $\pi$ places $d$ at
position $k$ and let $y$ indicate a ranking of size $K$:
$y=[y_{1},y_{2},\ldots,y_{K}]$, lastly, let $D=\\{d_{1},d_{2},\ldots,d_{K}\\}$
be the collection of items to be ranked. Most ranking metrics are a weighted
sum of item relevances, where the weights $\omega_{k}$ depend on the item
positions:

(5)
$\mathcal{R}(\pi)=\mathbb{E}_{y\sim\pi}\left[\sum^{K}_{k=1}\omega_{k}R_{y_{k}}\right]=\sum_{d\in
D}R_{d}\sum^{K}_{k=1}\pi(k\mid d)\omega_{k}.$

DCG (Järvelin and Kekäläinen, 2002) is a very traditional ranking metric:
$\omega_{k}^{\text{DCG}}=\log_{2}(k+1)^{-1}$, however, discounted cumulative
gain (DCG) has no clear interpretation in our assumed user model. In contrast,
we argue that our metric should actually be motivated by our user behavior
assumptions, accordingly, this work will use the weights:
$\omega_{k}=(\alpha_{k}+\beta_{k})$. This choice results in an easily
interpreted metric; for brevity of notation, we first introduce the expected
position weight per item:

(6)
$\omega_{d}=\mathbb{E}_{y\sim\pi}\left[\omega_{k(d)}\right]=\mathbb{E}_{y\sim\pi}\left[\alpha_{k(d)}+\beta_{k(d)}\right]=\sum_{k=1}^{K}\pi(k\mid
d)(\alpha_{k}+\beta_{k}),$

using Eq. 1, our ranking metric can then be formulated as:

(7) $\begin{split}\mathcal{R}(\pi)&=\sum_{d\in D}\omega_{d}R_{d}=\sum_{d\in
D}P(R=1\,|\ d)\sum_{k=1}^{K}\pi(k\,|\,d)(\alpha_{k}+\beta_{k})\\\ &=\sum_{d\in
D}\mathbb{E}_{y\sim\pi}\left[P(C=1,R=1\,|\ d,k)\right]=\sum_{d\in
D}P(C=1,R=1\,|\ d).\end{split}$

This formulation clearly reveals that our chosen metric directly corresponds
to the expected number of items that are both clicked and preferred in our
assumed user behavior model. Hence, we will call this metric: the number of
expected clicks on preferred items, abbreviated to ECP.

Given a ranking metric, the LTR field provides several optimization methods to
train ranking models. A popular approach for deterministic ranking models is
to optimize a differentiable lower bound on the ranking metric (Wang et al.,
2018b; Burges, 2010). For probabilistic ranking models, a simple sampled-
approximation of the policy-gradient can be applied (Williams, 1992).
Alternatively, recent methods provide more efficient approximation methods
specifically designed for the LTR problem (Oosterhuis, 2021; Ustimenko and
Prokhorenkova, 2020).

Finally, we note that our main contributions work with any choice of weights
$\omega_{k}$ and are therefore equally applicable to most traditional LTR
metrics. Furthermore, for the sake of simplicity and brevity and without loss
of generalization, our notation and our defined goal are limited to a single
query or ranking context. We refer to previous work by Joachims et al. (2017b)
and Oosterhuis and de Rijke (2021a) as examples of how straightforward it is
to expand these to expectations over multiple queries or contexts.

###  3.3. Historically Logged Click Data

Lastly, in the unbiased LTR setting, optimization is performed on historically
logged click data. This means a logging policy $\pi_{0}$ was used to show
rankings to users in order to collect the resulting clicks. We will assume the
data contains $N$ rankings that were sampled from $\pi_{0}$ and displayed to
users, where $y_{i}$ is the $i$th ranking and $c_{i}(d)\in\\{0,1\\}$ indicates
whether $d$ was clicked when $y_{i}$ was displayed. The bias parameters
$\alpha_{k}$ and $\beta_{k}$ have to be estimated from user behavior, we will
use $\hat{\alpha}_{k}$ and $\hat{\beta}_{k}$ to denote the estimated values.
To keep our notation brief, we will use the following to denote that all the
estimated bias parameters are accurate:

(8) $\begin{split}\hat{\alpha}=\alpha&\longleftrightarrow(\forall
k\in\\{1,2,\ldots,K\\},\;\hat{\alpha}_{k}=\alpha_{k}),\\\
\hat{\beta}=\beta&\longleftrightarrow(\forall
k\in\\{1,2,\ldots,K\\},\;\hat{\beta}_{k}=\beta_{k}).\end{split}$

We will investigate both the scenarios where the $\alpha$ and $\beta$ bias
parameters are known from previous experiments (Agarwal et al., 2019b; Fang et
al., 2019; Wang et al., 2018a) and where they still have to be estimated.
Similarly, the exact distribution of the logging policy $\pi_{0}$ may also
have to be estimated, the following denotes that the estimated distribution
$\hat{\pi}_{0}$ for item $d$ is accurate:

(9) $\hat{\pi}_{0}(d)=\pi_{0}(d)\longleftrightarrow\big{(}\forall
k\in\\{1,2,\ldots,K\\},\;\hat{\pi}_{0}(k\,|\,d)=\pi_{0}(k\,|\,d)\big{)}.$

To summarize, our goal is to maximize $\mathcal{R}(\pi)$ based on click data
gathered using $\pi_{0}$ from the position-biased click model in Eq. 1.

##  4\. Background: Applying Generic Counterfactual Estimation to Click-
Through-Rates

This section will give an overview of counterfactual estimation for generic
reinforcement learning (Dudík et al., 2014; Kang et al., 2007; Sutton et al.,
1998), its purpose is two-fold:  (i) to illustrate why it is not effective for
the LTR problem; and  (ii) to contrast the generic estimators with the
existing estimators for LTR and our novel estimators.  While it appears that
the field is aware that generic counterfactual estimation is not a practical
solution to LTR (Saito and Joachims, 2021; Kiyohara et al., 2022; Joachims et
al., 2017b), to the best of our knowledge, previous published research has not
gone in depth on the reasons for this ineffectiveness.

###  4.1. The Generic Estimation Goal

The first issue between the LTR problem and generic counterfactual estimation
is that the latter assumes that the rewards for the actions performed by the
logging policy are directly observed, as is the case for standard
reinforcement learning tasks (Dudík et al., 2014; Sutton et al., 1998).
However, in the LTR problem, clicks are observed instead of the relevances
$R_{d}$ on which metrics are based. Consequently, for this section, we will
restrict ourselves to estimating CTR instead, luckily this task is similar
enough to the LTR problem for our discussion. Let $y[k]$ indicate the $k$th
item in ranking $y$, under our assumed click model, the CTR of a policy $\pi$
is:

(10)
$\text{CTR}(\pi)=\sum_{y:\pi(y)>0}\pi(y)\sum_{k=1}^{K}(\alpha_{k}R_{y[k]}+\beta_{k}).$

The goal in this section is thus to estimate $\text{CTR}(\pi)$ for any given
policy $\pi$ using data collected by a logging policy $\pi_{0}$. Importantly,
to be effective at optimization, the estimation process should work for any
possible $\pi$ in the model space.

###  4.2. Generic Inverse-Propensity-Scoring Estimation

Standard inverse-propensity-scoring (IPS) estimation corrects for the mismatch
between $\pi$ and $\pi_{0}$ by reweighting the observed action inversely
w.r.t. their estimated propensity: the probability that $\pi_{0}$ takes this
observation (Dudík et al., 2014). In our case, an action is a ranking $y$ and
its estimated propensity is $\hat{\pi}_{0}(y)$. Applying standard IPS
estimation to the LTR task results in the following generic IPS estimator:

(11)
$\widehat{\mathcal{R}}_{\text{G-IPS}}(\pi)=\frac{1}{N}\sum_{i=1}^{N}\underbrace{\frac{\pi(y_{i})}{\hat{\pi}_{0}(y_{i})}}_{\text{IPS
weight}}\sum_{k=1}^{K}\underbrace{c_{i}(y_{i}[k])}_{\text{observed click}}.$

The IPS weight aims to correct for the difference in action probability
between $\pi_{0}$ and $\pi$, e.g. if an action is underrepresented in the data
because $\pi_{0}(y)<\pi(y)$ then IPS will compensate by giving more weight to
this action as: $\pi(y)/\hat{\pi}_{0}(y)>1$. To understand when this approach
can provide unbiased estimation, we first look at its expected value:

(12)
$\mathbb{E}_{c,y\sim\pi_{0}}\left[\widehat{\mathcal{R}}_{\text{G-IPS}}(\pi)\right]=\sum_{y:\pi_{0}(y)>0}\pi(y)\underbrace{\frac{\pi_{0}(y)}{\hat{\pi}_{0}(y)}}_{\text{ratio
between estimated and real
propensity}}\sum_{k=1}^{K}(\alpha_{k}R_{y[k]}+\beta_{k}).$

The result is very similar to the formula for CTR (Eq. 11) except for the
ratio between the estimated and real propensity. Clearly, for unbiasedness
this ratio must be equal to one, i.e. the estimated propensity needs to be
correct, additionally, each action that $\pi$ may take must have a positive
propensity from $\pi_{0}$:

(13) $\Big{(}\forall
y,\;\pi(y)>0\rightarrow\underbrace{\big{(}\pi_{0}(y)>0\land\hat{\pi}_{0}(y)=\pi_{0}(y)\big{)}}_{\text{estimated
propensity is correct and
positive}}\Big{)}\rightarrow\mathbb{E}_{c,y\sim\pi_{0}}\left[\widehat{\mathcal{R}}_{\text{G-IPS}}(\pi)\right]=\text{CTR}(\pi).$

Thus unbiased estimation via generic IPS is possible, however, the
requirements are practically infeasible for any large ranking problem due to
its enormous action space. Importantly, for unbiasedness, $\pi_{0}$ has to
give a non-zero probability to each action $\pi$ may take, but data is often
collected without knowledge of what $\pi$ will be evaluated (or reused for
many different policies). Moreover, when using IPS for unbiased optimization
it should be unbiased for any possible $\pi$ in the policy space that
optimization is performed over. In practice, this means that the number of
possible rankings is enormous and each should get a non-zero probability by
$\pi_{0}$, which translates to $\pi_{0}$ giving a positive probability to
$K!\binom{|D|}{K}$ rankings. This is quite undesirable since the user
experience is likely to suffer under such a random policy, but moreover, it
also brings serious variance problems. In particular, when we consider the
variance of the generic IPS estimator, we see that small $\hat{\pi}_{0}(y)$
propensities increase variance by a massive degree:

(14)
$\mathbb{V}\left[\widehat{\mathcal{R}}_{\text{G-IPS}}(\pi)\right]=\mathbb{E}_{y\sim\pi_{0}}\bigg{[}\overbrace{\frac{\pi(y)^{2}}{\hat{\pi}_{0}(y)^{2}}}^{\text{multiplier
from IPS
weight}}\underbrace{\mathbb{V}\bigg{[}\sum_{k=1}^{K}c(y[k])\bigg{]}}_{\text{variance
from clicks on ranking}}\bigg{]}.$

Thus, to summarize, to apply generic IPS to LTR unbiasedly, all rankings
require a positive propensity, but due to the enormously large number of
rankings this leads to extremely small propensity values which lead to
enormous variance. As a result, generic IPS is not a practical solution for
unbiased low-variance LTR and has been widely avoided in practice (Kiyohara et
al., 2022). Section 5.1 will describe the IPS approach specifically designed
for LTR that has much more feasible unbiasedness requirements.

###  4.3. The Generic Direct Method

Before we continue to LTR specific methods, we will describe the direct-method
(DM) and generic doubly-robust (DR) estimation, in order to compare them with
our novel estimator later. First, the direct method uses regression estimates
from a regression model to estimate policy performance (Dudík et al., 2014).
Let $\hat{R}_{d}$ indicate a regression estimate of $R_{d}$, the generic DM
estimator is then:

(15)
$\widehat{\mathcal{R}}_{\text{G-DM}}(\pi)=\sum_{y:\pi(y)>0}\pi(y)\sum_{k=1}^{K}\underbrace{\hat{\alpha}_{k}\hat{R}_{y[k]}+\hat{\beta}_{k}}_{\text{predicted
click prob.}}.$

Clearly, DM is unbiased when the regression estimates are correct for all
rankings that $\pi$ may show:

(16) $\Big{(}\forall
y,\;\pi(y)>0\rightarrow\underbrace{\left(\hat{\alpha}=\alpha\land\hat{\beta}=\beta\land\forall
k,\;\hat{R}_{y[k]}=R_{y[k]}\right)}_{\text{predicted click probabilities are
correct}}\Big{)}\longrightarrow\mathbb{E}_{c,y\sim\pi_{0}}\left[\widehat{\mathcal{R}}_{\text{G-DM}}(\pi)\right]=\text{CTR}(\pi).$

However, this is not a very useful requirement in practice, since solving the
regression problem is arguably just as difficult as the subsequent LTR
problem. Nonetheless, its unbiasedness requirements are very different than
those for IPS, a benefit of DR is that it combines both requirements
advantageously.

###  4.4. Generic Doubly Robust Estimation

Besides DM and IPS, DR estimation makes use of a covariate (CV), that aims to
have a large covariance with IPS estimation but the same expected value as DM.
We will call this the generic CV:

(17)
$\widehat{\mathcal{R}}_{\text{G-CV}}(\pi)=\frac{1}{N}\sum_{i=1}^{N}\underbrace{\frac{\pi(y_{i})}{\hat{\pi}_{0}(y_{i})}}_{\text{IPS
weight}}\sum_{k=1}^{K}\underbrace{\hat{\alpha}_{k}\hat{R}_{y[k]}+\hat{\beta}_{k}}_{\text{predicted
click prob.}}.$

CV makes use of the actions sampled by $\pi_{0}$, allowing it to have a high
covariance with IPS, but uses predicted click probabilities instead of using
the actual clicks, enabling it to have the same expected value as DM.
Importantly, when IPS is unbiased, i.e. when the estimated propensities are
correct, CV is also an unbiased estimate of DM:

(18) $\Big{(}\forall
y,\;\pi(y)>0\rightarrow\underbrace{\big{(}\pi_{0}(y)>0\land\hat{\pi}_{0}(y)=\pi_{0}(y)\big{)}}_{\text{estimated
propensity is correct and
positive}}\Big{)}\rightarrow\mathbb{E}_{y\sim\pi_{0}}\left[\widehat{\mathcal{R}}_{\text{G-CV}}(\pi)\right]=\widehat{\mathcal{R}}_{\text{G-DM}}(\pi).$

The DR estimator is a combination of the above three estimators (Dudík et al.,
2014; Kang et al., 2007; Robins et al., 1994):

(19)
$\begin{split}\widehat{\mathcal{R}}_{\text{G-DR}}(\pi)&=\widehat{\mathcal{R}}_{\text{G-DM}}(\pi)+\widehat{\mathcal{R}}_{\text{G-IPS}}(\pi)-\widehat{\mathcal{R}}_{\text{G-CV}}(\pi)\\\
&=\underbrace{\widehat{\mathcal{R}}_{\text{G-DM}}(\pi)}_{\text{predicted model
performance}}+\frac{1}{N}\sum_{i=1}^{N}\underbrace{\frac{\pi(y_{i})}{\pi_{0}(y_{i})}}_{\text{IPS
weight}}\sum_{k=1}^{K}\overbrace{\Big{(}c_{i}(y_{i}[k])-\hat{\alpha}_{k}\hat{R}_{y[k]}-\hat{\beta}_{k}\Big{)}}^{\text{diff.
between observed click and predicted click prob.}}.\end{split}$

The DR starts with regression-based estimate of DM then for each logged
ranking it adds the difference between the observed clicks and the predicted
clicks. In other words, DR uses DM as a baseline and adds an IPS estimate of
the difference between the regression model and the actual clicks.

The first advantage of DR estimation are its unbiasedness requirements. It has
the following bias w.r.t. CTR:

$\displaystyle\mathbb{E}\left[\widehat{\mathcal{R}}_{\text{G-DR}}(\pi)\right]-CTR(\pi)$
$\displaystyle=\sum_{y\,:\,\pi(y)>0}\pi(y)\sum_{k=1}^{K}\left(\frac{\pi_{0}(y)}{\hat{\pi}_{0}(y)}-1\right)\left(\alpha_{k}R_{y[k]}+\beta_{k}\right)+\left(1-\frac{\pi_{0}(y)}{\hat{\pi}_{0}(y)}\right)\left(\hat{\alpha}_{k}\hat{R}_{y[k]}+\hat{\beta}_{k}\right)$
(20)
$\displaystyle=\sum_{y\,:\,\pi(y)>0}\pi(y)\underbrace{\left(\frac{\pi_{0}(y)}{\hat{\pi}_{0}(y)}-1\right)}_{\text{error
in
propensity}}\sum_{k=1}^{K}\underbrace{\left(\alpha_{k}R_{y[k]}+\beta_{k}-\hat{\alpha}_{k}\hat{R}_{y[k]}-\hat{\beta}_{k}\right)}_{\text{error
in click prob. prediction}}.$

As we can see the bias of DR is a summation over rankings, where per ranking
the error in propensity is multiplied with the error in predicted click
probability. Due to this product, only one of the two errors has to be zero
per ranking for the total bias to be zero. In other words, DR is unbiased when
for each ranking either the propensity or the predicted click probabilities
are correct:

(21) $\begin{split}&\big{(}\forall
y,\;\pi(y)>0\rightarrow\big{(}\overbrace{\big{(}\pi_{0}(y)>0\land\hat{\pi}_{0}(y)=\pi_{0}(y)\big{)}}^{\text{propensity
is correct and
positive}}\lor\overbrace{\big{(}\hat{\alpha}=\alpha\land\hat{\beta}=\beta\land\forall
k,\;\hat{R}_{y[k]}=R_{y[k]}\big{)}}^{\text{predicted click probabilities are
correct}}\big{)}\big{)}\\\ &\hskip
227.62204pt\longrightarrow\mathbb{E}_{c,y\sim\pi_{0}}\left[\widehat{\mathcal{R}}_{\text{G-DR}}(\pi)\right]=\text{CTR}(\pi).\end{split}$

As a result, if either DM or IPS is unbiased then DR is unbiased, furthermore,
it can potentially be unbiased when neither DM or IPS are. In addition, to the
beneficial unbiasedness requirements, DR can also allow for reduced variance
if there is a positive covariance between IPS and CV:

(22)
$\mathds{V}\left[\widehat{\mathcal{R}}_{\text{G-DR}}(\pi)\right]=\mathds{V}\left[\widehat{\mathcal{R}}_{\text{G-IPS}}(\pi)\right]+\mathds{V}\left[\widehat{\mathcal{R}}_{\text{G-CV}}(\pi)\right]-2\mathbb{C}\text{ov}\left(\widehat{\mathcal{R}}_{\text{G-IPS}}(\pi),\widehat{\mathcal{R}}_{\text{G-CV}}(\pi)\right).$

In practice, this means that somewhat accurate regression estimates can
provide a decrease in variance over IPS. Nevertheless, this decrease is not
enough to overcome the variance problems that stem from the small propensities
that are involved in LTR. Consequently, state-of-the-art unbiased LTR does not
apply standard IPS and DR (Oosterhuis and de Rijke, 2021a; Ai et al., 2021).

##  5\. Background: Counterfactual Estimation for Unbiased Learning-to-Rank

While Section 4 covers the standard counterfactual estimation techniques and
why they are ineffective for the LTR problem, this section describes the
existing IPS estimator that is specifically designed for LTR and discuss
previous work that has applied DR estimation to click data.

###  5.1. Inverse-Propensity-Scoring in Unbiased LTR

As discussed in Section 2, the main approach in state-of-the-art unbiased LTR
work is based on inverse-propensity-scoring (IPS) estimation (Horvitz and
Thompson, 1952). Under the affine click model in Eq. 1, the propensities are
not the probability of observation, as in the earliest unbiased LTR work (Wang
et al., 2016; Joachims et al., 2017b), but the expected correlation between
the click probability and the user preference for an item $d$ under $\pi_{0}$
(Vardasbi et al., 2020b; Oosterhuis and de Rijke, 2021a):

(23)
$\rho_{d}=\mathbb{E}_{y\sim\pi_{0}}\left[\alpha_{k(d)}\right]=\sum_{k=1}^{K}\pi_{0}(k\mid
d)\alpha_{k},$

where $\pi_{0}(k\mid d)$ indicates the probability that $\pi_{0}$ places $d$
at position $k$. Because $\alpha$ are $\beta$ may be unknown, we use the
following estimated values:

(24)
$\begin{split}\hat{\rho}_{d}&=\max\left(\mathbb{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right],\,\tau\right)=\max\left(\sum_{k=1}^{K}\hat{\pi}_{0}(k\mid
d)\hat{\alpha}_{k},\,\tau\right),\\\ \hat{\omega}_{d}&=\sum_{k=1}^{K}\pi(k\mid
d)\left(\hat{\alpha}_{k}+\hat{\beta}_{k}\right),\end{split}$

where the clipping parameter $\tau\in(0,1]$ prevents small $\hat{\rho}_{d}$
values and is applied for variance reduction (Joachims et al., 2017b; Strehl
et al., 2010). The state-of-the-art IPS estimator introduced by Oosterhuis and
de Rijke (2021a) first corrects each (non-)click with $\hat{\beta}_{k_{i}(d)}$
– the $\hat{\beta}$ value for the position where the click took place – to
correct for clicks in spite of preference (trust-bias), and then inversely
weights the result by $\hat{\rho}_{d}$ to correct for the correlation between
the user preference and the click probability (position-bias and item-
selection-bias (Oosterhuis and de Rijke, 2020)):

(25)
$\widehat{\mathcal{R}}_{\text{IPS}}(\pi)=\frac{1}{N}\sum_{i=1}^{N}\sum_{d\in
D}\overbrace{\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}}^{\text{IPS
weight}}\underbrace{\left(c_{i}(d)-\hat{\beta}_{k_{i}(d)}\right)}_{\text{click
corrected for trust-bias}},$

where $k_{i}(d)$ indicates the position of $d$ in the $i$th ranking.

The main difference between the generic IPS estimation (Eq. 11) and the LTR
IPS estimator (Eq. 25) is that the former bases its corrections on the
differences between the action probabilities of $\pi$ and $\pi_{0}$, while the
latter uses the correlation between clicks and relevance under $\pi_{0}$. Thus
while both use the behavior of the logging policy $\pi_{0}$, the LTR IPS
estimator uses the assumed click model of Eq. 1 as well. While the reliance on
the click model makes the estimator more effective, it also makes the
estimator specifically designed for this click behavior. The remainder of this
section discusses that, due to this specific design, the theoretical
properties of the LTR IPS estimator are clearly preferable over those of
generic IPS estimation applied to the LTR problem.

To start, the IPS estimator has the following bias:

(26)
$\mathds{E}_{c,y\sim\pi_{0}}\left[\hat{\mathcal{R}}_{\text{IPS}}(\pi)\right]-\mathcal{R}(\pi)=\sum_{d\in
D}\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}\bigg{(}\underbrace{\left(\rho_{d}-\hat{\rho}_{d}\frac{\omega_{d}}{\hat{\omega}_{d}}\right)}_{\text{error
from $\hat{\alpha}$, $\hat{\beta}$ and
$\hat{\pi}$}}R_{d}+\underbrace{\mathds{E}_{y\sim\pi_{0}}\left[\beta_{k(d)}-\hat{\beta}_{k(d)}\right]}_{\text{error
from $\hat{\beta}$}}\bigg{)}.$

Appendix A provides a derivation of its bias, it also proves that the IPS
estimator is unbiased when both the bias parameters and the logging policy
distribution are correctly estimated and clipping has no effect (Joachims et
al., 2017b; Vardasbi et al., 2020b):

(27) $\overbrace{\big{(}\hat{\alpha}=\alpha\land\hat{\beta}=\beta}^{\text{pos.
bias correctly estimated}}\land\underbrace{\left(\forall d\in
D,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\rho_{d}\geq\tau\right)\big{)}}_{\text{$\hat{\pi}_{0}$
is correctly estimated and clipping has no
effect}}\longrightarrow\mathbb{E}_{c,y\sim\pi_{0}}\big{[}\widehat{\mathcal{R}}_{\text{IPS}}(\pi)\big{]}=\mathcal{R}(\pi).$

Conversely, IPS is biased when clipping does have an effect, even if the bias
parameters and logging policy distribution are correctly estimated.

Importantly, these unbiasedness requirements are much more feasible than those
for the generic IPS estimator (Eq. 21); where the generic IPS estimator
requires each ranking to have a positive probability ($\forall
y,\;\pi_{0}(y)>0$) of being displayed during logging, the LTR IPS estimator
requires each item to have a propensity greater than $\tau$ ($\forall
d,\;\rho_{d}\geq\tau$). In other words, the correlation between clicks and
relevances should be greater than $\tau$, this is even feasible under a
deterministic logging policy that always displays the same single ranking if
all items are displayed at once (Joachims et al., 2017b; Oosterhuis and de
Rijke, 2020). However, the IPS estimator does need accurate estimate of the
bias parameters $\hat{\alpha}$ and $\hat{\beta}$ in addition to an accurate
estimate of the logging policy $\hat{\pi}_{0}$, but previous work indicates
that this is actually doable in practice (Joachims et al., 2017b; Wang et al.,
2016, 2018a; Agarwal et al., 2019c). In summary, compared to generic IPS
estimation, the IPS estimator for LTR has replaced infeasible requirements on
the logging policy with attainable requirements on bias estimation.

The variance of the IPS estimator can be decomposed in the following parts:

(28)
$\mathds{V}\big{[}\widehat{\mathcal{R}}_{\text{IPS}}(\pi)\big{]}=\frac{1}{N}\sum_{d\in
D}\overbrace{\frac{\hat{\omega}_{d}^{2}}{\hat{\rho}_{d}^{2}}}^{\text{multiplier
from IPS weight}}\big{(}\underbrace{\mathds{V}\big{[}c(d)\big{]}}_{\text{var.
from
click}}+\overbrace{\mathds{V}\big{[}\hat{\beta}_{k(d)}\big{]}}^{\text{var.
from trust-bias
correction}}-\underbrace{2\mathds{C}\text{ov}\big{[}c(d),\hat{\beta}_{k(d)}\big{]}}_{\text{cov.
between click and correction}}\big{)}.$

We see how clipping prevents extremely large values for the variance
multiplier from the IPS weight by preventing small $\hat{\rho}_{d}$ values and
can thereby greatly reduce variance (Joachims et al., 2017b; Strehl et al.,
2010). Importantly, the reduction in variance is often much greater than the
increase in bias, making this an attractive trade-off that has been widely
adopted by the unbiased LTR field (Agarwal et al., 2019a; Oosterhuis and de
Rijke, 2020). There is currently no known method for variance reduction in
IPS-based position-bias correction that does not introduce bias, and thus, in
practice unbiased LTR methods are actually often applied in a biased
manner111Oosterhuis and de Rijke (2021a) apply unbiased LTR in an online
fashion to reduce variance, but this solution does not apply to our problem
setting..

###  5.2. Existing Cross-Entropy Loss Estimation

As discussed, DM requires an accurate regression model to be unbiased or
effective. In the ideal situation, one may optimize a regression model for
estimating relevance using the cross-entropy loss:

(29) $\mathcal{L}(\hat{R})=-\sum_{d\in
D}R_{d}\log(\hat{R}_{d})+(1-R_{d})\log(1-\hat{R}_{d}).$

However, this loss cannot be computed from the click-data since $R_{d}$ cannot
be observed. Luckily, Bekker et al. (2019) have introduced an estimator that
can be applied to position-biased clicks:

(30)
$\widehat{\mathcal{L}}^{\prime}(\hat{R})=-\frac{1}{N}\sum_{i=1}^{N}\sum_{d\in
D}\left(\frac{c_{i}(d)}{\hat{\rho}_{d}}\log(\hat{R}_{d})+\left(1-\frac{c_{i}(d)}{\hat{\rho}_{d}}\right)\log(1-\hat{R}_{d})\right).$

Saito et al. (2020) showed that this estimator is effective for recommendation
tasks on position-biased click data. $\widehat{\mathcal{L}}^{\prime}$ is
unbiased (Bekker et al., 2019; Saito et al., 2020) when there is no trust-
bias, propensities are accurate and clipping has no effect:

(31) $\underbrace{\big{(}(\forall k,\,\beta_{k}=0)}_{\text{no trust-
bias}}\land\overbrace{\hat{\alpha}=\alpha}^{\text{pos. bias correctly
estimated}}\land\underbrace{\left(\forall d\in
D,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\rho_{d}\geq\tau\right)\big{)}}_{\text{$\hat{\pi}$
is correctly estimated and clipping has no
effect}}\longrightarrow\mathbb{E}_{c,y\sim\pi_{0}}\big{[}\widehat{\mathcal{L}}^{\prime}(\hat{R})\big{]}=\mathcal{L}(\hat{R}).$

In Section 6.5, we propose a novel variation on this estimator that can also
correct for trust-bias and that treats non-displayed items in a more intuitive
way.

###  5.3. Existing Doubly-Robust Estimation for Logged Click Data

Our discussion of generic counterfactual estimation in Section 4 concluded
with DR estimation and the advantageous properties it can have over IPS and DM
(Kang et al., 2007; Robins et al., 1994). Given that the current state-of-the-
art in LTR is based on IPS, it seems very promising to apply DR to unbiased
LTR. Unfortunately, at first glance it seems DR is inapplicable to the LTR
problem, since treatment is the examination of the user and we cannot directly
observe whether a user has examined a non-clicked item or not. Because DR
estimation balances IPS and regression estimates unbiasedly using the
knowledge of treatment in the data, e.g. which actions where taken (Dudík et
al., 2014) (cf. Eq. 19), it appears this characteristic problem of position-
biased clicks makes existing DR estimation inapplicable.

However, as discussed in Section 4, this is not a problem for generic
counterfactual estimators for CTR estimation from logged click data.
Accordingly, previous work that has applied DR estimation to clicks has taken
the generic approach with corrections based on purely based on action
propensities. For instance, Yuan et al. (2020) use IPS and DR estimators for
CTR prediction on advertisements that are presented in different display
positions. Their IPS weights are based on the difference in action
probabilities between the logging policy and the evaluated policy (cf. Eq. 11
& 19). In a similar vain, Kiyohara et al. (2022) propose a DR estimator for
predicting a CTR-based slate-metric under cascading user behavior, they also
use IPS weights based solely on action probabilities. These method are very
different from the IPS approach for unbiased LTR (Section 5.1) because their
corrections are not based on the mismatch between clicks and relevance, but on
the mismatch between action probabilities between policies. As a result, they
cannot handle situations where $\pi_{0}$ is deterministic and position-bias
occurs, in contrast with the LTR IPS estimator. We thus argue that the
approaches of Yuan et al. (2020) and Kiyohara et al. (2022) are better
understood as methods for correcting policy differences, instead of methods
designed for correcting position-bias in clicks directly.

Another DR estimator applied to click data was proposed by Saito (2020), who
realized that when estimating post-click conversions, the click signal can be
seen as the treatment variable. This avoids the unobservable examination
problem as clicks are always directly observable in the data. The propensities
of Saito are thus based on click probabilities, instead of action or
examination probabilities. While being very useful for post-click conversions,
their method cannot be applied to predicting click probabilities or our LTR
problem setting.

In summary, existing DR estimation does not seem directly applicable to
position-bias since the treatment variable, item examination, is unobservable
in click logs. To the best of our knowledge, DR estimators that have been
applied to clicks correct for the mismatch between logging policy and the
evaluated policy. Currently, there does not appear to be a DR estimator that
uses the correlations between clicks and relevances as state-of-the-art IPS
estimation for LTR.

##  6\. Method: The Direct Method and Doubly Robust Estimation for Learning to
Rank

In Section 4 the generic IPS, DM and DR estimators were introduced,
subsequently, Section 5 showed how IPS has been successfully adapted for the
LTR problem specifically. This naturally raises the question whether
adaptations of DM and DR estimation for LTR could bring additional success to
the field. To answer this question, this section introduces novel DM and DR
estimators for LTR and also a novel estimator for the cross-entropy loss.

###  6.1. The Direct Method for Learning to Rank

As discussed in Section 4, the direct-method (DM) solely relies on regression
to estimate performance, in contrast with IPS which uses click frequencies and
propensities (Dudík et al., 2014). The generic DM estimator in Eq. 15
estimates CTR with the estimated bias parameters $\hat{\alpha}$ and
$\hat{\beta}$ and the relevance estimates $\hat{R}_{\pi}$. However, to
estimate $\mathcal{R}$ (Eq. 7), we only require the weight estimate
$\omega_{d}$ and $\hat{R}_{d}$ per item $d$. The DM estimate of
$\mathcal{R}(\pi)$ then is:

(32) $\widehat{\mathcal{R}}_{\text{DM}}(\pi)=\sum_{d\in
D}\hat{\omega}_{d}\hat{R}_{d}.$

While to the best of our knowledge it is novel, our DM estimator is extremely
straightforward: for each item we multiply its estimated expected position
weight $\hat{\omega}_{d}$ with its relevance estimate: $\hat{R}_{d}$. The
biggest difference with the generic DM is that instead of using the policy
probabilities $\hat{\pi}(y)$ or $\hat{\alpha}$ and $\hat{\beta}$ directly, it
uses $\hat{\omega}_{d}$ which is based on their values (Eq. 24).

By considering Eq. 7, 24 and 32, we can clearly see
$\widehat{\mathcal{R}}_{\text{DM}}$ has the following condition for
unbiasedness:

(33) $\big{(}\overbrace{\hat{\alpha}=\alpha\land\hat{\beta}=\beta}^{\text{pos.
bias correctly estimated}}\land\underbrace{\big{(}\forall d\in
D,\;\hat{R}_{d}=R_{d}\big{)}}_{\text{all regression estimates are
correct}}\big{)}\longrightarrow\widehat{\mathcal{R}}_{\text{DM}}(\pi)=\mathcal{R}(\pi).$

In other words, both the bias parameters and the regression model have to be
accurate for $\widehat{\mathcal{R}}_{\text{DM}}(\pi)$ to be unbiased. The
first part of the condition is required because accurate $\hat{\alpha}$ and
$\hat{\beta}$ are needed for an accurate estimate of the $\omega$ weights. The
second part of the condition: that all regression estimates $\hat{R}_{d}$ need
to be correct, show that it is practically infeasible for DM to be unbiased
since finding an accurate $\hat{R}_{d}$ values appears to be as difficult as
the ranking task itself. This reasoning could explain why – to the best of our
knowledge – no existing work has applied DM to unbiased LTR. However, the
experimental findings in this paper cast doubt on this reasoning, since they
show that DM can be more effective than IPS, especially when the number of
displayed rankings $N$ is not very large.

An advantage of DM over IPS is how non-clicked items are treated: The IPS
estimator (Eq. 25) treats items that are not clicked in the logged data as
completely irrelevant items that should be placed at the bottom of a ranking.
As pointed out in previous work (Wang et al., 2021), this seems very unfair to
items that were never displayed during logging, and this _winner-takes-all_
behavior could potentially explain the high variance of IPS. In contrast,
because DM relies on regression estimates it can provide non-zero values to
all items, even those never displayed. Additionally, DM does not require any
estimate of the logging policy $\hat{\pi}_{0}$ whereas IPS heavily relies on
$\hat{\pi}_{0}$. But DM does not utilize any of the click-data, and thus, DM
cannot correct for inaccuracies in the regression estimates. Furthermore, the
unbiasedness criteria for DM are much less feasible than those of IPS.
Ideally, the advantageous properties of both IPS and DM should be combined in
a single estimator, while avoiding the downsides of each approach. The
following subsection considers whether DR estimation could result in such a
combination.

###  6.2. A Novel Doubly-Robust Estimator for Relevance Estimation under
Position-Bias

Now that we have IPS and DM estimators for LTR, we only require a covariate
(CV) to construct a doubly-robust (DR) estimator (Dudík et al., 2014). As
discussed in Section 4, CV should have the same expected value as DM when IPS
is unbiased, while simultaneously having a high covariance with IPS. With
these requirements in mind, we propose the following CV:

(34)
$\widehat{\mathcal{R}}_{\text{CV}}(\pi)=\frac{1}{N}\sum_{i=1}^{N}\sum_{d\in
D}\overbrace{\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}}^{\text{IPS
weight}}\underbrace{\hat{\alpha}_{k_{i}(d)}\hat{R}_{d}}_{\text{increase in
click prob. due to relevance}}.$

Interestingly, CV does not use the observed clicks but utilizes at what ranks
an item was displayed in the logged data. The last part of the estimator
represents the increase in click probability an item receives by being
displayed at a position, the hope is that this correlates with the actual
observed clicks. Importantly, CV has the same expected value as DM when
$\hat{\pi}$ is correct and clipping has no effect (see Theorem B.2 for proof):

(35) $\underbrace{\big{(}\forall
d,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\hat{\rho}_{d}\geq\tau\big{)}}_{\text{$\hat{\pi}$
is correct and clipping has no
effect}}\longrightarrow\mathds{E}_{y\sim\pi_{0}}\left[\widehat{\mathcal{R}}_{\text{CV}}(\pi)\right]=\widehat{\mathcal{R}}_{\text{DM}}(\pi).$

If we compare the above condition with the unbiasedness condition of IPS in
Eq. 27, we see that the latter encapsulates the former. In other words, CV is
an unbiased estimate of DM when IPS is an unbiased estimate of $\mathcal{R}$.

Since our CV has the required properties, we can straightforwardly propose our
novel DR estimator (cf. Eq. 19):

(36)
$\begin{split}\widehat{\mathcal{R}}_{\text{DR}}(\pi)&=\widehat{\mathcal{R}}_{\text{DM}}(\pi)+\widehat{\mathcal{R}}_{\text{IPS}}(\pi)-\widehat{\mathcal{R}}_{\text{CV}}(\pi)\\\
&=\widehat{\mathcal{R}}_{\text{DM}}(\pi)+\frac{1}{N}\sum_{i=1}^{N}\sum_{d\in
D}\overbrace{\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}}^{\text{IPS
weight}}\underbrace{\left(c_{i}(d)-\hat{\alpha}_{k_{i}(d)}\hat{R}_{d}-\hat{\beta}_{k_{i}(d)}\right)}_{\text{diff.
between observed click and predicted click prob.}}.\end{split}$

We see that our DR estimator follows a similar structure as generic DR
estimation (Section 4): it starts with DM as a baseline then adds an IPS
estimate of the difference between DM and the true reward $\mathcal{R}$.
Concretely, the difference between each observed click signal $c_{i}(d)$ and
the predicted click probability
$\hat{\alpha}_{k_{i}(d)}\hat{R}_{d}+\hat{\beta}_{k_{i}(d)}$ is taken and
reweighted with an IPS estimate. Effectively, the observed clicks are thus
used to estimate and correct the error of DM.

An intuitive advantage of DR is that for items that were never displayed
during logging (i.e. $\forall 0<i\leq N,\;\hat{\alpha}_{k_{i}(d)}=0$), DR
relies solely on regression to estimate their relevance, similar to DM. Yet
for items that have been displayed many times, DR will estimate relevance more
similar to IPS for those items, thereby it is able to correct for regression
mistakes with clicks. The combination of these properties, means that DR can
avoid the _winner-takes-all_ behavior of IPS where all non-displayed or non-
clicked items are seen as completely non-relevant and pushed to the bottom of
the ranking. We expect this to mean that DR does not have the same variance
problems as IPS. At the same time, DR still relies on clicks and thus does not
require perfectly accurate regression estimates. Our theoretical analysis
shows that this enables DR to have more reasonable unbiasedness requirements
than DM.

The main difference with standard DR estimation for contextual bandits, i.e.
as described by Dudík et al. (2014), and our DR estimator is that our CV uses
a soft expected-treatment variable $\hat{\alpha}_{k_{i}(d)}$. This difference
is necessary because relevances $R_{d}$ cannot be observed directly and have
to be inferred from click signals $c_{i}(d)$. Thus, while standard CV would
use the observed reward signal, our CV infers the relevance from the observed
click. We call $\hat{\alpha}_{k_{i}(d)}$ a soft expected-treatment variable
because it can be seen as the expected effect that relevance had on the click
probability. To the best of our knowledge, our DR estimator is the first to
use such a soft-treatment variable.

Moreover, in contrast with the existing methods described in Section 4 and 5.3
that use propensities based on the mismatch between $\pi_{0}$ and $\pi$ (Yuan
et al., 2020; Kiyohara et al., 2022; Saito, 2020). Our DR estimator uses the
correlation between clicks and relevance to correct for position-bias, it is
thus also applicable when the logging policy is deterministic and inherents
the advantages that the LTR IPS estimator has over generic IPS estimation. We
thus argue that our DR estimator is the first that is designed to directly
correct for position-bias, and therefore provides a very significant
contribution to the unbiased LTR field.

###  6.3. Theoretical Properties of the Novel Doubly-Robust Estimator

Sections 7 and 8 experimentally investigate the performance improvements our
contribution brings, whereas Appendix C proves several theoretical advantages
DR has over both IPS and DM in terms of bias and variance. We summarize our
main theoretical findings in the remainder of this section.

Theorem C.1 shows that our DR has the following bias:

(37)
$\begin{split}&\mathds{E}_{c,y\sim\pi_{0}}\left[\widehat{\mathcal{R}}_{\text{DR}}(\pi)\right]-\mathcal{R}(\pi)\\\
&\hskip 17.07182pt=\sum_{d\in
D}\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}\bigg{(}\underbrace{\left(\mathds{E}_{y\sim\pi_{0}}\left[\alpha_{k(d)}\right]-\hat{\rho}_{d}\frac{\omega_{d}}{\hat{\omega}_{d}}\right)}_{\text{error
from $\hat{\pi}$, $\hat{\alpha}$, $\hat{\beta}$ and
clipping}}R_{d}+\underbrace{\left(\hat{\rho}_{d}-\mathds{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right]\right)}_{\text{error
from $\hat{\pi}$ and
clipping}}\hat{R}_{d}+\underbrace{\underset{y\sim\pi_{0}}{\mathds{E}}\left[\beta_{k(d)}-\hat{\beta}_{k(d)}\right]}_{\text{error
from $\hat{\beta}$}}\bigg{)}.\end{split}$

Furthermore, Corollary C.3 shows that if the bias parameters are correctly
estimated, this can be simplified to:

(38)
$\begin{split}\underbrace{\left(\hat{\alpha}=\alpha\land\hat{\beta}=\beta\right)}_{\text{pos.
bias is correctly
estimated}}\longrightarrow\mathds{E}_{c,y\sim\pi_{0}}\left[\widehat{\mathcal{R}}_{\text{DR}}(\pi)\right]-\mathcal{R}(\pi)&=\sum_{d\in
D}\frac{\omega_{d}}{\hat{\rho}_{d}}\bigg{(}\underbrace{\left(\mathds{E}_{y\sim\pi_{0}}\left[\alpha_{k(d)}\right]-\hat{\rho}_{d}\right)}_{\text{error
from $\hat{\pi}$ and
clipping}}\overbrace{\left(R_{d}-\hat{R}_{d}\right)}^{\text{error from
regression}}\bigg{)}.\end{split}$

The multiplication of errors in the bias can be beneficial for more robustness
(cf. Eq. 20), however, it only occurs when the bias parameters are correct.
From the simplified bias, Theorem C.4 derives the following unbiasedness
conditions:

(39) $\hskip
7.11317pt\big{(}\underbrace{\hat{\alpha}=\alpha\land\hat{\beta}=\beta}_{\text{pos.
bias is correctly estimated}}\land\,\big{(}\forall d\in
D,\,\underbrace{(\hat{\pi}_{0}(d)=\pi_{0}(d)\land\rho_{d}\geq\tau)}_{\text{$\hat{\pi}$
is correct and clipping has no
effect}}\lor\overbrace{\hat{R}_{d}=R_{d}}^{\text{regression is
correct}}\big{)}\big{)}\longrightarrow\mathds{E}_{c,y\sim\pi_{0}}\big{[}\widehat{\mathcal{R}}_{\text{DR}}(\pi)\big{]}=\mathcal{R}_{\pi}.$

In other words, DR is unbiased when the bias parameters are correctly
estimated and per item _either_ the logging policy distribution is correctly
estimated and clipping has no effect _or_ the regression estimate is correct.
In contrast, remember that IPS needs an accurate $\hat{\pi}_{0}(d)$ and
clipping to have no effects for _all_ items, and DM needs accurate regression
estimates for _all_ items. Therefore, DR is unbiased when either IPS or DM is
but can also be unbiased in situations where neither is. Clearly, our DR is
more robust than IPS and DM, yet all of the LTR estimators still require
accurate bias parameters. This seems inescapable since our reward
$\mathcal{R}$ is also based on user behavior, i.e. due to its $\omega$ weights
accurate $\alpha$ and $\beta$ estimates are needed.

In addition to the better unbiasedness conditions, Theorem C.5 proves our DR
estimator has less or equal bias than IPS when $\hat{\alpha}$ and
$\hat{\beta}$ are accurate and each $\hat{R}_{d}$ estimate is less than twice
the true $R_{d}$ value:

(40) $\begin{split}&\hskip
7.11317pt\big{(}\underbrace{\hat{\alpha}=\alpha\land\hat{\beta}=\beta}_{\text{pos.
bias is correctly estimated}}\land\overbrace{\big{(}\forall d\in
D,\;0\leq\hat{R}_{d}\leq 2R_{d}\big{)}}^{\text{regression estimates between
zero and twice true relevances}}\big{)}\\\\[-19.37494pt] &\hskip
119.50148pt\longrightarrow\underbrace{|\mathbb{E}_{c,y\sim\pi_{0}}\left[\mathcal{R}(\pi)\right]-\hat{\mathcal{R}}_{\text{DR}}(\pi)|\leq|\mathbb{E}_{c,y\sim\pi_{0}}\left[\mathcal{R}(\pi)\right]-\hat{\mathcal{R}}_{\text{IPS}}(\pi)|}_{\text{bias
of DR is less or equal than bias of IPS}}.\end{split}$

We see that our DR estimator is able to reduce bias with somewhat accurate
regression estimates. In particular, it appears that it mitigates some of the
bias introduced to IPS by clipping. Overall, it appears that our DR estimator
has better unbiasedness criteria than IPS or DM and has lower bias than IPS
given adequate regression estimates.

Besides bias, we should also consider the variance of our DR estimator, from
Eq. 36 it follows that (cf. Eq. 22):

(41)
$\mathds{V}\left[\widehat{\mathcal{R}}_{\text{DR}}(\pi)\right]=\mathds{V}\left[\widehat{\mathcal{R}}_{\text{IPS}}(\pi)\right]+\mathds{V}\left[\widehat{\mathcal{R}}_{\text{CV}}(\pi)\right]-2\mathbb{C}\text{ov}\left(\widehat{\mathcal{R}}_{\text{IPS}}(\pi),\widehat{\mathcal{R}}_{\text{CV}}(\pi)\right).$

Thus, a large covariance between IPS and CV allows for a reduction in the
variance of our DR estimator. To better understand when this may be the case,
Theorem C.6 proves the following condition for improved variance over IPS:

(42) $\hskip
7.11317pt\big{(}\underbrace{\hat{\alpha}=\alpha\land\hat{\beta}=\beta}_{\text{pos.
bias is correctly estimated}}\land\overbrace{\big{(}\forall d\in
D,\;0\leq\hat{R}_{d}\leq 2R_{d}\big{)}}^{\text{regression estimates between
zero and twice true
relevances}}\big{)}\longrightarrow\underbrace{\mathds{V}\big{[}\widehat{\mathcal{R}}_{\text{DR}}(\pi)\big{]}\leq\mathds{V}\big{[}\widehat{\mathcal{R}}_{\text{IPS}}(\pi)\big{]}}_{\text{variance
of DR is less or equal than that of IPS}}.$

We note that this is the same condition as in Eq. 40: correct $\hat{\alpha}$
and $\hat{\beta}$ estimates and regression estimates that are somewhat
correct. Interestingly, this shows that under this condition DR can improve
over IPS both in terms of bias and variance. In contrast, while the practice
of clipping reduces variance but introduces bias (Joachims et al., 2017b;
Strehl et al., 2010), it appears that under certain conditions DR can avoid
this tradeoff altogether.

Finally, we note that there is also an important exception; our DR estimator
is equivalent to IPS when all $\hat{\alpha}_{k_{i}(d)}$ are equal to their
corresponding $\rho_{d}$:

(43) $\big{(}\forall\,0<i\leq N,\;\forall d\in
D,\;\hat{\alpha}_{k_{i}(d)}=\hat{\rho}_{d}\big{)}\longrightarrow\widehat{\mathcal{R}}_{\text{DR}}(\pi)=\widehat{\mathcal{R}}_{\text{IPS}}(\pi).$

There are only two non-trivial situations where this can occur:  (i) when the
logging policy $\pi_{0}$ is deterministic _and_ clipping has no effect:
$\forall d\in D,\,\rho_{d}\geq\tau$; and  (ii) when all regression estimates
are zero: $\forall d\in D,\,\hat{R}_{d}=0$.  In all other scenarios, our DR
estimator does not reduce to IPS estimation. This means that even when
$\pi_{0}$ is deterministic, DR can have benefits over IPS when clipping is
applied.

To summarize, we have introduced a novel DR estimator that is specifically
designed for the LTR problem. In terms of bias and variance, our DR estimator
is more robust than both the IPS and the DM estimators: when either of IPS or
DM is unbiased the DR estimator is also unbiased, and in addition, there exist
cases where DR is unbiased and neither IPS nor DM are. Moreover, when the bias
parameters are accurate and all regression estimates are between zero and
twice the true preferences, we can prove that both the bias and variance of DR
are less or equal to those of IPS.

In terms of theory, our novel DR estimator is a breakthrough for the unbiased
LTR field: it is the first unbiased LTR method that uses DR estimation to
directly correct for position-bias, importantly, this makes it provenly more
robust than IPS estimation in terms of both bias and variance. Our DR
estimator is applicable in any unbiased LTR setting where IPS can be applied
and with any regression estimates, allowing for widespread adoption across the
entire field.

###  6.4. Applying LTR to Doubly-Robust Ranking Metric Estimates

It might not be directly obvious how LTR can be performed with the DR
estimator, while it is actually very straightforward. To begin, we consider
the common approaches for LTR when relevances are known: bounding (Wang et
al., 2018b; Burges, 2010) and sample-based approximation (Williams, 1992;
Oosterhuis, 2021; Ustimenko and Prokhorenkova, 2020). Bounding has a long
tradition in LTR for optimizing deterministic models (Burges, 2010); Wang et
al. (2018b) introduced the LambdaLoss method and proved that it can bound
ranking metrics, let $R$ be a vector of all true item relevances then:
$\text{LambdaLoss}(\pi,R)\leq\mathcal{R}(\pi)$. For probabilistic policies,
the policy gradient can be approximated based on sampled rankings (Williams,
1992), recently Oosterhuis (2021) proposed the PL-Rank method: $\text{PL-
Rank}(\pi,R)\approx\frac{\delta}{\delta\pi}\mathcal{R}(\pi)$.

To apply LTR methods like these to estimated metrics, we follow Oosterhuis and
de Rijke (2020) and reformulate the $\widehat{\mathcal{R}}_{\text{DR}}(\pi)$
to a sum over items that with expected-rank weights $\hat{\omega}_{d}$ and
relevance estimates $\hat{\mu}_{d}$:

(44) $\widehat{\mathcal{R}}_{\text{DR}}(\pi)=\sum_{d\in
D}\hat{\omega}_{d}\bigg{(}\hat{R}_{d}+\frac{1}{N\cdot\hat{\rho}_{d}}\sum_{i=1}^{N}\left(c_{i}(d)-\hat{\alpha}_{k_{i}(d)}\hat{R}_{d}-\hat{\beta}_{k_{i}(d)}\right)\bigg{)}=\sum_{d\in
D}\hat{\omega}_{d}\hat{\mu}_{d}.$

Let $\mu$ indicate a vector of all relevance estimates, Oosterhuis and de
Rijke (2020) prove that LambaLoss can be used as a bound on the estimated
metric:
$\text{LambdaLoss}(\pi,\hat{\mu})\leq\widehat{\mathcal{R}}_{\text{DR}}(\pi)$.
Similarly, the derivation of Oosterhuis (2021) is equally applicable to
$\widehat{\mathcal{R}}_{\text{DR}}(\pi)$ and can thus approximate the policy
gradient: $\text{PL-
Rank}(\pi,\hat{\mu})\approx\frac{\delta}{\delta\pi}\widehat{\mathcal{R}}_{\text{DR}}(\pi)$.
As such, existing LTR methods are straightforwardly applied to our DR
estimator in order to optimize ranking models w.r.t. unbiased click-based
estimates of performance.

###  6.5. Novel Cross-Entropy Loss Estimation

While our DR estimator can be applied with any regression model, we will
propose a novel estimator for the cross-entropy loss to optimize an accurate
regression model. There are two issues with the existing
$\widehat{\mathcal{L}}^{\prime}$ estimator (Eq. 30) we wish to avoid:  (i)
$\widehat{\mathcal{L}}^{\prime}$does not correct for trust-bias, and  (ii) for
any never-displayed item $d$ the $\widehat{\mathcal{L}}^{\prime}$ estimate
contains the $\log(1-\hat{R}_{d})$ loss that pushes $\hat{R}_{d}$ towards
zero.  In other words, $\widehat{\mathcal{L}}^{\prime}$ penalizes positive
$\hat{R}_{d}$ values for items that were never displayed during logging, while
it seems more intuitive that a loss estimate should be indifferent to the
$\hat{R}_{d}$ values of never-displayed items. We propose the following
estimator:

(45) $\widehat{\mathcal{L}}(\hat{R})=-\frac{1}{N}\sum_{i=1}^{N}\sum_{d\in
D}\overbrace{\frac{1}{\hat{\rho}_{d}}}^{\text{IPS
weight}}\Big{(}\underbrace{\big{(}c_{i}(d)-\hat{\beta}_{k_{i}(d)}\big{)}}_{\text{diff.
between observed click and predicted click prob. if
$R_{d}=0$}}\log\big{(}\hat{R}_{d}\big{)}+\overbrace{\big{(}\hat{\alpha}_{k_{i}(d)}+\hat{\beta}_{k_{i}(d)}-c_{i}(d)\big{)}}^{\text{diff.
between predicted click prob. if $R_{d}=1$ and observed
click}}\log\big{(}1-\hat{R}_{d}\big{)}\Big{)}.$

Our novel estimator has $\hat{\beta}$ corrections to deal with trust-bias and
utilizes the $\hat{\alpha}_{k_{i}(d)}$ to weight the negative part of the
loss: $\log(1-\hat{R}_{d})$. One possible interpretation is that
$\hat{\alpha}_{k_{i}(d)}$ replaces the $1$ in Eq. 30 using the fact that
$\mathds{E}_{y\sim\pi_{0}}[\alpha_{k_{i}(d)}/\rho_{d}]=1$. Another
interpretation is that the second weight looks at the difference between the
expected click probability if the item was maximally relevant ($R_{d}=1$) and
the observed click frequency, the expected difference reveals how much
relevance the item _lacks_. Regardless of interpretation, the important
property is that
$\mathds{E}_{c,y\sim\pi_{0}}\left[\frac{1}{\hat{\rho}_{d}}\left(\hat{\alpha}_{k_{i}(d)}+\hat{\beta}_{k_{i}(d)}-c_{i}(d)\right)\right]=(1-R_{d})$.
Furthermore, when an item $d$ is never displayed, the corresponding
$\hat{R}_{d}$ does not affect the estimate since in that case:
$\forall\,0<i\leq
N,\;\hat{\alpha}_{k_{i}(d)}=0\land\hat{\beta}_{k_{i}(d)}=0\land c_{i}(d)=0$.
Appendix D proves $\widehat{\mathcal{L}}$ is unbiased in the following
circumstances:

(46) $\overbrace{\big{(}\hat{\alpha}=\alpha\land\hat{\beta}=\beta}^{\text{pos.
bias correctly estimated}}\land\underbrace{\left(\forall d\in
D,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\rho_{d}\geq\tau\right)\big{)}}_{\text{$\hat{\pi}$
is correctly estimated and clipping has no
effect}}\longrightarrow\mathds{E}_{c,y\sim\pi_{0}}\big{[}\widehat{\mathcal{L}}(d)\big{]}=\mathcal{L}(d).$

These are the same conditions as those we proved for the IPS estimator (Eq.
27): the bias parameters and the logging policy need to be accurately
estimated and clipping should have no effect. Thus our novel cross-entropy
loss estimator can correct for position-bias, even when trust-bias is present,
and is indifferent to predictions on never-displayed items.

##  7\. Experimental Setup

In order to evaluate our novel DR estimator, we apply the semi-synthetic setup
that is common in unbiased LTR (Oosterhuis and de Rijke, 2018, 2019; Hofmann
et al., 2013; Zhuang and Zuccon, 2020; Vardasbi et al., 2020b; Ovaisi et al.,
2020; Joachims et al., 2017b). This simulates a web-search scenario by
sampling queries and documents from commercial search datasets, while user
interactions and rankings are simulated using probabilistic click models. We
use the three largest publicly-available LTR industry datasets: _Yahoo!
Webscope_ (Chapelle and Chang, 2011), _MSLR-WEB30k_ (Qin and Liu, 2013) and
_Istella_ (Dato et al., 2016). Each dataset contains queries, preselected
documents per query and for the query-document pairs: feature representations
and labels indicating expert-judged relevance, with
$\text{label}(d)\in\\{0,1,2,3,4\\}$ we use $P(R=1\mid
d)=0.25\cdot\text{label}(d)$. The queries in the datasets are divided into
training, validation and test partitions. Our logging policy is obtained by
supervised training on 1% of the training partition (Joachims et al., 2017b).
At each interaction $i$, a query is sampled uniformly over the training and
validation partitions and a corresponding ranking is sampled from the logging
policy. Clicks are simulated using the click model in Eq. 1. We simulate both
a top-$5$ setting, where only five items can be displayed at once, and a full-
ranking setting where all items are displayed simultaneously. The parameters
for the top-5 setting are based on empirical work by Agarwal et al. (2019b):
$\alpha^{\text{top-5}}=[0.35,0.53,0.55,0.54,0.52,0,0,\ldots]$ and
$\beta^{\text{top-5}}=[0.65,0.26,0.15,0.11,0.08,0,0,\ldots]$; for the full-
ranking setting we use Eq. 4 with: $P(O=1\,|\,k)=(1+(k-1)/5)^{-2}$,
$\epsilon^{+}_{k}=1$, and $\epsilon^{-}_{k}=0.1+0.6/(1+k/20)$, because these
closely match the top-5 parameters while being applicable to longer rankings.
We simulate both top-$5$ settings where $\alpha$ and $\beta$ are known and
where they are estimated with expectation-maximization (EM) (Vardasbi et al.,
2020b; Agarwal et al., 2019b). All models are neural networks with two 32-unit
hidden layers, applied in Plackett-Luce ranking models optimized using policy
gradients estimated with PL-Rank-2 (Oosterhuis, 2021). The only exception is
the logging policy in the full-ranking settings which is a deterministic
ranker to better match earlier work (Joachims et al., 2017b; Vardasbi et al.,
2020b; Agarwal et al., 2019a). Propensities $\rho_{d}$ use frequentist
estimates of the logging policy:
$\hat{\pi}_{0}(k\,|\,d)=\frac{1}{N}\sum_{i=1}^{N}\mathds{1}[k_{i}(d)=k]$, we
clip with $\tau^{\text{top-5}}=10/\sqrt{N}$ in the top-5 setting and
$\tau^{\text{full}}=100/\sqrt{N}$ in the full-ranking setting. Early stopping
is applied using counterfactual estimates based on clicks on the validation
set.

Our main performance metric is the expected number of clicks on preferred
items (ECP), as introduced in Section 3.2. In addition, Appendix E also
provides our main results measured with the NDCG metric.

Our results evaluate our DM estimator (Eq. 32) and our DR estimator (Eq. 32)
both using the estimates of a regression model optimized by our
$\widehat{\mathcal{L}}$ loss (Eq. 45). Their performance is compared with the
following baselines:  (i) a naive estimator that ignores bias (Eq. 25 with
$\tau=1$);  (ii) IPS(Eq. 25);  (iii) ratio-propensity-scoring(RPS) (Wang et
al., 2021); and  (iv) DMoptimized with $\widehat{\mathcal{L}}^{\prime}$ (Eq.
30 & 32) from previous work (Bekker et al., 2019; Saito et al., 2020).  None
of the estimators receive any information about queries that were not sampled
in the training data. To compare the differences with the optimal performance
possible, we also optimize a model based on the true labels (full-
information).

As an example for clarity, the following procedure is used to evaluate the
performance of our DR estimator at $N$ displayed rankings in the top-5 setting
with estimated bias parameters:  (1) $N$queries are sampled with replacement
from the training and validation partitions, a displayed ranking is generated
for each sampled query using the stochastic logging policy.  (2) Clicks on
each ranking are simulated using the click model in Eq. 1 and the true
$\alpha$ and $\beta$ parameters.  (3) EMis applied to the simulated click data
to obtain estimated $\hat{\alpha}$ and $\hat{\beta}$ parameters.  (4) A
regression model is optimized using $\mathcal{L}$, $\hat{\alpha}$,
$\hat{\beta}$ and the click data simulated on the training set, $\hat{R}_{d}$
is computed for each item.  (5) A ranking model is optimized to maximize the
DR estimate of its ECP, using $\hat{\alpha}$, $\hat{\beta}$, $\hat{R}_{d}$ and
the training click data, early stopping criteria are estimated with the
validation click data.  (6) Finally, the true ECP ($\mathcal{R}_{\pi}$, Eq. 7)
of the resulting ranking model is computed on the test-set and added to our
results.  We repeat each procedure twenty times independently and report the
mean results in addition to standard deviation and 90% confidence intervals.
Statistical differences with the performance of our DR estimator were measured
via a two-sided student’s t-test (Student, 1908).

|  Yahoo! Webscope |  MSLR-WEB30k | Istella
---|---|---|---
Top-5 Setting with Known Bias Parameters |  |  |
|  |
Top-5 Setting with Estimated Bias Parameters |  |  |
|  |
Full-Ranking with Known Bias Parameters |  |  |
|  |
Figure 1.  Policy performance in terms of ECP (Eq. 7) reached on three
datasets and several settings. Top row: top-5 setting with known $\alpha$ and
$\beta$ bias parameters; middle row: top-5 setting with estimated
$\hat{\alpha}$ and $\hat{\beta}$; bottom row: full-ranking setting (no cutoff)
with known $\alpha$ and $\beta$ bias parameters. Results are means over 20
independent runs, shaded areas indicate the 90% confidence intervals; y-axis:
ECP on the held-out test-set; x-axis: $N$ the number of displayed rankings in
the simulated training set.  Table 1.  Policy performance in terms of ECP (Eq.
7) reached using different estimators in three different settings and three
datasets for several $N$ values: the number of displayed rankings in the
simulated training set. In addition, the performance of the logging policy and
a model trained on the ground-truth (Full-Information) are included to
indicate estimated lower and upper bounds on possible performance
respectively. Top part: top-5 setting with known $\alpha$ and $\beta$ bias
parameters; middle part: top-5 setting with estimated $\hat{\alpha}$ and
$\hat{\beta}$; bottom part: full-ranking setting (no cutoff) with known
$\alpha$ and $\beta$ bias parameters. Reported numbers are averages over 20
independent runs evaluated on held-out test-sets, brackets display the
standard deviation (logging policy deviation is ommitted since it did not vary
between runs). Bold numbers indicate the highest performance per setting,
dataset and $N$ combination. Statistical differences with our DR estimator are
measured via a two-sided student-t test, ▼ and ▲ indicate methods with
significantly lower or higher ECP with $p<0.01$ respectively; additionally, ▽
and △ indicate significant differences with $p<0.05$.

| Yahoo! Webscope | MSLR-WEB30k | Istella
---|---|---|---
| $N=10^{4}$ | $N=10^{6}$ | $N=10^{9}$ | $N=10^{4}$ | $N=10^{6}$ | $N=10^{9}$ | $N=10^{4}$ | $N=10^{6}$ | $N=10^{9}$
| _Top-5 Setting with Known Bias Parameters_
Logging | 1.483 (0.000)- | 1.483 (0.000)- | 1.483 (0.000)- | 1.110 (0.007)- | 1.110 (0.007)- | 1.110 (0.007)- | 1.691 (0.000)- | 1.691 (0.000)- | 1.691 (0.000)-
Full-Info. | 1.628 (0.005)▲ | 1.628 (0.005)▲ | 1.628 (0.005)▲ | 1.282 (0.008)▲ | 1.282 (0.008)▲ | 1.282 (0.008)- | 1.994 (0.021)▲ | 1.994 (0.021)▲ | 1.994 (0.021)-
Naive | 1.495 (0.009)▼ | 1.498 (0.002)▼ | 1.500 (0.002)▼ | 1.114 (0.009)▼ | 1.121 (0.009)▼ | 1.121 (0.007)▼ | 1.707 (0.019)▼ | 1.736 (0.006)▼ | 1.737 (0.003)▼
DM (prev) | 1.519 (0.010)▼ | 1.540 (0.009)▼ | 1.565 (0.009)▼ | 1.139 (0.022)▽ | 1.214 (0.016)▼ | 1.201 (0.011)▼ | 1.539 (0.072)▼ | 1.696 (0.042)▼ | 1.904 (0.009)▼
RPS | 1.539 (0.007)▼ | 1.581 (0.004)▼ | 1.581 (0.005)▼ | 1.187 (0.009)▲ | 1.248 (0.004)▼ | 1.250 (0.006)▼ | 1.805 (0.007)▲ | 1.875 (0.008)▼ | 1.876 (0.007)▼
IPS | 1.486 (0.007)▼ | 1.552 (0.006)▼ | 1.590 (0.004)▼ | 1.110 (0.007)▼ | 1.187 (0.008)▼ | 1.237 (0.007)▼ | 1.710 (0.032)▼ | 1.879 (0.014)▼ | 1.950 (0.014)▼
DM (ours) | 1.542 (0.006)▽ | 1.594 (0.004)▼ | 1.616 (0.003)▼ | 1.143 (0.030)- | 1.252 (0.008)▼ | 1.271 (0.007)▼ | 1.721 (0.035)▼ | 1.898 (0.023)▼ | 1.966 (0.017)▼
DR (ours) | 1.548 (0.011)- | 1.602 (0.004)- | 1.623 (0.003)- | 1.157 (0.026)- | 1.263 (0.008)- | 1.281 (0.006)- | 1.769 (0.037)- | 1.952 (0.024)- | 2.004 (0.009)-
| _Top-5 Setting with Estimated Bias Parameters_
Logging | 1.483 (0.000)- | 1.483 (0.000)- | 1.483 (0.000)- | 1.110 (0.007)- | 1.110 (0.007)- | 1.110 (0.007)- | 1.691 (0.000)- | 1.691 (0.000)- | 1.691 (0.000)-
Full-Info. | 1.628 (0.005)▲ | 1.628 (0.005)▲ | 1.628 (0.005)▲ | 1.282 (0.008)▲ | 1.282 (0.008)▲ | 1.282 (0.008)- | 1.994 (0.021)▲ | 1.994 (0.021)▲ | 1.994 (0.021)-
Naive | 1.492 (0.006)▼ | 1.498 (0.003)▼ | 1.499 (0.003)▼ | 1.112 (0.008)▼ | 1.121 (0.008)▼ | 1.122 (0.006)▼ | 1.703 (0.018)- | 1.739 (0.005)▼ | 1.735 (0.011)▼
DM (prev) | 1.540 (0.007)▼ | 1.570 (0.009)▼ | 1.558 (0.005)▼ | 1.153 (0.025)- | 1.209 (0.016)▼ | 1.191 (0.011)▼ | 1.662 (0.039)▼ | 1.769 (0.049)▼ | 1.910 (0.014)▼
RPS | 1.537 (0.007)▼ | 1.582 (0.003)▼ | 1.581 (0.005)▼ | 1.188 (0.011)▲ | 1.245 (0.006)▼ | 1.250 (0.006)▼ | 1.811 (0.009)▲ | 1.875 (0.005)▼ | 1.876 (0.007)▼
IPS | 1.488 (0.009)▼ | 1.555 (0.006)▼ | 1.593 (0.003)▼ | 1.111 (0.007)▼ | 1.182 (0.007)▼ | 1.233 (0.009)▼ | 1.710 (0.033)- | 1.874 (0.013)▼ | 1.944 (0.019)▼
DM (ours) | 1.546 (0.007)- | 1.591 (0.010)▼ | 1.619 (0.005)▽ | 1.138 (0.021)- | 1.251 (0.011)▼ | 1.272 (0.008)▼ | 1.662 (0.047)▼ | 1.878 (0.043)▼ | 1.961 (0.010)▼
DR (ours) | 1.548 (0.006)- | 1.603 (0.003)- | 1.623 (0.004)- | 1.149 (0.028)- | 1.260 (0.005)- | 1.282 (0.005)- | 1.724 (0.057)- | 1.945 (0.014)- | 1.994 (0.012)-
| _Full-Ranking Setting with Known Bias Parameters_
Logging | 1.641 (0.000)- | 1.641 (0.000)- | 1.641 (0.000)- | 1.372 (0.006)- | 1.372 (0.006)- | 1.372 (0.006)- | 1.769 (0.000)- | 1.769 (0.000)- | 1.769 (0.000)-
Full-Info. | 1.764 (0.004)▲ | 1.764 (0.004)▲ | 1.764 (0.004)- | 1.531 (0.007)▲ | 1.531 (0.007)▲ | 1.531 (0.007)- | 2.025 (0.013)▲ | 2.025 (0.013)▲ | 2.025 (0.013)-
Naive | 1.642 (0.007)▼ | 1.642 (0.002)▼ | 1.645 (0.002)▼ | 1.369 (0.007)▼ | 1.374 (0.006)▼ | 1.374 (0.006)▼ | 1.757 (0.014)▼ | 1.777 (0.003)▼ | 1.777 (0.003)▼
DM (prev) | 1.642 (0.003)▼ | 1.630 (0.005)▼ | 1.597 (0.036)▼ | 1.368 (0.007)▼ | 1.365 (0.010)▼ | 1.356 (0.015)▼ | 1.795 (0.006)▼ | 1.810 (0.006)▼ | 1.807 (0.011)▼
RPS | 1.652 (0.004)▼ | 1.651 (0.001)▼ | 1.661 (0.002)▼ | 1.388 (0.006)▼ | 1.386 (0.006)▼ | 0.587 (0.004)▼ | 1.807 (0.018)▼ | 1.823 (0.002)▼ | 1.708 (0.044)▼
IPS | 1.643 (0.011)▼ | 1.716 (0.003)▼ | 1.762 (0.002)- | 1.368 (0.009)▼ | 1.468 (0.006)▼ | 1.532 (0.007)- | 1.766 (0.022)▼ | 1.953 (0.015)▼ | 2.033 (0.013)-
DM (ours) | 1.672 (0.009)- | 1.734 (0.005)▼ | 1.748 (0.009)▼ | 1.409 (0.021)- | 1.512 (0.010)- | 1.529 (0.007)- | 1.819 (0.028)- | 2.008 (0.013)- | 2.047 (0.009)▲
DR (ours) | 1.676 (0.010)- | 1.740 (0.004)- | 1.763 (0.004)- | 1.422 (0.017)- | 1.510 (0.009)- | 1.531 (0.006)- | 1.834 (0.019)- | 1.998 (0.019)- | 2.031 (0.012)-

##  8\. Results

Our main experimental results are displayed in Figure 1 and Table 7. Both
display performance reached, in terms of the ECP metric (Eq. 7), for different
estimators on varying amounts of simulated interaction data; and both are
split in three rows, each indicating the results of one of the three simulated
settings. The displayed results are means over twenty independent runs, 90%
confidence intervals are visualized in Figure 1 so that meaningful differences
can be recognized. Furthermore, Table 7 displays standard deviations and
statistical significant performance differences with DR using a two-sided
student’s t-test (Student, 1908).

###  8.1. Performance of Inverse Propensity Scoring

To begin our analysis, we consider the performance of IPS; In Figure 1, we see
that in both top-5 settings IPS is unable to reach optimal ECP when $N\leq
10^{9}$ on any of the datasets, an observation also made in previous work
(Oosterhuis and de Rijke, 2021a). In the top-5 setting with known bias
parameters, IPS is theoretically proven to be unbiased and will converge at
optimal ECP as $N\rightarrow\infty$. Consequently, we can conclude that it is
high variance which prevents us from observing IPS’s convergence in the top-
row of Figure 1 222The effect of clipping can be excluded since our clipping
strategy has no effect in our experimental setting when $N=10^{9}$.. This
observation illustrates the importance of variance reduction: it is not bias
but high variance that prevents IPS from reaching optimal performance with
feasible amounts of interaction data. In contrast with the two top-rows of
Figure 1, the bottom row shows that IPS can reach optimal ECP on all datasets
in the full-ranking setting. A plausible explanation is that interactions on a
complete ranking provide much more information than when only the top-5 can be
interacted with. Possibly, the item-selection-bias in the top-5 settings
greatly increase the variance of IPS due to the _winner-takes-all_ behavior
described in Section 6.1. Overall, we see that while IPS can approximate
optimal ECP in the full-ranking setting with reasonable amounts of data, its
variance prevents it from reaching good ECP in top-5 settings even when given
an enormous number of interactions.

###  8.2. Performance of Novel Direct Method and Doubly-Robust Estimators

Next we consider whether our DR estimator provides an improvement over the
performance of IPS. Figure 1 reveals that this is clearly the case: in all
settings it outperforms IPS when $N\approx 10^{4}$ and only in the full-
ranking setting does IPS catch up around $N\approx 10^{7}$. Moreover, DR
always has a higher or comparable mean ECP than IPS when $N\geq 10^{4}$,
across all datasets and settings. Table 7 does not report a single instance of
IPS significantly outperforming DR but many instances where DR significantly
outperforms IPS. In all of the top-5 settings, the ECP of DR when $N=10^{6}$
is not reached by IPS when $N=10^{9}$, regardless of whether bias parameters
are known or estimated. Therefore the DR appears to provide an increase in
data-efficiency over IPS of a factor greater than 1,000 in all of the top-5
settings. We thus confidently conclude that DR provides significantly and
considerably higher performance than state-of-the-art IPS, given that $N\geq
10^{4}$, which in top-5 settings leads to an enormous increase in data-
efficiency.

Subsequently, we compare the performance of our DM estimator with IPS. In
Figure 1, we see that in some cases DM has substantially better ECP than IPS,
particularly in the top-5 settings on Yahoo! and MSLR. Yet, we also see that,
on all settings on the Istella dataset, the ECP differences between DM and IPS
are much smaller; and on the full-ranking setting on Yahoo!, DM appears to
converge at noticeably worse ECP than IPS. These results are quite surprising
as it shows that this simple but previously-unconsidered approach is actually
a competitive baseline to IPS. We conclude that DM appears preferable over IPS
in top-5 settings where not all items can be displayed at once, but not
necessarily in full-ranking settings.

Lastly, our comparison considers both our novel DM and DR estimators. In
Figure 1, we see that overall DM has lower ECP than DR, but in some cases it
has comparable or not significantly different ECP. Table 7 reveals that in
both the top-5 settings and the full-ranking setting on Yahoo!, DR has a
significantly higher ECP than DM, even though these differences are smaller
than compared with IPS. This result confirms that the DR approach can indeed
effectively use click data to correct for the regression mistakes of DM. It
appears that this is especially the case on the Istella dataset, where in both
top-5 settings there is a considerable performance difference between our DR
and DM estimators; here Figure 1 shows the ECP reached by our DM when
$N=10^{9}$ is reached by our DR when $N\approx 10^{7}$. Notably, DM appears to
converge on suboptimal ECP in the full-ranking setting on Yahoo! and in both
top-5 settings on MSLR, indicating that its unbiasedness criteria (Eq. 33) are
not met in these situations. In stark contrast, our DR estimator reaches near-
optimal ECP in all tested scenarios, which corresponds with its much more
robust unbiasedness criteria. Overall, our results indicate that DR in the
majority of cases significantly outperforms DM.

Our observations seem to confirm several of our expectations from our
theoretical analysis: The inability of IPS to reach optimal ECP when
$N=10^{9}$ in top-5 settings confirms that variance is its biggest obstacle.
The large increase of DM over IPS seems to indicate that the usage of
regression estimates provides a large reduction in variance. The cases of
suboptimal convergence of DM show that its impractical unbiasedness criteria
are infeasible in some of our experimental settings. Finally, in all settings
and datasets, our DR estimator has significantly better or comparable ECP to
DM and IPS, while always converging near optimal ECP. This observation shows
that DR effectively combines the variance reduction of DM with the more
feasible unbiasedness criteria of IPS, and clearly provides the most robust
and highest performance across our tested settings and datasets.

Despite the large aforementioned advantages, we note that a downside of our DM
and DR estimators is that they provide low ECP in some settings when $N\leq
10^{4}$. It appears that our early-stopping strategy, which is very effective
for IPS, is not able to handle incorrect regression estimates very well.
Future work could investigate whether this could be remedied with safe
deployment strategies (Jagerman et al., 2020; Oosterhuis and de Rijke, 2021b),
that prevent deploying models with uncertain performance. However, it seems
doubtful to us that in a real-world setting such little data is available that
$N\leq 10^{4}$. Nonetheless, our results show that DM and DR are less
resilient to tiny amounts of training data than IPS.

###  8.3. Comparison with other Baselines

Finally, our comparison also includes other baseline methods: the naive
estimator, RPS and DM from previous work. We note that all of these methods
are biased in our setting: the naive estimator explicitly ignores position-
bias, RPS trades bias for less variance and the DM from previous work ignores
trust-bias. Unsurprisingly, Figure 1 and Table 7 show that they are all unable
to converge at optimal ECP in any of the settings. The effect of trust-bias
appears particularly large in the full-ranking setting, where none of these
baselines are able to substantially improve ECP over the logging policy. The
ECP of RPS appears very sensitive to propensity clipping: when $N\approx
10^{9}$ and clipping no longer has effect its performance completely drops.
Nevertheless, these baselines show that often a decrease in variance can be
favourable over unbiasedness, as some of them provide higher ECP than the
unbiased IPS estimator in the top-5 settings on Yahoo! and MSLR, especially
when $N$ is small. Regardless, due their bias, they are unable to combine
optimal convergence with low variance. It appears that our DR estimator is the
only method that effectively combines these properties.

Yahoo! Webscope | MSLR-WEB30k | Istella
---|---|---
Number of Displayed Queries ($N$) | Number of Displayed Queries ($N$) | Number of Displayed Queries ($N$)

Figure 2.  The effect of different clipping strategies on the ECP (Eq. 7) of
three estimators in the top-5 known-bias setting. Clipping strategies applied
are standard: $\tau^{\text{1x}}=10/\sqrt{N}$, little:
$\tau^{\text{0.001x}}=10^{-2}/\sqrt{N}$, and heavy:
$\tau^{\text{1000x}}=10^{4}/\sqrt{N}$ (cf. Eq. 24). Results are means over 20
independent runs; y-axis: policy performance in terms of ECP (Eq. 7) on the
held-out test-set; x-axis: $N$ the number of displayed rankings in the
simulated training set.

Yahoo! Webscope |  MSLR-WEB30k | Istella
---|---|---
Clipping Threshold ($\tau$) | Clipping Threshold ($\tau$) | Clipping Threshold ($\tau$)

Figure 3.  The effect of the clipping parameter $\tau$ (Eq. 24) on the ECP
(Eq. 7) of three estimators in the top-5 known-bias setting when the number of
impressions $N=10^{8}$. Results are means over 20 independent runs, shaded
areas indicate the 90% confidence intervals; y-axis: policy performance in
terms of ECP (Eq. 7) on the held-out test-set; x-axis: $\tau$ the clipping
threshold.

Yahoo! Webscope | MSLR-WEB30k | Istella
---|---|---
Number of Displayed Queries ($N$) | Number of Displayed Queries ($N$) | Number of Displayed Queries ($N$)

Figure 4.  Effect of very incorrect bias parameters $\hat{\alpha}$ and
$\hat{\beta}$ on the ECP (Eq. 7) of three estimators in the top-5 known-bias
setting. Incorrect bias estimates are the mean of the true values across all
positions: $\hat{\alpha}_{k}=\sum_{i=1}^{5}\alpha_{i}/5$ and
$\hat{\beta}_{k}=\sum_{i=1}^{5}\beta_{i}/5$, as if there is no position-bias
effect within the top-5. Results are means over 20 independent runs; y-axis:
policy performance in terms of ECP (Eq. 7) on the held-out test-set; x-axis:
$N$ the number of displayed rankings in the simulated training set.

Yahoo! Webscope |  MSLR-WEB30k | Istella
---|---|---
Bias-Parameter Interpolation ($z$) | Bias-Parameter Interpolation ($z$) | Bias-Parameter Interpolation ($z$)

Figure 5.  Effect of varying misestimations of the bias parameters
$\hat{\alpha}$ and $\hat{\beta}$ on the ECP (Eq. 7) of three estimators in the
top-5 known-bias setting when $N=10^{8}$. Bias parameters are interpolations
between the true values and their mean over positions with the interpolation
parameter $z$:
$\hat{\alpha}_{k}=z\cdot\alpha_{k}+(1-z)\sum_{i=1}^{5}\alpha_{i}/5$ and
$\hat{\beta}_{k}=z\cdot\beta_{k}+(1-z)\sum_{i=1}^{5}\beta_{i}/5$. Results are
means over 20 independent runs, shaded areas indicate the 90% confidence
intervals; y-axis: policy performance in terms of ECP (Eq. 7) on the held-out
test-set; x-axis: $z$ the interpolation parameter.

###  8.4. Correcting to Bias Introduced by the Clipping Strategy

As discussed in Section 6.3, one of the advantages of DR estimation is that,
in contrast with IPS, it can potentially correct for some of the bias
introduced by clipping. To experimentally verify whether these corrections can
lead to observable advantages in practice, we ran additional experiments with
varying clipping strategies applied to the IPS, DM and DR estimators in the
top-5 setting with known bias parameters.

Figure 3 shows the learning curves of these estimators with our standard
clipping strategy: $\tau^{\text{1x}}=10/\sqrt{N}$ (cf. Eq. 24), a strategy
with 1000 times less clipping: $\tau^{\text{0.001x}}=10^{-2}/\sqrt{N}$, and a
heavy clipping strategy: $\tau^{\text{1000x}}=10^{4}/\sqrt{N}$. In addition,
the effect of individual threshold values are visualized in Figure 3, where
ECP with $N=10^{8}$ is displayed for values of the clipping threshold $\tau$
ranging from $10^{-6}$ to $1$.

Clearly, IPS is the most sensitive to the clipping threshold as its ECP drops
dramatically when heavy clipping is applied. In contrast, while there is a
noticeable effect from varying $\tau$ on the DM and DR estimators, the
differences between light, standard and heavy clipping are relatively small on
the Yahoo! and MSLR datasets. On the Istella dataset, there is a larger
decrease in ECP for the DM and DR with heavy clipping, but it is still much
smaller than that of IPS. Importantly, we see that, regardless of what
clipping is applied, DR always has a higher ECP than DM and IPS. This
indicates that the performance advantage of DR over DM remains stable w.r.t.
the clipping strategy, where the differences with IPS become especially large
under heavy clipping.

Therefore, we conclude that the DM and DR are less sensitive to propensity
clipping than IPS and can better correct for the bias introduced by clipping
strategies. Where the performance of IPS considerably varies for different
clipping strategies, DM and DR are only affected by very heavy clipping. We
can thus infer that the use of regression by DM and DR makes them more robust
to propensity clipping. Moreover, the advantage of DR over both DM and IPS is
consistent across all our tested clipping strategies, indicating it is the
optimal choice regardless of what clipping strategy is applied.

###  8.5. Robustness to Incorrect Bias Specification

The main results presented in Figure 1 and Table 7 reveal that there is very
little difference in performance between the top-5 setting where the bias
parameters are known and where they have to be estimated. While this shows
that good performance is maintained when bias has to be estimated, it is
unclear whether this also means that the estimators are robust to misspecified
bias, since it is possible the estimated bias parameters are actually quite
accurate. Furthermore, most of our theoretical results assume that bias is
correctly estimated, it is thus valuable to empirically verify whether the
advantages of the DR remain when its bias parameters are incorrect.

To better understand how robust the DR estimator is to bias misspecification,
the ECP of the DR, DM and IPS estimators were measured in the top-5 setting
with intentionally misspecified bias parameters. For the incorrect bias
parameters, we choose the mean values across positions:
$\hat{\alpha}_{k}=\sum_{i=1}^{5}\alpha_{i}/5$ and
$\hat{\beta}_{k}=\sum_{i=1}^{5}\beta_{i}/5$. These mean values represent a
naive approach that ignores the effect of the position on the examination and
trust of users, i.e. it assumes that any document that is displayed in the
top-5 is treated equally by the user, regardless of its exact position.

Figure 5 displays the learning curves with these incorrect bias parameters.
Clearly, the ECP reached with all three estimators drops dramatically when the
bias is heavily misspecified. While IPS and DM converge on similar
performance, DR provides noticeably higher ECP when $N\geq 10^{5}$ on all
three datasets. This strongly indicates that DR is more robust to heavily
misspecified bias than DM and IPS.

We further investigate how the degree of misspecification affects the
estimators, by measuring ECP in the top-5 setting when $N=10^{8}$ and bias is
interpolated between the true values and the mean with the parameter
$z\in[0,1]$:
$\hat{\alpha}_{k}=z\cdot\alpha_{k}+(1-z)\sum_{i=1}^{5}\alpha_{i}/5$ and
$\hat{\beta}_{k}=z\cdot\beta_{k}+(1-z)\sum_{i=1}^{5}\beta_{i}/5$. The results
are displayed in Figure 5.

In line with our previous observations, Figure 5 reveals IPS to have the
lowest ECP, regardless of bias misspecification. Interestingly, the
differences between DR and DM vary: on Istella, DR considerably outperforms
DM, but on Yahoo! and MSLR, the difference is only clear when $z<0.1$ and
$z>0.9$. When the interpolation is more in between the extreme values, DM and
DR have comparable ECP where sometimes DM has slightly higher performance. As
a result, we cannot conclude whether DR better deals with bias
misspecification than DM. Nevertheless, the differences between DR and DM are
relatively small, thus the choice does not seem very consequential.
Conversely, our results clearly indicate that IPS provides worse ECP than DR
and DM whether bias is misspecified or not.

In summary, our results show that DR estimation is much more robust to bias
misspecification than IPS. Moreover, it appears to outperform DM under heavy
or light misspecification, but results are mixed when the misspecification is
moderate. Overall, our results indicate that the advantages of DR over IPS and
DM are mostly still applicable when bias is incorrectly estimated or
misspecified.

##  9\. Conclusion

This paper has introduced the first unbiased DR estimator that is specifically
designed to correct for position-bias in click feedback. Our estimator differs
from existing DR estimators by using the expected correlation between clicks
and preference per rank, instead of the unobservable examination variable or
corrections solely based on action probabilities. Additionally, we also
proposed a novel DM estimator and a novel cross-entropy loss estimator. In
terms of theory, this work has contributed the most robust estimator for LTR
yet: our DR estimator is the only method that corrects for position-bias,
trust-bias and item-selection bias and has less strict unbiasedness criteria
than the prevalent IPS approach. Moreover, our experimental results show that
it can provide enormous increases in data-efficiency compared to IPS and
better overall performance w.r.t. other existing state-of-the-art approaches.
Therefore, both our theoretical and empirical results indicate that our DR
estimator is the most reliable and effective way to correct for position-bias.
Consequently, we think there is large potential in replacing IPS with DR as
the new basis for the unbiased LTR field.

Future work hopefully finds similar gains in related tasks, e.g. exposure-
based ranking fairness (Singh and Joachims, 2018) or ranking display
advertisements (Lagrée et al., 2016). Overall, we expect the improvements in
efficiency and robustness to make unbiased LTR even more attractive for real-
world applications.

### Code, Resources and Data

To facilitate the reproducibility of the reported results, this work only made
use of publicly available data and our experimental implementation is publicly
available at https://github.com/HarrieO/2022-doubly-robust-LTR. Additionally,
a video presentation with accompanying slides is available at
https://harrieo.github.io//publication/2023-doubly-robust.

### Acknowledgments

We thank the reviewers of previous versions of this work for their valuable
comments and suggestions. This research was partially supported by the Google
Research Scholar Program. All content represents the opinion of the author,
which is not necessarily shared or endorsed by their respective employers
and/or sponsors.

## Appendices

##  Appendix A BIAS and Variance of IPS

###### Theorem A.1.

The IPS estimator (Eq. 25) has the following bias:

(47)
$\mathds{E}_{c,y\sim\pi_{0}}\left[\hat{\mathcal{R}}_{\text{IPS}}(\pi)\right]-\mathcal{R}(\pi)=\sum_{d\in
D}\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}\left(\left(\rho_{d}-\hat{\rho}_{d}\frac{\omega_{d}}{\hat{\omega}_{d}}\right)R_{d}+\mathds{E}_{y\sim\pi_{0}}\left[\beta_{k(d)}-\hat{\beta}_{k(d)}\right]\right).$

###### Proof.

Using Eq. 1, 7, 23 and 25 we get the following derivation:

(48)
$\displaystyle\mathds{E}_{c,y\sim\pi_{0}}\left[\hat{\mathcal{R}}_{\text{IPS}}(\pi)\right]$
$\displaystyle=\sum_{d\in
D}\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}\left(\rho_{d}R_{d}+\mathds{E}_{y\sim\pi_{0}}\left[\beta_{k(d)}-\hat{\beta}_{k(d)}\right]\right)$
(49) $\displaystyle=\mathcal{R}(\pi)+\sum_{d\in
D}\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}\left(\left(\rho_{d}-\hat{\rho}_{d}\frac{\omega_{d}}{\hat{\omega}_{d}}\right)R_{d}+\mathds{E}_{y\sim\pi_{0}}\left[\beta_{k(d)}-\hat{\beta}_{k(d)}\right]\right).\qed$

###### Lemma A.2.

By the definitions of $\omega$ (Eq. 6) and $\hat{\omega}$ (Eq. 24):

(50)
$\big{(}\hat{\alpha}=\alpha\land\hat{\beta}=\beta\big{)}\longrightarrow\left(\forall
d\in D,\;\hat{\omega}_{d}=\omega_{d}\right).$

###### Lemma A.3.

By the definitions of $\rho$ (Eq. 23) and $\hat{\rho}$ (Eq. 24):

(51) $\left(\hat{\alpha}=\alpha\land\left(\forall d\in
D,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\rho_{d}\geq\tau\right)\right)\longrightarrow(\forall
d\in D,\;\hat{\rho}_{d}=\rho_{d}).$

###### Lemma A.4.

Trivially, if the $\hat{\beta}$ bias parameters are correct then:

(52) $\hat{\beta}=\beta\longrightarrow\left(\forall d\in
D,\;\mathds{E}_{y\sim\pi_{0}}\left[\hat{\beta}_{k(d)}\right]=\mathds{E}_{y\sim\pi_{0}}\left[\beta_{k(d)}\right]\right).$

###### Corollary A.5.

When $\hat{\alpha}$ and $\hat{\beta}$ are correct IPS has the bias:

(53)
$(\hat{\alpha}=\alpha\land\hat{\beta}=\beta)\longrightarrow\mathbb{E}_{c,y\sim\pi_{0}}\left[\widehat{\mathcal{R}}_{\text{IPS}}(\pi)\right]-\mathcal{R}(\pi)=\sum_{d\in
D}\frac{{\omega}_{d}}{\hat{\rho}_{d}}\left(\rho_{d}-\hat{\rho}_{d}\right)R_{d}.$

###### Proof.

Follows from Theorem A.1 and Lemmas A.2 and A.4. ∎

###### Theorem A.6.

The IPS estimator (Eq. 25) is unbiased when $\hat{\alpha}$, $\hat{\beta}$ and
$\hat{\pi}_{0}$ are correctly estimated and clipping has no effect:

(54) $\big{(}\hat{\alpha}=\alpha\land\hat{\beta}=\beta\land\left(\forall d\in
D,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\rho_{d}\geq\tau\right)\big{)}\longrightarrow\mathds{E}_{c,y\sim\pi_{0}}\left[\hat{\mathcal{R}}_{\text{IPS}}(\pi)\right]=\mathcal{R}(\pi).$

###### Proof.

Follows from applying Lemma A.3 to Corollary A.5. ∎

###### Theorem A.7.

The IPS estimator (Eq. 25) has the variance:

(55)
$\mathds{V}\big{[}\widehat{\mathcal{R}}_{\text{IPS}}(\pi)\big{]}=\frac{1}{N}\sum_{d\in
D}\frac{\hat{\omega}_{d}^{2}}{\hat{\rho}_{d}^{2}}\big{(}\mathds{V}\big{[}c(d)\big{]}+\mathds{V}\big{[}\hat{\beta}_{k(d)}\big{]}-2\mathds{C}\text{ov}\big{[}c(d),\hat{\beta}_{k(d)}\big{]}\big{)}.$

###### Proof.

Follows from Eq. 1 and 25. ∎

##  Appendix B Bias of CV Estimator

###### Lemma B.1.

The CV estimator (Eq. 34) has the following expected value:

(56)
$\mathds{E}_{c,y\sim\pi_{0}}\left[\widehat{\mathcal{R}}_{\text{CV}}(\pi)\right]=\sum_{d\in
D}\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}\mathds{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right]\hat{R}_{d}.$

###### Proof.

Follows directly from Eq. 34. ∎

###### Theorem B.2.

The CV estimator (Eq. 34) is an unbiased estimate of DM (Eq. 32) if the
$\hat{\alpha}$ and $\hat{\beta}$ bias parameters are correctly estimated and
per item either $\hat{\pi}_{0}(d)$ is correct and clipping has no effect:

(57) $\big{(}\forall d\in
D,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\hat{\rho}_{d}\geq\tau\big{)}\longrightarrow\mathds{E}\left[\widehat{\mathcal{R}}_{\text{CV}}(\pi)\right]=\widehat{\mathcal{R}}_{\text{DM}}(\pi).$

###### Proof.

From Lemma B.1 it clearly follows that the expected value of CV is equal to DM
(Eq. 32) when
$\hat{\rho}_{d}=\mathds{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right]$.
The definition of $\hat{\rho}$ (Eq. 24) shows that this is the case when
$\hat{\pi}_{0}(d)$ is correct and clipping has no effect:

(58) $\big{(}\forall d\in
D,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\hat{\rho}_{d}\geq\tau\big{)}\longrightarrow\left(\forall
d\in
D,\;\hat{\rho}_{d}=\mathds{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right]\right).$

Applying Eq. 58 to Lemma B.1 thus proves Theorem B.2. ∎

##  Appendix C Bias and Variance of DR Estimator

###### Theorem C.1.

The DR estimator (Eq. 36) has the following bias:

(59)
$\begin{split}&\mathds{E}_{c,y\sim\pi_{0}}\left[\hat{\mathcal{R}}_{\text{DR}}(\pi)\right]-\mathcal{R}(\pi)\\\
&\hskip 48.36958pt=\sum_{d\in
D}\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}\bigg{(}\left(\rho_{d}-\frac{\hat{\rho}_{d}}{\hat{\omega}_{d}}\omega_{d}\right)R_{d}+\left(\hat{\rho}_{d}-\mathds{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right]\right)\hat{R}_{d}+\mathds{E}_{y\sim\pi_{0}}\left[\beta_{k(d)}-\hat{\beta}_{k(d)}\right]\bigg{)}.\end{split}$

###### Proof.

Using Eq. 7, 32 and 36 we make the following derivation:

$\displaystyle\mathds{E}_{c,y\sim\pi_{0}}\left[\hat{\mathcal{R}}_{\text{DR}}(\pi)\right]=\hat{\mathcal{R}}_{\text{DM}}(\pi)+\sum_{d\in
D}\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}\Big{(}\rho_{d}R_{d}-\mathds{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right]\hat{R}_{d}+\mathds{E}_{y\sim\pi_{0}}\left[\beta_{k(d)}-\hat{\beta}_{k(d)}\right]\Big{)}$
(60) $\displaystyle\hskip 19.91684pt=\sum_{d\in
D}\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}\left(\rho_{d}R_{d}-\big{(}\mathds{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right]-\hat{\rho}_{d}\big{)}\hat{R}_{d}+\mathds{E}_{y\sim\pi_{0}}\left[\beta_{k(d)}-\hat{\beta}_{k(d)}\right]\right)$
(61) $\displaystyle\hskip 19.91684pt=\mathcal{R}(\pi)+\sum_{d\in
D}\frac{\hat{\omega}_{d}}{\hat{\rho}_{d}}\Big{(}\Big{(}\rho_{d}-\frac{\hat{\rho}_{d}}{\hat{\omega}_{d}}\omega_{d}\Big{)}R_{d}-\left(\mathds{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right]-\hat{\rho}_{d}\right)\hat{R}_{d}+\mathds{E}_{y\sim\pi_{0}}\left[\beta_{k(d)}-\hat{\beta}_{k(d)}\right]\Big{)}.\qed$

###### Lemma C.2.

By the definition of $\rho$ (Eq. 23):

(62) $\hat{\alpha}=\alpha\longrightarrow\big{(}\forall d\in
D,\;\mathds{E}_{y\sim\pi_{0}}\big{[}\hat{\alpha}_{k(d)}\big{]}=\rho_{d}\big{)}.$

###### Corollary C.3.

The bias of the DR estimator (Eq. 36) can be simplified when $\hat{\alpha}$
and $\hat{\beta}$ are correctly estimated:

(63)
$(\hat{\alpha}=\alpha\land\hat{\beta}=\beta)\longrightarrow\mathbb{E}_{c,y\sim\pi_{0}}\left[\hat{\mathcal{R}}_{\text{DR}}(\pi)\right]-\mathcal{R}(\pi)=\sum_{d\in
D}\frac{\omega_{d}}{\hat{\rho}_{d}}\left(\rho_{d}-\hat{\rho}_{d}\right)\left(R_{d}-\hat{R}_{d}\right).$

###### Proof.

Apply Lemmas A.2, A.4 and C.2 to Theorem C.1. ∎

###### Theorem C.4.

The DR estimator (Eq. 36) is unbiased if the $\hat{\alpha}$ and $\hat{\beta}$
bias parameters are correctly estimated and per item either $\hat{\pi}_{0}(d)$
is correct and clipping has no effect or $\hat{R}_{d}$ is correct:

(64) $\big{(}\hat{\alpha}=\alpha\land\hat{\beta}=\beta\land\left(\forall d\in
D,\,(\hat{\pi}_{0}(d)=\pi_{0}(d)\land\rho_{d}\geq\tau\right)\lor\hat{R}_{d}=R_{d})\big{)}\longrightarrow\mathbb{E}_{c,y\sim\pi_{0}}\left[\hat{\mathcal{R}}_{\text{DR}}(\pi)\right]=\mathcal{R}_{\pi}.$

###### Proof.

From Corollary C.3 it clearly follows that the DR estimator is unbiased when
the $\hat{\alpha}$ and $\hat{\beta}$ bias parameters are correct and per item
$d$ either $\hat{\rho}_{d}$ or $\hat{R}_{d}$ is correct:

(65) $\left(\hat{\alpha}=\alpha\land\hat{\beta}=\beta\land\left(\forall d\in
D,\,\hat{\rho}_{d}={\rho}_{d}\lor\hat{R}_{d}=R_{d}\right)\right)\longrightarrow\mathbb{E}_{c,y\sim\pi_{0}}\left[\hat{\mathcal{R}}_{\text{DR}}(\pi)\right]=\mathcal{R}_{\pi}.$

Applying Lemma A.3 to Eq. 65 provides proof for Theorem C.4. ∎

###### Theorem C.5.

If $\hat{\alpha}$ and $\hat{\beta}$ are correct and the regression model
predicts each preference $\hat{R}_{d}$ between $0$ and twice the true $R_{d}$
value then the bias of the DR estimator (Eq. 36) is less or equal to that of
the IPS estimator (Eq. 25):

(66)
$\begin{split}&\left(\hat{\alpha}=\alpha\land\hat{\beta}=\beta\land\left(\forall
d\in D,\;0\leq\hat{R}_{d}\leq 2R_{d}\right)\right)\\\ &\hskip
113.81102pt\longrightarrow|\mathbb{E}_{c,y\sim\pi_{0}}\left[\mathcal{R}(\pi)\right]-\hat{\mathcal{R}}_{\text{DR}}(\pi)|\leq|\mathbb{E}_{c,y\sim\pi_{0}}\left[\mathcal{R}(\pi)\right]-\hat{\mathcal{R}}_{\text{IPS}}(\pi)|.\end{split}$

###### Proof.

This follows from comparing Corollary A.5 with C.3. ∎

###### Theorem C.6.

The DR estimator (Eq. 36) has the variance:

(67)
$\displaystyle\mathds{V}\big{[}\widehat{\mathcal{R}}_{\text{DR}}(\pi)\big{]}=\frac{1}{N}\sum_{d\in
D}\frac{\hat{\omega}_{d}^{2}}{\hat{\rho}_{d}^{2}}\Big{(}$
$\displaystyle\mathds{V}\big{[}c(d)\big{]}+\mathds{V}\big{[}\hat{\beta}_{k(d)}\big{]}+\hat{R}_{d}^{2}\cdot\mathds{V}\left[\hat{\alpha}_{k(d)}\right]$
$\displaystyle-2\Big{(}\mathds{C}\text{ov}\big{(}c(d),\hat{\beta}_{k(d)}\big{)}+\hat{R}_{d}\big{(}\mathds{C}\text{ov}\big{(}c(d),\hat{\alpha}_{k(d)}\big{)}-\mathds{C}\text{ov}\big{(}\hat{\beta}_{k(d)},\hat{\alpha}_{k(d)}\big{)}\big{)}\Big{)}\Big{)}.$

###### Proof.

This follows from Eq. 1 and 36. ∎

###### Lemma C.7.

The covariance between clicks on an item $c(d)$ and $\alpha_{k(d)}$ is:

(68)
$\mathds{C}\text{ov}\big{(}c(d),{\alpha}_{k(d)}\big{)}=R_{d}\mathds{V}\left[{\alpha}_{k(d)}\right]+\mathds{C}\text{ov}\big{(}{\alpha}_{k(d)},{\beta}_{k(d)}\big{)}.$

###### Proof.

$\displaystyle\mathds{C}\text{ov}\left(c(d),{\alpha}_{k(d)}\right)=\mathds{E}_{c,y\sim\pi_{0}}\left[\Big{(}c(d)-\mathds{E}_{c,y\sim\pi_{0}}\big{[}c(d)\big{]}\Big{)}\left({\alpha}_{k(d)}-\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]\right)\right]$
$\displaystyle=\mathds{E}_{c,y\sim\pi_{0}}\left[\left(c(d)-\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]R_{d}-\mathds{E}_{y\sim\pi_{0}}\left[{\beta}_{k(d)}\right]\right)\left({\alpha}_{k(d)}-\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]\right)\right]$
$\displaystyle=\mathds{E}_{c,y\sim\pi_{0}}\Big{[}{\alpha}_{k(d)}c(d)-\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]c(d)-{\alpha}_{k(d)}\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]R_{d}$
$\displaystyle\hskip
8.5359pt+\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]^{2}R_{d}-{\alpha}_{k(d)}\mathds{E}_{y\sim\pi_{0}}\left[{\beta}_{k(d)}\right]+\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]\mathds{E}_{y\sim\pi_{0}}\left[{\beta}_{k(d)}\right]\Big{]}$
(69)
$\displaystyle=\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}^{2}\right]R_{d}+\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}{\beta}_{k(d)}\right]-\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]^{2}R_{d}$
$\displaystyle\hskip
8.5359pt-\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]\mathds{E}_{y\sim\pi_{0}}\left[{\beta}_{k(d)}\right]-\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]^{2}R_{d}+\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]^{2}R_{d}$
$\displaystyle\hskip
8.5359pt-\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]\mathds{E}_{y\sim\pi_{0}}\left[{\beta}_{k(d)}\right]+\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]\mathds{E}_{y\sim\pi_{0}}\left[{\beta}_{k(d)}\right]$
$\displaystyle=R_{d}\left(\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}^{2}\right]-\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]^{2}\right)+\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}{\beta}_{k(d)}\right]-\mathds{E}_{y\sim\pi_{0}}\left[{\alpha}_{k(d)}\right]\mathds{E}_{y\sim\pi_{0}}\left[{\beta}_{k(d)}\right]$
$\displaystyle=R_{d}\mathds{V}\left[{\alpha}_{k(d)}\right]+\mathds{C}\text{ov}\big{(}{\alpha}_{k(d)},{\beta}_{k(d)}\big{)}.$

∎

###### Corollary C.8.

If $\hat{\alpha}$ and $\hat{\beta}$ are correct then the variance of the DR
estimator (Eq. 36) is:

(70) $\displaystyle(\hat{\alpha}=\alpha\land\hat{\beta}=\beta)\longrightarrow$
$\displaystyle\hskip
14.22636pt\mathds{V}\left[\hat{\mathcal{R}}_{\text{DR}}(\pi)\right]=\frac{1}{N}\sum_{d\in
D}\frac{{\omega}_{d}^{2}}{\hat{\rho}_{d}^{2}}\Big{(}\mathds{V}\left[c(d)\right]+\mathds{V}\left[{\beta}_{k(d)}\right]-2\mathds{C}\text{ov}\left(c(d),{\beta}_{k(d)}\right)+\mathds{V}\left[{\alpha}_{k(d)}\right]\left(\hat{R}_{d}^{2}-2\hat{R}_{d}R_{d}\right)\Big{)}.$

###### Proof.

In Theorem C.6 replace $\hat{\alpha}$ and $\hat{\beta}$ with $\alpha$ and
$\beta$ respectively and then use Lemma C.7 to replace
$\mathds{C}\text{ov}\big{(}c(d),{\alpha}_{k(d)}\big{)}$. ∎

###### Theorem C.9.

If $\hat{\alpha}$ and $\hat{\beta}$ are correct and the regression model
predicts each preference $\hat{R}_{d}$ between $0$ and twice the true $R_{d}$
value then the variance of the DR estimator (Eq. 36) is less or equal to that
of the IPS estimator (Eq. 25):

(71) $\left(\hat{\alpha}=\alpha\land\hat{\beta}=\beta\land\left(\forall d\in
D,\;0\leq\hat{R}_{d}\leq
2R_{d}\right)\right)\longrightarrow\mathds{V}\left[\hat{\mathcal{R}}_{\text{DR}}(\pi)\right]\leq\mathds{V}\left[\hat{\mathcal{R}}_{\text{IPS}}(\pi)\right].$

###### Proof.

Comparing Corollary A.5 and C.8 reveals that:

(72) $\left(\hat{\alpha}=\alpha\land\hat{\beta}=\beta\land\left(\forall d\in
D,\;\hat{R}_{d}^{2}-2\hat{R}_{d}R_{d}\leq
0\right)\right)\longrightarrow\mathds{V}\left[\hat{\mathcal{R}}_{\text{DR}}(\pi)\right]\leq\mathds{V}\left[\hat{\mathcal{R}}_{\text{IPS}}(\pi)\right].$

For a single $\hat{R}_{d}$ the following holds:

(73) $0\leq\hat{R}_{d}\leq
2R_{d}\longrightarrow\hat{R}_{d}^{2}-2\hat{R}_{d}R_{d}\leq 0.$

Theorem C.6 follows directly from Eq. 72 and 73. ∎

##  Appendix D Bias of The Cross-Entropy Estimator

###### Theorem D.1.

The $\widehat{\mathcal{L}}$ estimator (Eq. 45) has the following bias:

(74)
$\begin{split}&\mathbb{E}_{c,y\sim\pi_{0}}\big{[}\widehat{\mathcal{L}}(\hat{R})\big{]}-\mathcal{L}(\hat{R})=\sum_{d\in
D}\frac{1}{\hat{\rho}_{d}}\big{(}\big{(}(\hat{\rho}_{d}-\rho_{d})R_{d}+\mathbb{E}_{y\sim\pi_{0}}\big{[}\hat{\beta}_{k(d)}-\beta_{k(d)}\big{]}\big{)}\log(\hat{R}_{d})\\\
&\hskip
102.43008pt+\big{(}\mathbb{E}_{y\sim\pi_{0}}\big{[}\beta_{k(d)}-\hat{\beta}_{k(d)}-\hat{\alpha}_{k(d)}\big{]}+\hat{\rho}_{d}+(\rho_{d}-\hat{\rho}_{d})R_{d}\big{)}\log(1-\hat{R}_{d})\big{)}.\end{split}$

###### Proof.

First, we consider the expected value of $\widehat{\mathcal{L}}(\hat{R})$:

$\displaystyle\underset{c,y\sim\pi_{0}}{\mathbb{E}}\big{[}\widehat{\mathcal{L}}(\hat{R})\big{]}$
$\displaystyle=-\sum_{d\in
D}\frac{1}{\hat{\rho}_{d}}\big{(}\underset{c,y\sim\pi_{0}}{\mathbb{E}}\big{[}c(d)-\hat{\beta}_{k(d)}\big{]}\log(\hat{R}_{d})+\underset{c,y\sim\pi_{0}}{\mathbb{E}}\big{[}\hat{\alpha}_{k(d)}+\hat{\beta}_{k(d)}-c(d)\big{]}\log(1-\hat{R}_{d})\big{)}$
(75) $\displaystyle=-\sum_{d\in
D}\frac{1}{\hat{\rho}_{d}}\Big{(}\big{(}\rho_{d}R_{d}+\mathbb{E}_{y\sim\pi_{0}}\big{[}\beta_{k(d)}-\hat{\beta}_{k(d)}\big{]}\big{)}\log(\hat{R}_{d})$
$\displaystyle\hskip
51.21504pt+\big{(}\mathbb{E}_{y\sim\pi_{0}}\big{[}\hat{\alpha}_{k(d)}+\hat{\beta}_{k(d)}-\beta_{k(d)}\big{]}-\rho_{d}R_{d}\big{)}\log(1-\hat{R}_{d})\Big{)}.$

Subtract Eq. 29 from the result of Eq. D to prove Theorem D.1. ∎

###### Lemma D.2.

Following Lemma A.3 and Lemma C.2:

(76) $(\hat{\alpha}=\alpha\land(\forall d\in
D,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\rho_{d}\geq\tau))\longrightarrow(\forall
d\in D,\;\mathds{E}_{y\sim\pi_{0}}[\hat{\alpha}_{k(d)}]=\hat{\rho}_{d}).$

###### Theorem D.3.

$\widehat{\mathcal{L}}(\hat{R})$ is unbiased when $\hat{\alpha}$,
$\hat{\beta}$ and $\hat{\pi}_{0}$ are correctly estimated and clipping has no
effect:

(77) $(\hat{\alpha}=\alpha\land\hat{\beta}=\beta\land(\forall d\in
D,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\rho_{d}\geq\tau))\longrightarrow\mathbb{E}_{y\sim\pi_{0}}\big{[}\widehat{\mathcal{L}}(d)\big{]}=\mathcal{L}(d).$

###### Proof.

Theorem D.1 reveals an unbiasedness condition:

(78) $\Big{(}\forall d\in
D,\;\hat{\rho}_{d}=\rho_{d}\land\mathds{E}_{y\sim\pi_{0}}\big{[}\hat{\beta}_{k(d)}\big{]}=\mathds{E}_{y\sim\pi_{0}}\big{[}\beta_{k(d)}\big{]}\land\mathds{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right]=\hat{\rho}_{d}\Big{)}\rightarrow\mathds{E}_{y\sim\pi_{0}}\big{[}\widehat{\mathcal{L}}(\hat{R})\big{]}=\mathcal{L}(\hat{R}).$

From Lemma A.3, A.4 and D.2 it follows that:

(79) $\displaystyle(\hat{\alpha}=\alpha\land\hat{\beta}=\beta\land(\forall
d\in D,\;\hat{\pi}_{0}(d)=\pi_{0}(d)\land\rho_{d}\geq\tau))$
$\displaystyle\hskip 71.13188pt\longrightarrow\big{(}\forall d\in
D,\;\hat{\rho}_{d}=\rho_{d}\land\mathds{E}_{y\sim\pi_{0}}\big{[}\hat{\beta}_{k(d)}\big{]}=\mathds{E}_{y\sim\pi_{0}}\left[\beta_{k(d)}\right]\land\mathds{E}_{y\sim\pi_{0}}\left[\hat{\alpha}_{k(d)}\right]=\hat{\rho}_{d}\big{)}.$

Combining Eq. 78 and 79 directly proves Theorem D.3. ∎

##  Appendix E Main results evaluated with Discounted cumulative gain

The main results presented in Section 8 used ECP (Eq. 7) as the metric of
performance. As argued in Section 3.2, we think ECP is the most appropriate
metric as it is based on the actual user model in the simulation, i.e. it
utilizes the true $\alpha$ and $\beta$ values. Nevertheless, this makes it
harder to compare our results with previous work that relies on more
traditional metrics.

To better enable such comparisons, and to verify whether our conclusions
translate to other metrics, Table E reports the same results as Table 7 but in
terms of normalized discounted cumulative gain (NDCG) (Järvelin and
Kekäläinen, 2002):

(80) $DCG@K(y)=\sum^{K}_{k=1}\frac{R_{y_{k}}}{\log_{2}(k+1)},\qquad
NDCG@K(y)=\frac{DCG@K(y)}{\max_{y^{\prime}}DCG@K(y^{\prime})}.$

Comparing Table 7 with Table E reveals that both tables show the same trends
and relative differences between the different methods. This confirms that the
conclusions that were made from comparisons in Section 8 are still valid when
measuring with NDCG instead of ECP. In other words, Table E shows that even
when evaluating with NDCG, the performance improvements of DR and DM over IPS
and other baselines remain very clear.

Table 2.  NDCG reached using different estimators in three different settings
and three datasets for several $N$ values: the number of displayed rankings in
the simulated training set. In addition, the NDCG of the logging policy and a
model trained on the ground-truth (Full-Information) are included to indicate
estimated lower and upper bounds on possible performance respectively. Top
part: NDCG@5 in the top-5 setting with known $\alpha$ and $\beta$ bias
parameters; middle part: NDCG@5 in the top-5 setting with estimated
$\hat{\alpha}$ and $\hat{\beta}$; bottom part: NDCG in the full-ranking
setting (no cutoff) with known $\alpha$ and $\beta$ bias parameters. Reported
numbers are averages over 20 independent runs evaluated on held-out test-sets,
brackets display the standard deviation (logging policy deviation is ommitted
since it did not vary between runs). Bold numbers indicate the highest
performance per setting, dataset and $N$ combination. Statistical differences
with our DR estimator are measured via a two-sided student-t test, ▼ and ▲
indicate methods with significantly lower or higher NDCG with $p<0.01$
respectively; additionally, ▽ and △ indicate significant differences with
$p<0.05$.

| Yahoo! Webscope | MSLR-WEB30k | Istella
---|---|---|---
| $N=10^{4}$ | $N=10^{6}$ | $N=10^{9}$ | $N=10^{4}$ | $N=10^{6}$ | $N=10^{9}$ | $N=10^{4}$ | $N=10^{6}$ | $N=10^{9}$
| _Top-5 Setting with Known Bias Parameters_
Logging | 0.700 (0.000)- | 0.700 (0.000)- | 0.700 (0.000)- | 0.465 (0.002)- | 0.465 (0.002)- | 0.465 (0.002)- | 0.539 (0.000)- | 0.539 (0.000)- | 0.539 (0.000)-
Full-Info. | 0.767 (0.002)▲ | 0.767 (0.002)▲ | 0.767 (0.002)▲ | 0.541 (0.002)▲ | 0.541 (0.002)▲ | 0.541 (0.002)- | 0.639 (0.007)▲ | 0.639 (0.007)▲ | 0.639 (0.007)▽
Naive | 0.706 (0.004)▼ | 0.708 (0.001)▼ | 0.709 (0.001)▼ | 0.467 (0.003)▼ | 0.470 (0.003)▼ | 0.470 (0.002)▼ | 0.544 (0.006)▼ | 0.554 (0.002)▼ | 0.555 (0.001)▼
DM (prev) | 0.716 (0.005)▼ | 0.727 (0.004)▼ | 0.740 (0.004)▼ | 0.475 (0.011)▽ | 0.510 (0.008)▼ | 0.506 (0.004)▼ | 0.493 (0.023)▼ | 0.543 (0.014)▼ | 0.609 (0.003)▼
RPS | 0.727 (0.003)- | 0.747 (0.002)▼ | 0.748 (0.003)▼ | 0.500 (0.004)▲ | 0.527 (0.003)▼ | 0.528 (0.003)▼ | 0.577 (0.002)▲ | 0.600 (0.003)▼ | 0.601 (0.003)▼
IPS | 0.702 (0.004)▼ | 0.734 (0.003)▼ | 0.752 (0.002)▼ | 0.465 (0.002)▼ | 0.500 (0.003)▼ | 0.522 (0.004)▼ | 0.545 (0.011)▼ | 0.602 (0.004)▼ | 0.625 (0.004)▼
DM (ours) | 0.727 (0.003)- | 0.752 (0.002)▼ | 0.762 (0.001)▼ | 0.477 (0.016)- | 0.529 (0.003)▼ | 0.536 (0.003)▼ | 0.551 (0.011)▼ | 0.609 (0.007)▼ | 0.630 (0.005)▼
DR (ours) | 0.730 (0.005)- | 0.755 (0.002)- | 0.765 (0.001)- | 0.484 (0.012)- | 0.534 (0.003)- | 0.541 (0.002)- | 0.566 (0.012)- | 0.626 (0.008)- | 0.642 (0.003)-
| _Top-5 Setting with Estimated Bias Parameters_
Logging | 0.700 (0.000)- | 0.700 (0.000)- | 0.700 (0.000)- | 0.465 (0.002)- | 0.465 (0.002)- | 0.465 (0.002)- | 0.539 (0.000)- | 0.539 (0.000)- | 0.539 (0.000)-
Full-Info. | 0.767 (0.002)▲ | 0.767 (0.002)▲ | 0.767 (0.002)▲ | 0.541 (0.002)▲ | 0.541 (0.002)▲ | 0.541 (0.002)- | 0.639 (0.007)▲ | 0.639 (0.007)▲ | 0.639 (0.007)-
Naive | 0.705 (0.003)▼ | 0.708 (0.001)▼ | 0.709 (0.001)▼ | 0.466 (0.003)▼ | 0.470 (0.003)▼ | 0.470 (0.002)▼ | 0.543 (0.006)▽ | 0.555 (0.002)▼ | 0.554 (0.004)▼
DM (prev) | 0.727 (0.004)▽ | 0.742 (0.004)▼ | 0.737 (0.002)▼ | 0.481 (0.012)- | 0.507 (0.009)▼ | 0.501 (0.005)▼ | 0.532 (0.013)▼ | 0.566 (0.016)▼ | 0.612 (0.005)▼
RPS | 0.726 (0.003)▼ | 0.748 (0.002)▼ | 0.748 (0.003)▼ | 0.500 (0.004)▲ | 0.526 (0.003)▼ | 0.528 (0.003)▼ | 0.579 (0.003)▲ | 0.600 (0.002)▼ | 0.601 (0.003)▼
IPS | 0.703 (0.004)▼ | 0.735 (0.003)▼ | 0.753 (0.001)▼ | 0.465 (0.002)▼ | 0.498 (0.004)▼ | 0.520 (0.004)▼ | 0.545 (0.011)- | 0.600 (0.004)▼ | 0.623 (0.006)▼
DM (ours) | 0.730 (0.004)- | 0.750 (0.005)▼ | 0.763 (0.002)▽ | 0.473 (0.010)- | 0.528 (0.006)▼ | 0.537 (0.003)▼ | 0.532 (0.015)▼ | 0.603 (0.014)▼ | 0.629 (0.003)▼
DR (ours) | 0.730 (0.003)- | 0.756 (0.001)- | 0.765 (0.002)- | 0.479 (0.012)- | 0.532 (0.004)- | 0.541 (0.002)- | 0.552 (0.019)- | 0.624 (0.005)- | 0.640 (0.004)-
| _Full-Ranking Setting with Known Bias Parameters_
Logging | 0.858 (0.000)- | 0.858 (0.000)- | 0.858 (0.000)- | 0.746 (0.001)- | 0.746 (0.001)- | 0.746 (0.001)- | 0.728 (0.000)- | 0.728 (0.000)- | 0.728 (0.000)-
Full-Info. | 0.888 (0.001)▲ | 0.888 (0.001)▲ | 0.888 (0.001)- | 0.775 (0.002)▲ | 0.775 (0.002)▲ | 0.775 (0.002)- | 0.785 (0.003)▲ | 0.785 (0.003)▲ | 0.785 (0.003)▽
Naive | 0.859 (0.002)▼ | 0.859 (0.000)▼ | 0.859 (0.000)▼ | 0.745 (0.001)▼ | 0.746 (0.001)▼ | 0.746 (0.001)▼ | 0.724 (0.003)▼ | 0.729 (0.001)▼ | 0.729 (0.001)▼
DM (prev) | 0.858 (0.001)▼ | 0.856 (0.001)▼ | 0.849 (0.008)▼ | 0.743 (0.002)▼ | 0.743 (0.002)▼ | 0.744 (0.002)▼ | 0.732 (0.001)▼ | 0.737 (0.001)▼ | 0.736 (0.002)▼
RPS | 0.861 (0.001)▼ | 0.861 (0.000)▼ | 0.861 (0.000)▼ | 0.748 (0.002)▼ | 0.748 (0.001)▼ | 0.610 (0.001)▼ | 0.737 (0.004)▽ | 0.741 (0.000)▼ | 0.701 (0.014)▼
IPS | 0.859 (0.003)▼ | 0.877 (0.001)▼ | 0.888 (0.001)- | 0.745 (0.001)▼ | 0.762 (0.002)▼ | 0.774 (0.002)- | 0.725 (0.005)▼ | 0.769 (0.004)▼ | 0.787 (0.003)-
DM (ours) | 0.866 (0.002)- | 0.881 (0.001)▼ | 0.885 (0.002)▼ | 0.752 (0.006)▽ | 0.772 (0.002)- | 0.774 (0.002)- | 0.738 (0.007)- | 0.783 (0.003)▲ | 0.793 (0.002)▲
DR (ours) | 0.866 (0.003)- | 0.882 (0.001)- | 0.888 (0.001)- | 0.755 (0.004)- | 0.771 (0.002)- | 0.774 (0.002)- | 0.741 (0.005)- | 0.779 (0.004)- | 0.787 (0.003)-

## References

  * (1)
  * Agarwal et al. (2019a) Aman Agarwal, Kenta Takatsu, Ivan Zaitsev, and Thorsten Joachims. 2019a.  A General Framework for Counterfactual Learning-to-Rank. In _Proceedings of the 42nd International ACM SIGIR Conference on Research & Development in Information Retrieval_. ACM, 5–14.
  * Agarwal et al. (2019b) Aman Agarwal, Xuanhui Wang, Cheng Li, Michael Bendersky, and Marc Najork. 2019b.  Addressing Trust Bias for Unbiased Learning-to-Rank. In _The World Wide Web Conference_. ACM, 4–14.
  * Agarwal et al. (2019c) Aman Agarwal, Ivan Zaitsev, Xuanhui Wang, Cheng Li, Marc Najork, and Thorsten Joachims. 2019c.  Estimating Position Bias without Intrusive Interventions. In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_. ACM, 474–482.
  * Ai et al. (2021) Qingyao Ai, Tao Yang, Huazheng Wang, and Jiaxin Mao. 2021\.  Unbiased Learning to Rank: Online or Offline?  _ACM Transactions on Information Systems (TOIS)_ 39, 2 (2021), 1–29.
  * Bekker et al. (2019) Jessa Bekker, Pieter Robberechts, and Jesse Davis. 2019\.  Beyond the Selected Completely at Random Assumption for Learning from Positive and Unlabeled Data. In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. Springer, 71–85.
  * Burges (2010) Christopher J.C. Burges. 2010\.  _From RankNet to LambdaRank to LambdaMART: An Overview_.  Technical Report MSR-TR-2010-82. Microsoft.
  * Chapelle and Chang (2011) Olivier Chapelle and Yi Chang. 2011.  Yahoo! Learning to Rank Challenge Overview.  _Journal of Machine Learning Research_ 14 (2011), 1–24.
  * Craswell et al. (2008) Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey. 2008.  An Experimental Comparison of Click Position-Bias Models. In _Proceedings of the 2008 International Conference on Web Search and Data Mining_. 87–94.
  * Dato et al. (2016) Domenico Dato, Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, Nicola Tonellotto, and Rossano Venturini. 2016\.  Fast Ranking with Additive Ensembles of Oblivious and Non-Oblivious Regression Trees.  _ACM Transactions on Information Systems (TOIS)_ 35, 2 (2016), Article 15.
  * Dudík et al. (2014) Miroslav Dudík, Dumitru Erhan, John Langford, and Lihong Li. 2014.  Doubly Robust Policy Evaluation and Optimization.  _Statist. Sci._ 29, 4 (2014), 485–511.
  * Fang et al. (2019) Zhichong Fang, Aman Agarwal, and Thorsten Joachims. 2019\.  Intervention Harvesting for Context-Dependent Examination-Bias estimation. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 825–834.
  * Hofmann et al. (2013) Katja Hofmann, Anne Schuth, Shimon Whiteson, and Maarten de Rijke. 2013.  Reusing Historical Interaction Data for Faster Online Learning to Rank for IR. In _Proceedings of the Sixth ACM International Conference on Web Search and Data Mining_. ACM, 183–192.
  * Horvitz and Thompson (1952) Daniel G Horvitz and Donovan J Thompson. 1952.  A Generalization of Sampling Without Replacement from a Finite Universe.  _Journal of the American statistical Association_ 47, 260 (1952), 663–685.
  * Jagerman et al. (2020) Rolf Jagerman, Ilya Markov, and Maarten De Rijke. 2020\.  Safe Exploration for Optimizing Contextual Bandits.  _ACM Transactions on Information Systems (TOIS)_ 38, 3 (2020), 1–23.
  * Järvelin and Kekäläinen (2002) Kalervo Järvelin and Jaana Kekäläinen. 2002.  Cumulated Gain-Based Evaluation of IR Techniques.  _ACM Transactions on Information Systems (TOIS)_ 20, 4 (2002), 422–446.
  * Joachims (2002) Thorsten Joachims. 2002\.  Optimizing Search Engines Using Clickthrough Data. In _Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM, 133–142.
  * Joachims et al. (2017a) Thorsten Joachims, Laura Granka, Bing Pan, Helene Hembrooke, and Geri Gay. 2017a.  Accurately Interpreting Clickthrough Data as Implicit Feedback. In _ACM SIGIR Forum_ , Vol. 51. Acm New York, NY, USA, 4–11.
  * Joachims et al. (2017b) Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. 2017b.  Unbiased Learning-to-Rank with Biased Feedback. In _Proceedings of the Tenth ACM International Conference on Web Search and Data Mining_. ACM, 781–789.
  * Kang et al. (2007) Joseph DY Kang, Joseph L Schafer, et al. 2007\.  Demystifying Double Robustness: A Comparison of Alternative Strategies for Estimating a Population Mean from Incomplete Data.  _Statistical science_ 22, 4 (2007), 523–539.
  * Kiyohara et al. (2022) Haruka Kiyohara, Yuta Saito, Tatsuya Matsuhiro, Yusuke Narita, Nobuyuki Shimizu, and Yasuo Yamamoto. 2022\.  Doubly Robust Off-Policy Evaluation for Ranking Policies Under the Cascade Behavior Model. In _Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining_. 487–497.
  * Komiyama et al. (2015) Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. 2015\.  Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays. In _Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37_ (Lille, France) _(ICML’15)_. JMLR.org, 1152–1161.
  * Lagrée et al. (2016) Paul Lagrée, Claire Vernade, and Olivier Cappé. 2016\.  Multiple-Play Bandits in the Position-Based Model. In _Advances in Neural Information Processing Systems_. 1597–1605.
  * Li et al. (2018) Shuai Li, Yasin Abbasi-Yadkori, Branislav Kveton, S Muthukrishnan, Vishwa Vinay, and Zheng Wen. 2018.  Offline Evaluation of Ranking Policies with Click Models. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. ACM, 1685–1694.
  * Liu (2009) Tie-Yan Liu. 2009\.  Learning to Rank for Information Retrieval.  _Foundations and Trends in Information Retrieval_ 3, 3 (2009), 225–331.
  * Oosterhuis (2021) Harrie Oosterhuis. 2021\.  Computationally Efficient Optimization of Plackett-Luce Ranking Models for Relevance and Fairness. In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Virtual Event, Canada) _(SIGIR ’21)_. ACM, 1023–1032.
  * Oosterhuis and de Rijke (2018) Harrie Oosterhuis and Maarten de Rijke. 2018.  Differentiable Unbiased Online Learning to Rank. In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_. ACM, 1293–1302.
  * Oosterhuis and de Rijke (2019) Harrie Oosterhuis and Maarten de Rijke. 2019.  Optimizing Ranking Models in an Online Setting. In _Advances in Information Retrieval_. Springer International Publishing, Cham, 382–396.
  * Oosterhuis and de Rijke (2020) Harrie Oosterhuis and Maarten de Rijke. 2020.  Policy-Aware Unbiased Learning to Rank for Top-k Rankings. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM, 489–498.
  * Oosterhuis and de Rijke (2021a) Harrie Oosterhuis and Maarten de Rijke. 2021a.  Unifying Online and Counterfactual Learning to Rank. In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining (WSDM’21)_. ACM.