Stabilizing Dynamical Systems via Policy Gradient Methods

Abstract:
Stabilizing an unknown control system is one of the most fundamental problems in control systems engineering. In this paper, we provide a simple, model-free algorithm for stabilizing fully observed dynamical systems. While model-free methods have become increasingly popular in practice due to their simplicity and flexibility, stabilization via direct policy search has received surprisingly little attention. Our algorithm proceeds by solving a series of discounted LQR problems, where the discount factor is gradually increased. We prove that this method efficiently recovers a stabilizing controller for linear systems, and for smooth, nonlinear systems within a neighborhood of their equilibria. Our approach overcomes a significant limitation of prior work, namely the need for a pre-given stabilizing control policy. We empirically evaluate the effectiveness of our approach on common control benchmarks.

heading: 1 Introduction
text: Stabilizing an unknown control system is one of the most fundamental problems in control systems engineering. A wide variety of tasks - from maintaining a dynamical system around a desired equilibrium point, to tracking a reference signal (e.g a pilot’s input to a plane) - can be recast in terms of stability. More generally, synthesizing an initial stabilizing controller is often a necessary first step towards solving more complex tasks, such as adaptive or robust control design [Sontag, 1999, 2009].
In this work, we consider the problem of finding a stabilizing controller for an unknown dynamical system via direct policy search methods. We introduce a simple procedure based off policy gradients which provably stabilizes a dynamical system around an equilibrium point. Our algorithm only requires access to a simulator which can return rollouts of the system under different control policies, and can efficiently stabilize both linear and smooth, nonlinear systems.
Relative to model-based approaches, model-free procedures, such as policy gradients, have two key advantages: they are conceptually simple to implement, and they are easily adaptable; that is, the same method can be applied in a wide variety of domains without much regard to the intricacies of the underlying dynamics. Due to their simplicity and flexibility, direct policy search methods have become increasingly popular amongst practitioners, especially in settings with complex, nonlinear dynamics which may be challenging to model. In particular, they have served as the main workhorse for recent breakthroughs in reinforcement learning and control [Silver et al., 2016, Mnih et al., 2015, Andrychowicz et al., 2020].
Despite their popularity amongst practitioners, model-free approaches for continuous control have only recently started to receive attention from the theory community [Fazel et al., 2018, Kakade et al., 2020, Tu and Recht, 2019]. While these analyses have begun to map out the computational and statistical tradeoffs that emerge in choosing between model-based and model-free approaches,
∗Correspondence to jcperdomo@berkeley.edu
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
they all share a common assumption: that the unknown dynamical system in question is stable, or that an initial stabilizing controller is known. As such, they do not address the perhaps more basic question, how do we arrive at a stabilizing controller in the first place?

heading: 1.1 Contributions
text: We establish a reduction from stabilizing an unknown dynamical system to solving a series of discounted, infinite-horizon LQR problems via policy gradients, for which no knowledge of an initial stable controller is needed. Our approach, which we call discount annealing, gradually increases the discount factor and yields a control policy which is near optimal for the undiscounted LQR objective. To the best of our knowledge, our algorithm is the first model-free procedure shown to provably stabilize unknown dynamical systems, thereby solving an open problem from Fazel et al. [2018].
We begin by studying linear, time-invariant dynamical systems with full state observation and assume access to inexact cost and gradient evaluations of the discounted, infinite-horizon LQR cost of a state-feedback controller K. Previous analyses (e.g., [Fazel et al., 2018]) establish how such evaluations can be implemented with access to (finitely many, finite horizon) trajectories sampled from a simulator. We show that our method recovers the controller K? which is the optimal solution of the undiscounted LQR problem in a bounded number of iterations, up to optimization and simulator error. The stability of the resulting K? is guaranteed by known stability margin results for LQR. In short, we prove the following guarantee: Theorem 1 (informal). For linear systems, discount annealing returns a stabilizing state-feedback controller which is also near-optimal for the LQR problem. It uses at most polynomially many, ε-inexact gradient and cost evaluations, where the tolerance ε also depends polynomially on the relevant problem parameters.
Since both the number of queries and error tolerance are polynomial, discount annealing can be efficiently implemented using at most polynomially many samples from a simulator.
Furthermore, our results extend to smooth, nonlinear dynamical systems. Given access to a simulator that can return damped system rollouts, we show that our algorithm finds a controller that attains near-optimal LQR cost for the Jacobian linearization of the nonlinear dynamics at the equilibrium. We then show that this controller stabilizes the nonlinear system within a neighborhood of its equilibrium. Theorem 2 (informal). Discount annealing returns a state-feedback controller which is exponentially stabilizing for smooth, nonlinear systems within a neighborhood of their equilibrium, using again only polynomially many samples drawn from a simulator.
In each case, the algorithm returns a near optimal solution K to the relevant LQR problem (or local approximation thereof). Hence, the stability properties of K are, in theory, no better than those of the optimal LQR controller K?. Importantly, the latter may have worse stability guarantees than the optimal solution of a corresponding robust control objective (e.g. H∞ synthesis). Nevertheless, we focus on the LQR subroutine in the interest of simplicity, clarity, and in order to leverage prior analyses of model-free methods for LQR. Extending our procedure to robust-control objectives is an exciting direction for future work.
Lastly, while our theoretical analysis only guarantees that the resulting controller will be stabilizing within a small neighborhood of the equilibrium, our simulations on nonlinear systems, such as the nonlinear cartpole, illustrate that discount annealing produces controllers that are competitive with established robust control procedures, such as H∞ synthesis, without requiring any knowledge of the underlying dynamics.

