Cost-Effective Active Learning for Bid Exploration in Online Advertising
Pages 788 - 796
Abstract
As a bid optimization algorithm in the first-price auction (FPA), bid shading is used in online advertising to avoid overpaying for advertisers. However, we find the bid shading approach would incur serious local optima. This effect prevents the advertisers from maximizing long-term surplus. In this work, we identify the reasons behind this local optima - it comes from the lack of winning price information, which results in the conflict between short-term surplus and the winning rate prediction model training, and is further propagated through the over-exploitation of the model. To rectify this problem, we propose a cost-effective active learning strategy, namely CeBE, for bid exploration. Specifically, we comprehensively consider the uncertainty and density of samples to calculate exploration utility, and use a 2+ε-approximation greedy algorithm to control exploration costs. Instead of selecting bid prices that maximize the expected surplus for all bid requests, we employ the bid exploration strategy to determine the bid prices. By trading off a portion of surplus, we can train the model using higher-quality data to enhance its performance, enabling the system to achieve a long-term surplus. Our method is straightforward and applicable to real-world industrial environment: it is effective across various categories of winning rate prediction models. We conducted empirical studies to validate the efficacy of our approach. In comparison to the traditional bid shading system, CeBE can yield an average surplus improvement of 8.16% across various models and datasets.
References
[1]
Philip Bachman, Alessandro Sordoni, and Adam Trischler. 2017. Learning algorithms for active learning. In international conference on machine learning. PMLR, 301--310.
[2]
Jason Bigler. 2019. Rolling out first price auctions to Google Ad Manager partners. Consulted at https://www.blog.google/products/admanager/rolling-out-first-price-auctions-google-ad-manager-partners (2019).
[3]
Razvan Caramalau, Binod Bhattarai, and Tae-Kyun Kim. 2021. Sequential graph convolutional network for active learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 9583--9592.
[4]
Robert L Carraway, Robert L Schmidt, and Lawrence R Weatherford. 1993. An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns. Naval Research Logistics (NRL) 40, 2 (1993), 161--173.
[5]
John M Crespi and Richard J Sexton. 2005. A Multinomial logit framework to estimate bid shading in procurement auctions: Application to cattle sales in the Texas Panhandle. Review of industrial organization 27 (2005), 253--278.
[6]
John M Crespi and Richard J Sexton. 2005. A Multinomial logit framework to estimate bid shading in procurement auctions: Application to cattle sales in the Texas Panhandle. Review of industrial organization 27 (2005), 253--278.
[7]
Ying Cui, Ruofei Zhang,Wei Li, and Jianchang Mao. 2011. Bid landscape forecasting in online ad exchange marketplace. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 265--273.
[8]
Gautam Dasarathy, Robert Nowak, and Xiaojin Zhu. 2015. S2: An efficient graph based active learning algorithm with application to nonparametric classification. In Conference on Learning Theory. PMLR, 503--522.
[9]
Brian C Dean, Michel X Goemans, and Jan Vondrák. 2008. Approximating the stochastic knapsack problem: The benefit of adaptivity. Mathematics of Operations Research 33, 4 (2008), 945--964.
[10]
Djordje Gligorijevic, Tian Zhou, Bharatbhushan Shetty, Brendan Kitts, Shengjun Pan, Junwei Pan, and Aaron Flores. 2020. Bid shading in the brave new world of first-price auctions. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2453--2460.
[11]
Denis Gudovskiy, Alec Hodgkinson, Takuya Yamaguchi, and Sotaro Tsukizawa. 2020. Deep active learning for biased datasets via fisher kernel self-supervision. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 9041--9049.
[12]
Robbie A Haertel, Kevin D Seppi, Eric K Ringger, and James L Carroll. 2008. Return on investment for active learning. In Proceedings of the NIPS workshop on cost-sensitive learning, Vol. 72. Citeseer.
[13]
Ali Hortaçsu, Jakub Kastl, and Allen Zhang. 2018. Bid shading and bidder surplus in the us treasury auction system. American Economic Review 108, 1 (2018), 147--169.
[14]
Ashish Kapoor, Eric Horvitz, and Sumit Basu. 2007. Selective supervision: Guiding supervised learning with decision-theoretic active learning. In IJCAI'07 Proceedings of the 20th international joint conference on Artifical intelligence. 877--882.
[15]
Niklas Karlsson and Qian Sang. 2021. Adaptive bid shading optimization of first-price ad inventory. In 2021 American Control Conference (ACC). IEEE, 4983--4990.
[16]
Seho Kee, Enrique Del Castillo, and George Runger. 2018. Query-by-committee improvement with diversity and density in batch active learning. Information Sciences 454 (2018), 401--418.
[17]
Tor Lattimore and Csaba Szepesvári. 2020. Bandit algorithms. Cambridge University Press.
[18]
David D Lewis. 1995. A sequential algorithm for training text classifiers: Corrigendum and additional data. In Acm Sigir Forum, Vol. 29. ACM New York, NY, USA, 13--19.
[19]
David D Lewis and Jason Catlett. 1994. Heterogeneous uncertainty sampling for supervised learning. In Machine learning proceedings 1994. Elsevier, 148--156.
[20]
Xiang Li and Devin Guan. 2014. Programmatic buying bidding strategies with win rate and winning price estimation in real time mobile advertising. In Advances in Knowledge Discovery and Data Mining: 18th Pacific-Asia Conference, PAKDD 2014, Tainan, Taiwan, May 13--16, 2014. Proceedings, Part I 18. Springer, 447--460.
[21]
Xu Li, Michelle Ma Zhang, Zhenya Wang, and Youjun Tong. 2022. Arbitrary distribution modeling with censorship in real-time bidding advertising. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 3250--3258.
[22]
Hairen Liao, Lingxiao Peng, Zhenchuan Liu, and Xuehua Shen. 2014. iPinYou global rtb bidding algorithm competition dataset. In Proceedings of the Eighth International Workshop on Data Mining for Online Advertising. 1--6.
[23]
Shengjun Pan, Brendan Kitts, Tian Zhou, Hao He, Bharatbhushan Shetty, Aaron Flores, Djordje Gligorijevic, Junwei Pan, Tingyu Mao, San Gultekin, et al. 2020. Bid shading by win-rate estimation and surplus maximization. arXiv preprint arXiv:2009.09259 (2020).
[24]
Kan Ren, Jiarui Qin, Lei Zheng, Zhengyu Yang,Weinan Zhang, and Yong Yu. 2019. Deep landscape forecasting for real-time bidding advertising. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. 363--372.
[25]
Nicholas Roy and Andrew McCallum. 2001. Toward optimal active learning through sampling estimation of error reduction. Int. Conf. on Machine Learning. (2001).
[26]
Burr Settles. 2009. Active learning literature survey. (2009).
[27]
Burr Settles and Mark Craven. 2008. An analysis of active learning strategies for sequence labeling tasks. In proceedings of the 2008 conference on empirical methods in natural language processing. 1070--1079.
[28]
Burr Settles, Mark Craven, and Soumya Ray. 2007. Multiple-instance active learning. Advances in neural information processing systems 20 (2007).
[29]
H Sebastian Seung, Manfred Opper, and Haim Sompolinsky. 1992. Query by committee. In Proceedings of the fifth annual workshop on Computational learning theory. 287--294.
[30]
Claude Elwood Shannon. 1948. A mathematical theory of communication. The Bell system technical journal 27, 3 (1948), 379--423.
[31]
Marco A Wiering and Martijn Van Otterlo. 2012. Reinforcement learning. Adaptation, learning, and optimization 12, 3 (2012), 729.
[32]
WushWu, Mi-Yen Yeh, and Ming-Syan Chen. 2018. Deep censored learning of the winning price in the real time bidding. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2526--2535.
[33]
Wush Chi-Hsuan Wu, Mi-Yen Yeh, and Ming-Syan Chen. 2015. Predicting winning price in real time bidding with censored data. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 1305--1314.
[34]
Donggeun Yoo and In So Kweon. 2019. Learning loss for active learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 93--102.
[35]
Jifan Zhang, Julian Katz-Samuels, and Robert Nowak. 2022. Galaxy: Graph-based active learning at the extreme. In International Conference on Machine Learning. PMLR, 26223--26238.
[36]
T Zhang and FJ Oles. 2000. A probability analysis on the value of unlabeled data for classification problems. 17th ICML (pp. 1191--1198).
[37]
Weinan Zhang, Shuai Yuan, and Jun Wang. 2014. Optimal real-time bidding for display advertising. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 1077--1086.
[38]
Tian Zhou, Hao He, Shengjun Pan, Niklas Karlsson, Bharatbhushan Shetty, Brendan Kitts, Djordje Gligorijevic, San Gultekin, Tingyu Mao, Junwei Pan, et al. 2021. An efficient deep distribution network for bid shading in first-price auctions. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 3996--4004.
[39]
Wen-Yuan Zhu,Wen-Yueh Shih, Ying-Hsuan Lee,Wen-Chih Peng, and Jiun-Long Huang. 2017. A gamma-based regression for winning price estimation in real-time bidding advertising. In 2017 IEEE International Conference on Big Data (Big Data). IEEE, 1610--1619.
[40]
Christine Zulehner. 2009. Bidding behavior in sequential cattle auctions. International Journal of Industrial Organization 27, 1 (2009), 33--42.
[41]
Christine Zulehner. 2009. Bidding behavior in sequential cattle auctions. International Journal of Industrial Organization 27, 1 (2009), 33--42.
Index Terms
- Cost-Effective Active Learning for Bid Exploration in Online Advertising
Recommendations
From Second to First: Mixed Censored Multi-Task Learning for Winning Price Prediction
WSDM '24: Proceedings of the 17th ACM International Conference on Web Search and Data MiningA transformation from second-price auctions (SPA) to first-price auctions (FPA) has been observed in online advertising. The consequential coexistence of mixed FPA and SPA auction types has further led to the problem of mixed censorship, making bid ...
MEBS: Multi-task End-to-end Bid Shading for Multi-slot Display Advertising
CIKM '23: Proceedings of the 32nd ACM International Conference on Information and Knowledge ManagementOnline bidding and auction are crucial aspects of the online advertising industry. Conventionally, there is only one slot for ad display and most current studies focus on it. Nowadays, multi-slot display advertising is gradually becoming popular where ...
Scalable Bid Landscape Forecasting in Real-Time Bidding
Machine Learning and Knowledge Discovery in DatabasesAbstractIn programmatic advertising, ad slots are usually sold using second-price (SP) auctions in real-time. The highest bidding advertiser wins but pays only the second highest bid (known as the winning price). In SP, for a single item, the dominant ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2024
1246 pages
ISBN:9798400703713
DOI:10.1145/3616855
- General Chairs:
- Luz Angélica,
- Silvio Lattanzi,
- Andrés Muñoz Medina,
- Program Chairs:
- Leman Akoglu,
- Aristides Gionis,
- Sergei Vassilvitskii
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 March 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- China NSF grant
- Tencent Rhino Bird Key Research Project
- Science and Technology Innovation 2030 ?``New Generation Artificial Intelligence' Major Project
- Alibaba Innovative Research Program
Conference
WSDM '24: The 17th ACM International Conference on Web Search and Data Mining
March 4 - 8, 2024
Merida, Mexico
Acceptance Rates
Overall Acceptance Rate 498 of 2,863 submissions, 17%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 174Total Downloads
- Downloads (Last 12 months)174
- Downloads (Last 6 weeks)18
Reflects downloads up to 23 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in