Dueling Bandits with Team Comparisons

Lee Cohen, Ulrike Schmidt-Kraepelin, Yishay Mansour

Introduction

Multi-Armed Bandits (MAB) typically rely on numerical rewards, but in many applications, feedback is strictly comparative. The Dueling Bandits framework addresses this by learning from pairwise preferences rather than absolute scores. However, real-world scenarios often involve teams—such as doubles tennis, multiplayer online games (e.g., League of Legends), or competing corporate departments.

This paper introduces the Dueling Teams problem, a novel extension of the dueling bandits framework where a learner must identify the optimal team of size $k$ from a pool of $n$ players. The critical challenge introduced in this setting is that competing teams must be strictly disjoint. You cannot duel a team against itself, nor can a player simultaneously compete on both sides of a match.

The Disjoint Constraint

The requirement that teams be disjoint breaks standard dueling bandit algorithms. To determine if player $a$ is better than player $b$, the most informative comparison would be $(S \cup \{a\})$ versus $(S \cup \{b\})$. Because the subset $S$ overlaps, this duel is invalid. The learner's primary obstacle is deducing the ground-truth ranking of players and teams using only valid, non-overlapping team duels.

Problem Formulation

The authors formalize the dueling teams model using two foundational assumptions:

  1. Consistency: A team composed of the "top $k$" players is always a Condorcet winner. This means it will win against any other disjoint team with a probability of at least $1/2$.
  2. Strong Stochastic Transitivity (SST): If Team A beats Team B, and Team B beats Team C, then Team A beats Team C with at least the same probability as it beats Team B.

Methodology

The paper provides algorithms for both stochastic (probabilistic outcomes) and deterministic (certain outcomes) environments.

The Stochastic Setting

For the stochastic setting, the authors employ a reduction strategy. They define "witnesses"—specific configurations of disjoint team duels that isolate and reveal the relative strength of two individual players. By sampling these witnesses, the complex team-comparison problem is mathematically reduced to a classical single-player dueling bandit problem. This elegant reduction allows the authors to leverage existing, highly optimized algorithms for top-$k$ identification.

The Deterministic Setting

When duel outcomes are certain (probability 0 or 1), stochastic methods can fail because the distinguishability "gap" ($\Delta$) between players might be zero. To solve this, the authors propose a suite of specialized tools:

  • ReducePlayers: A preprocessing subroutine that builds a "dominance graph" to quickly prune the pool of $n$ players down to a manageable $O(k)$ size.
  • Uncover: A binary-search-like method that discovers pairwise player relations using only $O(\log k)$ team duels.
  • Additive Linear Orders: For environments where a team's overall strength is simply the sum of its individual players' strengths, they provide a highly optimized, polynomial-time algorithm.

Key Insights

  • Deducibility: A striking theoretical insight is that not all player relationships are "deducible." If a skill gap between players is masked by a specific team structure, a learner might never be able to definitively prove $a \succ b$. The paper formally characterizes exactly which relations can be uncovered.
  • The Power of Witnesses: While direct substitution is forbidden, comparing $(S \cup \{a\})$ vs $(S' \cup \{b\})$ alongside $(S \cup \{b\})$ vs $(S' \cup \{a\})$ provides a differential signal. The difference in these outcomes acts as a proxy to reveal the relative strengths of $a$ and $b$.
  • Pruning the Field: In the deterministic case, the learner does not need to find the exact rank of every player. The goal is simply to find a team that cannot be beaten. This shift in perspective allows the ReducePlayers method to rapidly discard the "long tail" of mediocre players.

Theoretical Results

As a theoretical paper focused on algorithmic complexity and regret bounds, the results are presented as mathematical proofs of sample complexity (the number of duels required to find the winning team):

  • Stochastic Complexity: The reduction strategy yields an algorithm that identifies the winning team within $\mathcal{O}\left((n + k \log k) \frac{\max(\log \log n, \log k)}{\Delta^2}\right)$ duels, where $\Delta$ is the distinguishability gap.
  • Deterministic (General): For any total order, the authors achieve a bound of $\mathcal{O}(kn \log k + k^2 \log k \cdot 2^{5k})$. While exponential in team size $k$, it scales linearly with the total number of players $n$.
  • Deterministic (Additive): If team strength is additive, the complexity drops significantly to $\mathcal{O}(nk \log k + k^5)$ duels, yielding a fully polynomial result.
  • Lower Bound: The authors prove that at least $\Omega(n - 2k)$ duels are strictly necessary for any algorithm to identify the winner, establishing a baseline for algorithmic efficiency.

Limitations and Future Work

While the paper establishes strong foundational bounds for the dueling teams problem, several open challenges remain. In the general deterministic setting, the $2^{5k}$ term represents a significant bottleneck for large team sizes. Furthermore, the authors note a distinction between identification and verification: while their algorithms can find a winner, the number of duels required to definitively prove a team is a Condorcet winner in a non-additive model remains an open question. Finally, the current model assumes a strict total order. Future work could explore non-strict orders or "cycles" in team dynamics (akin to Rock-Paper-Scissors), which would require shifting the target solution concept from Condorcet winners to the Smith set.

Summary updated

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.
BibTeX
@inproceedings{cohen2021dueling,
  author = {Lee Cohen and Ulrike Schmidt-Kraepelin and Yishay Mansour},
  title = {{Dueling Bandits with Team Comparisons}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Q4KFiEE4lTV},
}
Figure