强化学习中的精确遗忘

# 强化学习中的精确遗忘

## 摘要
我们提出了强化学习中的*精确遗忘*问题，其目标是设计一个高效框架，使得在收到用户数据删除请求后，能够移除该用户的数据，即在线学习者遗忘后的输出与假设该被删除用户从未与学习者交互时产生的输出是*不可区分的*。对于任意 ρ>0，我们证明存在一种强化学习（RL）算法，该算法是 ρ-TV-稳定的，并且支持一种精确遗忘过程，其期望计算成本仅为从头重新训练的计算成本的 ρ√lnT 分之一。我们为表格型马尔可夫决策过程（MDP）构建了这样一种 ρ-TV-稳定的 RL 算法，其遗憾界为 O(H²√(SAT) + H³S²A + H^{2.5}S²A/ρ)，其中 S、A、H 和 T 分别表示状态数、动作数、回合长度和回合数。我们还为 ρ-TV-稳定的 RL 算法建立了 Ω(H√(SAT) + SAH/ρ) 的下界，表明我们的算法几乎是极小化最优的。机器学习，ICML

## 1 引言

机器遗忘是一个相对较新的研究领域，旨在响应数据修改或删除请求时，高效地移除特定数据对机器学习（ML）模型的影响（Cao and Yang, 2015; Bourtoule et al., 2021）。这一需求源于日益增长的隐私关切和法律要求，即某些用户数据及其对模型的影响必须被完全移除。此类关切源于机器学习模型容易受到诸如成员推断（Shokri et al., 2017）和模型反转（Fredrikson et al., 2015）等攻击，这些攻击可能泄露敏感的训练数据。此外，各种数据保护法律已经确立了用户的*被遗忘权*，包括欧盟的《通用数据保护条例》（GDPR, 2018）、加利福尼亚消费者隐私法案（CCPA）（Bonta, 2022）、日本的《个人信息保护法》（APPI）（JDPO, 2019）以及加拿大拟议的《消费者隐私保护法案》（CPPA）（CPPA, 2023）。除了法规合规性，机器遗忘还提供了实际好处：可用于移除联邦系统中的中毒客户端或受损节点（Jin et al., 2023）、从模型中删除受版权保护或专有内容（Eldan and Russinovich, 2023）、加速留一法验证、支持用户数据市场，以及识别模型中的高价值数据点（Ginart et al., 2019, p. 2）。机器遗忘要求模型遗忘后的输出与假设该请求用户数据从未包含在训练过程中时产生的输出*不可区分*。虽然在此上下文中没有普遍接受的不可区分性定义，但主要出现了两种经过认证的遗忘概念：精确遗忘（Ullah et al., 2021; Ullah and Arora, 2023）和近似遗忘（Guo et al., 2019; Neel et al., 2021; Sekhari et al., 2021; Allouah et al., 2024; Van Waerebeke et al., 2025）。

#### 为什么要在强化学习中精确遗忘？
近似遗忘要求不那么严格，通常能够实现更高效的算法并改善空间复杂度。然而，它不能保证完全移除用户的影响，这在实践中可能存在问题，特别是因为难以确定一个合适的近似参数来确保充分的隐私保护。因此，训练大规模模型的组织可能更倾向于精确遗忘，接受训练期间内存使用增加的成本，以避免隐私泄露可能带来的灾难性后果，尤其是当单个个体能够证明其个人数据仍然嵌入在已部署模型中时。这对于持续记录每个用户回合的交互式系统（推荐、个人助理、医疗分诊）尤其相关。删除请求的产生出于隐私（被遗忘权、成员推断风险）、安全（移除中毒/异常交互）、合规（每个用户的可审计性）和工程（快速留一用户诊断）原因。我们的框架允许操作员在遗憾最优的学习器上附加强大的删除保证，同时保持重新训练稀有且局部化，即使是在支持许多现实世界管道（例如，带上下文分桶的赌博机）的表格设置中也很有价值。

