Diversified Multinomial Logit Contextual Bandits
Authors: Heesang Ann
Taehyun Hwang
Min-hwan Oh
Venue: ICLR 2026 Poster (2026)
Keywords: multinomial logistic choice model
contextual bandits
diversity
regret analysis
Primary area: learning theory
TL;DR: We propose the diverse multinomial logit choice model, which directly incorporates assortment diversity, and design a computationally efficient algorithm that operates effectively under this model.

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 *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 *white-box* UCB-based algorithm, `OFU-DMNL`, that constructs assortments item-wise by maximizing optimistic marginal gains, avoids black-box optimization oracles, and provides end-to-end guarantees.
We show that `OFU-DMNL` achieves at least a $(1-\tfrac{1}{e+1})$-*approximate* regret bound $\tilde{O}\big(d \sqrt{T/K}\big)$, 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 principled and practical foundation for diversity-aware assortment optimization under uncertainty, and `OFU-DMNL` offers a statistically and computationally efficient solution.

Published as a conference paper at ICLR 2026
DIVERSIFIED MULTINOMIAL LOGIT CONTEXTUAL BANDITS
Heesang Ann Seoul National University sang37988snu.ac ac.
Taehyun Hwang Seoul National University th. www.g@snu....mm..mm.mm........w. kc.
Min-hwan Oh
Seoul National University minoh@snu. ac kr
ABSTRACT
Existing contextual multinomial logit (MNL) bandits model relevance-driven choice but ignore the potential benefits of assormmenttt diversity, while sub- modular/commiintoriaal bandits encode diversity in rewards but lack structured choice probabilities. We bridge this gap with the diversified multinomial logit (DMNLL) contextual bandit, which augments MNI. probabilities with a gen- erally submodular diversity function, thereby formalizing the sievanccediversiio trade-off within single model. Incorporating diversity renders exact MNL as- sortment optimization intractable. We propose white-box JUCB-baser algo- rithm, OFU-DMNL, that constructs assortments item- wise by maximizing optimistic marginal gains, avoids black-box optimization oracles. We show that OFU-DMNL achieves at least (1 + approximmate regret bound (dvTT/K) 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 enumera- tion, comparable regret with substantially lower runtime. Overall, DMNL bandits provide principled and practical foundation for diversity-aware assortment opti- mization under uncertainty, and OFU-DMNL offers a statistically and computation- ally efficient solution.
INTRODUCTION
Sequential assortment selection arises whenever platform repeatedly presents set of items and ob- serves a user response. E-commerce websites curate product slates, streaming services recommend set of movies, and app stores surface a collection of apps. each round, the decision-making agent chooses an assortment subject to a size constraint, the user selects at most one item (or makes no selection), and the agent updates future assortments based on the observed feedback. Because user preferences are not known a priori and must be learned from interactions with users, the problem is naturally cast as an online learning task: maximize cumulative reward while balancing exploration and exploitation.
key ingredient in this setting is a probabilistic choice model that links an offered assortment to the user's selection. The multinomial logit (MNL) model (McFadden al. 1978) has served canonical choice model for dynamic assortment learning: it represents choice probabilities through latent item utilities based on relevance, structure that supports tractable assortment optimization and clean statistical learning guarantees. These advantages have motivated substantial literature on MNL assortment bandits (Kusmevichientong et al.) 2010 (Sauré & Zeevi 2013 Agrawal al.) 2017 2019) and contextual variants that exploit user and item features to generalize across con- texts (Cheung& Simchi-Levi 2017, Ou al., 2018 Chen et al. 2020 Oh Tyengar 2019 202T Perivier & Goyal 2022; Zhang & Sugiyamal 2024 Lee & Ohl 2024 2025). In these models, un- certainty resides in the relevance-dependent utilitics, and the agent's 'ss task is to estimate them online efficiently enough to enable netrmoptimal sequential assortments.
However, practical assortment design rarely driven by relevance alone: diversity within the of- fered set is often important in practice. Users tend to value assortments that span complementary attributes (c.g., different genres, brands, or styles), while assortments filled with near-duplicates cannibalize another and provide little additional benefit beyond offering single represen-

---

Published as a conference paper at ICLR 2026
tative item. At the same time, diversity is not substitute for relevance: a diverse but irrelevant assortment still performs poorly. This creates an inherent relevance-divers trade-off. Existing MNL bandits, both contextual and non-contextual, do not capture this trade-off because under the standard MNL model choice probabilities depend on items only through their individual utilities; consequently, within-assortment interactions- such as similarity-induced cannibalization com- plementarity effects- are not explicitly modeled.
A natural way incorporate such within-assortment interactions is to model the payoff of an offered set directly through submodular objective, which captures diminishing returns and encourages cov- erage and diversity. This idea underlies literature on submodular and combinatorial bandits (Yue) & Guestrin 2011 Chen et al.) [013) Qin et al. 2014] CCen et al.] [016;; 2017 Hiranandami et al. 2020 Hwaag al. 2023), where the agent selects subset of items each round and receives reward specified by an (often monotone) submodular set function, possibly depending on context. While these models capture diversity-aware set selection, they abstract away the choice-based feedback mechanism central to assortment settings: the reward is defined set function rather than arising from a user selecting at most one item according to a structured discrete choice model such as MNL. Moreover, they typically do not couple relevance-driver utilities with diversity effects within single probabilistic choice model. Consequently, there remains a modeling gap between diversity- aware set selection and relevance-based, choice-model-driven dynamic assortment learning.
We close this gap by introducing a practically motivated bandit model that embeds diversity directly into MNL choice probabilities. A key technical challenge is that, once diversity is incorporated, the tractable exact optimization available in classical MNL assortment problems is no longer ap- plicable-the optimal assortment may require exhaustive search. Many combinatorial bandit ap- proaches (Chen et al. 2013; Qin et al. 2014; Chen et al. 2016 et al. [2016] Hwang et al. (023) circumvent this difficulty by assuming access black-box combinatorial optimization oracle with a prescribed approximation factor, an assumption that can be unrealistic in practice and that ob- scures the source of approximation. Our goal, instead, is to design an algorithm that simultaneously guarantees sublinear regret and a provable approximation factor without relying on such oracles. To this end, we introduce the diversified multinomial logit (DMNL) contextual bandit together with an efficient learning algorithm and end-to-end guarantees.
We summarize our main contributions as follows:
Novel assortment bandit model. We introduce a new sequential decision-making model, which we call the diversified multinomial logit (DMNL) contextual bandit. In this model, user choice follows the multinomial logit choice model augmented with a diversity func- tion assumed submodular in general-ttee -that scores the diversity of assortments (Defini- tion D] To our knowledge, existing MNL bandit work does not account for assortment diversity. This is the first model to incorporate diversity directly into the choice probabil- ities. The model captures practical scenarios in which greater within-assorttmnt diversity increases the likelihood of selecting an individual item for a given level of relevance, while the choice probabilities still depend on item relevance. Hence, the model addresses the natural tension between relevance and diversity-a phenomenon commonly observed in real-workds recommender systems.
Algorithmic design. We propose an upper confidence bound (UCB) algorithm, OFU-DMNL (Algorithm [.. for DMNI. bandits. The salient feature of the algorithm is an item-wise optimistic construction of an assortment: it incrementally adds the item that yields the largest marginal increase in the optimistic reward estimate. This process is com- putationally efficient and comes with a provable guarantee
approximation rate !
Regret guarantee. We prove that our proposed algorithm is statistically efficient. Under a sufficient condition on the diversity function (Definition 2 we prove that the algorithm achieves at least a (1 - e >-approximate regret bound of O (d/T/K) (Theorem 3). where d is the context feature dimension, K is the maximum assortment size, T is the total number
1 'Due to the augmented diversity function, exact assortment optimization no longer tractable as in prior work (Ou et al. 2018 Oh & Iyengar 2021 Perivier & Goyal 2022 Lee & Oh 2024 (025); hence, we must resort to approximation. Unlike existing work on combinatorial bandits, which assumes access to a black- box optimization oracle returning super-arm (a set of hase arms) with prescribed approximation factor, algorithm employs transparent, white-box construction for which directly prove the approximation rate.
2

---

Published as a conference paper at ICLR 2026
Base items in Xx
x Items in selocted ussortment St
Relevance parameter 0*
Divensity soore
MNL bandits
DMNL bandits
Figure 1: Behavioral differences between MNL bandit algorithms and the proposed DMNL bandit algorithms (d = 3, K 4). While MNL bandit algorithms select the top-K relevant items in the uniform revenue setting, DMNL bandit algorithms consider both item relevance and assortment diversity, resulting in more diverse selections whose degree depends the DMNL environment.
of rounds, and suppresses logarithmic factors. This bound closely matches that of nearly minimax-optimal algorithms for MNL bandits under uniform revenues (Lee Oh 2024). despite additionally learning diversity parameter.
Approximation guarantee. We show that the item-wise greedy construction under the DMNL model attains a stronger approximation rate (Theorem T than those established in the submodular maximization literature (Nemhauser al. 1978 Feige 1998 Yue & Guestrin 201T). Unlike the prior literature on MNL bandits where identifying the opti- mal assortment be done efficiently efficientlyffinding the optimal assortment in DMNL bandits while accounting for diversity requires exhaustive search, making approximation guaran- essential. By leveraging the MNL structure together with the submodularity of the diversity function, we obtain an improved approximation rate of at least (1 1 with- out having to rely on black- bbx optimization oracles.
c+1
Numerical performance. Extensive numerical experiments show that our algorithm out- performs benchmark methods across wide range of scenarios. In particular, even relative to exhaustive enumeration over all possible assortments, our algorithm achieves compa- rable regret while offering substantial reduction in running time. Hence, our proposed method is both computationally and statistically efficient.
PRELIMINARIES
2.1 NOTATIONS AND DEFINITIONS
We use |x||| denote the no-m of vector E Rd and |x||A VxT Ax to denote the weighted norm of x induced by a positive definite matrix A E Rdxd, For symmetric matrices V and W of the same dimensions, V > W means that V W is positive semi-definite. For a positive integer n, we denote by [n]] the set n... Refer to Appendix A for additional notation.
2.2 PROBLEM SETTING
Diversified Multinomial Logit (DMNL) Contextual Bandits. We consider a sequential assort- ment selection problem where, each round / E [7), the agent receives a set of feature vectors X, : (Xe1. X&N C. Rd which may be chosen ad adversarially. The agent then offers assort- ment of size of at most K, ie.. S, = {(.,...,4)) . E S := {S C [N] S| < K}. where < K. After presenting the assortment St, the agent observes the user's decision it E St U (0). where 0 represents the "outside option", indicating that the user does not choose any item from S. The user's selection i, is modeled by the MNL choice model (McFadden al. 1978).
In the existing MNL bandit framework (Cheung & Simchi- 2011 Ou et al. 2018 Oh Iyen- 2021 Chen al. 2020 Lee & Oh 2024 2025) the click probability that user selects
gar 2019

---

Published as a conference paper at ICLR 2026
an item depends only the relevance utility of the item and the other items in the assortment. We instead consider an MNL choice model that incorporates the diversity of the assortment.
Definition 1 (Diversified multinomial logit choice model). For each round E [T), let 9: : S - Rzo be a given monotone submodular function, where (5( quantifies the diversity of the items in the assoriment S in round I. Then, the probability of selecting an item is S, U {0} in round & is defined as follows:
xx, 0-)
(d = St) =: pi St, 0", ,') exp( X ((t) + Ejes, exp(xx,') 0*)²
exp( (xxg
P(44 = 01 St) =: p0 S. 0,, X exp(-X* + DjEs, exp(x,,0")
where 0" E Ed and X* E are unknown parameters that represent the degree of relevance and diversity, respectively.
Remark 1. Inspired by the submodular bandit literature (Yue & Guestrin 2011: Chen et al. 2017
Hiranandani et al. 2020), our model captures diversity through monotone submodular functions 9t (Definition 3] and 4. Common notions of diversity-such as counting the number of distinct categories, measuring coverage of item attributes (e.g., brands or genres), quantifying dispersion in an embedding space via pairwise distances or spectral properties of a Gram matrix natrixy exhibit diminishing diversity returns: adding item similar to those already selected contributes less than adding one from a new category or a distant region in feature space. Such measures are monotone and submodular by construction, monotone submodular functions provide a unifying and behaviorally plausible abstraction for a broad class of real-world diversity notions.
In DMNL bandit setting, the user choice follows the DMNL model. In other words, the choice feedback y: == (yro- y11.-.., yuu) follows the following MNL distribution:
Y: Multinomial(1, (pe(0) St, 0" ,""), ..... Pe( S,, ,,,0",,'))},
where the parameter 1 indicates that y, is a single-trial sample, i.e. yeo + Ek Wikk = 1.
When two assortments consist of items with identical utility values, the one with higher diversity score reduces the probability of the outside option being chosen. As result, the probability of se- lecting each item in the assortment increases, leading to a higher expected reward for the assortment. Conversely, if an assortment with a lower diversity score is offered, the outside option becomes more attractive, resulting in lower selection probabilities for the items in the assortment.
Remark 2. We note that the proposed DMNL model generalizes the existing MNL models (Cheungg) & Simchi-Leew 2017 Ou et al. 2018 Oh & lyengar 2019 Chen et al.) 2020 Oh & Iyengar| [202]] Lee & Oh 2024 2025). When the diversity function gr (c(S) is constant across all assortments, the DMNL model reduces to the existing MNL model. In contrast, the existing MNL model does not allow the outside option's 's attraction to vary with the offered set, as DMNL does.
Then, the expected reward of an assortment S in round is defined as follows:
0""(x,,0")
R.(S, 0" (A)) = Σ (i SS x') Σ
iES exp(->>g + Ejes exp(x,,"') 0*)
The goal of the agent is to maximize the total expected reward, or equivalently, to minimize the cumulative regret over T rounds, defined total difference in expected reward between the offline optimal assortment S = argmaxses (S(S, 0- x-) and the assortment S, offered by the agent.
Remark 3. Previous works on MNL bandits (Oh & lyengar 2019: Chen et al. 2020 Oh & lyen-
gar 2021 Zhang & Luo 2024 Lee & Ohl (023:20023 have also studied the non non-uniform revenue setting, where in each round, the agent observes the wise-wise revenues {ra) N. In this setting, the optimal assortment is heavily influenced by high-revenue items, making the diversity of the assort-
ment less critical to the reward. In other words, encouraging diversity in the selected assortment may not align with the objective of reward maximization under non-uniform revenue. By contrast, in the uniform revenue setting (ru = 1) we study, maximizing diversity directly contributes to in- creasing the overall click probability and expected reward, making it more appropriate objective (Figure D.. We focus on the uniform revenue setting not only for analytical clarity but also because it allows to isolate and rigorously study the effect of assortment diversity on user choice behavior.
4

---

Published as a conference paper at ICLR 2026
y-approximate Regret. In the case of uniform revenues in MNL bandit setting, maximizing the expected reward of an assortment over all sets S E S reduces to selecting the K items with the highest relevance utillity. However, unlike in the existing MNL bandit literature, such top-K K lection strategy is no longer sufficient in the DMNL model. Because the diversity of an assortment influences click probabilities, the expected reward depends not only individual item relevance utilities but also on the overall diversity of the selected set. Thus, finding the optimal assortment requires evaluating all (x) subsets, which is computationally prohibitive even when 0" and X are known. In previous combinatorial bandit works (Chen al., 2013] Qin al.] 2014 Chen et al. 2016 Li ct al. 2016; Hwang et al.) 2023 Liu et al. 2024] 2025), such computational challenges are typically addressed by assuming access to aapproximmaee oracle, and the performance of algo- rithms is evaluated via cumulative 7-approximate regret rather than exact regret. The 7-approximate regret at round is defined as R Rt,t, St) = RR, 0" x²) R₂ (St, 0* A²)) Then, the alternative objective of the agent is to minimize the cumulative y-rrerret, defined
RT(T) = Σ (1)
Σ Re,(S, 0" X2) Re(S,,
We adopt this standard evaluation metric but do not rely on an oracle. Instead, in Section 3.1 we explicitly construct a computationally efficient assortment selection strategy that serves as an ap- proximation oracle. Specifically, we show that the item-wise greedy construction (Eq,6) achieves provable approximation ratio 2 1 e+I with respect to the offline optimum, while requiring only ((N K)) computation per round. This result enables practical deployment without sacrificing theoretical guarantees.
Following prior work on MNL contextual bandits, make the following boundedness assumption. Assumption (Boundedness). We assume that |1[0", >*]l22 S 1, ||x 2|2 S and 0 S gSt)) s for all t ( E [N], and there exists a constant 1 > O such that 1 < X
The boundedness in Assumption I is standard in the MNL bandit literature (hh & Iyengar 2019
2021 Perivier & Goyal 2022) Zhang & Sugiyama 2024 Lee & Oh 2024 2025). Since focus on scenarios where the diversity of an assortment influences user choice behavior, we assume that the effect of diversity is strictly positive-i.e., the minimum effect of diversity is bounded below by a positive constant (. We note that our proposed algorithm does not require the knowledge of l.
3
MAIN RESULTS
3.1 APPROXIMATION GUARANTEE OF LTEM-WISE GREEDY ASSORTMENT
In this section, as instantiation of "-approximate oracle, show that the item-wise greedy construction can approximate the offline optimal assortment reward (S; 0", The item- wise greedy construction refers to a process that incrementally builds solution by repeatedly adding the item with the highest marginal gain. To be specific, for any k: E [K]. the k-th element added during the item-wise greedy construction
argmax Re((ai...... - Hu (a), ,')'))
ag aE[NTT
It is well known that if the expected reward function R, is a monotone submodular function with respect to S E S. the wise-wise greedy construction in Eq.(2) can achieve a (1 - >-paproxxmmatioon rate (Nemhauser et al. 1978), and that obtaining an approximation rate better than (1 {) is in- tractable (Teige) 1998..
On the other hand, since (s, 0" ,,' increases as more items are added to S, it is a mono-
tone set function (Definition B). Moreover, by the definition of submodular functions (Defini- tion the LogSumExp function of the form log (Eres exp(xx]0') is submodular. The ex- eXP(f((S)
pected reward of an assortment S can be written as R, 0" X²) = (f where f((S) := log ( exp(x]]00 + (S))))) log (Eies exp(xx]0)) )') X (S). Since fe(S) is non- exp(2) negative sum of submodular functions, it remains submodular. Moreover, [+exp(#] is non- decreasing concave function for & > 0, and it is known that the composition of submodular
5

---

Published as a conference paper at ICLR 2026
Algorithm OFU-DMNL
Input: diversity function (9:)221 regularization parameter A, confidence radius {a:)21 step
size 7), exploration parameter y
2: Initializatio: H = Ala+1 and w at any point in W.
3: for = .,...,.... T do
if a = د then
4:
5:
Randomly choose S, ~ Unif(S) with |S,] K
6: else
7:
St +-+ 1
8:
for = I,.... ,,
K do
9:
Ot.k = IN
(a})
10:
S: < Se u {ac,*)
11: Offer S, and observe V/2
Update H, H, + ge W1+1, and H4+1 Hr G((+++1)
function with a non-decreasing concave function preserves submodularity (Proposition fore, Rg (S, 0", X*) is also submodular function.
2 There-
Consequently, the feem-wise greedy construction in Eq. achieves at least a (1 - ( approximation rate. This approximation guarantee holds for general monotone submodular functions under cardi- nality constraints ([S) < K). However, we further show that by leveraging the specific structure of the MNL model, it is possible to obtain an approximation ratio that strictly improves upon the standard (1 )) rate.
Theorem (Improved approximation rate for MNL submodular function). Let Sgready be the solu- tion computed by Eq. 2 For any t 2 1, if is monotone and submodular, then we have
1 v8)) 1/ (1 + vb)
(e 0", ,0,,*)
R
where t/o is a solution to the equation x = o.r + a 1, with a = e-1"
Theorem I holds for any parameter configuration [0. A] E Rd+1 provided that both the ttem-wise greedy construction and the optimal assortment are evaluated under the same parameters. Moreover, since a crude lower bound for (o(1+v0)) is ... for simplicity,
may state that the item-wise ( >approximmte rate. This surpasses the existing (1 1) approximation rate attainable under general submodularity assumption alone. The improvement arises from the structural properties of the MNL reward function, and is of standalone theoretical interest. The detailed proof is provided in Appendix
(1++)))))
greedy construction in Eq. achieves at least (1 c+1
3.2 ALGORITHM
In this section, we propose OFU-DMNL, algorithm that leverages the optimism-in-the-fucee uncertainty (OFU) principle in estimating the unknown relevance utility and diversity parameters. The complete process is described in Algorithm I consisting of three primary stages.
Let (S) = [x.. (S)] E Rd+ diversity- augmented feature vector, and w* := 10" x+] E Rd+1 Then, the DMNL probability in Eq.(I can be represented by
-aeesstty-aggenneer parameter estimation.
exp(z Tw))
pi(i S,0" X²) =: pe S, S,w")
1+ E exp(ziş ww))
(0 S. 0¹ X²) =: p. w-) 1 jes, exp( Zzj (S) w')
Consequently, parameter estimation in the DMNL model model-namelyy namely, (0" X*) can be reformu- lated as estimating single parameter vector w using diversity-augmented feature vectors 2n, (S))

---

Published as a conference paper at ICLR 2026
similarly the procedure used in existing MNL models. Adapting the computationally effi- cient parameter estimation used in Lee & Oh (2024), we use the online mirror descent algorithm to estimate the parameter w" Let define the multinomial logit loss function at round t as & (wW) Eies, Yti log (e St, w), and estimate the true parameter w as follows:
[0++1, = We+1 argmin { (VV)) w) + 2n || will V221, wEW
(3)
where W = (w WNER. RR ||ll2 S n 0 is the step-size parameter, and H, == H. Go (wi),
with H; = A16+1 E G. (W.+1) and
Ge (e(w)= Epelt St w (S.)a.
ΣΣ pr(i St w))((i St (e,,))a JES,
iES.
Based on the estimated parameter w, and a suitably chosen confidence radius or, we have with high probability that ||w, IH,, S ag (Lemma 1 in Lee & Oh (2024)). This concentration bound enables to construct optimistic estimate of the augerste utility by evaluating it over the diversity-augmented feature vector as:
ucb(z::(S)) == X 9: (5)] w. + avel(xxs ge (S))l
(4)
Based on the optimistic utility estimates ucb(z,;(5)) we formulate the diversified optimistic ex- pected reward for given assortment S as:
Re(S): = [1s)==Emm 1+ 1+1 E exp(ucb(z.:S)))
(5)
(xp(ucb(z,(SS))
IES
As discussed Section 2.2 in the existing MNL bandits with uniform revenues, it is sufficient to construct an assortment by selecting the top-K items with the highest optimistic utility estimates. since such an assortment serves as an optimistic estimate of the offline optimal reward. However, in the DMNL model, the diversity-augmentted feature vector z, depends the entire assort- ment S, which means that the optimistic reward (S) cannot be computed by evaluating each item in isolation. As a result, identifying the assortment that maximizes R₃ (S) requires evaluat- ing (x) combinations, which is computationally prohibitive for large N or K. In the following paragraph, we introduce a computationally efficient wethod-ssrvingg as the main component of our algorithm- for approximating maxş Rg (S) without exhaustive enumeration.
Item-wise optimistic construction. As diseussed in Section 3.1
the item-wise greedy construc- X*] achieves at least (1 c+I >approximaatin to the optimal
tion using the true parameters [0",>*] assortment. However, since the true model parameters are unknown to the agent, we replace them with their estimates. In particular, sortment construction, which encourages exploration over uncertain items while preserving compu- tational efficiency. Using the diversified optimistic reward defined in Eq. 5). we apply an item-wise optimistic construction: for each k E [K],
an optimistic estimate of the expected reward guide
argmax
((((a)......-))UU ua)))
dE[NT](ar,....
This procedure mirrors the ideal greedy construction under the true model, but substitutes the un- known parameters with optimistic astimates-hents the name item-wise optimistic construction. The agent then offers the assortment S, obtained via Eq. We note that the computation complex- ity of the item-wise optimistic construction in Eq. 6) is ONN for each round.
Adaptive exploration. As the two parameters A and are estimated jointly via the diversity- augmented feature vector, their individual uncertainties cannot be disentangled. However, the joint confidence width may not provide a sufficiently tight uncertainty estimate for X alone. This loose- ness in the confidence interval may result in a failure to ensure the optimism of the item-wise opti- mistic construction in (q. To address this, we employ an adaptive exploration that triggers when the confidence the diversity parameter estimate is deemed insufficient. We show that the number of such rounds is most O (Vdlog T) (Lemma

---

Published as a conference paper at ICLR 2026
3.3 REGRET BOUND
In this section, we establish an upper bound on the cumulative 7-approximate regret incurred by the proposed algorithm. To facilitate the theoretical analysis, first present a set of technical assumptions under which the regret bound is derived.
Assumption 2 (Non-degeneracy). The feature set X, = [xi1...., XIN) spans Re for all L E (T), ge is not constant over Sk- {S C [M]
K}, i.e, 38,5' E Sk such that 9c(S) # (i(").. Definition 2 (w-strict submodular function). For E (0, 1), submodular function f is said to be S w-strict submodular if and only for every S 5' with f(S) # f(S") and every e & S', satisfies
J(S' - f(8') S (1- ( (S(S - f(8))
Assumption 3 (Strict submodularity). The diversity score function gt is monotone and w-strict submodular for some > O.
Discussions of assumptions. set (E)))EEE spans Rd++1 Under Assumption 2 there exist S2 E Ss such that 51 0 S2 * and (S,) * (S2)) Let E S1 S2. Then have [0a, 1] ((())))(((2))
Assumption 2 is used to ensure the diversity feature
(1 ((xtio> (( (etiggg((S)) This shows that the (d 1)-th unit vector [0a, E
features. Moreover, the first d-dimensional components of Rd+1 can be spanned by the set ([xo, (]bkE[N] due to Assump- feature set {[x,, ge (e)) spans R++1, With the aiversit--nugmentee feature set spanning [R++1, we can define a constant og > such that for all t E [7].
Rd+1 can be expresses as a linear combination of
tion 2 Therefore, the
X (s) (S)) ł oo
Skl
SESK
We note that this type of non- -egeeeeeyyy condition is also commonly used in prior works on GLM and MNL bandits (Li et al. 2017 Chen al.) 2020 Oh & Iyengar 2021).
The strict submodularity in Assumption 3 implies that for any S S S" and any element & S, the marginal gain of gr from adding to S' is strictly smaller than that from adding e to S. This condition more explicitly captures the law of diminishing returns than the standard definition of sub- modularity (Definition 4). Unlike prior submodular bandit works (Yue & Guestrin 2011 Chen et al.] 2017 Hiranandani et al. 2020), the DMNL bandit setting assumes that the agent does not receive intermediate feedback on the diversity score during the construction of the assortment. Moreover, the agent does not observe the marginal gain in reward for each item in the assortment, which signif- icantly increases the difficulty of learning. On the other hand, Yue & Guestrin (201T) assume access to the marginal contribution of each item after the assortment is offered, while Chen al. (2017) receive interactive feedback on the gain of each added item during the assortment construction pro- cess. Similarly, |Hiranandani et al. (2220) assume that in cascading setting, the agent receives feedback corresponding to the utility gain of adding new items to a previously selected subset. In contrast, in the DMNL bandit setting, the agent only observes the final reward associated with the offered assortment St, making the problem significantly more challenging. However, under the strict submodularity assumption show that it is possible to recover submodularity of Rg (S) after suf- ficient exploration, even without intermediate feedback. Please refer to Appendix C for a detailed discussion strict submodularity.
We first present a lower bound for the worst-case expected regret in our DMNL bandit setting.
Theorem (Regret lower bound). Let Assumption 7 2 and holld Suppose is divisible by 4 and T 2 C- d' d'((K + 1)2 for some constant C> O. Then, in the DMNL bundit setting, for any policy T, there exists a worst-case problem instance such that the expected regret of n is lower bounded as
T
(a
T
sup LEA 0,1
Σ Ra(S), R. ) 2 Ω
d
K
Discussion of Theorem 2
The theorem shows that the regret lower bound of our DMNL bandit
setting matches that of MNL bandits under uniform revenues (Lee & Oh 2024). In our setting.
8

---

Published as a conference paper at ICLR 2026
the choice probabilities depend the value of the assortment's diversity function, and therefore the existing lower-bound arguments for MNL bandits cannot be applied directly. Specifically, we consider non-constant, strict submodular 9t and derive inequality for the instantaneous regret lower bound, even though the optimal assortment includes an item that is not individually optimal in terms of their relevance scores. The detailed proof is provided in Appendix [
We now present our main result: the cumulative 7-approximate regret bound for Algorithm
Theorem (Regret upper bound of OFU-DMNL). Suppose that Assumptions
7 2 and 3hold. For any
5 E (0,1), if we set the algorithmic parameters in Algorithm as follows: de (VVdlog log K), 17 = 2 log K + 1) + 2, A = /A + 1)n, v = 2' then with probability at least 1 - ō - (d +
the cumulative "y-regret of OFU-DMNL is upper-bounded by 1)7 O stck
VK(d+1) +T+ (d (d+ 1)2 ))
Vd tw
= K+1
where K. [ 01 Pt (1) A) 0 is problem-dependent instance, and 7 2 21 )
The theorem establishes that the regret upper bound of Algorithm D it matches the lower bound for our problem setting in its dependence on d, K. and T. up to the effects introduced by 7-approximation. Furthermore, our regret bound closely matches that of nearly minimax-optimal algorithms for MNL bandits under uniform revenues (Lee) & Oh 2024). The difference lies in the dimensionality: in our DMNL. setting, the agent must learn both the relevance parameter 0" and the diversity parameter X", whereas existing MNL bandits only require estimation of 0" Despite this additional complexity, the matching regret bound implies that the proposed algorithm remains statistically efficient while explicitly accounting for diversity.
Discussion of Theorem
nearly mininax-optimal,
Unlike prior works in combinatorial bandits that model diversity through an explicit balance between submodular diversity function and an additive reward function (Chen et al. [2033] Qin al. 2014
Chen et al. 2016). our DMNL framework jointly learns both the relevance parameter 0 and the diversity parameter X As a result, our method does not require manually tuning hyperparameters to balance relevance and diversity. Furthermore, the proposed algorithm leverages weee-wie optimistic construction based on the submodularity of the reward function, achieving computational efficiency (with ((NK) cost per round) and provably improved approximation ratio-without relying on black-box optimization oracle often assumed in combinatorial bandit literature. From a technical perspective, even though the agent does not receive intermediate feedback on the marginal reward gain for individual items, we show that the strict submodularity of the diversity score function is sufficient to guarantee the submodularity of the overall optimistic reward function (S). This allows us to maintain provable performance guarantees without requiring marginal gain feedback, which is typically assumed in prior submodular bandit settings (Yue & Guestrin, 2011 Chen et al.) 2017 Hiranandani al. 2020). The detailed proof is provided in Appendix
4 NUMERICAL EXPERIMENTS
We evaluate the empirical performance of our proposed algorithm against several baselines in the DMNL bandit setting. These include existing MNI. bandit algorithms: UCB-M MNL (Oh & Tyengar 2021 TS-MNL (Oh & Iyengar 2019). and OFU-MNL+ (Lee & Oh 2024), as well as two additional variants of OFU-MNL+ adapted to incorporate diversity.
First, we consider
(Algorithm 2 which follows the existing MNL choice model but
uses a submodular reward function of the form RS (",) == Eses exp(x], (0)
I+Σ exp(x,, 0'; + >g(S), where g(S) is the diversity score and À is a predefined balancing parameter. Note that DOU-MNL-DD requires tuning manually, unlike our approach which learns diversity directly.
Second, we include SFU-DMNL--T -FUL (Algorithm 3). which exactly implements the DMNL model via exhaustive search. It computes R₂ for all (k) subsets at each round, incurring computa- tional cost of roughly O ((N) )) per round. These two variants help illustrate the benefit of learning

---

Published as a conference paper at ICLR 2026
UCB-MNL
TS-MNL
OFU-MNL+
OFU-MNL-DR
OFU-DMNL-FULL
OFU-DMNL (ours)
N-10, K=5, d=5, A '00.4
N-20. K-5, d A '-0.4
N-20, K=5, d=5, --0.4
Cumulativv Regret
40
Cumulaaivv Regret
Total Total Runlime(see) (sec)
1600
20
20
500
10
10
8000
usa Mng
75 oRvsne ontiung Mulue--o
Rounds (t)
Rounds (t)
N=50, K=5, d=5, =0044
N=50, K=10, d= =00.4
N=100, K=10, d=5, 400.4
=0.4
Curulattiv Regret
Cunulative Regret
Cumulative Regret
30
40
90
20
20
20
10030
12020
20000
10000 Rounds (1)
16030
20003
Rounds (1)
Rounds (1)
Figure 2: Performance comparison between algorithms. The top row shows cumulative regret (left
two, N = 10, 20) and total runtime (rightmost, T = 10000), and the bottom row shows the cumula- tive regret of the top 3 algorithms under various parameter settings.
diversity directly (vs. tuning it manually) and the computational trade-off of our efficient item-wiss optimistic construction relative exhaustive search. Details on the implementation of these two variants are provided in Appendix G.I
each round, the contett are independently drawn from a Gaussian distribution A( Ia) and clipped the range [-1/ 1/Vd Each item is also assigned category, ans the diversity function on an assortment is then defined as the exponential decaying categorical function (Ex- ample To assess how effectively the proposed algorithm adapts relevance-diversity trade-offs, we fix the diversity parameter > at several values. We then sample the relevance parameter 0" from a uniform distribution over [-1/Vd, /dd and scale it to satisfy ||0*|12 + X = 1. We conducted 10 independent runs for each configuration,, and all reported results are averaged over these runs.
As shown in Figure 2 our algorithm exhibits superior performance compared to the baseline algo- rithms. Notably, it achieves competitive regret performance relative to the exhaustive-search algo- rithm, DFU-DMNL-POE our proposed algorithm outperforms both OFU-MNL+ and OFU-MNL-DR across various problem sizes and under various configurations that control the balance between relevance and diversity (controlled by X, refer to Figure 5). These results highlight the robustness of our method in handling different trade-off regimes between item relevance and assortment diversity. Detailed experimental settings and additional results under various configurations are provided Appendix G
while demonstrating a dramatic advantage in runtime efficiency. Moreover,
5 CONCLUSION
In this paper, we propose the diversified multinomial logit contextual bandit, a new model that captures the trade-off between item relevance and assortment diversity. To solve this problem, design a UCB-based algorithm that incrementally constructs assortment via item-wise optimistic utility estimates. Unlike prior works relying on black-box optimization oracles, our approach em- ploys a white-box. item-wise construction strategy with a provable approximation guarantee of at least (1 (1--1) d. We further show that the algorithm achieves a (1 1 >-approximate cumula-
e+1
tive regret bound of Ö (dd/T/K). matching the nearly minimax regret of MNL bandits despite the added challenge of jointly learning a diversity parameter-hhihlighhnng both statistical efficiency and modeling generality. Empirical results demonstrate superior performance across wide range of scenarios with significantly lower computational cost. Overall, our work offers a practical and theoretically grounded solution for diversity-awar sequential recision-making
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
This work was supported by the National Research Foundation of Korea (NRF) grant and the Institute of Information communications Technology Planning Evaluation (IITP) grant both funded by the Korea government (MSIT) (No. RS-2022-NR0718851 RS- 2S-2003-00222663, RS-2025- 25421879, RS-2025-25463300 and by AI-Bio Research Grant through Seoul National University.
LLM USAGE
We employed an LLM for typo correction and grammar checking.
REFERENCES
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-bandit. In Conference on learning theory, pp. 76-78. PMLR, 2017.
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi Mnl-bandit: A dynamic learning approach to assortment selection. Operations Research, 6765::143-11485 2019.
Francis Bach. Learning with submodular functions: A convex optimization perspective, 2013.
Lin Chen, Andreas Krause, and Amin Karbasi. Interactive submodular bandit. Advances in Neural Information Processing Systems, 30, 2017.
Lixing Chen, Jie Xu, and Zhuo Lu. Contextual combinatorial multi-armed bandits with volatile arms and submodular reward. Advances in Neural Information Processing Systems, 31, 2018.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning, pp. 151-159. PMLR, 2013.
Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. Combinatorial multi-armed bandit with general reward functions. Advances in Neural Information Processing Systems, 29, 2016.
Xi Chen and Yining Wang. A note on a tight lower bound for mnl-bandit assortment selection models. arXiv preprint arXiv:1709.06109, 2017.
Xi Chen, Yining Wang, and Yuan Zhou. Dynamic assortment optimization with changing contextual information. Journal of machine learning research, 21(216):1 2020.
Wang Chi Cheung and David Simchi-Levi. Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models. Available at SSRN 3075658, 2017.
Uriel Feige. A threshold of In for approximating set cover. ACM, 45 652, 652, July 1998.
Gaurush Hiranandani, Harvineet Singh, Prakhar Gupta, Iftikhar Ahamath Burhanuddin, Zheng Wen, and Branislav Kveton. Cascading linear submodular bandits: Accounting for position bias and diversity in online learning to rank. In Ryan Adams and Vibhav Gogate (eds.), Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pp. 722-732. PMLR, 22-25 Jul 2020.
Taehyun Hwang, Kyuwook Chai, and Min-hwan Oh. Combinatorial neural bandits. In International Conference on Machine Learning, pp. 14203-14236. PMLR, 2023.
Joongkyu Lee and Min-hwan Oh. Nearly minimax optimal regret for multinomial logistic bandit. Advances in Neural Information Processing Systems, 37: 179009903-000055 2024.
Joongkyu Lee and Min-hwan Oh. Improved online confidence bounds for multinomial logistic bandits. In Forty-second International Conference on Machine Learning, 2025.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contex- tual bandits. In International Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.

---

Published as a conference paper at ICLR 2026
Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International conference on machine learning, pp. 1245-1253. PMLR, 2016.
Xutong Liu, Jinhang Zuo, Siwei Wang, John C. S. Lui, Mohammad Hajiesmaili, Adam Wierman, and Wei Chen. Contextual combinatorial bandits with probabilistically triggered arms, 2024.
Xutong Liu, Xiangxiang Dai, Xuchuang Wang, Mohammad Hajiesmaili, and John C. Lui. Com- binatorial logistic bandits, 2025.
Daniel McFadden al. Modelling the choice of residential location. 1978.
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical Programming, 14(1):265-294, 1978.
Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits.
Advances in Neural Information Processing Systems, 32, 2019.
Min-hwan Oh and Garud lyengar. Multinomial logit contextual bandits: Provable optimality and practicality. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 9205-9213, 2021.
Mingdong Ou, Nan Li, Shenghuo Zhu, and Rong Jin. Multinomial logit bandit with linear utility functions. In Proceedings of the 27th International Joint Conference Artificial Intelligence, pp. 2602-2608, 2018.
Noemie Perivier and Vineet Goyal. Dynamic pricing and assortment under contextual mnl demand. Advances in Neural Information Processing Systems, 35:3461-3474 2022.
Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual combinatorial bandit and its application on diversified online recommendation. In Proceedings of the 2014 SIAM International Conference on Data Mining, pp. 461-469. SIAM, 2014.
Paat Rusmevichientong, Zuo-Jun Max Shen, and David B Shmoys. Dynamic assortment optimiza- tion with a multinomial logit choice model and capacity constraint, Operations research, 58(6): 1666-1680, 2010.
Denis Sauré and Assaf Zeevi. Optimal dynamic assortment planning with demand learning. Manu- fucturing Service Operations Management, 15(3):387-404, 2013.
Joel Tropp. User-friendly tail bounds for matrix martingales. ACM Report, 1, 2011.
Yisong Yue and Carlos Guestrin. Linear submodular bandits and their application to diversified re- trieval. In Shawe-Taylor, R. 7emel, P. Bartlett, F. Pereira, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 24, Curran Associates, Inc., 2011.
Mengxiao Zhang and Haipeng Luo. Contextual multinomial logit bandits with general value func- tions. Advances Neural Information Processing Systems, 37:34123-34166 2024.
Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. Advances in Neural Information Processing Systems, 36, 2024.
12

---

Published as a conference paper at ICLR 2026
CONTENTS OF APPENDIX
Definitions and Notations
14
Related Work
14
Strict Submodularity
15
C.I Challenges in Item-wise Optimistic Construction
15
C.2 Examples of Strict Submodular Diversity Functions
17
D Proof of Theorem
18
Lower Bound
19
E.1 Proof of Theorem 2
19
E.2 Technical Lemmas for Theorem
22
F Regret Upper Bound of Algorithm 1 (OFU-DMNL)
24
F.1 Technical Lemmas
24
F22 Proof of Theorem 3
27
Experimental Details
28
G.1 Baselines
28
G.2 Experimental Results Diverse Environments
29
G.2.1 Runtime Comparison
29
G.2.2 Regret Comparison
29
G.3 Experiment based on real-world Data
31
Auxiliary Lemmas
31
13

---

Published as a conference paper at ICLR 2026
A DEFINITIONS AND NOTATIONS
Recall that we define N as the total number of items and as the set of candidate assortments with size constraint of at most K, i.e., S = {S C [N] :S| K).
Definition 3 (Monotone increasing set function). The set function f mapping sets S E S to real- valued number monotone and only for every S. E S with S C S', satisfies f(S) S f(S'), Definition 4 (Submodular function). The set function f mapping sets S E S to real-valued number submodular if and only for every S _ S' and e @ S
number
satisfies
f(S' U (e}) f(S'
f(S).
Or, equivalently, for e1. C2 $ S, we have
f(SU(e))) - f(S) 2 f(S u (ee))
f(S
For convenience, we provide table summarizing the notations.
Table I: Notations
N
total number of items
K
maximum size of assortmens dimension of feature vectors number of total rounds
d
9t
diversity score function in round
Xii
feature vector for item i in round
(S)
X (e() diversity-augmenti outside option in MNL choice model
feature vector for item in round
O
min s. la 1,05A1 Pr(i) 0, (0) 0, >
S.
selected assortment in round / optimal assortment round
ST
yes
user's choice for item i Se U {0} in round t
RA 6" x²)
Eiss (i S, 0", X²), reward of the assortment in round Lies, Vu log Pe(i / Sc, w), loss function in round f (2)((w)
((w)
G.(w)
Σ pe(i Se, (S:)) - Σ Σ pi(i St, w)p(i St, JES:
FESt
regularization parameter
H,
= Al + -E- G. (w.+1)
H,
= :H,, + -H,+ (n,
V
-AI + Eies. Zoi (S.)) gram matrix
on
confidence radius
ucb(za(S))
(S) W. ael a (S) H.
R((S)
Eies I+Eees exp(ucb(2,,
exp(ucb(a., (5)))
f(())
log Eissexp(x],
(S))
F((S)
log Eies exp (u(())T a Iz (()()))),;)
B RELATED WORK
Contextual MNL bandits. The MNL bandit framework- applies the MNL choice model
to dynamic assortment optimization has led to significant progress in sequential decision-
making (Rusmevichientong et al.] 2010 Sauré & Zeevi 2013 Agrawal et al. 2017: Cheung &
Simchi-Levij 2011 Ou et al. 2018 Agrawal et al. 2019 Oh & Iyengar 2019 Chen et al. 2020
Oh Iyengar 2021: Perivier & Goyal 2022 Lee & Oh 2024; Zhang & Sugiyamal 2024 Les &
Oh 2025) Early results established the statistical efficiency of UCB-type (Agrawal al. 2017
14

---

Published as a conference paper at ICLR 2026
and Thompson Sampling (TS)-type (Agrawal al. 2019) algorithms, while Chen & Wang (2017)
derived lower bounds for the MNL bandit problem. The contextual MNL bandit was introduced
by Oh & Tyengar (2019). who proposed TS-type algorithm with provable guarantees, followed by UCB-type algorithm (Oh & Iyengar 2021 achieving ((vdT/R) regret, where K 0(1/k2)
is an instance-depender parameter. Subsequent works refined the theoretical analysis: ( Periiier & Goyal (2022) derived tighter regret bounds, and Lee & Oh (2024) (225)) proposed computationally efficient algorithms with nearly minimax guarantees. However, despite these advances, no prior work has incorporated diversity into the MNL bandit model to better reflect user preferences for varied assortments.
Submodular bandits and combinatorial bandits. Handling the computational problem via the submodular reward function in bandit setting is first explored by Yue & Guestrin (01TT). They introduced the linear submodular bandit framework, in which the reward of a set of items assumed by linear combination of submodular set functions. Built on the fact that by using submodular reward functions, wise selection (iteratively adding one item at a time in a greedy manner) for set construction guarantees the approximation rate (1 - _) for submodular rewards (Nemhauser et al. 1978), they suggest an algorithm that item- wem-wisely selects items during set optimization and proved theoretical bound for their algorithm with (1 ) )-approximate regret.
In the submodular bandit framework (Yue & Guestrin 2011 Chen et al., 2017; Hiranandani et al., 2020), the set of items is either ranked presented sequentially the user, and the probability of an item being selected depends on its marginal gain relative to the previously presented items. Especially, |Hirananaani al. (2020) proposed cascade variant of the model suggested by Yue & Guestrin (2011). It is notable that these settings are fundamentally different from the assortment bandit problem we study, since the feedback is determined by a user choice at the end. While we aim to exploit submodularity to design computationally tractable algorithms, unlike in submodular bandits, we cannot leverage information about the marginal gain obtained when items are added individually. Therefore, whether the optimization advantages of submodular diversity functions can be applied to the MNL framework remains an open direction.
In the combinatorial bandit framework (Chen et al. 2013 Qin et al., 2014; Chen et al. 2016 Li
jet al. 2016; Hwang et al. 2023), the reward of a set of items defined as a function of the rewards of the individual arms, which allows optimization to exploit properties of the set such diversity. However, the key difference from the assortment bandit is that the expected reward of each individual item is unaffected by the other items in the set; consequently, tasseuuendyy.hhn the properties of the set influence only the reward, not the choice model. In particular, when modeling diversity within the combinatorial bandit framework, the diversity parameter must be given in advance hyperparameter. This is fundamentally different from our setting, in which diversity is embedded into the MNL. choice probability model and the algorithm must estimate the corresponding parameters.
C STRICT SUBMODULARITY
C.I CHALLENGES IN ITEM-WISE OPTIMISTIC CONSTRUCTION
Lack of intermediate feedback. In the item-wise optimistic construction process in Eq. when selecting the k-th item a, (for k E [KD, the current partial assortment consists of the previ- ously selected items 0g.1 a (Line 9 in Algorithm MT. Therefore, the optimistic diversity- augmented utility in Eq. is computed using only the diversity score of the partial assortment, g(far,1..... a)). However, the agent does not receive any feedback about the diversity score at the time of item addition, nor does it observe the marginal gain in reward for each individual item- item-even even after offering the full assortment. Instead, it only observes the total reward associated with the final constructed set S, = {a..1...... ",, ). This lack of intermediate feedback complicates the analysis of regret, particularly in submodular bandit settings that rely on item-wise optimistic construction.
On the other hand, prior works on submodular bandits (uue & Guestrin 2011 Chen et al. 2017 Hiranandani et al. 2020) assume access to intermediate feedback on the marginal gain of each item during or after the construction of an assortment. For example, Yue Guestrin (201T) receives slot-level feedback after offering assortment (i.e., list of articles), which enables the agent to
15

---

Published as a conference paper at ICLR 2026
estimate the marginal utility contribution of each item. Similarly, in the cascading bandit model of Hiramandani et al. 2020), items are presented in a ranked list and examined sequentially by the user. This naturally reveals the marginal utility of each item conditioned In [heen et al. (017)) the agent receives explicit "interactive feedback" on the marginal gain of each newly added item during the construction process, making the feedback even more granular. We also emphasize that this challenge does not arise in the combinatorial bandit literature (Chen et al.) 2013 Qin al. 2014, Chen al., 2018 Hwang et al. 2023), where the diversity of selected arms incorporated solely through the reward function. Since diversity is not parameterized in those models, there no need to estimate any diversity-relater parameters during learning.
the items already shown.
Beyond submodular diversity, One way overcome the intermediate feedback problem to exploit the submodularity of the diversified optimistic expectd reward in E5.(5). For an assortment S, let define (S) as follows:
F.(S) log Σ exp (S) w. a a.Ilzn(())l
We note that if F(()) is submodular, then we show that the assortment St constructed by the item- wise optimistic construction can approximate the true optimal assortment of fi, making it possible to establish bounds without relying on feedback on marginal gain. However, unfortunately, while the submodularity of Gr guarantees that Sa is submodular (Section 3.1, it does not ensure the sub- modularity of ft-
To check whether is submodular or not, for any {er}. S2 = U (e2), Sz := S (2), Then,
S, and 61,e2 & S, define S = SU
F((S)) - Fc(S) (F((Ss) T.(52)
Eies, exp xx]00=- + 'x.s (Si) + at Xtss ge (S1)))lle
log
Eies exp
xx]00== (e) at Xtii So (c() |H,"
Eies, exp
x1100 + )ıgo (82) + 04 | 9 (52)]lll;;
X
EiEs, exp
0, Aug (8a) + ||x, (Sa) H,
x2 0. + xT.0 0, ( (S1) + (S2) au (I[xi (ell))((S))])) H, ||[ 9 (S2). ||, :))
Σ exp
iES.E8;
llog
Σ exp
X 02 x 02 + (S) )eg a (1(xt(+ Meeeegee(e (c)))) || (Sa))ll (Sa)llH,
iESJESs
T
0, + x 0, + Seg (Si) + (S2) + az (I[xxec De (e(S)))l + [1 9r (S2) H.
exp
0x + x 0, + (.) du (Sx) + (1 9e (c))))l + ||[x,j 9r (Sa)ll
exp
As in prior approaches to ensure the submodularity of the LogSumExp function, one would need to show that the numerator of the first term inside the logarithm larger than its denominator. However, this does not hold in general. In general, even though g is submodular, the following inequality does not hold:
(9) Specifically when j1 j2 j. we can prove that the left hand side is negative, since the weighted norm has convex structure. This means that the item wise optimistic construction cannot, in gen- eral, guarantee (1 ) optimality with respect to f.. However, show that the submodularity of f. can be recovered the diversity function 9, satisfies w-strict submodularity, as established in Lemma
||x De (S:)ll + [|xx Sr (S2)lll ! ||xx,, g. H. 1 || gelza.ge(S5) (c
16

---

Published as a conference paper at ICLR 2026
C.2 EXAMPLES OF STRICT SUBMODULAR DIVERSITY FUNCTIONS
In this section, we present several examples of strictly submodular set functions that are applicable wide range of practical settings.
Example (Categorical functions). For a given item set S, let ng denote the number of categories that can be covered by S, i.e., the size of the set of categories to which the items in S belong.
(i) Exponential decaying case. Consider the case when an item from the m-th new category is added, the value of (p(S) increases by pmt for p E (0, 1). Then, the diversity function is defined by go(S) = p p² +.... pas-- and is (1 p)-strict submodular.
(ii) Polynomial decaying case. If the diversity function is defined by gn(() == (ng) for 2M
E (0, 1), then, (a(S) is (1- (1-(2M))) (2M+1) 1--
--04))1000 ) -strict submodular, where M is the maximum
number of categories.
Proof of Example We define M as the number of categories, c(i) [M] the category that the
item i E [N] belongs to, and c(S) == {c(i) E S} (Jc[S) ng). Let S' = = fe'), e e S'. To
show w-strict submodularity of the set function g, is enough to show that if g(S) * g(S),, then the following holds.
g (0)))-9(55) < (1- -
(10)
We first show that for any PE (0. 1). the exponential decaying categorical function 9p is (1 p)- strict submodular. Suppose that S and S' satisfy (p( * (S"). Then, by the definition of 9p- e(e') E c(S). Thus,
9p(5) = 1+ p - + p
95(5)) = 1+ p+ + tps
If c(c) c(S), then (SU (c)) (,( = = 9 U (et)) (S(). Else if c(e) E c(S)),
iec c(e) = c(E'), then (S (,( pss and (S" U {et) ) go(5") = 0, and hence the
inequality (*) holds for all w (0, 1). Otherwise, if c(e) $ c(S'). then
9 (U - (e))) pd
( -c))) past1
and so, (p U (et)
- (e)) (S)) holds for w 1 p.
For all cases, the function 9p satisfies condition in 10 for w 1- p. and therefore is (1 p)- strict submodular.
Secondly, we will show that for any a E (0, 1), the polynomial decaying categorical function go (1 (2/41) 1-a) -strict submodular. By the same reasoning as in the exponential decaying case, it suffices that condition (*) holds for
(1 2M only when c(c') c(S")e((S) and
2M-+1
cle) $ c(S"). ofe(e ((S)) and c(e) & c(S'). then
(S (e}) (S) (ns + 1) (ns)
(S' U (e}) 9. (S") = (ns + 2)a (ng + 1)a-
Let h(x)) = x² for a E (0, Since is a increasing concave function, h (I + 1) < h(r + 1) h(x)= < h1(x + ) holds. Thus, (ns + 1) (ng) ins+1) and (ns + 2) (ns + 1)a
(ng T hold, and hence,
go (S) - (S) 9a. (SU (S)
(ns + 2)a (ng + 1)ar
(ns 1)00 (ns)
(ns + +1)1=a
(ns + 1-1--a
(1 + 2ng+1]
2M 1-a
2M +1
17

---

Published as a conference paper at ICLR 2026
1-a
Therefore, the function Ja satisfies condition in Eq. for --(1)
2M
and therefore it
(2M+1)
is (1
2M 2M++
)-strict submodular.
Example 2 (Categorical level functions). For each item [N], let c(i) E IR- be the calegorical feature vector of item i. Each category m E [M] has n'm levels, and the m-th entry of c(i) has
value of Cm (i) {0. __
Thm 1}. Define c(S) == Eme(M; maXies (i(() be a sum of
1amm nm ..... nu
categorical level-coverage of items in S. and for p (0, and 0, 9p.x(S) = =k(1 pp(s)) be
a categorical function on S E S.
Proposition 1. For any p E 10 and & > O, Ip.k is (1 pA)-strict submodular, where A
mi[ 7.m
[[A Ylom
Proof of Proposition 7 Let S' = S (e') and e & S To show strict submodularity. it is enough to show that if gp. + (S'), then the following holds.
9p.x(S' u (e]) (S* S ( (c]) 9p.x (
(11)
Suppose that S and satisfy 9 (S) + I (S'). Since h(x) k(1 p²) is one-to-one function, we have c(S) # c(S"). Then, by the definition of A, it holds that c(S') - c(5) 2 A.
By the (level-coverage) definition of the function c, e submodular, and hence,
c(S' U ((')) c(S") c(S -c())
(12)
Then,
g U (c}) g(S)) = (1- - pass (As')(e))) 1: (1 -(()))))
(p(s)) -pasrusett)
ho (prs)) {
(:p< < and Eq.
12
kp((s)) (1 (1- (1-p(sutet)-a(1)
1 (1 (1-)(SU(e))-a())
(:p<1 and (od c(8) + A)
-pp (Do(S) - -po(su(e))
-kp [(1 - polsu(el) (1-poisutet) - -(1 [
(g(S' U (et)) -S(')),
which results in that is (1 ~ J-sricc submodular.
Remark 4. In Example
we simply use c(S) == Eme(py max,es Cm (1) and gp.((S) Mc(S))
where h(x)= = k(1 p²)) However, if c is of a form with minimum increase (e.g.. max or sum) and
h is chosen as strictly concave function, then g h(((S)) becomes w-strict submodular for some E (0, 1).
D PROOF OF THEOREM
Proof of Theorem
For an assortment S E S, let us define fo(S) as follows:
fi(8) llog Σ exp((xT00' +X))(())) JES
log
Σ Eexp(xT00)) (S).
(13)
jES
Also, we abbreviate Rs X*) RS). If we let e/v (f )), then, by the definition
of fc.
(Sprecd))
2
+
18

---

Published as a conference paper at ICLR 2026
By the additivity of submodular functions, fi is monotone and submodular, and hence the greedy solution for maximizing fi can achieve (1 - - approxxmmaaio rate (Nemhauser et al. 1978). which means
fe 2 (1- 2) (((::).
Therefore, have
exp 6-1 f(((prood)))
exp(J+(5;))
4/
((() = 1+ cxp(f((S))
( fe(Sfreatt))
1 1 4/6
1 1 exp
where we denote a e-1' To get the approximation rate, we want to bound the below function
1(v)) = (1 15a0 (1+ (1
v5 (1+ w)) 11 20)
Since ('(b) t x 16ah (-1ba + axp + (a - 1)), the equation 1+(1)) = has a unique
solution vho > O, which the maximum point R4. Since h has the maximum at tho in R2,,
Rs(S))
2//2t 1 + 4//
)
4/2
h(t))) h(vo).
R2 (Stroddy
1 + 1/
which implies that
voo 1 v0 (s())).
R2 ( (preedy
(S,)
h(v0))
2/ (1 + vo)
Since vho satisfies v/6 = onbo + (a - 1). we have vho > and hence,
V/ + vo-
anto + (a - 1) + avd + (a 1)200
(()0))
1/ v/n wh+
to + a + (ax 1)y'0
0 + (2xx 1) + (a- (a- - () +1
a a-1 03/o
and + anto
anto axdo
1
< -1+-
1 is greater than e+1 which results in Therefore, the approximation rate A(po]
(1 1-e+1
(&(S)) < h(1b))
R((S)) S (S
e+l
E LOWER BOUND
E.1 PROOF OF THEOREM 2
The proof closely follows the lower-bound arguments developed for the MNL bandit setting (Chen et al. 2020 Lee & Oh 2024p. However, unlike the standard MNL setting teeting-hhere where the diversity function g can be treated constant- framework imposes Assumption which prevents from being a constant function. Consequently, we derive a lower bound where g is non-constant and strict submodular.
19

---

Published as a conference paper at ICLR 2026
Proof of Theorem 2 Let À 1/2 and (0, (0.1/d//3 that will be specified later. For every subset
V [d,, we define Oy I2 as [0vl; for j and [0v], for V. and θ := (0v :
V C Vajah where Va/4 = {V c [d] |V| = 4). Then, for E Va/4. | S
2
We consider the K x Vayal context vectors invariant across rounds t. For each U Vaja. there identical K context vectors with feature zU. where [ævly = 1/vā for j E U and (xuly = for
j & U. Then, for U Vay4, || - = 2'
0). We define g(5) = 1 only there exists U Uo such that xy S, and otherwise (i.e. S contains only xn 's), set ( 0. Then ! satisfies 0 < (SS) S (Assumption TD. Since ((o) 0 for So = (zn....,,4) and g(S) for all * So with size k. g satisfies Assumption Furthermore, g monotone and strict submodular for all w E 1).
Let Uo- = [d/4] E Va/a and Eo == DUo = ( Va J va. 0, 0,.....))
Since the worst-case regret in the worst-case problem instances is bounded below by the average of the worst-case expected regret of parameter instances in θ, we obtain
sup Σ7,A [R(T] e, A)] = sup Eg 0,2
Σ
Ro(S; 0, A) (.(...0.A)
0,
Σ
Σ
0. R.(S,, 0,1)
[ajal VEVaya
Let (5:)== be sequence of assortments generated by т. For a fixed V, we define 5t = {-T, ("o,...., I as the assortment that contains an identical feature vector tū,, where Tú. urgmax.yes, oT.rr. Furthermore, we simplify notation by Ev == E and IPv = Pa Ov.d
By Lemma for any V E Va/a. we have Pr(i] Ov, - Eiese Pr(i)S,, Ov, A) 2
(K- Sc where ō = d/4 - 10, VI. Thus, we have that
172 Kejz 2vd
Σ
Ey
Σ
Re(S7 0, Re(S.,
Va/4
VEV4/4
Σ
Ev
Σ
Σ
Ov,
Vajal VEVU24
LiES-
iest
1 11/2(K 1)
E(j/A-1unnD))
T
Σ Ev
Vajal (6-1/2 + Ke)2 2vd VEVa24
2 1/2 Ke)² 2vd
1/2 1) JT
1
Σ
Ey
Engets) |])
Majal
VEVa/4 jeV
For V, we define the random variables M, = Σt 11 ú.j. Then, the right hand side is equal to
(K 1) E
df
Σ
Σ Ev M₁)
1e-1/2 + Ke)² 2/d
4
Dajal
VEVAJA JEV
e 1// 1)
df 1
Σ
Evuid M,
1/-1/2 + Ke)² 2/d
Dajal
VeVafa-1jEV
1/2[[K 1)
dT
(Vas-2ll
1/2 + Ke)² 2/d
4
[V/44
max VEVaj4-1
Byol M₁
jēV
20

---

Published as a conference paper at ICLR 2026
1//KKK -1) E
df
[aaa-1l
(e-1/2 + Ke)a 2vd
4
Vaaal
VeVais-1
max
Σ Ev M₁ + Evugt
M3
- EE MM)
jeV
(K// -1) <
dT
dT
max
Σ
Eveis
Ma
Ev M1]
11- + <ke32vV
4
3 VEVa/4-1
jØV
1//(KK - -)
dT
(e-1/2 + -Ke)
6
max VEVa/4-1
Σ
ByUG
M₁
BBv M₁
jæV
e (11/ 1) c
dT
max
Σ
Brug) M₁
Ey
M1
(e 1/2 + Ke)² 2/d
6
VEVa24
1/1 - 1) E
dT
(e-1/2 + Ke)2 2
6
max VEVa/A-1
Evug)
M₁ - Ey
Mr]
3=1
We bound maxv EVa/1-1 Ejev Evuus of Mj. we can bound
My
Ev M₁
using KL divergence By the definition
Evub3
Mj
Ey
M2
Σ
Pv
Mj = $) Prucs M, =t] :]
T
M, = . - -Prucs [M, = $]
Pv
t=0
< sup [Pv (A) (A))
ST. (L(P///Pr))))
where the last inequality holds by Pinsker's inequality.
By Lemma we have KL(Py (IPv/IPruugg (|PPuu)) S C
K (1+K)=
Ey M,
for some C' > 0. Therefore,
c 1/2 1) c
dT
d
max VEV4/4
Bru
M₁ - Ev M
(e-1/2 1/2 + Ke)² 2dd
6
3
==1
1/2(K - 1)
dT
1
d
2 1/2 + Ke)z 2Vd
Σ
T
KL(PV
6
3
2
j=1
c1//2KK 1)
dT
Tvd
(L.(P/PPru)))
(e- 1/2 Ke)² 2dd
3
2
j=1
(1/ 1)
dT TVd
d
K
Ev
62
Σ
C
162 + Ke)
6
3
2
(1+
K)²
d
j=1
11//2(K-1) 11)
dT
TVd
C
K
d
dT
Tea
(:
E
Mr
<
1/2 Ke)² 2
6
3
8
(1+K)²
K)²
4
j=1
By setting
d
(1+K)²
finally have that
2CT
21

---

Published as a conference paper at ICLR 2026
T
sup _ [R(T] AJ] = -uup D.A 0.A
Σ
R, 02 O.))
0.2
1/1/2(K 1) E
di
TVd
C
K
Te2
1/2 1/2 + Ke)² 2Vd
6
3
(1+ +
KY²
c 113(K - -1)
(1+ K)²
dT
dT
(e-1/2 + Ke)² V 8CT
K
6
12
= Ω dVT
VK
E.2 TECHNICAL LEMMAS FOR THEOREM 2
Lemma 1. FixE (0,1/d/))) X = =. and V E Vaja and define 6 = d/4 10, n VI. Then,
e-1/2(K - 1) &c
Σ iES*
Pills 0v, Σ 0y.
(e-1/2 + Ke)² 2vd
EES
Proof of Lemma 7
We split the proof into two cases: (i) V * [d/4]. and (ii) V = [d/4].
Case 1. + [d/4].
We recall VG, == argmax Tv.v. If = 0, i.e. U. = V, then the lemma holds trivially, thus we suppose that + O.
V * [d/4]. is obvious that S = fIV...., vV3 with g(S*) = 1, and so we have
Σ pe(ils",Ov,A) - Σ NES-
EE
K (exp(xTdV)
K (exp(xT 0v)
U.
e 1-1 + K exp(xx(0v)
exp Ao((e) + K exp(x 0v)
K Kexp(eTOv)
K Kexp(x I 0v)
U.
(S)) 1)
c 1/2 + K exp(x c <12K(cxp((TBVV exp( θv))
exp 1/2 KK exp( c. 0v)
112 1/2 + K exp(xx)0)) 1/2 +K exp(x 0v))
c 111/2 (<x/2(( -xp(( cxp(x 0v))
(: (xpp(x]OVv) sev E Vaja)
(e-1/2 + Ke)²
6 1/22 - Xx,)² T 0y (xT, 0v)3/2)
(:1+asse 0 s1+a+ a² /2 Ya E (0, 1)
(e2 + Ke)²
1/2 Vd - (Vde)2/2)
11- + Ke)?
(: (Vde)) s (V < Se//Vd)
2/d(e-1/2 + Ke)²
c11/2(K- - 1)8c
2/d(le 1/2 + Ke)²
22

---

Published as a conference paper at ICLR 2026
Case 2. V = [d/4].
We recall that g(5) = if S contains only zV, 's, and otherwise g(S) = For V [d/4]] = Up-
since g( =o...... .20) O, have to compare whether it is better to fill only zo 's in S add another zz in 5", because g(S*) becomes in the second case. Specifically, since the following
inequality holds:
( K exp(x) Qv,) K exp(2x0 Qv,)
< e (K 1) exp(=o) 0v.)
((K 1) exp(2g Qv.) 0v.))
26 we obtain that S {IU, ................................ Fuy 26, for I0' [d/4] 4] d/4 1, and g(S))
zn E Sr, then U, = Un = V. In this case å = 0, and the lemma holds trivially. Thus, we suppose that $ St. Then, g(Si 1, and we have that
Σ Pr(iSS",yr A) Σ
Pr (ilS,, Ov,
E
SES*
e1//2 1/2
-11 1/2 + exp(x U. 0v)
e-122
1
e-12 + (K 1) (1) 0v) + exp(xx
(K 1) e 0v) + exp(xT..0v) K Kexp(1t 0v))
1/2 -1/2
e
(e-1/2 + (K - 1) ex) vv) + exp (lxpp--
1/2 +K exp [3)] Qv))
(K - (e)(xx(x( 0v) - exp(2 2 0v (exp)) - exp(x T U. θv))
=e 1/2
(e- 1/2 Ke)²
Since Ü, * V and U' satisfies I0" n VI = d/4 1, we have that exp(x1. 0v) exp(x 0v) 2 0. Thus the right handside is bounded by e 1/2 c/ 1)(exp(x:T00) exp(2r U. 0v))
(e- + Ke)²
vo(K 1)( - XT,) (x,,) Toy - (v)222)222)
(.1+a $lltasesltttd// / va [0,1])
(c- 1/2 Ke)²
Vo(K (8cc/V/ - (Vdc)² /2)))/22)))))))))))))))
10-1/2 + Ke)2
Do -o(K-1)e 1)88
(:: (Vde)2 se/Vd s de/va).
2v + Ke)²
Lemma' 2 (Bound on KL divergence, Lemma D.2 of Lee and Oh(2024)). For any V E Vaj4-1 and
j E [d]. there exists a positive constant C > O Duch that
K
Ey
M 2
(L(PP](PPve)) SC.
(1 + K)²
d
Proof of Lemma 2
In the proof of Lemma D.2 of Lee and Oh(2024), the following holds for some O.
positive constant
v (S,)ee
(L( (.) II P S.)) s C
(to + KY² d
where m55()) = Mij E Ü.), and up is outside option parameter, defined as exp( (Sp(-) in our setting. Since o(S.) has value of 0 or have that
K
my(S))e
KL(Pv(- 3.) || Prunn (.)) SC
(1+ KY²
d
23

---

Published as a conference paper at ICLR 2026
Therefore, by the chain rule of relative entropy, we have that
7
KL(PvI|PuGG)) = Σ By
[L
5.)
Prun
(.)
Ey mz
c²
K
$
C
(1+ KY²
d
By Mj
d
K
(1 + K)²
d
F REGRET UPPER BOUND OF ALGORITHM
T
(OFU-DMNL)
F.1 TECHNICAL LEMMAS
In this section, we introduce technical lemmas used to derive the regret bound of Algorithm
!
Lemma 3. Suppose Assumptions/ 7 and 3 hold, and set = in Algorithm
!
Let us define the
event T as the set of rounds corresponding to adaptive exploration, as follows:
whe
T t [T] 11 111
(14)
20k
Then, for 14 To, Fe is monotone and submodular where Fo is defined as follows:
Ji(S): log Σ exp (S) w. + (r)l)
log Σ exp (ucb(zu(S))
ViES
wee holds.
Proof of Lemma
3
Suppose |I 1|11 1||
1
201
Monotonicity.
Recall that the diversity-augmentt feature vector is defined Z;;(S) [X (r)].. Then, F. {i)) F.( can be written as follows:
Eyes exp (ucb([xr,,99 9 (i)))) exp (e (i))))
((()) = loog
Ejes exp (ucb([Xi,, (x (S))))
Then, for each S we have
ucb([xij.geG IS u (1)))) (ebbxxi)99(()))
= - (i}) - 9c())) + a: [[xxs]) (i))) H. [[xx))..e
ge (S))))
Se (i}) 9.(5)) a.
(i}) ((())]l
= -Aer - at Illoa. 11lle (o((S (1)) - (S))
2 (1-55 w ) ( (i)) - (S)) 2 0,
where the last inequality holds since [|0a, 1 ||| Fi(SU - >
wÅ. Zac
Therefore, we conclude
24

---

Published as a conference paper at ICLR 2026
Submodularity. To show submodularity of ft. it is enough to show that the inequality in Eq. holds. If (e( = (12),, then 9r (S1) -9: (:( 2 gr(Ss) - (c( by submodularity gt. and so
ge (S S ge (Sg)). By the monotonicity of 9t, have gr (S,) 9r (S²). Therefore, the inequality in Eq. holds
Now, suppose (s) (1())) Then, for all j1 S and j2 E S3, have
de (S:) + (( (c(S) (S
100-11[xp [[xx,,1 1e (c(S)) H,, - ||xx,,j I (5)) (7)) 2 Å (or(S1) - 9:( (g: 9: (S2))) (S)) 9c(5)) |1 1]HH,,
+a (1[x).) (r H. + ja Dr (S2) |
H," -
as())(S3) (e()) I1 11IH,
9: (S)) (11)
(S) - (c()) |1[0 H!
mNw 20
(gr(S)) - (s)) 2 0.
2011
Lemma 4. Suppose that Assumptions 7 and 3 hold. If Amin (H,))HH) 2 97 (1 + 2). we have L $ Te.
Proof of Lemma
4
Suppose that Amin (H,) (5) (1 B). To show t $ T we have to prove
wie
that [1 1]I S
By the properties of eigenvalues,
20r(())
1 [00a, 11l S Amax (H,') Amin (H,) S (2 (2+
(2 + w)r(())
Since X" = 10a, "0",0,"7 < 10a, 11 (0,, 2e) + a=lll0a 111 11
S d, + a. 0a. 11 H, by
Lemma 7 then we have
Oa. 1|| S (me + aell(0, arl(0,,))ll
(2 + w w)
(2 + waa d 2 l100a H,
By subtracting zía 11 I|]la the both side, it follows that
1
[1(0a. 1|||, S
(2 (2+ A
2 + w
and consequently,
[10a 1], S wit
2a
Lemma 5. Suppose Assumptions 7 andd hold. Let r = T n [4] denote the number of adaptive
exploration rounds up to round t. Then, with probability at least (d + 1) exe
(- Tap ). we have:
Amin Σ Σ 2ez(Sz)
KKoo
>
2
where on is defined in Eq.
25

---

Published as a conference paper at ICLR 2026
Proof of Lemma
Let He be the history {{Xy (ee()) (Se teejt ter breet) until round t. By for any adaptive exploration round 1'' E T n [t] we have
Assumption
(rr(Sv)ar 1He- ( 1)
Ze: (S)))) (2r
Amin
E
Σ
=
Amin
E
Σ
Σ LiES
Zes 2es(Se)) (2 (er
Amin
[
SES
2 Koo
Then, by the subadditivity of minimum eigenvalues,
Amiin
Σ
E
Σ JESP
aec(Se)
)er((S))ee (Se) (St))(HH
Amin
Σ
E
2e (Se())((())))) TIH
1=
MET
FES
Amin
E
Σ
zur(Se (z(((e))((()) (
MET*NI
iESy
1T n [t]]
Koo
-Koo
In other words, IP Amin EE E EveS, (S Zr ( (1H 2 -Koo) = holds.
By applying Lemma 8 and Amax Eves, ze )ze Meei(S;) (T) K for all l' E [4] to compute the lower bound of the minimum eigenvalue of the Gram matrix after rounds, we have
P Amin
Σ
Σ
Zr: Zr:(Sw))(:(Se)
TKau
< (d+1) (
0.5
~800 K
< (d + 1)e
T4p 10
2
0.50.5
f'=1 NES
using the fact that -.5 (.g) -0.1.
Lemma 6. Suppose that Assumptions
v and hold. we
we set v = in Algorithm 1 then for
Puva sklx=
8 E (0, 1) with probability 8 (d 1)7
the total number of adaptive exploration
rounds is bounded follows:
(dlogTlogy K kKowwl
=1=0-
Proof of Lemma 6 We will show that the number of adaptive exploration rounds can not exceed 20r klKoo
(1+ 2) rounds by contradiction. Suppose Algorithm |
induces klKoa
2ar
(1 2) adaptive
2 (1+
exploration rounds. Then, by Lemma 5 with probability at least
(d + 1) exp
10kl
1 - (d 1)T 0r x we have
C'T
2
Amin (V++1) 2
1 +
where V, == E1=1 Eies, ze (Sx (S Note that for any X,,X, E Rd, (x; - xx)
x2) X + X X X Oaxas which implies xxx] xxx x,x + x,x,
To simplify, for E St, if we abbreviate pi St, wx) by pri(wi, and 2 (S.) by Zei, then for all
26

---

Published as a conference paper at ICLR 2026
E (t - 11, we have
(w++++) = Σ
Poil W. 6 13:
Σ iES, JES,
Poilw Pa(W::1Dp(W..t100a
VES,
Σ
Poi ( 1ZziZzi
1/2 Σ *,S, JES,
Psc Pe((W.:)PPy + 2a5)
iES,
= Σ
Pst Ws+1 1
Σ
Σ Pu(W:st))pg(W::))222t. + 2n 2.52.aa)
2
VES,
BES.JES,
Σ 1ES,
Pei W )2ii2s
Σ
Poil Pai(W.s. (oilW+1))Ps) West)Pes( (W Σ
iES, JES
Σ iES,
Psi Poi(Wss (Ws+1) 1 Σ
Pes( (ws(Ws+)) 2ritig
jES,
Σ iES,
Pei ( (Poo=)))
2si4
seS.
where x == 1ish bus. (A) > 0. Hence, we have
=
AL d+1 Σ G. Al441 iES,
2. 2 KV4+1
Thus, holds that
Amin (H,+1) 2 KAmin (V+1) Ct 1
By Lemma this implies
& Te. Therefore, with probability at least 8 (d +
1)7-0( 2ovalos
the number of adaptive exploration rounds is bounded by
2ar
(1
= 2 w
VVdlog T log K KK kKoowl
T < klKoo
F.2 PROOF OF THEOREM
Proof of Theorem 3
We define the event T as the set of rounds corresponding to adaptive explo-
ration, formally defined in Equation [4
Fort & T by Lemma
since 7, Eq.18 is monotone and submodular, we have
exp(f((S)))
R(S 0" (*) = + exp((f(()))
exp():(S7))
1 exp((((())))
(G-T)
exp
(:: Je is submodular)
1 exp
((i)) f(()))
(
eep Js(Ss))
1+
eepp [(())))
+ 1
(S)),
27

---

Published as a conference paper at ICLR 2026
where the last inequality holds because h(v) == (Xp(f((S.) and --1 (refer to the proof of Theorem
yo
holds for v
1+
I+
Therefore, with probability 1 - (d 1)7- O( Lo K
aKww
T
R?(T)= = (S7 ,²) Rs(S,, 0"
Σ
RS 0" ,,,') (s,, 0" ,,,'))+++ +T9
*T
Σ (S,) Re 0 +'))+
**
VK(d+1)
VT ( +0 K+1
(15)
K
KK koow
V K+1
vd
VT - (d 1)2 kKagpl
where for Eg 15 we invoke the regret bound of OFU-MNL+ under uniform revenue setting from from
& Oh (2024)
our diversified optimistic expected reward R(S.) serves optimistic estimate
of Rg St )*). The subsequent analysis closely follows the proof of Theorem Lee & Oh 2024
G EXPERIMENTAL DETAILS
G.1 BASELINES
We compare the empirical performance of our algorithm against the existing MNL bandit algorithms UCB-MNL, TS-MNL, and OFU-MNL along with two variants of OFU-MNL+ that incorporate assortment diversity, in the DMNL bandit setting.
Algorithm for MNL bandits with submodular rewards. We consider the item-wise optimistic construction algorithm OFU-MNL-DR (Algorithm [ for the original MNL choice model with submodular reward function baseline. Inspired by Qin et al. (2014), diversity in the orig- inal MNL bandit can be promoted by modifying only the reward function as R 0" A)
Ejes exp(x,,0") 1+Ejes xx)(x,,0)) + Ag(S), where gSS) is the diversity score function, and À is balancing pa-
rameter between relevance and diversity. We adapt OFU-MNL+ with greedy assortment construction requires the value of À to be specified as a hyperparameter.
to maximize Rt Notably,
Algorithm OFU-MNL-DR (OFU-MNL- MIUU--NL--ivennn Diversity integrated Reward)
1: Input: diversity function {9r [9t regularization parameter A, confidence radius {ar step size 7, balancing diversity parameter À
2: Initialization: H; Alg and 0, at any point in {0 Rd: :|0]2 S 1}
3: for t 11 1,..., do
4: Compute U4 x,, + an xx||x,,
5: S. 5.+0
6: for 1s 1,..., K do
7:
01. + arg
1 1iEies exp(us.)) + Ag(S. u())
Eiercoto exp(urs)
8:
S; + S, U {ar,}}
9:
Offer S, and observe 1/:
Update H. H. + y G. (0.41). and update the estimator 0,+1
11:
Update H H. + G.(w+4))
28

---

Published as a conference paper at ICLR 2026
Exhaustive-Search Algorithm for DMNL bandits. We also consider the exhaustive-search algo- rithm, referred to as OFU-DMNL-FULL (Algorithm 3 for the DMNL bandit model. This algorithm
evaluates all (x) possible assortments in each round and thus requires approximately o ( ((NN)
reward estimations per round.
Algorithm OFU-DMNL- FULL (OFU-DHNL with exhaustive-search)
1: Input: diversity function {9i 1221, regularization parameter A, confidence radius {as 1221, step size 7, exploration parameter v
2: Initialization: H AIa+1 and w1 at any point in W.
3: for 1011=1.-- 1.,...," do
4: Offer S, < argmax (S), and observe y/ SES
5: Update H. H. + 7) G (We), Wr+1, and H441 = H, + Gr(We+1)
G.2 EXPERIMENTAL RESULTS IN DIVERSE ENVIRONMENTS
G.2.1
RUNTIME COMPARISON
UCB-MNL
TS-MNL
OFU-MNL+
OFU-MNL-DR
OFU-DMNL-FUl
OFU-DMNL (ours)
N-10, K=5,c.6, c.4. 2+0.4
N-20. K-5, d-5.A-04
N--00 Ko5, de5, A=0.4
Total Runlime (880)
Total Runtime (890)
100
800
(1)
Figure 3: Cumulative runtime of algorithms under N 10, 20, 30 and T 1000
The results in Figure shows that algorithm operates very efficiently by leveraging online mir- ror descent. In particular, compared to the exhaustive-search algorithm, which requires per-round algorithm runs in O(NK) time and thus achieves incomparably
O((eN/K) )) computation, better performance in large-N settings. Although is slower than other OMD-hased MNL algo- rithms due the cost of item-wise construction, still faster than MLE-based methods such as UCB-MNL and TS-MNL. This demonstrates that, despite incorporating the estimation of the diversity parameter, our algorithm remains computationally efficient.
Among the baselines, OFU-MNL+ outperforms UCB-MNL and TS-MNL, while DFU-DMNL-FULL is en- tirely impractical from a runtime perspective. Therefore, in the subsequent experiments we focus on comparing the performance of the three algorithms OFU-MNL++ OFU-MNL-DR, and OFU-DMNL.
G.2.2 REGRET COMPARISON
As shown in Figure our algorithm demonstrates strong performance even when N and K are large. Furthermore, Figure 5 shows that the balance between || |l2 and X varies across 0.6 0.4, 0.5 0.5, 0.4 0.6, and 0.3 0.7, the relative ranking of OFU-MNL and OFU-MNL-DR fluctuates, whereas our proposed algorithm consistently adapts and learns robustly across all balance settings.
29

---

Published as a conference paper at ICLR 2026
OFU-MNL+
OFU-MNL-DR
OFU-DMNL (ours)
N=50, K=10, d=5, A=0.4
N=100, K=10, d=5, A-0.4
N=150, K=10, d=6, A=0
20
Cumulaaive Regret
Curuuaaivve Regret
Cumulative Regret
Rounds (1)
Rounds (1)
Rounds (1)
N=50, d=5,
K=10,
K=10, d=5, A=0.6
Cumulative Regret
15.0
Curnuaalive Regret
Cumulative Regret
20
12.5
10.3
15
18
7.5
64
2.1
0.
2000
4000
9002
8000
10000
2000
4000
6000
8000
10000
2000
4000
6000
8002
10000
Rounds (1)
Rounds (1)
Rounds (1)
Figure 4: Performance of algorithms under various (N, K, X*) configurations
N-50, Km-10, drf, Amd
Nr:00, Km10, ded, Ar0.6
N-00, 10:10, de6, Ar1
Nr:00, 10, Jn0.7
Camulalive Regret
Cursdalive Regrett
X 8
Cundeetiv
Curuuativ
1980 2000 2006 2800
1580
1900
(1)
N-:00, 10:10, dSG, J00.4
N=100. K=10, d=G 2=0.5
N5:100 K=10, de5, 200.6
N=110. 0, d=5 2=0.7
Cumutstvv Rogret
Cumulative Regret
Cumulative Regret
Cumutative
v00 10000 2010 2002 1000
1000 19:00 20:00 2500
2000
1000
1000 18001
X00e
1092
2500 2010 Rounds
Rounds 10)
Rounds 10
Rounds
10
Figure 5: Performance of algorithms under different balances between relevance and diversity
30

---

Published as a conference paper at ICLR 2026
G.3 EXPERIMENT BASED ON REAL-WORLD DATA
We additionally designed semi-synthetic experiment based on real-world dataset, which pro- vides the most practical and feasible alternative in the absence of access to online field de- ployment. We used the Massive Rotten Tomatoes Movie & Review dataset provided in Kaggle (https:/www.kaag))) wtt.:/wwwwwgle.ommmmmm.. which contains over 1.4M+ reviews on 140K+ unique movies, each la- beled as positive or negative, along with rich movie-level metadata. We first converted each review text into a vector representation using TF-IDF (via Tfid/Vectrizer from scikit-learn), followed by dimensionality reduction using truncated SVD to obtain d-dimensional context vectors. This pro- cess resulted in context-labed dataset suitable for downstream modeling. From this dataset, we trained a linear model to classify the binary labels, which was then used to approximate the true relevance utility of each movie from its context features. This constructed online assortment lection environment in which we evaluated the performance of standard MNL bandit baselines, their variants, and our proposed method.
In each round of the online experiment, we N randomly sampled movies and asked the algorithm to choose an assortment of size K. We use exponential decaying categorical function defined as g(S) = + p + pas-1, where ny is the number of categories covered by the assortment S.
K-5,
K-5,
Cunulativv Regret
100
Cunulative Regret
100
2000
6332
4030
8332
10000
2000
4200
4000
8250
10000
Rounds (t)
Rounds
d=5
N=50, K=10, d=10
Cumulativv Regret
70
Cumulativee Regret
10
2000
4002
5000
10000
2000
4200
8000
8200
10000
Rounds
Rounds
Figure 6: Performance of algorithms with synthetic data
As shown in Figure 6 algorithm performs robustly in the synthetic-data experiments and con- sistently outperforms the baseline algorithms. These results suggest that our method is also likely to perform well real-world data.
H AUXILIARY LEMMAS
Proposition 2 (Proposition B.6 in Bach 2013)). Let f be monotone submodular function and Φ non-decreasing concave function. Then, the composition function @(f(S)) is submodular.
Proof of Proposition Define h(S) = ((f())) By submodularity of f. for any S S S2 and & S2, we have
((S) f(S)) 2 (S22 - f(52)
Also, concavity and non-decrggiigg property of é imply that the difference (0x,,) 6) = 6(x + + ((x) is non-increasing in the and non-decreasing in 6. That is, if œ1 22, then (6 2
31

---

Published as a conference paper at ICLR 2026
(22, 8), and if 61 - 82, then v(2,61) - (2) Using this, obtain the following:
ofs(S, u (e))) o(f(S))) = -
-
(: f(2))
2 -( -(())))()))))))))))))))))))))))) (() f(s))
-
-((s) -((((S))
This inequality is exactly
h(s U [e)) h(S1) 2 hS2 (et) - h(S)),
which shows that is also submodular.
Lemma (Lemma in Lee & Oh (2024). Suppose that Assumption 7 hold. For any 8 E (0, 1], if we set n = 2 log( K + 1) + 2, A
84v2(d + 1)n, and a₁ = O(vd log t log K), then we have
P P 1, ||w, 1o--ww I|: Saa)
where the estimated parameter updated by the rule in (3.
Lemma 8 (Theorem 3.1 in Tropp (21TT). Let Hi C. H2.... be filtration and consider a finite sequence { of positive semi-definite matrices with dimension d adapted to this filtration. Sup- pose that Xmax (x) S R almost surely. Define the series Y = EE X2 and W = En
Then for all a 2 O, 7 E (0,1) we have
-
P(Amiu (Y) $ (1 -7)1 and Amin (W) 2 14| S d(
)u/R
(1 11-1)1-9
32


Reviews:
[{"review_id": "II4PWQYWAI", "reviewer": "Reviewer_KWsv", "summary": "Proposes a diversified MNL (DMNL) contextual bandit: standard MNL utilities plus a submodular diversity term; gives a greedy OFU algorithm with an improved approximation constant over 1−1/e and √T-type regret; synthetic results show better relevance–diversity trade-offs than MNL baselines.", "questions": "- Is \\(g_t(S)\\) assumed exactly known at decision time? How would OFU-DMNL adapt if \\(g_t\\) is observed with noise or must be learned from implicit feedback?\n- Can guarantees be given under submodularity (ω=0) ?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Bridges choice modeling and diversity via DMNL; captures the relevance–diversity tension within the click probabilities rather than via ad-hoc reward shaping.\n- Item-wise optimistic greedy avoids black-box combinatorial oracles yet has provable guarantees", "weaknesses": "- The algorithm takes \\(g_t(S)\\) as given. Many applications may only have noisy diversity signals; robustness to misspecification or learned $g_t$ is not explored.\n- Experiments appear synthetic; adding a real recommendation/assortment dataset would strengthen the contribution", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o5jMzhnwfB", "reviewer": "Reviewer_wr1X", "summary": "The paper proposes DMNL, an extension of the MNL choice model with a diversity parameter $g_t(S)$, where the diversity of the assortment in some sense modifies the probability of the outside option. A major challenge of this new model is that it is not possible to \"greedily\" solve the offline best assortment problem. As a result, the authors present $\\gamma-$regret (approximate regret bound)", "questions": "1)$g_t$ needs to be sub-modular? It is not specified explicitly\n\nalso see the above weakness", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is overall well-written and easy to understand. The model of DMNL is novel and bridges the gap between MNL choice model and diversity-focused assortment", "weaknesses": "1. I hope the authors can motivate the model better. Modeling the diversity via the submodular function $g_t$ seems a bit contrived. Is there a good understanding why should be the diversity of assortment be modelled in this way? e.g. Appendix C.2 gives some mathematical examples, can authors suggest if there are any examples where those functions may be appropriate?\n\n2. The strict submodularity assumption is quite strong\n\n3. Why is uniform exploration of lines 4-5 (Algorithm 1) required? What step of the proof fails without it?\n\n4. Line 240 (Claim of \"composition of a submodular function with a non-decreasing .....preserve submodularity\" requires a proof or reference . it is not obvious.\n\n5. What is utility of Theorem 1? In what scenarios/instances is it helpful to give a stronger constant in regret?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PrayS5jdmi", "reviewer": "Reviewer_erMD", "summary": "The paper proposes Diversified Multinomial Logit (DMNL) Contextual Bandits, extending the Multinomial Logit (MNL) choice model to explicitly promote diversity in the chosen assortments. The authors incorporate a submodular diversity function directly into the choice probability formulation. Finding optimal assortment in DMNL is intractable and requires exhaustive search. To tackle with this difficulty, the authors developed a UCB-based method that achieves a (1-1/(e+1)) approximate regret guarantee. The claimed theoretical result parallels known regret bounds for standard MNL bandits under uniform revenue assumptions.", "questions": "1. For the regret upper bound, is it matching in all parameters? It would be helpful to discuss how the additional diversity parameter introduces looser constraints.\n2. A discussion on lower bound is also desirable. \n3. What is the exact setup of the numerical experiments shown in Figure 2? A brief introduction would be desirable. Providing this context would make the figure much easier to understand without referring back to the appendix.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The DMNL is a novel model that directly incorporates diversity as a submodular function added to the choice probability. This integration is conceptually appealing, as it allows diversity to influence user choice in a principled way rather than as a post-hoc balancing approach, seen in existing work.\n\nTo approximately solve the assortment selection problem, the authors constructed a UCB-based item-wise greedy algorithm that estimates the unknown relevance utility and diversity parameters jointly, avoiding exhaustive enumeration. The joint estimation of both parameter sets is a notable contribution. The authors further prove a regret bound of the algorithm that achieves comparable performance to existing MNL bandits, despite the added complexity of estimating diversity parameters.", "weaknesses": "The main weakness lies in the technical depth of the paper. While the formulation of the DMNL model is conceptually novel, the theoretical contributions are somewhat incremental. The improved approximation rate is a relatively straightforward derivation from the structure of the submodular function, which should be stated more of a proposition rather than theorem.\nThe item-size optimistic construction largely follows from UCB based algorithms that are commonly used in semi-bandit combinatorial multi-armed bandit literature. Although the adaptation to the DMNL context is sound, it seems not introducing new insights beyond existing frameworks. The joint estimation of $\\theta$ and $\\lambda$ comes from a relatively simple reparameterization of the choice probability that effectively treating diversity as an additional feature dimension. In addition, the presentation could be improved. The novelty is somewhat obscured by lengthy discussions that follow definitions and proofs, which destroys the flow of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)