Complexity of Derivative-Free Policy Optimization for Structured $\mathcal{H}_\infty$ Control
Authors: Xingang Guo
Darioush Keivan
Geir Dullerud
Peter Seiler
Bin Hu
Venue: NeurIPS 2023 poster (2023)
Keywords: Structured $\mathcal{H}_\infty$ Control
Nonsmooth Optimization
Complexity Analysis
TL;DR: We establish the sample complexity of model-free policy optimization method on finding $(\delta, \epsilon)$-stationary points for structured $\mathcal{H}_\infty$ robust control problem.

Abstract: The applications of direct policy search in reinforcement learning and continuous control have received increasing attention.
In this work, we present novel theoretical results on the complexity of derivative-free policy optimization on an important class of robust control tasks, namely the structured $H_\infty$ synthesis with static output feedback. 
Optimal $H_\infty$ synthesis under structural constraints leads to a constrained nonconvex nonsmooth problem and is typically
addressed using subgradient-based policy search techniques that are built upon the concept of Goldstein subdifferential or other notions of enlarged subdifferential.  In this paper, we study the complexity of finding $(\delta,\epsilon)$-stationary points for such nonsmooth robust control design tasks using policy optimization methods which can only access the zeroth-order oracle (i.e. the $H_\infty$ norm of the closed-loop system). First, we study the exact oracle setting and identify the coerciveness of the cost function to prove high-probability feasibility/complexity bounds for derivative-free policy optimization on this problem. Next, we derive a sample complexity result for the multi-input multi-output (MIMO)  $H_\infty$-norm estimation. We combine this with our analysis to obtain the first sample complexity of model-free, trajectory-based, zeroth-order policy optimization on finding $(\delta,\epsilon)$-stationary points for structured $H_\infty$ control. 
Numerical results are also provided to demonstrate our theory.

Complexity of Derivative-Free Policy Optimization for Structured Hoo Control
Xingang Guo ECE, CSL UIUC
Darioush Keivan MSE, CSL UIUC dk120illinois. edu
singang2@illinois.co
Geir Dullerud
Peter Seiler EECS
Bin Hu ECE, CSL UIUC binhu7@@llinois. edu
MSE, CSL UIUC dullerud@illinois.. edu
UMich
pseiler@umich.edu
Abstract
The applications of direct policy search in reinforcement learning and continuous control have received increasing attention. In this work, we present novel theoretical results on the complexity of derivative-fres policy optimization class of robust control tasks, namely the structured N30 synthesis with static output feedback. Optimal Hos synthesis under structural constraints leads a constrained nonconvex nonsmooth problem and is typically addressed using subgradient-based policy search techniques that built upon the concept of Goldstein subdifferential or other notions of enlarged subdifferential. In this paper, we study the complexity of finding (6, -)statiionary points for such nonsmooth robust control design tasks using policy optimization methods which can only access the zeroth-order oracle (i.c. the Hoo norm of the closed-loop system). First, we study the exact oracle setting and identify the coerciveness of the cost function to prove high-pu probbabbbabiltt feasibility/compleitg bounds for derivative- free policy optimization on this problem. Next, we derive sample complexity result for the multi-input multi-output (MIMO) -nom estimation. We combine this with our analysis to obtain the first sample complexity of model-free, enjectory-based zeroth-order policy optimization on finding (6, -)ssttiionary points for structured Hox control. Numerical results are also provided to demonstrate our theory.
important
Introduction
Policy optimization techniques have received increasing attention due to their impressive performance reinforcement Learning (RL) and continuous control tasks [65, 48, 64, 45). Despite the empirical successes, the theoretical properties of policy-based RL methods have not been fully understood, even on relatively simple linear control benchmarks. This has motivated a line of recent work developing sample complexity theory of model-free policy optimization on benchmark linear control problems such as linear quadratic regulator (LQR) [22, 47, 72, 50, 24, 33], stabilization [57, 56], linear abbustrisk-sensitiie control [30, 76, 77]. Markov jump linear quadratic control [59], and distributed LQR [44]. These existing sample complexity results heavily rely on the fact that the cost functions in these benchmark problems differentiable over the entire feasible set, and hence cannot be applied to cover the H.s robust control setting where the objective function is nonsmooth in the first place
18). In this paper, make meaningful initial step bridge this gap by
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

