Near-Optimal Policies for Dynamic Multinomial Logit Assortment Selection Models

Yining Wang; Xi Chen; Yuan Zhou

NeurIPS 2018poster25 citations

Near-Optimal Policies for Dynamic Multinomial Logit Assortment Selection Models

Abstract

In this paper we consider the dynamic assortment selection problem under an uncapacitated multinomial-logit (MNL) model. By carefully analyzing a revenue potential function, we show that a trisection based algorithm achieves an item-independent regret bound of O(sqrt(T log log T), which matches information theoretical lower bounds up to iterated logarithmic terms. Our proof technique draws tools from the unimodal/convex bandit literature as well as adaptive confidence parameters in minimax multi-armed bandit problems.

BibTeX

@inproceedings{NEURIPS2018_d88518ac,
 author = {Wang, Yining and Chen, Xi and Zhou, Yuan},
 booktitle = {Advances in Neural Information Processing Systems},
 editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
 pages = {},
 publisher = {Curran Associates, Inc.},
 title = {Near-Optimal Policies for Dynamic Multinomial Logit Assortment Selection Models},
 url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/d88518acbcc3d08d1f18da62f9bb26ec-Paper.pdf},
 volume = {31},
 year = {2018}
}