Private RL with General Function Approximation: Breaking the Linear Barrier

TL;DR

Researchers have finally bridged the gap between Differential Privacy (DP) and General Function Approximation in Reinforcement Learning (RL). By moving away from complex confidence sets toward a batched, unconstrained optimization objective using the Exponential Mechanism, this paper proves that we can achieve sublinear regret—specifically $O(K^{3/5})$—even when using non-linear models like deep networks.

Academic Positioning: This is a foundational theoretical work that generalizes private RL from simple "tabular/linear" environments to the "general function" regime, matching SOTA performance while correcting technical flaws in previous literature.

The "Liner" Problem in Private RL

Until now, if you wanted to perform RL while protecting user privacy (e.g., in medical recommendations or LLM fine-tuning), you were stuck with two options:

1. Tabular RL: Only works if your state space is tiny.
2. Linear Function Approximation: Assumes the world is linear, which it rarely is.

The primary technical hurdle was that traditional RL exploration depends on Upper Confidence Bounds (UCB). Constructing a private "confidence set" over a complex neural network's parameter space is a nightmare—it doesn't allow for the simple sufficient statistics used in linear models.

The Core Insight: Softmax and Batches

The authors propose a shift in perspective. Instead of saying "find the best policy within this private confidence region," they treat exploration as a sampling problem.

1. Unconstrained Optimization (The Score Function)

They define a score function $S(f)$ that balances two things:

• Bellman Loss: How well does the model fit the observed data?
• Optimism: Does the model predict high rewards for the initial state?

2. The Exponential Mechanism

To make the selection private, they don't pick the function that maximizes $S(f)$. Instead, they sample a function from the distribution: $P(f)\propto \exp (\beta \cdot S(f))$ This is effectively a Softmax version of the policy update, which inherently satisfies Differential Privacy.

3. Smart Batching

Updating after every episode destroys the privacy budget (high composition). By updating in batches of size $B$, the agent only "looks" at the private data occasionally, drastically slowing the accumulation of privacy loss.

Impact on LLMs (Deterministic Outcome Rewards)

A significant portion of the paper focuses on Deterministic MDPs with Outcome Rewards. This is precisely the setting for LLM alignment (e.g., RLHF):

• Deterministic: Given a prompt and a response, the "next state" is fixed in the context.
• Outcome Reward: You only get a reward (like a 'thumbs up') at the very end of the interaction.

In this setting, the authors show that you can relax the "Bellman Completeness" requirement—a notoriously hard-to-satisfy mathematical condition—requiring only Realizability (that the true Q-function is actually in your model class).

Experimental Proof-of-Concept

The authors validated their theory with a simulation involving context-dependent target sequences. The results demonstrate the "Privacy-Utility Tradeoff" clearly: as privacy constraints ($ϵ$) become tighter, the model takes longer to plateau, but still eventually learns the optimal policy.

Correcting the Record

A critical contribution of this paper is Appendix C, where the authors identify a "monotonicity gap" in previous papers (Ngo et al., 2022 and Sahu, 2025). Previous claims of $O(\sqrt{K})$ private regret in model-free linear settings relied on a "determinant trick" that fails when privacy noise is added to the design matrix. This paper clarifies that $K^{3/5}$ is the current true SOTA for this setting.

Conclusion

This work transitions Private RL from "toy examples" to "real-world potential." By leveraging the Coverability constant and unconstrained optimization, it provides the first rigorous guarantee for private RL agents that use the same complex models we actually use in production.

Future Outlook: The $K^{3/5}$ vs $\sqrt{K}$ gap remains an open theoretical battleground. Can we achieve $\sqrt{K}$ without the linear model tricks? This paper sets the stage for that next breakthrough.