Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
Year: 2021

Abstract:
Direct policy search serves as one of the workhorses in modern reinforcement learning (RL), and its applications in continuous control tasks have recently attracted increasing attention. In this work, we investigate the convergence theory of policy gradient (PG) methods for learning the linear risk-sensitive and robust controller. In particular, we develop PG methods that can be implemented in a derivative-free fashion by sampling system trajectories, and establish both global convergence and sample complexity results in the solutions of two fundamental settings in risk-sensitive and robust control: the finite-horizon linear exponential quadratic Gaussian, and the finite-horizon linear-quadratic disturbance attenuation problems. As a by-product, our results also provide the first sample complexity for the global convergence of PG methods on solving zero-sum linear-quadratic dynamic games, a nonconvex-nonconcave minimax optimization problem that serves as a baseline setting in multi-agent reinforcement learning (MARL) with continuous spaces. One feature of our algorithms is that during the learning phase, a certain level of robustness/risk-sensitivity of the controller is preserved, which we termed as the implicit regularization property, and is an essential requirement in safety-critical control systems.

heading: 1 Introduction
text: Recent years have witnessed the rapid development of reinforcement learning (RL) methods in handling continuous control tasks [1, 2, 3]. Central to the success of RL are policy optimization (PO) methods, including policy gradient (PG) [4, 5, 6], actor-critic [7, 8], and other variants [9, 10]. Progress reported in the literature has clearly shown an increasing interest in understanding theoretical properties of PO methods for relatively simple baselines such as linear control problems [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]. However, the theory of model-free PO methods on risk-sensitive/robust control remains underdeveloped in the literature. Since risk-sensitivity and robustness are important issues for designing safety-critical systems, it is natural to bring up the questions of whether and how model-free PO methods would converge for these continuous control tasks.
Our work in this paper is motivated by the above concern, and studies the sample complexity of model-free PG methods on two important baseline problems in risk-sensitive/robust control, namely the linear exponential quadratic Gaussian (LEQG), and the linear quadratic (LQ) disturbance attenuation problems. The former covers a fundamental setting in risk-sensitive control, and the latter is an important baseline for robust control. Based on the well-known equivalence between these problems and LQ dynamic games [22, 23, 24, 25, 26], we develop a unified PO perspective
\Equal contribution. K. Zhang is with the LIDS and the CSAIL at the Massachusetts Institute of Technology. Email: kaiqing@mit.edu. X. Zhang, B. Hu, and T. Başar are with the Department of ECE and the CSL at the University of Illinois at Urbana-Champaign. Emails: {xz7, binhu7, basar1}@illinois.edu.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
for both. A common feature for the above two problems is that their optimization landscapes are by nature more challenging than that of the linear quadratic regulator (LQR) problem, and existing proof techniques for model-free PG methods [11, 17, 18, 19] are no longer effective due to lack of coercivity of the objective functions. Specifically, when applying PG methods to LQR, the feasible set for the resultant constrained optimization problem is the set of all linear state-feedback controllers that stabilize the closed-loop dynamics. The objective function of LQR is coercive on this feasible set and serves as a barrier function itself [14], guaranteeing for the PG iterates to stay in the feasible set and converge to the globally optimal controller. For the LEQG and LQ disturbance attenuation problems, the risk-sensitivity/robustness conditions have reshaped the feasible set in a way that the objective function becomes non-coercive, i.e. the objective value can remain finite while approaching the boundary. The objective is no longer a barrier function, and new proof techniques are needed to show that model-free PG iterates will stay in the feasible set. This is significant for safety-critical control systems with model uncertainty, as the iterates’ feasibility here is equivalent to risk-sensitivity/robustness of the controller (cf. Remark A.8), and the failure to preserve robustness during learning can cause catastrophic effects, e.g., destabilizing the system in face of disturbances.
The most relevant result was developed in [16], which proposes implicit regularization (IR) arguments to show the convergence of several PG methods on the mixedH2/H1 control design problem (which can be viewed as the infinite-horizon variant of the LQ disturbance attenuation problem studied in this paper). The main finding there is that two specific PG search directions (with perfect model information) are automatically biased towards the interior of the robustness-related feasible set. In [16], it is emphasized that IR is a feature of both the problem and the algorithm, contrasting to that the stability-preserving nature of PG methods for LQR problems is based on the barrier function property of the objective and hence is algorithm-agnostic. Although the idea of IR is relevant to PO problems with non-coercive objective functions, the arguments in [16] only apply to the setting with a known model, since they rely on a specialized perturbation technique which may potentially generate arbitrarily small “margins". However, in the model-free setting, a uniform margin is required for provable tolerance of statistical errors. See a detailed comparison of the literature in §A.1.
In this paper, for the LEQG and LQ disturbance attenuation problems, we overcome the above margin issue and obtain the first IR result in the model-free setting. This enables the first model-free PG method that provably solves these control problems with a finite number of samples. We highlight our contributions as follows.
Contributions. We provide the first sample complexity results for model-free PG methods for solving linear control problems with risk-sensitivity/robustness concerns (the LEQG and LQ disturbance attenuation problems), which were viewed as important open problems in the seminal work [11]. From the robust control perspective, one feature of our algorithms is that, during the learning process, a certain level of robustness/risk-sensitivity of the controller is proved to be preserved. This has generalized the results in [16] with a known model, and has thus enabled the finite-sample convergence guarantees of PG methods for risk-sensitive/robust control design. Our algorithms and sample complexity results also address two-player zero-sum LQ dynamic games in the finite-horizon time-varying setting, which are among the first sample complexity results for the global convergence of policy-based methods for competitive multi-agent RL. Second, in the context of minimax optimization, our results address a class of nonconvex-nonconcave minimax constrained optimization problems, using zeroth-order multi-step gradient descent-ascent methods. Finally, part of our results provide the sample complexity analysis for PG methods that solve the finite-horizon time-varying LQR problem with system noises and a possibly indefinite state-weighting matrix.

