跳转至

Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities

会议: NeurIPS 2025
arXiv: 2601.06913
作者: Taehyun Hwang, Dahngoon Kim, Min-hwan Oh (Seoul National University)
代码: 未公开
领域: reinforcement_learning
关键词: contextual bandits, multinomial logit, 非线性效用函数, 组合选品优化, UCB, 神经网络

一句话总结

首次为MNL上下文赌博机问题在非线性效用函数（含神经网络）下设计了计算可行且统计最优的算法ONL-MNL，在不依赖NTK假设的情况下达到\(\widetilde{\mathcal{O}}(\sqrt{T})\)的遗憾上界。

研究背景与动机

问题背景

多项式Logit（MNL）上下文赌博机是推荐系统、在线零售和个性化营销中常见的序列选品问题模型。智能体在每轮观察物品特征后选择一个子集（assortment）展示给用户，用户按MNL选择模型选取物品，目标是最小化与最优选品策略的累积遗憾。

已有工作的不足

  • 几乎所有已有MNL上下文赌博机工作都假设效用函数关于特征是线性的，无法捕捉复杂非线性用户行为
  • Zhang & Luo (2025) 首次考虑一般效用函数类，但面临计算可行性与统计效率的根本矛盾：
    • \(\varepsilon\)-greedy方法计算可行，但遗憾仅达\(\widetilde{\mathcal{O}}(T^{2/3})\)（随机设定）或\(\widetilde{\mathcal{O}}(T^{5/6})\)（对抗设定）
    • log-barrier和Feel-Good TS方法可达\(\widetilde{\mathcal{O}}(\sqrt{T})\)，但计算不可行（非凸优化）
  • 现有神经网络赌博机依赖NTK近似，要求不切实际的过参数化

核心动机

设计一个同时满足计算可行性和\(\widetilde{\mathcal{O}}(\sqrt{T})\)最优遗憾的MNL上下文赌博机算法，支持包括神经网络在内的非线性参数化效用函数。

方法详解

问题建模

  • MNL选择模型：用户从展示集合\(S_t\)中选择物品\(i\)的概率为 \(p(i|X_t,S_t,\mathbf{w}^*) = \frac{\exp(f_{\mathbf{w}^*}(\mathbf{x}_{ti}))}{1+\sum_{j\in S_t}\exp(f_{\mathbf{w}^*}(\mathbf{x}_{tj}))}\)
  • 非线性参数化：效用函数\(f_\mathbf{w}(\cdot)\)属于一般参数化函数类\(\mathcal{F}\)（可以是神经网络），对参数\(\mathbf{w}\)可微但不要求对特征\(\mathbf{x}\)可微
  • 等价集：\(\mathcal{W}^* := \{\mathbf{w} \in \mathcal{W}: f_\mathbf{w}(\mathbf{x}) = f_{\mathbf{w}^*}(\mathbf{x})\ \forall \mathbf{x}\}\)，允许神经网络中因参数对称性产生多个全局最优
  • 目标：最小化累积遗憾 \(\mathrm{Regret}_T = \sum_{t=1}^T [R_t(S_t^*, \mathbf{w}^*) - R_t(S_t, \mathbf{w}^*)]\)

核心技术挑战

  1. 非线性MNL模型的负对数似然缺乏线性情况下的自一致性（self-concordance）性质
  2. 梯度依赖于未知参数，无法直接套用线性模型的集中不等式
  3. 非凸优化景观存在多个全局最优（如神经网络的神经元排列对称性）

算法：ONL-MNL（两阶段设计）

Phase I — 均匀探索（\(t_0\)轮）：

  • 随机均匀采样assortment，收集用户选择数据
  • 最小化负对数似然\(\mathcal{L}(\mathbf{w})\)获得先导估计\(\hat{\mathbf{w}}_0\)
  • 利用广义几何条件（Assumption 4）证明收敛率：\(\min_{\tilde{\mathbf{w}}\in\mathcal{W}^*}\|\hat{\mathbf{w}}_0 - \tilde{\mathbf{w}}\|_2^2 = \mathcal{O}(1/t_0)\)

Phase II — 乐观探索（剩余\(T-t_0\)轮）：

  • 构建线性化MNL模型：对效用函数\(f_\mathbf{w}\)在当前估计\(\hat{\mathbf{w}}_t\)处做一阶Taylor展开
  • 最小化正则化负对数似然（以\(\hat{\mathbf{w}}_0\)为正则化中心而非原点）
  • 构建乐观效用估计：
