A Privacy Budgeting Framework for Online Experimentation¶

作者: Gilian R. Ponte, Alina Ferecatu
主题: 因果推断
相关性: 6/10
链接: https://arxiv.org/abs/2608.19944

一、领域脉络与小综述¶

这个方向是什么¶

本文研究的子方向是在线实验（多臂老虎机，MAB）中的隐私保护，具体而言，是如何在利用 MAB 进行个性化推荐（如网站设计、推荐系统）时，量化并控制第三方通过观察消费者收到的实验输出（如横幅、广告、推荐）来推断其潜在细分市场（segment）的隐私风险。该方向的核心统计/科学问题是：如何在保证实验学习性能（最小化后悔）的同时，满足一个预设的隐私保护水平（差分隐私参数）。当前成熟度属于应用导向的方法论构建阶段，已有理论框架（差分隐私与 MAB 的链接），但缺乏一个系统性的、可操作的、跨实验的隐私预算管理框架。

发展脉络（history）¶

作者在引言中通过引用构建了一条清晰的脉络：

奠基工作：差分隐私与 MAB 的独立发展。Dwork and Roth (2014) 提供了差分隐私的算法基础，定义了隐私损失参数 ξ。Sutton and Barto (2018) 的 ε-greedy 策略是 MAB 中经典的探索-利用启发式算法。这两条线在本文之前是分离的。
主要进展：将差分隐私引入 MAB。Mishra and Thakurta (2015) 和 Tossou and Dimitrakakis (2015) 首次将差分隐私应用于 MAB，但他们的做法是对奖励（reward）加噪，即保护“消费者点击了什么”这一信息。Ren et al. (2020) 使用随机响应机制保护奖励。作者指出，这些工作保护的是消费者与实验输出的交互（Channel 2），而非实验输出本身（Channel 1）。
当前 frontier：保护实验输出本身。Ponte et al. (2026) 使用差分隐私来控制一次性优惠券定向中的隐私风险，但作者指出，该工作是在数据收集后应用隐私保护，而非嵌入实验设计中。本文的定位是：在实验进行时，通过将差分隐私机制直接嵌入 ε-greedy 策略，来保护每次展示的实验输出。
本文的位置：作者将本文定位为第一个将差分隐私嵌入在线实验设计、并系统性地提出从访客级到企业级隐私预算框架的工作。它填补了“如何在实验过程中主动控制实验输出泄露的隐私风险”这一空白。

子线索聚类¶

这些被引文献大致落在三条子线索上：

差分隐私在 MAB 中的应用（保护奖励）：Mishra and Thakurta (2015), Tossou and Dimitrakakis (2015), Ren et al. (2020)。这一簇的工作关注的是保护消费者对实验的反应，通过向累积奖励或奖励统计量加噪来实现差分隐私。
差分隐私在营销/定向中的应用（保护输出）：Ponte et al. (2026), Ponte et al. (2024), Tian et al. (2026)。这一簇的工作关注的是保护消费者被展示的内容，但通常是在数据收集后或一次性场景中应用隐私保护。
在线实验与 MAB 在营销中的应用：Schwartz et al. (2017), Hauser et al. (2009, 2014), Liberali and Ferecatu (2022), Misra et al. (2019), Wang et al. (2025)。这一簇的工作关注的是如何用 MAB 优化营销决策，但不涉及隐私保护。

这个方向在追问的核心问题¶

Q1: 如何量化实验输出带来的隐私风险？ 即，如何用一个可计算的参数来界定第三方从观察到的输出中能学到多少关于消费者细分市场的信息？
Q2: 如何在给定的隐私预算下，最优地平衡探索与利用？ 即，更强的隐私保护（更小的 ξ）需要更多的随机化（更大的 ε），这会增加后悔。如何找到最优的 ξ（或 ε）来最小化后悔？
Q3: 如何将隐私预算从单个实验扩展到企业级的实验组合？ 即，当企业同时运行多个实验时，如何分配一个总体的隐私预算 Γ 到各个实验，以最大化整体学习性能？
主流方法与已知瓶颈：主流方法要么保护奖励（Channel 2），要么在事后应用隐私保护。瓶颈在于：缺乏一个在实验过程中、针对实验输出（Channel 1）的、可操作的隐私预算框架，并且该框架需要能处理跨实验的预算分配。

