Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit

AAAI 2022 pp. 7096-7103

doi:10.1609/AAAI.V36I7.20669 /aaai/2022/karpov2022aaai-instance/

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.

PDF AAAI Semantic Scholar

Cite

Text

Karpov and Zhang. "Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit." AAAI Conference on Artificial Intelligence, 2022. doi:10.1609/AAAI.V36I7.20669

Markdown

[Karpov and Zhang. "Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit." AAAI Conference on Artificial Intelligence, 2022.](https://mlanthology.org/aaai/2022/karpov2022aaai-instance/) doi:10.1609/AAAI.V36I7.20669

BibTeX

@inproceedings{karpov2022aaai-instance,
  title     = {{Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit}},
  author    = {Karpov, Nikolai and Zhang, Qin},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2022},
  pages     = {7096-7103},
  doi       = {10.1609/AAAI.V36I7.20669},
  url       = {https://mlanthology.org/aaai/2022/karpov2022aaai-instance/}
}