Adversarial Dueling Bandits

Aadirupa Saha, Tomer Koren, Yishay Mansour
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:9235-9244, 2021.

Abstract

We introduce the problem of regret minimization in Adversarial Dueling Bandits. As in classic Dueling Bandits, the learner has to repeatedly choose a pair of items and observe only a relative binary ‘win-loss’ feedback for this pair, but here this feedback is generated from an arbitrary preference matrix, possibly chosen adversarially. Our main result is an algorithm whose T-round regret compared to the \emph{Borda-winner} from a set of K items is ˜O(K1/3T2/3), as well as a matching Ω(K1/3T2/3) lower bound. We also prove a similar high probability regret bound. We further consider a simpler \emph{fixed-gap} adversarial setup, which bridges between two extreme preference feedback models for dueling bandits: stationary preferences and an arbitrary sequence of preferences. For the fixed-gap adversarial setup we give an ˜O((K/Δ2)logT) regret algorithm, where Δ is the gap in Borda scores between the best item and all other items, and show a lower bound of Ω(K/Δ2) indicating that our dependence on the main problem parameters K and Δ is tight (up to logarithmic factors). Finally, we corroborate the theoretical results with empirical evaluations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-saha21a, title = {Adversarial Dueling Bandits}, author = {Saha, Aadirupa and Koren, Tomer and Mansour, Yishay}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {9235--9244}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/saha21a/saha21a.pdf}, url = {https://proceedings.mlr.press/v139/saha21a.html}, abstract = {We introduce the problem of regret minimization in Adversarial Dueling Bandits. As in classic Dueling Bandits, the learner has to repeatedly choose a pair of items and observe only a relative binary ‘win-loss’ feedback for this pair, but here this feedback is generated from an arbitrary preference matrix, possibly chosen adversarially. Our main result is an algorithm whose $T$-round regret compared to the \emph{Borda-winner} from a set of $K$ items is $\tilde{O}(K^{1/3}T^{2/3})$, as well as a matching $\Omega(K^{1/3}T^{2/3})$ lower bound. We also prove a similar high probability regret bound. We further consider a simpler \emph{fixed-gap} adversarial setup, which bridges between two extreme preference feedback models for dueling bandits: stationary preferences and an arbitrary sequence of preferences. For the fixed-gap adversarial setup we give an $\smash{ \tilde{O}((K/\Delta^2)\log{T}) }$ regret algorithm, where $\Delta$ is the gap in Borda scores between the best item and all other items, and show a lower bound of $\Omega(K/\Delta^2)$ indicating that our dependence on the main problem parameters $K$ and $\Delta$ is tight (up to logarithmic factors). Finally, we corroborate the theoretical results with empirical evaluations.} }
Endnote
%0 Conference Paper %T Adversarial Dueling Bandits %A Aadirupa Saha %A Tomer Koren %A Yishay Mansour %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-saha21a %I PMLR %P 9235--9244 %U https://proceedings.mlr.press/v139/saha21a.html %V 139 %X We introduce the problem of regret minimization in Adversarial Dueling Bandits. As in classic Dueling Bandits, the learner has to repeatedly choose a pair of items and observe only a relative binary ‘win-loss’ feedback for this pair, but here this feedback is generated from an arbitrary preference matrix, possibly chosen adversarially. Our main result is an algorithm whose $T$-round regret compared to the \emph{Borda-winner} from a set of $K$ items is $\tilde{O}(K^{1/3}T^{2/3})$, as well as a matching $\Omega(K^{1/3}T^{2/3})$ lower bound. We also prove a similar high probability regret bound. We further consider a simpler \emph{fixed-gap} adversarial setup, which bridges between two extreme preference feedback models for dueling bandits: stationary preferences and an arbitrary sequence of preferences. For the fixed-gap adversarial setup we give an $\smash{ \tilde{O}((K/\Delta^2)\log{T}) }$ regret algorithm, where $\Delta$ is the gap in Borda scores between the best item and all other items, and show a lower bound of $\Omega(K/\Delta^2)$ indicating that our dependence on the main problem parameters $K$ and $\Delta$ is tight (up to logarithmic factors). Finally, we corroborate the theoretical results with empirical evaluations.
APA
Saha, A., Koren, T. & Mansour, Y.. (2021). Adversarial Dueling Bandits. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:9235-9244 Available from https://proceedings.mlr.press/v139/saha21a.html.

Related Material