Stochastic Bandit Models for Delayed Conversions

Online advertising and product recommenda- tion are important domains of applications for multi-armed bandit methods. In these fields, the reward that is immediately available is most often only a proxy for the actual outcome of interest, which we refer to as a conversion. For instance, in web advertising, clicks can be observed within a few seconds after an ad dis- play but the corresponding sale –if any– will take hours, if not days to happen. This pa- per proposes and investigates a new stochas- tic multi-armed bandit model in the framework proposed by Chapelle (2014) –based on em- pirical studies in the field of web advertising– in which each action may trigger a future re- ward that will then happen with a stochas- tic delay. We assume that the probability of conversion associated with each action is un- known while the distribution of the conversion delay is known, distinguishing between the (idealized) case where the conversion events may be observed whatever their delay and the more realistic setting in which late conversions are censored. We provide performance lower bounds as well as two simple but efficient algo- rithms based on the UCB and KLUCB frame- works. The latter algorithm, which is prefer- able when conversion rates are low, is based on a Poissonization argument, of independent interest in other settings where aggregation of Bernoulli observations with different success probabilities is required.