Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities
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.
Proposes a UCB-based, computationally tractable algorithm for MNL contextual bandits with general non-linear (e.g., neural network) utilities, achieving Õ(√T) regret under realizability and a generalized geometric condition, without NTK assumptions.
Problem
MNL contextual bandit assortment selection where item utilities are non-linear parametric functions (e.g., neural networks); prior general-utility methods are either computationally intractable or achieve suboptimal regret (T^{2/3}, T^{5/6}).
Approach
Two-phase method: uniform exploration gives a pilot estimate; then regularized MLE on a linearized MNL model (first-order Taylor around past estimates) with regularization centered at the pilot yields optimistic utility estimates and a UCB assortment choice; a generalized geometric condition (growth or local strong convexity over an equivalence set of parameters) replaces unique-minimum and NTK as
Key results
- Theory: regret Õ(κ^{-3/2} d_w √T + κ^{-2} μ^{-1} d_w √T) with probability at least 1-2δ, independent of the number of items N.
- Experiments: in realizable and misspecified settings, the proposed method achieves lower cumulative regret than linear MNL baselines (UCB-MNL, TS-MNL, OFU-MNL+), whose regret grows steadily under non-linear utilities.
- Varying N in {100, 800} at T=500: epsilon-greedy-MNL regret grows with N, while the proposed method's Phase II slope stays stable, with its increase attributed to Phase I exploration.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ONL-MNL instead of $\varepsilon$-greedy for general utilities | MNL contextual bandits with stochastic contexts · MNL contextual bandits, stochastic contexts | regret bound: $\tilde{\Ocal}((d_w N K)^{1/3} T^{2/3})$ -> $\tilde{\Ocal}(\kappa^{-2} \mu^{-1} d_w \sqrt{T})$ | Helped |
| Use ONL-MNL instead of $\varepsilon$-greedy for general utilities | MNL contextual bandits with adversarial contexts · MNL contextual bandits, adversarial contexts | regret bound: $\tilde{\Ocal}((N K)^{1/3} T^{5/6})$ -> $\tilde{\Ocal}(\kappa^{-2} \mu^{-1} d_w \sqrt{T})$ | Helped |
| Use a non-linear utility model instead of linear utility models | UCB-MNL, TS-MNL, and OFU-MNL+ · Non-linear utility experiments | cumulative regret | Helped |
| Use ONL-MNL instead of $\varepsilon$-greedy-MNL | MNL contextual bandits with non-linear utilities · Realizable and misspecified settings | cumulative regret | Helped |
| Increase the number of items | ONL-MNL · Realizable setting, Gaussian and uniform contexts | cumulative regret | Hurt |
| Increase the number of items | $\varepsilon$-greedy-MNL · Realizable setting, Gaussian and uniform contexts | cumulative regret | Hurt |
Limitations
- Regret depends on problem-dependent instance factor kappa, which can scale as O(K^2) worst case and exponentially in utility range.
- Requires realizability of the function class and a geometric condition on the squared loss; Phase I requires i.i.d. contexts.
- Experiments are small synthetic settings (N=100, K=5, d=3) with two-layer networks, not large-scale real data.
Experimental setup
Benchmarks: simulated MNL bandit realizable setting simulated MNL bandit misspecified setting (cos-based utility)
Metrics: cumulative regret (mean and std over 30 seeds)
Baselines: UCB-MNL TS-MNL OFU-MNL+ epsilon-greedy-MNL
Builds on: Zhang & Luo 2024 general-utility MNL bandits linear MNL UCB bandits Feel-Good Thompson sampling
Closest papers by meaning
- Contextual Multinomial Logit Bandits with General Value Functions (NeurIPS 2024 · similarity 0.95)
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.93)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.88)
- Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.88)
- Catoni Contextual Bandits are Robust to Heavy-tailed Rewards (ICML 2025 · similarity 0.88)
- Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.88)
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.