Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Lasso Bandit with Compatibility Condition on Optimal Arm
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 FS-WLasso, a forced-sampling then weighted-loss Lasso bandit that achieves poly-log(dT) regret for sparse single-parameter linear contextual bandits using only a compatibility condition on the optimal arm's Gram matrix plus the margin condition.
Problem
Sparse linear contextual bandits in the single-parameter setting need strong diversity assumptions on context distributions (anti-concentration, relaxed symmetry, balanced covariance) to get poly-logarithmic regret in d and T.
Approach
Replace the compatibility condition on the averaged arm plus diversity assumptions with a single compatibility condition on the optimal arm's expected Gram matrix; forced uniform sampling starts a cycle in which good Lasso estimates lead to optimal-arm selection, which in turn keeps estimates good, analysed by an induction argument.
Key results
- FS-WLasso is shown to attain O(s0^2 log(dT) log T) regret under the margin condition with only the optimal-arm compatibility condition.
- In experiments, the proposed algorithms outperform DR Lasso, SA Lasso, TH Lasso, L1-CB-Lasso and ESTC in cumulative regret, including when sub-optimal arm contexts are fixed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FS-WLasso or the adaptive forced-sampling variant instead of the evaluated sparse linear bandit baselines | synthetic sparse linear bandits with correlated Gaussian contexts · correlated Gaussian contexts | cumulative regret | Helped |
| use FS-WLasso or the adaptive forced-sampling variant instead of the evaluated sparse linear bandit baselines | synthetic sparse linear bandits with fixed suboptimal-arm contexts · fixed suboptimal-arm contexts; optimal-arm context is random | cumulative regret | Helped |
Surprising findings
- Even when sub-optimal arm contexts are fixed (so anti-concentration fails), the proposed method still outperforms existing Lasso bandits.
Limitations
- Requires knowledge of sparsity s0 to set the forced-sampling length M0 (a sparsity-agnostic variant is not given for the main theorem).
- Regret bound depends on problem constants such as the compatibility ratio and margin parameters, and forced sampling incurs burn-in regret.
Experimental setup
Datasets: synthetic bandit instances (correlated Gaussian contexts; fixed sub-optimal arm contexts)
Benchmarks: synthetic sparse linear bandit instances
Metrics: cumulative regret (mean and std over 100 runs)
Baselines: DR Lasso Bandit SA Lasso Bandit TH Lasso Bandit L1-CB-Lasso ESTC
Builds on: Lasso Bandit forced sampling SA Lasso Bandit DR Lasso Bandit TH Lasso Bandit ESTC
Closest papers by meaning
- New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem (AAAI 2024 · similarity 0.90)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.89)
- Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.88)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.88)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.88)
- High-dimensional Linear Bandits with Knapsacks (ICML 2024 · 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.