acceptodds
Under review as a conference paper at ICLR 2027

Towards Regret for Private RL with General Function Approximation

Abstract

Recent work on private reinforcement learning with general function approximation establishes regret over episodes, but whether privacy permits the canonical dependence remains open. We resolve this question for a finite Bellman-complete value-function class with bounded Bellman–Eluder dimension. Our main algorithm, Priv-LazyGOLF, privatizes rare policy switching through a twofold use of AboveThreshold: it privately detects when the current hypothesis has accumulated enough Bellman inconsistency and privately selects an optimistic feasible replacement. We show that Priv-LazyGOLF is -jointly differentially private and, with high probability, achieves regret with only logarithmically many policy switches in . Thus, privacy preserves the regret of non-private learning. We also establish that the same private rare-switching template extends, through suitable decomposable losses, to a broader class of reinforcement learning problems while retaining regret and privacy.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Private RL, General function approximation, regret bound, rare switching

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_TvuLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces a private version of the LazyGOLF algorithm which combines the adaptive switching and AboveThreshold techniques from the RL and privacy literature respectively, to obtain and algorithm with a \sqrt{K} regret bound with (\epsilon, \delta)-JDP. This offers an improvement on prior work, which can only offer a O(K^{3/5}) regret with privacy.

On the RL side, this still does not answer the question in the most general terms, due to its Bellman completeness assumption inherent in the Bellman-Eluder framework. The algorithms need structural changes (doable) for the more general V-type settings such as in Bellman/Bilinear rank or DEC frameworks.

The techniques used seem relatively standard and well-known, both on the RL and privacy side. The main novelty relative to direct prior works seems to be adaptive switching based on data-dependent Bellman error checks, but most arguments used are largely standard in the literature.

The authors note that there is an undesirable multiplicative amplification of sample complexity in terms of privacy \epsilon, which does not happen in contextual bandits and supervised learning.

Critical strengths

The overall paper is well written, mostly easy to follow and the algorithm and its analysis are sound. The results do improve upon the best prior known results and the data-dependent switching approach seems clever.

Critical weaknesses

This paper largely falls into the bucket of combining ideas from two areas in a relatively straightforward manner, and it is not clear that there are significant new technical insights or elements involved.

This can be okay if the end result is practically important, but the paper does develop an information-theoretic algorithm, as the authors themselves admit. Owing to this, I find the work relatively underwhelming.

Questions for authors

If there are key technical insights or novelty that I am missing, please feel free to correct me.

2 comments

Thank you for the thoughtful review and for recognizing the soundness of our analysis. We address your concerns below and hope our responses convey the technical insights and significance of our results.


1. Key technical insights and novelty

Thank you for inviting us to clarify the technical insights. Our contribution is to show how confidence-set optimism and rare switching can be jointly privatized using AboveThreshold, resolving two fundamental challenges in privatizing GOLF.

(1) Privatizing confidence-set-based optimism. As He and Zhou (2026) emphasize, this approach is difficult to privatize because it requires repeatedly constructing and updating data-dependent confidence regions. We provide a private implementation of this approach through our selector (Appendix D.2, Lemma D.3).

(2) Establishing rare switching under privatization. A valid analysis must account for both private hypothesis selection and private update timing. This challenge arises even in linear settings: He and Zhou (2026) identify gaps in earlier private rare-switching analyses that invalidate the claimed guarantees.

Our key insight is that AboveThreshold can address both challenges through the selector and trigger in our algorithm, and we formally establish the guarantees needed for private optimism and rare switching (Lemma D.3 and Appendix D.3, Lemmas D.4–D.6 and Theorem D.7). To the best of our knowledge, this is the first use of AboveThreshold in private RL. We also view the use of a standard DP primitive to resolve these challenges as a contribution in its own right: it yields a simple construction with a rigorous analysis.

As a further consequence, our AboveThreshold-based rare-switching scheme can be combined with private LSVI-UCB to obtain, to the best of our knowledge, the first correct O~(K)\widetilde O(\sqrt K) regret guarantee for private linear MDPs. See Appendix F.1 of the revised paper for more discussion.


2. Significance of the information-theoretic result.

Our algorithm addresses a fundamental statistical question: can privacy preserve the non-private O~(K)\widetilde O(\sqrt K) regret rate under general function approximation? We answer this affirmatively for finite Bellman-complete classes with bounded point-mass Bellman–Eluder dimension, at fixed privacy and structural parameters (Theorem 5.1).

