Encrypted Value Iteration and Temporal Difference Learning over Leveled Homomorphic Encryption

Various HE schemes were applied to the linear controller in [7, 8, 9]. Importance of quantization and using non-deterministic encryption scheme was identified in [7]. Necessary conditions on encryption parameters for closed-loop stability were shown by [8]. The feasibility of FHE in encrypted control was first shown in [9] by managing multiple controllers. Evaluation of affine control law in explicit MPC was shown by [10]. In [11] encrypted implicit MPC control was shown to be feasible but the cost of privacy as increased complexity was identified. Real-time proximal gradient method was used in [12] to treat encrypted implicit MPC control and it showed undesired computation loads of encrypted control system. Privacy and performance degradation was further highlighted in [13] through experiments on motion control systems. Dynamic controller was encrypted in [14] using FHE exploiting the stability of the system while not relying on bootstrapping. Despite significant progress, encrypted control has been limited to simple computations where the motivation for cloud computing is questionable.

To study the feasibility of RL over HE, this paper makes the following contributions. First, as a first step towards more advanced problems of private RL, we formally study the convergence of encrypted tabular VI. We show that the impact of the encryption-induced noise can be made negligible if the $Q$-factor is decrypted in each iteration. Second, we present implementation results of temporal difference (TD) learning (namely, TD(0), SARSA(0), and Z-learning [15]) over the CKKS encryption scheme and compare their performances with un-encrypted cases. Although the formal performance analysis for this class of algorithms are difficult with encryption noise, we show numerically that these RL schemes can be implemented accurately over LHE.

In section II, we summarize the relevant essentials of RL and HE. In section III, we set up the encrypted control synthesis problem and specialize it to the encrypted model-based and model-free RL algorithms. We analyze how the encryption-induced noise influences the convergence of standard VI. In section IV-A, we perform the simulation studies to demonstrate the encrypted model-free RL over HE. Finally, in section V, we summarize our contributions and discuss the future research directions.

RL can be formalized through the finite state Markov decision process (MDP). We define a finite MDP as a tuple $(\mathcal{S},\mathcal{A},P,R)$, where $\mathcal{S}=(1,2,\dots,n)$ is a finite state space, $\mathcal{A}$ is a finite action space, $P=P(s_{t+1}|s_{t},a_{t})$ is a Markov state transition probability and $R=R(s_{t},a_{t},s_{t+1})$ is a reward function for the state-transition. A policy can be formalized via a sequence of stochastic kernels $\pi=(\pi_{0},\pi_{1},...)$, where $\pi_{t}(a_{t}|s_{0:t+1},a_{0:t})$ is a mapping for each state $s_{t}\in\mathcal{S}$ to the probability of selecting the action $a_{t}\in\mathcal{A}$ given the history $(s_{0:t-1},a_{0:t-1})$.

We consider a discounted problem with a discount factor $\gamma\in[0,1)$ throughout this paper. Under a stationary policy $\pi$, the Bellman’s optimality equation can be defined through a recursive operator $T$ applied on the initial value vector $V^{\pi}_{0}$ of the form $V^{\pi}=(V(1),\dots,V(n))^{\pi}$:

Throughout this paper, we adopt the conventional definition for the maximum norm $\|\cdot\|_{\infty}$. The following results are standard [16].

If some policy $\pi^{*}$ attains $V^{*}$, we call $\pi^{*}$ the optimal policy and the goal is to attain the optimal policy $\pi^{*}$ for the given MDP environment.

Often the state values are written conveniently as a function of state-action pairs called $Q$-values:

and for all state $s_{t}$, $V^{\pi}_{k+1}(s_{t})=\max_{a_{t}\in\mathcal{A}}Q^{\pi}(s_{t},a_{t})$.

RL is a class of algorithms that solves MDPs when the model of the environment (e.g., $P$ and/or $R$) is unknown. RL can be further classified into two groups: model-based RL and model-free RL [17]. A simple model-based RL first estimates the transition probability and reward function empirically (to build an artificial model) then utilizes the VI to solve the MDP. Model-free RL on the other hand directly computes the value function by averaging over episodes (Monte Carlo methods) or by estimating the values iteratively like TD learning.

