Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.




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.

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

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

4. 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.
limitations_and_societal_impact: The paper addresses societal impact in the broader impact section.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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).

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

In 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).

main_review: 
I 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.

- 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?

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

The paper was well-written and easy to read. 

limitations_and_societal_impact: No concerns here.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.  
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. 

-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?

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

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

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

-Lack of experiments: Even for work that is heavily theoretical, there is usually an experiments section. 
limitations_and_societal_impact: I think limitations/societal impacts were adequately addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: A new dueling bandit framework with team comparisons.
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.

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

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

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

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

No conclusion is included.   
limitations_and_societal_impact: no
review_title: null

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)