Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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. 
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. 
limitations_and_societal_impact: Yes,
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

main_review: Pros:

Compared 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.

This 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. 

Cons:

Compared 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]?
	 	
From 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? 	 					

[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. 
[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. 	
[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. 

========after authors response=======
 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.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

In 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. 

The 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. 


Pros:
- 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. 
- 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. 


Cons:
- 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]).
- 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. 
- 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). 
- Similarly, more discussion should be given on comparing to existing works and highlighting the novel aspects of this work.
- 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. 

In 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. 

------------------------------------

Update 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.


[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.
[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).
[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.
[4] Simchowitz, Max, and Dylan Foster. "Naive exploration is optimal for online lqr." International Conference on Machine Learning. PMLR, 2020.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

My 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.

1. 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?

2. 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?

3. 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.

4. 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?

Overall, 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.

I listed my confidence as a 3, but it is more like 3.5.
limitations_and_societal_impact: Yes they have. Thank you for doing this.
review_title: null

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)