Globally Convergent Policy Search for Output Estimation
Authors: Jack Umenberger
Max Simchowitz
Juan Carlos Perdomo
Kaiqing Zhang
Russ Tedrake
Venue: NeurIPS 2022 Accept (2022)
Keywords: Model-free reinforcement learning
policy optimization
global convergence
partially observable systems

Abstract: We introduce the first direct policy search algorithm which provably converges to the globally optimal dynamic filter for the classical problem of predicting the outputs of a linear dynamical system, given noisy, partial observations. Despite the ubiquity of partial observability in practice, theoretical guarantees for direct policy search algorithms, one of the backbones of modern reinforcement learning, have proven difficult to achieve. This is primarily due to the degeneracies which arise when optimizing over filters that maintain an internal state. In this paper, we provide a new perspective on this challenging problem based on the notion of informativity, which intuitively requires that all components of a filter’s internal state are representative of the true state of the underlying dynamical system. We show that informativity overcomes the aforementioned degeneracy. Specifically, we propose a regularizer which explicitly enforces informativity, and establish that gradient descent on this regularized objective - combined with a “reconditioning step” – converges to the globally optimal cost at a $O(1/T)$ rate.

Globally Convergent Policy Search for Output Estimation
Jack Umenberger CSAIL, MIT
Max Simchowitz CSAIL, MIT
Juan C. Perdomo EECS, UC Berkeley
umn.orgr@mit.cm
ms msimchow@mit.c edu
soperddco@bbreee edu
Kaiqing Zhang CSAIL & LIDS, MIT
Russ Tedrake CSAIL, MIT russt russt@mit.. edu
kaiqingemmit.edu
Abstract
We introduce the first direct policy search algorithm which provably converges to the globally optimal dynamic filter for the classical problem of predicting the outputs of a linear dynamical system, given noisy, partial observations. Despite the ubiquity of partial observability in practice, theoretical guarantees for direct policy search algorithms, one of the backbones of modern reinforcement learning. have proven difficult to achieve. This is primarily due the degeneracies which arise when optimizing over filters that maintain an internal state.
In this paper, provide on the notion of informativiry, which intuitively requires that all components of a filter's internal state representative of the true state of the underlying dynamical system. We show that informativity overcomes the aforementioned degeneracy. Specifically, propose regularizer which explicitly enforces informativity, and establish that gradient descent on this regularized objective combined with a "reconditioning step" converges to the globally optimal cost ((1/7) rate.
perspective this challenging problem based
Introduction
Data used for prediction and control of real world dynamical systems is almost always noisy and incomplete (partially observed). Sensors and other measurement procedures inevitably introduce emors into the datasets, so designing reliable learning algorithms for these noisy partially observed domains requires confronting fundamental questions of disturbance filtering and state estimation. Despite the ubiquity of partial observation in practice, these concerns often underexplored in modern analyses of learning for control that assume perfect observations of the underlying dynamics.
In this work, we study the output estimation (OE) problem learning to predict in partially observed linear dynamical systems. The output estimation problem is one the most fundamental problems in theoretical statistics and learning theory. Both in theory and in practice, advances in predicting partially observed linear systems have led to successes a variety of areas from controls to biology and economics, (c.f. e.g. Athans [1974], Lillacci and Khammash [2010], Gautier and Poignet [2001]). We revisit this classical problem from a modern optimization perspective, and study the possibility of learning the optimal predictor via model-free procedures and direct policy search.
Relative to model-based procedures, which first estimate the underlying dynamics and then return policy by solving optimization problem using the estimated model, model-free methods offer several potential advantages. For instance, direct policy search allows one to easily specify the com- plexity of the policy class over which one searches. In addition, model-free policy search optimizes
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

