# No-Regret Online Autobidding Algorithms in First-price Auctions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2025.

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

- [From No-Regret to Strategically Robust Learning in Repeated Auctions](https://mlsanity.com/paper/2601.03853/) (2026)
- [Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions](https://mlsanity.com/paper/2605.09448/) (2026)

## Abstract (arXiv)

Automated bidding to optimize online advertising with various constraints, e.g. ROI constraints and budget constraints, is widely adopted by advertisers. A key challenge lies in designing algorithms for non-truthful mechanisms with ROI constraints. While prior work has addressed truthful auctions or non-truthful auctions with weaker benchmarks, this paper provides a significant improvement: We develop online bidding algorithms for repeated first-price auctions with ROI constraints, benchmarking against the optimal randomized strategy in hindsight. In the full feedback setting, where the maximum competing bid is observed, our algorithm achieves a near-optimal widetildeO(√T) regret bound, and in the bandit feedback setting (where the bidder only observes whether the bidder wins each auction), our algorithm attains widetildeO(T3/4) regret bound.