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 based on a novel hybrid regularizer applied in the Follow the Regularized Leader (FTRL) framework. The algorithm achieves an $\mathcal{O}(\sqrt{kn}+\sqrt{D\log(k)})$ regret guarantee, where $k$ is the number of arms, $n$ is the number of rounds, and $D$ is the total delay. This result matches theoretical lower bounds within constants and requires no prior knowledge of $n$ or $D$. Additionally, we introduce a refined tuning mechanism that achieves an $\mathcal{O}(\sqrt{kn}+\min_{S}(|S|+\sqrt{D_{\bar S}\log(k)}))$ regret guarantee, effectively handling highly unbalanced delays. This work resolves several open problems regarding anytime algorithms and the removal of doubling tricks in delayed bandit settings.

The Challenge of Delayed Feedback

In the classic multi-armed bandit problem, a learner chooses an action and immediately observes the resulting reward or loss. However, real-world systems—such as recommendation engines or clinical trials—rarely provide immediate feedback. There is often a significant, and sometimes unpredictable, delay between an action and its observation.

This paper addresses the oblivious adversarial bandit setting with arbitrary delays, where an adversary chooses the sequence of losses and delays before the game begins. While previous state-of-the-art algorithms could achieve optimal regret bounds, they often relied on "cheat codes": prior knowledge of the total time horizon ($n$), the total sum of delays ($D$), or the specific delay of a round at the moment the action was taken. The goal of this research is to achieve optimal regret in a completely anytime fashion, without advance knowledge of the environment's temporal dynamics.

A Novel Hybrid Regularizer Approach

The authors utilize the Follow the Regularized Leader (FTRL) framework, introducing a "hybrid regularizer" to manage the trade-off between exploration and exploitation under delay. The regularizer is split into two distinct parts, each with its own learning rate:

  1. $\frac{1}{2}$-Tsallis entropy: Optimal for standard, non-delayed bandit settings.
  2. Negative entropy: Optimal for full-information games.

By combining these, the algorithm simultaneously targets the two components of the theoretical lower bound: the standard bandit penalty ($\sqrt{kn}$) and the penalty for playing "blind" due to delays ($\sqrt{D \log(k)}$).

Key Innovations: Observability and Adaptive Skipping

To make the algorithm truly anytime and adaptive, the authors introduced two critical mechanisms:

  • Tuning via Outstanding Observations: Instead of tuning learning rates based on unknown future delays, the algorithm uses the number of outstanding observations at the current round—a fully observable quantity. This allows the learner to adapt to the environment as it unfolds.
  • Adaptive Skipping: In scenarios where delays are highly unbalanced (e.g., one round has a massive delay while others are immediate), waiting for the outlier can degrade the learning rate for all subsequent rounds. The authors developed a technique to "skip" (stop waiting for) excessively delayed observations by adaptively calculating a timeout threshold. If an observation exceeds this threshold, the algorithm assumes a worst-case loss and moves on, preventing a single outlier from poisoning the entire learning process.

Theoretical Results and Performance

The proposed algorithm achieves minimax optimal regret bounds across various settings. Notably, it matches the lower bounds for uniform and arbitrary delays without requiring the "doubling trick" or prior knowledge of $n$ or $D$.

Comparison of regret bounds across different delay settings.

As shown in the table above, the "This paper" entries demonstrate improvements or parity with existing literature while operating under more restrictive (and realistic) information constraints. Specifically, the refined bound for unbalanced delays (Theorem 2) provides a significant theoretical speedup in cases where a small subset of rounds accounts for the majority of the total delay.

Conclusion and Future Directions

This work provides a robust, anytime solution for adversarial bandits with arbitrary delays. By shifting the focus from unknown variables to observable states and employing a hybrid regularization strategy, the authors have resolved long-standing open questions in the field.

Future work may explore the tightness of the adaptive skipping bound and investigate whether this hybrid FTRL approach can achieve logarithmic regret in stochastic delayed settings, potentially offering a unified solution for both adversarial and stochastic environments.

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) framework. It achieves $\mathcal{O}(\sqrt{kn}+\sqrt{D\log(k)})$ regret guarantee, where $k$ is the number of arms, $n$ is the number of rounds, and $D$ is the total delay. The result matches the lower bound within constants and requires no prior knowledge of $n$ or $D$. Additionally, we propose a refined tuning of the algorithm, which achieves $\mathcal{O}(\sqrt{kn}+\min_{S}|S|+\sqrt{D_{\bar S}\log(k)})$ regret guarantee, where $S$ is a set of rounds excluded from delay counting, $\bar S = [n]\setminus S$ are the counted rounds, and $D_{\bar S}$ is the total delay in the counted rounds. If the delays are highly unbalanced, the latter regret guarantee can be significantly tighter than the former. The result requires no advance knowledge of the delays and resolves an open problem of Thune et al. (2019). The new FTRL algorithm and its refined tuning are anytime and require no doubling, which resolves another open problem of Thune et al. (2019).
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