Towards Differentially Private Reinforcement Learning with General Function Approximation¶

会议: NeurIPS 2026
arXiv: 2605.07049
领域: 强化学习
关键词: 强化学习, 联合差分隐私, 一般函数逼近, 覆盖性, 指数机制

一句话总结¶

论文提出了首个面向一般函数逼近的差分隐私在线强化学习理论框架，结合固定批次策略更新与指数机制，在覆盖性条件下证明了 $\widetilde{O}(K^{3/5})$ 的次线性遗憾界，匹配了线性 MDP 无模型设定的当前最优理论界。

研究背景与动机¶

强化学习通过在未知环境中持续交互与试错优化决策策略，已成为在线推荐、个性化医疗干预以及大语言模型（LLM）基于人类反馈强化学习（RLHF / 规则奖励对齐）的核心使能技术。然而，这种强个性化交互模式在带来性能跃升的同时引发了严重的隐私泄露风险：在医疗场景中，状态编码了患者生理参数与病史，奖励反馈着治疗敏感反应；在 LLM 交互中，用户的输入 Prompt、偏好反馈与对话轨迹高度关联个人隐私意图。现有研究证实非私有强化学习算法极易遭受成员推理等攻击。为了提供严谨的理论隐私屏障，近期学者引入了差分隐私（DP）及适应个性化交互的联合差分隐私（Joint Differential Privacy, JDP）。

然而，以往私有强化学习的理论保证几乎完全局限在表格型（Tabular）MDP 或线性函数逼近（如线性 MDP、线性混合 MDP）设定中。这些线性结构使得算法能够高度依赖低维充分统计量、显式置信集构造或基于行列式倍增的策略切换机制进行私有化。在面向复杂非线性值函数的一般函数逼近下，基于置信集（Version Space / Confidence Set）的乐观探索机制无法直接进行隐私扰动与敏感度控制；同时，每轮在线交互更新策略会导致极为严重的隐私损耗累积（Privacy Loss Composition），标准理论工具彻底失效。

为了打破线性假设的桎梏，本文旨在回答一个根本性理论问题：在一般函数逼近下，满足 JDP 的在线强化学习能否仍然实现次线性遗憾？核心 idea：将置信集约束探索转化为平衡价值与贝尔曼误差的无约束单目标优化，引入固定批次更新控制高级隐私组合步数，并借助指数机制实现策略的隐私采样，在覆盖性（Coverability）条件下首次确立了与线性无模型一致的 $\widetilde{O}(K^{3/5})$ 次线性遗憾界。

方法详解¶

整体框架¶

本文针对有限期马尔可夫决策过程 $M=(\mathcal{S},\mathcal{A},H,P,R,\rho)$，在一般值函数类 $\mathcal{F}=\mathcal{F}_1\times\dots\times\mathcal{F}_H$ 下设计了私有在线强化学习框架。该架构通过批次调度解耦高频轨迹交互与低频策略更新，把传统非私有方法中难以私有化的置信集交集投影，改造为基于经验数据集的分数函数打分与指数机制 Softmax 采样，再由执行智能体根据保护后的 $Q$ 函数执行贪婪策略，满足 Billboard 引理下的 JDP 约束。

算法在通用随机 MDP（算法 1）与面向 LLM 场景的确定性转移+结果奖励 MDP（算法 2）中均遵循统一的高层流水线：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境轨迹收集与历史数据集 𝒟 累积"] --> B["批次边界判定：k = i·B + 1"]
    B -->|非更新轮| C["策略复用与贪婪执行"]
    B -->|更新轮| D["无约束探索打分函数构造"]
    D --> E["指数机制私有策略采样"]
    E --> F["更新贪婪策略 π_k 并向用户下发动作"]
    F --> A

关键设计¶

1. 固定批次策略更新：控制多轮迭代的隐私损耗累积

