7873_an_asymptotically_optimal_batc (1)

We study the K-armed dueling bandit problem, a variation of the traditional multiarmed bandit problem in which feedback is obtained in the form of pairwise comparisons. Previous learning algorithms have focused on the fully adaptive setting, where the algorithm can make updates after every comparison. The "batched" dueling bandit problem is motivated by large-scale applications like web search ranking and recommendation systems, where performing sequential updates may be infeasible. In this work, we ask: is there a solution using only a few adaptive rounds that matches the asymptotic regret bounds of the best sequential algorithms for K-armed dueling bandits? We answer this in the affirmative under the Condorcet condition, a standard setting of the K-armed dueling bandit problem.