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 proposes a new algorithm to generate the optimal control inputs for unknown linear dynamical systems (LDS) with known system dimensions. The idea is exciting LDS by wave filter inputs and record the output and directly estimate the operator that maps the input to the output instead of estimating the hidden states. After obtaining this operator, this paper substitutes this operator to the optimal control problem and solve the optimal control problem to estimate the optimal control input, and show that the gap between the true optimal cost and the cost from applying estimated optimal control input is small with high probability. I think estimating the operator from the input to the output is interesting, instead of constructing (A, B, C, D) matrices, but this idea and all the techniques are from Hazan et. el., 2017. After estimating this operator, it is straightforward to use this to generate the estimated optimal control input. So I think the idea is OK, but not a breakthrough. Also I found the symmetric matrix assumption on A is quite limited. This limitation is from Hazan et. el., 2017, where the authors wants to predict the output. For prediction purposes, this restriction might be OK, but for control purposes, many interesting plants does not satisfy this assumption, even simple RL circuit. I agree with authors that this is an attempt to combine system identification with generating control inputs together, but I am not sure how to remove the restriction on A. Dean et. el., 2017 also pursued this direction by combining system identification with robust controller synthesis to handle estimation errors in the system matrices (A, B) in the state-feedback case (LQR), and I can see that Dean et. el. could be extended to handle observer-feedback case (LQG) without any restriction. Despite of this limitation I think the paper*s idea is OK and the result is worth to be published but not in the current form. The paper is not clearly written and there are several areas need to be improved. 1. System identification. Subspace identification (N4SID) won*t take exponential time. I recommend the authors to perform either proper literature review or cite one or two papers on the time complexity and their weakness. Also note that subspace identification can estimate (A, B, C, D) matrices which is great for control purposes especially for the infinite horizon LQR. 2. Clarification on the unit ball constraints. Optimal control inputs are restricted to be inside the unit ball and overall norm is bounded by L. Where is this restriction coming from? The standard LQG setup does not have this restriction. 3. Clarification on the assumption (3). Where is this assumption coming from? I can see that this makes the analysis go through but is this a reasonable assumption? Does most of system satisfy this constraint? Is there any? It*s ok not to provide the answer if it*s hard to analyze, but if that*s the case the paper should provide some numerical case studies to show this bound either holds or the gap is negligible in the toy example. 4. Proof of theorem 3.3. Theorem 3.3 is one of the key results in this paper, yet its proof is just "noted". The setup is slightly different from the original theorem in Hazan et. el., 2017 including the noise model, so I strongly recommend to include the original theorem in the appendix, and include the full proof in the appendix. 5. Proof of lemma 3.1. I found it*s hard to keep track of which one is inside the expectation. I recommend to follow the notation E[variable] the authors been using throughout the paper in the proof instead of dropping these brackets. 6. Minor typos In theorem 2.4, ||Q||_op is used for defining rho, but in the text ||Q||_F is used. I think ||Q||_op is right.