Multi-Armed Bandits with Local Differential Privacy

Introduction

The multi-armed bandit (MAB) problem provides a classic model for abstracting sequential decision making under uncertainty, and has attracted a wide range of interest in various areas, such as communication networks, online advertising, clinical trials, product testing, etc. In an MAB model, there is a set of arms, and each pull of an arm generates a random reward according to some unknown latent distribution of this arm. The agent adaptively chooses arms to pull according to past observations in order to achieve some goal. A widely studied goal is regret minimization, where the regret is the expected gap between a proposed algorithm and an optimal algorithm that knows the latent distributions. To minimize the regret, the agent needs to balance the trade-off between exploration and exploitation, where exploration refers to learning the environment and exploitation refers to pulling the best arm according to the current knowledge.

In recent years, users have become increasingly concerned about protecting their private online information and activities, which may include their personal profiles, browsing histories, and activities on the Internet. They may not want to share this information with other parties. However, many real-world systems like medical experiments, recommender systems, advertisement allocators, online shopping websites, and search engines need such data to learn critical matters and provide better services. To handle this dilemma, there is a compelling need to develop algorithms that can optimally trade off system performance and the privacy level provided to the users.

A widely accepted and applied metric to measure the privacy level is the differential privacy (DP) , which, in theory, guarantees that it is difficult for any party or eavesdropper to determine whether or not an individual is listed in a private database. DP algorithms have been studied in many areas, such as data release , optimization , and Q-learning , just to name a few. However, DP remains under-explored in the MAB settings.

Here, we take clinical trials as a concrete example to illustrate the use of DP in MAB. In an experiment of an illness with multiple treatments (aka arms), the experimenter (aka agent) wants to sequentially choose treatments for patients (aka individual users) based on past observations on treatment effects. This problem can be viewed as an MAB regret minimization problem. However, the patients may not be willing to share the actual effects of the treatments with the experimenter due to privacy concerns. By the DP bandit algorithms, the actual effects will not be known by the experimenter, which provides a certain level of privacy guarantee to all patients, while also enabling the experimenter to learn from the observations efficiently.

The above example fits the local differentially private (LDP) bandit model . Different from the DP bandit model, in the LDP setting there is no trusted centroid curator . In this paper, we assume that each user has its own curator (or privacy mechanism) that can do randomized mapping on its data to provide privacy guarantee. This curator can be softwares or plugins embedded in the user’s devices or terminals, and the non-private data will not leave the control of the user unless they are processed by the user’s curator.

Another example of LDP MAB is shopping websites, which also indicates the necessity of the LDP setting instead of the DP setting: The server wants to sequentially choose products to recommend according to the users’ past purchase histories, while some users are not willing to share this information as the purchase histories may reveal private information (e.g., a person who buys a lot of heart-disease medicines is more likely to have related illness). In this scenario, it is unlikely that there is a third-party centroid curator that can gain access to all the purchase data, sine these data are commonly viewed as a valuable property for the company’s business success. In the literature, the DP bandit problems have been studied in different settings , while the LDP bandit problem remains under-explored.

2 Problem formulation

The goal of the agent is to minimize the regret.

Before we define local differential privacy, we provide some preliminary definitions. We first introduce the notion of $\epsilon$-differential privacy . We define the neighboring data records as any two records that differ by only one entry.

The above inequality must also hold if we switch $x$ and $x^{\prime}$.

This definition implies that for any neighboring records, after an $\epsilon$-DP mechanism, their statistical behaviors are similar. Hence, it is difficult for any party to determine which record is the source of the given output. Smaller values of $\epsilon$ implies higher levels of privacy. When $\epsilon=\infty$, there is no privacy.

This paper focuses on the LDP bandit model, which can be described as follows: We split the parties into three categories: the agent, the curators, and the users. The users do not trust the agent. The curators stand between the users and the agent, providing privacy to the users and also help the agent to minimize the regret. In each iteration, the agent makes a decision on which arm to pull according to the knowledge of past private responses and sends a request to a user’s curator. The curator then “pulls the arm” (e.g., awaiting the activity of the user), receives the reward, and returns a private response to the agent. In the LDP bandit model, the curators do not aggregate the rewards of the arms. To this end, for random vectors $X$ and $Y$, we use $X\in\sigma(Y)$ to represent that $X$ is determined by $Y$ plus some random factors independent of $Y$ and the bandit instance. In the following definition, it implies that the agent does not know the actual rewards. The formal definition of the LDP bandit model is stated in Definition 2, where $\mathcal{D}$ is the domain of the rewards.

