Near-Optimal Differentially Private Reinforcement Learning

Detailed comparisons with existing work on differentially private RL under tabular MDP (Vietri et al., 2020; Garcelon et al., 2021; Chowdhury and Zhou, 2021) are given in Table 1, while we leave more discussions about results on regret minimization to Appendix A. Notably, all existing algorithms privatize Hoeffding-type bonus and suffer from sub-optimal regret bound. In comparison, we privatize Bernstein-type bonus and the non-private part of our regret²²2As shown in Table 1, the regret bounds of all DP-RL algorithms contain two parts: one results from running the non-private RL algorithms, while the other is the additional cost due to DP guarantees. Throughout the paper, we use “non-private part” to denote the regret from running the non-private RL algorithms. matches the minimax lower bound in Jin et al. (2018).

Generally speaking, to achieve DP guarantee under RL, a common approach is to add appropriate noise to existing non-private algorithms, and derive tight regret bounds. We discuss about private algorithms under tabular MDP below and leave more discussions about algorithms under other settings to Appendix A. Under the constraint of JDP, Vietri et al. (2020) designed PUCB by privatizing UBEV (Dann et al., 2017). Private-UCB-VI (Chowdhury and Zhou, 2021) resulted from UCBVI (with bonus 1) (Azar et al., 2017). Under the constraint of LDP, Garcelon et al. (2021) designed LDP-OBI based on UCRL2 (Jaksch et al., 2010). However, all these works privatized Hoeffding-type bonus, which is easier to handle, but will lead to sub-optimal regret bound. In contrast, we directly build upon the non-private algorithm with minimax optimal regret bound: UCBVI with bonus 2 (Azar et al., 2017), where the privatization of Bernstein-type bonus requires more advanced techniques.

A concurrent work (Qiao and Wang, 2022b) focused on the offline RL setting and derived a private version of APVI (Yin and Wang, 2021). Their algorithm achieved tight sub-optimality bound of the output policy through privatization of Bernstein-type pessimism³³3Pessimism is the counterpart of bonus under offline RL, which aims to discourage the choice of $(s,a)$ pairs with large uncertainty.. However, their analysis relied on the assumption that the visitation numbers of all (state,action) pairs are larger than some threshold. We overcome the requirement of such assumption via an improved privatization of visitation numbers. More importantly, offline RL can be viewed as one step of online RL, therefore privatization of Bernstein type bonus is more technically demanding. Finally, our approach actually realizes the future direction stated in the conclusion of Qiao and Wang (2022b).

The general idea behind the previous differentially private algorithms under tabular MDP (Vietri et al., 2020; Garcelon et al., 2021; Chowdhury and Zhou, 2021) is to add noise to accumulative visitation numbers, and construct a private bonus based on privatized visitation numbers. Since Hoeffding-type bonus $b^{k}_{h}(s,a)$ only uses the information of visitation numbers (e.g., in Azar et al. (2017), $b^{k}_{h}(s,a)=\widetilde{O}(H\cdot\sqrt{1/N^{k}_{h}(s,a)})$), the construction of private bonus is straightforward. We can simply replace original counts $N^{k}_{h}(s,a)$ with private counts $\widetilde{N}^{k}_{h}(s,a)$ and add an additional term to account for the difference between these two bonuses. Next, combining the construction of private bonuses with the uniform upper bound of $|\widetilde{N}^{k}_{h}(s,a)-N^{k}_{h}(s,a)|$, we can upper bound the private bonus by its non-private counterpart plus some additional lower order term. Therefore the proof schedule of the original non-private algorithms also applies to their private counterparts.

Unfortunately, although the idea to privatize UCBVI with bonus 2 (Bernstein-type) (Azar et al., 2017) is straightforward, the generalization of the previous approaches is technically non-trivial. Since the bonus 2 in Azar et al. (2017) includes the term $\mathrm{Var}_{\widehat{P}^{k}_{h}(\cdot|s,a)}V^{k}_{h+1}(\cdot)$, the first technical challenge is to replace the empirical transition kernel $\widehat{P}^{k}_{h}(s,a)$ with a private estimate. However, the private transition kernel estimates constructed in previous works are not valid probability distributions. In this paper, for both JDP and LDP, we propose a novel privatization of visitation numbers such that the private transition kernel estimates are valid probability distributions and meanwhile, the upper bound on $|\widetilde{N}^{k}_{h}(s,a)-N^{k}_{h}(s,a)|$ is the same scale compared to previous approaches. With the private transition kernel estimates $\widetilde{P}^{k}_{h}$, we can replace $\mathrm{Var}_{\widehat{P}^{k}_{h}(\cdot|s,a)}V^{k}_{h+1}(\cdot)$ with $\mathrm{Var}_{\widetilde{P}^{k}_{h}(\cdot|s,a)}\widetilde{V}^{k}_{h+1}(\cdot)$ where $\widetilde{V}^{k}_{h}(\cdot)$ is the value function calculated from value iteration with private estimates. Then the second challenge is to bound the difference between these two variances and retain the optimism. We overcome the second challenge via concentration inequalities. Briefly speaking, we add an additional term (using private statistics) to compensate for the difference of these two bonuses and recovered the proof of optimism. With all these techniques, we derive our regret bound using techniques like error decomposition and error propagation originated from Azar et al. (2017).

