Research map / Bandits and online learning / RL theory and MDPs
Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error
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.
Studies misspecified Q-learning with k-sparse linear Q* approximation and gives an elimination algorithm achieving O(H·epsilon) suboptimality with poly(d) samples for constant k, plus matching lower bounds.
Problem
Whether an O(epsilon)-optimal policy can be learned with sample complexity polynomial in feature dimension d when Q* is approximated by a k-sparse linear function with misspecification epsilon in RL, where standard Bellman backup and OLIVE-style elimination give suboptimal guarantees.
Approach
A per-level parameter-elimination algorithm that selects, at each level, the parameter maximizing empirical value under the roll-in distribution, and eliminates only the parameters with large empirical Bellman error at that level, avoiding error amplification across levels and yielding O(H*epsilon) suboptimality with near-matching information-theoretic lower bounds.
Key results
- Algorithm returns a policy with suboptimality (2eps + 2eps_net + 4eps_stat)H using O(k d^k H^3 ln(dH/eps_net delta) eps_net^-k eps_stat^-2) samples.
- Without samples, any algorithm suffers Omega(H eps) suboptimality even for d=k=1 deterministic systems.
- With samples, achieving suboptimality H/T*eps requires exp(Omega(T)) samples, making the O(H eps) guarantee tight up to log factors for polynomial sample algorithms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use level-wise elimination with separate parameter sets and select parameters maximizing empirical roll-in value at each level | Misspecified sparse linear Q-learning · Misspecified sparse linear Q-learning, horizon H | policy suboptimality: O(H √d ε) -> (4ε_stat + 2ε_net + 2ε)H | Helped |
| Use the Elimination Algorithm instead of the existing bandit algorithm | Misspecified linear bandit · Misspecified linear bandit, H = 1 | action suboptimality: 4ε + ε_stat -> 2ε + 2ε_net + 4ε_stat | Helped |
| Require uniform reward approximation for all arms within 2ε | Misspecified linear bandit · Misspecified linear bandit with n arms and d = k = 1 | sample complexity: at least 0.9n samples | Hurt |
| Require suboptimality less than H/(2T) · ε | Misspecified sparse linear Q-learning · Misspecified sparse linear Q-learning, d = k = 1 | sample complexity: 0.1 · T · 2^T samples | Hurt |
Surprising findings
- Existing bandit algorithms amplify approximation error by a factor of 2 for a for-all guarantee, and this amplification is information-theoretically unavoidable without sample cost proportional to the action space size.
- Bellman rank of the sparse-linear RL setting can be as large as d for some instances, so the OLIVE bound H*sqrt(M)*eps becomes O(H sqrt(d) eps).
Limitations
- Sample complexity has a polynomial but large dependence on d (d^k) and is not tight in H; the authors note improvement is future work.
- Analysis assumes a deterministic initial state, a feature map with norm at most 1, and sparsity k constant; the algorithm enumerates an epsilon-net and all k-subsets of [d].
Experimental setup
Metrics: suboptimality sample complexity
Baselines: OLIVE Dong and Yang (2023) sparse bandit algorithm Bellman backup
Builds on: OLIVE Dong and Yang (2023) sparse misspecified linear bandit algorithm Bellman rank
Closest papers by meaning
- Does Sparsity Help in Learning Misspecified Linear Bandits? (ICML 2023 · similarity 0.91)
- Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification (NeurIPS 2024 · similarity 0.87)
- Sharper Guarantees for Misspecified Kernelized Bandit Optimization (NeurIPS 2026 · similarity 0.87)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.86)
- Nearly Minimax Optimal Submodular Maximization with Bandit Feedback (NeurIPS 2024 · similarity 0.85)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · 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.