Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit
  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.