迄今为止，大多数机器遗忘工作集中在监督和无监督学习设置上，其中数据点是静态且独立处理的。然而，许多现实世界的系统，如推荐平台、数字助手和个性化医疗工具，本质上是交互式的，并依赖强化学习（RL）来模拟顺序用户交互。在这些系统中，数据并非来自孤立的输入，而是来自与用户的时间扩展体验。RL 是顺序决策制定的基本范式，其中智能体通过试错在未知环境中学习最大化累积奖励。随着其在个性化服务（从在线推荐到虚拟助手和社交机器人）中的广泛应用，RL 算法越来越多地与用户流交互，并根据其行为持续调整。这自然引发了机器遗忘核心的相同隐私问题：*当被要求时，我们如何从 RL 系统中移除特定用户交互历史的影响？* 我们的动机源于个性化、交互式系统，例如语音助手、推荐平台、医疗数据轨迹或个性化导师，其中基于回合的 RL 交互对应于可识别的用户。以下是一个受到 Shani et al. (2005) 工作启发的具体例子。

###### 例 1.1. 推荐系统（例如，亚马逊等电子商务平台上的产品推荐）通常被建模为 MDP，其中 RL 智能体作为推荐者。系统依次与不同用户交互，每个用户对应一个回合 t。一个动作是一个物品推荐，用户在回合 t 和步骤 h 的状态可以由其最近选择的 k 个物品表示，即 s_h = (a_{h-k}, ..., a_{h-1})，因为最近的历史对预测最为相关。给定推荐 a，用户可能接受它，从 s_h = (a_{h-k}, ..., a_{h-1}) 转移到 s_{h+1} = (a_{h-k+1}, ..., a_{h-1}, a)，或者选择未推荐的物品 a'，转移到 s_{h+1} = (a_{h-k+1}, ..., a_{h-1}, a')。奖励反映了向用户销售物品的效用，而回合 t 的*采样*奖励和转移捕捉了与该系统交互的用户特征。在时间 t 与推荐者交互的用户可能随后因隐私或其他原因要求移除其交互数据。关键的是，仅删除原始数据是不够的，我们必须移除其对已训练系统的影响。

尽管这个问题具有相关性和紧迫性，但 RL 中的遗忘问题在很大程度上仍未得到解决。在这项工作中，我们旨在通过制定和解决 RL 中的精确遗忘问题来弥合这一差距（见 2.1 节）。我们的目标是设计样本高效的 RL 算法，能够在请求时高效移除任何用户的数据，同时确保所得模型的行为与未使用该数据训练的模型不可区分。我们的主要结果如下：

1. 我们制定了强化学习中的精确遗忘问题。为此，我们将 RL 抽象为一类具有前缀和结构的通用顺序学习问题，并基于总变差（TV）稳定性的最新概念（Ullah et al., 2021; Ullah and Arora, 2023）开发了一个统一的（遗忘）学习框架（见第3节）。
2. 我们证明，对于任意 ρ>0，存在一种针对表格型马尔可夫决策过程（MDP）的高效 RL 算法，该算法是 ρ-TV-稳定的（见定义2.2），并实现了遗憾界 Õ(H²√(SAT) + H³S²A + H^{2.5}S²A/ρ)，其中 S、A、H、T 分别表示状态数、动作数、回合长度和回合数（见第4节）。该算法支持一种高效的精确遗忘过程，其期望计算成本仅为从头重新训练成本的 ρ√lnT 分之一（见第3节）。
3. 我们推导出用于 ρ-TV-稳定 RL 算法类的极小化下界 Ω(H√(SAT) + HSA/ρ)，表明我们的上界几乎是紧的（见第4.1节）。

