Identification of the Generalized Condorcet Winner in Multi-dueling Bandits
Authors: Björn Haddenhorst
Viktor Bengs
Eyke Hüllermeier
Venue: NeurIPS 2021 Poster (2021)
Keywords: Best arm identification
Condorcet Winner
Dvoretzky–Kiefer–Wolfowitz inequality
Multi-armed Bandits
Preference Learning

Abstract: The reliable identification of the “best” arm while keeping the sample complexity as low as possible is a common task in the field of multi-armed bandits. In the multi-dueling variant of multi-armed bandits, where feedback is provided in the form of a winning arm among as set of k chosen ones, a reasonable notion of best arm is the generalized Condorcet winner (GCW). The latter is an the arm that has the greatest probability of being the winner in each subset containing it. In this paper, we derive lower bounds on the sample complexity for the task of identifying the GCW under various assumptions. As a by-product, our lower bound results provide new insights for the special case of dueling bandits (k = 2). We propose the Dvoretzky–Kiefer–Wolfowitz tournament (DKWT) algorithm, which we prove to be nearly optimal. In a numerical study, we show that DKWT empirically outperforms current state-of-the-art algorithms, even in the special case of dueling bandits or under a Plackett-Luce assumption on the feedback mechanism.


Identification of the Generalized Condorcet Winner in Multi-dueling Bandits
Björn Haddenhorst
Viktor Bengs Institute of Informatics
Department of Computer Science
Paderborn University Paderborn, Germany
University of Munich (LMU)
Munich, Germany viktor. www.seeng.mmmmmm.m
bjo bjoernha@mail. upb.de
Eyke Hüllermeier
Institute of Informatics
University of Munich (LMU)
Munich, Germany eyke@ifi. leu.de
Abstract
The reliable identification the "best" arm while keeping the sample complexity as low as possible is a common task in the field of multi-armed bandits. In the multi-dueling variant of multi-armed bandits, where feedback is provided in the form of winning arm among set of & chosen ones, reasonable notion of best arm is the generalized Condorcet winner (GCW). The latter is an arm that has the greatest probability of being the winner in each subset containing it. In this paper, we derive lower bounds on the sample complexity for the task of identifying the GCW under various assumptions. As by by-product, our lower bound results provide new insights for the special case of dueling bandits (A = 2). We propose the Dvoretzky- Kiirek--KKeffrooloooeo to be nearly optimal. a numerical study, we show that DKWT empirically outperforms current state-of-the-ant algorithms, even in the special case of dueling bandits or under Plackett-Luce assumption on the feedback mechanism.
tournament (DKWT) algorithm, which we prove
Introduction
The standard multi-armed bandit (MAB) problem describes a sequential decision scenario, which one of finitely many choice alternatives must be selected in each time step, resulting in the observation of a numerical reward of stochastic nature. One important and extensively studied variant of the MAB setting is the dueling bandits problem, where duel consisting of two arms is chosen in each time step and one of the duelling arms is observed as the winner [4] Recently, the multi-dueling bandits setting has been introduced 77 40 31] generalization with multiple practically relevant applications, such as algorithm confi configuration 13 or online retrieval evaluation (36). Instead of pairs of arms, in this generalization step. These arms compete against each other and determine a single winner, which is observed as feedback by the learner. The outcomes of the mnulti-)duehl in the (multi-)duellin bandit scenario are typically assumed to be of time-stationary stochastic nature in the sense that whenever arms a1...., ag compete against each other, then a; wins with some underlying (unknown) ground-truth probability P P(a:lfa.....,a ..))).
consisting of k: > arms be chosen in each time
One often targeted learning task in the context of multi- armed bandits and its variants is the problem of identifying the best among all arms. While for standard MABs, the canonical definition of the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