heading: 1.2 Related work
text: Given its central importance to the field, stabilization of unknown and uncertain dynamical systems has received extensive attention within the controls literature. We review some of the relevant literature and point the reader towards classical texts for a more comprehensive treatment [Sontag, 2009, Sastry and Bodson, 2011, Zhou et al., 1996, Callier and Desoer, 2012, Zhou and Doyle, 1998].
Model-based approaches. Model-based methods construct approximate system models in order to synthesize stabilizing control policies. Traditional analyses consider stabilization of both linear and
nonlinear dynamical systems in the asymptotic limit of sufficient data [Sastry and Bodson, 2011, Sastry, 2013]. More recent, non-asymptotic studies have focused almost entirely on linear systems, where the controller is generated using data from multiple independent trajectories [Fiechter, 1997, Dean et al., 2019, Faradonbeh et al., 2018a, 2019]. Assuming the model is known, stabilizing policies may also be synthesized via convex optimization [Prajna et al., 2004] by combining a ‘dual Lyapunov theorem’ [Rantzer, 2001] with sum-of-squares programming [Parrilo, 2003]. Relative to these analysis our focus is on strengthening the theoretical foundations of model-free procedures and establishing rigorous guarantees that policy gradient methods can also be used to generate stabilizing controllers.
Online control. Online control studies the problem of adaptively fine-tuning the performance of an already-stabilizing control policy on a single trajectory [Dean et al., 2018, Faradonbeh et al., 2018b, Cohen et al., 2019, Mania et al., 2019, Simchowitz and Foster, 2020, Hazan et al., 2020, Simchowitz et al., 2020, Kakade et al., 2020]. Though early papers in this direction consider systems without pre-given stabilizing controllers [Abbasi-Yadkori and Szepesvári, 2011], their guarantees degrade exponentially in the system dimension (a penalty ultimately shown to be unavoidable by Chen and Hazan [2021]). Rather than fine-tuning an already stabilizing controller, we focus on the more basic problem of finding a controller which is stabilizing in the first place, and allow for the use of multiple independent trajectories.
Model-free approaches. Model-free approaches eschew trying to approximate the underlying dynamics and instead directly search over the space of control policies. The landmark paper of Fazel et al. [2018] proves that, despite the non-convexity of the problem, direct policy search on the infinite-horizon LQR objective efficiently converges to the globally optimal policy, assuming the search is initialized at an already stabilizing controller. Fazel et al. [2018] pose the synthesis of this initial stabilizing controller via policy gradients as an open problem; one that we solve in this work.
Following this result, there have been a large number of works studying policy gradients procedures in continuous control, see for example Feng and Lavaei [2020], Malik et al. [2019], Mohammadi et al. [2020, 2021], Zhang et al. [2021] just to name a few. Relative to our analysis, these papers consider questions of policy finite-tuning, derivative-free methods, and robust (or distributed) control which are important, yet somewhat orthogonal to the stabilization question considered herein. The recent analysis by Lamperski [2020] is perhaps the most closely related piece of prior work. It proposes a model-free, off-policy algorithm for computing a stabilizing controller for deterministic LQR systems. Much like discount annealing, the algorithm also works by alternating between policy optimization (in their case by a closed-form policy improvement step based on the Riccati update) and increasing a damping factor. However, whereas we provide precise finite-time convergence guarantees to a stabilizing controller for both linear and nonlinear systems, the guarantees in Lamperski [2020] are entirely asymptotic and restricted to linear systems. Furthermore, we pay special attention to quantifying the various error tolerances in the gradient and cost queries to ensure that the algorithm can be efficiently implemented in finite samples.

