Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

技术摘要：面向解耦多臂老虎机的扰动后跟随领导者算法

问题设定
本文解决了解耦多臂老虎机（MAB）问题，该设定下学习者在每一轮 $t$ 选择两个不同的臂：一个臂 $i_t$ 用于利用（承担损失 $\ell_{t, i_t}$ 但不观察它），另一个臂 $j_t$ 用于探索（观察损失 $\ell_{t, j_t}$ 但不承担它）。该框架建模了诸如超宽带通信系统（探测与传输信道不同的信道）和机器人领域的从模拟到现实的迁移等场景。目标是最小化伪 regret，定义为学习者利用选择所承担的累积损失与事后最佳固定臂的累积损失之差。

本文旨在实现**双世界最优（BOBW）**保证，即达成：

1. 在对抗性环境（损失由自适应对手决定）中实现 $O(\sqrt{KT})$ 的最优 regret。
2. 在随机约束对抗性（SCA）环境（包含标准随机设定）中实现 $O(K/\Delta_{\min})$ 的近最优、与时间无关的 regret，其中 $\Delta_{\min}$ 为最小次优间隙。

方法论
作者提出了一种基于**扰动后跟随领导者（FTPL）**框架的新策略，专门设计用于克服现有 BOBW 策略在解耦设定下的计算瓶颈。

• 利用策略：学习者通过最小化受扰动的累积损失估计来选择利用臂 $i_t$：
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  其中 $\hat{L}_{t,i}$ 是估计的累积损失，$\eta_t$ 是学习率，$r_{t,i}$ 是从形状参数 $\alpha > 1$ 的帕累托分布 $P_\alpha$ 中采样的独立同分布随机扰动。这种扰动类型对应于 $\beta$-Tsallis-INF 策略（其中 $\alpha = 1/(1-\beta)$），已知其能实现 BOBW 保证。

• 探索策略（关键创新）：在标准 FTPL 老虎机算法中，构建无偏的重要性加权（IW）损失估计器通常需要知道选择臂 $i$ 的精确概率 $w_{t,i}$。在解耦老虎机中，探索概率 $p_{t,i}$ 必须基于 $w_{t,i}$ 设定。然而，FTPL 不像 FTRL 那样提供 $w_{t,i}$ 的闭式表达式，且通过几何重采样估计完整向量的计算成本高昂（$O(K^2)$ 或更高）。
  为解决此问题，作者引入了一个代理概率 $q_{t,i}$，该概率可直接从当前损失估计计算得出，无需重采样或凸优化：
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  其中 $\sigma_{t,i}$ 是 $\hat{L}_{t,i}$ 在所有臂中的排名。随后，探索臂 $j_t$ 根据归一化分布 $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$ 进行选择。这种方法避免了对显式 $w_{t,i}$ 值的需求，同时保持了实现 BOBW 保证所需的理论性质。

主要贡献

1. 首个面向解耦老虎机的基于 FTPL 的 BOBW 策略：本文提出了首个在解耦老虎机中实现 BOBW 保证的策略，无需解决 FTRL 类方法（如 Decoupled-Tsallis-INF）所需的凸优化问题，也无需采用通常用于 FTPL 概率估计的重采样过程。
2. 计算效率：通过将完整概率向量计算替换为高效可计算的代理 $q_{t,i}$，所提出的策略降低了每步计算复杂度。虽然对损失估计进行排序需要 $O(K \log K)$，但作者指出，通过增量跟踪排名变化，优化后的实现可实现 $O(K)$ 的更新。这与 FTRL 策略形成对比，后者需要在每一步进行迭代凸优化（例如牛顿法）。
3. 理论保证：
   • 对抗性环境：该策略实现了 $O(\sqrt{KT})$ 的 regret 上界，与解耦老虎机的已知下界相匹配。
   • 随机/SCA 环境：该策略实现了 $O(K/\Delta_{\min})$ 的 regret 上界（对于 $\alpha=3$，具体为 $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$），这是近最优的，并改进了标准随机老虎机的时间相关上界。

结果

• 理论方面：本文提供了严格的证明（通过将 regret 分解为稳定性和惩罚项），表明代理概率 $q_{t,i}$ 与真实的利用概率足够接近，从而维持了必要的 regret 上界。
• 实证方面：在合成数据（对抗性和随机环境）以及使用 MovieLens 100K 数据集的真实世界模拟中的实验表明，所提出的 FTPL 策略：
  • 与现有的 BOBW 策略（Decoupled-Tsallis-INF/FTRL 和 EXP3）相比，实现了更低的累积 regret。
  • 展现了卓越的计算效率。在对抗性环境中，所提出的策略运行速度显著快于基于 FTRL 的基线。对于 $K=64$，观察到 FTRL 与 FTPL 的运行时间比率约为 1363 倍（即 FTRL 慢 1363 倍）。
  • 随臂数 $K$ 有效扩展，并在不同的间隙大小 $\Delta$ 下保持鲁棒性。

意义与主张
本文声称其主要贡献在于弥合了基于 FTRL 的 BOBW 策略的理论最优性与解耦老虎机背景下 FTPL 的计算效率之间的差距。通过消除对凸优化和重采样的需求，所提出的方法使 FTPL 能够在不牺牲 regret 性能的情况下充分发挥其效率优势。作者建议，使用高效可计算的代理概率替代精确概率向量的技术可能适用于 FTPL 之外的其他算法框架（如 Prod 族），从而可能在更广泛的老虎机设定中实现计算效率的提升。该工作的动机源于通信系统和机器人领域的实际应用，其中每步计算延迟至关重要。