Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret

Introduction

Optimal control theory dates back to the 1950s, and has been applied successfully to numerous real-world engineering problems (e.g., Bermúdez and Martinez, 1994; Chen and Islam, 2005; Lenhart and Workman, 2007; Geering, 2007). Classical results in control theory pertain to asymptotic convergence and stability of dynamical systems, and recently, there has been a renewed interest in such problems from a learning-theoretic perspective with a focus on finite-time convergence guarantees and computational tractability.

Perhaps the most well-studied model in optimal control is Linear-Quadratic (LQ) control. In this model, both the state and the action are real-valued vectors. The dynamics of the environment are linear in both the state and action, and are perturbed by Gaussian noise; the cost is quadratic in the state and action vectors. When the costs and dynamics are known, the optimal control policy, which minimizes the steady-state cost, selects its actions as a linear function of the state vector, and can be derived by solving the algebraic Ricatti equations (e.g., Bertsekas et al., 2005).

Among the most challenging problems in LQ control is that of adaptive control: regulating a system with parameters which are initially unknown and have to be learned while incurring the associated costs. This problem is exceptionally challenging since the system might become unstable. Specifically, the controller must control the magnitude of the state vectors; otherwise, its cost might grow arbitrarily large.

Abbasi-Yadkori and Szepesvári (2011) were the first to address the adaptive control problem from a learning-theoretic perspective. In their setting, there is a learning agent who knows the quadratic costs, yet has no knowledge regarding the dynamics of the system. The agent acts for $T$ rounds; at each round she observes the current state then chooses an action. Her goal is to minimize her regret, defined as the difference between her total cost and $T$ times the steady-state cost of the optimal policy—one that is computed using complete knowledge of the dynamics.

Abbasi-Yadkori and Szepesvári (2011) gave $O(\sqrt{T})$-type regret bounds for LQ control where the dependency on the dimensionality is exponential, which was later improved by Ibrahimi et al. (2012) to a polynomial dependence. However, the algorithms given in these works are not computationally efficient and require solving a complex non-convex optimization problem at each step. Developing an efficient algorithm with $O(\sqrt{T})$ regret has been a long standing open problem. Recently, Dean et al. (2018) proposed a computationally-efficient algorithm attaining an $O(T^{2/3})$ regret bound, and stated as an open problem providing an $O(\sqrt{T})$ regret efficient algorithm.

In this paper, we give the first computationally-efficient algorithm that attains $\smash{\widetilde{O}}(\sqrt{T})$ regret for learning LQ systems, thus resolving the open problem of Abbasi-Yadkori and Szepesvári (2011) and Dean et al. (2018). The key to the efficiency of our algorithm is in reformulating the LQ control problem as a convex semi-definite program. Our algorithm solves a sequence of semi-definite relaxations of the infinite horizon LQ problem, the solutions of which are used to compute “optimistic” policies for the underlying unknown LQ system. As time progresses and the algorithm receives more samples from the system, these relaxations become tighter and serve as a better approximation of the actual LQ system. In this context, an optimistic policy is one that balances between exploration and exploitation; that is, between myopically utilizing its current information about the system parameters versus collecting new samples in order to obtain better estimates for subsequent predictions.

The techniques used in Abbasi-Yadkori and Szepesvári (2011); Ibrahimi et al. (2012) as well as those in this paper, draw inspiration from the UCRL algorithm (Jaksch et al., 2010) for learning in unknown Markov Decision Processes (MDPs). The main methodology is that of “optimism in the face of uncertainty” that has been highly influential in the reinforcement learning literature (Lai and Robbins, 1985; Brafman and Tennenholtz, 2002).

Over the years, techniques from reinforcement learning have been applied extensively in control theory. In particular, many recent works were published on the topic of learning LQ systems; these are Abbasi-Yadkori and Szepesvári (2011); Ibrahimi et al. (2012); Faradonbeh et al. (2017); Abbasi-Yadkori et al. (2018); Arora et al. (2018); Fazel et al. (2018); Malik et al. (2018) to name a few.

It is also worth noting an orthogonal line of works that attempts to adaptively control LQ systems using Thompson sampling, most notably Abeille and Lazaric (2017); Ouyang et al. (2017); Abeille and Lazaric (2018). Unfortunately, these works are also concerned with the statistical aspects of the problem, and none of them present computationally-efficient algorithms.

Preliminaries

The following notation will be used throughout the paper. We use $\|\cdot\|$ to denote the operator norm, that is, $\|M\|=\max_{x:\|x\|=1}\|Mx\|$ is the maximum singular value of a matrix $M$, and $\|\cdot\|_{*}$ to denote the trace norm, $\|M\|_{*}=\operatorname*{Tr}(\sqrt{M^{\mkern-1.5mu\scriptstyle\mathsf{T}}M})$. The notation $\rho(M)$ refers to the spectral radius of a matrix $M$, i.e., $\rho(M)$ is the largest absolute value of its eigenvalues.Note that for a non-symmetric matrix $M$ (as would often be the case in the sequel), the spectral radius can be very different from the operator norm of $M$. In particular, it could be the case that $\rho(M)<1$ yet $\|M\|\gg 1$. Finally, we use the $A\bullet B$ to denote the entry-wise dot product between matrices, namely $A\bullet B=\operatorname*{Tr}(A^{\mkern-1.5mu\scriptstyle\mathsf{T}}B)$.

1 Problem Setting and Background

Furthermore, the optimal steady-state cost $J^{\star}$ equals $P^{\star}\bullet W$.

Problem definition.

We henceforth consider a learning setting in which the learner is uninformed about the dynamics of the system. Namely, the matrices $A_{\star}$ and $B_{\star}$ in Eq. 1 are fixed but unknown to the learner. For simplicity, we assume that the cost matrices $Q$ and $R$ are fixed and known; a straightforward yet technical adaptation of our approach can handle uncertainties in these matrices as well.

A learning algorithm is a mapping from the current state $x_{t}$ and previous observations $\{x_{s},u_{s}\}_{s=1}^{t-1}$ to an action $u_{t}$ at time $t$. An algorithm is measured by its $T$-round regret, defined as the difference between its total cost over $T$ rounds and $T$ times the steady-state cost of the optimal policy which knows both $A_{\star}$ and $B_{\star}$. That is,

where $u_{1},\ldots,u_{T}$ are the actions chosen by the algorithm and $x_{1},\ldots,x_{T}$ are the resulting states.

Our assumptions.

We make the following assumptions about the LQ system (1):

there are known positive constants $\alpha_{0},\alpha_{1},\sigma,\vartheta,\nu>0$ such that