We consider finite-horizon episodic Markov Decision Processes (MDP) with non-stationary transitions, denoted by a tuple $\mathcal{M}=(\mathcal{S},\mathcal{A},H,\{P_{h}\}_{h=1}^{H},\{r_{h}\}_{h=1}^{H},d_{1})$ (Sutton and Barto, 1998), where $\mathcal{S}$ is state space with $|\mathcal{S}|=S$, $\mathcal{A}$ is action space with $|\mathcal{A}|=A$ and $H$ is the horizon. The non-stationary transition kernel has the form $P_{h}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\mapsto[0,1]$ with $P_{h}(s^{\prime}|s,a)$ representing the probability of transition from state $s$, action $a$ to next state $s^{\prime}$ at time step $h$. In addition, $r_{h}(s,a)\in\Delta([0,1])$ denotes the corresponding distribution of reward, we overload the notation so that $r$ also denotes the expected (immediate) reward function. Besides, $d_{1}$ is the initial state distribution. A policy can be seen as a series of mapping $\pi=(\pi_{1},\cdots,\pi_{H})$, where each $\pi_{h}$ maps each state $s\in\mathcal{S}$ to a probability distribution over actions, i.e. $\pi_{h}:\mathcal{S}\rightarrow\Delta(\mathcal{A})$, $\forall\,h\in[H]$. A random trajectory $(s_{1},a_{1},r_{1},\cdots,s_{H},a_{H},r_{H},s_{H+1})$ is generated by the following rule: $s_{1}\sim d_{1}$, $a_{h}\sim\pi_{h}(\cdot|s_{h}),r_{h}\sim r_{h}(s_{h},a_{h}),s_{h+1}\sim P_{h}(\cdot|s_{h},a_{h}),\forall\,h\in[H]$.

Given a policy $\pi$ and any $h\in[H]$, the value function $V^{\pi}_{h}(\cdot)$ and Q-value function $Q^{\pi}_{h}(\cdot,\cdot)$ are defined as: $V^{\pi}_{h}(s)=\mathbb{E}_{\pi}[\sum_{t=h}^{H}r_{t}|s_{h}=s],Q^{\pi}_{h}(s,a)=\mathbb{E}_{\pi}[\sum_{t=h}^{H}r_{t}|s_{h},a_{h}=s,a],\;\forall\,s,a\in\mathcal{S}\times\mathcal{A}.$ The optimal policy $\pi^{\star}$ maximizes $V_{h}^{\pi}(s)$ for all $s,h\in\mathcal{S}\times[H]$ simultaneously and we denote the value function and Q-value function with respect to $\pi^{\star}$ by $V^{\star}_{h}(\cdot)$ and $Q^{\star}_{h}(\cdot,\cdot)$. Then Bellman (optimality) equation follows $\forall\,h\in[H]$:

We measure the performance of online reinforcement learning algorithms by the regret. The regret of an algorithm is defined as

where $s_{1}^{k}$ is the initial state and $\pi_{k}$ is the policy deployed at episode $k$. Let $K$ be the number of episodes that the agent plan to play and total number of steps is $T:=KH$.

Under the episodic RL setting, each trajectory represents one specific user. We first consider the following RL protocol: during the $h$-th step of the $k$-th episode, user $u_{k}$ sends her state $s_{h}^{k}$ to agent $\mathcal{M}$, $\mathcal{M}$ sends back an action $a_{h}^{k}$, and finally $u_{k}$ sends her reward $r_{h}^{k}$ to $\mathcal{M}$. Formally, we denote a sequence of $K$ users who participate in the above RL protocol by $\mathcal{U}=(u_{1},\cdots,u_{K})$. Following the definition in Vietri et al. (2020), each user can be seen as a tree of depth $H$ encoding the state and reward responses they would reply to all $A^{H}$ possible sequences of actions from the agent. We let $\mathcal{M}(\mathcal{U})=(a_{1}^{1},\cdots,a_{H}^{K})$ denote the whole sequence of actions chosen by agent $\mathcal{M}$. An ideal privacy preserving agent would guarantee that $\mathcal{M}(\mathcal{U})$ and all users but $u_{k}$ together will not reveal much information about user $u_{k}$. We formalize such privacy preservation through adaptation of differential privacy (Dwork et al., 2006).