TD(0) is one of the simplest TD learning algorithm where the tuple $(s,R,s^{\prime})$ is sampled from the one-step ahead observation [18]. The on-policy iterative update rule for estimating the value is called TD(0) and is written as follows:

$\delta_{t}$ denotes the TD error and is computed with the sample as

starting with an initial guess $\hat{V}^{\pi}_{0}$. We use $\hat{V}$ to indicate that the values are estimated. With some standard assumptions on the step size $\alpha_{t}(s)$ and exploring policies, the convergence of TD(0) is standard in the literature, see [19].

HE is a structure-preserving mapping between the plain-text domain $\mathcal{P}$ and the cipher-text domain $\mathcal{C}$. Thus, encrypted data in $\mathcal{C}$ with a function $f(\mathcal{C})$ can be outsourced to the cloud for confidential computations.

PHE supports only the addition or the multiplication. On the other hand, LHE can support both the addition and the multiplication but the noise growth of ciphertext multiplication is significant without the bootstrapping [20]. The bootstrapping operation can promote a LHE scheme to FHE enabling unlimited number of multiplications but it requires a heavy computation resource on its own.

In order to use both addition and multiplication necessary in evaluating RL algorithms, we use an LHE. In particular, we employ CKKS encryption scheme proposed in [21] as it is well suited for engineering applications and also supports parallel computations. Also, there exists a widely available library optimized for implementations. We will only list and describe here several key operations and properties with more detailed information found in Appendix. We are particularly concerned with the fact that the CKKS encryption is noisy (due to error injection for security) but if properly implemented, the noise is manageable.

The security of CKKS scheme assumes the difficulty of the Ring Learning With Errors (RLWE) problem. Security parameters are a power-of-two integer $\mathcal{N}$, a ciphertext modulus $\mathcal{Q}$ and the variance $\sigma$ used for drawing error from a distribution. The operation KeyGen uses security parameters ($\mathcal{N}$, $\mathcal{Q}$, $\mathcal{\sigma}$) to create a $\lambda$-bit public key pk, a secret key sk, and an evaluation key evk.

Our control loop consists of the plant (environment) and the controller (client) and the cloud server. We are concerned with a possible data breach at the cloud. In order to prevent the privacy compromise of our data such as training data set and other parameters at play, we add the homomorphic encryption module as seen in Fig. 1. In particular, we ignore the malleability risks [22] inherent to the considered HE scheme, which is beyond the scope of this paper. In our context, $Syn(Enc(\cdot))$ can be thought of as a ciphertext domain implementation of RL algorithms. However, $Syn(Enc(\cdot))$ is a general control synthesis that can be evaluated remotely. Ideal uses for $Syn(Enc(\cdot))$ would include advanced data-driven control synthesis procedures such as MPC, or Deep RL. We emphasize that the encryption adds communication delays for control policy synthesis but does not add an extra computation cost to control implementation. For RL, the controller’s task is to implement the most up-to-date state-action map $\pi$ that is recently synthesized, which can be done locally.

We assume the tabular representation of the state and action pairs. The client explores its plant and samples the information set $h_{t}=(s_{t+1},a_{t},r_{t})$. Other necessary parameters such as learning rate $\alpha_{t}(s)$ and $\gamma$ are grouped as $\theta$ denoting the hyperparmeters. This set of data is then encrypted by the CKKS encryption module to generate ciphertexts $\textbf{c}_{v}$, $\textbf{c}_{v^{\prime}}$, $\textbf{c}_{\alpha}$, $\textbf{c}_{\gamma}$, and $\textbf{c}_{r}$, which are encrypted data for $\hat{V}_{t}^{\pi}(s)$, $\hat{V}_{t}^{\pi}(s^{\prime})$, $\alpha_{t}(s)$, $\gamma$, and $R(s,a)$, and will be used to implement (3). Note that the subscripts refer to the value when these ciphertexts are decrypted. The cloud is instructed on how to evaluate the requested algorithms in ciphertexts. One may concern about the cloud knowing the form of the algorithm, but this can be resolved by the circuit privacy. That is, we can hide the actual computation steps by adding zeros or multiplying ones in ciphertexts on the original algorithm. We also assume that the cloud is semi-honest so that the cloud faithfully performs the algorithm as instructed. The output of the cloud is a newly synthesized policy $\pi_{t}(s_{0:t})$, which, after a decryption, can be accessed on real-time by the client to produce the control action $a_{t}(s_{t})$.

