实现强化学习中数据删除的精准擦除，让系统表现如从未接触过该数据。
Exact Unlearning in Reinforcement Learning
- 设计可精确移除用户数据的强化学习框架，输出与从未交互时无差别。
- 计算成本仅为重训练的 ρ√(ln T) 倍，且在给定条件下接近最优。
- 适用于对数据隐私要求高的在线学习场景，如个性化推荐系统。
我们提出了强化学习中的精确删除问题，目标是设计高效框架，使学习器在收到删除请求后，能够完全移除任意用户的交互数据，使得删除后的输出与从未接收该用户数据时完全不可区分。对于任意 ρ > 0，我们证明存在一种 ρ-总变差稳定（ρ-TV-stable）的强化学习算法，其精确删除操作的期望计算成本仅为从头重训练的 ρ√(ln T) 倍。我们为表格型马尔可夫决策过程（MDPs）构造了这样的 ρ-TV 稳定算法，其遗憾界为 𝒪(H²√(SAT) + H³S²A + H²·⁵S²A/ρ)，其中 S、A、H、T 分别表示状态数、动作数、每轮时长和总轮数。我们还建立了 ρ-TV 稳定强化学习算法的下界 Ω(H√(SAT) + SAH/ρ)，表明我们的算法近乎极小极大最优。
原文摘要 · Abstract (English)
We formulate the problem of \emph{exact unlearning} in reinforcement learning, where the goal is to design an efficient framework that enables the removal of any user's data upon deletion request, i.e., the online learner's output after unlearning is \emph{indistinguishable} from what would have been produced had the deleted user never interacted with the learner. For any $ρ>0$, we show that there exists a reinforcement learning (RL) algorithm that is $ρ$-TV-stable and supports an exact unlearning procedure whose expected computational cost is only a $ρ\sqrt{\ln T}$ fraction of the computational cost of retraining from scratch. We construct such a $ρ$-TV-stable RL algorithm for tabular Markov decision processes (MDPs), which achieves a regret bound of $\mathcal{O}(H^2 \sqrt{SAT} + H^3 S^2 A + {H^{2.5} S^2 A}/ρ)$, where $S, A, H$, and $T$ denote the number of states, the number of actions, the episode horizon, and the number of episodes, respectively. We also establish a lower bound of $Ω(H\sqrt{\!SAT}\! +\! {SAH}/ρ)$ for $ρ$-TV-stable RL algorithms, showing that our algorithm is nearly minimax optimal.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。