Stochastic bandits with arm-dependent delays

Anne Gael Manegueu, Claire Vernade, Alexandra Carpentier, Michal Valko

This paper tackles a significant hurdle in applying reinforcement learning to real-world scenarios: delayed feedback. In many applications, such as online advertising or e-commerce, the "reward" (a conversion or purchase) does not happen instantly. Furthermore, the time it takes for that reward to arrive often depends on the action taken—for example, expensive products might have much longer "consideration periods" than cheap ones.

To address this, the authors introduce PatientBandits, the first algorithm designed to handle stochastic multi-armed bandits where delays are arm-dependent, partially observable, and potentially heavy-tailed. They prove that while these delays do not change the long-term asymptotic regret rate, they impose a mathematically unavoidable "performance drop" in the short term.

The Challenge of Arm-Dependent Delays

Standard Multi-Armed Bandit (MAB) models assume that once an arm is pulled, the reward is observed immediately. In reality, feedback is often delayed. Previous research into delayed bandits usually relied on restrictive assumptions, such as full observability (eventually seeing exactly how long every delay was), uniformity (all arms sharing the exact same delay distribution), or boundedness (delays never exceeding a fixed, known time).

This paper breaks these constraints by addressing partially observable delays. If a customer doesn't buy a product, the system never receives a "delay" signal—it just sees a zero reward. This creates a critical identifiability issue: if the best-performing arm also happens to be the slowest, it will look like a "bad" arm for a long time simply because its rewards haven't arrived yet. The authors specifically investigate heavy-tailed delays, which are common in "long-tail" retail environments and can even have infinite expected delays.

Introducing PatientBandits

The authors propose a UCB-based (Upper Confidence Bound) algorithm called PatientBandits.

  • The Core Innovation: Standard UCB algorithms use a "bonus" based on the variance of the reward. PatientBandits adds an extra bias term to the confidence bound. This term explicitly accounts for the rewards that are likely "still in the mail."
  • The $\alpha$ Parameter: The algorithm requires a parameter $\alpha$, representing the "heaviness" of the delay distribution's tail. A smaller $\alpha$ indicates longer, more frequent delays.
  • Adaptivity: They also introduce Adapt-PatientBandits, which uses a quantile-based estimator to "learn" the delay parameter $\alpha$ on the fly, provided the delay distributions follow certain regularity conditions.

Theoretical Insights and Guarantees

In delayed bandits, the learner isn't just fighting noise; they are fighting a systematic bias caused by missing data. The algorithm must "wait" long enough to be sure a zero is a true zero, not just a late arrival.

The authors prove a lower bound showing a "Price of Patience." If delays are heavy-tailed ($\alpha < 1/2$), the regret must grow as $T^{1-\alpha}$. This is significantly worse than the standard $\sqrt{T}$ regret in non-delayed bandits, representing the fundamental cost of arm-dependent delays. However, they also show an asymptotic resilience: as time goes to infinity, the presence of delays only affects the regret by a constant factor, allowing the learning rate to eventually recover.

PatientBandits achieves a problem-dependent upper bound of $O(\sum \frac{\log T}{\Delta_i})$, matching the efficiency of standard UCB algorithms in scaling with time $T$. For the heavy-tailed case, the algorithm achieves a regret of $O(K^\alpha T^{1-\alpha})$, which the authors prove is minimax optimal.

Empirical Performance

The authors evaluate their work using synthetic simulations with Bernoulli reward distributions and Pareto Type I delay distributions. This setup allows them to simulate "difficult" scenarios where the optimal arm is also the one with the longest delays.

Cumulative regret comparison between PatientBandits and D-UCB

In these simulations, PatientBandits significantly outperformed D-UCB (a previous state-of-the-art algorithm) in scenarios where delays varied across arms. D-UCB often failed to identify the best arm because it couldn't account for the heterogeneous "waiting times," whereas PatientBandits successfully managed the bias-variance tradeoff over time.

Limitations and Future Work

The basic PatientBandits algorithm requires prior knowledge of (or a lower bound for) the tail parameter $\alpha$. While the adaptive version mitigates this, it requires tighter assumptions on the shape of the delay distribution and introduces computational overhead to maintain complex statistics about arrival times. Furthermore, the authors prove that without extra assumptions, it is impossible for an algorithm to perfectly adapt to the delay parameter $\alpha$ while maintaining optimal performance across all possible delay types.

Future directions include exploring the gap between the problem-independent upper and lower bounds, and extending this logic to more complex "contextual" bandit settings where user features also influence delays.

Summary updated

Abstract

Significant work has been recently dedicated to the stochastic delayed bandits 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 problemsdependent and problems-independent bounds on the regret as well as performance lower bounds.
BibTeX
@inproceedings{manegueu2020stochastic,
  author = {Anne Gael Manegueu and Claire Vernade and Alexandra Carpentier and Michal Valko},
  title = {{Stochastic bandits with arm-dependent delays}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=Ki7s0vNXnS},
}
Figure