{"id":"d90d25ef-b149-4488-a7d0-f7e61497d124","arxiv_id":"2502.10020","paper_version":5,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"New ℓ∞-self-concordant analysis and Ville's-inequality martingale control yield an online confidence bound of O(√(d log t) + B√d), leading to variance-dependent MNL bandit regret with no K dependence and only asymptotic B dependence.","lead":"This paper gives tighter confidence bounds for multinomial logistic bandits, removing the assortment-size K from the bound and, in an asymptotic regime, the parameter-norm B. The two proposed algorithms, one constant-time and one MLE-based, are claimed to achieve the first variance-dependent regret bounds in this setting.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised B,K-free variance-dependent regret is not established at the stated threshold: at T≈Õ(e^{B²}+B⁸d²/κ²), the dropped 1/κ additive terms can dominate the variance term when Σσ_t² is small, and the threshold itself grows doubly exponentially in B.","rationale":"The reader's conditional verdict is well aligned with the main weakness: the headline B-free, K-free regret is asymptotic and conditioned on large T and small 1/κ. My stress-test sharpens this: even at the stated threshold T≥Õ(e^{B²}+B⁸d²/κ²), the proof does not yield the simplified O(d logT√Σσ_t²) bound for instances where Σσ_t² is small, because the additive (1/κ)B³d²(logT)² term is not dominated by the variance term. This is a genuine gap between the theorem statement (which includes additive terms) and the advertised claim in the abstract. The theorem itself appears internally coherent: Theorem 4.2's proof is intricate but the main steps (the ℓ∞ self-concordance, the Ville supermartingale, and the restricted-space construction) are consistent on inspection, and the warm-up event w*∈W_t^w(δ) is a standard high-probability conditioning. The imported MLE confidence sequence for OFU-M²NL and the under-specified experimental threshold are secondary concerns; they do not affect the core OFU-MNL++ argument. Therefore the reader's CONDITIONAL verdict remains appropriate, and I do not recommend changing it. The concrete check above would either confirm the overclaim or reveal additional structure (e.g., σ_t² is never that small under Assumption 3.1) that rescues the simplified bound.","tokens_in":51,"tokens_out":46604,"duration_ms":587183,"concrete_test":"Fix d=2, B=4, K=2, and set κ=1/(K²e^{3B}). Choose rewards so σ_t²=1/T for every t, giving √Σσ_t²=1. Let T=c·e^{B²} with a moderate constant c. Evaluate the right-hand side of Theorem 4.5 at this T: compare d log T√Σσ_t² ≈ d log T with the additive term (1/κ)B³d²(log T)². If the additive term is larger by a factor polynomial/exponential in B, the claimed O(d log T√Σσ_t²) bound is not obtained at the stated threshold. Repeating at T=c·B⁸d²/κ² should show the same issue unless an additional lower bound on Σσ_t² is supplied.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.5 states Reg_T ≤ O((d log T + B d√log T)√Σσ_t² + (1/κ)B³d²(log T)² + (1/κ)B⁴d log T). The discussion then claims that for T ≥ Õ(e^{B²}+B⁸d²/κ²) this becomes O(d log T√Σσ_t²). That simplification requires the additive (1/κ)B³d²(log T)² term to be dominated by d log T√Σσ_t², i.e., √Σσ_t² ≥ (1/κ)B³d log T. The stated size of T does not imply this: e.g., with σ_t²=1/T for all t, √Σσ_t²=1, and at T≈e^{B²} the additive term is about (1/κ)B⁷d², which is larger than d log T by a factor (1/κ)B⁵d. Since 1/κ=O(K²e^{3B}), that factor is exponential in B, so the B-free claim is not a consequence of the theorem for low-variance instances. Moreover, the threshold T ≥ B⁸d²/κ² itself is doubly exponential in B and K, so the advertised 'B-free, K-free' regime is unreachable in any practical finite horizon. The theorem with explicit additive terms is correct as stated, but the headline simplification in the abstract and Section 4.2 overclaims what the proof establishes.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops an improved online confidence bound for multinomial logistic (MNL) models, based on new self-concordance-like properties in the ℓ∞-norm and on Ville's inequality rather than the previously used Bernstein-type arguments. This bound is then applied to two MNL bandit algorithms: OFU-MNL++, a constant-time algorithm with an adaptive warm-up phase and a restricted confidence ellipsoid, and OFU-M2NL, an MLE-based algorithm. The paper claims regret bounds of the form O((d log T + B d sqrt(log T)) sqrt(sum_t σ_t^2)) plus additive 1/κ terms for OFU-MNL++, and O(d log(BT) sqrt(sum_t σ_t^2)) plus additive 1/κ terms for OFU-M2NL, and further claims that the additive terms vanish for sufficiently large T, yielding B-free, K-free variance-dependent regret.","tokens_in":46192,"tokens_out":15704,"duration_ms":153554,"significance":"The technical core of the paper is valuable: the ℓ∞-norm self-concordance properties in Propositions B.3–B.6 are a genuine improvement over the existing ℓ2-norm treatments, and the Ville-based supermartingale argument in Lemma C.2 gives a cleaner bound on the main estimation term than the smoothed Bernstein argument of Lee and Oh (2024). The explicit theorem statements with additive 1/κ terms are plausible and would already be a useful contribution to the MNL bandit literature, especially the constant-time OFU-MNL++ update and the variance-dependent regret decomposition. However, the headline asymptotic claim that the regret becomes B-free and K-free for sufficiently large T is not established by the stated theorems for low-variance instances, and the MLE-based 'poly(B),K-free anytime' claim is also overstated. No code is provided, so reproducibility rests on the mathematical appendices.","major_comments":[{"comment":"The claimed simplification of Theorem 4.5 to O(d log T sqrt(sum_{t=1}^T σ_t^2)) for T ≥ Õ(e^{B^2} + B^8 d^2 / κ^2) is not a consequence of the stated bound. Theorem 4.5 gives Reg_T ≤ O((d log T + B d sqrt(log T)) sqrt(sum σ_t^2) + (1/κ)B^3 d^2 (log T)^2 + (1/κ)B^4 d log T). The threshold T ≥ Õ(e^{B^2} + B^8 d^2/κ^2) only ensures that the B d sqrt(log T) factor in the leading term is dominated by d log T. Dominating the additive terms requires sqrt(sum σ_t^2) ≥ (1/κ)B^3 d log T + (1/κ)B^4, and no such lower bound on the reward variance is assumed or implied. For example, if σ_t^2 = 1/T for all t, then sqrt(sum σ_t^2) = 1, and at T = e^{B^2} the additive term is about (1/κ)B^7 d^2 while the variance term is d B^2; since 1/κ = O(K^2 e^{3B}), the additive term is exponentially larger. The explicit two-term bound in Theorem 4.5 may be correct, but the advertised B-free, K-free regime requires either an explicit lower-bound condition on sum σ_t^2 or a reformulation of the claim.","section":"Appendix D.2.3, Lemma D.6"},{"comment":"The proof of Lemma D.6 is not valid as written. It argues that if r_ti < tR_t(S_t), then removing item i from S_t would increase the optimistic revenue tR_t(S_t), contradicting optimality. But removing i increases tR_t(S_t) if and only if r_ti < tR_t(S_t \\ {i}), and tR_t(S_t \\ {i}) can be larger than tR_t(S_t). The lemma itself is true, because for an optimal assortment under an MNL model the revenue of the assortment is a weighted average of r_ti and the revenue after removing i, so r_ti ≥ tR_t(S_t) follows from optimality, but the displayed contradiction needs a repaired argument.","section":"Appendix D.2.3, Lemma D.6"},{"comment":"The claim that OFU-M2NL achieves 'completely poly(B), K-free regret' is too strong. The theorem states a regret bound of O(d log(BT) sqrt(sum σ_t^2) + (1/κ)d^2(log(BT))^2), and 1/κ = O(K^2 e^{3B}) is exponential in B and quadratic in K. Thus the additive term is neither poly(B)-free nor K-free. Moreover, the same low-variance issue as in Theorem 4.5 applies: the additive term can dominate the variance term unless an explicit lower bound on sqrt(sum σ_t^2) is imposed. The leading-term claim with an explicit additive term would be fine, but the wording in the abstract and in the discussion overstates what the theorem proves.","section":"Section 4.3, Theorem 4.12 and discussion"}],"minor_comments":[{"comment":"The experiments tune the threshold τ_t manually rather than using the theoretical value τ_t = 6√2 ζ_t(δ) specified in Algorithm 1. This is a sensible practical choice, but it should be stated explicitly in the main text as an implementation detail, not described only in the appendix.","section":"Section 5 and Appendix G"},{"comment":"The step-size parameter η appears in slightly different algebraic forms in Theorem 4.2 and in Lemma C.1 in Appendix C. If this is not a typographical artifact, the two statements should be harmonized and the proof of Lemma C.1 should be checked against the exact value used in the theorem.","section":"Theorem 4.2 and Lemma C.1"},{"comment":"Lemma 4.11 is stated in the main text as informal, and the formal version correctly relies on Theorem 3.1 of Lee et al. (2024b). Please make the dependence on that external result explicit at the point where the confidence radius is defined in the main text, rather than only in the appendix.","section":"Appendix F"}],"recommendation":"major_revision","confidential_remarks":"The main theorem statements with explicit additive terms appear defensible and the technical machinery is interesting. The problem is the asymptotic simplification: it is not just a presentation issue, because the advertised B-free, K-free result is not a consequence of the stated bounds without an additional condition on the reward variance. This can be repaired by restating the corollaries with honest conditions and de-emphasizing the 'B,K-free' headline, but as written the abstract overclaims what is proven. The paper fits the journal's scope and the underlying work is worth publishing after such a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the core technical work is real and the main proofs hold up on inspection, but the abstract and Section 4.2 oversell the B-free claim. The explicit regret bound in Theorem 4.5 is new and useful; the simplification to O(d log T sqrt(sum sigma_t^2)) is not a consequence of the stated large-T condition unless the cumulative variance is large enough.\n\nWhat is genuinely new: the l-infinity-norm self-concordance (Prop B.3), the Ville-inequality bound on the loss gap (Lemma C.2), and the covariance-based regret decomposition in Appendix D. These go beyond Lee & Oh 2024 and Zhang & Sugiyama, and the improved confidence bound in Theorem 4.2 is a real step forward. The warm-up / restricted-space idea is clever and the constant per-round cost is attractive.\n\nWhere the soft spots are: the stress-test concern is correct. Dropping the (1/kappa) terms requires sqrt(sum sigma_t^2) >= (1/kappa) B^3 d log T, and the stated threshold T >= ~O(e^{B^2} + B^8 d^2/kappa^2) does not give that. For low-variance instances the additive terms dominate, so 'B-free and K-free' is not established. The threshold is also doubly exponential in B and K, which makes the advertised regime essentially unreachable in finite horizons. This is not a load-bearing flaw in Theorem 4.5 as stated — that bound is still a valid contribution — but the marketing in the abstract overstates what is proven. Lemma D.6 is a two-sentence proof; it is correct in spirit but needs a real argument. The experiments tune tau_t without reporting the values, which is a reproducibility gap. The MLE-based bound imports Theorem 3.1 from Lee et al. (2024b); I have not verified that result, so the OFU-M2NL claim is conditional on it.\n\nWho this is for: bandit theorists, especially people working on MNL/logistic models. The techniques will likely be reused. I would send this to a serious referee. The referee should ask the authors to either prove the variance condition or soften the abstract, and to expand Lemma D.6 and report the tuned constants.","headline":"Real technical advances in MNL bandit confidence bounds, but the headline B-free variance-dependent regret is only established under an unstated cumulative-variance condition.","tokens_in":46787,"tokens_out":4273,"would_cite":true,"duration_ms":42390,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that online confidence bounds for multinomial logistic choice models can be made independent of the parameter norm bound B and the maximum assortment size K, and that the resulting bounds yield variance-dependent…","keywords":["multinomial logistic bandits","online confidence bounds","variance-dependent regret","self-concordant functions","Ville's inequality","assortment optimization","online mirror descent","maximum likelihood estimation"],"falsifier":"Track, in a simulation with adversarially correlated contexts, whether the true parameter $w^*$ stays inside the warm-up ellipsoid $W_t^w(\\delta)$ on every round; if the containment frequency drops below $1-\\delta$ or the empirical confidence radius exceeds $\\beta_t(\\delta)$, the constant-$\\alpha$ condition that sustains the $O(\\sqrt{d\\log t})$ radius has failed, and the regret bound reverts to the $B$-dependent warm-up radius.","tokens_in":45633,"feed_emoji":"🛒","tokens_out":9171,"duration_ms":85285,"temperature":0.7,"pith_summary":"The paper sets out to prove that the confidence radius for online estimation in multinomial logistic (MNL) choice models can be reduced from $O(B\\sqrt{d}\\log t\\log K)$ to $O(\\sqrt{d\\log t}+B\\sqrt{d})$, and eventually to $O(\\sqrt{d\\log t})$ at large horizons, with no dependence on the norm bound $B$ or the maximum assortment size $K$. It claims this tighter radius, enforced by updating the parameter only inside a shrinking ellipsoid, is enough to give contextual MNL bandits their first variance-dependent regret bounds: $O(d\\log T\\sqrt{\\sum_{t=1}^T\\sigma_t^2})$ for a constant-time algorithm (OFU-MNL++) when $T$ is large, and $O(d\\log(BT)\\sqrt{\\sum_{t=1}^T\\sigma_t^2})$ for an MLE-based algorithm (OFU-M2NL) at every horizon. If these claims hold, assortment-selection systems would stop paying penalties that grow exponentially in the parameter scale or linearly in assortment size, and their regret would adapt to how noisy observed rewards are rather than scaling with worst-case $T$. The technical engine is a self-concordant-like bound on the MNL loss in the $\\ell^\\infty$ norm plus a martingale argument that replaces a smoothing step costing $\\log K$.","feed_headline":"Multinomial-logit bandits get B- and K-free confidence bounds","feed_subtitle":"A sharper online confidence radius yields regret that scales with reward variance, not worst-case horizon.","key_machinery":"The machinery has three load-bearing pieces. First, the paper proves the MNL loss is $3\\sqrt{2}$-self-concordant-like in the $\\ell^\\infty$ norm, meaning third derivatives of the loss along a direction are controlled by the Hessian times the $\\ell^\\infty$ norm of the direction; this lets the online step size $\\eta$ depend on the update-condition constant $\\alpha$ rather than on $B$ and $\\log K$. Second, it forms a supermartingale $A_t=\\exp(\\sum_s(\\ell_s(w^*)-\\bar\\ell_s(\\tilde z_s)))$ over an intermediary softmax parameter $\\tilde z_s$, so Ville's inequality bounds the loss-gap term by $\\log(1/\\delta)$ instead of the $O(\\log K(\\log t)^2)$ incurred by the smoothed Bernstein argument. Third, the adaptive warm-up phase builds an ellipsoid $W_t^w(\\delta)$ around an auxiliary online estimate and refuses to plan on any context whose $H_w$-weighted norm is large, keeping $\\alpha=1/(3\\sqrt{2})$ during planning; the subsequent regret proof decomposes the per-round regret into a covariance between rewards and the $H_t^{-1}$ norm of context vectors and applies an elliptical-potential bound to that covariance.","core_discovery":"The central claim is Theorem 4.2: when the online mirror-descent update is restricted to a set where the deviation $|x_{ti}^\\top(w-w^*)|$ is at most $\\alpha$, the estimation error satisfies $\\|w_t-w^*\\|_{H_t}=O(\\alpha\\sqrt{d\\log(t/\\delta)}+B\\sqrt{\\lambda})$ with high probability. Taking $\\alpha$ constant (via the warm-up ellipsoid) and $\\lambda=144d$ turns this into $O(\\sqrt{d\\log t}+B\\sqrt{d})$, and for $t\\ge e^{B^2}$ the $B\\sqrt{d}$ term is absorbed. From this the paper derives, under uniform and non-uniform rewards, regret bounds proportional to $\\sqrt{\\sum_t \\sigma_t^2}$, the square root of cumulative reward variance, where earlier bounds scaled as $B^{3/2}d\\log K(\\log T)^{3/2}\\sqrt{T}$.","pith_inferences":["Beyond the paper, the same $\\ell^\\infty$-self-concordance route should transfer to other softmax-parameterized losses, such as top-$k$ or hierarchical softmax, where the number of categories enters only through a log factor that the Ville-inequality step would remove.","Beyond the paper, the empirical tuning of $\\tau_t$ in the experiments suggests the theoretical warm-up threshold is conservative; an adaptive threshold that lowers $\\tau$ once the elliptical potential stabilizes could shorten the $e^{B^2}$ burn-in without sacrificing the $B$-free radius.","Beyond the paper, the variance-dependent form of the bound suggests a practical diagnostic: in settings where observed reward variance is low, the planning-phase updates dominate and the algorithm should approach its asymptotic regret quickly; logging per-round $\\sigma_t^2$ alongside regret would test this directly."],"forward_implications":["If Theorem 4.5 is correct, then for horizons $T\\ge \\tilde O(e^{B^2}+B^8d^2/\\kappa^2)$ the OFU-MNL++ algorithm achieves regret $O(d\\log T\\sqrt{\\sum_{t=1}^T\\sigma_t^2})$ with per-round computational cost $O(Kd^3+\\mathrm{poly}(N))$, independent of $t$.","If Theorem 4.12 is correct, OFU-M2NL achieves $O(d\\log(BT)\\sqrt{\\sum_{t=1}^T\\sigma_t^2})$ regret for every $T$, with no $B$ or $K$ factor in the leading term, at the price of per-round cost that grows linearly with $t$.","Under uniform rewards ($r_{ti}=1$), Proposition 4.10 gives instance-dependent regret $\\tilde O(d\\sqrt{\\sum_t \\kappa_t^*})$, improving the earlier $e^B$ factor.","In the worst case over rewards, $\\sigma_t\\le 1$ makes the OFU-MNL++ bound $\\tilde O(d\\sqrt{T})$, matching the $\\Omega(d\\sqrt{T})$ minimax lower bound from the paper."],"supporting_citations":[{"why":"Establishes the previous online confidence bound $O(B\\sqrt{d}\\log t\\log K)$ and the minimax-optimal OFU-MNL+ regret that this paper improves.","marker":"(Lee & Oh, 2024)"},{"why":"Provides the online mirror descent framework and constant-cost update rule that the paper's estimator extends.","marker":"(Zhang & Sugiyama, 2024)"},{"why":"Source of the self-concordant-like property that the paper tightens from $\\ell^2$ to $\\ell^\\infty$ norm.","marker":"(Tran-Dinh et al., 2015)"},{"why":"Supplies the supermartingale inequality used to bound the loss-gap term by $\\log(1/\\delta)$ instead of $O(\\log K\\log^2 t)$.","marker":"(Ville, 1939)"},{"why":"Smoothing technique whose logarithmic-in-$K$ looseness the paper avoids by applying Ville's inequality directly.","marker":"(Foster et al., 2018)"},{"why":"Provides the unified MLE confidence sequence for generalized linear models that OFU-M2NL adapts to MNL rewards.","marker":"(Lee et al., 2024b)"},{"why":"Prior adaptive-warm-up algorithm for logistic bandits whose $B$-dependence and $\\kappa$ knowledge the paper's OFU-MNL++ removes.","marker":"(Faury et al., 2022)"}],"fun_headline_variants":["Variance-dependent regret for multinomial logit bandits","B- and K-free confidence bounds for MNL bandits","Sharper confidence bounds shrink MNL bandit regret","MNL bandits: regret scales with reward variance, not T"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole improvement rests on the true parameter $w^*$ remaining inside the warm-up confidence ellipsoid at every round; if that containment ever fails, the update-condition constant $\\alpha$ can no longer be held small, and the confidence radius reverts to the $B$-dependent warm-up scale.","fun_headline_variants_meta":{"raw":{"variants":["Variance-dependent regret for multinomial logit bandits","B- and K-free confidence bounds for MNL bandits","Sharper confidence bounds shrink MNL bandit regret","MNL bandits: regret scales with reward variance, not T"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000622,"raw_usage":{"total_tokens":2944,"prompt_tokens":1069,"completion_tokens":1875,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":685,"completion_tokens_details":{"reasoning_tokens":1806}},"tokens_in":685,"tokens_out":1875,"duration_ms":13176,"temperature":1.0,"reasoning_tokens":1806,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T19:41:17.983778+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Track, in a simulation with adversarially correlated contexts, whether the true parameter $w^*$ stays inside the warm-up ellipsoid $W_t^w(\\delta)$ on every round; if the containment frequency drops below $1-\\delta$ or the empirical confidence radius exceeds $\\beta_t(\\delta)$, the constant-$\\alpha$ condition that sustains the $O(\\sqrt{d\\log t})$ radius has failed, and the regret bound reverts to the $B$-dependent warm-up radius.","supporting_citations":[{"cited_title":"Etude critique de la notion de collectif, volume 3","cited_arxiv_id":null,"evidence_quote":"Supplies the supermartingale inequality used to bound the loss-gap term by $\\log(1/\\delta)$ instead of $O(\\log K\\log^2 t)$."},{"cited_title":"J., Kale, S., Luo, H., Mohri, M., and Sridharan, K","cited_arxiv_id":null,"evidence_quote":"Smoothing technique whose logarithmic-in-$K$ looseness the paper avoids by applying Ville's inequality directly."}],"review_version":1}