多项式 Logit 上下文强化学习：可证优化与实用性

AAAIMar, 2021

多项式 Logit 上下文强化学习：可证优化与实用性

Multinomial Logit Contextual Bandits: Provable Optimality and Practicality

Min-hwan Oh, Garud Iyengar

TL;DR本研究考虑了基于多项式逻辑回归选择模型的序贯选择问题，提出了基于上界置信度算法的解法，并得到了近似最优的遗憾上界；进一步，我们研究了该模型的极大似然估计量的置信度界，为实际应用提供了理论指导。

Abstract

We consider a sequential assortment selection problem where the user choice is given by a multinomial logit (MNL) choice model whose parameters are unknown. In each period, the learning agent observes a $d$-dimensional contextual information about the user and the $N$ available items, and offers an assortment of size $K$ to the user, and observes the bandit

multinomial logit choice model contextual bandit problem upper confidence bound regret analysis maximum likelihood estimator

发现论文，激发创造

多项式逻辑回归赌博机的几乎极小极大后悔

本论文研究了上下文多项式逻辑（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 上下文弃权文献中首次证明鞍点最优性和提出实现这一最优性的计算高效算法，达到联合因子标量对数。

May, 2024

广义线性情境赌博机的可证明最优算法

本文提出了针对广义线性情境臂的上界置信度算法，实现了与众不同的性能，同时我们还分析了更简单的上界置信度算法，在特定情况下证明了该算法具有最优的后悔。

Feb, 2017

上下文臂选择模型

介绍了在上下文密集应用中的模型选择问题及其解决方案，该方案适用于线性上下文密集应用，并在先验知识下达到了较低的后验概率。

Jun, 2019

线性效用函数的多项式 Logit 老虎机

该论文提出了一种算法 LUMB 来解决使用线性效用 MNL 选择模型的多项式对数拉致问题，证明此算法比以往算法更优，无需考虑候选集大小。

May, 2018

关于 MNL-Bandit 组合选择模型的紧密下限的说明

考虑多项式对数式组合 (MNL) 赌博模型下的动态组合规划问题，证明了关于累计遗憾的严格下界和现有遗憾上界相匹配，适用于所有参数（时间范围 T，物品数量 N 和最大组合容量 K），并减小了现有研究中上下限遗憾之间的 O (√K) 间隙。