在在线隐私强化学习中，直接在每轮 episode 结束时更新策略会导致单条用户轨迹参与 $K$ 次连续的私有发布，高级顺序组合（Advanced Sequential Composition）将引入极高的累积隐私噪声，摧毁次线性遗憾。为此，算法采用大小为 $B$ 的固定批次策略更新机制：将总共 $K$ 个 episode 划分为 $M = K/B$ 个批次，仅在批次起始点 $k = i\cdot B + 1$ 时利用截至当前收集的数据集 $\mathcal{D}_{[k]}$ 重新评估函数类，在批次内部的其余 episode 严格复用上一轮的策略 $f^{(k)} = f^{(k-1)}$。根据高级组合定理，总共仅需进行 $M$ 次 $(\varepsilon_0, 0)$-DP 机制调用，单步隐私预算配置为 $\varepsilon_0 = \frac{\varepsilon}{\sqrt{2(K/B)\log(1/\delta)}}$。通过在遗憾分析中精细权衡批次陈旧性代价 $H C_{\mathsf{cov}} B \log K$ 与隐私误差代价 $\frac{K}{\eta}\mathsf{Err}_{\mathsf{priv}}$，求解出最优批次大小 $B = \widetilde{O}(K^{3/5})$，成功压低了总隐私损耗。

2. 无约束探索目标：规避置信集投影以适配标准隐私机制

传统一般函数逼近（如 GOLF）依赖维护逐轮收缩的经验置信集（Version Space）以实现乐观探索（UCB），但高维非凸置信集本身的差分隐私化极难控制敏感度。本文借鉴无约束探索思想，将悲观惩罚与初始状态乐观项熔炼为单一标量打分函数 $S(f)$。在随机转移与逐步奖励下（算法 1），打分函数定义为： $$S(f) := \eta f_1(s_1) - L_{\mathcal{D}}^{\mathsf{BE}}(f)$$ 其中第一项为初始状态价值以驱动对高收益策略的探索，权重由超参数 $\eta > 0$ 调节；第二项 $L_{\mathcal{D}}^{\mathsf{BE}}(f)$ 为抵消双重采样偏差的解耦贝尔曼误差损失（Inherent Bellman Error Loss）： $$L_{\mathcal{D}}^{\mathsf{BE}}(f) := \sum_{h=1}^H \mathcal{E}_{\mathcal{D},h}(f_h, f_{h+1}) - \inf_{f' \in \mathcal{F}} \sum_{h=1}^H \mathcal{E}_{\mathcal{D},h}(f'_h, f_{h+1})$$ 其中 $\mathcal{E}_{\mathcal{D},h}(f_h, f_{h+1}) = \sum_{\tau \in \mathcal{D}} (f_h(s_h,a_h) - r_h - \max_{a'} f_{h+1}(s_{h+1}, a'))^2$。由于 $\eta f_1(s_1)$ 不依赖私有数据集 $\mathcal{D}$，单条轨迹更替对损失项的最大扰动不超过常数因子，从而严谨证明了该打分函数在任意相邻数据集下的 $L_1$ 敏感度满足 $\Delta_S \leq 8H$。

3. 指数机制私有选择与 Billboard 架构：达成严格 JDP 保证

针对上述标量评分函数，算法在更新轮次放弃非私有的 $\mathrm{argmax}_{f\in\mathcal{F}} S(f)$ 硬最大化，转而采用以温度参数 $\beta_{\varepsilon,\delta} = \frac{\varepsilon_0}{2\Delta_S}$ 调控的指数机制（Exponential Mechanism），实现 Softmax 形式的私有采样： $$\mathbb{P}(f) \propto \exp\left( \beta_{\varepsilon,\delta} \cdot S(f) \right)$$ 采样得到的 $f^{(k)}$ 充当公共“广告牌（Billboard）”。在 episode $k$ 中向当前用户推荐动作 $a_h^{(k)} = \mathrm{argmax}_{a} f_h^{(k)}(s_h^{(k)}, a)$ 时，由于其他用户 $j \neq k$ 的所有观测与后续动作仅通过经过 $(\varepsilon, \delta)$-DP 保护的序列 $\{f^{(k)}\}_{k=1}^K$ 进行交互，由 Billboard 引理直接推导出整个学习系统满足严苛的 $(\varepsilon,\delta)$-JDP。根据指数机制的极值效用界，采样解以高概率满足 $S(f^{(k)}) \geq \max_{f\in\mathcal{F}} S(f) - \mathsf{Err}_{\mathsf{priv}}$，其中私有化近似误差为 $\mathsf{Err}_{\mathsf{priv}} = O\left(\frac{1}{\beta_{\varepsilon,\delta}}\log\frac{|\mathcal{F}|K}{\alpha}\right)$。

