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:
- 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.
- 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