An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem

We study the K-armed dueling bandit problem, a variation of the traditional multi-armed bandit problem in which feedback is obtained in the form of pairwise comparisons. Previous learning algorithms have focused on the textitfully 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: textitis 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 textitunder the Condorcet condition, a standard setting of the K-armed dueling bandit problem. We obtain asymptotic regret of O(K2log2(K)) + O(Klog(T)) in O(log(T)) rounds, where T is the time horizon. Our regret bounds nearly match the best regret bounds known in the fully sequential setting under the Condorcet condition. Finally, in computational experiments over a variety of real-world datasets, we observe that our algorithm using O(log(T)) rounds achieves almost the same performance as fully sequential algorithms (that use T rounds).