heading: 1.3 Background on stability of dynamical systems
text: Before introducing our results, we first review some of the basic concepts and definitions regarding stability of dynamical systems. In this paper, we study discrete-time, noiseless, time-invariant dynamical systems with states xt ∈ Rdx and control inputs ut ∈ Rdu . In particular, given an initial state x0, the dynamics evolves according to xt+1 = G(xt,ut) where G : Rdx × Rdu → Rdx is a state transition map. An equilibrium point of a dynamical system is a state x? ∈ Rdx such that G(x?, 0) = x?. As per convention, we assume that the origin x? = 0 is the desired equilibrium point around which we wish to stabilize the system.
This paper restricts its attention to static state-feedback policies of the form ut = Kxt for a fixed matrix K ∈ Rdu×dx . Abusing notation slightly, we conflate the matrix K with its induced policy. Our aim is to find a policy K which is exponentially stabilizing around the equilbrium point.
Time-invariant, linear systems, whereG(x,u) = Ax+Bu are stabilizable if and only if there exists aK such thatA+BK is a stable matrix [Callier and Desoer, 2012]. That is if ρ(A+BK) < 1, where ρ(X) denotes the spectral radius, or the largest eigenvalue magnitude, of a matrix X . For general nonlinear systems, our goal is to find controllers which satisfy the following general, quantitative
definition of exponential stability (e.g Chapter 5.2 in Sastry [2013]). Throughout, ‖ · ‖ denotes the Euclidean norm. Definition 1.1. A controllerK is (m,α)-exponentially stable for dynamicsG if there exist constants m,α > 0 such that if inputs are chosen according to ut = Kxt, the sequence of states xt+1 = G(xt,ut) satisfy
‖xt‖ ≤ m · exp(−α · t)‖x0‖. (1.1)
Likewise, K is (m,α)-exponentially stable on radius r > 0 if (1.1) holds for all x0 such that ‖x0‖ ≤ r.
For linear systems, a controller K is stabilizing if and only if it is stable over the entire state space, however, the restriction to stabilization over a particular radius is in general needed for nonlinear systems. Our approach for stabilizing nonlinear systems relies on analyzing their Jacobian linearization about the origin equilibrium. Given a continuously differentiable transition operator G, the local dynamics can be approximated by the Jacobian linearization (Ajac, Bjac) of G about the zero equilibrium; that is
Ajac := ∇xG(x,u) ∣∣ (x,u)=(0,0) , Bjac := ∇uG(x,u) ∣∣ (x,u)=(0,0) . (1.2)
In particular, for x and u sufficiently small, G(x,u) = Ajacx+Bjacu+ fnl(x,u), where fnl(x,u) is a nonlinear remainder from the Taylor expansion of G. To ensure stabilization via state-feedback is feasible, we assume throughout our presentation that the linearized dynamics (Ajac, Bjac) are stabilizable.

heading: 2 Stabilizing Linear Dynamical Systems
text: We now present our main results establishing how our algorithm, discount annealing, provably stabilizes linear dynamical systems via a reduction to direct policy search methods. We begin with the following preliminaries on the Linear Quadratic Regulator (LQR). Definition 2.1 (LQR Objective). For a given starting state x, we define the LQR problem Jlin with discount factor γ ∈ (0, 1], dynamic matrices (A,B), and state feedback controller K as, Jlin(K | x, γ, A,B) := ∞∑ t=0 γt ( x>t Qxt + u > t Rut ) s.t. ut = Kxt, xt+1 = Axt +But, x0 = x.
Here, xt ∈ Rdx , ut ∈ Rdu , and Q,R are positive definite matrices. Slightly overloading notation, we define
Jlin(K | γ,A,B) := E x0∼ √ dx·Sdx−1 [Jlin(K | x, γ, A,B)],
to be the same as the problem above, but where the initial state is now drawn from the uniform distribution over the sphere in Rdx of radius √ dx.2
To simplify our presentation, we adopt the shorthand Jlin(K | γ) := Jlin(K | γ,A,B) in cases where the system dynamics (A,B) are understood from context. Furthermore, we assume that (A,B) is stabilizable and that λmin(Q), λmin(R) ≥ 1. It is a well-known fact that K?,γ := arg minK Jlin(K | γ,A,B) achieves the minimum LQR cost over all possible control laws. We begin our analysis with the observation that the discounted LQR problem is equivalent to the undiscounted LQR problem with damped dynamics matrices.3
Lemma 2.1. For all controllers K such that Jlin(K | γ,A,B) <∞,
Jlin(K | γ,A,B) = Jlin(K | 1, √ γ ·A,√γ ·B).
From this equivalence, it follows from basic facts about LQR that a controller K satisfies Jlin(0 | γ,A,B) < ∞ if and only if √γ(A + BK) is stable. Consequently, for γ < ρ(A)−2, the zero
2This scaling is chosen so that the initial state distribution has identity covariance, and yields cost equivalent to x0 ∼ N (0, I).
3This lemma is folklore within the controls community, see e.g. Lamperski [2020].
controller is stabilizing and one can solve the discounted LQR problem via direct policy search initialized at K = 0 [Fazel et al., 2018]. At this point, one may wonder whether the solution to this highly discounted problem yields a controller which stabilizes the undiscounted system. If this were true, running policy gradients (defined in Eq. (2.1)) to convergence, on a single discounted LQR problem, would suffice to find a stabilizing controller.
Kt+1 = Kt − η∇KJlin(Kt | γ), K0 = 0, η > 0 (2.1)
Unfortunately, the following proposition shows that this is not the case.
Proposition 2.2 (Impossibility of Reward Shaping). Fix A = diag(0, 2). For any positive definite cost matrices Q,R and discount factor γ such that √ γA is stable, there exists a matrix B such that (A,B) is controllable (and thus stabilizable), yet the optimal controller K?,γ := arg minK J(K | γ,A,B) on the discounted problem is such that A+BK?,γ is unstable.
We now describe the discount annealing procedure for linear systems (Figure 1), which provably recovers a stabilizing controller K. For simplicity, we present the algorithm assuming access to noisy, bounded cost and gradient evaluations which satisfy the following definition. Employing standard arguments from [Fazel et al., 2018, Flaxman et al., 2005], we illustrate how these evaluations can be efficiently implemented using polynomially many samples drawn from a simulator in Appendix C.
Definition 2.2 (Gradient and Cost Queries). Given an error parameter ε > 0 and a function J :

heading: Rd → R, ε-Grad(J, z) returns a vector ∇̃such that ‖∇̃−∇J(z)‖F ≤ ε. Similarly, ε-Eval(J, z, c)
text: returns a scalar v such that |v −min{J(z), c}| ≤ ε.
The procedure leverages the equivalence (Lemma 2.1) between discounted costs and damped dynamics for LQR, and the consequence that the zero controller is stabilizing if we choose γ0 sufficiently small. Hence, for this discount factor, we may apply policy gradients initialized at the zero controller in order to recover a controller K1 which is near-optimal for the γ0 discounted objective.
Our key insight is that, due to known stability margins for LQR controllers, K1 is stabilizing for the γ1 discounted dynamics for some discount factor γ1 > (1 + c)γ0, where c is a small constant that has a uniform lower bound. Therefore, K1 has finite cost on the γ1 discounted problem, so that we may again use policy gradients initialized at K1 to compute a near-optimal controller K2 for this larger discount factor. By iterating, we have that γt ≥ (1 + c)tγ0 and can increase the discount factor up to 1, yielding a near-optimal stabilizing controller for the undiscounted LQR objective.
The rate at which we can increase the discount factors γt depends on certain properties of the (unknown) dynamical system. Therefore, we opt for binary search to compute the desired γ in the absence of system knowledge. This yields the following guarantee, which we state in terms of properties of the matrix P?, the optimal value function for the undiscounted LQR problem, which satisfies minK Jlin(K | 1) = tr [P?] (see Appendix A for further details). Theorem 1 (Linear Systems). Let Mlin := max{16tr [P?] , Jlin(K0 | γ0)}. The following statements are true regarding the discount annealing algorithm when run on linear dynamical systems:
a) Discount annealing returns a controller K̂ which is ( √ 2tr[P?], (4tr [P?]) −1)-
exponentially stable.
b) If γ0 < 1, the algorithm is guaranteed to halt whenever t is greater than 64tr [P?] 4 log(1/γ0).
Furthermore, at each iteration t:
c) Policy gradients as defined in Eq. (2.1) achieves the guarantee in Eq. (2.2) using only poly(Mlin, ‖A‖op, ‖B‖op) many queries to ε-Grad(·, Jlin(· | γ)) as long as ε is less than poly(M−1lin , ‖A‖−1op , ‖B‖−1op ).
c) The noisy binary search algorithm (see Figure 2) returns a discount factor γ′ satisfying Eq. (2.3) using at most d4 log(tr [P?])e + 10 many queries to ε-Eval(·, Jlin(· | γ)) for ε = .1dx.
We remark that since ε need only be polynomially small in the relevant problem parameters, each call to ε-Grad and ε-Eval can be carried out using only polynomially many samples from a simulator which returns finite horizon system trajectories under various control policies. We make this claim formal in Appendix C.
Proof. We prove part b) of the theorem and defer the proofs of the remaining parts of to Appendix A. Define PK,γ to be the solution to the discrete-time Lyapunov equation. That is for √ γ(A + BK) stable, PK,γ solves:
PK,γ := Q+K >RK + γ(A+BK)>PK,γ(A+BK). (2.4)
Using this notation, P? = PK?,1 is the solution to the above Lyapunov equation with γ = 1. The key step of the proof is Proposition A.4, which uses Lyapunov theory to verify the following: given the current discount factor γt, an idealized discount factor γ′t+1 defined by
γ′t+1 :=
( 1
8‖PKt+1,γt‖4op + 1
)2 γt,
satisfies Jlin(Kt+1 | γ′t+1) = tr[PKt+1,γ′t+1 ] ≤ 2tr [ PKt+1,γt ] = 2Jlin(Kt+1 | γt). Since the control cost is non-decreasing in γ, the binary search update in Step 4 ensures that the actual γt+1 also satisfies
γt+1 ≥ (
1
8‖PKt+1,γt‖4op + 1
)2 γt ≥ ( 1
128tr [P?] 4 + 1
)2 γt,
The following calculation (which uses dx ≤ tr [P?] for λmin(Q) ≥ 1) justifies the second inequality above:
‖PKt+1,γt‖4op ≤ tr [ PKt+1,γt ]4 = Jlin(Kt+1 | γt)4 ≤ (min
K Jlin(K | γt) + dx)4 ≤ 16tr [P?]4 .
Therefore, γt ≥ (1/(128tr [P?]4) + 1)2tγ0. The precise bound follows from taking logs of both sides and using the numerical inequality log(1 + x) ≤ x to simplify the denominator.

