Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910533860458496 |
|---|---|
| author | Du, Ally Yalei Yang, Lin F. Wang, Ruosong |
| author_facet | Du, Ally Yalei Yang, Lin F. Wang, Ruosong |
| contents | The recent work by Dong & Yang (2023) showed for misspecified sparse linear bandits, one can obtain an $O\left(ε\right)$-optimal policy using a polynomial number of samples when the sparsity is a constant, where $ε$ is the misspecification error. This result is in sharp contrast to misspecified linear bandits without sparsity, which require an exponential number of samples to get the same guarantee. In order to study whether the analog result is possible in the reinforcement learning setting, we consider the following problem: assuming the optimal $Q$-function is a $d$-dimensional linear function with sparsity $k$ and misspecification error $ε$, whether we can obtain an $O\left(ε\right)$-optimal policy using number of samples polynomially in the feature dimension $d$. We first demonstrate why the standard approach based on Bellman backup or the existing optimistic value function elimination approach such as OLIVE (Jiang et al., 2017) achieves suboptimal guarantees for this problem. We then design a novel elimination-based algorithm to show one can obtain an $O\left(Hε\right)$-optimal policy with sample complexity polynomially in the feature dimension $d$ and planning horizon $H$. Lastly, we complement our upper bound with an $\widetildeΩ\left(Hε\right)$ suboptimality lower bound, giving a complete picture of this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_13622 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error Du, Ally Yalei Yang, Lin F. Wang, Ruosong Machine Learning Artificial Intelligence The recent work by Dong & Yang (2023) showed for misspecified sparse linear bandits, one can obtain an $O\left(ε\right)$-optimal policy using a polynomial number of samples when the sparsity is a constant, where $ε$ is the misspecification error. This result is in sharp contrast to misspecified linear bandits without sparsity, which require an exponential number of samples to get the same guarantee. In order to study whether the analog result is possible in the reinforcement learning setting, we consider the following problem: assuming the optimal $Q$-function is a $d$-dimensional linear function with sparsity $k$ and misspecification error $ε$, whether we can obtain an $O\left(ε\right)$-optimal policy using number of samples polynomially in the feature dimension $d$. We first demonstrate why the standard approach based on Bellman backup or the existing optimistic value function elimination approach such as OLIVE (Jiang et al., 2017) achieves suboptimal guarantees for this problem. We then design a novel elimination-based algorithm to show one can obtain an $O\left(Hε\right)$-optimal policy with sample complexity polynomially in the feature dimension $d$ and planning horizon $H$. Lastly, we complement our upper bound with an $\widetildeΩ\left(Hε\right)$ suboptimality lower bound, giving a complete picture of this problem. |
| title | Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2407.13622 |