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

ArXiv/SSRN - December 28, 2020

Social Distancing During a Pandemic: The Role of Friends

Michael Bailey, Drew Johnston, Martin Koenen, Theresa Kuchler, Dominic Russel, Johannes Stroebel

AISTATS - April 13, 2021

Multi-armed Bandits with Cost Subsidy

Deeksha Sinha, Karthik Abinav Sankararaman, Abbas Kazerouni, Vashist Avadhanula

Innovative Technology at the Interface of Finance and Operations - March 31, 2021

Market Equilibrium Models in Large-Scale Internet Markets

Christian Kroer, Nicolas E. Stier-Moses

EC - December 23, 2020

Matching Algorithms for Blood Donation

Duncan C. McElfresh, Christian Kroer, Sergey Pupyrev, Eric Sodomka, Karthik Abinav Sankararaman, Zack Chauvin, Neil Dexter, John P. Dickerson

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