Search papers, labs, and topics across Lattice.
This paper introduces the diversified multinomial logit (DMNL) contextual bandit model, which integrates a submodular diversity function into the traditional multinomial logit framework to address the relevance-diversity trade-off in choice modeling. The authors propose a white-box UCB-based algorithm, OFU-DMNL, which constructs assortments by maximizing optimistic marginal gains, avoiding the complexities of black-box optimization. Experimental results indicate that OFU-DMNL achieves a competitive approximate regret bound while significantly reducing runtime compared to exhaustive enumeration methods, thus enhancing diversity-aware assortment optimization under uncertainty.
Bridging relevance and diversity in choice modeling, the DMNL bandit model achieves a new level of efficiency in assortment optimization.
Existing contextual multinomial logit (MNL) bandits model relevance-driven choice but ignore the potential benefits of within-assortment diversity, while submodular/combinatorial bandits encode diversity in rewards but lack structured choice probabilities. We bridge this gap with the $\textit{diversified multinomial logit}$ (DMNL) contextual bandit, which augments MNL choice probabilities with a generally submodular diversity function, thereby formalizing the relevance--diversity trade-off within a single model. Incorporating diversity renders exact MNL assortment optimization intractable. We propose a $\textit{white-box}$ UCB-based algorithm, $\texttt{OFU-DMNL}$, that constructs assortments item-wise by maximizing optimistic marginal gains, avoids black-box optimization oracles. We show that $\texttt{OFU-DMNL}$ achieves at least a $(1-\frac{1}{e+1})$-$\textit{approximate}$ regret bound $\tilde{O}\left(d \sqrt{T/K}\right)$, where $d$ is the context dimension, $K$ the maximum assortment size, and $T$ the horizon, and attains an improved approximation factor over standard submodular baselines. Experiments demonstrate consistent gains and, relative to exhaustive enumeration, comparable regret with substantially lower runtime. Overall, DMNL bandits provide a practical foundation for diversity-aware assortment optimization under uncertainty, and $\texttt{OFU-DMNL}$ offers a statistically and computationally efficient solution.
