Sharp analysis of linear ensemble sampling

技术摘要：对线性集成采样（Linear Ensemble Sampling）的尖锐分析

问题设定
本文在随机线性老虎机（stochastic linear bandits）的框架下研究了集成采样（Ensemble Sampling, ES）。在此设定中，学习者在 $n$ 轮交互中，从闭集 $\mathcal{X} \subset \mathbb{R}^d$（通常为单位球）中选择动作 $X_t$，以最大化累积回报。回报遵循线性模型 $Y_t = \langle X_t, \theta^* \rangle + \eta_t$，其中 $\theta^*$ 是未知参数，$\eta_t$ 是亚高斯噪声。目标是最小化 $n$ 步伪遗憾（pseudo-regret），即最优策略与学习者策略之间的累积回报之差。

虽然 汤普森采样（Thompson Sampling, TS） 是该设定下探索机制的金标准，实现了高概率遗憾界 $\tilde{O}(d^{3/2}\sqrt{n})$，但 ES 在历史上一直表现滞后。以往对线性老虎机中 ES 的分析要么要求集成规模随动作数量缩放（这使得它们不适用于无限动作集），要么即使在集成规模为 $O(d \log n)$ 时也只能实现 $\tilde{O}(d^{5/2}\sqrt{n})$ 的次优遗憾界。

方法论
作者分析了使用标准高斯扰动的 ES。该算法维护着 $m$ 个岭回归模型。每个模型 $j$ 根据动作和回报的历史进行训练，但进行了两个关键修改：

1. 扰动先验（Perturbed Prior）： 正则化目标是一个从先验分布中抽取的随机向量 $\zeta^j$，而非零向量。
2. 扰动数据（Perturbed Data）： 观测到的回报被注入了独立的高斯噪声 $\xi^j_t$。

学习者在每一轮中从集成中均匀随机地选择一个模型，并选择在该模型下预测回报最大的动作。

核心技术挑战在于由自适应性引起的依赖关系：尽管注入模型的噪声是独立的，但这些模型是耦合的，因为它们是在由集成自身动作选择所收集的数据上进行训练的。

为了克服这一点，作者采用了**连续时间嵌入（continuous-time embedding）**方法：

1. 鞅表示（Martingale Representation）： 他们将驱动模型参数的噪声过程识别为可预测对角鞅变换（predictable diagonal martingale transforms），形式为 $S_t = \sum D_s \xi_s$，其中 $D_s$ 是可预测的对角矩阵。
2. 布朗运动嵌入（Brownian Embedding）： 利用扰动的高斯特性，作者证明了一个表示引理（定理 5.3），表明这些离散时间鞅变换可以精确地表示为在由变换的可预测二次变分确定的随机时间上评估的独立标准布朗运动。
3. 一致时间越界（Time-Uniform Exceedance）： 这种嵌入将控制遗憾的问题转化为分析 $m$ 个独立布朗运动的一致时间越界频率。具体而言，他们证明了必须有足够比例的布朗运动在时间上一致地保持在一条曲线边界 $c\sqrt{t}$ 之上。这通过使用随机分析工具实现，包括 Dambis–Dubins–Schwarz 时间变换、Ornstein–Uhlenbeck 过程以及边界穿越估计。

核心贡献

1. 尖锐的遗憾界： 本文证明，通过设置集成规模 $m = \Theta(d \log n)$，ES 可以达到 $\tilde{O}(d^{3/2}\sqrt{n})$ 的高概率遗憾界。这与汤普森采样的典型遗憾率相匹配。
2. 计算效率： 不同于以往要求集成规模随动作数量缩放（例如 $m = \Omega(k \log n)$）的结果，本研究保持了集成规模仅随维度 $d$ 线性缩放，这使其适用于无限动作集（如单位球），而无需昂贵的离散化成本。
3. 理论下界： 作者证明，如果集成规模 $m \le d/2$，则存在线性老虎机实例使得 ES 产生线性遗憾，从而证明了 $O(d)$ 缩放的必要性。
4. 新的分析视角： 该工作引入了一个用于分析离散时间自适应算法的“连续时间透镜”。通过将离散鞅嵌入到独立的布朗运动中，作者将自适应性隔离到了“时钟”（时间变换）中，从而使原本使用纯离散方法难以处理的自归一化越界问题变得可处理。

结果

• 定理 4.1： 对于 $m \ge 2000 d \log(n/\delta)$ 及特定的调优参数，$n$ 步遗憾 $R_n$ 以至少 $1 - 4\delta$ 的概率被限制在 $\tilde{O}(d^{3/2}\sqrt{n})$ 内。
• 定理 4.2： 如果 $m \le d/2$，ES 在某些问题实例中无法实现亚线性遗憾，证实了集成规模要求的紧致性。
• 对比： 这些结果在保持每轮计算开销与其它方法相当的前提下（假设 $m = \tilde{O}(d)$），缩小了 ES 与 TS 在遗憾缩放方面的差距。

意义与声明
论文声称其主要贡献是弥合了差距，即在随机线性老虎机设定下使集成采样（ES）的表现接近汤普森采样（TS）。作者强调，其证明技术为随机探索提供了一个新视角，将一个复杂的自适应离散时间问题简化为独立布朗运动的一致时间越界问题。

他们明确表示，目前尚未知晓其他路径可以获得尖锐的 ES 界，这突显了使用连续时间工具（特别是精确的布朗嵌入）来解决纯离散时间问题的创新性。作者对工具的适用范围持谦逊态度，指出虽然他们推测类似的结论可能适用于其他扰动分布（如 Rademacher），但证明这一点需要不同的工具（如 Skorokhod 嵌入），这仍是一个开放的研究方向。他们还指出，目前的方法依赖于噪声变换的对角结构（标量乘以单位矩阵），这与更一般的对角情况相比简化了分析。