mlsanityData to 7 Oct 2026

Improved Online Confidence Bounds for Multinomial Logistic Bandits

arXiv 2502.10020 ↗First posted 14 Feb 2025stat.ML cs.LGcited by 14

Not on the map. Why?

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) .

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

Builds on

26 of 36 references.

References · 26

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
  4. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 56
  5. 2017MNL-Bandit: A Dynamic Learning Approach to Assortment Selectioncited by 50
  6. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  7. 2022Jointly Efficient and Optimal Algorithms for Logistic Banditscited by 41
  8. 2018Logistic Regression: The Importance of Being Impropercited by 40
  9. 2017Thompson Sampling for the MNL-Banditcited by 35
  10. 2019On the Performance of Thompson Sampling on Logistic Banditscited by 32
  11. 2018Dynamic Assortment Optimization with Changing Contextual Informationcited by 28
  12. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 27
14 more
  1. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  2. 2024Generalized Linear Bandits with Limited Adaptivitycited by 22
  3. 2021Multinomial Logit Contextual Bandits: Provable Optimality and Practicalitycited by 21
  4. 2020Temporal Variability in Implicit Online Learningcited by 20
  5. 2021Dynamic pricing and assortment under a contextual MNL demandcited by 20
  6. 2024Nearly Minimax Optimal Regret for Multinomial Logistic Banditcited by 20
  7. 2018Multinomial Logit Bandit with Linear Utility Functionscited by 15
  8. 2020A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Banditcited by 15
  9. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  10. 2015Composite convex minimization involving self-concordant-like cost functionscited by 12
  11. 2021Mixability made efficient: Fast online multiclass logistic regressioncited by 12
  12. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  13. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
  14. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 10.

14 papers.

Sort:

  1. 2025Generalized Linear Bandits: Almost Optimal Regret with One-Pass Updatecited by 16
  2. 2025Neural Logistic Banditscited by 5
  3. 2025Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithmcited by 3
  4. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  5. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  6. 2026Generalized Linear Bandits with Memorycited by 1
  7. 2026Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilitiescited by 0
  8. 2026Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptionscited by 0
  9. 2026Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPscited by 0
  10. 2026Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descentcited by 0
  11. 2026Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identificationcited by 0
  12. 2026Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regretcited by 0
2 more
  1. 2026Efficient Multinomial Logistic Bandit via Frequent Directionscited by 0
  2. 2026Diversified Multinomial Logit Contextual Banditscited by 0