⚠️ 作者的 framing（必须明确标注成"这是作者的说法"）¶

作者把缺口 frame 成什么：作者将缺口 frame 为“现有工作要么保护了错误的隐私风险渠道（奖励而非输出），要么在错误的时间点应用隐私保护（事后而非实验过程中）”。因此，本文的贡献是“第一个在实验过程中、通过将差分隐私嵌入 ε-greedy 策略来保护实验输出，并系统性地提出三级隐私预算框架的工作”。
哪些竞争路线被他淡化或回避了：作者淡化了保护奖励（Channel 2） 的路线（Mishra and Thakurta 2015 等），仅在第 2.2.3 节中提及并指出“我们不同，我们在实验过程中干预”。作者也回避了更复杂的 MAB 算法（如 UCB、Thompson sampling）与差分隐私的结合，仅聚焦于 ε-greedy，因为其随机性天然适合与差分隐私链接。作者在脚注 3 中明确提到 Gittins index 是确定性的，因此不具隐私保护性，这实际上回避了“如何将差分隐私与更优的 MAB 算法结合”这一更困难的问题。
什么明显该被引 / 该存在、却没出现在 intro 里？ 作者没有引用任何关于局部差分隐私（Local Differential Privacy, LDP） 的文献。本文的机制（在访客端对臂进行随机化）本质上是一种 LDP 机制，但作者仅引用了 Dwork and Roth (2014) 的全局 DP 定义。引用 LDP 文献（如 Kasiviswanathan et al. 2011, Duchi et al. 2013）可以更精确地定位本文的贡献。此外，作者没有引用任何关于隐私与统计效率之间权衡的 minimax 理论的文献，例如 Duchi et al. (2013) 关于 LDP 下 minimax 估计率的工作。这可能是作者有意回避，因为本文的后悔界是 O(T^{2/3})，而 LDP 下的 minimax 后悔界可能不同。

张力¶

未见明显对立引用。所有被引工作都在各自的子线索内发展，没有出现彼此矛盾或在略不同条件下得相反结论的情况。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号：
- \( t \in \{1, \dots, T\} \)：访客索引，\( T \) 是实验总时长（总访客数）。
- \( S_t \in \mathcal{S} \)：访客 \( t \) 的细分市场（segment），\( \mathcal{S} \) 是有限集。这是潜在变量，第三方无法直接观测。
- \( \mathcal{A} = \{a_1, \dots, a_K\} \)：臂（arm）的集合，共 \( K \) 个，代表不同的实验输出（如不同的横幅、推荐）。
- \( A_t \in \mathcal{A} \)：访客 \( t \) 被展示的臂（实验输出）。这是可观测变量（第三方能看到）。
- \( R_t \in \{0, 1\} \)：访客 \( t \) 的奖励（是否点击）。这是可观测变量（第三方可能看到，但本文的隐私保护不覆盖它）。
- \( \mu_k(s) = \mathbb{P}(R_t = 1 \mid A_t = a_k, S_t = s) \)：臂 \( a_k \) 在细分市场 \( s \) 中的期望奖励（CTR）。这是未知参数，需要被学习。
- \( \varepsilon_t \)：在时刻 \( t \) 的探索概率。这是算法参数。
- \( \xi_t \)：在时刻 \( t \) 的访客级隐私风险参数。这是差分隐私参数，\( \xi_t \) 越小，隐私保护越强。
- \( \gamma \)：实验级隐私预算，满足 \( \gamma = \max_t \xi_t \)。这是企业设定的上界。
- \( \Gamma \)：企业级隐私预算，是跨实验的累积隐私风险上界。
模型：
- 数据生成机制：访客 \( t \) 到达，其细分市场 \( S_t \) 由外部过程决定（企业能观测到，第三方不能）。企业根据当前对每个臂在每个细分市场中的期望奖励的估计 \( Q_t(a_k, s) \)，使用 ε-greedy 策略选择展示的臂 \( A_t \)。访客 \( t \) 根据其细分市场 \( S_t \) 和展示的臂 \( A_t \)，以概率 \( \mu_{A_t}(S_t) \) 产生点击 \( R_t = 1 \)。
- 统计模型：奖励 \( R_t \) 服从伯努利分布，其均值 \( \mu_k(s) \) 是未知的、固定的参数。不同细分市场对同一臂的响应可以不同。
- 已知/未知：\( \mathcal{S}, \mathcal{A}, T, K \) 是已知的。\( \mu_k(s) \) 是未知的，需要被估计。\( S_t \) 对企业是已知的，对第三方是未知的。
可观测数据：
- 可观测：访客的细分市场 \( S_t \)（企业通过第一方数据获得）、展示的臂 \( A_t \)、点击结果 \( R_t \)。
- 潜在/不可观测：第三方无法直接观测到 \( S_t \)。第三方只能观测到 \( A_t \)（以及可能的 \( R_t \)），并试图从中推断 \( S_t \)。本文的隐私保护目标是限制第三方从 \( A_t \) 推断 \( S_t \) 的能力。

