A Note on a Tight Lower Bound for MNL-Bandit Assortment Selection Models

Abstract

In this short note we consider a dynamic assortment planning problem under the capacitated multinomial logit (MNL) bandit model. We prove a tight lower bound on the accumulated regret that matches existing regret upper bounds for all parameters (time horizon $T$, number of items $N$ and maximum assortment capacity $K$) up to logarithmic factors. Our results close an $O(\sqrt{K})$ gap between upper and lower regret bounds from existing works.

Final version, 4 pages (double column)

Cited by in corpus (4)

• Dynamic Assortment Optimization with Changing Contextual Information
• Robust Dynamic Assortment Optimization in the Presence of Outlier Customers
• Dynamic Assortment Selection under the Nested Logit Models
• Continuous Assortment Optimization with Logit Choice Probabilities under Incomplete Information