Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit
Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit
复制标题
DOI：
10.1609/aaai.v36i7.20669
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Nikolai Karpov;Qin Zhang
中科院分区：
文献类型：
--
作者：
Nikolai Karpov;Qin Zhang
受快速时尚零售和在线广告等实际应用的启发，Multinomial Logit Bandit（MNL-bandit）是在线学习和运筹学中的一个流行模型，在过去十年中引起了人们的广泛关注。在本文中，我们给出了有效的算法在MNL-强盗纯探索。我们的算法实现了实例敏感的拉复杂性。我们还补充了上界的几乎匹配的下限。
Motivated by real-world applications such as fast fashion retailing and online advertising, the Multinomial Logit Bandit (MNL-bandit) is a popular model in online learning and operations research, and has attracted much attention in the past decade. In this paper, we give efficient algorithms for pure exploration in MNL-bandit. Our algorithms achieve instance-sensitive pull complexities. We also complement the upper bounds by an almost matching lower bound.