As a first step towards investigating more sophisticated RL algorithms, we specialize the proposed framework to solving RL problems in finite MDP with more elementary methods. In particular, we consider the basic model-based RL and model-free RL using tabular algorithms. For the model-based, we theoretically analyze the convergence of VI under the presence of encryption-induced noise. For the model-free, we implement the encrypted TD algorithms to estimate the values and investigate how the encryption noise affects the output.

The client is assumed to explore the plant, sample the information sets $h_{t}$ and build the model first. A simple model of the state-transition probability can be in the form

where $N(s,a,s^{\prime})$ denotes the number of visits to the triplet $(s,a,s^{\prime})$ and $N(s,a)$ to the pair $(s,a)$ with $s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}$. Similarly, the reward function $R(s_{t},a_{t},s_{t+1})$ can be quantified by the average rewards accumulated per the state-action pair.

Then, the client can encrypt the initial values of the state along with the model $P$ and $R$ and the discount rate $\gamma$ and request the cloud to perform the computation of (2) over the ciphertext domain. Since comparison over HE is non-trivial, the max operation is difficult to be implemented homomorphically. Thus, the cloud computes the $Q$ values and the controller will receive the decrypted $Q$ values and completes the VI process for iteration index $k$:

However, note that the $Q$ values computed by the cloud will be noisy due to the encryption, hence we use $\tilde{Q}$ and $\tilde{V}$ to denote the noisy value. Let $w(s_{t},a_{t})$ be the encryption-induced noise produced by computations over HE. Then, the noisy $Q$ values can be written as

where the noise term is bounded such that $|w(s_{t},a_{t})|\leq\epsilon$ $\forall s_{t},a_{t}$ for some $\epsilon>0$. Appendix $A$ shows how $\epsilon$ depends on the encryption parameter and operations used to evaluate the given algorithm.

We now analyze the discrepancy between two sequences of vectors $V^{\pi}_{k}$ and $\tilde{V}^{\pi}_{k}$. We separate the analysis into the synchronous and the asynchronous cases.

Consider again the TD(0) update rule, (3). The cloud receives the set of ciphertexts $\{\textbf{c}_{v}$, $\textbf{c}_{v^{\prime}}$, $\textbf{c}_{\alpha}$, $\textbf{c}_{\gamma}$, $\textbf{c}_{r}\}$. Then, the update rule in the ciphertext domain becomes:

Upon decryption of $\textbf{c}_{v}(t+1)$, we need to remember that the computed value is corrupted with the noise. A similar error analysis for the TD algorithms can be performed (perhaps using stochastic approximation theory). However, the formal analysis in this domain presents some difficulties. Whereas a conventional theory on stochastic approximation with an exogenous noise seen in [16] requires the noise to approach zero in the limit and bounded, the encryption-induced noise satisfies only the bounded condition. We thus only provide some implementation results at this time to gain some insight. We hope to rigorously prove this case as in the future work.

We implement a GLIE (greedy in the limit with infinite exploration) type learning policy seen in [25], where the client starts completely exploratory ($\varepsilon=1.00$) and slowly becomes greedy ($\varepsilon=0.00$) with more episodes. The learning rate is set to be $0$ for non-visited states and for visited states, we set $\alpha(s,t)=\frac{500}{500+n(s,t)}$, with $n(s,t)$ counting the number of visits to the state $s$ at time $t$, to satisfy the standard learning rate assumptions. The discount factor is $\gamma=0.9$. *RULE* for TD(0) is the right hand side of equation (20).