However, although recommendation to other users will not affect the privacy of user $u_{k}$ significantly, it is impractical to privately recommend actions to user $u_{k}$ while protecting the information of her state and reward. Therefore, the notion of DP is relaxed to Joint Differential Privacy (JDP) (Kearns et al., 2014), which requires that for all user $u_{k}$, the recommendation to all users but $u_{k}$ will not reveal much information about $u_{k}$. JDP is weaker than DP, while JDP can still provide strong privacy protection since it protects a specific user from any possible collusion of all other users against her. Formally, the definition of JDP is shown below.

JDP ensures that even if an adversary can observe the recommended actions to all users but $u_{k}$, it is impossible to identify the trajectory from $u_{k}$ accurately. JDP is first defined and analyzed under RL by Vietri et al. (2020).

Although JDP provides strong privacy protection, the agent can still observe the raw trajectories from users. Under some circumstances, however, the users are not even willing to share their original data with the agent. This motivates a stronger notion of privacy which is called Local Differential Privacy (LDP) (Duchi et al., 2013). Since under LDP, the agent is not allowed to directly observe the state of users, we consider the following RL protocol for LDP: during the $k$-th episode, the agent $\mathcal{M}$ sends policy $\pi_{k}$ to user $u_{k}$, after deploying $\pi_{k}$ and getting trajectory $X_{k}$, user $u_{k}$ privatizes her trajectory to $X_{k}^{\prime}$ and finally sends it to $\mathcal{M}$. We denote the privacy mechanism on user’s side by $\widetilde{\mathcal{M}}$ and define local differential privacy formally below.

Local DP ensures that even if an adversary observes the whole reply from user $u_{k}$, it is still statistically hard to identify her trajectory. LDP is first defined and analyzed under RL by Garcelon et al. (2021).

The Central Privatizer protects the information of all single users by privatizing all the counter streams $N^{k}_{h}(s,a)$, $N^{k}_{h}(s,a,s^{\prime})$ and $R^{k}_{h}(s,a)$ using the Binary Mechanism (Chan et al., 2011), which focused on privately releasing data stream (Zhao et al., 2022). More specifically, for each $(h,s,a)$, $\{N^{k}_{h}(s,a)=\sum_{i=1}^{k-1}\mathds{1}(s_{h}^{i},a_{h}^{i}=s,a)\}_{k\in[K]}$ is the partial sums of data stream $\{\mathds{1}(s_{h}^{i},a_{h}^{i}=s,a)\}_{i\in[K]}$. Binary Mechanism works as below: for each episode $k$, after observing $\mathds{1}(s_{h}^{k-1},a_{h}^{k-1}=s,a)$, the mechanism outputs private version of $\sum_{i=1}^{k-1}\mathds{1}(s_{h}^{i},a_{h}^{i}=s,a)$ while ensuring Differential Privacy.⁴⁴4For more details about Binary Mechanism, please refer to Chan et al. (2011) or Kairouz et al. (2021). Given privacy budget $\epsilon>0$, we construct the Central Privatizer as below:

1. (1)

   For all $(h,s,a,s^{\prime})$, we privatize $\{N^{k}_{h}(s,a)\}_{k\in[K]}$ and $\{N^{k}_{h}(s,a,s^{\prime})\}_{k\in[K]}$ (which is summation of bounded streams) by applying Binary Mechanism (Algorithm 2 in Chan et al. (2011)) with $\epsilon^{\prime}=\frac{\epsilon}{3H\log K}$. We denote the output of Binary Mechanism by $\widehat{N}^{k}_{h}$.

2. (2)

   The private counts $\widetilde{N}^{k}_{h}$ are solved through the procedure in Section 5.1.1 with
   $E_{\epsilon,\beta}=O(\frac{H}{\epsilon}\log(HSAT/\beta)^{2})$.

3. (3)

   For the counters of accumulative reward, for all $(h,s,a)$, we apply the same Binary Mechanism with $\epsilon^{\prime}=\frac{\epsilon}{3H\log K}$ to privatize $R^{k}_{h}(s,a)$ and get $\widetilde{R}^{k}_{h}(s,a)$.

We sum up the properties of Central Privatizer below.

Therefore, combining Lemma 5.1 and Theorem 4.1, the following regret bound holds.

