技术摘要：针对异方差广义线性强化的对抗性破坏下，一种兼具高效性与最优性的算法

1. 问题设定

本文研究了在存在**对抗性破坏（adversarial corruptions）情况下的异方差广义线性老虎夹（Heteroskedastic Generalized Linear Bandits, GLBs）**问题。该设定统一了顺序决策中三个具有挑战性的方面：

1. 广义线性模型 (GLMs)： 臂 $x_t \in \mathbb{R}^d$ 的期望回报遵循 GLM，$E[r_t|x_t; \theta^\star] = \mu(\langle x_t, \theta^\star \rangle)$，其中 $\mu$ 是已知的反向链接函数（inverse link function），$\theta^\star$ 是未知参数。该框架涵盖了逻辑回归（logistic）、泊松（Poisson）和高斯线性（Gaussian linear）老虎夹。
2. 异方差性 (Heteroskedasticity)： 回报的方差不是恒定的，而是随臂和时间步的变化而变化。具体而言，$\text{Var}[r_t|x_t, \tau_t; \theta^\star] = g(\tau_t) \dot{\mu}(\langle x_t, \theta^\star \rangle)$，其中 $g(\tau_t)$ 是一个可以外生随时间变化（例如在高斯老虎夹中）或由臂的选择内生决定（例如在逻辑回归或泊松老虎夹中）的离散参数（dispersion parameter）。
3. 对抗性破坏： 一个自适应的对手通过在每个步骤 $t$ 添加一个破坏项 $c_t$ 来操纵观测到的回报，使得学习者观察到 $\tilde{r}_t = r_t + c_t$。对手在总预算约束 $\sum_{t=1}^T |c_t| \le C$ 下运行。

目标是最小化累计伪遗憾（pseudo-regret），即 $T$ 轮内最优臂的期望回报与所选臂回报之间的差值。

2. 方法论：HCW-GLB-OMD

作者提出了 HCW-GLB-OMD（基于 Hessian 置信权重的 GLB-OMD），该算法旨在同时实现计算高效性和统计最优性。该算法集成了两个主要组件：

A. 在线镜下降 (Online Mirror Descent, OMD) 估计器

不同于以往依赖批量最大似然估计（MLE）的方法（这类方法会在局部权重与全局估计之间产生时间索引失配），HCW-GLB-OMD 使用了一种在线 OMD 估计器。参数更新在第 $t$ 步定义为：
$$\theta_{t+1} \leftarrow \arg \min_{\theta \in \Theta} \left[ \langle \nabla \tilde{\ell}_t(\theta_t), \theta - \theta_t \rangle + \frac{1}{2} \|\theta - \theta_t\|^2_{\nabla^2 \tilde{\ell}_t(\theta_t)} + \frac{1}{2\eta} \|\theta - \theta_t\|^2_{H_t} \right]$$
其中 $\tilde{\ell}_t$ 是加权负对数似然。这种在线方法确保了估计器、臂以及权重在同一个局部时间步上是对齐的，从而便于对破坏影响进行严谨的分析。

B. 基于 Hessian 的置信权重

为了实现对破坏的鲁棒性，算法根据链接函数的局部 Hessian（曲率）和离散参数为每个观测分配一个置信权重 $w_t$：
$$w_t = \min \left\{ 1, \frac{\alpha g(\tau_t)}{\|x_t\|_{H_t^{-1}}} \right\}$$
这里，$\|x_t\|_{H_t^{-1}}$ 量化了沿 $x_t$ 方向的不确定性。

• 机制： 如果一个臂的方向相对于离散参数而言具有高度不确定性（在逆 Hessian 中的范数较大），则权重 $w_t$ 会降低（$<1$）。这降低了那些容易受到对抗性操纵的方向上的观测值的权重。
• 曲率感知： 不同于使用设计矩阵的线性老虎夹方法，该方法使用 Hessian $\nabla^2 \tilde{\ell}_t$，它结合了局部斜率 $\dot{\mu}$。这使得算法能够适应 GLM 的特定几何特性（例如逻辑回归中的饱和现象）。

C. 破坏鲁棒的置信序列

