Robust Budget Pacing with a Single Sample

arXiv:2302.02006v2 Announce Type: replace Abstract: 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(sqrt{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 ilde O(sqrt{T})-regret, while still being robust to noise in the sampling distributions.

Source: arXiv cs.LG | 2026-10-01