Differentially Private Contextual Linear Bandits
This work addresses privacy concerns in online learning systems like recommendation engines, offering a novel approach to balance privacy and performance, though it is incremental in adapting existing methods to a privacy-aware setting.
The paper tackles the problem of preserving privacy in contextual linear bandits, showing that standard differential privacy leads to linear regret, and proposes a joint differentially private algorithm based on linear-UCB with noise addition, achieving bounded regret and providing the first lower bound for private multi-armed bandit algorithms.
We study the contextual linear bandit problem, a version of the standard stochastic multi-armed bandit (MAB) problem where a learner sequentially selects actions to maximize a reward which depends also on a user provided per-round context. Though the context is chosen arbitrarily or adversarially, the reward is assumed to be a stochastic function of a feature vector that encodes the context and selected action. Our goal is to devise private learners for the contextual linear bandit problem. We first show that using the standard definition of differential privacy results in linear regret. So instead, we adopt the notion of joint differential privacy, where we assume that the action chosen on day $t$ is only revealed to user $t$ and thus needn't be kept private that day, only on following days. We give a general scheme converting the classic linear-UCB algorithm into a joint differentially private algorithm using the tree-based algorithm. We then apply either Gaussian noise or Wishart noise to achieve joint-differentially private algorithms and bound the resulting algorithms' regrets. In addition, we give the first lower bound on the additional regret any private algorithms for the MAB problem must incur.