1 Introduction↩︎

Offline Reinforcement Learning (or batch RL) aims to learn a near-optimal policy in an unknown environment¹ through a static dataset gathered from some behavior policy \(\mu\). Since offline RL does not require access to the environment, it can be applied to problems where interaction with environment is infeasible, e.g., when collecting new data is costly (trade or finance [1]), risky (autonomous driving [2]) or illegal / unethical (healthcare [3]). In such practical applications, the data used by an RL agent usually contains sensitive information. Take medical history for instance, for each patient, at each time step, the patient reports her health condition (age, disease, etc.), then the doctor decides the treatment (which medicine to use, the dosage of medicine, etc.), finally there is treatment outcome (whether the patient feels good, etc.) and the patient transitions to another health condition. Here, (health condition, treatment, treatment outcome) corresponds to (state, action, reward) and the dataset can be considered as \(n\) (number of patients) trajectories sampled from a MDP with horizon \(H\) (number of treatment steps), see Table 1 for an instance. However, learning agents are known to implicitly memorize details of individual training data points verbatim [4], even if they are irrelevant for learning [5], which makes offline RL models vulnerable to various privacy attacks.

Differential privacy (DP) [6] is a well-established definition of privacy with many desirable properties. A differentially private offline RL algorithm will return a decision policy that is indistinguishable from a policy trained in an alternative universe any individual user is replaced, thereby preventing the aforementioned privacy risks. There is a surge of recent interest in developing RL algorithms with DP guarantees, but they focus mostly on the online setting [7]–[11].

Offline RL is arguably more practically relevant than online RL in the applications with sensitive data. For example, in the healthcare domain, online RL requires actively running new exploratory policies (clinical trials) with every new patient, which often involves complex ethical / legal clearances, whereas offline RL uses only historical patient records that are often accessible for research purposes. Clear communication of the adopted privacy enhancing techniques (e.g., DP) to patients was reported to further improve data access [12].

Our contributions. In this paper, we present the first provably efficient algorithms for offline RL with differential privacy. Our contributions are twofold.

• We design two new pessimism-based algorithms DP-APVI (Algorithm 1) and DP-VAPVI (Algorithm 2), one for the tabular setting (finite states and actions), the other for the case with linear function approximation (under linear MDP assumption). Both algorithms enjoy DP guarantees (pure DP or zCDP) and instance-dependent learning bounds where the cost of privacy appears as lower order terms.

• We perform numerical simulations to evaluate and compare the performance of our algorithm DP-VAPVI (Algorithm 2) with its non-private counterpart VAPVI [13] as well as a popular baseline PEVI [14]. The results complement the theoretical findings by demonstrating the practicality of DP-VAPVI under strong privacy parameters.

Related work. To our knowledge, differential privacy in offline RL tasks has not been studied before, except for much simpler cases where the agent only evaluates a single policy [15], [16]. [15] privatized first-visit Monte Carlo-Ridge Regression estimator by an output perturbation mechanism and [16] used DP-SGD. Neither paper considered offline learning (or policy optimization), which is our focus.

There is a larger body of work on private RL in the online setting, where the goal is to minimize regret while satisfying either joint differential privacy [7], [10], [11], [17] or local differential privacy [8]–[11]. The offline setting introduces new challenges in DP as we cannot algorithmically enforce good “exploration”, but have to work with a static dataset and privately estimate the uncertainty in addition to the value functions. A private online RL algorithm can sometimes be adapted for private offline RL too, but those from existing work yield suboptimal and non-adaptive bounds. We give a more detailed technical comparison in Appendix 9.

Among non-private offline RL works, we build directly upon non-private offline RL methods known as Adaptive Pessimistic Value Iteration (APVI, for tabular MDPs) [18] and Variance-Aware Pessimistic Value Iteration (VAPVI, for linear MDPs) [13], as they give the strongest theoretical guarantees to date. We refer readers to Appendix 9 for a more extensive review of the offline RL literature. Introducing DP to APVI and VAPVI while retaining the same sample complexity (modulo lower order terms) require nontrivial modifications to the algorithms.

A remark on technical novelty. Our algorithms involve substantial technical innovation over previous works on online DP-RL with joint DP guarantee². Different from previous works, our DP-APVI (Algorithm 1) operates on Bernstein type pessimism, which requires our algorithm to deal with conditional variance using private statistics. Besides, our DP-VAPVI (Algorithm 2) replaces the LSVI technique with variance-aware LSVI (also known as weighted ridge regression, first appears in [19]). Our DP-VAPVI releases conditional variance privately, and further applies weighted ridge regression privately. Both approaches ensure tighter instance-dependent bounds on the suboptimality of the learned policy.

2 Problem Setup↩︎

Markov Decision Process. A finite-horizon Markov Decision Process (MDP) is denoted by a tuple \(M=(\mathcal{S}, \mathcal{A}, P, r, H, d_1)\) [20], where \(\mathcal{S}\) is state space and \(\mathcal{A}\) is action space. A non-stationary transition kernel \(P_h:\mathcal{S}\times\mathcal{A}\times\mathcal{S} \mapsto [0, 1]\) maps each state action \((s_h,a_h)\) to a probability distribution \(P_h(\cdot|s_h,a_h)\) and \(P_h\) can be different across time. Besides, \(r_h : \mathcal{S} \times{A} \mapsto \mathbb{R}\) is the expected immediate reward satisfying \(0\leq r_h\leq1\), \(d_1\) is the initial state distribution and \(H\) is the horizon. A policy \(\pi=(\pi_1,\cdots,\pi_H)\) assigns each state \(s_h \in \mathcal{S}\) a probability distribution over actions according to the map \(s_h\mapsto \pi_h(\cdot|s_h)\), \(\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 according to \(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]\).

For tabular MDP, we have \(\mathcal{S}\times\mathcal{A}\) is the discrete state-action space and \(S:=|\mathcal{S}|,A:=|\mathcal{A}|\) are finite. In this work, we assume that \(r\) is known³. In addition, we denote the per-step marginal state-action occupancy \(d^\pi_h(s,a)\) as: \(d^\pi_h(s,a):=\mathbb{P}[s_h=s|s_1\sim d_1,\pi]\cdot\pi_h(a|s),\) which is the marginal state-action probability at time \(h\).

Value function, Bellman (optimality) equations. The value function \(V^\pi_h(\cdot)\) and Q-value function \(Q^\pi_h(\cdot,\cdot)\) for any policy \(\pi\) is 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\, h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}.\) The performance is defined as \(v^\pi:=\mathbb{E}_{d_1}\left[V^\pi_1\right]=\mathbb{E}_{\pi,d_1}\left[\sum_{t=1}^H r_t\right]\). The Bellman (optimality) equations follow \(\forall\, h\in[H]\): \(Q^\pi_h=r_h+P_hV^\pi_{h+1},\;\;V^\pi_h=\mathbb{E}_{a\sim\pi_h}[Q^\pi_h], \;\;\;Q^\star_h=r_h+P_hV^\star_{h+1},\; V^\star_h=\max_a Q^\star_h(\cdot,a).\)

Linear MDP [21]. An episodic MDP \((\mathcal{S},\mathcal{A},H,P,r)\) is called a linear MDP with known feature map \(\phi:\mathcal{S}\times\mathcal{A}\rightarrow \mathbb{R}^d\) if there exist \(H\) unknown signed measures \(\nu_h\in\mathbb{R}^d\) over \(\mathcal{S}\) and \(H\) unknown reward vectors \(\theta_h\in\mathbb{R}^d\) such that \[{P}_{h}\left(s^{\prime} \mid s, a\right)=\left\langle\phi(s, a), \nu_{h}\left(s^{\prime}\right)\right\rangle, \quad r_{h}\left(s, a\right) =\left\langle\phi(s, a), \theta_{h}\right\rangle,\quad\forall\, (h,s,a,s^{\prime})\in[H]\times\mathcal{S}\times\mathcal{A}\times\mathcal{S}.\] Without loss of generality, we assume \(\|\phi(s,a)\|_2\leq 1\) and \(\max(\|\nu_h(\mathcal{S})\|_2,\|\theta_h\|_2)\leq \sqrt{d}\) for all \(h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}\). An important property of linear MDP is that the value functions are linear in the feature map, which is summarized in Lemma 40.

Offline setting and the goal. The offline RL requires the agent to find a policy \(\pi\) in order to maximize the performance \(v^\pi\), given only the episodic data \(\mathcal{D}=\left\{\left(s_{h}^{\tau}, a_{h}^{\tau}, r_{h}^{\tau}, s_{h+1}^{\tau}\right)\right\}_{\tau\in[n]}^{h\in[H]}\)⁴ rolled out from some fixed and possibly unknown behavior policy \(\mu\), which means we cannot change \(\mu\) and in particular we do not assume the functional knowledge of \(\mu\). In conclusion, based on the batch data \(\mathcal{D}\) and a targeted accuracy \(\epsilon>0\), the agent seeks to find a policy \(\pi_\text{alg}\) such that \(v^\star-v^{\pi_\text{alg}}\leq\epsilon\).

2.1 Assumptions in offline RL↩︎

In order to show that our privacy-preserving algorithms can generate near optimal policy, certain coverage assumptions are needed. In this section, we will list the assumptions we use in this paper.

Assumptions for tabular setting.

Assumption 1 is the weakest assumption needed for accurately learning the optimal value \(v^\star\) by requiring \(\mu\) to trace the state-action space of one optimal policy (\(\mu\) can be agnostic at other locations). Similar to [18], we will use Assumption 1 for the tabular part of this paper, which enables comparison between our sample complexity to the conclusion in [18], whose algorithm serves as a non-private baseline.

Assumptions for linear setting. First, we define the expectation of covariance matrix under the behavior policy \(\mu\) for all time step \(h\in[H]\) as below: \[\Sigma^p_h:=\mathbb{E}_{\mu}\left[\phi(s_h,a_h)\phi(s_h,a_h)^\top\right].\] As have been shown in [13], [23], learning a near-optimal policy from offline data requires coverage assumptions. Here in linear setting, such coverage is characterized by the minimum eigenvalue of \(\Sigma^p_h\). Similar to [13], we apply the following assumption for the sake of comparison.

