Parameter-Free Heavy-Tailed Bandits

技术摘要：无参数重尾多臂老虎机

问题陈述

本文研究了在重尾回报分布下的随机多臂老虎机 (MAB) 问题。在这种设定下，回报 $X$ 满足有限矩条件 $\mathbb{E}[|X|^{1+\epsilon}] \leq u$，其中尾部指数 $\epsilon \in (0, 1]$ 且矩界限 $u < +\infty$。虽然鲁棒估计量在已知 $\epsilon$ 和 $u$ 的情况下可以实现最优遗憾率，但现实世界的应用（如金融、广告）通常缺乏对这些参数的可靠估计。

核心问题是由 Genalti 和 Metelli (COLT 2025) 提出的一个开放性问题，即对于在关于 $u$ 和 $\epsilon$ 的假设上无假设 (assumption-free) 的算法，其最佳可能的遗憾保证是多少。具体而言，本文研究了：

1. 当 $u$ 未知时，无分布限制 (distribution-free) 与依赖于分布 (distribution-dependent) 遗憾之间的基本权衡。
2. 当 $\epsilon$ 也未知时所带来的额外代价。
3. 是否存在一种单一算法，能够在所有 $\epsilon \in (0, 1]$ 上一致地实现次线性遗憾。

方法论

作者采用了两步分析法：

1. $u$-适应性 (固定 $\epsilon$)： 他们首先分析了 $\epsilon$ 已知但 $u$ 未知的场景。他们定义了两种遗憾率：

   • $\Phi_{free}(K, T)$：一个无矩限制的无分布限制遗憾界限。
   • $\Phi_{dep}(K, T)$：一个间隙和归一化 (gap-sum-normalized) 的依赖于分布的遗憾界限。
     通过结合改变测度论证与特定的实例构建，他们推导出了这两个速率乘积的下界，从而建立了一个可实现的性能“前沿 (frontier)”。

2. 算法设计 (AdaR-ETC)： 为了匹配推导出的下界，作者提出了 AdaR-ETC (Adaptive Robust ETC)。这是一种采用以下技术的“先探索后提交 (Explore-Then-Commit)”策略：

   • 中位数之均值 (MoM) 估计器： 用于在不需要了解 $u$ 或 $\epsilon$ 的情况下鲁棒地估计臂均值。
   • 调度探索 (Scheduled Exploration)： 探索预算 $L_T$ 通过参数 $\alpha$（控制对时界 $T$ 的依赖）和 $q$（控制对臂数 $K$ 的依赖）进行调节。在 $u$-适应性设置（即 $\epsilon$ 已知）中，这些参数是基于 $\epsilon$ 显式设置的。然而，通过将探索计划校准为有限方差端点 $\epsilon = 1$，该算法可以实现完全的无参数化 (parameter-free)（即对 $u$ 和 $\epsilon$ 均不知情）。

3. $(\epsilon, u)$-适应性 (未知 $\epsilon$)： 作者将分析扩展到 $\epsilon$ 亦未知的案例。他们将 AdaR-ETC 算法校准至有限方差端点 $\epsilon = 1$（设置 $q=1/3$ 且 $\alpha=2/3$），以创建一个单一的、无参数的策略。随后，他们证明了一个成对下界，以表明这种校准在保持 $\epsilon=1$ 时具有最优保证的策略中，能产生最优的剖面 (profile)。

核心贡献与结果

1. 未知 $u$ 时的权衡前沿
论文证明，对于任何对 $u$ 无知的策略，在分布限制与依赖于分布的保证之间存在尖锐的权衡。具体而言，对于固定的 $\epsilon$：
$$\Phi_{dep}(K, T) \cdot \Phi_{free}(K, T)^{\frac{1+\epsilon}{\epsilon}} = \Omega\left(T^{\frac{1+\epsilon}{\epsilon}}\right)$$
这意味着，改善最坏情况（无分布限制）的速率必然会导致依赖于分布的速率恶化。作者刻画了 “K-前沿” 和 “T-前前沿”，表明没有任何单一算法能同时优化两者。

2. AdaR-ETC 算法
提出的 AdaR-ETC 算法实现的遗憾界限在对数因子范围内匹配了理论前沿。通过调节参数 $\alpha$ 和 $q$，该算法可以选取权衡前沿上的任何运行点。

• 无分布限制界限： $\tilde{O}\left(u^{\frac{1}{1+\epsilon}} K^{\frac{\epsilon}{1+\epsilon}(1-q)} T^{\alpha}\right)$
• 依赖于分布的界限： $\tilde{O}\left(K^{q-1} T^{\beta_\alpha}\right)$
  其中 $\beta_\alpha = (1-\alpha)(1+\epsilon)/\epsilon$。
  “平衡”点（对 $K$ 和 $T$ 的依赖相等）产生的速率为 $\tilde{O}\left(u^{\frac{1}{1+\epsilon}} K^{\frac{\epsilon}{1+2\epsilon}} T^{\frac{1+\epsilon}{1+2\epsilon}}\right)$。对于有限方差情况 ($\epsilon=1$)，这导致了 $\tilde{O}(T^{2/3})$ 的速率，这严格劣于在已知 $u$ 时可达到的 $\tilde{O}(\sqrt{T})$ 速率，从而量化了“适应性的代价”。

3. 同时进行 $(\epsilon, u)$ 适应的极限
当 $\epsilon$ 亦未知时，作者建议将 AdaR-ETC 校准至 $\epsilon=1$。

• 逐点次线性 (Pointwise Sublinearity)： 对于任何固定的 $\epsilon > 0$，校准后的算法实现了次线性遗憾。
• 一致性的不可能 (Impossibility of Uniformity)： 论文证明，没有任何单一策略能保证在所有 $\epsilon \in (0, 1]$ 上一致地实现次线性遗憾。随着 $\epsilon \to 0$， $T$ 的指数趋近于 1，意味着遗憾变为线性。
• 校准的最优性： 在所有保持 $\epsilon=1$ 时具有最优 $\tilde{O}(K^{1/3}T^{2/3})$ 保证的策略中，$\epsilon=1$ 校准后的 AdaR-ETC 被证明对于所有其他 $\epsilon$ 都是前沿最优的。

意义与主张

本文声称解决了关于无假设重尾多臂老虎机的 COLT 2025 开放性问题。其主要意义在于：

• 刻画统计代价： 它对适应未知重尾的统计代价进行了尖锐的刻画，证明了适应未知尺度 ($u$) 和阶数 ($\epsilon$) 会引入基本的权衡，而不仅仅是常数因子的变化。
• 前沿 vs. 先知 (Frontier vs. Oracle)： 它确立了不存在对所有矩阶数都最优的“先知曲线”；相反，适应性是由一个前沿来描述的。
• 算法解决方案： 它提供了一种简单的、无参数的算法 (AdaR-ETC)，可以在不需要预先了解分布尾部属性的情况下，实现这些最优权衡。

作者明确指出，他们的结果在没有额外结构性假设的情况下无法恢复先知速率，这证实了“适应性的代价”是重尾设定中固有的。他们识别了一致次线性遗憾的极限，并建议未来的工作应专注于设计该算法的随时可用 (anytime) 版本，以及确定恢复先知速率所需的最弱附加假设。