  Online ad platforms offer budget management tools for advertisers that aim to
maximize the number of conversions given a budget constraint. As the volume of
impressions, conversion rates and prices vary over time, these budget
management systems learn a spend plan (to find the optimal distribution of
budget over time) and run a pacing algorithm which follows the spend plan.
  This paper considers two models for impressions and competition that varies
with time: a) an episodic model which exhibits stationarity in each episode,
but each episode can be arbitrarily different from the next, and b) a model
where the distributions of prices and values change slowly over time. We
present the first learning theoretic guarantees on both the accuracy of spend
plans and the resulting end-to-end budget management system. We present four
main results: 1) for the episodic setting we give sample complexity bounds for
the spend rate prediction problem: given $n$ samples from each episode, with
high probability we have $|\widehat{\rho}_e - \rho_e| \leq
\tilde{O}(\frac{1}{n^{1/3}})$ where $\rho_e$ is the optimal spend rate for the
episode, $\widehat{\rho}_e$ is the estimate from our algorithm, 2) we extend
the algorithm of Balseiro and Gur (2017) to operate on varying, approximate
spend rates and show that the resulting combined system of optimal spend rate
estimation and online pacing algorithm for episodic settings has regret that
vanishes in number of historic samples $n$ and the number of rounds $T$, 3) for
non-episodic but slowly-changing distributions we show that the same approach
approximates the optimal bidding strategy up to a factor dependent on the
rate-of-change of the distributions and 4) we provide experiments showing that
our algorithm outperforms both static spend plans and non-pacing across a wide
variety of settings.
