DP-Dueling: Learning from Preference Feedback without Compromising User Privacy
This work addresses privacy-preserving preference learning for users in bandit settings, but it is incremental as it extends existing dueling bandit methods with differential privacy.
The paper tackles the dueling bandit problem with differential privacy constraints, proposing algorithms that achieve near-optimal regret bounds for both finite and infinite decision spaces, with specific bounds like O(∑_{i=2}^K log(KT/Δ_i) + K/ε) for finite cases.
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}{Δ_i} + \frac{K}ε\Big)$ regret bound for pure $ε$-DP, where $Δ_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 $ε$-DP algorithm with regret $\tilde{O} \left( \frac{d^6}{κε} + \frac{ d\sqrt{T }}κ \right)$, providing privacy for free when $T \gg d$.