Online joint bid/daily budget optimization of Internet advertising campaigns

Pay-per-click advertising includes various formats (e.g., search, contextual, social) with a total investment of more than 200 billion USD per year worldwide. An advertiser is given a daily budget to allocate over several campaigns, mainly distinguishing for the ad, target, or channel. Furthermore, publishers choose the ads to display and how to allocate them employing auctioning mechanisms, in which, every day and for each campaign, the advertisers set a bid corresponding to the maximum amount of money per click they are willing to pay and the fraction of the daily budget to invest. In this paper, we study the problem of automating the online joint bid/daily budget optimization of pay-per-click advertising campaigns over multiple channels, and we face the challenging goal of designing techniques with theoretical guarantees that can be applied in real-world applications, where, commonly, data scarcity is a crucial issue. We formulate our problem as a combinatorial semi-bandit problem, which requires solving a special case of the Multiple-Choice Knapsack problem every day. Furthermore, we address data scarcity by designing a model for the dependency of the number of clicks on the bid and daily budget, requiring few parameters at the cost of mild regularity assumptions. We propose two algorithms—the first is randomized, while the second is deterministic—and show that they suffer from a regret that is upper bounded with high probability as O˜(T), where T is the time horizon of the learning process. We experimentally evaluate our algorithms with synthetic settings generated from real data provided by Yahoo!, and we present the results of adopting our algorithms in a real-world application with a daily spent of 1,000 Euros for more than one year.