Assumption (i) is rather mild and only requires having upper and lower bounds on the unknown system parameters. We remark that the assumption $W=\sigma^{2}I$ is made only for simplicity, and in fact, our analysis only requires upper and lower bounds on the eigenvalues of $W$. Assumption (ii), which has already appeared in the context of learning in LQRs (Dean et al., 2018), is also not very restrictive. In realistic systems, it is reasonable that one knows how to “reset” the dynamics and prevent them from reaching unbounded states. Further, in many cases a stabilizing policy can be found efficiently (Dean et al., 2017).

2 SDP Formulation of LQR

A key step in our approach towards the design of an efficient learning algorithm is in reformulating the planning problem in LQRs as a convex optimization problem. To this end, we make use of a semidefinite formulation introduced in Cohen et al. (2018) that would allow us to find the optimal cost of the LQ system (1):

Here, $\Sigma$ is an $n\times n$ PSD matrix, with $n=d+k$, that has the following block structure:

Let $\Sigma$ be any feasible solution to the SDP (4), and let $K=\mathcal{K}(\Sigma)$. Then the policy $\pi(x)=Kx$ is stable for the LQR (1), and it holds that $\mathcal{E}(K)\preceq\Sigma$. In particular, $\mathcal{E}(K)$ is also feasible for the SDP and its cost is at most that of $\Sigma$.

3 Strong Stability

The quadratic cost function is unbounded. Indeed, it might be that the norms of the state vectors $x_{1},x_{2},\ldots$ grow exponentially fast resulting in poor regret for the learner.

To alleviate this issue we rely on the notion of a strongly-stable policy, introduced by Cohen et al. (2018). Intuitively, strongly-stable policies are ones in which the norms of the state vectors remain controlled.

A matrix $M$ is $(\kappa,\gamma)$-strongly stable (for $\kappa\geq 1$ and $0<\gamma\leq 1$) if there exists matrices $H\succ 0$ and $L$ such that $M=HLH^{-1}$, with $\|L\|\leq 1-\gamma$ and $\|H\|\|H^{-1}\|\leq\kappa$.

A policy $K$ for the linear system (1) is $(\kappa,\gamma)$-strongly stable (for $\kappa\geq 1$ and $0<\gamma\leq 1$) if $\|K\|\leq\kappa$ and the matrix $A_{\star}+B_{\star}K$ is $(\kappa,\gamma)$-strongly stable.

We note that, in particular, any stable policy $K$ is in fact $(\kappa,\gamma)$-strongly stable for some $\kappa,\gamma>0$ (see Cohen et al., 2018 for a proof). Our analysis requires a stronger notion that pertains to the stability of a sequence of policies, also borrowed from Cohen et al. (2018).

A sequence of policies $K_{1},K_{2},\ldots$ for the linear dynamics in Eq. 1 is $(\kappa,\gamma)$-strongly stable (for $\kappa>0$ and $0<\gamma\leq 1$) if there exist matrices $H_{1},H_{2},\ldots\succ 0$ and $L_{1},L_{2},\ldots$ such that $A_{\star}+B_{\star}K_{t}=H_{t}L_{t}H_{t}^{-1}$ for all $t$, with the following properties:

$\|L_{t}\|\leq 1-\gamma$ and $\|K_{t}\|\leq\kappa$;

$\|H_{t}\|\leq B_{0}$ and $\|H_{t}^{-1}\|\leq 1/b_{0}$ with $\kappa=B_{0}/b_{0}$;

For a sequentially strongly stable sequence of policies one can show that the expected magnitude of the state vectors remains controlled; for completeness, we include a proof in Section A.3.

Let $x_{1},x_{2},\ldots$ be a sequence of states starting from a deterministic state $x_{1}$, and generated by the dynamics in Eq. 1 following a $(\kappa,\gamma)$-strongly stable sequence of policies $K_{1},K_{2},\ldots$. Then, for all $t\geq 1$ we have

Efficient Algorithm for Learning in LQRs

In this section we describe our efficient online algorithm for learning in LQRs; see pseudo-code in Algorithm 1. The algorithm receives as input the parameters $\alpha_{0}$, $\nu$, $\sigma^{2}$ and $\vartheta$, further requires an initial estimate $\mathopen{}\left(A_{0}\,B_{0}\right)$ that approximates the true parameters $\mathopen{}\left(A_{\star}\,B_{\star}\right)$ within an error $\epsilon$. As we later show, this estimate only needs to be accurate to within $\epsilon=O(1/\sqrt{T})$ of the true parameters, and we can make sure this is satisfied by employing a known stabilizing policy $K_{0}$ for exploration over $O(\sqrt{T})$ rounds.

We next describe in detail the main steps of the algorithm. The algorithm maintains estimates $\mathopen{}\left(A_{t}\,B_{t}\right)$ of the true parameters $\mathopen{}\left(A_{\star}\,B_{\star}\right)$ that improve from round to round, as well as a PD matrix $V_{t}\succ 0$ that represents a confidence ellipsoid around the current estimates $\mathopen{}\left(A_{t}\,B_{t}\right)$. The algorithm proceeds in epochs, each starting whenever the volume of the ellipsoid is halved and consists of the following steps.

The first step of each epoch is standard: we employ a least-squares estimator (in 7) to construct a new approximation $(A_{t}\,B_{t})$ of the parameters $(A_{\star}\,B_{\star})$ based on the observations $z_{t}$ collected so far. The confidence bounds of this estimator are given in terms of the covariance matrix $V_{t}$ of the vectors $z_{1},\ldots,z_{t-1}$.

2 Computing a policy via an SDP

The main step of the algorithm takes place in line 8 of Algorithm 1, where we form a “relaxed” SDP program based on the current estimates $(A_{t}\,B_{t})$ and the corresponding confidence matrix $V_{t}$, and solve it in order to compute a stable policy for the underlying LQR system. The idea here is to adapt the SDP formulation (4) of the LQR system, whose description needs the true underlying parameters, to an SDP program that only relies on estimates of the true parameters and accounts for the uncertainty associated with them. Once the relaxed SDP is solved, extracting a (deterministic) policy $K_{t}$ from the solution $\Sigma_{t}$ is done in the same way as in the case of the exact SDP (4).

The relaxed SDP incorporates a relaxed form of the inequality constraint in (4); as we show in the analysis, this program is a relaxation of the “exact” SDP (4) provided that the estimates $(A_{t}\,B_{t})$ are sufficiently accurate (this is one place where having fairly accurate initial estimates as input to the algorithm is useful). In other words, the relaxed SDP always underestimates the steady-state cost of the optimal policy of the LQR (1). In this sense, Algorithm 1 is “optimistic in the face of uncertainty” (e.g., Brafman and Tennenholtz, 2002; Jaksch et al., 2010).

3 Exploring, exploiting, and updating confidence