Resolving this question independently of computational efficiency establishes what is statistically attainable and provides a foundation for efficient algorithm design, following the role of information-theoretic algorithms such as GOLF in non-private RL. Our result shows that a worse episode exponent is not an unavoidable consequence of privacy in this regime, making O~(K)\widetilde O(\sqrt K) a justified target for computationally efficient private methods.

We acknowledge that exhaustive hypothesis selection limits the algorithm’s practical applicability. Its contribution is the statistical guarantee and the private optimism and switching mechanisms that enable it. Developing an efficient implementation with comparable guarantees remains an important direction, discussed in Section 7 under “Towards oracle efficiency and infinite classes.”


3. Structural assumptions

We agree that our guarantees apply under the structural assumptions considered in the paper—Bellman completeness with bounded point-mass Bellman–Eluder dimension, or the stated ℓ2\ell_2-EC conditions (Section 6, Theorem 6.1, and Appendix E)—and do not establish coverage of general V-type, Bellman/bilinear-rank, or DEC settings. This limitation is also present in the corresponding non-private work of Xiong et al. (2024), whose guarantees rely on the EC and decomposability conditions.

Our contribution is to establish that K\sqrt{K}-regret remains attainable under joint differential privacy within this framework. We view this result as a foundation for developing private RL under other structural conditions, following the progression of non-private RL theory through guarantees under different and increasingly general assumptions. Extending our result to these broader settings is an important direction for future work.


4. Multiplicative privacy cost.

We agree that the multiplicative dependence on 1/ε1/\varepsilon is a limitation. However, this issue is not unique to our setting: existing JDP guarantees for linear MDPs also incur multiplicative privacy costs (Luyo et al., 2021). Moreover, recent additive-cost guarantees for linear contextual bandits assume i.i.d. contexts (Chen et al., 2025); That is, even for general linear contextual bandit problems, obtaining additive privacy cost under JDP remains open to our knowledge.

Thank you again for inviting us to clarify the technical contribution. As the discussion period draws to a close, we’d appreciate any feedback on our explanation of how the algorithm and analysis preserve both optimism and rare switching under privacy.

Reviewer_BzF3OpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies episodic RL with a finite Bellman-complete value-function class and bounded point-mass Bellman–Eluder (BE) dimension, under joint differential privacy (JDP). The prior state of the art for general function approximation (He & Zhou, 2026) achieves O(K3/5)O(K^{3/5}) regret under coverability, using fixed-size batching and the exponential mechanism. The authors propose Priv-LazyGOLF, a private version of the rare-switching algorithm LazyGOLF (Xiong et al., 2024), which uses AboveThreshold twice. A "trigger" privately decides when the current hypothesis has accumulated enough Bellman inconsistency. A "selector" scans a public, value-ordered list of hypotheses and picks the first one that passes a noisy feasibility test. AboveThreshold's privacy cost does not grow with the number of negative answers, and the number of switches is O(dHlog⁡K)O(dH \log K). A deterministic cap M on private calls makes composition valid on every execution path. The paper proves (epsilon,delta)-JDP and O(K)O(\sqrt{K}) regret (Thm 5.1), with privacy entering multiplicatively (the second term scales as (K/ϵ))\sqrt{(K/\epsilon))}. It then extends the template to the ℓ2\ell_2-Eluder Condition framework.

Critical strengths

Disclaimer: my expertise in theoretical RL is very limited. Please weigh my review accordingly.

A simple, well-motivated idea that gives a clear answer in its setting. Both data-dependent decisions in rare switching (when to switch, which hypothesis to pick) fit AboveThreshold's one-positive interface.

Critical weaknesses

From my limited vantage point, the construction mostly assembles known components (LazyGOLF, AboveThreshold, advanced composition, the Billboard Lemma). I cannot judge how non-trivial the epoch accounting and the cap argument are relative to prior work, and I defer to other reviewers on this. The privacy cost enters multiplicatively, with H5/4H^{5/4}, d1/2d^{1/2}, and dmax1/4d_max^{1/4} factors, and no lower bound is given. It is therefore unclear whether the ϵ\epsilon- and H-dependence is tight. The authors acknowledge the multiplicative-vs-additive question as open.

Questions for authors
  1. What happens to the regret guarantee if the certified d_max is smaller than the true d (e.g., d_max is misspecified)? Is there a way to avoid or adapt the cap, or to avoid knowing d_max at all?
  2. Please clarify the precise sense in which the "gap" between private and non-private RL is closed, given that coverability, the setting of He & Zhou (2026), is not covered.
