DP-Dueling: Learning from Preference Feedback without Compromising User
  Privacy
Aadirupa Saha Hilal Asi
We consider the well-studied dueling bandit problem, where a learner aims to
identify near-optimal actions using pairwise comparisons, under the constraint
of differential privacy. We consider a general class of utility-based
preference matrices for large (potentially unbounded) decision spaces and give
the first differentially private dueling bandit algorithm for active learning
with user preferences. Our proposed algorithms are computationally efficient
with near-optimal performance, both in terms of the private and non-private
regret bound. More precisely, we show that when the decision space is of finite
size $K$, our proposed algorithm yields order optimal $O\Big(\sum_{i =
2}^K\log\frac{KT}{\Delta_i} + \frac{K}{\epsilon}\Big)$ regret bound for pure
$\epsilon$-DP, where $\Delta_i$ denotes the suboptimality gap of the $i$-th
arm. We also present a matching lower bound analysis which proves the
optimality of our algorithms. Finally, we extend our results to any general
decision space in $d$-dimensions with potentially infinite arms and design an
$\epsilon$-DP algorithm with regret $\tilde{O} \left( \frac{d^6}{\kappa
\epsilon } + \frac{ d\sqrt{T }}{\kappa} \right)$, providing privacy for free
when $T \gg d$.