"best arm" is the arm with highest expected reward, the picture is less clear for its variants. In the realm of dueling bandits, any arm that is likely to win (i.e.. with probability > 1/2) in each duel against another arm is called the Condorcet winner (CW). This notion dates back to the 18th century [8] and also appears in the social choice literature 16 17,, where the data typically assumed to be available in the form of a list containing total rankings over all alternatives from different voters. In practice, the Condorcet winner does not necessarily exist due to the presence of preferential cycles in the probabilistic model in the sense that a is likely to win against aj. aj against ag. and dg against problem, this issue is overcome in
a, For the theoretical analysis of the pest-arm-identifcaatt the literature either by the consideration of alternative optimality concepts such as Borda winner or Copeland winner, which are guaranteed to exist, or by simply assuming the existence of the CW.
In this paper, we focus on finding a generalized variant of the CW in the multi-dueling bandits setting under the assumption that it exists. There have been several suggestions for generalizations of the CW in social choice. For example, weighted variant is introduced in 30,, where the weights control the relevance given to the ranking positions of the alternatives, while [55] the notion of k-winner is defined as alternative that (in some appropriate sense) outperforms all other arms among any k alternatives, In contrast to our work, these papers focus on offline learning tasks and suppose full rankings over all alternatives to be given. In this paper, we adapt the notion of generalized Condorcet winner (GCW) as in [ i.e., a GCW is an arm ag that outperforms each arm aj in every query set S containing both o, and aj. in the sense that P(a.)S) P(a,IS).
Regarding the dueling bandits setting as the multi-dueling setting where the allowed multi-duels S are exactly those with |S| 2. the GCW is indeed a generalization of the Condorcet winner. We analyze the sample complexity of (probabilistic) algorithms that are able to identify the GCW with high probability under the assumption of mere existence as well as more restrictive assumptions. We provide upper and lower bounds for this task, which depend on the desired confidence, the total number m of alternatives, the size k of allowed query sets as well the underlying unknown preference probabilities (aa
We start in Section 2 with brief literature overview on the multi multi-dueling bandits scenario. Section 3 introduces the basic formalism and a precise definition of the considered GCW identification problem. It also gives a rough, simplified overview of the sample complexity bounds obtained in this paper. In Section 4 we discuss the special case m = k; which the GCW identification problem essentially boils down to the task of finding the mode of categorical distribution. We provide solutions to this problem and prove their sample complexity to be optimal up to logarithmic factors in the worst-case sense. Section several upper bounds. In Section 7 we empirically compare the algorithms discussed before, prior to concluding in Section [ For the sake of convenience, detailed proofs of all theoretical results presented in the paper are deferred to the supplemental material.
(5 focuses
lower bounds for the general case m 2 k. and in Section 6 we discuss
2 Related Work
Initially, the multi-dueling bandit problem was studied intensively in the case of pairs as actions of the learner, which is also better known as dueling bandits [42.. The extension to the scenario considered in this paper, where more general sets as pairs of arms are selectable as an action, has been the focus of recent work. Part of these works model the feedback process by essentially tracing back to the dueling bandit case 7 40 31) The majority of papers, however, assume latent utility values for the arms and model the feedback process using a random utility model (RUM) 3 based on these utility values. Thanks to the latent utility values, an ordering of the arms is obtained quite naturally, which in turn makes it casy to define an objective such as the optimal arm or the top-k arms. Under these assumptions, the PB-MAB problem was investigated with respect to various performance metrics such as the regret B2 5 T
or the sampling complexity in an (c, 6)-PAC setting 33 35)
In [ different approach is taken by generalizing the concept for the naturally optimal arm in the dueling bandit case, namely the Condorcet winner (CW), under the term generalized Condorcet winner (GCW). The optimal arm defined in this way coincides with the optimal arm if latent utility values for the arms and a RUM for the feedback process are assumed. While in [ the problem for finding this GCW is investigated in regret minimization scenario, we are interested in the minimum sampling complexity. In light of this, the work by (35) is the most related to ours, although the authors assume PL model (a special case of RUM).

---

If we restrict the learner's 's actions to pairs of arms in our more general setting, i.c., the dueling bandits case, the GCW and the CW coincide. This special case of our problem setting has been dealt with by 266
20 and 29
Finally, it remains to mention that there are number of similar problem scenarios, namely the Stochastic click model (SCM) [43], the dynamic assortment problem (DAS) [9] and the best-of-k- bandits [39]. However, all these scenarios take into account other specific aspects in the modelling such as the order of the arms in the action subset (SCM), known revenues associated with the arms (DAS) or a so-called "no-choice option" " (all three). Accordingly, these problem scenarios are fundamentally different from our learning scenario (see also Sec. 6.6 in 4 for a more detailed discussion). The same is true for combinatorial bandits [IO], which also allow subsets of arms as actions, but differ fundamentally in the nature of feedback (quantitative vs. qualitative feedback).
3
The GCW Identification Problem
For adequately stating our results, we introduce in the following some basic terminology and notations used throghout this paper. For the sake of convenience, Table summarizes the most frequently used notations.
3.1 The Notion of GCW
If not explicitly stated otherwise, we suppose throughout the paper the total number of arms m, the
query set size k E .2...., m). desired confidence 1 Y E (0, 1) and complexity parameter E (0, 1) to be arbitrary but fixed. We write [m]] = (l....,m, m) and [m]] == {S C [mo] [S| = k).
Parameter spaces of categorical distributions. For any subset of size k, i.c., S E [m],. define As == {p- = (pj)jes E [0, 1||s| Ejes = 1} as the set of all possible parameters for categorical random variable X Cat((p))ees), i.e., PPX = j) = Pj for any j E S. For p As, we write mode(p) == arg jes s Pj and in case [mode(p)] = 1 we denote by mode(p) - with a slight abuse of notation also the unique element in mode(p). Let us define for E (0, 1] the sets
A $
{p E As Bi E s.t. pr 2 max Ps + h).
and with this A-- = U 1) 3/. These sets are nested in the sense that A C A + h N.
p As is fixed, the value h(p) == max(h E [0. 1] p A is well-defined and have p E A iff h < h(p). Obviously, the equivalence [mode(p)) = +> p E A holds for all E As.
SE(m], S E im]a. is called probability model (short: PM) [m]k. We write PME for the set of all probability models on [m]] and define the following subsets of PME
Probability models on [m/a- A family P = (P { of parameters P(-IS) As.
PME (A0) (P- (P(I SEmmla V E [m]] P(- E AS).
PM (Aa) = (P- = (P((1 SE(M)] VS E [m] P(.(S) E A }.
PM (PI.) ==
sE(]] | E (0, oT) [m]a P(i = 0//2 9
Note that PMM (PI) denotes the set of all probability models P consistent with Plackett-Luce
(PL) model (27 23 Let h(P) = ca (P E PM (A*)) minse(mj, h-P((1 then
is easy to see that P E PME h) iff h < (P))
An element i E [m] is called generalized Condorcet Winner (short: GCW) of P if
VS E [m] with i S,Vj E S P(i] P P(j
and we write GCW(P) for the set of all GCWs of P. With this, we define the following subsets of PMT related to the concept of the GCW:
PM (3GCW) = (P- = (P(-1 () SE[m),
GCW(P) * 0).
PM (BGCW") = (P- = -PP-1 SE(m)x
[GC((P) - 1}.
(EMGCW)) = (P(()1)))sE(m)) Bi:VS E [m],. E P([ - | 2 h).
3

---

Table 1: A list of frequently used notation
m
the total number of arms the query set size
k
the desired error rate bound the set (I,..., m)
m
mik
the set of all subsets of [m]] of size indicator function, which is if a true statement and 0 otherwise; also denoted by 1 (44
A
S
an element from [m]]
PME
set of all parameters [P(-IS) S [0.1] with Ejes P(IS) = 1 VS [m]]
PME
the set all P. which fulfill the condition(s) X the set PM (X) n PMM (Y)
P (XAY)
P
an clement from PM set of all GCWs of P: if [G) = it denotes the only element in GCW (P)
GCW(P)
A A", PL, 3GCW, set of all 3,C,,,,,,GGT 3AGCW and 3GCW", ef. Section 3.1 (wi)es E [o, 11181 with Eie(m ws here, S finite
As
A
set of all As, for which A resp. Ajk
exists with Vj E S [3] ws my h
A..A%
element from Ag an element from As for some [m]] arg max Pt for p (pI..... ........ ..P)): term mode(P (- defined accordingly max(h E [0, 1] Jp At) for p Ak
mode(p)
hp))
(P))
max (h E [o, 1] IP PMMMM (A*) algorithm
A
D(4)
the return value of .A
T
the sample complexity of A, i.e. the number of samples observed by A before termination An algorithm A called with the parameters .1,...,
A(z 21)
(X)
Problem of finding for any P E PM (X) with error prob. S y the GCW, cf. Def. 3.1
Clearly, it holds that PM = UNSo PMTT and every probability model P E PMMM(3GCW) has at least one GCW, while for probability model P GCW is unique.
the
The figure on the right illustrates the relationships between the introduced subsets of PM For the sake of convenience, we write simply (X) instead of PM (X), where
(3GCW)
(PL)
(RGOW")
(A))
X E (EGCW, EAGCW, A AA,AA,P)) PLJ.
(3&GCW)
(A*)
This convention will be used several times in the course of the paper.
3.2 Problem Formulation
We are interested in algorithms A able find the GCW of some P (P( which is unknown and only observable via sampling from P. More precisely, we suppose that at each time step / E N, such an algorithm A is allowed to choose one query set S, E [m]]e. for which it then observes a sample S; 3 X, ~ CPt(P(. St)). At some time, AA may decide to make no more queries and output prediction ((A) [m] for the GCW. We write T E NU {oo} for the sample complexity A, i.c., the total number of queries made by A before termination. Note that both D(A) and T-A are random variables w.r.t. the sigma-algebra generated by the stochastic feedback mechanism. We write Pp for the probability measure corresponding to the stochastic feedback mechanism if the unknown ground-truth PM is given by P.
PMM
Definition 3.1 (The GCW Identification Problem). Let (X) be any of the assumptions from above with PM mm (X) C PM (EGCW), and let 7 E (0, 1) be fixed. An algorithm A solves the problem Pm (X) if PP (D(A) GCW(P)) 2 - 7 holds for any P PM)
3.3 Overview of Results
In this paper, we provide several upper and lower sample complexity bounds for solutions to the GCW identification problem (x) under different assumptions (X). We start in Section with

---

the discussion of the special case m k, in which pk- (X) can simply be thought of as finding the mode of categorical distribution [k]. Sections 5 and we discuss lower and upper bounds for the general case m 2 k, respectively.
Table 2 summarizes the obtained worst-case sample complexity bounde of solutions to Par (X), where the worst-case is meant w.r.t PME (X A Y), for different choices of X and Y, and the Bachmann-Landie notations 2(-)) and (-) are to be understood w.r.t m, k. h and y In
addition, also provide instance-wiss bounds in Theorems 5.2 and E.
Table 2: Sample complexity bounds of solutions to (X)
(X)
(V)
Type
Asymptotic hounds
References
(PL)
(BAGCW)
in
52(
n3g (2
A) In !)
Thm
5.1
(A A A3GWW)
(A*)
in exp.
12 73
In 4)
Thm.
(PI. RGCW")
(BhGCW)
whhp
C
In( In +D
Thm.
(3GCW A
(A*)
w.h.p
m RAN
In 2 (la
(3kGCW A A
(3&GCW)
n.5.
In( 1)
Thm.
Due to PM. (A* AGCWW) & (M](EE) & (MGCW)) Thm. 5.2 implies in particular that any solution to Pk (EGCW) fulfills supPEpии(EиGOW Ep (TAA] E 92 m
EA² In(>=)))- As
Thm. 6. and Thm. 6.2 indicate that the bounds in Thm. 5.1 and Thm. 5.2 are asymptotically sharp up to logarithmic factors, the GCW identification problem seems to be easier under the PI. assumption by a factor 1/k + h.
4 The Single Bandit Case m = k
In this section, we address the problem P (X) for the special case h = m. For sake of convenience,
we abbreviate Ag == A and similarly A = A
j for any h E [0, 1]. Due to [k]s = {[K]), any probability model P E PM is completely characterized by (- and the GCW of P is simply mode(P ((])[K))) Since the latter always exists, we have PM C (EGCW).) Note that = (A9)
(EGCW") as well as PA (A*)) (BhGCW) are fulfilled trivially i.e.. we do not have to distinguish between the assumptions A and 3GCW resp. A and 3&GCW throughout this section. For the sake of convenience we will identify p = (P(-I[])) E PM with (pI..... pk) == (P(I[[A)),... ... P(k [k])) E Ak. Due to h(P) hu()), the set PM (A*) identified with A this way for any h [0, 1], and thus an algorithm A solves 2 for
[0, 1] iff it fulfills PP (D(A) (p)) 2 7 for any p E A
4.1 Lower Bounds
Based Wald's identity, the optimality of the sequential probability ratio test and result by 14 we are able to prove the following two results, each of which are proven in Section C In the appendix, we state with Prop. C.Ia more explicit but technical version of Prop. 4.1
Proposition 4.1. For any 70 E (0, 1/2) and ho E (0,1) there exists constant c(ho, 1o) > 0 with the following property: Whenever h (0, ho). 7 E (0, 70) and A is a solution to Pk- (A"), then
Vp E 4 Ep T 2c(ho, 7o) (h())) ((((p(((p))((1>))) In 11/x h).
In particular, sup Ep [T > 4c(ho, Yo)h -
Proposition 4.2. Let 7 E (0, 1/2) be fixed and suppose A is a solution to Ph (A"). Leep E AQ be arbitrary, == mode(p) and j == arg max max Pj- Then, the family {p (p(h)]se(0mppp)) C C defined via (p(h)); == (p.+p++h/a (p(h)); = (petr, -b0/2 and (p(h)); == for E [K] {i,j}
fulfills ph) E A as well as
lim limsupa o Epth) ( In 2 (1 (px pj) > 0.
Herr, "in exp." means in expectation, "w.h.p." means with prob. and "a.s." with prob. 1.
5

---

37 have recently proven result similar to Proposition 4.1 In contrast to theirs, our bound provides as additional information also the asymptotical behavior as k + oC. Moreover, our proof is based
on the optimality of the Sequential Probability Ratio Test 41 38 instead of measure-changing
argument
21
4.2 Upper Bounds and Further Prerequisites
To construct solution A (A"h,, we have to decide in a sequential manner at each time t, whether we want to make a further query S, E [K]a resulting in sample X₁ or to output an answer D(A) E [ As [k],- [[k],, we can only choose S: [k] in each time step t, upon which we observe as feedback X ~ Cat(p), i.e.. (X2 i) p; for any i E [R.] Having observed X1,..., X,, a straightforward idea for a prediction D(A) would be to use the mode of the empirical
distribution p := (oi,..., pk) given by p == = Ee [x==1) As the Dvoretzky-Kiefer Kiffeeffo----oiiizz
(DKW) inequality assures us that
P. (1 p11.0 > >6) 4e 422/2
holds for any > 0 (Lem. D.I), we can infer that P' close to p with high confidence for large values of t. Hence, if t is large enough, predicting the mode of p would be the correct prediction for mode(p) with high probability. In the following we show which choice of t is sufficient to assure a confidence 1 7
Let us first consider the case p E A It can shown that
(3i p: max Pj 2 and pi & max, pÿ) |1 pll 2 (h =)/2
holds for any h [0, 1), E E (-h, I. A and p E As (Lemma D.2) This result is optimal in the sense that the term (h e therein cannot be improved (Remark D33) Choosing e = 0 and p p
h/2 is necessary for mode(p') * mode Combining this with ① could simply query S; = [k] for T 1S1(4//)h-> - many times and return the mode of p" as the decision. This (non-sequential) strategy solves (A*) and terminates after exactly [8 In(4/7)h time steps (Proposition D.4h. Note that according to Prop. 4.1 this strategy is asymptotically optimal.
shows us that 1ip² - -pll>0
based on the DKW inequality,
Next, we intend to solve the more challenging problem Pf- (A"). Note that any solution to P (A) is also solution to Ph (AA* for any h > O, whence Prop. 4.1 shows that ph (A9) cannot be solved by any non-sequential algorithm, i..., one which decides a priori the number of samples observes. To construct a solution, make use of Alg. [ which also tackles the problem of finding the mode of p in a non-sequential manner but is allowed to return UNSURF as an indicator that it is not confident enough for its prediction. In other words, the algorithm is allowed to abstain from making a decision. Since
Vi: p. I max h
|p pll h.
holds for any > O. P E 3h and P E A (Lem. D.5 Alg. least 1 y the correct mode case p E 3h is fulfilled. The constraint p E A in the statement
1 can be shown to return with probability
above is sharp in the sense that we show in Lem. D.6 for any h 1/8) that
inf s
0
vp A A A As (Ai: p. < max Do - h = ||p
Pl1 2 h) } 3.
Algorithm 1 DKW codee-ddeniificttinn with abstention
Input: 7 E (0, 1), E (0, 1), access iid samples X, ~ Cat(p)
1: T t [8 (n4/(/4))
2: Observe samples X
XT
3: Calculate p" = (pT ...., P as Dr = + 1|x,=1), E [K]
4: Choose E mode(p"))
5: if pf. > maxj p h then return i*
6: else return UNSURE

---

Lemma 4.3. A == Alg. 1 initialized with parameters 7, h E (0, fulfills T = [8In(4/7)/h²),
Vp Ax (D(A) E [R:] and PD(A) < max Pÿ) S 7/
(2)
vp E A (DA)) E (mode(p); UNSURE)) 2 1 11119
(3)
Vp E A 3h (D(() = mode(p)) 21-7
(4)
Lemma 4.3 (proven in Section D) reveals that Alg. I has low failure rate (2) by appropriate choice of y. while in turn by an appropriate choice of ht namely h S h/(p), the correct decision will be returned 4 with high probability. However, there two problems arising: Alg. [ can also abstain from making a decision (3) and more importantly, the value of h(p) is unknown. As a remedy, we could Alg-[ successively with appropriately decreasing choices for y and h until (real) decision returned. This approach is followed by Alg. and the following proposition shows that is indeed
solution to "Pa (A"): its proof is an adaptation of Lem. 11 in 28 and given in Section D
Algorithm 2 DKW mode-identiifcation Solution to P (A
Input: y E (0, 1), sample access to Cat(p)
Initialization: A Alg.
1, Vr EN: 7r ==
by hy = 2---1
fcodback <- UNSURE
2: while feedback is UNSURE do
3: feedback +- A(7s, ha, sample access to Cat(
4: 8
5: return feedback
Proposition 4.4. A = Alg. 2 initialized with the parameter 7 E (0, solves Ph: s.t. PP(TT < 00)= 1 and (D((A) modc(p) and T I fo(r, (p))) - for any pe E 2h where to(7, h) is mon. decr. w.r.t. h with to(>, h) E O (h In - 1)).
The sample complexity of in Proposition 4.4 improves upon the existing alternative solution for (A9) (A9) bound is constant instead of increasing in &t and second, the dependence on the hardness parameter
in Theorem 2 in (37 with respect to two essential aspects: First, its sample complexity
hp)) is (2 h(p)
instead (p) In h((p)
5 Lower Bounds on the General GCW Identification Problem
In this section we provide lower sample complexity bounds for solutions to the GCW identification problem for arbitrary as Thm. B. I in the appendix.
k m. The following theorem is based result by (35), which we state
Theorem 5.1. Any solution A to PE (PL) fulfills
SIDPEPM/(PLASACOO) Ep [T>]] Q (m(1//+4)) (111/2//(w62))
(5)
One of the key ingredients for proving Thm. B. and thus for Thm. 5. is change-of-measun argument by (21). By means of the latter technique, we are also able to show the following instance- based as well as worst-case lower bounds for any solution to pm. (A* A 3GCW), which is proven in Section F
Theorem 5.2. Suppose A solves pm A EGCW) and ler P E PMF ^ 3GCW) be arbitrary with minse(m]a minjes P P(JSS > O. For S E [m] write ms == modo(P((IS)) and for
any E S {ms} define p!l (-1S) E As via
[l = P(ms|S), (ms|S) = P(4S), S ((])) P(]S).
Then,
Ep [T~]= 2 ((1224))))/((--1 Σ Liemm minselm)u.tes///e ( (s)
where (-1S), PM (-1S) denotes the Kolliback-eeibles divergence between categorical dis- tributions X ~ Cat(P(()SS) and Y ~ Cat(P (-[S). Moreover, have
SUPPEPMM Ep [T]] > m(1 In((2.47) (1)a)))))--/1/1))
7

---

In the special case of dueling bandits (k: = 2), the Instance-dependee lower bound is a novel result actually leads to a slightly larger worst-case lower bound than the worst-case bound Theorem 5.2 for the dueling bandit case (Cor. F.4) For k > 3. the worst-case bound in Theorem 5.2 is not consequence of the instance- wise version (Rem. (-3). instead it requires more involved proof than
the latter. For m k. the instance- wise lower bound underlying Prop. 4.1 is apparently larger than that of Thm. 5.2 (Rem. F.5). The reason is that the proof for the instance- wise bound in Theorem 5.2
is tailored to the problem class PME (A A3GCW) and consequently has to deal with combinatorial issues arising in case kt < m.
Upper Bounds on the General GCW Identification Problem
algorithm is introduced, which an algorithm able identify the GCW under the Plackett- assumption with (up to logarithmic terms) optimal instance-wise sample complexity, see Section B By translating the sample complexity result of PAC- WRAPPER into our setting, we obtain the following result (see Section B for its proof), which is also by Thm. 5.1 suggested to be optimal up to logarithmic factors.
In 35] the
Theorem 6.1. There exists a solation A P "(P 3GCW*) s.I.
(PLEEMMMCLLA (PLA3KGOW) Pp (D(A) E GCW(P) and T S hi, holds with t' m, k) O (m<1)4+h) (n(k/y (n/////)))))
7)) 2 1-7
Algorithm 3 DVORETZKY- WALEEEEERWWLLOOOTTTTTOOOAAAAAA
Solution to PTT (EGCW^A")
Input: k, m E 7 E (0, 1), sample access to P = (P(1)S)]sE[ml Initialization: A Alg. choose S1 [m]] arbitrary, Fi + [m]. 7 +- mm/[k-]]]
S, candidates in round 8, Fg remaining elements in round 8, i, output of A in round do
1: while s S m
2:
is < A-'' sample access P(-SS))
3:
F.41 < F. S.
4:
Write Fs+1 -1
5:
if [|s+1l < k then Fix distinct +1 $ E [m] Pat1-
6:
7:
S f- (1.,1...... 1x-1
8:
8-8 8-8+1
9: i, + -A((', sample access to P(-(S.)
return
Next, we consider the problem class (3GCW A A"), for which we propose the DVORET- KIEFRREFER- -WOFERRR- TOURNAMENT (DKWT) algorithm (see Alg. B.. DKWT a simple round- based procedure eliminating in each round those arms from a candidate set of possible GCWs that have been discarded by Alg. 2 with high confidence being the GCW. In the following theorem we derive theoretical guarantees for DKWT, while more sophisticated sample complexity bound is provided in Thm. E.T
Theorem 6.2. A DKWT initialized with the parameter 7 (0, 1) solves PmT (3GGWW A s.f.
Pp (D(A) E GCW(P) and A S ('(())), m, k, 7))
holds for all P E PMP A A with T' m. k, 7) E O kR
In
TE
In In 2))
The result stated in Table for (X) (3GCW A A and (Y) = (A)) follows from this by noting that h(P) > h holds for any P P (3KGOW A A)). Regarding Prop. 4.2 the additional factor
Aoo far, existing lower sample complexity bounds for solutions to P (A 3GCW) are either restricted to worst-case scenarios [6] or to the special case where P belongs to Thurstone model 29 a Plackett-Lure model (35).
8

---

Table 3: Comparison of DKWT with (PW) on 0 (1, 0.6,8, 0.4, 0.2)
T
Accuracy
DKWT
DKWT
PW
44293 (3095.6) .))
1631668198 (1153661392.0) 0)
1.0
1.0
32427 (2516.2)
263543687 (127401593.7)
1.0
1.0
In in the upper bounds from Thm. 6.1 and Thm. 6.2 appears indispensable. Since P PME (PLA EGCW") & PM (3GCW A A)) and PM A =GCW*) I PMMTTSGCNN A A hold, a solution to Pir (PLA3GCW") is in general not comparable with a solution to (3GGW ie., neither Thm. 6.1 nor Thm. 6.2 implies the other one.
Replacing 3GCW A with the more restrictive assumption 3AGCW A (as an assumption on P) makes the GCW identification task much easier. This is similar to the case of (A*) and (42) discussed in Section 4.2 For (EMGCW A A we can modify Alg. in order to incorporate the knowledge of h as tollows: choose in round s query set S. C F. (filedd up with F31 FF|- k further elements from [m]] \ Fs if F&5l k) and execute Alg. 1 with parameters A [m/(k-IJ and sample access to P P(-(S)). In case Alg. returns as decision an element E S.
we let Fa+1 F, (S. {z)), and otherwise Fa+1 F.. Then proceed with the next round 8 + 1. We repeat this procedure until [Fa| = 1, and return the unique element in F. as the prediction for the GCW. In Sec. E we provide detailed pseudocode for this algorithm (Alg. (5) and show that it indeed solves "r (AhGCW A A with the guarantee that it terminates almost surely for
any P E
A A)) before some time t'mm, ki h, 7) E O (m (n((mm(()>>)((x222))) (see Thm. A look at Thm. 5.2 reveals that this solution to P (J/GCW A A") is asymptotically optimal
E.2
up to logarithmic factors in a worst-case sense w.r.t. PM. T (3hGGW A A²).
7 Empirical Evaluation
In the following, we present experimental results on the performance of our GCW identification solution M We restrict ourselves in the main paper to DKWT, which is our solution of the most general problem ( A)). Throughout all experiments, if not specified differently in the pseudocode, every choice of an element within a specific set made by DK WT is performed uniformly at random. All experiments were conducted on machine with an Intel CMre 17-4700MQ Processor, executing all experiments (including those in the supplemental material) with only one CPU core in use took less than 72 hours.
At first, we compare DKWT with PAC-WRAPPER (PW), which is the solution to PM in 335 underlying Thm. 6.1 and so far the only solution in the literature to the best of our knowledge for identifying the GCW multi multi-dueling bandits with an eтror probability at most 7. Table 3 shows the results of both algorithms when started on an instance P E PM (PL) with underlying PL --rrmmeterr
and
(L, 0.8, 0.6, 0.4, 0.2) and 7 0.05, for different values of k. The observed termination time TAA the corresponding standard error (in brackets) and the accuracy are averaged over 10 repetitions.
Both algorithms achieve the desired accuracy 2 95% in every case, but DKWT requires far less samples than PW to find the GCW. Further experiments in the appendix (cf. Section G demonstrate the superiority of DKWT over PW also for other values of m, 0 and 7, including the problem instances considered in [35] Note that the observed extremely large sample complexity of PW appears be consistent with the experimental results in (35) and is supposedly caused by multiple runs of a costly procedure PAC CEC-BBST-ITERR which does not exploit the DKW inequality but is rather based on applications of Chernoff's bound.
In the case & = 2, the GCW identification problem coincides with the Condorcet winner (CW) identification problem in dueling bandits. Thus, we can compare DK WT state-of-the solutions for finding the CW if it exists: SELECT (26). SEEBS (29 and EXPLOOR--HEEN VERIFY (EtV)
20 Formally, SELECT requires h (0, 1) parameter as it solves P (EGCW A A*),
1 Our implementation is provided htthttss///ggt thub com/ htmm//ooorrnaa/GGW...ooo iicatiniinniiiiiiiiiiiii
'We include SEEBS even though it techniqually requires P to fulfill strong stochastic transitivity and the stochastic triangle inequality, cf. Sec. G.2

---

Table 4: Comparison of DKWT, SEEBS and EXPLORE-THEN THEN-VEIIYY (E(V)
h
DKWT
SEEBS
ENV
0.20
6010 (293.2)
7305 (432.1)
8601 (589.2)
0.15
8874 (460.0) 0)
13393 (904.5)
11899 (986.9) 9)
0.10
15769 (1457.1)
19802 (1543.2)
260171 (210678.1)
0.05
31454
(4127.4)
36855 (3533.2)
156634 (1150033.)
10
0.20
14334
(492.8)
16956 (617.9)
26115 (969.2)
10
0.15
18563 (734.5)
27527 (1126.7)
32548 (2514.6)
0.10
33040 (1625.1)
47330 (2138.2)
68858 (11304.5)
10
0.05
78660 (6517.2)
83877 (5842.6)
220098 (92484.9)
while DKWT, SEEBS and ErV solve the more challenging problem P A A As consequence, we compare here only the latter three algorithms on probability models P sampled uniformly at random from PM (3GCW algorithms with the explicit value of h. We also compare SELECT with the three considered algorithms in Section G Without great surprise, it turns out that SELECT has much smaller sample complexity due to its advantage of knowing the explicit value of h.
(MMCC A A") for various values of h without providing these
Table 4 reports the observed sample complexities, together with the standard errors in brackets, obtained for 7 0.05 and different choices of m and h, the numbers are averaged over 100 repetitions. Every algorithm achieves an accuracy of in each case. DKWT clearly outperforms SEEBS and EtV in any case, which is consistent with similar results for larger values of m in the appendix. Overall, these results show that DK WT is also well suited for the dueling bandit case.
We complement our empirical study Section G.3 with a comparison of DKWT with Alg. Showwing that the latter outperforms the former in the case where h(P) is small and P E PM m. (an GCW A
A for some a priori known h > (PP..
8 Conclusion
We investigated the sample complexity required for identifying the generalized Condorcet winner (GCW) in multi-dueling bandits within a fixed confidence setting. We provided lower bound results, which as a special case yield a novel instance-wise lower sample complexity bound for identifying the Condorcet winner in the realm of dueling bandits. We introduced DVORETZKY- KIEFER-W SAFEER-WOLFOOR WOLFOWITZ TOURNAMENT (DKWT), an algorithmic solution to the GCW identification task with asymptotically nearly optimal worst-case sample complexity. In our experiments, DK WT outperformed competing state-of-the art algorithms, even in the special case ducling bandits. Last but not least, we pointed out that and to which extent incorporating Plackett-Luce assumption on the feedback mechanism makes the GCW identification problem asymptotically easier w.r.t. the worst-case required sample complexity.
There are several directions in which this work could be extended. First, one could investigate the GCW identification problem in the so-called probably approximately correct (PAC) setting and search not for the GCW but instead for an arm that outperforms any other arm only with some margin > 0. Secondly, one may generalize this problem to the identification of the GCW without assuming its existence, where one has to check on-the-fly whether a GCW exists, i.e., a testification (test and identify) problem in [19 in the dueling bandit case for the Condorcet Winner. Morcover, one may also extend our problem to the case where query sets up to size are allowed at each time step. This variant has already been discussed in regret minimization scenario 32 PAC setting 33
Acknowledgments and Disclosure of Funding
The authors gratefully acknowledge financial support by the German Research Foundation (DFG project number 31 317046553).
10

---

References
[1] A. Agarwal, N. Johnson, and S. Agarwal. Choice bandits. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pages 18399-18410, 2020.
[2] H. Bauer and R. B. Burckel. Probability Theory. De Gruyter Studies in Mathematics, De Gruyter, 1996.
[3] M. Ben-Akiva and M. Bierlaire. Discrete choice methods and their applications to short term travel decisions. In Handbook of transportation science, pages 5-33. Springer, 1999.
[4] V. Bengs, R. Busa-Fekete, learning with dueling bandits: A survey, Journal of Machine Learning Research, 22(7):1-108, 2021.
Mesaoudi Pauul,, and Hüllermeier. Preference- online
[5] V. Bengs and E. Hüllermeier. Preselection bandits. In Proceedings of International Conference on Machine Learning (ICML), pages 778-787, 2020.
[6] M. Braverman and E. Mossel. Noisy sorting without resampling. In Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 268-276, 2008
[7] B. Brost, Y. Seldin, I. J. Cox, and C. Lioma. Multi-dueling bandits and their application to online ranker evaluation. In Proceedings of ACM International Conference on Information and Knowledge Management (CIKM), pages 2161-2166 2016.
[8] J. A. N. Caritat. Essai sur l'application de I' l'analyse à la probabilité des décisions rendues à pluralité des voix. De I' l'Imprimerie royale, 1785.
[9] Caro and J. Gallien. Dynamic assortment with demand learning for seasonal consumer goods. Management Science, 53(2):276-291 2007.
[10] N. Cesa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 7865):140-1422,, 2012.
[11] X. Chen and Y. Wang. A note on a tight lower bound for capacitated MNL-bandit assortment selection models. Operations Research Letters, 46(5):534-5377 2018
[12] A. Dvoretzky, Kiefer, and J. Wolfowitz. Asymptotic minimax character the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27(3):642 669, 1956.
[13] A. El Mesaoudi -Puul, D. Weiß, Bengs, E. Hüllermeier, and K. Tierney. Pool-based realtime algorithm configuration: preselection bandit approach. In Proceedings of International Conference on Learning and Intelligent Optimization (LION), pages 216-232, 2020.
[14] R. H. Farrell. Asymptotic behavior of expected sample size in certain one sided tests. The Annals of Mathematical Statistics, 35(1):36-72, 1964.
[15] S. Ferguson. Mathematical Statisties: Decision Theoretic Approach. Probability and mathematical statistics. Academic Press, 1967.
[16] P. C. Fishbum. Paradoxes of voting. American Political Science Review, 68(2):537-546, 1974.
[17] P. C. Fishburn and W. V. Gehrlein. Borda's rule, positional voting, and Condorcet's simple majority principle. Public Choice, 28:79-88 88, 1976.
[18] A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In Proceedings of Annual Conference Learning Theory (COLT), pages 998-1027, 2016.
[19] B. Haddenhorst, V. Bengs, J. Brandt, and E. Hüllermeier. Testification condorcet winners in ducling bandits. In Proceedings of Conference on Uncertainty in Artificial Intelligence ( (UAI), 2021.
[20] 7. Karnin. Verification based solution for structured MAB problems. In Proceedings of Advances in Neural Information Processing Systems (NIPS), pages 145-153, 2016.

---

[21] E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
[22] M. R. Kosorok. Introduction to Empirical Processes and Semiparametric Inference. Springer, New York, USA, 2008
[23] R. D. Luce. Individual Choice Behavior: A Theoretical Analysis. Wiley, 1959.
[24] P. Massart. The tight constant in the Dooretkyy-ieefe--Wolfvvii inequality, The Annals of Probability, 18(3):1269 1283, 1990.
[25] A. Meyers, M. E. Orrison, J. Townsend, S. Wolff, and A. Wu. Generalized Condorcet winners. Social Choice and Welfare, 43(1):11-27, 2014
[26] S. Mohajer, C. Suh, and A. Elmahdy, Active learning for top-k rank aggregation from noisy comparisons. In Proceedings of International Conference on Machine Learning (ICML), pages 2488 2497,2447,22 2017.
[27] R. I. Plackett. The analysis of permutations. Journal of the Royal Statistical Society. Series C (Applied Statistics), 24(1) (5(1)19932000 1975.
[28] W. Ren, J. Liu, and N. B. Shroff. On sample complexity upper and lower bounds for exact ranking from noisy comparisons. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pages 10014-10024, 2019.
[29] W. Ren, Liu, and N. B. Shroff. The sample complexity of best-k items selection from pairwise comparisons. In Proceedings of the International Conference on Machine Learning (ICML), pages 8051-8077 2020.
[30] D. G. Saari. Symmetry extensions of "neutrality" I: Advantage to the Condorcet loser. Social Choice and Welfare, 9())307-336, 1992.
[31] A. Saha and A. Gopalan. Battle of bandits. Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI), 2018
[32] A. Saha and A. Gopalan. Combinatorial bandits with relative feedback. In Advances in Neural Information Processing Systems (NeurIPS), pages 983-993, 2019.
[33] A. Saha and A. Gopalan. PAC Battling Bandits in the Plackett-Luce Model. In Proceedings of the International Conference on Algorithmic Learning Theory (ALT), pages 700-737, 2019.
[34] A. Saha and A. Gopalan. Best-item learning in random utility models with subset choices. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pages 4281 42912,11111 2020.
[35] A. Saha and A. Gopalan. From PAC to instance-optimal sample complexity in the Plackett- Luce model. In Proceedings of International Conference on Machine Learning (ICML), pages 8367-8376, 2020.
[36] A. Schuth, H. Oosterhuis, S. Whiteson, and M. de Rijke. Multileave gradient descent for fast online learning to rank. In Proceedings of ACM International Conference on Web Search and Data Mining (WSDM), page 457-466, 2016.
[37] D. Shah, Choudhury, N. Karamchandani, and A. Gopalan. Sequential mode estimation with oracle queries. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), volume 34, pages 5644-5651 2020.
[38] D. Siegmund. Sequential Analysis: Tests and Confidence Intervals. Springer Series in Statistics. Springer, 1985.
[39] M. Simchowitz, K. Jamieson, and B. Recht. Best-of-k bandits. In Proceedings of Annual Conference on Learning Theory (COLT), pages 1449- 2016.
[40] Y. Sui, V. Zhuang, J. W. Burdick, and Y. Yue. Multi-dueling bandits with dependent arms. In Proceedings of Conference Uncertainty in Artificial Intelligence (UAI), 2017.
12

---

[41] A. Wald and J. Wolfowitz. Optimum character of the sequential probability ratio test. The Annals of Mathematical Statistics, 19(3):26-339, 1948.
[42] Y. Yue and T. Joachims, Beat the mean bandit. In Proceedings of International Conference on Machine Learning (ICML), pages 241-248, 2011.
[43] M. Zoghi, T. Tunys, M. Ghavamzadeh, B. Kveton, C. Szepesvari, and Z. Wen. Online learning to rank in stochastic click models. Proceedings of International Conference on Machine Learning (ICML), pages 4199 4208.. PMLR, 2017.
13


Reviews:
[{"review_id": "qTkCeYkkFpt", "reviewer": "Reviewer_RVxf", "summary": "This work studies the BAI problem in the multi-dueling bandits. \nIt proposes algorithms with theoretical guarantee and provides related lower bounds.\nThere are detailed comparisons to existing works.\nMoreover, it compare the proposed algorithm with other existing algorithms numerically.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In general, the paper is well organized.\nIt involves rich amount of results and the amount of notations is a bit heavy. It would be easier for the readers to understand if there can be a table to compare all the upper and lower bounds.\n\nHowever, I have one major concern regarding the single bandit case $m=k$. What is the difference from this case to the standard multi-arm bandits --- the problem where the agent aims to find $1$ best arm among $m$ arms?\n\n\n\n=========\n\nThanks for the detailed response from the author(s). I have read them and all other discussions. Though I tend to remain my score, I am more favor to accept the paper for the time being.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is one suggestion for future work: if the query size can be different at different time step $t$, does the algorithm still work? Can there be any theoretical guarantee?", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "pBj4t0FR1GD", "reviewer": "Reviewer_NPR2", "summary": "This paper proposes the notion of a \"generalised Condorcet winner\"  (GCW) among contestants in a tournament (or candidates in an election). Every subset of contestants is associated with a probability distribution over the contestants in the subset; a GCW is the most probable choice in every subset. The authors propose a sampling algorithm for determining a GCW of a tournament with sufficiently high probability, and provide both lower and upper bounds on the sample complexity. They consider special cases based on the number of contestants (m) and the size of the queried subset (k).", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In my opinion, the paper has two major weaknesses.\n\n1. The paper is premised on the assumption that the input tournament will indeed have a GCW--which, as the authors themselves acknowledge, is not guaranteed. It is not clear how the proposed algorithms will fare when run on a tournament that is without a GCW. Moreover, I do not find sufficient motivation for the query model (in which subsets of size k, k being arbitrary, are queried). The experiments provided are on a synthetic data set: they do not bring out the practical relevance of the query model and the algorithms--how they can benefit real-world applications. In short, I am unable to attribute any practical significance to this paper. It must be assessed solely for its theoretical merit.\n\n2. The paper is very hard to read. To be fair to the authors, the contents are technically dense: multiple problems, multiple parameters, and so on. And I do believe that their presentation is CORRECT. However, substantive portions of the paper contain dense notation interspersed with the commentary (starting with Section 3, wherein the problem is introduced), hindering CLARITY. I do not expect readers who are not already familiar with this problem and associated notation to be able to follow the paper.\n\nI have two specific questions for the authors.\n\n- The case of m = k, which amounts to mode estimation, has recently been studied in the following paper, which provides an algorithm, as well as upper and lower bounds that match up to a logarithmic factor.\n\nSequential Mode Estimation with Oracle Queries. Dhruti Shah, Tuhinangshu Choudhury, Nikhil Karamchandani, and Aditya Gopalan. In Proc. AAAI 2020, pp. 5644—5651. AAAI Press, 2020.\n\nCould the authors please compare/distinguish their own problem and bounds from the one in this paper? Also, to the best of my understanding, the authors have not shown experimental results related to mode estimation, and comparisons with other mode estimation algorithms. Why not?\n\n- Could the authors please explain the qualitative interpretation of the parameter h? I was under the impression while reading the paper that it was similar in spirit to the usual tolerance parameter epsilon in PAC formulations, but the authors seem to indicate in the conclusion that there is room for a \"margin\" epsilon over and above h.\n\nPost-rebuttal: Based on the authors' response and the discussion among the reviewers, I am now more positive about both the theoretical merit of the paper and its readability. I update my score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "DaMWxPPdmE", "reviewer": "Reviewer_1aHC", "summary": "This paper studies the problem of identifying the generalized condorcet winner (GCW) of the multi-dueling bandits. In multi-dueling bandits, each time the learner chooses a set with size $k$ to sample, and the sample returns an arm as the winner according to a distribution. The GCW is an arm that has the largest probability to win for any set that contains it. The focus on this problem is to find the sample complexity (aka number of samples needed) bounds for finding the GCW of a set of arms with confidence $1-\\gamma$. This problem can be viewed as a generalization of the \"top item selection from noisy comparisons\" problems or the \"best arm identification from dueling bandits\" problems. The model considered in this paper is very general and covers the popular  Plackett-Luce model as well as most of the cases that have been studied in the literature. \n\nUnder this general model, the authors developed the sample complexity upper bounds and lower bounds and the bounds are optimal up to at most a log factor. Numerical results also show the improvements of the proposed algorithm. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies a novel and interesting abstraction of the long existing problems of dueling bandits or ranking from comparisons, and this abstraction is general and reasonable enough to cover most of the cases that would be met in the literature and in practice. The algorithm proposed in this work is non-trivial, and its sample complexity upper bound is close enough to the lower bound with only a log factor. \n\nThe results of this work are good enough for an acceptance in my opinion. \n\nThe paper is well written, with good mathematical definitions as well as verbal explanations. \n\nThe results are significant for understanding the theoretical limits for best arm/item identification from multi-wise comparisons or multi-dueling bandits.\n\nTherefore, I tend to give a score 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are two main limitations in this work.\n\nFirst, the algorithm and the lower bounds only work for worst cases, while in practice, we may expect instance-wise bounds that depend on the actual gaps of differences of the winning probabilities. There are instances where some of the gaps are very small but most of the gaps are very large. For these instances, the bounds in this paper may be much larger than those utilizing the unequal gaps. \n\nSecond, for the PL model, it is interesting to discuss whether and to what degree the value of $k$ can influence the sample complexity if the parameters remain the same. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers came to consensus that the theoretical strength overtakes the concerns such as the assumption on the existence of GCW and the heaviness of the technical materials. I agree with these opinions and please sincerely address the concerns raised by the reviewers in the final version such as the relation with the previous work pointed out by NPR2. In particular, though I agree that the dense notation of this paper might be somewhat unavoidable, I expect that the authors make the best effort to improve the readability with more intuitions for them so that the paper becomes a good starting point for multi-dueling setting.
Decision: Accept (Poster)