通过混合反馈在广义线性带臂中进行最佳臂识别

# 广义线性老虎机中基于混合反馈源的最佳臂识别

**来源**: https://arxiv.org/html/2605.05745  
**作者**: Qirun Zeng (香港城市大学计算机科学系, 中国香港特别行政区), Xuchuang Wang (马萨诸塞大学阿默斯特分校 Manning 信息与计算机科学学院, 美国), Jiayi Shen (中国科学技术大学管理学院, 中国安徽合肥), Xutong Liu (华盛顿大学计算机科学与系统系, 美国密苏里州圣路易斯), Fang Kong (南方科技大学计算机科学与技术学院, 中国广东深圳), Jinhang Zuo (香港城市大学计算机科学系)

###### 摘要

我们研究了广义线性老虎机（Generalized Linear Bandits）在混合反馈模型下的固定置信度最佳臂识别问题：在每一轮中，学习者可以查询单一臂的 $(i)$ 绝对奖励反馈，或者查询一对臂的 $(ii)$ 相对（dueling）反馈，两者均由广义线性模型（GLMs）控制。我们引入了一种基于似然比的置信序列，该序列统一了异构的广义线性观测，并在自协调（self-concordance）假设下生成了一个显式的椭球置信集。基于此置信集，我们提出了一种混合 Track-and-Stop 算法，该算法通过在臂和臂对的联合动作空间上跟踪极小极大最优设计来自适应地分配查询。我们证明了 $\delta$-正确性，并给出了停止时间的高概率上界。此外，我们将该框架扩展到一个考虑不同反馈模式之间异构获取成本的感知成本设置中。实证实验表明，所提出的算法在样本效率上显著优于基线方法。

## 1 引言

大规模交互式学习系统越来越依赖于异构的用户反馈。在现代对话式和推荐平台中，特别是通过基于人类反馈的强化学习（RLHF）训练的大语言模型（LLM）助手 \[Christiano et al., 2017\]; \[Ouyang et al., 2022\]，监督信号通常来自成对偏好，而绝对信号如评分、点击或任务完成指示器也可能可用。尽管这些反馈模式是由共享的潜在效用结构引起的，但它们对应着根本不同的统计观测模型：绝对反馈提供个体行动的噪声评估，而相对反馈传达对尺度偏移不变的比较信息。设计能够系统地利用这种异构但互补反馈的学习算法仍然是交互式学习中的一个核心挑战。

从理论角度来看，现有的老虎机模型大多孤立地处理不同的反馈模式。随机老虎机和线性老虎机专门关注基于奖励的观测，而决斗老虎机和基于偏好的学习框架仅假设可以访问成对比较 \[Yue and Joachims, 2011\]; \[Yue et al., 2012\]; \[Sui et al., 2018\]。最近的工作开始通过研究混合反馈老虎机来弥合这一差距 \[Wang et al., 2025\]。然而，现有方法主要通过联合消除过程在算法层面结合奖励和决斗反馈。因此，它们并未在统一的统计推理框架内充分利用这两种模式底层共享的潜在结构。

从算法融合转向统计整合的一种自然方式是将绝对和相对反馈建模为共享潜在效用的不同观测。广义线性老虎机（GLBs）提供了这样的框架：绝对观测提供关于个体臂效用的噪声非线性反馈，而决斗观测提供关于效用差异的噪声非线性反馈。因此，这两种模式通过不同的观测通道为同一个潜在参数提供信息。这激发了我们对广义线性结构下具有混合反馈的固定置信度最佳臂识别（BAI）的研究，其目标是在高置信度下识别最佳臂，同时在绝对和相对查询之间进行选择。

解决这个问题不仅仅是简单地组合两个反馈通道，还引入了几个新的挑战。首先，奖励和决斗反馈携带异构信息：奖励查询观测个体臂效用，而决斗查询观测效用差异。它们不同的非线性似然和曲率轮廓使得简单的聚合在统计上效率低下。其次，在广义线性结构下，固定置信度推断更加困难，因为不确定性既依赖于未知的潜在参数，也依赖于查询的臂或臂对。这 complicates 为自适应采样和停止构建时间均匀置信区域的过程。第三，探索必须在动作和反馈模式上进行联合优化。学习者必须决定查询哪些臂或臂对，何时使用绝对或相对反馈，以及如何考虑潜在异构的获取成本。

综上所述，这些挑战需要一个统一的推理、停止和分配框架，以估计共享的潜在效用，认证最佳臂，并在纯探索期间自适应地平衡绝对和相对反馈。

