PaperlayerView exact revision on arXiv

Source-linked AI summary

The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint

Stephen Tu, Benjamin Recht

arXiv:1812.03565v2cs.LGmath.OCstat.ML

TL;DR

The paper asks whether model-based methods are more sample efficient than model-free methods for continuous-control reinforcement learning. Using asymptotic analyses of policy evaluation and optimization on LQR, it finds strict sample-complexity advantages for simple model-based methods, including under common policy-gradient baselines.

  • Problem

    The paper studies the lack of general theory rigorously explaining the performance gap between model-based and model-free reinforcement-learning methods.

  • Method

    The paper compares asymptotic LQR performance using empirical-dynamics plugin methods, LSTD, nominal control, and policy gradients with different baselines.

  • Results

    The model-based methods are asymptotically more sample efficient: the policy-evaluation gap can reach a factor of state dimension, while policy optimization shows several factors of state and input dimension depending on the baseline.

  • Takeaways & Limitations

    The results provide a rigorous continuous-control setting with a strict sample-complexity separation favoring model-based methods on the studied LQR instances.

  • Takeaways & Limitations

    The policy-gradient result uses a specific step-size choice, and extending it to Polyak-Ruppert averaging is left for future work.

Abstract

from arXiv · show

The effectiveness of model-based versus model-free methods is a long-standing question in reinforcement learning (RL). Motivated by recent empirical success of RL on continuous control tasks, we study the sample complexity of popular model-based and model-free algorithms on the Linear Quadratic Regulator (LQR). We show that for policy evaluation, a simple model-based plugin method requires asymptotically less samples than the classical least-squares temporal difference (LSTD) estimator to reach the same quality of solution; the sample complexity gap between the two methods can be at least a factor of state dimension. For policy evaluation, we study a simple family of problem instances and show that nominal (certainty equivalence principle) control also requires several factors of state and input dimension fewer samples than the policy gradient method to reach the same level of control performance on these instances. Furthermore, the gap persists even when employing commonly used baselines. To the best of our knowledge, this is the first theoretical result which demonstrates a separation in the sample complexity between model-based and model-free methods on a continuous control task.

1 Introduction

This paper develops a theoretical comparison of model-based and model-free methods for continuous control, using LQR to study policy evaluation and optimization. It finds asymptotic sample-efficiency advantages for simple model-based methods over classical model-free estimators in both settings.

  • The paper addresses the longstanding debate over the relative merits of model-based and model-free reinforcement-learning methods.Existing theory does not yet rigorously explain their performance gap.
  • It studies asymptotic performance on LQR through policy evaluation and policy optimization.The comparison uses empirical transition data to fit dynamics models, temporal-difference learning, and policy-gradient methods.
  • The model-based plugin estimator is always asymptotically more sample efficient than LSTD for policy evaluation.The gap can be at least a factor of state dimension.
  • Nominal control is at least several factors of state and input dimension more efficient than policy gradients on a family of policy-optimization instances.This gap persists when commonly used variance-reduction baselines are applied.
  • The analysis provides minimax lower bounds and identifies a strict sample-complexity separation between model-based and model-free methods on the same continuous-control task.The authors present this as the first rigorous result of this kind.

2 Main Results

The paper compares model-based and model-free algorithms for LQR policy evaluation and optimization using asymptotic risk and sample-complexity analyses. Across the studied settings, model-based methods are more sample efficient, with optimality established for their dimension dependence in the considered families.

  • Policy evaluation and optimization: The study compares model-based plugin estimators with LSTD for policy evaluation and with policy gradient methods for policy optimization on LQR.Policy evaluation uses a fitted closed-loop dynamics model, while policy optimization fits system dynamics and solves an infinite-horizon control problem.
  • Policy Evaluation: Theorem 2.2 shows that the model-free policy-evaluation method always has greater asymptotic risk than the model-based plugin method.The comparison is proved even when the model-free method receives the true infinite-horizon cost, an idealized choice that reduces its risk variance.
  • Policy Evaluation: The plugin risk is a factor of state dimension n smaller than the LSTD risk on the family F(ρ, d).The corresponding LSTD non-asymptotic bound scales as eO(n^3/T), matching the asymptotic dependence up to logarithmic factors.
  • Policy Evaluation: The model-based policy-evaluation rate is unimprovable beyond constant factors, with optimal dependence on state dimension n and stability radius ρ over F(ρ, d).This is established through a minimax lower bound for any estimator in the considered family.
  • Policy Optimization: For policy optimization, model-free policy gradient has higher risk than model-based control under simple, value-function, and advantage baselines.The advantage baseline is closest, differing by one factor of input dimension d, while the other baselines incur additional factors of n and the horizon T.
  • Policy Optimization: The model-based policy-optimization method is asymptotically dimension-optimal over G(ρ, d), matching the lower bound Ω(nd/N).The information-theoretic lower bound applies to possibly adaptive feedback methods in the specified oracle model.

3 Related Work

Prior LQR theory includes model-based and model-free analyses, but explicit comparisons remain incomplete, especially for model-free policy optimization and problem-parameter dependence. Existing results largely provide upper bounds, leaving lower-bound comparisons open.

  • General MDP context: For general MDPs, model-free regret can be worse than model-based regret in horizon dependence, although no state-action gap is known in the cited tabular results.The literature leaves open whether the horizon gap is fundamental.
  • Model-based and model-free LQR: Model-based LQR methods estimate transition matrices before addressing control, while model-free methods directly optimize value functions or policies.Known analyses distinguish offline from online methods and compare storage, regret, and sample-complexity behavior.
  • Model-based methods: Existing model-based LQR work studies discounted or average-cost problems using model estimation and robust-control tools.These results quantify how model uncertainty affects control performance.
  • Model-free methods: LSTD has non-asymptotic risk analyses for discounted and average-cost LQR, while policy-gradient bounds are difficult to compare because problem-parameter dependence is not explicit.Prior policy-gradient work also studies different noise and horizon settings from this paper.
  • Open gap: For LQR, prior results are mainly upper bounds, and explicit lower bounds with problem-instance dependence remain unavailable.The paper positions its asymptotic comparison as addressing this gap.

4 Proof Sketch

The proofs derive asymptotic distributions for model-based estimators, LSTD, and policy-gradient procedures, then convert those distributions into risk statements. The policy-gradient analysis additionally handles projected stochastic optimization and baseline-dependent variance.

  • Model-based policy evaluation: Model-based policy evaluation combines a Markov-chain central limit theorem, the delta method, and uniform integrability to derive plugin-estimator risk.The map from dynamics to the Lyapunov solution is differentiated, and scaled risk converges to a covariance-trace expression.
  • Model-free policy evaluation: LSTD risk follows from directly computing the limiting distribution of its scaled estimation error and lower-bounding scaled risk by the limiting covariance trace.Unlike the plugin analysis, this argument does not require establishing uniform integrability.
  • Model-based policy optimization: Model-based policy optimization differentiates the Riccati solution with respect to model parameters and applies a second-order delta method to control-cost excess.Uniform integrability is again used to connect the limiting distribution to asymptotic risk.
  • Model-free policy optimization: Policy-gradient analysis proves restricted strong convexity, derives a projected-SGD limiting distribution, and computes variance for alternative gradient estimators and baselines.The selected problem family makes the otherwise difficult variance calculations tractable.

5 Conclusion

The paper finds an asymptotic sample-efficiency advantage for model-based plugin estimators over model-free methods in both LQR policy evaluation and selected policy-optimization instances. It also identifies broader analyses of policy gradients, baselines, and online learning as future directions.

  • Main findings: A simple plugin estimator is always asymptotically more sample efficient than classical LSTD for LQR policy evaluation.The conclusion compares the asymptotic performance of model-based and model-free methods on LQR.
  • Main findings: In a family of policy-optimization instances, the plugin estimator is asymptotically at least a state-dimension factor more efficient than policy gradient, depending on the baseline.The policy-gradient method is guaranteed to converge to the optimum on these instances.
  • Future directions: Future work includes broader policy-gradient instance families, more analysis of baseline estimators, and extension to online learning.The paper connects these directions to convergence conditions, baseline efficiency, and exploration comparisons.

A Asymptotic Toolbox

