Faster Rates for Private Adversarial Bandits¶

会议: ICML 2025
arXiv: 2505.21790
代码: 无
领域: AI安全
关键词: 差分隐私, 对抗性bandits, 专家建议bandits, 在线学习, Laplace机制

一句话总结¶

为差分隐私对抗性 bandits 问题提出简洁高效的非私有→私有转换框架，通过批量化损失+Laplace 噪声实现 O(√(KT/ε)) 的后悔界，首次证明中心 DP 和本地 DP 在该问题上存在分离，并给出首个私有 bandits with expert advice 算法。

研究背景与动机¶

对抗性 bandit 问题中，学习者在 T 轮中面对对手选择的损失函数，每轮选择一个动作并仅观察所选动作的损失，目标是最小化后悔值（与最优固定动作的累积损失差距）。

隐私需求：医疗试验中发布最佳治疗方案但不泄露患者信息、在线广告中推荐广告但不暴露用户偏好等场景需要 DP 保证。

已有工作的局限： - Agarwal & Singh (2017) 和 Tossou & Dimitrakakis (2017)：后悔界 O(√(KT·log(KT))/ε) - 这些算法满足更强的本地 DP，当 ε < 1/√T 时后悔变为线性（vacuous） - 之前不知道中心 DP 是否能做得更好，也不知道亚线性后悔需要多大的 ε

核心问题： 1. 中心 DP 和本地 DP 在对抗性 bandits 中是否存在可达性分离？ 2. ε 可以多小仍能获得亚线性后悔？

方法详解¶

整体框架¶

通用转换定理（Theorem 1）：将任意非私有 bandit 算法 B 转换为 ε-DP 算法 A_τ。

核心思路极其简洁： 1. 将 T 轮分成 T/τ 个大小为 τ 的批次 2. 每个批次中，重复使用 B 给出的同一动作 3. 批次结束时，计算批次内损失的平均值 4. 对平均损失加 Laplace(1/(ετ)) 噪声 5. 将加噪后的损失传给 B

后悔保证：R_{A_τ}(T,K) ≤ τ · R̃_B(T/τ, K, 1/(ετ)) + τ

其中 R̃_B 是 B 在有 Laplace 噪声损失上的后悔。关键在于批量化将噪声量级降低了 τ 倍。

关键设计¶

1. 处理负值损失的能力

加 Laplace 噪声后损失可以为负且无界。因此需要底层算法 B 能处理重尾/负值损失。本文利用了已有的重尾 bandit 算法 HTINF (Huang et al., 2022)，它使用修改的 FTRL 并能处理二阶矩有限的损失。

2. FTRL 转换（Corollary 2）

取 B = HTINF（α=2, σ=√6），τ = ⌈1/ε⌉，得到： - ε-DP 后悔界：O(√(KT)/√ε + 1/ε) - 对所有 ε ∈ [1/T, 1] 有效 - 当 ε > 1/T 即可亚线性！

3. Bandits with Expert Advice

三种方案覆盖不同参数区间：

方案	后悔界	最优区间
Corollary 8 (FTRL→expert)	O(√(NT)/√ε)	N ≤ K
Theorem 9 (Private EXP4)	O(√(KT·log N)·log(KT)/ε)	N ≥ K, ε ≥ K/N
Theorem 10 (Batched EXP4)	O(N^{1/6}K^{1/2}T^{2/3}/ε^{1/3} + N^{1/2}/ε)	N ≥ K, ε ≤ 1/√T

4. Private Batched EXP4（Algorithm 2）

专门为高维专家+高隐私需求设计： - 批量化专家权重更新 - 对 IPS 估计的专家损失加 Laplace 噪声（量级与 √N 相关） - 批内所有轮使用相同的专家权重分布 - 每批结束后用加噪损失更新权重

损失函数 / 训练策略¶

标准设定：损失函数 ℓ_t: [K] → [0,1]，对手选择后学习者仅观察所选动作损失
oblivious 对手：损失序列在游戏开始前确定（算法效用保证），但隐私保证对 adaptive 对手也成立
噪声机制：Laplace 机制，灵敏度为 1/τ（批量化平均损失的最大变化量）

实验关键数据¶

主实验¶

本文为纯理论工作，无实验。核心结果是理论上界的改进：

问题	已有最优	本文结果	改进
对抗性 Bandits	√(KT·log(KT))/ε	√(KT)/√ε	对所有 ε ≤ 1
Experts (N ≤ K)	N/A	√(NT)/√ε	首个结果
Experts (N ≥ K, 低隐私)	N/A	√(KT·log N)·log(KT)/ε	首个结果
Experts (N ≥ K, 高隐私)	N/A	N^{1/6}K^{1/2}T^{2/3}/ε^{1/3}	首个结果

消融实验¶

理论分析不同 ε 区间的行为： - ε > 1/√T 时：本文和先前工作都亚线性，但本文更优 - 1/T < ε < 1/√T 时：只有本文亚线性，先前工作线性 - ε < 1/T 时：两者都线性

关键发现¶

中心 DP vs 本地 DP 分离：中心 DP 在 ε = o(1/√T) 时仍可亚线性，本地 DP 不行
Oblivious vs Adaptive 对手分离：对 adaptive 对手，ε = o(1/√T) 时必须线性后悔
EXP3 难以私有化：IPS 估计器的概率 P_t 泄露信息，per-round 隐私损失随 T 增长
批量化 EXP3 的后悔下界：Lemma 11 证明满足特定条件的算法必须有 Ω(√(T/ε)) 后悔

亮点与洞察¶

极简转换的威力：整个方法就是"批量化+加 Laplace 噪声"，但理论效果深刻。批量化自然降低灵敏度，而连接重尾 bandit 算法是关键 insight
处理负损失=处理隐私噪声：这个等价关系是全新发现——重尾 bandit 文献和 DP 文献之间此前无交叉
三种 expert advice 算法互补：不同参数区间（N vs K, ε 大小）有不同最优算法，覆盖了完整的参数空间
下界分析的精妙：Lemma 11 的"两实例"构造——在损失结构变化时，DP 算法需要 1/ε 次探索才能"察觉"，优雅地解释了速率中 √ε 的来源
首次建立 bandit 设定下中心/本地 DP 的分离

局限与展望¶

仅限 oblivious 对手：效用保证不适用于 adaptive 对手，后者需要不同的 DP 定义和分析
无加法分离：未实现 O(√(KT) + poly(K)/ε) 形式的后悔界，即 T 和 ε 的加法分离
Bandits with experts 在 ε ≤ 1/√T 且 N ≥ T 时 vacuous：表明这一参数区间仍需新技术
缺少下界：对抗性 bandits 在中心 DP 下的最优后悔率仍是开放问题
纯理论：无实验验证，实际应用中批量化可能导致延迟和适应性损失

评分¶

新颖性: ⭐⭐⭐⭐⭐ — 极简方法+深刻理论洞察，首次分离结果
实验充分度: ⭐⭐ — 纯理论无实验
写作质量: ⭐⭐⭐⭐⭐ — 条理清晰，结果形式优美
价值: ⭐⭐⭐⭐⭐ — 在私有在线学习理论中具有重要意义