📊 statistics

Exact Unlearning in Reinforcement Learning

本文阐述了强化学习中精确遗忘的问题，并提出了一种针对表格型马尔可夫决策过程（MDP）的 $\rho$ -TV-稳定算法，该算法在实现接近极小极大最优遗憾的同时，能够以显著低于从头开始重新训练的计算成本实现高效的数据移除。

原作者： Thanh Nguyen-Tang, Raman Arora

发布于 2026-06-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Thanh Nguyen-Tang, Raman Arora

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

以下是对论文 "Exact Unlearning in Reinforcement Learning"（强化学习中的精确遗忘）的解释，采用了通俗易懂的语言和创意类比。

核心问题：“被遗忘权”与 AI

想象你有一个非常聪明的私人厨师（AI 智能体），他会随着时间的推移逐渐学习你的口味偏好。你每吃一顿饭，厨师就会记录下你喜欢什么、不喜欢什么，从而变得更擅长为你烹饪。

现在，假设你决定不再让这个厨师了解关于你的任何信息。你说：“删除我的数据。”

在大多数计算机系统中，“删除数据”是非常棘手的。这就像试图从一锅已经炖了好几个小时的汤中剔除某种特定的食材。你无法简单地把三天前加入的“盐”捞出来；那种味道已经融入了整锅汤中。如果你只是删除了你用餐的记录，厨师的记忆仍然会受到它的影响。这是一种隐私风险，因为黑客可能会根据厨师现在的行为来推测你曾经吃了什么。

这篇论文解决了针对一种特定类型的 AI——强化学习 (Reinforcement Learning, RL) 的这个问题。RL 被用于推荐引擎（如 Netflix、亚马逊）或虚拟助手等系统，在这些系统中，AI 通过与你的逐步交互来进行学习。

目标：“精确遗忘”

作者希望实现**“精确遗忘” (Exact Unlearning)**。

近似遗忘 (Approximate Unlearning) 就像是在说：“无论我是否加入了你的食材，这锅汤的味道基本是一样的。” 这很接近，但不完美。
精确遗忘 (Exact Unlearning) 则更为严格。这意味着在你被删除后，AI 的行为必须在统计学上等同于你从未存在过的行为。

挑战在于？每次有人要求被删除时，都重新训练 AI 会极其缓慢且昂贵。作者希望找到一种方法，能让你快速地“遗忘”，而无需从头开始。

解决方案：“二叉树”账本

作者提出了一种聪明的会计技巧来实现这一点。他们并没有仅仅保存一个运行总数（比如一个简单的累加和），而是将数据存储在一个二叉树 (Binary Tree) 中。

类比：账本图书馆
想象 AI 不仅仅持有一本笔记本，它持有一个嵌套账本组成的图书馆。

叶子节点 (The Leaves)： 每一次单独的交互（你的每一餐）都记录在树的最底层。
分支 (The Branches)： 在每个叶子节点之上，都有汇总一组交互的分支。
噪声 (The Noise)： 为了保护隐私并便于编辑，AI 在这些总和中加入了一点点随机的“静电”或噪声。

为什么这会有所帮助：
由于数据是以树状结构组织的，如果你想删除你的数据，AI 不需要重新计算整个历史记录。它只需要更新从你的叶子节点向上到树顶的那条特定路径。这就像是在电子表格中修改一个条目并让公式自动更新，而不是重写整本书。

“魔法”之源：耦合 (Coupling)

论文使用了数学概念——极大耦合 (Maximal Coupling)。你可以把它看作是一个“魔法橡皮擦”，试图尽可能多地复用旧数据。

当你要求被删除时：

AI 查看包含你的那个“带噪声”的总和。
它尝试看看是否可以保留同一个带噪声的数字，只是假装这个数字来自于一个“虚拟”用户而非你。
如果数学逻辑成立（通常都是成立的），AI 就会保留原有的数字。无需重新训练！
如果数学逻辑不成立（极少数情况），它才需要重新计算那一小部分。

论文证明了这种重新计算发生的频率非常低。你被“遗忘”的成本仅为重新训练整个 AI 成本的一个极小部分。

权衡：稳定性 vs. 技能

这里有一个代价。为了让这个“魔法橡皮擦”起作用，AI 必须是稳定 (Stable) 的。

类比：稳健的手
想象 AI 是一位画家。如果 AI 是“不稳定”的，改变一个微小的色点（你的数据）可能会导致整幅画发生剧烈变化。这使得很难干净利落地擦除你的痕迹。
如果 AI 是“稳定”的，改变一个点只会改变那个微小的区域。

作者表明，通过让 AI 变得稍微更稳定一些（通过前面提到的添加“噪声”），他们可以保证精确遗忘。然而，这种稳定性也会带来一个小小的代价：与一个完全不考虑遗忘功能的 AI 相比，该 AI 的学习速度可能会稍慢，或者在预测你的偏好时可能稍欠完美。

结果：近乎完美

论文提供了数学证明：

它有效： 该方法保证了精确遗忘。
它高效： 遗忘一个用户的计算成本非常低（与 episode 数量的平方根成比例，这是一个极小的数值）。
它是最优的： 该算法在性能损失（遗憾度/regret）方面几乎是任何想要支持精确遗忘的算法中所能达到的最佳水平。他们证明了一个“下界 (Lower Bound)”，这意味着在不破坏遗忘保证的前提下，没有任何其他方法能做得比这显著更好。

总结

简而言之，这篇论文为我们提供了一套配方，用于构建能够尊重“被遗忘权”的 AI 系统（如推荐系统或助手）。通过将数据组织在特定的树状结构中并加入一点受控的噪声，AI 可以瞬间“忘记”一个用户的影向力，而无需重启其整个学习过程，同时仍能高效地完成工作。

技术摘要：强化学习中的精确遗忘（Exact Unlearning）

1. 问题定义

本文研究了在强化学习（RL）背景下，特别是在表格型马尔可夫决策过程（MDP）中，**精确遗忘（exact unlearning）**的问题。与数据点静态的监督学习不同，RL 系统通过与用户进行序列化交互，生成状态、动作和奖励的轨迹。

核心目标是设计一个高效的框架，使得在用户提出删除请求时，系统能够移除该用户交互历史的影响。生成的模型必须在分布上与在剩余数据上训练的模型不可区分（即假设被删除的用户从未与系统交互过）。这被形式化为精确遗 forget（定义 2.1），它要求对于任何用户序列 $z_{1:T}$ 和被替换为虚拟用户 $z'$ 的被删除用户 $z_t$ ，遗忘算法 $U$ 满足：
$U(A(z_{1:T}), z_t, z') \stackrel{D}{=} A(z_1, \dots, z_{t-1}, z', z_{t+1}, \dots, z_T)$

本文将其与基于差分隐私（Differential Privacy）的近似遗忘进行了区分，认为精确遗忘对于高风险应用（如医疗保健、个性化助手）是必要的，因为即使是微小的残留影响也可能导致隐私泄露或安全违规。

2. 方法论

所提出的解决方案集成了三个主要组件：全变差（Total Variation, TV）稳定性、二叉树机制以及最大耦合（Maximal Coupling）。

2.1. TV-稳定性与遗忘框架

作者基于 $\rho$ -TV-稳定性（定义 2.2）的概念构建，即当单个数据点发生变化时，算法输出分布的变化在全变差距离内不超过 $\rho$ 。他们利用了这样一个理论结果： $\rho$ -TV-稳定性足以实现精确遗忘。

遗忘机制依赖于最大耦合。如果一个算法是 $\rho$ -TV-稳定的，那么在原始数据训练出的模型（分布 $P$ ）与替换用户后的数据训练出的模型（分布 $Q$ ）之间存在一种耦合，其不一致的概率恰好为 $\text{TV}(P, Q) \leq \rho$ 。这使得遗忘算法可以：

尝试复用现有的模型状态（从 $P$ 中采样）作为 $Q$ 的有效样本。
以概率 $1 - \text{TV}(P, Q)$ 接受复用（无需重新训练）。
以概率 $\text{TV}(P, Q)$ 拒绝并从头开始重新训练（或从特定检查点开始）。

2.2. 用于前缀和的二叉树机制

为了在在线设置中实现 TV-稳定性，作者借鉴了差分隐私中的二叉树机制（Dwork et al., 2010）。

结构： 算法不是存储原始的充分统计量（如访问计数、奖励），而是维护一棵完美的二叉树，每个节点存储一个带噪声的前缀和。
噪声注入： 在二进分解（dyadic decomposition）的节点中加入高斯噪声。前缀和 $u_t = \sum_{i=1}^t x_i$ 通过对 $O(\log T)$ 个带噪声的节点值求和来计算。
稳定性： 该结构确保了改变单个用户的数据 $x_t$ 只会影响树中的 $O(\log T)$ 个节点，从而限制了更新的敏感性，并实现了 $\rho$ -TV-稳定性保证。

2.3. 通过拒绝采样与反射实现的遗忘

遗忘算法（算法 3）遍历从被删除的叶节点到根节点的路径：

清洁更新（Clean Update）： 更新路径上每个节点的“清洁”值，以反映将 $x_t$ 替换为 $x'_t$ 的过程。
噪声值耦合（Noisy Value Coupling）： 对于“噪声”值，执行拒绝采样步骤。检查现有的噪声值 $\tilde{v}_b$ $\tilde{v}_{b}$ （在旧清洁均值 $v_b$ $v_{b}$ 下生成）是否可以被视为来自新分布 $N(v'_b, \sigma^2 I)$ $N (v_{b}^{'}, σ^{2} I)$ 的样本。
- 接受： 如果接受，则更新节点并向父节点移动。
- 拒绝： 如果拒绝，算法应用反射映射（一种最大耦合技术）生成一个新的有效噪声值，并触发从后序遍历中的下一个叶节点开始的重新训练过程。

2.4. RL 算法实例化（带噪声的 UCB-VI）

作者通过修改 UCB-VI 算法（Azar et al., 2017）将此框架应用于表格型 MDP：

环境 Oracle： 将轨迹统计量（状态-动作访问、转移、奖励）编码进前缀和结构中。
更新函数： 使用带噪声的前缀和来计算乐观的值估计。
奖励函数（Bonus Function）： 引入了一个特定的奖励项 $b(\tilde{n})$ ，它同时考虑了有限样本估计误差以及注入高斯噪声引入的近似误差。

3. 核心贡献与结果

3.1. 算法保证

精确遗忘： 提出的算法（算法 2 + 算法 3）实现了精确遗忘。
计算效率： 遗忘的预期计算成本仅为从头开始重新训练成本的 $\rho \sqrt{\ln T}$ 倍。只有当最大耦合失败时才会触发重新训练，而这种情况发生的概率很低。
遗憾界（Regret Bound）： 该算法实现的遗憾界为：
$R(T) = \tilde{O}\left(H^2\sqrt{SAT} + H^3S^2A + \frac{H^{2.5}S^2A}{\rho}\right)$
其中 $S$ $S$ 是状态数， $A$ $A$ 是动作数， $H$ $H$ 是步长， $T$ $T$ 是回合数。
- 前两项对应标准的 UCB-VI 行为（带有 $H^3S^2A$ 的热身成本）。
- 第三项代表了通过噪声稳定算法所付出的代价。

3.2. Minimax 下界

论文为任何 $\rho$ -TV-稳定 RL 算法建立了 Minimax 下界：
$R(T) = \Omega\left(H\sqrt{SAT} + \frac{HSA}{\rho}\right)$
这一结果表明，所提出的上界是近乎 Minimax 最优的，第二项的差距仅为 $H^{1.5}S$ 的因子。作者指出，通过更精细的分析（例如使用 Bernstein 型奖励而非 Hoeffding 型奖励）有可能缩小这一差距。

3.3. 与差分隐私的比较

论文强调，虽然差分隐私意味着 TV-稳定性，但反之则不然。因此，DP 的下界并不自动适用于 TV-稳定算法。作者证明，由于 TV-稳定性是比纯 DP 更弱的约束，其下界比以往基于 DP 的 RL 下界更为严格。

4. 重要性与主张

本文声称提供了第一个关于可证明精确遗忘的强化学习理论与算法框架。其意义在于：

弥补差距： 将精确遗忘理论从批量监督学习扩展到序列化、交互式的 RL 设置。
效率： 证明了精确遗忘可以通过显著低于全量重训的计算成本来实现，这使得大规模交互式系统（如推荐系统、语音助手）的应用成为可能。
最优性： 确立了所提出的遗憾与遗忘稳定性之间的权衡是近乎最优的。
基础性步骤： 刻画了一个自然的不可遗忘算法子类（具有 TV-稳定性的算法），并提供了结合了遗憾最优学习与可证明遗忘的端到端保证。

作者对局限性保持了谦逊的态度，承认：

目前的结果仅限于表格型 MDP；将该方法扩展到函数逼近（大规模/连续状态空间）仍是一个开放性挑战。
在遗憾分析中，上界与下界之间存在非平凡的差距。
由于二叉树结构的存在，该方法具有线性空间复杂度（ $O(T)$ ），且精确遗忘的最优空间-时间-效用权衡尚未得到充分理解。