# Bayesian Optimization under Stochastic Delayed Feedback

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 85 references that are in the map.
- First posted on arXiv 19 Jun 2022.

## Builds on (most cited first, 30 of 44)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Batch Bayesian Optimization via Local Penalization](https://mlsanity.com/paper/1505.08052/) (2015)
- [Federated Bayesian Optimization via Thompson Sampling](https://mlsanity.com/paper/2010.10154/) (2020)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Differentially Private Federated Bayesian Optimization with Distributed Exploration](https://mlsanity.com/paper/2110.14153/) (2021)
- [Best arm identification in multi-armed bandits with delayed feedback](https://mlsanity.com/paper/1803.10937/) (2018)
- [NASI: Label- and Data-agnostic Neural Architecture Search at Initialization](https://mlsanity.com/paper/2109.00817/) (2021)
- [Decentralized High-Dimensional Bayesian Optimization with Factor Graphs](https://mlsanity.com/paper/1711.07033/) (2017)
- [Top-k Ranking Bayesian Optimization](https://mlsanity.com/paper/2012.10688/) (2020)
- [Value-at-Risk Optimization with Gaussian Processes](https://mlsanity.com/paper/2105.06126/) (2021)
- [Attribution Modeling Increases Efficiency of Bidding in Display Advertising](https://mlsanity.com/paper/1707.06409/) (2017)
- [Bandit Online Learning with Unknown Delays](https://mlsanity.com/paper/1807.03205/) (2018)
- [Implicit Posterior Variational Inference for Deep Gaussian Processes](https://mlsanity.com/paper/1910.11998/) (2019)
- [Efficient Exploration of Reward Functions in Inverse Reinforcement Learning via Bayesian Optimization](https://mlsanity.com/paper/2011.08541/) (2020)
- [Gaussian Process Planning with Lipschitz Continuous Reward Functions: Towards Unifying Bayesian Optimization, Active Learning, and Beyond](https://mlsanity.com/paper/1511.06890/) (2015)
- [Bayesian Optimization with Binary Auxiliary Information](https://mlsanity.com/paper/1906.07277/) (2019)
- [Private Outsourced Bayesian Optimization](https://mlsanity.com/paper/2010.12799/) (2020)
- [An Information-Theoretic Framework for Unifying Active Learning Problems](https://mlsanity.com/paper/2012.10695/) (2020)
- [Censored Semi-Bandits: A Framework for Resource Allocation with Censored Feedback](https://mlsanity.com/paper/1909.01504/) (2019)
- [On Batch Bayesian Optimization](https://mlsanity.com/paper/1911.01032/) (2019)
- [R2-B2: Recursive Reasoning-Based Bayesian Optimization for No-Regret Learning in Games](https://mlsanity.com/paper/2006.16679/) (2020)
- [Nonmyopic Gaussian Process Optimization with Macro-Actions](https://mlsanity.com/paper/2002.09670/) (2020)

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

- [Sample-Then-Optimize Batch Neural Thompson Sampling](https://mlsanity.com/paper/2210.06850/) (2022)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [Delayed Feedback in Kernel Bandits](https://mlsanity.com/paper/2302.00392/) (2023)
- [Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints](https://mlsanity.com/paper/2211.14720/) (2022)
- [Batch Bayesian Optimization for Replicable Experimental Design](https://mlsanity.com/paper/2311.01195/) (2023)
- [Training-Free Neural Active Learning with Initialization-Robustness Guarantees](https://mlsanity.com/paper/2306.04454/) (2023)
- [TS-RSR: A provably efficient approach for batch Bayesian Optimization](https://mlsanity.com/paper/2403.04764/) (2024)
- [Lipschitz Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2510.00309/) (2025)
- [Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2608.16492/) (2026)
- [Linear and Neural Dueling Bandits with Delayed Feedback](https://mlsanity.com/paper/2605.26554/) (2026)

## Abstract (arXiv)

Bayesian optimization (BO) is a widely-used sequential method for zeroth-order optimization of complex and expensive-to-compute black-box functions. The existing BO methods assume that the function evaluation (feedback) is available to the learner immediately or after a fixed delay. Such assumptions may not be practical in many real-life problems like online recommendations, clinical trials, and hyperparameter tuning where feedback is available after a random delay. To benefit from the experimental parallelization in these problems, the learner needs to start new function evaluations without waiting for delayed feedback. In this paper, we consider the BO under stochastic delayed feedback problem. We propose algorithms with sub-linear regret guarantees that efficiently address the dilemma of selecting new function queries while waiting for randomly delayed feedback. Building on our results, we also make novel contributions to batch BO and contextual Gaussian process bandits. Experiments on synthetic and real-life datasets verify the performance of our algorithms.