Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Contextual Multinomial Logit Bandits with General Value Functions
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.
Extends contextual multinomial logit (MNL) bandits from (generalized) linear value functions to general value function classes, proposing stochastic and adversarial algorithms whose regret avoids the exponential problem-dependent constant kappa.
Problem
Contextual MNL bandits (assortment recommendation) have only been studied with (generalized) linear value functions, which limits applicability and yields regret bounds with an exponentially large constant kappa in the weight norm B.
Approach
Reduce MNL bandits to offline or online log-loss regression over a general value class; use a log-barrier regularized stochastic policy (low-regret-high-dispersion) for exploration, shown to bound a DEC even in adversarial settings, plus a feel-good Thompson sampling variant. A "reverse Lipschitzness" lemma links log loss to squared value error.
Key results
- Stochastic linear case: regret Otilde((dBNK)^{1/3} T^{2/3}) with uniform exploration and Otilde(K^2 sqrt(dBNT)) with log-barrier strategy, with no dependence on kappa.
- Adversarial linear case: O(K^2 sqrt(NB) T^{3/4}) with no dimension dependence and no kappa dependence, the first results handling fully adversarial contexts and rewards.
- Feel-good Thompson sampling achieves O(K^{2.5} sqrt(dNT log(BT))) with only logarithmic dependence on B, but is computationally inefficient.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace uniform singleton exploration with log-barrier exploration | Contextual MNL bandits with stochastic contexts and rewards · Stochastic contexts and rewards, linear class | regret upper bound: \mathcal{O}\left((dBNK\log K)^{\frac{1}{3}}T^{\frac{2}{3}}\log B\log T\right) -> \mathcal{O}\left(K^2\sqrt{dBNT\log B\lo | Helped |
| replace uniform exploration with log-barrier exploration | Contextual MNL bandits with adversarial contexts and rewards · Adversarial contexts and rewards, linear class | regret upper bound: \mathcal{O}\left((NKB)^{\frac{1}{3}}T^{\frac{5}{6}}\right) -> \mathcal{O}\left(K^2\sqrt{NB}T^{\frac{3}{4}}\right) | Helped |
| use Feel-Good Thompson Sampling instead of online-regression reduction with log-barrier exploration | Contextual MNL bandits with adversarial contexts and rewards · Adversarial contexts and rewards, linear class | regret upper bound: \mathcal{O}\left(K^2\sqrt{NB}T^{\frac{3}{4}}\right) -> \mathcal{O}\left(K^{2.5}\sqrt{dNT\log (BT)}\right) | Helped |
| use Feel-Good Thompson Sampling instead of online-regression reduction with log-barrier exploration | Contextual MNL bandits with adversarial contexts and rewards · Adversarial contexts and rewards, finite class | regret upper bound: \mathcal{O}\Big(K^2\sqrt{N\log\frac{K}{\beta}}T^{\frac{3}{4}}(\log|\calF|)^{\frac{1}{4}}\Big) -> \mathcal{O}\left(K^{2.5 | Helped |
Surprising findings
- The log-barrier regularized strategy designed for the stochastic setting also achieves small DEC in the adversarial setting, despite not being the exact DEC minimizer.
Limitations
- Log-barrier strategy requires solving a concave optimization over subsets, poly(N^K) time, so efficient only for small K.
- Regret for reduction-based adversarial algorithms is T^{3/4} or T^{5/6}, not optimal sqrt(T).
- FGTS sampling from the posterior-like distribution is computationally hard even for linear class.
Experimental setup
Metrics: regret
Baselines: Thompson sampling contextual MNL bandit adversarial contextual MNL bandit with linear value (kappa-dependent)
Builds on: FALCON (offline regression oracle contextual bandits) SquareCB / inverse gap weighting Feel-Good Thompson Sampling Decision-Estimation Coefficient
Closest papers by meaning
- Multinomial Logit Contextual Bandits: Provable Optimality and Practicality (AAAI 2021 · similarity 0.95)
- Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities (NeurIPS 2025 · similarity 0.95)
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.93)
- Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.88)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 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.