PaperlayerView exact revision on arXiv

Source-linked AI summary

Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems

Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter L. Bartlett, Martin J. Wainwright

arXiv:1812.08305v3cs.LGmath.OCstat.ML

TL;DR

Derivative-free policy optimization for LQR lacks explicit sample-complexity characterization across important noise and feedback settings. The paper analyzes standard one-point and two-point stochastic zero-order methods for additive-noise and randomly initialized systems, proving explicit convergence guarantees and identifying distinct tolerance dependences.

  • Problem

    The paper asks how many noisy rollout evaluations derivative-free methods require to learn an ǫ-suboptimal linear policy for LQR systems with unknown dynamics.

  • Method

    The paper analyzes stochastic zero-order optimization with one-point and shared-noise two-point oracles, specializing general curvature-based results to additive-noise and randomly initialized LQR systems.

  • Results

    The methods obtain high-probability ǫ-approximate solutions using eO(1/ǫ2) trajectories, or eO(1/ǫ) with paired cost observations, with explicit polynomial dependence on dimension and curvature.

  • Takeaways & Limitations

    One-point and two-point derivative-free methods achieve fast convergence rates for the non-convex LQR problem, while the underlying optimization result applies more broadly to functions with suitable local properties.

  • Takeaways & Limitations

    The analysis restricts step sizes according to curvature and must confine iterates to the region where the linear system remains stable.

Abstract

from arXiv · show

We study derivative-free methods for policy optimization over the class of linear policies. We focus on characterizing the convergence rate of these methods when applied to linear-quadratic systems, and study various settings of driving noise and reward feedback. We show that these methods provably converge to within any pre-specified tolerance of the optimal policy with a number of zero-order evaluations that is an explicit polynomial of the error tolerance, dimension, and curvature properties of the problem. Our analysis reveals some interesting differences between the settings of additive driving noise and random initialization, as well as the settings of one-point and two-point reward feedback. Our theory is corroborated by extensive simulations of derivative-free methods on these systems. Along the way, we derive convergence rates for stochastic zero-order optimization algorithms when applied to a certain class of non-convex problems.

1 Introduction

This paper studies offline model-free control of linear-quadratic systems using derivative-free optimization, focusing on explicit sample-complexity guarantees under different noise and feedback settings. It analyzes standard one-point and two-point methods while addressing stability and non-convexity challenges.

  • Motivation: The central question is the sample complexity of derivative-free methods for learning near-optimal linear policies in LQR systems with unknown dynamics.The analysis tracks dependence on error tolerance, dimension, and conditioning.
  • Problem settings: The study considers offline model-free control under both additive driving noise and random initialization.These settings differ in whether randomness enters through linear updates or the initial state.
  • Approach: The paper analyzes standard one-point and two-point derivative-free random-search variants for stochastic zero-order optimization.The two-point oracle evaluates both queried policies using shared noise.
  • Main result: With high probability, an ǫ-approximate solution can be obtained from eO(1/ǫ2) noisy-cost trajectories, reduced to eO(1/ǫ) when paired costs are observed.The theorem concerns linear quadratic systems and noisy cost observations.
  • Main result: The analysis provides explicit lower-order polynomial dependence on state dimension and curvature properties, improving the parameter specificity of prior guarantees.Earlier related work established polynomial sample complexity without making several parameter dependences explicit.
  • Technical challenges: The proof must keep iterates inside the stable-policy region, and step sizes are restricted by curvature to preserve stability.The paper reports this stability bottleneck for both feedback settings.

2 Background and problem set-up