Under the most prevalent regime where the privacy budget $\epsilon$ is a constant, the additional regret bound due to JDP is a lower order term. The main term of Theorem 5.2 improves the best known result $\widetilde{O}(\sqrt{SAH^{3}T})$ (Corollary 5.2 of Chowdhury and Zhou (2021)) by $\sqrt{H}$ and matches the minimax lower bound without constrains on DP (Jin et al., 2018).

For each episode $k$, the Local Privatizer privatizes each single trajectory by perturbing the statistics calculated from that trajectory. For visitation of (state,action) pairs, the original visitation number $\{\sigma^{k}_{h}(s,a)=\mathds{1}(s_{h}^{k},a_{h}^{k}=s,a)\}_{(h,s,a)}$ has $\ell_{1}$ sensitivity $H$. Therefore, the perturbed version of the counts above $\widetilde{\sigma}^{k}_{h}(s,a)=\sigma^{k}_{h}(s,a)+\text{Lap}(\frac{3H}{\epsilon})$ satisfies $\frac{\epsilon}{3}$-LDP. In addition, similar perturbations to $\{\mathds{1}(s^{k}_{h},a^{k}_{h},s^{k}_{h+1}=s,a,s^{\prime})\}_{(h,s,a,s^{\prime})}$ and $\{\mathds{1}(s_{h}^{k},a_{h}^{k}=s,a)\cdot r^{k}_{h}\}_{(h,s,a)}$ will lead to the same result. As a result, we construct Local Privatizer as below:

1. (1)

   For all $(k,h,s,a,s^{\prime})$, we perturb $\sigma^{k}_{h}(s,a)=\mathds{1}(s_{h}^{k},a_{h}^{k}=s,a)$ and $\sigma^{k}_{h}(s,a,s^{\prime})=\mathds{1}(s^{k}_{h},a^{k}_{h},s^{k}_{h+1}=s,a,s^{\prime})$ by adding independent Laplace noises:

   $$\widetilde{\sigma}^{k}_{h}(s,a)=\sigma^{k}_{h}(s,a)+\text{Lap}(\frac{3H}{\epsilon}),$$

   $$\widetilde{\sigma}^{k}_{h}(s,a,s^{\prime})=\sigma^{k}_{h}(s,a,s^{\prime})+\text{Lap}(\frac{3H}{\epsilon}).$$

2. (2)

   The noisy counts are calculated by

   $$\widehat{N}^{k}_{h}(s,a)=\sum_{i=1}^{k-1}\widetilde{\sigma}^{i}_{h}(s,a),$$

   $$\widehat{N}^{k}_{h}(s,a,s^{\prime})=\sum_{i=1}^{k-1}\widetilde{\sigma}^{i}_{h}(s,a,s^{\prime}).$$

   Then the private counts $\widetilde{N}^{k}_{h}$ are solved through the procedure in Section 5.1.1 with
   $E_{\epsilon,\beta}=O(\frac{H}{\epsilon}\sqrt{K\log(HSAT/\beta)})$.

3. (3)

   We perturb the trajectory-wise reward by adding independent Laplace noise: $\widetilde{r}^{k}_{h}(s,a)=\mathds{1}(s_{h}^{k},a_{h}^{k}=s,a)\cdot r^{k}_{h}+\text{Lap}(\frac{3H}{\epsilon})$. The accumulative statistic is calculated by $\widetilde{R}^{k}_{h}(s,a)=\sum_{i=1}^{k-1}\widetilde{r}^{i}_{h}(s,a)$.

Properties of our Local Privatizer is summarized below.

Therefore, combining Lemma 5.6 and Theorem 4.1, the following regret bound holds.

Theorem 5.7 improves the non-private part of regret bound in the best known result (Corollary 5.5 of Chowdhury and Zhou (2021)).

The step (1) of our Privatizers is similar to previous works (Vietri et al., 2020; Garcelon et al., 2021; Chowdhury and Zhou, 2021). However, different from their approaches (directly use $\widehat{N}^{k}_{h}$ as private counts), we apply the post-processing step in Section 5.1.1, which ensures that $\widetilde{P}^{k}_{h}$ is valid probability distribution while $E_{\epsilon,\beta}$ is only worse by a constant factor. Therefore, we can apply Bernstein type bonus to achieve the optimal non-private part in our regret bound.

We remark that the Laplace Mechanism can be replaced with other mechanisms, like Gaussian Mechanism (Dwork et al., 2014) for approximate DP (or zCDP). According to Theorem 4.1, the regret bounds can be easily derived by plugging in the corresponding $E_{\epsilon,\beta}$.