Dueling Bandits with Team Comparisons

Lee Cohen, Ulrike Schmidt-Kraepelin, Yishay Mansour

Abstract

Identifying the optimal subset of items from a large pool is a fundamental challenge in decision-making and machine learning. This paper investigates the "dueling teams problem," where a learner must identify the best $k$-sized team from a pool of $n$ players using only noisy, head-to-head comparisons between disjoint teams. We address the dual challenges of an exponential search space ($inom{n}{k}$) and the constraint that comparisons must occur between disjoint sets. We present algorithmic frameworks that achieve polynomial-time complexity in both stochastic and deterministic settings, demonstrating that the underlying player rankings can be efficiently recovered despite the team-level observation bottleneck.

1. Introduction

In the standard Multi-Armed Bandit (MAB) framework, a learner seeks to identify the best action ("arm") by observing numerical rewards. Dueling Bandits (DB) generalize this by replacing absolute rewards with relative preferences derived from pairwise comparisons. However, many real-world applications—ranging from e-sports roster construction and basketball team assembly to product bundling for advertisements—require selecting a team of $k$ elements rather than a single arm.

The "dueling teams problem" introduces two significant hurdles to the standard DB model:

  1. Exponential Search Space: The number of possible teams grows combinatorially as $inom{n}{k}$. For large pools, testing every combination is computationally and practically impossible.
  2. The Disjointness Constraint: In a physical or logical match, a player cannot participate on both sides simultaneously. This prevents direct comparisons between teams that share members, which can hide crucial information about how players compare when they are "stuck" on the same side of a matchup.

This paper explores whether a "Condorcet winning team"—one that defeats any other disjoint team—can be identified with a number of duels that scales polynomially with $n$ and $k$.

2. Methodology

The authors assume that team strength is consistent with an underlying (but hidden) ranking of individual players. They propose two primary algorithmic frameworks to navigate the search space.

2.1 Stochastic Reduction

In settings where match outcomes are noisy (i.e., a stronger team wins with probability $P > 1/2$), the authors develop a reduction to classical Dueling Bandits. The core of this approach is a "witness" system. By carefully selecting specific team compositions, the algorithm can simulate "singles duels" between individual players. These simulated duels are then processed by existing, optimized DB algorithms to identify the top $k$ players.

2.2 Deterministic and Additive Frameworks

When outcomes are deterministic, the stochastic "gap" between teams may be zero, requiring a different approach. The authors introduce two key subroutines:

  • ReducePlayers: A preprocessing step that utilizes a dominance graph to prune the player pool from $n$ down to $O(k)$ candidates.
  • Uncover: A subroutine that employs binary search over team compositions to resolve the relative ranking of specific players within $O(\log k)$ duels.

For the specific case of Additive Total Orders, where a team's strength is simply the sum of its members' values, the authors provide a highly efficient algorithm with $O(nk \log k + k^5)$ complexity.

3. Key Insights

A central finding of the paper is the concept of deducibility. Not all player relationships are directly observable through team duels due to the disjointness constraint. However, the authors prove that relationships which are not "deducible" do not impact the ability to identify a winning team. By focusing on player-level relationships rather than team-level matchups, the complexity of the problem drops from exponential to polynomial.

4. Results

The theoretical analysis establishes several key bounds for the number of duels required to identify the winning team:

  • Stochastic Setting: $O\left((n + k \log k) \frac{\max(\log \log n, \log k)}{\Delta^2}\right)$, where $\Delta$ is a gap parameter.
  • Deterministic Setting: $O(nk \log k + 2^{O(k)})$ for general orders, improving significantly to $O(nk \log k + k^5)$ for additive models.
  • Lower Bound: The authors prove that any algorithm must perform at least $n - 2k$ duels, showing that their $n$-dependency is near-optimal.

5. Conclusion and Future Work

This work provides a robust theoretical foundation for subset selection in dueling environments. While the algorithms are efficient, they primarily focus on additive team strengths. Future research is needed to address "synergy" or team chemistry, where the interaction between specific players creates non-additive effects. Additionally, extending this work from "best arm identification" to "regret minimization"—minimizing matches lost during the learning phase—remains a key open challenge.

Summary updated

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