The paper formulates offline stochastic zero-order optimization for model-free control of LQR systems with noisy function evaluations. It distinguishes additive dynamics noise from random initialization and establishes structural properties that support optimization despite non-convexity.

  • Optimization background: The stochastic zero-order problem minimizes an expected function using noisy one-point or shared-noise two-point evaluations.Two-point feedback can reduce gradient-estimation variance because both evaluations share the same noise realization.
  • Optimal control background: The LQR setting assumes unknown dynamics and unknown costs, so policies are optimized from rollout-cost observations rather than a known model.The offline framework uses restarted rollouts and separates model-free control from procedures that observe state sequences and construct dynamics models.
  • Optimal control background: The paper studies two randomness models: additive noise driving the dynamics and random initial states with deterministic transitions.These are called the additive noise setting and the randomly initialized setting, respectively.
  • Some properties of the LQR cost function: LQR policy optimization is non-convex because unstable policies have infinite cost and the stabilizing-policy region is non-convex.A stabilizing policy satisfies ρspec(A−BK) < 1, and the analysis initializes from a policy with finite cost.
  • Some properties of the LQR cost function: Despite non-convexity, the LQR cost satisfies a PL condition over stable policies, with the global optimum characterized through K∗.The PL property makes the cost amenable to stochastic optimization methods.
  • Some properties of the LQR cost function: Population costs in the additive-noise and random-initialization models are equivalent up to scaling when their driving noises share the same first two moments.The paper cautions that their observed costs remain quite different even when population costs behave identically.

3 Main results

The paper analyzes a canonical stochastic zero-order algorithm for locally smooth, non-convex functions satisfying a PL inequality, then derives convergence guarantees for several LQR settings. The resulting rates differ substantially between one-point and two-point feedback, while additive noise and random initialization have similar one-point behavior.

  • Convergence guarantees: The main theorem characterizes zero-order convergence using gradient-estimate variance and uniform magnitude bounds for locally smooth functions satisfying a PL inequality.The analysis is then specialized to the LQR cost functions.
  • LQR consequences: For one-point random initialization, choosing r ∼ǫ1/2 and η ∼ǫ2 yields T ∼η−1 log(1/ǫ) steps despite high-variance estimates.The result also guarantees stability of all iterates with constant probability.
  • LQR consequences: Minibatches of size k reduce gradient-estimate variance by a factor k and reduce iterations by a factor k, while leaving total zero-order evaluations unchanged.The canonical algorithm uses k = 1, whereas larger minibatches recover the setting associated with Fazel et al.
  • Limitations: Step-size selection is constrained by stability and curvature, so larger steps cannot be guaranteed to keep the iterates within stable policies.This bottleneck is observed empirically in both one-point and two-point settings.
  • LQR consequences: Two-point random-initialization feedback achieves eO(1/ǫ) iterations, substantially faster than the eO complexity required by one-point evaluations.The difference is attributed to the lower variance of the two-point gradient estimator.
  • Limitations: The analysis leaves online no-regret learning in the noisy-dynamics model for future work because it currently provides only a constant-probability offline guarantee.A high-probability convergence bound could in principle support such an extension.
  • LQR consequences: Both one-point random initialization and one-point noisy dynamics have O(1/ǫ2) zero-order complexity, whereas the two-point setting has O(1/ǫ) dependence.The one-point difficulty increases near the optimum because noise remains constant while the population-cost signal decreases.

4 Proofs of main results

The proofs establish convergence by analyzing stochastic zero-order updates under local curvature, gradient-estimate, and bounded-region conditions. A stopping-time and supermartingale argument controls both expected progress and the probability that iterates remain in the valid region.

  • General convergence argument: The proof analyzes cost error Δ_t and stops when an iterate exits the bounded region G0.Within G0, the gradient estimate is controlled by variance and almost-sure norm bounds.
  • General convergence argument: Proposition 1 establishes the convergence bound and shows that the iterates remain in G0 through T iterations with probability greater than 4/5.The theorem follows from this proposition by applying Markov’s inequality and the proposition’s expectation and stability bounds.
  • One-step progress: The one-step analysis combines local smoothness, the PL condition, and bounded stochastic-gradient estimates to control expected progress.The update uses a smoothing radius r and a step-size constrained so that the update remains within the local region.
  • Stability control: A stopped-process supermartingale and Doob’s maximal inequality bound the probability of leaving G0 during the algorithm.The proof runs the method for 2T iterations to construct the stopped process and establish the required maximal-probability control.
  • Zero-order estimators: The gradient estimator is formed from one-point or two-point reward feedback using random perturbations on the sphere, with corresponding scaling by r or 2r.The smoothed objective f_r is defined by averaging f(x + rv) over a unit ball, and the estimator’s properties are established through Lemma 6.

5 Discussion

The discussion presents the work as a derivative-free analysis of model-free LQR control that handles unbounded costs and non-convex domains through local bounded-set properties. It also identifies unresolved questions about sharpness, broader policy classes, and extensions to other algorithms and online learning.

  • Discussion: The paper derives convergence rates for one-point and two-point zero-order methods learning linear policies in noisy LQR systems.The analysis addresses both additive-noise and randomly initialized settings.
  • Discussion: The proof controls the potentially unbounded cost and non-convex optimization domain using local properties guaranteed on a bounded set.This local-property approach makes the optimization-theoretic result applicable beyond reinforcement learning.
  • Open questions: Lower bounds and sharp dependence on error tolerance, dimension, and local curvature remain open questions for model-free LQR.The authors conjecture sharp error-tolerance dependence but do not establish it rigorously.
  • Open questions: The cost-function characterizations may help sharpen natural-gradient analyses and analyze REINFORCE for LQR, but these directions are left for future work.The paper also leaves the sharp characterization of curvature parameters around a policy unresolved.
  • Open questions: Extending guarantees beyond linear policies and to more complex policy parameterizations is identified as a broader model-free reinforcement-learning challenge.The paper asks how sample complexity changes with the policy class and with larger system classes.

A.1 Proof of Lemma 1

Lemma 1 is established by proving auxiliary bounds under a local Frobenius perturbation condition and then selecting valid local-radius and Lipschitz constants.

  • Proof of Lemma 1: The proof establishes Lemma 1 for policy pairs satisfying ||K′ − K||F ≤ cK9.The argument verifies the condition required by a prior LQR result and derives bounds for the relevant quantities.
  • Proof of Lemma 1: Valid choices for the local radius and Lipschitz constants are obtained by comparing Lemma 7 with Lemma 1.The proof also notes λK ≤ eλK because m ≤ Cm.
  • Proof of Lemma 1: The proof concludes after combining the derived upper bounds with the cited lemmas and completing the remaining inequalities.The section explicitly states that putting the pieces together completes Lemma 1.
  • Proof of Lemma 1: The bounds for the three target terms are assembled from auxiliary estimates and results from Fazel et al. [FGKM18].These estimates control the operator and covariance-related quantities needed for the lemma.

A.1.1 Proofs of the auxiliary bounds

The auxiliary bounds (32a)–(32d) are proved using norm bounds, a cited covariance estimate, and previously established inequalities.

  • Proofs of the auxiliary bounds: Bound (32a) follows from ||K − K′||2 ≤ 1 and ||K||2 ≤ cK1.The second inequality is attributed to Lemma 22 of Fazel et al. [FGKM18].
  • Proofs of the auxiliary bounds: Bound (32b) is obtained by invoking Lemma 19 of Fazel et al. [FGKM18] together with the upper bound (34).The proof identifies inequality (34) as the basis for the final step.
  • Proofs of the auxiliary bounds: Bounds (32c) and (32d) follow from Lemma 17 and the norm bound ||K||2 ≤ cK1.The passage labels the second result as bound (32c), although the surrounding text refers to (32d).

A.2 Proof of Lemma 2