After retrieving a policy $K_{t}$, the algorithm takes action: it computes $u_{t}=K_{t}x_{t}$, which is the action recommended by policy $K_{t}$ at state $x_{t}$, and then plays $u_{t}$ and updates the confidence matrix $V_{t}$ with the new observations at step $t$. The policy $K_{t}$ therefore serves and balances two goals—exploitation and exploration—as it is used both as a “best guess” to the optimal policy (based on past observations), as well as means to collect new samples and obtain better estimates of the system parameters in subsequent steps of the algorithm.

Overview of Analysis

We now formally state our main result: a high-probability $\smash{\widetilde{O}}(\sqrt{T})$ regret bound for the efficient algorithm given in Algorithm 1.

Suppose that Algorithm 1 is initialized so that the initial estimation error $\|(A_{0}\,B_{0})-(A_{\star}\,B_{\star})\|_{\mathsf{F}}^{2}\leq\epsilon$ satisfies

Furthermore, the run-time per round of the procedure is polynomial in these factors.

At first glance it may appear that the regret bound of Theorem 4 becomes worse as the noise variance $\sigma^{2}$ becomes smaller. This seems highly counter-intuitive and, indeed, is not true in general. This is because when $\sigma$ is small we also expect the bound on the optimal loss $\nu$ to be small. In particular, suppose that $K_{\star}$ is $(\kappa_{\star},\gamma_{\star})$-strongly stable; then, one can show that $J^{\star}\leq\sigma^{2}\alpha_{1}\kappa_{\star}^{2}/\gamma_{\star}$. Plugging this as $\nu$ into the bound of Theorem 4 reveals a linear dependence in $\sigma^{2}$.

In Section 6 we show how to set up the initial conditions of Theorem 4; we utilize a stable (but otherwise arbitrary) policy given as input and show the following.

rounds; thereafter, we run Algorithm 1. Then, the initial conditions of Theorem 4 hold by the end of the warm-up phase, and with probability at least $1-\delta$ the regret of the overall procedure is bounded as

Furthermore, the runtime per round of the procedure is polynomial in these factors and in $T,\log(1/\delta)$.

In the remainder of the section, we give an overview of the main steps in the analysis, delegating the technical proofs to later sections and appendices.

Algorithm 1 repeatedly computes least-square estimates of $\mathopen{}\left(A_{\star}\;B_{\star}\right)$. The next theorem, similar to one shown in Abbasi-Yadkori and Szepesvári (2011), yields a high-probability bound on the error of this least-squares estimate.

Let $\Delta_{t}=\mathopen{}\left(A_{t}\,B_{t}\right)-\mathopen{}\left(A_{\star}\,B_{\star}\right)$. For any $\delta\in(0,1)$, with probability at least $1-\delta$,

In particular, when $\|\Delta_{0}\|_{\mathsf{F}}^{2}\leq 1/(4\lambda)$ and $\sum_{s=1}^{t}\|z_{s}\|^{2}\leq 2\beta T$, one has $\operatorname*{Tr}(\Delta_{t}V_{t}\Delta_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}})\leq 1$.

We see that the boundness of the states $z_{t}$ (specifically, the fact that they do not grow exponentially with $t$) is crucial for the estimation. Below, we will show how the policies computed by the algorithm ensure this condition.

The proof of Lemma 6 is based on a self-normalized martingale concentration inequality due to Abbasi-Yadkori et al. (2011); for completeness, we include a proof in Section B.3.

2 Policy computation via a relaxed SDP

Next, assume that the estimates $A_{t},B_{t}$ of $A_{\star},B_{\star}$ computed in the previous step are indeed such that the error $\Delta_{t}=(A_{t}\,B_{t})-(A_{\star}\,B_{\star})$ has $\operatorname*{Tr}(\Delta_{t}V_{t}\Delta_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}})\leq 1$ for the confidence matrix $V_{t}=\lambda I+\beta^{-1}\sum_{s=1}^{t-1}z_{s}z_{s}^{\mkern-1.5mu\scriptstyle\mathsf{T}}$.

Consider the relaxed SDP program solved by the algorithm in 8. The following lemma follows from the optimality conditions of the SDP and will be used to extract a stable policy from the SDP solution, and to relate the cost of actions taken by this policy to properties of the SDP solutions. This lemma, together with Lemma 9 below, summarize the key consequences of the relaxed SDP formulation that central to our approach; we elaborate more on the relaxed SDP and its properties in Section 5 below.

Assume the conditions of Theorem 4, and further that $\|V_{t}\|\leq 4T$. Then the SDP solved in 8 of the algorithm is a relaxation of the exact SDP (4), and we have:

the value of the optimal solution is at most $J^{\star}\leq\nu$ which implies $\|\Sigma_{t}\|_{*}\leq J^{\star}/\alpha_{0}$;

$(\Sigma_{t})_{xx}$ is invertible and so the policy $K_{t}=(\Sigma_{t})_{ux}(\Sigma_{t})_{xx}^{-1}$ is well defined;

there exists a positive semi-definite matrix $P_{t}\succeq 0$ with $\|P_{t}\|_{*}\leq J^{\star}/\sigma^{2}$ such that

The positive definite matrix $P_{t}$ in the above lemma is in fact the dual variable corresponding to the optimal solution $\Sigma_{t}$ of the (primal) SDP, and the equality involving $P_{t}$ follows from the complementary slackness conditions of the SDP. This equality can be viewed as an approximate version of the Ricatti equation that applies to policies computed based on estimates of the system parameters (as opposed to the “exact” Ricatti equation, which is relevant only for optimal policies of the actual LQR, that can only be computed based on the true parameters).

3 Boundness of states

Next, we show that the policies computed by the algorithm keep the underlying system stable, and that state vectors visited by the algorithm are uniformly bounded with high probability. To this end, consider the following sequence of “good events” $\mathcal{E}_{1}\supseteq\mathcal{E}_{2}\supseteq\cdots\supseteq\mathcal{E}_{T}$, where for each $t$,

That is, $\mathcal{E}_{t}$ is the event on which everything worked as planned up to round $t$: our estimations were sufficiently accurate and the norms of $\{z_{s}\}_{s=1}^{t}$ were properly bounded. We show that the events $\mathcal{E}_{1},\ldots,\mathcal{E}_{T}$ hold with high probability; this would ensure that $V_{t}$ is appropriately bounded.

Under the conditions of Theorem 4, the event $\mathcal{E}_{T}$ occurs with probability $\geq 1-\delta/2$.

4 Sequential strong stability

Crucially, Lemma 8 above holds true since the sequence of policies extracted by Algorithm 1 from repeated solutions to the relaxed SDP is sequentially strongly stable.

