技术摘要：差分隐私策略优化的样本复杂度

问题陈述

策略优化（PO）是现代强化学习（RL）的核心组成部分，其应用范围从机器人技术到大语言模型（LLM）训练。然而，将 PO 部署于敏感领域（如个性化医疗、LLM 对齐）引发了重大的隐私担忧，因为最近的实证研究表明，标准算法（如 GRPO）可能会泄露隐私信息。

虽然差分隐私（DP）在监督学习中已得到充分确立，但将其应用于 PO 却面临独特的挑战。标准的 DP 定义假设数据集是固定的，其中隐私单元是单条数据记录。而在 PO 中，特别是采用同策略（on-policy）学习时，数据集是动态的；动作是基于当前策略采样的，这意味着改变单个数据点可能会改变未来所有样本的整个轨迹。因此，现有的 DP 定义无法直接适用，且 PO 中由隐私约束引发的样本复杂度代价在理论上仍未被探索。

方法论

1. 为 PO 重新定义差分隐私

作者首先形式化了专为 PO 定制的 DP 定义。借鉴私有在线多臂老虎机（bandit）文献，他们将数据集定义为一组 $N$ 个独特的“用户”（例如患者或提示词），而非一组固定的独立同分布（i.i.d.）样本。每个用户与智能体交互以生成轨迹 $(x, y, r)$。

• 隐私单元：单个“用户”。
• 定义：如果改变数据集中的一个用户不会显著改变最终输出策略的分布，则该算法为 $(\epsilon, \delta)$-DP。
• 区别：这与标准监督学习中的 DP 不同，因为“相邻”关系是由用户的初始状态及其交互历史定义的，而非静态记录。

2. 统一的元算法

为了在统一框架下分析各种 PO 算法，作者提出了一个元算法（算法 1）。这是一个批处理、单次遍历的算法，其中：

• 在每次迭代 $t$ 中，学习器从 $m$ 个不同的用户处收集一批新的 $m$ 个样本。
• 调用 PrivUpdate 预言机，基于当前批次和隐私约束计算下一个策略 $\theta_{t+1}$。
• 隐私保证：通过利用 DP 的并行组合性质，如果 PrivUpdate 预言机满足标准 DP（定义 1），则整个元算法满足所提出的 PO-DP 定义（定义 2）。

3. 具体实例化

该框架针对三种广泛使用的 PO 算法进行了实例化：

• DP-PG（策略梯度）：使用 REINFORCE 风格的梯度估计器，并在梯度更新中添加高斯噪声（算法 2）。
• DP-NPG（自然策略梯度）：将 PO 更新简化为一个私有回归问题（最小化优势函数与线性近似之间的平方损失）。它利用私有最小二乘预言机（算法 3）。
• DP-REBEL：与 DP-NPG 类似，它将 PO 简化为一系列关于相对奖励差的私有回归问题，利用 REBEL 公式。

主要贡献与结果

1. 样本复杂度界限

本文推导了差分隐私 PO 算法的第一组样本复杂度界限。采样的轨迹总数为 $N = m \times T$（批量大小 $\times$ 迭代次数）。

• DP-PG（一阶平稳点）：
  在 Lipschitz 平滑假设下，该算法实现的期望梯度范数平方为：
  $$\mathbb{E}[\|\nabla J(\theta_U)\|^2] \leq O_\delta\left( \frac{1}{\sqrt{N}} + \left(\frac{\sqrt{d}}{N\epsilon}\right)^{2/3} \right)$$
  此处，第一项代表非隐私收敛率，而第二项代表隐私代价。

• DP-PG（全局最优）：
  在额外假设（Fisher 信息非退化及兼容函数近似）下，平均遗憾是有界的。实现次优性间隙 $\alpha$ 所需的样本复杂度为：
  $$N \geq O_\delta\left( \frac{1}{\alpha^4 \gamma^4} + \frac{\sqrt{d}}{\alpha^3 \gamma^3 \epsilon} \right)$$
  其中 $\gamma$ 是 Fisher 信息下界。隐私代价表现为低阶加性项。

• DP-NPG 和 DP-REBEL：
  通过将 PO 简化为私有回归，作者利用了私有随机优化和私有线性回归的现有结果。

  • 对于低维度的对数线性策略，样本复杂度约为 $O_\delta(d/\alpha^4 + d/(\alpha^3 \epsilon))$。
  • 对于高维度，界限取决于所使用的具体私有回归预言机（例如指数机制或 ISSP），通常表明隐私代价随维度及 $1/\epsilon$ 缩放。

2. 结构洞察

• 隐私代价作为低阶项：一个核心发现是，隐私代价通常表现为整体样本复杂度中的低阶项。对于常数 $\epsilon$ 和维度 $d$，隐私开销并不主导收敛率。
• 问题结构的作用：本文强调，底层问题的结构属性（例如 Fisher 信息非退化、表格 softmax 结构）可以显著提高统计效率和计算效率，有时甚至能消除对 $\gamma$ 等有问题的参数的依赖。

3. 实证验证

作者在 CartPole-v1 环境中进行了概念验证实验。

• 设置：在隐私预算 $\epsilon=5$ 和 $\epsilon=3$ 下，将标准 PG/NPG 与 DP-PG 和 DP-NPG 进行了比较。
• 发现：
  • DP-NPG 始终优于 DP-PG，证明了即使在隐私约束下，曲率感知更新的优势。
  • $\epsilon=5$ 的 DP-NPG 实现了接近最优的性能（$\sim 478$ 奖励对比非隐私的 $492$），与理论预测一致。
  • 正如预期，随着隐私预算 $\epsilon$ 的降低，性能有所下降。

意义与主张

本文声称开启了差分隐私策略优化的理论研究，特别关注样本复杂度。其主要贡献包括：

1. 形式化定义：建立了一个严格的 PO 的 DP 定义，考虑了同策略动态并将“用户”作为隐私单元。
2. 统一框架：提供了一个元算法，使得在隐私约束下能够系统性地分析 PG、NPG 和 REBEL。
3. 隐私代价量化：证明了 PO 中的隐私代价通常表现为低阶项，表明在不产生过高样本复杂度惩罚的情况下，理论上可行地实现隐私保护 PO。
4. 实践指导：提供了关于结构属性（如 Fisher 信息非退化）如何缓解隐私代价的见解，指导未来隐私保护 RL 算法的设计。

作者指出，虽然其主要关注点是理论，但结果恢复了经典的非隐私界限，并为私有 PO 提供了首个严格的样本复杂度分析。他们承认局限性，例如侧重于单次遍历采样以及缺乏大规模真实世界数据集的评估，但强调其方法在 RLHF 和医疗决策等隐私敏感领域的广泛适用性。