Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces the first direct policy search algorithm (a model-free gradient descent type algorithm) with the global optimum convergence guarantee for solving the output estimation (OE) problem of a linear dynamical system, given Gaussian noises and partial observations.

To learn the global optimality condition related to the first-order stationary point, previous literature limited to the study of minimality condition, where gradient descent might still fail to converge to the global optimum and only converge to a suboptimal stationary point. This paper introduces a stronger condition, informativity, that is sufficient to imply that all informative stationary points are global optimum.

Thus, in order to maintain the informativity condition, the authors add regularizations to the loss function $\mathcal{L}_{\texttt{OE}}$ and show that the suboptimality of the regularized loss function $\mathcal{L}_\lambda$ upper bounds the suboptimality of the original one. The informativity is crucial to establish the weak Polyak-Łojasiewicz (PL) condition of the function $\mathcal{L}_\lambda$. Further, by adding a reconditioning step, the loss function $\mathcal{L}_\lambda$ maintains the smoothness property in the compact set. The resulted algorithm is called informative-regularized policy gradient (IR-PG). Combined with the weak PL condition and the smoothness, the authors establish $\mathcal{O}(1/T)$ sublinear global optimal convergence rate of the algorithm IR-PG.
strengths_and_weaknesses: My knowledge on optimal control theory is limited. As far as I can tell, the work tackles a rather important open problem and the authors are the first to do it successfully. Most of the work in the paper neatly builds up to the main global optimum convergence result Theorem 2 in Section 3.3 and this is done in a sound manner. The discussion between the previous work minimality criterion and the informativity in Section 3.1 and the experiments in the appendix are also interesting and help to understand under which condition gradient descent of such problem will converge.

However, I found the paper to be quite hard to follow. For instance, the controllability condition in Assumption 2.4 is not defined before, which is only provided late in Appendix E. One stylistic choice by the authors that has made my reading harder is the lack of the clear definitions for many variables, e.g. $\Sigma_{11}, \Sigma_{22}, \Sigma_{11,\text{sys}}$. What is the similarity or difference between $\Sigma_{11}$ and $\Sigma_{11,\text{sys}}$ or $\Sigma_{22}$ and $\Sigma_{22,K}$ ? For instance, they can be properly defined together with the notation section in the appendix.
questions: 1. Is the informativity condition enough to show the weak PL condition of $\mathcal{L}_\lambda$ ? If this is the case, the authors should highlight this aspect earlier when introducing the informativity. This is an important motivation, as weak PL condition implies the global optimality of the first-order stationary point.

2. In LQR, [1] only shows that the loss function is "almost" smooth, which does not satisfy the smoothness condition. Could you bring more insights why $\mathcal{L}_\lambda$ is smooth.

3. What is the value of $d_z$ in Proposition 4.2 ? It should be provided in the proposition as well.

[1] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gra- dient methods for the linear quadratic regulator. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceed- ings of Machine Learning Research, pages 1467–1476. PMLR, 10–15 Jul 2018.

Typos:

Line 178-179: subsampled in discrete intervals

Line 259: see Appendix E.4 for proof

Algorithm 1 Line 2: $t = 0, 1, 2$; Line 4: $\nabla_t$

Line 302: $x : f(x) \neq \infty$

Line 303: on a domain $\mathcal{K}$

Line 319: in two aspects


limitations: The authors have adequately addressed the limitations of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies a policy search algorithm for the output estimation problem of a linear dynamical system, with provable convergence to the globally optimal dynamic ﬁlter. 
strengths_and_weaknesses: ## Strengths
- This paper deals with a challenging problem of policy search in linear dynamical systems, yet provable convergence is achieved and the proof seems to be theoretically sound. 
- The proposed notion of informativity characterizes the existence of critical points and hence well motivates the proposed IR-PG algorithm which appears to be novel. 
- The technical tools used might be of independent interest.

## Weaknesses
- The writing and organization of this paper could be improved. Currently, it's relatively hard to follow, especially Section 4 where technical definitions and propositions are presented. It is suggested that the author provide more intuition/motivation for the analysis. 


questions: How does the regularization parameter $\lambda$ influence the optimization landscape? What happens to the limiting cases where $\lambda$ vanishes? Is there any trade-off/criteria in choosing $\lambda$ from either a theoretical or practical perspective?

