On the Sample Complexity of Differentially Private Policy Optimization

• URL: http://arxiv.org/abs/2510.21060v1
• Date: Fri, 24 Oct 2025 00:21:38 GMT
• Title: On the Sample Complexity of Differentially Private Policy Optimization
• Authors: Yi He, Xingyu Zhou,
• Abstract summary: Policy optimization (PO) is a cornerstone of modern reinforcement learning (RL), with diverse applications spanning robotics, healthcare, and large language model training.<n>In this paper, we initiate a theoretical study of differentially private policy optimization, focusing explicitly on its sample complexity.<n>We first formalize an appropriate definition of differential privacy (DP) tailored to PO, addressing the inherent challenges arising from on-policy learning dynamics.<n>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.
• Score: 11.50986905833618
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning [66.4260157478436]
  We study reinforcement learning in the policy learning setting.<n>The goal is to find a policy whose performance is competitive with the best policy in a given class of interest.
  arXiv  Detail & Related papers  (2025-07-06T14:40:05Z)
• A Novel Approach to Differential Privacy with Alpha Divergence [3.289248622896901]
  We present alpha iteration differential privacy (ADP), an innovative privacy framework grounded in alpha divergence.<n>This study delineates the theoretical underpinnings of ADP and contrasts its performance with competing privacy frameworks.<n>The suggested method markedly improves privacy-preserving methods, providing a flexible solution for contemporary data analysis issues.
  arXiv  Detail & Related papers  (2025-06-20T14:10:18Z)
• Reinforcement Learning for Individual Optimal Policy from Heterogeneous Data [3.6714630660726586]
  offline reinforcement learning (RL) aims to find optimal policies in dynamic environments in order to maximize the expected total rewards by leveraging pre-collected data.<n>Traditional methods focus on learning an optimal policy for all individuals with pre-collected data from a single episode or homogeneous batch episodes.<n>We propose an individualized offline policy optimization framework for heterogeneous time-stationary Markov decision processes.
  arXiv  Detail & Related papers  (2025-05-14T15:44:10Z)
• Differentially Private Policy Gradient [48.748194765816955]
  We show that it is possible to find the right trade-off between privacy noise and trust-region size to obtain a performant differentially private policy gradient algorithm.<n>Our results and the complexity of the tasks addressed represent a significant improvement over existing DP algorithms in online RL.
  arXiv  Detail & Related papers  (2025-01-31T12:11:13Z)
• Statistical Analysis of Policy Space Compression Problem [54.1754937830779]
  Policy search methods are crucial in reinforcement learning, offering a framework to address continuous state-action and partially observable problems. Reducing the policy space through policy compression emerges as a powerful, reward-free approach to accelerate the learning process. This technique condenses the policy space into a smaller, representative set while maintaining most of the original effectiveness.
  arXiv  Detail & Related papers  (2024-11-15T02:46:55Z)
• Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality [94.89246810243053]
  This paper studies offline policy learning, which aims at utilizing observations collected a priori to learn an optimal individualized decision rule.<n>Existing policy learning methods rely on a uniform overlap assumption, i.e., the propensities of exploring all actions for all individual characteristics must be lower bounded.<n>We propose Pessimistic Policy Learning (PPL), a new algorithm that optimize lower confidence bounds (LCBs) instead of point estimates.
  arXiv  Detail & Related papers  (2022-12-19T22:43:08Z)
• Privacy-Constrained Policies via Mutual Information Regularized Policy Gradients [54.98496284653234]
  We consider the task of training a policy that maximizes reward while minimizing disclosure of certain sensitive state variables through the actions. We solve this problem by introducing a regularizer based on the mutual information between the sensitive state and the actions. We develop a model-based estimator for optimization of privacy-constrained policies.
  arXiv  Detail & Related papers  (2020-12-30T03:22:35Z)
• Private Reinforcement Learning with PAC and Regret Guarantees [69.4202374491817]
  We design privacy preserving exploration policies for episodic reinforcement learning (RL) We first provide a meaningful privacy formulation using the notion of joint differential privacy (JDP) We then develop a private optimism-based learning algorithm that simultaneously achieves strong PAC and regret bounds, and enjoys a JDP guarantee.
  arXiv  Detail & Related papers  (2020-09-18T20:18:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.