2 comments

Thank you for the careful review and constructive questions. We address your concerns below and hope our responses clarify the guarantees and contributions of our work.


Q1. Misspecified or unknown dimension. Underestimating dmax⁡d_{\max} preserves JDP when the noise is calibrated to the supplied public cap, but can invalidate sublinear regret: exhausting the cap freezes the current policy and can cause linear remaining regret (revised Remark 5.2).

We can adapt to unknown dd via doubling trick, with only logarithmic overhead in regret. Start with D0=1D_0=1. Whenever a phase exhausts its cap, discard its data and internal state, double the guess, and restart with fresh noise.

Crucially, on the joint utility event, the trigger-count argument remains valid even when Dj<dD_j<d. The phase-dependent radius Γj\Gamma_j appears in both the total residual-energy bound, O(dHΓjlog⁡K)O(dH\Gamma_j\log K), and the energy consumed per trigger, Ω(Γj)\Omega(\Gamma_j), so it cancels. Thus the trigger count is O(dHlog⁡K)O(dH\log K) regardless of the guess. With our cap constants, exhausting a phase implies Dj≤d/2D_j\le d/2; consequently, at most 1+⌊log⁡2d⌋1+\lfloor\log_2d\rfloor phases are entered. Appendix F.3 of the revised paper sketches the privacy argument and the treatment of random restart times, retaining the polynomial parameter dependence of Theorem 5.1 with dmax⁡=dd_{\max}=d, up to logarithmic factors.


Q2. Precise scope of the gap claim.

By “closing the gap,” we mean establishing that private RL can attain the non-private O~(K)\widetilde O(\sqrt K) episode dependence under our stated BE and ℓ2\ell_2-EC assumptions (Theorems 5.1 and 6.1). We do not mean improving He & Zhou’s O~(K3/5)\widetilde O(K^{3/5}) guarantee under coverability, which is a different structural setting; Proposition A.1 establishes the incomparability of coverability and our point-mass BE condition. The revised Introduction and the clarification following Theorem 5.1 make this distinction explicit.

Thank you again for your questions about the switching cap and the scope of the regret guarantee. As the discussion period draws to a close, we’d welcome any thoughts on whether our response addresses those questions.

Reviewer_5z1oOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

I understand that Priv-LazyGOLF aims to address whether reinforcement learning under privacy constraints can still achieve regret close to K\sqrt{K}. The method uses two “AboveThreshold” channels to hide the timing of policy updates and the choice of optimistic Q-functions (or hypotheses), respectively, and uses a deterministic upper bound on policy switches to establish Joint Differential Privacy (JDP). The authors’ theorem requires a finite Bellman-complete function class and specific Bellman–Eluder complexity conditions; I would not interpret this as providing a general deep RL algorithm that can be efficiently deployed.

Critical strengths

S1/S2: I believe that simultaneously protecting both when a policy switches and which optimistic hypothesis is chosen is the meaningful part of the paper. Privacy mechanisms often interfere with RL’s adaptive updates; therefore, linking the privacy composition with regret analysis—and ultimately preserving the O~(K)\widetilde O(\sqrt K) order of magnitude—does indeed provide theoretical evidence of feasibility.

Critical weaknesses

W1: My original question was: Since sparse switching and AboveThreshold are not new tools, compared to Xiong et al.’s non-private sparse-switching RL framework, which aspects of the coupled analysis are new? Additionally, the finite function class and exhaustive hypothesis search limit the algorithm’s applicability; this needs to be made clear in the abstract or alongside the main theorems.

W2: My greatest concern is the finite-sample constant. The asymptotic regret of K\sqrt K does not imply that, for K=106K=10^6 and given ε,δ\varepsilon,\delta, the privacy threshold allows the algorithm to perform a useful policy update. If the trigger threshold for AboveThreshold is higher than the advantage signal that can be accumulated over the entire learning period, the algorithm may continue to use the initial suboptimal policy indefinitely. This is the practical issue I really want the authors to address.

Questions for authors

Q1: I would like to see the proof steps that genuinely address private triggering and private hypothesis selection, as compared to non-private LazyGOLF-style methods.

Q2: I would like to see a concrete finite-parameter example with KK, ε\varepsilon, and δ\delta that demonstrates how the threshold can be matched with the accumulated Bellman-loss signal.

