# Regret Minimization in Stochastic Contextual Dueling Bandits

arXiv: https://arxiv.org/abs/2002.08583 · HTML: https://mlsanity.com/paper/2002.08583/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2020.

## Built on by (most cited first, 2 of 2)

- [Bias-Robust Bayesian Optimization via Dueling Bandits](https://mlsanity.com/paper/2105.11802/) (2021)
- [Learning to Identify Top Elo Ratings: A Dueling Bandits Approach](https://mlsanity.com/paper/2201.04480/) (2022)

## Abstract (arXiv)

We consider the problem of stochastic K-armed dueling bandit in the contextual setting, where at each round the learner is presented with a context set of K items, each represented by a d-dimensional feature vector, and the goal of the learner is to identify the best arm of each context sets. However, unlike the classical contextual bandit setup, our framework only allows the learner to receive item feedback in terms of their (noisy) pariwise preferences--famously studied as dueling bandits which is practical interests in various online decision making scenarios, e.g. recommender systems, information retrieval, tournament ranking, where it is easier to elicit the relative strength of the items instead of their absolute scores. However, to the best of our knowledge this work is the first to consider the problem of regret minimization of contextual dueling bandits for potentially infinite decision spaces and gives provably optimal algorithms along with a matching lower bound analysis. We present two algorithms for the setup with respective regret guarantees tilde O(d√T) and tilde O(√dT log K). Subsequently we also show that Omega(√ dT) is actually the fundamental performance limit for this problem, implying the optimality of our second algorithm. However the analysis of our first algorithm is comparatively simpler, and it is often shown to outperform the former empirically. Finally, we corroborate all the theoretical results with suitable experiments.