On the Sample Complexity of Differentially Private Policy Optimization

Thanks for your positive evaluation of our paper. We will recap your valuable comments and present our detailed response.

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.

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.

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:

• (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.

• (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.

Thanks for your positive evaluation of our paper. We will recap your valuable comments and present our detailed response.

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.

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.

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.

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|$.

Thank you again for your valuable comments!

As the discussion period is drawing to a close, we wanted to check in and see if our rebuttal has helped clarify your concerns. We’d be happy to further engage if there are any remaining questions.

If our response is satisfying, we would also appreciate knowing whether there’s an opportunity to update your score before the final justification.

Best,

Authors

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.

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.

To 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.

On 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.

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.

1. Experiments. While 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. For DP-NPG, we implemented a simple differentially private least-squares update by adding calibrated Gaussian noise to the Fisher information matrix and bias vector.

Since we are unable to upload images, we summarize the results using the table below:

Performance Summary for CartPole-v1( $\epsilon = 5$ and $\epsilon = 3$ with $\delta = 1e-5$)

Takeaway messages:

• (a) NPG consistently outperforms PG, both in private and non-private settings, thanks to its curvature-aware updates.

• (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.

• (c) As $\epsilon$ decreases (i.e., stronger privacy), utility degrades, as expected from our theory.

---

2. Clipping norm. This parameter is regarded as a hyperparameter in DP ML, even in DP-SGD for supervised leanring settings. There are two common approaches for choosing it (see [R1]):

• Use a small amount of public data to estimate the norm
• Jointly tune it with the learning rate

We 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.

[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.

---

3. Comparison with [Rio et al, 2025]. While [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.

---

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.