Learning to Bid in Repeated First-Price Auctions with Budgets

Qian Wang, Zongjun Yang, Xiaotie Deng, Yuqing Kong
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:36494-36513, 2023.

Abstract

Budget management strategies in repeated auctions have received growing attention in online advertising markets. However, previous work on budget management in online bidding mainly focused on second-price auctions. The rapid shift from second-price auctions to first-price auctions for online ads in recent years has motivated the challenging question of how to bid in repeated first-price auctions while controlling budgets. In this work, we study the problem of learning in repeated first-price auctions with budgets. We design a dual-based algorithm that can achieve a near-optimal $\widetilde{O}(\sqrt{T})$ regret with full information feedback where the maximum competing bid is always revealed after each auction. We further consider the setting with one-sided information feedback where only the winning bid is revealed after each auction. We show that our modified algorithm can still achieve an $\widetilde{O}(\sqrt{T})$ regret with mild assumptions on the bidder’s value distribution. Finally, we complement the theoretical results with numerical experiments to confirm the effectiveness of our budget management policy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-wang23ao, title = {Learning to Bid in Repeated First-Price Auctions with Budgets}, author = {Wang, Qian and Yang, Zongjun and Deng, Xiaotie and Kong, Yuqing}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {36494--36513}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/wang23ao/wang23ao.pdf}, url = {https://proceedings.mlr.press/v202/wang23ao.html}, abstract = {Budget management strategies in repeated auctions have received growing attention in online advertising markets. However, previous work on budget management in online bidding mainly focused on second-price auctions. The rapid shift from second-price auctions to first-price auctions for online ads in recent years has motivated the challenging question of how to bid in repeated first-price auctions while controlling budgets. In this work, we study the problem of learning in repeated first-price auctions with budgets. We design a dual-based algorithm that can achieve a near-optimal $\widetilde{O}(\sqrt{T})$ regret with full information feedback where the maximum competing bid is always revealed after each auction. We further consider the setting with one-sided information feedback where only the winning bid is revealed after each auction. We show that our modified algorithm can still achieve an $\widetilde{O}(\sqrt{T})$ regret with mild assumptions on the bidder’s value distribution. Finally, we complement the theoretical results with numerical experiments to confirm the effectiveness of our budget management policy.} }
Endnote
%0 Conference Paper %T Learning to Bid in Repeated First-Price Auctions with Budgets %A Qian Wang %A Zongjun Yang %A Xiaotie Deng %A Yuqing Kong %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-wang23ao %I PMLR %P 36494--36513 %U https://proceedings.mlr.press/v202/wang23ao.html %V 202 %X Budget management strategies in repeated auctions have received growing attention in online advertising markets. However, previous work on budget management in online bidding mainly focused on second-price auctions. The rapid shift from second-price auctions to first-price auctions for online ads in recent years has motivated the challenging question of how to bid in repeated first-price auctions while controlling budgets. In this work, we study the problem of learning in repeated first-price auctions with budgets. We design a dual-based algorithm that can achieve a near-optimal $\widetilde{O}(\sqrt{T})$ regret with full information feedback where the maximum competing bid is always revealed after each auction. We further consider the setting with one-sided information feedback where only the winning bid is revealed after each auction. We show that our modified algorithm can still achieve an $\widetilde{O}(\sqrt{T})$ regret with mild assumptions on the bidder’s value distribution. Finally, we complement the theoretical results with numerical experiments to confirm the effectiveness of our budget management policy.
APA
Wang, Q., Yang, Z., Deng, X. & Kong, Y.. (2023). Learning to Bid in Repeated First-Price Auctions with Budgets. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:36494-36513 Available from https://proceedings.mlr.press/v202/wang23ao.html.

Related Material