Unifying Online and Counterfactual Learning to Rank: A Novel Counterfactual Estimator that Effectively Utilizes Online Interventions (Extended Abstract)

1 Introduction

Ranking systems form the basis for most search and recommendation applications [Liu, 2009]. As a result, the quality of such systems can greatly impact the user experience, and thus, it is important that the underlying ranking models perform well. The field of unbiased Learning to Rank (LTR) considers methods that optimize ranking models based on user clicks, while correcting for the interaction biases that are present in these interactions. User interactions are a form of implicit feedback, and therefore, generally strongly affected by other factors than user preference [Joachims et al., 2005]. To be able to reliably learn from interaction data, the effect of factors other than preference has to be corrected for. In clicks on rankings three prevalent factors are well known: (i) position bias: users are less likely to examine, and thus click, lower ranked items [Craswell et al., 2008]; (ii) item-selection bias: users cannot click on items that are not displayed [Ovaisi et al., 2020; Oosterhuis and de Rijke, 2020a]; and (iii) trust bias: because users trust the ranking system, they are more likely to click on highly ranked items that they do not actually prefer [Agarwal et al., 2019; Joachims et al., 2005]. As a result of these forms of bias, which ranking system was used to gather clicks can have a substantial impact on the clicks that will be observed. Current unbiased LTR methods can be divided into two families: counterfactual approaches [Joachims et al., 2017] - that learn from historical data, i.e., clicks that have been logged in the past - and online approaches [Yue and Joachims, 2009] - that can perform interventions, i.e., they can decide what rankings will be shown to users. Recent work has noticed that some counterfactual methods can be applied as an online method [Jagerman et al., 2019], or vice versa [Zhuang and Zuccon, 2020; Ai et al., 2021]. Nonetheless, every existing method was designed for either the online or counterfactual setting, never both.

In this work, we propose a novel estimator for both counterfactual and online unbiased LTR from clicks: the intervention-aware estimator. The intervention-aware estimator builds on ideas that underlie the latest existing counterfactual methods: the policy-aware estimator [Oosterhuis and de Rijke, 2020a] and the affine estimator [Vardasbi et al., 2020]; and expands them to consider the effect of online interventions. It does so by considering how the effect of bias is changed by an intervention, and utilizes these differences in its unbiased estimation. As a result, the interventionaware estimator is both effective when applied as a counterfactual method, i.e., when learning from historical data, and as an online method where online interventions lead to enormous increases in efficiency. In our experimental results the intervention-aware estimator is shown to reach state-of-theart LTR performance in both online and counterfactual settings, and it is the only method that reaches top-performance in both settings.

2 Interactions with Rankings

This paper assumes that three forms of interaction bias occur: position bias, item-selection bias, and trust bias.

Position bias occurs because users only click an item after examining it, and users are more likely to examine items displayed at higher ranks [Craswell et al., 2008]. Thus the rank (a.k.a. position) at which an item is displayed heavily affects the probability of it being clicked. We model this bias using P(E = 1 | k): the probability that an item d displayed at rank k is examined by a user [Wang et al., 2018].

Item-selection bias occurs when some items have a zero probability of being examined in some displayed rankings [Ovaisi et al., 2020; Oosterhuis and de Rijke, 2020a]. This can happen because not all items are displayed to the user, or if the ranked list is so long that no user ever considers the entire list. We model this bias by stating: ∃k, ∀k′ , (k′ > k → P(E = 1 | k′ ) = 0), i.e., there exists a rank k such that items ranked lower than k have no chance of being examined.

Finally, trust bias occurs because users trust the ranking system and, consequently, are more likely to perceive top ranked items as relevant even when they are not [Joachims et al., 2005]. We model this bias using: P(C = 1 | k, R, E): the probability of a click conditioned on the displayed rank k, the relevance of the item R, and examination E.

To combine these three forms of bias into a single model, we follow Agarwal et al. [2019] and Vardasbi et al. [2020]:

Existing work has considered how the α and β values can be inferred accurately [Agarwal et al., 2019; Wang et al., 2018; Fang et al., 2019], we will assume they are known. With P(R = 1 | d, q) as the probability that an item d is deemed relevant w.r.t. query q by the user, we obtain the following compact notation for the click probability:

For a single ranking y, let k be the rank at which item d is displayed in y; we denote αk = αd,y and βk = βd,y. Finally, let π be a ranking policy used for logging clicks, where π(y | q) is the probability of π displaying ranking y for query q, then the click probability conditioned on π is:

3 Background: Counterfactual LTR

Most ranking metrics are additive w.r.t. documents; let P(q) be the probability that a user-issued query is query q, then the metric reward R commonly has the form:

Here, the λ function scores each item d depending on where π places d; λ can be chosen to match a desired metric, for instance, the popular Discounted Cumulative Gain (DCG) metric [Järvelin and Kekäläinen, 2002]:

Supervised LTR methods can optimize π to maximize R if relevance scores P (R = 1 | d, q) are known [Liu, 2009].

