Identification of the Generalized Condorcet Winner in Multi-dueling Bandits
Year: 2021

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 a set of k chosen ones, a 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 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.

heading: 1 Introduction
text: The standard multi-armed bandit (MAB) problem describes a sequential decision scenario, in 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 a 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 [7, 40, 31] as a generalization with multiple practically relevant applications, such as algorithm configuration [13] or online retrieval evaluation [36]. Instead of pairs of arms, in this generalization a set consisting of k ≥ 2 arms can be chosen in each time step. These arms compete against each other and determine a single winner, which is observed as feedback by the learner. The outcomes of the (multi-)duels in the (multi-)dueling bandit scenario are typically assumed to be of time-stationary stochastic nature in the sense that whenever arms a1, . . . , ak compete against each other, then ai wins with some underlying (unknown) ground-truth probability P(ai|{a1, . . . , ak}). 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 (NeurIPS 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 is 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 ai is likely to win against aj , aj against ak, and ak against ai. For the theoretical analysis of the best-arm-identification problem, this issue is overcome in 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, a weighted variant is introduced in [30], where the weights control the relevance given to the ranking positions of the alternatives, while in [25] the notion of a k-winner is defined as an 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 [1], i.e., a GCW is an arm ai that outperforms each arm aj in every query set S containing both ai and aj , in the sense that P(ai|S) ≥ P(aj |S). 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 as the underlying unknown preference probabilities P(ai|S). We start in Section 2 with a brief literature overview on the 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, in which the GCW identification problem essentially boils down to the task of finding the mode of a 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 5 focuses on lower bounds for the general case m ≥ k, and in Section 6, we discuss several upper bounds. In Section 7, we empirically compare the algorithms discussed before, prior to concluding in Section 8. For the sake of convenience, detailed proofs of all theoretical results presented in the paper are deferred to the supplemental material.

heading: 2 Related Work
text: 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 it 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 easy 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 [32, 5, 1] or the sampling complexity in an ( , δ)-PAC setting [33, 34, 35].
In [1] a 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 [1] the problem for finding this GCW is investigated in a 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 a PL model (a special case of a RUM).
If we restrict the learner’s actions to pairs of arms in our more general setting, i.e., the dueling bandits case, the GCW and the CW coincide. This special case of our problem setting has been dealt with by [26], [20] and [29].
Finally, it remains to mention that there are a number of similar problem scenarios, namely the Stochastic click model (SCM) [43], the dynamic assortment problem (DAS) [9] and the best-of-kbandits [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 [10], which also allow subsets of arms as actions, but differ fundamentally in the nature of feedback (quantitative vs. qualitative feedback).

heading: 3 The GCW Identification Problem
text: 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 1 summarizes the most frequently used notations.

heading: 3.1 The Notion of a GCW
text: If not explicitly stated otherwise, we suppose throughout the paper the total number of arms m, the query set size k ∈ {2, . . . ,m}, a desired confidence 1 − γ ∈ (0, 1) and a complexity parameter h ∈ (0, 1) to be arbitrary but fixed. We write [m] := {1, . . . ,m} and [m]k := {S ⊆ [m] | |S| = k}.
Parameter spaces of categorical distributions. For any subset of size k, i.e., S ∈ [m]k, define ∆S := {p = (pj)j∈S ∈ [0, 1]|S| | ∑ j∈S pj = 1} as the set of all possible parameters for a categorical random variable X ∼ Cat((pj)j∈S), i.e., P(X = j) = pj for any j ∈ S. For p ∈ ∆S , we write mode(p) := arg maxj∈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 h ∈ (0, 1] the sets
∆hS := { p ∈ ∆S | ∃i ∈ S s.t. pi ≥ maxj∈S\{i} pj + h } ,
and with this ∆0S := ⋃ h∈(0,1) ∆ h S . These sets are nested in the sense that ∆ h S ⊆ ∆h ′
S ⇔ h ≥ h′. If p ∈ ∆S is fixed, the value h(p) := max{h ∈ [0, 1] |p ∈ ∆hS} is well-defined and we have p ∈ ∆hS iff h ≤ h(p). Obviously, the equivalence |mode(p)| = 1⇔ p ∈ ∆0S holds for all p ∈ ∆S .
Probability models on [m]k. A family P = {P(· |S)}S∈[m]k of parameters P(· |S) ∈ ∆S , S ∈ [m]k, is called a probability model (short: PM) on [m]k. We write PMmk for the set of all probability models on [m]k and define the following subsets of PMmk :
PMmk (∆ 0) := {P = {P(· |S)}S∈[m]k ∣∣ ∀S ∈ [m]k : P(· |S) ∈ ∆0S}, PMmk (∆ h) := {P = {P(· |S)}S∈[m]k ∣∣ ∀S ∈ [m]k : P(· |S) ∈ ∆hS },
PMmk (PL) := {{P(· |S)}S∈[m]k ∣∣ ∃θ ∈ (0,∞)m ∀S ∈ [m]k : P(i |S) = θi/(∑j∈S θj)}.
Note that PMmk (PL) denotes the set of all probability models P consistent with a Plackett-Luce (PL) model [27, 23]. Let h(P) := maxh∈[0,1]{P ∈ PMmk (∆h)} = minS∈[m]k h(P(· |S)), then it is easy to see that P ∈ PMmk (∆h) iff h ≤ h(P). An element i ∈ [m] is called a generalized Condorcet Winner (short: GCW) of P if
∀S ∈ [m]k with i ∈ S, ∀j ∈ S : P(i |S)−P(j |S) ≥ 0 and we write GCW(P) for the set of all GCWs of P. With this, we define the following subsets of PMmk related to the concept of the GCW:
PMmk (∃GCW) := {P = {P(· |S)}S∈[m]k ∣∣GCW(P) 6= ∅},
PMmk (∃GCW ∗) := {P = {P(· |S)}S∈[m]k ∣∣ |GCW(P)| = 1}, PMmk (∃hGCW) := {{P(· |S)}S∈[m]k ∣∣ ∃i : ∀S ∈ [m]k, j ∈ S \ {i} : P(i |S)−P(j |S) ≥ h}.
Clearly, it holds that PMmk (∃GCW ∗) = ⋃ h>0 PM m k (∃hGCW) and every probability model P ∈ PMmk (∃GCW) has at least one GCW, while for a probability model P ∈ PMmk (∃GCW ∗) the GCW is unique.
(∃GCW)
(∃GCW∗)
(∃hGCW)
(PL)
(∆0)
(∆h)
The figure on the right illustrates the relationships between the introduced subsets of PMmk . For the sake of convenience, we write simply (X) instead of PMmk (X), where
X ∈ {∃GCW,∃GCW∗,∃hGCW,∆0,∆h,PL}. This convention will be used several times in the course of the paper.

heading: 3.2 Problem Formulation
text: We are interested in algorithms A able to find the GCW of some P = {P(· |S)}S∈[m]k ∈ PMmk , which is unknown and only observable via sampling from P. More precisely, we suppose that at each time step t ∈ N, such an algorithm A is allowed to choose one query set St ∈ [m]k, for which it then observes a sample St 3 Xt ∼ Cat(P(· |St)). At some time, A may decide to make no more queries and output a prediction D(A) ∈ [m] for the GCW. We write TA ∈ N ∪ {∞} for the sample complexity of A, i.e., the total number of queries made by A before termination. Note that both D(A) and TA 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. Definition 3.1 (The GCW Identification Problem). Let (X) be any of the assumptions from above with PMmk (X) ⊆ PMmk (∃GCW), and let γ ∈ (0, 1) be fixed. An algorithm A solves the problem Pm,γk (X) if PP ( D(A) ∈ GCW(P) ) ≥ 1− γ holds for any P ∈ PMmk (X).

heading: 3.3 Overview of Results
text: In this paper, we provide several upper and lower sample complexity bounds for solutions to the GCW identification problem Pm,γk (X) under different assumptions (X). We start in Section 4 with
the discussion of the special case m = k, in which Pk,γk (X) can simply be thought of as finding the mode of a categorical distribution on [k]. In Sections 5 and 6, we discuss lower and upper bounds for the general case m ≥ k, respectively. Table 2 summarizes the obtained worst-case sample complexity bounds1 of solutions to Pm,γk (X), where the worst-case is meant w.r.t. PMmk (X ∧ Y), for different choices of X and Y, and the Bachmann-Landau notations Ω(·) and O(·) are to be understood w.r.t. m, k, h−1 and γ−1. In addition, we also provide instance-wise bounds in Theorems 5.2 and E.1.
Due to PMmk (∆ h∧∃GCW) ( PMmk (∃hGCW) ( PMmk (∃GCW), Thm. 5.2 implies in particular that any solution A to Pm,γk (∃GCW) fulfills supP∈PMmk (∃hGCW) EP[T A] ∈ Ω( mkh2 ln(γ
−1)). As Thm. 6.1 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 PL assumption by a factor 1/k + h.

heading: 4 The Single Bandit Case m = k
text: In this section, we address the problem Pm,γk (X) for the special case k = m. For sake of convenience, we abbreviate ∆k := ∆[k] and similarly ∆hk := ∆ h [k] for any h ∈ [0, 1]. Due to [k]k = {[k]}, any probability model P ∈ PMkk is completely characterized by P(·|[k]) and the GCW of P is simply mode(P(·|[k])). Since the latter one always exists, we have PMkk ⊆ PMkk (∃GCW). Note that Pk,γk (∆0) = P k,γ k (∃GCW ∗) as well as Pk,γk (∆h) = P k,γ k (∃hGCW) are fulfilled trivially – i.e., we do not have to distinguish between the assumptions ∆0 and ∃GCW∗ resp. ∆h and ∃hGCW throughout this section. For the sake of convenience we will identify P = {P(·|[k])} ∈ PMkk with p := (p1, . . . , pk) := (P(1|[k]), . . . ,P(k|[k])) ∈ ∆k. Due to h(P) = h(p), the set PMkk (∆h) is identified with ∆hk this way for any h ∈ [0, 1], and thus an algorithm A solves P k,γ k (∆
h) for h ∈ [0, 1] iff it fulfills Pp(D(A) = mode(p)) ≥ 1− γ for any p ∈ ∆hk .

heading: 4.1 Lower Bounds
text: Based on Wald’s identity, the optimality of the sequential probability ratio test and a 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.1 a more explicit but technical version of Prop. 4.1.
Proposition 4.1. For any γ0 ∈ (0, 1/2) and h0 ∈ (0, 1) there exists a constant c(h0, γ0) > 0 with the following property: Whenever h ∈ (0, h0), γ ∈ (0, γ0) and A is a solution to Pk,γk (∆h), then
∀p ∈ ∆hk : Ep[TA] ≥ 2c(h0, γ0)(h(p))−2 ln(γ−1) (1/k + h) .
In particular, supp∈∆hk Ep[T A] ≥ 4c(h0, γ0)h−2 ln(γ−1).
Proposition 4.2. Let γ ∈ (0, 1/2) be fixed and suppose A is a solution to Pk,γk (∆0). Let p ∈ ∆0k be arbitrary, i := mode(p) and j := arg maxj∈[k]\{i} pj . Then, the family {p(h)}h∈(0,pi−pj) ⊆ ∆0k defined via (p(h))i := (pi+pj+h)/2, (p(h))j := (pi+pj−h)/2 and (p(h))l := pl for l ∈ [k] \ {i, j} fulfills p(h) ∈ ∆hk as well as
lim suph→ 0 Ep(h)[T A]/(h−2 ln lnh−1) ≥ (1− 2γ)(pi + pj) > 0.
1Here, “in exp.” means in expectation, “w.h.p.” means with prob. ≥ 1− γ and “a.s.” with prob. 1.
[37] have recently proven a result similar to Proposition 4.1. In contrast to theirs, our bound provides as additional information also the asymptotical behavior as k → ∞. Moreover, our proof is based on the optimality of the Sequential Probability Ratio Test [41, 38] instead of a measure-changing argument [21].

heading: 4.2 Upper Bounds and Further Prerequisites
text: To construct a solution A to Pk,γk (∆h), we have to decide in a sequential manner at each time t, whether we want to make a further query St ∈ [k]k resulting in a sample Xt or to output an answer D(A) ∈ [k]. As [k]k = {[k]}, we can only choose St = [k] in each time step t, upon which we observe as feedback Xt ∼ Cat(p), i.e., Pp(Xt = i) = pi for any i ∈ [k]. Having observed X1, . . . , Xt, a straightforward idea for a prediction D(A) would be to use the mode of the empirical distribution p̂t := (p̂t1, . . . , p̂ t k) given by p̂ t i := 1 t ∑ t′≤t 1{Xt=i}. As the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality assures us that
Pp (∣∣∣∣p̂t − p∣∣∣∣∞ > ε) ≤ 4e−tε2/2 (1)
holds for any ε > 0 (Lem. D.1), we can infer that p̂t is close to p with high confidence for large values of t. Hence, if t is large enough, predicting the mode of p̂t 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− γ. Let us first consider the case p ∈ ∆hk . It can be shown that
(∃i : p̃i −maxj 6=i p̃j ≥ ε and pi 6= maxj pj) ⇒ ||p̃− p||∞ ≥ (h+ ε)/2
holds for any h ∈ [0, 1], ε ∈ (−h, 1],p ∈ ∆hk and p̃ ∈ ∆k (Lemma D.2). This result is optimal in the sense that the term (h+ ε)/2 therein cannot be improved (Remark D.3). Choosing ε = 0 and p̃ = p̂t shows us that ||p̂t − p||∞ > h/2 is necessary for mode(p̂t) 6= mode(p). Combining this with (1) based on the DKW inequality, we could simply query St = [k] for T = d8 ln(4/γ)h−2e many times and return the mode of p̂T as the decision. This (non-sequential) strategy solves Pk,γk (∆h) and terminates after exactly d8 ln(4/γ)h−2e time steps (Proposition D.4). Note that according to Prop. 4.1, this strategy is asymptotically optimal.
Next, we intend to solve the more challenging problem Pk,γk (∆0). Note that any solution to P k,γ k (∆ 0) is also a solution to Pk,γk (∆h) for any h > 0, whence Prop. 4.1 shows that P k,γ k (∆
0) cannot be solved by any non-sequential algorithm, i.e., one which decides a priori the number of samples it observes. To construct a solution, we make use of Alg. 1, which also tackles the problem of finding the mode of p in a non-sequential manner but is allowed to return UNSURE 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
∀i : p̃i ≤ maxj 6=i p̃j + h ⇒ ||p− p̃||∞ ≥ h.
holds for any h > 0, p ∈ ∆3hk and p̃ ∈ ∆k (Lem. D.5), Alg. 1 can be shown to return with probability at least 1− γ the correct mode in case p ∈ ∆3hk is fulfilled. The constraint p ∈ ∆3hk in the statement above is sharp in the sense that we show in Lem. D.6 for any h ∈ (0, 1/8) that
inf { s > 0 ∣∣∣ ∀p ∈ ∆shk ∀p̃ ∈ ∆k : (∀i : p̃i ≤ maxj 6=i p̃j + h ⇒ ||p− p̃||∞ ≥ h)} = 3. Algorithm 1 DKW mode-identification with abstention Input: γ ∈ (0, 1), h ∈ (0, 1), access to iid samples Xt ∼ Cat(p)
1: T ← d8 ln(4/γ)/h2e 2: Observe samples X1, . . . , XT 3: Calculate p̂T = (p̂T1 , . . . , p̂ T k ) as p̂ T i := 1 T ∑T t=1 1{Xt=i}, i ∈ [k] 4: Choose i∗ ∈ mode(p̂T ) 5: if p̂Ti∗ > maxj 6=i∗ p̂Tj + h then return i∗ 6: else return UNSURE
Lemma 4.3. A := Alg. 1 initialized with parameters γ, h ∈ (0, 1) fulfills TA = d8 ln(4/γ)/h2e, ∀p ∈ ∆k : Pp(D(A) ∈ [k] and pD(A) < maxj∈[k] pj) ≤ γ, (2) ∀p ∈ ∆0k : Pp(D(A) ∈ {mode(p),UNSURE}) ≥ 1− γ, (3) ∀p ∈ ∆3hk : Pp(D(A) = mode(p)) ≥ 1− γ. (4)
Lemma 4.3 (proven in Section D) reveals that Alg. 1 has a low failure rate (2) by appropriate choice of γ, while in turn by an appropriate choice of h, namely h ≤ 13h(p), the correct decision will be returned (4) with high probability. However, there are two problems arising: Alg. 1 can also abstain from making a decision (3) and more importantly, the value of h(p) is unknown. As a remedy, we could run Alg. 1 successively with appropriately decreasing choices for γ and h until a (real) decision is returned. This approach is followed by Alg. 2 and the following proposition shows that it is indeed a solution to Pk,γk (∆0); its proof is an adaptation of Lem. 11 in [28] and given in Section D.
Algorithm 2 DKW mode-identification – Solution to Pk,γk (∆0) Input: γ ∈ (0, 1), sample access to Cat(p) Initialization: Ã := Alg. 1, s← 1, ∀r ∈ N : γr := 6γπ2r2 , hr := 2 −r−1
1: feedback← UNSURE 2: while feedback is UNSURE do 3: feedback← Ã(γs, hs, sample access to Cat(p)) 4: s← s+ 1 5: return feedback
Proposition 4.4. A := Alg. 2 initialized with the parameter γ ∈ (0, 1) solves Pk,γk (∆0) s.t. Pp(TA <∞) = 1 and Pp ( D(A) = mode(p) and TA ≤ t0(γ, h(p)) ) ≥ 1− γ
for any p ∈ ∆0k, where t0(γ, h) is mon. decr. w.r.t. h with t0(γ, h) ∈ O ( h−2 ( ln lnh−1 + ln γ−1 )) .
The sample complexity of A in Proposition 4.4 improves upon the existing alternative solution for Pk,γk (∆0) in Theorem 2 in [37] with respect to two essential aspects: First, its sample complexity bound is constant instead of increasing in k and second, the dependence on the hardness parameter h(p) is h(p)−2 ln lnh(p)−1 instead of h(p)−2 lnh(p)−1.

heading: 5 Lower Bounds on the General GCW Identification Problem
text: In this section we provide lower sample complexity bounds for solutions to the GCW identification problem for arbitrary 2 ≤ k ≤ m. The following theorem is based on a result by [35], which we state as Thm. B.1 in the appendix. Theorem 5.1. Any solution A to Pm,γk (PL) fulfills
supP∈PMmk (PL∧∃hGCW) EP [ TA ] ∈ Ω (m(1/k+h) ln(1/γ)/(kh2)) . (5)
One of the key ingredients for proving Thm. B.1 and thus for Thm. 5.1 is a change-of-measure argument by [21]. By means of the latter technique, we are also able to show the following instancebased as well as worst-case lower bounds for any solution to Pm,γk (∆h ∧ ∃GCW), which is proven in Section F. Theorem 5.2. Suppose A solves Pm,γk (∆h ∧ ∃GCW) and let P ∈ PMmk (∆h ∧ ∃GCW) be arbitrary with minS∈[m]k minj∈S P(j|S) > 0. For S ∈ [m]k write mS := mode(P(·|S)) and for any l ∈ S \ {mS} define P[l](·|S) ∈ ∆S via
P[l](l|S) := P(mS |S), P[l](mS |S) := P(l|S), ∀j ∈ S \ {l,mS} : P[l](j|S) := P(j|S). Then,
EP [ TA ] ≥ ln((2.4γ)−1)/(k−1) ∑ l∈[m]\{GCW(P)} minS∈[m]k:l∈S\{mS} 1/KL(P(·|S),P [l](·|S)),
where KL(P(·|S),P[l](·|S)) denotes the Kullback-Leibler divergence between two categorical distributions X ∼ Cat(P(·|S)) and Y ∼ Cat(P[l](·|S)). Moreover, we have
supP∈PMmk (∆h∧∃GCW) EP [ TA ] ≥ m(1−h2) ln((2.4γ)−1)/(4kh2).
In the special case of dueling bandits (k = 2), the instance-dependent lower bound is a novel result,2 it actually leads to a slightly larger worst-case lower bound than the worst-case bound in Theorem 5.2 for the dueling bandit case (Cor. F.4). For k ≥ 3, the worst-case bound in Theorem 5.2 is not a consequence of the instance-wise version (Rem. F.3), instead it requires a 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 PMmk (∆
h∧∃GCW) and consequently has to deal with combinatorial issues arising in case k < m.

heading: 6 Upper Bounds on the General GCW Identification Problem
text: In [35] the PAC-WRAPPER algorithm is introduced, which is an algorithm able to identify the GCW under the Plackett-Luce 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. Theorem 6.1. There exists a solution A to Pm,γk (PL ∧ ∃GCW ∗) s.t.
infP∈PMmk (PL∧∃hGCW) PP ( D(A) ∈ GCW(P) and TA ≤ t′(m,h, k, γ) ) ≥ 1− γ
holds with t′(h,m, k, γ) ∈ O (m(1/k+h) ln(k/γ ln(1/h))/(kh2)).
Algorithm 3 DVORETZKY–KIEFER–WOLFOWITZ TOURNAMENT – Solution toPm,γk (∃GCW∧∆0) Input: k,m ∈ N, γ ∈ (0, 1), sample access to P = {P(·|S)}S∈[m]k Initialization: Ã := Alg. 2, choose S1 ∈ [m]k arbitrary, F1 ← [m], γ′ ← γdm/(k−1)e , s← 1
. Ss : candidates in round s, Fs : remaining elements in round s, is : output of Ã in round s 1: while s ≤ d mk−1e − 1 do 2: is ← Ã(γ′, sample access to P(·|Ss)) 3: Fs+1 ← Fs \ Ss 4: Write Fs+1 = {j1, . . . , j|Fs+1|}. 5: if |Fs+1| < k then 6: Fix distinct j|Fs+1|+1, . . . , jk−1 ∈ [m] \ Fs+1. 7: Ss+1 ← {is, j1, . . . , jk−1} 8: s← s+ 1 9: is ← Ã(γ′, sample access to P(·|Ss))
10: return is
Next, we consider the problem class Pm,γk (∃GCW ∧ ∆0), for which we propose the DVORETZKY–KIEFER–WOLFOWITZ TOURNAMENT (DKWT) algorithm (see Alg. 3). DKWT is 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 as being the GCW. In the following theorem we derive theoretical guarantees for DKWT, while a more sophisticated sample complexity bound is provided in Thm. E.1. Theorem 6.2. A := DKWT initialized with the parameter γ ∈ (0, 1) solves Pm,γk (∃GCW ∧∆0) s.t.
PP ( D(A) ∈ GCW(P) and TA ≤ T ′(h(P),m, k, γ) ) ≥ 1− γ
holds for all P ∈ PMmk (∃GCW ∧∆0) with T ′(h,m, k, γ) ∈ O ( m kh2 ln ( m k ) ( ln ln 1h + ln 1 γ )) .
The result stated in Table 2 for (X) = (∃GCW ∧∆0) and (Y) = (∆h) follows from this by noting that h(P) ≥ h holds for any P ∈ PMmk (∃hGCW ∧∆h). Regarding Prop. 4.2, the additional factor
2So far, existing lower sample complexity bounds for solutions to Pm,γ2 (∆h ∧ ∃GCW) are either restricted to worst-case scenarios [6] or to the special case where P belongs to a Thurstone model [29] or a Plackett-Luce model [35].
ln lnh−1 in the upper bounds from Thm. 6.1 and Thm. 6.2 appears indispensable. Since PMmk (PL∧ ∃GCW∗) 6⊆ PMmk (∃GCW ∧ ∆0) and PMmk (PL ∧ ∃GCW
∗) 6⊆ PMmk (∃GCW ∧ ∆0) hold, a solution to Pm,γk (PL∧∃GCW
∗) is in general not comparable with a solution to Pm,γk (∃GCW∧∆0), i.e., neither Thm. 6.1 nor Thm. 6.2 implies the other one.
Replacing ∃GCW ∧ ∆0 with the more restrictive assumption ∃hGCW ∧ ∆0 (as an assumption on P) makes the GCW identification task much easier. This is similar to the case of Pk,γk (∆h) and Pk,γk (∆0) discussed in Section 4.2. For P m,γ k (∃hGCW ∧∆0) we can modify Alg. 3 in order to incorporate the knowledge of h as follows: choose in round s a query set Ss ⊆ Fs (filled up with |Fs| − k further elements from [m] \ Fs if |Fs| < k) and execute Alg. 1 with parameters h3 ,γ dm/(k−1)e and sample access to P(·|Ss). In case Alg. 1 returns as decision an element i ∈ Ss, we let Fs+1 = Fs \ (Ss \ {i}), and otherwise Fs+1 = Fs. Then we proceed with the next round s+ 1. We repeat this procedure until |Fs| = 1, and return the unique element in Fs as the prediction for the GCW. In Sec. E we provide detailed a pseudocode for this algorithm (Alg. 5) and show that it indeed solves Pm,γk (∃hGCW ∧∆0) with the guarantee that it terminates almost surely for any P ∈ PMmk (∃hGCW ∧∆0) before some time t′(m, k, h, γ) ∈ O (m ln(m/(kγ))/(kh2)) (see Thm. E.2). A look at Thm. 5.2 reveals that this solution to Pmk (∃hGCW ∧∆0) is asymptotically optimal up to logarithmic factors in a worst-case sense w.r.t. PMmk (∃hGCW ∧∆0).

heading: 7 Empirical Evaluation
text: In the following, we present experimental results on the performance of our GCW identification solution.3 We restrict ourselves in the main paper to DKWT, which is our solution of the most general problem Pm,γk (∃hGCW∧∆0). Throughout all experiments, if not specified differently in the pseudocode, every choice of an element within a specific set made by DKWT is performed uniformly at random. All experiments were conducted on a machine with an Intel® Core™ i7-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,γk (PL) in [35] underlying Thm. 6.1 and so far the only solution in the literature to the best of our knowledge for identifying the GCW in multi-dueling bandits with an error probability at most γ. Table 3 shows the results of both algorithms when started on an instance P ∈ PM5k (PL) with underlying PL-parameter θ = (1, 0.8, 0.6, 0.4, 0.2) and γ = 0.05, for different values of k. The observed termination time TA, the corresponding standard error (in brackets) and the accuracy are averaged over 10 repetitions.
Both algorithms achieve the desired accuracy ≥ 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, θ and γ, including the problem instances considered in [35]. Note that the observed extremely large sample complexity of PW appears to be consistent with the experimental results in [35] and is supposedly caused by multiple runs of a costly procedure PAC-BEST-ITEM, which does not exploit the DKW inequality but is rather based on applications of Chernoff’s bound.
In the case k = 2, the GCW identification problem coincides with the Condorcet winner (CW) identification problem in dueling bandits. Thus, we can compare DKWT to state-of-the art solutions for finding the CW if it exists: SELECT [26], SEEBS4 [29] and EXPLORE-THEN-VERIFY (EtV) [20]. Formally, SELECT requires h ∈ (0, 1) as a parameter as it solves Pm,γ2 (∃GCW ∧ ∆h),
3Our implementation is provided at https://github.com/bjoernhad/GCWidentification. 4We include SEEBS even though it techniqually requires P to fulfill strong stochastic transitivity and the
stochastic triangle inequality, cf. Sec. G.2.
while DKWT, SEEBS and EtV solve the more challenging problem Pm,γ2 (∃GCW ∧ ∆0). As a consequence, we compare here only the latter three algorithms on probability models P sampled uniformly at random from PMmk (∃GCW ∧ ∆h) for various values of h without providing these 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 a much smaller sample complexity due to its advantage of knowing the explicit value of h.
Table 4 reports the observed sample complexities, together with the standard errors in brackets, obtained for γ = 0.05 and different choices of m and h, the numbers are averaged over 100 repetitions. Every algorithm achieves an accuracy of 1 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 DKWT is also well suited for the dueling bandit case.
We complement our empirical study in Section G.3 with a comparison of DKWT with Alg. 5 showing that the latter outperforms the former in the case where h(P) is small and P ∈ PMm,γk (∃h′GCW ∧ ∆0) for some a priori known h′ > h(P).

heading: 8 Conclusion
text: 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 DVORETZKYKIEFER-WOLFOWITZ TOURNAMENT (DKWT), an algorithmic solution to the GCW identification task with asymptotically nearly optimal worst-case sample complexity. In our experiments, DKWT outperformed competing state-of-the art algorithms, even in the special case of dueling bandits. Last but not least, we pointed out that and to which extent incorporating a 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 as in [19] in the dueling bandit case for the Condorcet Winner. Moreover, one may also extend our problem to the case where query sets up to size k are allowed at each time step. This variant has already been discussed in a regret minimization scenario [32, 1] or a PAC setting [33].
Acknowledgments and Disclosure of Funding
The authors gratefully acknowledge financial support by the German Research Foundation (DFG - project number 317046553).

Review summaries:
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).

This work studies the BAI problem in the multi-dueling bandits.  It proposes algorithms with theoretical guarantee and provides related lower bounds. There are detailed comparisons to existing works. Moreover, it compare the proposed algorithm with other existing algorithms numerically.

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.   Under 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.