Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Sparsity-Agnostic Linear Bandits with Adaptive Adversaries
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 SparseLinUCB and AdaLinUCB, sparsity-agnostic linear bandit algorithms that randomize over nested confidence-set radii (via online-to-confidence-set conversion with SeqSEW) to get Õ(S√(dT)) regret against adaptive adversaries without structural assumptions.
Problem
Sparse stochastic linear bandits with unknown sparsity level S and adaptively adversarial action sets; prior sparsity-agnostic bounds needed nestedness, i.i.d. actions, or other assumptions and none beat OFUL's Õ(d√T).
Approach
Run online-to-confidence-set conversion over a hierarchy of nested confidence sets with radii 2^i log T, randomly choosing the radius index with probability ~2^{-i} so that the safe (sufficiently large) radius is chosen often enough; AdaLinUCB replaces the fixed distribution with Exp3 adaptation plus forced exploration.
Key results
- SparseLinUCB achieves Õ(S√(dT)) regret with no assumptions on sparsity structure or on the (adaptive adversarial) action sets, improving on OFUL's Õ(d√T) when S=o(√d).
- When S is known, the algorithm recovers Õ(√(SdT)) regret, matching the lower bound up to log factors.
- In synthetic experiments, AdaLinUCB (Unif and Theory variants) outperforms OFUL in cumulative regret; SparseLinUCB_Theory is roughly on par with OFUL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a randomized hierarchy of confidence sets instead of a single dimension-wide confidence radius | SparseLinUCB · Adaptive adversarial action sets | expected regret: \widetilde{O}(S\sqrt{dT}) vs. \widetilde{O}\big(d\sqrt{T}\big) | Helped |
| Use Exp3 to adaptively select confidence sets | AdaLinUCB · Synthetic model selection; S=1,2,4,8,16 | cumulative regret | Helped |
| Use the theory-based confidence-set distribution instead of a uniform distribution (ablation) | SparseLinUCB · Synthetic model selection; S=1,2,4,8,16 | cumulative regret | Helped |
| Use the theory-based confidence-set distribution instead of a uniform distribution (ablation) | AdaLinUCB · Synthetic model selection; S=1,2,4,8,16 | cumulative regret | No clear effect |
| Tune the confidence-set index to the known sparsity level (ablation) | SparseLinUCB_Known · Synthetic model selection; S=1,2,4,8,16 | cumulative regret | Helped |
| Use Exp3-based adaptive selection instead of fixed confidence-set probabilities | AdaLinUCB · Stochastic linear bandits | regret | No clear effect |
| Set the confidence-set distribution using known S rather than a sparsity-agnostic distribution (ablation) | SparseLinUCB · Adaptive adversarial action sets; known S | expected regret: \widetilde{O}(S\sqrt{dT}) -> {O}\big(\sqrt{SdT}\log T\big) | Helped |
Surprising findings
- AdaLinUCB's regret bound is no better than SparseLinUCB's, and the paper notes the constant forced exploration probability makes its bound pessimistic despite strong empirics.
- The sparse implementation is not used in experiments: SeqSEW has no efficient implementation, so experiments use X_hat=X and effectively run OFUL instances with different radii.
Limitations
- AdaLinUCB requires bounded noise (in [-1,1]) rather than just subgaussian noise.
- Instance-dependent bound scales as d^2/Delta independent of S, and worst-case bound for sparsity-agnostic case is not tight (sqrt(S) gap to lower bound).
- Experiments do not implement the sparsity-aware SeqSEW; only model-selection effect is tested.
Experimental setup
Datasets: synthetic data
Benchmarks: synthetic linear bandit experiments (d=16, |A|=30, T=10^4, S in {1,2,4,8,16})
Metrics: cumulative regret
Baselines: OFUL SparseLinUCB_Unif SparseLinUCB_Known AdaLinUCB_Unif AdaLinUCB_Theory
Builds on: OFUL SeqSEW Exp3 online to confidence set conversion
Closest papers by meaning
- Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits (NeurIPS 2020 · similarity 0.93)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.93)
- An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction (NeurIPS 2025 · similarity 0.92)
- Hybrid Regret Bounds for Combinatorial Semi-Bandits and Adversarial Linear Bandits (NeurIPS 2021 · similarity 0.92)
- High-Dimensional Sparse Linear Bandits (NeurIPS 2020 · similarity 0.92)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.90)
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.