Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update
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 GLB-OMD, a generalized linear bandit algorithm using one-pass online mirror descent with a mix-loss-based confidence set, achieving near-optimal regret O(log T sqrt(T/κ*)) with O(1) per-round time and memory.
Problem
Generalized linear bandits need both low per-round computation/memory and statistically efficient (kappa-free) regret; MLE-based methods are costly while one-pass methods incur a linear dependence on the link-function constant kappa.
Approach
Uses an online mirror descent (one-pass, second-order-approximated loss) estimator and builds an ellipsoidal confidence set via a mix-loss analysis with time-varying Gaussian mixtures centered at OMD iterates, via Ville's inequality, yielding kappa-free radius and O(1) per-round cost.
Key results
- Regret bound O(log T sqrt(T/κ*)) with O(1) time and memory per round, matching MLE-based dependence on T, κ, d up to non-leading terms.
- On Poisson bandits with S=7 (κ≈882), the method reduces OFUGLB's computational cost by roughly 1000x with a modest regret increase.
- On logistic bandits, the method achieves regret comparable to ECOLog and RS-GLinCB with constant per-round cost, while OFUGLB has lowest regret but highest cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GLB-OMD's one-pass OMD estimator and mix-loss confidence set instead of GLM-UCB | GLB bandit methods · GLBs | regret guarantee: $\O(\kappa (\log T)^{\frac{3}{2}} \sqrt{T})$ -> $\O(\log T \sqrt{T/\kappa_*})$ | Helped |
| Use a one-pass OMD estimator rather than MLE | GLB bandit methods · GLBs | time per round: $\O(t)$ -> $\O(1)$ | Helped |
| Use a one-pass OMD estimator rather than MLE | GLB bandit methods · GLBs | memory per round: $\O(t)$ -> $\O(1)$ | Helped |
| Use GLB-OMD instead of OFUGLB | logistic bandits · logistic bandits | regret | Hurt |
| Use GLB-OMD instead of OFUGLB | logistic bandits · logistic bandits | running time | Helped |
| Use GLB-OMD instead of ECOLog and RS-GLinCB | logistic bandits · logistic bandits | regret | Helped |
| Use GLB-OMD instead of ECOLog and RS-GLinCB | logistic bandits · logistic bandits | running time | Helped |
| Use GLB-OMD instead of OFUGLB | Poisson bandits · Poisson bandits | running time: roughly 1000 times | Helped |
| Use GLB-OMD instead of OFUGLB | Poisson bandits · Poisson bandits | regret | Hurt |
Surprising findings
- Authors identify potential technical issues in a concurrent MNL bandit paper's analysis, relying on a normalization condition unlikely to hold in general.
Limitations
- Retains S^2 dependence in the leading term due to one-pass updates, unlike MLE-based methods.
- Non-leading term scales with kappa rather than the geometry-aware kappa_X; warm-up needed to improve.
- Relies on self-concordance assumption and bounded rewards for some baselines.
Experimental setup
Datasets: Covertype
Benchmarks: logistic bandit simulation Poisson bandit simulation Covertype
Metrics: cumulative regret running time
Baselines: GLM-UCB GLOC OFUGLB RS-GLinCB OFULog-r ECOLog
Builds on: GLM-UCB OFUGLB ECOLog Ville's inequality
Closest papers by meaning
- Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions (ICLR 2026 · similarity 0.93)
- Scalable Generalized Linear Bandits: Online Computation and Hashing (NeurIPS 2017 · similarity 0.92)
- Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.92)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.90)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.89)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.89)
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.