PaperlayerView exact revision on arXiv

Source-linked AI summary

Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator

Maryam Fazel, Rong Ge, Sham M. Kakade, Mehran Mesbahi

arXiv:1801.05039v3cs.LGstat.ML

TL;DR

Direct policy gradients are easy to apply without an explicit model, but their efficiency and convergence are poorly understood even for non-convex LQR optimization. This paper analyzes exact and sample-based policy-gradient methods and proves global convergence to the optimal policy with polynomial computational and sample complexity. It also shows that natural policy gradients have a considerably improved convergence rate over naive gradients.

  • Problem

    Policy gradient methods face a non-convex optimization problem in LQR, while their statistical and computational efficiency has limited theoretical understanding.

  • Method

    The paper analyzes exact gradient descent and model-free policy gradients using simulated trajectories, with zeroth-order optimization providing the bridge from exact to sample-based methods.

  • Results

    The analyzed methods globally converge to the optimal policy with finite polynomial computational and sample complexities.

  • Takeaways & Limitations

    Policy-gradient approaches for LQR receive provable guarantees that place them on a theoretical footing comparable to other principled control methods.

  • Takeaways & Limitations

    The results require the initial policy to be a stable controller, meaning C(K0) is finite, which may be a stronger assumption than in model-based approaches.

Abstract

from arXiv · show

Direct policy gradient methods for reinforcement learning and continuous control problems are a popular approach for a variety of reasons: 1) they are easy to implement without explicit knowledge of the underlying model 2) they are an "end-to-end" approach, directly optimizing the performance metric of interest 3) they inherently allow for richly parameterized policies. A notable drawback is that even in the most basic continuous control problem (that of linear quadratic regulators), these methods must solve a non-convex optimization problem, where little is understood about their efficiency from both computational and statistical perspectives. In contrast, system identification and model based planning in optimal control theory have a much more solid theoretical footing, where much is known with regards to their computational and statistical properties. This work bridges this gap showing that (model free) policy gradient methods globally converge to the optimal solution and are efficient (polynomially so in relevant problem dependent quantities) with regards to their sample and computational complexities.

1 Introduction

Policy gradient methods are popular but theoretically less understood than model-based control approaches. This work studies LQR and establishes global convergence guarantees for exact and model-free policy optimization.

  • Motivation: Policy gradient methods offer model-free, end-to-end optimization but have limited statistical and computational theory.Model-based control instead estimates dynamics and designs controllers with provable guarantees.
  • LQR setting: The paper studies the time-homogeneous, infinite-horizon linear quadratic regulator as a special continuous-control problem.The setting uses linear dynamics, quadratic costs, positive definite Q and R, and random initial states without disturbance noise.
  • Model-based control: For known models, LQR planning can be performed by solving the Algebraic Riccati Equation using iterative or algebraic methods.The Riccati solution parameterizes the cost-to-go and determines the optimal control gain.
  • Contributions: Even though direct policy optimization is non-convex, local search with model-free policy gradients can find an epsilon-close globally optimal policy.The paper separately establishes global convergence for exact gradients and for stochastic gradients estimated from simulated trajectories.
  • Contributions: Natural policy gradients receive a guarantee of a considerably improved convergence rate over naive gradients.The contribution concerns a widely used family that includes related trust-region and natural actor-critic methods.
  • Related work: The work combines optimal control, mathematical optimization, and sample-based reinforcement learning, while model-free theory remains less developed than model-based LQR learning.Related model-based approaches use system identification and robust control synthesis, whereas model-free approaches directly optimize policies or estimate values from simulation.

2 Preliminaries and Background

