Fully Gap-Dependent Bounds for Multinomial Logit Bandit

Jiaqi Yang
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:199-207, 2021.

Abstract

We study the multinomial logit (MNL) bandit problem, where at each time step, the seller offers an assortment of size at most $K$ from a pool of $N$ items, and the buyer purchases an item from the assortment according to a MNL choice model. The objective is to learn the model parameters and maximize the expected revenue. We present (i) an algorithm that identifies the optimal assortment $S^*$ within $\widetilde{O}(\sum_{i = 1}^N \Delta_i^{-2})$ time steps with high probability, and (ii) an algorithm that incurs $O(\sum_{i \notin S^*} K\Delta_i^{-1} \log T)$ regret in $T$ time steps. To our knowledge, our algorithms are the \emph{first} to achieve gap-dependent bounds that \emph{fully} depends on the suboptimality gaps of \emph{all} items. Our technical contributions include an algorithmic framework that relates the MNL-bandit problem to a variant of the top-$K$ arm identification problem in multi-armed bandits, a generalized epoch-based offering procedure, and a layer-based adaptive estimation procedure.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-yang21a, title = { Fully Gap-Dependent Bounds for Multinomial Logit Bandit }, author = {Yang, Jiaqi}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {199--207}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/yang21a/yang21a.pdf}, url = {https://proceedings.mlr.press/v130/yang21a.html}, abstract = { We study the multinomial logit (MNL) bandit problem, where at each time step, the seller offers an assortment of size at most $K$ from a pool of $N$ items, and the buyer purchases an item from the assortment according to a MNL choice model. The objective is to learn the model parameters and maximize the expected revenue. We present (i) an algorithm that identifies the optimal assortment $S^*$ within $\widetilde{O}(\sum_{i = 1}^N \Delta_i^{-2})$ time steps with high probability, and (ii) an algorithm that incurs $O(\sum_{i \notin S^*} K\Delta_i^{-1} \log T)$ regret in $T$ time steps. To our knowledge, our algorithms are the \emph{first} to achieve gap-dependent bounds that \emph{fully} depends on the suboptimality gaps of \emph{all} items. Our technical contributions include an algorithmic framework that relates the MNL-bandit problem to a variant of the top-$K$ arm identification problem in multi-armed bandits, a generalized epoch-based offering procedure, and a layer-based adaptive estimation procedure. } }
Endnote
%0 Conference Paper %T Fully Gap-Dependent Bounds for Multinomial Logit Bandit %A Jiaqi Yang %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-yang21a %I PMLR %P 199--207 %U https://proceedings.mlr.press/v130/yang21a.html %V 130 %X We study the multinomial logit (MNL) bandit problem, where at each time step, the seller offers an assortment of size at most $K$ from a pool of $N$ items, and the buyer purchases an item from the assortment according to a MNL choice model. The objective is to learn the model parameters and maximize the expected revenue. We present (i) an algorithm that identifies the optimal assortment $S^*$ within $\widetilde{O}(\sum_{i = 1}^N \Delta_i^{-2})$ time steps with high probability, and (ii) an algorithm that incurs $O(\sum_{i \notin S^*} K\Delta_i^{-1} \log T)$ regret in $T$ time steps. To our knowledge, our algorithms are the \emph{first} to achieve gap-dependent bounds that \emph{fully} depends on the suboptimality gaps of \emph{all} items. Our technical contributions include an algorithmic framework that relates the MNL-bandit problem to a variant of the top-$K$ arm identification problem in multi-armed bandits, a generalized epoch-based offering procedure, and a layer-based adaptive estimation procedure.
APA
Yang, J.. (2021). Fully Gap-Dependent Bounds for Multinomial Logit Bandit . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:199-207 Available from https://proceedings.mlr.press/v130/yang21a.html.

Related Material