Stabilizing Dynamical Systems via Policy Gradient Methods
Authors: Juan Carlos Perdomo
Jack Umenberger
Max Simchowitz
Venue: NeurIPS 2021 Poster (2021)
Keywords: control theory
stability
LQR
policy gradients

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. 


Stabilizing Dynamical Systems via Policy Gradient Methods
Juan C. Perdomo" University of California, Berkeley
Jack Umenberger MIT
Max Simchowitz MIT
Abstract
Stabilizing an unknown control system one the most fundamental problems in control systems engineering. In this paper, we provide simple, model-free algorithm for stabilizing fully observed dynamical systems. While model-free methods have become increasingly popular in practice due their simplicity and flexibility, stabilization via direct policy search has received surprisingly little at- tention. Our algorithm proceeds by solving a series of discounted LQR problems. where the discount factor is gradually increased. We prove that this method effi- ciently recovers a stabilizing controller for linear systems, and for smooth, nonlin- ear systems within a neighborhood of their equilibria. Our approach overcomes significant limitation of prior work, namely the need for a pre-given stabiliz- ing control policy. We empirically evaluate the effectiveness of our approach on common control benchmarks.
Introduction
Stabilizing an unknown control system one of the most fundamental problems in control systems engineering. A wide variety of tasks from maintaining dynamical system around desired equi- librium point, to tracking a reference signal (e.g a pilot's 's input to a plane) can be recast in terms of stability. More generally, synthesizing initial stabilizing controller 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 simple procedure based off policy gradients which provably stabilizes a dynamical system around an equilibrium point. Our algorithm only requires access 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 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 Comdsppoddeeeerrrrrdddbbbbbbeeb jcperdomo@berkeeey.ccomm edu
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

they all share common assumption: that the unknown dynamical system in question is stable, or that an initial stabilizing controller known. As such, they do not address the perhaps more basic question, how do we arrive stabilizing controller in the first place?
1.1 Contributions
We establish reduction from stabilizing an unknown dynamical system to solving a series of dis- counted, 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 control policy which is near optimal for the undiscounted LQR objec- tive. To the best of our knowledge, our algorithm 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, sume access to inexact cost and gradient evaluations of the discounted, infinite-horizon LQR cost of feetbbcke controller K. Previous analyses (e.g., [Fazel et al., 2018]) establish how such eval- uations can be implemented with access to (finitely many, finite horizon) trajectories sampled from 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:
dynamical systems with full state observation and
Theorem (informal). For linear systems, discount annealing returns a stabilizing state feeebfke controller which is also near-optimal for the LQR problem. It uses at most polynomially many, E-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 simulator.
Furthermore, our results extend to smooth, nonlinear dynamical systems. Given access to a sim- ulator that can return damped system rollouts, we show that our algorithm finds a controller that attains near-optimal LQR cost for the Jacobian linearization the nonlinear dynamics at the equi- librium. We then show that this controller stabilizes the nonlinear system within neighborhood of its equilibrium.
Theorem (informal). Discount annealing returns a state-feedbacc controller which is exponen- tially 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, better than those of the optimal LQR controller K. Importantly, the latter may have worse stability guarantees than the optimal solution of corresponding robust control objective (c.g. Hov 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 Hog synthesis, without requiring any knowledge of the underlying dynamics.
1.2 Related work
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 litera- ture and point the reader towards classical texts for more comprehensive treatment [Sontag, 2009, Sastry and Bodson, 201 1, 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 1, Sastry. 2013]. More recent, non-asympiotic 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., 8a, 2019]. Assuming the model is known, stabilizing policies may also be synthesized via convex optimization [Prajna et al., 2004] by combining 'dual Lyapunov theorem' [Rantzer, 2001] with sum-of- -um-of-quarees 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-stabilizingg control policy on 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, Simehowitz 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 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 dy- namics 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-hrizonn 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 umite-tuning, derivative-free methods, and robust (or distributed) con- trol which are important, yet somewhat orthogonal to the stabilization question considered herein. The recent analysis by Lamperski [2020] perhaps the most closely related piece of prior work. It proposes model-free, off-policy algorithm for computing stabilizing controller for determin- istic 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 conver- gence guarantees to 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.
1.3 Background on stability of dynamical systems
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 dy- namical systems with states x, E Rd= and control inputs u, Rd In particular, given an initial state Xy. the dynamics evolves according to X(+1 = G(x,, u,) where G Rd x Rd + Rd= is a state transition map. An equilibrium point of a dynamical system is a state x, E Rdz such that G(x,, x.. As per convention, we assume that the origin x. 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 u, Kx, for fixed matrix K E dd.. Abusing notation slightly, we conflate the matrix K with its induced policy. Our aim is to find policy K which is exponentially stabilizing around the equilbrium point.
Time-invariant, linear systems, where G(x, u) = Ax + Bu are stabilizable if and only if there exists a K such that A+ BK is stable matrix [Callier and Desoer, 2012]. That is if p(A+BK) < 1, where p(X) denotes the spectral radius, or the largest eigenvalue magnitude, of matrix X. For general nonlinear systems, our goal is to find controllers which satisfy the following general, quantitative
3

---

definition of exponential stability (e.g Chapter 5.2 in Sastry [2013]). Throughout, || denotes the Euclidean norm.
Definition 1.1. A controller K is (m, a) exponentialll stable for dynamics G if there exist constants m, a > 0 such that if inputs are chosen according to u, = Kx,, the sequence of states X = G(x,, ue) satisfy
x S m exp(-a -)) E)||x
(1.1)
Likewise, K (m, a) exxponetiall stable on radius r (1.1) holds for all xo such that ||xo|| ST.
For linear systems, controller K stabilizing and only it is stable over the entire state space, however, the restriction to stabilization a particular radius is in general needed for nonlinear systems. Our approach for stabilizing nonlinear systems relies on analyzing their Jacobian lin- earization about the origin equilibrium. Given continuously differentiable transition operator G, the local dynamics can be approximated by the Jacobian linearization (Ajae, Bjue) of G about the zero equilibrium; that is
Ajac :- Vx w) (x.0)
:- VuG(x, V (x.)
(1.2)
particular, for x and sufficiently small, G(x, u) AjacX + Bjacu fnlxx, u), where fni u) a nonlinear remainder from the Taylor expansion of G. To ensure stabilization via state-feedback feasible, we assume throughout our presentation that the linearized dynamics (Afac Bjac) are stabilizable.
2 Stabilizing Linear Dynamical Systems
We now present our main results establishing how our algorithm, discount annealing, provably sta- bilizes linear dynamical systems via reduction direct policy search methods. We begin with the following preliminaries on the Linear Quadratic Regulator (LQQR..
Definition 2.1 (LQQR Objective). For a given starting state x, we define the LQQ problem Jin with discount factor E (0, 1), dynamic matrices (A, B), and state feedback controller K as,
Jin(K x, 7. A,
y2 (x, Qxi + u, Ruu) s.t. u Kxt, Xx+1 = Ax; + Bu, Xo = x.
Here, X; E Rdd, E Rdd, and Q, R are positive definite matrices. Slightly overloading notation, define
Jmn (K 7, A, B)
E Ny d Sts
[Jin [ xx 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 12d of radius vdz.²
To simplify our presentation, we adopt the shorthand Jın (K 7) == Jan(K | 7, A) in cases where the system dynamics (A, B) are understood from context. Furthermore, we as- sume that (A, B) is stabilizable and that Xmin(Q), Amin RR) 2 1. It is a well-known fact that Ka, == arg ming Jiin [ Y, 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."
Lemma 2.1. For all controllers K such that Jiin (K 7, A, oo.
JIn(K A, B) = Jua (K 1, V A, A.VT-BL B).
From this equivalence, it follows from basic facts about LQR that controller К satisfies Jun (0 A, B) < oo if and only if (AA + BK) is stable. Consequently, for < p(A)-2 the zero
TTiis scaling is chosen so that initial state distribution has identity covariance, and yields cost equivalent to Xg (0 7). This lemma is folklore within the controls community, e.g. Lamperski [2020).

---

Discount Annealing
Initialize: Objective J(: To E (0.P(A)) Ko + O, and Q + 1,
For 1 = 0,
1. If yt = 1, run policy gradients once more as in Step 2, break, and return the resulting K'.
2. Using policy gradients (see Eq. (2.1)) initialized at K,, find K' such that:
Jun( ("' 7/e) - min Jii (K (6) S dg.
(2.2)
K
3. Update initial controller K441 + K".
4. Using binary or random search, find a discount factor 7 E lyve such that
2Ka4 (n) J(Ke+1 >1) 8J(K2+1 (x).
(2.3)
5. Update the discount factor Yo+1 +/--
Figure 1: Discount annealing algorithm. The procedure is identical for both linear and nonlinear systems. For linear, we initialize J J. 70) and for nonlinear J J.(( Y0, rx) where r. is chosen in Theorem 2. See Theorem 1, Theorem 2, and Appendix C for details regarding policy gradients and binary (or random) search. The constants above are chosen for convenience, any constants C1, Cg such that c1 < c2 suffice.
controller is stabilizing and one can solve the discounted LQR problem via direct policy search initialized at K = [Fazel et al., 2018]. At this point, one may wonder whether the solution to this highly discounted problem yields 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 stabilizing controller.
K1+1 K₁ V Jin (K₃ 17), Ko 0, 7>
(2.1)
Unfortunately, the following proposition shows that this not the case.
Proposition 2.2 (Impossibility Reward Shaping). Fix A d0ag(0,2) 2). For any positive definite cost matrices Q, R and discount factor y such that V is stable, there exists matrix B such that (A, B) is controllable (and thus stabilizable), yet the optimal controller K,,y == arg ming J(K Y, A, B) the discounted problem is such that A + BK.,y ky is unstable.
We now describe the discount annealing procedure for linear systems (Figure 1), which provably re- covers 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 simulator in Appendix C.
Definition 2.2 (Gradient and Cost Queries). Given error parameter 0 and function J Rd + IR, e-Grad J, 2) returns vector such that ||V [J(2)]lF -Similarly, e-Eval 2,2.0, (J, cH S 8.
returns a scalar such that l min (J))
The procedure leverages the equivalence (Lemma 2.1) between discounted costs and damped dy- namics for LQR, and the consequence that the zero controller is stabilizing if we choose Yo suffi- ciently small. Hence, for this discount factor, we may apply policy gradients initialized at the zero controller in order to recover controller K₃ which is near-optimal for the discounted objective.
Our key insight is that, due to known stability margins for LQR controllers, K2 is stabilizing for the Yi discounted dynamics for some discount factor > (1 + c). where e is small constant that has finite cost on the 71 discounted problem, so that we
has a uniform lower bound. Therefore, may again use policy gradients initialized at K₁ to compute a near-optimal controller K₂ for this larger discount factor. By iterating, we have that 7 (1 + e) and can increase the discount factor up to 1, yielding optrmal stabilizing controller for the undiscounted LQR objective.
5

---

The rate at which we can increase the discount factors "/e depends on certain properties of the (un- known) dynamical system. Therefore, we opt for binary search compute the desired y 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 undiscounted LQR problem, which satisfies ming Jiin K 11] tr (P.) (see Appendix A for further details).
16tr 16tr , Jin (Ko I no)). The following state- ments are true regarding the discount annealing algorithm when run on linear dynamical systems:
Theorem 1 (Linear Systems). Let Min max
a) Discount annealing returns controller K which is (v2tr(P.), (4tr (P.)) !) exponentially stable.
b) If 7o < 1. the algorithm is guaranteed to halt whenever t is greater than 64tr [P.] log(1/7)).
Furthermore, at each iteration t:
c) Policy gradients as defined Eq. (2.1) achieves the guarantee in Eq. (2.2) using only poly(Min, |Allap: || op) many queries to g-Grad(', Juil 7)) as long is less than poly(Mim)
|| |B
c) The noisy binary search algoritim (see Figure 2) returns discount factor Vf satisfying Eq. (2.3) using at most [4log(tr [P+I)] + 10 many queries to E-Eval(- Jmn( 7)) for
= =1d.
We remark that since need only be polynomially small in the relevant problem parameters, each call e-Grad and s-Eval can be carried using only polynomially many samples from simulator which returns finite horizon system trajectories under various control policies. We make this claim formal in Appendix C.
Proof. We prove part 6) of the theorem and defer the proof's of the remaining parts of to Appendix A. Define Pk.., to be the solution the discrete-time Lyapunov equation. That for v7(A BK) stable, PK.y solves:
PK. == 2 KTRKTRRK >(A BK) Pk,)(A BK).
(2.4)
Using this notation, P. P 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 % an idealized discount factor Y41 defined by
( %
h+1 =
satisfies Jun (Ke+1 7411) tr|Pk 2tr [P 2J (Ke+1 1)). Since the control cost is non-decreasing in y, the binary search update in Step 4 ensures that the actual 7441 also satisfies
2
7++1
+1 7 2
128tr [P.]* + n
8llPken llbp
The following calculation (which uses d, S Lr [Pa] for Amin (Q) 2 1) justtifiss the second inequality above:
|| P 1l < tr [P Jii((K4 1x)* < (min Jmn [K] (m) + dz) < 16tr [P.]*_
Therefore, 7. > (1/(128ur [P.]a) 1)2 The precise bound follows from taking logs of both sides and using the numerical inequality log(1 + x) S x. to simplify the denominator.

---

Stabilizing Nonlinear Dynamical Systems
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 simulator which given a controller K, returns trajectories generated according to X:+1 = vaGmi Kx+) for any damping factor y e (0, IJ. where Gal 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, 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. again works by repeatedly solving series quadratic cost objectives on nonlinear dynamics as defined below, and progressively increasing the damping factor
Definition 3.1 (Nonlinear Objective). For state feedback controller K Rdd - Rdv, damping factor y E (0, 1]. and an initial state x, we define:
In x, = Σ
xi Qx: + u, Ru,
(3.1)
t=0
s.t u Kxt,
X,+1
V7 (, uz), Xg =x
(3.2)
Overloading notation as before, we let Mni(K 7, Ex (Ki(( 7, x,) $
The normalization by dg/r² above is chosen so that the nonlinear objective coincides with the LQR objective when GnI 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 (Local Smoothness). The transition map Gui is continuously differentiable. Further- more, there exist Tal, Put > O such that for all (x, u) E Rd. with |x||| + ||u||| S Tal.
Gmix u) Vx.u Gul (0, 0)llop < S.a( |x|| + |[ll)
For simplicity. we assume Bal 2 1 and Vul < 1. Using Assumption 1, we can apply Taylor's theorem to rewrite G. its Jacobian linearization around the equilibrium point, plus nonlinear remainder term.
Lemma 3.1. If Gul satisfies Assumption 1, then all x, u for which ||x||| + ||
S Ful
Gni(x, u) -jaax + Biac + fni(x, u);
(3.3)
where [x uIll < +=a([||/++||u]]) I[V[n uill S Pm [|| + [|l])) and where (Ajucr Bjuc)
the system's '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 's Jacobian lin- earization. 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 Jiin (1))====))> == Jin( (- Ajacs Bjac) as the LQR objective from Definition 2.1 where (A, B) = (Ajacs Bjac).
Lemma 3.2 (Restatement of Lemma B.2). Suppose that C2 = Jin(K 1 7) < oc, then is (C)/2, (4C,)-1 -1) exponentially stable on the damped system VTGal over radius Tul (Bmn))/2)
7

---

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 of the initial state distribution Xo r Sd reduces the magnitude of the nonlinear remainder term fui- Hence, the nonlinear system smoothly approximates its Jacobian linearization. More precisely, we establish that the difference in gradients and costs between Jni(K 7)r) and Jin ( 7) decrease linearly with the radius r.
Proposition 3.3. Assume Jun (K 17) < cc. Then, for PK.y defined as in Eq. (2.4):
Ful a) Ifr < 29a1 Paal Top then Jni(K 7/; Jiin (K [7] S 8da, Pk: llop r.
b) r S 128mll 1 then, Ja(K y: Jia 1) I 48dg +
[Bllop)|lPkx>//
Lastly, because policy gradients on linear dynamical systems is robust to inexact gradient queries, show that for sufficiently small, rumning policy gradients Jul converges to controller which has performance close to the optimal controller for the LQR problem with dynamic matrices (Ajacs B. As noted previously, 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.
then use Lemma 3.2 to translate the performance of the
Theorem (Nonlinear Systems), Let Ma == max [P+] Jia (Ko [0)) The following state- ments are true regarding the discount annealing algorithm for nonlinear dynamical systems when T, is less than a fixed quantity that is poly(1/Mm), 1/11
Tnt Bm1)
a) Discount annealing returns a controller K which is (v/tr (8tr [P.)) -)-- exponentially stable over a radius r = Tul Tul (88mitr [P.]3)
b) If To < 1, the algorithm is guaranteed to halt whenever t is greater than 64tr log(1/o).
Furthermore, at each iteration t:
c) Policy gradients achieves the guarantee Eq. (2.2) using only poly (Mli, ||A] B|)ppp many queries to g-Grad(:, Jmll: 7)) long S is less than some fixed polynomial poly(M.)
|| |B
c) Let co denote universal constant. With probability 1 8, the noisy random search algorithm (see Figure 2) returns a discount factor 7 satiisfing Eq. (2.3) using at most co tr [P.]* log(1/5) queries to e-Eval(:; Jal(: (,rx)) for .01d.-
We note that while our theorem only guarantees that the controller stabilizing around a polyno- mially 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 random search algorithm to simplify the analysis.
Experiments
In this section, we evaluate the ability of the discount annealing algorithm stabilize simulated nonlinear system. Specifically, we consider the familiar cart-pole, with d= = 4 (positions and (horizontal force applied the cart). The goal is to
velocities of the cart and pole), and d, stabilize the system with the pole in the unstable 'upright' equilibrium position. For further details, including the precise dynamics, see Appendix D. The system was simulated in discrete-time with simple forward Fuler discretization, i.e., X++1 x, + T, where x, is given by the continuous time dynamics, and T, 0.05 (20Hz). Simulations were carried out PyTorc (Paszke et al., 2019] and run on a single GPU.

---

Table 1: Final region of attraction radius Trea as function of the initial state radius y used during training (discount annealing). We report the [min, max] values of Tro over 5 independent trials. The optimal LQR policy for the linearized system achieved froa 0.703 when applied to the nonlinear system. We also synthesized an Ho optimal controller for the linearized dynamics, which achieved mmm 0.506.
0.1
0.3
0.5
0.6
0.7
m'ma [0.702, 0.704]
[0.711, 0.713]
[0.727, 0.734]
[0.731, 0.744] [0.769, 0.777]
Setup. The discounted annealing algorithm of Figure was implemented as follows. In place of the true infinite horizon discounted cost Jni(K 7, in Eq. (C.4) we use finite horizon, finite sample Monte Carlo approximation as described in Appendix C,
JaiK (7) ~
1 J (K (0),
~ r
Here, _ (K) 7. Σ プドー x Qx, +u! RuG, is the length H, finite horizon cost of controller K in which the states evolve according to the v damped dynamics from Eq. (C.5) and u, = Kx,- We used N 5000 and H 1000 in our experiments. For the cost function, we used Q T, and R = T.. We compute unbiased approximations of the gradients using automatic differentiation on the finite horizon objective )
Instead of using SGD updates for policy gradients, we use Adam [Kingma and Ba, 2014] with a learning rate of 17 0.01/r. Furthermore, 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. 17, 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 To = 0.9 || A 122 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 stabilizing controller (that is, increase T/ to 1). ii) the maximum radius of the ball of initial conditions x r ddd for which discount annealing succeeds at stabilizing the system, and iii) the radius rrou 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 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 independent trials for each initial radius r E {0.1, 0.3, 0.5, 0.7) (giving 20 independent trials, in total) the algorithm never required more than 9 iterations to return stabilizing policy.
Concerning (ii), discount annealing reliably stabilized the system for r I 0.7. For r z 0.75, we observed trials in which the state of the damped system (y < 1) diverged infinity. For such 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 (ii), in Table we report the final radius Troa for the region of attraction of the final con- troller returned by discount anncaling 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.c. Tie r. Moreover, for each r > .1. the Tiee achieved by discount annealing is greater than the Tua = 0.703 achieved by the exact optimal LQR controller and the Frea 0.506 achieved by the exact optimal H.s controller for the system's 's Jacobian lin- earization (see Table 1). (The Hos 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 (LQQR and H.g control), find the optimal controller

---

for an idealized linearization of the dynamics. Indeed, there is evidence to support this hypothe- sis. In Figure presented in Appendix D, we plot the error pgpp(())) K (n:)ll between the policy pg (1t) returned by policy gradients, and the optimal LQR policy Ki (7t) for the (damped) linearized system, as a function of the discount factor "/t used in each iteration of the discount an- nealing algorithm. For small training radius, such as r = 0.05, Kpp(Tr) & Kin((r) for all % However, for larger radii (i.e r 0.7), we see that | (7x) - Kinn (*t)llz steadily increases as "Y
increases.
That is, as discount annealing increases the discount factor y and the closed-loop trajectories explore regions of the state space where the dynamics are increasingly nonlinear, K begins to diverge from Kin Moreover, at the conclusion of discount annealing Kj (1) achieves lower cost, namely [15.2, 15.4] vs [16.5, 16.8] (here [a, 6] denotes [min, max] over 5 trials) and larger Tma- namely [0.769, 0.777] vs [0.702, 0.703). than Kjjn 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].
Discussion
This works illustrates how one can provably stabilize a broad class of dynamical systems via simple model-free procedure based off policy gradients. In line with the simplicity and flexibility that have made model-free methods weak assumptions and with little knowledge of the underlying dynamics. Furthermore, we solve an open problem from previous work [Fazel al., 2018) and take 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.
popular in practice, our algorithm works under relatively
In particular, our theoretical analysis states that discount annealing returns a controller whose sta- bility properties are similar to those of the optimal LQR controller for the system's 's Jacobian lin- carization. We were therefore quite surprised when experiments, the resulting controller had a significantly better radius of attraction than the exact optimal LQR and Ho controllers for the lin- earization of the dynamics. It is an interesting and important direction for future work to gain a better understanding of exactly when and how model-fin fidee-free procedures ities of the system and improve upon these model-based baselines. Furthermore, for our analysis of nonlinear systems, require access damped system trajectories. It would be valuable to under- stand whether this is indeed necessary or whether our analysis could be extended to work without access damped trajectories.
adaptive to the nonlinear-
As a final note, in this work we reduce the problem of stabilizing dynamical systems to running policy gradients for simplicity to leverage previous analyses. However, is possible that overall performance could be improved if rather than reducing LQR, we instead attempted 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.
discounted LQR objective. This choice of reducing to LQR was in part made
model-free method that
Acknowledgments
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-22111
10

---

References
Yasin Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference Learning Theory, pages 1-26, 2011.
OpenAl: Marcin Andrychowicz, Bowen Baker, Macick Chociej, Rafal Jozefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, al. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 39(1):3-20, 2020.
Frank M Callier and Charles Desoer. Linear system theory. Springer Science & Business Media, 2012.
Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Conference Learning Theory, pages 1114-1143 143. PMIR, 2021.
Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only sqr((t) regret. In International Conference on Machine Learning, pages 1300-1309, PMLR, 2019.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, pages 4188-4199 2018.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample com- plexity of the linear quadratic regulator. Foundations of Computational Mathematics, pages 1-47, 2019.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Finite-time adap- tive stabilization of linear systems. IEEE Transactions on Automatic Control, 6448):3498-3555 2018a.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. On optimality of adaptive linear-quadratic regulators. arXiv preprint urXiv:1806.10749 2018b.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Randomized al- gorithms for data-driven stabilization of stochastic linear systems. In 2019 IEEE Data Science Workshop (DSW), pages 170-174. IEEE, 2019.
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradi- ent methods for the linear quadratic regulator. In International Conference on Machine Learning, pages 1467-1476. PMLR, 2018
Han Feng and Javad Lavaci. Escaping locally optimal decentralized control polices via damping. In 2020 American Control Conference (ACC), pages 50-57. IEEE, 2020.
Claude-Nicolas Fiechter. Pac adaptive control of linear systems. In Proceedings of the tenth annual conference on Computational learning theory, pages 72-80, 1997.
Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. Proceedings of the Sixteenth Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, page 385-394, USA, 2005. Society for Industrial and Applied Mathematics.
Elad Hazan, Sham Kakade, and Karan Singh. The nonstochastic control problem. In Algorithmic Learning Theory, pages 408 421. PMLR, 2020.
Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey Motoya Ohnishi, and Wen Sun. Infor- mation theoretic regret bounds for online nonlinear control. In Advances in Neural Information Processing Systems, volume 33, pages 15312-15325. 2020.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization, arXiv preprint arXiv: 142.66442,,6900 2014.