2.2 Differential Privacy in offline RL↩︎

In this work, we aim to design privacy-preserving algorithms for offline RL. We apply differential privacy as the formal notion of privacy. Below we revisit the definition of differential privacy.

In the problem of offline RL, the dataset consists of several trajectories, therefore one data point in Definition 1 refers to one single trajectory. Hence the definition of Differential Privacy means that the difference in the distribution of the output policy resulting from replacing one trajectory in the dataset will be small. In other words, an adversary can not infer much information about any single trajectory in the dataset from the output policy of the algorithm.

During the whole paper, we will use zCDP (defined below) as a surrogate for DP, since it enables cleaner analysis for privacy composition and Gaussian mechanism. The properties of zCDP (e.g., composition, conversion formula to DP) are deferred to Appendix 12.3.

Finally, we go over the definition and privacy guarantee of Gaussian mechanism.

We emphasize that the privacy guarantee covers any input data. It does not require any distributional assumptions on the data. The RL-specific assumptions (e.g., linear MDP and coverage assumptions) are only used for establishing provable utility guarantees.

3 Results under tabular MDP: DP-APVI (Algorithm 1)↩︎

For reinforcement learning, the tabular MDP setting is the most well-studied setting and our first result applies to this regime. We begin with the construction of private counts.

Private Model-based Components. Given data \(\mathcal{D}=\left\{\left(s_{h}^{\tau}, a_{h}^{\tau}, r_{h}^{\tau}, s_{h+1}^{\tau}\right)\right\}_{\tau\in[n]}^{h \in[H]}\), we denote \(n_{s_h,a_h}:=\sum_{\tau=1}^n\mathbb{1}[s_h^{\tau},a_h^{\tau}=s_h,a_h]\) be the total counts that visit \((s_h,a_h)\) pair at time \(h\) and \(n_{s_h,a_h,s_{h+1}}:=\sum_{\tau=1}^n\mathbb{1}[s_h^{\tau},a_h^{\tau},s_{h+1}^{\tau}=s_h,a_h,s_{h+1}]\) be the total counts that visit \((s_h,a_h,s_{h+1})\) pair at time \(h\), then given the budget \(\rho\) for zCDP, we add independent Gaussian noises to all the counts: \[\label{eqn:noisy95est} n_{s_h,a_h}^{\prime}=\left\{n_{s_h,a_h}+\mathcal{N}(0,\sigma^{2})\right\}^{+},\,\,n_{s_h,a_h,s_{h+1}}^{\prime}=\left\{n_{s_h,a_h,s_{h+1}}+\mathcal{N}(0,\sigma^{2})\right\}^{+},\,\, \sigma^{2}=\frac{2H}{\rho}.\tag{1}\]

However, after adding noise, the noisy counts \(n^{\prime}\) may not satisfy \(n^{\prime}_{s_h,a_h}=\sum_{s_{h+1}\in\mathcal{S}}n^{\prime}_{s_h,a_h,s_{h+1}}\). To address this problem, we choose the private counts of visiting numbers as the solution to the following optimization problem (here \(E_{\rho}=4\sqrt{\frac{H\log{\frac{4HS^{2}A}{\delta}}}{\rho}}\) is chosen as a high probability uniform bound of the noises we add): \[\label{eqn:final95choice} \begin{align} \{\widetilde{n}_{s_h,a_h,s^{\prime}}\}_{s^{\prime}\in\mathcal{S}}=\mathrm{argmin}_{\{x_{s^{\prime}}\}_{s^{\prime}\in\mathcal{S}}} \max_{s^{\prime}\in\mathcal{S}} \left|x_{s^{\prime}}-n^{\prime}_{s_h,a_h,s^{\prime}}\right| \\ \text{such that}\,\, \left|\sum_{s^{\prime}\in\mathcal{S}}x_{s^{\prime}}-n^{\prime}_{s_h,a_h}\right|\leq \frac{E_{\rho}}{2}\,\,\text{and}\,\,x_{s^{\prime}}\geq 0, \forall\, s^{\prime}\in \mathcal{S}. \\ \widetilde{n}_{s_h,a_h}=\sum_{s^{\prime}\in\mathcal{S}}\widetilde{n}_{s_h,a_h,s^{\prime}}. \end{align}\tag{2}\]

