有限适应性下的上下文Slate GLM Bandits

###### 摘要 我们研究了在有限自适应条件下的上下文面板赌博机问题，其奖励服从广义线性模型。在每一轮中，学习器被提供 N 个物品集合，每个物品由一个 d 维特征向量表示。学习器通过从每个集合中选择一个物品构建一个面板；由此产生的面板产生一个从广义线性模型（GLM）采样的标量奖励。我们提出了两种有限自适应设置下的算法：(a) 分批 和 (b) 低频切换。对于分批设置，我们提出了 B-SlateGLinCB，它将时间范围划分为 O(log log T) 个批次，使得每个批次的策略仅依赖于之前批次的数据。对于低频切换设置，我们提出了 RS-SlateGLinCB，它仅自适应地进行 O(N d log T) 次参数更新。在物品序列的多样性假设下，我们证明了 B-SlateGLinCB 和 RS-SlateGLinCB 分别实现了 O(N d^{3/2} √T) 和 O(N d √T) 的遗憾界。值得注意的是，这两个界都与非线性参数 κ 无关，而该参数通常用于缩放 GLM 赌博机算法的遗憾值。我们的算法计算效率高，尽管有 2^{Ω(N)} 种可能的面板，但每轮仅需 poly(N) 时间。仿真表明，我们的算法在有限自适应设置下优于现有基线，并且与完全自适应的最先进算法 Slate-GLM-OFU 相比具有竞争力。值得注意的是，一个稍作修改的 B-SlateGLinCB 在经验上与这个基线相匹配。最后，我们在语言模型的实际上下文示例选择任务中展示了强大的性能。

目录 ## 1 引言 ## 1.1 我们的贡献 ## 1.2 相关工作 ## 2 符号与问题设定 ## 2.1 上下文面板赌博机 ## 2.2 广义线性模型（GLM） ## 2.3 有限自适应下的上下文面板赌博机 ## 1 引言 在线面板赌博机框架建模了序贯决策过程，其中学习器必须在每一轮中选择一个物品面板。面板由从多个槽位中各选一个物品构成，每个槽位拥有一个不同的、可能动态变化的候选物品池。选择后，学习器观察到整个面板的单一奖励（即赌博机反馈）。学习器的目标是设计一个选择策略，以最大化累积奖励，或等价地，最小化在 T 轮时间范围上的累积遗憾。该框架非常适合许多实际应用，例如登陆页面优化（其中选择页面组件以最大化转化率[14 (https://arxiv.org/html/2606.31449#bib.bib21)]）以及动态广告创意优化（其中广告从各种元素自动组装而成[5 (https://arxiv.org/html/2606.31449#bib.bib22)]）。在线面板赌博机的广泛应用已促使其在各种设置下得到广泛研究。当每个槽位的物品集合在整个时间范围内保持不变，并且提供半赌博机反馈（即面板内单个物品级别的奖励）时，高效且低遗憾的算法是众所周知的[15 (https://arxiv.org/html/2606.31449#bib.bib1),26 (https://arxiv.org/html/2606.31449#bib.bib3)]。最近，[7 (https://arxiv.org/html/2606.31449#bib.bib2)] 针对固定物品集场景提出了一种高效的汤普森采样方法，通过将相同的面板级奖励归属于所选面板中的所有物品来适应赌博机反馈。随后，[12 (https://arxiv.org/html/2606.31449#bib.bib5)] 探索了随机上下文设置，其特点是物品集合随时间随机变化，并利用了来自逻辑模型的赌博机反馈。他们提出的算法 Slate-GLM-OFU 通过对每个槽位进行乐观选择过程，高效地遍历了指数级大的候选面板空间。该算法在所选物品序列满足“多样性”假设的条件下实现了最优遗憾，从而在带赌博机反馈的上下文逻辑面板赌博机问题上取得了强大的理论和实证性能。