The paper formulates linear policy optimization for infinite-horizon LQR and develops exact, stochastic, natural-gradient, and zeroth-order perspectives for estimating or improving policies.

  • Policy and cost: A matrix K parameterizes the linear policy that generates controls, and its induced trajectory defines the infinite-horizon cost C(K).The trajectory starts from a random initial state x0 sampled from D, with K* denoting a minimizer of C.
  • Exact gradient descent: Exact gradient descent updates K using a fixed stepsize and the gradient of C(K).The gradient analysis introduces the cost-to-go matrix P_K and the un-normalized state correlation matrix Sigma_K.
  • Exact gradient descent: The policy gradient can be expressed as 2 E_K Sigma_K, linking the optimization direction to the state-correlation matrix.The derivation expands the dependence of future states on K through the closed-loop dynamics.
  • Model-free optimization: Model-free policy gradients estimate gradients from randomized simulated trajectories rather than explicit model knowledge.REINFORCE uses Monte Carlo trajectory estimates under a stochastic policy, while zeroth-order methods use function-value queries and Gaussian smoothing.
  • Natural policy gradient: Natural policy gradients precondition updates with the Fisher information matrix; for linear Gaussian policies, its structure is determined by Sigma_K.The Fisher matrix is block diagonal across action coordinates, with each nonzero block equal to Sigma_K.

3 The (non-convex) Optimization Landscape

The LQR objective is non-convex, yet its gradient domination structure rules out non-optimal full-rank stationary points. Global convergence analysis remains difficult because the objective is not globally smooth, especially near instability boundaries.

  • If d ≥3, some LQR optimization problems are neither convex, quasi-convex, nor star-convex.
  • Two finite-cost policies can have an infinite-cost midpoint, demonstrating that the objective is not generally convex.
  • Gradient domination makes small policy gradients imply near-optimal objective values under the stated full-rank covariance condition.
  • Every stationary point is optimal unless its state covariance ΣK is rank deficient.
  • Classical gradient-descent guarantees do not apply directly because local smoothness is difficult to characterize and global smoothness fails near unstable policies.
  • The analysis uses an almost-smoothness condition away from the stability boundary and controls the covariance change through a Taylor approximation.

4 Main Results

The paper establishes global convergence for exact and model-free policy-gradient methods in the LQR problem, then gives polynomial computational and sample-complexity guarantees for the model-free setting.

  • Exact gradient methods: Exact gradient methods are analyzed first, providing the foundation for extending convergence results to simulation-based, model-free methods.The model-free analysis uses zeroth-order optimization because gradients are unavailable and must be approximated from sampled function values.
  • Exact gradient methods: Gauss–Newton has the strongest convergence-rate guarantee but requires the most complex oracle, while gradient descent has the simplest oracle and slowest rate.Natural policy gradient lies between them in both oracle requirements and convergence rate.
  • Exact gradient methods: Gradient descent, natural policy gradient, and Gauss–Newton methods each have global convergence guarantees under C(K0) finite and µ > 0.The theorem covers the three exact update rules and states method-specific performance bounds.
  • Exact gradient methods: The exact-method results require the initial policy to be stable, meaning C(K0) is finite, which may be a stronger assumption than in model-based approaches.The paper identifies this assumption as a direction for future work.
  • Model-free optimization: In the model-free setting, simulated trajectories and zeroth-order estimates of the gradient and covariance yield globally convergent policy-gradient methods with polynomial computational and sample complexities.Theorem 9 assumes bounded initial-state norm and gives high-probability performance bounds for gradient descent and natural policy gradient.
  • Model-free optimization: The model-free proof controls finite-horizon approximation, estimates gradients and covariance accurately with enough samples, and tolerates bounded estimation perturbations.Algorithm 1 uses randomized policy perturbations, simulated rollouts, and empirical cost and covariance estimates.
  • Model-free optimization: The analysis prioritizes polynomial dependence in complexity bounds rather than optimizing the best dependence on relevant parameters.The proofs are technical and deferred to supplementary material.

5 Conclusions and Discussion

