English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recently, the study of linear misspecified bandits has generated intriguingimplications of the hardness of learning in bandits and reinforcement learning(RL). In particular, Du et al. (2020) show that even if a learner is givenlinear features in $\mathbb{R}^d$ that approximate the rewards in a bandit orRL 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\sqrt{d})$-optimal solution can be learned within$\operatorname{poly}(d/\varepsilon)$ queries. Yet it is unknown whether astructural assumption on the ground-truth parameter, such as sparsity, couldbreak the $\varepsilon\sqrt{d}$ barrier. In this paper, we address thisquestion by showing that algorithms can obtain $O(\varepsilon)$-optimal actionsby querying $O(\varepsilon^{-s}d^s)$ actions, where $s$ is the sparsityparameter, removing the $\exp(d)$-dependence. We then establishinformation-theoretical lower bounds, i.e., $\Omega(\exp(s))$, to show that ourupper bound on sample complexity is nearly tight if one demands an error $O(s^{\delta}\varepsilon)$ for $0<\delta<1$. For $\delta\geq 1$, we further showthat $\operatorname{poly}(s/\varepsilon)$ queries are possible when the linearfeatures are "good" and even in general settings. These results provide anearly complete picture of how sparsity can help in misspecified banditlearning and provide a deeper understanding of when linear features are"useful" for bandit and reinforcement learning with misspecification.

Does Sparsity Help in Learning Misspecified Linear Bandits?