---

Andrew Lamperski. Computing stabilizing linear controllers via policy iteration. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 1902-1907. IEEE, 2020.
Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selec- tion. Annals of Statistics, pages 1302-1333 1138,, 2000.
Frank L Lewis, Darren M Dawson, and Chaouki T Abdallah. Robot manipulator control: theory and practice. CRC Press, 2003.
Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter Bartlett, and Martin Wain- wright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2916-2925. PMLR, 2019.
Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. In Advances Neurul Information Processing Systems, pages 10154-10164, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 51 518(7540):5295533 2015.
Hesameddin Mohammadi, Mahdi Soltanolkotabi, and Mihailo Jovanović. On the linear conver- gence of random search for discrete-time lqr. IEEE Control Systems Letters, ((3):989-994, 2020.
Hesameddin Mohammadi, Armin Zare, Mahdi Soltanolkotabi, and Mihailo R Jovanovic. Conver- gence and sample complexity of gradient methods for the model-free linear quadratic regulator problem. IEEE Transactions on Automatic Control, 2021.
Pablo A Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical programming, 96(2):933-320 2003.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. arXiv preprint arXiv: 2019.
Xue Bin Peng, Marein Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 3803-3810, 2018, doi: 10.1109//CRA.201 246655
Juan C. Perdomo, Max Simehowitz, Alekh Agarwal, and Peter L. Bartlett. Towards a dimension- free understanding of adaptive linear control. In Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3681-3770. PMLR, 2021.
Stephen Prajna, Pablo A Parrilo, and Anders Rantzer. Nonlinear control synthesis by convex opti- mization. IEEE Transactions Automatic Control, 49(2):310-33 2004.
Guannan Qu, Chenkai Yu, Steven Low, and Adam Wierman. Combining model based and model- free methods for nonlinear control: A provably convergent policy gradient approach. arXiv preprint arXiv:2006.07476 2020.
Anders Rantzer. A dual to lyapunov's stability theorem. Systems & Control Letters, 42(3):161-168, 2001.
Shankar Sastry. Nonlinear systems: analysis, stability, and control, volume 10. Springer Science & Business Media, 2013.
Shankar Sastry and Marc Bodson. Adaptive control: stability, convergence and robustness. Courier Corporation, 201
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche,
Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. Nature, 529(7587)4884448) 2016.
Max Simchowitz and Dylan Foster. Naive exploration optimal for online lqr. In International Conference on Machine Learning, pages 8937-8948. PMLR, 2020.
12

