On the Sample Complexity of Differentially Private Policy Optimization
Authors: Yi He
Xingyu Zhou
Venue: NeurIPS 2025 poster ()
Keywords: Policy optimization
differential privacy
policy gradient
natural policy gradient
sample complexity
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We establish the first set of sample complexity bounds for private policy optimization

Abstract: Policy optimization (PO) is a cornerstone of modern reinforcement learning (RL), with diverse applications spanning robotics, healthcare, and large language model training. The increasing deployment of PO in sensitive domains, however, raises significant privacy concerns. In this paper, we initiate a theoretical study of differentially private policy optimization, focusing explicitly on its sample complexity. We first formalize an appropriate definition of differential privacy (DP) tailored to PO, addressing the inherent challenges arising from on-policy learning dynamics and the subtlety involved in defining the unit of privacy. We then systematically analyze the sample complexity of widely-used PO algorithms, including policy gradient (PG), natural policy gradient (NPG) and more, under DP constraints and various settings,  via a unified framework. Our theoretical results demonstrate that privacy costs can often manifest as lower-order terms in the sample complexity, while also highlighting subtle yet important observations in private PO settings. These offer valuable practical insights for privacy-preserving PO algorithms.

On the Sample Complexity of Differentially Private Policy Optimization
He Wayne State University yihe wayne.edu
Xingyu Zhou Wayne State University
xingyu.zhou @ wayne.edu
Abstract
Policy optimization (PO) is a cornerstone of modern reinforcement learning (RL), with diverse applications spanning robotics, healthcare, and large language model training. The increasing deployment of PO in sensitive domains, however, raises significant privacy concerns. In this paper, we initiate theoretical study of differ- entially private policy optimization, focusing explicitly on its sample complexity. We first formalize appropriate definition of differential privacy (DP) tailored PO, addressing the inherent challenges arising from on-policy learning dynamics and the subtlety involved in defining the unit of privacy. We then systematically analyze the sample complexity of widely-used PO algorithms, including policy gradient (PG), natural policy gradient (NPG) and more, under DP constraints and various settings, via a unified framework. Our theoretical results demonstrate that privacy costs can often manifest as lower-order terms in the sample complexity, while also highlighting subtle yet important observations in private PO settings. PO algorithms.
These offer valuable practical insights for
1 Introduction
Policy Optimization (PO) such as REINFORCE [1, 2], proximal policy optimization (PPO) [3] and group relative policy optimization (GRPO) [4] has gained increasing interest recently across various applications. Due its popularity, there is a rich literature that provides various theoretical understandings of different PO methods (c.g., iteration or sample complexity [5-8]).
As PO becomes increasingly prevalent in real-world applications, privacy concerns are emerging as a critical challenge. For instance, personalized medical care, patient interactions wwhre the state represents medical history, the action corresponds to prescribed medication. and the reward reflects treatment effectiveness- conssiiit sensitive data that must be protected. Similarly, RL- based training of large language models (LL.Ms), user prompts may contain private information that requires protection.
fact, recent empirical work has shown that standard GRPO indeed has privacy leakage issues [9]. Hence, addressing these privacy concerns is essential for ensuring the responsible deployment of PO methods in sensitive domains.
Contribution. In this paper, we initiate the theoretical study of differentially private policy optimiza- tion, focusing on the central question: What's the sample complexity cost induced by differential privacy in PO? To this end, we first carefully define a suitable notion of differential privacy (DP) [10] for PO. highlighting its distinctions from the standard DP definitions used in supervised learning. These differences stem from the unique learning dynamics and the notion of the privacy unit in PO. Then, we propose meta algorithm for private PO, which enables us to study private policy gradient with REINFORCE (DP-PG), private natural policy gradient (NPG) [11] (DP-NPG), and private version of REBEL recently proposed in [12] -REBE) in a unified perspective. Moreover, for DP-NPG and DP-REBEL, further reduce PO to sequence of private regression problems, thus allowing to
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

