Linear-quadratic (LQ) control is one of the most widely studied problems in control theory (Anderson et al., 1972; Bertsekas, 1995; Zhou et al., 1996). It has been applied successfully to problems in statistics, econometrics, robotics, social science and physics. In recent years, it has also received much attention from the machine learning community, as increasingly difficult control problems have led to demand for data-driven control systems (Abbeel et al., 2007; Levine et al., 2016; Sheckells et al., 2017).

In LQ control, both the state and action are real-valued vectors. The dynamics of the environment are linear in the state and action, and are perturbed by Gaussian noise. The cost is quadratic in the state and control (action) vectors. The optimal control policy, which minimizes the cost, selects the control vector as a linear function of the state vector, and can be derived by solving the algebraic Ricatti equations.

The main focus of this work is control of linear systems whose quadratic costs vary in an unpredictable way. This problem may arise in settings such as building climate control in the presence of time-varying energy costs, due to energy auctions or unexpected demand fluctuations. To measure how well a control system adapts to time-varying costs, it is common to consider the notion of regret: the difference between the total cost of the controller, one that is only aware of previously observed costs, and that of the best fixed control policy in hindsight. This notion has been thoroughly studied in the context of online learning, and particularly in that of online convex optimization (Cesa-Bianchi & Lugosi, 2006; Hazan, 2016; Shalev-Shwartz, 2012). LQ control was considered in the context of regret by Abbasi-Yadkori et al. (2014), who give a learning algorithm for the problem of tracking an adversarially changing target in a system with noiseless linear dynamics.

In this paper we consider online learning with fixed, known, linear dynamics and adversarially chosen quadratic cost matrices. Our main results are two online algorithm that achieve regret, when comparing to any fast mixing linear policy.One of our online algorithms is based on Online Gradient Descent of Zinkevich (2003). The other is based on Follow the Lazy Leader of Kalai & Vempala (2005), a variant of Follow the Perturbed Leader with only expected number of policy switches.

Overall, our approach follows Even-Dar et al. (2009). We first show how to perform online learning in an “idealized setting”, a hypothetical setting in which the learner can immediately observe the steady-state cost of any chosen control policy. We proceed to bound the gap between the idealized costs and the actual costs.

Our technique is conceptually different to most learning problems: instead of predicting a policy and observing its steady-state cost, the learner predicts a steady-state distribution and derives from it a corresponding policy. Importantly, this view allows us to cast the idealized problem as a semidefinite program which minimizes the expected costs as a function of a steady state distribution (of both states and controls). As the problem is now convex, we apply OGD and FLL to the SDP and argue about fast-mixing properties of its feasible solutions.

For online gradient descent, we define a “sequential strong stability” property that couples consecutive control matrices, and show that it guarantees that the observed state distributions closely track those generated in the idealized setting. We then show that the sequence of policies generated by the online gradient descent algorithm satisfies this property. In Follow the Lazy Leader, following each switch our algorithm resets the system—a process that takes a constant number of rounds, after which the cost of playing the new policy is less than its steady-state cost.

The holy grail of reinforcement learning is controlling a dynamical stochastic system under uncertainty, and clearly both MDPs and LQ control are well within this mission statement. There are obvious differences between the two models: MDPs model discrete state and action dynamics while LQ control addresses continuous linear dynamics with a quadratic cost. In this work we are inspired by methodologies from online-MDP and regret minimization to derive new results for LQ control. We believe that exploring the interface between the two will be fruitful for both sides, and holds significant potential for future RL research agenda.

1.1 Related Work

LQ control can be seen as a continuous analogue of the discrete Markov Decision Process (MDP) model. As such, our results are conceptually similar to those of Even-Dar et al. (2009), who derive regret bounds for MDPs with known dynamics and changing rewards. However, our technical approach and the derivation of our algorithms are very different than those applicable in context of MDPs.

Among the many follow-up works to Even-Dar et al. (2009), let us note Yu et al. (2009) and Abbasi et al. (2013) that propose lazy algorithms similar to our second algorithm. We remark that, compared to our regret bounds, Abbasi-Yadkori et al. (2014) give an regret bound under much stronger assumptions.Similar bounds are established by Neu & Gómez (2017) for online learning in linearly solvable MDPs, that were shown to capture appropriately discretized versions of LQ control systems (Todorov, 2009). In light of these results, it is interesting to investigate whether our bounds are tight or can actually be improved. We leave this investigation for future work.

