Biased Dueling Bandits with Stochastic Delayed Feedback
Authors: Bongsoo Yi
Yue Kang
Yao Li
Venue: Accepted by TMLR ()

Abstract: 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.

Published in Transactions on Machine Learning Research (08/2024)
Biased Dueling Bandits with Stochastic Delayed Feedback
Bongsoo Yi
bongsoo &unc. eduu
Deportment of Statistics and Operations Research University of North Carolina at Chapel Hill
Yue Kang
yuckang@uodavis.c edu
Department Statistics University of California, Davis
Yao Li
yooli@unc.edd edu
Department of Statistics and Operations Research University of North Carolina al Chapel Hill
Reviewed OpenReview: https: opennevveeen...veeeeu net/ formm? id= HuAZDVakIX
Abstract
The dueling bandit problem, 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 not immediately available to the agent. This partially observable issue poses a significant challenge to existing ducling 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 more realistic and intriguing scenario involving preference bias between the selections. We present two algorithms designed to handle situa- tions involving delay. Our first algorithm, requiring complete delay distribution information, achioves the optimal rogret bound for the ducling bandit problem when there no delay. The second algorithm is lailored for situations where the distribution is unknown, but only the expected value of delay available. We provide comprehensive regret analysis for the two proposed algorithms and then evaluate their empirical performance on both synthetic and real datasets.
Introduction
In recent years, the dueling bandit problem has gained significant attention, finding wide applications in practical domains such as online advertising and recommendation systems (Yue & Joachims
2009 Ailon
eet al. 2014 Zoghi et al.) 2014a 2015b Komiyama et al. 2015 Agarwal et al. (021). The K Karred dueling
bandil problem (Yue al.] 2012 is a variation of the classical K-armed bandit problem (Auer et al. 2002)
providing only relative comparison instcad of absolute foodback. In the ducling bandit problem, the learner is presented with K arms. At each trial, the learner selects a pair of arms and receives stochastic feedback indicating which of the two chosen options is preferred, based model. This setup enables users to express their preference for one item over another rather than assigning numerical scores. Recognizing the challenges of consistently offering accurate absolute reviews, leveraging preference feedback with dueling bandits has emerged as a practical approach, gaining widespread popularity in online learning (Radlinski et al. 2008
underlying stochastic pairwise preference
While existing studies in ducling bandit problem (Zoghi al. 2014a Komiyama al. 2015) assume
immediate feedback observation, major practical challenge in real-world applications is the issue of delayed

---

Published in Transactions on Machine Learning Research (08/2024)
Rccommandation
Which one better?
Product
Observed
A
Click Observed
A
Click A + A
Buy
Unobserved
A>
Click B + A
Product
Product A
Product B
(a) Biased dueling bandit with delayed leedback
(b) Traditonal dueling bandit
Figure Case (a) illustrates the e-commerce example of the biased dueling bandit with delayed feedback: delay occurs before the user can evaluate and potentially select Product B, and any data collected during this delay suggests A >> B. Case (b) showcases the traditional ducling bandit with immediate feodback.
foedback. In practice, feedback on actions often not observable until after a random period. For example, in recommendations within e-commerce (Vernade et al. 2017]; it takes time for users to decide whether to buy a product. Moreover, if user has chosen not to purchase, the system remains unaware of this decision. It cannot distinguish whether the decision is not to buy or if the user has not made decision yet, dilemma often referred to as the delayed conversion problem. This complexity introduces significant challenges in managing delayed leedback. A similar siluation occurs with web advertisements (Chapelle) 2014 Yoshikawa & Imai 2018). Users take time to consider whether to click on an ad after viewing it. However, the system must continuc display ads other users before recciving this foodback. In particular, Chapelle (2014) analyzed data from the online advertising company Criteo and confirmed that only 35% of leedback observed within hour, while 50% was observed after 24 hours, and notably, 13% emerged two weeks later. Another instance can be seen in clinical trials (Chow & Chang 2006), where the impact of medical treatment on a patient's health frequently encounters delays. Due to these real-world challenges, the past few years have witnessed extensive research on various types of bandit problems with delayed feedback (Vernade et al. 2017 Grover et al. 2018). However, to the best of our knowledge, all the existing literature merely focuses on the bandit problems with absolute numerical rewards, and how to handle the delayed feedback under the practical dueling bandit problem receiving relative preferences between pairs still remains unexplored.
In this work, we introduce by stochastic delay between the selection of action pairs and the receipl of corresponding preference feedback. Different from other types of bandits with delayed feedback, we further delve into a more practical and challenging problem called biased dueling bandits under delayed feedback. Specifically, we keep the same formulation as other bandit literature with binary rewards (Vernade et al.) 2017 2020): the player observes a zero value when the reward for an action inaccessible due delay. However, unlike other bandits with absolute numerical rewards where pulling one arm does not provide direct information about the others, the dueling bandit outputs binary responses revealing relative preference between pairs of arms. Consequently, the zero rewards under dueling bandits indicate biased preference for one arm, particularly when rewards are delayed, making the delay effect much more malicious and challenging to handle. This treatment naturally gives an advantage to the second arm in a pair. For example, if arm i is presented first and arm j second, and the reward delayed, the player observes a zero value while making a decision. This results in arm j being favored, while arm i suffers from the delay-induced bias. We will further elaborate on this issue in Section 2 In practice, this bias in our problem setting is very common and can be characterized location effect indicating that one has intrinsic advantage over the other. For instance, in the e-commerce recommendation shown in Figure I (a), user is browsing product A, and the platform suggests product B on the sidebar. Before the user makes the comparison after some delay, we can only observe the user stay al product A and hence assume the user likes A over B. In other words, due to the common delay before the user can compare and perhaps select product B, any data collected during that delay may inaccurately suggest a preference for product A. This comparative bias exists in many real-wort world applications, and highlights a unique and practical challenge implementing ducling bandit algorithms with delayed feedback, compared to other bandit algorithms with delayed feedback where each
problem of ducling bandits in the presence of delayed feedback, characterized
as the prior knowledge
2

---

Published in Transactions on Machine Learning Research (08/2024)
arm is evaluated based on independent selections and feedback, even if the feedback is delayed. Therefore, given the existing literature on bandits with delayed feedback, our work is highly novel and intriguing since we successfully address both the usual challenges of delayed feedback and the additional practical concerns of bias simultancously.
Given the broad applicability of the dueling bandit: problem and the significance of handling delayed feedback in real-world applications, our paper explores the dueling bandit with delayed feedback and presents two ducling bandit algorithms designed to handle stochastic delayed feedback. We note that the proposed algorithm can also be applied in general cases where there is no delay. Our main contributions can be summarized as follows:
We describe and formulate a novel biased dueling bandit framework that incorporates stochastic delayed feedback.
We present RUCB-Delay (Relative Upper Confidence Bound with delayed feedback), which deals with delayed feedback by employing the delay distribution information. We establish the regret bound for the algorithm and demonstrate that it matches the regret lower bound of the dueling bandit problem when all delays are zero.
We introduce and analyze another algorithm, MRR-DB-Delay (Multi Round-Robin Dueling Bandit with delayed feedback), suitable for situations where the delay distribution is unknown. The algo- rithm requires only the expected value of the delay, making it versatile and applicable in various cases.
We conduct an empirical evaluation of the performance of six synthetic and real-world datasets.
RUCB-Delay and MRR-DB-Delay using
1.1 Related Work
Originating from the practical benefits of considering relative feedback over absolute feedback, the duel- ing bandit problem, initially introduced by Yue et al. (2009), has been widely investigated across various settings. Yue et al.] (2009) began with strong assumptions, relying on strong stochastic transitivity and stochastic triangle incquality, which may frequently not align with real-world cases. Yue & Joachims (2011) suggested setting on relaxed form of strong stochastic transitivity, although this remained fairly re- strictive condition. In response, Urvoy et al. (2013) introduced the Condorcet winner sctting, where we assume the existence of unique best arm. Subsequent efforts have been made to generalize the concept of the Condorcet winner, including alternatives like Borda winner (Jamieson et al.) 2015 Saha et al.) 2021) Copeland winner (Zoghi et al.] 2015a Komiyama et al. 2016), and Von-Neumann winner (Dudik et al. Nevertheless, our locus in this study remains on the Condorcet winner Assumption, a premise commonly found in various other studies (Zoghi et al. 201 4a bj 2015b Komiyama
2015
Balsubramani et al.] 2016).
et al.
2015
Chen & Frazier 2017 Haddenhorst et al. 2021 Agarwal et al. 2021 Saha & GGailladd 2022).
2013) and Zoghi et al. (2013 presented algorithms with a regret bound of O(K² log T)) for the dueling bandit. problem in the Condorcet winner setting. Subsequently, Zoghi et al. (0114a) and Komiyama et al. 2015 introduced RUCB and RMED algorithms,, respectively, achieving a bound of O(K2 + K log lo) that matches a lower bound established in Yuue et al. 2012 RUCB is built on the estimation of pairwise probabilities and utilizes the Upper Confidence Bound (UCB) strategy to select the best arm, whereas RMED explores the likelihood of each arm being the Condorcet winner. Several other studics have examined the dueling bandit. problem in specific settings, including investigations into robustness to corruptions (Agarwal et al. 2021), oest-of-hu both world scenarios (Saha & Gaillard 2022), and adversarial settings (Gajane et al,, 2015 Saha et al.] 2021). To the best of our knowledge, our paper is the first to explore the ducling bandit problem with stochastic delayed feedback.
Crvoy et al.
Delayed feedback, given its practical significance, has been a key area research in multi-armes bandits and online learning (Joulani al.) 2013 Vernade et al. 2017 Grover et al. 2018 Gael et al.] (020): Lancewicki et al.] 2021). A thorough analysis of online learning problems with delayed feedback including partial monitoring settings is given in Joulani et al. (2013). Additionally, Vernade et al. (0117) proposed algorithms
3

