# No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 15 Apr 2024.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [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)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Online Learning with Vector Costs and Bandits with Knapsacks](https://mlsanity.com/paper/2010.07346/) (2020)
- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [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)
- [Learning to Bid in Repeated First-Price Auctions with Budgets](https://mlsanity.com/paper/2304.13477/) (2023)
- [Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem](https://mlsanity.com/paper/2209.12013/) (2022)
- [Approximately Stationary Bandits with Knapsacks](https://mlsanity.com/paper/2302.14686/) (2023)
- [Bandits with Replenishable Knapsacks: the Best of both Worlds](https://mlsanity.com/paper/2306.08470/) (2023)
- [Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions](https://mlsanity.com/paper/2210.07502/) (2022)
- [Online Learning under Budget and ROI Constraints via Weak Adaptivity](https://mlsanity.com/paper/2302.01203/) (2023)

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

- [Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2405.16118/) (2024)
- [Joint Value Estimation and Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2502.17292/) (2025)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [Games with Payments between Learning Agents](https://mlsanity.com/paper/2405.20880/) (2024)
- [From No-Regret to Strategically Robust Learning in Repeated Auctions](https://mlsanity.com/paper/2601.03853/) (2026)
- [Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback](https://mlsanity.com/paper/2502.04678/) (2025)
- [Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions](https://mlsanity.com/paper/2605.09448/) (2026)
- [Plan-Driven Adaptive Bidding for First-Price Auctions with Budget Constraints under Nonstationarity](https://mlsanity.com/paper/2505.02796/) (2025)
- [Auto-bidding under Return-on-Spend Constraints with Uncertainty Quantification](https://mlsanity.com/paper/2509.16324/) (2025)

## Abstract (arXiv)

Advertisers increasingly use automated bidding to optimize their ad campaigns on online advertising platforms. Autobidding optimizes an advertiser's objective subject to various constraints, e.g. average ROI and budget constraints. In this paper, we study the problem of designing online autobidding algorithms to optimize value subject to ROI and budget constraints when the platform is running any mixture of first and second price auction. We consider the following stochastic setting: There is an item for sale in each of T rounds. In each round, buyers submit bids and an auction is run to sell the item. We focus on one buyer, possibly with budget and ROI constraints. We assume that the buyer's value and the highest competing bid are drawn i.i.d. from some unknown (joint) distribution in each round. We design a low-regret bidding algorithm that satisfies the buyer's constraints. Our benchmark is the objective value achievable by the best possible Lipschitz function that maps values to bids, which is rich enough to best respond to many different correlation structures between value and highest competing bid. Our main result is an algorithm with full information feedback that guarantees a near-optimal tilde O(√ T) regret with respect to the best Lipschitz function. Our result applies to a wide range of auctions, most notably any mixture of first and second price auctions (price is a convex combination of the first and second price). In addition, our result holds for both value-maximizing buyers and quasi-linear utility-maximizing buyers. We also study the bandit setting, where we show an Omega(T2/3) lower bound on the regret for first-price auctions, showing a large disparity between the full information and bandit settings. We also design an algorithm with tilde O(T3/4) regret, when the value distribution is known and is independent of the highest competing bid.