An orthogonal line of research that has gained popularity in recent years is controlling linear quadratic systems with unknown fixed dynamics. The majority of recent papers deal with off-policy learning: either by policy gradient (Fazel et al., 2018); by estimating the transition matrices (Dean et al., 2017); or by improper learning (Hazan et al., 2017; Arora et al., 2018). In contrast to that, Abbasi-Yadkori & Szepesvári (2011) and Ibrahimi et al. (2012) present an on-policy learning algorithm with

Semidefinite programming for LQ control has been previously used (Balakrishnan & Vandenberghe, 2003; Dvijotham et al., 2013; Lee & Hu, 2016), mostly in the context of infinite-horizon constrained LQRs (Lee & Khargonekar, 2007; Schildbach et al., 2015). In many of these formulations, one has to solve the SDP exactly to obtain a stabilizing solution; in other words, only the optimal policy is known to be stable and suboptimal policies need not be stabilizing. This is not the case in our SDP formulation, as any feasible solution is not only stable but, in fact, strongly-stable (see the formal definition in Section 3).

2.1 Linear Quadratic Control

The standard linear quadratic (Gaussian) control problem is as follows. Let be the system state at time t and let be the control (action) taken at time t. The system transitions to the next state using linear time-invariant dynamics

where are i.i.d. Gaussian noise vectors with zero mean and covariance . The cost incurred at each time point is a quadratic function of the state and control, , for positive definite matrices Q and R.

A policy is a mapping from the current state to a control (i.e., an action) . The cost of a policy after T time steps is

where are chosen according to ; the expectation is w.r.t. the randomness in the state transitions and (possibly) the policy. In the infinite-horizon version of the problem, the goal is to minimize the steady-state cost

In the infinite-horizon setting and when the system is controllable,it is well-known that the optimal policy is given by constant linear feedback . For the optimal K, the dynamics are given by is guaranteed to be stable; a policy K is called stable if where for a matrix is the spectral radius of M. In this case, converges to a steady-state (stationary) distribution, i.e., has the same distribution as . This implies that and the covariance matrix

The steady-state cost of a stable policy K with steady-state covariance X is given by J(K) = denotes element-wise inner product, i.e.,

2.2 Problem Setting

We consider an online setting, where a sequence of positive definite cost matrices is chosen by the environment ahead of time and unknown to the learner. We assume throughout that for all t, for some constant C > 0. We assume that the dynamics (A, B) are time-invariant and known, and that the system is initialized at . At each time step t, the learner observes the state , chooses an action , and suffers cost . Thereafter, the system transitions to the next state.

A (randomized) learning algorithm A is a mapping from and the previous cost matrices and to a distribution over a control . We define the cost of an algorithm as are chosen at random according to A.

The goal of the learner is to minimize the regret, defined as:

where is a set of benchmark policies. In the sequel, we fix to be the set of all strongly stable policies; we defer the formal definition of this class of policies to Section 3 below.

In this section we formalize the notion of a strongly stable policy and discuss some of its properties. Intuitively, a strongly stable policy is a policy that exhibits fast mixing and converges quickly to a steady-state distribution. Note that, while stable policies K (for which ) necessarily converge to a steady-state, nothing is guaranteed regarding their rate of convergence. The following definition helps remedy that.

Definition 3.1 (Strong Stability). A policy K is (for and ) if , and there exists matrices L and H such that , with and

Strong-stability is a quantitative version of stability, in the sense that any stable policy is strongly-stable for some and (See Lemma B.1 in the supplementary material). Conversely, strong-stability implies stability: if K is strongly-stable then A + BK is similar to a matrix L with , and so , i.e., K is stable. Notice that for a strongly stable K, although , it may not be the case that , and a non-trivial transformation be required to make the norm smaller than one (this is indeed the case with feasible solutions to our SDP relaxation).

Strong stability ensures exponentially fast convergence to steady-state, as is made precise in the next lemma.

Lemma 3.2. For all t = 1, 2, . . . let be the state covariance matrix on round t starting from some and following a ()-strongly stable policy . Then approaches a steady-state covariance matrix X, and further, for all t it holds that

This exponential convergence is true even if the policy is randomized and follows K in expectation; that is, if , and provided that

Proof. Let us first analyze deterministic policies. As noted above, we know that K is stable and as a result the state covariances approach a steady-state covariance X. By definition, we have