---

Published in Transactions on Machine Learning Research (08/2024)
for delayed conversions in multi-armed bandits, assuming full knowledge of the delay distribution. Pike-Burks et al. (2018) addressed a more complex problem related to delayed, aggregated anonymous feedback. Here, the player only observes the sum of rewards received in each round after certain delays, without information about which past actions contributed to this aggregated reward. Delays have also boen extensively explored in the adversarial selting Bessa-Bianchi et al., 2016 Bistritz et al.] 2019 Thune et al. 2019 Zimuert & Soldin 2020). Furthermore, recent studies have investigated delays various bandit scttings and objectives, including linear bandits (Vernade et al. 2020), generalized linear bandits (Zhou et al. 2019 Howson et al. )023), kernel bandits (Vakili et al., 2023), adversarial Markov decision processes (Lancewicki et al. 2022
Jin et al. 2022), and best-of-both-wordds algorithms (Masoudian et al. 2022
Saha & Gaillard 2022
1.2
Organization
The structure of the remaining sections in this paper is as follows: Section 2 provides formal description of our problem setting. Following that, in Section 3 we introduce the RUCB-Delay algorithm, applicable when complete knowledge of the delay distribution is known. Section | presents another algorithm, MRR- DR-Delay, designed for scenarios where the delay distribution is unknown, with only the expected value known. The comprehensive regret analysis for the two algorithms, RUCB-Delay and MRR-DB-Delay, is also provided in Sections [ and [ respectively. In Section []] we demonstrate the performance of our two algorithms using various simulated and real-world datasets. Finally, we conclude with a discussion of our results in Scction 0
2 Problem Setting
In this paper, we investigate a dueling bandit problem with K arms, denoted as (1, At each time step, we select a pair of arms (i,j) and obtain the outcome of a pairwise comparison between the selected arms, which is subject to delay. The outcome of the pairwise comparison between (i,j) is stochastically determined by a probability Pkj, where Pij represents the likelihood of arm beating arm j in a comparison between the two arms. The delay is decided by a discrete distribution D, which is supported on N and is independent of the selection of arm pairsl We assume the existence of Condorces winner (Urvoy et al. 2013), specifically arm without loss of generality. This implies that there exists unique arm, i.e. arm 1, with M1s P(1 i) held for all # 1.
In this work, we introduce new problem of dueling bandits under the presence of delayed feedback. The exact procedure repeats the following steps:
1. At time step f. the player selects pair of arms (ue, v1)-
2. The environment stochastically samples an outcome X, T(me > ve) E (0, 1) from the Bernoulli distribution B() Additionally, it determines delay D, E N from the delay distribution D.
At the beginning of time step t+ 1, the player receives outcomes from carlier rounds. For 8 < + the censoring variable I(D, S t +++1-s) determines whether the outcome from time step s is revealed by time step t + 1. Define Y X,I(D, S t 1- s); the player then observes the collection (1s.s))
Our problem setting aligns with the classic delayed feedback formulation with binary observations (Vernade et al. 2017 2020): the player observes zero value for delayed responses until they become available. However, as we mention in Section [ different from other types of bandits, the dueling bandit is intrinsically more difficult with delayed rewards due to its feedback mechanism that involves two arms at once: on the one hand, when Y.,-- = 1, it is straightforward to determine that X, = 1. We say that the reward converted if X, = and the actual observation of this conversion event is indicated by Y., Y Ys = 0, the status of X. (X, 0 or X, = 1) remains uncertain due to the potential delay since we always
On the other hand, if
We note that analysis can be extended scenarios where the delay distribution depends on the pair of arms. This is advantageous because user may hesitate longer when Mij is close 1/2, resulting in longer delays. However, for simplicity and clarity, we assume independence in our work.
4

---

Published in Transactions on Machine Learning Research (08/2024)
observe Ye, 0 when the delayed feedback is not available yet regardless of the pairwise comparison result X. Specifically, the scenarios X, = 0 or D. > --8 8 both would result. in our observation Ys,, = 0, making it impossible to distinguish between these two cases until the delay is resolved. Conclusively, this phenomenon leads to a preference bias on e2 over ut, and this issue is practical under the ducling bandit application as we mention Section | Therefore, our problem is intrinsically more challenging than other lypes of bandits with delayed feedback due the additional bias effects on pairwise comparisons.
Our goal is to minimize the cumulative regret up to time step T, given by
A Av.
R(T)
Σ
(1)
where 4; = Mis 3. This formulation aligns with the standard concept of regret used other studies
(ee--
nade et al. 2017 Pike- Burke et al., 2018 Vernade et al.) 20200.
3
Algorithm: Known Delay Distribution
In this scction, we introduce an algorithm designed for situations where the delay distribution DD is known. Our approach begins with estimating the parameters Pij in the pairwise preference model. Following this, propose RUCB-Delay, rithm (Zoghi et al. 2014a). RUCB-Delay utilizes the upper confidence bound (UCB) methodology computed from the estimated parameters. Finally, we establish a regret bound for our proposed algorithm, demon- strating its effect iveness in addressing the K-armed dueling bandit problem with delayed feedback.
algorithm adapted from the RUCB (Relative Upper Confidence Bound) algo-
3.1 Parameter Estimation
Let 7 IP(D; < t) represent the cumulative distribution function of the delay distribution. Assuming knowledge of the delay distribution, we possess information regarding the individual values of TІ. Addition- ally, we incorporate an M-threshold delay, restricting the observation of conversions to occur within M time steps after the corresponding action. In other words, if the reward conversion has not been observed within the initial M rounds, the algorithm presumes it will never occur. This censored observation setting aligns with the study conducted in Vernade et al. (2017 2020 This assumption has a practical advantage, there is no need to keep track of observations (Y.,) for > s M.
We first introduce some key notations. We utilize the notation I = I((u,, v.) = (i, for simplicity when there is no polential confusion in the context. Define Niş(() as the exact count of times we select a pair of arms (i up to time f, and (ty(t) as the delay-discountedd count, which takes into account the probability of the reward not yet being observed:
(-1 (T. + +1,))
N1,(1) Σ
(2)
t- M
(-1
N,J(1) = Σ TM [T + 1g +
Σ T--
( (1,,)
+
(3)
s=1-M+1
Moreover, for practical benefit, as mentioned earlier, we introduce the censored observation Ys,, which differs from Y., only when the reward X, is one and the delay D, exceeds M:
Y.D,, S M) X, IDD, S min s)).
Lastly, introduce Syy as follows:
t- M
(ty = Σ
You 1i + (TM Yo,e 17 +
Σ
Yov Ui + (Te-e - Yo,)) 15,6
s M+1
5

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm RUCB-Delay
Input: Time horizon T,, a, M, (TalaT A = (1, Initialization:
for t = 1, T do
2: Compute (4)(4) for all i + based on Equation 5
3: (t)(t) + for all i E A
4: Select a pair of arms (u,, v/) according to RUCB
5: Observe the collection (Ye,41))see0..
Update (1 + 1), (ty(t+) + 1), and Si,(t+)
end for
(t) captures the bias-corrected count of arm i beating arm j up time When comparing (i,j) and if the current observation implies j > i, we add т instead of 1. This adjustment accounts for the preference
bias favoring the second arm over the first arm, which enables to construct an unbiased estimator of pij. We define Pıg as follows:
(ty(t) Sty(t)
(4)
(1)(1)
which serves as a conditionally unbiased estimator of Pij when conditioned on the arm selections. Proposition 1. (t)(t) is conditionally unbiased estimator of pij; when conditioning the selections of armss
Proof. If (u,, Us) (i,j),
B(Y,, (u,, Us) [4j7mii(MM.0-d)
Then,
((),, valisase-))
L
Σ MayTas Hi + (TM - MHTTM)
Σ
P Hig + (Tc- 12, (t)),
M+1
where the last equality holds from the definition of (t)(t) and the relation Jéj = P4j- Therefore,
(t)if(t)lfu,
"ellluu.ueeeeeee velsees-11) = Maj-
3.2 Algorithm
Utilizing the estimator and variables defined in Section 3.1 designed for the dueling bandit problem in the presence of delayed foedback. RUCB-Delay is built upon the framework of the RUCB algorithm (Zoghi et al.] 2014a retaining a similar structure but with novel estimators, variables, and an altered upper confidence bound. The modified upper confidence bound given by:
propose algorithm named RUCB-DD Delay
(t) (b)(t) a NN),(()) N3 (t)
where 2 1. Refer to Algorithm D for an outlinc of the RUCB-Delay procedure. With the novel upper confidence bound, we follow RUCB's approach of selecting a pair of arms (ve,v)). At each time step, we define a potential champion set consisting of arms that optimistically win against all other arms, meaning U.j 2 for all j. We then update the current best arm B, which will either have one element or be empty. The idea twofold: first, the arm in B loses its top position as the best arm is optimistically beaten by another arm, and second, the arm is will be selected from B with high probability, or from the potential

---

Published in Transactions on Machine Learning Research (08/2024)
champion set C. Specifically, if C contains exactly element, set B to C and select that unique element as U4- If C has multiple elements, we choose from B with a probability of 0.5 and from the remaining potential champion arms in C. B with equal probability. After selecting the first arm ue, the second arm is chosen as the one that maximizes Una.
3.3 Regret Analysis
Here, we present a regret analysis for the proposed RUCB-Delay algorithm. This is achieved by first es- tablishing a general deviation inequality between Pij and fkg in Lemma 2 and utilizing to prove the high probability bound Lemma 3
Lemma 2. For any a > 0 and any pair of arms (1,j), the following inequality holds for all t,
2 [2a
where riz(t) = aN (t)
(N)
P (1)) pusl Ta (t)(t)
(1
The proof of Lemma is provided in Appendix A.1 With the upper confidence bound Uz defined in
Equation for i * and Un 2 for all i, we define Liy(t) =1-U,a(t) We now state the high probability concentration inequality:
Lemma 3. Let 1/2 and 8 >> 0. Then, with probability at least 1 8, for any t C(6) and any pair of arms (i, the following holds:
Li((t) S Pij S Un((),
where C(δ) = ((daa-1(22 (4o-D(M-IK(K-I) I
(2a-1)6
The lemma establishes high probability inequality that involves all large time steps and pairs of arms. By leveraging symmetry, our analysis can be confined to cases where i < j. Additionally, if arms and j are compared at time 81, then at time $2, Nij and Ng remain constant for all time steps between 81 + M and s2- This observation narrows down the range of time steps that need to be considered. Given these observations and Lemma 2 we present a comprehensive proof of Lemma in Appendix A.1
Given the high probability upper and lower bounds of jaj from Lemma we derive the following high probability upper bound on the regret for the RUCB-Delay algorithm and state the expected regret bound.
Theorem 1. Let a 2 1 and 5 > O. For any T 2 1, with probability at least 5, the cumuulative regret R(T) of AUCB-Delay is upper bounded by
MK
+ +
log
Ain A?)
A
Theorem 2. For a 2 1, the expected regret [(((T))) of Delay is upper bounded by
o OMK3)+ +
+0
log
t min (A? AA A3)
2 A
The components of the expected regret upper bound in Theorem 2 share a similar structure with the regret bounds obtained in a fully stochastic setting (Zoghi et al., 2014 but with an additional multiplicative constant 1/7?. We may easily verify that the absence of delay, when T₁ 1, our algorithm RUCB-Delay recovers the optimal regret bound in the standard stochastic ducling bandit problem (Zoghi et al. 2014a, Komiyama et al. 2015).
The detailed proofs for Theorems 1 and 2 are available in Appendix A.2
Remark We have developed an algorithm opplicable the delayed feedback setting in the dueling bandit problem by introducing a series of new variables and modifying the upper confidence bound when the delay distribution is knoun. We anticipate that many bandit. algorithms using the Upper Confidence Bound (UCB)
7

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm 2 Multi Round- Robin Ducling Bandit with Delayed Feedback (MRR-DB-Delay)
Input: Time horizon T, {m JMEN
Initialization: "n = 7.t = 1, m = 1, = (.,,,
(0) = Ø for all i.j E A1
1: while T do /+ Round starts */
3: for i,j E Am do
4:
Let [iş(m) := T= (m - 1)
while [Ti{(m)] S nm and S do
Play arms and j
(m) < (m) (1) 2
end while
10:
end for
11:
* Update mean estimates and active arm set +/
12:
for i,j E Am do
13:
Yiy(m) = [Ts(m)) EOET,(m) Ys,
14:
end for
15: Am+1 = Am \ of Am 3j E Am stt. (m) + +m < }
16:
7m+1 6 Im
17:
m
18:
end while
strategy can transition to scenarios with delayed feedback by employing novel variations similar to our upper bound.
For instance, the RR-DB algorithm (Saha & Gaillard 2022) designed for stochastic dueling bondits can be transformed in similar manner. RR-DB is struightforward methodology that, in each round, compares all pairs of potentially optimal arms in round-robe fashion, gradually removing significantly suboptimal arms. Although RR-DB achieves a regret bound of O(K² log T) and is not optimal overall, it performs optimally concerning the order of Amin. In contrast to other dueling bandit algorithms (Zoghi et al. 2014aa Bengs el ol. 2021) suffering from a regrel of order Ami. RR-DB relies only on Amin- which leads to an improved worst-case regret. We adjust the upper bound usy of the RR-DB algorithm from
log(Kt/5)
= : +
(ts
N1,(1) log (og))))()/)))) (1)
= (o)(1)
where Pij is defined as Equation Then, the algorithm becomes suitable for the delayed feedback setting. We refer to this as RR-DB DB-Delag Since RR-DD BB is not optimal, we do not delve into in detail in this paper. However, we will evaluate and compare the performance of R.R. FE--DBDDeloe in the ezperimental section (Section 5) later
Remark 2. We can formulate a non- non- asymptotic lower bound for the dueling bandit problem with stochastic delayed feedback. For any dueling bandit algorithm and T, there erists Koarmed dueling bandit such that R(T)) 2 c/TK/TM where e is constant. The proof for this is deferred Appendir D while it remains open problem whether this lower bound is tight.
8

---

Published in Transactions on Machine Learning Research (08/2024)
4 Algorithm: Known and Bounded Expected Delay
In practice, the exact delay distribution D is often unknown and can be challenging to estimate. This section presents a novel algorithm named Multi Round- Dueling bandit with Delayed Feedback (MRR-DB- Delay) that can be implemented when only the expected value of the delay is known and bounded.
4.1 Algorithm
MRR-DB-Delay employs round-based climination strategy that iteratively refines the set of active arms. In each round, all possible pairs of active arms are played multiple times, and based the accumulated observations, suboptimal arms are eliminated at the end of the round.
Algorithm 2 provides a detailed overview of our algorithm, MRR-DB-Delay. In this algorithm, m denotes the current round, while represents the current time step, with T being the total time steps until the algorithm concludes. Additionally, nm represents the number of times each active arm pair should be played by round m. In the collection (m), we store all time steps when arm pair (i,j) were played in the first rounds. The set A. identifies the active arms during round m, indicating the subset of arms currently under consideration.
In round m, each pair of arms (i,j), where j E Ams is played nm - 1m-- times. Then, we compute the mean estimates (m)) of arm pairs based on the observations at that point. Finally, arm i is eliminated if there exists another arm j in Am such that the mean estimate (m) is less than 1 by 7m- The gap tolerance I'm decreases exponentially over rounds, and in our further analysis (Lemma 4. we establish an inequality between the difference of (m) and jij. These provide a guarantee that, with high probability, all arms, except. the best arm 1, will be removed.
Lastly, in cach round, we need to determine the value of nm indicating how many times we will play cach pair of arms. The determination of nm is crucial as it plays significant role in the algorithm's 's ability to efficiently eliminate suboptimal arms and has a substantial impact on regret performance. We choose nmm so that the confidence bound established in Lemma | holds with high probability. This naturally results in the algorithm effectively removing arms with suboptimal performance. The sclection of nmm Algorithm 4 is follows:
C1 log(T
C2 B[VEDDlog(TTT
C3E(D) 7/m
fm
(6)
Ym
where C1 and C2 are some constants, and B[D] represents the expected value of the delay. The complete formula for Nem and further details on the derivation of nm are provided in Appendix B.1
Remark 3. In fact, with different value of nm, MRR-DB-Delay mous delayed feedbuck [Pike-Burke Burke et. al., 2018). In this siluation, the player only observes the reward summation in each round after some delay, without knowing which specific past actions led to this total reward. Detailed analysis on this aspect can be found in Appendir
also manage aggregated and anong-
4.2 Regret Analysis
Here, we conduct regret analysis for MRR-DB-Deed D-Day under the choice of nm in Equation 6 We establish error bound between Piy and Y (m), and subsequently derive the expected regret bound of the algorithm.
Let fm be the time step at the end of round m. The sum of discrepancies between jaj and the observation Ys during comparisons of arms and j can be decomposed as follows:
Σ
(Mig Y Yalln)
Σ ( - + (X, - Ye,em)
SET, (m)
SETiy(m)
The first term represents the difference between the true parameter Py and the outcome X,, capturing the error in the absence of delayed feedback. Since the average of X, an unbiased estimator of pıy. the first term be bounded using concentration inequalities. On the other hand, the second term is nonzero
9

---

Published in Transactions on Machine Learning Research (08/2024)
only when the reward is converted but remains unobserved due to the delay, thereby illustrating the impact of delay on unobserved converted output. This decomposition allows us to separately analyze the effect of preference bias and delay. We establish an upper bound for each term and present the following high probability bound, along with a comprehensive proof given in Appendix [.I]
Lemma 4. For any round m 2 and any pair of active arms (i.j) Am; with probability at least T
2
7m 2
Mij Yi (m) S
We now provide the expected regret bound of MRR-DB-Delay in Theorem 3 for detailed proof.
Please refer to Appendix B.2
Theorem 3. The expected regret E[R(T))) of Algorithm is upper bounded by
K (oog(TA)) K log (ogg(TA))) KKE[D)
Σo
Vog
A;
While its regret bound is larger than that of RUCB-Delay proposed in Section 3 MRR-DB-Delay possesses significant advantage in that it can be utilized even when the complete delay distribution is unknown. Moreover, MRR-DB-Delay is advantageous in terms of the order of Amin, as it only depends on Ami.: whereas RUCB-Delay relies on Ami.
5 Experiments
Following the introduction of our algorithms and theoretical analysis, this section involves comparison of the performance of our proposed algorithms through numerical experiments conducted various synthetic and real-world datasets.
Algorithms. We evaluate the performance of three algorithms introduced in our paper with the baseline: 1. RUCB-Delay (Section 3), 2. RR-DB-Delay (Remark 1 in Section 3. and 3. MRR-DB-Delay (Section 4 RUCB-Delay and RR-DB-Delay are algorithms that necessitate knowledge of the complete delay distribution, whereas FRRR-D--Delar only requires the expected value of the delay. We note that the regret bound, considering only terms related to K and T, for RUCB-Delay is OoK T), while RR-DB-Delay and MRR- DB-Delay have bound of O(?² log T). To the best of our knowledge, there applicable to dueling bandit. problems when there is a delay in leedback. However, we also included baseline comparison using RUCB (Zoghi et al. 2014 to effectively demonstrate the advantages of our proposed delay- specific algorithms. RUCB is an algorithm designed without accounting for dclayed foodback; therefore, we update the output as soon as the delayed feedback received.
other known methods
Experimental Setup. We plot the regret performance of all three algorithms on six distinct datasets, which are described in the following paragraph. For all experiments, set the time horizon to T = 200, 000. However, for datasets where all three algorithms converge earlier than this fixed horizon, we plot the results only up to the earlier convergence time for better visualization. The regret performance for all plots was assessed by averaging the cumulative regret, as defined in Equation [ across 100 runs. Both the average and standard deviation are reported in the plots. Similar to Vernade et al. 2017 2020 we assume that the delay distribution follows a geometric distribution with p 0.01, implying a mean E.. D) = 100. Also, based on our regret analysis in Theorem 2 we set a 1.0 for RUCB-Delay. For the baseline comparison, RUCB uses the number of times arm i beats arm j to establish their upper confidence bound, which includes potentially delayed feedback. We employ the most up-to-date values and update this count
as delayed feedback is reccived. Lastly, as discussed in Section 3.1 we introduce a windowing parameter denoted as M for computational efficiency in RUCB-Delay and RR-DB-Delay. When dealing with an unbounded delay, we encounter practical storage issues since we need to keep track of previous actions to update Ni and Sty. The windowing framework allows us to address this with an array of size M. We set the windowing parameter M 1000. Given that T1000 0.999 with the geometric delay distribution, introducing the windowing parameter in this experiment is expected to have practically impact regret performance.
10

---

Published in Transactions on Machine Learning Research (08/2024)
3300
1600
3000
1400
1750
2300
Cumuuative Rogret
1200
1000
1250
800
Cumulative
1000
400
500
500
19-08-Dri
00.00 Daly
18.00 19.08-D01 Dddada
1833-28 Dolay
1811-05-00 Oclay
1011.0 Oday
20000
40000
60000
80000
10000
20000
30000
40000
10000
20000
30000
40000
Time
Time
Time
Six Rankers
(b) MSLR
(c) Tennis
7003
3500
6000
5000
Cumulttvv Regrot
Cumutatvve hoaret
4000
3000
4000
2000
RiCh
3000
RUCD Deliy Datay
RJCB Deley Delay
RDCD Delyy
Dely
50000
50000
90000
150000
(d) Arithmetic
(e) Car Preference
(f) Sushi
Figure 2: Average Cumulative Regret. The regret performances, averaged over 100 independent runs, along with their standard deviations, are reported for cach dataset and algorithm.
Datasets. We perform experiments using the following six datasets. We provide a brief description of each dataset, including the number of arms:
Six rankers (K 6): preference matrix generated from the six retrieval functions within the full-text search engine of ArXiv.org Yue & Joachims 2011
MSLR (K = 5): a 5 x 5 preference matrix introduced by Zoghi et al. (015a) is extracted from a subset of rankers originating from the Microsoft Learning to Rank (MSLR) dataset (Qin & Liu 2013). The MSLR dataset includes relevant information between queries and URLs, comprising more than 30,000 queries.
Tennis (K = 8): a dataset, constructed by Ramamohan al. (2016). based on the results of tennis matches organized by the Association of Tennis Professionals (ATP) among 8 international tennis players. The element (i,j) represents the proportion of times player has defeated player j.
Arithmetic (K 10): synthetic preference matrix with ten arms where Pa 0.5 0.025(j i).
A similar data was first used in (Komiyama al. 2015).
Car Preference (K = 10): dataset of car preferences [Abbasnejad et al. 2013 collected from 60 users in the United States. The preference matrix was constructed based on the pairwise comparison data of users evaluating 10 different cars. Each user expressed their preferences for all 45 pairs of cars.
Sushi (K 16): a dataset derived from the sushi preference dataset Kamishima the preferences 5,000 Japanese users for 100 different types of sushi. Komiyama al. 2015 2016) selected 16 sushi types from the dataset and represented them in a preference matrix.
2003 comprising
11

---

Published in Transactions on Machine Learning Research (08/2024)
Results. The regret evaluations of the three algorithms for all datasets are presented in Figure Across all datasets except for Tennis, RUCR-Delay outperforms RR-DB-Delay and MRR-DB-Delay, providing em- pirical support for their respective regret bound guarantees. Additionally, upon comparing the average performance of RR-DB-Delay and MRR-DB-Delay, we observe a slight superiority of RR-DB-Delay. How- ever, it is essential to highlight. that MRR-DB-Delay holds a notable advantage as it can be implemented with only the knowledge of the expected value of delay, unlike RUCB-Delay and RR-DR-Delay, which require complete delay distribution. Another critical aspect to highlight is the baseline comparison: The baseline method, RUCB, becomes futile and fails to converge across all datasets. This observation distinctly high- lights the superiority of our approaches, specifically tailored for settings with delayed rewards. Notably, the innovative estimator introduced in RUCB-Delay significantly enhances the algorithm's effectiveness and robustness to delayed observations.
When examining the performance of RUCB-Delay, it can be observed that the regret increases more slowly the carly stages compared to RR-DB-Delay and MRR-DB-Delay This fact is aligned with our expectation since both RR-DB-Delay and MRR-DB-Delay initially attempt all possible arm pairs before eliminating suboptimal arms, leading to rapid increase in regret at the beginning. Additionally, for datasets with many arms having small A,, these arms tend to be climinated later. As a result, comparably large differences in regret performance may arise between HUCB-Delay and both RR-DB-Delay and MRR-DB-Delay.
6 Discussion
We have studied the biased dueling bandit problem with stochastic delayed feedback and introduced two main algorithms, each accompanied by a comprehensive analysis. The first algorithm, RUCB-Delas is designed for scenarios where the complete delay distribution is available. It leverages parameter estimation of the underlying model and incorporates a UCB strategy. This algorithm recovers the optimal regret bound for the dueling bandit problem in the absence of delay. The second algorithm, MRR-DB-Delay, is crafted for situations where information about the distribution is unavailable, and only the expected values are known. It employs a robi-rinun fashion by playing all active arm pairs a predetermined number of times in each round. To the best of our knowledge, our methods are the first to delve into the delayed feedback setting within the ducling bandit framework. The efficiency of our proposed algorithms then validatod under numerical experiments.
There several potential directions for future research. To begin with, it is intriguing to investigate algorithms that can be implemented without any knowledge of the delay, such as its expected value, while this problem remains challenging since existing algorithms for the simpler multi-armed bandit, with delayed feedback still require additional side information. Furthermore, conducting theoretical studies to understand the impact of employing estimates of the delay distribution could be insightful. While our study assumed Condorcet winner, it would be beneficial to extend the problem to consider Borda or Copeland winners. Last but not least,, the biased dueling bandit presents a compelling area of study due to the pervasive nature of biases confounding user preferences in real-world applications. Despite its practical significance, this challenge remains largely underexplored in the existing literature.
Acknowledgments
We thank the anonymous reviewers and the Action Editor for their constructive feedback, which helped improve this work. This work was supported in part by the National Science Foundation under grants DMM-2152289, DMS-2134107, and Cisco Faculty Award.
References
Ehsan Abbasnojad, Scott Sanner, Edwin V Bonilla, and Pascal Poupart. Learning community-basie prefer- ences via dirichlet process mixtures of gaussian processes. In Twenly- third international joinl conference on artificial intelligence, 2013.
Arpit Agarwal, Shivani Agarwal, and Prathamesh Patil. Stochastic dueling bandits with adversarial corrup- tion. In Algorithmic Learning Theory, pp. 217-248. PMLR, 2021.
12

---

Published in Transactions on Machine Learning Research (08/2024)
Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In Inter- national Conference on Machine Learning, pp. 856-864. PMLR, 2014.
Peter Auer, Nicolo Cesa-Bianche Bianchi,, and Paul Fischer. Finile-lime analysis of the multiarmed bandit problem. Machine learning, 47:235 256, 2002.
Akshay Balsubramani, Zohar Karnin, Robert E Schapire, and Masrour Zoghi. Instance-dependent regret bounds for ducling bandits. In Conference on Learning Theory, pp. 336-360. PMLR, 2016.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Panl, and Eyke Hüllermeier. Preferenco-based online learning with dueling bandits: A survey. The Journal of Machine Learning Research, 22(1):278 385, 2021.
Ilai Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, and Jose Blanchet. Online exp3 learning in adversarial bandits with delayed feedback. Advances in newral information processing systems, 32, 2019.
Nicol'o Cesa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora. Delay and cooperation in nonstochastic bandits. In Conference on Learning Theory, pp. 605 622.. PMLR, 2016.
Olivier Chapelle. Modeling delayed feedback display advertising. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1097-1105, 2014.
Bangrui Chen and Peter T Frazier. Dueling bandits with weak regret. In International Conference on Machine Learning, pp. 731 739. PMLR, 2017.
Shein-Chung Chow and Mark Chang. Adaptive design methods in clinical trials. Chapman and Hall/CRC 2006.
Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Conference on Learning Theory, pp. 563-587, 587. PMLR, 2015.
David A Freedman. On tail probabilities for martingales. The Annals of Probability, pp. 100-118, 1975.
Manegueu Anne Gacl, Claire Vernade, Alexandra Carpentier, and Michal Valko. Stochastic bandits with arm-dependent delays. In International Conference Machine Learning, pp. 3348-3356. PMLR, 2020.
Pratik Gajane, Tanguy Urvoy, and Fabrice Clérot. A relative exponential weighing algorithm for adversarial utility-based dueling bandits. In International Conference on Machine Learning, pp. 218 227. PMLR, 2015.
Aditya Grover, Todor Markov, Peter Attia, Norman Jin, Nicolas Perkins, Bryan Cheong, Michael Chen, Zi Yang, Stephen Harris, William Chueh, et al. Best arm identification in multi-armed bandits with delayed feedback. Tn International Conference on Artificial Intelligence and Statistics, pp. 333-842. PMLR, 2018.
Björn Haddenhorst, Viktor Bengs, Jasmin Brandt, and Eyke Hüllermeier. Testification of condorcet winners in dueling bandits. In Uncertainty in Artificial Intelligence, pp.
PMLR, 2021.
Benjamin Howson, Ciara Burke,urke, and Sarah Filippi. Delayed feedback in generalised linear bandits revisited. In International Conference on Artificial Intelligence and Statistics, pp. 6095 6119. PMLR, 2023.
Kevin Jamieson, Sumeet Katariya, Atul Deshpande, and Robert Nowak. Sparse Ducling Bandits. In Pro- ceedings of the Eighteenth International Conference on Artificial Intelligence and Stalistics, pp. 416-424.
PMLR, 2015.
Tiancheng Jin, Tal Lancewicki, Haipeng Luo, Yishay Mansour, and Aviv Rosenberg. Near-optimal regret for adversarial mdp with delayed bandit feedback. Advances in Neural Information Processing Systems. 35:33469- -34489, 2022.
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In Interna- tional Conference on Machine Learning, pp. 1453 1461. PMLR, 2013.
13

---

Published in Transactions on Machine Learning Research (08/2024)
Toshihiro Kamishima. Nantonac collaborative filtering: recommendation based on order responses. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 583 588, 2003.
Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference on learning theory, pp. 1141-1154. PMLR, 2015.
Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Copeland dueling bandit problem: Regret lower bound, optimal algorithm, and computationally efficient algorithm. In International Conference on Ma- chine Learning, pp. 1235-1244. PMLR, 2016.
Tal Lancewicki, Shahar Segal, Tomer Koren, and Yishay Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, pp. 19699-9788 PMT.R, 2021.
Tal Lancewicki, Aviv Rosenberg, and Yishay Mansour. Learning adversarial markov decision processes with delayed feedback. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7):7281-7289, 2022.
Saeed Masoudian, Julian Zimmert, and Yevgeny Seldin. best--of-both-worldds algorithm for bandits with delayed feedback. Advances in Neural Information Processing Systems, 35:11752 11762, 2022.
Ciara Pike-Burke, Shipra Agrawal, Csaba Szepesvari, and Steffen Grunewalder. Bandits with delayed, ag- gregated anonymous feedback. In International Conference on Machine Learning, pp. 4105-4113. PMLR, 2018.
Tao Qin and Tie- Yan Liu. Introducing LETOR 4.0 datasets. CoRR, abs/1306.2597, 2013.
URL http:
7arxiv orrg/ivorr//io wwwp:/ggg//b/////eeee 2597
Filip Radlinski, Madhu Kurup, and Thorsten Joachims. How does clickthrough data reflect retrioval quality? Proceedings of the 17th ACM conference on Information and knowledge management, pp. 43 52, 2008.
Siddartha Y Ramamohan, Arun Rajkumar, and Shivani Agarwal. Dueling bandits: Beyond condorcet winners to general tournament solutions. Advances in Newral Information Processing Systems, 29, 2016.
Aadirupa Saha and Pierre Gaillard. Versatile ducling bandits: Best-of-both world analyses for learning from relative preferences. In International Conference Machine Learning, pp. 19011 19026. PMLR, 2022.
Aadirupa Saha, Tomer Koren, and Yishay Mansour. Adversarial dueling bandits. In International Conference on Machine Learning, pp. 9235 9244. PMLR, 2021.
Tobias Sommer Thine, Nicolò Cesa-Bianchi, and Yevgeny Seldin. Nonstochastic multiarmed bandits with unrestricted delays. Advances Neural Information Processing Systems, 32, 2019.
Tanguy Urvoy, Fabrice Clerot, Raphael Féraud, and Sami Naamanc. Generic exploration and k-armed voting bandits. In International Conference on Machine Learning, pp. 91 99. PMLR, 2013.
Sattar Vakili, Danyal Ahmed, Alberto Bernacchia, and Ciara In International Conference on Machine Learning, pp. 34779 34792. PMLR, 2023.
Delayed feedback in kernel bandits.
Claire Vernade, Olivier Cappé, and Vianney Perchet. Stochastic bandit models for delayed conversions. In Conference on Uncertainty in Artificial Intelligence, 2017.
Claire Vernade, Alexandra Carpentier, Tor Lattimore, Giovanni Zappella, Beyza Ermis, and Michael Brueck- ner. Linear bandits with stochastic delayed feedback. In International Conference on Machine Learning, pp. 9712-9721. PMLR, 2020.
Yuya Yoshikawa and Yusaku Imai. A nonparametric delayed feedback model for conversion rate prediction. arXiv preprint or Xie: 1822.8822000 00255, 2018.
14

---

Published in Transactions on Machine Learning Research (08/2024)
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems dueling bandits problem. In Proceedings of the 26th Annuul International Conference on Machine Learning, pp- 1201-12 1208, 2009.
Yisong Yue and Thorsten Joachims. Beat the mean bandit. In Proceedings of the 28th international conference machine learning (ICML-11), pp. 241-248, 2011.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. In Proceedings of the 22nd Conference on Learning Theory, 2009.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Compuler and System Sciences, 78(5):1538 155611656616 2012.
Zhengyuan Zhou, Renyuan Xu, and Jose Blanchet. Learning in generalized linear contextual bandits with stochastic delays. Advunces in Neural Information Processing Systems, 32, 2019.
Julian Zimmert and Yevgeny Seldin. optimal algorithm for adversarial bandits with arbitrary delays. In International Conference on Artificial Intelligence and Statistics, pp. 3285 3294 PMLR, 2020.
Masrour Zoghi, Shimon Whiteson, Rémi Mumos, and M. de Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. ArXiv, abs/1312.3393, 2013.
Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten Rijke. Relative upper confidence bound for the k-armed ducling bandit problem. In International conference on machine learning, pp. 10-18. PMLR, 2014a.
Masrour Zoghi, Shimon A Whiteson, Maarten De Rijke, and Remi Munos. Relative confidence sampling for efficient on-line ranker evaluation. In Proceedings of the 7th ACM international conference Web search and data mining, pp. 73 82, 2014b.
Masrour Zoghi, Zohar S Karnin, Shimon Whiteson, and Maarten De Rijke. Copeland dueling bandits. Advances in neural information processing systems, 28, 2015a.
Masrour Zoghi, Shimon Whiteson, and Maarten de Rijke. Mergerucb: A method for large-scale online ranker evaluation. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, pp. 17-26, 2015b.
15

---

Published in Transactions on Machine Learning Research (08/2024)
A Regret Analysis of RUCB-Delay
A.1 Proof of Lemmas 2 and 3
Lemma 2. For any > 0 and any pair of arms (1,j), the following inequality holds for all t,
2 [2a
aNy (t) logt
P ((())(()) pijl (t)(t)
where riş(!)
(1
Proof. Let
: =
y
s,t i. + -Y,,)
s=1
Then, we obtain the relation
1-1
S,y(1) - 2 +
Σ
(mmin(M, 1)11...
Let's first consider the case conditioning on the selection of arms {u,, Uslises-- Then, we have
1-1
Sty(t) - Σ 1 Miy (, E(Z).
Therefore, we can set an upper bound for the left-hand side conditioned on the selection of arms as:
2
P (()ii)(() اجيl > ray(()) (u,, Us w.hisse-r)> = P( B(Z)] (1y(t) (u,, 0s whsssee))) S f2a
The incquality holds by Hoeffding's Incquality since each censored observation V,, is independent given the selection of arms.
Finally, since the right- right-hand side term of the above inequality does not depend on the selection of arms, we may remove the conditioning by the law of total probability and obtain:
IP ((Arg] Misl > ri)(t)) S
12a
Lemma 3. Let > and 8 > 0. arms (i, the following holds:
Then, with probobility at least 1 - 8, for any 1 >> C(8) and any pair of
Li(()) S my S Us)(),
where C(5) = -0100-1100111100 (#0-I)(M-IK((-I) -0-7 120-116
Proof. Let (t) denote the good event where we have Mag [L (t), Ut), at time and let (t) be the bad event where Pij & [Li (f), (t)(t) at time f.
For < j, the relations Pi = - Hja, Uiz(() = =1 -1;;(0,,, and Lig(() = 1 - Uza(() hold. Thus, the event (t) true if and only (t) true. Additionally, (t(() is always true because, as constructed, Pu = (t((t) (xx(t) = 1. Hence, is sufficient to focus only on (t)(t) for j.
We define of the time step when arms i and j were compared for the n-th time. We note that Niy(o n
by definition. For any n, if o + M < oin then
(1) is increasing function of t for all N2
di + M <t< oir Also, (ty(t) is a constant for all a + +M < t < of n+r Therefore, if Giy(a + k) holds true for all 0 < k & M, it implies that (t((t holds for all ot
R+1
16

---

Published in Transactions on Machine Learning Research (08/2024)
Using the above observations, for any T > O, we have
P T, (1)(t)
P Vi < j. G15 (t) for VT St max (N,,,)) + +,
and Gi + k) for An 2 (2) + +10
Next, by considering the complement of the events both sides of the above equation and applying the union bound, arrive at the following:
PEt T, s.t. (t)(t))
Σ icj
(P (3EE
max (0% (N) M,T)] s.t. Bi)(t))
s.t. of + k < tht and Buylo + k)))
-P
NNN log
$ Σ ijj
P
3 E
T. max (,) + +,,T 1oas - (t)(
N2(())
(a)
aNN, k) log(o +k) N3(0 + k))
+ P
3n E (T) 1,T,,, & 10, [0,M]
ot + k < t and
Mis - Aug + >
aNy + log(o + k)
+ P 3n T,K 0, :a:M:]f of k o and |nis - A + +b]l>
N7 + k))
Let's break down the expression on the right-hand side into three components, denoted as (a), (b), and (c), and then derive upper bounds for each of these components. The first part (a) can be upper bounded as:
(N) log N2
(a) S
T. M N2,(t) (T) and Ipy - Aig(t) V
oxNay log N2
SP
71 T, :N,(1) (T) and - ))r(11)>
M T
NN, (T + k) log T
=,, = and |ng - Pag (T ++++
N2 k)
k=
1
2(M +
Too
17

---

Published in Transactions on Machine Learning Research (08/2024)
where the last inequality holds from Lemma 2
Second, (b) can be upper bounded as:
aN. + k: log T
(b) s P
3i (T) +1
T. S A M: of + k o and | (o 1b)l
N3 (o + k))
aNiylo + -kllog??
log T
P
oit + k < o T+1 and |mg مus(o + +k)]
N3 + +k))
k=0n=1
T
$ 2(M
Σ
1
T
The first inequality holds because (T) + S n and o + > T, while the second inequality results from applying the union bound. The last incquality holds again from Lemma [ S of and Lemma 2
Similarly, by using the fact that
we can obtain an upper bound for (c) as follows:
aNi + logo
(c) P
3n T, S.SSSSSSMM
02 + < o and Imn - Pey(o + +k)]
N2 + k))
M
aNy(o + k)) log
P
o + n+1 and |mss - L + k))
No + +1)
k= n=T++
22(M 1)
20
T+1
Putting all these results together, we obtain
((t T,i,j s.t. (t))
2 + 1)
T2a
naa
n=T+1
= 2(M + +1)K(K 1) 72a-1
+ (M + 1)K((K 1)
Σ 22a
n=T+1
000
dx
< 2(M + 1) 1) T2a-1 + (M + +1K(KKKKK -
20
(M 1) - 1)K(K- 1)
(2a - 1)723-1
Therefore, when T = C(8), we obtain P(3 (13>0(()) i, s.t. B,)()) S 8 which concludes the proof.
A.2 Proof of Theorems and 2
Theorem 1. Let a and 0. For any T 2 1, with probability at least 8, the currulative regrel R(T) of LUCB-Delay is upper bounded by
MK² (M))
+
7 A log T )
8
min A7 A3)
Proof. We first state a high probability bound for the number of comparisons for each arm.
With probability at least - 5, for any t > C(8) and any pair of arms (i,j) * (1, the following holds:
N1y(1) < 4a logt
(7)
77 min minn A3)
18

---

Published in Transactions on Machine Learning Research (08/2024)
Moreover, let (t) denote the number of comparisons between arms i and performed between time C(6) and L. Then,
4a logt
(1)(1) rf min(m, A3)
holds as well. The proof this statement closely follows the analysis presented in Proposition 2 of Zoghi et al. (2014),, with modification Equation (3) Zoghi et al. (2014a) as follows:
< (s) (s)
algs
aogt
Usy(s) (8)(s) = V2
2
NiNis(s) /
NiNis(() I min (A;,
Now, let T3 be the smallest time that such that
f: > C
+ D log To.
where D := + Eiej Ai)(A and the existence of such Л3 guaranteed. Then, according the above statement and Lemma we can assert with a probability of 1 that
0 (
1.j. My E U,) V C
and
4a log To Ti min A A3)
8/2 (fs) v(i.)) + (1,1), Ni
In this case, when > C (3) and i 1, arm cannot be compared against itself. This due to the fact that (t)(t) Mni (n)(t) which holds by Lemma 3 Additionally, we have
( is ( (2-c(2)) Σ N 2/2
(Ta) 2 Ts -g-Ol (-)(2))
1 - +
Σ
4ax log Ts
> 0
min , A3)
by the definition of Tg. Therefore, this implies that there exists a time T3 E (C To when arm 1 was played against itself. At that time To, we had un < 3 for all j> 1, indicating that B = (1).
With the above insights, we follow the proof strategy outlined Theorem 4 of Zoghi et al. 2014a Equation in Zoghi al. (2014a) requires modification, taking the form:
K
4a log T (T)
(I(T) S Σ N
A
#=2
Furthermore, we can upper bound the cumulative regret similar to Equation 8 in Zoghi et al. (0014a] as follows:
K 4aA1, log T
N.
R(T) < T3A MAX
Σ m
(9)
While the notations for and D have undergone modifications compared Zoghi al. (2014a). we may verify that all subsequent stalements remain valid, and we able to upper bound each term in Equation g as follows:
N (T)
2a log T
R(T) S TAA max
Σ
Σ
ni A1amax
7iA;
5=2
K
K
2a log T
2
8o
< 2C
+ 2D log log2D)
A Amax
Σ
4A max log
+
max log T
7A
T
A
3=2
J=2
which concludes the proof.
19

---

M+1- However, for simplicity, we Published in Transactions on Machine Learning Research (08/2024)
Theorem 2. For 2 1, the expected regret [[R( of RUCB-DeCL Deloy is upper bounded by
(MK3) +0
a mini A A3)
+0
log T
Proof. Let
Hr(1-8) 20 ( 2D log 2D
2x log T
2
K 8a
A Amax
Σ
+ 4 max log
max log T.
.
For fixed T, we view R(T) as a random variable. By the relationship between the expected value of a random variable and its cumulative distribution function, we obtain:
ER(()) - S ( S. HL
Then, for integration of Hr, we only need to foucs on lerms that depend on 6:
E[R(T)) < S Hr(g)dg
= S/' [/(cc (1-9)
(2c
K
2a log
2
K
8a
+ 2D log 2D
Amax +
+
+ 44 log
+
>
Amax log Tdq
2
TiA,
1-
T
j=2
j=2
2x log T
A max log + A Amax /
1
11-8 9
= 2D log 2DA max
max
+
20
+
4logg
dq.
A
A
2
1-g q_
f=2
j=2
Moreover, the above integral can be computed as:
1/' 20 20 + log
1 4
2(4a
1)(M + ()K(K-KKI))
20
20
1 1-q. q dg
+ 4(log
2a 1
Q-1
2(4a 1)( + 1)K(K - 1)
20-1
2a 1
+
2a
2
Therefore, the expected regret can be upper bounded by
E(R(T)) & 8 2( 1)(M + +1)K(( - -1)
20-1 2a 1
2a
K 20(A; + 444mmax)
+2D log 2DA +
log T.
7/13
Remark 4. In studies focusing on delayed feedback [Vernade el al. 2017 2020), certain analyses include
Tm in the regret bound instead of TI. We note that in Theorem and can be replaced with IMr. This substitution is justified by the following inequality. If Nis(t MJ 2 1, then
M41-
No(1) M
(1)
No 2 M+1 M + 1+1N N M)
Nij(t M).
M
+ MM+1" TM
M +1
TM
M (t)
The condition Nty(t M) 2 1 is satisfied when all pairs of arms are initially selected before the beginning of the algorithm. Therefore, further analysis, Ti can be substituted with TM mainlain the of in subsequent analysis.
20

---

Published in Transactions on Machine Learning Research (08/2024)
B Regret Analysis of MRR-DB-Deke Delay
B.1 Proof of Lemma 4
Lemma 4. For any round m 2 and any pair of active arms (i,1) Ams with probability least T-p
Paj Y.s(m) S 7m 2
Proof. Let bm denote the time step when round m concludes, and define P. = X,T(D, > Im - E (i)(m)) Additionally, denote Ge as the o-algebra generated by actions, outcomes, delays, and observations up to time step We will start by proving two lemmas.
Lemma 5. With probability greater than 1 - TT2
(mig Xx) < (
(m)
Proof.
Applying Hoeffding's inequality and Lemma 19 from Pike-Burke et al.
2018 we obtain the inequal-
ity:
-21
P
Σ
(mi Xx) 2 d
S exp
7lm
sET, (m)
Then, choosing À (n
completes the proof.
Lemma 6. Let Qi -==- 21= (Ps E(Ps.gg-1)). With probability at least 1
The
2 Qtm S log 2 + log
3
Proof. (Qr) a martingale with respect to the filtration {- with increments Qi - Qi-1 = P. E(P,(9r-1). Also, we have
E(. = Σ Var(Ps S Σ B(P? 1m -) -
Then by Freedman's version Bernstein's inequality (Theorem 1.6 Freedman 1975 we obtain the following inoquality:
X²/2 D + A/3
P(Q... 2 A) S exp
Finally, pick A 1
log (T
+ +EE (T))) and since
3
Log(TT2)
log 2 (Th2) 2
+ 2EE[D] (T < 3
+ //2[ log(T?2)
3
9
this concludes the proof.
21

---

Published in Transactions on Machine Learning Research (08/2024)
Now, employ the following decomposition:
Σ
(ps - Ye(m))
Σ
(my- X,) + (X, (eeem)
sETi (m)
TET,, (m)
(pi- - X,) + Qtm + fm
Σ (ETi)(m)
Both the first. and second terms be bounded with high probability using Lemma 5 and 6 respectively. The last term can be bounded as follows:
bm
E(P.GG--) S moy
Σ
P(D, hm 8) S E[D]
Therefore, with a probability greater than 1
2 Thm
the following holds:
2E D
D[D] 7lm
[ig (m)
Σ
(uig - (att)) S (m) +
v (T'2.)
(10)
Thm
3mmm
2m
Thm
(m)
Defining 7mm
27
log (m))
log (T (m))
+
+ mm log(T>>h) + 2mm 2E|D) log + 27/m P/mB
mm
2
2
3
ensures that the right-hand side of Equation
10 is less than or equal to Tou 2
concluding the proof.
B.2 Proof of Theorem 3
Theorem 3. The expected regret B(R(T)) of Algorithm
is upper bounded by
K
K Klog((A?))
A + K (og( + KE(D)
Proof. We follow the proof structure presented in the proof of Theorem 2 of Pike-Burke et al. (0188 For any arm i, let Mj denote the round when arm is eliminated. Additionally, for any arm i, let's define
7m < 3 2/4.
m, = min m 2 1: 7m
Then by the definition of my we have
mmm
A
3
Furthermore, we introduce Ny as the number of comparisons between arms and j up time T, and N the total number of times arm has been played by time T::
No :N) Σ I((u,, vz) (i.j)) I((u,, vz) (i.
T
N₂ = Σ
I(u = i) + +1v = i)
T=1
22

---

Published in Transactions on Machine Learning Research (08/2024)
Also, for any arm let R₂(T) N₁ 2..
Then the cumulative regret can be expressed as
K
R(T)
Σ
No
Σ R((T).
2
i
Therefore, we decompose the expected regret as follows:
K
[T)( = E
(T)
K
E
R. (T) 2 m.)
+E
Σ
R. (T) < <m)
(a)
To bound each component, we prove the following two lemmas.
Lemma 7. For any arm i # 1,
2
P(M my and M1 2 m,) S
T
Proof. Define event
A = (mss) S pal + Yim
2
which occurs with high probability, specifically at least 1
Thp by Lemma 4 If the event happens,
(m(m)) 141
7mm
1
A
+
Ymm
2
2
1
3
7m,
1
7m;
2 7m,
2
2
2
Therefore, if M1 2 my we have M, S m,, This implies that if M, >> my and M1 2 mi. the event A does not occur. Hence, we obtain
2
P(M, and Mi 2 m.) < IPAAntiE Am;)) S
T-2
Lemma 8. Let the event Fe(m) be the event that the optåmal arm 1 is eliminated by arm i in round m. Then, for any orm i,
((F((m)) I Tr2
Proof. By the condition that an arm is eliminated,
((F(())) P i, E Am and F1e(m) + 7m < (/2
Define event
A (Vi((m) > Mii
Ym 2
If A occurs,
Yie(m) M4:
7m
1
7m 1
7
2
2
which implies will not be removed by i in round Therefore, by Lemma 4 obtain
2
P(F((m)) s IPA ni Am))
T-2
23

---

Published in Transactions on Machine Learning Research (08/2024)
Bounding Term (a).
By Lemma 7
we can bound the first term as follows:
( ma)
E
K
K
TA
E
(T),()) & <m;]]+
+
E
(M, > m. Mi 2 m.)
2
K
T
24;
K
+
2
2
mm
1=1
K
A
K
9
9
A. K
1mm
K
2
A
A
2
1=1
Bounding Term (b).
Let maax
max my By Lemma
and
K
R. (T) < ma)
E
Memaxe
I(M1 m) Σ NA
2
i.m Smz
mmax
T(M1 = m)T
max
A
s:m, Pm
m==
M2ax
K
Σ 3P(M = mm Σ
3P(F((m)) Tm
m
1=1
Σ
Σ
3P(M 2 mi, Mr > ms) + Σ
3P(F:(m))TTi
m=1
Em <m
k.m, 2m
Mmax
Σ
Tm
Tym
Th
2
Th
==1
iim <m
i:, mm
K
K
2 m
7mu
2-m
T7 172,
1=1 m=1
36
+
12. 2
A
K
K
K
36
A
A
A
i=1
where the last two incqualities hold from 2
7m, < A.
Therefore, we have provided upper bound for terms (a) and (b), and the expected regret is overall upper bounded by:
K
A Anm, K
BR((T) <
Σ
+
A
2
i=1
24

---

Published in Transactions on Machine Learning Research (08/2024)
Lastly, choice of Am, can be bounded follows:
27
log(TT))
Th?
im:
log Tmm
+ Ym, log(TTmm) 2mmm V 2E D) log log(TTmm)
+ 2ym. E[D]
Ymm
2
2
1
2log mm)
+ mm, log(1 (T
+ 4ym,
2E|D] (T
+ 4mm B[D]
7m;
2 log( (4T44/9)
8 8log(4TA2/9
4/2E(D) (og(4TA)/7)
< +
8/m
7/m
Ym
18 log 47 4T (9)
8 log /9)
12 / 2EE[D)
log
47 A
12E D
< 1
A?
A
A
4
Thus, the total expected regret is bounded by
81 9K log log(4TA)//9) + 4K log (og(4T4)//) + 6, / logg) (4T + A;
1 +6K + k
([R(T)
4
C MRR-DB-Delay on delayed, aggregated, and anonymous feedback
In this section, we illustrate the regret guarantee of MRR-DBB-Deee Delay when handling delayed, aggregated, and anonymous feedback the ducling bandit problem. Here we also assume a known and bounded delay as in Section For comprehensive description of the delayed, aggregated, and anonymous feedback setting, please refer to Tike-Burke al. (2018). We conduct regret analysis with the following choice of nmm
1 mm
8 Vlog(TTh2)) + 2 (oog(TT)) 2 + 7m log(T + 67 mi[(T) 6mm
(11)
Lemma 9. Consider the delayed, aggregated, and anonymous feedback setting and the choice of nem given by equation 11 For any round 2 1 and any pair of aclive arms (i.j) E Am, with probubility al least T-z."
3
Pij - (m)(m) S 7m
2
Proof. We omit the proof here since the analysis of Lemma in (Pike-Burke et al. (2018) can be similarly applicd here.
Theorem 10. Under the delayed, aggregated, and anonymous feedback setting and the choice of nm given by equation 11 the expected regret ([)) of Algorithm is upper bounded by
K (lg
1 A
Σ
K log
[E[T]
A
Proof. We follow the organization in the proof of Theorem 3 in Appendix B.2 Similarly, for any arm i, let. M, be the round when arm i is removed and define = min {m 1 Tm < A. Then we know S 7m, < A. Additionally, we use the same notation of Ney, Nr, R(T), and RT(T) as employed in the proof of Theorem 3 in Appendix B.2 We once again break down the expected regret and bound each
25

---

Published in Transactions on Machine Learning Research (08/2024)
element using Lemma 1 and 12
K E
(T)
(T(
K
E
R((T)I(M 2 m²)
+E
R. (T (TM < <m:)
1==1
(a)
Lemma 11. For any orm i + 1,
P(M my and Mi 2 m.)
Tim.
Proof. The proof is identical to that of Lemma] 7 with the only difference being the utilization of the upper bound probability from Lemma g
Lemma 12. Let the event (i(m) be the event that the optimal arm 1 is eliminated by arm i in round m. Then, for any orm i,
((D(()) S T
Proof.
The proof is identical to that of Lemma 8. differing only in the upper bound probability from Lemma !
Bounding Term (a). By Lemma
11 have
K
E
R.(T)(( 2 ma)
TA
E (R, S m;)]
E
m. Mi m.)
2
K
A
T
3A;
nmm
K
2
2
Th2
K
K
K
A
27
A Am K
K
Σ
+
2
2
A
2
A
2
1=1
1=1
26

---

Published in Transactions on Machine Learning Research (08/2024)
Bounding Term (6).
Let maax max1411 my Using Lemma, 11 and 12
obtain
Σ (T) < ma)
E
Whmax
T(M m) Σ NA
2
i:m; 2.12
I(M, = m)T max A
3P mm
Σ
3P(M
mi; M₁.
Tm + Σ
3P(F:(m))TTTm
imm m
maxx
Σ
9
T 7m
9
T
Tim
Thin
2 mi
T
Em,,
Minxx
my
2m
7m
2-m
f=1
K
K
K
K
K
54
54
54
108
18
2
<
A
4
A,
1=1
1=1
1=1
1=1
1=1
where we also employed the relation 2d Consequently, by the upper bound proved for lerms (a) and (b), the expected regret can be upper bounded
3
7m
by:
K Σ
243 A,
E[R(T) S
2 A
2
1=1
and since nm, defined in equation 11 can be bounded as
27
1
8
Tm:
[log(T + y 2 log((Tnmm))
3 mm. log({'>?. + 6%m, B[B
Ymu
16
+ 12 m; ]
x
logg
mm.
+ 3
mmm log(T
2
8 Boog(474) (T /T43//) /9)
16log( 4T /9)
12 10 [3/A,)[[r])
<
Im;
3
Ymm
log 4 /9)
16 log 4TA4 (9)
72 (3/ A [[
< 1
A
A
A
we conclude that the total expected regret is bounded by
E(R(T)) Σ
36K log (4944999)) + 8K log (474477))) + 36K 13/
243
+
1
(K,)
A
A
2
27

---

Published in Transactions on Machine Learning Research (08/2024)
D Lower Bound on the Regret
Proposition 13. For any dueling bandit algorithm and T, there crists a K-armed dueling bondit such that R(T)= 2 TK/T/M, where c > O is conslant.
Proof. The proof of this proposition closely follows the proof of Theorem 3 in Vernadee et al. 2020 Firstly, let's define a parameter μ² k x K For all i > 1, we set M1 = = + A and u41 = 2 A, where 0 < A <
Additionally, for all * 1 and * 1, we define ni = 1/2 Now, let = arg min;>1 E [NV(T)) Since we choose two arms at each time step, using the pigeonhole principle, we find that [N (T)) S K-I' Next,
27
we introduce another parameter n² IR BKXK,, We define p4 1 + A and uh: 1 + 2A for all 2, while for all and f k, mij mky.
Then, by the definition of regret and p², it follows that
Ry (T) 2 TA
E [NI(T)]
2
= TA
> 7)
2
TA
2 TA
2
TA
4t (NT(T) ST).
2
Similarly, we have
TA R (T) 2 B
A
2 (N) [ T))
Then, we use Bretagnolle-HHubr inequality and obtain Rya + (T) 2 IA (F, the relative entropy between PA, and p2 can be expressed follows:
Also,
Σ B (T)
Tm
Tm
24
2
2 A ))
+ R [Nai
Tm
Tm
2
K
E (N)
Tm
1
24 ))
1 Tm
2
2
1=2
2 - )
+ F. [NIR
Tm
+
.m
2
64T
< (N 32Tm
2
Tm A
K
where d(p,g) = plog(?) (²) (1 p) log( ( and the incquality holds by the relation between the relative entropy and x² distance. Therefore,
TA
64T
R (1) + R (T) (T) 4
exp
( K Tm A2)
Finally.by by setting
K-1 128T
we achieve
RyJ (T) + RTp(T) 2 o TKT//T..
which completes the proof.
28


Reviews:
[{"review_id": "YFKv6BXQ6W", "reviewer": "Reviewer_5bEz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#### **Strengths of the paper:**\n1. To the best of my knowledge, this paper is the first to consider the problem of stochastic dueling bandits with stochastic delays.\n2. The authors consider two settings: one where the distribution of delays is known and a second where only the expected value of delays is known. The authors propose algorithms for both settings and show that both algorithms have sub-linear regret3\n3. Finally, the authors have considered different problem instances derived from real datasets to show the performance gain of the proposed algorithms over baselines.\n\n\n#### **Weaknesses of the paper:**\n1. Assumption: The assumption of censored feedback is a bit strict in unobserved feedback. Saying the unobserved feedback only implies A>B will cause the biased estimation of preference feedback because it is possible that a user may not like both A and B in real life. \n\n2. Motivational examples and delay assumption: There needs to be a motivational example that fits well into your setting. The given example is more suitable for contextual dueling bandits. It is unclear how one can know the distribution or expected value of delay in the motivational example considered in the paper. The assumptions considered on delays limit the applications of proposed algorithms.\n\n3. Analysis novelty: The dueling bandits and bandits problem with stochastic delay are now separately well-studied problems. From the paper, it is unclear what the key challenges are with bringing stochastic delay feedback in stochastic dueling bandits. The settings considered in the paper are very simple compared to the stochastic delay feedback settings already considered in bandits. The best problem setting can be the most settings (e.g., contextual dueling bandits with non-linear reward function and unknown stochastic delays), which can be motivated from the following paper:\n\n    1. Bayesian Optimization under Stochastic Delayed Feedback: https://proceedings.mlr.press/v162/verma22a/verma22a.pdf\n\n    2. Delayed feedback in kernel bandits: https://proceedings.mlr.press/v202/vakili23a/vakili23a.pdf", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the stochastic dueling bandits problem with stochastic delay. Here, the number of arms is finite, and the distribution or expected value of stochastic delays is assumed to be known. The goal is to learn a policy that selects two arms (duel) in each round to minimize the cumulative regret (dueling bandits variant). \n\nThe authors propose two algorithms: RUCB-Delay when the distribution of delays is known and MRR-DB-Delay when the only expected value of delays is known. They have shown sub-linear regret bounds for both algorithms and corroborated their theoretical results using experiments on instances derived from real-world datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the weaknesses mentioned in **Strengths And Weaknesses**.", "broader_impact_concerns": "Since it is a theoretical paper, I do not find any ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cP8aTgFiFS", "reviewer": "Reviewer_WpS9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n* This paper addresses a novel and intuitive dueling bandit problem with stochastic delayed feedback.\n\n* For the setting with known delay distribution, the authors introduce a modified upper confidence bound (UCB) algorithm. This modification could potentially benefit other UCB-based dueling bandit algorithms dealing with delayed feedback. \n\n* For the setting with known expected delay, they propose a multi round-robin algorithm and provide a thorough regret analysis.\n\n* Experiments on six datasets demonstrate the superior performance of the proposed algorithms.\n\n**Weaknesses**\n\n* Despite the example provided in Fig. 1, it is still unclear why unobserved means A>B in dueling bandits: if a user has not yet decided between two recommended items, why do we assume the user prefers the first one? \n\n* More explanation is needed to justify the practicality of this model.\n\n* The authors demonstrate that RUCB-Delay achieves the optimal regret bound for the dueling bandit problem when there is no delay. However, they do not provide regret lower bounds for settings with known delay distribution or known expected delay, leaving the optimality of the proposed algorithms in these settings uncertain.\n\n* This paper studies the known expected delay setting. In contrast, prior literature on stochastic bandits with delayed feedback has explored settings without prior delay information. This limitation may narrow the scope of the paper.\n\n* Experiments: The authors do not explain why RR-DB-Delay outperforms RUCB-Delay in Figure 2(c). It would be helpful to include experiments on different delay distributions to better understand the algorithms' performance across varied conditions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the dueling bandit problem with stochastic delayed feedback. The authors introduce two algorithms designed to address scenarios where either the full delay distribution information is available or only the expected delay is known. They provide a comprehensive regret analysis for the proposed algorithms and demonstrate their empirical performance using both synthetic and real datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weaknesses section above.", "broader_impact_concerns": "this is a theory paper and the reviewers do not see any concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "axgvRxCPW8", "reviewer": "Reviewer_oe1e", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem studied in this paper, dueling bandits under delayed feedback, seems novel, and it leads to some unique challenges given that feedback is limited to relative comparisons. For the setting where the delay distribution is known, the proposed algorithm is adapted from RUCB and uses a modified upper confidence bound that manages delays; it recovers the optimal regret bound for dueling bandits when there is no delay. For the setting where only the expected delay is known, the proposed algorithm extends ideas from (Pike-Burke et al., 2018) to dueling bandits. The empirical study is nice to have, and seems to validate the theoretical findings.\n\nI have some questions/concerns about the problem formulation. It seems to me that the preference/comparative bias is introduced by the algorithm/formulation and is not necessarily inherent in dueling bandits itself. The authors mention that in multi-armed bandits under delayed feedback (Vernade et al., 2017; 2020), the learner observes a zero reward when the reward is not yet available. I am not entirely convinced that this should be kept the same for dueling bandits, as this naive extension would imply that a learner should assume that one arm in a pair is primary, which does not seem native to the dueling bandits setting. It is not yet clear to me how a simple algorithm would behave if it simply does not use comparisons that have not been observed yet (e.g., Joulani et al., 2013, Section 4), instead of presuming that one arm is preferred by default. In particular, how would this baseline algorithm behave in the experiments?\n\nIn addition, the paper assumes that the delay distribution is independent of the selected pair of arms. In the context of preference comparisons, it would be a lot more interesting and natural to see settings where, for example, a user hesitates more because $\\mu_{ij}$ is close to $1/2$.\n\nThe presentation of this paper seems fair. Some of the technical discussions (e.g., Section 3.2) can be a bit hard to follow.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies dueling bandits under delayed feedback, where each delay is randomly drawn from a distribution that is independent of the chosen pair of arms and supported on $\\mathbb{N}$. In particular, the paper assumes that when a comparison feedback between two arms is not yet available due to a delay, the learner presumes that one of the arms is preferred, resulting in a preference bias; one given example is that, in e-commerce, if a user is looking at an item A, and the platform recommends another item B, a delay suggests that the user stays at A and therefore presumably prefers A over B.\n\nThe paper proposes two algorithms: RUCB-Delay, for the case where the delay distribution is known and that any feedback can only be seen if the delay is no more than $M$ rounds, and MRR-DB-Delay which only requires that the expected delay is bounded and known. Regret guarantees for these algorithms are provided as well as an empirical study that uses preference datasets, to which simulated delays are added.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It would be helpful if the authors could discuss, for each choice of a pair of arms $(i,j)$ by the player, when/how the order of the arms matters because of comparative/preference bias.\n\n2. In Section 3.1, it would be helpful if the authors could provide some explanations/intuitions about the definition of $S_ij$.\n\n3. The latter half of Section 3.2 can be hard to follow -- some intuitive explanations would help?\n\n4. In Section 4, there seems to be no discussion about the role of comparative/preference bias anymore.\n\n5. In Section 5, it is mentioned that the baseline RUCB algorithm “uses the number of times arm $i$ beats arm $j$ to establish their upper confidence bound.\" Does this number include potentially delayed feedback?", "broader_impact_concerns": "No particular concerns. The authors could briefly discuss how this work can be potentially related to reinforcement learning with human feedback for large language models.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I would ask the authors to please revise the last claim in light of my comment in the Claims and Evidence section. I believe just a factual summary description of the experiments run is sufficient (even just removing the word "comprehensive" is fine with me).
Decision: Accept (poster)