Abstract
Motivated by privacy concerns in sequential decision-making on sensitivedata, we address the challenge of nonparametric contextual multi-armed bandits(MAB) under local differential privacy (LDP). We develop auniform-confidence-bound-type estimator, showing its minimax optimalitysupported by a matching minimax lower bound. We further consider the case whereauxiliary datasets are available, subject also to (possibly heterogeneous) LDPconstraints. Under the widely-used covariate shift framework, we propose ajump-start scheme to effectively utilize the auxiliary data, the minimaxoptimality of which is further established by a matching lower bound.Comprehensive experiments on both synthetic and real-world datasets validateour theoretical results and underscore the effectiveness of the proposedmethods.