# Bandit Online Learning with Unknown Delays

arXiv: https://arxiv.org/abs/1807.03205 · HTML: https://mlsanity.com/paper/1807.03205/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2018.

## Built on by (most cited first, 18 of 18)

- [Nonstochastic Bandits with Composite Anonymous Feedback](https://mlsanity.com/paper/2112.02866/) (2021)
- [Online Strongly Convex Optimization with Unknown Delays](https://mlsanity.com/paper/2103.11354/) (2021)
- [Bayesian Optimization under Stochastic Delayed Feedback](https://mlsanity.com/paper/2206.09341/) (2022)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Asynchronous Gradient Play in Zero-Sum Multi-agent Games](https://mlsanity.com/paper/2211.08980/) (2022)
- [Online Sequential Decision-Making with Unknown Delays](https://mlsanity.com/paper/2402.07703/) (2024)
- [Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback](https://mlsanity.com/paper/2510.09127/) (2025)
- [Projection-free Online Learning with Arbitrary Delays](https://mlsanity.com/paper/2204.04964/) (2022)
- [Dynamical Linear Bandits](https://mlsanity.com/paper/2211.08997/) (2022)
- [Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-Fidelity Feedback](https://mlsanity.com/paper/2110.07232/) (2021)
- [Lazy Queries Can Reduce Variance in Zeroth-order Optimization](https://mlsanity.com/paper/2206.07126/) (2022)
- [Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback](https://mlsanity.com/paper/2204.12764/) (2022)
- [Stochastic Contextual Bandits with Long Horizon Rewards](https://mlsanity.com/paper/2302.00814/) (2023)
- [Learning from Delayed Feedback in Games via Extra Prediction](https://mlsanity.com/paper/2509.22426/) (2025)
- [Risk-averse learning with delayed feedback](https://mlsanity.com/paper/2409.16866/) (2024)
- [Revisiting Multi-Agent Asynchronous Online Optimization with Delays: the Strongly Convex Case](https://mlsanity.com/paper/2503.10013/) (2025)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)
- [Linear Convergence in Games with Delayed Feedback via Extra Prediction](https://mlsanity.com/paper/2602.17486/) (2026)

## Abstract (arXiv)

This paper deals with bandit online learning problems involving feedback of unknown delay that can emerge in multi-armed bandit (MAB) and bandit convex optimization (BCO) settings. MAB and BCO require only values of the objective function involved that become available through feedback, and are used to estimate the gradient appearing in the corresponding iterative algorithms. Since the challenging case of feedback with unknown delays prevents one from constructing the sought gradient estimates, existing MAB and BCO algorithms become intractable. For such challenging setups, delayed exploration, exploitation, and exponential (DEXP3) iterations, along with delayed bandit gradient descent (DBGD) iterations are developed for MAB and BCO, respectively. Leveraging a unified analysis framework, it is established that the regret of DEXP3 and DBGD are cal Obig( √Kbard(T+D) big) and cal Obig( √K(T+D) big), respectively, where bard is the maximum delay and D denotes the delay accumulated over T slots. Numerical tests using both synthetic and real data validate the performance of DEXP3 and DBGD.