Subtracting the equations and recursing, we have which gives

For further bounding the right-hand side, observe that

Combining the inequalities gives the result for deterministic policies. For randomized policies with E[u|x] = Kx and finite V = Cov[u|x], the dynamics of the state covariance take the form

Since the analysis above only depends on the difference between the equations, the added term has no effect on the convergence of . Note, however, that the steady state X itself will be a function of V in general.

Let us state one more property of strongly stable policies that will be useful in our analysis.

Lemma 3.3. Assume that -strongly stable, and let X and U be the covariances of x and u at steady-state when following

3.1 Sequential strong stability

We next present a stronger notion of strong stability which plays a central role in our analysis. Roughly speaking, the goal is to argue about fast mixing when following a sequence of different policies (rather than a fixed policy K throughout). In this case, for any kind of mixing to take place, not only does one has to require that each policy is strongly stable, but also that the sequence is “slowly changing.” This motivates the following definition.

Definition 3.4 (sequential strong stability). A sequence of policies ) if there exist matrices for all t, with the following properties:

Strongly stable sequences mix quickly, in the following sense (proof is deferred to Appendix A).

Lemma 3.5. Let ) be a sequence of policies with respective steady-state covariance matrices , such that -strongly stable sequence and be the state covariance matrix on round t starting from some and following this sequence. Then

The same is true even if the policies are randomized, such that and is finite.

We now present our SDP relaxation for the infinite-horizon LQ control problem. Our presentation requires the following definitions. Consider an LQ control problem parameterized by matrices A, B, Q, R and W. For any stable policy (for which a steady-state distribution exists), define

where x is distributed according to the steady-state distribution of , and . Then, the infinite horizon cost of is given by . For a policy defined by a stable control matrix K (i.e., for which ), this matrix takes the form

where X is the state covariance at steady-state. (We slightly abuse notation and write E(K) instead of ). In this case, one also has

4.1 The relaxation

We can now present our SDP relaxation for the LQ control problem given by (A, B, Q, R, W), which takes the form:

Here, is a parameter whose value will be determined later, and matrix that decomposes to blocks as follows:

Lemma 4.1. For any stable policy such that at steady-state , the matrix is feasible for (3).

Proof. Let be any stable policy and consider the matrix . Then (by definition, recall Eq. (1)), and satisfies the equality constraint of (3), since if x is at steady-state and , then Ax + Bu + w has the same distribution as x for independent of x and u, thus the latter is equivalent to . Finally, observe that are distributed according to the steady-state distribution of satisfies the trace constraint.

4.2 Extracting a policy

We next show that from any feasible solution to the SDP, one can extract a stable policy with the same (if not better) cost, provided that . For any feasible solution for the SDP, define a control matrix as follows:

Note that, due to the equality constraint of the SDP, our assumption ensures that is nonsingular and is well defined.

be any feasible solution to the SDP, and let . Then the policy is stable, and it holds that . In particular, E(K) is also feasible for the SDP and its cost is at most that of

Without the trace constraint, the theorem particularly implies that for the optimal solution of the SDP, the corresponding control matrix is an optimal policy for the original problem, recovering a classic result in control theory.

Proof of Theorem 4.2. Our first step is to show that

To see this, observe that by definition of

Thus, it suffices to show that is PSD. The latter matrix is the Schur complement of and is PSD because

Next, we show that the control matrix K gives rise to a stable policy. Let us develop Eq. (3). First, since we also have that . Moreover, by Eq. (5),

Let be a (possibly complex) eigenvalue and left-eigenvector associated with A + BK. Then,

which, by . This is true for all eigenvalues , and shows that that is, K is stable.

Finally, let us show that , which together with Eq. (5) would imply our claim . Denote by X the state covariance at steady-state when following K; then,

To establish that it is enough to show . To this end, let

from which we get . Applying the latter inequality recursively, we obtain

Recall that ; thus, taking the limit as , we get which implies . This shows that , as required.

To complete the proof observe that E(K) is feasible for the SDP since and is feasible. Furthermore, since is PSD, we have

4.3 Strong stability of solutions

Let us show that from a solution to the SDP one can extract a strongly stable policy.

Lemma 4.3. Assume that and let . Then for any feasible solution for the SDP, the policy -strongly stable.

