# Biased Dueling Bandits with Stochastic Delayed Feedback

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 50 references that are in the map.
- First posted on arXiv 26 Aug 2024.

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

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Introducing LETOR 4.0 Datasets](https://mlsanity.com/paper/1306.2597/) (2013)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Contextual Dueling Bandits](https://mlsanity.com/paper/1502.06362/) (2015)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Reducing Dueling Bandits to Cardinal Bandits](https://mlsanity.com/paper/1405.3396/) (2014)
- [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)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [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)
- [Copeland Dueling Bandits](https://mlsanity.com/paper/1506.00312/) (2015)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions](https://mlsanity.com/paper/2106.02436/) (2021)
- [Adversarial Dueling Bandits](https://mlsanity.com/paper/2010.14563/) (2020)
- [Learning Adversarial Markov Decision Processes with Delayed Feedback](https://mlsanity.com/paper/2012.14843/) (2020)
- [A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits](https://mlsanity.com/paper/1601.03855/) (2016)
- [Sparse Dueling Bandits](https://mlsanity.com/paper/1502.00133/) (2015)
- [Best arm identification in multi-armed bandits with delayed feedback](https://mlsanity.com/paper/1803.10937/) (2018)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [Delayed Feedback in Generalised Linear Bandits Revisited](https://mlsanity.com/paper/2207.10786/) (2022)
- [Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2201.13172/) (2022)
- [A Nonparametric Delayed Feedback Model for Conversion Rate Prediction](https://mlsanity.com/paper/1802.00255/) (2018)
- [Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm](https://mlsanity.com/paper/1605.01677/) (2016)
- [Dueling Bandits With Weak Regret](https://mlsanity.com/paper/1706.04304/) (2017)
- [Delayed Feedback in Kernel Bandits](https://mlsanity.com/paper/2302.00392/) (2023)

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

- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Quantum Lipschitz Bandits](https://mlsanity.com/paper/2504.02251/) (2025)
- [Lipschitz Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2510.00309/) (2025)

## Abstract (arXiv)

The dueling bandit problem, an essential variation of the traditional multi-armed bandit problem, has become significantly prominent recently due to its broad applications in online advertising, recommendation systems, information retrieval, and more. However, in many real-world applications, the feedback for actions is often subject to unavoidable delays and is not immediately available to the agent. This partially observable issue poses a significant challenge to existing dueling bandit literature, as it significantly affects how quickly and accurately the agent can update their policy on the fly. In this paper, we introduce and examine the biased dueling bandit problem with stochastic delayed feedback, revealing that this new practical problem will delve into a more realistic and intriguing scenario involving a preference bias between the selections. We present two algorithms designed to handle situations involving delay. Our first algorithm, requiring complete delay distribution information, achieves the optimal regret bound for the dueling bandit problem when there is no delay. The second algorithm is tailored for situations where the distribution is unknown, but only the expected value of delay is available. We provide a comprehensive regret analysis for the two proposed algorithms and then evaluate their empirical performance on both synthetic and real datasets.