3 Related work

Non-private MAB problems have been studied for decades. For non-private bandit problems, either frequentist methods like UCB (Upper Confidence Bound) or Bayesian methods like Thompson Sampling have been shown to achieve optimal regret performance (up to constant factors). For a literature review on MAB, we refer readers to . Recently, privacy issues have received increasing attention in the machine learning community. Differential privacy provides a quantitative metric to measure the privacy level and has been gaining popularity. We refer readers to that introduces the fundamental concepts and methods of DP.

To the best of our knowledge, the earliest work that studied LDP bandits is , which proposed an LDP bandit algorithm that works for arms with Bernoulli rewards. In comparison, our algorithms can work for a much more general set of instances. The other work that studied the LDP bandit problem is , in which distribution-dependent and distribution-free regret lower bounds were proved. We note that the distribution-dependent regret lower bound in is looser than the one proved in this paper.

Besides the LDP bandit mode, there have been other works on MAB problems with other types of DP guarantees . These works are not directly comparable to our work, and so we give a brief introduction here. In the bandit models of , it is difficult for the agent to learn individual rewards from the private empirical means, i.e., the curator can aggregate the rewards from different users. In the bandit models of , it is difficult for any adversary to learn the individual rewards from the sequence of actions taken by the agent, i.e., the agent is trusted. This model is named the sequential DP bandits in . In the bandit models of , it is difficult for any adversary to learn the context features in a contextual bandit setting, which we name it as environmental DP bandits. In , the authors studied privacy-preserving adversarial bandits.

4 Main results

Our key contributions are summarized as follows:

We prove a tight regret lower bound (up to a constant factor) for the LDP bandit problem.

For bandits with bounded rewards, we propose a Laplace mechanism and a Bernoulli mechanism, and develop corresponding UCB algorithms for them, both of which match the lower bound proved in this paper (up to constant factors).

For bandits with unbounded support and i.i.d. Term “i.i.d.” stands for “identically independent distributed”. sub-Gaussian noises, we use a Sigmoid preprocessing and obtain algorithms with tight regret upper bounds (up to constant factors).

Lower bound

Let $\epsilon>0$ be given. Assume that the rewards of all arms follow Bernoulli distributions. The regret $R(T)$ of any $\epsilon$-LDP policy satisfies

When $\epsilon\rightarrow 0$, since $e^{\epsilon}-e^{-\epsilon}\simeq 2\epsilon$, we have $\liminf_{T\rightarrow\infty}\frac{R(T)}{\log{T}}\gtrsim\frac{1}{4\epsilon^{2}}\sum_{a:\Delta_{a}>0}\frac{1}{\Delta_{a}}$.

Algorithms and upper bounds

In this section, we propose two $\epsilon$-DP mechanisms: one is to convert bounded rewards to Laplace responses, and the other is to convert bounded rewards to Bernoulli responses. After converting the rewards to private responses, the agent uses UCB-like methods, e.g., , to trade off the exploration and exploitation. Although the agent has no access to the actual rewards of the arms, it can bound the number of pulls of any suboptimal arm by similar techniques as the non-private UCB algorithms. Based on both mechanisms, the private UCB algorithms can achieve optimal regrets (up to constant factors). In this paper, we adopt the Hoeffding bounds in to bound the empirical mean rewards. We note that one may use other confidence bounds by which one may get better constant factors, but this is beyond the scope of this paper. From the theoretical perspective, the Hoeffding bounds in can already achieve optimal regrets in order sense.

The Laplace mechanism (i.e., adding Laplace noises to data records) is a widely used mechanism in the areas of DP. The key idea of the Laplace mechanism is to add an independent Laplace$(\frac{1}{\epsilon})$ noise to each reward, which preserves $\epsilon$-DP and does not change the mean values of the records. For any $b>0$, the PDF of the Laplace$(b)$ distribution is defined as:

The mean of Laplace$(b)$ distribution is , and its variance is $2b^{2}$. The Laplace mechanism is stated in Curator 1 and its theoretical guarantee is stated in Lemma 2.

Curator CTL (i.e., $M_{L}$) is $\epsilon$-DP on $$.

