Dueling Bandits with Team Comparisons
Authors: Lee Cohen
Ulrike Schmidt-Kraepelin
Yishay Mansour
Venue: NeurIPS 2021 Poster (2021)
Keywords: Dueling bandits
Preference learning
Online learning

Abstract: We introduce the dueling teams problem, a new online-learning setting in which the learner observes noisy comparisons of disjoint pairs of $k$-sized teams from a universe of $n$ players. The goal of the learner is to minimize the number of duels required to identify, with high probability, a Condorcet winning team, i.e., a team which wins against any other disjoint team (with probability at least $1/2$).
Noisy comparisons are linked to a total order on the teams. 
We formalize our model by building upon the dueling bandits setting (Yue et al. 2012) and provide several algorithms, both for stochastic and deterministic settings. For the stochastic setting, we provide a reduction to the classical dueling bandits setting, yielding an algorithm that identifies a Condorcet winning team within $\mathcal{O}((n + k \log (k)) \frac{\max(\log\log n, \log k)}{\Delta^2})$ duels, where $\Delta$ is a gap parameter. For deterministic feedback, we additionally present a gap-independent algorithm that identifies a Condorcet winning team within $\mathcal{O}(nk\log(k)+k^5)$ duels. 

Dueling Bandits with Team Comparisons
Lee Cohen" Tel Aviv University
Ulrike Schmidt-Kraepeling Technische Universität Berlin u. schscchite deedddt-rreeeiiine @tu-berlin.de
Yishay Mansour Tel Aviv University and Google Research mansour, munsour.ysshen www.yyyysshhyaaaaooommmmm
leecohencs@gmail.com
Abstract
We introduce the dueling teams problem, new online-learning setting in which the learner observes noisy comparisons of disjoint pairs of k-sized teams from a universe of n players. The goal of the learner to minimize the number of duels required to identify, with high probability. Condorcet winning team, i.e., a team which wins against any other disjoint team (with probability least 1/2). Noisy comparisons are linked to a total order on the teams. We formalize our model by building upon the dueling bandits setting (Yue al., 2012) and provide several algorithms, both for stochastic and deterministic settings. For the stochastic setting, we provide a reduction the classical dueling bandits setting, yielding an algorithm that identifies a Condorcet winning team within ((n+* k log(k)) max log n,log k) duels, where A is a gap parameter. For deterministic feedback, additionally present a gap-independent algorithm that identifies a Condorcet winning team within Onk log(k) 1-5) duels.
Introduction
Multi-arm bandits (MAB) is a classical model of decision making under uncertainty. In spite of the simplicity of the model, it already incorporates the essential tradeoff between exploration and exploitation. In MAB, the learner performs actions and can only observe rewards of the actions performed. One of the main tasks in MAB is best arm identification, where the goal is to identify near-optimal action while minimizing the number of actions executed. The MAB model has numerous practical applications. including online advertising, recommendation systems, clinical trials, and more. (See Sllvkinns/ (2019): Lattimore Szepesvári 2020) for more background).
One weakness of the MAB model the assumption that real-valued rewards are always available. In many applications, it is more natural compare two actions and observe which one of them is better rather than give every single action a numerical reward. For example, recommendation systems often suggest items and obtain only their relative preference feedback (e.g., by click them). This leads very naturally to the well-known model of dueling bandits (Yue et al.) (2012), where the learner selects pair of actions each time and observes the binary "winner" of duel between the two. (See Busa-Fekete et al. (2018) for a survey on extensions of the dueling bandit model).
of
In this work which are k-sized subsets the actions (which we call players). This appears naturally in sports online games, where the goal is to pick one of the best teams from set of players by observing the outcomes of matches (say, to be school representative team, or to sponsor for tournaments). Examples include doubles tennis, basketball, and the online game League of Legends, where each match requires two disjoint teams of players to compete. Similar phenomena appear in working environments, where different R&D teams compete implementing project. Another example could be online advertisements where multiple products are bundled to display ad and a customer
interested in the
that the learner has to select disjoint teams for duel,
'These authors contributed equally to this work.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