Proof. According to Theorem 4.2, the policy K is (weakly) stable and the matrix is feasible for the SDP. Let be the state covariance of K at steady-state. Since is feasible, and since

In particular, this means that . On the other hand, we have , thus . Overall,

Given that X is nonsingular, we can define . Multiplying Eq. (6) by both sides, we obtain Thus , so . Also, Eq. (7) shows that . It is left to establish the bound on the norm . To this end, use the fact that

together with (recall Eq. (7)) to obtain

We can also prove an analogous statement for sequences of feasible solutions, provided that they change slowly enough (we defer the proof to Appendix A).

Lemma 4.4. Assume that be a sequence of feasible solutions of (3), and suppose that for all t for some . Then the sequence , where -strongly stable.

In this section we describe our gradient based algorithm for online LQ control, presented in Algorithm 1. The algorithm maintains an “ideal” steady-state covariance matrix by performing online gradients steps directly on the SDP we formulated in Section 4 (with the linear cost functions changing from round to round). Then, a control matrix is extracted from the covariance and is used to generate a prediction.

Notice that the predictions made by the algorithm are randomly drawn from the Gaussian and only follow the extracted policies in expectation. This randomization step is crucial for the algorithm to exhibit fast mixing: sampling the prediction from a distribution with the right covariance ensures the observed covariance matrices converge to those generated by the algorithm, and consequently this sequence “mixes” more quickly.

For Algorithm 1 we prove the following guarantee.

Theorem 5.1. Assume that and . Given and , set and . The expected regret of Algorithm 1 compared to any -strongly stable control matrix

provided that

We remark that the theorem (in fact, Algorithm 1 itself) tacitly assumes that the SDP defined by S is feasible; otherwise, the set of strongly-stable policies is empty and the statement of Theorem 5.1 is vacuous.

Proof. Fix an arbitrary -strongly stable control matrix , and denote by be the covariances induced by using throughout. Also, let be the actual observed covariance matrices induced by the algorithm. Denoting the expected regret of the algorithm can be then written as follows:

Observe that the sequence generated by the algorithm is feasible for the (feasibility) SDP described by the set S. Thanks to Lemma 4.3, for any feasible the corresponding control matrix is -strongly stable, for and ; in particular, this applies to each of the matrices

We proceed by bounding each of the sums on the right-hand side of Eq. (8). We start with the second term and use a well-known regret bound for the Online Gradient Descent algorithm, due to Zinkevich (2003).

Additionally, the are slowly changing in the sense that, for all t,

We next bound the first term, now relying on Eq. (9) and the fact that the sequence of (randomized) policies chosen by Algorithm 1 is strongly stable.

, it holds that

Finally, the last term in Eq. (8) can be bounded using the strong stability of

-strongly stable

The theorem now follows by plugging in the bounds we established in Lemmas 5.2 to 5.4 into Eq. (8) and setting our choices of . (See Appendix A for details.)

In this section we present a different approach that is based on Follow the Lazy Leader of Kalai & Vempala (2005). In contrast to Algorithm 1, this approach does not require a lower bound on the noise but rather relies on occasionally performing resets, and needs a bound on the cost of this reset (this is established in Appendix C under reasonable assumptions). We assume access to an Oracle procedure that receives cost matrices Q, R, and parameter . It returns a control matrix K that minimizes the steady-state cost, subject to , where X is the steady-state covariance matrix associated with

Algorithm 2 is similar to Follow the Perturbed Leader, and in fact behaves the same in expectation. At every round t, Oracle is called using the sum of previously seen Qs and Rs plus an additional random noise, returns a matrix that is used to choose

For the measure , we use the joint measure over symmetric matrices Q and R, whose upper triangle is sampled coordinate-wise i.i.d from Laplace(). The "lazyness" of the algorithm stems from and being sampled dependently over time such that the cumulative perturbed loss only changes with small probability between rounds. Consequently, the expected number of switches of K as well as the expected number of resets are only

The reset step in the algorithm, informally, drives the system to zero at some cost. Here we assume that B has full column-rank in which case we can reset in one step. In Appendix C, we show how resetting can be done over a sequence of steps under much weaker assumptions.

Observation 6.1. Suppose that B has full column-rank. Resetting the system in round t can be done by setting , such that at the next round . Moreover, the expected cost of the reset is at most

For Algorithm 2 we will show the following regret bound.

