Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Establishes minimax-optimal regret bounds for contextual MNL bandits (uniform rewards: Ω(√(v0K)/(v0+K)·d√T) lower bound and matching constant-time algorithm UCB-style via online mirror descent; non-uniform: Ω(d√T) lower bound and matching Õ(d√T) upper bound).
Problem
Closing the gap between lower and upper regret bounds for contextual multinomial logit (MNL) bandits with adversarial contexts, dependence on assortment size K, outside-option attraction v0, and reward structure.
Approach
An online mirror descent (single-gradient-step) parameter estimator with a K-free self-concordant-like property of the MNL loss, combined with an optimistic utility that makes assortment selection reduce to top-K sorting under uniform rewards; for non-uniform rewards, centralized features and a new elliptical potential lemma remove 1/κ from the leading term.
Key results
- Under uniform rewards, the proposed algorithm achieves Õ(√(v0K)/(v0+K)·d√T + d²/κ), matching the new lower bound up to log factors (Õ(d√(T/K)) when v0=Θ(1)).
- Under non-uniform rewards, the algorithm achieves Õ(d√T + d²/κ) against a new Ω(d√T) lower bound, establishing minimax optimality up to logs.
- Simulations (T=3000, 20 instances) show the method beats UCB-MNL and TS-MNL and runs at constant per-round cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase assortment size K | AlgName under uniform rewards with v0=Theta(1) · Uniform rewards | cumulative regret: \BigOTilde(d \sqrt{T/K}) | Helped |
| Increase assortment size K | AlgName under non-uniform rewards · Non-uniform rewards | cumulative regret: \BigOTilde(d \sqrt{T}) | No clear effect |
| Use AlgName instead of UCB-MNL or TS-MNL | MNL bandit algorithms · Numerical experiments, uniform and non-uniform rewards | cumulative regret | Helped |
| Increase assortment size K | All evaluated algorithms · Uniform rewards | cumulative regret | Helped |
| Increase assortment size K | Evaluated algorithms · Non-uniform rewards | cumulative regret | No clear effect |
| Use online parameter estimation and the proposed assortment selection | AlgName versus the other evaluated algorithms · Numerical experiments, runtime per round | runtime: \BigO(1) | Helped |
Surprising findings
- Regret upper bound under uniform rewards decreases as assortment size K increases (unless v0=Θ(K)), contrary to prior bounds that did not improve with K.
Limitations
- Instance-dependent bounds are only established under uniform rewards.
- Bounds include a d^2/κ lower-order term that depends on the problem-dependent constant κ = O(1/K^2).
Experimental setup
Benchmarks: simulated contextual MNL bandit environments
Metrics: cumulative regret runtime per round
Baselines: UCB-MNL TS-MNL
Builds on: UCB-MNL online mirror descent self-concordant-like functions logistic bandit (Faury et al.)
Closest papers by meaning
- Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities (NeurIPS 2025 · similarity 0.93)
- Contextual Multinomial Logit Bandits with General Value Functions (NeurIPS 2024 · similarity 0.93)
- Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.91)
- Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions (NeurIPS 2026 · similarity 0.90)
- Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.90)
- Improved Online Confidence Bounds for Multinomial Logistic Bandits (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.