Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit

Nikolai Karpov; Qin Zhang

AAAI 2022technical3 citations

Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit

Abstract

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.

BibTeX

@inproceedings{aaai2022_instancesensitiv,
  title = {Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit},
  author = {Nikolai Karpov and Qin Zhang},
  booktitle = {AAAI 2022},
  year = {2022}
}