Q3: I would like the authors to explain the relationship between M<KM<K in Algorithm 2 and the parameter conditions in Theorem 5.1.

5 comments

Thank you for the thoughtful review and for recognizing our theoretical contribution. We address your concerns below and hope our responses clarify the novelty and significance of our results.


Q1/W1. What is new beyond Xiong et al. (2024)?

Our new contribution lies in privatizing the non-private algorithm of Xiong et al. (2024), which requires resolving two fundamental challenges.

(1) Privatizing confidence-set-based optimism. As He and Zhou (2026) emphasize, this approach is difficult to privatize because it requires repeatedly constructing and updating data-dependent confidence regions. We provide a private implementation of this approach through our selector (Appendix D.2, Lemma D.3).

(2) Establishing rare switching under privacy. A valid analysis must account for both private hypothesis selection and private update timing. This challenge arises even in linear settings: He and Zhou (2026) identify gaps in earlier private rare-switching analyses that invalidate the claimed guarantees.

Our key insight is that AboveThreshold can address both challenges through the selector and trigger in our algorithm, and we formally establish the guarantees needed for private optimism and rare switching (Lemma D.3 and Appendix D.3, Lemmas D.4–D.6 and Theorem D.7). To the best of our knowledge, this is the first use of AboveThreshold in private RL. We also view the use of a standard DP primitive to resolve these challenges as a contribution in its own right: it yields a simple construction with a rigorous analysis.

As a further consequence, our AboveThreshold-based rare-switching scheme can be combined with private LSVI-UCB to obtain, to the best of our knowledge, the first correct root-K regret guarantee for private linear MDPs. See more discussion in Appendix F.1 of the revised paper.


W2/Q2. Finite-time guarantees.

We agree that our asymptotic root-K bound can be vacuous at finite KK with conservative constant choices. This issue also arises without privacy: a conservative explicit instantiation of Xiong et al.’s (2024) non-private bound can likewise be vacuous at K=106K=10^6 because of large constants.

We did not optimize these constants in the current version. They can be improved through sharper analysis within the same Algorithm 2. For example, we can tighten the concentration argument leading to Eq. (11), retain the harmonic sum in Lemma B.3 instead of its coarser upper bound, and sharpen the historical residual budget in Lemma D.4. These refinements improve the constants in the energy and regret bounds, Eqs. (13)–(14).

Moreover, for small finite function classes, such as the reviewer’s example, a no-reselection argument bounds positive triggers by N−1N-1 (where NN is the size of function class). We can therefore use M=NM=N when it is smaller than the original dimension-based cap, reducing privacy noise at the same privacy level. Taking the minimum with the original cap preserves logarithmic explicit dependence on NN.

Please refer to Appendix F.2 of the revised paper for more discussion on this.


Q3. The condition M<KM<K.

This restriction is unnecessary. We initially included M<KM<K to emphasize the intended rare-switching regime, where the cap is smaller than the episode budget. However, neither proof requires it: privacy uses only the all-path call bound 2min⁡{M,K}−1≤2M−12\min\{M,K\}-1\le 2M-1, while utility requires M>32dHΛKM>32dH\Lambda_K, satisfied by the theorem’s choice M=⌈64dmax⁡HΛK⌉M=\lceil64d_{\max}H\Lambda_K\rceil since dmax⁡≥dd_{\max}\ge d. We therefore remove M<KM<K from Algorithm 2 and Remark 4.2, requiring only a public positive integer MM. This correction preserves Theorem 5.1’s original parameters and privacy and regret guarantees.

Reviewer_5z1oOpenReview ↗

Finite-sample calibration

I will keep my score at 3. The argument for removing M<K is convincing: privacy uses a deterministic bound on the number of calls, while utility needs a lower bound on the cap. Protecting both update timing and optimistic selection is also a useful contribution. I agree with the stated scope of the root-K result for finite Bellman-complete point-mass BE classes. The finite-sample issue is still open for me. Take a single-state H=1 instance, rewards (0,1/2), and the two functions (0,1/2) and (1,0). This satisfies the assumptions with N=2 and d=1; the initial policy is suboptimal and before the first switch, its excess-loss statistic equals k. With K=1,000,000, epsilon=1, delta=0.000001, alpha=0.05 and c0=64, replacing the cap by M=N=2 still leaves the switching threshold minus its accuracy margin at about 1.44 million. The policy therefore never switches on the AboveThreshold accuracy event under this calibration. This is a limitation of the conservative finite-sample parameters; the asymptotic theorem remains intact. Could you show whether the further refinements in F.2 give a useful guarantee for this example? A short calculation would settle the remaining part of my question.

