Dueling Bandits with Team Comparisons
This addresses the challenge of efficient team selection in competitive scenarios, such as sports or gaming, by extending dueling bandits to team comparisons, representing an incremental advancement in online learning.
The paper tackles the problem of identifying a Condorcet winning team from noisy comparisons of disjoint pairs of teams in an online-learning setting, achieving algorithms with duel complexities of O((n + k log(k)) max(log log n, log k)/Δ²) for stochastic feedback and O(nk log(k) + k⁵) for deterministic feedback.
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)}{Δ^2})$ duels, where $Δ$ 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.