\[z_{ti} = f_{\hat{\mathbf{w}}_t}(\mathbf{x}_{ti}) + \sqrt{\beta_t}\|\nabla f_{\hat{\mathbf{w}}_t}(\mathbf{x}_{ti})\|_{\mathbf{V}_t^{-1}} + \frac{\beta_t C_h}{\lambda}\]
  • 选择使乐观期望收入最大的assortment：\(S_t = \arg\max_{S\in\mathcal{S}} \widetilde{R}_t(S)\)
  • 更新Gram矩阵\(\mathbf{V}_{t+1} = \mathbf{V}_t + \sum_{i\in S_t}\nabla f_{\hat{\mathbf{w}}_t}(\mathbf{x}_{ti})\nabla f_{\hat{\mathbf{w}}_t}(\mathbf{x}_{ti})^\top\)

关键技术创新

广义几何条件（Assumption 4）：对期望平方损失\(\ell_\mathrm{sq}(\mathbf{w})\)要求满足\((\tau,\gamma)\)-增长条件或\(\mu\)-局部强凸性（相对于等价集\(\mathcal{W}^*\)），严格弱于现有工作要求全局唯一最优的假设。允许高度非凸损失景观中存在任意多个虚假局部最优和多个全局最优，天然适配神经网络。

\(\lambda\)-无关集中不等式：针对\(\lambda = \mathcal{O}(\sqrt{T})\)的大正则化参数设定，推导出对\(\lambda\)无关（up to对数因子）的新型集中不等式，突破现有Bernstein型bound要求\(\lambda = \mathcal{O}(d\log T)\)的瓶颈。

数学归纳法证明置信集：递推证明Phase II中所有轮次的估计误差\(\min_{\tilde{\mathbf{w}}\in\mathcal{W}^*}\|\hat{\mathbf{w}}_t-\tilde{\mathbf{w}}\|_2^2 = \widetilde{\mathcal{O}}(1/t_0)\)，进而保证\(\beta_t = \widetilde{\mathcal{O}}(\mu^{-2}\kappa^{-4}d_w)\)。

主定理

设\(\kappa := \min_{\mathbf{w},X,S,i} p(0|X,S,\mathbf{w})\cdot p(i|X,S,\mathbf{w})\)，取\(t_0 = \lceil \kappa^{-3/2}d_w\sqrt{T}\rceil\)，则以高概率：

\[\mathrm{Regret}_T = \widetilde{\mathcal{O}}\left(\kappa^{-3/2}d_w\sqrt{T} + \kappa^{-2}\mu^{-1}d_w\sqrt{T}\right)\]

在\(T\)上达到\(\widetilde{\mathcal{O}}(\sqrt{T})\)，且不依赖物品总数\(N\)。

实验关键数据

实验1：可实现与模型误配下的累积遗憾

设定：\(N=100\)物品，\(K=5\)最大选品数，\(d=3\)特征维度，30个随机种子，\(T=1000\)轮。

算法 效用类型 可实现性 Gaussian上下文表现 关键特点
ONL-MNL (本文) 非线性 可实现 遗憾最低，快速收敛 计算可行+统计最优
ONL-MNL (本文) 非线性 误配 仍保持低遗憾 鲁棒性强
\(\varepsilon\)-greedy-MNL 一般 可实现 遗憾显著高于ONL-MNL 计算可行但次优
UCB-MNL 线性 误配 遗憾持续线性增长 无法捕捉非线性
TS-MNL 线性 误配 遗憾持续线性增长 线性假设失效
OFU-MNL+ 线性 误配 遗憾持续线性增长 近似最优但限于线性
  • 可实现设定：真实效用为2层sigmoid神经网络（3个隐藏神经元），\(t_0=50\)
  • 误配设定：真实效用为\(\cos(2\pi(\mathbf{x}^\top\mathbf{w}^*)) - \frac{1}{2}(\mathbf{x}^\top\mathbf{w}^*)\)，估计器用15个隐藏神经元，\(t_0=100\)

实验2：物品数量\(N\)对遗憾的影响

设定：可实现环境（10个隐藏神经元），\(T=500\)，比较\(N=100\)和\(N=800\)。