With CTL, we develop a UCB algorithm that takes the private responses of CTL as the input. Note that since CTL adds a Laplace noise to each reward, we need an additional term to bound the summations of independent Laplace random values. We adopt the concentration inequality used in , which is stated in Lemma 3.

The corresponding UCB algorithm, termed LDP-UCB-L (LDP UCB algorithm with the Laplace mechanism), is described in Agent 2. In Line 3, the term $\sqrt{({2\log{t}})/{N^{t}_{a}}}$ is the Hoeffding bound for bounding the summation of independent bounded random variables and the term $\sqrt{(32\log{t})/(N^{t}_{a}\epsilon^{2})}$ is for bounding the summation of independent Laplace variables, which is derived from Lemma 3. The theoretical guarantee of LDP-UCB-L is stated in Theorem 4 and the proof is relegated to the supplementary material due to space limitation.

LDP-UCB-L is $\epsilon$-LDP. Its distribution-dependent regret is at most

and its distribution-free regret (for $T\geq n$) is at most $O(\epsilon^{-1}\sqrt{nT\log{T}})$.

Remark. i) Compared to non-private UCB using the same confidence bounds , the regret of LDP-UCB-L is increased by a $(1+4/\epsilon)^{2}$ factor, which can be viewed as the cost for preserving privacy. When $\epsilon$ approaches infinity, this factor approaches one, and the regret approaches that of the non-private version. ii) According to Theorem 1, the distribution-dependent regret of LDP-UCB-L is optimal (up to a constant factor). iii) In [4, Theorem 1], a distribution-free lower bound $\Omega(\epsilon^{-1}\sqrt{nT})$ was given, and thus the distribution-free regret of LDP-UCB-L is optimal up to a $\sqrt{\log{T}}$ factor.

1.2 Bernoulli mechanism

In addition to the Laplace mechanism, we propose another mechanism called Convert-to-Bernoulli (CTB), which converts bounded rewards to Bernoulli responses. Both the theoretical analysis and the empirical results indicate that the Bernoulli mechanism performs better than the Laplace mechanism.However, if we can find tighter concentration bounds on the summation of independent Laplace variables, then we may get better regret bounds for the Laplace mechanism.

In , the authors proposed a similar mechanism that only works for Bernoulli rewards. By contrast, in this paper, we allow the reward to be an arbitrary value in $$. CTB is described in Curator 3. Its theoretical guarantee is stated in Lemma 5, and the proof is left to the supplementary material.

Curator CTB (i.e., $M_{B}$) is $\epsilon$-DP on $$, and the returned value follows the Bernoulli distribution with mean$\mu_{a,\epsilon}:=\frac{1}{2}+(2\mu_{a}-1)\cdot\frac{e^{\epsilon}-1}{2(e^{\epsilon}+1)}$.

We can view CTB as a procedure that converts an arm $a$ to a Bernoulli arm with mean $\mu_{a,\epsilon}$. By CTB, we take the converted arms as inputs to non-private UCB algorithms, and obtain an LDP UCB algorithm called LDP-UCB-B (LDP UCB algorithm with the Bernoulli mechanism), which is described in Agent 4. By similar insights as in the non-private UCB algorithms, we can bound the number of pulls of each suboptimal arm, and hence, upper bound the regret. The theoretical guarantee is stated in Theorem 6 and the proof is relegated to the supplementary material.

LDP-UCB-B$(\epsilon)$ is $\epsilon$-LDP. Its distribution-dependent regret is at most

and its distribution-free regret (for $T\geq n$) is at most $O(\epsilon^{-1}\sqrt{nT\log{T}})$.

Remark. i) Compared to non-private UCB algorithms using the same confidence bounds , the regret of LDP-UCB-L is increased by a $(\frac{e^{\epsilon}+1}{e^{\epsilon}-1})^{2}$ factor, which can be viewed as the cost for preserving privacy. When $\epsilon$ approaches infinity, this factor approaches one, and the regret approaches that of the non-private version. ii) According to Theorem 1, the distribution-dependent regret of LDP-UCB-B is optimal (up to a constant factor). iii) In [4, Theorem 1], a distribution-free lower bound $(\Omega(\epsilon^{-1}\sqrt{nT}))$ was given, and thus the distribution-free regret of LDP-UCB-B is optimal up to a $\sqrt{\log{T}}$ factor. iv) The $\epsilon$-term $(\frac{e^{\epsilon}+1}{e^{\epsilon}-1})^{2}$ of LDP-UCB-B is always smaller than $(1+\frac{4}{\epsilon})^{2}$, that of LDP-UCB-L. When $\epsilon$ increases, the difference becomes smaller, and when $\epsilon$ approaches infinity, they all converge to one. Later, the numerical results will also indicate that LDP-UCB-B’s empirical performance tends to be better than that of LDP-UCB-L and the difference tends to be smaller as $\epsilon$ increases.

