An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem
Authors: Arpit Agarwal
Rohan Ghuge
Viswanath Nagarajan
Venue: NeurIPS 2022 Accept (2022)

Abstract: We study the $K$-armed dueling bandit problem, a variation of the traditional multi-armed bandit problem in which feedback is obtained in the form of pairwise comparisons. Previous learning algorithms have focused on the fully adaptive setting, where the algorithm can make updates after every comparison. The "batched" dueling bandit problem is motivated by large-scale applications like web search ranking and recommendation systems, where  performing sequential updates may be infeasible. In this work, we ask: is there a solution using only a few adaptive rounds that matches the asymptotic regret bounds of the best sequential algorithms for $K$-armed dueling bandits? We answer this in the affirmative under the Condorcet condition, a standard setting of the $K$-armed dueling bandit problem. We obtain asymptotic regret of $O(K^2\log^2(K))$ + $O(K\log(T))$ in $O(\log(T))$ rounds, where $T$ is the time horizon. Our regret bounds nearly match  the best regret bounds known in the fully sequential setting under the Condorcet condition. Finally, in computational experiments  over a variety of real-world datasets, we observe that our algorithm using $O(\log(T))$ rounds achieves almost the same performance as fully sequential algorithms (that use $T$ rounds).

An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem
Arpit Agarwal Columbia University
Rohan Ghuge University of Michigan rghuge@umich edu
Viswanath Nagarajan University of Michigan viswa@umi ch, edu
edu
Abstract
We study the K-armed dueling bandit problem, a variation of the traditional multi- armed bandit problem in which feedback is obtained in the form of pairwise comparisons. Previous learning algorithms have focused on the fully adaptive set- ting, where the algorithm can make updates after every comparison. The "batched" dueling bandit problem is motivated by large-scale applications like web search ranking and recommendation systems, where performing sequential updates may be infeasible. In this work, we ask: is there a solution using only a few adaptive rounds that matches the asymptotic regret bounds of the best sequential algorithms for K -aareed dueling bandits? We answer this in the affirmative under the Con- dorcet condition, a standard setting of the K-armed ducling bandit problem. We obtain asymptotic regret of O(K² log" (K)) + O(K log(T)) in (log(T)) rounds, where T is the time horizon. Our regret bounds nearly match the best regret bounds known in the fully sequential setting under the Condorcet condition. Finally, in computational experiments over variety of real-world datasets, we observe that our algorithm using (log(T)) rounds achieves almost the same performance as fully sequential algorithms (that use T rounds).
1 Introduction
The K Karredd dueling bandit problem is a variation of the traditional multi-armed bandit problem in which feedback is obtained in the form of pairwise preferences. This problem has applications in a wide-variety of domains like search ranking, recommendation systems and sports ranking where eliciting qualitative feedback is easy while real-valued feedback is not easily interpretable; thus, has been a popular topic of research in the machine learning community (see, for example,
SI
54 52
53
21
32
35
36
42 18).
Previous learning algorithms have focused on fully adaptive setting: that is, the learning algorithm can make updates in a sequential fashion. Such updates might be impractical in large systems; for example, consider web-search ranking where the goal is to provide a list (usually ranked) of candidate documents to the user of the system in response search engines use hundred parameters to compute a ranked list in response to a query, and online learning frameworks (based user feedback) have been invaluable in automatically tuning these parameters [88. However, given the scale of the system, it may be infeasible to adapt after each interaction: users may make multiple queries in a short time or multiple users may simultaneously query the system. Hence, we prefer solutions with limited rounds of adaptivity. Concretely, we ask: is there solution using only a few adaptive rounds that matches the asymptotic regret bounds of the best sequential algorithms for K -arreed dueling bandits?
query
[4] 33 50 31. Modern day
This "batched" dueling bandit problem was introduced recently in [2]. Here, the learning algorithm's 's actions are partitioned into a limited number of rounds. In each round/batch, the algorithm commits to a fixed set of pairwise comparisons, and the feedback for all these comparisons is received
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

simultaneously. Then, the algorithm uses the feedback from the current batch of comparisons to choose comparisons for the next batch. 2 studied this problem under two different conditions: (i) the strong stochastic transitivity and stochastic triangle inequality (SST+STI) condition, which enforces a certain linear ordering over the arms; (ii) the Condorcet condition, which requires one arm to be superior to all others. Under SST+STI, their work provided almost tight upper and lower bounds on the trade-off between number of rounds and regret, in particular, they showed that one can achieve worst-case regret of OK log" T) using (llo T) rounds (T' is the time- horizoor Under the Condorcet condition, which is more general than SST+STI, they achieved regret upper bound of O(K² log T) in Olog 7) rounds. Previous work (54) 35 on fully sequential algorithms has shown that it is possible to achieve an asymptotic upper bound of O(K² + K log 7') under the Condorcet condition. Very recently, [4] improved the sequential regret bound even further by obtaining regret O(K log T", which is the best possible even in the special case of SST+STI [49]. In the batched setting, the upper bound of [2] does not achieve this asymptotic optimality, irrespective of the number of batches, due to the presence of K2 multiplicative factor in the regret bound. Their work left open the possibility of obtaining a batched algorithm achieving asymptotic optimality under the Condorcet condition. In this paper, we nearly resolve this question, by providing an algorithm with OKK² log" K + K log T)) regret in Ollo T)) rounds, under the Condorcet condition.
1.1 Contributions
We design an algorithm, denoted C2B, for the batched dueling bandit problem, and analyze its regret under the Condorcet condition. This algorithm achieves a smooth trade-off between the expected regret and the number of batches, B.
Crucially, when B = log(T"), ), our regret bounds nearly match the best regret bounds [3 54 known in the fully sequential setting. Hence, our results show that Ollog T') rounds are sufficient to achieve asymptotically optimal regret as function of T'
Our results rely on new ideas for showing that the Condorcet winner arm can be 'trapped' using few adaptive rounds with high (constant) probability while incurring a reasonable amount of regret. We can then integrate over this space of probabilities to obtain a bound on the expected regret (in the same vein as (54)). Once the Condorcet arm is 'trapped', we can quickly climinate all other 'sub-optimal" arms and minimize regret in the process.
Finally, run computational experiments to validate our theoretical results. We show that C2B, using Olog 7) batches, achieves almost the same performance as fully sequential algorithms (which effectively use T batches) over a variety of real datasets.
1.2 Preliminaries
The K-armed dueling bandit problem 49 is online optimization problem, where the goal is to find the best among K bandits B = {1..... K} using noisy pairwise comparisons with low regret. In each time-step, noisy comparison between two arms (possibly the same), say (i, is performed. The outcome of the comparison is an independent random variable, and the probability of picking i over is denoted pt,j = 1 + A.. where Aijj E (- /. 4). Here, Aij can be thought of measure of distinguishability between the two arms, and we use i > jj when A. > 0. We also refer to A., as the gap between and j.
This problem has been studied under various conditions on the pairwise probabilities pt, 's One such condition is the strong stochastic transifivity and stochastic triangle inequality (SST+STI) condition where there exists an ordering over arms, denoted by 2, such that for every triple i ž 2 k, we have Ar, max A.jj Aj.), i and AI, Ar, + AJAA 49 5T. In this paper, we work under the well-studied Condorcet winner condition, which is much more general than the SST+STI condition
[47 (54 (35]. We say that arm is Condorcet winner if, and only if, Pi.j N for all B {i).
The Condorcet condition means that there exists a Condorcet winner.
Throughout the paper, we let a" refer to the Condorcet arm. To further simplify notation, we define A = Da ij that is, the gap between a" and j. We define the regret per time-step as follows: suppose arms i, and je are chosen in time-step then the regret r(t) A., tAu, The cumulative regret up to time T is R(T)-
2
T r(t), where T is the time horizon, and it's assumed that K < T. The
They also gave more complicated algorithm with regret O(K log² K log?) in O(log + log K log log K) rounds, under the SST+STI condition.

---

Table 1: An overview of our results. Note that Ô hides polylog(K) factors.
Setting
Regret
Fully Adaptive
0
K²
Σ 5:
log
54
35
A min
B
Ej:d,20 O log(T)
rounds
45
A,
Batched
Eji O (KT1/B. 3,
log(T)
rounds
Our Algorithm
B rounds
K² A
+
T .K2) + +E, o ln
log (T) rounds
K²
+ EE 0 log(T) Aj
A2
cumulative regret can be equivalently stated as R(T) = Σý= TjAj. where T, denotes the number comparisons involving arm j. The goal of algorithm is to minimize the cumulative R(T). We define Amin = m Aj to be the smallest non-zero gap of any arm with a".
1.3 Batch Policies
In traditional bandit settings, actions are performed sequentially, utilizing the results of all prior actions in determining the action. In the batched setting, the algorithm must commit round (or batch) of actions to be performed in parallel, and can only observe the results after all actions in the batch have been performed. More formally, given number of batches, the algorithm proceeds as follows. In each batch 1, ..... B, the algorithm first decides on the comparisons be performed; then, all outcomes of the batch-r comparisons are received simultaneously. The algorithm can then, adaptively, select the next batch of comparisons. Note that even the size of the next batch can be adaptively decided based the observations previous batches. Finally, the total number of comparisons (across all batches) must sum to T. We assume that the values of T and B are known. Observe that when = B, we recover the fully sequential setting.
1.4 Results and Techniques
We provide a overview our results and prior results in Table Given any integer B 2 1, we obtain B-round algorithm for the dueling bandit problem. We provide both high-probability and expected regret bounds, stated in the following theorems.
Theorem 1.1. For any integer B 2 1, there is an algorithm for the K-armed dueling bandit problem that uses at most B rounds with the following guarantee. For any 8 >> O, with probability at least 1 $. its regret under the Condorcet condition is at most
R(T) 50 (T
K2 log(K)
log
log K
)
+ O
T2/B K2.
A
A Amin
(1/B
logg KT)
Σ O j
A
Theorem 1.2. For any integer B 2 1, there is algorithm for the K -armed dueling bandit problem that uses at most B rounds, with expected regret under the Condorcet condition at most
E(R(T)] = -(T1//B.
K2 log(K) log
(logK) K Amin
))
+ (T2/B. K2)
2 min
T1/B log KTT)
+
Σ 0
A
j

---

When the number of rounds B = log(T), we obtain a batched algorithm that achieves the asymptotic optimality (in terms of T), even for sequential algorithms. We formalize this observation in the following corollary.
Corollary 1.3. There is an algorithm for the K-armed dueling bandit problem that uses at most (T) rounds, with expected regret under the Condorcet condition at most
B[R(T)] = (**
( log(K)
llog K
))
log KT) A
-log
A min
Amin
By a lower-bound result from [2]. it follows that no algorithm can achieve O K_ poly T))
regret using ol log Tog rounds, even under the SST+STI condition. So, the Oloog T) rounds required
to achieve asymptotic optimality in Corollary 1.3 is nearly the best possible.
Technical Challenges. The only prior approach for batched dueling bandits (under the Condorcet condition) is the algorithm PCOMP from 22. which performs all all-pairs comparisons among arms in an active set. Such an approach cannot achieve regret better than O log T') because the active set may remain large throughout. In order to achieve better regret bounds, 2 focus on the stronger SST+STI condition. In this setting, their main idea is to first sample seed set, and use this seed set to eliminate sub-optimal arms. Their algorithm proceeds by performing all pairwise comparisons between the seed set and the set of active arms. However, the analysis of these 'seeded comparison' algorithms crucially rely on the total oodering imposed by the SST and STI assumptions. Unfortunately. there is no such structure to exploit in the Condorcet setting: if the seed set does not contain the Condorcet winner, we immediately incur high regret.
The existing fully sequential algorithms such as RUCB 54 and RMED 35 are highly adaptive in nature. For instance, RUCB plays each candidate arm against an optimistic competitor arm using upper confidence bounds (UCB) on pairwise probabilities. This allows RUCB to quickly filter out candidates and uncover the Condorcet arm. Similarly, RMED plays each arm against a carefully selected competitor arm that is likely to beat this arm. However, such competitors can change frequently over trials in both RUCB and RMED. Since the batched setting requires comparisons to be predetermined, do not have the flexibility to adapt such changes in competitors. Hence, these existing fully sequential algorithms cannot be easily implemented in our setting.
Furthermore, we might also be tempted to consider an explore-thens theneeeooo--- strategy where we first explore to find the Condorcet arm and exploit by playing this arm for remaining trials. However, this strategy is likely to fail because identifying the Condorctt arm with high probability might involve performing many comparisons, directly leading to high (?2(K2 log T)) regret; on the other hand, the Condorcet winner is not identified with high probability, the exploit phase becomes expensive. This motivated us to consider algorithms that allow some form of recourse; that is, unless an arm is found to be sub-optimal, it must be given the opportunity to participate in the comparisons (as it could be the Condorcet winner).
The idea behind our algorithm is to identify the Condorcet winner a" in a small expected number of rounds, after which it uses this arm as an "anchor" to eliminate sub-optimal arms while incurring low regret. To identify the best arm, in each round we define a candidate arm and compare it against arms that it "defeats". Arms that are not defeated by the candidate arm are compared to all active arms: this step ensures that the Condorcet winner is eventually discovered. We show that a" becomes the candidate, and defeats all other arms within small number of rounds (though the algorithm may not know if this has occurred). Additionally, once this condition is established, it remains invariant in future rounds. This allows us to climinate sub-optimal arms and achieve low regret.
Comparison to RUCB. Initially, RUCB puts all arms in pool of potential champions, and "optimisti- cally" (using a upper confidence bound) performs all pairwise comparisons. Using these, it constructs a set of candidates C. If [C|= 1, then that arm is the hypothesised Condorcet winner and placed in a set B. Then, a randomized strategy is employed to choose a champion arm ag (from sets C' and B) which is compared to arm aa which is most likely to beat it. The pair (ac, ad) is compared, the probabilities are updated and the algorithm continues. Although our algorithm also seeks to identify the best arm, we do not employ the UCB approach nor do we use any randomness. In their analysis, (54) show that the best arm eventually enters the set B, and remains in B: we also show a similar property for our algorithm in the analysis. Finally, similar to the analysis of [54], first give

---

high-probability regret bound for our algorithm which we then convert to bound on the expected regret.
2 Related Work
The K K-armed dueling bandit problem has been widely studied in recent years (we refer the reader to [46] for a comprehensive survey). Here, we survey the works that are most closely related to our setting. This problem was first studied in [9 under the SST and STI setting. The authors obtained worst-case regret upper bound of Ö log T/ min) and provided matching lower bound. [51] considered a slightly more general version of the SST and STI setting and achieved an instance-wiis wise optimal regret upper bound of مر. O (log(T) A2). Since, the SST+STI condition
imposes a total order over the arms and might not hold for real-world datasets, [47 initiated the study of dueling bandits under the Condorcet winner condition. [47] proved ( log T/Amin)
regret upper bound under the Condorcet condition, which was improved by (54) O(K² / min) مودم,s O OlogT/ shown to be asymptotically instance-wise optimal (even in terms constant factors). There are also other works that improve the dependence on K in the upper bound, but suffer a worse dependence on A, 's [33 This problem has also been studied under other noise models such as utility based models [5] and other notions of regret [8]. Alternate notions of winners such as Borda winner [32], Copeland winner [52 36 48 and von Neumann winner [21] have also been considered. There are also several works on extensions of dueling bandits that allow multiple arms to be compared at once
(35 achieved a similar but tighter KL divergence-basee bound, which is
45 3 44
All of the aforementioned works on the dueling bandits problem are limited to the sequential setting. Recently. 22] initiated the study of the batched version of the K K-armed dueling bandits. Their main results are under the SST and STI setting. They give two algorithms, called SCOMP and SCOMP2, for the batched K-armed dueling bandit problem. For any integer B, SCOMP uses at most B + batches and has expected regret bounded by Ej.2,s O(VKT//BK log(T)/A,). When B = log(T).
this nearly matches (up to factor of vK) the best known mnstance-dependerr regret bound of Σدردد >o (log(T)) /A,) obtained by 49). SCOMP2 aims to achieve better worst-case regret:
uses at most 2B + 1 batches, and has regret O (KBTI/B / Thus, when B = the expected worst-case regret is O (K (T)) matching the best known result in the sequential setting up to an additional logarithmic factor. Under the Condorcet condition, ( give straightforward pairwise comparison algorithm (PCOMP), that achieves expected regret bounded by O(K2 log(T)/ Amin) in log( batches. They also provide nearly matching lower bound of
KTT/B for any B-batched algorithm. This implies that our bound (for B-round algorithms) in 2 B
Theorem
2
cannot be significantly improved.
43 designed fully adaptive algorithm achieving an optimal regret of Σ م='A>> O(log >0 A; for dueling bandits under the Condorcet setting. This algorithm is based on the idea of dueling two classical bandit (MAB) algorithms against each other in a repeated zero-sum game with carefully designed rewards. The reward for one algorithm depends on the actions of the other; hence, these algorithms need to achieve bext-of-buth-woord
Recently,
guarantee for both stochastic and adversarial settings. However, the approach of [43] is not directly applicable to the batched setting that we consider. This because, as shown by 23 any B-round algorithm for batched MAB in the adversarial setting has regret Q(T/B).
There has also been substantial work on best-arm or top-k identification using pairwise comparisons with limited adaptivity. [15] 14] 19 considered this problem under the noisy pairwise comparison setting, which is special case of SST+STI. They showed that constant number of rounds of adaptivity are sufficient to solve these problem with the optimal sample complexity. [4] showed that one can also solve this problem under SST in constant number of rounds with the optimal sample complexity. However, these existing results focus on the SST setting, whereas we focus on the more general Condorcet winner setting. Moreover, these existing works focus on sample complexity for best-arm identification whereas our goal is regret minimization.
3 The Batched Algorithm
In this section, we describe B-round algorithm for the K Karmedd dueling bandit problem under the Condorcet condition. Recall that given set of K arms, B {l...., K). and positive integer
5

---

B S lTg( we wish to find sequence of B batches of noisy comparisons with low regret. Given amns i and j. recall that pi.j = S.y denotes the probability of winning over j where Ai, E (-1 / 1 /2). We use a" to denote the Condorcet winner; recall that a" is a Condorcet winner if Pa--j 1/2 for all j E B. To simplify notation, we use A = A Before describing our algorithm, we first define some notation. We use A to denote the current set of active arms; i.e., the arms that have not been eliminated. We will use index r for rounds or batches. If pair (i,j) is compared round r, compared Gr = [gr"] times where q - T1/B. We define the following quantities at the end of each round r:
Nigg(r the total number of times the pair (i,j) has been compared. Pis(() (r) is the frequentist estimate of pi. i..,
(r) # i wins against j until end of round r
(I)
Nry(r)
Two confidence-interval radii for each (i,j) pair:
2 (rg (r)
Tis(r) log(K? BT) (N
(ra(r)
and
We now describe our B-round algorithm, called CATCHING THE CONDORCET WINNER IN BATCHES (or, C2B). At a high-level, the algorithm identifies the best arm a' in small expected number of rounds, after which uses this arm as an "anchor" to eliminate sub-optimal arms while incurring low regret. In every round we do the following:
1. We define a defeated set (i) for every active arm i; this set comprises arms that are defeated with confidence by Specifically, j (i) if fr 1) 1/2 + c.5(r 1).
2. Then, define a candidate i, the arm that defeats the most number of arms; that is,
1, = arg e (i).
3. For every arm + i,:
i E (i,)), then we compare to i, for qr times. The idea here to use i, as an anchor against We will show that a" becomes the candidate i, in small number of rounds. Then, this step ensures that we eliminate arms efficiently using a" as an anchor.
i & (i,), then is compared to all arms in A for g. times. This step crucially protects the algorithm against cases where a sub-optimal arm becomes the candidate (and continues to become the candidate). For example, suppose K [5] and the arms are linearly ordered as > 2 > ... 5. Furthermore suppose that in some round we have that (a) 2 defeats 3, 4, and (b) (best arm) defeats but not the others. So, is the candidate in round r; if is not compared to 3, 4, 5, then 2 would continue to be the candidate (leading to high regret).
4. If, for any arm j, there arm such that (r) 1/2 + (r) then j is eliminated from A.
This continues until T total comparisons performed. See Algorithm I for formal description. The main result of this section is to show that C2B achieves the guarantees stated in Theorems [.] and] I.2
Overview of the Analysis. We provide brief outline of the proofs of our main results. Towards proving Theorem I.I
we first define two events:
The first event, denoted G, ensures that a" is not eliminated during the execution of C2B. We show that P(G) 2 1/TT
The second event, denoted E(6), says that there exists round C(8) (defined later) such that for all > C()), the estimate (r, - 1) satisfies the confidence interval of cr 1). Moreover, P(E())) 2 8-
By union bound, P(G n E()) > - 8- 1/T. Together, we use G' and E()) to argue that:

---

Algorithm C2B (CATCHING THE CONDORCET WINNER IN BATCHES)
1: Input: Arms B, time-horizon T, integer B 221
2: active arms A B, < emprical probabilities (0) for all i,j E B
3:
while number of comparisons < ' do
4: Af {i] for some then play (i. i) for remaining trials
5:
(i( t (j A: P A
1) > 2 + trylr 1)}
6:
by
+ arg
7:
for i E A ( do
8:
if (1r then
9:
compare (ir, i) for times else
11:
for each E A, compare (i,j) for times
compute (r)) values
if 3i p 2 + (r) then
14:
A + (}}
15:
++
the best arm, a", is not defeated by any arm in any round Lemma 3.5)
C(8) (formalized in and that there exists round r(0) 2 C()) such that for every round after r(8), arm defeats every other arm (formalized in Lemma 3.7.
Intuitively, these observations imply that our algorithm identifies the best arm after r()) rounds. Thus, beyond round r(d), we only perform pairwise comparisons of the form (a", i) for j a": thus, a" is used as an anchor to eliminate sub-optimal arms. We then analyze the regret in two parts: (i) regret incurred up to round r(6). which upper bounded by K2 Ersr(s) 9" and (ii) regret after r(8), which the regret incurred in eliminating sub-optimal arms using as an anchor. Finally, we can use the high-prog gighprobbbbility bound to also obtain bound on the expected regret, proving Theorem 1.2 We provide some details of the proof of Theorem [.] We defer the proof of Theorem 1.2 Appendix D
3.1 The Analysis
In this section, we give high-probability and expected regret bounds for C2B, Recall that y = T1/B and that q 2 2. The following lemma is used prove that a" is never eliminated. We defer the proofs of the Lemmas
3.1 3.1 3.2 to Appendix B
Lemma 3.1. For any batch
[B]. and any pair (i,J), we have
P (r)),(r) Pı,l/> (.. S 2n,
where 7) - B/.
We first define the good event G as follows.
Definition 3.1 (Event G). An estimate (r.;(r) at the end of batch is strongly-correct if (r. Ps S (r). We say that event G occurs if every estimate in every batch r E [B] is strongly-correct
The following two lemmas show that G occurs with high probability and that a* is not eliminated under G.
Lemma 3.2. The probability that every estimate in every batch of C2B is strongly-coreet is at least 1 1/T
Lemma 3.3. Conditioned G, is never eliminated from in the elimination step of C2B.
Proof. In C2B, an arm j deleted in batch iff there is arm i with (r.) 1 (r, Ifa" eliminated due to some arm j. then by definition of event G, we get Pj.a- 2 Pr.(r) - (r,) 3 contradiction.

---

3.1.1 High- blob--robbbility Regret Bound
In this section, give details required to prove Theorem 1.1 Fix any 8 > O. We first define another good event as follows.
Definition 3.2 (Event E(6)). An estimate (r) in batch r is weakly-correct if (r.((r) -p,ll (r((r. Let C()) = - log, (1/6)] We say that event E(6) occurs for each batch r 2 ((6), every
estimate is weakly-correct.
The next lemma shows that E()) occurs with probability at least 1 - 8.
Lemma 3.4. For all
have
P(-F(6)) P (()) (P) - Pa. (r)(r)) s 6.
We will analyze our algorithm under both events G and E()). Note that event is required to ensure that a' is not climinated in rounds before C(a) (where the Lemma 3.4 not apply).
Lemma 3.5. Conditioned G and (()), for any round C((), a² is not defeated by any other arm, Le., a" É Uita (i).
To proceed, we need the following definitions.
Definition 3.3. The candidate i, of round r is called the champion (t))( | |A|-1; that is, if i defeats every other active arm.
Definition 3.4. Let r()) Z C(6) + be the smallest integer such that
32
(=( 2 2A log A, where =
log((K2))
2
min
We use the following inequality based on this choice of r(8).
Lemma 3.6. The above choice of r(0) satisfies
log (2K
Vr 2 r(6).
Proof of Lemma 3.6
Using the fact that or S 9 it suffices to show q" - (log(2k3) + log d²)
Moreover,
log 2) + log q" - (1 log(2k3)) (1 + log q²) < 4 4-log(22' (2K3) log
where the last inequality uses 2 2, 2 r(8) 2 1 and g 2 2. So, suffices to show:
32
g" > A log(g"),
2 r(6),
where A
(2K2)
(3)
2
min
Below, let q", R. 2A log A and function f(x) = Alogæ. We will show that f(x) for all x > R, which would imply (3) because (6) R. As R2 A, and is increasing for A. it suffices to show that f(R) 2 0. Indeed,
f(R)
log A log(2A A) log loog A) 0,
where the inequality uses A 2 8.
Then, have the following.
Lemma 3.7. Conditioned G and E(8), the best arm a" the champion in every round r()).
We have all components required to prove Theorem I.I: its proof, and the proofs of the aforementioned lemmas can be found in Appendix

---

C2B
RMED
SCOMP2
Regges RR1
C28
C25
RMED
Regrer
SCOMP2
Rogrest
SCOMP2
BUCS
HUCH
8TM
2-
0-
0-
0.5
0.5
1.0
0.2
0.4
0.5
1.0
0.0
0.2
1.0
105
165
165
(a) Six rankers
(b) Sushi
(c) Irish-Mon frish-Mcath
103
2c4
10c
3.0-
Regget R00)
2.5-
RMED
C28
RIO
RMED
C28
RUCB
ScrWP?
SCOMP?
0.3
1.5
165
1e6
le6
(d) Irish- Subb-Dublin
(c) MSLR30
(f) Yahoo30
Figure I: Regret v/s plots of algorithms when B [log(T)]
4 Computational Results
In this section, we provide details of our computational experiments. The goal of our experiments to answer the following questions: (i) How does the regret of C2B using B (log(T) batches compare to that of existing fully sequential as well as batched algorithms? and (ii Can the regret of C2B match the regret the best known sequential algorithms; if yes. then how many rounds suffice to achieve this? Towards answering (i), we compare C2B to representative set of sequential algorithms for dueling bandits using the library due to [35]. We compare C2B the sequential algorithms RUCB [54]], RMED 35 and BEAT-THE-MEAN (BTM) [5I] We allow these algorithms work as prescribed: that is, they work in B T batches. The reason that we chose these sequential algorithms is that our batched algorithm (C2B) is based on a similar paradigm, and such a comparison demonstrates the power of adaptivity in this context. We also compare C2B to the batched algorithm SCOMP2 [2]. We plot the cumulative regret R(() incurred by the algorithms against time 4. We set = [To](T)) for C2B and SCOMP2 in this experiment. For (ii), we increased by small amount; we found that the performance of C2B improves noticeably when given constant number of additional rounds (we use = [log(T)) + in this experiment). We perform these experiments using the following real-world datasets.
Six rankers. This dataset based on the 6 retrieval functions used in the engine of ArXiv.org.
Sushi. The Sushi dataset is based on the Sushi preference dataset 334 that contains the preference data regarding 100 types of Sushi. A preference dataset using the top-16 16 most popular types of sushi is obtained.
Irish election data. The Irish election data for Dublin and Meath is available at preftib.org. It contains partial preference orders over candidates. As in 33, these are transformed into preference matrices by selecting subset of candiates to ensure that Condorcet winner exists. There are 12 candidates in the Irish-Meath dataset, and 8 in the Fishh-uullin dataset.
MSLR and Yahoo! data. We also run experiments on two web search ranking datasets: the Microsoft Learning to Rank (MSLR) dataset 440 and the Yahoo! Learning Rank Challenge Set [6] These datasets have been used in prior work on online ranker evaluation [53] 37]. We use preference matrices generated using the "navigational" configuration (see (37 for details). The MSLR dataset has 136 rankers and the Yahoo! dataset has 700 rankers. We sample 30 rankers from each dataset while ensuring the existence of a Condorcer winner. this way, we obtain two datasets, denoted MSLR30 and Yahoo30.

---

C2B
RMED
Regnet 40
C28
Roggee R00
C28
RMFN
RMFD
Rog
SCOMP2
SCOMP2
HUCH
RUCS
6TM
2-
0
0-
0.5
0.5
1.0
0.2
0.4
0.5
1.0
0.0
0.2
1.0
105
165
165
(a) Six rankers
(b) Sushi
(c) Irish-Mcane
103
10c
Bogget R00
2.0
C2B
RNED SCOMPO
Regret R13
RUCB
Regret
RUCB
0.3
1.0
165
1e6
le6
(d) Dush-Dublin
(c) MSLR30
(f)
Yahoo30
Figure 2: Regret v/s plots algorithms when B [Tog(T))
Note that there exists Condorcet winner in all datasets. We repeat each experiment 20 times and report the average regret. In our algorithm, we use the KL-divergence based confidence bound due to (35] for elimination it performs much better empirically, and our theoretical bounds continue E This KL-divergence based climination criterion climinates an arm in round log(T) f(K) where [r(r) Ejst, Nry(r) DRL (Pi 2) and
to hold (see
if (r)
I (r) = minje[K] L(r).
Computational Results. As mentioned earlier, we compare our algorithms against a representative set of sequential dueling bandits algorithms (RUCB, RMED, and BTM). We set a 0.51 for RUCB, and f(K) = 1.3. for RMED and C2B, and 1.3 for BTM: these parameters are known to perform well both theoretically and empirically [35] We set T 10 for MSLR30 and Yahoo30 datasets (as they have larger number of arms), and T = 10 for the remaining four. For the first set of experiments, we set = [log(T)].
observe that C2B always outperforms BTM and beats SCOMP2 on most of the datasets. We observe that even when SCOMP2 beats C2B it has slightly linear curve (implying that its regret would keep increasing as increases) while the regret curve of C2B is mostly flat. Furthermore, C2B performs comparably to RUCB in all datasets except Yahoo30. We plot the results in Figure [ In the second set experiments, we set B = (T)( + We observe that C2B always outperforms RUCB and, in fact, performs comparably datasets except Yahoo30. We plot the results Figure 2 Finally, we note that SCOMP2 exhibits varying performance across runs (even the same dataset) and we think that this is due to the randomness involved in selecting the "seed set"..
RMED all
Conclusion
In this paper, we proposed a batched algorithm, named C2B, for the K K-armed ducling bandit problem. Assuming the existence of a Condorcet winner, we show both high-probability and expected regret bounds for C2B that trade-off smoothly with the number of batches. Furthermore, we obtain asymp- totic regret of O(K" log" (K)) ((Kllog(TT)) in O(log(T) batches, nearly matching the best regret bounds known in the fully sequential setting under the Condorcet condition. Our computational results show that C2B, using (log(TT) batches, achieves almost the same performance as fully sequential algorithms over a variety real-world datasets. A direction for future research is to design batched algorithms for the K -armed dueling bandit problem when Condorcet winner does not exist; for example, designing an algorithm for more general concept of winner, such as Copeland winner 48 or Neumann winner [22]
10

---

References
[1] A. Agarwal, Assadi, and S. Khanna. Stochastic submodular cover with limited adaptivity, In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, page 323-342, 2019.
[2] A. Agarwal, Ghuge, and Nagarajan. Batched dueling bandits. In Proceedings of the 39th International Conference on Machine Learning, pages 110, 2022.
[3] A. Agarwal, N. Johnson, and S. Agarwal. Choice bandits. In NeurlPS, 2020.
[4] A. Agarwal, S. Khanna, and P. Patil. PAC top-k identification under SST in limited rounds. In G. Camps- Valls, F. R. Ruiz, and I. Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 6814-6839. PMLR, 2022.
[5] N. Ailon, Z. Karnin, and T. Joachims. Reducing Dueling Bandits Cardinal Bandits. In Proceedings of the 31st International Conference on Machine Learning, 2014.
[6] E. Balkanski, A. Breuer, and Y. Singer. Non-monotone submodular maximization exponentially fewer iterations. In Advances in Neural Information Processing Systems, pages 2359-2370, 2018.
[7] E. Balkanski, A. Rubinstein, and Y. Singer. An exponential speedup in parallel running time for submodular maximization without loss in approximation. In Proceedings of the 30th Annual ACM-SIAM Symposium Discrete Algorithms, pages 283-302, 2019.
[8] E. Balkanski and Y. Singer. The adaptive complexity of maximizing submodular function. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1138 1151, 2018
[9] E. Balkanski and Singer. Approximation guarantees for adaptive sampling. In Proceedings of the 35th International Conference on Machine Learning, pages 393-402, 2018.
[10] N. Bansal, A. Gupta, J. Li, J. Mestre, V. Nagarajan, and A. Rudra. When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica, 63(4):733- 762, 2012.
[11] N. Bansal and V. Nagarajan. On the adaptivity gap of stochastic orienteering. Math. Program., 154(1- 14:145- 2015.
[12] S. Behnezhad, M. Derakhshan, and M. Hajiaghayi. Stochastic matching with few queries: (I-r) approxi- mation. In Proccedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pages 1111-1124, 2020.
[13] A. Bhalgat, A. Goel, and S. Khanna. Improved approximation results for stochastic knapsack problems. In Proceedingy of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1647-1665, 2011.
[14] M. Braverman, J. Mao, and Y. Peres. Sorted top-k in rounds. In A. Beygelzimer and D. Hsu, editors, Con- ference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 342 382. PMLR, 2019.
[15] M. Braverman, J. Mao, and S. M. Weinberg. Parallel Algorithms for Select and Partition with Noisy Comparisons. In Proceedings of the 48th Annual Symposium on the Theory of Compuring, 2016.
[16] O. Chapelle and Chang. Yahoo! learning to rank challenge overview. In Proceedings of the 2010 International Conference on Yahoo! Learning to Rank Challenge Volume 14, page 1-24. JML..org. 2010.
[17] C. Chekuri and K. Quanrud. Parallelizing greedy for submodular set function maximization in matroids and beyond. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 78-89, 2019.
[18] B. Chen and P. T. Frazier. Dueling Bandits with Weak Regret. In Proceedings of the 34th International Conference on Machine Learning. 2017.
[19] V. Cohen-Addad, F. Mallmann-Trentt and C. Mathieu. Instance-optimaality in the noisy value-and comparison-noddl. In S. Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2124-2143 SIAM, 2020.
[20] B. C. Dean, M. X. Goemans, and J. Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res., 33(4):945 964, 2008

---

[21] M. Dudik. K. Hofmann, R. E. Schapire, A. Slivkins, and M. Zoghi. Contextual Dueling Bandits. In Proceedings of the 28th Conference on Learning Theory, 2015.
[22] M. Dudík, K. Hofmann, R. E. Schapire, A. Slivkins, and M. Zoghi. Contextual dueling bandits. In P. Grünwald, E. Hazan, and S. Kale, editors, Proceedings of The 28th Conference on Learning Theory. COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings pages 563-587. JogR.org, 2015.
[23] H. Esfandiari, A. Karbasi, A. Mehrabian, and V. Mirrokni. Regret bounds for batched bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8):7340-7333 May 2021.
[24] H. Esfandiari, A. Karbasi, and V. Mirrokni. Adaptivity in adaptive submodularity. In Proceedings of 34th Conference on Learning Theory, volume 134, pages 1823-1846. PMLR, 2021.
[25] Z. Gao, Y. Han, Z. Ren, and Z. Zhou. Batched multi-armed bandits problem. H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. B. Fox, and R. Garnett, editors, Advances in Neural Information P Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14 14, 2019, Vancouver, BC, Canada, pages 501-511, 2019.
[26] R. Ghuge, A. Gupta, and V. Nagarajan. The power of adaptivity for stochastic submodular cover. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3702 3712. PMLR, 24 2021.
[27] D. Golovin and A. Krause. Adaptive submodularity: A new approach active learning and stochastic optimization. CoRR, abs/1003.3967, 2017.
[28] S. Guha and K. Munagala. Multi-armed bandits with metric switching costs. In Automata, Languages and Programming, 36th Internatilonal Colloquium (ICALP). pages 496-507,2222 2009.
[29] A. Gupta, R. Krishnaswamy, V. Nagarajan, and R. Ravi. Running errands in time: Approximation algorithms for stochastic orienteering. Math. Oper. Res., 40(1):56-79, 2015.
[30] A. Gupta and V. Nagarajan. A stochastic probing problem with applications. In Integer Programming and Combinatorial Optimization 16th International Conference, pages 205-216, 2013.
[31] K. Hofmann, S. Whiteson, and M. Rijke. Balancing exploration and exploitation in listwise and pairwise online learning to rank for information retrieval. Inf. Retr., 16(1):63-90, feb 2013.
[32] K. Jamieson, S. Katariya, A. Deshpande, and R. Nowak. Sparse Ducling Bandits. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, 2015.
[33] T. Joachims. Optimizing search engines using clickthrough data. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '02, page 133-142, New York, NY, USA, 2002. Association for Computing Machinery.
[34] T. Kamishima. Nantonac collaborative filtering: recommendation based on order responses. In Proceed- ings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24- 27, 2003, pages 583-588, 2003.
[35] J. Komiyama, J. Honda, H. Kashima, and H. Nakagawa. Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem. In Proceedings of the 28th Conference on Learning Theory, 2015.
[36] J. Komiyama, J. Honda, and H. Nakagawa. Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm. In Proceedings of the 33rd International Conference on Machine Learning, 2016.
[37] C. Li, I. Markov, M. de Rijke, and M. Zoghi. Mergedls: A method for effective large-scale online ranker evaluation. ACM Trans, Inf. Syst., 38(4):40:1-40222 2020.
[38] T.-Y. Liu. Learning rank for information retrieval. Found. Trends Inf. Retr, 3(3):225-331, mar 2009.
[39] V. Perchet, P. Rigollet, S. Chassang, and E. Snowberg. Batched bandit problems. The Annals of Statistics, 44(2):600-611, 2016.
[40] T. Qin and T.-Y. Liu. Introducing letor 4.0 datascts. ArXiv, abs/1306 0111130669997 2597, 2013.
[41] F. Radlinski, M. Kurup, and T. Joachims. How does clickthrough data reflect retrieval quality? In Proceedings of the 17th ACM Conference on Information and Knowledge Management, CIKM '08, page 33-52, New York, NY, USA, 2008. Association for Computing Machinery.
12

---

[42] S. Ramamohan, A. Rajkumar, and S. Agarwal. Dueling Bandits Beyond Condorcet Winners to General Tournament Solutions. In Advances in Neural Information Processing Systems 29, 2016.
[43] A. Saha and P. Gaillard. Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences. In International Conference Machine Learning, pages 19011 1-19026. PMLR, 2022.
[44] A. Saha and A. Gopalan. Combinatorial bandits with relative feedback. In H. M. Wallach, H. Larochelle, A. Beygelzimer, d' Alché- Bue, B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 983-993, 2019.
[45] Y. Sui, V. Zhuang. J. W. Burdick, and Y. Yue. Multi-dueling Bandits with Dependent Arms. In Proceedings of the 33rd Conference Uncertainty in Artificial Intelligence, 2017.
[46] Y. Sui, M. Zoghi, K. Hofmann, and Y. Yue. Advancements in dueling bandits. In J. Lang, editor, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 5502-5510. ijeai.org. 2018.
[47] T. Urvoy, F. Clerot, R. Feraud, and S. Naamane. Generic Exploration and K-armed Voting Bandits, In Proceedings of the 30th International Conference on Machine Learning, 2013.
[48] H. Wu and X. Liu. Double thompson sampling for dueling bandits. In Advances Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 649-657, 2016.
[49] Y. Yue, Broder, R. Kleinberg, and Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 18(5):158-11556 2012. JCSS Special Issue: Cloud Computing 2011.
[50] Y. Yue and Joachims. Interactively optimizing information retrieval systems as a ducling bandits problem. In Proceedings the the 26th Anmual International Conference on Machine Learning, ICMI. '09, page 1201-1208, New York, NY, USA, 2009. Association for Computing Machinery.
[51] Y. Yue and T. Joachims. Beat the mean bandit. In Proceedings of the 28th International Conference on Machine Learning, 2011.
[52] M. Zoghi, Z. Karnin, S. Whiteson, and M. de Rijke. Copeland Dueling Bandits. In Advances in Neurul Information Processing Systems 28, 2015.
[53] M. Zoghi, S. Whiteson, and M. de Rijke. MergeRUCB: A method for large-scale online ranker evaluation. In Proceedings of the 8th ACM International Conference on Web Search and Data Mining, 2015.
[54] M. Zoghi, S. Whiteson, R. Munos, and M. de Rijke. Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem. Proceedings of the 31st International Conference on Machine Learning, 2014.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes]. [No], or [N/A]. You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questionssansswrs below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
13

---

(b) Did you describe the limitations of your work? [Yes] We design a batched algorithm for the Kaarmed dueling bandit when the SST+STI condition does not hold; we work under the Condorcet condition. In $5, we pose designing algorithms for even more general settings as an open problem.
(c) Did you discuss any potential negative societal impacts of your work? [No] We don't t forsee any negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We include the code in the supplemental material.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] We include the details in $4.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] We include the details in $4.
(d) Did you include the total amount of compute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] We include the details in the appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] using/curating? [N/A] The library we used is publicly available. (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "rEgPyKqtS_", "reviewer": "Reviewer_AugK", "summary": "This work considered the batched dueling bandit problem under the Condorcet condition. It proposed a sequential elimination-based algorithm and derived regret bounds in expectation and with high probability. It also presented numerical experiments to show the effectiveness of the proposed algorithm.", "questions": "1. Are the authors willing to provide a regret lower bound? If it matches the derived lower bound, it would be more convincing that the upper bound is tight and the algorithm is optimal. There should be some discussions in Section 1.4.\n2. As the algorithms are proposed for different settings, how are they compared? It is nice that the algorithms are compared using several datasets, but more explanation of the experiment setup is appreciated.\n3. In Section 2, in addition to the detailed discussion, the readers may get a even clear view if a table comparing the bounds and conditions of algorithms in the existing literature is presented.", "limitations": "There seems to be no societal issue from my view.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is well organized and is easy to follow. It clearly discussed the motivation of problem setting, algorithm design and the technique challenges in detail and evaluate the algorithm with real-life datasets.\n\nWeaknesses: A lower bound may help strengthen the theoretical results and more explanation in the experiments setup is appreciated. (See \"Questions\" part for more details.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "asvxnifX6X", "reviewer": "Reviewer_Zi8f", "summary": "The authors study the batched dueling bandit problem under the Condorcet condition. They design an algorithm named C2B with a few adaptive rounds, and derive the upper bound for the asymptotic regret. Computational experiments are carried out with a number of real-world datasets.", "questions": "1. The authors claim that their method can nearly achieve the best rate for regret (line 12 and 115). Meanwhile, they mention a lower bound of $O(\\frac{K}{\\Delta_{\\min}}\\cdot poly(\\log T))$ (line 113), while the regret bound they derive is $\\tilde{O}(\\frac{K^2}{\\Delta_{\\min}^2})$. It seems a gap exists here, especially when $K$ is large or $\\Delta_{\\min}$. Is it possible to diminish the gap by trade-off the number of batches with performance?\n\n2. In the proposed algorithm, whenever a pair $(i,j)$ is compared in round $r$, it is always compared $q_r = \\lfloor q^r\\rfloor$ times. Will it be useful to adaptively assign the number of times for compare at each round based on previous compare results, in order to improve the performance? Intuitively, we might want to compare a pair more times if it is harder to tell which one is better.", "limitations": "The authors discuss the limitations of their work to some extent. There seems no negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The authors show that the proposed algorithm can achieve good performance with number of batches as small as $O(\\log t)$, which seems an interesting and new result.\n2. The feature of few adaptive rounds of the algorithm might accommodate modern applications of large scale.\n3. Overall, the paper is well-organized and easy to follow. The paper is detailed in backgrounds as well.\n\nWeakness:\nPlease find my questions/concerns in the next part.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QnScr5ckDmR", "reviewer": "Reviewer_iZS2", "summary": "This paper studies the dueling bandit problem with regret minimization as the objective under the assumption of an existing Condorcet winner. In contrast to most existing work dealing with fully adaptive learning situations, this work considers the situation of batched learning, where the learner does not decide before each learning round which pairwise comparison to perform, but decides this only in a limited number of rounds, i.e., it performs a batch of the same pairwise comparison at certain learning rounds. For this learning scenario, a learning algorithm is proposed that has a near-optimal upper bound on its cumulative regret using a nearly optimal number of batches. This improves upon existing methods which additionally need stronger assumptions than merely the existence of a Condorcet winner. The suggested algorithm is compared in a numerical study on real-world data sets with existing regret minimizing learning algorithms for the dueling bandit setting.", "questions": "Although the main ideas of the algorithm are described quite well, I would have liked to see a remark on the usage of two different confidence intervals in Section 3. I was wondering if this is technically not even one of the key design ideas which improve the theoretical results?\n\nMoreover, the textual description in Section 3 could be connected to the high-level description in Section 1.1 by reusing the term “trapped” and “recourse”, as it does not appear in Section 3 anymore.\n\nFinally, I am wondering why the theoretical analysis is not carried out for the KL-divergence-based confidence intervals if it (a) leads to the same theoretical results and (b) performs better empirically?\n\n### Minor things:\n\n- Typo in line 165: von Neumann.\n- There is a typo in [35].\n- In the math display of Proof of Lemma 3.1. it should be $\\hat p_{i,j}(r)$\n- The idea of the proof of Theorem 1.2 goes back to the proof of RUCB’s expected regret bound. I think the RUCB authors deserve some more credit.\n", "limitations": "## Potential negative social impact\nAs this is a theoretical work, there is no seemingly potential negative social impact.\n\n## Limitations\nThe authors clearly state that their algorithm is based on the Condorcet winner assumption and mention that it would be desirable to consider learning settings without such an assumption, e.g. Copeland winner or von Neumann winner settings.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- Batched learning settings are definitely relevant for practical applications and have also been studied recently in the standard multi-armed bandit setting. Thus, the scope of the paper is relevant to the ML community. \n\n- The paper is generally well-written. The notation is well thought out and the main ideas underlying the suggested learning algorithm are described in sufficient detail.\n- Although the learning setting is not novel, as it has been considered by other authors before, the suggested learning algorithm comes with stronger theoretical guarantees than existing methods.\n- The proofs seem to be sound as far as I can tell.\n\n# Weaknesses\n\n## Related literature\n\nThere is some missing related literature:\n\n-  Mark Braverman, Jieming Mao, and S. Matthew Weinberg. Parallel algorithms for select and partition with noisy comparisons. In Proceedings of the ACM symposium on Theory of Computing, pages 851- 862, 2016. \n\nThis paper also studies the question of round/batch complexity of learners in the dueling bandit setting, but for the objective of finding the top-k arms.\n\n- Chuang-Chieh Lin and Chi-Jen Lu. Efficient mechanisms for peer grading and dueling bandits. In Asian Conference on Machine Learning (ACML), pages 740-755, 2018.\n\nThis paper studies the question of round/batch complexity of learners in the multi-dueling bandit setting (with utilities of the arms), but for the objective of finding the best arm (NB: the Borda winner scenario is considered as well).\n\nAlthough the objectives of the two papers are different from the considered regret minimization objective, I think they are definitely worth mentioning.\n\nAs a side note: These two papers are discussed in the following survey paper on dueling bandits (Section 3.1.18, 3.2.6, and 4.2.8):\n\n- Bengs, V., Busa-Fekete, R., El Mesaoudi-Paul, A., & Hüllermeier, E. (2021). Preference-based Online Learning with Dueling Bandits: A Survey. Journal of Machine Learning Research, 22(7), 1-108.\n\nMoreover, there are some missing references (lines 166-167) regarding the multiple arm comparison for the regret minimization objective (see Chapter 6 of Bengs et al. (2021)).\n\n## Experimental study \n\nThe experimental study leaves room for improvement. First, the considered competing algorithms BTM and RUCB are out of date and Double Thompson Sampling and Self-Sparring are currently the state-of-art (together with the considered RMED). Next, it is a bit doubtful that the elimination strategy is changed for the experiments, although the theoretical analysis uses a Hoeffding-based elimination strategy. While I agree with the author’s statement that *the theoretical guarantee will continue to hold*, it is nevertheless something that needs to be shown. Thus, the authors should include the original algorithm in the experiments and call the one using KL elimination differently in the experiments. Finally, it would be nice if the authors could comment on whether the data sets satisfy SST or STI, i.e., the assumptions needed for SCOMP and SCOMP2, and also report the number of batches used by C2B and SCOMP2.\n\nNB: There is also a quite recent Python package for dueling bandits: https://duelpy.gitlab.io/duelpy/index.html\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept