Introduction
The linear quadratic regulator (LQR) asks for the state-feedback gain K K K that minimizes the infinite-horizon average quadratic cost C ( K ) C(K) C ( K ) of a linear plant driven by Gaussian process noise. When the plant is known, the optimal gain K ⋆ K^{\star} K ⋆ follows from a Riccati equation, or from Hewer’s policy iteration [2 ] , which alternates evaluating the current gain (policy evaluation) with choosing the input that minimizes its state-action value (policy improvement). Policy-gradient methods search over gains directly. The cost C ( K ) C(K) C ( K ) is not convex in K K K , but Fazel et al. [3 ] showed that it is gradient dominated, that is, the gap C ( K ) − C ( K ⋆ ) C(K)-C(K^{\star}) C ( K ) − C ( K ⋆ ) is at most a multiple of the squared norm of the gradient. With suitable step sizes, the gradient, natural-gradient and Gauss–Newton iterations therefore converge linearly from any stabilizing gain. The Gauss–Newton step rescales the gradient on the left by the inverse Hessian of the state-action value with respect to the input and on the right by the inverse stationary state covariance, and with step size one half it is Hewer’s step [4 ] .
In adaptive LQR the plant is unknown and the controller improves its gain from closed-loop data, which raises two difficulties. Firstly, the switching between gains that each stabilize the plant can still destabilize the closed loop. The state stays bounded when the gains are uniformly strongly stable and consecutive gains stay close, a property used in [5 ] that we call sequential stability in this paper. A gradient method secures it by taking small steps. Secondly, the data generated by a fixed linear feedback u = K x u=Kx u = K x cannot identify the plant, because several plants produce the same closed loop on the subspace where these data lie [6 ] . The controller must therefore add to its input a probing perturbation, that is, a component that is not a linear function of the state.
Policy-gradient adaptive control (PGAC) [1 ] is a framework of policy-gradient methods for adaptive LQR that addresses both difficulties. At every sample, a PGAC method applies the current gain plus a probing perturbation and then takes one gradient, natural-gradient or Gauss–Newton step on the gain. The indirect form computes this step from a recursive least-squares estimate of the plant, and the direct form computes it from the sample covariance of the data. Computing a step requires solving only Lyapunov equations, whereas recomputing the optimal gain of the changing plant estimate at every sample would require solving a Riccati equation. Zhao et al. [1 ] also cite the robustness of small updates. Zhao et al. [1 ] prove that, if the step size is small and the data have a large enough signal-to-noise ratio, the switching gains keep the closed loop stable and the cost of the gain converges linearly up to a bias that shrinks as this ratio grows. In their analysis the probing matters only through the data it produces, and its cost is not part of the cost that the gain update decreases. The covariance of the probing perturbation is a design parameter, constant and isotropic in the experiments of [1 ] , and both PGAC and the earlier data-enabled policy optimization (DeePO) [7 ] leave its choice to the designer.
This paper studies adaptive LQR through the lens of KL regularization, which is common in reinforcement learning [8 ] and in probabilistic approaches to control [9 ] . A KL-regularized problem minimizes the expected cost plus a penalty equal to a positive regularization weight times the KL divergence of the policy from a reference policy. Two of its properties matter for adaptive LQR. Firstly, when the reference is a Gaussian policy, the optimal policy is also randomized, as for the LQR with an entropy bonus [10 ] , so the problem produces the probing and counts its cost in the objective . Secondly, when the reference is the current policy, the KL penalty keeps the new policy close to it, which gives the small steps that sequential stability needs. Just as PGAC takes one gradient-type step per sample, we take one policy improvement per sample instead of solving the regularized problem. Repeating this policy improvement with the current policy as reference and a fixed regularization weight makes the probing die out, because each repetition adds to the precision (inverse covariance) of the policy. Tempering the reference, that is, raising the density of the current policy to a power α < 1 \alpha< 1 α < 1 and renormalizing, gives a policy improvement that penalizes the KL divergence to the current policy and rewards the entropy [11 , 12 , 13 ] . For the LQR, tempering keeps the policy covariance bounded away from zero when the regularization weight is bounded away from zero. For brevity, we refer to this scheme, in which the policy improvement is repeated against the tempered current policy, as KL-regularized policy iteration (KLPI).
Related work: KLPI applies to adaptive LQR the KL-and entropy-regularized policy iteration of reinforcement learning [11 , 12 ] . This policy iteration is a policy mirror-descent method [12 ] . Without tempering and with a fixed regularization weight, the repeated policy improvement reweights the initial policy exponentially in the summed state-action values of earlier policies, as in POLITEX [14 ] for finite Markov decision processes. The model-free LQR method MFLQ [15 ] instead plays the gain that minimizes its sum of past estimated state-action values and probes with scheduled random inputs. In trajectory optimization, Mahmoudi Filabadi et al. [13 ] regularize the backward pass of differential dynamic programming with an entropy bonus and a KL penalty to the policy of the previous iteration. Over the iterations, their Gaussian policies accumulate the input gradients and Hessians of the local state-action values with geometrically decaying weights, and the authors interpret this accumulation as momentum. Closest to this paper, Szpruch et al. [16 ] probe only through entropy-regularized Gaussian policies when controlling an unknown continuous-time linear-quadratic system over finite-horizon episodes, and one of their algorithms penalizes the KL divergence to the previous episode’s policy. In this paper, every policy improvement evaluates the current gain on a least-squares plant estimate updated at every sample of a single trajectory, and our stability analysis follows that of [1 ] .
Contributions: (i) We show that one policy improvement of the KL-regularized LQR returns a gain update and a probing covariance, and that for suitable references the gain update is PGAC’s Gauss–Newton or natural-gradient step with any step size below a bound (Propositions 1 and 3). (ii) With a known plant and tempering, we prove that the cost of KLPI’s gains converges linearly and that its probing covariance keeps a floor proportional to the regularization weight (Theorem 1). (iii) On an estimated plant, under conditions like those in PGAC’s analysis, we prove that KLPI keeps the closed loop stable and that its cost converges linearly up to a bias (Theorem 2), and that its probing covariance keeps a floor proportional to the regularization weight (Corollary 1). (iv) In simulations at equal probing cost, the shape of KLPI’s probing covariance, which PGAC can adopt, lowers the extra cost caused by suboptimal gains on nearly all tested plants, while KLPI’s use of past iterations in its gain update changes this cost little (Section VI).
Organization: Section II recalls the LQR, its policy-gradient updates and PGAC. Section III introduces the KL-regularized LQR problem and its policy improvement. Section IV introduces KLPI, analyses it when the plant is known and compares it with PGAC’s Gauss–Newton iterations. Section V analyses KLPI on an estimated plant. Section VI compares KLPI and PGAC in simulations, and Section VII concludes.
Notation: ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ is the spectral norm, σ ( ⋅ ) \sigma(\cdot) σ ( ⋅ ) the smallest singular value, λ min \lambda_{\min} λ m i n , λ max \lambda_{\max} λ m a x the extreme eigenvalues of a symmetric matrix, and M ⪰ N M \succeq N M ⪰ N means that M − N M-N M − N is positive semidefinite. N ( m , Ψ ) \mathcal{N}(m,\Psi) N ( m , Ψ ) is the Gaussian distribution with mean m m m and covariance Ψ \Psi Ψ . Capitals X t X_t X t , U t U_t U t , W t W_t W t , Ω t \Omega_t Ω t denote the closed-loop state, input, process noise and probing perturbation, lowercase x x x , u u u denote values, and Z t : = [ U t ; X t ] Z_t := [U_t; X_t] Z t := [ U t ; X t ] . D K L ( μ ′ ∥ μ ) D_{\mathrm{KL}}(\mu'\Vert\mu) D KL ( μ ′ ∥ μ ) is the KL divergence of a distribution μ ′ \mu' μ ′ from a distribution μ \mu μ , and h ( μ ) h(\mu) h ( μ ) is the differential entropy of μ \mu μ . For stationary policies π \pi π and ρ \rho ρ , we write κ ρ π ( x ) : = D K L ( π ( ⋅ ∣ x ) ∥ ρ ( ⋅ ∣ x ) ) \kappa^\pi_\rho(x) := D_{\mathrm{KL}}(\pi(\cdot\mid x)\Vert\rho(\cdot\mid x)) κ ρ π ( x ) := D KL ( π ( ⋅ ∣ x ) ∥ ρ ( ⋅ ∣ x )) for the KL divergence of π \pi π from ρ \rho ρ in the state x x x .
Policy-gradient methods for LQR & PGAC
This section sets up the plant and its cost, then states the policy-gradient updates that PGAC takes and its condition on the data, which Section V also adopts.
Plant and cost: We consider the plant
X t + 1 = A X t + B U t + W t , W t ∼ N ( 0 , Σ W ) , (1) X_{t+1}=AX_t+BU_t+W_t,\qquad W_t\sim\mathcal{N}(0,\Sigma_W), \tag*{(1)} X t + 1 = A X t + B U t + W t , W t ∼ N ( 0 , Σ W ) , (1)
with X t ∈ R n X_t\in\mathbb{R}^n X t ∈ R n , U t ∈ R m U_t\in\mathbb{R}^m U t ∈ R m , a process-noise covariance Σ W ≻ 0 \Sigma_W\succ0 Σ W ≻ 0 , ( W t ) (W_t) ( W t ) independent over time and of the initial state X 0 X_0 X 0 , which has a finite second moment, ( A , B ) (A,B) ( A , B ) controllable, and the stage cost c ( x , u ) : = x T Q x + u T R u c(x,u):=x^\mathsf{T}Qx+u^\mathsf{T}Ru c ( x , u ) := x T Q x + u T R u with Q , R ≻ 0 Q,R\succ0 Q , R ≻ 0 . A stationary policy π \pi π assigns to each state x x x a distribution π ( ⋅ ∣ x ) \pi(\cdot\mid x) π ( ⋅ ∣ x ) of the input, and P \mathbb{P} P denotes the law of the closed loop (1) with U t ∼ π ( ⋅ ∣ X t ) U_t\sim\pi(\cdot\mid X_t) U t ∼ π ( ⋅ ∣ X t ) . Its average cost is
C ( π ) : = lim sup T → ∞ 1 T E P [ ∑ t < T c ( X t , U t ) ] . (2) C(\pi):=\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}_{\mathbb{P}}\left[\sum_{t<T}c(X_t,U_t)\right]. \tag*{(2)} C ( π ) := T → ∞ lim sup T 1 E P [ t < T ∑ c ( X t , U t ) ] . (2)
A gain K K K defines the deterministic policy u = K x u=Kx u = K x and the closed-loop matrix A K : = A + B K A_K:=A+BK A K := A + B K , and S \mathcal{S} S is the set of gains for which A K A_K A K is Schur. Adding a Gaussian probing perturbation of covariance Ψ \Psi Ψ , drawn independently of the past, gives the linear-Gaussian policy N ( K x , Ψ ) \mathcal{N}(Kx,\Psi) N ( K x , Ψ ) .
Matrices of a gain: For K ∈ S K\in\mathcal{S} K ∈ S , the cost matrix P K P_K P K solves P K = Q + K T R K + A K T P K A K P_K=Q+K^\mathsf{T}RK+A_K^\mathsf{T}P_KA_K P K = Q + K T R K + A K T P K A K , the stationary state covariance solves Σ K = Σ W + A K Σ K A K T \Sigma_K=\Sigma_W+A_K\Sigma_KA_K^\mathsf{T} Σ K = Σ W + A K Σ K A K T , so that Σ K ⪰ Σ W \Sigma_K\succeq\Sigma_W Σ K ⪰ Σ W , and C ( K ) = Tr ( P K Σ W ) = Tr ( ( Q + K T R K ) Σ K ) C(K)=\operatorname{Tr}(P_K\Sigma_W)=\operatorname{Tr}((Q+K^\mathsf{T}RK)\Sigma_K) C ( K ) = Tr ( P K Σ W ) = Tr (( Q + K T R K ) Σ K ) . For K ∉ S K\notin\mathcal{S} K ∈ / S , C ( K ) = ∞ C(K)=\infty C ( K ) = ∞ . The state-action value of K K K is the cost of applying u u u once in state x x x and K x Kx K x afterwards, relative to the average cost,
Q K ( x , u ) : = c ( x , u ) − C ( K ) + E X ′ ∼ N ( A x + B u , Σ W ) [ X ′ T P K X ′ ] = u T S K u + 2 u T N K x + x T ( Q + A T P K A ) x , (3) \begin{aligned}
Q_K(x,u):=c(x,u)-C(K)+\mathbb{E}_{X'\sim\mathcal{N}(Ax+Bu,\Sigma_W)}[X'^\mathsf{T}P_KX'] \\
&= u^\mathsf{T}S_Ku+2u^\mathsf{T}N_Kx+x^\mathsf{T}(Q+A^\mathsf{T}P_KA)x, \tag*{(3)}
\end{aligned} Q K ( x , u ) := c ( x , u ) − C ( K ) + E X ′ ∼ N ( A x + B u , Σ W ) [ X ′ T P K X ′ ] = u T S K u + 2 u T N K x + x T ( Q + A T P K A ) x , (3)
with the input Hessian S K : = R + B T P K B S_K:=R+B^\mathsf{T}P_KB S K := R + B T P K B (half the Hessian of Q K Q_K Q K in u u u ) and N K : = B T P K A N_K:=B^\mathsf{T}P_KA N K := B T P K A . Its gradient in u u u at u = K x u=Kx u = K x is $2E_Kx$, with the slope E K : = S K K + N K E_K:=S_KK+N_K E K := S K K + N K , which vanishes exactly at K ⋆ K^\star K ⋆ . We write P ⋆ P^\star P ⋆ , S ⋆ S^\star S ⋆ , Σ ⋆ \Sigma^\star Σ ⋆ , $C^\star for the objects of K ⋆ K^\star K ⋆ , and γ ⋆ : = ∥ Σ ⋆ ∥ / σ ( Σ W ) ≥ 1 \gamma^\star:= \|\Sigma^\star\|/\sigma(\Sigma_W) \ge1 γ ⋆ := ∥ Σ ⋆ ∥/ σ ( Σ W ) ≥ 1 . Since P K ⪰ Q P_K \succeq Q P K ⪰ Q , every input Hessian satisfies S K ⪰ s I S_K \succeq sI S K ⪰ s I with s : = λ min ( R + B T Q B ) s := \lambda_{\min}(R+B^\mathsf{T}QB) s := λ m i n ( R + B T QB ) .
Policy-gradient updates of the gain: The gradient of the cost is ∇ C ( K ) = 2 E K Σ K \nabla C(K)=2E_K\Sigma_K ∇ C ( K ) = 2 E K Σ K [3 ] . With a step size η > 0 \eta>0 η > 0 , the natural-gradient and Gauss–Newton steps of [3 ] are
K − 2 η E K , K − 2 η S K − 1 E K . (4) K-2\eta E_K,\qquad K-2\eta S_K^{-1}E_K. \tag*{(4)} K − 2 η E K , K − 2 η S K − 1 E K . (4)
Both steps of (4) are preconditioned steps K − H − 1 E K K-H^{-1}E_K K − H − 1 E K , in which a symmetric positive definite matrix H H H (the preconditioner) sets the size and direction of the step, with H = 1 2 η I H=\frac{1}{2\eta}I H = 2 η 1 I and H = S K 2 η H=\frac{S_K}{2\eta} H = 2 η S K respectively. For η = 1 2 \eta=\frac{1}{2} η = 2 1 the Gauss–Newton step minimizes (3) over u u u , which is Hewer’s step [2 , 4 ] .
Adaptive loop and PGAC: In the adaptive problem the controller knows Q Q Q , R R R and the state but not ( A , B ) (A,B) ( A , B ) , and it starts from t 0 t_0 t 0 offline samples and a gain K t 0 ∈ S K_{t_0}\in\mathcal{S} K t 0 ∈ S . In what follows, PGAC refers to its indirect form. At time t t t PGAC applies U t = K t X t + Ω t U_t=K_tX_t+\Omega_t U t = K t X t + Ω t with probing perturbation Ω t \Omega_t Ω t , observes X t + 1 X_{t+1} X t + 1 , updates the least-squares estimate Θ ^ t + 1 = [ B ^ t + 1 A ^ t + 1 ] \widehat{\Theta}_{t+1}=[\widehat{B}_{t+1}\ \widehat{A}_{t+1}] Θ t + 1 = [ B t + 1 A t + 1 ] of Θ = [ B A ] \Theta=[B\ A] Θ = [ B A ] , and takes the step (4) with S K t S_{K_t} S K t , E K t E_{K_t} E K t computed on this plant estimate [1 ] . The data enter through Φ t : = 1 t ∑ i < t Z i Z i T \Phi_t:=\frac{1}{t}\sum_{i<t}Z_iZ_i^\mathsf{T} Φ t := t 1 ∑ i < t Z i Z i T and W t : = 1 t ∑ i < t W i Z i T W_t:=\frac{1}{t}\sum_{i<t}W_iZ_i^\mathsf{T} W t := t 1 ∑ i < t W i Z i T , so that Θ ^ t − Θ = W t Φ t − 1 \widehat{\Theta}_t-\Theta=W_t\Phi_t^{-1} Θ t − Θ = W t Φ t − 1 , and PGAC measures how informative they are by the signal-to-noise ratio S N R t : = σ ( Φ t ) / ∥ W t ∥ \mathrm{SNR}_t:=\sigma(\Phi_t)/\|W_t\| SNR t := σ ( Φ t ) /∥ W t ∥ .
Assumption 1 (Invertible data [1 ] ). For all t ≥ t 0 t\ge t_0 t ≥ t 0 , Φ t \Phi_t Φ t is invertible.
Then ∥ Θ ^ t − Θ ∥ ≤ 1 / S N R t \|\widehat{\Theta}_t-\Theta\|\le1/\mathrm{SNR}_t ∥ Θ t − Θ∥ ≤ 1/ SNR t [1 Lemma 1] . Suppose that S N R t \mathrm{SNR}_t SNR t exceeds a constant for all t t t , which we call the data condition, and that the step size is small. For the gradient, natural-gradient and Gauss–Newton steps, [1 Theorems 1, 3 and 4] then state that the gains are sequentially stable, that the state is bounded by a decaying transient plus a multiple of the largest disturbance, and that C ( K t ) − C ⋆ C(K_t)-C^\star C ( K t ) − C ⋆ contracts linearly up to a bias equal to a discounted sum of 1 / S N R i 1/\mathrm{SNR}_i 1/ SNR i over t 0 ≤ i ≤ t t_0\le i\le t t 0 ≤ i ≤ t .
One KL-regularized policy improvement
This section introduces the KL-regularized LQR (P), then computes one policy improvement of (P) and shows that it returns a gain update together with a probing covariance (Proposition 1). It then computes what the probing costs (Proposition 2) and identifies the references for which the gain update is one of PGAC’s steps (Proposition 3).
The regularized problem: Let ρ \rho ρ be a reference policy and τ > 0 \tau>0 τ > 0 a regularization weight. The KL-regularized LQR is
(P) min π J ρ ( π ) , \text{(P)}\quad\min_{\pi} J_\rho(\pi), (P) π min J ρ ( π ) ,
J ρ ( π ) : = lim sup T → ∞ 1 T E π [ ∑ t < T ( c ( X t , U t ) + τ κ ρ π ( X t ) ) ] . (5) J_\rho(\pi):=\limsup_{T\to\infty}\frac{1}{T}\mathbb{E}_{\pi}\left[\sum_{t<T}\left(c(X_t,U_t)+\tau\kappa_\rho^\pi(X_t)\right)\right]. \tag*{(5)} J ρ ( π ) := T → ∞ lim sup T 1 E π [ t < T ∑ ( c ( X t , U t ) + τ κ ρ π ( X t ) ) ] . (5)
over stationary policies π \pi π . When the reference has a positive definite covariance, every deterministic policy has an infinite penalty, so (P) selects a randomized policy. We take Gaussian references of the form ρ ( ⋅ ∣ x ) = N ( K ρ x , Ψ ρ ) \rho(\cdot\mid x)=\mathcal{N}(K_\rho x,\Psi_\rho) ρ ( ⋅ ∣ x ) = N ( K ρ x , Ψ ρ ) with Ψ ρ ≻ 0 \Psi_\rho\succ0 Ψ ρ ≻ 0 , and write D : = τ 2 Ψ ρ − 1 D:=\frac{\tau}{2}\Psi_\rho^{-1} D := 2 τ Ψ ρ − 1 for the scaled precision (inverse covariance) of the reference.
Policy improvement: Policy iteration for (P) first evaluates the current policy π \pi π , which yields a relative state value V π V_\pi V π (defined up to an additive constant) and the state-action value Q π ( x , u ) : = c ( x , u ) + E X ′ ∼ N ( A x + B u , Σ W ) [ V π ( X ′ ) ] Q_\pi(x,u):=c(x,u)+\mathbb{E}_{X'\sim\mathcal{N}(Ax+Bu,\Sigma_W)}[V_\pi(X')] Q π ( x , u ) := c ( x , u ) + E X ′ ∼ N ( A x + B u , Σ W ) [ V π ( X ′ )] . It then improves π \pi π , that is, it replaces π \pi π by
π ′ ( ⋅ ∣ x ) ∈ arg min μ E U ∼ μ [ Q π ( x , U ) ] + τ D K L ( μ ∥ ρ ( ⋅ ∣ x ) ) . (6) \pi'(\cdot\mid x)\in\arg\min_{\mu}\mathbb{E}_{U\sim\mu}[Q_\pi(x,U)]+\tau D_{\mathrm{KL}}(\mu\|\rho(\cdot\mid x)). \tag*{(6)} π ′ ( ⋅ ∣ x ) ∈ arg μ min E U ∼ μ [ Q π ( x , U )] + τ D KL ( μ ∥ ρ ( ⋅ ∣ x )) . (6)
Its minimizer is the reference reweighted by e − Q π ( x , ⋅ ) / τ e^{-Q_\pi(x,\cdot)/\tau} e − Q π ( x , ⋅ ) / τ and normalized (Lemma B.1).
Proposition 1 (Policy improvement). Let K ∈ S K\in\mathcal{S} K ∈ S , Ψ ≻ 0 \Psi\succ0 Ψ ≻ 0 , π = N ( K x , Ψ ) \pi=\mathcal{N}(Kx,\Psi) π = N ( K x , Ψ ) and ρ = N ( K ρ x , Ψ ρ ) \rho=\mathcal{N}(K_\rho x,\Psi_\rho) ρ = N ( K ρ x , Ψ ρ ) with Ψ ρ ≻ 0 \Psi_\rho\succ0 Ψ ρ ≻ 0 . Let P K ρ P_K^\rho P K ρ solve P = Q + K T R K + ( K − K ρ ) T D ( K − K ρ ) + A T P A K P=Q+K^\mathsf{T}RK+(K-K_\rho)^\mathsf{T}D(K-K_\rho)+A^\mathsf{T}P A_K P = Q + K T R K + ( K − K ρ ) T D ( K − K ρ ) + A T P A K , and let S K ρ : = R + B T P K ρ B S_K^\rho:=R+B^\mathsf{T}P_K^\rho B S K ρ := R + B T P K ρ B and E K ρ : = S K ρ K + B T P K ρ A + D ( K − K ρ ) E_K^\rho:=S_K^\rho K+B^\mathsf{T}P_K^\rho A+D(K-K_\rho) E K ρ := S K ρ K + B T P K ρ A + D ( K − K ρ ) . (a) V π ( x ) = x T P K ρ x V_\pi(x)=x^\mathsf{T}P_K^\rho x V π ( x ) = x T P K ρ x and J ρ ( π ) = Tr ( P K ρ Σ W ) + Tr ( S K ρ Ψ ) + τ D K L ( N ( 0 , Ψ ) ∥ N ( 0 , Ψ ρ ) ) J_\rho(\pi)=\operatorname{Tr}(P_K^\rho\Sigma_W)+\operatorname{Tr}(S_K^\rho\Psi)+\tau D_{\mathrm{KL}}(\mathcal{N}(0,\Psi)\|\mathcal{N}(0,\Psi_\rho)) J ρ ( π ) = Tr ( P K ρ Σ W ) + Tr ( S K ρ Ψ ) + τ D KL ( N ( 0 , Ψ ) ∥ N ( 0 , Ψ ρ )) . (b) The policy improvement (6) returns π ′ = N ( K ′ x , Ψ ′ ) \pi'=\mathcal{N}(K'x,\Psi') π ′ = N ( K ′ x , Ψ ′ ) with
K ′ = K − H − 1 E K ρ , Ψ ′ = τ 2 H − 1 , H : = S K ρ + D . (7) K'=K-H^{-1}E_K^\rho,\qquad\Psi'=\frac{\tau}{2}H^{-1},\qquad H:=S_K^\rho+D. \tag*{(7)} K ′ = K − H − 1 E K ρ , Ψ ′ = 2 τ H − 1 , H := S K ρ + D . (7) (c) K ′ ∈ S K'\in\mathcal{S} K ′ ∈ S and J ρ ( π ′ ) ≤ J ρ ( π ) J_\rho(\pi')\le J_\rho(\pi) J ρ ( π ′ ) ≤ J ρ ( π ) . (d) If K ρ = K K_\rho=K K ρ = K , then P K ρ = P K P_K^\rho=P_K P K ρ = P K , Q π = Q K + C ( K ) Q_\pi=Q_K+C(K) Q π = Q K + C ( K ) , and (7) reads
K ′ = K − H − 1 E K , Ψ ′ = τ 2 H − 1 , H : = S K + D , (8) K'=K-H^{-1}E_K,\qquad\Psi'=\frac{\tau}{2}H^{-1},\qquad H:=S_K+D, \tag*{(8)} K ′ = K − H − 1 E K , Ψ ′ = 2 τ H − 1 , H := S K + D , (8) with P K ′ ⪯ P K − E K T H − 1 E K P_{K'}\preceq P_K-E_K^\mathsf{T}H^{-1}E_K P K ′ ⪯ P K − E K T H − 1 E K .
Proof. See Appendix B.
The gain update (7) is Hewer’s step for the LQR whose stage cost c c c is augmented by ( u − K ρ x ) T D ( u − K ρ x ) (u-K_\rho x)^\mathsf{T}D(u-K_\rho x) ( u − K ρ x ) T D ( u − K ρ x ) , a penalty on the distance of the input from the mean of the reference. We call a reference with K ρ = K K_\rho=K K ρ = K , as in Proposition 1(d), centred at K K K . With a centred reference and a fixed regularization weight, the KL penalty pulls the new gain towards the current one, and the pull grows as the reference covariance shrinks.
Proposition 2 (Cost of the probing). For K ∈ S K\in\mathcal{S} K ∈ S and Ψ ≻ 0 \Psi\succ0 Ψ ≻ 0 , the average cost (2) of N ( K x , Ψ ) \mathcal{N}(Kx,\Psi) N ( K x , Ψ ) is C ( K , Ψ ) = C ( K ) + Tr ( S K Ψ ) C(K,\Psi)=C(K)+\operatorname{Tr}(S_K\Psi) C ( K , Ψ ) = C ( K ) + Tr ( S K Ψ ) . For Ψ ≻ 0 \Psi\succ0 Ψ ≻ 0 , Tr ( S K Ψ ) ≥ m ( det S K det Ψ ) 1 / m \operatorname{Tr}(S_K\Psi)\ge m(\det S_K\det\Psi)^{1/m} Tr ( S K Ψ ) ≥ m ( det S K det Ψ ) 1/ m , with equality if and only if Ψ \Psi Ψ is proportional to S K − 1 S_K^{-1} S K − 1 .
Proof. See Appendix B.
Proposition 2 separates two properties of a probing covariance Ψ \Psi Ψ ,
amount Tr ( S K Ψ ) \operatorname{Tr}(S_K\Psi) Tr ( S K Ψ ) , \hspace{1em} shape { λ Ψ : λ > 0 } \{\lambda\Psi:\lambda>0\} { λ Ψ : λ > 0 } . (9)
The amount of Ψ \Psi Ψ is the cost that the probing adds to the average cost at every sample, and the shape of Ψ \Psi Ψ is Ψ \Psi Ψ up to a positive factor. Among covariances with a given determinant, and hence a given entropy of N ( 0 , Ψ ) \mathcal{N}(0,\Psi) N ( 0 , Ψ ) , the amount is smallest for the shape S K − 1 S_K^{-1} S K − 1 . Proposition 3 identifies the centred references for which the gain update is exactly PGAC’s natural-gradient or Gauss–Newton step (4).
Proposition 3 (Correspondence). Let K ∈ S K\in\mathcal{S} K ∈ S and τ > 0 \tau>0 τ > 0 . (i) Every symmetric H ⪰ S K H\succeq S_K H ⪰ S K is the preconditioner (8) of exactly one centred reference, the one with Ψ ρ = τ 2 ( H − S K ) − 1 \Psi_\rho=\frac{\tau}{2}(H-S_K)^{-1} Ψ ρ = 2 τ ( H − S K ) − 1 .
(ii) The Gauss–Newton step with 0 < η < 1 2 0 < \eta< \frac{1}{2} 0 < η < 2 1 is the gain update of the policy improvement against N ( K x , η τ 1 − 2 η S K − 1 ) \mathcal{N}(Kx,\frac{\eta\tau}{1-2\eta}S_K^{-1}) N ( K x , 1 − 2 η η τ S K − 1 ) , whose probing covariance is Ψ ′ = η τ S K − 1 \Psi'=\eta\tau S_K^{-1} Ψ ′ = η τ S K − 1 .
(iii) The natural-gradient step with 0 < η < 1 2 λ max ( S K ) 0 < \eta< \frac{1}{2\lambda_{\max}(S_K)} 0 < η < 2 λ m a x ( S K ) 1 is the gain update of the policy improvement against the reference N ( K x , τ ( η − 1 I − 2 S K ) − 1 ) \mathcal{N}(Kx,\tau(\eta^{-1}I-2S_K)^{-1}) N ( K x , τ ( η − 1 I − 2 S K ) − 1 ) , whose probing covariance is Ψ ′ = η τ I \Psi'=\eta\tau I Ψ ′ = η τ I .
(iv) Hewer’s step is the limit of (8) as D → 0 D\to0 D → 0 , that is, as the reference covariance grows without bound. If E K ≠ 0 E_K\ne0 E K = 0 , no Gaussian reference centred at K K K gives the Gauss–Newton step with η ≥ 1 2 \eta\ge\frac{1}{2} η ≥ 2 1 .
Proof. See Appendix B.
Thus PGAC’s natural-gradient step with η < 1 2 λ max ( S K t ) \eta<\frac{1}{2\lambda_{\max}(S_{K_t})} η < 2 λ m a x ( S K t ) 1 , followed by an isotropic probing perturbation of variance σ 2 \sigma^2 σ 2 , is the policy improvement against the centred reference of Proposition 3(iii) with τ = σ 2 / η \tau=\sigma^2/\eta τ = σ 2 / η . When E K E_K E K has full row rank, PGAC’s Gauss–Newton step with its probing perturbation is a policy improvement only if the probing covariance is η τ S K − 1 \eta\tau S_K^{-1} η τ S K − 1 , and constant isotropic probing has this form only when S K S_K S K is a multiple of the identity.
KL-regularized policy iteration with a tempered reference
This section introduces KLPI. We first show that, when the plant is known and the regularization weight is constant, no iteration of KLPI increases a fixed objective. We then prove that the cost of its gains converges, and finally compare KLPI with PGAC.
The tempered reference: Taking the current policy itself as the next reference makes the probing die out (Theorem 1(b)), and tempering the policy first prevents this. To temper a Gaussian policy, we raise its density to a power α t > 0 \alpha_t>0 α t > 0 and normalize it, which keeps the mean and divides the covariance by α t \alpha_t α t . For π t = N ( K t x , Ψ t ) \pi_t=\mathcal{N}(K_tx,\Psi_t) π t = N ( K t x , Ψ t ) , the tempered reference ρ t ∝ π t α t \rho_t\propto\pi_t^{\alpha_t} ρ t ∝ π t α t is therefore N ( K t x , Ψ t / α t ) \mathcal{N}(K_tx,\Psi_t/\alpha_t) N ( K t x , Ψ t / α t ) , which is centred at K t K_t K t , so Proposition 1(d) applies.
Proposition 4 (One iteration of KLPI). Let α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] , τ t > 0 \tau_t>0 τ t > 0 , π t = N ( K t x , Ψ t ) \pi_t=\mathcal{N}(K_tx,\Psi_t) π t = N ( K t x , Ψ t ) with Ψ t = τ t 2 H t − 1 \Psi_t=\frac{\tau_t}{2}H_t^{-1} Ψ t = 2 τ t H t − 1 , H t ≻ 0 H_t\succ0 H t ≻ 0 , and let S S S , E E E be the input Hessian and slope of K t K_t K t on a model that K t K_t K t stabilizes. The policy improvement with regularization weight τ t + 1 \tau_{t+1} τ t + 1 against ρ t ∝ π t α t \rho_t\propto\pi_t^{\alpha_t} ρ t ∝ π t α t , α t : = α τ t / τ t + 1 \alpha_t:=\alpha\tau_t/\tau_{t+1} α t := α τ t / τ t + 1 , is π t + 1 = N ( K t + 1 x , Ψ t + 1 ) \pi_{t+1}=\mathcal{N}(K_{t+1}x,\Psi_{t+1}) π t + 1 = N ( K t + 1 x , Ψ t + 1 ) with
H t + 1 = α H t + S , K t + 1 = K t − H t + 1 − 1 E , H_{t+1}=\alpha H_t+S,\qquad K_{t+1}=K_t-H_{t+1}^{-1}E, H t + 1 = α H t + S , K t + 1 = K t − H t + 1 − 1 E , Ψ t + 1 = τ t + 1 2 H t + 1 − 1 . (9) \Psi_{t+1}=\frac{\tau_{t+1}}{2}H_{t+1}^{-1}. \tag*{(9)} Ψ t + 1 = 2 τ t + 1 H t + 1 − 1 . (9)
Proof. The reference ρ t = N ( K t x , Ψ t / α t ) \rho_t=\mathcal{N}(K_tx,\Psi_t/\alpha_t) ρ t = N ( K t x , Ψ t / α t ) has the scaled precision D = τ t + 1 2 α t Ψ t − 1 = α H t D=\frac{\tau_{t+1}}{2}\alpha_t\Psi_t^{-1}=\alpha H_t D = 2 τ t + 1 α t Ψ t − 1 = α H t , and Proposition 1(d), applied to the model on which S S S and E E E are computed, gives (10).
With α = 1 \alpha=1 α = 1 and a constant regularization weight, α t = 1 \alpha_t=1 α t = 1 , so the reference is the current policy itself, and we call this case untempered. The regularization weight does not enter the recursion of ( K t , H t ) (K_t,H_t) ( K t , H t ) . It only converts H t H_t H t into the probing covariance. Unrolling the recursion gives ( 1 − α ) H t + 1 = ∑ k ≤ t ( 1 − α ) α t − k S K k + α t + 1 ( 1 − α ) H 0 = : S ˉ t (1-\alpha)H_{t+1}=\sum_{k\le t}(1-\alpha)\alpha^{t-k}S_{K_k}+\alpha^{t+1}(1-\alpha)H_0=:\bar S_t ( 1 − α ) H t + 1 = ∑ k ≤ t ( 1 − α ) α t − k S K k + α t + 1 ( 1 − α ) H 0 =: S ˉ t , which for α < 1 \alpha<1 α < 1 is a weighted average of the past input Hessians and, of ( 1 − α ) H 0 (1-\alpha)H_0 ( 1 − α ) H 0 . The gain update K t + 1 = K t − ( 1 − α ) S ˉ t + 1 − 1 E K_{t+1}=K_t-(1-\alpha)\bar S_{t+1}^{-1}E K t + 1 = K t − ( 1 − α ) S ˉ t + 1 − 1 E is thus a Gauss–Newton step with step size η = 1 − α 2 \eta=\frac{1-\alpha}{2} η = 2 1 − α and an averaged input Hessian.
A fixed objective: Because the reference changes at every iteration, each policy improvement decreases a different regularized objective. With a known plant and a constant regularization weight τ \tau τ , KLPI nevertheless does not increase one fixed objective, defined for π = N ( K x , Ψ ) \pi=\mathcal{N}(Kx,\Psi) π = N ( K x , Ψ ) with K ∈ S K\in\mathcal{S} K ∈ S , Ψ ≻ 0 a n d \Psi\succ0 and Ψ ≻ 0 an d \vartheta:=(1-\alpha)\tau$ as
J ϑ ( π ) : = C ( K , Ψ ) − ϑ h ( N ( 0 , Ψ ) ) , (10) \mathcal{J}_{\vartheta}(\pi):=\mathcal{C}(K,\Psi)-\vartheta h(\mathcal{N}(0,\Psi)), \tag*{(10)} J ϑ ( π ) := C ( K , Ψ ) − ϑ h ( N ( 0 , Ψ )) , (10)
the average cost minus ϑ \vartheta ϑ times the entropy of the probing, since every iteration is a generalized majorization–minimization step [17 ] (Lemma B.2). For ϑ > 0 \vartheta>0 ϑ > 0 , the unique minimizer of J ϑ \mathcal{J}_{\vartheta} J ϑ among these policies is N ( K ∗ x , ϑ 2 ( S ∗ ) − 1 ) \mathcal{N}(K^*x,\frac{\vartheta}{2}(S^*)^{-1}) N ( K ∗ x , 2 ϑ ( S ∗ ) − 1 ) , so the entropy term changes only its covariance. This descent gives no rate, and Theorem 1 derives one from the gain step of (10), indexing iterations by g g g .
Theorem 1 (Known plant). Let K 0 ∈ S K_0\in\mathcal{S} K 0 ∈ S , H 0 ≻ 0 H_0\succ0 H 0 ≻ 0 , α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] , and iterate (10) with S = S K g S=S_{K_g} S = S K g , E = E K g E=E_{K_g} E = E K g , for any regularization weights τ g > 0 \tau_g>0 τ g > 0 , and let Ψ g : = τ g 2 H g − 1 \Psi_g:=\frac{\tau_g}{2}H_g^{-1} Ψ g := 2 τ g H g − 1 for all g ≥ 0 g\ge0 g ≥ 0 . Let S ˉ : = ∥ R ∥ + ∥ B ∥ 2 ∥ C ( K 0 ) ∥ 2 / σ min ( Σ W ) \bar S:=\|R\|+\|B\|^2\|C(K_0)\|_2/\sigma_{\min}(\Sigma_W) S ˉ := ∥ R ∥ + ∥ B ∥ 2 ∥ C ( K 0 ) ∥ 2 / σ m i n ( Σ W ) . Then every K g ∈ S K_g\in\mathcal{S} K g ∈ S and P K g + 1 ⪯ P K g − E K g T H g + 1 − 1 E K g P_{K_{g+1}}\preceq P_{K_g}-E_{K_g}^{\mathsf T}H_{g+1}^{-1}E_{K_g} P K g + 1 ⪯ P K g − E K g T H g + 1 − 1 E K g . (a) If α < 1 \alpha<1 α < 1 , then C ( K g ) − C ∗ ≤ ( 1 − θ α ) g ( C ( K 0 ) − C ∗ ) \mathcal{C}(K_g)-C^*\le(1-\theta_\alpha)^g(\mathcal{C}(K_0)-C^*) C ( K g ) − C ∗ ≤ ( 1 − θ α ) g ( C ( K 0 ) − C ∗ ) with θ α : = ( 1 − α ) s ˉ ( 1 − α ) ∥ H 0 ∥ + s ˉ γ ∗ ∈ ( 0 , 1 ] \theta_\alpha:=\frac{(1-\alpha)\bar s}{(1-\alpha)\|H_0\|+\bar s\gamma^*}\in(0,1] θ α := ( 1 − α ) ∥ H 0 ∥ + s ˉ γ ∗ ( 1 − α ) s ˉ ∈ ( 0 , 1 ] , Ψ g ≥ τ g 2 ( ∥ H 0 ∥ + s ˉ 1 − α ) − 1 I \Psi_g\ge\frac{\tau_g}{2}(\|H_0\|+\frac{\bar s}{1-\alpha})^{-1}I Ψ g ≥ 2 τ g ( ∥ H 0 ∥ + 1 − α s ˉ ) − 1 I , K g → K ∗ K_g\to K^* K g → K ∗ and H g → S ∗ 1 − α H_g\to\frac{S^*}{1-\alpha} H g → 1 − α S ∗ , so that for a constant regularization weight Ψ g → ( 1 − α ) τ 2 ( S ∗ ) − 1 \Psi_g\to\frac{(1-\alpha)\tau}{2}(S^*)^{-1} Ψ g → 2 ( 1 − α ) τ ( S ∗ ) − 1 . (b) If α = 1 \alpha=1 α = 1 , then C ( K g ) − C ∗ ≤ ( c 1 1 + g ( C ( K 0 ) − C ∗ ) ) \mathcal{C}(K_g)-C^*\le\left(\frac{c_1}{1+g}(\mathcal{C}(K_0)-C^*)\right) C ( K g ) − C ∗ ≤ ( 1 + g c 1 ( C ( K 0 ) − C ∗ ) ) with c 1 : = 1 + ∥ H 0 ∥ s ˉ c_1:=1+\frac{\|H_0\|}{\bar s} c 1 := 1 + s ˉ ∥ H 0 ∥ , c 2 : = s ˉ s ˉ γ ∗ c_2:=\frac{\bar s}{\bar s\gamma^*} c 2 := s ˉ γ ∗ s ˉ , and τ g 2 ( λ min ( H 0 ) + g λ min ( R ) ) I ⪯ Ψ g ⪯ τ g 2 ( ∥ H 0 ∥ + g s ˉ ) I \frac{\tau_g}{2(\lambda_{\min}(H_0)+g\lambda_{\min}(R))}I\preceq\Psi_g\preceq\frac{\tau_g}{2(\|H_0\|+g\bar s)}I 2 ( λ m i n ( H 0 ) + g λ m i n ( R )) τ g I ⪯ Ψ g ⪯ 2 ( ∥ H 0 ∥ + g s ˉ ) τ g I .
Proof. See Appendix C. The proof combines the Loewner-order descent lemma (Lemma A.3) and its consequence for the cost (Lemma A.4) with the bound H g + 1 ⪰ S K g H_{g+1}\succeq S_{K_g} H g + 1 ⪰ S K g .
Theorem 1(b) shows the collapse that tempering prevents. Without tempering, the probing covariance decays like 1 / g 1/g 1/ g when the regularization weights are bounded above and away from zero. For α < 1 \alpha<1 α < 1 , the covariance keeps a floor proportional to τ g \tau_g τ g , and for a constant regularization weight it tends to ( 1 − α ) τ 2 ( S ∗ ) − 1 \frac{(1-\alpha)\tau}{2}(S^*)^{-1} 2 ( 1 − α ) τ ( S ∗ ) − 1 , the covariance of the minimizer of J ϑ \mathcal{J}_{\vartheta} J ϑ , which adds m ( 1 − α ) τ 2 \frac{m(1-\alpha)\tau}{2} 2 m ( 1 − α ) τ to the average cost (Proposition 2).
Single steps against whole iterations: Proposition 3 matches one step of KLPI with one step of PGAC, but over many iterations the two methods form their preconditioners and probing covariances differently. PGAC recomputes its preconditioner H H H from the current gain alone, and the designer chooses its step size and probing covariance. KLPI takes D = α H t D=\alpha H_t D = α H t from the policy it has just produced, so for α < 1 \alpha<1 α < 1 its preconditioner remembers past input Hessians with geometrically decaying factors. The same geometric averaging appears for state-action values in [12 ] and, read as momentum, in the policy updates of [13 ] . KLPI’s probing covariance follows from a chosen regularization weight. KLPI reproduces PGAC’s Gauss–Newton iterates if α H t = 1 − 2 η 2 η S K t \alpha H_t=\frac{1-2\eta}{2\eta}S_{K_t} α H t = 2 η 1 − 2 η S K t at every t t t , and only if this equality holds at every iteration at which E K t E_{K_t} E K t has full row rank.
Algorithm 1 KLPI on the estimated plant
Input: offline data with Φ t 0 ≻ 0 \Phi_{t_0} \succ0 Φ t 0 ≻ 0 and plant estimate Θ ^ t 0 \hat{\Theta}_{t_0} Θ ^ t 0 ; gain K t 0 ∈ S K_{t_0} \in\mathcal{S} K t 0 ∈ S
Parameters: H t 0 ≻ 0 H_{t_0} \succ0 H t 0 ≻ 0 ; α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] ; regularization weights τ t > 0 \tau_t > 0 τ t > 0
for t = t 0 , t 0 + 1 , … t=t_0,t_0+1,\ldots t = t 0 , t 0 + 1 , … do
Ψ t ← τ t 2 H t − 1 \Psi_t \gets\frac{\tau_t}{2}H_t^{-1} Ψ t ← 2 τ t H t − 1 ; draw Ω t ∼ N ( 0 , Ψ t ) \Omega_t \sim\mathcal{N}(0,\Psi_t) Ω t ∼ N ( 0 , Ψ t )
apply U t = K t X t + Ω t U_t=K_tX_t+\Omega_t U t = K t X t + Ω t and observe X t + 1 X_{t+1} X t + 1
update Θ ^ t + 1 \hat{\Theta}_{t+1} Θ ^ t + 1 by recursive least squares
S ^ t , E ^ t ← \hat{S}_t,\hat{E}_t \gets S ^ t , E ^ t ← input Hessian and slope of K t K_t K t on ( A ^ t + 1 , B ^ t + 1 ) (\hat{A}_{t+1},\hat{B}_{t+1}) ( A ^ t + 1 , B ^ t + 1 )
H t + 1 ← α H t + S ^ t H_{t+1} \gets\alpha H_t+\hat{S}_t H t + 1 ← α H t + S ^ t
K t + 1 ← K t − H t + 1 − 1 E ^ t K_{t+1} \gets K_t-H_{t+1}^{-1}\hat{E}_t K t + 1 ← K t − H t + 1 − 1 E ^ t
The adaptive loop
This section applies KLPI in the adaptive loop, with one iteration per sample in which the plant estimate replaces the plant in the policy evaluation. Under the data condition and with small updates (α \alpha α close to one), we prove a guarantee like PGAC’s, i.e., the switching closed loop is stable and the cost converges linearly up to a bias, and we show that the probing covariance keeps a floor proportional to the regularization weight.
Algorithm 1 applies (10) once per sample and needs the same computation per sample as PGAC’s Gauss–Newton step. It differs from that step in two ways. Its preconditioner H t + 1 H_{t+1} H t + 1 accumulates the estimated input Hessians of past samples instead of using the current one alone, and the tempering exponent α \alpha α of Section IV acts in this sum as a forgetting factor. Its probing covariance τ t 2 H t − 1 \frac{\tau_t}{2}H_t^{-1} 2 τ t H t − 1 follows from this preconditioner and the regularization weight, instead of being chosen separately.
Theorem 2 (Adaptive loop). Let Assumption 1 hold, K t 0 ∈ S K_{t_0} \in\mathcal{S} K t 0 ∈ S and α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . There are constants ν 1 , … , ν 5 > 0 \nu_1,\ldots,\nu_5>0 ν 1 , … , ν 5 > 0 with ν 3 ≥ 1 ≥ ν 4 \nu_3 \ge1 \ge\nu_4 ν 3 ≥ 1 ≥ ν 4 and s ˉ a ≥ ∥ R ∥ + ∥ B ∥ 2 ( C ( K t 0 ) + 2 ) / σ ( Σ W ) \bar{s}_a \ge\lVert R\rVert+\lVert B\rVert^2(C(K_{t_0})+2)/\sigma(\Sigma_W) s ˉ a ≥ ∥ R ∥ + ∥ B ∥ 2 ( C ( K t 0 ) + 2 ) / σ ( Σ W ) , depending only on ( A , B , Q , R , Σ W , C ( K t 0 ) ) (A,B,Q,R,\Sigma_W,C(K_{t_0})) ( A , B , Q , R , Σ W , C ( K t 0 )) , such that, if
(C1) 1 − α ≤ ν 2 1-\alpha\le\nu_2 1 − α ≤ ν 2 ,
(C2) S N R t ≥ ν 1 \mathrm{SNR}_t \ge\nu_1 SNR t ≥ ν 1 for all t ≥ t 0 t \ge t_0 t ≥ t 0 , and
(C3) s 2 ( 1 − α ) I ⪯ H t 0 ⪯ s ˉ a 1 − α I \frac{s}{2(1-\alpha)}I \preceq H_{t_0} \preceq\frac{\bar{s}_a}{1-\alpha}I 2 ( 1 − α ) s I ⪯ H t 0 ⪯ 1 − α s ˉ a I ,
then, for all regularization weights τ t > 0 \tau_t>0 τ t > 0 , the estimated input Hessians and slopes S ^ t , E ^ t \hat{S}_t,\hat{E}_t S ^ t , E ^ t of Algorithm 1 are well defined at every sample, the gains K t K_t K t are sequentially stable,
∥ X t ∥ ≤ ν 3 ( 1 − ν 4 2 ) t − t 0 ∥ X t 0 ∥ + 2 ν 3 ν 4 max t 0 ≤ i < t ∥ B Ω i + W i ∥ , (11) \lVert X_t\rVert\le\nu_3\left(1-\frac{\nu_4}{2}\right)^{t-t_0}\lVert X_{t_0}\rVert+\frac{2\nu_3}{\nu_4}\max_{t_0\le i<t}\lVert B\Omega_i+W_i\rVert, \tag*{(11)} ∥ X t ∥ ≤ ν 3 ( 1 − 2 ν 4 ) t − t 0 ∥ X t 0 ∥ + ν 4 2 ν 3 t 0 ≤ i < t max ∥ B Ω i + W i ∥ , (11) and, with q α : = 1 − ( 1 − α ) s 2 s ˉ a γ ⋆ q_\alpha:=1-\frac{(1-\alpha)s}{2\bar{s}_a\gamma^\star} q α := 1 − 2 s ˉ a γ ⋆ ( 1 − α ) s ,
C ( K t ) − C ⋆ ≤ q α t − t 0 ( C ( K t 0 ) − C ⋆ ) + ( 1 − α ) ν 5 ∑ i = t 0 + 1 t q α t − i S N R i − 1 . (12) C(K_t)-C^\star\le q_\alpha^{t-t_0}\bigl(C(K_{t_0})-C^\star\bigr)+(1-\alpha)\nu_5\sum_{i=t_0+1}^{t}q_\alpha^{t-i}\mathrm{SNR}_i^{-1}. \tag*{(12)} C ( K t ) − C ⋆ ≤ q α t − t 0 ( C ( K t 0 ) − C ⋆ ) + ( 1 − α ) ν 5 i = t 0 + 1 ∑ t q α t − i SNR i − 1 . (12) Under (C2), (C3) holds for H t 0 = S ^ o f f 1 − α H_{t_0}=\frac{\hat{S}_{\mathrm{off}}}{1-\alpha} H t 0 = 1 − α S ^ off , where S ^ o f f \hat{S}_{\mathrm{off}} S ^ off is the input Hessian of K t 0 K_{t_0} K t 0 on Θ ^ t 0 \hat{\Theta}_{t_0} Θ ^ t 0 .
Proof. See Appendix D. The proof follows the proofs of [1 Theorems 1 and 3] . It compares the computed update with the exact update that uses the true slope, and bounds their difference by a multiple of 1 / S N R t + 1 1/\mathrm{SNR}_{t+1} 1/ SNR t + 1 , where S N R t + 1 \mathrm{SNR}_{t+1} SNR t + 1 measures the data behind the plant estimate Θ ^ t + 1 \hat{\Theta}_{t+1} Θ ^ t + 1 . Two ingredients are new: a Loewner-order descent lemma for matrix preconditioners (Lemma A.3), and an induction that keeps H t H_t H t in the band of (C3).
Condition (C1) is the counterpart of PGAC’s small step size, and the probing enters only through (C2) and B Ω i B\Omega_i B Ω i in (12). Appendix D gives every constant of Theorem 2 in closed form, except a supremum of the slope norm ∥ E K ∥ \lVert E_K\rVert ∥ E K ∥ inside ν 2 \nu_2 ν 2 .
Corollary 1 (Probing in the adaptive loop). Under the conditions of Theorem 2, for all t ≥ t 0 t \ge t_0 t ≥ t 0 , the probing covariance Ψ t = τ t 2 H t − 1 \Psi_t=\frac{\tau_t}{2}H_t^{-1} Ψ t = 2 τ t H t − 1 of Algorithm 1 satisfies
( 1 − α ) τ t 2 s ˉ a I ⪯ Ψ t ⪯ ( 1 − α ) τ t s I . (13) \frac{(1-\alpha)\tau_t}{2\bar{s}_a}I \preceq\Psi_t \preceq\frac{(1-\alpha)\tau_t}{s}I. \tag*{(13)} 2 s ˉ a ( 1 − α ) τ t I ⪯ Ψ t ⪯ s ( 1 − α ) τ t I . (13)
Proof. Starting from (C3), the induction of Appendix D applies Lemma D.2(i) at every t ≥ t 0 t \ge t_0 t ≥ t 0 and so keeps H t H_t H t in the band of (C3). Inverting this band gives (14). □ \square □
Hence, as on a known plant (Theorem 1(a)), the probing does not die out in the adaptive loop when the regularization weights are bounded away from zero. We leave open whether this floor on the probing covariance implies the data condition (C2).
Comparing KLPI and PGAC in Simulation
This section compares in simulation the two design choices in which KLPI differs from PGAC’s Gauss–Newton step. The first is the probing shape (9), since KLPI probes with a covariance proportional to the inverse of its preconditioner. The second is the averaging of past estimated input Hessians in this preconditioner. We define the compared quantity (Section VI-A), describe the simulation setup (Section VI-B), and report the effect of each choice (Sections VI-C and VI-D).
The Compared Quantity
This subsection defines the ratio we compare, from a split of the regret, and the input directions along which probing shapes differ.
Regret and its parts: We measure each method by its regret over T T T samples,
Reg T : = E P [ ∑ t < T c ( X t , U t ) ] − T C ⋆ , (14) \operatorname{Reg}_T:=\mathbb{E}_{\mathbb{P}}\left[\sum_{t<T}c(X_t,U_t)\right]-TC^\star, \tag*{(14)} Reg T := E P [ t < T ∑ c ( X t , U t ) ] − T C ⋆ , (14)
where P \mathbb{P} P is the law of the closed loop under the method. For a method that applies U t = K t X t + Ω t U_t=K_tX_t+\Omega_t U t = K t X t + Ω t with Ω t ∼ N ( 0 , Ψ t ) \Omega_t\sim\mathcal{N}(0,\Psi_t) Ω t ∼ N ( 0 , Ψ t ) , we define two costs at each time t t t : the probe cost, P t \mathcal{P}_t P t , and the gain-error cost E t \mathcal{E}_t E t , which is the cost caused by the suboptimal gain K t K_t K t :
P t : = Tr ( S ⋆ Ψ t ) , E t : = X t T ( K t − K ⋆ ) T S ⋆ ( K t − K ⋆ ) X t . (15) \mathcal{P}_t:=\operatorname{Tr}(S^\star\Psi_t),\qquad\mathcal{E}_t:=X_t^\mathsf{T}(K_t-K^\star)^\mathsf{T}S^\star(K_t-K^\star)X_t. \tag*{(15)} P t := Tr ( S ⋆ Ψ t ) , E t := X t T ( K t − K ⋆ ) T S ⋆ ( K t − K ⋆ ) X t . (15)
Proposition 5 splits the regret into a boundary term and the sums of these two costs.
Proposition 5 (Cost split). Let U t = K t X t + Ω t U_t=K_tX_t+\Omega_t U t = K t X t + Ω t , where the gain K t K_t K t and the probing covariance Ψ t \Psi_t Ψ t are functions of the data I t : = ( X 0 , U 0 , … , U t − 1 , X t ) \mathcal{I}_t:=(X_0,U_0,\ldots,U_{t-1},X_t) I t := ( X 0 , U 0 , … , U t − 1 , X t ) observed up to time t t t . Let the probing perturbation Ω t \Omega_t Ω t have the conditional distribution N ( 0 , Ψ t ) \mathcal{N}(0,\Psi_t) N ( 0 , Ψ t ) given I t \mathcal{I}_t I t , and let the process noise W t W_t W t be independent of ( Ω t , I t ) (\Omega_t,\mathcal{I}_t) ( Ω t , I t ) . If, under the closed-loop law P \mathbb{P} P , E P ∥ X t ∥ 2 \mathbb{E}_{\mathbb{P}}\lVert X_t\rVert^2 E P ∥ X t ∥ 2 , E P ∥ K t X t ∥ 2 \mathbb{E}_{\mathbb{P}}\lVert K_tX_t\rVert^2 E P ∥ K t X t ∥ 2 and E P Tr Ψ t \mathbb{E}_{\mathbb{P}}\operatorname{Tr}\Psi_t E P Tr Ψ t are finite for t ≤ T t\le T t ≤ T , then
E P [ ∑ t < T c ( X t , U t ) ] = T C ⋆ + E P [ X 0 T P ⋆ X 0 − X T T P ⋆ X T ] + ∑ t < T E P [ P t ] + ∑ t < T E P [ E t ] . (16) \mathbb{E}_{\mathbb{P}}\left[\sum_{t<T}c(X_t,U_t)\right]=TC^\star+\mathbb{E}_{\mathbb{P}}\left[X_0^\mathsf{T}P^\star X_0-X_T^\mathsf{T}P^\star X_T\right]+\sum_{t<T}\mathbb{E}_{\mathbb{P}}[\mathcal{P}_t]+\sum_{t<T}\mathbb{E}_{\mathbb{P}}[\mathcal{E}_t]. \tag*{(16)} E P [ t < T ∑ c ( X t , U t ) ] = T C ⋆ + E P [ X 0 T P ⋆ X 0 − X T T P ⋆ X T ] + t < T ∑ E P [ P t ] + t < T ∑ E P [ E t ] . (16)
Proof. See Appendix D.
The probing cost P t P_t P t does not depend on the applied gain, so two methods that probe with the same covariance pay the same probing cost.
Equal probing cost: Probing makes the data more informative, so a method that probed more could improve its gains for that reason alone. To make the two methods comparable, we therefore give both the same probing cost at every sample. We fix this common cost through a probing budget c c c per sample, chosen by the designer (Section VI-B). The methods start after t 0 t_0 t 0 offline samples (Section VI-B), so we apply Proposition 5 from the first online sample t 0 t_0 t 0 on. The summed probing costs of the two methods in (17) are then equal, and so are the first parts E P [ X t 0 T P ⋆ X t 0 ] \mathbb{E}_{\mathbb{P}}[X_{t_0}^{\mathsf{T}}P^\star X_{t_0}] E P [ X t 0 T P ⋆ X t 0 ] of their boundary terms, since both methods start from the same state X t 0 X_{t_0} X t 0 . The last part E P [ X T T P ⋆ X T ] \mathbb{E}_{\mathbb{P}}[X_T^{\mathsf{T}}P^\star X_T] E P [ X T T P ⋆ X T ] depends only on the final state and does not grow with T T T when the gains stabilize the plant. The summed gain-error cost, in contrast, adds a term at every sample, so for long runs the regrets differ mainly through the summed gain-error costs. We run each method with many random seeds s s s , and we compare two methods a a a and b b b by the ratio of their summed gain-error costs:
r : = ∑ s ∑ t = t 0 t 0 + T − 1 E t , s a ∑ s ∑ t = t 0 t 0 + T − 1 E t , s b . (17) r := \frac{\sum_s \sum_{t=t_0}^{t_0+T-1} \mathcal{E}_{t,s}^{a}}{\sum_s \sum_{t=t_0}^{t_0+T-1} \mathcal{E}_{t,s}^{b}}. \tag*{(17)} r := ∑ s ∑ t = t 0 t 0 + T − 1 E t , s b ∑ s ∑ t = t 0 t 0 + T − 1 E t , s a . (17)
We call a difference clear when the 95% paired-bootstrap interval of r r r over the seeds excludes one. Since the designer of each method chooses how much to probe, we repeat the comparison at the budgets c / C ⋆ ∈ { 1 / 64 , 1 / 16 , 1 / 4 , 1 / 2 , 1 , 2 } c/C^\star\in\{1/64, 1/16, 1/4, 1/2, 1, 2\} c / C ⋆ ∈ { 1/64 , 1/16 , 1/4 , 1/2 , 1 , 2 } . We do not consider larger budgets, at which the input would serve mainly to identify the plant rather than to control it.
Cheap and expensive input directions: We call the unit eigenvectors of S ⋆ S^\star S ⋆ the input directions . By (16), probing with variance ψ \psi ψ along an input direction with eigenvalue λ \lambda λ costs λ ψ \lambda\psi λ ψ , so different probing shapes can divide the probing cost differently among the input directions. We call an input direction cheap when its eigenvalue lies below the mean eigenvalue of S ⋆ S^\star S ⋆ , and expensive otherwise. We measure how much the input directions differ in cost by the quantity ϱ : = λ max ( S ⋆ ) / λ min ( S ⋆ ) \varrho:= \lambda_{\max}(S^\star)/\lambda_{\min}(S^\star) ϱ := λ m a x ( S ⋆ ) / λ m i n ( S ⋆ ) , which we call the input spread .
Remark 1 (KLPI’s probing shape against isotropic probing). With a known plant, α < 1 \alpha< 1 α < 1 and a constant regularization weight, KLPI’s probing covariance approaches a multiple of ( S ⋆ ) − 1 (S^\star)^{-1} ( S ⋆ ) − 1 (Theorem 1(a)). This covariance gives an input direction with eigenvalue λ \lambda λ , a variance proportional to 1 / λ 1/\lambda 1/ λ , and hence an equal share of the probing cost. Isotropic probing gives every input direction the same variance, and hence a share proportional to λ \lambda λ . At the same probing cost, the shape ( S ⋆ ) − 1 (S^\star)^{-1} ( S ⋆ ) − 1 therefore probes every cheap input direction more than isotropic probing does, and every expensive one less. The two shapes coincide when ϱ = 1 \varrho= 1 ϱ = 1 .
Simulation Setup
This subsection describes the four variants of KLPI and PGAC, how much they probe, the plants and the two ways a run starts. The code of all simulations is available at https://github.com/marginallyunstable/klpi4a1qr.
Table II. Plants used in the simulations. All plants have two inputs, Q = I n Q=I_n Q = I n and Σ W = I n \Sigma_W=I_n Σ W = I n . a ^a a Rescaled to a spectral radius drawn uniformly from [ 0.5 , 1.05 ] [0.5,1.05] [ 0.5 , 1.05 ] . For the random plants, twenty have φ = 1 \varphi=1 φ = 1 and twenty have log 10 φ \log_{10}\varphi log 10 φ drawn uniformly from [ 0 , 2 ] [0,2] [ 0 , 2 ] .
Compared variants: Both methods update a recursive least-squares estimate of the plant at every sample and compute their gain update on this plant estimate. KLPI’s gain update is a Gauss–Newton step with step size η = 1 − α 2 \eta=\frac{1-\alpha}{2} η = 2 1 − α and an averaged input Hessian (Section IV). We let PGAC take Gauss–Newton steps with the same step size, and we set α = 0.9 \alpha=0.9 α = 0.9 . To separate the two design choices, each method probes either isotropically, as in [1 ] , or with a covariance proportional to the inverse of its own preconditioner. The four combinations are the variants of Table I .
Table I. Gain update and probing of the four variants. Every variant starts from H t 0 = S ^ o f f / ( 1 − α ) H_{t_0}=\hat{S}_{\mathrm{off}}/(1-\alpha) H t 0 = S ^ off / ( 1 − α ) (Theorem 2) and updates its gain by K t + 1 = K t − H t + 1 − 1 E ^ t K_{t+1}=K_t-H_{t+1}^{-1}\hat{E}_t K t + 1 = K t − H t + 1 − 1 E ^ t .
Amount of probing: For KLPI, we use the constant regularization weight τ = 2 c / ( m ( 1 − α ) ) \tau=2c/(m(1-\alpha)) τ = 2 c / ( m ( 1 − α )) , for which Theorem 1(a) gives a probing cost P t P_t P t that tends to the budget c c c . The other variants probe with Σ t u = σ t 2 A t \Sigma_t^u=\sigma_t^2 A_t Σ t u = σ t 2 A t , where A t A_t A t is the shape in Table I . We choose σ t 2 \sigma_t^2 σ t 2 so that each of these variants pays the same probing cost (16) as KLPI at every sample, where KLPI probes with Ψ t K L P I = 2 τ ( H t K L P I ) − 1 \Psi_t^{\mathrm{KLPI}}=\frac{2}{\tau}(H_t^{\mathrm{KLPI}})^{-1} Ψ t KLPI = τ 2 ( H t KLPI ) − 1 .
σ t 2 Tr ( S ⋆ A t ) = Tr ( S ⋆ Ψ t K L P I ) . (18) \sigma_t^2\operatorname{Tr}(S^\star A_t)=\operatorname{Tr}(S^\star\Psi_t^{\mathrm{KLPI}}). \tag*{(18)} σ t 2 Tr ( S ⋆ A t ) = Tr ( S ⋆ Ψ t KLPI ) . (18)
This matching is the only computation that uses the true input Hessian S ⋆ S^\star S ⋆ , and no gain update uses it.
Plants: We test the variants on four plants, each chosen to bring out one effect, and on forty random plants that guard against conclusions specific to those four (Table II). P1 is the DeePO benchmark [7 ] , whose input spread is the smallest of P1–P4, so it serves as a control case. P2 and P3 have the same A A A and a large input spread, obtained from the input weight R R R on P2 and from the input matrix B B B on P3. P2 tests whether KLPI’s probing shape helps when the input directions differ strongly in cost, and P3 tests whether the source of the input spread matters. P4 has nearly the input spread of P2, but its A A A , B B B and R R R are diagonal, so each input drives its own state and the input directions are the two inputs. Its cheap input drives a state that decays slowly, whereas its expensive input affects its state for one sample only. Compared with isotropic probing, KLPI’s probing shape moves probing from the expensive input to the cheap one (Remark 1), so on P4 its probing enlarges the slowly decaying state. Since the gain-error cost (16) is quadratic in the state, P4 tests whether
KLPI’s probing shape still helps when its probing makes a gain error costlier.
Starts: Every run begins with t 0 = 100 t_0 = 100 t 0 = 100 offline samples under independent standard Gaussian inputs, to which we fit a least-squares estimate of the plant, followed by T = 10 5 T = 10^5 T = 1 0 5 online samples. In the standard start , the variants begin, as in [1 ] , with the certainty-equivalent gain of this plant estimate. The poor-gain start , used in Section VI-D, differs only in the initial gain, which is the certainty-equivalent gain of a plant estimate fitted to the first eight offline samples only. The gain updates still use the plant estimate fitted to all t 0 t_0 t 0 offline samples, so the poor initial gain is paired with a much more accurate plant estimate. Although this pairing is not a practical scenario, we use it as a controlled test of the averaging when the gain has much to improve.
The Probing Shape
We compare KLPI with PGAC-iso from the standard start by the ratio r r r in (18), which Figure 1 presents in three views. In Figure 1 (a), r r r covers whole runs on P1–P4 at every budget. In Figure 1 (b), r r r covers whole runs on the forty random plants at c = C ⋆ / 2 c = C^\star/2 c = C ⋆ /2 and is plotted against the input spread. Figure 1 (c) follows P1–P4 over time at c = C ⋆ c = C^\star c = C ⋆ , by the windowed ratio, which is r r r computed over a short window of online samples. KLPI and PGAC-iso differ in both design choices. However, KLPI and PGAC-shaped, which differ only in the averaging, have summed gain-error costs within 0.6% of each other on P1–P4 at every budget and on every random plant at c = C ⋆ / 2 c = C^\star/2 c = C ⋆ /2 . Figure 1 therefore omits PGAC-shaped, whose ratios in panels (a) and (b) would coincide with those of KLPI. The differences in summed gain-error cost between KLPI and PGAC-iso in Figure 1 thus come from KLPI’s probing shape, and PGAC-shaped shows the same differences against PGAC-iso.
Figure 1. Ratio r r r in (18) of KLPI to PGAC-iso from the standard start, with 95% bootstrap intervals over the seeds (480 per plant for P1–P4, 50 per random plant): (a) whole runs on P1–P4; (b) whole runs on the random plants, c = C ⋆ / 2 c = C^\star/2 c = C ⋆ /2 ; (c) windowed ratio on P1–P4, c = C ⋆ c = C^\star c = C ⋆ , with windows evenly spaced on the logarithmic axis.
KLPI’s probing shape lowers the summed gain-error cost on nearly every tested plant and budget, most on P2 and P4 (Figure 1 (a)). On the random plants, r r r tends to be smaller on plants with a larger input spread (Figure 1 (b)). Intuitively, the gain update multiplies the estimated slope by the inverse preconditioner, which is largest along the cheap input directions, so errors in the plant estimate move the gain update most along these directions. KLPI’s probing shape excites these directions more than isotropic probing does (Remark 1), and thus makes the plant estimate more accurate along these directions. The windowed ratio on P2 falls nearly steadily over the run (Figure 1 (c)).
The probing shape helps less on P3, and costs more early in the run on P3 and P4, and briefly on P1. P3 has the same A A A and the same input spread as P2, but its spread comes from B B B instead of R R R . On P3 the ratio r r r over whole runs stays close to one at every budget (Figure 1 (a)). On P3 the windowed ratio exceeds one for the first few dozen samples, falls to about 0.8 and then rises back towards one, whereas on P2 it keeps falling (Figure 1 (c)). The input spread alone therefore does not determine how much the probing shape helps. On P4, KLPI pays more than PGAC-iso early in the run and less afterwards (Figure 1 (c)). We attribute this early loss to KLPI’s stronger probing of the cheap input of P4, which enlarges the slowly decaying state, and with it the gain-error cost (16), before the gain has improved. In runs at c = 2 C ⋆ c = 2C^\star c = 2 C ⋆ , which Figure 1 (c) does not show, the early loss is larger, which is consistent with the rise of the ratio on P4 in Figure 1 (a)). Over whole runs, KLPI’s probing shape clearly raises the summed gain-error cost only on one random plant, and only slightly (Figure 1 (b)).
Overall, KLPI’s probing shape lowers the summed gain-error cost over whole runs on nearly every tested plant and budget, but by amounts that differ widely between plants, and not at every stage of a run. Intuitively, the probing covariance acts on the summed gain-error cost in two ways. It sets how strongly each input direction is excited, and thereby along which input directions the plant estimate becomes accurate, which shapes the gain updates. The probing also drives the state through B B B , and the gain-error cost (16) grows quadratically with the state. How the two effects combine depends on the plant, the budget and the stage of the run, and they can pull in opposite directions, as the early loss on P4 shows (Figure 1 (c)). A model that predicts when a probing shape helps and when it hurts would therefore help to design the probing. We do not develop such a model in this paper and leave it to future work.
The Averaging
This subsection asks how the averaging affects the gain-error cost from each of the two starts. We use the two pairs of variants of Table I that differ only in the averaging: KLPI-iso and PGAC-iso, and KLPI and PGAC-shaped. To see how fast each method improves its gain, we follow the relative gap of the gain, δ t : = ( C ( K t ) − C ⋆ ) / C ⋆ \delta_t := (C(K_t) - C^\star)/C^\star δ t := ( C ( K t ) − C ⋆ ) / C ⋆ , where C ( K t ) C(K_t) C ( K t ) is the average cost of the gain K t K_t K t without probing (Section II).
From the standard start, the ratio within each of the two pairs is close to one on P1–P4 at every budget, so Figure 2 shows only the poor-gain start. Intuitively, the averaged and the current input Hessians differ much only while the input Hessian changes quickly, as it does while a poor gain improves.
Figure 2. Effect of the averaging from the poor-gain start at c = C ⋆ c = C^\star c = C ⋆ (480 seeds per plant): (a) the ratio r r r in (18) within each pair that differs only in the averaging, with 95% bootstrap intervals; (b) the ratio of the median relative gap δ t \delta_t δ t of KLPI-iso to that of PGAC-iso, averaged over short windows of online samples.
From the poor-gain start, the averaging raises the gain-error cost slightly on some plants, and the probing shape barely alters this effect (Figure 2 (a)). Early in the run, KLPI-iso improves the gain more slowly than PGAC-iso, and afterwards the two relative gaps agree (Figure 2 (b)). Intuitively, as a poor gain improves, its input Hessian S K S_K S K shrinks with P K P_K P K (Lemma A.3 ), so an average over past input Hessians stays above the current one. The averaged preconditioner is then larger than PGAC’s, which shortens the gain step.
Conclusion
We approached adaptive LQR through a KL-regularized formulation, in which the probing is the randomness of a Gaussian policy and its cost enters the objective. This formulation offers one way to choose the probing covariance, which earlier works on policy-gradient adaptive control [1 ] , [7 ] leave as a design parameter. Each policy improvement yields a preconditioned gain update together with a probing covariance proportional to the inverse preconditioner (Proposition 1). With a suitable reference centred at the current gain, this gain update is PGAC’s Gauss–Newton or natural-gradient step for any step size below a bound (Proposition 3). We repeat the policy improvement against a tempered copy of the current policy, which gives KLPI, and show that with a known plant and α < 1 \alpha< 1 α < 1 the cost of its gain converges linearly and its probing covariance keeps a floor proportional to the regularization weight (Theorem 1). In the adaptive loop, with small updates, a suitably initialized preconditioner and the data condition, KLPI keeps the closed loop stable and its cost converges linearly up to a bias (Theorem 2), and its probing covariance keeps a floor proportional to the regularization weight (Corollary 1). In simulations at equal probing cost, KLPI’s probing shape, which PGAC can adopt, lowered the summed gain-error cost compared with isotropic probing on nearly all tested plants and budgets, by amounts that varied widely between plants. The probing shape raised the gain-error cost early in the run on some plants, and slightly over whole runs on one random plant. KLPI’s averaging of past input Hessians changed the gain-error cost little, except in a controlled test that starts from a poor gain, where it slowed the early improvement of the gain. We leave to future work a way to predict when a probing shape helps and when it hurts, and a regret bound, including which schedules of the regularization weight and of α \alpha α make the regret sublinear.
Acknowledgment
The authors used Claude (Anthropic), a large language model, in preparing this work. It drafted the proofs, the simulation code and parts of the text under the direction of the authors, who checked the results and take full responsibility for the content of this paper.
Overview of the Appendices
We collect the proofs in four appendices, and Figure 3 shows which results each proof uses. Appendix A collects the facts about the LQR that the later proofs use, and its first four lemmas build on one another. The cost-difference identity (Lemma A.1 ) expresses the change of the cost between two gains, and gradient dominance (Lemma A.2 ) follows from this identity. The expansion (21) in Lemma A.1 also gives a descent lemma in the Loewner order (Lemma A.3 ). This lemma shows that a gain step with a large enough preconditioner keeps the closed loop stable and decreases the solution P K P_K P K of its Lyapunov equation. Combined with gradient dominance, Lemma A.3 shows that each of these steps shrinks the gap C ( K ) − C ∗ C(K)-C^* C ( K ) − C ∗ to the optimal cost by a guaranteed fraction (Lemma A.4 ). Lemma A.5 bounds P K P_K P K , Σ K \Sigma_K Σ K and K K K for all gains of bounded cost, which gives the constants of Appendices C and D. Lemma A.6 bounds how the solution of a Lyapunov equation changes with its data, which Appendix D uses to compare the plant estimate with the true plant.
Figure 3. Dependencies among the results of the appendices. An arrow from one result to another means that the proof of the second uses the first, and the grey line in a box lists the lemmas of Appendix A used in the proof of that result. Shaded boxes are results stated in the body of the paper, and dashed boxes are proved there.
Appendix B proves Propositions 1 to 3 on one KL-regularized policy improvement, and the proof of Proposition 1 rests on the Gibbs variational identity (Lemma B.1). Lemma B.2 then shows that the iterations of KLPI do not increase the fixed objective of Section IV.
Appendix C proves Theorem 1 for a known plant by applying Lemmas A.3 and A.4 at every iteration, with the bounds of Lemma A.5.
Appendix D proves Theorem 2 on the adaptive loop and Proposition 5 on the cost split. Fact F1 bounds the error of the objects of a gain computed on the plant estimate, and Fact F2 bounds how these objects change with the gain. Facts F3 and F4 give the stability of the closed loop and a bound on its state. With these facts, Lemma D.1 keeps the estimated input Hessian in a fixed band, and Lemma D.2 bounds the cost after one step of Algorithm 1. An induction over the samples combines these results into Theorem 2.
Appendix A: Preliminaries
This appendix collects the facts about the LQR that the proofs use: a cost-difference identity, gradient dominance, a descent lemma for preconditioned steps in the Loewner order with its consequence for the cost, bounds on gains of bounded cost, and a perturbation bound for Lyapunov equations. The first four lemmas build on one another, and the last two supply bounds for the later appendices. For v ≥ C ⋆ v \ge C^{\star} v ≥ C ⋆ let S ( v ) : = { K ∈ S : C ( K ) ≤ v } \mathcal{S}(v) := \{K \in\mathcal{S}: C(K) \le v\} S ( v ) := { K ∈ S : C ( K ) ≤ v } . Lemmas A.1 and A.2 are proved in [3 ] for a noise-free plant with a random initial state. Their statements hold in the setting of this paper with Σ W \Sigma_W Σ W in place of the initial-state covariance of [3 ] , because in both settings the cost is the trace of P K P_K P K times this covariance, and P K P_K P K and Σ K \Sigma_K Σ K solve Lyapunov equations of the same form.
Lemma A.1 (Cost difference [3 Lemmas 10 and 12] ). For K , K ′ ∈ S K,K' \in\mathcal{S} K , K ′ ∈ S and Δ : = K ′ − K \Delta:= K' - K Δ := K ′ − K ,
C ( K ′ ) − C ( K ) = Tr ( Σ K ′ ( Δ T E K + E K T Δ + Δ T S K Δ ) ) , (19) C(K') - C(K) = \operatorname{Tr}\left(\Sigma_{K'}(\Delta^{\mathsf{T}}E_K + E_K^{\mathsf{T}}\Delta+ \Delta^{\mathsf{T}}S_K\Delta)\right), \tag*{(19)} C ( K ′ ) − C ( K ) = Tr ( Σ K ′ ( Δ T E K + E K T Δ + Δ T S K Δ ) ) , (19) where, with P : = P K P := P_K P := P K , the matrix in the trace is
Y : = Q + K ′ T R K ′ + A K ′ T P A K ′ − P Y := Q + K'^{\mathsf{T}}RK' + A_{K'}^{\mathsf{T}} P A_{K'} - P Y := Q + K ′ T R K ′ + A K ′ T P A K ′ − P = Δ T E K + E K T Δ + Δ T S K Δ . (20) = \Delta^{\mathsf{T}}E_K + E_K^{\mathsf{T}}\Delta+ \Delta^{\mathsf{T}}S_K\Delta. \tag*{(20)} = Δ T E K + E K T Δ + Δ T S K Δ. (20) The expansion (21) holds for every K ′ ∈ R m × n K' \in\mathbb{R}^{m \times n} K ′ ∈ R m × n , since it involves P K P_K P K but neither P K ′ P_{K'} P K ′ nor Σ K ′ \Sigma_{K'} Σ K ′ . In particular, (20) with K ⋆ K^{\star} K ⋆ in place of K K K and K K K in place of K ′ K' K ′ gives, since E K ⋆ = 0 E_{K^{\star}} = 0 E K ⋆ = 0 ,
C ( K ) − C ⋆ = Tr ( Σ K ( K − K ⋆ ) T S ⋆ ( K − K ⋆ ) ) , C(K) - C^{\star} = \operatorname{Tr}\left(\Sigma_K(K-K^{\star})^{\mathsf{T}}S^{\star}(K-K^{\star})\right), C ( K ) − C ⋆ = Tr ( Σ K ( K − K ⋆ ) T S ⋆ ( K − K ⋆ ) ) , which vanishes only at K = K ⋆ K = K^{\star} K = K ⋆ . Moreover, for K ∈ S K \in\mathcal{S} K ∈ S ,
P K − P ⋆ = A K T ( P K − P ⋆ ) A K + ( K − K ⋆ ) T S ⋆ ( K − K ⋆ ) , P_K - P^{\star} = A_K^{\mathsf{T}}(P_K-P^{\star})A_K + (K-K^{\star})^{\mathsf{T}}S^{\star}(K-K^{\star}), P K − P ⋆ = A K T ( P K − P ⋆ ) A K + ( K − K ⋆ ) T S ⋆ ( K − K ⋆ ) , so P K ⪰ P ⋆ P_K \succeq P^{\star} P K ⪰ P ⋆ .
The identity for P K − P ⋆ P_K-P^{\star} P K − P ⋆ in Lemma A.1 is not stated in [3 ] ; it follows from (21). Taking K ⋆ K^{\star} K ⋆ in place of K K K , K K K in place of K ′ K' K ′ and E K ⋆ = 0 E_{K^{\star}}=0 E K ⋆ = 0 in (21) gives Q + K T R K + A K ⋆ T P ⋆ A K ⋆ − P ⋆ = ( K − K ⋆ ) T S ⋆ ( K − K ⋆ ) Q+K^{\mathsf{T}}RK+A_{K^{\star}}^{\mathsf{T}}P^{\star}A_{K^{\star}}-P^{\star}=(K-K^{\star})^{\mathsf{T}}S^{\star}(K-K^{\star}) Q + K T R K + A K ⋆ T P ⋆ A K ⋆ − P ⋆ = ( K − K ⋆ ) T S ⋆ ( K − K ⋆ ) , and subtracting this identity from the Lyapunov equation P K = Q + K T R K + A K T P K A K P_K=Q+K^{\mathsf{T}}RK+A_K^{\mathsf{T}}P_KA_K P K = Q + K T R K + A K T P K A K gives the identity for P K − P ⋆ P_K-P^{\star} P K − P ⋆ . This identity is a Lyapunov equation with the Schur matrix A K A_K A K and a positive semidefinite constant term, so P K − P ⋆ ⪰ 0 P_K-P^{\star}\succeq0 P K − P ⋆ ⪰ 0 .
In [3 ] , gradient dominance is derived from Lemma A.1. Completing the square in the gain change Δ \Delta Δ bounds the matrix Y Y Y of (21) from below by − E K T S K − 1 E K -E_K^{\mathsf{T}}S_K^{-1}E_K − E K T S K − 1 E K , and (20) with K ⋆ K^{\star} K ⋆ in place of K ′ K' K ′ then gives the bound.
Lemma A.2 (Gradient dominance [3 Lemma 11] ). For K ∈ S K \in\mathcal{S} K ∈ S , C ( K ) − C ⋆ ≤ ∥ Σ ⋆ ∥ Tr ( E K T S K − 1 E K ) C(K)-C^{\star} \le\|\Sigma^{\star}\|\operatorname{Tr}(E_K^{\mathsf{T}}S_K^{-1}E_K) C ( K ) − C ⋆ ≤ ∥ Σ ⋆ ∥ Tr ( E K T S K − 1 E K ) .
Lemma A.3 (Loewner descent). Let K ∈ S K \in\mathcal{S} K ∈ S , S : = S K S := S_K S := S K , E : = E K E := E_K E := E K , χ ∈ ( 0 , 2 ) \chi\in(0,2) χ ∈ ( 0 , 2 ) , M ≻ 0 M \succ0 M ≻ 0 with M S M ⪯ χ M MSM \preceq\chi M M S M ⪯ χ M , and K ′ : = K − M E K' := K-ME K ′ := K − M E . Then K ′ ∈ S K' \in\mathcal{S} K ′ ∈ S and P K ′ ⪯ P K − ( 2 − χ ) E T M E P_{K'} \preceq P_K-(2-\chi)E^{\mathsf{T}}ME P K ′ ⪯ P K − ( 2 − χ ) E T M E .
Proof. Let F ( P ′ ) : = Q + K ′ T R K ′ + A K ′ T P ′ A K ′ F(P') := Q+K'^{\mathsf{T}}RK'+A_{K'}^{\mathsf{T}}P'A_{K'} F ( P ′ ) := Q + K ′ T R K ′ + A K ′ T P ′ A K ′ be the Lyapunov map of K ′ K' K ′ . We first evaluate F ( P K ) − P K F(P_K)-P_K F ( P K ) − P K , and then deduce that K ′ K' K ′ is stabilizing and that P K ′ P_{K'} P K ′ lies below P K P_K P K . With P = P K P=P_K P = P K , the matrix Y Y Y in (21) is F ( P K ) − P K F(P_K)-P_K F ( P K ) − P K , and the gain change is Δ = − M E \Delta=-ME Δ = − M E . Since M M M is symmetric, inserting Δ = − M E \Delta=-ME Δ = − M E into the right side of (21) gives − 2 E T M E + E T M S M E = − E T ( 2 M − M S M ) E -2E^{\mathsf{T}}ME+E^{\mathsf{T}}MSME=-E^{\mathsf{T}}(2M-MSM)E − 2 E T M E + E T M S M E = − E T ( 2 M − M S M ) E . Since M S M ⪯ χ M MSM\preceq\chi M M S M ⪯ χ M , we have 2 M − M S M ⪰ ( 2 − χ ) M 2M-MSM\succeq(2-\chi)M 2 M − M S M ⪰ ( 2 − χ ) M , and therefore
F ( P K ) − P K = − E T ( 2 M − M S M ) E ⪯ − ( 2 − χ ) E T M E . (21) F(P_K)-P_K=-E^{\mathsf{T}}(2M-MSM)E\preceq-(2-\chi)E^{\mathsf{T}}ME. \tag*{(21)} F ( P K ) − P K = − E T ( 2 M − M S M ) E ⪯ − ( 2 − χ ) E T M E . (21) Next we show that K ′ K' K ′ is stabilizing. Since F ( P K ) ⪯ P K F(P_K)\preceq P_K F ( P K ) ⪯ P K by (22), we have A K ′ T P K A K ′ − P K ⪯ − Q ≺ 0 A_{K'}^{\mathsf{T}}P_KA_{K'}-P_K\preceq-Q\prec0 A K ′ T P K A K ′ − P K ⪯ − Q ≺ 0 with P K ≻ 0 P_K\succ0 P K ≻ 0 . For an eigenvector v v v of A K ′ A_{K'} A K ′ with eigenvalue ζ v \zeta_v ζ v , this matrix inequality gives ( ∣ ζ v ∣ 2 − 1 ) v T P K v < 0 (|\zeta_v|^2-1)v^{\mathsf{T}}P_Kv<0 ( ∣ ζ v ∣ 2 − 1 ) v T P K v < 0 , so ∣ ζ v ∣ < 1 |\zeta_v|<1 ∣ ζ v ∣ < 1 and K ′ ∈ S K'\in\mathcal{S} K ′ ∈ S . It remains to compare P K ′ P_{K'} P K ′ with P K P_K P K . Since P K ′ = F ( P K ′ ) P_{K'}=F(P_{K'}) P K ′ = F ( P K ′ ) and F ( P K ) − F ( P K ′ ) = A K ′ T ( P K − P K ′ ) A K ′ F(P_K)-F(P_{K'})=A_{K'}^{\mathsf{T}}(P_K-P_{K'})A_{K'} F ( P K ) − F ( P K ′ ) = A K ′ T ( P K − P K ′ ) A K ′ , the difference P K − P K ′ P_K-P_{K'} P K − P K ′ satisfies
P K − P K ′ = ( P K − F ( P K ) ) + ( F ( P K ) − F ( P K ′ ) ) P_K-P_{K'}=(P_K-F(P_K))+(F(P_K)-F(P_{K'})) P K − P K ′ = ( P K − F ( P K )) + ( F ( P K ) − F ( P K ′ )) = ( P K − F ( P K ) ) + A K ′ T ( P K − P K ′ ) A K ′ , =(P_K-F(P_K))+A_{K'}^{\mathsf{T}}(P_K-P_{K'})A_{K'}, = ( P K − F ( P K )) + A K ′ T ( P K − P K ′ ) A K ′ , a Lyapunov equation with the Schur matrix A K ′ A_{K'} A K ′ . Its solution is ∑ k ≥ 0 ( A K ′ T ) k ( P K − F ( P K ) ) A K ′ k \sum_{k\geq0}(A_{K'}^{\mathsf{T}})^k(P_K-F(P_K))A_{K'}^k ∑ k ≥ 0 ( A K ′ T ) k ( P K − F ( P K )) A K ′ k , whose terms are positive semidefinite by (22), so the solution is at least its term k = 0 k=0 k = 0 , which is P K − F ( P K ) P_K-F(P_K) P K − F ( P K ) . Therefore (22) gives P K − P K ′ ⪰ ( 2 − χ ) E T M E P_K-P_{K'}\succeq(2-\chi)E^{\mathsf{T}}ME P K − P K ′ ⪰ ( 2 − χ ) E T M E .
Lemma A.4 (Preconditioned descent). Under the hypotheses of Lemma A.3, with ϰ : = λ min ( S 1 / 2 M S 1 / 2 ) \varkappa:= \lambda_{\min}(S^{1/2}MS^{1/2}) ϰ := λ m i n ( S 1/2 M S 1/2 ) and γ ⋆ \gamma^{\star} γ ⋆ as in Section II,
C ( K ′ ) − C ⋆ ≤ ( 1 − ( 2 − χ ) ϰ / γ ⋆ ) ( C ( K ) − C ⋆ ) , (22) C(K')-C^{\star}\leq(1-(2-\chi)\varkappa/\gamma^{\star})(C(K)-C^{\star}), \tag*{(22)} C ( K ′ ) − C ⋆ ≤ ( 1 − ( 2 − χ ) ϰ / γ ⋆ ) ( C ( K ) − C ⋆ ) , (22) and 0 < ( 2 − χ ) ϰ ≤ 1 ≤ γ ⋆ 0<(2-\chi)\varkappa\leq1\leq\gamma^{\star} 0 < ( 2 − χ ) ϰ ≤ 1 ≤ γ ⋆ , so the factor lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] .
Proof. Multiplying the Loewner decrease of Lemma A.3 by Σ W \Sigma_W Σ W and taking traces gives
C ( K ) − C ( K ′ ) = Tr ( ( P K − P K ′ ) Σ W ) ≥ ( 2 − χ ) Tr ( Σ W E ⊤ M E ) ≥ ( 2 − χ ) σ ( Σ W ) Tr ( E ⊤ M E ) ≥ ( 2 − χ ) ϰ σ ( Σ W ) Tr ( E ⊤ S − 1 E ) , \begin{aligned}
C(K)-C(K') &= \operatorname{Tr}\left((P_K-P_{K'})\Sigma_W\right)\\
&\ge(2-\chi)\operatorname{Tr}(\Sigma_W E^\top M E)\\
&\ge(2-\chi)\sigma(\Sigma_W)\operatorname{Tr}(E^\top M E)\\
&\ge(2-\chi)\varkappa\sigma(\Sigma_W)\operatorname{Tr}(E^\top S^{-1}E),
\end{aligned} C ( K ) − C ( K ′ ) = Tr ( ( P K − P K ′ ) Σ W ) ≥ ( 2 − χ ) Tr ( Σ W E ⊤ M E ) ≥ ( 2 − χ ) σ ( Σ W ) Tr ( E ⊤ M E ) ≥ ( 2 − χ ) ϰ σ ( Σ W ) Tr ( E ⊤ S − 1 E ) ,
where the last inequality uses M ⪰ ϰ S − 1 M \succeq\varkappa S^{-1} M ⪰ ϰ S − 1 , which follows from S 1 / 2 M S 1 / 2 ⪰ ϰ I S^{1/2}MS^{1/2} \succeq\varkappa I S 1/2 M S 1/2 ⪰ ϰ I . Lemma A.2 together with γ ⋆ = ∥ Σ ⋆ ∥ / σ ( Σ W ) \gamma^\star=\lVert\Sigma^\star\rVert/\sigma(\Sigma_W) γ ⋆ = ∥ Σ ⋆ ∥ / σ ( Σ W ) gives σ ( Σ W ) Tr ( E ⊤ S − 1 E ) ≥ ( C ( K ) − C ⋆ ) / γ ⋆ \sigma(\Sigma_W)\operatorname{Tr}(E^\top S^{-1}E)\ge(C(K)-C^\star)/\gamma^\star σ ( Σ W ) Tr ( E ⊤ S − 1 E ) ≥ ( C ( K ) − C ⋆ ) / γ ⋆ , so C ( K ) − C ( K ′ ) ≥ ( 2 − χ ) ( ϰ / γ ⋆ ) ( C ( K ) − C ⋆ ) C(K)-C(K')\ge(2-\chi)(\varkappa/\gamma^\star)(C(K)-C^\star) C ( K ) − C ( K ′ ) ≥ ( 2 − χ ) ( ϰ / γ ⋆ ) ( C ( K ) − C ⋆ ) , and subtracting this bound from C ( K ) − C ⋆ C(K)-C^\star C ( K ) − C ⋆ gives (23). For the bounds on ( 2 − χ ) ϰ (2-\chi)\varkappa ( 2 − χ ) ϰ , multiplying M S M ⪯ χ M MSM\preceq\chi M M S M ⪯ χ M on both sides by M − 1 / 2 M^{-1/2} M − 1/2 gives M 1 / 2 S M 1 / 2 ⪯ χ I M^{1/2}SM^{1/2}\preceq\chi I M 1/2 S M 1/2 ⪯ χ I . The matrices M 1 / 2 S M 1 / 2 M^{1/2}SM^{1/2} M 1/2 S M 1/2 and S 1 / 2 M S 1 / 2 S^{1/2}MS^{1/2} S 1/2 M S 1/2 have the same eigenvalues, and S 1 / 2 M S 1 / 2 ≻ 0 S^{1/2}MS^{1/2}\succ0 S 1/2 M S 1/2 ≻ 0 , so 0 < ϰ ≤ χ 0<\varkappa\le\chi 0 < ϰ ≤ χ . Hence 0 < ( 2 − χ ) ϰ ≤ ( 2 − χ ) χ ≤ 1 ≤ γ ⋆ 0<(2-\chi)\varkappa\le(2-\chi)\chi\le1\le\gamma^\star 0 < ( 2 − χ ) ϰ ≤ ( 2 − χ ) χ ≤ 1 ≤ γ ⋆ , where ( 2 − χ ) χ ≤ 1 (2-\chi)\chi\le1 ( 2 − χ ) χ ≤ 1 because 1 − ( 2 − χ ) χ = ( 1 − χ ) 2 1-(2-\chi)\chi=(1-\chi)^2 1 − ( 2 − χ ) χ = ( 1 − χ ) 2 .
The proofs of Theorems 1 and 2 need bounds that hold for every gain along the iterations and a compact set that contains these gains, and the next lemma provides both.
Lemma A.5 (Bounds). For K ∈ S K\in\mathcal{S} K ∈ S , ∥ P K ∥ ≤ C ( K ) / σ ( Σ W ) \lVert P_K\rVert\le C(K)/\sigma(\Sigma_W) ∥ P K ∥ ≤ C ( K ) / σ ( Σ W ) , ∥ Σ K ∥ ≤ C ( K ) / σ ( Q ) \lVert\Sigma_K\rVert\le C(K)/\sigma(Q) ∥ Σ K ∥ ≤ C ( K ) / σ ( Q ) and ∥ K ∥ 2 ≤ C ( K ) / ( σ ( R ) σ ( Σ W ) ) \lVert K\rVert^2\le C(K)/(\sigma(R)\sigma(\Sigma_W)) ∥ K ∥ 2 ≤ C ( K ) / ( σ ( R ) σ ( Σ W )) , and S ( v ) \mathcal{S}(v) S ( v ) is compact.
Proof. The first two bounds are [3 Lemma 13] , and the third extends [1 Lemma 10] to a general Σ W \Sigma_W Σ W . The bounds follow from C ( K ) = Tr ( P K Σ W ) = Tr ( ( Q + K ⊤ R K ) Σ K ) C(K)=\operatorname{Tr}(P_K\Sigma_W)=\operatorname{Tr}((Q+K^\top RK)\Sigma_K) C ( K ) = Tr ( P K Σ W ) = Tr (( Q + K ⊤ R K ) Σ K ) with P K ⪰ 0 P_K\succeq0 P K ⪰ 0 and Σ K ⪰ Σ W ⪰ σ ( Σ W ) I n \Sigma_K\succeq\Sigma_W\succeq\sigma(\Sigma_W)I_n Σ K ⪰ Σ W ⪰ σ ( Σ W ) I n ; in particular S ( v ) \mathcal{S}(v) S ( v ) is bounded. For closedness, let K j ∈ S ( v ) K_j\in\mathcal{S}(v) K j ∈ S ( v ) converge to K ‾ \overline{K} K ; since Σ K j = ∑ k ≥ 0 A K j k Σ W ( A K j ⊤ ) k \Sigma_{K_j}=\sum_{k\ge0}A_{K_j}^k\Sigma_W(A_{K_j}^\top)^k Σ K j = ∑ k ≥ 0 A K j k Σ W ( A K j ⊤ ) k , the partial sums ∑ k ≤ N A K j k Σ W ( A K j ⊤ ) k ⪯ Σ K j ⪯ v σ ( Q ) σ ( Σ W ) I \sum_{k\le N}A_{K_j}^k\Sigma_W(A_{K_j}^\top)^k\preceq\Sigma_{K_j}\preceq\frac{v}{\sigma(Q)\sigma(\Sigma_W)}I ∑ k ≤ N A K j k Σ W ( A K j ⊤ ) k ⪯ Σ K j ⪯ σ ( Q ) σ ( Σ W ) v I pass to the limit for every N N N , so A K ‾ A_{\overline{K}} A K is Schur, and C ( K ‾ ) ≤ v C(\overline{K})\le v C ( K ) ≤ v by continuity of C C C on S \mathcal{S} S .
The last lemma of this appendix bounds the change of the solution of a Lyapunov equation when its Schur matrix L L L and its constant term Y Y Y change, and Appendix D uses it to prove Facts F1 and F2. It is a variant of [1 Lemma 11] , which treats Σ = I n + L Σ L ⊤ \Sigma=I_n+L\Sigma L^\top Σ = I n + L Σ L ⊤ and gives a bound of this kind with other constants. The general weight Y Y Y is needed for the equation of P K P_K P K , whose weight is Q + K ⊤ R K Q+K^\top RK Q + K ⊤ R K , and for the equation of Σ K \Sigma_K Σ K with a general Σ W \Sigma_W Σ W ; the proof of Fact F2 uses the change of the weight.
Lemma A.6 (Lyapunov perturbation). Let L L L be Schur, Y ⪰ y I Y\succeq yI Y ⪰ y I with y > 0 y>0 y > 0 , and let P P P solve P = Y + L ⊤ P L P=Y+L^\top P L P = Y + L ⊤ P L . Let L ′ L' L ′ and a symmetric Y ′ Y' Y ′ be such that δ : = ∥ L ′ − L ∥ \delta:=\lVert L'-L\rVert δ := ∥ L ′ − L ∥ satisfies β : = ∥ P ∥ δ ( 2 ∥ L ∥ + δ ) ≤ y / 2 \beta:=\lVert P\rVert\delta(2\lVert L\rVert+\delta)\le y/2 β := ∥ P ∥ δ ( 2 ∥ L ∥ + δ ) ≤ y /2 . Then L ′ L' L ′ is Schur, and the solution P ′ P' P ′ of P ′ = Y ′ + L ′ ⊤ P ′ L ′ P'=Y'+L'^\top P'L' P ′ = Y ′ + L ′⊤ P ′ L ′ satisfies
∥ P ′ − P ∥ ≤ 2 ∥ P ∥ y ( ∥ Y ′ − Y ∥ + β ) . (23) \lVert P'-P\rVert\le\frac{2\lVert P\rVert}{y}(\lVert Y'-Y\rVert+\beta). \tag*{(23)} ∥ P ′ − P ∥ ≤ y 2 ∥ P ∥ (∥ Y ′ − Y ∥ + β ) . (23)
The same holds with L L L and L ′ L' L ′ replaced by L ⊤ L^\top L ⊤ and L ′ ⊤ L'^\top L ′⊤ , which covers the equations Σ = Y + L Σ L ⊤ \Sigma=Y+L\Sigma L^\top Σ = Y + L Σ L ⊤ .
Proof. The idea is that P P P certifies the stability of L ′ L' L ′ with margin y / 2 y/2 y /2 , and summing the Lyapunov difference along L ′ L' L ′ then bounds P ′ − P P'-P P ′ − P . The matrix Δ : = L ′ ⊤ P L ′ − L ⊤ P L = ( L ′ − L ) ⊤ P L ′ + L ⊤ P ( L ′ − L ) \Delta:=L'^\top P L'-L^\top P L=(L'-L)^\top P L'+L^\top P(L'-L) Δ := L ′⊤ P L ′ − L ⊤ P L = ( L ′ − L ) ⊤ P L ′ + L ⊤ P ( L ′ − L ) satisfies ∥ Δ ∥ ≤ ∥ P ∥ δ ( ∥ L ′ ∥ + ∥ L ∥ ) ≤ β \lVert\Delta\rVert\le\lVert P\rVert\delta(\lVert L'\rVert+\lVert L\rVert)\le\beta ∥ Δ ∥ ≤ ∥ P ∥ δ (∥ L ′ ∥ + ∥ L ∥) ≤ β , so P − L ′ ⊤ P L ′ = Y − Δ ⪰ y I / 2 P-L'^\top P L'=Y-\Delta\succeq yI/2 P − L ′⊤ P L ′ = Y − Δ ⪰ y I /2 . For an eigenvector v v v of L ′ L' L ′ with eigenvalue ζ v \zeta_v ζ v , the bound P − L ′ ⊤ P L ′ ⪰ y I / 2 P-L'^\top P L'\succeq yI/2 P − L ′⊤ P L ′ ⪰ y I /2 gives ( 1 − ∣ ζ v ∣ 2 ) v ⊤ P v > 0 (1-\lvert\zeta_v\rvert^2)v^\top Pv>0 ( 1 − ∣ ζ v ∣ 2 ) v ⊤ P v > 0 with P v ≠ 0 Pv\ne0 P v = 0 , so L ′ L' L ′ is Schur. Summing L ′ k ⊤ ( P − L ′ ⊤ P L ′ ) L ′ k L'^{k\top}(P-L'^\top P L')L'^k L ′ k ⊤ ( P − L ′⊤ P L ′ ) L ′ k over k ≤ N k\le N k ≤ N telescopes to P − L ′ ( N + 1 ) ⊤ P L ′ N + 1 ⪯ P P-L'^{(N+1)\top}PL'^{N+1}\preceq P P − L ′ ( N + 1 ) ⊤ P L ′ N + 1 ⪯ P , so G : = ∑ k ≥ 0 L ′ k ⊤ L ′ k ⪯ 2 P / y G:=\sum_{k\ge0}L'^{k\top}L'^k\preceq2P/y G := ∑ k ≥ 0 L ′ k ⊤ L ′ k ⪯ 2 P / y . Subtracting the two Lyapunov equations gives P ′ − P = Y ′ − Y + Δ + L ′ ⊤ ( P ′ − P ) L ′ P'-P=Y'-Y+\Delta+L'^\top(P'-P)L' P ′ − P = Y ′ − Y + Δ + L ′⊤ ( P ′ − P ) L ′ , so P ′ − P = ∑ k ≥ 0 L ′ k ⊤ ( Y ′ − Y + Δ ) L ′ k P'-P=\sum_{k\ge0}L'^{k\top}(Y'-Y+\Delta)L'^k P ′ − P = ∑ k ≥ 0 L ′ k ⊤ ( Y ′ − Y + Δ ) L ′ k , whose norm is at most ∥ G ∥ ∥ Y ′ − Y + Δ ∥ ≤ 2 ∥ P ∥ y ( ∥ Y ′ − Y ∥ + β ) \lVert G\rVert\lVert Y'-Y+\Delta\rVert\le\frac{2\lVert P\rVert}{y}(\lVert Y'-Y\rVert+\beta) ∥ G ∥ ∥ Y ′ − Y + Δ ∥ ≤ y 2 ∥ P ∥ (∥ Y ′ − Y ∥ + β ) , which is (24). The transposed case is the same argument applied to L ⊤ L^\top L ⊤ and L ′ ⊤ L'^\top L ′⊤ , which have the norms of L L L and L ′ L' L ′ .
Appendix B: Proofs of Sections III and IV
The proofs rest on the Gibbs variational identity, applied state by state.
Lemma B.1 (Gibbs variational identity [18 Thm. 1 and Lemma 1] ). Let τ > 0 \tau>0 τ > 0 , μ \mu μ a distribution and f f f a function with E Y ∼ μ [ e − f ( Y ) / τ ] < ∞ \mathbb{E}_{Y\sim\mu}[e^{-f(Y)/\tau}]<\infty E Y ∼ μ [ e − f ( Y ) / τ ] < ∞ , and μ ⋆ : = μ e − f / τ / Z \mu^\star:=\mu e^{-f/\tau}/\mathcal{Z} μ ⋆ := μ e − f / τ / Z . For every μ ′ \mu' μ ′ with D K L ( μ ′ ∥ μ ) < ∞ D_{\mathrm{KL}}(\mu'\Vert\mu)<\infty D KL ( μ ′ ∥ μ ) < ∞ and E Y ∼ μ ′ [ f ( Y ) ] < ∞ \mathbb{E}_{Y\sim\mu'}[f(Y)]<\infty E Y ∼ μ ′ [ f ( Y )] < ∞ ,
E Y ∼ μ ′ [ f ( Y ) ] + τ D K L ( μ ′ ∥ μ ) = − τ log Z + τ D K L ( μ ′ ∥ μ ⋆ ) , (24) \mathbb{E}_{Y\sim\mu'}[f(Y)]+\tau D_{\mathrm{KL}}(\mu'\Vert\mu)=-\tau\log\mathcal{Z}+\tau D_{\mathrm{KL}}(\mu'\Vert\mu^\star), \tag*{(24)} E Y ∼ μ ′ [ f ( Y )] + τ D KL ( μ ′ ∥ μ ) = − τ log Z + τ D KL ( μ ′ ∥ μ ⋆ ) , (24)
so μ ⋆ \mu^\star μ ⋆ is the unique minimizer of the left side.
The cited results state the variational form of (25) and its minimizer; the identity itself follows by inserting the density of μ ⋆ \mu^\star μ ⋆ into D K L ( μ ′ ∥ μ ⋆ ) D_{\mathrm{KL}}(\mu'\Vert\mu^\star) D KL ( μ ′ ∥ μ ⋆ ) .
Proof of Proposition 1: The proof evaluates π \pi π through its Bellman equation for (a), computes the Gibbs minimizer by completing a square for (b), shows that the new gain is stabilizing and compares the two policies by telescoping for (c), and then specializes to K ρ = K K_{\rho}=K K ρ = K for (d). Throughout, P : = P K ρ P := P^{\rho}_{K} P := P K ρ , S : = S K ρ S := S^{\rho}_{K} S := S K ρ , N : = B T P A N := B^{\mathsf T}PA N := B T P A and E : = E K ρ = S K + N + D ( K − K ρ ) E := E^{\rho}_{K}=SK+N+D(K-K_{\rho}) E := E K ρ = S K + N + D ( K − K ρ ) . We first prove (a). Since π ( ⋅ ∣ x ) \pi(\cdot\mid x) π ( ⋅ ∣ x ) and ρ ( ⋅ ∣ x ) \rho(\cdot\mid x) ρ ( ⋅ ∣ x ) are Gaussian with means K x Kx K x and K ρ x K_{\rho}x K ρ x , the penalty is τ κ ρ π ( x ) = ϖ + x T ( K − K ρ ) T D ( K − K ρ ) x \tau\kappa^{\pi}_{\rho}(x)=\varpi+x^{\mathsf T}(K-K_{\rho})^{\mathsf T}D(K-K_{\rho})x τ κ ρ π ( x ) = ϖ + x T ( K − K ρ ) T D ( K − K ρ ) x with ϖ : = τ D K L ( N ( 0 , Ψ ) ∥ N ( 0 , Ψ ρ ) ) \varpi:= \tau D_{\mathrm{KL}}(\mathcal{N}(0,\Psi)\Vert\mathcal{N}(0,\Psi_{\rho})) ϖ := τ D KL ( N ( 0 , Ψ ) ∥ N ( 0 , Ψ ρ )) . With V ( x ) : = x T P x V(x):=x^{\mathsf T}Px V ( x ) := x T P x , Q ( x , u ) : = c ( x , u ) + E X ′ ∼ N ( A x + B u , Σ W ) [ V ( X ′ ) ] = x T Q x + u T R u + ( A x + B u ) T P ( A x + B u ) + Tr ( P Σ W ) Q(x,u):=c(x,u)+\mathbb{E}_{X'\sim\mathcal{N}(Ax+Bu,\Sigma_{W})}[V(X')] = x^{\mathsf T}Qx+u^{\mathsf T}Ru+(Ax+Bu)^{\mathsf T}P(Ax+Bu)+\operatorname{Tr}(P\Sigma_{W}) Q ( x , u ) := c ( x , u ) + E X ′ ∼ N ( A x + B u , Σ W ) [ V ( X ′ )] = x T Q x + u T R u + ( A x + B u ) T P ( A x + B u ) + Tr ( P Σ W ) . Averaging over U = K x + Ω U=Kx+\Omega U = K x + Ω , Ω ∼ N ( 0 , Ψ ) \Omega\sim\mathcal{N}(0,\Psi) Ω ∼ N ( 0 , Ψ ) , removes the term linear in Ω \Omega Ω and gives
E U ∼ π ( ⋅ ∣ x ) [ Q ( x , U ) ] + τ κ ρ π ( x ) = V ( x ) + Tr ( P Σ W ) + Tr ( S Ψ ) + ϖ , (25) \mathbb{E}_{U\sim\pi(\cdot\mid x)}[Q(x,U)]+\tau\kappa^{\pi}_{\rho}(x)
=V(x)+\operatorname{Tr}(P\Sigma_{W})+\operatorname{Tr}(S\Psi)+\varpi, \tag*{(25)} E U ∼ π ( ⋅ ∣ x ) [ Q ( x , U )] + τ κ ρ π ( x ) = V ( x ) + Tr ( P Σ W ) + Tr ( S Ψ ) + ϖ , (25)
because Q + K T R K + ( K − K ρ ) T D ( K − K ρ ) + A K T P A K = P Q+K^{\mathsf T}RK+(K-K_{\rho})^{\mathsf T}D(K-K_{\rho})+A^{\mathsf T}_{K}PA_{K}=P Q + K T R K + ( K − K ρ ) T D ( K − K ρ ) + A K T P A K = P . Hence V V V and J ˉ : = Tr ( P Σ W ) + Tr ( S Ψ ) + ϖ \bar{J}:=\operatorname{Tr}(P\Sigma_{W})+\operatorname{Tr}(S\Psi)+\varpi J ˉ := Tr ( P Σ W ) + Tr ( S Ψ ) + ϖ solve the Bellman equation of π \pi π for (P). Summing (26) at X t X_t X t along P π \mathbb{P}^{\pi} P π telescopes the terms in V V V , and since A K A_K A K is Schur and the inputs are Gaussian, E P π [ V ( X T ) ] \mathbb{E}_{\mathbb{P}^{\pi}}[V(X_T)] E P π [ V ( X T )] is bounded in T T T , so J ρ ( π ) = J ˉ J_{\rho}(\pi)=\bar{J} J ρ ( π ) = J ˉ and V π = V V_{\pi}=V V π = V up to a constant. Next we prove (b) by computing the minimizer of (6). We apply Lemma B.1 with μ = ρ ( ⋅ ∣ x ) \mu=\rho(\cdot\mid x) μ = ρ ( ⋅ ∣ x ) and f = Q ( x , ⋅ ) f=Q(x,\cdot) f = Q ( x , ⋅ ) ; the function f f f is bounded below since S ≻ 0 S\succ0 S ≻ 0 , so Z < ∞ Z<\infty Z < ∞ . Since V π = V V_{\pi}=V V π = V up to a constant, Q π Q_{\pi} Q π and Q Q Q differ by a constant, so the left side of (25) with these choices equals the objective of (6) up to a constant, and the minimizer of (6) is the distribution μ ⋆ \mu^{\star} μ ⋆ of Lemma B.1, proportional to ρ ( u ∣ x ) e − Q ( x , u ) / τ \rho(u\mid x)e^{-Q(x,u)/\tau} ρ ( u ∣ x ) e − Q ( x , u ) / τ . Its exponent in u u u is
− 1 2 u T ( Ψ ρ − 1 + 2 τ S ) u + u T ( Ψ ρ − 1 K ρ − 2 τ N ) x + terms in x , (26) -\frac{1}{2}u^{\mathsf T}\left(\Psi_{\rho}^{-1}+\frac{2}{\tau}S\right)u+u^{\mathsf T}\left(\Psi_{\rho}^{-1}K_{\rho}-\frac{2}{\tau}N\right)x+\text{terms in }x, \tag*{(26)} − 2 1 u T ( Ψ ρ − 1 + τ 2 S ) u + u T ( Ψ ρ − 1 K ρ − τ 2 N ) x + terms in x , (26)
so π ′ ( ⋅ ∣ x ) \pi^{\prime}(\cdot\mid x) π ′ ( ⋅ ∣ x ) is Gaussian with precision Ψ ρ − 1 + 2 τ S = 2 τ ( D + S ) = 2 τ H \Psi_{\rho}^{-1}+\frac{2}{\tau}S=\frac{2}{\tau}(D+S)=\frac{2}{\tau}H Ψ ρ − 1 + τ 2 S = τ 2 ( D + S ) = τ 2 H and mean H − 1 ( D K ρ − N ) x = H − 1 ( H K − E ) x H^{-1}(DK_{\rho}-N)x=H^{-1}(HK-E)x H − 1 ( D K ρ − N ) x = H − 1 ( H K − E ) x , which is (7). We now prove (c). Write c ρ ( x , u ) : = c ( x , u ) + ( u − K ρ x ) T D ( u − K ρ x ) c_{\rho}(x,u):=c(x,u)+(u-K_{\rho}x)^{\mathsf T}D(u-K_{\rho}x) c ρ ( x , u ) := c ( x , u ) + ( u − K ρ x ) T D ( u − K ρ x ) . For this stage cost, P P P solves the Lyapunov equation of the gain K K K , and expanding as in (21) gives, for every K ′ K^{\prime} K ′ with Δ : = K ′ − K \Delta:=K^{\prime}-K Δ := K ′ − K ,
Q + K ′ T R K ′ + ( K ′ − K ρ ) T D ( K ′ − K ρ ) + A K ′ T P A K ′ − P = Δ T E + E T Δ + Δ T H Δ . Q+K^{\prime\mathsf T}RK^{\prime}+(K^{\prime}-K_{\rho})^{\mathsf T}D(K^{\prime}-K_{\rho})+A^{\mathsf T}_{K^{\prime}}PA_{K^{\prime}}-P
=\Delta^{\mathsf T}E+E^{\mathsf T}\Delta+\Delta^{\mathsf T}H\Delta. Q + K ′ T R K ′ + ( K ′ − K ρ ) T D ( K ′ − K ρ ) + A K ′ T P A K ′ − P = Δ T E + E T Δ + Δ T H Δ.
By (7), Δ = − H − 1 E \Delta=-H^{-1}E Δ = − H − 1 E , so the right side of this expansion is − 2 E T H − 1 E + E T H − 1 E = − E T H − 1 E ⪯ 0 -2E^{\mathsf T}H^{-1}E+E^{\mathsf T}H^{-1}E=-E^{\mathsf T}H^{-1}E\preceq0 − 2 E T H − 1 E + E T H − 1 E = − E T H − 1 E ⪯ 0 . The matrix P P P solves the Lyapunov equation of the Schur matrix A K A_K A K with a constant term at least Q Q Q , so P ⪰ Q P\succeq Q P ⪰ Q . Hence A K ′ T P A K ′ − P ⪯ − Q ≺ 0 A^{\mathsf T}_{K^{\prime}}PA_{K^{\prime}}-P\preceq-Q\prec0 A K ′ T P A K ′ − P ⪯ − Q ≺ 0 with P ⪰ Q ≻ 0 P\succeq Q\succ0 P ⪰ Q ≻ 0 , so A K ′ A_{K^{\prime}} A K ′ is Schur by Lyapunov’s stability theorem, that is, K ′ ∈ S K^{\prime}\in\mathcal{S} K ′ ∈ S . By the optimality of π ′ \pi^{\prime} π ′ in (6) and by (26), for every x x x ,
E U ∼ π ′ ( ⋅ ∣ x ) [ Q ( x , U ) ] + τ κ ρ π ′ ( x ) ≤ V ( x ) + J ˉ . (27) \mathbb{E}_{U\sim\pi^{\prime}(\cdot\mid x)}[Q(x,U)]+\tau\kappa^{\pi^{\prime}}_{\rho}(x)\leq V(x)+\bar{J}. \tag*{(27)} E U ∼ π ′ ( ⋅ ∣ x ) [ Q ( x , U )] + τ κ ρ π ′ ( x ) ≤ V ( x ) + J ˉ . (27)
Evaluating (28) at X t X_t X t under P π ′ \mathbb{P}^{\pi^{\prime}} P π ′ , using E P π ′ [ Q ( X t , U t ) ] = E P π ′ [ c ( X t , U t ) + V ( X t + 1 ) ] \mathbb{E}_{\mathbb{P}^{\pi^{\prime}}}[Q(X_t,U_t)]=\mathbb{E}_{\mathbb{P}^{\pi^{\prime}}}[c(X_t,U_t)+V(X_{t+1})] E P π ′ [ Q ( X t , U t )] = E P π ′ [ c ( X t , U t ) + V ( X t + 1 )] and summing over t < T t<T t < T gives E P π ′ [ ∑ t < T ( c ( X t , U t ) + τ κ ρ π ′ ( X t ) ) ] ≤ T J ˉ + E P π ′ [ V ( X 0 ) − V ( X T ) ] ≤ T J ˉ + E P π ′ [ V ( X 0 ) ] \mathbb{E}_{\mathbb{P}^{\pi^{\prime}}}\left[\sum_{t<T}(c(X_t,U_t)+\tau\kappa^{\pi^{\prime}}_{\rho}(X_t))\right]\leq T\bar{J}+\mathbb{E}_{\mathbb{P}^{\pi^{\prime}}}[V(X_0)-V(X_T)]\leq T\bar{J}+\mathbb{E}_{\mathbb{P}^{\pi^{\prime}}}[V(X_0)] E P π ′ [ ∑ t < T ( c ( X t , U t ) + τ κ ρ π ′ ( X t )) ] ≤ T J ˉ + E P π ′ [ V ( X 0 ) − V ( X T )] ≤ T J ˉ + E P π ′ [ V ( X 0 )] , since V ≥ 0 V\geq0 V ≥ 0 ; the expectations are finite because K ′ ∈ S K^{\prime}\in\mathcal{S} K ′ ∈ S and κ ρ π ′ \kappa^{\pi^{\prime}}_{\rho} κ ρ π ′ is quadratic in x x x . Dividing by T T T gives J ρ ( π ′ ) ≤ J ˉ = J ρ ( π ) J_{\rho}(\pi^{\prime})\leq\bar{J}=J_{\rho}(\pi) J ρ ( π ′ ) ≤ J ˉ = J ρ ( π ) . Finally, we prove (d). If K ρ = K K_{\rho}=K K ρ = K , the Lyapunov equation of P K ρ P^{\rho}_{K} P K ρ is that of P K P_K P K , so S = S K S=S_K S = S K , E = E K E=E_K E = E K , Q = Q K + C ( K ) Q=Q_K+C(K) Q = Q K + C ( K ) by (3), and (7) becomes (8). Since H ⪰ S K H\succeq S_K H ⪰ S K , M : = H − 1 M:=H^{-1} M := H − 1 satisfies M S K M ⪯ M MS_KM\preceq M M S K M ⪯ M , and the gain of (8) is K ′ = K − M E K K^{\prime}=K-ME_K K ′ = K − M E K . Lemma A.3 with this M M M and χ = 1 \chi=1 χ = 1 therefore gives V K − E K T M E K = P K − E K T H − 1 E K V_K-E_K^{\mathsf T}ME_K=P_K-E_K^{\mathsf T}H^{-1}E_K V K − E K T M E K = P K − E K T H − 1 E K .
Proof of Proposition 2: The closed loop X t + 1 = A K X t + B Ω t + W t X_{t+1}=A_KX_t+B\Omega_t+W_t X t + 1 = A K X t + B Ω t + W t is stable with the sum B Ω t + W t B\Omega_t+W_t B Ω t + W t of covariance Σ W + B Ψ B T \Sigma_W+B\Psi B^{\mathsf T} Σ W + B Ψ B T , so by the duality of the two Lyapunov equations its average cost is Tr ( P K ( Σ W + B Ψ B T ) ) + Tr ( R Ψ ) = C ( K ) + Tr ( S K Ψ ) \operatorname{Tr}(P_K(\Sigma_W+B\Psi B^{\mathsf T}))+\operatorname{Tr}(R\Psi)=C(K)+\operatorname{Tr}(S_K\Psi) Tr ( P K ( Σ W + B Ψ B T )) + Tr ( R Ψ ) = C ( K ) + Tr ( S K Ψ ) . With λ 1 , … , λ m \lambda_1,\ldots,\lambda_m λ 1 , … , λ m the eigenvalues of S K 1 / 2 Ψ S K 1 / 2 S_K^{1/2}\Psi S_K^{1/2} S K 1/2 Ψ S K 1/2 , Tr ( S K Ψ ) = ∑ i λ i ≥ m ( ∏ i λ i ) 1 / m \operatorname{Tr}(S_K\Psi)=\sum_i\lambda_i\geq m(\prod_i\lambda_i)^{1/m} Tr ( S K Ψ ) = ∑ i λ i ≥ m ( ∏ i λ i ) 1/ m by the inequality of arithmetic and geometric means, with equality exactly when the λ i \lambda_i λ i are equal.
Proof of Proposition 3: For (i), H = S K + D H=S_K+D H = S K + D by (8), and D = τ 2 Ψ ρ − 1 D=\frac{\tau}{2}\Psi_{\rho}^{-1} D = 2 τ Ψ ρ − 1 is a bijection between Ψ ρ ≻ 0 \Psi_{\rho}\succ0 Ψ ρ ≻ 0 and D ≻ 0 D\succ0 D ≻ 0 , so H H H is reached exactly by D = H − S K D=H-S_K D = H − S K . For (ii), H = S K 2 η H=\frac{S_K}{2\eta} H = 2 η S K gives D = 1 − 2 η 2 η S K ≻ 0 D=\frac{1-2\eta}{2\eta}S_K\succ0 D = 2 η 1 − 2 η S K ≻ 0 for η < 1 2 \eta<\frac{1}{2} η < 2 1 , hence Ψ ρ = τ 2 D − 1 = η τ 1 − 2 η S K − 1 \Psi_{\rho}=\frac{\tau}{2}D^{-1}=\frac{\eta\tau}{1-2\eta}S_K^{-1} Ψ ρ = 2 τ D − 1 = 1 − 2 η η τ S K − 1 and Ψ ′ = τ 2 H − 1 = η τ S K − 1 \Psi^{\prime}=\frac{\tau}{2}H^{-1}=\eta\tau S_K^{-1} Ψ ′ = 2 τ H − 1 = η τ S K − 1 . For (iii), H = 1 2 λ max ( S K ) I H=\frac{1}{2\lambda_{\max}(S_K)}I H = 2 λ m a x ( S K ) 1 I gives D = 1 2 λ max ( S K ) I − S K ≻ 0 D=\frac{1}{2\lambda_{\max}(S_K)}I-S_K\succ0 D = 2 λ m a x ( S K ) 1 I − S K ≻ 0 for η < 1 2 λ max ( S K ) \eta<\frac{1}{2\lambda_{\max}(S_K)} η < 2 λ m a x ( S K ) 1 , so Ψ ρ = τ ( η − 1 I − 2 S K ) − 1 \Psi_{\rho}=\tau(\eta^{-1}I-2S_K)^{-1} Ψ ρ = τ ( η − 1 I − 2 S K ) − 1 and Ψ ′ = η τ I \Psi^{\prime}=\eta\tau I Ψ ′ = η τ I . For (iv), the first claim is continuity of (8) in D D D . If a centred reference with scaled precision D ≻ 0 D\succ0 D ≻ 0 gave the step K − 2 η S K − 1 E K K-2\eta S_K^{-1}E_K K − 2 η S K − 1 E K , then for x x x with E K x ≠ 0 E_Kx\ne0 E K x = 0 the vector v : = 2 η S K − 1 E K x ≠ 0 v:=2\eta S_K^{-1}E_Kx\ne0 v := 2 η S K − 1 E K x = 0 would satisfy ( S K + D ) v = E K x = 1 − 2 η 2 η S K v (S_K+D)v=E_Kx=\frac{1-2\eta}{2\eta}S_Kv ( S K + D ) v = E K x = 2 η 1 − 2 η S K v , so v T D v = 1 − 2 η 2 η v T S K v ≤ 0 v^{\mathsf T}Dv=\frac{1-2\eta}{2\eta}v^{\mathsf T}S_Kv\leq0 v T D v = 2 η 1 − 2 η v T S K v ≤ 0 for η ≥ 1 2 \eta\geq\frac{1}{2} η ≥ 2 1 , which contradicts v T D v > 0 v^{\mathsf T}Dv>0 v T D v > 0 .
Lemma B.2 gives the fixed objective of Section IV: no iteration of KLPI increases J ϑ J_{\vartheta} J ϑ of (11). The majorization–minimization (MM) principle [17 ] decreases an objective F F F through a surrogate that lies above F F F and touches it at the current iterate, and a step that decreases the surrogate without minimizing it also does not increase F F F .
Lemma B.2 (Majorization and fixed objective). Let τ t = τ \tau_t=\tau τ t = τ , α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] , ϑ : = ( 1 − α ) τ \vartheta:= (1-\alpha)\tau ϑ := ( 1 − α ) τ , and iterate (9) with the true model from K 0 ∈ S K_0\in\mathcal{S} K 0 ∈ S , H 0 ≻ 0 H_0\succ0 H 0 ≻ 0 , and let π t : = N ( K t x , τ 2 H t − 1 ) \pi_t := \mathcal{N}(K_tx,\frac{\tau}{2}H_t^{-1}) π t := N ( K t x , 2 τ H t − 1 ) . For linear-Gaussian π \pi π as in (10) , with d π d_\pi d π the stationary state distribution of the closed loop under π \pi π , let
G t ( π ) : = J ϑ ( π ) + α τ E X ∼ d π [ κ π t π ( X ) ] . (28) G_t(\pi) := J_\vartheta(\pi) + \alpha\tau\mathbb{E}_{X\sim d_\pi}\left[\kappa_{\pi_t}^{\pi}(X)\right]. \tag*{(28)} G t ( π ) := J ϑ ( π ) + α τ E X ∼ d π [ κ π t π ( X ) ] . (28) (a) G t = J ρ t − τ log Z t G_t = J_{\rho_t} - \tau\log Z_t G t = J ρ t − τ log Z t with a constant Z t Z_t Z t that does not depend on π \pi π , G t ≥ J ϑ G_t\geq J_\vartheta G t ≥ J ϑ with equality at π t \pi_t π t , and
J ϑ ( π t + 1 ) ≤ G t ( π t + 1 ) ≤ G t ( π t ) = J ϑ ( π t ) . (29) J_\vartheta(\pi_{t+1}) \leq G_t(\pi_{t+1}) \leq G_t(\pi_t) = J_\vartheta(\pi_t). \tag*{(29)} J ϑ ( π t + 1 ) ≤ G t ( π t + 1 ) ≤ G t ( π t ) = J ϑ ( π t ) . (29) (b) In every state x x x , π t + 1 ( ⋅ ∣ x ) \pi_{t+1}(\cdot\mid x) π t + 1 ( ⋅ ∣ x ) minimizes E U ∼ μ [ Q π t ( x , U ) ] − ϑ h ( μ ) + α τ D K L ( μ ∥ π t ( ⋅ ∣ x ) ) \mathbb{E}_{U\sim\mu}[Q_{\pi_t}(x,U)]-\vartheta h(\mu)+\alpha\tau D_{\mathrm{KL}}(\mu\Vert\pi_t(\cdot\mid x)) E U ∼ μ [ Q π t ( x , U )] − ϑ h ( μ ) + α τ D KL ( μ ∥ π t ( ⋅ ∣ x )) over distributions μ \mu μ , which is the form of a policy mirror-descent step on the entropy-regularized cost [19 ] , [20 ] .
(c) For ϑ > 0 \vartheta>0 ϑ > 0 , among the linear-Gaussian policies of (10) , J ϑ J_\vartheta J ϑ has the unique minimizer N ( K ⋆ x , ϑ 2 ( S ⋆ ) − 1 ) \mathcal{N}(K^\star x,\frac{\vartheta}{2}(S^\star)^{-1}) N ( K ⋆ x , 2 ϑ ( S ⋆ ) − 1 ) .
Each iteration of KLPI is thus a generalized MM step: one policy improvement does not increase the surrogate G t G_t G t , although it need not minimize it. For α = 1 \alpha=1 α = 1 , J 0 = C ( K , Ψ ) J_0=C(K,\Psi) J 0 = C ( K , Ψ ) , and (29) is the average-cost counterpart of the finite-horizon majorization of [9 ] . The infimum C ⋆ C^\star C ⋆ of J 0 J_0 J 0 is approached only as Ψ → 0 \Psi\to0 Ψ → 0 , so (c) requires ϑ > 0 \vartheta>0 ϑ > 0 .
Proof of Lemma B.2: We first express G t G_t G t through the objective J ρ t J_{\rho_t} J ρ t of the policy improvement, then deduce (29) and (b) from Proposition 1, and finally minimize J ϑ J_\vartheta J ϑ in closed form. For a density μ \mu μ on R m \mathbb{R}^m R m and x x x fixed, write π t = π t ( ⋅ ∣ x ) \pi_t=\pi_t(\cdot\mid x) π t = π t ( ⋅ ∣ x ) and Z t : = ∫ π t ( u ) α d u Z_t:=\int\pi_t(u)^\alpha\,du Z t := ∫ π t ( u ) α d u , so that ρ t = π t α / Z t \rho_t=\pi_t^\alpha/Z_t ρ t = π t α / Z t ; for π t = N ( K t x , Ψ t ) \pi_t=\mathcal{N}(K_tx,\Psi_t) π t = N ( K t x , Ψ t ) , Z t Z_t Z t depends on Ψ t \Psi_t Ψ t and α \alpha α only. Since log ( μ / ρ t ) = α log ( μ / π t ) + ( 1 − α ) log μ + log Z t \log(\mu/\rho_t)=\alpha\log(\mu/\pi_t)+(1-\alpha)\log\mu+\log Z_t log ( μ / ρ t ) = α log ( μ / π t ) + ( 1 − α ) log μ + log Z t , averaging over U ∼ μ U\sim\mu U ∼ μ gives
τ D K L ( μ ∥ ρ t ) = α τ D K L ( μ ∥ π t ) − ϑ h ( μ ) + τ log Z t . (30) \tau D_{\mathrm{KL}}(\mu\Vert\rho_t)=\alpha\tau D_{\mathrm{KL}}(\mu\Vert\pi_t)-\vartheta h(\mu)+\tau\log Z_t. \tag*{(30)} τ D KL ( μ ∥ ρ t ) = α τ D KL ( μ ∥ π t ) − ϑ h ( μ ) + τ log Z t . (30)
For π = N ( K x , Ψ ) \pi=\mathcal{N}(Kx,\Psi) π = N ( K x , Ψ ) with K ∈ S K\in\mathcal{S} K ∈ S , h ( π ( ⋅ ∣ x ) ) = h ( N ( 0 , Ψ ) ) h(\pi(\cdot\mid x))=h(\mathcal{N}(0,\Psi)) h ( π ( ⋅ ∣ x )) = h ( N ( 0 , Ψ )) , which is 1 2 log det Ψ \frac{1}{2}\log\det\Psi 2 1 log det Ψ plus a constant that depends on m m m only, for every x x x , and κ π t π ( x ) \kappa_{\pi_t}^{\pi}(x) κ π t π ( x ) is a quadratic function of x x x plus a constant. Under P π \mathbb{P}^\pi P π the second moment of X t X_t X t converges to that of d π = N ( 0 , Σ K , Ψ ) d_\pi=\mathcal{N}(0,\Sigma_{K,\Psi}) d π = N ( 0 , Σ K , Ψ ) , Σ K , Ψ = Σ W + B Ψ B ⊤ + A K Σ K , Ψ A K ⊤ \Sigma_{K,\Psi}=\Sigma_W+B\Psi B^\top+A_K\Sigma_{K,\Psi}A_K^\top Σ K , Ψ = Σ W + B Ψ B ⊤ + A K Σ K , Ψ A K ⊤ , so every time average in (5) converges, and by (30) and Proposition 2, J ρ t ( π ) = G t ( π ) + τ log Z t J_{\rho_t}(\pi)=G_t(\pi)+\tau\log Z_t J ρ t ( π ) = G t ( π ) + τ log Z t . Since κ π t π t ≥ 0 \kappa_{\pi_t}^{\pi_t}\geq0 κ π t π t ≥ 0 , G t ≥ J ϑ G_t\geq J_\vartheta G t ≥ J ϑ , with equality at π = π t \pi=\pi_t π = π t . Next we prove (29) . By Proposition 4 with α t = α \alpha_t=\alpha α t = α , π t + 1 \pi_{t+1} π t + 1 is the policy improvement of π t \pi_t π t against ρ t \rho_t ρ t , and Proposition 1(c), applied with π = π t \pi=\pi_t π = π t and ρ = ρ t \rho=\rho_t ρ = ρ t , both centred at K t K_t K t , gives K t + 1 ∈ S K_{t+1}\in\mathcal{S} K t + 1 ∈ S and J ρ t ( π t + 1 ) ≤ J ρ t ( π t ) J_{\rho_t}(\pi_{t+1})\leq J_{\rho_t}(\pi_t) J ρ t ( π t + 1 ) ≤ J ρ t ( π t ) . Subtracting τ log Z t \tau\log Z_t τ log Z t from both sides gives G t ( π t + 1 ) ≤ G t ( π t ) G_t(\pi_{t+1})\leq G_t(\pi_t) G t ( π t + 1 ) ≤ G t ( π t ) , and the bound G t ≥ J ϑ G_t\geq J_\vartheta G t ≥ J ϑ with equality at π t \pi_t π t gives the two remaining relations of (29) . For (b), by (30) the objective of (b) equals that of (6) with the reference ρ t \rho_t ρ t minus the constant τ log Z t \tau\log Z_t τ log Z t , and the state-action value Q π t Q_{\pi_t} Q π t of (6) is Q K t + C ( K t ) Q_{K_t}+C(K_t) Q K t + C ( K t ) by Proposition 1(d), whatever the reference centred at K t K_t K t . Finally, we prove (c). By Proposition 2,
J ϑ = C ( K ) + Tr ( S K Ψ ) − ϑ 2 log det Ψ + c o n s t , J_\vartheta=C(K)+\operatorname{Tr}(S_K\Psi)-\frac{\vartheta}{2}\log\det\Psi+\mathrm{const}, J ϑ = C ( K ) + Tr ( S K Ψ ) − 2 ϑ log det Ψ + const ,
which is strictly convex in Ψ ≻ 0 \Psi\succ0 Ψ ≻ 0 with the unique minimizer Ψ = ϑ 2 S K − 1 \Psi=\frac{\vartheta}{2}S_K^{-1} Ψ = 2 ϑ S K − 1 and minimum C ( K ) + ϑ 2 log det S K + c o n s t C(K)+\frac{\vartheta}{2}\log\det S_K+\mathrm{const} C ( K ) + 2 ϑ log det S K + const . Both terms of this minimum are minimized at K ⋆ K^\star K ⋆ , the first uniquely by Lemma A.1, and the second because S K = R + B ⊤ P K B ⪰ S ⋆ S_K=R+B^\top P_KB\succeq S^\star S K = R + B ⊤ P K B ⪰ S ⋆ , since P K ⪰ P ⋆ P_K\succeq P^\star P K ⪰ P ⋆ for K ∈ S K\in\mathcal{S} K ∈ S by Lemma A.1. □ \square □
Appendix C: Proof of Theorem 1
The step is an instance of Lemma A.4 with the preconditioner M = H g + 1 − 1 M=H_{g+1}^{-1} M = H g + 1 − 1 , and the work lies in bounding the accumulated Hessian H g + 1 H_{g+1} H g + 1 , which sets the fraction of the gap removed per step. We first show that every step decreases the cost, then bound the accumulated Hessian, and finally treat the cases α < 1 \alpha<1 α < 1 and α = 1 \alpha=1 α = 1 . If K g ∈ S K_g\in\mathcal{S} K g ∈ S and H g ⪰ 0 H_g\succeq0 H g ⪰ 0 , then H g + 1 = α H g + S K g ⪰ S K g ≻ 0 H_{g+1}=\alpha H_g+S_{K_g}\succeq S_{K_g}\succ0 H g + 1 = α H g + S K g ⪰ S K g ≻ 0 , so M : = H g + 1 − 1 M:=H_{g+1}^{-1} M := H g + 1 − 1 satisfies M S K g M ⪰ M MS_{K_g}M\succeq M M S K g M ⪰ M , and Lemmas A.3 and A.4 with χ = 1 \chi=1 χ = 1 give K g + 1 ∈ S K_{g+1}\in\mathcal{S} K g + 1 ∈ S , the Lyapunov decrease, and
C ( K g + 1 ) − C ⋆ ≤ ( 1 − s λ max ( H g + 1 ) γ ⋆ ) ( C ( K g ) − C ⋆ ) . (31) C(K_{g+1})-C^\star\leq\left(1-\frac{s}{\lambda_{\max}(H_{g+1})\gamma^\star}\right)(C(K_g)-C^\star). \tag*{(31)} C ( K g + 1 ) − C ⋆ ≤ ( 1 − λ m a x ( H g + 1 ) γ ⋆ s ) ( C ( K g ) − C ⋆ ) . (31)
since ϰ ≥ λ min ( M ) s = s / λ max ( H g + 1 ) \varkappa\geq\lambda_{\min}(M)s=s/\lambda_{\max}(H_{g+1}) ϰ ≥ λ m i n ( M ) s = s / λ m a x ( H g + 1 ) . The regularization weights do not enter. Since K 0 ∈ S K_0\in\mathcal{S} K 0 ∈ S , H 0 ≻ 0 H_0\succ0 H 0 ≻ 0 and H g + 1 ⪰ S K g ≻ 0 H_{g+1}\succeq S_{K_g}\succ0 H g + 1 ⪰ S K g ≻ 0 , induction on g g g shows that K g ∈ S K_g\in\mathcal{S} K g ∈ S and P K g + 1 ⪯ P K g P_{K_{g+1}}\preceq P_{K_g} P K g + 1 ⪯ P K g for every g g g . Next we bound the accumulated Hessian. By P K k ⪯ P K 0 P_{K_k}\preceq P_{K_0} P K k ⪯ P K 0 and Lemma A.5, ∥ P K k ∥ ≤ ∥ P K 0 ∥ ≤ C ( K 0 ) / σ ( Σ W ) \lVert P_{K_k}\rVert\leq\lVert P_{K_0}\rVert\leq C(K_0)/\sigma(\Sigma_W) ∥ P K k ∥ ≤ ∥ P K 0 ∥ ≤ C ( K 0 ) / σ ( Σ W ) , so R ⪯ S K k ⪯ S ˉ R\preceq S_{K_k}\preceq\bar S R ⪯ S K k ⪯ S ˉ , and unrolling the recursion,
λ max ( H g + 1 ) ≤ α g + 1 ∥ H 0 ∥ + s ˉ ∑ k ≤ g α g − k . (32) \lambda_{\max}(H_{g+1})\leq\alpha^{g+1}\lVert H_0\rVert+\bar s\sum_{k\leq g}\alpha^{g-k}. \tag*{(32)} λ m a x ( H g + 1 ) ≤ α g + 1 ∥ H 0 ∥ + s ˉ k ≤ g ∑ α g − k . (32)
We now treat the two cases. For α < 1 \alpha<1 α < 1 , (32) gives H g ⪯ ( ∥ H 0 ∥ + s ˉ 1 − α ) I H_g\preceq\left(\lVert H_0\rVert+\frac{\bar s}{1-\alpha}\right)I H g ⪯ ( ∥ H 0 ∥ + 1 − α s ˉ ) I for all g g g , hence the floor on Ψ g = τ g 2 H g − 1 \Psi_g=\frac{\tau_g}{2}H_g^{-1} Ψ g = 2 τ g H g − 1 , and (31) gives the factor 1 − θ α 1-\theta_\alpha 1 − θ α , since θ α = s ( ( ∥ H 0 ∥ + s ˉ 1 − α ) γ ⋆ ) ≤ s ( λ max ( H g + 1 ) γ ⋆ ) \theta_\alpha=\frac{s}{((\lVert H_0\rVert+\frac{\bar s}{1-\alpha})\gamma^\star)}\leq\frac{s}{(\lambda_{\max}(H_{g+1})\gamma^\star)} θ α = ((∥ H 0 ∥ + 1 − α s ˉ ) γ ⋆ ) s ≤ ( λ m a x ( H g + 1 ) γ ⋆ ) s . Moreover, s / ( λ max ( H g + 1 ) γ ⋆ ) ≤ κ / γ ⋆ ≤ 1 s/(\lambda_{\max}(H_{g+1})\gamma^\star) \le\kappa/\gamma^\star\le1 s / ( λ m a x ( H g + 1 ) γ ⋆ ) ≤ κ / γ ⋆ ≤ 1 , by the bound on κ \kappa κ stated after (32) and by Lemma A.4 with χ = 1 \chi=1 χ = 1 ; hence θ α ≤ 1 \theta_\alpha\le1 θ α ≤ 1 . The gains stay in the compact set S ( C ( K 0 ) ) \mathcal{S}(C(K_0)) S ( C ( K 0 )) (Lemma A.5) and their costs tend to C ⋆ C^\star C ⋆ ; since K ⋆ K^\star K ⋆ is the only gain of cost C ⋆ C^\star C ⋆ (Lemma A.1) and C C C is continuous on S \mathcal{S} S , K g → K ⋆ K_g \to K^\star K g → K ⋆ , so S K g → S ⋆ S_{K_g} \to S^\star S K g → S ⋆ , and the affine recursion gives H g → S ⋆ 1 − α H_g \to\frac{S^\star}{1-\alpha} H g → 1 − α S ⋆ . For α = 1 \alpha=1 α = 1 , (33) gives λ max ( H g + 1 ) ≤ ∥ H 0 ∥ + ( g + 1 ) s ˉ = s ˉ ( c 1 + g ) \lambda_{\max}(H_{g+1}) \le\|H_0\|+(g+1)\bar{s}=\bar{s}(c_1+g) λ m a x ( H g + 1 ) ≤ ∥ H 0 ∥ + ( g + 1 ) s ˉ = s ˉ ( c 1 + g ) , so the factor in (32) is at most 1 − c 2 / ( c 1 + g ) 1-c_2/(c_1+g) 1 − c 2 / ( c 1 + g ) , with c 2 ≤ 1 ≤ c 1 c_2\le1\le c_1 c 2 ≤ 1 ≤ c 1 because γ ⋆ ≥ 1 \gamma^\star\ge1 γ ⋆ ≥ 1 and s ≤ s ˉ s\le\bar{s} s ≤ s ˉ , the latter since Q ⪯ P K 0 Q\preceq P_{K_0} Q ⪯ P K 0 . Then
∏ k < g ( 1 − c 2 c 1 + k ) ≤ exp ( − c 2 ∑ k < g 1 c 1 + k ) ≤ ( c 1 c 1 + g ) c 2 , (33) \prod_{k<g}\left(1-\frac{c_2}{c_1+k}\right)\le\exp\left(-c_2\sum_{k<g}\frac{1}{c_1+k}\right)\le\left(\frac{c_1}{c_1+g}\right)^{c_2}, \tag*{(33)} k < g ∏ ( 1 − c 1 + k c 2 ) ≤ exp − c 2 k < g ∑ c 1 + k 1 ≤ ( c 1 + g c 1 ) c 2 , (33)
since ∑ k < g 1 c 1 + k ≥ ∫ 0 g d y c 1 + y = log c 1 + g c 1 \sum_{k<g}\frac{1}{c_1+k}\ge\int_0^g\frac{dy}{c_1+y}=\log\frac{c_1+g}{c_1} ∑ k < g c 1 + k 1 ≥ ∫ 0 g c 1 + y d y = log c 1 c 1 + g . Finally R ⪯ S K k ⪯ s ˉ I R\preceq S_{K_k}\preceq\bar{s}I R ⪯ S K k ⪯ s ˉ I gives ( λ min ( H 0 ) + g λ min ( R ) ) I ⪯ H g ⪯ ( ∥ H 0 ∥ + g s ˉ ) I (\lambda_{\min}(H_0)+g\lambda_{\min}(R))I\preceq H_g\preceq(\|H_0\|+g\bar{s})I ( λ m i n ( H 0 ) + g λ m i n ( R )) I ⪯ H g ⪯ ( ∥ H 0 ∥ + g s ˉ ) I , which bounds Ψ g = τ g 2 H g − 1 \Psi_g=\frac{\tau_g}{2}H_g^{-1} Ψ g = 2 τ g H g − 1 on both sides. □
Appendix D: Proofs of Section V and Proposition 5
The proof of Theorem 2 follows the architecture of the proofs of [1 Theorems 1 and 3] and uses four facts, whose counterparts for Σ W = I n \Sigma_W=I_n Σ W = I n are in [1 ] .
Stability notions [1 , 5 ] : A gain K K K is ( b , ϵ ) (b,\epsilon) ( b , ϵ ) -strongly stable, b ≥ 1 b\ge1 b ≥ 1 , ϵ ∈ ( 0 , 1 ] \epsilon\in(0,1] ϵ ∈ ( 0 , 1 ] , if A K = G L G − 1 A_K=GLG^{-1} A K = G L G − 1 with G ≻ 0 G\succ0 G ≻ 0 , ∥ L ∥ ≤ 1 − ϵ \|L\|\le1-\epsilon ∥ L ∥ ≤ 1 − ϵ , ∥ G ∥ ≤ b \|G\|\le b ∥ G ∥ ≤ b , ∥ G − 1 ∥ ≤ 1 \|G^{-1}\|\le1 ∥ G − 1 ∥ ≤ 1 and ∥ K ∥ ≤ b \|K\|\le b ∥ K ∥ ≤ b . A sequence ( K t ) (K_t) ( K t ) is sequentially stable if every K t K_t K t is ( b , ϵ ) (b,\epsilon) ( b , ϵ ) -strongly stable with common constants through matrices G t G_t G t with ∥ G t + 1 − 1 G t ∥ ≤ 1 + ϵ / 2 \|G_{t+1}^{-1}G_t\|\le1+\epsilon/2 ∥ G t + 1 − 1 G t ∥ ≤ 1 + ϵ /2 .
Four facts: Let c ˉ : = C ( K t 0 ) + 2 \bar{c}:=C(K_{t_0})+2 c ˉ := C ( K t 0 ) + 2 . For K ∈ S ( c ˉ ) K\in\mathcal{S}(\bar{c}) K ∈ S ( c ˉ ) , the numbers ℓ P : = c ˉ / σ ( Σ W ) \ell_P:=\bar{c}/\sigma(\Sigma_W) ℓ P := c ˉ / σ ( Σ W ) , ℓ Σ : = c ˉ / σ ( Q ) \ell_\Sigma:=\bar{c}/\sigma(Q) ℓ Σ := c ˉ / σ ( Q ) , ℓ K : = ( c ˉ / ( σ ( R ) σ ( Σ W ) ) ) 1 / 2 \ell_K:=\left(\bar{c}/(\sigma(R)\sigma(\Sigma_W))\right)^{1/2} ℓ K := ( c ˉ / ( σ ( R ) σ ( Σ W )) ) 1/2 and ℓ A : = ( ℓ P / σ ( Q ) ) 1 / 2 \ell_A:=(\ell_P/\sigma(Q))^{1/2} ℓ A := ( ℓ P / σ ( Q ) ) 1/2 bound ∥ P K ∥ \|P_K\| ∥ P K ∥ , ∥ Σ K ∥ \|\Sigma_K\| ∥ Σ K ∥ , ∥ K ∥ \|K\| ∥ K ∥ and ∥ A K ∥ \|A_K\| ∥ A K ∥ , the first three by Lemma A.5 and ∥ A K ∥ ≤ ℓ A \|A_K\|\le\ell_A ∥ A K ∥ ≤ ℓ A because σ ( Q ) ∥ A K v ∥ 2 ≤ v ⊤ A K ⊤ P K A K v ≤ v ⊤ P K v \sigma(Q)\|A_Kv\|^2\le v^\top A_K^\top P_KA_Kv\le v^\top P_Kv σ ( Q ) ∥ A K v ∥ 2 ≤ v ⊤ A K ⊤ P K A K v ≤ v ⊤ P K v for every v v v . They also satisfy ℓ P ≥ ∥ P K ∥ ≥ σ ( Q ) \ell_P\ge\|P_K\|\ge\sigma(Q) ℓ P ≥ ∥ P K ∥ ≥ σ ( Q ) and ℓ Σ ≥ ∥ Σ K ∥ ≥ σ ( Σ W ) \ell_\Sigma\ge\|\Sigma_K\|\ge\sigma(\Sigma_W) ℓ Σ ≥ ∥ Σ K ∥ ≥ σ ( Σ W ) . There are constants p 1 , p 2 , p 4 , p 5 , p 6 , p 9 > 0 p_1,p_2,p_4,p_5,p_6,p_9>0 p 1 , p 2 , p 4 , p 5 , p 6 , p 9 > 0 , numbered as their counterparts in [1 ] and given in the proofs that follow the facts, depending only on ( A , B , Q , R , Σ W , c ˉ ) (A,B,Q,R,\Sigma_W,\bar{c}) ( A , B , Q , R , Σ W , c ˉ ) , such that for every K ∈ S ( c ˉ ) K\in\mathcal{S}(\bar{c}) K ∈ S ( c ˉ ) the following hold, where, for each t ≥ t 0 t\ge t_0 t ≥ t 0 , a hat denotes an object computed on the plant estimate ( A ^ t , B ^ t ) (\hat{A}_t,\hat{B}_t) ( A ^ t , B ^ t ) (Fact F1 is applied at index t + 1 t+1 t + 1 to S ^ t \hat{S}_t S ^ t and E ^ t \hat{E}_t E ^ t of Algorithm 1, and at index t 0 t_0 t 0 to S ^ o f f \hat{S}_{\mathrm{off}} S ^ off ).
Fact F1 (Sensitivity to the plant estimate). Under Assumption 1, if S N R t ≥ 1 / p 2 \mathrm{SNR}_t\ge1/p_2 SNR t ≥ 1/ p 2 , then A ^ t + B ^ t K \hat{A}_t+\hat{B}_tK A ^ t + B ^ t K is Schur, ∥ P ^ K − P K ∥ ≤ p 1 / S N R t \|\hat{P}_K-P_K\|\le p_1/\mathrm{SNR}_t ∥ P ^ K − P K ∥ ≤ p 1 / SNR t and ∥ E ^ K − E K ∥ ≤ p 9 / S N R t \|\hat{E}_K-E_K\|\le p_9/\mathrm{SNR}_t ∥ E ^ K − E K ∥ ≤ p 9 / SNR t .
Fact F2 (Local Lipschitz continuity). If ∥ K ~ − K ∥ ≤ p 4 \|\widetilde{K}-K\|\le p_4 ∥ K − K ∥ ≤ p 4 , then K ~ ∈ S \widetilde{K}\in\mathcal{S} K ∈ S , ∥ Σ K ~ − Σ K ∥ ≤ p 5 ∥ K ~ − K ∥ \|\Sigma_{\widetilde{K}}-\Sigma_K\|\le p_5\|\widetilde{K}-K\| ∥ Σ K − Σ K ∥ ≤ p 5 ∥ K − K ∥ and ∣ C ( K ~ ) − C ( K ) ∣ ≤ p 6 ∥ K ~ − K ∥ |C(\widetilde{K})-C(K)|\le p_6\|\widetilde{K}-K\| ∣ C ( K ) − C ( K ) ∣ ≤ p 6 ∥ K − K ∥ .
Fact F3 (Uniform strong stability). K K K is ( ν 3 , ν 4 ) (\nu_3,\nu_4) ( ν 3 , ν 4 ) -strongly stable with G = ( Σ K / σ ( Σ W ) ) 1 / 2 \mathcal{G}=(\Sigma_K/\sigma(\Sigma_W))^{1/2} G = ( Σ K / σ ( Σ W ) ) 1/2 , ν 3 : = c ˉ / ( σ ( Σ W ) min ( σ ( Q ) , σ ( R ) ) ) 1 / 2 \nu_3:=\bar{c}/(\sigma(\Sigma_W)\min(\sigma(Q),\sigma(R)))^{1/2} ν 3 := c ˉ / ( σ ( Σ W ) min ( σ ( Q ) , σ ( R )) ) 1/2 and ν 4 : = 1 − ( 1 − ν 3 − 2 ) 1 / 2 \nu_4:=1-(1-\nu_3^{-2})^{1/2} ν 4 := 1 − ( 1 − ν 3 − 2 ) 1/2 .
Fact F4 (State bound). If K t ∈ S ( c ˉ ) K_t\in\mathcal{S}(\bar{c}) K t ∈ S ( c ˉ ) and ∥ Σ K t + 1 − 1 Σ K t ∥ ≤ 1 + ν 4 / 2 \|\Sigma_{K_{t+1}}^{-1}\Sigma_{K_t}\|\le1+\nu_4/2 ∥ Σ K t + 1 − 1 Σ K t ∥ ≤ 1 + ν 4 /2 for all t ≥ t 0 t\ge t_0 t ≥ t 0 , then ( K t ) (K_t) ( K t ) is sequentially stable and (12) holds for X t + 1 = A K t X t + B Ω t + W t X_{t+1}=A_{K_t}X_t+B\Omega_t+W_t X t + 1 = A K t X t + B Ω t + W t .
Proof of Fact F1: Let ξ : = 1 / S N R t \xi:=1/\mathrm{SNR}_t ξ := 1/ SNR t , L : = A K L:=A_K L := A K and L ′ : = A ^ t + B ^ t K L':=\hat{A}_t+\hat{B}_tK L ′ := A ^ t + B ^ t K . By [1 Lemma 1] , δ : = ∥ L ′ − L ∥ = ∥ [ ( B ^ t − B ) ( A ^ t − A ) ] [ K n ; I ] ∥ ≤ ( 1 + ℓ K ) ξ \delta:=\|L'-L\|=\|[(\hat{B}_t-B)\;(\hat{A}_t-A)] [K_n;I]\|\le(1+\ell_K)\xi δ := ∥ L ′ − L ∥ = ∥ [( B ^ t − B ) ( A ^ t − A )] [ K n ; I ] ∥ ≤ ( 1 + ℓ K ) ξ . Let p 2 : = σ ( Q ) / ( 2 ℓ P ( 1 + ℓ K ) ( 2 ℓ A + 1 ) ) p_2:=\sigma(Q)/(2\ell_P(1+\ell_K)(2\ell_A+1)) p 2 := σ ( Q ) / ( 2 ℓ P ( 1 + ℓ K ) ( 2 ℓ A + 1 )) and p 1 : = 2 ℓ P ( 1 + ℓ K ) / σ ( Q ) p_1:=2\ell_P(1+\ell_K)/\sigma(Q) p 1 := 2 ℓ P ( 1 + ℓ K ) / σ ( Q ) . If ξ ≤ p 2 \xi\le p_2 ξ ≤ p 2 , then δ ≤ σ ( Q ) / ( 2 ℓ P ( 2 ℓ A + 1 ) ) ≤ 1 / 2 \delta\le\sigma(Q)/(2\ell_P(2\ell_A+1))\le1/2 δ ≤ σ ( Q ) / ( 2 ℓ P ( 2 ℓ A + 1 )) ≤ 1/2 , so Lemma A.6 with P = P K P=P_K P = P K and Y = Y ′ = Q + K ⊤ R K ⪰ σ ( Q ) I Y=Y'=Q+K^\top RK\succeq\sigma(Q)I Y = Y ′ = Q + K ⊤ R K ⪰ σ ( Q ) I applies with β ≤ ℓ P δ ( 2 ℓ A + 1 ) ≤ σ ( Q ) / 2 \beta\le\ell_P\delta(2\ell_A+1)\le\sigma(Q)/2 β ≤ ℓ P δ ( 2 ℓ A + 1 ) ≤ σ ( Q ) /2 . Lemma A.6 shows that L ′ L' L ′ is Schur and gives ∥ P ^ K − P K ∥ ≤ 2 ℓ P σ ( Q ) ℓ P ( 2 ℓ A + 1 ) ( 1 + ℓ K ) ξ = p 1 ξ \|\hat{P}_K-P_K\|\le\frac{2\ell_P}{\sigma(Q)}\ell_P(2\ell_A+1)(1+\ell_K)\xi=p_1\xi ∥ P ^ K − P K ∥ ≤ σ ( Q ) 2 ℓ P ℓ P ( 2 ℓ A + 1 ) ( 1 + ℓ K ) ξ = p 1 ξ . Since E K = R K + B ⊤ P K A K E_K=RK+B^\top P_KA_K E K = R K + B ⊤ P K A K and E ^ K = R K + B ^ t ⊤ P ^ K L ′ \hat{E}_K=RK+\hat{B}_t^\top\hat{P}_KL' E ^ K = R K + B ^ t ⊤ P ^ K L ′ ,
E ^ K − E K = ( B ^ t − B ) ⊤ P ^ K L ′ + B ⊤ ( P ^ K − P K ) L ′ + B ⊤ P K ( L ′ − L ) . \hat{E}_K-E_K=(\hat{B}_t-B)^\top\hat{P}_KL'+B^\top(\hat{P}_K-P_K)L'
+B^\top P_K(L'-L). E ^ K − E K = ( B ^ t − B ) ⊤ P ^ K L ′ + B ⊤ ( P ^ K − P K ) L ′ + B ⊤ P K ( L ′ − L ) .
and with ∥ B ^ t − B ∥ ≤ ξ \|\hat{B}_t-B\|\le\xi ∥ B ^ t − B ∥ ≤ ξ , ∥ P ^ K ∥ ≤ ℓ P + p 1 p 2 = 2 ℓ P \|\hat{P}_K\|\le\ell_P+p_1p_2=2\ell_P ∥ P ^ K ∥ ≤ ℓ P + p 1 p 2 = 2 ℓ P and ∥ L ′ ∥ ≤ ℓ A + 1 \|L'\|\le\ell_A+1 ∥ L ′ ∥ ≤ ℓ A + 1 , this gives ∥ E ^ K − E K ∥ ≤ p 9 ξ \|\hat{E}_K-E_K\|\le p_9\xi ∥ E ^ K − E K ∥ ≤ p 9 ξ with p 9 : = ( ℓ A + 1 ) ( 2 ℓ P + ∥ B ∥ p 1 ) + ∥ B ∥ ℓ P ( 1 + ℓ K ) p_9:=(\ell_A+1)(2\ell_P+\|B\|p_1)+\|B\|\ell_P(1+\ell_K) p 9 := ( ℓ A + 1 ) ( 2 ℓ P + ∥ B ∥ p 1 ) + ∥ B ∥ ℓ P ( 1 + ℓ K ) . For Σ W = I n \Sigma_W=I_n Σ W = I n , counterparts of the bounds on P ^ K \hat{P}_K P ^ K and E ^ K \hat{E}_K E ^ K appear in [7 Lemma 8] and [1 Lemmas 12 and 23] .
Proof of Fact F2: Let d : = ∥ K ~ − K ∥ ≤ p 4 d:=\|\widetilde{K}-K\|\le p_4 d := ∥ K − K ∥ ≤ p 4 with p 4 : = min { 1 , σ ( Q ) / ( 2 ℓ P ∥ B ∥ ( 2 ℓ A + 1 ) ) , σ ( Σ W ) / ( 2 ℓ Σ ∥ B ∥ ( 2 ℓ A + 1 ) ) } p_4:=\min\{1,\sigma(Q)/(2\ell_P\|B\|(2\ell_A+1)),\sigma(\Sigma_W)/(2\ell_\Sigma\|B\|(2\ell_A+1))\} p 4 := min { 1 , σ ( Q ) / ( 2 ℓ P ∥ B ∥ ( 2 ℓ A + 1 )) , σ ( Σ W ) / ( 2 ℓ Σ ∥ B ∥ ( 2 ℓ A + 1 ))} . Then δ : = ∥ A K ~ − A K ∥ ≤ ∥ B ∥ d ≤ 1 2 \delta:=\|A_{\widetilde{K}}-A_K\|\le\|B\|d\le\frac12 δ := ∥ A K − A K ∥ ≤ ∥ B ∥ d ≤ 2 1 , and ∥ K ~ ⊤ R K ~ − K ⊤ R K ∥ ≤ ∥ R ∥ ( 2 ℓ K + 1 ) d \|\widetilde{K}^{\top}R\widetilde{K}-K^\top RK\|\le\|R\|(2\ell_K+1)d ∥ K ⊤ R K − K ⊤ R K ∥ ≤ ∥ R ∥ ( 2 ℓ K + 1 ) d . Lemma A.6 with P = P K P=P_K P = P K , Y = Q + K ⊤ R K Y=Q+K^\top RK Y = Q + K ⊤ R K and Y ′ = Q + K ~ ⊤ R K ~ Y'=Q+\widetilde{K}^\top R\widetilde{K} Y ′ = Q + K ⊤ R K applies with β ≤ ℓ P ∥ B ∥ ( 2 ℓ A + 1 ) d ≤ σ ( Q ) / 2 \beta\le\ell_P\|B\|(2\ell_A+1)d\le\sigma(Q)/2 β ≤ ℓ P ∥ B ∥ ( 2 ℓ A + 1 ) d ≤ σ ( Q ) /2 , so K ~ ∈ S \widetilde{K}\in\mathcal{S} K ∈ S and
∥ P ~ K − P K ∥ ≤ 2 ℓ P σ ( Q ) ( ∥ R ∥ ( 2 ℓ K + 1 ) + ℓ P ∥ B ∥ ( 2 ℓ A + 1 ) ) d . \|\widetilde{P}_K-P_K\|\le\frac{2\ell_P}{\sigma(Q)}\left(\|R\|(2\ell_K+1)+\ell_P\|B\|(2\ell_A+1)\right)d. ∥ P K − P K ∥ ≤ σ ( Q ) 2 ℓ P ( ∥ R ∥ ( 2 ℓ K + 1 ) + ℓ P ∥ B ∥ ( 2 ℓ A + 1 ) ) d .
Since ∣ C ( K ~ ) − C ( K ) ∣ = ∣ Tr ( ( P ~ K − P K ) Σ W ) ∣ ≤ Tr ( Σ W ) ∥ P ~ K − P K ∥ |C(\widetilde{K})-C(K)|=|\operatorname{Tr}((\widetilde{P}_K-P_K)\Sigma_W)|\le\operatorname{Tr}(\Sigma_W)\|\widetilde{P}_K-P_K\| ∣ C ( K ) − C ( K ) ∣ = ∣ Tr (( P K − P K ) Σ W ) ∣ ≤ Tr ( Σ W ) ∥ P K − P K ∥ , this gives the cost bound with p 6 : = 2 ℓ P Tr ( Σ W ) σ ( Q ) ( ∥ R ∥ ( 2 ℓ K + 1 ) + ℓ P ∥ B ∥ ( 2 ℓ A + 1 ) ) p_6:=\frac{2\ell_P\operatorname{Tr}(\Sigma_W)}{\sigma(Q)}\left(\|R\|(2\ell_K+1)+\ell_P\|B\|(2\ell_A+1)\right) p 6 := σ ( Q ) 2 ℓ P Tr ( Σ W ) ( ∥ R ∥ ( 2 ℓ K + 1 ) + ℓ P ∥ B ∥ ( 2 ℓ A + 1 ) ) . The transposed form of Lemma A.6 with $P=\Sigma_K and Y = Y ′ = Σ W Y = Y' = \Sigma_W Y = Y ′ = Σ W applies with β ≤ ℓ Σ ∥ B ∥ ( 2 ℓ A + 1 ) d ≤ σ ( Σ W ) 2 \beta\le\ell_\Sigma\lVert B\rVert(2\ell_A + 1)d \le\frac{\sigma(\Sigma_W)}{2} β ≤ ℓ Σ ∥ B ∥ ( 2 ℓ A + 1 ) d ≤ 2 σ ( Σ W ) and gives the covariance bound with p 5 : = 2 ℓ Σ 2 ∥ B ∥ ( 2 ℓ A + 1 ) / σ ( Σ W ) p_5 := 2\ell_\Sigma^2\lVert B\rVert(2\ell_A + 1)/\sigma(\Sigma_W) p 5 := 2 ℓ Σ 2 ∥ B ∥ ( 2 ℓ A + 1 ) / σ ( Σ W ) . For Σ W = I n \Sigma_W = I_n Σ W = I n , the counterpart of Fact F2 is [1 Lemma 13] .
Proofs of Facts F3 and F4: Fact F3 repeats the argument of [1 ] , [5 ] : by the Lyapunov equation, L : = Σ K − 1 / 2 A K Σ K 1 / 2 L := \Sigma_K^{-1/2}A_K\Sigma_K^{1/2} L := Σ K − 1/2 A K Σ K 1/2 satisfies L L ⊤ = I n − Σ K − 1 / 2 Σ W Σ K − 1 / 2 ⪯ ( 1 − σ ( Σ W ) / ∥ Σ K ∥ ) I n LL^\top= I_n - \Sigma_K^{-1/2}\Sigma_W\Sigma_K^{-1/2} \preceq(1 - \sigma(\Sigma_W)/\lVert\Sigma_K\rVert)I_n L L ⊤ = I n − Σ K − 1/2 Σ W Σ K − 1/2 ⪯ ( 1 − σ ( Σ W ) / ∥ Σ K ∥) I n , so Lemma A.5 gives ∥ L ∥ 2 ≤ 1 − ν 3 − 2 \lVert L\rVert^2 \le1-\nu_3^{-2} ∥ L ∥ 2 ≤ 1 − ν 3 − 2 , that is, ∥ L ∥ ≤ 1 − ν 4 \lVert L\rVert\le1-\nu_4 ∥ L ∥ ≤ 1 − ν 4 , while Σ K ⪰ σ ( Σ W ) I n \Sigma_K \succeq\sigma(\Sigma_W)I_n Σ K ⪰ σ ( Σ W ) I n gives ∥ G − 1 ∥ ≤ 1 \lVert G^{-1}\rVert\le1 ∥ G − 1 ∥ ≤ 1 , and Lemma A.5 gives ∥ G ∥ ≤ ν 3 \lVert G\rVert\le\nu_3 ∥ G ∥ ≤ ν 3 and ∥ K ∥ ≤ ν 3 \lVert K\rVert\le\nu_3 ∥ K ∥ ≤ ν 3 , and ν 3 ≥ 1 \nu_3 \ge1 ν 3 ≥ 1 because c ˉ ≥ C ( K ) ≥ Tr ( Q Σ W ) ≥ σ ( Q ) σ ( Σ W ) \bar c \ge C(K) \ge\operatorname{Tr}(Q\Sigma_W) \ge\sigma(Q)\sigma(\Sigma_W) c ˉ ≥ C ( K ) ≥ Tr ( Q Σ W ) ≥ σ ( Q ) σ ( Σ W ) . Fact F4 uses G t = ( Σ K t / σ ( Σ W ) ) 1 / 2 G_t = (\Sigma_{K_t}/\sigma(\Sigma_W))^{1/2} G t = ( Σ K t / σ ( Σ W ) ) 1/2 and ∥ G t + 1 − 1 G t ∥ 2 = λ max ( Σ K t + 1 − 1 / 2 Σ K t Σ K t + 1 − 1 / 2 ) ≤ ∥ Σ K t + 1 − 1 Σ K t ∥ \lVert G_{t+1}^{-1}G_t\rVert^2 = \lambda_{\max}(\Sigma_{K_{t+1}}^{-1/2}\Sigma_{K_t}\Sigma_{K_{t+1}}^{-1/2}) \le\lVert\Sigma_{K_{t+1}}^{-1}\Sigma_{K_t}\rVert ∥ G t + 1 − 1 G t ∥ 2 = λ m a x ( Σ K t + 1 − 1/2 Σ K t Σ K t + 1 − 1/2 ) ≤ ∥ Σ K t + 1 − 1 Σ K t ∥ , with 1 + x ≤ 1 + x \sqrt{1+x} \le1+x 1 + x ≤ 1 + x ; the state bound is then the argument of [5 Lemma 3] reproduced in [1 ] .
The proof of Theorem 2 is an induction on t t t that keeps the gain in S ( c ˉ ) S(\bar c) S ( c ˉ ) and H t H_t H t in the band of (C3). Lemma D.1 bounds the estimated input Hessian of every gain in S ( c ˉ ) S(\bar c) S ( c ˉ ) , and Lemma D.2 uses this bound to carry out one step of the induction.
Constants: Let p ˉ : = c ˉ / σ ( Σ W ) + p 1 p 2 \bar p := \bar c/\sigma(\Sigma_W) + p_1p_2 p ˉ := c ˉ / σ ( Σ W ) + p 1 p 2 , b ˉ : = ∥ B ∥ + p 2 \bar b := \lVert B\rVert+ p_2 b ˉ := ∥ B ∥ + p 2 , s ˉ a : = ∥ R ∥ + b ˉ 2 p ˉ \bar s_a := \lVert R\rVert+ \bar b^2\bar p s ˉ a := ∥ R ∥ + b ˉ 2 p ˉ , r 0 : = s / ( 2 s ˉ a γ ⋆ ) r_0 := s/(2\bar s_a\gamma^\star) r 0 := s / ( 2 s ˉ a γ ⋆ ) , p S : = b ˉ ( p ˉ + ∥ B ∥ p 1 ) + ∥ B ∥ c ˉ / σ ( Σ W ) p_S := \bar b(\bar p + \lVert B\rVert p_1) + \lVert B\rVert\bar c/\sigma(\Sigma_W) p S := b ˉ ( p ˉ + ∥ B ∥ p 1 ) + ∥ B ∥ c ˉ / σ ( Σ W ) , ν 5 : = 2 p 6 p 9 / s \nu_5 := 2p_6p_9/s ν 5 := 2 p 6 p 9 / s , ν 1 : = max { 1 / p 2 , 8 p S / s , 8 p 9 / ( s p 4 ) , 2 ν 5 / r 0 } \nu_1 := \max\{1/p_2, 8p_S/s, 8p_9/(sp_4), 2\nu_5/r_0\} ν 1 := max { 1/ p 2 , 8 p S / s , 8 p 9 / ( s p 4 ) , 2 ν 5 / r 0 } , p 8 : = sup K ∈ S ( c ˉ ) ∥ E K ∥ + p 9 p 2 p_8 := \sup_{K\in S(\bar c)}\lVert E_K\rVert+ p_9p_2 p 8 := sup K ∈ S ( c ˉ ) ∥ E K ∥ + p 9 p 2 , finite by Lemma A.5, and ν 2 : = s 2 min { p 4 / p 8 , σ ( Σ W ) ν 4 / ( 4 ν 3 p 5 p 8 ) } \nu_2 := \frac{s}{2}\min\{p_4/p_8, \sigma(\Sigma_W)\nu_4/(4\nu_3p_5p_8)\} ν 2 := 2 s min { p 4 / p 8 , σ ( Σ W ) ν 4 / ( 4 ν 3 p 5 p 8 )} . Since Q ⪯ P K Q \preceq P_K Q ⪯ P K and ∥ P K ∥ ≤ c ˉ / σ ( Σ W ) \lVert P_K\rVert\le\bar c/\sigma(\Sigma_W) ∥ P K ∥ ≤ c ˉ / σ ( Σ W ) on S ( c ˉ ) S(\bar c) S ( c ˉ ) (Lemma A.5), s ≤ ∥ R ∥ + ∥ B ∥ 2 c ˉ / σ ( Σ W ) ≤ s ˉ a s \le\lVert R\rVert+ \lVert B\rVert^2\bar c/\sigma(\Sigma_W) \le\bar s_a s ≤ ∥ R ∥ + ∥ B ∥ 2 c ˉ / σ ( Σ W ) ≤ s ˉ a , and with γ ⋆ ≥ 1 \gamma^\star\ge1 γ ⋆ ≥ 1 this gives r 0 ≤ 1 2 r_0 \le\frac{1}{2} r 0 ≤ 2 1 .
Lemma D.1 (Band of the estimated input Hessian). Let Assumption 1 hold. For every k ≥ t 0 k \ge t_0 k ≥ t 0 with SNR k ≥ ν 1 \operatorname{SNR}_k \ge\nu_1 SNR k ≥ ν 1 and every K ∈ S ( c ˉ ) K \in S(\bar c) K ∈ S ( c ˉ ) , the input Hessian S ^ \hat S S ^ of K K K on Θ ^ k \hat\Theta_k Θ ^ k is well defined, ∥ S ^ − S K ∥ ≤ s 8 \lVert\hat S-S_K\rVert\le\frac{s}{8} ∥ S ^ − S K ∥ ≤ 8 s and s 2 I ⪯ S ^ ⪯ s ˉ a I \frac{s}{2}I \preceq\hat S \preceq\bar s_aI 2 s I ⪯ S ^ ⪯ s ˉ a I .
Proof of Lemma D.1: Write ξ : = SNR k − 1 \xi:= \operatorname{SNR}_k^{-1} ξ := SNR k − 1 , which is at most 1 / ν 1 1/\nu_1 1/ ν 1 by the hypothesis SNR k ≥ ν 1 \operatorname{SNR}_k \ge\nu_1 SNR k ≥ ν 1 , and write S : = S K S := S_K S := S K , ( A , B ^ ) : = ( A ^ k , B ^ k ) (A,\hat B) := (\hat A_k,\hat B_k) ( A , B ^ ) := ( A ^ k , B ^ k ) , and P ^ \hat P P ^ , S ^ \hat S S ^ for the objects of K K K on ( A ^ , B ^ ) (\hat A,\hat B) ( A ^ , B ^ ) . Since SNR k ≥ ν 1 ≥ 1 / p 2 \operatorname{SNR}_k \ge\nu_1 \ge1/p_2 SNR k ≥ ν 1 ≥ 1/ p 2 , Fact F1 at index k k k shows that A ^ + B ^ K \hat A+\hat B K A ^ + B ^ K is Schur, so P ^ \hat P P ^ and S ^ \hat S S ^ are well defined, and that ∥ P ^ − P K ∥ ≤ p 1 ξ \lVert\hat P-P_K\rVert\le p_1\xi ∥ P ^ − P K ∥ ≤ p 1 ξ . With Lemma A.5 this gives ∥ P ^ ∥ ≤ p ˉ \lVert\hat P\rVert\le\bar p ∥ P ^ ∥ ≤ p ˉ , and [1 Lemma 1] gives ∥ B ^ − B ∥ ≤ ∥ Θ ^ k − Θ ∥ ≤ ξ ≤ p 2 \lVert\hat B-B\rVert\le\lVert\hat\Theta_k-\Theta\rVert\le\xi\le p_2 ∥ B ^ − B ∥ ≤ ∥ Θ ^ k − Θ ∥ ≤ ξ ≤ p 2 , so ∥ B ^ ∥ ≤ b ˉ \lVert\hat B\rVert\le\bar b ∥ B ^ ∥ ≤ b ˉ . The difference S ^ − S \hat S-S S ^ − S decomposes as
S ^ − S = ( B ^ − B ) ⊤ P ^ B ^ + B ⊤ ( P ^ − P K ) B ^ + B ⊤ P K ( B ^ − B ) (34) \hat S-S=(\hat B-B)^\top\hat P\hat B+B^\top(\hat P-P_K)\hat B+B^\top P_K(\hat B-B) \tag*{(34)} S ^ − S = ( B ^ − B ) ⊤ P ^ B ^ + B ⊤ ( P ^ − P K ) B ^ + B ⊤ P K ( B ^ − B ) (34)
and, since ∥ B ^ − B ∥ ≤ ξ \lVert\hat B-B\rVert\le\xi ∥ B ^ − B ∥ ≤ ξ , ∥ B ^ ∥ ≤ b ˉ \lVert\hat B\rVert\le\bar b ∥ B ^ ∥ ≤ b ˉ , ∥ P ^ ∥ ≤ p ˉ \lVert\hat P\rVert\le\bar p ∥ P ^ ∥ ≤ p ˉ , ∥ P ^ − P K ∥ ≤ p 1 ξ \lVert\hat P-P_K\rVert\le p_1\xi ∥ P ^ − P K ∥ ≤ p 1 ξ and ∥ P K ∥ ≤ c ˉ / σ ( Σ W ) \lVert P_K\rVert\le\bar c/\sigma(\Sigma_W) ∥ P K ∥ ≤ c ˉ / σ ( Σ W ) , its norm is at most p S ξ p_S\xi p S ξ , which is at most s / 8 s/8 s /8 because ξ ≤ 1 / ν 1 ≤ s / ( 8 p S ) \xi\le1/\nu_1 \le s/(8p_S) ξ ≤ 1/ ν 1 ≤ s / ( 8 p S ) ; moreover ∥ S ^ ∥ ≤ ∥ R ∥ + b ˉ 2 p ˉ = s ˉ a \lVert\hat S\rVert\le\lVert R\rVert+\bar b^2\bar p=\bar s_a ∥ S ^ ∥ ≤ ∥ R ∥ + b ˉ 2 p ˉ = s ˉ a . With S ⪰ s I S\succeq sI S ⪰ s I this gives s 2 I ⪯ S ^ ⪯ s ˉ a I \frac{s}{2}I\preceq\hat S\preceq\bar s_aI 2 s I ⪯ S ^ ⪯ s ˉ a I . □
Lemma D.2 (One step of Algorithm 1). Let Assumption 1 hold, let α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) satisfy (C1), let t ≥ t 0 t\ge t_0 t ≥ t 0 , and suppose that K t ∈ S ( c ˉ ) K_t\in S(\bar c) K t ∈ S ( c ˉ ) , s 2 ( 1 − α ) I ⪯ H t ⪯ s ˉ a 1 − α I \frac{s}{2(1-\alpha)}I\preceq H_t\preceq\frac{\bar s_a}{1-\alpha}I 2 ( 1 − α ) s I ⪯ H t ⪯ 1 − α s ˉ a I and SNR t + 1 ≥ ν 1 \operatorname{SNR}_{t+1}\ge\nu_1 SNR t + 1 ≥ ν 1 . Then S ^ t \hat S_t S ^ t and E ^ t \hat E_t E ^ t are well defined, and the following hold.
(i) s 2 I ⪯ S ^ t ⪯ s ˉ a I \frac{s}{2}I\preceq\hat S_t\preceq\bar s_aI 2 s I ⪯ S ^ t ⪯ s ˉ a I , s 2 ( 1 − α ) I ⪯ H t + 1 ⪯ s ˉ a 1 − α I \frac{s}{2(1-\alpha)}I\preceq H_{t+1}\preceq\frac{\bar s_a}{1-\alpha}I 2 ( 1 − α ) s I ⪯ H t + 1 ⪯ 1 − α s ˉ a I .
(ii) K t + 1 ∈ S ( c ˉ ) K_{t+1}\in S(\bar c) K t + 1 ∈ S ( c ˉ ) and C ( K t + 1 ) − C ⋆ ≤ q α ( C ( K t ) − C ⋆ ) + ( 1 − α ) ν 5 SNR t + 1 − 1 C(K_{t+1})-C^\star\le q_\alpha(C(K_t)-C^\star)+(1-\alpha)\nu_5\operatorname{SNR}_{t+1}^{-1} C ( K t + 1 ) − C ⋆ ≤ q α ( C ( K t ) − C ⋆ ) + ( 1 − α ) ν 5 SNR t + 1 − 1 .
(iii) ∥ Σ K t + 1 − 1 Σ K t ∥ ≤ 1 + ν 4 / 2 \lVert\Sigma_{K_{t+1}}^{-1}\Sigma_{K_t}\rVert\le1+\nu_4/2 ∥ Σ K t + 1 − 1 Σ K t ∥ ≤ 1 + ν 4 /2 .
Proof of Lemma D.2: The computed step is compared with the exact step K ′ ′ : = K t − H t + 1 − 1 E K t K'' := K_t-H_{t+1}^{-1}E_{K_t} K ′′ := K t − H t + 1 − 1 E K t , which uses the computed preconditioner and the true slope and contracts the cost gap C ( K t ) − C ⋆ C(K_t)-C^\star C ( K t ) − C ⋆ by Lemma A.4 ; as in [1 ] , the difference of the two steps is bounded by a multiple of 1 / SNR t + 1 1/\operatorname{SNR}_{t+1} 1/ SNR t + 1 . Write ξ : = SNR t + 1 − 1 \xi:=\operatorname{SNR}_{t+1}^{-1} ξ := SNR t + 1 − 1 , which is at most 1 / ν 1 1/\nu_1 1/ ν 1 by the hypothesis SNR t + 1 ≥ ν 1 \operatorname{SNR}_{t+1}\ge\nu_1 SNR t + 1 ≥ ν 1 , and write S : = S K t S:=S_{K_t} S := S K t , E : = E K t E:=E_{K_t} E := E K t , ( A ^ , B ^ ) : = ( A ^ t + 1 , B ^ t + 1 ) (\hat A,\hat B):=(\hat A_{t+1},\hat B_{t+1}) ( A ^ , B ^ ) := ( A ^ t + 1 , B ^ t + 1 ) , and S ^ t \hat S_t S ^ t , E ^ t \hat E_t E ^ t for the objects of K t K_t K t on ( A ^ , B ^ ) (\hat A,\hat B) ( A ^ , B ^ ) .
We first prove (i). Since SNR t + 1 ≥ ν 1 ≥ 1 / p 2 \operatorname{SNR}_{t+1}\ge\nu_1\ge1/p_2 SNR t + 1 ≥ ν 1 ≥ 1/ p 2 , Fact F1 at index t + 1 t+1 t + 1 shows that A ^ + B ^ K t \hat A+\hat B K_t A ^ + B ^ K t is Schur, so S ^ t \hat S_t S ^ t and E ^ t \hat E_t E ^ t are well defined, and that ∥ E ^ t − E ∥ ≤ p 9 ξ \lVert\hat E_t-E\rVert\le p_9\xi ∥ E ^ t − E ∥ ≤ p 9 ξ . Lemma D.1 with k = t + 1 k=t+1 k = t + 1 and K = K t K=K_t K = K t , which applies since K t ∈ S ( c ˉ ) K_t\in S(\bar c) K t ∈ S ( c ˉ ) and SNR t + 1 ≥ ν 1 \operatorname{SNR}_{t+1}\ge\nu_1 SNR t + 1 ≥ ν 1 , gives ∥ S ^ t − S ∥ ≤ s / 8 \lVert\hat S_t-S\rVert\le s/8 ∥ S ^ t − S ∥ ≤ s /8 and s 2 I ⪯ S ^ t ⪯ s ˉ a I \frac{s}{2}I\preceq\hat S_t\preceq\bar s_aI 2 s I ⪯ S ^ t ⪯ s ˉ a I . Since α s 2 ( 1 − α ) + s 2 = s 2 ( 1 − α ) \frac{\alpha s}{2(1-\alpha)}+\frac{s}{2}=\frac{s}{2(1-\alpha)} 2 ( 1 − α ) α s + 2 s = 2 ( 1 − α ) s and α s ˉ a 1 − α + s ˉ a = s ˉ a 1 − α \alpha\frac{\bar s_a}{1-\alpha}+\bar s_a=\frac{\bar s_a}{1-\alpha} α 1 − α s ˉ a + s ˉ a = 1 − α s ˉ a , and the recursion H t + 1 = α H t + S ^ t H_{t+1}=\alpha H_t+\hat S_t H t + 1 = α H t + S ^ t keeps H t + 1 H_{t+1} H t + 1 in the band, which proves (i), M ^ t : = H t + 1 − 1 \hat M_t:=H_{t+1}^{-1} M ^ t := H t + 1 − 1 satisfies
∥ M t ∥ ≤ 2 ( 1 − α ) s , λ min ( M t ) ≥ 1 − α s ˉ a . (35) \lVert M_t\rVert\le\frac{2(1-\alpha)}{s},\qquad\lambda_{\min}(M_t)\ge\frac{1-\alpha}{\bar s_a}. \tag*{(35)} ∥ M t ∥ ≤ s 2 ( 1 − α ) , λ m i n ( M t ) ≥ s ˉ a 1 − α . (35)
We now prove (ii), and first show that the exact step K ′ ′ = K t − M t E K''=K_t-M_tE K ′′ = K t − M t E contracts the cost gap C ( K t ) − C ⋆ C(K_t)-C^\star C ( K t ) − C ⋆ . Since S ⪯ S ^ t + s 8 I ⪯ H t + 1 + s 8 I S\preceq\hat S_t+\frac{s}{8}I\preceq H_{t+1}+\frac{s}{8}I S ⪯ S ^ t + 8 s I ⪯ H t + 1 + 8 s I by Lemma D.1 and H t + 1 = α H t + S ^ t ⪰ S ^ t H_{t+1}=\alpha H_t+\hat S_t\succeq\hat S_t H t + 1 = α H t + S ^ t ⪰ S ^ t , and M t 2 ⪯ ∥ M t ∥ M t M_t^2\preceq\lVert M_t\rVert M_t M t 2 ⪯ ∥ M t ∥ M t ,
M t S M t ⪯ M t + s 8 M t 2 ⪯ ( 1 + s 8 ∥ M t ∥ ) M t ⪯ 3 2 M t . (36) M_tSM_t\preceq M_t+\frac{s}{8}M_t^2\preceq\left(1+\frac{s}{8}\lVert M_t\rVert\right)M_t\preceq\frac{3}{2}M_t. \tag*{(36)} M t S M t ⪯ M t + 8 s M t 2 ⪯ ( 1 + 8 s ∥ M t ∥ ) M t ⪯ 2 3 M t . (36)
Lemmas A.3 and A.4 with K = K t K=K_t K = K t , M = M t M=M_t M = M t and χ = 2 3 \chi=\frac{2}{3} χ = 3 2 give K ′ ′ ∈ S K''\in S K ′′ ∈ S , C ( K ′ ′ ) ≤ C ( K t ) C(K'')\le C(K_t) C ( K ′′ ) ≤ C ( K t ) and C ( K ′ ′ ) − C ⋆ ≤ ( 1 − 1 2 χ γ ⋆ ) ( C ( K t ) − C ⋆ ) C(K'')-C^\star\le(1-\frac{1}{2}\chi\gamma^\star)(C(K_t)-C^\star) C ( K ′′ ) − C ⋆ ≤ ( 1 − 2 1 χ γ ⋆ ) ( C ( K t ) − C ⋆ ) , and z ≥ λ min ( M t ) s ≥ ( 1 − α ) s / s ˉ a z\ge\lambda_{\min}(M_t)s\ge(1-\alpha)s/\bar s_a z ≥ λ m i n ( M t ) s ≥ ( 1 − α ) s / s ˉ a by (36) bounds this factor by 1 − ( 1 − α ) s 2 s ˉ a γ ⋆ = q α 1-\frac{(1-\alpha)s}{2\bar s_a\gamma^\star}=q_\alpha 1 − 2 s ˉ a γ ⋆ ( 1 − α ) s = q α .
Table III. Guarantees of indirect PGAC with the Gauss–Newton step [1 Theorems 1 and 4] and of KLPI (Theorem 2)
Constants with a tilde are those of [1 ] , which defines its cost with Σ W = I n \Sigma_W=I_n Σ W = I n , so C C C , C ⋆ C^\star C ⋆ and Σ ⋆ \Sigma^\star Σ ⋆ in the PGAC column are those of Σ W = I n \Sigma_W=I_n Σ W = I n . In both columns, S ^ t \hat{S}_t S ^ t and E ^ t \hat{E}_t E ^ t are the input Hessian and the slope of K t K_t K t on the plant estimate Θ ^ t + 1 \hat{\Theta}_{t+1} Θ ^ t + 1 . We read [1 Theorem 4] as replacing the condition η ≤ 2 ∥ Σ ⋆ ∥ / σ ( R ) \eta\leq2\lVert\Sigma^\star\rVert/\sigma(R) η ≤ 2 ∥ Σ ⋆ ∥ / σ ( R ) of [1 Theorem 1] by η < 2 ∥ Σ ⋆ ∥ \eta<2\lVert\Sigma^\star\rVert η < 2 ∥ Σ ⋆ ∥ .
We then show that the computed step K t + 1 = K t − M t E ^ t K_{t+1}=K_t-M_t\hat{E}_t K t + 1 = K t − M t E ^ t is a small change of the exact step K ′ ′ = K t − M t E K''=K_t-M_tE K ′′ = K t − M t E . The two steps differ by K t + 1 − K ′ ′ = − M t ( E ^ t − E ) K_{t+1}-K''=-M_t(\hat{E}_t-E) K t + 1 − K ′′ = − M t ( E ^ t − E ) , so (36) and ∥ E ^ t − E ∥ ≤ p 9 ξ \lVert\hat{E}_t-E\rVert\leq p_9\xi ∥ E ^ t − E ∥ ≤ p 9 ξ give
∥ K t + 1 − K ′ ′ ∥ = ∥ M t ( E ^ t − E ) ∥ ≤ 2 ( 1 − α ) s p 9 ξ ≤ p 4 2 , (37) \lVert K_{t+1}-K''\rVert=\lVert M_t(\hat{E}_t-E)\rVert\leq\frac{2(1-\alpha)}{s}p_9\xi\leq\frac{p_4}{2}, \tag*{(37)} ∥ K t + 1 − K ′′ ∥ = ∥ M t ( E ^ t − E )∥ ≤ s 2 ( 1 − α ) p 9 ξ ≤ 2 p 4 , (37)
where the last inequality uses ξ ≤ 1 / ν 1 ≤ s p 4 / ( 8 p 9 ) \xi\leq1/\nu_1\leq sp_4/(8p_9) ξ ≤ 1/ ν 1 ≤ s p 4 / ( 8 p 9 ) and 1 − α ≤ 1 1-\alpha\leq1 1 − α ≤ 1 . Since C ( K ′ ′ ) ≤ C ( K t ) ≤ c ˉ C(K'')\leq C(K_t)\leq\bar{c} C ( K ′′ ) ≤ C ( K t ) ≤ c ˉ , Fact F2, applied at K ′ ′ K'' K ′′ with K ~ = K t + 1 \widetilde{K}=K_{t+1} K = K t + 1 , gives K t + 1 ∈ S K_{t+1}\in\mathcal{S} K t + 1 ∈ S and ∣ C ( K t + 1 ) − C ( K ′ ′ ) ∣ ≤ p 6 ∥ K t + 1 − K ′ ′ ∥ ≤ ( 1 − α ) ν 5 ξ \lvert C(K_{t+1})-C(K'')\rvert\leq p_6\lVert K_{t+1}-K''\rVert\leq(1-\alpha)\nu_5\xi ∣ C ( K t + 1 ) − C ( K ′′ )∣ ≤ p 6 ∥ K t + 1 − K ′′ ∥ ≤ ( 1 − α ) ν 5 ξ , by (38) and ν 5 = 2 p 6 p 9 / s \nu_5=2p_6p_9/s ν 5 = 2 p 6 p 9 / s . Combining this bound with the contraction of the exact step gives
C ( K t + 1 ) − C ⋆ ≤ q α ( C ( K t ) − C ⋆ ) + ( 1 − α ) ν 5 SNR t + 1 − 1 . (38) C(K_{t+1})-C^\star\leq q_\alpha(C(K_t)-C^\star)+(1-\alpha)\nu_5\operatorname{SNR}_{t+1}^{-1}. \tag*{(38)} C ( K t + 1 ) − C ⋆ ≤ q α ( C ( K t ) − C ⋆ ) + ( 1 − α ) ν 5 SNR t + 1 − 1 . (38)
It remains to show that the cost stays below c ˉ \bar{c} c ˉ . Since ν 5 ξ ≤ r 0 / 2 \nu_5\xi\leq r_0/2 ν 5 ξ ≤ r 0 /2 by ξ ≤ 1 / ν 1 ≤ r 0 / ( 2 ν 5 ) \xi\leq1/\nu_1\leq r_0/(2\nu_5) ξ ≤ 1/ ν 1 ≤ r 0 / ( 2 ν 5 ) , and 1 − q α = ( 1 − α ) r 0 1-q_\alpha=(1-\alpha)r_0 1 − q α = ( 1 − α ) r 0 , subtracting C ( K t ) − C ⋆ C(K_t)-C^\star C ( K t ) − C ⋆ from both sides of (39) gives C ( K t + 1 ) − C ( K t ) ≤ ( 1 − α ) r 0 ( 1 2 − ( C ( K t ) − C ⋆ ) ) ≤ ( 1 − α ) r 0 ( 1 − ( C ( K t ) − C ⋆ ) ) C(K_{t+1})-C(K_t)\leq(1-\alpha)r_0(\frac{1}{2}-(C(K_t)-C^\star))\leq(1-\alpha)r_0(1-(C(K_t)-C^\star)) C ( K t + 1 ) − C ( K t ) ≤ ( 1 − α ) r 0 ( 2 1 − ( C ( K t ) − C ⋆ )) ≤ ( 1 − α ) r 0 ( 1 − ( C ( K t ) − C ⋆ )) . Hence the cost does not increase if C ( K t ) − C ⋆ ≥ 1 C(K_t)-C^\star\geq1 C ( K t ) − C ⋆ ≥ 1 , and otherwise C ( K t + 1 ) ≤ C ⋆ + 1 + r 0 ≤ c ˉ C(K_{t+1})\leq C^\star+1+r_0\leq\bar{c} C ( K t + 1 ) ≤ C ⋆ + 1 + r 0 ≤ c ˉ , since r 0 ≤ 1 2 r_0\leq\frac{1}{2} r 0 ≤ 2 1 and C ⋆ ≤ C ( K t 0 ) C^\star\leq C(K_{t_0}) C ⋆ ≤ C ( K t 0 ) . Thus K t + 1 ∈ S ( c ˉ ) K_{t+1}\in\mathcal{S}(\bar{c}) K t + 1 ∈ S ( c ˉ ) , which together with (39) proves (ii).
Finally, we prove (iii). By (C1), that is, 1 − α ≤ ν 2 1-\alpha\leq\nu_2 1 − α ≤ ν 2 , and by ∥ E ^ t ∥ ≤ ∥ E ∥ + p 9 ξ ≤ p 8 \lVert\hat{E}_t\rVert\leq\lVert E\rVert+p_9\xi\leq p_8 ∥ E ^ t ∥ ≤ ∥ E ∥ + p 9 ξ ≤ p 8 , the gain update K t + 1 − K t = − M t E ^ t K_{t+1}-K_t=-M_t\hat{E}_t K t + 1 − K t = − M t E ^ t satisfies
∥ K t + 1 − K t ∥ = ∥ M t E ^ t ∥ ≤ 2 ( 1 − α ) p 8 s ≤ min { p 4 , σ ( Σ W ) ν 4 4 ν 3 2 p 5 } , (39) \lVert K_{t+1}-K_t\rVert=\lVert M_t\hat{E}_t\rVert\leq\frac{2(1-\alpha)p_8}{s}\leq\min\left\{p_4,\frac{\sigma(\Sigma_W)\nu_4}{4\nu_3^2p_5}\right\}, \tag*{(39)} ∥ K t + 1 − K t ∥ = ∥ M t E ^ t ∥ ≤ s 2 ( 1 − α ) p 8 ≤ min { p 4 , 4 ν 3 2 p 5 σ ( Σ W ) ν 4 } , (39)
so Fact F2 gives ∥ Σ K t + 1 − Σ K t ∥ ≤ σ ( Σ W ) ν 4 / ( 4 ν 3 2 ) \lVert\Sigma_{K_{t+1}}-\Sigma_{K_t}\rVert\leq\sigma(\Sigma_W)\nu_4/(4\nu_3^2) ∥ Σ K t + 1 − Σ K t ∥ ≤ σ ( Σ W ) ν 4 / ( 4 ν 3 2 ) , and since Σ K t + 1 ⪯ σ ( Σ W ) I n \Sigma_{K_{t+1}}\preceq\sigma(\Sigma_W)I_n Σ K t + 1 ⪯ σ ( Σ W ) I n , ∥ Σ K t + 1 − 1 Σ K t ∥ ≤ 1 + ∥ Σ K t + 1 − Σ K t ∥ / σ ( Σ W ) ≤ 1 + ν 4 / 2 \lVert\Sigma_{K_{t+1}}^{-1}\Sigma_{K_t}\rVert\leq1+\lVert\Sigma_{K_{t+1}}-\Sigma_{K_t}\rVert/\sigma(\Sigma_W)\leq1+\nu_4/2 ∥ Σ K t + 1 − 1 Σ K t ∥ ≤ 1 + ∥ Σ K t + 1 − Σ K t ∥ / σ ( Σ W ) ≤ 1 + ν 4 /2 , since ν 3 ≥ 1 \nu_3\geq1 ν 3 ≥ 1 . □ \square □
Proof of Theorem 2: We show by induction on t ≥ t 0 t\geq t_0 t ≥ t 0 that K t ∈ S ( c ˉ ) K_t\in\mathcal{S}(\bar{c}) K t ∈ S ( c ˉ ) and s 2 ( 1 − α ) I ⪯ H t ⪯ s ˉ a 1 − α I \frac{s}{2(1-\alpha)}I\preceq H_t\preceq\frac{\bar{s}_a}{1-\alpha}I 2 ( 1 − α ) s I ⪯ H t ⪯ 1 − α s ˉ a I ; this induction hypothesis holds at t 0 t_0 t 0 by (C3) and C ( K t 0 ) < c ˉ C(K_{t_0})<\bar{c} C ( K t 0 ) < c ˉ . If the induction hypothesis holds at t t t , then (C2) gives SNR t + 1 ≥ ν 1 \operatorname{SNR}_{t+1}\geq\nu_1 SNR t + 1 ≥ ν 1 , and Lemma D.2(i) and (ii) give the induction hypothesis at t + 1 t+1 t + 1 . Hence Lemma D.2 applies at every t ≥ t 0 t\geq t_0 t ≥ t 0 , so S ^ t \hat{S}_t S ^ t and E ^ t \hat{E}_t E ^ t are well defined, and the bounds of Lemma D.2(ii) and (iii) hold at every t ≥ t 0 t\geq t_0 t ≥ t 0 . Facts F3 and F4 then give sequential stability and (12), and unrolling the cost bound of Lemma D.2(ii) from t 0 t_0 t 0 gives (13). For the last claim of Theorem 2, note that K t 0 ∈ S K_{t_0}\in\mathcal{S} K t 0 ∈ S , since K t 0 ∈ S K_{t_0}\in\mathcal{S} K t 0 ∈ S and C ( K t 0 ) < c ˉ C(K_{t_0})<\bar{c} C ( K t 0 ) < c ˉ . Lemma D.1 with k = t 0 k=t_0 k = t 0 and K = K t 0 K=K_{t_0} K = K t 0 , which applies by (C2), gives s 2 I ⪯ S ^ o f f ⪯ s ˉ a I \frac{s}{2}I\preceq\hat{S}_{\mathrm{off}}\preceq\bar{s}_aI 2 s I ⪯ S ^ off ⪯ s ˉ a I , so H t 0 = S ^ o f f 1 − α H_{t_0}=\frac{\hat{S}_{\mathrm{off}}}{1-\alpha} H t 0 = 1 − α S ^ off satisfies (C3). □ \square □
Comparison with PGAC: We compare Theorem 2 with the guarantee of [1 Theorems 1 and 4] for PGAC’s Gauss–Newton step and write both in the notation of this paper (Table III). KLPI’s gain update becomes this step when its preconditioner H t + 1 H_{t+1} H t + 1 is replaced by S ^ t / ( 1 − α ) \hat{S}_t/(1-\alpha) S ^ t / ( 1 − α ) , which gives the step size η = 1 − α 2 \eta=\frac{1-\alpha}{2} η = 2 1 − α . At this step size both guarantees state that the gains are sequentially stable, that the state is bounded by a decaying transient plus a multiple of the largest disturbance, and that the cost gap contracts linearly up to a discounted sum of 1 / SNR i 1/\operatorname{SNR}_i 1/ SNR i . The constants of the two guarantees come from different proofs, and we do not compare them. The two guarantees differ in four points. First, (C3) asks the initial preconditioner H t 0 H_{t_0} H t 0 to lie in the band in which the proof keeps H t H_t H t , and Theorem 2 shows that (C3) holds for H t 0 = S ^ o f f / ( 1 − α ) H_{t_0}=\widehat{S}_{\mathrm{off}}/(1-\alpha) H t 0 = S off / ( 1 − α ) under (C2). PGAC’s Gauss–Newton step uses the current estimated input Hessian alone and has no preconditioner to initialize. Second, the guaranteed decrease of the cost gap per sample differs by a constant factor. When Σ W = I n \Sigma_W=I_n Σ W = I n , the covariance with which [1 ] defines its cost, γ ⋆ = ∥ Σ ⋆ ∥ \gamma^\star=\lVert\Sigma^\star\rVert γ ⋆ = ∥ Σ ⋆ ∥ , and the decrease 1 − q α = ( 1 − α ) s 2 s ˉ a ∥ Σ ⋆ ∥ 1-q_\alpha=\frac{(1-\alpha)s}{2\bar{s}_a\lVert\Sigma^\star\rVert} 1 − q α = 2 s ˉ a ∥ Σ ⋆ ∥ ( 1 − α ) s of Theorem 2 is 2 s / s ˉ a 2s/\bar{s}_a 2 s / s ˉ a times the decrease 1 − ρ η = 1 − α 4 ∥ Σ ⋆ ∥ 1-\rho_\eta=\frac{1-\alpha}{4\lVert\Sigma^\star\rVert} 1 − ρ η = 4 ∥ Σ ⋆ ∥ 1 − α of [1 Theorem 4] . Third, the sum in (12) starts at i = t 0 + 1 i=t_0+1 i = t 0 + 1 , because Algorithm 1 computes its first gain K t 0 + 1 K_{t_0+1} K t 0 + 1 from the plant estimate Θ ^ t 0 + 1 \widehat{\Theta}_{t_0+1} Θ t 0 + 1 , whereas the sum in [1 Theorem 4] starts at i = t 0 i=t_0 i = t 0 . Finally, the condition η < 2 ∥ Σ ⋆ ∥ \eta<2\lVert\Sigma^\star\rVert η < 2 ∥ Σ ⋆ ∥ of [1 Theorem 4] has no counterpart in Theorem 2, and it holds at η = 1 − α 2 \eta=\frac{1-\alpha}{2} η = 2 1 − α , since Σ ⋆ ⪰ I n \Sigma^\star\succeq I_n Σ ⋆ ⪰ I n when Σ W = I n \Sigma_W=I_n Σ W = I n .
Proof of Proposition 5: By the Riccati equation P ⋆ = Q + A ⊤ P ⋆ A − A ⊤ P ⋆ B ( S ⋆ ) − 1 B ⊤ P ⋆ A P^\star=Q+A^\top P^\star A-A^\top P^\star B(S^\star)^{-1}B^\top P^\star A P ⋆ = Q + A ⊤ P ⋆ A − A ⊤ P ⋆ B ( S ⋆ ) − 1 B ⊤ P ⋆ A and C ⋆ = Tr ( P ⋆ Σ W ) C^\star=\operatorname{Tr}(P^\star\Sigma_W) C ⋆ = Tr ( P ⋆ Σ W ) , for all x , u x,u x , u ,
c ( x , u ) + E X ′ ∼ N ( A x + B u , Σ W ) [ X ′ ⊤ P ⋆ X ′ ] = x ⊤ P ⋆ x + C ⋆ + ( u − K ⋆ x ) ⊤ S ⋆ ( u − K ⋆ x ) . (40) \begin{aligned}
c(x,u)+\mathbb{E}_{X'\sim\mathcal{N}(Ax+Bu,\Sigma_W)}\left[X'^\top P^\star X'\right]
&=x^\top P^\star x+C^\star+(u-K^\star x)^\top S^\star(u-K^\star x). \tag*{(40)}
\end{aligned} c ( x , u ) + E X ′ ∼ N ( A x + B u , Σ W ) [ X ′⊤ P ⋆ X ′ ] = x ⊤ P ⋆ x + C ⋆ + ( u − K ⋆ x ) ⊤ S ⋆ ( u − K ⋆ x ) . (40)
Evaluating (40) at ( X t , U t ) (X_t,U_t) ( X t , U t ) , which is legitimate since W t W_t W t is independent of ( X t , U t ) (X_t,U_t) ( X t , U t ) , taking expectations under P \mathbb{P} P , which are finite by the moment hypotheses, and summing over t < T t<T t < T telescopes the terms in P ⋆ P^\star P ⋆ . With U t − K ⋆ X t = ( K t − K ⋆ ) X t + Ω t U_t-K^\star X_t=(K_t-K^\star)X_t+\Omega_t U t − K ⋆ X t = ( K t − K ⋆ ) X t + Ω t , the cross term vanishes because Ω t \Omega_t Ω t has zero mean given I t \mathcal{I}_t I t , which determines ( X t , K t , Ψ t ) (X_t,K_t,\Psi_t) ( X t , K t , Ψ t ) , and E P [ Ω t ⊤ S ⋆ Ω t ] = E P [ Tr ( S ⋆ Ψ t ) ] \mathbb{E}_{\mathbb{P}}[\Omega_t^\top S^\star\Omega_t]=\mathbb{E}_{\mathbb{P}}[\operatorname{Tr}(S^\star\Psi_t)] E P [ Ω t ⊤ S ⋆ Ω t ] = E P [ Tr ( S ⋆ Ψ t )] . □