Dueling Bandits: From Two-dueling to Multi-dueling

We study a general multi-dueling bandit problem, where an agent compares multiple options simultaneously and aims to minimize the regret due to selecting suboptimal arms. This setting generalizes the traditional two-dueling bandit problem and inds many real-world applications involving subjective feedback on multiple options. We start with the two-dueling bandit setting and propose two eicient algorithms, DoublerBAI and MultiSBM-Feedback. Dou-blerBAI provides a generic schema for translating known results on best arm identiication algorithms to the dueling bandit problem, and achieves a regret bound of O(lnT). MultiSBM-Feedback not only has an optimal O(lnT) regret, but also reduces the constant factor by almost a half compared to benchmark results. Then, we consider the general multi-dueling case and develop an eicient algorithm MultiRUCB. Using a novel inite-time regret analysis for the general multi-dueling bandit problem, we show that MultiRUCB also achieves an O(lnT) regret bound and the bound tightens as the capacity of the comparison set increases. Based on both synthetic and real-world datasets, we empirically demonstrate that our algorithms outperform existing algorithms.