An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays

Julian Zimmert, Yevgeny Seldin

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.

Illustration of the delay handling mechanism and the 'skipping' technique.

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.

Comparison of regret bounds across different delay settings.
  1. 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.
  2. 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

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) fra...
BibTeX
@inproceedings{zimmert2020optimal,
  author = {Julian Zimmert and Yevgeny Seldin},
  title = {{An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=BWnuzYgYvIw},
}
Figure