Robust Budget Pacing with a Single Sample
Jul 25, 2023
Speakers
Rachitesh Kumar
Speaker · 0 followers
Santiago Balseiro
Speaker · 0 followers
Vahab Mirrokni
Speaker · 0 followers
Balasubramanian Sivan
Speaker · 0 followers
About
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.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 expenditu…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards
Watch later
Yulian Wu, …
The Catalog Problem: Clustering and Ordering Variable-Sized Sets
Watch later
Parallel Q-Learning: a Scheme for Time-efficient Reinforcement Learning
Watch later
Zechu Li, …
Addressing Technology Mediated Social Harms
Watch later
Are Equivariant Equilibrium Approximators Beneficial?
Watch later
Zhijian Duan, …