2 Mechanisms for MAB with unbounded reward supports

In practice, the rewards may not have bounded supports, and the mechanisms studied in the last subsection do not work in this situation. For the Laplace mechanism, adding Laplace$(s/\epsilon)$ noise to the rewards does not provide $\epsilon$-DP if the difference between two rewards is larger than $s$. For the Bernoulli mechanism, when $r<0$ or $r>1$, the value $(re^{\epsilon}+1-r)/(e^{\epsilon}+1)$ is outside of $$, making the Bernoulli mechanism ill-defined.

After the Sigmoid mapping, the new mechanism maps the Sigmoid values to CTL or CTB. We name these two new mechanism as CTL-S (CTL with Sigmoid preprocessing) and CTB-S (CTB with Sigmoid preprocessing). They are described in Curators 5 and 6, respectively, and their theoretical guarantees are stated in Lemmas 8 and 9. With these two new mechanisms, we develop new LDP UCB algorithms LDP-UCB-LS (LDP-UCB-L with Sigmoid preprocessing) and LDP-UCB-BS (LDP-UCB-B with Sigmoid preprocessing) for bandits with unbounded reward supports, whose theoretical guarantees are stated in Corollaries 10 and 11, respectively.

Curator CTL-S (i.e., $M_{LS}$) is $\epsilon$-DP. For two arms $a$ and $b$ with mean rewards $\mu_{a}\geq\mu_{b}$, the difference between the expected responses of CTL-S$(\epsilon)$ on arms $a$ and $b$ is at least $c_{s}(\mu_{a}-\mu_{a})$, where $c_{s}>0$ is a universal constant.

Curator CTB-S (i.e., $M_{BS}$) is $\epsilon$-DP. For two arms $a$ and $b$ with mean rewards $\mu_{a}\geq\mu_{b}$, the difference between the expected responses of CTB-S$(\epsilon)$ on arms $a$ and $b$ is at least $c_{s}(\mu_{a,\epsilon}-\mu_{a,\epsilon})$, where $c_{s}>0$ is a universal constant.

Replacing CTL in LDP-UCB-L by CTL-S, we get LDP-UCB-LS. LDP-UCB-LS is $\epsilon$-LDP. Its distribution-dependent regret is at most

where $c_{s}>0$ is a universal constant. Its distribution-free regret is at most $O(\epsilon^{-1}\sqrt{nT\log{T}})$.

Replacing CTB in LDP-UCB-B by CTB-S, we get LDP-UCB-BS. LDP-UCB-BS is $\epsilon$-LDP. Its distribution-dependent regret is at most

where $c_{s}>0$ is a universal constant. Its distribution-free regret is at most $O(\epsilon^{-1}\sqrt{nT\log{T}})$.

Numerical results

In this section, we illustrate the numerical results for our algorithms. Due to space limitation, we only present the results for bandits with bounded supports. The results for bandits with unbounded supports can be found in the supplementary material. To the best of our knowledge, there is no previous LDP bandit algorithm in the literature except in . However, the algorithm in only works for Bernoulli rewards and can be viewed as a special case of our Bernoulli mechanism. Thus, the only LDP bandit algorithms we present are LDP-UCB-L and LDP-UCB-B. We also include the performance of the non-private UCB algorithm (i.e., $\epsilon=\infty$) as a baseline to see the cost for preserving $\epsilon$-LDP. Here, we use the UCB1 algorithm in as the baseline since our private algorithms adopt the same confidence bounds as in . The codes can be found in the supplementary material.

