Title: TOWARDS PROVABLE CONTROL FOR UNKNOWN LIN-EAR DYNAMICAL SYSTEMS

Abstract: We study the control of symmetric linear dynamical systems with unknown dynamics and a hidden state. Using a recent spectral filtering technique for concisely representing such systems in a linear basis, we formulate optimal control in this setting as a convex program. This approach eliminates the need to solve the nonconvex problem of explicit identification of the system and its latent state, and allows for provable optimality guarantees for the control signal. We give the first efficient algorithm for finding the optimal control signal with an arbitrary time horizon 𝑇 , with sample complexity (number of training rollouts) polynomial only in log 𝑇 and other relevant parameters.

1. INTRODUCTION:

Recent empirical successes of reinforcement learning involve using deep nets to represent the underlying MDP and policy. However, we lack any supporting theory, and are far from developing algorithms with provable guarantees for such settings. We can make progress by addressing simpler setups, such as those provided by control theory.

Control theory concerns the control of dynamical systems, a non-trivial task even if the system is fully specified and provable guarantees are not required. This is true even in the simplest setting of a linear dynamical system (LDS) with quadratic costs, since the resulting optimization problems are high-dimensional and sensitive to noise.

The task of controlling an unknown linear system is significantly more complex, often giving rise to non-convex and high-dimensional optimization problems. The standard practice in the literature is to first solve the non-convex problem of system identification-that is, recover a model that accurately describes the system-and then apply standard robust control methods. The non-convex problem of system identification is the main reason that we have essentially no provable algorithms for controlling even the simplest linear dynamical systems with unknown latent states.

In this paper, we take the first step towards a provably efficient control algorithm for linear dynamical systems. Despite the highly non-convex and high-dimensional formulation of the problem, we can efficiently find the optimal control signal in polynomial time with optimal sample complexity. Our method is based on wave-filtering, a recent spectral representation technique for symmetric LDSs (Hazan et al., 2017) .

1.1. OUR RESULTS:

A dynamical system converts input signals {𝑥 1 , . . . , 𝑥 𝑇 } ∈ R 𝑛 into output signals {𝑦 1 , . . . , 𝑦 𝑇 } ∈ R 𝑚 , incurring a sequence of costs 𝑐 1 , . . . , 𝑐 𝑇 ∈ R. We are interested in controlling unknown dynamical systems with hidden states (which can be thought of as being partially "observed"via the output signals). A vast body of work focuses on linear dynamical systems with quadratic costs, in which the {𝑦 𝑡 } and {𝑐 𝑡 } are governed by the following dynamics:

ℎ 𝑡+1 = 𝐴ℎ 𝑡 + 𝐵𝑥 𝑡 , 𝑦 𝑡 = 𝐶ℎ 𝑡 + 𝐷𝑥 𝑡 + 𝜂 𝑡 , 𝑐 𝑡 = 𝑦 ⊤ 𝑡 𝑄𝑦 𝑡 + 𝑥 ⊤ 𝑡 𝑅𝑥 𝑡 ,

where ℎ 1 , . . . , ℎ 𝑇 ∈ R 𝑑 is a sequence of hidden states starting with a fixed ℎ 1 . Matrices 𝐴, 𝐵, 𝐶, 𝐷, 𝑄, 𝑅 of appropriate dimension describe the system and cost objective; the {𝜂 𝑡 } are Gaussian noise vectors. All of these matrices, as well as the parameters of the Gaussian, can be unknown. The most fundamental control problem involves controlling the system for some time horizon 𝑇 : find a signal 𝑥 1 , . . . , 𝑥 𝑇 that minimizes the sum of these quadratic output costs 𝑡 𝑐 𝑡 . Clearly, any algorithm for doing so must first learn the system parameters in some form, and this is often the source of computational intractability (meaning algorithms that take time exponential in the number of system parameters).

