Waterfall Bandits: Learning to Sell Ads Online
This addresses the challenge for publishers in maximizing ad revenue through sequential price offers, representing a novel approach in online advertising optimization.
The paper tackles the problem of optimizing revenue in online ad sales via waterfall auctions by designing an online learning algorithm that interleaves learning and optimization, achieving sublinear regret and demonstrating quick learning of high-quality pricing strategies on synthetic and real-world data.
A popular approach to selling online advertising is by a waterfall, where a publisher makes sequential price offers to ad networks for an inventory, and chooses the winner in that order. The publisher picks the order and prices to maximize her revenue. A traditional solution is to learn the demand model and then subsequently solve the optimization problem for the given demand model. This will incur a linear regret. We design an online learning algorithm for solving this problem, which interleaves learning and optimization, and prove that this algorithm has sublinear regret. We evaluate the algorithm on both synthetic and real-world data, and show that it quickly learns high quality pricing strategies. This is the first principled study of learning a waterfall design online by sequential experimentation.