# Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithm

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 28 references that are in the map.
- First posted on arXiv 7 Jul 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [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)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits](https://mlsanity.com/paper/2011.11222/) (2020)
- [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)
- [A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit](https://mlsanity.com/paper/2011.14033/) (2020)
- [Improved Online Confidence Bounds for Multinomial Logistic Bandits](https://mlsanity.com/paper/2502.10020/) (2025)
- [UCB-based Algorithms for Multinomial Logistic Regression Bandits](https://mlsanity.com/paper/2103.11489/) (2021)
- [Mixability made efficient: Fast online multiclass logistic regression](https://mlsanity.com/paper/2110.03960/) (2021)
- [Multinomial Logit Bandit with Low Switching Cost](https://mlsanity.com/paper/2007.04876/) (2020)
- [Efficient Methods for Online Multiclass Logistic Regression](https://mlsanity.com/paper/2110.03020/) (2021)

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

- [Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptions](https://mlsanity.com/paper/2604.22161/) (2026)
- [Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs](https://mlsanity.com/paper/2605.19768/) (2026)
- [Efficient Multinomial Logistic Bandit via Frequent Directions](https://mlsanity.com/paper/2606.11968/) (2026)

## Abstract (arXiv)

We consider the multinomial logistic bandit problem in which a learner interacts with an environment by selecting actions to maximize expected rewards based on probabilistic feedback from multiple possible outcomes. In the binary setting, recent work has focused on understanding the impact of the non-linearity of the logistic model (Faury et al., 2020; Abeille et al., 2021). They introduced a problem-dependent constant kappa_* ≥ 1 that may be exponentially large in some problem parameters and which is captured by the derivative of the sigmoid function. It encapsulates the non-linearity and improves existing regret guarantees over T rounds from smashO(d√T) to smashO(d√T/kappa_*), where d is the dimension of the parameter space. We extend their analysis to the multinomial logistic bandit framework with a finite action space, making it suitable for complex applications with more than two choices, such as reinforcement learning or recommender systems. To achieve this, we extend the definition of  kappa_*  to the multinomial setting and propose an efficient algorithm that leverages the problem's non-linearity. Our method yields a problem-dependent regret bound of order  smashwidetildeO( R d √ KT/kappa_* )  , where R denotes the norm of the vector of rewards and K is the number of outcomes. This improves upon the best existing guarantees of order  smashwidetildeO( RdK √T ). Moreover, we provide a matching smash Omega(dR√KT/kappa_*) lower-bound, showing that our algorithm is minimax-optimal and that our definition of kappa_* is optimal.