heading: 2 Background
text: We first introduce two classic settings in risk-sensitive and robust control, namely LEQG, and LQ disturbance attenuation, and their equivalence to zero-sum LQ dynamic games.

heading: 2.1 Linear Exponential Quadratic Gaussian
text: Consider the finite-horizon LEQG problem [22, 27, 28], with time-varying systems dynamics described by xt+1 = Atxt +Btut +wt , t 2 {0, · · · ,N 1}, where xt 2 Rm represents the system state; ut 2 Rd is the control input; wt 2 Rm is an independent (across time) Gaussian random noise with wt ⇠ N (0,W ) for some W > 0; the initial state x0 ⇠ N (0,X0) for some X0 > 0, which is
independent of {wt}; and At , Bt are time-varying system matrices. The objective function is given by J ({ut}) := 2 logEexp h 2 ⇣PN 1 t=0 (x > t Qtxt + u > t Rtut) + x > NQNxN ⌘i , where Qt,QN 0 and Rt > 0 are symmetric weighting matrices; and > 0 is a parameter capturing the degree of risk-sensitivity, which is upper-bounded by some ⇤ > 0 [23, 28, 29].
The goal in the LEQG problem is to find the J -minimizing optimal control policy µ⇤t : (Rm ⇥Rd )t ⇥ Rm! Rd that maps, at time t, the history of state-control pairs up to time t and the current state xt to the control ut . It has been shown in [22] that µ⇤t has a linear state-feedback form µ ⇤ t(xt) = K ⇤t xt , where K ⇤t 2 Rd⇥m, for all t. Therefore, it suffices to search K ⇤t in the matrix space Rd⇥m for all t 2 {0, · · · ,N 1}, without losing any optimality. The resulting PO problem as well as its closed-form objective function and PG are provided in §A.3.1.