Theorem 6.2. Assume that , and suppose that the cost of a reset is at most . Then for , the expected regret of Algorithm 2 against any -strongly-stable control matrix

satisfies

Remark 6.3. Oracle requires that the matrices Q and R are PSD. Nonetheless, we invoke Oracle using the perturbed cumulative loss that might not be PSD, as the perturbations and themselves are typically not PSD. To solve this issue, we first notice that with high-probability (Vershynin, 2010), we have and . Therefore, to guarantee that the perturbed cumulative loss is PSD, we can add an initial large pretend loss by setting and . This would contribute an term to the regret which ensures that, by our choice of , Theorem 6.2 still holds.

be the actual observed covariance matrices induced by Algorithm 2. Also, let be the covariances induced by using a fixed control matrix throughout. Similarly, define to be the covariance matrices of the steady-state distributions induced by respectively, and As in the analysis of OGD, the expected regret can be decomposed as follows:

The second term in Eq. (10), the regret in the “idealized setting”, is bounded due to Kalai & Vempala (2005). It requires the additional observation that, by Lemma 3.3, we have

Moreover, the probability that the algorithm changes and performs a reset at any step t is at most

The third term of Eq. (10) is bounded by due to Lemma 5.4. It remains to bound the first term in the equation. To that end, we will next show that after the system is reset, the cost of the learner on round t is at most that of the steady-state induced by

Figure 1: Data center cooling loop; see Section 7.

Lemma 6.5. Suppose the learner starts playing K at state . Then the expected cost of the learner is always less then the steady-state cost induced by K.

Proof. Let , and recall that . Let be the covariance of , and X be the covariance of x at the steady-state induced by We now show that for all by induction. Indeed, for the base case . Now assume that , that implies

Since is PSD, the expected cost of the learner at time t is

Combining Lemmas 6.4 and 6.5 obtains the theorem (see Appendix A for more details).

We demonstrate our approach on the problem of regulating conditions inside a data center (DC) server floor in the presence of time-varying power costs. We learn system dynamics from a real data center, but vary the costs and run algorithms in simulation.

Fig. 1 shows a schematic of the cooling loop of a typical data center. Water is cooled to sub-ambient temperatures in the chiller and evaporative cooling towers, and then sent to multiple air handling units (AHUs) on the server floor. Server racks are arranged into rows with alternating hot and cold aisles, such that all hot air exhausts face the hot aisle. The AHUs circulate air through the building; hot air is cooled through air-water heat exchange and blown into the cold aisle, and the resulting warm water is sent back to the chiller and cooling towers. The primary goal of floor-level cooling is to control the cold aisle temperatures (CATs) and differential air pressures (DPs). The control vector includes the blower speed and water valve command for each of n = 30 AHUs, set every 30s. The state vector includes 2n temperature measurements and n pressure measurements, as well as sensor measurements and controls for the preceding time step. System noise is in part due to variability in server loads and the temperature of the chilled water.

We learn a linear approximation (A, B) of the dynamics in the operating range of interest on 4h of exploratory data with controls following a random walk. We estimate the system noise covariance W as the empirical covariance of training data residuals. For the purpose of the experiment, we amplify the noise by a factor of 5. We set the diagonal coefficients of corresponding to the most recent (normalized) sensor measurements to 1 and remaining coefficients to 0, and keep constant throughout the experiment. We set diagonal coefficients of corresponding to water usage (valve command) to 1 throughout, and all coefficients corresponding to power usage (fan speed) to . We generate by (a) i.i.d sampling a uniform distribution on [0.1, 1], and (b) using a random walk restricted to [0.1, 1] taking steps of size with probabilities respectively.

Figure 2: Normalized regret for FLL and Recent strategies, with power costs generated uniformly (top) and by random walk (bottom). Resets occur at time steps indicated by dashed lines.

We run the FLL algorithm on this problem with the following modifications: we set , and , an upper bound on . Rather than executing hard resets to 0, we perform a soft reset by running a policy for n steps. Here is similar to the next FLL policy, but based on the 1.1 times the corresponding state cost Q.

We compare the cost of FLL to that of a fixed linear controller that is based on the average of the matrices, and to a Recent strategy which selects one of ten controllers corresponding to power costs in based on the most recently observed . The normalized regret of to the two strategies is shown in Fig. 2. FLL performance quickly approaches that of the fixed linear policy in both cases, and is better than the Recent strategy on uniform random costs. The Recent strategy has an advantage in the case where costs vary slowly, and empirical performance of FLL could likely be improved in this case by forgetting the old costs.

