Nonstochastic Bandits and Experts with Arm-Dependent Delays

Abstract

We study nonstochastic bandits and experts in a delayed setting where delays depend on both time and arms. While the setting in which delays only depend on time has been extensively studied, the arm-dependent delay setting better captures real-world applications at the cost of introducing new technical challenges. In the full information (experts) setting, we design an algorithm with a first-order regret bound that reveals an interesting trade-off between delays and losses. We prove a similar first-order regret bound also for the bandit setting, when the learner is allowed to observe how many losses are missing. These are the first bounds in the delayed setting that depend on the losses and delays of the best arm only. When in the bandit setting no information other than the losses is observed, we still manage to prove a regret bound through a modification to the algorithm of Zimmert and Seldin (2020). Our analyses hinge on a novel bound on the drift, measuring how much better an algorithm can perform when given a look-ahead of one round.

References in corpus (10)

• Efficient Optimal Learning for Contextual Bandits
• More Adaptive Algorithms for Adversarial Bandits
• Delay and Cooperation in Nonstochastic Bandits
• Bandits with Delayed, Aggregated Anonymous Feedback
• Learning in Games: Robustness of Fast Convergence
• Nonstochastic Bandits with Composite Anonymous Feedback
• AdaDelay: Delay Adaptive Distributed Stochastic Convex Optimization
• Stochastic bandits with arm-dependent delays
• Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism
• Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications