PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem

Hesameddin Mohammadi, Armin Zare, Mahdi Soltanolkotabi, Mihailo R. Jovanović

arXiv:1912.11899v3math.OCcs.AIcs.LGeess.SYphysics.data-an

TL;DR

Model-free LQR optimization lacks exact gradients and is difficult to analyze because controller search is nonconvex. The paper studies gradient flow, gradient descent, and two-point random search for continuous-time infinite-horizon LQR, establishing stability and convergence guarantees. Its principal sample-complexity result is logarithmic scaling in 1/ε for both simulation time and function evaluations.

  • Problem

    Model-free reinforcement learning for unknown dynamical systems lacks exact gradients, while the underlying controller optimization is nonconvex and its convergence and sample complexity remain poorly understood.

  • Method

    The paper analyzes gradient flow and forward-Euler gradient descent for continuous-time infinite-horizon LQR, then studies random search using two-point gradient estimates.

  • Results

    log (1/ε) simulation time and log (1/ε) function evaluations suffice to achieve ε-accuracy in the model-free results, alongside exponential stability and linear convergence guarantees.

  • Takeaways & Limitations

    The results provide convergence and sample-complexity guarantees for model-free continuous-time LQR methods using only function-value-based gradient approximations.

Abstract

from arXiv · show

Model-free reinforcement learning attempts to find an optimal control action for an unknown dynamical system by directly searching over the parameter space of controllers. The convergence behavior and statistical properties of these approaches are often poorly understood because of the nonconvex nature of the underlying optimization problems and the lack of exact gradient computation. In this paper, we take a step towards demystifying the performance and efficiency of such methods by focusing on the standard infinite-horizon linear quadratic regulator problem for continuous-time systems with unknown state-space parameters. We establish exponential stability for the ordinary differential equation (ODE) that governs the gradient-flow dynamics over the set of stabilizing feedback gains and show that a similar result holds for the gradient descent method that arises from the forward Euler discretization of the corresponding ODE. We also provide theoretical bounds on the convergence rate and sample complexity of the random search method with two-point gradient estimates. We prove that the required simulation time for achieving $ε$-accuracy in the model-free setup and the total number of function evaluations both scale as $\log \, (1/ε)$.

I. INTRODUCTION

The paper studies convergence and sample complexity for model-free gradient methods applied to continuous-time infinite-horizon LQR with unknown system parameters. It establishes stability and convergence guarantees for gradient flow, gradient descent, and two-point random search, including logarithmic simulation-time and evaluation complexity.

  • Motivation: Model-free control is motivated by settings where system models are unavailable, while nonconvex controller search and unknown gradients complicate analysis.Structural constraints can also create disjoint search landscapes, limiting conventional descent methods.
  • Problem and scope: The paper analyzes gradient-based methods for the continuous-time infinite-horizon LQR problem despite its nonconvex formulation.The analysis concerns stabilizing feedback gains and uses a convex reparameterization as part of the proof strategy.
  • Gradient methods: Exponential stability holds for the gradient-flow ODE over stabilizing feedback gains, and gradient descent converges linearly with a suitable stepsize.These results address both the continuous dynamics and its forward-Euler discretization.
  • Random search: Two-point random search has linear convergence, using gradient approximations formed from objective-function values at perturbed feedback gains.The method operates in the model-free setting and does not require exact gradients.
  • Sample complexity: log (1/ε) function evaluations and log (1/ε) simulation time are sufficient for ε-accuracy in the reported model-free results.The paper contrasts this scaling with prior results requiring polynomial simulation time or assuming infinite simulation time.
  • Guarantee scope: The convergence guarantees cover both objective-value error and error in the feedback gain matrix.Earlier cited results established convergence only in objective value.

II. PROBLEM FORMULATION