4. 确定性 MDP 下的结果奖励机制：摆脱贝尔曼完备性约束

对于大语言模型生成等典型任务，环境状态转移通常为确定性过程（前缀拼接新 token），且仅在完整回答生成后返回单个标量结果奖励（Outcome Reward）$r = \sum_{h=1}^H R_h(s_h, a_h)$。在算法 2 中，作者充分利用确定性转移下贝尔曼方程处处成立而非仅均值成立的性质，将复杂的两层最小化贝尔曼误差简化为轨迹级贝尔曼残差损失（Bellman Residual Loss）： $$L_{\mathcal{D}}^{\mathsf{BR}}(f) := \sum_{(\tau,r) \in \mathcal{D}} \left( \sum_{h=1}^H [f_h(s_h,a_h) - f_{h+1}(s_{h+1})] - r \right)^2$$ 同时将打分函数中的初始项替换为关于先验已知分布 $\rho$ 的分布乐观值 $\bar{f}_1 := \mathbb{E}_{s_1 \sim \rho} \max_a f_1(s_1,a)$。该设计将损失函数的敏感度严格控制在 $\Delta_S = O(H^2)$，彻底免除了对复杂反向函数族贝尔曼完备性（Bellman Completeness）的苛刻假定，仅需最基础的可实现性假设（Realizability: $Q^\star \in \mathcal{F}$）即可保证算法收敛。

损失函数 / 训练策略¶

在算法更新步骤中，超参数 $\eta$ 和批次大小 $B$ 依据理论最优平衡进行显式设置： - 随机环境：设置批次大小 $B = \widetilde{O}\left( \frac{K^{3/5} \Delta_S^{2/5} \log^{2/5}(|\mathcal{F}|K/\alpha) \log^{1/5}(1/\delta)}{\varepsilon^{2/5} C_{\mathsf{cov}}^{2/5}} \right)$，同时调节平衡系数 $\eta = \Theta\left(\max\left\{\sqrt{\frac{K H \kappa}{C}}, \frac{K^{3/4} \Delta_S^{1/2} (\log|\mathcal{F}|)^{1/2}}{B^{1/4} \varepsilon^{1/2} C^{1/2}}\right\}\right)$。 - 确定性结果奖励环境：敏感度为 $\Delta_S = O(H^2)$，有效覆盖度替换为 $C'_{\mathsf{cov}} = \mathbb{E}_{s_1\sim\rho} C_{\mathsf{cov}}(\Pi_{\mathcal{F}}; M_{s_1}^\star)$，无需内层 $\inf$ 求解。若面对无限函数类 $\mathcal{F}$，可基于 $L_\infty$ 范数构建离线 $\beta$-覆盖集 $\mathcal{C}_\beta$，此时引入额外的 $\beta K$ 逼近误差，将 $|\mathcal{F}|$ 替代为覆盖数 $\mathcal{N}(\mathcal{F},\beta)$。

实验关键数据¶

主实验¶

论文重点在于奠定差分隐私强化学习的基础理论边界。在附录 D 中，作者设计了面向确定性结果奖励 MDP（$H=4$，$|\mathcal{A}|=2$，$6$ 维二进制上下文，非线性假设空间 $|\mathcal{F}|=243$）的受控概念验证仿真，对比了无私有化连续更新、无私有化批次更新、以及不同隐私预算下的收敛速度。实验采用高原轮次（Plateau Episode，即达到 95% 最终累积遗憾时的首个交互轮次，越小代表收敛进入平稳期越快）作为关键度量指标。

环境配置	无私有化无批次 (Baseline)	无私有化批次更新	私有化 $\varepsilon=8$ (算法 2)	私有化 $\varepsilon=5$ (算法 2)
简单环境 (Easy: 密集奖励)	13	24	37	127
困难环境 (Hard: 奇偶稀疏)	31	34	87	218

消融实验¶

为解析批次机制与隐私噪声对性能衰退的独立贡献，作者在简单与困难两类代表性任务下评估了各配置的收敛延迟放大比例（相对于无私有无批次基准）：

配置变体	简单环境 Plateau 延迟倍数	困难环境 Plateau 延迟倍数	机制作用说明
无私有化无批次 (Ideal)	1.00× (13 轮)	1.00× (31 轮)	每轮实时贪婪更新，无陈旧度与噪声
纯批次更新 (w/o Privacy Noise)	1.85× (24 轮)	1.10× (34 轮)	固定批次更新引入信息滞后，带来适度平缓延迟
私有批次更新 ($\varepsilon=8$, 弱噪声)	2.85× (37 轮)	2.81× (87 轮)	引入指数机制采样扰动，策略探索产生一定发散
私有批次更新 ($\varepsilon=5$, 强噪声)	9.77× (127 轮)	7.03× (218 轮)	强隐私预算下 Softmax 熵增极大，需要更多样本抑制次优分支

关键发现¶

隐私预算对收敛速度的非线性影响：无论在何种难度环境下，放宽隐私约束（$\varepsilon$ 从 5 增至 8）都会显著降低 Plateau 轮次（简单环境从 127 降至 37，困难环境从 218 降至 87），验证了理论界中遗憾界随 $\varepsilon^{-2/5}$ 减小的多项式权衡。
批次调度的开销可控性：无隐私约束下，引入批次更新仅使高原轮次从 13/31 增加至 24/34，延迟幅度远小于强隐私噪声的影响，说明批次更新是控制多轮隐私组合预算的高度实用范式。
环境稀疏度与探索难度的复合效应：在依赖奇偶校验的困难环境中，各算法的平稳期普遍后移，且强隐私噪声会在稀疏反馈下显著延长次优探索时间。

亮点与洞察¶

填补理论空白的首个一般函数逼近 DP-RL 框架：打破了以往私有强化学习只能处理表格型或线性 MDP 的严苛限制，使理论保证首次覆盖到了具有丰富非线性表征能力的函数类族。
覆盖性下批次在线学习的全新分析工具：技术上证明了引理 E.1，通过将访问批次划分为“好批次”与“坏批次”，建立了首个基于标准覆盖性（Coverability）常数的批次在线强化学习遗憾分解不等式，作为副产物在非私有批次 RL 领域优于基于复杂 Eluder-Condition 的先前工作。
揭示现有线性私有 RL 论文的关键理论缺陷：澄清了线性 MDP 领域近期的理论争议，指出文献 [38] 与 [45] 试图借助行列式倍增技巧（Rare Policy Switching）达成 $\widetilde{O}(\sqrt{K})$ 私有遗憾时，因高斯隐私噪声破坏了设计矩阵单调正定递增性所导致的理论证明漏洞，确立了无模型私有 RL 下 $\widetilde{O}(K^{3/5})$ 界限的基石地位。

局限与展望¶

计算复杂度瓶颈：算法需要在值函数空间上运行指数机制采样，对于大规模参数化网络（如深度神经网络），在连续函数空间上精确进行 Softmax 配分函数积分与采样计算极具挑战性，目前仍主要适配有限类或具有高效 MCMC 采样的紧致空间。
理论下界尚未闭环：尽管无模型私有 RL 的遗憾界与线性环境的最优模型持平在 $\widetilde{O}(K^{3/5})$，但是否存在某种精巧机制能突破至 $\widetilde{O}(\sqrt{K})$，或者 $\Omega(K^{3/5})$ 是否构成了无模型 JDP 强化学习的不可逾越下界，仍是悬而未决的公开问题。
依赖覆盖性假设：若马尔可夫决策过程的状态空间存在严重不可达分支且覆盖性常数 $C_{\mathsf{cov}}$ 极大，算法的遗憾界将显著劣化，未来需探索结合更弱探索测度（如 DEC 或弱可外推性）的私有扩展。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次打破线性函数逼近束缚，提出一般函数逼近下首个私有 RL 算法架构与全新证明技巧。
实验充分度: ⭐⭐⭐ 偏向纯理论突破工作，仅包含极简非线性 MDP 的受控概念验证仿真，缺乏高维复杂环境测试。
写作质量: ⭐⭐⭐⭐⭐ 逻辑缜密，算法动机清晰，从随机通用 MDP 到确定性 LLM 场景的过渡极其自然，附录证明完整详实。
价值: ⭐⭐⭐⭐⭐ 为大模型对齐与隐私序列决策奠定了基础理论支撑，同时纠正了顶会相关文献的理论硬伤。