🤖 machine learning

Towards Differentially Private Reinforcement Learning with General Function Approximation

本文首次为具有通用函数逼近能力的差分隐私在线强化学习提供了理论保证，通过新颖地结合批量策略更新与指数机制实现了 $\widetilde{O}(K^{3/5})$ 的遗憾界，同时也厘清了先前线性设定中存在的差距。

原作者： Yi He, Xingyu Zhou

发布于 2026-05-11

📖 1 分钟阅读☕ 轻松阅读

原作者： Yi He, Xingyu Zhou

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在教一个机器人玩一款复杂的电子游戏。机器人通过尝试不同的动作、观察结果并获得积分（奖励）来学习。随着时间的推移，它会变得越来越擅长。这就是强化学习（RL）。

然而，在现实世界中，这个机器人不仅仅是在玩游戏；它正在与你互动。也许它是一个正在学习你喜好的聊天机器人，或者是一个正在学习如何治疗患者的医疗人工智能。每次机器人与你互动时，它都会了解到关于你的一些秘密：你的健康史、个人偏好或私密想法。

问题出在哪里？标准的学习方法就像一位老师，在白板上的每个学生的名字旁边写下他们的错误。最终，任何人都可以查看白板，确切地找出是谁犯了哪个错误。这就是隐私泄露。

重大挑战：隐私与学习速度的权衡

科学家们一直试图利用一种称为**差分隐私（DP）**的概念来解决这个问题。可以将 DP 想象为在老师的笔记中加入一点“静电”或“噪声”，这样没有人能确切知道某个特定学生做了什么，但整个班级仍然能学到正确的答案。

但这里有个陷阱：如果你为了保护隐私而加入太多噪声，机器人学习得非常慢；如果你加入的噪声太少，它学习得很快，但会泄露秘密。

长期以来，科学家们只能证明这种隐私技巧仅适用于非常简单的游戏（例如只有几个方格的网格）或规则非常简单（线性）的游戏。但现代人工智能（如我们今天使用的聊天机器人）玩的是复杂、非线性的游戏。旧的数学方法无法适用于这些复杂场景。

本文做了什么

本文首次证明了，你可以在保护用户秘密的同时教机器人玩复杂游戏，而无需牺牲过多的学习速度。

他们是如何做到的？主要使用了三个技巧：

1. “批处理”策略（集体照）

想象一下，机器人每听一个学生说一句话，就拍一张教室的照片。如果你想保护隐私，你就必须每次都对照片进行模糊处理。模糊处理 1,000 张照片工作量巨大，而且会破坏照片质量。

相反，本文建议：等到有一整组学生（一个“批次”）时，再拍一张照片。

工作原理：机器人与用户互动一段时间，收集所有数据，然后一次性为整个群体更新其策略。
好处：你只需要添加几次“隐私噪声”（每个批次一次），而不是成千上万次。这在保护每个人的同时，使学习速度保持得更快。

2. “指数机制”（加权彩票）

通常，当机器人学习时，它会挑选迄今为止找到的单个“最佳”动作。但挑选绝对最佳动作对隐私是危险的，因为它会确切地揭示数据的样子。

相反，本文使用了一种加权彩票：

想象机器人有一个可能的策略列表。
它给“最佳”策略多分配几张彩票，但也给“尚可”的策略分配几张彩票。
然后，它根据这些彩票随机选择一个策略。
结果：机器人大多数时候仍然会选择一个非常好的策略，但由于这是一种彩票，局外人无法 100% 确定是哪个具体的数据点导致机器人选择了该策略。这就像在不知道谁买了彩票的情况下猜测哪张彩票中奖了。

3. “记分牌”（不再需要复杂的规则）

过去，为了私下教授复杂游戏，科学家们试图构建“置信度地图”（一本复杂的规则书，上面写着“我对这一点有 90% 的把握”）。这些地图很难用隐私噪声来保护。

本文跳过了地图。相反，它使用了一个简单的记分牌：

它根据每个可能策略的表现和探索程度给它们打分。
然后，它根据这些分数运行加权彩票（来自第 2 步）。
这要简单得多，也更容易保护。

结果：速度有多快？

本文从数学上证明了这种方法有效。

速度：机器人学习的速度几乎与最好的非隐私机器人一样快。如果机器人进行 $K$ 轮游戏，它所犯的“错误”以大约 $K^{3/5}$ 的速率增长（这比总轮数慢得多）。
对比：这是以前仅适用于简单线性游戏的速度记录。现在，它也适用于复杂的一般游戏。

关于“线性”声明的说明

本文还指出了最近一些研究中的一个错误。其他一些研究人员声称，通过非常罕见地更新策略，他们可以为简单游戏实现更快的隐私学习速度（速度为 $\sqrt{K}$ ）。本文的作者发现了他们数学中的一个缺陷：他们添加的隐私噪声实际上破坏了他们“罕见更新”技巧的逻辑。因此，本文得出的 $K^{3/5}$ 速度目前是针对此类隐私学习已证明的最佳速度。

总结

用通俗的话来说：本文建立了一种新方法，用于教导人工智能代理执行复杂任务（如聊天机器人或医疗顾问），同时尊重用户隐私。它通过在更新人工智能之前将互动分组，使用随机化彩票来选择新策略而不是僵化的规则，并证明该方法在数学上是安全且高效的。这是让从我们身上学习的人工智能在不窥探我们的情况下向前迈出的重要一步。

技术摘要：迈向具有通用函数近似的差分隐私强化学习

