Sample Complexity of the Linear Quadratic Regulator: A Reinforcement Learning Lens
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908409467502592 |
|---|---|
| author | Moghaddam, Amirreza Neshaei Olshevsky, Alex Gharesifard, Bahman |
| author_facet | Moghaddam, Amirreza Neshaei Olshevsky, Alex Gharesifard, Bahman |
| contents | We provide the first known algorithm that provably achieves $\varepsilon$-optimality within $\widetilde{\mathcal{O}}(1/\varepsilon)$ function evaluations for the discounted discrete-time LQR problem with unknown parameters, without relying on two-point gradient estimates. These estimates are known to be unrealistic in many settings, as they depend on using the exact same initialization, which is to be selected randomly, for two different policies. Our results substantially improve upon the existing literature outside the realm of two-point gradient estimates, which either leads to $\widetilde{\mathcal{O}}(1/\varepsilon^2)$ rates or heavily relies on stability assumptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_10851 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sample Complexity of the Linear Quadratic Regulator: A Reinforcement Learning Lens Moghaddam, Amirreza Neshaei Olshevsky, Alex Gharesifard, Bahman Systems and Control Machine Learning Optimization and Control We provide the first known algorithm that provably achieves $\varepsilon$-optimality within $\widetilde{\mathcal{O}}(1/\varepsilon)$ function evaluations for the discounted discrete-time LQR problem with unknown parameters, without relying on two-point gradient estimates. These estimates are known to be unrealistic in many settings, as they depend on using the exact same initialization, which is to be selected randomly, for two different policies. Our results substantially improve upon the existing literature outside the realm of two-point gradient estimates, which either leads to $\widetilde{\mathcal{O}}(1/\varepsilon^2)$ rates or heavily relies on stability assumptions. |
| title | Sample Complexity of the Linear Quadratic Regulator: A Reinforcement Learning Lens |
| topic | Systems and Control Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2404.10851 |