Digital advertising revenue growth rate has on average remained a double-digit one for more than two decades, with the revenue reaching a total of $124.6 billion in 2019. Such a trend remarks the incredible run of internet advertising, resulted from the continued shift from traditional advertising and the rise of the digital realm. In online advertising auctions, advertisers’ goal is usually to set a bid — the maximum amount of money they are willing to pay for a click — to balance the tradeoff between achieving high volumes, maximizing the sales of the products to advertise, and high profitability, that is maximizing the Return-On-Investment (ROI). However, state-of-the-art methods for bid optimization focus on maximizing volumes without guaranteeing to meet ROI constraints. The aim of this thesis is to deal with this issue, providing an online learning algorithm for safe bid optimization, that satisfies the ROI constraints with high probability. We find that the optimization problem with ROI and budget constraints cannot be approximated within any strictly positive factor unless P = NP. However, when dealing with a bids’ discretized space, the problem admits a pseudo-polynomial time algorithm based on dynamic programming, computing the optimal solution. Remarkably, we prove that no online learning algorithm violates the ROI constraint less than a linear number of times while guaranteeing sublinear pseudo-regret. Then, we show that we can obtain sublinear pseudo-regret adopting an algorithm from the state of the art of the GP combinatorial bandit field, such as the GCB algorithm proposed by Accabi et al. . However, it violates the ROI constraints during the learning process and at convergence. Then, we propose GCBsafe, a novel algorithm that provides guarantees on the satisfaction of the ROI constraints with high probability, but suffering of linear pseudo-regret. Finally, we evaluate the empirical performance of the two algorithms on synthetically generated advertising problems. Remarkably, GCBsafe provides good performance in terms of safety, while suffering from a small loss with respect to GCB in terms of cumulative revenue.
Il giro di affari per le campagne pubblicitarie online è in crescita esponenziale da più di due decadi, raggiungendo nel 2019 un ammontare pari a oltre le 120 migliaia di miliardi di dollari. Una crescita apparentemente inarrestabile, che si deve al ruolo sempre più centrale di Internet nel quotidiano e ai vantaggi del mezzo digitale. In una campagna pubblicitaria va impostata una bid — il prezzo massimo che si ha intenzione di pagare per ogni click — con l’obiettivo di massimizzare le vendite, pagando il meno possibile, per ottenere il massimo ritorno sugli investimenti (ROI). Trovare l’equilibrio tra massimizzare le vendite e il ritorno sugli investimenti (ROI) non è semplice, soprattutto considerando la mole di dati e di parametri forniti dalle piattaforme, ed è impraticabile senza alcun supporto automatico. Solitamente questo obiettivo si traduce nel massimizzare le vendite garantendo una soglia minima di ritorno sull’investimento (ROI), tuttavia, per quanto ne sappiamo, nessun algoritmo di ottimizzazione della bid e del budget esistente considera vincoli di ROI. L’obiettivo di questa tesi è quello di colmare questa lacuna fornendo un algoritmo per l’ottimizzazione della bid per le campagne pubblicitarie online, che soddisfi il vincolo di ROI con alta probabilità. Affrontando il problema, abbiamo dimostrato che nessun algoritmo online che violi il vincolo di ROI meno di un numero lineare di volte, può ottenere uno pseudo-regret sublineare, e l’abbiamo mostrato considerando GCB, un algoritmo dello stato dell’arte. Dunque presentiamo GCBsafe, un nuovo algoritmo per l’ottimizzazione della bid che garantisce la soddisfazione del vincolo di ROI con alta probabilità, ma con uno pseudo-regret lineare. Infine forniamo evidenze empiriche in un ambiente artificiale della bontà dell’algoritmo proposto, che ottiene ottimi risultati in termini di safety (garanzia di soddisfazione del vincolo), a discapito di una minima perdita in termini di guadagni rispetto a GCB.
Online bid optimization with return-on-investment constraints
Spadaro, Giorgio
2019/2020
Abstract
Digital advertising revenue growth rate has on average remained a double-digit one for more than two decades, with the revenue reaching a total of $124.6 billion in 2019. Such a trend remarks the incredible run of internet advertising, resulted from the continued shift from traditional advertising and the rise of the digital realm. In online advertising auctions, advertisers’ goal is usually to set a bid — the maximum amount of money they are willing to pay for a click — to balance the tradeoff between achieving high volumes, maximizing the sales of the products to advertise, and high profitability, that is maximizing the Return-On-Investment (ROI). However, state-of-the-art methods for bid optimization focus on maximizing volumes without guaranteeing to meet ROI constraints. The aim of this thesis is to deal with this issue, providing an online learning algorithm for safe bid optimization, that satisfies the ROI constraints with high probability. We find that the optimization problem with ROI and budget constraints cannot be approximated within any strictly positive factor unless P = NP. However, when dealing with a bids’ discretized space, the problem admits a pseudo-polynomial time algorithm based on dynamic programming, computing the optimal solution. Remarkably, we prove that no online learning algorithm violates the ROI constraint less than a linear number of times while guaranteeing sublinear pseudo-regret. Then, we show that we can obtain sublinear pseudo-regret adopting an algorithm from the state of the art of the GP combinatorial bandit field, such as the GCB algorithm proposed by Accabi et al. . However, it violates the ROI constraints during the learning process and at convergence. Then, we propose GCBsafe, a novel algorithm that provides guarantees on the satisfaction of the ROI constraints with high probability, but suffering of linear pseudo-regret. Finally, we evaluate the empirical performance of the two algorithms on synthetically generated advertising problems. Remarkably, GCBsafe provides good performance in terms of safety, while suffering from a small loss with respect to GCB in terms of cumulative revenue.| File | Dimensione | Formato | |
|---|---|---|---|
|
2019_12_Spadaro.pdf
accessibile in internet per tutti
Dimensione
642.13 kB
Formato
Adobe PDF
|
642.13 kB | Adobe PDF | Visualizza/Apri |
I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/10589/170793