Research map / Bandits and online learning / RL theory and MDPs
Does Sparsity Help in Learning Misspecified Linear Bandits?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Parameter elimination over all s-subsets with epsilon-net guessing (query complexity O(eps^{-s} d^s)) | s-sparse epsilon-misspecified linear bandit · theoretical (query complexity) | query complexity for O(eps)-optimal action | Helped |
| G-optimal design based elimination over s-subsets (no epsilon-net guessing) | s-sparse misspecified linear bandit · theoretical (query complexity) | query complexity and error guarantee | Mixed |
| Feature compression via Johnson-Lindenstrauss plus action elimination on benign (good) features | s-sparse misspecified linear bandit with benign features · theoretical (query complexity) | query complexity for O(s eps)-optimal action | Helped |
| Compression plus l0-constrained estimation on general features | s-sparse misspecified linear bandit with general features · theoretical (query complexity) | query complexity and error | Helped |
| Lower bound: sound algorithms with approximation error Delta need exp(Omega(s)) queries when Delta=O(s^delta eps), delta<1 | s-sparse misspecified linear bandit · theoretical (lower bound) | query lower bound | No clear effect |
Closest papers by meaning
- Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error (ICLR 2025 · similarity 0.91)
- Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification (NeurIPS 2024 · similarity 0.90)
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.89)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.88)
- Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.88)
- Testing the Feasibility of Linear Programs with Bandit Feedback (ICML 2024 · similarity 0.87)
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.