Multi-dueling Bandits with Dependent Arms

Yanan Sui, Vincent Zhuang, Joel W. Burdick, Yisong Yue
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:551-560, 2017.

Abstract

The dueling bandits problem is an online learning framework for learning from pairwise preference feedback, and is particularly well- suited for modeling settings that elicit subjec- tive or implicit human feedback. In this paper, we study the problem of multi-dueling bandits with dependent arms, which extends the orig- inal dueling bandits setting by simultaneously dueling multiple arms as well as modeling de- pendencies between arms. These extensions capture key characteristics found in many real- world applications, and allow for the opportu- nity to develop significantly more efficient al- gorithms than were possible in the original set- ting. We propose the SELFSPARRING algo- rithm, which reduces the multi-dueling bandits problem to a conventional bandit setting that can be solved using a stochastic bandit algo- rithm such as Thompson Sampling, and can naturally model dependencies using a Gaus- sian process prior. We present a no-regret anal- ysis for multi-dueling setting, and demonstrate the effectiveness of our algorithm empirically on a wide range of simulation settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-sui17a, title = {Multi-dueling Bandits with Dependent Arms}, author = {Sui, Yanan and Zhuang, Vincent and Burdick, Joel W. and Yue, Yisong}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {551--560}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/sui17a/sui17a.pdf}, url = {https://proceedings.mlr.press/r15/sui17a.html}, abstract = {The dueling bandits problem is an online learning framework for learning from pairwise preference feedback, and is particularly well- suited for modeling settings that elicit subjec- tive or implicit human feedback. In this paper, we study the problem of multi-dueling bandits with dependent arms, which extends the orig- inal dueling bandits setting by simultaneously dueling multiple arms as well as modeling de- pendencies between arms. These extensions capture key characteristics found in many real- world applications, and allow for the opportu- nity to develop significantly more efficient al- gorithms than were possible in the original set- ting. We propose the SELFSPARRING algo- rithm, which reduces the multi-dueling bandits problem to a conventional bandit setting that can be solved using a stochastic bandit algo- rithm such as Thompson Sampling, and can naturally model dependencies using a Gaus- sian process prior. We present a no-regret anal- ysis for multi-dueling setting, and demonstrate the effectiveness of our algorithm empirically on a wide range of simulation settings.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Multi-dueling Bandits with Dependent Arms %A Yanan Sui %A Vincent Zhuang %A Joel W. Burdick %A Yisong Yue %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-sui17a %I PMLR %P 551--560 %U https://proceedings.mlr.press/r15/sui17a.html %V R15 %X The dueling bandits problem is an online learning framework for learning from pairwise preference feedback, and is particularly well- suited for modeling settings that elicit subjec- tive or implicit human feedback. In this paper, we study the problem of multi-dueling bandits with dependent arms, which extends the orig- inal dueling bandits setting by simultaneously dueling multiple arms as well as modeling de- pendencies between arms. These extensions capture key characteristics found in many real- world applications, and allow for the opportu- nity to develop significantly more efficient al- gorithms than were possible in the original set- ting. We propose the SELFSPARRING algo- rithm, which reduces the multi-dueling bandits problem to a conventional bandit setting that can be solved using a stochastic bandit algo- rithm such as Thompson Sampling, and can naturally model dependencies using a Gaus- sian process prior. We present a no-regret anal- ysis for multi-dueling setting, and demonstrate the effectiveness of our algorithm empirically on a wide range of simulation settings. %Z Reissued by PMLR on 04 October 2026.
APA
Sui, Y., Zhuang, V., Burdick, J.W. & Yue, Y.. (2017). Multi-dueling Bandits with Dependent Arms. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:551-560 Available from https://proceedings.mlr.press/r15/sui17a.html. Reissued by PMLR on 04 October 2026.

Related Material