The private estimation of the transition kernel is defined as: \[\label{eqn:mb95est} \widetilde{P}_h(s^{\prime}|s_h,a_h)=\frac{\widetilde{n}_{s_h,a_h,s^{\prime}}}{\widetilde{n}_{s_h,a_h}},\tag{3}\] if \(\widetilde{n}_{s_h,a_h}>E_{\rho}\) and \(\widetilde{P}_h(s'|s_h,a_h)=\frac{1}{S}\) otherwise.

Algorithmic design. Our algorithmic design originates from the idea of pessimism, which holds conservative view towards the locations with high uncertainty and prefers the locations we have more confidence about. Based on the Bernstein type pessimism in APVI [18], we design a similar pessimistic algorithm with private counts to ensure differential privacy. If we replace \(\widetilde{n}\) and \(\widetilde{P}\) with \(n\) and \(\widehat{P}\)⁶, then our DP-APVI (Algorithm 1) will degenerate to APVI. Compared to the pessimism defined in APVI, our pessimistic penalty has an additional term \(\widetilde{O}\left(\frac{SHE_\rho}{\widetilde{n}_{s_h,a_h}}\right)\), which accounts for the additional pessimism due to our application of private statistics.

We state our main theorem about DP-APVI below, the proof sketch is deferred to Appendix 10.1 and detailed proof is deferred to Appendix 10 due to space limit.

Comparison to non-private counterpart APVI [18]. According to Theorem 4.1 in [18], the sub-optimality bound of APVI is for large enough \(n\), with high probability, the output \(\widehat{\pi}\) satisfies: \[0\leq v^\star-v^{\widehat{\pi}}\leq \widetilde{O}\left(\sum_{h=1}^H\sum_{(s_h,a_h)\in\mathcal{C}_h}d^{\pi^\star}_h(s_h,a_h)\sqrt{\frac{\mathrm{Var}_{P_h(\cdot|s_h,a_h)}(V^\star_{h+1}(\cdot))}{nd^\mu_h(s_h,a_h)}}\right)+\widetilde{O}\left(\frac{H^3}{n\cdot\bar{d}_m}\right).\] Compared to our Theorem 5, the additional sub-optimality bound due to differential privacy is \(\widetilde{O}\left(\frac{SH^2E_\rho}{n\cdot\bar{d}_m}\right)=\widetilde{O}\left(\frac{SH^\frac{5}{2}}{n\cdot\bar{d}_m\sqrt{\rho}}\right)=\widetilde{O}\left(\frac{SH^{\frac{5}{2}}}{n\cdot\bar{d}_m\epsilon}\right)\).⁷ In the most popular regime where the privacy budget \(\rho\) or \(\epsilon\) is a constant, the additional term due to differential privacy appears as a lower order term, hence becomes negligible as the sample complexity \(n\) becomes large.

Comparison to Hoeffding type pessimism. We can simply revise our algorithm by using Hoeffding type pessimism, which replaces the pessimism in line 5 with \(C_1H\cdot\sqrt{\frac{\iota}{\widetilde{n}_{s_h,a_h}-E_\rho}}+\frac{C_2SHE_{\rho}\cdot\iota}{\widetilde{n}_{s_h,a_h}}\). Then with a similar proof schedule, we can arrive at a sub-optimality bound that with high probability, \[0\leq v^\star-v^{\widehat{\pi}}\leq \widetilde{O}\left(H\cdot\sum_{h=1}^H\sum_{(s_h,a_h)\in\mathcal{C}_h}d^{\pi^\star}_h(s_h,a_h)\sqrt{\frac{1}{nd^\mu_h(s_h,a_h)}}\right)+\widetilde{O}\left(\frac{SH^2E_\rho}{n\cdot\bar{d}_m}\right).\] Compared to our Theorem 5, our bound is tighter because we express the dominate term by the system quantities instead of explicit dependence on \(H\) (and \(\mathrm{Var}_{P_h(\cdot|s_h,a_h)}(V^\star_{h+1}(\cdot))\leq H^2\)). In addition, we highlight that according to Theorem G.1 in [18], our main term nearly matches the non-private minimax lower bound. For more detailed discussions about our main term and how it subsumes other optimal learning bounds, we refer readers to [18].

Apply Laplace Mechanism to achieve pure DP. To achieve Pure DP instead of \(\rho\)-zCDP, we can simply replace Gaussian Mechanism with Laplace Mechanism (defined as Definition 5). Given privacy budget for Pure DP \(\epsilon\), since the \(\ell_1\) sensitivity of \(\{n_{s_h,a_h}\}\cup\{n_{s_h,a_h,s_{h+1}}\}\) is \(\Delta_1=4H\), we can add independent Laplace noises \(\mathrm{Lap}(\frac{4H}{\epsilon})\) to each count to achieve \(\epsilon\)-DP due to Lemma 44. Then by using \(E_\epsilon=\widetilde{O}\left(\frac{H}{\epsilon}\right)\) instead of \(E_\rho\) and keeping everything else (2 , 3 and Algorithm 1) the same, we can reach a similar result to Theorem 5 with the same proof schedule. The only difference is that here the additional learning bound is \(\widetilde{O}\left(\frac{SH^3}{n\cdot\bar{d}_m\epsilon}\right)\), which still appears as a lower order term.

4 Results under linear MDP: DP-VAPVI(Algorithm 2)↩︎

In large MDPs, to address the computational issues, the technique of function approximation is widely applied, and linear MDP is a concrete model to study linear function approximations. Our second result applies to the linear MDP setting. Generally speaking, function approximation reduces the dimensionality of private releases comparing to the tabular MDPs. We begin with private counts.

Private Model-based Components. Given the two datasets \(\mathcal{D}\) and \(\mathcal{D}'\) (both from \(\mu\)) as in Algorithm 2, we can apply variance-aware pessimistic value iteration to learn a near optimal policy as in VAPVI [13]. To ensure differential privacy, we add independent Gaussian noises to the \(5H\) statistics as in DP-VAPVI (Algorithm 2) below. Since there are \(5H\) statistics, by the adaptive composition of zCDP (Lemma 43), it suffices to keep each count \(\rho_0\)-zCDP, where \(\rho_0=\frac{\rho}{5H}\). In DP-VAPVI, we use \(\phi_1,\phi_2,\phi_3,K_1,K_2\)⁸ to denote the noises we add. For all \(\phi_i\), we directly apply Gaussian Mechanism. For \(K_i\), in addition to the noise matrix \(\frac{1}{\sqrt{2}}(Z+Z^{\top})\), we also add \(\frac{E}{2}I_d\) to ensure that all \(K_i\) are positive definite with high probability (The detailed definition of \(E,L\) can be found in Appendix 8).

Below we will show the algorithmic design of DP-VAPVI (Algorithm 2). For the offline dataset, we divide it into two independent parts with equal length: \(\mathcal{D}=\{(s_{h}^\tau, a_{h}^\tau, r_{ h}^\tau, s_{ h+1}^{\tau})\}^{h\in[H]}_{\tau \in[K]}\) and \(\mathcal{D}'=\{(\bar{s}_{ h}^\tau, \bar{a}_{h}^\tau, \bar{r}_{h}^\tau, \bar{s}_{h+1}^{\tau})\}^{h\in[H]}_{\tau \in[K]}\). One for estimating variance and the other for calculating \(Q\)-values.

Estimating conditional variance. The first part (line 4 to line 8) aims to estimate the conditional variance of \(\widetilde{V}_{h+1}\) via the definition of variance: \([\mathrm{Var}_h \widetilde{V}_{h+1}](s,a)=[P_h(\widetilde{V}_{h+1})^2](s,a)-([P_h\widetilde{V}_{h+1}](s,a))^2\). For the first term, by the definition of linear MDP, it holds that \(\left[{P}_{h}\widetilde{V}_{h+1}^{2}\right](s, a)={\phi}(s, a)^{\top} \int_{\mathcal{S}} \widetilde{V}_{h+1}^2\left(s^{\prime}\right)\mathrm{~d} {\nu}_{h}\left(s^{\prime}\right)=\langle\phi ,\int_{\mathcal{S}} \widetilde{V}_{h+1}^2\left(s^{\prime}\right) \mathrm{~d} {\nu}_{h}\left(s^{\prime}\right)\rangle\). We can estimate \(\beta_h=\int_{\mathcal{S}} \widetilde{V}_{h+1}^2\left(s^{\prime}\right) \mathrm{~d} {\nu}_{h}\left(s^{\prime}\right)\) by applying ridge regression. Below is the output of ridge regression with raw statistics without noise:

\[\underset{{\beta} \in \mathbb{R}^{d}}{\operatorname{argmin}} \sum_{k=1}^{K}\left[\left\langle{\phi}(\bar{s}^k_h,\bar{a}^k_h), {\beta}\right\rangle-\widetilde{V}_{h+1}^2\left(\bar{s}_{h+1}^k\right)\right]^{2}+\lambda\|{\beta}\|_{2}^{2}={\bar{\Sigma}}_{h}^{-1} \sum_{k=1}^{K} {{\phi}}(\bar{s}^k_h,\bar{a}^k_h) \widetilde{V}_{h+1}^2\left(\bar{s}_{h+1}^k\right),\] where definition of \(\bar{\Sigma}_{h}\) can be found in Appendix 8. Instead of using the raw statistics, we replace them with private ones with Gaussian noises as in line 5. The second term is estimated similarly in line 6. The final estimator is defined as in line 8: \(\widetilde{\sigma}_h(\cdot,\cdot)^2=\max\{1,\widetilde{\mathrm{Var}}_h\widetilde{V}_{h+1}(\cdot,\cdot)\}\).⁹

Variance-weighted LSVI. Instead of directly applying LSVI [14], we can solve the variance-weighted LSVI (line 10). The result of variance-weighted LSVI with non-private statistics is shown below: \[\underset{{w} \in \mathbb{R}^{d}}{\operatorname{argmin}} \;\lambda\|{w}\|_{2}^{2}+\sum_{k=1}^{K}\frac{\left[\langle {\phi}(s_{h}^k,a_{h}^k), {w}\rangle-r_{ h}^k-\widetilde{V}_{h+1}(s_{h+1}^{ k})\right]^{2}}{\widetilde{\sigma}^2_h(s_h^k,a_h^k)}=\widehat{\Lambda}_{h}^{-1}\sum_{k=1}^{K}\frac{ \phi\left(s_{h}^{k}, a_{h}^{k}\right) \cdot\left[r_{h}^{k}+\widetilde{V}_{h+1}\left(s_{h+1}^{k}\right)\right]}{\widetilde{\sigma}_h^2(s^k_h,a^k_h)},\] where definition of \(\widehat{\Lambda}_h\) can be found in Appendix 8. For the sake of differential privacy, we use private statistics instead and derive the \(\widetilde{w}_h\) as in line 10.

Our private pessimism. Notice that if we remove all the Gaussian noises we add, our DP-VAPVI (Algorithm 2) will degenerate to VAPVI [13]. We design a similar pessimistic penalty using private statistics (line 11), with additional \(\frac{D}{K}\) accounting for the extra pessimism due to DP.

Main theorem. We state our main theorem about DP-VAPVI below, the proof sketch is deferred to Appendix 11.1 and detailed proof is deferred to Appendix 11 due to space limit. Note that quantities \(\mathcal{M}_i,L,E\) can be found in Appendix 8 and briefly, \(L=\widetilde{O}(\sqrt{H^3d/\rho})\), \(E=\widetilde{O}(\sqrt{Hd/\rho})\). For the sample complexity lower bound, within the practical regime where the privacy budget is not very small, \(\max\{\mathcal{M}_i\}\) is dominated by \(\max\{\widetilde{O}(H^{12}d^3/\kappa^5),\widetilde{O}(H^{14}d/\kappa^5)\}\), which also appears in the sample complexity lower bound of VAPVI [13]. The \(\sigma_{V}^2(s,a)\) in Theorem 6 is defined as \(\max\{1,\mathrm{Var}_{P_h}(V)(s,a)\}\) for any \(V\).

Comparison to non-private counterpart VAPVI [13]. Plugging in the definition of \(L,E\) (Appendix 8), under the meaningful case that the privacy budget is not very large, \(DH\) is dominated by \(\widetilde{O}\left(\frac{H^{\frac{11}{2}}d/\kappa^{\frac{3}{2}}}{\sqrt{\rho}}\right)\). According to Theorem 3.2 in [13], the sub-optimality bound of VAPVI is for sufficiently large \(K\), with high probability, the output \(\widehat{\pi}\) satisfies: \[v^\star-v^{\widehat{\pi}}\leq \widetilde{O}\left(\sqrt{d}\cdot\sum_{h=1}^H\mathbb{E}_{\pi^\star}\bigg[\sqrt{\phi(\cdot, \cdot)^{\top} \Lambda_{h}^{\star-1} \phi(\cdot, \cdot)}\bigg]\right)+\frac{2H^4\sqrt{d}}{K}.\] Compared to our Theorem 6, the additional sub-optimality bound due to differential privacy is \(\widetilde{O}\left(\frac{H^{\frac{11}{2}}d/\kappa^{\frac{3}{2}}}{\sqrt{\rho}\cdot K}\right)=\widetilde{O}\left(\frac{H^{\frac{11}{2}}d/\kappa^{\frac{3}{2}}}{\epsilon\cdot K}\right)\).¹⁰ In the most popular regime where the privacy budget \(\rho\) or \(\epsilon\) is a constant, the additional term due to differential privacy also appears as a lower order term. Instance-dependent sub-optimality bound. Similar to DP-APVI (Algorithm 1), our DP-VAPVI (Algorithm 2) also enjoys instance-dependent sub-optimality bound. First, the main term in ?? improves PEVI [14] over \(O(\sqrt{d})\) on feature dependence. Also, our main term admits no explicit dependence on \(H\), thus improves the sub-optimality bound of PEVI on horizon dependence. For more detailed discussions about our main term, we refer readers to [13].

5 Tightness of our results↩︎

We believe our bounds for offline RL with DP is tight. To the best of our knowledge, APVI and VAPVI provide the tightest bound under tabular MDP and linear MDP, respectively. The suboptimality bounds of our algorithms match these two in the main term, with some lower order additional terms. The leading terms are known to match multiple information-theoretical lower bounds for offline RL simultaneously (this was illustrated in [13], [18]), for this reason our bound cannot be improved in general. For the lower order terms, the dependence on sample complexity \(n\) and privacy budget \(\epsilon\): \(\widetilde{O}(\frac{1}{n\epsilon})\) is optimal since policy learning is a special case of ERM problems and such dependence is optimal in DP-ERM. In addition, we believe the dependence on other parameters (\(H,S,A,d\)) in the lower order term is tight due to our special tricks as 2 and Lemma 17.

6 Simulations↩︎

In this section, we carry out simulations to evaluate the performance of our DP-VAPVI (Algorithm 2), and compare it with its non-private counterpart VAPVI [13] and another pessimism-based algorithm PEVI [14] which does not have privacy guarantee.

Experimental setting. We evaluate DP-VAPVI (Algorithm 2) on a synthetic linear MDP example that originates from the linear MDP in [13], [31] but with some modifications.¹¹ For details of the linear MDP setting, please refer to Appendix 13. The two MDP instances we use both have horizon \(H=20\). We compare different algorithms in figure 3 (a), while in figure 3 (b), we compare our DP-VAPVI with different privacy budgets. When doing empirical evaluation, we do not split the data for DP-VAPVI or VAPVI and for DP-VAPVI, we run the simulation for \(5\) times and take the average performance.

Results and discussions. From Figure 3, we can observe that DP-VAPVI (Algorithm 2) performs slightly worse than its non-private version VAPVI [13]. This is due to the fact that we add Gaussian noise to each count. However, as the size of dataset goes larger, the performance of DP-VAPVI will converge to that of VAPVI, which supports our theoretical conclusion that the cost of privacy only appears as lower order terms. For DP-VAPVI with larger privacy budget, the scale of noise will be smaller, thus the performance will be closer to VAPVI, as shown in figure 3 (b). Furthermore, in most cases, DP-VAPVI still outperforms PEVI, which does not have privacy guarantee. This arises from our privitization of variance-aware LSVI instead of LSVI.

7 Conclusion and future works↩︎

In this work, we take the first steps towards the well-motivated task of designing private offline RL algorithms. We propose algorithms for both tabular MDPs and linear MDPs, and show that they enjoy instance-dependent sub-optimality bounds while guaranteeing differential privacy (either zCDP or pure DP). Our results highlight that the cost of privacy only appears as lower order terms, thus become negligible as the number of samples goes large.

Future extensions are numerous. We believe the technique in our algorithms (privitization of Bernstein-type pessimism and variance-aware LSVI) and the corresponding analysis can be used in online settings too to obtain tighter regret bounds for private algorithms. For the offline RL problems, we plan to consider more general function approximations and differentially private (deep) offline RL which will bridge the gap between theory and practice in offline RL applications. Many techniques we developed could be adapted to these more general settings.

Acknowledgments↩︎

The research is partially supported by NSF Awards #2007117 and #2048091. The authors would like to thank Ming Yin for helpful discussions.

8 Notation List↩︎

8.1 Notations for tabular MDP↩︎

\(E_{\rho}\)	\(4\sqrt{\frac{H\log{\frac{4HS^{2}A}{\delta}}}{\rho}}\)
\(n\)	The original counts of visitation
\(n^{\prime}\)	The noisy counts, as defined in 1
\(\widetilde{n}\)	Final choice of private counts, as defined in 2
\(\widetilde{P}\)	Private estimate of transition kernel, as defined in 3
\(\widehat{P}\)	Non-private estimate of transition kernel, as defined in 6
\(\iota\)	\(\log\frac{HSA}{\delta}\)
\(\rho\)	Budget for zCDP
\(\delta\)	Failure probability

8.2 Notations for linear MDP↩︎

\(L\)	\(2H\sqrt{\frac{5Hd\log(\frac{10Hd}{\delta})}{\rho}}\)
\(E\)	\(\sqrt{\frac{10Hd}{\rho}}\left(2+\left(\frac{\log(5c_1 H/\delta)}{c_2 d}\right)^{\frac{2}{3}}\right)\)
\(D\)	\(\widetilde{O}\left(\frac{H^2L}{\kappa}+\frac{H^4E\sqrt{d}}{\kappa^{3/2}}+H^3\sqrt{d}\right)\)
\(\widehat{\Lambda}_h\)	\(\sum_{k=1}^K\phi(s_{h}^k,a_{h}^k)\phi(s_{h}^k,a_{h}^k)^\top/\widetilde{\sigma}^2_h(s_{h}^k,a_{h}^k) +\lambda I_d\)
\(\widetilde{\Lambda}_h\)	\(\sum_{k=1}^K\phi(s_{h}^k,a_{h}^k)\phi(s_{h}^k,a_{h}^k)^\top/\widetilde{\sigma}^2_h(s_{h}^k,a_{h}^k) +\lambda I_d+K_2\)
\(\widetilde{\Lambda}^p_h\)	\(\mathbb{E}_{\mu,h}[\widetilde{\sigma}_h^{-2}(s,a)\phi(s,a)\phi(s,a)^{\top}]\)
\({\Lambda}_h\)	\(\sum_{\tau=1}^K \phi(s^\tau_h,a^\tau_h) \phi(s^\tau_h,a^\tau_h)^\top/\sigma_{\widetilde{V}_{h+1}}^2(s^\tau_h,a^\tau_h) +\lambda I\)
\(\Lambda_h^p\)	\(\mathbb{E}_{\mu,h}[\sigma^{-2}_{\widetilde{V}_{h+1}}(s,a)\phi(s,a)\phi(s,a)^\top]\)
\({\Lambda}^\star_h\)	\(\sum_{\tau=1}^K \phi(s^\tau_h,a^\tau_h) \phi(s^\tau_h,a^\tau_h)^\top/\sigma_{{V}^\star_{h+1}}^2(s^\tau_h,a^\tau_h) +\lambda I\)
\(\bar{\Sigma}_h\)	\(\sum_{\tau=1}^K\phi(\bar{s}_{h}^\tau,\bar{a}_{h}^\tau)\phi(\bar{s}_{h}^\tau,\bar{a}_{h}^\tau)^\top +\lambda I_d\)
\(\widetilde{\Sigma}_h\)	\(\sum_{\tau=1}^K\phi(\bar{s}_{h}^\tau,\bar{a}_{h}^\tau)\phi(\bar{s}_{h}^\tau,\bar{a}_{h}^\tau)^\top +\lambda I_d+K_1\)
\(\Sigma^p_h\)	\(\mathbb{E}_{\mu,h}\left[\phi(s,a)\phi(s,a)^\top\right]\)
\(\kappa\)	\(\min_h \lambda_{\mathrm{min}}(\Sigma^p_h)\)
\(\sigma_{V}^2(s,a)\)	\(\max\{1,\mathrm{Var}_{P_h}(V)(s,a)\}\) for any \(V\)
\(\sigma^{\star2}_{h}(s,a)\)	\(\max \left\{1, {\mathrm{Var}}_{P_h} {V}^\star_{h+1}(s,a)\right\}\)
\(\widetilde{\sigma}_{h}^2(s,a)\)	\(\max\{1,\widetilde{\mathrm{Var}}_h \widetilde{V}_{h+1}(s,a)\}\)
\(\mathcal{M}_1\)	\(\max\{2\lambda, 128\log(2dH/\delta),\frac{128H^4\log(2dH/\delta)}{\kappa^2},\frac{\sqrt{2}L}{\sqrt{d\kappa}}\}\)
\(\mathcal{M}_2\)	\(\max\{\widetilde{O}(H^{12}d^3/\kappa^5),\widetilde{O}(H^{14}d/\kappa^5)\}\)
\(\mathcal{M}_3\)	\(\max \left\{\frac{512 H^4\log \left(\frac{2 dH}{\delta}\right)}{\kappa^2}, \frac{4 \lambda H^2}{\kappa}\right\}\)
\(\mathcal{M}_4\)	\(\max\{\frac{H^2L^2}{d\kappa},\frac{H^6E^2}{\kappa^2},H^4\kappa\}\)
\(\rho\)	Budget for zCDP
\(\delta\)	Failure probability (not the \(\delta\) of \((\epsilon,\delta)\)-DP)
\(\xi\)	\(\sup_{V\in[0,H],\;s'\sim P_h(s,a),\;h\in[H]}\left|\frac{r_h+{V}\left(s'\right)-\left(\mathcal{T}_{h} {V}\right)\left(s, a\right)}{{\sigma}_{{V}}(s,a)}\right|\)

9 Extended related work↩︎

Online reinforcement learning under JDP or LDP. For online RL, some recent works analyze this setting under Joint Differential Privacy (JDP), which requires the RL agent to minimize regret while handling user’s raw data privately. Under tabular MDP, [7] design PUCB by revising UBEV [32]. Private-UCB-VI [10] results from UCBVI (with bonus-1) [33]. However, both works privatize Hoeffding type bonus, which lead to sub-optimal regret bound. Under linear MDP, Private LSVI-UCB [17] and Privacy-Preserving LSVI-UCB [11] are private versions of LSVI-UCB [21], while LinOpt-VI-Reg [34] and Privacy-Preserving UCRL-VTR [11] generalize UCRL-VTR [35]. However, these works are usually based on the LSVI technique [21] (unweighted ridge regression), which does not ensure optimal regret bound.

In addition to JDP, another common privacy guarantee for online RL is Local Differential Privacy (LDP), LDP is a stronger definition of DP since it requires that the user’s data is protected before the RL agent has access to it. Under LDP, [8] reach a regret lower bound and design LDP-OBI which has matching regret upper bound. The result is generalized by [9] to linear mixture setting. Later, [11] provide an unified framework for analyzing JDP and LDP under linear setting.

Some other differentially private learning algorithms. There are some other works about differentially private online learning [36]–[38] and various settings of bandit [39]–[44]. For the reinforcement learning setting, [45] propose privacy-preserving Q-learning to protect the reward information. [46] study the problem of distributed reinforcement learning under LDP. [47] present an actor critic algorithm with differentially private critic. [48] tackle DP-RL under the policy gradient framework. [49] consider the adaptive control of differentially private linear quadratic (LQ) systems.

Offline reinforcement learning under tabular MDP. Under tabular MDP, there are several works achieving optimal sub-optimality/sample complexity bounds under different coverage assumptions. For the problem of off-policy evaluation (OPE), [50] uses Tabular-MIS estimator to achieve asymptotic efficiency. In addition, the idea of uniform OPE is used to achieve the optimal sample complexity \(O(H^3/d_m\epsilon^2)\) [51] for non-stationary MDP and the optimal sample complexity \(O(H^2/d_m\epsilon^2)\) [52] for stationary MDP, where \(d_m\) is the lower bound for state-action occupancy. Such uniform convergence idea also supports some works regarding online exploration [53], [54]. For offline RL with single concentrability assumption, [55] arrive at the optimal sample complexity \(O(H^3SC^\star/\epsilon^2)\). Recently, [18] propose APVI which can lead to instance-dependent sub-optimality bound, which subsumes previous optimal results under several assumptions.

Offline reinforcement learning under linear MDP. Recently, many works focus on offline RL under linear representation. [14] present PEVI which applies the idea of pessimistic value iteration (the idea originates from [21]), and PEVI is provably efficient for offline RL under linear MDP. [13] improve the sub-optimality bound in [14] by replacing LSVI by variance-weighted LSVI. [56] consider Bellman consistent pessimism for general function approximation, and their result improves the sample complexity in [14] by order \(O(d)\) (shown in Theorem 3.2). However, there is no improvement on horizon dependence. [57] propose a new offline actor-critic algorithm that naturally incorporates the pessimism principle. Besides, [23], [58] study the statistical hardness of offline RL with linear representations by presenting exponential lower bounds.

10 Proof of Theorem 5↩︎

10.1 Proof sketch↩︎

Since the whole proof for privacy guarantee is not very complex, we present it in Section 10.2 below and only sketch the proof for suboptimality bound.

First of all, we bound the scale of noises we add to show that the \(\widetilde{n}\) derived from 2 are close to real visitation numbers. Therefore, denoting the non-private empirical transition kernel by \(\widehat{P}\) (detailed definition in 6 ), we can show that \(\|\widetilde{P}-\widehat{P}\|_1\) and \(|\sqrt{\mathrm{Var}_{\widetilde{P}}(V)}-\sqrt{\mathrm{Var}_{\widehat{P}}(V)}|\) are small.

Next, resulting from the conditional independence of \(\widetilde{V}_{h+1}\) and \(\widetilde{P}_h\), we apply Empirical Bernstein’s inequality to get \(|(\widetilde{P}_h-P_h)\widetilde{V}_{h+1}|\lesssim\sqrt{\mathrm{Var}_{\widetilde{P}}(\widetilde{V}_{h+1})/\widetilde{n}_{s_h,a_h}}+SHE_\rho/\widetilde{n}_{s_h,a_h}\). Together with our definition of private pessimism and the key lemma: extended value difference (Lemma 33 and 34), we can bound the suboptimality of our output policy \(\widehat{\pi}\) by: \[\label{eqn:tabularsketch} v^\star-v^{\widehat{\pi}}\lesssim \sum_{h=1}^H\sum_{(s_h,a_h)\in\mathcal{C}_h}d^{\pi^\star}_h(s_h,a_h)\sqrt{\frac{\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(\widetilde{V}_{h+1}(\cdot))}{\widetilde{n}_{s_h,a_h}}}+SHE_\rho/\widetilde{n}_{s_h,a_h}.\tag{4}\]

Finally, we further bound the above suboptimality via replacing private statistics by non-private ones. Specifically, we replace \(\widetilde{n}\) by \(n\), \(\widetilde{P}\) by \(P\) and \(\widetilde{V}\) by \(V^\star\). Due to 4 , we have \(\|\widetilde{V}-V^\star\|_\infty\lesssim \sqrt{\frac{1}{n\bar{d}_m}}\). Together with the upper bounds of \(\|\widetilde{P}-\widehat{P}\|_1\) and \(|\sqrt{\mathrm{Var}_{\widetilde{P}}(V)}-\sqrt{\mathrm{Var}_{\widehat{P}}(V)}|\), we have \[\label{eqn:1111} \begin{align} &\sqrt{\frac{\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(\widetilde{V}_{h+1}(\cdot))}{\widetilde{n}_{s_h,a_h}}}\lesssim \sqrt{\frac{\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(V^\star_{h+1}(\cdot))}{\widetilde{n}_{s_h,a_h}}}+\frac{1}{n\bar{d}_m}\\\lesssim& \sqrt{\frac{\mathrm{Var}_{\widehat{P}_h(\cdot|s_h,a_h)}(V^\star_{h+1}(\cdot))}{\widetilde{n}_{s_h,a_h}}}+\frac{1}{n\bar{d}_m}\lesssim\sqrt{\frac{\mathrm{Var}_{P_h(\cdot|s_h,a_h)}(V^\star_{h+1}(\cdot))}{\widetilde{n}_{s_h,a_h}}}+\frac{1}{n\bar{d}_m}\\\lesssim&\sqrt{\frac{\mathrm{Var}_{P_h(\cdot|s_h,a_h)}(V^\star_{h+1}(\cdot))}{nd^\mu_h(s_h,a_h)}}+\frac{1}{n\bar{d}_m}. \end{align}\tag{5}\]

The final bound using non-private statistics results from 4 and 5 .

10.2 Proof of the privacy guarantee↩︎

The privacy guarantee of DP-APVI (Algorithm 1) is summarized by Lemma 2 below.

10.3 Proof of the sub-optimality bound↩︎

10.3.1 Utility analysis↩︎

First of all, the following Lemma 3 gives a high probability bound for \(|n^{\prime}-n|\).

According to the utility analysis above, we have the following Lemma 4 giving a high probability bound for \(|\widetilde{n}-n|\).

Let the non-private empirical estimate be: \[\label{eqn:np95est} \widehat{P}_h(s^{\prime}|s_h,a_h)=\frac{n_{s_h,a_h,s^{\prime}}}{n_{s_h,a_h}},\tag{6}\] if \(n_{s_h,a_h}>0\) and \(\widehat{P}_h(s'|s_h,a_h)=\frac{1}{S}\) otherwise. We will show that the private transition kernel \(\widetilde{P}\) is close to \(\widehat{P}\) by the Lemma 5 and Lemma 6 below.

10.3.2 Validity of our pessimistic penalty↩︎

Now we are ready to present the key lemma (Lemma 7) below to justify our use of \(\Gamma\) as the pessimistic penalty.

Note that the previous Lemmas rely on the condition that \(\widetilde{n}\) is not very small (\(\widetilde{n}_{s_h,a_h}\geq 3E_\rho\)). Below we state the Multiplicative Chernoff bound (Lemma 8 and Remark 7) to show that under our condition in Theorem 5, for \((s_h,a_h)\in\mathcal{C}_h\), \(\widetilde{n}_{s_h,a_h}\) will be larger than \(3E_\rho\) with high probability.

Next we prove the asymmetric bound for \(\xi_h\), which is the key to the proof.

10.3.3 Reduction to augmented absorbing MDP↩︎

Before we prove the theorem, we need to construct an augmented absorbing MDP to bridge \(\widetilde{V}\) and \(V^\star\). According to Line 5 in Algorithm 1, the locations with \(\widetilde{n}_{s_h,a_h}\leq E_\rho\) is heavily penalized with penalty of order \(\widetilde{O}(H)\). Therefore we can prove that under the high probability event in Remark 7, \(d_h^{\widehat{\pi}}(s_h,a_h)>0\) only if \(d_h^{\mu}(s_h,a_h)>0\) by induction, where \(\widehat{\pi}\) is the output of Algorithm 1. The conclusion holds for \(h=1\). Assume it holds for some \(h>1\) that \(d_h^{\widehat{\pi}}(s_h,a_h)>0\) only if \(d_h^{\mu}(s_h,a_h)>0\), then for any \(s_{h+1}\in\mathcal{S}\) such that \(d_{h+1}^{\widehat{\pi}}(s_{h+1})>0\), it holds that \(d_{h+1}^{\mu}(s_{h+1})>0\), which leads to the conclusion that \(d_{h+1}^{\widehat{\pi}}(s_{h+1},a_{h+1})>0\) only if \(d_{h+1}^{\mu}(s_{h+1},a_{h+1})>0\). To summarize, we have \[\label{eqn:two95coverage} d_{h}^{\pi_0}(s_h,a_h)>0\,\,\text{only if}\,\,d_{h}^{\mu}(s_h,a_h)>0,\,\,\pi_0\in\{\pi^\star,\widehat{\pi}\}.\tag{7}\]

Let us define \(M^\dagger\) by adding one absorbing state \(s_h^\dagger\) for all \(h\in\{2,\ldots,H\}\), therefore the augmented state space \(\mathcal{S}^\dagger=\mathcal{S}\cup\{s^\dagger_h\}\) and the transition and reward is defined as follows: (recall \(\mathcal{C}_h:=\{(s_h,a_h):d^\mu_h(s_h,a_h)>0\}\)) \[P^{\dagger}_h(\cdot \mid s_h, a_h)=\left\{\begin{array}{ll} P_h(\cdot \mid s_h, a_h) & s_h, a_h \in \mathcal{C}_h, \\ \delta_{s^{\dagger}_{h+1}} & s_h=s_h^{\dagger} \text{ or } s_h, a_h \notin \mathcal{C}_h, \end{array} \;\; r^{\dagger}_h( s_h, a_h)=\left\{\begin{array}{ll} r_h(s_h, a_h) & s_h, a_h \in \mathcal{C}_h\\ 0 & s_h=s^{\dagger}_{h} \text{ or } s_h, a_h \notin \mathcal{C}_h \end{array}\right.\right.\] and we further define for any \(\pi\), \[\label{eqn:value95pMDP} V^{\dagger \pi}_h(s)=\mathbb{E}^\dagger_\pi\left[\sum_{t=h}^H r_t^\dagger\middle| s_h=s\right], v^{\dagger\pi}=\mathbb{E}^\dagger_\pi\left[\sum_{t=1}^H r_t^\dagger\right]\;\forall h\in[H],\tag{8}\] where \(\mathbb{E}^\dagger\) means taking expectation under the absorbing MDP \(M^{\dagger}\).

Note that because \(\pi^\star\) and \(\widehat{\pi}\) are fully covered by \(\mu\) 7 , it holds that \[\label{eqn:dagger95to95none} v^{\dagger\pi^\star}=v^{\pi^\star},\,\,v^{\dagger\widehat{\pi}}=v^{\widehat{\pi}}.\tag{9}\]

Define \((\mathcal{T}^\dagger_{h} V)(\cdot,\cdot):=r_h^\dagger(\cdot,\cdot)+(P_h^\dagger V)(\cdot,\cdot)\) for any \(V\in\mathbb{R}^{S+1}\). Note \(\widehat{\pi}\), \(\overline{Q}_h\), \(\widetilde{V}_h\) are defined in Algorithm 1 (we extend the definition by letting \(\widetilde{V}_h(s^\dagger_h)=0\) and \(\overline{Q}_h(s_h^\dagger,\cdot)=0\)) and denote \(\xi^\dagger_h(s,a)=(\mathcal{T}^\dagger_h\widetilde{V}_{h+1})(s,a)-\overline{Q}_h(s,a)\). Using identical proof to Lemma 9, we have \[\label{eqn:sub95decomp2} V_1^{\dagger\pi^\star}(s)-V_1^{\dagger\widehat{\pi}}(s)\leq \sum_{h=1}^H\mathbb{E}^\dagger_{\pi^\star}\left[\xi^\dagger_h(s_h,a_h)\mid s_1=s\right]-\sum_{h=1}^H\mathbb{E}^\dagger_{\widehat{\pi}}\left[\xi^\dagger_h(s_h,a_h)\mid s_1=s\right],\tag{10}\] where \(V_1^{\dagger\pi}\) is defined in 8 . Furthermore, 10 holds for all \(V_h^{\dagger\pi^\star}(s)-V_h^{\dagger\widehat{\pi}}(s)\).

10.3.4 Finalize our result with non-private statistics↩︎

For those \((s_h,a_h)\in\mathcal{C}_h\), \(\xi^\dagger_h(s_h,a_h)=r_h(s_h,a_h)+P_h\widetilde{V}_{h+1}(s_h,a_h)-\overline{Q}_h(s_h,a_h)=\xi_h(s_h,a_h)\). For those \((s_h,a_h)\notin\mathcal{C}_h\) or \(s_h=s_h^\dagger\), we have \(\xi^\dagger_h(s_h,a_h)=0\).

Therefore, by 10 and Lemma 10, under the high probability events in Lemma 4, Lemma 7 and Lemma 8, we have for all \(t\in[H]\), \(s\in\mathcal{S}\) (\(\mathcal{S}\) does not include the absorbing state \(s_t^\dagger\)), \[\label{eqn:expression95bound} \begin{align} &V_t^{\dagger\pi^\star}(s)-V_t^{\dagger\widehat{\pi}}(s)\leq \sum_{h=t}^H\mathbb{E}^\dagger_{\pi^\star}\left[\xi^\dagger_h(s_h,a_h)\mid s_t=s\right]-\sum_{h=t}^H\mathbb{E}^\dagger_{\widehat{\pi}}\left[\xi^\dagger_h(s_h,a_h)\mid s_t=s\right]\\ \leq&\sum_{h=t}^H\mathbb{E}^\dagger_{\pi^\star}\left[\xi^\dagger_h(s_h,a_h)\mid s_t=s\right]-0\\ \leq&\sum_{h=t}^H\mathbb{E}^\dagger_{\pi^\star}\left[2\sqrt{\frac{2\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(\widetilde{V}_{h+1}(\cdot))\cdot\iota}{\widetilde{n}_{s_h,a_h}-E_\rho}}+\frac{32 SHE_\rho\cdot\iota}{\widetilde{n}_{s_h,a_h}}\mid s_t=s\right]\cdot\mathbb{1}\left((s_h,a_h)\in\mathcal{C}_h\right)\\ \leq&\sum_{h=t}^H\mathbb{E}^\dagger_{\pi^\star}\left[2\sqrt{\frac{2\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(\widetilde{V}_{h+1}(\cdot))\cdot\iota}{n_{s_h,a_h}-2E_\rho}}+\frac{32 SHE_\rho\cdot\iota}{n_{s_h,a_h}-E_\rho}\mid s_t=s\right]\cdot\mathbb{1}\left((s_h,a_h)\in\mathcal{C}_h\right)\\ \leq&\sum_{h=t}^H\mathbb{E}^\dagger_{\pi^\star}\left[4\sqrt{\frac{\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(\widetilde{V}_{h+1}(\cdot))\cdot\iota}{n_{s_h,a_h}}}+\frac{128 SHE_\rho\cdot\iota}{3n_{s_h,a_h}}\mid s_t=s\right]\cdot\mathbb{1}\left((s_h,a_h)\in\mathcal{C}_h\right)\\ \leq&\sum_{h=t}^H\mathbb{E}^\dagger_{\pi^\star}\left[4\sqrt{\frac{2\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(\widetilde{V}_{h+1}(\cdot))\cdot\iota}{nd^\mu_h(s_h,a_h)}}+\frac{256 SHE_\rho\cdot\iota}{3nd^\mu_h(s_h,a_h)}\mid s_t=s\right]\cdot\mathbb{1}\left((s_h,a_h)\in\mathcal{C}_h\right)\\ \end{align}\tag{11}\]

The second and third inequality are because of Lemma 10, Remark 7 and the the fact that either \(\xi^\dagger=0\) or \(\xi^\dagger=\xi\) while \((s_h,a_h)\in\mathcal{C}_h\). The forth inequality is due to Lemma 4. The fifth inequality is because of Remark 7. The last inequality is by Lemma 8.

Below we present a crude bound of \(\left|V_t^{\dagger\pi^\star}(s)-\widetilde{V}_t(s)\right|\), which can be further used to bound the main term in the main result.

Now we are ready to bound \(\sqrt{\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(\widetilde{V}_{h+1}(\cdot))}\) by \(\sqrt{\mathrm{Var}_{P_h(\cdot|s_h,a_h)}(V^{\dagger\star}_{h+1}(\cdot))}\). Under the high probability events in Lemma 4, Lemma 7 and Lemma 8, with probability \(1-\delta\), it holds that for all \((s_h,a_h)\in\mathcal{C}_h\), \[\label{eqn:var95bound} \begin{align} &\sqrt{\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(\widetilde{V}_{h+1}(\cdot))}\leq\sqrt{\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(V^{\dagger\star}_{h+1}(\cdot))}+\left\lVert\widetilde{V}_{h+1}-{V}^{\dagger\pi^\star}_{h+1}\right\rVert_{\infty,s\in\mathcal{S}}\\\leq&\sqrt{\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(V^{\dagger\star}_{h+1}(\cdot))}+\frac{4\sqrt{2\iota}H^2}{\sqrt{n\cdot\bar{d}_m}} +\frac{256SH^2E_\rho\cdot \iota}{3n\cdot \bar{d}_m}\\\leq& \sqrt{\mathrm{Var}_{\widehat{P}_h(\cdot|s_h,a_h)}(V^{\dagger\star}_{h+1}(\cdot))}+\frac{4\sqrt{2\iota}H^2}{\sqrt{n\cdot\bar{d}_m}} +\frac{256SH^2E_\rho\cdot \iota}{3n\cdot \bar{d}_m}+4H\sqrt{\frac{SE_\rho}{\widetilde{n}_{s_h,a_h}}}\\\leq& \sqrt{\mathrm{Var}_{\widehat{P}_h(\cdot|s_h,a_h)}(V^{\dagger\star}_{h+1}(\cdot))}+\frac{4\sqrt{2\iota}H^2}{\sqrt{n\cdot\bar{d}_m}} +\frac{256SH^2E_\rho\cdot \iota}{3n\cdot \bar{d}_m}+8H\sqrt{\frac{SE_\rho}{n\cdot\bar{d}_m}}\\\leq& \sqrt{\mathrm{Var}_{P_h(\cdot|s_h,a_h)}(V^{\dagger\star}_{h+1}(\cdot))}+\frac{4\sqrt{2\iota}H^2}{\sqrt{n\cdot\bar{d}_m}} +\frac{256SH^2E_\rho\cdot \iota}{3n\cdot \bar{d}_m}+8H\sqrt{\frac{SE_\rho}{n\cdot\bar{d}_m}}+3H\sqrt{\frac{\iota}{n\cdot\bar{d}_m}}\\\leq& \sqrt{\mathrm{Var}_{P_h(\cdot|s_h,a_h)}(V^{\dagger\star}_{h+1}(\cdot))}+\frac{9\sqrt{\iota}H^2}{\sqrt{n\cdot\bar{d}_m}} +\frac{256SH^2E_\rho\cdot \iota}{3n\cdot \bar{d}_m}+8H\sqrt{\frac{SE_\rho}{n\cdot\bar{d}_m}}. \end{align}\tag{15}\] The second inequality is because of Lemma 11. The third inequality is due to Lemma 6. The forth inequality comes from Lemma 4 and Remark 7. The fifth inequality holds with probability \(1-\delta\) because of Lemma 31 and a union bound.

Finally, by plugging 15 into 11 and averaging over \(s_1\), we finally have with probability \(1-4\delta\), \[\label{eqn:final95result} \begin{align} &v^{\pi^\star}-v^{\widehat{\pi}}=v^{\dagger\pi^\star}-v^{\dagger\widehat{\pi}}\leq \sum_{h=1}^H\mathbb{E}^\dagger_{\pi^\star}\left[4\sqrt{\frac{2\mathrm{Var}_{\widetilde{P}_h(\cdot|s_h,a_h)}(\widetilde{V}_{h+1}(\cdot))\cdot\iota}{nd^\mu_h(s_h,a_h)}}+\frac{256 SHE_\rho\cdot\iota}{3nd^\mu_h(s_h,a_h)}\right]\\ \leq& 4\sqrt{2}\sum_{h=1}^H\mathbb{E}^\dagger_{\pi^\star}\left[\sqrt{\frac{\mathrm{Var}_{P_h(\cdot|s_h,a_h)}(V^{\dagger\star}_{h+1}(\cdot))\cdot\iota}{nd^\mu_h(s_h,a_h)}}\right]+\widetilde{O}\left(\frac{H^3+SH^2E_\rho}{n\cdot\bar{d}_m}\right)\\ =&4\sqrt{2}\sum_{h=1}^H\sum_{(s_h,a_h)\in\mathcal{C}_h}d^{\pi^\star}_h(s_h,a_h)\sqrt{\frac{\mathrm{Var}_{P_h(\cdot|s_h,a_h)}(V^{\dagger\star}_{h+1}(\cdot))\cdot\iota}{nd^\mu_h(s_h,a_h)}}+\widetilde{O}\left(\frac{H^3+SH^2E_\rho}{n\cdot\bar{d}_m}\right)\\ =&4\sqrt{2}\sum_{h=1}^H\sum_{(s_h,a_h)\in\mathcal{C}_h}d^{\pi^\star}_h(s_h,a_h)\sqrt{\frac{\mathrm{Var}_{P_h(\cdot|s_h,a_h)}(V^\star_{h+1}(\cdot))\cdot\iota}{nd^\mu_h(s_h,a_h)}}+\widetilde{O}\left(\frac{H^3+SH^2E_\rho}{n\cdot\bar{d}_m}\right),\\ \end{align}\tag{16}\] where \(\widetilde{O}\) absorbs constants and Polylog terms. The first equation is due to 9 . The first inequality is because of 11 . The second inequality comes from 15 and our assumption that \(n\cdot\bar{d}_m\geq c_1 H^2\). The second equation uses the fact that \(d^{\pi^\star}_h(s_h,a_h)=d^{\dagger\pi^\star}_h(s_h,a_h)\), for all \((s_h,a_h)\). The last equation is because for any \((s_h,a_h,s_{h+1})\) such that \(d^{\pi^\star}_h(s_h,a_h)>0\) and \(P_h(s_{h+1}|s_h,a_h)>0\), \(V^{\dagger\star}_{h+1}(s_{h+1})=V^{\star}_{h+1}(s_{h+1})\).

10.4 Put everything together↩︎

Combining Lemma 2 and 16 , the proof of Theorem 5 is complete.

11 Proof of Theorem 6↩︎

11.1 Proof sketch↩︎

Since the whole proof for privacy guarantee is not very complex, we present it in Section 11.2 below and only sketch the proof for suboptimality bound.

First of all, by extended value difference (Lemma 33 and 34), we can convert bounding the suboptimality gap of \(v^\star-v^{\widehat{\pi}}\) to bounding \(\sum_{h=1}^H \mathbb{E}_\pi\left[\Gamma_h(s_h,a_h)\right]\), given that \(|(\mathcal{T}_h\widetilde{V}_{h+1}-\widetilde{\mathcal{T}}_h\widetilde{V}_{h+1})(s,a)|\leq \Gamma_h(s,a)\) for all \(s,a,h\). To bound \((\mathcal{T}_h\widetilde{V}_{h+1}-\widetilde{\mathcal{T}}_h\widetilde{V}_{h+1})(s,a)\), according to our analysis about the upper bound of the noises we add, we can decompose \((\mathcal{T}_h\widetilde{V}_{h+1}-\widetilde{\mathcal{T}}_h\widetilde{V}_{h+1})(s,a)\) to lower order terms (\(\widetilde{O}(\frac{1}{K})\)) and the following key quantity:

\[\phi(s, a)^{\top} \widehat{\Lambda}_{h}^{-1}\left[\sum_{\tau=1}^{K} \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right) \cdot\left(r_{h}^{\tau}+\widetilde{V}_{h+1}\left(s_{h+1}^{\tau}\right)-\left(\mathcal{T}_{h} \widetilde{V}_{h+1}\right)\left(s_{h}^{\tau}, a_{h}^{\tau}\right)\right)/\widetilde{\sigma}^2_h(s^\tau_h,a^\tau_h)\right].\]

For the term above, we prove an upper bound of \(\left\lVert\sigma^2_{\widetilde{V}_{h+1}}-\widetilde{\sigma}_h^2\right\rVert_\infty\), so we can convert \(\widetilde{\sigma}_h^2\) to \(\sigma^2_{\widetilde{V}_{h+1}}\). Next, since \(\mathrm{Var}\left[r_{h}^{\tau}+\widetilde{V}_{h+1}\left(s_{h+1}^{\tau}\right)-\left(\mathcal{T}_{h} \widetilde{V}_{h+1}\right)\left(s_{h}^{\tau}, a_{h}^{\tau}\right)\mid s^\tau_h,a^\tau_h\right]\approx \sigma^2_{\widetilde{V}_{h+1}}\), we can apply Bernstein’s inequality for self-normalized martingale (Lemma 36) as in [13] for deriving tighter bound.

Finally, we replace the private statistics by non-private ones. More specifically, we convert \(\sigma^2_{\widetilde{V}_{h+1}}\) to \(\sigma_h^{\star2}\) (\(\Lambda_h^{-1}\) to \(\Lambda_h^{\star-1}\)) by combining the crude upper bound of \(\left\lVert\widetilde{V}-V^\star\right\rVert_\infty\) and matrix concentrations.

11.2 Proof of the privacy guarantee↩︎

The privacy guarantee of DP-VAPVI (Algorithm 2) is summarized by Lemma 12 below.

11.3 Proof of the sub-optimality bound↩︎

11.3.1 Utility analysis and some preparation↩︎

We begin with the following high probability bound of the noises we add.

Define the Bellman update error \(\zeta_h(s,a):=(\mathcal{T}_h\widetilde{V}_{h+1})(s,a)-\widehat{Q}_h(s,a)\) and recall
\(\widehat{\pi}_h(s)=\mathrm{argmax}_{\pi_h}\langle\widehat{Q}_{h}(s, \cdot), \pi_{h}(\cdot \mid s)\rangle_{\mathcal{A}}\), then because of Lemma 34, \[\label{eqn:diff} V_1^{\pi}(s)-V_1^{\widehat{\pi}}(s)\leq \sum_{h=1}^H\mathbb{E}_{\pi}\left[\zeta_h(s_h,a_h)\mid s_1=s\right]-\sum_{h=1}^H\mathbb{E}_{\widehat{\pi}}\left[\zeta_h(s_h,a_h)\mid s_1=s\right].\tag{17}\]

Define \(\widetilde{\mathcal{T}}_h\widetilde{V}_{h+1}(\cdot,\cdot)=\phi(\cdot,\cdot)^{\top}\widetilde{w}_h\). Then similar to Lemma 10, we have the following lemma showing that in order to bound the sub-optimality, it is sufficient to bound the pessimistic penalty.

11.3.2 Bound the pessimistic penalty↩︎

By Lemma 14, it remains to bound \(|(\mathcal{T}_{h} \widetilde{V}_{h+1})(s, a)-(\widetilde{\mathcal{T}}_{h}\widetilde{V}_{h+1})(s, a)|\). Suppose \(w_h\) is the coefficient corresponding to the \(\mathcal{T}_{h} \widetilde{V}_{h+1}\) (such \(w_h\) exists by Lemma 40), i.e. \(\mathcal{T}_{h} \widetilde{V}_{h+1}=\phi^\top w_h\), and recall \((\widetilde{\mathcal{T}}_{h} \widetilde{V}_{h+1})(s, a)=\phi(s, a)^{\top}\widetilde{w}_{h}\), then: \[\label{eqn:decompose} \begin{align} &\left(\mathcal{T}_{h} \widetilde{V}_{h+1}\right)(s, a)-\left(\widetilde{\mathcal{T}}_{h} \widetilde{V}_{h+1}\right)(s, a)=\phi(s, a)^{\top}\left(w_{h}-\widetilde{w}_{h}\right) \\ =&\phi(s, a)^{\top} w_{h}-\phi(s, a)^{\top} \widetilde{\Lambda}_{h}^{-1}\left(\sum_{\tau=1}^{K} \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right) \cdot\left(r_{h}^{\tau}+\widetilde{V}_{h+1}\left(s_{h+1}^{\tau}\right)\right)/\widetilde{\sigma}^2_h(s^\tau_h,a^\tau_h)+\phi_3\right) \\ =&\underbrace{\phi(s, a)^{\top} w_{h}-\phi(s, a)^{\top} \widehat{\Lambda}_{h}^{-1}\left(\sum_{\tau=1}^{K} \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right) \cdot\left(r_{h}^{\tau}+\widetilde{V}_{h+1}\left(s_{h+1}^{\tau}\right)\right)/\widetilde{\sigma}^2_h(s^\tau_h,a^\tau_h)\right)}_{(\mathrm{i})}\\&-\underbrace{\phi(s,a)^{\top}\widehat{\Lambda}_h^{-1}\phi_3}_{(\mathrm{ii})}+\underbrace{\phi(s, a)^{\top} (\widehat{\Lambda}_{h}^{-1}-\widetilde{\Lambda}_{h}^{-1})\left(\sum_{\tau=1}^{K} \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right) \cdot\left(r_{h}^{\tau}+\widetilde{V}_{h+1}\left(s_{h+1}^{\tau}\right)\right)/\widetilde{\sigma}^2_h(s^\tau_h,a^\tau_h)+\phi_3\right)}_{(\mathrm{iii})}, \end{align}\tag{18}\] where \(\widehat{\Lambda}_h=\widetilde{\Lambda}_{h}-K_2 =\sum_{\tau=1}^{K} \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right) \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right)^{\top}/\widetilde{\sigma}_h^2(s^\tau_h,a^\tau_h)+\lambda I\).

Term (ii) can be handled by the following Lemma 15

The difference between \(\widetilde{\Lambda}_h^{-1}\) and \(\widehat{\Lambda}_h^{-1}\) can be bounded by the following Lemma 16

Then we can bound term (iii) by the following Lemma 17

Now the remaining part is term (i), we have \[\label{eqn:decompose2} \begin{align} &\underbrace{\phi(s, a)^{\top} w_{h}-\phi(s, a)^{\top} \widehat{\Lambda}_{h}^{-1}\left(\sum_{\tau=1}^{K} \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right) \cdot\left(r_{h}^{\tau}+\widetilde{V}_{h+1}\left(s_{h+1}^{\tau}\right)\right)/\widetilde{\sigma}^2_h(s^\tau_h,a^\tau_h)\right)}_{(\mathrm{i})} \\ =&\underbrace{\phi(s, a)^{\top} w_{h}-\phi(s, a)^{\top} \widehat{\Lambda}_{h}^{-1}\left(\sum_{\tau=1}^{K} \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right) \cdot\left(\mathcal{T}_{h} \widetilde{V}_{h+1}\right)\left(s_{h}^{\tau}, a_{h}^{\tau}\right)/\widetilde{\sigma}^2_h(s^\tau_h,a^\tau_h)\right)}_{(\mathrm{iv})}\\ &-\underbrace{\phi(s, a)^{\top} \widehat{\Lambda}_{h}^{-1}\left(\sum_{\tau=1}^{K} \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right) \cdot\left(r_{h}^{\tau}+\widetilde{V}_{h+1}\left(s_{h+1}^{\tau}\right)-\left(\mathcal{T}_{h} \widetilde{V}_{h+1}\right)\left(s_{h}^{\tau}, a_{h}^{\tau}\right)\right)/\widetilde{\sigma}^2_h(s^\tau_h,a^\tau_h)\right)}_{(\mathrm{v})} . \end{align}\tag{20}\]

