Regret Minimization in Stochastic Contextual Dueling Bandits
  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 $\Omega(\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.