The asymptotic toolbox establishes convergence and distributional results for stable linear systems, least-squares estimators, LSTD, and projected stochastic optimization. These results support the paper’s later risk analyses, while some bounds retain sub-optimal horizon dependence.

  • Stable linear systems: Stability makes the linear-system state process geometrically ergodic, enabling standard limit theorems for Markov chains.The toolbox repeatedly uses stationary distributions and Markov-chain central limit arguments.
  • Least-squares estimation: Least-squares estimators for stable autonomous and controlled systems converge almost surely to their true dynamics parameters.The results cover both single-trajectory and multiple-independent-trajectory settings.
  • LSTD: The LSTD asymptotic analysis assumes a stable closed-loop system and defines stationary feature moments needed for its limiting distribution.The toolbox also specifies the true infinite-horizon cost setting used in the LSTD result.
  • Risk conversion: Convergence in distribution is converted into convergence of risk using nonnegative continuous functions and suitable uniform moment bounds.Uniform integrability supplies the expectation-convergence step.
  • Technical limitation: The least-squares concentration argument has sub-optimal dependence on rollout horizon T, although this is sufficient when T is treated as fixed and only the number of rollouts grows.A more careful combination of within-trajectory and across-trajectory concentration could improve the dependence.
  • Projected stochastic optimization: Projected stochastic-gradient results require restricted strong convexity, a stochastic gradient oracle, and an interior optimum.These conditions support the asymptotic analysis used for policy-gradient methods.

B.1 Proof of Theorem 2.1

The proof combines asymptotic normality for the estimated closed-loop matrix with the delta method for the Lyapunov solution. Stability perturbation bounds and uniform integrability then convert asymptotic calculations into the stated risk bound.

  • Asymptotic transfer: The delta method transfers the asymptotic distribution of the regularized least-squares estimator bL(T) to P(bL(T)) through the differentiable Lyapunov map.The proof represents the resulting fluctuation using the Fréchet derivative of P.
  • Stability control: Lemma B.1 ensures that sufficiently small perturbations preserve stability and yield the bound ∥(A + ∆)k∥≤Cγk.The proof derives stability from the corresponding uniform power bound and the spectral-radius inequality.
  • High-probability event: On the high-probability event EBdd, the estimator remains close enough to L⋆ for the stability perturbation argument and the algorithmic bounds to apply.The event has probability at least 1 −δT, with δT = O(1/T^(p/2)).
  • Uniform integrability: The proof combines bounds on EBdd and its complement to establish uniform integrability of the scaled Lyapunov error.This condition completes the passage from the asymptotic distribution to moment and risk statements.
  • Risk bound: The resulting moment bound is E[∥bPplug(T) −P⋆∥p] ≤O(1/T^(p/2)).The proof obtains this after controlling the estimator on the bounded and complementary events.

B.2 Proof of Theorem 2.2

The proof derives the asymptotic risk bound by combining auxiliary lemmas with the risk bound established for the plugin estimator.

  • Lemma A.3 combined with Lemma A.5 supplies the intermediate asymptotic relation used in the proof.
  • The proof’s final step is therefore an application of the previously established plugin-estimator result.
  • Theorem 2.1’s risk bound then yields the claim for Theorem 2.2.

B.3 Proof of Theorem 2.3

The proof constructs many stable LQR instances using separated subspaces and applies information-theoretic reasoning to obtain a lower bound. It also analyzes the optimal cost landscape used in the control comparison.

  • Hard-instance construction: The hard-instance family sets Ai = τPEi + γIn for separated d-dimensional subspaces, with τ + γ = ρ ensuring contractivity and stability.The subspaces satisfy a Frobenius separation condition and can be chosen in exponentially many ways.
  • Lower-bound argument: Choosing d = n/4 and applying Fano’s inequality yields the stated information-theoretic lower bound.The construction first selects τ so that the mutual-information condition is controlled.
  • Control setup: For the control analysis, the state evolves under xt+1 = A⋆xt + B⋆ut + wt with feedback ut = Kxt and Gaussian process noise.The induced cost is expressed through powers of the closed-loop matrix L(K) = A⋆ + B⋆K.
  • Optimal controller: The optimal controller is K⋆= −B†⋆A⋆ under the stated range condition.The range condition permits the corresponding representation of A⋆.
  • Cost geometry: JΣ(K) is not convex but satisfies quadratic growth and restricted strong convexity around the unique stationary point K⋆.The restricted strong-convexity constant is m = 2(T −1)λmin(Σ)σmin(B⋆)^2.
  • Cost geometry: The gradient and Hessian calculations establish positive curvature at K⋆ and support the local control-performance analysis.

C.2 Proof of Theorem 2.4