The update rule for SARSA(0) is:

where $\delta_{t}^{S}=\left(r(s,a)+\gamma\hat{Q}_{t}(s^{\prime},a^{\prime})-\hat{Q}_{t}(s,a)\right).$

The policy for SARSA(0) is also a GLIE (greedy in the limit with infinite exploration) type learning policy used in TD(0). The learning rate $\alpha(s,t)$ and the discount factor $\gamma$ are unchanged. *RULE* for SARSA(0) is the right hand side of equation (20) after substituting $\textbf{c}_{v}$ and $\textbf{c}_{v^{\prime}}$ with $\textbf{c}_{Q}$ and $\textbf{c}_{Q^{\prime}}$.

An off-policy learning control called Z-learning was proposed in [15]. It is formulated on the key observation that the control action can be regarded as an effort to change the passive state transition dynamics. The update rule for Z-learrning is:

where $\delta_{t}^{Z}=exp(-l_{t})\hat{Z}_{t}(s^{\prime})-\hat{Z}_{t}(s)$. The estimate $Z$ is named the desirability function and it uses the cost $l_{t}$ associated with the unknown state-transitions, rather than the reward. Z-learrning by default is exploratory. Thus, we fix the policy to be greedy ($\varepsilon=1.00$) but it will continuously explore, too. The learning rate $\alpha(s,t)$ and the discount factor are unchanged. *RULE* for Z-learning is evaluating the right hand side of equation (22) after encrypting. Since evaluating $exp(-l_{t})$ over a ciphertext is not straightforward, we approximate with Taylor series.

We observed that encryption-induced noise over time approached some small numbers with minimal fluctuations. Moreover, the effects of encryption-induced noise were minimal regarding the convergence of values. This observation complements the analysis on VI in Section III as the TD-algorithms are sampling based value estimation algorithms.

Encryption and decryption are all done at the client’s side and so significant computation time is expected for the client. For this reason, the ideal application will require less frequent needs for uploading and downloading and more advanced synthesis procedure that operate on a large set of data.

CKKS encoding procedure maps the vector of complex numbers sized $\frac{\mathcal{N}}{2}$ to the message $m$ in plain-text space $\mathcal{P}$. The plaintext $\mathcal{P}$ is defined as the set $\mathbb{Z}_{\mathcal{Q}}[\mathcal{X}]/\left(\mathcal{X}^{\mathcal{N}}+1\right)$, where $\mathbb{Z}_{\mathcal{Q}}[\mathcal{X}]$ denotes the polynomials of $x\in\mathcal{X}$ whose coefficients are integers modulo $\mathcal{Q}$, and $\mathcal{X}^{\mathcal{N}}+1$ denotes the degree $\mathcal{N}$ cyclotomic polynomials. This allows for CKKS encryption scheme to accept multiple complex-valued inputs of a size $\frac{\mathcal{N}}{2}$ at once, which is convenient for many computing applications.

Then, encryption on the message $m\in\mathcal{P}$ yields the ciphertext $\textbf{c}\in\mathcal{C}$

Each ciphertext is designated with a level $L$, which indicates how many multiplications you can perform before decryption fails. This is a key limitation in comparison to FHE.

The encryption also creates a noise polynomial $e$. A properly encrypted ciphertext has a bound on the message $\|m\|_{\infty}\leq p$ and also on the noise $\|e\|_{\infty}\leq B$ when the norm is defined on those polynomials. Thus, a CKKS ciphertext can be defined as a tuple $\textbf{c}=(c,L,p,B)$. Then, decryption can be defined as follows.

where $q_{L}$ is the coefficient modulus at level $L$.

For ciphertexts $\textbf{c}_{i}=Enc_{pk}(m_{i})$ at the same level $L$,

where $\|e_{add}\|_{\infty}\leq B_{1}+B_{2}$.