{"id":"88216803-6527-4ef2-ba2f-a6c937f1fbe5","arxiv_id":"2607.11684","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"OFU-DMNL achieves a (1-1/(e+1))-approximate regret bound Õ(d √(T/K)) for contextual assortment selection under a diversity-augmented MNL choice model via item-wise optimistic construction.","lead":"The paper introduces diversified multinomial logit (DMNL) contextual bandits that fold a submodular diversity score into MNL choice probabilities, then gives a white-box UCB algorithm that builds assortments greedily. This yields a (1-1/(e+1))-approximate regret of order d sqrt(T/K) without black-box oracles, useful for diversity-aware recommenders.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified beyond the reader's already-flagged ω-strict-submodularity assumption.","rationale":"I re-examined the chain from the DMNL model (Def. 1) through the item-wise optimistic construction (Eq. 6), the restoration of submodularity of êf_t (Lemma E.1), the forced-exploration bound (Lemma E.4), and the final regret decomposition (proof of Thm. 3). Every step is internally consistent once Assumptions 1–3 are granted; the matching lower bound (Thm. 2) and the improved approximation ratio (Thm. 1) further corroborate that the modeling and algorithmic contributions are sound. The sole non-standard hypothesis is precisely the ω-strict-submodularity already highlighted by the reader; no stronger or additional load-bearing gap appears. Consequently the ACCEPT verdict with high confidence stands, and the concrete test above is offered only as a practical stress check of that already-identified caveat.","tokens_in":37454,"tokens_out":610,"duration_ms":5138,"concrete_test":"Instantiate g_t as ordinary (non-strict) coverage, e.g., g(S)=|categories covered by S|, which is monotone submodular but not ω-strict for any fixed ω>0. Run OFU-DMNL for T=10^4, N=50, K=5, d=5 and record (i) whether the empirical cumulative γ-regret still tracks the claimed Õ(d√(T/K)) envelope and (ii) the fraction of rounds that trigger the adaptive-exploration branch. If either quantity degrades by more than a constant factor relative to the exponential-decay g used in the paper, the dependence on strictness is load-bearing in practice.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 3) holds under the stated Assumptions 1–3. The only material soft spot is exactly the one the reader already isolates: Assumption 3 (ω-strict submodularity of g_t) is required both for Lemma E.1 (to restore submodularity of the optimistic LogSumExp after the UCB terms appear) and for the O(√d log T) bound on forced-exploration rounds in Lemma E.4. Ordinary submodularity is insufficient for the inequality that cancels the weighted-norm increments (display after Eq. B.2). The paper is transparent about this; the lower bound (Theorem 2) and the improved approximation factor (Theorem 1) do not rely on strictness. No hidden inconsistency, missing case, or unstated dependence on intermediate feedback was found.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper introduces the diversified multinomial logit (DMNL) contextual bandit, which embeds a monotone submodular diversity score g_t into the outside-option attraction of the classical MNL choice model, thereby coupling relevance utilities with within-assortment diversity. Exact assortment optimization becomes intractable, so the authors propose OFU-DMNL: an online-mirror-descent UCB algorithm that builds assortments by item-wise maximization of optimistic marginal gains (Eq. 6) without a black-box combinatorial oracle. Under Assumptions 1–3 they prove that the greedy construction attains an improved approximation factor γ ≥ 1−1/(e+1) (Theorem 1), that the problem admits a matching Ω(d √(T/K)) lower bound (Theorem 2), and that OFU-DMNL achieves a high-probability γ-approximate regret of order Õ(d √(T/K)) (Theorem 3). Experiments on synthetic and semi-synthetic Rotten Tomatoes data show competitive regret versus exhaustive search at far lower runtime.","tokens_in":37706,"tokens_out":884,"duration_ms":8164,"significance":"The work cleanly closes a modeling gap between relevance-driven MNL assortment bandits and diversity-aware submodular/combinatorial bandits. The white-box item-wise construction, the improved approximation factor that exploits MNL structure, and the nearly minimax regret that matches the lower bound up to the approximation factor and lower-order terms are all technically non-trivial. Full proofs appear in the appendices, concentration arguments reuse the standard OFU-MNL toolkit of Lee & Oh (2024), and the experimental suite (multiple (N,K,λ*) regimes plus a semi-synthetic movie-review environment) is reproducible and informative. The free parameters ω and l are stated explicitly; the paper does not hide them inside fitted constants.","major_comments":[{"comment":"Assumption 3 (ω-strict submodularity of g_t, Definition 2) is load-bearing for both Lemma E.1 (restoration of submodularity of the optimistic LogSumExp after UCB terms appear) and Lemma E.4 (O(√d log T) bound on forced-exploration rounds). Ordinary submodularity is insufficient to cancel the weighted-norm increments that appear after Eq. (B.2). The paper is transparent about this dependence, and Theorems 1–2 do not require strictness, yet the main algorithmic guarantee (Theorem 3) collapses without it. A short discussion of how restrictive the condition is for common diversity measures (beyond the two categorical examples in Appendix B.2) would strengthen the claim that the result is practically relevant.","section":null}],"minor_comments":[{"comment":"In the abstract and introduction the regret is written Õ(d √(T/K)); Theorem 3 states the more precise form Õ(√K(d+1)/(K+1)·√T + …). Aligning the two statements would avoid confusion.","section":null},{"comment":"Figure 1 caption and the surrounding text use “DMNL setting” without defining the concrete diversity function used for the illustration; a one-line clarification would help.","section":null},{"comment":"Typographical inconsistencies appear in several places (e.g., “eO” versus “Õ”, missing spaces around “λ*”, and the occasional “ans” for “and” in §5). A careful copy-edit pass is warranted.","section":null},{"comment":"The experimental section reports averages over 10 runs but does not display error bars or standard deviations in the main figures; adding them (or stating that they are negligible) would improve readability.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is a solid, self-contained contribution that sits comfortably within the scope of a top ML / OR journal. The only material soft spot is the ω-strict-submodularity assumption already flagged by the reader; it is not a hidden flaw and can be addressed by a short discussion. I see no citation or novelty issues that would require editorial intervention."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper does something useful: it puts a generally submodular diversity score directly into the MNL choice probabilities rather than only into the reward, then gives a practical white-box UCB algorithm that builds the assortment item-wise and still gets a (1-1/(e+1))-approximate regret of order d sqrt(T/K). That rate matches the pure-MNL lower bound they prove, even though they are also learning the diversity weight. The improved approximation factor over classical submodular greedy is a nice structural observation that comes from the specific shape of the MNL reward.\n\nWhat works well is the end-to-end package. They avoid black-box oracles, give complete proofs for the approximation, the lower bound, and the upper bound, and the experiments (synthetic plus a Rotten Tomatoes semi-synthetic) show the method tracks exhaustive search while running far faster. The adaptive-exploration trigger that keeps the diversity-parameter confidence under control is cleanly analyzed and only costs O(sqrt(d) log T) rounds. Citations look honest; they sit on top of the recent OFU-MNL line (especially Lee & Oh) without pretending the concentration arguments are new.\n\nThe soft spot is exactly the one already flagged: they need omega-strict submodularity of the diversity function so that the optimistic LogSumExp remains submodular after the UCB terms appear and so that the forced-exploration count stays small. Ordinary submodularity is not enough for that cancellation. The paper is transparent about it, and neither the improved approximation nor the lower bound relies on strictness, so the modeling contribution still stands. Boundedness and non-degeneracy are standard.\n\nThis is for people who work on assortment bandits or diversity-aware recommenders and want a model that couples the two effects inside the choice probabilities. It deserves a serious referee. I would bring it to reading group and expect to cite the model and the white-box construction.","headline":"Clean joint model of relevance and diversity inside MNL choice, with a white-box algorithm whose approximate regret matches pure-MNL rates; the only real caveat is the strict-submodularity assumption needed for the optimistic analysis.","tokens_in":38300,"tokens_out":493,"would_cite":true,"duration_ms":5713,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","68T05","90C27"],"pacs":[],"model":"grok-4.5","headline":"A new bandit model embeds assortment diversity into MNL choice probabilities and learns both relevance and diversity with nearly minimax approximate regret.","keywords":["contextual bandits","multinomial logit","assortment optimization","diversity","submodular maximisation","UCB","approximate regret"],"falsifier":"Construct a monotone submodular diversity function that is not ω-strict for any fixed ω>0, run OFU-DMNL, and check whether the cumulative (1-1/(e+1))-approximate regret still grows as Õ(d √(T/K)) or whether the approximation guarantee collapses.","tokens_in":38353,"feed_emoji":"📦","tokens_out":966,"duration_ms":7663,"temperature":0.7,"pith_summary":"Standard contextual multinomial-logit bandits decide which set of items to show by estimating only how relevant each item is; they never model the fact that a more diverse slate often raises the chance a user picks something. This paper defines the diversified MNL (DMNL) model, which multiplies the usual MNL denominators by a monotone submodular diversity score so that relevance and diversity trade off inside a single choice probability. Exact optimization of the resulting expected reward is hard, so the authors give a white-box algorithm that builds the assortment item by item, always adding the product that most improves an optimistic estimate of that reward. Under a mild strengthening of submodularity they prove that the procedure is at least a (1-1/(e+1))-approximation of the optimal assortment and that the cumulative approximate regret scales as Õ(d √(T/K)), matching the information-theoretic lower bound up to the approximation factor. Experiments confirm that the method matches exhaustive-search regret while running far faster, and that it outperforms both pure-relevance MNL bandits and manually-tuned diversity hybrids. The result supplies a practical, oracle-free foundation for diversity-aware sequential assortment decisions.","feed_headline":"Diversity enters MNL bandits with nearly-optimal regret","feed_subtitle":"White-box item-wise UCB learns relevance and diversity together at Õ(d √(T/K)) cost","key_machinery":"Item-wise optimistic construction: at each step the algorithm adds the single item that maximises the optimistic DMNL expected reward of the enlarged set; under ω-strict submodularity the optimistic reward remains submodular, yielding both the improved approximation factor and the regret bound without an external optimisation oracle.","core_discovery":"The diversified multinomial logit contextual bandit jointly encodes item relevance and within-assortment diversity inside MNL choice probabilities; the white-box algorithm OFU-DMNL that constructs assortments by successive optimistic marginal gains attains a (1-1/(e+1))-approximate regret of order d √(T/K) that is nearly minimax optimal.","pith_inferences":["The same item-wise optimistic construction may extend to other discrete-choice models (nested logit, mixed logit) once an analogous strict-submodularity condition is verified.","If the diversity parameter itself is allowed to depend on user context, the same analysis would yield a contextual diversity model without changing the algorithmic skeleton.","The forced-exploration phase that restores submodularity is short; replacing it with a more refined confidence-set projection could remove the last logarithmic dependence on 1/ω."],"forward_implications":["Diversity-aware assortment policies can be learned online without black-box combinatorial oracles and without hand-tuned relevance-diversity weights.","The (1-1/(e+1)) approximation factor is strictly better than the classical (1-1/e) guarantee for general submodular maximisation under cardinality constraints.","The regret matches the known lower bound for ordinary MNL bandits (up to the approximation factor), so the extra diversity parameter does not increase the statistical price.","Any diversity measure that is monotone and ω-strictly submodular (category coverage, embedding dispersion, etc.) can be plugged in directly."],"fun_headline_variants":["DMNL fuses diversity into MNL choice with white-box UCB regret","OFU-DMNL builds assortments via optimistic gains at Õ(d√(T/K))","White-box item-wise UCB hits (1-1/(e+1))-approx DMNL regret","Contextual DMNL bandits trade off relevance and assortment diversity","Submodular diversity joins MNL probabilities under nearly-optimal bound"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The diversity score must be strictly submodular with a fixed positive gap (ω-strict submodularity); ordinary submodularity alone does not guarantee that the optimistic reward stays submodular after estimation error.","fun_headline_variants_meta":{"raw":{"variants":["DMNL fuses diversity into MNL choice with white-box UCB regret","OFU-DMNL builds assortments via optimistic gains at Õ(d√(T/K))","White-box item-wise UCB hits (1-1/(e+1))-approx DMNL regret","Contextual DMNL bandits trade off relevance and assortment diversity","Submodular diversity joins MNL probabilities under nearly-optimal bound"]},"model":"grok-4.5","effort":"low","cost_usd":0.005696,"raw_usage":{"total_tokens":1562,"prompt_tokens":823,"num_sources_used":0,"completion_tokens":92,"cost_in_usd_ticks":56960000,"prompt_tokens_details":{"text_tokens":823,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":647,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":823,"tokens_out":92,"duration_ms":5230,"temperature":1.0,"reasoning_tokens":647,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T03:53:35.560760+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Construct a monotone submodular diversity function that is not ω-strict for any fixed ω>0, run OFU-DMNL, and check whether the cumulative (1-1/(e+1))-approximate regret still grows as Õ(d √(T/K)) or whether the approximation guarantee collapses.","supporting_citations":[],"review_version":1}