We are able to bound term (iv) by the following Lemma 18.

For term (v), denote: \(x_\tau=\frac{\phi(s_h^\tau,a_h^\tau)}{\widetilde{\sigma}_h(s_h^\tau,a_h^\tau)},\quad \eta_\tau=\left(r_{h}^{\tau}+\widetilde{V}_{h+1}\left(s_{h+1}^{\tau}\right)-\left(\mathcal{T}_{h} \widetilde{V}_{h+1}\right)\left(s_{h}^{\tau}, a_{h}^{\tau}\right)\right)/\widetilde{\sigma}_h(s^\tau_h,a^\tau_h)\), then by Cauchy-Schwarz inequality, it holds that for all \(h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}\), \[\label{eqn:termv} \begin{align} &\left|\phi(s, a)^{\top} \widehat{\Lambda}_{h}^{-1}\left(\sum_{\tau=1}^{K} \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right) \cdot\left(r_{h}^{\tau}+\widetilde{V}_{h+1}\left(s_{h+1}^{\tau}\right)-\left(\mathcal{T}_{h} \widetilde{V}_{h+1}\right)\left(s_{h}^{\tau}, a_{h}^{\tau}\right)\right)/\widetilde{\sigma}^2_h(s^\tau_h,a^\tau_h)\right)\right|\\ \leq&\sqrt{\phi(s,a)^\top\widehat{\Lambda}_h^{-1}\phi(s,a)}\cdot\left\lVert \sum_{\tau=1}^K x_\tau \eta_\tau\right\rVert_{\widehat{\Lambda}_h^{-1}}. \end{align}\tag{21}\]

