Abstract
Significant work has been recently dedicated to the stochastic delayed bandit setting because of its relevance in applications. The applicability of existing algorithms is however restricted by the fact that strong assumptions are often made on the delay distributions, such as full observability, restrictive shape constraints, or uniformity over arms. In this work, we weaken them significantly and only assume that there is a bound on the tail of the delay. In particular, we cover the important case where the delay distributions vary across arms, and the case where the delays are heavy-tailed. Addressing these difficulties, we propose a simple but efficient UCB-based algorithm called the PatientBandits. We provide both problems-dependent and problems-independent bounds on the regret as well as performance lower bounds.
Introduction
In real-world reinforcement learning and recommendation systems, such as online advertising or e-commerce, rewards rarely arrive immediately. A user might purchase a product days after clicking an ad, creating a scenario of delayed feedback. Existing delayed bandit algorithms typically rely on restrictive assumptions: they often assume delays are fully observable, bounded by a known constant, or identically distributed across all arms.
In practice, delays are often partially observable (censored), arm-dependent (e.g., expensive items take longer to convert), and heavy-tailed. This creates an identifiability issue where an optimal arm with long delays may temporarily appear worse than a suboptimal arm with short delays. This paper introduces PatientBandits to navigate this ambiguity without relying on the restrictive assumptions of prior work.
The PatientBandits Algorithm
The authors propose PatientBandits, an optimistic Upper Confidence Bound (UCB) style algorithm. In standard UCB, confidence intervals are built around estimated means. However, unobservable delayed rewards cause estimators to be inherently biased downward, as missing rewards are indistinguishable from zeros.
To correct this, PatientBandits introduces an extra bias term into its UCB equation. This term explicitly accounts for missing observations by utilizing a known lower bound parameter ($\alpha$) on the polynomial tail of the delay distributions. This forces the algorithm to be "patient," exploring arms that might simply be suffering from long delays. For scenarios where $\alpha$ is unknown, the authors provide Adapt-PatientBandits (Algorithm 2), which estimates this parameter on the fly using extreme value theory.
Theoretical Insights
- Asymptotic Resilience: Surprisingly, in the long run ($T \to \infty$), heavy-tailed delays do not affect regret by more than a constant factor compared to standard bandits. The temporary information loss does not permanently cripple the learner.
- The Price of Heavy Tails: In problem-independent scenarios with extremely heavy-tailed delays ($\alpha < 1/2$), performance drops significantly. Regret degrades from the standard $\sqrt{T}$ to $T^{1-\alpha}$. The authors prove this is a fundamental environmental limit.
- Hardness of Adaptivity: The paper demonstrates a lower bound showing it is mathematically impossible to adapt to the delay tail parameter $\alpha$ without prior knowledge or stricter structural assumptions.
Empirical Evaluation
The algorithms were evaluated using synthetic simulations with Bernoulli rewards and Pareto Type I delay distributions to simulate heavy-tailed, arm-dependent delays.
In "trick" scenarios where the best arm has the longest delays, PatientBandits successfully identifies the optimal arm and achieves sub-linear regret. In contrast, the baseline D-UCB—which assumes homogeneous delays—focuses on fast-but-suboptimal arms, resulting in linear regret. Theoretically, PatientBandits achieves a problem-dependent regret of $\mathcal{O}(\sum \frac{\log T}{\Delta_i})$, matching standard UCB asymptotically.
Conclusion
While PatientBandits effectively handles complex delay structures, the base version requires prior knowledge of the tail parameter $\alpha$. The adaptive variant mitigates this but requires stronger structural assumptions. Future work may focus on closing the minor mathematical gaps in problem-independent bounds and extending these insights to contextual bandits or full reinforcement learning setups.
Summary updated