Global Convergence of Direct Policy Search for State-Feedback $\mathcal{H}_\infty$ Robust Control: A Revisit of Nonsmooth Synthesis with Goldstein Subdifferential
Authors: Xingang Guo
Bin Hu
Venue: NeurIPS 2022 Accept (2022)
Keywords: policy gradient
robust control
reinforcement learning
nonsmooth optimization

Abstract: Direct policy search has been widely applied in modern reinforcement learning and continuous control. However, the theoretical properties of direct policy search on nonsmooth robust control synthesis have not been fully understood. The optimal $\mathcal{H}_\infty$ control framework aims at designing a policy to minimize the closed-loop $\mathcal{H}_\infty$ norm, and is arguably the most fundamental robust control paradigm. In this work, we show that direct policy search is guaranteed to find the global solution of the robust $\mathcal{H}_\infty$ state-feedback control design problem. Notice that policy search for optimal $\mathcal{H}_\infty$ control leads to a constrained nonconvex nonsmooth optimization problem, where the nonconvex feasible set consists of all the policies stabilizing the closed-loop dynamics. We show that for this nonsmooth optimization problem, all Clarke stationary points are global minimum. Next, we identify the coerciveness of the closed-loop $\mathcal{H}_\infty$ objective function, and prove that all the sublevel sets of the resultant policy search problem are compact. Based on these properties, we show that Goldstein's subgradient method and its implementable variants can be guaranteed to stay in the nonconvex feasible set and eventually find the global optimal solution of the $\mathcal{H}_\infty$ state-feedback synthesis problem. Our work builds a new connection between nonconvex nonsmooth optimization theory and robust control, leading to an interesting global convergence result for direct policy search on optimal $\mathcal{H}_\infty$ synthesis.