算法 \(N=100\) (Gaussian) \(N=800\) (Gaussian) \(N\)增大的影响
ONL-MNL (本文) 低遗憾 遗憾略增（仅Phase I阶段） Phase II斜率不变，学习效率不受\(N\)影响
\(\varepsilon\)-greedy-MNL 中等遗憾 遗憾显著增加 理论遗憾\(\propto N^{1/3}\)，与理论一致

实验在Gaussian和Uniform两种上下文分布下均观察到一致结论：ONL-MNL在Phase II的收敛斜率与\(N\)无关。

与已有方法的理论比较

算法 效用类型 计算可行 遗憾 依赖\(N\)?
\(\varepsilon\)-greedy [Zhang & Luo] Lipschitz ✓ \(\widetilde{\mathcal{O}}((d_wNK)^{1/3}T^{2/3})\) 是
log-barrier [Zhang & Luo] Lipschitz ✗ \(\widetilde{\mathcal{O}}(K^2\sqrt{d_wNT})\) 是
Feel-Good TS [Zhang & Luo] Lipschitz ✗ \(\widetilde{\mathcal{O}}(K^2\sqrt{d_wNT})\) 是
ONL-MNL (本文) 光滑 ✓ \(\widetilde{\mathcal{O}}(\kappa^{-2}\mu^{-1}d_w\sqrt{T})\) 否

亮点

  • 首个可行+最优算法：在非线性效用MNL赌博机中，首次同时达到计算可行性和\(\widetilde{\mathcal{O}}(\sqrt{T})\)遗憾，打破此前计算-统计效率的根本矛盾
  • 无需NTK假设：直接处理一般非线性参数化（含神经网络），不需要过参数化或特定网络架构限制
  • 遗憾不依赖\(N\)：区别于已有方法对物品总数\(N\)的多项式依赖，适用于大规模物品池场景
  • 广义几何条件：严格弱化了已有几何假设，允许多全局最优的非凸损失景观，天然适配神经网络
  • 新型集中不等式：推导出对正则化参数\(\lambda\)无关的参数估计集中bound，突破了\(\lambda = \mathcal{O}(\sqrt{T})\)时的技术瓶颈

局限与展望

  • 实例依赖因子\(\kappa\)：遗憾bound中\(\kappa^{-1}\)在最坏情况下可达\(\mathcal{O}(K^2)\)，消除或弱化此依赖是开放问题
  • Phase I需i.i.d.上下文：Assumption 3要求探索阶段上下文独立同分布，虽然Phase II可对抗，但仍是限制
  • 广义几何条件验证困难：Assumption 4难以对一般神经网络架构事先验证，论文未给出具体验证方法
  • 实验规模有限：仅在\(N\leq 800\)、\(d=3\)的设定下验证，未涉及高维特征或更大规模实际数据集
  • 未考虑完全对抗设定：Phase II虽理论上允许对抗上下文，但实验仅在随机上下文下进行
  • MNL MDP扩展：论文提出将框架扩展到MNL MDP的方向，但未给出具体方案

与相关工作的对比

  • UCB-MNL [Oh & Iyengar 2021]、TS-MNL [Cheung & Simchi-Levi 2017]：仅支持线性效用，在非线性场景下遗憾不收敛
  • OFU-MNL+ [Lee & Oh 2024]：线性效用下的近最优算法，改进了\(\kappa\)依赖，但仍限于线性
  • Zhang & Luo [2025]：首次考虑一般效用，但陷入计算-统计效率的tradeoff，计算可行的方法仅\(T^{2/3}\)遗憾
  • NTK-based neural bandits [Zhou et al., Hwang et al.]：需要过参数化假设，不适用于实际规模的网络
  • Non-NTK neural bandits [Xu et al. 2024, Huang et al. 2021]：需要特定激活函数（二次）或上下文分布（Gaussian），适用范围窄
  • 线性/GLM bandits [Abbasi-Yadkori et al., Filippi et al.]：全局强凸假设不适用于非线性模型

评分

  • 新颖性: ⭐⭐⭐⭐⭐ — 首次解决非线性MNL赌博机中计算可行性与统计最优性的矛盾
  • 实验充分度: ⭐⭐⭐ — 验证了核心claims但规模较小，缺少真实应用数据集
  • 写作质量: ⭐⭐⭐⭐ — 问题动机清晰，技术路线自洽，理论推导严谨
  • 价值: ⭐⭐⭐⭐ — 填补重要理论空白，对推荐系统等实际应用有潜在价值

相关论文