heading: 3 Stabilizing Nonlinear Dynamical Systems
text: We now extend the guarantees of the discount annealing algorithm to smooth, nonlinear systems. Whereas our study of linear systems explicitly leveraged the equivalence of discounted costs and damped dynamics, our analysis for nonlinear systems requires access to system rollouts under damped dynamics, since the previous equivalence between discounting and damping breaks down in nonlinear settings.
More specifically, in this section, we assume access to a simulator which given a controller K, returns trajectories generated according to xt+1 = √ γGnl(xt,Kxt) for any damping factor γ ∈ (0, 1], where Gnl is the transition operator for the nonlinear system. While such trajectories may be infeasible to generate on a physical system, we believe these are reasonable to consider when dynamics are represented using software simulators, as is often the case in practice [Lewis et al., 2003, Peng et al., 2018].
The discount annealing algorithm for nonlinear systems is almost identical to the algorithm for linear systems. It again works by repeatedly solving a series of quadratic cost objectives on the nonlinear dynamics as defined below, and progressively increasing the damping factor γ.
Definition 3.1 (Nonlinear Objective). For a state feedback controller K : Rdx → Rdu , damping factor γ ∈ (0, 1], and an initial state x, we define:
Jnl(K | x, γ) := ∞∑ t=0 x>t Qxt + u > t Rut (3.1)
s.t ut = Kxt, xt+1 = √ γ ·Gnl(xt,ut), x0 = x. (3.2)
Overloading notation as before, we let Jnl(K | γ, r) := Ex∼r·Sdx−1 [Jnl(K | γ,x)]× dxr2 .
The normalization by dx/r2 above is chosen so that the nonlinear objective coincides with the LQR objective when Gnl is in fact linear. Relative to the linear case, the only algorithmic difference for nonlinear systems is that we introduce an extra parameter r which determines the radius for the initial state distribution. As established in Theorem 2, this parameter must be chosen small enough to ensure that discount annealing succeeds. Our analysis pertains to dynamics which satisfy the following smoothness definition.
Assumption 1 (Local Smoothness). The transition map Gnl is continuously differentiable. Furthermore, there exist rnl, βnl > 0 such that for all (x,u) ∈ Rdx+du with ‖x‖+ ‖u‖ ≤ rnl,
‖∇x,uGnl(x,u)−∇x,uGnl(0, 0)‖op ≤ βnl(‖x‖+ ‖u‖).
For simplicity, we assume βnl ≥ 1 and rnl ≤ 1. Using Assumption 1, we can apply Taylor’s theorem to rewrite Gnl as its Jacobian linearization around the equilibrium point, plus a nonlinear remainder term.
Lemma 3.1. If Gnl satisfies Assumption 1, then all x,u for which ‖x‖+ ‖u‖ ≤ rnl,
Gnl(x,u) = Ajacx +Bjacu + fnl(x,u), (3.3)
where ‖fnl(x,u)‖ ≤ βnl(‖x‖2 +‖u‖2), ‖∇fnl(x,u)‖ ≤ βnl(‖x‖+‖u‖), and where (Ajac, Bjac) are the system’s Jacobian linearization matrices defined in Eq. (1.2).
Rather than trying to directly understand the behavior of stabilization procedures on the nonlinear system, the key insight of our nonlinear analysis is that we can reason about the performance of a state-feedback controller on the nonlinear system via its behavior on the system’s Jacobian linearization. In particular, the following lemma establishes how any controller which achieves finite discounted LQR cost for the Jacobian linearization is guaranteed to be exponentially stabilizing on the damped nonlinear system for initial states that are small enough. Throughout the remainder of this section, we define Jlin(· | γ) := Jlin(· | γ,Ajac, Bjac) as the LQR objective from Definition 2.1 where (A,B) = (Ajac, Bjac).
Lemma 3.2 (Restatement of Lemma B.2). Suppose that CJ = Jlin(K | γ) < ∞, then K is (C1/2J , (4CJ)−1) exponentially stable on the damped system √ γGnl over radius r = rnl / (βnlC3/2J ).
The second main building block of our nonlinear analysis is the observation that if the dynamics are locally smooth around the equilibrium point, then by Lemma 3.1, decreasing the radius r of the initial state distribution x0 ∼ r · Sdx−1 reduces the magnitude of the nonlinear remainder term fnl. Hence, the nonlinear system smoothly approximates its Jacobian linearization. More precisely, we establish that the difference in gradients and costs between Jnl(K | γ, r) and Jlin(K | γ) decrease linearly with the radius r.
Proposition 3.3. Assume Jlin(K | γ) <∞. Then, for PK,γ defined as in Eq. (2.4):
a) If r ≤ rnl2βnl‖PK,γ‖2op , then ∣∣Jnl(K | γ, r)− Jlin(K | γ)∣∣ ≤ 8dxβnl‖PK,γ‖4op · r.
b) If r ≤ 1 12βnl‖PK,γ‖5/2op , then, ‖∇KJnl(K | γ, r) − ∇KJlin(K | γ)‖F ≤ 48dxβnl(1 + ‖B‖op)‖PK,γ‖7op · r
Lastly, because policy gradients on linear dynamical systems is robust to inexact gradient queries, we show that for r sufficiently small, running policy gradients on Jnl converges to a controller which has performance close to the optimal controller for the LQR problem with dynamic matrices (Ajac, Bjac). As noted previously, we can then use Lemma 3.2 to translate the performance of the optimal LQR controller for the Jacobian linearization to an exponential stability guarantee for the nonlinear dynamics. Using these insights, we establish the following theorem regarding discount annealing for nonlinear dynamics.
Theorem 2 (Nonlinear Systems). Let Mnl := max{21tr [P?] , Jlin(K0 | γ0)}. The following statements are true regarding the discount annealing algorithm for nonlinear dynamical systems when r? is less than a fixed quantity that is poly(1/Mnl, 1/‖A‖op, 1/‖B‖op, rnl/βnl)
a) Discount annealing returns a controller K̂ which is ( √ 2tr[P?], (8tr [P?]) −1)-
exponentially stable over a radius r = rnl / (8βnltr [P?] 2 )
b) If γ0 < 1, the algorithm is guaranteed to halt whenever t is greater than 64tr [P?] 4 log(1/γ0).
Furthermore, at each iteration t:
c) Policy gradients achieves the guarantee in Eq. (2.2) using only poly(Mnl, ‖A‖op, ‖B‖op) many queries to ε-Grad(·, Jnl(· | γ)) as long as ε is less than some fixed polynomial poly(M−1nl , ‖A‖−1op , ‖B‖−1op ).
c) Let c0 denote a universal constant. With probability 1 − δ, the noisy random search algorithm (see Figure 2) returns a discount factor γ′ satisfying Eq. (2.3) using at most c0 · tr [P?]4 log(1/δ) queries to ε-Eval(·, Jnl(· | γ, r?)) for ε = .01dx.
We note that while our theorem only guarantees that the controller is stabilizing around a polynomially small neighborhood of the equilibrium, in experiments, we find that the resulting controller successfully stabilizes the dynamics for a wide range of initial conditions. Relative to the case of linear systems where we leveraged the monotonicity of the LQR cost to search for discount factors using binary search, this monotonicity breaks down in the case of nonlinear systems and we instead analyze a random search algorithm to simplify the analysis.

heading: 4 Experiments
text: In this section, we evaluate the ability of the discount annealing algorithm to stabilize a simulated nonlinear system. Specifically, we consider the familiar cart-pole, with dx = 4 (positions and velocities of the cart and pole), and du = 1 (horizontal force applied to the cart). The goal is to stabilize the system with the pole in the unstable ‘upright’ equilibrium position. For further details, including the precise dynamics, see Appendix D.1. The system was simulated in discrete-time with a simple forward Euler discretization, i.e., xt+1 = xt + Tsẋt, where ẋt is given by the continuous time dynamics, and Ts = 0.05 (20Hz). Simulations were carried out in PyTorch [Paszke et al., 2019] and run on a single GPU.
Setup. The discounted annealing algorithm of Figure 1 was implemented as follows. In place of the true infinite horizon discounted cost Jnl(K | γ, r) in Eq. (C.4) we use a finite horizon, finite sample Monte Carlo approximation as described in Appendix C,
Jnl(K | γ) ≈ 1
N ∑N i=1 J (H) nl (K | γ,x (i)), x(i) ∼ r · Sdx−1.
Here, J (H)nl (K | γ,x) = ∑H−1 j=0 x > t Qxt+u > t Rut, is the lengthH , finite horizon cost of a controller K in which the states evolve according to the √ γ damped dynamics from Eq. (C.5) and ut = Kxt. We used N = 5000 and H = 1000 in our experiments. For the cost function, we used Q = Ts · I and R = Ts. We compute unbiased approximations of the gradients using automatic differentiation on the finite horizon objective J (H)nl .
Instead of using SGD updates for policy gradients, we use Adam [Kingma and Ba, 2014] with a learning rate of η = 0.01/r. Furthermore, we replace the policy gradient termination criteria in Step 2 (Eq. (2.2)) by instead halting after a fixed number (M = 200) of gradient descent steps. We wish to emphasize that the hyperparameters (N,H, η,M) were not optimized for performance. In particular, for r = 0.1, we found that as few as M = 40 iterations of policy gradient and horizons as short as H = 400 were sufficient. Finally, we used an initial discount factor γ0 = 0.9 · ‖Ajac‖−22 , where Ajac denotes the linearization of the (discrete-time) cart-pole about the vertical equilibrium.
Results. We now proceed to discuss the performance of the algorithm, focusing on three main properties of interest: i) the number of iterations of discount annealing required to find a stabilizing controller (that is, increase γt to 1), ii) the maximum radius r of the ball of initial conditions x0 ∼ r · Sdx−1 for which discount annealing succeeds at stabilizing the system, and iii) the radius rroa of the largest ball contained within the region of attraction (ROA) for the policy returned by discount annealing. Although the true ROA (the set of all initial conditions such that the closed-loop system converges asymptotically to the equilibrium point) is not necessarily shaped like a ball (as the system is more sensitive to perturbations in the position and velocity of the pole than the cart), we use the term region of attraction radius to refer to the radius of the largest ball contained in the ROA.
Concerning (i), discount annealing reliably returned a stabilizing policy in less than 9 iterations. Specifically, over 5 independent trials for each initial radius r ∈ {0.1, 0.3, 0.5, 0.7} (giving 20 independent trials, in total) the algorithm never required more than 9 iterations to return a stabilizing policy.
Concerning (ii), discount annealing reliably stabilized the system for r ≤ 0.7. For r ≈ 0.75, we observed trials in which the state of the damped system (γ < 1) diverged to infinity. For such a rollout, the gradient of the cost is not well-defined, and policy gradient is unable to improve the policy, which prevents discount annealing from finding a stabilizing policy.
Concerning (iii), in Table 1 we report the final radius rroa for the region of attraction of the final controller returned by discount annealing as a function of the training radius r. We make the following observations. Foremost, the policy returned by discount annealing extends the radius of the ROA beyond the radius used during training, i.e. rroa > r. Moreover, for each r > .1, the rroa achieved by discount annealing is greater than the rroa = 0.703 achieved by the exact optimal LQR controller and the rroa = 0.506 achieved by the exact optimal H∞ controller for the system’s Jacobian linearization (see Table 1). (TheH∞ optimal controller mitigates the effect of worst-case additive state disturbances on the cost; cf. Appendix D.2 for details).
One may hypothesize that this is due to the fact that discount annealing directly operates on the true nonlinear dynamics whereas the other baselines (LQR and H∞ control), find the optimal controller
for an idealized linearization of the dynamics. Indeed, there is evidence to support this hypothesis. In Figure 3 presented in Appendix D, we plot the error ‖K?pg(γt) − K?lin(γt)‖F between the policy K?pg(γt) returned by policy gradients, and the optimal LQR policy K ? lin(γt) for the (damped) linearized system, as a function of the discount factor γt used in each iteration of the discount annealing algorithm. For small training radius, such as r = 0.05, K?pg(γt) ≈ K?lin(γt) for all γt. However, for larger radii (i.e r = 0.7), we see that ‖K?pg(γt) −K?lin(γt)‖F steadily increases as γt increases.
That is, as discount annealing increases the discount factor γ and the closed-loop trajectories explore regions of the state space where the dynamics are increasingly nonlinear, K?pg begins to diverge from K?lin. Moreover, at the conclusion of discount annealing K ? pg(1) achieves a lower cost, namely [15.2, 15.4] vs [16.5, 16.8] (here [a, b] denotes [min, max] over 5 trials) and larger rroa, namely [0.769, 0.777] vs [0.702, 0.703], than K?lin(1), suggesting that the method has indeed adapted to the nonlinearity of the system. Similar observations as to the behavior of controllers fine tuned via policy gradient methods are predicted by the theoretical results from Qu et al. [2020].

