Abstract
We study online auto-bidding algorithms for a single advertiser maximizing value under the Return-on-Spend (RoS) constraint, quantifying performance in terms of regret relative to the optimal offline solution that knows all queries a priori. We contribute a simple online algorithm that achieves near-optimal regret in expectation while always respecting the RoS constraint when the input queries are i.i.d. samples from some distribution. Integrating our results with [9] achieves near-optimal regret under both RoS and fixed budget constraints. Our algorithm uses the primal-dual framework with online mirror descent (OMD) for the dual updates, and the analysis utilizes new insights into the gradient structure.
| Original language | English (US) |
|---|---|
| Title of host publication | ACM Web Conference 2023 - Proceedings of the World Wide Web Conference, WWW 2023 |
| Publisher | Association for Computing Machinery, Inc |
| Pages | 3550-3560 |
| Number of pages | 11 |
| ISBN (Electronic) | 9781450394161 |
| DOIs | |
| State | Published - Apr 30 2023 |
| Externally published | Yes |
| Event | 32nd ACM World Wide Web Conference, WWW 2023 - Austin, United States Duration: Apr 30 2023 → May 4 2023 |
Publication series
| Name | ACM Web Conference 2023 - Proceedings of the World Wide Web Conference, WWW 2023 |
|---|
Conference
| Conference | 32nd ACM World Wide Web Conference, WWW 2023 |
|---|---|
| Country/Territory | United States |
| City | Austin |
| Period | 4/30/23 → 5/4/23 |
Bibliographical note
Publisher Copyright:© 2023 Owner/Author.
Keywords
- Autobidding
- Online Advertising
- Primal-Dual Algorithms