# Nearly Minimax Optimal Regret for Multinomial Logistic Bandit

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 49 references that are in the map.
- First posted on arXiv 16 May 2024.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2010.12642/) (2020)
- [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)
- [Logistic Regression: The Importance of Being Improper](https://mlsanity.com/paper/1803.09349/) (2018)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Lipschitz Adaptivity with Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1902.10797/) (2019)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Dynamic Assortment Optimization with Changing Contextual Information](https://mlsanity.com/paper/1810.13069/) (2018)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [Online Stochastic Linear Optimization under One-bit Feedback](https://mlsanity.com/paper/1509.07728/) (2015)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Multinomial Logit Contextual Bandits: Provable Optimality and Practicality](https://mlsanity.com/paper/2103.13929/) (2021)
- [Temporal Variability in Implicit Online Learning](https://mlsanity.com/paper/2006.07503/) (2020)
- [Dynamic pricing and assortment under a contextual MNL demand](https://mlsanity.com/paper/2110.10018/) (2021)
- [Best Arm Identification in Generalized Linear Bandits](https://mlsanity.com/paper/1905.08224/) (2019)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [Multinomial Logit Bandit with Linear Utility Functions](https://mlsanity.com/paper/1805.02971/) (2018)
- [A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit](https://mlsanity.com/paper/2011.14033/) (2020)
- [Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2209.06983/) (2022)
- [Composite convex minimization involving self-concordant-like cost functions](https://mlsanity.com/paper/1502.01068/) (2015)
- [UCB-based Algorithms for Multinomial Logistic Regression Bandits](https://mlsanity.com/paper/2103.11489/) (2021)
- [Contextual Multinomial Logit Bandits with General Value Functions](https://mlsanity.com/paper/2402.08126/) (2024)

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

- [Optimal Design for Reward Modeling in RLHF](https://mlsanity.com/paper/2410.17055/) (2024)
- [Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update](https://mlsanity.com/paper/2507.11847/) (2025)
- [Improved Online Confidence Bounds for Multinomial Logistic Bandits](https://mlsanity.com/paper/2502.10020/) (2025)
- [Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation](https://mlsanity.com/paper/2405.17061/) (2024)
- [Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2405.20165/) (2024)
- [Neural Logistic Bandits](https://mlsanity.com/paper/2505.02069/) (2025)
- [Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update](https://mlsanity.com/paper/2503.00419/) (2025)
- [Learning an Optimal Assortment Policy under Observational Data](https://mlsanity.com/paper/2502.06777/) (2025)
- [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)
- [A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2602.10971/) (2026)
- [Generalized Linear Bandits with Memory](https://mlsanity.com/paper/2608.15848/) (2026)
- [Privacy-Preserving Dynamic Assortment Selection](https://mlsanity.com/paper/2410.22488/) (2024)
- [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)
- [Offline Clustering of Preference Learning with Active-data Augmentation](https://mlsanity.com/paper/2510.26301/) (2025)
- [Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities](https://mlsanity.com/paper/2601.06913/) (2026)
- [Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent](https://mlsanity.com/paper/2605.25590/) (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)

In this paper, we study the contextual multinomial logit (MNL) bandit problem in which a learning agent sequentially selects an assortment based on contextual information, and user feedback follows an MNL choice model. There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the maximum assortment size K. Additionally, the variation in reward structures between these bounds complicates the quest for optimality. Under uniform rewards, where all items have the same expected reward, we establish a regret lower bound of Omega(d√T/K) and propose a constant-time algorithm, OFU-MNL+, that achieves a matching upper bound of tildeO(d√T/K). We also provide instance-dependent minimax regret bounds under uniform rewards. Under non-uniform rewards, we prove a lower bound of Omega(d√T) and an upper bound of tildeO(d√T), also achievable by OFU-MNL+. Our empirical studies support these theoretical findings. To the best of our knowledge, this is the first work in the contextual MNL bandit literature to prove minimax optimality -- for either uniform or non-uniform reward setting -- and to propose a computationally efficient algorithm that achieves this optimality up to logarithmic factors.