limitations: I don't see any limitations or potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The submission concerns a model-free policy gradient method to find the feedback gain of an observer in the linear Gaussian setting, i.e. find the Kalman gain. This optimization problem runs into issues due to the observer maintaining an internal latent Gaussian state, therefore the authors propose an additional regularization term that ensures the internal covariance is sufficient rank. 
strengths_and_weaknesses: This is obviously work of high quality. I am not well-versed in this aspect of the theory, but I can appreciate that this analysis will be of value for researchers looking at similar partially-observed problems.

However, I take some issue with the 60 pages of dense appendix. I wonder why work of such maturity and breadth is submitted to a conference and not a journal, where the review process affords more time and care. I unfortunately did not have time to review this paper in great enough detail that I think it requires, and I also think expecting a reviewer to consider ~70 pages is a rather big ask. 

I read through the main text and did not have any concerns, however I found the motivation for 'model-free Kalman filtering' (29 --38), beyond the need to develop sufficient theoretical tools for further study, a bit daft. I think the theoretical study and open nature to the problem is sufficent motivation.

One aspect I found quite strange (47 -- 59) is that we typcally use a time-varying Kalman gain in state estimation / LQG, whereas this work purely looks at a fixed feedback gain in the stationary case. A discussion about the challenges of model-free methods and their analysis for the more common finite-horizon case could be beneficial to the reader.
 
questions: Are the terms 'static' and 'dynamic' established? Because I think 'with memory' and 'memoryless' is perhaps a clearer wording for the distinction used in the paper, since it makes me think of fixed vs time-varying policies. 
limitations: No issues
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a direct policy search algorithm for the output estimation (OE) problem. The authors provide the global optimality guarantee of their algorithm in linear dynamical systems.
strengths_and_weaknesses: pros: 1. The paper discusses the problem and settings in detail.

2. The intuition behind the proposed framework is also clear and inspiring.

3. The theoretical results might be an important milestone for the community.

cons: 1. I'm not an expert in output estimation (OE) problems. Is it restricted to partially observed *linear* dynamical systems? It might be better to include the linear setting in the title.

2. Can the authors explain when suboptimal stationary points occur when the system is observable or controllable?
questions: See the cons above.
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper deals with state-space models with linear Gaussian transition and emission models (related terms for this setup are output estimation, Kalman filtering, multivariate autoregressive Gaussian state-space models). This work focuses on continuous-time problems without control inputs. The authors propose a gradient-based algorithm that uses a regularizer term and show that it converges to the global optimum.
strengths_and_weaknesses: ### Strengths

* The paper identifies a vulnerability in gradient-based optimization of filter matrices and proposes a solution. Both problem and solution are based on a well-motivated mathematical analysis.

* The authors find a new condition that qualifies a critical point as the global optimum. Crucially, the set of points that satisfy the condition is amenable to gradient descent. This would be a landmark result if it is novel (and as far as I can tell it is, but as I've indicated with my confidence score, my expertise is limited).

### Weaknesses

* The paper's connections to control problems are somewhat weak. The authors themselves acknowledge that the output estimation problem is not a control problem. Still, the paper places a heavy emphasis on framing this state estimation problem as a control problem. I am not sure I agree with the usage of terms such as policy gradient and policy search, for instance. None of this disqualifies the paper's contributions in other areas, but if the authors wish to present their work as related to reinforcement learning and optimal control, I believe the connections there need to be explored more in the text.

* I find the structure of the paper a bit difficult to follow. The paper presents many mathematical results before it becomes clear why these are necessary, which makes it harder to follow the author's line of reasoning. No doubt my own lack of familiarity with the content played a role here though.
questions: * Can you elaborate on the connection between your work and control problems? I can see that both LQG and OE require a hidden state that is maintained over time, but the same can be said about any state estimation problem and any POMDP. What I'm missing here is a decision-making aspect, where the outputs of the policy would affect which future states are visited.

* If we view OE as a control problem, the "cost" of this problem has a very specific form: $(Gx - u)^2$ (where I replaced $\hat z$ from eq. 1.3 or $C_K \hat x$ from eq. 1.2 with u to highlight the fact that it is a control). Do you see this as an issue in terms of how limiting it is? I don't think I can think of many control problems that have such a cost.
limitations: I don't have any concern for societal impact. The authors do discuss the precise mathematical perimeter where their results apply.
review_title: null

Meta-review: metareview: The paper establishes the first global optimum convergence guarantee for solving the output estimation (OE) problem of a linear dynamical system through a model-free gradient descent algorithm. The contribution is novel and of interest for the community. All the reviewers are convinced by authors' answers and agree that the paper is a solid contribution.
confidence: Certain
Decision: Accept