#### 技术概述。
我们的工作建立在 Ullah 和 Arora (2023) 的基础上，他们证明在基于耦合的自然学习框架中，TV-稳定性对于批量监督学习的精确遗忘既是充分的也是必要的。将这一理论扩展到顺序 RL 是高度非平凡的，因为它需要 (a) 建立 TV-稳定的 RL 算法，以及 (b) 证明这些算法同时实现接近最优的遗憾。我们以非平凡的方式扩展了 UCB-VI (Azar et al., 2017)，以实现精确遗忘。我们的 RL 算法是第一个既具有 ρ-TV-稳定性又支持精确遗忘的遗憾最优变体。这需要 (i) 用二叉树、噪声扰动的前缀和替换访问统计量，同时保持乐观性，(ii) 以与耦合兼容的方式存储中间充分统计量，以便遗忘可以通过最大耦合重用随机性，(iii) 扩展遗憾证明以控制来自相关高斯噪声的额外方差，匹配 UCB-VI 直至对数因子。我们还为 TV-稳定算法的遗憾建立了第一个极小化下界。因此，我们的贡献在于将这些基础思想整合并扩展到 RL 设置中，提供明确的算法和严格的理论分析，填补了文献中的重大空白。

#### 相关工作。
在更广泛的领域中，不同学习任务中出现了一些重要发展。虽然我们不打算详尽无遗，但我们强调几个关键贡献。机器遗忘这个术语最早由 Cao 和 Yang (2015) 提出，他们提出了在训练模型中进行数据删除的确定性概念。他们的工作集中在具有限制性结构假设的统计查询问题上。Ginart 等人 (2019) 通过差分隐私开创了对近似遗忘的研究，重点关注 k-均值问题。Guo 等人 (2019) 将该工作扩展到线性和逻辑回归，而 Neel 等人 (2021) 将其扩展到一般凸模型。与我们工作最相关的是 Ullah 等人 (2021) 以及 Ullah 和 Arora (2023) 的工作。这些工作将批量设置中的精确遗忘概念形式化，特别是与自适应查询发布机制的联系。相比之下，我们在顺序学习的背景下研究精确遗忘，特别是在强化学习和遗憾最小化中。虽然我们的设置不同，但我们采用了他们的精确遗忘概念，并建立在类似的算法原语上，最显著的是使用前缀和来支持在线框架中的高效遗忘。

在 RL 的背景下，关于遗忘的先前工作极其有限。据我们所知，唯一相关的努力是由 Ye 等人 (2023) 进行的，他们引入了强化遗忘的概念。然而，在他们的设置中，多个不同的 MDP 被同时训练（例如，针对不同的任务或领域），遗忘涉及移除整个 MDP，而不是单个 MDP 内单个用户的回合。相比之下，我们考虑一个更细粒度和更实际的目标：在单个用户交互层面进行遗忘。此外，虽然 Ye 等人 (2023) 经验性地研究了近似遗忘，但他们没有提供理论保证或分析其对遗憾的影响。我们的工作不同之处在于，我们为精确遗忘提供了有限样本遗憾界，以及一个匹配的下界。

最后，我们的工作与不断增长的差分隐私强化学习文献有关（Vietri et al., 2020; Zhou, 2022; Chowdhury and Zhou, 2022; Qiao and Wang, 2023）。虽然差分隐私与近似遗忘有概念上的相似之处（实际上，一些技术有重叠），但其保证是根本不同的。差分隐私要求无论训练集中是否包含单个数据点，模型输出在统计上都是相似的。相比之下，精确遗忘要求所得模型与未使用被删除数据训练的模型是同分布的。因此，差分隐私和近似遗忘的结果不能直接推导出精确遗忘的保证。尽管如此，差分隐私文献中开发的技术，如二叉树机制，在我们的框架中起着至关重要的作用。

在准备本文时，我们了解到 Hu 等人 (2025) 的独立平行工作，该工作研究了在线凸优化设置中的遗忘。虽然这两项工作都涉及在线学习中的遗忘，但有两个关键区别。首先，我们的工作侧重于*精确*遗忘，而 Hu 等人 (2025) 开发了用于*近似*遗忘的方法。