heading: 5 Discussion
text: This works illustrates how one can provably stabilize a broad class of dynamical systems via a simple model-free procedure based off policy gradients. In line with the simplicity and flexibility that have made model-free methods so popular in practice, our algorithm works under relatively weak assumptions and with little knowledge of the underlying dynamics. Furthermore, we solve an open problem from previous work [Fazel et al., 2018] and take a step towards placing model-free methods on more solid theoretical footing. We believe that our results raise a number of interesting questions and directions for future work.
In particular, our theoretical analysis states that discount annealing returns a controller whose stability properties are similar to those of the optimal LQR controller for the system’s Jacobian linearization. We were therefore quite surprised when in experiments, the resulting controller had a significantly better radius of attraction than the exact optimal LQR and H∞ controllers for the linearization of the dynamics. It is an interesting and important direction for future work to gain a better understanding of exactly when and how model-free procedures are adaptive to the nonlinearities of the system and improve upon these model-based baselines. Furthermore, for our analysis of nonlinear systems, we require access to damped system trajectories. It would be valuable to understand whether this is indeed necessary or whether our analysis could be extended to work without access to damped trajectories.
As a final note, in this work we reduce the problem of stabilizing dynamical systems to running policy gradients on a discounted LQR objective. This choice of reducing to LQR was in part made for simplicity to leverage previous analyses. However, it is possible that overall performance could be improved if rather than reducing to LQR, we instead attempted to run a model-free method that directly tries to optimize a robust control objective (which explicitly deals with uncertainty in the system dynamics). We believe that understanding these tradeoffs in objectives and their relevant sample complexities is an interesting avenue for future inquiry.