We bound \(\sqrt{\phi(s,a)^\top\widehat{\Lambda}_h^{-1}\phi(s,a)}\) by \(\sqrt{\phi(s,a)^\top\widetilde{\Lambda}_h^{-1}\phi(s,a)}\) using the following Lemma 19.

11.3.3 An intermediate result: bounding the variance↩︎

Before we handle \(\left\lVert\sum_{\tau=1}^K x_\tau \eta_\tau\right\rVert_{\widehat{\Lambda}_h^{-1}}\), we first bound \(\sup_h\left\lVert\widetilde{\sigma}_h^2-\sigma_{\widetilde{V}_{h+1}}^2\right\rVert_\infty\) by the following Lemma 20.

11.3.4 Validity of our pessimism↩︎

Recall the definition \(\widehat{\Lambda}_{h} =\sum_{\tau=1}^{K} \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right) \phi\left(s_{h}^{\tau}, a_{h}^{\tau}\right)^{\top}/\widetilde{\sigma}_h^2(s^\tau_h,a^\tau_h)+\lambda \cdot I\) and
\({\Lambda}_h=\sum_{\tau=1}^K \phi(s^\tau_h,a^\tau_h) \phi(s^\tau_h,a^\tau_h)^\top/\sigma_{\widetilde{V}_{h+1}}^2(s^\tau_h,a^\tau_h) +\lambda I\). Then we have the following lemma to bound the term \(\sqrt{\phi(s,a)^\top\widehat{\Lambda}_h^{-1}\phi(s,a)}\) by \(\sqrt{\phi(s,a)^\top\Lambda_h^{-1}\phi(s,a)}\).

