Adaptive Control of Differentially Private Linear Quadratic Systems

We consider the discrete-time episodic linear quadratic (LQ) control problem with $H$ time steps at every episode. Let $x_{h}\!\in\!\mathbb{R}^{n}$ be the state of the system, $u_{h}\!\in\!\mathbb{R}^{d}$ be the control and $c_{h}\!\in\!\mathbb{R}$ be the cost at time $h$. An LQ problem is characterized by linear dynamics and a quadratic cost function

where $A$, $B$ are unknown matrices, and $Q$, $R$ are known positive definite (p.d.) matrices. The starting state $x_{1}$ is fixed (can possibly be chosen by an adversary) and the system noise $w_{h}\!\in\!\mathbb{R}^{n}$ is zero-mean. We summarize the unknown parameters in $\Theta\!=\![A,B]^{\top}\!\in\!\mathbb{R}^{(n+d)\times n}$ .

The goal of the agent is to design a closed-loop control policy $\pi:[H]\times\mathbb{R}^{n}\to\mathbb{R}^{d}$ mapping states to controls that minimizes the expected cost

for all $h\in[H]$ and $x\in\mathbb{R}^{n}$. Here the expectation is over the random trajectory induced by the policy $\pi$ starting from state $x$ at time $h$. From the standard theory for LQ control (e.g., [19]), the optimal policy $\pi^{*}$ has the form

where the gain matrices $K_{h}(\Theta)$ are given by

Here the symmetric positive semidefinite matrices $P_{h}(\Theta)$ are defined recursively by the Riccati iteration

with $P_{H+1}(\Theta):=0$. The optimal cost is given by

We now formally define the notion of differential privacy in the context of episodic LQ control. We write $v\!=\!(v_{1},\ldots,v_{K})\!\in\!\mathcal{V}^{K}$ to denote a sequence of $K$ unique users participating in the private RL protocol with an RL agent $\mathcal{M}$, where $\mathcal{V}$ is the set of all users. Each user $v_{k}$ is identified by the state responses $\{x_{k,h+1}\}_{h\in[H]}$ she gives to the controls $\{u_{k,h}\}_{h\in[H]}$ chosen by the agent. We write $\mathcal{M}(v)\!=\!\{u_{k,h}\}_{k\in[K],h\in[H]}\in(\mathbb{R}^{d})^{KH}$ to denote the privatized controls chosen by the agent $\mathcal{M}$ when interacting with the users $v$. Informally, we will be interested in randomized algorithms $\mathcal{M}$ so that the knowledge of the output $\mathcal{M}(v)$ and all but the $k$-th user $v_{k}$ does not reveal ‘much’ about $v_{k}$. We formalize in the following definition, which is adapted from [20].

We now relax this definition motivated by the fact that the controls recommended to a given user $v_{k}$ is only observed by her. We consider joint differential privacy [21], which requires that simultaneously for all $k$, the joint distribution on controls sent to users other than $v_{k}$ will not change substantially upon changing the state responses of the user $v_{k}$. To this end, we let $\mathcal{M}_{-k}(v)\!:=\!\mathcal{M}(v)\!\setminus\!\{u_{k,h}\}_{h\in[H]}$ to denote all the controls chosen by the agent $\mathcal{M}$ excluding those recommended to $v_{k}$.

This relaxation is necessary in our setting since knowledge of the controls recommended to the user $v_{k}$ can reveal a lot of information about her state responses. It weakens the constraint of DP only in that the controls given specifically to $v_{k}$ may be sensitive in her state responses. However, it is still a very strong definition since it protects $v_{k}$ from any arbitrary collusion of other users against her, so long as she does not herself make the controls reported to her public.

In this work, we look for algorithms that are $(\varepsilon,\delta)$-JDP. But, we will build our algorithm upon standard DP mechanisms. Furthermore, to establish privacy, we will use a different relaxation called concentrated differential privacy (CDP) [22]. Roughly, a mechanism is CDP if the privacy loss has Gaussian tails. To this end, we let $\mathcal{M}$ to be a mechanism taking as input a data-stream $x\!\in\!\mathcal{X}^{n}$ and releasing output from some range $\mathcal{Y}$.

