# Optimal Spend Rate Estimation and Pacing for Ad Campaigns with Budgets

arXiv: https://arxiv.org/abs/2202.05881 · HTML: https://mlsanity.com/paper/2202.05881/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 39 references that are in the map.
- First posted on arXiv 4 Feb 2022.

## Builds on (most cited first, 9 of 9)

- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising](https://mlsanity.com/paper/2103.10246/) (2021)
- [Multiplicative Pacing Equilibria in Auction Markets](https://mlsanity.com/paper/1706.07151/) (2017)
- [Online Joint Bid/Daily Budget Optimization of Internet Advertising Campaigns](https://mlsanity.com/paper/2003.01452/) (2020)
- [Pacing Equilibrium in First-Price Auction Markets](https://mlsanity.com/paper/1811.07166/) (2018)
- [Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising](https://mlsanity.com/paper/1305.3011/) (2013)
- [Online Market Equilibrium with Application to Fair Division](https://mlsanity.com/paper/2103.12936/) (2021)
- [Non-quasi-linear Agents in Quasi-linear Mechanisms](https://mlsanity.com/paper/2012.02893/) (2020)
- [The Complexity of Pacing for Second-Price Auctions](https://mlsanity.com/paper/2103.13969/) (2021)

## Built on by (most cited first, 4 of 4)

- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [Robust Budget Pacing with a Single Sample](https://mlsanity.com/paper/2302.02006/) (2023)
- [Multi-Platform Budget Management in Ad Markets with Non-IC Auctions](https://mlsanity.com/paper/2306.07352/) (2023)
- [Delivery Optimized Discovery in Behavioral User Segmentation under Budget Constraint](https://mlsanity.com/paper/2402.03388/) (2024)

## Abstract (arXiv)

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ρe - ρe| ≤ tildeO(frac1n1/3) where ρe is the optimal spend rate for the episode, widehatρ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.