Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator

Abstract

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 $\epsilon$-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.

References in corpus (5)

• Prioritized Experience Replay
• End-to-End Training of Deep Visuomotor Policies
• CVXPY: A Python-Embedded Modeling Language for Convex Optimization
• On the Sample Complexity of the Linear Quadratic Regulator
• Nonparametric risk bounds for time-series forecasting

Cited by in corpus (11)

• Simple random search provides a competitive approach to reinforcement learning
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• Simple Regret Minimization for Contextual Bandits
• On the Utility of Model Learning in HRI
• Combining Model-Based and Model-Free Methods for Nonlinear Control: A Provably Convergent Policy Gradient Approach
• Natural Actor-Critic Converges Globally for Hierarchical Linear Quadratic Regulator
• Structured Control Nets for Deep Reinforcement Learning
• Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems
• System Identification via Meta-Learning in Linear Time-Varying Environments
• Continuous Control with Contexts, Provably
• Alice's Adventures in the Markovian World