Dueling Bandits with Team Comparisons
  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.