Lemma 2 establishes local smoothness of the LQR cost by bounding gradient differences and the terms arising from the cost-gradient decomposition.

  • Proof of Lemma 2: The cost function C(K) is locally Lipschitz within a ball of radius ζK around K.This property is stated as the starting point for the proof of Lemma 8.
  • Proof of Lemma 2: For K′ satisfying ||K′ − K||F ≤ cK9, the proof bounds changes in E and Σ using prior LQR lemmas and norm estimates.The gradient expression used is ∇C(K) = EKΣK.
  • Proof of Lemma 2: The gradient ∇C(K) is Lipschitz with constant φK, obtained by combining bounds on the cost-gradient components.The constant φK is defined from the problem parameters and auxiliary constants.
  • Proof of Lemma 2: Within Glqr, the cost satisfies C(K) ≤ 10C(K0) − 9C(K∗), enabling scaled choices ρlqr = g cK9, φlqr = g cK7, and λlqr = g cK8.These choices give local-radius and smoothness parameters for the LQR setting.
  • Proof of Lemma 2: The noisy-dynamics setup uses st = (A − BK)st−1 + zt with discount factor γ ∈ (0, 1), where the driving noise is bounded almost surely.The section relates population costs and establishes gradient-estimate properties for noisy dynamics.
  • Proof of Lemma 2: Lemma 10 states equivalence of population costs up to scaling, while Lemma 11 provides a uniform bound for any policy K.These lemmas support the noisy-dynamics analysis.

B.1 Proof of Lemma 4

Lemma 4 is proved by analyzing finite-horizon cumulative costs, applying trace and matrix inequalities, and taking the infinite-horizon limit.

  • Proof of Lemma 4: The cumulative cost Ct is analyzed first, and its infinite-horizon limit establishes the relation required for Lemma 4.The proof concludes by taking t → +∞ on the left-hand side.
  • Proof of Lemma 4: The bound on the cumulative cost uses the almost-sure noise bound ∥zi∥2∥zj∥2 ≤ Cm.This controls the terms appearing in the finite-horizon expansion.
  • Proof of Lemma 4: The first and second terms in equation (42) are bounded by symmetric arguments.The resulting uniform bound is then extended to the infinite-horizon cost.
  • Proof of Lemma 4: The auxiliary inequalities (41a)–(41c) are proved using trace inequalities, the definition of ΣK,γ, and multiplication by 1 − γ.These estimates are used in the final uniform-bound argument.

C Proof of Lemma 6

The proof of Lemma 6 is divided into two claims and uses symmetry, unbiasedness, Jensen’s inequality, and local Lipschitz continuity. The accompanying experiments tune initialization, step size, smoothing radius, and rollout length.

  • The proof of Lemma 6 is split into two separate claims.
  • Symmetry of the uniform distribution on the shell S^{d−1} is used in one equality of the proof.
  • The identity f(x) = Eξ∼D[F(x, ξ)] justifies another equality in part (a).
  • Jensen’s inequality and local Lipschitz continuity of ∇f with parameter φ0 support the bound in part (b).
  • Experimental setup: Experiments randomly perturb K∗ to initialize K0, tune the step size manually, and choose the smoothing radius to preserve stability.

D.1 Details of Experiments from Section 3

This section specifies the LQR instances and feedback settings used for the experiments in Section 3. The setups vary system matrices, initialization distributions, additive noise, feedback type, and discount factors.

  • Instance comparison: For one one-dimensional example, the population-level costs in the random-initialization and additive-noise settings are equal up to a constant scaling factor.
  • Random initialization: The one-point random initialization example uses A = 5, B = 0.33, Q = 1, and R = 1.
  • Feedback and initialization: The experiments include one-point random initialization, two-point random initialization, and one-point additive noise settings.
  • Random initialization: The two-point random initialization setting samples the initial state uniformly from canonical basis vectors and uses discount factor 1.
  • Additional instances: Another instance uses A = 0.1 × I, B = 0.01 × I, Q = 100 × I, and R = 100 × I, with random initialization or additive noise across figures.
  • Additive noise: The one-point additive-noise example uses A = 0.1 × I, B = 0.01 × I, Q = 25 × I, and R = 25 × I.

