论文标题
实例敏感算法用于多项式logit bandit中的纯探索算法
Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit
论文作者
论文摘要
由真实世界的应用程序（例如快速时尚零售和在线广告）的动机，多项式Logit Bandit（MNL-Bandit）是在线学习和运营研究中的一种流行模型，并且在过去十年中引起了很多关注。然而，到目前为止，在MNL-Bandit中尚未对Bandit理论中的一个基本问题纯粹的探索，这有点令人惊讶。在本文中，我们提供了有效的算法，以用于MNL-Bandit中的纯探索。我们的算法达到了实例敏感的拉力复杂性。我们还通过几乎匹配的下限来补充上限。
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. However, it is a bit surprising that pure exploration, a basic problem in bandit theory, has not been well studied in MNL-bandit so far. 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.
