Dynamic Knapsack Optimization Towards Efficient Multi-Channel Sequential Advertising

Xiaotian Hao, Zhaoqing Peng, Yi Ma, Guan Wang, Junqi Jin, Jianye Hao, Shan Chen, Rongquan Bai, Mingzhou Xie, Miao Xu, Zhenzhe Zheng, Chuan Yu, Han Li, Jian Xu, Kun Gai
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:4060-4070, 2020.

Abstract

In E-commerce, advertising is essential for merchants to reach their target users. The typical objective is to maximize the advertiser’s cumulative revenue over a period of time under a budget constraint. In real applications, an advertisement (ad) usually needs to be exposed to the same user multiple times until the user finally contributes revenue (e.g., places an order). However, existing advertising systems mainly focus on the immediate revenue with single ad exposures, ignoring the contribution of each exposure to the final conversion, thus usually falls into suboptimal solutions. In this paper, we formulate the sequential advertising strategy optimization as a dynamic knapsack problem. We propose a theoretically guaranteed bilevel optimization framework, which significantly reduces the solution space of the original optimization space while ensuring the solution quality. To improve the exploration efficiency of reinforcement learning, we also devise an effective action space reduction approach. Extensive offline and online experiments show the superior performance of our approaches over state-of-the-art baselines in terms of cumulative revenue.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-hao20b, title = {Dynamic Knapsack Optimization Towards Efficient Multi-Channel Sequential Advertising}, author = {Hao, Xiaotian and Peng, Zhaoqing and Ma, Yi and Wang, Guan and Jin, Junqi and Hao, Jianye and Chen, Shan and Bai, Rongquan and Xie, Mingzhou and Xu, Miao and Zheng, Zhenzhe and Yu, Chuan and Li, Han and Xu, Jian and Gai, Kun}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {4060--4070}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/hao20b/hao20b.pdf}, url = {https://proceedings.mlr.press/v119/hao20b.html}, abstract = {In E-commerce, advertising is essential for merchants to reach their target users. The typical objective is to maximize the advertiser’s cumulative revenue over a period of time under a budget constraint. In real applications, an advertisement (ad) usually needs to be exposed to the same user multiple times until the user finally contributes revenue (e.g., places an order). However, existing advertising systems mainly focus on the immediate revenue with single ad exposures, ignoring the contribution of each exposure to the final conversion, thus usually falls into suboptimal solutions. In this paper, we formulate the sequential advertising strategy optimization as a dynamic knapsack problem. We propose a theoretically guaranteed bilevel optimization framework, which significantly reduces the solution space of the original optimization space while ensuring the solution quality. To improve the exploration efficiency of reinforcement learning, we also devise an effective action space reduction approach. Extensive offline and online experiments show the superior performance of our approaches over state-of-the-art baselines in terms of cumulative revenue.} }
Endnote
%0 Conference Paper %T Dynamic Knapsack Optimization Towards Efficient Multi-Channel Sequential Advertising %A Xiaotian Hao %A Zhaoqing Peng %A Yi Ma %A Guan Wang %A Junqi Jin %A Jianye Hao %A Shan Chen %A Rongquan Bai %A Mingzhou Xie %A Miao Xu %A Zhenzhe Zheng %A Chuan Yu %A Han Li %A Jian Xu %A Kun Gai %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-hao20b %I PMLR %P 4060--4070 %U https://proceedings.mlr.press/v119/hao20b.html %V 119 %X In E-commerce, advertising is essential for merchants to reach their target users. The typical objective is to maximize the advertiser’s cumulative revenue over a period of time under a budget constraint. In real applications, an advertisement (ad) usually needs to be exposed to the same user multiple times until the user finally contributes revenue (e.g., places an order). However, existing advertising systems mainly focus on the immediate revenue with single ad exposures, ignoring the contribution of each exposure to the final conversion, thus usually falls into suboptimal solutions. In this paper, we formulate the sequential advertising strategy optimization as a dynamic knapsack problem. We propose a theoretically guaranteed bilevel optimization framework, which significantly reduces the solution space of the original optimization space while ensuring the solution quality. To improve the exploration efficiency of reinforcement learning, we also devise an effective action space reduction approach. Extensive offline and online experiments show the superior performance of our approaches over state-of-the-art baselines in terms of cumulative revenue.
APA
Hao, X., Peng, Z., Ma, Y., Wang, G., Jin, J., Hao, J., Chen, S., Bai, R., Xie, M., Xu, M., Zheng, Z., Yu, C., Li, H., Xu, J. & Gai, K.. (2020). Dynamic Knapsack Optimization Towards Efficient Multi-Channel Sequential Advertising. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:4060-4070 Available from https://proceedings.mlr.press/v119/hao20b.html.

Related Material