Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Generalized Linear Bandits with Limited Adaptivity
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.
Gives two limited-adaptivity algorithms for generalized linear contextual bandits (batched B-GLinCB under M1, rarely-switching RS-GLinCB under M2) whose leading regret terms are independent of the non-linearity parameter kappa.
Problem
Generalized linear contextual bandits under limited policy-update budgets: M1 (decide M update rounds upfront) and M2 (adaptively decide up to M updates), where prior regret bounds depend linearly on the instance non-linearity parameter kappa.
Approach
Uses a scaled design matrix (weighted by the link derivative at a warm-up estimate) together with distributional optimal design and a kappa-dependent batch schedule for M1, and a context-dependent switching criterion plus determinant-doubling on the scaled Hessian for M2, removing kappa from the leading regret term.</put_text>
Key results
- RS-GLinCB shows the smallest regret against ECOLog and GLOC in simulated logistic bandits (d=5, K=20, T=20,000).
- RS-GLinCB outperforms GLOC and GLM-UCB in simulated probit bandits (T=5,000).
- For low kappa, RS-GLinCB takes about one-fifth of ECOLog's execution time; for probit, under half of GLOC's time at low kappa.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RS-GLinCB instead of ECOLog | Logistic bandits · Logistic bandits | regret | Helped |
| Use RS-GLinCB instead of GLOC and GLM-UCB | Probit bandits · Probit bandits | regret | Helped |
| Use RS-GLinCB instead of ECOLog | Logistic bandits, execution time · Logistic bandits, low and high κ | execution time: about one-fifth of the time; slightly more than one-third | Helped |
| Use RS-GLinCB instead of GLOC | Probit bandits, execution time · Probit bandits, low and high κ | execution time: less than half time; about two-third time | Helped |
| Add the context-dependent Switching Criterion I (ablation) | RS-GLinCB · Generalized linear contextual bandits, M2 | regret | Helped |
| Use the scaled design matrix in Switching Criterion II instead of the unscaled matrix (ablation) | RS-GLinCB · Generalized linear contextual bandits, M2 | regret | Helped |
| Add the context-dependent switching criterion (ablation) | RS-GLinCB · Generalized linear contextual bandits, M2 | κ-dependence of regret: linear dependence on κ | Helped |
| Use κ-dependent first-batch length construction (ablation) | B-GLinCB · Generalized linear contextual bandits, M1 | κ-dependence of the leading regret term | Helped |
| Scale the arm set before applying distributional optimal design (ablation) | B-GLinCB · Generalized linear contextual bandits, M1 | regret | Helped |
Surprising findings
- The paper claims a counterexample to a kappa-independent regret claim for all bounded GLMs in prior work.
Limitations
- Per-round complexity can reach O(T) for B-GLinCB and RS-GLinCB, unlike ECOLog.
- Regret dependence on d and kappa-avg is not tight.
- Projection step for MLE is non-convex; a convex relaxation gives slightly worse guarantees.
Experimental setup
Benchmarks: simulated logistic bandit simulated probit bandit
Metrics: cumulative regret execution time
Baselines: ECOLog GLOC GLM-UCB
Builds on: distributional optimal design determinant-doubling switching GLM-UCB ECOLog GLOC
Closest papers by meaning
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.92)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.90)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.90)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.90)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.90)
- Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints (ICML 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.