Abbasi, Y., Bartlett, P. L., Kanade, V., Seldin, Y., and Szepesvári, C. Online learning in markov decision processes with adversarially chosen transition probability distributions. In Advances in neural information processing systems, pp. 2508–2516, 2013.

Abbasi-Yadkori, Y. and Szepesvári, C. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 1–26, 2011.

Abbasi-Yadkori, Y., Bartlett, P., and Kanade, V. Tracking adversarial targets. In International Conference on Machine Learning, pp. 369–377, 2014.

Abbeel, P., Coates, A., Quigley, M., and Ng, A. Y. An application of reinforcement learning to aerobatic helicopter flight. In Advances in neural information processing systems, pp. 1–8, 2007.

Abeille, M. and Lazaric, A. Thompson sampling for linear-quadratic control problems. In AISTATS, 2017.

Anderson, B., Moore, J., and Molinari, B. Linear optimal control. IEEE Transactions on Systems, Man, and Cybernetics, (4):559–559, 1972.

Arora, S., Hazan, E., Lee, H., Singh, K., Zhang, C., and Zhang, Y. Towards provable control for unknown linear dynamical systems. International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id=BygpQlbA-. workshop track.

Åström, K. J. and Wittenmark, B. On self tuning regulators. Automatica, 9(2):185–199, 1973.

Auer, P. and Ortner, R. Logarithmic online regret bounds for undiscounted reinforcement learning. In Advances in Neural Information Processing Systems, pp. 49–56, 2007.

Balakrishnan, V. and Vandenberghe, L. Semidefinite programming duality and linear time-invariant systems. IEEE Transactions on Automatic Control, 48(1):30–41, 2003.

Bertsekas, D. P. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995.

Bittanti, S. and Campi, M. C. Adaptive control of linear time invariant systems: the bet on the best principle. Communications in Information & Systems, 6(4):299–320, 2006.

Bradtke, S. J. Reinforcement learning applied to linear quadratic regulation. In Advances in neural information processing systems, pp. 295–302, 1993.

Campi, M. C. and Kumar, P. Adaptive linear quadratic gaussian control: the cost-biased approach revisited. SIAM Journal on Control and Optimization, 36(6):1890–1907, 1998.

Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.

Dean, S., Mania, H., Matni, N., Recht, B., and Tu, S. On the sample complexity of the linear quadratic regulator. arXiv preprint arXiv:1710.01688, 2017.

Dvijotham, K., Todorov, E., and Fazel, M. Convex control design via covariance minimization. In Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on, pp. 93–99. IEEE, 2013.

Even-Dar, E., Kakade, S. M., and Mansour, Y. Online markov decision processes. Mathematics of Operations Research, 34(3):726–736, 2009.

Fazel, M., Ge, R., Kakade, S. M., and Mesbahi, M. Global convergence of policy gradient methods for linearized control problems. arXiv preprint arXiv:1801.05039, 2018.

Gao, J. and Jamidar, R. Machine learning applications for data center optimization. Google White Paper, 2014.

Hazan, E. Introduction to online convex optimization. , 2 (3-4):157–325, 2016.

Hazan, E., Singh, K., and Zhang, C. Learning linear dynamical systems via spectral filtering. In Advances in Neural Information Processing Systems, pp. 6705–6715, 2017.

Ibrahimi, M., Javanmard, A., and Roy, B. V. Efficient reinforcement learning for high dimensional linear quadratic systems. In Advances in Neural Information Processing Systems 25, pp. 2636–2644. Curran Associates, Inc., 2012.

Kalai, A. and Vempala, S. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291–307, 2005.

Lee, D.-H. and Hu, J. A semidefinite programming formulation of the lqr problem and its dual. 2016.

Lee, J.-W. and Khargonekar, P. P. Constrained infinite-horizon linear quadratic regulation of discrete-time systems. IEEE Transactions on Automatic Control, 52(10):1951–1958, 2007.

Levine, S., Finn, C., Darrell, T., and Abbeel, P. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334–1373, 2016.

Lewis, F. L. and Vrabie, D. Reinforcement learning and adaptive dynamic programming for feedback control. IEEE circuits and systems magazine, 9(3), 2009.