Assume the conditions of Theorem 4, and further that for any $t$, $\|V_{s}\|\leq 4T$ for all $s=1,\ldots,t$. Then the sequence of policies $K_{1},\ldots,K_{t}$ is $(\kappa,\gamma)$-strongly stable for $\kappa=\sqrt{2\nu/\alpha_{0}\sigma^{2}}$ and $\gamma=1/2\kappa^{2}$.

This follows from a stability property of solutions to the relaxed SDP: we show that as the relaxed constraint becomes tighter, the optimal solutions of the SDP do not change by much (see Section 5). This, in turn, can be used to show that the policies extracted from these solutions are not drastically different from each other, and so the sequence of policies generated by the algorithm keeps the system stable. Lemma 8 is then implied via a simple inductive argument: suppose that the state-vector norms are bounded up until round $t$; then the sequence of policies generated until time $t$ is strongly-stable thus keeping the norms of future states bounded with high probability.

We remark that stability of the individual policies does not suffice, and the stronger sequential strong stability condition is in fact required for our analysis. Indeed, even if we guarantee the (non-sequential) strong stability of each individual policy, the system’s state might blow up exponentially in the number of times the algorithm switches between policies: after switching to a new policy there is an initial burn-in period in which the norm of the state can increase by a constant factor (and thereafter stabilize). Thus, even if we ensure that there are as few as $O(\log{T})$ policy switches, the states might become polynomially large in $T$ and deteriorate our regret guarantee. Sequential strong stability wards off against such a blow up in the magnitude of states.

5 Regret analysis

To bound the random variable $\smash{\widetilde{R}}_{T}$, we appeal to Lemma 7 that can be used to relate the instantaneous regret of the algorithm to properties of the SDP solutions it computes. Conditioned on the good event $\mathcal{E}_{t}$, the boundness of the visited states ensures that the confidence matrix $V_{t}$ is bounded as the lemma requires. The lemma then implies that

On the other hand, as $u_{t}=K_{t}x_{t}$ and $J^{\star}\geq\sigma^{2}\|P_{t}\|_{*}$ (which is also a consequence of Lemma 7), we have

Combining the inequalities and summing over $t=1,\ldots,T$, gives via some algebraic manipulations the following bound:

We now proceed to bounding each of the sums in the above. The first sum above telescopes over consecutive rounds in which Algorithm 1 uses the same policy and thus the matrix $P_{t}$ remains unchanged. Therefore, the number of remaining terms, each of which is bounded by a constant, is exactly the number of times that Algorithm 1 computes a new policy. We show that when the good events occur, the number of policy switches is at most $O(n\log T)$, which gives rise to the following.

The next two terms in the bound above are sums of martingale difference sequences, as the noise terms $w_{t}$ are i.i.d., and each $w_{t}$ is independent of $P_{t}$, $K_{t}$ and $x_{t}$. Using standard concentration arguments, we show that both are bounded by $\smash{\widetilde{O}}(\sqrt{T})$ with high probability.

With probability at least $1-\delta/4$, it holds that

With probability at least $1-\delta/4$, it holds that

Finally, using the elementary identity $z^{\mkern-1.5mu\scriptstyle\mathsf{T}}V^{-1}z\leq 2\log(\det(V+zz^{\mkern-1.5mu\scriptstyle\mathsf{T}})/\det(V))$ for $V\succ 0$ and any vector $z$ such that $z^{\mkern-1.5mu\scriptstyle\mathsf{T}}V^{-1}z\leq 1$, we show that the final sum in the bound telescopes and can be bounded in terms of $\log(\det(V_{T+1})/\det(V_{1}))$; in turn, the latter quantity can be bounded by $O(n\log{T})$ using the fact that the $z_{t}$ are uniformly bounded on the event $\mathcal{E}_{T}$. This argument results with:

Our main theorem now follows by plugging-in the bounds into Eq. 5, using a union bound to bound the failure probability, and applying some algebraic simplification.

The relaxed SDP program

In this section we present useful properties of the relaxed SDP program repeatedly solved by Algorithm 1, which are used to prove Lemmas 7 and 9 discussed above and are central to our development.

The relaxed SDP program takes the following form. Let $\mu>0$ be a fixed parameter, and assume $A$, $B$ and $V$ are matrices such that the error matrix $\Delta=(A\,B)-(A_{\star}\,B_{\star})$ satisfies $\operatorname*{Tr}(\Delta V\Delta^{\mkern-1.5mu\scriptstyle\mathsf{T}})\leq 1$.

For this section, the dual program to (6) will be useful:

We now aim at proving Lemma 7 which states that SDP (6) is a relaxation of the original exact SDP (4). It follows directly from Lemmas 15 and 16 given below; see Section B.4. First, we present a matrix-perturbation lemma also proven in Section C.1.

Let $X$ and $\Delta$ be matrices of matching sizes and assume $\Delta^{\mkern-1.5mu\scriptstyle\mathsf{T}}\Delta\preceq V^{-1}$ for some matrix $V\succ 0$. Then for any $\Sigma\succeq 0$ and $\mu\geq 1+2\|X\|\|V\|^{1/2}$,

Assume $\mu\geq 1+2\vartheta\|V\|^{1/2}$. Then the optimal value of SDP (6) is at most $J^{\star}$. Consequently, for a primal-dual optimal solution $\Sigma$, $P$ we have $\|\Sigma\|_{*}\leq J^{\star}/\alpha_{0}$ and $\|P\|_{*}\leq J^{\star}/\sigma^{2}$.

It suffices to show that $\Sigma^{\star}$, the solution to the original SDP (4), is feasible for the relaxed SDP. Indeed, $\Sigma^{\star}\succeq 0$, and combining Eqs. 4 and 14 (note that $\operatorname*{Tr}(\Delta V\Delta^{\mkern-1.5mu\scriptstyle\mathsf{T}})\leq 1$ implies that $\Delta^{\mkern-1.5mu\scriptstyle\mathsf{T}}\Delta\preceq V^{-1}$) yields Eq. 6 due to

The next lemma shows how to extract a policy from the relaxed SDP. Somewhat surprisingly, this policy is deterministic and has the linear form $x\mapsto Kx$, as is the case in the original SDP.

Assume that $V\succeq(\nu\mu/\alpha_{0}\sigma^{2})I,$ and $\mu\geq 1+2\vartheta\|V\|^{1/2}.$ Let $\Sigma$ and $P$ be primal and dual optimal solutions to the relaxed SDP. Then $\Sigma_{xx}$ is invertible, and for $K=\Sigma_{ux}\Sigma_{xx}^{-1}$ we have

Recall the complementary-slackness conditions of the SDP, that read $\Sigma Z=0$. We now show that $\Sigma_{xx}\succ 0$ and $\operatorname{rank}(\Sigma)=d$ as this would entail that

