No-Regret Online Autobidding Algorithms in First-price Auctions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911220276133888 |
|---|---|
| author | Deng, Yuan Li, Yilin Tang, Wei Zhang, Hanrui |
| author_facet | Deng, Yuan Li, Yilin Tang, Wei Zhang, Hanrui |
| contents | 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 $\widetilde{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 $\widetilde{O}(T^{3/4})$ regret bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_16869 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | No-Regret Online Autobidding Algorithms in First-price Auctions Deng, Yuan Li, Yilin Tang, Wei Zhang, Hanrui Computer Science and Game Theory 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 $\widetilde{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 $\widetilde{O}(T^{3/4})$ regret bound. |
| title | No-Regret Online Autobidding Algorithms in First-price Auctions |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2510.16869 |