Machine learning algorithms for the optimization of internet advertising campaigns

Online advertising revenue grew to 124.6 billion dollars in 2019, showing a 15.9% increase over the previous year. The opportunities provided by this market attracted wide attention of the scientific community as well as the industry that requires automatic tools to manage the main processes involved in this market. For this purpose, Artificial Intelligence can play a crucial role in providing techniques to support both publishers and advertisers in their tasks. In this thesis, we study the Internet advertising campaign optimization problem from the advertiser’ point-of-view. An advertising campaign is composed of a set of sub-campaigns that differ for the ad (e.g., including text or images), target (e.g., keywords, age, interests), or channel (e.g., search, social, display). In pay-per-click advertising, to get an ad impressed, the advertisers take part in an auction carried out by the publisher, in which they set a bid and a daily budget for each sub-campaign. The bid represents the maximum amount of money the advertisers are willing to pay for a click, whereas the daily budget is the maximum spend in a day for a sub-campaign. The advertisers’ goal is to create a set of sub-campaigns and for each of them set the bid/daily budget values that maximize the revenue under budget or return-on-investment constraints. This optimization problem is particularly challenging, as it includes many intricate subproblems. In this work, we study four different settings and we propose algorithms specifically crafted for each of them. First, we study the joint bid/budget optimization problem and we propose an online learning algorithm that combines Gaussian Processes estimation with Combinatorial-bandit techniques to find the optimal bid/budget values. We define four variants of our method and we derive high probability regret bounds of the order of O( T), where T is the learning time horizon. Second, we introduce the novel framework of safe bid optimization where the goal is to maximize the revenue while satisfying with high-probability some budget and return-on-investment constraints. We propose two algorithms, namely GCB and GCB saf e that differ on how they balance the revenue maximization and constraints violation. The first provides a sublinear bound on the regret but rarely satisfies the ROI constraints. The second keeps the probability of violating the constraints under a confidence δ at the cost of a linear pseudo-regret bound. Third, we study the problem of optimizing the target, the bids and the budgets of an advertising campaign. We formulate it as a Learning from Logged Bandit Feedback (LLBF) problem, and we propose an offline algorithm that computes a tree expansion of the target space to learn the partition that maximizes the revenue. Last, we study the problem of the sub-campaigns interdependence in the advertising campaign optimization. We provide an algorithm that employes Granger Causality to learn the campaign interdependence model from past data, Gaussian Processes to predict the sub-campaigns performance, and a dynamic programming procedure to compute the bid/daily budget allocation. Theoretical guarantees on the loss of the algorithm w.r.t. the clairvoyant solution are also proven. For all the problems mentioned above, we evaluate our approaches in both synthetic and real-world scenarios showing their superiority if compared with baselines and with the previous human campaign management.

Nel 2019, il revenue mondiale dell’Online Advertising ha raggiunto i 124.6 miliardi di dollari, con un incremento del 15,9% rispetto all’anno precedente. Le grandi opportunità di questo mercato hanno richiamato l’attenzione della comunità scientifica e delle aziende che necessitano sempre più di strumenti automatici per gestire i principali processi coinvolti. A tal proposito, l’Intelligenza Artificiale sta giocando un ruolo chiave nel fornire tecniche in grado di supportare sia i publisher che gli inserzionisti nei loro task. In questa tesi, ci focalizziamo sul punto di vista dell’inserzionista e analizziamo il problema dell’ottimizzazione di una campagna di advertising online. Una campagna di advertising è composta da un insieme di sottocampagne che differiscono tra loro per gli annunci (che ad esempio possono includere testi o immagini), per il target (es. età, interessi, sesso), o per il canale (es. search, social o display). Nel pay-per-click advertising, affinché un annuncio venga mostrato, gli inserzionisti devono prendere parte a un’asta indetta dal publisher nella quale devono impostare un valore di bid e di budget giornaliero per ciascuna sottocampagna. Il bid corrisponde al massimo prezzo che l’inserzionista è disposto a pagare per un click, mentre il daily budget è la massima spesa che è disposto a pagare in un giorno per una sottocampagna. L’obiettivo dell’inserzionista è quello di creare il set ottimale di sottocampagne e per ciascuna di esse impostare i valori di bid e di budget al fine di massimizzare il revenue e soddisfare dei vincoli di budget o di ROI. Questo problema di ottimizzazione è particolarmente complesso poiché richiede di risolvere intricati sottoproblemi. In questo lavoro, ci focalizziamo su quattro diversi scenari e presentiamo degli algoritmi specificamente progettati per ciascuno di essi. Il primo problema affrontato è quello dell’ottimizzazione congiunta del bid e del budget. Proponiamo un algoritmo di online learning che combina predizioni fornite dai Gaussian Process con tecniche di Combinatorial-bandit per trovare i valori di bid e di budget ottimi. Proponiamo quattro varianti del nostro metodo e deriviamo un bound sul regret dell’ordine di O(T), dove T è l’orizzonte temporale dell’apprendimento. Il secondo problema che affrontiamo è quello dell’ottimizzazione safe del bid, dove l’obiettivo è quello di massimizzare il revenue soddisfando, in alta probabilità, dei vincoli di budget e di ROI. Proponiamo due algoritmi, GCB e GCB safe che differiscono per come bilanciano l’ottimizzazione del revenue e la violazione dei vincoli. Il primo fornisce un bound sul regret sublineare ma senza alcuna garanzia sui vincoli di ROI. Il secondo, mantiene la probabilità di violare i vincoli sotto una certa soglia δ, al costo di un bound sul regret lineare. Il terzo problema affrontato è quello dell’ottimizzazione congiunta del target, delle bid e dei budget di una campagna di advertising. Formuliamo questo problema come un “Learning from Logged Bandit Feedback (LLBF) problem”, e proponiamo un algoritmo off-line che sfrutta un albero di ricerca per trovare sullo spazio del target la partizione che massimizza il revenue. Infine, analizziamo il problema dell’interdipendenza tra sottocampagne nell’ottimizzazione di una campagna di advertising. In particolare, presentiamo un algoritmo che utilizza un Granger Causality test per apprendere dai dati storici il modello di interdipendenza, i Gaussian Processs per predire le performance delle sottocampagne, e un algoritmo di dynamic-programming per il calcolo dell’allocazione ottima del bid e del budget. Infine, forniamo garanzie teoriche sulla loss del nostro approccio rispetto alla performance di un algoritmo chiaroveggente. Per tutti i problemi affrontati, valutiamo i nostri approcci sia in scenari sintetici che reali, mostrando la loro superiorità se confrontati con delle baseline o con la precendente gestione manuale delle campangne.