# Delayed Bandits: When Do Intermediate Observations Help?

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 67 references that are in the map.
- First posted on arXiv 30 May 2023.

## Builds on (most cited first, 20 of 20)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays](https://mlsanity.com/paper/1910.06054/) (2019)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [Adapting to Delays and Data in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2010.06022/) (2020)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [A Generalized Online Mirror Descent with Applications to Classification and Regression](https://mlsanity.com/paper/1304.2994/) (2013)
- [Nonstochastic Bandits and Experts with Arm-Dependent Delays](https://mlsanity.com/paper/2111.01589/) (2021)
- [No Weighted-Regret Learning in Adversarial Bandits with Delays](https://mlsanity.com/paper/2103.04550/) (2021)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [On the Complexity of Learning with Kernels](https://mlsanity.com/paper/1411.1158/) (2014)
- [Confidence Decision Trees via Online and Active Learning for Streaming (BIG) Data](https://mlsanity.com/paper/1604.03278/) (2016)
- [See the Tree Through the Lines: The Shazoo Algorithm -- Full Version --](https://mlsanity.com/paper/1301.5160/) (2013)
- [Multitask Protein Function Prediction Through Task Dissimilarity](https://mlsanity.com/paper/1611.00962/) (2016)

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

- [Contextual Linear Bandits with Delay as Payoff](https://mlsanity.com/paper/2502.12528/) (2025)
- [Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs](https://mlsanity.com/paper/2503.19856/) (2025)
- [Exploiting Curvature in Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2506.07595/) (2025)
- [A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees](https://mlsanity.com/paper/2602.02634/) (2026)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [Capacity-Constrained Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2606.11711/) (2026)
- [Pooling and Drift in Delayed Bandits](https://mlsanity.com/paper/2609.01761/) (2026)
- [Delay Complexity Dimension: Learning with Delayed and Censored Labels](https://mlsanity.com/paper/2610.18935/) (2026)

## Abstract (arXiv)

We study a K-armed bandit with delayed feedback and intermediate observations. We consider a model where intermediate observations have a form of a finite state, which is observed immediately after taking an action, whereas the loss is observed after an adversarially chosen delay. We show that the regime of the mapping of states to losses determines the complexity of the problem, irrespective of whether the mapping of actions to states is stochastic or adversarial. If the mapping of states to losses is adversarial, then the regret rate is of order √(K+d)T (within log factors), where T is the time horizon and d is a fixed delay. This matches the regret rate of a K-armed bandit with delayed feedback and without intermediate observations, implying that intermediate observations are not helpful. However, if the mapping of states to losses is stochastic, we show that the regret grows at a rate of √big(K+min|S|,dbig)T (within log factors), implying that if the number |S| of states is smaller than the delay, then intermediate observations help. We also provide refined high-probability regret upper bounds for non-uniform delays, together with experimental validation of our algorithms.