The paper establishes global convergence and polynomial computational and sample complexity for model-based and model-free policy-gradient methods in LQR. It also situates these results within classical LQR solution methods and identifies boundaries for future work.

  • Conclusions: Model-based gradient methods and model-free sample-based policy-gradient methods converge globally to an optimal solution with finite polynomial computational and sample complexities.These results provide theoretical guarantees for both exact and simulated-trajectory settings.
  • Limitations and future work: Future work includes handling finite C(K0) assumptions, reducing sample size through variance reduction, constructing sample-based Gauss–Newton estimators, and proving robustness in model-free settings.The paper notes that finite C(K0) may be difficult in some infinite-horizon problems and that model-free robustness remains open.
  • LQR background: Finite-horizon LQR can be formulated as a linearly constrained quadratic program whose adjoint-system recursion is equivalent to Riccati recursion.The QP is convex, but naive scaling with horizon length is poor.
  • LQR background: Classical LQR solutions include Riccati recursions, algebraic methods, semidefinite programs, and finite-horizon dynamic-programming approaches.The Riccati recursion converges to the unique positive semidefinite solution of the algebraic Riccati equation.
  • Nonconvexity: The stabilizing state-feedback-gain set is generally nonconvex, so averaging two stabilizing gains can produce a gain with unstable closed-loop eigenvalues.This supplies a concrete source of nonconvexity in the policy-optimization problem.
  • Analytical tools: The advantage function measures the cost change from taking a one-step deviation from the current policy, supporting cost-difference and gradient-domination analyses.These lemmas underpin the paper’s convergence arguments.

C.2 Gauss-Newton Analysis

The Gauss–Newton analysis establishes one-step progress under suitable conditions and shows that the chosen update remains stabilizing. With unit stepsize, the convergence proof follows from a contraction argument.

  • Gauss-Newton progress: The Gauss–Newton update is analyzed through a lemma bounding its one-step progress.The proof first assumes the updated policy is stabilizing and then establishes this property for the selected stepsize.
  • Stability: The updated policy remains stabilizing for the permitted stepsizes, established by continuity and a contradiction argument around the stability boundary.A neighborhood of a stabilizing policy is also shown to remain stabilizing.
  • Convergence: With the one-step lemma established, the Gauss–Newton convergence-rate proof follows immediately.The analysis connects the update guarantee directly to the global convergence result.
  • Convergence: For Gauss–Newton, η = 1 yields a contraction factor of 1 − ηµ / ∥ΣK∗∥ at every step.This is the stated contraction underlying the convergence theorem.

C.3 Natural Policy Gradient Descent Analysis

The natural policy-gradient analysis bounds one-step progress under a stepsize restriction and shows that each update remains stabilizing. Induction then completes the convergence-rate argument.

  • Progress bound: The natural policy-gradient analysis begins with a lemma bounding the update’s one-step progress.The proof uses a stepsize condition involving R + B⊤PKB.
  • Stability: The updated policy is shown to remain stabilizing for all selected stepsizes using the same strategy as the gradient-descent analysis.The proof first handles stabilizing updates and then establishes stability for the chosen update.
  • Progress bound: The remaining terms in the natural policy-gradient progress bound are controlled to complete the one-step estimate.This closes the technical lemma needed for the convergence proof.
  • Convergence: Induction applies the one-step bound at every iteration while maintaining C(Kt) ≤ C(K0).The initialization and inductive step both rely on the applicable progress lemma.
  • Convergence: The proof quantifies how ΣK′ changes with η before bounding gradient-descent progress.This covariance dependence is the bridge between the update size and the cost decrease.

ΣK perturbation analysis

The perturbation analysis controls how the covariance operator and covariance matrix change under nearby policy updates. These bounds preserve stability and support the gradient-descent convergence proof.

  • Technical lemmas: The operator analysis relies on technical norm and perturbation lemmas for FK, FK′, TK, and TK′.These lemmas connect policy distance to covariance and stability control.
  • Operator formulation: For a stable closed loop, TK is the inverse of I − FK and maps the initial covariance to the policy covariance ΣK.This operator representation enables perturbation bounds.
  • Covariance perturbations: Perturbation bounds control TK′ − TK when policies are sufficiently close, using induced operator norms and a smallness condition.The key condition is ∥TK∥∥FK − FK′∥ ≤ 1/2.
  • Stability preservation: The analysis shows that sufficiently nearby policies remain stabilizing, completing the covariance perturbation lemma.The argument combines the weaker perturbation result with a separate stability lemma.
  • Covariance growth: tr(ΣK′) ≥ µ / 2(1 − ρ(A − BK′)) for any stabilizing K′, so covariance grows as the spectral radius approaches one.This lower bound helps rule out instability inside the permitted policy neighborhood.
  • Gradient-descent consequence: The perturbation lemmas provide the bounds needed to establish one-step gradient-descent progress.The convergence proof selects a stepsize polynomial in relevant problem-dependent quantities and iterates the resulting decrease.

