New DMNL Bandit Model Balances Relevance and Diversity in Assortments

Existing contextual multinomial logit (MNL) bandits model relevance-driven choice but ignore the benefits of within-assortment diversity. Meanwhile, submodular/combinatorial bandits encode diversity in rewards but lack structured choice probabilities. Ann, Hwang, and Oh bridge this gap with the Diversified Multinomial Logit (DMNL) contextual bandit, which augments standard MNL probabilities with a generally submodular diversity function. This single model formalizes the fundamental trade-off between relevance and diversity in assortment selection. However, incorporating diversity makes exact assortment optimization intractable.

To solve this, the authors propose OFU-DMNL, a white-box upper confidence bound algorithm that constructs assortments item-by-item using optimistic marginal gains, eliminating the need for black-box optimization oracles. The algorithm achieves at least a (1−1/(e+1))-approximate regret bound of Õ(d√(T/K)), where d is context dimension, K maximum assortment size, and T the horizon. This improves over standard submodular baselines. Experiments show consistent regret gains and, relative to exhaustive enumeration, comparable performance with substantially lower runtime. The DMNL bandit framework thus offers a statistically and computationally efficient solution for diversity-aware assortment optimization under uncertainty, with immediate applications in e-commerce, content recommendation, and online advertising.