# Improved Online Confidence Bounds for Multinomial Logistic Bandits

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 36 references that are in the map.
- First posted on arXiv 14 Feb 2025.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (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)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [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)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [On the Performance of Thompson Sampling on Logistic Bandits](https://mlsanity.com/paper/1905.04654/) (2019)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Dynamic Assortment Optimization with Changing Contextual Information](https://mlsanity.com/paper/1810.13069/) (2018)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Generalized Linear Bandits with Limited Adaptivity](https://mlsanity.com/paper/2404.06831/) (2024)
- [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)
- [Nearly Minimax Optimal Regret for Multinomial Logistic Bandit](https://mlsanity.com/paper/2405.09831/) (2024)
- [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)
- [Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2212.13540/) (2022)
- [Composite convex minimization involving self-concordant-like cost functions](https://mlsanity.com/paper/1502.01068/) (2015)
- [Mixability made efficient: Fast online multiclass logistic regression](https://mlsanity.com/paper/2110.03960/) (2021)
- [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)
- [Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2406.13633/) (2024)

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

- [Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update](https://mlsanity.com/paper/2507.11847/) (2025)
- [Neural Logistic Bandits](https://mlsanity.com/paper/2505.02069/) (2025)
- [Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithm](https://mlsanity.com/paper/2507.05306/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret](https://mlsanity.com/paper/2606.09668/) (2026)
- [A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2602.10971/) (2026)
- [Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptions](https://mlsanity.com/paper/2604.22161/) (2026)
- [Generalized Linear Bandits with Memory](https://mlsanity.com/paper/2608.15848/) (2026)
- [Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities](https://mlsanity.com/paper/2601.06913/) (2026)
- [Optimal Exploration of New Products under Assortment Decisions](https://mlsanity.com/paper/2604.18800/) (2026)
- [Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs](https://mlsanity.com/paper/2605.19768/) (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)
- [Efficient Multinomial Logistic Bandit via Frequent Directions](https://mlsanity.com/paper/2606.11968/) (2026)
- [Diversified Multinomial Logit Contextual Bandits](https://mlsanity.com/paper/2607.11684/) (2026)

## Abstract (arXiv)

In this paper, we propose an improved online confidence bound for multinomial logistic (MNL) models and apply this result to MNL bandits, achieving variance-dependent optimal regret. Recently, Lee & Oh (2024) established an online confidence bound for MNL models and achieved nearly minimax-optimal regret in MNL bandits. However, their results still depend on the norm-boundedness of the unknown parameter B and the maximum size of possible outcomes K. To address this, we first derive an online confidence bound of Oleft(√d log t + B √d right), which is a significant improvement over the previous bound of O (B √d log t log K ) (Lee & Oh, 2024). This is mainly achieved by establishing tighter self-concordant properties of the MNL loss and applying Ville's inequality to bound the estimation error. Using this new online confidence bound, we propose a constant-time algorithm, OFU-MNL++, which achieves a variance-dependent regret bound of O Big( d log T √ sumt=1T σt2  Big)  for sufficiently large T, where σt2 denotes the variance of the rewards at round t, d is the dimension of the contexts, and T is the total number of rounds. Furthermore, we introduce a Maximum Likelihood Estimation (MLE)-based algorithm, OFU-MN2L, which achieves an anytime poly(B)-free regret of O Big( d log (BT) √ sumt=1T σt2  Big) .