2025-11-15T02:07:10.757818

Nearly Minimax Optimal Regret for Multinomial Logistic Bandit

Lee, Oh

In this paper, we study the contextual multinomial logit (MNL) bandit problem in which a learning agent sequentially selects an assortment based on contextual information, and user feedback follows an MNL choice model. There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the maximum assortment size $K$. Additionally, the variation in reward structures between these bounds complicates the quest for optimality. Under uniform rewards, where all items have the same expected reward, we establish a regret lower bound of $Î©(d\sqrt{T/K})$ and propose a constant-time algorithm, OFU-MNL+, that achieves a matching upper bound of $\tilde{O}(d\sqrt{T/K})$. We also provide instance-dependent minimax regret bounds under uniform rewards. Under non-uniform rewards, we prove a lower bound of $Î©(d\sqrt{T})$ and an upper bound of $\tilde{O}(d\sqrt{T})$, also achievable by OFU-MNL+. Our empirical studies support these theoretical findings. To the best of our knowledge, this is the first work in the contextual MNL bandit literature to prove minimax optimality -- for either uniform or non-uniform reward setting -- and to propose a computationally efficient algorithm that achieves this optimality up to logarithmic factors.

academic

Nearly Minimax Optimal Regret for Multinomial Logistic Bandit

基本信息

论文ID: 2405.09831
标题: Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
作者: Joongkyu Lee (Seoul National University), Min-hwan Oh (Seoul National University)
分类: stat.ML cs.LG
发表时间/会议: NeurIPS 2024 (38th Conference on Neural Information Processing Systems)
论文链接: https://arxiv.org/abs/2405.09831

MNL老虎机问题：在推荐系统和在线零售等应用中，智能体需要向用户提供一组商品，用户的选择行为遵循多项式逻辑(MNL)模型
上下文信息：每轮中智能体可以观察到商品特征和可能的用户上下文信息
理论空白：现有工作在遗憾界的上界和下界之间存在显著差距，特别是关于商品组合大小K的依赖性

研究动机

理论完备性：弥补MNL老虎机理论分析的空白，建立紧致的遗憾界
算法效率：设计计算高效的算法，避免现有方法的指数时间复杂度
实际应用：为推荐系统等实际应用提供理论保证和高效算法

现有方法局限性

理论差距：下界Ω(d√T/K)与上界Õ(d√T)之间存在√K的差距
计算复杂度：现有算法需要枚举所有可能的商品组合，导致指数时间复杂度
参数依赖：对问题相关常数κ有不良依赖，其中1/κ = O(K²)

核心贡献

建立紧致遗憾界：
- 统一奖励下：下界Ω(√(v₀K/(v₀+K))d√T)，上界Õ(√(v₀K/(v₀+K))d√T)
- 非统一奖励下：下界Ω(d√T)，上界Õ(d√T)
提出高效算法OFU-MNL+：
- 常数时间复杂度O(1)，与轮数t无关
- 首个在MNL老虎机中证明随K增加而遗憾减少的算法
理论创新：
- 首次明确展示外部选项吸引参数v₀对遗憾的影响
- 提供实例相关的极小极大遗憾界
技术改进：
- 改进的椭圆势引理，消除对K的依赖
- 常数自协调性质的损失函数分析

方法详解

任务定义

输入：

每轮t，观察到N个商品的特征向量x_ ∈ ℝᵈ
最大商品组合大小K
外部选项吸引参数v₀

输出：

选择商品组合S_t ⊆ {1,...,N}，|S_t| ≤ K
观察用户选择c_t ∈ S_t ∪ {0}，遵循MNL模型

目标：最小化累积遗憾Reg_T(w*) = Σ_^T R_t(S_t, w) - R_t(S_t, w*)

模型架构

MNL选择模型

用户选择商品i ∈ S_t的概率为：

p_t(i|S_t, w*) = exp(x_{ti}^T w*) / (v₀ + Σ_{j∈S_t} exp(x_{tj}^T w*))

外部选项（不选择任何商品）的概率为：

p_t(0|S_t, w*) = v₀ / (v₀ + Σ_{j∈S_t} exp(x_{tj}^T w*))

OFU-MNL+算法核心组件

在线参数估计：
```
w_{t+1} = argmin_{w∈W} ⟨∇ℓ_t(w_t), w⟩ + (1/2η)||w - w_t||²_{H̃_t}
```
其中H̃_t = H_t + ηG_t(w_t)，G_t(w)为MNL损失的Hessian矩阵
置信集构造：
```
C_t(δ) = {w ∈ W : ||w_t - w||_{H_t} ≤ β_t(δ)}
```
其中β_t(δ) = O(√(d log t log K))

乐观效用计算：

α_{ti} = x_{ti}^T w_t + β_t(δ)||x_{ti}||_{H_t^{-1}}

商品组合选择：
- 统一奖励：选择K个最高α_的商品
- 非统一奖励：求解多项式时间的组合优化问题

技术创新点

改进的自协调分析：证明MNL损失函数具有3√2-自协调性质，相比之前的√(6K)改进了√K因子

K无关的椭圆势引理：

Σ_{t=1}^T Σ_{i∈S_t} p_t(i|S_t,w_{t+1})p_t(0|S_t,w_{t+1})||x_{ti}||²_{H_t^{-1}} ≤ 2d log(1 + T/(dλ))

紧致KL散度界：建立了更紧的KL散度上界，改进了Chen等人的结果

实验设置

数据集

合成数据集，参数w* ∈ ℝᵈ从-1/√d, 1/√dᵈ均匀采样
上下文特征x_从多元高斯分布N(0_d, I_d)采样并截断到-1/√d, 1/√dᵈ
配置：N=100, K∈{5,10,15}, d=5, T=3000

评价指标

累积遗憾：Σ_^T R_t(S_t, w) - R_t(S_t, w*)
每轮计算时间

对比方法

UCB-MNL：基于置信上界的方法
TS-MNL：基于Thompson采样的方法

实现细节

正则化参数λ = 84√(2d)η
步长η = (1/2)log(K+1) + 2
置信半径β_t(δ) = O(√(d log t log K))

实验结果

主要结果

遗憾性能：
- 统一奖励下，随着K增加，所有算法的累积遗憾都减少
- 非统一奖励下，K的增加不能保证遗憾改善
- OFU-MNL+在所有设置下都显著优于基线方法
计算效率：
- OFU-MNL+保持常数计算成本，与轮数t无关
- 基线方法的计算时间随t线性增长
- 统一奖励设置下的运行时间约为非统一设置的1/10