May, 2024
多项式逻辑回归赌博机的几乎极小极大后悔
Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
Joongkyu Lee, Min-hwan Oh
TL;DR本论文研究了上下文多项式逻辑（MNL）弃权问题，其中学习代理根据上下文信息顺序选择一组，用户反馈遵循 MNL 选择模型。我们在特征维度 d 和最大组合大小 K 之间发现了显著的遗憾下界差异，并且这些边界之间奖励结构的变化使得追求最优性变得复杂。在统一奖励下，我们建立了一个遗憾下界 $Omega (dsqrt {T/K})$，并提出了一个常数时间算法 OFU-MNL+，该算法达到了上下界 $tilde {O}(dsqrt {T/K})$。在非统一奖励下，我们证明了一个下界 $Omega (dsqrt {T})$ 和上界 $tilde {O}(dsqrt {T})$，OFU-MNL+ 也可以实现这一界限。我们的实证研究支持这些理论结果。据我们所知，这是 MNL 上下文弃权文献中首次证明鞍点最优性和提出实现这一最优性的计算高效算法，达到联合因子标量对数。