通过绝对扰动实现线性赌博机中的随机探索

# 通过绝对扰动实现线性赌博机的随机化探索
来源：https://arxiv.org/html/2606.28616
###### 摘要

在随机线性赌博机中，经典的 Upper Confidence Bound (UCB) 算法具有简单的频率派遗憾分析，但计算代价可能较高；而 Thompson Sampling (TS) 计算上具有吸引力，但由于其非乐观特性，通常更难分析。我们提出 Absolute Thompson Sampling (ATS)，这是对 TS 的一个简单修改，通过将带符号的探索噪声替换为其绝对值，确保了期望上的乐观性。这保留了 TS 的计算效率，同时避免了 TS 分析中常见的技术上复杂的反集中论证，使得遗憾分析可以像 UCB 那样简单。我们证明 ATS 实现了 O~(d^(3/2)√K) 的遗憾，与线性赌博机中 TS 的现有界相匹配。我们进一步引入 Ensemble Absolute Thompson Sampling (EATS)，它取多个绝对扰动的最大值并按集成规模进行归一化。随着集成规模增长，EATS 收敛到 UCB 目标，在极限情况下恢复 UCB 的行为。实验表明，适中的集成规模已经能产生强劲的性能。我们的结果在理论和实践上都在随机化探索与确定性乐观之间架起了一座桥梁。

## 1 引言

我们研究随机线性赌博机问题，其中学习者从给定的臂集中顺序选择臂，并观察带噪声的线性奖励。高效探索是实现低遗憾的核心挑战。最广泛使用的两类方法是基于乐观的算法（如 Upper Confidence Bound, UCB）和随机化算法（如 Thompson Sampling, TS）。

UCB 算法根据“面对不确定性的乐观”(OFU) 原则选择臂，最大化关于估计奖励的上置信界。这一原则带来了基于置信集和椭圆势引理 (abbasi2011improved) 的简单而优雅的遗憾分析。然而，UCB 计算上可能代价高昂，因为它需要在臂集上最大化一个椭圆奖励项。相比之下，TS 通过从后验分布中采样一个参数并贪婪地作用于该采样参数来选择臂。由于每轮计算简化为了在臂集上求解一个线性最大化问题，TS 在计算上具有吸引力。然而，其频率派遗憾分析比 UCB 更复杂。因为采样参数可能低估真实奖励，典型的分析要求 TS 以一定概率产生乐观参数，并控制在非乐观轮次中产生的遗憾 (agrawal2013thompson; abeille2017linear)。

因此，UCB 和 TS 在计算和分析性质上具有互补性。我们通过引入 TS 的一个简单修改来弥合这一差距，该修改模拟了 UCB 的行为。在第 4 节中，我们引入 Absolute Thompson Sampling (ATS)，它将 TS 中带符号的探索噪声替换为其绝对值。这一修改确保了“期望上的乐观性”：ATS 中使用的探索奖励项在期望上与 UCB 奖励项相匹配。因此，遗憾分析在概念上类似于 UCB，并且避免显式处理非乐观轮次。我们证明 ATS 以高概率实现 O~(d^(3/2)√K) 的遗憾，与线性赌博机中现有的 TS 遗憾界相匹配 (abeille2017linear)。此外，ATS 保留了 TS 的计算效率，每轮仅需多一次线性最大化。

虽然 ATS 达到了与 TS 相同的遗憾界，但与 UCB 相比，它引入了一个额外的 d√d 因子 (abbasi2011improved)。为了解决这一问题，我们提出了 ATS 的一个扩展，使其更接近于 UCB。受高斯随机变量极值性质 (命题 5.1) 的启发，我们引入集成绝对 Thompson Sampling (EATS)，它将 ATS 中的单个扰动替换为多个扰动的最大值。我们证明，随着集成规模增长，EATS 目标收敛到 UCB 目标，在极限情况下恢复 UCB 的行为。实验表明，适中的集成规模已经能产生强劲的性能，表明随机化探索与确定性乐观之间的实践折中 (第 6 节)。为具有有限集成规模的 EATS 建立理论保证仍是一个有趣的开放问题 (注记 5.3)。

总之，我们的结果揭示了随机化探索的一个新视角：通过精心塑造探索项，可以设计出保留 TS 计算效率同时分析和行为与 UCB 密切对齐的算法。我们的工作为设计用于赌博机问题的简单而高效的随机化算法开辟了新方向。