In order to bound \(\left\lVert\sum_{\tau=1}^K x_\tau \eta_\tau\right\rVert_{\widehat{\Lambda}_h^{-1}}\), we apply the following Lemma 22.

Now we are ready to prove the following key lemma, which gives a high probability bound for \(\left|(\mathcal{T}_h\widetilde{V}_{h+1}-\widetilde{\mathcal{T}}_h\widetilde{V}_{h+1})(s,a)\right|\).

11.3.5 Finalize the proof of the first part↩︎

We are ready to prove the first part of Theorem 6.

11.3.6 Finalize the proof of the second part↩︎

To prove the second part of Theorem 6, we begin with a crude bound on \(\sup_h\left\lVert V^\star_h-\widetilde{V}_h\right\rVert_\infty\).

Then we can give a high probability bound of \(\sup_h\lvert\lvert \sigma^{2}_{\widetilde{V}_{h+1}}-\sigma^{\star 2}_{h}\rvert\rvert_\infty\).

We transfer \(\sqrt{\phi(s,a)^\top{\Lambda}_h^{-1}\phi(s,a)}\) to \(\sqrt{\phi(s,a)^\top {\Lambda}_h^{\star-1}\phi(s,a)}\) by the following Lemma 26.

Finally, the second part of Theorem 6 can be proven by combining Theorem 10 (with \(\pi=\pi^\star\)) and Lemma 26.