Thank you for recognizing the positive contribution of our work and for the further opportunity of clarifying the finite-time guarantee through a concrete example.

Yes, our algorithm can switch to the optimal function in your example via two different tighter analyses.

1. Tighter constants in Lemma D.4 and Lemma D.6. As hinted in Appendix F.2, we can derive a smaller switching multiplier (from 16 to 6) via improved constants in these two lemmas, which leads to the successful switch and a regret less than KK.

Specifically, write β=βfit\beta=\beta_{\mathsf{fit}} and Γ=β+4ω\Gamma=\beta+4\omega. We will show that β~switch=6Γ\widetilde\beta_{\mathsf{switch}}=6\Gamma is sufficient (rather than 16Γ16 \Gamma). On the good event, recomputing Lemma D.4 with this threshold gives the historical squared-residual budget

B=43(6Γ+2ω+β)≤283Γ,B=\frac43(6\Gamma+2\omega+\beta)\le\frac{28}{3}\Gamma,

instead of carrying over the original coarse bound 24Γ24\Gamma. We also recompute the fresh energy in Lemma D.6: a positive trigger gives terminal prefix excess at least 6Γ−2ω6\Gamma-2\omega, while the prefix excess at the epoch's start is at most Γ\Gamma. Subadditivity and the concentration upper bound therefore give fresh squared-residual energy at least

=\frac{12}{5}\Gamma+\frac{24}{5}\omega \ge\frac{12}{5}\Gamma.$$ Lemma B.3 bounds total executed energy by $12dB\Lambda_K\le112d\Gamma\Lambda_K$ per stage. Consequently, the trigger count through any putative first cap hit is at most $$\frac{112dH\Gamma\Lambda_K}{(12/5)\Gamma} =\frac{140}{3}dH\Lambda_K <64d_{\max}H\Lambda_K.$$ Thus the smaller multiplier ($6\Gamma$) still works. The finite-class no-reselection argument in F.2 also remains valid: a triggered hypothesis has subsequent excess loss at least $(7/5)\beta+(66/5)\omega>\Gamma$, so it cannot pass another selector. Since $Q^\star$ never triggers, there are at most $N-1$ positive triggers, and your finite-class cap $M=N=2$ remains nonbinding. Keeping $c_0=64$ and sensitivity $\Delta=8$, your parameters give $$\varepsilon_0=\frac{1}{4\sqrt{6\log(2\times10^6)}}\approx0.0267948, \qquad \beta\approx2316.2305, \qquad \omega\approx22701.0729, \qquad \Gamma\approx93120.5222.$$ The new switching threshold is $6\Gamma\approx558723.1332$. On the AboveThreshold accuracy event, the identity $\widehat E_k((1,0))=k$ forces a trigger by $$\tau\le\lceil6\Gamma+2\omega\rceil=604126<K.$$ At the trigger, the wrong hypothesis has excess at least $6\Gamma-2\omega\approx513320.9873>\Gamma$, so the selector rejects it and accepts $Q^\star=(0,1/2)$, whose excess remains at most $\beta$ and hence below the trigger threshold on the joint event. Each pre-switch episode incurs regret $1/2$, giving $$\operatorname{Reg}(10^6)\le\tau/2\le302063,$$ compared with $500000$ if the initial policy never switches. *2. Replace advanced composition with basic composition.* An even simpler alternative is to retain the original switching multiplier $16$ and use basic adaptive composition. With the same $M=2$, Algorithm 2 makes at most $L=3$ AboveThreshold invocations on every execution path. Each invocation is pure $\varepsilon_0$-DP, so choosing $\varepsilon_0=\varepsilon/L=1/3$ gives **$(1,0)$-JDP**, which is stronger than the requested $(1,10^{-6})$-JDP guarantee. Recomputing the noise allowance and thresholds gives $\omega\approx1824.8132$ and $\Gamma\approx9615.4831$. The same switching argument then yields $$\tau\le\lceil16\Gamma+2\omega\rceil=157498, \qquad \operatorname{Reg}(10^6)\le78749.$$ Note that the basic composition only gains in the regime where $L$ is small, as in the example. --- We hope the above calculations address your remaining concern. We are looking forward to your valuable feedback. Thanks again for your time!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.