非单调凸脊强盗问题中的Thompson采样：多项式遗憾不需要单调性

# 非单调凸岭带臂问题的汤普森采样：多项式遗憾无需单调性

来源：https://arxiv.org/html/2609.10981

玄黎  
单位：新南威尔士大学，悉尼，澳大利亚 · [email protected]  
单位：ORCID: 0009-0002-0213-6991 (https://orcid.org/0009-0002-0213-6991)  
2026年9月10日

###### 摘要
Bakhtiari, Lattimore 和 Szepesvári (COLT 2025) 证明了对于具有凸*单调*岭损失 $f(x) = \ell(\langle x, \theta \rangle)$ 的带臂凸优化问题，汤普森采样 (TS) 的贝叶斯遗憾为 $\tilde{O}(d^{5/2}\sqrt{n})$，并提出了连接函数的单调性是否必要的问题。我们给出了一个定性的否定答案。对于任意具有任意凸（可能非单调）连接函数的 $[0,1]$ 值、1-利普希茨凸岭损失的先验，以及任何固定的可测极小元选择，精确后验 TS 的贝叶斯遗憾为 $O\left((d+1)^4\sqrt{dn}\,\log(e+nd\max\{1,\mathrm{diam}K\})\right) = \tilde{O}(d^{9/2}\sqrt{n})$。单调性的证明依赖于单点移除的约翰椭球二分法；我们通过一个显式的十二点构型表明，该二分法对非单调连接函数不成立，并用一个 $O(d^2)$ 的“无信息”构型基数界限取代之。该界限使用了布尔舍入论证：一个在最大范数内距离秩为 $r$ 的矩阵不超过 $1/(4r)$ 的 $0-1$ 矩阵，其秩至多为 $2r-1$。我们构造了 $d(d+1)$ 个无信息损失，表明该基数界限在大直径与间隔比情形下紧至常数因子，并提供了一个独立的信息比到遗憾的转换，该转换对固定的可测选择是一致的。单调情形下 $d^{5/2}$ 的依赖关系是否能够保持仍是一个开放问题。

## 1 引言
贝叶斯带臂凸优化是以下博弈。已知一个凸体 $K \subset \mathbb{R}^d$ 和一个从 $K$ 到 $[0,1]$ 的凸函数类 $\mathcal{F}$，以及一个关于 $\mathcal{F}$ 的先验 $\xi$。环境采样 $f \sim \xi$ 一次。在每一轮 $t=1,\dots,n$，学习者选择 $X_t \in K$ 并观察 $Y_t \in \{0,1\}$，其中 $\mathbb{E}[Y_t \mid X_1,Y_1,\dots,X_t,f] = f(X_t)$。学习者 $\mathcal{A}$ 的贝叶斯遗憾定义为 $\mathrm{BReg}_n(\mathcal{A},\xi) = \mathbb{E}\Big[\sup_{x \in K}\sum_{t=1}^n \big(f(X_t)-f(x)\big)\Big]$。汤普森采样 (TS) 在每一轮从后验分布中采样 $f_t$，并选择所采样函数的极小元 $X_t = x_{f_t}$ 作为行动。Bakhtiari, Lattimore 和 Szepesvári [1] 通过信息比分析了该设定下的 TS。在他们的结果中，他们证明了如果 $\xi$ 支持在*单调*凸岭函数上，即 $f(x) = \ell(\langle x, \theta \rangle)$，其中 $\ell:\mathbb{R} \to \mathbb{R}$ 是凸且非减的，那么 $\mathrm{BReg}_n(\mathrm{TS},\xi) = O(d^{2.5}\sqrt{n}\log^2(nd\,\mathrm{diam}K))$；他们还证明了 TS 在一般凸损失上可能会灾难性地失败。在他们的讨论中写道：
> “目前我们尚不确定在岭设定中单调性假设是否必要。我们最好的猜测是不需要。”
单调岭类是具有未知凸增连接函数的广义线性带臂的贝叶斯版本。放弃单调性允许像 $\ell(s) = \|s-s_0\|$ 这样的连接函数，其在 $K$ 上的极小元集合（当 $d \geq 2$ 且 $s_0$ 位于投影区间 $\{\langle x,\theta\rangle : x \in K\}$ 的内部时）是一个完整的超平面截面；凸岭损失的极小元因此可能是不唯一的，因此 TS 的打平规则变得重要，并且驱动单调分析的几何结构（沿岭方向的极小元排序）丢失了。我们的目标是统计性的而非计算性的：我们问的是经典的精确后验 TS 规则本身在这个结构化类上是否安全。凸岭连接函数存在低遗憾算法并不能解决这个问题。Lattimore [3] 使用不同的算法得到了一个具有隐藏固定方向且凸连接函数可能随时间变化的对抗性岭模型的极小极大遗憾 $O(d\sqrt{n}\log(nD))$，但这里的问题是算法特定的：[1] 表明标准 TS 在一般高维凸损失上可能会灾难性地失败，因此结构对于保证 TS 本身是真正必需的，而单调岭类是他们能够做到这一点的类别。我们的结果表明，即使连接函数是非单调的，凸岭结构也足够：这是关于经典贝叶斯采样规则的一个定性稳健性陈述，而非极小最优性主张。

#### 贡献。令 $\mathcal{F}_{\mathrm{blr}}$ 表示从 $K$ 到 $[0,1]$ 的 1-利普希茨凸岭函数类，具有任意凸连接函数（第 2 节）。
1. **无单调性的遗憾界**（定理 3.1）。对于 $\mathcal{F}_{\mathrm{blr}}$ 上的任意先验和任意固定的可测极小元选择，TS 满足 $\mathrm{BReg}_n(\mathrm{TS},\xi) = \tilde{O}(d^{9/2}\sqrt{n})$；具体地，$\mathrm{BReg}_n(\mathrm{TS},\xi) \leq 7+73{,}728\sqrt{3}\,(d+1)^4 d^{1/2}\sqrt{n}\,\log(e+nd\max\{1,\mathrm{diam}K\})$。这解决了精确后验 TS 的多项式贝叶斯遗憾是否需要单调性的定性问题；匹配单调情形 $d^{5/2}$ 依赖关系的定量问题仍然是开放的，将在第 9 节讨论。
2. **无信息构型的基数界**（定理 3.3）。[1] 的信息比机制归结为证明一个有限损失函数集合很小，该集合的极小元彼此不提供信息。在单调情形下，这通过一个约翰椭球二分法证明。我们表明这个单点移除的二分法没有非单调类比（命题 3.6），并直接证明每个这样的构型至多有 $3(d+1)^2-(d+1)-1$ 个元素。关键工具是一个初等的舍入引理（引理 5.3）：如果一个 $0-1$ 矩阵在每个元素上距离一个秩为 $r$ 的矩阵不超过 $1/(4r)$，那么它的秩至多为 $2r-1$。该界紧至常数：命题 3.5 展示了大小为 $d(d+1)$ 的无信息构型。
3. **在任意固定可测选择规则下从信息比到遗憾的转换**（定理 7.5）。[1] 的覆盖论证使用了极小元之间平局的处理是一致的。由于凸岭损失的极小元可能不唯一，我们为精确 TS 提供了一个独立的转换定理，适用于每个固定的可测选择规则，使用基于下确界卷积逼近的覆盖和对选择规则一致的信息比界。该规则是任意的但必须预先固定；不依赖于历史的打平规则不在覆盖范围内。
#### 相关工作。岭（单指标）带臂问题在不同的学习标准和算法下已被研究。Lattimore [3] 证明了对于一个具有隐藏固定方向且凸连接函数可能随时间变化的对抗性岭模型，通过信息论论证和极小极大对偶性，得到了极小极大遗憾 $O(d\sqrt{n}\log(nD))$；如上所述，这确立了岭结构的可学习性，但不涉及标准 TS 在任意先验下的情况。Bakhtiari 等人 [1] 直接分析精确 TS 并证明了单调岭界；本文在岭结构内移除了单调性。Rajaraman, Han, Jiao 和 Ramchandran [10]、Rajaraman 和 Han [11] 以及 Kang 等人 [13] 研究了使用除 TS 以外的算法的频繁主义非线性岭、单指标和上下文单指标带臂问题，而 Rajaraman 和 Han [12] 给出了通用随机带臂凸优化的极小极大下界，这些量化了通用凸损失的难度，但不针对非单调岭损失或 TS。这些结果都没有为任意凸非单调岭连接函数上的精确后验 TS 提供贝叶斯遗憾保证。我们不处理 [1] 同一段落中的*第二个*问题（*已知*连接函数的信息比）；另见 Bakhtiari 的硕士论文 [2]。TS 的信息比分析可追溯至 [7]；我们所依赖的凸带臂机制来自 [5,6,4,1]。

## 2 设定与记号
全文中，$K \subset \mathbb{R}^d$ 是一个凸体（紧致、凸、非空内部），且 $0 \in K$，$D = \mathrm{diam}(K)$。函数 $f:K \to \mathbb{R}$ 是*凸岭函数*，如果 $f(x) = \ell(\langle x,\theta\rangle)$ 对于某个凸 $\ell:\mathbb{R} \to \mathbb{R}$ 和 $\theta \in \mathbb{R}^d$（允许 $\theta=0$）。我们记 $\mathcal{F}_{\mathrm{bl}} = \{f:K \to [0,1]\ \text{凸},\ \mathrm{Lip}(f) \leq 1\}$，$\mathcal{F}_{\mathrm{blr}} = \{f \in \mathcal{F}_{\mathrm{bl}}:\ f\text{ 是凸岭函数}\}$，以及 $\mathcal{F}_{\mathrm{blrm}} \subset \mathcal{F}_{\mathrm{blr}}$ 表示具有非减连接函数的子类。类 $\mathcal{F}_{\mathrm{bl}}$ 和 $\mathcal{F}_{\mathrm{blrm}}$ 是 [1] 中的那些；$\mathcal{F}_{\mathrm{blr}}$ 在那里未被处理。
#### 可测性与打平（约定）。我们在 $\mathcal{F}_{\mathrm{blr}}$ 上配备一个 $\sigma$-代数 $\mathcal{A}$，使得对于每个 $x \in K$，$f \mapsto f(x)$ 可测，并且一个可测选择 $f \mapsto x_f \in \mathrm{arg\,min}_K f$ 已经一劳永逸地固定（这样的选择存在；见 [1, 附录 B]）。逐点可测性使得恒等映射 $(\mathcal{F}_{\mathrm{blr}},\mathcal{A}) \to (C(K),\mathcal{B})$ 可测，其中 $\mathcal{B}$ 是一致范数下的博雷尔 $\sigma$-代数；$\mathcal{A}$ 可能严格细于 $\mathcal{B}$。第 7 节构造的所有逼近函数作为 $(C(K),\mathcal{B})$-值映射是可测的，并且那里信息比假设仅应用于 $\mathcal{F}_{\mathrm{blr}}$ 的有限值随机元，这些元自动是 $\mathcal{A}$-可测的；这使得任意先验和任意固定选择成为可能。所有陈述对*每个*这样的选择规则都成立，但规则是预先固定的：它不能依赖于博弈的历史。我们记 $f^\star = \min_K f = f(x_f)$。对于 $\mathcal{F}_{\mathrm{blr}}$ 上的概率测度 $\xi$，我们记 $\bar{f} = \mathbb{E}_\xi[f]$（逐点），这是一个从 $K$ 到 $[0,1]$ 的凸函数，通常*不是* $\mathcal{F}_{\mathrm{blr}}$ 中元素的有限凸组合（例如，在平面中随机方向上的 $x \mapsto \max\{\langle x,\theta\rangle,0\}$ 的平均值是欧几里得范数的倍数）；下面的论证仅使用 $\bar{f}$ 的逐点值。
#### 汤普森采样。具有先验 $\xi$ 的 TS 是 [1] 的算法 1：在第 $t$ 轮，从后验 $\mathbb{P}(f \in \cdot \mid X_1,Y_1,\dots,X_{t-1},Y_{t-1})$ 中采样 $f_t$ 并行动 $X_t = x_{f_t}$。观察模型是伯努利的：$Y_t \in \{0,1\}$，其中 $\mathbb{E}[Y_t \mid X_1,Y_1,\dots,X_t,f] = f(X_t)$。
#### 遗憾与信息项。除非另有说明，随机函数 $h:K \to [0,1]$ 是 $C(K)$ 的博雷尔随机元（因此 $(\omega,x) \mapsto h_\omega(x)$ 是联合可测的且 $h^\star = \min_K h$ 可测）；$\mathcal{F}_{\mathrm{bl}}$ 上的律，以及通过恒等映射 $(\mathcal{F}_{\mathrm{blr}},\mathcal{A})$ 上的律，都包含在内。对于这样一个随机函数 $h$ 的律 $\nu$ 和策略 $\pi \in \mathcal{P}(K)$，令 $(X,h) \sim \pi \otimes \nu$，$\bar{h} = \mathbb{E}_\nu[h]$，并定义 $\Delta(\pi,\nu) = \mathbb{E}[\bar{h}(X)-h^\star]$，$I(\pi,\nu) = \mathbb{E}\big[(h(X)-\bar{h}(X))^2\big]$。对于 $\xi \in \mathcal{P}(\mathcal{F}_{\mathrm{blr}})$，令 $\pi^\xi_{\mathrm{TS}}$ 表示 $f \sim \xi$ 下 $x_f$ 的律。遵循 [1]，$\mathrm{IR}(\mathcal{F}) = \Big\{(\alpha,\beta) \in \mathbb{R}_+^2:\ \sup_{\xi \in \mathcal{P}(\mathcal{F})}\big[\Delta(\pi^\xi_{\mathrm{TS}},\xi) - \alpha - \sqrt{\beta I(\pi^\xi_{\mathrm{TS}},\xi)}\big] \leq 0\Big\}$。由于 $\pi^\xi_{\mathrm{TS}}$ 依赖于选择，因此 $\mathrm{IR}(\mathcal{F})$ 也依赖于选择；我们说 $(\alpha,\beta) \in \mathrm{IR}(\mathcal{F})$ 如果对每个可测选择都成立，则称其*一致*。
#### 分解引理。以下是对 [1, 引理 3] 中分解工具的重新陈述，该工具在原文中是针对 $\bar{f} \in \mathrm{conv}(\mathcal{F})$ 陈述的。由于 $\mathbb{E}_\xi f$ 不必是有限凸组合，我们在附录 A 中包含了证明。
###### 引理 2.1（分解；继 [1, 引理 3]）。令 $\mathcal{F} \subseteq \mathcal{F}_{\mathrm{blr}}$ 且 $\alpha,\beta_0 \geq 0$。假设存在整数 $k \geq 2$ 和 $m \geq 1$ 使得