Research map / Federated learning and privacy / Differential privacy
On the Sample Complexity of Differentially Private Policy Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Initiates a theoretical study of differentially private policy optimization, defining user-level DP for PO and deriving sample complexity bounds for private PG, NPG and REBEL under a unified meta-algorithm framework.
Problem
Sample complexity cost of enforcing differential privacy in policy optimization, where data is generated on-policy and the privacy unit is ambiguous.
Approach
Defines a user-level (one 'user' per sample) DP notion for PO that handles on-policy data, then casts private PG, NPG and REBEL as a batched one-pass meta algorithm with a private update oracle, reducing NPG/REBEL to private regression to import existing private estimation bounds.
Key results
- DP-PG reaches first-order stationary point with E||grad||^2 = O_delta(1/sqrt(N) + (sqrt(d)/(N eps))^{2/3}), so privacy cost is a lower-order additive term.
- DP-NPG via exponential mechanism is pure (eps,0)-DP with sample complexity N = O~((1/alpha^4 + 1/(alpha^4 eps)) log|W| beta W^2) for general function classes.
- Under log-linear policies in low dimension, DP-NPG sample complexity is O~_delta((d/alpha^4 + d/(alpha^3 eps) + d/(alpha^2 eps^2)) B^2 W^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add differential privacy to policy-gradient updates | Policy gradient · Bandit PO, FOSP | expected squared gradient norm: \frac{1}{\sqrt{N}} + \left( \frac{\sqrt{d}}{N \epsilon} \right)^{2/3} | Mixed |
| Add differential privacy to policy-gradient updates | Policy gradient · Bandit PO, FOSP | sample complexity: O(1/\alpha^{4}); O_{\delta}\left(\frac{\sqrt{d}}{\alpha^3 \epsilon}\right) | Mixed |
| Use tabular softmax with log-barrier regularization | DP-PG · Tabular softmax PO, average regret | sample complexity: \frac{1}{\alpha^6} + \frac{\sqrt{d}}{\alpha^{9/2}\epsilon} | Mixed |
| Add privacy using the exponential mechanism | NPG · Bandit PO, general function class | sample complexity: \frac{1}{\alpha^4} + \frac{1}{\alpha^4\epsilon} | Mixed |
| Use private regression with ISSP | NPG · Bandit PO, log-linear policy, low dimension | sample complexity: \frac{d}{\alpha^4} + \frac{d}{\alpha^3\epsilon} + \frac{d}{\alpha^2 \epsilon^2} | Mixed |
| Use private regression in the high-dimensional setting | NPG · Bandit PO, log-linear policy, high dimension | sample complexity: \frac{1}{\alpha^6} + \frac{1}{\alpha^5\epsilon} | Mixed |
Surprising findings
- Privacy-induced bounds depend on the norm bound W, which can scale as sqrt(d) because the Gaussian noise added in the private oracle inflates the weight norm.
- Under a high-dimensional log-linear class the privacy-related sample complexity term has a worse dependence on alpha than the non-private term.
Limitations
- Analysis restricted to bandit formulation rather than full MDP.
- General-class DP-NPG via exponential mechanism is not computationally efficient.
- Bounds depend on boundedness of the weight vector W, which can be large (order sqrt(d)) under Gaussian noise.
Experimental setup
Metrics: sample complexity suboptimality gap
Builds on: REINFORCE natural policy gradient REBEL Gaussian mechanism exponential mechanism
Closest papers by meaning
- Differentially Private Policy Evaluation (ICML 2016 · similarity 0.93)
- Private Reinforcement Learning with PAC and Regret Guarantees (ICML 2020 · similarity 0.91)
- Local Differential Privacy for Regret Minimization in Reinforcement Learning (NeurIPS 2021 · similarity 0.90)
- Differentially Private Reinforcement Learning with Self-Play (NeurIPS 2024 · similarity 0.90)
- Towards Differentially Private Reinforcement Learning with General Function Approximation (NeurIPS 2026 · similarity 0.89)
- Shifted Interpolation for Differential Privacy (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.