Inverse Propensity Score based offline estimator for deterministic ranking lists using position bias

The mission of Just Eat Takeaway is to empower users’ every food moment. A big part of fulfilling that mission is ensuring that we show the right restaurants to the right users. To do this, we design large-scale machine learning recommendation systems that can learn which types of users tend to enjoy which types of restaurants.

A crucial part of this process is being able to compare the quality of different recommendation systems, in order to decide which is most effective. The gold standard approach to this evaluation problem is A/B testing - allow the different systems to recommend items to randomly selected groups of users, and compare their relative performance.

However, A/B testing is both slow, taking time to reach sufficient statistical power, and expensive [5, 1] if we serve poor recommendations to a subset of users.

Therefore, evaluating recommender systems in offline fashion without running A/B tests is of significant importance. These offline approaches avoid serving experimental recommenders to users, and instead evaluates them using old online data, where users were served recommendations from a different system. Metrics such as Root Mean Squared Error [2] Mean Average Precision, Normalized Discounted Cumulative Gain, Mean Reciprocal Rank and Hit Rate have been used repeatedly for offline evaluation.

All of these evaluation approaches are prone to selection, presentation and position biases [11, 6] and therefore the results from offline evaluation are often inaccurate, meaning the evaluated algorithms perform differently when served online than the offline evaluation predicted.

For this reason, “offline” approaches to evaluation have been subject to intense research [7] with the goal of coming up with offline performance indicators, which match the online performance. Counterfactual off-policy evaluation ($OPE$, henceforth) based approaches often make use of Inverse Propensity Score, also known as importance sampling [10]. However, IPS requires us to use a stochastic logging policy. In practice, this means that our recommender systems output a probability distribution over all the possible items that could be recommended, and we choose our recommendations by drawing them from this distribution. Our recommender will assign high probabilities to items it thinks are good recommendations, and low probabilities to poor items, but we will occasionally serve very different recommendations to those the recommender thinks is best.

If we want to evaluate a different recommender using the data acquired, this randomness is crucial, as it means we will sometimes have recommendations in our logged data that are close to what our new recommender would have selected.

However, introducing this randomness comes at a clear monetary cost, and it can be hard to justify paying this concrete cost for the less well defined benefit of faster recommender iteration. Ideally, we would like some way to evaluate non-random (deterministic) recommender systems offline. In the next section, we describe our approach to the counterfactual offline estimator we used for measuring the performance of deterministic ranking lists by making use of position-bias model [14].

The propensity used in IPS is the probability that an item was selected to be displayed to a user. Position-bias modelling, in particular the examination model, gives us an alternative definition of item propensity. The examination model imagines that when a user sees a list of recommendations, they randomly choose a set of items to examine.

Each list position, k, has an associated examination probability, $P_k\left(E\right)$, which usually is at its highest at the top of the list, and then decays to 0 for items in lower positions. From the list of examined items, the user chooses items which are relevant to them and clicks those which are. This process is modelled by assigning each item-user pair a probability of relevance $P_{i,u}\left(r\right)$.

We can use expectation maximisation [4] on logged clicked data to measure $P_k\left(E\right)$, the probability that an item is examined in each position [14]. Despite its simplicity, the examination model has been shown to predict user behaviour well [3], and we have used it with success on our ranking data in other applications.

$P_k\left(E\right)$ gives us the probability distribution of restaurants being examined from top to bottom. We replace the propensity of an item being shown to a user with the propensity that they examine it. We argue that even if the ranked list is deterministic in nature, the user actually examines/sees the restaurant as a probability and under this assumption, the traditional IPS estimator still applies. So, we are doing IPS, but we’re doing it with estimated propensities, which are coming from an examination model [14].

For the new policy, we get scores from new algorithm, rank restaurants according to those scores and find what position $p$ the restaurant holds in this ranking according to the new policy and then find the position-bias for each restaurant in this new ranking. For the logging policy, we find the position $k$ of each restaurant in which it was originally shown and then find its position-bias. Hence, our estimator becomes as follows:

We also assume that the users come from the top and actions below the last order/click can be ignored. We only consider those restaurants above the clicked restaurant as true negative samples, as they were likely to have been seen. This assumption is similar to that of the RIPS estimator [9]. Hence our estimator further becomes:

$K=max\left(k\right)$ is the maximum position at which the click/order happened in each session and $n$ is the total number of sessions, in which at least one restaurant was shown in the ranked list.

There is also a problem associated with equation 2 that most of the restaurants at lower ranks have a probability close to 0 of being examined. [12] and [13] address this sort of problem. This issue will increase the variance of our estimator, but as our position bias decays only slowly to 0, we have not found significant variance problems.

In this section, we describe the experiments done using two different A/B tests. We first compute our OPE score given by equation 2 for the novel recommender in both the experiments and compare it with the actual CTR obtained for the variant recommender.

In this work, we presented a novel way of computing IPS using a position-bias model for deterministic logging policies. This technique significantly widens the policies on which OPE can be used. We validated this technique using two different experiments on industry-scale data. The OPE results are clearly strongly correlated with the online results, with some constant bias. The estimator requires the examination model to be a reasonably accurate approximation of real user behaviour.

We would like to thank Lauren Rodney, Erdem Biyik, Hakan Simsek, Liza Chukreeva and Rishi Kumar for helping us run these experiments. We would also like to thank Sabrican Özan, Max Knobbout and Boris Slesar for helping us review this article. Finally, we would like to thank Ozlem Ozer for sponsoring this project.