The paper formulates continuous-time infinite-horizon LQR as direct optimization over stabilizing linear feedback gains and develops a simulation-based two-point gradient method when system matrices are unknown.

  • LQR formulation: The continuous-time LQR objective integrates state and control costs over an infinite horizon, with unknown system matrices A and B.The state and control weights are positive definite, and the initial-state distribution has a positive-definite second-moment matrix.
  • LQR formulation: The optimal controller can be sought by directly optimizing the linear feedback gain K under the state-feedback law u = −Kx.The optimization variable is K, while A, B, Q, R, and Ω are problem parameters.
  • Stability domain: The stabilizing-gain set S_K determines finite cost, while gains outside it receive infinite cost under the stated assumption on Ω.For stabilizing gains, the associated matrix X(K) is characterized through a Lyapunov equation.
  • Optimization dynamics: The paper studies gradient-flow dynamics and their discretized gradient-descent variant before analyzing random search for the same optimization problem.The gradient descent stepsize is denoted by α.
  • Model-free algorithm: Random search estimates the gradient by simulating randomly perturbed gains K + rU_i and K − rU_i, then updates K using the estimate.The procedure uses simulation time τ, N random samples, and initial conditions drawn from a distribution D.
  • Model-free algorithm: The two-point gradient estimator requires access to a simulation engine but not knowledge of the system matrices A and B.This makes the procedure applicable to the model-free formulation of the LQR problem.

III. MAIN RESULTS

The nonconvex LQR objective has unique critical points and compact sublevel sets, enabling asymptotic-stability analysis for gradient flow. Additional analysis is required to establish an exponential convergence rate.

  • The LQR objective is nonconvex but has unique critical points and compact sublevel sets.These properties support the use of the objective error as a Lyapunov function.
  • The objective error f(K) − f(K⋆) serves as a maximal Lyapunov function for analyzing gradient-flow dynamics.
  • Gradient-flow dynamics are asymptotically stable over the set of stabilizing feedback gains SK.
  • Asymptotic-stability analysis alone does not guarantee a convergence rate, so additional analysis is needed for exponential stability.

A. Known model

For the known-model case, the paper establishes exponential stability of gradient flow from any stabilizing initial gain and linear convergence of gradient descent with a sufficiently small stepsize.

  • Exponential stability holds for gradient-flow dynamics from any stabilizing initial feedback gain K(0).The result provides an explicit bound on convergence to the LQR solution K⋆.
  • The analysis uses explicit expressions for the gradient-flow convergence rate and constant.
  • Gradient descent converges linearly over SK when the stepsize α is sufficiently small.
  • The convergence rate and associated constant depend on the initial gain and the LQR problem parameters.

B. Unknown model

In the unknown-model setting, the paper analyzes random search under a sub-Gaussian initial-state assumption. With a constant stepsize, it reaches ε-accuracy linearly with high probability, while function evaluations and simulation time scale logarithmically in 1/ε.

  • Under Assumption 1, random search reaches accuracy ε in O(log (1/ε)) iterations with high probability.The initial-state distribution has independent zero-mean unit-variance entries with bounded sub-Gaussian norm.
  • The result uses a constant stepsize that does not depend on ε.
  • Function evaluations and simulation time both scale as log (1/ε) to achieve accuracy ε.
  • The random-search guarantee depends on simulation time, sample count, smoothing, and stepsize choices satisfying the theorem's conditions.

IV. CONVEX REPARAMETERIZATION

The paper addresses the nonconvexity challenge by reparameterizing the LQR problem into a convex problem, proving exponential stability there, and transferring the guarantee back to the original gradient flow.

  • Nonconvexity is the main challenge in establishing exponential stability for gradient flow.
  • A standard change of variables reparameterizes the LQR problem into a convex problem.
  • Exponential-stability guarantees are first established for gradient flow in the convex reparameterization.
  • The gradient flow in the convex parameterization is connected to its nonconvex counterpart, yielding exponential stability for the original dynamics.

A. Change of variables

The paper reparameterizes the LQR design using K = YX^-1, converting the problem into a convex formulation over stabilizing variables. The resulting feasible set is characterized by a positive-definiteness condition equivalent to closed-loop stability.

  • Change of variables: K = YX^-1 reparameterizes LQR design into a convex optimization problem.The objective becomes h(X,Y) = trace(QX + Y^TRYX^-1), jointly convex for X ≻ 0.
  • Change of variables: For invertible A, X can be expressed as an affine function of Y, enabling the reduced formulation.The paper also states that an alternative change of variables extends the results to noninvertible A.
  • Change of variables: The transformed feasible set SY consists of matrices Y satisfying X(Y) ≻ 0.This set is open and convex because X(Y) is affine.
  • Change of variables: The condition X(Y) ≻ 0 is equivalent to the closed-loop matrix A − BY(X(Y))^-1 being Hurwitz.Thus, the transformed domain preserves stabilizing feedback gains.