The proof establishes regularity of the Riccati solution and controller map, then controls policy-gradient fluctuations and estimation errors through Taylor expansions, concentration, and uniform integrability.

  • Riccati regularity: Under stabilizability and full column rank, the DARE has a unique positive definite solution with bounds P ⪰Q and, for contractive A, ∥P∥≤∥Q∥/(1−∥A∥^2).These properties provide uniform control of Riccati solutions over the parameter set.
  • Derivative analysis: The Riccati solution and optimal-policy maps are differentiated by the implicit function theorem and the chain rule.At the target instance, the derivative of the Riccati solution vanishes because the closed-loop matrix is zero.
  • Asymptotic cost: The second-order delta method relates the asymptotic behavior of the estimated controller to the excess-cost expansion around K⋆.The Hessian at K⋆ supplies the quadratic term in this expansion.
  • Error control: On the bounded estimation event, Taylor expansion bounds excess cost by powers of the errors in bA(N) and bB(N).The resulting bound is N^p E[(J(bK(N)) −J⋆)^p1EBdd] ≤ C N^p(E[∥bA(N) −A⋆∥^(2p)] + E[∥bB(N) −B⋆∥^(2p)]).
  • Final asymptotic step: The proof combines event-wise bounds to establish uniform integrability, after which the asymptotic bound follows.The same analysis includes simple and value-function baselines in the policy-gradient variance calculation.
  • Policy-gradient analysis: The policy-gradient analysis verifies smoothness and restricted strong convexity on a compact policy domain, then applies Gaussian concentration.The gradient’s derivative has polynomial dependence on the noise and uniformly bounded coefficients over the domain.

D.4 Proof of Corollary A.4

The proof computes Gaussian quadratic-form expectations to characterize A∞ and B∞, then establishes invertibility and derives a lower bound using matrix inequalities.

  • Matrix properties: A∞ is invertible because it is expressed as the product of two invertible matrices.
  • Expectation calculations: Gaussian quadratic-form expansions compute the expectations needed to characterize A∞ and B∞.The proof invokes Magnus’s formula for products of three Gaussian quadratic forms and decomposes the estimation error into T1, T2, and T3.
  • Lower bound: The lower-bound argument applies a lemma for positive-semidefinite and symmetric matrices, using Young’s inequality and Cauchy-Schwarz.The proof conditions on x, iterates expectations, and uses the resulting trace inequalities.
  • Lower bound: The proof specializes the decomposition of B∞ with m = n, using nonnegativity of the T2 term and vanishing of the T3 term.The vanishing follows because the relevant expression contains odd powers of w.
  • Conclusion: The proof completes the formulas for A∞ and B∞ after applying the lower bound for arbitrary test vectors.

D.5 Proof of Lemma A.6

The proof bounds regularized least-squares quantities through singular-value inequalities, concentration, and moment estimates, then selects δ to control the resulting error term.

  • Matrix bound: On the event that XᵀX is invertible, the proof uses the compact SVD of X to analyze the regularized matrix expression.
  • Matrix bound: Regularization is controlled by the Loewner inequality (XᵀX + λI_n)^−2 ⪯ (XᵀX)^−2.The inequality is transferred through conjugation by M = WᵀX.
  • Concentration: A high-probability event from Simchowitz et al. supplies the concentration bound used for the remainder of the proof.The event has probability at least 1 − δ when T ≥ C L⋆,n log(1/δ).
  • Moment bound: The p-th moment is bounded by decomposing on the concentration event and applying (a + b)^p ≤ 2^(p−1)(a^p + b^p).A crude bound on ||WᵀX||^(2p) follows from Hölder’s inequality.
  • Rate choice: Choosing δ = O(1/T^(3p)) makes the relevant term O(1/T^(p/2)) for sufficiently large T.

E Proof of Lemma A.8

The proof analyzes projected SGD by separating projection effects from unconstrained dynamics, controlling covariance terms, and applying Taylor expansions to establish asymptotic behavior.

  • SGD control: The proof uses a high-probability SGD bound adapted from Rakhlin et al. because gradients are not almost surely bounded.
  • Projection: Projection effects are isolated by comparing θ_t with its unprojected iterate, using that θ⋆ lies in the interior of Θ.When the unprojected iterate remains within a radius R of θ⋆, the projection step is inactive.
  • Variance decomposition: The covariance recursion decomposes the variance into unprojected variance, projection variance, and two cross-covariance terms.
  • Asymptotic control: Projection-related variance and covariance terms decay as O(exp(−tα)), while E[||θ_t − θ⋆||²] is bounded by O(1/t).
  • Limit argument: Taylor expansions around θ⋆ and a bias-variance decomposition control higher-order terms and identify the limiting second-moment expression.The proof uses covariance identities and bounds the cubic remainder before taking limits.
  • Limit argument: The resulting matrix recursion is solved using Corollary C.1 of Toulis and Airoldi.
Loading 1812.03565v2…