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

arXiv: https://arxiv.org/abs/1709.06109 · HTML: https://mlsanity.com/paper/1709.06109/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2017.

## Built on by (most cited first, 7 of 7)

- [Multinomial Logit Contextual Bandits: Provable Optimality and Practicality](https://mlsanity.com/paper/2103.13929/) (2021)
- [Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricing](https://mlsanity.com/paper/2309.08634/) (2023)
- [Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimization](https://mlsanity.com/paper/2402.18917/) (2024)
- [Combinatorial Bandits without Total Order for Arms](https://mlsanity.com/paper/2103.02741/) (2021)
- [MNL-Bandit in non-stationary environments](https://mlsanity.com/paper/2303.02504/) (2023)
- [A Re-solving Heuristic for Dynamic Assortment Optimization with Knapsack Constraints](https://mlsanity.com/paper/2407.05564/) (2024)
- [Diversified Multinomial Logit Contextual Bandits](https://mlsanity.com/paper/2607.11684/) (2026)

## Abstract (arXiv)

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(√K) gap between upper and lower regret bounds from existing works.