## 2 相关工作

对于线性赌博机，agrawal2013thompson 和 abeille2017linear 提供了 TS 的基本频率派遗憾分析，建立了 O~(d^(3/2)√K) 的界。这些工作中的常见策略是证明 TS 以常数概率 p 采样一个乐观参数，然后通过将乐观遗憾乘以 1/p 来约束遗憾 (janz2023ensemble)。类似的证明技术后来被扩展到多项逻辑赌博机 (oh2019thompson)、广义线性赌博机 (kveton2020randomized) 和线性 MDP (zanette2020frequentist)。abeille2025and 发展了更严格的分析，避免依赖常数概率的乐观性，实现了 O~(d√K) 的遗憾，匹配线性赌博机的下界 (dani2008stochastic; rusmevichientong2010linearly)。然而，他们的结果需要动作集上的额外结构假设，例如 L2 单位球。

虽然这些工作建立了次线性遗憾保证，但现有的线性 TS 分析在技术上很复杂，因为它们必须仔细控制在非乐观轮次中产生的遗憾。相比之下，通过确保“期望上的乐观性”，我们的方法避免单独分析非乐观轮次，使得证明在概念上像 UCB 一样简单 (abbasi2011improved)。关于我们方法的更多细节见第 4 节。

与我们的工作更接近的是，zhang2022feel 和 huix2023tight 修改 TS 以强制更强的乐观性。然而，他们的方法依赖于通过马尔可夫链蒙特卡罗从偏斜的后验分布中采样，这增加了计算复杂度并削弱了 TS 的实际吸引力。相比之下，vaswani2019old 通过引入随机扰动修改 UCB。虽然他们实现了 O~(d√K) 的遗憾，但他们的方法需要在臂集上最大化一个椭圆奖励项，这在实际中计算代价高昂。相比之下，我们的方法仅对 TS 进行了微小的修改，并且可以使用与标准 TS 相同的线性最大化预言机来实现。

## 3 预备知识

给定两个向量 x,y ∈ ℝ^d 和一个正定矩阵 A ∈ ℝ^{d×d}，记 ⟨x,y⟩ = x^⊤ y 和 ∥x∥_A = √(x^⊤ A x)。记 S^{d-1} 为 ℝ^d 中的单位球面。全零向量和全一向量分别记为 0 和 1。对于随机变量 X_n 和 X，记 X_n →P X 表示依概率收敛，即对任意 ε>0，lim_{n→∞} P(|X_n - X| > ε) = 0。

### 3.1 随机线性赌博机

设 A ⊂ ℝ^d 是紧的臂集。不失一般性，假设对所有 φ∈A 有 ∥φ∥_2 ≤ 1。在每一轮 k，智能体拉取一个臂 φ_k ∈ A 并观察奖励 r_k = (θ^⋆)^⊤ φ_k + ε_k。其中 θ^⋆ ∈ ℝ^d 对智能体未知，满足 ∥θ^⋆∥_2 ≤ B，且 ε_k 是零均值 R 次高斯噪声。定义 r(φ) ≔ (θ^⋆)^⊤ φ。智能体的目标是实现次线性遗憾：

Reg(K) := ∑_{k=1}^K r^⋆ - r(φ_k) = o(K)   (1)

其中 r^⋆ = max_{φ∈A} r(φ)。记 φ^⋆ ∈ arg max_{φ∈A} r(φ) 为最优臂。

记 Λ_k 为正则化 Gram 矩阵，θ̂_k 为 θ^⋆ 在第 k 轮的岭估计：

Λ_k = λI + ∑_{i=1}^{k-1} φ_i φ_i^⊤,   θ̂_k = Λ_k^{-1} ∑_{i=1}^{k-1} φ_i r_i,   (2)

其中 λ>0 是正则化参数。

### 3.2 基本算法

两个流行的算法是 Upper Confidence Bound (UCB) 和 Thompson Sampling (TS)。

#### UCB 算法。

UCB 为 θ^⋆ 构造一个置信集，并选择具有最大上置信界的臂。下面的引理给出了估计误差 θ̂_k - θ^⋆ 的置信界。

###### 引理 3.1 (置信界；abbasi2011improved)。

设 E 为事件，使得对所有 k 有

