# On the Sample Complexity of Differentially Private Policy Optimization

arXiv: https://arxiv.org/abs/2510.21060 · HTML: https://mlsanity.com/paper/2510.21060/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 55 of its 74 references that are in the map.
- First posted on arXiv 24 Oct 2025.

## Builds on (most cited first, 30 of 55)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [REBEL: Reinforcement Learning via Regressing Relative Rewards](https://mlsanity.com/paper/2404.16767/) (2024)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [Private Reinforcement Learning with PAC and Regret Guarantees](https://mlsanity.com/paper/2009.09052/) (2020)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy](https://mlsanity.com/paper/1906.10306/) (2019)
- [An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule](https://mlsanity.com/paper/1905.09383/) (2019)
- [Multi-Armed Bandits with Local Differential Privacy](https://mlsanity.com/paper/2007.03121/) (2020)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)

## Built on by (most cited first, 3 of 3)

- [Auditing Data Membership in Reinforcement Learning With Verifiable Rewards](https://mlsanity.com/paper/2511.14045/) (2025)
- [Improved Bounds for Private and Robust Alignment](https://mlsanity.com/paper/2512.23816/) (2025)
- [Private Direct Preference Optimization for LLM Alignment](https://mlsanity.com/paper/2608.05040/) (2026)

## Abstract (arXiv)

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.