Fixed-Budget Pure Exploration in Multinomial Logit Bandits
Abstract
In this paper we investigate pure exploration problem in Multinomial Logit bandit(MNL-bandit) under fixed budget settings, a problem motivated by real-time applications in online advertising and retailing. Given an MNL-bandit instance and a fixed exploration budget, our goal is to minimize the misidentification error of the optimal assortment. Towards such an end we propose an algorithm that achieve gap-dependent complexities, and complement our investigation with a discussion on recent studies and a minimax lower bound on misidentification probability. To the best of our knowledge, our paper is the first to address the recently proposed open problem of fixed-budget pure exploration problem for MNL-bandits.
Cite
Text
Fang. "Fixed-Budget Pure Exploration in Multinomial Logit Bandits." International Joint Conference on Artificial Intelligence, 2022. doi:10.24963/IJCAI.2022/409Markdown
[Fang. "Fixed-Budget Pure Exploration in Multinomial Logit Bandits." International Joint Conference on Artificial Intelligence, 2022.](https://mlanthology.org/ijcai/2022/fang2022ijcai-fixed/) doi:10.24963/IJCAI.2022/409BibTeX
@inproceedings{fang2022ijcai-fixed,
title = {{Fixed-Budget Pure Exploration in Multinomial Logit Bandits}},
author = {Fang, Boli},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2022},
pages = {2951-2957},
doi = {10.24963/IJCAI.2022/409},
url = {https://mlanthology.org/ijcai/2022/fang2022ijcai-fixed/}
}