Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator

1 Introduction

• LQR is a useful RL benchmark because it combines theoretical tractability with practical engineering applications, while model-free methods are often preferred for flexibility and ease of use.Prior work by Dean et al. [11] takes a model-based approach, estimating unknown state-transition matrices to design a stabilizing controller.Source: §1 · p. 1
• Ignoring instance-specific factors, roughly n^2/ε^2 samples suffice for LSTD to estimate a stabilizing policy’s value function within ε-relative error.The analysis bounds the minimum eigenvalue of the sample covariance of transformed states, extending a small-ball technique to fast-mixing dependent covariates.Source: §1 · p. 2
• On certain LQR instances, model-free LSPI is substantially less sample efficient and less robust than model-based methods.The comparison corroborates a state-dimension gap between value-function estimation and bounds for robustly computing a stabilizing controller.Source: §1 · p. 2

1.1 Related Work

• This is the first finite-time analysis of temporal-difference learning on LQR; in the bounded setting, its covariance result reduces the required trajectory length from Ω(d^2) to Ω(d).Earlier non-asymptotic analyses commonly assumed uniformly bounded features and rewards, excluding LQR; prior LQR policy-iteration results were asymptotic.Source: §1.1 · p. 2

2 A Sample Covariance Bound for Fast-Mixing Processes

• The theorem’s process assumption allows exponentially decaying β-mixing, and the authors note the analysis can also accommodate slower decay such as polynomial rates.The stated process condition includes β(k) ≤ Γρ^k for Γ > 0 and ρ in (0, 1).Source: §2 · p. 3
• The section generalizes Koltchinskii and Mendelson’s result to fast-mixing processes, without optimizing the resulting constants.The proof uses small-ball probabilities and partitions the dependent sample path into blocks to control the empirical process.Source: §2 · pp. 3, 6
• A corollary replaces the small-ball condition with a stronger moment-contractivity assumption.The text states that the corollary follows a similar line of reasoning; its application invokes the theorem’s conditions.Source: §2 · p. 7

3 Fast-Mixing of Linear Dynamical Systems

• For stable LTI dynamics, the section develops a bound on the β-mixing coefficient to enable application of the preceding fast-mixing results.The setup uses an n-dimensional system with independent noise across timesteps; stability means the spectral radius of A is below one.Source: §3 · p. 7
• A stable linear system has a stationary Gaussian distribution N(0, P∞), with covariance P∞ determined by a discrete-time Lyapunov equation.The marginal state distribution is Gaussian as well, with covariance evolving according to the system dynamics.Source: §3 · pp. 7–8
• The section characterizes geometric decay of powers of a stable matrix using its stability radius and the H∞ norm of its resolvent.The resulting decay bound is used with a bound on transition-to-stationary total-variation distance to control mixing.Source: §3 · pp. 8–9

4.1 Bounded features and rewards

• The covariance-eigenvalue analysis extends a fast-mixing-process result and relaxes the trajectory-length condition under a contractivity condition for the stationary distribution.The authors note that they did not optimize the result’s constants.Source: §4.1 · p. 12
• In the bounded-feature and bounded-reward setting, the trajectory-length requirement improves from eΩ(d^2) to eΩ(d) over the prior bound.The section treats this separately from LQR, which relaxes the boundedness assumptions.Source: §4 · p. 11, §4.1 · p. 12

4.2 Linear Quadratic Regulator

• For LQR, the analysis assumes a stabilizing linear policy; this makes the dynamics mix and the value function finite, while the case where only √γL is stable is not handled.The value function uses quadratic features φ(x) = svec(xx^T + ηI), with lifted feature dimension d = n(n + 1)/2.Source: §4.2 · p. 12
• The LQR analysis gives a sufficient trajectory-length condition for the LSTD estimate of a fixed policy’s value function to have relative error below ε.The bound concerns the difference between the estimated and true value-function matrices.Source: §4.2 · pp. 12–13
• The sample requirement increases with κ(P∞), the condition number of the closed-loop controllability gramian; simulations are reported to exhibit this predicted trend.The paper gives the example of a diagonal closed-loop matrix, where increasing a mode toward one raises the predicted sample requirement.Source: §4.2 · p. 13
• Ignoring instance-specific factors, the bounds suggest eΩ(n^2/ε^2) samples for one value function versus at most eΩ(n/ε^2) for model-based controller design; lower bounds separating the methods remain future work.The authors report empirical evidence that LSPI can be less sample efficient than model-based methods on certain LQR instances.Source: §4.2 · pp. 13–14

5 Experiments

