Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?

技术摘要：1/2-Tsallis-INF 是否也适用于最佳臂识别？

问题设定
本文研究了在随机多臂老虎机（MAB）框架下，1/2-Tsallis-INF 算法在最佳臂识别（Best-Arm Identification, BAI）任务中的能力。虽然 1/2-Tsallis-INF 是一个经典的“最佳情况与最坏情况兼顾”（Best-of-Both-Worlds, BOBW）算法，已知在随机环境中能实现对数级伪遗憾（pseudo-regret），并在无需预知环境类型的情况下在对抗性环境中实现极小极大最优（minimax-optimal）遗憾，但其在 BAI 任务中的表现仍有待探索。

具体目标是分析失败概率，记作 $Err_t = P(i^*_t \neq i^*)$，其中 $i^*_t$ 是由算法累积的重要性加权损失估计值确定的经验最佳臂，$i^*$ 是真实的优化臂。本研究重点在于：在不添加显式的强制探索机制（否则会破坏其 BOBW 特性）的情况下，该算法能否利用其标准的的重要性加权估计量可靠地识别出最优臂。

方法论挑战
主要的底层技术障碍是用于跟随正则化领先算法（Follow-The-Regularized-Leader, FTRL）的重要性加权（Importance-Weighted, IW）估计量所固有的高方差。

• 在标准的 UCB 类算法中，BAI 分析依赖于经验均值的集中不等式。
• 在 1/2-Tsallis-INF 中，次优臂的采样概率约为 $O(1/t)$ 以实现对数级遗憾。因此，在单轮中，次优臂的 IW 估计量的方差为 $O(t)$。
• 这导致累积估计量的波动规模与其均值与最优臂之间的差距处于同一线性量级。由于噪声强度与信号间隙相当，标准的集中性论证失效了。
• 先前的研究通过添加显式探索来绕过此方差问题，但这会破坏 BOBW 的保证。本文使用未经修改的算法来解决这一问题。

方法论：李雅普诺夫函数分析
为了克服方差问题，作者构建了一个**李雅普诺夫函数（Lyapunov function）**来分析间隙过程 $D_t = \hat{L}_{t, i^*} - N_t$ 的随机动力学，其中 $N_t$ 是次优臂中最小的累积估计损失。

1. 玩具模型（Toy Models）： 推导过程由两个简化的玩具模型引导：
   • 一个近似间隙动力学的离散时间过程。
   • 一个通过 Itô 公式导出的连续时间扩散过程。
2. 函数构建： 这些模型揭示了一种特定的漂移-方差平衡，从而构建了一个分段李雅普诺夫函数 $g_t(y)$：
   • 当 $y < 0$（间隙为负）时：$g_t(y) = \Delta^2 t^q e^{\lambda y}$。
   • 当 $y \geq 0$（间隙为正）时：$g_t(y) = t^{-\theta}(y + \Delta t)^2$。
     这里，$\Delta$ 是次优性间隙，参数 $q, \theta, \lambda$ 被调节以确保 $g_t(D_t)$ 表现为一个超鞅（supermartingale）。
3. 核心洞察： 分析表明，多项式项中的指数 $m=2$ 至关重要。若 $m > 2$，由于 IW 估计量的重尾特性，将无法维持超鞅性质；而当 $m=2$ 时，在 $m \leq 2$ 的约束下，可以使收敛速率参数 $q$ 最大化。

主要贡献与结果
本文首次提供了针对不带额外探索的 FTRL 算法的定量 BAI 类保证。

• 上界（定理 3.1）： 对于学习率 $\eta_t = \alpha/\sqrt{t}$，失败概率呈多项式衰减：
  $$Err_t \leq C \cdot t^{-q}$$
  其中 $q < 2 - \frac{\alpha^2 \mu_{i^*}}{4}$（具体而言，$q \in (0, 2 - \frac{\alpha^2 \mu_{i^*}}{4})$）。随着学习率系数 $\alpha \to 0$，衰减速率趋近于 $t^{-2}$。
• 下界（定理 3.3）： 作者建立了一个匹配的下界，表明对于任何 $\epsilon > 0$，都有 $Err_t \geq C' t^{-2-\epsilon}$。这证明了该算法的指数 $2$ 基本上是紧致的。
• 技术新颖性： 该工作证明了尽管存在高方差的重要性加权估计量，但 1/2-Tsallis-INF 正则化器的特定结构仍允许可靠的 BAI。李雅普诺夫函数分析被强调为分析其他 BOBW 设置和 Tsallis 熵 FTRL 算法的潜在工具。

意义
本文声称，这是首次直接分析未经修改的重要性加权估计量在 BAI 背景下概率行为的研究结果。它解决了遗憾最小化与最佳臂识别之间在 BOBW 算法中的张力，表明 1/2-Tsallis-INF 可以在不牺牲其对对抗性环境鲁棒性的情况下，以多项式衰减的失败概率识别出最优臂。结果表明，遗憾与识别准确度之间的权衡受学习率系数 $\alpha$ 控制，其中较小的 $\alpha$ 会产生更快的识别速度，但可能带来更高的遗憾常数，这与已知的关于累积遗憾与简单遗憾关系的下界是一致的。