Offline Reinforcement Learning with Differential Privacy
Authors: Dan Qiao
Yu-Xiang Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential privacy
offline reinforcement learning
reinforcement learning theory
TL;DR: This paper presents the first provably efficient algorithms for offline RL with DP guarantee.

Abstract: The offline reinforcement learning (RL) problem is often motivated by the need to learn data-driven decision policies in financial, legal and healthcare applications.  However, the learned policy could retain sensitive information of individuals in the training data (e.g., treatment and outcome of patients), thus susceptible to various privacy risks. We design offline RL algorithms with differential privacy guarantees which provably prevent such risks. These algorithms also enjoy strong instance-dependent learning bounds under both tabular and linear Markov Decision Process (MDP) settings. Our theory and simulation suggest that the privacy guarantee comes at (almost) no drop in utility comparing to the non-private counterpart for a medium-size dataset.

Offline Reinforcement Learning with Differential Privacy
Dan Qiao
Yu-Xiang Wang Department of Computer Science
Department of Computer Science UC Santa Barbara
UC Santa Barbara
Santa Barbara, CA 93106 dangiao@ucsb.
Santa Barbara, CA 93106 yuxiangwecs ucsb edu
Abstract
The offline reinforcement learning (RL) problem is often motivated by the need to learn data-driven decision policies in financial, legal and healthcare applications. However, the learned policy could retain sensitive information of individuals in the training data (c.g., treatment and outcome of patients), thus susceptible to various privacy risks. We design offline RL algorithms with differential privacy guarantees which provably prevent such risks. These algorithms also enjoy strong instance- dependent learning bounds under both tabular and linear Markov Decision Process (MDP) settings. Our theory and simulation suggest that the privacy guarantee comes at (almost) no drop in utility comparing the non-private counterpart for a medium-size dataset.
1 Introduction
Offline Reinforcement Learning (or batch RL) aims to learn near-optimal policy in an unknown environment through static dataset gathered from some behavior policy μ.. Since offline RL does not require access the environment, it can be applied problems where interaction with environment is infeasible, e.g., when collecting new data is costly (trade or finance [Zhang et al., 2020J), risky (autonomous driving [Sallab al., 2017J) or illegal unethical (healthcare [Raghu et al., 2017]). In such practical applications, the data used by an RL agent usually contains sensitive information. Take medical history for instance, for each patient, 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 treatment outcome (whether the patient feels good, etc.) and the patient transitions to another health condition. Here, (health condition, treatment, treatment outcome) corresponds (state, action, reward) and the dataset can be considered as n (number of patients) trajectories sampled from MDP with horizon H (number of treatment steps). However, learning agents are known to implicitly memorize details of individual training data points verbatim [Carlini et al., 2019], even if they are irrelevant for learning [Brown et al., 2021], which makes offline RL models vulnerable to various privacy attacks.
Differential privacy (DP) [Dwork et al., 2006] is well-established definition of privacy with many desirable properties. A differentially private offline RL algorithm will return decision policy that is indistinguishable from policy trained in an alternative universe any individual user is replaced, thereby preventing the aforementioned privacy risks. There a surge of recent interest developing RL algorithms with DP guarantees, but they focus mostly on the online setting [Vietri et al., 2020, Garcelon al., 2021, Liao et al., 2021, Chowdhury and Zhou, 2021, Luyo et al., 2021].
'The environment is usually characterized by Markov Decision Process (MDP) in this paper.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

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 [Kim et al., 2017].
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 pussimism-based algorithms DP-APVI (Algorithm 1) and DP- -A-VI (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- OP-VAPVI (Algorithm 2) with its non- non-private counterpart VAPVI [Yin et al., 2022] as well as a popular baseline PEVI [Jin et al., 2021]. 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 single policy [Balle et al., 2016, Xie et al., 2019]. Balle et al. [2016] privatized first-visit Monte Maroe-Ridge Regression estimator by an output perturbation mechanism and Xie et al. [2019] 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 [Vietri et al., 2020, Chowdhury and Zhou, 2021, Ngo et al., 2022, Luyo et al., 202 I] or local differential privacy [Garcelon et al., 2021, Liao et al., 2021, Luyo et al., 2021, Chowdhury and Zhou, 2021]. 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 RI. 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 B.
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) [Yin and Wang. 2021b] and Variance-Awar Pessimistic Value Iteration (VAPVI, for linear MDPs) [Yin et al., 2022], as they give the strongest theoretical guarantees to date. We refer readers to Appendix 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 I) 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 [Zhou et al., 2021]). Our VAPVI releases conditional variance privately, and further applies weighted ridge regression privately. Both approaches ensure tighter instance- -eeendeed bounds on the suboptimality of the learned policy.
2 Problem Setup
Markov Decision Process. A finite-horizon Markov Decision Process (MDP) is denoted by tuple M = (S,A, P. r, H. d1) [Sutton and Barto, 2018], where S is state space and AA is action space. A non-stationary transition kernel PA S x A S + j0, 1] maps each state action (s), an)) a probabil- ity distribution Pa (-ls,, an) and Pn, can be different across time. Besides, Th S x A +> R is the ex- pected immediate reward satisfying S rh S 1, dj is the initial state distribution and H is the horizon.
Here we only compare our techniques (for offline RL) with the works for online RL under joint DP guarantee. both settings allow access the raw data.
2

---