---

Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
Eduardo Sontag. Nonlinear feedback stabilization revisited. Dynamical Systems, Control, Coding, Computer Vision, pages 223-262. Springer, 1999.
Eduardo D. Sontag. Stability and feedback stabiliizatio. Springer New York, New York, NY, 2009. doi: 10.10079775.0-888.3444033.33335
ISBN 978-0-380 778-0-387-30440-3
Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. In Conference on Learning Theory, pages 3036-3083, PMLR, 2019.
Kaiqing Zhang. Xiangyuan Zhang, Bin Hu, and Tamer Başar. Derivative- frree policy optimization for risk-sensitive and robust control design: implicit regularization and sample complexity. arXiv preprint arXiv:2 101.01041, 2021.
Kemin Zhou and John Comstock Doyle. Essentials of robust control, volume 104. Prentice Hall, 1998.
Kemin Zhou, John Comstock Doyle, Keith Glover, et al. Robust and optimal control, volume 40. Prentice hall New Jersey, 1996.
13


Reviews:
[{"review_id": "uRPSVuxg10X", "reviewer": "Reviewer_uRW9", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers an important problem, since many control methods require a stabilizing controller even when the system is unknown. Moreover, the paper leverages existing techniques but uses new insights to overcome the limitations of said techniques. The theoretical results appear to be correct but I wasn’t able to check all the details. \n\nHowever, the significance of the result can be strengthened by comparing with other stabilization methods for linear systems with similar access models. For example, “Finite-Time Adaptive Stabilization of Linear Systems” and “Randomized algorithms for data-driven stabilization of stochastic linear systems”  give algorithms for stabilization. How does this paper compare with the techniques used there? \n\nI’m also not completely convinced of model-free methods’ advantages over mode-based methods for linear systems, since linear systems don’t have arbitrary dynamics. \n\nSome limitations of the work:\nThe setting for linear systems assumes there is no noise, which is restrictive. Can the results be extended to accommodate stochastic noise?\nThe experimental section could be improved by including other, and possibly more difficult, tasks.\n\nPost rebuttal: I have read the authors' response, and will increase my score. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "_Dh2VFZe-PS", "reviewer": "Reviewer_YL9s", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: In my opinion, this paper is quite original and considers an important question. Stabilization is a fundamental question for control, and how to solve it via policy gradient is unclear. This paper makes progress in answering such an important question, and I can see there is unique contribution in this paper. \n\nReferences: This paper missed a large body of literature on policy optimization of linear control problems. The following papers are relevant, and the authors should discuss them.\n\n1. T. Rautert and E. W. Sachs, “Computational design of optimal output feedback controllers,” SIAM Journal on Optimization, 1997.\n\n2. K.M°artensson and A. Rantzer, “Gradient methods for iterative distributed control synthesis,” CDC, 2009.\n\n3. D. Malik, A. Pananjady, K. Bhatia, K. Khamaru, P. Bartlett, and M. Wainwright. \"Derivative-free methods for policy optimization: Guarantees for linear quadratic systems,\" AIstats, 2019.\n\n4. K. Zhang, B. Hu, and T. Basar, “Policy optimization for H2 linear control with H-infinity robustness guarantee: Implicit regularization and global convergence,” L4DC, 2020.\n\n5. L. Furieri, Y. Zheng, and M. Kamgarpour, “Learning the globally optimal distributed LQ regulator,” L4DC, 2020.\n\n6. J. P. Jansch-Porto, B. Hu, and G. Dullerud, “Convergence guarantees of policy optimization methods for Markovian jump linear systems,” ACC, 2020.\n\n7. B. Gravell, P. M. Esfahani, and T. Summers, “Learning optimal controllers for linear systems with multiplicative noise via policy gradient,” IEEE TAC, 2020.\n\n8. K. Zhang, B. Hu, and T. Basar, “On the stability and convergence of robust adversarial reinforcement learning: A case study on linear quadratic systems,” NeurIPS, 2020.\n\n9. I. Fatkhullin and B. Polyak, “Optimizing static linear feedback: Gradient method,” arXiv preprint arXiv:2004.09875, 2020.\n\n10. H. Mohammadi, M. Soltanolkotabi, and M. R. Jovanovic, “On the linear convergence of random search for discrete-time LQR,” IEEE Control Systems Letters, 2020.\n\n11. H. Mohammadi, A. Zare, M. Soltanolkotabi, and M. R. Jovanovic. \"Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem.\" IEEE TAC, 2021.\n\n12. Zheng, Y., Tang, Y. and Li, N. \"Analysis of the optimization landscape of linear quadratic Gaussian (LQG) control,\" L4DC, 2021\n\n13. Zhang, K., Zhang, X., Hu, B. and Başar, T. \"Derivative-free policy optimization for risk-sensitive and robust control design: Implicit regularization and sample complexity.\"  arXiv, 2021.\n\n\nQuality: This is a solid paper, although it is unclear how the authors draw the conclusion that their method improves the H-infinity control method. I have a few more questions here.\n1) How can the authors prove that gamma keeps increasing to 1 without approaching some limit point in the middle? I guess the proof will require some lower bound on how much progress on gamma can be made at each iteration. Is that true? Any uniform lower bound here?\n2) In the nonlinear setting, it seems that based on Lyapunov's indirect method, one can just linearize the dynamics and then stabilize the linear systems. Right? What is the point of developing new theory for \"local\" stabilization of nonlinear systems?\n3) Any evidence supporting the claim that the proposed approach is competitive with established robust control procedures? I mean, I can't find how the authors set up robust control baselines in their numerical study.\n4) For simulations, how does the proposed approach work on systems which have modes blowing up to infinity very quickly? In this case, although the theory states that a very small discount factor can be used such that the zero control gain lead to a finite cost, practically the system states in the simulations can blow up quickly to cause numerical issues, right? Can the authors provide an example on this?\n\nClarity: The paper is well written. The idea is quite clear.\n\nSignificance: I think the paper is significant in that it tries to answer a fundamental question with relatively simple ideas. In my opinion, such a solution for stabilization is novel and interesting. \n\n================\nPost-rebuttal: I am convinced to increase my score to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "I have not seen any such issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "V1SdqQc4sKh", "reviewer": "Reviewer_9Hp6", "summary": "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. \n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written and insightful. The proofs appear to be rigorous. However, as discussed below, the basic idea of using the discount factor for model-free stabilization has appeared independently in the literature. The proofs appear to be very different from the existing work, and the similarities appear to be coincidental. So, overall, this is nice work, the contribution feels a bit smaller as a result.\n\nA very similar model-free methodology has already been devised for computing stabilizing controllers and solving LQR in:\n\nLamperski, Andrew. \"Computing Stabilizing Linear Controllers via Policy Iteration.\" 2020 59th IEEE Conference on Decision and Control (CDC). IEEE, 2020.\n\nBoth are model free, and both interleave policy improvement steps with increases in the discount factor. Both give stabilizing controllers and converge to the LQR solution. \n\nThe prior work uses policy-iteration style updates in an off-policy manner. In particular, it can be used on a single trajectory or an offline data set. The current submission uses gradient evaluations, which effectively require restating the system for each new gradient. The current submission does give more explicit convergence bounds and gives applications to nonlinear systems.\n\nEdit based on Response: Based on the response, I can see greater merit and distinction in the work and I will raise my score appropriately.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed the limitations. I do not forsee any negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers find an interesting and important idea in this paper. Although some reviewers point out that the similar idea is found in some existing works, the authors clarify the significant difference or their work from those. As a total, this is a nice paper that could appear in NeurIPS. Therefore, my recommendation is acceptance (poster) for this paper.
Decision: Accept (Poster)