leverage various well-established results in private estimation and supervised learning. Throughout this process, we not only highlight the difference between DP-PG and DP-NPG, but also uncover some subtleties when applying private regression results within the current analytical framework of PO. The key takeaway from our theoretical results that the privacy cost can often appear as lower-order terms in the overall sample complexity. Meanwhile, it is worth noting that structural properties of the underlying problem can further improve both statistical and computational efficiency.
Related work. We mainly discuss the most relevant work here and relegate a detailed discussion to Appendix A. The very recent work [13] studies private PG, but mainly from an empirical perspective without sample complexity bounds. From the online regret perspective, optimistic PPO has been studied in the tabular case [14] and linear case [15], respectively. In contrast, we aim to consider general function classes from the optimization perspective. We also note that NPG with softmax or log-linear policy is equivalent to PPO. The authors of [16] study private policy evaluation, which aims to evaluate a given policy rather than finding the best policy in policy optimization. From an application perspective, [17] applies private PPO for LLM alignment via reinforcement learning from human feedback (RLHF).
2 Preliminaries
Policy optimization (PO). In this work, instead of considering a general Markov decision process (MDP), we focus on the simpler bandit formulation, which allows to easily demonstrate the key ideas. We note that generalizing it to MDP is standard, as done in the literature [6. 18]. This bandit formulation already captures many interesting real-world applications, such as personalized medical care [19] and alignmentreasonnig training in large language models (LLMs) [20]. In particular, given prompt in LLMs) sampled from distribution p. an
an initial state E X (e.g., medical status action y E y (c.g., a medical prescription or a response LLMs) is generated according to a policy and reward r(z, y) E |- Rmax Rmax] is observed. In policy optimization, we parameterize the policy by xe with 0 E θ = Rd (e.g.. neural network), and the goal is to leverage interactions (e.g., sample trajectories) to find an optimal policy that maximizes the following objective:
( = (() == Eapp..rr (+1x) [r( v)]
Vanilla policy gradient (PG). One simple and direct approach to solving the above policy optimiza- tion problem via vanilla policy gradient, i.e., O 0, + 7/ J(,,), where 7) >> 0 some learning rate, v.((e) is the gradient at step f, and 0₁ is some initial value. The gradient can be written as follows by the classic policy gradient theorem
((()) = EE-p. [A (I, y) V log ne (y/xz),
where A 1 (x, r(x, v) - (yy-ro v²) is the advantage function.
Natural policy gradient (NPG). Another approach to solving the PO problem is natural policy gradient (NPG) [1]], which uses the Fisher information matrix as the preconditioner to account for the geometry. Specifically,, the NPG update given by 0++1 0, + 1/FF J(:)) where (0) := Ex=pprrroo-la) (V log (2(y)z)) log [)(2)>)] is the expected Fisher information matrix (with superscript being the Moore-Penrose pseudoinver) and (..))) is the same before. An cquivalent way to write the above update is the following [5]
0 0, + 17 We, Wy E argmin E Be-p.yvoa, m) (A (I, w V Vllg (
(2)
which essentially reduces PO to a sequence of regression problems.
Regression to Relative Reward Based RL (REBEL). Recently, simple and scalable PO algorithm called REBEL is proposed in [12], which also reduces PO to a sequence of regression problems, but now over relative reward difference, motivated from the DPO-style reparameterization trick in [21].
In the expected form, the update under REBEL is given by
[L "1)
Te x) In
To x)
0.t1 argmin E In
-(1(2, ()(,,)) (((r,,))r(r(/)))
(3)
9
To. (y x)
no. (v' (x)
where the expectation here over x ~ P: y ~ (((1)), V ~ no, (-1x)), and μ can be either on-policy distribution ne, any offline reference policy.

---

Sample complexity. All the aforementioned ideal policy updates (e.g., full gradient) involve expecta- tion, which is often difficult to compute in practice due to both statistical (e.g., without knowing p) and computational (e.g., averaging over all possible trajectories) issues. Thus, one needs to replace the expectation with a sample-based estimate by sampling dataset of trajectories at each iteration from
an underlying distribution. The sample complexity typically refers to the total number of sampled trajectories for finding an a-optimal policy (i.e., J(T)) - J(T) S a).
In this paper, our ultimate goal is to formally introduce differential privacy (DP) into the problem of policy optimization and derive the sample complexity bounds under privacy constraints. To this end, we need to carefully define both privacy and samples in the private case, as discussed next.
3 Differential Privacy in Policy Optimization
In this section, we formally introduce DP to PO, highlighting some subtleties compared with standard DP in supervised learning problems. We first recall the standard DP definition with a fixed dataset.
Definition 1 (Dwork et al. [10]. A randomized mechanism M satisfies (s, 6)-DP if for any adjacent datasets D, D' differing by one record, and AS C Range(M):
P[M(D) E S) < of P[M(D') E S) +.
This standard DP notion can be directly used in supervised learning problems with D being a set of ii.d samples (2 y4) } from an unknown distribution and .MDD being the final model. This has been utilized in private empirical risk minimization (ERM) [22, 23] as well as private stochastic optimization (both convex and non-convex), e.g., Bassily et al. [24]. For example, the optimal excess population risk for stochastic convex optimization is O&(1/VN + vd/(N)) for (c, D)DD, where d is the dimension of the parameter space.
One may attempt to adopt the above notion directly to PO with the dataset D being {(T;, yi ) and M(D) being the final policy. However, this does not make too much sense because (i) there is no such a fixed dataset in PO as the actions are often sampled in the on m--policy fashion, i.e., using the most recent policy: (ii) the neighboring relation of differing in one sample (I,, y44 (i.e., privacy unit) actually does not hold as changing one sample will lead to difference in all future samples due to different policies onward. Thus, we need a new definition that can address the above two issues. Before proceeding, we consider two motivating examples to illustrate the subtlety.
Example 1 (SFT vs. RL fine-tuning in L.Ls)). Consider a reasoning task in L.Mss. With supervised fine-tuning (SFT), we are given fixed dataset of pairs ((1;, v))) == where x; is the prompt/question and y; is the correct answer. Standard DP is natural here, which ensures that changing one sample (zi, y4) will not change the final policy too much. On the other hand, if one uses RL (c.g., PPO) to do the fine-tuning, then the given dataset consists of only prompts, as the answers are generated on the fly. So, proper privacy unit here is protect each prompt in the sense that changing one prompt will not change the policy too much.
Example (Supervised learning vs. RL for healthcare). In this case, to train a healthcare system, one can supervised learning approach by collecting dataset of {x;; 3/ )) where x; is the medical status and y/ is the recommended medicine. One can also adopt an RL approach (even in an online manner) where the dataset consists of (stream) set of users/patients, each with medical status I; sampled from a distribution while the recommendation yi can only be determined on the fly. The privacy protection is that changing one user/patient will not change the final policy too much.
To handle both scenarios, we borrow the idea from private online bandit and RL. literature [25, 14], which essentially considers a set of "users" as the dataset. For instance, the dataset could be N unique patients interacting with the learning agent, and each user has an initial state (c.g., medical status), which distributed according to p. We can fix the "users" in advance (or arrive online) and the privacy unit is now for each patient, hence resolving both issues above. Meanwhile, the set of "users" " can also represent N (static) prompts in the fine-tune menttning of LLMs, with each "user" contributing one prompt. Note that although we use "users" to align with personalization application, this is still an item-level DP, as each "user" appears only once (as a patient or prompt). The learning agent can interact with each "user" to observe (ær, y) and r(x, v) dynamically, i.e., on-the-fly. With the above notion of dataset, the privacy protection PO is that changing one "user" in the dataset will not change the final policy too much, leading to the following definition.
3

---

Definition 2 (DP in PO). Consider any policy optimization algorithm M interacting with set D of N "users" and M(D being the final output policy. We say M is (z. 8)D if for any adjacent datasets D, D' differing by one "user", and AS [ Range(M):
P[M(D) E S] E of P[M((D) E +
We emphasize that the above DP notion is defined for the problem PO rather than for specific algorithm, analogous to the standard DP in statistical learning (e.g., supervised learning). In this paper, we aim to design some private variants of PO methods (DP-PG, DP-NPG, DP- -RRELL) and analyze their sample complexity under the above privacy constraint.
Remark
4 A Meta Algorithm for Private PO
In this section, we present a meta algorithm for private PO, which builds upon a unified view of PG, NPG, and REBEL. We believe that this meta viewpoint is also interesting in the non- non-private case.
Our meta algorithm is given by Algorithm which essentially batched one-pass algorithm. In particular, at each iteration f, the learner collects m fresh samples by sampling from a distribution over x and y. To be more specific, one can view each sample (I,, y/, v/) as generated via interaction with new fresh "user", which provides the context/prompt r;. Then, leveraging the dataset D, and specific PrivUpdate oracle, the learner finds the next policy iteratively.
Algorithm 1 A Meta Algorithm
1: Input: reward r, learning rate 77, batch size m, and policy class TT, PrivUpdate oracle, base policy μ
2: Initialize 01 0
3: for wart=1..... T do
4: Collect a fresh dataset D. {12 Vi, v/ of size using the no, and μ::
32 P. Vi pl ((-124), of no, (-12;;
5: For all i E [m)] let Ae 34) == r(x; U/) - r(ri y/) be the estimate of T (Iz, Vi)
6: Call a Pri PrivUpdate oracle D: : ((T,, Mr. v/. Ae w))) to find next policy 0,-1
7: end for
Under this one-pass algorithm design, we naturally have the following privacy guarantee, connecting standard DP (Definition 1) with DP in PO (Definition 2). Proposition 1. Suppose PrivUpdate satisfies (s, 6 under Definition 1, then Algorithum I satisfies (E in terms of Definition 2.
This simply follows from our one-pass algorithm and (adaptive) parallel composition of DP, by noting that changing one "user" would only change one record in D, of a single E [T].
Remark 2. Our meta algorithm can also be used in the online setting where a stream of N "users" arrive sequentially. By the so-called billboard lemma [26], our meta algorithm also satisfies the commonly used joint differential privacy (JDP) in the literature of private online RL/bandits [25, 27, 14, 15, 28]. Roughly speaking, JDP guarantees that changing one "user" (say u) will not change all the actions prescribed to all other "users" except u, as well as the final policy.
For sample complexity, due to the batched one- one-pass algorithm over N unique "users", the total number of sampled trajectories is simply N fresh user. To put it in another way, for a fixed N, the key here is to balance between batch size m and number of iterations T so to balance between the per-iteration accuracy and the total number of updates. This balance, in turn, depends on the specific choice of PrivUpdate oracle, which will be instantiated in the next sections for DP-PG, DP-NPG, DP-REBEL, respectively.
T, where each trajectory (I1, Vs, v/4 is from
5 Differentially Private Policy Gradient
In this section, we propose DP-PG by building upon our meta algorithm and analyze its sample complexity bounds under different settings.

---

Our proposed DP-PG is Algorithm with the instantiation of PrivUpdate as in Algorithm 2 below. In particular, it first computes an unbiased REINFORCE-style estimate (i.e., (0)) of the full gradient ((,,, as (1), using the m trajectories in D. Then, a Gaussian noise is added with o² depending the privacy parameters of e and 6. Finally, θ(+1 is obtained by updating the current policy 9r along the direction of Gt, scaled by a properly chosen learning rate 1).
Algorithm 2 PrivUpdate Instantiation for DP-PG
1: Input: dataset D, (2,, Vo: (2,, y))) policy 8,, learning rate n, noise scale
2: Output: 0t+1
3: Compute gradient
m(]( == V log To, (yi [.))) Ax ys)
4: Add noise: gt == v ((O) + +N(00 o2)
5: Output policy: 0--1 0, 17 9t
By the standard Gaussian mechanism [29] and Proposition 1, we have the following privacy guarantee. Theorem (Privacy guarantee). Assume for any x X and O, there exists a constant G such that [IV log (o
x))| & G. Then, setling o² 16.25(1.25//) R2 in Algorithm 2 ensures that DP-PG satisfies (e, 8)-DP as in Definition
m²
The boundedness assumption of G is satisfied by softmax policy as well as Gaussian policy [6]. In fact, they satisfy even stronger condition in Assumption 1, to be discussed shortly.
Next, we aim establish the sample complexity results of our DP-PG with Algorithm 2 for both first-order stationary point (FOSP) and global optimum convergence, respectively.
5.1 First-order Stationary Point Convergence
We start with the sample complexity bound for FOSP convergence. This result is not only of its own importance, but will also be useful for our later results on the global optimum convergence. We will consider the following general class of policies, which is widely studied in previous non-private work and also includes commonly used policies such as softmax and Gaussian policy [6].
Assumption 1 (Lipschitz Smoothness (LS)). There exist constants G, F > 0 such that for every state x E X, the gradient and Hessian of log Tp(: (: x)) any
satisfy
Va log No [y][)>)]| < G and VV log To (u(ya>)) < F.
Remark 3. For simplicity, in previous work, will often view G and F as constants @(1), hence omitted in the sample complexity bound. Moreover, we omit log(1/8) term by writing Os(,). Theorem 2 (FOSP convergence). Under the same setting of Theorem I and Assumption 1, there exists a proper parameter choices of m. and n, such that DP-PG achieves
2/3
Vd
E [[ Ob
VN
N
where Gr is uniformly sampled from (0,....,,77
Remark We can see that the first term in (4) matches the previous non-private term, i.c., for an accuracy of a, the sample complexity is ((1/a²) [6]; Second, the privacy cost is a lower order additive term (for constant e and d), i.e., the additional sample complexity due to privacy is Og a
vd
5.2 Global Optimum Convergence
We now turn our focus to the global optimum convergence in the sense of average regret, i.e., J J + E [J.))]- Following the non-private work [6], we will also consider two different scenarios and aim to establish the corresponding sample complexities in the private case.
5

---

In the first scenario, in addition to Assumption 1, we further assume the following two conditions on the policy class, both of which are commonly used the non-private case. The first condition the so-called
policy, formally defined below.
Assumption 2 (Fisher-now noneer-oo-deee non-degenerate, adapted from Assumption 2.1 of Ding et al. [30]). For all / E IR there exists y >> 0 s.t. the Fisher information matrix (0) induced by policy na and initial state distribution satisfies
(0 (
[V log (1) [ Vo (u(()))) -I2-
This assumption is commonly used in the literature non-private PG methods [6, 30, 5, 31]. As shown in Sec B.2 in Ding et al. [30], this assumption is satisfied by the Gaussian policy and even certain neural policies.
The next condition the so-called compatible function approximation, which is also a common assumption in the PG literature to handle function approximation error in the non-tabular case.
Assumption 3 (Compatible, adapted from Assumption 4.6 in Ding et al. [30]). For 0 E R4, there
exists Olbaas > 0 such that the transferred compatible function approximation error satisfies
Basparaa (-1a) [(AT (Ir, y) u Vo log No {o(y)))) & Olbias:
where Tg- is an optimal policy and u² = (O)
The "compatible" here means that the Ve log Myy (a|s) )) as the feature vector; The "transfer error" here means that we are shifting to the expectation over optimal policy (rather than the current policy). The error Obias is zero for softmax tabular policy and small when my is a rich neural policy. [30-32].
approximating the advantage function A a) using
With the above two additional assumptions along with the LS assumption in Assumption 1, we have the following important result, which implics that the objective (0) satisfies the so-called relaxed weak gradient domination.
Lemma (Lemma 4.7 in Ding et al. [30]). If the policy class no satisfies Assumptions 1, 2 and 3, then have
G |VJ + / /Obias
J - J(0)
This lemma essentially allows to easily translate guarantee in terms of FOSP certain global optimum convergence. This leads to our next main result with its proof given in Appendix E.2.
Theorem 3. Consider the same setling of Theorem 2 and farther let Assumptions 2 and 3 hold, Then, for any > 0, DP-PG enjoys the following average regret guarantee
E B(J())) < <0(a) + (Vatiass)
when the sample size satisfies N O5
Remark 5, In the above bound, explicitly include the parameter 7 to clearly illustrate its impact. The first term O
matches the non-private one in Yuan et al. [6] while the second term the privacy cost. As we can see, for both terms, there exists an additional 1/r factor compared to the sample complexity of FOSP. Thus, for very small but still positive y, our bound could be large.
Our second scenario is about the specific policy class of softmax in the tabular setting, which allows us to get rid of the parameter y. Due space limit, we relegate these results to Appendix B.
Differentially Private NPG and REBEL
In this section, we turn to DP-NPG and DP- private variants of NPG and RRBEL, and analyze their sample complexities. In particular, we will consider general private regression oracle as the PrivUpdate in Algorithm 1 and then give concrete examples under different specific regression oracles. Given the similarity, we will mainly focus on DP-NPG in the main paper and relegate the detailed discussion on DP- RE-REBEL to Appendix D.

---

6.1 A Master Algorithm and Guarantee
Our proposed DP-NPG is Algorithm with its PrivUpdate being instantiated in Algorithm 3 below, which relies on general private regression oracle to return an approximate minimizer of an estimation problem under the square loss. The square loss in (6) is almost the same as before, as (2), except that we now take the expectation over a general base policy rather than the specific on-policy ng, This update is often called approximate NPG in the literature [5]. As will be shown later, the performance of the algorithm will depend the choice of in terms of its coverage.
Algorithm 3 PrivUpdate Instantiation for DP-NPG
1: Input: D, ((T,, Mi, Ae(x,, ==) current policy 0,, base policy μs learning rate 7, PrivLS oracle
2: Output: 01+1
3: Call the PrivLS oracle on Dj = {(Ii, Vis (x vi))3 find an approximate minimizer w, of (
argmin F((w) -pmp.or1((1)) (ATH (z, y) w T log To, (v1z))
(6)
wEW
4: Output policy 0c11 0₁ 1pwe
We now aim to establish generic performance guarantee of DP-NPG. To start with, we assume that the approximate minimizer wi returned by PrivL. each iteration satisfies the following guarantee. Assumption 4 (Private estimation error). For each E [T], the PrivLS oracle satisfies (s, 0DD while ensuring that with probability at least 1 -.
B Ez-par=((la) [AATH (x, W, V log xe, (vlz)) < (m, 8,C),
for some emror function err? (m, E, <) over batch size m, privacy parameters E, 6, and probability In addition, we assume standard regularity assumptions commonly used even in the non-private case. Assumption 5 (9-smoothness and boundedness). log ()(2)z) is a 8-smooth function of for all x, y, i.c..
Ve log To (y(=)) Ver log ner (y|x)]l2 & B |0 0'112.
Moreover, there exists constant W 0 such that for all t [2]. the weight vectors w; generated by the update rule satisfy [well2 I W.
Our main result given by the following theorem.
Theorem 4 (Master theorem). Let Assumptions and hold. Then, DP-NPG satisfies (E,5)-DP as in Definition 2. Moreover, if क := Te, uniform distribution at each state and 1) probability at least - Ç, for any comparator policy x we have
2log y
TBWT. with
1 T
3W2 log D
VC
J(TT) T
Σ
((T)
<
Σ emr,
27
T
t=1
where CR- max
x Cylar (()))
and Te,
We use the most intuitive coverage definition for Ca-sr+ i.e., the density ratio, for illustrating the key idea. One can easily extend it to other types of coverage, e.g., relative condition number for the linear case [5] and transfer coefficient for general function classes [33].
6.2 Applications
With the above master theorem in hand, we now only need to determine the estimation error under different types of PrivLs. To start with, we consider a general PrivLS under general function classes for both reward and policy. Specifically, it runs approximate least squares with the exponential
7

---

mechanism [34] for privacy protection, as detailed in Algorithm 4 below. To determine its estimation error, we will first present a new result, which could be independent interest.
Algorithm 4 PrivLS Instantiation for DP-NPG via Exponential Mechanism
Input: D; [(14, yr, Az(z,, 31)) H/)) privacy budget E, current policy 0,, reward range Rmax
2: Output: W/
3: Sample wy E W with the following distribution:
(- 8/82
P(w) x exp
((w)) Vw w,
where L(w) ;= : w V log Te, (vilzz)) Ar(
Lemma (Private LS with exponential mechanism). Let R O, S (0. 1), we consider a general
sequential estimation setting with instance spuce U and larget space Z. Let H. u + |-R, R2] be a class of real-valued functions. Let D {uss 2x) )r) be a dutaset of m points where u, ~ ps = ps(wisi z1si-1,, and z = h (w;) + tbe where q is zero-mean noise and he satisfies approximate realizability, ie.,
inf GEH m
Σ B Burp, ((h( h(u)) &
Cappprox
Suppose max; |2al & R and max (h² & R. Then, sampling hn via the following distribution from exponential mechanism
P(h) x exp (-
8 L(i)
4h E H.
8R²
with L(h) = Eim =13² yields that
E Eu-o: 11" (14))) & Rloog( HI/C) + R² log( (H//S) >
m
log((H(((S)
Oapprox-
This lemma can be viewed as the private variant of Lemma 15 in [33]. To leverage this lemma for Algorithm 4, we observe the following mappings for each iteration t: H. maps to W, u, (To, Ty yt). M(u,) = w T V log To, (ys [x)) 2; = Ax, yi) with E [2]] = A (æ,, yi), which can be rewritten as an unknown function u² h" over (mo, Fz. y/). Finally, in case, P: is non-sequential and fixed during each update, i.e., D; ~ P. Yi p(-(2;) and To, is fixed at t. Thus, the approximation error condition in (7) translates the following one:
(a=poru(-10) [(ATHL (z,y) w T WEW
inf
V log no, To, (ylx)²] < Oaapprox-
(8)
Based on these discussions, we have the following guarantee of DP-NPG with Algorithm 4. Corollary 1 (General function class). Consider DP-NPG with PrivLS Algorithm 4. Then, DP-NPG satisfies (e, -D. Suppose for each t E [T], there exists an Clapprox such that (8) holds. Then, under the same assumptions in Theorem 4, we have
1 Σ J(TT) T
3W2 log y T
Cu-osr + y Cu-os (1 1/E) log (W/(C)
J(TT) S
m
This implies that, for given suboptimality gap of O(a + / Qapproo) the sample complexity bound is N = m = (( +++)+ log 332).
Remark Several remarks are in order. First, due to the exponential mechanism, we achieve pure DP (i.e.,& 8 = 0) rather than approximate DP: Second, our results hold for general reward and policy function classes. We state the result for a finite W for ease of presentation. It can be easily extended for infinite class using standard covering argument. For instance, if W Rd then log(DW) can

---

be converted to (d). Meanwhile, we remark that in general, Algorithm 4 is not computationally efficient. Thus, the above result is mainly from the statistical perspective. Note that we also explore several efficient oracles for specific scenarios later. Finally, we highlight that the approximation error in (8) different from the transfer error (5), which directly takes expectation over the target optimal policy. In contrast, when we use Oapprox we have to account for the transition from js to x² explicitly via Cp- This is the case even in the non-private case (cf. Corollary 21 in [5].
Log-linear policy class with realizability. We now turn to computationally efficient PrivLS oracles by considering concrete case where the policy is log-linear and reward r is realizable. More specifically. the policy Th is given by some 0 E Rd and feature vector ΦN.y E IRd with exp(0" ex.u) Evecy (xp(( )x.y?) and [1 - B.
T x²)
This leads the fact that Vo log (y(zr) &n,y Byy-wooo-laa) [6x,y'] (=)))))
and smoothness parameter of B², Further, we assume the reward r(z, y) = (w* Sn..)) is linear function with respect to &z.gr i.e. compatible realizability. In this case, Assumption 4 reduces to estimation error (or in-distribution generalization error) of linear regression:
Bawpsrru(t1)) ((ur - w", 3h )²) & (m, e, s,
where 0% := 22.9 Byraa (a)]oayy which depends on the current policy.
The above particular form allows us to leverage recent advances in private linear regression, both in the now-dimension and high-dimenen
cases, respectively.
Corollary 2 (Log-linear policy in low-dimension). Consider DP-NPG with the above log-linear class (with smoothness parameter B = B²). Suppose PrivLS is instantiated with the ISSP algorithm in [35]. Then, by [35, Theorem 5], we have that erı,(m,,, & a. when >
Thus, by Theorem 4, for a suboptimality gap of O()), the d dvlog(1/8) d(log(/88) 62
sample complexity bound is N T m = Ög ((.t + are a=c (.a))B2W'
Corollary 3 (Log-linear policy in high-dimension). Consider DP-NPG with the above log-linear class (with smoothness parameter B B²2) Suppose PrivLS is instantiated with Algo- rithm 5 in [36]. Then, by 136, Theorem 6.21, we have that e,,
a when m 2 Thus. by Theorem for a suboptimality gap of O(a), the sample complexity bound is N = Tm m = Ōs (1) + +b))) -B2W).
δ log(1/S) + /C)g(1/))log(11)) a²
One key subtlety behind these two corollaries is that W can be large and depend on d. This is due to the fact that the update in both PrivLS oracles is privatized by Gaussian noise in the last step. Thus, by standard concentration of Gaussian vector, W can be on the order of /d. This subtlety somewhat unique due to the interplay between PrivLS oracle and "regret-lemma"" type analysis in Theorem 4. In practice, one can properly truncate We, which preserves privacy. In theory, we conjecture that one may use different technique (e.g.. based on the three-point lemma in [37]) to avoid the requirement of bounded wy, which is left to be an exciting future work.
Connection to private stochastic optimization. In the context of the above discussion and corollaries, one in in-between solution is to aim for suffering dimension dependence only in the private term. This leads us to consider private SGD over a bounded domain, since the estimation error in (9) is equivalent to excess population risk under realizability. Thus, one can leverage existing results on private stochastic optimization to bound err,(m, s, 5, C), which does not have dimension dependence in the non private term, but at a cost of a slower rate ((1/mm) vs. O(1/m). See Appendix C.
7 Conclusion
We initiate a systematic theoretical investigation into the sample complexity of differentially private PO, leveraging a unified meta-algorithmic framework and reductions to private regression problems. We establish the first set of sample complexity results for several widely used PO algorithms under differential privacy constraints, including DP-PG, DP-NPG and DP-REBEL. Our analysis not only quantifies the privacy cost in PO but also uncovers subtle and important interplays between privacy

---

mechanisms and algorithmic structures in PO. These insights offer practical guidance for designing preecyppreerving PO methods. We hope our work will open new avenues for future research in both the theoretical understanding and empirical development of private policy optimization. Besides, although we mainly focus on the theory the main body, we have also managed to conduct some experiments as proof of concept, see Appendix H for details.
Acknowledgements
This work was supported in part by the National Science Foundation (NSF) under Grant Nos. CAREER-2441519, CNS-2312835, and CNS-2153220.
References
[1] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8:229-255 2226,256,,11 1992.
[2] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
[3] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint rrXivv1707.06347, 2017.
[4] Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.033.2 03330 2024.
[5] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1 2021.
[6] Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vamilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332-3380. PMLR, 2022.
[7] Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 34, pages 8668-5675, 2020.
[8] Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimization attains globally optimal policy, Advances neural information processing systems, 32, 2019.
[9] Yule Liu, Heyi Zhang, Jinyi Zheng, Zhen Sun, Zifan Peng, Tianshuo Cong, Yilong Yang, Xinlei He, and Zhuo Ma. Grpo privacy is at risk: A membership inference attack against reinforcement learning with verifiable rewards, 2025. URL httth::t////attt //axxiv. org/ abs abss/211... 1.11..1445.
[10] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[11] Sham M Kakade. natural policy gradient. Advances neural processin systems, 14, 2001.
[12] Zhaolin Gao, Jonathan D. Chang, Wenhao Zhan, Owen Oertell, Gokul Swamy, Kianté Brantley, Thorsten Joachims, J. Andrew Bagnell, Jason D. Lee, and Wen Sun. Rebel: Reinforcement learning via regressing relative rewards, 2024. URL ptttpp://arxivv org/ porg/abe abss/204..
[13] Alexandre Rio, Merwan Barlier, and Igor Colin. Differentially private policy gradient. arXiv preprint 17Xiv:2501.19080, 2025.
10

---

[14] Sayak Ray Chowdhury and Xingyu Zhou. Differentially private regret minimization in episodic markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 36, pages 6375-6388 2022.
[15] Xingyu Zhou, Differentially private reinforcement learning with linear function approximation. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(1):1-27, 2022.
[16] Borja Balle, Maziar Gomrokchi, and Doina Precup. Differentially private policy evaluation. In International Conference on Machine Learning, pages 2130- 2138. PMLR, 2016.
[17] Fan Wu, Huseyin A Inan, Arturs Backurs, Varun Chandrasekaran, Janardhan Kulkarni, and Robert Sim. Privately aligning language models with reinforcement learning. arXiv preprins arXiv:2310. 16960, 2023.
[18) Zhaolin Gao, Wenhao Zhan, Jonathan D Chang, Gokul Swamy, Kianté Brantley, Jason D Lee, and Wen Sun. Regressing the relative future: Efficient policy optimization for multi-turn rlhf. arXiv preprint arXiv:2410.046122 2024.
[19] Tongxin Zhou, Yingfei Wang, Lu Yan, and Yong Tan. Spoiled for choice? personalized recommendation for healthcare decisions: A multiarmed bandit approach. Information Systems Research, (4933)1493311 1512, 2023.
[20] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information prucessing systems, 35:27730-27744, 2022.
[21] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36:53728-53777 2023.
[22] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
[23] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464-473. IEEE, 2014.
[24] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances neural information processing systems, 32, 2019.
[25] 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.
[26] J Hsu, Z Huang, A Roth, T Roughgarden, and ZS Wu. Private matchings and allocations. SIAM Journal on Computing, 15:1953-1984 2016.
[27] Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31, 2018
[28) Dan Qiao and Yu-Xiang Wang. Near-optimal differentially private reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9914-9940. PMLR, 2023.
[29] Cynthia Dwork. Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, 9(3-4)2211-407 2014.
[30] Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global optimum convergence of momentum- based policy gradient. In Gustau Camps-Vall,, Francisco R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 1910-1934, PMLR, 28-30 Mar 2022.
11

---

[31] Yanli Liu, Kaiqing Zhang, Tamer Başar, and Wotao Yin. An improved analysis of (variance- reduced) policy gradient and natural policy gradient methods, 2022. URL https://arxiv: org/abs/ /tbps/221107777 07937.
[32] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence, 2019. URL https://arxxx......// http://..rgr/bb//////eaae abs91909. 01150.
[33] Yuda Song. Yifei Zhou, Ayush Sekhari, Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make rl efficient. arXiv preprint arXiv:2210.06718, 2022.
[34] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103, IEEE, 2007.
[35] Gavin Brown, Jonathan Hayase, Samuel Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C Perdomo, and Adam Smith. Insufficient statistics perturbation: Stable estimators for private least squares. arXiv preprint arXiv:2404. /5409, 2024.
[36] Fan Chen, Jiachun Li, Alexander Rakhlin, and David Simchi-Levi. Near-optimal private learning in linear contextual bandits, 2025. URL /tttps://arxiv.rrggg wttpoor.gb.........1111 13115.
[37] Rui Yuan, Simon S Du, Robert M Gower, Alessandro Lazaric, and Lin Xiao. Linear convergence of natural policy gradient methods with log-linear policies. arXiv preprint arXiv:2210.014400, 2022.
[38] Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In International conference on machine learning, pages 4026 4035. PMLR, 2018
[39] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
[40] Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. Operations Research, 1265):1906-1927, 2024.
[41] Boyi Liu, Qi Cai, Zhuoran Yang. and Zhaoran Wang. Neural proximal/rust region policy optimization attains globally optimal policy (2019). arXiv preprint arXiv: 10306, 1906.
[42] Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance- reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624-7633 2020.
[43] Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference Machine Learning, pages 6613- PMLR, 2020.
[44] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
[45] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Po-pg: Policy cover directed exploration for provable policy gradient learning. Advances in neural information processing systems, 33:13399-13412, 2020.
[46] Andrea Zanette, Ching-An Cheng, and Alckh Agarwal. Cautiously optimistic policy optimiza- tion and exploration with linear function approximation. In Conference on Learning Theory, pages 4473-4525 PMLR, 2021.
[47] Qinghua Liu, Gellért Weisz, András György, Chi Jin, and Csaba Szepesvári. Optimistic natural policy gradient: a simple efficient policy optimization framework for online rl. Advances in Neural Information Processing Systems, 36:3560-3577, 2023.
12

---

[48] Nikita Mishra and Abhradeep Thakurta. (nearly) optimal differentially private stochastic multi-arm bandits. In Proceedings of the Thirty-Firss First Conference on Uncertainty in Artificial Intelligence, pages 592-601, 2015.
[49] Touqir Sajed and Sheffet. An optimal private stochastic-mab algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pages 5579-5588. PMI.R, 2019.
[50] Sayak Ray Chowdhury and Xingyu Zhou, Distributed differential privacy in multi-armed bandits. arXiv preprint arXiv:2206.0577 2022.
[51] Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff. Multi-armed bandits with local differential privacy. arXiv preprint arXiv:2007.33121 2020.
[52] Yulian Wu, Xingyu Zhou, Youming Tao, and Di Wang. On private and robust bandits. Advances in Neural Information Processing Systems, 36:34778-34790, 2023.
[53] Jiahao Hc, Jiheng Zhang, and Rachel Q Zhang. A reduction from linear contextual bandits lower bounds to estimations lower bounds. In International Conference on Machine Learning, pages 8660-8677. PMLR, 2022.
[54] Sayak Ray Chowdhury and Xingyu Zhou. Shuffle private linear contextual bandits. arXiv preprint arXiv:2202.05567, 2022.
[55] Xingyu Zhou and Sayak Ray Chowdhury, On differentially private federated linear contextual bandits. arXiv preprint arXhv:2302.13945, 2023.
[56] Paul Luyo, Evrard Garcelon, Alessandro Lazaric, and Matteo Pirotta. Differentially private ex- ploration in reinforcement learning with linear representation. arXiv preprint a2X.v221 2021.
[57] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Thheory of Computing, pages 439 449, 2020.
[58] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: Optimal rates in 11 geometry. In International Conference on Machine Learning, pages 393-403, PMLR, 2021.
[59] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. In Conference on Learning Theory, pages 474-499, PMLR, 2021.
[60] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth empirical risk minimiza- tion and stochastic convex optimization in subquadratic steps. arXiv preprint arXiv:2103.15 15352, 2021.
[61] Andrew Lowy and Meisam Razaviyayn. Private federated learning without trusted server: Optimal algorithms for convex losses. In The Eleventh International Conference on Learning Representations, 2023.
[62] Changyu Gao, Andrew Lowy, Xingyu Zhou, and Stephen J Wright. Private heterogeneous federated learning without a trusted server revisited: Error-optimal and commumication-cffican algorithms for convex losses. arXiv preprint arXiv:2407.09699 2024.
[63] Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pages 6526 6535. PMLR, 2019.
[64] Yingxue Zhou, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Arindam Banerjee. Private stochastic non-convex optimization: Adaptive algorithms and tighter generalization bounds. arXiv preprint arXiv:2006. 13501, 2020.
13

---

[65] Raman Arora, Raef Bassily, Tomás González, Cristóbal A Guzmán, Michael Menart, and Enayat Ullah. Faster rates of convergence stationary points differentially private optimization. In International Conference on Machine Learning, pages 1060-1092. PMLR, 2023.
[66] Daogao Liu, Arun Ganesh, Sewoong Oh, and Abhradeep Guha Thakurta. Private (stochastic) non-conves optimization revisited: Second-order stationary points and excess risks. Advances in Neural Information Processing Systems, 11156186664,, 2023.
[67] Daogao Liu and Kunal Talwar. Adaptive batch size for privately finding second-order stationary points. arXiv preprint 2400022410.07502, 2024.
[68] Yu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction estimation in unbounded domain. arXiv preprint arXiv:/803.02553 2018.
[69] Or Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theoor, pages 789-827. PMLR, 2019.
[70] T Tony Cai, Yichen Wang, and Linjum Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825-22 2850, 2021.
[71] Gavin Brown, Krishnamurthy Dvijotham, Georgina Evans, Daogao Liu, Adam Smith, and Abhradeep Thakurta. Private gradient descent for linear regression: Tighter error bounds and instance-specific uncertainty estimation. arXiv preprint arXiv:2402.13531, 2024.
[72] Prateek Varshney, Abhradeep Thakurta, and Prateek Jain. (nearly) optimal private linear regression for sub-gaussian data via adaptive clipping. In Conference on Learning Theory, pages 1126-1166 1166. PMLR, 2022.
[73] Xiyang Liu, Prateek Jain, Weihao Kong, Sewoong Oh, and Arun Suggala. Label robust and differentially private linear regression: Computational and statistical efficiency. Advances in Neural Information Processing Systems, 36:23019 2-0333, 2023.
[74] Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, and Stefan Tiegel. Sample-optimal private regression polynomial time. arXiv preprint (.Xiv:2503.24322 2025.
[75] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:21 13447,
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction, we clearly state the main contributions of our work. We present meta algorithm for Private PO and give out three private algorithm: DP-PG, DP-NPG, DP-REBLL and analyze their sample complexity.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
14

---

Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this work can be found in appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification; In this paper, all theoretical results are accompanied by a full set of assumptions and complete proofs. These are clearly stated and numbered within the main text and are croseereferenced appropriately. Detailed proofs for major theorems are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
15

---

Answer: [NA]
Justification: The nature of this paper is purely theoretical research, and its conclusions are derived through mathematical deduction and logical argumentation; therefore, it does not involve experimental validation.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Our conclusions are derived through mathematical deduction and logical argumentation, it does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/ public/ LeaeeessoooSuubmssseeeeeeeeeeeee
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: // httpppplw/pppieeeeeeeeeuubbeeeee
for more details.
16

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2iggma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
17

---

Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethies
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: ptttps://neuripee cc Taabblic/Etiisuutiee
Answer:
[Yes]
Justification: Our research adheres to all guidelines outlined in the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
18

---

Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
19

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This research does not involve any form of crowdsourcing or studies with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The study does not include human subjects, and therefore IRB approval is not required.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the L.M is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not use large language models as an important component of the core methodology. it is used only for editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy (https:/ /ttpss:///euip...eeee wwt.cc//eeeeenee//222222222 for what should or should not be described.
20

---

Contents of Appendix
Additional Related Work
21
Tabular Softmax with Log- barrier Regularization
22
Connection to Private Stochastic Optimization
23
Differentially Private REBEL
23
Proof of Chapter 5
24
E.1 Proof of Theorem
24
E.2 Proof of Theorem 3
27
E.3 Proof of Theorem
E.3.1 FOSP of softmax policy
28
E.3.2
Global optimum convergence
30
F Proof of Chapter 6
32
F.1 Proof of Theorem
32
F.2 Proof of Lemma
33
G Proof of Appendix D
34
G.I Proof of Theorem
35
H Experiments
36
I Limitations
37
A Additional Related Work
Policy optimization. The thcoretical study of policy optimization can be roughly divided into two lines of work. The first line often assumes a certain reachability (coverage) condition and takes perspective from optimization. Under this assumption, various types of policy gradient methods have been investigated, including REINFORCE [1], variance-reduction variants [38], and preconditioned variants such as NPG [11]. TRPO [39], and PPO [3]. The performance metrics are often convergence some typical results in [5, 40, 6, 41, 42]. The second line of work
rate or sample complexity, focuses on the exploration setting, i.e., without the coverage condition. To this end, the algorithm design is often based optimism, e.g., an optimistic version of NPG or PPO via bonus terms or global optimism. Several recent papers have made progress in this direction for tabular RL [43], linear mixture MDP [44], linear MDP and more [45-47]. Our paper can be viewed as the first work that aims to privatize the first line of work above.
Differentially private RL and bandits. Recently, line of work studies RL (bandits) under the constraint of differential privacy, e.g., multi-armed bandits (MABs) [48-52], contextual bandits [27, 36, 53-55], and RL [25, 14, 28, 15, 56]. To the best of our knowledge, only [14] and [15] studied private RL under policy optimization. They consider the exploration setting and characterize the cost of privacy in regret bounds by privatizing optimistic versions of PPO (NPG) under tabular or linear function approximations, respectively. In contrast, we take the optimization perspective (with the coverage condition) and study private PO for general reward/policy function approximations.
21

---

Differentially private stochastic optimization. Extensive research has been done around private stochastic convex and non-convex optimization. In particular, for the problem differentially private stochastic convex optimization (DP-SCO), [24] gave the first optimal algorithm in terms of excess population loss, and [57] developed the first linear-time efficient and optimal algorithm. There are also many follow-up papers under various settings, e.g., [58-62]. Moving to the non-convex case, the performance metrics include first-order or second-order population stationary points (e.g., [63-67]) as well excess population loss (e.g.. [66]). As already mentioned, these results in private stochastic optimization can be useful to us since the estimation error our master theorem equivalent to excess population loss/risk under square loss and realizability,, see Appendix C for more details.
Differentially private linear regression. For the specific problem private linear regression (which is special case of DP-SCO), one can possibly achieve better results by leveraging its structure. We can roughly group the research efforts in this area based on the conditions on the boundedness of the feature vector (and the true parameter). Assuming boundedness, fate-of-the-ar results are established in [68, 69]. On the other hand, without boundedness but under a general uub-Gaussian data, ISSP in [35] is the first efficient and nearly-optimal algorithm, which does not require an identity covariance matrix compared with [70, 71] and does not depend on the condition number of the covariance matrix compared with [72, 73]. Moving from approximate DP to pure DP, the very recent work [74] gives the first polynomial time and sample-optima private regression algorithm. As mentioned before, these results private linear regression useful to since, under log linear policy parameterization, our estimation error reduces to the estimation error in linear regression.
B Tabular Softmax with Log-barrier Regularization
In this section, we move to the second scenario for our DP-PG of global convergence where we consider the tabular case with the classic softmax policy:
Definition 3 (Tabular softmax policy). Consider a finite state space A' and action space V. For any state-action pair (z, y) X x V, the softmax policy is given by
exp(Oz.p)
To(y)>) Eyey e (xp())))))
where 0 IR x1|21)
One key motivation here is to leverage the tabular structure and the specific property of softmax policy to establish a sample complexity of global optimum convergence that is independent of the parameter ry. To this end, in the non-private case [5, 6], will consider a regularized problem, whose FOSP turns out to be an approximate global optimal solution of the unregularized (original) objective, for proper choice of regularization. In particular, we consider the following log-barrier regularization objective:
JA = J(0) AEEuttuiit [Ln,U,,, no (-1x))]
A
= J +
log mo (ylar) Alog [*
(10)
where the KL divergence is KL(p, Exep [log over a set x and
n(a) q(x)
Unifx denotes the uniform distribution
the regularization constant.
We will run our DP-PG over this regularized objective by using the sample-based gradient estimator each step with proper choices of batch size and learning rate. Then, we have the following main result regarding the global optimum convergence in terms of the unregularized J (0). The proof is given in Appendix E.3.
Theorem 5. Consider Algorithm applied to (2( For any m > 0. setting o² ensures (e, D)DP as in Definition 2. Further, there exist proper choices of parameters for and 1), such that the following holds
16 25/81..//8822 RR. G²
m"
J
E E(J(OO) < O(a).
T
As before, this is not complete list of all the works in this area.
22

---

when the sample size satisfies N
O
va a=/2E
a
Remark 7. The first term in the sample complexity bound matches the non-private one in Yuan et al. [6], while the second term is the lower-order privacy cost (for constant and d). note that while the dependence is worse than the previous one, there is no dependence in the bound, which could offer benefits when y is quite small.
C Connection to Private Stochastic Optimization
In this section, we first aim to bound the estimation error (9) by leveraging the existing result in private SCO. In particular, function. The first step is to realize that under realizability, the LHS in (9) is equal to the excess population loss for square loss, which is both Lipschitz (with parameter of order O(B2W) under our boundedness assumption for both feature and parameter space) and smooth (with parameter of O(B²)) Hence, by [24, Theorem 3.2], we obtain that err, em,, & when m > T v /doog1188) a"E
aim to apply Theorem 3.2 in [24] for a Lipschitz and smooth loss
O(Poly BB W)). Thus, by Theorem 4, for suboptimality gap of O(a),
the sample complexity bound is N T m = Ōs + Poly(B,W)) W)). Recall that due to projection in the mini-batch SGD in [24]. one can ensure that |ewell S W for some W that is independent of d. Thus, the non-private term does not depend on d. We mention in passing that one can also potentially directly bound the error in Assumption 4 by leveraging the excess population loss for non-convex loss functions.
D Differentially Private REBEL
In this section, we will consider DP-REBEL which includes a general private regression oracle as the PrivUpdate in Algorithm 1 and then similar our previous DP-NPG, we will give some concrete applications under different specific regression oracles.
Our proposed DP-REBEL is Algorithm 1 with its PrivUpdate being instantiated in Algorithm 5, which also relies on general private least-square regression oracle to return an approximate minimizer of estimation problem under the square loss. The square loss in (11) is the same as before (3).
Algorithm 5 PrivUpdate Instantiation for DP-REBEL
1: Input: D, {(1,, Vi, Ar b))) current policy 1,, base policy μ, learning rate 1), PrivLS oracle
2: Output: 0t+1
3: Call the PrivLS oracle on Dj = { Yi, (x y:))} to find an approximate minimizer wa of
T x)_ - In To (z)) ) (A((as.
argmin F((O) E
In
(11)
To, (y)az)
Te. (e(()))))
8EB
where expectation is over P.Y u(-1)),8'' (-1z)
4: Output policy 0.+1 = 0, + mww
We now turn to establish a generic performance guarantee of DP-REBEL. Similar to DP-NPG, we assume that the approximate minimizer w, returned by PrivLS each iteration satisfies the following guarantee.
Assumption 6 (Private estimation error). For each [2']. the PrivLS oracle satisfies (s, 6) differential privacy and ensures that with probability at least - C.
1
Te (y/z) To, (y]x)
In To. (e/lz)) Te. (v'1z)
E
In
< cmf (,
for some statistical error function err? e, () depending on batch size m, privacy parameters (s, 8), and probability Ç. also, expectation here is over P.y p(+12), y' ne, (-|z).
23

---

Remark 8. This assumption parallels Assumption in DP-NPG and ensures that our private oracle accurately estimates the relative reward differences while preserving our DP PO as Definition 2.
Our main result given by the following theorem.
Theorem Under Assumption 6, according to Lemma 11 and Lemma 12, we have with probability at least S, for any comparator policy x² such that:
1 T ((m) & 2 T
In D
V10C
T
J(xt)
+
crry(m, a,0m,,,,660 6)
T
T
Remark 9, If we simply set the base policy To. which make this assumption simpler, then we can have a tighter bound, it is easy show that the bound will turns to 2A Iu D 120, 1= err,(m, e, 6)
The application here is totally same as the DP-NPG, thus we can directly use our previous Corol- lary 1. Corollary and Corollary 3 which derive the almost same bound of sample complex- ity. For PrivLS with exponential mechanism, consider DP-REBB with PrivLS as in Algo- rithm 4, for given suboptimality gap of O(a + (Cp-ox-approox) the sample complexity bound is
N T m Ō (( + + log (W|A3)) For log-linear policy class with realizabilityy, assume that err, (m, 6, & a, therefore, for log- oog-liier-policy in low-dimension and high-dimension,
d dvloR(1/d) d(log(2/8))² and Ō log(1/5)
/lo((1/C) (og(1/8) a²
have > 0
re-
spectively. Thus, we can derive such sample complexity: T-m Ös (1 for log-liner-policy in low-dimension and N - mm Os (1# a+)c) A²) for high-dimension.
4
A2)
E Proof of Chapter 5
E.1 Proof of Theorem 2
Lemma 3 (ABC). There exists constants A, B, C 0 such that the policy gradient estimator
satisfies:
v |00)1/] < +10
E
(12)
where VJ(
Ex-p,y-< (x=*(x,)) Vo ())l=)), and A 0, 1/m, C
1R2 G²
+ do?.
Proof. For notation simplicity, we let go(T)) = AT A V, log no (3)(2.)) Thus, we have J() 1 n (T.)) + Z. Notice that EEgo(T:)) E I VJ((), cause Z is the gaussian bias, which expectation is O.
24

---

Now, we have
1
E
=E
g0 (Ti) + Z
[ go (T) |
E
go (Ti)
+ [12 +2- E
m
E
go(
+ do +0
171
E
(T((T)) VJ(0) +J(0)++J[ +J
do
m
|VJ(0)] + E
m Σ (T VJ(0)
+ do
[V](I)] + m
E
[190(TT) [
- d
|VJ(0)] + m
E
[[90(TT]]
+ do?
To proceed, need to establish upper bound E [19)(()))) In particular, we have
[z)] +
E [1(g(())] = [ (x), log mo(n
< A. G2,
which follows from Assumption 1.
Hence, we conclude that:
7 (
19
<
(
[V](1)]2 +
4R2 G2 mmax
+ do²
m
412. G2
i... ABC condition in (12) is satisfied with A B = 1/m,
do²
m
Lemma 4 (Smoothness under LS). Under LS assumption in Assumption 1, J(-) is L-smooth, namely J()( & for all 0, with
= 2R & + F).
Proof. For smoothness, it suffices to bound the operator norm of Hessian, i.e., [[)] By definition, we have
(²)(0)
V&E, VgEn~pyyrat [A (z. v) Vo log [ey(a))
/
Vo pa(35 (A (z. To d(x.y)
b VaPo y) (z. y) Vo log d(a,y)+ + / Po(a, y) (AT (z. v) (ggo()))))) d(a, v) Eayyrs [A (z. V log Te log ( T + En (z v (ogg
where in (a), we let (1 3) p(z)mo()(z) and (b) holds by chain rules.
25

---

Thus, we have
[2J[0)]| - Exy [A (x. v) || Vo log [o(
Exy [1A"0(x v)
v log To (u|l))
T2
For Ti and T2, by Assumption 1, we have
T1 S 2R max G², To S 2Rmax
which hence completes the proof.
Lemma 5 (Adapted from Theorem 3.4 in Yuan et al. [6]. Suppose that satisfies smoothness
and the ABC assumption in Lemma 3. Consider the iterates Or of the PG method with step size = 7) E (0, L.). ) let 81 = J J(0]). In particular, if = 0, we have:
26
LCn
E
[VJ(OU)
< 1/T LBn)
(13)
LBn
where Oy is uniformly sampled from (01,-.,, Or)
Proof of Theorem 2. Followed by Lemma 5, when 17 < LB we can simplify the equation into this:
I
281
E [VTJ(()) < n/T
LCn,
(14)
where = 1/m, J (01). (.)))LL 2Rmax constants.
(G2 + F), C=
4R G 4 max do? G and F
m
From Theorem 1, to make sure algorithm satisfy the (c,8)-DP in Definition 2, set x² 161u(1.25/6)-Rf 25 m²g²
Based on Lemma and Equation (14), choose = min LB
22
we have:
VTLC
28 LB
2020, LC
E [[
+
T
VT
1
VC
T
VT
m
TVmd
N
VN
VN
Vd
m
=0
N
VN
ev
N
To proceed, we need to determine the value m.
In order balance the terms in the convergence bound O
VN +
dd eVNmm
set
/d ev/2m
Thus, we have:
2/3
vd
N1/3
(1/E)2/3 (Nd)
Substituting back, the convergence bound simplifies to:
2/3
1 +
d
Ne
26

---

E.2 Proof of Theorem 3
Proof. We know that:
T Σ
[
- -
E
(15)
1=1
Besides, followed by Lemma 1, we obtain that:
G [
G |V](0]] + 20bias
(J J()) <
Obbias
which holds by ( < 2p² + 2q
Taking expectation over both sides, condition on fe, yields that
T
T
Σ E
B
E
[[J[6))1
+ 20
T
72 T
(15)
E
|
20biia
2/3
vd
+
+ O ((rbias)
VN
Ne
where (a) holds by Theorem 2.
By applying Jensen inequality twice, have:
T
-E(r- E
J
3
J
1
E [
T
T
1=1
t=1
So we can derive that:
2/3
J -
1
1
Vd
<0
+
+ ((iiia))
72
VN
Ne
t=1
In that case, we finally get the result:
T J
( NN-1/++
Vd
1/3
Σ E [[()))]
O (Vobiass)
Otbias)
Ne
Suppose J - - E (0.)) < 0(a)) + O(Vabias). we have:
Vd +
N 0 atys a3733
E.3 Proof of Theorem 5
Based on softmax settings in Definition 3, by simple calculus, we have
a log (v(xx)
1, (0),
(16)
09=
22 log (e(
(O)=
003
27

---

where 1g E RDI is vector with all zero entries except being for the entry corresponding to action and (T,,(()) = Diag( (0)) (=)0TT,
In partieular, for softmax, determine the G and F in Assumption 1:
& log To x)|l < G := 1
D
v To .I)| & == 1.
E.3.1 FOSP of softmax policy
Lemma 6. The regularized gradient estimator V xx satisfies ABC assumption in Lemma with parameters:
1
A 0, ==
m
2 1
X²
C= m
AR +
+ do"
[28
Specifically, we have the variance bound: E
[|
(1])) (
& (1
+ do -
2 (1
3) (AR Max + )
Proof. Similar to Appendix E. here we (T( be stochastic gradient estimator of one single sampled trajectory т. Thus we have: J(0) = Σ. (0())) Z.
From equation (10) we have the following gradient estimator
V mm))(0) = V (() + X
Vo log nz,y (0).
Z.
For a state a E X, we have
A
log nr (0) (16)
A
Ea, (0))
|
a0,
D
yEV
NEY
A1
A
(0)
|''1
|X
(0)
X
[20
where 1 RDI is vector of all ones.
Thus have
A
M2 = mm)( + |2| (IDi) - -(==(0))exx)
(17)
where 1 E R R and (T. (0) Tx (0).
| (0); ...; Tap (0)) E | is the stacking of the vectors
28

---

Next, taking expectation on the trajectories, we have
E
V
E
(0)
A
1
(x)
11]
X
D
A
+ (m) -
E
[D)] [T= (0)
V J(B) =)To
|V +E E
|| [(0) + -- -VJ(
V TE
E (T) VJ(0)11
+ do²
(V)
+ d
-VJ(() - गि (13) [Tx xEX 11?
E
(a((T)) किे [JT [Tx
7
(9((T)) + (²) (D) [=x(0))=xx)) 119
E
(c) 1 1
+ ddo
||
2E (1 ][3] + 2 [ि1 [JT - (T)(O)
(d)
1
|
+
+ do?
m
where (a) and (c) hold by definition of v.)(0); (6) holds by definition of V m (d) holds by (p+ + q)² & 2p² + 2q².
In particular, we have
X
1
(T)
)(
A
X [>
+
(21)
22
(1
1
DI
| T| (0)
[)/2
|
[>
where the inequality obtained by using As for E. [190 (T:)))))]), we have
< 1.
E [Ilgu(T)))1]] & 4R G2 4R22 (1-
1
where the equality is obtained by Assumption I with G2 G²= 02=(1- D
Combining above, proved the gradient estimator mm) satisfies ABC assumption with
E || ||
< (1-- m | [VJA()))
(1
X2
+
do²
[x]
m
where
A A= B=1- 1 2 1 |
12
C= m
4R2 R
+ do²
m'
Lemma 7 (Regularized FOSP Convergence). Under the learning rate condition 1) < satisfy:
LB the iterates
1
25 [0)))
+ LC
(18)
T/T
where B = 1/m, 81 = - J(()) I. 2 Rm
- and C as defined in Lemma 6.
29

---

Proof. To proceed with the analysis, we first introduce the following key lemma:
Lemma 8 (Adapted from Lemma E.3 in Yuan et al. [6]). J(.) with the softmax tabular policy is 2Rmax
1DT) -smooth and 2maax / [ST -Liscchitz.
From Lemma 8, we know that J2(+) is smooth and Lipschitz. Then, based on Lemma 5, we have:
20,
LCn
[VJ{(0)) 1fT(2 LBq))
2 L.B
Assuming 7) < LB the above equation simplifies to:
201
E [[VJs(00))
+ LCn,,
1/T
where B 1 1/m, 81 J- (01), L 22 4) C == m (1 (1- (1-1 (4R
12 [27
do G
1 [ and F 1.
Note that the sensitivity of the gradient estimator V (x) is dominated by the data-dependent term. Despite introducing the regularization term X, this term only depends the policy parameters 0 (independent of data), thus it does not affect the sensitivity. So the eeseiiiitvv of the gradient remains same as before.
Lemma 9. let o²
16 (in(125//))) 13/55-12. Re G
the batch size be as: m (1/8)2/3 (Nd) and
m"²e
7 min( LB VTLC
we have:
2/3
Vd
E
|IT.A(00)1 <
+
(19)
VN
NE
Proof. for 1 = min(
we know:
LB VTLC
28, LB
2 2//0,LC
1
VC
σ mdd
E [0)10))11
+
-0
0
T
VT
T
VT
VN
N
Plug in 0² 161n(1.25/86 and m (1))) we have:
E
[
<o
VN
1
+
vd
2/3
No
E.3.2 Global optimum convergence
We first introduce an important proposition to bound our global private optimum convergence of softmax with log barrier regularization.
Proposition (Adapted from Theorem 5.2 in Agarwal et al. [5]). Suppose 0 is such that [|V < x||r Then for every initial distribution p. we have
J" (0) < 2X.
(20)
Proof. Firstly, we define the following set of "bad" iterates:
A 2| /
1+ a 11. T
|VJx(0)) >
30

---

with À =
From Proposition 2, we know that if JV
&
A 2//1/ we have J - J(0) < 21.
Hence, we have:
T J(O.)
1 Er + +T J'
T
T
1=1
LEI+
141+
(a)
|
4Bmax + Σ J J(0
T
T
1EST
(20)
|+
T T |T+
4maax
22
T
[+1
R + 2X
T
|+1
4.mmax +
(21)
T
where (a) holds by J(.) & Rmaxx then J J(O,) & J + J(Oi) & 48max
Now bound |/+ From the definition, we have:
T
> I++
(J.)
> Σ
[VJA(00)1
4
RET
Through a straightforward mathematical transformation, we get
1+1
T
T
X
T
t=1
T
16
1211111
(0)111
a
T
t=1
Thus, we have
T
64Rmax (21)
T Σ
Σ
((.)
|xD1?
[V)x(1) +a.
T
a²
T
Taking expectation over the iterations on both sides, we have
J 1 T B[J(0.) <
64 64Rmax
12p2212
T Σ
1
a²
To guarantee that J 7 ΣT [[J( & a, we need to show:
T
E
T
Obviously, we have:
1 T
E
[VJA
= - M E [8)11
31

---

Hence, based on Lemma 9, it is obvious to show that:
N o a a9/2E)
+ vd
F
Proof of Chapter 6
F.1 Proof of Theorem 4
For notation simplicity, we let IT = no, By the performance difference lemma, we have
T
T
Σ - ((Te) =
Σ
E p. (-1x)) 1 (x,, 8)]
1=1
Define emr, := Expp.yr (:1a) [ATOr (I, 1) we log Te, (y x))] Then, we have
T
T
J(mT) - -[(T)) =
E Perpere (.10) [1 (2.1)) v)]
T
E Bapp.y wa (:10) Kwe, Vo Tel x))] +
Σ
enr
1=1
1 (0.+1 Oc, Vo log Tr xx)
Σ emr
B (11)
1
T (y 1 x3) )
T
nB
Ex- (1x)
log
|well* +
Σ err:
"
( x))
2
1=1
Tr+1 (y (2) )]
Tni
T
Pgpp g (-10)
log
+
W
+
err,
(T x))
2
t=1
Tn3 W
T
log |3] +
+
err
where (a) holds by the update rule of our algorithm; (b) is true since the 3-smooth condition of log no ())r) is equivalent to the following inequality:
3 110 40, 2, |log mo To- | z) log (z x) V log Toly x) (6' -V--81 -0)1<
0'112:
2
(c) follows from the Assumption 5, which has a bounded norm of W. along with telescope sum; (d)
true since गi a uniform distribution each state. Thus, dividing by on both sides and choosing
2 [2] TBW2
yields
T log |
m/W?
T
J(T²)
J(m)) <
+
Σ
err
T [=1
n/T
2
T
1=1
3W2 log [J'
1
err:
2T
T
t=1
32

---

To bound em, we will simply leverage the guarantee of the regression oracle and the concentrability coefficient to transfer from j to x². In particular, we have for any [T]
em
Exmppyr (1la (A (z, y) w. V log no. (y x))]
M3 M
E Bempyre (A (x,, y) wi log no, (y x))
Tu-p-ren- (ATM (1 wi log me, (v =;))²]
V Ca-r (m,,
where (a) holds by Cauchy-Schrae inequality; in (b), we define the single-policy concentrability
coefficient Cy-on == maXx,y p(al)
x' (' m). (c) follows directly from the guarantee of PrivateLS oracle.
Finally, putting everything together, yields
J(x²)
1 E J(m.) <
3W2 log D
VC p-
Σ
(m, 5, 8,
2T
T
F22
Proof of Lemma 2
key lemma in our proof is the following form of Freedman's 's inequality.
Lemma 10 (Lemma A.2 in [75]). Let {Xi)ign be real-valued martingale difference sequence adapted to a filtration [Filism. If |xi S R almost surely, then for any 1) (0, (0,1/R), with
probability at least C
log(1/C)
Σ X; S 1=1
Σ
E 1
where E,-1 F1-1-
Proof of Lemma 2. For any fixed h E H. we define
U. = (h(u.) 2,)² (h" (u;) - 2,)2 we define the filtration F, = ou ..,..., U/ 24) and let [E,-[[] = 1B1-1--]]. then we have that
(im) where
D : R. [U U. a martingale difference sequence adapted {Fi)ism. We further notice that
E, E,-,((D!)) < E, (U,)) = E,- ((h(u)) - 10" (u:)) + h- (u;) 22z)²²
S R / h-" (u,))
where the last step holds by the boundedness of z;, h E H and h² Moreover, by definition, we have
E, E,-LU = E,-1(((((u)) - 11" (m4))) - h² (w4) 22:)]
= E, (1)()) h1 (.
With the above results, we first apply Lemma 10 to (D) Jimm along with a union bound, yielding that with probability at least 1 - C. for all h E H
Σ E. EE-Iihh [(h(us) - h- (u:))
$ Σ U + R² (og(())))).
(22)
Similarly, we can apply Lemma 10 to {- D.d fism along with a union bound, which give us
U
E. [hh(() - h- (x4))) log(((((())))
(23)
33

---

Now, we set h = h in (22), i.e., the output of the exponential mechanism, and by the standard utility guarantee of the exponential mechanism [34], we have
UK + R²² log((1 loog(1H///00) (HH(() + R²a log((HL1/s)
E [(((u)) - - (u:))
where E arg minnen H (hh = arg arg min Σ Eie(m) (h(u)) - -2 Since Σ. U
S - U.
where h = argmin E Ex-1((h(u.)) - ht (u,)) by (23) and the above inequality, we have
Σ B ((h(u)))) - h1" (u.))) Σ E, ((((u)) - h,,,,,,,)), R² + R² log( (1H1/S)
mAkapprox R log((H1/()) R² 1og(1?(/9))
E
where (a) holds the assumption on the approximation error.
G Proof of Appendix D
Lemma 11. Consider any [T]. For notation simplicity, define fe(x, y) In (xl1(
Define A (xx, v) Se(r,y) - r((x,)) Define Ax, (x) = (- and A,(T)
Ey-u((1)) A (xr v). Under Assumption 6, for all t, we have the following:
(x (fe(x, - r(x,)) - An, (x)) & enf(m, e, C)2
Exgos(())) (fe( r(x,y) (x(x))² & emiim, 8, ()2
Ex (Ax, (I) - An(x))) & emri 8, C).
Proof. From Assumption 6, we have:
En w02 (fi(z,)1) - v1) - (x) - (fe(1, - r(x, - A,(x)) + Ax,()) su(x))
En (f((x, r(x, Dr, (x)) En (f (fi( r(x, 12) Ax(2))
2 2E N (f( r(x, v1) AT, (z)) (f( r(x, y2) Ax(x))
+ 2 2E (fe(2, - -( v1) - (x)) (z)
- 2 E (Je( - r(x, v2) - (x)) (A,, (1)) -n(x))
+ E. (Ax, (x) - (x))
Ex,nr (f( (z, 91) r(x, (1).81)= (x)) Ex.yrry (f( v2) r(x, (2) Ax(x))²
(A (I) A=())) 2
< err (m, 8, 8)
In that case, since the total sum is less than erri 6, 6,6, it follows that each term must be less than err? (m, E, 8. C). Hence, the lemma holds.
Lemma 12. Assume maXz. [At y)1 < R and ग. is uniform over y. Then with v (n((""))(APTT)) for the sequence of policies computed by REBEL, we have:
VT, T
12) < 2AAIn((D))T..
34

---

Proof. By the definition of ft. we have
= In (1+1() (1(222)
r(2, v)-
Taking exp both sides, we get:
(r(z,)) + (z, v))) = exp y) + (a, Ax(x)))
Vx, y (vla) Te (1(l)) exp (n
exp(-n),(xz))
Denote
9t (x, == r(x, v) + (z,, Ax(2),
and the advantage
A, v) (e, y) By ( (,y
We can rewrite the above update rule as:
Yz,y y
Te+1 (y/l) x कe (yl exp (1 Ax, 4))
The remain part of the proof is similar to the analysis of NPG in E.1.
G.1 Proof of Theorem 6
Proof. We know that:
T
T Σ
(Ex.g~a (1a) - (e
1
Σ
E yor (12) (A (z. 8)).
T
t=1
Then, we have:
T
B (Ha) (A (x, =
1
Σ
Eny (11x) (Ai(x,)))
T
T
1
+
Ex Ex.grT (I, - Ac(x, B))
T
1=1
(a)
In(())))
$ 2A
T
1
ES Eynar (11)) (Ix w) Ae v))
T
where (a) holds by Lemma 12.
Then we need bound: EgE (-1x) (A 11) ((x,,))²
By the definition of concentrability coefficient Cy-Ex" we know that:
EE (1
(z. v))² < CU 2) (A - Ar(x, v))
We now bound E (e (x, Ar(x,
Bx.yra(1)) (A 1T (2. Ar(x, u))
=R (r(x,y) (o v/) gi (x, + (y v')2
< 2E (En.grp(1e) (r(z, v) (e + By ~m (r(x,v') - g((x.
35

---

Recall the ge(2, y) r(z, v) + A(x - A2(x), and from Lemma 11, we can see that
E Be (r ((. 1a) - (x)))) & sm, For E,
(0 /
(r(a,y') (x), we have:
(y (r(x,))) gr(2, Ey (112) (A y²) (z)2)
= E, (11z) A (z, 3²) (z, + (z) (r)))
< 2E By ~ (+w) ( (xx A (x)) 21E (A (x) - 2x)))
< 4err (m, s, 5, 5)
where the last inequality uses Lemma again. Combining things together, we can conclude that:
EgE (41t) - A,(x, u)) & Cu-on (10er) ,,))..
Hence, we can derive our main theorem:
T
In |n
E Bayan- (A** & 2AV
+
Σ
v 10C om
T
T
T
In |n
110
=2A
emr,(m,,,6) 6,
T
H Experiments
We conduct experiments on the CartPole-vi environment from OpenAl Gym, standard benchmark for evaluating policy gradient methods. The task requires balancing a pole on moving cart, with maximum episode reward of 500.
Environment.
Policy Parameterization. Policies represented by two-layer fully-connected neural networks with 64 hidden units, ReLU activation, and softmax output layer, i.c., the architecture is Linear(4, 64) + ReLU Linear(64, 2) - Softmax.
Privacy Settings. We evaluate (5, 10- and (c, 5) (3, 10-5), representing moderate and strong privacy guarantees respectively.
algorithmss under two privacy budgets: (c,8)
Training Details. All algorithms are trained for 100 epochs with batch size 10 (i.e., 10 episodes per gradient update) and discount factor 0.99. We use advantage normalization with baseline subtraction for variance reduction. Each algorithm trained with random seeds, and we report the average performance with standard deviation.
Evaluation. We evaluate performance using three metrics: (i) Mean Final Reward: average reward in the final epoch across all seeds, (ii) Std Final Reward: standard deviation of final rewards across seeds, and (iii) Best Epoch Mean: highest average reward achieved during training.
Results. Table summarizes the performance under different privacy settings.
We can see that (i) NPG consistently outperforms PG in both private and non-private settings, demonstrating benefit of curvature-aware updates, (ii) DP-NPG with E = achieves near-optimal performance (~ 500), aligning with our theoretical predictions and empirical findings in Rio et al. [13] who use PPO instead of NPG, and (iii) as privacy budget decreases (smaller E), performance degrades as expected from theory.
36

---

Algorithm
Mean Final Reward
Std Final Reward
Best Epoch Mean
PG
N/A
334.37
25.25
361.70
DP-PG
5
190.34
52.91
199.17
DP-PG
143.87
22.88
187.17
NPG
N/A
492.90
10.04
500.00
DP-NPG
478.73
28.05
494.70
DP-NPG
400.87
65.37
410.43
Table Performance summary for CartPole-vl under different privacy budgets (E and s
6 10 10"
I Limitations
In this study, we propose private variants of three classical algorithms for policy optimization and provide comprehensive analysis of their sampling complexity under both private and non-pni non-private settings. Our analysis successfully recovers the classical complexity bounds the non-private regime, validating the theoretical soundness of our approach. However, current results focus only on the one-pass sampling setting; the sampling complexity in the multi-pass scenario may admit further improvements.
Moreover, while this work primarily focuses on the theoretical foundations of the proposed algorithms, we have also conducted simple empirical validations to support our theoretical findings. It should be noted, however, that we have not yet performed large-scale evaluations on real-world datasets. Nevertheless, since our methods serve as core components in policy optimization, they have broad applicability across various reinforcement learning domains partiiillrar in privacy-sensitive settings such reinforcement learning with human feedback (RLHF) and medical data analysis. Applying our approach to these areas could further enhance the secure handling of sensitive information.
37


Reviews:
[{"review_id": "5SxKCTRcnN", "reviewer": "Reviewer_XUJ9", "summary": "This paper is purely theoretical (it includes no experiments or algorithms) and derives sample complexity bounds for Differentially Private Policy Optimization (DP-PO). After redefining adjacent datasets in terms of users, the authors present a general scheme for DP-PO. First, the authors introduce a vanilla DP-PG algorithm and provide corresponding privacy guarantees and convergence bounds. Finally, they derive the DP-NPG and DP-REBEL algorithms, also with privacy guarantees and regret bounds.", "questions": "see weaknesses", "limitations": "yes, in the appenx", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- The paper is well written and easy to follow\n- The problem addressed in this paper is important for the DP-RL community. Finite-sample guarantees are particularly valuable for understanding the impact of various parameters and could help guide parameter tuning.\n- The theoretical analysis is exhaustive thoroughly covers privacy guarantees, convergence, and regret bounds across different algorithmic settings\n\nWeaknesses\n\n- My main concern about this paper is the lack of experimental results. A key challenge in DP algorithms is selecting the appropriate \\epsilon which requires balancing performance and privacy.For the three proposed algorithms, it is difficult to gain intuition about reasonable values for this parameter. Have the authors conducted any experiments, even on small benchmarks like RiverSwim, to develop intuition? What happens when using large values for the parameter \\w, for example in the case of a deep policy?\n- DP-PG seems to rely on a parameter G that appears to be impossible to compute directly. Can the authors propose a practical method for setting this parameter? What are the theoretical implications of adopting a clipping strategy similar to that used in DP-SGD? Once again, an empirical evaluation of this parameter’s impact would have been highly beneficial.\n- Although the theoretical work is novel, I don't find enough originality in the paper: defining DP in an RL context has already been analyzed and the proposed algorithms do not differ a lot from the work of [Rio et al, 2025].\n- [Minor remark] Placing the section on DP-REBEL in the appendix disrupts the flow of the paper, alhtough the space constraint and trade-off.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and detailed review. Below, we address your key concerns point by point. We hope our answers will resolve your concern.\n\n**1. Experiments.**\nWhile the primary contribution of our paper is theoretical—providing the first sample complexity guarantees for DP policy optimization—we appreciate the reviewer's suggestion for empirical validation. We conducted experiments using the standard CartPole environment from OpenAI Gym with two-layer neural networks as policies. \nFor DP-NPG, we implemented a simple differentially private least-squares update by adding calibrated Gaussian noise to the Fisher information matrix and bias vector.\n\n\nSince we are unable to upload images, we summarize the results using the table below:\n\n### Performance Summary for CartPole-v1( $\\epsilon = 5$  and $\\epsilon = 3$ with $\\delta = 1e-5$)\n\n| Algorithm | $\\epsilon$ | Mean Final Reward | Std Final Reward | Best Epoch Mean |\n|-----------|---|-------------------|------------------|-----------------|\n| PG        | NA | 334.37            | 25.25            | 361.70          |\n| DP-PG     | 5 | 190.34            | 52.91            | 199.17          |\n| DP-PG     | 3 | 143.87            | 22.88            | 187.17          |\n| NPG       | NA | 492.90            | 10.04            | 500.00          |\n| DP-NPG    | 5 | 478.73            | 28.05            | 494.70          |\n| DP-NPG    | 3 | 400.87            | 65.37            | 410.43          |\n\n\n**Takeaway messages:**\n- (a) NPG consistently outperforms PG, both in private and non-private settings, thanks to its curvature-aware updates.\n\n- (b) DP-NPG achieves near-optimal reward (~500) even with privacy ($\\epsilon$ = 5), consistent with our theory (i.e., privacy cost could be a lower-order term) as well as the empirical results in [Rio et al., 2025], which uses PPO instead of NPG. Note that, given the close relationship between NPG (TRPO) and PPO, this is expected.\n\n- (c) As $\\epsilon$ decreases (i.e., stronger privacy), utility degrades, as expected from our theory.\n\n---\n\n**2. Clipping norm.** This parameter is regarded as a hyperparameter in DP ML, even in DP-SGD for supervised leanring settings.\nThere are two common approaches for choosing it (see [R1]):\n- Use a small amount of public data to estimate the norm\n- Jointly tune it with the learning rate\n\nWe combine the two approaches when determining our clipping norm. We finally mention in passing that another possible approach could be leveraging the insight derived in [Rio et al., 2025] when choosing this parameter. \n\n[R1] Ponomareva, Natalia, et al. \"How to dp-fy ml: A practical guide to machine learning with differential privacy.\" Journal of Artificial Intelligence Research 77 (2023): 1113-1201.\n\n---\n\n**3. Comparison with [Rio et al, 2025].**\nWhile [Rio et al., 2025] makes an important empirical contribution, our work is the **first to establish formal sample complexity bounds** for DP versions of PG, NPG, and REBEL. Our unified framework complements prior empirical work and provides a theoretical foundation for principled privacy–utility tradeoffs in policy optimization.\n\n\n\n---\n\n**4. Presentation.** We appreciate the suggestion and agree that DP-REBEL is a core contribution. We will move more discussion into the main text in the final version."}, {"review_id": "PpVi6j0gfp", "reviewer": "Reviewer_VYZ7", "summary": "The paper studies DP version of 3 big algorithms in policy optimization in RL by stating suitable new DP definitions, proposing DP algorithms, and proving that adding the privacy requirement do not increase the sample complexity.", "questions": "- while the result looks good, should I think of the extra terms from privacy as \"expected\"? I.e. it is intuitive to say that with \"epsilon noise\", the penalty is around the same level as alpha? Maybe some toy examples or theoretical analysis of lower bound / tightness could help that this privacy term is expected or tight or not.", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "(+) seems like a new, useful area of study. The main contribution must be the ideation of the settings (the alg or adding Gaussian is more standard and expected)\n(+) complete statement and proofs\n(-) as it is on theory, it's with no experiments and estimate of constants are out of scope here. It may lead to more practical studies later.", "was_revised": true, "final_justification": "I see the authors adding some experimental results. I am not confident to judge them, but I do not think this is their main contribution anyway. My bigger concern though is the confidence among pool of reviewers we have.", "rebuttal": "Thank you for your positive evaluation and encouraging remarks. We are glad to hear that you found the problem setting and theoretical contributions promising for future work.\n\n**1. Privacy cost.** A key insight of our paper is that the additional sample complexity cost induced by privacy manifests as **lower-order terms** in many problem settings. That is, the $\\alpha$ term related to privacy is smaller than the non-private $\\alpha$ term, illustrating that privacy cost does not dominate the sample complexity.\n\nTo complement the theory, we have now conducted experiments (see our response to Reviewer XUJ9) and observed that DP-NPG can nearly match non-private NPG performance even under privacy ( $\\epsilon = 5$ ). These empirical results further support our theory.\n\nOn the other hand, we also tend to believe that there exists a gap between our privacy term and its corresponding lower bound. We leave it as future work, as even for the supervised learning setting, there exist gaps between upper and lower bounds in the case of private non-convex optimization."}, {"review_id": "8b8c8xe5Ty", "reviewer": "Reviewer_FwLs", "summary": "While policy optimization is an important technique in RL and LLM, its privacy concerns could be an issue. This paper focuses on the sample complexity of private PO algorithms. They first analyze the challenges of defining DP-PO compared to standard SFT, and then formulate the definition of DP for PO. The sample complexity of three commonly used algorithms (PG, NPG, and REBEL) is studied under DP setting.", "questions": "- Suppose there is a dataset of size $N$. Does the user represent a static prompt? If so, then why is the user dynamic?\n\n- Do current reward models satisfy the assumption of bounded reward $[R_{min}, R_{max}]$?\n\n- In Theorem 4, $|Y|$ is typically the same as the vocabulary size in LLMs, which is very large. Will the bound be loose in that case?\n\n  Minor:\n\n  - Eq.1: it should be $y \\sim \\pi_{\\theta}(\\cdot|x)$", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n- The motivation to analyze DP-PO with sample complexity is well discussed. The paper also gives a detailed discussion on related work, leading to a clear demonstration of its contribution and novelty.\n- While DP can protect privacy, it often requires extra cost. As PO needs to sample multiple trajectories, the sample complexity is especially critical. This paper targets this interesting and important question, which would benefit the community of both PO and DP.\n- This paper proposes a unified framework to analyze three popular and important algorithms, including PG, NPG, and REBEL. The sample complexity is also studied in various conditions, such as FOSP and global optimum. \n\nWeakness:\n\n- The formulation of PO in Sec. 2 maximizes the reward. However, in practice, a constraint on the KL divergence of $\\pi_{\\theta}$ and $\\pi_{SFT}$ is usually used. Ignoring this term would limit the applicability of this paper.\n- The definition of “DP in PO” is not clear enough to me. In Def.2 the author uses the term “users” to define DP-PO, while the description of users is overwhelming. I suggest giving more illustrations on the description of the users and adding more mathematical details in Def . 2.\n- I wonder if the theories in this paper can be easily evaluated by (simulated) experiments. Empirical experiments will enhance the validity and application of the theories.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns and I will maintain my support to the paper.", "rebuttal": "Thanks for your positive evaluation of our paper. We will recap your valuable comments and present our detailed response. \n\n**1. Metric.** We clarify that our work adopts the **standard reward-maximization formulation** used in most prior work on PO, such as PG, NPG, REBEL, TRPO, and PPO. For LLM, we agree that we often add an additional KL term. In this case, our algorithm can still be implemented by merging the KL term into the reward.\n\n**2. DP in PO.** We can use Examples 1 and 2 in the paper to understand the concept of \"users\". Each \"user\" can represent each prompt in Example 1, while \"user\" can also represent each patient in Example 2. We clarify that the word \"dynamic\" refers to the dataset. That is,  as the reviewer mentioned, each user can be each prompt (which is the $x$ and it is static), but the response $y$ and reward $r(x,y)$ are dynamic, since they are determined in the on-policy manner. This is in sharp contrast to supervised learning where the whole dataset $(x_i,y_i)$ is static and fixed in advance.\n\n\n**3. Experiments.** Although our paper focuses on theory, we have now added empirical evaluations using the CartPole-v1 benchmark in OpenAI Gym. As detailed in our response to Reviewer XUJ9, the results validate the theoretical trends.\n\n\n**4. Parameters.** Yes, many reward models in practice satisfy boundedness, like in LLM alignment and reasoning. We also note that our dependence on $ |Y| $ is only on the **log order**, which is the same as the non-private case, like REBEL. Moreover, as shown in the REBEL paper, the practical performance is quite good even with a theory bound of $\\log |Y|$."}, {"review_id": "m4dXRPCV54", "reviewer": "Reviewer_LxTk", "summary": "This paper initiates a theoretical study of differentially private policy optimization (PO), focusing on sample complexity under privacy constraints. The authors first define a tailored notion of differential privacy (DP) for PO, addressing challenges arising from on-policy learning dynamics and the definition of a privacy unit. The authors propose a meta-algorithm for private PO, instantiating it for policy gradient (DP-PG), natural policy gradient (DP-NPG), and REBEL (DP-REBEL). Theoretical results establish polynomial sample complexity bounds, showing that privacy costs often appear as lower-order terms, and the analysis is validated through corollaries for log-linear policies in low and high dimensions.", "questions": "1. Could the authors detail the technical difficulties in deriving sample complexity bounds?  \n2. Will empirical results on RL benchmarks be provided to validate the practical performance of the proposed methods? \n3. Could the authors give any insight on how their framework handles multi-round user interactions, which may violate the single-sample privacy unit assumption?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n1. This paper is well-organized and easy to follow. \n2. The study connects theory to real-world applications (e.g., healthcare, LLM alignment), where privacy is critical. The examples of LLM finetuning and healthcare-rl help me better understand the broad application of differential privacy policy optimization.\n3. The authors derive rigorous sample complexity bounds under various settings. Key contributions include: 1) Propose a general framework for privacy policy optimization. 2) Proving that privacy costs manifest as lower-order terms in sample complexity, e.g., $\\(O(1/\\alpha^4)\\)$ vs. $\\(O(\\sqrt{d}/(\\alpha^3\\varepsilon))\\)$. 3) Showing how structural properties (e.g., Fisher non-degeneracy, compatibility) refine regret guarantees. \n\n## Weaknesses\n1. The proposed framework and theoretical analysis are not highly innovative, which mainly combines existing policy optimization algorithms (e.g., PG, NPG) with differential privacy techniques.\n2. The paper lacks experimental results on real-world benchmarks.", "was_revised": true, "final_justification": "My concerns regarding the experiment and technical contribution have been addressed, and I will keep my score at 4.", "rebuttal": "Thanks for your positive evaluation of our paper. We will recap your valuable comments and present our detailed response. \n\n**1. Technical difficulty.** One technical contribution worth highlighting is Lemma 2, which gives the first estimation error bound for private LS with the exponential mechanism under approximation error. This enables us to be the first to analyze the sample complexity of DP-NGP and DP-REBEL under **pure DP, even for general function approximations**. Moreover, given the wide use of private LS oracle in other RL settings, we believe that Lemma 2 is of broad interest to the community. \n\n**2. Experiments.** Yes, we have added some experiments on standard RL benchmarks to validate the practical performance of proposed algorithms, see our response to Reviewer XUJ9 above.\n\n**3. Multi-round user interactions.** This is an insightful and sharp point. Our current framework assumes **one-round interaction per user**, which is standard in almost all prior work on DP-RL. To support **multi-round user interactions**, we distinguish two cases in the context of PO:\n\n- **(a) Within-batch reuse**: If a user appears multiple times within the same batch, then the sensitivity must scale with the number of appearances. We can incorporate this into the privacy analysis by adjusting the added noise.\n\n- **(b) Across-batch reuse**: If a user interacts in multiple rounds across different batches, we can apply **privacy composition theorems** (e.g., advanced composition or Rényi DP accounting) to compute cumulative privacy loss."}]

Author rebuttal:

Meta-review: This work analyzes the sample complexity of several PO algorithms under DP constraints. There is one unified framework for doing this. The manuscript shows that the privacy costs can often manifest as lower-order terms in the sample complexity.

The reviews are mostly positive, with one borderline rejection review. While I inspect the reviews, I found the concerns have been mainly addressed in the rebuttal. I suggest the authors to incorporate the additional results they have provided in the rebuttal to their next revision. I recommend acceptance.
Decision: Accept (poster)