Generalized Linear Bandits with Local Differential Privacy
Year: 2021

Abstract:
Contextual bandit algorithms are useful in personalized online decision-making. However, many applications such as personalized medicine and online advertising require the utilization of individual-specific information for effective learning, while user’s data should remain private from the server due to privacy concerns. This motivates the introduction of local differential privacy (LDP), a stringent notion in privacy, to contextual bandits. In this paper, we design LDP algorithms for stochastic generalized linear bandits to achieve the same regret bound as in non-privacy settings. Our main idea is to develop a stochastic gradient-based estimator and update mechanism to ensure LDP. We then exploit the flexibility of stochastic gradient descent (SGD), whose theoretical guarantee for bandit problems is rarely explored, in dealing with generalized linear bandits. We also develop an estimator and update mechanism based on Ordinary Least Square (OLS) for linear bandits. Finally, we conduct experiments with both simulation and real-world datasets to demonstrate the consistently superb performance of our algorithms under LDP constraints with reasonably small parameters (ε, δ) to ensure strong privacy protection.

heading: 1 Introduction
text: Contextual bandit algorithms have received extensive attention for their efficacy for online decision making in many applications such as recommendation system, clinic trials, and online advertisement [7, 35, 24]. Despite their success in many applications, intensive utilization of user-specific information, especially in privacy-sensitive domains such as clinical trials and e-commerce promotions, raises concerns about data privacy protection. Differential privacy, as a provable protection against identification from attackers [18, 19], has been put forth as a competitive candidate for a formal definition of privacy and has received considerable attention from both academic research [33, 17, 43, 36, 8] and industry adoption [20, 12, 37]. While increasing attention has been paid to bandit algorithms with joint differential privacy [34, 9], we introduce in this paper a more stringent notion, local differential privacy (LDP), in which users even distrust the server collecting the data, to contextual bandits.
*Equal contributions.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In contextual bandit, at each time round t with individual-specific context Xt, the decision maker can take an action at from a finite set (arms) to receive a reward randomly generated from the distribution depending on the context Xt and the chosen arm through its parameter θ?at which is not unknown to the decision maker. We use the standard notion of expected regret to measure the difference between expected rewards obtained by the action at and the best achievable expected reward in this round. While several papers consider the adversarial setting (i.e., Xt can be arbitrary determined in each round), this paper considers the stochastic contextual case where Xt is generated i.i.d. from a distribution PX . The goal is to maximize the rewards accumulated over the time horizon. An algorithm achieves LDP guarantee if every user involved in this algorithm is guaranteed that anyone else can only access her context (and related information such as the arm chosen and the reward) with limited advantage over a random guess. Recently there is an emerging steam of works combining LDP and bandit. [6, 29, 10] consider the LDP contextual-free bandit and design algorithms to achieve the same regret as in the non-privacy setting. For contextual bandits, [44] considers the adversarial setting. Despite their pioneering work, their regret bounds O(T 3/4) leave a gap from the corresponding non-privacy results O(T 1/2), which is conjectured to be inevitable. A natural question arises: can we close this gap for stochastic contextual bandits? In this paper, we design several algorithms and show that they can achieve the same regret rate in terms of T as in the non-private settings.
If we don’t assume any structure on the arms’ parameters, the above formulation is referred to as multi-parameter contextual bandits. If we impose structural assumptions such as all arms share the same parameter (see Section 2.2 for details), then the formulation is referred to as singleparameter contextual bandits. Although multi-parameter and single-parameter settings can be shown to be equivalent, they need independent analysis and design of algorithms because of their distinct properties based on different modeling assumptions (e.g., [27]). In this paper, we consider the privacy guarantee in both settings. In fact, multi-parameter setting is more difficult since we need to estimate the parameters for all K arms with sufficient accuracy to make good decisions. However, privacy protection also requires protecting the information about which arm is pulled in each round. Such a requirement hinders the identification of optimal arm and may incur considerable regret in the decision process. A proper balance between privacy protection and estimation accuracy is the key to design algorithms with desired performance guarantee in this setting.
Contributions. We organize our results for various settings in Table 1. Our main contributions can be summarized as follows:
1. We develop a framework for implementing LDP algorithms by integrating greedy algorithms with a private OLS estimator for linear bandits and a private SGD estimator for generalized linear bandits. We prove that our algorithms achieve regret bound matching the corresponding non-privacy results.
2. In the multi-parameter setting, to ensure the privacy of the arm pulled in each round, we design a novel LDP strategy by simultaneously updating all the arms with synthetic information instead of releasing the pulled arm. By conducting such synthetic updates for unselected arms, we protect the information of the pulled arm from being identified by the server or other users. This is at the cost of corrupting the estimation of the un-selected arms. To deal with this issue, we design an elimination method that is only based on data collected during a short warm up period. We show that such a mechanism can be combined with the OLS and SGD estimators to achieve the desired performance guarantees.
3. We introduce the SGD estimator to bandit algorithms to tackle generalized linear reward structure. To the best of our knowledge, few papers have ever considered SGD-based bandit algorithms. Theoretical regret bounds are established in [13] by combining SGD and Thompson Sampling, while most of the others are limited to empirical studies [7, 32]. We establish such theoretical regret bounds for SGD-based bandit algorithms. Our private SGD estimator for bandits is highly computationally efficient, and more importantly, greatly simplifies the data processing mechanism for LDP guarantee.

heading: 2 Preliminaries
text: Notations. We start by fixing some notations that will be used throughout this paper. For a positive integer n, [n] denotes the set {1, · · · , n}. |A| denotes the cardinality of the set A. ‖·‖2 is Euclidean norm. W (i, j) denotes the element in the i-th row and j-th column of matrix W . We write W > 0 if the matrix W is symmetric and positive definite. We denote Id as the d-dimensional identity matrix. Let ⊗ denote the Kronecker product. Let Bdr denote the d-dimensional ball with radius r and Sd−1r denotes the (d − 1)-dimensional sphere for the ball. Given a set A, Unif(A) denote the uniform distribution over A. For a tuple (Zi,j)i≤N,j≤M and 1 ≤ k1 < k2 ≤ M , we denote Zi,k1:k2 = (Zi,k1 , · · · , Zi,k2). We adopt the standard asymptotic notations: for two non-negative sequences {an} and {bn}, {an} = O({bn}) iff lim supn→∞ an/bn < ∞, an = Ω(bn) iff bn = O(an), an = Θ(bn) iff an = O(bn) and bn = O(an). We also write Õ(·), Ω̃(·) and Θ̃(·) to denote the respective meanings within multiplicative logarithmic factors in n.

heading: 2.1 Local Differential Privacy
text: Definition 2.1 (Local differential privacy). We say a (randomized) mechanism M : X → Z is (ε, δ)-LDP, if for every x 6= x′ ∈ X and any measurable set C ⊂ Z we have
P (M(x) ∈ C) ≤ eεP (M(x′) ∈ C) + δ. When δ = 0, we simply denote ε-LDP.
We now present some tools that will be useful for our analysis. Lemma 2.1 (Gaussian Mechanism [16, 19]). For any f : X → Rn, let σε,δ = 1ε supx,x′∈X ‖f(x)− f(x′)‖2 √ 2 ln(1.25/δ). The Gaussian mechanism, which adds random noise independently drawn from distribution N (0, σ2ε,δIn) to each output of f , ensures (ε, δ)-LDP.
Besides the Gaussian mechanism, we also use the following privacy mechanism for bounded vectors. Lemma 2.2 (Privacy Mechanism for l2-ball [14]). For anyR > 0, let rε,d = R √ π
2
eε + 1 eε − 1 dΓ(d+12 )
Γ(d2 + 1)
where Γ is the Gamma function. For any x ∈ BdR, consider the mechanism Ψε,R : BdR → Sd−1rε,d of generating Zx as the follows. First, generate a random vector X̃ = (2b− 1)x where b is a Bernoulli random variable with success probability 12 + ‖x‖2 2R . Next, generate random vector Zx via
Zx ∼ {
Unif{z ∈ Rd : zT X̃ > 0, ‖z‖2 = rε,d} with probability eε/(1 + eε), Unif{z ∈ Rd : zT X̃ ≤ 0, ‖z‖2 = rε,d} with probability 1/(1 + eε).
Then Ψε,R is ε-LDP and E[Ψε,R(x)] = x. Lemma 2.3 (Post-Processing property [19]). If M : X → Y is (ε, δ)-LDP and f : Y → Z is a fixed map, then f ◦M : X → Z is (ε, δ)-LDP. Lemma 2.4 (Composition property [19]). If M1 : X → Z1 is (ε1, δ1)-LDP and M2 : X → Z2 is (ε2, δ2)-LDP, then M = (M1,M2) : X → Z1 ×Z2 is (ε1 + ε2, δ1 + δ2)-LDP.

heading: 2.2 Local Differential Privacy in Bandit
text: We consider contextual bandits with LDP guarantee in the context of the user-server communication protocol described in Figure 1. The user in round t with context Xt ∈ Rd receives (processed) historical information St−1 from the server, and chooses an action at ∈ [K] to obtain a random reward rt = v(Xt, at) + t . Define Ft as the filtration of all historical information up to time
t, i.e., Ft = σ(X1, · · · , Xt, 1, · · · , t−1), and we require t is bounded and E[ t|Ft] = 0. Then the user processes the tuple (Xt, rt) by some mechanism ψ with LDP guarantee and send the processed information Zt = ψ(Xt, rt) to the server. After receiving Zt, the server updates the historical information St to get St+1. We consider the generalized linear bandits by allowing v(Xt, at) = µ(X T t θ ? at), where µ : R→ R is a link function and θ ? i ∈ Rd is the underlying parameter of the i-th arm. For a fix time t, we denote a∗t = arg maxi∈[K] µ(X T t θ ? i ). The regret over time
horizon T is Reg(T ) = ∑T t=1 ( µ(XTt θ ? a∗t )− µ(XTt θ?at) )
. If we don’t assume any structure on {θ?i }i∈[K], we refer it as the multi-parameter setting. We also consider d-dimensional single-param setting by assuming θ?i = ei⊗θ? for some θ? ∈ Rd where {ei}i∈[K] is canonical basis of RK . In this case, xt,i ∈ Rd is the i-th segment of Xt ∈ RdK and XTt θ?i = xTt,iθ?, so choosing arm i becomes choosing the i-th segment xt,i of the context.
In the rest of paper, we always assume that ‖θ?i ‖2 ≤ 1,∀i ∈ [K], the reward is bounded by cr and the Euclidean norm of the context is bounded by CB , our analysis can be easily generalized to the case where t and the context follow sub-gaussian distributions. In fact, when the context and noise are subgaussian, it is guaranteed by the subgaussian concentration that there are at least T −O(log T ) users have contexts and rewards bounded by C1,T , C2,T with overwhelming probability, so we can still use above LDP mechanisms to protect their privacy. For users whose contexts and reward are out of range C1,T , C2,T , they can send a private version of (0, 0) vector so that there is no privacy leakage. We also impose regularize assumptions on the link function, which are common in previous work [44, 31, 39] and the corresponding family contains a lot of commonly-use model, e.g., linear model, logistic model. Assumption 1. The link function µ is continuously differentiable, Lipschitz and there exists some ζ > 0 such that infx∈[−CB ,CB ] µ ′(x) = ζ > 0.

heading: 3 Single-Parameter Setting
text: In this section, we develop a LDP contextual bandit framework (Algorithm 1) by combining statistical estimation and privacy mechanisms in the single-param bandit setting to achieve optimal regret bound in various cases. We use an abstract privacy mechanism ψ in (1) and estimator ϕ in (2) to allow the plug-in of various components.

heading: 3.1 Privacy Guarantee
text: For the linear case where the link function µ(x) = x, we can use the following ordinary least square (OLS) estimator. Let with σε,δ = 2 √ 2 ln(1.25/δ)/ε. Define Mt = xt,atx T t,at + Wt where Wt is a random matrix with Wt(i, j) ∼ N (0, 4C2Bσ2ε,δ) and Wt(j, i) = Wt(i, j), and ut = rtxt,at + ξt where ξt is a random vector following distribution N (0, C2Bc2rσ2ε,δId). The OLS privacy mechanism and the corresponding estimator are
ψOLSt (xt,at , rt; θ̂t−1) = (Mt, ut), (3)
ϕOLSt (Z1, . . . , Zt; θ̂t−1) = ( t∑ i=1 Mi + c̃ √ tI )−1 t∑ i=1 ui, (4)
where c̃ > 0 is to be determined. We have the following LDP guarantee using the Gaussian mechanism (Lemma 2.1) and post-processing (Lemma 2.3).
Algorithm 1: LDP Single-parameter Contextual Bandit Input: Time horizon T ; Privacy Level ε, δ.
1 Initialization: Setting θ̂0 = 0. 2 for t← 1 to T do 3 User side: 4 Receive θ̂t−1 from the server. 5 Pull arm at = argmaxa∈[K]x T t,aθ̂t−1 and receive rt. 6 Generate Zt by Zt = ψt(xt,at , rt; θ̂t−1). (1)
7 Server side: 8 Receive Zt from the user. 9 Update the estimation via
θ̂t = ϕt(Z1, . . . , Zt; θ̂t−1). (2)
10 end
Proposition 3.1. Algorithm 1 with the private OLS update mechanism ψOLSt and estimator ϕOLSt is (ε, δ)-LDP for ε ∈ (0, 1].
For the general link function µ, its non-linearity adds to the difficulty in terms of both privacypreserving and bandits. To estimate parameters in generalized linear bandits, one common approach to use a maximum likelihood estimator (MLE) at each step. In contrast to OLS solution, MLE does not have a close form solution with simple sufficient statistics in general. Thus, solving an MLE optimization procedure requires using all the previous data points and conducting costly operations at each round, resulting in time complexity and memory usage increasing with time. Instead, we use a one-step stochastic gradient approximation to incrementally update the estimator with the new observation at each round. To obtain a LDP version of this approximation, we use the LDP l2-ball mechanism in Lemma 2.2.
ψSGDt (xt,at , rt; θ̂t−1) = Ψε,R (( µ(xTt,at θ̂t−1)− rt ) xt,at ) , (5)
ϕSGDt (Z1, . . . , Zt; θ̂t−1) = θ̂t−1 − ηtψSGDt . (6)
where ηt > 0 is the stepsize to be determined and R = 2crCB . Similarly, we can prove the following LDP guarrantee using the l2-ball mechanism Lemma 2.2 and post-processing Lemma 2.3.
Proposition 3.2. Algorithm 1 with the private SGD update mechanism ψSGDt and estimator ϕSGDt is ε-LDP.

heading: 3.2 Regret Analysis
text: To derive the regret bound of our framework, we need the following assumptions on the marginal distribution PX of the stochastic contexts {xt,a}a∈[K]. Assumption 2. There exists some κu > 0 such that λmax(Σa) ≤ κud where Σa is the covariance matrix of PX and λmax(Σa) is the largest eigenvalues of Σa. Assumption 3. For every ‖u‖2 = 1, denote a∗ = arg maxa∈[K] xTt,au, there exist some κl > 0, p∗ > 0 such that Pu((xT v)2 > κl/d) ≥ p∗ holds for any u, v ∈ Sd−11 , where Pu(·) is the distribution of xt,a∗ .
Similar assumptions are common in the analysis of single-parameter contextual bandits, e.g. [13, 22], and our conditions contain a wide range of distributions, including sub-gaussian with bounded density. See appendix A for discussion. Now we can show that our framework indeed achieves optimal regret bound. Theorem 3.1. Under Assumptions 2 and 3, with the choice of c̃ = 2σε,δ(4 √ d + 2 log(2T/α)) in (4), Algorithm 1 with OLS mechanism ψOLSt and estimator ϕ OLS t achieve the following regret with
probability at least 1− α for some constant C,
Reg(T ) ≤ C √ T (CB(σε,δ + σ )d
√ (d+ log(T/α)) log(KT/α)
κlp∗ + o(1))
Under Assumptions 1–3, with the choice of ηt = c′d/(κlζp∗t) for some c′ > 1 in (6), Algorithm 1 with SGD mechanism ψSGDt and estimator ϕ SGD t achieves the following regret with probability at least 1− α for some constant C,
Reg(T ) ≤ C √ T ( rε,d √ d
ζκlp∗ log log(T/α) + o(1)).
with o(1) means some factor that turns to 0 as T →∞.
In the algorithm we shift the sample covariance matrix by c̃ √ t to ensure the positive-definiteness of the noise matrix as in [34]. Such a shift guarantee the estimation accuracy in the early stage. Note that the optimal worst-case regret bound in the non-privacy case is Õ(T 1/2), our results show that we can achieve the same regret bound as in the non-privacy case in terms of time T . In fact, we can show a Ω( √ T/ε) lower bound in this setting even when K = 2, which verified our optimal dependence on both T and ε. Theorem 3.2. For θ ∈ Rd and an algorithm π, we denote E[Regπ(T ; θ)] the expectation regret of π when the underlying parameter is θ. When K = 2 and xt,a ∼ N (0, Id/d) are independent over a ∈ [K], we have for any possible ε-LDP algorithm π, supθ?:‖θ?‖2≤1 E[Regπ(T ; θ ?)] = Ω( √ T/ε).
Given the best known O(T 3/4) regret bound of adversarial contextual LDP bandit in [44], our O( √ T/ε) result points out a possible gap between stochastic contextual bandits and adversarial contextual bandits under the LDP constriant.
The bounds given above are problem-independent, which do not dependent on the underlying parameters. If we consider an additional assumption that there is a gap between the optimal arm and the rest, which is usually the case when the number of contexts is small, then we can obtain sharper bounds than the problem-independent ones in Theorems 3.1. Assumption 4 ((γ, β)-margin condition). We say PX satisfies the (γ, β)-strong margin condition with γ > 0, 0 < β ≤ 1, if for 4t := µ(xTt,a∗t θ ?) − maxj 6=a∗t µ(x T t,jθ
?) and h ∈ [0, b] with some positive constant b, we have P[4t ≤ h] ≤ γhβ . Theorem 3.3. Under Assumptions 2–4 with the same choice of c̃ in Theorems 3.1, Algorithm 1 with OLS mechanism ψOLSt and estimator ϕ OLS t achieves the following regret with probability at least 1− α for some constant C,
Reg(T ) ≤ C ·  γCB log T [( CBd(CBσ + σε,δ) √ d+ log(T/α) κlp∗ )2 + oβ,γ(1)], β = 1,
γCB 1− β T 1−β 2 [(
CBd(CBσ + σε,δ) √ d+ log(T/α)
κlp∗ )1+β + oβ,γ(1)], 0 ≤ β < 1.
Under Assumptions 1–4 and with the same choice of ηt in Theorems 3.1, Algorithm 1 with SGD mechanism ψSGDt and estimator ϕ SGD t achieves the following regret with probability at least 1− α for some constant C,
Reg(T ) ≤ C ·  γLCB log T [( rε,dLdCB √ log(log(T )/α) ζκlp∗ )2 + oβ,γ(1)], β = 1,
γLCB 1− β T 1−β 2 [(
rε,dLdCB √ log(log(T )/α)
ζκlp∗ )1+β + oβ,γ(1)], 0 ≤ β < 1.
with oβ,γ(1) being a factor depending on β, γ that converges to 0 as T →∞.
Unlike in the worst-case bound, it is more challenge to establish corresponding lower under the margin condition. A possible roadmap to show the Ω(log T/ε2) lower bound is to follow the argument in [21]: Their argument uses the Van-Tree inequality to bound the mean squared estimation error from below for each time to show the Ω(log T ) bound in non-private setting. To consider the influence of private noise, it is possible to combine the LDP-version Van-Tree inequality in [2] with the above argument to get Ω(log T/ε2) bound.

heading: 4 Multi-parameter Setting
text: In this section, we present our LDP framework for the multiple parameter setting. Compared with the single parameter setting, this framework introduces three non-trivial components to match classical regret bounds while still guarantee LDP: warm up, synthetic update and elimination.
Algorithm 2: LDP Multi-parameter Contextual Bandit Input: Time horizon T ; Warm up period length s0; Privacy Level ε, δ.
1 Initialization: Setting θ̂0,i = 0, i ∈ [K]. 2 for t← 1 to Ks0 do 3 User side: 4 Receiving θ̂t−1,1:K from the server. 5 Pulling arm at := (t mod K) + 1 and receive rt. 6 Generate and update Zt,i = 1{at = i}ψt(Xt, rt; θ̂t−1,i), i ∈ [K] to the server. 7 Server side: 8 Receive the update Zt,1:K from the user. 9 Re-estimate parameters via θ̂t,i := ϕt(Z1,i, . . . , Zt,i),∀i ∈ [K].
10 end 11 for t← Ks0 + 1 to T do 12 User side: 13 Receive θ̂t−1,1:K from the server. 14 Determine a subset K̂t of [K] by setting
K̂t := {a ∈ [K] : XTt θ̂Ks0,a > max a∈[K]
XTt θ̂Ks0,a − h
2 } (7)
15 Pulling arm at := argmaxa∈K̂tµ(X T t θ̂t−1,a) and receive rt. 16 Generating information for all arms {Zi,t}i∈[K] by setting
Zi,t = { ψt(Xt, rt; θ̂t−1,i) if at = i, ψt(0, 0; θ̂t−1,i) otherwise.
17 Server side: 18 Receive the update {Zi,t}i∈[K] from the user. 19 Re-estimate parameters via
θ̂t,i := ϕt(Z1,i, . . . , Zt,i).
20 end
Warm up. In the warm up stage, all arms are given equal opportunities to be explored for a preliminary estimation of their parameters. Such estimation does not aim for the accuracy to select the optimal arm with high probability. Instead, we only need accuracy at the level of ruling out the substantially inferior arms. Thus, this stage only needs O(log T ) steps.
Since the actions in this stage are independent of the contexts, there is no need to protect the pulled arm. However, we still need to protect the contexts by using a privacy mechanism similar in the single-parameter setting.
Synthetic update. After the warm up, we need to make decisions based on the contexts to achieve vanishing regret. In order to obtain the privacy guarantee, we introduce our synthetic update mechanism. Although in each time only one arm is pulled, we create synthetic data for all unselected arms. In this way, the server receives synthetic feedback about all arms, regardless of whether it is selected or not, and thus cannot figure out which one is selected.
Another method to provide LDP protection for the selected arm is to ensure the action at satisfies LDP. However, the regret will grow linearly, as shown in [34].
Elimination. We use the information obtained during warm up to exclude obviously inferior arms. Such a method has been applied in [5] to guarantee a certain kind of independence of the information in each round. However, we use this method for a different purpose. The necessity of such an elimination strategy comes from protecting privacy in the multi-parameter setting. Although we have obtained an estimation to a certain level of accuracy in the warm up stage, our knowledge on un-selected arms will be gradually corrupted by the noise incurred in the synthetic update in each round. Such corruption will make us fail to distinguish arms that are possibly optimal from the surely sub-optimal ones. To avoid corruption, we may need to pick the sub-optimal arms frequently but this will result in large regret. That is why we use the warm up information to eliminate the arms with extremely poor performance as in (7).

heading: 4.1 Privacy Guarantee
text: The OLS/SGD mechanisms and estimators are the same as (3)–(6) in the single-parameter setting. To prevent the server from distinguishing the selected arm from the other K − 1 arms, a straightforward idea is to use (ε/K, δ/K)-LDP mechanism for the synthetic update by composition property in lemma 2.4. However, we can prove that our algorithm can still achieve the same LDP guarantee with a much less stringent privacy mechanism, say (ε/2, δ/2)-LDP, in Propositions 4.1 and 4.2. Proposition 4.1. Algorithm 2 with the private OLS update mechanism ψOLSt and estimator ϕOLSt is (ε, δ)-LDP. Proposition 4.2. Algorithm 2 with the private SGD update mechanism ψSGDt and estimator ϕSGDt is ε-LDP.

heading: 4.2 Regret Analysis
text: Assumption 5 (Diversity condition). Let Kopt and Ksub be a partition of [K] such that for any i ∈ Ksub, µ(XT θi) < maxj 6=i µ(XT θj) − hsub for some hsub > 0 and every X ∈ X . For any i ∈ Kopt define the set Ui := {X : µ(XT θi) > maxj 6=i µ(XT θj)}. There exists κl > 0, p′ > 0 such that for all i ∈ Kopt and unit vector v,P((vTX)21{X ∈ Ui} ≥ κl/Kopt) > p′. Assumption 6 ((γ, β)-margin condition). This is almost identical to Assumption 4 except that we replace4t with4t := µ(XTt θa∗t )−maxj 6=a∗t µ(X T t θj).
In our algorithm, diversity condition guarantees that conditioning on the arm i is pulled, the distribution of Xt still can provide enough information about θi. We would remark here that we need no longer any deterministic gap in the definition of Ui, which weakens the assumption made in [4],[5]. Now we are in the suited position to present our theoretical guarantee of the algorithm. Theorem 4.1. Under Assumptions 1, 5 and 6, with the choice of c̃ = 2σε/2,δ/2(4 √ d+2 log(2TK/α)) in (4), s0 = C ·K( CBσ + σε,δ
min{λ0, h}p′κl )2(d + log(TK/α)) and h = hsub, λ0 = (2γLCB)−1(
p′ 2 )1/β ,
Algorithm 2 with OLS mechanism ψOLSt and estimator ϕ OLS t achieve the following regret with probability at least 1− α for some constant C,
Reg(T ) ≤ γCCB [(KCB(CBσ + σε,δ)√d+ log((TK)/α) κlp′ )1+β + ohsub,β,γ(1) ] ·  log T, β = 1, T 1−β 2
1− β , 0 < β < 1.
Under Assumptions 1, 5 and 6, with the choice of step-size
ηt := (1{t≤Ks0}((t mod K) + 1) + 1{t>Ks0}(t− (K − 1)s0)) −1Kopt(ζκlp ′)−1c′
for any c′ ≥ 1 and h = hsub, Algorithm 2 with SGD mechanism ψSGDt and estimator ϕSGDt achieve the following regret with probability at least 1− α for some constant C,
Reg(T ) ≤ γLCCB [(Krε,dLCB√log((TK log T )/α) ζκlp′ )1+β + ohsub,β,γ(1) ] ·  log T, β = 1, T 1−β 2
1− β , 0 < β < 1.
Theorem 4.1 recovers the non-privacy bound in [5] under similar condition up to a logarithmic factor. Notice that unlike Theorem 3.3 in the single-parameter case, we cannot establish the regret when
β = 0. The reason is that in our analysis, we need the probability of 4t > h vanish as h → 0 to guarantee the estimation error for θi, i ∈ Kopt converges. The corresponding theoretical result in this setting when β = 0 is left as an open question.

heading: 5 Experiment
text: To the best of our knowledge, the contextual bandit algorithms with LDP guarantee has only been studied by [44], who propose a variant of LinUCB algorithm for linear bandits and a variant of Generalized Linear Online-to-confidence-set Conversion (GLOC) framework [23] for generalized linear bandits. We refer their methods as LDP-UCB and LDP-GLOC. We call our method LDP-OLS if we plug in the OLS mechanism and estimator into Algorithms 1 and 2, and LDP-SGD if we plug in the SGD ones. We evaluate all the four methods on two different privacy levels ε = 0.5 and 1 in synthetic datasets, which are industry standards. For example, Apple uses ε = 4 in their projects on Emojis and Safari usage [38]. Similar choices of the privacy parameter ε can be found in [3, 20]. We also demonstrate the efficacy of our algorithms with real data on Auto Lending2 in Appendix G. For the sake of comparison, the learning step parameter for LDP-GLOC and LDP-SGD are tuned in the same way.3. The first and second columns in Figure 4 are for single-param and multi-param settings, respectively, which are simulation studies on linear bandits. The context is generated from Unif(Sd−11 ) at each round.
In conclusion, our methods significantly outperform existing ones in all settings consistently. LDPSGD achieves better performance under more strigent privacy requirements.
2On-Line Auto Lending dataset CRPM-12-001 provided by Columbia University https://www8.gsb. columbia.edu/cprm/research/datasets, and has been used in the study of contextual bandits by [26, 11].
3The source code to reproduce all the results is available at the GitHub repo liangzp/LDP-Bandit.

heading: 6 Conclusion
text: In this paper, we propose LDP contextual bandit frameworks in both single-parameter and multiparameter settings with flexibility to deal generalized linear reward structure, and establish theoretical guarantee of our algorithms based on the frameworks. Our algorithms are highly efficient and have superior empirical performance. There are still some open questions to be explored. Whether our regret bounds are optimal in terms of ε in the multi-parameter setting is still unknown. It will be interesting to explore estimators and mechanisms beyond the private OLS and SGD ones to study the optimality in terms of ε. Moreover, whether there is a fundamental limit in adversarial contextual bandit under LDP constraints is still an open question. It also remains an open question to analyze the regret bound in the multi-parameter setting when β = 0 in the margin condition.
Acknowledgments and Disclosure of Funding
This work was supported by Hong Kong Research Grant Council (Grants 16317416, 16204718, 16214121) and Guangdong-Hong Kong-Macao Joint Laboratory for Data-Driven Fluid Mechanics and Engineering Applications.

Review summaries:
The paper studies (generalized) linear contextual bandits in the context of local differential privacy (DP). At every time step a single user’s sensitive data point arrives, which serves as a context, and a reward is sampled as a function of this context and an unknown (generalized) linear reward-generating function. The difficulty with minimizing regret with local DP is that one has to learn the reward-generating function without compromising users’ privacy. The analysis is split by cases: in the setting of linear rewards, an OLS-based solution is proposed, and in the setting of generalized linear rewards, an SGD-based solution is proposed. In addition, two different bandit models are considered depending on whether the rewards from different arms are related.

Authors design LDP algorithms for stochastic generalized linear bandits to achieve the same regret bound as in non-privacy settings. The main idea is to develop a stochastic gradient-based estimator and update mechanism to ensure LDP. They also develop an estimator and update mechanism based on Ordinary Least Square (OLS) for linear bandits. Finally, they conduct experiments with both simulation and real-world datasets to demonstrate the consistently superb performance of algorithms to ensure strong privacy protection. 

This paper proposes to design and analyze algorithms for generalized linear bandits with local differential privacy (LDP). The main idea is to design a stochastic gradient based estimator to ensure LDP. It is show, by a comparison to the lower bound that the worst-case results contained herein are close to optimal. 

This paper studies the local differential privacy (LDP) problem for stochastic generalized linear bandits. They develop the Stochastic Gradient Descent and Ordinary Least Square estimators and update mechanism for generalized linear bandits and linear bandits with privacy guarantee. The regret bound is proved to be the same as in non-privacy settings.