{"ID":2853176,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.16869","arxiv_id":"2510.16869","title":"No-Regret Online Autobidding Algorithms in First-price Auctions","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 $\\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.","short_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 auctio...","url_abs":"https://arxiv.org/abs/2510.16869","url_pdf":"https://arxiv.org/pdf/2510.16869v1","authors":"[\"Yuan Deng\",\"Yilin Li\",\"Wei Tang\",\"Hanrui Zhang\"]","published":"2025-10-19T15:00:25Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}