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):
 The paper presents a provable algorithm for controlling an unknown linear dynamical system (LDS). Given the recent interest in (deep) reinforcement learning (combined with the lack of theoretical guarantees in this space), this is a very timely problem to study. The authors provide a rigorous end-to-end analysis for the LDS setting, which is a mathematically clean yet highly non-trivial setup that has a long history in the controls field. The proposed approach leverages recent work that gives a novel parametrization of control problems in the LDS setting. After estimating the values of this parametrization, the authors formulate the problem of finding optimal control inputs as a large convex problem. The time and sample complexities of this approach are polynomial in all relevant parameters. The authors also highlight that their sample complexity depends only logarithmically on the time horizon T. The paper focuses on the theoretical results and does not present experiments (the polynomials are also not elaborated further). Overall, I think it is important to study control problems from a statistical perspective, and the LDS setting is a very natural target. Moreover, I find the proposed algorithmic approach interesting. However, I am not sure if the paper is a good fit for ICLR since it is purely theoretical in nature and has no experiments. I also have the following questions regarding the theoretical contributions: (A) The authors emphasize the logarithmic dependence on T. However, the bounds also depend polynomially on L, and as far as I can tell, L can be polynomial in T for certain systems if we want to achieve a good overall cost. It would be helpful if the authors could comment on the dependence between T and L. (B) Why does the bound in Theorem 2.4 become worse when there are some directions that do not contribute to the cost (the lambda dependence)? (C) Do the authors expect that it will be straightforward to remove the assumption that A is symmetric, or is this an inherent limitation of the approach? Moreover, I have the following comments: (1) Theorem 3.3 is currently not self-contained. It would enhance readability of the paper if the results were more self-contained. (It is obviously good to cite results from prior work, but then it would be more clear if the results are invoked as is without modifications.) (2) In Theorem 1.1, the notation is slightly unclear because B^T is only defined later. (3) In Section 1.2 (Tracking a known system): "given" instead of "give" (4) In Section 1.2 (Optimal control): "symmetric" instead of "symmetrics" (5) In Section 1.2 (Optimal control): the paper says "rather than solving a recursive system of equations, we provide a formulation of control as a one-shot convex program". Is this meant as a contrast to the work of Dean et al. (2017)? Their abstract also claims to utilize a convex programming formulation. (6) Below Definition 2.3: What is capital X? (7) In Definition 2.3: What does the parenthesis in .phi_j(1) denote? (8) Below Theorem 2.4: Why is Phi now nk x T instead of nk x nT as in Definition 2.3? (9) Lemma 3.2: Is .hat{D} defined in the paper? I assume that it involves .hat{M}, but it would be good to formally define this notation.