Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Improved Online Confidence Bounds for Multinomial Logistic Bandits
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 sharper K-free online confidence bound for MNL models via ℓ∞ self-concordant-like properties and Ville's inequality, and uses it to build a constant-time, B-improved, variance-dependent regret algorithm (plus an MLE-based poly(B)-free variant) for contextual MNL bandits.
Problem
Online parameter estimation and regret minimization in contextual multinomial logistic (MNL) bandits, where existing confidence bounds and regret depend polynomially on the parameter norm bound B and on the maximum assortment size K, and no variance-dependent regret was known.
Approach
Establish an ℓ∞-norm self-concordant-like property of the MNL loss (constant 3√2 rather than B/log K-dependent), use a constant step size η≈α, and apply Ville's inequality without smoothing to get an online confidence bound O(√(d log t)+B√d) under an update-condition parameter α; combine with an adaptive warm-up that keeps α constant to get a constant-time algorithm with variance-dependent regret.
Key results
- Online confidence bound improves from O(B√d log t log K) to O(√(d log t)+B√d) when the update condition parameter α is constant.
- Constant-time algorithm (ada-style warm-up) achieves variance-dependent regret O((d log T + Bd√log T) √(Σσ_t²)), and O(d log T √(Σσ_t²)) asymptotically, free of B and K.
- MLE-based variant achieves anytime poly(B)-free regret O(d log(BT) √(Σσ_t²)) at per-round cost growing linearly in t.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AlgName with adaptive warm-up and restricted-space online updates instead of OFU-MNL+ | Contextual MNL bandits · Contextual MNL bandits | regret: \BigO \Big( B^{3/2} d \log K (\log T)^{3/2} \sqrt{T} \Big) -> \BigO \Big( \left(d \log T + Bd \sqrt{ \log T} \right) \sq | Helped |
| Use variance-dependent regret in place of a worst-case \sqrt{T} term | AlgName · Contextual MNL bandits | regret: \BigOTilde(\sqrt{T}) -> \BigOTilde \Big( \sqrt{ \sum_{t=1}^T \sigma_t^2 } \Big) | Helped |
| Use the MLE-based algorithm for a poly(B)-free regret bound at every round | Contextual MNL bandits · Contextual MNL bandits | regret: d \log (B T) \sqrt{ \sum_{t=1}^T \sigma_t^2 } + \frac{1}{\kappa} d^2 \left(\log (B T)\right)^2 | Helped |
| Use MLE-based updates rather than online updates | AlgNameMLE · Contextual MNL bandits | computation per round: \BigO(1) -> \BigO(t) | Hurt |
| Apply Ville’s inequality without smoothing to bound the intermediary loss term | MNL online parameter estimation · MNL online parameter estimation | intermediary loss-term bound: \BigO\left( (\log t)^2 \log K \right) -> \BigO(\log t) | Helped |
| Use the \ell_\infty-norm self-concordant property for the MNL loss | MNL online parameter estimation · MNL online parameter estimation | self-concordance constant: 3\sqrt{2} | Helped |
| Replace OFU-MNL+ with AlgNameMLE | Contextual MNL bandits · Numerical experiments, cumulative regret | cumulative regret | Helped |
| Use online updates rather than MLE-based parameter estimation | AlgName · Numerical experiments, runtime per round | runtime per round | Helped |
Limitations
- Asymptotic B-freeness requires T large (T ≥ Õ(e^{B²} + B⁸d²/κ²)); the non-leading term still depends on B.
- Constant-time algorithm depends on problem constant 1/κ = O(K² e^{3B}) in lower-order terms.
- Requires known bound B on the parameter norm; experiments only on simulated data.
Experimental setup
Benchmarks: simulated contextual MNL bandit instances (T=3000, 20 independent instances)
Metrics: cumulative regret runtime per round
Baselines: UCB-MNL TS-MNL OFU-MNL+ MLE-UCB OFU-MNL OFULog
Builds on: Lee & Oh (2024) online confidence bound for MNL bandits OFU-MNL+ MLE-based GLM confidence bounds Ville's inequality
Closest papers by meaning
- Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits (ICML 2021 · similarity 0.92)
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.90)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.89)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.89)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.88)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · 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.