**表 1**: 不同反馈模型和结构假设下固定置信度 BAI 的比较。
$C_{\text{reward}}$ 和 $C_{\text{dueling}}$ 分别表示奖励和决斗反馈的获取成本，$\emptyset$ 表示不可用。
† Opt. 表示算法是否在日志因子范围内匹配显示的特征时间。对于我们的混合行，这指的是置信宽度设计准则；附录讨论了其与一般 GLM 局部信息论下界松弛的关系。
‡ $T^\star_{a,b}(\bm{\theta}^\star)$ 表示成本 $(a,b)$ 下的相关特征时间；在我们的混合行中，它是极小极大置信宽度特征时间。$T'(\cdot)$ 和 $T''(\cdot)$ 表示先前工作中使用的有限时间复杂度度量。我们将特征时间的详细讨论和精确定义推迟到附录。

### 1.1 我们的贡献

我们研究了广义线性老虎机在允许奖励和决斗查询的混合反馈模型下的固定置信度 BAI。表 1 总结了代表性的 BAI 结果，并突出了本研究解决的差距。我们的主要贡献总结如下：

*   **混合 GLM BAI  formulation**: 我们在共享 GLM 参数化下制定了具有奖励和决斗反馈的结构化纯探索。与无结构的混合老虎机模型 \[Wang et al., 2025\] 不同，此设置通过潜在参数传输信息，同时允许两种模式具有不同的似然和曲率。
*   **混合置信序列**: 我们将自协调 GLM 的基于似然比的置信序列扩展到混合观测。尽管奖励和决斗反馈诱发了异构似然，但生成的置信区域具有单一的显式椭球形式，从而实现了统一推理和固定置信度停止。
*   **几何感知 Track-and-Stop**: 基于这些置信集，我们设计了 HyTS-GLB，这是一种 Track-and-Stop 风格的算法，它在臂和臂对的联合查询空间上跟踪插值极小极大设计。我们证明了 $\delta$-正确性和高概率停止时间保证，并进一步将分配规则与局部极小极大实验设计下界联系起来。
*   **感知成本扩展**: 我们将 HyTS-GLB 扩展到异构获取成本，并提供总成本的高概率保证。这使得学习者能够在奖励和决斗查询之间权衡信息和成本。
*   **实证验证**: 我们进行了实验，显示混合反馈相对于单模态基线减少了样本复杂度，而感知成本变体进一步适应了模态间不对称的查询成本。

综上所述，这些贡献为广义线性老虎机中具有混合反馈的固定置信度最佳臂识别提供了一个统一的统计和算法框架。由于篇幅限制，所有详细证明都推迟到附录中。

### 1.2 相关工作

**广义线性老虎机**。GLMs \[McCullagh, 2019\] 对自然参数为 $\bm{x}^\top \bm{\theta}^\star$ 且均值为 $\mu(\bm{x}^\top \bm{\theta}^\star)$ 的指数族观测进行建模。Filippi et al. \[2010\] 引入了基于 GLM 的结构化老虎机，随后有关于在自协调等假设下的遗憾和推断的工作 \[Russo et al., 2021\]。Lee et al. \[2024\] 开发了针对自协调 GLM 的基于似然比的置信序列，产生了凸且数值紧密的置信区域。我们通过为混合奖励-决斗反馈开发置信序列超越了 Lee et al. \[2024\]，其中自适应查询可能来自不同的 GLM 通道。这需要单个置信证书来聚合跨模态的异构 Fisher 曲率和特征几何，这是先前单通道 GLM 分析中不存在的设置。此外，Kirschner et al. \[2025\]; Clerico et al. \[2025\] 也为 GLM 构建了类似的置信序列。

**最佳臂识别和 Track-and-Stop**。最佳臂识别在随机和线性老虎机中得到了广泛研究 \[Bubeck et al., 2009\]; \[Audibert and Bubeck, 2010\]; \[Soare et al., 2014\]; \[Jourdan and Degenne, 2022\]; \[Shao and Fang, 2025\]。Kaufmann et al. \[2016\] 建立了多臂老虎机的一般固定置信度下界，并提出了 Track-and-Stop，其渐近达到该下界。对于线性老虎机，Soare \[2015\] 推导了实例依赖的下界，Jedra and Proutiere \[2020\] 给出了匹配的算法。Degenne et al. \[2020\] 表明迭代鞍点求解器可以为结构化老虎机设计渐近最优的 BAI 算法。对于 GLBs，Kazerouni and Wein \[2021\] 研究了 $(\epsilon, \delta)$-PAC BAI 并提供了相应的样本复杂度保证。