heading: Acknowledgments
text: We would like to thank Peter Bartlett for many helpful conversations and comments throughout the course of this project, and Russ Tedrake for support with the numerical experiments. JCP is supported by an NSF Graduate Research Fellowship. MS is supported by an Open Philanthropy Fellowship grant. JU is supported by the National Science Foundation, Award No. EFMA-1830901, and the Department of the Navy, Office of Naval Research, Award No. N00014-18-1-2210.

Review summaries:
This paper proposes a model-free algorithm for stabilizing linear and nonlinear dynamical systems. The algorithm solves a series of discounted LQR problems using policy gradient, and provably converges to a stabilizing controller for LTI systems; for nonlinear systems, the algorithm recovers a stabilizing controller in a small ball around the origin (assuming origin is the equilibrium point). This work overcomes a significant limitation of prior work on policy gradient methods for control, which requires a stabilizing controller a priori. Experiments on a simulated nonlinear system suggest that the algorithm can produce a controller in a few iterations that is stabilizing in a ball of reasonable radius around the origin. 

This paper studies how to stabilize dynamic systems using policy gradient methods. In the linear setup, a global stabilization problem is addressed. In the nonlinear setup, a local stabilization problem is solved. The basic idea is that a zero control can be used when the discount  factor is sufficiently small, and one can iteratively apply a discounted LQR formulation to increase the discount factor. The core algorithm is "Discount Annealing." Both theory and simulations are provided to justify the proposed method. Overall, this paper provides the first sample complexity result for solving stabilization via policy gradient methods.

This work gives a method to compute stabilizing controllers given access to noisy gradient evaluations with respect to the policy. The challenge is that if a controller does not stabilize the system, then the cost is infinite and the gradient is undefined. They key insight is to use the discount factor as  a free parameter. Namely, for sufficiently small discount factors, the cost is finite and the gradient can be evaluated. So, the algorithm alternates between taking gradient steps and increasing the discount factor. When a discount factor of 1 is reached, stabilization has been obtained and the problem reduces to a policy gradient method. Bounds on convergence and applications to nonlinear systems are given.