第二步：讲最小内核¶

最简特例：两臂（\( K=2 \)）、单细分市场（\( |\mathcal{S}|=1 \)）、恒定隐私预算（\( \xi_t = \gamma \)）

在这个最简特例下，我们去掉所有复杂性，只保留核心机制。

设定：只有两个臂 \( a_1, a_2 \)，所有访客都属于同一个细分市场。企业不知道哪个臂的 CTR 更高，需要通过实验来学习。
ε-greedy 策略：在时刻 \( t \)，企业以概率 \( 1 - \varepsilon \) 选择当前估计的“贪婪”臂（即历史点击率最高的臂），以概率 \( \varepsilon \) 随机选择一个臂（探索）。
差分隐私链接：作者的核心想法是，将 ε-greedy 策略中的“探索”步骤视为一个差分隐私机制。具体来说，如果贪婪臂是 \( a_1 \)，那么展示 \( a_1 \) 的概率是 \( 1 - \varepsilon + \varepsilon/2 \)，展示 \( a_2 \) 的概率是 \( \varepsilon/2 \)。反之亦然。这个机制是一个 \( K \)-ary 随机响应机制。
隐私参数 \( \xi \) 与探索概率 \( \varepsilon \) 的映射：为了满足 \( \xi \)-差分隐私，需要保证对于任何两个不同的贪婪臂 \( a \) 和 \( a' \)，展示同一个臂 \( a^* \) 的概率之比不超过 \( e^\xi \)。对于两臂情况，这要求：
\[\frac{\mathbb{P}(A_t = a_1 \mid \text{greedy} = a_1)}{\mathbb{P}(A_t = a_1 \mid \text{greedy} = a_2)} = \frac{1 - \varepsilon + \varepsilon/2}{\varepsilon/2} \le e^\xi\]
解这个不等式，可以得到 \( \varepsilon \) 与 \( \xi \) 的关系：
\[\varepsilon = \frac{2}{1 + e^\xi}\]
（注：原文公式 (12) 给出 \( \varepsilon = K / (K + e^\xi - 1) \)，当 \( K=2 \) 时，\( \varepsilon = 2 / (1 + e^\xi) \)，与上式一致。）
核心思路：这个映射是整篇论文的基石。它表明：
- 更强的隐私保护（更小的 \( \xi \)） 要求 更多的探索（更大的 \( \varepsilon \)）。当 \( \xi = 0 \) 时，\( \varepsilon = 1 \)，策略退化为完全随机。
- 更弱的隐私保护（更大的 \( \xi \)） 允许 更多的利用（更小的 \( \varepsilon \)）。当 \( \xi \to \infty \) 时，\( \varepsilon \to 0 \)，策略退化为纯贪婪。
要解决的问题：给定一个实验级隐私预算 \( \gamma \)，企业应该选择多大的 \( \xi \)（从而 \( \varepsilon \)）来最小化实验的后悔（regret）？这就是探索-利用与隐私保护之间的权衡。
结论（在这个特例下）：如果使用恒定策略（\( \xi_t = \gamma \) 对所有 \( t \)），那么后悔界是 \( O(T \varepsilon_\gamma + \sqrt{T \log T / \varepsilon_\gamma}) \)，其中 \( \varepsilon_\gamma = 2/(1+e^\gamma) \)。这个后悔界在 \( \gamma \) 很小时（强隐私）由线性项 \( T \varepsilon_\gamma \) 主导（因为探索太多），在 \( \gamma \) 很大时（弱隐私）由次线性项主导（因为探索太少，可能锁定次优臂）。存在一个最优的 \( \gamma \) 来平衡两者。

这个最小内核清晰地展示了本文的核心数学问题：如何通过一个简单的随机化机制（ε-greedy）来同时实现差分隐私和探索，并量化由此产生的后悔成本。

三、这篇论文做了什么¶

三句话：
1. 研究了什么问题：本文研究了在线多臂老虎机实验中，如何量化并控制第三方通过观察实验输出（如推荐、广告）来推断消费者细分市场的隐私风险。
2. 核心工具 / 方法：核心工具是将 ε-greedy 策略与差分隐私中的 \( K \)-ary 随机响应机制链接，从而将探索概率 \( \varepsilon \) 与隐私风险参数 \( \xi \) 建立一一映射。基于此，提出了两种隐私预算支出策略（恒定和动态），并推导了相应的后悔界和隐私弹性。
3. 主要结论：动态策略在长周期、复杂实验中优于恒定策略；通过后悔界推导出的隐私弹性可以指导管理者找到最小化后悔的最优隐私预算；将隐私预算视为稀缺资源进行企业级组合优化，能显著提升整体学习性能。
关键设定与假设（在第二节最小记号的基础上补全）：
- 分段特定学习：企业为每个细分市场 \( s \) 独立维护一个对每个臂 \( a_k \) 的期望奖励估计 \( Q_t(a_k, s) \)。这意味着不同细分市场的访客即使在同一时刻，其贪婪臂也可能不同。这是对标准 MAB 的推广，增加了学习的复杂性（后悔界中出现了 \( J^{1/3} \) 因子，\( J = |\mathcal{S}| \)）。
- 伯努利奖励：奖励 \( R_t \) 是二值的（点击/不点击），且条件独立于臂和细分市场。
- 平稳性：每个臂-细分市场对的期望奖励 \( \mu_k(s) \) 在实验期间是固定的。
- ε-greedy 策略：作者明确选择 ε-greedy 而非 UCB 或 Thompson sampling，因为其固有的随机性使其易于与差分隐私链接。这是一个关键的设计选择，也是一个限制。
- 并行组合（Parallel Composition）：作者假设每个访客的隐私机制是独立应用的（Web Appendix C），因此实验级隐私预算 \( \gamma \) 由最大的访客级隐私风险 \( \xi_t \) 决定。这是一个标准且合理的假设，使得隐私核算简单。
- 第三方只能观测到实验输出（Channel 1）：本文的隐私保证仅覆盖第三方通过观察实验输出 \( A_t \) 来更新信念。它不保护第三方通过观察点击 \( R_t \)（Channel 2）来推断，也不保护第三方通过其他渠道（如访客的公开社交媒体）获得的信息。这是一个明确的边界。
主要结果：
- 定理 1（恒定策略的后悔界）：公式 (15) 给出了恒定策略的期望累积后悔上界：\( \mathbb{E}[R_{\text{constant}}(T)] \le T \frac{K}{K+e^\gamma-1} + \sqrt{K+e^\gamma-1} \sqrt{T \log T} \)。这个界由两部分组成：线性探索成本和次线性估计误差成本。它揭示了恒定策略的刚性：无法根据学习进度调整探索概率。
- 定理 2（动态策略的后悔界）：公式 (18) 给出了动态策略的期望累积后悔上界。它由三部分组成：预算耗尽前的标准 ε-greedy 后悔（\( O(T^{2/3}) \)）、预算耗尽后的线性探索成本、以及预算耗尽后的次线性估计误差成本。这个界揭示了动态策略的优势：只要预算 \( \gamma \) 足够大，使得 \( t_\gamma \ge T \)（预算从未耗尽），后悔就能达到 \( O(T^{2/3}) \) 的最优率。
- 定理 3（隐私弹性）：作者推导了恒定策略（公式 (I.1)）和动态策略（公式 (I.2)）的隐私弹性。弹性为负表示增加隐私预算（降低隐私保护）能减少后悔；弹性为正表示增加预算反而增加后悔。对于恒定策略，弹性存在一个从负到正的零点，对应着后悔最小化的最优预算 \( \gamma^*_{\text{constant}} \)。对于动态策略，弹性始终非正，其零点对应着预算刚好够用的点 \( \gamma^*_{\text{dynamic}} \)。
证明路线与技术技巧：
- 整体路线：
  1. 链接 ε 和 ξ：通过匹配 ε-greedy 策略的随机化矩阵与 \( K \)-ary 随机响应机制，建立 \( \varepsilon = K / (K + e^\xi - 1) \) 的映射（公式 12）。
  2. 推导后悔界：使用标准 MAB 后悔分析框架（清洁事件 + 置信半径）。关键在于，将探索概率 \( \varepsilon_t \) 与隐私参数 \( \xi_t \) 绑定后，后悔界中的探索项和估计误差项都成为 \( \xi_t \) 的函数。
  3. 计算弹性：对后悔界关于 \( \gamma \) 求导，得到弹性表达式。对于动态策略，需要先隐式求解预算耗尽时间 \( t_\gamma \)（公式 71），然后使用链式法则求导。
- 关键跳跃点：
  - 从 ε-greedy 到差分隐私的映射：这是最关键的跳跃。作者没有发明新的隐私机制，而是识别出 ε-greedy 策略中的随机探索步骤本身就是一个满足差分隐私的随机响应机制。这个洞察使得后续所有分析成为可能。
  - 动态策略的后悔界推导：难点在于处理预算耗尽后的阶段。作者将后悔分解为“预算耗尽前”和“预算耗尽后”两部分，并分别用不同的方法上界。预算耗尽后的部分，探索概率是常数，因此其后悔结构与恒定策略类似。
- 技术技巧点名：
  - K-ary 随机响应机制：用于实现差分隐私的核心机制。
  - 并行组合（Parallel Composition）：用于将访客级隐私保证扩展到实验级。
  - 清洁事件（Clean Event）与置信半径：标准 MAB 后悔分析技术。
  - 积分比较（Integral Comparison）：用于将求和上界为积分，得到闭式后悔界。
  - 隐函数求导与链式法则：用于推导动态策略的弹性。
真实例子与应用：
- 应用 1：网站设计（§4.1）：
  - 数据：来自 Liberali and Ferecatu (2022) 的 MBA 网站 RCT 数据，有两个臂（抽象语言 vs. 具体语言），CTR 分别为 0.295 和 0.324。
  - 方法：模拟不同 \( T \)（1万、10万、100万访客）和不同 \( \gamma \)（0.05, 0.5, 1, 3, 5）下的恒定和动态策略，并与 ε-greedy、Gittins index、完美信息、随机策略对比。
  - 结果：动态策略在 \( \gamma \) 较大时性能接近非隐私的 ε-greedy，而恒定策略在中间 \( \gamma \) 处达到峰值后下降。动态策略的优势随 \( T \) 增大而更显著。
  - 说明：验证了理论后悔界：动态策略能更好地利用“早期探索、后期利用”的模式，而恒定策略的刚性导致其在 \( \gamma \) 过大时因探索不足而锁定次优臂。
- 应用 2：推荐系统（§4.2）：
  - 数据：来自 ZOZOTOWN 的 7 天 RCT 数据，有 80 个臂（时尚单品），CTR 范围 0.0012 到 0.0078。
  - 方法：模拟 \( K \in \{2, 4, 8\} \) 和 \( T \in \{10万, 100万\} \) 下的策略。
  - 结果：与网站设计应用一致。但恒定策略的非单调性在 \( K \) 较大时减弱，因为 \( K \) 本身增加了探索概率。
  - 说明：验证了理论在更复杂（多臂、低CTR）场景下的鲁棒性。
- 应用 3：企业级预算分配（§6.3）：
  - 数据：来自 ASOS 的 78 个在线 RCT 数据集（Liu et al. 2021），包含每个实验的臂数、访客数、CTR 等。
  - 方法：将 78 个实验视为一个组合，给定企业级预算 \( \Gamma \)，使用基于后悔界的边际学习增益 \( G_{e,s}(\gamma) \) 来优化预算分配，并与等分基准对比。
  - 结果：基于后悔界的分配在中等 \( \Gamma \) 下显著优于等分基准，能提升数万次点击。
  - 说明：展示了本文框架的实际应用价值：企业可以通过优化预算分配，在不增加总隐私风险的前提下提升实验性能。
🔎 结论是否比证明窄：
- 是。作者在正文中声称“动态策略在更长、更复杂的实验中价值更大”，这个结论在模拟中得到了验证，但证明中给出的后悔界是上界，而非精确值。模拟中动态策略的优势是经验性的，其理论保证是“在最坏情况下，动态策略的后悔不会比某个界更差”，而非“动态策略的后悔一定小于恒定策略”。作者在 §5.2 的末尾也承认，\( \gamma^*_{\text{constant}} \) 和 \( \gamma^*_{\text{dynamic}} \) 不能直接比较绝对后悔水平。
- 另一个窄化：作者在 §7.1 的局限性中承认，后悔界是最坏情况保证，独立于期望 CTR。这意味着，如果企业事先知道某些实验的 CTR 很高，那么基于最坏情况后悔的预算分配可能不是最优的。作者将此作为未来工作。

四、开放问题¶

臂特定隐私预算：作者在 Web Appendix J 中探讨了臂特定隐私预算，并证明这会增加最坏情况后悔。一个开放问题是：在什么条件下，臂特定隐私预算可以比均匀隐私预算获得更好的性能（例如，在贝叶斯平均后悔意义下）？ 这扎根于 Web Appendix J 的结论：“arm-level privacy heterogeneity increases the worst-case per-round regret bound”。
非参数奖励分布：本文假设奖励是伯努利分布。一个自然的推广是：当奖励分布是更一般的非参数分布时，如何将差分隐私嵌入 MAB 并推导后悔界？ 这扎根于本文 §3.1 的模型假设：“\( R_t \mid \{A_t = a_k, S_t = s\} \sim \text{Bernoulli}(\mu_k(s)) \)”。
自适应隐私预算：本文的动态策略是预先设定好的（公式 16）。一个更灵活的方案是：能否根据实验过程中观测到的数据，自适应地调整隐私预算 \( \xi_t \)，以在保证隐私的同时进一步降低后悔？ 这扎根于本文 §3.3.2 中动态策略的设定，以及 §7.1 中“conditioning the allocation rule on expected CTRs”的讨论。
更紧的后悔界：本文的后悔界是 \( O(T^{2/3}) \)。一个开放问题是：在差分隐私约束下，对于分段特定的 ε-greedy 策略，是否存在更紧的 minimax 后悔下界？ 或者，是否存在其他 MAB 算法（如 UCB、Thompson sampling）能在差分隐私约束下达到 \( O(\sqrt{T}) \) 的后悔界？ 这扎根于本文 §3.1.2 中引用的标准 ε-greedy 后悔界 \( O(T^{2/3}) \)，以及作者在脚注 3 中提到的 Gittins index 是确定性的、不具隐私保护性这一事实。

Maintained by 陈星宇 · Homepage · Source on GitHub