技术摘要：依赖实例的随机 Lipschitz 多臂老虎机问题

问题设定

本文研究了随机 Lipschitz 多臂老虎机问题，其中学习者在有界域 $X \subset [0, 1]^d$ 上试图顺序最大化一个未知的 $L$-Lipschitz 函数 $f: X \to \mathbb{R}$。在每一轮 $t$，学习者选择一个动作 $x_t \in X$ 并观察到一个含噪奖励 $Y_t = f(x_t) + \eta_t$，其中 $\eta_t$ 是零均值、条件 1-次高斯噪声。目标是最小化期望累积遗憾 $R_T = \mathbb{E}[\sum_{t=1}^T (f^* - f(x_t))]$，其中 $f^* = \max_{x \in X} f(x)$。

尽管现有文献提供了最坏情况下的遗憾界，其缩放比例为 $\tilde{\Theta}(T^{\frac{d+1}{d+2}})$，以及基于缩放维度 $d_z$ 的自适应界，缩放比例为 $\tilde{\Theta}(T^{\frac{d_z+1}{d_z+2}})$，但作者认为这些界是不够的。基于缩放的保证仅依赖于近优水平集的渐近增长，未能捕捉特定实例 $(X, f)$ 更精细的结构属性，特别是最大化者集合 $X^*$ 的几何性质。

方法论

1. 算法框架：PACO

作者针对老虎机设定提出了**分阶段自适应覆盖优化（PACO）**算法。该算法在 $k=1, 2, \dots$ 阶段运行，其中分辨率 $r_k = 2^{-k}$ 随时间递减。

• 离散化：在每个阶段，PACO 使用离散化预言机构建一个有限点集 $S_k$，用半径为 $r_k/L$ 的 $\ell_\infty$-球覆盖当前的“活跃”区域 $A_k$。该预言机确保点之间充分分离，且集合大小受该区域覆盖数的限制。
• 连续消除：在每个阶段内，算法在 $S_k$ 上运行连续消除子程序（算法 2）。它通过拉取臂来估计其均值，并消除那些相对于当前幸存最佳臂在统计上次优的臂，同时根据该阶段的分辨率 $r_k$ 进行调整。
• 活跃区域更新：下一阶段的活跃区域更新为以幸存臂为中心的球的并集。

2. 理论分析：积分表征

核心理论贡献是从基于渐近维度的界转向非渐近、依赖实例的积分界。

• 打包数到积分的链接：作者推导了一个遗憾界，表示为水平集环带上的打包数之和。随后，他们利用对间隙函数 $\Delta(x) = f^* - f(x)$ 水平集的“剥皮”论证，将此离散和桥接为连续积分。
• 几何假设：为了建立积分形式，他们假设了一个温和的几何条件（假设 3/4）：对于任何近优点，以该点为中心的小球的一部分包含在 $X$ 内。这确保了水平集的体积表现可预测。
• 截断积分界：所得的遗憾界具有截断积分的形式：
  $$R_T \leq C R \log(T) \int_{X \setminus X^*} \frac{dx}{\max(\Delta(x), 2^{-k_T})^{d+1}}$$
  其中 $k_T$ 是视界 $T$ 处的阶段索引。该积分显式地依赖于 $f$ 的水平集几何性质，而不仅仅是一个渐近指数。

3. 扩展到 Lipschitz 专家

本文将这些结果扩展到全信息 Lipschitz 专家设定（算法 3：SOUS）。在此设定中，学习者在每一轮观察整个奖励函数 $f_t(\cdot)$。作者提出了一种算法，从具有“合理良好”估计的点集中均匀采样。他们推导了类似的依赖实例的积分界，并展示了 $X^*$ 的几何性质如何细化最坏情况下的速率。

4. 松弛条件

分析被扩展到单侧 Lipschitz函数（假设 6），其中 Lipschitz 条件仅对 $x \preceq y$ 成立。这需要修改离散化预言机以提供“前向覆盖”，并调整积分证明以使用后向盒子，但核心的积分表征仍然有效。

主要结果

1. 依赖实例的上界和下界

本文提供了匹配的遗憾上界和下界（对数因子范围内）。

• 上界：遗憾由定义域上逆间隙的积分界定。
• 下界：对于任何 $a_0$-一致算法（其中 $a_0 = \frac{d+1}{d+2}$），存在某些实例，其遗憾下界由类似的积分项界定。这证明了依赖实例的表征在本质上是最优的。

2. 细化的渐近速率

通过分析关于缩放维度 $d_z$ 和最大化者集合维度 $d^*$ 的积分界，作者推导出了改进的渐近速率。

• 主要推论：当最大化者集合 $X^*$ 的维度 $d^* > 0$ 时，遗憾缩放比例为：
  $$R_T \leq \tilde{O}\left( T^{\frac{d_z+1}{\max(d_z, d^*) + 2}} \right)$$
• 改进：当 $d^* > d_z$ 时，这严格优于经典的缩放界（$\tilde{O}(T^{\frac{d_z+1}{d_z+2}})$）。
• 几何关系：作者证明，在温和的连通性假设下，$d_z + 1 \geq d^*$，确保指数保持非负且界有效。

3. 全信息设定

对于 Lipschitz 专家设定，获得了类似的细化速率：
$$R_T \leq \tilde{O}\left( T^{\frac{1+d_z-\max(d_z, d^*)}{2}} \right)$$
这突显了即使在完全信息体制下，最大化者集合的几何性质也决定了遗憾的改进。

意义与主张

本文声称填补了文献中的空白，为 Lipschitz 老虎机提供了精确的、非渐近的、依赖实例的分析。

• 超越渐近性：与依赖渐近复杂度参数（如 $d_z$）的先前工作不同，本文通过水平集上亚优间隙的积分来表征遗憾。这捕捉了实例 $(X, f)$ 的具体几何性质，而不仅仅是其渐近增长。
• 缩放界的细化：这项工作表明，当最大化者集合“较大”（高 $d^*$）时，经典缩放界并不总是紧的。在这些体制下，新界严格优于现有速率。
• 紧性：提供匹配的下界证实，对于一致算法，推导出的积分表征在本质上是最优的。
• 通用性：该框架被证明可适应于较弱的正则性假设（单侧 Lipschitz）和全信息设定，表明连续臂优化具有稳健的理论基础。

作者指出，虽然他们的分析特定于 PACO 算法，但将这些依赖实例的界扩展到其他流行算法（如标准缩放算法或基于树的方法）仍然是未来工作的开放方向。