# Online Bidding Algorithms for Return-on-Spend Constrained Advertisers

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 35 references that are in the map.
- First posted on arXiv 29 Aug 2022.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Learning to Bid Without Knowing your Value](https://mlsanity.com/paper/1711.01333/) (2017)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Robust Auction Design in the Auto-bidding World](https://mlsanity.com/paper/2111.02468/) (2021)
- [Towards Efficient Auctions in an Auto-bidding World](https://mlsanity.com/paper/2103.13356/) (2021)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Learning in repeated auctions](https://mlsanity.com/paper/2011.09365/) (2020)
- [Pacing Equilibrium in First-Price Auction Markets](https://mlsanity.com/paper/1811.07166/) (2018)
- [Bid Prediction in Repeated Auctions with Learning](https://mlsanity.com/paper/2007.13193/) (2020)
- [No-regret Learning in Repeated First-Price Auctions with Budget Constraints](https://mlsanity.com/paper/2205.14572/) (2022)
- [The Parity Ray Regularizer for Pacing in Auction Markets](https://mlsanity.com/paper/2106.09503/) (2021)
- [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)
- [Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems](https://mlsanity.com/paper/1903.03944/) (2019)
- [Using Optimization to Solve Positive LPs Faster in Parallel](https://mlsanity.com/paper/1407.1925/) (2014)
- [Trading Networks with Bilateral Contracts](https://mlsanity.com/paper/1510.01210/) (2015)

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

- [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 Algorithms in non-Truthful Auctions with Budget and ROI Constraints](https://mlsanity.com/paper/2404.09832/) (2024)
- [Offline Reinforcement Learning for Optimizing Production Bidding Policies](https://mlsanity.com/paper/2310.09426/) (2023)
- [No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization](https://mlsanity.com/paper/2405.06575/) (2024)
- [Online Learning under Budget and ROI Constraints via Weak Adaptivity](https://mlsanity.com/paper/2302.01203/) (2023)
- [Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgets](https://mlsanity.com/paper/2306.07709/) (2023)
- [Interpolating Item and User Fairness in Multi-Sided Recommendations](https://mlsanity.com/paper/2306.10050/) (2023)
- [Online Bidding under RoS Constraints without Knowing the Value](https://mlsanity.com/paper/2503.03195/) (2025)
- [Online Ad Procurement in Non-stationary Autobidding Worlds](https://mlsanity.com/paper/2307.05698/) (2023)
- [Bid2X: Revealing Dynamics of Bidding Environment in Online Advertising from A Foundation Model Lens](https://mlsanity.com/paper/2510.23410/) (2025)
- [Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions](https://mlsanity.com/paper/2605.09448/) (2026)
- [Neural Optimization with Adaptive Heuristics for Intelligent Marketing System](https://mlsanity.com/paper/2405.10490/) (2024)
- [Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint](https://mlsanity.com/paper/2502.05599/) (2025)
- [Auto-bidding under Return-on-Spend Constraints with Uncertainty Quantification](https://mlsanity.com/paper/2509.16324/) (2025)
- [Multi-Armed Bandits with Minimum Aggregated Revenue Constraints](https://mlsanity.com/paper/2510.12523/) (2025)
- [Stochastic Primal-Dual Decoding for Multiobjective Generative Recommender Systems](https://mlsanity.com/paper/2607.19357/) (2026)

## Abstract (arXiv)

Online advertising has recently grown into a highly competitive and complex multi-billion-dollar industry, with advertisers bidding for ad slots at large scales and high frequencies. This has resulted in a growing need for efficient "auto-bidding" algorithms that determine the bids for incoming queries to maximize advertisers' targets subject to their specified constraints. This work explores efficient online algorithms for a single value-maximizing advertiser under an increasingly popular constraint: Return-on-Spend (RoS). We quantify efficiency in terms of regret relative to the optimal algorithm, which knows all queries a priori. We contribute a simple online algorithm that achieves near-optimal regret in expectation while always respecting the specified RoS constraint when the input sequence of queries are i.i.d. samples from some distribution. We also integrate our results with the previous work of Balseiro, Lu, and Mirrokni [BLM20] to achieve near-optimal regret while respecting both RoS and fixed budget constraints. Our algorithm follows the primal-dual framework and uses online mirror descent (OMD) for the dual updates. However, we need to use a non-canonical setup of OMD, and therefore the classic low-regret guarantee of OMD, which is for the adversarial setting in online learning, no longer holds. Nonetheless, in our case and more generally where low-regret dynamics are applied in algorithm design, the gradients encountered by OMD can be far from adversarial but influenced by our algorithmic choices. We exploit this key insight to show our OMD setup achieves low regret in the realm of our algorithm.