11.4 Put everything toghther↩︎

Combining Lemma 12, Theorem 10, and the discussion above, the proof of Theorem 6 is complete.

12 Assisting technical lemmas↩︎

12.1 Extended Value Difference↩︎

12.2 Assisting lemmas for linear MDP setting↩︎

12.3 Assisting lemmas for differential privacy↩︎

13 Details for the Evaluation part↩︎

In the Evaluation part, we apply a synthetic linear MDP case that is similar to [13], [31] but with some modifications for our evaluation task. The linear MDP example we use consists of \(|\mathcal{S}|=2\) states and \(|\mathcal{A}|=100\) actions, while the feature dimension \(d=10\). We denote \(\mathcal{S}=\{0,1\}\) and \(\mathcal{A}=\{0,1,\ldots,99\}\) respectively. For each action \(a\in\{0,1,\ldots,99\}\), we obtain a vector \(\mathbf{a}\in\mathbb{R}^8\) via binary encoding. More specifically, each coordinate of \(\mathbf{a}\) is either \(0\) or \(1\).
First, we define the following indicator function \(\delta(s, a)= \begin{cases}1 & \text{ if } \mathbb{1}\{s=0\}=\mathbb{1}\{a=0\} \\ 0 & \text{ otherwise }\end{cases},\) then our non-stationary linear MDP example can be characterized by the following parameters.
The feature map \(\boldsymbol{\phi}\) is: \[\boldsymbol{\phi}(s, a)=\left(\mathbf{a}^{\top}, \delta(s, a), 1-\delta(s, a)\right)^{\top} \in \mathbb{R}^{10}.\] The unknown measure \(\nu_h\) is: \[\boldsymbol{\nu}_{h}(0)=\left(0, \cdots, 0,\alpha_{h,1}, \alpha_{h,2}\right),\] \[\boldsymbol{\nu}_{h}(1)=\left(0, \cdots, 0,1-\alpha_{h,1}, 1-\alpha_{h,2}\right),\] where \(\{\alpha_{h,1},\alpha_{h,2}\}_{h\in[H]}\) is a sequence of random values sampled uniformly from \([0,1]\).
The unknown vector \(\theta_h\) is: \[\theta_h= (r_h/8,0,r_h/8,1/2-r_h/2,r_h/8,0,r_h/8,0,r_h/2,1/2-r_h/2)\in\mathbb{R}^{10},\] where \(r_h\) is also sampled uniformly from \([0,1]\). Therefore, the transition kernel follows \(P_h(s'|s,a)=\langle \phi(s,a),\boldsymbol{\nu}_h(s')\rangle\) and the expected reward function \(r_h(s,a)=\langle \phi(s,a), \theta_h \rangle\).
Finally, the behavior policy is to always choose action \(a=0\) with probability \(p\), and other actions uniformly with probability \((1-p)/99\). Here we choose \(p=0.6\). The initial distribution is a uniform distribution over \(\mathcal{S}=\{0,1\}\).

