Stochastic Linear Bandits with Parameter Noise

技术摘要：带参数噪声的随机线性 Bandit

问题定义
本文研究了带参数噪声的随机线性 Bandit模型。在该设定下，学习者在时间范围 $T$ 内与环境交互，从动作集 $\mathcal{A} \subseteq \mathbb{R}^d$ 中选择动作 $a_t$。与奖励为 $X_t = a_t^\top \theta^\star + \eta_t$（其中 $\theta^\star$ 固定，$\eta_t$ 为噪声）的标准加性噪声模型不同，参数噪声模型假设奖励由 $X_t = a_t^\top \theta_t$ 给出，其中 $\theta_t$ 独立同分布地从一个固定的未知分布 $\nu$ 中采样，该分布的均值为 $\theta^\star$，协方差矩阵为 $\Sigma$。

本文强调了一个关键区别：在参数噪声模型中，学习者可以影响奖励的方差。具体而言，$\text{Var}(X_t) = a_t^\top \Sigma a_t$，而在加性噪声模型中，方差完全由环境决定。作者指出，虽然参数噪声模型是对对抗性线性 Bandit 模型（其中 $\theta_t$ 由对手选择）的一种松弛，但它具有独特的结构特性，使得在某些几何设定下，其遗憾界可能比加性噪声模型更紧。

方法论与算法
作者提出了两种针对不同动作集几何结构的算法：

1. VASE（方差感知最优设计连续消除）：

   • 目标： 通用有限动作集（以及通过覆盖论证处理的无限集）。
   • 机制： 一种利用方差信息的连续消除算法。在每个阶段，它计算一个 G-最优设计 $\pi_\ell$ 来选择动作。它使用停止规则算法（SR）显式估计设计支撑集中动作的方差。
   • 关键创新： 该算法以两种方式利用估计的方差：一是减少探索所需的样本数量，二是作为加权最小二乘估计器中的权重。这种加权确保了即使样本较少，估计器的协方差也能保持受控，从而得出依赖于方差的遗憾界。

2. VALEE（方差感知线性探索 - 利用）：

   • 目标： $\ell_p$ 单位球，其中 $p \in (1, 2]$（及其对偶范数 $q \ge 2$）。
   • 机制： 一种简单的探索 - 利用算法。
     • 探索： 算法播放标准基向量 $e_i$。它使用中位数 - 均值（MoM）技术逐坐标估计均值向量 $\theta^\star$。如果协方差矩阵 $\Sigma$ 未知，则首先估计基向量的方差。
     • 利用： 一旦估计误差相对于方差和时间范围足够小，算法便承诺执行一个由估计均值 $\hat{\theta}$ 导出的动作 $\hat{a}$，具体为 $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$。
   • 关键创新： 分析利用了 $\ell_p$ 球的几何结构和参数噪声结构。作者表明，探索基向量产生的估计误差与 $\sqrt{\sigma^2(e_i)}$ 成正比，这比加性噪声模型中标准的 $\epsilon$ 界更紧。这使得算法能够实现依赖于奖励分布方差结构的最优遗憾界。

主要结果
本文建立了上界和下界，证明了所提出的算法在特定设定下是最小最大最优的（对数因子范围内）。

• 通用有限动作集（$K$ 个动作）：

  • 上界： VASE 实现的遗憾为 $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$，其中 $M_\sigma$ 是一个依赖于方差的量，其上界为 $\max_a \sigma^2(a)$。
  • 下界： 证明了 $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ 的下界，表明当 $\log(K) \approx d$ 时，上界在对数因子范围内是紧的。

• $\ell_p$ 单位球（$p \le 2$）：

  • 已知协方差： VALEE 实现的遗憾为 $\tilde{O}(d + \sqrt{dT \sigma^2_q})$，其中 $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$。通过匹配的下界 $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$ 证明了其最优性。
  • 未知协方差： VALEE 产生一个额外的加性项，导致遗憾为 $\tilde{\O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$。作者指出，这个加性项源于方差估计阶段。

• $\ell_p$ 单位球（$p > 2$）：

  • 本文提供了 $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$ 的下界，与这些几何结构下对抗性设定中已知的下界相匹配。

意义与主张
本文声称解决了一个关于线性 Bandit 的“奇特情况”：对于像 $\ell_2$ 单位球这样的特定动作集，加性噪声模型往往产生比对抗性模型（$\sqrt{dT}$）更差的遗憾界（$d\sqrt{T}$）。作者证明，参数噪声模型更符合“随机模型应比对抗性模型更容易”的直觉。

• 更紧的界： 对于 $p \le 2$ 的 $\ell_p$ 球，参数噪声模型允许达到 $\sqrt{dT \sigma^2_q}$ 量级的遗憾界，当方差较小时，这可能显著小于加性噪声模型典型的 $d\sqrt{T}$ 界。
• 结构优势： 结果表明，实现（而不仅仅是期望）的线性以及学习者影响方差的能力，对于实现这些改进的界至关重要。
• 简洁性： 令人惊讶的是，$p \le 2$ 的 $\ell_p$ 球的最优遗憾可以使用非常简单的探索 - 利用算法（VALEE）获得，这与加性噪声设定中通常所需的复杂最优设计算法形成对比。

作者总结道，虽然他们在协方差已知时关于 $p \le 2$ 的结果是最优的（对数因子范围内），但协方差未知的情况仍留下一个开放差距（$T^{1/3}$ 项），这可能是未来工作要解决的问题。他们还将设计一个匹配 $p > 2$ 下界的算法列为一个开放问题。