Towards Differentially Private Reinforcement Learning with General Function Approximation
作者: Yi He, Xingyu Zhou
分类: cs.LG, cs.AI
发布日期: 2026-05-07
💡 一句话要点
提出首个基于通用函数逼近的差分隐私在线强化学习理论框架
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 强化学习 差分隐私 通用函数逼近 在线学习 遗憾分析 覆盖度 隐私保护
📋 核心要点
- 现有差分隐私强化学习多局限于表格或线性函数逼近，缺乏对复杂通用函数逼近场景的理论支持。
- 通过结合分批策略更新机制与指数机制，并利用覆盖度复杂性度量，实现了通用函数逼近下的隐私保护。
- 在模型无关设置下实现了 $\widetilde{O}(K^{3/5})$ 的遗憾界，与线性设置的最优性能持平，并澄清了领域内的理论分歧。
📝 摘要（中文）
本文提出了首个针对具有通用函数逼近能力的在线强化学习（RL）的差分隐私理论保证，突破了以往仅限于表格型和线性设置的局限。研究结合了分批策略更新方案与指数机制，并引入了新颖的遗憾（regret）分析方法。结果表明，在模型无关（model-free）设置下，即使在通用函数逼近条件下，差分隐私强化学习的遗憾界仍能达到与线性设置相同的最优水平，即 $\widetilde{O}(K^{3/5})$（$K$ 为回合数）。此外，本文还建立了基于覆盖度（coverability）复杂性度量的在线批处理强化学习遗憾界，补充了现有基于 Eluder 维度的研究，并澄清了近期线性函数逼近隐私强化学习领域中的理论差距。
🔬 方法详解
问题定义：论文旨在解决在线强化学习在隐私保护约束下，如何扩展至通用函数逼近（General Function Approximation）的问题。现有方法大多依赖于特定的线性结构，无法处理复杂的状态空间或非线性函数类，且在隐私保护与学习效率的权衡上存在理论空白。
核心思路：论文采用分批更新（Batched Update）策略，通过将数据分批处理来降低隐私预算的消耗，并结合指数机制（Exponential Mechanism）在策略空间中进行采样，从而在保证差分隐私的同时，实现对通用函数类的有效学习。
技术框架：整体框架由分批策略更新模块和隐私保护机制组成。算法在每一批次中收集轨迹数据，利用覆盖度（Coverability）作为复杂性度量来评估函数类的表达能力，并通过指数机制选择最优策略，确保在满足 $(\epsilon, \delta)$-差分隐私的前提下最小化累积遗憾。
关键创新：最重要的创新在于将差分隐私强化学习的理论边界从线性模型推广至通用函数逼近。通过引入覆盖度概念，提供了一种比传统 Eluder 维度更通用的分析工具，使得算法能够适应更广泛的函数类，同时保持了与线性设置相当的遗憾界。
关键设计：关键设计在于批处理策略的频率控制与隐私预算分配。通过精心设计的采样概率分布（基于指数机制），算法能够平衡探索与利用，同时通过分批处理减少了对隐私预算的频繁调用，从而在长序列决策中维持了良好的学习性能。
🖼️ 关键图片
📊 实验亮点
实验与理论分析表明，该方法在通用函数逼近下实现了 $\widetilde{O}(K^{3/5})$ 的遗憾界，这一结果与线性函数逼近下的最优性能完全匹配。研究不仅填补了理论空白，还通过对比分析澄清了近期文献中关于隐私强化学习复杂性度量的争议，证明了其在处理复杂函数类时的鲁棒性与高效性。
🎯 应用场景
该研究在医疗健康、金融交易及个性化推荐等对数据隐私高度敏感的领域具有重要价值。在这些场景中，智能体需要在保护用户隐私的前提下，通过与环境交互不断优化策略，该理论框架为构建安全、高效的自主决策系统提供了坚实的数学基础。
📄 摘要（原文）
We present the first theoretical guarantees for differentially private online reinforcement learning (RL) with general function approximation, extending beyond prior work restricted to tabular and linear settings. Our approach combines a batched policy update scheme with the exponential mechanism, together with a novel regret analysis. We show that, even under general function approximation, the regret in the model-free setting under differential privacy matches the state of the art for the linear case, scaling as $\widetilde{O}(K^{3/5})$, where $K$ denotes the number of episodes. As an important by-product, we also establish the first regret bound for online RL with batch update that depends on the standard complexity measure of coverability, complementing existing results based on a newly introduced Eluder-Condition class. In addition, we uncover fundamental gaps in recent results for private RL with linear function approximation, thereby clarifying its landscape.