Differentially Private Contextual Linear Bandits
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 [10,18]. 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.
Summary:  In this paper the authors study how to achieve differential privacy in the contextual linear bandits setting. The authors first show that the standard notion of privacy in this setting leads to the linear regret and then they adopt the more relaxed notion of joint differential privacy. They propose the Linear UCB with changing perturbations algorithm as a general framework for achieving this joint differential privacy while achieving a reasonable regret guarantees. The authors provide general regret bounds for their proposed algorithm under some assumptions in section 3. Later in section 4, they explain two different ways for perturbing the estimations in order to achieve joint differential privacy and they combine them with the results in section 3 to provide regret bounds for them. Finally, in section 5 of the paper, the authors provide some lower bounds and show that any algorithm that achieves differential privacy is required to incur an extra regret term.   Evaluation:  The paper is very well-written and well-motivated. This work draws an interesting connection between the contextual linear bandit literature and the differential privacy literature. In order to achieve algorithms that can provide privacy and low-regret simultaneously, the authors: (1) derive general regret bounds for their proposed algorithm (which can be found in Proposition 4) and (2) show that with reasonable perturbations the privacy can also be achieved. From the technical analysis, (1) is an easy extension of analysis in [1] and for (2) authors use the result in [2] or the concentration bounds on \chi^2 distribution. Therefore, the technical analysis does not seem to be very different that what existed in the literature.   On the other hand, the derivation of lower bounds seem to be pretty novel. Also, I like the fact the proposed algorithm is very general and authors show two different ways to make it work. Finally, I want to emphasize the clarity of this work.  Gathering all these points together, I recommend this paper to be accepted to the conference.  One slight comment: the citations [28] and [29] in the paper are the same.  [1] Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems (pp. 2312-2320). [2] Sheffet, O. (2015). Private approximations of the 2nd-moment matrix using existing techniques in linear regression. arXiv preprint arXiv:1507.00056.