D Analysis: the Model-free case

The model-free analysis uses zeroth-order optimization to estimate costs, covariances, and gradients from simulator access, while proving stability under policy perturbations. These polynomially controlled approximations support convergence analysis for gradient-based updates.

  • Model-free setting: Zeroth-order optimization enables model-free operation with only black-box simulator access.The parameter dependencies are polynomial in problem-dependent quantities, with dimension and accuracy dependence stated separately.
  • Approximation: With an upper bound on C(K), both C(K) and Σ(K) can be approximated to any desired accuracy.Finite-horizon truncation bounds the approximation error between the infinite-horizon quantities and their truncated counterparts.
  • Perturbation stability: The perturbation proofs use positivity and operator bounds to control covariance and value-function differences.The covariance operator preserves positive semidefiniteness, while matrix differences are bounded using the policy perturbation size.
  • Perturbation stability: Small policy perturbations preserve the objective value and gradient up to polynomially bounded errors.The analysis bounds changes in state covariance, value-function matrices, and gradient terms as functions of ∥K−K′∥.

D.3 Smoothing and the gradient descent analysis

The gradient descent analysis replaces ill-defined Gaussian smoothing with uniform smoothing on a Frobenius-norm sphere and estimates the smoothed gradient from sampled trajectories. Concentration and truncation arguments yield polynomial sample and computational requirements for convergence.

  • Smoothing: Ball-based smoothing avoids the fact that C(K) is not finite for every policy, making the smoothed objective well defined.The algorithm samples perturbations uniformly on the boundary of a Frobenius-norm ball.
  • Gradient estimation: A standard zeroth-order oracle estimates the smoothed gradient using only function-value evaluations.The construction follows the standard smoothing technique associated with Flaxman et al. (2005).
  • Gradient estimation: Polynomially many perturbation samples make the estimated gradient ε-close to ∇C(K) in Frobenius norm with high probability.The guarantee combines smoothing bias control with vector Bernstein concentration.
  • Convergence: Theorem 31 guarantees C(K_T)−C(K⋆)≤ε with high probability after polynomially bounded gradient-descent computation.The result uses truncated trajectory estimates, polynomial sample requirements, and a suitable step size and iteration count.

D.4 The natural gradient analysis

The natural-gradient analysis estimates the state covariance under perturbed policies alongside the gradient, then uses these estimates in the natural-gradient update. The covariance estimate is accurate and remains sufficiently nonsingular, enabling a high-probability performance guarantee.

  • Covariance estimation: Covariance estimation combines perturbation control, finite-horizon truncation, and concentration over simulated trajectories.The proof bounds smoothing and truncation errors before applying matrix concentration inequalities.
  • Covariance estimation: The covariance estimator approximates Σ(K) within ε and preserves σ_min(Σ̂_K)≥μ/2 when ε≤μ/2.This supports stable inversion of the estimated covariance matrix in the natural-gradient update.
  • Natural-gradient update: Natural gradient uses the update K′′=K−η∇̃Σ̃_K^-1 with estimated gradient and covariance.The theorem specifies polynomial choices for perturbation radius, samples, and truncation length.
  • Convergence: Accurate gradient and covariance estimates allow the natural-gradient proof to inherit the convergence argument of the exact-gradient method.The analysis controls the difference between approximate and ideal updates using matrix perturbation bounds.

E Simulation Results

Simulations evaluate gradient descent with backtracking step size on randomly generated linear systems and indicate convergence within reasonable practical time.

  • The experiment uses x ∈R100 and u ∈R20 with random matrices A and B.
  • A is scaled so that it is stabilizing with high probability, specifically λmax(A) ≤1.
  • The solution starts at K0 = 0, ensuring C(K0) is finite because A is stabilizing.
Loading 1801.05039v3…