The numerical results are illustrated in Figure 1. In all the experiments, we set the number of arms $n=20$. The best arm has a mean reward $0.9$; five arms have mean rewards $0.8$; five arms have mean rewards $0.7$; five arms have mean rewards $0.6$; and four arms have mean rewards $0.5$. In Figure 1 (a) to (d), we use Bernoulli arms, i.e., the rewards of all arms follow Bernoulli distributions. In Figure 1 (e) (f), the rewards of arms follow different types of distributions to show that our algorithms work beyond Bernoulli arms. To be specific, arms with mean rewards $0.9$ or $0.6$ generate rewards from Bernoulli distributions; arms with mean rewards $0.8$ generate rewards from Beta$(4,1)$ distribution; arms with mean rewards $0.7$ generate rewards from $\{0.4,1\}$ uniformly at random; and arms with mean rewards $0.5$ generate rewards from $$ uniformly at random. Each line in each figure is averaged over 50 independent trials.

In Figure 1 (a), we fix $\epsilon=2.0$. We can see that the regret of LDP-UCB-B is slightly larger than that of the non-private UCB and smaller than that of LDP-UCB-L. The ratio of the regrets of LDP-UCB-B to non-private UCB is $1.6$, and that of LDP-UCB-L is $8.5$. In theory, the upper bounds of the ratios are $(\frac{e^{\epsilon}+1}{e^{\epsilon}-1})^{2}=1.7$ for LDP-UCB-B and $(1+\frac{4}{\epsilon})^{2}=9.0$ for LDP-UCB-L. Thus, the numerical results in Figure 1 (a) are consistent with our theoretical results. In Figure 1 (b), we fix $\epsilon=0.2$. The ratio of the regret of LDP-UCB-L (LDP-UCB-B) to non-private UCB becomes much larger, which is consistent with the theory that the ratio grows with $(1+\frac{4}{\epsilon})^{2}$ ($(\frac{e^{\epsilon}+1}{e^{\epsilon}-1})^{2}$). In theory, the ratios are upper bounded by $441$ and $101$, respectively, which are larger and not far away from the empirical results.

In Figure 1 (c), we compare the regrets of LDP-UCB-L with different $\epsilon$-values. In Figure 1 (d), we do the same for LDP-UCB-B. From (c) and (d), we can see that the regrets of LDP-UCB-L and LDP-UCB-B both increase with $\frac{1}{\epsilon}$ and the convergence speed both decrease as $\epsilon$ decreases. In Figure 1 (e) and (f), the rewards of the arms follow different types of rewards, and the performances of LDP-UCB-L and LDP-UCB-B are similar to that for Bernoulli arms, which indicates that our algorithms work for arms with various types of latent distributions.

Conclusion

This paper studied the multi-armed bandit problem with local differential privacy guarantee. We proved the tight regret lower bound and proposed algorithms with tight regret upper bounds (up to constant factors). Numerical results also confirmed our theoretical results.

References

Appendix A Proofs

Now, we let $a$ be an arm with Bernoulli$(p)$ rewards and $b$ be an arm with Bernoulli$(q)$ rewards. Without loss of generality, we assume $p\geq q$. Let $h_{a}$ be the PDF of the output of CTB$(\epsilon)$ on arm $a$ and $h_{b}$ be the PDF of the output of CTB$(\epsilon)$ on $b$. We have

Let $\Omega_{f}$ be the support of $f$ and $\Omega_{g}$ be the support of $g$. Since $M$ is $\epsilon$-DP, we have

which also implies $\Omega_{f}=\Omega_{g}$. To simplify notation, we let $\Omega=\Omega_{f}=\Omega_{g}$.

The key to the proof is to show the following lemma.

Thus, for any suboptimal arm $a$ and $\epsilon$-DP randomized mapping $M$, we have

Since the bandit algorithm only has access to the private responses, i.e., $A^{t+1}\in\sigma(A^{1},A^{2},...,A^{t},M(R^{1}),M(R^{2}),...,M(R^{t}))$ for any time $t$, by Theorem 2 in , we conclude that if

A.2 Proof of Theorem 4

The $\epsilon$-LDP of LDP-UCB-L follows from the the $\epsilon$-DP of CTL stated in Lemma 2.

By the Chernoff-Hoeffding inequality , for any arm $a$, positive integer $k$, and time $t$, we have