作者构建了一个考虑了估计误差和对抗性破坏的置信集 $C_t(\delta)$。该集合的半径包含一个与破坏预算 $C$ 成正比 world 的加性项：
$$C_t(\delta) \equiv \{ \theta \in \Theta : \|\theta - \theta_t\|_{H_t} \le \beta_t(\delta) + 2\eta\alpha C \}$$
该序列的证明依赖于应用于加权似然比的超鞅（supermartingale）论证，并利用了映射 $x \mapsto x^{w_t}$ 的凹性来处理 $w_t < 1$ 的情况。

3. 核心贡献与结果

A. 遗憾上界

在假设链接函数 $\mu$ 是**自共轭（self-concordant）**的（假设 3）条件下，本文确立了 HCW-GLB-OMD 的遗憾上界。以至少 $1-\delta$ 的概率，遗憾被限制在：
$$\text{Reg}(T) \lesssim \log d \left( \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + d^2 g_{\max} \kappa + d(g_{\max} + \kappa)C \right)$$
其中：

• $\dot{\mu}_{t,\star} = \dot{\mu}(\langle x_{t,\star}, \theta^\star \rangle)$ 是最优臂处的链接函数斜率。
• $g_{\max} = \max_t g(\tau_t)$ 是最大离散度。
• $\kappa = (\min_{x,\theta} \dot{\mu}(\langle x, \theta \rangle))^{-1}$ 是曲率参数。
• $C$ 是总破坏预算。

该上界的意义：

• 实例级最优性 (Instance-Wise Optimality)： 前导项 $\sqrt{\sum g(\tau_t) \dot{\mu}_{t,\star}}$ 取决于最优臂的实际斜率，而非最坏情况下的曲率 $\kappa$。这与无破坏 GLB 的极小极大下界相匹配。
• 破坏鲁棒性： 破坏项随 $C$ 线性缩放（具体为 $d(g_{\max} + \kappa)C$），在曲率因子 $\kappa$ 意义下达到了极小极大最优。
• 统一性： 该界限同时恢复了异方差线性老虎夹、逻辑回归老虎夹和泊松老虎夹的最前沿结果。

B. 统一遗憾下界

作者证明了一个适用于任何具有对抗性破坏的自共轭异方差 GLB 的统一下界：
$$\Omega \left( d \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + dC \right)$$
该下界：

• 涵盖了现有的特定问题下的下界，如逻辑回归老虎夹、异方差线性老虎夹和受破坏的线性老虎夹。
• 证实了该算法的前导项在实例级上是极小极大最优的。
• 表明破坏项 $dC$是不可避免的，尽管目前的上界在破坏项中包含了一个额外的$\kappa$因子（即$d\kappa C$）。

C. 计算效率

本文的一个关键贡献是算法的效率。通过使用在线 OMD 更新和递归 Hessian 更新，HCW-GLB-OMD 在每次迭代中实现了 $O(1)$ 的空间和时间复杂度。这与以往针对 GLM 的破坏鲁棒算法（例如 CR-Eluder-UCB, GAdaOFUL）形成对比，后者由于采用批量处理或复杂的置信集构建，通常需要 $O(t)$ 的复杂度。

4. 重要性与主张

本文声称提供了第一个针对异方差 GLB 在对抗性破坏下兼具高效性与最优性的算法。其主要意义在于：

1. 弥合差距： 它解决了在受破坏的 GLB 中，计算效率与统计最优性之间的权衡问题。以往的工作要么以高计算成本实现最优性，要么以次优的遗憾界（通常随最坏情况曲率 $\kappa$ 缩放）来实现效率。
2. 实例级最优性： 该算法实现的遗憾界能够适应实例的具体难度（通过 $\dot{\mu}_{t,\star}$），而不是依赖于最坏情况假设，即使在存在破坏的情况下也是如此。
3. 统一框架： 它提供了一个单一的理论框架，覆盖了广泛的老虎夹问题（线性、逻辑回归、泊松、异方差），且无需针对特定问题进行算法修改。

作者指出仍存在一个差距：上界中的破坏项随 $d\kappa C$ 缩放，而下界为 $dC$。他们推测$\kappa$因子是分析过程中的产物，且$O(dC)$的界限是可实现的，但这仍是一个开放性问题。此外，目前的分析假设学习者已知离散参数$\tau_t$；处理未知的$\tau_t$ 被确定为一个未来的研究方向。