Adversarial Dueling Bandits

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 $\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).

arXiv comment26 pages

References in corpus (11)

• The best of both worlds: stochastic and adversarial bandits
• Efficient learning by implicit exploration in bandit problems with side observations
• Random Utility Theory for Social Choice
• Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem
• Double Thompson Sampling for Dueling Bandits
• An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
• Reducing Dueling Bandits to Cardinal Bandits
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm
• PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds
• PAC Battling Bandits in the Plackett-Luce Model