Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator
Stephen Tu and Benjamin Recht University of California, Berkeley
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 $\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 [19] 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.
中文速览
连续控制中的强化学习到底需要多少样本才够用？研究者以经典的线性二次型调节器（Linear Quadratic Regulator, LQR）为基准，分析了无模型方法里广泛使用的最小二乘时间差分（Least-Squares Temporal Difference, LSTD）估计器的样本复杂度，给出了首个有限时间（非渐近）保证：在状态维度为 n 的系统中，大约需要 n²/ε² 条样本才能把值函数估计到 ε 相对误差以内。为了推导这一结果，作者还将 Koltchinskii 和 Mendelson 关于独立样本协方差矩阵最小特征值的经典结论推广到了快速混合的相关数据场景，并在有界协变量条件下将所需轨迹长度从 Ω(d²) 改进到 Ω(d)。实验对比进一步表明，无模型的最小二乘策略迭代（LSPI）在样本效率和鲁棒性上明显逊于基于模型的方法，这与理论预测的状态维度量级差距相吻合，为理解连续控制场景下强化学习的根本统计瓶颈提供了重要依据。
原文 arXiv:1712.08642;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1712.08642v1