Abstract
We propose a new algorithm for adversarial multi-armed bandits with unrestricted delays. The algorithm is based on a novel hybrid regularizer applied in the Follow the Regularized Leader (FTRL) framework, achieving optimal regret bounds without requiring prior knowledge of the time horizon or total delay.
Introduction
In the standard multi-armed bandit (MAB) problem, a learner selects an action and receives immediate feedback. However, real-world applications like online advertising or clinical trials often involve significant delays between an action and its observed outcome. In adversarial settings, where losses are chosen by an opponent, handling these delays is particularly challenging.
Previous research into adversarial bandits with delays faced several hurdles: the need for prior knowledge of the time horizon ($n$) or total delay ($D$), reliance on inefficient "doubling schemes," and loose bounds when delays are unbalanced. This paper introduces an "anytime" algorithm that addresses these limitations, providing optimal performance for any sequence of delays, even when they are highly skewed.
Methodology
The proposed algorithm utilizes the Follow the Regularized Leader (FTRL) framework. The learner selects actions by minimizing the sum of past estimated losses plus a regularizer function $F_t(x)$.
Hybrid Regularizer
The core innovation is a novel hybrid regularizer that combines two mathematical tools: $\frac{1}{2}$-Tsallis Entropy, the standard for bandits without delays, and Negative Entropy, typically used in full-information settings. By assigning separate, independent learning rates to these components, the algorithm treats the bandit exploration and the delay uncertainty with specialized tools. The learning rate for the negative entropy component is adaptive, based on the number of "outstanding" observations—those that have been initiated but not yet received.
Advanced Tuning and Skipping
To handle highly unbalanced delays, the authors introduce an "Advanced Tuning" technique. If an observation's delay exceeds a certain threshold, the algorithm "skips" that round when calculating the adaptive learning rate. This prevents a small number of massive delays from making the algorithm overly conservative. Crucially, the delayed data is still incorporated once it eventually arrives, ensuring no information is lost.
Theoretical Results
The paper establishes two major theoretical guarantees for "regret"—the difference between the learner's performance and that of the best fixed action in hindsight.
- Optimal General Bound: The algorithm achieves a regret of $O(\sqrt{kn} + \sqrt{D \log k})$, matching known lower bounds. This indicates that no algorithm can perform significantly better in the worst case.
- Adaptive Bound for Unbalanced Delays: With advanced tuning, the regret is refined to $O(\sqrt{kn} + \min_S(|S| + \sqrt{D_{\bar{S}} \log k}))$. This bound is significantly tighter when a few rounds ($S$) have outlier delays, as the performance only degrades linearly with the number of outliers and sub-linearly with the remaining "reasonable" delays ($D_{\bar{S}}$).
Conclusion and Future Directions
This work resolves several open problems in the field of adversarial bandits with delays, specifically by providing an anytime algorithm that handles unbalanced delays optimally. While the focus is on the adversarial setting, the authors conjecture that the algorithm may also be optimal in stochastic environments. Future work could involve formally proving this stochastic optimality and exploring more computationally efficient implementations of the hybrid regularizer minimization.
Summary updated