B. Smoothness and strong convexity of h(Y )

The transformed objective h(Y) is smooth and strongly convex on every nonempty sublevel set, supporting explicit convergence-rate bounds. The paper contributes an explicit strong-convexity expression in terms of the sublevel-set bound and LQR parameters.

  • Smoothness and strong convexity: The smoothness and strong-convexity parameters depend only on the problem parameters.
  • Smoothness and strong convexity: The analysis relies on bounding the second-order Taylor term of h(Y + Ỹ) over SY(a).Earlier work established the relevant upper and lower bounds for this term.
  • Smoothness and strong convexity: The paper provides an explicit expression for µ in terms of a and the LQR problem parameters.This explicit modulus enables bounds on gradient-method convergence rates.
  • Smoothness and strong convexity: h(Y) is L-smooth and µ-strongly convex over every nonempty sublevel set SY(a).These properties support convergence analysis for gradient methods.

C. Gradient methods over SY

Gradient-flow analysis exploits the convex transformed objective h(Y), while gradient descent follows its forward Euler discretization. These results transfer convergence guarantees to the original nonconvex LQR problem over stabilizing gains.

  • Gradient methods over SY: The unique minimizer Y⋆ is an exponentially stable equilibrium of gradient flow for any Y(0) ∈ SY.The proof uses strong convexity and smoothness of h(Y) on the relevant sublevel set.
  • Gradient methods over SY: The transformed gradient-flow and descent results establish exponential and linear convergence for the original nonconvex LQR problem.The original objective has a unique equilibrium at the optimum over stabilizing gains.
  • Gradient methods over SY: Gradient descent uses the update Y_k+1 := Y_k − α∇h(Y_k), with α ∈ [0, 1/L] preserving the iterates in the sublevel set.
  • Gradient methods over SY: The gradient-descent iterates converge to Y⋆ at a linear rate γ = 1 − αµ.
  • Gradient methods over SY: The LQR objective is not convex, but its optimal solution is the unique equilibrium over the stabilizing domain.Its smoothness and coercive behavior support the stability analysis.

A. Gradient-flow dynamics: proof of Theorem 1

The proof transfers exponential decay from the convex gradient flow in Y to the original gradient flow in K. A geometric comparison between the induced and true vector fields supplies the key lower bound.

  • Gradient-flow dynamics: proof of Theorem 1: The change of variables relates the convex and nonconvex LQR formulations through Y = KX(K).The proof compares their gradients over stabilizing sublevel sets.
  • Gradient-flow dynamics: proof of Theorem 1: The gradient-flow objective decays exponentially at rate ρ = 2µc^2.
  • Gradient-flow dynamics: proof of Theorem 1: The objective error f(K) − f(K⋆) satisfies a Polyak-Łojasiewicz condition on every stabilizing sublevel set.The PL parameter is µ_f = µc^2.
  • Gradient-flow dynamics: proof of Theorem 1: The induced trajectory K_ind(t) and the original trajectory K(t) start from the same initial condition and are illustrated with level sets of f(K).
  • Gradient-flow dynamics: proof of Theorem 1: A uniform positive lower bound on the projection of the induced vector field onto −∇f(K) transfers exponential decay to the original dynamics.This geometric bound is identified as the key feature connecting the two flows.

C. Gradient descent: proof of Theorem 2

The analysis establishes linear convergence for gradient descent on stabilizing feedback gains and develops the gradient-estimation results needed for model-free random search. With two-point estimates, the method achieves accuracy ε in logarithmic iterations, function evaluations, and simulation time under the stated conditions.

  • Gradient descent convergence: The gradient is Lipschitz continuous over every non-empty sublevel set SK(a), enabling stepsize selection for descent.The Lipschitz parameter depends on the problem parameters.
  • Gradient descent convergence: Gradient descent converges linearly on the stabilizing sublevel set when α ∈ (0, 1/Lf], with rate γ ≤ 1 − αµf.The rate uses the PL parameter µf and smoothness parameter Lf.
  • Gradient estimation: Two-point random search uses an unbiased gradient estimate whose projection concentrates in the true gradient direction with N = ˜O(n) samples.The analysis avoids directly controlling the full gradient-estimation error and instead exploits directional correlation.
  • Model-free convergence: The required function evaluations and simulation time are proportional to log (1/ε), improving over prior polynomial or 1/ε-dependent bounds.The cited comparisons include at least (1/ε^4) log (1/ε), 1/ε, and polynomial simulation-time requirements.
  • Model-free convergence: The random-search iterates achieve ε-accuracy at a linear rate, requiring O(log (1/ε)) iterations with high probability.The guarantee is obtained under the stated stepsize and probability conditions.

B. Unknown model

The paper analyzes model-free gradient estimation and random search for continuous-time LQR when system parameters and exact gradients are unknown. Its analysis establishes convergence guarantees by exploiting correlation between simulated and true gradients, while identifying finite-horizon and numerical-integration limitations.

  • Gradient-estimation accuracy: The gradient-estimation error decreases exponentially with simulation time before reaching a saturation level determined by the smoothing parameter r.Reducing r lowers the observed saturation level.
  • Gradient-estimation accuracy: The bias bound exhibits exponential dependence on simulation time τ and a saturation term that depends quadratically on r.These properties are consistent with the numerical gradient-estimation results.
  • Model-free gradient estimation: The gradient estimate may remain far from the true gradient, but the simulated gradient is close to the estimate and highly correlated with the true gradient.This correlation is sufficient for the convergence analysis and improves sample-complexity and simulation-time guarantees.
  • Random search convergence: The random search method achieves linear convergence, while both required simulation time and total function evaluations scale as O(log (1/ε)).The convergence experiment uses α = 10^-4, r = 10^-5, and τ = 200.
  • Scope and limitations: The theoretical analysis accounts only for finite-horizon approximation error, whereas empirical ODE solvers and numerical integration may introduce additional errors.The paper identifies these numerical effects as requiring further scrutiny.
  • Convergence analysis: The convergence analysis applies to a nonconvex controller-search formulation by relating its gradient flow to a convex reparameterization.The paper establishes exponential convergence for gradient flow and linear convergence for gradient descent over stabilizing gains.
  • Scope and extensions: The paper establishes model-free sample-complexity bounds for continuous-time LQR without requiring knowledge of system parameters.The work extends related results previously obtained for discrete-time LQR.

I. Proofs of Section VI-B1

This proof section develops concentration and tail bounds for random matrix and gradient-estimation quantities. These tools yield high-probability sample requirements and control the deviation of the random search estimator.

  • Random-matrix concentration: The proofs use concentration results for Gaussian matrices and matrices whose vectorizations are uniformly distributed on a sphere.These results control spectral and Frobenius norms of random matrix products.
  • Random-matrix concentration: The analysis introduces auxiliary events that simultaneously bound spectral and Frobenius norms for all sampled perturbation matrices.A union bound converts individual matrix bounds into a joint event over N samples.
  • Sample complexity: A sufficient sample-size condition has the form N ≥ C′(β^2κ^2/δ)^2(∥M*∥2 + ∥M*∥S)^2 n log^6 N.Under the resulting bounds, the estimator deviation exceeds its tolerance with probability at most 1/N^β.

J. Proofs for Section VI-B2 and probabilistic toolbox

This section supplies the probabilistic and operator-theoretic lemmas used in the convergence and sample-complexity proofs. It bounds random perturbations, establishes concentration properties, and controls Lyapunov operators over objective sublevel sets.

  • Random directions: Uniform-sphere random vectors and normalized Gaussian columns provide concentration bounds for random directional estimators.The proofs relate sphere-distributed perturbations to normalized Gaussian matrices.
  • Probabilistic toolbox: The probabilistic toolbox includes Bernstein, Hanson–Wright, Gaussian-matrix norm, and ψα-norm inequalities.These results control tails, products, and sums of random variables appearing in the estimator analysis.
  • LQR sublevel-set bounds: The auxiliary bounds control controller, Lyapunov, and state-related quantities over sublevel sets of the LQR objective.These bounds support uniform estimates needed in the convergence analysis.
  • Lyapunov operators: For stable closed-loop dynamics, the inverse Lyapunov operator admits norm bounds that can be combined with the sublevel-set estimates.The relevant operator is defined through an integral involving the stable matrix exponential.
  • Connection to convergence proofs: The resulting parameter bounds are used to control the operator quantities appearing in the random-search convergence theorem.The construction relies on bounds for the closed-loop Lyapunov operator and related adjoint operators.
Loading 1912.11899v3…