Multinomial Logit Contextual Bandits: Provable Optimality and Practicality
This work addresses the problem of optimizing user choices in online platforms like e-commerce or advertising, offering a practical and theoretically optimal solution for contextual bandits with MNL models.
The paper tackles the sequential assortment selection problem with unknown multinomial logit (MNL) choice models by proposing upper confidence bound algorithms, achieving an optimal regret of $ ilde{\mathcal{O}}(\sqrt{dT})$ that matches the lower bound up to logarithmic terms and improves on prior results by a $\sqrt{d}$ factor.
We consider a sequential assortment selection problem where the user choice is given by a multinomial logit (MNL) choice model whose parameters are unknown. In each period, the learning agent observes a $d$-dimensional contextual information about the user and the $N$ available items, and offers an assortment of size $K$ to the user, and observes the bandit feedback of the item chosen from the assortment. We propose upper confidence bound based algorithms for this MNL contextual bandit. The first algorithm is a simple and practical method which achieves an $\tilde{\mathcal{O}}(d\sqrt{T})$ regret over $T$ rounds. Next, we propose a second algorithm which achieves a $\tilde{\mathcal{O}}(\sqrt{dT})$ regret. This matches the lower bound for the MNL bandit problem, up to logarithmic terms, and improves on the best known result by a $\sqrt{d}$ factor. To establish this sharper regret bound, we present a non-asymptotic confidence bound for the maximum likelihood estimator of the MNL model that may be of independent interest as its own theoretical contribution. We then revisit the simpler, significantly more practical, first algorithm and show that a simple variant of the algorithm achieves the optimal regret for a broad class of important applications.