Offline Reinforcement Learning with Differential Privacy
Authors: Dan Qiao
Yu-Xiang Wang
Venue: Submitted to ICLR 2023 (2023)
Keywords: offline reinforcement learning
differential privacy

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.

Under review as a conference paper at ICLR 2023
OFFLINE REINFORCEMENT LEARNING WITH DIFFER- ENTIAL PRIVACY
Anonymous authors Paper under double-blind review
ABSTRACT
The offline reinforcement learning (RL) problem is often motivated by the need 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 utility comparing to the non-private counterpart for a medium-size dataset.
INTRODUCTION
Offline Reinforcement Learning (or batch RL) aims to learn near-optimal policy in an unknown environment through a static dataset gathered from some behavior policy μ. Since offline RL does not require access to the environment, it can be applied to problems where interaction with environment is infeasible, e.g., when collecting new data is costly (trade or finance (Zhang et al. 20200), risky (autonomous driving (Sallab al. 2017)) or illegal / unethical (healthcare (Raghu et al. (017)). 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 to (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 a decision policy that is indistinguishable from policy trained in alternative universe any individual user is replaced, thereby preventing the aforementioned privacy risks. There a surge of recent interest in developing RL algorithms with DP guarantees, but they focus mostly on the online setting (Vietri al. 2020
Garcelon et al. 2021 Liao et al., 2021 Chowdhury & Zhou 2021 Luyo et al. 2021).
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. 2017p.
Our contributions. In this paper, we present the first provably efficient algorithms for offline RL with differential privacy. Our contributions are twofold.
The environment is usually characterized by Markov Decision Process (MDP) in this paper.

---

Under review as a conference paper at ICLR 2023
We design two new pessimism- based algorithms DP-APVI (Algorithm D and DP- VAPVI (Algorithm 2 one for the tabular setting (finite states and actions), the other for the case with linear function approximation (under linear MDP assumption). Both algorithms enjoy DP guarantees (pure DP or zCDP) and instance-dependent learning bounds where the cost of privacy appears lower order terms.
We perform numerical simulations to evaluate and compare the performance of our algorithm DP- VAPVI (Algorithm 2 with its non- non-privenn private counterpart VAPVI (Yin al. 2022) as well as a popular baseline PEVI (Jin et al., (021). The results complement the theoretical findings by demonstrating the practicality of DP- VAPVT under strong privacy parameters.
Related work. To knowledge, differential privacy in offline RL tasks has not been studied before, except for much simpler cases where the agent only evaluates a single policy (Balle et al., 2016; X al. 2019). Balle al. (2016) privatized first-visit Monte Carlo-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 & Zhou| 2021
Ngo
et al..] 2022 Luyo et al., (02T) or local differential privacy (Garcelon et al. [021]] Liao et al. 2021
Luyo et al.
|021] Chowdhury Zhou 202T). The offline setting introduces new challenges in DP
as we cannot algorithmically enforce good "exploration", but have to work with a static dataset and
privately estimate the uncertainty in addition to the value functions. A private online RL algorithm
can sometimes be adapted for private offline RL too, but those from existing work yield suboptimal and non-adaptive bounds. We give a more detailed technical comparison in Appendix B
Among non- non-private offfine RL works, we build directly upon non- non-private offline RL methods known as Adaptive Pessimistic Value Iteration (APVI, for tabular MDPs) (Yin & Wang (021b) and Variance- Aware Pessimistic Value Iteration (VAPVI, for linear MDPs) (Yin et al., (022), as they give the
strongest theoretical guarantees to date. We refer readers to Appendix [ for more extensive review of the offline RL literature. Introducing DP APVI and VAPVI while retaining the same sample complexity (modulo lower order terms) require nontrivial modifications to the algorithms.
A remark technical novelty. Our algorithms involve substantial technical innovation over previous works on online DP-RL with joint DP guaranted Different from previous works, our DP-APVI (Algorithm D 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 (Zoou et al. 202I)). Our VP-VA releases conditional variance privately, and further applies weighted ridge regression privately. Both approaches ensure tighter instance-dependent bounds on the suboptimality of the learned policy.
PROBLEM SETUP
Markoy Decision Process. A finite-horizon Markov Decision Process (MDP) is denoted by tuple
M = (S, A, p.r, H,d;) (Sutton & Barto 2018), where S is state space and AA is action space. A non- stationary transition kernel Ph. S x A x S
+ [0, 1] maps each state action (sh, a;.) ) to a probability distribution Px (- a,) and Pt, can be different across time. Besides, r4 S A +> IR is the expected immediate reward satisfying 0 < rh I 1, dj is the initial state distribution and H is the horizon. A policy π (Ti ................................ TH) assigns each state s S probability distribution over actions according to the map 8n. + (-1s)), Vh E [H]. A random trajectory 81, 41, ,,,"" , 8H an, TH, 8H+11 is generated according to 81 di, On ~ Th (-(s)),,, rh ~ Th (s an), 8h+1 Ph (-11%, 4,),, Vh E [M].
For tabular MDP, we have S x A is the discrete state-action space and 5 = |S], A |A| are finite. In this work, we assume that r is k In addition, we denote the per-step marginal state-action occupancy dz (s, a) as: di a)= : P(sn 8|si ~ d1, m) - (a|s), which is the marginal state-action probability at time h.
'Here we only compare our techniques (for offine RL) with the works for online RL under joint DP guarantee, as both settings allow access to the raw data.
'This is due to the fact that the uncertainty of reward function is dominated by that of transition kemel in RI..
2

---

Furthermore, we Under review as a conference paper at ICLR 2023
Value function, Bellman (optimality) equations. The value function (g(() and Q-value func- tion (t-). for any policy x is defined as: (s) E> re|sh s]. (1,
E. 1 tt=h Tr Tr|Sh;
8, s.
A 8h,8,a E [M] x S x A. The performance is defined as 8"
Ed [VT]] = E EE To The Bellman (optimality) equations follow 4 [H]] Q7
Th + PAV Vi2T E Ba-ay QQ1, Q7 = + Pitt Vi = max, Q)(:a))
Linear MDP JJin et al. 2020b). An episodic MDP (S, A, H, P.r) is called a linear MDP with known feature map : S x A- IR if there exist H unknown signed measures Va E R over S and H unknown reward vectors On E R such that
Pa. (s' s, a) (ő(s, a), vn (s')) TA (s. a) = (,(s.a))
sh,,s, E [H] x
Without loss generality, we assume [[ø(s, a)ll2 S and max(] 110x112) & vd for all h, 8,a [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 in Lemma E. E.14
Offline setting and the goal. The offline RL requires the agent find policy in order to maximize the performance v", given only the episodic data D {(sT, a ri, sh+ fe rolled out from some fixed and possibly unknown behavior policy μ., which means cannot change μ and in particular we do not assume the functional knowledge of μ.. In conclusion, based on the batch data 'D and a targeted accuracy
he
the agent seeks to find policy Talg such that 8 a S
2.1 ASSUMPTIONS OFFLINE RL
In order to show that our privacy-preserving algorithms can generate near optimal policy, certain coverage assumptions needed. In this section, we will list the assumptions use in this paper.
Assumptions for tabular setting.
Assumption 2.1 (Liuu al. 2019)). There exists one optimal policy such that x² is fully covered by μ, i.e. V Sh, ag S X A d', (sh, an) 0 only if di, (sh,an) >> 0. Furthermore, we denote the trackable set as Cp == {(sh, an) di (sh, an)) > 0}.
Assumption 2.1 is the weakest assumption needed for accurately learning the optimal value vz by requiring yu to trace the state-action space of one optimal policy (/u can be agnostic other locations). Similar to (Yin & Wang 2021b), we will use Assumption 2.1 for the tabular part of this paper, which enables comparison between our sample complexity to the conclusion in (Yin & Wang 2021b), whose algorithm serves non-private baseline.
Assumptions for linear setting. First, we define the expectation of covariance matrix under the behavior policy μ for all time step h E [H] as below:
DP Ey, [d(s) an )o 8h, (,) 7
As have been shown in (Wang et al. offline data requires coverage assumptions. Here in linear setting, such coverage characterized by the minimum eigenvalue of 2%,- Similar to (Yin et al. 2022 apply the following assumption for the sake of comparison.
2021 Yin et al. 2022). learning near-optimal policy from
2021 ). The data distributions μ satisfy the minimum eigenvalue condition: V E [H] Ky. = Amin (2)) >
Assumption 2.2 (Feature Coverage, Assumption 2 in (Wang et al.
denote ming Kt.
2.2 DIFFERENTIAL PRIVACY IN OFFLINE RL.
In this work, we aim to design privacy preceyyirreevinngg algorithms for offline RL. We apply differential privacy as the formal notion of privacy. Below revisit the definition of differential privacy.
Definition 2.3 (Differential Privacy (Dwork et al. (0066). randomized mechanism M satisfies (c. (). diffferential privacy ((c, 6)-DP) for all neighboring datasets U, U that differ by one data point and for all possible event in the output range, holds that
P[M(U) E E < e (U') E E +
*For clarity we for tabular MDP and K for linear MDP when referring the sample complexity.
3

---

Under review as a conference paper at ICLR 2023
When 6 = 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.3rrefrs to one single trajectory. Hence the definition of Differential Privacy means that the difference the distribution of the output policy resulting from replacing one trajectory in the dataset will be small. In other words, adversary can not infer much information about any single trajectory in the dataset from the output policy of the algorithm.
During the whole paper, we will use zCDP (defined below) 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.4 (zCDP (Dwork Rothblum 2016) Bun & Steinke 2016)). randomized mechanism M satisfies and all a (1))
Differential Privacy (p-zCDP), if for all neighboring datasets U, U
Do (M()))) S pa.
where Da, the Renyi-divergence (Van Erven & Harremos
2014).
Finally, we go over the definition and privacy guarantee of Gaussian mechanism. Definition 2.5 (Gaussian Mechanism @work et al. 2014)). Define the l sensitivity of a function f: T.N* + Rd as
D2(
|1(()) -[(U))l2 sup
neighboring U,!"
The Gaussian mechanism M with noise level is then given by
M(U) f(U) + (0,
Lemma 2.6 (Privacy guarantee Gaussian mechanism (Dwork al. 2014 Bun Steinke 2016 )
Let f N. + Rd be an arbitrary d-dimensional function with &g sensitivity A2. Then for any > 0,
Gaussian Mechanism with parumeter a²
A3
2p satisfies p-zCDP. In addition, for all < 8, 1,
Gaussian Mechanism with parameter ب log L.25 satisfies (e, 6)-
We emphasize that the privacy guarantee covers any input data. It does not require any distributional assumptions the data. The RL- RL-specific assumptions (e.g., linear MDP and coverage assumptions) are only used for establishing provable utility guarantees.
RESULTS UNDER TABULAR MDP: DP-APVI (ALGORITHM I
For reinforcement learning, the tabular MDP setting is the most well-studied setting and our first result applies to this regime. We begin with the construction of private counts.
Private Model-based Components. Given data D = [(*,, ahs The #)) AEtRi we denote Nsn.an.
E- (8% 1 oz 8h, 0n) be the total counts that visit (sh, ax) pair at time h and Rss,: Er [8% 4/ Th11 = 8h, ah, $1+1] ] be the total counts that visit (sh, Oh 81+1) pair at time h, then given the budget for zCDP, we add independent Gaussian noises to all the counts:
{Reg.aa + Ren = (Raneneeees + +N(0,03)3* 0²
2H P
(2)
However, after adding noise, the noisy counts ní' may not satisfy n',,an, = En n' To address this problem, we choose the private counts of visiting numbers as the solution to the
following optimization problem (here E.p 4 H log 4
( Mas Jo'Es bo = argmin (x argmin
(xyr)rss
max
E n' sn
S'ES
Σ Vss whn S Eg 1'ES
such that
and aes 2 2 E.
(3)
Tig as Σ ah.ss 8
s'ES
4

---

Under review as a conference paper at ICLR 2023
Remark 3.1. The optimization problem can be reformulated as:
min i, s.l. [Tg' Was S and a. 2 204EE
Fe - n Ninnoa S'ES
Σ
Ep 2
(4)
Note that is Linear Programming problem with S + variables and 25 2 (one con- straint on absolute value is equivalent to two linear constraints) linear constraints, which can be solved efficiently by the simplex method (Ficken 2015) or other provably efficient algorithms Nemhauser & Wolsey 1988). In addition, if we do not solve this optimization problem and di- Tsn and Tannon EantLEs a5.4.0 we can only derive O(VSEp)) through concentration on summation of i.i.d. Gaussian noises. In contrast, solving ensures that Mes.on .Rnnaal S Ep with high probability F
rectly take Tep
[ -Os
The private estimation of the transition kernel is defined as:
(s an) Rap.a
(5)
if Max on > Ep and Pr an) = otherwise.
Remark 3.2. Different from the transition kernel estimate in previous works (Vietri el al. 2020 Chowdhury & Zhou (027) that may not be distribution, we have ensure that ours a probability distribution, because our Bernstein type pessimism (line 5 in Algorithm D needs to take variance over this transition kernel estimate. The intuition behind the construction of our private transition kernel is that, for those state-action pairs with Nan.on. S Ep. we can not distinguish whether the non-zero private count comes from noise or actual visitation. Therefore we only take the empirical estimate of the state-action pairs with sufficiently large Ns..on.
Algorithm Differentially Private Adaptive Pessimistic Value Iteration (DP-APVI)
I: Input: Offfine dataset D {(sh, ah, Phe 11)+))) Reward function r. Constants Ci V2,C2 16, C> 1, failure probability 8, budget for xCDP
2: Initialization: Calculate men Pai as
Ps (sh, as) as Vu+1(.) + 0. Ep t-
log 4H²2a
3: for H, - 1,...., log(HSA/0).
VV
4: Qu(.)) & rn(::)) (Ph. Vn+a)(,-))
Var Varp (Vat1)s
5: Ysh, on, let (sh, on) + C.V
CaSHE if Ron > Ep, otherwise CH.
Region -Eo
@g(+)) )n(:.) -..(s)).
Q.(+)) +
-
Vsa. let (-(3) <- argmaxx, (Qn(sn)) .), Ta (118a)) and Vn (sn) <- (Qn (sn, tr (-1sa)))
9: end for
10: Output: ).
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 APVI (Yin & Wang 2021b). we
design a similar pessimistic algorithm with private counts to ensure differential privacy. If we replace
ñ and P with and A then AP-APVI (Algorithm I will degenerate to APVI Compared to
the pessimism defined in APVI, our pessimistic penalty has an additional term Ō (SHEE. accounts for the additional pessimism due our application of private statistics.
which
We state our main theorem about AP-APVI below, the proof sketch is deferred to Appendix detailed proof deferred to Appendix due to space limit.
C.I and
*This conclusion is summarized Lemma 'The pri-ptivate empirical estimate, defined as
Appendix
5

---

Under review as a conference paper at ICLR 2023
Theorem 3.3. DP-APVI (Algorithm ! satisfies p-zCDP. Furthermore, under Assumption 2.1 denote dm == minnee mj d4 ($h, ax) d (Sh: ap) > 0}. For any < < 1, there exists constant C1 > 0,
such that when n > max H22 / - (t log (A/6))), with probability 1 - ô, the output
11 log amgRa
policy it of DP-APVI satisfies (Ō hides constants and Polylog terms, E.p 4V
Varpal-onn.a as) (V h+1
H S
S 0²
4V
Σ Σ
(sh, V
+0
nd, (8 ahh)
nt dm
(SN.0aJECn
Comparison to non-private counterpart APVI Yin Wang 2021b). According to Theorem 4.1 in (Yin & Wang 2021b), the sub-optimality bound of APVI is for large enough n, with high probability, the output î satisfies:
0 0a
H Σ
Σ
dh (sh, and
Var a (Vi+a (-)) ndl, (sh, an)
+ Ō
H3 dm
(7)
h= (n),
Compared our Theorem 3.3
the additional sub-optimality bound due to differential privacy is
E
SH
SH m-dmm
In the most popular regime where the privacy budget
n.dmy?
P or é a constant, the additional term due to differential privacy appears as a lower order term, hence becomes negligible the sample complexity becomes large.
Comparison to Hoeffding type pessimism. We can simply revise our algorithm by using Hoeffding type pessimism, which replaces the pessimism in line with C₁ H / "ap..n + C,SHE, Then
Rag.oh with similar proof schedule, arrive at sub-optimality bound that with high probability,
SHH=Ep ddm
5 v- - S
H
Σ
The (sn, an) (dt an)
+
(8)
R=1 (EC,
Compared to our Theorem 3.3 system quantities instead of explicit dependence H (and Varp, (-lan,e)) (Vitt (+)) < H2). In addition, we highlight that according to Theorem G. in YYin & Wang 2021b), our main term nearly matches the non-private minimax lower bound. For more detailed discussions about our main term and how it subsumes other optimal learning bounds, we refer readers to (Yin & Wang 20216).
our bound tighter because we express the dominate term by the
Apply Laplace Mechanism to achieve pure DP. To achieve Pure DP instead of p-zCDP. we can simply replace Gaussian Mechanism with Laplace Mechanism (defined as Definition 19 Given privacy budget for Pure DP e, since the l sensitivity of {Ne,.en) {Mes,en..s4:) } is A 4H. we can add independent Laplace noises Lap( 4/1 to each count to achieve e-DP due to Lemma E.20
Then by using F., = Ô ( () instead of F., and keeping everything else ① and Algorithm the same, we can reach a similar result to Theorem 3.3 with the same proof schedule. The only difference
that here the additional learning bound is θ 8H3
which still appears as lower order term n.dmm
4 RESULTS UNDER LINEAR MDP: DP- VAPVI(ALGORITHM 2
In large MDPs, to address the computational issues, the technique of function approximation is widely applied, and linear MDP 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 μ) as in Algorithm we can apply variance-aware pessimistic value iteration to learn a near optimal policy as in
Herre apply the second part of Lemma 2.6 to achieve (c, 5DDP, the notation Ô also absorbs log (only here & denotes the privacy budget instead of failure probability).

---

Under review as a conference paper at ICLR 2023
VAPVI (Ynn et al.
2022). To ensure differential privacy, we add independent Gaussian noises to the 2 below. Since there are 5H statistics, by the adaptive composition of zCDP (Lemma E.17 it suffices to keep each count Po-zCDP, where po 5 In DP-VAPVI, we use Φ1, Φ2, Øa, K1, K denote the noises we add. For all Φi. we directly apply Gaussian Mechanism. For K,, in addition to the noise matrix (2 + Z )),, we also add _ to ensure that all K, are positive definite with high probability (The detailed definition of E, L can be found in Appendix
5H statistics as in DP- VAPVI (Algorithm
Algorithm 2 Differentially Private Variance-Awar Pessimistic Value Iteration (DP- VAPVI)
K.H. I: Input: Dataset D {(5), oh ri. +)+1)) v.h=1 D' [(5,, Th The 5)+1)) h.mm Budget for zCDP p. Failure probability 8. Universal constant C.
Initialization: Set po <- 5 V++1(() &- Sample oi ~N(( (0. 2 2
la). o2 Φs ~ NN ~N(0, po
2#² Ia
K2 La (Z + )" where Zis -N (0, 1 (i.id.), E ō ō(v
Hd p
Set D
δ 0(10 1 + 23/2
H4Evd + v1)
3:
for h = H. H 1...., do
4:
Set En f- -1 6(5 di)o(sis. an) + Al K1
>
5:
Set Bg + Σn 1 o(3, a Va+1 +b]
6:
Set On t Srp | o(5,, a Vn-1 (1+)) + d2)
7:
Set Vara Vn+aa (5.) + -, Bn) (0.11 - [(6(:-), -), 0n) 11
8:
Set (., )² max(1, (1, Varn (:+)
9:
Set Ar Σx o (0%, and 2 (8h) a7)
(0h oT) + AT K2
10:
Set Wh + A (Ex- @ (5%,
Vuta (oh+1) /o a7)) + 0z)
11:
Set (x.-)) - Cvd- (o(s-) -) An (()))))))
1/2
+
12:
Set (.(:))) + )(:)))
T ih - -')(s.) Set (n(.)) () + min (1 )) H, - +1
13:
14:
Set (. 1 ())
argmax,,, g (Qa(s) ,), mn(-1 +)) Val.) + maxa, (Qals)), m.( (1)))
15:
end for
16:
Output: (fn 1
Below we will show the algorithmic design of DP-VAPVI (Algorithm) 2. For the offline dataset, ke(M]] we divide it into two independent parts with equal length: DD = (( % rh *h+1)) and A One for estimating variance and the other for calculating Q-values.
D' (55 Th Fh. (T+)))
Estimating conditional variance. The first part (line 4 to line 8) aims to estimate the condi- tional variance of Vn+1 via the definition of variance: (VarAVn4lle a) = [P%((V a) [PP a))2 For the first term, by the definition of linear MDP, it holds that PA P h+1 (s,a) = a(s,a)T Js ViL (s') dup (s') [s. V2t1 (s') dr, (s')). We can estimate dup (s') by applying ridge regression. Below is the output of ridge regression with raw statistics without noise:
Bn [s
argiiin BERU
Σ Kocs
Vhin () 11ee
S Σ
a at) Vi+n (dht1);
where definition of E., can be found in Appendix A Instead of using the raw statistics, we replace them with private ones with Gaussian noises as in line 5. The second term is estimated similarly in line 6. The final estimator is defined as in line 8: (, )²2 = max(1, Var, (++1(s-)))
$ We need to add noise to each of the 5H counts, therefore for di, we actually sample H i.i.d samples ó1,a. = 1,... from the distribution of d1. Then we add Φ1,A to ΣK_ 66%, 2.)) V ( V E [H]. For simplicity, we use di to represent all the Φ1,k- The procedure applied to the other AH statistics are similar. The max(1, 1 operator here is for technical reason only: we want lower bound for each variance estimate.
7

---

Under review as a conference paper at ICLR 2023
Variance-weighted LSVI. Instead of directly applying LSVI (Jin et al., suriance-weighted LSVI (line 10). The result of variance-weighted LSVI with non-private statistics is shown below:
2021). solve the
K (blsh: an),, w) --
K Φ (shh
(1t Vata (sh+t))
argmin wErd
Al[w||
(6 af)
of (1f
1
where definition of An can be found in Appendix A private statistics instead and derive the wh as in line TO.
For the sake of differential privacy, we use
Our private pessimism. Notice that if we remove all the Gaussian noises we add, our DP- DP-VAPVI (Algorithm 2 will degenerate to VAPVI (Yin et al. 2022). We design similar pessimistic penalty using private statistics (line 11), with additional
K accounting for the extra pessimism due to DP.
Main theorem. We state our main theorem about DP-VAPVI below, the proof sketch deferred to Appendix D.I and detailed proof is deferred to Appendix D due to space limit. Note that quantities
Mi. L, E can be found in Appendix A and briefly, L O Olv H)) E DD/Hd//p) For the sample complexity lower bound, within the practical regime where the privacy budget is not very small, max [MMi} is dominated by max (0 (x,5) )..5).C O ((HL)//x)) which also appears in the
sample complexity lower bound of VAPVI (Yin al. 2022). The of (s. a) in Theorem is defined as max(1, P, (V)ssa)) } for any V. Theorem 4.1. DP-VAPVI (Algorithm satisfies p-zCDP. Furthermore, let K be the number of episodes. Under the condition that K m M2, Ma} and vd &, where &
(+) (T.V)(a)))))))
Su dPPaa(,,), bE[H]
for any 0 < X < K. with probability 1 for all policy n simultaneously, the output āo of DP-VAVVI satisfies (Ō hides constants and Polylog terms)
(v.a)
-- 2ō Va.
EE, E
H
+
DH
(9)
A=1
where An = EK In particular, define A
+ and
and D) = Ō H
H'E 2372
H3
dieh o ((thaat) + Ala, we have with probability
H1
Ee (VOGOTAA-'6..)) 0..))
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
dominated by δ bound of VAPVI is for sufficiently large K, with high probability, the output म satisfies:
H 7 d/a
According Theorem 3.2 in Yin al. 2022), the sub-optimality
VP
E. Vo ( + 2H'Vd
u²
t <ō
Vd
(11)
the additional sub-optimality bound due to differential privacy is In the most popular regime where the privacy budget p or is a constant, the additional term due to differential privacy also appears as a lower order term.
Compared to our Theorem 4.1
δ
11 d/R3
#1 2 a/c e-K
VP-K
Instance-dependent sub-optimality bound. Similar AP-APVI (Algorithm D.. our DP- VAPVI (Algorithm 2 also enjoys Instance-dependee sub-optimality bound. First, the main term in (IO improves PEVI ( 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).
Here apply the second part of Lemma 2.6 to achieve (c, 5)-P,, the notation Ô also absorbs log (only here 8 denotes the privacy budget instead of failure probability).
8

---

Under review as a conference paper at ICLR 2023
5 SIMULATIONS
In this section, carry out simulations to evaluate the performance of our DP-VAPVI (Algorithm and compare it with its non privati counterpart VAPVI (Yin et al. 2022) and another pessimism- algorithm PEVI (Jin al. 202T which does not have privacy guarantee.
2
Experimental setting. We evaluate DP VAPVI (Algorithm 2 on a synthetic linear MDP example that
originates from the linear MDP in (Min et al. 2021 Yin et al. 2022) but with some modifications [ For details of the linear MDP setting, please refer to Appendix
The two MDP instances we use
both have horizon H 20. We compare different algorithms in figure [a] while in figure [(b] compare our DP-VAP VAPVI with different privacy budgets. When doing empirical evaluation, we do not split the data for OP-VAPVI or VAPVI and for DP-VAPVI, we run the simulation for 5 times and take the average performance.
FEA
VAPM
WPPI
SP-VAPVLPHO
BP-AAVLLEES DP-VAPVLp:25
200
620
1000
optoudes
(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* n while x-axis denotes the number of episodes K. The horizons are fixed to be H 20. The number of episodes takes value from to 1000.
Results and discussions. From Figure I we observe that DP- P--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 DA-VI with larger privacy budget, the scale of noise will be smaller, thus the performance will be closer to VAPVI, as shown in figure I(b) Furthermore, in most cases, VAPVI still outperforms PEVI, which does not have privacy guarantee. This arises from our privitization of variance-aware LSVI instead of LSVI.
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 lower order terms, thus become negligible as the number of samples goes large.
Future extensions are numerous. We believe the technique in our algorithms (privitization of Bernstein-type pessimism and variance-aware LSVI) and the corresponding analysis can be used in online settings too obtain tighter regret bounds for private algorithms. For the offline RL problems, we plan to consider more general function approximations and differentially private (deep) offline RL which will bridge the gap between theory and practice in offline RL applications. Many techniques we developed could be adapted to these more general settings.
11 We keep the state space S {1,2), 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.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yasin Abhasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Interna- tional Conference on Machine Learning, pp. 32-40. PMLR, 2017.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value- targettd regression. In International Conference on Machine Learning, pp. 463 474.474.B PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 263-272. JMLR. org, 2017.
Borja Balle, Maziar Gomrokchi, and Doina Precup. Differentially private policy evaluation. In International Conference on Machine Learning, pp. 2130-2138. PMLR, 2016.
Debabrota Basu, Christos Dimitrakakis, and Aristide Tossou. Differential privaey for multi-armed bandits: What is it and what is its cost? arXiv preprint arXi:: 12298, 2019.
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. When is memorization of irrelevant training data necessary for high-accuracy learning? ACM SIGACT Symposium on Theory of Computing, pp. 123-132 2021.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pp. 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, pp. 1283-1294, PMLR, 2020.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernjj Kos, and Dawn Song. The secret sharer: Evalu- ating and testing unintended memorization in neural networks. In USENIX Security Symposium (USENIX Security 19), pp. 267-284, 2019.
Xiaoyu Chen, Kai Zheng, Zixin Zhou, Yunchang Yang. Wei Chen, and Liwei Wang. (locally) differ- entially private combinatorial semi-bandits. In International Conference Machine Learning, pp. 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-50) 1952.
Sayak Ray Chowdhury and Xingyu Zhou Differentially private regret minimization in episodic markov decision processes. arXiv preprint arXiv:2112.105500 2021.
Sayak Ray Chowdhury, Xingyu Zhou, and Ness Shroff. Adaptive control of differentially private linear quadratic systems. 202/ IEEE International Symposium on Information Theory (ISIT), pp. 485-490. IEEE, 2021.
Chris Cundy and Stefano Ermon. Privacy-constrainee policies via mutual information regularized policy gradients. arXiv preprint w.Xi:220/2.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, pp.
5713-5723, 2017.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint 10030 2016.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 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 1-407, 2014.
10

---

Under review as a conference paper at ICLR 2023
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, pp. 387-412. PMLR, 2018.
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 Mchta. Optimal algorithms for private online learning in a stochastic environment. arXiv preprint arXiv:2102.07922: 2021.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pp. 4870-4879, PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function upproximation. Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In International Conference on Machine Learning, pp. 5084-5096. 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-385 2017.
Jonathan Lebensold, William Hamilton, Borja Balle, and Doina Precup. Actor critic with differentially private critic. arXiv preprint arXiv:1910.05876, 2019.
Chonghua Liao, Jiafan He, and Quanquan Gu. Locally differentially private reinforcement learning for linear mixture markov decision processes. arXiv preprint arXiv:21 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 12.05:211..01585, 2021.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion. Conference on 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.
George Nemhauser and Laurence Wolsey, Polynomial- algorithms for linear programming. Integer and Combinatorial Optimization, pp. 146-181, 1988.
Dung Daniel Ngo, Giuseppe Vietri, and Zhiwei Steven Wu. Improved regret for differentially private exploration in linear mdp. arXiv preprint arXiv:2202.01292, 2022.
Hajime Ono and Tsubasa Takahashi. Locally private distributed reinforcement learning. arXiv
preprint arXiv:2001. ////000/.111.......1 2020.
Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficient reinforcement learning with ITglog(T) switching cost. Proceedings of the 39th International Conference on Machine Learning, pp. 18031-18061. PMLR, 2022.
11

---

Under review as a conference paper at ICLR 2023
Aniruddh Raghu, Matthieu Komorowski, Leo Anthony Celi, Peter Szolovits, and Marzyeh Ghas- semi. Continuous state-space models for optimal sepsis treatment: a deep reinforcement learning approach. In Machine Learning for Healthcare Conference, pp. 147-163, 2017.
Rachel Redberg and Yu-Xiang Wang. Privately publishable per-instance privacy. Advances 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):70-76, 2017.
Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31, 2018.
Karthik Sridharan. A gentle introduction concentration inequalities. Dept. Comput. Sci., Cornell Univ. Tech. Rep, 2002.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
Aristide Charles Yedia Tossou and Christos Dimitrakakis. Achieving privacy in the adversarial multi-armed bandit. In Thirty-First 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):3777-3200, 2014.
Giuseppe Vietri, Borja Balle, Akshay Krishnamurthy, and Steven Wu. Private reinforcement learning with pac and regret guarantees. International Conference on Machine Learning, pp. 9754-9764, PMLR, 2020.
Baoxiang Wang and Nidhi Hegde. Privacy-preserving q-learning with functional noise 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, 2021.
Tengyang Xie, Philip S Thomas, and Gerome Miklau. Privacy preserving off-policy evaluation. arXiv preprint arXiv: 2019.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. 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-efiiiient offline and online reinforcement learning. Advances in neural information processing systems, 2021b.
Ming Yin and Yu-Xiang Wang- Asymptotically efficient off-policy evaluation for tabular reinforce- ment learning. International Conference on Artificial Intelligence and Statistics, pp. 3948-3958.
PMLR, 2020.
Ming Yin and Yu-Xiang Wang. Optimal uniform ope and model-based offline reinforcement learning in time-homogeneous, reward-free and task-agnostic settings. Advances in neural information processing systems, 2021a.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances 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, pp. 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 preprint arXiv:2203.05800 2022.
12

---

Under review as a conference paper at ICLR 2023
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. In International Conference on Machine Learning, pp. 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.
Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems, 33:12300- 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, pp. 4532-4576. PMLR, 2021.
Xingyu Zhou. Differentially private reinforcement learning with linear function approximation. arXiv preprint arXiv:2201.0700 2022.
13


Reviews:
[{"review_id": "Y615QHk8ED9", "reviewer": "Reviewer_g4wC", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides an algorithm for Differentially-Private offline reinforcement learning, for the tabular and linear MDP settings.", "summary_of_the_review": "While the topic of the paper is important, has good motivation, and is novel, the paper is very difficult to read and may contain errors.", "strength_and_weaknesses": "Strengths\n- the problem is interesting and has good motivation:  protection of sensitive information in the trajectories saved in offline reinforcement learning, and this is especially important in healthcare and financial contexts.\n\nWeaknesses\n1.  The paper is not clearly written.  Objects and variables are used without proper notation or introduction.  For instance I'm assuming $n$ is the number of trajectories in the dataset, but this doesn't seem to be stated.  What is $\\phi(s,a)$, used in algorithm 2?\nAlso, the theorems can be stated more clearly.  For instance Theorem 3.1 has parentheses with phrases that distract from the reading of the theorem - this should be re-written.\n2.  It's not obvious how the noise value $\\sigma^2$ is derived for Algorithm 1.  Shouldn't the l2 sensitivity of the counts be $Hn\\sqrt{n}$, and so $\\sigma^2= H^2n^3/(2\\rho)$ ?\n3.  Too much information is relegated to the appendix, to the extent that it isn't easy to the read the paper without reading the appendix.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "QSZL9UQo_WN", "reviewer": "Reviewer_txBL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes two privacy-preserved (i.e., DP Guaranteed) versions of existing offline RL algorithms (i.e., APVI and VAPVI) proposed in previous works . DP-APVI  is for tabular settings and  DP-VAPVI  for the case with linear function approximation (under linear MDP assumption). The authors provide theoretical analysis and also simulation results to confirm their theoretical analysis and show that their DP Guaranteed algorithms come with little drop in utility. ", "summary_of_the_review": "Overall, the paper is well motivated, aiming to solve an important problem in the area of offline reinforcement learning. The work is theoretically well grounded, and well organized. As said the novelty is low, and I think it lacks enough experimental evaluation.", "strength_and_weaknesses": "Strength:\n* Addresses an important problem in offline RL\n* The paper is well organized, theoretically grounded\n\nWeakness:\n* Lack of empirical evaluation such as experimentations on benchmark tasks such as D4RL. Additionally is there any reason that there is no simulation results for DP-APVI algorithm ? \n* Incremental Novelty. Would be nice to distinguish more clearly the novelty of this paper from previous offline works (i.e., VAPVI).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FeHlNpJy9bn", "reviewer": "Reviewer_MbLZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes offline RL algorithms with DP guarantees for tabular case and linear MDP. The key components are the private estimates of the visitation counts/conditional variance based on the Gaussian Mechanism, with some modifications to allow the use of existing pessimism-based value iteration algorithms. The paper provides privacy guarantees and utility guarantees for the proposed algorithms, and an empirical study to support the theoretical findings. ", "summary_of_the_review": "In summary, I am giving a weak accept recommendation, conditional on the empirical section can be improved as suggested. I think the paper can have a significant contribution to the offline RL community as a first step towards more practical DP offline RL algorithms, however, some improvements are required as mentioned in my comments on weakness and clarity. I would be happy to raise my score if the concerns are addressed. \n\n------Post-rebuttal update------  \nAfter the author response and internal discussions with other reviewers and AC, I think my concerns about the presentation clarity and the empirical study have not been fully addressed. I think these issues are not difficult to address, however, the authors did not upload a revision. Therefore, I think the paper requires some improvements before being published, and I slightly lowered my score to 5. However, I encourage the authors to keep improving the paper and re-submit to a future conference. ", "strength_and_weaknesses": "**Strength**\n- The paper proposes a new offline RL algorithm with DP, which is claimed to be the first DP RL algorithm in the offline setting. I think the paper can have significant contribution to the offline RL community. \n- The paper in general is clearly-written and easy to follow. \n- The theoretical analysis is sound (although I acknowledge that I only check the proof for tabular case, and didn’t check the proof for linear MDP carefully).   \n\n**Weaknesses**\n- The definition of DP for the RL setting used in the paper is not well-motivated (see comments below).\n- The presentation of the key components in Algorithm 1 and Algorithm 2 is not very clear to me (see the next part on quality and clarity).\n- Major improvement is required for the empirical study.\n\n**DP Definition**  \nThe paper defines neighboring datasets as two datasets that differ in one trajectory. However, I can think of other definitions in the RL setting. For example, two datasets that differ in one transition, or differ in one observed reward (if we want to preserve the privacy for reward only). The paper should provide more motivation for this particular definition used here, and discuss how existing work define DP in the RL setting. \n\n**Empirical study**  \nI think the empirical study requires some improvements. The empirical study is supposed to support the theocratical findings, but I think the current results raise more concerns.  \n\nFirst of all, the results do not have error bars, so I don’t know whether the difference are statistically significant. Please include the error bar in the results. Moreover, the paper mentions\n> as the size of dataset goes larger, the performance of DP-VAPVI will converge to that of VAPVI\n\nI don’t see the performance of DP-VAPVI converges to the non-private one in Figure 1. Maybe try to run the experiments with more episodes. Otherwise, I think this observation is not true. \n\nFinally, please explain how significant the difference in performance between the private and non-private ones are. For example, non-private gets a suboptimality gap ~= 1, while the private one with $\\rho = 5$ gets a gap ~= 2. Is the difference (i.e., 1) significant? What is the range here? What value of $\\rho$ is commonly used in practice?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject