[edit]

# Robust Budget Pacing with a Single Sample

*Proceedings of the 40th International Conference on Machine Learning*, PMLR 202:1636-1659, 2023.

#### 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*$T\log 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 $\tilde O(\sqrt{T})$-regret, while still being robust to noise in the sampling distributions.