for performance directly on the true system, rather than an approximate model. As such, there is no gap between the model used for synthesis and the system on which the policy is deployed.
In light of these advantages, there has recently been significant interest from both theoreticians and practitioners in understanding the foundations of model-free decision making. So far, this attention has focused mostly on problems with full-state observation such as the linear quadratic regulator (LQR) or fully-observed Markov Decision Processes (MDPs), for which optimal policies are static (without memory). Progress on partially observed problems has been complicated by the difficulties associated with optimizing over dynamic policies (with memory) that maintain internal state to sum- marize past observations. In this paper, we provide the first policy search algorithm which provably converges to the globally optimal filter for the OE problem, and shed new light on the intricacies of the underlying optimization landscape.
The Output Estimation problem. We study one of the simplest and most basic problems with partial observability; the output estimation (OE) problem. In brief, the goal is to search for pre- dictor of the output z(I) a linear dynamical system given partial measurements y(). For the true system with states x(t) and dynamics that evolve according to,
x1( = Ax(() + ((), y(t) Cx(() + (t),, z(t) Gx((), x(0) 0,
(1.1)
w(t) iid (O, W1), v(t) lid NOO,, W2),
the goal is to find the parameters K = (Ak, Bk, Ck) of the filter (interchangably, policy),
xx() = Akε(t) + Bky(t), 2(t) Ck&(t),
(1.2)
that minimizes the steady-state prediction error,
1 T
ER / (2(() - 2(1)]Rat 0
Loz(K) = lim T-000
= lim Bl|z(() -(11)1 t-300
(1.3)
In this paper, we study solving the OE problem via model-free methods, where the goal is to search for the optimal filter parameters K (Ak, BK, Ck) using direct policy search without knowledge or estimation of the true system parameters A, C, G. W1, W2; see Section 2 for further details. The OE problem is not control problem per se, as decisions do not influence the state evolution of the true system (1.1). Nonetheless, it is an attractive stepping stone for studying model-free control. Like LQG, optimal policies for OE are dynamic, i.e. have memory. OE therefore serves as valuable testhed to develop the theoretical foundations of direct policy search for this important class of policies which has thus far remained poorly understood.
Related work. Recent years have witnessed resurgence of interest in direct policy search for control and reinforcement learning. Fazel et al. [2018] established global convergence of policy gradient methods discrete-time LQR. Subsequent work has sharpened rates [Malik et al., 2019], analyzed convergence under more general frameworks [Bu et al., 2019], and extended the analysis continuous-timg [Mohammadi et al., 2021]. Beyond I.QR, Zhang et al. [2020) analyzed policy search for mixed H2/ and risk-sensitive control. Sun and Fazel [2021] also considered analysis via convex reformulations, for state feedback problems. For discrete state-action MDPs, Agarwal et al. [2021] established convergence rates for a variety of policy gradient methods, cf. also Bhandari and Russo [2019]. All of these works considered static state-feedback policies, with perfect state information. For problems with partial observation which necessitates the use of dynamic policies the work most relevant our own Tang et al. [2021], which studied policy search for LOG. They established that all stationary points corresponding to minimal controllers are globally optimal, and demonstrated that gradient descent may fail to converge optimal policies.
1.1 Contributions
We propose a novel policy search method which provably converges to globally optimal Loe cost. Despite extensive prior work on static policy search (see above), our result constitutes the first rigorous guarantee for policy search over dynamic policies. While the OF problem admits a convex reformulation [Scherer al., 1997], it also well known that its landscape contains suboptimal critical points. This may seem like contradiction at first, but we demonstrate that such spurious

---

critical points occur precisely when the policy loses what we term "informativity": that the steady covariance between the controller state and system state, Σ1 lim + x(t)x(t) dtj, becomes rank-deficient. With this insight, we propose a regularizer R that ensures the internal state of the learned policy remains "uniformly informative" about the state of the true system, and prove that gradient descent on the regularized objective Lax(.) + XR(() converges at O (1/T) rate an optimal policy. The efficacy of the approach is illustrated via numerical experiments, cf. Appendix F.6. Code is provided in the supplementary material.
Our techniques. Searching over dynamic policies introduces two key challenges: (1) spurious critical points can arise when one or more factors become "degenerate" in a certain way; (2) changes of basis produce continuum of "equivalent realizations" of the filter K, some of which are poorly conditioned. Similar challenges have been observed problems with rotational symmetries, e.g- nonconvex matrix factorization. Neither challenge arises when searching over static policies [Fazel et al.. 2018J. Our approach is centered around the idea of convex reformulations of control syn- thesis problems, and the following fact regarding functions which admit these reformulations, ef. Appendix H.1 for proof.
Fact 1.1. Let f I + R. be differentiable, possibly nonconvex function such that ming f(x)) finite. Suppose there exists differentiable function Th - Th satisfying the following two properties: (i) the mapping V is surjective, i.e. for all x E TM there exists v E RaV such that = V (v). (ii) under the change of variables the function fevx (V) == ((V(v) is differentiable and convex. Then all first-order stationary points, æ s.t (z O, are globally optimal.
The OF problem, LQG, and many other related control tasks admit convex reformulations [Scherer ct al., 1997, Masubuchi et al., 1998]. Given that gradient descent (under mild regularity assumptions) converges to stationary points, we might hope that Fact 1.1 guarantees that direct policy search on the OE filter will succeed at finding an optimal policy, when applied to loss functions admitting such convex reformulations. Somewhat surprisingly, we find that this is emphatically not the case: gradi- ent descent on the Lo objective fails to reliably converge to optimal solutions (see Section 3.1).
To resolve this paradox, we show that the surjectivity condition of Fact 1.1 may fail for the convex reparametrization of OR: there are filters with finite cost Loe (K), which are not in the image of the reformulation map (.). We find that degeneracy occurs precisely when informativity, defined in Section 1.1 as 12.K having full rank, fails to hold. Conversely, when Σ12K is full-rank, the conditions of Fact 1.1 are met and the paramctrization behaves as needed. Thus, we identify non- informativity rank deficiency of Σ as the fundamental notion of degeneracy corresponding to challenge (1). Motivated by this observation, we introduce novel "informativity regularizer" Rinfo which enforces that Σ12K is full rank. Our proposed algorithm, IR-PG alternates between gradient updates the regularized loss Lx(+) Loe(1) + XRinto (-), and "reconditioning" steps to ensure rell-conditioned realizations of the filters K, thereby addressing challenge (2) above. We stress that our notion of informativity differs from the minimality criterion emphasized in Tang al.
[2021], whose limitations we discuss in Section 3.1.
In order to achieve our quantitative converge guarantees, we establish numerous results which may be of independent interest, including: (i) a quantitative analysis of the OE convex reformulation due to Scherer [1995]. (ii) novel bounds the magnitude of solution to Lyapunov equations under the closed-loop OE filter dynamics. Both arguments appeal to (quantitative measure of) informativ- ity. Finally, we develop quantitative analogue of Fact 1.1 via paradigm call differentiable convex liftings, which allows us to establish a form of gradient dominance that we term weak- PL in reference to the well-known -ojaaak--ojssiiiizzz inequality; cf. Section 4.1 for details.
2 Preliminaries
Before presenting our main results in Section 3, we first introduce some relevant definitions, and provide the reader with some relevant background on prediction in partially-observe systems. We adopt standard notation wherever possible, and for brevity, defer details to Appendix A. As outlined in the introduction, consider the problem of predicting the outputs of a partially observed linear dynamical system. We refer to the dynamical system defined in Eq. (1.1) as the true
dynamical
Failure modes for the LQG problem were presented by Tang et al. [2021]]
3

---

system, with states x(t) E R", observations (t) E R" and performance outputs z(t) E R'. To ensure the dynamical system has a well-defined steady-state, we assume that A stable. Assumption 2.1. The matrix A is Hurwitz stable. That is, the real components of all its eigenvalues are strictly negative: (A)) < 0 for i E [n].
Because these policies only access the system outputs, and are only evaluated in relation to system outputs, we assume that the true system state is observable. Further, we assume that dynamics are subject to sufficiently rich noise excitations.
Assumption 2.2. The pair (A, C) in Eq. (1.1) observable. That is, the observability Gramian defined as Gohs = Jo exp(>A)T CT Cexp(sA)ds is strictly positive definite.
Assumption 2.3. We assume that the noise matrices W, and W₂ are strictly positive definite.
As stated previously, we restrict our attention to finding the best dynamic filter within the parametric family described in Eq. (1.2). Note that this family contains the Bayes optimal predictor for the Cos objective, as we will later describe in more detail. We review number of basic facts:
A. Steady state distributions. We define Kutaa == (K: Ak is Hurwitz-stable) be the set of filters such that Ak is stable. Under Assumption 2.1, Appendix E.1 shows that this is equivalent to the stability of the closed-loop matrix Act.k:
A BkC
A
Ak| Kotab [K: Act,k is Hurwitz-stable).
(2.1)
Stability of A is a sufficient condition for (K) to be finite, and for the following limiting covariance be well defined: ΣK lim E
x(1)
x(()
E s4 This steady-state covari-
8x(1)
8x(t)
ance is given by the solution to the continuous-time Lyapunov equation.
A + EAJ. + WaLK =,
where Walk := o
W. B
(2.2)
Notice that ΣK depends only on (Ak, Bk), but not on Ck, and that the first n x n block of ΣK does not depend on all. To highlight these distinctions, we partition
Σ Σ
E1 Σga
Σ Lys
Σ Σ22K
Σ =
ΣK =
(2.3)
Σ 12,K
and define Keerb (K E Ketab Σz2. > 0} as the set of filters whose internal state covariance is full rank. We refer to these as the controllable policies, as these are precisely the policies for which the pair (Ak, Bk) is controllable.
B. Equivalent realizations. There are many different ways of parametrizing a given dynamic feedback policy, all of which have exactly the same input-output behavior. Let CIL(n) denote the set of invertible n x matrices. In particular, given an invertible matrix S E GL(n) the OE loss of filter K is invariant under the following class of similarity transforms:
Sims (K) (Ak, BK: Ck) + (SAkS -1 SBK, CKS-').
(2.4)
Formally. for any K E Ketab and any S E GL((), (k)(K) = Cas Tuemmm We say that K and K' are equivalent realizations if they are related by a similarity transformation Sims = K' for some S E (L(n). Note that the set Ketro is also preserved under similarity transformation.
C. Optimal policies. The landmark result by Kalman shows that for the system defined by (A, C, W,, W2) the Kalman filter K. = (A - L,C, L., G) achieves minimal Lug loss. Here, L, is the Kalman gain which is defined in terms of the solution of the following Riccati equation:
AP. + P.A T - P.C - W + W, 0,
L, P...WWW'
(2.5)
We define the set of optimal filters Kapz to be those which are equivalent to the Kalman filter:
Kopt =
U
{Sims(A A L,C, L,, G)}.
(2.6)
SECL(m)
We may relax this assumption (A, W1) being controllable.

---

D. Restricted problem setting, The problem description outlined above, including Assump- tions 2.1 2.3, constitutes the standard OE problem, well-known in control theory, cf. [Doyle et al., 1989, $IV.D]. In this paper, we will make the following additional assumption that restricts the class of OE problems we consider. Further discussion on the utility and necessity of this as- sumption (for our analysis) is provided in Section 3.2 and Appendix D; the latter also shows that Assumption 2.4 holds for "generic" problem instances.
Assumption 2.4. The (cannonical) optimal policy (A L., is controllable, i.e.
Jo exp( (( - L, L, cxp(s(A - LA))) Td ds is strictly positive definite.
E. Interaction protocol. In the spirit of model-free methods, we introduce algorithms which work only assuming access to cost and gradient evaluation oracles. We abstract away the particular implementation of these oracles to simplify our presentation and assume that they are exact, in order to focus on the overall optimization landscape of the OE problem. More formally, for any filter K E Ketab. Eval(K, Lae) returns the OE cost, La (k)(K) and Grad(K, LOE) return the gradient of the OE cost, (K). Despite this simplification, we would like again emphasize that these can be efficiently approximated in finite samples, and purely on the basis of observations Yt subsampled in discrete intervals. For further discussion, please see Appendix C.
Lastly, in addition to standard cost and gradient evaluations of the Lae loss, as part of our algorithm, we further require access to gradient and cost evaluations of smooth functions of the stationary covariance. Specifically, if f 3 - R is a function of the covariance matrix K, we assume we can compute Evalcov (K, f) which returns the f(Ek) and Gradeov (K, f) which returns Vkf In Appendix C.2, we show that these oracles can be implemented without direct state access by "subsampling" multiple observations at different time steps.
3 Main Results
In this section, we present the main contributions of our work. After demonstrating that the OE cost function contains stationary points that not globally optimal, we present informativity- regularized policy gradient (IR-PG), a direct policy search algorithm based on a novel regular- ization strategy to preserve informativity, introduced in Section 1.1. We state formal convergence result showing that IR-PG converges to a globally optimal filter at a O (1/T) rate. The efficacy of IR-PG illustrated via numerical experiments in Appendix F.6, cf. Fig. in particular to see how informativity regularization dramatically improves the convergence of policy gradient methods.
3.1 Existence of suboptimal stationary points
Perhaps the simplest model-free approach to the OE problem is run gradient descent on Loe (-) Under mild assumptions on the loss function Lor. gradient descent will converge to a first-order stationary point of Coz. Unfortunately, despite the existence of convex reformulation [Scherer et al., 1997] and Fact 1.1, the Las loss function contains suboptimal stationary points:
Example 3.1. Consider the OE instance given by A -I, C I2,, W1
I,, W2 =2 L,,
and the filter Kbad given by Abad - x I2, >> 0, Bbad O2. Chad O2. Kbad constitutes suboptimal stationary point of Loe for this OE instance.
The example is similar in spirit to Tang et al. [2021, Theorem 431:; details are given in Appendix F.1. Importantly, the cost is invariant under perturbations to any single parameter of the filter and Knad being equivalent to the zero-filted filter,, is suboptimal. The same is true for any OE instance: every filter with Bbad = O, Cbad = O, and Abad being stable is a suboptimal stationary point of Log. We again emphasize that these suboptimal stationary points arise when the change of variables in the convex reparametrization "breaks down", i.c., these suboptimal filters are not in the image of the reformulation map (-) of Fact 1.1.
The perils of enforeing minimality. A filter K is minimal (Ak. Bk) is controllable, and (Ak, Ck) is observable. Example 3.1 is the extreme case of a non-minimal filter, since Bbad = Cbad = O2- Conversely, as a special case of LQG, the OE problem inherits the property that all stationary points corresponding to minimal filters are globally optimal [Tang et al., 2021, Theorem 4.3]. Therefore, it may be natural to ask: can a local search algorithm enforce minimality to avoid suboptimal stationary points? A classical result due to Brockett [1976] suggests not: the set of
5

---

minimal n-th order snneee-inpu-ssigle--oe transfer functions (e.g. filters) is the disjoint union of open sets. Thus impossible for a continuous path to pass from one of these open sets to another without entering region corresponding to a non-minimal filter, suggesting that local search algorithm regularized to ensure minimality every iteration may never converge the opti- mal solution (unless a sufficiently large, and lucky, step allows the iterate to hop over the boundary at non non-minimalltt). See Appendix F.2 for further discussion and supporting numerical experiments.
Futher challenges. Given the drawbacks of enforcing minimality, one may wonder whether it is sufficient enforce controllability or observability alone. In Example 3.1 above and indeed, for all the examples in Tang et al. [2021] of suboptimal stationary points in the LQG landscape there is loss of both observability (Cbad 0) and controllability (Baad 0). Unfortunately, suboptimal stationary points can occur at controllable policies and observable policies.
Example 3.2. Consider the OE instance given by
0 1
A
C= 12,
=1=3x 12.
W2 = 12,
and the filter Kbad given by
-
0 -7
1 0 0 0 Cbad =
1 0
A bad
Bbad =
0
7 > 0.
7
The filter Kbad a controllable but strictly suboptimal first-order critical point of Coe (K).
A formal proof is provided in Proposition F.1, but the intuition as follows: Kbad is suboptimal because no information about the second state of the true system ever enters the filter (due to sparsity Further discussion appears Appendix F.3,
of Bbad). However, Kosd is controllable as y where it is also shown that one can similarly construct examples of filters that are observable (but controllable) that correspond we also demonstrate that, for the setup in Example 3.2, the minimum eigenvalue of the Hessian 2 Las (Kubd) can be made arbitrarily close to zero by taking 7 in Abad to be arbitrarily large. This casts doubt on whether approaches based on saddle-poing escape with appropriate random perturbations [Jin et al., 2017] or acceleration [Jin et al., 2018] should be expected to work.
strictly suboptimal first-order critical points of Caz(K). There
3.2
A provably convergent algorithm
The previous discussion puts us in bind: regularizing to preserve minimality may introduce prob- lems related to sitt-dcccooneetdness:: yet, neither controllability nor observability alone suffi- cient to rule out suboptimal stationary points. We identify stronger condition called informativiry which is sufficient. We define the set of informative filters as
Kinto == {K E Ketab rank Σ12,k) = n].
First, we check that all optimal filters lie in this set, under Assumption 2.4 (proof in Appendix E.3).
Lemma 3.1. Under Assumptions 2.1 to 2.4, Kopt C. Kinto C. Ketrb- and Kinto is an open set.
Our key insight is that informativity is also sufficient to ensure optimality of stationary points, but does not cause cath-connectedness issues did for minimality (see Appendix G.3 for the proof).
Theorem 1. Let K E Kantt: then (i) there a continuous path lying Kinto connecting to some K, E Kopt and (ū) (Lz()) = 0, then K E Kayt-
Theorem 1 suggests that gradient descent with enforced informativity should converge to optimal filters. It not, however, implied by the landscape analysis of Tang et al. [2021], which focuses solely on minimal stationary points. Still, numerous challenges remain: (1) How can one enforce informativity a smooth fashion? (2) What quantitative measure of informativity provides quanti- tative suboptimality guarantees on approximate first-order stationary points? (3) Given that Coe (oe(K) need not have compact level sets (see Appendix F.3), how does one ensure that the iterates of policy search do not escape to infinity, reach regions where the loss of smoothness is arbitrarily poor?

---

The explained covariance matrix. In light of Theorem 1, we design a policy search algorithm which ensures that Σι2, remains full-rank throughout the search, but does so in quantitative fashion. Our central object is the explained covariance matrix, which measures how much of the covariance of the steady-state system x(t) is explained by the internal filter state Xx (t) in the large limit: ZK == lim (Cov (Cov[x(t)] E[Cov[x(() (t())).. When K E Ketrr Zk admits an elegant closed-form expression, which provides an alternative definition of Kinto:
ZK- E12K E
D 22,K 12,K:
so that Kinto {K K E Ketrb and ZK > 0}.
Since ZK is invariant under similarity transformations, Zk logue of Σı2K. Informally, the quadratic form v' Z is a sufficient statistic for how much infor- mation (t) contains about the "v-direction" of x()); see Appendix E.6 for precise statement.
be interpreted normalized
Explained-covarianee regularization. We preserve informativity by ensuring our iterates satisfy ZK > 0. To this end, we run gradient descent on the regularized objective for some À >
tx [Z I1 xc
K E Kinto otherwise.
(K) = (K) + A Rinto (K), where Rinto (K)
(3.1)
The proposed regularizer has several important properties. First, though Rinto is nonconvex in K, both Rinfo and La can be made convex under the same change of variables, in the sense of Fact 1.1, cf. Lemma I.2. In addition, Rinto is non-negative, and tends to oo as ZK approaches singularity. Furthermore, Rinfo is invariant under similarity transformations. Next, many of the essential quantities arising in our analysis can be bounded in terms of Zk² justifying ZK is a natural quantitative measure of informativity. Lastly, the set of global-min minimizers of (-nto is precisely the optimal filters for the OE problem, per the following lemma (see Appendix E.4 for proof).
Lemma 3.2 (Existence of maximal Zk). Under Assumptions 2. to 2.3, there exists unique Z, > 0 such that Z. = ZK if and only if E Kopt, and Z. 2 for all E Ketzb \ Koppt. Consequently, Kopt arg minke..... Rinto (K).
Lemma 3.2 directly implies that the suboptimality of C-(-) upper bounds the suboptimality in Los (-), so we can minimize LA as a proxy for minimizing LoE- Corollary 3.1. For any K, we have Coe mink Coe S (x(K) mink' Lx(K').
Reconditioning, We introduce additional normalization step between policy updates to ensure the iterates produced by our algorithm have well-conditioned covariance matrices; this in turn en- sures the iterates produced by algorithm remain in compact set, and that the smoothness of Zx is uniformly bounded, For any filter K E Ketzb such that Σ22, > 0, the reconditioning operator recond(K) returns a filter K' which equivalent to K, but for which Σ22, In. Formally..
recond(K) == Sims BK, Ck), where S = Exz.k 1/2 Since K and K' recond(K) are equivalent realizations, we have Coz(K) = Loz(K'), Ranso (K'), and thus L2 (K) = (K').
(3.2)
Statement of IR-PG. We can now describe our algorithm IR-PG, whose pseudocode is displayed in Algorithm 1. IR-PG applies gradient descent the regularized Lae objective, with additional balancing step between gradient updates. Appendix B. provides a variant where the step size is chosen by backtracking line-search, which enjoys the same rigorous convergence guarantees. To guarantee convergence to an optimal filter (and finiteness of Lx). we need to initialize at a filter such that Zk. > 0. i.e. Ko Kinro- Fortunately, random initializations from a continuous distribution satisfy this condition with probability (see Appendix E.7 for a formal statement and proof). Con- cerning the choice of X, the formal guarantees in Section 3.3 below hold for any > O. Nonetheless, the choice of X can influence the numerical properties of the loss function, such as smoothness and the size of the gradients; ef. Appendix F.6 for further discussion.
Our proposed algorithm also works with an approximate balancing recond(-), where recond(K) returns a K' which is equivalent to K, and [2aa - In] S e for some tolerance > 0 (e.g. 1/8).
7

---

Algorithm Informativity-regllaiia Policy Gradient (IR-PG)
1: Input: Initial Kn E Kinfo step size 0, regularization parameter À > 0
$ Define (K) == Coe (-) (+)+ Atr[Zx
2: for each iteration s = 0, 1, 2,............ do
3: Recondition K₁ (ec), where recond(-) is defined in Eq. (3.2).
4: Compute V (Kr)
5: Update K, K2 V/
3.3 Formal guarantees
We conclude this section by stating the formal convergence guarantee for IR-PG. Our results depend on natural problem quantities, among which is the minimum singular value of P. (as defined in Eq. (2.5)), which we show is always strictly positive.
Lemma 3.3. Let Le be the solution to the Riccati equation Eq. (2.5). Then under Assumptions 2.1 to 2.3, J = Xin (P+) is strictly positive. Moreover, P. = 11,,ys
Z.
In other words, P. the limiting conditional covariance of the true state x(t) given the poaicy-state *x(() under (any) optimal policy. Lemma 3.3 states that this covariance is nonsingular, i.e. not even optimal policies contain perfect information about any mode of xt)). Given an initialization Ko, our convergence rate depends polynomially the following problem parameters:
Caya max {I |II,, I[GI,, (IWal. W '1. //
II 1E o.
(3.3)
Theorem 2. Fix > O, Ko Kinto- There are terms C1, C2 2 1, which are most polynomial in n, m, Caye: A, X 11 and Lx(Ko) such that the iterates of IR-PG with any stepsize n S ट satisfy
C2 1j
(oe(K.) min (ke(K) < (K.)) min (x(K) &
V1
The formal guarantee for The oracle complexity of IR-PG is described in Appendix B.2. We sketch the highlights of the proof the following section, after introducing our DCL framework. A rigorous proof overview deferred to Appendix G.2.
stepsizes is nearly analogous, and given in Appendix B.1.
4 Analysis Framework
In this section, we sketch our analysis two halves. In the first, we provide a framework for analyzing gradient descent objectives which admit convex reformulations. This takes place in two parts: first, via our technique of differentiable convex liftings (DCLs) we establish a form of gradient dominance term weak-PL. Second, show that weak-PL, together with smoothness (i.e. upper bound on the magnitude of the Hessian) implies convergence of gradient descent at (11tt) rate. The DCL formalizes the developments in the "our techniques" discussion of Section 1.1.
Next, we instantiate the analysis framework regularized output estimation loss L, defined the previous section. It suffices to establish both (a) smoothness of LA and (b) weak-PL by exhibiting valid DCL. Interestingly, the upper bounds on both the Hessian magnitude and the weak-PL factor depend on the magnitude of tr (r(Zz)), which precisely what is controlled by the informativity regularizer in Eq. 13.1).
4.1 Differentiable convex liftings (DCLs)
This section introduces differentiable conver liftings (DCLs), rigorous and flexible framework for operationalizing convex reformulations of nonconvex objectives.
Preliminaries. To neatly accommodate optimization
constrained domains, express func- tions f 2d + Rh. as taking values in the extended reals := R U {20).* Given such an f. we
Beecause solely consider minimizations, R does not include

---

denote its domain dom(f): {æ f(x) # 20) as the set on which f is finite; we say f is proper if dom(f) /) * 0; we define its minimal value iff( = =nf f(x) We say E E8* on a domain K. if f is k-times continuously differentiable (and finite) on some open set containing K. C RR.
DCLS The DCL is generic template for convex reformulation that significantly generalizes the setup in Fact 1.1. Rather than relating / directly to a convex Sevr, we "lift" / to a function fitt by appending auxiliary variables. We then assume reparametrization & mapping the domain of fir to that of fevx in this higher dimensional space; intuitively, + is the "inverse" of v in Fact 1.1.
Definition 4.1. A triplet of functions (fexx fin, Φ) is a DCL of a proper function f R + Rf (1) feex Rd. + R is a proper convex function whose minimum is attained by some z"
(2) For some additional number of parameters de 2 0. firt Rd+d; + R is related via partial minimization: f(x) minger" (xtt( E).
(3) There is an open set y 2 dom(firt) for which y - dom(ferx) is E and satisfies fixe()) feex (+))).
Above, d2 and de are arbitrary dimensions representing the arguments of (.) and fire (z. respectively. The mere existence of a DCL implies that approximate stationary points of are also approximate minimizers, under conditions elaborated on below:
Theorem 3. Let f Id R be a proper function with DCL (fevx: firi, D). Then, for any x e dfm(f) at which f is differentiable, f satisfies the weak-PL condition:
Od, (V E))
(x)) 2 auci(() (x) (f(x)) - ifn((f), where (ipc (x)
max Earg min few(()
|| [ E) 2=1
gEarg min (1.)
Theorem 3 strengthens Fact 1.1 in two respects. For one, it does not impose any smoothness re- strictions on fire or fexxi in particular feex can be highly non-smooth and, due to the extended-real function formulation, can also include constraints. And second, the lifting fire adds considerable flexibility, which we show is necessary to capture the convex reformulation of OE (Appendix 1).
The factor (uci(w) depends ( E) for any & E arg min fas=(x, :). This captures how large perturbations of fist 's arguments must be in order to achieve a desired perturbation of the arguments of ferz, under the reparameteri- zation Φb The additional arguments in firt compared to f adds additional columns to V thereby making it easier ensure ad, (V)(.)) 0. On the other hand, the denominator measures the Eu- clidean distance between any minimizer of the convex function feox() (.) and image of (æ, {) under the reparameterization 4 and can be bounded under quite benign conditions.
two quantities. The numerator is the d,-th singular value of
Proof Sketch. The formal proof of Theorem 3 (given in Appendix H.2) takes special care to handle cases where fir, and feex are finite only restricted domains, well as possible non- smoothness; still, the main ideas behind are intuitive. For ferx being convex, ferx(z) iff(fer)) = <()V)() Using the DCL definition and analyzing the inverse image of point under 4 can also establish a gradient dominance result for fitt- Weak-PL for the original function f follows since ff is related to fist by partial minimization, so its gradients must be larger than those of fist-
Gradient descent with DCLs. We now describe how DCLS yield quantitative convergence guar- antees for gradient descent. A more general guarantee accommodating the reconditioning step in IR-PG is deferred to Appendix G. and encompasses the bound below as a special case. Given a >> O, we say that proper f IRd >> satisfies a-weak-PL. (named after the stronger Polyak- tojasiewicz condition) on domain K. c Rd if f E (IC) and [[[](=)] 2 a(f(x) - inf(J). From Theorem 3, we see f satisfies wx-weak PL on If has a DCL and ax := infzek aper > 0. To analyze gradient descent, we also require smoothness: we say f is S-upper-smooth on K. if EEE (X) and for all x E K. v²f(x) < 31. The following follows from a standard descent lemma for smooth (though possibly nonconvex) functions.
Proposition 4.1. Let Do E dom(s), and suppose that the level set K(xo) == (a: f(x) S <((x)))
is compact, and I satisfies Omng -weak PL with Orzg > O, and 3mg -uppe smoothness on K(x) with Am > 0. Then, Zo lies in the same path-connected component of some minimizer of J, and for any m S 1/Bao the updates Øx+1 = σx vVV((x)) satisfy f(xx) inf((f) S 2/(k- a)..).
9

---

4.2 Proof of Theorem 2.
In light of Proposition 4.1 (and its generalization to include reconditioning), it suffices to establish both the weak- PL and smoothness of the loss Lx(-) on the well-conditioned sublevel set Koo := {K (K) I (K()). ÿ 3 Σ22, I ) To establish the weak-PL property, we exhibit a DCL for which (kcc(() depends only on the operator norms of Σk. Ex! Zk: as well as other system- quantities. Here, poly.p(.... denotes quantity most polynomial in the operator norms of its arguments.
Proposition 4.2. For any X 2 O (non-strict), the objective (x(K) admits a DCL (ferzi fitt, 4) where the lifted parameter takes the form (K, Σk) E Kinto x S Lx(K) firt(K, Σx) millees"" Jite(K, E), and where
04, 0a, (VO(K, Ek)) 2 1/poly (A,C, W Dk, ZiK ZK Loe(K)) [[0(K, le, I (max(n, /mn} v (k)( poly (A,C,W5' EK, EK zk²)
Furthermore, the norms of the parameters Ak. BK, Ck satisfy the following bounds:
max{||A ||<llopp polyop (A,C, Zx' Ek, Ek), |[K]|e (K)/(1)/
(4.1)
Smoothness is established in (Proposition G.5), which relies on novel (and rather challenging) bound on the solutions to Lyapunov equations involving A,1
Proposition 4.3 (Stability of Act.). Suppose that K Kinto- Then, for any matrix Y E g2n the
solution Σk,y to the Lyapunov equation Act, ε + ΣK,Y A T + Y 0 satisfies
Elo CKy
|| where C1yap (K) poly (EK, Dx ZK' WT W W2'CO) C),
and where || lle denotes either the operator, Frobenius, nuclear norm.
The regularization Rinto (K) ensures Zzxll 'll remains bounded on the sublevel Ko; further show (Lemma G.7) that _T, < Σ22, 8 I, implies ΣK is invertible, and ensures || |[x|]] ll, |Ex] are uniformly bounded. Thus, the woestat. constant and smoothness parameters are uniformly bounded on Ko. concluding the proof. We stress that the proofs Proposition 4.2 and Proposition 4.3 require several novel technical arguments, which may be of independent interest. A full proof roadmap, including formal statements of the aforementioned results, is given in Appendix G.2. The fact that |E Ex II. Z appear throughout the analysis suggests that (a) informativity as measured by ZK and (b) the conditioning of Σ may be fundamental to the OE landscape.
Proof of Theorem 1. The proof of Theorem is simpler, as it relies mainly on the existence of a DCL for which Opcc. does not vanish. See Appendix G.3 for details.
5 Conclusion
In this work, we introduce the first direct policy search algorithm which converges to the globally optimal dynamic policy for the output estimation problem. We hope that our analysis serves valuable starting point to study direct policy search for reinforcement learning and control problems with partial observations, in which the relevant classes of policies are dynamic ones that maintain an internal state. We also hope that both our proposed principle of "informativity": and our technical contributions around convex reformulations, continue prove useful future work.
Acknowledgments and Disclosure of Funding
The authors acknowledge Pablo Parrilo and Tobia Marcucci for helpful discussions. J.U. is sup- ported by NSF Award No. EFMA-1830901, Office of Naval Research (ONR) Award No. N00014- 18-1-2210 and ONR Award No. N00014-17-1-2699, M.S. is supported by Amazon.com Services ILC,, PO# #D-06310223 and the MIT Quest for Intelligence. K.Z. is supported by Simons- Berkeley Research Fellowship.
10

---

References
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approxi- mate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. pages 1195-1155 1199, 2017.
Michael Athans. The importance of Kalman filtering methods for economic systems. In Annals of Economic and Social Measurement, Volume 3, number 1, pages 49-64. NBER, 1974.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv:1906.0/786, 2019.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Roger Brocket. Some geometric questions in the theory of linear systems. JEEE Transactions on Automatic Control, 2144):449-455, 1976. doi: 10. 197. 101301.
101301.
Jingjing Bu, Afshin Mesbahi, Maryam Fazel, and Mehran Mesbahi. LQR through the lens of first order methods: Discrete-time case. arXiv preprint 1rXiv:190700892, 2019.
Sébastien Bubeck. Convex optimization:
Algorithms and complexity. arXiv preprint
2014.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal Optimization, 2752)175 2018.
J.C. Doyle, K. Glover, P.P. Khargonekar, and B.A. Francis. State-space solutions to standard h2 and how control problems. IEEE Transactions Automatic Control, 34(8):831-847, 1989. doi: 10.1109/9.29425.
Guang-Ren Duan and Ron J Patton. A note hurwitz stability of matrices. Automatica, 34(4): 509-511, 1998.
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.
Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the Sixteenth Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, page 385-394, USA, 2005. Society for Industrial and Applied Mathematics.
Maxime Gautier and Ph Poignet. Extended kalman filtering and weighted least squares dynamic identification of robot. Control Engineering Practice, (12):1361-1372, 2001.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225-1234. PMLR, 2016.
Arieh Iserles. Ordinary differential equations, page 1-2. Cambridge Texts in Applied Mathematics. Cambridge University Press, 2 edition, 2008.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael Jordan. How to escape saddle points efficiently. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume Proceedings of Machine Learning Research, pages 1724-1732. PMLR, 06-11 Aug 2017.

---

Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Sébastien Bubeck. Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31sl Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 1042-1085. PMLR, 06-09 Jul 2018.
Claude Lemaréchal. Cauchy and the gradient method. Doc Math Extra, 251(254):10, 2012.
Gabriele Lillacci and Mustafa Khammash. Parameter estimation and model selection in computa- tional biology. PLoS computational biology, 6(3):e1000696, 2010.
Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter Bartlett, and Martin Wain- wright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2916-2925. PMLR, 2019.
Izumi Masubuchi, Atsumi Ohara, and Nobuhide Suda. LMI-based controller synthesis: A unified formulation and solution. International Journal of Robust and Nonlinear Control, 8(8):669- 686. 1998. doi: http://oo..rg111..000/////// 0.CO;2-W.
Hesameddin Mohammadi, Armin Zare, Mahdi Soltanolkotabi, and Mihailo R Jovanovic. Conver- gence and sample complexity of gradient methods for the model-free linear quadratic regulator problem. IEEE Transactions on Automatic Control, 2021.
Kevin Scaman and Cedric Malherbe. Robustness analysis of non-convex stochastic gradient descent using biased expectations. Advances in Neural Information Processing Systems, 33, 2020.
C. Scherer, P. Gahinet, and M. Chilali. Multiobjectiive outpu control via LMI optimization. IEEE Transactions Automatic Control, 42(7))896-911, 1997. doi: 10.1 109/9
Carsten Scherer. Mixed H2 /Hoo control. Trends in control, pages 173-216, 1995.
Yue Sun and Maryam Fazel. Learning optimal controllers by policy gradient: Global optimality via convex parameterization. 2021 60th IEEE Conference on Decision and Control (CDC), pages 4576-4588 IEEE, 2021.
Yujie Tang, Yang Zheng, and Na Li. Analysis of the optimization landscape of linear quadratic Gaussian (LQG) control. In Learning for Dynamics and Control, pages 599-610, PMLR, 2021.
Joel A Tropp. An introduction to matrix concentration inequalities. 1rXiv:1501.01571, 2015.
arXiv preprint
Stephen Wright, Jorge Nocedal, et al. Numerical optimization. Springer Science, 35(67-68):7, 1999.
Bin Yu. Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, pages 94-116, 1994.
Kaiqing Zhang, Bin Hu, and Tamer Basar. Policy optimization for Hz linear control with Hox robustness guarantee: Implicit regularivation and glohal convergence. In Alexandre M. Bayen, Ali Jadbabaie, George Pappas, Pablo A. Parrilo, Benjamin Recht, Claire Tomlin, and Melanie Zeilinger, editors, Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 179-190. PMLR, 10-11 Jun 2020.
Kemin Zhou, John Comstock Doyle, Keith Glover, et al. Robust and Optimal Control, volume 40. Prentice hall New Jersey, 1996.
12

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] . You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section.
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section 2.
(b) Did you describe the limitations of your work? [Yes] See Assumption 2.4 and Ap-
pendix
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(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] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See appendices.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] Code provided in supplementary materials.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix F.6.
(c) Did you report error bars (c.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] See Figs. 3 and 4.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See beginning of Appendix F.6.
4. If you using existing assets (e.g., code, data, models) 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 obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if 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 participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "ujCc5IvgqDy", "reviewer": "Reviewer_MNwe", "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.\n\nTo 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.\n\nThus, 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.", "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.\n\n2. 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.\n\n3. What is the value of $d_z$ in Proposition 4.2 ? It should be provided in the proposition as well.\n\n[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.\n\nTypos:\n\nLine 178-179: subsampled in discrete intervals\n\nLine 259: see Appendix E.4 for proof\n\nAlgorithm 1 Line 2: $t = 0, 1, 2$; Line 4: $\\nabla_t$\n\nLine 302: $x : f(x) \\neq \\infty$\n\nLine 303: on a domain $\\mathcal{K}$\n\nLine 319: in two aspects\n\n", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nHowever, 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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mcgfkyV8Lw", "reviewer": "Reviewer_zdF9", "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.", "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.\n\n* 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.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n* 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.\n\n* 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).\n\n### Weaknesses\n\n* 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.\n\n* 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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mY074lubxwI", "reviewer": "Reviewer_aK2U", "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.", "questions": "See the cons above.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "pros: 1. The paper discusses the problem and settings in detail.\n\n2. The intuition behind the proposed framework is also clear and inspiring.\n\n3. The theoretical results might be an important milestone for the community.\n\ncons: 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.\n\n2. Can the authors explain when suboptimal stationary points occur when the system is observable or controllable?", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "h6odMIVzO4y", "reviewer": "Reviewer_1P3M", "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. ", "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", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nHowever, 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. \n\nI 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.\n\nOne 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.\n ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JPT2KEPYOb", "reviewer": "Reviewer_6hcE", "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. ", "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?\n", "limitations": "I don't see any limitations or potential negative societal impact of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- 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. \n- 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. \n- The technical tools used might be of independent interest.\n\n## Weaknesses\n- 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. \n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept