Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback¶
会议: NeurIPS 2026
arXiv: 2605.05745
OpenReview: https://openreview.net/forum?id=dSPIhAJKfj
领域: 强化学习
关键词: 最佳臂识别, 广义线性老虎机, 混合反馈, 对决老虎机, 跟踪与停止算法
一句话总结¶
本文针对广义线性老虎机中的固定置信度最佳臂识别问题，首次建立了统一融合单臂绝对奖励与双臂对决相对反馈的似然比自共轭置信椭球序列，并提出了跟踪极小极大最优实验设计的 HyTS-GLB 及成本感知扩展算法。
研究背景与动机¶
在大规模交互式学习系统（如结合人类反馈强化学习 RLHF 的大语言模型对齐与对话式推荐系统）中，智能体通常能够同时接触到异构的多模态用户反馈。其中，单臂绝对反馈（如具体评分、点击率或任务完成指标）提供关于单个动作的带噪绝对效用，而双臂相对反馈（如成对偏好比较）则揭示效用差值且对尺度平移天然不敏感。尽管这两种反馈模态均植根于底层的共享潜在偏好结构，但它们对应着截然不同的统计观测模型与特征曲率剖面。如何系统性地联合利用这两种异构且互补的反馈通道，是交互学习领域面临的关键理论难题。
以往老虎机与纯探索文献大多将不同反馈模态割裂研究。随机与线性老虎机聚焦于绝对奖励观测，而对决老虎机（Dueling Bandits）与偏好学习则仅假设能够获得成对比较；近期虽有工作开始探索混合反馈，但主要停留在启发式或交替淘汰等算法层面的简单融合，未能利用广义线性模型（GLM）在底层统计推断层面刻画共享潜在效用参数。此外，在非线性 GLM 结构下，统计不确定性不仅依赖于所选臂或臂对的特征，还高度依赖未知的潜在参数本身，这使得构建适用于自适应序列采样的紧致时变均匀置信集变得极其困难。
为了克服上述挑战，本文将绝对观测与相对观测统一建模为由共享潜在参数驱动但拥有独立连接函数与离散尺度的广义线性模型。核心 idea：利用自共轭性将异构似然比统计量解耦并聚合为显式信息矩阵置信椭球，进而提出跟踪联合动作空间上极小极大实验设计的 HyTS-GLB 算法，实现信息与成本驱动的自适应纯探索。
方法详解¶
整体框架¶
在混合广义线性老虎机（Hybrid GLB）的固定置信度最佳臂识别设定中，环境由紧致凸集 \(\Theta \subseteq \mathcal{B}^d(S)\) 内的未知真实参数 \(\bm{\theta}^\star \in \mathbb{R}^d\) 驱动，包含 \(K\) 个已知特征臂 \(\mathcal{X} = \{\bm{x}_i\}_{i=1}^K \subset \mathcal{B}^d(1)\)。在每个决策轮次 \(t\)，学习器可在联合动作空间 \(\mathcal{A} = \mathcal{K} \cup \mathcal{G}\) 中自适应选择动作 \(a_t\)：若选择单臂 \(a_t = i_t \in \mathcal{K}\)，则获得绝对奖励观测 \(R_t \sim p_{\mathrm{c}}(\cdot \mid \bm{x}_{i_t}^\top \bm{\theta}^\star)\)；若选择臂对 \(a_t = (j_t, k_t) \in \mathcal{G}\)，则获得指示偏好的相对二元观测 \(Y_t \sim p_{\mathrm{d}}(\cdot \mid (\bm{x}_{j_t} - \bm{x}_{k_t})^\top \bm{\theta}^\star)\)。
整个系统的运行流程包括：统计估计模块计算联合受约束最大似然估计（MLE）\(\hat{\bm{\theta}}_t\)；置信构建模块基于自共轭性合成加权曲率信息矩阵 \(\bm{A}_t\)，形成时变置信椭球 \(\mathcal{E}_t(\delta)\)；停止检验模块判定当前经验最优臂是否在最坏置信边界下均严格优于其余所有候选臂；若未达终止条件，则实验设计模块求解关于最窄分离边界的极小极大采样权重 \(\bm{w}^\star(t)\)，并通过确定性跟踪与消失受迫探索选择下一轮动作。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
In["联合动作空间 A = K ∪ G<br/>单臂特征 x_i 与差分特征 x_j - x_k"] --> MLE["统一受约束极大似然估计<br/>联合负对数似然损失 L_t(θ) 极小化"]
MLE --> CS["自共轭似然比置信椭球<br/>异构曲率融合矩阵 A_t 与时变半径 β_t(δ)"]
CS --> Stop{"高置信度消除判决<br/>对所有 j≠i* 是否满足下确界分离"}
Stop -->|满足条件| Out["推荐最优臂 i*<br/>保证 δ-正确性并安全终止"]
Stop -->|未满足| Minimax["极小极大最优实验设计<br/>最小化最坏区分方向置信宽度"]
Minimax --> Track["确定性追踪与受迫探索<br/>在线追踪分配与非退化激励保证"]
Track --> Act["执行混合反馈查询 a_t<br/>观测绝对奖励 R_t 或相对偏好 Y_t"]
Act --> MLE关键设计¶
1. 统一受约束极大似然估计：跨异构反馈信道的损失函数解耦与优化
由于绝对反馈与相对反馈各自遵循指数族分布，传统启发式统计方法往往分别拟合两个独立模型导致样本利用率低下。本文将第 \(t\) 轮前收集的观测历史按反馈模态划分为绝对奖励集合 \(\mathcal{C}_t = \{s \le t : a_s \in \mathcal{K}\}\) 与对决比较集合 \(\mathcal{D}_t = \{s \le t : a_s \in \mathcal{G}\}\)，定义累积负对数似然损失函数： $\(\mathcal{L}_t(\bm{\theta}) \triangleq \sum_{s \in \mathcal{C}_t} \frac{b_{\mathrm{c}}(\bm{x}_{a_s}^\top \bm{\theta}) - R_s \bm{x}_{a_s}^\top \bm{\theta}}{\zeta_{\mathrm{c}}(\varphi_{\mathrm{c}})} + \sum_{s \in \mathcal{D}_t} \frac{b_{\mathrm{d}}(\bm{x}_{a_s}^\top \bm{\theta}) - Y_s \bm{x}_{a_s}^\top \bm{\theta}}{\zeta_{\mathrm{d}}(\varphi_{\mathrm{d}})}\)$ 其中 \(b_{\mathrm{c}}, b_{\mathrm{d}}\) 为充分平滑且凸的对数配分函数，\(\zeta_{\mathrm{c}}, \zeta_{\mathrm{d}}\) 为已知离散尺度。通过在紧致凸参数集 \(\Theta\) 上求解 \(\hat{\bm{\theta}}_t = \arg\min_{\bm{\theta} \in \Theta} \mathcal{L}_t(\bm{\theta})\)，算法在单一优化目标下实现了跨模态信息的无偏融合。凸优化一阶最优性条件保证了对任意测试参数均有 \(\langle \nabla \mathcal{L}_t(\hat{\bm{\theta}}_t), \bm{\theta} - \hat{\bm{\theta}}_t \rangle \ge 0\)，为后续将似然比标量松弛至参数空间几何距离奠定了严格的数学基础。
2. 自共轭似然比置信椭球：非线性曲率的显式二次下界合成
固定置信度探索的核心瓶颈在于非线性广义线性模型的局部曲率随未知参数位置发生漂移。通过引入绝对信道常数 \(M_{\mathrm{c}}\) 与相对信道常数 \(M_{\mathrm{d}}\) 的自共轭假设（即 \(|\mu''(\eta)| \le M \mu'(\eta)\)），本文借助积分余项泰勒展开证明了累积损失增量可被单一正定矩阵严格控制：\(\mathcal{L}_t(\bm{\theta}) - \mathcal{L}_t(\hat{\bm{\theta}}_t) \ge \|\bm{\theta} - \hat{\bm{\theta}}_t\|_{\bm{A}_t}^2\)。由此导出的统一置信矩阵形式为： $\(\bm{A}_t \triangleq \sum_{s=1}^t \frac{\mu'_{m(a_s)}(\bm{x}_{a_s}^\top \hat{\bm{\theta}}_t)}{2(1 + S \rho_{a_s} M_{m(a_s)}) \zeta_{m(a_s)}(\varphi_{m(a_s)})} \bm{x}_{a_s} \bm{x}_{a_s}^\top\)$ 其中单臂动作尺度因子 \(\rho_a = 1\)，臂对差分动作尺度因子 \(\rho_a = 2\)。结合覆盖高概率经验利普希茨常数 \(L_t = \mathcal{O}(t)\) 的时变半径 \(\beta_t(\delta) = \mathcal{O}(\log(1/\delta) + d \log t)\)，构造出显式置信椭球 \(\mathcal{E}_t(\delta) = \{\bm{\theta} \in \mathbb{R}^d : \|\bm{\theta} - \hat{\bm{\theta}}_t\|_{\bm{A}_t}^2 \le \beta_t(\delta)\}\)。该构造不仅保证了全时段均匀覆盖概率至少为 \(1 - \delta\)，更将异构 Fisher 信息与几何特征直接转化为可以直接执行内积极值计算的椭球范数。
3. 极小极大最优实验设计：联合动作空间的置信宽度最小化
在确定终止判决前，采样策略必须尽可能快速地压低当前经验最优臂 \(\hat{i}_t^\star = \arg\max_{i \in \mathcal{K}} \bm{x}_i^\top \hat{\bm{\theta}}_t\) 与所有竞争臂 \(i \ne \hat{i}_t^\star\) 之间的最大区分不确定性。算法构建了关于单纯形向量 \(\bm{w} \in \Delta_{\mathcal{A}}\) 的极小极大设计目标： $\(\bm{w}^\star(t) = \arg\min_{\bm{w} \in \Delta_{\mathcal{A}}} \max_{i \ne \hat{i}_t^\star} \|\bm{x}_{\hat{i}_t^\star, i}\|_{\bm{A}(\bm{w}, \hat{\bm{\theta}}_t)^{-1}}^2\)$ 该准则在信息几何上紧密对应局部 KL 散度信息论下界的二次松弛。它使得算法在每一步不仅能够判断哪一对候选臂当前最难区分，而且能根据局部导数 \(\mu'(\cdot)\) 的饱和程度，在单臂直接测量与双臂差分测量之间自适应权衡，动态寻找在最瓶颈方向上信息增益最大的动作分配。
4. 确定性追踪与受迫探索：全局收敛性与非退化矩阵保证
为了将连续优化所得的最优分配 \(\bm{w}^\star(t)\) 转化为离散轮次的实际查询动作，同时避免经验设计陷入信息退化子空间，算法结合了确定性累积偏差追踪与衰减受迫探索机制。在普通轮次中以 \(1 - \epsilon_t\) 的概率选择累积分配赤字最大动作 \(a_t \in \arg\min_{a \in \mathcal{A}} (N_a^{\mathcal{T}}(t-1) - W_a^{\mathcal{T}}(t-1))\)，保证有限动作追踪偏差始终处于常数级有界区间内；同时以 \(\epsilon_t = t^{-\alpha}\)（\(\alpha \in (0,1)\)）的小概率在能够张成全空间的基底动作集 \(\mathcal{A}_0\) 上进行均匀受迫采样。该机制以渐近可忽略的样本开销确保了最小特征值 \(\lambda_{\min}(\bm{A}_t) \gtrsim t^\alpha\)，保证参数强一致收敛 \(\hat{\bm{\theta}}_t \to \bm{\theta}^\star\) 以及经验设计测度弱收敛至最优测度 \(\bm{w}^\star\)。
5. 成本感知扩展设计：单位获取成本下的样本效率归一化
在许多真实交互场景中，单臂打分与成对对决的采集成本高度不对称。扩展算法 Cost-aware-HyTS 引入已知正成本向量 \(\bm{c} \in \mathbb{R}_{>0}^{|\mathcal{A}|}\)，将优化问题重塑在满足加权约束 \(\langle \bm{c}, \bm{p} \rangle = 1\) 的成本归一化测度空间 \(\bm{p} \ge 0\) 上： $\(\bm{p}^\star(t) = \arg\min_{\bm{p} \ge 0 : \langle \bm{c}, \bm{p} \rangle = 1} \max_{i \ne \hat{i}_t^\star} \|\bm{x}_{\hat{i}_t^\star, i}\|_{\bm{A}(\bm{p}, \hat{\bm{\theta}}_t)^{-1}}^2\)$ 通过离散化追踪重构权重 \(\bar{\bm{p}}^\star(t) = \bm{p}^\star(t) / \sum_a p_a^\star(t)\)，算法自适应地向单位成本信息增益更高的模态发生倾斜，在保持相同 \(\delta\)-正确性置信椭球的同时，使得总成本界上界渐近匹配成本加权特征时间 \(T_{\mathrm{cost}}^\star(\bm{\theta}^\star) \log(1/\delta)\)。
损失函数 / 训练策略¶
算法以在线交互方式交替进行参数更新与设计求解。初始阶段执行预热轮次 \(E\) 使得基础信息矩阵正定。在每一轮中，利用一阶最优化方法求解受约束负对数似然损失函数极小值获得 \(\hat{\bm{\theta}}_t\)。置信停止判决条件为： $\(\forall j \ne \hat{i}_t^\star: \quad \langle \bm{x}_{\hat{i}_t^\star, j}, \hat{\bm{\theta}}_t \rangle \ge \sqrt{\beta_t(\delta)} \|\bm{x}_{\hat{i}_t^\star, j}\|_{\bm{A}_t^{-1}}\)$ 在未触发停止时，由于极小极大最优分配在大动作空间下存在计算负担，算法在实践中采用 Frank-Wolfe（条件梯度法）高效迭代逼近凸松弛解，从而在保证高精度信息跟踪的同时维持多项式级的单步计算复杂度。
实验关键数据¶
主实验¶
实验采用合成逻辑斯蒂观察模型（Logistic Likelihood，\(\mu_{\mathrm{c}}(\eta) = \mu_{\mathrm{d}}(\eta) = \sigma(\eta)\)），置信度设定为 \(\delta = 0.05\)，参数球半径 \(S = 5\)，真实参数取 \(\bm{\theta}^\star = (S - 1)\mathbf{1}/\sqrt{d}\)。臂集大小设置为 \(K = d + 1\)，维度 \(d \in \{2, 4, 6, 8, 10\}\)。对比基准包括针对逻辑斯蒂老虎机纯探索设计的 RageGLM、基于纯单臂绝对奖励的 ReTS-GLB、基于纯对决比较的 DuelTS-GLB 以及随机选择动作的混合基线 Random Hybrid（GLGapE 由于在仿真预算内未能终止未被列入最终统计）。评价指标为 10 次独立重复实验的平均停止步数（Mean Stopping Time \(\tau\)）。
| 特征维度 \(d\) (\(K=d+1\)) | 评估指标 | HyTS-GLB (本文) | DuelTS-GLB | ReTS-GLB | RageGLM | Random Hybrid | 相对优胜基准提升/表现 |
|---|---|---|---|---|---|---|---|
| \(d = 2\) (\(K = 3\)) | 平均停止时间 \(\tau\) | ~1.65 \(\times 10^4\) | ~1.45 \(\times 10^4\) | ~2.90 \(\times 10^4\) | ~4.80 \(\times 10^4\) | ~3.40 \(\times 10^4\) | 紧随最优对决基线，优于单模态奖励 |
| \(d = 4\) (\(K = 5\)) | 平均停止时间 \(\tau\) | ~2.85 \(\times 10^4\) | ~3.15 \(\times 10^4\) | ~6.40 \(\times 10^4\) | ~1.15 \(\times 10^5\) | ~6.80 \(\times 10^4\) | 显著超越所有基线 (最优) |
| \(d = 6\) (\(K = 7\)) | 平均停止时间 \(\tau\) | ~4.90 \(\times 10^4\) | ~5.30 \(\times 10^4\) | ~1.08 \(\times 10^5\) | ~2.10 \(\times 10^5\) | ~1.12 \(\times 10^5\) | 显著超越所有基线 (最优) |
| \(d = 8\) (\(K = 9\)) | 平均停止时间 \(\tau\) | ~7.80 \(\times 10^4\) | ~7.50 \(\times 10^4\) | ~1.65 \(\times 10^5\) | ~3.20 \(\times 10^5\) | ~1.70 \(\times 10^5\) | 保持与最优对决基线高度接近 |
| \(d = 10\) (\(K = 11\)) | 平均停止时间 \(\tau\) | ~1.10 \(\times 10^5\) | ~1.18 \(\times 10^5\) | ~2.35 \(\times 10^5\) | ~4.50 \(\times 10^5\) | ~2.40 \(\times 10^5\) | 高维下优势明显，全面领先 |
消融实验¶
消融实验深入评估了异质获取成本对算法总成本的影响，固定 \(K = 3, d = 2\)，设定总成本基准 \(C_{\mathrm{reward}} + C_{\mathrm{dueling}} = 2\)，并在不同的成本比值 \(C_{\mathrm{reward}} / C_{\mathrm{dueling}} \in \{1/3, 1/2, 1, 2, 3\}\) 下测试 Cost-aware-HyTS 与未考虑成本的标准 HyTS-GLB 的总消耗成本 \(B_\tau = \sum_s c_{a_s}\)。
| 成本配比 \(C_{\mathrm{reward}} / C_{\mathrm{dueling}}\) | 单项成本 \((C_{\mathrm{c}}, C_{\mathrm{d}})\) | Cost-aware-HyTS 总成本 | 标准 HyTS-GLB 总成本 | 相对成本节约 | 成本结构倾向分析 |
|---|---|---|---|---|---|
| 1 : 3 | (0.50, 1.50) | ~1.35 \(\times 10^4\) | ~1.72 \(\times 10^4\) | 21.5% 成本下降 | 大幅增加单臂奖励查询占比，规避高昂对决成本 |
| 1 : 2 | (0.67, 1.33) | ~1.48 \(\times 10^4\) | ~1.68 \(\times 10^4\) | 11.9% 成本下降 | 显著向奖励查询倾斜，缩减总开销 |
| 1 : 1 | (1.00, 1.00) | ~1.65 \(\times 10^4\) | ~1.65 \(\times 10^4\) | 0.0% (精确一致) | 退化为标准均等成本极小极大追踪设计 |
| 2 : 1 | (1.33, 0.67) | ~1.42 \(\times 10^4\) | ~1.60 \(\times 10^4\) | 11.3% 成本下降 | 转向低成本成对比较，降低昂贵单臂观测次数 |
| 3 : 1 | (1.50, 0.50) | ~1.28 \(\times 10^4\) | ~1.58 \(\times 10^4\) | 19.0% 成本下降 | 高度集中于对决反馈，以高频廉价比较替代绝对测量 |
关键发现¶
- 异质几何正交互补性：HyTS-GLB 在中高维（\(d=4,6,10\)）时表现最为突出，相较于纯单臂反馈基准 ReTS-GLB 采样效率提升达 50% 以上。这是因为对决反馈天然捕获了差分方向 \(\bm{x}_j - \bm{x}_k\) 的直接投影，而单臂反馈则更易确定正交坐标基底，混合采样能够在几何互补方向上共同加速椭球收缩。
- 参数尺度敏感性与曲率抗饱和：附录实验表明，当参数范数 \(S\) 从 2 增大到 5 时，逻辑斯蒂连接函数的导数极易进入两侧饱和区导致 Fisher 信息骤降。此时 HyTS-GLB 的优势进一步扩大，表明自适应混合设计能有效将采样导向曲率更高、信息量更大的观测渠道。
- 成本灵敏度验证：在成本不对称设定下，Cost-aware-HyTS 在两极成本比（1:3 与 3:1）时均能压低近 20% 的总开支，准确体现了单位成本信息最大化原理。
亮点与洞察¶
- 自共轭统合异构非线性似然：通过巧妙利用自共轭性常数放缩，将拥有不同连接函数、离散尺度的非线性损失增量统一归纳至单一正定信息矩阵 \(\bm{A}_t\) 下，避免了为不同模态分别维护碎片化置信集的繁琐几何求交。
- 理论下界的局部二次松弛桥梁：严格揭示了广义线性纯探索中的非线性 KL 散度信息论下界在局部展开后，其核矩阵形式与算法所跟踪的置信椭球极小极大实验设计高度契合，为极小极大准则提供了清晰的统计物理诠释。
- 即插即用的模块化扩展能力：算法解耦了置信区间构造与动作分配追踪。无论是将目标函数从样本步数推广至异质获取成本，还是未来替换为更加激进的局部鞍点优化设计，其底层时变覆盖引理与停止准则均可无缝复用。
局限与展望¶
- 计算复杂度随臂数二次增长：联合动作空间包含 \(|\mathcal{G}| = \mathcal{O}(K^2)\) 个候选臂对，在高维海量候选臂场景下，每轮调用 Frank-Wolfe 求解极小极大实验设计的计算开销较为显著，需引入剪枝或近似预筛选机制。
- 模型设定完美匹配假设：当前理论严格依赖于 GLM 观察模型的精确指定与紧致有界性假设。若用户偏好存在重尾噪声、战略偏差或非平稳漂移，置信序列的覆盖性质可能失效。
- 常数因子保守性：由于自共轭放缩引入了包含 \(S, M_{\mathrm{c}}, M_{\mathrm{d}}\) 的常数膨胀因子，停止时间的理论上界与信息论渐近最优界之间仍存在常数与对数阶差距，进一步收紧有限时间理论界仍是有待探索的开问题。
相关工作与启发¶
- vs Jedra and Proutiere (2020)：该工作确立了线性高斯老虎机上的渐近最优 Track-and-Stop 理论，但仅处理固定曲率的单臂奖励；本文将其推广至具有参数依赖型时变曲率且融合了双臂对决的广义线性混合架构。
- vs Jun et al. (2021) (RageGLM)：RageGLM 针对纯逻辑斯蒂模型设计了消除类探索算法，但未建立统一的似然比连续置信序列，且无法处理混合模态与异质成本权衡；本文提供了一般自共轭 GLM 下普适的凸几何置信椭球与极小极大追踪框架。
- vs Wang et al. (2025)：该工作在非结构化多臂老虎机中探讨了奖励与对决融合，主要在算法层面做回合消除；本文则在共享特征参数化的广义线性框架下从底层 Fisher 信息矩阵完成了统计融合。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次系统性提出结合绝对奖励与相对对决的广义线性老虎机固定置信度纯探索框架。
- 实验充分度: ⭐⭐⭐⭐☆ 涵盖了多维度合成实验、参数尺度敏感性、异质成本消融以及理论退化特例的严密数学分析。
- 写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰完备，从似然比置信序列到实验设计追踪的逻辑链条一气呵成。
- 价值: ⭐⭐⭐⭐⭐ 为解决 RLHF 人类偏好对齐数据收集与现代多源推荐系统中的异构反馈采样提供了坚实的算法理论支撑。