Tractable Multinomial Logistic Bandits with Non-linear Utilities
Taehyun Hwang, Dahngoon Kim, Min-hwan Oh
We study the contextual _multinomial logistic_ (MNL) bandit problem, a widely used framework for sequential assortment selection. Although most existing research assumes utility functions to be linear in item features, this linear assumption significantly restricts the modeling of intricate interactions between items and user preferences. A recent work (Zhang & Luo, 2024) has investigated general utility function classes, yet they face fundamental trade-offs between computational tractability and statistical efficiency.To address these limitations, we propose a novel computationally efficient algorithm for contextual MNL 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{\mathcal{O}}(\sqrt{T})$, where $T$ denotes the total number of rounds. Remarkably, this result establishes that sharp $\tilde{\mathcal{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 contextual MNL bandits with non-linear utilities that provably attains $\tilde{\mathcal{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.