Stochastic bandits for multi-platform budget optimization in online advertising

The Web Conference


We study the problem of an online advertising system that wants to optimally spend an advertiser’s given budget for a campaign across multiple platforms, without knowing the value for showing an ad to the users on those platforms. We model this challenging practical application as a Stochastic Bandits with Knapsacks problem over T rounds of bidding with the set of arms given by the set of distinct bidding m-tuples, where m is the number of platforms. We modify the algorithm proposed in Badanidiyuru et al., [11] to extend it to the case of multiple platforms to obtain an algorithm for both the discrete and continuous bid-spaces. Namely, for discrete bid spaces we give an algorithm with regret O(OPTmn/B + √mnOPT), where OPT is the performance of the optimal algorithm that knows the distributions. For continuous bid spaces the regret of our algorithm is Õ(m1/3 · min {B2/3 , (mT)2/3). When restricted to this special-case, this bound improves over Sankararaman and Slivkins [34] in the regime OPT << T, as is the case in the particular application at hand. Second, we show an Ω (√mOPT) lower bound for the discrete case and an Ω (m1/3 B2/3) lower bound for the continuous setting, almost matching the upper bounds. Finally, we use a real-world data set from a large internet online advertising company with multiple ad platforms and show that our algorithms outperform common benchmarks and satisfy the required properties warranted in the real-world application.

Related Publications

All Publications

ISAAC - December 5, 2021

On the Extended TSP Problem

Julián Mestre, Sergey Pupyrev, Seeun William Umboh

Journal of Big Data - July 19, 2021

Cumulative deviation of a subpopulation from the full population

Mark Tygert

Management Science (journal) - September 30, 2021

Pacing Equilibrium in First Price Auction Markets

Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Nicolas Stier, Eric Sodomka, Christopher A. Wilkens

ArXiv/SSRN - July 1, 2021

Social Connectedness in Urban Areas

Michael Bailey, Patrick Farrell, Theresa Kuchler, Johannes Stroebel

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy