# Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 46 references that are in the map.
- First posted on arXiv 30 Jan 2023.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Tight last-iterate convergence rates for no-regret learning in multi-player games](https://mlsanity.com/paper/2010.13724/) (2020)
- [Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games](https://mlsanity.com/paper/1905.08396/) (2019)
- [Robust Auction Design in the Auto-bidding World](https://mlsanity.com/paper/2111.02468/) (2021)
- [Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence](https://mlsanity.com/paper/2205.08674/) (2022)
- [Online Bidding Algorithms for Return-on-Spend Constrained Advertisers](https://mlsanity.com/paper/2208.13713/) (2022)
- [Multiplicative Pacing Equilibria in Auction Markets](https://mlsanity.com/paper/1706.07151/) (2017)
- [Pacing Equilibrium in First-Price Auction Markets](https://mlsanity.com/paper/1811.07166/) (2018)
- [The Price of Anarchy in Auctions](https://mlsanity.com/paper/1607.07684/) (2016)
- [Bidding Agent Design in the LinkedIn Ad Marketplace](https://mlsanity.com/paper/2202.12472/) (2022)
- [Non-quasi-linear Agents in Quasi-linear Mechanisms](https://mlsanity.com/paper/2012.02893/) (2020)
- [Efficiency Guarantees in Auctions with Budgets](https://mlsanity.com/paper/1304.7048/) (2013)
- [Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees](https://mlsanity.com/paper/2102.10476/) (2021)
- [The Complexity of Pacing for Second-Price Auctions](https://mlsanity.com/paper/2103.13969/) (2021)
- [Auctions without commitment in the auto-bidding world](https://mlsanity.com/paper/2301.07312/) (2023)
- [Liquid Price of Anarchy](https://mlsanity.com/paper/1511.01132/) (2015)

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

- [Online Advertisements with LLMs: Opportunities and Challenges](https://mlsanity.com/paper/2311.07601/) (2023)
- [Multi-channel Autobidding with Budget and ROI Constraints](https://mlsanity.com/paper/2302.01523/) (2023)
- [No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints](https://mlsanity.com/paper/2404.09832/) (2024)
- [Impact of Decentralized Learning on Player Utilities in Stackelberg Games](https://mlsanity.com/paper/2403.00188/) (2024)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [Online Learning in Contextual Second-Price Pay-Per-Click Auctions](https://mlsanity.com/paper/2310.05047/) (2023)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [Games with Payments between Learning Agents](https://mlsanity.com/paper/2405.20880/) (2024)
- [Adaptive maximization of social welfare](https://mlsanity.com/paper/2310.09597/) (2023)
- [Online Bidding under RoS Constraints without Knowing the Value](https://mlsanity.com/paper/2503.03195/) (2025)
- [BAT: Benchmark for Auto-bidding Task](https://mlsanity.com/paper/2505.08485/) (2025)
- [Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners](https://mlsanity.com/paper/2502.08597/) (2025)
- [Autobidding Arena: unified evaluation of the classical and RL-based autobidding algorithms](https://mlsanity.com/paper/2510.19357/) (2025)
- [Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions](https://mlsanity.com/paper/2605.09448/) (2026)
- [Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint](https://mlsanity.com/paper/2502.05599/) (2025)
- [Large-Scale Auto-bidding with Nash Equilibrium Constraints](https://mlsanity.com/paper/2503.10304/) (2025)
- [Plan-Driven Adaptive Bidding for First-Price Auctions with Budget Constraints under Nonstationarity](https://mlsanity.com/paper/2505.02796/) (2025)
- [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)
- [Inference Auctions](https://mlsanity.com/paper/2609.40070/) (2026)

## Abstract (arXiv)

We study a game between autobidding algorithms that compete in an online advertising platform. Each autobidder is tasked with maximizing its advertiser's total value over multiple rounds of a repeated auction, subject to budget and return-on-investment constraints. We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret. Our algorithm uses only bandit feedback and can be used with the first- or second-price auction, as well as with any "intermediate" auction format. Our main result is that when these autobidders play against each other, the resulting expected liquid welfare over all rounds is at least half of the expected optimal liquid welfare achieved by any allocation. This holds whether or not the bidding dynamics converges to an equilibrium.