Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

以下是论文《单策略可集中性下带前向 KL 正则化的离线上下文多臂老虎机快速速率》的详细技术总结。

问题陈述

本文探讨了在离线上下文多臂老虎机（Contextual Bandits, CBs）学习中，当学习目标涉及前向 Kullback-Leibler（Forward-KL）正则化时的统计效率。目标函数定义为：
$$J_{FKL}(\pi) := \mathbb{E}[r] - \eta^{-1} \text{KL}(\pi_{\text{ref}} \| \pi)$$
其中 $r$ 是奖励，$\eta$ 是正则化强度的倒数，$\pi_{\text{ref}}$ 是参考（行为）策略。

尽管反向 KL 正则化（$\text{KL}(\pi \| \pi_{\text{ref}})$）已被广泛研究，并证明在单策略可集中性（即行为策略仅覆盖最优策略）下具有 $\tilde{O}(\epsilon^{-1})$ 的样本复杂度（快速速率），但 Forward-KL 情形仍是一个未决问题。现有的 Forward-KL 分析要么无法适用，要么导致缓慢的 $\tilde{O}(\epsilon^{-2})$ 速率。此外，鉴于 Forward-KL 具有“质量覆盖”特性（即在 $\pi_{\text{ref}} > 0$ 处惩罚 $\pi \to 0$）而非“模式寻求”特性，可能需要更强的覆盖假设，因此单策略可集中性是否足以支持 Forward-KL 尚不明确。

本文旨在回答两个核心问题：

1. 前向 KL 正则化目标的决策制定统计速率是什么？
2. 在此设定下，单策略可集中性是否足以实现速率最优的离线学习？

方法论

作者提出了一种针对**前向 KL 正则化悲观上下文多臂老虎机（FKL-PCB）**的简化分析。该方法与以往依赖泰勒展开和中值定理（MVT）的工作有显著不同。

1. 摒弃传统的基于 MVT 的分析：
以往分析正则化目标的工作通常利用中值定理在中间点 $\bar{u}$ 处进行泰勒展开，以分解次优性差距。对于反向 KL，所得项在悲观主义下表现出单调性，允许利用单策略可集中性来界定误差。
然而，作者证明（引理 5.3），对于 Forward-KL，次优性分解项的导数涉及一个中心随机变量的“倾斜偏度”。该导数的符号不确定，意味着单调性论证失效。因此，标准的基于 MVT 的流程无法在不诉诸更强（全策略）可集中性假设的情况下实现快速速率。

2. 凸分析流程：
为了绕过 MVT 的局限性，作者引入了一种基于凸共轭和Bregman 散度的新颖证明技术：

• 对偶视角： 他们通过概率单纯形上的凸共轭来刻画正则化目标。
• 自界论证： 他们推导了一个次优性差距的恒等式（引理 5.5），该恒等式直接将误差表示为真实奖励与悲观估计之间的平方差，并乘以最优策略与参考策略的比率进行加权。
• 关键恒等式： 核心技术贡献是不等式：
  $$\text{SubOpt}_{FKL}(\hat{\pi}) \leq 2\eta \sum_{a} \frac{(\pi^*_{FKL}(a))^2}{\pi_{\text{ref}}(a)} (r(a) - \hat{r}(a))^2$$
  该界仅依赖于单策略可集中性系数 $C_{\pi^*} = \sup \frac{\pi^*}{\pi_{\text{ref}}}$，避免了对全策略可集中性的需求。

3. 算法设计：
本文提出了 FKL-PCB，这是一种适用于表格和函数逼近设定的悲观算法：

• 估计： 使用最小二乘法估计奖励函数。
• 悲观主义： 减去一个惩罚项（置信界），以确保估计奖励 $\hat{r}$ 以高概率被真实奖励 $r$ 下界约束。
• 优化： 输出最大化悲观正则化目标的策略。

主要贡献与结果

1. 快速样本复杂度上界：
本文建立了在单策略可集中性下，Forward-KL 正则化离线 CB 的第一个 $\tilde{O}(\epsilon^{-1})$ 样本复杂度上界：

• 表格设定： $\tilde{O}\left( \eta (C_{\pi^*})^2 |S||A| \epsilon^{-1} \right)$。
• 函数逼近： $\tilde{O}\left( \eta C_{\pi^*} D^2_{\pi^*} \log N_G \epsilon^{-1} \right)$，其中 $D^2_{\pi^*}$ 是 $D^2$ 型可集中性系数，$N_G$ 是函数类的覆盖数。
• 这些结果改进了 Aminian 等人（2025）之前的最先进 $\tilde{O}(\epsilon^{-2})$ 上界，并将要求从全策略可集中性放宽为单策略可集中性。

2. 极小极大下界：
作者提供了匹配的下界以证明其上界的紧致性：

• 表格下界： 在高正则化区域为 $\Omega(\eta |S||A| \epsilon^{-1})$。这证实了对 $\eta$ 的线性依赖和 $1/\epsilon$ 速率是最优的。
• 相变： 下界揭示了类似于反向 KL 的“相变”。在低正则化区域（大 $\eta$），样本复杂度退化为缓慢的 $\tilde{O}(\epsilon^{-2})$ 速率，表明正则化是实现快速速率所必需的。

3. 技术新颖性：
本文声称，这种“凸分析流程”统一了表格和函数逼近设定，并完全绕过了基于中值定理的证明流程。该方法被提出作为分析其他散度正则化决策问题的独立兴趣点。

意义与主张

本文定位为第一项精确刻画离线学习中 Forward-KL 正则化统计速率的工作。其主要意义在于：

• 解决未决问题： 它解决了单策略可集中性是否足以支持 Forward-KL 的问题，并以快速速率给出了肯定回答。
• 统一理论： 它表明，只要采用新颖的分析方法，Forward-KL 的“质量覆盖”特性并不像“模式寻求”的反向 KL 那样 inherently 需要更强的覆盖假设。
• 算法简洁性： 它表明，基于最小化悲观主义的算法（FKL-PCB）足以实现这些最优速率，无需复杂的算法修改。

作者对未来方向保持谦逊，指出虽然他们确立了充分性，但单策略可集中性对于 Forward-KL 的必要性（即使在多臂老虎机中）仍然是一个未决问题。此外，推导专门针对函数逼近中 $D^2$ 型可集中性的、与上界匹配的下界，留待未来工作完成。