heading: 2.2 LQ Disturbance Attenuation
text: Second, consider the LQ disturbance attenuation problem, with time-varying dynamical systems described by xt+1 = Atxt + Btut +Dtwt and zt = Ctxt + Etut , where xt 2 Rm is the system state; ut 2 Rd is the control input; wt 2 Rn is the (unknown) disturbance input; zt 2 Rl is the controlled output; At,Bt,Ct,Dt,Et are system matrices with appropriate dimensions; and x0 2 Rm is unknown. In addition, we assume that E>t [Ct Et] = [0 Rt] for some Rt > 0 for normalization, with no loss of generality (see §3.5.1 of [25] for a simple procedure that can transform the general problem into a form that satisfies this “normalization” assumption). Subsequently, we denote the `2-norms of the vectors ! := h x>0 C > 0 ,w > 0 , · · · ,w > N 1 i> and z := h z>0 , · · · , z > N 1,x > NQ 1/2 N i> as k!k and kzk = n C ⇣ {ut}, {wt} ⌘o1/2 , where QN 0. Then, the robustness of a designed controller can be guaranteed by a constraint on the ratio between kzk and k!k. Specifically, the goal of disturbance attenuation is the following: Given a > ⇤, where ⇤ = p ( ⇤) 1 > 0 is the optimal (minimax) level of disturbance attenuation at the output and recall that ⇤ is the upper bound for the risk-sensitivity parameter in LEQG [23, 25], find a control policy µt = Ktxt , t 2 {0, · · · ,N 1}, that solves min{µt } J ({µt(xt)}) subject to supx0,{wt } n C({µt(xt)}, {wt}) o1/2 /k!k < , where J ({µt(xt)}) is an upper bound of the LQG cost [30]. We defer the precise formulations of the LQ disturbance attenuation problem to §A.3.2. Also, see Remark A.3 for the challenges when addressing LEQG and LQ disturbance attenuation directly using derivative-free PG methods.

heading: 2.3 An Equivalent Dynamic Game Formulation
text: To overcome the challenges spelled out in Remark A.3, we now introduce an equivalent dynamic game formulation to the LEQG and the LQ disturbance attenuation problems due to that the natural PGs of the objective function of the game can be directly sampled (as we will show in §4). Under certain conditions to be introduced shortly, the saddle-point gain matrix of the minimizing player in the dynamic game (if exists) also addresses these two robust/risk-sensitive control problems. We aim to address these three classes of problems in a unified fashion. Now, consider a two-player zero-sum LQ stochastic dynamic game (henceforth, game) with closedloop perfect-state information pattern, characterized by xt+1 = Atxt + Btut + Dtwt + ⇠t , where xt 2 Rm is the system state, and ut := Ktxt 2 Rd (resp., wt := Ltxt 2 Rn) is the linear statefeedback controller of the minimizing (resp., maximizing) player1, which suffices to attain the saddle point whenever exists [26]. The initial state x0 and the additive process noises ⇠t are drawn independently from a distribution D and At,Bt,Dt are system matrices. Further, we assume that D is zero-mean, has a positive-definite covariance, and satisfies almost surely that kx0k,k⇠tk  #, for all t 2 {0, · · · ,N 1} and some constant #. The goal of the minimizing (resp. maximizing) player is to minimize (resp. maximize) a quadratic objective function, namely to solve the game
inf {Kt } sup {Lt } Ex0,⇠0,··· ,⇠N 1
"N 1X
t=0 x>t (Qt +K > t R u t Kt L > t R w t Lt)xt + x > NQNxN
# , (2.1)
1Hereafter we will use player and agent interchangeably. Also, restrictions to instantaneous linear statefeedback policies do not lead any loss of generality, as the results of §2.3 hold for general square-integrable policies, allowed to use the entire state history.
where Qt,QN 0, Rut ,Rwt > 0 are symmetric weighting matrices. Whenever the solution to (2.1) exists such that the inf and sup can be interchanged, the value (2.1) is the value of the game, and the corresponding policies are the saddle-point/Nash equilibrium policies. To characterize the solution to (2.1), we first introduce the following time-varying Riccati difference equation (RDE):
P⇤t =Qt +A > t P ⇤ t+1⇤ 1 t At , t 2 {0, · · · ,N 1}, (2.2)
where ⇤t := I + ⇣ Bt(Rut ) 1B>t Dt(Rwt ) 1D>t ⌘ P⇤t+1 and P ⇤ N = QN . From [26], whenever a saddle point exists, the saddle-point control policies are linear state-feedback (i.e., µ⇤u,t(hu,t) = K ⇤t xt and µ⇤w,t(hw,t) = L⇤txt), and the gain matrices K ⇤t = (Rut ) 1B>t P⇤t+1⇤ 1 t At and L ⇤ t =
(Rwt ) 1D>t P⇤t+1⇤ 1 t At are unique, where P ⇤ t+1 0 is generated by (2.2). Then, we introduce a
standard assumption that ensures the existence of the value of the game [25].
Assumption 2.1 Rwt D>t P⇤t+1Dt > 0, for all t 2 {0, · · · ,N 1}, where P ⇤ t+1 0 is generated by (2.2). Under Assumption 2.1, the value in (2.1) is attained by the sequence ⇣ {K ⇤t }, {L⇤t} ⌘ , where K ⇤t 2 Rd⇥m and L⇤t 2 Rn⇥m are gain matrices at the saddle-point/Nash equilibrium. Thus, we can replace the inf and sup in (2.1) with min and max, respectively. Some further notes on Assumption 2.1 are provided in Remark A.5, showing that it is not restrictive and is in fact “quite tight”. Lastly, we state the equivalences between three classes of problems, with its proof provided in §B.3.
Lemma 2.2 (Connections) For any fixed > ⇤ in the LQ disturbance attenuation problem, we can introduce an equivalent LEQG problem and an equivalent zero-sum LQ dynamic game. Specifically, if we set 1I ,Rt,C>t Ct,W in LEQG, 2I ,Rt,C > t Ct,DtD > t in the LQ disturbance attenuation problem, and Rwt ,R u t ,Qt,DtD > t in the game to be the same, for all t 2 {0, · · · ,N 1}, then the optimal gain matrices in LEQG, the gain matrix in the LQ disturbance attenuation problem, and the Nash equilibrium gain matrix for the minimizing player in the game are the same.
By Lemma 2.2 and Remark A.3, we will hereafter focus on solving the game formulation in §2.3 using PG methods. As a result, the minimizing controller we obtain solves three classes of problems introduced above altogether.

heading: 3 Policy Gradient Methods
text: For ease of analysis, we define x = h x>0 , · · · ,x > N i> , u = h u>0 , · · · ,u > N 1 i> , w = h w>0 , · · · ,w > N 1 i> , ⇠ = h x>0 ,⇠ > 0 , · · · ,⇠ > N 1 i> , Q = diag(Q0 N ),
A = 2 666664 0m⇥mN 0m⇥m diag(A0 (N 1)) 0mN⇥m 3 777775 , B = 2 666664 0m⇥dN diag(B0 (N 1)) 3 777775 , D = 2 666664 0m⇥nN diag(D0 (N 1)) 3 777775 , R u = diag(Ru0 (N 1)),
R w = diag(Rw0 (N 1)), K = h diag(K0 (N 1)) 0dN⇥m i , L =  diag(L0 (N 1)) 0nN⇥m . (3.1)
where diag(X0 N ) denotes the block-diagonal matrix with X0, · · · ,XN on the diagonal block entries. Some other notations are introduced in §A.2. Now, using the compact notations, we develop PG methods with exact PG accesses that provably converge to the Nash equilibrium of the game, (K⇤,L⇤) 2 S(d,m,N ) ⇥ S (n,m,N ), where S(d,m,N ) and S(n,m,N ) are the subspaces that we confine our searches of K and L to, respectively. In particular, we only search over K 2 RNd⇥(N+1)m and L 2 RNn⇥(N+1)m, and K ,L satisfy the sparsity patterns in (3.1), without losing any optimality. Then, for any (K ,L), the objective function G(K ,L) is given by
G(K ,L) = E⇠ h ⇠ > PK ,L⇠ i = Tr ⇣ PK ,L⌃0 ⌘ = Tr ⇣ (Q +K>RuK L>RwL)⌃K ,L ⌘ , (3.2)
where PK ,L := diag(PK0,L0 , · · · ,PKN ,LN ) and PKt,Lt , t 2 {0, · · · ,N 1}, solves the Lyapunov equation PKt,Lt = (At BtKt DtLt ) >PKt+1,Lt+1 (At BtKt DtLt) +Qt +K > t R u t Kt L > t R w t Lt , (3.3)
with PKN ,LN :=QN . Moreover, PK ,L, ⌃K ,L are the solutions to the Lyapunov equations
PK ,L = (A BK DL)>PK ,L(A BK DL) +Q +K>RuK L>RwL, (3.4) ⌃K ,L= (A BK DL)⌃K ,L(A BK DL)>+⌃0, ⌃0 :=E h diag(x0x > 0 ,⇠0⇠ > 0 , · · · ,⇠N 1⇠ > N 1) i >0, (3.5)
where ⌃0 > 0 is full-rank because x0,⇠0, · · · ,⇠N 1 are drawn independently from D which has a positive-definite covariance matrix. The solutions to (3.4) and (3.5) always exist and are unique because (3.4) and (3.5) are recursive formulas in blocks. Since kx0k,k⇠tk  # almost surely, for all t, diag(x0x>0 ,⇠0⇠ > 0 , · · · ,⇠N 1⇠ > N 1) F  (N +1)# 2almost surely. Next, define the following notations:
c0 := (N +1)#2, d⌃ :=m 2(N +1), := min(⌃0) > 0, HK ,L := Rw D>PK ,LD, EK ,L := ( Rw +D>PK ,LD)L D>PK ,L(A BK), FK ,L := (Ru +B>PK ,LB)K B>PK ,L(A DL), (3.6) GK ,L(K) := R u +B>ePK ,L(K)B, ePK ,L(K) := PK ,L(K) +PK ,L(K)D(Rw D>PK ,L(K)D) 1D>PK ,L(K). (3.7)
Our goal is to solve the minimax optimization problem minK maxLG(K ,L) such that G(K⇤,L)  G(K⇤,L⇤)  G(K ,L⇤) for any K and L. Some properties of G(K ,L) are presented in the following lemmas, with their proofs being deferred to §B.4 and §B.5, respectively.
Lemma 3.1 (Nonconvexity-Nonconcavity) There exist zero-sum LQ dynamic games such that the objective function G(K ,L) is nonconcave in L for a fixed K , and nonconvex in K for a fixed L.
Lemma 3.2 (PG & No Spurious Local Minimum) The PGs of G(K ,L) can be computed as rKG(K ,L) = 2FK ,L⌃K ,L and rLG(K ,L) = 2EK ,L⌃K ,L. Also, if at some stationary point (K ,L) of G(K ,L) (i.e., where rKG(K ,L) = 0 and rLG(K ,L) = 0), it holds that PK ,L 0 and Rw D>PK ,LD > 0, then (K ,L) is the unique Nash equilibrium.

heading: 3.1 Double-Loop Scheme
text: We introduce a double-loop update scheme. Specifically, we first fix K , and solve for the optimal L, denoted as L(K), whenever exists, by maximizing G(K , ·) over L 2 S(n,m,N ). Then, we update K to minimize G(K ,L(K)) over K 2 S (d,m,N ). For each fixed K , the inner-loop is an indefinite LQR problem where Q K>RuK is not positive semi-definite (p.s.d.). Our goal is to find, via PG methods, the maximizing gain matrix L(K) whenever the objective function G(K , ·) admits a finite upper bound value. We formally state the precise condition for the solution to the inner-loop maximization problem to be well-defined as follows, with its proof being deferred to §B.6.
Lemma 3.3 (Inner-Loop Well-Definedness Condition) For the Riccati equation
PK ,L(K) =Q +K > R u K + (A BK)>ePK ,L(K)(A BK), (3.8)
define the following set of outer-loop gain matrices K:
K := n K 2 S(d,m,N ) | (3.8) admits a solution PK ,L(K) 0, and Rw D>PK ,L(K)D > 0 o . (3.9)
Then, K 2K is sufficient for the inner-loop solution L(K) to be well defined. Also, L(K) is unique, and takes the form of:
L(K) = ( Rw +D>PK ,L(K)D) 1D>PK ,L(K)(A BK). (3.10)
Moreover, K 2K is also almost necessary, in that if K <K, where
K := n K 2 S(d,m,N ) | (3.8) admits a solution PK ,L(K) 0, and Rw D>PK ,L(K)D 0 o , (3.11)
then the solution to the inner loop is not well defined, i.e., the objective G(K , ·) could be driven to arbitrarily large values. Lastly, the solution to (3.8) satisfies PK ,L(K) PK ,L,8L in the p.s.d. sense.
Note that K is nonempty due to Assumption 2.1, but it might be unbounded. Also, every K 2K is equivalent to a control gain matrix that attains a -level of disturbance in the original disturbance attenuation problem (cf. Lemma 2.2). Then, by Lemmas 3.1 and 3.3, the inner-loop maximization problem for a fixed K 2 K is nonconcave in L and always admits a unique maximizing solution. Thus, applying a variant of the Danskin’s theorem [31] yields that maxLG(K ,L) is differentiable with respect to K and rK {maxLG(K ,L)} = rKG(K ,L(K)). The outer loop is then a nonconvex (as we will show in Lemma 3.5) constrained optimization problem in K , expressed as minK2KG(K ,L(K)). Then, the PG of the outer loop is computed as rKG(K ,L(K)) = 2FK ,L(K)⌃K ,L(K). Lastly, we comment on the double-loop scheme we study in Remark A.7.

heading: 3.2 Optimization Landscape
text: For a fixed K , we present the optimization landscape of the inner-loop and defer the proof to §B.7.
Lemma 3.4 (Inner-Loop Landscape) There exists K 2K such that G(K ,L) is nonconcave in L. For a fixed K 2K, G(K ,L) is coercive (i.e., G(K ,L)! 1 as kLkF !1), and the superlevel set
LK (a) := n L 2 S(n,m,N ) | G(K ,L) a o (3.12)
is compact for any a such that LK (a) , ?. Moreover, there exist some lK ,L, K ,L,⇢K ,L > 0 such that G(K ,L) is (lK ,L,⇢K ,L) locally Lipschitz and ( K ,L,⇢K ,L) locally smooth at (K ,L). Further, there exist some lK ,a, K ,a > 0 such that G(K ,L) is lK ,a-globally Lipschitz and K ,a-globally smooth over LK (a). Lastly, G(K ,L) is µK -PL for some µK > 0 which depends only on K and the problem parameters.
The optimization landscape of the inner loop is similar to that of the finite-horizon stochastic LQR [32] (which is an independent work that appears concurrently to our work). However, we allow the state-weighting matrix to be indefinite, while [32] requires Q to be positive-definite. For both our inner-loop problem and the LQR problem in [32], independent process noises (together with the random initial state) with a positive-definite covariance matrix guarantee the non-degeneracy of the state covariance matrix ⌃K ,L at any time, which leads to the stationary point of the inner-loop objective function G(K ,L) also being the unique optimum (cf. Lemma 3.2). Further, the non-degeneracy of ⌃K ,L also ensures that G(K ,L) is PL (cf. Lemma 3.4). These two properties together are essential for establishing the global convergence of PG methods in our nonconvex-nonconcave setting.
Subsequently, we analyze the optimization landscape of the outer loop (proved in §B.8), subject to K defined by (3.9). Note that K is critical, as by Lemma 3.3, it is a sufficient and almost necessary condition to ensure that the solution to the associated inner-loop subproblem is well defined. More importantly, from a robust control perspective, such a set K represents the set of control gains that enjoy a certain level of robustness, which share the same vein as the celebratedH1-norm constraint. Indeed, they both enforce the gain matrix to attenuate a prescribed level of disturbance. This level of robustness also corresponds to the level of risk-sensitivity of the controllers in LEQG problems.
Lemma 3.5 (Outer-Loop Landscape) There exist zero-sum LQ dynamic games such that G(K ,L(K)) is nonconvex and noncoercive on K. Specifically, as K approaches the boundary of K, G(K ,L(K)) does not necessarily approach +1. Moreover, the stationary point of G(K ,L(K)) in K, denoted as (K⇤,L(K⇤)), is unique and constitutes the unique Nash equilibrium of the game.
Lack of the coercivity brings up challenges for convergence analysis, as a decrease in the value of the objective function cannot ensure feasibility of the updated gain matrix, in sharp contrast to the LQR problem [11, 14]. We illustrate the difficult landscape of the outer loop in Figure 1. To address this challenge, we will show next that the natural PG (NPG) and Gauss-Newton (GN) updates, with some stepsize choices, can automatically preserve the feasibility of the iterates on-the-fly, termed the implicit regularization (IR) property.

heading: 3.3 Update Rules and Global Convergence
text: We use l, k 0 to represent the iteration indices of the inner- and outer-loop updates, respectively, and introduce three PG-based update rules as follows:
PG: Ll+1 = Ll + ⌘rLG(Kk ,Ll ), (3.13) NPG: Ll+1 = Ll + ⌘EKk ,Ll , (3.14)
GN: Ll+1 = Ll + ⌘H 1 Kk ,Ll EKk ,Ll , (3.15)
Kk+1 = Kk ↵rKG(Kk ,L(Kk )), (3.16) Kk+1 = Kk ↵FKk ,L(Kk ), (3.17) Kk+1 = Kk ↵G 1Kk ,L(Kk )FKk ,L(Kk ), (3.18)
where ⌘,↵ > 0 are constant stepsizes for the inner loop and the outer loop, respectively. We first present the convergence results for three inner-loop PG updates.
Theorem 3.6 (Inner-Loop Global Convergence) For a fixed K 2K and an arbitrary L0 that induces a finite G(K ,L0), we define a superlevel set LK (a) as in (3.12), where a < G(K ,L0) is arbitrary. Then, iterates Ll of the updates (3.13), (3.14), and (3.15) with stepsizes satisfying PG: ⌘  1/ K ,a, NPG: ⌘  1/(2kHK ,L0k), GN: ⌘  1/2, converge to L(K) with globally linear rates, where K ,a is the smoothness constant of G(K ,L) over LK (a). Moreover, with ⌘ = 1/2, GN (3.15) converges to L(K) with a locally Q-quadratic rate.
In contrast to the standard convergence proof for first-order methods in nonconvex optimization problems where the objective function is PL, the proof of Theorem 3.6 is more involved since we do not have the global smoothness property in our control setting. A careful analysis that addresses this issue has been carried out in §B.9. For the outer loop, we require the iterates of K to stay within K in order for the solution to the associated inner-loop subproblem to be well defined. To meet this requirement, we introduce the IR property for the NPG (3.17) and GN (3.18) updates in Theorem 3.7, with its proof being provided in §B.10.
Theorem 3.7 (IR) Let K0 2K and let the stepsizes satisfy NPG: ↵  1/kGK0,L(K0)k, GN: ↵  1. Then, the iterates Kk 2K for all k 0. In other words, the sequence of solutions to (3.8), {PKk ,L(Kk )}, exists, and for all k 0, PKk ,L(Kk ) always satisfies the conditions in (3.9). Furthermore, the sequence {PKk ,L(Kk )} is monotonically non-increasing and bounded below by PK⇤,L(K⇤), in the p.s.d. sense.
A key step of the proof for Theorem 3.7 is to ensure the existence of a solution to (3.8) along the iterations, by carefully controlling the stepsizes of certain descent directions. We provide an illustration of the proof idea in Figure 2. In particular, the IR property holds for NPG and GN directions because they can ensure matrix-wise decrease of PKk ,L(Kk ), while other descent directions (e.g., vanilla PG) can only decrease G(K ,L(K)), which is a scalar. We highlight the importance of IR in Remark A.8, and establish the convergence result for the outer loop in the following theorem.
Theorem 3.8 (Outer-Loop Global Convergence) Suppose K0 2K and let the stepsizes satisfy NPG: ↵  1/(2kGK0,L(K0)k), GN: ↵  1/2. Then, the sequence of average natural gradient norm squares {k 1 Pk 1 =0 kFK ,L(K)k 2 F }, k 1, converges to 0 with O(1/k) rate. Moreover, this convergence is towards the unique Nash equilibrium. Lastly, the NPG (3.17) and GN (3.18) updates enjoy locally linear and Q-quadratic rates, respectively, around the Nash equilibrium.
The proof of Theorem 3.8 is deferred to §B.11. In the derivative-free setting where PGs are estimated through samples of system trajectories, if we can uniformly control the estimation bias using a fixed number of samples per iterate, then Theorems 3.6 and 3.8 together imply that the global convergence to the Nash equilibrium also holds. We will substantiate this in the next section.

heading: 4 Derivative-Free Policy Gradient Methods
text: We present the sample complexity of our double-loop algorithm, when the exact PG is not accessible, and can only be estimated through samples of system trajectories. In particular, we propose a zeroth-order NPG (ZO-NPG) algorithm with a (zeroth-order) maximization oracle that approximately solves the inner-loop subproblem (cf. Algorithms 1 and 2). In Remark A.9, we comment on how to construct Algorithms 1 and 2 when explicit knowledge on the system parameters is not available.
Algorithm 1 Inner-Loop Zeroth-Order Maximization Oracle 1: Input: gain matrices (K , L0), iteration L, batchsize M1, problem horizon N , distribution D,
smoothing radius r1, dimension d1 =mnN , stepsize ⌘. 2: for l = 0, · · · ,L 1 do 3: for i = 0, · · · ,M1 1 do 4: Sample Lil = Ll + r1U i l , where U i l is uniformly drawn from S(n,m,N ) with kU i l kF = 1. 5: Simulate (K ,Lil ) and (K ,Ll ) for horizon N starting from x i,0 l,0 ,x i,1 l,0 ⇠ D, and collect the
empirical estimates G(K ,Lil ) = PN t=0 c i,0 l,t , ⌃ i K ,Ll = diag h xi,1l,0(x i,1 l,0) >, · · · ,xi,1l,N (x i,1 l,N ) > i , where n ci,0l,t o is the sequence of stage costs following the trajectory generated by (K ,Lil ) and n xi,1l,t o is the sequence of states following the trajectory generated by (K ,Ll ), for t 2 {0, · · · ,N }, under independently sampled noises ⇠ i,0l,t ,⇠ i,1 l,t ⇠D for all t 2 {0, · · · ,N 1}.
6: end for 7: Obtain: rLG(K ,Ll ) = 1M1 PM1 1 i=0 d1 r1 G(K ,Lil )U i l , ⌃K ,Ll = 1 M1 PM1 1 i=0 ⌃ i K ,Ll . 8: Update: PG: Ll+1 = Ll + ⌘rLG(K ,Ll ), NPG: Ll+1 = Ll + ⌘rLG(K ,Ll )⌃ 1 K ,Ll .
9: end for 10: Return LL.

heading: 4.1 Inner-Loop Maximization Oracle
text: Sample complexities of zeroth-order PG algorithms for solving standard infinite-horizon LQR have been investigated in both discrete-time [11, 19, 33] and continuous-time [17] settings. Our innerloop maximization oracle extends the sample complexity result to finite-horizon time-varying LQR with system noises and a possibly indefinite state-weighting matrix. In particular, we show that zeroth-order PG and NPG with a one-point minibatch estimation scheme enjoy eO(✏ 21 ) sample complexities, where ✏1 is the desired accuracy level in terms of inner-loop objective values, i.e., G(K ,L(K)) G(K ,L(K)) ✏1 for the L(K) returned by the algorithm. The two specific zeroth-order PG updates are introduced as follows:
ZO-PG: Ll+1 = Ll + ⌘rLG(K ,Ll ), (4.1) ZO-NPG: Ll+1 = Ll + ⌘rLG(K ,Ll )⌃ 1 K ,Ll , (4.2)
where ⌘ > 0 is the stepsize to be chosen, l 0 is the iteration index, rLG(K ,L) and ⌃K ,L are the noisy estimates of rLG(K ,L) and ⌃K ,L, respectively, obtained through zeroth-order oracles. We establish the sample complexity of Algorithm 1 in the following theorem.
Theorem 4.1 (Inner-Loop Sample Complexity) Let the desired accuracy level be ✏1, 1 2 (0,1), and parameters of the minibatch zeroth-order oracle (cf. Algorithm 1) satisfy
Minibatch Size: M1 ⇠ eO(✏ 21 ), Stepsize: ⌘ ⇠ O(1), Smoothing Radius: r1 ⇠⇥( p ✏1).
Then, with probability at least 1 1 and L ⇠ O(log(✏ 11 )) steps, updates (4.1) and (4.2) output some L(K) := LL satisfying G(K ,L(K)) G(K ,L(K)) ✏1 and kL(K) L(K)kF  q 1min(HK ,L(K)) · ✏1.
Complete versions of Theorem 4.1 for PG and NPG updates (4.1) and (4.2) are given respectively in §B.12 and §B.13, along with their proofs. The total sample complexity of both (4.1) and (4.2) scales as M1 ·L ⇠ eO(✏ 21 · log( 1 1 )), where the logarithmic dependence on ✏1 is suppressed. In contrast to [11], our Algorithm 1 uses an unperturbed pair of gain matrices to generate the state sequence for estimating ⌃K ,L. This modification avoids the estimation bias induced by the perturbations on the gain matrix, while only adding a constant factor of 2 to the total sample complexity.

heading: 4.2 Outer-Loop ZO-NPG
text: With the approximate inner-loop solution L(K) obtained from Algorithm 1, the outer-loop ZO-NPG algorithm approximately solves minK2KG(K ,L(K)), with the following update rule:
ZO-NPG: Kk+1 = Kk ↵rKG(Kk ,L(Kk ))⌃ 1 Kk ,L(Kk ) , (4.3)
Algorithm 2 Outer-Loop ZO-NPG 1: Input: initial gain matrix K0 2 K, number of iterates K , batchsize M2, problem horizon N ,
distribution D, smoothing radius r2, dimension d2 =mdN , stepsize ↵. 2: for k = 0, · · · ,K 1 do 3: Find L(Kk) such that G(Kk ,L(Kk)) G(Kk ,L(Kk)) ✏1. 4: for j = 0, · · · ,M2 1 do 5: Sample K jk = Kk + r2V j k , where V j k is uniformly drawn from S(d,m,N ) with kV j k kF = 1. 6: Find L(K jk) such that G(K j k ,L(K j k)) G(K j k ,L(K j k)) ✏1 using Algorithm 1. 7: Simulate (K jk ,L(K j k)) and (Kk ,L(Kk)) for horizon N starting from x j,0 k,0,x j,1 k,0 ⇠D, and collect
G(K jk ,L(K j k)) = PN t=0 c j,0 k,t , ⌃ j Kk ,L(Kk ) = diag h x j,1 k,0(x j,1 k,0) >, · · · ,xj,1k,N (x j,1 k,N ) > i , where n c j,0 k,t o is the sequence of stage costs following the trajectory generated by (K jk ,L(K j k)) and n x j,1 k,t o is the sequence of states following the trajectory generated by (Kk ,L(Kk)), for t 2 {0, · · · ,N }, under independently sampled noises ⇠ j,0k,t ,⇠ j,1 k,t ⇠D for all t 2 {0, · · · ,N 1}.
8: end for 9: Obtain: rKG(Kk ,L(Kk)) = 1M2 PM2 1 j=0 d2 r2 G(K jk ,L(K j k))V j k , ⌃Kk ,L(Kk ) = 1 M2 PM2 1 j=0 ⌃ j Kk ,L(Kk ) .
10: NPG update: Kk+1 = Kk ↵rKG(Kk ,L(Kk))⌃ 1 Kk ,L(Kk ). 11: end for 12: Return KK .
where ↵ > 0 is the stepsize, k 0 is the iteration index, and rKG(K ,L(K)) and ⌃K ,L(K) are the estimated PG and state correlation matrices, obtained from Algorithm 2. Similar to the modification in §4.1, we estimate the correlation matrix ⌃(K ,L(K)) using the state sequence generated by the unperturbed gain matrices, (K ,L(K)), to avoid the estimation bias induced by the perturbations on the gain matrices. In the following theorem (Theorem 4.2), with its complete version and proof being deferred to §B.14, we have that the IR property in Theorem 3.7 also holds in the derivative-free setting, with high probability. We provide here a sketch of the proof of Theorem 4.2.
Theorem 4.2 (IR: Derivative-Free Setting) For any K0 2K, define the following strict subset of K:
bK := ⇢ K | (3.8) admits a solution PK ,L(K) 0, and PK ,L(K)  PK0,L(K0) + min(HK0,L(K0))
2kDk2 · I .
Let 2 2 (0,1) and parameters of the minibatch zeroth-order algorithm (cf. Algorithm 2) satisfy
Minibatch Size: M2 ⇠ eO(K4), Stepsize: ↵ ⇠ O(1), Smoothing Radius: r2 ⇠ O(K 1),
Inner-Loop Accuracy: ✏1 ⇠ O(K 2), 1 ⇠ O( 2M 12 K 1).
Then, it holds with probability at least 1 2 that Kk 2 bK ⇢K for all k 2 {1, · · · ,K}.
Proof Sketch. Due to lack of coercivity, the objective function of the outer loop cannot act as a barrier function to guarantee that the iterates of PG updates stay in K (cf. Figure 1), and thus new candidates are needed. To this end, we construct two compact sets bK and K0 for a given K0 2K, as shown in blue and red in Figure 3, respectively, where K0 := n K | K 2 K, and PK ,L(K)  PK0,L(K0) o . Clearly, K0 2 @K0 and a sequence of iterates {Kk} that stays in bK or K0 is also uniformly separated from @K (dashed lines in Figure 3). Denote the gain matrix after one step of the exact NPG update (3.17) as eK1. Then, under an appropriate stepsize, Theorem 3.7 demonstrates that PeK1,L(eK1) 0 exists and satisfies PeK1,L(eK1)  PK0,L(K0) almost surely, implying
fK1 2K0 almost surely. In contrast, when the model is not known, one step of the ZO-NPG update (4.3) using estimated gradients sampled through system trajectories could drive the gain matrix outside of K0 (even worse, outside of K) due to the induced statistical errors. Moreover, these errors accumulate over all the iterations, raising significant challenges to find a uniform “margin” that is needed to safely select the parameters of Algorithm 2.
To overcome this challenge, we establish some arguments stronger than that in Theorem 3.7, i.e., Kk stays in bK, for all k, with high probability. We first show that with polynomial samples, the estimated NPG could be accurate enough such that K1, the iterate after applying one step of (4.3), is close to eK1, and thus stays in bK, with high probability. The same arguments could be iteratively applied to all future iterations, because starting from any Kk 2K and choosing an appropriate stepsize, Theorem 3.7 guarantees that the iterates following the exact NPG direction are monotonically moving toward the interior of K. Also, there exist parameters of Algorithm 2 such that the NPG estimates could be arbitrarily close to the exact ones. These two properties together imply that we can control, with high probability, the rate under which the iterates following (4.3) is moving “outward”, i.e. toward @K. Therefore, we manage to demonstrate that even in the worse case, the iterates of the ZO-NPG update will not travel beyond @bK (the blue line), with high probability. Since bK is compact, we can then safely choose the parameters of Algorithm 2 when analyzing the convergence rate of (4.3). ⌅
Theorem 4.2 appears to be the first IR result of PO in robust control in the derivative-free setting, with previous work [16] focusing only on the case with exact PG accesses. With Theorem 4.2 at hand, we now present the sample complexity of ZO-NPG (4.3), deferring its proof to §B.15.
Theorem 4.3 (Outer-Loop Sample Complexity) For any K0 2K, let ✏2  /2, 2,✏1, 1,M2, r2,↵ in Algorithm 2 have the same order as the requirements introduced in Theorem 4.2. Then, it holds with probability at least 1 2 that the sequence {Kk}, k 2 {0, · · · ,K}, converges with O(1/K) rate in the sense that K 1
PK 1 k=0 kFKk ,L(Kk )k 2 F  ✏2 with K = Tr(PK0,L(K0) PK⇤,L(K⇤))/[↵ ✏2].
Hence, ZO-NPG converges to the ✏2-neighborhood of the Nash equilibrium with probability at least 1 2, after using M2 ·K ⇠ eO(✏ 52 · log( 1 2 )) samples. Moreover, the convergent gain matrix KK also solves the LEQG and the LQ disturbance attenuation problems (cf. Lemma 2.2).
Compared with the eO(✏ 2) rate of PG methods for solving LQR [19] and our inner-loop (cf. Theorem 4.1), the eO(✏ 5) rate of ZO-NPG for solving our outer-loop is less efficient, due to the much richer landscape presented in Lemma 3.5. In particular, the objective function of LQR is coercive (leading to the “compactness” of sub-level sets and the “smoothness” over the sub-level sets, and enabling the use of “any” descent direction of the objective to ensure feasibility) and PL. In contrast, none of these properties hold true for the objective function of our outer loop, and a descent direction of the objective value may still drive the iterates out of K, which will lead to unbounded/undefined value. To guarantee that the ZO-NPG iterates will stay within K (which is necessary for the iterates to be well-defined), we need to use large number of samples (eO(✏ 5) in ✏ and polynomial in other parameters) to obtain a very accurate approximation of the exact NPG update (3.17), similar to what has been done in [11], to ensure that PK ,L(K) is monotonically non-increasing in the p.s.d. sense with a high probability along iterations. For LQR, any descent direction of the objective value, which is a scalar, suffices to guarantee that the PG iterates will stay in the feasible set. Therefore, for LQR, the eO(✏ 2) rate is expected for the smooth (since the iterates will not leave the feasible set, which is compact) and PL objective functions; while for our robust control setting, due to the more stringent requirements on the estimation accuracy and the non-PL objective function, the eO(✏ 5) rate is reasonable. In fact, to our knowledge, there is no sample complexity lower-bound applicable to our outer loop (stochastic nonconvex optimization with no global smoothness nor coercivity nor PL condition, with an inner-loop oracle).

heading: Acknowledgments
text: K. Zhang, X. Zhang, and T. Başar were supported in part by the US Army Research Laboratory (ARL) Cooperative Agreement W911NF-17-2-0196, and in part by the Office of Naval Research (ONR) MURI Grant N00014-16-1-2710. B. Hu was supported by the National Science Foundation (NSF) award CAREER-2048168. The authors would like to thank Dhruv Malik and Na Li for helpful discussions and feedback. The authors would also like to thank the anonymous reviewers of NeurIPS for valuable comments and suggestions.

Review summaries:
While the machine learning community has given much attention to the LQR problem, much less attention has been given to more sophisticated control problems. This work takes a step in this direction by studying the sample complexity of derivative-free methods applied to the Linear Exponential Quadratic Gaussian (LEQG) and LQ Disturbance Attenuation problems. To solve these problems, they show a reduction of each to the LQ game setting, then propose and analyze the convergence rates and sample complexity of a derivative-free optimization (DFO) algorithm.

This article studies the convergence of double-loop policy gradient methods for finite-horizon two-layer zero-sum LQ game arising from the risk-sensitive control problems. It shows that, for suitable choices of the initial guess of the outer iteration, both the natural gradient method and the Gauss-Newton method converge to the unique Nash equilibrium. The authors then extend the algorithm to derivative-free methods based on observed state trajectories. To the best of my knowledge, this is the first theoretical result on convergence of gradient-based methods for competitive multi-agent RL problems.