Introduction
Learning to control an unknown system during operation requires balancing exploration, which collects informative data to reduce uncertainty about the dynamics, with exploitation, which uses the available knowledge to achieve good control performance. The linear–quadratic regulator (LQR) with unknown dynamics has become a standard benchmark for studying this trade-off in online control and in reinforcement learning with continuous state and action spaces. In LQR, under a fixed feedback u t = K x t u_t = Kx_t u t = K x t , the next state x t + 1 = A x t + B u t + w t x_{t+1} = Ax_t + Bu_t + w_t x t + 1 = A x t + B u t + w t depends on ( A , B ) (A, B) ( A , B ) only through the closed loop A + B K A + BK A + B K , so models that share this closed loop cannot be distinguished from the collected data. A certainty-equivalence (CE) learner, which always plays the controller that is optimal for a nominal system estimate, may therefore keep collecting data that cannot reveal such model errors. Moreover, classical results show that convergence of self-tuning LQ controllers to the optimal controller generally requires identification of the true parameter [19 ] . This motivated a variety of exploration strategies [1 , 18 , 3 ] , which attain the worst-case optimal O ~ ( T ) \tilde{O}(\sqrt{T}) O ~ ( T ) regret rate over T T T interactions with the unknown system [21 ] . CE can achieve faster, polylogarithmic rates when additional structure, such as prior knowledge of the dynamics, makes the data generated under optimal feedback sufficiently informative to identify all unknown parameters. In this work, we show that singular input penalties (degenerate LQR) can allow CE to achieve finite-time polylogarithmic expected regret even when the dynamics are not fully identifiable under optimal feedback.
Related Work
Exploration in online LQR. In the finite-time regret formulation of adaptive LQR, Abbasi-Yadkori and Szepesvári [1 ] obtained the first O ~ ( T ) \widetilde{O}(\sqrt{T}) O ( T ) regret bound using optimism in the face of uncertainty, and Cohen et al. [6 ] subsequently gave the first computationally efficient algorithm attaining the same rate. Mania et al. [18 ] established this rate for CE with injected input noise, and Simchowitz and Foster [21 ] proved that the regret rate achieved by such naive exploration cannot be improved in the worst case for fully unknown systems, up to logarithmic factors. These approaches provide O ~ ( T ) \widetilde{O}(\sqrt{T}) O ( T ) regret guarantees, but do not capture the faster rates that may be attainable when the data generated under optimal feedback are sufficiently informative.
CE under structured dynamics. With suitable structure in the dynamics, the data generated by a CE controller can be sufficiently informative for learning. CE can then achieve improved regret rates without persistent exploration. For example, a greedy CE algorithm achieves polylogarithmic expected regret when the input matrix B ⋆ B_{\star} B ⋆ is known, or when the state matrix A ⋆ A_{\star} A ⋆ is known and the optimal feedback gain is sufficiently non-degenerate [5 , 11 ] . Shirani Faradonbeh et al. [20 ] showed that an episodic CE scheme attains O ( log 2 T ) O(\log^{2} T) O ( log 2 T ) asymptotic regret almost surely, assuming that the parameters lie in a known set over which the closed-loop prediction error uniformly bounds the error of the optimal gain. Lee et al. [15 ] established finite-time polylogarithmic expected-regret bounds for CE with a known linear representation of the dynamics when the optimal controller persistently excites the unknown parameters.
When some parameter directions cannot be detected from data collected under optimal feedback, the consequences depend on whether they affect the optimal controller. For known A ⋆ A_{\star} A ⋆ , Ziemann and Sandberg [28 ] established a local asymptotic minimax lower bound of order T \sqrt{T} T around uninformative instances, where optimal feedback fails to reveal a parameter direction that changes the optimal gain. Motivated by this result, Liu [17 ] showed that it suffices to identify the optimal gain rather than the dynamics, and used controller identifiability (CI), which excludes such directions, to separate logarithmic from square-root local minimax regret. These results assume a positive definite input penalty R ≻ 0 R \succ0 R ≻ 0 . In this setting, CI requires all unknown parameters to be identifiable under optimal feedback whenever A ⋆ A_{\star} A ⋆ is nonsingular [17 Corollary 2] . The extent to which singular input penalties relax this requirement remains unaddressed.
CE for degenerate cost functions. A separate line of work studies minimum variance control (MVC). In a related multivariate stochastic regression setting, Lai [13 ] obtained asymptotically logarithmic regret by combining CE with sparse probing inputs. Lai and Wei [14 ] extended this approach to MVC of finite-order scalar autoregressive models with exogenous inputs (ARX models). More recently, Singh et al. [23 ] established finite-time polylogarithmic regret for self-tuning regulation of ARX models, of order log T \log T log T for bounded noise and log 3 T \log^{3} T log 3 T for sub-Gaussian noise. Lin et al. [16 ] further argued that CE can fail to converge to the optimal controller for cost criteria other than minimum output variance. Together, these results suggest that degenerate input costs can also contribute to making full parameter identification unnecessary. However, the MVC guarantees for ARX models concern scalar-output regulation without an input penalty. They do not provide guarantees for general quadratic state costs in underactuated systems, or for costs that penalize only some input directions.
Contributions
We extend controller identifiability to LQR with potentially singular input penalties, R ⪰ 0 R \succeq0 R ⪰ 0 , and establish finite-time polylogarithmic expected-regret guarantees for CE. Specifically:
In § 3.1 , we restate CI in terms of the curvature of the cost, which makes the role of the cost function explicit, and extend it to R ⪰ 0 R \succeq0 R ⪰ 0 . With m m m inputs, a singular R R R admits up to m dim ker R m \dim\ker R m dim ker R additional parameter directions that cannot be detected from data collected under optimal feedback but are harmless for control, so that CI no longer requires full parameter identifiability, even for nonsingular A ⋆ A_\star A ⋆ .
In § 4.1 , we prove that CE with a short warm-up achieves O ( log 2 T ) O(\log^2 T) O ( log 2 T ) expected regret whenever CI holds at the true system. The bound is non-asymptotic and requires only a stabilizing controller and coarse bounds on the system parameters.
In § 4.2 , we prove a local Ω ( T ) \Omega(\sqrt{T}) Ω ( T ) minimax lower bound around a system where CI fails, for any input penalty, including R = 0 R = 0 R = 0 .
In § 5 , we specialize these results to MVC and show that CI holds whenever range ( B ⋆ ) \operatorname{range}(B_\star) range ( B ⋆ ) is known. This prior is weaker than knowing B ⋆ B_\star B ⋆ and covers underactuated systems, as we illustrate on a cart–pole example.
Problem Setting
We use ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ for the Euclidean vector or spectral matrix norm, ∥ ⋅ ∥ F \|\cdot\|_F ∥ ⋅ ∥ F for the Frobenius norm, and ⟨ X , Y ⟩ F = Tr ( X ⊤ Y ) \langle X,Y\rangle_F = \operatorname{Tr}(X^\top Y) ⟨ X , Y ⟩ F = Tr ( X ⊤ Y ) .
Degenerate LQR
Dynamics and model class. We consider the linear system
x t + 1 = A ⋆ x t + B ⋆ u t + w t , t ≥ 1 , x 1 = 0 , (1) x_{t+1} = A_\star x_t + B_\star u_t + w_t,\qquad t \ge1,\qquad x_1 = 0, \tag*{(1)} x t + 1 = A ⋆ x t + B ⋆ u t + w t , t ≥ 1 , x 1 = 0 , (1)
with i.i.d. process noise w t ∼ N ( 0 , σ 2 I n ) w_t \sim\mathcal{N}(0,\sigma^2 I_n) w t ∼ N ( 0 , σ 2 I n ) of known variance σ 2 > 0 \sigma^2 > 0 σ 2 > 0 . The matrices Θ ⋆ = [ A ⋆ B ⋆ ] \Theta_\star= [A_\star\ B_\star] Θ ⋆ = [ A ⋆ B ⋆ ] , with A ⋆ ∈ R n × n A_\star\in\mathbb{R}^{n \times n} A ⋆ ∈ R n × n and B ⋆ ∈ R n × m B_\star\in\mathbb{R}^{n \times m} B ⋆ ∈ R n × m , are unknown, but the learner is given an affine model class that contains them,
C = { Θ ( θ ) : θ ∈ R p } , Θ ( θ ) = Θ r e f + E θ , \mathcal{C} = \{\Theta(\theta): \theta\in\mathbb{R}^p\},\qquad\Theta(\theta) = \Theta_{\mathrm{ref}} + \mathcal{E}\theta, C = { Θ ( θ ) : θ ∈ R p } , Θ ( θ ) = Θ ref + E θ ,
E θ = ∑ j = 1 p θ j E j , ⟨ E i , E j ⟩ F = 1 { i = j } , (2) \mathcal{E}\theta= \sum_{j=1}^{p}\theta_j E_j,\qquad\langle E_i,E_j\rangle_F = \mathbf{1}_{\{i=j\}}, \tag*{(2)} E θ = j = 1 ∑ p θ j E j , ⟨ E i , E j ⟩ F = 1 { i = j } , (2)
where Θ r e f \Theta_{\mathrm{ref}} Θ ref and E j E_j E j are known and Θ ⋆ = Θ ( θ ⋆ ) \Theta_\star= \Theta(\theta_\star) Θ ⋆ = Θ ( θ ⋆ ) for an unknown θ ⋆ ∈ R p \theta_\star\in\mathbb{R}^p θ ⋆ ∈ R p . This class includes fully unknown dynamics, but can also encode prior structural knowledge. Any finite-dimensional affine family admits this representation after removing redundant coordinates and orthonormalizing its directions. In this representation, ∥ E h ∥ F = ∥ h ∥ 2 \|\mathcal{E}h\|_F = \|h\|_2 ∥ E h ∥ F = ∥ h ∥ 2 and we write [ Δ A h Δ B h ] = E h [\Delta A_h\ \Delta B_h] = \mathcal{E}h [ Δ A h Δ B h ] = E h for h ∈ R p h \in\mathbb{R}^p h ∈ R p .
Cost and optimal controller. Policies are causal; that is, u t u_t u t is chosen based on x 1 , … , x t x_1,\ldots,x_t x 1 , … , x t , past inputs, and internal randomization that is independent of the process noise. Given known Q ≻ 0 Q \succ0 Q ≻ 0 and R ⪰ 0 R \succeq0 R ⪰ 0 , the stage cost at step t t t is
c t = x t ⊤ Q x t + u t ⊤ R u t . (3) c_t = x_t^\top Qx_t + u_t^\top Ru_t. \tag*{(3)} c t = x t ⊤ Q x t + u t ⊤ R u t . (3)
For a model Θ = [ A B ] \Theta= [A\ B] Θ = [ A B ] representing the linear dynamics and a linear controller K K K , we then define the following infinite-horizon average cost
J Θ ( K ) : = lim sup T → ∞ 1 T E K Θ [ ∑ t = 1 T c t ] , (4) J_{\Theta}(K) := \limsup_{T\to\infty} \frac{1}{T}\mathbb{E}^{\Theta}_{K}\left[\sum_{t=1}^{T} c_t\right], \tag*{(4)} J Θ ( K ) := T → ∞ lim sup T 1 E K Θ [ t = 1 ∑ T c t ] , (4)
where the expectation is over the noise w t w_t w t under the dynamics Θ \Theta Θ and the feedback u t = K x t u_t = Kx_t u t = K x t . We omit this dependence of the expectation when clear from the context and write J ( K ) : = J Θ ⋆ ( K ) J(K) := J_{\Theta_\star}(K) J ( K ) := J Θ ⋆ ( K ) .
The following assumption ensures that the LQR problem and optimal controller are well defined even when R R R is singular.
Assumption 1 ( A ⋆ , B ⋆ ) (A_\star, B_\star) ( A ⋆ , B ⋆ ) is stabilizable, Q ≻ 0 Q \succ0 Q ≻ 0 , R ⪰ 0 R \succeq0 R ⪰ 0 , and ker R ∩ ker B ⋆ = { 0 } \ker R \cap\ker B_\star= \{0\} ker R ∩ ker B ⋆ = { 0 } .
Proposition 7 shows that, under Assumption 1, the discrete-time algebraic Riccati equation (DARE)
P = Q + A ⋆ ⊤ P A ⋆ − A ⋆ ⊤ P B ⋆ ( R + B ⋆ ⊤ P B ⋆ ) − 1 B ⋆ ⊤ P A ⋆ P = Q + A_\star^\top P A_\star- A_\star^\top P B_\star(R + B_\star^\top P B_\star)^{-1} B_\star^\top P A_\star P = Q + A ⋆ ⊤ P A ⋆ − A ⋆ ⊤ P B ⋆ ( R + B ⋆ ⊤ P B ⋆ ) − 1 B ⋆ ⊤ P A ⋆
admits a unique positive definite stabilizing solution P ⋆ ≻ 0 P_\star\succ0 P ⋆ ≻ 0 . The same proposition proves that u t = K ⋆ x t u_t = K_\star x_t u t = K ⋆ x t is the unique stationary linear feedback minimizing J ( K ) J(K) J ( K ) , with
S ⋆ = R + B ⋆ ⊤ P ⋆ B ⋆ ≻ 0 , K ⋆ = − S ⋆ − 1 B ⋆ ⊤ P ⋆ A ⋆ , S_\star= R + B_\star^\top P_\star B_\star\succ0,\qquad K_\star= -S_\star^{-1}B_\star^\top P_\star A_\star, S ⋆ = R + B ⋆ ⊤ P ⋆ B ⋆ ≻ 0 , K ⋆ = − S ⋆ − 1 B ⋆ ⊤ P ⋆ A ⋆ ,
and ensures that the closed-loop matrix L ⋆ = A ⋆ + B ⋆ K ⋆ L_\star= A_\star+ B_\star K_\star L ⋆ = A ⋆ + B ⋆ K ⋆ is Schur stable. The assumption Q ≻ 0 Q \succ0 Q ≻ 0 ensures that every nonzero state direction is penalized, and the kernel condition that every unpenalized input direction affects the state; for R = 0 R = 0 R = 0 , the latter means that B ⋆ B_\star B ⋆ has full column rank.
Regret and certainty equivalence
Let J ⋆ : = J Θ ⋆ ( K ⋆ ) J_\star:= J_{\Theta_\star}(K_\star) J ⋆ := J Θ ⋆ ( K ⋆ ) denote the optimal infinite-horizon average cost. We measure the cost of learning over T T T decision rounds by the cumulative regret
R T = ∑ t = 1 T ( c t − J ⋆ ) , (5) R_T = \sum_{t=1}^{T}(c_t - J_\star), \tag*{(5)} R T = t = 1 ∑ T ( c t − J ⋆ ) , (5)
where c t c_t c t denotes the cost incurred by the learner on the true system Θ ⋆ \Theta_\star Θ ⋆ . Our performance criterion is then the expected cumulative regret E [ R T ] \mathbb{E}[R_T] E [ R T ] , where the expectation is taken over the process noise and any internal randomization of the learning algorithm.
Remark 1 (Expected regret) Since J ⋆ J_\star J ⋆ is an average over the noise, whereas each c t c_t c t depends on its realization, the standard deviation of R T R_T R T is of order T \sqrt{T} T , even under the optimal controller. For this definition of regret, polylogarithmic rates are therefore only meaningful in expectation. Asymptotic almost-sure polylogarithmic rates, such as those of Shirani Faradonbeh et al. [20 ] , are instead stated for a regret that compares the cost of the learner with that of the optimal controller under the same noise realization, so that this contribution of the noise cancels. We also note that, compared to an analysis on a high-probability event, bounding the expected regret additionally requires controlling the cost of rare failures, such as estimates that destabilize the system, which can be very large (Cassel et al., [5 ] ).
Finally, for an estimated model Θ ^ = [ A ^ B ^ ] \widehat{\Theta} = [\widehat{A}\ \widehat{B}] Θ = [ A B ] , we define the certainty-equivalent controller by
K ( Θ ^ ) = arg min K J Θ ^ ( K ) . (6) K(\widehat{\Theta}) = \mathop{\arg\min}_{K} J_{\widehat{\Theta}}(K). \tag*{(6)} K ( Θ ) = arg min K J Θ ( K ) . (6)
The minimizer is unique whenever ( A ^ , B ^ ) (\widehat{A}, \widehat{B}) ( A , B ) satisfies the conditions of Assumption 1 in place of ( A ⋆ , B ⋆ ) (A_\star, B_\star) ( A ⋆ , B ⋆ ) (Proposition 7). For models in C \mathcal{C} C , we overload notation by writing K ( θ ) : = K ( Θ ^ ( θ ) ) K(\theta) := K(\widehat{\Theta}(\theta)) K ( θ ) := K ( Θ ( θ )) .
Controller Identifiability
Fix a feedback gain K K K that stabilizes the model Θ ( θ ) = [ A ( θ ) B ( θ ) ] \Theta(\theta) = [A(\theta)\ B(\theta)] Θ ( θ ) = [ A ( θ ) B ( θ )] . Under this feedback, let p θ K ( y ∣ x ) p_\theta^K(y \mid x) p θ K ( y ∣ x ) denote the conditional density of the next state y y y given the current state x x x . This density is Gaussian with mean ( A ( θ ) + B ( θ ) K ) x (A(\theta) + B(\theta)K)x ( A ( θ ) + B ( θ ) K ) x and covariance σ 2 I n \sigma^2 I_n σ 2 I n . We quantify the information about θ \theta θ provided by each transition using the stationary per-step Fisher information:
I θ ( K ) = E θ , K [ ∇ θ log p θ K ( y ∣ x ) ( ∇ θ log p θ K ( y ∣ x ) ) ⊤ ] \mathcal{I}_\theta(K) = \mathbb{E}_{\theta,K}\left[\nabla_\theta\log p_\theta^K(y \mid x)(\nabla_\theta\log p_\theta^K(y \mid x))^\top\right] I θ ( K ) = E θ , K [ ∇ θ log p θ K ( y ∣ x ) ( ∇ θ log p θ K ( y ∣ x ) ) ⊤ ]
where the expectation is over two consecutive states ( x , y ) (x,y) ( x , y ) in the stationary closed loop and the gradient is taken with respect to θ \theta θ , holding K K K fixed. We further define
I ⋆ = I θ ⋆ ( K ⋆ ) , H ⋆ = ∇ θ 2 J Θ ⋆ ( K ( θ ) ) ∣ θ = θ ⋆ , \mathcal{I}_\star= \mathcal{I}_{\theta_\star}(K_\star), \qquad\mathcal{H}_\star= \left.\nabla_\theta^2 J_{\Theta_\star}(K(\theta))\right|_{\theta=\theta_\star}, I ⋆ = I θ ⋆ ( K ⋆ ) , H ⋆ = ∇ θ 2 J Θ ⋆ ( K ( θ )) θ = θ ⋆ ,
where H ⋆ \mathcal{H}_\star H ⋆ measures the local sensitivity of the CE controller’s performance to identification errors. For θ \theta θ sufficiently close to θ ⋆ \theta_\star θ ⋆ , K ( θ ) K(\theta) K ( θ ) stabilizes the true system Θ ⋆ \Theta_\star Θ ⋆ , and, since K ( θ ⋆ ) = K ⋆ K(\theta_\star) = K_\star K ( θ ⋆ ) = K ⋆ is optimal, a second-order Taylor expansion gives
J Θ ⋆ ( K ( θ ) ) − J ⋆ = 1 2 ( θ − θ ⋆ ) ⊤ H ⋆ ( θ − θ ⋆ ) + o ( ∥ θ − θ ⋆ ∥ 2 ) . J_{\Theta_\star}(K(\theta)) - J_\star= \frac{1}{2}(\theta-\theta_\star)^\top\mathcal{H}_\star(\theta-\theta_\star) + o(\lVert\theta-\theta_\star\rVert^2). J Θ ⋆ ( K ( θ )) − J ⋆ = 2 1 ( θ − θ ⋆ ) ⊤ H ⋆ ( θ − θ ⋆ ) + o (∥ θ − θ ⋆ ∥ 2 ) .
We refer to the parameter directions in ker I ⋆ \ker\mathcal{I}_\star ker I ⋆ as invisible directions , because perturbations along them do not change the distribution of data collected under the fixed controller K ⋆ K_\star K ⋆ . We call directions in ker H ⋆ \ker\mathcal{H}_\star ker H ⋆ harmless , meaning that identification errors along them have no second-order effect on the CE controller’s cost. Controller identifiability (CI) requires every invisible direction to be harmless.
Definition 2 Controller identifiability holds at θ ⋆ \theta_\star θ ⋆ if ker I ⋆ ⊆ ker H ⋆ \ker\mathcal{I}_\star\subseteq\ker\mathcal{H}_\star ker I ⋆ ⊆ ker H ⋆ .
CI was introduced by Liu [17 ] , who defined it for R ≻ 0 R \succ0 R ≻ 0 by requiring the derivative of the optimal gain to vanish along invisible directions, thereby excluding the uninformative instances of Ziemann and Sandberg [28 ] . We show in Lemma 12 that our definition agrees with that of Liu [17 ] for R ≻ 0 R \succ0 R ≻ 0 , while extending CI to potentially singular input penalties R ⪰ 0 R \succeq0 R ⪰ 0 . Our formulation directly highlights the role of the cost function in determining whether an invisible direction is harmless for performance. This leads to the following generalization of Liu [17 ] , which quantifies how many additional harmless invisible directions a singular input penalty allows.
Lemma 3 Suppose Assumption 1 holds and CI holds at θ ⋆ \theta_\star θ ⋆ . In the nonredundant affine representation (2),
dim ker I ⋆ ≤ m ( n − rank A ⋆ + dim ker R ) . \dim\ker\mathcal{I}_\star\leq m(n-\operatorname{rank} A_\star+ \dim\ker R). dim ker I ⋆ ≤ m ( n − rank A ⋆ + dim ker R ) .
The proof is given in Appendix B. When A ⋆ A_\star A ⋆ is nonsingular and R ≻ 0 R \succ0 R ≻ 0 , CI therefore implies I ⋆ ≻ 0 \mathcal{I}_\star\succ0 I ⋆ ≻ 0 , i.e., all unknown parameters must be identifiable under optimal feedback. A singular R R R instead allows CI with up to m dim ker R m\dim\ker R m dim ker R invisible directions. In § 5 , we give an MVC model class (R = 0 R = 0 R = 0 ) for which CI holds with dim ker I ⋆ = m 2 = m dim ker R \dim\ker\mathcal{I}_\star= m^2 = m\dim\ker R dim ker I ⋆ = m 2 = m dim ker R , matching the upper bound when A ⋆ A_\star A ⋆ is nonsingular.
Example. Consider the scalar system x t + 1 = a x t + b u t + w t x_{t+1} = ax_t + bu_t + w_t x t + 1 = a x t + b u t + w t , where a a a and b b b are unknown and nonzero. Under optimal feedback u t = K ⋆ x t u_t = K_\star x_t u t = K ⋆ x t , the observations identify only the closed-loop coefficient a + b K ⋆ a+bK_\star a + b K ⋆ . The invisible directions therefore satisfy Δ a + K ⋆ Δ b = 0 \Delta a + K_\star\Delta b = 0 Δ a + K ⋆ Δ b = 0 . For R > 0 R > 0 R > 0 , Lemma 3 implies that CI would require full parameter identifiability because a ≠ 0 a \ne0 a = 0 , so CI fails. When R = 0 R = 0 R = 0 , K ⋆ = − a / b K_\star= -a/b K ⋆ = − a / b , and small invisible perturbations scale a a a and b b b by the same factor. These perturbations preserve the ratio a / b a/b a / b , hence the optimal gain and the CE controller’s cost, so they are harmless. Thus CI holds even though a a a and b b b cannot be separately identified under optimal feedback.
Main Results
In this section, we show that, when CI holds at θ ⋆ \theta_\star θ ⋆ , a CE algorithm achieves polylogarithmic regret after a short exploration phase. § 4.2 complements this result with a worst-case lower bound over a family of systems including a plant where CI fails.
Regret Upper Bound
Algorithm
Similarly to Cassel et al. [5 ] , the learner is supplied with a gain K 0 K_0 K 0 that stabilizes the true system. It first plays K 0 K_0 K 0 with independent exploration noise η t ∼ N ( 0 , σ 2 I m ) \eta_t \sim\mathcal{N}(0,\sigma^2 I_m) η t ∼ N ( 0 , σ 2 I m ) for τ 0 − 1 \tau_0-1 τ 0 − 1 rounds, where τ 0 \tau_0 τ 0 is an input to the algorithm (Algorithm 1). The learner then proceeds in epochs, each of length at most τ 0 \tau_0 τ 0 . At each epoch boundary, the learner computes a regularized least-squares estimate restricted to the model class C \mathcal{C} C
Θ ^ t = arg min Θ ∈ C { ∑ s = 1 t − 1 ∥ x s + 1 − Θ z s ∥ 2 2 + λ ∥ Θ ∥ F 2 } , (7) \widehat{\Theta}_t = \underset{\Theta\in\mathcal{C}}{\arg\min}\left\{\sum_{s=1}^{t-1}\lVert x_{s+1}-\Theta z_s\rVert_2^2+\lambda\lVert\Theta\rVert_F^2\right\}, \tag*{(7)} Θ t = Θ ∈ C arg min { s = 1 ∑ t − 1 ∥ x s + 1 − Θ z s ∥ 2 2 + λ ∥ Θ ∥ F 2 } , (7)
where z t = ( x t ⊤ , u t ⊤ ) ⊤ z_t=(x_t^\top,u_t^\top)^\top z t = ( x t ⊤ , u t ⊤ ) ⊤ and the regularization parameter λ \lambda λ is an input to the algorithm. The learner plays the CE gain K ( Θ ^ t ) K(\widehat{\Theta}_t) K ( Θ t ) until the next epoch boundary, without additional exploration noise. The algorithm permanently falls back to K 0 K_0 K 0 if the estimated model has no positive definite stabilizing Riccati solution with S ^ t = R + B ^ t ⊤ P ^ t B ^ t ≻ 0 \widehat{S}_t=R+\widehat{B}_t^\top\widehat{P}_t\widehat{B}_t\succ0 S t = R + B t ⊤ P t B t ≻ 0 , or if ∥ K ( Θ ^ t ) ∥ > κ \lVert K(\widehat{\Theta}_t)\rVert>\kappa ∥ K ( Θ t )∥ > κ or ∥ x t ∥ 2 > x b \lVert x_t\rVert^2>x_b ∥ x t ∥ 2 > x b , where the thresholds κ , x b \kappa,x_b κ , x b are also inputs to the algorithm. These checks prevent a poor estimate from destabilizing the closed loop, which is needed to bound the regret in expectation. Our analysis uses coarse bounds on the problem parameters to construct explicit values of τ 0 , x b , κ , λ \tau_0,x_b,\kappa,\lambda τ 0 , x b , κ , λ for which Algorithm 1 achieves polylogarithmic regret under CI.
Specifically, the learner is supplied with constants α 0 , α 1 , ϑ , ν , ν 0 > 0 \alpha_0,\alpha_1,\vartheta,\nu,\nu_0>0 α 0 , α 1 , ϑ , ν , ν 0 > 0 such that
∥ Q ∥ , ∥ R ∥ ≤ α 1 , ∥ Q − 1 ∥ ≤ α 0 − 1 , ∥ A ⋆ ∥ , ∥ B ⋆ ∥ ≤ ϑ , J ⋆ ≤ ν , J ( K 0 ) ≤ ν 0 . \lVert Q\rVert,\lVert R\rVert\leq\alpha_1,\qquad\lVert Q^{-1}\rVert\leq\alpha_0^{-1},\qquad\lVert A_\star\rVert,\lVert B_\star\rVert\leq\vartheta,\qquad J_\star\leq\nu,\qquad J(K_0)\leq\nu_0. ∥ Q ∥ , ∥ R ∥ ≤ α 1 , ∥ Q − 1 ∥ ≤ α 0 − 1 , ∥ A ⋆ ∥ , ∥ B ⋆ ∥ ≤ ϑ , J ⋆ ≤ ν , J ( K 0 ) ≤ ν 0 .
Moreover, it is given conservative lower bounds on λ min ( S ⋆ ) \lambda_{\min}(S_\star) λ m i n ( S ⋆ ) and on σ min + ( D ⋆ ) \sigma_{\min}^{+}(D_\star) σ m i n + ( D ⋆ ) , the smallest nonzero singular value of the linear map D ⋆ h = Δ A h + Δ B h K ⋆ D_\star h=\Delta A_h+\Delta B_hK_\star D ⋆ h = Δ A h + Δ B h K ⋆ , which gives the change of the closed loop under the fixed gain K ⋆ K_\star K ⋆ when the parameter moves from θ ⋆ \theta_\star θ ⋆ along h ∈ R p h\in\mathbb{R}^p h ∈ R p (the latter bound is not needed if D ⋆ = 0 D_\star=0 D ⋆ = 0 ). The resulting values of the algorithmic parameters are
τ 0 = ⌈ C τ log ( 5 T ) ⌉ , x b = C x log ( 5 T ) , λ = C λ log ( 5 T ) , (8) \tau_0=\lceil C_\tau\log(5T)\rceil,\qquad x_b=C_x\log(5T),\qquad\lambda=C_\lambda\log(5T), \tag*{(8)} τ 0 = ⌈ C τ log ( 5 T )⌉ , x b = C x log ( 5 T ) , λ = C λ log ( 5 T ) , (8)
where κ \kappa κ and the constants C τ , C x , C λ C_\tau,C_x,C_\lambda C τ , C x , C λ depend on these bounds but not on T T T (see Remark 15).
As in Cassel et al. [5 ] and Lee et al. [15 ] , the warm-up provides an initial estimate that is accurate enough for the CE gains to be well defined and stabilizing, which is needed to ensure that, with high probability, the algorithm never falls back to K 0 K_0 K 0 . Unlike an explore-then-commit scheme that fixes its controller after exploring, Algorithm 1 keeps updating its estimate after the warm-up using the data generated by CE, so the warm-up only needs to reach a fixed accuracy that does not depend on T T T . This accuracy must, however, be reached with a confidence that increases with T T T . An inaccurate warm-up estimate may cause the algorithm to fall back to K 0 K_0 K 0 for the remaining rounds, incurring regret of order T T T . A fixed failure probability would therefore lead to a contribution of order T T T to expected regret. Our analysis chooses a failure probability δ = T − 2 \delta=T^{-2} δ = T − 2 , which keeps the expected contribution of failures bounded (Appendix C). Since a fixed accuracy can be reached with failure probability δ \delta δ using O ( log ( 1 / δ ) ) O(\log(1/\delta)) O ( log ( 1/ δ )) samples, this choice gives a warm-up length τ 0 = O ( log T ) \tau_0=O(\log T) τ 0 = O ( log T ) .
Algorithm 1 Certainty Equivalence for a CI system
Require: horizon T T T , parameters τ 0 \tau_0 τ 0 , x b x_b x b , κ \kappa κ , λ \lambda λ , a stabilizing gain K 0 K_0 K 0 , and the affine class C \mathcal{C} C
initialize: N T = ⌈ ( T − τ 0 + 1 ) / τ 0 ⌉ N_T = \lceil(T-\tau_0+1)/\tau_0\rceil N T = ⌈( T − τ 0 + 1 ) / τ 0 ⌉ , τ i ← min { τ 0 ( i + 1 ) , T + 1 } \tau_i \leftarrow\min\{\tau_0(i+1),T+1\} τ i ← min { τ 0 ( i + 1 ) , T + 1 } for 0 ≤ i ≤ N T 0 \le i \le N_T 0 ≤ i ≤ N T , and aborted ← \leftarrow ← false
for t = 1 , … , min { τ 0 − 1 , T } t=1,\ldots,\min\{\tau_0-1,T\} t = 1 , … , min { τ 0 − 1 , T } do
play u t = K 0 x t + η t u_t=K_0x_t+\eta_t u t = K 0 x t + η t , where η t ∼ i . i . d . N ( 0 , σ 2 I m ) \eta_t \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} \mathcal{N}(0,\sigma^2 I_m) η t ∼ i.i.d. N ( 0 , σ 2 I m )
for epoch i = 0 , … , N T − 1 i=0,\ldots,N_T-1 i = 0 , … , N T − 1 do
compute Θ ^ τ i \widehat{\Theta}_{\tau_i} Θ τ i by (7)
if no P ^ τ i ≻ 0 \widehat{P}_{\tau_i}\succ0 P τ i ≻ 0 solves the estimated DARE with S ^ τ i ≻ 0 \widehat{S}_{\tau_i}\succ0 S τ i ≻ 0 and stable estimated closed loop, or ∥ K ( Θ ^ τ i ) ∥ > κ \lVert K(\widehat{\Theta}_{\tau_i})\rVert>\kappa ∥ K ( Θ τ i )∥ > κ then
aborted ← \leftarrow ← true
for t = τ i , … , τ i + 1 − 1 t=\tau_i,\ldots,\tau_{i+1}-1 t = τ i , … , τ i + 1 − 1 do
if ∥ x t ∥ 2 > x b \lVert x_t\rVert^2>x_b ∥ x t ∥ 2 > x b then aborted ← \leftarrow ← true
play u t = K 0 x t u_t=K_0x_t u t = K 0 x t if aborted, else u t = K τ i x t u_t=K_{\tau_i}x_t u t = K τ i x t with K τ i = K ( Θ ^ τ i ) K_{\tau_i}=K(\widehat{\Theta}_{\tau_i}) K τ i = K ( Θ τ i )
Regret guarantee
Theorem 4 Let Assumption 1 hold, and suppose CI holds at θ ⋆ \theta_\star θ ⋆ . Run Algorithm 1 with the parameters of Equation (8) . Then, for every T ≥ 1 T\ge1 T ≥ 1 ,
E [ R T ] ≤ C log 2 ( 5 T ) , \mathbb{E}[R_T]\le C\log^2(5T), E [ R T ] ≤ C log 2 ( 5 T ) , where C < ∞ C<\infty C < ∞ depends on the problem parameters and the supplied bounds, but not on T T T .
Proof sketch. The full proof, including an explicit expression for C C C , is given in Appendix C. We first bound the expected regret incurred during the warm-up by O ( τ 0 ) = O ( log T ) O(\tau_0)=O(\log T) O ( τ 0 ) = O ( log T ) . We then analyze the remaining rounds separately on a success event and its complement. On the success event, the warm-up produces an estimate sufficiently close to the true model that its CE gain is well defined and stabilizing. State bounds and estimation confidence bounds ensure that subsequent estimates remain in this neighborhood, so the algorithm never aborts. CI then bounds the suboptimality of each estimated controller by the closed-loop prediction error of the estimated model under that controller. A self-normalized confidence bound (Abbasi-Yadkori and Szepesvári, 2011) and the elliptical-potential lemma (Abbasi-Yadkori et al., 2011) bound the cumulative prediction error, each contributing one logarithmic factor, which yields the O ( log 2 T ) O(\log^2 T) O ( log 2 T ) term. Finally, the choices of τ 0 \tau_0 τ 0 , x b x_b x b , λ \lambda λ ensure that the failure event has probability at most T − 2 T^{-2} T − 2 . The abort mechanism controls the cost incurred on this event by switching to K 0 K_0 K 0 , yielding an O ( 1 ) O(1) O ( 1 ) contribution to expected regret.
Knowledge of the horizon. Similarly to Cassel et al. [5 ] , Algorithm 1 requires knowledge of the horizon T T T , which is used to ensure that the probability of the failure event is at most T − 2 T^{-2} T − 2 and that the states collected in every epoch are sufficiently informative. We expect that this requirement can be removed, e.g., by allowing the algorithm to resume CE even after using K 0 K_0 K 0 (Jedra and Proutiere, [11 ] ), and by using epochs that only end once sufficiently informative data have been collected (Bartos et al., [3 ] ). We leave this extension for future work.
Verifying CI. Theorem 4 requires CI at the unknown parameter θ ⋆ \theta_\star θ ⋆ , which in general cannot be checked before learning. In some problem classes, however, CI follows from the prior knowledge available to the learner. For example, if B ⋆ B_\star B ⋆ is known, as in Cassel et al. [5 ] and Jedra and Proutiere [11 ] , one can show that I ⋆ ≻ 0 \mathcal{I}_\star\succ0 I ⋆ ≻ 0 , so CI holds for every R ⪰ 0 R \succeq0 R ⪰ 0 . Their setting with known A ⋆ A_\star A ⋆ also satisfies CI under their additional condition K ⋆ K ⋆ ⊤ ≻ 0 K_\star K_\star^\top\succ0 K ⋆ K ⋆ ⊤ ≻ 0 . In both settings, however, all parameters are identifiable under optimal feedback. We show in § 5 that, for MVC (R = 0 R = 0 R = 0 ), CI holds whenever range ( B ⋆ ) \operatorname{range}(B_\star) range ( B ⋆ ) is known, an interpretable condition on the model class under which up to m 2 m^2 m 2 parameter directions remain invisible under optimal feedback.
Comparison with local minimax guarantees. Liu [17 ] proves local minimax guarantees for R ≻ 0 R \succ0 R ≻ 0 : assuming CI at a known nominal parameter, O ( log T ) O(\log T) O ( log T ) regret bounds hold uniformly over neighborhoods of radius O ( T − 1 / 4 ) O(T^{-1/4}) O ( T − 1/4 ) around it, and over neighborhoods of sufficiently small fixed radius if the nominal state matrix is nonsingular, although in this case CI excludes nontrivial invisible directions. Our algorithm instead requires no nominal model and achieves O ( log 2 T ) O(\log^2 T) O ( log 2 T ) expected regret at every fixed unknown parameter satisfying CI, but its constant degrades as the true system approaches one where CI fails (§ 4.2 ). Hence, neither type of guarantee implies the other.
Regret Lower Bound
We now show that the bound of Theorem 4 cannot hold uniformly over the following family of systems, which includes a system where CI fails. Fix r ≥ 0 r \ge0 r ≥ 0 and consider the family defined by the affine model
A = [ 0 1 / 4 0 0 ] , B θ = [ θ 1 ] , ∣ θ ∣ ≤ 0.05 , (9) A = \begin{bmatrix} 0 & 1/4 \\ 0 & 0 \end{bmatrix}, \qquad B_\theta= \begin{bmatrix} \theta\\ 1 \end{bmatrix}, \qquad\lvert\theta\rvert\le0.05, \tag*{(9)} A = [ 0 0 1/4 0 ] , B θ = [ θ 1 ] , ∣ θ ∣ ≤ 0.05 , (9)
with Q = I 2 Q = I_2 Q = I 2 , R = r R = r R = r , σ = 1 \sigma= 1 σ = 1 , and x 1 = 0 x_1 = 0 x 1 = 0 , where θ \theta θ is the unknown parameter and K 0 = 0 K_0 = 0 K 0 = 0 stabilizes every system in the family. At θ = 0 \theta= 0 θ = 0 , the optimal controller applies zero input. Since θ \theta θ appears only in the input matrix, observations under this controller contain no information about θ \theta θ . Nevertheless, controllers designed for nearby parameters incur a quadratic increase in cost on the θ = 0 \theta= 0 θ = 0 system, so this invisible direction is not harmless and CI fails. For every θ ≠ 0 \theta\ne0 θ = 0 , the scalar Fisher information I θ ( K ( θ ) ) \mathcal{I}_\theta(K(\theta)) I θ ( K ( θ )) is positive, so there is no nonzero invisible parameter direction and CI holds. However, as θ \theta θ approaches zero, the optimal controller uses progressively smaller inputs, so the data become less informative about θ \theta θ . Consequently, the constant in Theorem 4 deteriorates even though CI continues to hold at every nonzero $\theta ({xref}Appendix D`). The following theorem shows that this cannot be avoided.
Theorem 5 For every fixed r ≥ 0 r \ge0 r ≥ 0 and every T ≥ 10 4 T \ge10^4 T ≥ 1 0 4 , over the above family of systems
inf π sup ∣ θ ∣ ≤ 0.05 E θ [ R T ] ≥ 3.6 ⋅ 10 − 4 1 + r T − 2.4. \inf_{\pi}\sup_{\lvert\theta\rvert\le0.05} \mathbb{E}_\theta[R_T] \ge\frac{3.6 \cdot10^{-4}}{1+r}\sqrt{T} - 2.4. π inf ∣ θ ∣ ≤ 0.05 sup E θ [ R T ] ≥ 1 + r 3.6 ⋅ 1 0 − 4 T − 2.4. where the infimum is over all causal, possibly randomized policies.
Proof sketch. The full proof is given in Appendix § 11 . We compare two systems with θ = ± Δ \theta= \pm\Delta θ = ± Δ , where Δ = T − 1 / 4 / 2 \Delta= T^{-1/4}/2 Δ = T − 1/4 /2 . To keep regret small, the learner must choose inputs close to optimal feedback. In both systems, these inputs are small, so the resulting observations provide too little information to distinguish the two parameter values reliably. Distinguishing them matters because their optimal controllers prescribe opposite actions. These actions differ by order Δ \Delta Δ whenever the second state component is bounded away from zero, which Gaussian noise ensures with constant probability. The learner therefore cannot stay close to both optimal controllers. Averaging over the two systems, the resulting control errors yield a regret lower bound of order T Δ 2 T\Delta^2 T Δ 2 , and hence T \sqrt{T} T , even when R = 0 R = 0 R = 0 .
Theorem 5 gives a worst-case regret lower bound of order T \sqrt{T} T over this family, which includes the system θ = 0 \theta= 0 θ = 0 , where CI fails. The bound remains valid when R = 0 R = 0 R = 0 , so the absence of an input penalty alone does not guarantee polylogarithmic minimax regret. Since both systems used in the proof have θ ≠ 0 \theta\ne0 θ = 0 , the same lower bound holds over the subfamily obtained by removing θ = 0 \theta= 0 θ = 0 , in which every system satisfies CI. This is consistent with Theorem 4, since its instance-specific constant C C C is finite for every fixed θ ≠ 0 \theta\ne0 θ = 0 but not uniformly bounded as θ \theta θ approaches zero.
Minimum Variance Control
We consider MVC in the state-space setting of § 2 , with no input penalty (R = 0 R = 0 R = 0 ). The objective is therefore to minimize the stationary weighted state variance E [ x T Q x ] \mathbb{E}[x^{\mathsf{T}}Qx] E [ x T Q x ] .
Corollary 6 (Minimum variance control) Let R = 0 R = 0 R = 0 , suppose Assumption 1 holds, and consider the model class C = { [ A B ] : A ∈ R n × n , B ∈ B } \mathcal{C} = \{[A\ B] : A \in\mathbb{R}^{n \times n},\ B \in\mathcal{B}\} C = {[ A B ] : A ∈ R n × n , B ∈ B } , where B ⊃ B ⋆ \mathcal{B} \supset B_{\star} B ⊃ B ⋆ is a known affine set. If range ( B ) ⊆ range ( B ⋆ ) \operatorname{range}(B) \subseteq\operatorname{range}(B_{\star}) range ( B ) ⊆ range ( B ⋆ ) for every B ∈ B B \in\mathcal{B} B ∈ B , then CI holds at θ ⋆ \theta_{\star} θ ⋆ , and the regret bound of Theorem 4 applies. Conversely, if rank [ A ⋆ B ⋆ ] = n \operatorname{rank}[A_{\star}\ B_{\star}] = n rank [ A ⋆ B ⋆ ] = n , CI holds only if this range condition holds.
The proof is given in Appendix B. The range condition means that the learner knows range ( B ⋆ ) \operatorname{range}(B_{\star}) range ( B ⋆ ) , the subspace through which inputs enter the state equation. Let U U U have orthonormal columns spanning this subspace. The largest affine set satisfying the range condition is B = { U Γ : Γ ∈ R n × m } \mathcal{B} = \{U\Gamma: \Gamma\in\mathbb{R}^{n \times m}\} B = { U Γ : Γ ∈ R n × m } . In this class, ker I ⋆ \operatorname{ker} I_{\star} ker I ⋆ has dimension m 2 m^2 m 2 . Corollary 6 guarantees CI, so all these invisible directions are harmless. When A ⋆ A_{\star} A ⋆ is nonsingular, this attains the bound of Lemma 3, whereas CI would fail for this model class under any positive definite input penalty R ≻ 0 R \succ0 R ≻ 0 .
Knowing range ( B ⋆ ) \operatorname{range}(B_{\star}) range ( B ⋆ ) requires less prior information than knowing the full matrix B ⋆ B_{\star} B ⋆ , as assumed in the corresponding result of Cassel et al. [5 ] for R ≻ 0 R \succ0 R ≻ 0 . For square, nonsingular input matrices, as assumed in Lai’s [13 ] stochastic regression model, the range is R n \mathbb{R}^{n} R n , so the range condition holds automatically, whereas our corollary also covers underactuated systems with m < n m < n m < n , provided range ( B ⋆ ) \operatorname{range}(B_{\star}) range ( B ⋆ ) is known. Finally, note that in the lower-bound family of § 4.2 , A ⋆ A_{\star} A ⋆ is known but range ( B ⋆ ) \operatorname{range}(B_{\star}) range ( B ⋆ ) is not. There, the constant of Theorem 4 degrades because σ min + ( D ⋆ ) → 0 \sigma_{\min}^{+}(D_{\star}) \to0 σ m i n + ( D ⋆ ) → 0 as θ → 0 \theta\to0 θ → 0 . In contrast, σ min + ( D ⋆ ) ≥ 1 \sigma_{\min}^{+}(D_{\star}) \ge1 σ m i n + ( D ⋆ ) ≥ 1 in the class of Corollary 6 (Appendix B) and λ min ( S ⋆ ) ≥ α 0 σ min ( B ⋆ ) 2 \lambda_{\min}(S_{\star}) \ge\alpha_{0}\sigma_{\min}(B_{\star})^{2} λ m i n ( S ⋆ ) ≥ α 0 σ m i n ( B ⋆ ) 2 . Hence, the constant C C C of Theorem 4 is uniformly bounded over all systems in this class that satisfy the norm and cost bounds of § 4.1.1 and have σ min ( B ⋆ ) \sigma_{\min}(B_{\star}) σ m i n ( B ⋆ ) bounded away from zero (Remark 14).
Cart–Pole Case Study
We consider a case study of learning to balance a pole upright on a cart. The cart has mass M c > 0 M_{\mathrm{c}} > 0 M c > 0 , and the pole is modeled as a point mass M p > 0 M_{\mathrm{p}} > 0 M p > 0 attached to the cart by a massless rigid rod of length ℓ > 0 \ell> 0 ℓ > 0 . The controller applies a horizontal force F = g u u F = g_{u}u F = g u u to the cart, where u ∈ R u \in\mathbb{R} u ∈ R is the controller command and g u > 0 g_{u} > 0 g u > 0 is the actuator gain. We use the state x = ( p , ϕ , p ˙ , ϕ ˙ ) T x = (p,\phi,\dot{p},\dot{\phi})^{\mathsf{T}} x = ( p , ϕ , p ˙ , ϕ ˙ ) T , where p p p is the cart position and ϕ \phi ϕ is the pole’s angular deviation from upright. We linearize the equations of motion in Tedrake [24 ] around the unstable upright equilibrium ( x , u ) = ( 0 , 0 ) (x,u) = (0,0) ( x , u ) = ( 0 , 0 ) , with g g g denoting gravitational acceleration. Discretizing the resulting dynamics using the forward-Euler method with sampling interval h > 0 h > 0 h > 0 gives
A d = I 4 + h [ 0 0 1 0 0 0 0 1 0 M p g M c 0 0 0 ( M c + M p ) g M c ℓ 0 0 ] , B d = h g u M c [ 0 0 1 1 / ℓ ] . A_d = I_4 + h\begin{bmatrix}
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & \frac{M_{\mathrm{p}}g}{M_{\mathrm{c}}} & 0 & 0 \\
0 & \frac{(M_{\mathrm{c}}+M_{\mathrm{p}})g}{M_{\mathrm{c}}\ell} & 0 & 0
\end{bmatrix},
\qquad
B_d = h\frac{g_u}{M_{\mathrm{c}}}\begin{bmatrix}
0 \\
0 \\
1 \\
1/\ell
\end{bmatrix}. A d = I 4 + h 0 0 0 0 0 0 M c M p g M c ℓ ( M c + M p ) g 1 0 0 0 0 1 0 0 , B d = h M c g u 0 0 1 1/ ℓ .
Notably, the pole length, which can be easily measured in practice, suffices to determine range(B d B_d B d ), whereas identifying B d B_d B d would additionally require the scale h g u / M c h g_u/M_c h g u / M c . Since A d A_d A d is nonsingular for small h h h , Corollary 6 implies that CI holds for MVC if and only if the learner knows range(B d B_d B d ). Figure 1 compares two learners: one knows range(B d B_d B d ) and estimates only the scaling, while the other estimates the last two entries of B d B_d B d independently. With the range known, the observed regret is consistent with the polylogarithmic upper bound. Without this information, regret grows visibly faster.
Figure 1. Expected regret of Algorithm 1, estimated via (15) , for minimum variance control of the linearized cart–pole, with and without knowledge of range(B d B_d B d ). We report the mean and the standard error over 100 seeds. We use h = 0.05 h = 0.05 h = 0.05 , M c = 1 M_c = 1 M c = 1 , M p = 0.1 M_p = 0.1 M p = 0.1 , ℓ = 0.5 \ell= 0.5 ℓ = 0.5 , g = 9.81 g = 9.81 g = 9.81 , g u = 20 g_u = 20 g u = 20 , Q = I 4 Q = I_4 Q = I 4 , σ = 0.05 \sigma= 0.05 σ = 0.05 , and T = 7 ⋅ 10 5 T = 7 \cdot10^5 T = 7 ⋅ 1 0 5 ; since the constants of Remark 15 are conservative, we set τ 0 = 2000 \tau_0 = 2000 τ 0 = 2000 and choose the norm thresholds heuristically (they were never triggered in the reported runs).
Conclusion
This work studied when certainty equivalence achieves polylogarithmic regret in online LQR with possibly singular input penalties. We extended controller identifiability to this setting and showed that it suffices for O ( log 2 T ) O(\log^2 T) O ( log 2 T ) expected regret. Our results clarify how singular input penalties can make parameter directions that are unidentifiable under optimal feedback harmless for control. In MVC, knowing range(B ⋆ B_\star B ⋆ ) suffices for controller identifiability, allowing polylogarithmic regret without identifying all system parameters. A complementary lower bound shows that the absence of an input penalty alone does not guarantee polylogarithmic minimax regret.
An interesting direction for future work is to carry these insights over to nonlinear control by extending the analysis of Wang et al. [26 ] . In particular, one could investigate whether their persistent-excitation condition under the optimal policy can be relaxed to a nonlinear analogue of CI.
Generative AI Use
Generative AI tools have only been used in this work for text polishing, code assistance, and checking mathematical proofs. All ideas, derivations, and conclusions presented in this work remain the sole responsibility of the authors.
Acknowledgments
Bruce D. Lee was supported by an ETH AI Center Postdoctoral Fellowship. This work was also supported in part by NCCR Automation, a National Centre of Competence in Research, funded by the Swiss National Science Foundation (grant number 51NF40_225155).
Technical Lemmas
This appendix collects properties of the Riccati equation for possibly singular R R R . We retain the notation from § 2 and impose Assumption 1, with Q ⪰ α 0 I ≻ 0 Q \succeq\alpha_0 I \succ0 Q ⪰ α 0 I ≻ 0 , R ⪰ 0 R \succeq0 R ⪰ 0 , and max { ∥ Q ∥ , ∥ R ∥ } ≤ α 1 \max\{\lVert Q\rVert,\lVert R\rVert\} \le\alpha_1 max {∥ Q ∥ , ∥ R ∥} ≤ α 1 as in § 4.1.1 . Lemma, equation, and section numbers of Mania et al. [18 ] refer to its extended version, arXiv:1902.07826.
Riccati Well-Posedness
The following proposition collects well-known properties of the discrete algebraic Riccati equation, under the conditions of Assumption 1. A short proof is provided below for completeness.
Proposition 7 Suppose that ( A , B ) (A,B) ( A , B ) is stabilizable, Q ≻ 0 Q \succ0 Q ≻ 0 , R ⪰ 0 R \succeq0 R ⪰ 0 and ker R ∩ ker B = { 0 } \ker R \cap\ker B = \{0\} ker R ∩ ker B = { 0 } . Then the DARE
P = Q + A T P A − A T P B ( R + B T P B ) − 1 B T P A (10) P = Q + A^{\mathsf{T}} P A - A^{\mathsf{T}} P B(R + B^{\mathsf{T}} P B)^{-1}B^{\mathsf{T}} P A \tag*{(10)} P = Q + A T P A − A T P B ( R + B T P B ) − 1 B T P A (10) has a unique positive definite solution P P P , and, for every x 0 ∈ R n x_0 \in\mathbb{R}^n x 0 ∈ R n ,
x 0 T P x 0 = inf u 0 , u 1 , … ∑ t ≥ 0 ( x t T Q x t + u t T R u t ) , (11) x_0^{\mathsf{T}} P x_0 = \inf_{u_0,u_1,\ldots} \sum_{t \ge0}(x_t^{\mathsf{T}}Qx_t + u_t^{\mathsf{T}}Ru_t), \tag*{(11)} x 0 T P x 0 = u 0 , u 1 , … inf t ≥ 0 ∑ ( x t T Q x t + u t T R u t ) , (11) where x t + 1 = A x t + B u t x_{t+1}=Ax_t+Bu_t x t + 1 = A x t + B u t . With K = − ( R + B T P B ) − 1 B T P A K=-(R+B^{\mathsf{T}}PB)^{-1}B^{\mathsf{T}}PA K = − ( R + B T P B ) − 1 B T P A , the matrix A + B K A+BK A + B K is Schur stable, u t = K x t u_t=Kx_t u t = K x t is the unique stationary linear policy attaining the infimum in (11) from every initial state, and K K K is the unique minimizer of the average cost J [ A B ] J_{[A\ B]} J [ A B ] in (4) . Conversely, if Q ≻ 0 Q \succ0 Q ≻ 0 , R ⪰ 0 R \succeq0 R ⪰ 0 , ker R ∩ ker B = { 0 } \ker R \cap\ker B=\{0\} ker R ∩ ker B = { 0 } , and (10) has a positive definite solution, then ( A , B ) (A,B) ( A , B ) is stabilizable.
Proof. Stabilizability makes the cost in (11) finite for every x 0 x_0 x 0 , so Ferrante and Ntogramatzidis [7 ] gives a solution P ⪰ 0 P \succeq0 P ⪰ 0 of the generalized DARE satisfying (11) , and P ⪰ Q ≻ 0 P \succeq Q \succ0 P ⪰ Q ≻ 0 since the cost is at least x 0 T Q x 0 x_0^{\mathsf{T}}Qx_0 x 0 T Q x 0 . By the kernel assumption, R + B T P B ≻ 0 R+B^{\mathsf{T}}PB \succ0 R + B T P B ≻ 0 , so P P P solves (10) and, by the same theorem, u t = K x t u_t=Kx_t u t = K x t is the unique optimal input. Since Q ≻ 0 Q \succ0 Q ≻ 0 , Lyapunov’s theorem shows that every positive definite solution of (10) is stabilizing, which gives the Schur stability of A + B K A+BK A + B K and the converse; uniqueness then follows from Ionescu and Weiss [10 ] .
For the average cost, quadratic completion gives, with S = R + B T P B S=R+B^{\mathsf{T}}PB S = R + B T P B ,
x T Q x + u T R u + ( A x + B u ) T P ( A x + B u ) − x T P x = ( u − K x ) T S ( u − K x ) . (12) x^{\mathsf{T}}Qx+u^{\mathsf{T}}Ru+(Ax+Bu)^{\mathsf{T}}P(Ax+Bu)-x^{\mathsf{T}}Px=(u-Kx)^{\mathsf{T}}S(u-Kx). \tag*{(12)} x T Q x + u T R u + ( A x + B u ) T P ( A x + B u ) − x T P x = ( u − K x ) T S ( u − K x ) . (12)
For a gain G G G stabilizing ( A , B ) (A,B) ( A , B ) , the Lyapunov and covariance equations give, with J = J [ A B ] J=J_{[A\ B]} J = J [ A B ] ,
P G = Q + G T R G + ( A + B G ) T P G ( A + B G ) , J ( G ) = σ 2 Tr ( P G ) , P G ≻ 0 , (13) \begin{aligned}
P_G &= Q+G^{\mathsf{T}}RG+(A+BG)^{\mathsf{T}}P_G(A+BG),\\
J(G) &= \sigma^2\operatorname{Tr}(P_G),\qquad P_G \succ0, \tag*{(13)}
\end{aligned} P G J ( G ) = Q + G T R G + ( A + B G ) T P G ( A + B G ) , = σ 2 Tr ( P G ) , P G ≻ 0 , (13)
and taking stationary expectations in (12) with u = G x u=Gx u = G x yields
J ( G ) − σ 2 Tr ( P ) = Tr ( Σ G ( G − K ) T ( R + B T P B ) ( G − K ) ) , (14) J(G)-\sigma^2\operatorname{Tr}(P)=\operatorname{Tr}\left(\Sigma_G(G-K)^{\mathsf{T}}(R+B^{\mathsf{T}}PB)(G-K)\right), \tag*{(14)} J ( G ) − σ 2 Tr ( P ) = Tr ( Σ G ( G − K ) T ( R + B T P B ) ( G − K ) ) , (14)
where Σ G = σ 2 ∑ j ≥ 0 ( A + B G ) j ( ( A + B G ) j ) T ⪰ σ 2 I \Sigma_G=\sigma^2\sum_{j\ge0}(A+BG)^j((A+BG)^j)^{\mathsf{T}}\succeq\sigma^2 I Σ G = σ 2 ∑ j ≥ 0 ( A + B G ) j (( A + B G ) j ) T ⪰ σ 2 I is the stationary state covariance. This is the identity of Mania et al. [18 ] , which assumes R ≻ 0 R \succ0 R ≻ 0 ; the derivation above uses only R + B T P B ≻ 0 R+B^{\mathsf{T}}PB \succ0 R + B T P B ≻ 0 . Hence J ( G ) > J ( K ) J(G)>J(K) J ( G ) > J ( K ) for every stabilizing G ≠ K G\ne K G = K . If instead ρ ( A + B G ) ≥ 1 \rho(A + BG) \ge1 ρ ( A + B G ) ≥ 1 , then ∥ ( A + B G ) j ∥ F ≥ 1 \|(A + BG)^j\|_F \ge1 ∥ ( A + B G ) j ∥ F ≥ 1 for all j j j , so E ∥ x t ∥ 2 ≥ σ 2 ( t − 1 ) \mathbb{E}\|x_t\|^2 \ge\sigma^2(t - 1) E ∥ x t ∥ 2 ≥ σ 2 ( t − 1 ) and, since Q ≻ 0 Q \succ0 Q ≻ 0 , the average cost is infinite.
For any causal policy with finite second moments, taking expectations in (12) at ( A ⋆ , B ⋆ ) (A_\star, B_\star) ( A ⋆ , B ⋆ ) and telescoping gives
E [ R T ] = E [ ∑ t = 1 T ( u t − K ⋆ x t ) ⊤ S ⋆ ( u t − K ⋆ x t ) ] + x 1 ⊤ P ⋆ x 1 − E [ x T + 1 ⊤ P ⋆ x T + 1 ] . (15) \mathbb{E}[R_T] = \mathbb{E}\left[\sum_{t=1}^{T}(u_t-K_\star x_t)^\top S_\star(u_t-K_\star x_t)\right] + x_1^\top P_\star x_1-\mathbb{E}[x_{T+1}^\top P_\star x_{T+1}]. \tag*{(15)} E [ R T ] = E [ t = 1 ∑ T ( u t − K ⋆ x t ) ⊤ S ⋆ ( u t − K ⋆ x t ) ] + x 1 ⊤ P ⋆ x 1 − E [ x T + 1 ⊤ P ⋆ x T + 1 ] . (15)
Here independence and centering of w t w_t w t contribute σ 2 Tr ( P ⋆ ) = J ⋆ \sigma^2\operatorname{Tr}(P_\star)=J_\star σ 2 Tr ( P ⋆ ) = J ⋆ per step. This is the matrix counterpart of Cassel et al. [5 ] .
Lyapunov Inverse and Matrix Powers
Lemma 8 (cf. Mania et al. [18 ] ) Let L ⋆ L_\star L ⋆ be Schur stable, fix γ ⋆ ∈ ( ρ ( L ⋆ ) , 1 ) \gamma_\star\in(\rho(L_\star),1) γ ⋆ ∈ ( ρ ( L ⋆ ) , 1 ) , and put
τ ⋆ ≥ sup j ≥ 0 ∥ L ⋆ j ∥ γ ⋆ − j , L T = τ ⋆ 2 1 − γ ⋆ 2 . \tau_\star\ge\sup_{j\ge0}\|L_\star^j\|\gamma_\star^{-j}, \qquad L_T=\frac{\tau_\star^2}{1-\gamma_\star^2}. τ ⋆ ≥ j ≥ 0 sup ∥ L ⋆ j ∥ γ ⋆ − j , L T = 1 − γ ⋆ 2 τ ⋆ 2 . The operator T ( X ) = X − L ⋆ ⊤ X L ⋆ \mathcal{T}(X)=X-L_\star^\top XL_\star T ( X ) = X − L ⋆ ⊤ X L ⋆ is invertible and
T − 1 ( Y ) = ∑ j = 0 ∞ ( L ⋆ ⊤ ) j Y L ⋆ j , ∥ T − 1 ( Y ) ∥ F ≤ L T ∥ Y ∥ F . (16) \mathcal{T}^{-1}(Y)=\sum_{j=0}^{\infty}(L_\star^\top)^jYL_\star^j,\qquad\|\mathcal{T}^{-1}(Y)\|_F\le L_T\|Y\|_F. \tag*{(16)} T − 1 ( Y ) = j = 0 ∑ ∞ ( L ⋆ ⊤ ) j Y L ⋆ j , ∥ T − 1 ( Y ) ∥ F ≤ L T ∥ Y ∥ F . (16) Moreover, for every square matrix E E E and integer j ≥ 0 j\ge0 j ≥ 0 ,
∥ ( L ⋆ + E ) j ∥ ≤ τ ⋆ ( γ ⋆ + τ ⋆ ∥ E ∥ ) j . (17) \|(L_\star+E)^j\|\le\tau_\star(\gamma_\star+\tau_\star\|E\|)^j. \tag*{(17)} ∥ ( L ⋆ + E ) j ∥ ≤ τ ⋆ ( γ ⋆ + τ ⋆ ∥ E ∥ ) j . (17)
Proof. The series representation and the spectral-norm bound are in Mania et al. [18 ] , and the power estimate is Mania et al. [18 ] with M = L ⋆ M=L_\star M = L ⋆ , ρ = γ ⋆ \rho=\gamma_\star ρ = γ ⋆ , and Δ = E \Delta=E Δ = E ; finiteness of τ ⋆ \tau_\star τ ⋆ follows from Gelfand’s formula Mania et al., [18 ] . The Frobenius bound follows from the same series, since ∥ ( L ⋆ ⊤ ) j Y L ⋆ j ∥ F ≤ τ ⋆ 2 γ ⋆ 2 j ∥ Y ∥ F \|(L_\star^\top)^jYL_\star^j\|_F\le\tau_\star^2\gamma_\star^{2j}\|Y\|_F ∥ ( L ⋆ ⊤ ) j Y L ⋆ j ∥ F ≤ τ ⋆ 2 γ ⋆ 2 j ∥ Y ∥ F . These statements involve only L ⋆ L_\star L ⋆ , so they do not depend on the standing assumption R ≻ 0 R\succ0 R ≻ 0 of Mania et al. [18 ] .
For the optimal closed loop, the Bellman equation P ⋆ = Q + K ⋆ ⊤ R K ⋆ + L ⋆ ⊤ P ⋆ L ⋆ P_\star=Q+K_\star^\top RK_\star+L_\star^\top P_\star L_\star P ⋆ = Q + K ⋆ ⊤ R K ⋆ + L ⋆ ⊤ P ⋆ L ⋆ gives L ⋆ ⊤ P ⋆ L ⋆ ⪯ ( 1 − α 0 / ∥ P ⋆ ∥ ) P ⋆ L_\star^\top P_\star L_\star\preceq(1-\alpha_0/\|P_\star\|)P_\star L ⋆ ⊤ P ⋆ L ⋆ ⪯ ( 1 − α 0 /∥ P ⋆ ∥ ) P ⋆ , hence ∥ L ⋆ j ∥ ≤ ∥ P ⋆ ∥ / λ min ( P ⋆ ) ( 1 − α 0 / ∥ P ⋆ ∥ ) j / 2 \|L_\star^j\|\le\sqrt{\|P_\star\|/\lambda_{\min}(P_\star)}(1-\alpha_0/\|P_\star\|)^{j/2} ∥ L ⋆ j ∥ ≤ ∥ P ⋆ ∥/ λ m i n ( P ⋆ ) ( 1 − α 0 /∥ P ⋆ ∥ ) j /2 . Since σ 2 ∥ P ⋆ ∥ ≤ J ⋆ ≤ ν \sigma^2\|P_\star\|\le J_\star\le\nu σ 2 ∥ P ⋆ ∥ ≤ J ⋆ ≤ ν and P ⋆ ⪰ Q ⪰ α 0 I P_\star\succeq Q\succeq\alpha_0 I P ⋆ ⪰ Q ⪰ α 0 I , the computable pair
τ ⋆ = ν α 0 σ 2 , γ ⋆ = 1 − α 0 σ 2 2 ν \tau_\star=\sqrt{\frac{\nu}{\alpha_0\sigma^2}},\qquad\gamma_\star=\sqrt{1-\frac{\alpha_0\sigma^2}{2\nu}} τ ⋆ = α 0 σ 2 ν , γ ⋆ = 1 − 2 ν α 0 σ 2
is admissible, and ∥ L ⋆ ∥ ≤ τ ⋆ \|L_\star\|\le\tau_\star ∥ L ⋆ ∥ ≤ τ ⋆ .
Riccati Sensitivity
In this section, we introduce some notation and derive several technical preliminary identities that will be used in the proof of the Riccati sensitivity bound in Lemma 9 . For a symmetric matrix P P P , define
S A , B ( P ) = R + B T P B , K A , B ( P ) = − S A , B ( P ) − 1 B T P A , L A , B ( P ) = A + B K A , B ( P ) , F A , B ( P ) = Q + A T P A − A T P B S A , B ( P ) − 1 B T P A . (18) \begin{aligned}
S_{A,B}(P) &= R + B^{\mathsf{T}}PB,\\
K_{A,B}(P) &= -S_{A,B}(P)^{-1}B^{\mathsf{T}}PA,\\
L_{A,B}(P) &= A + BK_{A,B}(P),\\
F_{A,B}(P) &= Q + A^{\mathsf{T}}PA - A^{\mathsf{T}}PBS_{A,B}(P)^{-1}B^{\mathsf{T}}PA. \tag*{(18)}
\end{aligned} S A , B ( P ) K A , B ( P ) L A , B ( P ) F A , B ( P ) = R + B T P B , = − S A , B ( P ) − 1 B T P A , = A + B K A , B ( P ) , = Q + A T P A − A T P B S A , B ( P ) − 1 B T P A . (18)
whenever S A , B ( P ) ≻ 0 S_{A,B}(P) \succ0 S A , B ( P ) ≻ 0 . Under the standing assumptions, Proposition 7 supplies the reference solution P ⋆ = F A ⋆ , B ⋆ ( P ⋆ ) ≻ 0 P_{\star} = F_{A_{\star},B_{\star}}(P_{\star}) \succ0 P ⋆ = F A ⋆ , B ⋆ ( P ⋆ ) ≻ 0 and a stabilizing gain, with
S ⋆ = R + B ⋆ T P ⋆ B ⋆ ≻ 0 , K ⋆ = K A ⋆ , B ⋆ ( P ⋆ ) , L ⋆ = A ⋆ + B ⋆ K ⋆ . S_{\star} = R + B_{\star}^{\mathsf{T}}P_{\star}B_{\star} \succ0,\qquad K_{\star} = K_{A_{\star},B_{\star}}(P_{\star}),\qquad L_{\star} = A_{\star} + B_{\star}K_{\star}. S ⋆ = R + B ⋆ T P ⋆ B ⋆ ≻ 0 , K ⋆ = K A ⋆ , B ⋆ ( P ⋆ ) , L ⋆ = A ⋆ + B ⋆ K ⋆ .
For P ≻ 0 P \succ0 P ≻ 0 and S = R + B T P B ≻ 0 S = R + B^{\mathsf{T}}PB \succ0 S = R + B T P B ≻ 0 , write K = K A , B ( P ) K = K_{A,B}(P) K = K A , B ( P ) , L = A + B K L = A + BK L = A + B K , W = B S − 1 B T W = BS^{-1}B^{\mathsf{T}} W = B S − 1 B T , and ℓ = λ min ( P ) \ell= \lambda_{\min}(P) ℓ = λ m i n ( P ) . The matrix C = P 1 / 2 B S − 1 / 2 C = P^{1/2}BS^{-1/2} C = P 1/2 B S − 1/2 satisfies C T C ⪯ I C^{\mathsf{T}}C \preceq I C T C ⪯ I because S ⪰ B T P B S \succeq B^{\mathsf{T}}PB S ⪰ B T P B . Using C C T ⪯ I CC^{\mathsf{T}} \preceq I C C T ⪯ I and I − W P = P − 1 / 2 ( I − C C T ) P 1 / 2 I - WP = P^{-1/2}(I - CC^{\mathsf{T}})P^{1/2} I − W P = P − 1/2 ( I − C C T ) P 1/2 therefore gives
0 ⪯ P 1 / 2 W P 1 / 2 ⪯ I , ∥ W ∥ ≤ ℓ − 1 , ∥ I − W P ∥ ≤ ∥ P ∥ / ℓ , ∥ B S − 1 / 2 ∥ ≤ ℓ − 1 / 2 , ∥ S − 1 / 2 B T P ∥ ≤ ∥ P ∥ . (19) \begin{aligned}
0 &\preceq P^{1/2}WP^{1/2} \preceq I,\\
\lVert W\rVert&\le\ell^{-1},\qquad\lVert I - WP\rVert\le\sqrt{\lVert P\rVert/\ell},\\
\lVert BS^{-1/2}\rVert&\le\ell^{-1/2},\qquad\lVert S^{-1/2}B^{\mathsf{T}}P\rVert\le\sqrt{\lVert P\rVert}. \tag*{(19)}
\end{aligned} 0 ∥ W ∥ ∥ B S − 1/2 ∥ ⪯ P 1/2 W P 1/2 ⪯ I , ≤ ℓ − 1 , ∥ I − W P ∥ ≤ ∥ P ∥ / ℓ , ≤ ℓ − 1/2 , ∥ S − 1/2 B T P ∥ ≤ ∥ P ∥ . (19)
For symmetric X X X with ∥ X ∥ < ℓ \lVert X\rVert< \ell ∥ X ∥ < ℓ , attach the subscript X X X to quantities evaluated at P + X P + X P + X . Since P + X ⪰ ( 1 − ∥ X ∥ / ℓ ) P P + X \succeq(1 - \lVert X\rVert/\ell)P P + X ⪰ ( 1 − ∥ X ∥ / ℓ ) P , subtracting the stationarity equations S X K X = − B T ( P + X ) A S_XK_X = -B^{\mathsf{T}}(P + X)A S X K X = − B T ( P + X ) A and S X K = S K + B T X B K S_XK = SK + B^{\mathsf{T}}XBK S X K = S K + B T X B K , and applying the matrix inversion lemma ([4 Appendix C.4.3] ) to I + ( B S − 1 ) ( B T X ) I + (BS^{-1})(B^{\mathsf{T}}X) I + ( B S − 1 ) ( B T X ) gives
S X ⪰ ( 1 − ∥ X ∥ / ℓ ) S ≻ 0 , K X − K = − S X − 1 B T X L , L X = ( I − B S X − 1 B T X ) L = ( I + W X ) − 1 L . (20) \begin{aligned}
S_X &\succeq(1 - \lVert X\rVert/\ell)S \succ0,\qquad K_X - K = -S_X^{-1}B^{\mathsf{T}}XL,\\
L_X &= (I - BS_X^{-1}B^{\mathsf{T}}X)L = (I + WX)^{-1}L. \tag*{(20)}
\end{aligned} S X L X ⪰ ( 1 − ∥ X ∥ / ℓ ) S ≻ 0 , K X − K = − S X − 1 B T X L , = ( I − B S X − 1 B T X ) L = ( I + W X ) − 1 L . (20)
Here ∥ W X ∥ < 1 \lVert WX\rVert< 1 ∥ W X ∥ < 1 ensures invertibility. Quadratic completion, valid for every gain G G G , gives
Q + G T R G + ( A + B G ) T P ( A + B G ) = F A , B ( P ) + ( G − K ) T S ( G − K ) . (21) Q + G^{\mathsf{T}}RG + (A + BG)^{\mathsf{T}}P(A + BG) = F_{A,B}(P) + (G - K)^{\mathsf{T}}S(G - K). \tag*{(21)} Q + G T R G + ( A + B G ) T P ( A + B G ) = F A , B ( P ) + ( G − K ) T S ( G − K ) . (21)
For symmetric Z Z Z , the Riccati derivatives are
D P F A , B ( P ) [ Z ] = L T Z L , D_PF_{A,B}(P)[Z] = L^{\mathsf{T}}ZL, D P F A , B ( P ) [ Z ] = L T Z L ,
D A , B F A , B ( P ) [ Δ A , Δ B ] = ( Δ A + Δ B K ) T P L + L T P ( Δ A + Δ B K ) . (22) D_{A,B}F_{A,B}(P)[\Delta A,\Delta B] = (\Delta A + \Delta BK)^{\mathsf{T}}PL + L^{\mathsf{T}}P(\Delta A + \Delta BK). \tag*{(22)} D A , B F A , B ( P ) [ Δ A , Δ B ] = ( Δ A + Δ B K ) T P L + L T P ( Δ A + Δ B K ) . (22)
The first is Guo [8 ] , whose domain only requires S S S invertible. For the second, apply (21) at ( A + t Δ A , B + t Δ B ) (A + t\Delta A, B + t\Delta B) ( A + t Δ A , B + t Δ B ) with G = K G = K G = K fixed. The gain K t = K A t , B t ( P ) K_t = K_{A_t,B_t}(P) K t = K A t , B t ( P ) and input curvature S t = R + B t T P B t S_t = R + B_t^{\mathsf{T}}PB_t S t = R + B t T P B t are smooth near zero because S ≻ 0 S \succ0 S ≻ 0 , so ( K − K t ) T S t ( K − K t ) = O ( t 2 ) (K - K_t)^{\mathsf{T}}S_t(K - K_t) = O(t^2) ( K − K t ) T S t ( K − K t ) = O ( t 2 ) because K t − K = O ( t ) K_t - K = O(t) K t − K = O ( t ) and S t S_t S t is bounded. Differentiating the remaining quadratic gives the stated formula.
Write Δ A = A ^ − A ⋆ \Delta A = \widehat{A}-A_{\star} Δ A = A − A ⋆ , Δ B = B ^ − B ⋆ \Delta B = \widehat{B}-B_{\star} Δ B = B − B ⋆ , E = Δ A + Δ B K ⋆ E = \Delta A+\Delta B K_{\star} E = Δ A + Δ B K ⋆ , M = Δ B T P ⋆ L ⋆ M = \Delta B^{\mathsf{T}}P_{\star}L_{\star} M = Δ B T P ⋆ L ⋆ , S 0 = R + B ^ T P ⋆ B ^ S_{0} = R+\widehat{B}^{\mathsf{T}}P_{\star}\widehat{B} S 0 = R + B T P ⋆ B , and G 0 = M + B ^ T P ⋆ E G_{0} = M+\widehat{B}^{\mathsf{T}}P_{\star}E G 0 = M + B T P ⋆ E . Put ℓ ⋆ = λ min ( P ⋆ ) \ell_{\star} = \lambda_{\min}(P_{\star}) ℓ ⋆ = λ m i n ( P ⋆ ) and s ⋆ = λ min ( S ⋆ ) s_{\star} = \lambda_{\min}(S_{\star}) s ⋆ = λ m i n ( S ⋆ ) . The reverse triangle inequality applied to the norm of [ R 1 / 2 v ; P ⋆ 1 / 2 B ^ v ] [R^{1/2}v; P_{\star}^{1/2}\widehat{B}v] [ R 1/2 v ; P ⋆ 1/2 B v ] gives
S 0 ⪰ ( s ⋆ − ∥ P ⋆ ∥ ∥ Δ B ∥ ) 2 I ≻ 0 if ∥ P ⋆ ∥ ∥ Δ B ∥ < s ⋆ . (23) S_{0} \succeq\left(\sqrt{s_{\star}}-\sqrt{\lVert P_{\star}\rVert}\lVert\Delta B\rVert\right)^{2}I \succ0 \qquad\text{if } \sqrt{\lVert P_{\star}\rVert}\lVert\Delta B\rVert< \sqrt{s_{\star}}. \tag*{(23)} S 0 ⪰ ( s ⋆ − ∥ P ⋆ ∥ ∥ Δ B ∥ ) 2 I ≻ 0 if ∥ P ⋆ ∥ ∥ Δ B ∥ < s ⋆ . (23)
Reference stationarity yields
R K ⋆ + B ^ T P ⋆ ( L ⋆ + E ) = Δ B T P ⋆ L ⋆ + B ^ T P ⋆ E = G 0 , RK_{\star}+\widehat{B}^{\mathsf{T}}P_{\star}(L_{\star}+E)=\Delta B^{\mathsf{T}}P_{\star}L_{\star}+\widehat{B}^{\mathsf{T}}P_{\star}E=G_{0}, R K ⋆ + B T P ⋆ ( L ⋆ + E ) = Δ B T P ⋆ L ⋆ + B T P ⋆ E = G 0 ,
hence
K A ^ , B ^ ( P ⋆ ) − K ⋆ = − S 0 − 1 G 0 . (24) K_{\widehat{A},\widehat{B}}(P_{\star})-K_{\star}=-S_{0}^{-1}G_{0}. \tag*{(24)} K A , B ( P ⋆ ) − K ⋆ = − S 0 − 1 G 0 . (24)
Substituting in (21) and subtracting the reference Bellman identity P ⋆ = Q + K ⋆ T R K ⋆ + L ⋆ T P ⋆ L ⋆ P_{\star}=Q+K_{\star}^{\mathsf{T}}RK_{\star}+L_{\star}^{\mathsf{T}}P_{\star}L_{\star} P ⋆ = Q + K ⋆ T R K ⋆ + L ⋆ T P ⋆ L ⋆ gives
F A ^ , B ^ ( P ⋆ ) − P ⋆ = L ⋆ T P ⋆ E + E T P ⋆ L ⋆ + E T P ⋆ E − G 0 T S 0 − 1 G 0 , (25) \mathcal{F}_{\widehat{A},\widehat{B}}(P_{\star})-P_{\star}=L_{\star}^{\mathsf{T}}P_{\star}E+E^{\mathsf{T}}P_{\star}L_{\star}+E^{\mathsf{T}}P_{\star}E-G_{0}^{\mathsf{T}}S_{0}^{-1}G_{0}, \tag*{(25)} F A , B ( P ⋆ ) − P ⋆ = L ⋆ T P ⋆ E + E T P ⋆ L ⋆ + E T P ⋆ E − G 0 T S 0 − 1 G 0 , (25)
L 0 − L ⋆ = ( I − B ^ S 0 − 1 B ^ T P ⋆ ) E − B ^ S 0 − 1 M , (26) L_{0}-L_{\star}=(I-\widehat{B}S_{0}^{-1}\widehat{B}^{\mathsf{T}}P_{\star})E-\widehat{B}S_{0}^{-1}M, \tag*{(26)} L 0 − L ⋆ = ( I − B S 0 − 1 B T P ⋆ ) E − B S 0 − 1 M , (26)
where L 0 = L A ^ , B ^ ( P ⋆ ) L_{0}=L_{\widehat{A},\widehat{B}}(P_{\star}) L 0 = L A , B ( P ⋆ ) and we used L 0 = L ⋆ + E + B ^ ( K A ^ , B ^ ( P ⋆ ) − K ⋆ ) L_{0}=L_{\star}+E+\widehat{B}(K_{\widehat{A},\widehat{B}}(P_{\star})-K_{\star}) L 0 = L ⋆ + E + B ( K A , B ( P ⋆ ) − K ⋆ ) . For any s 0 > 0 s_{0}>0 s 0 > 0 with S 0 ⪰ s 0 I S_{0}\succeq s_{0}I S 0 ⪰ s 0 I , (19) implies
∥ S 0 − 1 / 2 G 0 ∥ F ≤ ∥ P ⋆ ∥ ∥ E ∥ F + ∥ M ∥ F s 0 , ∥ M ∥ F ≤ ∥ P ⋆ L ⋆ ∥ ∥ Δ B ∥ F . (27) \lVert S_{0}^{-1/2}G_{0}\rVert_{F}\leq\sqrt{\lVert P_{\star}\rVert}\lVert E\rVert_{F}+\frac{\lVert M\rVert_{F}}{\sqrt{s_{0}}},\qquad\lVert M\rVert_{F}\leq\lVert P_{\star}L_{\star}\rVert\lVert\Delta B\rVert_{F}. \tag*{(27)} ∥ S 0 − 1/2 G 0 ∥ F ≤ ∥ P ⋆ ∥ ∥ E ∥ F + s 0 ∥ M ∥ F , ∥ M ∥ F ≤ ∥ P ⋆ L ⋆ ∥ ∥ Δ B ∥ F . (27)
Consequently, the residual identities give
∥ F A ^ , B ^ ( P ⋆ ) − P ⋆ ∥ F ≤ 2 ∥ P ⋆ L ⋆ ∥ ∥ E ∥ F + ∥ P ⋆ ∥ ∥ E ∥ F 2 + ∥ S 0 − 1 / 2 G 0 ∥ F 2 , (28) \lVert\mathcal{F}_{\widehat{A},\widehat{B}}(P_{\star})-P_{\star}\rVert_{F}\leq2\lVert P_{\star}L_{\star}\rVert\lVert E\rVert_{F}+\lVert P_{\star}\rVert\lVert E\rVert_{F}^{2}+\lVert S_{0}^{-1/2}G_{0}\rVert_{F}^{2}, \tag*{(28)} ∥ F A , B ( P ⋆ ) − P ⋆ ∥ F ≤ 2 ∥ P ⋆ L ⋆ ∥ ∥ E ∥ F + ∥ P ⋆ ∥ ∥ E ∥ F 2 + ∥ S 0 − 1/2 G 0 ∥ F 2 , (28)
∥ L 0 − L ⋆ ∥ F ≤ ∥ P ⋆ ∥ ℓ ⋆ ∥ E ∥ F + ∥ M ∥ F ℓ ⋆ s 0 . (29) \lVert L_{0}-L_{\star}\rVert_{F}\leq\sqrt{\frac{\lVert P_{\star}\rVert}{\ell_{\star}}}\lVert E\rVert_{F}+\frac{\lVert M\rVert_{F}}{\sqrt{\ell_{\star}s_{0}}}. \tag*{(29)} ∥ L 0 − L ⋆ ∥ F ≤ ℓ ⋆ ∥ P ⋆ ∥ ∥ E ∥ F + ℓ ⋆ s 0 ∥ M ∥ F . (29)
The following perturbation argument follows the Lyapunov-inverse fixed-point method in Mania et al. [18 ] . Here the residual and derivative estimates use R + B T P B ≻ 0 R+B^{\mathsf{T}}PB\succ0 R + B T P B ≻ 0 , allowing R R R to be singular.
Lemma 9 Let γ ⋆ \gamma_{\star} γ ⋆ , τ ⋆ \tau_{\star} τ ⋆ , L T L_{T} L T be as in Lemma 8, and let L P L_{P} L P and the radius r > 0 r>0 r > 0 be given by (30) –(31) below; they depend only on ∥ P ⋆ ∥ \lVert P_{\star}\rVert ∥ P ⋆ ∥ , ℓ ⋆ \ell_{\star} ℓ ⋆ , s ⋆ s_{\star} s ⋆ , ∥ K ⋆ ∥ \lVert K_{\star}\rVert ∥ K ⋆ ∥ , ∥ L ⋆ ∥ \lVert L_{\star}\rVert ∥ L ⋆ ∥ , ∥ P ⋆ L ⋆ ∥ \lVert P_{\star}L_{\star}\rVert ∥ P ⋆ L ⋆ ∥ , and L T L_{T} L T . If ε = ∥ [ A ^ − A ⋆ B ^ − B ⋆ ] ∥ F ≤ r \varepsilon=\lVert[\widehat{A}-A_{\star}\ \widehat{B}-B_{\star}]\rVert_{F}\leq r ε = ∥[ A − A ⋆ B − B ⋆ ] ∥ F ≤ r , then ( A ^ , B ^ ) (\widehat{A},\widehat{B}) ( A , B ) has a unique stabilizing Riccati solution P ^ ≻ 0 \widehat{P}\succ0 P ≻ 0 , with S ^ = R + B ^ T P ^ B ^ ≻ 0 \widehat{S}=R+\widehat{B}^{\mathsf{T}}\widehat{P}\widehat{B}\succ0 S = R + B T P B ≻ 0 , and
∥ P ^ − P ⋆ ∥ F ≤ L P ε ; \lVert\widehat{P}-P_{\star}\rVert_{F}\leq L_{P}\varepsilon; ∥ P − P ⋆ ∥ F ≤ L P ε ; moreover, (37) below holds, with η r \eta_{r} η r , s r s_{r} s r , ξ r \xi_{r} ξ r defined in (32) . These conclusions remain valid when r r r is replaced by any smaller radius in all the quantities below.
Proof. Put c E = 1 + ∥ K ⋆ ∥ 2 c_{E}=\sqrt{1+\lVert K_{\star}\rVert^{2}} c E = 1 + ∥ K ⋆ ∥ 2 , and define the following bounds, used to choose the radius:
L P = 2 L T ( 1 + 2 ∥ P ⋆ L ⋆ ∥ c E ) , L_{P}=2L_{T}(1+2\lVert P_{\star}L_{\star}\rVert c_{E}), L P = 2 L T ( 1 + 2 ∥ P ⋆ L ⋆ ∥ c E ) ,
N ‾ = ∥ P ⋆ ∥ c E 2 + ( ∥ P ⋆ ∥ c E + 2 ∥ P ⋆ L ⋆ ∥ s ⋆ ) 2 , \overline{N}=\lVert P_{\star}\rVert c_{E}^{2}+\left(\sqrt{\lVert P_{\star}\rVert}c_{E}+\frac{2\lVert P_{\star}L_{\star}\rVert}{\sqrt{s_{\star}}}\right)^{2}, N = ∥ P ⋆ ∥ c E 2 + ( ∥ P ⋆ ∥ c E + s ⋆ 2 ∥ P ⋆ L ⋆ ∥ ) 2 ,
ξ ‾ = 2 ( ∥ P ⋆ ∥ ℓ ⋆ c E + 2 ∥ P ⋆ L ⋆ ∥ ℓ ⋆ s ⋆ + ∥ L ⋆ ∥ L P ℓ ⋆ ) . (30) \overline{\xi}=2\left(\sqrt{\frac{\lVert P_{\star}\rVert}{\ell_{\star}}}c_{E}+\frac{2\lVert P_{\star}L_{\star}\rVert}{\sqrt{\ell_{\star}s_{\star}}}+\frac{\lVert L_{\star}\rVert L_{P}}{\ell_{\star}}\right). \tag*{(30)} ξ = 2 ℓ ⋆ ∥ P ⋆ ∥ c E + ℓ ⋆ s ⋆ 2 ∥ P ⋆ L ⋆ ∥ + ℓ ⋆ ∥ L ⋆ ∥ L P . (30)
Set
r = min { ℓ ⋆ 2 L P , s ⋆ 2 ∥ P ⋆ ∥ , 1 N ‾ , 1 2 L T ξ ‾ ( ∥ L ⋆ ∥ 2 + ( 2 L T ) − 1 + ∥ L ⋆ ∥ ) } (31) r=\min\left\{\frac{\ell_\star}{2L_P},\frac{\sqrt{s_\star}}{2\sqrt{\lVert P_\star\rVert}},\frac{1}{\overline{N}},\frac{1}{2L_T\overline{\xi}\left(\sqrt{\lVert L_\star\rVert^2+(2L_T)^{-1}}+\lVert L_\star\rVert\right)}\right\} \tag*{(31)} r = min ⎩ ⎨ ⎧ 2 L P ℓ ⋆ , 2 ∥ P ⋆ ∥ s ⋆ , N 1 , 2 L T ξ ( ∥ L ⋆ ∥ 2 + ( 2 L T ) − 1 + ∥ L ⋆ ∥ ) 1 ⎭ ⎬ ⎫ (31)
We also define
η r = L P r ℓ ⋆ , s r = ( s ⋆ − ∥ P ⋆ ∥ r ) 2 , \eta_r=\frac{L_Pr}{\ell_\star},\qquad s_r=\left(\sqrt{s_\star}-\sqrt{\lVert P_\star\rVert}r\right)^2, η r = ℓ ⋆ L P r , s r = ( s ⋆ − ∥ P ⋆ ∥ r ) 2 ,
ξ r = 1 1 − η r ( ∥ P ⋆ ∥ ℓ ⋆ c E + ∥ P ⋆ L ⋆ ∥ ℓ ⋆ s r + ∥ L ⋆ ∥ L P ℓ ⋆ ) , \xi_r=\frac{1}{1-\eta_r}\left(\sqrt{\frac{\lVert P_\star\rVert}{\ell_\star}}c_E+\frac{\lVert P_\star L_\star\rVert}{\sqrt{\ell_\star s_r}}+\frac{\lVert L_\star\rVert L_P}{\ell_\star}\right), ξ r = 1 − η r 1 ℓ ⋆ ∥ P ⋆ ∥ c E + ℓ ⋆ s r ∥ P ⋆ L ⋆ ∥ + ℓ ⋆ ∥ L ⋆ ∥ L P ,
χ r = L T ( 2 ∥ L ⋆ ∥ ξ r r + ξ r 2 r 2 ) . (32) \chi_r=L_T\left(2\lVert L_\star\rVert\xi_r r+\xi_r^2r^2\right). \tag*{(32)} χ r = L T ( 2 ∥ L ⋆ ∥ ξ r r + ξ r 2 r 2 ) . (32)
For a perturbed model with ε ≤ r \varepsilon\le r ε ≤ r , one has ∥ Δ B ∥ F ≤ ε \lVert\Delta B\rVert_F\le\varepsilon ∥ Δ B ∥ F ≤ ε and ∥ E ∥ F ≤ c E ε \lVert E\rVert_F\le c_E\varepsilon ∥ E ∥ F ≤ c E ε . The radius restrictions immediately give η r ≤ 1 / 2 \eta_r\le1/2 η r ≤ 1/2 , s r ≥ s ⋆ / 4 s_r\ge s_\star/4 s r ≥ s ⋆ /4 , and ξ r ≤ ξ ‾ \xi_r\le\overline{\xi} ξ r ≤ ξ . The last restriction is equivalent to ξ ‾ r ≤ ∥ L ⋆ ∥ 2 + ( 2 L T ) − 1 − ∥ L ⋆ ∥ \overline{\xi}_r\le\sqrt{\lVert L_\star\rVert^2+(2L_T)^{-1}}-\lVert L_\star\rVert ξ r ≤ ∥ L ⋆ ∥ 2 + ( 2 L T ) − 1 − ∥ L ⋆ ∥ , which implies χ r ≤ 1 / 2 \chi_r\le1/2 χ r ≤ 1/2 . Since N ‾ r ≤ 1 \overline{N}r\le1 N r ≤ 1 and L P / 2 = L T ( 1 + 2 ∥ P ⋆ L ⋆ ∥ c E ) L_P/2=L_T(1+2\lVert P_\star L_\star\rVert c_E) L P /2 = L T ( 1 + 2 ∥ P ⋆ L ⋆ ∥ c E ) , we obtain the certificate
η r , χ r ≤ 1 2 , ∥ P r ∥ ≤ 1 2 s ⋆ , L T ( 2 ∥ P ⋆ L ⋆ ∥ c E + N ‾ r ) ≤ ( 1 − χ r ) L P . (33) \eta_r,\chi_r\le\frac{1}{2},\qquad\sqrt{\lVert P_r\rVert}\le\frac{1}{2}\sqrt{s_\star},\qquad L_T(2\lVert P_\star L_\star\rVert c_E+\overline{N}r)\le(1-\chi_r)L_P. \tag*{(33)} η r , χ r ≤ 2 1 , ∥ P r ∥ ≤ 2 1 s ⋆ , L T ( 2 ∥ P ⋆ L ⋆ ∥ c E + N r ) ≤ ( 1 − χ r ) L P . (33)
All denominators in (31) are positive, so r > 0 r>0 r > 0 . The case ε = 0 \varepsilon=0 ε = 0 is immediate; henceforth suppose 0 < ε ≤ r 0<\varepsilon\le r 0 < ε ≤ r .
Consider the closed ball of symmetric matrices B ε = { X : ∥ X ∥ F ≤ L P ε } \mathcal{B}_\varepsilon=\{X:\lVert X\rVert_F\le L_P\varepsilon\} B ε = { X : ∥ X ∥ F ≤ L P ε } , and write P X = P ⋆ + X P_X=P_\star+X P X = P ⋆ + X , L X = L A ^ , B ^ ( P X ) L_X=L_{\widehat{A},\widehat{B}}(P_X) L X = L A , B ( P X ) , and S X = R + B ^ T P X B ^ S_X=R+\widehat{B}^{\mathsf T}P_X\widehat{B} S X = R + B T P X B . By (23) and (20) , throughout this ball
S 0 ⪰ s r I , P X ⪰ ( 1 − η r ) P ⋆ ≻ 0 , S X ⪰ ( 1 − η r ) S 0 ≻ 0. S_0\succeq s_rI,\qquad P_X\succeq(1-\eta_r)P_\star\succ0,\qquad S_X\succeq(1-\eta_r)S_0\succ0. S 0 ⪰ s r I , P X ⪰ ( 1 − η r ) P ⋆ ≻ 0 , S X ⪰ ( 1 − η r ) S 0 ≻ 0.
Thus the Riccati map is defined on the entire ball. Put W 0 = B ^ S 0 − 1 B ^ T W_0=\widehat{B}S_0^{-1}\widehat{B}^{\mathsf T} W 0 = B S 0 − 1 B T . Since ∥ W 0 X ∥ ≤ η r < 1 \lVert W_0X\rVert\le\eta_r<1 ∥ W 0 X ∥ ≤ η r < 1 , (20) gives
L X − L ⋆ = ( I + W 0 X ) − 1 ( L 0 − L ⋆ − W 0 X L ⋆ ) . L_X-L_\star=(I+W_0X)^{-1}(L_0-L_\star-W_0XL_\star). L X − L ⋆ = ( I + W 0 X ) − 1 ( L 0 − L ⋆ − W 0 X L ⋆ ) .
The Neumann-series bound and (29) therefore imply
∥ L X − L ⋆ ∥ F ≤ ∥ L 0 − L ⋆ ∥ F + ℓ ⋆ − 1 ∥ X ∥ F ∥ L ⋆ ∥ 1 − η r ≤ ξ r ε . (34) \lVert L_X-L_\star\rVert_F\le\frac{\lVert L_0-L_\star\rVert_F+\ell_\star^{-1}\lVert X\rVert_F\lVert L_\star\rVert}{1-\eta_r}\le\xi_r\varepsilon. \tag*{(34)} ∥ L X − L ⋆ ∥ F ≤ 1 − η r ∥ L 0 − L ⋆ ∥ F + ℓ ⋆ − 1 ∥ X ∥ F ∥ L ⋆ ∥ ≤ ξ r ε . (34)
With T ( X ) = X − L ⋆ T X L ⋆ \mathcal{T}(X)=X-L_\star^{\mathsf T}XL_\star T ( X ) = X − L ⋆ T X L ⋆ , define
R ( X ) = F A ^ , B ^ ( P ⋆ + X ) − P ⋆ − L ⋆ T X L ⋆ , \mathcal{R}(X)=\mathcal{F}_{\widehat{A},\widehat{B}}(P_\star+X)-P_\star-L_\star^{\mathsf T}XL_\star, R ( X ) = F A , B ( P ⋆ + X ) − P ⋆ − L ⋆ T X L ⋆ ,
Φ ( X ) = T − 1 ( R ( X ) ) . (35) \Phi(X)=\mathcal{T}^{-1}(\mathcal{R}(X)). \tag*{(35)} Φ ( X ) = T − 1 ( R ( X )) . (35)
A fixed point of Φ \Phi Φ is precisely a DARE solution P ⋆ + X P_\star+X P ⋆ + X . By (22) , D R ( X ) [ Z ] = L X T Z L X − L ⋆ T Z L ⋆ D\mathcal{R}(X)[Z]=L_X^{\mathsf T}ZL_X-L_\star^{\mathsf T}ZL_\star D R ( X ) [ Z ] = L X T Z L X − L ⋆ T Z L ⋆ . Expanding around L ⋆ L_\star L ⋆ and using (34) bounds its norm by ( 2 ∥ L ⋆ ∥ ξ r ε + ξ r 2 ε 2 ) ∥ Z ∥ F (2\lVert L_\star\rVert\xi_r\varepsilon+\xi_r^2\varepsilon^2)\lVert Z\rVert_F ( 2 ∥ L ⋆ ∥ ξ r ε + ξ r 2 ε 2 ) ∥ Z ∥ F . Integrating along segments in B ε \mathcal{B}_\varepsilon B ε and using (16) gives
∥ Φ ( X ) − Φ ( Y ) ∥ F ≤ L T ( 2 ∥ L ⋆ ∥ ξ r ε + ξ r 2 ε 2 ) ∥ X − Y ∥ F ≤ χ r ∥ X − Y ∥ F . (36) \begin{aligned}
\lVert\Phi(X)-\Phi(Y)\rVert_F\le L_T(2\lVert L_\star\rVert\xi_r\varepsilon+\xi_r^2\varepsilon^2)\lVert X-Y\rVert_F \\
&\le\chi_r\lVert X-Y\rVert_F. \tag*{(36)}
\end{aligned} ∥ Φ ( X ) − Φ ( Y ) ∥ F ≤ L T ( 2 ∥ L ⋆ ∥ ξ r ε + ξ r 2 ε 2 ) ∥ X − Y ∥ F ≤ χ r ∥ X − Y ∥ F . (36)
Since s r ≥ s ⋆ / 4 s_r \ge s_\star/4 s r ≥ s ⋆ /4 , (27)–(28) bound the quadratic residual coefficient by N ‾ \overline{N} N . Together with the certificate, this gives
∥ Φ ( X ) ∥ F ≤ ∥ Φ ( 0 ) ∥ F + χ r ∥ X ∥ F ≤ L T ( 2 ∥ P ⋆ L ⋆ ∥ c E + N ‾ ε ) ε + χ r L P ε ≤ L P ε . \begin{aligned}
\|\Phi(X)\|_F &\le\|\Phi(0)\|_F+\chi_r\|X\|_F\\
&\le L_T(2\|P_\star L_\star\|_{cE}+\overline{N}\varepsilon)\varepsilon+\chi_rL_P\varepsilon\\
&\le L_P\varepsilon.
\end{aligned} ∥Φ ( X ) ∥ F ≤ ∥Φ ( 0 ) ∥ F + χ r ∥ X ∥ F ≤ L T ( 2∥ P ⋆ L ⋆ ∥ c E + N ε ) ε + χ r L P ε ≤ L P ε .
Hence Φ \Phi Φ maps B ε B_\varepsilon B ε into itself and is a contraction. Banach’s theorem supplies a fixed point X X X . The matrix P ^ = P ⋆ + X ≻ 0 \widehat{P}=P_\star+X\succ0 P = P ⋆ + X ≻ 0 solves the DARE with S ^ ≻ 0 \widehat{S}\succ0 S ≻ 0 , which also implies ker R ∩ ker B ^ = { 0 } \ker R\cap\ker\widehat{B}=\{0\} ker R ∩ ker B = { 0 } . The converse in Proposition 7 therefore proves stability and uniqueness without assuming stabilizability of the perturbed model. The ball and closed-loop bounds give ∥ P ^ − P ⋆ ∥ F ≤ L P ε \|\widehat{P}-P_\star\|_F\le L_P\varepsilon ∥ P − P ⋆ ∥ F ≤ L P ε and
P ^ ⪰ ( 1 − η r ) P ⋆ , S ^ ⪰ ( 1 − η r ) s r I , ∥ L ^ − L ⋆ ∥ F ≤ ξ r ε . (37) \widehat{P}\succeq(1-\eta_r)P_\star,\qquad
\widehat{S}\succeq(1-\eta_r)s_rI,\qquad
\|\widehat{L}-L_\star\|_F\le\xi_r\varepsilon. \tag*{(37)} P ⪰ ( 1 − η r ) P ⋆ , S ⪰ ( 1 − η r ) s r I , ∥ L − L ⋆ ∥ F ≤ ξ r ε . (37)
Finally, every restriction in (31) is an upper bound on the radius, so the argument applies verbatim with r r r replaced by any smaller radius.
The following corollary shows that the Riccati solution and the gain are smooth on an explicit neighborhood of the true model, and that the gain is uniformly Lipschitz in that neighborhood.
Corollary 10 Let r r r be the radius of Lemma 9 and consider the convex set of models
N r = { ( A , B ) : ∥ [ A − A ⋆ B − B ⋆ ] ∥ F ≤ r } . \mathcal{N}_r=\{(A,B):\|[A-A_\star\ \ B-B_\star]\|_F\le r\}. N r = {( A , B ) : ∥ [ A − A ⋆ B − B ⋆ ] ∥ F ≤ r } . The stabilizing Riccati solution and the CE gain are real-analytic functions of ( A , B ) (A,B) ( A , B ) , in particular twice continuously differentiable, in a neighborhood of every model in N r \mathcal{N}_r N r . For any two models ( A 1 , B 1 ) , ( A 2 , B 2 ) ∈ N r (A_1,B_1),(A_2,B_2)\in\mathcal{N}_r ( A 1 , B 1 ) , ( A 2 , B 2 ) ∈ N r with CE gains K 1 , K 2 K_1,K_2 K 1 , K 2 ,
∥ K 1 − K 2 ∥ F ≤ L K , 1 ∥ [ A 1 − A 2 B 1 − B 2 ] ∥ F , (38) \|K_1-K_2\|_F\le L_{K,1}\|[A_1-A_2\ \ B_1-B_2]\|_F, \tag*{(38)} ∥ K 1 − K 2 ∥ F ≤ L K , 1 ∥ [ A 1 − A 2 B 1 − B 2 ] ∥ F , (38) where L K , 1 L_{K,1} L K , 1 is given in (39) below.
Proof. Put k ˉ r = ∥ P ⋆ ∥ + L P r ( 1 − η r ) s r ( ∥ A ⋆ ∥ + r ) \bar{k}_r=\sqrt{\frac{\|P_\star\|+L_Pr}{(1-\eta_r)s_r}}(\|A_\star\|+r) k ˉ r = ( 1 − η r ) s r ∥ P ⋆ ∥ + L P r ( ∥ A ⋆ ∥ + r ) and define
L P , 1 = 2 L T 1 − χ r ( ∥ P ⋆ ∥ + L P r ) ( ∥ L ⋆ ∥ + ξ r r ) 1 + k ˉ r 2 , L_{P,1}=\frac{2L_T}{1-\chi_r}(\|P_\star\|+L_Pr)(\|L_\star\|+\xi_rr)\sqrt{1+\bar{k}_r^2}, L P , 1 = 1 − χ r 2 L T ( ∥ P ⋆ ∥ + L P r ) ( ∥ L ⋆ ∥ + ξ r r ) 1 + k ˉ r 2 ,
L K , 1 = ( ∥ P ⋆ ∥ + L P r ) ( ∥ L ⋆ ∥ + ξ r r ) ( 1 − η r ) s r + ∥ P ⋆ ∥ + L P r ( 1 − η r ) s r 1 + k ˉ r 2 + ( ∥ L ⋆ ∥ + ξ r r ) L P , 1 ( 1 − η r ) ℓ ⋆ s r . (39) L_{K,1}=\frac{(\|P_\star\|+L_Pr)(\|L_\star\|+\xi_rr)}{(1-\eta_r)s_r}
+\sqrt{\frac{\|P_\star\|+L_Pr}{(1-\eta_r)s_r}}\sqrt{1+\bar{k}_r^2}
+\frac{(\|L_\star\|+\xi_rr)L_{P,1}}{(1-\eta_r)\sqrt{\ell_\star s_r}}. \tag*{(39)} L K , 1 = ( 1 − η r ) s r ( ∥ P ⋆ ∥ + L P r ) ( ∥ L ⋆ ∥ + ξ r r ) + ( 1 − η r ) s r ∥ P ⋆ ∥ + L P r 1 + k ˉ r 2 + ( 1 − η r ) ℓ ⋆ s r ( ∥ L ⋆ ∥ + ξ r r ) L P , 1 . (39)
Fix ( A , B ) ∈ N r (A,B)\in\mathcal{N}_r ( A , B ) ∈ N r and write P , K , L , S P,K,L,S P , K , L , S for its Riccati quantities. Put T L ( Z ) = Z − L ⊤ Z L \mathcal{T}_L(Z)=Z-L^\top ZL T L ( Z ) = Z − L ⊤ Z L . Then
( T − T L ) ( Z ) = L ⊤ Z L − L ⋆ ⊤ Z L ⋆ (\mathcal{T}-\mathcal{T}_L)(Z)=L^\top ZL-L_\star^\top ZL_\star ( T − T L ) ( Z ) = L ⊤ Z L − L ⋆ ⊤ Z L ⋆ , and, as in the proof of (36) with ε = r \varepsilon=r ε = r ,
∥ T − 1 ( T − T L ) ∥ F → F ≤ L T ( 2 ∥ L ⋆ ∥ ξ r r + ξ r 2 r 2 ) = χ r < 1. \|\mathcal{T}^{-1}(\mathcal{T}-\mathcal{T}_L)\|_{F\to F}
\le L_T(2\|L_\star\|\xi_rr+\xi_r^2r^2)=\chi_r<1. ∥ T − 1 ( T − T L ) ∥ F → F ≤ L T ( 2∥ L ⋆ ∥ ξ r r + ξ r 2 r 2 ) = χ r < 1.
Factoring T L = T [ I − T − 1 ( T − T L ) ] \mathcal{T}_L=\mathcal{T}[I-\mathcal{T}^{-1}(\mathcal{T}-\mathcal{T}_L)] T L = T [ I − T − 1 ( T − T L )] and applying the Neumann series yields
∥ T L − 1 ∥ F → F ≤ L T 1 − χ r . (40) \|\mathcal{T}_L^{-1}\|_{F\to F}\le\frac{L_T}{1-\chi_r}. \tag*{(40)} ∥ T L − 1 ∥ F → F ≤ 1 − χ r L T . (40)
Since D P ( P − F A , B ( P ) ) = T L D_P(P-F_{A,B}(P))=\mathcal{T}_L D P ( P − F A , B ( P )) = T L , the analytic implicit-function theorem gives a real-analytic local solution, since the Riccati map is rational wherever S ≻ 0 S\succ0 S ≻ 0 . Positivity of P , S P,S P , S persists locally, and Proposition 7 identifies this solution uniquely.
Differentiating the DARE and R K + B T P ( A + B K ) = 0 RK + B^{\mathsf{T}}P(A + BK) = 0 R K + B T P ( A + B K ) = 0 in any direction Δ = ( Δ A , Δ B ) \Delta= (\Delta A, \Delta B) Δ = ( Δ A , Δ B ) gives, using the chain rule and (22)
T L ( D P [ Δ ] ) = ( Δ A + Δ B K ) T P L + L T P ( Δ A + Δ B K ) , (41) \mathcal{T}_{L}(DP[\Delta]) = (\Delta A + \Delta BK)^{\mathsf{T}}PL + L^{\mathsf{T}}P(\Delta A + \Delta BK), \tag*{(41)} T L ( D P [ Δ ]) = ( Δ A + Δ B K ) T P L + L T P ( Δ A + Δ B K ) , (41)
S D K [ Δ ] = − ( Δ B T P L + B T D P [ Δ ] L + B T P ( Δ A + Δ B K ) ) . (42) SDK[\Delta] = -(\Delta B^{\mathsf{T}}PL + B^{\mathsf{T}}DP[\Delta]L + B^{\mathsf{T}}P(\Delta A + \Delta BK)). \tag*{(42)} S D K [ Δ ] = − ( Δ B T P L + B T D P [ Δ ] L + B T P ( Δ A + Δ B K )) . (42)
These are Liu [17 ] up to the sign convention u = − K x u = -Kx u = − K x and require only S ≻ 0 S \succ0 S ≻ 0 so they remain valid here; see also Kao and Hennequin [12 ] .
By (19) , Lemma 9, and ∥ A ∥ ≤ ∥ A ⋆ ∥ + r \lVert A\rVert\le\lVert A_{\star}\rVert+ r ∥ A ∥ ≤ ∥ A ⋆ ∥ + r , we have ∥ K ∥ ≤ ∥ S − 1 / 2 ∥ ∥ S − 1 / 2 B T P ∥ ∥ A ∥ ≤ k ˉ r \lVert K\rVert\le\lVert S^{-1/2}\rVert\lVert S^{-1/2}B^{\mathsf{T}}P\rVert\lVert A\rVert\le\bar{k}_{r} ∥ K ∥ ≤ ∥ S − 1/2 ∥ ∥ S − 1/2 B T P ∥ ∥ A ∥ ≤ k ˉ r . Since ∥ Δ A + Δ B K ∥ F ≤ 1 + ∥ K ∥ 2 ∥ [ Δ A Δ B ] ∥ F \lVert\Delta A + \Delta BK\rVert_{F} \le\sqrt{1 + \lVert K\rVert^{2}}\lVert[\Delta A\ \Delta B]\rVert_{F} ∥ Δ A + Δ B K ∥ F ≤ 1 + ∥ K ∥ 2 ∥[ Δ A Δ B ] ∥ F , (40) gives
∥ D P [ Δ ] ∥ F ≤ 2 L T ∥ P ∥ ∥ L ∥ 1 − χ r ∥ Δ A + Δ B K ∥ F ≤ L P , 1 ∥ [ Δ A Δ B ] ∥ F . \lVert DP[\Delta]\rVert_{F} \le\frac{2L_{\mathcal{T}}\lVert P\rVert\lVert L\rVert}{1-\chi_{r}}\lVert\Delta A + \Delta BK\rVert_{F}
\le L_{P,1}\lVert[\Delta A\ \Delta B]\rVert_{F}. ∥ D P [ Δ ] ∥ F ≤ 1 − χ r 2 L T ∥ P ∥ ∥ L ∥ ∥ Δ A + Δ B K ∥ F ≤ L P , 1 ∥[ Δ A Δ B ] ∥ F .
The three terms of (42) and (19) give
∥ D K [ Δ ] ∥ F ≤ ∥ P ∥ ∥ L ∥ λ min ( S ) ∥ Δ B ∥ F + ∥ L ∥ ∥ D P [ Δ ] ∥ F λ min ( P ) λ min ( S ) + ∥ P ∥ λ min ( S ) ∥ Δ A + Δ B K ∥ F . \lVert DK[\Delta]\rVert_{F} \le\frac{\lVert P\rVert\lVert L\rVert}{\lambda_{\min}(S)}\lVert\Delta B\rVert_{F} + \frac{\lVert L\rVert\lVert DP[\Delta]\rVert_{F}}{\sqrt{\lambda_{\min}(P)}\lambda_{\min}(S)} + \sqrt{\frac{\lVert P\rVert}{\lambda_{\min}(S)}}\lVert\Delta A + \Delta BK\rVert_{F}. ∥ D K [ Δ ] ∥ F ≤ λ m i n ( S ) ∥ P ∥ ∥ L ∥ ∥ Δ B ∥ F + λ m i n ( P ) λ m i n ( S ) ∥ L ∥ ∥ D P [ Δ ] ∥ F + λ m i n ( S ) ∥ P ∥ ∥ Δ A + Δ B K ∥ F .
Substituting the bounds from Lemma 9 bounds the gain derivative by L K , 1 ∥ [ Δ A Δ B ] ∥ F L_{K,1}\lVert[\Delta A\ \Delta B]\rVert_{F} L K , 1 ∥[ Δ A Δ B ] ∥ F . Since N r \mathcal{N}_{r} N r is convex, integrating the gain derivative along a segment proves (38) .
Certainty Equivalence and Strong Stability
The argument follows Mania et al. [18 ] , using the semidefinite-cost sensitivity bound above. Following Cassel et al. [5 ] , we say that K K K is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly stable if ∥ K ∥ ≤ κ \lVert K\rVert\le\kappa ∥ K ∥ ≤ κ and A ⋆ + B ⋆ K = H L H − 1 A_{\star} + B_{\star}K = H L H^{-1} A ⋆ + B ⋆ K = H L H − 1 for some H , L H, L H , L with ∥ H ∥ ∥ H − 1 ∥ ≤ κ \lVert H\rVert\lVert H^{-1}\rVert\le\kappa ∥ H ∥ ∥ H − 1 ∥ ≤ κ and ∥ L ∥ ≤ 1 − γ \lVert L\rVert\le1-\gamma ∥ L ∥ ≤ 1 − γ .
Lemma 11. Let r r r be the radius of Lemma 9, let C K = L K , 1 C_{K} = L_{K,1} C K = L K , 1 be the constant of Corollary 10, and put
r C E = min { r , 1 − γ ⋆ 2 τ ⋆ ∥ B ⋆ ∥ C K } , C J = σ ⋆ 2 τ ⋆ 2 ∥ S ⋆ ∥ C K 2 1 − ( ( 1 + γ ⋆ ) / 2 ) 2 , r_{\mathrm{CE}} = \min\left\{r,\frac{1-\gamma_{\star}}{2\tau_{\star}\lVert B_{\star}\rVert C_{K}}\right\}, \qquad C_{J} = \frac{\sigma_{\star}^{2}\tau_{\star}^{2}\lVert S_{\star}\rVert C_{K}^{2}}{1-((1+\gamma_{\star})/2)^{2}}, r CE = min { r , 2 τ ⋆ ∥ B ⋆ ∥ C K 1 − γ ⋆ } , C J = 1 − (( 1 + γ ⋆ ) /2 ) 2 σ ⋆ 2 τ ⋆ 2 ∥ S ⋆ ∥ C K 2 , omitting the second radius restriction if ∥ B ⋆ ∥ C K = 0 \lVert B_{\star}\rVert C_{K}=0 ∥ B ⋆ ∥ C K = 0 . If a model ( A , B ) (A,B) ( A , B ) satisfies ε = ∥ [ A − A ⋆ B − B ⋆ ] ∥ F ≤ r C E \varepsilon= \lVert[A-A_{\star}\ B-B_{\star}]\rVert_{F} \le r_{\mathrm{CE}} ε = ∥[ A − A ⋆ B − B ⋆ ] ∥ F ≤ r CE , then its CE gain K K K exists, stabilizes the true plant, and satisfies
∥ K − K ⋆ ∥ F ≤ C K ε , J ( K ) − J ⋆ ≤ C J ε 2 . \lVert K-K_{\star}\rVert_{F} \le C_{K}\varepsilon,\qquad J(K)-J_{\star} \le C_{J}\varepsilon^{2}. ∥ K − K ⋆ ∥ F ≤ C K ε , J ( K ) − J ⋆ ≤ C J ε 2 . Moreover, for 0 < ε 0 ≤ r C E 0 < \varepsilon_{0} \le r_{\mathrm{CE}} 0 < ε 0 ≤ r CE , J ⋆ ≤ ν J_{\star} \le\nu J ⋆ ≤ ν , and k ˉ ⋆ ≥ ∥ K ⋆ ∥ \bar{k}_{\star} \ge\lVert K_{\star}\rVert k ˉ ⋆ ≥ ∥ K ⋆ ∥ , every such gain with ε ≤ ε 0 \varepsilon\le\varepsilon_{0} ε ≤ ε 0 is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly stable, where
κ = max { ν + C J ε 0 2 α 0 σ 2 , k ˉ ⋆ + C K ε 0 , 1 } , γ = 1 2 κ 2 . \kappa= \max\left\{\sqrt{\frac{\nu+C_{J}\varepsilon_{0}^{2}}{\alpha_{0}\sigma^{2}}},\bar{k}_{\star}+C_{K}\varepsilon_{0},1\right\},\qquad\gamma= \frac{1}{2\kappa^{2}}. κ = max ⎩ ⎨ ⎧ α 0 σ 2 ν + C J ε 0 2 , k ˉ ⋆ + C K ε 0 , 1 ⎭ ⎬ ⎫ , γ = 2 κ 2 1 .
Proof Lemma 9 supplies existence, and (38) with ( A ⋆ , B ⋆ ) ∈ N r (A_\star,B_\star)\in\mathcal{N}_r ( A ⋆ , B ⋆ ) ∈ N r gives the gain bound. The radius restriction and (17) give
∥ ( A ⋆ + B ⋆ K ) j ∥ ≤ τ ⋆ ( ( 1 + γ ⋆ ) / 2 ) j , ∥ Σ K ∥ ≤ σ 2 τ ⋆ 2 1 − ( ( 1 + γ ⋆ ) / 2 ) 2 . \lVert(A_\star+B_\star K)^j\rVert\leq\tau_\star\left((1+\gamma_\star)/2\right)^j,\qquad\lVert\Sigma_K\rVert\leq\frac{\sigma^2\tau_\star^2}{1-\left((1+\gamma_\star)/2\right)^2}. ∥( A ⋆ + B ⋆ K ) j ∥ ≤ τ ⋆ ( ( 1 + γ ⋆ ) /2 ) j , ∥ Σ K ∥ ≤ 1 − ( ( 1 + γ ⋆ ) /2 ) 2 σ 2 τ ⋆ 2 .
Thus the true closed loop is stable, and (14) yields J ( K ) − J ⋆ ≤ ∥ Σ K ∥ ∥ S ⋆ ∥ ∥ K − K ⋆ ∥ F 2 ≤ C J ε 2 J(K)-J_\star\leq\lVert\Sigma_K\rVert\lVert S_\star\rVert\lVert K-K_\star\rVert_F^2\leq C_J\varepsilon^2 J ( K ) − J ⋆ ≤ ∥ Σ K ∥ ∥ S ⋆ ∥ ∥ K − K ⋆ ∥ F 2 ≤ C J ε 2 .
For strong stability, use the Lyapunov argument of Cassel et al. [5 ] with H = P K − 1 / 2 H=P_K^{-1/2} H = P K − 1/2 , where P K P_K P K is given by (13) with G = K G=K G = K and ( A , B ) = ( A ⋆ , B ⋆ ) (A,B)=(A_\star,B_\star) ( A , B ) = ( A ⋆ , B ⋆ ) , and L = P K 1 / 2 ( A ⋆ + B ⋆ K ) P K − 1 / 2 L=P_K^{1/2}(A_\star+B_\star K)P_K^{-1/2} L = P K 1/2 ( A ⋆ + B ⋆ K ) P K − 1/2 . It gives
∥ H ∥ ∥ H − 1 ∥ ≤ J ( K ) α 0 σ 2 , ∥ L ∥ ≤ 1 − α 0 σ 2 2 J ( K ) . \lVert H\rVert\lVert H^{-1}\rVert\leq\sqrt{\frac{J(K)}{\alpha_0\sigma^2}},\qquad\lVert L\rVert\leq1-\frac{\alpha_0\sigma^2}{2J(K)}. ∥ H ∥ ∥ H − 1 ∥ ≤ α 0 σ 2 J ( K ) , ∥ L ∥ ≤ 1 − 2 J ( K ) α 0 σ 2 .
These estimates use only Q ⪰ α 0 I Q\succeq\alpha_0I Q ⪰ α 0 I and R ⪰ 0 R\succeq0 R ⪰ 0 . The cited lemmas then use R ≻ 0 R\succ0 R ≻ 0 to bound the gain itself; here ∥ K ∥ ≤ k ˉ ⋆ + C K ε 0 \lVert K\rVert\leq\bar{k}_\star+C_K\varepsilon_0 ∥ K ∥ ≤ k ˉ ⋆ + C K ε 0 supplies that bound.
Controller Identifiability
Recall D ⋆ D_\star D ⋆ from § 4.1.1 ; we also use M ⋆ h = Δ B h ⊤ P ⋆ L ⋆ M_{\star h}=\Delta B_h^\top P_\star L_\star M ⋆ h = Δ B h ⊤ P ⋆ L ⋆ and write P ( θ ) P(\theta) P ( θ ) for the stabilizing Riccati solution of Θ ( θ ) \Theta(\theta) Θ ( θ ) wherever it exists.
We use the equivalent tests below to verify controller identifiability. The gain-based CI criterion is Liu [17 ] ; the differential reduction below is the semidefinite-cost version of Liu [17 ] .
Lemma 12 Under Assumption 1 and (2) ,
ker I ⋆ = ker D ⋆ , ker H ⋆ = ker d K ( θ ⋆ ) , \ker\mathcal{I}_\star=\ker D_\star,\qquad\ker\mathcal{H}_\star=\ker dK(\theta_\star), ker I ⋆ = ker D ⋆ , ker H ⋆ = ker d K ( θ ⋆ ) , where d K ( θ ⋆ ) dK(\theta_\star) d K ( θ ⋆ ) is the differential of θ ↦ K ( θ ) \theta\mapsto K(\theta) θ ↦ K ( θ ) at θ ⋆ \theta_\star θ ⋆ . Consequently, CI is equivalent to ker D ⋆ ⊆ ker M ⋆ \ker D_\star\subseteq\ker M_\star ker D ⋆ ⊆ ker M ⋆ .
Proof Put Σ ⋆ = σ 2 ∑ j ≥ 0 L ⋆ j ( L ⋆ j ) ⊤ ≻ 0 \Sigma_\star=\sigma^2\sum_{j\geq0}L_\star^j(L_\star^j)^\top\succ0 Σ ⋆ = σ 2 ∑ j ≥ 0 L ⋆ j ( L ⋆ j ) ⊤ ≻ 0 . The conditional Gaussian score gives
h ⊤ I ⋆ h = σ − 2 ∥ D ⋆ h Σ ⋆ 1 / 2 ∥ F 2 . h^\top\mathcal{I}_\star h=\sigma^{-2}\lVert D_\star h\Sigma_\star^{1/2}\rVert_F^2. h ⊤ I ⋆ h = σ − 2 ∥ D ⋆ h Σ ⋆ 1/2 ∥ F 2 .
The smoothness of P ( θ ) P(\theta) P ( θ ) and K ( θ ) K(\theta) K ( θ ) near θ ⋆ \theta_\star θ ⋆ from Corollary 10 and true-plant stability from Lemma 11 allow differentiation of the stationary performance identity (14) . Since K ( θ ⋆ ) = K ⋆ K(\theta_\star)=K_\star K ( θ ⋆ ) = K ⋆ , it gives
h ⊤ H ⋆ h = 2 ∥ S ⋆ 1 / 2 d K ( θ ⋆ ) [ h ] Σ ⋆ 1 / 2 ∥ F 2 . h^\top\mathcal{H}_\star h=2\lVert S_\star^{1/2}dK(\theta_\star)[h]\Sigma_\star^{1/2}\rVert_F^2. h ⊤ H ⋆ h = 2 ∥ S ⋆ 1/2 d K ( θ ⋆ ) [ h ] Σ ⋆ 1/2 ∥ F 2 .
Here the stationary covariance depends smoothly on the stable closed-loop matrix through its invertible Lyapunov equation. Positivity of S ⋆ S_\star S ⋆ and Σ ⋆ \Sigma_\star Σ ⋆ proves the two kernel identities. Finally, for h ∈ ker D ⋆ h\in\ker D_\star h ∈ ker D ⋆ , (41) and invertibility of the Lyapunov operator give d P ( θ ⋆ ) [ h ] = 0 dP(\theta_\star)[h]=0 d P ( θ ⋆ ) [ h ] = 0 . Then (42) reduces to S ⋆ d K ( θ ⋆ ) [ h ] = − M ⋆ h S_\star dK(\theta_\star)[h]=-M_\star h S ⋆ d K ( θ ⋆ ) [ h ] = − M ⋆ h , and, since S ⋆ ≻ 0 S_\star\succ0 S ⋆ ≻ 0 , d K ( θ ⋆ ) [ h ] = 0 dK(\theta_\star)[h]=0 d K ( θ ⋆ ) [ h ] = 0 if and only if M ⋆ h = 0 M_\star h=0 M ⋆ h = 0 , which proves the last assertion.
Proof of Lemma 3. Under CI, every h ∈ ker D ⋆ h \in\ker D_\star h ∈ ker D ⋆ satisfies M ⋆ h = Δ B h ⊤ P ⋆ L ⋆ = 0 M_\star h = \Delta B_h^\top P_\star L_\star= 0 M ⋆ h = Δ B h ⊤ P ⋆ L ⋆ = 0 by Lemma 12 , so each column of Δ B h \Delta B_h Δ B h lies in ker ( L ⋆ ⊤ P ⋆ ) \ker(L_\star^\top P_\star) ker ( L ⋆ ⊤ P ⋆ ) , which has dimension n − rank L ⋆ n-\operatorname{rank}L_\star n − rank L ⋆ . Moreover, h ↦ Δ B h h \mapsto\Delta B_h h ↦ Δ B h is injective on ker D ⋆ \ker D_\star ker D ⋆ , since Δ B h = 0 \Delta B_h=0 Δ B h = 0 forces Δ A h = D ⋆ h = 0 \Delta A_h=D_\star h=0 Δ A h = D ⋆ h = 0 , hence h = 0 h=0 h = 0 by nonredundancy. Thus dim ker I ⋆ = dim ker D ⋆ ≤ m ( n − rank L ⋆ ) \dim\ker I_\star=\dim\ker D_\star\leq m(n-\operatorname{rank}L_\star) dim ker I ⋆ = dim ker D ⋆ ≤ m ( n − rank L ⋆ ) , as in the proof of Liu [17 ] . Then, put Z = I − B ⋆ S ⋆ − 1 B ⋆ ⊤ P ⋆ Z=I-B_\star S_\star^{-1}B_\star^\top P_\star Z = I − B ⋆ S ⋆ − 1 B ⋆ ⊤ P ⋆ , so that L ⋆ = Z A ⋆ L_\star=ZA_\star L ⋆ = Z A ⋆ . We claim ker Z = B ⋆ ker R \ker Z=B_\star\ker R ker Z = B ⋆ ker R . Indeed, Z B ⋆ v = B ⋆ S ⋆ − 1 R v = 0 ZB_\star v=B_\star S_\star^{-1}Rv=0 Z B ⋆ v = B ⋆ S ⋆ − 1 R v = 0 if R v = 0 Rv=0 R v = 0 . Conversely, if Z x = 0 Zx=0 Z x = 0 , let v = S ⋆ − 1 B ⋆ ⊤ P ⋆ x v=S_\star^{-1}B_\star^\top P_\star x v = S ⋆ − 1 B ⋆ ⊤ P ⋆ x . Then x = B ⋆ v x=B_\star v x = B ⋆ v and S ⋆ v = B ⋆ ⊤ P ⋆ B ⋆ v S_\star v=B_\star^\top P_\star B_\star v S ⋆ v = B ⋆ ⊤ P ⋆ B ⋆ v , hence R v = 0 Rv=0 R v = 0 . Moreover, B ⋆ B_\star B ⋆ is injective on ker R \ker R ker R , since ker R ∩ ker B ⋆ = { 0 } \ker R\cap\ker B_\star=\{0\} ker R ∩ ker B ⋆ = { 0 } . The rank inequality rank ( Z A ⋆ ) ≥ rank A ⋆ − dim ker Z \operatorname{rank}(ZA_\star)\geq\operatorname{rank}A_\star-\dim\ker Z rank ( Z A ⋆ ) ≥ rank A ⋆ − dim ker Z therefore proves the claimed bound.
The following lemma is a quantitative adaptation of Liu [17 ] , which we extend to semidefinite input costs. We follow the same invariance and orthogonal-decomposition argument, but use the explicit sensitivity bounds above and then pass from optimal-feedback prediction error to prediction error under the estimated feedback.
Lemma 13. Use the constants of Lemma 11 and Corollary 10. Assume
ker D ⋆ ⊆ ker M ⋆ . (43) \ker D_\star\subseteq\ker M_\star. \tag*{(43)} ker D ⋆ ⊆ ker M ⋆ . (43) If rank D ⋆ > 0 \operatorname{rank}D_\star>0 rank D ⋆ > 0 , let μ ⋆ = σ min + ( D ⋆ ) > 0 \mu_\star=\sigma_{\min}^{+}(D_\star)>0 μ ⋆ = σ m i n + ( D ⋆ ) > 0 , the smallest nonzero singular value, and put
ρ l o c = min { r C E , μ ⋆ 2 L K , 1 } , C p r e d = 2 L K , 1 μ ⋆ . \rho_{\mathrm{loc}}=\min\left\{r_{\mathrm{CE}},\frac{\mu_\star}{2L_{K,1}}\right\},\qquad C_{\mathrm{pred}}=\frac{2L_{K,1}}{\mu_\star}. ρ loc = min { r CE , 2 L K , 1 μ ⋆ } , C pred = μ ⋆ 2 L K , 1 . For θ ^ ∈ R p \hat{\theta}\in\mathbb{R}^{p} θ ^ ∈ R p with e = θ ^ − θ ⋆ e=\hat{\theta}-\theta_\star e = θ ^ − θ ⋆ and ∥ e ∥ 2 ≤ ρ l o c \|e\|_2\leq\rho_{\mathrm{loc}} ∥ e ∥ 2 ≤ ρ loc , write [ A ^ B ^ ] = Θ ( θ ^ ) [\hat A\ \hat B]=\Theta(\hat{\theta}) [ A ^ B ^ ] = Θ ( θ ^ ) , Δ A = A ^ − A ⋆ \Delta A=\hat A-A_\star Δ A = A ^ − A ⋆ , Δ B = B ^ − B ⋆ \Delta B=\hat B-B_\star Δ B = B ^ − B ⋆ , and K ^ = K ( θ ^ ) \hat K=K(\hat{\theta}) K ^ = K ( θ ^ ) . Then
∥ K ^ − K ⋆ ∥ F ≤ C p r e d ∥ Δ A + Δ B K ^ ∥ F . (44) \|\hat K-K_\star\|_F\leq C_{\mathrm{pred}}\|\Delta A+\Delta B\hat K\|_F . \tag*{(44)} ∥ K ^ − K ⋆ ∥ F ≤ C pred ∥Δ A + Δ B K ^ ∥ F . (44) For every h ∈ ker D ⋆ h\in\ker D_\star h ∈ ker D ⋆ with ∥ h ∥ 2 ≤ r \|h\|_2\leq r ∥ h ∥ 2 ≤ r , one has P ( θ ⋆ + h ) = P ⋆ P(\theta_\star+h)=P_\star P ( θ ⋆ + h ) = P ⋆ and K ( θ ⋆ + h ) = K ⋆ K(\theta_\star+h)=K_\star K ( θ ⋆ + h ) = K ⋆ . If D ⋆ = 0 D_\star=0 D ⋆ = 0 , then P ( θ ) = P ⋆ P(\theta)=P_\star P ( θ ) = P ⋆ and K ( θ ) = K ⋆ K(\theta)=K_\star K ( θ ) = K ⋆ whenever ∥ θ − θ ⋆ ∥ 2 ≤ r \|\theta-\theta_\star\|_2\leq r ∥ θ − θ ⋆ ∥ 2 ≤ r , and (44) holds with C p r e d = 0 C_{\mathrm{pred}}=0 C pred = 0 and ρ l o c = r C E \rho_{\mathrm{loc}}=r_{\mathrm{CE}} ρ loc = r CE , without division by a singular value.
Proof. For h ∈ ker D ⋆ h\in\ker D_\star h ∈ ker D ⋆ with ∥ h ∥ 2 ≤ r \|h\|_2\leq r ∥ h ∥ 2 ≤ r , the isometry [ Δ A h Δ B h ] = E h [\Delta A_h\ \Delta B_h]=\mathcal{E}h [ Δ A h Δ B h ] = E h puts the perturbed model in N r \mathcal{N}_r N r . At P ⋆ P_\star P ⋆ , its reference residuals satisfy E = D ⋆ h = 0 E=D_\star h=0 E = D ⋆ h = 0 and M = M ⋆ h = 0 M=M_\star h=0 M = M ⋆ h = 0 by (43) . Hence (24) –(25) give the same Riccati solution and gain, with S 0 ≻ 0 S_0\succ0 S 0 ≻ 0 by (23) . Proposition 7 identifies them uniquely. This also proves the assertion for D ⋆ = 0 D_\star=0 D ⋆ = 0 .
Otherwise, decompose e = h + v e=h+v e = h + v orthogonally with h ∈ ker D ⋆ h\in\ker D_\star h ∈ ker D ⋆ and v ∈ ( ker D ⋆ ) ⊥ v\in(\ker D_\star)^\perp v ∈ ( ker D ⋆ ) ⊥ . Since ∥ h ∥ 2 ≤ ∥ e ∥ 2 ≤ r \|h\|_2\leq\|e\|_2\leq r ∥ h ∥ 2 ≤ ∥ e ∥ 2 ≤ r , both θ ⋆ + h \theta_\star+h θ ⋆ + h and θ ^ \hat{\theta} θ ^ correspond to models in N r \mathcal{N}_r N r , so (38) and exact invariance at h h h (i.e., K ( θ ⋆ + h ) = K ⋆ K(\theta_\star+h)=K_\star K ( θ ⋆ + h ) = K ⋆ ) give
∥ K ^ − K ⋆ ∥ F ≤ L K , 1 ∥ v ∥ 2 ≤ L K , 1 μ ⋆ ∥ D ⋆ e ∥ F . \|\hat K-K_\star\|_F\leq L_{K,1}\|v\|_2\leq\frac{L_{K,1}}{\mu_\star}\|D_\star e\|_F . ∥ K ^ − K ⋆ ∥ F ≤ L K , 1 ∥ v ∥ 2 ≤ μ ⋆ L K , 1 ∥ D ⋆ e ∥ F .
because D ⋆ e = D ⋆ v D_\star e=D_\star v D ⋆ e = D ⋆ v and ∥ D ⋆ v ∥ F ≥ μ ⋆ ∥ v ∥ 2 \|D_\star v\|_F\geq\mu_\star\|v\|_2 ∥ D ⋆ v ∥ F ≥ μ ⋆ ∥ v ∥ 2 on ( ker D ⋆ ) ⊥ (\ker D_\star)^\perp ( ker D ⋆ ) ⊥ . Finally, D ⋆ e = Δ A + Δ B K ^ − Δ B ( K ^ − K ⋆ ) D_\star e=\Delta A+\Delta B\hat K-\Delta B(\hat K-K_\star) D ⋆ e = Δ A + Δ B K ^ − Δ B ( K ^ − K ⋆ ) implies
∥ K ^ − K ⋆ ∥ F ≤ L K , 1 μ ⋆ ( ∥ Δ A + Δ B K ^ ∥ F + ∥ Δ B ∥ ∥ K ^ − K ⋆ ∥ F ) . \|\hat K-K_\star\|_F\leq\frac{L_{K,1}}{\mu_\star}\left(\|\Delta A+\Delta B\hat K\|_F+\|\Delta B\|\|\hat K-K_\star\|_F\right). ∥ K ^ − K ⋆ ∥ F ≤ μ ⋆ L K , 1 ( ∥Δ A + Δ B K ^ ∥ F + ∥Δ B ∥∥ K ^ − K ⋆ ∥ F ) .
Since ∥ Δ B ∥ ≤ ∥ e ∥ 2 ≤ μ ⋆ / ( 2 L K , 1 ) \|\Delta B\|\leq\|e\|_2\leq\mu_\star/(2L_{K,1}) ∥Δ B ∥ ≤ ∥ e ∥ 2 ≤ μ ⋆ / ( 2 L K , 1 ) , the last gain term is absorbed with a factor at most 2 2 2 , proving (44) .
Proof of Corollary 6 Since A A A is unrestricted and independent of B B B , the direction space contains all [ Δ A 0 ] [\Delta A\ 0] [ Δ A 0 ] , on which D ⋆ h = Δ A h D_{\star}h=\Delta A_h D ⋆ h = Δ A h . Thus D ⋆ D ⋆ ∗ ⪰ I D_{\star}D_{\star}^{*}\succeq I D ⋆ D ⋆ ∗ ⪰ I , hence σ min + ( D ⋆ ) ≥ 1 \sigma_{\min}^{+}(D_{\star})\ge1 σ m i n + ( D ⋆ ) ≥ 1 , where D ⋆ ∗ D_{\star}^{*} D ⋆ ∗ is the adjoint for the Euclidean and Frobenius inner products.
For CI, every admissible Δ B h \Delta B_h Δ B h is paired with the invisible direction Δ A h = − Δ B h K ⋆ \Delta A_h=-\Delta B_hK_{\star} Δ A h = − Δ B h K ⋆ , so ker D ⋆ = { h : Δ A h = − Δ B h K ⋆ } \ker D_{\star}=\{h:\Delta A_h=-\Delta B_hK_{\star}\} ker D ⋆ = { h : Δ A h = − Δ B h K ⋆ } contains a direction for each admissible Δ B h \Delta B_h Δ B h . By Lemma 12, CI is therefore equivalent to M ⋆ h = Δ B h T P ⋆ L ⋆ = 0 M_{\star}h=\Delta B_h^{\mathsf T}P_{\star}L_{\star}=0 M ⋆ h = Δ B h T P ⋆ L ⋆ = 0 , i.e., range ( Δ B h ) ⊆ ker ( L ⋆ T P ⋆ ) \operatorname{range}(\Delta B_h)\subseteq\ker(L_{\star}^{\mathsf T}P_{\star}) range ( Δ B h ) ⊆ ker ( L ⋆ T P ⋆ ) , for every admissible Δ B h \Delta B_h Δ B h . For R = 0 R=0 R = 0 , stationarity gives B ⋆ T P ⋆ L ⋆ = 0 B_{\star}^{\mathsf T}P_{\star}L_{\star}=0 B ⋆ T P ⋆ L ⋆ = 0 , so range ( B ⋆ ) ⊆ ker ( L ⋆ T P ⋆ ) \operatorname{range}(B_{\star})\subseteq\ker(L_{\star}^{\mathsf T}P_{\star}) range ( B ⋆ ) ⊆ ker ( L ⋆ T P ⋆ ) ; under the range condition, range ( Δ B h ) ⊆ range ( B ⋆ ) \operatorname{range}(\Delta B_h)\subseteq\operatorname{range}(B_{\star}) range ( Δ B h ) ⊆ range ( B ⋆ ) , which proves sufficiency. For necessity, recall from the proof of Lemma 3 that L ⋆ = Z A ⋆ L_{\star}=ZA_{\star} L ⋆ = Z A ⋆ , where Z = I − B ⋆ S ⋆ − 1 B ⋆ T P ⋆ Z=I-B_{\star}S_{\star}^{-1}B_{\star}^{\mathsf T}P_{\star} Z = I − B ⋆ S ⋆ − 1 B ⋆ T P ⋆ satisfies ker Z = range ( B ⋆ ) \ker Z=\operatorname{range}(B_{\star}) ker Z = range ( B ⋆ ) when R = 0 R=0 R = 0 . Hence rank L ⋆ = rank A ⋆ − dim ( range A ⋆ ∩ range B ⋆ ) = rank [ A ⋆ B ⋆ ] − m \operatorname{rank}L_{\star}=\operatorname{rank}A_{\star}-\dim(\operatorname{range}A_{\star}\cap\operatorname{range}B_{\star})=\operatorname{rank}[A_{\star}\ B_{\star}]-m rank L ⋆ = rank A ⋆ − dim ( range A ⋆ ∩ range B ⋆ ) = rank [ A ⋆ B ⋆ ] − m . If rank [ A ⋆ B ⋆ ] = n \operatorname{rank}[A_{\star}\ B_{\star}]=n rank [ A ⋆ B ⋆ ] = n , then ker ( L ⋆ T P ⋆ ) \ker(L_{\star}^{\mathsf T}P_{\star}) ker ( L ⋆ T P ⋆ ) has dimension m m m and equals range ( B ⋆ ) \operatorname{range}(B_{\star}) range ( B ⋆ ) (since B ⋆ B_{\star} B ⋆ has full column rank), so CI requires range ( B − B ⋆ ) ⊆ range ( B ⋆ ) \operatorname{range}(B-B_{\star})\subseteq\operatorname{range}(B_{\star}) range ( B − B ⋆ ) ⊆ range ( B ⋆ ) , i.e., range ( B ) ⊆ range ( B ⋆ ) \operatorname{range}(B)\subseteq\operatorname{range}(B_{\star}) range ( B ) ⊆ range ( B ⋆ ) , for every B ∈ B B\in\mathcal{B} B ∈ B .
Remark 14 (Constants in the class of Corollary 6) Besides σ min + ( D ⋆ ) ≥ 1 \sigma_{\min}^{+}(D_{\star})\ge1 σ m i n + ( D ⋆ ) ≥ 1 , shown in the proof above, every system in this class satisfies λ min ( S ⋆ ) ≥ α 0 σ min ( B ⋆ ) 2 \lambda_{\min}(S_{\star})\ge\alpha_{0}\sigma_{\min}(B_{\star})^{2} λ m i n ( S ⋆ ) ≥ α 0 σ m i n ( B ⋆ ) 2 , since R = 0 R=0 R = 0 and P ⋆ ⪰ Q ⪰ α 0 I P_{\star}\succeq Q\succeq\alpha_{0}I P ⋆ ⪰ Q ⪰ α 0 I . Moreover, the Lyapunov argument in the proof of Lemma 11 gives ∥ A ⋆ + B ⋆ K 0 ∥ ≤ ν 0 / ( α 0 σ 2 ) \lVert A_{\star}+B_{\star}K_{0}\rVert\le\sqrt{\nu_{0}/(\alpha_{0}\sigma^{2})} ∥ A ⋆ + B ⋆ K 0 ∥ ≤ ν 0 / ( α 0 σ 2 ) , so κ ˉ 0 = ∥ K 0 ∥ \bar{\kappa}_{0}=\lVert K_{0}\rVert κ ˉ 0 = ∥ K 0 ∥ in Remark 15 satisfies κ ˉ 0 ≤ ( ν 0 / ( α 0 σ 2 ) + ϑ ) / σ min ( B ⋆ ) \bar{\kappa}_{0}\le(\sqrt{\nu_{0}/(\alpha_{0}\sigma^{2})}+\vartheta)/\sigma_{\min}(B_{\star}) κ ˉ 0 ≤ ( ν 0 / ( α 0 σ 2 ) + ϑ ) / σ m i n ( B ⋆ ) . Hence, with μ − = 1 \mu_{-}=1 μ − = 1 and s − = α 0 σ min ( B ⋆ ) 2 s_{-}=\alpha_{0}\sigma_{\min}(B_{\star})^{2} s − = α 0 σ m i n ( B ⋆ ) 2 , every constant in Remark 15 and in the proof of Theorem 4 is bounded in terms of the norm and cost bounds of § 4.1.1 and a lower bound on σ min ( B ⋆ ) \sigma_{\min}(B_{\star}) σ m i n ( B ⋆ ) , which gives the uniform bound on C C C stated after Corollary 6.
Proof of the Regret Upper Bound
Remark 15 (Constants for Algorithm 1) Use the supplied norm and cost bounds in § 4.1.1 , and put d = n + m d=n+m d = n + m , q = max { n , m } q=\max\{n,m\} q = max { n , m } . Let κ ˉ 0 \bar{\kappa}_{0} κ ˉ 0 be a known upper bound on ∥ K 0 ∥ \lVert K_{0}\rVert ∥ K 0 ∥ and define
κ 0 = max { ν 0 α 0 σ 2 , κ ˉ 0 , 1 } , γ 0 = 1 2 κ 0 2 . (45) \kappa_{0}=\max\left\{\sqrt{\frac{\nu_{0}}{\alpha_{0}\sigma^{2}}},\bar{\kappa}_{0},1\right\},\qquad\gamma_{0}=\frac{1}{2\kappa_{0}^{2}}. \tag*{(45)} κ 0 = max { α 0 σ 2 ν 0 , κ ˉ 0 , 1 } , γ 0 = 2 κ 0 2 1 . (45)
By the Lyapunov argument in the proof of Lemma 11, K 0 K_{0} K 0 is ( κ 0 , γ 0 ) (\kappa_{0},\gamma_{0}) ( κ 0 , γ 0 ) -strongly stable. Let s − ≤ λ min ( S ⋆ ) s_{-}\le\lambda_{\min}(S_{\star}) s − ≤ λ m i n ( S ⋆ ) and μ − ≤ σ min + ( D ⋆ ) \mu_{-}\le\sigma_{\min}^{+}(D_{\star}) μ − ≤ σ m i n + ( D ⋆ ) be the supplied lower bounds, and put k ˉ ⋆ = ϑ ν / ( σ 2 s − ) ≥ ∥ K ⋆ ∥ \bar{k}_{\star}=\vartheta\nu/(\sigma^{2}s_{-})\ge\lVert K_{\star}\rVert k ˉ ⋆ = ϑ ν / ( σ 2 s − ) ≥ ∥ K ⋆ ∥ (by (19) and ∥ P ⋆ ∥ ≤ J ⋆ / σ 2 \lVert P_{\star}\rVert\le J_{\star}/\sigma^{2} ∥ P ⋆ ∥ ≤ J ⋆ / σ 2 ). Take r C E , C K , C J r_{\mathrm{CE}},C_{K},C_{J} r CE , C K , C J from Lemma 11 and ρ l o c , C p r e d \rho_{\mathrm{loc}},C_{\mathrm{pred}} ρ loc , C pred from Lemma 13, evaluated with the admissible pair ( τ ⋆ , γ ⋆ ) (\tau_{\star},\gamma_{\star}) ( τ ⋆ , γ ⋆ ) following Lemma 8 and with ν / σ 2 \nu/\sigma^{2} ν / σ 2 , α 0 \alpha_{0} α 0 , k ˉ ⋆ \bar{k}_{\star} k ˉ ⋆ , τ ⋆ \tau_{\star} τ ⋆ , ν τ ⋆ / σ 2 \nu\tau_{\star}/\sigma^{2} ν τ ⋆ / σ 2 , ϑ \vartheta ϑ , α 1 + ϑ 2 ν / σ 2 \alpha_{1}+\vartheta^{2}\nu/\sigma^{2} α 1 + ϑ 2 ν / σ 2 , s − s_{-} s − , μ − \mu_{-} μ − in place of ∥ P ⋆ ∥ \lVert P_{\star}\rVert ∥ P ⋆ ∥ , λ min ( P ⋆ ) \lambda_{\min}(P_{\star}) λ m i n ( P ⋆ ) , ∥ K ⋆ ∥ \lVert K_{\star}\rVert ∥ K ⋆ ∥ , ∥ L ⋆ ∥ \lVert L_{\star}\rVert ∥ L ⋆ ∥ , ∥ P ⋆ L ⋆ ∥ \lVert P_{\star}L_{\star}\rVert ∥ P ⋆ L ⋆ ∥ , ∥ A ⋆ ∥ \lVert A_{\star}\rVert ∥ A ⋆ ∥ and ∥ B ⋆ ∥ \lVert B_{\star}\rVert ∥ B ⋆ ∥ , ∥ S ⋆ ∥ \lVert S_{\star}\rVert ∥ S ⋆ ∥ , s ⋆ s_{\star} s ⋆ , μ ⋆ \mu_{\star} μ ⋆ . This is valid because the restrictions in (31) are upper bounds on the radius, so Lemma 9 holds for every smaller radius, and all constants in these lemmas are monotone in the replaced quantities. Then fix
0 < ε 0 ≤ min { ρ l o c , 1 } , (46) 0<\varepsilon_{0}\le\min\{\rho_{\mathrm{loc}},1\}, \tag*{(46)} 0 < ε 0 ≤ min { ρ loc , 1 } , (46)
and set
κ = max { ν + C J ε 0 2 α 0 σ 2 , k ˉ ⋆ + C K ε 0 , 1 } , γ = 1 2 κ 2 . (47) \kappa=\max\left\{\sqrt{\frac{\nu+C_{J}\varepsilon_{0}^{2}}{\alpha_{0}\sigma^{2}}},\bar{k}_{\star}+C_{K}\varepsilon_{0},1\right\},\qquad\gamma=\frac{1}{2\kappa^{2}}. \tag*{(47)} κ = max ⎩ ⎨ ⎧ α 0 σ 2 ν + C J ε 0 2 , k ˉ ⋆ + C K ε 0 , 1 ⎭ ⎬ ⎫ , γ = 2 κ 2 1 . (47)
For a given horizon T ≥ 1 T \ge1 T ≥ 1 , define
x b = 135 σ 2 κ 2 max { κ 0 6 ( 1 + ϑ ) 2 , 4 κ 6 } log ( 5 T ) , λ = ( 1 + max { ( 1 + κ 0 ) 2 , κ 2 } ) x b , (48) \begin{aligned}
x_b &= 135\sigma^2\kappa^2\max\{\kappa_0^6(1+\vartheta)^2,4\kappa^6\}\log(5T),\\
\lambda&= (1+\max\{(1+\kappa_0)^2,\kappa^2\})x_b, \tag*{(48)}
\end{aligned} x b λ = 135 σ 2 κ 2 max { κ 0 6 ( 1 + ϑ ) 2 , 4 κ 6 } log ( 5 T ) , = ( 1 + max {( 1 + κ 0 ) 2 , κ 2 }) x b , (48)
and the integer epoch length
τ 0 = ⌈ 712 ( 1 + κ 0 2 ) λ d ( 1 + ϑ 2 ) σ 2 ε 0 2 ⌉ . (49) \tau_0=\left\lceil\frac{712(1+\kappa_0^2)\lambda d(1+\vartheta^2)}{\sigma^2\varepsilon_0^2}\right\rceil. \tag*{(49)} τ 0 = ⌈ σ 2 ε 0 2 712 ( 1 + κ 0 2 ) λ d ( 1 + ϑ 2 ) ⌉ . (49)
Since κ , κ 0 ≥ 1 \kappa,\kappa_0 \ge1 κ , κ 0 ≥ 1 and ε 0 ≤ 1 \varepsilon_0 \le1 ε 0 ≤ 1 , these choices imply λ ≥ max { 8 n σ 2 log ( 5 T ) , σ 2 / 20 } \lambda\ge\max\{8n\sigma^2\log(5T),\sigma^2/20\} λ ≥ max { 8 n σ 2 log ( 5 T ) , σ 2 /20 } and τ 0 ≥ γ − 1 log ( 2 κ ) + 1 \tau_0 \ge\gamma^{-1}\log(2\kappa)+1 τ 0 ≥ γ − 1 log ( 2 κ ) + 1 ; they also give b ≤ 17 σ 2 κ 4 b \le17\sigma^2\kappa^4 b ≤ 17 σ 2 κ 4 for the constant b b b in (57), and hence
τ 0 − 2 ≥ 1000 9 ( log ( 5 T 2 ) + d log ( 2223 ( 1 + κ 0 2 ) λ / σ 2 ) ) , \tau_0-2\ge\frac{1000}{9}\left(\log(5T^2)+d\log(2223(1+\kappa_0^2)\lambda/\sigma^2)\right), τ 0 − 2 ≥ 9 1000 ( log ( 5 T 2 ) + d log ( 2223 ( 1 + κ 0 2 ) λ / σ 2 ) ) ,
τ 0 − 1 ≥ 1000 9 ( log ( 10 T 3 ) + n log ( 2223 b / σ 2 ) ) . (50) \tau_0-1\ge\frac{1000}{9}\left(\log(10T^3)+n\log(2223b/\sigma^2)\right). \tag*{(50)} τ 0 − 1 ≥ 9 1000 ( log ( 10 T 3 ) + n log ( 2223 b / σ 2 ) ) . (50)
Except in the last step of the proof of Theorem 4 , we consider horizons satisfying T ≥ τ 0 T\ge\tau_0 T ≥ τ 0 .
Lemma 16 Condition on the history at time s s s , including x s x_s x s and a chosen ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly stable gain K K K on the true plant. For an integer N ≥ 1 N\ge1 N ≥ 1 , apply this fixed gain at all times s , … , s + N − 1 s,\ldots,s+N-1 s , … , s + N − 1 , without additional input noise, and put
X = ∑ j = 0 N − 1 x s + j x s + j ⊤ , v = n log 9 + log ( 2 / δ ) , 0 < δ < 1. X=\sum_{j=0}^{N-1}x_{s+j}x_{s+j}^{\top},\qquad v=n\log9+\log(2/\delta),\qquad0<\delta<1. X = j = 0 ∑ N − 1 x s + j x s + j ⊤ , v = n log 9 + log ( 2/ δ ) , 0 < δ < 1. Then, with conditional probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
X ⪯ b N I , b = 4 κ 2 ∥ x s ∥ 2 γ N + 8 σ 2 κ 2 γ + 12 σ 2 κ 2 v γ 2 N . (51) X\preceq bNI,\qquad b=\frac{4\kappa^2\lVert x_s\rVert^2}{\gamma N}+\frac{8\sigma^2\kappa^2}{\gamma}+\frac{12\sigma^2\kappa^2v}{\gamma^2N}. \tag*{(51)} X ⪯ b N I , b = γ N 4 κ 2 ∥ x s ∥ 2 + γ 8 σ 2 κ 2 + γ 2 N 12 σ 2 κ 2 v . (51) and, if moreover N − 1 ≥ 1000 9 ( log ( 2 / δ ) + n log ( 2223 b / σ 2 ) ) N-1\ge\frac{1000}{9}\left(\log(2/\delta)+n\log(2223b/\sigma^2)\right) N − 1 ≥ 9 1000 ( log ( 2/ δ ) + n log ( 2223 b / σ 2 ) ) , then with conditional probability at least 1 − δ 1-\delta 1 − δ also X ⪰ a N I X\succeq aNI X ⪰ a N I with a = 9 σ 2 / 3200 a=9\sigma^2/3200 a = 9 σ 2 /3200 .
Proof. All probabilities below are conditional on the block-start history. Write F = A ⋆ + B ⋆ K F=A_\star+B_\star K F = A ⋆ + B ⋆ K , so ∥ F j ∥ ≤ κ ( 1 − γ ) j \lVert F^j\rVert\le\kappa(1-\gamma)^j ∥ F j ∥ ≤ κ ( 1 − γ ) j . For the upper bound, fix a unit vector u u u and write the stacked observations as
( u ⊤ x s + j ) j = 0 N − 1 = d u + Y u , \left(u^\top x_{s+j}\right)_{j=0}^{N-1}=d_u+Y_u, ( u ⊤ x s + j ) j = 0 N − 1 = d u + Y u ,
where
( d u ) j = u ⊤ F j x s , ( Y u ) j = ∑ ℓ = 0 j − 1 u ⊤ F j − 1 − ℓ w s + ℓ . (d_u)_j=u^\top F^jx_s,\qquad(Y_u)_j=\sum_{\ell=0}^{j-1}u^\top F^{j-1-\ell}w_{s+\ell}. ( d u ) j = u ⊤ F j x s , ( Y u ) j = ℓ = 0 ∑ j − 1 u ⊤ F j − 1 − ℓ w s + ℓ .
The empty sum is zero, and Y u Y_u Y u is centered Gaussian. With C u = Cov ( Y u ) C_u=\operatorname{Cov}(Y_u) C u = Cov ( Y u ) , geometric sums give
∥ d u ∥ 2 ≤ κ 2 ∥ x s ∥ 2 γ , Tr C u ≤ σ 2 κ 2 N γ , ∥ C u ∥ ≤ σ 2 κ 2 γ 2 . \lVert d_u\rVert^2\le\frac{\kappa^2\lVert x_s\rVert^2}{\gamma},\qquad\operatorname{Tr}C_u\le\frac{\sigma^2\kappa^2N}{\gamma},\qquad\lVert C_u\rVert\le\frac{\sigma^2\kappa^2}{\gamma^2}. ∥ d u ∥ 2 ≤ γ κ 2 ∥ x s ∥ 2 , Tr C u ≤ γ σ 2 κ 2 N , ∥ C u ∥ ≤ γ 2 σ 2 κ 2 .
The last bound follows by writing the noise-to-Y u Y_u Y u map as a sum of lag operators, which has norm at most ∑ j ≥ 0 ∥ F j ∥ ≤ κ / γ \sum_{j\ge0}\lVert F^j\rVert\le\kappa/\gamma ∑ j ≥ 0 ∥ F j ∥ ≤ κ / γ . For centered Gaussian Y Y Y with covariance C C C , apply Hsu et al. [9 ] Proposition 1.1 to C 1 / 2 g C^{1/2}g C 1/2 g , where g g g is standard Gaussian. Using 2 Tr ( C 2 ) v ≤ Tr C + ∥ C ∥ v 2\sqrt{\operatorname{Tr}(C^2)v}\le\operatorname{Tr}C+\lVert C\rVert v 2 Tr ( C 2 ) v ≤ Tr C + ∥ C ∥ v gives
P { ∥ Y ∥ 2 > 2 Tr C + 3 ∥ C ∥ v } ≤ e − v . (52) \mathbb{P}\{\lVert Y\rVert^2>2\operatorname{Tr}C+3\lVert C\rVert v\}\le e^{-v}. \tag*{(52)} P {∥ Y ∥ 2 > 2 Tr C + 3 ∥ C ∥ v } ≤ e − v . (52)
By Vershynin [25 ] , there is a deterministic set U \mathcal{U} U of at most 9 n 9^n 9 n unit vectors such that ∥ X ∥ ≤ 2 max u ∈ U u ⊤ X u \lVert X\rVert\le2\max_{u\in\mathcal{U}} u^\top X u ∥ X ∥ ≤ 2 max u ∈ U u ⊤ X u . Apply (52) to Y u Y_u Y u for each u ∈ U u\in\mathcal{U} u ∈ U and use ∥ d u + Y u ∥ 2 ≤ 2 ∥ d u ∥ 2 + 2 ∥ Y u ∥ 2 \lVert d_u+Y_u\rVert^2\le2\lVert d_u\rVert^2+2\lVert Y_u\rVert^2 ∥ d u + Y u ∥ 2 ≤ 2 ∥ d u ∥ 2 + 2 ∥ Y u ∥ 2 . A union bound gives, with probability at least 1 − 9 n e − v = 1 − δ / 2 1-9^n e^{-v}=1-\delta/2 1 − 9 n e − v = 1 − δ /2 ,
∥ X ∥ ≤ 4 κ 2 ∥ x s ∥ 2 2 γ + 8 σ 2 κ 2 N γ + 12 σ 2 κ 2 v γ 2 = b N . \lVert X\rVert\le\frac{4\kappa^2\lVert x_s\rVert_2^2}{\gamma}+\frac{8\sigma^2\kappa^2N}{\gamma}+\frac{12\sigma^2\kappa^2v}{\gamma^2}=bN. ∥ X ∥ ≤ γ 4 κ 2 ∥ x s ∥ 2 2 + γ 8 σ 2 κ 2 N + γ 2 12 σ 2 κ 2 v = b N .
For the lower bound, we omit x s x_s x s , which is fixed under the conditioning. Each of the N − 1 N-1 N − 1 states after it is conditionally Gaussian with covariance σ 2 I \sigma^2I σ 2 I given its past, so its projection on any unit vector exceeds σ \sigma σ in absolute value with conditional probability at least 3 / 10 3/10 3/10 (Simchowitz et al. [22 ] , Eq. (3.12)). These states thus satisfy the ( 1 , Γ s b , 3 / 10 ) (1,\Gamma_{\mathrm{sb}},3/10) ( 1 , Γ sb , 3/10 ) -block martingale small-ball condition of Simchowitz et al. [22 ] (Definition 2.1) with Γ s b = σ 2 I \Gamma_{\mathrm{sb}}=\sigma^2I Γ sb = σ 2 I , and, as N ≤ 2 ( N − 1 ) N\le2(N-1) N ≤ 2 ( N − 1 ) , on the event X ⪯ b N I X\preceq bNI X ⪯ b N I their Gram matrix is at most ( N − 1 ) Γ ˉ (N-1)\bar{\Gamma} ( N − 1 ) Γ ˉ with Γ ˉ = 2 b ˉ I ⪰ Γ s b \bar{\Gamma}=2\bar{b}I\succeq\Gamma_{\mathrm{sb}} Γ ˉ = 2 b ˉ I ⪰ Γ sb . The condition on N N N is Simchowitz et al. [22 ] (Eq. (2.7)) with failure probability δ / 2 \delta/2 δ /2 , so the argument of Simchowitz et al. [22 ] (Appendix D.1) shows that, with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 , either X ⋠ b N I X\npreceq bNI X ⋠ b N I or X ⪰ 9 ( N − 1 ) σ 2 I / 1600 ⪰ a N I X\succeq9(N-1)\sigma^2I/1600\succeq aNI X ⪰ 9 ( N − 1 ) σ 2 I /1600 ⪰ a N I ; see also Ziemann et al. [29 ] . Combining the two failure probabilities proves the claim.
Lemma 17 (cf. Abbasi-Yadkori et al. (2011, Lemma 11)). Let λ > 0 \lambda>0 λ > 0 and z 1 , … , z T ∈ R d z_1,\ldots,z_T\in\mathbb{R}^d z 1 , … , z T ∈ R d . Let τ 0 < τ 1 < ⋯ < τ N = T + 1 \tau_0<\tau_1<\cdots<\tau_N=T+1 τ 0 < τ 1 < ⋯ < τ N = T + 1 , with epoch i i i equal to { τ i , … , τ i + 1 − 1 } \{\tau_i,\ldots,\tau_{i+1}-1\} { τ i , … , τ i + 1 − 1 } for 0 ≤ i < N 0\le i<N 0 ≤ i < N . Define V t = λ I d + ∑ s = 1 t − 1 z s z s ⊤ V_t=\lambda I_d+\sum_{s=1}^{t-1}z_sz_s^\top V t = λ I d + ∑ s = 1 t − 1 z s z s ⊤ and Z i = ∑ t = τ i τ i + 1 − 1 z t z t ⊤ Z_i=\sum_{t=\tau_i}^{\tau_{i+1}-1}z_tz_t^\top Z i = ∑ t = τ i τ i + 1 − 1 z t z t ⊤ , so that V τ i + 1 = V τ i + Z i V_{\tau_{i+1}}=V_{\tau_i}+Z_i V τ i + 1 = V τ i + Z i . If c > 0 c>0 c > 0 and λ max ( V τ i − 1 / 2 Z i V τ i − 1 / 2 ) ≤ c \lambda_{\max}(V_{\tau_i}^{-1/2}Z_iV_{\tau_i}^{-1/2})\le c λ m a x ( V τ i − 1/2 Z i V τ i − 1/2 ) ≤ c for every 0 ≤ i < N 0\le i<N 0 ≤ i < N , then
∑ i = 0 N − 1 ∑ t = τ i τ i + 1 − 1 ∥ z t ∥ V τ i − 1 2 ≤ c log ( 1 + c ) log det ( V T + 1 ) det ( V τ 0 ) . \sum_{i=0}^{N-1}\sum_{t=\tau_i}^{\tau_{i+1}-1}\lVert z_t\rVert_{V_{\tau_i}^{-1}}^2\le\frac{c}{\log(1+c)}\log\frac{\det(V_{T+1})}{\det(V_{\tau_0})}. i = 0 ∑ N − 1 t = τ i ∑ τ i + 1 − 1 ∥ z t ∥ V τ i − 1 2 ≤ log ( 1 + c ) c log det ( V τ 0 ) det ( V T + 1 ) .
Proof. As in Abbasi-Yadkori et al. (2011, Lemma 11), put M i = V τ i − 1 / 2 Z i V τ i − 1 / 2 M_i=V_{\tau_i}^{-1/2}Z_iV_{\tau_i}^{-1/2} M i = V τ i − 1/2 Z i V τ i − 1/2 , so that 0 ⪯ M i ⪯ c I 0\preceq M_i\preceq cI 0 ⪯ M i ⪯ c I . Concavity of log ( 1 + x ) \log(1+x) log ( 1 + x ) gives x ≤ c log ( 1 + x ) / log ( 1 + c ) x\le c\log(1+x)/\log(1+c) x ≤ c log ( 1 + x ) / log ( 1 + c ) for 0 ≤ x ≤ c 0\le x\le c 0 ≤ x ≤ c . Applying this inequality to the eigenvalues of M i M_i M i yields
∑ t = τ i τ i + 1 − 1 ∥ z t ∥ V τ i − 1 2 = Tr ( M i ) ≤ c log ( 1 + c ) log det ( I + M i ) = c log ( 1 + c ) log det ( V τ i + 1 ) det ( V τ i ) . \begin{aligned}
\sum_{t=\tau_i}^{\tau_{i+1}-1}\lVert z_t\rVert_{V_{\tau_i}^{-1}}^2=\operatorname{Tr}(M_i) \\
&\le\frac{c}{\log(1+c)}\log\det(I+M_i) \\
&=\frac{c}{\log(1+c)}\log\frac{\det(V_{\tau_{i+1}})}{\det(V_{\tau_i})}.
\end{aligned} t = τ i ∑ τ i + 1 − 1 ∥ z t ∥ V τ i − 1 2 = Tr ( M i ) ≤ log ( 1 + c ) c log det ( I + M i ) = log ( 1 + c ) c log det ( V τ i ) det ( V τ i + 1 ) .
Summing over i i i telescopes the log-determinant ratios.
From now on, use the assumptions and algorithm of Theorem 4 , with the parameters of Remark 15. Put
V t = λ I d + ∑ s = 1 t − 1 z s z s ⊤ , ∥ M ∥ V t 2 = Tr ( M V t M ⊤ ) . V_t=\lambda I_d+\sum_{s=1}^{t-1}z_sz_s^\top,\qquad\lVert M\rVert_{V_t}^2=\operatorname{Tr}(MV_tM^\top). V t = λ I d + s = 1 ∑ t − 1 z s z s ⊤ , ∥ M ∥ V t 2 = Tr ( M V t M ⊤ ) .
Before abort, hold Θ ^ t \widehat{\Theta}_t Θ t , P ^ t \widehat{P}_t P t , K t K_t K t equal to their values at τ i \tau_i τ i for τ i ≤ t < τ i + 1 \tau_i \le t < \tau_{i+1} τ i ≤ t < τ i + 1 . Define
D t = ∥ u t − K ⋆ x t ∥ ⋆ 2 , Δ τ i = Θ ^ τ i − Θ ⋆ , b 0 = ϑ 2 τ 0 σ 2 3200 ( 1 + κ 0 2 ) . D_t = \lVert u_t - K_\star x_t\rVert^2_\star,\qquad\Delta_{\tau_i} = \widehat{\Theta}_{\tau_i} - \Theta_\star,\qquad b_0 = \frac{\vartheta^2 \tau_0 \sigma^2}{3200(1+\kappa_0^2)}. D t = ∥ u t − K ⋆ x t ∥ ⋆ 2 , Δ τ i = Θ τ i − Θ ⋆ , b 0 = 3200 ( 1 + κ 0 2 ) ϑ 2 τ 0 σ 2 .
For the analysis, define the constrained estimator at every epoch boundary from the observed data, even on paths on which the algorithm has already aborted and does not actually compute it. This latent definition does not affect the actions and makes the following events globally defined. We use the events below, where η t \eta_t η t , t ≥ τ 0 t \ge\tau_0 t ≥ τ 0 , are auxiliary independent N ( 0 , σ 2 I m ) \mathcal{N}(0,\sigma^2 I_m) N ( 0 , σ 2 I m ) variables not used by the algorithm.
E Θ = { Tr ( Δ τ i V τ i Δ τ i ⊤ ) ≤ 4 σ 2 n log ( 5 n T 2 det ( V τ i ) det ( V 1 ) ) + 2 λ ∥ Θ ⋆ ∥ F 2 , 0 ≤ i < N T } (53) \mathcal{E}_{\Theta} = \left\{
\begin{aligned}
\operatorname{Tr}\left(\Delta_{\tau_i}V_{\tau_i}\Delta_{\tau_i}^{\top}\right)
&\le4\sigma^2 n\log\left(5nT^2\frac{\det(V_{\tau_i})}{\det(V_1)}\right)+2\lambda\lVert\Theta_\star\rVert_F^2,\\
&0\le i<N_T
\end{aligned}
\right\} \tag*{(53)} E Θ = ⎩ ⎨ ⎧ Tr ( Δ τ i V τ i Δ τ i ⊤ ) ≤ 4 σ 2 n log ( 5 n T 2 det ( V 1 ) det ( V τ i ) ) + 2 λ ∥ Θ ⋆ ∥ F 2 , 0 ≤ i < N T ⎭ ⎬ ⎫ (53)
E z i n i t = { ∑ t = 2 τ 0 − 1 z t z t ⊤ ⪰ 9 ( τ 0 − 2 ) σ 2 3200 ( 1 + κ 0 2 ) I d } (54) \mathcal{E}^{\mathrm{init}}_z = \left\{
\sum_{t=2}^{\tau_0-1} z_t z_t^{\top} \succeq\frac{9(\tau_0-2)\sigma^2}{3200(1+\kappa_0^2)}I_d
\right\} \tag*{(54)} E z init = { t = 2 ∑ τ 0 − 1 z t z t ⊤ ⪰ 3200 ( 1 + κ 0 2 ) 9 ( τ 0 − 2 ) σ 2 I d } (54)
E w = { max 1 ≤ t ≤ T ∥ w t ∥ ≤ σ 15 q log ( 5 T ) } (55) \mathcal{E}_w = \left\{\max_{1\le t\le T}\lVert w_t\rVert\le\sigma\sqrt{15q\log(5T)}\right\} \tag*{(55)} E w = { 1 ≤ t ≤ T max ∥ w t ∥ ≤ σ 15 q log ( 5 T ) } (55)
E η = { max 1 ≤ t < T ∥ η t ∥ ≤ σ 15 q log ( 5 T ) } . (56) \mathcal{E}_{\eta} = \left\{\max_{1\le t<T}\lVert\eta_t\rVert\le\sigma\sqrt{15q\log(5T)}\right\}. \tag*{(56)} E η = { 1 ≤ t < T max ∥ η t ∥ ≤ σ 15 q log ( 5 T ) } . (56)
Then we have the following lemma.
Lemma 18 Let
E i n i t = E Θ ∩ E z i n i t ∩ E w ∩ E η . \mathcal{E}_{\mathrm{init}}=\mathcal{E}_{\Theta}\cap\mathcal{E}^{\mathrm{init}}_z\cap\mathcal{E}_w\cap\mathcal{E}_{\eta}. E init = E Θ ∩ E z init ∩ E w ∩ E η . Then, under the choices in Remark 15,
P ( E i n i t c ) ≤ 4 / ( 5 T 2 ) . \mathbb{P}(\mathcal{E}_{\mathrm{init}}^c)\le4/(5T^2). P ( E init c ) ≤ 4/ ( 5 T 2 ) . Moreover, on E w ∩ E η \mathcal{E}_w\cap\mathcal{E}_{\eta} E w ∩ E η , ∥ x t ∥ 2 ≤ x b \lVert x_t\rVert^2\le x_b ∥ x t ∥ 2 ≤ x b for t ≤ τ 0 t\le\tau_0 t ≤ τ 0 and ∥ z t ∥ 2 ≤ λ \lVert z_t\rVert^2\le\lambda ∥ z t ∥ 2 ≤ λ for t < τ 0 t<\tau_0 t < τ 0 .
Proof. Let Θ ~ t \widetilde{\Theta}_t Θ t be the unconstrained ridge estimate. By Cassel et al. [5 ] with δ = 1 / ( 5 T 2 ) \delta=1/(5T^2) δ = 1/ ( 5 T 2 ) , the inequality in (53) holds for Θ ~ t \widetilde{\Theta}_t Θ t at all t t t with probability at least 1 − 1 / ( 5 T 2 ) 1-1/(5T^2) 1 − 1/ ( 5 T 2 ) . Completing the square in (7) shows that Θ ^ t \widehat{\Theta}_t Θ t is the V t V_t V t -orthogonal projection of Θ ~ t \widetilde{\Theta}_t Θ t onto the affine set C ∋ Θ ⋆ \mathcal{C}\ni\Theta_\star C ∋ Θ ⋆ , so ∥ Θ ^ t − Θ ⋆ ∥ V t ≤ ∥ Θ ~ t − Θ ⋆ ∥ V t \lVert\widehat{\Theta}_t-\Theta_\star\rVert_{V_t}\le\lVert\widetilde{\Theta}_t-\Theta_\star\rVert_{V_t} ∥ Θ t − Θ ⋆ ∥ V t ≤ ∥ Θ t − Θ ⋆ ∥ V t , and P ( E Θ ) ≥ 1 − 1 / ( 5 T 2 ) \mathbb{P}(\mathcal{E}_{\Theta})\ge1-1/(5T^2) P ( E Θ ) ≥ 1 − 1/ ( 5 T 2 ) .
By Cassel et al. [5 ] with δ = 1 / ( 5 T 2 ) \delta=1/(5T^2) δ = 1/ ( 5 T 2 ) , n , m ≤ q n,m\le q n , m ≤ q , and log ( 5 T 3 ) ≤ 3 log ( 5 T ) \log(5T^3)\le3\log(5T) log ( 5 T 3 ) ≤ 3 log ( 5 T ) , P ( E w ) , P ( E η ) ≥ 1 − 1 / ( 5 T 2 ) \mathbb{P}(\mathcal{E}_w),\mathbb{P}(\mathcal{E}_{\eta})\ge1-1/(5T^2) P ( E w ) , P ( E η ) ≥ 1 − 1/ ( 5 T 2 ) . On E w ∩ E η \mathcal{E}_w\cap\mathcal{E}_{\eta} E w ∩ E η , the states for t ≤ τ 0 t\le\tau_0 t ≤ τ 0 are generated by the ( κ 0 , γ 0 ) (\kappa_0,\gamma_0) ( κ 0 , γ 0 ) -strongly stable gain K 0 K_0 K 0 under the disturbances w t + B ⋆ η t w_t+B_\star\eta_t w t + B ⋆ η t , whose norms are at most σ ( 1 + ϑ ) 15 q log ( 5 T ) \sigma(1+\vartheta)\sqrt{15q\log(5T)} σ ( 1 + ϑ ) 15 q log ( 5 T ) . Hence Cassel et al. [5 ] and γ 0 − 1 = 2 κ 0 2 \gamma_0^{-1}=2\kappa_0^2 γ 0 − 1 = 2 κ 0 2 give ∥ x t ∥ 2 ≤ 60 q σ 2 κ 0 6 ( 1 + ϑ ) 2 log ( 5 T ) ≤ x b \lVert x_t\rVert^2\le60q\sigma^2\kappa_0^6(1+\vartheta)^2\log(5T)\le x_b ∥ x t ∥ 2 ≤ 60 q σ 2 κ 0 6 ( 1 + ϑ ) 2 log ( 5 T ) ≤ x b . Since u t = K 0 x t + η t u_t=K_0x_t+\eta_t u t = K 0 x t + η t and ∥ η t ∥ ≤ σ 15 q log ( 5 T ) ≤ x b / 3 \lVert\eta_t\rVert\le\sigma\sqrt{15q\log(5T)}\le\sqrt{x_b}/3 ∥ η t ∥ ≤ σ 15 q log ( 5 T ) ≤ x b /3 , also ∥ z t ∥ 2 ≤ ( 1 + ( 1 + κ 0 ) 2 ) x b ≤ λ \lVert z_t\rVert^2\le(1+(1+\kappa_0)^2)x_b\le\lambda ∥ z t ∥ 2 ≤ ( 1 + ( 1 + κ 0 ) 2 ) x b ≤ λ for t < τ 0 t<\tau_0 t < τ 0 , which proves the second claim.
It remains to bound P ( E w ∩ E η ∩ ( E z i n i t ) c ) \mathbb{P}(\mathcal{E}_w\cap\mathcal{E}_{\eta}\cap(\mathcal{E}^{\mathrm{init}}_z)^c) P ( E w ∩ E η ∩ ( E z init ) c ) . During the warm-up, z t = U ( x t , η t ⊤ ) ⊤ z_t=U(x_t,\eta_t^{\top})^{\top} z t = U ( x t , η t ⊤ ) ⊤ with U = [ I 0 ; K 0 I ] U=[I\ 0;K_0\ I] U = [ I 0 ; K 0 I ] . For t ≥ 2 t\ge2 t ≥ 2 , given F t − 1 = σ ( x 1 , u 1 , … , x t − 1 , u t − 1 ) \mathcal{F}_{t-1}=\sigma(x_1,u_1,\ldots,x_{t-1},u_{t-1}) F t − 1 = σ ( x 1 , u 1 , … , x t − 1 , u t − 1 ) , the vector ( x t , η t ) (x_t,\eta_t) ( x t , η t ) is Gaussian with covariance σ 2 I \sigma^2 I σ 2 I ; z 1 z_1 z 1 is excluded because x 1 = 0 x_1 = 0 x 1 = 0 . Since ∥ U − 1 ∥ ≤ 1 + κ 0 \lVert U^{-1}\rVert\le1 + \kappa_0 ∥ U − 1 ∥ ≤ 1 + κ 0 , z t z_t z t is conditionally Gaussian with covariance σ 2 U U ⊤ ⪰ σ 2 I / ( 1 + κ 0 ) 2 \sigma^2 UU^\top\succeq\sigma^2 I/(1+\kappa_0)^2 σ 2 U U ⊤ ⪰ σ 2 I / ( 1 + κ 0 ) 2 , so by Simchowitz et al. [22 ] Eq. (3.12) its projection on any unit vector exceeds σ / ( 1 + κ 0 ) \sigma/(1+\kappa_0) σ / ( 1 + κ 0 ) in absolute value with conditional probability at least 3 / 10 3/10 3/10 . As ( 1 + κ 0 ) 2 ≤ 2 ( 1 + κ 0 2 ) (1+\kappa_0)^2 \le2(1+\kappa_0^2) ( 1 + κ 0 ) 2 ≤ 2 ( 1 + κ 0 2 ) , ( z t ) 2 ≤ t < τ 0 (z_t)_{2\le t<\tau_0} ( z t ) 2 ≤ t < τ 0 thus satisfies the ( 1 , Γ s b , 3 / 10 ) (1,\Gamma_{\rm sb},3/10) ( 1 , Γ sb , 3/10 ) -block martingale small-ball condition of Simchowitz et al. [22 ] Definition 2.1 with Γ s b = σ 2 I / ( 2 ( 1 + κ 0 2 ) ) \Gamma_{\rm sb}=\sigma^2 I/(2(1+\kappa_0^2)) Γ sb = σ 2 I / ( 2 ( 1 + κ 0 2 )) , and, on E w ∩ E η \mathcal{E}_w\cap\mathcal{E}_\eta E w ∩ E η , its Gram matrix is at most ( τ 0 − 2 ) Γ ˉ (\tau_0-2)\bar{\Gamma} ( τ 0 − 2 ) Γ ˉ with Γ ˉ = λ I ⪰ Γ s b \bar{\Gamma}=\lambda I\succeq\Gamma_{\rm sb} Γ ˉ = λ I ⪰ Γ sb . The first inequality in (50) is Simchowitz et al. [22 ] Eq. (2.7) with failure probability 1 / ( 5 T 2 ) 1/(5T^2) 1/ ( 5 T 2 ) , so the argument of Simchowitz et al. [22 ] Appendix D.1 gives P ( E w ∩ E η ∩ ( E z i n i t ) c ) ≤ 1 / ( 5 T 2 ) \mathbb{P}(\mathcal{E}_w\cap\mathcal{E}_\eta\cap(\mathcal{E}_z^{\mathrm{init}})^c)\le1/(5T^2) P ( E w ∩ E η ∩ ( E z init ) c ) ≤ 1/ ( 5 T 2 ) . A union bound concludes.
Lemma 19 [cf. 5 Lemma 7] On E i n i t \mathcal{E}_{\mathrm{init}} E init , the algorithm never aborts, and for all 1 ≤ t ≤ T 1\le t\le T 1 ≤ t ≤ T and 0 ≤ i < N T 0\le i<N_T 0 ≤ i < N T :
∥ x t ∥ 2 ≤ x b \lVert x_t\rVert^2\le x_b ∥ x t ∥ 2 ≤ x b and ∥ z t ∥ 2 ≤ λ \lVert z_t\rVert^2\le\lambda ∥ z t ∥ 2 ≤ λ ;
∥ Δ τ i ∥ V τ i ≤ b 0 \lVert\Delta_{\tau_i}\rVert_{V_{\tau_i}}\le b_0 ∥ Δ τ i ∥ V τ i ≤ b 0 and ∥ Δ τ i ∥ F ≤ ϵ 0 \lVert\Delta_{\tau_i}\rVert_F\le\epsilon_0 ∥ Δ τ i ∥ F ≤ ϵ 0 , where V τ i ⪰ 9 τ 0 σ 2 I / ( 3200 ( 1 + κ 0 2 ) ) V_{\tau_i}\succeq9\tau_0\sigma^2 I/(3200(1+\kappa_0^2)) V τ i ⪰ 9 τ 0 σ 2 I / ( 3200 ( 1 + κ 0 2 )) ;
K τ i K_{\tau_i} K τ i passes the checks of Algorithm 1 and is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly stable.
Proof. The argument follows Cassel et al. [5 ] (Lemmas 7, 19, and 22). Warm-up. By Lemma 18, ∥ x t ∥ 2 ≤ x b \lVert x_t\rVert^2\le x_b ∥ x t ∥ 2 ≤ x b for t ≤ τ 0 t\le\tau_0 t ≤ τ 0 and ∥ z t ∥ 2 ≤ λ \lVert z_t\rVert^2\le\lambda ∥ z t ∥ 2 ≤ λ for t < τ 0 t<\tau_0 t < τ 0 . On E i n i t \mathcal{E}_{\mathrm{init}} E init and since λ ≥ σ 2 / 20 \lambda\ge\sigma^2/20 λ ≥ σ 2 /20 , V τ i ⪰ V τ 0 ⪰ 9 τ 0 σ 2 3200 ( 1 + κ 0 2 ) I V_{\tau_i}\succeq V_{\tau_0}\succeq\frac{9\tau_0\sigma^2}{3200(1+\kappa_0^2)}I V τ i ⪰ V τ 0 ⪰ 3200 ( 1 + κ 0 2 ) 9 τ 0 σ 2 I for all i i i .
Estimation. Fix i i i and suppose that ∥ z t ∥ 2 ≤ λ \lVert z_t\rVert^2\le\lambda ∥ z t ∥ 2 ≤ λ for all t < τ i t<\tau_i t < τ i ; for i = 0 i=0 i = 0 , this holds by the warm-up step. Then Cassel et al. [5 ] (Lemma 37) gives log ( det V τ i / det V 1 ) ≤ d log T \log(\det V_{\tau_i}/\det V_1)\le d\log T log ( det V τ i / det V 1 ) ≤ d log T , so E Θ \mathcal{E}_\Theta E Θ , ∥ Θ ⋆ ∥ F 2 ≤ d ϑ 2 \lVert\Theta_\star\rVert_F^2\le d\vartheta^2 ∥ Θ ⋆ ∥ F 2 ≤ d ϑ 2 , n ≤ T n\le T n ≤ T , and λ ≥ 8 n σ 2 log ( 5 T ) \lambda\ge8n\sigma^2\log(5T) λ ≥ 8 n σ 2 log ( 5 T ) give
∥ Δ τ i ∥ V τ i ≤ 4 σ 2 n ( log ( 5 n T 2 ) + d log T ) + 2 λ d ϑ 2 ≤ 2 λ d ( 1 + ϑ 2 ) ≤ b 0 , \lVert\Delta_{\tau_i}\rVert_{V_{\tau_i}}\le4\sigma^2 n\bigl(\log(5nT^2)+d\log T\bigr)+2\lambda d\vartheta^2
\le2\lambda d(1+\vartheta^2)\le b_0, ∥ Δ τ i ∥ V τ i ≤ 4 σ 2 n ( log ( 5 n T 2 ) + d log T ) + 2 λ d ϑ 2 ≤ 2 λ d ( 1 + ϑ 2 ) ≤ b 0 ,
where the last step is (49) . With the lower bound on V τ i V_{\tau_i} V τ i , this gives ∥ Δ τ i ∥ F ≤ ϵ 0 \lVert\Delta_{\tau_i}\rVert_F\le\epsilon_0 ∥ Δ τ i ∥ F ≤ ϵ 0 . Hence, by Lemmas 9 and 11 , the estimated DARE has a positive definite stabilizing solution with S ^ τ i ≻ 0 \widehat{S}_{\tau_i}\succ0 S τ i ≻ 0 , and K τ i K_{\tau_i} K τ i is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly stable; in particular, it passes the checks of Algorithm 1. This proves claims 2 and 3 at epoch i i i .
No abort. We show by induction over i i i that ∥ z t ∥ 2 ≤ λ \lVert z_t\rVert^2\le\lambda ∥ z t ∥ 2 ≤ λ for all t < τ i t<\tau_i t < τ i and that no abort occurs before τ i \tau_i τ i ; the warm-up step gives the base case i = 0 i=0 i = 0 . Assume this holds for i i i . By the estimation step, applied at epochs 0 , … , i 0,\ldots,i 0 , … , i , the state evolves from τ 0 \tau_0 τ 0 to τ i + 1 \tau_{i+1} τ i + 1 under ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly stable gains that pass the checks, each held for τ 0 ≥ γ − 1 log ( 2 κ ) \tau_0\ge\gamma^{-1}\log(2\kappa) τ 0 ≥ γ − 1 log ( 2 κ ) steps except possibly the last. Since the halving step in the proof of Cassel et al. [5 ] (Lemma 39) is used only at controller switches, that lemma and E w \mathcal{E}_w E w give, for τ 0 ≤ t ≤ τ i + 1 \tau_0\le t\le\tau_{i+1} τ 0 ≤ t ≤ τ i + 1 ,
∥ x t ∥ ≤ 3 κ max { 1 2 ∥ x τ 0 ∥ , κ γ max s ≤ T ∥ w s ∥ } ≤ x b \lVert x_t\rVert\le3\kappa\max\left\{\frac{1}{2}\lVert x_{\tau_0}\rVert,\frac{\kappa}{\gamma}\max_{s\le T}\lVert w_s\rVert\right\}\le\sqrt{x_b} ∥ x t ∥ ≤ 3 κ max { 2 1 ∥ x τ 0 ∥ , γ κ s ≤ T max ∥ w s ∥ } ≤ x b
by (48) . Hence no state-triggered abort occurs before τ i + 1 \tau_{i+1} τ i + 1 , and ∥ z t ∥ 2 ≤ ( 1 + κ 2 ) x b ≤ λ \lVert z_t\rVert^2\le(1+\kappa^2)x_b\le\lambda ∥ z t ∥ 2 ≤ ( 1 + κ 2 ) x b ≤ λ for τ 0 ≤ t < τ i + 1 \tau_0\le t<\tau_{i+1} τ 0 ≤ t < τ i + 1 , which completes the induction and proves claim 1. ◼
Lemma 20 Let N i = τ i + 1 − τ i N_i=\tau_{i+1}-\tau_i N i = τ i + 1 − τ i , let F f u l l = { 0 ≤ i < N T : N i = τ 0 } \mathcal{F}_{\mathrm{full}}=\{0\le i<N_T:N_i=\tau_0\} F full = { 0 ≤ i < N T : N i = τ 0 } , and put
v T = n log 9 + log ( 10 T 3 ) , a = 9 σ 2 3200 , (57) v_T=n\log9+\log(10T^3),\qquad a=\frac{9\sigma^2}{3200}, \tag*{(57)} v T = n log 9 + log ( 10 T 3 ) , a = 3200 9 σ 2 , (57) b = 4 κ 2 x b γ τ 0 + 8 σ 2 κ 2 γ + 12 σ 2 κ 2 v T γ 2 τ 0 . (58) b=\frac{4\kappa^2x_b}{\gamma\tau_0}+\frac{8\sigma^2\kappa^2}{\gamma}+\frac{12\sigma^2\kappa^2v_T}{\gamma^2\tau_0}. \tag*{(58)} b = γ τ 0 4 κ 2 x b + γ 8 σ 2 κ 2 + γ 2 τ 0 12 σ 2 κ 2 v T . (58) For the actual state blocks X i = ∑ t = τ i τ i + 1 − 1 x t x t T X_i=\sum_{t=\tau_i}^{\tau_{i+1}-1}x_tx_t^\mathsf{T} X i = ∑ t = τ i τ i + 1 − 1 x t x t T , define
E x = { X i ⪯ b τ 0 I for all 0 ≤ i < N T , X i ⪰ a τ 0 I for all i ∈ F f u l l } . (59) \mathcal{E}_x=\left\{\begin{aligned}
&X_i\preceq b\tau_0I\text{ for all }0\le i<N_T,\\
&X_i\succeq a\tau_0I\text{ for all }i\in\mathcal{F}_{\mathrm{full}}
\end{aligned}\right\}. \tag*{(59)} E x = { X i ⪯ b τ 0 I for all 0 ≤ i < N T , X i ⪰ a τ 0 I for all i ∈ F full } . (59) Then E s u c c = E i n i t ∩ E x \mathcal{E}_{\mathrm{succ}}=\mathcal{E}_{\mathrm{init}}\cap\mathcal{E}_x E succ = E init ∩ E x satisfies P ( E s u c c ) ≥ 1 − T − 2 \mathbb{P}(\mathcal{E}_{\mathrm{succ}})\ge1-T^{-2} P ( E succ ) ≥ 1 − T − 2 .
Proof. For each i i i , let G i ∈ F τ i G_i\in\mathcal{F}_{\tau_i} G i ∈ F τ i be the event that no abort occurred before τ i \tau_i τ i , ∥ x τ i ∥ 2 ≤ x b \lVert x_{\tau_i}\rVert^2\le x_b ∥ x τ i ∥ 2 ≤ x b , and K τ i K_{\tau_i} K τ i is ( κ , γ ) (\kappa,\gamma) ( κ , γ ) -strongly stable, and let X ~ i \widetilde{X}_i X i be the Gram matrix of the states obtained from x τ i x_{\tau_i} x τ i by applying K τ i K_{\tau_i} K τ i throughout epoch i i i , regardless of the abort rule. Conditionally on F τ i \mathcal{F}_{\tau_i} F τ i and on G i G_i G i , Lemma 16 with δ = 1 / ( 5 T 3 ) \delta=1/(5T^3) δ = 1/ ( 5 T 3 ) shows that X ~ i \widetilde{X}_i X i violates the bounds in (59) with probability at most 1 / ( 5 T 3 ) 1/(5T^3) 1/ ( 5 T 3 ) ; the upper bound uses N i ≤ τ 0 N_i\le\tau_0 N i ≤ τ 0 and ∥ x τ i ∥ 2 ≤ x b \lVert x_{\tau_i}\rVert^2\le x_b ∥ x τ i ∥ 2 ≤ x b , and the lower bound for full epochs uses the second inequality in (50) . On E i n i t \mathcal{E}_{\mathrm{init}} E init , Lemma 19 shows that every G i G_i G i holds and X ~ i = X i \widetilde{X}_i=X_i X i = X i . Hence E i n i t ∩ E x c \mathcal{E}_{\mathrm{init}}\cap\mathcal{E}_x^c E init ∩ E x c is contained in the union over i i i of the events G i ∩ { X ~ i G_i\cap\{\widetilde{X}_i G i ∩ { X i violates the bounds} \} } , and a union bound gives P ( E i n i t ∩ E x c ) ≤ N T / ( 5 T 3 ) ≤ 1 / ( 5 T 2 ) \mathbb{P}(\mathcal{E}_{\mathrm{init}}\cap\mathcal{E}_x^c)\le N_T/(5T^3)\le1/(5T^2) P ( E init ∩ E x c ) ≤ N T / ( 5 T 3 ) ≤ 1/ ( 5 T 2 ) . Together with Lemma 18 , this proves the claim.
Lemma 21 Let a , b a,b a , b be as in (57), and put
c = b ( 1 + κ 2 ) ( 1 + κ 0 2 ) a . (60) c=\frac{b(1+\kappa^2)(1+\kappa_0^2)}{a}. \tag*{(60)} c = a b ( 1 + κ 2 ) ( 1 + κ 0 2 ) . (60) If CI holds at θ ⋆ \theta_\star θ ⋆ , then on E s u c c \mathcal{E}_{\mathrm{succ}} E succ
∑ t = τ 0 T D t ≤ ∥ S ⋆ ∥ b a C p r e d 2 b 0 c log ( 1 + c ) d log ( T + 1 ) + 1 { N T − 1 < τ 0 } ∥ S ⋆ ∥ b τ 0 C K 2 ε 0 2 . (61) \sum_{t=\tau_0}^{T}D_t\le\lVert S_\star\rVert\frac{b}{a}C_{\mathrm{pred}}^2b_0\frac{c}{\log(1+c)}d\log(T+1)+\mathbf{1}_{\{N_{T-1}<\tau_0\}}\lVert S_\star\rVert b\tau_0C_K^2\varepsilon_0^2. \tag*{(61)} t = τ 0 ∑ T D t ≤ ∥ S ⋆ ∥ a b C pred 2 b 0 log ( 1 + c ) c d log ( T + 1 ) + 1 { N T − 1 < τ 0 } ∥ S ⋆ ∥ b τ 0 C K 2 ε 0 2 . (61) If D ⋆ = 0 D_\star=0 D ⋆ = 0 , the left side is zero.
Proof. On E s u c c \mathcal{E}_{\mathrm{succ}} E succ , Lemma 19 gives no abort and ∥ Δ τ i ∥ F ≤ ε 0 ≤ ρ l o c \lVert\Delta_{\tau_i}\rVert_F\le\varepsilon_0\le\rho_{\mathrm{loc}} ∥ Δ τ i ∥ F ≤ ε 0 ≤ ρ loc . Since the parametrization (2) is isometric, this is also the parameter-error bound required by Lemma 13 , whose assumption (43) is CI by Lemma 12 . Put Z i = ∑ t = τ i τ i + 1 − 1 z t z t T Z_i=\sum_{t=\tau_i}^{\tau_{i+1}-1}z_tz_t^\mathsf{T} Z i = ∑ t = τ i τ i + 1 − 1 z t z t T and Π i = Δ τ i [ I ; K τ i ] \Pi_i=\Delta_{\tau_i}[I;K_{\tau_i}] Π i = Δ τ i [ I ; K τ i ] . For each full block, the covariance bounds and that lemma give
∑ t = τ i τ i + 1 − 1 D t ≤ b τ 0 ∥ S ⋆ ∥ ∥ K τ i − K ⋆ ∥ F 2 \sum_{t=\tau_i}^{\tau_{i+1}-1}D_t\le b\tau_0\lVert S_\star\rVert\lVert K_{\tau_i}-K_\star\rVert_F^2 t = τ i ∑ τ i + 1 − 1 D t ≤ b τ 0 ∥ S ⋆ ∥ ∥ K τ i − K ⋆ ∥ F 2 ≤ b τ 0 ∥ S ⋆ ∥ C p r e d 2 ∥ Π i ∥ F 2 \le b\tau_0\lVert S_\star\rVert C_{\mathrm{pred}}^2\lVert\Pi_i\rVert_F^2 ≤ b τ 0 ∥ S ⋆ ∥ C pred 2 ∥ Π i ∥ F 2 ≤ ∥ S ⋆ ∥ b a C p r e d 2 ∑ t = τ i τ i + 1 − 1 ∥ Δ τ i z t ∥ 2 . (62) \le\lVert S_\star\rVert\frac{b}{a}C_{\mathrm{pred}}^2\sum_{t=\tau_i}^{\tau_{i+1}-1}\lVert\Delta_{\tau_i}z_t\rVert^2. \tag*{(62)} ≤ ∥ S ⋆ ∥ a b C pred 2 t = τ i ∑ τ i + 1 − 1 ∥ Δ τ i z t ∥ 2 . (62)
where the last step uses ∑ i ∥ Π i x t ∥ 2 = Tr ( Π i ⊤ Π i X i ) ≥ a τ 0 ∥ Π i ∥ F 2 \sum_i \|\Pi_i x_t\|^2 = \operatorname{Tr}(\Pi_i^\top\Pi_i X_i) \ge a\tau_0\|\Pi_i\|_F^2 ∑ i ∥ Π i x t ∥ 2 = Tr ( Π i ⊤ Π i X i ) ≥ a τ 0 ∥ Π i ∥ F 2 on this block. For every epoch, the confidence bound implies
∥ Δ τ i z t ∥ 2 ≤ ∥ Δ τ i V τ i 1 / 2 ∥ F 2 ∥ z t ∥ V τ i − 1 2 ≤ b 0 ∥ z t ∥ V τ i − 1 2 . \|\Delta_{\tau_i}z_t\|^2 \le\|\Delta_{\tau_i}V_{\tau_i}^{1/2}\|_F^2\|z_t\|_{V_{\tau_i}^{-1}}^2 \le b_0\|z_t\|_{V_{\tau_i}^{-1}}^2. ∥ Δ τ i z t ∥ 2 ≤ ∥ Δ τ i V τ i 1/2 ∥ F 2 ∥ z t ∥ V τ i − 1 2 ≤ b 0 ∥ z t ∥ V τ i − 1 2 .
Moreover, {(58)} and Lemma 19 give
Z i = [ I ; K τ i ] X i [ I ; K τ i ] ⊤ ⪯ b τ 0 ( 1 + κ 0 2 ) I d , V τ i ⪰ a τ 0 1 + κ 0 2 I d . Z_i = [I;K_{\tau_i}]X_i[I;K_{\tau_i}]^\top\preceq b\tau_0(1+\kappa_0^2)I_d,\qquad V_{\tau_i} \succeq\frac{a\tau_0}{1+\kappa_0^2}I_d. Z i = [ I ; K τ i ] X i [ I ; K τ i ] ⊤ ⪯ b τ 0 ( 1 + κ 0 2 ) I d , V τ i ⪰ 1 + κ 0 2 a τ 0 I d .
Hence V τ i − 1 / 2 Z i V τ i − 1 / 2 ⪯ c I d V_{\tau_i}^{-1/2}Z_iV_{\tau_i}^{-1/2}\preceq cI_d V τ i − 1/2 Z i V τ i − 1/2 ⪯ c I d . Applying Lemma 17 and then Cassel et al. [5 ] yields
∑ i = 0 N T − 1 ∑ t = τ i τ i + 1 − 1 ∥ z t ∥ V τ i − 1 2 ≤ c log ( 1 + c ) log det V T + 1 det V τ 0 ≤ c log ( 1 + c ) d log ( T + 1 ) . \sum_{i=0}^{N_T-1}\sum_{t=\tau_i}^{\tau_{i+1}-1}\|z_t\|_{V_{\tau_i}^{-1}}^2
\le\frac{c}{\log(1+c)}\log\frac{\det V_{T+1}}{\det V_{\tau_0}}
\le\frac{c}{\log(1+c)}d\log(T+1). i = 0 ∑ N T − 1 t = τ i ∑ τ i + 1 − 1 ∥ z t ∥ V τ i − 1 2 ≤ log ( 1 + c ) c log det V τ 0 det V T + 1 ≤ log ( 1 + c ) c d log ( T + 1 ) .
These bounds prove the full-epoch term. If the last epoch is short, its covariance upper bound and Lemma 11 suffice:
∑ t = τ N T − 1 T D t ≤ ∥ S ⋆ ∥ b τ 0 ∥ K τ N T − 1 − K ⋆ ∥ F 2 ≤ ∥ S ⋆ ∥ b τ 0 C K 2 ε 0 2 . \sum_{t=\tau_{N_T-1}}^T D_t \le\|S_\star\|b\tau_0\|K_{\tau_{N_T-1}}-K_\star\|_F^2 \le\|S_\star\|b\tau_0 C_K^2\varepsilon_0^2. t = τ N T − 1 ∑ T D t ≤ ∥ S ⋆ ∥ b τ 0 ∥ K τ N T − 1 − K ⋆ ∥ F 2 ≤ ∥ S ⋆ ∥ b τ 0 C K 2 ε 0 2 .
Finally, if D ⋆ = 0 D_\star=0 D ⋆ = 0 , exact invariance in Lemma 13 makes every CE loss zero.
Put
R 2 = 1 E s u c c ∑ t = τ 0 T D t , R 3 = ∑ t = 1 τ 0 − 1 D t . R_2=\mathbf{1}_{\mathcal{E}_{\mathrm{succ}}}\sum_{t=\tau_0}^{T}D_t,\qquad R_3=\sum_{t=1}^{\tau_0-1}D_t. R 2 = 1 E succ t = τ 0 ∑ T D t , R 3 = t = 1 ∑ τ 0 − 1 D t .
Lemma 22. Under the assumptions of this section, there are finite constants C f , C w C_f,C_w C f , C w , independent of T T T , such that
E [ R 2 ] ≤ C f ( 1 + x b / T ) , E [ R 3 ] ≤ C w τ 0 . \mathbb{E}[R_2]\le C_f(1+x_b/T),\qquad\mathbb{E}[R_3]\le C_w\tau_0. E [ R 2 ] ≤ C f ( 1 + x b / T ) , E [ R 3 ] ≤ C w τ 0 . Their explicit values are given in {(62)} and {(63)}.
Proof. The argument follows Cassel et al. [5 ] , which do not use a lower bound on R R R . Let τ a b o r t \tau_{\mathrm{abort}} τ abort be the abort time, with τ a b o r t = T + 1 \tau_{\mathrm{abort}}=T+1 τ abort = T + 1 if no abort occurs, F = { τ a b o r t ≤ T } F=\{\tau_{\mathrm{abort}}\le T\} F = { τ abort ≤ T } , W = max s ≤ T ∥ w s ∥ W=\max_{s\le T}\|w_s\| W = max s ≤ T ∥ w s ∥ , and H = max s < τ 0 ∥ η s ∥ H=\max_{s<\tau_0}\|\eta_s\| H = max s < τ 0 ∥ η s ∥ . By Lemma 19 , F ⊆ E i n i t c F\subseteq\mathcal{E}_{\mathrm{init}}^c F ⊆ E init c , so P ( F ) ≤ T − 2 \mathbb{P}(F)\le T^{-2} P ( F ) ≤ T − 2 , and P ( E s u c c c ) ≤ T − 2 \mathbb{P}(\mathcal{E}_{\mathrm{succ}}^c)\le T^{-2} P ( E succ c ) ≤ T − 2 by Lemma 20.
Before abort. For τ 0 ≤ t < τ a b o r t \tau_0\le t<\tau_{\mathrm{abort}} τ 0 ≤ t < τ abort , the checks of Algorithm 1 give ∥ K t ∥ ≤ κ \|K_t\|\le\kappa ∥ K t ∥ ≤ κ and ∥ x t ∥ 2 ≤ x b \|x_t\|^2\le x_b ∥ x t ∥ 2 ≤ x b , hence D t ≤ C p r e x b D_t\le C_{\mathrm{pre}}x_b D t ≤ C pre x b with C p r e = ∥ S ⋆ ∥ ( κ + ∥ K ⋆ ∥ ) 2 C_{\mathrm{pre}}=\|S_\star\|(\kappa+\|K_\star\|)^2 C pre = ∥ S ⋆ ∥ ( κ + ∥ K ⋆ ∥ ) 2 . These terms contribute to E [ R 2 ] \mathbb{E}[R_2] E [ R 2 ] at most T C p r e x b P ( E s u c c c ) ≤ C p r e x b / T TC_{\mathrm{pre}}x_b\mathbb{P}(\mathcal{E}_{\mathrm{succ}}^c)\le C_{\mathrm{pre}}x_b/T T C pre x b P ( E succ c ) ≤ C pre x b / T .
At abort. If τ 0 < τ a b o r t ≤ T \tau_0<\tau_{\mathrm{abort}}\le T τ 0 < τ abort ≤ T , the state at τ a b o r t − 1 \tau_{\mathrm{abort}}-1 τ abort − 1 passed the checks, so ∥ x τ a b o r t ∥ 2 ≤ 2 ϑ 2 ( 1 + κ ) 2 x b + 2 W 2 \|x_{\tau_{\mathrm{abort}}\|^2\le2\vartheta^2(1+\kappa)^2x_b+2W^2} ∥ x τ abort ∥ 2 ≤ 2 ϑ 2 ( 1 + κ ) 2 x b + 2 W 2 . If τ a b o r t = τ 0 \tau_{\mathrm{abort}}=\tau_0 τ abort = τ 0 , Cassel et al. [5 ] gives ∥ x τ 0 ∥ 2 ≤ 2 κ 0 2 γ 0 − 2 ( W 2 + ϑ 2 H 2 ) \|x_{\tau_0}\|^2\le2\kappa_0^2\gamma_0^{-2}(W^2+\vartheta^2H^2) ∥ x τ 0 ∥ 2 ≤ 2 κ 0 2 γ 0 − 2 ( W 2 + ϑ 2 H 2 ) . Applying Cassel et al. [5 ] to these two events, each of probability at most T − 2 T^{-2} T − 2 , and using log ( 3 T 3 ) ≤ 3 log ( 5 T ) \log(3T^3)\le3\log(5T) log ( 3 T 3 ) ≤ 3 log ( 5 T ) and x b ≥ 135 q σ 2 log ( 5 T ) x_b\ge135q\sigma^2\log(5T) x b ≥ 135 q σ 2 log ( 5 T ) , we get E [ 1 F ∥ x τ a b o r t ∥ 2 ] ≤ C a x b / T 2 \mathbb{E}[1_F\|x_{\tau_{\mathrm{abort}}}\|^2]\le C_ax_b/T^2 E [ 1 F ∥ x τ abort ∥ 2 ] ≤ C a x b / T 2 , where
C a = 2 ϑ 2 ( 1 + κ ) 2 + 2 9 ( 1 + κ 0 2 γ 0 − 2 ( 1 + ϑ 2 ) ) . C_a=2\vartheta^2(1+\kappa)^2+\frac{2}{9}(1+\kappa_0^2\gamma_0^{-2}(1+\vartheta^2)). C a = 2 ϑ 2 ( 1 + κ ) 2 + 9 2 ( 1 + κ 0 2 γ 0 − 2 ( 1 + ϑ 2 )) .
After abort. The fallback satisfies ∥ ( A ⋆ + B ⋆ K 0 ) j ∥ ≤ κ 0 ( 1 − γ 0 ) j \|(A_\star+B_\star K_0)^j\|\le\kappa_0(1-\gamma_0)^j ∥ ( A ⋆ + B ⋆ K 0 ) j ∥ ≤ κ 0 ( 1 − γ 0 ) j , and the abort is decided before w τ a b o r t w_{\tau_{\mathrm{abort}}} w τ abort is drawn, so the subsequent noise is independent of { τ a b o r t = s } \{\tau_{\mathrm{abort}}=s\} { τ abort = s } for every s s s . Unrolling the closed loop and summing geometric series gives, with C y = n σ 2 κ 0 2 / γ 0 C_y=n\sigma^2\kappa_0^2/\gamma_0 C y = n σ 2 κ 0 2 / γ 0 ,
E [ 1 F ∑ t = τ a b o r t T ∥ x t ∥ 2 ] ≤ 2 κ 0 2 C a x b γ 0 T 2 + 2 C y T P ( F ) . \mathbb{E}\left[\mathbf{1}_{F}\sum_{t=\tau_{\mathrm{abort}}}^{T}\|x_t\|^2\right]\le\frac{2\kappa_0^2C_ax_b}{\gamma_0T^2}+2C_yT\mathbb{P}(F). E [ 1 F t = τ abort ∑ T ∥ x t ∥ 2 ] ≤ γ 0 T 2 2 κ 0 2 C a x b + 2 C y T P ( F ) .
and D t ≤ ∥ S ⋆ ∥ ∥ K 0 − K ⋆ ∥ 2 ∥ x t ∥ 2 D_t\le\|S_\star\|\|K_0-K_\star\|^2\|x_t\|^2 D t ≤ ∥ S ⋆ ∥∥ K 0 − K ⋆ ∥ 2 ∥ x t ∥ 2 after abort. Combining the three steps proves the bound on E [ R 2 ] \mathbb{E}[R_2] E [ R 2 ] with
C f = C p r e ′ + 2 ∥ S ⋆ ∥ ∥ K 0 − K ⋆ ∥ 2 ( κ 0 2 C a γ 0 + C y ) . (63) C_f=C^{\prime}_{\mathrm{pre}}+2\|S_\star\|\|K_0-K_\star\|^2\left(\frac{\kappa_0^2C_a}{\gamma_0}+C_y\right). \tag*{(63)} C f = C pre ′ + 2∥ S ⋆ ∥∥ K 0 − K ⋆ ∥ 2 ( γ 0 κ 0 2 C a + C y ) . (63)
Warm-up. The effective disturbance w t + B ⋆ η t w_t+B_\star\eta_t w t + B ⋆ η t has covariance σ 2 ( I + B ⋆ B ⋆ ⊤ ) ⪯ ( 1 + ϑ 2 ) σ 2 I \sigma^2(I+B_\star B_\star^\top)\preceq(1+\vartheta^2)\sigma^2I σ 2 ( I + B ⋆ B ⋆ ⊤ ) ⪯ ( 1 + ϑ 2 ) σ 2 I . Hence, as in the proof of Cassel et al. [5 ] , Cassel et al. [5 ] with x 1 = 0 x_1=0 x 1 = 0 , Q ⪰ α 0 I Q\succeq\alpha_0I Q ⪰ α 0 I , R ⪰ 0 R\succeq0 R ⪰ 0 , and J ( K 0 ) ≤ ν 0 J(K_0)\le\nu_0 J ( K 0 ) ≤ ν 0 gives ∑ t < τ 0 E ∥ x t ∥ 2 ≤ ( 1 + ϑ 2 ) ν 0 τ 0 / α 0 \sum_{t<\tau_0}\mathbb{E}\|x_t\|^2\le(1+\vartheta^2)\nu_0\tau_0/\alpha_0 ∑ t < τ 0 E ∥ x t ∥ 2 ≤ ( 1 + ϑ 2 ) ν 0 τ 0 / α 0 . Since u t = K 0 x t + η t u_t=K_0x_t+\eta_t u t = K 0 x t + η t and E ∥ η t ∥ 2 = m σ 2 \mathbb{E}\|\eta_t\|^2=m\sigma^2 E ∥ η t ∥ 2 = m σ 2 , this gives E [ R 3 ] ≤ C w τ 0 \mathbb{E}[R_3]\le C_w\tau_0 E [ R 3 ] ≤ C w τ 0 with
C w = 2 ∥ S ⋆ ∥ ( ∥ K 0 − K ⋆ ∥ 2 ( 1 + ϑ 2 ) ν 0 α 0 + m σ 2 ) . (64) C_w=2\|S_\star\|\left(\|K_0-K_\star\|^2\frac{(1+\vartheta^2)\nu_0}{\alpha_0}+m\sigma^2\right). \tag*{(64)} C w = 2∥ S ⋆ ∥ ( ∥ K 0 − K ⋆ ∥ 2 α 0 ( 1 + ϑ 2 ) ν 0 + m σ 2 ) . (64)
Proof of Theorem 4 . The Gaussian warm-up, the state and gain bounds before abort, and the linear fallback give finite second moments at every finite time, so (15) applies. Since x 1 = 0 x_1=0 x 1 = 0 and its terminal term is nonpositive, splitting the rounds t ≥ τ 0 t\ge\tau_0 t ≥ τ 0 according to E s u c c \mathcal{E}_{\mathrm{succ}} E succ gives
E [ R T ] ≤ E [ 1 E s u c c ∑ t = τ 0 T D t ] + E [ R 2 ] + E [ R 3 ] . \mathbb{E}[R_T]\le\mathbb{E}\left[\mathbf{1}_{\mathcal{E}_{\mathrm{succ}}}\sum_{t=\tau_0}^{T}D_t\right]+\mathbb{E}[R_2]+\mathbb{E}[R_3]. E [ R T ] ≤ E [ 1 E succ t = τ 0 ∑ T D t ] + E [ R 2 ] + E [ R 3 ] .
Using Lemmas 21 and 22 ,
E [ R T ] ≤ ∥ S ⋆ ∥ b a C p r e d 2 b 0 c log ( 1 + c ) d log ( T + 1 ) + 1 { N N T − 1 < τ 0 } ∥ S ⋆ ∥ b τ 0 C K 2 ε 0 2 + C f ( 1 + x b / T ) + C w τ 0 . (65) \mathbb{E}[R_T]\le\|S_\star\|\frac{b}{a}C_{\mathrm{pred}}^2b_0\frac{c}{\log(1+c)}d\log(T+1)+\mathbf{1}_{\{N_{N_T}^{-1}<\tau_0\}}\|S_\star\|b\tau_0C_K^2\varepsilon_0^2+C_f(1+x_b/T)+C_w\tau_0. \tag*{(65)} E [ R T ] ≤ ∥ S ⋆ ∥ a b C pred 2 b 0 log ( 1 + c ) c d log ( T + 1 ) + 1 { N N T − 1 < τ 0 } ∥ S ⋆ ∥ b τ 0 C K 2 ε 0 2 + C f ( 1 + x b / T ) + C w τ 0 . (65)
where a a a , b b b , c c c , C f C_f C f , C w C_w C w are defined in (57), (60) , (63) , and (64) . The constants ε 0 \varepsilon_0 ε 0 , κ \kappa κ , γ \gamma γ , C K C_K C K , C p r e d C_{\mathrm{pred}} C pred , C f C_f C f , and C w C_w C w do not depend on T T T , whereas x b x_b x b and λ \lambda λ are proportional to log ( 5 T ) \log(5T) log ( 5 T ) by (48) , and so are τ 0 \tau_0 τ 0 and b 0 b_0 b 0 up to the rounding in (49) . Since v T ≤ ( n log 9 + 3 ) log ( 5 T ) v_T\le(n\log9+3)\log(5T) v T ≤ ( n log 9 + 3 ) log ( 5 T ) , the constants b b b and c c c , which depend on T T T only through x b / τ 0 x_b/\tau_0 x b / τ 0 and v T / τ 0 v_T/\tau_0 v T / τ 0 , are bounded uniformly in T T T , and so is c / log ( 1 + c ) c/\log(1+c) c / log ( 1 + c ) , which is increasing in c c c . As 1 ≤ log ( T + 1 ) ≤ log ( 5 T ) 1\le\log(T+1)\le\log(5T) 1 ≤ log ( T + 1 ) ≤ log ( 5 T ) , every term of (65) is therefore at most a T T T -independent multiple of log 2 ( 5 T ) \log^2(5T) log 2 ( 5 T ) .
Finally, if T < τ 0 T<\tau_0 T < τ 0 , only warm-up inputs are played up to time T T T . Since D t ≥ 0 D_t\ge0 D t ≥ 0 , (15) and the warm-up step in the proof of Lemma 22 , which does not use T ≥ τ 0 T\ge\tau_0 T ≥ τ 0 , give E [ R T ] ≤ C w τ 0 \mathbb{E}[R_T]\le C_w\tau_0 E [ R T ] ≤ C w τ 0 , which is again at most a T T T -independent multiple of log 2 ( 5 T ) \log^2(5T) log 2 ( 5 T ) .
Proof of the Regret Lower Bound
In the family (9) , take the two alternatives
θ = ν Δ , Δ = 1 2 T − 1 / 4 , ν ∼ Unif { − 1 , 1 } , B ν : = B ν Δ . (66) \theta=\nu\Delta,\qquad\Delta=\frac{1}{2}T^{-1/4},\qquad\nu\sim\operatorname{Unif}\{-1,1\},\qquad B_\nu:=B_{\nu\Delta}. \tag*{(66)} θ = ν Δ , Δ = 2 1 T − 1/4 , ν ∼ Unif { − 1 , 1 } , B ν := B ν Δ . (66)
For T ≥ 10 4 T\ge10^4 T ≥ 1 0 4 both belong to the stated parameter interval. By Yao’s principle [27 ] , as in Cassel et al. [5 ] , Theorem 5 follows from the following bound for deterministic policies under the random sign ν \nu ν .
Theorem 23 (cf. Cassel et al. [5 ] , Theorem 13) For T ≥ 10 4 T\ge10^4 T ≥ 1 0 4 , every deterministic learning algorithm for the alternatives (66) satisfies
E [ R T ] ≥ 3.6 ⋅ 10 − 4 1 + r T − 2.4 , \mathbb{E}[R_T]\ge\frac{3.6\cdot10^{-4}}{1+r}\sqrt{T}-2.4, E [ R T ] ≥ 1 + r 3.6 ⋅ 1 0 − 4 T − 2.4 , where the expectation includes the process noise and the random sign ν \nu ν .
For P = diag ( 1 , p ) P=\operatorname{diag}(1,p) P = diag ( 1 , p ) , one has A T P A = diag ( 0 , 1 / 16 ) A^\mathsf{T}PA=\operatorname{diag}(0,1/16) A T P A = diag ( 0 , 1/16 ) and B ν T P A = [ 0 , ν Δ / 4 ] B_\nu^\mathsf{T}PA=[0,\nu\Delta/4] B ν T P A = [ 0 , ν Δ/4 ] , so the DARE reduces to
p = 17 16 − Δ 2 16 β 2 , β = r + Δ 2 + p , p=\frac{17}{16}-\frac{\Delta^2}{16\beta^2},\qquad\beta=r+\Delta^2+p, p = 16 17 − 16 β 2 Δ 2 , β = r + Δ 2 + p ,
whose unique positive root gives the stabilizing solution, with gains K ν = [ 0 , − ν k ⋆ ] K_\nu=[0,-\nu k_\star] K ν = [ 0 , − ν k ⋆ ] , k ⋆ = Δ / ( 4 β ) k_\star=\Delta/(4\beta) k ⋆ = Δ/ ( 4 β ) , and closed loops L ν = A + B ν K ν L_\nu=A+B_\nu K_\nu L ν = A + B ν K ν with eigenvalues { 0 , − ν k ⋆ } \{0,-\nu k_\star\} { 0 , − ν k ⋆ } . Since P = Q + K ν T R K ν + L ν T P L ν ⪰ I 2 P=Q+K_\nu^\mathsf{T}RK_\nu+L_\nu^\mathsf{T}PL_\nu\succeq I_2 P = Q + K ν T R K ν + L ν T P L ν ⪰ I 2 and Δ ≤ 0.05 \Delta\le0.05 Δ ≤ 0.05 ,
1 ≤ p ≤ 17 16 , 1 + r ≤ β ≤ 1.065 + r , 1\le p\le\frac{17}{16},\qquad1+r\le\beta\le1.065+r, 1 ≤ p ≤ 16 17 , 1 + r ≤ β ≤ 1.065 + r ,
0.23 Δ 1 + r ≤ k ⋆ ≤ 0.25 Δ 1 + r , ∥ L ν ∥ 2 ≤ 0.065. (67) \frac{0.23\Delta}{1+r}\le k_\star\le\frac{0.25\Delta}{1+r},\qquad\lVert L_\nu\rVert^2\le0.065. \tag*{(67)} 1 + r 0.23Δ ≤ k ⋆ ≤ 1 + r 0.25Δ , ∥ L ν ∥ 2 ≤ 0.065. (67)
and Tr ( P ) = 1 + p ≤ 2.0625 \operatorname{Tr}(P)=1+p\le2.0625 Tr ( P ) = 1 + p ≤ 2.0625 , ∥ B ν ∥ 2 = 1 + Δ 2 ≤ 1.01 \lVert B_\nu\rVert^2=1+\Delta^2\le1.01 ∥ B ν ∥ 2 = 1 + Δ 2 ≤ 1.01 .
Lemma 24 (cf. Cassel et al. [5 ] , Lemma 14) Fix ν ∈ { − 1 , 1 } \nu\in\{-1,1\} ν ∈ { − 1 , 1 } and any causal policy, and let E ν \mathbb{E}_\nu E ν denote the expectation conditional on this sign. Then
∑ t = 1 T − 1 E ν [ ( u t − K ν x t ) 2 ] ≤ 1.2 ( E ν [ R T ] + 2.4 ) 1 + r . \sum_{t=1}^{T-1}\mathbb{E}_\nu[(u_t-K_\nu x_t)^2]\le\frac{1.2\left(\mathbb{E}_\nu[R_T]+2.4\right)}{1+r}. t = 1 ∑ T − 1 E ν [( u t − K ν x t ) 2 ] ≤ 1 + r 1.2 ( E ν [ R T ] + 2.4 ) .
Proof. If E ν [ R T ] = ∞ \mathbb{E}_\nu[R_T]=\infty E ν [ R T ] = ∞ , the claim is immediate. Otherwise x t x_t x t , t ≤ T t\le T t ≤ T , and, since B ν B_\nu B ν has full column rank, u t u_t u t , t ≤ T − 1 t\le T-1 t ≤ T − 1 , have finite second moments. Put v t = u t − K ν x t v_t=u_t-K_\nu x_t v t = u t − K ν x t . Applying (15) over the first T − 1 T-1 T − 1 rounds and adding the last stage cost minus J ⋆ = Tr ( P ) J_\star=\operatorname{Tr}(P) J ⋆ = Tr ( P ) gives
E ν [ R T ] = β ∑ t = 1 T − 1 E ν [ v t 2 ] − E ν [ x T T ( P − I 2 ) x T ] + E ν [ r u T 2 ] − Tr ( P ) . (68) \mathbb{E}_\nu[R_T]=\beta\sum_{t=1}^{T-1}\mathbb{E}_\nu[v_t^2]-\mathbb{E}_\nu[x_T^\mathsf{T}(P-I_2)x_T]+\mathbb{E}_\nu[ru_T^2]-\operatorname{Tr}(P). \tag*{(68)} E ν [ R T ] = β t = 1 ∑ T − 1 E ν [ v t 2 ] − E ν [ x T T ( P − I 2 ) x T ] + E ν [ r u T 2 ] − Tr ( P ) . (68)
Unrolling the dynamics, using ∥ L ν j ∥ F 2 ≤ 2 ∥ L ν ∥ 2 j \lVert L_\nu^j\rVert_F^2\le2\lVert L_\nu\rVert^{2j} ∥ L ν j ∥ F 2 ≤ 2 ∥ L ν ∥ 2 j , and applying Cauchy–Schwarz as in Cassel et al. [5 ] , Lemma 32 gives
E ν ∥ x T ∥ 2 ≤ 2 ∥ B ν ∥ 2 1 − ∥ L ν ∥ 2 ∑ t = 1 T − 1 E ν [ v t 2 ] + 4 1 − ∥ L ν ∥ 2 \mathbb{E}_\nu\lVert x_T\rVert^2\le\frac{2\lVert B_\nu\rVert^2}{1-\lVert L_\nu\rVert^2}\sum_{t=1}^{T-1}\mathbb{E}_\nu[v_t^2]+\frac{4}{1-\lVert L_\nu\rVert^2} E ν ∥ x T ∥ 2 ≤ 1 − ∥ L ν ∥ 2 2 ∥ B ν ∥ 2 t = 1 ∑ T − 1 E ν [ v t 2 ] + 1 − ∥ L ν ∥ 2 4
≤ 2.2 ∑ t = 1 T − 1 E ν [ v t 2 ] + 4.4. \le2.2\sum_{t=1}^{T-1}\mathbb{E}_\nu[v_t^2]+4.4. ≤ 2.2 t = 1 ∑ T − 1 E ν [ v t 2 ] + 4.4.
Since 0 ⪯ P − I 2 ⪯ 0.0625 I 2 0 \preceq P-I_{2} \preceq0.0625I_{2} 0 ⪯ P − I 2 ⪯ 0.0625 I 2 , β ≥ 1 + r \beta\ge1+r β ≥ 1 + r , r u T 2 ≥ 0 ru_{T}^{2} \ge0 r u T 2 ≥ 0 , and Tr ( P ) ≤ 2.0625 \operatorname{Tr}(P) \le2.0625 Tr ( P ) ≤ 2.0625 , inserting this in (68) yields
E ν [ R T ] ≥ 0.86 ( 1 + r ) ∑ t = 1 T − 1 E ν [ v t 2 ] − 2.4 , (69) \mathbb{E}_{\nu}[R_{T}] \ge0.86(1+r)\sum_{t=1}^{T-1}\mathbb{E}_{\nu}[v_{t}^{2}]-2.4, \tag*{(69)} E ν [ R T ] ≥ 0.86 ( 1 + r ) t = 1 ∑ T − 1 E ν [ v t 2 ] − 2.4 , (69)
because β − 0.1375 ≥ 0.86 ( 1 + r ) \beta-0.1375 \ge0.86(1+r) β − 0.1375 ≥ 0.86 ( 1 + r ) and 0.275 + 2.0625 ≤ 2.4 0.275+2.0625 \le2.4 0.275 + 2.0625 ≤ 2.4 . In particular E ν [ R T ] ≥ − 2.4 \mathbb{E}_{\nu}[R_{T}] \ge-2.4 E ν [ R T ] ≥ − 2.4 , and rearranging proves the claim since 1 / 0.86 ≤ 1.2 1/0.86 \le1.2 1/0.86 ≤ 1.2 .
Proof of Theorem 23. We proceed similarly to the proof of Cassel et al. [5 ] . Infinite expected cost is immediate, so assume finite cost and, for a contradiction, E [ R T ] < c r T − 2.4 \mathbb{E}[R_{T}] < c_{r}\sqrt{T}-2.4 E [ R T ] < c r T − 2.4 , where c r = 3.6 ⋅ 10 − 4 / ( 1 + r ) c_{r}=3.6\cdot10^{-4}/(1+r) c r = 3.6 ⋅ 1 0 − 4 / ( 1 + r ) . Put v t = u t − K ν x t v_{t}=u_{t}-K_{\nu}x_{t} v t = u t − K ν x t and let P ν \mathbb{P}_{\nu} P ν be the trajectory law through x T − 1 x_{T-1} x T − 1 . As in Cassel et al. [5 ] , the Gaussian KL-divergence chain rule gives KL ( P ν ∥ P − ν ) = 2 Δ 2 ∑ t = 1 T − 2 E ν [ u t 2 ] \operatorname{KL}(\mathbb{P}_{\nu}\Vert\mathbb{P}_{-\nu})=2\Delta^{2}\sum_{t=1}^{T-2}\mathbb{E}_{\nu}[u_{t}^{2}] KL ( P ν ∥ P − ν ) = 2 Δ 2 ∑ t = 1 T − 2 E ν [ u t 2 ] . Pinsker in both directions, followed by averaging over the sign, gives
TV ( P 1 , P − 1 ) 2 ≤ Δ 2 ∑ t = 1 T − 1 E [ u t 2 ] . (70) \operatorname{TV}(\mathbb{P}_{1},\mathbb{P}_{-1})^{2}\le\Delta^{2}\sum_{t=1}^{T-1}\mathbb{E}[u_{t}^{2}]. \tag*{(70)} TV ( P 1 , P − 1 ) 2 ≤ Δ 2 t = 1 ∑ T − 1 E [ u t 2 ] . (70)
Using u t 2 ≤ 2 v t 2 + 2 k ⋆ 2 ∥ x t ∥ 2 u_{t}^{2}\le2v_{t}^{2}+2k_{\star}^{2}\lVert x_{t}\rVert^{2} u t 2 ≤ 2 v t 2 + 2 k ⋆ 2 ∥ x t ∥ 2 , Lemma 24, and the cost bound ∑ t < T E ∥ x t ∥ 2 ≤ E [ R T ] + 2.1 T \sum_{t<T}\mathbb{E}\lVert x_{t}\rVert^{2}\le\mathbb{E}[R_{T}]+2.1T ∑ t < T E ∥ x t ∥ 2 ≤ E [ R T ] + 2.1 T (which holds since r u t 2 ≥ 0 ru_{t}^{2}\ge0 r u t 2 ≥ 0 ), we obtain
TV ( P 1 , P − 1 ) 2 ≤ 2 Δ 2 ( 1.2 ( E [ R T ] + 2.4 ) 1 + r + k ⋆ 2 ( E [ R T ] + 2.1 T ) ) ≤ 1 16 . \operatorname{TV}(\mathbb{P}_{1},\mathbb{P}_{-1})^{2}\le2\Delta^{2}\left(\frac{1.2(\mathbb{E}[R_{T}]+2.4)}{1+r}+k_{\star}^{2}(\mathbb{E}[R_{T}]+2.1T)\right)
\le\frac{1}{16}. TV ( P 1 , P − 1 ) 2 ≤ 2 Δ 2 ( 1 + r 1.2 ( E [ R T ] + 2.4 ) + k ⋆ 2 ( E [ R T ] + 2.1 T ) ) ≤ 16 1 .
where the last inequality holds because, by T ≥ 10 4 T\ge10^{4} T ≥ 1 0 4 , E [ R T ] ≤ c r T \mathbb{E}[R_{T}]\le c_{r}\sqrt{T} E [ R T ] ≤ c r T , and (67) , the first term is at most 0.6 c r / ( 1 + r ) + 1.44 T − 1 / 2 ≤ 0.015 0.6c_{r}/(1+r)+1.44T^{-1/2}\le0.015 0.6 c r / ( 1 + r ) + 1.44 T − 1/2 ≤ 0.015 and the second at most ( c r T − 1 / 2 + 2.1 ) / 128 ≤ 0.017 (c_{r}T^{-1/2}+2.1)/128\le0.017 ( c r T − 1/2 + 2.1 ) /128 ≤ 0.017 .
For each 2 ≤ t < T 2\le t<T 2 ≤ t < T , put A t = { u t x 2 , t ≥ 0 } A_{t}=\{u_{t}x_{2,t}\ge0\} A t = { u t x 2 , t ≥ 0 } and C t = { ∣ x 2 , t ∣ > 2 / 5 } C_{t}=\{\lvert x_{2,t}\rvert>2/5\} C t = {∣ x 2 , t ∣ > 2/5 } . These are events of the same observed trajectory under both signs because the policy is deterministic. Since x 2 , t = u t − 1 + w 2 , t − 1 x_{2,t}=u_{t-1}+w_{2,t-1} x 2 , t = u t − 1 + w 2 , t − 1 under either sign, its conditional Gaussian density is at most ( 2 π ) − 1 / 2 (2\pi)^{-1/2} ( 2 π ) − 1/2 , giving P − 1 ( C t ) ≥ 1 − 4 / ( 5 2 π ) > 2 / 3 \mathbb{P}_{-1}(C_{t})\ge1-4/(5\sqrt{2\pi})>2/3 P − 1 ( C t ) ≥ 1 − 4/ ( 5 2 π ) > 2/3 . On A t ∩ C t A_{t}\cap C_{t} A t ∩ C t under ν = 1 \nu=1 ν = 1 , or A t c ∩ C t A_{t}^{c}\cap C_{t} A t c ∩ C t under ν = − 1 \nu=-1 ν = − 1 , the control has the wrong sign and v t 2 = ( u t + ν k ⋆ x 2 , t ) 2 ≥ 4 k ⋆ 2 / 25 v_{t}^{2}=(u_{t}+\nu k_{\star}x_{2,t})^{2}\ge4k_{\star}^{2}/25 v t 2 = ( u t + ν k ⋆ x 2 , t ) 2 ≥ 4 k ⋆ 2 /25 . Consequently,
E [ v t 2 ] ≥ 2 k ⋆ 2 25 ( P 1 ( A t ∩ C t ) + P − 1 ( A t c ∩ C t ) ) ≥ 2 k ⋆ 2 25 ( P − 1 ( C t ) − TV ( P 1 , P − 1 ) ) ≥ k ⋆ 2 30 . \mathbb{E}[v_{t}^{2}]\ge\frac{2k_{\star}^{2}}{25}\left(\mathbb{P}_{1}(A_{t}\cap C_{t})+\mathbb{P}_{-1}(A_{t}^{c}\cap C_{t})\right)
\ge\frac{2k_{\star}^{2}}{25}\left(\mathbb{P}_{-1}(C_{t})-\operatorname{TV}(\mathbb{P}_{1},\mathbb{P}_{-1})\right)\ge\frac{k_{\star}^{2}}{30}. E [ v t 2 ] ≥ 25 2 k ⋆ 2 ( P 1 ( A t ∩ C t ) + P − 1 ( A t c ∩ C t ) ) ≥ 25 2 k ⋆ 2 ( P − 1 ( C t ) − TV ( P 1 , P − 1 ) ) ≥ 30 k ⋆ 2 .
Summing and averaging (69) over the two signs now gives
E [ R T ] ≥ 0.86 ( 1 + r ) 30 ( T − 2 ) k ⋆ 2 − 2.4 ≥ c r T − 2.4 , \mathbb{E}[R_{T}]\ge\frac{0.86(1+r)}{30}(T-2)k_{\star}^{2}-2.4\ge c_{r}\sqrt{T}-2.4, E [ R T ] ≥ 30 0.86 ( 1 + r ) ( T − 2 ) k ⋆ 2 − 2.4 ≥ c r T − 2.4 ,
by using (67) and that 0.86 ⋅ 0.23 2 ( T − 2 ) / ( 120 T ) ≥ 3.6 ⋅ 10 − 4 T 0.86\cdot0.23^{2}(T-2)/(120\sqrt{T})\ge3.6\cdot10^{-4}\sqrt{T} 0.86 ⋅ 0.2 3 2 ( T − 2 ) / ( 120 T ) ≥ 3.6 ⋅ 1 0 − 4 T for T ≥ 10 4 T\ge10^{4} T ≥ 1 0 4 . This is a contradiction.
Relation to CI. Replacing Δ \Delta Δ by θ \theta θ in the DARE solution above gives K ( θ ) = [ 0 , − k ( θ ) ] K(\theta)=[0,-k(\theta)] K ( θ ) = [ 0 , − k ( θ )] with k ( θ ) = θ / [ 4 ( r + θ 2 + p θ ) ] k(\theta)=\theta/[4(r+\theta^2+p\theta)] k ( θ ) = θ / [ 4 ( r + θ 2 + pθ )] , so k ( 0 ) = 0 k(0)=0 k ( 0 ) = 0 and k ( θ ) ∼ θ / [ 4 ( r + 17 / 16 ) ] k(\theta)\sim\theta/[4(r+17/16)] k ( θ ) ∼ θ / [ 4 ( r + 17/16 )] as θ → 0 \theta\to0 θ → 0 . Under a gain [ 0 , − k ] [0,-k] [ 0 , − k ] with ∣ k ∣ < 1 |k|<1 ∣ k ∣ < 1 , the state obeys x 1 , t + 1 = ( 1 / 4 − θ k ) x 2 , t + w 1 , t x_{1,t+1}=(1/4-\theta k)x_{2,t}+w_{1,t} x 1 , t + 1 = ( 1/4 − θ k ) x 2 , t + w 1 , t and x 2 , t + 1 = − k x 2 , t + w 2 , t x_{2,t+1}=-kx_{2,t}+w_{2,t} x 2 , t + 1 = − k x 2 , t + w 2 , t , so x 2 x_2 x 2 has stationary variance 1 / ( 1 − k 2 ) 1/(1-k^2) 1/ ( 1 − k 2 ) . Since only θ \theta θ is unknown, the derivative of the mean of x t + 1 x_{t+1} x t + 1 with respect to θ \theta θ is ( − k x 2 , t , 0 ) ⊤ (-kx_{2,t},0)^\top ( − k x 2 , t , 0 ) ⊤ , and hence I θ ( K ( θ ) ) = k ( θ ) 2 / ( 1 − k ( θ ) 2 ) I_\theta(K(\theta))=k(\theta)^2/(1-k(\theta)^2) I θ ( K ( θ )) = k ( θ ) 2 / ( 1 − k ( θ ) 2 ) . At θ = 0 \theta=0 θ = 0 , these recursions give J Θ ( 0 ) ( [ 0 , − k ] ) = 1 + ( 17 / 16 + r k 2 ) / ( 1 − k 2 ) = 33 / 16 + ( r + 17 / 16 ) k 2 + O ( k 4 ) J_{\Theta}(0)([0,-k])=1+(17/16+rk^2)/(1-k^2)=33/16+(r+17/16)k^2+O(k^4) J Θ ( 0 ) ([ 0 , − k ]) = 1 + ( 17/16 + r k 2 ) / ( 1 − k 2 ) = 33/16 + ( r + 17/16 ) k 2 + O ( k 4 ) ; with k ( 0 ) = 0 k(0)=0 k ( 0 ) = 0 and k ′ ( 0 ) = 1 / [ 4 ( r + 17 / 16 ) ] k'(0)=1/[4(r+17/16)] k ′ ( 0 ) = 1/ [ 4 ( r + 17/16 )] , this yields H 0 = 2 ( r + 17 / 16 ) k ′ ( 0 ) 2 = 1 / [ 8 ( r + 17 / 16 ) ] > 0 = I 0 H_0=2(r+17/16)k'(0)^2=1/[8(r+17/16)]>0=I_0 H 0 = 2 ( r + 17/16 ) k ′ ( 0 ) 2 = 1/ [ 8 ( r + 17/16 )] > 0 = I 0 . Finally, when θ \theta θ is the true parameter, D ⋆ h = Δ B h K ( θ ) D_\star h=\Delta B_hK(\theta) D ⋆ h = Δ B h K ( θ ) has the single nonzero entry − h k ( θ ) -hk(\theta) − hk ( θ ) , so σ min + ( D ⋆ ) = ∣ k ( θ ) ∣ \sigma_{\min}^{+}(D_\star)=|k(\theta)| σ m i n + ( D ⋆ ) = ∣ k ( θ ) ∣ .