• The experiments include LSTD value-function estimation and an end-to-end LSPI comparison with model-based methods; synthetic runs use 100 trajectories of length 1,000.For each trajectory, the LSTD estimate is computed on prefixes of 100 through 1,000 points.Source: §5 · p. 19, §5.1 · p. 20

5.1 Synthetic Data

• As ρ rises toward one, the first synthetic experiment increases κ(P∞), and the trajectory length needed for ε-relative error increases as predicted.It uses A = B = I5 and varies K so the closed-loop response is diag(ρ, ρ, ..., 0.01).Source: Figure 1 · p. 20, §5.1 · p. 20
• In the second synthetic experiment, increasing κ(P∞) also increases the trajectory length required, though Theorem 4.3 appears conservative about the scaling.The selected instances have κ ≈ 7, κ ≈ 35, and κ ≈ 7 × 10^5 for ρ = 0.1, 0.5, and 0.9, respectively.Source: Figure 2 · p. 20, §5.1 · p. 20

5.2 Least-Squares Policy Iteration

• The LSPI comparison uses an initialized stable controller because the trivial zero controller does not induce a finite Q-function; model-based baselines include nominal and common Lyapunov controllers.The common Lyapunov procedure supplies a stability certificate when its program succeeds, while its robustness guarantee can trade off with performance.Source: §5.2 · p. 22
• At 3,000 timesteps, discounted LSPI is less stable than nominal at 250; its relative error is comparable, and average-cost LSPI needs over 10× samples to reach 10^-1.For average cost, the nominal and common Lyapunov controllers with actual error bounds perform best; the 2×-bound common Lyapunov controller performs slightly worse.Source: Figure 3 · p. 23, Figure 4 · p. 23, §5.2 · p. 23

• On certain LQR instances, LSPI requires substantially more samples than Dean et al.'s model-based methods.The authors note that this empirical comparison corroborates a state-dimension gap between fixed-policy value estimation and robust stabilizing-controller computation.Source: §6 · p. 23
• The paper provides a sample-complexity bound for fixed-policy LSTD value estimation and a covariance-eigenvalue concentration result for trajectories of beta-mixing processes.Source: §6 · p. 23

End-to-end guarantees

• The analysis bounds value estimation for a fixed policy, but how to iterate it and the sample count for policy iteration to reach near-optimal reward remain open.Source: §6 · pp. 23–24

• Figures 5 and 6 compare controller stability frequency and relative error for LSPI, nominal synthesis, and common Lyapunov procedures.Figure 5's stability criterion is necessary and sufficient for finite average infinite-horizon cost; Figure 6 marks medians and interquartile ranges across 100 trials.Source: Figure 5 · p. 24, Figure 6 · p. 24

Lower bounds

• The bound's sharpness, algorithmic lower bounds for LSTD, and information-theoretic sample lower bounds for LQR remain unresolved.Numerical experiments suggest the bound's qualitative behavior, but do not rigorously confirm it.Source: §6 · p. 24

Other model-free RL estimators

• The sample complexity of policy-gradient methods such as TRPO relative to LSPI and Dean et al.'s model-based methods is an open question.Source: §6 · p. 24

• For x ∼ N(0, I) and symmetric A and B, the fourth-moment expression is Tr(A) Tr(B) + 2 Tr(AB).The appendix presents this as an elementary claim and provides a proof.Source: A Gaussian Moment Lemmas · pp. 27–28
• The proof computes moments for fixed vectors u and v, then uses eigen-decompositions of A and B to obtain the matrix expression.Source: A Gaussian Moment Lemmas · pp. 27–28
• The appendix also states a Gaussian hypercontractivity result for degree-d polynomials with x ∼ N(0, I) and q > 2.Source: A Gaussian Moment Lemmas · p. 28

• Following Lazaric et al., the proof organizes trajectory data into feature, next-feature, and reward matrices for the LSTD analysis.Source: B Proof of Lemma 4.4 · pp. 28–29
• With ψ(x) defined as the expected next feature under the policy, LSTD chooses bw to satisfy its sample equation using the reward vector R.Under the linear-architecture assumption, Bellman's equation implies the stated relation.Source: B Proof of Lemma 4.4 · pp. 28–29
• The projected empirical Bellman operator is contractive because the empirical transition is non-expansive and the orthogonal projection is non-expansive in the ℓ2 norm.Source: B Proof of Lemma 4.4 · p. 29
• The contraction gives the operator a unique fixed point, and the LSTD estimator solves the corresponding fixed-point equation under the stated full-column-rank condition.Source: B Proof of Lemma 4.4 · p. 29
• Proposition B.3 bounds feature-space estimation error by a projected residual; the proof combines additional inequalities to obtain Lemma 4.4.Source: B Proof of Lemma 4.4 · pp. 30–31