In the counterfactual LTR setting the relevance scores are not known, instead optimization is based on historical user interactions. Let D be a set of collected interaction data over T timesteps; for each timestep t it contains the user issued query qt, the logging policy ¯πt used to generate the displayed ranking ¯ yt, and the clicks ct received on the ranking:

where ct(d) ∈ {0, 1} indicates whether item d was clicked at timestep t. While clicks are indicative of relevance they are also affected by several forms of bias, as discussed in Section 2. Counterfactual LTR methods utilize estimators that correct for such bias to unbiasedly estimate the reward of a policy π. The prevalent methods introduce a function ˆ∆ that transforms a single click signal to correct for bias. The general estimate of the reward is:

ˆR(π |D) = 1 T ∑Tt=1 ∑d λ(d | π, q) ˆ∆(d | ¯πt, qt, ¯ yt, ct). (6) We note the important distinction between the policy π for which we estimate the reward, and the policy ¯πt that was used to gather interactions. During optimization only π is changed in order to maximize the estimated reward.

The original Inverse-Propensity-Scoring (IPS) estimator introduced by Wang et al. [2016] and Joachims et al. [2017] weights clicks according to examination probabilities:

This estimator results in unbiased optimization if no itemselection bias or trust bias is present, thus it can only correct for position bias, for a proof we refer to previous work by Joachims et al. [2017] and Vardasbi et al. [2020]. Oosterhuis and de Rijke [2020a] introduced policy-aware propensities for the IPS estimator to correct for item-selection bias, and Vardasbi et al. [2020] introduced an estimator based on affine corrections that can correct for trust bias. Currently, there is no estimator to correct for all three forms of bias together.

4 The Intervention-Oblivious Estimator

Before we propose our main contribution, the interventionaware estimator, we first introduce an estimator that simultaneously corrects for position bias, item-selection bias, and trust bias, without considering the effects of interventions.

First we note the probability of a click conditioned on a single logging policy πt can be expressed as:

where the expected values of α and β conditioned on πt are:

By reversing Eq. 8 the relevance probability can be obtained from the click probability. We introduce our interventionoblivious estimator, which applies this transformation to correct for bias:

The intervention-oblivious estimator brings together the policy-aware [Oosterhuis and de Rijke, 2020a] and affine estimators [Vardasbi et al., 2020]: on every click it applies an affine transformation based on the logging policy behavior. Unlike existing estimators, we can prove that the intervention-oblivious estimator is unbiased w.r.t. our assumed click model (Section 2). For the sake of brevity and because it is extremely analogous to the proof for Theorem 5.1, we omit this proof of unbiasedness in this extended abstract.

5 The Intervention-Aware Estimator

Existing estimators for counterfactual LTR are designed for a scenario where the logging policy is static: ∀(πt, πt′) ∈ D, πt = πt′ . While they are still unbiased when interventions do take place [Jagerman et al., 2019], they ignore any effect an intervention may have. In other words, any click is treated by considering how the corresponding logging policy treats the item, ignoring the treatment of all the other logging policies. Our goal is to introduce an estimator whose individual corrections are not only based on single logging policies, but instead consider the entire collection of logging policies used to gather the data D.

For ease of notation, we use ΠT for the set of policies that gathered the data in D: ΠT = {π1, π2, . . . , πT}. With the expected values of α and β conditioned on ΠT :

the probability of a click can be conditioned on the ΠT set is:

We propose our intervention-aware estimator that corrects for bias using the expectations conditioned on ΠT :

The salient difference with the intervention-oblivious estimator is that the expectations are conditioned on ΠT , all logging policies in D, instead of an individual logging policy πt. While the difference with the intervention-oblivious estimator may seem small, the resulting estimates can be very different, our experimental results show that this result in a sizeable reduction in variance.

To better understand the difference, consider an example where T = 100 and an item was ranked very highly but not clicked for t = 1 up to t = 99 but ranked lowly and clicked at t = 100. The intervention-oblivious estimator would assign a high weight to the click at t = 100 to compensate for the low rank at which it was displayed when clicked. Conversely, the intervention-aware estimator would assign a much lower weight to this click because it compensates both for the low rank at t = 100 but also the high ranking of the item received the first 99 timesteps. Thus we see how online interventions can create large differences between the two estimates.

Lastly, we note that when no interventions take place the intervention-oblivious estimator and intervention-aware estimators are equivalent. Because the intervention-aware estimator is the only existing counterfactual LTR estimator whose corrections are influenced by online interventions, we consider it an important step to bridge the gap between counterfactual and online LTR.

Finally, we prove that the intervention-aware estimator is unbiased w.r.t. our assumed click model (Section 2).

Theorem 5.1. The estimated reward ˆR (Eq. 6) using the intervention-aware estimator (Eq. 13) is unbiased w.r.t. the true reward R (Eq. 3) under two assumptions: (i) our click model (Eq. 2), and (ii) the click probability on every item, conditioned on ΠT , is correlated with relevance:

