Battle of Bandits

Aadirupa Saha, Aditya Gopalan
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:804-813, 2018.

Abstract

We introduce Battling-Bandits – an online learning framework where given a set of n arms, the learner needs to select a subset of k $\geq$2 arms in each round and subsequently observes a stochastic feedback indicating the winner of the round. This framework generalizes the standard Dueling-Bandit framework which applies to several practical scenarios such as medical treatment preferences, recommender systems, search engine optimization etc., where it is easier and more effective to collect feedback for multiple options simultaneously. We develop a novel class of pairwise-subset choice model, for modelling the subset-wise winner feedback and propose three algorithms - Battling-Doubler, Battling-MultiSBM and Battling-Duel: While the first two are designed for a special class of linear-link based choice models, the third one applies to a much general class of pairwisesubset choice models with Condorcet winner. We also analyzed their regret guarantees and show the optimality of Battling-Duel proving a matching regret lower bound of $\Omega$(n log T), which (perhaps surprisingly) shows that the flexibility of playing size-k subsets does not really help to gather information faster than the corresponding dueling case (k = 2), at least for the current subsetwise feedback choice model. The efficacy of our algorithms are demonstrated through extensive experimental evaluations on a variety of synthetic and real world datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-saha18a, title = {Battle of Bandits}, author = {Saha, Aadirupa and Gopalan, Aditya}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {804--813}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/saha18a/saha18a.pdf}, url = {https://proceedings.mlr.press/r16/saha18a.html}, abstract = {We introduce Battling-Bandits – an online learning framework where given a set of n arms, the learner needs to select a subset of k $\geq$2 arms in each round and subsequently observes a stochastic feedback indicating the winner of the round. This framework generalizes the standard Dueling-Bandit framework which applies to several practical scenarios such as medical treatment preferences, recommender systems, search engine optimization etc., where it is easier and more effective to collect feedback for multiple options simultaneously. We develop a novel class of pairwise-subset choice model, for modelling the subset-wise winner feedback and propose three algorithms - Battling-Doubler, Battling-MultiSBM and Battling-Duel: While the first two are designed for a special class of linear-link based choice models, the third one applies to a much general class of pairwisesubset choice models with Condorcet winner. We also analyzed their regret guarantees and show the optimality of Battling-Duel proving a matching regret lower bound of $\Omega$(n log T), which (perhaps surprisingly) shows that the flexibility of playing size-k subsets does not really help to gather information faster than the corresponding dueling case (k = 2), at least for the current subsetwise feedback choice model. The efficacy of our algorithms are demonstrated through extensive experimental evaluations on a variety of synthetic and real world datasets.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Battle of Bandits %A Aadirupa Saha %A Aditya Gopalan %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-saha18a %I PMLR %P 804--813 %U https://proceedings.mlr.press/r16/saha18a.html %V R16 %X We introduce Battling-Bandits – an online learning framework where given a set of n arms, the learner needs to select a subset of k $\geq$2 arms in each round and subsequently observes a stochastic feedback indicating the winner of the round. This framework generalizes the standard Dueling-Bandit framework which applies to several practical scenarios such as medical treatment preferences, recommender systems, search engine optimization etc., where it is easier and more effective to collect feedback for multiple options simultaneously. We develop a novel class of pairwise-subset choice model, for modelling the subset-wise winner feedback and propose three algorithms - Battling-Doubler, Battling-MultiSBM and Battling-Duel: While the first two are designed for a special class of linear-link based choice models, the third one applies to a much general class of pairwisesubset choice models with Condorcet winner. We also analyzed their regret guarantees and show the optimality of Battling-Duel proving a matching regret lower bound of $\Omega$(n log T), which (perhaps surprisingly) shows that the flexibility of playing size-k subsets does not really help to gather information faster than the corresponding dueling case (k = 2), at least for the current subsetwise feedback choice model. The efficacy of our algorithms are demonstrated through extensive experimental evaluations on a variety of synthetic and real world datasets. %Z Reissued by PMLR on 04 October 2026.
APA
Saha, A. & Gopalan, A.. (2018). Battle of Bandits. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:804-813 Available from https://proceedings.mlr.press/r16/saha18a.html. Reissued by PMLR on 04 October 2026.

Related Material