技术摘要：基于混合反馈的广义线性 Bandit 中最佳臂识别

问题表述

本文在混合反馈模型下，针对**广义线性 Bandit（GLBs）框架中的固定置信度最佳臂识别（BAI）**问题展开研究。

• 设定：学习者与 $K$ 个臂进行交互，每个臂关联一个已知特征向量 $x_i \in \mathbb{R}^d$ 和一个未知潜在参数 $\theta^*$。目标是以至少 $1-\delta$ 的概率识别出最大化期望奖励 $\mu_c(x_i^\top \theta^*)$ 的臂 $i^*$，同时使用最少的样本数量。
• 混合反馈：与依赖单一反馈类型的标准 Bandit 设定不同，学习者在每一轮 $t$ 可以选择两种模态之一：
  1. 绝对奖励：选择一个臂 $i$，并观察一个噪声奖励 $R_t \sim p_c(\cdot | x_i^\top \theta^*)$。
  2. 相对（对抗）反馈：选择一对臂 $(j, k)$，并观察一个二元偏好 $Y_t \in \{0, 1\}$，该偏好服从 $p_d(\cdot | (x_j - x_k)^\top \theta^*)$，其中 $Y_t=1$ 表示偏好 $j$。
• 统计模型：两种反馈类型均被建模为广义线性模型（GLM），它们共享相同的潜在参数 $\theta^*$，但可能具有不同的链接函数、离散度参数和曲率分布。目标是自适应地选择反馈模态以及具体要查询的臂或臂对，以最小化停止时间（或总成本）。

方法论

所提出的解决方案 HyTS-GLB（面向 GLB 的混合跟踪与停止算法），将统计推断与实验设计相结合，以应对反馈的异质性。

1. 统一置信序列

核心的统计贡献是一个基于似然比的置信序列，该序列统一了异质观测值。

• 似然比构建：作者将 Lee 等人 [2024] 的框架扩展至混合观测。他们定义了一个累积负对数似然 $L_t(\theta)$，该函数聚合了奖励损失和对抗损失。
• 椭球置信集：在自共轭性（链接函数的一种属性，确保三阶导数有界）的假设下，作者推导出了一个显式的椭球置信集 $E_t(\delta)$。
  • 该集合定义为 $\{ \theta : \|\theta - \hat{\theta}_t\|_{A_t}^2 \leq \beta_t(\delta) \}$，其中 $\hat{\theta}_t$ 是受约束的最大似然估计量（MLE）。
  • 矩阵 $A_t$ 是一个聚合信息矩阵，它结合了来自两种反馈模态的曲率信息，并根据其采样频率和特征几何结构进行加权。这使得算法能够将绝对反馈和相对反馈视为关于潜在参数的统一信息来源。

2. 混合跟踪与停止算法

基于置信集，作者提出了一种跟踪与停止策略：

• 极小化极大最优设计：该算法跟踪一个采样比例向量 $w$，该向量最小化所有臂对上的最坏情况置信宽度。具体而言，它求解一个极小化极大问题，以最小化 $\max_{i \neq \hat{i}^*_t} \|x_{\hat{i}^*_t, i}\|_{A(w, \hat{\theta}_t)^{-1}}^2$，其中 $\hat{i}^*_t$ 是当前经验最佳臂。
• 跟踪规则：学习者选择动作以匹配目标比例 $w^*(t)$，同时结合一个渐消失的强制探索机制，以确保信息矩阵保持非退化。
• 停止规则：当当前的经验最佳臂在置信集 $E_t(\delta)$ 内被证明优于所有竞争对手时，算法终止。

3. 成本感知扩展

该框架被扩展至成本感知设定，其中奖励查询和对抗查询具有不同的获取成本（$c_{reward}$ 与 $c_{dueling}$）。

• 该算法优化一个成本归一化设计向量 $p$（单位成本的采样强度），而非原始采样比例。
• 这使得学习者能够在信息增益与货币或计算成本之间进行权衡，自适应地偏向更具成本效益的模态。

主要贡献

1. 混合 GLM 公式化：本文在共享 GLM 参数化的框架下，构建了包含奖励和对抗反馈的纯探索问题。与无结构的混合模型不同，该方法利用共享的潜在结构在不同模态间传递信息，同时适应不同的似然函数和曲率。
2. 混合置信序列：作者开发了一个单一的、显式的椭球置信区域，该区域聚合了来自奖励和对抗通道的异质 Fisher 曲率。这统一了推断与停止过程，避免了协调独立置信集的需求。
3. 几何感知算法（HyTS-GLB）：他们提出了一种算法，在臂和臂对的联合动作空间上跟踪极小化极大最优设计。该算法被证明是 $\delta$-正确的，并提供了停止时间的高概率上界。
4. 理论保证：停止时间被证明与极小化极大特征时间 $T^*(\theta^*)$ 成比例，该时间捕捉了混合反馈的联合信息效率。成本感知变体在总获取成本上实现了类似的界。
5. 实证验证：实验表明，与单模态基线（仅奖励或仅对抗）相比，混合方法显著降低了样本复杂度。成本感知变体成功适应了非对称的查询成本。

结果与性能

• 样本效率：在具有逻辑回归观测模型的合成实验中，HyTS-GLB 在各种维度下始终优于基线方法（Rage-GLM, ReTS-GLB, DuelTS-GLB）。在大多数配置中，它实现了最小的平均停止时间，特别是在奖励和对抗反馈在不同方向上提供互补信息时。
• 成本适应：当反馈成本不对称时，成本感知变体通过将采样转向更便宜的模态而不牺牲正确性，从而降低了总成本。
• 复杂度分析：理论分析表明，样本复杂度由特征时间 $T^*(\theta^*)$ 决定。本文提供了具体示例，说明根据实例几何结构的不同，奖励或对抗反馈可能更具信息量，从而证明了混合算法能够动态适应这些条件，而不是固守单一模态。

意义与主张

本文声称提供了一个统一的统计与算法框架，用于解决具有混合反馈的广义线性 Bandit 中的固定置信度 BAI 问题。

• 统计整合：这项工作超越了算法融合（例如简单的消除法），实现了统计整合，将绝对反馈和相对反馈建模为共享潜在效用不同观测值。这通过利用共享参数结构，实现了更高效的数据利用。
• 处理异质性：所提出的置信序列成功应对了由异质似然函数和曲率分布带来的统计挑战，提供了一个单一的优化性证明，指导停止和分配决策。
• 实际相关性：该框架解决了现实世界场景（例如 RLHF、对话推荐系统）中的问题，在这些场景中，系统接收混合反馈（评分与成对偏好），且查询成本可能各不相同。
• 最优性的谦逊：作者承认，虽然其设计准则与信息论下界的局部二次松弛相一致，但有限时间保证涉及保守的常数和的对数因子。他们指出，由于 GLM 中 KL 散度的非线性，获得针对一般 GLM 的完全实例最优算法仍然是一个未解决的问题。

总之，本文确立了，当混合反馈通过具有自共轭置信序列的统一 GLM 框架进行处理时，在样本和成本效率方面可以严格优于单模态策略。