# Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2022.

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

- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [Multi-channel Autobidding with Budget and ROI Constraints](https://mlsanity.com/paper/2302.01523/) (2023)
- [No-regret Learning in Repeated First-Price Auctions with Budget Constraints](https://mlsanity.com/paper/2205.14572/) (2022)
- [No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints](https://mlsanity.com/paper/2404.09832/) (2024)
- [No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization](https://mlsanity.com/paper/2405.06575/) (2024)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [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)
- [Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgets](https://mlsanity.com/paper/2306.07709/) (2023)
- [Online Learning in Contextual Second-Price Pay-Per-Click Auctions](https://mlsanity.com/paper/2310.05047/) (2023)
- [Dynamic Budget Throttling in Repeated Second-Price Auctions](https://mlsanity.com/paper/2207.04690/) (2022)
- [Learning in Strategic Queuing Systems with Small Buffers](https://mlsanity.com/paper/2502.08898/) (2025)
- [Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions](https://mlsanity.com/paper/2605.09448/) (2026)
- [Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising](https://mlsanity.com/paper/2604.12799/) (2026)
- [Decision-Calibrated Conformal Uncertainty for Pacing Decisions in Streaming Advertising](https://mlsanity.com/paper/2606.10187/) (2026)
- [When Privacy Moves ML-Mediated Decisions On Device: Information and Incentive Misalignment in Auctions](https://mlsanity.com/paper/2609.33312/) (2026)
- [Inference Auctions](https://mlsanity.com/paper/2609.40070/) (2026)

## Abstract (arXiv)

We study the aggregate welfare and individual regret guarantees of dynamic pacing algorithms in the context of repeated auctions with budgets. Such algorithms are commonly used as bidding agents in Internet advertising platforms, adaptively learning to shade bids by a tunable linear multiplier in order to match a specified budget. We show that when agents simultaneously apply a natural form of gradient-based pacing, the liquid welfare obtained over the course of the learning dynamics is at least half the optimal expected liquid welfare obtainable by any allocation rule. Crucially, this result holds without requiring convergence of the dynamics, allowing us to circumvent known complexity-theoretic obstacles of finding equilibria. This result is also robust to the correlation structure between agent valuations and holds for any core auction, a broad class of auctions that includes first-price, second-price, and generalized second-price auctions as special cases. For individual guarantees, we further show such pacing algorithms enjoy dynamic regret bounds for individual utility- and value-maximization, with respect to the sequence of budget-pacing bids, for any auction satisfying a monotone bang-for-buck property. To complement our theoretical findings, we provide semi-synthetic numerical simulations based on auction data from the Bing Advertising platform.