Multinomial Logit Bandit with Low Switching Cost
Abstract
We study multinomial logit bandit with limited adaptivity, where the algorithms change their exploration actions as infrequently as possible when achieving almost optimal minimax regret. We propose two measures of adaptivity: the assortment switching cost and the more fine-grained item switching cost. We present an anytime algorithm (AT-DUCB) with $O(N \log T)$ assortment switches, almost matching the lower bound $\Omega(\frac{N \log T}{ \log \log T})$. In the fixed-horizon setting, our algorithm FH-DUCB incurs $O(N \log \log T)$ assortment switches, matching the asymptotic lower bound. We also present the ESUCB algorithm with item switching cost $O(N \log^2 T)$.
Cite
Text
Dong et al. "Multinomial Logit Bandit with Low Switching Cost." International Conference on Machine Learning, 2020.Markdown
[Dong et al. "Multinomial Logit Bandit with Low Switching Cost." International Conference on Machine Learning, 2020.](https://mlanthology.org/icml/2020/dong2020icml-multinomial/)BibTeX
@inproceedings{dong2020icml-multinomial,
title = {{Multinomial Logit Bandit with Low Switching Cost}},
author = {Dong, Kefan and Li, Yingkai and Zhang, Qin and Zhou, Yuan},
booktitle = {International Conference on Machine Learning},
year = {2020},
pages = {2607-2615},
volume = {119},
url = {https://mlanthology.org/icml/2020/dong2020icml-multinomial/}
}