Research Card on how to attribute positive outcomes to touchpoints in a sequence of displays leading to a conversion.

Paper: Fixed Point Label Attribution for Real-Time Bidding
Authors: Martin Bompaire, Antoine Désir, Benjamin Heymann
Category: Operations Research
Revue: Manufacturing and Service Operations Management

Why did we work on this topic (the problem we want to solve)?

In display advertising, advertisers usually provide rewards at the user level, meaning they reward when a user makes a purchase or takes a specific action. However, our machine learning models need to predict the value of each individual ad, which requires these rewards to be tied to individual ad displays to train effectively. This mismatch creates a fundamental problem in accurately attributing rewards to individual displays before using them in a learning algorithm, referred to as the label attribution problem.

While we usually pretend our datasets have the following schema:

The truth is that the reward is first associated to a user before being spread among several displays with label attribution:

How did we proceed? What did we find?

We developed an approach called the Fixed Point Label Attribution (FiPLA) Algorithm to solve the label attribution problem. The Fixed Point Label Attribution Algorithm iteratively updates the label attribution mechanism and the machine learning model in three steps. First, it generates a training dataset by attributing user-level rewards to individual display opportunities using the current label attribution mechanism. Second, it trains a machine learning model on this dataset to predict display-level rewards. Third, it updates the label attribution mechanism using the predictions from the model, redistributing the user-level rewards proportionally to the predicted values of the displays. This process repeats until the label attribution and model predictions converge, ensuring they are aligned.

Observe that the label attribution mechanism is updated using the predictions from the model. When the process converges, the labels generated by the updated mechanism should lead to predictions that do not change significantly in subsequent iterations: this is the fixed point. We tested our solution using a large-scale publicly available dataset from Criteo and found that our algorithm improves the attribution of user-level rewards to display-level rewards, leading to better performance in predicting the value of display opportunities. Better performance means in particular (a) that we are better at predicting on a timeline if a user will convert or not, (b) if we simulate a market competition and use the output of our model for bidding, instead of the baseline, we observe a notable increase in profit.

What is the originality here?

First, the paper properly formalizes the label attribution problem, which is often overlooked despite being ubiquitous. Second, it proposes a principled approach to solve it with the FiPLA Algorithm. This novel method uses a fixed-point approach to iteratively refine the label attribution and valuation functions, providing a scalable and robust solution that can be integrated into existing machine learning pipelines. This method significantly improves the accuracy and robustness of training models in real-time bidding scenarios.

Check all our research cards 👇
https://medium.com/criteo-engineering/research-cards/home