尽管取得了这些算法进展，但在实践中部署这些方法仍面临关键挑战。网络规模的应用，如在线广告和实时推荐，要求赌博机算法在有限自适应条件下运行。文献中研究的两种流行的有限自适应设置是：(a) 分批——算法必须将时间范围 {1,...,T} 划分为极少的区间（批次），并且在一个批次内的策略只能依赖于之前批次的观察结果（所选面板和获得的奖励）；(b) 低频切换——算法自适应地（且罕见地）决定何时更新其对奖励参数的估计。虽然这两种设置都通过减少参数估计次数带来了实际的效率提升，但分批设置还支持并行化，即批次内的各轮可以独立执行，从而显著提高吞吐量。受这些挑战的驱动，我们在这两种有限自适应设置下解决了在线上下文面板赌博机问题。此外，我们假设环境为所选面板提供单一奖励（赌博机反馈），该奖励由带有未知参数的广义线性模型（GLM）生成。我们在此总结我们的贡献。 ### 1.1 我们的贡献 首先，在第3节 (https://arxiv.org/html/2606.31449#S3) 中，我们提出了 B-SlateGLinCB（算法1 (https://arxiv.org/html/2606.31449#alg1)），一种针对具有 GLM 奖励的上下文面板赌博机问题的分批算法，该算法在 O(log log T) 个批次上运行。我们证明，如果物品集合是随机选择的，那么在 T 轮结束时，在常见的多样性假设（假设 2.1 (https://arxiv.org/html/2606.31449#S2.Thmassumption1)）下，B-SlateGLinCB 产生的遗憾为 Õ(N d^{3/2} √T)，其中每个物品由 d 维特征向量表示。在附录 B (https://arxiv.org/html/2606.31449#A2) 的算法3 (https://arxiv.org/html/2606.31449#alg3) 中，我们还展示了一种使用分布最优设计[27 (https://arxiv.org/html/2606.31449#bib.bib6)]的替代方法，并获得了 Õ(N d √T min{√d, √N}) 的遗憾保证。接下来，在第4节 (https://arxiv.org/html/2606.31449#S4) 中，我们提出了 RS-SlateGLinCB（算法2 (https://arxiv.org/html/2606.31449#alg2)），一种针对具有 GLM 奖励的上下文面板赌博机问题的低频切换算法，该算法仅估计参数 O(N d log T) 次。我们证明，在 T 轮结束时，对于对抗性选择的物品集合，在相同的多样性假设下，RS-SlateGLinCB 产生了 O(N d √T) 的遗憾，与 Slate-GLM-OFU（算法1，[12 (https://arxiv.org/html/2606.31449#bib.bib5)]）的遗憾界相匹配，而 Slate-GLM-OFU 在所有 T 轮都估计参数，即不受有限自适应约束。我们两个算法的一个关键特征是每轮的效率。它们通过独立地选择各槽位的物品，实现了每轮 poly(N) 的时间复杂度。这样做避免了遍历 2^{Ω(N)} 个可能面板的集合，使得它们在 N 较大时实际可行。最后，在第5节 (https://arxiv.org/html/2606.31449#S5) 中，在不同的实验设置下，我们凭经验证明了我们的两个算法都实现了亚线性遗憾，显著优于其他有限自适应基线，并且 RS-SlateGLinCB 与完全自适应算法 Slate-GLM-OFU 具有很强的竞争力。我们还提出了 B-SlateGLinCB+，一种对 B-SlateGLinCB 稍作修改的分批算法，并表明其遗憾与 Slate-GLM-OFU 相匹配。使用 B-SlateGLinCB+，我们实现了语言模型上基于示例选择的提示微调。我们展示了在二分类任务中的强大性能，并表明我们的性能与 Slate-GLM-OFU 相匹配。 ### 1.2 相关工作 面板赌博机：由于在推荐系统和广告等实际应用中的相关性，面板赌博机最近受到了相当大的关注[5 (https://arxiv.org/html/2606.31449#bib.bib22),14 (https://arxiv.org/html/2606.31449#bib.bib21)]。然而，许多这些工作缺乏严谨的理论基础，这一方面已在另一条研究线中进行了探索[31 (https://arxiv.org/html/2606.31449#bib.bib19),15 (https://arxiv.org/html/2606.31449#bib.bib1),26 (https://arxiv.org/html/2606.31449#bib.bib3),18 (https://arxiv.org/html/2606.31449#bib.bib20),7 (https://arxiv.org/html/2606.31449#bib.bib2),12 (https://arxiv.org/html/2606.31449#bib.bib5)]。虽然其中一些工作[31 (https://arxiv.org/html/2606.31449#bib.bib19),18 (https://arxiv.org/html/2606.31449#bib.bib20),26 (https://arxiv.org/html/2606.31449#bib.bib3),15 (https://arxiv.org/html/2606.31449#bib.bib1)]假设半赌博机反馈（即面板中每个所选物品都有一个奖励），但最近的努力如[7 (https://arxiv.org/html/2606.31449#bib.bib2)]和[12 (https://arxiv.org/html/2606.31449#bib.bib5)]解决了具有挑战性的面板级赌博机反馈场景。特别地，[7 (https://arxiv.org/html/2606.31449#bib.bib2)]使用一种基于启发式的方法将赌博机反馈归因于每个槽位，而[12 (https://arxiv.org/html/2606.31449#bib.bib5)]将选择规则分解为槽位级选择规则，使其算法能够避免遍历指数大小的候选面板集合，同时仍获得最优遗憾保证。然而，这些算法在每一轮都更新其参数，因此不易适应有限自适应设置。