Global Convergence of Direct Policy Search for State-Feedback Hx Robust Control: A Revisit of Nonsmooth Synthesis with Goldstein Subdifferential
Xingang Guo, Bin Hu
Department of Electrical and Computer Engineering Coordinated Science Laboratory University of Illinois at Urbana- Champaainn (xingang2, binhu7) @illinois..... edu
Abstract
Direct policy search has been widely applied in modern reinforcement learning and continuous control. However, the theoretical properties direct policy search on nonsmooth robust control synthesis have not been fully understood. The optimal Hos control framework aims at designing a policy to minimize the closed-loop Hox norm, and is arguably the most fundamental robust control paradigm. In this work, we show that direct policy search is guaranteed to find the global solution of the robust Hoo stae-feedbbcck control design problem. Notice that policy search for optimal Hox control leads to constrained nonconvex nonsmooth optimization problem, where the nonconvex feasible set consists of all the policies stabilizing the closed-loop dynamics. We show that for this nonsmooth optimization problem, all Clarke stationary points are global minimum. Next, we identify the coerciveness the closed-loop No objective function, and prove that all the sublevel sets the resultant policy search problem compact. Based on these properties, we show that Goldstein's 's subgradient method and its implementable variants can be guaranteed to stay in the nonconvex feasible and eventually find the global optimal solution of the Hox state-feedback synthesis problem. Our work builds a connection between nonconvex nonsmooth optimization theory and robust control, leading to an interesting global convergence result for direct policy search on optimal Hos synthesis.
1 Introduction
Reinforcement learning (RL) has achieved impressive performance on many continuous control tasks [59, 40]. and policy optimization is one of the main workhorses for such applications [18, 65, 58, 60]. Recently, there have been extensive research efforts studying the global convergence properties of policy optimization methods on benchmark control problems including linear quadratic regulator (LQR) [21, 41, 70, 44, 22, 29], stabilization [52, 51], linear cobust/risk-sensiinn
control [73, 72, 26, 74, 75, 12], Markov jump linear quadratic control [32, 31, 33. 55], Lur's e system control [53], output feedback control [20, 77, 39, 17, 16, 43, 76], and dynamic filtering [68]. For all these benchmark problems, the objective function in the policy optimization formulation is always differentiable the entire feasible set, and the existing convergence theory heavily relies on this fact. Consequently, important open question remains whether direct policy search can enjoy similar global convergence properties when applied to the famous Hoo control problem whose objective function can be non- differentiable over certain points in the policy space [1-3, 28, 9, 13, 48]. Different from LQR which considers stochastic disturbance sequences, Hos control directly addresses the worst-case disturbance, and provides arguably the most fundamental robust control paradigm [78, 19, 62, 4, 15, 23). Regarding
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the connection with RL, it has also been shown that H.x control can be applied to stabilize the training of adversarial RL schemes in the linear quadratic setup [72, Section 5J. Given the fundamental importance of Hos control, we view it as an important benchmark for understanding the theoretical properties of direct policy search in the context of robust control and adversarial RI.. In this work, we study and prove the global convergence properties of direct policy search on the Ho state-feedback synthesis problem.
The objective of the H.s state-feedback synthesis is to design a linear state-feedback policy that stabilizes the closed-loop system and minimizes the 3o norm from the disturbance to a performance signal at the same time. The design goal is also equivalent to synthesizing state-feedback policy that minimizes a quadratic cost subject to the worst-case disturbance. We will present the problem formulation for the Ho state-feedback synthesis and discuss such connections in Section 2. Essentially, Hos state-feedback synthesis can be formulated as a constrained policy optimization problem minkex JKK,, where the decision variable K is matrix parameterizing the linear state- feedback policy, the objective function J(K) is the closed-loop Hox-norm for given K, and the feasible set 'C consists of all the linear state-feedback policies stabilizing the closed-loop dynamics. Notice that the feasible set for the H.x state-feedback control problem is the same as the nonconvex feasible set for the LQR policy search problem [21, 7]. However, the objective function J ((K) for the His control problem can be non-differential over certain feasible points, introducing new difficulty to direct policy search. There has been large family of nonsmooth Hoc policy search algorithms developed based on the concept of Clarke subdifferential [1-3, 28, 9, 13]. However, a satisfying global convergence theory is still missing from the literature. Our paper bridges this gap by making the following two contributions.
1. We show that all Clarke stationary points for the H. state-feedback policy search problem are also global minimum.
2. We identify the coerciveness of the Hos cost function and use this property to show that Goldstein's 's subgradient method [25] and its implementable variants [71, 14, 9, 10, 37, 38] can be guaranteed to stay in the nonconvex feasible set of stabilizing policies during the optimization process and eventually find the global optimal solution of the Hos state- feedback control problem. Finite-time complexity bounds for finding (6, -)sttioionyyy points are also provided.
Our work sheds new light on the theoretical properties of policy optimization methods on Hos control problems, and serves meaningful initial step towards a general global convergence theory of direct policy search on nonsmooth robust control synthesis.
Finally, it is worth clarifying the differences between Hos control and mixed H2/Hoo design. For mixed H2/ Hoo. control, the objective is to design a stabilizing policy that minimizes an Hz performance bound and satisfies an H.x constraint at the same time [24, 36, 34, 47). In other words, mixed H2/ /Hoo control aims at improving the average H2 performance while "maintaining" certain level of robustness by keeping the closed-loop -lop Hos norm to be smaller than pre-specified number. In contrast, Hos control aims at "improving" the system robustness and the worst-case performance via achieving the smallest closed-loop Hox norm. In [73], it has been shown that the natural policy gradient method initialized from a policy satisfying the Ho constraint can be guaranteed to maintain the Ho0 requirement during the optimization process and eventually converge to the optimal solution of the mixed design problem. However, notice that the objective function for the mixed H2/ HooHo control problem is still differentiable over all the feasible points, and hence the amalysis technique in [73] cannot be applied to our Hox control setting. More discussions on the connections and differences between these two problems will be given in the supplementary material.
2 Problem Formulation and Preliminaries
2.1 Notation
The set of p-dimensional real vectors is denoted as IR.. For a matrix A, we use the notation AT, ||]]] Ir A, Gmin (A), ||A and p(AA) to denote its transpose, largest singular value, trace, smallest singular value, Frobenius norm, and spectral radius, respectively. When a matrix P is negative semidefinite (definite), we will use the notation P < (-)0. When P positive semidefinite (definite), we use the notation P = (=)0. Consider a (real) sequence == {wo, "1,...} where u, E 1 for all t. This

---

sequence is said to be in Ennh if Et= ||ull oo where ||u, || denotes the standard (vector) 2- 2-norm
of ur In addition, the 2-norm for u E lg is defined as ||||² :=
||
2.2 Problem statement: Hx state-feedback synthesis and a policy optimization formulation
We consider the following linear time-invariant (LTT) system
Ft+1 AAx + Bu Wt, To =
(1)
where 2t R is the state, Ur E RT is the control action, and w, Rn= is the disturbance. We have A E x=x,, B E I X*t, and nww = Rgg We denote x := {2o, Z1, ... J. u: {uo. "1.-.. }. and := {wo: "....... The initial condition is fixed as Zg O. The objective of Hos control is to choose { to minimize the quadratic cost Ei=o( [x]]Q=: + u, Ru,) in the presence of the worst-case E disturbance satisfying ||w|| S 1. In this paper, the following assumption is adopted.
Assumption 1. The matrices Q and are positive definite. The matrix pair (A, B) is stabilizable.
In Hos control, fwe? is considered to be the worst-case disturbance satisfying the & norm bound ||w|| S 1, and can be chosen in an adversarial manner. This is different from LQR which makes stochastic assumptions on { [wa)- Without loss of generality, we have chosen the &g upper bound on w to be 1. In principle, we can formulate the Hoc control problem with any arbitrary & upper bound on w, and there is no technical difference. We will provide more explanations on this fact in the supplementary material. Therefore, Hox control can be formulated the following minimax problem
min w:| WI
(o.TQee Qu: u Rua)
Under Assumption it is well known that the optimal solution for (2) can be achieved using a linear state-feedback policy u, = - -Kæ, (see [4]). Given any K, the LTI system (1) can be rewritten as
Fe+1 (A - BK) a + We, Do 0.
Now we define 2, = (Q + (K) We have || 12 = (Q K RK) = + uf Ruy- We denote z = [20, ..... If E Ey then we have ||
xx7
Et= (x] Qu: + u/ Ru,) < +oo. Therefore, the closed-loop LTT system (3) can be viewed as a linear operator mapping any disturbance sequence }w,} to another sequence } We denote this operator as Gk. where the subscript highlights the dependence of this operator on K. If is stabilizing, i.e. p(A BK) < 1, then Gx is bounded in the sense that it maps any l2 sequence w to another sequence z in l For any stabilizing K, the le - f2 induced norm of GR can be defined as:
|z
GKIla-22 = sup
(4)
[ ||w|]
Since GK is a linear operator, it is straightforward to show
2
|| 11 =
IT(Q+KTRK)E =
Σ
[T[aa + ut Rut).
max w:|lw SI
max w:|lw SI
Therefore, the minimax optimization problem (2) can be rewritten as the policy optimization problem: minkek | 1 where K. is the set of all linear state-feedback stabilizing policies, i.e. K. {K E XR, : p(A - BK) < J.. In the robust control literature [1-3, 28, 9, 13), is standard to drop the square in the cost function and just reformulate (2) as min exc G 1xl1--22 This is exactly the policy optimization formulation for Hg state- feedbffc control. The main reason why this problem is termed as Hoo state-feedback control is that in the frequency domain, Gx can be viewed function which lives in the Hardy Hos space and has an Ho0 norm being exactly equal to |[ 1|2-22 Applying the frequency-domat
transfer
formula for the Hox norm, we can calculate ||Gx 112-22 as
(Q + || 122-2222 = sup 11/2 ((e (c--3=I - - K RK) - A BK) (5)
where / is the identity matrix, and Amax denotes the largest eigenvalue of a given symmetric matrix. Therefore, eventually the Hos state-feedback control problem can be formulated as
min J(K),
(6)
Kek
3

---

where J(K) is equal to the Hoc norm specified by (5). Classical Mo control theory typically solves (6) via introducing extra Lyapunov variables and reparameterizing the problem into a higher- dimensional convex domain over which convex optimization algorithms can be applied [78, 19, 6]. In this paper, we revisit (6) as a benchmark for direct policy search, and discuss how to search the optimal solution of (6) in the policy space directly. Applying direct policy search to address (6) leads to a nonconvex nonsmooth optimization problem. A main technical challenge is that the objective function (5) can be non-differentiable over some important feasible points [1-3, 28, 9, 13].
2.3 Direct policy search: A nonsmooth optimization perspective
Now we briefly review several key facts known for the Hoc policy optimization problem (6). Proposition 1.
The set K. = {K: p(A - BK) < 1] is open. In general, it can be unbounded and nonconvex. The cost function (5) continuous and nonconvex K.
See [21, 8] for some related proofs. We have also included more explanations in the supplementary material. An immediate consequence is that (6) becomes a nonconvex optimization problem. Another important fact is that the objective function (5) is also nonsmooth. As matter of fact, (5) is subject to two sources of nonsmoothness. Based on (5), we can see that the largest eigenvalue for a fixed frequency w is nonsmooth, and the optimization step over w [0, 2n] is also nonsmooth. As matter of fact, the Hos objective function (5) can be non non-differentiable over important feasible points, e.g. optimal points. Fortunately, is well known' that the H.s objective function (5) has the following desired property so it is Clarke subdifferentiable.
The 2. objective functioon (5) is locally Lipschitz and subdifferentially regular over the stabilizing feasible set K.
Proposition 2.
Recall that K R is locally Lipschitz if for any bounded S C K., there exists constant L > 0 such that [J(K) - J(K)] < L||K- 1 la2 for all K, K' E S. Based on Rademacher's 's theorem, a locally Lipschitz function is differentiable almost everywhere, and the Clarke subdifferential is well defined for all feasible points. Formally, the Clarke subdifferential is defined as
(K) == convt lim VJ(K.) K, + K, K; E dom(vV) C.J 1-000
(7)
where conv denotes the convex hull. Then we know that the Clarke subdifferential for the Hos. objective function (5) is well defined for all K E K. We say that K is a Clarke stationary point if 0 E (KK). The following fact is also well known.
Proposition 3. If K is local min of J, then 0 E (K) and K is Clarke stationary point.
Under Assumption 1, it is well known that there exists K' IC achieving the minimum of (6). Since K' is an open set, K has to be an interior point of K and hence K* has to be a Clarke stationary point. In Section 3, we will prove that any Clarke stationary points for (6) are actually global minimum.
Now we briefly elaborate on the subdifferentially regular property stated in Proposition 2. For any given direction d (which has the same dimension as K), the generalized Clarke directional derivative of J is defined as
J(K' + (d) - J(K')
JKK, = Iim sup K' 0
(8)
In contrast, the (ordinary) directional derivative is defined as follows (when existing)
J(K + tcl J(K)
J'(K,d) = lim 250
t
Wee cannot find a formal statement of Proposition 2 in the literature. However, based on our discussion with other researchers who have worked on nonsmooth Hos synthesis for long time, this fact is well known and hence do claim any credits in deriving this result. As matter of fact, although not explicitly stated, the proof of Proposition is hinted in the last paragraph of [2, Section III] given the facts that the Has norm is a convex function over the Hardy How space (which a Banach space) and the mapping from K E K to the Proposition 2 based Clarke's chain rule [11] is included in the supplementary material.
Hardy Hox space is strietly differentiable. For completeness. simple proof of

---

In general, the Clarke directional derivative can be different from the (ordinary) directional derivative. Sometimes the ordinary directional derivative may not even exist. The objective function J (K) is subdifferentially regular if for every K E K. the ordinary directional derivative always exists and coincides with the generalized one for every direction, i.e. J'(K, d) = (K,KK) The most important consequence of the subdifferentially regular property is given follows.
Corollary 1. Suppose K' E K. is a Clarke stationary point for J. If J is subdifferentially regular, then the directional derivatives J' J'(K), d) are non-negative for all d.
See [56, Theorem 10.1] for related proofs and more discussions. Notice that having non-negative directional derivatives does not mean that the point Ktt is local minimum. Nevertheless, the above fact will be used in our main theoretical developments. Now we briefly summarize two key difficulties establishing a global convergence theory for direct policy search on the H.s state-feedback control problem (6). First, it is unclear whether the direct policy search method will get stuck at some local minimum. Second,
challenging to guarantee the direct policy search method to stay in the nonconvex feasible set K. during the optimization process. Since K. is nonconvex, we cannot use projection step to maintain feasibility. Our main results will address these two issues.
2.4 Goldstein subdifferential
Generating a good descent direction for nonsmooth optimization is not trivial. Many nonsmooth optimization algorithms are based on the concept of Goldstein subdifferential [25]. Before proceeding to our main result, we briefly review this concept here.
Definition (Goldstein subdifferential). Suppose is locally Lipschitz. Given a point K E K. and parameter > the Goldstein subdifferential of K defined to be the following set
(K) conv (K
(10)
where BB (K) denotes the 5-ball around K. The above definition implicitly requires B&(K) C C.
Based on the above definition, one can further define the notion of (6, -tsttiionar A point K is said to be (8, e)-stationary if dist (0, (K)) S is well-known that the minimal norm element of the Goldstein subdifferential generates a good descent direction. This fact is stated as follows.
Proposition 4 ([25)). Let F be the minimal norm element in J₃) Suppose K - aF/[ E for any 0 5. Then we have
J(K - (K/1FF/ S J(K) F12.
(11)
The idea of Goldstein subdifferential has been used designing algorithms for nonsmooth Hox control [3. 28, 9, 13]. We will show that such policy search algorithms can be guaranteed to find the global minimum of (6). It is worth mentioning that there are other notions of enlarged subdifferential [2] which can lead to good descent directions for nonsmooth Hos synthesis. In this paper, we focus on the notion of Goldstein subdifferential and related policy search algorithms.
3 Optimization Landscape for Hoc State-Feedback Control
In this section, we investigate the optimization landscape of the Hos state-feedback policy search problem, and show that any Clarke stationary points of (6) are also global minimum. We start by showing the coerciveness of the Hos objective function (5).
Lemma 1. The Hos functionn J(K) defined by (5) is coercive over the set K. in the sense that for any sequence { C K. we huve J(Kt) - +oo, if either ||K|||2 - +00, or K converges to an element in the boundary OK.
Proof. We will only provide proof sketch here. A detailed proof is presented in the supplementary material. Suppose we have a sequence {K'} satisfying 12 + +oo. We can choose w
(wo, O, 0, ....... with ||l I| = and show J(K') 2 wof (Q + ( 2 Amin [R)] [ l Clearly, we have used the positive definiteness of R in the above derivation. Then by carefully
choosing wo. we can ensure J(K*) - +oo as | + +00. Next, we assume K + K E aK..
We have p(A BK) 1, and hence there exists some we such that (6dwo1- A + BK) becomes
5

---

singular. Then we can use the positive definiteness of Q to show J(K') > A X (
A + BK ||(e- A -
II)) 1 Notice Umin(e
A+ BK) - as + 00,
which implies ||(e=joo - A 1| + +oo as l + oo. Therefore, have J(KK) +00 as
K' + K OK. More details for the proof can be found in the supplementary material.
We want to emphasize that the positive definiteness of (Q, R) are crucial for proving the coerciveness of the cost function (5). Built upon Lemma 1, we can obtain the following nice properties of the sublevel sets of (6).
Lemma 2. Consider the Has state ftede-feedback policy search problem (6) with the objective function
J (K) defined in (5). Under Assumption I, the sublevel set defined as K. == {K E K. J(K) S 7} is compuct and path-connected for every y 2 J(K)) where K is the global minimum of (6).
Proof. The compactness of K,,, directly follows from the continuity and coerciveness of J(K., and is actually a consequence of [5, Proposition 11.12). The path-connectedness of the strict sublevel sets for the continuous-time Ho control problem has been proved in [30]. We can slightly modify the proof in [30] to show that the strict sublevel set {K E KC J(K < 7 is path-connected. Based on the fact that every non-strict sublevel sets are compact, now we can apply [42, Theorem 5.2] to show
Kc, is also path conneeconeeted. An independent proof based on the non-strict version of the bounded real lemma is also provided in the supplementary material.
The path-connectedness of K,, for every y actually implies the uniqueness of the minimizing set in a certain strong sense [42, Sections 2&3]. Due to the space limit, we will defer the discussion on the uniqueness of the minimizing set the supplementary material. Here, we present a stronger result which is one of the main contributions of our paper.
Theorem 1. Consider the Hox state-feedback policy search problem (6). Under Assumption 1, any Clarke stationary point of J( J(K) is a global minimum.
detailed proof is presented in the supplementary material. Here we provide a proof sketch. Since Q and R are positive definite. the non-strict version of the bounded real lemma" states that (K) < y if and only if there exists a positive definite matrix P such that the following matrix inequality holds
[A- (1-BK)TP(A- - BK)-K P (A - (-BK)PP) P
+ Q [Q
10+KY KTRKRR 0
0 0 00 (12) -721
The above matrix inequality is linear in P but not linear in K. A standard trick from the control theory can be combined with the Schur complement lemma to convert the above matrix incquality condition to another condition which is linear in all the decision variables [6]. Specifically, there exists matrix function LMI(Y, L, 7) which is linear in (Y, 7) such that LMI(Y, L, 7) = 0 and Y > if and only if (12) is feasible with K LY and P = -Y-13 > O. The matrix function LMI(Y, L, 7) involves a larger matrix. Hence we present the analytical formula of LMI(Y, L, in the supplementary material and skip it here. Since LMI(Y, L,7) is linear in (Y, L,7,) we know LMI(Y, L, 7) < is just a convex semidefinite programming condition. Based on this convex necessary and sufficient condition for J(K) S 7, we can prove the following important lemma.
Lemma 3. For any K E KC satisfying J(K)= J", there exists matrix direction d + 0 such that J'(K,d) S - (KK < O, where J = [(K) and K is the global minimum of (6).
Proof. Suppose we have K = LY where ((K) is a feasible point for the convex regime LMI(Y, L, ((K) 3 O. In addition, we have K* = -Y+ where (Y" L" J(K")) is a point satisfying LMI(Y*, L (J(K)) << O. Since the LMI condition is convex, the line segment between (Y, ((K)) and "",
also in this convex set. For any > O we know (Y + tAY, L+
ALL.((K + t(J(K*) - -(K)) also satisfies LMI(Y + +tAY L + J + {(J(K)- J(K))) 3 O, where AL = L L., and AY y Y. Therefore, based on the bounded
'The difference between the strict and non nor-strict versions of the bounded real lemma is quite subtle [6. Section 2.7.3]. For completeness, we will provide more explanations for the non-strict version of the bounded real lemma in the supplementary material.

---

real lemma, we know J[(L + EY + +TAr) S J(K) + =(J((K) J(K)). Let's choose
ALY LY- AYY Then we have
+( +1AY)-
o(()) S - < 0.
J' < lim t
A detailed verification of the above inequality is provided in the supplementary material. Notice * O. If ALY-1 LY AVY-1 0, the above argument still works and we reach to the conclusion J'(K, 0) < O. But this is impossible since we always have J' 0) = 0. Hence we have of This completes the proof for this lemma.
Now are ready to provide the proof for Theorem 1. Based on Lemma 3 and the fact that J(.) is subdifferentially regular, the proof can be done by contradiction. Suppose K is the global minimum, and Kt is Clarke stationary point. If Ktt is not a global minimum. Then by Lemma 3, there exists ( d) 2 for all by Corollary 1. + 0 such that (K*, d) < 0, this contradicts the fact that J'(KT, Therefore, Ktt has to be the global minimum of (6).
The above proof relies on Lemma 3 and the fact that J is subdifferentially regular. Without using the subdifferentially regular property, Lemma itself not sufficient for proving Theorem 1. is also worth mentioning that Lemma 3 can be viewed as modification of the convex parameterizatioo//iitng results in [64, 68) for non-differentiable points.
4 Global Convergence of Direct Policy Search on Hox State-Feedback Control
In this section, we first show that Goldstein's 's subgradient method [25] can be guaranteed to stay in the nonconvex feasible regime X during the optimization process and eventually converge to the global minimum of (6). The complexity of finding (ō, c)-stationary points of (6) is also presented. Then we further discuss the convergence guarantees for various implementable forms of Goldstein's subgradient method.
4.1 Global convergence and complexity of Goldstein's 's subgradient Method
We will investigate the global convergence of Goldstein's 's subgradient method for direct policy search of the optimal Ho state-feedback policy. Goldstein's 's subgradient method iterates as follows
k = K" - F0""FFF/ll F|
(13)
where F" the minimum norm element of the Goldstein subdifferential ((K)). We assume that an initial stabilizing policy is available, i.e. K K. The same initial policy assumption has also been made in the global convergence theory for direct policy search on LQR [21]. More recently, some provable guarantees have been obtained for finding such stabilizing policies via direct policy search [52, 51J. Hence such an assumption on the initial policy K" is reasonable. Our global convergence result relies on the fact that there is a strict separation between any sublevel set of (6) and the boundary of IC. This fact is formalized as follows.
Lemma 4, Consider the Hox state State-feedback policy search problem (6) with the cost function ((K) defined in (5). Denote the complement of the feasible set KC as Kc Suppose Assumption holds and 2 J Then there is a strict separation between the sublevel set K.,, and KC In other words, we O.
have (ky,
Proof. Obviously, the set K., n KC' is empty (since we know K. C K.). Based on Lemma 2, we know K., is compact. Since IC is open, we know K is closed. Therefore, there is strict separation between K,, and ICS, and we have dist(K,, K*) > 0.
Now we are ready to present our main convergence result.
Theorem Consider the Hos state-feedback policy search problem (6) with the cost cost function J (K) defined in (5). Suppose Assumption holds, and an initial stabilizing policy is given, i.e. K E K. Denote Au == j(( K.) > O. Choose 8" cDo
=+11 for all with being a fixed number in
(0, 1). Then Goldstein's subgradient method (13) guaranteed to stay in K. all n. In addition, we have J [K") - J +
7

---

Proof. We have 8 S cAo < Do for all n. Now we use an induction proof to show K" E []((K)) for all n. For n 0, we know K F0 /1 122 has to be within the Ao ball around K since we know the norm of F /||4=112 112
> O, we know K 50 30 /|| E K. As a matter of fact, we know 30 (K*) has to be a subset of K. Hence we can apply (11) to show that K' exists and is also in Jo(oo Similarly, we can repeat this argument to show K" E KJ(Ko) for all n. Next, we can apply (11) to every step and then sum the inequalities over all n. Then the following inequality holds for all N:
is exactly equal to 1. Since Do == dist(K)(kk))
N
Σ
6 6, S J(K)) - J
(14)
Since we have En 8 +0G, we know lim nn | 2|2 - O. There exists one subsequence
{in} such that || ||2 O. For this subsequence, the resultant policy sequence {K*) } is also bounded (notice that the policy parameter sequence stays in the compact set K.J(Ko) for all n) and has convergent subsequence. We can show that the limit of this subsequence a Clarke stationary point. Hence the function value associated with this subsequence converges to J Notice that ((K) monotonically decreasing for the entire sequence {n). Hence we have J ((K") + J
We have tried to be brief in giving the above proof. We will present more detailed proof in the supplementary material. We believe that this is the first result showing that direct policy search can be guaranteed to converge to the global optimal solution of the Ho. stateffeedback control problem. The above result only provides an asymptotic convergence guarantee to ensure (KK) - J One similar argument to establish finite-time complexity bound for finding the (6, -stattooaryy points of (6). Such a result is given as follows.
Theorem 3. Consider the Hox problem (6) with the cost function (5). Suppose Assumption holds, and K K. Denote Do dist K39) > O. For any 8 < Ao, we can choose 8th 5 for all n to ensure that Goldstein's 's subgradient method (13) stays in K. and satisfies the following finite-ime complexity bound:
J(KD)-1 - J | 112 S
min MOSASN
(15)
(N + 115
In other words, we have m ||F" S c after N = = where A == J(K)) J For any 8 < Do and e >> 0, the complexity of finding (δ, -stattiony point is O (A)
Proof. The above result can be proved using similar argument from Theorem 2. We can use the same induction argument to show K" E KJ(koo for all n, and (14) holds with d" = 6. Then the desired conclusion directly follows.
The complexity for nonsmooth optimization of Lipschitz functions is quite subtle. While the above result gives a reasonable characterization of the finite-time performance of Goldstein's 's subgradient method on the H.w feedbbcc control problem, it does not quantify how fast J(K") converges to J'. Recall that (6, -)sttaiionay means dist(0, (0, JzJ (K)) < 6, while e-stationarity means dist(0, Jc.((K] (K))
As commented in [61, 71, 14], (6, -statiittiiy does not imply being 5-close to an c-stationary point of J. Importantly, the function value of a (5, c)-stationary point can be far from J even for small 5 and Theorem 5 in [71] shows that there is no finite time algorithm that can find e-stationary points provably for all Lipschitz functions. It is still possible that one can develop some finite time bounds for (J(K") J") via exploiting other advanced properties of the Hox cost function (5). This is an important future task.
4.2 Implementable variants and related convergence results
In practice, it can be difficult to evaluate the minimum norm element of the Goldstein subdifferential. Now diseuss implementable variants of Goldstein's 's subgradient method and related guarantees.
Gradient sampling [9, 10, 37]. The gradient sampling (GS) method the main optimization algorithm used in the robust control package HIFOO [3, 28). Suppose can access first-order
8

---

oracle which can evaluate V for any differentiable points in the feasible set'. Based on Rademacher's theorem, a locally Lipschitz function differentiable almost everywhere. Therefore, for any K K. we can randomly sample policy parameters over lBx- (K") ) and obtain differentiable points with probability one. For all these sampled differentiable points, the Clarke subdifferential each point just the gradient. Then the convex hull of these sampled gradients can be used as an approximation for the Goldstein subdifferential Ōz- K The minimum norm element from the convex hull of the sampled gradients can be solved via a simple convex quadratic program, and is sufficient for generating a reasonably good descent direction for updating k as long as we sample at least (n 1) differentiable points for each n [9]. In the unconstrained setup, the cluster points of the GS algorithm can be guaranteed to be Clarke stationary [37. 9]. Such a result can be combined with Theorem 1 and Lemma 4 to show the global convergence of the GS method on the Ho state state-feedbad feedback synthesis problem. The following theorem will be treated formally in the supplementary material.
Theorem 4 (Informal statement), Consider the policy optimization problem (6) with the Hos cost function defined in (5). Suppose Assumption 1 holds, and K K. The iterations generated from the trust-region version of the GS method (described in [37, Section 4.2] and restated in the supplementary material) can be guaranteed to stay in for all iterations and achieve ((K)) J with probability one.
Non-derivative sampling (NS) [38]. The NS method can be viewed as the derivative-free version of the GS algorithm. Suppose we only have the zeroth-order oracle which can evaluate the function value JK) for K E K. The main difference between NS and GS is that the NS algorithm relies on estimating the gradient from function values via Gupal's estimation method. In the unconstrained setting, the cluster points of the NS method can be guaranteed to be Clarke stationary with probability one [38, Theorem 3.8]. We can combine [38, Theorem 3.8] with our results (Theorem and Lemma 4) to prove the global convergence of NS in our setting, A detailed discussion is given in the supplementary material.
Model-free implementation of NS. When the system model is unknown, there are various methods available for estimating the -nom from data [45, 46, 57, 54, 69, 50, 67, 66). Based on our own experiences/tesss, the multi-input multi-output (MIMO) power iteration method [49] works quite well as stochastic zeroth- oracle for the purpose of implementing NS in the model-free setting. While the sample complexity for model-free NS is unknown, we will provide some numerical justifications to show that such model-free implementation closely tracks the convergence behaviors of its model-based counterpart.
Interpolated normalized gradient descent (INGD) with finite-time complexity. No finite- time guarantees for finding (6, -sstaiionnr points have been reported for the GS/NS methods. In [71, 14], the INGD method has been developed as another implementable variant of Goldstein's 's subgradient method, and is proved to satisfy high-probabile stationary points of Lipschitz functions. INGD uses an iterative sampling strategy to generate a descent direction which serves a role similar to the minimal norm element of the Goldstein subdifferential. A first-order oracle for differentiable points is needed for implementing the version of INGD in [14]. It has been show [71, 14] that for unconstrained nonsmooth optimization of T-Lipschitz functions*, the INGD algorithm can be guaranteed to find the (b. ))-stationary point with
finite-time complexity bounds for finding (5, c)-
the probbabibbyyl iteration complexity O ( (Al) log( (og() where A := ((K)) - J is the initial function value gap, and p is the failure probability (i.e. the optimization succeeds with the probability (1-p)). We can combine the proofs for [14, Theorem 2.6] and Theorem 3 to obtain the following complexity result for our Hos setting. A formal treatment given the supplementary material.
Theorem 5 (Informal statement), Consider the policy optimization problem (6) with the Hog cost function defined in (5). Suppose Assumption I holds, and the initial policy is stabilizing, i.e. K E K.. Denote Do == dist (KK)KK)),K3 K?) x= > O, and let To be the Lipschitz constant of J(K) over the set K. For any 8 < Do, we can choose 5" = 8 for all n to ensure that the iterations of the INGD algorithm stay in K. almost surely, and find (5, (6,e))stationan point with the high-probability iteration complexity O ( AL2
23 log(pbe))
log( ( where p is the failure probability.
'When (A, BB is known, one can calculate the Hos gradient at differential points using the chain rule in [2]. More explanations can be found the supplementary material.
'We slightly abuse our notation by denoting the Lipschitz constant as L. Previously, we have used L to denote particular matrix used in the LMI formulation for Hos feedback synthesis.

---

0.85
0.25
0.2
Modell Bven
(11A) -3"/
10
0.15
0.1
0.1
10
40
100
30
50
70
Trerasions
Icecationn
Trarations
Figure 1: Simulation results. Left: The trajectory of relative error of GS, NS, INGD, and Model-free NS methods (16). Middle: The trajectory of relative optimality gap of 8 randomly generated cases for NS method. Right: The trajectory of Model-free NS method with more noisy oracle on (16).
5 Numerical Simulations
To support our theory, we provide some numerical simulations in this section. The left plot in Figure 1 shows that GS, NS, INGD, and model-free NS work well for the following example:
57
2 -1
0
Q = -1
A = - 1 1
B =
-1
R=1.
(16)
-1 2
For this example, we have J 7.3475. We initialize from K = [0.4931 -0.1368 -..2654].
which satisfies p(A - BK3) = 0.5756 < 1. The hyperparameter choices are detailed in the supplementary material. We can see that model-free NS closely tracks the trajectory of NS and works well. In the middle plot of Figure I, we test the NS method on randomly generated cases. We set A E 3333 to be I + where each element of & 33x3 is sampled uniformly from [0, 1). For B E 13x1 each element uniformly sampled from [0, 1]. We have Q = + ÇI E p with uniformly sampled from [0, 0.1]. and R IR uniformly sampled from [1, 1.5). For each experiment, the initial condition K3D E RR13 is also randomly sampled such that p(A BK < 1. The NS method converges globally for all the cases. In the right plot, focus the model-free setting for (16). We decrease the number of samples used in the Ho estimation and show how this increases the noise in the zeroth-order Hos oracle and worsens the convergence behaviors of the model-free NS method. Nevertheless, the model-free NS method tracks its model-based counterpart with enough samples. More numerical results be found in the supplementary material.
Conclusions and Future Work
In this paper, we developed the global convergence theory for direct policy search on the Hos state- feedback synthesis problem. Although the resultant policy optimization formulation is nonconvex and nonsmooth, we managed to show that any Clarke stationary points for this problem are actually global minimum, and the concept of Golstein subdifferential search algorithms which are guaranteed to converge to the global optimal solutions. The finite-time guarantees in this paper are developed only for finding (staatttay points. An important future task is to investigate the finite-time bounds for the optimality gap (i.e. J(K") JJ") as well as the sample complexity of direct policy search on model-free Hoc control. also of great interests to investigate the convergence properties of direct policy search in nonlinear/outpu--feedbba
be used build direct policy
settings".
Acknowledgments and Disclosure of Funding
This work is generously supported by the NSF award CAREER-20488 and the 2020 Amazon research award. The authors would like to thank Michael L.. Overton, Maryam Fazel, Yang Zheng, Peter Seiler, Geir Dullerud, Aaron Havens, Darioush Kevian, Kaiqing Zhang, Na Li, Mehran Mesbahi, Tamer Başar, Mihailo Jovanovic, and Javad Lavaei for the valuable discussions, as well as the helpful suggestions from the anonymous reviewers of Pe.
'Some discussions on possible extensions along this direction have been given in the supplementary material.
10

---

References
[1] P. Apkarian and D. Noll. Controller design via nonsmooth multidirectional search. SIAM Journal on Control and Optimization, 44(6):12331149,, 2006.
[2] P. Apkarian and Noll. Nonsmooth H.s synthesis. IEEE Transactions Automatic Control, 51(1):71 (11):71-86., 86, 2006.
[3] D. Arzelier, G. Deaconu, S. Gumussoy, and D. Henrion. H2 for HIFOO, In International Conference on Control and Optimization With Industrial Applications (COIA 2011), 2011.
[4] T. Bagar and P. Bernhard. H -Opttiaa Control and Related Minimax Design Problems. Birkhäuser, 2nd edition, 1995.
[5] H. H. Bauschke, P. L. Combettes, al. Convex analysis and monotone operator theory in Hilbert spaces. volume 408. Springer, 2011.
[6] S. Boyd, L. EI Ghaoui, E. Feron, and V. Balakrishnan. Linear Matrix Inequalities in System and Control Theory, volume 15 of Studies in Applied Mathematics. SIAM, 1994,
[7] J. Bu, A. Mesbahi, M. Fazel, and M. Meshahi. IQQ through the lens of first order methods: Discrete-time case. arXiv preprint arXiv: I 1907.08921, 2019.
[8] J. Bu, A. Mesbahi, and M. Mcsbahi. On topological and metrical properties of stabilizing feedback gains: the MIMO case. arXiv preprint arXiv:1904.0275:) 2019.
[9] J. V. Burke, F. E. Curtis, A. S. Lewis, M. L. Overton, and L. E. Simões. Gradient sampling methods for nonsmooth optimization. Numerical Nonsmooth Optimization, pages 201-225, 2020.
[10] J. V. Burke, A. S. Lewis, and M. L. Overton. A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM Journal on Optimization, 15(3):55--77, 2005.
[11] F. H. Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
[12] L., Cui and I., Molu, Mixed H2 / lq games for rohust policy optimization under unknown dynamics. arXiv preprint arXiv:2209.c. 04477, 2022.
[13] F. E. Curtis, T. Mitchell, and M. L. Overton. A BFGS-SQP method for nonsmooth, nonconvex, constrained optimization and its evaluation using relative minimization profiles. Optimization Methods and Software, 32(1):148-181, 2017.
[14] D. Davis, D. Drusvyatskiy, Y. Tat Lee, S. Padmanabhan, and G. Ye. A gradient sampling method with complexity guarantees for general Lipschitz functions. arXiv preprint urXiv:2112.06969, 2021.
[15] J. Doyle, K. Glover, P. Khargonekar, and B. Francis. State-space solutions to standard Hz and Hos control problems. IEEE Transactions Automatic Control, 34:831-844 847, 1989.
[16] J. Duan, W. Cao, Y. Zheng, and L. Zhao. On the optimization landscape of dynamical output feedback linear quadratic control. arXiv preprint arXiv:2201. 09598, 2022.
[17] J. Duan, J. Li, and L. Zhao. Optimization landscape of gradient descent for discrete- time static output feedback. arXiv preprint arXiv:2109. 13132. 2021.
[18] Y. Duan, X. Chen, R. Houthooft, J. Schulman, and P. Abbeel. Benchmarking deep reinforvement learning for continuous control. In International Conference on Machine Learning, pages 1329-1338. 2016.
[19] G. Dullerud and F. Paganini. A Course in Robust Control Theory: A Corvex Approuch. Springer, 1999.
[20] Fatkhullin and B. Polyak. Optimizing static linear feedback: Gradient method. SIAM Journal on Control and Optimization, (755)3387739111 2021.
[21] M. Fazel, R. Ge, S. Kakade, and M. Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 1467-1476, 2018.
[22] L. Furieri. Y. Zheng, and M. Kamgarpour Learning the globally optimal distributed LQ regulator. In Learning for Dynamics and Control, pages 287-297, 2020.
[23] P. Gahinet and P. Apkarian. A linear matrix inequality approach to Hox control. International Journal of Robust and Nonlinear Control, 4:421 148, 1994.

---

[24] K. Glover and J. C. Doyle. State-space formulae for all stabilizing controllers that satisfy an -ne-norm bound and relations relations to risk sensitivity. Systems & Control Letters, 11(3):167-172, 1988.
[25] A. Goldstein. Optimization of lipschitz continuous functions. Mathematical Programming, 13(1):14-22, 1977.
[26] B. Gravell, P. M. Esfahani, and T. Summers. Learning optimal controllers for linear systems with multiplicative noise via policy gradient. IEEE Transactions on Automatic Control, 66(1 1):2833-5298, 2020.
[27] P. Grohs and S. Hosseini. s-subgradient algorithms for locally Lipschitz functions Riemannian manifolds. Advances Computational Mathematics, pages 333-360 330,360,00 2016.
[28] S. Gumussoy, D. Henrion, M. Millstone, and M. I.. Overton. Multiobjective robust control with HIFOO
2.0. IFAC Proceedings Volumes, 42(6)) 144-149, 2009.
[29] B. Hambly, R. Xu, and H. Yang. Policy gradient methods for the noisy lincar quadratic regulator over a finite horizon. SIAM Journal Control and Optimization, 59(5):3359-33 1391, 2021.
[30] B. Hu and Y. Zheng. Connectivity of the feasible and sublevel sets of dynamic output feedhack control with robustness constraints. IEEE Control Systems Letters, 7:442 447, 2023.
[31] J. P. Pansch-Porto, B. Hu, and G. Dullcrud. Policy learning of MDPs with mixed continuous/discrete variables: A case study on model-free control of Markovian jump systems. In Learning for Dynamics and Control, pages 947-957, 2020.
[32] J. P. Jansch- Porto, B. Hu, and G. E. Dullerud. Convergence guarantees of policy optimization methods for Markovian jump linear systems. American Control Conference, pages 2882 2887, 2020.
[33] Jansch-Porto. B. Hu, and G. E. Dullerud. Policy optimization for Markovian jump linear quadratic control: Gradient method and global convergence. IEEE Transactions on Automatic Control, 2022.
[34] I. Kaminer, P. P. Khargonekar, and M. A. Rotea. Mixed Ha/Ho control for discrete-time systems via convex optimization. Automatica, 29(1):77-70, 1993.
[35] D. Keivan, A. Havens, P. Seiler, G. Dullerud, and B. Hu. Model-free synthesis via adversarial reinforcement learning. 2022 American Control Conference (ACC), pages 5335-3341, 2022.
[36] P. P. Khargonekar and M. A. Rotea. Mixed H2/H.e Hoc control: A convex optimization approach. IEEE Transactions on Automatic Control, 36(7):824-837, 1991.
[37] K. C. Kiwiel. Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM Journal on Optimization, 18(2)379-388, 2007.
[38] K. C. Kiwiel. A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM Journal on Optimization. 1064):1983-194 2010.
[39] Y. Li, Y. Tang, R. Zhang, and N. Li. Distributed reinforcement learning for decentralized linear quadratic control: A derivative-free policy optimization approach. IEEE Transactions on Automatic Control, 2021,
[40] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver. and D. Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: /5000029977, 2015.
[41] D. Malik, A. Pananjady, K. Bhatia, K. Khamaru, Bartlett, and M. Wainwright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. In International Conference on Artificial Intelligence and Statistics, pages
2019.
[42] D. H. Martin. Connected level sets, minimizing sets, and uniqueness in optimization. Journal of Optinization Theory and Applications, 36(1):71-91, 1982.
[43] H. Mohammadi, M. Soltanolkotabi, and M. R. Jovanovié. On the lack of gradient domination for linear quadratic gaussian problems with incomplete state information. 2021 60th IEEE Conference on Decision and Control (CDC), pages 1120-112 1124, 2021.
[44] 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 Transactions on Automatic Control, 2021.
12

---

[45] M. Müller and C. R. Rojas. Gain estimation of linear dynamical systems using thompson sampling. In The 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), volume 89, pages 1535-1543, 2019.
[46] M. I. Müller, P. F. Valenzuela, A. Proutiere, and C. R. Rojas. A stochastic multi-armed bandit approach to nonparametric -nom estimation. In IEFE 56th Annual Conference on Decision and Control, pages 4632-4637, 2017.
[47] D. Mustafa and D. Bernstein. LQG cost bounds in discrete-time Hz/ control. Transactions of the Institute of Measurement and Control, 13(5):269-2) 275, 1991.
[48] D. Noll and P. Apkarian. Spectral bundle methods for non-convex maximum eigenvalue functions: sccond-order methods. Mathematical Programming, 104())229-747, 2005.
[49] T. Oomen, R. van der Maas. C. R. Rojas, and H. Hjalmarsson. Iteratively learning the H.--norm of multivariable systems applied to model-errot-modeline of vibration isolation system. In 2013 American Control Conference, pages 6703-6708. IEEE, 2013.
[50] T. Oomen, R. van der Maas, C. R. Rojas, and H. Hjalmarsson. Iterative data-driven Hoc norm estimation of multivariable systems with application rohust active vihration isolation. IEEE Transactions on Control Systems Technology, (26))2247-226 2014.
[51] I. K. Ozaslan, H. Mohammadi, and M. R. Jovanović. Computing stabilizing feedback gains via model-free policy gradient method. IEEE Control Systems Letters, 7:407 412, 2022.
[52] J. Perdomo, J. Umenberger, and M. Simchowitz. Stabilizing dynamical systems via policy gradient methods. Advances Neural Information Processing Systems, 34, 2021.
[53] G. Qu, C. Yu, S. Low, and A. Wierman. Exploiting linear models for model-free nonlinear control: A provably convergent policy gradient approach. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 6539-6546, 2021.
[54] G. Rallo. S. Formentin, C. R. Rojas, T. Oomen, and S. M. Savaresi. Data-driven H..-noom estimation via expert advice. IEEE 56th Annual Conference on Decision and Control, pages 1560-1565, 2017.
[55] S. Rathod, M. Bhadu, and A. De. Global convergence using policy gradient methods for model-free markovian jump linear quadratic control. arXiv preprint arXiv:2111.15228, 2021.
[56] R. T. Rockafellar and R. J.BB. Wets. Variational analysis. volume 317. Springer Science & Business Media, 2009.
[57] C. R. Rojas, T. Oomen, H. Hjalmarsson, and B. Wahlberg. Analyzing iterations in identification with application to nonparametric Hoe -nom estimation. Automatica, (1761):77662790, 2012.
[58] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International Conference on Machine Learning, pages 1889-1897, 2015.
[59] Schulman, Moritz, S. Levine, M. Jordan, and P. Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:15066 150:.02436. 2015.
[60] Schulman, F. Wolski, Dhariwal, Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint (exXiv:/07..000 2017.
[61] O. Shamir. Can we find aaa-apppoximatelystatiiooo points of nonsmooth nonconvex functions? arXiv preprint arXiv:2002. 1962, 2020.
[62] S. Skogestad and I. Postlethwaite. Mulrivariable Feedback Control: Analysis and Design, volume 2. Wiley New York, 2007.
[63] S. Subramani. On suns of singular values. PhD thesis, The University of New South Wales Sydney, 1993.
[64] Y. Sun and M. Fazel. Leamning optimal controllers by policy gradient: Global optimality via convex parameterization. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 4576 45811, 2021.
[65] R. S. Sutton, D. A. McAllester, S. P. Singh, and Y. Mansour, Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, pages 1057-1063, 2000.
[66] S. Tu, R. Boczar, and B. Recht. On the approximation of toeplitz operators for nonparametric How noom estimation. In American Control Conference, pages 1867-1872, 2018
13

---

[67] S. Tu, R. Boczar, and B. Recht. Minimax lower bounds for -nom estimation. In American Control Conference, pages 3538-3543, 2019.
[68] J. Umenberger, M. Simchowitz, J. C. Perdomo, K. Zhang, and R. Tedrake. Globally convergent policy search over dynamic filters for output estimation. arXiv preprint arXiv:2202.11659, 2022.
[69] B. Wahlberg, M. B. Syberg, and H. Hjalmarsson. Non-parametric methods for 12-gain estimation using iterative experiments. Automatica, 1678)11376-1381 2010.
[70] 7. Yang, Y. Chen, M. Hong, and 7. Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. Advances in neural information processing systems, 32, 2019.
[71] J. Zhang. H. Lin, S. Jegelka, S. Sra, and A. Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In Proceedings of the 37th International Conference on Machine Learning, volume 119. pages 11173- 11182. PMLR, 2020.
[72] K. Zhang, B. Hu, and T. Başar. On the stability and convergence of robust adversarial reinforcement learning: A case study on linear quadratic systems. Advances in Neural Information Procexsing Systems, 33, 2020.
[73] K. Zhang, Hu, Basar. Policy optimization for Hz linear control with Hos robustness guarantee: Implicit regularization and global convergence. SIAM Journal on Control and Optimization, 59(6):4081- 4109, 2021.
[74] K. Zhang, X. Zhang, B. Hu, and T. Başar. Derivative-free policy optimization for linear risk-sensitive and robust control design: Implicit regularization and sample complexity. In Thitty-Fifth Conference on Neural Information Processing Systems, 2021.
[75] F. Zhao and K. You. Primal-dual learning for the model-free risk-constrained linear quadratic regulator. In Learning for Dynamics and Control, pages 702-77 702,714, 2021.
[76] Y. Zheng, Y. Sun, M. Fazel, and N. Li. Escaping high-order saddles in policy optimization for linear quadratic Gaussian (LQG) control. arXiv preprint arXiv:2204.00912, 2022.
[77] Y. Zheng, Y. Tang, and N. Li. Analysis of the optimization landscape of linear quadratic gaussian (LQG) control. arXiv preprint 2xxx:2102.00499) 2021.
[78] K. Zhou, J. Doyle, and K. Glover, Robust and Optimul Control. Prentice-Hall, 1996.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Our works only addresses the
Hoc state-feedback control problem. More study is needed for the partial observation case.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We do not believe that our current work will create any negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix in the supplementary material.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] Our code has been included in the supplementary material. We emphasize that the nature of our work is theoretical, and our code is only provided to demonstrate our theory.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "nj5nH57OG6", "reviewer": "Reviewer_fj7B", "summary": "The authors study direct policy optimization for finding the minimal $\\mathcal{H}_\\infty$-norm stabilizing controller. They prove various analytic properties about the landscape of policy optimization such that a Goldstein subdifferential method converges in function value to the global minimum. While the Goldstein subdifferential method can be difficult to implement, they also discuss various sampling based strategies for finding the minimum norm subdifferential.", "questions": "- As a point of clarification, is there a unique minimum $K^*$ for problem (6), or are there possibly many global minima? \n\n- Can the authors discuss the barriers to removing the $Q$ positive definite assumption and replacing it with a more standard $(A, Q^{1/2})$ is observable assumption?\n\n- For the proof of Theorem 1, I am curious why the first case assuming $J’(K^{\\dagger}, d) > 0$ is necessary. What is insufficient with the following argument: suppose $K^{\\dagger}$ is a Clarke stationary point, but $K^{\\dagger}$ is not a global minimum and hence $J(K^{\\dagger}) > J^*$. In this case, Lemma 3 guarantees the existence of $d \\neq 0$ such that $J’(K^{\\dagger}, d) < 0$. However, by the subdifferential regularity of $J$ (Proposition 2), we know that $J’(K^{\\dagger}, d) \\geq 0$ for all $d$, hence a contradiction. \n\n- Theorem 2: consider stating that $\\delta^n = \\frac{c \\Delta_0}{n+1}$ for some $c \\in (0, 1)$ instead of setting $c = 0.99$. The proof still goes through, but this would allow you to underestimate $\\Delta_0$.\n\n- Theorem 2: how do you compute (or estimate) $\\Delta_0$? \n\n- Theorem 2: Does $K^n \\rightarrow K_\\infty$ with $K_\\infty \\in \\mathcal{K}$? The theorem is a statement about the function values, but is it possible for the $K^n$’s to not converge? This is related to my question about uniqueness of $K^*$. \n\n- Theorem 2: Can one obtain a rate of convergence on $J(K^n) \\rightarrow J^*$?\n", "limitations": "Some limitations are already discussed in weaknesses. \n\nAlso, the authors point out that their work only applies to the full state observation case, with partial observability needing future work. This is not an issue for me, as I see the partial observability case as follow up work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- The paper is written very clearly and concisely. \n- The result is elegant. \n- The proofs are clean and read quite nicely.\n\n**Weaknesses:**\n\n- The main result is asymptotic (Theorem 2 does not give any rates of convergence). \n\n- It is acknowledged that computing the minimum norm subdifferential is challenging (see e.g. Line 317), but the sampling algorithms to address this are discussed mainly in the appendix. The authors present several implementation schemes, but it is not clear as a reader which one to prefer. \n\n- An end to end statement combining Theorem 2 and any one of the sampling schemes to give a result on a practical algorithm is not clearly stated in the paper (although can possibly be inferred from the discussion in Appendix C). \n\n- The algorithms listed in the appendix (Algorithm 1,2,3,4) all require function evaluations of the form $J(K)$, which involves computing the $\\mathcal{H}_\\infty$-norm of the system in feedback with a given $K$. Without access to the system dynamics $(A, B)$ (which is the whole point of studying policy search methods otherwise the $K^*$ can be computed via an SDP as noted in Lines 124-126), it is not clear how one computes $J(K)$, even with access to a simulator.\n\n- There are no experiments showing the effectiveness of the proposed algorithms.\n\n**Recommendation:**\n\nIn light of these weaknesses, I am not sure about the immediate impact/relevance of this paper beyond a small niche in the NeurIPS community. Nevertheless, it is a nice result from a mathematical point of view which in my opinion warrants an accept. The one caveat is that I am not that familiar with the nonsmooth optimization literature. Hence, while the results appear novel to me, if a reviewer who is more knowledgable in this area disagrees, then I would reconsider my recommendation based on said reviewer's arguments.\n\n**EDIT:** After reviewing the author's responses and draft, I raised my score from 6 to 7. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CLnAUlQttao", "reviewer": "Reviewer_Uf74", "summary": "This paper establishes asymptotic convergence for Goldstein's method for H-infinity policy search. On the plus side, it does so with elegant topological and optimization-theoretic arguments. A negative, however, is that the rates are non-quantitative, and it is not clear how the complexity of implementing the optimization would depend on problem parameters.", "questions": "1. Can the authors remark on the computational complexity of the sampling methods referred to in [49,13], and well as the zero-th order methods [9,10,31]? Do the authors conjecture that these methods could be implemented with samples scaling polynomially in relevant parameters?\n\n2. Is there a way to bound the minimal separation between K_0 and K, Delta_0, in terms of a more natural problem quantity?\n\n3. Can the argument of Theorem 2 be modified to given quantitative bounds for finite iterations?", "limitations": "As noted, the guarantees are non-quantitative and hence I am not sure if this is a good fit for NeurIPS. \n\nHowever, I can be convinced! - if the authors can show precedent for similarly qualitative optimization papers (or if my fellow reviewers can), then I will be inclined to increase my score because I did enjoy this paper. \n\nEDIT: After reviewing the author changes, most of my concerns regarding the computational infeasibility of finding approximate Goldstein differentials have been allayed. I am raising my review to a 7. I am tempted to give the paper an 8, but I am still concerned that the Delta_0 quantity is a little mysterious, and may hide nasty problem-dependent factors. Still the authors  should be proud of their excellent submission, I hope to see this in the program.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am torn about this paper; I thoroughly enjoyed reading it. I think it was excellently written, the proofs were clear and correct, and balanced concision with transparency perfectly. The fact that the results were purely qualitative made the paper easy and enjoyable to read. Were I asked to review this paper for an optimization or control journal, I would enthusiastically support acceptance. \n\nI think the weakness of this paper is that, the NeurIPS theory community comes out of the learning theory tradition, where one cares about finite sample/iteration rates that reflect how problem parameters reflect the complexity of solving a problem. For example, many of the main papers on policy search for H2 control stress polynomial dependence in dimension, norms / bounds on various problem parameters, and on desired accuracy. \n\nIn this paper, the rates are purely asymptotic. Moreover, the algorithm requires the computation of a minimal norm element Goldstein differential, which may potentially be computationally prohibitive, especially if it requires sampling arbitrarily adversarial non-convex functions. Therefore, it is unclear to me whether even a single step of the proposed algorithm can be implemented efficiency (say, where the number of samples is poly(d,e,log(1/delta)). I did appreciate the authors discussion of the various implementation choices, and that level of specificity may be appropriate for other communities. But I think that for NeurIPS the author must convince the reader that the algorithm can be implemented efficiently in the sense that it can be performed in number of iterations / sampling calls which are polynomial in relevant problem parameters.\n\nSimilarly, the final guarantee in Theorem 2 is asymptotic, not giving a sense of rates.\n\nEDIT: The authors have addressed the majority of my concerns, and I am increasing my score to a 7.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7-VS9gOtRuR", "reviewer": "Reviewer_HdMw", "summary": "This paper studies the optimization landscape of the H_inf control problem. It is shown that all Clarke stationary points are global minimal even though H_inf is nonconvex. Further, a  Goldstein subdifferential method is proposed and shown to stay in the nonconvex feasible set and eventually reach a global optimal solution.", "questions": "Please add some numerical evaluation.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "H_inf control is an important robust control problem and is worth being studied, especially from the learning perspective. The optimization landscape results in this paper are significant. The Goldstein subdifferential method can guarantee the iterated control policies to stay in the nonconvex feasible set and eventually reach a global optimal solution. Further, the limitations of the Goldstein subdifferential method is discussed and implementable variants are proposed.\n\nThe major weakness of this paper is that no numerical evaluation is provided.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2kxODQo1tMB", "reviewer": "Reviewer_5f2x", "summary": "This paper considers the problem of direct policy search in the optimal $\\mathcal{H}_\\infty$ control framework. $\\mathcal{H}_\\infty$ control is an important framework in the robust control literature, but the problem of finding the optimal controller is challenging because it is a constrained nonconvex nonsmooth optimization problem. In this paper, the authors first study the landscape of the optimization problem to show the existence of a unique global minimizing set and any Clarke stationary points are global minimum. Then, they show a direct policy search method, the Goldstein subdifferential method, can stay in the feasible set and find a global optimal state-feedback controller.", "questions": "I encourage the authors to add a more detailed discussion about the future directions of this work. Despite a more general convergence bound, it will also be interesting to see if the linear time-invariant system and the time-invariant quadratic cost functions considered here can be generalized to more general dynamics/costs.", "limitations": "The authors discussed a limitation when practically implementing their algorithm in the last section, and proposed several potential solutions. I do not see any potential negative social impacts of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: This paper makes a significant contribution to the interdisciplinary field of robust control and machine learning. Although similar results about the convergence of direct policy search exist in the literature of $\\mathcal{H}_2$ control and mixed $\\mathcal{H}_2/\\mathcal{H}_\\infty$ control, the authors discuss the difference between these settings clearly at the end of the Introduction. After reading the discussion, I believe the problem considered in this work is fundamental and challenging. This paper is also well-written and easy to follow in general.\n\nWeakness: In Section 4.2, the authors mentioned that the minimum norm element of the Goldstein subdifferential $F^n$ can be difficult to evaluate in practice. However, the convergence result in Theorem 2 does not consider the potential error/noises when evaluating $F^n$ and perform the update. Further, Theorem 2 only provides an asymptotic convergence guarantee rather than a finite time error bound. Since the page limit is 9 pages, some contents in the appendix (e.g., the algorithm to evaluate $F^n$) can be moved into the main body.\n\nIn conclusion, I feel the strength of this work outweighs its weakness. This work is a very meaningful initial step towards more general convergence results.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept