- 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 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.
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) 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) 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) 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-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-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/ε 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.