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 $\tilde{O}(\sqrt{T})$, where $T$ denotes the total number of rounds. Our result establishes that sharp $\tilde{O}(\sqrt{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 $\tilde{O}(\sqrt{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.

Hence, the following research questions arise: What is the optimal regret lower bound in contextual MNL bandits?

Neural Information Processing Systems http://nips.cc/

These selected items are sequentially presented one at a time to a user. If the user clicks on a presented item, the cascading round ends.

These selected items are sequentially presented one at a time to a user. If the user clicks on a presented item, the cascading round ends.

The theorem statement should say "there exists a GCC choice model We will correct this in the final version if accepted. Re. structured bandits lower bound: Thanks for pointing us to this reference (which we will certainly include). We will add a discussion on this in the final version if accepted. We will incorporate all these suggestions and include this reference in the final version if accepted. The goal is to identify the'best' arm Essentially, we are interested in applications where the goal is to identify the'best' We will be happy to add some comments on this as well.

The classic Mallows model is a foundational tool for modeling user preferences. However, it has limitations in capturing real-world scenarios, where users often focus only on a limited set of preferred items and are indifferent to the rest. To address this, extensions such as the top-k Mallows model have been proposed, aligning better with practical applications. In this paper, we address several challenges related to the generalized top-k Mallows model, with a focus on analyzing buyer choices. Our key contributions are: (1) a novel sampling scheme tailored to generalized top-k Mallows models, (2) an efficient algorithm for computing choice probabilities under this model, and (3) an active learning algorithm for estimating the model parameters from observed choice data. These contributions provide new tools for analysis and prediction in critical decision-making scenarios. We present a rigorous mathematical analysis for the performance of our algorithms. Furthermore, through extensive experiments on synthetic data and real-world data, we demonstrate the scalability and accuracy of our proposed methods, and we compare the predictive power of Mallows model for top-k lists compared to the simpler Multinomial Logit model.

Hence, the following research questions arise: What is the optimal regret lower bound in contextual MNL bandits?

Choice models are essential for understanding decision-making processes in domains like online advertising, product recommendations, and assortment optimization.