Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator
This work addresses fundamental open questions about sample efficiency in RL for continuous control, offering theoretical insights that are incremental but specific to the LQR domain.
The paper tackles the sample complexity of reinforcement learning in continuous control by analyzing the Least-Squares Temporal Difference (LSTD) estimator on the Linear Quadratic Regulator (LQR) problem, providing the first finite-time analysis to estimate the value function within ε-relative error with a specified number of samples.
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.