{'fraction_non_alphanumeric': 0.02557415664170943, 'fraction_numerical': 0.003365020610751241, 'mean_word_length': 4.690761129727142, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Inverse Propensity Score based offline estimator for deterministic ranking lists using position bias

In this work, we present 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 validate 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.


Introduction
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 (OP E, 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].

Offline estimation using a Position-Bias Model
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 (E), 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 (r).
We can use expectation maximisation [4] on logged clicked data to mea-sure P k (E), 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 (E) 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: where, n = number of all restaurants spread over all sessions K = maximum position on which click happened in that session π e (a i |x i ) = propensity of treatment policy for restaurant a i for given user x i π 0 (a i |x i ) = propensity of control policy for restaurant a i for given user x i α k r i,k = the reward of item i at position k (dcg, number of clicks, precision) (1) 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: where, θ p = position-bias-at-position-p θ k = position-bias-at-position-k (2) K = max(k) 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.

Experiments
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.

Multi-Objective Optimization Ranking Experiments
In this section, we evaluate a deterministic multi-objective ranking recommender for ranking restaurants. We ran an A/B test comparing a control 2-objective control recommender which combined an objective function for new restaurants as well as a rule based objective focussing on distance and restaurant quality, which resulted in a blended ranking between these two objectives. The variant recommender combines 3 objectives: new restaurants , rule-based, and an additional personalization objective.
To test the quality of our OPE, we take the ranking sessions and clicks from the control experimental data and compute the counterfactual ranking that would have been served by the variant policy in this session. We can then use our estimator and the logged feedback to evaluate the offline quality of the new policy. By comparing this measurement to the real variant policy performance in the A/B test, we can test the quality of our OPE framework.

Independent Assumption
In this experiment, we use the independence assumption. This also helps in making the action space tractable. Every restaurant click is taken as independent from other restaurant clicks. This means that one single appearance of a restaurant in the ranked list is one data point in the experiment. The number of all such appearances is denoted by n in equation 2 Then, CTR definition is modified to: where, c = number of clicks in that session Day by day results shown in Figure 1 show a very strong correlation between the OP E estimated from control logs and CT R value computed from treatment logs. There is a constant difference between the CT R and OP E value, which we are still trying to explain. In text search, users come in and input a text query in the text box and the ranked list of restaurants are shown. The K = max(k) in equation 2 is the maximum position at which the click/order happened in each session and n is the total number of sessions in which search was done and there was at least one result returned. We first run the position bias examination model on 1 month of logs in order to obtain P k (E).

Text Search Ranking Experiments
Then we take logs from control and treatment and join these sessions on the text query and restaurant to compute the position of each restaurant which was clicked in control. For control, we already have the position, but, for treatment, we take the median of all the possible positions, which we end up as a result of the join. Then, we compare it with actual click-throughrate of each day of the treatment. For computing the OPE, we use equation 2 Actual Click-Through-Rate is given by: where, c = #clicks in that session v = #views in that session (4) K as before is the maximum position at which the click happened in that session. By using the maximum position, we make the clicks in ranked list a bit more dependent on each other. This kind of assumption is also similar to [8].
The results are shown in Figure 2, which shows day by day comparison of CT R and OP E. As evident from the Figure, OP E is strongly correlated with the actual click-through-rate obtained in treatment. There is a constant difference between the OP E and actual CT R, which means OP E is a bit underestimated compared to the actual CT R. Variance of OPE is also less compared to typical IPS estimator. This could have been due to the position-bias values not converging properly. This could also have been due to the fact that control and treatment policies don't differ a lot from each other. At this time, we are still investigating this further.

Conclusion
In this work, we presented a novel way of computing IPS using a positionbias 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.

Acknowledgments
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.