  The dueling bandit problem is a variation of the classical multi-armed bandit
in which the allowable actions are noisy comparisons between pairs of arms.
This paper focuses on a new approach for finding the "best" arm according to
the Borda criterion using noisy comparisons. We prove that in the absence of
structural assumptions, the sample complexity of this problem is proportional
to the sum of the inverse squared gaps between the Borda scores of each
suboptimal arm and the best arm. We explore this dependence further and
consider structural constraints on the pairwise comparison matrix (a particular
form of sparsity natural to this problem) that can significantly reduce the
sample complexity. This motivates a new algorithm called Successive Elimination
with Comparison Sparsity (SECS) that exploits sparsity to find the Borda winner
using fewer samples than standard algorithms. We also evaluate the new
algorithm experimentally with synthetic and real data. The results show that
the sparsity model and the new algorithm can provide significant improvements
over standard approaches.
