When and why randomised exploration works (in linear bandits)

技术摘要：随机探索何时以及为何有效（在线性 Bandit 问题中）

问题设定
本文研究了线性 Bandit 问题，这是一个序列决策设定，智能体从单位欧几里得球内的一个闭子集 $\mathcal{X}$ 中选择动作 $X_t$。智能体接收到的奖励 $Y_t$ 其均值为 $\langle X_t, \theta^\star \rangle$，其中 $\theta^\star$ 是一个未知的参数向量。目标是最小化 $n$ 步遗憾值（regret），即最优动作的奖励与所选动作奖励之间的累积差值。

虽然乐观算法（例如置信上限法 UCB）已在处理线性 Bandit 问题时建立了 $O(d\sqrt{n} \log n)$ 的频率派遗憾界，但像 Thompson sampling 这样的随机化探索算法在这一设定下的分析一直较为困难。以往对随机化方法的频率派分析通常依赖于“强制乐观”（forced optimism）或“后验膨胀”（posterior inflation）——即通过修改算法来人为地增大后验分布的方差，以确保以高概率实现乐观。这些修改通常会导致次优的遗憾界，例如 $O((d \log n)^{3/2}\sqrt{n})$，与乐观算法相比引入了额外的 $\sqrt{d}$ 因子。此外，最近的下界研究（Hamidi and Bayati, 2023; Zhang, 2022）表明，在特定的病态设定下，未经修改的 Thompson sampling 可能会产生线性遗憾，这表明如果没有结构性假设，随机化探索并非普遍最优。

方法论与假设
作者提出了一种新的分析框架，该框架避免了修改随机化算法（即不进行强制乐观或后验膨胀）。相反，该分析依赖于动作集 $\mathcal{X}$ 的特定几何性质。

1. 算法框架： 本文考虑了一类随机化算法，其中在每一步 $t$，采样一个参数 $\theta_t = \hat{\theta}_{t-1} + V_{t-1}^{-1/2}\eta_t$，其中 $\hat{\theta}_{t-1}$ 是正则化最小二乘估计，$V_{t-1}$ 是设计矩阵，$\eta_t$ 是旋转不变的扰动。动作的选择为 $X_t = \arg\max_{x \in \mathcal{X}} \langle x, \theta_t \rangle$。
2. 扰动假设： 假设扰动 $\eta_t$ 是独立的、旋转不变的随机变量，且具有有界的二阶和四阶矩（例如高斯分布或球面上的均匀分布）。
3. 动作集假设（光滑性与强凸性）： 核心理论贡献在于假设 4.2，该假设要求动作集 $\mathcal{X}$ 是单位球内的一个闭的、吸收性的（absorbing）子集，使得其支撑函数的平方 $J_{\mathcal{X}}^2$ 相对于特定的范数 $\|\cdot\|_*$ 既是 $m$-强凸的，又是 $M$-光滑的。
   • 强凸性： 确保支撑函数不存在“平坦”区域，保证参数空间的微小变化能转化为有意义的动作空间变化。
   • 光滑性： 确保支撑函数的梯度（将参数映射到动作的映射）是 Lipschitz 连续的，防止由于参数扰动导致遗憾值的剧烈跳变。
   • 示例： 此类集合包括缩放后的 $\ell_q$-球（其中 $q \in (1, \infty)$）。

核心贡献与分析
本文提供了一个不需要依赖“面对不确定性时的乐观主义”框架的频率派遗憾分析。相反，该分析直接分析了探索过程的动力学以及置信集的演化。

• 遗憾分解： 作者将期望遗憾分解为两个部分：算法处于“乐观”状态（采样的参数产生的数值高于真实最优值）的步骤，以及不处于乐观状态的步骤。
• 非乐观探索： 一个关键的洞察是，即使采样值并非乐观，它仍然提供了有价值的信息，从而缩小了置信集。作者利用每步遗憾的 Bregman 散度形式化表示 $r_t = D_{J_{\mathcal{X}}}(\theta^\star, \theta_t)$，并利用 $J_{\mathcal{X}}^2$ 的强凸性和光滑性来限制该散度。
• 信息增长： 证明过程通过建立期望信息增益 $\mathbb{E}_{t-1}[X_t X_t^\top]$ 与置信椭球几何形状之间的联系，确立了设计矩阵 $V_t$ 增长的下界。这建立了参数空间的大小（由 $V_t^{-1/2}$ 衡量）与实际执行的探索之间的联系。
• 避免膨胀： 与以往的工作不同，本分析不需要膨胀采样分布的方差。它证明了算法自身的自然随机性，结合 $\mathcal{X}$ 的几何性质，足以驱动探索并控制遗憾值。

主要结果
在所述假设下，作者证明了任何满足扰动条件的随机化算法都能实现如下频率派遗憾界：
$$R_n \lesssim O(d\sqrt{n} \log n)$$
具体而言，定理 4.1 提供的界为 $O(d\sqrt{n} \log n)$ 阶（忽略 $n$ 和 $\delta$ 中的对数因子）。这在忽略对数因子的情况下，达到了线性 Bandit 已知的下界（Rusmevichientong and Tsitsiklis, 2010）。

意义与主张
本文声称解决了关于线性 Bandit 中 Thompson sampling 的维度依赖性的重要开放问题。

• 最优维度依赖性： 本文首次证明，在结构化线性 Bandit 设定中（特别是当动作空间是光滑且强凸时），未经修改（非膨胀）的 Thompson sampling 可以实现最优的维度依赖性（$O(d)$）。
• 成功机制： 该工作阐明了随机化探索在这些设定下为何奏效：动作集的几何性质确保了参数空间的扰动能够有效地探索动作空间，而无需人工引入乐观性。
• 局限性与范围： 作者承认，其结果并不矛盾于那些显示在非光滑或非吸收性动作空间（例如含有“陷阱”臂的集合）中 Thompson sampling 会产生线性遗憾的现有下界。该方法的成功取决于动作集是否满足光滑性和强凸性假设。本文并未声称这些条件是必要的，而是说明它们足以在无需算法修改的情况下实现最优速率。

总而言之，本文确立了对于一类广泛的良好行为的动作集（包括 $\ell_q$-球），随机化探索算法能自然地达到最优的遗憾率，从而消除了此前被认为实现理论保证所必需的、针对方差膨胀的权宜之计。