mlsanityData to 7 Oct 2026

Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities

arXiv 2601.06913 ↗First posted 11 Jan 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the multinomial logit (MNL) contextual bandit problem for sequential assortment selection. Although most existing research assumes utility functions to be linear in item features, this linearity assumption restricts the modeling of intricate interactions between items and user preferences. A recent work (Zhang & Luo, 2024) has investigated general utility function classes, yet its method faces fundamental trade-offs between computational tractability and statistical efficiency. To address this limitation, we propose a computationally efficient algorithm for MNL contextual bandits leveraging the upper confidence bound principle, specifically designed for non-linear parametric utility functions, including those modeled by neural networks. Under a realizability assumption and a mild geometric condition on the utility function class, our algorithm achieves a regret bound of tildeO(√T), where T denotes the total number of rounds. Our result establishes that sharp tildeO(√T)-regret is attainable even with neural network-based utilities, without relying on strong assumptions such as neural tangent kernel approximations. To the best of our knowledge, our proposed method is the first computationally tractable algorithm for MNL contextual bandits with non-linear utilities that provably attains tildeO(√T) regret. Comprehensive numerical experiments validate the effectiveness of our approach, showing robust performance not only in realizable settings but also in scenarios with model misspecification.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 31 of its 46 references that are in the map. First posted on arXiv 11 Jan 2026.

Builds on

31 of 46 references.

References · 31

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  3. 2020Neural Thompson Samplingcited by 127
  4. 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
  5. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 114
  6. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  7. 2020Neural Contextual Bandits with Deep Representation and Shallow Explorationcited by 71
  8. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  9. 2017MNL-Bandit: A Dynamic Learning Approach to Assortment Selectioncited by 50
  10. 2015Fast rates in statistical and online learningcited by 47
  11. 2022Jointly Efficient and Optimal Algorithms for Logistic Banditscited by 41
  12. 2021Neural Contextual Bandits without Regretcited by 40
19 more
  1. 2018Dynamic Assortment Optimization with Changing Contextual Informationcited by 28
  2. 2021Multinomial Logit Contextual Bandits: Provable Optimality and Practicalitycited by 21
  3. 2021Dynamic pricing and assortment under a contextual MNL demandcited by 20
  4. 2024Nearly Minimax Optimal Regret for Multinomial Logistic Banditcited by 20
  5. 2023Combinatorial Neural Banditscited by 16
  6. 2018Multinomial Logit Bandit with Linear Utility Functionscited by 15
  7. 2020A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Banditcited by 15
  8. 2025Improved Online Confidence Bounds for Multinomial Logistic Banditscited by 14
  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. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  12. 2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
  13. 2022Global Optimization with Parametric Function Approximationcited by 7
  14. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
  15. 2021Robust Generalization of Quadratic Neural Networks via Function Identificationcited by 5
  16. 2024Contextual Multinomial Logit Bandits with General Value Functionscited by 4
  17. 2024Stochastic Bandits with ReLU Neural Networkscited by 2
  18. 2025Quantum Non-Linear Bandit Optimizationcited by 2
  19. 2023Communication-Efficient Federated Non-Linear Bandit Optimizationcited by 1

Built on by

Not cited yet.