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