No-Regret Online Autobidding Algorithms in First-price Auctions
Yilin LI, Yuan Deng, Wei Tang, Hanrui Zhang
Abstract
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 $\tilde O(\sqrt{T})$ regret bound, and in the bandit feedback setting (where the bidder only observes whether the bidder wins each auction), our algorithm attains $\tilde O(T^{3/4})$ regret bound.
BibTeX
@inproceedings{
li2025noregret,
title={No-Regret Online Autobidding Algorithms in First-price Auctions},
author={Yilin LI and Yuan Deng and Wei Tang and Hanrui Zhang},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=xL5kQNdN6k}
}