References↩︎

---

1. The environment is usually characterized by a Markov Decision Process (MDP) in this paper.↩︎

2. Here we only compare our techniques (for offline RL) with the works for online RL under joint DP guarantee, as both settings allow access to the raw data.↩︎

3. This is due to the fact that the uncertainty of reward function is dominated by that of transition kernel in RL.↩︎

4. For clarity we use \(n\) for tabular MDP and \(K\) for linear MDP when referring to the sample complexity.↩︎

5. This conclusion is summarized in Lemma 4.↩︎

6. The non-private empirical estimate, defined as 6 in Appendix 10.↩︎

7. Here we apply the second part of Lemma 1 to achieve \((\epsilon,\delta)\)-DP, the notation \(\widetilde{O}\) also absorbs \(\log\frac{1}{\delta}\) (only here \(\delta\) denotes the privacy budget instead of failure probability).↩︎

8. We need to add noise to each of the \(5H\) counts, therefore for \(\phi_1\), we actually sample \(H\) i.i.d samples \(\phi_{1,h}\), \(h=1,\cdots,H\) from the distribution of \(\phi_1\). Then we add \(\phi_{1,h}\) to \(\sum_{\tau=1}^K\phi(\bar{s}_h^\tau,\bar{a}_h^\tau)\cdot \widetilde{V}_{h+1}(\bar{s}_{h+1}^\tau)^2\), \(\forall\,h\in[H]\). For simplicity, we use \(\phi_1\) to represent all the \(\phi_{1,h}\). The procedure applied to the other \(4H\) statistics are similar.↩︎

9. The \(\max\{1,\cdot\}\) operator here is for technical reason only: we want a lower bound for each variance estimate.↩︎

10. Here we apply the second part of Lemma 1 to achieve \((\epsilon,\delta)\)-DP, the notation \(\widetilde{O}\) also absorbs \(\log\frac{1}{\delta}\) (only here \(\delta\) denotes the privacy budget instead of failure probability).↩︎

11. We keep the state space \(\mathcal{S}=\{1,2\}\), action space \(\mathcal{A}=\{1,\cdots,100\}\) and feature map of state-action pairs while we choose stochastic transition (instead of the original deterministic transition) and more complex reward.↩︎

12. For more detailed explanation, we refer the readers to Appendix D of [59].↩︎

13. Note that the conclusion in [14] hold here even though we have an extra constant \(C_2\).↩︎

14. Note that here the assumption is stronger than the assumption in [13], therefore the conclusion of Lemma C.4 holds.↩︎