Does Sparsity Help in Learning Misspecified Linear Bandits?
This work addresses a fundamental challenge in bandit and reinforcement learning theory, providing insights into when linear features are useful under misspecification, with implications for algorithm design in high-dimensional settings.
The paper tackles the problem of learning in misspecified linear bandits by investigating whether sparsity assumptions can overcome the known sample complexity barriers, showing that algorithms can achieve O(ε)-optimal actions with O(ε^{-s}d^s) queries, nearly matching lower bounds of Ω(exp(s)).
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 $\mathbb{R}^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 $Ω(\exp(d))$ queries. Furthermore, Lattimore et al. (2020) show that a degraded $O(\varepsilon\sqrt{d})$-optimal solution can be learned within $\operatorname{poly}(d/\varepsilon)$ queries. Yet it is unknown whether a structural assumption on the ground-truth parameter, such as sparsity, could break the $\varepsilon\sqrt{d}$ barrier. In this paper, we address this question by showing that algorithms can obtain $O(\varepsilon)$-optimal actions by querying $O(\varepsilon^{-s}d^s)$ actions, where $s$ is the sparsity parameter, removing the $\exp(d)$-dependence. We then establish information-theoretical lower bounds, i.e., $Ω(\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 $δ\geq 1$, we further show that $\operatorname{poly}(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.