Previously known algorithms are of two types. The first type tries to solve the non-convex problem, with algorithms that lack provable guarantees and may take exponential time in the worst case: e.g., expectation-maximization (EM) or gradient-based methods (back-propagation through time, like the training of RNNs) which identify both the hidden states and system parameters.

Algorithms of the second type rely upon regression, often used in time-series analysis. Since 𝑇 -step dynamics of the system involve the first 𝑇 powers of 𝐴, the algorithm represents these powers as new variables and learns the 𝑇 -step dynamics via regression (e.g., the so-called VARX(𝑝, 𝑠) model) assuming that the system is well-conditioned; see Appendix A. This has moderate computational complexity but high sample complexity since the number of parameters in the regression scales with 𝑇 , the number of time steps.

Our new method obtains the best of both results: few parameters to train resulting in low sample complexity, as well as polynomial computational complexity. In Section 2 we state the precise algorithm. The informal result is as follows.

Theorem 1.1 (Controlling an unknown LDS; informal). Let D be a linear dynamical system with a symmetric transition matrix 𝐴 and with size |D|. Then, for every 𝜀 > 0, Algorithm 1 produces a sequence of controls (x 1 , . .

EQUATION

Assuming i.i.d. Gaussian noise 𝜂 𝑡 ∼ 𝒩 (0, Σ), the algorithm samples Õ (poly (|D|, 𝐿, Tr Σ, 1/𝜀)) trajectories from D, and runs in time polynomial in the same parameters.

1.2. RELATED WORK:

The field of optimal control for dynamical systems is extremely broad and brings together literature from machine learning, statistical time-series analysis, dynamical system tracking and Kalman filtering, system identification, and optimal control. For an extensive survey of the field, see e.g. (Todorov, 2006; Bertsekas, 2000) .

Tracking a known system. A less ambitions goal than control is tracking of a dynamical system, or prediction of the output given a known input. For the special case of LDS, the well-known Kalman filter (Kalman, 1960) is an optimal recursive least-squares solution for maximum likelihood estimation (MLE) under Gaussian perturbations to a linear dynamical system.

System identification. When the underlying dynamical system is unknown, there are essentially no provably efficient methods for recovering it. For various techniques used in practice, see the classic survey (Ljung, 1998) . Roweis & Ghahramani (1999) suggest using the EM algorithm to learn the parameters of an LDS, nowadays widespread, but it is well-known that optimality is not guaranteed. The recent result of Hardt et al. (2016) gives a polynomial time algorithm for system recovery, although it applies only to the single-input-single-output case and makes various statistical assumptions on the inputs.

Model-free tracking. Our methods depend crucially on a new algorithm for LDS sequence prediction, at the heart of which is a new convex relaxation for the tracking formulation (Hazan et al., 2017) . In particular, this method circumvent the obstacle of explicit system identification. We detail our usage of this result in Definition 2.3.

We note an intriguing connection to the recently widespread use of deep neural networks to represent an unknown MDP in reinforcement learning: the main algorithm queries the unknown dynamical system with exploration signals, and uses its responses to build a compact representation (denoted by M in Algorithm 1) which estimates the behavior of the system.

Time-series analysis. One of the most common approaches to modeling dynamical systems is the autoregressive-moving average (ARMA) model and its derivatives in the time-series analysis literature (Hamilton, 1994; Box et al., 1994; Brockwell & Davis, 2009) . At the heart of this method is the autoregressive form of a time series, namely,

𝑥 𝑡 = 𝑘 𝑖=1 𝐴 𝑖 𝑥 𝑡-𝑖 + 𝜀 𝑡 .

Using online learning techniques, it is possible to completely identify an autoregressive model, even in the presence of adversarial noise (Anava et al., 2013) . This technique lies at the heart of a folklore regression method for optimal control, given in the second row of table 1 .

Optimal control. The most relevant and fundamental primitive from control theory, as applied to the control of linear dynamical systems, is the linear-quadratic-Gaussian (LQG) problem. In this setting, the system dynamics are assumed to be known, and the task is to find a sequence of inputs which minimize a given quadratic cost. A common solution, the LQG controller, is to combine Kalman filtering with a linear-quadratic regulator, a controller selected by solving the Bellman equation for the problem. Such an approach admits theoretical guarantees under varied assumptions on the system; see, for example, Dean et al. (2017) .

Our setting also involves a linear dynamical system with quadratic costs, and thus can be seen as a special case of the LQG setup, in which the process noise is zero, and the transition matrix is assumed to be symmetric. However, our results are not analogous: our task also includes learning the system's dynamics. As such, our main algorithm for control takes a very different approach than that of the standard LQR: rather than solving a recursive system of equations, we provide a formulation of control as a one-shot convex program.

2. STATEMENT OF MAIN THEOREM:

First, we state the formal definitions of the key objects of interest. Definition 2.1 (Dynamical system). A dynamical system D is a mapping that takes a sequence of input vectors 𝑥 1 , . . . , 𝑥 𝑇 ∈ B 2 = {𝑥 ∈ R 𝑛 : ‖𝑥‖ 2 ≤ 1} to a sequence of output vectors 𝑦 1 , . . . , 𝑦 𝑇 ∈ R 𝑚 and costs 𝑐 1 , . . . , 𝑐 𝑇 ∈ R. Denote 𝑥 𝑠:𝑡 = [𝑥 𝑠 ; . . . ; 𝑥 𝑡 ] as the concatenation of all input vectors from time 𝑠 to 𝑡, and write

D 𝑡 (𝑥 1:𝑡 ) = 𝑦 𝑡 , cost 𝑡 D (𝑥 1:𝑡 ) = 𝑐 𝑡 .

Definition 2.2 (Linear dynamical system). A linear dynamical system (LDS) is a dynamical system whose outputs and costs are defined by

ℎ 𝑡+1 = 𝐴ℎ 𝑡 + 𝐵𝑥 𝑡 , 𝑦 𝑡 = 𝐶ℎ 𝑡 + 𝐷𝑥 𝑡 + 𝜂 𝑡 with 𝜂 𝑡 ∼ 𝒩 (0, Σ), 𝑐 𝑡 = 𝑦 ⊤ 𝑡 𝑄𝑦 𝑡 + 𝑥 ⊤ 𝑡 𝑅𝑥 𝑡 ,

where ℎ 1 , . . . , ℎ 𝑇 ∈ R 𝑑 is a sequence of hidden states starting with fixed ℎ 1 , and 𝐴, 𝐵, 𝐶, 𝐷, 𝑄, 𝑅 are matrices (or vectors) of appropriate dimension. We assume ‖𝐴‖ op ≤ 1, i.e., all singular values of 𝐴 are at most one, and that 𝑄 0, 𝑅 0.

Our algorithm and its guarantees depend on the construction of a family of orthonormal vectors in R 𝑇 , which are interpreted as convolution filters on the input time series. We define the wave-filtering matrix below; for more details, see Section 3 of Hazan et al. (2017) . Definition 2.3 (Wave-filtering matrix). Fix any 𝑛, 𝑇 , and 1 ≤ 𝑘 ≤ 𝑇 . Let 𝜑 𝑗 be the eigenvector corresponding to the 𝑗-th largest eigenvalue of the Hankel matrix 𝑍 𝑇 ∈ R 𝑇 ×𝑇 , with entries

𝑍 𝑖𝑗 := 2 (𝑖+𝑗) 3 -(𝑖+𝑗)

. The wave-filtering matrix Φ ∈ R 𝑛𝑘×𝑛𝑇 is defined by 𝑘 vertically stacked block matrices {Φ (𝑗) ∈ R 𝑛×𝑛𝑇 }, defined by horizontally stacked multiples of the identity matrix:

Φ (𝑗) def = ï 𝜑 𝑗 (1) 𝐼 𝑛 𝜑 𝑗 (2) 𝐼 𝑛 . . . 𝜑 𝑗 (𝑇 ) 𝐼 𝑛 ò .

Then, letting 𝑡 range from 1 to 𝑇 , Φ𝑥 𝑡:𝑡-𝑇 then gives a dimension-wise convolution of the input time series by the filters {𝜑 𝑗 } of length 𝑇 . Theorem 3.3 uses a structural result from Hazan et al. (2017) , which guarantees the existence of a concise representation of D in the basis of these filters.

The main theorem we prove is the following.

Theorem 2.4 (Controlling an unknown LDS). Let D be a LDS with a symmetric transition matrix 𝐴 and with ‖𝐵‖ 𝐹 , ‖𝐶‖ 𝐹 , ‖𝐷‖ 𝐹 , ‖𝑄‖ op ≤ 𝜌, and with 𝑄 𝜆𝐼. For every 𝜀 > 0, Algorithm 1,

EQUATION

assuming that min

𝑥 1:𝑇 ∈ B 𝑇 2 ‖𝑥 1:𝑇 ‖ ≤ 𝐿 E 1 𝑇 𝑇 𝑡=1 cost 𝑡 D (𝑥 1:𝑡 ) ≤ Tr(𝑄Σ) + 𝑐 (3)

Further, the algorithm samples poly 1 𝜀 , log 1 𝛿 , log 𝑇, log 𝜌, 1 𝜆 , 𝐿, 𝑛, 𝑘, Tr(Σ) trajectories from the dynamical system, and runs in time polynomial in the same parameters. We remark on some of the conditions. 𝜆 is bounded away from 0 when we suffer loss in all directions of 𝑦 𝑡 . In condition (3), Tr(𝑄Σ) is inevitable loss due to background noise, so (3) is an assumption on the system's controllability.

We set up some notation for the algorithm. Let Φ ∈ R 𝑛𝑘×𝑛𝑇 be the wave-filtering matrix from Definition 2.3. Let 𝑥 𝑖 = 0 for 𝑖 ≤ 0, and let 𝑋 𝑡 = 𝑥 𝑡:𝑡-𝑇 +1 . Let 𝜌 = max(‖𝐵‖ 𝐹 , ‖𝐶‖ 𝐹 , ‖𝐷‖ 𝐹 , ‖𝑄‖ 𝐹 ) be an upper bound for the matrices involved in generating the outputs and costs.

3. PROOF OF MAIN THEOREM:

To prove Theorem 2.4, we invoke Lemma 3.1 and Lemma 3.2, proved in Subsection 3.1 and Subsection 3.2, respectively. Lemma 3.1 (Learning dynamics). For every 𝜀 > 0 and symmetric LDS D, with probability ≥ 1 -𝛿, setting 𝑘 = Ω(log 2 𝑇 log(𝑛𝜌/𝜀)) and 𝑆 = Ω 

EQUATION

)

Lemma 3.2 (Robustness of control to uncertainty in dynamics). Let x1:𝑇 = arg min

𝑥 1:𝑇 ∈ B 𝑇 2 ‖𝑥 1:𝑇 ‖ ≤ 𝐿 𝑇 𝑡=1 î D𝑡 (𝑥 1:𝑡 ) ⊤ 𝑄 D𝑡 (𝑥 1:𝑡 ) + 𝑥 𝑇 𝑡 𝑅𝑥 𝑡 ó ,

where M ∈ R 𝑚×𝑛𝑘 is such that for every sequence of input signals (𝑥 1 , . . . , 𝑥 𝑇 ) ∈ B 𝑇 2 with ‖𝑥 1:𝑇 ‖ 2 ≤ 𝐿 and 𝑡 ≤ 𝑇 , Equation (5) holds with ŷ𝑡 = D𝑡 (𝑥 1:𝑡 ). Assume (3). Then

EQUATION

Moreover, the minimization problem posed above is convex (for 𝑄, 𝑅 0), and can be solved to within 𝜀 opt acccuracy in poly(𝑇, 𝜌, 1/𝜀 opt ) time using the ellipsoid method.

Proof of Theorem 2.4. Use Lemma 3.1 with 𝜀 ← 𝑂 » 𝜆 𝑐 𝜀 𝜌 . Note that 𝑥 1:𝑇 = 𝜑 𝑗 is a valid input to the LDS because ‖𝜑 𝑗 ‖ 2 = 1. Now use Lemma 3.2 on the conclusion of Lemma 3.1.

3.1. LEARNING THE DYNAMICS:

To prove Lemma 3.1, we will use the following structural result from Hazan et al. (2017) restated to match the setting in consideration.

Theorem 3.3. Let D be a symmetric LDS with the stated conditions from Section 2, with fixed ℎ 1 . Let 𝜀 > 0, and let 𝑘 = Ω(log 2 𝑇 log(𝑛𝜌/𝜀)). Let 𝑧 1:𝑡 be the output if the input signal is 0. Let 𝑀 ′ be the matrix such that for all input-output pairs (𝑥 1:𝑇 , 𝑦 1:𝑇 ), E(𝑦 𝑇 -𝑧 𝑇 ) = 𝑀 ′ 𝑋 𝑇 . Then for all

EQUATION

Proof. This follows from Theorem 3b in Hazan et al. (2017) after noting four things.

1. E(𝑦 𝑡 -𝑧 𝑡 ) are the outputs when the system is started at ℎ 1 = 0 with inputs 𝑥 1:𝑡 and no noise. A linear relationship 𝑦 𝑡 -𝑧 𝑡 = 𝑀 ′ 𝑋 𝑡 holds by unfolding the recurrence relation.

2. Examining the construction of 𝑀 in the proof of Theorem 3b, the 𝑀 is exactly the projection of 𝑀 ′ onto the subspace defined by Φ. (Note we are using the fact that the rows of Φ are orthogonal.)

3. Theorem 3b is stated in terms of the quantity 𝐿 𝑦 , which is bounded by 𝜌 2 by Lemma F.5 in Hazan et al. (2017) .

4. We can modify the system so that 𝐷 = 𝑂 by replacing (𝐴, 𝐵, 𝐶, 𝐷) with (( 𝐴 𝑂 𝑂 𝑂 ) , ( 𝐵 𝐼 ) , (𝐶 𝐷), 𝑂). This replaces 𝜌 by 𝑂(max(𝜌, √ 𝑛)). Theorem 3b originally had dependence of 𝑦 𝑡 on both Φ𝑋 𝑡 and 𝑥 𝑡 , but if 𝐷 = 𝑂 then the dependence is only on Φ𝑋 𝑡 .

Proof of Lemma 3.1.

Take 𝑆 = Ω Å 𝐿 2 𝑛𝑘 Tr(Σ) ln( 𝑇 𝛿 ) 𝜀 2 ã

. Letting 𝑀 ′ be the matrix such that 𝑦 𝑡 -𝑧 𝑡 = 𝑀 ′ 𝑋 𝑡 , and 𝑀 = 𝑀 ′ Φ ⊤ as in Theorem 3.3, we have that

EQUATION

Let 1 ≤ 𝑡 ≤ 𝑇 . We bound the error under controls 𝑥 1:𝑡 ∈ B 𝑡 2 , ‖𝑥 1:𝑡 ‖ 2 ≤ 𝐿 using the triangle inequality. Letting 𝑦 1:𝑡 be the output under 𝑥 1:𝑡 ,

E[𝑦 𝑡 ] -𝑧 𝑡 -M Φ𝑋 𝑡 2 ≤ ‖E[𝑦 𝑡 -𝑧 𝑡 ] -𝑀 Φ𝑋 𝑡 ‖ 2 + ‖E[𝑧 𝑡 ] -𝑧 𝑡 ‖ 2 + 𝑀 Φ𝑋 𝑡 -M Φ𝑋 𝑡 2 .

