Diversified Multinomial Logit Contextual Bandits Heesang Ann
Seoul National University
Taehyun Hwang
Seoul National University
Min-hwan Oh
Seoul National University
arXiv:2607.11684v1 [stat.ML] 13 Jul 2026
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, 1 avoids black-box optimization oracles. We show that OFU-DMNL achieves at least a (1 − e+1 )p e d T /K , where d is the context dimension, K the maximum approximate regret bound O assortment size, and T the horizon, and attains an improved approximation factor over standard submodular baselines. Experiments demonstrate consistent gains and, relative to exhaustive enumeration, comparable regret with substantially lower runtime. Overall, DMNL bandits provide a practical foundation for diversity-aware assortment optimization under uncertainty, and OFU-DMNL offers a statistically and computationally efficient solution.
1 Introduction Sequential assortment selection arises whenever a platform repeatedly presents a set of items and observes a user response. E-commerce websites curate product slates, streaming services recommend a set of movies, and app stores surface a collection of apps. In 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. A 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 et al., 1978) has served as a canonical choice model for dynamic assortment learning: it represents choice probabilities through latent item utilities based on relevance, a structure that supports tractable assortment optimization and clean statistical learning guarantees. These advantages have motivated a substantial literature on MNL assortment bandits (Rusmevichientong et al., 2010; Sauré and Zeevi, 2013; Agrawal et al., 2017; 2019) and contextual variants that exploit user and item features to generalize across contexts (Cheung and Simchi-Levi, 2017; Ou
Ann, Hwang, and Oh
et al., 2018; Chen et al., 2020; Oh and Iyengar, 2019; 2021; Perivier and Goyal, 2022; Zhang and Sugiyama, 2024; Lee and Oh, 2024; 2025). In these models, uncertainty resides in the relevance-dependent utilities, and the agent’s task is to estimate them online efficiently enough to enable near-optimal sequential assortments. However, practical assortment design is rarely driven by relevance alone: diversity within the offered set is often important in practice. Users tend to value assortments that span complementary attributes (e.g., different genres, brands, or styles), while assortments filled with near-duplicates can cannibalize one another and provide little additional benefit beyond offering a single representative item. At the same time, diversity is not a substitute for relevance: a diverse but irrelevant assortment still performs poorly. This creates an inherent relevance–diversity trade-off. Existing MNL bandits, both contextual and non-contextual, do not capture this trade-off because under the MNL model choice probabilities depend on items only through their individual utilities; consequently, within-assortment interactions—such as similarity-induced cannibalization or complementarity effects—are not modeled. A natural way to incorporate such within-assortment interactions is to model the payoff of an offered set directly through a submodular objective, which captures diminishing returns and encourages coverage and diversity. This idea underlies a literature on submodular and combinatorial bandits (Yue and Guestrin, 2011; Chen et al., 2013; Qin et al., 2014; Chen et al., 2016; 2017; Hiranandani et al., 2020; Hwang et al., 2023), where the agent selects a subset of items each round and receives a 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 as a 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-driven utilities with diversity effects within a single probabilistic choice model. Consequently, there remains a modeling gap between diversity-aware set selection and relevance-based, choice-model-driven 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 applicable—the optimal assortment may require exhaustive search. Many combinatorial bandit approaches (Chen et al., 2013; Qin et al., 2014; Chen et al., 2016; Li et al., 2016; Hwang et al., 2023) circumvent this difficulty by assuming access to a black-box combinatorial optimization oracle with a prescribed approximation factor, an assumption that can be unrealistic in practice and that obscures 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 function—assumed submodular in general—that scores the diversity of assortments (Definition 1). To our knowledge, existing MNL bandit work does not 2
Diversified MNL Contextual Bandits
Base items in Xt Items in selected assortment St Relevance parameter ✓ ⇤ <latexit sha1_base64="dadV+KVQaLLqdrLrfwJJRgxz4v0=">AAAC2HicjVHLSsNAFD2Nr1pf0S7dBFvBVUlEqsuiG5cV7ANrKUk6rUPzIpkIpQjuxK0/4Fa/SPwD/QvvjCmoRXRCkjPn3nNm7r1O5PFEmOZrTpubX1hcyi8XVlbX1jf0za1mEqaxyxpu6IVx27ET5vGANQQXHmtHMbN9x2MtZ3Qi461rFic8DM7FOGJd3x4GfMBdWxDV04vHJDa4YH5i8MAot3ui3NNLZsVUy5gFVgZKyFY91F9wiT5CuEjhgyGAIOzBRkJPBxZMRMR1MSEuJsRVnOEGBdKmlMUowyZ2RN8h7ToZG9BeeiZK7dIpHr0xKQ3skiakvJiwPM1Q8VQ5S/Y374nylHcb09/JvHxiBa6I/Us3zfyvTtYiMMCRqoFTTZFiZHVu5pKqrsibG1+qEuQQESdxn+IxYVcpp302lCZRtcve2ir+pjIlK/dulpviXd6SBmz9HOcsaO5XrGqlerZfqh1ko85jGzvYo3keooZT1NEg7zEe8YRn7UK71e60+89ULZdpivi2tIcPrTSWLA==</latexit>
<latexit sha1_base64="wvUHujcTosmlV74RRl/qdqSrlM4=">AAAC53icjVHLSgMxFD2Or/quunQTbAVXZSpSXRbc6E7RqlClzKRRg/MiyQiluHfnTtz6A271T8Q/0L/wJo7gA9EMM3Ny7j0nufeGWSS18f3nAW9waHhktDQ2PjE5NT1Tnp3b12muuGjxNErVYRhoEclEtIw0kTjMlAjiMBIH4fmGjR9cCKVlmuyZXiaO4+A0kSeSB4aoTnlxy4hYM5kw8hDciC4LtE6ViUViWHW3Y6qdcsWv+W6xn6BegAqKtZ2Wn3CELlJw5IghkMAQjhBA09NGHT4y4o7RJ04Rki4ucIlx0uaUJSgjIPacvqe0axdsQnvrqZ2a0ykRvYqUDEukSSlPEbanMRfPnbNlf/PuO097tx79w8IrJtbgjNi/dB+Z/9XZWgxOsO5qkFRT5hhbHS9cctcVe3P2qSpDDhlxFncprghzp/zoM3Ma7Wq3vQ1c/MVlWtbueZGb49XekgZc/z7On2B/pVZv1Bo7K5XmajHqEhawiGWa5xqa2MQ2WuR9hXs84NGT3rV3492+p3oDhWYeX5Z39wb6Mpzb</latexit>
<latexit sha1_base64="g+wslS7MjTejJp4DtrgjcfsH1Kc=">AAAC2HicjVHLSgMxFD2Or1pf1S7dDBbBVZmKqMuCG5dVbBVrkUyMOph5kMkIpQjuxK0/4Fa/SPwD/QtvYgo+EM0wMyfn3nOSe2+YySjXQfAy4o2OjU9MlqbK0zOzc/OVhcVOnhaKizZPZaoOQ5YLGSWirSMtxWGmBItDKQ7Cy20TP7gSKo/SZF/3M9GL2XkSnUWcaaJOKtU9IcUVS7jwM6ZYLLRQJ5VaUA/s8n+ChgM1uNVKK884xilScBSIIZBAE5ZgyOnpooEAGXE9DIhThCIbF7hGmbQFZQnKYMRe0vecdl3HJrQ3nrlVczpF0qtI6WOFNCnlKcLmNN/GC+ts2N+8B9bT3K1P/9B5xcRqXBD7l26Y+V+dqUXjDFu2hohqyixjquPOpbBdMTf3P1WlySEjzuBTiivC3CqHffatJre1m94yG3+1mYY1e+5yC7yZW9KAG9/H+RN01uqNjfrG7lqtue5GXcISlrFK89xEEztooU3efTzgEU/ekXfj3Xp3H6neiNNU8WV59++Ds5db</latexit>
<latexit sha1_base64="hJoEx1q6+gzdOLupoXe1rGq3FWM=">AAAC23icjVHLSsNAFD2Nr1pfUcGNm2ARxEVJH1TdFdy4rGAf0NaSpNM2NC+SiVBqV+7ErT/gVv9H/AP9C++MKdRF0QnJnDn3nJO5M2bg2BHX9Y+UsrS8srqWXs9sbG5t76i7e/XIj0OL1Szf8cOmaUTMsT1W4zZ3WDMImeGaDmuYo0tRb9yxMLJ974aPA9ZxjYFn923L4ER11YO26Tu9aOzSNGnzIePG9PY001Wz+Zwuh6bPgWKhWL7QZqUsklH11Xe00YMPCzFcMHjghB0YiOhpIQ8dAXEdTIgLCdmyzjBFhrwxqRgpDGJH9B3QqpWwHq1FZiTdFv3FoTckp4Zj8vikCwmLv2myHstkwS7KnshMsbcxzWaS5RLLMST2L99M+V+f6IWjj3PZg009BZIR3VlJSixPRexcm+uKU0JAnMA9qoeELemcnbMmPZHsXZytIeufUilYsbYSbYwvscv5C14M6oVcvpwrX5eylVJy1Wkc4ggndJ9nqOAKVdQo+x4veMWb0lEelEfl6UeqpBLPPn4N5fkb5keYrA==</latexit>
Diversity score <latexit sha1_base64="URS7PePkhNlFVYy31CDDdo4P+Xo=">AAAC1HicjVHLSsNAFD2Nr1ofrbp0EyyCq5IWqS4LunBZwT6glpJMp3VomoTJRCjVlbj1B9zqN4l/oH/hnTEFtYhOSHLm3HPuzL3Xi3wRK8d5zVgLi0vLK9nV3Nr6xma+sLXdjMNEMt5goR/KtufG3BcBbyihfN6OJHfHns9b3uhEx1vXXMYiDC7UJOLdsTsMxEAwVxHVK+RPhQmriR2zUPJeoeiUHLPseVBOQRHpqoeFF1yijxAMCcbgCKAI+3AR09NBGQ4i4rqYEicJCRPnuEWOvAmpOClcYkf0HdKuk7IB7XXO2LgZneLTK8lpY588IekkYX2abeKJyazZ33JPTU59twn9vTTXmFiFK2L/8s2U//XpWhQGODY1CKopMoyujqVZEtMVfXP7S1WKMkTEadynuCTMjHPWZ9t4YlO77q1r4m9GqVm9Z6k2wbu+JQ24/HOc86BZKZWrpep5pVg7TEedxS72cEDzPEINZ6ijYWb+iCc8W03rxrqz7j+lVib17ODbsh4+AFiRlbw=</latexit>
MNL bandits
DMNL bandits
<latexit sha1_base64="smgM6DhHFwVS7rA4ngTKXDvlJ0M=">AAACznicjVHLSsNAFD2Nr1pfVZdugkVwVZIi1WXBjQuVCvYBtUiSTuvQvJhMCqUUt/6AW/0s8Q/0L7wzpqAW0QlJzpx7zp2597qxzxNpWa85Y2FxaXklv1pYW9/Y3Cpu7zSTKBUea3iRH4m26yTM5yFrSC591o4FcwLXZy13eKrirRETCY/CazmOWTdwBiHvc8+RRHUuLs9N1wl7XCa3xZJVtvQy54GdgRKyVY+KL7hBDxE8pAjAEEIS9uEgoacDGxZi4rqYECcIcR1nmKJA3pRUjBQOsUP6DmjXydiQ9ipnot0eneLTK8hp4oA8EekEYXWaqeOpzqzY33JPdE51tzH93SxXQKzEHbF/+WbK//pULRJ9nOgaONUUa0ZV52VZUt0VdXPzS1WSMsTEKdyjuCDsaeesz6b2JLp21VtHx9+0UrFq72XaFO/qljRg++c450GzUrar5epVpVQ7ykadxx72cUjzPEYNZ6ijoTv+iCc8G3VjZEyN+0+pkcs8u/i2jIcPKSOTUA==</latexit>
<latexit sha1_base64="oeec1TI3WAzw2kEjuhjc8GZJJGk=">AAACz3icjVHLSsNAFD2Nr1pfVZdugkVwVdIi1WVBFy5UWrAPsEUm6bQOzYtkopSiuPUH3OpfiX+gf+GdMQW1iE5Icubce87MvdcOXRFLy3rNGDOzc/ML2cXc0vLK6lp+faMZB0nk8IYTuEHUtlnMXeHzhhTS5e0w4syzXd6yh4cq3rrmUSwC/1yOQt712MAXfeEwSVTn6PTsxLSZ3xMyvswXrKKllzkNSikoIF21IP+CDnoI4CCBBw4fkrALhpieC5RgISSuizFxESGh4xy3yJE2oSxOGYzYIX0HtLtIWZ/2yjPWaodOcemNSGlihzQB5UWE1WmmjifaWbG/eY+1p7rbiP526uURK3FF7F+6SeZ/daoWiT4OdA2Cago1o6pzUpdEd0Xd3PxSlSSHkDiFexSPCDtaOemzqTWxrl31lun4m85UrNo7aW6Cd3VLGnDp5zinQbNcLFWKlXq5UN1LR53FFraxS/PcRxXHqKFB3iEe8YRno27cGHfG/WeqkUk1m/i2jIcP82OTng==</latexit>
Figure 1: Differences between MNL bandit algorithms and 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 on the DMNL setting. account for assortment diversity. This is the first model to incorporate diversity directly into the choice probabilities. The model captures practical scenarios in which greater within-assortment 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-world recommender systems. • Algorithmic design. We propose an upper confidence bound (UCB) algorithm, OFU-DMNL (Algorithm 1), for DMNL 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 computationally efficient and comes with a provable approximation guarantee.1 • Regret guarantee. We prove that our proposed algorithm is statistically efficient. Under a sufficient condition on the diversity function (Definition 2), we prove p that 1 e d T /K the algorithm achieves at least a (1 − e+1 )-approximate regret bound of O (Theorem 3), where d is the context feature dimension, K is the maximum assortment e suppresses logarithmic factors. This bound size, T is the total number of rounds, and O closely matches that of nearly minimax-optimal algorithms for MNL bandits under uniform revenues (Lee and Oh, 2024), despite learning a diversity parameter. • Approximation guarantee. We show that the item-wise greedy construction under the DMNL model attains a stronger approximation rate (Theorem 1) than those established in the submodular maximization literature (Nemhauser et al., 1978; Feige, 1998; 1. Due to the augmented diversity function, exact assortment optimization is no longer tractable as in prior work (Ou et al., 2018; Oh and Iyengar, 2019; 2021; Perivier and Goyal, 2022; Lee and Oh, 2024; 2025); hence, we must resort to approximation. Unlike existing work on combinatorial bandits, which assumes access to a black-box optimization oracle returning a super-arm (a set of base arms) with a prescribed approximation factor, our algorithm employs a transparent, white-box construction for which we directly prove the approximation rate.
3
Ann, Hwang, and Oh
Yue and Guestrin, 2011). Unlike the prior literature on MNL bandits—where identifying the optimal assortment can be done efficiently—finding the optimal assortment in DMNL bandits while accounting for diversity requires exhaustive search, making approximation guarantees essential. By leveraging the MNL structure together with the submodularity of the diversity function, we obtain an improved approximation rate 1 , without having to rely on black-box optimization oracles. of at least 1 − e+1 • Numerical performance. Extensive numerical experiments show that our algorithm outperforms benchmark methods across a wide range of scenarios. In particular, even relative to exhaustive enumeration over all possible assortments, our algorithm achieves comparable regret while offering a substantial reduction in running time. Hence, our proposed method is both computationally and statistically efficient.
2 Related Work Contextual MNL bandits. The MNL bandit framework—which applies the MNL choice model to dynamic assortment optimization—has led to significant progress in sequential decision-making (Rusmevichientong et al., 2010; Sauré and Zeevi, 2013; Agrawal et al., 2017; Cheung and Simchi-Levi, 2017; Ou et al., 2018; Agrawal et al., 2019; Oh and Iyengar, 2019; Chen et al., 2020; Oh and Iyengar, 2021; Perivier and Goyal, 2022; Lee and Oh, 2024; Zhang and Sugiyama, 2024; Lee and Oh, 2025). Early results established the statistical efficiency of UCB-type (Agrawal et al., 2017) and Thompson Sampling (TS)-type (Agrawal et al., 2019) algorithms, while Chen and Wang (2017) derived lower bounds for the MNL bandit problem. The contextual MNL bandit was introduced by Oh and Iyengar (2019), who proposed a TS-type algorithm with provable guarantees, followed by a UCB-type algorithm (Oh and p e Iyengar, 2021) achieving O( dT /κ) regret, where κ = O(1/K 2 ) is an instance-dependent parameter. Subsequent works refined the theoretical analysis: Perivier and Goyal (2022) derived tighter regret bounds, and Lee and Oh (2024; 2025) 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 and Guestrin (2011). They introduced the linear submodular bandit framework, in which the reward of a set of items is assumed by a linear combination of submodular set functions. Built on the fact that by using submodular reward functions, item-wise selection (iteratively adding one item at a time in a greedy manner) for set construction guarantees the approximation rate (1 − 1e ) for submodular rewards (Nemhauser et al., 1978), they suggest an algorithm that item-wisely selects items during set optimization and proved a theoretical bound for their algorithm with (1 − 1e )-approximate regret. In the submodular bandit framework (Yue and Guestrin, 2011; Chen et al., 2017; Hiranandani et al., 2020), the set of items is either ranked or presented sequentially to the user, and the probability of an item being selected depends on its marginal gain relative to the previously presented items. Especially, Hiranandani et al. (2020) proposed a cascade variant of the model suggested by Yue and Guestrin (2011). It is notable that these settings are 4
Diversified MNL Contextual Bandits
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 et al., 2016; Hwang et al., 2023), the reward of a set of items is defined as a function of the rewards of the individual arms, which allows optimization to exploit properties of the set such as 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, 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 as a 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.
3 Preliminaries 3.1
Notations and Definitions
√ We use ∥x∥2 to denote the l2 -norm of a vector x ∈ Rd and ∥x∥A := x⊤ Ax to denote the weighted norm of x induced by a positive definite matrix A ∈ Rd×d . For a 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 {1, . . . , n}. 3.2
Problem Setting
Diversified Multinomial Logit (DMNL) Contextual Bandits. We consider a sequential assortment selection problem where, in each round t ∈ [T ], the agent receives a set of feature vectors Xt := {xt1 , . . . , xtN } ⊂ Rd , which may be chosen adversarially. The agent then offers an assortment of size of at most K, i.e., St = {i1 , . . . , il } ∈ S := {S ⊂ [N ] : |S| ≤ K}, where l ≤ K. After presenting the assortment St , the agent observes the user’s decision it ∈ St ∪ {0}, where 0 represents the “outside option”, indicating that the user does not choose any item from St . The selection it is modeled by the MNL model (McFadden et al., 1978). In the existing MNL bandit framework (Cheung and Simchi-Levi, 2017; Ou et al., 2018; Oh and Iyengar, 2019; 2021; Chen et al., 2020; Lee and Oh, 2024; 2025) the click probability that a user selects an item depends only on 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 t ∈ [T ], let gt : S → R≥0 be a given monotone submodular function, where gt (S) quantifies the diversity of the items in the assortment S in round t. Then, the probability of selecting an item 5
Ann, Hwang, and Oh
it ∈ St ∪ {0} in round t is defined as follows: P(it = i | Xt , St ) =: pt (i | St , θ ∗ , λ∗ ) :=
∗ exp(x⊤ ti θ ) P ∗ , exp(−λ∗ gt (St )) + j∈St exp(x⊤ tj θ )
exp(−λ∗ g(St )) P P(it = 0 | Xt , St ) =: pt (0 | St , θ , λ ) := ∗ , exp(−λ∗ gt (St )) + j∈St exp(x⊤ tj θ ) ∗
(1)
∗
where θ ∗ ∈ Rd and λ∗ ∈ R are unknown parameters that represent the degree of relevance and diversity, respectively. Remark 1. Inspired by the submodular bandit literature (Yue and Guestrin, 2011; Chen et al., 2017; Hiranandani et al., 2020), our model captures diversity through monotone submodular functions gt (Definition A.1 and A.2). Common notions of diversity—such as counting the number of distinct categories, measuring coverage of item attributes (e.g., brands or genres), or quantifying dispersion in an embedding space via pairwise distances or spectral properties of a Gram matrix—naturally exhibit diminishing diversity returns: adding an 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, so 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 yt := (yt0 , yt1 , . . . , ytl ) follows the following MNL distribution: yt ∼ Multinomial{1, (pt (0 | St , θ ∗ , λ∗ ), . . . , pt (il | St , θ ∗ , λ∗ ))} , P where the parameter 1 indicates that yt is a single-trial sample, i.e. yt0 + lk=1 ytk = 1. When two assortments consist of items with identical utility values, the one with a higher diversity score reduces the probability of the outside option being chosen. As a result, the probability of selecting 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 (Cheung and Simchi-Levi, 2017; Ou et al., 2018; Oh and Iyengar, 2019; Chen et al., 2020; Oh and Iyengar, 2021; Lee and Oh, 2024; 2025). When the diversity function gt (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 attraction to vary with the offered set, as DMNL does. Then, the expected reward of an assortment S in round t is defined as follows: ∗ X X exp(x⊤ ti θ ) P Rt (S, θ ∗ , λ∗ ) := pt (i | S, θ ∗ , λ∗ ) = ∗ . exp(−λ∗ gt (S)) + j∈S exp(x⊤ tj θ ) i∈S i∈S The goal of the agent is to maximize the total expected reward, or equivalently, to minimize the cumulative regret over T rounds, defined as total difference in expected reward between the offline optimal assortment St∗ = argmaxS∈S Rt (S, θ ∗ , λ∗ ) and the assortment St offered by the agent. 6
Diversified MNL Contextual Bandits
Remark 3. Previous works on MNL bandits (Oh and Iyengar, 2019; Chen et al., 2020; Oh and Iyengar, 2021; Zhang and Luo, 2024; Lee and Oh, 2024; 2025) have also studied the non-uniform revenue setting, where in each round, the agent observes the item-wise revenues {rti }N i=1 . In this setting, the optimal assortment is heavily influenced by high-revenue items, making the diversity of the assortment 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 (rti = 1) we study, maximizing diversity directly contributes to increasing the overall click probability and expected reward, making it a more appropriate objective (Figure 1). We focus on the uniform revenue setting not only for analytical clarity but also because it allows us to isolate and rigorously study the effect of assortment diversity on user choice behavior. γ-approximate Regret. In the case of uniform revenues in MNL bandit setting, maximizing the expected reward of an assortment over all sets S ∈ S reduces to selecting the K items with the highest relevance utility. However, unlike in the existing MNL bandit literature, such a top-K selection strategy is no longer sufficient in the DMNL model. Because the diversity of an assortment influences click probabilities, the expected reward depends not only on individual item relevance utilities but also on the overall diversity of the selected N set. Thus, finding the optimal assortment requires evaluating all K subsets, which is computationally prohibitive even when θ ∗ and λ∗ are known. In previous combinatorial bandit works (Chen et al., 2013; Qin et al., 2014; Chen et al., 2016; Li et al., 2016; Hwang et al., 2023; Liu et al., 2024; 2025), such computational challenges are typically addressed by assuming access to a γ-approximate oracle, and the performance of algorithms is evaluated via cumulative γ-approximate regret rather than exact regret. The γ-approximate regret at round t is defined as Rγ (t, St ) = γRt (St∗ , θ ∗ , λ∗ ) − Rt (St , θ ∗ , λ∗ ). Then, the alternative objective of the agent is to minimize the cumulative γ-regret, defined as Rγ (T ) :=
T X t=1
Rγ (t, St ) =
T X
[γRt (St∗ , θ ∗ , λ∗ ) − Rt (St , θ ∗ , λ∗ )] .
t=1
We adopt this standard evaluation metric but do not rely on an oracle. Instead, in Section 4.1, we explicitly construct a computationally efficient assortment selection strategy that serves as an approximation oracle. Specifically, we show that the item-wise greedy 1 construction (Eq.(6)) achieves a provable approximation ratio γ ≥ 1 − e+1 with respect to the offline optimum, while requiring only O(N K) computation per round. This result enables practical deployment without sacrificing theoretical guarantees. Following prior work on MNL bandits, we make the following boundedness assumption. Assumption 1 (Boundedness). We assume that ∥[θ ∗ , λ∗ ]∥2 ≤ 1, ∥xti ∥2 ≤ 1 and 0 ≤ g(St ) ≤ 1 for all t ∈ [T ], i ∈ [N ], and there exists a constant l > 0 such that l < λ∗ . The boundedness in Assumption 1 is standard in the MNL bandit literature (Oh and Iyengar, 2019; 2021; Perivier and Goyal, 2022; Zhang and Sugiyama, 2024; Lee and Oh, 2024; 2025). Since we 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 l. We note that our proposed algorithm does not require the knowledge of l. 7
Ann, Hwang, and Oh
4 Main Results 4.1
Approximation Guarantee of Item-wise Greedy Assortment
In this section, as an instantiation of γ-approximate oracle, we show that the item-wise greedy construction can approximate the offline optimal assortment reward Rt (St∗ , θ ∗ , λ∗ ). The item-wise greedy construction refers to a process that incrementally builds a solution by repeatedly adding the item with the highest marginal gain. To be specific, for any k ∈ [K], the k-th element added during the item-wise greedy construction is: ak =
Rt ({a1 , . . . , ak−1 } ∪ {a}, θ ∗ , λ∗ ) .
argmax
(2)
a∈[N ]\{a1 ,...,ak−1 }
Assortment C
J
F
A
B
C
D
E
F
G
H
Figure 2: Item-wise construction It is well known that if the expected reward function Rt is a monotone submodular function with respect to S ∈ S, the item-wise greedy construction in Eq.(2) can achieve a (1 − 1e )-approximation rate (Nemhauser et al., 1978), and that obtaining an approximation rate better than (1 − 1e ) is intractable (Feige, 1998). On the other hand, since Rt (S, θ ∗ , λ∗ ) increases as more items are added to S, it is a monotone set function (Definition A.1). Moreover, by the definition of submodular functions P ∗ ⊤ (Definition A.2), the LogSumExp function of the form log i∈S exp(xti θ ) is submodular. exp(ft (S)) The expected reward of an assortment S can be written as Rt (S, θ ∗ , λ∗ ) = 1+exp(f , where t (S)) P P ∗ ∗ ⊤ ∗ ⊤ ∗ ft (S) := log i∈S exp(xti θ + λ gt (S)) = log i∈S exp(xti θ ) + λ gt (S). Since ft (S) is exp(x) a non-negative sum of submodular functions, it remains submodular. Moreover, 1+exp(x) is a non-decreasing concave function for x > 0, and it is known that the composition of a submodular function with a non-decreasing concave function preserves submodularity (Proposition G.1). Therefore, Rt (S, θ ∗ , λ∗ ) is also a submodular function. Consequently, the item-wise greedy construction in Eq.(2) achieves at least a (1 − 1e ) approximation rate. This approximation guarantee holds for general monotone submodular functions under cardinality 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 − 1e ) rate. Theorem 1 (Improved approximation rate for MNL submodular function). Let Stgreedy be the solution from Eq.(2). For any t ≥ 1, if gt is monotone and submodular, then we have Rt (Stgreedy , θ ∗ , λ∗ ) ≥
ψ0 (1 + ψ0α ) · Rt (St∗ , θ ∗ , λ∗ ) , ψ0α (1 + ψ0 )
e where ψ0 is a solution to the equation xα = αx + α − 1, with α = e−1 .
8
Diversified MNL Contextual Bandits
Algorithm 1 OFU-DMNL 1: Input: diversity function {gt }t≥1 , regularization parameter Λ, confidence radius {αt }t≥1 ,
step size η, exploration parameter ν 2: Initialization: H1 = ΛId+1 and w1 at any point in W. 3: for t = 1, . . . , T do 4: if ∥[0d , 1]∥H−1 ≥ ν αλ̂tt then t 5: Randomly choose St ∼ Unif(S) with |St | = K 6: else 7: St ← ∅ 8: for k = 1, . . . , K do et ({at,1 , . . . , at,k−1 } ∪ {a}) 9: at,k = argmaxa∈[N ]\St R 10: St ← St ∪ {at,k } 11: 12:
Offer St and observe yt e t = Ht + η Gt (wt ), wt+1 , and Ht+1 = Ht + Gt (wt+1 ) Update H
Theorem 1 holds for any parameter configuration [θ, λ] ∈ Rd+1 , provided that both the item-wise greedy construction and the optimal assortment are evaluated under the same ψ (1+ψ α ) 1 parameters. Moreover, since a crude lower bound for ψ0α (1+ψ00 ) is e+1 , for simplicity, we 0
1 may state that the item-wise greedy construction in Eq.(2) achieves at least a (1 − e+1 )1 approximate rate. This surpasses the existing (1 − e ) 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 C.
4.2
Algorithm
In this section, we propose OFU-DMNL, an algorithm that leverages the optimism-in-the-faceof-uncertainty (OFU) principle in estimating the unknown relevance utility and diversity parameters. The complete process is described in Algorithm 1, consisting of three stages. Diversity-augmented parameter estimation. Let zti (S) := [xti , gt (S)] ∈ Rd+1 be a diversity-augmented feature vector, and w∗ := [θ ∗ , λ∗ ] ∈ Rd+1 . Then, the DMNL probability in Eq.(1) can be represented by exp(zti (S)⊤ w∗ ) P , 1 + j∈St exp(ztj (S)⊤ w∗ ) 1 P pt (0 | S, θ ∗ , λ∗ ) =: pt (0 | S, w∗ ) = . 1 + j∈St exp(ztj (S)⊤ w∗ )
pt (i | S, θ ∗ , λ∗ ) =: pt (i | S, w∗ ) =
Consequently, parameter estimation in the DMNL model—namely, (θ ∗ , λ∗ )—can be reformulated as estimating a single parameter vector w∗ using diversity-augmented feature vectors zti (S), similarly to the procedure used in existing MNL models. Adapting the computationally efficient parameter estimation used in Lee and Oh (2024), we use the online mirror descent algorithm to estimate the parameter w∗ . Let us define the multinomial logit loss 9
Ann, Hwang, and Oh
function at round t as ℓt (w) := − w∗ as follows:
P
i∈St yti log pt (i | St , w), and estimate the true parameter
n o 1 [θ̂ t+1 , λ̂t+1 ] = wt+1 = argmin ⟨∇ℓt (wt ), w⟩ + ∥w − wt ∥2H et , 2η w∈W
∀t ≥ 1 ,
(3)
e t := where W := {w ∈ Rd+1 : ∥w∥2 P ≤ 1}, η > 0 is the step-size parameter, and H t−1 Ht + η Gt (wt ), with Ht := ΛId+1 + s=1 Gs (ws+1 ) and X XX Gt (w) = pt (i | St , w)zti (St )zti (St )⊤ − pt (i | St , w)pt (j | St , w)zti (St )ztj (St )⊤ . i∈St
i∈St j∈St
Based on the estimated parameter wt and a suitably chosen confidence radius αt , we have with high probability that ∥wt −w∗ ∥Ht ≤ αt (Lemma 1 in Lee and Oh (2024)). This concentration bound enables us to construct an optimistic estimate of the diversity-augmented utility by evaluating it over the diversity-augmented feature vector as: ucb(zti (S)) := [xti , gt (S)]⊤ wt + αt ∥[xti , gt (S)]∥H−1 . t
(4)
Based on the optimistic utility estimates ucb(zti (S)), we formulate the diversified optimistic expected reward for a given assortment S as: X exp(ucb(zti (S))) et (S) := P R . (5) 1 + j∈S exp(ucb(ztj (S))) i∈S
As discussed in Section 3.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-augmented feature vector zti (S) et (S) cannot be depends on the entire assortment S, which means that the optimistic reward R computed by evaluating each item in isolation. As a result, identifying the assortment that et (S) requires evaluating N combinations, which is computationally prohibitive maximizes R K for large N or K. In the following paragraph, we introduce a computationally efficient et (S) method—serving as the main component of our algorithm—for approximating maxS R without exhaustive enumeration. Item-wise optimistic construction. As discussed in Section 4.1, the item-wise greedy 1 construction using the true parameters [θ ∗ , λ∗ ] achieves at least (1 − e+1 )-approximation to the optimal assortment. However, since the true model parameters are unknown to the agent, we replace them with their estimates. In particular, we use an optimistic estimate of the expected reward to guide assortment construction, which encourages exploration over uncertain items while preserving computational efficiency. Using the diversified optimistic reward defined in Eq.(5), we apply an item-wise optimistic construction: for each k ∈ [K], ak =
argmax
et ({a1 , . . . , ak−1 } ∪ {a}) . R
(6)
a∈[N ]\{a1 ,...,ak−1 }
This procedure mirrors the ideal greedy construction under the true model, but substitutes the unknown parameters with optimistic estimates—hence the name item-wise optimistic construction. The agent then offers the assortment St obtained via Eq.(6). We note that the complexity of the item-wise optimistic construction in Eq.(6) is O(N K) for each round. 10
Diversified MNL Contextual Bandits
Adaptive exploration. As the two parameters θ 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 λ∗ alone. This looseness in the confidence interval may result in a failure to ensure the optimism of the item-wise optimistic construction in Eq.(6). To address this, we employ an adaptive exploration that triggers when the confidence on the diversity √parameter estimate is deemed insufficient. We show that the number of rounds is at most O( d log T ) (Lemma E.4). 4.3
Regret Bound
In this section, we establish an upper bound on the cumulative γ-approximate regret incurred by the proposed algorithm. To facilitate the theoretical analysis, we first present a set of technical assumptions under which the regret bound is derived. Assumption 2 (Non-degeneracy). The feature set Xt = {xt1 , . . . , xtN } spans Rd for all t ∈ [T ], gt is not a constant over SK := {S ⊂ [N ] : |S| = K}, i.e., ∃S, S ′ ∈ SK such that gt (S) ̸= gt (S ′ ). Definition 2 (ω-strict submodular function). For ω ∈ (0, 1), a submodular function f is said to be ω-strict submodular if and only if for every S ⊆ S ′ with f (S) ̸= f (S ′ ) and every e∈ / S ′ , f satisfies f (S ′ ∪ {e}) − f (S ′ ) ≤ (1 − ω) (f (S ∪ {e}) − f (S)) . Assumption 3 (Strict submodularity). The diversity score function gt is monotone and ω-strict submodular for some ω > 0. Discussions of assumptions. Assumption 2 is used to ensure the diversity-augmented feature set {[xti , gt (S)]}i∈[N ],S∈SK spans Rd+1 . Under Assumption 2, there exist S1 , S2 ∈ SK such that S1 ∩ S2 ̸= ∅ and gt (S1 ) ̸= gt (S2 ). Let i0 ∈ S1 ∩ S2 . Then we have [0d , 1] = 1 gt (S1 )−gt (S2 ) ([xti0 , gt (S1 )] − [xti0 , gt (S2 )]). This shows that the (d + 1)-th unit vector [0d , 1] ∈
Rd+1 can be expresses as a linear combination of diversity-augmented features. Moreover, the first d-dimensional components of Rd+1 can be spanned by the set {[xti , 0]}i∈[N ] due to Assumption 2. Therefore, the diversity-augmented feature set {[xti , gt (S)]}i∈[N ],S∈SK spans Rd+1 . With the diversity-augmented feature set spanning Rd+1 , we can define a constant σ0 > 0 such that for all t ∈ [T ], X X 1 [xti , gt (S)][xti , gt (S)]⊤ ⪰ σ0 Id+1 . |SK | · K
(7)
S∈SK i∈S
We note that this type of non-degeneracy condition is also commonly used in prior works on GLM and MNL bandits (Li et al., 2017; Chen et al., 2020; Oh and Iyengar, 2021). The strict submodularity in Assumption 3 implies that for any S ⊊ S ′ and any element e∈ / S, the marginal gain of gt from adding e 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 submodularity (Definition A.2). Unlike prior submodular bandit works (Yue and Guestrin, 2011; Chen et al., 2017; Hiranandani et al., 2020), the DMNL bandit setting 11
Ann, Hwang, and Oh
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 significantly increases the difficulty of learning. On the other hand, Yue and Guestrin (2011) assume access to the marginal contribution of each item after the assortment is offered, while Chen et al. (2017) receive interactive feedback on the gain of each added item during the assortment construction process. Similarly, Hiranandani et al. (2020) assume that in a 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 we show that it is possible et (S) after sufficient exploration, even without intermediate to recover submodularity of R feedback. Please refer to Appendix B for a detailed discussion on strict submodularity. We first present a lower bound for the worst-case expected regret in the DMNL setting. Theorem 2 (Regret lower bound). Let Assumption 1, 2, and 3 hold. Suppose d is divisible by 4 and T ≥ C · d4 (K + 1)2 /K for some constant C > 0. Then, in the DMNL bandit setting, for any policy π, there exists a worst-case problem instance such that the expected regret of π is lower bounded as " T # r ! X T . sup Eπθ,λ Rt (St∗ , θ, λ) − Rt (St , θ, λ) ≥ Ω d K θ,λ t=1
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 and Oh, 2024). In our setting, the choice probabilities depend on 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 a non-constant, strict submodular gt and derive an 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 D. We present the main result: the cumulative γ-approximate regret bound for Algorithm 1. Theorem 3 (Regret upper bound of OFU-DMNL). Suppose that Assumptions 1, 2, and 3 hold. For parameters in Algorithm 1 as follows: √ any δ ∈ (0, 1), if 1we set the algorithmic p αt = O( d log t log K), η = 2 √ log(K + 1) + 2, Λ = 84 (d + 1)η, ν = ω2 , then with probability at least 1 − δ − (d + 1)T −O(
σ0
e Rγ (T ) = O
d log K ) κlωK
, the cumulative γ-regret of OFU-DMNL is bounded by √ !! √ K(d + 1) √ 1 d · T+ (d + 1)2 + , K +1 κ lω
where κ := mint∈[T ],S∈S,i∈S,∥θ∥2 ≤1,0≤λ≤1 pt (i|S, θ, λ)pt (0|S, θ, λ) > 0 is a problem-dependent 1 instance, and γ ≥ (1 − 1+e ). Discussion of Theorem 3. The theorem establishes that the regret upper bound of Algorithm 1 is nearly minimax-optimal, as it matches the lower bound for our problem 12
Diversified MNL Contextual Bandits
setting in its dependence on d, K, and T , up to the effects introduced by γ-approximation. Furthermore, our regret bound closely matches that of nearly minimax-optimal algorithms for MNL bandits under uniform revenues (Lee and Oh, 2024). The difference lies in the dimensionality: in our DMNL setting, the agent must learn both the relevance parameter θ ∗ and the diversity parameter λ∗ , whereas existing MNL bandits only require estimation of θ ∗ . Despite this additional complexity, the matching regret bound implies that the proposed algorithm remains statistically efficient while explicitly accounting for diversity. Unlike prior works in combinatorial bandits that model diversity through an explicit balance between a submodular diversity function and an additive reward function (Chen et al., 2013; Qin et al., 2014; Chen et al., 2016), our DMNL framework jointly learns both the relevance parameter θ ∗ and the diversity parameter λ∗ . As a result, our method does not require manually tuning hyperparameters to balance relevance and diversity. Furthermore, the proposed algorithm leverages item-wise optimistic construction based on the submodularity of the reward function, achieving computational efficiency (with O(N K) cost per round) and provably improved approximation ratio—without relying on a 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 et (S). This allows guarantee the submodularity of the overall optimistic reward function R us to maintain provable performance guarantees without requiring marginal gain feedback, which is typically assumed in prior submodular bandit settings (Yue and Guestrin, 2011; Chen et al., 2017; Hiranandani et al., 2020). The detailed proof is provided in Appendix E.
5 Numerical Experiments We evaluate the empirical performance of our proposed algorithm against several baselines in the DMNL bandit setting. These include existing MNL bandit algorithms: UCB-MNL (Oh and Iyengar, 2021), TS-MNL (Oh and Iyengar, 2019), and OFU-MNL+ (Lee and Oh, 2024), as well as two additional variants of OFU-MNL+ adapted to incorporate diversity. First, we consider OFU-MNL-DR (Algorithm F.1), which follows the existing MNL choice P
∗ exp(x⊤ tj θ ) ∗ + ⊤ j∈S exp(xtj θ )
model but uses a submodular reward function of the form Rt′ (S, θ ∗ , λ) := 1+Pj∈S
λg(S), where g(S) is the diversity score and λ is a predefined balancing parameter. Note that OFU-MNL-DR requires tuning λ manually, unlike our approach which learns diversity directly. Second, we include OFU-DMNL-FULL (Algorithm F.2), which exactly implements the DMNL et (S) for all N subsets at each round, incurring model via exhaustive search. It computes R K K per round. These two variants help illustrate the a computational cost of roughly O ( eN ) K benefit of learning diversity directly (vs. tuning it manually) and the computational trade-off of our efficient item-wise optimistic construction relative to exhaustive search. Details on the implementation of these two variants are provided in Appendix F.1. For each round, the context features are drawn from a Gaussian distribution √ independently √ N (0d , Id ) and clipped to the range [−1/ d, , 1/ d]d . Each item is also assigned a category, ans the diversity function on an assortment S is then defined as the exponential decaying categorical function (Example B.1). To assess how effectively the proposed algorithm adapts to relevance–diversity trade-offs, we fix the diversity parameter λ∗ at several values. We then 13
Ann, Hwang, and Oh
OFU-MNL+
N=10, K=5, d=5, * =0.4
40 30 20 10
2000
4000
6000
Rounds (t)
8000
30 20 10
10000
2000
10000
Rounds (t)
15000
6000
Rounds (t)
8000
1500 1000 500
10000
20000
40 20 0
0
5000
10000
Rounds (t)
15000
20000
0 -MNL TS-MNLFU-MNL+-MNL-DRMNL-Full U-DMNL O OFU FU-D OF O
UCB
Cumulative Regret
Cumulative Regret
Cumulative Regret
20
5000
4000
OFU-DMNL (ours)
N=20, K=5, d=5, * =0.4
N=50, K=10, d=5, * =0.4
40
0
OFU-DMNL-FULL
N=20, K=5, d=5, * =0.4
40
N=50, K=5, d=5, * =0.4
0
OFU-MNL-DR
Total Runtime(sec)
TS-MNL
Cumulative Regret
Cumulative Regret
UCB-MNL
N=100, K=10, d=5, * =0.4
30 20 10 0
0
5000
10000
Rounds (t)
15000
20000
Figure 3: 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 cumulative regret of the top 3 algorithms under various parameter settings. √ √ sample the relevance parameter θ ∗ from a uniform distribution over [−1/ d, 1/ d]d and scale it to satisfy ∥θ ∗ ∥2 + λ∗ = 1. We conducted 10 independent runs for each configuration„ and all reported results are averaged over these runs. As shown in Figure 3, our algorithm exhibits superior performance compared to the baseline algorithms. Notably, it achieves competitive regret performance relative to the exhaustive-search algorithm, OFU-DMNL-FULL, while demonstrating a dramatic advantage in runtime efficiency. Moreover, 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 λ, refer to Figure F.3). 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 in Appendix F.
6 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, we 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 employs a white-box, item-wise construction strategy with a provable 1 approximation guarantee of at least (1 − e+1 ). We further show that the algorithm achieves p 1 e d T /K , matching the nearly a (1 − e+1 )-approximate cumulative regret bound of O minimax regret of MNL bandits despite the added challenge of jointly learning a diversity parameter—highlighting both statistical efficiency and modeling generality. Empirical results 14
Diversified MNL Contextual Bandits
demonstrate superior performance across a wide range of scenarios with significantly lower computational cost. Overall, our work offers a practical and theoretically grounded solution for diversity-aware sequential decision-making.
References Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-bandit. In Conference on learning theory, pages 76–78. PMLR, 2017. Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-bandit: A dynamic learning approach to assortment selection. Operations Research, 67(5):1453–1485, 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, pages 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–44, 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 ln n for approximating set cover. J. ACM, 45(4):634–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 P. Adams and Vibhav Gogate, editors, Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 722–732. PMLR, 22–25 Jul 2020. 15
Ann, Hwang, and Oh
Taehyun Hwang, Kyuwook Chai, and Min-hwan Oh. Combinatorial neural bandits. In International Conference on Machine Learning, pages 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:109003–109065, 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 contextual bandits. In International Conference on Machine Learning, pages 2071–2080. PMLR, 2017. Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International conference on machine learning, pages 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. S. Lui. Combinatorial logistic bandits, 2025. Daniel McFadden et 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 Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 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 on Artificial Intelligence, pages 2602–2608, 2018. Noemie Perivier and Vineet Goyal. Dynamic pricing and assortment under a 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, pages 461–469, 2014. Paat Rusmevichientong, Zuo-Jun Max Shen, and David B Shmoys. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research, 58(6):1666–1680, 2010. 16
Diversified MNL Contextual Bandits
Denis Sauré and Assaf Zeevi. Optimal dynamic assortment planning with demand learning. Manufacturing & Service Operations Management, 15(3):387–404, 2013. Joel A 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 retrieval. In Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011. Mengxiao Zhang and Haipeng Luo. Contextual multinomial logit bandits with general value functions. Advances in Neural Information Processing Systems, 37:34123–34160, 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.
17
Ann, Hwang, and Oh
Appendix Table of Contents A Definitions and Notations
18
B Strict Submodularity B.1 Challenges in Item-wise Optimistic Construction . . . . . . . . . . . . . . B.2 Examples of Strict Submodular Diversity Functions . . . . . . . . . . . . .
19 19 21
C Proof of Theorem 1
23
D Lower Bound D.1 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Technical Lemmas for Theorem 2 . . . . . . . . . . . . . . . . . . . . . . .
24 24 27
E Regret Upper Bound of Algorithm 1 (OFU-DMNL) E.1 Technical Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.2 Proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30 30 34
F
35 35 36 38
Experimental Details F.1 Baselines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F.2 Experimental Results in Diverse Environments . . . . . . . . . . . . . . . F.3 Experiment based on real-world Data . . . . . . . . . . . . . . . . . . . .
G Auxiliary Lemmas
39
A Definitions and Notations Recall that we define N as the total number of items and S as the set of candidate assortments with a size constraint of at most K, i.e., S = {S ⊂ [N ] : |S| ≤ K}. Definition A.1 (Monotone increasing set function). The set function f mapping sets S ∈ S to a real-valued number is monotone if and only if for every S, S ′ ∈ S with S ⊆ S ′ , f satisfies f (S) ≤ f (S ′ ), Definition A.2 (Submodular function). The set function f mapping sets S ∈ S to a real-valued number is submodular if and only if for every S ⊆ S ′ and e ∈ / S ′ , f satisfies f (S ′ ∪ {e}) − f (S ′ ) ≤ f (S ∪ {e}) − f (S) . Or, equivalently, for e1 , e2 ∈ / S, we have f (S ∪ {e1 }) − f (S) ≥ f (S ∪ {e1 , e2 }) − f (S ∪ {e2 }) . For convenience, we provide a table summarizing the notations. 18
Diversified MNL Contextual Bandits
Table A.1: Notations
N K d T gt xti zti (S) 0 κ St St∗ yti Rt (S, θ ∗ , λ∗ ) ℓt (w) Gt (w)
total number of items maximum size of assortmens dimension of feature vectors number of total rounds diversity score function in round t feature vector for item i in round t := [xti , gt (S)], diversity-augmented feature vector for item i in round t outside option in MNL choice model := mint∈[T ],S∈S,i∈S,∥θ∥2 ≤1,0≤λ≤1 pt (i|S, θ, λ)pt (0|S, θ, λ) > 0 selected assortment in round t optimal assortment in round t user’s i ∈ St ∪ {0} in round t P choice for item ∗ ∗ := P p (i | S, θ , λ ), reward of the assortment S in round t i∈S t := − i∈St yti log pt (i | St , w), loss function in round t := ∇2 ℓt (w) =
P
pt (i | St , w)zti (St )zti (St )⊤ −
i∈St
Λ Ht et H Vt αt ucb(zti (S)) et (S) R ft (S) fet (S)
P P
pt (i | St , w)pt (j | St , w)zti (St )ztj (St )⊤
i∈St j∈St
regularization parameter P := ΛId+1 + t−1 s=1 Gs (ws+1 ) := Ht + η Gt (wt ) P P := ΛId+1 + ts=1 i∈Ss zsi (Ss )zsi (Ss )⊤ , gram matrix confidence radius := zti (S)⊤ wt + αt ∥zti (S)∥H−1 . t P ti (S))) := i∈S 1+Pexp(ucb(z j∈S exp(ucb(ztj (S))) P ⊤ θ ∗ + λ∗ g (S)) := log i∈S exp(x t ti P ⊤ w + α ∥z (S)∥ := log exp z (S) . −1 ti t t ti i∈S H t
B Strict Submodularity B.1
Challenges in Item-wise Optimistic Construction
Lack of intermediate feedback. In the item-wise optimistic construction process in Eq.(6), when selecting the k-th item at,k (for k ∈ [K]), the current partial assortment consists of the previously selected items at,1 , . . . , at,k−1 (Line 9 in Algorithm 1). Therefore, the optimistic diversity-augmented utility in Eq.(4) is computed using only the diversity score of the partial assortment, g({at,1 , . . . , at,k−1 }). 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—even after offering the full assortment. Instead, it only observes the total reward associated with the final constructed set St = {at,1 , . . . , at,K }. This lack of intermediate feedback complicates the analysis of regret, particularly in submodular bandit settings that rely on item-wise optimistic construction. 19
Ann, Hwang, and Oh
On the other hand, prior works on submodular bandits (Yue and 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 and Guestrin (2011) receives slot-level feedback after offering an assortment (i.e., a list of articles), which enables the agent to estimate the marginal utility contribution of each item. Similarly, in the cascading bandit model of Hiranandani 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 on the items already shown. In Chen et al. (2017), 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 et al., 2014; Chen et al., 2018; Hwang et al., 2023), where the diversity of selected arms is incorporated solely through the reward function. Since diversity is not parameterized in those models, there is no need to estimate any diversity-related parameters during learning. Beyond submodular diversity. One way to overcome the intermediate feedback problem is to exploit the submodularity of the diversified optimistic expectd reward in Eq.(5). For an assortment S, let us define fet (S) as follows: ! X ⊤ e ft (S) := log exp zti (S) wt + αt ∥zti (S)∥ −1 . (B.1) Ht
i∈S
We note that if fet (S) is submodular, then we show that the assortment St constructed by the item-wise optimistic construction can approximate the true optimal assortment of fet , making it possible to establish bounds without relying on feedback on marginal gain. However, unfortunately, while the submodularity of gt guarantees that ft is submodular (Section 4.1), it does not ensure the submodularity of fet . To check whether fet is submodular or not, for any S ∈ S, and e1 , e2 ∈ / S, define S1 := S ∪ {e1 }, S2 := S ∪ {e2 }, S3 := S ∪ {e1 , e2 }. Then, fet (S1 ) − fet (S) − fet (S3 ) − fet (S2 ) P ⊤ i∈S1 exp xti θ̂ t + λ̂t gt (S1 ) + αt ∥[xti , gt (S1 )]∥H−1 t = log P ⊤ exp x θ̂ + λ̂ g (S) + α ∥[x , g (S)]∥ −1 t t t ti t i∈S ti t Ht P ⊤ θ̂ + λ̂ g (S ) + α ∥[x , g (S )]∥ exp x −1 t t 2 t ti t 2 ti t i∈S2 Ht ×P ⊤ i∈S3 exp xti θ̂ t + λ̂t gt (S3 ) + αt ∥[xti , gt (S3 )]∥H−1 t P ⊤ θ̂ + λ̂ g (S ) + λ̂ g (S ) + α ∥[x , g (S )]∥ exp x⊤ θ̂ + x + ∥[x , g (S )]∥ −1 −1 t t t t 1 t t 2 t ti t 1 tj t 2 ti tj Ht Ht i∈S,j∈S3 = log P ⊤ θ̂ + λ̂ g (S) + λ̂ g (S ) + α ∥[x , g (S)]∥ −1 + ∥[x , g (S )]∥ −1 exp x⊤ θ̂ + x t t t t t t 3 t ti t tj t 3 ti tj H H t
i∈S,j∈S3
t
⊤ θ̂ + λ̂ g (S ) + λ̂ g (S ) + α ∥[x exp x⊤ θ̂ + x t t 1 t t 2 t t,e1 , gt (S1 )]∥H−1 + ∥[xt,e2 , gt (S2 )]∥H−1 t,e1 t t,e2 t t t + P . ⊤ θ̂ + λ̂ g (S) + λ̂ g (S ) + α ∥[x , g (S)]∥ −1 + ∥[x , g (S )]∥ −1 exp x⊤ θ̂ + x ti t tj t 3 t t t t t t 3 t ti tj H H t
i∈S,j∈S3
20
t
Diversified MNL Contextual Bandits
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 is larger than its denominator. However, this does not hold in general. In general, even though g is submodular, the following inequality does not hold: ∥[xj1 , gt (S1 )]∥H−1 + ∥[xj2 , gt (S2 )]∥H−1 ≥ ∥[xj1 , gt (S)]∥H−1 + ∥[xj2 , gt (S3 )]∥H−1 . t
t
t
t
(B.2)
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 general, guarantee (1 − 1e )-approximate optimality with respect to fet . However, we show that the submodularity of fet can be recovered if the diversity function gt satisfies ω-strict submodularity, as established in Lemma E.1. B.2
Examples of Strict Submodular Diversity Functions
In this section, we present several examples of strictly submodular set functions that are applicable to a wide range of practical settings. Example B.1 (Categorical functions). For a given item set S, let nS 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 gρ (S) increases by ρm−1 for ρ ∈ (0, 1). Then, the diversity function is defined by gρ (S) := 1 + ρ + ρ2 + · · · + ρnS −1 and is (1 − ρ)-strict submodular. (ii) Polynomial decaying case. If the diversity function is defined by gα (S) := (nS )α 1−α 2M for α ∈ (0, 1), then, gα (S) is 1 − 2M -strict submodular, where M is the +1 maximum number of categories. Proof of Example B.1. We define M as the number of categories, c(i) ∈ [M ] the category that the item i ∈ [N ] belongs to, and c(S) := {c(i) | i ∈ S} (|c(S)| = ns ). Let S ′ = S ∪ {e′ }, e∈ / S ′ . To show ω-strict submodularity of the set function g, it is enough to show that if g(S) ̸= g(S ′ ), then the following holds. g(S ′ ∪ {e}) − g(S ′ ) ≤ (1 − ω)[g(S ∪ {e}) − g(S)]
(B.3)
We first show that for any ρ ∈ (0, 1), the exponential decaying categorical function gρ is (1 − ρ)-strict submodular. Suppose that S and S ′ satisfy gρ (S) ̸= gρ (S ′ ). Then, by the definition of gρ , c(e′ ) ∈ / c(S). Thus, gρ (S) = 1 + ρ + . . . + ρnS −1 gρ (S ′ ) = 1 + ρ + . . . + ρnS . If c(e) ∈ c(S), then gρ (S ∪ {e}) − gρ (S) = 0 = gρ (S ′ ∪ {e}) − gρ (S ′ ). Else if c(e) ∈ ′ c(S )\c(S), i.e. c(e) = c(e′ ), then gρ (S ∪ {e}) − gρ (S) = ρnS and gρ (S ′ ∪ {e}) − gρ (S ′ ) = 0, 21
Ann, Hwang, and Oh
and hence the inequality (*) holds for all ω ∈ (0, 1). Otherwise, if c(e) ∈ / c(S ′ ), then gρ (S ∪ {e}) − gρ (S) = ρnS gρ (S ′ ∪ {e}) − gρ (S ′ ) = ρnS +1 , and so, gρ (S ′ ∪ {e}) − gρ (S ′ ) = ρ[gρ (S ∪ {e}) − gρ (S)] holds for ω = 1 − ρ. For all cases, the function gρ satisfies condition in Eq.(B.3) for ω = 1 − ρ, and therefore it is (1 − ρ)-strict submodular. Secondly, we will show that for any α ∈ (0, 1), the polynomial decaying categorical 1−α 2M function gα is 1 − 2M -strict submodular. By the same reasoning as in the +1 1−α 2M exponential decaying case, it suffices that condition (∗) holds for ω = 1 − 2M only +1 when c(e′ ) ∈ c(S ′ )\c(S) and c(e) ∈ / c(S ′ ). If c(e′ ) ∈ c(S ′ )\c(S) and c(e) ∈ / c(S ′ ), then gα (S ∪ {e}) − gα (S) = (nS + 1)α − (nS )α gα (S ′ ∪ {e}) − gα (S ′ ) = (nS + 2)α − (nS + 1)α . Let h(x) = xα for α ∈ (0, 1). Since h is a increasing concave function, h′ (x + 1) < h(x + 1) − α α α < h(x) < h′ (x + 12 ) holds. Thus, (nS + 1)α − (nS )α > (nS +1) 1−α and (nS + 2) − (nS + 1) α hold, and hence, (n + 3 )1−α S
2
gα (S ′ ∪ {e}) − gα (S ′ ) (nS + 2)α − (nS + 1)α = gα (S ∪ {e}) − gα (S) (nS + 1)α − (nS )α (nS + 1)1−α 1 < 1−α 3 1−α = (nS + 2 ) 1 + 2(nS1+1) 1−α 2M . ≤ 2M + 1 Therefore, the function gα satisfies condition in Eq.(B.3) for ω = 1 − 1−α 2M therefore it is (1 − 2M )-strict submodular. +1
2M 2M +1
1−α
, and
Example B.2 (Categorical level functions). For each item i ∈ [N ], let c(i) ∈ RM be the categorical feature vector of item i. Each category m ∈ [M ] has nm levels, P and the m-th entry m of c(i) has a value of cm (i) ∈ {0, n1m , n2m , . . . , nnm = 1}. Define c(S) := m∈[M ] maxi∈S cm (i) be a sum of categorical level-coverage of items in S, and for ρ ∈ (0, 1) and k > 0, gρ,k (S) = k 1 − ρc(S) be a categorical function on S ∈ S. Proposition B.1. For any ρ ∈ (0, 1) and k > 0, gρ,k is (1 − ρ∆ )-strict submodular, where ∆ := minm∈[M ] n1m = max 1 nm . m∈[M ]
/ S ′ . To show strict submodularity, it is Proof of Proposition B.1. Let S ′ = S ∪ {e′ } and e ∈ ′ enough to show that if gρ,k (S) ̸= gρ,k (S ), then the following holds. gρ,k (S ′ ∪ {e}) − gρ,k (S ′ ) ≤ ρ∆ [gρ,k (S ∪ {e}) − gρ,k (S)] 22
(B.4)
Diversified MNL Contextual Bandits
Suppose that S and S ′ satisfy gρ,k (S) ̸= gρ,k (S ′ ). Since h(x) = k(1 − ρx ) is a one-to-one function, we have c(S) ̸= c(S ′ ). Then, by the definition of ∆, it holds that c(S ′ ) − c(S) ≥ ∆. By the (level-coverage) definition of the function c, c is submodular, and hence, c(S ′ ∪ {e′ }) − c(S ′ ) ≤ c(S ∪ {e}) − c(S).
(B.5)
Then, ′ ′ g(S ′ ∪ {e}) − g(S ′ ) = k 1 − ρc(S ∪{e}) − k 1 − ρc(S ) ′ ′ = k ρc(S ) − ρc(S ∪{e}) ′ ′ ≤ k ρc(S ) − ρc(S∪{e})+c(S )−c(S) (∵ ρ < 1 and Eq. B.5) ′ ≤ kρc(S ) 1 − ρc(S∪{e})−c(S) ≤ kρc(S)+∆ 1 − ρc(S∪{e})−c(S) (∵ ρ < 1 and c(S ′ ) ≥ c(S) + ∆) = kρ∆ ρc(S) − ρc(S∪{e}) h i = kρ∆ 1 − ρc(S∪{e} − 1 − ρc(S) = ρ∆ [g(S ′ ∪ {e}) − g(S ′ )] , which results in that g is (1 − ρ∆ )-strict submodular. P Remark B.1. In Example B.2, we simply use c(S) := m∈[M ] maxi∈S cm (i) and gρ,k (S) = h(c(S)) where h(x) := k(1 − ρx ). However, if c is of a form with minimum increase (e.g., max or sum) and h is chosen as a strictly concave function, then g = h(c(S)) becomes ω-strict submodular for some ω ∈ (0, 1).
C Proof of Theorem 1 Proof of Theorem 1. For an assortment S ∈ S, let us define ft (S) as follows: X X ∗ ∗ ∗ = log ft (S) = log exp(x⊤ exp(x⊤ + λ∗ gt (S) . tj θ + λ gt (S)) tj θ ) j∈S
(C.1)
j∈S
Also, we abbreviate Rt (S, θ ∗ , λ∗ ) as Rt (S). If we let ψt := exp(ft (Stgreedy )), then, by the definition of ft , ψt Rt (Stgreedy ) = . 1 + ψt By the additivity of submodular functions, ft is monotone and submodular, and hence the greedy solution for maximizing ft can achieve (1 − 1e )-approximation rate (Nemhauser et al., 1978), which means ft (Stgreedy ) ≥ 1 − 1e ft (St∗ ) . 23
Ann, Hwang, and Oh
Therefore, we have
e · ft (Stgreedy ) exp e−1 exp(ft (St∗ )) ψtα ∗ Rt (St ) = = , ≤ e 1 + exp(ft (St∗ )) 1 + ψtα 1 + exp e−1 · ft (Stgreedy ) e . where we denote α = e−1 To get the approximation rate, we want to bound the below function ψα ψ ψ α (1 + ψ) h(ψ) := / = . 1 + ψα 1+ψ ψ(1 + ψ α )
Since h′ (ψ) = (ψ+ψ1α+1 )2 ×ψ α (−ψ α + αψ + (α − 1)), the equation h′ (ψ) = 0 has a unique solution ψ0 > 0, which is the maximum point in R+ . Since h has the maximum at ψ0 in R+ , Rt (St∗ ) ψt ψtα ≤ / = h(ψt ) ≤ h(ψ0 ) , 1 + ψtα 1 + ψt Rt (Stgreedy ) which implies that Rt (Stgreedy ) ≥
ψ0 (1 + ψ0α ) 1 Rt (St∗ ) = α Rt (St∗ ) . h(ψ0 ) ψ0 (1 + ψ0 )
Since ψ0 satisfies ψ0α = αψ0 + (α − 1), we have ψ0 > 1, and hence, ψ0α + ψ0α+1 αψ0 + (α − 1) + αψ02 + (α − 1)ψ0 = ψ0 + αψ02 + (α − 1)ψ0 ψ0 + ψ0α+1 αψ02 + (2α − 1)ψ0 + (α − 1) (α − 1)(ψ0 + 1) α−1 = = =1+ 2 αψ0 + αψ0 αψ0 αψ0 + αψ0 1 <1+ . e
h(ψ0 ) =
e Therefore, the approximation rate h(ψ1 0 ) is greater than e+1 , which results in 1 1 1− Rt (St∗ ) ≤ Rt (St∗ ) ≤ Rt (Stgreedy ) . e+1 h(ψ0 )
D Lower Bound
D.1
Proof of Theorem 2
The proof closely follows the lower-bound arguments developed for the MNL bandit setting (Chen et al., 2020; Lee and Oh, 2024). However, unlike the standard MNL setting—where the diversity function g can be treated as a constant—our framework imposes Assumption 2, which prevents g from being a constant function. Consequently, we derive a lower bound where g is non-constant and strict submodular. 24
Diversified MNL Contextual Bandits
Proof of Theorem 2. Let λ = 12 and ϵ ∈ 0, 1/d3/2 that will be specified later. For every subset V ⊂ [d], we define θ V ∈ Rd as [θ V ]j = ϵ for j ∈ V , and [θ V ]j = 0 for j ∈ / V, d and Θ := {θ V : V ⊂ Vd/4 } where Vd/4 = {V ⊂ [d], |V | = 4 }. Then, for V ∈ Vd/4 , q 2 ∥θ V ∥2 ≤ dϵ4 ≤ 12 . We consider the K × |Vd/4 | context vectors invariant across rounds t. For each U ∈ Vd/4 , √ there are identical K context vectors with featureqxU , where [xU ]j = 1/ d for j ∈ U and [xU ]j = 0 for j ∈ / U . Then, for U ∈ Vd/4 , ∥xU ∥2 ≤
d 1 1 4 · d = 2. Let U0 = [d/4] ∈ Vd/4 and x0 := xU 0 = ( √1d , √1d , . . . , √1d , 0, . . . , 0 . We define g(S) := 1 only if there exists U ̸= U0 such that xU ∈ S, and otherwise (i.e. S contains only x0 ’s),
we set g(S) := 0. Then g satisfies 0 ≤ g(S) ≤ 1 (Assumption 1). Since g(S0 ) = 0 for S0 = {x0 , . . . , x0 } and g(S) = 1 for all S = ̸ S0 with size k, g satisfies Assumption 2. Furthermore, g is monotone and strict submodular for all ω ∈ (0, 1). 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 Eπθ,λ [R(T |θ, λ)] = sup Eπθ,λ θ,λ
θ,λ
≥
" T X
# Rt (St∗ , θ, λ) − Rt (St , θ, λ)
t=1
1
X
|Vd/4 |
Eπθ,λ
V ∈Vd/4
" T X
# Rt (St∗ , θ, λ) − Rt (St , θ, λ)
.
t=1
Let {St }Tt=1 be a sequence of assortments generated by π. For a fixed V , we define Set := {xUet , . . . , xUet } as the assortment that contains an identical feature vector xUet , where π xUet := argmaxxU ∈St x⊤ U θ V . Furthermore, we simplify notation by EV := Eθ V ,λ and PV := PπθV ,λ . P P By Lemma D.1, for any V ∈ Vd/4 , we have i∈S ∗ pt (i|S ∗ , θ V , λ) − i∈S t pt (i|St , θ V , λ) ≥ e−1/2 (K−1) δϵ et ∩ V |. Thus, we have that √ , where δ := d/4 − |U −1/2 2 (e
+Ke) 2 d
1
X
|Vd/4 | =
EV
V ∈Vd/4
1 |Vd/4 |
X V ∈Vd/4
" T X
# Rt (St∗ , θ, λ) − Rt (St , θ, λ)
t=1
EV
" T " X X t=1
## pt (i|St , θ V , λ) −
i∈S ∗
X
pt (i|St , θ V , λ)
i∈S t
" T # X X e−1/2 (K − 1) ϵ et ∩ V |) √ ≥ EV (d/4 − |U |Vd/4 | (e−1/2 + Ke)2 2 d t=1 V ∈Vd/4 " " T ## −1/2 X X X e (K − 1) ϵ dT 1 et } √ − EV 1{j ∈ U ≥ −1/2 2 4 |Vd/4 | (e + Ke) 2 d 1
V ∈Vd/4 j∈V
25
t=1
Ann, Hwang, and Oh
fj := PT 1{j ∈ U et }. Then, the right hand side For j ∈ V , we define the random variables M t=1 is equal to h i −1/2 X X e (K − 1) ϵ dT 1 fj √ − EV M −1/2 2 4 |Vd/4 | (e + Ke) 2 d V ∈Vd/4 j∈V h i −1/2 X X 1 e (K − 1) ϵ dT fj √ EV ∪{j} M − = −1/2 2 4 |Vd/4 | (e + Ke) 2 d V ∈Vd/4−1 j ∈V / h i −1/2 X |Vd/4−1 | e (K − 1) ϵ dT fj √ ≥ −1/2 − max EV ∪{j} M 2 4 |Vd/4 | V ∈Vd/4−1 (e + Ke) 2 d j ∈V /
e−1/2 (K − 1)
h i fj fj + EV ∪{j} M fj − EV M M
|Vd/4−1 | ϵ dT √ − max EV 4 |Vd/4 | V ∈Vd/4−1 2 d j ∈V / h i h i −1/2 X e (K − 1) ϵ dT 1 dT 1 fj − EV M fj √ ≥ −1/2 − · − max EV ∪{j} M 4 3 4 3 V ∈Vd/4−1 (e + Ke)2 2 d j ∈V / h i h i X 1 e−1/2 (K − 1) ϵ dT fj − EV M fj √ − max = −1/2 EV ∪{j} M 6 3 V ∈Vd/4−1 (e + Ke)2 2 d j ∈V / d h i h i X 1 e−1/2 (K − 1) ϵ dT fj − EV M fj √ − max EV ∪{j} M ≥ −1/2 6 3 V ∈Vd/4−1 (e + Ke)2 2 d j=1 d h i h i −1/2 X e (K − 1) ϵ dT 1 fj − EV M fj . √ = −1/2 − max EV ∪{j} M 2 V ∈Vd/4−1 6 3 (e + Ke) 2 d
=
X
(e−1/2 + Ke)2
h
i
h
i
j=1
h i h i P f f We bound maxV ∈Vd/4−1 j ∈V / |EV ∪{j} Mj − EV Mj | using KL divergence. By the fj , we can bound definition of M T h i h i h i h i X fj − EV M fj ≤ fj = t − PV ∪{j} M fj = t EV ∪{j} M t · PV M t=0
≤T·
T X
h i h i fj = t − PV ∪{j} M fj = t PV M
t=0
≤ T · sup |PV (A) − PV ∪{j} (A)| A r 1 ≤T· KL(PV ∥PV ∪{j} ), 2 where the last inequality holds by Pinsker’s inequality. 26
Diversified MNL Contextual Bandits
fj ]ϵ2 EV [M K By Lemma D.2, we have KL(PV ∥PV ∪{j} ) ≤ C · (1+K) , for some C > 0. 2 · d Therefore, d i i h h −1/2 X e (K − 1) ϵ dT 1 fj fj − EV M √ − max EV ∪{j} M −1/2 2 V ∈Vd/4−1 6 3 (e + Ke) 2 d j=1 r d −1/2 X e (K − 1) ϵ dT 1 1 √ ≥ −1/2 − T· KL(PV ∥PV ∪{j} ) 2 6 3 2 (e + Ke) 2 d j=1 v √ u d −1/2 X u 1 e (K − 1) ϵ dT T d t √ ≥ −1/2 − · KL(PV ∥PV ∪{j} ) 2 6 3 2 (e + Ke) 2 d j=1 v h i u √ uX fj ϵ2 EV M u d 1 K e−1/2 (K − 1) ϵ dT − T d · t √ C · · ≥ −1/2 3 2 (1 + K)2 d (e + Ke)2 2 d 6 j=1
e−1/2 (K − 1) ϵ √ ≥ −1/2 (e + Ke)2 2 d
By setting ϵ =
q
! √ s dT T d K C 2 − · · · Tϵ 6 3 8 (1 + K)2
(∵
d X j=1
h i dT fj ≤ EV M ). 4
(1+K)2 d , we finally have that 2CT · K
sup Eπθ,λ [R(T |θ, λ)] = sup Eπθ,λ θ,λ θ,λ
" T X
# Rt (St∗ , θ, λ) − Rt (St , θ, λ)
t=1
! √ s dT T d K e−1/2 (K − 1) ϵ C √ − · · · T ϵ2 ≥ −1/2 6 3 8 (1 + K)2 (e + Ke)2 2 d r e−1/2 (K − 1) 1 (1 + K)2 dT dT ≥ −1/2 · − K 6 12 (e + Ke)2 8CT √ ! d T =Ω √ . K
D.2
Technical Lemmas for Theorem 2
et ∩ V |. Lemma D.1. Fix ϵ ∈ (0, 1/d3/2 ), λ = 12 , and V ∈ Vd/4 , and define δ := d/4 − |U Then, X X e−1/2 (K − 1) δϵ √ . pt (i|S ∗ , θ V , λ) − pt (i|St , θ V , λ) ≥ −1/2 (e + Ke)2 2 d i∈S ∗ i∈S t Proof of Lemma D.1. We split the proof into two cases: (i) V ̸= [d/4], and (ii) V = [d/4].
27
Ann, Hwang, and Oh
Case 1. V ̸= [d/4]. f We recall xUet := argmaxxU ∈St x⊤ U θ V . If δ = 0, i.e. Ut = V , then the lemma holds trivially, thus we suppose that δ ̸= 0. If V ̸= [d/4], it is obvious that S ∗ = {xV , . . . , xV } with g(S ∗ ) = 1, and so we have X i∈S ∗
X
pt (i|S ∗ , θ V , λ) −
pt (i|St , θ V , λ)
i∈S t
K exp(x⊤e θ V ) K exp(x⊤ Ut V θV ) ≥ −1/2 − −λg(St ) +K exp(x⊤ θ ) e + K exp(x⊤ exp θ ) V V e V
Ut ⊤ K exp(x e θ V ) K exp(x⊤ Ut V θV ) ≥ −1/2 − ⊤ −1/2 e + K exp(xV θ V ) exp +K exp(x⊤e θ V ) Ut
=
= ≥
(∵ g(St ) ≤ 1)
⊤ e−1/2 K(exp(x⊤ V θ V ) − exp(x e θ V ))
Ut ⊤ −1/2 −1/2 +K exp(x⊤e θ V )) (e + K exp(xV θ V ))(exp Ut ⊤ e−1/2 K(exp(x⊤ V θ V ) − exp(x e θ V )) Ut
(∵ exp(x⊤ U θ V ) ≤ e, ∀U ∈ Vd/4 )
(e−1/2 + Ke)2 e−1/2 K((xV − XUet )⊤ θ V − (x⊤e θ V )2 /2) Ut
(∵ 1 + a ≤ ea ≤ 1 + a + a2 /2, ∀a ∈ [0, 1])
(e−1/2 + Ke)2 √ √ e−1/2 K(δϵ/ d − ( dϵ)2 /2) ≥ (e−1/2 + Ke)2
√ √ √ (∵ ( dϵ)2 ≤ ϵ/ d ≤ δϵ/ d)
e−1/2 Kδϵ ≥ √ 2 d(e−1/2 + Ke)2 e−1/2 (K − 1)δϵ > √ . 2 d(e−1/2 + Ke)2
Case 2. V = [d/4]. We recall that g(S) = 0 if S contains only xU0 ’s, and otherwise g(S) = 1. For V = [d/4] = U0 , since g({x0 , . . . x0 }) = 0, we have to compare whether it is better to fill only x0 ’s in S ∗ or add another xU ′ in S ∗ , because g(S ∗ ) becomes 1 in the second case. Specifically, since the following inequality holds: ⊤ eλg(S0 ) K exp(x⊤ 0 θ U0 ) = K exp(x0 θ U0 )
< e1/2 (K − 1) exp(x⊤ 0 θ U0 ) ⊤ < eλg({xU0 ,...,xU0 ,xU ′ }) (K − 1) exp(x⊤ θ ) + exp(x θ ) , ′ 0 U0 U U0 we obtain that S ∗ = {xU0 , . . . , xU0 , xU ′ } for |U ′ ∩ [d/4] | = d/4 − 1, and g(S ∗ ) = 1. 28
Diversified MNL Contextual Bandits
et = U0 = V . In this case δ = 0, and the lemma holds trivially. Thus, If x0 ∈ St , then U we suppose that x0 ∈ / St . Then, g(St ) = 1, and we have that X X pt (i|S ∗ , θ V , λ) − pt (i|St , θ V , λ) i∈S ∗
≥
i∈S t
e−1/2 1 − −1/2 ⊤ e + (K − 1) exp(x⊤ 0 θ V ) + exp(xU ′ θ V )
= e−1/2
! −
e−1/2 1 − −1/2 e + K exp(x⊤e θ V )
!
Ut
⊤ ⊤ (K − 1) exp(x⊤ 0 θ V ) + exp(xU ′ θ V ) − K exp(x e θ V )) Ut
⊤ −1/2 +K exp(x⊤ θ )) (e−1/2 + (K − 1) exp(x⊤ 0 θ V ) + exp(xU ′ θ V ))(exp e V Ut
= e−1/2
⊤ ⊤ ⊤ (K − 1)(exp(x⊤ 0 θ V ) − exp(x e θ V )) + (exp(xU ′ θ V ) − exp(x e θ V )) Ut
Ut
(e−1/2 + Ke)2
et ̸= V and U ′ satisfies |U ′ ∩ V | = d/4 − 1, we have that exp(x⊤′ θ V ) − exp(x⊤ θ V ) ≥ 0. Since U U et U Thus the right handside is bounded by ⊤ e−1/2 (K − 1)(exp(x⊤ V θ V ) − exp(x e θ V )) Ut
≥
(e−1/2 + Ke)2 v0 (K − 1)((xV − XUet )⊤ θ V − (x⊤e θ V )2 /2) Ut
(e−1/2 + Ke)2 √ √ v0 (K − 1)(δϵ/ d − ( dϵ)2 /2) ≥ (e−1/2 + Ke)2 v0 (K − 1)δϵ ≥ √ 2 d(e−1/2 + Ke)2
(∵ 1 + a ≤ ea ≤ 1 + a + a2 /2, ∀a ∈ [0, 1])
√ √ √ (∵ ( dϵ)2 ≤ ϵ/ d ≤ δϵ/ d).
Lemma D.2 (Bound on KL divergence, Lemma D.2 of Lee and Oh(2024)). For any V ∈ Vd/4−1 and j ∈ [d], there exists a positive constant C > 0 such that h i fj ϵ2 M E V K KL(PV ∥PV ∪{j} ) ≤ C · · (1 + K)2 d Proof of Lemma D.2. In the proof of Lemma D.2 of Lee and Oh(2024), the following holds for some positive constant C > 0. KL(PV (· | Set ) ∥ PV ∪{j} (· | Set )) ≤ C ·
mj (Set )ϵ2 v0 K · , (v0 + K)2 d
et }, and v0 is a outside option parameter, defined as exp(−λg(Set )) where mj (Set ) := 1{j ∈ U e in our setting. Since g(St ) has a value of 0 or 1, we have that KL(PV (· | Set ) ∥ PV ∪{j} (· | Set )) ≤ C · 29
mj (Set )ϵ2 K · , (1 + K)2 d
Ann, Hwang, and Oh
Therefore, by the chain rule of relative entropy, we have that KL(PV ||PV ∪{j} ) =
T X
h i EV KL(PV (· | Set ) ∥ PV ∪{j} (· | Set ))
t=1
≤
T X
C·
t=1
K · (1 + K)2
h i EV mj (Set ) ϵ2 d h
i
fj ϵ2 EV M K =C· · . (1 + K)2 d
E Regret Upper Bound of Algorithm 1 (OFU-DMNL) E.1
Technical Lemmas
In this section, we introduce technical lemmas used to derive the regret bound of Algorithm 1. Lemma E.1. Suppose Assumptions 1 and 3 hold, and set ν = ω2 in Algorithm 1. Let us define the event T e as the set of rounds corresponding to adaptive exploration, as follows: ( ) ω λ̂t e T := t ∈ [T ] : ∥[0d , 1]∥H−1 > . (E.1) t 2αt Then, for t ∈ / T e , fet is monotone and submodular where fet is defined as follows: ! ! X X ⊤ exp zti (S) wt + αt ∥zti (S)∥ −1 = log exp (ucb(zti (S)) . fet (S) := log Ht
i∈S
i∈S
Proof of Lemma E.1. Suppose ∥[0d , 1]∥H−1 ≤ t
ω λ̂t holds. 2αt
Monotonicity. Recall that the diversity-augmented feature vector is defined zti (S) := [xti , gt (S)]. Then, fet (S ∪ {i}) − fet (S) can be written as follows: "P # exp (ucb([xtj , gt (S ∪ {i})])) + exp (ucb([xti , gt (S ∪ {i})])) j∈S P fet (S∪{i})−fet (S) = log . j∈S exp (ucb([xtj , gt (S)])) Then, for each j ∈ S we have ucb([xtj , gt (S ∪ {i})]) − ucb(xtj , gt (S)) = λ̂t (gt (S ∪ {i}) − gt (S)) + αt ∥[xtj , gt (S ∪ {i}])∥H−1 − ∥[xtj , gt (S)]∥H−1 t
≥ λ̂t (gt (S ∪ {i}) − gt (S)) − αt ∥[0d , gt (S ∪ {i}) − gt (S)]∥H−1 t = λ̂t − αt ∥[0d , 1]∥H−1 (gt (S ∪ {i}) − gt (S)) t ω ≥ 1− λ̂t (gt (S ∪ {i}) − gt (S)) ≥ 0, 2 30
t
Diversified MNL Contextual Bandits
where the last inequality holds since ∥[0d , 1]∥H−1 ≤ w2αλ̂tt . Therefore, we conclude fet (S ∪ t {i}) − fet (S) > 0. Submodularity. To show submodularity of fet , it is enough to show that the inequality in Eq. B.2 holds. If gt (S) = gt (S2 ), then gt (S1 ) − gt (S) ≥ gt (S3 ) − gt (S2 ) by submodularity of gt , and so gt (S1 ) ≤ gt (S3 ). By the monotonicity of gt , we have gt (S1 ) = gt (S3 ). Therefore, the inequality in Eq. B.2 holds. Now, suppose gt (S) < gt (S2 ). Then, for all j1 ∈ S and j2 ∈ S3 , we have λ̂t (gt (S1 ) + gt (S2 ) − gt (S) − gt (S3 )) + αt ∥[xt,j1 , gt (S1 )]∥H−1 + ∥[xt,j2 , gt (S2 )]∥H−1 − ∥[xt,j1 , gt (S))∥H−1 − ∥[xt,j2 , gt (S))∥H−1 t
t
t
t
≥ λ̂t (gt (S1 ) − gt (S) − (gt (S3 ) − gt (S2 ))) − αt (gt (S1 ) − gt (S)) · ∥[0d , 1]∥H−1 t
− αt (gt (S3 ) − gt (S2 )) · ∥[0d , 1]∥H−1 t
≥ λ̂t ω(gt (S1 ) − gt (S)) − 2αt (gt (S1 ) − gt (S)) · ∥[0d , 1]∥H−1 t ! λ̂t ω > λ̂t ω − 2αt (gt (S1 ) − gt (S)) ≥ 0 . 2αt
Lemma E.2. Suppose that Assumptions 1 and 3 hold. If λmin (Ht ) ≥ αlT 1 + ω2 , we have t∈ / T e. Proof of Lemma E.2. Suppose that λmin (Ht ) ≥ αTl(δ) 1 + ω2 . To show t ∈ / T e , we have to ω λ̂t prove that ∥[0, 1]∥Ht −1 ≤ . By the properties of eigenvalues, 2αt (δ) ∥[0d , 1]∥H−1 ≤ λmax (H−1 t )= t
ω ω 1 ≤ λ∗ . ≤l λmin (Ht ) (2 + ω)αT (δ) (2 + ω)αt (δ)
Since λ∗ = [0d , 1]⊤ [θ ∗ , λ∗ ] ≤ [0d , 1]⊤ (θ̂ t , λ̂t ) + αt ∥[0d , 1]∥H−1 ≤ λ̂t + αt ∥[0d , 1]∥H−1 by t t Lemma G.1, then we have ω ∥[0d , 1]∥H−1 ≤ λ̂t + αt ∥(0, 1)∥H−1 · t t (2 + ω)αt ω ω = ∥[0d , 1]∥H−1 . λ̂t + t (2 + ω)αt 2+ω ω By subtracting 2+ω ∥[0d , 1]∥H−1 on the both side, it follows that t ω ω 1− ∥[0d , 1]∥H−1 ≤ λt , t 2+ω (2 + ω)αt (δ)
and consequently, ∥[0d , 1]∥H−1 ≤ t
31
ωλt . 2αt
Ann, Hwang, and Oh
Lemma E.3. Suppose Assumptions 1 and 2 hold. Let τ := |T e ∩ [t]| denote the number of σ0 adaptive exploration rounds up to round t. Then, with probability at least 1−(d+1) exp − τ10 , we have: t X X τ Kσ0 λmin zt′ i (St′ )zt′ i (St′ )⊤ ≥ , 2 ′ t =1 i∈St′
where σ0 is defined in Eq.(7). Proof of Lemma E.3. Let Ht be the history {{Xt′ }t′ ∈[t] , {St′ }t′ ∈[t] , {yt′ }t′ ∈[t] } until round t. By Assumption 2, for any adaptive exploration round t′ ∈ T e ∩ [t], we have X X λmin E zt′ i (St′ )zt′ i (St′ )⊤ |Ht′ −1 = λmin E zt′ i (St′ )zt′ i (St′ )⊤ i∈St′
i∈St′
" #! 1 X X zt′ i (St′ )zt′ i (St′ )⊤ |S|
= λmin
S∈S
i∈S
≥ Kσ0 . Then, by the subadditivity of minimum eigenvalues, t t X X X λmin E zt′ i (St′ )zt′ i (St′ )⊤ |Ht′ −1 ≥ λmin t′ =1
E
t′ ∈T e ∩[t]
i∈St′
≥
t X
X
zt′ i (St′ )zt′ i (St′ )⊤ |Ht′ −1
i∈St′
λmin E
t′ ∈T e ∩[t]
X
zt′ i (St′ )zt′ i (St′ )⊤ |Ht′ −1
i∈St′
e
≥ |T ∩ [t]| · Kσ0 = τ Kσ0 h P hP i i t ⊤ |H ′ ′ ′ ′ ′ In other words, P λmin E z (S )z (S ) ≥ τ Kσ ) = 1 holds. ′ 0 ti t t −1 t =1 i∈St′ t i t P ⊤ ≤ K for all t′ ∈ [t] to By applying Lemma G.2 and λmax i∈St′ zt′ i (St′ )zt′ i (St′ ) compute the lower bound of the minimum eigenvalue of the Gram matrix after t rounds, we have 0 0.5 − τ Kσ t X X K τ σ0 τ Kσ e 0 ⊤ ≤ (d + 1) ≤ (d + 1)e− 10 , P λmin zt′ i (St′ )zt′ i (St′ ) ≤ 0.5 2 0.5 ′ i∈S t =1
t′
using the fact that −0.5 − 0.5 log(0.5) ≤ −0.1. Lemma E.4. Suppose that Assumptions 1, 2, and 3 hold. If we set ν = ω2 in Algorithm 1, √ σ
−O( 0
d log K
)
κKlλ ω then for δ ∈ (0, 1) with probability 1 − δ − (d + 1)T , the total number of adaptive exploration rounds is bounded as follows: ! √ d log T log K e |T | = O . κKσ0 ωl
32
Diversified MNL Contextual Bandits
Proof of Lemma E.4. We will show that the number of adaptive exploration rounds can not 2αT 2αT exceed κlKσ 1 + ω2 rounds by contradiction. Suppose Algorithm 1 induces κlKσ 1 + ω2 0 0 adaptive rounds. Then, by √Lemma E.3, with probability at least 1 − (d + exploration 2 σ0 d log K 2αT (1+ ω ) = 1 − (d + 1)T −O( κKωl ) , we have 1) exp − 10κlK 1 αT λmin (Vt+1 ) ≥ κ l
2 1+ , ω
P P d ⊤ where Vt := t−1 t′ =1 i∈St′ zt′ i (St′ )zt′ i (St′ ) . Note that for any xi , xj ∈ R , (xi − xj )(xi − ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ xj )⊤ = xi x⊤ i + xj xj − xi xj − xj xi ⪰ 0d×d , which implies xi xi + xj xj ⪰ xi xj + xj xi . To simplify, for i ∈ St , if we abbreviate pt (i | St , wt ) by pti (wt ) and zti (St ) by zti , then for all s ∈ [t − 1], we have X XX Gs (ws+1 ) = psi (ws+1 )zsi z⊤ psi (ws+1 )psj (ws+1 )zsi z⊤ si − sj i∈Ss
=
X
i∈Ss j∈Ss
i∈Ss
⪰
X
=
XX
XX
psi (ws+1 ) 1 −
=
psi (ws+1 )psj (ws+1 ) zsi z⊤ si
X
psj (ws+1 ) zsi z⊤ si
j∈Ss
i∈Ss
X
⊤ psi (ws+1 )psj (ws+1 ) zsi z⊤ si + zsj zsj
i∈Ss j∈Ss
=
i∈Ss j∈Ss
psi (ws+1 )zsi z⊤ si −
i∈Ss
X
⊤ psi (ws+1 )psj (ws+1 ) zsi z⊤ sj + zsj zsi
i∈Ss j∈Ss 1 psi (ws+1 )zsi z⊤ si − 2
i∈Ss
X
XX
1 psi (ws+1 )zsi z⊤ si − 2
psi (ws+1 )ps0 (ws+1 )zsi z⊤ si
i∈Ss
⪰κ
X
zsi z⊤ si ,
i∈Ss
where κ := mint∈[T ],S∈S,i∈S,∥θ∥2 ≤1,0≤λ≤1 pt (i|S, θ, λ)pt (0|S, θ, λ) > 0. Hence, we have Ht+1 = ΛId+1 +
t−1 X
Gs (ws+1 ) ⪰ ΛId+1 + κ
s=1
Thus, it holds that
t−1 X X
zsi z⊤ si ⪰ κVt+1 .
s=1 i∈Ss
α λmin (Ht+1 ) ≥ κλmin (Vt+1 ) ≥ l
2 1+ . ω
By Lemma E.2, this implies t + 1 ∈ / T e . Therefore, with probability at least 1 − δ − (d + √ 1)T −O(
σ0
d log K ) κKωl
, the number of adaptive exploration rounds is bounded by ! √ 2αT 2 d log T log K e |T | ≤ 1+ =O . κlKσ0 ω κKσ0 ωl
33
Ann, Hwang, and Oh
E.2
Proof of Theorem 3
Proof of Theorem 3. We define the event T e as the set of rounds corresponding to adaptive exploration, formally defined in Equation E.1. For t ∈ / T e , by Lemma E.1 since fet in Eq.(B.1) is monotone and submodular, we have R(St∗ , θ ∗ , λ∗ ) = ≤
exp(ft (St∗ )) 1 + exp(ft (St∗ )) exp(fet (S ∗ )) t
1 + exp(fet (St∗ )) e exp ( e−1 )fet (St )) ≤ e 1 + exp ( e−1 )fet (St )) } h i( e ) e−1 exp fet (St )) = h i( e ) e−1 1 + exp fet (St )) e+1 e ≤ Rt (St ) , e
(∵ fet is submodular)
α ψ ψ where the last inequality holds because h(ψ) := 1+ψ / < 1 + 1e holds for ψ = α 1+ψ exp(fet (St )) and α = e (refer to the proof of Theorem 1). e−1
Therefore, with probability 1 − δ − (d + 1)T
γ
R (T ) =
T X
σ
√ d log K
−O( 0 κKlω
)
,
E[γRt (St∗ , θ ∗ , λ∗ ) − Rt (St , θ ∗ , λ∗ )
t=1
≤
X
E[γRt (St∗ , θ ∗ , λ∗ ) − Rt (St , θ ∗ , λ∗ ) + |T e |
t∈T / e
≤
X t∈T / e
et (St ) − Rt (St , θ ∗ , λ∗ )] + |T e | E[R √
e =O √ e =O
K(d + 1) √ 1 · T + (d + 1)2 K +1 κ
√
! +O
d log T log K κKσ0 ωl !
√ K(d + 1) √ 1 d 2 · T + (d + 1) + K +1 κ κKσ0 ωl
! (E.2)
,
where for Eq.(E.2), we invoke the regret bound of OFU-MNL+ under uniform revenue setting e t ) serves as an from Lee and Oh (2024), as our diversified optimistic expected reward R(S ∗ ∗ optimistic estimate of Rt (St , θ , λ ). The subsequent analysis closely follows the proof of Theorem 2 in Lee and Oh (2024). 34
Diversified MNL Contextual Bandits
F Experimental Details F.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 F.1 OFU-MNL-DR (OFU-MNL-Diversity integrated Reward) diversity function {gt }t≥1 , regularization parameter Λ, confidence radius {αt }t≥1 , step size η, balancing diversity parameter λ 2: Initialization: H1 = ΛId and θ 1 at any point in {θ ∈ Rd : ∥θ∥2 ≤ 1} 3: for t = 1, . . . , T do 4: Compute ut,i = x⊤ t,i θ t + αt ∥xt,i ∥H−1 t 5: St ← ∅ 6: for k = 1, . . . , K do h P i 1: Input:
7:
at,k ← argmaxe∈[N ]\St
8:
St ← St ∪ {at,k }
9: 10: 11:
i∈St ∪{e} exp(ut,i ) P 1+ i∈S ∪{e} exp(ut,i ) + λg(St ∪ {e}) t
Offer St and observe yt e t = Ht + η Gt (θ t+1 ), and update the estimator θ t+1 Update H Update Ht+1 = Ht + Gt (wt+1 )
Algorithm F.2 OFU-DMNL-FULL (OFU-DMNL with exhaustive-search) 1: Input: diversity function {gt }t≥1 , regularization parameter Λ, confidence radius {αt }t≥1 ,
step size η, exploration parameter ν 2: Initialization: H1 = ΛId+1 and w1 at any point in W. 3: for t = 1, . . . , T do et (S), and observe yt 4: Offer St ← argmax R S∈S
5:
e t = Ht + η Gt (wt ), wt+1 , and Ht+1 = Ht + Gt (wt+1 ) Update H
Algorithm for MNL bandits with submodular rewards. We consider the item-wise optimistic construction algorithm OFU-MNL-DR (Algorithm F.1) for the original MNL choice model with a submodular reward function as a baseline. Inspired by Qin et al. (2014), diversity in the original can be promoted by modifying only the reward function P MNL bandit ∗ ⊤ j∈S exp(xtj θ ) P as Rt′ (S, θ ∗ , λ) := ∗ + λg(S), where g(S) is the diversity score function, 1 + j∈S exp(x⊤ tj θ ) and λ is a balancing parameter between relevance and diversity. We adapt OFU-MNL+ with greedy assortment construction to maximize Rt′ . Notably, OFU-MNL+ requires the value of λ to be specified as a hyperparameter. Exhaustive-Search Algorithm for DMNL bandits. We also consider the exhaustivesearch algorithm, referred to as OFU-DMNL-FULL (Algorithm F.2), for the DMNL bandit 35
Ann, Hwang, and Oh
N model. This algorithm evaluates all K possible assortments in each round and thus requires eN K approximately O reward estimations per round. K Experimental Results in Diverse Environments
F.2.1
Runtime Comparison TS-MNL
OFU-MNL+
N=10, K=5, d=5, =0.4
50
Total Runtime (sec)
Total Runtime (sec)
UCB-MNL
40 30 20 10 0
0
2000
4000
6000
Rounds (t)
8000
10000
OFU-MNL-DR
OFU-DMNL-Full
N=20, K=5, d=5, =0.4
200
Total Runtime (sec)
F.2
150 100 50 0
0
2000
4000
6000
Rounds (t)
8000
10000
OFU-DMNL (ours)
N=30, K=5, d=5, =0.4
200 150 100 50 0
0
2000
4000
6000
Rounds (t)
8000
10000
40
200
Total Runtime (sec)
50
Total Runtime (sec)
Total Runtime (sec)
Figure F.1: Cumulative runtime of N=20, algorithms under N = 10,N=30, 20,K=5, 30d=5, and T = 1000 N=10, K=5, d=5, =0.4 K=5, d=5, =0.4 =0.4 200
150 The 30results in Figure F.1 shows150 that our algorithm operates very efficiently by leveraging 100 100 online mirror descent. In particular, compared to the exhaustive-search algorithm, which 20 50 requires 10per-round O((eN/K)K ) computation, our algorithm50runs in O(N K) time and thus 0 0 achieves 0incomparably better performance in large-N settings. Although it 8000 is slower than 0 2000 4000 6000 8000 10000 0 2000 4000 6000 8000 10000 0 2000 4000 6000 10000 Rounds (t) Rounds (t) Rounds (t) other OMD-based MNL algorithms due to the cost of item-wise construction, it is 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 OFU-DMNL-FULL is entirely 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.
F.2.2
Regret Comparison
As shown in Figure F.2, our algorithm demonstrates strong performance even when N and K are large. Furthermore, Figure F.3 shows that as the balance between ∥θ ∗ ∥2 and λ∗ 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.
36
Diversified MNL Contextual Bandits
OFU-MNL+
20 15 10 5 0 0
2000
4000
6000
Rounds (t)
8000
N=100, K=10, d=5, =0.4
20
10 5 0 0
10.0 7.5 5.0 2.5 0.0 6000
Rounds (t)
4000
6000
Rounds (t)
8000
10 5 0
10000
0
8000
10000
15 10 5 0 0
2000
4000
6000
Rounds (t)
8000
2000
4000
6000
Rounds (t)
8000
10000
N=150, K=10, d=5, =0.6
20
Cumulative Regret
12.5
4000
2000
15
N=100, K=10, d=5, =0.6
Cumulative Regret
Cumulative Regret
N=50, K=10, d=5, =0.6
2000
N=150, K=10, d=5, =0.4
15
10000
15.0
0
OFU-DMNL (ours)
Cumulative Regret
Cumulative Regret
Cumulative Regret
N=50, K=10, d=5, =0.4
OFU-MNL-DR
20 15 10
10000
5 0 0
2000
4000
6000
Rounds (t)
8000
10000
Figure F.2: Performance of algorithms under various (N, K, λ∗ ) configurations
10 0
0
5000 10000 15000 20000 25000 30000
40 30 20 10 0
0
20 10 0
Rounds (t)
N=100, K=10, d=5, =0.4
50
30
5000 10000 15000 20000 25000 30000
Rounds (t)
0
5000 10000 15000 20000 25000 30000
40 30 20 10 0
0
40 30 20 10 0
Rounds (t)
N=100, K=10, d=5, =0.5
50
5000 10000 15000 20000 25000 30000
Rounds (t)
N=50, K=10, d=5, =0.6
50
Cumulative Regret
20
40
OFU-DMNL (ours)
0
5000 10000 15000 20000 25000 30000
N=100, K=10, d=5, =0.6
50 40 30 20 10 0
0
5000 10000 15000 20000 25000 30000
Rounds (t)
N=50, K=10, d=5, =0.7
50 40 30 20 10 0
Rounds (t)
Cumulative Regret
30
N=50, K=10, d=5, =0.5
50
Cumulative Regret
Cumulative Regret
40
OFU-MNL-DR
Cumulative Regret
N=50, K=10, d=5, =0.4
50
Cumulative Regret
Cumulative Regret
Cumulative Regret
OFU-MNL+
0
5000 10000 15000 20000 25000 30000
Rounds (t)
N=100, K=10, d=5, =0.7
50 40 30 20 10 0
0
5000 10000 15000 20000 25000 30000
Rounds (t)
Figure F.3: Performance of algorithms under different balances between relevance and diversity
37
Ann, Hwang, and Oh
F.3
Experiment based on real-world Data
We additionally designed a semi-synthetic experiment based on a real-world dataset, which provides the most practical and feasible alternative in the absence of access to online field deployment. We used the Massive Rotten Tomatoes Movie & Review dataset provided in Kaggle (https://www.kaggle.com), which contains over 1.4M+ reviews on 140K+ unique movies, each labeled as positive or negative, along with rich movie-level metadata. We first converted each review text into a vector representation using TF-IDF (via TfidfVectorizer from scikit-learn), followed by dimensionality reduction using truncated SVD to obtain d-dimensional context vectors. This process resulted in a context–label 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 an online assortment selection 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) := 1 + ρ + . . . + ρnS −1 , where nS is the number of categories covered by the assortment S. TS-MNL
OFU-MNL+
N=30, K=5, d=5
Cumulative Regret
100 80 60 40 20 0
0
2000
4000
6000
Rounds (t)
8000
10000
40 30 20 10 0
2000
4000
6000
Rounds (t)
8000
10000
OFU-DMNL (ours)
N=30, K=5, d=10
100
N=50, K=10, d=5
50
0
OFU-MNL-DR
Cumulative Regret
Cumulative Regret
Cumulative Regret
UCB-MNL
80 60 40 20 0
0
2000
4000
6000
Rounds (t)
8000
10000
8000
10000
N=50, K=10, d=10
30 25 20 15 10 5 0
0
2000
4000
6000
Rounds (t)
Figure F.4: Performance of algorithms with synthetic data
As shown in Figure F.4, our algorithm performs robustly in the synthetic-data experiments and consistently outperforms the baseline algorithms. These results suggest that our method is also likely to perform well on real-world data. 38
Diversified MNL Contextual Bandits
G Auxiliary Lemmas Proposition G.1 (Proposition B.6 in Bach (2013)). Let f be a monotone submodular function and ϕ a non-decreasing concave function. Then, the composition function ϕ(f (S)) is submodular. Proof of Proposition G.1. Define h(S) := ϕ(f (S)). By submodularity of f , for any S1 ⊆ S2 and e ∈ / S2 , we have f (S1 ∪ {e}) − f (S1 ) ≥ f (S2 ∪ {e}) − f (S2 ) . Also, concavity and non-decreasing property of ϕ imply that the difference ψ(x, δ) = ϕ(x + δ) − ϕ(x) is non-increasing in the x and non-decreasing in δ. That is, if x1 ≤ x2 , then ψ(x1 , δ) ≥ ψ(x2 , δ), and if δ1 ≤ δ2 , then ψ(x, δ1 ) ≤ ψ(x, δ2 ). Using this, we obtain the following: ϕ(f (S1 ∪ {e})) − ϕ(f (S1 )) = ϕ(f (S1 ) + f (S1 ∪ {e}) − f (S1 )) − ϕ(f (S1 )) = ψ(f (S1 ), f (S1 ∪ {e}) − f (S1 )) ≥ ψ(f (S2 ), f (S1 ∪ {e}) − f (S1 ))
(∵ f (S1 ) ≤ f (S2 ))
≥ ψ(f (S2 ), f (S2 ∪ {e}) − f (S2 )) (∵ f (S1 ∪ {e}) − f (S1 ) ≥ f (S2 ∪ {e}) − f (S2 )) = ϕ(f (S2 ) + f (S2 ∪ {e}) − f (S2 )) − ϕ(f (S2 )) = ϕ(f (S2 ∪ {e})) − ϕ(f (S2 )) . This inequality is exactly h(S1 ∪ {e}) − h(S1 ) ≥ h(S2 ∪ {e}) − h(S2 ) , which shows that h is also submodular. Lemma G.1 (Lemma 1 in Lee and Oh (2024)).√ Suppose that Assumption √ 1 hold. For any δ ∈ (0, 1], if we set η = 12 log(K + 1) + 2, Λ = 84 2(d + 1)η, and αt = O( d + 1 log t log K), then we have P (∀t ≥ 1, ∥wt − w∗ ∥Ht ≤ αt ) , where the estimated parameter updated by the rule in Eq.(3). Lemma G.2 (Theorem 3.1 in Tropp (2011)). Let H1 ⊂ H2 · · · be a filtration and consider a finite sequence {Xk } of positive semi-definite matrices with dimension d adapted P to this filtration. Suppose that λ (X ) ≤ R almost surely. Define the series Y ≡ max k k Xk and P W ≡ k E[Xk |Hk−1 ]. Then for all µ ≥ 0, γ ∈ [0, 1) we have P[λmin (Y ) ≤ (1 − γ)µ and λmin (W ) ≥ µ] ≤ d(
39
e−γ )µ/R . (1 − γ)1−γ