有限自适应：最近，分批和低频切换的有限自适应设置引起了极大的兴趣。在多臂赌博机设置中，一些工作研究了分批的优势[3 (https://arxiv.org/html/2606.31449#bib.bib32),24 (https://arxiv.org/html/2606.31449#bib.bib33),11 (https://arxiv.org/html/2606.31449#bib.bib9)]。随后，[27 (https://arxiv.org/html/2606.31449#bib.bib6)]提出了针对上下文线性赌博机的分批算法，通过引入分布最优设计，并使用它们来指导和确定策略更新。基于这些思想，最近的工作探索了针对更复杂奖励模型的分批算法，包括 GLM[28 (https://arxiv.org/html/2606.31449#bib.bib4)] 和多项逻辑（MNL）模型[21 (https://arxiv.org/html/2606.31449#bib.bib8)]。上下文线性赌博机的低频切换设置由[1 (https://arxiv.org/html/2606.31449#bib.bib23)]引入，此后也在其他奖励模型中得到研究[28 (https://arxiv.org/html/2606.31449#bib.bib4),21 (https://arxiv.org/html/2606.31449#bib.bib8)]。然而，这些算法不容易扩展到面板赌博机设置，其中组合动作空间和结构化反馈引入了之前分批赌博机文献中未解决的独特挑战。 ## 2 符号与问题设定 在本节中，我们定义一些通用符号并详细描述问题设定。我们将集合 {1,...,N} 和 {m,...,N} 分别表示为 [N] 和 [m,N]。除非另有说明，所有向量、矩阵和集合分别使用粗体小写、粗体大写和花体大写字母表示。如果一个矩阵 A 的所有特征值非负，则称其为半正定矩阵（p.s.d），记作 A ⪰ 0。我们定义向量 x 关于半正定矩阵 A 的范数为 ∥x∥_A = √(x^⊤ A x)。我们使用 P 和 E 分别表示概率和期望。对于任意向量 x = (x^1_1, ..., x^1_d, ..., x^N_1, ... x^N_d) ∈ ℝ^{Nd}，x^i = (x^i_1, ..., x^i_d) ∈ ℝ^d 表示 x 的第 i 个块。最后，我们使用 Õ(·) 来抑制多对数因子。 ### 2.1 上下文面板赌博机 令 T ∈ ℕ 表示学习器与环境之间的总交互轮数。在上下文面板赌博机问题中，在每一轮 t ∈ [T] 中，学习器被提供 N 个物品集合 X_t^1, ..., X_t^N ⊂ ℝ^{Nd}。对于每个 i ∈ [N]，学习器选择一个物品 x_t^i ∈ X_t^i，从而构建一个面板 x = (x_t^1, ..., x_t^N) ∈ X_t := X_t^1 × ... × X_t^N。我们说物品 x_t^i 被用在面板的第 i 个“槽位”。然后环境向她揭示一个标量奖励 r_t(x_t)。学习器的目标是最小化其累积遗憾 R(T)，定义为， R(T) = E[ ∑_{t∈[T]} max_{x∈X_t} r_t(x) - r_t(x_t) ], (1) 其中期望是关于奖励的随机性。 ### 2.2 广义线性模型（GLM） 我们遵循[28 (https://arxiv.org/html/2606.31449#bib.bib4)]中定义2.1提供的 GLM 定义。令 r ∈ ℝ 是一个随机变量，x ∈ ℝ^{Nd} 是欧几里得空间中的一个随机向量。我们说 r(x) 是从一个 GLM 中采样的，如果条件随机变量 r | x 按照指数分布分布，即， P_{θ^⋆}(r | x) = exp( r·(x^⊤ θ^⋆) - b(x^⊤ θ^⋆) + c(r) )。这里 θ^⋆ ∈ ℝ^{Nd} 参数化了密度函数。此外，遵循[28 (https://arxiv.org/html/2606.31449#bib.bib4)]，我们假设 b 是二次可微的，假设 ḃ 是单调的，并且 r ∈ [0, R] 几乎必然成立，其中 R ∈ ℝ 已知。我们将连接函数 μ 定义为 μ(x_t^⊤ θ^⋆) = E[r_t | x_t] = ḃ(x_t^⊤ θ^⋆)。因此，μ 是单调的，并且进一步，遵循[10 (https://arxiv.org/html/2606.31449#bib.bib10)]，我们假设它是 L_μ-Lipschitz 的。GLM 的一个重要性质是*自协调*性质[28 (https://arxiv.org/html/2606.31449#bib.bib4)]，即对于支持在 [0, R] 上的 GLM，有 |μ̈(z)| ≤ R μ̇(z) ∀ z ∈ ℝ。 ### 2.3 有限自适应下的上下文面板赌博机 在有限自适应设置中，学习器被限制进行 M 次策略更新。我们的目标是解决由未知参数向量 θ^⋆ 参数化的具有 GLM 奖励的上下文赌博机问题。