A policy π (TI1... ... , TH) assigns each state S/ S probability distribution over actions accord- ing the map Sp. + n (+1s)), Ah E [H] random trajectory $1, 01. "..... ,.H asr. rH ---11 generated according 81 d1, Oh ~ n (+1s),, r' (a( 0h), 8h+1 (- as), V E [M]
For tabular MDP, have S x A is the discrete state-action space and S = |S], A |A| are finite. In this work, we assume that r is known'. In addition, we denote the per-step marginal state-action occupancy di, (s, a) as: (s, a) := P(sh s|si d1, ---TTATTee (a]ss,, which is the marginal state-action probability at time h.
Value function, Bellman (optimality) equations. The value function VØ (-) and Q-value func- tion (T.) for any policy æ is defined as: (s) = E relsn s]. (% a)
E., tt=h Ti Pr/88; = 8, 8, Vh, 8,a E [M] x S x A. The performance is defined as n" Edd [VT] = iT EE rt The Bellman (optimality) equations follow 4/ [H]: QR
Th PAVVED VIr = Ba-an 1Q1, === Th + Pr. Phtt+ VK = max, ()(+aa).
Linear MDP [Jin et al., 2020b]. An episodic MDP (S, H, P.r) is called linear MDP with known feature map o S A + IR if there exist H unknown signed measures vn E Rd over S and H unknown reward vectors On E Rd such that
Ps (s' s, a) a) (s')) Th (s, a) = (o(s,)), Y(h, s,,,s, E [ x
Without loss of generality, we assume ([0(s, a)ll S and (S) |10 I vd for all h,, 8,a E [H] x S x A. An important property of linear MDP is that the value functions are linear in the feature map, which is summarized Lemma 14.
Offline setting and the goal. The offline RL requires the agent to find a policy π in order to maximize the performance v", given only the episodic data D> = {(s,, oj rī, sh+1)) 1)) rolled out from some fixed and possibly unknown behavior policy jr, which means we cannot change μ and in particular we do not assume the functional knowledge of p. In conclusion, based on the batch data D and
targeted accuracy > 0, the agent seeks to find a policy Talg such that er - aate S e.
2.1 Assumptions offline RL
In order to show that our privacy-preserving algorithms can generate near optimal policy, certain coverage assumptions are needed. this section, we will list the assumptions we use in this paper.
Assumptions for tabular setting.
Assumption 2.1 ([Liu et al., 2019]). There exists one optimal policy such that x5 is fully covered by p. f.e. V Sh, aj E S x AA di," (sh, an) > 0 only if d% (s,, >> 0. Furthermore, we denote the trackable set as Cn. == {(82, an.) di (8h, ax)) > 0}.
Assumption 2.1 is the weakest assumption needed for accurately learning the optimal value v² by requiring y to trace the state-action space of one optimal policy (I can be agnostic at other locations). Similar to YYnn and Wang, 2021b), we will use Assumption 2. for the tabular part of this paper, which enables comparison between our sample complexity to the conclusion in [Yin and Wang, 2021b], whose algorithm serves as a non- non-private baseline.
Assumptions for linear setting. First, we define the expectation of covariance matrix under the behavior policy ze for all time step h E [M]] as below:
(I) As have been shown in [Wang et al., 2021a, Yin et al., 2022], learning a near-optimal policy from offline data requires coverage assumptions. Here in linear setting, such coverage characterized by the minimum eigenvalue of D/. Similar to [Yin et al., 2022], we apply the following assumption for the sake of comparison.
> = Ex, [o(s), an (s) an)
Assumption 2.2 (Feature Coverage, Assumption 2 in [Wang et al., 2021a)). The data distributions I satisfy the minimum eigenvalue condition: h E [H) Ky == Amin (2,) > 0. Furthermore, we denote k ming K4.
This is due to the fact that the uncertainty reward function is dominated by that of transition kemel in RI.. For clarity n for tabular MDP and K for linear MDP when referring the sample complexity.
3

---

2.2 Differential Privacy in offline RL
In this work, we aim design rivacy-preserving algorithms for offline RL. We apply differential privacy as the formal notion of privacy. Below we revisit the definition of differential privacy.
Definition 2.3 (Differential Privacy [Dwork et al., 2006]). randomized mechanism M satisfies (e, 8) differrentii privacy ((e, 6)-DP) if for all neighboring datasets U,U U" that differ by one data point and for all possible event E in the oulpul range, holds that
P[M(U) E E S E -P(M(()) E +
When 8 0, we say pure DP, while for 8 O, we say approximate DP.
In the problem of offline RL, the dataset consists of several trajectories, therefore one data point in Definition 2.3 refers 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 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.
Remark 2.4. For a concrete motivating example, please refer to the first paragraph of Introduction. We remark that our definition of DP is consistent with Joint DP and Local DP defined under the online RL setting where JDP/LDP also cast each user as one trajectory and provide user-wise privacy protection. For detailed definitions and more discussions about JDP/LDP, please refer to Qiao and Wang [2023a].
During the whole paper, we will use zCDP (defined below) as 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 E.3.
Definition 2.5 (zCDP [Dwork and Rothblum, 2016, Bun and Steinke, 2016]). A randomized mecha- nism M satisfies p-Zero- ConcoeCCCneeeeeeed Differential Privacy (p-cCDP), for all neighboring datasets U. and all a (0).
(M())) S pa,
where Dr, is the Renyi-divergence [Van Erven and Harremos, 2014).
Finally, we go over the definition and privacy guarantee of Gaussian mechanism. Definition 2.6 (Gaussian Mechanism [Dwork et al., 2014]). Define the l2 sensitivity of function f: F:N* + Rd as
A2(
sup
|I((U) - J(U')ll2
neighboring U,U
The Gaussian mechanism. M with noise level a is then given by
M(U) f(V) +N
Lemma 2.7 (Privacy guarantee of Gaussian mechanism [Dwork et al., 2014, Bun and Steinke, 2016)). N Let : - R&d be an arbitrary d-dimensional function with E, sensitivity A Then for any > 0,
Gaussian Mechanism with parameter o²
A3
2p satisfies p-zCDP. In addition, for all 8,
Gaussian Mechanism with parameter مZ 2log L26
satisfies (c, 8)-D..
We emphasize that the privacy guarantee covers any input data. It does not require any distributional assumptions the data. The Rp-speiific 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 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 D = {(*,, aj, rā. 1) he we denote Nss..an
Ex=1 1[s,, aj, -hh 0n] be the total counts that visit (sy, ax) pair at time h and Rak,ah.Sh41

---

Ei=1 1|s Th h/11 = an, Sh+il given the budget for zCDP, we add independent Gaussian noises to all the counts:
I be the total counts that visit (sh, OA S/+1) pair at time h, then
nea {naz.an + We = (Manonnent +N(0, 0² 2H (2)
P
However, after adding noise, the noisy counts n' may not satisfy s,,,,, = E n $h To address this problem, choose the private counts of visiting numbers the solution to the
I1 log 4M52A
following optimization problem (here Ep = 4V bound of the noises we add):
chosen as a high probability uniform
on IoES argmin wesee (r
max [g'' n' an.s
s'ES
E and Vi 2 2,08's ES.
such that
Σ LEES
Ves nl S
(3)
Σ Nen nan.as.s.
Nip aa
s'ES
Remark 3.1 (Some explanations). The optimization problem above serves a post-processing step which will not affect the DP guarantee of our algorithm. Briefty speaking, (3) (3) finds set of noisy counts such that oe = =Eves an. and the estimation error for each Tap and as roughly Epp In contrast, if we directly take the crude approach that ony
- and Nan.as EeanEs Tisn.as 8h+11 we can only derive [Nen.on -asn,y S Ö(VSE,) through concentration on summation of S ii.dd Gaussian noises. conclusion, solving the optimization problem (3) enables tight analysis for the lower order term (the additional cost of privacy).
Remark 3.2 (Computational efficiency). The optimization problem (3) can be reformalated as:
min I s.l. [Egg as S and ag 20AEES,
Σ SES
Fs - n ninnan
Ep 2
(4)
Note that (4) is Linear Programming problem with S variables and 25 + 2 linear constraints (one constraint on absolute value is equivalent to two linear constraints), which can be solved efficiently by the simplex method [Ficken, 2015] other provably efficient algorithms [Nemhauser and Wolsey, 1988]. Therefore, our Algorithm is computationally friendly.
The private estimation of the transition kernel is defined as:
Pa(8'I an)
(5)
Mss..n Ep and Pa(s'(sh, an) = otherwise.
Remark 3.3. Different from the transition kernel estimate previous works [Vietri et al., 2020, Chowdhury and Zhou, 2021] that may not be distribution, we have to ensure that ours is probability distribution, because our Bernstein type pessimism (line in Algorithm 1) needs to take variance over this transition kernel estimate. The intuition behind the construction of our private transition kernel is that, for those stale-action pairs with ner & F.p we can not distinguish whether the non-zero private count comes from noise actual visitation. Therefore only take the empirical estimate of the state-action action pairs with sufficiently large Nan.or.
"This conclusion is summarized in Lemma C.3.
5

---

Algorithm Differentially Private Adaptive Pessimistic Value Iteration (DP-APVI)
1: Input: Offfine dataset D = [( ahs The 8 ()))))
r,h=1- Reward function r. Constants C1 = v2
16, C > 1, failure probability budget for zCDP p.
2: Initialization: Calculate Reg. Phi (3), Ps(4 (s,, aa) as (5). VH+1(.) +- 0. Fip +-
21 log 4
VV
L (oS(H))/)).
P
3: for h = H. H - 1,...,1 do
Qu(:.) -- rn(::)) + (Pr. V.+ Var Aogi0n Fi
5:
Vsh, an. let (sn on) +GV
Var Puzz mn (at1ha
CySHEp Rn
Mon.an > Ep, otherwise CH.
6:
(2(+) + (.(:.)) --(s))-
7:
Qx(+) &- min (h. +++
8: Vsa. let (-(w)))) E argmax,, (sh -) Na (-1s5)) and (s()) t (Qn :), 8r (-1on))
9: end for
10: Output: (m.).
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 [Yin and Wang, 2021b), we design a similar pessimistic algorithm with private counts to ensure differential privacy. If we replace 72 and P with n and p6, then our DP-APVI (Algorithm 1) will degenerate to APVI. Compared to the pessimism defined APVI, our pessimistic penalty has an additional term Ō accounts for the additional pessimism due our application of private statistics.
which
We state our main theorem about DP-APVI below, the proof sketch is deferred to Appendix C.I and detailed proof is deferred to Appendix C due to space limit.
Theorem 3.4. DP-APVI (Algorithm 1) satisfies p-zCDP. Furthermore, under Assumption 2.1, denote dm == min {dl (sh, ah) d (Sh: aq) > 0}. For any 0 < 5 < 1, there exists constant ei >> O, such that when n. > C1 max Eo//dm policy गे of DP-APVI satisfies
log H A/8)), with probability 1 1- 6, the output
Var Var (V+ ()) nal (Sh, ah)
+Ō ( (11* 18+SSHED
05 4/2 Σ
di (sh,an) (EC
Σ
n dm
(6)
where O hides constants and Polylog terms, E.p = 4 log 4852A
Comparison to non-private counterpart APVI [Yin and Wang, 2021b]. According to Theorem 4.1 in (Ynn and Wang. 2021b], the sub-optimality bound of APVI is for large enough n, with high probability, the output के satisfies:
(as.a. (V (.) ndd (sh, an)
H
0- - 3 s
Σ
Σ
(sh, (9h and
+
(7)
dm
h= (EC.
Compared to our Theorem 3.4, the additional sub-optimality bound due to differential privacy is
( SHH niddo
SH = n-dm
SH 12-dm
7 In the most popular regime where the privacy budget
P 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 C,SHE, Then
type pessimism, which replaces the pessimism in line with C, H
N,,,,,,- EEp
TThe non-private empirical estimate, defined as (15) in Appendix C. 'Here we apply the second part of Lemma 2.7 to achieve (c, 6DDP, the notation also absorbs log (only here å denotes the privacy budget instead of failure probability).

---

with similar proof schedule, we can arrive at sub-optimality bound that with high probability,
/ 72 dm
0 Os 0 1 E. E
di (sh, andy ndl (oh, an)
Ō
(8)
h=1 (FC.
Compared to our Theorem 3.4, our bound is tighter because we express the dominate term by the system quantities instead of explicit dependence on H (and Varp, (-I,.a) (V (+)) I H²). In addition, we highlight that according to Theorem G. in [Yin and Wang. 2021b], , our main term nearly matches the non-prine non-private minimax lower bound. For more detailed discussions about our main term and how subsumes other optimal learning bounds, we refer readers to [Yin and Wang, 2021b].
Apply Laplace Mechanism to achieve pure DP. To achieve Pure DP instead of p-7CDP, we can simply replace Gaussian Mechanism with Laplace Mechanism (defined as Definition 19) Given privacy budget for Pure DP e, since the f sensitivity of (N,g, J (0,444 is A 4H, we can add independent Laplace noises Lap( AM) to each count to achieve c-DP due to Lemma E.20.
Then by using E. = Ô ( ()) instead of E and keeping everything else ((3), (5) and Algorithm 1) the same, can reach similar result to Theorem 3.4 with the same proof schedule. The only difference is that here the additional learning bound is θ SH"
which still appears lower order term. nn-dme))
4 Results under linear MDP: DP-VAPVI(Algoritm) 2)
In large MDPs, to address the computational issues, the technique of function approximation is widely applied, and linear MDP 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 D and D' (both from j() as in Algorithm we can apply variance-aware pessimistic value iteration to learn near optimal policy as in VAPVI [Yin et al., 2022]. To ensure differential privacy, we add independent Gaussian noises to the 5H statistics as in PP-VAPVI (Algorithm 2) below. Since there are 5H statistics, by the adaptive composition of zCDP (Lemma 1717), it suffices to keep each count Po-7CDP, where pa = 5H In VAPVI, we use Φ1, $2, da,, K1, K2² to denote the noises we add. For all di, we directly apply Gaussian Mechanism. For K3, in addition to the noise matrix (Z + Z "), we also add E 2 la to ensure that all K, are positive definite with high probability (The detailed definition of E, L can be found in Appendix A).
Below we will show the algorithmic design of DP- VAPVI (Algorithm 2). For the offline dataset, he[H] we divide it into two independent parts with equal length: D {(5h, ah rh. ) and D' (15 Th, Fh. (h4))) One for estimating variance and the other for calculating Q- -aluuus.
Estimating conditional variance. The first part (line 4 line 8) aims estimate the condi- tional variance Vh+1 via the definition of variance: [Var,, V a) = [P% (V)+)))))))(,, a) ([P Va+i][ss, a))2. For the first term, by the definition of linear MDP, it holds that PA PA A+1 (s,a) = a( SS ViL (s') drn (s') = [s V2 (s') dr, (s')). We can estimate 3r fs V.2 (s') du, (s') by applying ridge regression. Below is the output of ridge regression with raw statistics without noise:
argmin BERA
Ko(sh, at), Vhin 1shht)]² + 21131k = Ez Σ
( ah Vh (sh+1),
We need to add noise to each of the 5H counts, therefore for Φi, we actually sample H i.i.d samples 61,6. h = 1, ... H from the distribution of ó1 Then we add Ø1,1 to Σ**,, 0(5), ag) ( v E [H]. For simplicity, use di represent all the 61,6. The procedure applied to the other 4H statistics are similar.
7

---

Algorithm 2 Differentially Private Variance-Aware Pessimistic Value Iteration (DP-VAPVI)
K.H 1: Input: Dataset D = {(5h, ai rh. sh+1)) K.H D' = {(8,, The Thi 8h,41) T, Budget for zCDP
Failure probability 8. Universal constant
2: Initialization: Set pu < siu V+) &- O. Sample Φr ~ ~N(O,
201
la). 02, Φ ~ ~N[ (0, 2H2 Ia)
Po
K1, K2 la J2 + ) where Ze, N (0, 4pu 1.0) (d.i.d), E Ō Ö(V Hd
Sct D
H + 44g Va).
3372
3:
for h H, H -1,..., do
4: Set En f Σ 663%, ah (355, " + +
5: Set 3n. + 2n 12 o(s añ) (5 +i]
6: Set On < En E o(5h. añ) (5641) dzl
7:
Set Vara Vn+1 (1.)) + (6 3n (0.0011
[( -), 0n) (k/.::), p.n
8:
Set (- )2 f max(1, Vara (141(:;))
9:
Set Σx @ (8h, añd (shi 07.
(oh an) + K2
10:
Set Wh + A%5 (2 @ (5% an)
1 +
Vht1 (sh+2) / añ) + 0z)
11:
Set ((,.)) +- CVd. (6(:-) ) 7 (x,)),
1/2
12:
Set (n(, s -((-)) wh [((s))
13:
Set (1) c <mmn|| (1 ) 9, 11- h 11
14:
Set (.
argmaax,, (a((.)) )) TT( (,)) Va(.) + maxa, (Qn(s)), m. 1.))
15:
end for
16:
Output: [ThTk=11
where definition of Σn can be found in Appendix A. Instead of using the raw statistics, we replace them with private ones with Gaussian noises in line 5. The second term is estimated similarly in line 6. The final estimator is defined as in line (=.-) max(1, Var, (.+1(.))).
weightee-weighted weighted LSVI. Instead of directly applying LSVI [Jin al., 2021]. we can solve the variance- warigtee-weighted LSVI (line 10). The result of werigte LSVI with non-private statistics is shown below:
(olsk. ah),, w) - -V--((((+1)
K Φ (sh. al)
(r + Vata (#h+1))
argmin 1| wead
06 ())
o7 af)
A=1
where definition of A₁ can be found in Appendix A. For the sake of differential privacy, we private statistics instead and derive the Wh 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 [Yin et al., 2022]. We design similar pessimistic penalty using private statistics (line 11), with additional D
K accounting for the extra pessimism due to DP.
Main theorem. We state our main theorem about Appendix D.1 and detailed proof is deferred to Appendix D due to space limit. Note that quantities M,, L, E can be found in Appendix A and briefly, L (L))))/)). E OdVHd/p) For the sample complexity lower bound, within the practical regime where the privacy budget is not very small, max max{ is dominated by max (0 /x²) Ō ((Hld/xx)) which also appears in the sample complexity lower bound of VAPVI [Yin et al., 2022]. The of (s,a) in Theorem 4.1 is defined as max 1, Varr, (V)(s, a)} for any V.
below, the proof sketch deferred to
a)
Theorem 4.1. DP-VAPVI (Algorithm 2) satisfies p-zCDP. Furthermore, let K be the number of episodes. Under the condition that K > max{M1, Ma. and vd > E, where & := - for any 0 < A < K, with probabiliy for (v.a)
supve(o.H), Pa hE[H]
9The max(1.)) operator here is for technical reason only: we want lower bound for each variance estimate.
8

---

all policy π simultaneously. the output ß of DP- VAPVI satisfies
0² -~ 50 Vd.
Σ
11
B
(((6::)AA0(6)))) +
DH
K
A=1
where A,, EK=1 blek Mek
+ Nla D D= -=0 SH Haavd
0(
+ HDVd) and Ô hides
x312
constants and Polylog terms.
pio ol (ohiot
In particular, define A k==
+ Ala we have with probability 1 8,
0² <ō
Vd. Σ Ees (o(.))AA 10.3))
H
DH
+ K
(10)
Comparison to non-private counterpart VAPVI [Yin et al., 2022]. Plugging in the definition of L, E (Appendix A), under the meaningful case that the privacy budget is not very large, DH is
dominated by Ō bound of VAPVI is for sufficiently large K, with high probability, the output î satisfies:
1 d/ VP
According to Theorem 3.2 in [Yin et al., 2022], the sub-optimality
0* - 3 So
<0(v
Vd. Vi
Σ B. h=1
(VO...TA; + 2H
(11)
Compared to our Theorem 4.1, the additional sub-optimality bound due to differential privacy is
H d/k Ō H d/w 10 In the most popular regime where the privacy budget p or
Jp-K
<
constant, the additional term due to differential privacy also appears as a lower order term.
Instance-deeendent sub-optimality bound. Similar DP-APVI (Algorithm 1), DP-VAPVI (Algorithm 2) also enjoys instance-dependen sub-optimality bound. First, the main term in (10) improves PEVI [Jin et al., 2021] over O(vd) on feature dependence. Also, our main term admits no explicit dependence on H, thus improves the sub-optimality bound PEVI on horizon dependence. For more detailed discussions about our main term, we refer readers to [Yin et al., 2022].
Private and safe policy improvement. In addition to the sub-optimality bound (10), have the so called oracle inequality
(9). Therefore, the performance y can be lower bounded by (
sup= [ -z - (d Σ"= Ex Vo(..) (6.)))
DH
When choosing π to be the opti-
mal policy in the neighborhood of the behavior policy our DP- VAPVI (Algorithm 2) sheds light on safe policy improvement with differential privacy guarantee.
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-theoreiic. lower bounds for offline RL simultancously (this was illustrated in Yin and Wang [2021b], Yin al. [2022]), for this reason our bound cannot be improved in general. For the lower order terms, the dependence
sample complexity and privacy budget Ō (1) is optimal since policy learning is special case of ERM problems and such dependence is optimal in DR-ERM. In addition, we believe the dependence on other parameters (H, S, A, d) in the lower order term is tight due to special tricks (3) and Lemma D.6.
Here we apply the second part of Lemma 2.7 to achieve (c, 6D- the notation also absorbs log (only here å denotes the privacy budget instead of failure probability).

---

6 Simulations
In this section, we carry out simulations to evaluate the performance of our DP-VA VAPVI (Algorithm 2). and compare it with its non-privann private counterpart VAPVI [Yin et al., 2022] and another pessimism- -aase algorithm PEVI [Jin et al., 2021] which does not have privacy guarantee.
Experimental setting. We evaluate DP-VAPVI (Algorithm 2) synthetic linear MDP example that originates from the linear MDP in [Min et al., 2021, Yin et al.. 2022] but with some modifications. "I For details of the linear MDP setting, please refer Appendix The two MDP instances we use both have horizon H = 20. We compare different algorithms in figure ((a), while in figure 1(b), we compare our DP-VAP VAPVI with different privacy budgets. When doing empirical evaluation, we do not split the data for DP-VAPY or VAPVI and for DP-VAPVI, we run the simulation for 5 times and take the average performance.
PEVI
VAPA
WAP
DP-MAPN,
DA
DP-UAPAS.p2
DF VAPVLL5-=25
DE-WANSS,PS DP-UAPNS,P-25
Ruhorp Suh may 090
Suboot
200
600
1000
(a) Compare different algorithms, H 20 (b) Different privacy budgets, H 20
Figure 1: Comparison between performance of PEVI, VAPVI and DP-VAPVI (with different privacy budgets) under the linear MDP example described above. each figure, y-axis represents sub- optimality gap o* vd while x-axis denotes the number of episodes K. The horizons are fixed to be H. 20. The number episodes takes value from to 1000.
Results and discussions. From Figure 1, can observe that VAPVI (Algorithm 2) performs slightly worse than its non-private version VAPVI [Yin et al., 2022]. This is due to the fact that add Gaussian noise each count. However, 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 lower order terms. For DP- with larger privacy budget, the scale of noise will be smaller, thus the performance will be closer to VAPVI, as shown in figure 1(b). Furthermore, in most cases, DP-VAPVI still outperforms PEVI, which does not have privacy guarantee. This arises from our privitization of variance-awaid 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 I.VV)) 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 offline RL applications. Many techniques we developed could be adapted to these more general settings.
We keep the state space S = {1,2), action space A = (1..... 100} and feature map of state-action pairs while we choose stochastic transition (instead of the original deterministic transition) and more complex reward.
10

---

Acknowledgments
The research is partially supported by NSF Awards #2007117 and #2048091, The authors would like to thank Ming Yin for helpful discussions.
References
Yasin Yadkor,, Dávid Päl, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Interna- tional Conference on Machine Learning, pages 32 40.4.. PMLR, 2017.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, pages 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings the 34th International Conference on Machine Learning- Volume 70, pages 263-272. JMLR. org, 2017.
Borja Balle, Maziar Gomrokchi, and Doina Precup. Differentially private policy evaluation. In International Conference Machine Learning, pages 2130-2138. PMLR, 2016.
Debabrota Basu, Christos Dimitrakakis, and Aristide Tossou. Differential privacy for multi-arme bandits: What is and what is its cost? arXiv preprint I9055 12298, 2019.
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. When memorization of irrelevant training data necessary for high-accuracy learning? In ACM SIGACT Symposium Theory of Computing, pages 232-32,-7 2021.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and
lower bounds. In Theory of Cryptography Conference, pages 635-658. Springer, 2016.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jemnj Kos, and Dawn Song. The secret sharer: Evalu- ating and testing unintended memorization neural networks. In USENIX Security Symposium (USENIX Security 19), pages 267-284, 2019..
Xiaoyu Chen, Kai Zheng, Zixin Zhou, Yunchang Yang, Wei Chen, and Liwei Wang. (locally) differ- entially private combinatorial semi-bandits. International Conference on Machine Learning, pages 1757-1767. PMLR, 2020.
Herman Chernoff et al. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23(4):493-507, 1952.
Sayak Ray Chowdhury and Xingyu Zhou. Differentially private regret minimization in episodic markov decision processes. arXiv preprint arXiv:21 10599, 2021.
Sayak Ray Chowdhury, Xingyu Zhou, and Ness Shroff. Adaptive control of differentially private linear quadratic systems. 2021 IEEE International Symposium on Information Theory (ISIT), pages 485-490. IEFE, 2021.
Chris Cundy and Stefano Ermon. Privacy-constrained policies via mutual information regularized policy gradients. arXiv preprint arXiv:2012.15019 2020.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pages 5713-5723, 2017.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint arXiv:1603.01887, 2016.

---

Cynthia Dwork, Frank McSherry. Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor, Comput. Sci., 9(3-4):211-400) 2014.
Frederick Arthur Ficken. The simplex method of linear programming. Courier Dover Publications, 2015.
Pratik Gajane, Tanguy Urvoy, and Emilie Kaufmann. Corrupt bandits for preserving local privacy. In Algorithmic Learning Theory, pages 387-412. PMLR, 2018.
Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00494 2021.
Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke, and Matteo Pirotta. Local differential privacy for regret minimization in reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Abhradeep Guha Thakurta and Adam Smith. (nearly) optimal algorithms for private online learning in full-information and bandit settings. Advances in Neural Information Processing Systems, 26, 2013.
Bingshan Hu, Zhiming Huang, and Nishant A Mehta. Optimal algorithms for private online learning in a stochastic environment. arXiv preprint arXiv:2102.07929, 2021.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learming, pages 4870-4879. PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143.
PMLR, 2020b.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rI? In International Conference on Machine Learning, pages 5084-5090 PMLR, 2021.
Hyeoneui Kim, Elizabeth Bell, Jihoon Kim, Amy Sitapati, Joe Ramsdell, Claudiu Farcas, Dexter
Friedman, Stephanie Feudjio Feupe, and Lucila Ohno-Machado. iconcur: informed consent for clinical data and bio-sample use for research. Journal of the American Medical Informatics Association, 24(2):380-387, 2017.
Jonathan Lebensold, William Hamilton, Borja Balle, and Doina Precup. Actor critic with differentially private critic. arXiv preprint arXiv: 2019.
Chonghua Liao, Jiafan He, and Quanquan Gu. Locally differentially private reinforcement learning for linear mixture markov decision processes. arXiv preprint vrXiv:2110.10133 2021.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. In Uncertainty in Artificial Intelligence, 2019.
Paul Luyo, Evrard Garcelon, Alessandro Lazaric, and Matteo Pirotta. Differentially private explo- ration in reinforcement learning with linear representation. arXiv preprint arXiv:2112.01588 2021.
Sunil Madhow, Dan Qiao, Ming Yin, and Yu-Xiang Wang. Offline policy evaluation for reinforcement learning with adaptively collected data. arXiv preprint 2006633306..4063 2023. 2023.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion. Conference Learning Theory, 2009.
Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Variance-aware off-policy evaluation
with linear function approximation. Advances in neural information processing systems, 34, 2021.
12

---

George Nemhauser and Laurence Wolsey, Polynomial Simemomial-time algorithms for linear programming. Integer and Combinatorial Optimization, pages 146-181, 1988.
Dung Daniel Ngo, Giuseppe Vietri, and Zhiwei Steven Wu. Improved regret for differentially private exploration linear mdp. arXiv preprint arXiv:2202.01292. 2022.
Hajime Ono and Tsubasa Takahashi. Locally private distributed reinforcement learning. arXiv
preprint arXiv:2001.11718, 2020.
Dan Qiao and Yu-Xiang Wang. Npar-optimal differentially private reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9914 9940.09.0 PMLR, 2023a.
Dan Qiao and Yu-Xiang Wang. Near-optimal deployment efficiency in reward-free reinforcement learning with linear function approximation. In The Eleventh International Conference Learning Representations, 2023b.
Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog(T) switching cost. Proceedings of the 39th International Conference on Machine Learning, pages 18031-18061 PMLR, 2022.
Dan Qiao, Ming Yin, and Yu-Xiang Wang. Logarithmic switching cost in reinforcement learning beyond linear mdps. arXiv preprint arXiv:2302. 2ww::3302.1255555 12456, 2023.
Aniruddh Raghu, Matthieu Komorowski, Leo Anthony Celi, Peter Szolovits, and Marzyeh Ghas- semi. Continuous state-space models for optimal sepsis treatment: deep reinforcement learning approach. In Muchine Learning for Healthcare Conference, pages 147-163, 2017.
Rachel Redberg and Yu-Xiang Wang. Privately publishable per-instance privacy. Advances in Neural Information Processing Systems, 34, 2021.
Ahmad EL Sallab, Mohammed Abdou, Etienne Perot, and Senthil Yogamani. Deep reinforcement learning framework for autonomous driving. Electronic Imaging, 2017(19) 2017.
Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31, 2018.
Karthik Sridharan. A gentle introduction to concentration inequalities. Dept. Comput. Sci., Cornell Univ., Tech. Rep, 2002.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Aristide Charles Yedia Tosson and Christos Dimitrakakis. Achieving privacy in the adversarial multi-armed bandit. In Thirty- AAAI Conference on Artificial Intelligence, 2017.
Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory, 60(7):377733800, 2014.
Giuseppe Vietri, Borja Balle, Akshay Krishnamurthy, and Steven Wu. Private reinforcement learning with pac and regret guarantees. In International Conference on Machine Learning, pages 9754- 9764. PMLR, 2020.
Baoxiang Wang and Nidhi Hegde. Privacy-preserving q-learning with functional noise in continuous spaces. Advances in Neural Information Processing Systems, 32, 2019.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? International Conference on Learning Representations, 2021a.
Tianhao Wang. Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances in Neural Information Processing Systems, 34: 34:13524-13536, 2021b.
Tengyang Xie, Philip S Thomas, and Gerome Miklau. Privacy preserving off-policy evaluation, arXiv preprint 1902::190 2019.
13

---

Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-coo consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficiet offline and online reinforcement learning. Advances in neural information processing systems, 2021b.
Jianyu Xu, Dan Qiao, and Yu-Xiang Wang. Doubly fair dynamic pricing. In International Conference on Artificial Intelligence and Statistics, pages 9941-9975. PMLR, 2023.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient ooflpy evaluation for tabular rein- forcement learning. In International Conference on Artificial Intelligence and Statistics, pages PMLR, 2020.
Ming Yin and Yu- XiaXia Wang. Optimal uniform ope and model-based offline reinforcement learning in homogeoomgessuss, reward-free and task-agnostic settings. Advances neural information processing systems, 2021a.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34, 2021b.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In International Conference Artificial Intelligence and Statistics, pages 1567-1575. PMLR, 2021.
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprinl 2Xiv:2203.05804 2022.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. International Conference on Machine Learning, pages 12287-12297. PMLR, 2021.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 2021.
Zihao Zhang, Stefan Zohren, and Stephen Roberts. Deep reinforcement learning for trading. The Journal of Financial Data Science, 2(2):25-40, 2020.
Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. Differentially private linear sketches: Efficient implementations and applications. Advances in Neural Information Processing Systems, 35: 122112261222000 2022.
Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems, 32:02300- 12310, 2020.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR, 2021.
Xingyu Zhou. Differentially private reinforcement learning with linear function approximation. arXiv preprint XXX::2201.07052. 2022.
14

---

A
Notation List
A.1 Notations for tabular MDP
2 log 2852A
E
The original counts of visitation
n'
The noisy counts, as defined in (2)
n
Final choice of private counts, as defined in (3)
P
Private estimate of transition kernel, as defined in (5)
P
Non-private estimate of transition kernel, as defined (15)
log HSA
L
Budget for zCDP
8
Failure probability
A.2
Notations for linear MDP
GHdlog(
1020
L
2H
10Hd
2
(ogg(5e) H16) cnd
D
0 H²L
H'FVa 1a12
H
A
(5) Ala Σ R=1 (8) a ( a
K
A
En oss dos ) 1 a Ala + K2
()) ()))s,))
A
ΣR ol
(5) 07.) + XI
AR
E Vor ())
A
IR 06 005 /0 (5% 07)) +X
E
Σ K ol 005% a + +
En
Et= 63,, (733 T + Ala + K1
Ep,h [o(s, a)o(s,a)
min; Amiu (E%)
())
max (1, [1, Varp, (V) a)} for any V
(x,,))
max {1, Varp, (+,
(8,
max (1, Vara Vn+1 (x, a)}
Mi
max (2A, 128 log (2dH//).
128 log (2)(2
/2L1
vdx
M2
max 12 / /k²), "(H''//K*)
max
Ma
max
512H Tog 24H
4XH2
MA
max
H H
p
Budget for zCDP
8
Failure probability (not the 8 of (e, 0)-D)
(
(Ta
g
supvelo.HH, P'.aa, he[H]
(s.0)
15

---

B 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, Vietri et al. [2020] design PUCB by revising UBEV [Dann et al., 2017]. Private-UCB-VI [Chowdhury and Zhou, 2021] results from UCBVI (with bonus-1) 1) [Azar et al., 2017]. However, both works privatize Hoeffding type bonus, which lead to sub-optimal regret bound. Under linear MDP, Private LSVI-UCB [Ngo et al., 2022] and Frivacy-Preserving LSVI-UCB [Luyo et al., 2021] are private versions of LSVI-UCB [Jin et al., 2020b], while LinOpt-VI-Reg [Zhou, 2022] and generalize UCRL-VTR [Ayoub et al., 2020]. However, these works are usually based on the LSVI technique [Jin et al., 2020b] (unweighted ridge regression), which does not ensure optimal regret bound.
UCRL-VTR [Luyo et al., 2021]
In addition to JDP, another common privacy guarantee for online RL is Local Differential Privacy (LDP), LDP is stronger definition of DP since it requires that the user's data is protected before the RL agent has access it. Under LDP, Garcelon et al. [2021] reach a regret lower bound and design LDP-OBI which has matching regret upper bound. The result is generalized by Liao et al. [2021] to linear mixture setting. Later, Luyo et al. [2021] provide an unified framework for analyzing JDP and LDP under linear setting.
Some other differentially private learning algorithms. There some other works about dif- ferentially private online learning [Guha Thakurta and Smith, 2013, Agarwal and Singh, 2017, Hu al., 2021] and various settings of bandit [Shariff and Sheffet, 2018, Gajane et al., 2018, Basu et al., 2019, Zheng et al., 2020, Chen et al., 2020, Tossou and Dimitrakakis, 2017]. For the reinforcement learning setting, Wang and Hegde [2019] propose privacy- privacy-preserving Q-learning to protect the reward information. Ono and Takahashi [2020] study the problem of distributed reinforcement learning under LDP. Lebensold et al. [2019] present an actor critic algorithm with differentially private critic. Cundy and Ermon [2020] tackle DP-RL under the policy gradient framework. Chowdhury et al. [2021] consider the adaptive control of differentially private linear quadratic (LQ) systems. Zhao et al. [2022] designed differentially private linear sketch algorirthms.
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 (OPB), Yin and Wang [2020] uses Tabular-MIS estimator to achieve asymptotic efficiency. In addition, the idea of uniform OPE is used to achieve the optimal sample complexity 0HH =d [Yin et al.. 2021] for non-stationary MDP and the optimal sample complexity 0(H²2 /dm [Yin and Wang, 202 for stationary MDP, where dm is the lower bound for state-action occupancy. Such uniform convergence idea also supports some works regarding online exploration [Jin et al., 2020a, Qiao et al., 2022, Xu et al., 2023]. For offline RL with single concentrability assumption, Xie et al. [2021b] arrive at the optimal sample complexity SCH /2?). Recently, Yin and Wang [2021b] propose APVI which can lead to instance setance-dependen sub sub-optti uuboopimalltty bound, which subsumes previous optimal results under several assumptions. Madhow et al. [2023] consider offline policy evaluation for adaptively collected datasets.
Recently, many works focus on offiine RL Offline reinforcement learning under linear MDP.
under linear representation. Jin et al. [2021) present PEVI which applies the idea of pessimistic value iteration (the idea originates from [Jin et al., 2020b]), and PEVI is provably efficient for offline RL under linear MDP. Yin et al. [2022] improve the sub-optimality bound in [Jin et al., 2021] by replacing LSVI by aariance-weighter LSVI. Xie et al. [2021a] consider Bellman consistent pessimism for general function approximation, and their result improves the sample complexity in [Jin et al., 2021] by order (dd (shown in Theorem 3.2). However, there is no improvement on horizon dependence. Zanette et al. [2021] propose a new offline actor-critic algorithm that naturally incorporates the pessimism principle. Besides, Wang et al. [2021a], Zanette [2021] study the statistical hardness of offline RI. with linear representations by presenting exponential lower bounds. When relaxing the offline setting to low adaptive RI, Gao et al. [2021], Wang et al. [2021b], Qiao and Wang [2023b]. Qiao et al. [2023] designed algorithms with low adaptivity.
16

---

C Proof of Theorem 3,4
C.1 Proof sketch
Since the whole proof for privacy guarantee not very complex, we present it in Section C.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 derived from (3) are close real visitation numbers. Therefore, denoting the non-private empirical transition kernel by P (detailed definition in (15)), we can show that |P Pl12 and Vv //rrp(V) <VVarp(V) are small.
Next, resulting from the conditional independence of VA+1 and Pr. we apply Empirical Bernstein's + SH Nan.a.. Together with our
inequality get I(Ph V++l S (Varp((V definition of private pessimism and the key lemma: extended value difference (Lemma E.7 and E.8), we can bound the suboptimality of our output policy # by:
H
Var (lla,, (Vm-1())
dh (sh, an)
+ SH Ep De Dag
(12)
h=1 (CC
Finally, we further bound the above suboptimality via replacing private statistics by non- non-private ones. Specifically, replace ñ by n, P by P and V by V*. Due to (12), we have I| V* S nd..
Together with the upper bounds of |P Pll1 and lv (Vr Varp((V) we have
Varpa P.len an)
(Vn+
(l (-i+t()))
+
nan.as
nannas
rud
Var Pa (-la and h+t1 (-)
1
Var Pa (lmsoo)) (Vi+1())
1
(13)
nd
Den.as
nd
Var (ll (Vi+1
1
ndm The final bound using non-private statistics results from (12) and (13).
ndl (5h, ax))
C.2 Proof of the privacy guarantee
The privacy guarantee of DP-APVI (Algorithm 1) summarized by Lemma C.1 below. Lemma C.1 (Privacy analysis DP-APVI (Algorithm 1)). DP-APVI (Algorithm satisfies p-2CDP.
Proof of Lemma C.I. The & sensitivity of (n.., is V2H. According to Lemma 2.7, the Gaussian Mechanism used on (ns,.as) } with 0² = 2H satisfies G-CDDP. Similarly, the Gaussian Mechanism used on (res.en.sher) with o² 2H also satisfies f-ZDDP. Combining these two results, due the composition of zCDP (Lemma E. E.1 the construction of (n'} satisfics p-2CDP. Finally, DP-APVI satisfies p-zCDP because the output स is post processing of [n'].
C.3 Proof of the sub-optimality bound
C.3.1 Utility analysis
First of all, the following Lemma C.2 gives high probability bound for In' nl).
Lemma C.2. Let E,- = 2/200 / log AHS2A
4v
H log ARSRA
then with probability - 8, for all
8h, Oh. 81 it holds that
Ep
Eg (14)
In In an
Das.anl
In 1n. Des.
2
17

---

Proof of Lemma C.2. The inequalities directly result from the concentration inequality of Gaussian distribution and union bound.
According to the utility analysis above, we have the following Lemma C.3 giving high probability bound for ( r2/.
Lemma C.3. Under the high probability event in Lemma C.2, for all 8h; ah Sh+1 holds that
Mannas
Ep, |Ma. aa S Epp
Proof of Lemma C.3. When the event in Lemma C.2 holds, the original counts (n an foe is feasible solution to the optimization problem, which means that
Ep
max Dsn,
max [is Tonnasie S en Wh
2
Due to the second part of (14), holds that for any Sh, ahs Sh+1.
[ n 7
Th an.
|n (ms..nn Ray 22 S Ep.
For the second part, because of the constraints in the optimization problem, it holds that
Eg 2
Mannas
Due to the first part of (14), holds that for any Sh: ah.
Men.on nanias S [een.n nn mnss.nn Mennall S Ep.
Let the non-private empirical estimate be:
PM (sh an) Ds.
(15)
if Dag.on >> O and (r'ls's |s,, an) 1 otherwise. We will show that the private transition kernel P is close to by the Lemma C.4 and Lemma C.5 below. Lemma C.4. Under the high probability event of Lemma for Sh. ab. that
if Nen.en 3Ep. it holds
Pr an) Pa am)l s
5SEp
(16)
Mannan
Proof of Lemma C.4. If Mss.an 2 3Ep and the conclusion in Lemma C.3 hold, we have
Pa( an) - Pa( an)l,, - Σ
(s an) P ( an)
S'ES
+ Ep
Mag.on
E,p
Than aa
s'eS
Σ
2Ep
(eei.nnis + Ep)
non as
(17)
722 8a.an
Nay
s'ES
SEp
2Ep p
2SE2
p
20D 11
5SEp
The second inequality is because
"o Ee Meyay t.p
aap mayion
ie E. Mepian Ep
and "ap of E.
The, Exp
"up. Ray.an
Ry "p. F. Ray,a, F
The third inequality is because of Lemma E.6. The last
Pog..ng
incquality is because Nin 3.e
18

---

Lemma C.5. Let V E R$ be any function with || S H, under the high probability event of Lemma C.3. Shy ah if is 2 pp it holds that
SEp 1lan,ah
Var (nl (V) V (l) S AHl,
(18)
Proof of Lemma C.5. For sh, an such that Men.on अEp. we use P() and P() instead of (:.s:1s. ax) and (- an) for simplicity. Because Lemma C.4, we have
P()) (1)-P(l1 =
5SEp
non.as
Therefore, it holds that
Varp(s(V) - Varmm) (V)
$ Var (V) Var Var (V)
P(s') P('')-((3)) P())) +
Σ
(((')) + P(S)) v(6)
Σ
- V(8)
((()) - P()))
e'ES
e'ES
e'ES
S/ H² |(t)-(())))
- p())|, + +2Hz [P(] P()|
S
SAH
Pen.ah
(19)
The second incquality due to the definition of variance.
C.3.2
Validity of our pessimistic penalty
Now we are ready to present the key lemma (Lemma C.6) below to justify our use of I as the pessimistic penalty.
Lemma C.6. Under the high probability event of Lemma C.3, with probability 8. for any shi ab. if Mannaa 2 3Ep (which implies nan >> 0), it holds that
2ar P.. (1s an (v)+1())
16SHEp
(Ph Pb) (itz(sh, S
(20)
Ep
Tsp aa
where V is the private version of estimated V function, which appears in Algorithm and log(H HSA/)).
Proof of Lemma C.6.
(Pr Ph) Vn I an) s
Vnni(sn, (hnlssn.a/// + (PP 11p-PP -Pa) Vh+1 and
PP.(-oon <H |Pa(-1on - an)l, + +1(Ph. - Ph) Vn+z(on,
(21)
- 5SHE, (P%- Ph) (Sn.
where the third inequality is due to Lemma C.4.
Next, recall #1 in Algorithm is computed backwardly therefore only depends on sample tuple from time h + 1 to H. As result, V (Q Ru+1) also only depends the sample tuple from time h + 1 to H and some Gaussian noise that is independent to the offline dataset. On the other side, by the definition, P/ only depends on the sample tuples from time h to h - 1. Therefore V and Pr are Conditionally independent (This trick is also used in [Yin et al., 2021] and [Yin and Wang,
19

---

2021b]). by Empirical Bernstein's 's inequality (Lemma E.4) and a union bound, with probability 1 - 5, for all Sh, dn such that no,,... 2 p
Var P.(l) (V++1())
7H
(Ph Ph)) 1h an) an)
S
(22)
Bay.
Therefore, have
Var Pa ( (s)
(V)-1(-))
7H-6
5SHE
(Ph Ph.) Vn+ (52, s
3m0m.
2 Var Py ()
(V)+1())) (-))
9SHEp -
9SHE, 1L
2 Var a.)
(V)-1-))-
+ 442H
SEp* .
(23)
Mannap a
2ar Pr (n))
(Vi+1 (-))
16SHEp 1
Varri (.
(V)+1()))
16SHE,
10 Exp
The second and forth incquality is because when Man.as 2 3Ep. Rannaa these two inequalities are also because usually we only care about the case when S 2 1, which is equivalent being not very large. The third inequality is due to Lemma C.5. The last inequality is due to Lemma C.3.
20 Specifically,
Note that the previous Lemmas rely the condition that ñi is not very small (as 2 3E,). Below we state the Multiplicative Chernoff bound (Lemma C.7 and Remark C.8) to show that under our condition in Theorem 3.4, for (sh, a4.) Cn. ns, will be larger than 3E, with high probability. Lemma C.7 (Lemma B. in [Yin and Wang, 2021b]). For any < 1, there exists an absolute constant oj such that when total episode vh E [
c1 1/dm loo((HSS///H) then with probability 1 8,
nan.as 2 n ma.d% (ss,
A an) Cn.
Furthermore, we denote
E:= (ne on
2 (sh, /22, V (sh,an) Cn. h [H].]
(24)
then equivalently P(E) > 1 -. 8. In addition, we denote
:' (nsnas S n (sn, an), A (sn, Ch. h [H].}
(25)
then similarly P(E')>1-
Remark C.8. According to Lemma C.7. for any failure probability 5, there exists some constant > O such that when 2 E,E, with probability 1 - 8, for all (sh,ax) E Cr. Day,on 2 4Ep. Therefore,
dm
under the condition of Theorem 3.4 and the high probability events in Lemma C.3 and Lemma C.7,
holds that for all (Sh, an) E Cho Dsa.an 2 3Ep while for all (Sh, an) & Cho Den.an S Epp
Lemma C.9. Define (TrV)(,)) = ( + (PrV) - for any V E RRS Note मं Qne Vn are (T
defined in Algorithm and denote (n(s,a)
(s a). Then it holds that
H
#
V (s) (i(s)
E. [En (sh. an) 11 = s]
Σ
Ex [En (sh, an) s1 = =s] (26)
A=1
Furthermore, (26) holds for all Vi (s) VR (s).
20

---

Proof of Lemma C.9. Lemma C.9 is a direct corollary of Lemma E.8 with π x², Q = Qn V. Vn and मे Ωt in Algorithm 1, we obtain this result since by the definition of म in Algorithm 1, (2n (sh, ,,, ma (-Isn) - tr (-1sa)) S O. The proof for V (s) (s) is identical. O
Next we prove the asymmetric bound for Ek, which is the key to the proof.
Lemma C.10 (Private version of Lemma D.6 in [Yin and Wang. 2021b]). Denote En(s, a) (TA Wh4))) a) - (s a), where Vn+1 and Qn, are the quantities in Algorithm and (v(V) == Th Ph V for any V R Then under the high probability events in Lemma C.3 and Lemma C.6. for any h, $b: On such that on > >3Ep. we have
0 (shn an)
(Th VhnVi+>)ss on) (sh an)
2 Var Pa(-lennon) (V)++(-)) 32SH
oen.on Ep
nan
where: log( log(HSA/8).
Proof of Lemma C.10. The first inequality: We first prove En. (3h, an) 2 for all (sh, an), such that
Mag.an 2 pEp
Indeed, if QR (sh, an) < 0, then (s an) an) (note Vn 2 by the definition). If ( an) 2 0, then by definition 2n (sh, an) = min @inn@ an), H h 11+ < 2% an) and this implies
O. In this case, (su, an) ( (sh, an) 2
(sh, an) Z (Th V an) - (R(s, an)
-(P - Ph)) ( an) (sns,,
2Vr (. (V)+1()))
16SHE,
(8h5 = 0,
E'p
Tia
where the second inequality uses Lemma C.6, and the last equation uses Line of Algorithm 1.
The second inequality: Then we prove (n(s,, on) I 2
2Va Palllen .n, ) (-))
328H for
Rogion E.p
nog
all (s); ax) such that Max.as 2 3Ep
First, since by construction Vn x H - h for all h [H], this implies
Φh = Qn - In s Q = r + (Ph Vi+1) s 1 + (If - = -
which is because Th and Ph is probability distribution. Therefore, we have the equivalent definition
O min 0 11 + 11+ max( 2 0%
Then it holds that
En an) (Th Vs an) (n an) S (Th an) Q (sh, an)
= =(Th Vh+1))s) an) - (s and + In an)
-(Ph- - -Ph) Vn+1 (sn, an) + (nhssha
Var Pa (-len.an ) (Vn+1 (+))
16SH + T (Sh,
Tes - Ep
Ten
Var Pr. (- (vn+1()) .1 32SHE,
=2
Nss .n Ep
The proof is complete by combining the two parts.
21

---

C.3.3 Reduction to augmented absorbing MDP
Before we prove the theorem, we need to construct an augmented absorbing MDP to bridge V and V. According to Line 5 in Algorithm 1, the locations with as S Fi is heavily penalized with penalty of order (H). Therefore we can prove that under the high probability event Remark C.8, di (s), a.) 0 only if (5), a4) > by induction, where
the output of Algorithm The conclusion holds for 1. Assume holds for some h > 1 that (sh, an) > 0 only ( an) > 0, then for any 8h+1 E S such that di (8h+1) > O, holds that d (8h+1) > 0, which leads to the conclusion that di (3h+1, 04+11 > 0 only if d++1 (5h+1, ah+1) > 0. To summarize, we have
dh (sh, an) > only if (s) an) > 0, To E { 7).
(27)
Let us define Mt by adding one absorbing state s) for all h E f2...., . H). therefore the augmented state space St = s u { and the transition and reward is defined as follows: (recall C.. == {(sh, an) (sn, an) > 0})
P 8h; sh;ap) an)
1
Sh. E Ch: Pa(.- sh. an.)
Sh s) or sh, an & Ch, rl(sn; = { (s(s an)
Sh, an E
64g
= s) or sh. & Cs.
and we further define for any n,
H
(5)
Et
r
9h
Et
r!
wh E [H],
(28)
where Et means taking expectation under the absorbing MDP M Note that because n² and ãे fully covered by p (27), it holds that
y 1/ = -x' v1 x
(29)
Define (T, == r + (P) for any RS+1, Note ã, Q₁ V, are defined in Algorithm (we extend the definition by letting (s()) 0 and (s),)) 0) and denote (s)) (T. VT. a) as) Using identical proof to Lemma C.9, we have
V/-" (8) (s) S Σ B (ch(sn an) |s =
Σ A=1
(s), an) 181 =s1= (30) Et
where 81 is defined in (28). Furthermore, (30) holds for all Vy (s)- -V, V1((ss).
C.3.4 Finalize our result with non-private statistics
For those (sh, on) E Ch. (s,, an) = (sh, an) + Py (h an) - (sh, an) = (sh az). For those (5h, an) & Cn sh s/ we have (s on) 0.
22

---

Therefore, by (30) and Lemma C.10, under the high probability events in Lemma C.3, Lemma C.6 and Lemma C.7, we have for all & E [H]. S (S does not include the absorbing state s)),
H
H Σ
1ata (8) V
E
(sh, an) 81 =
Tet R
St
(Sh, an) 88 =
h=t
H
<
E
(sh, and 1t = -0
hmm
H
2ar (.(-lan,a)) (Vi+1())) 32SH -6
B1
21
8t
11 (n) E Cn.
a
Exp
h=t
F1
Var Pr, (llsn, .n) (V++1())
B2
(31)
E
2
an -2Ep
Ep
=
1 ((sh, ap) E Cn)
h=t
H
Var Varpa Pa on) (Va+1()))
128SH
E
4
+
81
((hh,a)) E Cx)
1 na
3ng
hmt
H
2 2 Var an (Vi+z()))
256SH -
< h=t
4
8: =
1l ((sn, an) E Ca.
ndl (sh, an)
3rd (sh, an)
The second and third inequality are because of Lemma C.10, Remark C.8 and the the fact that either <t or t = while (8p, as. E Cn. The forth inequality is due to Lemma C.3. The fifth inequality is because of Remark C.8. The last inequality is by Lemma C.7.
Below present crude bound of Vat=" (s) - Vi( which can be further used to bound the main term in the main result.
Lemma C.11 (Self-bounding, private version of Lemma D.7 in [Yin and Wang, 2021b]). Under the high probability events in Lemmaa C.3, Lemma C.6 and Lemma C.7, it holds that for all E [H] and s E S,
Vtt (s) - Vi(s)) S 4v21H²
256SH²
Vn dm
3n dm
where dm is defined in Theorem 3.4.
Proof of Lemma C.I1. According to (31), since Var (elen.on)) (Vn+1()) S H², we have for all
t e [H].
4 4/21H² 256SH²Ep
Vt t (8) 19t2(s) <
(32)
v n dm
3n dm
Next, apply Lemma E.7 by setting क म _' = n., Q = Q. V
V under M then we have
H
V.TT (8)- Vi(s))
Σ
B (s and | = +
E [ (sh, ), o (.18%) 2n (+18k)) = s]
h=t
h=
Bt_ (t((s,, an) 1
4 2
256SH2F,
n dm
3n dm
(33)
23

---

Also, apply Lemma E.7 by setting π = = ., - -QQ. = V uudde Mt, then we have
=
H
(i(5)
18 (8) = Σ
an) 18 = =6 s 0.
(34)
h=t
The proof is complete by combing (32), (33) and (34).
Now we are ready to bound V Var (1sa.aa) ( by v Varpaaaeea.a (V (.)). Under the high probability events in Lemma C.3, Lemma C.6 and Lemma C.7, with probability 1 1 8, it holds that for all (Sh, an) E Cu.
Var an (Vo+(()) S V Var Pallsaa .n)
(V 1+1 (-)) + 1itt
Vtt h+1
00
2v
256SH2Fr Pp
Var an (+))
v n dm
3n dd
2
256SH Ep
SE
Var Ballanan) (Vi7
+ 4H
Vn.da dm
3n dm
Ranias
(35)
2.
256 Epp
SF.
Var Var (.)) +
+ +
Vn- dm
3n dm
n. dm
22
256S
SEp
+ 8H
+ 3H
Vn. dm
3n dm
n. dm
V n dm
9
256SH + 8H
SEp n nd
(V
Vn- .d
3n dm
The second inequality is because of Lemma C. The third inequality is due Lemma C.5. The forth inequality comes from Lemma C.3 and Remark C.8. The fifth inequality holds with probability 1 8 because of Lemma E.5 and union bound.
Finally, by plugging (35) into (31) and averaging over $1, we finally have with probability 1 -48,
2 ir (1s,,a)))) (Vn+i(-))
256SH
8
v
Bt
$1
nal (sk, and
3nd (sh, (sh, ah)
Varra an) (v (-)) - ndlh (8h (h)
+0 H + SH
<4v2
ni dm
/m1
(36)
H
Varpuclen.as) (V (1)+(-).
+0 (
H SH
2
di. (sh, (sp.an)
(sp, an.)
.d
==1 JECs
Var (Viti nal (sh, an.
(H3 SH
-4
Σ
di ash
+0 n dn
Amm (Sp,0a) JEC,
where Ô absorbs constants and Polylog terms. The first equation is due to (29). The first inequality is because of (31). The second inequality comes from (35) and our assumption that n dm 2 Ci H². The second equation equation is because for any (Sh, an. sh+1) such that d (sn, an) 0 and (s (sh as)
the fact that d% (sh, an) d. (sh, an), for all an). The last
v/l+ (8h-1) Vi+z1
C.4 Put everything together
Combining Lemma C.I and (36), the proof of Theorem 3.4 is complete.
24

---

D Proof of Theorem 4.1
D.I Proof sketch
Since the whole proof for privacy guarantee not very complex, we present it in Section D.2 below and only sketch the proof for suboptimality bound.
First of all, by extended value difference (Lemma E.7 and E.8), we can convert bounding the subopti- mality gap of
to bounding Σ Ex (T' an)]. given that (Tx VA+1 Th (h+1)(sss - T (s, a) for all h. To bound (Tx V++1 Th (8, a), according to our analysis about the upper bound of the noises add, decompose (Th Vh++ -Th (s,))) a) to lower order terms
(0(x) and the following key quantity:
K
p(s, a) A
1
Σ
oh)
(5 o (rh Vata (sh+z) (ThVint)) (sh. (o)(5)
(37)
For the term above, we prove an upper bound of 10 07
so we can convert o to oz Vati"
we can apply Bern- stein's inequality for self normalzzdl martingale (Lemmaa E.10) as in Yin et al. [2022] for deriving tighter bound.
Next, since Var rx Vh+1 (5%+1) (TrVi+t)) (5%, ()) 8/ ob
~ of 11
Finally, we replace the private statistics by non-private ones. More specifically, convert of
th 2 (Ap to A by combining the crude upper bound of [ v* and matrix concentrations.
D.2 Proof of the privacy guarantee
The privacy guarantee of DP-VAPVI (Algorithm 2) is summarized by Lemma D.1 below.
Lemma D.1 (Privacy analysis of DP-VAPVI (Algorithm 2)). DP-VAPVI (Algorithm 2) satisfies p-zCDP.
Proof of Lemma D.I. For Σ 655), (7)) Va+i (5 the l2 sensitivity is 2H2 For Σ (33 a.) (x and Σ ø (5% a7))) (r% + Vn+1 (5%+1) o aj)) the 62 sen- sitivity is 2H. Therefore according to Lemma 2.7, the use of Gaussian Mechanism (the additional noises Φ1, Φ2, Φs) ensures Po-zCDP for each counter. For Σ 68%, (75 a,) + A and ΣK ø (5%, a.) @ (s7, a ( ag.)) + AI, according Appendix D in [Redberg and Wang. 2021], the per-instance l sensitivity is
|| 112
sup
1000 T
||
sup
Σ 1.
/2
de #
V2 o:1l 11
V2
Therefore the use of Gaussian Mechanism (the additional noises K1, K2) also ensures po-2CDP for each counter." 12 Combining these results, according to Lemma E. 17, the whole algorithm satisfies 5H p-zCDP.
D.3 Proof of the sub-optimality bound
D.3.1 Utility analysis and some preparation
We begin with the following high probability bound the noises we add.
For more detailed explanation, refer the readers Appendix D of [Redberg and Wang, 2021].
25

---

stdd logl 1054) log( 1 = 2H
Lemma D.2 (Utility analysis). Let L = 2H
and
Pa
P
$
E 2d 2
(og( H/8) o2d
10Hr
2 + [og( H16) O2d
for some universal constants
Pa
C1, Then with probability 1 8, the following inequalities hold simultaneously:
For all E [M), | HT,, 1/b2l12 I, 1|bal12 L.. For all E [H), K1, K2 are synmetric and positive definite and K; - E, i {1,2]. (38)
Proof of Lemma D.2. The second line (38) results from Lemma 19 in [Redberg and Wang, 2021] and Weyl's Inequality. The first line of (38) directly results from the concentration inequality for Guassian distribution and a union bound.
Define the Bellman update error (n a) == (Ta (T) (s a) and recall (*) = argmax,, xn. (Q) () (. (.1 8)) then because of Lemma E.8,
H1
(5"(s) vf
Σ h=1
En (sh an) 51 s] - Σ Ea (sh, s1 s]. A=1
(39)
Define 1 ) Wh. Then similar to Lemma C.10, we have the following lemma showing that in order to bound the sub-optimality, it is sufficient to bound the pessimistic penalty.
Lemma D.3 (Lemma C.I in [Yin et al., 2022]). Suppose with probability 1 5, it holds for all s. E S x A x [M]] that [(T% V Tn (s)++) a)l I Tn(s, a), then it implies Vs, a h S S Ax 0 (a(s, a) < (s, Furthermore, with probability 1 - 8, it holds for any policy simultaneously,
VT(s) - (T(
Σ 2. E. (T(h,, s]. h=1
Proof of Lemma D.3. We first show given (Th VT. h+1 (V) Tu(s,a), then 0 s (1(8, a) < 2T, a), Vs,a, a E S x A x [H].
Step 1: The first step is to show 0 < Cn a), Vs, a, E [M].
Indeed, if (s, a) < 0, then by definition
a) 0 and therefore (s, == (s)
as = (Th (n1 2 (n, > then (n a) S (s, and
(n(s,a) -Th (Th Qn (Th () -Q((()))
(Th ()) aa) 0.
Step 2:
The second step show Ço (8. a) < (s, A
Ax [H].
Under the assumption that (Tx Vn+1 To V/ < have
Qn(s, = (Th v1)) (x < (TAVA+1)s,,)) S h +1, which implies that (x. () max (ax(QQ Therefore, holds that
(n(s, a) == - -Q)(s - (s) (1. (1,4))++(((npp S (2,x((,))
(x(s,))
-(ThVn+1)
For the last statement, denote 3 = (0 < (a(s,a) a) < 2T,(s,,), Vs E x []]] Note conditional on then by (39), (s) (s) < _ 2 E, (n an) | holds for any
26

---

policy т almost surely. Therefore,
P VTT - S
Σ
2
Ex (s), |8 =s].
h=1
H
VT, (s)(s) (s) -
Σ
2 E (Thh,, an) |s1 =
[P(3]
h=1
+P
VT, (T((s) (V())) &
Σ
2 E. [T ( 0n)
|81 = 8 IP(
h=1
>P
VT. (s) Ví - Σ
2 E. (T onh
|s =
[P 1 1
which finishes the proof.
D.3.2 Bound the pessimistic penalty
By Lemma D.3, it remains bound corresponding to the Th Vn+1 (such wy exists by Lemma E. 14), iee Ta Vn+11 = o" TTw,, (TrVi)))(ssa) a) = +0s a) Wh. then:
Vn+ (s, a)). Suppose wn. is the coefficient who and recall
(Th Vitttt)) (s) (TnVitt)
(s, a(s,aa (wn wp.)
= a)] wh - ()
Σ Φ (T) (r% + Vh+i (8%+1) 10 a7) + 03
K
6(8,0) T wh a( A
Σ ② (sho a7) (1% + Vn+i (sh+z) 15% ah
- Φ(s,a) A 2s + a) ((AT A)
Σ δ (5h an) (1h Vota (sh+1) /oh ah) + 0s
(ii)
(ii)
(40)
where A, = An K₂ = EK (8h, af d of) (oo( + AT.
Term (ii) can be handled by the following Lemma D.4
Lemma D.4. Recall in Assumption 2.2. Under the high probability event in Lemmaa D.2, suppose
K 2 max 312H4 288)
12H² then with probability - 8. for all h E S x Ax x [H], it
holds that
4H²L/K
((s, a) T 1 <
K
Proof of Lemma D.4. Define NY = Enn 2s, a)o(s, a)o(s, a) 2.2 and T H, it holds that Amin (AP) H2. Therefore, due to Lemma E.13, have with
a)T} J. Then because of Assumption
27

---

probability 1 1-6. 8,
((8, a) tot s 1 10(s,))ll,, ") I
4
10(s, (((s)))l((pp> |05)1(80))
K
AL
((AA))
K
4H L/K
K
The first inequality is because of Cauchy-Schward inequality. The second inequality holds with probability 5 due to Lemma E.13 and a union bound. The third inequality holds because Va Ta.. AA a < /|aalla A = ||a||2 / The last inequality arises from [I(A)) =
Amax ((A ((A)) Amiu (A E H²
The difference between A7= and Az7 can be bounded by the following Lemma D.5
128H log 24H
Lemma D.5. Under the high probability event in Lemma D.2, suppose K 2 probability 1 - 6, for all h E [H), it holds that |A A I
then with
4H Esx²
K²
Proof of Lemma D.5. First of all, we have
|& T 1| = || (An An) A
A || ||Ån AAll -|A
(41)
min (Ax) Amh (Ax) ) E.
The first inequality is because ||A B| S |||||| |BB|. The second inequality is due to Lemma D.2.
Let N4. Ar. then because of Lemma 12, with probability 1 8, it holds that for all h E [H]
M Emnll(s, a))(s,) a) [s)
la
<
4v2 K
log
2dH
1/2
K
5
which implies that when K > 12811 log 248
it holds that (according to Weyl's Inequality)
Amin (Nr) 2 Amin (E (0l, a)o(s, a) / a)))
K 2H 2
2H
Under this high probability event, have Amin (Aa) 2
Kx 2
and therefore Amin (An) \ 2 Ami Amin
Kx. Plugging these two results into (41), we have
2H
E/K2
A
Ko <
K2
Then we can bound term (iii) by the following Lemma D.6
Lemma D.6. Suppose K 2 max{ 128H log 24h1
yBL }. under the high probability events in S Ax [H].
x²
Lemma D.2 and Lemma D.S, it holds that for all
K
t (sh, ah) (1% Then (ft+1) (5% ah) + +05) )
4/2H* E Evd/23/2
((s,a)) T(A - 1,,'))
Σ
K
Proof of Lemma D.6. First of all, the left hand side is bounded by
K
δ (sh am) (rh + Vn+a (sh+1) (5h. )
4H AHA/R
(7 )²²))
Σ
K²
28

---

due to Lemma D.5. Then the left hand side can be further bounded by
4H EL/K²
H
(A h Nx ) (5h o (oh
2
K²
K
- Tr (A - A $ (5% 0%)) @ (5% (%))
(A 1 A,:1)
-A,')
4H FT///
+
(5% 07)
K²
V .T (Ar71 - -イ))));)) Rn (A - xn-)) AH+EL/R2
SH
K²
Kd Amax (Am² - A7 An (A - -(,1))
4H F.L. k2
SH
+
K²
V Kd. |( (A k) An (Ax² - و,,t +
4H/K
-H
K2
Kd. | 1. -| - An |1 Inn - Az
-
4H EL/K²
S11
+
K2
2 2/2H*E EVd/k3/2
4H*EL/12
K²
EVd/312 K
The first inequality is because |all, VaTa VTr(aaT). The second inequality is due to Gauchy-Schward inequality. The third inequality is because for positive definite matrix A, it holds that Tr(A) = D E (A) S dDmaxx The equation is because for symmetric, positive definite matrix A, ||
Amas(()), The forth inequality is due to || Bl S ||| B]] The fifth
inequality is because of Lemma D.2, Lemma D.5 and the statement in the proof of Lemma D.5 that
Amii (Ax) 2
Kx 2H
The last inequality uses the assumption that K /2L
ddx."
Now the remaining part is term (i), we have
K
(ssaa)J wh -((ss a) T,
Σ
④ (s ah) (1h + Vnta (sh+1) (oi(sh. 07)
((s,a) wp o(s,a) A,
Σ ④ (sh ahh (Th /o a
(iv)
K
- ((8,0) T
An
Σ
Φ (5h ap)
(rh Vn+1 (5h+1) - (ThVitt) (sh, 05) /07 a7)
(v)
(42)
We are able to bound term (iv) by the following Lemma D.7.
Lemma D.7. Recall in Assumption 2.2. Under the high probability event in Lemma D.2, suppose
K 2 max 612H* log 2nd
1AH²
then with probability - for all s, e Ax [H),
8AH* Vd/K
a) ([s,a)Tw, wn - ((
Σ 2 (5h 0%) (Th (nai (5h (6000/20000000 5 K
29

---

Proof of Lemma D.7. Recall TA Vh+1 = 6Tw,, w/ and apply Lemma E.13, we obtain with probability 1- 6, for all s, a. S A x H].
K
(Th (sh, ah) 1o6 ar) |
wh a() Tn 0(s,a) (dss,)AA Am
Σ
④ (s/, ah)
o(s,a) wh a(s,a)
Σ ah)) ((sh: www/// (5h ohh
a(s.a) wh ((s, "
(An -A1)
wh
A (0)((, a) 7n"W ww
SA l0(s, a) ">"" ||wallā='
4A
|1 a) (1))) 1. =-Iwall(33)>
K
4X
2H Vd ||(2)-11
K
SAH
Vd/K
K
where N3 == Enthh (s. a)--a)--3200 "0(s, ())(s, a) J. The first inequality applies Cauchy- Schwarz in- equality. The second inequality holds with probability 1 - 5 due to Lemma E.13 and union bound. The third inequality uses Va AA 2 || 2 |all2 = ||a||2 v||Al12 and ||wx||| < 2H Vd. Fi- nally, Amin (AR)
H² maXi...a (s,a 2 # implies (Ap)- s xx
the last incquality holds. O
For term (v), denote: dt then by Cauchy-Schie Schwarz inequality, it holds that for all h, s, E [H] x S x A,
1/- = rr + Vh+1 (sh+1) - (Th Vn+
(0h (h)) /ān o7).
a. (sf "
(rh + Vh+t (5h+1) - (hhtit)) (sh, (5) (0% añ) )
a( TAn'
Σ à (5)
K
S V a(ss A a(s
Σ
Iz Drr
(43)
We bound v as) Ant ((,,a) by Vos T) (0, a) using the following Lemma D.8. Lemma D.8. Suppose K max 128H log 2014
VEL b. under the high probability events in
Van
Lemma D.2 and Lemma D.5, holds that for all s, a, h h S Ax [H)
2H VE/K
Vo(s,a) &n o(s,a) s Vo(s,a) (
d(s,a)+
K
Proof of Lemma D.8.
V ((T, ()) v //((, a) T A (6 + (A -77))((00)) a)
s ()s,,) ( a)) + | - -An²
(44)
S [v((s,)) (
/ || Tn 2
211 VE/K
S\ /vo(s N 1
K
30

---

The first inequality uses la Aa I |aal ||A||- The second inequality is because for a, 2 0. Va + vb 2 Va b. The last inequality uses Lemma D.5.
Remark D.9. Similarly, under the same assumption in Lemina D.8, we also have for all a, h S A x [H].
V ((s,)) 2H'VE/E
Vo( ( o(s,a) s
K
D.3.3 An intermediate result: bounding the variance
- 2. nol1 we first bound sup, oo o2 of by the following
Before we handle
Lemma D.10.
Lemma D.10 (Private version of Lemma C.7 in [Yin 2022]). Recall the definition of of (:
max Vara Vx+1(-,-)} in Algorithu where [Vara V.+i](.))) = ()(:.)) (. (o.... (o.1)-
((((-)),0)) (a,t (3p and On defined in Algorithm 2) and Vuta (1,))
max (1, Varr, Vn+1(,))) Suppose K 2 max
512log( 2514
4A
log 24H
2LL
and K >
N²
H
max 1 PR
11a 32 16x² Px
}, under the high probability event in Lemma D.2, holds that with proba-
bility 1 -- 60,
H&d
(A + K)2KdH2
soploo Votn 11
<36V
log
sK
A8
Proof of Lemma D.10. Step 1: The first step is to show for all h, s, E 1 35,
[H] X x A, with probability
H
(A + K)2KdH²
(0(8, a), 32) [ Pr, (V S 12
log
RK
Ad
Proof of Step We can bound the left hand side by the following decomposition:
(b(s, a), (n) (0.0H---11) PA (VA41))) a) $ (0(s, PA (Va+s)))
a(s,a) Ein"
Σ O1)
Pi. (5h+1) + di - PP (s)
K
0) 5m
Σ
665 ob)) (
((s,a) (.,
(1)
((, (Sin - )
(65 and
Vnti(Shez) oz
(9)
where En En K1 ΣK K
668 (OT Tn) AI.
Similar to the proof in Lemma D.5, when K > max ity - 5, for all h E [H].
128 log 24H
JLL }. it holds that with probabil- H
KK Amin (Eh)
KK
4E/K2
Amin (Ex)
5-
K2
(The only difference to Lemma D.5 is here Ep, (o(s s, ())(s, a) 1 K.)
Under this high probability event, for term (2), it holds that for all h, E [H] x S x A,
2H 2H
(o(s.a) ( - s [lo(s, a)ll || || & X HL <
(45)
K
31

---

For term (3), similar to Lemma D.6, we have for all h, s, [H] x S A.
4v 4v E d/
as t
ah) 1 151)
(46)
K
(The only difference to Lemma D.6 is that here (8)2 S 112 11b111111 S HL,
E0 1|
S
2 and K
N -
1E/K2 R
We further decompose term (I) as below.
K
(1) = ((s,a) Σn
Σ
6(3% ah) (5+1())+1)2)
k
K
ø(s, a) "in 1
Σ
V ((5, (2aa))/ 7
213 a o oh) + +1) /
==1
1=1
< a() [5x]
2
Σ
(5 aT)
(Vi+1(5h4112
PA (A (5h. (R)
+ (a(s,a)T5))) /
(4)
(5)
(47)
For term (5), because K 2 max
512log
28d
11
by Lemma E.13 and a union bound, with
probability 1 - 5, for all h, a H x A
2 A(0, a) E--1 _ / (Vitz) s (All((s,))l55
1/800 (S
5:-1
<\ 2
2
1 (ont))
H2
H2
10(s |))
4A
VK
VK
kK
(2%))-
(48)
where Σ E E a))(s, and Amin ( 2 K.
For term (4), can be bounded by the following inequality (because of Cauchy-Schwarz inequality).
K
(4) $ (10(s,0))ls=-
Σ
55 07. (Vn+1(th+1) (V ( (h)
(49)
Bounding using covering. Note for any fix Vh+ we can define x, = (53 ag) (løl12 Σ 1) and
? = ( - PA (V aj)) is H² -ssbauussia,, by Lemma E.9 (where t = K and 1), it holds that with probability -.
Σ 65h ab) (Vo41(5h+1) Pa
$ 88
d log
(
2
A5
Let Ne(e) be the minimal c-cover (with respect to the supremum norm) of Vn= Vn: Vn(+)) max (min(((ss
Civa o( TT T ((())) C2 H- h -
That is. for any V E Va. there exists a value function V E Ni(e)) such that sup.es (V(s) - v'(s)] < e. Now by union bound, we obtain with probability 1-
sup
655 ah) (V4+1(5)+1) Pa ( Σ
K
< $1
8814
d
log
(x+ K
WN++
(1)
2
A8
32

---

which implies
K Σ
(3/ 0h)
(Vit1(5h+113 - -Pa((Vh+1) ( ahh)
d
(X+
Wanr(el) + 4H2 VEK2/X
8/14
log
2
choosing dvA/K, K, applying Lemma B.3 of [Jin et al., 2021] 13 to the covering number Na (e) w.r.t. V4+1, we can further bound above by
8H4 d3
A+ K A8
(>+
S
log
2dHK) + AH s < H d3 1og
2dHK
Ad
Apply a union bound for h E [H]] we have with probability for all h [H].
K
(A+ K)2KdH²
Σ ol% aT) (Vi+2(5)+11)
1 /
H
A8
(50)
and similar to term (2), it holds that for all h, 8, a E [
x S x A.
2
(1((s, )) S
S V rK
(51)
Combining (45), (46), (47), (48), (49), (50), (51) and the assumption that K
2
max
( H dxk
41,"
32F
16A"
), obtain with probability 1 36 for all h 8, E [H] S x A.
1
(A + K)2K d1H
a), (,) - -
S 12
log
kK
Step 2: The second step is to show for all h, s,
[H]
x A, with probability 1 35,
H2
(A K)2KdH²
()(s,a), a), a)) Pa (V
< 12
log
(52)
RK
A6
The proof of Step 2 nearly identical to Step
except V2 is replaced by Vn.
Step 3: The last step to prove sup,llö? - Vi 1ll0 S 3 probability.
#4d3
log
()+ 25
with high
kk
Proof of Step 3. By (52),
[[)(:)),, 0n) 0. - 1 - [Fx (V (s, a))²
(o(s, 0n) 0n) PA PP a) (66(s, a)(s,)), 0),00),.,,))11)) -P. (s,
Hdd
(A KJ)KK) dH2
<2H1 (0(s,a), -
(V)+ a)
24
log
kK
A8
Combining this with Step we have with probability 1
68, Vh, s,
[H] x x A.
Had
(A+ K)2KdH²
Vara Vieti (s, a) Varp, Va (8, a) S 36
log
kK
A8
Finally, by the non-expansiveness of operator max (1, .. the proof is complete.
Note that the conclusion in [Jin et al., 2021] hold here though have extra constant C2.
33

---

D.3.4 Validity of our pessimism
Recall the definition A, Σx= ( ( ( o7)
(0 aA) + A and
An Σx (1% (5) at) /0 Pati (oh,a)) X., Then we have the following lemma bound the term (((s,a) TA, o(s, a) by /0(s, a) ((s,a). (s,
Lemma D.11 (Private version of lemma C.3 in [Yin et al., 2022]), Denote the quantities C1 max (2X, 128 /2dHH))/8), 128H/ log(2dtr//) and C2 6 /w²). Suppose the number of episode K satisfies K > m events in Lemma D.2 and Lemma D.10, it holds that with probability 25, for all h, 8, a [H] x S X A.
1C }2} and the condition in Lemma D.10, under the high probability
V (( 6(s,a) s 2 o(s A á(s,a).
Proof of Lemma D.II. By definition
/ (((,,a)T, 1 ((1 11((,, a) 1))
Then denote
Mg - Ap= = 1-RAn An:
1
where A₁ - 0(8 (06 T7/T/0 Vnts
Un+1 (5) + AI. Under the assumption of K, by the
conclusion in Lemma D.10, we have
((s,))((saa)
((s.a) (5,a)
A/
1/
1 sup
(s, a)
Vas
(8, 0)
1h11 (8,a)
||o(s, a)l?
sup 8,0
(s, 0 ( a)
V1+1 (s,a)
(53)
(s, a)
(8,a)
Vhi1
< sup 8,0
1
H
+A+ + K)2Kd112
<36
log
krK'
A6
Next by Lemma E.12 (with & to be é/ S/O and therefore C' = 1) and a union bound, it holds with probability 1 5, for all h [H].
N/1 (En.Ales, a))(s, T /0
4 VK
2dH
1/2
Vn+t (s.
K La
log
Therefore by Weyl's inequality and the assumption that K satisfies that ), the above inequality leads to A
K max(2X, 128 log(2dH/5), 128H log(2dH/8)
4 2
2dH
1/2
[|A Amax((()))) S Amax (Funl a) /02 Vo_ (8,
+
log
K
VK
4
2dH
1/2
= =|Eunl0(s, a) Vo (8, a))
+ K
log
2
VK
4v2
2dH
1/2
A
4
2dH
1/2
s 1|
log
<
1
log
S 2,
VK
K
VK
4
2dH
1/2
Amin (1/) 2 Amin
(Fnnl((s a)T /02 /
Voti (s,
+
log
K
VK
2
2dH
1/2
2
Amin (a,.lo((,,)o(s. a) /0 Vnss (s,
log
VK
4/2
2dH
1/2
k
>
log
H
VK
2H²
34

---

Hence with probability 1 6, || < 2 and
| = X (A S 2 -iiilarly,, one can show
A
2H with probability - 8 using identical proof.
Now apply Lemma E.11 and a union bound to N,, and A, we obtain with probability for all 8, E H) x S x A,
[lo(s, ()(s,))]xx) 5
+
| ||
[
-|
1|o(s, a))s,)
2H2
2H2
| Mill
<
+
2
-|0(s, A)"ااr
K
K
288
Hdds log
(A + K)2Kd1t)
n2
KK
1216668,0)11
2
where the third inequality uses (53) and the last inequality uses K > 0(H22d /=²)). Note the conclusion can be derived directly by the above inequality multiplying 1/vK K on both sides. O
In order to bound || - E+dl x,,. we apply the following Lemma D.12.
Lemma D.12 (Lemma C.4 in [Yin et al., 2022]). Recall I, ((22.0%) (n)
and /ōn(sh o7). Denote
Mr (TT + Vh+1 (sh+1) (Th (Th (5%, o7))
Fh + VV) (T,V)
{ :
sup VE(O,HH, P.(a)) NE[H]
ov(s,
Suppose K 2 k(H)4 then with probability 1 1- 8,
K
Σ
s Ō max { (vd.e))
xe
Th
A
where Ô absorbs constants and Polylog terms.
Now ready prove the following key lemma, which gives high probability bound for (TrV - Tn (1++))sss,))
Lemma D.13. Assume K Ma. M3, Ma). for any < < K, suppose Vd &. ((+
where = =supvelo. M) s'Pa(s,,), NEiM]
Then with probability 1 8, for all
(v.8))
8, E [ x S x A.
To VV. sō =v(vaoolss))
p(s a) A5-'0(s00) + D
(Tn Vn+1
K
where Nn = =KK 6(87, oo5 NOT (7)) -I K2
Đ=Ō H2 H'EVd Vd+
H2 Ed
H
H'EVd + HVVd)
=
K
k22
K
k3/2
and Ô absorbs constants and Polylog terms.
Note that here the assumption is stronger than the assumption in [Yin et al., 2022], therefore the conclusion of Lemma C.4 holds.
35

---

Proof of Lemma D.13. The proof is by combining (40), (42), Lemma D.4, Lemma D.6, Lemma D.7.
Lemma D.8, Lemma D.12 and union bound.
Remark D.14. Under the same assumption of Lemma D.13, because of Remark D.9 and Lemma D.11, we have with probability 1 6, for all h, s, [H] x A.
D
(Th V - Tiit Wō
<Vd 0(s, a) A
+
K
2D
<ō
Vd a( () An ((s,)s
+ K
(54)
2D
< 2v 0(s aoTT))A p(s.a) + K
Because D = 0 11 H² EVa Hava and Ô absorbs constant, will write below for simplicity:
(ThVi41- - 5ō o(s.)) (0/0)))))
Ar =(
D
+
(55)
K
D.3.5 Finalize the proof of the first part
We are ready to prove the first part of Theorem 4.1.
Theorem D.15 (First part of Theorem 4.1). Let K be the number of episodes. Suppose vd &, where
V (s')-(TT (x.aa) and K > max My M.}. (v.))))
& = supve e H), s'-PP,ssa), he[H]
Then for any < < K, with probability 1 - 8, for all policy a simultaneously, the output क of Algorithm 2 satisfies
Vd.
E
(o(s.) ()-))))))))))
+ DH
h=1
where AG - -(
+ Ala D = Ō H
(
H H' xa12 + H VV and Ô absorbs
of
constants and Polylog terms.
Proof of Theorem D.15. Combining Lemma D.3 and Remark D.14, we have with probability 1 8, for all policy x simultancously,
H
DH
(T
V (s) á
Vd.
Σ h=1
Ex
[
((.)))) 81
-
(56)
K
now the proof is complete by taking the initial distribution d1 both sides.
D.3.6 Finalize the proof of the second part
To prove the second part of Theorem 4.1, we begin with a crude bound on sup, V
V.
Lemma D.16 (Private version of Lemma C.8 in [Yin et al., 20221). Suppose K > max(M,, M3, under the high probability event in Lemma D.13, with probability at least 1 - 8,
H2 H2
sup Vi
Vn
VEK
Proof of Lemma D.16. Step 1: The first step is to show with probability at least 1 - 8,
sup, V V
s Ō
H² VeR
36

---

Indeed, combine Lemma D.3 and Lemma D.13, similar to the proof of Theorem D.15, we directly have with probability 6, for all policy x simultaneously, and for all E S, [H].
(s) V (s) S
Vil
Σ t=h
Ex
(, 1/2
8n
+
DH
(57)
K
512log 2Nd
Next, since K 2 max
11 by Lemma E.13 and union bound over h [H]. with
probability 1 1-6, 6,
2
2 VK
2H
sup 8,0
10 a)IlA
sup (ol(s ( S
A (AP) S
vh [H],
VK
VKK
s.
where NI. = lo 10 (s, (aa()sss) a))ss a) I1 and Amin (A 112.
Va+1
Lastly, taking क = x* (57) to obtain
05 V (8) (s) <ō
Vd Σ E
(o(,-) A, 12"
5n -5)
DH
K
(58)
H²
HO + HVE/d/a21 H'Vd
+0
VKK
K
This implies by using the condition K > max
n15² H²1²
HAR,, we finish the proof of Step 1.
de
x²
Step 2: The second step is to show with probability 6, supı
[/
V I 2
vKk
Indeed, applying Lemma E.7 with क n'' म. then with probability 5, for all s, h
(s) - Vi Σ ER @n and 10---TTii Vn+t)))) (sh, (s,,a)) sn =
11
Σ
(Th Mh+1 - Tn Tr V)
1=h
HVd A5 ) +
DH
<
K
H2Vd
VKK
where the second inequality uses Lemma D.13, Remark D.14 and the last inequality holds due to the same reason as Step
Step 3: The proof of the lemma is complete by combining Step I, Step 2, triangular inequality and union bound.
Then we can give high probability bound of sup,, I|o P -
Lemma D.17 (Private version of Lemma C.10 in [Yin et al., 2022]). Recall of Bun max 1I, Va Vn+1 } and o²22 max {1, Varp, Vitid. Suppose K 2 M2 then with probability 1 8,
H3
sup lopllo? Prns o 2ō
VKK
37

---

Proof of Lemma D.17. By definition and the non non-expansiveness of max(1, +,, we have
2
0
-
VarVu+1 Varl
11
20
1.2 - Vitti) )1
+ +I[(EnWa+t) (Py (PnVitt)
1< Ph
h-1
V/
+
(Ph + PP PPPaiit))(P VA+1 PA PPAV++)
2H
| Viit1
+111
Pn Vh+1 PA Vitta
HaVd
<
VKK
The second inequality is because of the definition of variance. The last inequality comes from Lemma D.16.
We transfer ((s A ass,a) to v a(s A ((s a) by the following Lemma D.18.
Lemma D.18 (Private version of Lemma C.11 in [Yin et al., 2022]). Suppose K 2 Ma, then with probability 6,
(() s a) M (s,a), ((s o
Proof of Lemma D.18. By definition
p(s a) ||o(s, a) AlA,, 1. Then denote / (0s A
A/. An.
A Al
where Ag = Σx= 6(8h, (7)())))s a / (5h,
+ AI. Under the condition of K, by
h
Lemma D.17, with probability 6, for all H).
(ss a))() T) (s,a))(s,a) T)
AA Nol S sup
(8,
E.n (8,
8.0
h 8, a) 02 Vn+* (s)a)
sup
|0((,
σ 8 a)
11 (8,0) a)
8
(59)
h 8, a)
2
o Vi+1
(s, a)
< sup
11
5,a
H3
VKK
Next by Lemma E.12 (with be Φ/avi,, and C = 1), it holds with probability
J - (Imnnl6(s. (s, +
R (s)
A
4
2dH
1/2
<
log
VK
8
38

---

Therefore by Weyl's inequality and the condition K max (2X, 128 log (2d the above inequality implies
128H log 2d 20)
A =Amax (Ax) Amax (EuAlo(s,a)j(s.u) a) /o (s,a)l)
A
4
2dH
1/2
+
+
log
K
VK
< Bu a)p(s, /ovr, (8,))
+
4v2
log
2dH
1/2
K
VK
A + +
4
2dH
1/2
4
2dH
1/2
- $1106,
log 8
11+
+
log
S
2,
K
VK
K
VK
8
4
2dH
1/2
Amin(A 2 Amin
[p,i ()),, a) T /o (s,a))
log
K
VK
6
4
2dH
> Amin
[p,ilo(s, a)d(s, a) T /o6 h+1
(s, (s,a)]
log
K
K
4
2dH
1/2
2 1
log
2
VK
8
2H
Hence with probability 1 6,
A
S and
A/1 - -
min (A 211². Similarly, we can show
that i
2H
holds with probability 1 - by using identical proof.
Now apply Lemma E.11 and a union bound to Ag and M/e we obtain with probability 1 - 5, for all h, s,a E [H] x S x A.
10(8,))llAN-1
V / 11 | 1 11
- -vll
2112
2H2
1
2.
K
16
H
H3va VKK
1+
1 ())as,
R
2
[ a) اللااy--
where the third inequality uses (59) and the last inequality uses K 2 'dH1e) The conclusion can be derived directly by the above inequality multiplying 1/VK K on both sides.
Finally, the second part of Theorem 4.1 can be proven by combining Theorem D.15 (with and Lemma D.18.
D.4 Put everything toghther
Combining Lemma D.1, Theorem D.15, and the discussion above, the proof of Theorem 4.1 is complete.
E
Assisting technical lemmas
Lemma E.1 (Multiplicative Chernoff bound [Chernoff et al., 1952]). Let X be a Binomial random variable with parameler p, For any 1 > 0 > 0, we have that
02 pm
and P 2 (1 0)pm] <e- 62
P[X < (1 pm <
Lemma E.2 (Hoeffding's 's Inequality [Sridharan, 2002]). Let Zı. Fn be independent bounded random variables such that B[r;] 0 and |2,]| < Es with probability 1. Then for any > 0 we have
m
2,2 2
P
24 2
1=1
39

---

Lemma E.3 (Bernstein's ' Inequality). Let 21...., 2n be independent bounded random variables such I & with probability 1. Let o² - Var[z,), then with probability
that [[z,] = 0 and |zy|
1 8 we have
1 72
20 log(1/8)
2
24
log(1/)).
n
3n
Lemma E,4 (Empirical Bernstein's Inequality [Maurer and Pontil, 2009]). Let #1,,., In be i.i. random variables such that |2.| S & with probability 1. Let 2 Ei= 24 and Vn, n "E 10= x)? then with probability 1 we have
27n log(2/6)
TE 3n
24 B[r]
+ log(2/6).
n2
n
Lemma E.5 (Lemmaa L8 in [Yin and Wang, 2021b]). Let 2 2 and V E R be any function with || H. P be any S-dimensional distribution and P be its empirical version using n. samples. Then with probability - 6,
V VVr - 11 Varr(V)
log (2/()
S 2H
n
n --1
Lemma E.6 (Claim 2 in [Vietri et al., 2020). Let y E IR be any positive real number. Then all x E with 2 2y, holds that z-y S
1/4 +
E.1 Extended Value Difference
Lemma E.7 (Extended Value Difference (Section B.1 [Cai et al., 2020])). Let ग = { and n' {
LH be two arbitrary policies and let (Q H fhmt be any given Q-functions. Then define (s) (s, mnl 6)) for all S. Then for all S
H Σ
vi((s) - VT (s)
Ex
(2n (8h, (s)s)) 2/h (-1 81 =
1=1
(60)
E [2 (82: an) - -TTi (ThVuet)) (s2, an) =
h=1
where (TrV),.) : + (PAV)..)) for any V E R.S.
Lemma E.8 (Lemma 1.10 in [Yin and Wang, 2021b]). Let (Tn) and Qn(:,)) be the arbitrary policy and Q-function and also Vs(s) = (Qn(s.)) )-ms() vs E S, and (s) = (Th VT41))) a) - Qn(s, a) wissey Then for any arbitrary n. we have
H
- (s)
Ey [En( an) =]=]
Σ
Es (Sn (sh, an)
181 = s]
H Ex (2n (8a, (sh, Th (+18n) - Tr. (-19%)) | 81
==
where the expectation are taken over Oh--
E.2
Assisting lemmas for linear MDP setting
Lemma E.9 (Hoeffding inequality for self-normalize martingales [Abbasi-Yadkorri Yadkori al., 201 ID.. Let (me )e i be a real-valued stochastic process. Let {Fi) be a filtration, such that is Ft- measurable, Assume Th also satisfies qt given F.-1 zero-mean and R-subgaussian, i.c.
AY H, EE AT Fr-1] < 22
40

---

Let { be an R -alued stochastic process where is Fi-1 measurable and || I L. Ler Ar Ala + Fg Then for any ô > O, with probability 1 8, for all t 0,
d log
A + tL
Σ &
S &R
2
Lemma E.10 (Bernstein inequality for self-normalized martingales [Zhou et al., 2021J). Let { he be stochastic process. Let {Fi) be a filtration, such that nt is F.-measurable. Assume Oo also satisfies
ml - R. E 1 Ft-1] = 0, E Wh Fe-1 S
Lef {2x 1i be -v-uuueed stochastic process where is Fz-1 measurable and ||aell S L. Let
A Ala E.=1 FzH.. Then for any 5 > 0, with probability 1 8, for all t 0,
LL2 Ad
412
(412
X.Ils
I 80
dlog
1+
llog
4R log
A
Lemma E.11 (Lemma H.4 in [Yin et al., 2022]). Let A and A2 E Rdxd be two positive semi-defiiie
matrices. Then:
|| || S A ||
||L
||
||A_ |1 ||- 1IA1I Azll
and
1 S 14 | ||42|| ||T ||A1 A2ll -101l,,"
for all Φ E Rd..
Lemma E.12 (Lemma H.4 in [Min et al., 2021J). Let á S A - Rd satisfies [lø(s, S for
all 8, 8,0 S x A. For any K > 0, X > define GK = =kEn p(sk, as (s(K, ax) + Mla where
(sk, 0k) 's are i.i.d samples from some distribution Then with probability 8.
GK K
Gk K
4V2C2
2d 1/2
E,
log
VK
8
Lemma E.13 (Lemma H.5 in [Min al.. 2021]). Let & S A Rd be a bounded function s.t. l S C. Define GK = Σ k= (8 ax (x))k ax) T Na where (sk, ax) 's are i.i.d samples from
some distribution v. Let = E (0(5, ()0(s, a) Then for any (0, 1), if K satisfies
K> max 512C |G | log σ
4A 1,4x||G ||
Then with probability at least 1 - 8, it holds simultaneously for all u E IRd that
2 VK |/u|l-11
|ullo S
Lemma E.14 (Lemma H.9 in [Yin et al., 2022]). For a linear MDP. for any 0 S V(.) S H, there exists a Wy E Rd s.t. Tv = (é, wp) and [|w,l2a & 2H dd for all E [H]. Here Tx (V) a) (n( a) + (Pr (s, a). Similarly, for any n, there exists wj, Rd, such that Q = (d) wx) with || 2 < 2(H h + 1)va.
E.3
Assisting lemmas for differential privacy
Lemma E.15 (Converting zCDP to DP [Bun and Steinke, 2016)). If M satisfies p-zCDP then M satisfies (p + 2 o)
Lemma E.16 (zCDP Composition [Bun and Steinke, 2016)). Let M u - y and M' :u - Z be randomized mechanisms. Suppose that M satisfies p-2CDP and M' satisfies I dCD.. Define M" n + x by (U) (M(U), M (U)) Then M" satisfies (p + CDPP
41

---

Lemma E.17 (Adaptive composition and Post processing of zCDP [Bun and Steinke, 2016]), Let M. x y and M' x y Z. Suppose M satisfies p-zCDP and M' satisfies p' d'-CDP (as a function of its first argument). Define M" : - Z by (x) = M2 M (x)). Then M satisfies (p- + D/DDP
Definition E.18 (L1 sensitivity). Define the & sensitivity of function f ::NA + Rd as [lf(U) f(U')ll
(1
sup
neighboring U,U"
Definition E.19 (Laplace Mechanism [Dwork et al., 2014]). Given any function f Nx IRd, the Laplace mechanism is defined as:
MI(x, f(x) +
where Y; are i.i.d. random variables drawn from
Lemma E.20 (Privacy guarantee of Laplace Mechanism [Dwork al., 2014]). The Laplace mecha- nism preserves (e, 0) O)-fifferential privacy. For simplicity, we say e-DP.
Details for the Evaluation part
In the Evaluation part, we apply a synthetic linear MDP that is similar [Min al., 2021, Yin et al., 2022] but with some modifications for our evaluation task. The linear MDP example we use consists of S]
states and |A| 100 actions, while the feature dimension d 10. We denote S = {0, 1} and A = {0, 1.... 99} respectively. For each action a E {0, 1,... 99), we obtain vector a E R via binary encoding. More specifically, each coordinate of a is either 0 or 1.
if = 0} 1a 0} then otherwise
First, we define the following indicator function 8(s,
our non-stationary linear MDP example can be characterized by the following parameters.
The feature map is:
((s,a) - " 5(s,aa) E 10
The unknown measure 1/ is:
2% (0) (0,... 04,1 04,2)
DA (1) (0.... ,0, 04,1; 04h,2),
where (an,1. 2 is sequence of random values sampled uniformly from [0, 1).
The unknown vector 0n is:
O₂ =
R
where Th is also sampled uniformly from [0. 1]. Therefore, the transition kernel follows Ps (s'(ss,, (ő(s, a), Ma (s')) and the expected reward function тı (s, a) = (ó(s, a), 0n).. Finally, the behavior policy is always choose action uniformly with probability (1 - p)/9 /99. Here we choose p = 0.6. The initial distribution is uniform distribution over {0. 1).
0 with probability p, and other actions
42


Reviews:
[{"review_id": "lujNvEPn5v", "reviewer": "Reviewer_2mbC", "summary": "This paper focuses on the offline RL problem with differential privacy. The authors propose algorithms for offline tabular MDP and offline linear MDP with $\\rho$-DP. For the first problem, the sub-optimality bound almost matches the best-existing non-private counter-part in spite of an additional term $O(\\sqrt{\\frac{1}{\\rho}})$. For the second problem, the gap between the proposed sub-optimality bound to the best existing non-private counter part is $\\mathrm{poly}(d,H,\\kappa^{-1})/\\sqrt{\\rho}$, where $\\kappa$ is the minimal coverage parameter. ", "questions": "1. For the non-privacy problem, does the error bound have a polynomial dependence on $\\kappa$ for the linear MDP problem?\n\n", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper firstly provides analysis for offline RL, and proposes error bounds which  matches the non-privacy counterparts up to some lower order terms.\n\n2. In technique, the authors  make efforts to operate on Bernstein type pessimism while keeping privacy to achieve the tighter sub-optimality bound.", "weaknesses": "1. The technique novelty is  somewhat limited given literature in online RL with DP.\n\n2. The discussion about related work is insufficient. In particular, I wonder what are the best existing regret bounds for online RL with DP (either tabular or linear MDPs)? If the regret bounds are not tight, could we use the Bernstein-style bonus with DP to improve the regret bounds?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your high-quality review and positive score. We will reply to the weaknesses you stated.\n\n**The technique novelty is somewhat limited given literature in online RL with DP.**\n\nWe politely disagree. It is true that current techniques for online RL with DP can be adapted to the offline case. However, the current works for the online case all focus on privatizing Hoeffding-type bonuses. Therefore, directly adapting current online techniques to the offline case will not provide tight sub-optimality bounds. In comparison, we operate on Bernstein-type pessimism, which is highly non-trivial. We manage to provide a confidence bound using private pessimism and lower order additional terms, prove its validity and bound this private Bernstein pessimism by its non-private counterpart in our final result. All such techniques are novel to our knowledge.\n\n**The discussion about related work is insufficient. In particular, I wonder what are the best existing regret bounds for online RL with DP (either tabular or linear MDPs)? If the regret bounds are not tight, could we use the Bernstein-style bonus with DP to improve the regret bounds?**\n\nWe discuss about the algorithms for online RL with joint DP (JDP) or local DP (LDP) in Appendix B. We did not discuss about the detailed regret bounds and kindly refer you to [1] for the results under tabular MDP and [2] for the results under linear MDP.\n\nUsing the Bernstein-style bonus with DP to improve the regret bounds is a very good point. Under tabular MDP, the best result ([3]) with Hoeffding-type bonus is $\\sqrt{SAH^3T}+$ additional cost due to DP, which is sub-optimal in the first term. Recently, following the idea of privatizing Bernstein-type bonus, a follow-up work ([1]) of this submission has improved the first term of the regret bound to $\\sqrt{SAH^2T}$ (minimax optimal) while keeping the additional cost due to DP unchanged. Under linear MDP, the best known result ([2]) is derived by privatizing Hoeffding-type bonus. It is an open problem whether the regret can be improved through Bernstein-type bonus and we believe it is a good future direction. \n\n[1] Dan Qiao and Yu-Xiang Wang. Near-Optimal Differentially Private Reinforcement Learning. AISTATS, 2023.\n\n[2] Dung Daniel Ngo, Giuseppe Vietri, Zhiwei Steven Wu. Improved Regret for Differentially Private Exploration in Linear MDP. ICML, 2022.\n\n[3] Sayak Ray Chowdhury and Xingyu Zhou. Differentially private regret minimization in episodic markov decision processes. arXiv preprint arXiv:2112.10599, 2021.\n\n**For the non-privacy problem, does the error bound have a polynomial dependence on $\\kappa$ for the linear MDP problem?**\n\nFor the non-privacy problem, the error bound does not have polynomial dependence on $\\kappa$. The main term in our bound is identical to the non-privacy case. The polynomial dependence on $\\kappa$ only happens on the lower order term and such dependence results from bounding the worst case difference between private and non-private statistics.\n\nThanks again for the helpful review! We hope that our response could address your main concerns. We would greatly appreciate it if you could consider raising the score. "}, {"review_id": "fKZwYppuVX", "reviewer": "Reviewer_fvW2", "summary": "The paper proposes an algorithm for offline reinforcement learning with differential privacy (DP), which protects the privacy of the original information using a Gaussian mechanism based on pessimism. The motivation and ideas behind the paper are clear and meaningful. However, there are some issues with the methods and experiments.\n\nOverall, the paper presents some interesting ideas, but additional experiments and comparisons are needed to fully evaluate the proposed method and its practical value. \n", "questions": "Please refer to the weakness ", "limitations": "Please refer to the weakness", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The authors propose a method for protecting the privacy of original information in offline reinforcement learning. They achieve this goal by implementing differential privacy (DP) in their proposed method, which is a meaningful contribution to the field of privacy-preserving machine learning. \n2. The authors implement their ideas in APVI and VAPVI models and provide a thorough theoretical analysis of the proposed method. The writing is clear and the theoretical analysis is extensive, providing a strong foundation for the authors' claims. \n3. The authors conduct experiments on simulated datasets, which provide preliminary evidence of the method's performance. \n", "weaknesses": "The paper proposes two models, DP-APVI and DP-VAPVI, for solving the offline reinforcement learning problem with privacy guarantees. While the paper presents some interesting ideas, there are several issues:\n1. The paper only includes results for DP-VAPVI, and does not provide any experimental results for DP-APVI. It would be helpful to see how DP-APVI performs in comparison to DP-VAPVI and other baseline methods.\n2. The results for DP-VAPVI consistently show a performance gap compared to VAPVI, which raises questions about the competitiveness of DP-VAPVI in practice. Without additional experiments or comparisons with other methods, it is difficult to assess the practical value of DP-VAPVI.\n3. The paper claims that DP-VAPVI will converge to VAPVI as the dataset size increases, but there is no experimental evidence to support this claim.\n4. The paper does not discuss the impact of the privacy budget (ρ) on the privacy protection and performance of the algorithms. It would be helpful to see how different values of ρ affect the results.\n5. The paper lacks ablation experiments to investigate the extent to which DP itself as an optimization plug-in for APVI and VAPVI models maintains privacy and affects performance. It would be helpful to see how different components of the DP-APVI and DP-VAPVI models contribute to the overall performance.\n6. The paper only compares DP-VAPVI and VAPVI with PEVI, which is not a privacy-preserving method. It would be helpful to see how DP-VAPVI and DP-APVI compare to other privacy-preserving methods.\n7. The experiments are conducted on synthetic datasets, which may not fully reflect the complexity and diversity of real-world problems. It would be helpful to see how the proposed methods perform on real-world datasets.\nMethodologically, the paper proposes to add additional Gaussian mechanisms to APVI and VAPVI models to ensure privacy, but the main methods are still based on APVI and VAPVI. While the paper's definition of neighboring datasets and the use of Gaussian mechanism for differential privacy are contributions, the experimental results are not convincing enough. The authors should demonstrate the advantages of their proposed methods on a wider range of datasets and models.\n\nI'm not an expert on differential privacy. My evaluation is based on how well I was able to comprehend the information in the paper. I don't fully comprehend how this work contributes to the overall growth of the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your high-quality review and positive score. We agree that we mainly use simulations to support our theories. Since we are taking the first step towards differential privacy under offline RL, we mainly analyze our algorithms through theory while only running simulations on toy examples. We leave real-world experiments (which will require designing deep offline RL algorithms with DP) as a future direction. We will reply to the weaknesses you stated.\n\n**The paper only includes results for DP-VAPVI, and does not provide any experimental results for DP-APVI. It would be helpful to see how DP-APVI performs in comparison to DP-VAPVI and other baseline methods.**\n\nWe focus on simulations under linear MDPs since this is the first simulation under linear MDP. Previous works regarding DP RL under linear MDP only focus on theories. For comparison, DP-APVI and DP-VAPVI are not directly comparable since the settings are different. In addition, this is the first work studying offline RL with DP, and there are no available baselines, that's why we do not include baseline methods.\n\n**The paper does not discuss the impact of the privacy budget ($\\rho$) on the privacy protection and performance of the algorithms. It would be helpful to see how different values of $\\rho$ affect the results.**\n\nAs the privacy budget $\\rho$ goes larger, the privacy protection will be weaker, while the performance (sub-optimality) of the output policy will be better and closer to the non-private case. The impact of the choice of $\\rho$ is shown in the theorems and Figure (b) of the experiments.\n\n**The paper only compares DP-VAPVI and VAPVI with PEVI, which is not a privacy-preserving method. It would be helpful to see how DP-VAPVI and DP-APVI compare to other privacy-preserving methods.**\n\nTo the best of our knowledge, this is the first work studying offline RL with DP, and there is no other privacy-preserving methods for this task. Although there exists previous works regarding off-policy evaluation (OPE) with DP, they are not comparable to our methods. Therefore, we mainly compare the DP-VAPVI algorithm to its non-private counterpart. \n\n**The experiments are conducted on synthetic datasets, which may not fully reflect the complexity and diversity of real-world problems. It would be helpful to see how the proposed methods perform on real-world datasets.**\n\nThis is a very good point and we agree that real-world experiments could help validate the theories for DP RL. However, real-world problems often admit more complex structures compared to linear MDPs (this is the reason why previous works regarding DP RL all focus on synthetic datasets). Experiments on more realistic offline RL benchmark such as D4RL may require incorporating various tricks from offline Deep RL literature, and we leave those as future work.\n\nThanks again for the helpful review! We hope that our response could address your main concerns. We would greatly appreciate it if you could consider raising the score. "}, {"review_id": "FjoTd9k2aZ", "reviewer": "Reviewer_ZbTu", "summary": "This paper focuses on reinforcement learning (RL) in an offline setting under differential privacy considerations. It studies the proposal and analysis of a new approach to learning policies in this specific setting, leveraging the Bernstein concentration inequality.\n\nReinforcement learning explores an agent's interaction with its environment over a series of episodes. The environment is defined as a Markov decision process (MDP) comprising states, actions available to the agent, a reward function, and transition dynamics. Through this interaction, the agent gathers feedback to learn a policy that optimizes the cumulative reward. In this paper, the agent operates under the constraints of differential privacy, implying that it interacts in an environment with sensitive data. Here, observations from each episode are deemed private, being tied to individual users.\n\nTraditionally, two settings have been studied: the online and offline settings. In the online setting, an agent learns a policy through active data collection by exploring the environment. Conversely, the offline setting involves the agent receiving all data upfront, barring any access to the environment for training. Prior studies have explored these settings without privacy constraints, but only the online setting has been studied under differential privacy.\n\nThis paper breaks new ground by studying reinforcement learning in the offline setting under differential privacy. Like its online counterpart, the offline setting necessitates the construction of tight confidence bounds around sufficient statistics for policy approximation. However, due to privacy-induced noise, the algorithm must inflate the confidence bounds to compensate.\nThe primary innovation of this paper is the proposal of new confidence bounds, utilizing the Bernstein concentration inequality, a departure from the traditional Hoeffding concentration. This novel method offers improved error bounds under specific instance-dependent conditions, although the bounds are equivalent to Hoeffding's in the worst-case scenario.\n\nThe authors cleverly adapt techniques from previous research while also introducing new methodologies that could potentially extend beyond this work. A significant contribution lies in the estimation of variance from noisy statistics, thereby enabling the utilization of the Bernstein concentration.\n\nIn sum, this paper illuminates a hitherto unexplored area in the RL community, offering innovative solutions and techniques for reinforcement learning in the offline setting under differential privacy.\n", "questions": "No questions. ", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The primary strength of this paper lies in its pioneering examination of differential privacy reinforcement learning (DP-RL) in the offline setting, effectively bridging a notable gap in existing academic literature. By venturing into this uncharted territory, the paper opens up possibilities for practical applications in real-world scenarios where sensitive data may be involved.\n\nThe paper's successful application of differential privacy to offline RL deserves commendation, given the unique challenges associated with this endeavor. While one might assume that the principles governing DP-RL in the online setting would seamlessly translate to the offline setting, this is not the case. The paper adeptly navigates these challenges, setting a benchmark for future investigations into this area.\nAnother significant contribution of this work is the innovative use of Bernstein concentration in the estimation of error bounds. Prior studies primarily employed Hoeffding concentration, which, although effective, offered limited utility under specific conditions. In contrast, Bernstein concentration proves to be more flexible, offering improved error bounds, particularly under specific instance-dependent conditions. This innovative application, therefore, has the potential to enhance results not only in the offline setting but also in the online RL environment.\n\nFurthermore, the paper presents an empirical evaluation that provides rich insights into the practical implications of their proposed techniques. This robust empirical analysis not only validates the theoretical contributions but also offers tangible results that underscore the effectiveness of the proposed methods.\n\nIn conclusion, the paper's merits extend from filling a knowledge void in DP-RL literature, effectively tackling challenges in translating DP-RL principles from online to offline settings, to innovatively employing Bernstein concentration in error bound estimation. The comprehensive empirical evaluation serves as the icing on the cake, demonstrating the practicality and effectiveness of the proposed methods. The paper's contributions are both theoretical and practical, promising to advance understanding and application of DP-RL in offline settings.\n", "weaknesses": "Many of the techniques presented in this paper are not new. The concentration bounds utilized, for instance, have been previously developed and employed in other works. However, the paper's merit lies in its successful adaptation of these existing techniques for a specific context. Therefore, this paper effectively demonstrates how to repurpose these pre-existing tools for its unique setting, thereby contributing to the literature in a meaningful way.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your high-quality review and your support. We really appreciate the detailed and insightful summary. For the weakness, we agree that part of the techniques (including Gaussian mechanism and Bernstein-type pessimism) have been studied. Our main technical contribution is to privatize Bernstein-type pessimism to get tight sub-optimality bounds, as discussed in your review.\n\nThanks again for the appreciation of our work. We are open to further discussions."}, {"review_id": "zO9E4an7zn", "reviewer": "Reviewer_7uyZ", "summary": "This paper addresses the offline RL with Differential Privacy constraints problem. Tabular and linear MDP are considered, while both forms of DP, traditional DP and zCDP are studied. The authors cast the DP definition into the offline RL problem as a constraint for protecting trajectories. Two algorithms, DP-APVI (resp. DP-VAPVI), are introduced, treating the tabular (resp. linear) case. Those algorithms rely on the pessimism principle, and DP is obtained by adding a Gaussian mechanism, either on the counts or during variance estimation. Authors prove zCDP compliance for both algorithms, and a comparison with non-private algorithms is provided. Finally, authors empirically evaluate the performance of DP-VAPVI under different privacy budgets.", "questions": "- See section weakness, could the authors comment on the \\rho factor? And would it allow to robustness to membership inference attacks?\n- You only consider an MDP with 2 states in the experiments, would the algorithm scale to bigger MDPs? ", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The main strength of this paper is that it is, according to my knowledge, the first to tackle the offline RL with DP constraints, which is an important problem. This paper introduce two sound and practical algorithms, respecting Differential Privacy by design. Furthermore, we  have a discussion comparing the algorithms with their non-private counterpart and experimental validation.", "weaknesses": "- Globally, the paper is well-written, however, I found the section on DP-VAPVI very hard to follow, especially the algorithm\n- Experiments study the performance of the algorithms under differential privacy budgets, but it feels very hard to have an interpretation of those budgets for zCDP. In the traditional DP case, one often sees very high values of \\epsilon, leading to a discussable Differentially Private algorithm in practice. Would it be possible to have a discussion about \\alpha?  What would be reasonable values?\n- Although there may not be other paper directly studying directly DP offline RL, there is work in literature on privacy attacks in RL, such as membership inference attack: R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models) or Maziar Gomrokchi, Susan Amin, Hossein Aboutalebi, Alexander Wong, and Doina Precup. Membership Inference Attacks Against Temporally Correlated Data in Deep Reinforcement Learning. It would have been nice to have a discussion on those attacks to have a better estimation of the practical impact of DP casted like this. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your high-quality review and your support. We will reply to the weaknesses you stated.\n\n**Globally, the paper is well-written, however, I found the section on DP-VAPVI very hard to follow, especially the algorithm.**\n\nWe apologize for this and we will improve the readability in the revision. Briefly speaking, the non-private counterpart of DP-VAPVI contains three parts: variance estimation, weighted ridge regression and adding pessimism. In the first part, the variance of value function is estimated. In the second part, the algorithm applies weighted ridge regression based on the estimated variances to derive tighter results. Finally, pessimism is added to the estimated value function. To achieve differential privacy, we add Guassian noises to sufficient statistics. We will surely improve the writing according to your suggestions.\n\n**Experiments study the performance of the algorithms under differential privacy budgets, but it feels very hard to have an interpretation of those budgets for zCDP. In the traditional DP case, one often sees very high values of $\\epsilon$, leading to a discussable Differentially Private algorithm in practice. Would it be possible to have a discussion about $\\rho$? What would be reasonable values?**\n\nThat's a very good point and we will add the discussions. Briefly speaking, the budget for zCDP can be transferred to the budget for DP and $\\rho$ is roughly $\\min(\\epsilon,\\epsilon^2/2)$. Therefore, smaller $\\rho$ provides stronger privacy protection and a small constant would be a reasonable value for the zCDP budget. For instance, [1] takes the privacy budget to be around 1. In practice, any $\\rho<10$ should be considered meaningful privacy guarantees. The choice of $\\rho$ is often cast as a social problem and the preferred value differ in each application. For this reason, we experimented on a range of different $\\rho$ in our simulation. \n\n[1] Xu et al. Federated Learning of Gboard Language Models with Differential Privacy. arXiv:2305.18465. 2023.\n\n**Although there may not be other paper directly studying directly DP offline RL, there is work in literature on privacy attacks in RL, such as membership inference attack: R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models) or Maziar Gomrokchi, Susan Amin, Hossein Aboutalebi, Alexander Wong, and Doina Precup. Membership Inference Attacks Against Temporally Correlated Data in Deep Reinforcement Learning. It would have been nice to have a discussion on those attacks to have a better estimation of the practical impact of DP casted like this.**\n\nThanks for pointing us to the literature regarding membership inference attack. The guarantee of DP ensures that even if all the other training data points are known, it is statistically hard to predict whether some data point appears in the training dataset. More specifically, given a fixed type-I error rate, DP guarantee provides a lower bound for the type-II error rate of the membership inference attack. Therefore, a DP algorithm provably provides robustness against membership inference attacks. \n\n**You only consider an MDP with 2 states in the experiments, would the algorithm scale to bigger MDPs?**\n\nWe use the same MDP setting as previous papers regarding offline RL. The algorithm can be applied under MDPs with larger state space as well as it admits linear structure. We leave experiments on more complex benchmarks such as D4RL (which will require designing deep offline RL algorithms with DP) as a future direction. \n\nThanks again for the helpful review! We hope that our response could address your main concerns. We are open to further discussions."}, {"review_id": "Ok1FSKc8JH", "reviewer": "Reviewer_ytfu", "summary": "This paper proposes two offline RL algorithms with differential privacy guarantees. The two pessimism-based algorithms apply to both tabular and linear MDP settings. In theory, the authors prove that the proposed algorithms achieve instance-dependent sub-optimality bounds while guaranteeing differential privacy. A nice property is that the cost of privacy only appears as lower order terms, thus become negligible as the number of samples goes large.\n", "questions": "See Weakness section", "limitations": "None.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) While DP algorithm has been studied in online RL settings, the study of DP in offline RL is limited. This paper provides the first provable study along this line. \n\n(2) In spite of a theoretical paper, it is well written and easy to follow. \n", "weaknesses": "\n(1) The motivation of the considered problem needs more real justifications. In the introduction, the authors used a medical example to motivate the need of considering privacy in offline RL. Why could not the data owner (hospital or doctors) do offline policy evaluation or policy optimization directly on the raw data? Why do we need to generate a private policy? On the other hand, if the offline policy optimization is requested from a third-part not the data owner, it is justified that the patient's data needs to be protected. However, in this case, the third-part would not have access to the raw data. This contradicts with the setting considered in this paper as in the proposed Algorithm 1 and Algorithm 2, the input is the raw data. Therefore, it is important and helpful to provide a convincing real example to justify the problem setting and algorithm designs. \n\n(2) In Assumption 2.2, the data distribution needs to satisfy the minimum eigenvalue condition. This assumption might be violated when the feature space is large or some features are highly correlated. It is helpful to provide some discussion on this assumption and how to remedy it when this assumption is violated. \n\n(3) In the tabular MDP (DP-APVI) algorithm, the Gaussian noise is added to the integer counts $n_{s_h, a_h}$ and $n_{s_h, a_h, s_{h+1}}$ to obtain a private estimation of the transition kernel. Because of the design, the private counts might be negative or very small, which makes the uncertainty estimation (line 5 of Algorithm 1) to be unstable. To handle it, the authors used some truncation approach with some theoretical truncation rate $E_{\\rho}$. It is unclear if it is a good choice to add the Gaussian noise to the count statistics. Can we add the Gaussian noise directly to the non-private estimation of transition kernel? Some justifications on the proposed private estimation would be helpful. It is also important to discuss the advantages and limitations of the proposed private estimation while comparing with other choices in existing RL literature. \n\n(4) In Algorithm 2 and line 235 of Page 7, the authors require two independent offline dataset with equal length. Can authors clarify what the rigorous condition of the \"two independent offline dataset\"? Do you need each sample (across $K$) at each time horizon (across $H$) to be independent in each offline data? If yes, this is an unrealistic condition in offline RL problem. Moreover, I did not find such condition in the statement of Theorem 4.1. Where do you use this \"independence\" assumption? \n\n(5) In the experiments (Figure 1), the simulations are for 5 replicates. Can authors include the uncertainty in Figure 1? If the uncertainty is large, it is helpful to increase the replication times.  \n\n\n~~~~~~~~~~~\nAfter rebuttal: my major comments have been nicely addressed. I have increased the score to 7.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your high-quality review and your support. We will reply to the weaknesses you stated.\n\n**In the introduction, the authors used a medical example to motivate the need of considering privacy in offline RL. Why could not the data owner (hospital or doctors) do offline policy evaluation or policy optimization directly on the raw data? Why do we need to generate a private policy?**\n\nEven if the owner has access to the raw data, it is risky to work directly on the raw data. If the data owner do offline RL directly on the raw data, there will be risk of privacy leakage. For instance, membership inference attack ([1]) could detect the data used in the training procedure by observing the output policy of the offline RL algorithm. In other words, the attacker could reconstruct the medical history of the patients whose data is used for training the model, which is harmful to the privacy of those patients. In contrast, training the model with DP guarantee could provably prevent such risks. \n\n[1] R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models. \n\n**On the other hand, if the offline policy optimization is requested from a third-part not the data owner, it is justified that the patient's data needs to be protected. However, in this case, the third-part would not have access to the raw data. This contradicts with the setting considered in this paper as in the proposed Algorithm 1 and Algorithm 2, the input is the raw data.**\n\nThis is a very good point. Local DP, where the data needs to be privatized before being sent to the algorithm is used to characterize such situation. Under such circumstances, noise should be added to the raw data, and then the algorithm would aggregate the privatized data and learn the policy. This is an interesting but different problem from our setting. We believe that this could be a good future direction.  \n\n**About Assumption 2.2: the minimum eigenvalue condition.**\n\nFirst, we would like to highlight that the DP guarantee does not depend on this assumption, and the assumption is only used to derive sub-optimality bounds. In addition, such coverage assumption is standard in offline RL literature since without such assumption, there will be a constant sub-optimality gap for the output policy even without constraints of DP, in the worst case ([2]). Therefore, we base on the coverage assumption and derive an asymptotic sub-optimality bound. We will add the discussions in the revision.\n\n[2] Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. NeurIPS 2021.\n\n\n**Can we add the Gaussian noise directly to the non-private estimation of transition kernel? Some justifications on the proposed private estimation would be helpful. It is also important to discuss the advantages and limitations of the proposed private estimation while comparing with other choices in existing RL literature.**\n\nAdding noise to visitation counts is a widely applied method in DP RL literature ([3],[4]). It is a possible choice to add noise to the empirical transition kernel, while there are two issues for the method. First, given the sensitivity analysis, the $\\ell_1$ difference between the private and non-private transition kernel estimates will be the same order as our approach. Second, in this way, the private transition kernel will not be a valid probability distribution, which is not applicable for our Bernstein-type pessimism. In comparison, we effectively solve the second issue through solving the optimization problem.\n\nSimilar approaches of private estimation also appears in the DP online RL literature. [4] directly adds Gaussian noise to the visitation counts and constructs the private transition kernel estimate. As a result, [4] could only operate on the Hoeffding-type bonus and derive sub-optimal regret bounds. Recently, [3] follows our construction of the private transition kernel estimate and operates on the Bernstein-type bonus. As a result, [3] improves the regret bound in [4] and derives nearly minimax optimal results. Therefore, our method for privately estimating the transition kernel is not improvable in general.  \n\n[3] Dan Qiao and Yu-Xiang Wang. Near-Optimal Differentially Private Reinforcement Learning. AISTATS, 2023.\n\n[4] Sayak Ray Chowdhury and Xingyu Zhou. Differentially private regret minimization in episodic\nmarkov decision processes. arXiv preprint arXiv:2112.10599, 2021.\n\n**In Algorithm 2 and line 235 of Page 7, the authors require two independent offline dataset with equal length. Can authors clarify what the rigorous condition of the \"two independent offline dataset\"? Do you need each sample (across $K$) at each time horizon (across $H$) to be independent in each offline data? If yes, this is an unrealistic condition in offline RL problem. Moreover, I did not find such condition in the statement of Theorem 4.1. Where do you use this \"independence\" assumption?**\n\nThis is a good question. Instead of requiring the data to be independent at each time horizon, we only require each trajectory (across $K$) to be independent, and this is naturally ensured by our offline RL setting where the data is sampled i.i.d according to some behavior policy. The independence of the two datasets is only for technical reason, which is to ensure that the dataset for weighted ridge regression is sampled i.i.d from the behavior policy even given the estimated variances. We will clarify this in the revision.  \n\n**In the experiments (Figure 1), the simulations are for 5 replicates. Can authors include the uncertainty in Figure 1? If the uncertainty is large, it is helpful to increase the replication times.**\n\nWe will add the confidence interval in the revision. \n\nThanks again for the helpful review! We hope that our response could address your main concerns. We are open to further discussions.\n"}]

Author rebuttal:

Meta-review: The paper makes its main contribution by introducing offline RL algorithms with differential privacy guarantees. The paper introduces algorithms for tabular and linear MDPs. It develops a proof technique based on Bernstein concentration. The paper also studies the cost of privacy, comparing theoretical results for algorithms that come with differential privacy guarantees with those that do not. Overall, this is a well-scoped and well-executed research project.  The main shortcomings are that (1) there are some remaining concerns about novelty / related work, (2) the experimental evaluation is limited (3) the impact of privacy budget not studied sufficiently, (4) more ablations would be better and (5) experiments are on synthetic datasets only. However, these are not fatal in a theoretical paper.
Decision: Accept (poster)