Stochastic Bandit Models for Delayed Conversions

Claire Vernade, Olivier Cappé, Vianney Perchet

Abstract

In many real-world applications of multi-armed bandits (MAB), such as online advertising, rewards are not observed immediately. Instead, they arrive with stochastic delays, and in many cases, may be censored if they do not occur within a specific observation window. This paper introduces a framework for handling these delays by developing "delay-corrected" versions of the UCB and KL-UCB algorithms. By incorporating the probability of reward arrival into the estimation process, these algorithms account for pending feedback, achieving optimal asymptotic performance and significantly outperforming naive strategies in simulations inspired by real-world digital advertising data.

Introduction

Standard Multi-Armed Bandit (MAB) models operate on the assumption of immediate feedback: once an action is taken, the reward is observed before the next decision point. However, in domains like display advertising, the feedback loop is inherently asynchronous. While a click might happen seconds after an ad is shown, the ultimate goal—a conversion or purchase—might take hours, days, or even weeks to materialize.

When a learner ignores these delays, two primary issues arise:

  1. Estimation Bias: The system may underestimate the value of an arm because its rewards are still "in flight," leading the algorithm to favor arms with shorter delay profiles rather than higher conversion rates.
  2. Censoring: In practical engineering systems, if a conversion does not occur within a fixed window (e.g., 14 days), the event is often lost to the system's memory or treated as a zero, further distorting the learning process.

This paper addresses these challenges by proposing a model where each arm $k$ is characterized by a conversion probability $ heta_k$ and a delay distribution $ au$. The authors investigate both uncensored settings (where rewards eventually arrive) and censored settings (where rewards are only observable within a window $m$).

Methodology

Delay-Corrected Estimators

The core innovation of this work is the move away from simple empirical averages. Instead, the authors propose a weighted estimator:

$$\hat{\theta}_k(t) = \frac{S_k(t)}{\tilde{N}_k(t)}$$

In this formulation, $S_k(t)$ is the number of observed successes, while $\tilde{N}_k(t)$ is a "delay-corrected" count. Rather than simply counting the number of times an arm was pulled, $\tilde{N}_k(t)$ sums the probabilities—based on the known cumulative distribution function (CDF) of the delay—that a reward should have been observed by time $t$. This allows the algorithm to maintain an accurate estimate of the conversion rate even when many outcomes are still pending.

DelayedUCB and DelayedKLUCB

Building on this estimator, the authors adapt the Upper Confidence Bound (UCB) and Kullback-Leibler UCB (KL-UCB) frameworks.

  • DelayedUCB: Adjusts the exploration bonus to account for the effective sample size $\tilde{N}_k(t)$.
  • DelayedKLUCB: Employs a Poissonization argument to handle the aggregation of Bernoulli observations. This is particularly effective in advertising contexts where conversion rates are typically very low (e.g., $\theta \approx 0.1$ or much lower), as it better models the distribution of rare events.

Key Insights

The "Discarding" Trap

A common industry heuristic for dealing with delay is to simply ignore the most recent $m$ actions, as their feedback is considered incomplete. The authors demonstrate that this leads to a "linear regret phase" at the start of learning. During this period, the algorithm effectively learns nothing, wasting valuable exploration opportunities. The proposed delay-corrected approach enables "anytime" learning, extracting partial information from even the most recent pulls.

The Complexity of Censoring

The research proves that the censored setting is fundamentally more difficult than the uncensored one. The regret lower bound increases as the observation window $m$ decreases. Essentially, the difficulty of the bandit problem scales inversely with the probability of observing a conversion within the window, providing a theoretical justification for the performance degradation seen in systems with short memory buffers.

Experimental Results

To validate these models, the authors used simulated data designed to mimic the characteristics of real-world digital advertising, specifically inspired by empirical studies of data from Criteo.

In simulations featuring low conversion rates, DelayedKLUCB significantly outperformed standard UCB-based approaches. A key finding was the avoidance of the initial performance "flat-line" seen in discarding-based benchmarks. By using the delay CDF to calculate the likelihood that a reward is still "on its way," the proposed algorithms began identifying optimal arms much earlier in the experiment's horizon.

Limitations and Future Work

While the framework provides a robust theoretical foundation for delayed rewards, several areas remain for future exploration:

  • Known Delay Distribution: The current model assumes the delay distribution $ au$ is known upfront. While this can often be estimated from historical logs, a fully online model would ideally learn the delay distribution and conversion rates simultaneously.
  • Homogeneity: The paper assumes all arms share the same delay distribution. In reality, different products or ad creatives may have different "incubation periods."
  • Contextual Extensions: The current analysis focuses on the multi-armed case. Extending these delay-correction techniques to contextual bandits, where user features influence both the probability and the delay of a conversion, is a vital next step for practical deployment.

Summary updated

Abstract

Online advertising and product recommendation 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 display but the corresponding sale --if any-- will take hours, if not days to happen. This paper proposes and investigates a new stochas-tic multi-armed bandit model in the framework proposed by Chapelle (2014) --based on empirical studies in the field of web advertising-- in which each action may trigger a future reward that will then happen with a stochas-tic delay. We assume that the probability of conversion associated with each action is unknown 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 algorithms based on the UCB and KLUCB frameworks. The latter algorithm, which is preferable 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.
BibTeX
@inproceedings{vernade2017stochastic,
  author = {Claire Vernade and Olivier Cappé and Vianney Perchet},
  title = {{Stochastic Bandit Models for Delayed Conversions}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=qhZs0c9gC4},
}
Figure