# Fully Gap-Dependent Bounds for Multinomial Logit Bandit

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2020.

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

- [Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification](https://mlsanity.com/paper/2605.25592/) (2026)

## Abstract (arXiv)

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 widetildeO(sumi = 1N Deltai-2) time steps with high probability, and (ii) an algorithm that incurs O(sumi notin S^* KDeltai-1 log T) regret in T time steps. To our knowledge, our algorithms are the first to achieve gap-dependent bounds that fully depends on the suboptimality gaps of 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.