# Multinomial Logit Bandit with Linear Utility Functions

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2018.

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

- [Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models](https://mlsanity.com/paper/2108.06422/) (2021)
- [Multinomial Logit Contextual Bandits: Provable Optimality and Practicality](https://mlsanity.com/paper/2103.13929/) (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)
- [Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework](https://mlsanity.com/paper/2202.13227/) (2022)
- [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)
- [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)
- [Learning an Optimal Assortment Policy under Observational Data](https://mlsanity.com/paper/2502.06777/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [A Scalable Recommendation Engine for New Users and Items](https://mlsanity.com/paper/2209.06128/) (2022)
- [Privacy-Preserving Dynamic Assortment Selection](https://mlsanity.com/paper/2410.22488/) (2024)
- [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)

Multinomial logit bandit is a sequential subset selection problem which arises in many applications. In each round, the player selects a K-cardinality subset from N candidate items, and receives a reward which is governed by a it multinomial logit (MNL) choice model considering both item utility and substitution property among items. The player's objective is to dynamically learn the parameters of MNL model and maximize cumulative reward over a finite horizon T. This problem faces the exploration-exploitation dilemma, and the involved combinatorial nature makes it non-trivial. In recent years, there have developed some algorithms by exploiting specific characteristics of the MNL model, but all of them estimate the parameters of MNL model separately and incur a regret no better than tildeObig(√NTbig) which is not preferred for large candidate set size N. In this paper, we consider the it linear utility MNL choice model whose item utilities are represented as linear functions of d-dimension item features, and propose an algorithm, titled bf LUMB, to exploit the underlying structure. It is proven that the proposed algorithm achieves tildeObig(dK√Tbig) regret which is free of candidate set size. Experiments show the superiority of the proposed algorithm.