**相对和混合反馈**。相对（决斗）反馈在老虎机学习中得到了广泛研究，特别是在决斗老虎机和基于偏好的学习中 \[Yue and Joachims, 2011\]; \[Yue et al., 2012\]; \[Sui et al., 2018\]。它在实践中也很有吸引力，因为在对话式推荐中，相对反馈比绝对奖励更容易获取 \[Zhang et al., 2020\]; \[Yang et al., 2024\]。最相关的是，Wang et al. \[2025\] 研究了具有奖励和决斗反馈的随机老虎机，并提出了基于消除和分解的遗憾最小化算法，表明即使没有结构，混合反馈也有帮助。我们则研究共享 GLM 结构下的固定置信度 BAI，这需要时间均匀的置信序列、基于置信的停止以及基于臂和臂对的设计分配。He et al. \[2024\] 也探索了多臂老虎机、决斗老虎机和具有离线数据的老虎机的相关混合设置。

## 2 问题 formulation

**广义线性模型**。我们首先介绍奖励和决斗反馈底层的广义线性模型 \[McCullagh, 2019\]。令 $r \in \mathbb{R}$ 表示一个通用标量观测。在 GLM 中，给定标量参数 $\eta \in \mathbb{R}$，$r$ 的条件分布属于指数族，并由下式指定：

$$
p(r \mid \eta) = \exp\left( \frac{r\eta - b(\eta)}{\zeta(\varphi)} + c(r, \varphi) \right), \quad (1)
$$

其中 $\eta$ 是规范（自然）参数，$\varphi$ 是色散参数，$b(\cdot)$ 是对数分区函数，$c(r, \varphi)$ 是基准测度。我们使用 $p(r \mid \eta)$ 表示给定 $\eta$ 时 $r$ 的条件概率密度（或质量）函数。GLM 的一个基本属性是 $r$ 的条件均值由 $\mathbb{E}[r \mid \eta] = b'(\eta) \triangleq \mu(\eta)$ 给出，其中 $\mu(\cdot)$ 是均值函数（链接函数）。许多常见的观测模型，包括高斯、泊松和伯努利分布，都属于这一框架。

**混合广义线性老虎机**。我们考虑一个具有 $K$ 个臂的随机决策问题，索引为 $\mathcal{K} \triangleq \{1, 2, \dots, K\}$。每个臂 $i \in \mathcal{K}$ 关联一个已知特征向量 $\bm{x}_i \in \mathbb{R}^d$，环境由未知参数 $\bm{\theta}^\star \in \mathbb{R}^d$ 控制。我们假设臂集 $\mathcal{K}$ 张成 $\mathbb{R}^d$。学习者与环境顺序交互，可以通过两种不同的反馈模式获取信息。

在每一轮 $t$，学习者选择 *奖励查询* 或 *决斗查询*。在前者中，它选择 $i_t \in \mathcal{K}$ 并观测 $R_t \sim p_{\text{c}}(\cdot \mid \bm{x}_{i_t}^\top \bm{\theta}^\star)$。在后者中，它选择 $(j_t, k_t) \in \mathcal{G} \triangleq \{(j, k) \in \mathcal{K}^2 : j < k\}$ 并观测二元结果 $D_t \in \{0, 1\}$，其分布由 $\mathbb{P}(D_t = 1) = \mu(\bm{x}_{j_t}^\top \bm{\theta}^\star - \bm{x}_{k_t}^\top \bm{\theta}^\star)$ 给出。

**固定置信度最佳臂识别**。目标是识别最佳臂 $i^\star = \arg\max_{i \in \mathcal{K}} \mu(\bm{x}_i^\top \bm{\theta}^\star)$，并在以概率至少 $1-\delta$ 停止时输出正确的臂。我们定义置信集 $\mathcal{C}_t \subseteq \mathbb{R}^d$，使得 $\mathbb{P}(\forall t, \bm{\theta}^\star \in \mathcal{C}_t) \geq 1-\delta$。当 $\mathcal{C}_t$ 足够小以唯一确定最佳臂时，算法停止。

**初始化与探索**。为确保初始信息，我们假设在时间 $t=0$ 时，学习者对一组初始动作 $\mathcal{A}_0$ 进行初始化查询，使得 $\lambda_{\min}\left( \sum_{a \in \mathcal{A}_0} \bm{x}_a \bm{x}_a^\top \right) > 0$，其中 $\lambda_{\min}(\cdot)$ 表示最小特征值。令 $\pi_0$ 表示支持在 $\mathcal{A}_0$ 上的概率分布（例如，均匀分布）。令 $\mathcal{T}_t$ 为截至时间 $t$ 的跟踪轮次集合，令 $\bm{N}^{\mathcal{T}}(t)$ 和 $\bm{W}^{\mathcal{T}}(t)$ 表示相应的拉动计数和累积目标质量。在每一轮中，$a_t \in \begin{cases} \argmin_{a \in \mathcal{A}} \left( N^{\mathcal{T}}_a(t-1) - W^{\mathcal{T}}_a(t-1) \right), & \text{w.p. } 1-\epsilon_t, \\ a \sim \pi_0, & \text{w.p. } \epsilon_t, \end{cases}$