D.2 Additional Experiments

Additional experiments examine complexity scaling with initial cost and error tolerance, including a prior LQR instance and a randomly generated 8 × 8 system. The reported initial-cost scaling is approximately quadratic, while larger minibatches can become suboptimal.

  • Plot interpretation: The additional experiments use dotted lines representing best fits for their corresponding data points.
  • Minibatching: Larger minibatches are often suboptimal because the step size eventually plateaus as batch size increases.
  • Scaling with initial cost: O(C(K0)^2) approximately describes the algorithm’s zero-order complexity scaling with initial cost C(K0).The authors suggest this indicates their Lipschitz and smoothness bounds are not sharp in this respect.
  • Scaling with tolerance: Figure 5 measures total zero-order complexity across eight logarithmically spaced tolerances in the interval (0.005, 1).The experiment uses the LQR instance from [DMM+17] and reports C(K∗) = 2.36.
  • Higher-dimensional example: Figure 6 tests tolerance scaling on a randomly generated 8 × 8 LQR system.The matrices A, B, Q, and R are generated from Gaussian samples and then used to form the experiment.

E Improved analysis of minibatching algorithm from Fazel et al. [FGKM18]

The improved analysis studies Fazel et al.’s minibatching algorithm, which averages one-point evaluations before taking gradient steps. Its total-evaluation convergence rate matches that of the canonical zero-order algorithm under the sharpened bounds.

  • Algorithm: Each minibatched iteration averages one-point zero-order evaluations to obtain a low-variance gradient estimate, then takes a gradient step.
  • Algorithm: The algorithm introduces a minibatch-size hyperparameter k in addition to r, η, and T.
  • Complexity accounting: k · T zero-order evaluations are used when the minibatched algorithm runs for T iterations.
  • Convergence comparison: The minibatching algorithm has the same e O convergence rate in total zero-order evaluations as the canonical zero-order algorithm.The paper attributes this result to sharpened problem-specific bounds.
  • High-probability guarantee: The high-probability analysis sets δ = T^-1δ′ and gives evaluation complexity of order ǫ^-2 log(1/ǫ)·log log(1/ǫ)·log(1/δ′).The stated guarantee holds with probability 1−δ′.
  • LQR consequence: The analysis yields a corollary for LQR control with one-point feedback under specified step-size and smoothing-radius choices.

E.1 Proof of Theorem 2

The proof establishes a minibatch gradient-estimation bound, then combines it with local smoothness, parameter conditions, and induction to control the optimization error with high probability.

  • Gradient-estimate concentration: Lemma 13 bounds the k-sample minibatch gradient estimate for any smoothing radius r in (0, ρ0).The proof invokes concentration for i.i.d. bounded random vectors and identifies the estimator’s mean as ∇f_r(x).
  • Application to Theorem 2: Theorem 2 applies the result when the current suboptimality satisfies f(x) − f* ≤ 10∆0 and uses a minibatch size k tied to µ and ǫ.The proof concludes by substituting the selected tuple of η and T.
  • Local control: The step size is restricted so the update ηg(x) remains within radius ρ0, where the required local Lipschitz and smoothness properties hold.The argument uses a bound on the step magnitude together with η and the error-tolerance assumptions.
  • One-step analysis: The proof combines the gradient-estimation bound with smoothness, the PL inequality, and elementary inequalities to derive the key recursion.The displayed intermediate bounds separate the gradient-estimation error from terms involving ∥∇f(xt)∥² and the smoothing radius r.
  • High-probability recursion: Induction and a union bound show that the error-control events hold through time t with probability exceeding 1 −δ(t + 1).The base case establishes E1 with probability exceeding 1 −δ, and the induction step propagates the bound to E_{t+1}.
Loading 1812.08305v3…