Robust Budget Pacing with a Single Sample

02/03/2023
by   Santiago Balseiro, et al.
0

Major Internet advertising platforms offer budget pacing tools as a standard service for advertisers to manage their ad campaigns. Given the inherent non-stationarity in an advertiser's value and also competing advertisers' values over time, a commonly used approach is to learn a target expenditure plan that specifies a target spend as a function of time, and then run a controller that tracks this plan. This raises the question: how many historical samples are required to learn a good expenditure plan? We study this question by considering an advertiser repeatedly participating in T second-price auctions, where the tuple of her value and the highest competing bid is drawn from an unknown time-varying distribution. The advertiser seeks to maximize her total utility subject to her budget constraint. Prior work has shown the sufficiency of Tlog T samples per distribution to achieve the optimal O(√(T))-regret. We dramatically improve this state-of-the-art and show that just one sample per distribution is enough to achieve the near-optimal Õ(√(T))-regret, while still being robust to noise in the sampling distributions.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset