Research map / Bandits and online learning / Contextual bandits and Thompson sampling
A Unified Confidence Sequence for Generalized Linear Models, with Applications to 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.
Derives a unified likelihood-ratio confidence sequence for convex GLMs via time-uniform PAC-Bayes with uniform prior/posterior, and uses it in OFUGLB, an optimistic bandit algorithm with poly(S)-free regret for logistic bandits.
Problem
Confidence sequences for generalized linear models are loose (often poly(S) or exponential-in-S radius, esp. Bernoulli), and optimistic GLM bandit regret analyses carry poly(S) factors in the leading term.
Approach
Derive a likelihood-ratio CS for any convex GLM using a time-uniform PAC-Bayes bound with a uniform prior over Theta and a uniform posterior over a shrunk set around the constrained MLE, plus a new regret proof that avoids the self-concordance control lemma.
Key results
- Proposed OFUGLB has a poly(S)-free radius for Bernoulli CS, improving on the prior S log(1/delta) radius (theory).
- On simulated logistic bandits, OFUGLB and EMK match or beat EVILL with heuristic hyperparameters and outperform the other baselines for S in {8,10}.
- RS-GLinCB with its theoretical hyperparameters performs worst, even below ada-OFU-ECOLog, in the experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the unified likelihood ratio-based confidence sequence instead of the prior state-of-the-art likelihood ratio-based Bernoulli confidence sequence | Bernoulli GLMs · Bernoulli GLMs | confidence-sequence radius: \mathcal{O}\left( S \log(1 / \delta) + d \log (St / d) \right) -> \mathcal{O}\left(\log(1 / \delta) + d \log (St / d)\ri | Helped |
| Apply OFUGLB instead of RS-GLinCB | R-bounded GLB · R-bounded GLB | regret bound: d^2 R^5 S^2 κ_X(T) -> d^2 R R_{\dot{\mu}} κ(T) | Mixed |
| Apply OFUGLB instead of the prior state-of-the-art algorithm | Logistic bandits · Logistic bandits | regret bound: d^2 S^2 \kappa_\gX(T) -> d^2 \kappa(T) | Helped |
| Apply OFUGLB instead of the prior state-of-the-art algorithm | Linear bandits · Linear bandits | regret bound: \sigma d \sqrt{T} -> \sigma d \sqrt{T} | No clear effect |
| Apply OFUGLB instead of the prior state-of-the-art algorithm | Poisson bandits · Poisson bandits | regret bound: d S \sqrt{T / \kappa_\star(T)} + d^2 e^{2S} \kappa(T) | Mixed |
| Use OFUGLB rather than the other considered algorithms | Logistic bandits · Logistic bandits, S ∈ {8, 10} | regret | Helped |
| Use the ellipsoidal confidence sequence (OFUGLB-e) instead of the likelihood ratio confidence sequence (OFUGLB) | OFUGLB · Logistic bandits | regret | Hurt |
| Use OFULog+ instead of OFUGLB-e | Logistic bandits · Logistic bandits | regret | Hurt |
| Use RS-GLinCB with its exact theoretical hyperparameters | RS-GLinCB · Logistic bandits | regret | Hurt |
| Use OFUGLB instead of RS-GLinCB with exact theoretical hyperparameters | Logistic bandits · Logistic bandits | regret | Helped |
Surprising findings
- RS-GLinCB with exact theoretical hyperparameters performs worst, because its theory-based constants are not numerically tight and force exploration throughout.
Limitations
- Likelihood-ratio CS requires computing the Lipschitz constant L_t, which is NP-hard in general; closed-form bounds are used instead.
- OFUGLB requires Omega(T) switches and a convex UCB maximization that is computationally heavy.
- Transient term scales with kappa(T) and is not adaptive to arm-set geometry.
Experimental setup
Benchmarks: simulated logistic bandits (S in {4,6,8,10})
Metrics: cumulative regret confidence set size
Baselines: EMK EVILL RS-GLinCB OFULog+ ada-OFU-ECOLog
Builds on: OFUL Logistic-UCB-2 PAC-Bayes time-uniform bounds Ville's inequality
Closest papers by meaning
- Likelihood Ratio Confidence Sets for Sequential Decision Making (NeurIPS 2023 · similarity 0.90)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.88)
- Improved Online Confidence Bounds for Multinomial Logistic Bandits (ICML 2025 · similarity 0.88)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.87)
- Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits (NeurIPS 2024 · similarity 0.86)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.85)
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.