A combinatorial-bandit algorithm for the online joint bid/budget optimization of pay-per-click advertising campaigns.

Abstract

Il pay-per-click comprende formati diversi — search, contextual, social — per un investimento complessivo di oltre 140 miliardi di dollari l'anno. Una campagna è fatta di più sottocampagne, ciascuna con un annuncio diverso, e di un budget giornaliero complessivo. L'allocazione degli annunci è regolata da meccanismi d'asta.

In questo paper proponiamo, per la prima volta per quanto ne sappiamo, un algoritmo per l'ottimizzazione online e congiunta di bid e budget nelle campagne pay-per-click multicanale. Formuliamo il problema come un combinatorial bandit problem: usiamo i Gaussian Processes per stimare le funzioni stocastiche, tecniche di Bayesian bandit per gestire il trade-off tra exploration ed exploitation e la programmazione dinamica per risolvere una variante del Multiple-Choice Knapsack problem.

Valutiamo l'algoritmo sperimentalmente sia in simulazione, con uno scenario sintetico generato da un dataset Yahoo!, sia in un'applicazione reale durata due mesi.