We start with the adaptive LQ control with changing regularizers. This not only allows us to generalize previous results for non-private control, but more importantly serves as a basis for the analysis of private control in the next section. We first define the following compact notations. For a state and control pair at step $h$ in episode $k$, i.e., $x_{k,h}$ and $u_{k,h}$, we write $z_{k,h}\!=\![x_{k,h}^{\top},u_{k,h}^{\top}]^{\top}$. For any $k\!\geqslant\!1$, we define the following matrices: $Z_{k}\!:=\![z_{k^{\prime},h^{\prime}}^{\top}]_{k^{\prime}\in[k-1],h^{\prime}\in[H]}$, $X_{k}^{\text{next}}\!:=\![x_{k^{\prime},h^{\prime}+1}^{\top}]_{k^{\prime}\in[k-1],h^{\prime}\in[H]}$ and $W_{k}\!:=\![w_{k^{\prime},h^{\prime}}^{\top}]_{k^{\prime}\in[k-1],h^{\prime}\in[H]}$. For two matrices $A$ and $B$, we also define $\left\lVert A\right\rVert_{B}^{2}\!:=\!\text{trace}(A^{\top}BA)$. Now, at every episode $k$, we consider the following ridge regression estimate w.r.t. a regularizing p.d. matrix $H_{k}\in\mathbb{R}^{(n+d)\times(n+d)}$:

In contrast to the standard online LQ control [14], here the sequence of matrices $\{Z_{k}^{\top}Z_{k}\}_{k\geqslant 1}$ is perturbed by a sequence of regularizers $\{H_{k}\}_{k\geqslant 1}$. In particular, when $H_{k}\!=\!\lambda I$, we get back the standard estimate of [14]. In addition, we also allow $Z_{k}^{\top}X_{k}^{\text{next}}$ to be perturbed by a matrix $L_{k}$ at every episode $k$. Setting $V_{k}\!:=\!Z_{k}^{\top}Z_{k}\!+\!H_{k}$ and $U_{k}\!:=\!Z_{k}^{\top}X_{k}^{\text{next}}\!+\!L_{k}$, we now define the estimate under changing regularizers $\{H_{k}\}_{k\geq 1}$ and $\{L_{k}\}_{k\geq 1}$ as

Now, we are going to bound each term, respectively. For the first two terms, we can show that both of them are bounded martingale difference sequences. Therefore, by Azuma–Hoeffding inequality, we have $\sum_{k,h}\Delta_{k,h}\!=\!O\big{(}\sqrt{KH^{3}}\big{)}$ and $\sum_{k,h}\Delta^{\prime}_{k,h}\!=\!O\big{(}\sqrt{KH}\big{)}$ with high probability. We use Lemma 1 and the OFU principle (9) to bound the third term as $\sum_{k,h}\Delta^{\prime\prime}_{k,h}\!=\!O\big{(}H\sqrt{K}\beta_{k}(\alpha)\sqrt{\ln\det\left(I\!+\!\lambda_{\min}^{-1}Z_{k}^{\top}Z_{k}\right)}\big{)}$. To put everything together, first note from Assumption 1 that

Plugging this into $\beta_{k}(\alpha)$ given in Lemma 1 and the third term above, yields the final result. ∎

We end the section with a proof sketch of Lemma 1.

In this section, we introduce the $\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$ algorithm (Alg. 1). At every episode $k$, we keep track of the history via private version of the matrices $Z_{k}^{\top}Z_{k}$ and $Z_{k}^{\top}X_{k}^{\text{next}}$. To do so, we first initialize two private counter mechanisms $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$, which take as parameters the privacy levels $\varepsilon$, $\delta$, number of episodes $K$, horizon $H$ and a problem-specific constant $\gamma$ (see Assumption 1). The counter $\mathcal{B}_{1}$ (resp. $\mathcal{B}_{2}$) take as input an event stream of matrices $\{\sum_{h=1}^{H}z_{k,h}z_{k,h}^{\top}\}_{k\in[K]}$ (resp. $\{\sum_{h=1}^{H}z_{k,h}x_{k,h+1}^{\top}\}_{k\in[K]}$), and at the start of each episode $k$, release the private version of the matrix $Z_{k}^{\top}Z_{k}$ (resp. $Z_{k}^{\top}X_{k}^{\text{next}}$), which itself is a matrix of the same dimension. Let $T_{1,k}$ and $T_{2,k}$ denote the privatized versions for $Z_{k}^{\top}Z_{k}$ and $Z_{k}^{\top}X_{k}^{\text{next}}$, respectively. For some $\eta>0$ (will be determined later), we define $V_{k}\!:=\!T_{1,k}\!+\!\eta I$ and $U_{k}\!:=\!T_{2,k}$. We now instantiate the general $\mathrm{OFU}\text{-}\mathrm{RL}$ procedure under changing regularizers (Section III-A) with these private statistics. First, we compute the point estimate $\widehat{\Theta}_{k}$ from (7) and build the confidence set $\mathcal{C}_{k}(\alpha)$ from (8). Then, we choose the most optimisitic policy $\pi_{k}$ w.r.t. the entire set $\mathcal{C}_{k}(\alpha)$ from (9) and (10). Finally, we execute the policy for the entire episode and update the counters with observed trajectory.