Thus the span of $\Sigma$ is the span of $\begin{pmatrix}I\\ K\end{pmatrix}$ whence $\begin{pmatrix}I\\ K\end{pmatrix}^{\mkern-1.5mu\scriptstyle\mathsf{T}}Z\begin{pmatrix}I\\ K\end{pmatrix}=0$ as required.

To that end, we begin by stating the following basic fact about matrices: For any two $n$-dimensional symmetric matrices, $X,Y$, that satisfy $XY=0$, it must be that $\operatorname{rank}(X)+\operatorname{rank}(Y)\leq n$. Then it suffices to show $\Sigma_{xx}\succ 0$ and $\operatorname{rank}(Z)\geq k$. Indeed, using Lemma 15,

as $W=\sigma^{2}I$ and $\begin{pmatrix}Q&0\\ 0&R\end{pmatrix}\succeq\alpha_{0}I$. Plugging Eq. 8 into Eq. 6 and using $\Sigma\succeq 0$, shows that $\Sigma_{xx}\succ 0$. Moreover, $Z$ is the difference of

which is of rank $d+k$ in light of Eq. 9 and since $P\succeq 0$, and $\begin{pmatrix}P&0\\ 0&0\end{pmatrix}$ which is of rank at most $d$. Therefore, $\operatorname{rank}(Z)\geq k$ as required. ∎

We continue with proving the main result of this section that would imply Lemma 9 (see Section B.6). We show that the sequence of policies generated by solving a certain series of relaxed SDPs is strongly-stable.

Let ${P}_{1},{P}_{2},\ldots$ be optimal solutions to the relaxed dual SDP; each ${P}_{t}$ associated with $(A_{t}\;B_{t})$ and $V_{t}$ respectively. Let $\kappa=\sqrt{2\nu/\alpha_{0}\sigma^{2}}$, $\gamma=1/2\kappa^{2}$, and suppose that $\mu\geq 1+2\vartheta\|V_{t}\|^{1/2}$ and $V_{t}\succeq 16\kappa^{10}\mu I$ for all $t$. Moreover, let $K_{t}$ be the policy associated with $P_{t}$ (as in Lemma 16). Then the sequence $K_{1},K_{2},\ldots$ is $(\kappa,\gamma)$-strongly stable.

The proof is given by combining the following two lemmas. Indeed, in Section C.2 we show that each policy $K_{t}$ is strongly stable.

$K_{t}$ is $(\kappa,\gamma)$-strongly stable for $A_{\star}+B_{\star}K_{t}=H_{t}L_{t}H_{t}^{-1}$ where $H_{t}=P_{t}^{1/2}$ and $\|L_{t}\|\leq 1-\gamma$. Moreover, $(\alpha_{0}/2)I\preceq P_{t}\preceq(\nu/\sigma^{2})I$.

Furthermore, having established strong stability, the next lemma shows that $P_{t}$ is “close” to $P_{t+1}$ (see Section C.3 for a proof).

$P_{t}\preceq P^{\star}\preceq P_{t+1}+(\alpha_{0}\gamma/2)I$ for all $t\geq 1$.

We show that the conditions for sequential strong-stability hold. Notice that not only does Lemma 18 show that for all $t$, $K_{t}$ is $(\kappa,\gamma)$-strongly stable, it also gives us uniform upper and lower bounds on $H_{t}=P_{t}^{1/2}$ as $\|P_{t}\|\leq\|P_{t}\|_{*}\leq\nu/\sigma^{2}$ (Lemma 15), and $\|P_{t}^{-1}\|\leq 2/\alpha_{0}$. Together with $P_{t+1}\succeq(\alpha_{0}/2)I$, the lemma implies

Thus $\|H_{t+1}^{-1}H_{t}\|\leq\sqrt{1+\gamma}\leq 1+\smash{\tfrac{1}{2}}\gamma$ which provides sequential strong-stability. ∎

Warm-up Using a Stable Policy

In this section we give a simple warm-up scheme that can be used in an initial exploration phase, after which the conditions of our main algorithm are met. Here we assume that we are given a policy $K_{0}$ which is known to be $(\kappa_{0},\gamma_{0})$-strongly stable for the LQR (1).

Starting from $x_{1}=0$ and over $T_{0}$ rounds, the warm-up procedure samples actions $u_{t}\sim\mathcal{N}(K_{0}x_{t},2\sigma^{2}\kappa_{0}^{2}I)$ independently; this is summarized in Algorithm 2.

Let $V_{0}=\sum_{t=1}^{T_{0}}z_{t}z_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}}$ be the empirical covariance matrix corresponding to the samples $z_{t}$ collected during warm-up, where $z_{t}=\begin{pmatrix}x_{t}\\ u_{t}\end{pmatrix}$ for all $t$. The main result of this section gives upper and lower bounds on the matrix $V_{0}$.

and for $V=V_{0}+\sigma^{2}\vartheta^{-2}I$ and initial estimates \mathopen{}\big{(}A_{0}\,B_{0}\big{)}=\sum_{t=1}^{T_{0}-1}x_{t+1}z_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}}V^{-1} we have

With Theorem 20 in hand, the proof of Corollary 5 readily follows; see details in Section B.2. The proof of Theorem 20 itself is based on adaptations of techniques developed in Simchowitz et al. (2018) in the context of identification of Linear Dynamical Systems, and is given in Section D.1.

We thank Yoram Singer and Kunal Talwar for many helpful discussions. YM was supported in part by a grant from the Israel Science Foundation (ISF). AC thanks Lotem Peled for her assistance and support.

References

Appendix A Preliminaries

First, we state a variant of the Hanson-Wright inequality (Hanson and Wright, 1971; Wright, 1973), which can be found in Hsu et al. (2012).

The following is Azuma’s inequality for concentration of martingales with bounded differences.

Let $X_{1},\ldots,X_{N}$ be a martingale difference sequence such that $\lvert X_{i}\rvert\leq c$ for all $i=1,\ldots,n$. Then,

The following is is a self-normalized concentration inequality for vector-valued martingales useful for guaranteeing generalization in linear regression.

Let $(\mathcal{F}_{t})_{t=0}^{\infty}$ be a filtration and let $(\eta_{t})_{t=1}^{\infty}$ be a real-valued martingale difference sequence adapted to $(\mathcal{F}_{t})$ such that $\eta_{t}$ is $R$-sub-Gaussian conditioned on $\mathcal{F}_{t-1}$, that is,

Then, for any $\delta\in(0,1)$ we have with probability at least $1-\delta$ that

A.2 Technical Lemmas

Let $X$ and $\Delta$ be matrices of matching sizes and assume $\Delta^{\mkern-1.5mu\scriptstyle\mathsf{T}}\Delta\preceq V^{-1}$ for some matrix $V\succ 0$. Then for any $P\succeq 0$ and $\mu\geq 1+2\|X\|\|V\|^{1/2}$,

Note that $(X+\Delta)^{\mkern-1.5mu\scriptstyle\mathsf{T}}P(X+\Delta)-X^{\mkern-1.5mu\scriptstyle\mathsf{T}}PX=X^{\mkern-1.5mu\scriptstyle\mathsf{T}}P\Delta+\Delta^{\mkern-1.5mu\scriptstyle\mathsf{T}}PX+\Delta^{\mkern-1.5mu\scriptstyle\mathsf{T}}P\Delta$. Let $\epsilon>0$. We have

this can be seen by expanding the inequality $(\epsilon^{-1/2}X-\epsilon^{1/2}\Delta)^{\mkern-1.5mu\scriptstyle\mathsf{T}}P(\epsilon^{-1/2}X-\epsilon^{1/2}\Delta)\succeq 0.$ Setting $\epsilon=\|X\|\|V\|^{1/2}$ and using our assumption that $\Delta^{\mkern-1.5mu\scriptstyle\mathsf{T}}\Delta\preceq V^{-1}$ yields

This, together with $\Delta^{\mkern-1.5mu\scriptstyle\mathsf{T}}P\Delta\preceq\|P\|\Delta^{\mkern-1.5mu\scriptstyle\mathsf{T}}\Delta\preceq\|P\|V^{-1}$, proves one direction of the inequality. For the other direction, a similar argument shows

Let $X,Z$ be symmetric matrices of equal sizes and $Y$ a $(\kappa,\gamma)$-strongly stable matrix such that $X\preceq Y^{\mkern-1.5mu\scriptstyle\mathsf{T}}XY+Z$. Then $X\preceq(\kappa^{2}/\gamma)\|Z\|I$.

The inequality $X\preceq Y^{\mkern-1.5mu\scriptstyle\mathsf{T}}XY+Z$ implies there exists a matrix $M$ such that $M\succeq 0$, and $X=Y^{\mkern-1.5mu\scriptstyle\mathsf{T}}XY+Z-M$. As $Y$ is stable, the equation has a unique solution that satisfies:

Let us proceed in bounding the norm of the right-hand side of this inequality. As $Y$ is $(\kappa,\gamma)$-strongly stable, $Y=HLH^{-1}$ with $\|L\|\leq 1-\gamma$ and $\|H\|\|H^{-1}\|\leq\kappa$. Therefore,

For $M\succ 0$ and a vector $z$ such that $z^{\mkern-1.5mu\scriptstyle\mathsf{T}}M^{-1}z\leq 1$,

Observe that $\det(M+zz^{\mkern-1.5mu\scriptstyle\mathsf{T}})=\det(M)\det(I+M^{-1/2}zz^{\mkern-1.5mu\scriptstyle\mathsf{T}}M^{-1/2})=(1+z^{\mkern-1.5mu\scriptstyle\mathsf{T}}M^{-1}z)\det(M)$ by the determinant lemma, and so

The proof is finished using the concavity of $x\mapsto\log(1+x)$ and the fact that $0\leq z^{\mkern-1.5mu\scriptstyle\mathsf{T}}M^{-1}z\leq 1$:

If $N\succeq M\succ 0$, then for any vector $v$ one has

Note that the claimed inequality is equivalent to $N\preceq(\det(N)/\det(M))M$, which in turn is equivalent to $\|M^{-1/2}NM^{-1/2}\|\leq\det(M^{-1/2}NM^{-1/2})$. The latter is true because $R=M^{-1/2}NM^{-1/2}\succeq I$, and so the product of the eigenvalues of $R$ (all of which are $\geq 1$) is no smaller than the maximal eigenvalue of $R$. ∎

A.3 Proof of Lemma 3

Following the sequence $K_{1},K_{2},\ldots$ induces updates $x_{t+1}=(A_{\star}+B_{\star}K_{t})x_{t}+w_{t}$. Thus

Since the sequence $K_{1},K_{2},\ldots$ is sequential strong stable, there exist matrices $H_{1},H_{2},\ldots$ and $L_{1},L_{2},\ldots$ such that $A_{\star}+B_{\star}K_{j}=H_{j}L_{j}H_{j}^{-1}$ with the properties specified in Definition 2. Thus, we have for all $1\leq s<t$ that

As $\kappa\geq 1$, the same holds for $M_{t}$.

Appendix B Proofs of Section 4

For the proofs in this section, we require the following two simple lemmas.

Assume $T\geq 2$, $\lambda\geq 1$ and $\sum_{s=1}^{t}\|z_{s}\|^{2}\leq 2\beta t$. Let $V_{t}=\lambda I+\beta^{-1}\sum_{t=1}^{t-1}z_{t}z_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}}$. Then

Assume that $\|z_{s}\|^{2}\leq 4\kappa^{4}e^{-\gamma(t-1)}+\beta$ for $s=1,\ldots,t$, and $\kappa=\sqrt{2\nu/\alpha_{0}\sigma^{2}}$, $\gamma=1/2\kappa^{2}$. Also suppose that $t\geq\|x_{1}\|^{2}$. Then $\sum_{s=1}^{t}\|z_{s}\|^{2}\leq 2\beta t$.

To bound the random variable $\smash{\widetilde{R}}_{T}$, we appeal to Lemma 7. The lemma requires that, at round $s$, the confidence matrix $V_{s}$ is well-conditioned. Indeed, assuming $\mathcal{E}_{t}$ holds, then on the one hand $V_{s}\succeq\lambda I$ for $\lambda\geq(10\nu\vartheta/\alpha_{0}\sigma^{2})\sqrt{T}$, and on the other hand, $\|V_{s}\|\leq\lambda+\beta^{-1}\sum_{r=1}^{s-1}\|z_{r}\|^{2}\leq T+2T\leq 4T$ thanks to Lemma 29. Now, for any time $t$, let $\tau(t)$ denote the last time before round $t$ in which Algorithm 1 updated its policy, so that $A_{t}=A_{\tau(t)}$, $B_{t}=B_{\tau(t)}$, $K_{t}=K_{\tau(t)}$ and $P_{t}=P_{\tau(t)}$ for all $t$. Lemma 7 then implies

On the other hand, as $u_{t}=K_{t}x_{t}$ and $J^{\star}\geq\sigma^{2}\|P_{t}\|_{*}$, we have

Thus, given that $\mathcal{E}_{t}$ holds,

and since Algorithm 1 maintains that $\det(V_{t})\leq 2\det(V_{\tau(t)})$, we have $z_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}}V_{\tau(t)}^{-1}z_{t}\leq 2z_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}}V_{t}^{-1}z_{t}$ as a result of Lemma 27. This, along with the fact that $\|P_{t}\|_{*}\leq\nu/\sigma^{2}$ on $\mathcal{E}_{t}$ (recall Lemma 7), yields

The theorem now follows by plugging in the bounds of Lemmas 10, 11, 12 and 13, using a union bound to bound the failure probability, and applying some algebraic simplifications. ∎

B.2 Proof of Corollary 5

First, let us show that if Theorem 20 holds then the initial conditions of Theorem 4 are satisfied. Indeed, using $V\succeq V_{0}\succeq(T_{0}\sigma^{2}/80)I$ gives

which, by our choice of $T_{0}$, is at most $\smash{\tfrac{\alpha_{0}^{5}\sigma^{10}}{2^{13}\nu^{5}\vartheta\sqrt{T}}}$. This means that the conditions of Theorem 4 hold. Now, by a union bound, with probability at least $1-\delta$ Theorems 20, 4 and 6 hold, each with probability at least $1-\delta/3$. Then the regret of this procedure is

and regret on the remaining rounds is bounded by virtue of Theorem 4. ∎

B.3 Proof of Lemma 6

Denote $\Theta_{\star}=\mathopen{}\left(A_{\star}\,B_{\star}\right)$ and $\Theta_{t}=\mathopen{}\left(A_{t}\,B_{t}\right)$. Note that the solution to the least-square estimate is given as:

Plugging $x_{s+1}=\Theta_{\star}z_{s}+w_{s}$ into Eq. 10 and denoting $S_{t}=\sum_{s=1}^{t}w_{s}z_{s}^{\mkern-1.5mu\scriptstyle\mathsf{T}}$, we have

To get the result we need to bound the first term. Denote $S_{t}(i)=\sum_{s=1}^{t-1}w_{s}(i)z_{s}$ for all $i=1,\ldots,d$. For each $i$, applying Theorem 23 yields that, with probability at least $1-\delta/d$,

By additionally applying a union bound, the above holds with probability at least $1-\delta$ for all $i=1,\ldots,d$ simultaneously, and then

Plugging this to the inequality above, and using $\beta\geq 1$, gives the main statement of the lemma.

To show $\operatorname*{Tr}(\Delta_{t}V_{t}\Delta_{t})\leq 1$ under the conditions of Algorithm 1, note that $\|\Delta_{0}\|_{F}^{2}\leq\epsilon\leq 1/4\lambda$ by assumption. Thus it remains to prove \log\mathopen{}\big{(}\smash{\tfrac{d}{\delta}}\smash{\tfrac{\det(V_{t})}{\det(V_{1})}}\big{)}\leq\smash{\tfrac{\beta}{8\sigma^{2}d}}. Indeed, in view of Lemma 28 and the definition of $\beta$:

B.4 Proof of Lemma 7

To prove the lemma, we aim to apply Lemmas 15 and 16.

First, we show that $\mu\geq 1+2\vartheta\|V_{t}\|$. Indeed, assuming $\|V_{t}\|\leq 4T$ and $T\geq\vartheta^{-2}$ implies that

Consequently, Lemma 15 gives item (i) as well as that the dual solution of the SDP, $P_{t}$, is bounded as $\|P_{t}\|_{*}\leq\nu/\sigma^{2}$.

Next, note that $V_{t}\succeq\lambda I$ as well as $\lambda\geq\nu\mu/\alpha_{0}\sigma^{2}~{},$ where we have used the fact that $\nu\geq J^{\star}\geq P^{\star}\bullet W\geq\begin{pmatrix}Q&0\\ 0&R\end{pmatrix}\bullet W\geq\alpha_{0}\sigma^{2}$. This gives $V_{t}\succeq(\nu\mu/\alpha_{0}\sigma^{2})I$. Thus we apply Lemma 16 that shows item (ii).

To show item (iii), we have that $P_{t}$ is positive semi-definite immediately from the dual formulation of the SDP (7). Moreover, notice that Lemma 16 also gives

which we link with the true parameters $(A_{\star}\,B_{\star})$ by combining the equation with Lemma 24. ∎

B.5 Proof of Lemma 8

With probability at least $1-\delta/2$, Lemma 6 holds. Also, for any $t=1,\ldots,T$ with probability at least $1-\delta/2T$, by the Hanson-Wright concentration inequality (Theorem 21),

as $T\geq 2$. Thus, via a union bound, both statements hold simultaneously with probability $1-\delta$.

Next, we show by induction on $t$ that $\operatorname*{Tr}(\Delta_{t}V_{t}\Delta_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}})\leq 1$ and $\|V_{t}\|\leq 4T$. This will particularly ensure that the policies generated by Algorithm 1 are sequentially strongly-stable which will give us $\|z_{t}\|^{2}\leq 4\kappa^{4}e^{-\gamma(t-1)}\|x_{1}\|^{2}+\beta$ for all $t=1,\ldots,T$.

For the base case, $t=1$, we have by assumption

Now, assume that for all $s=1,\ldots,t-1$, $\operatorname*{Tr}(\Delta_{s}V_{s}\Delta_{s}^{\mkern-1.5mu\scriptstyle\mathsf{T}})\leq 1$ and $\|V_{s}\|\leq 4T$. We show that $\operatorname*{Tr}(\Delta_{t}V_{t}\Delta_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}})\leq 1$ and $\|V_{t}\|\leq 4T$.

To that end we first show that $\|z_{s}\|^{2}\leq 4\kappa^{4}e^{-(t-1)\gamma}\|x_{1}\|^{2}+\beta$ for all $s=1,\ldots,t$. Indeed, by $V_{t}\succeq\lambda I\succeq 16\kappa^{10}\mu I$, Lemma 9 implies that policies generated by Algorithm 1 up to round $t$ form a $(\kappa,\gamma)$-strongly stable sequence for $\kappa=\sqrt{2\nu/\alpha_{0}\sigma^{2}}$ and $\gamma=\smash{\tfrac{1}{2}}\kappa^{-2}$. Consequently, Lemma 3 yields for all $s=1,\ldots,t$

In particular, $\sum_{s=1}^{t}\|z_{s}\|^{2}\leq 2\beta T$ in view of Lemma 29. This, along with assuming $T\geq\lambda$, immediately gives

Finally, as we’ve shown $\sum_{s=1}^{t}\|z_{s}\|^{2}\leq 2\beta T$, Lemma 6 additionally provides $\operatorname*{Tr}(\Delta_{t}V_{t}\Delta_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}})\leq 1$. ∎

B.6 Proof of Lemma 9

The proof follows by applying Theorem 17 over the sequence $K_{1},\ldots,K_{T}$ of policies generated by Algorithm 1. To that end, define $\tau(t)$ as the last round before $t$ in which Algorithm 1 updates its policy. Note that each policy $K_{t}$ is associated with $A_{t},B_{t},P_{t}$ and $V_{\tau(t)}$.

