Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
Authors: Kaiqing Zhang
Xiangyuan Zhang
Bin Hu
Tamer Basar
Venue: NeurIPS 2021 Poster (2021)
Keywords: Robust Control
Policy Gradient
Reinforcement Learning
Nonconvex-Nonconcave Optimization

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. 

Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
Kaiqing Zhang?
Xiangyuan Zhang
Bin Hu
Tamer Başar
Abstract
Direct policy search serves as one of the workhorses in modern reinforcement learning (RL), and its applications in continuous control tasks have recently at- tracted 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 two fundamental settings in risk-sensitive and robust control: the inite-horizon linear exponential quadratic Gaussian, and the shite-horizon linear- quadratu disturbance attenuation problems. As by yy-product, results also provide the first sample complexity for the global convergence of PG methods on solving zero-sum linear-quadratic minimax optimization problem that serves as a baseline setting in multi-agent reinforcement learning (MARL) with continuous spaces. One feature of our algorithms that during the learning phase, a certain level of robustness/risk-eee sensitvivy of the controller is preserved, which we termed the implicit regularization property, and is an essential requirement in safety-critical control systems.
dynamic games,
Introduction
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 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 risk-sennittive/robust control remains underdeveloped in the literature. Since tisk-sensitivity and robustness are important issues for designing safety-critical systems, it is natural 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 concem, and studies the sample complexity of model-free PG methods on two important baseline problems riskesensitiverrobuut 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 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
Equua contribution. K. Zhang is with the LIDS the CSAIL at Massachusetts Institute of Technology. Email: kaiqing@ edu. X. Zhang, B. Hu, and T. Başar are with the Department of ECE and the CSL at the University of Illinois Urbana-Chann Shhana-Champaign. Emails: (xz7, binhu7, basarl ) @illinois.edu.
35th Conference on Neural Information Processing Systems (NcurIPS 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 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
conditions have reshaped the feasible set in 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 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, the iterates' feasibility here is equivalent to bonk-eeniiiiiityrbbssness 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 mixed 2z/Hoo 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 caausttess-relatte feasible set. In [16], it is emphasized that IR is feature of both the problem and the algorithm, contrasting to that the
nature of PG methods for LQR problems is based on the barrier function property of the objective and hence is algoritlmm-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 S..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 follows.
Contributions. We provide the first sample complexity results for model-free PG methods for solving linear control problems with iisk-seesiiiiity/robusnee bance attenuation problems), which were viewed as important open problems in the seminal work [1]]. From the robust control perspective, one feature of our algorithms is that, during the learning process, a certain level of abbustnnss/riss--ssniiiii has generalized the results in [16] with known model, and has thus enabled the sample convergence guarantees of PG methods for risk senssitiiive//oo 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 volicy-based methods for competitive multi-agent RL. Second, in the context of minimax opti- mization, our results address a class of 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 possibly indefinite seigh-weightin matrix.
concerns (the LEQG and LQ distur-
of the controller is proved to be preserved. This
minimax constrained optimization
2 Background
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.
2.1 Linear Exponential Quadratic Gaussian
Consider the finite-horizon LEQG problem [22, 27, 28], with time-varying systems dynamics de- scribed by X = A₂x, + B,u, + w,, f E [0, .......N 11), where x, E IR" represents the system state: u E Id is the control input; w, E RM is an independent (across time) Gaussian random noise with wi- (0, W) for some W > 0; the initial state xg (0, for some X, 0, which is

---

independent of (w 1: and A, B, are time-varying system matrices. The objective function is given by ((u,)) := / l (exeee/(xxxXeeeeee ( (x/ Qix; + u, R + x QN xNxx]] where Qi, QN and R are symmetric weighting matrices; and f >>0 0 is a parameter capturing the degree of sisk-sensitivity, which is upper- upper-bounded by some &" 0 [23, 28, 29].
The goal in the LEQG problem is to find the J -minimizing optimal control policy 14: (R" x ) x R - Ra that maps, at time t. the history of state-control pairs up to time and the current state X to the control u, It has been shown in [22] that μi has a linear state-feedback form μī(x,) = - X++, where K; E IRáxm,, for all t. Therefore, it suffices to search Kł in the matrix space R for all t E [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.
2.2 LQ Disturbance Attenuation
Second, consider the LQ disturbance attenuation problem, with time-varying dynamical systems described by Xt+1 = A₁x; + B + D and 2, = Cjx; + E,u,, where X E R" is the system state; u, E IR the control input; w, E R" is the (unknown) disturbance input; 2, E IR' is the controlled output; A, B,, C, E, are system matrices with appropriate dimensions; and Xo R" is unknown. In addition, we assume that E, [C, E, = [0 R. for some R, > 0 for normalization, with no loss of generality (see $ of [25] for simple procedure that can transform the general problem into a form that satisfies this "normalization" assumption). Subsequently, we denote the e² -o-mss of the vectors
@ = xx C wT..... W and z : - - x QN!" as ||ي||| and ||||| = [c((u,),, (w;)), (w;))) where QN 2 O. Then, the robustness of a designed controller can be guaranteed by a constraint on the ratio between ||ر|| and ||a|]| Specifically, the goal of disturbance attenuation is the following: Given a y y'" where y = ((B')- > is the optimal (minimaxx level of disturbance attenuation at the output and recall that 8" is the upper bound for the risk-sensitivity parameter in LEQG [23, 25], find a control policy pe: -,,,,, f E (0,... ,N 1}. that solves min(H.) J (x,)(x,))) subject
1/2 to suPx (x(( [ww,)))))) /|wll y, where [(p, (x,))) is an upper bound of the LQG cost [30]. We defer the precise formulations of the LQ disturbance attenuation problem to S..2.2 Also, see Remark A.3 for the challenges when addressing LEQG and LQ disturbance attenuation directly using derivative-free PG methods.
2.3 An Equivalent Dynamic Game Formulation
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 sensiivve control problems. We aim to address these three classes of problems in a unified fashion.
Now, consider two-player zero-sum LQ stochastic dynamic game (henceforth, game) with closed- loop perfect-state information pattern, characterized by X A,x; B,u, + D,W; & where X; E RR" is the system state, and i, K,,x, Rd (resp., W. := -L,x, E R") is the linear state- feedback controller of the minimizing (resp., maximizing) player', which suffices to attain the saddle point whenever exists [26]. The initial state Xg and the additive process noises & drawn independently from a distribution D and A,, B,, D, are system matrices. Further, we assume that D is zero-mean, has a positive-definit covariance, and satisfies almost surely that ||xo|]. S 8, for all t E (O...., ,N - 1) and some constant 9. The goal of the minimizing (resp. maximizing) player is to minimize (resp. maximize) a quadratic objective function, namely to solve the game
inf sup F Exo EX-1 (K,) (L,)
Σ xTTIQ K. R.
I,
R L.)++
UN
(2.1)
1 Hereafter we will use player and agent interchangeably. Also, restrictions to instantancous linear state- feedback policies do not lead any loss of generality, as the results of $2.3 hold for general square interriiteee policies, allowed to use the entire state history.
3

---

where O2 ON 2 O, R > O are symmetric weighting matrices. Whenever the solution to (2.1) exists such that the inf and sup be interchanged, the value (2.1) is the value of the game, and the corresponding policies are the suddle-point/NNe (2.1), we first introduce the following vinyingrying Riccati difference equation (RDE):
equilibrium policies. To characterize the solution to
P Q + A, AT A,, EE (O,...,NN1
(2.2)
where A, := I+ (B, (R Pr,,, and PN QN. From [26], whenever sad- dle point exists, the saddle-point control policies are linear state-feedback (i.e., Pu, (hu,z)
-K₃ and (hw)()) = -L,x),, and the gain matrices K; = (R₂) B, A7 Ar and L; -(R P. A, A, are unique, where Pi+ 0 is generated by (2.2). Then, we introduce standard assumption that ensures the existence of the value of the game [25].
Assumption 2.1 R P., 0, for all e (0,..., where P 2 2 is generated by (2.2).
Under Assumption 2.1, the value in (2.1) is attained by the sequence (I:)), where K; E R and L; E RR"* are gain matrices at the paddle-point/NN equilibrium. Thus, we can replace the inf and sup in (2.1) with min and max, respectively. Some further notes on Assumption 2. are provided in Remark A.5, showing that it 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.
> Y" in the LQ disturbance attenuation problem, we can introduce an equivalent LEQG problem and equivalent zero-sum LQ dynamic game. Specifically, if we set II R2, C.T C2 W in LEQG, I'I, C, D,D.D. in the LQ disturbance attenuation I,
Lemma 2.2 (Connections) For any fixed y>
problem, and Ry, R4 Qr, D,D. in the game to be the same, for all NN NN11, 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 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.
3 Policy Gradient Methods
For ease of analysis, we define
W WN I. &
[x] 50 .... N. I. Q diag(Qo-N).
MmmM
O mxx
0 OmxdN
OwxnN
A
B
R" diag(RR((NN1))
(oag(AA-(N-I)
Nm
diag (ong(Bo-NN-1)) diag(Do-(N-1))
RM (rig((R((N-1))
(diag(Ko-(N-i)
0aNxm
(oag(Lo-(N-I)) OnN
(3.1)
where d'aggXXoN denotes the block-diagonal matrix with Xo. .N on the diagonal block entries. Some other notations introduced in $A.2. Now, using the compact notations, we develop PG methods with exact PG accesses that provably converge the Nash equilibrium of the game, (K*,L') S(d, m, N) x S ((n, m, N), where S(d, M) and S(n, m, N) are the subspaces that we confine our searches of K and to, respectively. In particular, we only search over E dáx(N +1mm +1mm and L E N +1mm and K, L satisfy the sparsity patterns in (3.1), without losing any optimality. Then, for any (K, L), the objective function Ç(K, L) is given by
Tr(P,, = G(K,L) FE &
Tr((Q + RT K L)
(3.2)
where IK diag( PK ko.lor" ... ,PK and Pk.,,, E (0..... N 1), solves the Lyapunov equation
Pk,,1, = (A, B.K, D,L,) Pk (A, B,KG D.L.) Q: K, R L, R
(3.3)
with PKN.LN := QN Moreover, L Σx,L are the solutions to the Lyapunov equations
P (A BK T LA BK -D) Q
(3.4)
Σx,1 - (A BK DL)E (A- BK - DL) +Lo, Σo = E ddag(xxxx -. EN-16&-11>>0,
(3.5)

---

where Σg > O is full-rank because xp, -.. are drawn independently from D which has definie 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 ||xa|||||e||| s 9 almost surely, for all t, | $000 EN-16N-1lle (N + 11822lmost surely. Next, define the following notations:
co: (N+ 1)82, Ek,L == (-R" D BRI.DDL-D PK.I(A (A- BK), FK.I == (R" +B PR. B PK - DL), (3.6) GK.L(K)= := R" + +B RK,LK) PK,14K]= == PK.1K)++++ DK, - -D D( DJ PK,KK) (3.7)
:=: 1),
& = Amin (Eo) > O,
HK == R DTRK,LD.
Our goal is solve the minimax optimization problem mink max,, G(K, L) such that G(K', s G(""L"") S 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-Noncee -Nonconcavity) There exist zero-sum LQ dynamic games such that the objective function G(K, L) is nonconcave in L for fixed K, and nonconvex in K for fixed L.
Lemma 3.2 (PG & No Spurious Local Minimum) The PGs of G(K,L) can be computed as () 2F,,1EK. and V VIG,,L 2,,,I Also, if at some stationary point (K, of (),, (i.e. where V LK)(K,L)= = and V L(K, 0), it holds that Pk,L 2 0 and -T T'Px 0. then (K is the unique Nash equilibrium.
3.1 Double-Loop Scheme
We introduce double-loop update scheme. Specifically, first fix K. and solve for the optimal L, denoted as LK)), whenever exists, by maximizing 9(K,-) over L E E m, N). Then, we update K to minimize G(K, L(K)) over K E S(d, m, For each fixed K, the inner-loop is indefinite LQR problem where QQ QQ-KKT KT R"K 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 finite upper bound value. We formally state the precise condition for the solution to the inner-loop maximization problem to be well-defined follows, with its proof being deferred to $B.6.
Lemma 3.3 (Inner-Loop Well-Definenness Condition) For the Riccati equation
PK,K(K) K R"K (A- BK) (k,14k)(--KK,
(3.8)
define the following set of outer-loop gain matrices K:
k:= {K S(d, (3) admits a solution PK,LIK) 0, and R -D -DT-DPPK.IKE DK,,LKKDD>> 0).
(3.9)
Then, Ke
E K. is sufficient for the inner-loop solution L(K) to be well defined. Also, L(K) is unique, and takes the form of:
+ (-R" D DK.LLKKKDD' D PK.LKK -KK).
(3.10)
Moreover, K E K. is also almost necessary, in that if @ K, where
T (==(KESld,,,,) (3.8) admits solution PK O, and R -D -D PK 0).
(3.11)
then the solution to the inner loop is not well defined, i.e., the objective ((K,,) could be driven to arbitrarily large values. Lastly, the solution to (3.8) satisfies PK.LIK) P VL in the p.s.d. sense.
Note that IC is nonempty due to Assumption 1. but it might be unbounded. Also, every K E KC is equivalent to a control gain matrix that attains yeleel 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 Thus, applying a variant of the Danskin's 's theorem [31] yields that max, G(K, L) is differentiable with respect to and Vx (max G(K, L)] = (K L(K).. The outer loop then a nonconvex (as we will show in Lemma 3.5) constrained optimization problem in K, expressed as minker G(K,L(()) L(K)). Then, the PG of the outer loop computed as VKG(K, L(K)) = 2FK,L(K) F K,L(K)- Lastly, we comment on the double-loop scheme we study in Remark A.7.
IC is nonconcave in L and always admits unique maximizing solution.
5

---

N-3
N-2
N-1
Ry Dā- 9x
R. Dj P
A Paiaray 2 0 exlats & P PRiarry S. PRANAK
Figure I: Left: Optimization landscape of LQR, where the dashed line represents the boundary of the stabilizing controller set. Right: Optimiza- tion landscape of the outer loop, with the dashed line representing the boundary of K. The solid lines represent the contour lines of the objective function, K denotes the control gain of one iter- ate, and * is the global minimizer.
Figure 2: Proof idea for Theorem 3.7: For any E EKK, denote the gain matrix after one-step PG update as K'. We construct an iterative argument find a constant stepsize such that (x,,IK.) 2 exists and satisfies Pk,,KK)) S Pk,,4K.) for all f.
Specifically, any K; satisfying also satisfies Moreover, is enforced by Assumption 2. Combined, K' E is ensured.
3.2 Optimization Landscape
For fixed K, we present the optimization landscape of the inner-loop and defer the proof to $B.7.
Lemma 3.4 (Inner-oopp Landscape) There exists K E K. such that Ç(K, L) is nonconcave in L. For a afixeed K E K, L) is coercive (i.e., G(K, -00 as || - oo), and the superlevel set
Cx(a) : S(n, | L)
(3.12)
compact for any a such that (x(a) # Ø. Moreover, there exist some IK. L, LKK,L. IK.IIKKKKL O such that G(K, L) is (K,,I, locally Lipschitz and (fK,,IPK.I) locally smooth at L). Further, there exist some Ka KK,a 0 such that G(K, L) K. -lobbally Lipschitz and Ka globball smooth over Lx (a). Lastly, G(K, L) is 4k-PPlfor some Hk O 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 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 positive-definite covariance matrix guarantee the non-degeneracy of the state covariance matrix Σ k. at any time, which leads to the stationary point of the inner-loop objective function Ç(K,L, L) also being the unique optimum (ef. Lemma 3.2). Further, the degennery of X 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
nonconvex-nonconeee 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 sufficient and almost necessary condition to ensure that the solution to the associated inner-loop subproblem well defined. More importantly, from a robust control perspective, such set K. represents the set of control gains that enjoy a certain level of robustness, which share the same vein as the celebrated 2o constraint. Indeed, they both enforee the gain matrix to attenuate prescribed level of disturbance. This level of robustness also corresponds to the level risk- sensitivity 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 necessarily approach 400. Moreover, the stationary point 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 To address this challenge, we will show next that the natural PG (NPG) and Gauss-Newtee (GN) updates, with some stepsize choices, can automatically preserve the feasibility of the iterates on-the-fly, termed the implicit regularization (IR) property.

---

3.3 Update Rules and Global Convergence
We use 1,k 2 0 to represent the iteration indices of the inner- and outer-loop updates, respectively. and introduce three PG-based update rules as follows:
PG: L411 = LV Li),
(3.13)
k++ = K2 -x--aVa x
(3.16)
NPG: 4 + E
(3.14)
K = KR LIKE)
(3.17)
GN: 1 + L, Ek
(3.15)
Kx+1 = KR - KG.KKKKKKKKKK LK,g) L(Ke))
(3.18)
where a 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 e and an arbitrary Lg that induces finite G(K, Lo), we define a superievel set Lx (a) as in (3.12), where < G(K, Lo) is arbitrary. Then, iterates L of the updates (3.13), (3.14), and (3.15) with stepsizes satisfying
PG: yj 1/1K,ar NPG: 1j 1/(2|
GN: 1/2..
converge to L(K) with globally linear rates, where KKK, the smoothness constant of G(K, L) over L (a). Moreover, with = 1/2, GN (3.15) converges to L(() 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 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 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 Ko E IC and let the stepsizes satisfy
GN: a S L. NPG: S 1/I|GK,,L(K,,)ll
Then, the iterates K2 E KC for all k 220 0. In other words, the sequence of solutions to (3.8), (PK,,LIK,).. exists, and for all k 2 0, Pky,L always satisfies the conditions in (3.9). Furthermore, the sequence (KK), is monotonically non-increasing and bounded below by Pkt,,1K.), in the p.s.a. sense.
A key step of the proof for Theorem 3.7 is to ensure the existence of 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 Pk.,,(Kg)- while other descent directions (e-g., vanilla PG) can only decrease G(K, L(K)), which is 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 Ky E K. and let the stepsizes satisfy NPG: a S III
GN: a S 1/2.
Then, the sequence of average natural gradient norm squares (k-1 "k-bbb=bll [IKK,, (.l k 1, con- verges to 0 with ((1kk) rute. Moreover, this convergence is towards the unique Nash equilibrium. Lastly, the NPG (3.17) and GN (3.18) updates enjoy locally linear and Q Q-quadratic rates, respectively, around the Nash equilibrium.
The proof of Theorem 3.8 is deferred $B.11. 11. In the derivative-free setting where PGs are estimated through samples of system trajectories, if we can uniformly control the estimation bias using 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.
Derivative-Free Policy Gradient Methods
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 (zeroth-order) maxinization oracle that approximately solves the inner-loop subproblem (cf. Algorithms 1 and 2). In Remark A.9, we comment on how to construct Algorithms and 2 when explicit knowledge the system parameters is not available.
7

---

Algorithm Inner-Loop Zeroth-Order Maximization Oracle
1: Input: gain matrices (K, Lg), iteration L, batchsize M, problem horizon N, distribution D, smoothing radius r, dimension d, mmn, stepsize 17-
2: for / 0,. ,- do
3: for 0, 0,... MM 111-16 do
4: Sample 1 Li + ri U. where Uf is uniformly drawn from S(n, m, with ||U]
5: Simulate (K.L)) and L,) for horizon N starting from ..00 4.1
$1,0=110 D, and collect the empirical estimates ((K, Li= 1.0 I12 Ex,,, = diag %1,0 (1,,0 (T ,,,,,, ( where
(4.r] is the sequence of stage costs following the trajectory generated by (K, Lj) and (x1,) the sequence of states following the trajectory generated by (,, for f (0, .N),
$1,1 under independently sampled noises E zhd1 ~ D for all E (O,...,NNE 1J.
6: end for
M1-1 E'K,,, 7: Obtain: ( = -. - LOKKLJU ΣK,L, = Mi L.1
8: Update: PG: L++1= = L (IVI,KLL NPG: L + VL
9: end for
10: Return L1-
4.1 Inner-Loop Maximization Oracle
Sample complexities of zeroth-order PG algorithms for solving standard infinite- LQR have been investigated both discrete-ting secreet-timme/te [11, 19, 33] and continuous-timg [17] settings. Our inner- loop 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 one-point minibatch estimation scheme enjoy Ö(e7?) sample complexities, where 6₁ is the desired accuracy level in terms of inner-loop objective values, i.e., 2 G(K, ((K)) - ej for the I(K) returned by the algorithm. The two specific zeroth-order PG updates are introduced as follows:
ZO-PG: L
= L1 V,KK,
(4.1)
ZO-NPG: Li+1 =1 VV.KKKKLLL)Ek (4.2)
where 11 > the stepsize to be chosen, I 0 is the iteration index, (z9(K,L) and Σx.1 are the noisy estimates of V,9(K,L) and Σk,I. respectively, obtained through zeroth-order oracles. We establish the sample complexity of Algorithm in the following theorem.
Theorem 4.1 (Inner-Loop Sample Complexity) Let the desired accuracy level be c1, E (0, 1), and parameters of the minibatch zeroth-order oracle (cf. Algorithm 1) satisfy
Minibatch Size: M1 -Ole,2), Stepsize: 11 O(1), Smoothing Radius: O(vE1).
Then, with probability at least - ò1 and L ((og((T)) steps, updates (4.1) and (4.2) output some
I(K) := Lg satisfying G(K, T((K) L(K) and (|)(K|))(K]])]) (((((KK-((KKI)))) I(KK]lF A (HK,LIK)) 61
Complete versions of Theorem 4. 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 M1 I.~ 0 1og(57')) )), where the logarithmic dependence E is suppressed. In contrast to [11], our Algorithm uses an unperturbed pair of gain matrices to generate the state sequence for estimating Σ This modification avoids the estimation bias induced by the perturbations the gain matrix, while only adding constant factor of 2 to the total sample complexity.
4.2
Outer-Loop ZO-NPG
With the approximate inner-loop solution L(K) obtained from Algorithm 1, the outer-loop ZO-NPG algorithm approximately solves minkex: G(K, I(K)), with the following update rule:
ZO-NPG: Kk+1 = a IKK K.
(4.3)

---

Algorithm 2 Loter-Loop ZO-NPG
1: Input: initial gain matrix Kg E K. number of iterates K, batchsize M2, problem horizon N, distribution D. smoothing radius 72. dimension d2 = mdN, stepsize a.
2: for k = 0,...,K K -
do
3: Find [(Kk)) such that G(K [(K{)) 2 ((,,, -1
4: for j= 0.... .M, do
5: Sample K K 12 VV where v is uniformly drawn from Sdd, m, N) with II 1.
6: Find [(K{) such that G(K L(K))) 2 9Kk L(K))) - using Algorithm 1.
7: Simulate (K{ [(K:)) and (K [(K))) for horizon N starting from 2,,0 *,0 ~ D. and collect En Cg," Σ k.,KIK)) = diag w (x
1.1
R,N (x where {<x:] is
j.1 1.1
the sequence of stage costs following the trajectory generated by (K. [(K:)) and (x
the sequence of states following the trajectory generated by (K,, ((Kk)) for (0,.... .N). D for all E (0..... ,N,,,N111 1).
under independently sampled noises e/.0 ci.l
Sk,t" Skt
8: end for
9: Obtain: V मेद م TK LK EK. = the - M2-1 E
I(K.))
10: NPG update: KR+1 = - LIK K..(()))
11: end for
Return Kg.
where a is the stepsize, 2 is the iteration index, and VxG(K, and ΣK.IIK) are the estimated PG and state correlation matrices, obtained from Algorithm 2. Similar to the modification in 1,.1, we estimate the correlation matrix L(K,L(K) using the state sequence generated by the unperturbed gain matrices, (K, I(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- Setting) For any Ko E K., define the following strict subset of K.:
:= K (3.8) admits a solution PK.LIK) 2 O, and PK.LIK) S PK.,LIK) + Amin Mmin(HK,,,i (H,,,, -1)
2||D1|
Let 62 E (0,1) and parameters of the minibatch zeroth-order algorithm (cf. Algorithm 2) satisfy
Minihatch Size: M2 ~ O(K"), Stepsize:
a ~ O1)(), Smoothing Radius: r2 OO(I--)
Inner-Loop Accuracy: E1 ~ 2),
81 0100662,
Then, it holds with probability at least d
d2 that K₁ E C for all k (K)..,
Proof Sketch. Due to lack of coercivity, the objective function of the outer loop cannot act as barrier function to guarantee that the iterates of PG updates stay in K. (cf. Figure 1), and thus new candidates needed. To this end, construct compact sets K. and KC for given Kg K,, shown in blue and red in Figure 3, respectively, where K, = K K e K,, and Pk,M(K)= S Pk.,,4KK))) Clearly,
Ko E aKo and a sequence of iterates [Kg] that stays in Æ or ACo is also uniformly separated from ai (dashed lines in Figure 3). Denote the gain matrix after one step of the exact NPG update 17. as K, Then, under an appropriate stepsize, Theorem 3.7 demonstrates that ,,I 2 0 exists and
satisfies II, I Lk,)))K)) almost surely, implying K₁ E Ko almost surely. In contrast, when the model is not known, one step the ZO-NPG update (4.3) using estimated gradients sampled through system trajectories could drive the gain matrix outside of Ko (even worse, outside of K.) due to the induced statistical errors. Moreover, these errors accumulate over the iterations, raising significant challenges to find uniform "margin" that is needed to safcly select the parameters of Algorithm 2.

---

Figure 3: Illustrating the proof idea for The- orem 4.2. For any Kg E K., we construct two compact sets K and Ko shown in blue and red, respectively, that are independent of the con- tour lines of the objective function. Our analy- sis proves that the iterates following (4.3) stay within K with high probability, thus uniformly separated from aK. with high probability.
OK
ak
kee
Ko * K
To overcome this challenge, we establish some arguments stronger than that in Theorem 3.7, i.e., K stays in K, for all k, with high probability. We first show that with polynomial samples, the estimated NPG could be accurate enough such that K,, the iterate after applying one step of (4.3), is close to
K1 and thus stays in K, with high probability. The same arguments could be iteratively applied to all future iterations, because starting from any K; E KC 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 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 aiC. Therefore, we manage to demonstrate that even in the worse case, the iterates of the 70-NPG update
will not travel beyond ak (the blue line), with high probability. Since K 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 serivaaivee-ree 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 15.
Theorem 4.3 (Outer-Loop Sample Complexity) For any Ko E K., let e2 S 1/2, 1,,,,,,,,,22 in Algorithm have the same order as the requirements introduced in Theorem 4.2. Then, holds with probability at least 1 1- Ö2 that the sequence (Kg). k E (0, K), converges with O(1/K) rate in e2 with K (Tr(Px,,(K,)) P
the sense that K Σ k [|FK,,LIK))ll
Hence, ZO-NPG converges to the E ncighbooooo of the Nash equilibrium with probability at least 1 52, after using M2 K O(e log(ō,') -log_, )) samples. Moreover, the convergent gain matrix Kg also solves the LEQG and the LQ disturbance attenuation problems (cf. Lemma 2.2).
Compared with the Ō rate of PG methods for solving LQR [19] and our inner-loop (cf. Theorem 4.1). the 5(E-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 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 PI.. 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 (Ö(e-5) in and polynomial in other parameters) to obtain a very accurate approximation of the exact NPG update (3), similar to what has been done in [11], to ensure that P 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 scalar, suffices to guarantee that the PG iterates will stay in the feasible set. Therefore, for
LQR, the Ō 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 (5 rate reasonable. In fact, our knowledge, there no sample complexity lower-bound applicable to our outer loop (stochastic nonconvex optimization with no global smoothness nor coercivity nor PL condition, with an lnner-loop oracle).
10

---

Acknowledgments
K. Zhang, X. Zhang, and T. Baş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 19M0014-16-1-2111 (NSF) award CAREER-2048160 168. 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 NeurlPS for valuable comments and suggestions.
Hu was supported by the National Science Foundation
References
[1] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint arXivv1506.024385 2015.
[2] Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: 1ww...5099999771 2015.
[3] Benjamin Recht. A tour of reinforcement learning: The view from continuous control. Anmual Review of Control, Robotics, and Autonomous Systems, 2:253-279, 2019.
[4] Richard S Sutton, David A McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, pages 1057-1063, 2000.
[5] Sham M Kakade. A natural policy gradient. In Advances in Neural Information Processing Systems, pages 1531-1538, 2002.
[6] Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Başar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 2020.
[7] Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems, pages 1008-1014, 2000.
[8] Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor-critic algorithms. Automatica, (5(11):2471-243) 2009.
[9] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 170..06777.0647 2017.
[10] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pages 1897, 2015.
[11] Maryam Fazel, Rong Ge, Sham M Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. International Conference on Machine Learning, pages 1467-1476, 2018.
[12] Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. In Advances in Neural Information Processing Systems, pages 8353 8365, 2019.
[13] Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods the linear quadratic regulator: An asymptotic viewpoint. In Conference on Learning Theory, pages 3036-3083, 2019.
[14] Jingjing Bu, Afshin Mesbahi. Maryam Fazel, and Mchran Mesbahi. LQR through the lens of first order methods: Discrete-time case. arXiv preprint /00700/9070002..1 2019.
[15] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar: Policy optimization provably converges to Nash equilibria zero-sum linear quadratic games. In Advances Neural Information Processing Systems, pages 1 11602-11614, 2019.

---

[16] Kaiqing Zhang. Bin Hu, and Tamer Başar. Policy optimization for 722 linear control with Hos robustness guarantee: Implicit regularization and global convergence. arXiv preprint arXiv: WiXiv:9900009900 2019.
[17] Hesameddin Mohammadi, Armin Zare, Mahdi Soltanolkotabi, and Mihailo R Jovanović. Conver- gence and sample complexity of gradient methods for the model-free free linear quadratic regulator problem. arXiv preprint 19Iiv:192..111
2019.
[18] Luca Furieri, Yang Zheng, and Maryam Kamgarpour, Learning the globally optimal distributed LQ regulator. In Learning for Dynamics and Control, pages 287-297, 2020.
[19] Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter L Bartlett, and Martin J Wainwright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. Journal of Machine Learning Research, 21(21):1-51, 2020.
[20] Paulo Jansch-Porto, Bin Hu, and Geir Dullerud. Convergence guarantees of policy optimization methods for Markovian jump linear systems. In American Control Conference, pages 2882- 2887, 2020.
[21] llyas Fatkhullin and Boris Polyak. Optimizing static linear feedback: Gradient method. arXiv preprint trXiv:2004.098755 2020.
[22] David Jacobson. Optimal stochastic linear systems with exponential performance criteria and their relation to deterministic differential games. IEEE Transactions on Automatic Control, 18(2):124-131, 1973.
[23] Keith Glover and John C Doyle. State-space formulae for all stabilizing controllers that satisfy an How -norm -nom bound and relations to risk sensitivity. Systems & Control Letters, 11(3):177-77.. 1988.
[24] Tamer Başar. A dynamic games approach to controller design: Disturbance rejection in discrete- time. IEEE Transactions Automatic Control, 36(8):936-99)) 1991.
[25] Tamer Başar and Pierre Bernhard. I-IIffinity Optimal Control and Related Minimax Design Problems: A Dynamic Game Approach. Springer Science & Business Media, 2008.
[26] Tamer Başar and Geert Jan Olsder. Dynamic Noncooperative Game Theory. SIAM, 1998.
[27] Peter Whittle. Risk-sensitive linear/quadratic/ganssin control. Advances in Applied Probability, pages 764-777, 1981.
[28] Peter Whittle. Risk-Sensitive Optimal Control, volume 2. Wiley, 1990.
[29] Haruki Nishimura, Negar Mehr, Adrien Gaidon, and Mac Schwager. RAT ILQR: A risk auto- tuning controller to optimally account for stochastic model mismatch. IEEE Robotics and Automation Letters, 6(2):763-770, 2021.
[30] Denis Mustafa and Dennis S Bernstein. LQG cost bounds in discrete-time Hz/Hoo control. Transactions of the Institute of Measurement and Control, 13(5):269-21) 1991.
[31] Pierre Bernhard and Alain Rapaport. On a theorem of Danskin with an application to theorem of Von Neumann-Sinn Sion. Nonlinear Analysis: Theory, Methods & Applications, (468):1163-111 1995.
[32] Ben M Hambly, Renyuan Xu, and Huining Yang. Policy gradient methods for the noisy linear quadratic regulator over a finite horizon. arXiv preprint arXiv:2011. 10300, 2020.
[33] Hesameddin Mohammadi, Mahdi Soltanolkotabi, and Mihailo R Jovanovié. On the linear convergence of random search for discrete-time LQR. IEEE Control Systems Letters, 5(3)9989- 994, 2020.
[34] George Zames. Feedback and optimal sensitivity: Model reference transformations, multi- plicative seminorms, and approximate inverses. IEEE Transactions on Automatic Control, 26(2):301-320, 1981.
12

---

[35] J Doyle, K Glover, P Khargonekar, and B Francis. State-space solutions to standard 22 and oo control problems. IEEE Transactions on Automatic Control, 34:831-847, 1989.
[36] Tamer Başar. Minimax disturbance attenuation in LTV plants in discrete time. In American Control Conference, pages 31 11-31113 13, 1990.
[37] Tankred Rautert and Ekkehard W Sachs. Computational design of optimal output feedback controllers. SIAM Journal on Optimization, 7(3):837-852, 1997.
[38] Karl Märtensson and Anders Rantzer. Gradient methods for iterative distributed control synthe- sis. In IEEE Conference Decision and Control held jointly with Chinese Control Conference, pages 549-554, 2009.
[39] Jingjing Bu, Lillian J Ratliff, and Mehran Mesbahi. Global convergence policy gradient for sequential aero-sum linear quadratic dynamic games. arXiv preprint 1eXiv:9911.40000 2019.
[40] Benjamin Gravell, Peyman Mohajerin Esfahani, and Tyler Summers, Learning robust controllers for linear quadratic systems with multiplicative noise via policy gradient. arXiv preprint 1rXiv:1907.03668 2019.
[41] Jingjing Bu and Mehran Mesbahi. Global convergence of policy gradient algorithms for indefinite least squares stationary optimal control. IEEE Control Systems Letters, 4(3):638 643, 2020.
[42] Vincent Roulet, Maryam Fazel, Siddhartha Srinivasa, and Zaid Harchaoui. On the convergence of the iterative linear exponential quadratic gaussian algorithm to stationary points. In American Control Conference, pages 132-137. IEEE, 2020.
[43] Yingying Li, Yujie Tang, Runyu Zhang, and Na Li. Distributed reinforcement learning for decentralized linear quadratic control: A derivative-free policy optimization approach. arXiv preprint arXiv: 19/2.099/2009133 2019.
[44] Joao Paulo Jansch-Porte Bin Hu, and Geir Dullerud. Policy learning of MDPs with mixed continuous/diserete variables: A case study model-free control of Markovian jump systems. In Learning for Dynamics and Control, pages 947-957, 2020.
[45] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator. Foundations of Compulational Mathematics, 20(4):633-679, 2020.
[46] Yang Zheng, Luca Furieri, Maryam Kamgarpour, and Na Li. Sample complexity of linear quadratic Gaussian (LQQ) control for output feedback systems. In Learning for Dynamics and Control, pages 559-570. PMLR, 2021.
[47] Yasin Abbasi-Yadkori quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pages 1-26. JMLR Workshop and Conference Proceedings, 2011.
Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear
[48] Max Simchowitz and Dylan Foster. Naive exploration is optimal for online LQR, In Interna- tional Conference on Machine Learning, pages 8937-8948. PMLR, 2020.
[49] Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. Advances in Neural Information Processing Systems, pages 9236-9246, 2018.
[50] Ya-Ping Hsieh, Chen Liu, and Volkan Cevher. Finding mixed Nash equilibria of generative adversarial networks. In International Conference on Machine Learning, pages 2810-2819, 2019.
[51] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? In International Conference on Machine Learning. 2020.
13

---

[52] -amsinoul-Vasileios Vasileios Vlatakis Vlatakis-Gkaragee Gkaragkounis, Lampros Flokas, and Georgios Piliouras. Poincaré recurrence, cycles and spurious equilibria gradient-descent-ascee for non-convex non-concave zero-sum games. In Advances in Neural Information Processing Systems, pages 10450-10461, 2019.
[53] Junchi Yang. Negar Kiyavash, and Niao He. Global convergence and variance-reduced op- timization for a class of conconvex-nnocooeawy minimax problems. In Advances in Neural Information Processing Systems, 2020.
[54] Jelena Diakonikolas, Constantinos Daskalakis, and Michael I Jordan. Efficient methods for structured nonconvex-nonconccaee min-max optimization. arXiv preprint arXiv:2011.00 1.00364, 2020.
[55] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. arXiv preprint UrXiv:2009.09623, 2020.
[56] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint arXiv:/911.10633, 2019.
[57] Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
[58] Jun Morimoto and Kenji Doya. Robust reinforcement learning. Neural computation, 17(2)3335- 359, 2005.
[59] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In International Conference Machine Learning, pages 2817-2826, 2017.
[60] Kaiqing Zhang, Bin Hu, and Tamer Başar. On the stability and convergence of robust adversarial reinforcement learning: A case study on linear quadratic systems. In Advances in Neural Information Processing Systems, 2020.
[61] Arnb Nilim and Laurent El Ghaoui Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780- 2005.
[62] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280, 2005.
[63] Shiau Hong Lim, Huan Xu, and Shie Mannor. Reinforcement learning in robust Markov decision processes. In Advances in Neural Information Processing Systems, pages 701-709, 2013.
[64] Shiau Hong Lim and Arnaud Autef. Kernel-based reinforcement learning in robust markov decision processes. In International Conference on Machine Learning, pages 3973-3981, 2019.
[65] Daniel J Mankowitz, Nir Levine, Rae Jeong, Abbas Abdolmaleki, Jost Tobias Springenberg, Timothy Mann, Todd Hester, and Martin Riedmiller. Robust reinforcement learning for continu- control with model misspecification. arXiv preprint /:Xiv:/906.075/6 2019.
[66] Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, and Qiaomin Xie. Risk- sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret. arXiv preprint arXiv:2006.13880 13277, 2020.
[67] Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Robust policy gradient against strong data corruption. arXiv preprint arXiv:2102.05800 2021.
[68] Isaac Kaminer, Pramod Khargonekar, and Mario A Rotea. Mixed Hz/Hos control for discrete-time systems via convex optimization. Automatica, 29(1)577770, 1993.
[69] Lloyd Shapley. Stochastic games. Proceedings of the National Academy of Sciences, -99-0010095-1100 1953.
14

---

[70] Michael L Littman. Markov games as framework for multi-agent reinforcement learning, In Machine Learning Proceedings, pages 157-163. Elsevier, 1994.
[71] Kaiqing Zhang, Sham M Kakade, Tamer Başar, and Lin F Yang. Model-based multi-agent RL in zero-sum markov games with near-optimal sample complexity. arXiv preprint wrXi::2007.07611, 2020.
[72] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems, pages 14934-14943 2019.
[73] Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex-concan minimax problems. In International Conference on Machine Learning, 2020.
[74] Tanner Fiez and Lillian Ratliff. Gradient descent-ascent provably converges to strict local minmax equilibria with finite timescale separation. arXiv preprint arXiv:2009.14882 2020.
[75] Christian Berg. Kompleks Fanktionsteori. Universitesshogladen, 2001.
[76] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[77] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without gradient. ACM-SIAM Symposium on Discrete Algorithms, pages 385-394, 2005.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] As initial attempt, we focus on the fundamental LQ settings and do not optimize the dependencies with respect to various parameters in sample complexity bounds. Based on the intricate analysis established in $4, we expect that accelerated algorithms with sharper rates could be developed. Despite the above limitations, these LQ robust control settings help pave the way for future investigations into whether and how model-free PO methods converge for general safety-critical controller designs. More importantly, our results bridge the gap between classical robust control concepts and modern policy-based RL theories, pushing forward the development of RL for safety-critical controller designs in the broader community of learning for control. Based on this robust control perspective, researchers could potentially improve the robustness of existing policy-based RL algorithms, and also develop new model-free RL algorithms with strong safe on-the-fly robustness guarantees.
believe that results and insights for
(c) Did you discuss any potential negative societal impacts of your work? [Yes] we do not believe work will cause any potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The only assumption that have made is Assumption 2.1, which is standard in the literature. (b) Did you include complete proofs all theoretical results? [Yes] The proofs are deferred to the supplementary material, see the first page of our appendix for an outline.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] All code and data are included in the supplementary material.
15

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See $D of our appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- randomness iments multiple times)? [No] For the exact PG updates (3.13) (3.13)-(3.13
enters only when we are randomly searching for an initial Kg E IC in S(d, m, m,N), where deter- (id, m) is defined in $3. For given Kg K. fixed, exact PG updates ministic and thus not affected by varying random seed. For the zeroth-order updates (4.1), (4.2), and (4.3), randomness enters into the optimization process in addition initialization. However, we utilize mini-batch gradient estimators with large batchsizes sample PGs at high accuracy, thus the effects of random seeds minimal.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See $D of our appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 'r using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "xft5zQwLfnz", "reviewer": "Reviewer_16Qr", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This article contains novel convergence results of policy gradient methods for multi-agent problems, which are important contributions to the literature. Even though the details have not been carefully checked, the theoretical results seem to be correct. I don't have any further suggestion to improve the paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes,", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "mtpLykgWNxG", "reviewer": "Reviewer_cU8A", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work studies the application of policy gradient-type algorithms to the LEQG and LQ disturbance attenuation problems, both fundamental problems in robust control. Rather than analyzing these problems directly, it shows that there is a reduction from each of these problems to the LQ game problem, and then analyzes the LQ game problem, obtaining guarantees for the LQ game problem which then apply to the LEQG and LQ disturbance attenuation problems.\n\nIn addition to analyzing standard policy gradient methods, it also analyzes derivate-free methods that rely on estimation of the gradient from rollouts of the system’s trajectories. It provides finite-time convergence guarantees for both and shows that both types of algorithms converge to the Nash equilibrium controller. A core technical challenge in obtaining these results is that, unlike LQR where the cost blows up when the controller leaves the feasible set, here the cost may not blow up when the controller leaves the feasible set, and further regularization is needed. To handle this, the authors show that the proposed algorithm has an implicit regularization property, and ensures feasibility of the controller throughout learning. \n\nThe primary novel contribution of interest in this work is their analysis of the sample complexity of derivative-free methods to the LQ game problem and control problems more complex than LQR. To my knowledge this is the first work that gives explicit sample complexities on the number of trajectories needed to guarantee converge of derivative free methods on these problems, and in addition shows that assuming sufficiently many samples are collected, the controllers produced when running the algorithm always stabilize the system. \n\n\nPros:\n- The question of sample complexity of derivate-free methods for LQR has been studied in several works now, and several works look at the convergence of pure policy gradient methods in robust control settings, but no works have yet considered the sample complexity of derivative free methods for robust control. As such, this work addresses a relevant problem that is of interest to the community. \n- While the rates obtained are likely suboptimal, this work makes a non-trivial contribution in that it obtains polynomial rates, and deepens our understanding of robust control. \n\n\nCons:\n- In my opinion the main novel aspect of interest in this paper are the results in Section 4. However, the sample complexity results given appear to be very suboptimal (they achieve a rate of O(1/epsilon^5) while it is known that for LQR a rate of O(1/epsilon^2) can be achieved [3]). At minimum some discussion of the optimality is required, while none is given. Furthermore, the dimensionality dependance and dependence on curvature parameters is hidden in the main text, but should be made clear (I would expect something comparable to the statements in [3]).\n- In addition, I could not find a clear statement of what ’N’, the rollout length, must be. While the focus of this work is slightly different than works such as [4] that study regret for LQR in terms of the total samples taken, it is still of interest in this setting to state precisely how many total samples are needed for the optimization procedure. \n- I believe the paper could be reorganized slightly in order to make clear what the primary novel contributions are. In particular, it seems that most of the results in Section 3 are closely related to existing results (e.g. [1] studies policy gradient methods for the LEQG problem and [2] studies policy gradient methods for the LQ game problem), and the main novel results of interest are in Section 4. I would suggest expanding Section 4 and shrinking Section 3 to highlight these results. In doing this, it would be useful to put the algorithms from Section 4 (e.g. Algorithm 1 and Algorithm 2 in the appendix) in the main text. Currently, when reading section 4, it is rather unclear what the actual query model is, which makes it difficult to parse the theorem statements (for example, a ‘minibatch’ is never defined in the main text, though this is an essential parameter in the algorithm and important for understanding the true sample complexity). \n- Similarly, more discussion should be given on comparing to existing works and highlighting the novel aspects of this work.\n- Assumption 2.1 is stated as an assumption on the two-player game problem, but due to the equivalence between the various settings also imposes a constraint on the allowable LEQG and LQ disturbance attenuation problems. How restrictive is this assumption in these settings? It should be discussed in more detail. \n\nIn summary, I believe this work does make a contribution to a problem of interest in its analysis of DFO methods for robust control, yet the suboptimality of the sample complexity and lack of clarity in the presentation of the results makes it difficult for me to recommend an accept. \n\n------------------------------------\n\nUpdate after rebuttal: I believe the authors' response to my concerns, and in particular their explanation of the O(1/epsilon^5) dependence, seems reasonable and I have raised my score accordingly.\n\n\n[1] Zhang, Kaiqing, Bin Hu, and Tamer Basar. \"Policy Optimization for $\\mathcal {H} _2 $ Linear Control with $\\mathcal {H} _\\infty $ Robustness Guarantee: Implicit Regularization and Global Convergence.\" Learning for Dynamics and Control. PMLR, 2020.\n[2] Bu, Jingjing, Lillian J. Ratliff, and Mehran Mesbahi. \"Global convergence of policy gradient for sequential zero-sum linear quadratic dynamic games.\" arXiv preprint arXiv:1911.04672 (2019).\n[3] Malik, Dhruv, et al. \"Derivative-free methods for policy optimization: Guarantees for linear quadratic systems.\" The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.\n[4] Simchowitz, Max, and Dylan Foster. \"Naive exploration is optimal for online lqr.\" International Conference on Machine Learning. PMLR, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "jM46TPMmriV", "reviewer": "Reviewer_1dUQ", "summary": "In this paper, the authors established the first sample complexity result of the policy gradient method for a class of risk-sensitive linear-quadratic control problems. This class of control problems can also be viewed as a class of zero-sum two-player games.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\nCompared to the seminal work (Fazel et. al 2018) which considers an LQR problem with deterministic dynamics and infinite time-horizon, the set-up in this paper (with stochastic dynamics and finite time-horizon) has more applications but is less understood in the literature.\n\nThis paper provides the first convergence and sample complexity results for this important control/game framework. I believe it will be a nice contribution to the literature of RL theory. \n\nCons:\n\nCompared to the existing works ([1], [2], and [3]), the technical contributions should be further elaborated. Are there any additional technical difficulties when integrating partial ideas from [1] and [2]? To handle the stochastic dynamics and the finite time-horizon, are there any technical similarities or differences compared to [3]?\n\t \t\nFrom a game perspective, the inner-loop updates for L (under a fixed K) seem to be time-consuming and not practical for certain applications. Is it possible to extend the result to an iterative framework where L is updated once which followed by one update of K? \t \t\t\t\t\t\n\n[1] Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Policy optimization provably converges to Nash equilibria in zero-sum linear quadratic games. In Advances in Neural Information Processing Systems, pages 11602–11614, 2019. \n[2] Kaiqing Zhang, Bin Hu, and Tamer Basar. Policy optimization for H2 linear control with H1 robustness guarantee: Implicit regularization and global convergence. arXiv preprint arXiv:1910.09496, 2019. \t\n[3] Ben M Hambly, Renyuan Xu, and Huining Yang. Policy gradient methods for the noisy linear quadratic regulator over a finite horizon. arXiv preprint arXiv:2011.10300, 2020. \n\n========after authors response=======\n Thanks for the response from the authors. I read the comments from other reviewers and the authors' responses to all reviewers. Risk-sensitive RL with robust design is a hard problem and I think this paper has a solid contribution to the theoretical front of RL. Also, I am happy with the response from the authors.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "3xHSlQZZiWk", "reviewer": "Reviewer_DsD5", "summary": "The paper analyzes policy gradient methods in the context of the Linear Exponential Quadratic Gaussian and the Linear Quadratic Disturbance Attenuation frameworks. It provides a reduction from these frameworks to a 2 player LQR game, and shows that given a polynomial number of sampled trajectories, one can solve this game and hence the original frameworks.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I should say that I am coming at this as someone who is very familiar with optimization, especially with zero order/bandit optimization. While I am also familiar with the conventional LQR setup in the context of such methods, I generally am not very familiar with control theory.\n\nMy answers to the \"originality, quality, clarity, and significance\" depend on some questions that I have for the authors. So I will directly state my questions.\n\n1. For the reduction described in Lemma 2.2, it seems that one requires at least some knowledge of the system. For instance, $D_t$ is a system matrix, and it seems that this is assumed to be known in order to make the reduction? A similar comment applies for $C_t$? Also, why is it reasonable that the noise covariance $W$ is known, which surely should also appear in the reduction? I agree that it is more reasonable for $R_t$ and $Q_t$ to be known, since these are typically designed by a user. But just to be clear, knowledge of these is also required?\n\n2. It seems that the inner loop solution step is more or less completely standard. We are given access to a (locally) smooth function that satisfies the PL inequality, and there is plenty of prior work which can handle this (Fazel et al., Malik et al. and others). Note that the local smoothness causes no real issues, because the Lipschitz constants should decay as the cost decreases (i.e. as the descent algorithm progresses). Am i accurate in this?\n\n3. The outer loop solution is quite interesting to me, and seems like the meat of this paper. As I said above, in prior work for convention LQR, the typical story is that if the cost function decreases, then the iterates’ stability/feasibility is preserved. This is no longer true here. The authors say that their proof shows that the $P_{K, L(K)}$ matrix itself is decreasing (in the PSD sense), and this is a consequence of the implicit regularization of natural gradient. Can the authors provide me with more explanation of why the decrease of $P_{K, L(K)}$ matrix is important? It seems like a more fine grained characterization of the decrease in cost.  Also, can the authors please provide more intuition (perhaps even using a few equations) for why the natural gradient has this implicit regularization property. I know that they tried to provide this in their paper, but honestly I struggled to understand it.\n\n4. As for the conversion of the population level algorithm to a sample based derivative-free algorithm, the authors discussed a few challenges, but this confused me. Note that the authors are only offering a polynomial sample efficiency guarantee, as opposed to a fine grained characterization of the sample complexity dependency on different problem parameters. Given this, it seems to me that there shouldn’t any issues? For instance, the authors state in their Proof Sketch of Theorem 4.2 that using estimated gradients can lead to deviations in the algorithm’s iterates from the algorithm’s iterates at the population level, and that such statistical errors may blow up over time. But can’t one simply use a very large (but of course still polynomial) number of samples to obtain a very accurate approximation of the population level gradients, and then simply mimic the population level analysis? Indeed, this is what is done in Fazel et al. in the conventional LQR setting. Or is this essentially what the proof sketch is arguing?\n\nOverall, to the best of my knowledge, I liked the paper and I think it makes a good contribution. My questions are more for my own understanding. As long as the answers to these questions are reasonable and don't raise any major red flags, I will keep my score. But I reserve the right to change my score, in the case that a different reviewer finds an issue that I agree with. So please answer the reviewers' questions in depth, since I will read the other reviews.\n\nI listed my confidence as a 3, but it is more like 3.5.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes they have. Thank you for doing this.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper analyzes policy gradient methods in the context of a two-player LQR game (which can be shown to correspond to certain robust control problems) and establishes polynomial sample complexity. The authors show that the optimization landscape is more difficult, as unlike standard LQR, a decrease in the objective does not ensure feasibility of the iterates. They propose a double-loop algorithm that alternates between optimizing controllers for the two players. For the problematic outer loop, they show that NPG and Gauss-Newton with certain step size preserve feasibility. They extend the results to the case where gradients are estimated from samples, and show a polynomial sample complexity.
The established sample complexity seems suboptimal, and the paper could be organized better, especially when it comes to terms of positioning contributions in the context of existing work. However, overall the contributions are strong enough to warrant acceptance.

Decision: Accept (Poster)