Safe Linear-Quadratic Dual Control with Almost Sure Performance Guarantee
Year: 2021

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+ ), while the suboptimality gap of control performance scales as O(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.

heading: 1 INTRODUCTION
text: One of the most fundamental and well-studied problems in optimal control, Linear-Quadratic Regulation (LQR) has recently aroused renewed interest in the context of data-driven control and reinforcement learning. Considering it is usually challenging to obtain an exact system model from first principles, and that the system may slowly change over time due to various reasons, e.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 et al. (2019); Cohen et al. (2019); Wagenmaker & Jamieson (2020). In particular, from the perspective of reinforcement learning theory, the LQR problem has become a standard benchmark for continuous control.
In this paper, we focus on the dual control (Feldbaum, 1960) setting, also known as 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 exploration-exploitation dilemma. Recently, it was shown by Simchowitz & Foster (2020) that the optimal regret for this problem setting scales as Θ̃( √ T ), which can be achieved with probability 1 − δ using a certainty equivalent 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 strategy proposed in this work, like those in its predecessors (Abbasi-Yadkori & Szepesvári, 2011; Dean et al., 2018; Mania et al., 2019), may have a nonzero probability δ of failing. Furthermore, it shall be noticed that δ has been chosen as a fixed design parameter in the aforementioned works, which 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:
Can we design a learning scheme for LQR dual control, such that the policy adopted in almost every trajectory converges to the optimal policy?
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 corrupted 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 a notion of bounded-cost safety for the LQR dual control problem: we recognize a learning scheme to be safe if no destabilizing control policy is applied during the entire learning process.
In this paper, we propose a learning scheme that satisfies the above definition of bounded-cost safety, and guarantees both the parameter inference error and the suboptimality gap of controller performance converge to zero almost surely. Our strategy consists of two parts: a safe switched controller and a parameter inference algorithm. The switched controller can be viewed as a safety-augmented 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 a conservative 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,B 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 martingales. We prefer this approach for its clarity in 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 parameter inference error scales asO(T−1/4+ ), while the suboptimality gap of control performance scales as O(T−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 a 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-probability 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 boundedcost safe learning scheme. Section 3 presents and interprets our algorithm. Section 4 states the main theoretical results and characterizes the convergence rates. Section 5 provides simulation results on an industrial process example to illustrate the effectiveness of our proposed strategy. Section 6 summarizes the related literature. Finally, Section 7 gives concluding remarks and discusses future directions.

heading: 2 PROBLEM FORMULATION
text: We consider the control of the following discrete-time linear system:
xk+1 = Axk +Buk + wk, (1)
where xk ∈ Rn is the state vector, uk ∈ Rp is the input vector, and wk ∈ Rn is the process noise. We assume x0 ∼ N (0, X0) , wk ∼ N (0,W ), and that x0, w0, w1, . . . are pairwise independent. We also assume w.l.o.g. that (A,B) is controllable.
We consider control policies of the form
π : Rn × Rq → Rp × Rq, (uk, ξk+1) = π(xk, ξk), (2) which can be either deterministic or stochastic, where ξk ∈ Rq is the internal state of the policy. Notice that we allow the flexibility of the policy being non-Markovian with the introduction of ξk,
and we also use the simplified notation uk = π(xk) if π is Markovian. The performance of a policy π can be characterized by the infinite-horizon quadratic cost
Jπ = lim sup T→∞
1 T E [ T−1∑ k=0 x>k Qxk + u > k Ruk ] , (3)
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π, π∗ ∈ arg min π Jπ. (4)
It is well-known that the optimal policy is a linear function of the state π∗(x) = K∗x, with associated cost J∗ = tr (WP ∗), where P ∗ is the solution to the discrete-time algebraic Riccati equation
P ∗ = Q+A>P ∗A−A>P ∗B ( R+B>P ∗B )−1 B>P ∗A, (5)
and the linear feedback control gain K∗ can be determined by
K∗ = − ( R+B>PB )−1 B>P ∗A. (6)
Based on the definitions above, we can use Jπ−J∗ to measure of the suboptimality gap of a specific policy π.
In the online LQR setting, the system and input matrices A,B are assumed unknown, and the learning process can be viewed as deploying a sequence of time-varying policies {πk} with the dual objectives of exploring the system parameters and stabilizing the system. To characterize the safety of a learning process, we make the definitions below:
Definition 1. A policy π is destabilizing if Jπ = +∞. Definition 2. A learning process applying policies {πk}∞k=0 is bounded-cost safe, if πk is not destabilizing for any time k and for any realization of the noise process.
Notice that Definition 1 is a generalization of the common notion of destabilizing linear feedback gain, i.e., π(x) = Kx is destabilizing when ρ(A + BK) ≥ 1, which is equivalent to Jπ = +∞. 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 out that bounded-cost safety does not guarantee the stability of trajectories, but is an indicator of the reliability of a learning scheme.
We assume the system is open-loop strictly stable, i.e., ρ(A) < 1. Indeed, if there is a known stabilizing linear feedback gain K0, then we can apply the dual control scheme on the pre-stabilized system (A + BK0, B) instead of (A,B). Existence of such a 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 et al., 2019; Faradonbeh et al., 2018b) or adaptive stabilization methods (Faradonbeh et al., 2018a; 2019).

heading: 3 ALGORITHM
text: The complete algorithm we propose for LQR dual control is presented in Algorithm 1. The modules in the algorithm will be described later in this section.

heading: 3.1 SAFE CONTROL POLICY
text: This subsection describes the policy for determining the control input uk. The first n + p steps are a warm-up period where purely random inputs are injected. Afterwards, in each step, we inject a exploitation term ũ plus a polynomial-decaying exploratory noise (k+ 1)−βζ, where the decay rate β ∈ (0, 1/2) is a constant. The exploitation term ũ is a modified version of the certainty equivalent control input K̂kxk, and this modification, described in Algorithm 2, is crucial to the safety of the learning process, which we will detail below.
Algorithm 1 Safe LQR dual control Input: State dimension n, input dimension p, exploratory noise decay rate β
1: for k = 0, 1, . . . , n+ p− 1 do 2: ξk+1 ← 0 3: Apply control input uk ← (k + 1)−βζk, where ζk ∼ N (0, Ip) 4: for k = n+ p, n+ p+ 1, . . . do 5: Observe the current state xk 6: for τ = 0, 1, . . . , n+ p− 1 do
7: Ĥk,τ ← 1
k − τ k∑ i=τ+1
(i− τ)β [ xi −
τ−1∑ t=0 Ĥk,tũi−t−1 ] ζ>i−τ−1
8: Reconstruct Âk, B̂k from Ĥk,0, . . . , Ĥk,n+p−1 using Algorithm 3 9: Compute certainty equivalent feedback gain K̂k by replacing A,B with Âk, B̂k in (5),(6)
10: Determine policy πk(·, ·)← π(·, ·; k, K̂k, β), where π is described by Algorithm 2 11: (uk, ξk+1) ← πk(xk, ξk); record ũk ← ũ, ζk ← ζ, where ũ, ζ are the corresponding vari-
ables generated when executing the policy 12: Apply control input uk
Algorithm 2 Safe policy π(x, ξ; k,K, β) Input: Arguments: system state x, policy internal state ξ; Parameters: step k, linear feedback gain
K, exploratory noise decay rate β Output: Control input u and next policy internal state ξ′, i.e., (u, ξ′) = π(x, ξ; k,K, β)
1: if ξ > 0 then 2: ũ← 0, ξ′ ← ξ − 1 3: else 4: if max{‖K‖ , ‖x‖} ≥ log k then 5: ũ← 0, ξ′ ← blog kc 6: else 7: ũ← Kx, ξ′ ← 0 8: u← ũ+ (k + 1)−βζ, where ζ ∼ N (0, I)
In short, we stop injecting the exploitation input for blog kc+ 1 consecutive steps, if either the state norm ‖xk‖ or the norm of the feedback gain ‖K̂k‖ exceeds the threshold log k. Recall from (2) that we use ξk to denote the internal state of the policy, and in Algorithm 1, ξk is a 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 a critical feature of our control design, without which the controller learned from data may destabilize the system, albeit with a 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 in Section 5.
We choose both the switching threshold and the length of the “non-action” period to be timegrowing. The enlarging threshold corresponds to diminishing degree of conservativeness, which is essential for the policy performance to converge to the optimal performance. Meanwhile, the prolonging “non-action” period rules out the potential oscillation of state caused by the frequent switching 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 as O(tM exp(−cM2)), where M is the switching threshold, t is the length of the “non-action” period, and c is a system-dependent constant (see Lemma 10 in Appendix A.1.2). With both M and t growing as O(log k), the contribution of our switching strategy to the overall suboptimality gap is merely Õ(1).

heading: 3.2 PARAMETER INFERENCE
text: The Markov parameters of the system described in (1) are defined as
Hτ , A τB, τ = 0, 1, . . . . (7)
The Markov parameter sequence {Hτ}∞τ=0 can be interpreted as the impulse response of the system. It 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. In particular, our inference algorithm estimates the first n + p terms of the impulse response. We denote our estimate of Hτ at step k by Ĥk,τ , whose expression is specified in line 7 of Algorithm 1. Based on the cross-correlation between the current state xk and a past exploratory noise input ζk−τ−1, we can produce an unbiased estimate of Hτ at each step, and Ĥk,τ is a cumulative average of such unbiased estimates, whose almost-sure convergence to Hτ can be established through a law of large numbers for martingales (see Appendix A.1.3).
Remark 1. From a computational perspective, line 7 of Algorithm 1 can be decomposed to enable efficient recursive updates. To see this, we can rearrange this expression as
Ĥk,τ = 1
k − τ k∑ i=τ+1 (i− τ)βxiζ>i−τ−1 − τ−1∑ t=0 Ĥk,t
[ 1
k − τ k∑ i=τ+1 (i− τ)β ũi−t−1ζ>i−τ−1
] ,
the weighted sum of τ + 1 cumulative averages, each of which can be updated with a 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 {Ĥk,τ}n+p−1τ=0 , we can reconstruct Âk, B̂k by fitting the data obtained from several rollouts on the virtual system described by {Ĥk,τ}n+p−1τ=0 . The procedure is detailed in Algorithm 3.
Algorithm 3 Restoring system and input matrices from Markov parameters
Input: Markov parameter estimate sequence Ĥ0, Ĥ1, . . . , Ĥn+p−1, number of simulated trajectories N Output: System matrices estimate Â, B̂
1: Construct block Toeplitz matrix T ←  0 0 0 · · · 0 Ĥ0 0 0 · · · 0 Ĥ1 Ĥ0 0 · · · 0 ... ... ... . . .
... Ĥn+p−1 Ĥn+p−2 Ĥn+p−3 · · · 0  2: Choose N independent random input trajectories, each (n + p)-long, denoted by ui ←[
u (1) i u (2) i · · · u (N) i
] , i = 0, 1, . . . , n+ p− 1.
3: Stack the inputs vertically and compute states: Uv ← [u0;u1; · · · ;un+p−1] , [x1;x2; · · · ;xn+p] =: X v1 ← T Uv 4: Stack the inputs and states horizontally to form the following matrices: Uh ← [u0 u1 · · · un+p−1] ,X h1 ← [x1 x2 · · · xn+p] ,X h0 ← [0n×N x1 · · · xn+p−1]
5: Compute estimate [ B̂ Â ] ← X h1 [ Uh;X h0 ]† .
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τ = AτB for all τ = 0, 1, . . . , n + p− 1, and the matrix [ Uh X h0 ] defined
in Algorithm 3 has full row rank, the result of Algorithm 3 satisfies Â = A, B̂ = B.
Proof. When Ĥτ = AτB, we have X h1 = AX h0 +BUh = [B A] [ Uh X h0 ] . Since [ Uh X h0 ] has full row
rank, we have [ Uh X h0 ] [ Uh X h0 ]† = I , and therefore [B A] = X h1 [ Uh X h0 ]† = [ B̂ Â ] .
Remark 2. Lemma 1 guarantees the consistency of our controller, i.e., accurate Markov parameter estimates would generate an optimal exploitation input. The full-row-rank condition in Lemma 1, naturally satisfied by randomly generated inputs, guarantees that the inputs provide sufficient excitation to reconstruct system matrices from impulse responses. For the ease of analysis, it is also legitimate to use fixed, rather than random ui’s for each time step k of the outer loop of Algorithm 1, as long as the rank condition is satisfied.

heading: 4 MAIN RESULTS
text: 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 1 is bounded-cost safe according to Definition 2.
Theorem 2. Assuming A is stable, and 0 < β < 1/2, for Ĥk,τ computed in Algorithm 1, the following limit holds almost surely, i.e., with probability 1:
lim k→∞ Ĥk,τ −Hτ k−γ+ = 0, (8)
where γ = 1/2− β > 0, for any > 0 and any τ = 0, 1, . . . , n+ p− 1.
Remark 3. Theorem 2 states that our estimate of the Markov parameters converge at the order O (k−γ+ ). As a 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 estimates of A,B at O (k−γ+ ) using concentration bounds for martingale least-squares (e.g., Lemma E.1 in Simchowitz & Foster (2020)). Therefore, our parameter inference algorithm based on crosscorrelation can be viewed as a competitive alternative to the least-squares estimator. One feature of our cross-correlation approach compared to the least-squares approach, however, is that the estimation of Markov parameters can be easily extended to the partially observable LQR setting like the one considered in Zheng et al. (2020). Also, the convergence of our cross-correlation approach is not based on the sub-Gaussianity of the process noise (see Appendix A.3), which allows straightforward generalization to long-tailed noise models.
Theorem 3. Assuming A is stable, and 0 < β < 1/2, let πk be the control policy used at step k in Algorithm 1, then with Jπk and J∗ defined in (3), (4) respectively, for any > 0, the following limit holds almost surely, i.e., with probability 1:
lim k→∞
Jπk − J∗
k−min(2β,2γ)+ = 0, (9)
where γ = 1/2− β > 0.
Due to space limits, all the proofs are deferred to the appendix.
Remark 4. According to Theorem 2, the convergence rate γ is maximized when β → 0+. However, the exploration term k−β does not decay in this case, and the control performance Jπk will not converge to the optimal performance J∗. To achieve the fastest convergence of Jπk , we need to choose the decay rate of the exploration term to be β = 1/4, which maximizes min(2β, 2γ) = min(2β, 1 − 2β). When β = 1/4, we have both parameter estimation errors and policy suboptimality gaps scaling at Õ(1/ √ T ), which matches the asymptotic rates of corresponding components in the (with-high-probability) regret-optimal algorithm proposed in Simchowitz & Foster (2020). However, due to the challenging nature of the analysis of the nonlinear closed-loop system under our safe control scheme, the exact regret of our scheme is still under investigation.

heading: 5 SIMULATION
text: 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 a simplified version of TEP from Liu et al. (2020), where the state and input dimensions are n = 8, p = 4, and the spectral radius of the system matrix is ρ(A) ≈ 0.96. We assume Q,R, are identity matrices, and W,X0 are also identity matrices, i.e., the process noise is i.i.d. standard Gaussian. We choose N = 50 (in Algorithm 3) for all the experiments. In the practical implementation, the estimated system matrices Âk, B̂k and the feedback gain K̂k are updated only at steps b10n/2c(n ∈ 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 β ∈ {0, 1/4, 1/2}, with 108 steps in each experiment. Fig. 1 shows the error of the estimated system and input matrices, i.e.,
∥∥∥Âk −A∥∥∥ and ∥∥∥B̂k −B∥∥∥ against the time k for different values of β.
From Fig. 1, one can see when β 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 a 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 rateO (k−γ+ ), with γ = 1/2−β, i.e., convergence is only guaranteed with β < 1/2 and is faster when β is smaller.
Now we consider the performance of policies with different values of β. To quantify the policy performance, one shall in theory compute Jπk as defined in (3). However, the policies πk are nonlinear, rendering it very difficult, if not impossible, to compute Jπk analytically. As a surrogate approach for evaluating a policy πk, we define the empirical cost Ĵπk as
Ĵπk = 1
N
1
T N∑ i=1 T−1∑ t=0 ( x (i) t )> Qx (i) t + ( u (i) t )> Ru (i) t ,
where x(i)t , u (i) t are states and inputs collected from the closed-loop system under πk in N independent T -long sample paths indexed by i. 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 performance of controllers with different values of β against time k.
From Fig. 2, one can observe that among our choices of β, only β = 1/4 drives the controller toward the optimal one. For β = 0, 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 is because the exploration term (k + 1)−βζk in the control input does not decay, and the resulting controller is a noisy one. Meanwhile, for β = 1/2, diverging parameter estimates would lead to illperforming controllers. The observations are consistent with the theoretical conclusion indicated by Theorem 3 that β = 1/4 corresponds to the optimal trade-off between exploration and exploitation.
Finally, we compare our algorithm with the naive centainty equivalence algorithm, which applies uk = K̂kxk+k
−βζ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, as we did in Fig. 1 and Fig. 2. The results of this comparison experiment are presented in Fig. 3. In a proportion of the experiments (actually 7 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 a warm-up period for estimation, it should be noted that the failure probability is always nonzero as long as a linear feedback policy with learned gain is deployed. Even compared to the case where the certainty equivalence algorithm converges, our algorithm still delivers slightly lower estimation error and significantly better policy performance, which indicates that the conservativeness caused by our switching mechanism does not harm the long-term performance.

heading: 6 RELATED WORKS
text: The concept of dual control was initiated by Feldbaum (1960), and since then sustained research efforts have been devoted to learning to make decisions in unknown environments. Classical literature on adaptive control, e.g., Åströ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 a 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 to the LQR of unknown linear systems described by the state-space model.
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 developed 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 is to synthesize a controller based on the identification result and analyze the resulting closed-loop system’s performance. The Coarse-ID control framework (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 feedback (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 (Mania 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 intersection of the above two methods, an optimistic robust framework was proposed to achieve a combination of fast convergence rate and robustness (Umenberger & Schö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.
The problem of designing controllers that improve over time has been studied in the context of online LQR and regret analysis. The online LQR setting was initially proposed by Abbasi-Yadkori & Szepesvári (2011), and since then, Optimism in the Face of Uncertainty (OFU), Thompson Sampling (TS) and ε-greedy exploration have been applied to solve the online LQR problem. AbbasiYadkori & Szepesvári (2011) applied OFU principle to prove a theoretical Õ( √ T ) regret upper bound, but their method is computationally intractable. Cohen et al. (2019) proposed a tractable algorithm for OFU based on semidefinite programming to realize Õ( √ T ) regret. TS has been shown to achieve Õ( √ T ) (frequentist) regret for scalar system (Abeille & Lazaric, 2018), and Õ( √ T ) expected 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 ε-greedy exploration can also achieve Õ( √ T ) regret, and Simchowitz & Foster (2020) prove that Õ( √ T ) 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 expectation, and lack almost sure guarantee. Faradonbeh et al. (2020b) prove that Õ( √ T ) regret for both TS and CE and hold almost surely, but under the restrictive assumption that the closed-loop 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 LQR without assumptions on the system other than the existence a known initial stabilizer.

heading: 7 CONCLUSION
text: 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 error is O(T−1/4+ ), while that of the suboptimality gap is O(T−1/2+ ), 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 interesting to investigate the exact convergence rates, especially dimension dependence, of our parameter inference scheme and the standard least-squares procedure.

heading: A PROOF OF MAIN RESULTS

heading: A.1 PRELIMINARIES FOR PROOFS

heading: A.1.1 NOTATIONS
text: We will use the following notations throughout the proofs:
Notation Definition
X> transpose of matrix X
‖X‖ , ‖x‖ norm of matrix X or vector x, 2-norm by default ‖X‖F Frobenius norm of matrix X tr(X) trace of matrix X
ρ(X) spectral radius of matrix X
X 0 matrix X is positive definite X ≺ Y for matrix X,Y , Y −X 0 λmin(X) minimum eigenvalue of matrix X
κ(X) ratio between maximum and minimum eigenvalues for matrix X 0, i.e., κ(X) = ‖X‖ /λmin(X)
vec(X) vectorization of matrix X
X ⊗ Y Kronecker product of matrices X and Y 1S indicator function of set S
f(x) ∼ O(g(x)) there exists M > 0, such that |f(k)| ≤ M × g(k) for all k ∈ N
f(x) ∼ Õ(g(x)) there exists M > 0 and n ∈ N, such that |f(k)| ≤ M × g(k)× log(k)n for all k ∈ N
In addition, we define the following short-hand notation for characterizing the almost-sure asymptotic convergence or growth rate of random processes: for a random variable (vector, or matrix) sequence {xk}, we denote that xk ∼ C(α) if for all > 0 and almost all realizations of randomness, we have xk ∼ O (kα+ ), i.e., limk→∞ ‖xk‖ /kα+ a.s. = 0. The following lemma establishes some basic properties of C(α) functions: Lemma 2. Assume xk, yk are random variable (vector, or matrix) sequences with proper dimensions, then the following properties hold:
1. If xk ∼ C(α), yk ∼ C(β), then xk + yk ∼ C (max(α, β)).
2. If xk ∼ C(α), yk ∼ C(β), then xkyk ∼ C(α+ β).
3. If f is a function differentiable at 0 and xk ∼ C(α), α < 0, then f (xk)− f(0) ∼ C(α).
Proof. The first two claims follow trivially from the definition of C(α). For the third claim, notice that for all realizations of randomness, limk→∞ ‖xk‖ = 0. Therefore, Taylor expansion of f(x) at x = 0 gives f(xk) − f(0) = Df(0)xk + O(‖xk‖2), where Df is the Fréchet derivative of f . Dividing both sides by kα+ leads to the conclusion.

heading: A.1.2 PROPERTIES OF A CLASS OF SWITCHED LINEAR SYSTEMS
text: We state and prove some properties of a class of switched linear systems that will be useful for the proof of all the main theorems of this paper.
Consider the dynamical system xk+1 = Akxk + wk, (10)
where xk, wk ∈ Rn, x0 ∈ N (0,W−1) , wk ∼ N (0,Wk), x0, {wk | x0:k} are pairwise independent, and Ak,Wk are functions of x0:k and k. We assume
Wk 0, ‖Ak‖ ≤ A , ‖Wk‖ ≤ W , ∀k. (11)
We first prove a few miscellaneous lemmas that will be useful shortly:
Lemma 3. Let X ∼ χ2(p), then P(X ≥M) ≤ 2p/2 exp(−M/4) for any M > 0.
Proof. Applying the Chernoff bound, we have P(X ≥M) ≤ E [ etX/etM ] = (1− 2t)−p/2 exp(−tM)
for any 0 < t < 1/2. Choosing t = 1/4 leads to the conclusion. Lemma 4. Let w ∈ Rp, w ∼ N (0,W ) ,W 0, then P(‖w‖ ≥M) ≤ 2p/2 exp ( −M2 4‖W‖ ) .
Proof. Let v = W−1/2w, then v ∼ N (0, I) and hence ‖v‖2 ∼ χ2(p). From ‖w‖2 = w>w = v>Wv ≤ ‖v‖2 ‖W‖, we have P(‖w‖ ≥ M) = P(‖w‖2 ≥ M2) ≤ P(‖v‖2 ≥ M2/ ‖W‖). Applying Lemma 3 leads to the conclusion.
Lemma 5. Let 0 < x ≤ 1/2 and 1 < α < 2, then ∑∞ n=0 x αn < 2x/(α− 1).
Proof. By α > 1, we have αn−1 = (1+α−1)n−1 > n(α−1). Therefore, in view of 0 < x < 1, we have
∞∑ n=0 xα n = x ∞∑ n=0 xα n−1 < x ∞∑ n=0 x(α−1)n = x 1− xα−1 .
In view of the inequality (1+t)r ≤ 1+rt for t ≥ −1, 0 ≤ r ≤ 1, we have xα−1 = (1+x−1)α−1 ≤ 1 + (α− 1)(x− 1), and therefore,
x 1− xα−1 ≤ x (α− 1)(1− x) ≤ 2x α− 1
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 < ρ < 1 and P 0 such that A>k PAk ≺ ρP for every Ak, then when M ≥ √ 3W κ(P )/(1− ρ1/4), there is
P (‖xk‖ ≥M) ≤ 2n/2+1
ρ−1/2 − 1 exp
( − (1− ρ 1/4)2M2
4W κ(P )
) , ∀k.
Proof. From (10), we have
xk = Ak−1xk−1 + wk−1
= Ak−1(Ak−2xk−2 + wk−2) + wk−1
= · · · = wk−1 +Ak−1wk−2 + · · ·+Ak−1Ak−2 · · ·A1w0 +Ak−1Ak−2 · · ·A0x0.
Pre-multiplying by P 1/2 on both sides and applying the triangle inequality, we have∥∥∥P 1/2xk∥∥∥ ≤ ∥∥∥P 1/2wk−1∥∥∥+ ∥∥∥P 1/2Ak−1wk−2∥∥∥+ · · ·+ ∥∥∥P 1/2Ak−1 · · ·A1w0∥∥∥+∥∥∥P 1/2Ak−1 · · ·A0x0∥∥∥ . (12)
From A>k PAk ≺ ρP , we have for any w ∈ Rn, k ∈ N,
w>A>k PAkw < ρw >Pw ⇒ ∥∥∥P 1/2Akw∥∥∥ < ρ1/2 ∥∥∥P 1/2w∥∥∥ . (13) Applying (13) to (12) recursively, we have∥∥∥P 1/2xk∥∥∥ ≤ ∥∥∥P 1/2wk−1∥∥∥+ ρ1/2 ∥∥∥P 1/2wk−2∥∥∥+ · · ·+ ρ(k−1)/2 ∥∥∥P 1/2w0∥∥∥+ ρk/2 ∥∥∥P 1/2x0∥∥∥ .
(14)
Meanwhile, we have {‖xk‖ ≥M} = {∥∥∥P−1/2P 1/2xk∥∥∥ ≥M}
⊆ {∥∥∥P−1/2∥∥∥ ∥∥∥P 1/2xk∥∥∥ ≥M} = { 1√
λmin(P ) ∥∥∥P 1/2xk∥∥∥ ≥M} = {∥∥∥P 1/2xk∥∥∥ ≥M√λmin(P )} .
Therefore, for any σ ∈ (ρ1/2, 1), in view of (14), we have {‖xk‖ ≥M} ⊆ {∥∥∥P 1/2xk∥∥∥ ≥M√λmin(P )}
⊆ {∥∥∥P 1/2xk∥∥∥ ≥M√λmin(P )(1− σk+1)} ⊆ {∥∥∥P 1/2wk−1∥∥∥+ ρ1/2 ∥∥∥P 1/2wk−2∥∥∥+ · · ·+ ρ(k−1)/2 ∥∥∥P 1/2w0∥∥∥+ ρk/2 ∥∥∥P 1/2x0∥∥∥ ≥
M √ λmin(P )(1− σk+1) } ⊆ {∥∥∥P 1/2wk−1∥∥∥ ≥ (1− σ)M√λmin(P )} ∪ {ρ1/2 ∥∥∥P 1/2wk−2∥∥∥ ≥ σ(1− σ)M√λmin(P )}∪
· · · ∪ { ρ(k−1)/2 ∥∥∥P 1/2w0∥∥∥ ≥ σk−1(1− σ)M√λmin(P )}∪{ ρk/2
∥∥∥P 1/2x0∥∥∥ ≥ σk(1− σ)M√λmin(P )} . Taking the union bound, we have
P(‖xk‖ ≥M) ≤P (∥∥∥P 1/2wk−1∥∥∥ ≥ (1− σ)M√λmin(P ))+
P (∥∥∥P 1/2wk−2∥∥∥ ≥ σ
ρ1/2 (1− σ)M
√ λmin(P ) ) +
· · ·+
P (∥∥∥P 1/2w0∥∥∥ ≥ ( σ ρ1/2 )k−1 (1− σ)M √ λmin(P ) ) +
P (∥∥∥P 1/2x0∥∥∥ ≥ ( σ ρ1/2 )k (1− σ)M √ λmin(P ) ) .
Since P 1/2wk | x0:k ∼ N ( 0, P 1/2WkP 1/2 ) , and ‖Wk‖ ≤ W , applying Lemma 4, we have
P (∥∥∥P 1/2wk−1∥∥∥ ≥ (1− σ)M√λmin(P )∣∣∣x0:k) ≤ 2n/2 exp(− (1− σ)2M2λmin(P )
4 ‖Wk‖ ‖P‖ ) ≤ 2n/2 exp ( − (1− σ) 2M2
4W κ(P )
) . (15)
Noticing that the RHS of (15) does not depend on x0:k, we have P (∥∥∥P 1/2wk−1∥∥∥ ≥ (1− σ)M√λmin(P )) ≤ 2n/2 exp(− (1− σ)2M2
4W κ(P )
) .
Similarly, we have P (∥∥∥P 1/2wk−2∥∥∥ ≥ σ
ρ1/2 (1− σ)M
√ λmin(P ) ) ≤ exp ( − (1− σ) 2M2
4W κ(P ) · σ
2
ρ
) ,
...
P (∥∥∥P 1/2w0∥∥∥ ≥ ( σ ρ1/2 )k−1 (1− σ)M √ λmin(P ) ) ≤ exp ( − (1− σ) 2M2 4W κ(P ) · ( σ2 ρ )k−1) ,
P (∥∥∥P 1/2x0∥∥∥ ≥ ( σ ρ1/2 )k (1− σ)M √ λmin(P ) ) ≤ exp ( − (1− σ) 2M2 4W κ(P ) · ( σ2 ρ )k) .
Choose σ = ρ1/4, then σ2/ρ = ρ−1/2. Assuming w.l.o.g. that ρ ∈ (1/4, 1), we have σ2/ρ = ρ−1/2 ∈ (1, 2). When M ≥ √ 3W κ(P )/(1− ρ1/4), there is
2n/2 exp ( − (1− σ) 2M2
4W κ(P )
) < exp ( −3
4
) < 1
2 .
Applying Lemma 5 leads to the conclusion.
Lemma 7. For the system described in (10)-(11), assume there exists 0 < ρ < 1, P 0 andM > 0 such that A>k PAk ≺ ρP as long as ‖xk‖ ≥M . Let Vk = x>k Pxk, then
EVk < (M2A 2 + W ) ‖P‖
1− ρ , ∀k.
Proof. We first derive a recursive bound on EVk: from (10), we have Vk+1 = x > k+1Pxk+1 = x > k A > k PAkxk + 2w > k PAkxk + w > k Pwk. (16)
When ‖xk‖ < M , we have x>k A>k PAkxk ≤ M2A 2 ‖P‖. Otherwise, by A>k PAk ≺ ρP , we have x>k A > k PAkxk < ρx > k Pxk = ρVk. Therefore, in view of the fact that M
2A 2 ‖P‖ ≥ 0 and ρVk ≥ 0, we have
x>k A > k PAkxk ≤ max{M2A 2 ‖P‖ , ρVk ≥ 0} ≤M2A 2 ‖P‖+ ρVk, (17)
which holds for any k. Substituting (17) into (16), we have
Vk+1 ≤ ρVk + ηk + C, (18)
where ηk = 2w>k PAkxk + w > k Pwk, C = M 2A 2 ‖P‖. With such defined ηk, we have Eηk ≤ W ‖P‖ , (19)
where we noticed that E[w>k PAkxk] = E[E[w>k PAkxk | x0:k]] = E[E[wk | x0:k]>Akxk] = 0, and that E[w>k Pwk] = E[E[w>k Pwk | x0:k]] = E[tr(WkP )] ≤ W ‖P‖. Taking the expectation on both sides of (18), we have
EVk+1 ≤ ρEVk + (M2A 2 + W ) ‖P‖ . (20)
We can proceed using induction: we have
EV0 = E[x>0 Px0] = E[tr(W−1P )] ≤ W ‖P‖ < (M2A 2 + W ) ‖P‖
1− ρ .
Assuming EVk < (M 2A 2+W )‖P‖ 1−ρ , it follows from (20) that EVk+1 < (M2A 2+W )‖P‖
1−ρ , which concludes 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>k PAk ≺ ρP as long as ‖xk‖ ≥ M , and that Ak only depends on ‖xk‖. Let Vk = x > k Pxk, then
EV 2k < (M2A 2 + W ) ‖P‖2 (1− ρ)(1− ρ2) [ (1 + ρ)(M2A 2 + W ) + 4A 2W κ(P ) ] , ∀k.
Proof. From the inequality (18) in the proof of Lemma 7, we have
EV 2k+1 ≤ρ2EV 2k + Eη2k + C2 + 2ρE[Vkηk] + 2ρCEVk + 2CEηk, (21)
where ηk = 2w>k PAkxk + w > k Pwk, C = M 2A 2 ‖P‖. Let us bound Eηk,EVk,Eη2k,E[Vkηk] which appear in the RHS of (21) respectively:
• Eηk ≤ W ‖P‖ from (19) in the proof of Lemma 7.
• EVk < (C + W ‖P‖)/(1− ρ) according to the conclusion of Lemma 7.
• Eη2k = 4E[x>k A>k Pwkw>k PAkxk] + 4E[w>k PAkxkw>k Pwk] + E[w>k Pwkw>k Pwk] ≤ 4E ‖xk‖2 A 2W ‖P‖2 + W 2 ‖P‖2, where we noticed E[w>k PAkxkw>k Pwk] = E[E[w>k PAkxkw>k Pwk | xk]] = tr { E[AkxkE[w>k Pwkw>k P | xk]] } = 0 due to
symmetry. From Vk = x>k Pxk ≥ λmin(P ) ‖xk‖ 2, we can further deduce Eη2k ≤ 4A 2W ‖P‖κ(P )EVk + W 2 ‖P‖2.
• E[Vkηk] = 2E[w>k PAkVk] + E[Vkw>k Pwk] = 2E[E[w>k PAkxkVk | xk]] + E[E[vkw>k Pwk | xk]] = 2E[E[wk | xk]>PAkxkVk] + E[VkE[w>k Pwk | xk]] ≤ W ‖P‖EVk.
Substituting the above terms into the RHS of (21), we have
EV 2k+1 < ρ2EV 2k + ( 4A 2W ‖P‖κ(P ) + 2ρ(C + W ‖P‖) ) C + W ‖P‖ 1− ρ +
C2 + 2CW ‖P‖+ W 2 ‖P‖2
= ρ2EV 2k + C + W ‖P‖ 1− ρ [ (1 + ρ)(C + W ‖P‖) + 4A 2W ‖P‖κ(P ) ] . (22)
We can then proceed using induction: we have
EV 20 ≤ W 2 ‖P‖ 2 = (W ‖P‖)(W ‖P‖)
< C + W ‖P‖
1− ρ (C + W ‖P‖)
< C + W ‖P‖ (1− ρ)(1− ρ2) [ (1 + ρ)(C + W ‖P‖) + 4A 2W ‖P‖κ(P ) ] .
Assuming EVk < C+W ‖P‖(1−ρ)(1−ρ2) [ (1 + ρ)(C + W ‖P‖) + 4A 2W ‖P‖κ(P ) ] , we also have
EVk+1 < C+W ‖P‖(1−ρ)(1−ρ2) [ (1 + ρ)(C + W ‖P‖) + 4A 2W ‖P‖κ(P ) ] by (22). Therefore, we have
EVk < C + W ‖P‖ (1− ρ)(1− ρ2) [ (1 + ρ)(C + W ‖P‖) + 4A 2W ‖P‖κ(P ) ] = (M2A 2 + W ) ‖P‖2
(1− ρ)(1− ρ2) [ (1 + ρ)(M2A 2 + W ) + 4A 2W κ(P ) ] 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:
xk+1 = Axk +Buk + wk, (23)
We consider the following two classes of policies:
• Linear feedback policy: uk = πK(xk) = Kxk. • Safe switching policy: (uk, ξk+1) = π̄K,M,t(xk, ξk), whereM > 0 is the switching thresh-
old and t ∈ N∗ is the “non-action” duration, and π̄K,M,t determines uk, ξk+1 as follows: – If ξk > 0, then uk = 0, ξk+1 = ξk − 1;
– If ξk = 0,max{‖K‖, ‖xk‖} ≥M , then uk = 0, ξk+1 = t− 1; – If ξk = 0,max{‖K‖, ‖xk‖} < M , then uk = Kxk, ξk+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., πK = π̄K,+∞,1.
For the simplicity of expressions, when a safe switching policy π̄Kk,Mk,tk is applied at each step k, let us define the following notations:
i(0) = 0, i(k + 1) = { i(k) + 1 ui(k) 6= 0 i(k) + ti(k) ui(k) = 0 , x̃k = xi(k). (24)
In plain words, {x̃k} = {xi(k)} is the subsequence of {xk} where “non-action” steps are skipped. In addition, let
W = ∥∥∥ lim t→∞ W +AWA> + · · ·+AtW (At)> ∥∥∥ , (25)
which is a finite value since A is stable.
Lemma 9. For the system described in (23)-(25), assume a safe switching policy π̄Kk,Mk,tk is applied at each step k, Mk ≤ M for any k, and there exists 0 < ρ < 1 and P 0 such that A>PA ≺ ρP , then
E ‖xk‖4 < 8 [ Q(M,ρ, P ) + W 2κ(P )2 ] ,
where
Q(M,ρ, P ) = (M 2A 2 + W ) ‖P‖2 (1− ρ)(1− ρ2) [ (1 + ρ)(M2A 2 + W ) + 4A 2W κ(P ) ] ,
A = ‖A‖+ ‖B‖M.
Proof. According to (23) and (24), the state trajectory {x̃k} evolves subject to the dynamics
x̃k+1 = Akx̃k + w̃k, (26)
where
Ak = { A max{‖Kk‖ , ‖x̃k‖} ≥M A+BKk otherwise ,
w̃k | x̃k ∼ N (0,Wk) ,Wk = { W max{‖Kk‖ , ‖x̃k‖} ≥M W +AWA> + · · ·+AtkW (Atk)> otherwise .
Let Vk = x>k Pxk and Ṽk = x̃ > k Px̃k. Since A >PA ≺ ρP , the system (26) satisfies the assumption of Lemma 8, and ‖Wk‖ ≤ W , ‖Ak‖ ≤ ‖A‖+ ‖B‖M = A . Therefore, and therefore,
EṼ 2k < (M2A 2 + W ) ‖P‖2 (1− ρ)(1− ρ2) [ (1 + ρ)(M2A 2 + W ) + 4A 2W κ(P ) ] = Q(M,ρ, P )λmin(P )2.
(27)
Next, to establish the relationship between EṼ 2k and EV 2k , notice that
xk = A k−i(j)x̃j + w̃k, (28)
where j = sup{s ∈ N | i(s) ≤ k}, i.e., x̃j is the last state in {x̃k} that physically occurs no later than xk, and w̃k = ∑k−i(j)−2 l=0 A
k−i(j)−1−lwi(j)+l, Since A is stable, we have ‖E[w̃kw̃>k ]‖ ≤ W . Pre-multiplying both sides of (28) with P 1/2 and applying the triangle inequality, we have∥∥∥P 1/2xk∥∥∥ ≤ ∥∥∥P 1/2Ak−i(j)x̃j∥∥∥+ ∥∥∥P 1/2w̃k∥∥∥ .
Therefore, applying the power means inequality (a+b2 ) 4 ≤ a
4+b4
2 , we have V 2k = ∥∥∥P 1/2xk∥∥∥4 ≤ 8(∥∥∥P 1/2Ak−i(j)x̃j∥∥∥4 + ∥∥∥P 1/2w̃k∥∥∥4)
= 8 (( x̃>j ( Ak−i(j) )> PAk−i(j)x̃j )2 + ( w̃>k Pw̃k )2) ≤ 8 ( ρ2(k−i(j))Ṽ 2j + ( w̃>k Pw̃k )2) .
Taking the expectation on both sides of the above inequality and applying (27), we get EV 2k ≤ 8 [ Q(M,ρ, P )λmin(P )2 + W 2 ‖P‖2 ] .
Finally, using the fact that Vk = x>k Pxk ≥ λmin(P ) ‖xk‖ 2, we have
E ‖xk‖4 ≤ EV 2k
λmin(P )2 ≤ 8
[ Q(M,ρ, P ) + W 2κ(P )2 ] ,
which concludes our proof.
Lemma 10. For the system described in (23)-(25), assume K is a stabilizing linear feedback (i.e., ρ(A + BK) < 1) gain with ‖K‖ ≤ M , and there exists 0 < ρ < 1 and P 0 such that A>PA ≺ ρP, (A+BK)>P (A+BK) ≺ ρP . Let J be the cost (defined in (3)) associated with the linear feedback policy πK , and JM,t be the cost associated with the safe switching policy π̄K,M,t. Then
JM,t − J ≤ 2C1(ρ, P,K)G(M, t, ρ, P,K) + G(M, t, ρ, P,K)2, where
C1(ρ, P,K) =
( W κ(P ) ∥∥Q+K>RK∥∥ 1− ρ )1/2 ,
G(M, t, ρ, P,K) = C2(ρ,K)t [ Q(M,ρ, P ) + W 2κ(P )2 ]1/4 E(M,ρ, P ), C2(ρ,K) =
∥∥Q+K>RK∥∥ ‖BK‖ · ∞∑ s=0 ‖(A+BK)s‖ · 2 n/2+7/4 ρ−1/2 − 1 ,
(C2(ρ,K) <∞ because ρ(A+BK) < 1),
Q(M,ρ, P ) = (M 2A 2 + W ) ‖P‖2 (1− ρ)(1− ρ2) [ (1 + ρ)(M2A 2 + W ) + 4A 2W κ(P ) ] ,
E(M,ρ, P ) = exp ( − (1− ρ 1/4)2M2
4W κ(P )
) .
In particular, if the system specification A,B,Q,R,W , the stabilizing linear feedback gain K, and the parameters ρ, P are all fixed, we have
JM,t − J ∼ O ( tM exp(−cM2) ) as M →∞, t→∞, tM exp(−cM2)→ 0, where c = (1−ρ 1/4)2
4W κ(P ) .
Proof. Let {xk}, {uk} denote the state and input trajectories driven by πK , and {x̄k}, {ūk} denote the state and input trajectories driven by π̄K,M,t. Then from πK(x) = Kx and π̄K,M,t(x) ∈ {Kx, 0}, we have
J = lim T→∞
E
[ 1
T T−1∑ k=0 x>k (Q+K >RK)xk ] = lim T→∞ 1 T T−1∑ k=0 E [ x>k (Q+K >RK)xk ] ,
JM,t ≤ lim sup T→∞ E
[ 1
T T−1∑ k=0 x̄>k (Q+K >RK)x̄k
] = lim sup
T→∞
1
T T−1∑ k=0 E [ x̄>k (Q+K >RK)x̄k ] .
Therefore, we only need to prove E [ x̄>k (Q+K >RK)x̄k ] − E [ x>k (Q+K >RK)xk ] ≤
2C1(ρ, P,K)G(M, t, ρ, P,K) + G(M, t, ρ, P,K)2
for every k. Let Q̃ = Q + K>RK. Since Q 0 and R 0, we have Q̃ 0, and therefore ‖x‖Q̃ , √ x>Q̃x defines a norm. In the follows, we bound E ‖x̄k‖2Q̃ − E ‖xk‖ 2 Q̃.
We notice that
x̄k = (A+BK)x̄k−1 + wk−1 −BKx̄k−11{ūk−1=0} = (A+BK) [ (A+BK)x̄k−2 + wk−2 −BKx̄k−21{ūk−2=0} ] + wk−1−
BKx̄k−11{ūk−1=0}
= · · ·
= (A+BK)kx0 + k−1∑ s=0 (A+BK)swk−s−1 − k−1∑ s=0 (A+BK)sBKx̄k−s−11{ūk−s−1=0}
= xk − k−1∑ s=0 (A+BK)sBKx̄k−s−11{ūk−s−1}.
Hence,
‖x̄k‖Q̃ ≤ ‖xk‖Q̃ + k−1∑ s=0 ∥∥(A+BK)sBKx̄k−s−11{ūk−s−1}∥∥Q̃ ≤ ‖xk‖Q̃ +
∥∥∥Q̃∥∥∥ ‖BK‖ k−1∑ s=0 ‖(A+BK)s‖ ∥∥x̄k−s−11{ūk−s−1}∥∥ .
From the fact that E(X1 + · · · + Xn)2 ≤ (√ EX21 + · · ·+ √ EX2n )2 , where X1, . . . , Xn are
arbitrary random variables with bounded second-order moments, we have
E ‖x̄k‖2Q̃ ≤ (√ E ‖xk‖2Q̃ + ∥∥∥Q̃∥∥∥ ‖BK‖ k−1∑ s=0 ‖(A+BK)s‖ √ E [ ‖x̄k−s−1‖2 1{ūk−s−1=0} ])2 .
By Cauchy-Schwarz inequality, we have
E ‖x̄k‖2Q̃ ≤ (√ E ‖xk‖2Q̃ + ∥∥∥Q̃∥∥∥ ‖BK‖ k−1∑ s=0 ‖(A+BK)s‖ ( E ‖x̄k−s−1‖4 ) 1 4 P (ūk−s−1 = 0) )2 .
By Lemma 9, we have E ‖x̄k−s−1‖4 ≤ 8[Q(M,ρ, P ) + W 2κ(P )2] for any s, and hence, E ‖x̄k‖2Q̃ ≤ (√ E ‖xk‖2Q̃ + ∥∥∥Q̃∥∥∥ ‖BK‖ 23/4[Q(M,ρ, P ) + W 2κ(P )2]1/4
k−1∑ s=0 ‖(A+BK)s‖P (ūk−s−1 = 0)
)2 . (29)
According to the update rule of ξk in π̄K,M,t, we have
{ūk = 0} ⊆ t−1⋃ τ=0 {‖x̄k−t‖ ≥M} .
Taking the union bound, we have
P (ūk = 0) ≤ t−1∑ τ=0 P (‖x̄k−t‖ ≥M) .
By Lemma 6, we have
P (‖x̄k−t‖ ≥M) ≤ 2n/2+1
ρ−1/2 − 1 E(M,ρ, P )
for every k and t, and hence
P (ūk = 0) ≤ t 2n/2+1
ρ−1/2 − 1 E(M,ρ, P ) (30)
for every k. Substituting (30) into (29), we get E ‖x̄k‖2Q̃ ≤ (√ E ‖xk‖2Q̃ + ∥∥∥Q̃∥∥∥ ‖BK‖ 2n/2+7/4
ρ−1/2 − 1 [Q(M,ρ, P ) + W 2κ(P )2]1/4
k−1∑ s=0 ‖(A+BK)s‖ E(M,ρ, P )
)2
≤ (√
E ‖xk‖2Q̃ + C2(ρ,K)[Q(M,ρ, P ) + W 2κ(P )2]1/4E(M,ρ, P ) )2 = (√ E ‖xk‖2Q̃ + G(M, t, ρ, P,K)
)2 = E ‖xk‖2Q̃ + 2 √ E ‖xk‖2Q̃G(M, t, ρ, P,K) + G(M, t, ρ, P,K) 2.
Applying Lemma 7 with M = 0, we have
E[x>k Pxk] ≤ W ‖P‖ 1− ρ ,
and hence
E ‖xk‖2Q̃ ≤ ∥∥∥Q̃∥∥∥ ‖xk‖2 ≤ W κ(P ) ‖Q‖
1− ρ = C1(ρ, P,K)2.
Therefore,
E ‖x̄k‖2Q̃ − E ‖xk‖ 2 Q̃ ≤ 2C1(ρ, P,K)G(M, t, ρ, P,K) + G(M, t, ρ, P,K) 2,
and hence
JM,t − J ≤ 2C1(ρ, P,K)G(M, t, ρ, P,K) + G(M, t, ρ, P,K)2,
which concludes our proof.

heading: A.1.3 A LAW OF LARGE NUMBERS FOR MARTINGALES
text: Let {Fk} be a filtration of σ-algebras and {Sk} be a matrix-valued stochastic process adapted to {Fk}, we call {Sk} a matrix-valued martingale (with respect to the filtration {Fk}) if E[Sk+1 | Fk] = Sk holds for all k. Now we can state a law of large numbers for matrix-valued martingales: Lemma 11. (Liu et al., 2020, Lemma 4) If Sk = Φ0 + Φ1 + · · ·+ Φk is a matrix-valued martingale such that
E ‖Φk‖2 ∼ C(β),
where 0 ≤ β < 1, then Sk/k converges to 0 almost surely. Furthermore,
Sk k ∼ C
( β − 1
2
) .

heading: A.1.4 A PERTURBATION ANALYSIS OF ALGEBRAIC RICCATI EQUATION
text: An interesting property of LQR is that near the optimal controller (which corresponds to the solution of the discrete algebraic Riccati equation), the perturbation of the discrete Lyapunov equation solution is quadratic in the perturbation of controller gain. Basically, this results in the convergence speed of the certainty equivalent control performance being twice that of the estimation error. Similar results have been reported in (Mania et al., 2019; Simchowitz & Foster, 2020), and here we present a simplified version that would suffice for our purpose. Lemma 12. Consider the discrete Lyapunov equation
A>XA−X +Q = 0, where Q 0 and ρ(A) < 1, then the unique positive definite solution X satisfies
‖X‖F ≤ ∥∥∥(I −A> ⊗A>)−1∥∥∥
2 ‖Q‖F .
Proof. Vectorizing the Lyapunov equation, we get vec(X) = ( I −A> ⊗A> )−1 vec(Q),
and hence ‖X‖F = ‖vec(X)‖2 ≤ ∥∥∥(I −A> ⊗A>)−1∥∥∥
2 ‖vec(Q)‖2 = ∥∥∥(I −A> ⊗A>)−1∥∥∥ 2 ‖Q‖F .
Lemma 13. Let P be the solution to the discrete algebraic Riccati equation P = Q+A>PA−A>PB ( R+B>PB )−1 B>PA,
and let K be defined as
K = − ( R+B>PB )−1 B>PA.
Assume K̂ is such that Ã = A+BK̂ is stable, and P̂ satisfies the discrete Lyapunov equation
P̂ = Q+ K̂>RK̂ + Ã>P̂ Ã. (31)
Let ∆P = P̂ − P,∆K = K̂ −K, then ‖∆P‖F ≤ ∥∥∥∥(I − Ã> ⊗ Ã>)−1∥∥∥∥
2
‖R‖F ‖∆K‖ 2 F .
Proof. It can be shown P satisfies the discrete Lyapunov equation P = Q+K>RK + (A+BK)>P (A+BK). (32)
Meanwhile, substituting ∆P = P̂ − P,∆K = K̂ −K into (31), we get P + ∆P
= Q+ (K + ∆K) > R (K + ∆K) + (A+B (K + ∆K)) > (P + ∆P ) (A+B (K + ∆K))
= Q+K>RK + ∆K>R∆K + (A+BK)>P (A+BK) + Ã>∆PÃ, (33) where for the second equality we used the fact(
R+B>PB ) K +B>PA = 0.
By taking the difference between (33) and (32), we can see ∆P also satisfies a discrete Lyapunov equation:
∆P = ∆K>R∆K + Ã>∆PÃ.
Applying Lemma 12, we obtain ‖∆P‖F ≤ ∥∥∥∥(I − Ã> ⊗ Ã>)−1∥∥∥∥
2
∥∥∆K>R∆K∥∥ F
≤ ∥∥∥∥(I − Ã> ⊗ Ã>)−1∥∥∥∥
2
‖R‖F ‖∆K‖ 2 F ,
which concludes our proof.

heading: A.2 PROOF OF THEOREM 1
text: Proof. According to our definition of bounded-cost safety, we only need to prove Jπk < +∞ for every k, where Jπk is defined in (3).
Let {xi}, {ui} denote the state and input trajectories driven by πk. According to Algorithm 2, we have ui ∈ {K̂kxi, 0}, and therefore,
Jπk ≤ lim sup T→∞ E
[ 1
T T−1∑ i=0 x>i ( Q+ K̂>k RK̂k ) xi ] = lim sup T→∞ 1 T T−1∑ i=0 E [ x>i ( Q+ K̂>k RK̂k ) xi ] .
Notice that under πk, there is xi+1 = Axi +wi as long as ‖xi‖ ≥ log k, and since A is stable, there exists 0 < ρ < 1 and P 0 such that A>PA ≺ ρP . By Lemma 7, we have
E [ x>i Pxi ] <
((log k)2A 2 + ‖W‖) ‖P‖ 1− ρ ,
where A = max{‖A‖ , ‖A+BK̂k‖}. Therefore, by x>i Pxi ≥ λmin(P ) ‖xi‖ 2 and x>i ( Q+ K̂>k RK̂k ) xi ≤ ‖Q+ K̂>k RK̂k‖ ‖xi‖ 2, we have
E [ x>i ( Q+ K̂>k RK̂k ) xi ] < ((log k)2A 2 + ‖W‖)κ(P )‖Q+ K̂>k RK̂k‖ 1− ρ .
This implies
Jπk ≤ ((log k) 2A 2 + ‖W‖)κ(P )‖Q+ K̂>k RK̂k‖
1− ρ < +∞,
which concludes our proof.

heading: A.3 PROOF OF THEOREM 2
text: Proof. We shall assume throughout the proof that {Fk} is the σ-algebra generated by the random variables {x0, w0, . . . , wk, ζ0, . . . , ζk}. We first cast the system (1) into a static form by writing xk as
xk = A kx0 + k−1∑ t=0 AtBuk−t−1 + k−1∑ t=0 Atwk−t−1
= Akx0 + k−1∑ t=0 Ht [ ũk−t−1 + (k − t)−βζk−t−1 ] + k−1∑ t=0 Atwk−t−1. (34)
In order to estimate Hτ , post-multiply both sides of (34) with ζ>k−τ−1 and rearrange the terms, and we get
xkζ > k−τ−1 = ( k−1∑ t=0 Atwk−t−1 +A kx0 ) ζ>k−τ−1 + k−1∑ t=0 (k − t)−βHtζk−t−1ζ>k−τ−1+
k−1∑ t=0 Htũk−t−1ζ > k−τ−1. (35)
To take the expectation of (35), notice that for any time step k, the variables x0, ζ0, ζ1, . . . , ζk, w0, w1, . . . , wk, ũ0, ũ1, . . . , ũk+1 are measurable w.r.t. Fk, which, together with the independence among x0, ζ0, ζ1, . . . , ζk, w0, w1, . . . , wk, leads to the following relations:
E [ ζk1ζ > k2 | Fk2−1 ] = { I if k1 = k2 0 otherwise,
(36)
E [ ũk1ζ > k2 | Fk2−1 ] = { 0 if k1 ≤ k2 other values otherwise,
(37)
E [ wk1ζ > k2 | Fk2−1 ] = 0, (38)
E [ x0ζ > k2 | Fk2−1 ] = 0, (39)
for any two time steps k1 ≥ 0 and k2 ≥ 1. Now let us prove the conclusion using induction on τ .
First consider the case τ = 0: we have
Ĥk,0 −H0 = 1
k k∑ i=1 [ (i+ 1)βxiζ > i−1 −H0 ] = 1 k k−1∑ i=0 [ (i+ 2)βxi+1ζ > i −H0 ] . (40)
Let Φk = (k + 1)βxk+1ζ>k − H0. By substituting (35) and (36) to (39) into (40) it can be seen E[Φk | Fk−1] = 0, and hence Sk , ∑k i=0 Φi is a martingale w.r.t. {Fk}. Furthermore, we can verify E ‖Φk‖2 ∼ C(2β): by Cauchy-Schwarz inequality,
E ∥∥(k + 1)βxk+1ζ>k ∥∥2 ≤ (k + 1)2β√E ‖xk+1‖4√E ‖ζk‖4.
By the procedure described in Algorithm 2, the switching threshold is no larger than log k for every step before k, and therefore, according to Lemma 9,
E ‖xk‖4 < 8 [ Q(log k, ρ, P ) + W 2κ(P )2 ] ∼ O ( (log k)8 ) ∼ C(0),
where 0 < ρ < 1 and P 0 are constants such that A>PA ≺ ρP , 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 ‖ζk‖4 = p(p+ 2) ∼ C(0), we have
E ∥∥(k + 1)βxk+1ζ>k ∥∥2 ∼ C(2β),
and hence, E ‖Φk‖2 = E ∥∥(k + 1)βxk+1ζ>k −H0∥∥2 ≤ E (∥∥(k + 1)βxk+1ζ>k ∥∥+ ‖H0‖)2
≤ 2 ( E ∥∥(k + 1)βxk+1ζ>k ∥∥2 + ‖H0‖2) ∼ C(2β).
By applying Lemma 11 to the martingale {Sk} defined above, we get Ĥk,0 −H0 ∼ C ( β − 1
2
) .
Now assume that τ ≥ 1 and that we already have Ĥk,t −Ht ∼ C ( β − 1
2
) (41)
for t = 0, 1, . . . , τ − 1. Then
Ĥk,τ −Hk,τ
= 1
k − τ k∑ i=τ+1
{ (i− τ)β [ xi −
τ−1∑ t=0 Ĥk,tũi−t−1 ] ζ>i−τ−1 −Hk,τ }
= 1
k − τ k−τ−1∑ i=0
{ (i+ 1)β [ xi+τ+1 −
τ−1∑ t=0 Ĥk,tũi+τ−t ] ζ>i −Hk,τ }
= 1
k − τ k−τ−1∑ i=0
{ (i+ 1)β [ xi+τ+1 −
τ−1∑ t=0 Htũi+τ−t ] ζ>i −Hk,τ } −
τ−1∑ t=0 ( Ĥk,t −Ht ) 1 k − τ k−τ−1∑ i=0 (i+ 1)β ũi+τ−tζ > i . (42)
Completely similarly to the case τ = 0, we can show
1
k − τ k−τ−1∑ i=0
{ (i+ 1)β [ xi+τ+1 −
τ−1∑ t=0 Htũi+τ−t ] ζ>i −Hk,τ } ∼ C ( β − 1 2 ) .
Meanwhile, for each of t = 0, 1, . . . , τ − 1, define Φtk = (k+ 1)β ũk−tζ>k . In view of (37) it can be shown E[Φtk | Fk−1] = 0, and hence Stk , ∑k i=0 Φ t k is a martingale w.r.t. {Fk}. Furthermore, by the procedure described in Algorithm 2, ‖ũk−t‖2 ≤ (log(k − t))4 ≤ (log k)4, we have
E ∥∥Φtk∥∥2 ≤ (k + 1)2β (log k)4 E ‖ζk‖2 ∼ C(2β).
By applying Lemma 11 to the martingale Stk defined above, we get
1
k − τ k−τ−1∑ i=0 (i+ 1)β ũi+τ−tζ > i ∼ C ( β − 1 2 ) ,
which together with (41) implies( Ĥk,t −Ht ) 1 k − τ k−τ−1∑ i=0 (i+ 1)β ũi+τ−tζ > i ∼ C ( 2 ( β − 1 2 )) ∼ C ( β − 1 2 ) .
Now that we have shown the RHS of (42) is the sum of τ + 1 matrices, each of order C ( β − 12 ) , we get
Ĥk,τ −Hk,τ ∼ C ( β − 1
2
) .
According to our definition of C(α), this is to say it holds almost surely that
lim k→∞ Ĥk,τ −Hτ k−γ+ = 0,
where γ = 1/2− β > 0, for any > 0, which concludes our proof.

heading: A.4 PROOF OF THEOREM 3
text: Let us denote by JπW the cost of a policy π when acting on a system in the form (1) with process noise covariance W . Let us consider the following variants of policies:
• π∗: optimal policy, i.e., π∗(x) = K∗x, with K∗ defined in (6). • π̂k: certainty equivalent policy with no exploratory noise, i.e., π̂k(x) = K̂kx. • π̃k: safe switching policy with no exploratory noise, i.e., Algorithm 2 invoked as π(x, ξ; k, K̂k,+∞). • πk: safe switching policy with exploratory noise, i.e., the actually applied policy at step k.
Notice that Jπk = JπkW and J ∗ = Jπ
∗
W . Our plan is decomposing J πk − J∗ as Jπk − J∗ = ( JπkW − J π̃k W+(k+1)−2βI ) + ( J π̃k W+(k+1)−2βI − J π̂k W+(k+1)−2βI ) +(
J π̂k W+(k+1)−2βI − J π̂kW ) + ( J π̂kW − J π∗ W ) ,
and bounding the RHS terms respectively. We next tackle these terms in reverse order:
1. J π̂kW − Jπ ∗
W : for an arbitrary stabilizing linear feedback policy π(x) = Kx, we know the cost is JπW = tr(WP ), where P solves the discrete Lyapunov equation (32). By Theorem 2, the Markov parameter estimates converge as C(−γ). Since with random input
in Algorithm 3, the matrix [ Uh X h0 ] is full row rank, it follows that the pseudo-inverse operator is differentiable, which together with Lemma 2 guarantees that Âk−A, B̂k−B ∼ C(−γ). Due to the differentiability of the stabilizing solution of the discrete algebraic equation, there is also K̂k − K∗ ∼ C(−γ). In particular, {K̂k} converges to K∗ almost surely, and since K∗ is stabilizing, we have for almost every realization of randomness, K̂k is also stabilizing for sufficiently large k. Assuming w.l.o.g. that K̂k is stabilizng for any
k, we have J π̂kW − Jπ ∗ W = tr(W (Pk − P ∗)), where P ∗ is the Lyapunov equation solution corresponding to K∗, also the solution to the Riccati equation (5), and Pk is the Lyapunov equation solution corresponding to K̂k. According to Lemma 13, we have
‖Pk − P ∗‖F ≤ ∥∥∥∥(I − Ã>k ⊗ Ã>k )−1∥∥∥∥
2
‖R‖F ∥∥∥K̂k −K∗∥∥∥2
F ,
where Ãk = A + BK̂k. Since every Ãk is stable, we have ∥∥∥∥(I − Ã>k ⊗ Ã>k )−1∥∥∥∥
2
is
a continuous function of Ãk. Meanwhile, {Ãk} converges to A + BK∗, which implies∥∥∥∥(I − Ã>k ⊗ Ã>k )−1∥∥∥∥ 2 is bounded. Hence, K̂k − K∗ ∼ C(−γ) implies Pk − P ∗ ∼ C(−2γ). Finally, we have J π̂kW − Jπ ∗ W = tr(W (Pk − P ∗)) ∼ C(−2γ).
2. J π̂k W+(k+1)−2βI − J π̂kW : from J π̂k W = tr(WPk), with Pk defined the same as above, we have
J π̂k W+(k+1)−2βI − J π̂kW = tr((k + 1)−2βPk). Since {Pk} converges to P ∗ 0, we have J π̂k W+(k+1)−2βI − J π̂kW ∼ C(−2β).
3. J π̃k W+(k+1)−2βI − J π̂k W+(k+1)−2βI : we can basically apply Lemma 10. To verify the conditions of Lemma 10, we first fix ρ, P : since A + BK∗ is stable, for any fixed Q 0, the discrete Lyapunov equation (A + BK∗)>P (A + BK∗) + Q = P has a solution P 0. Therefore, there exists P 0, 0 < ρ < 1, such that (A + BK∗)>P (A + BK∗) < ρP . Since {K̂k} converges to K∗ almost surely, we may assume w.l.o.g. that (A + BK̂k)>P (A + BK̂k) < ρP for any k. Furthermore, since A is stable, there is At → 0 as t → ∞, and therefore, with t = blog kc sufficiently large, we also have (At)> PAt < ρP . 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 are all fixed, we can apply the conclusion of Lemma 10 by taking the limit K̂k → K∗ to obtain J π̃k
W+(k+1)−2βI − J π̂k W+(k+1)−2βI ∼ O((log k)2 exp(−c(log k)2)) ∼ C(−∞).
4. JπkW −J π̃k W+(k+1)−2βI : these two costs are associated with the same closed-loop system and
differ only in the u>k Ruk terms. In particular, J πk W −J π̃k W+(k+1)−2βI = tr((k+ 1)−2βR) ∼ C(−2β).
Adding up the above four terms using Lemma 2, we obtain Jπk−J∗ ∼ C(max{−2β,−2γ,−∞}) ∼ C(−min{2β, 2γ}). According to our definition of C(α), this is to say it holds almost surely that
lim k→∞
Jπk − J∗
k−min{2β,2γ}+ = 0,
for any > 0, which concludes our proof.

heading: B AN ILLUSTRATION OF OSCILLATION UNDER SWITCHING
text: In this section, we provide a simple illustrative example to explain why we need prolonging “nonaction” period in Algorithm 2.
Consider a simple two-dimensional noise-free system
xk+1 = Akxk,
where the candidates for Ak are
A0 = [ 0.5 2 0 0.5 ] , A1 = [ 0.5 0 2 0.5 ] .
It can be seen ρ(A0) = ρ(A1) = 0.5, i.e., both the system matrices are stable.
Now consider the following switching strategy:
• If ‖xk‖ ≥M , then apply A0 for t consecutive steps. • Otherwise, apply A1.
Figure 4 shows simulation results with x0 = (0.1, 1),M = 1 and t = 1, 2. We can observe that even for this simple system, the frequent switching caused by t = 1 may cause the state to oscillate, while t = 2 suffices to suppress the oscillation. Indeed, we can verify ρ(A1A0) ≈ 4.5 > 1 even though both A0 and A1 are stable. However, as long as A0 is stable, A1At0 will eventually become stable as t is chosen to be sufficiently large. This explains why we use prolonging t in our policy.

Review summaries:
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. 

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.

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.