# Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 8 Feb 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [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)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Robust Auction Design in the Auto-bidding World](https://mlsanity.com/paper/2111.02468/) (2021)
- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [Towards Efficient Auctions in an Auto-bidding World](https://mlsanity.com/paper/2103.13356/) (2021)
- [Online Bidding Algorithms for Return-on-Spend Constrained Advertisers](https://mlsanity.com/paper/2208.13713/) (2022)
- [Unifying the stochastic and the adversarial Bandits with Knapsack](https://mlsanity.com/paper/1811.12253/) (2018)
- [The Online Saddle Point Problem and Online Convex Optimization with Knapsacks](https://mlsanity.com/paper/1806.08301/) (2018)
- [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)
- [Packing a Knapsack of Unknown Capacity](https://mlsanity.com/paper/1307.2806/) (2013)
- [Online Inventory Management with Application to Energy Procurement in Data Centers](https://mlsanity.com/paper/1901.04372/) (2019)

## Abstract (arXiv)

Auto-bidding problem under a strict return-on-spend constraint (ROSC) is considered, where an algorithm has to make decisions about how much to bid for an ad slot depending on the revealed value, and the hidden allocation and payment function that describes the probability of winning the ad-slot depending on its bid. The objective of an algorithm is to maximize the expected utility (product of ad value and probability of winning the ad slot) summed across all time slots subject to the total expected payment being less than the total expected utility, called the ROSC. A (surprising) impossibility result is derived that shows that no online algorithm can achieve a sub-linear regret even when the value, allocation and payment function are drawn i.i.d. from an unknown distribution. The problem is non-trivial even when the revealed value remains constant across time slots, and an algorithm with regret guarantee that is optimal up to logarithmic factor is derived.