Towards $\sqrt{K}$ Regret for Private RL with General Function Approximation

Recent work on private reinforcement learning with general function approximation establishes $\tilde{O}(K^{3/5})$ regret over $K$ episodes, but whether privacy permits the canonical $\tilde{O}(\sqrt{K})$ 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 $(ϵ,\delta )$-jointly differentially private and, with high probability, achieves $\tilde{O}(\sqrt{K})$ regret with only logarithmically many policy switches in $K$. Thus, privacy preserves the $\sqrt{K}$ 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 $\tilde{O}(\sqrt{K})$ regret and privacy.