Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit
This work provides efficient algorithms for pure exploration in the MNL-bandit model, which is relevant for applications like fast fashion retailing and online advertising, benefiting practitioners in these fields.
This paper addresses the pure exploration problem in the Multinomial Logit Bandit (MNL-bandit) model, which has been previously underexplored. The authors developed efficient algorithms that achieve instance-sensitive pull complexities, complemented by an almost matching lower bound.
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.