We now describe the private counters $\mathcal{B}_{1}$ adapting the Binary counting mechanism of [24]. First, we write $\Sigma_{1}[i,j]=\sum_{k=i}^{j}\sum_{h=1}^{H}z_{k,h}z_{k,h}^{\top}$ to denote a partial sum ($\mathrm{P}\text{-}\mathrm{sum}$) involving the state-control pairs in episodes $i$ through $j$. Next, we consider a binary interval tree, where each leaf node represents an episode (i.e., the tree has $k-1$ leaf nodes at the start of episode $k$), and each interior node represents the range of episodes covered by its children. At the start of episode $k$, we first release a noisy $\mathrm{P}\text{-}\mathrm{sum}$ $\widehat{\Sigma}_{1}[i,j]$ corresponding to each node in the tree. Here $\widehat{\Sigma}_{1}[i,j]$ is obtained by perturbing both $(p,q)$-th and $(q,p)$-th, $1\!\leqslant\!p\!\leqslant\!q\!\leqslant\!(n\!+\!d)$, entries of $\Sigma_{1}[i,j]$ with i.i.d. Gaussian noise $\zeta_{p,q}\!\sim\!\mathcal{N}(0,\sigma_{1}^{2})$.³³3This will ensure symmetry of the $\mathrm{P}\text{-}\mathrm{sums}$ even after adding noise. Then $T_{1,k}$ is computed by summing up the noisy $\mathrm{P}\text{-}\mathrm{sums}$ released by the set of nodes that uniquely cover the range $[1,k\!-\!1]$. Observe that, at the end each episode, the mechanism only needs to store noisy $\mathrm{P}\text{-}\mathrm{sums}$ required for computing private statistics at future episodes, and can safely discard $\mathrm{P}\text{-}\mathrm{sums}$ that are no longer needed. For the private counter $\mathcal{B}_{2}$, we maintain $\mathrm{P}\text{-}\mathrm{sums}$ $\Sigma_{2}[i,j]\!=\!\sum_{k=i}^{j}\sum_{h=1}^{H}z_{k,h}x_{k,h+1}^{\top}$ with i.i.d. noise $\mathcal{N}(0,\sigma_{2}^{2})$ and compute the private statistics $T_{2,k}$ using a similar procedure. The noise levels $\sigma_{1}$ and $\sigma_{2}$ depends on the problem intrinsics ($K$, $H$, $\gamma$) and privacy parameters ($\varepsilon$, $\delta$). These, in turn, govern the constants $\lambda_{\max}$, $\lambda_{\min}$, $\nu$ appearing in the confidence set $\mathcal{C}_{k}(\alpha)$ and the regularizer $\eta$. The details will be specified in the next Section as needed.

To prove Theorem 2, we now use the billboard lemma [25, Lemma 9] which, informally, states that an algorithm is JDP under continual observation if the output sent to each user is a function of the user’s private data and a common quantity computed using standard differential privacy. Note that at each episode $k$, $\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$ computes private statistics $T_{1,k}$ and $T_{2,k}$ for all users using the counters $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$. These statistics are then used to compute the policy $\pi_{k}$. By composition and post-processing properties of DP, we can argue that the sequence of policies $\{\pi_{k}\}_{k\in[K]}$ are computed using an $(\varepsilon,\delta)$-DP mechanism. Now, the controls $\{u_{k,h}\}_{h\in[H]}$ during episode $k$ are generated using the policy $\pi_{k}$ and the user’s private data $x_{k,h}$ as $u_{k,h}\!=\!\pi_{k,h}(x_{k,h})$. Then, by the billboard lemma, the composition of the controls $\{u_{k,h}\}_{k\in[K],h\in[H]}$ sent to all the users is $(\varepsilon,\delta)$-JDP.∎