Consider a service that learns a routing or driving policy from many people's trips. Each person's trip is sensitive, because a handful of locations is enough to identify someone. At the same time, the service must never, even while it is still learning, recommend actions that are likely to end in a dangerous state. Private reinforcement learning already exists: an agent learns from many users' episodes while guaranteeing that what it tells one user reveals almost nothing about any other user's trajectory. So does safe exploration: an agent keeps a cost budget satisfied throughout training, not only at the end. But the private methods achieve privacy by adding zero-mean random noise to the statistics they learn from. Safe exploration depends on those same statistics never underestimating danger. Half the time, symmetric noise makes a risky transition look rarer than it is. Plugging a private learner into a safe explorer therefore breaks the safety guarantee in the one place it matters.
We propose to make the privacy noise one-sided with respect to danger. The agent keeps privatized visitation counts, as existing private learners do. It then builds confidence sets that are widened by a known bound on the privacy noise and plans against the worst case inside those sets whenever it evaluates cost. A new policy is deployed only if this pessimistic cost estimate stays under the safety budget; otherwise the agent falls back toward a known-safe policy. The result is a learner that is jointly differentially private toward users and keeps constraint violations during learning below a target probability. The price of privacy shows up as a measurable extra delay spent near the safe policy, not as safety violations.
Core Claim
In a constrained Markov decision process with unknown dynamics learned from users' trajectories, one can obtain joint differential privacy (JDP) and high-probability safety during exploration at the same time. JDP means the actions given to user $k$ may depend on $k$'s own trajectory but are $(\epsilon, \delta)$-private with respect to every other user's. A constrained Markov decision process (CMDP) is a decision process where the agent maximizes reward subject to a separate cumulative cost budget.
The mechanism is to replace the optimism-preserving post-processing of private counts with a pessimism-preserving one for the cost side. Let $\tilde N(s,a)$ be the privatized visit count of state-action pair $(s,a)$. Let $\hat P$ be the noisy empirical transition model, $\hat C_{\hat P}(\pi)$ the expected episode cost of policy $\pi$ under $\hat P$, and $\tau$ the safety budget. The deployment rule is
$$\max_{P \in \mathcal{B}(\hat P,\, \tilde N)} C_{P}(\pi) \;\le\; \tau, \qquad \text{radius of } \mathcal{B} \propto \sqrt{\frac{S\log(1/\beta)}{\tilde N}} + \frac{S\, E_\epsilon}{\tilde N}.$$
Here $S$ is the number of states and $\beta$ the failure probability. $E_\epsilon$ is a high-probability bound on the noise of a tree-based private counter, which scales like $H\log^{O(1)}(K)/\epsilon$ for horizon $H$ and $K$ users, following Private Reinforcement Learning with PAC and Regret Guarantees. The first term in the radius is ordinary statistical uncertainty. The second is privacy uncertainty; it shrinks as $1/\tilde N$ rather than $1/\sqrt{\tilde N}$, which is where we expect "privacy almost for free" to hold asymptotically.
Our hypothesis is that the cost of privacy for safety concentrates in an additive number of early, conservative episodes, of order $S^2AH^3/\epsilon$, where $A$ is the number of actions. This mirrors the additive privacy term in existing private regret bounds. It is a conjecture to be proved or refuted, not a known result.
Where Privacy Actually Touches Safety
Honesty about scope matters. If the hazard map and dynamics were public, a safety filter could run on public information alone and privacy would be irrelevant to safety. The setting where the two collide is one where the learner must estimate transitions, and therefore reachability of unsafe states, from users' trajectories. Examples are how often a maneuver on a given road segment leads to a near-miss, or how often a route choice leads into a congested or hazardous cell. In that setting every safety check reads private data.
Two findings motivate the privacy side. Trajectory Recovery From Ash reconstructs individual trajectories from aggregate density counts with 73% to 91% accuracy at 100,000 users, and shows that the two most frequent locations identify over 95% of people. Aggregation alone is therefore not a defense, and a sequence of released policies built from raw counts is exactly this kind of aggregate.
A third finding constrains the safety side. Breaking Safety Paradox with Feasible Dual Policy Iteration observes that safer policies see fewer violations, which starves the cost estimates. Under privacy, those rare cost-relevant counts are also the ones most swamped by noise. Pessimism is therefore not optional, and its size must track the privacy noise explicitly.
Research Program
The method is built directly on two tabular private learners. Private Reinforcement Learning with PAC and Regret Guarantees introduced PUCB. It keeps private counters with tree-based mechanisms and adds an exploration bonus that accounts for privacy noise, but it has no cost signal. Near-Optimal Differentially Private Reinforcement Learning introduced DP-UCBVI. It privatizes a variance-aware exploration bonus and uses a linear-program projection so that noisy counts form valid probabilities and never underestimate visits, which preserves optimism for reward. We reuse their counters and accounting unchanged, since post-processing of private counts costs no extra privacy.
We then add three components. The first is a cost-side projection: the dual of Qiao and Wang's linear program, which chooses transition probabilities within the privacy-widened confidence set that maximize expected cost. The second is an optimistic-reward, pessimistic-cost planner, solved as a small linear program over occupancy measures. The third is a safe-mixture rule: when the pessimistic cost of the candidate policy exceeds $\tau$, the agent deploys the largest mixture with the known-safe policy that still passes the check.
Like the backward value function approach in Constrained Markov Decision Processes via Backward Value Functions, which turns trajectory budgets into state-wise checks and needs an initially safe policy, we assume a safe baseline policy is given. Unlike that work, all quantities entering our check are private.
The theory target has two parts: a high-probability bound on the number of budget-violating episodes, and a regret bound whose privacy-dependent term separates cleanly from the statistical one. On the empirical side, we will release the same learner with the privacy width set to zero. This is the ablation that shows symmetric noise alone causes violations.
A second, more exploratory stage asks whether the idea carries to neural policies. There, the privacy mechanism is gradient noise and clipping, not count noise. Differentially Private Multivariate Time Series Forecasting of Aggregated Human Mobility With Deep Learning found that gradient perturbation beats input perturbation for mobility forecasting, with 0.57% to 2.8% error increase, but misses sharp peaks. Rare cost events are exactly such peaks. We will test a cost critic trained with gradient-perturbed training whose output is shifted upward by a calibrated bound on clipping bias. This stage is secondary: its guarantee would be empirical, not proved.
Baselines
The naive reference point is to always run the known-safe baseline policy. It trivially satisfies the budget and leaks nothing beyond the fixed policy, so it anchors the reward floor. Any method must earn reward above it without exceeding its violation rate by more than the target $\beta$.
The strongest private competitor is DP-UCBVI from Near-Optimal Differentially Private Reinforcement Learning, extended with a Lagrangian cost term so that it can target the budget at all. It is the best-known private tabular learner, and its projection is the closest existing mechanism to ours. On Riverswim, the paper reports only that regret at $\epsilon=1$ and $\epsilon=2$ is "only slightly higher than the non-private baseline". No numeric value was reported on Lacuna, so we will rerun it ourselves. It will receive the same privacy accounting, the same $\epsilon$ values, and the same Lagrange-multiplier tuning grid, and the tuning episodes will count toward reported violations for both methods. Beating it means matching its reward within its confidence interval while having a violation count during learning at least an order of magnitude lower at equal $\epsilon$.
The non-private upper reference is our own planner run on exact counts, with the privacy width set to zero and no noise. This isolates the cost of privacy.
The key ablation keeps the noise but removes the privacy width from the confidence radius. It isolates whether the one-sided correction, rather than pessimism in general, is what prevents violations.
For the neural stage, the reference is PPO-Lag from the SafePO library in Safety Gymnasium, which reports a 98% reduction in violations relative to PPO with a 45% reward drop on velocity tasks. It will be trained with standard private gradient training at matched $\epsilon$, both with and without our upward critic shift.
Why not just…?
Why not just tighten the safety budget by a fixed margin and use noisy counts as they are? This is the most serious alternative, because it is one line of code. A fixed margin cannot track the privacy noise. That noise is large relative to counts early on and negligible later, so a fixed margin is either too small early, producing violations, or too large late, freezing the agent near the safe policy. We will sweep the margin over a grid tuned with the same budget as our method and plot violations against reward. If some fixed margin matches our frontier across all $\epsilon$ and environment sizes, we will report that the count-dependent width adds nothing.
Why not privatize the data once and run offline safe RL on it? One could generate synthetic trajectories with DPTraj-PM, which builds a noisy prefix tree plus Markov model under $\epsilon$-DP. Post-processing is free, so one could then train with a constrained offline method such as DRCORL, which reaches normalized return 0.91 against 0.38 for the next safe baseline on CarGoal1. This works if the historical data already cover the risky regions. It fails when the service must explore new actions, because synthetic data inherit the coverage of the logged behavior. DPTraj-PM also reports that fine grids make noise overwhelm sparse transitions. We will run this pipeline at matched $\epsilon$ on the same mobility MDP, varying how much of the state space the logging policy covered. It is a real threat in the high-coverage regime, and we will say so if it wins there.
Why not just coarsen locations and run a non-private safe learner? Xu et al. show aggregated counts are reconstructible at 73% to 91% accuracy, so coarsening provides no formal guarantee. We will include the coarsened learner and attack its released policy sequence with a matching attack in the style of Xu et al., to measure leakage directly rather than argue it.
Why not just put a non-private safety supervisor on top? The on-ramp supervisor in Combining Reinforcement Learning with Model Predictive Control for On-Ramp Merging reaches a 0% crash rate, but it assumes known dynamics and exposes exact states. In our setting the supervisor's model must be learned from users, which returns us to the same private estimation problem.
Proposed Experiments
The first testbed is Riverswim with an added cost on the far-right states, matching the DP-UCBVI setup. The second is the gridworld used for backward value functions. Both are run at $\epsilon \in \{0.5, 1, 2, 5\}$ with $10^4$ to $10^6$ user episodes.
The applied testbed is a routing CMDP built on a 20×20 grid over the Porto taxi data and Geolife. The 20×20 grid is the resolution DPTraj-PM found useful. In this CMDP, transitions are estimated from held-out users' trips, and cost marks cells with high rates of abrupt stops or unusually slow segments, as extracted from the traces. Held-out real traces serve as the simulator.
The metrics are the number of episodes whose realized cost exceeds $\tau$ during learning, cumulative reward regret against the best feasible policy, the number of episodes spent in safe-mixture fallback, and the success rate of a trajectory-matching attack in the style of Xu et al. on the released policies.
Three results are decisive. The first is whether the ablation without the privacy width shows violations that grow as $\epsilon$ shrinks, while the full method keeps violations at or below $\beta K$. The second is whether fallback episodes scale roughly as $1/\epsilon$, as the conjecture predicts, or worse. The third is whether the fixed-margin and offline-synthesis alternatives are dominated on the violation–reward frontier in the low-coverage regime. If the first check fails, symmetric noise was not the problem and the proposal is wrong. If the third fails everywhere, the simpler pipeline should be preferred, and we will report it as the finding.
References
- Private Reinforcement Learning with PAC and Regret Guarantees
- Trajectory Recovery From Ash: User Privacy Is NOT Preserved in Aggregated Mobility Data
- Breaking Safety Paradox with Feasible Dual Policy Iteration
- Near-Optimal Differentially Private Reinforcement Learning
- Constrained Markov Decision Processes via Backward Value Functions
- Differentially Private Multivariate Time Series Forecasting of Aggregated Human Mobility With Deep Learning: Input or Gradient Perturbation?
- Safety Gymnasium: A Unified Safe Reinforcement Learning Benchmark
- DPTraj-PM: Differentially Private Trajectory Synthesis Using Prefix Tree and Markov Process
- Don’t Trade Off Safety: Diffusion Regularization for Constrained Offline RL
- Combining Reinforcement Learning with Model Predictive Control for On-Ramp Merging