Near-Optimal Differentially Private Reinforcement Learning
Near-Optimal Differentially Private Reinforcement Learning
复制标题
DOI：
10.48550/arxiv.2212.04680
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Dan Qiao;Yu-Xiang Wang
中科院分区：
文献类型：
--
作者：
Dan Qiao;Yu-Xiang Wang
受个性化医疗保健和其他涉及敏感数据的应用的启发，我们研究了具有差异隐私(DP)约束的强化学习中的在线探索。已有的研究表明，在联合差分隐私(JDP)和局部差分隐私(LDP)下，无遗憾学习是可能的，但没有提供一个具有最优遗憾的算法。我们通过设计一个带有$\widetilde{O}(\sqrt{SAH^2T}+S^2AH^3/\epsilon)$遗憾的$epsilon$-jdp算法来弥补这一差距，该算法匹配$epsilon>；S^{1.5}A^{0.5}H^2/\Sqrt{T}的所有选择的非私人学习的信息论下界。其中，$S$，$A$表示状态和行动的数量，$H$表示规划范围，$T$表示步骤数。就我们所知，这是第一个私有RL算法，它以$T\right tarrow\infty$的形式渐进地实现了\emph{免费隐私}。我们的技术--可能是独立利益的--包括私下发放伯恩斯坦式的勘探奖金，以及一种改进的发布访问统计数据的方法。同样的技巧也意味着，自民党案的悔恨界限略有改善。
Motivated by personalized healthcare and other applications involving sensitive data, we study online exploration in reinforcement learning with differential privacy (DP) constraints. Existing work on this problem established that no-regret learning is possible under joint differential privacy (JDP) and local differential privacy (LDP) but did not provide an algorithm with optimal regret. We close this gap for the JDP case by designing an $\epsilon$-JDP algorithm with a regret of $\widetilde{O}(\sqrt{SAH^2T}+S^2AH^3/\epsilon)$ which matches the information-theoretic lower bound of non-private learning for all choices of $\epsilon>S^{1.5}A^{0.5} H^2/\sqrt{T}$. In the above, $S$, $A$ denote the number of states and actions, $H$ denotes the planning horizon, and $T$ is the number of steps. To the best of our knowledge, this is the first private RL algorithm that achieves \emph{privacy for free} asymptotically as $T\rightarrow \infty$. Our techniques -- which could be of independent interest -- include privately releasing Bernstein-type exploration bonuses and an improved method for releasing visitation statistics. The same techniques also imply a slightly improved regret bound for the LDP case.