can click on any of two presented bundles, e.g., some online games offer in app bundle purchases, and the information regarding sales of different bundles can improve the bundles' composition.
Our basic model is the following. We have a universe of n players, and at each iteration the learner selects two disjoint teams for duel and observes the winner. For any two different teams, there exists an unknown stationary probability that determines the winner of a duel between them. The requirement that dueling teams need to be disjoint is in accordance with the situation in games, where a single person cannot play for both teams. The goal of the learner is to minimize the number of duels required to identify, with high probability, a Condorcet winning team, i.e., a team which wins against any other disjoint team (with a probability of at least 1/2). We assume these probabilities are linked strict total order on all teams, which implies the existence of Condorcet winning team, yet is typically not unique. We make two minimal and natural assumptions on this total order on teams: that it is consistent to some total order among the players, and that team probabilistic comparisons hold Strong Stochastic Transitivity, a common assumption in dueling bandit settings.
Our consistency assumption implies that the best team is the team of top-k players, and this also a Condorcet winning team. However, not all relations between players are deducible for the learner. In particular, even achieving accurate estimations of the latent winning probabilities between all disjoint teams might not suffice to separate the top-k players from the rest. Consider for example an instance with four players
> 3 > 4 where k 2 and the total order among the teams is lexicographical, i.e., 12x > 13 > 14 > 23: > 24 > 34. Assume that each of the three feasible duels is won by the team containing player 1 with a fixed probability y > 1/2. Then, the learner has no chance of detecting the team 12 as the top-I team. However, any of the teams 12, 13 and 14 is Condorcet winning team.
Our main target is to present algorithms for which the number of duels is bounded by polynomial in the number of players and the team size k. although the number of teams is exponential in k, i.e., (((/k))*)) and the number of valid duels is 12(2*( (2x )aa) Even if one were to accept an exponential number of arms, a direct reduction to the standard dueling bandits setting would not be feasible as not all pairs of teams are comparable in our model. In particular, duels of the form (SU {a}, S J (b)), which would yield a signal regarding the relation between players a and b, are forbidden. The inherent difficulty of our endeavor comes from two limitations:
(1) Not all the relations between two single players are deducible, (see example above), and (2) even for pairs of players with deducible relation, having 52(2*( ) )²k) valid duels and the same amount of (latent) winning probabilities makes the task of deducing their relations hard.
We start by giving a full characterization of the deducible pairwise relations between players, namely relations that can be detected by an unlimited amount of duels. Our characterization implies that every deducible players relation has one of two types of wilnesses, which are constant-size sets of duels that prove their relation. Once we find a witness for one pair of players, it can often be transformed to a witness for other pairs of players. Building upon this characterization, we introduce parameter Dess which captures the distinguishability of any two players a and b and takes a value of 0 whenever the pair is not deducible. Assuming A := Ax, > O, where k and k 1 are kthh and (k + 1)th best players, we give reduction to the classic dueling bandits problem. Combining this reduction with high-probability top-k identification algorithm for the dueling bandits setting (e.g., Mo.ajer et al.) (2017); Ren al. al. (2020)) yields a similar sample complexity upper bound, e.g., this implies a high- high-probbbility top-k identification algorithm for dueling teams with O A 2 (n + k log(k)) max(log log n, log k)) duels.
Interestingly, it turns out that the deterministic case, i.e., when winning probabilities are in (0, 1}. constitutes a challenging special case of our problem where A can be particularly small, even O. To overcome this issue we design delicate algorithms which are independent of A. On a high level, a preprocessing procedure first excludes as many bad players as possible. To do so, runs a method for identifying pairwise relations between players which performs only a small number of duels, but has little control over the pair for which the relation is uncovered. For general total orders this implies an algorithm requiring Onk log(k) 20(k) duels. For the natural case of additive linear orders, we present a more elaborated approach for detecting a Condorcet winning team within the reduced instance, resulting in algorithm that performs Onk log(k) + 1-5) duels.
We introduce our model in Section 2 give a characterization of deducible relations in Section and discuss the stochastic and deterministic setting in Sections 4 and [ respectively. In Section 6 we provide a discussion including a lower bound and a regret bound. Algorithms and (full) proois are relegated to Sections ( in the appendix, and Section E characterizes additive linear total orders.
2

---

1.1
Related Work
MAB best arm or subset identification single arm identification was initiated in Even- Dar et al.
(2006) and later studied in many works including Bubeck al. (2011); Kaufmann al. (2016); Chen et al. 20177) This setting was extended by Kalyanakrishnan & Stone (2010) for multiple arms identification (i.e., top k arms), using a single arm samples. Other works that address the objective of top-k identification include Chen et al. (2014); Zhou et al. (2014); Bubeck et al. (2013).
Dueling bandits The work of Yue al. 2012) lay down the framework of non-parametric bandit feedback under total order among arms, strong stochastic transitivity, and stochastic triangle inequality assumptions and were followed by many subsequent works (For more, see survey, (Busa-Fekett et al. 2018).) In particular, some subsequent works target the task of identifying the top l players in this setting Mohajer et al. (2017); Ren et al. (2020).
Ducling bandits with sets of actions One line of dueling bandits extension consider the case where the learner selects a subset of actions and observes the outcomes of all duels between all pairs of actions the subset (Brost et al. 2016 Sui et al.] 2017). or the winner of the subset (Saaa & Gopalan (2018); Ren et al. (2018). As consequence, these settings give the learner strictly more information than the ducling bandits setting. In contrast, feedback in our setting reveals lcss information.
MAB with multiple actions selection There are works in which the learner selects a (sometimes fixed-sized) subset of actions at each iteration, and observes either all of the individual selected arms rewards (semi-bandi feedback) or aggregated form of the rewards (full-bandit feedback), and the task is to detect to best arm or the top These include combinatorial bandits Cesa-BBinnci & Lugosi] (2012), top-k Rejwan & Mansour (2020), linear bandit and routing Awerbuch & Kleinberg (2008), and more. The main difference between combinatorial bandits and our setting is the feedback.
Comparison models Noisy pairwise comparison models, especially for sorting and ranking, have long history which dates backs to the 1950's (For more, see a survey, PPlc (2002).). Specifically, the mathematical problem Counterfeit coin was introduced in the form of a puzzle (Grossman) (945): given a pile of 12 coins, determine which coins has a different weight (and therefore counterieit) using balance scales while minimizing the number of measurements. The problem was followed by numerous generalizations Isee/Gy & Nowakowskij (1955). While this problem is restricted to coins with two different weights, our setting can be seen as variant with multiple weights. Finally, a PAC related comparison-basse model was studied in [alcaan et al. (2016).
2 The Dueling Teams Problem
We formalize our problem as follows. Let n. k E with S h S n We denote the set of players by [n] := [1....,n] and call any set of k distinct players a team. Moreover, we assume the existence of an underlying strict total order among all teams, and denote it by >. We also refer to > as the ground truth order. In particular, for any two teams A and B either A > B holds, in which case we say that A is better than B, or vice versa, and this relation is transitive. Additionally, we require the total order among the teams to be consistent with total order among players and formalize this in the consistency assumption at the end of this section.
2.
In each round, the learner selects ordered pair of two disjoint teams, A and B to perform a duel, and receives a noisy binary feedback about which team is better. Note that in contrast to the usual dueling bandits setting, our setting does not allow duels of the form (A, A), as selecting teams with mutual players for a duel is not an option. We denote the (directly) observable part of > by > >obs, i.c., A toe B iff A and B are disjoint teams and A > B. Note that >ob is not transitive.
We write A > B if team A is the random winner of duel (A, B). The probability Pr[A > B] is stationary and denoted by PA.B Pr[A> > B). In each duel of team A against team B the outcome A > B is sampled independently from a Bernoulli distribution with parameter PA.B
PB.A- We assume that the probabilistic comparisons are linked to the total order among the teams, i.e., A > B implies PA,R > 1/2, and that PA,B exists for every pair of teams (not only disjoint ones). In the deterministic setting, it holds that PAIB E 1) for any teams A 전 B. In other words, > B, and for two disjoint teams A and B the learner can observe whether A Toe B or B obs A by performing single duel.
A abs iff the outcome of each duel (A, B)
3

---