Also, for any time $t$ and positive integer $k>4\log{t}$, setting $\nu=\sqrt{\sum_{r=1}^{k}(1/\epsilon)^{2}}=\sqrt{k}/\epsilon$ and $\lambda=\sqrt{({32k\log{t}})/{\epsilon^{2}}}$, we have $\lambda<\sqrt{8k^{2}/{\epsilon^{2}}}=2\sqrt{2}\epsilon\nu^{2}=2\sqrt{2}k/\epsilon$, which by Lemma 3 implies

Therefore, for any arm $a$, time $t$, and positive integer $k>4\log{t}$, we have

Here, we note that the above inequalities hold only if $k>4\log{t}$ as required by Lemma 3. This is the reason why we have Lines 5 and 6 in the algorithm LDP-UCB-L.

Also, since $\Delta_{a}\leq 1$, we have $v_{a,t}>4\log{t}$.

For any suboptimal arm $a$ and time $t$, we have

Recall that $A^{t}$ is the $t$-th arm to be pulled and note that for any round $t>n$ and suboptimal arm $a$ with $N^{t}_{a}>4\log{t}$, arm $a$ is pulled only if $u^{t}_{a}\geq u^{t}_{a^{*}}$. Therefore, we have

where (a) is due to $v_{a,t}=\frac{8(1+4/\epsilon)^{2}\log{t}}{\Delta_{a}^{2}}$ and $v_{a,t}>4\log{t}$ for all arms $a$ ($\Delta_{a}\leq 1$ always holds) and time $t$.

Thus, the (expected) regret of LDP-UCB-L is at most

The proof of the distribution-dependent regret is complete.

By choosing $\alpha=\Theta(\sqrt{\frac{n\log{T}}{T\epsilon^{2}}})$ and recalling $T\geq n$, the regret is upper bounded by

This completes the proof of the distribution-free regret, and the proof of Theorem 6 is complete. ∎

A.3 Proof of Lemma 5

Let arm $a$ with mean reward $\mu_{a}$ and privacy parameter $\epsilon>0$ be given. Let $R$ denote the reward received by pulling the arm and use $X$ to denote the output (returned value) of CTB$(\epsilon)$. We have $X=M_{B}(R)$. The value of $X$ is either $1$ or , and thus, $X$ follows some Bernoulli distribution.

Let $r,r^{\prime}$ in $$ be given. Observe that

This proves the mean of the returned value.

Thus, by the definition of $\epsilon$-DP stated in Definition 1, we conclude that CTB is $\epsilon$-DP. This completes the proof. ∎

A.4 Proof of Theorem 6

The $\epsilon$-LDP of LDP-UCB-B follows from the $\epsilon$-DP of CTB stated in Lemma 5.

Distribution-dependent regret. According to Lemma 5, for any arm $a$, the private response generated by CTB$(a,\epsilon)$ follows the Bernoulli$(\mu_{a,\epsilon})$ distribution, where

Define $\mu^{*}_{\epsilon}:=\max_{a\in[n]}\mu_{a.\epsilon}$ and

for any arm $a$ in $[n]$. We note that $\Delta_{a}>0$ if and only if $\Delta_{a,\epsilon}>0$. An arm $a$ is said to be optimal if $\Delta_{a}=0$, and is said to be suboptimal if $\Delta_{a}>0$.

For any suboptimal arm $a$ and time $t$, we have

Also, by the Chernoff-Hoeffding Inequality , for any suboptimal arm $a$, time $t$, and positive integer $k\leq t$, we have

Note that at any round $t>n$ and for any suboptimal arm $a$, $a$ is pulled only if $u^{t}_{a}\geq u^{t}_{a^{*}}$. Thus, setting $v_{a,t}=\frac{8\log{t}}{\Delta_{a,\epsilon}^{2}}$, we have

Thus, the (expected) regret of LDP-UCB is at most

The proof of the distribution-dependent regret is complete.

Distribution-free regret. Similar to the proof of the distribution-dependent regret, we have $\Delta_{a,\epsilon}=(\frac{e^{\epsilon}-1}{e^{\epsilon}+1})\Delta_{a}=\Omega(\epsilon\Delta_{a})$ and

By choosing $\alpha=\Theta(\sqrt{\frac{n\log{T}}{T\epsilon^{2}}})$ and recalling $T\geq n$, the regret is upper bounded by

This completes the proof of the distribution-free regret, and the proof of Theorem 6 is complete. ∎

A.5 Proof of Lemma 7