Thus, to apply Theorem 17 it suffice to show that $\mu\geq 1+2\vartheta\|V_{t}\|^{1/2}$ and $V_{t}\succeq 16\kappa^{10}\mu I$ for all rounds $t\geq 1$. Indeed, as we assume $T\geq\vartheta^{-2}$ and $\|V_{t}\|\leq 4T$, we have

Furthermore, using $\kappa=\sqrt{2\nu/\alpha_{0}\sigma^{2}}$, we have $V_{t}\succeq\lambda I$ where $\lambda\geq 2^{9}\nu^{5}\cdot 5\vartheta\sqrt{T}/\alpha_{0}^{5}\sigma^{10}=16\kappa^{10}\mu$ as required. ∎

B.7 Proof of Lemma 10

Let $N$ the last round $t$ such that $\mathcal{E}_{t}$ holds. Let $\tau_{1}<\cdots<\tau_{M}$ be the time instances in which Algorithm 1 changes policy up to round $N$, and let $\tau_{0}=1$, $\tau_{M+1}=N+1$. By Lemma 28, as $\mathcal{E}_{N}$ holds,

Since $\|P_{t}\|_{*}\leq\nu/\sigma^{2}$ and $\|x_{t}\|^{2}\leq\|z_{t}\|^{2}\leq 4\kappa^{4}\|x_{1}\|^{2}+\beta$ on $\mathcal{E}_{t}$, we can bound

B.8 Proof of Lemma 11

The lemma would follow directly from the following.

Let $\delta\in(0,1)$. Let $(\mathcal{F}_{t})_{t=1}^{\infty}$ be a filtration. Let $w_{1},w_{2},\ldots\sim\mathcal{N}(0,\sigma^{2}I)$ be i.i.d Gaussian random variables. Let $v_{1},v_{2},\ldots$ be a sequence of vectors such that $v_{t}$ is $\mathcal{F}_{t-1}$-measurable and $\sum_{t=1}^{T}\|v_{t}\|^{2}\leq D^{2}$ almost surely for each $t$. Then with probability $1-\delta$,

Denote $Y_{t}=v_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}}w_{t}$. Note that, conditioned on the randomness before round $t$, each $Y_{t}$ is a zero-mean Gaussian random variable. Thus we can write $Y_{t}=\eta_{t}m_{t}$, where $m_{t}^{2}$ is the variance of $Y_{t}$ given $\mathcal{F}_{t-1}$, and $\eta_{t}\sim\mathcal{N}(0,1)$.

Let $\lambda>0$. Using the observation above, we apply Theorem 23 with $V=\lambda$ to obtain that with probability $1-\delta$

We now proceed by upper bounding $\sum_{t=1}^{T}m_{t}^{2}$. The variance of $Y_{t}$ given $\mathcal{F}_{t-1}$ is:

Set $\lambda=\sigma^{2}D^{2}$. Plugging the bound above into Eq. 11 and rearranging gets us this lemma’s statement. ∎

B.9 Proof of Lemma 12

The lemma is an immediate consequence of the following.

Let $(\mathcal{F}_{t})_{t=1}^{\infty}$ be a filtration, and let $M_{1},M_{2},\ldots$ be a sequence of symmetric positive semi-definite matrices such that $M_{t}$ is $\mathcal{F}_{t-1}$-measurable and $\|M_{t}\|_{*}\leq D$ almost surely for each $t$. Further, let $w_{1},w_{2},\ldots\sim\mathcal{N}(0,\sigma^{2}I)$ be a sequence of i.i.d. Gaussian random variables. Then for $T\geq 2$ and for any $\delta\in(0,1)$, it holds with probability at least $1-\delta$ that

Define the random variables $X_{t}=w_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}}M_{t}w_{t}-\sigma^{2}\|M_{t}\|_{*}$ for all $t\geq 1$. Observe that

with probability at least $1-\delta^{\prime}$. Since $\|M_{t}\|_{*}\leq D$, this implies that $X_{t}\leq\Gamma$ for all $t$ with probability at least $1-\delta/2T$, which in turn means that $\smash{\widetilde{X}}_{t}=X_{t}$ for all $t$ with the same probability.

B.10 Proof of Lemma 13

Note that for any $t$ we have on $\mathcal{E}_{t}$ that

using $\lambda\geq\vartheta\sqrt{T}$ as $\kappa\geq 1$, and $T\geq\vartheta^{-2}(1+\|x_{1}\|^{2})^{2}$. Let $N$ the last round $t$ such that $\mathcal{E}_{t}$ holds, then

Appendix C Proofs of Section 5

C.2 Proof of Lemma 18

Now, recall that, by assumption, $V\succeq 2\kappa^{2}\mu I$. Therefore, by Lemma 14,

Hence, as $Q\succeq\alpha_{0}I$ and $R\succeq\alpha_{0}I$,

In particular, this shows that $P_{t}\succeq\frac{1}{2}\alpha_{0}I$. Further, using again the fact that $\|P_{t}\|_{*}\leq\nu/\sigma^{2}$ (Lemma 15) to bound $P_{t}-\frac{1}{2}\alpha_{0}I\preceq(1-\kappa^{-2})P_{t}$ and rearranging yields

Letting $H_{t}=P_{t}^{1/2}$ and L_{t}=P_{t}^{-1/2}\mathopen{}\big{(}A_{\star}+B_{\star}K_{t}\big{)}P_{t}^{1/2}, we have established that $\|L_{t}\|\leq\sqrt{1-\kappa^{-2}}\leq 1-\frac{1}{2}\kappa^{-2}$, as well as $\|H_{t}\|\leq\sqrt{\nu/\sigma^{2}}$ and $\|H_{t}^{-1}\|\leq\sqrt{2/\alpha_{0}}$. To bound the norm of $K_{t}$, observe that Eq. 13 implies $P_{t}\succeq\smash{\tfrac{1}{2}}\alpha_{0}K_{t}^{\mkern-1.5mu\scriptstyle\mathsf{T}}K_{t}$ hence

As $A_{\star}+B_{\star}K_{t}=H_{t}L_{t}H_{t}^{-1}$, this shows that $K_{t}$ is $(\kappa,\gamma)$-strongly stable. ∎

C.3 Proof of Lemma 19

It suffices to show that $P_{t}\preceq P^{\star}\preceq P_{t}+\smash{\tfrac{\alpha_{0}\gamma}{2}}I$ for all $t\geq 1$.

For $P_{t}\preceq P^{\star}$, let $K_{\star}$ denote the optimal policy corresponding to $P^{\star}$. As $P^{\star}$ is the solution to the Riccati equation:

On the other hand, applying Lemma 24 over Eq. 7 gives

and, as $K_{\star}$ is a (strongly) stable policy, Lemma 25 implies $P-P^{\star}\preceq 0$.