Stochastic Bandit Models for Delayed Conversions

Claire Vernade, Olivier Cappé, Vianney Perchet

TL;DR

This paper introduces new stochastic multi-armed bandit models designed for scenarios where rewards (such as user conversions in online advertising) occur after a random, potentially infinite delay. The authors establish theoretical regret lower bounds and propose delay-corrected UCB and KL-UCB algorithms that dynamically adjust confidence intervals based on the delay distribution. Their approach prevents the severe performance lags suffered by naive strategies, particularly in realistic, low-conversion settings.

What Problem Does This Paper Address?

Standard multi-armed bandit algorithms assume immediate feedback: you pull an arm, and you instantly see the reward. In many real-world applications like online advertising or product recommendation, this assumption fails completely. While a user might click an ad immediately, the actual target behavior—a purchase or "conversion"—can take hours, days, or weeks to occur.

If an algorithm treats missing immediate feedback as a zero reward, it severely underestimates the value of recently pulled arms. Conversely, if it waits for feedback before updating, it slows down learning. This paper addresses this dilemma by modeling stochastic, potentially infinite delays under two settings:

  1. Uncensored Setting: Conversions are eventually observed, no matter how long the delay.
  2. Censored Setting: The environment enforces a hard time window ($m$), after which any late conversions are permanently unobservable (censored).

Methods

The authors propose a framework that incorporates the Cumulative Distribution Function (CDF) of the delays, denoted as $\tau$, to correct the bandit's internal metrics.

  • Delay-Corrected Estimators: Instead of dividing total rewards by the total number of arm pulls ($N_k$), the algorithms divide by a delay-corrected pull count ($\tilde{N}_k$). This count weights past pulls by the probability that their rewards should have been observed by the current time step. This yields a conditionally unbiased estimator of the true conversion rate.
  • Scaled Confidence Bounds: The uncertainty term in their UCB index is scaled by a factor of $\sqrt{N_k / \tilde{N}_k}$. If an arm has many pending, delayed rewards, $\tilde{N}_k$ is small relative to $N_k$, widening the confidence interval to reflect this heightened uncertainty.
  • Poissonization for KL-UCB: In scenarios with very low conversion rates (common in advertising), standard UCB performs poorly. The authors adapt the more efficient KL-UCB algorithm. However, because delayed feedback effectively scales the underlying Bernoulli trials, standard Kullback-Leibler divergence bounds break down. The authors introduce a novel Poissonization argument, substituting Bernoulli KL divergence with Poisson KL divergence ($d_{Pois}$) to maintain tight, valid upper confidence bounds.

Datasets

The algorithms were evaluated using synthetic simulations designed to mimic real-world digital advertising conditions (motivated by empirical Criteo dataset analyses):

  • Delays: Modeled using a geometric distribution with an expected delay ($\mu$) of 500 time steps.
  • Regimes: Tested under a high conversion rate regime ($\theta_H = [0.5, 0.4, 0.3]$) and a realistic low conversion rate regime ($\theta_L = [0.1, 0.05, 0.03]$).
  • Horizon: Evaluated over $T = 10,000$ steps with a censoring threshold of $m = 1,000$.

Key Insights and Ideas

  • The Danger of Discarding: A naive way to handle censored delays is to simply ignore the most recent $m$ steps of data (the "Discarding" policy). The authors demonstrate that this creates a disastrous linear regret phase at the start of learning because the algorithm operates blindly during the initial window.
  • Uncertainty Inflation: The ratio $N_k / \tilde{N}_k$ elegantly captures the cost of delay. The longer you have to wait for an arm's feedback, the larger your uncertainty grows, naturally forcing the algorithm to explore other options rather than getting stuck.
  • Poisson Approximation Power: The Poissonization trick proves that aggregating independent Bernoulli trials with different delay-dependent success probabilities can be safely managed using a Poisson process approximation, providing near-optimal asymptotic performance without sacrificing mathematical rigor.

Key Results

The experiments validated the theoretical lower bounds derived in the paper:

  • KL-UCB Dominance: In low-conversion settings ($\theta_L$), the DelayedKLUCB algorithm significantly outperformed DelayedUCB, matching the typical performance gap seen in standard immediate-feedback bandits.
  • Mitigating the Delay Penalty: Both proposed algorithms drastically outperformed the naive DISCARDING baseline, entirely avoiding the initial linear regret penalty phase.
Figure 2: Expected regret of D-UCB and D-KLUCB in the censored setting vs the equivalent discarding policies when µ = 500 and m = 1000. Results are averaged over 200 in- dependent runs.
  • Agnostic Learning: In Section 7, the authors showed that even if the delay distribution parameter ($\lambda$) is unknown, estimating it online via a stochastic approximation process ("on-the-go") achieves virtually identical performance to knowing it a priori.

Limitations and Future Work

The primary limitation of the core theoretical model is the assumption that the delay distribution is identical across all arms and independent of context. In real-world advertising, the time it takes a user to buy a product highly depends on the product type and user demographics.

The authors note that an essential future direction is extending this framework to contextual bandits, where the delay distribution is conditioned on context variables via generalized linear models.

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},
}

Loading related content...

Figure