Stochastic Matching Bandits with Rare Optimization Updates¶
会议: NeurIPS 2026
arXiv: 2509.04194
论文: https://arxiv.org/abs/2509.04194
领域: 强化学习
关键词: 多臂老虎机, 随机匹配, 多项Logit模型, 批次学习, 组合优化
一句话总结¶
针对多臂老虎机中带有非线性多项Logit（MNL）选择偏好的双边随机匹配收益最大化问题，本文提出基于分批淘汰机制与G-最优设计的B-SMB及无曲率先验的B-SMB+算法，仅需 \(\Theta(\log\log T)\) 次昂贵的NP-hard组合优化更新即可达到 \(\widetilde{\mathcal{O}}(\sqrt{T})\) 次线性遗憾。
研究背景与动机¶
在线双边匹配市场（如网约车派单、在线招聘和众包平台）的核心目标是撮合双边资源并最大化平台累积收益。传统的在线二分匹配理论大多关注确定性到达与匹配数量最大化，忽视了用户对候选对象的潜在偏好与收益反馈；而近年兴起的稳定匹配老虎机（Stable Matching Bandits）虽然引入了在线学习，但普遍假设接收方按照已知且固定的偏好序确定性地接受候选者，且着眼于系统稳定性（如消除阻塞对）。在网约车等实际平台中，司机面对分配的多个订单往往依据其潜在未知的效用函数以概率方式做出接受决策，促使系统建模从“确定性稳定匹配”转向“随机选择下的全系统期望收益最大化”。
为了刻画这一现实行为，将离散选择理论中的多项Logit（MNL）模型引入多臂老虎机框架成为自然选择。然而，不同于经典单品类MNL老虎机仅需在每个时间步挑选一个商品集合（存在多项式时间动态规划或贪心算法），随机匹配老虎机（SMB）要求同时为 \(K\) 个手臂分别分配互不相交的候选代理子集。这种跨手臂的分配耦合与MNL非线性概率结构交织在一起，使得每一轮求解最优匹配集合成为一个强NP-hard组合优化问题，在穷举搜索下的单轮复杂度可达 \(\mathcal{O}(K^N)\)。若采用标准的逐轮乐观策略（OFU），整个生命周期内求解该组合优化的总计算代价将随时间跨度 \(T\) 线性爆炸（\(\mathcal{O}(T K^N)\)），在实际生产系统中完全不可行。
本文的核心矛盾在于：如何在保持 \(\widetilde{\mathcal{O}}(\sqrt{T})\) 次线性最优遗憾（No-Regret）的同时，大幅压缩调用高昂NP-hard组合优化的频次。核心 idea：通过几何膨胀的批次时间调度将决策更新严格限制在 \(\Theta(\log\log T)\) 阶极稀疏批次边界，并结合基于收益置信界的多项式候选淘汰机制与自适应G-最优实验设计，在非线性偏好耦合下实现计算复杂度与遗憾界的双重最优平衡。
方法详解¶
整体框架¶
本文提出的随机匹配老虎机（SMB）在双边包含 \(N\) 个代理与 \(K\) 个手臂。每个代理 \(n\) 具有已知特征向量 \(x_n \in \mathbb{R}^d\)，每个手臂 \(k\) 对应潜在未知偏好参数 \(\theta_k \in \mathbb{R}^d\)。在每轮 \(t \in [T]\) 中，算法为每个手臂分配至多 \(L\) 个代理的互斥集合 \(S_{k,t}\)。手臂 \(k\) 依据MNL模型概率 \(p(n|S_{k,t}, \theta_k) = \frac{\exp(x_n^\top \theta_k)}{1 + \sum_{m \in S_{k,t}} \exp(x_m^\top \theta_k)}\) 随机接受至多一名代理（或以剩余概率选择外部选项 \(n_0\) 并获得0收益），成功匹配则产生已知奖励 \(w_{n,k} \in [0,1]\)。
针对该问题，作者设计了分批随机匹配老虎机算法（B-SMB及其改进版B-SMB+）。算法在进入在线阶段前首先对特征矩阵执行截断SVD降维，消除冗余特征维度；随后进入以双对数频次更新的批次迭代中。在每个批次内，算法仅在批次起始点执行一次昂贵的参数估计、收益置信区间构建、劣质匹配淘汰以及实验设计分布求解，在批次内部的连续时间步内则固定匹配集合执行静态探索与收益积累。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["特征矩阵预处理 SVD<br/>投影至 r 维子空间 zn = Ur^T xn"] --> B["批次初始参数估计<br/>负对数似然极大似然估计 MLE"]
B --> C["收益置信界构建与代表性组合生成<br/>计算 UCB/LCB 并构建代表性候选分配"]
C --> D["劣质匹配淘汰机制<br/>排除全局收益置信上界低于下界的代理-手臂对"]
D --> E["G-最优实验设计采样<br/>Frank-Wolfe 求解最小包围椭球最优探索权重"]
E --> F["批次内确定性调度探索<br/>在 T_tau 轮次内冻结匹配分配并收集反馈"]
F -->|批次轮次推进 T_tau+1 = eta_T sqrt T_tau| G{"是否达到时间跨度 T"}
G -->|未达到| B
G -->|已达到| H["结束交互，输出全生命周期匹配策略"]关键设计¶
1. 特征空间SVD投影预处理：消除多余维度与隐式正则化
标准上下文老虎机往往依赖协方差矩阵的正定性或严格的特征多样性假设。若原始特征维度 \(d\) 较高且存在共线性，MLE估计器的海森矩阵极易退化。针对这一痛点，算法在离线阶段对代理特征矩阵 \(X = [x_1, \dots, x_N] \in \mathbb{R}^{d \times N}\) 计算奇异值分解（SVD）\(X = U \Sigma V^\top\)，提取非零奇异值对应的左奇异向量矩阵 \(U_r \in \mathbb{R}^{d \times r}\)（其中 \(r = \mathrm{rank}(X) \leq d\)），将特征向量与隐式偏好参数严格投影至 \(r\) 维子空间： $\(z_n = U_r^\top x_n \in \mathbb{R}^r, \quad \theta_k^* = U_r^\top \theta_k \in \mathbb{R}^r\)$ 由于 \(x_n\) 本身落在 \(U_r\) 张成的子空间中，严格保证了内积不变性 \(x_n^\top \theta_k = z_n^\top \theta_k^*\)。该设计无需预知真实秩 \(r\)，不仅直接将后续优化与矩阵逆运算的复杂度降至 \(r\) 维，而且为初始预热阶段提供了天然的特征正则化保证。
2. 收益级置信界与代表性分配淘汰：规避组合爆炸的统计筛选
在MNL模型中，单个代理效用的置信下界并不必然对应于集合期望收益的下界（因为分母归一化项随其他元素效用增大而增大）。以往MNL老虎机仅对效用参数构建置信界的方法在此失效。为此，B-SMB通过均值定理将误差项从非线性比值形式中解耦，直接在期望收益层面构建对称置信区间： $\(R_{k,\tau}^{UCB}(S_k) := \sum_{n \in S_k} w_{n,k} p(n|S_k, \widehat{\theta}_{k,\tau}) + 2\beta_T \max_{n \in S_k} \|z_n\|_{V_{k,\tau}^{-1}}\)$ $\(R_{k,\tau}^{LCB}(S_k) := \sum_{n \in S_k} w_{n,k} p(n|S_k, \widehat{\theta}_{k,\tau}) - 2\beta_T \max_{n \in S_k} \|z_n\|_{V_{k,\tau}^{-1}}\)$ 为了避免直接枚举所有可能的可行匹配集合 \(\mathcal{M}\) 进行淘汰带来的巨大统计开销，算法针对每个活跃代理-手臂对 \((n, k)\)，求解一个代表性乐观分配 \(\{S_{l,\tau}^{(n,k)}\}_{l \in [K]}\)（强制要求 \(n \in S_k\)）。若该代表性分配的总收益上界甚至无法超过当前活跃集合族所能达到的最大收益下界 \(\max_{\{S_l\} \in \mathcal{M}_{\tau-1}} \sum_{l \in [K]} R_{l,\tau}^{LCB}(S_l)\)，则代理 \(n\) 绝不可能属于手臂 \(k\) 的最优匹配池，可安全从活跃集合 \(\mathcal{N}_{k,\tau}\) 中剔除。
3. G-最优实验设计探索与双对数批次调度：压缩计算开销至Θ(log log T)
在淘汰剩余的活跃候选集 \(\mathcal{N}_{k,\tau}\) 上，算法并不采用耗时的逐轮贪心探索，而是调用Kiefer-Wolfowitz定理框架下的G-最优设计（G-optimal design），求解离散概率分布 \(\pi_{k,\tau} \in \mathcal{P}(\mathcal{N}_{k,\tau})\) 以最小化预测方差的最大椭球范数： $\(\pi_{k,\tau} \leftarrow \mathop{\mathrm{argmin}}_{\pi \in \mathcal{P}(\mathcal{N}_{k,\tau})} \max_{n \in \mathcal{N}_{k,\tau}} \|z_n\|^2_{\left(\sum_{n \in \mathcal{N}_{k,\tau}} \pi(n) z_n z_n^\top + \frac{1}{r T_\tau} I_r\right)^{-1}}\)$ 由Carathéodory型定理可知，该最优解的支撑集大小被严格限制在至多 \(r(r+1)/2\) 个代理之内，可通过Frank-Wolfe算法快速求解。更重要的是，批次长度采用递推调度 \(T_{\tau+1} = \eta_T \sqrt{T_\tau}\)（其中 \(\eta_T = (T/rK)^{\frac{1}{2(1-2^{-M})}}\)）。这种次二次方指数膨胀机制确保了在整个时间跨度 \(T\) 内，批次总数 \(\tau_T \leq M\)。当令更新预算 \(M = \Theta(\log\log(T/rK))\) 时，昂贵的组合优化调用次数由 \(\mathcal{O}(T)\) 骤降至 \(\Theta(\log\log T)\)，而带来的额外遗憾开销仅为高阶小量。
4. 局部经验海森矩阵与自适应尺度扩展（B-SMB+）：摆脱非线性先验κ
B-SMB算法的置信半径 \(\beta_T\) 依赖问题未知的非线性常数 \(\kappa := \inf p(n|S,\theta)p(n_0|S,\theta)\)，在最坏情况下 \(1/\kappa\) 可达 \(\mathcal{O}(L^2)\) 甚至指数级恶化。进阶算法 B-SMB+ 通过引入局部经验正则化海森矩阵捕获对数似然的局部曲率： $\(H_{k,\tau}(\widehat{\theta}_{k,\tau}) = \lambda I_r + \sum_{t \in \mathcal{T}_{k,\tau-1}} \left[ \sum_{n \in S_{k,t}} p(n|S_{k,t}, \widehat{\theta}_{k,\tau}) z_n z_n^\top - \sum_{n,m \in S_{k,t}} p(n|S_{k,t}, \widehat{\theta}_{k,\tau}) p(m|S_{k,t}, \widehat{\theta}_{k,\tau}) z_n z_m^\top \right]\)$ 通过在中心化特征 \(\widetilde{z}_{n,k,\tau} = z_n - \sum_{m \in S_{k,t}} p(m|S_{k,t}, \widehat{\theta}_{k,\tau}) z_m\) 上构造一阶与二阶泰勒展开置信边界，并结合对代理集合族 \(\mathcal{J}(\mathcal{N}_{k,\tau})\) 与联合对 \(\mathcal{K}(\mathcal{N}_{k,\tau})\) 的三重G/D-最优设计探索，B-SMB+在无需先验知道 \(\kappa\) 的情况下彻底去除了遗憾界中对 \(1/\kappa\) 的线性依赖，仅付出额外的 \(\sqrt{r}\) 因子代价即可实现强自适应性。
损失函数 / 训练策略¶
在每个批次 \(\tau\) 的开始，算法聚合手臂 \(k\) 在历史探索集 \(\mathcal{T}_{k,\tau-1}\) 中收集到的二值反馈 \(y_{n,k,t} \in \{0,1\}\)，构建正则化负对数似然损失函数并求解极大似然估计： $\(l_{k,\tau}(\theta) = -\sum_{t \in \mathcal{T}_{k,\tau-1}} \sum_{n \in S_{k,t} \cup \{n_0\}} y_{n,k,t} \log p(n|S_{k,t}, \theta) + \frac{1}{2} \|\theta\|_2^2\)$ 其中 \(y_{n_0,k,t} = 1 - \sum_{n \in S_{k,t}} y_{n,k,t}\) 表示手臂拒绝所有候选者的外部选项指示。优化采用有约束凸优化求解器在 \(\|\theta\|_2 \leq 1\) 闭球内最小化 \(l_{k,\tau}(\theta)\)。
实验关键数据¶
主实验¶
论文在合成环境下进行了充分的对比验证：特征与真实效用参数均从均匀分布抽样后单位归一化，基础匹配奖励 \(w_{n,k} \sim \mathrm{Unif}[0,1]\)。对比基线包括：逐轮求解组合优化的标准MNL扩展算法 OFU-MNL+（Lee & Oh, 2024），以及两款面向稳定匹配的队列算法 UCB-QMB 与 TS-QMB（Kim & Oh, 2024）。时间跨度均设为 \(T = 5000\)。
| 实验规模配置 | 评测指标 | B-SMB（本文） | B-SMB+（本文） | OFU-MNL+（逐轮精确优化） | 相对削减/提升 |
|---|---|---|---|---|---|
| 小规模 (\(N=3, K=2, r=2\)) | 组合优化更新调用次数 | 3 | 3 | 5,000 | -99.94% 更新调用 |
| 小规模 (\(N=3, K=2, r=2\)) | 算法运行时间 (s) | ~25% 基准耗时 | ~28% 基准耗时 | 100% (Baseline) | -75% 耗时减少 |
| 小规模 (\(N=3, K=2, r=2\)) | 累积遗憾 (\(T=5000\)) | ~120 | ~140 | ~110 | 处于同等次线性水平 |
| 中规模 (\(N=7, K=4, r=2\)) | 组合优化更新调用次数 | 3 | 3 | 5,000 | -99.94% 更新调用 |
| 中规模 (\(N=7, K=4, r=2\)) | 算法运行时间 (s) | ~2% 基准耗时 | ~3% 基准耗时 | 100% (Baseline) | -98% 耗时减少 |
| 中规模 (\(N=7, K=4, r=2\)) | 累积遗憾 (\(T=5000\)) | ~260 | ~290 | ~230 | 紧密贴合逐轮最优界 |
消融实验与扩展可扩展性压力测试¶
为了评估算法在大规模动作空间下的可扩展性上限，作者设计了高维压力测试（\(N=18, K=5\)，此时潜在匹配空间大小达到 \(K^N \approx 3.8 \times 10^{12}\) 级别）。在此规模下，逐轮精确优化的OFU-MNL+在24小时内完全无法跑完5000轮，因此在同一机器上对比相同时间预算（3961秒）下的完成轮数与优化频次。
| 算法配置 (\(N=18, K=5\)) | 5000轮总耗时 (s) | 组合优化调用总次数 | 3961秒内完成轮数 | 完成进度百分比 |
|---|---|---|---|---|
| B-SMB (已知 \(\kappa\)) | 1,419 | 4 | 5,000 (已完成) | 100% |
| B-SMB+ (无先验 \(\kappa\)) | 3,961 | 3 | 5,000 (已完成) | 100% |
| OFU-MNL+ (逐轮基线) | > 24小时 (超时中断) | 5,000 (理论) | 44 | 0.88% |
关键发现¶
- 运行时间随规模指数级拉开差距：在 \(N=3, K=2\) 时，B-SMB相比逐轮基线节省了约75%的时间；当规模微幅扩展至 \(N=7, K=4\) 时，时间节省幅度迅速扩大至98%（耗时仅为基线的2%）。在大规模测试中，逐轮基线在相同时间内仅能推进0.88%的进度，彻底证实了稀疏更新在大动作空间下的决定性价值。
- 极少数更新足以实现充分探索：在 \(T=5000\) 的全流程中，B-SMB和B-SMB+的实际优化更新调用次数均稳定在3到4次，严格契合理论上的 \(\tau_T \leq M = \Theta(\log\log T)\) 证明。
- 算法遗憾代价微乎其微：分批淘汰策略造成的遗憾损失相比每轮重新规划的OFU-MNL+极小，两条累积遗憾曲线保持几乎相同的次线性凹增长形态，证明了统计效率未因批次冻结而受损。
亮点与洞察¶
- 组合优化与老虎机更新的频次解耦：将NP-hard组合优化的单轮求解复杂度和多臂老虎机的时间探索解耦，证明了即便底层的动作选取面临组合爆炸，也不需要每轮重解优化，\(\Theta(\log\log T)\) 次调用足以支撑 \(\widetilde{\mathcal{O}}(\sqrt{T})\) 遗憾。
- 从效用置信界跃迁至收益置信界：巧妙绕开了经典MNL老虎机在非线性分式下难以做下界估计（LCB）的缺陷，通过泰勒中值定理将Lipschitz连续性传导至整个分配方案的期望收益上，构建了对称的收益级置信椭球。
- 局部曲率对未知非线性常数的自适应：通过在海森矩阵的中心化特征上开展多重G/D-最优实验设计，彻底消除了对非线性参数 \(\kappa\)（可能低至指数小）的先验依赖，为广义非线性老虎机提供了具有理论保证的自适应样板。
局限与展望¶
- 理论遗憾界与下界存在差距：作者在讨论中承认，多分配MNL老虎机的理论遗憾下界为 \(\Omega(K\sqrt{T})\)，而本文算法在多手臂探索中为覆盖所有潜在匹配，上界引入了 \(K^{3/2}\)，存在一个 \(\sqrt{K}\) 的理论间隙尚未闭合。
- 缺乏真实双边匹配平台数据集的检验：论文目前的实验均基于合成数据验证时间与遗憾，尚未在带有复杂时空约束或动态排队机制的真实打车/众包平台上开展系统级仿真。
- 组合预言机依赖度：虽然调用次数被压至 \(\log\log T\)，但在每次批次更新时调用的离线组合优化本质仍是NP-hard问题；未来需进一步结合多项式时间近似预言机（\(\alpha\)-approximation oracle）深入研究近似遗憾与精确遗憾的权衡边界。
相关工作与启发¶
- vs. 稳定匹配老虎机 (Stable Matching Bandits, 如 Liu et al., 2020; Basu et al., 2021)：稳定匹配老虎机大多假设偏好序确定且以追求消除阻塞对为目标；本文的SMB框架将重心转向平台总体期望收益最大化，并将接受行为建模为遵循MNL的随机离散选择，更契合实际网约车与外卖派单场景。
- vs. 经典MNL单品类老虎机 (Agrawal et al., 2017a; Lee & Oh, 2024)：经典MNL老虎机仅针对单一接收方推荐单组商品（存在多项式求解算法）；本文将其推广至多臂多组合分配（\(K\) 个互斥品类集），揭示了这一拓展带来的强NP-hard本质，并通过批次更新成功攻克了计算瓶颈。
- vs. 批次线性老虎机 (Ruan et al., 2021; Sawarni et al., 2024)：先前批次老虎机主要探讨单手臂在线性或广义线性奖励下的分批更新；本文攻克了多手臂分配互斥约束以及MNL集合依赖非线性反馈带来的复杂关联。
评分¶
- 新颖性: ⭐⭐⭐⭐ [首次将批次稀疏更新理论引入多项Logit随机匹配老虎机，问题建模极具现实指导意义]
- 实验充分度: ⭐⭐⭐ [理论推导严密完备，但实验部分仅采用小规模合成数据与压力测试，缺少真实产业数据支持]
- 写作质量: ⭐⭐⭐⭐⭐ [逻辑链条清晰，理论体系自洽，主文与附录推导严密且符号统一规范]
- 价值: ⭐⭐⭐⭐ [成功解决了强化学习与组合优化交叉领域中“逐轮重规划算力爆炸”的根本痛点，方法论极具实用推广价值]