Let $F$ be the cumulative probability function of $\mathcal{N}$ (here, we allow point mass on $\mathcal{N}$). Note that $\lambda,\mu\in$, and we have

Since the function $e^{-x}$ is decreasing and convex on $x$ and $(e^{-x})^{\prime}|_{x=1}=-e^{-1}$, we have

Let $Z$ be a random variable that follows $\mathcal{N}$, i.e., the CDF of $Z$ is $F$. For $a\in(0,1/4)$, solving the equation and we get

Here, we let $v_{a}$ denote the positive part of the right-hand side. Since $\frac{e^{-x}}{(1+e^{-x})^{2}}$ decreases with $x$, $\frac{e^{-x}}{(1+e^{-x})^{2}}\geq a$ if and only if $|x|\leq v_{a}$. Therefore, we have

where (a) is due to the property of sub-Gaussian distributions. Thus,

Along with $e^{-\mu}-e^{-\lambda}\geq e^{-1}(\lambda-\mu)$, we get

Specifically, if the noises are Gaussian with mean and variance $1$, then by numerically computing the integration, we have

A.6 Proof of Lemma 8

The $\epsilon$-DP of CTL-S follows from the $\epsilon$-DP of CTL stated in Lemma 2. The difference between the expected responses of CTL-S$(\epsilon)$ on arms $a$ and $b$ follows from Lemma 7. This completes the proof of Lemma 8. ∎

A.7 Proof of Lemma 9

The $\epsilon$-DP of CTB-S follows from the $\epsilon$-DP of CTB stated in Lemma 5.

A.8 Proof of Lemma 12

To prove this lemma, we introduce a fact about $D_{\mbox{\tiny{KL}}}$.

For two PDFs $f_{1}$ and $g_{1}$ with the same support $\Omega$, if for all $x$ in $\Omega$ we have $0<r\leq f_{1}(x)/g_{1}(x)\leq R<\infty$, then the following holds

where the two equalities hold if and only if $f_{1}$ and $g_{1}$ are equal almost surely.

Define $r(x)=f_{1}(x)/g_{1}(x)$, and we have $e^{-\epsilon}\leq r(x)\leq e^{\epsilon}$. For any $x$ in $\Omega$, we have

If $p\geq q$, then $h_{a}(x)/h_{b}(x)$ is non-decreasing with $r(x)$, which implies

If $p<q$, then $h_{a}(x)/h_{b}(x)$ is non-increasing with $r(x)$, which implies

In both cases, by Fact 13, we have $D_{\mbox{\tiny{KL}}}(h_{a}||h_{b})\leq\frac{(R-r)^{2}}{4rR}$, where

where (a) is due to $x^{2}+(1-x)^{2}\geq 1/2$ for any $x$. This completes the proof of Lemma 12. ∎

Appendix B Additional numerical results

In this section, we present the empirical performance of LDP-UCB-LS and LDP-UCB-BS, and the results are illustrated in Figure 2. In the experiments, there are $n=20$ arms. The best arm has mean reward $0.9$; five arms have mean rewards $0.8$; five arms have mean rewards $0.7$; five arms have mean rewards $0.6$; and four arms have mean rewards $0.5$. The rewards of all arms follow the Gaussian distributions with variance one. We also include the non-private UCB algorithm UCB1 in as a baseline. For fair comparisons, we also add the Sigmoid preprocessing on the rewards when running the non-private UCB algorithm.

In Figure 2 (a), we set $\epsilon=0.5$ and compare different algorithms. In (b), we vary the values of $\epsilon$ to compare the performance of LDP-UCB-LS under different values of $\epsilon$. In Figure 2 (b), we vary the value of $\epsilon$ to evaluate the performance of LDP-UCB-LS under different values of $\epsilon$. In Figure 2 (c), we vary the value of $\epsilon$ to evaluate the performance of LDP-UCB-BS. From the results, we can see that the ratios of the regrets of LDP-UCB-LS and LDP-UCB-BS to that of the non-private UCB is similar to that of the bounded arms. In theory, when $\epsilon=0.5$, the upper bounds of the ratios are $(1+\frac{4}{\epsilon})^{2}=81$ for LDP-UCB-LS and $(\frac{e^{\epsilon}+1}{e^{\epsilon}-1})^{2}=17$ for LDP-UCB-BS, larger than the empirical results $15$ and $10$ shown in Figure 2 (a), which confirms our theoretical results.