Diversified Multinomial Logit Contextual Bandits

Traditional contextual multinomial logit (MNL) bandits focus on item relevance but fail to account for the benefits of diversity within an assortment, such as preventing cannibalization or satisfying user preferences for variety. Conversely, submodular bandits capture diversity but lack the structured choice-based feedback mechanisms of MNL models. This paper addresses this gap by proposing the Diversified Multinomial Logit (DMNL) bandit, which integrates a submodular diversity function directly into the MNL choice probability model.

The authors define the DMNL model, where the probability of a user selecting an item depends on both its relevance (modeled via feature-based utilities) and the overall diversity of the offered assortment (modeled via a monotone submodular function). Because incorporating diversity makes exact assortment optimization computationally intractable, the authors introduce OFU-DMNL, a white-box, UCB-based algorithm. Instead of relying on black-box optimization oracles, OFU-DMNL constructs assortments greedily by maximizing optimistic marginal gains.

The study proves that OFU-DMNL achieves a $(1 - 1/(e+1))$-approximate regret bound of $\tilde{O}(d \sqrt{T/K})$, where $d$ is the context dimension, $T$ is the time horizon, and $K$ is the assortment size. This result demonstrates that the algorithm is both statistically efficient and provides a strong approximation guarantee for the underlying optimization problem. Numerical experiments confirm that the approach outperforms existing benchmarks, offering comparable regret to exhaustive enumeration while significantly reducing computational runtime.

This work provides a practical, theoretically grounded framework for real-world recommendation systems where relevance and diversity are both critical. By embedding diversity into the choice model itself, the authors offer a more realistic representation of user behavior than standard MNL models, while the proposed algorithm ensures that this added complexity does not sacrifice computational efficiency.