Neu, G. and Gómez, V. Fast rates for online learning in linearly solvable markov decision processes. Proceedings of Machine Learning Research vol, 65:1–22, 2017.

Schildbach, G., Goulart, P., and Morari, M. Linear controller design for chance constrained systems. Automatica, 51:278–284, 2015.

Shalev-Shwartz, S. Online learning and online convex optimization. Learning, 4(2):107–194, 2012.

Sheckells, M., Garimella, G., and Kobilarov, M. Robust policy search with applications to safe vehicle navigation. In Robotics and Automation (ICRA), 2017 IEEE International Conference on, pp. 2343– 2349. IEEE, 2017.

Todorov, E. Efficient computation of optimal actions. Proceedings of the national academy of sciences, 106(28):11478–11483, 2009.

Vershynin, R. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.

Yu, J. Y., Mannor, S., and Shimkin, N. Markov decision processes with arbitrary reward processes. Mathematics of Operations Research, 34(3):737–757, 2009.

Zhou, K., Doyle, J. C., Glover, K., et al. Robust and optimal control, volume 40. Prentice hall New Jersey, 1996.

Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 928–936, 2003.

A.1 Proof of Lemma 3.3

Proof. Strong stability ensures that

Write

As a result,

Further, notice that

A.2 Proof of Lemma 3.5

is the action taken on round t). By definition, for all t we have

Subtracting the equations, substituting and rearranging yields

Denote . Then the above can be rewritten as

Let us first analyze the simpler case where all policies converge to the same steady-state covariance X. Then , thus Eq. (11) reads

Taking norms, we obtain

whence . Recalling , we obtain

For the general case, taking norms in Eq. (11) results in

and unfolding the recursion we obtain

A.3 Proof of Lemma 4.4

(cf. Eq. (5)). Now, since is feasible for the SDP we have

Proceeding as in the proof of Lemma 4.3, one can show that , and that the matrix satisfies with and . To establish sequential strong stability it thus suffices to show that for all t. To this end, observe that

Hence, if as required.

A.4 Proof of Lemma 5.2

Proof. The diameter of the feasible domain of the SDP (with respect to ) is upper bounded by . Also, the linear loss function is Lipschitz for all t (again, with respect to ). Plugging this into the regret bound of the Online Gradient Descent algorithm gives the lemma.

A.5 Proof of Lemma 5.3

Proof. Denote the policy used by the algorithm on round t by with . Notice that

whence . Next, denote , and similarly , . Observe that

Further, for for any feasible

It is left to control the norms . To this end, recall Lemma 4.4 which asserts that the sequence -strongly stable, since we assume . Now, since , applying Lemma 3.5 to the sequence of randomized policies now yields

We can further bound the right-hand side using . Combining Eqs. (13) and (14) and using the fact that , we obtain the result.

A.6 Proof of Lemma 5.4

Thus . Now, Lemma 3.3 asserts that hence and by Eq. (12), it follows that

Now, an application of Lemma 3.2 gives

where in the ultimate inequality we have used again the fact that . Finally, we have Combining the inequalities gives the result.

A.7 Proof of Theorem 5.1

Proof. Plugging in the bounds we established in Lemmas 5.2 to 5.4 into Eq. (8) and setting the values for (and using to simplify), we obtain

for any such that . Thus, a choice of (for which it can be verified that ) gives the regret bound

Finally, plugging in gives the result.

A.8 Proof of Theorem 6.2

Proof. Since after a reset, the system starts at state 0, the cost of the learner is always less than the steady-state cost. The expected number of switches is at most , and whenever a switch occurs we pay an additional cost of for performing a reset. Combining that with our bounds on the three terms in Eq. (10), we get

In this section, we give additional justification for the stability assumption. The following lemma shows that for any stable controller K, there are finite bounds on its strong stability parameters.

Lemma B.1. Suppose that for a linear system defined by A, B, a policy K is stable. Then there are parameters for which it is -strongly stable.

Proof. A theorem of Lyapunov says that a matrix M is stable, i.e., its spectral radius is smaller than 1 if and only if there exists a positive definite matrix P such that

Indeed satisfies this condition. Let . Applying the above result to , we conclude that for some positive definite matrix P,

Pre- and post-multiplying by and rearranging,

Letting , we conclude that the condition number of , the claim follows.

In the following sections, we give quantitative bounds on the strong stability parameters of optimal policies K, under certain more graspable assumptions on the system.

B.1 Invertible B