Proof. Using Eq. 12 and Eq. 14 the relevance probability can be derived from the click probability by:

Eq. 15 can be used to show that ˆ∆IA is an unbiased indicator of relevance:

Finally, combining Eq. 16 with Eq. 6 and Eq. 3 reveals that ˆR based on ˆ∆IA is unbiased w.r.t. R:

6 Experimental Setup

Our experiments aim to compare the performance of the intervention-aware estimator with existing LTR methods in both the online and counterfactual setting. 1 We use the semisynthetic experimental setup that is common in existing work on both online LTR [Hofmann et al., 2013; Oosterhuis and de Rijke, 2018; Oosterhuis and de Rijke, 2019; Zhuang and Zuccon, 2020] and counterfactual LTR [Joachims et al., 2017; Vardasbi et al., 2020; Ovaisi et al., 2020]. At each timestep, we simulate a user-issued query by uniformly sampling from the training and validation partitions of the Yahoo Webscope dataset [Chapelle and Chang, 2011], a dataset based on real-world commercial search logs. We apply Eq. 2 with α = [0.35, 0.53, 0.55, 0.54, 0.52] and β = [0.65, 0.26, 0.15, 0.11, 0.08] [Agarwal et al., 2019]; the relevance probabilities are based on the five-grade annotations from the dataset: P(R = 1 | d, q) = 0.25 · label(d, q).

To obtain a production ranker policy, we apply supervised LTR on 1% of the training partition [Joachims et al., 2017]. We vary the number of interventions per run; they are always evenly spread on an exponential scale, at each intervention the logging policy is replaced with the latest learned model. Ranking models are neural networks with two 32node hidden layers, optimized using policy gradients [Oosterhuis and de Rijke, 2020b]. The propensity weights for training clicks are clipped at 10/√|D| to reduce variance. The following baseline methods are used: (i) The policy-aware estimator [Oosterhuis and de Rijke, 2020a]. (ii) The affine estimator [Vardasbi et al., 2020]. (iii) Pairwise Differentiable Gradient Descent (PDGD) [Oosterhuis and de Rijke, 2018]. (iv) Biased-PDGD, PDGD without the debiasing weights. (v) Counterfactual Online Learning to Rank (COLTR) [Zhuang and Zuccon, 2020].

1 Our experimental implementation is publicly available at https: //github.com/HarrieO/2021wsdm-unifying-LTR.

7 Results and Discussion

For our comparison with existing counterfactual LTR methods, we consider Figure 1 which displays the performance of LTR using different counterfactual estimators.

The top of Figure 1 displays performance in the counterfactual setting where the logging policy is static. Very clearly the intervention-aware estimator quickly reaches a higher performance than the other methods, this is expected since it is the only unbiased estimator of the three. While the theory guarantees that intervention-aware estimator will converge at the optimal performance, we are unable to observe the number of queries it requires to do so. The bottom of Figure 1 regards an online setting with 50 online interventions. The online interventions have a clear positive effect leading to a higher mean performance for all estimators. However, this also introduces an enormous amount of variance to the policy-aware and intervention-oblivious estimators. In stark contrast, the intervention-aware estimator hardly has an increase in variance while it also learns much faster than the other estimators. Moreover, it is now able to reach optimal performance with roughly a million logged queries.

We therefore conclude that the intervention-aware estimator leads to higher performance than existing counterfactual estimators, especially when online interventions take place.

Figure 2 compares the performance of the interventionaware estimator with online LTR methods. The top of Figure 2 shows that the intervention-aware estimator applied with 100 interventions provides performance comparable to PDGD applied fully online (an intervention at each query). We can conclude that, aside from a small difference before 2 · 104 queries, the intervention-aware estimator appears to match state-of-the-art online LTR performance without needing the costly overhead of constant interventions.

The bottom of Figure 2 considers the performance of PDGD when not applied fully online. We see that PDGD converges at very suboptimal performance when provided 100 or less interventions; this observation does not contradict the existing theory since PDGD is not proven to be unbiased w.r.t. ranking metrics. Its suboptimal convergence in not fullyonline settings makes PDGD very unreliable in practice; we conclude that the intervention-aware estimator remains the safer and more reliable choice for these settings.

8 Conclusion

This paper has introduced an intervention-aware estimator which corrects for position-bias, trust-bias, and itemselection bias, and considers the effect of online interventions. Our results show that the intervention-aware estimator outperforms existing counterfactual LTR estimators, and greatly benefits from online interventions. Moreover, with only 100 interventions it can reach performance comparable to state-of-the-art online LTR methods. Because the intervention-aware estimator appears to be the most reliable method for both counterfactual and online LTR, we hope its introduction further unifies the division between these fields.

Acknowledgments

This research was partially supported by the Netherlands Organisation for Scientific Research (NWO) under project nr 612.001.551. All content represents the opinion of the authors, which is not necessarily shared or endorsed by their respective employers and/or sponsors.