developing a novel complexity theory for an important class of Mo robust control problems, namely the structured H. synthesis with static output feedback.
Hoe synthesis is arguably the most fundamental paradigm for robust control [80, 20). Therefore, is important understand the complexity of policy optimization on such problems. In this work, we will develop complexity theory for derivative-free policy optimization on the structured static output-feedback Hos synthesis problem [3]. Notice that this is an important class of Hoc control problems with practical importance [2, 3, 4, 31, 12, 18] due to the following reasons.
Structured control refers to fixing the structure of the controller/policy without using the order information of the plant to be controlled. In practice, the state dimension of the true system is typically unknown (e.g. the system is assumed to be rigid body dynamics, but there will always be flexible modes with unknown state order for the true plant due to elasticity or other unmodeled dynamics). It can be very challenging to learn the exact order of the plant [55, 61]. Therefore, it is preferred to fix the structure of the controller/policy beforehand.
Static output feedback is one of the most important forms of structured controller used in control, and it has long history dating back to [42, 67, 49, 60]. Static output feedback has been extensively studied and applied in various areas, including acrospace [23], robotics [25], and chemical engineering [1]. In addition, the static output-feedbact setting covers several important problems as special cases such as distributed controller design [14, 34] and pypportionalintegrrn lniggall-drivativee (PID) control [73].
Studying the complexity of policy optimization methods on structured Nsc synthesis is of great importance for several reasons. First, this problem cannot be solved using convexification tech- niques [62, 7, 26, 63] and hence it is natural to pose this problem as policy optimization [2, 3]. This is significantly different from the full-order Hox control design which yields convex reparameteri- zations [80, 20]. Specifically, if the order (i.e. state dimension) of the plant is exactly known, one can use a dynamical controller whose order the same as the order of the plant, and the resultant full-order Ho. synthesis can be lifted as a convex optimization problem. However, if the plant order unknown and the controller structure is fixed beforehand, the resultant structured Ho problem is non-convex by nature [2, 31. Second, the objective function in structured Ho synthesis can be oondiifferentable over important feasible points (e.g. stationary points), and hence the structured Hos synthesis is nonconvex nonsmooth optimization problem by nature. In the model- based setting, various advanced nonconvex nonsmooth optimization methods have been developed to solve this problem [2, 3, 4, 31, 12, 18, 52, 13, 40], leading to practical toolboxes such as HIFOO [4, 31]. Some convergence analysis has also been recently developed in [32]. However, in the model-free setting, the sample complexity of this problem remains largely unknown. The nonsmoothness of the cost function raises new challenges in developing the complexity analysis. There is gap between the existing sample complexity theory and the model-free policy optimization on nonsmooth Hos synthesis. Our work will bridge this gap via offering the first sample complexity result of model-free policy optimization derivative free policy optimization for structured Hoc static output feedback problem when we can only access the zeroth-order oracle. We consider both exact and inexact zeroth-order oracle settings. Our contributions are two-fold:
nonsmooth Hoc robust control. Specifically, we study the complexity of
1. Exact zeroth-order oracle: We establish the coerciveness of the cost function and then provide gigh-probbbility feasibility and complexity bounds by leveraging the relationship between Goldstein's 's subdifferential and uniform smoothing. Specifically, we show that to find (8, -ttttioony point, the required number of iterations is on the order of O (.)
2. Inexact zeroth-order oracle: We first derive sample complexity bounds for the MIMO Hos. estimation, which are then combined to establish the high-probability sample complexity bounds on the model-free, trajectory-brat based zeroth-order policy optimization methods for structured Hos problem. In particular, we show that the sample complexity bounds for finding a (6, e) -statioonay point under inexact oracle setting are on the order of Ω (x+²) ). To the best of our knowledge, this is the first sample complexity result for model-free policy optimization on nonsmooth Ho synthesis.
More discussions on related work. Our paper focuses on the sample complexity of model-free policy optimization. Other than sample complexity, many other results on optimization landscape and
2

---

algorithm convergence of policy optimization for control have also been recently developed in the literature [9, 21, 79, 78, 75, 74, 16, 58, 39, 37, 38, 69, 66, 36]. See [35] for a comprehensive survey.
Preliminaries and Problem Formulation
2.1 Notation
Let I& denote the d-dimensional real vectors, R denote the set of real matrices with dimension m n. For matrix A. the notations AT. max m (II))) |||||,
p(A) denote its transpose, largest singular value (spectral norm), Frobenius norm, and spectral radius, respectively. The symbol IB, (x) denotes closed Euclidean ball of radius around a point x. Consider sequence = {Wo, W1,,... with Wy E Rn" for all t. This sequence belongs to 2 if Ei=n / < co
defined where well is the standard 2-norm of vector. In addition, the 2-norm for w E 2
as ||w]] : wo=ll/ell?. We say function f(z) = O(g(z)) if lim su s(x)
< oc, f(z) = [(e] O, and f(z) (g(()) if f(x) Og((z) and f(x) l(g(x)).
[(w)
(gg(z)) if lim inf g(a)
Given a matrix sequence {P& E C"** kkez,, ""**]kkz,, let (P) denote the infinite Toeplitz matrix T(P) = (P, (Pi-)) ocd and (P) denote the N N block Toeplitz matrix (P()) (P--)) N-12
2.2 Static output feedback H.s control
Consider the following linear time-invariant (LTI) system
F++11 Az; + Bu: + Wt: To 0
y1 C..
where Te _8 is the system state, u, E R" the control action, Wy E R is the disturbance,
and E I2 is the output measurement. We have A E R xn. B E Rnaxn. C Ra Xna and Tu Og. The initial condition is fixed as 2g We denote
(Wp, W1: ... }
In this work, we consider the static output feedback defined as u, = Ky: = - KCa, where K Rea Xny is constant matrix. Then the closed loop system is given by
T++1 (A BKC),, + Wt, To 0.
The structured H.x synthesis with static output feedback is defined as the following minimax problem
I.. F(Q+CTKE CIQ++CKTRKCOUR
min KEK w
max
II
t=
where IC is the set of all linear static output feedback stabilizing policies, i.e. KC {K Pa...ny p(A - BKC) < 1} and we consider the standard quadratic cost function with worst case disturbance that satisfies the & norm bound ||w|| 1. This is different than the conventional Linear Quadratic Regulator (LQR) problem where only the stochastic disturbance is considered. Throughout this paper, also adopt the following standard assumption [21].
Assumption 2.1. There exists K K. The matrices Q and R are positive definite. The matrix C is full row rank.
In general, the problem of finding stablizing static output feedback policy is known to be NP- hard [5]. For the developments of policy optimization theory, it is standard to assume that such an initial stabilizing policy is available.
In the frequency domain, we can show that the above cost function (3) equivalent to the Hoc norm of the associated closed-loop transfer function [3]. Specifically, the structured Hoc static output-feedback control problem can be formulated as
min J(K), KeK
'Our results in this work can be generalized to the case with measurement noise, i.e., yt = Cx. + Ut. See discussions this extension the supplementary material.

---

where JKK is the No norm of the associated closed-loop transfer function that can be calculated as
J (KK) =
sup maxx ((Q + C K RKC) (e - A+ 1) 2m]
(5)
More details on the derivation of (5) can be found in the supplementary material. We emphasize that the policy search problem (4) is nonconvex nonsmooth optimization problem. There are two sources of nonsmoothness for the cost (5). Specifically, computing the largest singular value and taking supremum over the frequency [0, 2x] can both be nonsmooth. Consequently, the objective function (5) can be non-differentiable over some important feasible points [2, 3, 4, 31, 12, 18).
2.3 Subgradient methods in the bodel-based setting
A key concept in the nonconvex nonsmooth optimization theory is the so-called Clarke subdifferential [15, 43]. A function J K + R is said be locally Lipschitz if for any bounded set S C K. there exists a constant L such that [J(K) - J(K') I L - K''llr for all K, K' E S. It well known that the closed-loop Hos cost (5) is locally Lipschitz over the set of stabilizing controllers [3]. For locally Lipschitz function, the Clarke subdifferential exists and is defined as (K) == conv flim VJ((K): K + K, K E dom(VV) C KC), where conv stands for the convex hull [15]. In the boseel setting, structural Hox synthesis is typically solved using advanced nonsmooth optimization algorithms that generate good descent directions via enlarging the Clarke subdifferential. Two main types of algorithms are briefly reviewed as follows.
Goldstein's 's subgradient method and gradient sampling. The main workhorse for the HIFOO toolbox is the gradient sampling method [11], which is developed based on the concept of Goldstein subdifferential [28]. Specificallyy, the Goldstein ō-subdifferential for a point K E K. is defined as
JkK(K) == conv conv (K)
which implicitly requires (K) C K. It is well known that the minimum norm element of the Goldstein subdifferential generates good descent direction, i.e. J(K / [[F) S J(K)- 5 || Ie for H being the minimum norm element of 05 [28]. Although calculating the exact minimum norm element from the Goldstein subdifferential can be difficult, one can still estimate a good descent direction from approximating (g. as the convex hull of randomly sampled gradients over (K) This leads the gradient sampling method.
Frequency-domain methods. Another popular technique is generateing the descent directions via enlarging the Clarke subdifferential in the frequency domain [17, 54). Such enlargement method relies on standard chain rules to exploit the fact that the closed-loop Hov cost can be rewritten as composition of smooth mapping and convex norm. The Matlab function Hinfstruct from the robust control package [3] is developed based on such frequency-domai technique.
2.4 Randomized smoothing
Our analysis relies on the concept of randomized smoothing techniques, which have been widely used in convex/nonconvex optimization problems [19, 27]. The smoothed version of ((K) via uniform randomized smoothing is defined below.
Definition 2.2. Consider an L-Lipschitz function (possibly nonconvex and nonsmooth) and a uniform distribution P on {U R Xm,,,,, || = 1}. Then the smoothed version of J is defined as Ja is defined as
J&(K) -E + SU)]
The above definition requires both K and K SU to belong to the feasible set K. for all U P.. Very recently, [46] established the relationship between Goldstein subdiffcrential and uniform smoothing. We briefly restate such connections below.
Lemma 2.3. Suppose (KK is L-Lipschitz over some bounded set S C K. and for any K E S, we have K + 8U E for all U with |U]|| such that Js(K) well defined (see Definition 2.2). Let O&J(K be the Goldstein 5-subdifferential at K, then for any K E S, we have:
(i) [J(K) - JsK) S 8T.
(ūi) J& is differentiable and L-piscchitz with the slydd 8
-Lipshhiiii gradient, where d = By. is the
problem dimension and e>> O is a constant,
(iii) JJs(K) E (K).

---

This lemma is essentially [46, Proposition 2.3, Theorem 3.1]. Based on the definition of Goldstein b-subdifferential (6), we say a point K is a (6, -statiionayy point dist(0. 0zJ (K)) S c. Then Lemma 2.3 (iii) implies that if K is e-stationary point of Ja(K) (i.e., [[VJs(K)l & 6), then K is also a (6, e) )-stationary point of the original function J(K).
Suppose that we can compute VJs(K), then we can simply apply gradient descent based on the gradient of Js(K)
K = K VJ(*')
to find a e-stationary point of Js(K). However, how to choose the stepsize and smooth radius à to guarantee the feasibility and convergence an (6, -S-stooion points of the original cost function (5) is unknown. We will discuss this setup more in Section 3.2.
2.5 Problem formulation: two zeroth-order oracle assumptions
In this paper, we aim minimize the cost function J(K) in the policy space directly via derivative- free methods. Specifically, we consider two different zeroth-order oracle settings:
1. Exact zeroth-order oracle: This oracle assumption is standard for zeroth-order optimization literature and natural for the model-based control setting. In particular, we assume that we exactly calculate J(K (which is the closed-loop Hoc norm) for every stabilizing K. When the system dynamics are known, such an oracle is available since the closed- loop Ho norm can be efficiently calculated using existing robust control packages in MATLAB (currently, the state-of-the-art techniques for model-based Hoo norm calculations rely on using the relation between the singular values of the transfer function matrix and the eigenvalues of a related Hamiltonian matrix [6, 8J.. Under the same oracle setting, the non-derivative sampling method has been successfully applied to state-feedback H.o control problem in [32] without complexity guarantee. In this work, we close this gap by showing that, for constrained policy optimization problem (4), our algorithm returns (6, c)-stationary point with high-probbbblity feasibilityccompexitty bounds.
2. Inexact zeroth-order oracle: This oracle assumption is relevant for the model-free learning- based control setting, where the system dynamics are unknown, and J(K) (the closed-loop Hox norm) can only be estimated from the input/output data of a black-box simulator of the underlying system. particular, we use the model-free time-reversal power-iteration-bass Hox estimation from [70] to serve as the inexact oracle for J J(K), (.). Despite the existence of such algorithms, the prior literature lacks sample complexity bounds for general MIMO systems. Therefore, we presented the first sample complexity result for Hoc norm estimation
for general MIMO systems. Building upon this, we obtain the first sample complexity results for model-free policy optimization of Ho control with noisy function values.
3 Main Results
In this section, we present our main result for the exact eeroth-order oracle case. will start with the optimization landscape of the policy optimization problem (4).
3.1 Optimization landscape
Proposition 3.1. The set K. = : disconnected. In general, it can be either bounded or unbounded. The cost function (5) is locally Lipsehitz over and hence continuous K.
-(A- BKC) < 1} is open and nonconvex. It can be
The proof of the above proposition can be found in [10, 22, 3]. Next, we identify the coerciveness of the cost function J(K).
Lemma 3.2. The Hos objective function J(K) defined by (5) is coercive over the set K. in the sense that for any sequence {K]) C K. we have
J(K') + +00
if either | + t00, K' converges to an element in the boundary ÒK.
5

---

It is worth mentioning that the above lemma relies on the assumption that both Q and R are positive definite. The formal proof of Lemma 3.2 is deferred to the supplementary material. The continuity and coerciveness of J( directly lead to the following results.
Lemma 3.3. Consider the H.s output feedback policy search problem (4) with the objectiveffunction J(K) defined in (5). Under Assumption 2.1, for any y > J", the sublevel set defined as S, := {K E
K: J(K) S 7) is compact.
Remark 3.4. Based on Lemma 3.3 and the fact that the set I. is open, we can show that there is a strict separation between the sublevel S, and OK. It is obvious that aK is closed. Since S. is compact and Sy n OK = Ø, we have (ist OK) > 0.
3.2 Warm-up: convergence of smoothed function
In this section, we assume that the exact gradient oracle (a) is available for each K E K. such that (K)) well defined. Then we analyze the finite-time convergence and feasibility of the vanilla gradient descent method (8). To this end, let K E K. be an arbitrary feasible initial controller. Without loss of generality, define two feasible sets:
5 == [K ((K) I ()) S : (K]((K) ))
Denote Ao dist( aK) and A dist(S), aK)). Let Lo and L1 be the Lipschitz constants of J J(K associated with the sublevel set 8 and S respectively. It is obvious that Do 2 A and Lo S L1. In addition, we have A dist as²) > 0 by Remark 3.4.
Remark 3.5. Since J(K) is continuous function of K by Proposition 3.1 and the sublevel sets g and S are compact by Lemma 3.3, this implies that there exists a constant & > 0 such that for any K 8 and K' with K K' &, we have K' E S1.
Now we are ready to state the following result.
Theorem 3.6. Let K K be an arbitrary feasible initial controller and suppose that Jg(K) defined as in (7) is L, -ipischhitzz with the sh,/dd Lipschtiz gradient on the sublevel set S) Choose Then the iterative method (8) stays in K. and we 2L, } and minf & V.ival..
5 = minn A1, 49J(Kk)
have:
< VJ&( 2(Jb(Ko) -J)) n/T
min t=0,1,-. T-1
(10)
In other words, we have minogegT-1 JJJ(K"))ll S cater T = 0
The proof of Theorem 3.6 can be found in the supplementary material. Since we have constrained optimization problem, it is crucial to guarantee the feasibility of the gradient descent method (8). The careful choice of smooth radius 8 and step size 7) ensures that Kt stays inside the feasible set.
3.3 Analysis for the exact oracle case
In this section, we consider the exact zeroth-order oracle setup, where can obtain the exact Hox norm of the closed-loop system for a given K E K.. One straightforward extension of (8) is to compute an unbiased estimation of the gradient V JJs('') via the zeroth-order oracle. Then can perform the one-step gradient descent. In particular, we analyze the feasibility and convergence of the Algorithm in the following result.
Theorem 3.7. Let K E IC be an arbitrary feasible initial controller and suppose J(K) is Li- Lipschtiz with the clavd clysa-Lipschtiz gradient on the sublevel set St. Let 1 S S 80 and suppose we choose
6
8 min AA, A. J(K2),
(K))
28
Sea
L1 T
cd3/22 7) min( d(100J(K9) J+)' 3500cd3/2 L
Then the following two statements hold:
(I) the controllers (KT)T=) generated by Algorithm I are all stabilizing with probability at least
0.95 0.0lv.
(2) the outpul of Algorithm KR satisfies
min minn[| [ H H S
(11)
with probability at least 0.87 - - 0.01v.

---

Algorithm 1: Derivative-Fres Methods for Policy Optimization Problem (4)
Require: feasible initial point K E R X"y, stepsize rj > 0, problem dimension
d = nu X ny 2 1, smoothing parameter å and iteration number T 1. for t = 0, 1. ... T
do
Sample W E R uniformly at random over matrices such that ||]|| 1. Compute g' d (J(K* + +Ww) J(K - SW
28 Update K K ng'.
end for
Output: K" where R E {0, 10,1,2,... , -T is uniformly sampled.
The proof of Theorem 3.7 can be found in the supplementary material. Now provide some discussions regarding Theorem 3.7 in order:
Statement suggests that as T increases, the probability that all the generated controllers are stabilizing will decrease. This is because our algorithm uses a zeroth-order oracle to build an estimator of the smoothed function gradient. As T increases, the biases and variance of the gradient estimation accumulate, resulting in a larger failure probability. In addition, Statement 2 suggests that as 7 increases, the probability of finding (6, e)-stationary point will first increase and then decrease. Indeed, when T is too small, more iterations will improve the performance the generated controllers, while for large T, the probability of generating unstable controllers becomes dominant. In addition, the constant factors in the probability bounds are not restrictive, they can be further improved by e.g., increasing the level of S", using smaller step size nj using smaller smooth radius 8 in the analysis.
Probability Bounds:
Feasibility: Statement 1 states that all the output controllers {K*)T=) are feasible with high probability under the choice of algorithm parameters. It is worth mentioning that, to ensure the feasibility of the iterates {K* 7 we need to show that (Js(K')) ) are well defined so that we can apply the smoothness property of J& (K) in our theoretical analysis. Furthermore, this also guarantees that (J(K*
JE=D
)o used in Algorithm are well defined. This turns out to be a nontrivial task and one needs to design algorithm parameters carefully to resolve the feasibility issue. More discussions will be provided in the end of this section.
Output Controller: Since our cost function J(K) is nonconvex, we consider an output con- troller K uniformly sampled from [ Such random output technique has been used in smooth//nosmootth nonconvex optimization problems for theoretical analysis [27, 46, 44]. In particu- lar, Statement implies that the output controller KR R is a (6, e)sstaioonaryy point with high probability. In practical implementation, one can just select the iterate that gives the lowest cost ((K)) for t = 1,... .T Our numerical experiments suggest that selecting KT often yields satisfactory performance (see Section 5).
Sample Complexity: For sufficiently small c, the number of iterations to guarantee (11) is given by:
d 1
T-O θ
(12)
Sed
where d > 1 is the problem dimension, Li is the Lipschtiz parameter. We also ignore the numerical constants since they are conservative and not restrictive.
Finally, we close this section by highlighting the main technical contributions of Theorem 3.7 and 3.6. In our control setup, unlike the unconstrained optimization problems [46], we need to ensure that the iterate Kt and the perturbed iterate K' + ów stay within a non-convex feasible set X. Previous work on policy optimization theory of H.s control addresses this feasibility issue via using the coerciveness of J(K) and mainly relies on the fact that J(K) is a barrier function on the non-convex set of stabilizing policies [32]. In particular, such previous results rely on model-based algorithms (such as Goldstein's 's subgradient method) which can decrease the value of J(K) directly. However, the zeroth-order policy search can only decrease the value of the smoothed function (K).. which is not coercive over the non-convex feasible set and hence cannot be used as barrier function. Importantly, the descent of J& K) does not imply the descent of the original function value and hence cannot ensure fcasibility by itself. In Theorem 3.7 and 3.6, by carefully choosing the smooth radius
7

---

5 and step size 77 we manage to show that the iterate K" and the perturbed iterate K + 8W stay within a non-convex feasible set with high probability.
4 Sample Complexity for the Model-Free Case
In this section, we assume that the system dynamics in (1) are unknown and we can only use samples to obtain an estimation of the cost function (K) with some error ((K) = (K) + ((K). To obtain an end-to-end sample complexity result of Algorithm we first derive the sample complexity of Hoc norm estimation for the general MIMO systems such that ((K) S k for all K E K.
4.1 Complexity of Hos norm estimation for MIMO systems
The Hoc norm estimation method via input/output data can be roughly categorized into two major approaches: (a) try to find the worst case fz-norm signal using power-iteration algorithm [71, 53]. (b) discretizing the interval [0, 2T] and search for the maximizing frequency using multi-armed bandit [51]. However, there are no sample complexity results of the aforementioned methods for the general MIMO system. In this section, we analyze the Ho norm estimation method proposed in [53] and establish its sample complexity bounds for the general MIMO systems.
To this end, let P(=) (Q + C² RKC)
A + BKC)- be the transfer function associated with the system (1) to the cost function (3), let T(P) denote the corresponding Toeplitz (convolution) operator and Ty be the N N upper-left submatrix of T(P). Then it known that J(K) = []]l))| and [PT +
[P) as N - oc. With large enough N, the largest singular value of the Tv (P) can be used as a reasonable estimation of J(K), which can be approximated by running the power iteration algorithm n steps 2. Therefore, there are two error terms based on this approach. The first term (K) comes from the difference between [Tx(P)) and [[T(P)) [. and the second term (2(K) is induced by computing the largest singular value of (P))) via the power iteration algorithm:
((K)]= = [J(K) - J(K) S (J(K) [[xx(P)]I |1]x* ((K) = (K) + (K)), (13)
where J(K) is the approximated largest singular value of Txx and hence an estimation of J ((K).
Therefore, if we can choose N and n large enough such that (K) S k//2 and (2( I x2/2, we
will have ((K) S x holds by (13). The finite-time condition on N has been established in [68] for
single input single output (SISO) systems only. In the following result, we extend the result in [68] to the general MIMO system. Furthermore, we provide the finite-time condition on the number of power iteration iterations n.
Theorem 4.1. Let P(z) = =E Pka be the corresponding transfer function of system (1) to the
cost function (3) with stability radius E (0, 1). And choose E (t. 1) and D 2 oma (Po). Let
| lo denotes the Hox norm of the system (2) == PP(22). Then N 2 3, we have
(J(K) J(K (1) + (2(K)
(14)
where
((K)= = C1 PIP 8o (1 72) + P 1 1
|
1
N2 + C2
(15)
|| 7)
| (1 + 7) - 765 N3
(2(K)= C3l1Pllaa 3
(16)
are errors due to approximating T by Tn and using power iteration to estimate | [|, respectively. Here Ci =3v2m2 + 3m C2 -v2 2x2 are universal constants and Ca depends on angle between power iteration initialization and the eigenvector corresponding to the biggest eigenvalue of T (P))x()).
The proof of Theorem 4.1 can be found in the supplementary material. Theorem 4.1 implies that the approximation error (<(K) S k is guaranteed by choosing
P 12 2 P K
(1C
N inf Ω <59<1
n
Ω
(17)
11
For completeness, the pseudo-code material.
code of the power iteration algorithm is provided in the supplementary
8

---

4.2 Sample complexity of zeroth-order optimization
In this section, we consider that Algorithm I can only access the inexact zeroth-order oracle of the cost function JKK). In this case, do have unbiased estimation of V.a( (K*). Nevertheless, can make the estimation as small as possible and assume that the estimation error ((K) is uniformly upper bounded for all K E St:
[<() S K, A St.
(18)
Clearly, the smaller is, the larger power iteration number and approximation horizon N are needed. We will specify the choice of и in the next result, where we obtain the feasibility/sample complexity bounds of Algorithm via inxacc zeroth-orde cooth-order oracle on finding a (6, e)-stationary point.
Theorem 4.2. Lel K E K. be an arbitrary feasible initial controller and suppose J is Lı -ipschhiii on the sublevel set S Consider the Algorithm with inexact ceroth-order oracle and suppose that
the estimation error S suppose we choose
Denote I == cLi (LLIvd((6v/222))
( ))) Let 1 S v S 25 and
T00dI.1
min (1I A. J(K)), L
( 2T²2 min dr<100J((K0) J 100r
8
8E²
}.
Then the following statements hold:
(I) the controllers {K"T T-1 generated by Algorithm with inexact zeroth-order oracle are all stabilizing with probability at least 0.95 0.03v.
(2) the outpul of Algorithm K salisfies
min H H E 0sJ(KK)) se
(19)
with probability at least 0.8 - 0.15e 0.03v.
The proof of Theorem 4.2 can be found in the supplementary material. For sufficiently small we can obtain the following lower bound on the number of iterations to guarantee (19):
d
L ded
T = Ω
(20)
Since we require k < To0dL, we have the following lower bounds on the power iteration number and approximation horizon by (17):
6x2
1//2
(dL1) 82.
= Ω
81/2
12
Finally, by combining the above sample complexity bounds for MIMO Hox estimation with (20), the number of samples to guarantee (19) with high probability given by:
/2/22
nNT Ω
(21)
53
In this section, we consider the sample complexity of Algorithm with the inexact oracle case. This is particularly relevant for the model-free control setting. Specifically, we are using imperfect estimates of J (KK) that are calculated using the model-free -rre MIMO power iteration method. Therefore, an extra statistical error term appears the iterations of zeroth-order policy optimization and requires special treatment. Such an extra term has not been considered in the literature on zeroth-order optimization for nonconvex nonsmooth problems. To address this extra technical difficulty, we first establish sample complexity bounds for H.. norm estimation of the general MIMO system (Theorem 4.1). Then we carefully propagate such sample complexity bounds to obtain an error bound for VJs(K) in terms of and 8. Built upon this, we demonstrate that Algorithm I remains effective even with an inexact oracle, ensuring the feasibility of the iterates while achieving finite-time sample complexity with high probability (Theorem 4.2).

---

5 Numerical Experiments
In this section, present the numerical study to show the effectiveness of Algorithm 1. The left plot Figure displays the relative error trajectories Algorithm with an exact oracle for system dimensions ni {10, 50, 100). The system is of form (1) with parameters (A, B, C),, where the entries of (A, B, C) are sampled from a standard normal distribution N (O, 1). The results show that Algorithm performs well even for larger-scale systems. In the middle plot, trajectories of Algorithm with both exact and incxact zeroth-order oracle. can be observed that the inexact oracle case closely tracks the performance of the exact oracle casc. The right plot illustrates the zeroth-order complexity of the exact oracle case with varying c. As shown, the number oracle calls increases decreases. It is important to note that the complexity bounds derived in (12) are not tight. We conjecture that by leveraging other advanced properties the cost function (5), further improvements in complexity can be achieved.
compare the
Exses Otocle
10"
J18
1011
Relabve
50
100
150
200
10
10
Inssoc: Oraioe
J(K]
1001
10"
10
2000
4000
6300
8000
10000
60
100
200
Ineratinss
Figure I: Left: The relative error trajectories of Algorithm I with exact zeroth-order oracle and B2 {10, 50, 100), the solid lines represent the mean values and the shade represents 98% confidence intervals; Middle: The trajectory of Algorithm with exact and inexact zeroth-order oracle; Right: Number of zeroth-order oracle calls required to find (5, -tsttioonyayy point with varying c.
Table 1: Comparison of Algorithm with model-based methods
Example
(Na, Ny)
HIFOO
Hinfstruct
Algorithm I (Ours)
AC15
(4,
15.2919
15.2
15.4141
HF2D11
25,
7.7237 x 10a
7.72
10a
7.7223 x 10a
DLR2
(40, 2,
4.0066 x 10
4.01
103
4.0094 103
HE4
(8,4.6)
22.8382
22.8
22.8538
In addition, we conducted a comparison of derivative-free method with the model-based methods HIFOO and Hinfstruct, using several benchmark examples from COMPI, [41]. Table 1 shows the corresponding optimal closed-loop His norm. It can be seen that derivative-free method yields comparable results with the model-based packages even without the knowledge of system models. More details about the numerical experiments can be found in the supplementary material.
Conclusion and Future Work
This paper presents the fcasibility and complexity bounds for the derivative-free policy optimization method on the structured H.s synthesis, considering both exact and inexact zeroth-order oracles. Despite the fact that this structured Ho0 synthesis is a constrained nonconvex nonsmooth opti- mization problem, we leverage the intriguing connections between randomized smoothing and (6, c)-stationnaity, enabling the first sample analysis for model-free, trajectory-basse zeroth-order policy optimization in structured Hox synthesis. One limitation of this work is the uncertain tightness of the sample complexity bounds obtained.
For future studies, it is important to tighten the sample complexity results by exploring more properties of Hox control problems. addition, it interesting to explore the behavior of the structured Hos problem with dynamic output feedback controller.
10

---

Acknowledgement
The work of Xingang Guo and Bin Hu is generously supported by the NSF award CAREER 2048 168 and the IBMIIIDAI award 11066--01. The work of Darioush Kevian and Geir Dullerud was supported by NSF under Grant ECCS 1932735. The work of Peter Seiler was supported by the U.S. Office of Naval Research (ONR) under Grant N00014-18-1-2209.
References
[1] C. Antoniades and P. Christofides. Integrating nonlinear output feedback control and optimal actuator/sensor placement for transport-reaction processes. Chemical Engineering Science, 56(15):4517 -435, 2001.
[2] P. Apkarian and D. Noll. Controller design via nonsmooth multidirectional search. SIAM Journal on Control and Optimization, 44(6):1923- 1949, 2006.
[3] P. Apkarian and D. Noll. Nonsmooth Hos synthesis. IEEF Transactions on Automatic Control, 51(1):71-86,
2006.
[4] D. Arzelier, G. Deaconu, S. Gumussoy, and D. Henrion. H2 for HIFOO. In International Conference on Control and Optimization With Industrial Applications, 2011.
V. Blondel and Tsitsiklis. Np-hardness of some linear control design problems. SIAM journal on control and optimization, (3(6):2118-2111 2127, 1997.
S. Boyd, V. Balakrishnan, and Kabamba. A bisection method for computing the h.s of transfer matrix and related problems. Mathematics of Control, Signals and Systems, 2(3):207-29, 1989.
S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan. Linear Matrix Inequalities in System and Control Theory, volume 15. SIAM, 1994.
[8] N. Bruinsma and M. Steinbuch. A fast algorithm to compute the hnom of transfer function matrix. Systems & Control Letters, 14(4):287-2) 1990.
Mesbahi, Fazel, M. Mesbahi. LQR through the lens of first order methods: Discrete-time case. arXiv preprint 1XXXv:1907.00800 2019.
[10] Bu, A. Mesbahi, and M. Mesbahi. topological and metrical properties of stabilizing feedback gains: the MIMO case. arXiv preprint arXiv: 2019.
[11] Burke, D. Henrion, Lewis, and M. Overton. HIFOO A MATLAB package for fixed-order controller design and Hoc optimization. IFAC Proceedings Volumes, 39(9):3393344, 2006.
[12] V. Burke, E. Curtis, S. Lewis, M. L. Overton, and L. E. Simões. Gradient sampling methods for nonsmooth optimization. Numerical Nonsmooth Optimization, pages 201-225 2020.
[13] J. V. Burke, A. S. Lewis, and M. L. Overton. A robust gradient sampling algorithm for nonsmooth, noncoлvex optimization. SIAM Journal on Optimization, 15(3):751-77, 2005.
[14] P. Christofides and A. Armaou. Global stabilization of the kuramoto-sivashinskk equation via distributed oulput feedback control. Systems & Control Letters, (9()):833-294, 2000.
[15] F. H. Clarke. Optimization and nonsmooth analysis. STAM, 1990.
[16] L. Cui and L. Molu. Mixed H2 Ho LQ games for robust policy optimization under unknown dynamics. arXiv preprint ar0iv:2209, 04477, 2022.
[17] J. Cullum, W. Donath, and P. Wolfe. The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices. Nondifferentiable optimization, pages 35-55, 1975.
[18] 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.
[19] J. Duchi, P. Bartlett, and M. Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
[20] G. Dullerud and F. Paganini. A Course in Robust Control Theory: A Convex Approach. Springer, 1999.
11

---

[21] I. Fatkhullin and B. Polyak. Optimizing static linear feedback: Gradient method. SIAM Journal on Control and Optimization, 5965)33877-311, 2021.
[22] Fazel, Ge, Kakade, and M. Mesbahi. Global convergence of policy gradient methods the linear quadratic regulator. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 1467-1476, 2018.
[23] F. Fonte. S. Ricci, and P. Mantegazza. Gust load alleviation for regional aircraft through static output feedback. Journal of Aircraft, 52(5):1559-155) 2015.
[24] L. Furieri, Y. Zheng, and M. Kamgarpour. Learning the globally optimal distributed LQ regulator. In Learning for Dynamics and Control, pages 287-297, 2020.
[25] J. Gadewadikar, F. Lewis, K. Subbarao, K. Peng. and B. Chen. H-infinity static output-feedbace control for rotorcraft, Journal of Intelligent and Robotic Systems, 54:2646662666, 2009.
[26] P. Gahinet and P. Apkarian. A linear matrix inequality approach to Ho control. International Journal of Robust and Nonlinear Control, 4:421-448, 1994.
[27] S. Ghadimi and G. Lan. Stochastic first-and zeroth- methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
[28] A. Goldstein. Optimization of lipschitz continuous functions. Mathematical Programming, 13(1):14 100:144-2 22,
1977.
[29] G. Golub and C. Van Loan. Matrix computations. JHU press, 2013.
[30] B. Gravell, P. M. Esfahani, and T. Summers. Leaminng optimal controllers for linear systems with multiplicative noise via policy gradient. IEEE Transactions on Automatic Control, 66(11):5283-529 2020.
[31] S. Gumussoy, D. Henrion, M. Millstone, and M. L. Overton. Multiobjective robust control with HIFOO 2.0. IFAC Proceedings Volumes, 144-149, 2009.
[32] X. Guo and B. Hu. Global convergence of direct policy search for stedbake 11.0 robust control:
A revisit of nonsmooth synthesis with goldstein subdifferential. In Conference on Neural Information Processing Systems, 2022.
[33] B. Hambly, R. Xu, and H. Yang. Policy gradient methods for the noisy linear quadratic regulator over a finite horizon. SIAM Journal on Control and Optimizution, 59(5):3359-33 2021.
[34] K. Hengster-Movric, F. Lewis, and M. Sebek. Distributed static output-eeddback control for state synchro- nization in networks of identical Iti systems. Automatica, 53:282-290, 2015.
[35] B. Hu, Zhang, N. Li. M. Mesbahi. Fazel, and T. Başar. Towards a theoretical foundation of policy optimization for learning control policies. arXiv preprint ww..iv:220000481/ 2022.
[36] B. Hu and Y. Zheng. Connectivity of the feasible and sublevel sets of dynamic output feedback control with robustness constraints. IEEE Control Systems Letters, 7:442-447, 2022.
[37] J. P. Jansch-Porto, B. Hu, and G. Dullerud. Policy learning of MDPs with mixed continuous/discreee variahles: A case study model-free control of Markovian jump systems. In Learning for Dynamics and Control, pages 947-957, 2020.
[38] J. P. Jansch-Porto, B. Hu, and G. Dullerud. Policy optimization for Markovian jump linear quadratic control: Gradient- based methods and global convergence. IEEE Transactions on Automatic Control, 2020.
[39] J. P. Jansch-Porto, B. Hu, and G. E. Dullerud. Convergence guarantees of policy optimization methods for Markovian jump linear systems. In American Control Conference, pages 2882-2887, 2020.
[40] C. Kiwiel. Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM Journal on Optimization,, (6(2):3793388 2007.
[41] F. Leibfritz and W. Lipinski. COMPleib 1.0-user manual and quick reference, 2004.
[42] W. Levine and M. Athans. On the determination of the optimal constant output feedback gains for linear multivariable systems, IEEE Transactions on Automatic control, 15(1):44 48, 1970.
12

---

[43] J. Li. A. So. and W. Ma. Understanding notions of stationarity in nonsmooth optimization: A guided tour of various constructions of subdifferential for nonsmooth functions. IEEE Signal Processing Magazine, 37(5):18-31, 2020.
[44] 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.
[45] T. P. Lillicrap, J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: 525.099997,,. 2015.
[46] Т. Lin, Z. Zheng. and M. Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. In Conference on Neural Information Processing Systems, 2022.
[47] 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 2916-2925, 2019.
[48] V. Mnih, K. Kavukcuoglu, D. Silver, A. Rusu, J. Veness, M. Bellemare, A. Graves, M. Riedmiller, A. Fidjeland, G. Ostrovski, and S. Petersen. Human-level control through deep reinforcement learning. Nature, 518:529-533, 2015.
[49] D. Moerder and A. Calise. Convergence of a numerical algorithm for calculating optimal output feedback gains. IEEE Transactions on Automatic Control, 30(9)9900- 900-903,, 1985.
[50] 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 Automatic Control, 2021.
[SI] M. L. Müller, P. E. Valenzuela, A. Proutiere, and C. R. Rojas. A stochastic multi-armed bandit approach to nonparametric H.s--nrm estimation. In 2017 IELE 56th Annual Conference on Decision and Control (CDC), pages 4632-46377. IEEE, 2017.
[52] D. Noll and P. Apkarian. Spectral bundle methods for non-convex maximum eigenvalue functions: second-order methods. Mathematicul Programming, 104(2):229-744 2005.
[53] T. Oomen, R. der Maas, C. R. Rojas, and H. Hjalmarsson. Iteratively learning the -nom of multivariable systems applied to modellerror-modeling of a vibration isolation system. In 2013 American Control Conference, pages 6703 0708.667700000 IEEE, 2013.
[54] F. Oustry. A second-order bundle method to minimize the maximum eigenvalue function. Mathematical Programming, 89:1-33, 2000.
[55] S. Oymak and N. Ozay. Non-asymptotic identification of Iti systems from a single trajectory. 2019 American control conference (ACC), pages 5655-5661.11B55 2019.
[56] K. Ozaslan, H. Mohammadi, and M. R. Jovanović, Computing stabilizing feedback gains via a model-free policy gradient method. IEEE Control Systems Letters, 7:407-412, 2022.
[57] J. Perdomo, J. Umenberger, and M. Simchowitz. Stabilizing dynamical systems via policy gradient methods. Advances in Neural Information Processing Systems, 34, 2021.
[58] G. Qu, C. Yu, S. Low, and A. Wierman. Exploiting linear models for model-free nonlinear control: provably convergent policy gradient approach. In 202/ 60th IEEE Conference on Decision and Control (CDC), pages 6539-6546,, 2021.
[59] 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.
[60] T. Rautert and F. W. Sachs. Computational design of optimal output feedhack controllers. SIAM Journal on Optimization, 73):8877882, 1997.
[61] T. Sarkar and A. Rakhlin. Near optimal finite time identification of arbitrary linear dynamical systems. In International Conference on Machine Learning, pages 5610-5618, 2019.
[62] C. Scherer, P. Gahinet, and M. Chilali. Multiobjective output-feedbace control via Imi optimization. IEEE Transactions on automatic control, 42(7):896 9911, 1997.
[63] C. Scherer and S. Wieland, Linear matrix inequalities in control. Lecture notes for a course of the dutch institute of systems and control, Delft University of Technology, 2004.
13

---

[64] J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint urXiv:/506.024555 2015.
[65] D. Silver, J. Schritwieser, K. Simonyan, I. Antonoglou, A. Huang. A. Guez, T. Hubert, I. Baker, M. Lai, A. Bolton, al. Mastering the game of Go without human knowledge. Nature, 550(7676):354-3555 -59, 2017.
[66] Y. Tang and Y. Zheng. On the global optimality of direct policy search for nonsmooth low output-feedback control. arXiv preprint wrXiv:2304.00733, 2023.
[67] H. Toivonen. A globally convergent algorithm for the optimal constant output feedback problem. Interna- tional Journal of Control, 4166):1589-1599) 1985.
[68] S. Tu, R. Boczar, and B. Recht. On the approximation of Toeplitz operators for nonparametric -norm estimation. In 2018 Annual American Control Conference (ACC), pages 1867-1872. IEEE, 2018.
[69] J. Umenberger, M. Simchowitz, J. C. Perdomo, K. Zhang, and R. Tedrake. Globally convergent policy search over dynamic filters for output estimation. arXiv preprint 1rX1v:2202.11659, 2022.
[70] B. Wahlherg, M. Syberg, and H. Hjalmarsson. Non-parametric methods for lz-gain estimation using iterative experiments. Automatica, 16(8):1376-1381, 2010.
[71] B. Wahlberg, M. B. Syberg, and H. Hjalmarsson, tor-maraectric methods for l2-gain estimation using iterative experiments. Automatica, 1666)11376 2010.
[72] Z. Yang, Y. Chen, M. Hong, and Z. Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. Advances in neural information processing systems, 32, 2019.
[73] H. Zhang, Y. Shi, and A. Mehr. Robust static output feedback control and remote pid design for networked motor systems. IEEE Transactions Industrial Electronics, (811)):339655405 2011.
[74] K. Zhang, B. Hu, and T. Başar, On the stability and convergence of robust adversarial reinforcement lcarning: A case study on linear quadratic systems. Advances in Neural Information Processing Systems, 33, 2020.
[75] K. Zhang, Hu, and T. Basar. Policy optimization for Hz linear control with Hox rohustness guarantce: Implicit regularization and global convergence. SIAM Journal on Control and Optimization, 59(6):401- 4109, 2021.
[76] 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 Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
177] F. Zhao and K. You. Primal-dual learning for the model- free tisk-constrained lincar quadratic regulator. In Learning for Dynamics and Control, pages 702-714, 2021.
[78] Y. Zheng, Y. Sun, M. Fazel, and N. Li. Escaping high-order saddles in policy optimization for linear quadratic gaussian (lgg) control. In IEFE 61st Conference on Decision and Control (CDC), pages 5329-5334, 2022.
[79] Y. Zheng, Y. Tang, and N. Li. Analysis of the optimization landscape of linear quadratic gaussian (LQG) control. arXiv preprint 102::2102200499 2021.
[80] K. Zhou, J. Doyle, and K. Glover. Robust and Optimal Control. Prentice-Hall, 1996.
14

---

Supplementary Material
A More on Problem Formulation
A.1 Derivation of the cost function in frequency domain
The goal of the structured Hoo synthesis with static output feedback is to find the optimal controller gain K solve the following minimax problem:
min max KEK w: w:|lwwll 1
+ C
(A.1)
Now if we define 24 (Q + ar Qu++u, Ruy. Then the closed-loop LTT system (2) can viewed as linear operator GK mapping
we have || = x CTKTRKOO =
any disturbance sequence {w,} to another sequence {=t}. If K is stabilizing, i.e. p(A - BKC) < 1, then GK is bounded in the sense that maps any le sequence w to another sequence z f For any stabilizing K, the & + &z induced norm of Gx can be defined as:
|G = sup
(A.2)
O>|| [w]
Since GK is a linear operator, it is straightforward show
DC
2
| | 12:=2= = MIX wi||w||
t. KK++CKKRRKOJ.
Σ
(x) [x]Qxr Qui + us Rue).
max w: w
Therefore, the minimax optimization problem (A.1) can be rewritten as the policy optimization problem: minkex/||yy 112-22 We can just drop the square in the cost function and reformulate (A.1) as minxex [G This is exactly the policy optimization formulation for structured H. with static neeputt control. In the frequency domain, Gk can viewed as transfer function that maps signal to z,. Applying the frequency-domain formula for the Hos norm, we can calculate || 2|2-22 as
1G = sup max ((Q + CTRTTRRRR- (e A+ BK)-)), 2
(A.3)
which is the same as we defined (5).
A.2 LTI system with measurement noise
In this section, we extend the LTI system (1) considered in the main paper to the one with measurement noise below:
11+1 = Ar; Bu, + We
2o = O,
(A.4)
Vt Cz, + T4-1,
with n-1 O. We denote n (n-1, no, .......... noise falls within our framework via a proper state augmentation trick. In particular, it is obvious that (A.4) can be rewritten as:
........ }. We will show that the problem with measurement
8++1 n4
A
0
B
W
0
n 1
+
U4
+
n2
y/ = C
I
1x-1
In this setup, the control inputs become
Wr Kyr KK Kn
and the closed-loop system can be represented as
Ø141
A - BKC
-BK
Zt
+
n4
0
14-1
72
15

---

Then, the min-man max cost function can be written
2
J(K)
max
us Rut
3t
Q
0
Ft Pr-1
(KCr, + Km-11) Rnn-))R(KCTa + Kn--1)
14-1
0
S
1=0
n
n
T
Q C RKC
RK K
Ft
W
max
W
14-1
KKR
ne-1
II
Q RKK CKRRKK
If we define
in frequency domain, we can rewrite
RKC
K
R4-1
the above cost function as
(1 (1o [ KTRKC
CURTRK KURK
(J [--
-BK A BKC
J(K) sup mmax w
0 0
(A.5)
We slightly modify proof of Lemma 3.2 show that (A.5) remains coercive. Therefore, all the results presented in the paper follow.
B
Detailed Proofs
B.1 Proof of Lemma 3.2
Suppose we have a sequence {K*) satisfying ||*|| - +o0. Let w = {wo, 0..,.... with ||w/||| such that max (K'C) || Then we have:
J(K')
(K')
max
w IS1
My (0) w/ (Q (K'CRRRKRCC
NV (a)) Ami (R) K' C'C'll
V Amia (R) min (o (Kt)
where inequality (4) holds since we plugged into a specific w' over the max operation and the matrix Q (K RK'C is positive definite. Inequality (ii) uses the fact that R Amin (R),, where Amiin R is the minimum eigenvalue of R. Since ||
+oo by equivalence of norms Tmax ) +00, and knowing C' is full row rank matrix guarantees that Amin (CCT) 0. therefore J J(K') + too as | [F - +00.
Next, we assume Kd - where K on the boundary OK. Clearly we have p(A BKC)
We will use a frequency-doma argument to prove J(K+) - +oo. Since p(A - BKC) 1, there exists some such that the matrix (e I A+ BKC) becomes singular. Obviously, for the same BKC) also singular. Therefore, we have:
wo. the matrix (etwor
J(K')
= sup mmax (1Q+ (Q++(K()) (( - A+BK'O)-)
w (0,2mm
sup Omin (Q') maax A+BK'C)-
w 2
1/2 (Q) maax ((ejw) - A+ BK'C)-)
Clearly, the above argument relies the fact that Q is positive definite and 2 Amin (Q) Notice that we have p(A- BK'C) < 1 for each I, and hence we have Jmin ((elwo A BK'C)) > 0.
16

---

Le. the smallest singular values of (el40) - A-A+BK' are strictly positive for all I. By the continuity of the m. we must have a min (( 1 - + C)) + 0 as lim K³ E Ōk. Hence we have max (( I - A + CK'C) - too as I + cc. Therefore, we have J(K)) + +00 as Kt + K E OC. This completes the proof.
B.2 Proof of Lemma 3.3
We first prove Lemma 3.3. Since is continuous, for any 7 J", know S. - {K K. J(K) S > is closed set. It remains to show S. is bounded. Suppose that S. is unbounded. Then there exists a sequence { Ji=1 C S such that || 1a + +oo as + cc. But by coerciveness of J (K), we must have (K') + +oo as well, which contradicts that J(K)) S for all l. Hence S bounded. Therefore, S, is compact.
B.3 Proof of Theorem 3.6
We first use induction to show that the iterative method (8) stays in K. for L. Since K So and 5 < A we know that J3 () is well defined. In addition, we have:
|| k V/l
nL S.
(B.1)
where we use the fact that Js is Li-isscciizz on the sublevel set S and S E. Therefore we have K S by Remark 3.5 and Js (sKK) is well defined. Since Ja is I, Lipiscccit with the el, v Lipschtiz gradient, we have:
cL.VI Vd
J&(K') - Js(kk) & (VJo(K"), K' K0) + 17
[Ja(K))
28
(172 cli Vd 1))l [)]lFJss
25
S " (K )|
2
where the last inequality holds since we have < r7 min ( siival Therefore, we have
Js(K') S (kK).. This implies:
J(K')= S Js(K') + 5L, S (KK) ōL, S J(K") + 28L, S 50J(K').
(B.2)
Hence we have Kt Sa. Repeating this argument, leads the fact that Kt 8 for all t. Thus:
Jo(K - Jo(K') (VJss() k++1 K2) + +12 cLi vd
[J((K))
26
S J((kk) - 2 VJa(K')
Rearranging terms of the above inequality yields:
VJs(K*) )|? S Js(K') J.(
Summing up the above inequality over t 0,1, ... T - 1 gives: [JJ{( Js(K - -J(KTT)
J&(K - J
7
T
where we use the inequality Jo(KT) 2 l by definition of J&(K). Therefore, we have:
VJs(K*) 2(Js(K)) - J*)
min
[]]b(K)) )1 <
1=0.1.-
1/T
Therefore, have:
2(J5(K))-
min 1=0,1,- T-1
1)
and the sample complexity result follows. This completes the proof.
17

---

B.4 Proof of Theorem 3.7
We first provide several technical lemmas which will be useful for proving Theorem 3.7. To this end, let Fi denote the filtration o (K* S t) for each = 1,2,- ,
Lemma B.1. Suppose J&(K) = 49JJ(K() and 8 = J(K"), Then we have K E S
Proof. Since Js(K) is well defined, we must have K. by definition of Jg. Then Proposition 2.3 (i) implies that J(K) I Js(K) + 8L1 I 49J(K)) + - L1 50J Hence we have K 8
Lemma B.2. Suppose that J(K) Li-Lipschitz on the sublevel set S and let T and Jt-0 be generated by Algorithm I such that {K') are feasible and (Js(K*)) are well defined. Then, we have
E[g" Fi = (.a(
(B.3)
Bllg / || Fi < 16
(B.4)
Proof. The proof can be found in [46, Lemma D.I]. We omit it here.
Lemma B.3. J(K) is Lo Lo-Lisschitz on the sublevel set 80, let y S ((100)(K))-5) and S
28g
min A}, then long as Kt E SS, we will have K 8 and
EjJs(K+11) Fil S Jo(K') V nZ,
(B.5)
where Z - 11= 21 edd L
Proof. Since || || = 1, we have:
|K K' = n/ (J(K' + SW4) J(K' -OW9)W"lle
nd
(J(K* +OW)) - J(K- -OW")
28
nd
28 (100J(RR)) - J*)
where the second inequality holds since we have K oW E S² when < A. This implies that K*+1 E St by Remark 3.5. In addition, K*+1 E S² and < Ai ensures that Ja (K+++) is well defined. By Proposition 2.3 (ii), we know that J5(K) is differentiable and Li-iishhitz with eLivd Lipschitz gradient the sublevel set S!, Then have:
Jo(K*+)) S "o((K))n(VJssi))
1
(B.6)
28
Taking the expectation on both sides conditioned on F, and using Lemma B.2 yiclds
T Vd
B[Jx(K+H)) [F] < - -VV)( Big² [F)) +
Ellls
E
Fi
28
LIdLivd 16 16v2
S -
28
= -((K"))>\\v>]((())) nZ,
with 7 1/(8 3d 3/2 2 138-1, This completes the proof.
Now we are ready to prove the Theorem 3.7. We will first prove Statement in Theorem 3.7: all the generated controllers are within the feasible set with high probability. Then we will show Statement 2: the Algorithm I returns (6, -tsttioioy point with high probability.
18

---

Proof of Statement 1 We first define a stopping time T as below:
:: min(t E (0, 1,, ... T } Jo(K') > 49J(K*)}
(B.7)
Based on Lemma B.1, it can be seen that long as 2 T the iterates {K*)T=) generated by Algorithm are feasible. Therefore our goal becomes bounding the probability Pr(r S T - 1). To this end, we can define nonnegative supermartingale Y (t) as below
(t) == Já (Kmin(tr)) + (T t)nZ.
(B.8)
To show it is supermartingale, noticing that we have
E[ + 1) Fi] = E[J Fi) [[ 1 Fil (T 1)mZ
(i) + B[Js(k*+
[i] + (7' - - 1)n2
Su) Jo(K + -> || + 22 -t- 1)n2
S Jo (K + -1)
where in equality (i), 1 well defined by the definition the 7; in particular, we have Js(K*) < 49J hence Kt E 8 by Lemma B.I and we can apply Lemma B.3 to obtain inequality (ii). Then Doob's 's maximal inequality for super martt-nartnngales gives
Pr(r S 1) Pr( 1,,,,,,-,TT- T- V(() > 49J(K"))
[O) Ja(K + +TZ
J(K') + 8Th1 TnZ 5() 49J(Kg) 49)(K))
( (K))
TnZ
(1) 49
49J(K'O)
where inequality (i) uses Lemma 2.3 and (ii) is true since
< J(K') bu
For sufficiently small e, we
have 17 = 3500 then one can verify that T T'z
6e2
1/2xV 25
J (KK).
Therefore, we have
TnZ 2
2TT
Pr(r T -T
< 0.05 + 0.01e.
49)(
49
1225
100
This implies that all the iterates K are stabilizing with probability least 1 (0.05 + 0.01v) 0.95 0.01v. This completes the proof for Statement 1.
Proof of Statement 2 We first show that
extend (B.5) as (K 1 Fi] S (((K") - VI
+ 7 If then know Jo (K*) 49)(K"), hence J(K') J&(K*) 8L1 S (0)( have
(B.9)
K E S and K E St. Therefore, we can apply Lemma B.3 to show that:
B[Jo(K'+))L Lr
Fi] S B[Js(K++)) [
S Js(K') // J. IK + +
- - (K + 7Z.
On the other hand, if S f, we have
- Fi] = 0 - (k) 1 + 1/2
(B.10)
since Z 2 Therefore, (B.9) holds. Taking the expectation and rearranging the terms of (B.9) gives:
E[J + Z.
(B.11)
1
Summing up the above incquality over = 0, ,T ,T- - 1 yields
T
(KI]V), 5 Jo(KD) E[Js(K")) 11>2T] +Z.
TT
19

---

Since the cost function JKK is nonnegative, we have B[J5(K 1,>r] 2 0 and:
Js(K -[J[[K"" ) | 2 J(K") + őL1 ).
Hence we conclude that
2J(K2)
E [[]])
1,T 7.
By the choice of 1 and T', the above inequality becomes:
T-1
Σ B [[]J)
2J(K))
5 + 2
(
112
5 + -
8V 2t
T
n/
0
3500
Since the random count R (0,1,2,... ,T 1} uniformly sampled, we have
T-1 E[| VJA < 11
8v2
V]I 1>
3500
which implics
E| 00
Therefore, we have
Pr([VJJsK 2) - 24r7
26TST
- Pr(IIVJs 26
Pr(7 T
- [[]] Pr(r -
< . 0.08 24 100
v
+
where the second inequality uses the Markov's inequality. By Proposition 2.3 (iii), we have (JK(K E (K)). This implies that
Pr(min([1 H||: : H E 0sJ(K R) 2 c)) & ( Ir = + 0.13 + 0.01e.
Therefore algorithm can find (6, --stationary point with probability least 1 - (0.17e 0.13 + 0.01v) = 0.87 0.17 0.01v. This completes the proof for Statement 2.
Remark B.4. It worth mentioning that the choice of sublevels in sets in (9) is WI.OG. Tuning these two numbers entails trade-offs. On the one hand, a larger sublevel in set S yields higher probability as observed from the proofs of Theorem 3.7 where we are bounding the term Pr(7 T -1'-- 1) as an example. On the other hand, larger sublevel set also results in a larger Lipschitz constant L1 and smaller smooth radius ò, thereby worsening the complexity bounds.
B.5 Proof of Theorem 4.1
We first state several technical lemmas which will be useful in proving of Theorem 4.1.
Lemma B.5. Let P(z) = Ex= Paz k be a stable, discrete-time MIMO LTI system, where P = (Pr E Cna JkEz. is the impulse response of P(z) and T(P) (Pi-)) denote the Toeplitz operator associated with system P(z). Suppose for any given Euclidean unit vectors C* and
E Ch we define scalar sequence g = [0x = yy" Paot Juzz. Let G(z)
00 -* denote
the z-transform of the impulse response g and T(g) = (gi-)) be the corresponding Toeplitz matrix. For any given Euclidean unit vectors x and y, we can show:
[Tx(a)l & [Px(P)]I
(B.12)
where (P( and (x(g) are Nn, x Nn, and N x N upper-left submatrix of T(P) and T(g), respectively, ||
is the spectral norm of a given matrix.
20

---

Proof. Using the definition of gk: = Pk we can write (g) as:
90
y Poz
0
91
90
0
y P'a
(g(
9N-1
9N-2
90
Ly PN-1I
y PN-22
y" Poz
Po
0
(B.13)
y
0
0
P1
Po
0
:
y
PN-1
PN-2
Po.
X
(P)
Since ||-|||
|| 1, we have max (Y*) maxx (X)= 1.
[T maxx (Tn(g)) maxx (Y'TN(P)X)
S mux (Y*) 0 (TN m
(B.14)
max (P)) [PTx(P)]
which completes the proof.
Corollary B.6. Let P(z) and G(z) be defined lemma B.5, fix y (1, 1) and define the systems :=(2)==PP(9)) and (z) = -G(2)). We can show that:
|| S |7
(B.15)
Proof. This result can be shown by applying lemma B.5 to (7) and (z) and considering this fact that 1|Tx [I and [P*)]l converge to ||G || and | oo N + co, respectively. O
Now we are ready to extend [68] results of norm approximation of SISO system using the corresponding truncated Toeplitz matrix more general MIMO systems.
Lemma B.7. Let P(z) = Ek=o L Paz- be a stable, discrete-ting time MIMO LTI system with stability
radius & (0, 1). aix (1, and suppose that max (Po) I D. For all N 2 3, have that
(2) (ox 72) | (z)
[P(2)]| 1|Tx(P)) S C1
(B.16)
P(())
N2
(2)
1
+ C2
+ +1) (P)))ll
-7)5 N/
where || denotes the Hos -nom of the system p7(z) = 7P(rz), Ci 3/22(2 3π 3)*),, C2 = 9x²2² are universal constants.
Proof. We can write || as follows
|| ||||
max maxx (P(e()) maax ( (P()))))) wE[0,2m]
(B.17)
This means that there exists Euclidean unit vectors and such that || Pllcc 1 P(ehwa Jr. Now de- fine a SISO LTI system G(z) = y P(z)æ, which has the impulse response g = {9k- = y P&r kez.- Since P(z) is stable function, is G(z) and we have || PP
||G Additionally, regarding the stability radius of G, it can be derived that, bg < and E (tg: 1). Consequently:
||
yly" Poze Tmaz (P)) S D
(B.18)
Now we invoke Theorem 4.1 from [68]; for stable, SISO LTI system G(z) = -E + with fix (1g, 1) and |! < D, we have:
||G|| [ل)l < Ci DI|G* 11 - 7)) +| 12 7 1
| 12c0
N2 + +2 ||G (1 + 7) - 7)5 N'
C2
|| (1- 7)
-
From lemma B.5 and corollary B.6, we know that [gTx( S [Tx(P)]| and || |7 S || || |xx.
Also using this fact that ||||| = || lo we have
||| [Tx Sc
(B.19)
where G = P| (1- 1P
1
[1> N + C2 Pll
(1+x)11- N3.
21

---

Algorithm 2: Power iteration method to find the maximum eigenvalue of a matrix
Require: Given a positive semi-definite matrix M E R RRNRxXN and an initial vector v( E Rm,
for i 0, 0,1.
do
200) Mr(i-))
o())
A [u(t]] Mc())
end for Output: (m))
Lemma B.8. Given a positive semi definief matrix M E R-Nn,xNn, with factoriiaa
V*MV = diag( diaag(A1..... (A..... \Nn.)
Where V = [uI]...|UN__]] is orthogonal, A 2 A2 2... 2 ANnz 2 0 and A > O. Suppose we choose a ti such that "..... Aj E [I] - v/, A1]. Let the vectors u(i) be specified by Algorithm 2 and define 8g E x/)) by cos(Oo) = lu (0) For i = 0, 1... we have
( - -6 21
IA - A1l s tan(fo)² w++ A1
(B.20)
A1
Proof. The idea of our proof is based on the results in section 8.2.1 of [29]. Suppose (0) has the cigenvector expansion (0)) aιd1 + 02U2 + ... + ONn, UN,,, then
|t |0| [00) cos (0s) +
a az ... a'vnz=
and
[u(00jT 2i 22
Σ k= a3A13
Nn. 2
1 [100 Mc Mo())
Σ k= 0 X2
No.
and so
Σ
Nux 2 22 (2x - A1)
2 aE - A11
( A1l
2=
2 2i Σ k=
a7
Σ
ag 2i (Ax
A11)
kkjt1 a o2 (>x -x1)
Nn.
k
of x2?
af
1
28
dx
2i
+
()x -x1)
X1
A1
k=j+1
A2
Aj+1
24
1
+
A1
A1
01
A1
k=2
k=j+1
A2
Aj+1
25
S(0) tan(
16
+ A1
A1
A1
4b
21
< tan(
& +
A1
A1
where the inequality (4) follows from the fact that (an
1-a
and this completes the proof. 0
22

---

Corollary B.9. Let matrix M be given as lemma B.8, we can show that for each iteration i, minimize the upper bound in power iteration algorithm (B.20), and (B.20)
V2r
can be written
1A - >1 S (an(6))2>1 (1-
1
1 1
(B.21)
2i
Proof. Since the right hand side of incquality (B.20) is a convex function of dh, we can minimize it by setting its derivative with respect to y equal to zero. Define f(() tan(
(سي=))) 2
1 + A
we have:
A1 - v 28-1
('()) = tan(
1
2i
= 0
is straightforward to show that 2i(1)
A1
11
makes ('(() and substitute (5(() in
f(0), gives f(yii)) = (an( (1
(1
21 which completes the proof.
2/2
Now we are ready to prove Theorem 4.1. As mentioned before, cost function J(K) equal Ho norm of P(z). >l From lemma B.7, We can find the bound & (K) for (J(K) ||T (P) ((K). Also, using Algorithm 2 can obtain the model-free cost function (KK as J(K) v It is also well-known that vA1 < || and v || N + 0c. Now invoke lemma B.8 corollary B.9 and use M == Tx (P) "T (P)),, (P), we have
1
2n )
[(() (TN < ton)
1
2n-V/n
_ ))
I t
1
1
2n
2n
2m
is easy to show that
(i(K) (P)ll < (an()))
(1-
(1
2m )
2n-V/2n
In addition, for > 1, one can verify that
1
1
2n 2/
2n
and hence (J(K) (P) S Pll + = (2(K) with C3 tan(0))². This gives us sample
complexity (16). Finally, applying triangle inequality, we have
[J(K) - ((K) s [J(K) |[Tx (P) - J(K) S (K()+ which completes the proof.
+ +<()
(B.22)
B.6 Proof of Theorem 4.2
We consider that we have inaccurate function value estimation J(K) J(K) <(K), here assume that the estimation error ((K) is uniformly upper bounded for all E S as stated in (18).
Then have:
d
g' (j(k + +8w*) - j(K' WW
20
d
(J(Kt +WW") - J(K* SW") (c(K"+
+ - - -oW))
28
28
= g" + d(cf - (b) W²
28
where we denote Ç = <(K' + SW*) and C <(K" SW*) for simplicity. To prove Theorem 4.2, we first present some technical lemmas.
23

---

Lemma B.10. Suppose that J(K) is L1 Li-Liscchtzz on the sublevel set S' and let {g') and {K" It=0 be generated by Algorithm I such that { (K Ft=0 are feasible and (J{(K*)) are well
defined. Then, we have
||_| FFl - VoJ(K*))l S de | ||
(B.23)
8
dk
FF. - 32v 2md + +2( )2
(B.24)
8
Proof. By definition of g', have:
d(ci
(2)
Fil
V&J(K*))F=
g +
W Fe - VoJ(KK')l
28
= |IE 19¹ FF
+
E
ddcs
(
W" Fi
VoJ(K())le
28
d(c)
(E
|IB
W
F
1|F
28
d(si (2)
dn
1 E
||||
Fi
28
|1 + d(s) - (2
B|1b'1| Fel E
W
||:
F
28
d(ci
(2)
s 2 [F. + 2F|
Fil
25
dr
< <32v2ndL
+ 2(
This completes the proof.
Lemma B.11. J(K) is L Li-Lisschitz the sublevel set St let n S
68
and 8 S
min(Ar, A}. then as long as Kt E S we will have Kt+1 S¹ and
{[ Fi] S J&(K*) - 17 VJ]JJ + 1 + Z2),
(B.25)
where Zi Lidx and Zn = zr with r cLi cLiVd 216 3 (4x)))
Proof. Since || 1, we have:
|K K' = 1/l d (j(K* + &WW) - j(K (((K"&W""))n W
25
nd
(J(K* +8W") J(K SW 1st cá
28
ndn
(100J(KK) Jr)
SE
where the second inequality holds since have KJ + SW E S when 5 < A and | - -66 2k. This implies that K*41 E S by Remark 3.5. In addition, K*+1 E S and < A ensures that Jo (+( is well defined. By Proposition 2.3 (ii), we know that Js(K) is differentiable and
L1 Lipschitt with cLivd Lipschitz gradient on the sublevel set St, Then we have:
on2 L1 vd
J 5 -J(KK) -V(VV)(K"))))))
l
28
24

---

Taking the expectation of both sides conditioned on K", we have
F.)) L
B[Ja(K())) Fi] (
1 Fil
20
5 Jo(K') - (V..( VJb(K*) - VJa(K') Blg Fi)) , r
500 J(KK - "IIV P/ m V ElO' Filll r + " r
Li rf
S(m) Jo(K*) - (00C)-~/VVJJ(H / + 5
8
= -
+ 11 n/22.
where inequality (i) and (iii) use the bounds in Lemma B. and (ii) holds by Cauchy- inequality. This completes the proof.
Now are ready to prove the Theorem 4.2. We will first prove Statement in Theorem 4.2: all the generated controllers are within the feasible set with high probability. Then we will show Statement 2: the Algorithm I returns a (6, e) -stttionnyyy point with high probability.
Proof of Statement 1 We first define stopping time as below:
:: min(l E (0, 1,,1,2,... 7 - 1} : J&(K') > 49J(K*)}
(B.26)
Based on Lemma 3.2, it can be seen that as long 2 T - 1, the iterates {KT) =t= generated by Algorithm are feasible. Therefore our goal becomes bounding the probability Pr(r S 1). To this end, we can define nonnegative supermartingale Y (t) as below
Y(t)= == Js( (/(mimi(t))))) + n - (Z + Z2).
(B.27)
To show it is supermartingale, noticing that we have
E| ( + 1) [5] = B[J{( Fi] [[Js(K(*)))))))) 1 Fi] nTT - - 1)(21 + Tz)
[F] + (T - 1-11-1111 1)
+ -72)
(0) 1 "|
|| 7(2 + +22) + (T -t- 1)(21 + +Z2
S Js (s((miin(ttr)) (T (Z + Z2) = Y(t),
where the inequality (1) uses (B.25). This is valid since 7 > t implies J&(K') I 49J(K*)) by the definition of r. Then we have J(K)) < Js(K') + 8L, S (0) Hence we have K E S The choice of 1 guarantees that K*+1 E S Hence K is feasible and Js (+)) is well defined when 5 < A,. Then Doob's maximal inequality for super-martingales gives
Pr(r < - 1) < Pr( max
Y()) > 49)(K())
1=0,1,- TT-1
(0) Jo(K") + TT(Zi + Z2)
J(KK) -0L 49J(KK))
Tn(2i + 2z) 49J(KK)
49J(K()
2 + Tn(Zi + 7z)
49
(K)(
For sufficiently small e, we have " Toor then can verify that Tni 22) S vJ(KK) ( by the choice of T, 1), and k. Therefore, we have
8x2
2
TnZ 49J(K))
2
v
Pr(r < - 1)
+
<
+
< 0.05 + 0.03v.
49
49
49
This implies that all the iterates Kt are stabilizing with probability least (0.05 + 0.03v) 0.95 0.03v. This completes the proof for Statement 1.
25

---

Proof of Statement 2 We first show that we can extend (B.25)
([Ja(K+)) 7 Fi) S Jo = V>>>
7 7//2,,
(B.28)
r > then we know J8 (5(K)) - ), hence J(K)) - Jb(K*) + 8L1 & 50J(KK), we have
Kt 8 and Ktt1 E S Therefore,
can apply Lemma B.3 to show that:
E 112444 Fil - B[Jo(K* Fi]
- Jo(K)) - "/llv/////)))) + +11 +122
=
||
+ 7211 + 7Z2.
On the other hand, if S (, we have
B[Js(K++1) ,,,+1 Fi]
/ +|? 1/11 + n/2 (B.29)
since Z1 2 and Zz 2 Therefore, (B.28) holds. Taking the expectation and rearranging the terms of (B.28) gives:
[ (KJ,(K')
[[Ja(K 1124l
+ +1 + Zz.
(B.30)
Summing up the above inequality over t 0,1, T 1 yields
T-1
T-1
Σ
BIll (K 112
T
1=
) ([Js(KT) )
+ Zi Zz.
n/
Since the cost function J(K) is nonnegative, we have B[Ja(KT) 1>>7] 2 and:
1 (
)KK)
+ 11 + Zz.
T
v/
By the choice of and T, the above inequality becomes:
T-1 E JJ (K)
J(K
2 +
2 2
+ 21 + Z2
1)
+ 21 $
+
T
1/T
V
100
Since the random count R E (0,1,2,....
1} uniformly sampled, have
1
2
B R)
22)
+2)
T
100'
which implics
Therefore, have
Pr([
2r 2
< P2 P
< 1 [I]IJJ(( [|,s]- + Pr(r T
< 0.15u - 0.15 0.05 + 0.03c
= 0.150 + + 0.03v,
where the second inequality uses the Markov's inequality. By Proposition 2.3 (iii,, we have (KK(K E R.KR). This implies that Pr(min [ [| H e (K R) 2 <t) S Pr( 2 S 0.15v + 0.2 + 0.03v.
Therefore our algorithm can find a (6, e e)-stationary point with probability at least 1 - (0.15u 0.2 0.03v) 0.8 -1 0.03c. This completes the proof for Statement 2.
26

---

C Numerical Experiments
In this section, we provide more details the numerical experiments. All the experiments are performed on desktop computer with a 3.7 GHz Intel i5-9600K processor.
C.1 Two-dimension example
In this subsection, we first present an example where the iterates of Algorthm can be visualized in controller space directly. In particular, consider the following system
0.5
0
-
-1
I
1
1
0
A
0.5
0.5
B
(C.1)
0
0
1
0
0
0.5
The weight matrices Q and R are set as identity matrices with proper dimensions. In this case, we stable matrix, we initialize Y = [0 0). For Algorthm
have [k1 kz] RIx2 Since
10-3 The iterates and contour lines of the Hox norm are drawn in Figure 2. It can be seen that Algorithm I yields to a local minimum and after 5000 iterations, it converges controller K 0.1429 -0.6425..
set 17 1 10-3 5 1 x 10-4 and
0.2
0.1
0
K10
-0.1
-0.2
65
-11
-15
-1
-0.8
-0.6
-0.4
-0.2
0
0.2
k2
Figure 2: Algorithm 1 iterates in controller space for (C.1).
C.2 Experiments for Figure!
this subsection, we discuss more details about three different experiments displayed in Figure to show the effectiveness of Algorithm I with exact and inexact oracle.
Left plot of Figure 1 For the left plot Figure 1, we show the relative error the Algorithm
with exact oracle for different system dimensions n. {10, 50, 1003. The system is of form (1) with parameters ( (A, B, C). The entries of [A, B. C)) are sampled from a standard normal distribution (0 1). The system matrix A is scaled when necessary make p(A) < 1 such that as zero matrices. The cost matrices Q and R are set to be identities with appropriate dimensions. Table 2 shows the detailed algorithm parameters.
K
Table Algorithm parameters
(Nay Buy nyy)
7
(10, 5)
1 x 10-6
1 10
1 10
(50, 10, 10)
1 10-7
x 10-4
10-3 1 10-3
(100, 20, 20)
1 10-9
x 10-1
27

---

Middle plot of Figure and inexact zeroth-order oracles. In particular, we consider the following specific MIMO system:
For the second experiment, we perform the Algorithm I with both exact
0.5
1
0 C
1 1
=
0.5
0.5
0
0 0011
(C.2)
0
0
0.5
1 0
The weight matrices Q and are set as:
2
-1
0
1 0
0 1
Q =
2
-1
R
1
0
-1
2
Since the system matrix A is Schur stable, set the initial point K the smooth radius = 0.001 and the stepsize 7 = 0.0001. can be seen that the inexact oracle case works well and tracks the exact oracle scenario.
matrix. We also set
Right plot of Figure Finally, we examine how the sample complexity varies with different e for the exact oracle setting with system matrices (C.2). It is worth mentioning that in Algorithm 1, we cannot really determine whether an iterate K is a (Ó, e)sttaiionayy point or not since we cannot calculate the exact (.K').). In practice, we use the magnitude of g as stationarity criterion. In particular, we terminate the algorithm when the norm of g is less than c.
AC15
x 10
HF2D11
40
9.5
Algorithm HIFOO
Algorithm 1
9
HIFOO Hinfstruct
Hinfstruct
30
J(K)
J(K
8.5
8
20
7.5
10
7
0
1000
2000
3000
4000 5000
0
1000
2000
3000
4000 5000
Iterations
Iterations
DLR2
HE4
5000
120
Algorithm
Algorithm
HIFOO
100
HIFOO
Hinfstruct
Hinfstruct
4500
J(K)
80
60
40
4000
20
1000
2000
3000
4000 5000
0
1000
2000
3000
4000 5000
Iterations
Iterations
Figure 3: Algorithm trajectories for selected the library examples.
C.3
Comparison with model-based methods
In this subsection, we compare our derivative-fre methods to model-based packages HIFOO and Hinfstruct, which available in MATLAB. In particular, we select several benchmark models from COMPI,ib including aircraft model AC15, 2D heat flow model HF2D11, second-order model DLR2, and helicopter models HE4 [41]. Table 3 summarized more details the selected examples.
worth mentioning that the models in COMP1,ib are all continuous time models. In addition, the implementations of HIFOO and Hinfstruct are also based continuous-time models. Therefore,
28

---

Table 3: Selected examples form COMPI.
Physical model
Example
(Nzz Ru: Ny)
Structure of A
Stability of A
Air craft model
AC15
(4,
dense
stable
2-D heat flow model
HF2D11
(5.
dense
unstable
second-order model helicopter model
DLR2
(40,
sparse
stable
HE4
(8,4,
dense
unstable
implemented the continuous-time version of Algorithm In other words, when we compute the Hox norm of the closed-loop system, we are computing the H.s norm of continuous-time system instead of discrete-time system. Figure 3 shows the trajectories of the four selected examples when we run Algorithm for 5000 iterations. It can be seen that our algorithm converges to the ones computed by the model-based methods HIFOO and Hinfstruct with proper initialization. In practice, one can use multiple initial points and run Algorithm multiple times then just report the best case with the lowest J (K) ). Such strategy is used in HIFOO and Hinfstruct. can be seen that our derivative-free method can achieve comparable results even without the knowledge of the system dynamics.
29


Reviews:
[{"review_id": "nGzYhAX5uC", "reviewer": "Reviewer_v5nm", "summary": "This paper studies the static output feedback $\\mathcal{H}_{\\infty}$ control problem. It proposes a derivative-free policy optimization algorithm via randomized smoothing and further provides sample complexity analysis for the cases with exact and inexact zeroth-order oracles. To validate the performance of the new algorithm, the authors also conduct some numerical experiments and compete against the model-based methods in the literature. ", "questions": "None.", "limitations": "None.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. As the authors claim, the proposed algorithm is the first derivative-free policy optimization algorithm for constrained structured $\\mathcal{H}_{\\infty}$ control problem (there have been some works on the unconstrained setting).\n2. The authors also consider the inexact oracle setting.\n3. The paper provides both theoretical analysis and numerical experiments.", "weaknesses": "I am not very familiar with the problem studied by this paper and it looks fine to me. However, I feel like the paper is mainly a combination of existing techniques (such as randomized smoothing and gradient sampling with zeroth order feedback). Would the authors highlight any novel techniques they apply in the analysis or explain what makes the problem different from other nonsmooth nonconvex problems such that this paper is not simply A+B?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's time and effort in evaluating our manuscript. We value your insightful comments and suggestions. Below are our responses.\n\n**Would the authors highlight any novel techniques they apply in the analysis or explain what makes the problem different from other nonsmooth nonconvex problems such that this paper is not simply A+B?** \n\nWe thank the reviewer for the valuable comment. We would like to highlight the novelty of our main results presented in Theorem 3.6, 3.7, and 4.2 in twofold: \n\n1. **Feasibility of the generated controllers.** In our control setup, unlike the unconstrained optimization problems, we need to ensure that the iterate $K^t$ and the perturbed iterate $K^t \\pm \\delta W^t$ stay within a non-convex feasible set (namely, the set of stabilizing policies). Previous work on policy optimization theory of $H_\\infty$ control addresses this feasibility issue via using the coerciveness of $J(K)$ and mainly relies on the fact that $J(K)$ is a barrier function on the non-convex set of stabilizing policies. Such previous results rely on model-based algorithms (such as Goldstein's subgradient method) which can decrease the value of $J(K)$ directly. In our paper, we consider the model-free setting and hence need to use zeroth-order policy optimization. However, the zeroth-order policy search can only decrease the value of the smoothed function $J_\\delta(K)$, which is not coercive over the non-convex feasible set and hence cannot be used as a barrier function. Importantly, the descent of $J_\\delta(K)$ does not imply the descent of the original function value and hence does not ensure feasibility by itself. As a matter of fact, how to choose $\\delta$ to ensure that $J_\\delta$ is well defined is already non-trivial. Consequently, we need to design the smooth radius $\\delta$ carefully (as indicated in Theorems 3.6, 3.7, and 4.2) to ensure the feasibility of the iterates. \n\n \n\n2. **Inexact Oracle.** For Theorem 4.2, we consider the inexact oracle case which is particularly relevant for the model-free control setting. Specifically, we are using imperfect estimates of $J(K)$ that are calculated using the model-free MIMO power iteration method. Therefore, an extra statistical error term appears in the iterations of zeroth-order policy optimization, and requires special treatment. Such an extra term has not been considered in the literature of zeroth-order optimization for nonconvex nonsmooth problems. To address this extra technical difficulty, we first establish sample complexity bounds for $H_\\infty$ norm estimation of the general MIMO system. Then we carefully propagate such sample complexity bounds to obtain an error bound for $\\nabla J_\\delta$ in terms of $\\epsilon$ and $\\delta$.\nBuilt upon this, we demonstrate that Algorithm 1 remains effective even with an inexact oracle, ensuring the feasibility of the iterates while achieving finite-time sample complexity with high probability. The inexact zeroth-order oracle has not been considered by any previous papers. "}, {"review_id": "Vx1ClauD68", "reviewer": "Reviewer_vRAL", "summary": "This paper focuses on the structured $H_\\infty$ control problem. They provide sample complexity bounds for policy optimization in $H_\\infty$ control problem. \nThe results are provided for two separate scenarios namely: \n- Exact Oracle Setting  (exact $J(K)$ for any $K$ is available, for the given closed loop system)\n- Inexact Oracle Setting (the system matrices are not known)\n\nThe theoritical results provide the sample complexity of $H_\\infty$ norm estimation.\nFinally, the paper provides a few numerical experiments supporting their theoritical results along with comparison to some model-based approaches. ", "questions": "Following are my concerns/ questions regarding the paper.\n- Can authors explain why they call this approach as \"derivative free\" approach since calculating $g_t$  is required in the algorithm?\n- I would like to know the motivation behind considering the two separate type of oracle scenarios. \n- Authors mention that their probability bounds can be sharpened (line 248), I request authors to present the best possible results in the main body of the paper.\n\nI also request authors to address the comments in the weakness section if possible.\n", "limitations": "The results rely on access to an oracle.\n\nSocial Impact: NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- $H_\\infty$ control problem is one of the important setting in linear systems , which is well studied in adaptive control literature but has received less attention in recent learning theory literature unlike the standard LQR setting. The paper highlights the various challenges involved in the analysis of $H_\\infty$ control due to non-convexity and non-smoothness.\n\n- The Sample complexity of the $H_\\infty$ norm estimation are provided by exploiting the randomized smoothing techniques.\n\n", "weaknesses": "- The algorithm relies on access to an oracle. More discussion on the oracle is warranted. \n- The simulation section in the main body (as well as the appendix) of the paper is meager. The presentation quality of plots included can be improved. \n- Authors mention in the appendix that (line 806) that when necessary, one can reinitiate to avoid bad local minima, but how would one know that they are at a 'bad' local minima.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking time and effort to review our manuscript. We sincerely appreciate all your valuable comments. Please see our responses below.    \n\n**More discussion on the oracle is warranted.**    \n\nWe appreciate the valuable suggestion from the reviewer. Our paper considers two zeroth-order oracles: the exact oracle is standard for zeroth-order optimization literature and natural for the model-based control setting, while the inexact oracle is relevant for the model-free learning-based control setting. The exact oracle assumes that we can exactly calculate $J(K)$ (which is the closed-loop $H_\\infty$ norm) for every stabilizing $K$.  When the system dynamics are known, such an oracle is available since the closed-loop $H_\\infty$ norm can be efficiently calculated using existing robust control packages in MATLAB (currently, the state-of-the-art techniques for model-based $H_\\infty$ norm calculations rely on using the relation between the singular values of the transfer function matrix and the eigenvalues of a related Hamiltonian matrix [BBK1989,BS1990]).      \n\n[BBK1989] Boyd, Balakrishnan, and Kabamba, 1989. A bisection method for computing the $H_\\infty$ norm of a transfer matrix and related problems. Mathematics of Control, Signals and Systems.    \n[BS1990] Bruinsma and Steinbuch, 1990. A fast algorithm to compute the $H_\\infty$-norm of a transfer function matrix. Systems & Control Letters.    \n\nHowever, in the model-free learning-based $H_\\infty$ control setting, the system dynamics are unknown, and $J(K)$ (the closed-loop $H_\\infty$ norm) can only be estimated from the input/output data of a black-box simulator of the underlying system. The inexact oracle is natural for such a model-free setting and can be provided by model-free $H_\\infty$ norm estimations methods (see the beginning of Section 4.1 for a review). Our paper uses the model-free time-reversal power-iteration-based $H_\\infty$ estimation from [WSH2010] to serve as the inexact oracle for $J(K)$. Despite the existence of such algorithms, the prior literature lacks sample complexity bounds for general MIMO systems. Therefore, we first present the first sample complexity result for $H_\\infty$ norm estimation for general MIMO systems in Theorem 4.1. Building upon this, we obtain the first sample complexity results for model-free policy optimization of $H_\\infty$ control with noisy function values. We will add more discussion on this in the revised manuscript.     \n\n[WSH2010] Wahlberg, Syberg, and Hjalmarsson, 2010. Non-parametric methods for $\\ell_2$-gain estimation using iterative experiments. Automatica.    \n\n**The simulation section in the main body (as well as the appendix) of the paper is meager. The presentation quality of plots included can be improved.**    \n\nWe thank the reviewer for the constructive comments. We agree with the reviewer that the presentation quality of the plots should be improved. We have revised the plots via proper scaling and adding more explanations. Please see our uploaded one-page pdf file. If the reviewer has more concrete suggestions, please let us know. Any comments are highly appreciated and we will revise accordingly.  \n\n**How would one know that they are at a 'bad' local minimum.**    \n\nThat statement is misleading and we will revise it. In practice, one can use multiple initial points and run the algorithm multiple times then just report the best case with the lowest $J(K)$. Such a strategy is used in existing packages such as HIFOO and Hinfstruct. So one does not explicitly check whether the solution is a bad local minimum or not. In general, there are no polynomial-time guarantees for finding the global solutions of such nonconvex problems.   \n\n**Can authors explain why they call this approach as \"derivative free\" approach since calculating $g_t$ is required in the algorithm?**    \n\nIn Algorithm 1, we use the function value $J(K)$ to build an estimation of $\\nabla J_\\delta J(K)$. The function value is typically referred to as “zeroth-order oracle” in zeroth-order optimization literature. The methods that use zeroth-order oracle are referred to as derivative-free methods or zeroth-order methods [GL2013, CSV2009].    \n\n[GL2013] Ghadimi and Lan, 2013. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization.    \n[CSV2009] Conn, Scheinberg, and Vicente, 2009. Introduction to derivative-free optimization. SIAM \n\n**Motivation behind considering the two separate types of oracle scenarios.**    \n\nWe first study the exact oracle case, which is a standard oracle assumption in zeroth-order optimization literature. This oracle can be obtained when the system matrices are known (model-based oracle). Building upon the complexity results under this assumption, we further extend our analysis to a more practical context: the inexact oracle scenario, where we only have access to a black-box system simulator for generating imperfect estimates of $J(K)$.  This aligns more closely with learning-based control where system models are unknown (model-free oracle).     \n\n**The best possible results in the main body of the paper.**    \n\nWe are sorry for the confusion here. We really mean that the constant factors of the probability bounds in Theorems 3.7 and 4.2 can be improved by e.g., increasing the level of $\\mathcal{S}^1$, using smaller step sizes, using smaller smooth radius delta, etc. For example, in the proof of Theorem 3.7, if we choose a larger sub level of the set $\\mathcal{S}^1$, then we can obtain a refined constant term in the probability bounds.  However, we want to emphasize that refining the constant factors will not change the order dependence of $\\epsilon$ and $\\delta$ in the sample complexity results (Eq. 12, Eq. 21), which stands as the most crucial aspect of the sample complexity theory. The order of our curret sample complexity results is already the best as we can find. We will clarity this point in revision."}, {"review_id": "0SkEx6PQwQ", "reviewer": "Reviewer_UPcn", "summary": "This paper considers solving the $H_\\infty$ control problem using zero-th-order policy optimization. The main results are sample complexity bounds for both the exact Oracle setting and the model-free setting. Numerical simulations are conducted to demonstrate the effectiveness of the algorithm.", "questions": "From the numerical simulations, is it possible to tell what the convergence rate of the algorithm is?", "limitations": "The sample complexity bounds are not necessarily optimal, which was pointed out by the authors.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well-written. The $H_\\infty$ control problem is known to be challenging and the policy optimization results are likely to be of great interest to the learning-in-control community. The sample complexity result, while not necessarily optimal, is the first non-asymptotic result in the literature.", "weaknesses": "(1) Related Work: The related work section could be more structured. I went through [32] to complete the review of this work. It seems that the main technical tools are already developed in [32]. However, [32] does not provide any sample complexity result. What are the major technical challenges (and the ideas used to overcome them) in going beyond the global convergence in [32] to the sample complexity results in this work?\n\n(2) Theorem 3.7 and Theorem 4.2: Usually for high probability bounds, as the tolerance level $v$ decreases, more iterations are needed. However, for Theorem 3.7 and Theorem 4.2, as $v$ decreases, $T$ also decreases, which seems counter-intuitive. Moreover, the bound has a polynomial tail rather than an exponential tail. Is this an artifact of the proof or are exponential tail bounds not achievable?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking time and effort to review our manuscript. We sincerely appreciate all your valuable comments and suggestions. Please see our responses below.    \n\n**Related Work: The related work section could be more structured. What are the major technical challenges (and the ideas used to overcome them) in going beyond the global convergence in [32]?**  \n\nWe thank the reviewer for the valuable comment. For the $H_\\infty$ control problem discussed in [32], the policy update is performed using the minimum-norm element of the associated Goldstein’s subdifferential. The main idea is based on the fact that such a minimum-norm element is a descent direction of the original cost function $J(K)$. While in our work, we aim to obtain the sample complexity of the zeroth-order methods for solving structured $H_\\infty$ control problem. To this end, the zeroth-order oracle is used to construct an estimator of $\\nabla J_\\delta (K)$, which is a descent direction of the smoothed function $J_\\delta (K)$. We obtain our sample complexity results based on the fact that an $\\epsilon$-stationary point of $J_\\delta (K)$ is also a $(\\delta, \\epsilon)$-stationary point of the original nonsmooth cost function $J(K)$. Indeed, there are several technical challenges in developing the sample complexity via this approach:   \n\n1. **Feasibility of the generated controllers.** In our control setup, unlike the unconstrained optimization problems, we need to ensure that the iterate $K^t$ and the perturbed iterate $K^t \\pm \\delta W^t$ stay within a non-convex feasible set (namely, the set of stabilizing policies). Previous work on policy optimization theory of $H_\\infty$ control addresses this feasibility issue via using the coerciveness of $J(K)$ and mainly relies on the fact that $J(K)$ is a barrier function on the non-convex set of stabilizing policies. Such previous results rely on model-based algorithms (such as Goldstein's subgradient method) which can decrease the value of $J(K)$ directly. In our paper, we consider the model-free setting and hence need to use zeroth-order policy optimization. However, the zeroth-order policy search can only decrease the value of the smoothed function $J_\\delta(K)$, which is not coercive over the non-convex feasible set and hence cannot be used as a barrier function. Importantly, the descent of $J_\\delta(K)$ does not imply the descent of the original function value and hence does not ensure feasibility by itself. As a matter of fact, how to choose $\\delta$ to ensure that $J_\\delta$ is well defined is already non-trivial. Consequently, we need to design the smooth radius $\\delta$ carefully (as indicated in Theorems 3.6, 3.7, and 4.2) to ensure the feasibility of the iterates.  \n\n2. **Inexact Oracle.** For Theorem 4.2, we consider the inexact oracle case which is particularly relevant for the model-free control setting. Specifically, we are using imperfect estimates of $J(K)$ that are calculated using the model-free MIMO power iteration method. Therefore, an extra statistical error term appears in the iterations of zeroth-order policy optimization, and requires special treatment. Such an extra term has not been considered in the literature of zeroth-order optimization for nonconvex nonsmooth problems. To address this extra technical difficulty, we first establish sample complexity bounds for $H_\\infty$ norm estimation of the general MIMO system. Then we carefully propagate such sample complexity bounds to obtain an error bound for $\\nabla J_\\delta$ in terms of $\\epsilon$ and $\\delta$. \n\nWe will include a more structured related work section and highlight our contributions in the revised manuscript. We emphasize that our study is more relevant to the model-free learning-based control setting, since our sample complexity results address the model-free control directly.\n\n**Theorem 3.7 and Theorem 4.2: Probability bounds seem counter-intuitive. Moreover, the bound has a polynomial tail rather than an exponential tail. Is this an artifact of the proof or are exponential tail bounds not achievable?**  \n\nWe thank the reviewer for such an insightful comment. We agree with the reviewer that in general, more iterations are needed to decrease the tolerance level. Our results are also intuitive. Specifically, in both Theorem 3.7 and 4.2, Statement 1 suggests that as $T$ increases, the probability that all the generated controllers are stabilizing will decrease. This is because our algorithm uses zeroth-order oracle to build an estimator of the smoothed function gradient. As $T$ increases, the biases and variance of the gradient estimation accumulate, resulting in a larger failure probability. In addition, Statement 2 suggests that as $T$ increases, the probability of finding a $(\\delta, \\epsilon) $-stationary point will first increase and then decrease. This is also intuitive, when $T$ is too small, more iterations will improve the performance of the generated controllers, but for large $T$, the probability of generating unstable controllers becomes dominant. We will add the above discussions in the revised manuscript.   \n\nThe reviewer is right about the polynomial tail about our bounds. This is the result of the proof techniques, and our polynomial bounds match the existing one for unconstrained optimization.   \n\n **Convergence rate from the numerical simulations.**  \n\nFrom the left plot of Figure 1,  the convergence rate in terms of iteration vs. error looks sublinear.  This is consistent with our complexity theory which can be viewed as a \"sublinear rate\" result."}]

Author rebuttal:
We deeply appreciate the insightful feedback provided by the reviewers. In response to the comments from Reviewer vRAL, we have attached a PDF file containing the updated plots from the main paper. Each comment from the reviewers has been addressed below. We hope our explanations have resolved the reviewers' concerns. Please let us know if you have any additional questions or require further clarification, all comments are highly appreciated.

Meta-review: I appreciate the authors for conducting the rebuttal and the following discussions. Unlike most linear control sample complexity results that heavily rely on the fact that the cost functions in these benchmark problems are differentiable over the entire feasible set, this paper tackles the non-smooth $H_\infty$ control which can only access the zeroth-order oracle. The major contributions, the design for the smooth radius $J_\delta(K)$, iterations to ensure $K^t$ and $K^t+\delta W^t$ are stabilizing controllers, and the first sample complexity result via the model-free MIMO power iteration method, are significant to both NeurIPS and control communities. Therefore, I recommend the paper be accepted. Besides, as a small issue mentioned by reviewer UPcn, the authors should clearly discuss how the polynomial tail in the theorem compares to other control works and whether it is possible to further break it and attain the exponential tails in the final revision
Decision: Accept (poster)