Incrementality, which measures the causal effect of showing an ad to a potential customer (e.g. a user in an internet platform) versus not, is a central object for advertisers in online advertising platforms. This paper investigates the problem of how an advertiser can learn to optimize the bidding sequence in an online manner without knowing the incrementality parameters in advance. We formulate the offline version of this problem as a specially structured episodic Markov Decision Process (MDP) and then, for its online learning counterpart, propose a novel reinforcement learning (RL) algorithm with regret at most Oe(H2 √T), which depends on the number of rounds H and number of episodes T, but does not depend on the number of actions (i.e., possible bids). A fundamental difference between our learning problem from standard RL problems is that the realized reward feedback from conversion incrementality is mixed and delayed. To handle this difficulty we propose and analyze a novel pairwise moment-matching algorithm to learn the conversion incrementality, which we believe is of independent interest.
|Original language||English (US)|
|Title of host publication||Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022|
|Editors||S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh|
|Publisher||Neural information processing systems foundation|
|State||Published - 2022|
|Event||36th Conference on Neural Information Processing Systems, NeurIPS 2022 - New Orleans, United States|
Duration: Nov 28 2022 → Dec 9 2022
|Name||Advances in Neural Information Processing Systems|
|Conference||36th Conference on Neural Information Processing Systems, NeurIPS 2022|
|Period||11/28/22 → 12/9/22|
Bibliographical noteFunding Information:
T. Li is supported in part by the NSF grant DMS-2015298 and 3Caverliers award from the University of Virginia. H. Xu is supported in part by an ARO award W911NF-23-1-0030.
© 2022 Neural information processing systems foundation. All rights reserved.