mlsanityData to 7 Oct 2026

Does Sparsity Help in Learning Misspecified Linear Bandits?

arXiv 2303.16998 ↗First posted 29 Mar 2023cs.LG cs.AIcited by 3

Not on the map. Why?

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.

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

Builds on

28 of 56 references.

References · 28

  1. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 698
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  6. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  7. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  8. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  9. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  10. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  11. 2019Doubly robust off-policy evaluation with shrinkagecited by 87
  12. 2021Adapting to Misspecification in Contextual Banditscited by 81
16 more
  1. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  2. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  3. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 63
  4. 2020High-Dimensional Sparse Linear Banditscited by 61
  5. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  6. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  7. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  8. 2019Doubly-Robust Lasso Banditcited by 49
  9. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  10. 2020An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Samplingcited by 30
  11. 2020Online Sparse Reinforcement Learningcited by 25
  12. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
  13. 2020Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysiscited by 15
  14. 2013Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systemscited by 13
  15. 2020Regularized Off-Policy TD-Learningcited by 10
  16. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 0; 2026: 2.

3 papers.

  1. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  2. 2024Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Errorcited by 0
  3. 2026Sharper Guarantees for Misspecified Kernelized Bandit Optimizationcited by 0