Diversified Multinomial Logit Contextual Bandits

• URL: http://arxiv.org/abs/2607.11684v1
• Date: Mon, 13 Jul 2026 15:21:30 GMT
• Title: Diversified Multinomial Logit Contextual Bandits
• Abstract summary: Existing contextual multinomial logit (MNL) bandits model relevance-driven choice but ignore the potential benefits of within-assortment diversity.<n>We bridge this gap with the $textitdiversified multinomial logit$ (DMNL) contextual bandit.<n>We show that $textttOFU-DMNL$ achieves at least a $(frac1e+1)$-$textitapproximate$ regret bound $tildeOleft(d sqrtT/K
• Score: 34.403840521131606
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.

Related papers

• Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification [39.805192541498634]
  We study optimal experimental design for multinomial logit (MNL) bandits.<n>Unlike linear or generalized linear bandits, MNL bandits have a nonlinear action space.<n>We develop a best identification algorithm for MNL bandits.
  arXiv  Detail & Related papers  (2026-05-25T08:41:56Z)
• Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs [56.28491566735463]
  Existing algorithms for episodic Markov Decision Processes yield a regret of $smashtildeO(dH2sqrtT)$.<n>We propose an algorithm achieving a regret of $smashtildeO(dH2bar_TsqrtT)$, which recovers the existing bound in the worst case and improves upon it for structured MDPs.
  arXiv  Detail & Related papers  (2026-05-19T12:39:32Z)
• Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
  We introduce a novel algorithm titled MultinoulliSCG, which is parameterfree and can achieve the same approximation guarantees as the distorted local-search methods.<n>We also present two novel online algorithms, namely, Multinoulli-CG and Multinoulli-GAGA, for the unexplored online subset selection problems over partition constraints.
  arXiv  Detail & Related papers  (2026-03-23T02:30:01Z)
• One Good Source is All You Need: Near-Optimal Regret for Bandits under Heterogeneous Noise [49.12618706309658]
  Source-Optimistic Adaptive Regret minimization (SOAR) is a novel algorithm that prunes high-variance sources using sharp variance-concentration bounds.<n>We show it achieves the optimal instance-dependent regret of standard single-source MAB with variance $*2$.<n>Our theoretical bounds represent a significant improvement over some proposed baselines.
  arXiv  Detail & Related papers  (2026-02-16T05:25:06Z)
• GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility [16.843606527688326]
  We study a novel subset selection problem called max-min diversification with monotone submodular utility ($textsfMDMS$)<n>Given a set of points in a metric space, the goal of $textsfMDMS$ is to maximize $f(S) = g(S) + lambda cdot textttdiv(S)$ subject to a cardinality constraint.<n>We show that $texttGIST$ outperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet
  arXiv  Detail & Related papers  (2024-05-29T04:39:24Z)
• Nearly Minimax Optimal Regret for Multinomial Logistic Bandit [39.805192541498634]
  We study the contextual multinomial logit (MNL) bandit problem in which a learning agent sequentially selects an assortment based on contextual information.<n>There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the maximum assortment size.<n>We propose a constant-time algorithm, OFU-MNL+, that achieves a matching upper bound of $tildeO(dsqrtT/K)$ under uniform rewards.
  arXiv  Detail & Related papers  (2024-05-16T06:07:31Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
  This paper presents a new model-free algorithm for episodic finite-horizon Markov Decision Processes (MDP), Adaptive Multi-step Bootstrap (AMB) We show AMB achieves a gap-dependent regret bound that only scales with the sum of the inverse of the sub-optimality gaps. We also show AMB suffers an additional $frac|Z_mul|Delta_min$ regret, where $Z_mul$ is the set of state-action pairs $(s,a)$'s satisfying $a$ is a non-unique optimal action for
  arXiv  Detail & Related papers  (2021-02-09T07:46:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.