Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator
Reinforcement learning (RL) has been successfully used to solve many continuous control tasks. Despite its impressive results however, fundamental questions regarding the sample complexity of RL on continuous problems remain open. We study the performance of RL in this setting by considering the behavior of the Least-Squares Temporal Difference (LSTD) estimator on the classic Linear Quadratic Regulator (LQR) problem from optimal control. We give the first finite-time analysis of the number of samples needed to estimate the value function for a fixed static state-feedback policy to within $\varepsilon$-relative error. In the process of deriving our result, we give a general characterization for when the minimum eigenvalue of the empirical covariance matrix formed along the sample path of a fast-mixing stochastic process concentrates above zero, extending a result by Koltchinskii and Mendelson in the independent covariates setting. Finally, we provide experimental evidence indicating that our analysis correctly captures the qualitative behavior of LSTD on several LQR instances.
Code (0)
등록된 구현이 없습니다.
Tasks
continuous-controlContinuous ControlReinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Accelerated Gradient Temporal Difference Learning
The family of temporal difference (TD) methods span a spectrum from computationally frugal linear methods like TD({\lambda}) to data efficient least squares methods. Least square methods make the best use of available da…
Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guarantees
We propose a single time-scale actor-critic algorithm to solve the linear quadratic regulator (LQR) problem. A least squares temporal difference (LSTD) method is applied to the critic and a natural policy gradient method…
Bilevel OptimizationA Convergent O(n) Temporal-difference Algorithm for Off-policy Learning with Linear Function Approximation
We introduce the first temporal-difference learning algorithm that is stable with linear function approximation and off-policy training, for any finite Markov decision process, target policy, and exciting behavior policy…
Supplementary material for Uncorrected least-squares temporal difference with lambda-return
Here, we provide a supplementary material for Takayuki Osogami, "Uncorrected least-squares temporal difference with lambda-return," which appears in {\it Proceedings of the 34th AAAI Conference on Artificial Intelligence…
Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform sampling
We propose a stochastic approximation (SA) based method with randomization of samples for policy evaluation using the least squares temporal difference (LSTD) algorithm. Our proposed scheme is equivalent to running regul…
Multi-Armed BanditsNews RecommendationregressionTraffic Signal Control