Regret Minimization in Stochastic Contextual Dueling Bandits
This work addresses a practical problem in online decision-making scenarios like recommender systems and information retrieval, where eliciting relative preferences is easier than absolute scores, and it is the first to provide provably optimal algorithms for this contextual setting.
The paper tackles the problem of regret minimization in stochastic contextual dueling bandits, where learners receive only pairwise preference feedback instead of absolute scores, and presents two algorithms with regret guarantees of Õ(d√T) and Õ(√(dT log K)), along with a matching lower bound of Ω(√(dT)) showing the second algorithm is optimal.
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\sqrt{T})$ and $\tilde O(\sqrt{dT \log K})$. Subsequently we also show that $Ω(\sqrt {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.