A team A is a Condorcet winning tean if A > Jobs B for all teams B such that A B = 0. From our assumption on > there always exists a Condorcet winning team, but it not necessarily unique. The learner's goal is to minimize the number of duels required to identify, with high probability in the stochastic setting and with probability in the deterministic case, a Condorcet winning team.
In the following we formalize two more assumptions we impose on our model, the former affects the linking of the probabilities to the strict total order >- the latter restricts the total order > itself.
Strong stochastic transitivity (SST) Similarly to the dueling bandits settings in Yue et al. (0012).
assume strong stochastic transitivity. Namely, for every triplet of different teams A > B > Cit holds that PA. 2 max{ PA.B. PB,C}-
Consistency We assume that the total order > is consistent to a total order among single players. More precisely, we say that > satisfies consistency Flit for every two players a, E [x] either of the following holds true:
ii SU > (b( for all S S [x] (s (ii) Su (b) > (a()a (a) for all S S [n] [s) 1-
The consistency assumption lets us derive relation among the single players. by defining a > b iff S {a} > S U {6} holds for some S. By team relation transitivity, > implics a total order on [n] Whenever write > b for some players a, b [ra] this is short-hand notation for SU{a} > {b for all subsets S _ [n] \ {a, b} of size h - 1. Though the consistency assumption might appear strong at first sight, dropping it would render the model intractable the order among the teams would be independent of the players' identities. Namely, there is no linkage to the composition of the teams
For notational convenience, we assume without loss of generality that 1 > 2 ... > and write Ar for the set of players containing the top m players, i.e., A = [ma]. In particular, the consistency assumption yields that AB is Condorcet winning team. However, though the ground truth ranking induces a total order among the players, the learner might not be able to deduce the entire order. In the following give characterization of the deducible part of the ground truth order >
3 Witnesses: A Characterization of Deducible Relations
In this section we provide a high level description of the complete characterization of all the pairwise relations between single players that can be deduced via team duels. We refer the reader to the full description of the characterization, which appears in Appendix A Though single players relations cannot be sampled via feasible team duels directly as intersected teams cannot duel each other, we show sufficient and necessary condition for deducible relations in the form of constant number of winning probabilities of observable (feasible) duels. We refer to pairs of sets of players participating in such duels as wilnesses.
We denote by Podr the set of all tuples (P',>",, where each p' is a team winning probability matrix that satisfy SST w.r.t. >', which is consistent strict total order on teams, and both pr and x/ are compatible with the winning probabilities of observable duels and each other, i.c.. (PA,.B = PA.B A and B are disjoint teams} and PA = = - P/ B, 1/2 iff A Y B. We remark that it follows directly from the definition of Pase that (P,> Pohs. where P is the ground truth winning probability matrix and > the ground truth total order.
We denote by Coks the set of strict total orders >' for which there exists a tuple (P',>) E Pobs- Intuitively, total order >' is in Cobs if there exists an instance (P", that has > as its ground truth total order, follows our assumptions and is compatible with the observable part of (P, >). Lastly, we define A >~ B if and only if A >' B for all X'E Coba, where A and B are not necessarily disjoint. We refer to > as the deducible relation. For single player relations, we define a >" b if and only if
"The name is motivated by the fact that such team is weak Condorcet winner for the relation ohe- 3 "Consistency is also reminiscent of separable preferences from economic theory (Breton & Sen 1999). *For example, the following instance would be possible: Players players' (i.e., they lose in almost all duels) but together they form the best team (and a unique Condorcet winning team), and players 1, ...,, A are the 'intuitively best players' and form the second best team in the linear order among teams. In such model any algorithm would need to iterate over all teams. In other words, the problem becomes a dueling bandits problem with ((nn/k)*) arms.
k ..., n. are the 'intuitively worst

---

there exists S S [n] use ohs and Cobs for analysis and never compute them.
\ {a.b) such that S {afa} >' (b} for all > Cobs. We stress that we only
Next, we define two sets of potential witnesses that have a simple structure and, in some cases, allow us to deduce single players relation: (1) A potential subsets witnesses set, denoted by Sa,b, that contains all pairs SS) such that S and S" are disjoint subsets of [rx] \ {a, bj and both are of size k 1, and (2) A potential subset-team witnesses set, denoted by To,b. that contains all pairs (S, T) where S and I are disjoint subsets of [T>] \ {a, b}. such that S is of size ls - 1 and '' is of size k (and therefore team). Below, we define under which conditions a potential witness indeed a wimess.
Definition 3.1.
An element (S, S*) Sa.b is subsets witness for > b if Psu(a),8 > (b) An element (S, T) E Ta.b is a subset-team witness for > b Psu().. > PSu
We capture the set of the elements of Sa.b that are subsets witnesses for > b by Sü, and analogously, Tab = {(S,T) E Ta,b (S, is a subset-team team witness for a > b}. It might be the case that S² U TT, is empty, in particular this holds when b > a. It is also possible that both S², U UT,,, and St U TTa are empty, in which case we will show that the relation between players in a and cannot be deduced. The following theorem implies that the other direction is also true.
Theorem 3.2. Let a, b [n]. Then, a > b if and only if Sū U UTa #0.
Proof sketch. Assume that S U To.b * O. We show that >- b by using SST, the fact that > is a consistent striet total order, and an exhaustive case analysis. For the sake of illustration we
present only one case here, namely, that (8,S") E St and that both (1) SU {a} > S' U {6} and (2) S {b} S' U {a} hold. Assume for contradiction that a >- b does not hold. It thus follows that there exists an order, E'E Cobs for which b >' a holds. Let PAA.B be the corresponding winning probabilities. Then, using consistency of > and (1) respectively, we get S U {b} > SU [a) > S' U [b} and from SST Pd (su (b) 2 P (u(),, > 1/2. In addition, applying consistency again, it follows that S U [b} > U'U {b} + (a). Applying SST once more we get (s 2 P S'u(() 2 P S' a contradiction (S. E Sü (since this implies S > ('
For the other direction start by defining Da as the set of observable duels (A, B) such that a E A. Moreover, we define a permutation π on the set of teams, which simply exchanges the players a and b when present. We then show that a b implies PA.B 2 (x(A))<(B) for all (A, B) E Da- Moreover, we show that >- b implies that there exists (A, E Da with PA.B (B) as follows. Assume not. Then we show that the relation >' defiined by A' B iff a (AA > x(B) is
included in Cohs. However, a > implies that for any S C [x] \ {a, bj of size 6-1 11 it holds that
(a) >* (U(b) which implies (i) SU(a) > (b] as well as (1i) (af X (b.. Applying the definitions of > and π,, statement (ii) implies S SU (b) = (S U (a)) > (S) S (a)
and hence yields a contradiction to (t). Finally, take some (), E Da with PA.B > (B) If
b E B, then (AV (a], B {b)) E S2,0, otherwise (A) (a), B) E
Tr,
For the sake of brevity, we introduce the set No.s which combines the pairs from Sa, and Ta into a set of triples. Formally, X = (S,,S' T) (S,S") E Su,, (S, T) E J. We say that (S, T) a witness for > b (S, (.55') E Si, or (S.T) To and denote (S, (S,S',T) E X,,'
4 Stochastic Setting
In this section we focus on algorithms identifying, with high probability, the top-k team, which is in particular a Condorcet winning team. The main idea is to utilize the results from the previous section to reduce the dueling teams setting to the classic dueling bandits setting (uue et al. (2012)). To this end we will introduce our gap parameter, A, which intuitively captures how easy it is to prove the relationship between the top l: and the top (k + 1) player. We start by defining, for any element (S, T') E Xa,b. a random variable (S, S', T)) that combines the outcomes of four duels that helps determining whether (8, S', T' is a witness for a > b. Formally,
Xa, ,TT)- = (1[S U (a} > [b - 1ss (6} > S'Uf - 1[SU > T| - 1 (b) > /1)/4.
5

---

Observe that Xa, (5, can take values from 1-1/2.-1/4.011442222
thus
B[ S¹ ,T] 1 1/2,11/2). Moreover, we have the following properties:
1. For every (S, E Na,b, it holds that & (", T)) > 0 = (5,5', E x
2. I[ (S, [)] = 00 for every (S, ( Xa,b, then Theorem 3.2 implies that the pairwise relation between players a, cannot be deduced.
Building upon the random variables Xa, (T, which are defined for fix pair of players, a, and for each element in Xa, we define single random variable Xa.b by picking random triplet T) E Xa,b and returning a realization of X2,b(S, S.:T):.)))))) T). For convenience, whenever we write B[Xa,6] we mean Ess,s Ka.s (X..).. Using the probabilistic method, we obtain the following theorem, which then brings us to the definition of gap parameter for our problem.
Theorem 4.1. For every two players a, [n>] it holds that a >- b if and only if E[Xo,b] > 0.
Gap parameter We define our gap parameter by A == [[Xx, Another interpretation for A is that A 1/2 1). where [0, the probability that the top k player wins against the top k + 1 player, when the two players are placed with random potential subsets witness from St,++1 (i.e.. disjoint random subsets of l- 1 players) and B [0, 1] captures the difference in winning probabilities when & and k + are placed with random potential subset-team witness from T (i.e., two disjoint random subsets of sizes k- - and k). Within Appendix B we show that for k 1, this gap is at least of the same order as the gap parameter for the classical dueling bandit setting.
In the following
distinguish between the top k and (k + 1) players, but also allows us to distinguish other players in A and players from [nx] At. To this end, we show in Lemma 4.2 that the expectations E[X,,b] satisfy strong stochastic transitivity w.r.t. the ground truth total order on players. We note that most elements (", T) E Nn, hold e[Xa,e(T(S)) π (S'), (T)) 2 B[Xa,b(S, S' TT) (and analogously for Xx.c). where π is permutation exchanging players b and c, but, surprisingly this is not true in general. By carefully constructing a charging scheme, we manage to show that this holds in expectation over all elements of Xa. and derive strong stochastic transitivity for the distinguishabilities of players.
show that our gap parameter does not just help
Lemma 4.2. For a triplet of players a > b > c it holds that
E x[ 2 max (F( B [[.......
This also yields the following theorem, which paves the way for our reduction in what follows.
Theorem 4.3. For any a, b E [n] with a E Aj,b b & A2 it holds that E E[Xa, > E[ = A. Thus, if A and for a team A it holds that 1E(Xa,>] 2 for all A, [n] A. then A A
The reduction We now outline the gap- depeneentd algorithm. The results we have derived in Section 3 will allow us to deduce, with high probability, whether a distinguishability of a given pair of players is at least A, and if so determine which is the better player. Intuitively, this is done by performing O + team duels. We use E[X,,t] as a proxy for the distinguishability between two single players, b, taking advantage of the fact that if their relation is deducible, then E[X..t] n. o and in this case
E[X B[Xa,5] > iff a > b. Similar to the dueling bandits setting, even though [E[ < A for some pairs of players, identifying A with high probability is possible.
Since we cannot directly sample Xa, we will instead sample uniformly at random triplet of sets, (S,S" .T) from X. Using (S, (E Sa,r) and (S, () To, we can then perform all the duels required for an unbiased sample of (a, S" T)) which is by itself sampling of X..b- Given any dueling teams instance, we define dueling bandits instance as follows: for every two players a. b E [n]], we define the probability that a wins a (singles) duel against as
Pab 1/2 + E[X,,o).
Clearly, 1- Pas Pas =
Po.a. Pa. [0, and Pa. > 1/2 implies a > b. In addition, Theorem 4.1
implies that a is better than in this dueling bandits instance iff >- b. So whenever a dueling bandits algorithm is asking for duel query, (a, b). we can make an independent sample of Xa, by randomly drawing a triplet (S,S", T) E X1,b and returning random sampling of Xa,, S' T) 1/2. In cases where the realization of X (S, S' T) + 112 in (1/4, 1/2, 3/4), we assign as the duel (S,SS, T) + 1/2 is 1. We formalize this idea in winner if the result of flipping a coin with bias (S,
the sub- proceduee singlesDuel (in the appendix), that simulates a duel for classical ducling bandits

---

settings using team duels. Notice that, by Lemma the probabilities Pa.b defined in ① satisfy SST with respect to the total order among the players induced by the ground truth order > In addition, the feedback of each single player duel we perform is invarinan,,,,,, thus all the non-parametric assumptions for dueling bandits settings apply here. The reduction allows us to identify the top-k players using any dueling bandit algorithm with the same goal that works for total order on arms that satisfy SST, and a gap between the top & and (k + 1) arms as assumptions. We formalize this below.
Theorem 4.4. Given any dueling leams instance with n and k (namely, PA,B for every two teams that hold strict total order, SST, and consistency), we have that the dueling bandit instance defined by 4 satisfies SST with respect to the ground truth order among players > and for any two players a > b it holds that Po,b Z 1/2. Moreover, Px,K+11 = 1/2 + A.
Using the above theorem we can use any dueling bandit algorithm for top-k identification to solve our problem. Mohajer et (017)) provide an algorithm that returns the top-k players with probability ex- ceeding 1 (log r2) -c0 with sample complexity at most e₁ A (n + k log k) max (log log n, log k) in expectation, where co and 01 are universal positive constants and 4 k is the distinguishability between the it and the (A: + 1) best players (see Algorithm/ 2 and Theorem in Mohajer et al. (2017))
Ren et al. 2020) show an algorithm that returns the top-k players with probability at least 1 8 with sample complexity i( (4,2 (log(n (6/) + log log 1-))), where A; = 1i A + 1xx- A..; and k; k + 1 are the top k and the top (k + 1) players, respectively (see Algorithm 5 and Theorem 8 in Ren et al. (2020) These algorithms, together with Theorem 4.1 allow us to derive the following theorem.
Theorem 4.5. There exists an algorithm that returns Aî, with probability exceeding 1 - (log n) to with sample complexity at most c1(n + k log k) max (log log, ko in expectation, where co and er are universal positive constants. In addition, there exists an algorithm that returns A& with probability at least 1 - 5 with sample complexity O(Eret (A,2
A2
+ log log A,1)), where A; 1o [[[ layi -B(xx.a) and i denotes the top i player, thus A, A all i [n]]
5 Deterministic Setting
In Section we showed the existence of algorithms that identify the top-k team with a number of duels that depends on A. But what if A is very small or even 0? One reason for that can be that all relevant probabilities (c.g., P(RJUS.T. P(8++1US8,)) are very close to 1/2 for all (S, S' T) E + Then, a high number of duels to identify A is unavoidable and giving upper bounds in dependence of a gap parameter very much resembles the literature on dueling bandits, where gap between the top k (c.g.. Mohajer et al. (017)). Another reason for A to be small is that the number of witnesses for k > k + 1 is small. We overcome this issue by designing A A-independent algorithms, assuming deterministic feedback, i.e., PA.B E {0. for all pairs of teams (A, B). In this setting, (5, T) E To if and only if (a > obs T > obs SU(b),
and & ++J 1 players is often a parameter of the sample complexity (c.g..
and (S, .') E & if and only if USU {a} obs S' U [b] and S' U {a} > obs S U (b). In the appendix (Section C we show that our results extend to slightly stochastic environment.
The limitation of the set of witnesses makes the task of identifying a Condorcet winning team in the deterministic setting surprisingly hard. For general total orders, a crucial difficulty lies in proving that a given team is indeed Condorcet winning. Nevertheless, we are able to get the following result:
Theorem 5.1. For deterministic feedback, there exists an algorithm that performs Okk log(k) + 2.2 2k) duels and outputs a Condorcet winning team.
For the natural special case of additive total orders we obtain significantly better upper bound. A total order > is additive total, if there exist values for the players denoted by v(x), x: E [n]] such that A > B iff Enc v((a) > Eoe B v(b). In Section El of the appendix we give a sufficient and necessary condition for a total order to be additive. For additive total orders we present an algorithm that identifies Condorcet winning team after polynomial many duels and also outputs a proof.
Theorem 5.2. For deterministic feedback and additive total orders, there exists an algorithm that finds a Condoret winning team within Okn log(k) (b)) + k²) duels.
'e remark that Ren et al. 2020) also assume Stochastic triangle inequality which we do not, however it is only used derive lower bound.
7

---

Both algorithms rely on the same preprocessing procedure called ReducePlayers which reduces the number of players from n O(k). At the heart of this procedure is subroutine called Uncover. After describing Uncover and ReducePPayerss we prove Theorem 5.1 Towards proving Theorem [.2] we introduce two more subroutines, namely NewCul and Compare, which are crucial for identifying and proving Condorcet winning team within the smaller instance. Finally, Algorithm SandoreerWinning combines all components and proves Theorem 5.2 While all algorithms are formalized in Appendix C we give sketches thereof and theorems stating their input and output below.
The Uncover Subroutine Given two disjoint teams A > B, the Uncover subroutine finds a pair of players a E and b E B and a subsets witness for their relation, i.e., an element from S2.6 To understand the idea of the subroutine, consider some arbitrary ordering of the elements in A and B, respectively, i.e., A = {aI...., ) and B = {bi,... : bb Then, iteratively exchange the elements 01 and b1. 02 and by, resulting in sets Ag A. B. = B, A1 = {bi 02 o.,....,,....................... a& ]. B1 = {a1. bg..... b Ag = {b1. b2, A3..... ...) holds, there needs to be some earliest point in time S for which B, A is true. This implies a; > b, as (fa)..... 4, b ) (b........ b ai+1...... ax }) is subsets witness.
4 ) and so on. Since Ao > Bu but An = BB > A Bo
While the above sketched subroutine is simple, it performs Ao duels in the worst case. We refine this idea by a binary search approach, decreasing the number of duels to log(k))
Lemma 5.3. Let A and B be two disjoint teams with A > B. After performing (log(k)) duels, Uncover returns (a. b) with E A, b E B and (S,S') S2, and thus a > b.
We remark that Lemma C.2 in the appendix is a slightly stronger version of the above lemma which allows us to partition A and B into two subsets each, A A U A(2) and B B(1) U B(2), Under some circumstances, we can then guarantee that Uncover reveals the pairwise comparison between two players a > 6, where a is from A and 6 is from ((),
Reducing the Number of Players to O (k) The fact that we can eliminate some players from [n] and still find (and prove) a Condorcet winning team is due to the following observation.
Observation 5.4. Let R C teams A S R \ Á. Then, Å is Condorcet winning team.
[n] such that Aixx S R. Let Å C R be team such that À > A for all
The procedure ReducePlayers reduces the set of players [m] to some subset R S [n] guaranteeing that A&s C R and [R] < 6k. The algorithm maintains dominance graph = (V, E) on the set of players. More precisely, the nodes of D are the players, i.e., V = =[n]. and there exists an are from node a to node b if the algorithm has proven that > b. The set V<26 is the subset of the players having an indegree smaller than 2k in D. The high level idea of the algorithm is the following: It starts with the empty dominance graph D= = ([r]), 0). Then, it iteratively identifies pairwise relations of the players with help of Uncover and adds the respective ares to the graph. By adding more and more ares to D, the set of nodes V=24 shrinks while Air C Ve2k is always guaranteed. At some point, the algorithm cannot identify any more pairwise relations and returns Ve2k- How does the algorithm identify pairwise relations? At any point it tries to find a matching between 2k players, say ((a), bi). ... (ax: b with the constraint that, for all i [k], none of the ares (a,, b:) or (b;, a;) is present within the graph D yet, and then applies Uncover on the sets A {ai,..., .ax) and |V22l > 6k 1, the
B (bi,...,by bx). In the proof of Lemma 5.5 we show that, as long
algorithm can find such a matching. With the help of Lemma 5.5 we then prove Theorem 5.1
Lemma 5.5. Given the set of players [n). ReducePlayers returns R S [n]] with R S 6k: - 2 and Ar C R. ReducePlayers performs O lo)(k)) duels and runs in time O (nn22))
Let D be the dominance graph at the end of ReducePlayers. Then, the learer selects a k-sized subset of Ve2k, call it A, with the property that there is no are from any node in V22k \ Á towards some node in A. Then, the learner tests Á against all possible teams containing players from Ve \ A, which (25%)) many. If Á wins all of these duels, then Á is Condorcet winning team by Observation 5.4 However, if there exists A > A, then, by the choice of A, there does not exist any are from towards Å. Hence, by calling the subroutine Uncover for two arbitrary orderings of A {ai,...,ay) and À = {ār, 0g ). the learner will identify one additional arc. This procedure can be repeated (kk2) times and thus shows Theorem 5.1
Proof sketch (of Theorem 5.1
L
8

---

Tes
X
U2
U1
<
1
2al
1za
U1
U2
X
Y
W Wi
z
Y
W₂
W1
k
2k
<
Figure 1: Illustration of the proof technique of algorithm Condorceriimingl. In the left illustration, the solid black line indicates that all players left to were proven to be better than all players right to it. The dashed line marked with "I- indicates that the sets to its left contain & players in total. However, this line does not indicate proven relations, i.e., players from X are not necessarily better than players from Y. The right figure illustrates the proof for X UU U UU2 being Condorcet winning.
Subroutines NewCur and Compare The NewCut subroutine takes as input subset of the players R S [m]] a pair a, b E R. and a witness proving that a > b, i.c., (5,T") E S2,5 U UTa.b That means, T" can be either of size k- - 1 or k, and S and T are not required to be subsets of R. The subroutine outputs partition of R into two non-empty sets U and L with UD L, which is short-hand notation for u > É for any u E U and E L. The subroutine starts by initiating the set U = {a} and redefines R = R \ {a, bj. At all times, U contains only players u for which the algorithm has found witness for u > b. These witnesses are stored in a list W. and it is checked whether they can be modified to become witnesses for x > b for any other element in x E R. This modification is done by applying permutations on the set of subsets of the players, similarly as in the proof of Theorem 3.2 and Lemma 4.2 If the algorithm finds a witness for x > b, then is added to U and removed from R. The new witness is also stored in W. This process ends when either R is empty or all witnesses in W have been checked. At this point it holds that U à R RUUC (b), and the algorithm returns (U, L == R (b)).
Lemma 5.6. Let R S [m], a, b E R and (S, T E S U.T. Then, NewCut (a, b), (S, ))) returns partition of R into U and L such that U > L, a E U and b E L. The number of duels performed by NewCut and its running time can be bounded by ((
From now on we assume additive linear orders. The compare subroutine is crucial for obtaining upper bounds for differences between values of players' subsets. It is used in the following situation. Let (a, b) be pair of players and (S, S") E S2,6 be a witness for > b. Then, it can be casily shown that v(a) v(b) > Ju(S) v())). We will be interested in the question whether a similar relation holds for two subsets of S and S', namely, C C 5 and D C S' of equal size. The compare subroutine checks whether such relation holds by performing two additional duels. If it returns True, then v(a) 11-v(l v(b) > |v(C- - v( ((D). Otherwise, there can be found a pair e E C and d E D and witness for their relation by one call to the Uncover subroutine. This observation is formalized below.
Lemma 5.7. Let a > be two players, (S,S') E S and C S S, D S S' with -C| [D]. If Compare (a, b), (5, S'), (C, D)) returns True, then v(a) - v(b) > Iw(C) v(D)) Otherwise, one call to Uncover returns e C and d E D together with witness for their relation.
Algorithm CondorcetWinning The algorithm maintains a partition of the players into a weak ordering, i... / [TT.. Tr} with Ti T2 D. .... Te. We introduce the short-hand notation Tsj = Umeei T. and T<j = Umeli-i) Tm- After the application of the preprocessing procedure ReducePlayers, this partition consists of one set, namely T {Ti}, where [T, E ((k) and Aie S Tú. At any point in the execution of the algorithm, we are especially interested in two indices, namely i E [e] such that [Tei,l < k < |Tsi and similarly i2s E [f] such that [ < 2k < |T'siull I- Observe that all players from Tei, are guaranteed to be among the top-k players. On the other hand,
among the players from Tú, some belong to A and others do not. The main idea of the algorithm is then the following: Take a prefix of I of size k, i.c., this team contains the set of players Tes and is a subset of the players in Tz and either prove that this prefix is Condorcet Winning team, or refine the partition 9 and repeat the process. The refinement is done by splitting one element of J. say Tú, into non-empty sets, T T?, and re-indexing the sets within T. This is done with the help of Uncover and NewCut. Clearly, this increases the number of sets in the partition P by one.
'In case one of these indices does not exist, it implies that we have either identified the set Ai, or Alt. In the first case we have found Condorcet winning team and in the second case Observation 5.4]impiees that we can find one by performing one additional duel. For the sake of brevity disregard this case from now

---

We provide two different algorithms, namely CondorcetWiming! for the case in 12x and Con- dorcerWinning2 when i& * 12g. Unsurprisingly. the latter case requires strictly less sophisticated approach, which is why we focus on Condorcet / in the following.
The algorithm starts by partitioning the set T<i, into Tei. of size Trig - 2k. It partitions the set Tip into five sets X, Y, W1, W2, and Z. In particular it known that (U1 J U2) (X UY UW U U22
sets U1 and U2, where U1 is prefix of
Z) but no relation among any pair in Ti is known.
Regarding the sizes of the sets it holds that |U,] = [W;] for i E {1, [X] = =| = k - |U1 - 1U2]
and |U1| = Z The main aim of the algorithm will be to define 0 < 61 Cg and prove that the following statements are true:
(i [xX) .\Y) <
(ii) (e(aa - u(b) < c2 for all a E YEYUU W1 U 2 and b E Z, and
(iii) there exist ;
U1 U U2 as well as w1,-... 2|+1 W1 W2 such that (a) v(m)) - v(n) 2 e1 and
(b) v(u)) vw:) 2 (2 for all i {2,.... 11] 13.
With these statements we show that U1 U U/ X is a Condorcet winning team. More precisely, we show (Ui U UUUUU oWW, U 22 UY) > |Z] 62 and v(W, U W2 UY) - u > - 62, where B" the best response towards U1 U U. See Figure 1 for an illustration of the argument.
It remains to sketch how the algorithm defines E1, E2 and proves (t) (1ii). For simplicity assume U U2. The algorithm then attempts to do the following steps: (1) Find a witness for players ū E U2 and Φ E W2, using Uncover. (2) Use Compare, to prove that [c(X) - v .\Y) | < o(ū) v(w)) and < v(ū) - v(w) holds for all players a E W1 UW2 UY and E Z. (3) Repeat step (2) by replacing 1 with any player of W1. If one of the steps (1)-(3) fails, we show that the partition I can be refined. Otherwise, we show that (i) (áit) hold for 6 v(ū)- v(wj) and Eg = v(ū) e(ws).
where wf and ws are the best and second best players from W1 U [1. respectively. The following Lemma concludes the proof sketch of Theorem 5.2
Lemma 5.8. For every instance with Olk) players, after performing O(k*) many duels, Con- dorcetWinningl has identified a Condorcet winning team. CondorcetWimning2 identifies Condorcet winning team after O(k² log(k)) duels.
6 Extensions and Discussion
Below, we discuss several implications of our results well directions for future work.
Regret bound this paper we provided algorithms to identify, with high probability, a Condorcet winning team. Another common performance metrics for the dueling bandits setting is (e.g., weak) regret. We define a regret in our setting w.r.t. Ai. This is reasonable since SST implics that PAR.B
B 2 PA.B for every Condorcet winning team À and any team B. Then, for time horizon T we denote by (Ar, B,) the selected duel at time and define the regret to be
T
RT Σ min (PAg.A. 1/2, Pag.n. 1/23.
This definition based on weak regret for dueling bandits, as defined in Yue et al. (012)). Within Appendix D we derive a regret bound of Rg O(n( A - (log(TT) + log log A ")).
Checking Condorcet winners beyond additive linear orders The question how many duels are necessary to prove or disprove that given team is Condorcet winning remains open for total orders that are not additive linear, even if n E (k)). Nevertheless, our algorithm from Theorem 5. shows that a polynomial upper bound for this number would imply the existence of an algorithm with polynomial number of duels. More formally: Let g be the number of duels required to check whether given team is Condorcet winning team within an instance with (kk) players. Then, there exists an algorithm that identifies a Condorcet winning team within (km log(k) + kolog (k) )4) duels.
Lower bounds For both settings, we can show a lower bound of n 2k duels in order to identify a Condorcet winning team. We refer to Appendix D for a formal statement and proof.
We call 8² best response towards U1 UU2 X. if B² contains the best & players from [r] \ (U1
10

---

7 Acknowledgments
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 882396), the Israel Science Foundation (grant number 993/17), the Yandex Initiative for Machine Learning Tel Aviv University, the Deutsche Forschungsgemiinscaaff under grant BR 4744/2-1, and the Ariane de Rothschild Women Doctoral Program.
This paper is dedicated to Hunter, dear friend who passed away May 31, 2021.
References
Awerbuch, B., & Kleinberg, R. (2008). Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1), 97-114.
Balcan, M., Vitercik, E., & White, C. (2016). Learning combinatorial functions from pairwise comparisons. In Proceedings of the 29th Conference on Learning Theory, COLT.
Breton, M. L., & Sen, A. (1999). Separable preferences, strategyproofness, and decomposability. Econometrica, 67(3), 605-628.
Brost, B., Seldin, Y., Cox, I. J., & Lioma, C. (2016). Multi-dueling bandits and their application to online ranker evaluation. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management (CIKM), (pp. 2161-2166).
Bubeck, S., Munos, R., & Stoltz, G. (2011). Pure exploration in finitely-armed and continuous-ame armed bandits. Theoretical Computer Science, 412(19), 1832-1852.
Bubeck, S., Wang. T., & Viswanathan, N. (2013). Multiple identifications in multi-armed bandits. In Proceedings of the 30th International Conference Machine Learning (ICML), (pp. 258-265). PMLR.
Busa-Fekete. R., Hüllermeier, E., & Mesaoudi-Paie Paul, A. E. (2018). Preference-bast online learning with dueling bandits: A survey. Tech. rep., arXiv: 1398.
Cesa-Bianchi N., & Lugosi, G. (2012). Combinatorial bandits. Journal of Computer and System Sciences, 78(5), 1404-1422.
Chen, L., Li, J., & Qiao, M. (2017). Towards instance optimal bounds for best arm identification. In Proceedings of the 30th Conference on Learning Theory (COLT), (pp. 535-592), PMLR.
Chen, S.. Lin. T., King. I., Lyu, M. R., & Chen, W. (2014). Combinatorial pure exploration of multi-armed bandits. In Advances in Neural Information Processing Systems (NIPS). Curran Associates, Inc.
Even-Dar, E., Mannor, S., Mansour, Y. (2006). Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(39), 1079-1105.
Grossman, H. D. (1945). The twelve-coin problem. Scripta Mathematica, 11, 360-361.
Guy, R. K., Nowakowski, R. J. (1995). Coin-weighing problems. The American Mathematical Monthly, 102(2), 164-167.
Kalyanakrishnan, S., & Stone, (2010). Efficient selection of multiple bandit arms: Theory and practice. In Proceedings of the 27th International Conference Machine Learning (ICML), (pp. 511-518), PMLR.
Kaufmann, E., Cappé. O., & Garivier, A. (2016). On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17(1), 1-42.
Lattimore, T., & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.

---

Mohajer, S., Suh, C., & Elmahdy, A. (2017). Active learning for top-k rank aggregation from noisy comparisons. In Proceedings of the 34th International Conference on Machine Learning (ICML), (pp. 2488-2888 2497).
Pelc, A. (2002). Searching games with errors fifty years of coping with liars. Theoretical Computer Science, 270(1-2), 71-109.
Rejwan, I., & Mansour, Y. (2020). Top-SkS combinatorial bandits with full-bandit feedback. In Proceedings of the 31st Internationcal Conference Algorithmic Learning Theory (ALT), (pp. 752-776). PMLR.
Ren, W., Liu, J., & Shroff, N. (2020). The sample complexity of best-k items selection from pairwise comparisons. In Proceedings of the 37th International Conference on Machine Learning, (pp. 8051-80725 PMLR.
Ren, W., Liu, J., & Shroff, N. B. (2018). PAC ranking from pairwise and listwise queries: Lower bounds and upper bounds. Tech. rep., arxiv.org/abs/ 806. 080.02970.
Saha, A., & Gopalan, A. (2018). Battle of bandits. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence (UAI), (pp. 805-814). AUAI Press.
Slivkins, A. (2019). Introduction multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2), 1-286.
Sui, Y., Zhuang, V., Burdick, J., & Yue, Y. (2017). Multi-dueling bandits with dependent arms, In Proceedings of 33rd the Conference on Uncertainty in Artificial Intelligence (UAI).
Yue, Y., Broder, J., Kleinberg, R., Joachims, T. (2012). The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5), 1538 - 1556.
Zhou, Y., Chen, X., & Li, J. (2014). Optimal pac multiple arm identification with applications to crowdsourcing, Proceedings of the 31st International Conference on Machine Learning (ICML), (pp. 217-225). PMLR.
12


Reviews:
[{"review_id": "jTMUQ-QC596", "reviewer": "Reviewer_HAJh", "summary": "A new dueling bandit framework with team comparisons.", "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": "This paper presents an interesting and non-trival generalization of dueling bandits by considering the duel between teams rather than single player. I can see this is a solid work with new framework and insights but the current presentation needs improvement and makes me feel hard to read.\n\nThe intro and Section 2 are generally good. The description of the problem is clear to me. One question is about the consistency assumption. Is that kind of an implicit gap assumption on the performance of a single player? That means for play 1 should be much better than other players such that no matter what teammates it has, this team is always better. This should be not required for standard dueling bandits? One minor is Line 64, there is no definition of set S.\n\nI can understand what is included in Section 3 but it's better to clearly state why we need this. I think a standard flow might be stating the problem, defining performance metrices, having the algorithm and proving the theorem.  \n\nSection 4 starts to confuse me. Do you propose new algorithm eventually? Becuase you write any dueling bandit algorithm for top k identification can solve your problem. In orignial dueling bandits paper, they properly define the measure of regret. But in this paper, there is no such measure. I think it's better to comment on that. \n\nSection 5 is not well-organized. It's pretty long and dense. And it's hard to get the key point. Will not determinstic setting be a special case of stochastic setting? There are too many newly defined concepts in this section. If you have new algorithms, it's better to have an algorithm box here. And it looks like the algorithm and theorem always mix together.\n\nNo conclusion is included.   ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "XKHkilNolh0", "reviewer": "Reviewer_6N8R", "summary": "The paper introduces a new problem in which a learner can choose k disjoint teams from a set of n players and observe a winner. The objective is to pick a team that would win against any other team with probability at least 0.5 (Condorcet winner) and to do with a minimal number of duels. Deterministic and Stochastic settings are considered and upper bounds on the number of duels are obtained.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "-The problem seems relevant and an interesting generalization of the duelling bandits setting. Further, various settings are considered and the solutions seem well-thought out. \n\n-Can the notion of the Condorcet winner be generalized? i.e. winning against any other team with probability 3/4 or in general p>= 1/2? How would that look like and affect the algorithms?\n\n-Isn't the problem statement restrictive, specifically the learner is choosing teams of k players. Suppose instead that the learner can choose teams of up to k, would this change things significantly? This would enable pairwise relations between single players.  \n\n-Is the consistency assumption realistic? Since it ignores the interaction between different players. E.g., we might have a>b, but if c complements b much better than a, we could have {b,c} > {a,c}. \n\n-Although there are significant differences, I believe the problem of communications complexity in stable marriage could be relevant, see e.g. Gonczarowski et al \"A Stable Marriage Requires Communication\". I wonder if the authors see any connections or applications of their techniques especially from the deterministic setting, etc.  \n\n-Lack of experiments: Even for work that is heavily theoretical, there is usually an experiments section. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think limitations/societal impacts were adequately addressed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Pz9sSgfMCd6", "reviewer": "Reviewer_bjRF", "summary": "This paper considers a variation of the dueling bandits problem where teams of arms compete against each other rather than individual arms. The paper considers two different models for team-wise comparisons: (1) stochastic where each competing team wins with certain probability and the better team wins with probability >= 1/2; (2) deterministic where the better team always wins. This paper works in the pure exploration setting as the goal is to find the Condorcet winner rather than minimising regret. For the deterministic setting the paper shows that any solution for the classic dueling bandits problem can be used to solve the team-wise dueling bandits problem with bounded number of duels depending on a \\emph{gap} parameter. For the deterministic setting the paper gives an algorithm to find the Condorcet winner with a bounded number of duels with no dependence on gap.\n\n\n\n", "questions": "", "limitations": "", "rating": 5, "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": "1. Real world applications: The paper should expand a bit on the real-world applications where only team comparisons are possible. In my opinion the applications that suit this problem are based on team sports/gaming as one can only observe team comparisons here. In many other cases such as advertising one can even compare individual arms to each other which might be better from a sample complexity point of view.\n\n2. Consistency Assumptions: This assumptions roughly states that there is an ordering among arms, and if a is better than b then adding a to  any team S results in a better team than adding b to S. In my opinion this assumption destroys the essence of team comparisons as one can expect that player a can be more compatible with players in S, and b can be more compatible with players in S'. Hence, adding a to S will result in a better team, whereas adding b to S' will result in a better team. If there is such a linear ordering amongst teams, then why can't we just compare arms a and b directly based on skills etc? It would be easier to make this assumption if there is a real-world validation based on experiments. \n\n3. Dependence on \\Delta and computation complexity: In the stochastic setting the algorithm is essentially searching for a witness among O(n^k) potential witnesses and if there are a few witnesses (which may likely be the case) then it can take O(n^k) time and samples. However, this detail is hidden away in the definition of \\Delta (addressed briefly in Section 5). The paper mentions that the \\Delta in this setting is similar to the \\Delta in dulling bandits. I would argue that this is not the case as \\Delta in dueling bandits is a natural parameter and can be even constant, whereas \\Delta here is a result of the reduction to dueling bandits and will likely have a polynomial dependence on n.\n\n4. Experiments: The paper would benefit greatly through experimental validation of the theoretical results on synthetic/real data and comparisons to a few baselines. Understanding the dependence of \\Delta on n through experiments would also be helpful.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper addresses societal impact in the broader impact section. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "7zXU_VlJYCb", "reviewer": "Reviewer_Bd1b", "summary": "This paper studies a variant of dueling bandits with teams. There are n players, and your goal is to select the “best” team of k of these players (more specifically, you want to select a team of k of these players that doesn’t lose to any team of size k that you can form from the remainder of the n-k players). Each round you can pick two teams of size k, watch them compete, and see who wins. The probabilities that one team beats another are chosen in such a way to be consistent with an underlying ordering of the players, in addition to satisfying some other assumptions (e.g. strong stochastic transitivity).\n\nThe authors study this problem in both the stochastic setting and the deterministic setting (where all the probabilities are guaranteed to be 0/1). In the stochastic setting, they can identify an optimal team whp with O((n + klog(k))/Delta^2), where Delta is some notion of “gap” between the performance of the kth player and the (k+1)th player. They accomplish this by first showing how to compare two players (roughly, you do something like pick a random S of size (k-1) and compare S + {a} to S + {b}, but something a little more complex than this). They then use this to reduce the problem to the well-studied problem of top K identification under pairwise comparisons. \n\nIn the deterministic case (where Delta is usually 0, so the previous bounds don’t apply), they give an algorithm which identifies a “best” team with O(kn log (k) + 2^{O(k)}) comparisons. Furthermore, when the order is an “additive total order” (i.e. generated by just adding values corresponding to specific members), they give an algorithm that only uses O(kn log(k) + k^5). These algorithms are complex combinatorial algorithms -- the main idea is showing that it is possible to identify useful comparisons somewhat quickly (especially under additive orders).\n", "questions": "", "limitations": "", "rating": 5, "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": "\nI think the problem of team selection in this sort of dueling bandits framework is an interesting practical problem (as the authors mention, it shows up in many different settings, especially in sports / games), and I think interesting progress on it would be welcome at NeurIPS. I also think that this paper is quite technically impressive (mainly the algorithms for the deterministic case). I do have some qualms about this paper, however.\n\n- One issue I have is that the Delta gap in the bound of the algorithm in the stochastic case is very “tailored” to the specific algorithm they present. What I mean by this is that, usually when gaps appear in regret bounds, they correspond to some semantically meaningful notion about the test data (e.g. the gap in expected reward between the best and second-best solutions). This Delta is somewhat connected to the gap between the kth and (k+1)th players, but the definition feels not at all natural. Is there a good reason to care about this specific choice of Delta?\n\n- The analysis of the deterministic case is definitely a combinatorial tour-de-force, but I think 1. it is unlikely to be applicable in practice (even the stochastic case has pretty strong assumptions that prevent it from being applicable in practice) and 2. I don’t really see the result or techniques in the analysis proving useful in other areas / for other problems (they are very tailored to this setting). These facts combined make me concerned how interesting the deterministic results will be to the NeurIPS audience.\n\nThe paper was well-written and easy to read. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers generally appreciate the analysis while questioning the assumptions and raising also some interesting questions about the Delta terms that I found well addressed by the authors in the response.

I also read the paper, and while I share some of the reviewers concerns, I also found the setup and analysis interesting and also just fun. I am not bothered that this is purely theoretical work. NeurIPS has in my time always accepted good theoretical papers, even when not accompanied by experiments. 

I do agree with the reviewers that question the assumptions, which are strongly violated in all of the proposed applications. Players on sports teams have roles, and in League of Legends as well. R&D teams are almost always greater than the sum of their parts. Bundles in advertising will surely benefit from (an absence of) diversity. 

The paper is quite dense, which is a problem with short page limits. I hope the authors can use the extra pages to introduce more intuition and clarity as suggested by the reviewers.
Decision: Accept (Poster)