∥θ̂_k - θ^⋆∥_{Λ_k} ≤ √λ B + R √(d ln((1 + k/λ)/δ)) =: β_k ,

其中 δ>0。那么，对任意 δ>0，有 P(E) ≥ 1-δ，从而对任意 φ∈A 和 k 有

|φ^⊤ θ^⋆ - φ^⊤ θ̂_k| ≤ β_k ∥φ∥_{Λ_k^{-1}}.   (3)

利用 (3) 式，UCB 选择具有最大上置信界的臂：

(UCB) φ_k^{UCB} ∈ arg max_{φ∈A} φ^⊤ θ̂_k + β_k ∥φ∥_{Λ_k^{-1}}.   (4)

这一规则体现了“面对不确定性的乐观”(OFU) 原则：它偏好估计奖励高且不确定性大的臂，从而平衡利用与探索。UCB 以至少 1-δ 的概率具有 O(d√K ln(K δ^{-1})) 的遗憾 (abbasi2011improved)。

#### Thompson sampling。

TS 维护未知参数 θ^⋆ 的后验分布，并贪婪地作用于一个采样参数。当使用高斯先验和似然估计 θ^⋆ 时，后验分布也是高斯的，TS 通过以下方式选择臂：

(TS) φ_k^{TS} ∈ arg max_{φ∈A} f(φ, ξ_k) ≔ φ^⊤ θ̂_k + β_k φ^⊤ Λ_k^{-1/2} ξ_k  其中 ξ_k ∼ N(0, I).   (5)

TS 在实践中通常更受欢迎，因为它在计算上更简单，更易于实现。对于固定的高斯样本，(5) 式简化为在 A 上的线性最大化，而 UCB 在 (4) 式中最大化一个线性项加上一个椭圆奖励项。

然而，TS 的遗憾分析比 UCB 更具挑战性。与 UCB 不同，TS 可能选择非乐观的臂，这需要对非乐观轮次进行更精细的分析。典型的证明策略首先通过反集中论证（例如 agrawal2013thompson 中的引理 2）证明 TS 以常数概率 p>0 采样一个乐观参数，然后将乐观遗憾乘以 1/p（例如 janz2023ensemble 中的“主定理”）。这产生了 O(p^{-1} √(d^3 K) ln(K δ^{-1})) 的遗憾界 (agrawal2013thompson; abeille2017linear)。

## 4 绝对 Thompson Sampling

如前一节所述，UCB 具有简单的遗憾分析但计算密集，而 TS 计算高效但需要更复杂的分析。为了弥合这一差距，我们设计了一个随机化算法，它既保留了 TS 的计算效率，又允许更接近 UCB 的遗憾分析。

我们的关键思想是对 TS 进行最小的修改，使其行为更像 UCB。具体来说，我们使用以下等式：对于任意对称正定矩阵 Λ 和向量 φ∈ℝ^d，

E_{ξ∼N(0,I)} [ |φ^⊤ Λ^{-1/2} ξ| ] = √(2/π) ∥φ∥_{Λ^{-1}}.   (6)

因此，对于固定的 φ，TS 中的绝对内积项 |φ^⊤ Λ_k^{-1/2} ξ_k| 在期望上表现得像 UCB 奖励项 ∥φ∥_{Λ_k^{-1}}。

受这一观察启发，我们将 (5) 式中的带符号内积替换为其绝对值。

(ATS) φ_k^{ATS} ∈ arg max_{φ∈A} φ^⊤ θ̂_k + √(π/2) β_k |φ^⊤ Λ_k^{-1/2} ξ_k|  其中 ξ_k ∼ N(0, I).   (7)

我们将此算法称为绝对 Thompson Sampling (ATS)。

### 4.1 ATS 的性质

设 F_k ≔ σ(ξ_1, ε_1, ..., ξ_k, ε_k) 为滤子，使得 ε_k 和 ξ_k 是 F_k 可测的。我们稍作滥用记号，使用缩写 E_{ξ_k}[·] := E[· | F_{k-1}]。

**for** k=1,...,K **do**

更新 Gram 矩阵

Λ_k = λI + ∑_{i=1}^{k-1} φ_i φ_i^⊤;

采样

ξ_k ∼ N(0, I);

计算

φ_k ∈ arg max_{φ∈A} φ^⊤ θ̂_k + √(π/2) β_k |φ^⊤ Λ_k^{-1/2} ξ_k|;