Safe Linear-Quadratic Dual Control with Almost Sure Performance Guarantee
Authors: Yiwen Lu
Yilin Mo
Venue: ICLR 2022 Submitted (2022)
Keywords: reinforcement learning

Abstract: This paper considers the linear-quadratic dual control problem where the system parameters need to be identified and the control objective needs to be optimized in the meantime. Contrary to existing works on data-driven linear-quadratic regulation, which typically provide error or regret bounds within a certain probability, we propose an online algorithm that guarantees the asymptotic optimality of the controller in the almost sure sense. Our dual control strategy consists of two parts: a switched controller with time-decaying exploration noise and Markov parameter inference based on the cross-correlation between the exploration noise and system output. Central to the almost sure performance guarantee is a safe switched control strategy that falls back to a known conservative but stable controller when the actual state deviates significantly from the target state. We prove that this switching strategy rules out any potential destabilizing controllers from being applied, while the performance gap between our switching strategy and the optimal linear state feedback is exponentially small. Under our dual control scheme, the parameter inference error scales as $O(T^{-1/4+\epsilon})$, while the suboptimality gap of control performance scales as $O(T^{-1/2+\epsilon})$, where $T$ is the number of time steps, and $\epsilon$ is an arbitrarily small positive number. Simulation results on an industrial process example are provided to illustrate the effectiveness of our proposed strategy.

Under review as a conference paper at ICLR 2022
Safe Linear-Quadratic Dual Control with Almost Sure Performance Guarantee
Anonymous authors Paper under double-blind review
ABSTRACT
This paper considers the linear-quadratic dual control problem where the system parameters need to be identified and the control objective needs to be optimized in the meantime. Contrary to existing works data-driven linear-quadrati regu- lation, which typically provide error or regret bounds within a certain probability, we propose online algorithm that guarantees the asymptotic optimality of the controller in the almost sure sense. Our dual control strategy consists of two parts: switched controller with time-decaying exploration noise and Markov parameter inference based on the cross-correlation between the exploration noise and system output. Central to the almost sure performance guarantee is a safe switched con- trol strategy that falls back to a known conservative but stable controller when the actual state deviates significantly from the target state. We prove that this switch- ing strategy rules out any potential destabilizing controllers from being applied, while the performance gap between our switching strategy and the optimal linear state feedback is exponentially small. Under our dual control scheme, the param- eter inference error scales as ((T-1/++e), while the suboptimality gap of control performance scales as ((T-1/2+*), where T is the number of time steps, and is an arbitrarily small positive number. Simulation results on an industrial process example are provided to illustrate the effectiveness of our proposed strategy.
INTRODUCTION
One of the most fundamental and well-studied problems in optimal control, Linear-Quadratic Reg- ulation (LQR) has recently aroused renewed interest in the context of data-driven control and rein- forcement learning. Considering it usually challenging obtain an exact system model from first principles, and that the system may slowly change over time due to various reasons, c.g., component wear-out, data-driven regulation of unknown linear systems has become an active research problem in the intersection of machine learning and control, with recent works including e.g., Dean et al. (2019); Mania al. (2019); Cohen et al. (2019); Wagemmaker & Jamieson (2020). In particular, from the perspective of reinforcement learning theory, the LQR problem has become standard benchmark for continuous control.
In this paper, we focus on the dual control (Feldbaum, 1 1960) setting, also known online adaptive control in the literature, where the same policy must be adopted to identify the system parameters and optimize the control objective. leading to the well-known suploration-ceploiiatioo dilemma. Recently, it was shown by Simchowitz & Foster (2020) that the optimal regret for this problem set- using a certainty equivalent
ting scales as é /T), which can be achieved with probability control strategy, where the learner selects control inputs according to the optimal controller for the current estimate of the system while injecting time-decaying exploration noise. However, the strat- egy proposed in this work, like those in its predecessors AAbbasi-Yadkon & Szepesvári, 2011; 1; Dean et al., 2018; Mania et al., 2019), may have a nonzero probability å of failing. Furthermore, it shall be noticed that ó has been chosen implies the probability of failing does not converge to zero even if the policy is run indefinitely. The above observation gives rise to the question that we address in this paper:
fixed design parameter in the aforementioned works, which
Can we design a learning scheme for LQR dual control, such that the policy adopted in almost every trajectory converges to the optimal policy?

---

Under review as a conference paper at ICLR 2022
We identify that the above goal can hardly be achieved by a naive certainty equivalent learning scheme. Qualitatively, the system parameters learned from data are always cortupted by random noise, and as a result, the controller proposed in previous works may destabilize the system, albeit with a small probability, causing catastrophic system failure. Based on the above reasoning, we propose notion of bounded-cost safety for the L.QR dual control problem: we recognize learning scheme to be safe if no destabilizing control policy is applied during the entire learning process.
In this paper, we propose learning scheme that satisfies the above definition of bounded-cost safety, and guarantees both the parameter inference error and the suboptimality gap of controller perfor- mance converge to zero almost surely. Our strategy consists of two parts: a safe switched controller and parameter inference algorithm. The switched controller can be viewed as a version of the certainty equivalent controller: it normally selects control inputs according to the optimal linear feedback for the currently estimated system parameters, but falls back to conser- vative controller for several steps when the actual state deviates significantly from the target state. We prove that this switching strategy ensures the bounded-cost safety of the learning process, while only inducing a suboptimality gap that decays exponentially as the switching threshold increases. For the parameter inference part, in contrast to the direct least-squares approach for estimating the matrices A, widely adopted in the literature, we estimate the Markov parameters, also known as the impulse response of the system, based on the cross-correlation between the exploration noise and the system output, and establish the almost-sure convergence using a law of large numbers for mar- tingales. We prefer this approach for its clarity physical meaning and simplicity of convergence analysis, but we do not foresee substantial difficulty in replacing our parameter inference module with standard least-squares. We prove that under the above described learning scheme, the parame- ter inference error scales as O(T-1/4+s), while the suboptimality gap of control performance scales as (TT-1/2+*), where T is the number of time steps, and is an arbitrarily small positive number. Both the above results match the corresponding asymptotic rates in Simchowitz & Foster (2020), which provides an rate-optimal algorithm for online LQR in the high-probability regime.
The main contributions of this paper are as follows:
1. We propose practical notion of safety for the LQR dual control problem that has not been considered in the literature, and provide an instance of safe learning scheme based on a switching strategy.
2. We prove almost sure convergence rates of parameter inference error and suboptimality gap of control performance for our scheme, which match the corresponding optimal rates in the high-probabilityy regime. To the best of our knowledge, this is the first analysis of the almost sure convergence rate for online LQR.
The rest of this paper is organized as follows: Section 2 gives a brief introduction of LQR, formulates the LQR dual control problem, and defines the performance metrics as well as the notion of bounded- cost safe learning scheme. Section 3 presents and interprets algorithm. Section 4 states the main theoretical results and characterizes the convergence rates. Section 5 provides simulation results on industrial process example illustrate the effectiveness of our proposed strategy. Section 6 summarizes the related literature. Finally, Section 7 gives concluding remarks and discusses future directions.
PROBLEM FORMULATION
We consider the control of the following discrete-time linear system:
Tk+1 -Ax + Bug + wks
(I)
where I& E Ra is the state vector, up E RP is the input vector, and wv E R" is the process noise. We assume To ~ N' (0, Xo) Wgg ~ N (0, W). and that zo Wps Wi.... are pairwise independent. We also assume w.l.o.g. that (A, B) is controllable.
We consider control policies of the form
Rd R + R9, (ue, Cx+1) = π (xx, Ex),
(2)
which can be either deterministic or stochastic, where & E IR9 is the internal state of the policy. Notice that allow the flexibility of the policy being non-Markovian with the introduction of &x.
2

---

Under review as a conference paper at ICLR 2022
and we also the simplified notation uy (2x)) if i is Markovian. The performance of policy t can be characterized by the
quadratic cost
J
= lim sup
E
ry QTy + u4 Rug
(3)
T-
T
k=
where Q > 0, R. 0 are known weight matrices specified by the system operator.
We denote the optimal cost and the optimal control law by
J inf J πT" E min π
(4)
is well-known that the optimal policy a linear function of the state (x) = x' with associ- ated cost J tr (WF (WP*). )*), where P is the solution to the discrete- time algebraic Riccati equation
x,
p = Q + A P'A B -1 A*
(5)
and the linear feedback control gain K* can be determined by
K (R+B B P*A.
Based on the definitions above, we can use - - to measure of the suboptimality gap a specific policy
1*
In the online LQR setting, the system and input matrices A, B are assumed unknown, and the learn- ing process can be viewed as deploying sequence of time-varying policies {TR} with the dual objectives of exploring the system parameters and stabilizing the system. To characterize the safety of learning process, we make the definitions below:
Definition 1. A policy π is destabilizing =
Definition 2. learning process applying policies { is bounded-cost safe, if is not desta- bilizing for any time i and for any realization of the noise process.
Notice that Definition 1 is generalization of the common notion of destabilizing linear feedback gain, i.e., (x) = K destabilizing when p(A + BK) 2 1, which is equivalent to J +00. Based on the notion of destabilizing policies, we propose the concept of bounded-cost safety in Definition 2, which requires that destabilizing policies, or policies with unbounded cost, are never applied. It should be pointed that bounded-cost safety does guarantee the stability of trajec- tories, but is an indicator of the reliability of a learning scheme.
We assume the system is open-loop strictly stable, i.c., p(A) stabilizing linear feedback gain Kg. then we can apply the dual control scheme on the pre-stabilized system (A + BK, B) instead of (A, B). Existence of such known stabilizing linear feedback gain a standard assumption in previous works on online LQR (Mania et al., 2019; Simchowitz & Foster, 2020), and relatively easy to establish through coarse system identification (Dean al., 2019; Faradonbeh al., 2018b) or adaptive stabilization methods (Faradonbeh et al., 201 Sa; 2019).
Indeed, if there is a known
ALGORITHM
The complete algorithm we propose for LQR dual control is presented in Algorithm The modules in the algorithm will be described later in this section.
3.1 SAFE CONTROL POLICY
This subsection describes the policy for determining the control input The first n + steps are a warm-up period where purely random inputs are injected. Afterwards, in each step, we inject exploitation term ä plus polynomial-decayine exploratory noise (A: + 1)-9 where the decay rate e (0, 1/2) is a constant. The exploitation term ū is a modified version of the certainty equivalent control input Kg and this modification, described in Algorithm 2, is crucial to the safety of the learning process, which will detail below.
3

---

Under review as a conference paper at ICLR 2022
Algorithm Safe LQR dual control
Input: State dimension input dimension exploratory noise decay rate 8
1: for 0, :.....". n + - do
2: Ex+1 4 0
3: Apply control input 4n + (k: + 1) A where So N (p)
4: for k = p, + p + .,...dd do
5: Observe the current state Zik
6: for 0, 0.1,...,,n + 1 do
7:
HRT K-T E
Σ 1=
Hn STr-1
8:
Reconstruct As. B& from Ha.u..... HE using Algorithm
9: Compute certainty equivalent feedback gain Kg by replacing A, B with As, By in (5).(6)
Determine policy Th (1)-) 7 Ku, 8), where is described by Algorithm 2
11:
(uR,5k++) 1k+1) < (T {x); record ūe <- ú, Ce x S, where ú, S are the corresponding vari-
ables generated when executing the policy
12:
Apply control input
Algorithm Safe policy E;
Input: Arguments: system state z, policy internal state E; Parameters: step ks linear feedback gain K, exploratory noise decay rate B
Output: Control input u and next policy internal state i.., i.e. (u. = (z, K,
1: if > 0 then
2:
+ 0,5' 5
3: else
4:
if' max [K],, ||0||] 2 log then
5:
+ 0,5' llog k|
6:
else
7:
ú Kx,
8: u
+ (k 1) Pg. where (~ (0,1)
In short, we stop injecting the exploitation input for [log k| + consecutive steps, if either the state norm || || or the norm the feedback gain || exceeds the threshold log k. Recall from (2) that use ε denote the internal state of the policy, and in Algorithm & is counter that records how many steps are left in the "non-action" period. Essentially, we utilize the innate stability of the system to prevent the state from exploding catastrophically. This "non-action" mechanism is critical feature of our control design, without which the controller learned from data may destabilize the system, albeit with small probability, causing system failure in practice and forbidding the establishment of almost sure performance guarantees in theory. We provide an ablation study of this "non-action" mechanism Section 5.
We choose both the switching threshold and the length of the "non-action" period to be time- growing. The enlarging threshold corresponds diminishing degree of conservativeness. which is essential for the policy performance to converge to the optimal performance. Meanwhile, the pro- longing "non-action" period rules out the potential oscillation of state caused by the frequent switch- ing of the controller (see Appendix B for an illustrative example of this oscillation phenomenon). In particular, it can be shown that the suboptimality gap incurred by the switching strategy scales (tt exp(-cM2) where M is the switching threshold, is the length of the "non-action" pe- riod, and e is a system-dependent constant (see Lemma in Appendix 1.1.2). With both M and t growing Oloo k), the contribution of our switching strategy to the overall suboptimality gap is merely (1).
4

---

Under review as a conference paper at ICLR 2022
3.2
PARAMETER INFERENCE
The Markov parameters of the system described in (1) are defined as
H, ATB, T= 1,......
The Markov parameter sequence } can be interpreted as the impulse response of the system. shall be noted that finite terms of the Markov parameter sequence would suffice to characterize the system, since higher-order Markov parameters can be represented as the linear combination of lower-order Markov parameters using the characteristic polynomial of A in combination with Cayley-Hamilton theorem. particular, our inference algorithm estimates the first n + + terms of the impulse response. We denote our estimate H, at step k by HR.7. whose expression specified in line 7 of Algorithm 1. Based on the cross-correlation between the current state æı and past exploratory noise input Sk-r-1+ we can produce an unbiased estimate H, at each step, and HA.- is a cumulative average of such unbiased estimates, whose almost-sure convergence to H, can be established through law of large numbers for martingales (see Appendix A.1.3).
Remark 1. From a computational perspective, line 7 of Algorithm can be decomposed enable efficient recursive updates. To see this, we can rearrange this expression as
k
HR. k T-
Σ (i - T)
Hr.
Σ 1
(1 (i-T)
k K-T
the weighted sum of cumulative averages, each of which can be updated with constant amount of computation in each step. Therefore, the time complexity of each iteration and the total memory consumption are constant.
From the inferred Markov parameters {Hk, 3"tp-1 reconstruct Aç. Bg by fitting the data obtained from several rollouts on the virtual system described by (H 1 yn+p-1 The procedure is detailed in Algorithm 3.
Algorithm 3 Restoring system and input matrices from Markov parameters
Input: Markov parameter estimate sequence Ho, #1...., Hutp-1, number of simulated trajecto- ries N
Output: System matrices estimate Á, /
0
Åo
0
1: Construct block Toeplitz matrix T <-
H1
Ho
Ha+r-11 intp-2 Hntr-3
2: Choose independent random input trajectories, each (n + long. denoted by u,
(1)
" (N)
i = 1........ ........ n + -
W
3: Stack the inputs vertically and compute states:
u
[uo u.... un+p-1], [x] X2: xx+pp =: X +- Tu
4: Stack the inputs and states horizontally to form the following matrices:
th
[uo u Un+p-1].
[ X2
X, Xn+pl.2t ph
10.NN
Xn+p-1]
5:
Compute estimate
[É A]
X [M,; x011
It can be shown the procedure described in Algorithm 3 restores the actual system and input matrices as long as the Markov parameter estimates are accurate:
Lemma 1. When H, = H, = B for all = 0, 0, 1, and the matrix
defined
X
in Algorithm 3 has full row rank, the result of Algorithm 3 satisfies Á A, B B.
5

---

Under review as a conference paper at ICLR 2022
4 X
24 X
Proof. When f1 = A B, we have X = AX + BU [B
A]
Since
has full row
[4h 1
24 X
rank, we have
I, and therefore [ A]
X1
[
A).
Remark Lemma guarantees the consistency of our controller, i.e., accurate Markov parameter estimates would generule an optimal exploitation input. The full-row-rand condition in Lemma I, naturally satisfied by randomly generated inpuis, guarantees that the impuls provide sufficient ex- citation reconstruct system matrices from impulse responses. For the of analysis, it is also legitimate to use fixed, rather than random u, 's for each time step of the outer loop of Algorithm 1, as long as the rank condition is satisfied.
MAIN RESULTS
The main theoretical properties of our proposed LQR dual control scheme are stated as follows:
Theorem 1. Assuming A is stable, the learning process described in Algorithm I is bounded-cost safe according to Definition 2.
Theorem 2. Assuming A is stable, and 0 < < < 1/2, for flr. computed in Algorithm 1, the following limit holds almost surely, i.e., with probability 1:
H H
lim 10000
0,
(8)
where 7 = 1/2 - 0, for any e and any T 0, I...., - -p-1.
Remark 3. Theorem states that our estimate of the Markov parameters converge at the order O (k- As corollary, our estimate of the system and input matrices A, B also converge at O (k- (see Appendix A.4). This convergence rate coincides with the one guaranteed by the more commonly used least-squares method, for which one can establish the convergence of esti- mates of A, B O (k-+t) using concentration bounds for martingale least past-squaaess (e.g.. Lemma E.I in Simchowitz & Foster (2020)). Therefore, our parameter inference algorithm based on cross- correlation can be viewed as a competitive alternative to the least- least-squares estimator. One feature of our cros-correllttin approach compared to the least-squares approach, however, is that the timation of Markov parameters can be easily extended to the partially observable LQR setting like the considered in Zheng et al. (2020). Also, the convergence of our cross cross-corres cooss-coreelatin approach not based on the sub- Gaussianity of the process noise (see Appendix A.3), which allows straight- tailed noise models.
forward generalization to long-tailed
stable, and 0 < B < 1/2, let Ta be the control policy used at step k in Algorithm 1, then with J and J" defined in (3), (4) respectively, for any > 0, the following limit holds almost surely, ie., with probubility 1:
Theorem 3. Assuming
J J
lim 10000 k- (2,277
where y = 1/2- 3 3> 0.
Due to space limits, all the proofs are deferred to the appendix.
Remark 4. According Theorem 2, the convergence rate 7 is maximized when + 0+,, How- ever, the exploration term k does not decay in this case, and the control performance J will not converge to the optimal performance J To achieve the fastest convergence of Jes, we need to choose the decay rate of the exploration term to be B = 1/4, which maximizes min 27) = min(2 23)). When = 1/4, we have both parameter estimation errors and policy suboptimality gaps scaling at ((1/VT)) which matches the asymptotic rates of correspond- ing components in the wwith-hiigh-robbbiii
regret-optinal algorithm proposed in Simchowitz & Foster (2020). However, due to the challenging nature of the analysis of the nonlinear closed-loop system under safe control scheme, the exact regret of our scheme is still under investigation.

---

Under review as a conference paper at ICLR 2022
5 SIMULATION
In this section, the performance of our proposed algorithm is evaluated using Tennessee Eastman Process (TEP), an industrial process example for benchmarking linear controllers (Ricker, 1993). We used simplified version of TEP from Liu al. (2020), where the state and input dimensions are 8. p 4, and the spectral radius of the system matrix is p(A) 0.96. We assume Q, R. are identity matrices, and W, Xo are also identity matrices, i.e., the process noise i.i.d. standard Gaussian. We choose N 50 (in Algorithm 3) for all the experiments. In the practical implementation, the estimated system matrices Ag, B3 and the feedback gain K₂ updated only at steps [ N) to speed up the computation.
To illustrate the impact of the parameter / on the convergence of the algorithm, we perform 100 independent experiments for each of 3 E {0, 1/4, 1/2), with 10t steps in each experiment. Fig.
shows the error of the estimated system and input matrices, i.e., the time for different values of/
| - A and Bx - B against
10
10
10'
10-1
10-1
10-4
10
10
10
10"
10
10
10
10
10
10-
10
10'
10"
10
10
10
10
10
Figure 1: Error of estimated system matrices for different /3 against time k. The solid lines are the median among the experiments, and the shades represent the range among the experiments.
From Fig. 1, one can when 3 is 0 or 1/4, the estimation error of the system matrices converges to zero as time k goes to infinity, and the convergence approximately follows power law. Furthermore, the convergence speed of the estimation error is significantly faster when $ 0. Meanwhile, when = 1/2, the estimate error diverges in some of the experiments. The above observations are consistent with the theoretical result in Theorem 2, where it is stated that the parameter estimates converge with rate O (k=*+)), with = 1/2 B, i.e., convergence is only guaranteed with 3 < 1/2 and is faster when is smaller.
Now we consider the performance of policies with different values of B. To quantify the policy performance, one shall in theory compute T defined in (3). However, the policies Ti nonlinear, rendering it very difficult, if not impossible, to compute J analytically. As a surrogate approach for evaluating policy Th, we define the empirical cost j as
N T
j
1 NT E=1
Qui (2) + +(11)))
Rud
==
where 2 24 are states and inputs collected from the closed-loop system under in N indepen- dent To-ong sample paths indexed by In our simulations, we take T = 10000, N 10 to evaluate each stabilizing policy, which yields consistent results in practice. Fig. 2 shows the empirical per- formance of controllers with different values of 3 against time k.
From Fig. 2, one can observe that among our choices of B, only 3 = 10 1/4 drives the controller toward the optimal one. For = O, although the parameter estimates converge the fastest as discussed above, the performance of the resulting closed-loop system is even worse than the free system. This because the exploration term (k + 1)-"(c in the control input does not decay, and the resulting controller is noisy one. Meanwhile, for 3 1/2, diverging parameter estimates would lead ill- performing controllers. The observations are consistent with the theoretical conclusion indicated by Theorem 3 that B = 1/4 corresponds the optimal trade-off between exploration and exploitation.

---

Under review as a conference paper at ICLR 2022
1022
1020
20-4
10
3014
Figure 2: The empirical performance of controllers for different 3 against time k. For each policy Tke the empirical cost 7 is obtained by approximating the actual cost with random sampling from the closed-loop system. The solid lines are the median among the experiments, and the shades represent the interval between the first and third quantiles among the experiments. The purple and brown dashed lines represent the analytical optimal cost, and the analytical cost of the control-free system, respectively.
Finally, we compare algorithm with the naive centainty equivalence algorithm, which applies us = =K at each step. We invoke both algorithms with the "optimal" parameter 1/4, and perform 20 independent experiments for each algorithm. We consider the system parameter estimation error and the policy suboptimality gap for each algorithm, The results of this comparison experiment are presented in Fig. 3. In a proportion of the experiments (actually out of 20), certainty equivalence causes the estimation error and the policy suboptimality gap to diverge, while our algorithm ensures convergence in each experiment. Although existing works (e.g. Simchowitz Foster (2020)) contain methods for decreasing the failure probability with warm-up period for estimation, it should be noted that the failure probability is always nonzero as long as linear feedback policy with learned gain is deployed. Even compared to the case where the certainty equivalence algorithm converges, error and significantly better policy performance, which indicates that the conservativeness caused by our switching mechanism does not harm the long-tern term performance.
did in Fig. 1 and Fig. 2.
algorithm still delivers slightly lower estimation
[4-4]
077
17
12
10
12
10
10
10
100
12
10
12
12
100
12
107
30
16
Figure 3: Comparison between proposed algorithm (Safe) and the certainty equivalence algo- rithm (CF), in terms estimation error and policy performance. In a proportion of the experiments, CE causes the estimation error and the policy suboptimality gap diverge, while our algorithm ensures convergence in each experiment.
6 RELATED WORKS
The concept of dual control was initiated by Feldbaum (1960), and since then sustained research ef- forts have been devoted to learning to make decisions unknown environments. Classical literature on adaptive control, e.g., Áström & Wittenmark (1973); Lai & Wei (1986); Guo & Chen (1988); Guo (1996), have addressed the dual control of linear systems described by the ARMAX model with the objective of tracking reference signal. This objective do not consider the cost of exerting control input and is less involved than the LQR setting. For the rest of this section, we restrict our focus the LQR of unknown linear systems described by the state-space model.
8

---

The problem of designing controllers that improve over time has been studied in the context of on- line LQR and regret analysis. The online LQR setting was initially proposed by Abbasi- Abbasi-Yadkori & Szepesvári (2011), and since then, Optimism in the Face of Uncertainty (OFU), Thompson Sam- pling (TS) and E-greedy exploration have been applied to solve the online LQR problem. Abbasi- Yadkori & Szepesvári (2011) applied OFU principle to prove theoretical Õ(VT) regret upper bound, but their method is computationally intractable. Cohen et al. (2019) proposed tractable al- gorithm for OFU based on semidefinite programming to realize Ö(VT) regret. TS has been shown to achieve (VT) (frequentist) regret for scalar system (Abeille & Lazaric, 2018), and (VTT) ex- pected regret in a Beyesian setting (Ouyang et al., 2017). Recently, Faradonbeh et al. (2020a) and Mania et al. (2019) prove that randomized Certainty Equivalent (CE) control with e-greedy explo- ration can also achieve Ö(VT) regret, and Simchowitz & Foster (2020) prove that ((VT) regret is indeed the fundamental limit for the general online LQR setting. Under further assumptions, e.g., partially known system parameters, logarithm regret bound may be achieved (Cassel et al., 2020). The aforementioned results and the fundamental limit hold either with high probability or in ex- pectation, and lack almost sure guarantee. Faradonbeh et al. (2020b) prove that Õ(VT) regret for both TS and CE and hold almost surely, but under the restrictive assumption that the closed-loop Under review as a conference paper at ICLR 2022
In the offline learning regime, system identification and controller synthesis based on the estimated system are performed in separate stages. The study of linear system identification has been devel- oped for decades, with classical asymptotic guarantees summarized in Ljung (1999), and there has been a recent interest in non-asymptotic system identification based on a finite-size dataset. One can generate the dataset either by injecting random inputs to the system (Oymak & Ozay, 2019; Zheng & Li, 2020), or using active learning techniques to achieve optimal system-dependent finite-time rate (Wagenmaker & Jamieson, 2020). For a summary of recent results on non-asymptotic linear system identification, please refer to Zheng & Li (2020).
A natural step following system identification result and analyze the resulting closed-loop system's 's performance. The Coarse-ID control frame- work (Dean et al., 2019) adopts robust control techniques to derive controllers taking identification error into account, resulting in high-probability bounds on the control performance suboptimality gap. This framework has been applied to LQR (Dean et al., 2019). SISO system with output feed- back (Boczar et al., 2018), and LQG (Zheng et al., 2020). As an alternative approach, the certainty equivalence framework synthesizes the controller by treating the identified system as the truth (Ma- nia et al., 2019; Tsiamis et al., 2020), which is shown to achieve a faster convergence rate of control performance, at the cost of higher sensitivity to poorly estimated system parameters. At the intersec- tion of the above two methods, an optimistic robust framework was proposed achieve combina- tion of fast convergence rate and robustness (Umenherger & Schön, 2020). It should be pointed out the offline algorithms in the above works and the online setting we consider in the present work are not mutually exclusive but complementary to each other: online algorithms can continually refine the controller obtained by offline methods without interrupting normal system operation.
synthesize a controller based on the identification
system remains stable when the policy is being employed. Our work attempts to fill in the gap by performing an almost sure analysis for online LQQ without assumptions on the system other than the existence known initial stabilizer.
7 CONCLUSION
In this paper, we propose a safe LQR dual control scheme based on a switching, which guarantees almost sure convergence to zero of both parameter inference error and suboptimality gap of control performance. The convergence rate of inference enror is (144t)) while that of the suboptimal- ity gap is ( both of which match the known optimal rates proved in the non-asymptotic setting. For future works, we plan to extend the notion of regret to our almost-sure convergence setting, and formally establish the fundamental limits for this setting. It would also be interest- ing to investigate the exact convergence rates, especially dimension dependence, of our parameter inference scheme and the standard least-squares procedure.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Yasin Abbasi- Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pp. I- 26. JMLR Workshop and Conference Proceedings, 2011.
Mare Abeille and Alessandro Lazaric. Improved regret bounds for thompson sampling in linear quadratic control problems. In International Conference on Machine Learning, pp. 1-9, PMLR, 2018.
Karl Johan Áström and Björn Wittemmark. On self tuning regulators. Automatica, 9(2):185-199 1973.
Ross Boczar, Nikolai Matni, and Benjamin Recht. Finite-data performance guarantees for the Seeuut-fedbbac control of unknown system. In 2018 IEEE Conference Decision and Con- trol (CDC), pp. 2994-2999 IEEE, 2018.
Asaf Cassel, Alon Cohen, and Tomer Koren. Logarithmic regret for learning linear quadratic reg- ulators efficiently. International Conference on Machine Learning, pp. 1328-1337. PMLR, 2020.
Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only vT regret. In International Conference on Machine Learning, pp. 1300-1309, PMLR, 2019.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. arXiv preprint 17X.v:8805.09388 2018.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample com- plexity of the linear quadratic regulator. Foundations of Computational Mathematics, pp. 1-47, 2019.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Finite-time adap- tive stabilization of linear systems. IEEE Transactions on Automatic Control, 64(8):3498-33) 3505, 2018a 8a.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Finite time identifi- cation unstable linear systems. Automatica, 96:342-553 13432-33,,00 2018b.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Randomized al- gorithms for data-driven stabilization stochastic linear systems. In 2019 IEEE Data Science Workshop (DSW), pp. 170-174. IEEE, 2019.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Input perturbations for adaptive control and learning. Automatica, 1 117:108950, 2020a.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. On adaptive linear- quadratic regulators. Automatica, 107:2, 2020b.
AA Feldbaum. Dual control theory. i. Avtomatika i ('elemekhanika, 21(9): 1960.
Guo and HF Chen. Convergence rate of els based adaptive tracker. Syst. Sci & Math. Sci, 1: 131-138, 1988.
Lei Guo. Self-convergence of weighted least-squares with applications to stochastic adaptive con- trol. IEEE transactions on automatic control, 41(1):79-89, 1996.
Tze Lai and Ching-Zong Wei. Extended least squares and their applications adaptive control and prediction in linear systems. IEEE Transactions on Automatic Control, 31(10):898-906 1986.
Hanxiao Liu, Yilin Mo, Jiagi Yan, Lihua Xie, and Karl H. Johansson. An online approach to physical watermark design. IEEE Transactions on Automatic Control, (5()) -3002 Sep 2020. ISSN 0018-9286, 1558-2523, 2334-3303, doi: 10.1 109/TAAC.222.29711999.
10

---

Under review as a conference paper at ICLR 2022
Lennart Ljung. System identification. Wiley encyclopedia of electrical and electronics engineering, pp. 1-19, 1999.
Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. arXiv preprint arXiv:1902.07820 2019.
Yi Ouyang, Mukul Gagrani, and Rahul Jain. Learning- control of unknown linear systems with thompson sampling. arXiv preprint arXiv: 2017.
Samet Oymak and Necmiye Ozay. Non-asymptotic identification of Iti systems from single trajec- tory. In 2019 American control conference (ACC), pp. 5655-5661. IEEE, 2019.
Lawrence Ricker. Model predictive control of continuous, nonlinear, two-phase reactor. Journal of Process Control, 10): 1993.
Max Simchowitz and Dylan Foster. Naive exploration optimal for online lqr. In International Conference on Machine Learning, pp. 8937-8948 PMLR, 2020.
Anastasios Tsiamis, Nikolai Matni, and George Pappas. Sample complexity of kalman filtering for unknown systems. In Learning for Dynamics and Control, pp. 435-444. PMLR, 2020.
Jack Umenberger and Thomas B Schön. Optimistic robust linear quadratic dual control. Learning for Dynamics and Control, pp. 550-560. PMLR, 2020.
Andrew Wagenmaker and Kevin Jamieson. Active learning for identification of linear dynamical systems. In Conference on Learning Theory, pp. 3487-3582. PMLR, 2020.
Yang Zheng and Na Li. Non-asympiotic identification of linear dynamical systems using multiple trajectories. IEEE Control Systems Letters, 5(5): 693-1698, 2020.
Yang Zheng, Luca Furieri, Maryam Kamgarpour, and Na Li. Sample complexity lag control for output feedback systems. arXiv preprint arXiv:201 I. 09999, 2020.
11

---

Under review as a conference paper at ICLR 2022
A PROOF OF MAIN RESULTS
A.1 PRELIMINARIES FOR PROOFS
A.1.1 NOTATIONS
We will the following notations throughout the proofs:
Notation
Definition
XT
transpose of matrix X
|| |x|||
norm matrix X or vector 2, 2-norm by default
|X
Frobenius norm of matrix X
tx()
trace of matrix X spectral radius of matrix X matrix X positive definite for matrix X, X.Y. minimum eigenvalue of matrix
p(X)
X >
X-Y
- X
Amin(A) (X)
x(X)
ratio between maximum and minimum eigenvalues for ma- trix X 0, i.e., x(X) ||x|]] (X)in(X)
vec(X)
vectorization matrix X
X @ Y
Kronecker product of matrices X and Y
1s
indicator function of set S
f(z) ~ O(g(z))
there exists M > 0, such that [f(k)] S M x g(k) for all
k E N
f(x) (gg(z))
there exists M > and n E N, such that [f())] s M x g(k) log(k))* nM for all & E N
In addition, we define the following short-hand notation for characterizing the almost-sure asymp- totic convergence or growth rate of random processes: for a random variable (vector, or matrix) sequence }. we denote that Iy ~ C(a) if for all >> 0 and almost all realizations of randomness, have 2y O (ka+t), i.e., lim || /ho+t a.s. 0. The following lemma establishes some basic properties of C(a) functions:
Lemma 2. Assume Ik, yk random variable (vector, matrix) sequences with proper dimen- sions, then the following properties hold:
1. Df ~ C(a), 8k ~ C(3), then Ik + yk ~ C (max(a,
2. If my. ~ ~((a), yk ~ C(B). then Dalk ~ C(a + 3).
3. If f is a functio differentiable at and By ~ C(a), a < 0, then ff (Ix) - f(0) ~ C(a).
Proof. The first two claims follow trivially from the definition of C(a). For the third claim, notice
that for all realizations of randomness, lim || 0. Therefore, Taylor expansion of f (xx
at x = gives f**x f() = D0) + O[| where Df is the Fréchet derivative f. Dividing both sides by t leads the conclusion.
A.1.2 PROPERTIES OF A CLASS OF SWITCHED LINEAR SYSTEMS
We state and prove some properties of class of switched linear systems that will be useful for the proof of all the main theorems of this paper.
Consider the dynamical system
Ek+1 AgTE Wks
(10)
12

---

Under review as a conference paper at ICLR 2022
where k4, wk RR",0 E V (0, W-1), (0, wy N (0, Wx), zu. fwy Tookk are pairwise indepen- dent, and Ag, We are functions of To:k and k. We assume
We - 0, || As S of W - W Vk.
(11)
We first prove a few miscellaneous lemmas that will be useful shortly:
Lemma 3. Let X ~ (p), then P(X 2 M) - 2n/ (/4) for any M > 0.
Proof. Applying the Chernoff bound, we have
p/2 exp( P(X 2 M) E f /e (1 21) 2/?
for any 0 1 < 1/2. Choosing = 1/4 leads to the conclusion.
Lemma 4. Let w E IR, ~ N (0, W), W > 0, then P([[w]] 2 M) S 2D/2 exp
-M <|[T
Proof. Let W-1/2w, then N (0, and hence ||u||2 xp).. From | = w 1
TWe S ||=ll [[]]] we have P[[[W]] 2 M) P[[]w]] 2 M²) S P([|o)] M² [[]]).
Applying Lemma 3 leads to the conclusion.
Lemma 5. Let
1/2 and 1 < 2, then En=o xa 22/(a-11 1).
Proof. By > 1, we have a -1 (1+a- 11- n(aa 1). Therefore, in view of < < < 1,
we have
(a-1)r
x
xa-1
n=0
7=0
n=0
In view of the inequality (1+t)* < ++t 2 1, < S 1, we have 0- (1+x-1)0-1
1 + (a 1)(x - 1), and therefore,
2x
<
x
(a
1)(1 x)
when 0 < x $ 1/2, and the conclusion follows.
Now we state several properties of the system described in (10)-(11):
Lemma 6. For the system described in (10)-(11), assuming there exists 0 < p < 1 and P > 0 such
that AT PAg 4 pP for every As. then when M 2 /3W k(P)/(1 - p21/),, there is
2n/2+1
(1 (1- (1-p2/4y222)
P [[| 2 M) < 1-112-1 exp
Vk.
4W<K(P)
Proof. From (10), we have
Ik = A 1T-1 + Wk-1
Ap-1 10 (As (Ak-221 2 + wk-2) Wk-1
Wk-1 1
1 Aw + Ak-1Ax-2-- A0xo
Pre-multiplying by p1/2 on both sides and applying the triangle inequality, we have
pll/2zu| pl/ + pl/2 A Aa-wwe-ph we-
+
p1/2 A
A Alwo|
(12)
13

---

Under review as a conference paper at ICLR 2022
From AI pP, we have for any w E RR, k N,
w T PA < prc Pw |1/2 Awwel < p//2 p2/2
(13)
Applying (13) to (12) recursively, we have
| $ 11/22/ + p1/2 p1/2wx + +... p( po/2 + ////2 11//
(14)
Meanwhile, we have
[||0*|| 2 M) =
p- p-1/2 1-112p1/2 p1/2211/ xk 2 M)]
S 5|||-111 1/2 22
2 MM)
1
p2/2
2 M
Amin
= =111p1/2211 xx6 2 MM Mv Amin (P)
Therefore, for any a E (pt/22 1), in view of (14), we have
[||Iж|| 2 M} _ { pl/22x こ M (mmaaa(P))
5 p1/2rx rx
2 M Aminn (P)(1- - o
5 p1/2
+ p2/2
w 2| + ....t + pl 11/2 p2/2210 wol + pk/2 p2/22000 2
M / Amin (P) -otti)}
S
|||| 11/2
2 (1 J)M
Amain [P) U p2/2 p2/2 wk
2 (0)1-o)Me v Aunin (P)
... ...u of (plt-1) 1)/2
p1 p1/2 wo/ 2 10- - x Amnin(P) u
{ fo//2 pl/220||
> o# -o)M v Amin(())
Taking the union bound, we have
F( 2 M) <P
p1/2
2 (1 (o) Amin (P)) +
IP
w
2
(1 o)M v Amain (P) +
12/2
4-1
IP
11/2w0
ww
7
(1 -1-63 --o)MM v /mmin(P) +
p1/2
k
IP
>
σ
(1- Amin (P)
Since p1/2wx 1 rosk ~ N (0. p1/2 p1/2), and ||alll
< W. applying Lemma 4, we have
(1 - o) 2 (P)
P (1p1)/00 2 (1-o))M / Amii (P) To.k)
s 2m exp
4 ||
11-0)²M²
221 exp
(15)
4W ro(P)
Noticing that the RHS of (15) does not depend on Tock, have
(1 (1-0)²M2
p 01111/2 wok 2 (1- O0)M V Amii (P)) 2n/² exp
4W
14

---

Under review as a conference paper at ICLR 2022
Similarly, we have
(1
(-a-0ppf.
( - ..)
P
p 1lpl//wx-x
w/
(1- -o)M Ammu((P)) S exp
p2/²
k-1
(1- -)--2)2222 (02 R-1
P
p wo
p1/2
2
0
(1 (o- V Amin(P)
S eex
p2/²
4W k(P)
b
(1-o)aM² 022 h 4W x(P)
P
|
(1 o)M Amin(()
S exp
p1l2
Choose p!/4, then o² /pp p 1/2, --1122 Assuming w.l.ogg that p E (1/4, 1), we have o² 0²/p
1-1 E (1, When M 2 /3W x(P)/(1 - p11/), there is
(11-0)²M²) 4W k(P) (-WW<<P)
3
1
2n exp
< exp
< -.
2
Applying Lemma 5 leads to the conclusion.
Lemma 7. For the system described in (10)-(11), assume there exists p < 1, 0 and M such that A P + pP as long as ||=x||| 2 M. Let Vv- = 2x Pet, then
(M2 cd
|PI
EV <
4k.
1
Proof. We first derive recursive bound on EVg: from (10), we have
VK+1 x
2/_ Ag PA + 2w PA + W Pun.
(16)
When || < M. we have 2, A PALI S of ||II. Otherwise, by A PA x pP, we
have 2g A/ PALIK- < par PTx = pVz. Therefore, in view of the fact that M of || 2 0 and
pV: 2 0. we have
1 A PA S max (M of2 |P||| PV&& 2 0) S M |||| + pVk.
(17)
which holds for any k. Substituting (17) into (16), we have
Vx+1 S pVn 7 CC,
(18)
where Tp 2 PALTA + we Puk, C= 2 cf 2 ||||] With such defined 7kk we have
En - W ||P||
(19)
where we noticed that B[ PA = [[ P PA [o:A]] E[ wwy xo AuTx] and
that EE Pww] = [E[E[[, Pwn xo:s]] BBttr P)] S / |||| Taking the expectation on both sides of (18), we have
EV S PEV& + (M2 od2 + w/ P||
(20)
We can proceed using induction: we have
EV = Pxro]= = B[tr(W- < W P|| (M2 + W) |PP|
1-p
(f PI] it follows from (20) that EV441 I-p
(f2 + which con- 1-p
Assuming EV;
cludes our proof.
Lemma 8. For the system described in (10)-(11), assume that there exists 0 < < 1,P > 0 and
M 0 such that A PAs < pP as long as || 2 M, and that A only depends on || Let
V₂ = x PIt, then
(M2 of + W ||PI|
EVZ <
(1 (1 p²) [(1 (M +w 4d Vk.
15

---

Under review as a conference paper at ICLR 2022
Proof. From the inequality (18) in the proof of Lemma 7, we have
EV EV + E + C² + 2 [Venn + 2pC + 2CTBAR
(21)
where The 2 PAAT + w Pwk: C = of ||||- Let us bound Eyy. EV2. En (V which appear in the RHS of (21) respectively:
Eme S w || from (19) in the proof of Lemma 7.
EV < (C + w (1 p) according to the conclusion of Lemma 7.
En 2 A Puxwi R PALTR] + 4B[wg PARTAUE Pwn] + E(w Pww., Pwal S
4E ||xx|] of W/ |PI|2 + w ||P|| where we noticed Elwy P Pwi]
E PA Pwn
xı]]
tr [IE[Aaa) Puraw P mxl]] 0 due to
symmetry, From V = Ik
T PIę 2 Xmin (P) |== we can further deduce Emj. S
W ||P))N()EVE, + W |PPI?
E[VanTol [E[E(G Pwr W P| V.V.
2 & PA Vwl + V Pwul = 2 PA Vo
xæll + sR]]
rR]]] 2R[E|ux mx) PAA. V&] + [[ Pick
S
Substituting the above terms into the RHS of (21), we have
EV < DEVVV + (Lof |P|| K< + 2p(C + * (PII)) C C+W |P|
1-p +
C² + 2CW |||| + W 1|
C+ + / |P||
= P +
[(1+ PC + W [P]) + [P||
(22)
1
We can then proceed using induction: we have
EVV < w P|| ( [PI)(W (PI))
C W |P||| (C+ W (PI)
1-
C + W |P||| [(1 p) + W (PI)) + 4. [P]]]
(1 (1 - -P
Assuming EV2
<
(I-P)[-pT) () + */ (PI)) + 20/2// ||| k()], we also have
C+WIPI
EV++1
C+
[11 (CC + W (P]) + 4407W |P]| [(P) by (22). Therefore, we have
[I-MXI-P*)
C' W |||||
EV4 <
[(1+)] + W (Pl) + /0 |P| [(P]]
(1- (1 12)
(f2 2 + W) |P||
[(1 (M of 4
(1 (1-p)(1 p)(1 - p2)
for any k.
A linear dynamical system (1) driven by our safe switching policy can be viewed as an instance of the system described in (10)-(11). Formally, we consider the following system:
Fk+1 Ar + Buy + Wks
(23)
We consider the following two classes of policies:
Linear feedback policy: us = kk (xx) KIR-
Safe switching policy: (ux, Ex+1) = / *K,,.'(Z,, Ex). where M > O the switching thresh- old and t No is the "non-action" duration, and म K.M.t determines uy, Ex+1 as follows:
If &x 0, then uy 0, E 1;
16

---

Under review as a conference paper at ICLR 2022
If EA 0, max [|| || 2 M, then uy 0, 0,
1;
If Ek O, max | M, then uy Ke Ex+1 0.
Notably, the linear feedback policy can be viewed as a special case of the safe switching policy where the switching threshold is infinity, i.e., x = #k,00011,
For the simplicity of expressions, when a safe switching policy Kee,lut is applied at each step k let us define the following notations:
(0) = 0, ik + + = ikk) +
(((k) 7 0 [i(k) + (()) (4(k) 0
Ix [((())-
(24)
In plain words, {0x} { J is the subsequence of { where "non-action" steps are skipped. In addition, let
* = lim W + AWA + +... AAW(
(25)
which is finite value since A is stable.
Lemma 9. For the system described in (23)-(25), assume safe switching policy n Me, is applied at each step Ms S M for any ki and there exists < p < 1 and P > such that A PA + pP, then
E| < ((M P)
W ((P))))
where
(f2 + W/ ||P1?
(M, p. P)
[(1 + (M of2 + W) + 4 W W k(P)),
(1- p)(1 - p²)
d ||||| M.
Proof. According to (23) and (24), the state trajectory {0x} evolves subject to the dynamics
Ās+1 = Auăx + Wk.
(26)
where
(A
max[]| M
Ag A + BK₃
otherwise
W
max [| || 1|=x111] otherwise
M
4x &x N (0, Wh). We
( AWA" AT +... + (A
Let V82 N Pxx and V/ PT.. Since TA x pP, the system (26) satisfies the assumption of Lemma 8, and || < W Aull & |A|l B M d. Therefore, and therefore,
EVZ < (M 2 + */ |P||
[(1 + PMM + W 1 A k()) 2(M, p, P)Amiu (P)2.
(1 p) )²)
(27)
Next, establish the relationship between EV? and EV? notice that
T4 A 1--00) J Wk.
(28)
where j = ss N | i(s) < k}, i.c. ž, is the last state in { that physically occurs no later
than Tg, and WH = - -ー - ( +ts Since A is stable, we have [B [I] < W.
Pre-mus fre-multiplying both sides of (28) with p1/2 and applying the triangle inequality, we have
|1/2 xx s |11/2/1/ // k- 100 31) + |||11//
17

---

Under review as a conference paper at ICLR 2022
Therefore, applying the power means inequality ( a'4b", 2. we have
Vi = p1/2222
<8
(00 11 +
+ *+1p21220011)
83 (1) PAR-(()3s)) ) + (1o Putu))
= 8
8 (2 + (w Pūx))
Taking the expectation on both sides of the above inequality and applying (27), we get
EV < 8 [2MM P)Amin (P)² + w [|11"]
Finally, using the fact that V - PIk Amin (P) |xx we have
EV?
E |
S
Amin A 5 P)
which concludes our proof.
Lemma 10. For the system described in (23)-(25). assume K is stabilizing linear feedback (i.e., P(A + BK) < 1) gain with ||]]|| S M, and there exists < < and P such that P(A+ BK) x pP. Let J be the cost (defined in (3)) associated with the linear feedback policy π K and JMH be the cost associated with the safe switching policy म K.M.A.
A PA x (A+ BK) (A
Then
MM -M--J- 1 1
where
1/2
C().P.)) W Wr(P) Q+ + K RK
1-p
G(M,,, K) - C2(e, (2(, p, P)
W HH--W3KWPPT ((P))) E(M, P);
2n/247/4
(ep,)) = 11Q + KK +KTRKK] |BK]|
[[(+BB))*)
p-1/2-1
==0
(C2 K) < 00 because p(A + BK) < 1),
(f2 + W) ||P1|
Q(M. p. P) (1 - p)(1 - p²)
[(1 (M +
(1 111/44422M2
E(M,p, = exp
4WK((P)
In particular, if the system specification A, B, Q R, W, the stabilizing linear feedback gain K, and the parameters p, P are all fixed, we have
JM J ~ O (LM exp(-cM²))
(1-p"/a92
as M + 00, 0o, LM expeeeppfc - 0, where = [.K(P]
Proof. Let {I+}, } denote the state and input trajectories driven by T and {Tx}. {ūg denote the state and input trajectories driven by # RR,,,t, Then from n (x) Kr and *K.M. (x) (Kx, 0}, we have
J lim -00
L (Q + K
RK)
lim T-
x (Q + K RK)aa].
T
T
km 0
T-1
MM < sup E
x (Q + K RK)
lim limsup
T
T
00000
T T-
k=D
k=0
18

---

Under review as a conference paper at ICLR 2022
Therefore, only need to prove
+Q+ K E E (Q + K RK) - E K RK)aN] &
PC P. + P,K)²
for every k. Let Q Q+ + KTRK, Since Q and R > O, have Q
0. and therefore
|| & V Qu defines a norm. the follows, we bound E ||alll |1
We notice that
f = (A+ + BK) + Wk-1 1 (
=(A+ + BK) [(A + BK) 3 wk-2 B BK ( -
BK (a=-1=0)
k-1
(A+ BK) & xp + Σ (A+ BK) (kK)wk-s-1 Σ BK) -- (at-
1
= TK
( A + BKY BK 17.
Hence,
k-1 1
| - |ق*1| +
Σ
1-
==0
k-1
$ 1omد1| + |00
|BK]]
[( + BK) -|a-1 1 (an wll- Σ a=0
From the fact that [X(1, + x,)² < (VEX +...+ V EX where X1...., Xn are arbitrary random variables with bounded second-order moments, have
1 3 S (V |os l2 + +||0|1BBK Σ
1-1
2
IIA I(A+BK)) BKY y [ 11 188---1-00)
By Cauchy-Schwand inequality, we have
2 (11---1-0) = 0)) T + 1|| BK] [[(A + BK) (B1)) p
S
By Lemma 9, we have E 1i 1| < 8[Q(M, p. + x xPP()) for any 8, and hence,
E 1 s
(V BBBl + 1
k-1
[IA+ BK) P = 00 Σ
(29)
According to the update rule of & # K,M, we have
[ 0} C
[| 2 M).
T=0
Taking the union bound, we have
IP (ū. 0) <
P ([ P1 2 M).
T=0
19

---

Under review as a conference paper at ICLR 2022
By Lemma 6, we have
2n/2+1
P [( -ll 2 M) <
1/2 EM P)
for every & and t, and hence
2n/2+1 P (īg 0) St
P 1/2 E(M, p. P)
(30)
for every k. Substituting (30) into (29), we get
2n/2+7/4
1 -
(VEllenll
|
|B
p-1 1Q(M. P) + (2
k-1
Σ
IIAA BKYII(MM.).)
(VElleM BIN
E 1 P.(M,,,.PKK))
E | + P.
Applying Lemma 7 with M O, we have
W P|
Ei2g P <
1 1-p p
and hence
#x(P) 11Q1 P,)P,
E
|
l3 - O
|x
1-p
Therefore,
E
T 13
E. Jar 12 S P.K G(M.,,)
and hence
MM J 111.
which concludes our proof.
A.1.3 A LAW OF LARGE NUMBERS FOR MARTINGALES
Let {Fi} be filtration of alalgebras and (S²) } be matrix-valued stochastic process adapted to
{Fx). ). we call } a matrix-valued martingale (with respect to the filtration {F&}) if E|S
Fr] Sy holds for all k. Now we state a law of large numbers for matrix-valued martingales:
Lemma 11. (Liu et al., 2020, Lemma 4) If St 40 + $
+ Dy is a matrix-valued martingale
such that
E +
C(3).
where 0 05 3 < 1, then Se/k converges 0 almost surely. Furthermore,
Sk ~ C
(
[ (3-1)
k
2
20

---

Under review as a conference paper at ICLR 2022
1.1.4 A PERTURBATION ANALYSIS OF ALGEBRAIC RICCATI EQUATION
An interesting property of LQR is that near the optimal controller (which corresponds the solu- tion of the discrete algebraic Riccati equation), the perturbation of the discrete Lyapunov equation solution quadratic the perturbation of controller gain. Basically, this results the convergence speed of the certainty equivalent control performance being twice that of the estimation error. Sim- ilar results have been reported in (Mania et al., 2019; Simchowitz Foster, 2020), and here we present simplified version that would suffice for our purpose.
Lemma 12. Consider the discrete Lyapunov equation
A XA- - X = where Q > and p(A) < 1, then the unique positive definite solution X satisfies
| [ (1-
A & ( | 1Q
Proof. Vectorizing the Lyapunov equation, we get
vec(.X) (I A
@ A -1 vec(Q),
and hence
|X|| ||vec(X)]l $ (1-A" A 2 AT) |/ecl()]l2 = - 111 A 19
Lemma 13. Let P be the solution to the discrete algebraic Riccati equation
P= Q PA-
AB PB R B B PA
and let be defined as
K= -R- PA.
Assume K is such that À + BK is stable, and P satisfies the discrete Lyapunov equation
p= RT RĀ + PAP
(31)
Let AP = P.AK- = K, then
|AP|| s (1- (T)
AT) -1 | |
Proof. It can be shown satisfies the discrete Lyapunov equation
P Q=QKK* RK + (A + BK) P(A + BK). Meanwhile, substituting AP P P. AK K K into (31), we get
(32)
P AP
= Q + (K (K+ R(K + AK) + (A + B B(K + AK)) (P AP) (A B K + AK))
Q + KT RK + AKTRAK RAK + (A+ + BK) P(A + BK) + ÄTAPÁ
(33)
where for the second equality we used the fact
(R+ B PB) K BT PAA 0.
By taking the difference between (33) and (32), we can see AP also satisfies a discrete Lyapunov equation:
AP T APAPA
Applying Lemma 12, we obtain
||P|| F x
[ AT @ )A''
-1
AK ReTRAK]|
1 (I-A A 8 A )
|R|| JAKI
<
which concludes proof.
21

---

Under review as a conference paper at ICLR 2022
A.2 PROOF OF THEOREM 1
Proof. According to our definition of bounded-cost safety, we only need to prove J < too for every where J is defined in (3).
Let (ax), {ui denote the state and input trajectories driven by Th- According to Algorithm 2, we have E (K 0}, and therefore,
T
T < sup E 7'000 T
Σ 1=0
(o x
K2 RKA)
= lim sup T-200
Σ 1=0
E x4
(Q+
RRs ma)
T
Notice that under there is 2141 = Ar + as long as |xy|| > log k. and since A is stable, there exists p 1 and P > 0 such that A PA < pll. By Lemma 7, we have
(llg of ed 1-p BR 11.. Therefore, by x. Px, x; 2 ||Q + K2 RK ||==:1² we have (Q+ ( RKa)
[[W]]) ||
E r
Pa.]
where of max a 11A
Amia (P) |a;11 and
( K RKx) zi1 ((log (logh))2000 + [ KJ RKIll 1
E
P
This implies
(log k)? || (I))ll)) Rg RKell +00,
J
which concludes our proof.
A.3 PROOF OF THEOREM 2
Proof. We shall assume throughout the proof that (Fi) the o-algebra generated by the random variables (To, wo, ......, Wk: .o..... }+
We first cast the system (1) into static form by writing F as
k-1
26
A B0
+
A' A'Bu- 1
A A'wa-t-1
k-1
k-1 +
A a 20
+
He [ + (I- - Ce-e-1]
A w
(34)
t=0
t=0
In order to estimate H,, post-multiply both sides of (34) with -T and rearrange the terms, and we get
A-1
5 C
A' --1 1-1 + A Sh--1 Σ
(k
1)-
1=0
Hoūh-t-1
(35)
To take the expectation of (35), notice that for any time step k. the variables Po. Co, G1,... Gk. Wo, W,...., Wh: ūo, uj,..., ux+1 are measurable w.r.t. Fs. which, together with the independence among To, Co, Si...., (R, wo, W....., Wk. leads the following relations:
if kj ka
E Sk. Ska
Fka- -1
(36)
0
otherwise,
0 other values
if if < K2 otherwise,
E
iiki
Skz
T
F F 2]
(37)
E
[Kin Skz
= O, F
(38)
E
T
F
0.
(39)
22

---

Under review as a conference paper at ICLR 2022
for any two time steps A 2 0 and l2 2 1. Now let us prove the conclusion using induction on T.
First consider the case 0: have
1 k K
Hs.0 Ho
Σ + () Ho] Σ [ 2) x
Ho]
(40)
Let 42 + x Hp. By substituting (35) and (36) to (39) into (40) it can be seen 2 Fk-1] = O, and hence S& - > D2 is a martingale w.r.t. { Furthermore, we can verify E [ C(28): by Sauchy-Schward inequality.
E (1 + 1)8 I 1| = (I: + 1)28 E + V E I
By the procedure described in Algorithm 2, the switching threshold is no larger than log k for every step before k, and therefore, according Lemma 9,
E |
[2((lg p. p, w x(P)) O ((log k))) C(D),
where < p. < and P > are constants such that A PA x pP. which exist due to the stability of A, Q is defined as in Lemma 9, and W is defined in (25). Also taking note of the fact E
E| p(p 2) C()), we have
E B|[(k + 1) IK+I GI C(23),
and hence,
E 1h 1 = E ((: + 1) 1 Ho 122 S (I( |s + 1) Fx+ GT + [|Holl)
2 E (A: + 1) 15 1| + Holl 12) ~ C(2
By applying Lemma 11 to the martingale } defined above, we get
H Ho (B-2)
Now assume that т 2 1 and that we already have
Al, He ~ c c(3 111
(41)
for = 0, I....,T - 1. Then
Ar. HE,
(i 7)
Ij Hu si--1 Hurr
h: i=741
t=0
(i+ 1)3
U
CuT - Hkr -HKT
h:
(1+1)8
Fit++1
H r-t
57 -HEr
[ H.
(i + 1)8ūrtt-
(42)
k:
Completely similarly to the case T = 0, we can show
k-r-1
Σ
(i+ 1)8
Σ
5. Hk.r ~ (3-12)
1: - 1=0
I44+1
2
1=0
23

---

Under review as a conference paper at ICLR 2022
Meanwhile, for each of t 0, .. 1, define $ = (k+ + 1) uSA In view of (37) it can be shown E Fi-i] = 0, and hence S _ Eiz 2 is martingale w.r.t {Fr). Furthermore, by the procedure described in Algorithm 2, - I| I (log(k t))² < (log k)*, we have
x l| $ (k 1)28 (log k)* E || 11 C(28).
By applying Lemma 11 to the martingale S defined above, we get
K-T-1
( ~ (8-
Σ
which together with (41) implies
1 u ~ (c(2(8-))) ~e c(8-2)
(He. H1)
Now that we have shown the RHS of (42) is the sum of + matrices, each of order (3 - -) we get
H HE C (B (
According to our definition of C(a), this is to say it holds almost surely that
H
lim R-000
O,
where 7 112 1/2-1 - B>> 0, for any O, which concludes proof.
A.4 PROOF OF THEOREM 3
Let us denote by Jūy the cost of a policy x when acting on a system in the form (1) with process noise covariance W. Let consider the following variants of policies:
optimal policy, i.c., T² (x) K'x, with K defined in (6).
नें certainty equivalent policy with no exploratory noise, i.e., #x(x) = Rg..
नxं safe switching policy with no exploratory noise, i... Algorithm 2 invoked as
(xx, &; +oo).
Tai safe switching policy with exploratory noise, i.e., the actually applied policy step k.
Notice that J JW and J J.. Our plan decomposing J J as
gh - J (JW - - +++1)) 201) + ('++(++1) (W -W (JW- - -WW
jåz (( 20 W - 201) +
and bounding the RHS terms respectively. We next tackle these terms in reverse order:
1. J : for arbitrary stabilizing linear feedback policy (()) Kx, know the cost is J = tr(WP)) P), where solves the discrete Lyapunov equation (32). By Theorem 2, the Markov parameter estimates converge C(-7). Since with random input
[4
in Algorithm 3, the matrix
is full row rank, it follows that the pseudo-inverse inverse operator
is differentiable, which together with Lemma guarantees that A A, B,. Due to the differentiability of the stabilizing solution of the discrete algebraic equation, there is also K₂ K* C(-7)- In particular, [K&} converges to K almost surely, and since K is stabilizing, have for almost every realization of randomness, K₂ is also stabilizing for sufficiently large k. Assuming w.l.o.g. that K₂ is stabilizng for any
C(-7)-
24

---

Under review as a conference paper at ICLR 2022
k, have JW - JW tr( P*)). where P is the Lyapunov equation solution corresponding to K also the solution to the Riccati equation (5), and Ps. is the Lyapunov equation solution corresponding to Rg. According to Lemma 13, we have
(1 (1- 2 AT)
2
|| - - -
|
Rs
- K
F
A + BKg. Since every As is stable, we have (1 | Ag x A
where Aş
is
a continuous function of Ag. Meanwhile, {As} converges to A+ BK*, which implics
AI 2 A
is bounded. Hence, Ks K* C(-7) implies Pa P
12
C(-27). Finally, we have JW - Jiy (P( - PP)) ~ C(-2n).
2. J R W+(k+1)-281 - :w from Juy = (r(WWP)) with Pk. defined the same as above, we have f&
Pk). Px). Since (Pk} converges to p 0. we have W++k+1) 291 -w = tr((k + 1)
W++++1) 291 - JW C(-23).
3. J W+(++1)-281 J ( we can basically apply Lemma 10. To verify the con- ditions of Lemma 10, first fix p. P: since A BK* is stable, for any fixed > 0, P(A T
the discrete Lyapunov equation (A + BK*)
+ BK*) + Q = has a solution P 0. Therefore, there exists P 0,0 p < 1, such that (A + BK*) P(A + BK*) < pP. Since (K&} converges to K* almost surely, we may assume w.l.o.g. that (A + PR() + BK₃) < pP for any k. Furthermore, since A is stable, OC, and therefore, with
[logk] sufficiently large, also have (A') PA < pP. For an upper bound of the noise magnitude, we insert W + I in place of W in (25) to compute W. Now that A, B, Q, R. W p, P are all fixed, tain Jhe
there is A'
as
apply the conclusion of Lemma 10 by taking the limit K₁ K ob- W++++2) 201
Jhk (l++))) 201 ((log k22 exp(- k)))) C(- C(-o)).
4. JW (k++1) 2ay these two costs are associated with the same closed-loog -loo system and differ only in the u. Rug terms. In particular, JW - (K++k) 20, = tr( + 2. R) ~
C(-28).
Adding up the above four terms using Lemma 2. we obtain J C(max -23, -00}
C(- m23 2n)).. According to our definition of C(x)), this is to say it holds almost surely that
J
J
lim A-
(2 O,
for any e > 0, which concludes our proof.
B AN ILLUSTRATION OF OSCILLATION UNDER SWITCHING
In this section, we provide simple illustrative example to explain why we need prolonging "non- action" period in Algorithm 2.
Consider a simple two-dimensional noise-free system
Tk+1 Ag.ts
where the candidates for Aş are
0.5
2
0.5 0
An =
A =
0.5
0.5
It can be seen p(Ao) = p(Ai) = 0.5, i.e., both the system matrices are stable. Now consider the following switching strategy:
25

---

Under review as a conference paper at ICLR 2022
If | 2 M, then apply Ag for t consecutive steps.
Otherwise, apply A1.
Figure 4 shows simulation results with zp = (0.1, 1). M = 1 and t 1,2. We can observe that even for this simple system, the frequent switching caused by while / = suffices to suppress the oscillation. Indeed, we can verify p(A1 Ao) & 4.5 > even though both Ag and A₁ are stable. However, long as Ag stable, A1 will eventually become stable as is chosen to be sufficiently large. This explains why we use prolonging t in our policy.
may cause the state oscillate,
Threshold Tnit. state
2
3
Figure 4: Illustrative example of oscillation under switching. In this example, 1 causes the state to oscillate, while t = 2 can suppress the oscillation.
26


Reviews:
[{"review_id": "ssh5UEEzSY9", "reviewer": "Reviewer_ZdU6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The studied problem of online learning for LQR control is a very interesting topic and has gained significant attention lately. There are many existing results on the regret analysis in a probabilistic setting, e.g. using certainty equivalent control strategy. Compared to that line of work, the key difference in this paper is the modified version of the standard certainty equivalent control strategy, by allowing the system to take zero action for a certain amount of time and avoid potential destabilization. While the reviewer found this idea intriguing, there are places where further clarification is needed to better justify the claims. Please see detailed comments as follows:\n\n- Safety v.s. stability: it is a bit confusing to use the notion of safety rather than stability in the paper, since safe learning often refers to a different problem where a dynamical system is expected to avoid entering certain risky states during learning. The reviewer would suggest to use stable/stability that better describe the discussed problem here. \n\n- Motivation of using Markov parameter inference: while the convergence of parameter inferences looks good, it is unclear why not use the standard least square estimation that directly estimate the matrices A and B. Or in other words, will it disrupt performance and estimation guarantees if switching to the least square approach?\n\n- Proof of theorem 1: One key claim is that all policies derived from the proposed learning process is stable, which seems to mainly rely on the assumption of the innate stability of the system without external control input. However, it is difficult to see how this could be justified given the switching control strategy which also has the normal certainty equivalent control component with exploration noise. For example, it seems the proof of Theorem 1 (Section A.2) only discusses the innate stability analysis when \\norm{x_i} is larger than log k. Also, given the assumption of the innate stability with the matrix A, wouldn’t that be straightforward to simply take no-action and thus converging to the origin easily?\n\n- Correspondence to optimal rates with high probability: While it is claimed that the derived performance match up with the known optimal regret in the high probability regime, the reviewer does not find the analysis. Authors are encouraged to provide more details in the main context to help build the connections. For example, it is still unclear to me how the almost sure performance is achieved despite the stochastic noise in the dynamics. \n\n- Experimental results: there are no comparison results to other work (e.g. standard certainty equivalent control), which is a weakness to the reviewer. \n\n===== After Rebuttal ======\nI appreciate the authors’ responses and revised content. Given the remaining concerns from the reviewer, additional feedback has been provided in the detailed response to help strengthen and justify the technical contribution further.\n", "summary_of_the_paper": "This paper addresses the unconstrained stochastic linear-quadratic dual control problem with online parameter identification in an online setting, where a near-optimal control policy is sought to minimize the infinite-horizon quadratic cost (i.e. stabilizing the linear dynamical system) while learning the initially unknown matrices A and B. Instead of deriving a regret bound with a high probability done in the standard certainty equivalent learning schemes, this paper focuses on the almost sure convergence to the optimal control performance. The presented main contribution is the proposed switched control strategy (a stability-augmented certainty equivalent controller) and a parameter inference scheme that estimates the impulse response of the dynamical system in contrast of the matrices A and B. Theoretical analysis of the convergence rate of inference error and control performance is provided. Simulation results on the Tennessee Eastman Process (TEP) are given to validate the proposed LQ dual control algorithm. ", "summary_of_the_review": "The paper is in general well-written, but the reviewer still has several critical concerns over the justification of the claimed property due to lack of enough details. Authors are encouraged to provide more discussion in the main context to justify how the proposed components lead to the improvement compared to the standard approaches. More comparative results to other baseline algorithms are necessary to demonstrate the claimed significance of the proposed algorithm.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "oHiupMrgS9P", "reviewer": "Reviewer_oE9i", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although my overall impression of the paper is positive, there are several concerns which limit the significance of the result. First, while the definition of a \"safe learning process\" is clearly articulated in Definition 2, such a definition by itself does not ensure stability, as the act of switching between stable policies may be unstable -- as observed by the authors. While the authors address this issue using inherent stability of the process and implementing what is effectively a kill switch, such an approach is clearly conservative, and, moreover, there is no statement in the main results directly establishing stability of the trajectories (although clearly such trajectories are bounded).\n\nThis brings up the second point, which is that the proposed approach is rather cautious. Convergence in the simulation seems to require $~10^8$ time steps - presumably due to the rather large state-dimension of the numerical example.\n\nAnother point which I found significant is the omission of the vast literature on the problem of adaptive control (aside from the 1960 paper). While clearly the adaptive control approach is dated and only estimates a few system parameters, it considers precisely the problem formulated by the authors. \n\nFinally, I would have liked to see more justification for the estimate of the performance metric in the numerical analysis. It is unclear to me that Algorithm 2 actually produces a policy -- as opposed to simply the next input value. Yet computing the objective requires such a policy. What is being done here?\n\nIf the issues mentioned above can be satisfactorily addressed, the paper should be suitable for publication.\n\nNotes:\n- Why is there no $B_2$ matrix for representing the effect of process noise?\n- It is unclear if the numerical examples include process noise and if so, what are the properties of this noise?\n- The simulated is system is non-trivial and provides plausible insight into the performance of the algorithm.\n- Remark 2: Can the authors support \"easily satisfied\" with a proof or reference?\n- The use of $J^{\\pi_k}$ is a bit unclear. Algorithm 2 does not actually return a policy -- only the next input and internal state. How can a policy be extracted from this algorithm? -- a policy which is needed to compute the performance index.\n- Define \"almost surely\" in Theorem 2.\n- Typos: \"The complete algorithm we propose LQR dual control is presented in Algorithm 1.\"; \"would suffice characterize\"; \"\"\n", "summary_of_the_paper": "This paper addresses the problem of combining system identification and optimal control in an online framework for stable linear systems with full-state sensing. Despite the restrictions of linearity, stability, and full-state sensing, the proposed problem formulation is still challenging and I am unaware of any results which provide the same optimality guarantees provided by the authors in the online framework. The paper itself is unusually well-conceived, well-written, well-structured, is clear, and makes very efficient use of notation.", "summary_of_the_review": "My overall impression of the paper is positive. While the switching between policies seems a bit ad-hoc, the performance and convergence guarantees are solid -- correctly formulated and true. The paper addresses a real problem of current interest and provides a solid theoretical foundation for the proposed method. The numerical simulations are non-trivial and convincing. I have some minor concerns, but they can likely be addressed in the author response.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kDw8K_eohj9", "reviewer": "Reviewer_qNrU", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The question asked by the paper is very intriguing: establishing a.s. guarantees instead of w.h.p. guarantees for learning-based control is indeed very important for safe implementation on physical systems. Hence, I read the paper with great interest and checked the proofs of the paper. The paper is well-written. However, I have several concerns listed below.\n\n1. [Def 2] My biggest concern on the safety definition is on Def 2. In this paper, a time-varying sequence of policies is considered, thus inducing a time-varying system. It is well-known that the stability of individual time-invariant systems does not guarantee the stability of the time-varying systems, even for linear systems, i.e. even if Ak is stable for all k, the linear time-varying system x_{k+1}=Ak x_k can no longer be stable. In fact, this is one of the major difficulties in adaptive control, i.e. how to guarantee stability while updating the policies. One approach to get around this is by considering piecewise-constant policies (or episodic based policies) as in most papers on learning-based LQR. But this paper updates the policy at every step, which calls for other ways to ensure closed-loop stability (e.g. slowly varying policies), hence I found it weird to define stability/safety purely on individual policies. \n\n2. [Def 1 and Theorem 1] Further, for Def 1, the definition makes sense for linear systems because a finite stochastic LQR's cost happens to coincide with the stability of a linear policy u=Kx. However, the policy designed in Algo 2 is essentially a nonlinear policy or piecewise linear policy. For nonlinear policies, a more common stability notion is input-to-state stability (ISS), which essentially requires that if the noises are small, then the states will be small. However, Def 1 does not seem to capture this. Further, Def 1 does not seem to require the stability of K used when |x|< log(k) for some index k in the policy structure considered in Algo 2. This suggests that a safe policy according to Def 1 may constantly steer the state to a distant though bounded location even when the system noises w are very small. Hence, I found the safe definition in Def 1 quite weak and it can be satisfied by merely adding this switch-to-0 policy structure without implying any stability property on the system.\n\n3. [Algo 3 and Theorem 2] The Markov parameter estimation is very interesting. But I hope the authors can provide more explanation on why using Markov parameter estimation instead of the traditional least-square estimation directly on A, B. For output-feedback, it is more intuitive to learn markov parameters, but for full-state-feedback, learning markov parameters seem to increase the number of parameters to be learned, thus increasing the sample complexity and slower the learning. The only reason I can imagine from reading the paper is that the authors are able to establish the a.s. convergence rate of Alg 3, while the current literature on least-square estimation usually gives results on finite-sample confidence bound with some probability p<1, e.g. [Dean et al. 2018]. That being said, those literature focuses on the finite-sample case, but this paper considers the asymptotic case, so I am struggling to compare the results in this paper and in the literature. From one side, since ordinary least square also has strong consistency, so least square estimation should also result in a.s. convergence in the asymptotic sense, right? From the other side, how does Theorem 2 extend to the non-asymptotic case? I guess the result will still look like confidence bound with some probability in (0,1)? I would really love to hear the authors' thoughts on this.\n\n4. [Theorem 3] The authors compare Theorem 3 with the regret analysis in (Simchowitz & Foster (2020)), but I found this comparison not straightforward. Notice that J^pi_k does not represent the stage cost, but the infinite-horizon-averaged cost by implementing the policy generated at time k in a separate trajectory for infinitely long. So summing J^pi_k over k does not directly represent the realized cost of the adaptive learning algorithm. Could the authors provide more comments on this difference from the standard regret guarantee? \n\n5. [Simulation] I appreciate the numerical results provided in this paper. I just wonder how this algorithm compares with existing adaptive learning algorithms? it would be great to show that some scenarios where some existing adaptive learning algorithm does not converge but your algorithm does.\n", "summary_of_the_paper": "This paper studies an adaptive control for LQR and provides an algorithm to converge to the optimal policy almost surely in an asymptotic sense, where the convergence rate is also provided. The paper assumes that the system is open-loop stable, and switches to zero control input (with exponentially decaying excitation noises) for a while when the state or control gain is larger than O(log(k)), which can steer the state to a smaller neighbourhood of 0 due to the open-loop stability of the original system. Theoretically, the paper shows that any switched policy generated by the algorithm guarantees a finite infinite-horizon-averaged cost, which is called \"safe\" in this paper. Further, the paper establishes the strong consistency of the Markov parameter estimation in Alg 3 with an error convergence rate. Besides, the paper shows that the learned policies converge to the optimal policy at a rate of O(1/sqrt(k)) in terms of the infinite-horizon-averaged cost. Lastly, the performance is evaluated with different parameter choices of the algorithm.", "summary_of_the_review": "The paper asks a very important question: establishing a.s. guarantees instead of w.h.p. ones for safety. The paper is well-written. However, the safety definitions introduced in this paper do not indicate the stability of the system in any sense, thus I found these safety requirements relatively weak. Further, though the authors compare the results with the regret bounds, Theorem 3's result does not directly reflect the regret, so I hope to see more comments on the connections between Theorem 3 and regret. Lastly, the paper establishes a.s. guarantees only in the asymptotic sense, instead of for finite samples. Since the least square estimation used in the current literature also converges a.s. asymptotically, I am not sure how much progress this paper provides compared with the literature. I think it would be much more interesting to establish a.s. guarantees in non-asymptotic cases (some random example that comes to me right now is  Regret <o(T) a.s. for any finite T, instead of w.h.p., but any other a.s. guarantees would be great, especially in constraint satisfaction, which is also an important requirement for safety). ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7RTfFjGPqPg", "reviewer": "Reviewer_1scp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Update: After the edits the authors did, together with the edits they promise to do, the paper can be accepted.\n_________________________________________________________\nOriginal Review: Regretfully, the manuscript cannot be accepted due to different issues. First, it aims to re-establish existing results. Moreover, there are frequent incorrect and/or incomplete claims in the manuscript. Unfortunately, lack of novelty, lack of connections to existing work, incomplete literature review, unsupported and/or wrong statements, and subpar presentation, prevent the manuscript from being accepted.\n\nThe claim that high probability results do not imply almost sure convergence is ONLY true if the failure probability is a design parameter. (Of course, even in this case, by letting it shrink as time grows, we obtain almost sure convergence). So, to see a work that failure probability is not a used in the algorithm, search for \"Input perturbations for adaptive control and learning\" and see the reference therein. Specially, one of the references exactly establishes the almost sure results this manuscript aims to provide. Further, in the existing literature, the problem is addressed without the assumption of open-loop stability (or initial stabilizer), and I recommend the authors to use google scholar to find the rich literature of adaptive stabilization. \n\nHere, I mention a few more issues, but there are multiple similar things the authors need to address for resubmitting the manuscript. The existing literature also relaxes the assumptions on the noise so that neither normality nor stationarity are needed. Also, there are results on worst-case performance (ie stochastic sub-optimality) which are stronger than the approach of average-case (ie expected) sub-optimality of the manuscript. I guess by \"learning process\" in Def 2 the authors mean 'sequence of policies'. It is unclear why line 7 of algorithm 1 is better than the least-squares estimate (although it is very similar). About Lem 10, isn't it an immediate consequence of sub-Gaussianity? Statement of Lemma 1 assumes full accuracy, and so is unacceptable and does not provide consistency (as the authors claim). \"It should be noticed ...\" on p8 is not accurate. Finally, \"TS is in general computationally inefficient\" needs justifications.\n\n ", "summary_of_the_paper": "The paper studies reinforcement learning policies for an unknown linear system with quadratic cost functions. It is shown that the presented algorithm provides consistent estimates and the rates are provided.", "summary_of_the_review": "Update: After the edits the authors did, together with the edits they promise to do, the paper can be accepted.\n_________________________________________________________\nOriginal Summary: Regretfully, the manuscript cannot be accepted due to different issues. First, it aims to re-establish existing results. Moreover, there are frequent incorrect and/or incomplete claims in the manuscript. Unfortunately, lack of novelty, lack of connections to existing work, incomplete literature review, unsupported and/or wrong statements, and subpar presentation, prevent the manuscript from being accepted.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main contribution of the paper is in providing an additional layer to standard certainty-equivalent control for LQR dynamics, that essentially prevents the state from exploding exponentially, via forcing a "descent" to a small bounded state space in growing epoch sizes. Theoretically, this is shown to ensure a notion of boundedness which is termed as "bounded cost safety".

Overall, the reviewers raised several concerns in their initial reviews. These included the relevance of the proposed new approach to modeling "safety" here, whether it is actually novel given the assumptions about open loop stability of the original plant, the fact that the learning algorithm could take the state to arbitrarily large states durign the learning process, the significance of the contribution of the paper wherein a "kill switch" is effectively being designed depending on the state norm, whether least squares is an arguably simpler system estimation method compared to the impulse response estimator here, whether existing approaches based on an input failure probability parameter can be used to yield the same result by iteratively taking it down to zero, and other concerns about the technical exposition.

The author(s) provided detailed responses to the reviewers' concerns. Specifically, the safety/stability notion was clarified as being distinct from standard input-to-state stability, that the learning algorithm could, during its operation, drive the system state to arbitrarily large sizes (although asymptotically almost surely this is supposed to not happen), and how this paper's assumptions are different (and lighter) than other related work that achieves almost-sure guarantees.

In the discussion that ensued after the author response period, it was clear that the author responses had helped to address many of the reviewers' concerns. However, the overall impression has still not been convincing enough to recommend acceptance. This is primarily on two fronts, which I hope that the author(s) can address in the future to strengthen the submission: (1) The attempt at expressing "safety of learning" is found to be not satisfactory, in view of the observation that the proposed scheme does not guarantee classical notions of stability while in the process of learning. It also makes the main message of the paper confusing -- the reviewers noted that the words "safety" and "safe learning" still recur in the revised manuscript, creating scope for misinterpretation. (2) The algorithmic contribution appears to be incremental -- its essence is to "apply the brakes when the car runs too fast". This is not to take away from the hard work put in to analyzing the algorithm and deriving guarantees. (3) The experiments benchmarking the proposed strategy are not comprehensive
-- more relevant baselines drawn from existing work, such as the ones
that have emerged from the author response discussion, could be compared against. In fact, it would be compellingly in favor of this submission for the author(s) to show that other approaches fail to offer the same kind of "safe" performance that is expected.

Upon a more careful reading by myself in the recent past, I would also like to bring up a fundamental technical criticism about Theorem 1 and Defn. 2 ("bounded-cost safety"), which I believe must be fixed before the paper's conclusions can be accepted. Defn. 2 states that a learning process if bounded cost safe if for all times $k$, $\pi_k$ is not destabilizing in the sense that its value function is finite. However, the sequence of policies $\pi_k$, $k=1, 2, \ldots$ is a sequence of
*random* objects. So in what sense is Defn. 2 to be interpreted? If
the author(s) mean(s) to say that the event {$\forall k=1, 2, ...: \pi_k$ is not destabilizing} occurs w.p. 1, then this is a very strong requirement and cannot be guaranteed (random noise can cause a 'bad' controller to be learnt and applied at some time t with positive probability). Basically my contention is that Defn. 2 is incomplete for a theory-oriented paper like this, and as a consequence I do not see why Theorem 1 should hold (or more precisely, in what sense it should hold). The proof of Theorem 1 is not clear as well: The expectation in the third sentence of Sec A.2 ought to be taken for a
*fixed* controller $\hat{K}_k$ *always applied* to a system from time
zero until infinity. I do not see why a fixed controller's (standard infinite horizon average) cost should always be finite, leading me to suspect an irregularity in the proof argument. I wish this point could be discussed and resolved earlier in the author response phase, but it is unfortunately too late.
Decision: Reject