# Does Sparsity Help in Learning Misspecified Linear Bandits?

arXiv: https://arxiv.org/abs/2303.16998 · HTML: https://mlsanity.com/paper/2303.16998/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 56 references that are in the map.
- First posted on arXiv 29 Mar 2023.

## Builds on (most cited first, 28 of 28)

- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Doubly robust off-policy evaluation with shrinkage](https://mlsanity.com/paper/1907.09623/) (2019)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration](https://mlsanity.com/paper/2008.07737/) (2020)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling](https://mlsanity.com/paper/2006.04012/) (2020)
- [Online Sparse Reinforcement Learning](https://mlsanity.com/paper/2011.04018/) (2020)
- [Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient](https://mlsanity.com/paper/2011.04019/) (2020)
- [Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis](https://mlsanity.com/paper/2002.11332/) (2020)
- [Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systems](https://mlsanity.com/paper/1303.5984/) (2013)
- [Regularized Off-Policy TD-Learning](https://mlsanity.com/paper/2006.05314/) (2020)
- [Improved Algorithms for Misspecified Linear Markov Decision Processes](https://mlsanity.com/paper/2109.05546/) (2021)

## Built on by (most cited first, 3 of 3)

- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)
- [Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error](https://mlsanity.com/paper/2407.13622/) (2024)
- [Sharper Guarantees for Misspecified Kernelized Bandit Optimization](https://mlsanity.com/paper/2605.05967/) (2026)

## Abstract (arXiv)

Recently, the study of linear misspecified bandits has generated intriguing implications of the hardness of learning in bandits and reinforcement learning (RL). In particular, Du et al. (2020) show that even if a learner is given linear features in ℝd that approximate the rewards in a bandit or RL with a uniform error of varepsilon, searching for an O(varepsilon)-optimal action requires pulling at least Omega(exp(d)) queries. Furthermore, Lattimore et al. (2020) show that a degraded O(varepsilon√d)-optimal solution can be learned within operatornamepoly(d/varepsilon) queries. Yet it is unknown whether a structural assumption on the ground-truth parameter, such as sparsity, could break the varepsilon√d barrier. In this paper, we address this question by showing that algorithms can obtain O(varepsilon)-optimal actions by querying O(varepsilon-sds) actions, where s is the sparsity parameter, removing the exp(d)-dependence. We then establish information-theoretical lower bounds, i.e., Omega(exp(s)), to show that our upper bound on sample complexity is nearly tight if one demands an error  O(sδvarepsilon) for 0<δ<1. For δ≥ 1, we further show that operatornamepoly(s/varepsilon) queries are possible when the linear features are "good" and even in general settings. These results provide a nearly complete picture of how sparsity can help in misspecified bandit learning and provide a deeper understanding of when linear features are "useful" for bandit and reinforcement learning with misspecification.