# Best arm identification in multi-armed bandits with delayed feedback

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

## Key facts

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

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

- [Diffusion Models for Black-Box Optimization](https://mlsanity.com/paper/2306.07180/) (2023)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [Generative Pretraining for Black-Box Optimization](https://mlsanity.com/paper/2206.10786/) (2022)
- [Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delay](https://mlsanity.com/paper/2307.09943/) (2023)
- [Bayesian Optimization under Stochastic Delayed Feedback](https://mlsanity.com/paper/2206.09341/) (2022)
- [Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2111.03917/) (2021)
- [Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits](https://mlsanity.com/paper/2106.14866/) (2021)
- [Optimal Batched Best Arm Identification](https://mlsanity.com/paper/2310.14129/) (2023)
- [Adaptive Elicitation of Latent Information Using Natural Language](https://mlsanity.com/paper/2504.04204/) (2025)
- [Partial Likelihood Thompson Sampling](https://mlsanity.com/paper/2203.00820/) (2022)
- [Biased Dueling Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2408.14603/) (2024)
- [PAC Best Arm Identification Under a Deadline](https://mlsanity.com/paper/2106.03221/) (2021)
- [Smooth Sequential Optimisation with Delayed Feedback](https://mlsanity.com/paper/2106.11294/) (2021)
- [Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutions](https://mlsanity.com/paper/2208.05844/) (2022)
- [Adaptive Experimentation at Scale: A Computational Framework for Flexible Batches](https://mlsanity.com/paper/2303.11582/) (2023)
- [Multi-Agent Bandit Learning through Heterogeneous Action Erasure Channels](https://mlsanity.com/paper/2312.14259/) (2023)
- [A Batch Sequential Halving Algorithm without Performance Degradation](https://mlsanity.com/paper/2406.00424/) (2024)
- [Comparative Performance of Collaborative Bandit Algorithms: Effect of Sparsity and Exploration Intensity](https://mlsanity.com/paper/2410.12086/) (2024)
- [Best-Arm Identification with Generative Proxy](https://mlsanity.com/paper/2607.06879/) (2026)
- [Optimal Algorithms for Range Searching over Multi-Armed Bandits](https://mlsanity.com/paper/2105.01390/) (2021)
- [Multi-armed Bandit Algorithms on System-on-Chip: Go Frequentist or Bayesian?](https://mlsanity.com/paper/2106.02855/) (2021)
- [Adaptively Optimize Content Recommendation Using Multi Armed Bandit Algorithms in E-commerce](https://mlsanity.com/paper/2108.01440/) (2021)
- [Sales Channel Optimization via Simulations Based on Observational Data with Delayed Rewards: A Case Study at LinkedIn](https://mlsanity.com/paper/2209.07749/) (2022)
- [Budgeted Recommendation with Delayed Feedback](https://mlsanity.com/paper/2405.11417/) (2024)
- [Short-Long Policy Evaluation with Novel Actions](https://mlsanity.com/paper/2407.03674/) (2024)
- [Predicting Long Term Sequential Policy Value Using Softer Surrogates](https://mlsanity.com/paper/2412.20638/) (2024)
- [Linear and Neural Dueling Bandits with Delayed Feedback](https://mlsanity.com/paper/2605.26554/) (2026)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)

## Abstract (arXiv)

We propose a generalization of the best arm identification problem in stochastic multi-armed bandits (MAB) to the setting where every pull of an arm is associated with delayed feedback. The delay in feedback increases the effective sample complexity of standard algorithms, but can be offset if we have access to partial feedback received before a pull is completed. We propose a general framework to model the relationship between partial and delayed feedback, and as a special case we introduce efficient algorithms for settings where the partial feedback are biased or unbiased estimators of the delayed feedback. Additionally, we propose a novel extension of the algorithms to the parallel MAB setting where an agent can control a batch of arms. Our experiments in real-world settings, involving policy search and hyperparameter optimization in computational sustainability domains for fast charging of batteries and wildlife corridor construction, demonstrate that exploiting the structure of partial feedback can lead to significant improvements over baselines in both sequential and parallel MAB.