问题陈述
本文解决了在形式化隐私保证下，当环境采用通用函数近似建模时，实现样本高效的在线强化学习（RL）所面临的挑战。尽管此前关于差分隐私（DP）RL 的理论工作已建立了次线性遗憾界，但这些结果主要局限于表格型环境或线性函数近似设置。作者指出了一个关键缺口：将这些保证扩展到通用的、非线性的函数类（例如神经网络或复杂的假设类）仍然是一个未解决的问题。核心问题在于：在**联合差分隐私（JDP）**下，针对具有通用函数近似的隐私保护 RL，是否能够实现次线性遗憾？JDP 是标准 DP 的一种松弛形式，适用于个性化 RL，其中必须保持单个用户动作的隐私，同时学习全局策略。

方法论
作者提出了一种无模型 RL 框架，该框架整合了三个关键算法组件，以应对探索、通用函数近似与隐私之间的张力：

无约束优化目标：与通常依赖基于置信集约束优化的标准非隐私 RL（例如上置信界方法）不同，所提出的方法采用无约束优化目标。该目标显式地平衡估计值（乐观性）与统计误差（贝尔曼损失）。这种公式化避免了私有化复杂的、数据依赖的置信集的困难。
用于策略选择的指数机制：为了从函数类 $\mathcal{F}$ 中私有化价值函数（进而策略）的选择，算法采用指数机制。算法不是确定性地选择得分最高的函数（这将泄露敏感数据），而是以与 $\exp(\beta \cdot S(f))$ 成正比的概率采样函数 $f^{(k)}$ ，其中 $S(f)$ 是结合乐观价值与贝尔曼损失的得分函数。
批处理策略更新：为了控制 $K$ 个回合中累积的隐私损失（组合），算法仅在固定大小、大小为 $B$ 的批次开始时更新策略。在一个批次内，策略保持不变。这种策略限制了单个数据点参与私有更新的次数，从而允许隐私损失呈次线性累积，而非线性累积。

本文提出了两种具体算法：

算法 1：专为通用随机马尔可夫决策过程（MDP）设计。它要求贝尔曼完备性（函数类必须在贝尔曼算子下封闭），并使用带有下确界修正的贝尔曼误差损失来处理双重采样问题。
算法 2：专为具有结果奖励的确定性 MDP设计（这一设置受大语言模型应用的启发）。该变体将要求放宽为可实现性（最优 Q 函数存在于该类中），并用基于结果的贝尔曼残差损失替代贝尔曼误差损失，从而消除了对极小极大优化的需求。

主要贡献

通用函数近似的第一个理论保证：本文建立了在 JDP 下具有通用函数近似的在线 RL 的首个次线性遗憾界。
遗憾界：
- 对于通用随机 MDP（算法 1），遗憾规模为 $\tilde{O}(K^{3/5})$ ，取决于刻画探索难度的覆盖性参数 $C_{cov}$ 。
- 对于具有结果奖励的确定性 MDP（算法 2），在较弱可实现性假设下，实现了类似的 $\tilde{O}(K^{3/5})$ 界。
- 尽管通用函数类的复杂性增加，这些界与无模型设置中线性函数近似案例的最先进结果相匹配。
非隐私副产品：该分析得出了在适应性约束（固定大小批处理）下非隐私 RL 的新遗憾界。具体而言，它表明在覆盖性条件下，通过 $\sqrt{K}$ 次更新可实现 $\tilde{O}(\sqrt{K})$ 的遗憾，这补充了基于 Eluder 条件类的现有结果。
线性 MDP 文献的澄清：作者指出了近期关于具有线性 MDP 的隐私 RL 改进的 $\tilde{O}(\sqrt{K})$ 遗憾界主张中的根本缺陷。他们认为，现有依赖“罕见策略切换”和行列式技巧的证明在隐私约束下失效，因为注入隐私噪声破坏了设计矩阵所需的单调性。

结果与分析
理论分析依赖于覆盖性常数，这是由 Xie 等人 [XFBJK22] 引入的复杂度度量，它将探索难度的概念推广到线性设置之外。证明概要包括：

将遗憾分解为与“训练误差”（贝尔曼损失）相关的项和“同策略”（测试）误差。
利用指数机制来界定所选函数与最优函数之间的偏差（隐私成本）。
推导一个新的不等式，以在存在批处理的情况下将同策略误差与训练误差联系起来，利用覆盖性常数来界定数据收集策略与当前策略之间的分布偏移。
优化批次大小 $B$ 和温度参数 $\eta$ ，以平衡信息新鲜度（遗憾）与隐私成本之间的权衡。

本文包含一个在确定性结果奖励设置中的概念验证模拟。结果展示了预期的隐私 - 效用权衡：更强的隐私（更低的 $\epsilon$ ）导致更慢的收敛（更高的平台期回合数），而批处理与非隐私、非批处理学习相比引入了适度的延迟。

意义
本文声称，为反映现代应用（如涉及大语言模型（LLM）和复杂的非线性函数近似器的应用）的场景中的隐私 RL 提供了首个原则性的理论基础。通过证明在线性设置中可实现的 $\tilde{O}(K^{3/5})$ 遗憾缩放可扩展到 JDP 下的通用函数类，这项工作弥合了隐私保护理论与实际 RL 系统之间的重大差距。此外，通过揭示近期关于线性 MDP 文献中的缺陷，本文旨在阐明隐私 RL 的格局，确保未来的理论进步建立在坚实的分析基础之上。该框架被提出作为一种模块化方法，可适应各种隐私机制和函数类。