Research map / Federated learning and privacy / Differential privacy

Towards Differentially Private Reinforcement Learning with General Function Approximation

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Private online and user-level learning · 0 citations (OpenAlex)

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.

Gives the first regret guarantees for joint-differentially-private online RL with general function approximation, using batched updates and the exponential mechanism over an unconstrained Bellman-loss score, achieving K^{3/5} privacy cost plus coverability-based sqrt(K) term.

Problem

Private (joint DP) online reinforcement learning with general function approximation, where prior private RL results were restricted to tabular or linear settings and standard confidence-set exploration is hard to privatize.

Approach

Replace confidence-set constrained optimization with an unconstrained score (optimism term minus Bellman loss), update policy only at fixed-size batch starts, and sample the update function via the exponential mechanism; the regret analysis relates on-policy test error to training error via coverability under batching.

Key results

• Theory: regret of order sqrt(C_cov K) plus privacy term (C_cov K log K)^{3/5} (log(|F|K/alpha)/eps)^{2/5}, matching the K^{3/5} linear model-free private rate.
• Without privacy, batch size B=O(sqrt K) still gives sqrt(K) regret under coverability, a by-product for batched RL.
• Small proof-of-concept (H=4, |F|=243): plateau episode for private eps=8 is 37 vs 13 for non-private no-batch on the easy instance; eps=5 takes 127 episodes.

Surprising findings

• Claimed sqrt(K) private regret bounds for linear MDPs in follow-up works (via rare policy switching) are argued to be ungrounded because privatized design matrices are non-monotone.
• Bellman-Eluder-dimension analyses can yield T^{2/3} regret where sqrt(T) is achievable under coverability.

Limitations

• Theory requires realizability or Bellman completeness and finite function classes (infinite handled via covering with extra beta K error).
• Privacy term scales as K^{3/5}, not sqrt(K), in the model-free setting.
• Experiments are a minimal proof-of-concept only.

Experimental setup

Datasets: synthetic deterministic outcome-reward MDP (proof-of-concept)

Benchmarks: synthetic deterministic outcome-reward MDP (easy and hard instances)

Metrics: cumulative regret plateau episode (95% of final regret)

Baselines: linear private RL model-free (K^{3/5}) Eluder-condition batched RL rare-policy-switch private linear RL claims

Builds on: MEX GOLF coverability (Xie et al.) billboard lemma advanced composition

Closest papers by meaning

• Improved Regret for Differentially Private Exploration in Linear MDP (ICML 2022 · similarity 0.91)
• Local Differential Privacy for Regret Minimization in Reinforcement Learning (NeurIPS 2021 · similarity 0.90)
• Private Reinforcement Learning with PAC and Regret Guarantees (ICML 2020 · similarity 0.90)
• On the Sample Complexity of Differentially Private Policy Optimization (NeurIPS 2025 · similarity 0.89)
• Differentially Private Reinforcement Learning with Self-Play (NeurIPS 2024 · similarity 0.88)
• Online Optimization for Offline Safe Reinforcement Learning (NeurIPS 2025 · similarity 0.86)