A bandit algorithm for the joint optimization of budgets in an online advertising context

Online advertising, e.g., Search Engine marketing and Social advertisement, has become one of the principal form of marketing in the last decades. In particular, in Pay-per-Click models the advertiser displays its ad on a web page thanks to a publisher, who is paid for each click on the ad. Moreover, the allocation of the ads is determined resorting to auction mechanisms in which multiple advertisers bid for the available slots. In this context, then, the problem of choosing the best spending plan and an optimal bid, i.e., to choose a joint bid/budget allocation which maximizes the number of clicks when managing several advertising campaigns simultaneously, arises naturally. In this work we provide an online algorithm, called COMB-GP, belonging to the field of combinatorial bandits, that searches the optimal joint allocation of bid/budget over all the advertising campaigns using Gaussian Processes to perform function estimation and solving the optimization problem modeling it as an extension of a Multiple-Choice-Knapsack (MPK). Moreover, we derived an high probability upper bound on the regret O(sqrt(n)). Finally, we reported both synthetic and real experiments that validate the performances of our algorithm.

Il marketing online in tutte le sue forme, per esempio la pubblicità sui motori di ricerca e sulle piattaforme social, è diventato una delle forme di marketing più utilizzate negli ultimi anni. In particolare, nei modelli “Pay-per-Click” l’inserzionista pubblica i suoi banner pubblicitari su internet attraverso le piattaforme di alcuni editori che vengono poi pagati per ogni click ricevuto. Inoltre, l’assegnazione degli spot pubblicitari è regolata attraveso delle aste fra i vari inserzionisti. In questo contesto, perciò, diventa fondamentale la scelta di un piano di investimento ottimo, che consiste nell’allocazione di una coppia bid/budget per massimizzare il numero di click ricevuti, sopratutto nel caso di gestione di più campagne pubblicitarie in parallelo. Per risolvere questo problema in questa tesi viene proposto un algoritmo che appartiene al filone dei bandit combinatori, chiamato COMB-GP, che ricerca l’allocazione ottima dei bid/budget per tutte le campagne, utilizzando i Processi Gaussiani per la stima di funzioni incognite e risolvendo il problema di ottimizzazione fra le varie campagne modellandolo come una variante dei problemi Multiple-Choice-Knapsack (MPK). Inoltre, in questo lavoro viene anche dimostrato che il regret dell’algoritmo è limitato superiormente da una funzione che ha un andamento O(sqrt(n)). Infine vengono descritti ed analizzati sia degli esperimenti basati su dati simulati, sia un caso basato su dati reali che confermano empiricamente le buone prestazioni dell’algoritmo.