(10) By Theorem 3.3, for 𝑘 = Ω(log 2 𝑇 log(𝑛𝜌/𝜀)), choosing constants appropriately, the first term is ≤ 𝜀 4 . To bound the second term in (10), we show 𝑧 𝑡 concentrates around E𝑧 𝑡 . We have

EQUATION

)

By concentration of sums of 𝜒 2 random variables (see Hsu et al. (2012) , for example),

EQUATION

)

Take 𝛿 ′ = 𝛿 2𝑇 and 𝜀 ′ = 𝜀 4𝐿 √ 𝑛𝑘 and note 𝑆 was chosen to satisfy (12). Use the union bound to get that

EQUATION

)

To bound the third term in (10), we first show that M concentrates around 𝑀 . We have

EQUATION

By 𝜒 2 concentration,

EQUATION

)

We also have

(E𝑧 𝑇 -𝑧 𝑇 )1 ⊤ 𝐹 ≤ √ 𝑛𝑘 ‖E𝑧 𝑇 -𝑧 𝑇 ‖ 2 .

With ≥ 1 -𝛿 probability, we avoid both the bad events in ( 13) and ( 18) so ‖𝑧

EQUATION

and for all ‖𝑥 1:𝑡 ‖ ≤ 𝐿, the third term of ( 10) is bounded by (note ‖Φ‖ op = 1 because it has orthogonal rows)

EQUATION

)

Thus by ( 10),

E[𝑦 𝑡 ] -𝑧 𝑡 -M Φ𝑋 𝑡 2 ≤ 𝜀 with probability ≥ 1 -𝛿.

3.2. ROBUSTNESS OF CONTROL TO UNCERTAINTY IN DYNAMICS:

To prove Lemma 3.2, we need the following helpful lemma. Lemma 3.4. For a symmetric LDS D with 𝜌 = max(‖𝐵‖ 𝐹 , ‖𝐶‖ 𝐹 , ‖𝐷‖ 𝐹 , ‖𝑃 ‖ op ) and 𝐴 𝐼, 𝑄 𝜆𝐼, and an approximation D𝑡 whose predictions ŷ𝑡 satisfy the conclusion of Lemma 3.1, we have that for every sequence of controls (𝑥 1 , . . . , 𝑥 𝑇 ) ∈ B 𝑇 2 , and for every 1

EQUATION

