# Multinomial Logit Contextual Bandits: Provable Optimality and Practicality

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 60 references that are in the map.
- First posted on arXiv 25 Mar 2021.

## Builds on (most cited first, 15 of 15)

- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Dynamic Pricing in High-dimensions](https://mlsanity.com/paper/1609.07574/) (2016)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Provably Optimal Algorithms for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/1703.00048/) (2017)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014)
- [Dynamic Assortment Optimization with Changing Contextual Information](https://mlsanity.com/paper/1810.13069/) (2018)
- [Online Stochastic Linear Optimization under One-bit Feedback](https://mlsanity.com/paper/1509.07728/) (2015)
- [Multinomial Logit Bandit with Linear Utility Functions](https://mlsanity.com/paper/1805.02971/) (2018)
- [A Note on a Tight Lower Bound for MNL-Bandit Assortment Selection Models](https://mlsanity.com/paper/1709.06109/) (2017)
- [Assortment Optimization under Unknown MultiNomial Logit Choice Models](https://mlsanity.com/paper/1704.00108/) (2017)

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

- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Dynamic pricing and assortment under a contextual MNL demand](https://mlsanity.com/paper/2110.10018/) (2021)
- [Nearly Minimax Optimal Regret for Multinomial Logistic Bandit](https://mlsanity.com/paper/2405.09831/) (2024)
- [Improved Online Confidence Bounds for Multinomial Logistic Bandits](https://mlsanity.com/paper/2502.10020/) (2025)
- [Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2212.13540/) (2022)
- [Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation](https://mlsanity.com/paper/2405.17061/) (2024)
- [Harm Mitigation in Recommender Systems under User Preference Dynamics](https://mlsanity.com/paper/2406.09882/) (2024)
- [Conversational Dueling Bandits in Generalized Linear Models](https://mlsanity.com/paper/2407.18488/) (2024)
- [Contextual Multinomial Logit Bandits with General Value Functions](https://mlsanity.com/paper/2402.08126/) (2024)
- [Learning an Optimal Assortment Policy under Observational Data](https://mlsanity.com/paper/2502.06777/) (2025)
- [Low-Rank Online Dynamic Assortment with Dual Contextual Information](https://mlsanity.com/paper/2404.17592/) (2024)
- [Dynamic Assortment Selection and Pricing with Censored Preference Feedback](https://mlsanity.com/paper/2504.02324/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [Online Learning of Independent Cascade Models with Node-level Feedback](https://mlsanity.com/paper/2109.02519/) (2021)
- [New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem](https://mlsanity.com/paper/2312.12400/) (2023)
- [Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptions](https://mlsanity.com/paper/2604.22161/) (2026)
- [On Pareto Optimality for Parametric Choice Bandits](https://mlsanity.com/paper/2501.19277/) (2025)
- [Stochastic Matching Bandits with Rare Optimization Updates](https://mlsanity.com/paper/2509.04194/) (2025)
- [Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities](https://mlsanity.com/paper/2601.06913/) (2026)
- [Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification](https://mlsanity.com/paper/2605.25592/) (2026)
- [Diversified Multinomial Logit Contextual Bandits](https://mlsanity.com/paper/2607.11684/) (2026)

## Abstract (arXiv)

We consider a sequential assortment selection problem where the user choice is given by a multinomial logit (MNL) choice model whose parameters are unknown. In each period, the learning agent observes a d-dimensional contextual information about the user and the N available items, and offers an assortment of size K to the user, and observes the bandit feedback of the item chosen from the assortment. We propose upper confidence bound based algorithms for this MNL contextual bandit. The first algorithm is a simple and practical method which achieves an tildeO(d√T) regret over T rounds. Next, we propose a second algorithm which achieves a tildeO(√dT) regret. This matches the lower bound for the MNL bandit problem, up to logarithmic terms, and improves on the best known result by a √d factor. To establish this sharper regret bound, we present a non-asymptotic confidence bound for the maximum likelihood estimator of the MNL model that may be of independent interest as its own theoretical contribution. We then revisit the simpler, significantly more practical, first algorithm and show that a simple variant of the algorithm achieves the optimal regret for a broad class of important applications.