As a warmup, we start with the setting when B is invertible. We will show quantitative bounds on the trace bound such that the optimal policy K will be feasible for the SDP. A quantitative bound on the strong stability parameters will then follow from Lemma 4.3

Lemma B.2. Assume that B is square and invertible, and

the SDP is feasible and the trace constraint is not binding.

Proof. Consider the control matrix

Then is PSD and, as , also satisfies

Further, we have

On the other hand, where we have used our assumption that Combining the two inequalities, we see that . Thus, we proved that is feasible.

Finally, to see that the constraint is not binding, consider the optimal solution SDP excluding this constraint (which is, of course, also feasible). Then, as before,

is therefore not binding.

B.2 Controllability

We now define general conditions on a linear system that allow us to prove quantitative bounds on the strong stability of the optimal solution. We first recall the notion of controllability of a system. A system defined by is said to be controllable if the matrix is full rank. A standard result in control theory says that one can drive any state to zero if and only if the system is controllable. We define a quantitative version of this condition.

-Strong Controllability). A system defined by controllable if the matrix

We first show that for a strongly controllable system, any state can be driven to zero at bounded cost.

Lemma B.4. Suppose that a dynamical system is -strongly controllable and that Q and R have spectral norm at most . Then there is a constant such that the system starting at a state can be driven to zero in k steps at cost at most . I.e. there exist a

Proof. Consider the following quadratic program:

Rewriting, this is equivalent to

By lemma B.6, the optimal solution is given by

For this setting of ’s, the corresponding

An easy calculation then shows that for this solution,

We now prove a generalization of Lemma B.2 in terms of the zeroing cost.

Theorem B.5 (Trace Bound). Suppose that matrices A and B are such that for any , the system can be driven to zero in k steps at cost for cost matrices Q = I, R = I. Consider the noisy system is feasible and the trace constraint is not binding.

Proof. By assumption, given , there is a sequence of actions and corresponding states such that . Consider the covariance matrices

From the fact that , it follows that

Further and we have

B.3 Solving Least Squares

The following is a standard fact about least squares regression; we give a proof for completeness.

Lemma B.6. Consider a QP: subject to Bx = c, where A is PD. Then the value of the optimal solution is

Proof. When minimizing any convex function over the constraint Bx = c, the gradient at the optimal solution is in the null space of B. Namely, there is some such that . Combining that with the constraint Bx = c, we can choose . Setting that into the objective function, we get the desired result.

Here we argue that under reasonable assumptions, the reset cost can be bounded. It will be useful to have some bound on the cost of driving a state to zero for a noiseless system. Lemma B.4 gives such a bound under the Strong Controllability assumption. We next give an alternate bound coming from the existence of a strongly stable policy.

Lemma C.1 (Zeroing using Strong Stability). Suppose that a linear system has a -strongly stable policy K. Then for , a start state can be driven to norm at most in steps at cost

Proof. Let K be a -strongly stable policy. We argue that playing K for approximately steps nearly zeroes the state; indeed at that point, the residual norm falls to belowso that the overall overhead coming from this residual is o(1). This is a consequence of the fact that for the noiseless model, the steady state X is zero. By Lemma 3.2

so that

Moreover the cost of this near-reset is at most

The following Theroem shows how resetting can be done in the general case using Lemma B.4, or Lemma C.1 to bound the cost of driving a state to zero. It follows that under either the assumption of strong controllability, or the existence of a strongly stable policy, we can derive a bound on the cost the reset step in FLL.

Theorem C.2 (Resetting). Consider the noisy system where . Suppose that

• The noiseless system starting from can be driven to zero in k steps at cost

• for some strategy K, the noisy system starting at state 0 has steady state cost and steady state covariance

Then, given initial state , there is a sequence of actions such that state and the cost of the the first k steps is at most

Proof. The idea is to use the linearity of the transition function, and split the sequence of k states into two sequences: one that starts at and the other at . We will play K on the sequence , and simultaneously drive the sequence be the set of actions that drive the noiseless system starting at to zero. At time t, we will play the control vector actual state of the system is . Thus we obtain and , and indeed

After k rounds we will have , and the system would be at state . A simple induction proof along the lines of Lemma 6.5 implies that . Finally, the sequences are statistically-independent and has mean-zero. As the cost is a quadratic function of the state, the total expected cost of the reset is the sum of the expected costs of the two sequences individually.