where cost 𝑡 D(𝑥 1:𝑡 ) = D𝑡 (𝑥 

:

CONCLUSIONWe have presented an algorithm for finding the optimal control inputs for an unknown symmetric linear dynamical system, which requires querying the system only a polylogarithmic number of times in the number of such inputs 𝑇 , while running in polynomial time. Deviating significantly from previous approaches, we circumvent the non-convex optimization problem of system identification by a new learned representation of the system. We see this as a first step towards provable, efficient methods for the traditionally non-convex realm of control and reinforcement learning.

Figures and Tables:

𝑛𝑘 Tr(Σ) ln( 𝑇 𝛿 ) 𝜀 2 ã , step 7 in Algorithm 1 computes a matrix M ∈ R 𝑚×𝑛𝑘 such that for every sequence of input signals (𝑥 1 , . . . , 𝑥 𝑇 ) ∈ B 𝑇 2 satisfying ‖𝑥 1:𝑇 ‖ 2 ≤ 𝐿 and 1 ≤ 𝑡 ≤ 𝑇 , we have that ‖ŷ 𝑡 -E𝑦 𝑡 ‖ ≤ 𝜀 (5) where ŷ𝑡 = M Φ𝑋 𝑡 + 𝑧 𝑡 and 𝑦 𝑡 = D 𝑡 𝑦 (𝑥 1:𝑡 ). (6) Algorithm 1: Control with an LDS oracle Input : Oracle access to LDS D, cost matrices 𝑄, 𝑅, filter parameter 𝑘, sample count 𝑆. Output: Control inputs x1:𝑇 . 1 Run D with the all-zeros input 𝑆 times, recording responses 𝑧(𝑠) 1:𝑇 := D 1:𝑇 (0) for each 1 ≤ 𝑠 ≤ 𝑆. 2 Average the zero-impulse responses: 𝑧 1:𝑇 := 1 . 3 for 1 ≤ 𝑗 ≤ 𝑛𝑘 do 4 Run D with input 𝜑 𝑗 𝑆 times, recording responses 𝑦 (𝑠,𝑗) 𝑇 := D 𝑇 (𝜑 𝑗 ) for each 1 ≤ 𝑠 ≤ 𝑆. Let M be the matrix whose 𝑗-th column is M𝑗 := 𝑦 (𝑗) 𝑇 -𝑧 𝑇 . 8 Solve the following convex program to obtain controls (x 1 , . . . x𝑇 ): x1:𝑇 := arg min

𝑇 ∈ B 𝑇 2 ‖𝑥 1:𝑇 ‖ ≤ 𝐿 E 𝑇 𝑡=1 D 𝑡 𝑐 (𝑥 1:𝑡 )(30)x1:𝑇 = arg min𝑥 1:𝑇 ∈ B 𝑇 2 ‖𝑥 1:𝑇 ‖ ≤ 𝐿 𝑇 𝑡=1 D𝑡 𝑐 (𝑥 1:𝑡 ) (31) Let 𝑉 = 𝑇 𝑡=1 [E[cost 𝑡 D (𝑥 * 1:𝑡 )] -Tr(𝑄Σ)],for inputs 𝑥 * 1:𝑡 . By assumption (3), 𝑉 ≤ 𝑐𝑇 . We have𝑉 ≥ 𝑇 𝑡=1 (E𝑦 𝑡 ) 𝑇 𝑄(E𝑦 𝑡 ) ≥ 𝜆 ‖E𝑦 1:𝑇 ‖2 𝑇 be the outputs under D under the control x1:𝑇 , note that similar to (32), x1:𝑡 is optimal for D. By Lemma 3.4 for inputs x1:𝑡 ,𝑇 𝑡=1 î cost 𝑡 D(x 1:𝑡 ) + Tr(𝑄Σ) -E[cost 𝑡 D (x 1:𝑡 )] ó ≤ 2𝜌𝜀 √ 𝑇 ‖ŷ 1:𝑇 ‖ + 𝑇 𝜌𝜀 2 . (36)Now by (34), (35), and (36),E[cost D (x 1:𝑡 )] -cost D (𝑥 * 1:𝑡 ) ≤ (cost D x1:𝑡 + Tr(𝑄Σ) -cost D(x 1:𝑡 ))(37) + (cost D(x 1:𝑡 ) -cost D(𝑥 * 1:𝑡 )) + (cost D(𝑥 * 1:𝑡 ) -Tr(𝑄Σ) -cost D (𝑥 * 1

Table 1 below compares the different methods, where we denote by |D| = max(‖𝐵‖ 𝐹 , ‖𝐶‖ 𝐹 , ‖𝐷‖ 𝐹 , ‖𝑄‖ op , 𝑚, 𝑛) the size of the system, and by 𝑇 the time horizon for planning. Comparison of control algorithms.

Table content: <table><tr><td>Method</td><td>Sample complexity</td><td>Time complexity</td><td/><td colspan="4">Assumptions</td></tr><tr><td>System Identification</td><td>poly(𝜖 -1 , |D|)</td><td>exponential</td><td/><td/><td colspan="2">none</td><td/></tr><tr><td>VARX(0, 𝑠)</td><td>poly(𝜖 -1 , |D|, 𝑠)</td><td>poly(𝑇, |D|)</td><td>𝑠 = Ω</td><td>Ä</td><td>1 1-‖𝐴‖2</td><td>ä</td><td>or 𝑠 = 𝑇</td></tr><tr><td>Ours</td><td>poly(𝜖 -1 , |D|, log 𝑇 )</td><td>poly(𝑇, |D|)</td><td/><td colspan="4">𝐴 symmetric</td></tr></table>

𝑄ŷ 𝑡 -E[𝑦 𝑡 ] ⊤ 𝑄E[𝑦 𝑡 ] (26) ≤ 2 ‖ŷ 𝑡 -E𝑦 𝑡 ‖ ‖𝑄‖ op min(‖ŷ 𝑡 ‖ , ‖E𝑦 𝑡 ‖) + ‖𝑄‖ op ‖ŷ 𝑡 -E𝑦 𝑡 ‖

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td>2</td><td>(27)</td></tr><tr><td>𝑇</td><td/><td/><td/><td/><td/><td/></tr><tr><td>î</td><td colspan="5">cost 𝑡 D(𝑥 1:𝑡 ) + Tr(𝑄Σ) -E cost 𝑡 D (𝑥 1:𝑡 )</td><td>ó</td><td>(28)</td></tr><tr><td>𝑡=1</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>Ã</td><td>𝑇</td><td/><td>𝑇</td><td/><td/></tr><tr><td colspan="2">≤ 2 ‖𝑄‖ op 𝜀</td><td>𝑇 min</td><td>‖ŷ 𝑡 ‖</td><td>2 ,</td><td>‖E𝑦 𝑇 ‖ 2</td><td>+ 𝑇 ‖𝑄‖ op 𝜀 2</td><td>(29)</td></tr><tr><td/><td/><td>𝑡=1</td><td/><td>𝑡=1</td><td/><td/></tr><tr><td>using Cauchy-Schwarz.</td><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="2">Proof of Lemma 3.2. Define</td><td/><td/><td/><td/><td/></tr><tr><td/><td colspan="3">𝑥 * 1:𝑇 = arg min</td><td/><td/><td/></tr></table>

Peer review (iclr2018):
 This paper studies the control of symmetric linear dynamical systems with unknown dynamics. Typically this problem is split into a (non-convex) system ID step followed by a derivation of an optimal controller, but there are few guarantees about this combined process. This manuscript formulates a convex program of optimal control without the separate system ID step, resulting in provably optimality guarantees and efficient algorithms (in terms of the sample complexity). The paper is generally pretty well written. This paper leans heavily on Hazan 2017 paper (https://arxiv.org/pdf/1711.00946.pdf). Where the Hazan paper concerns itself with the system id portion of the control problem, this paper seems to be the controls extension of that same approach. From what I can tell, Hazan*s paper introduces the idea of wave filtering (convolution of the input with eigenvectors of the Hankel matrix); the filtered output is then passed through another matrix that is being learned online (M). That matrix is then mapped back to system id (A,B,C,D). The most novel contribution of this ICLR paper seems to be equation (4), where the authors set up an optimization problem to solve for optimal inputs; much of that optimization set-up relies on Hazan*s work, though. However, the authors do prove their work, which increases the novelty. The novelty would be improved with clearer differentiation from the Hazan 2017 paper. My biggest concerns that dampen my enthusiasm are some assumptions that may not be realistic in most controls settings: - First, the most concerning assumption is that of a symmetric LDS matrix A (and Lyapunov stability). As far as I know, symmetric LDS models are not common in the controls community. From a couple of quick searches it seems like there are a few physics / chemistry applications where a symmetric A makes sense, but the authors don*t do a good enough job setting up the context here to make the results compelling. Without that context it*s hard to tell how broadly useful these results are. In Hazan*s paper they mention that the system id portion, at least, seems to work with non-symmetric, and even non-linear dynamical systems (bottom of page 3, Hazan 2017). Is there any way to extend the current results to non-symmetric systems? - Second, it appears that the proposed methods may rely on running the dynamical system several times before attempting to control it. Am I misunderstanding something? If so this seems like it may be a significant constraint that would shrink the application space and impact even further.