A natural motivation for problems of the form (3) arises in system identification, where inputs are designed to make the collected data informative. Rather than injecting excitation naively, active experiment design shapes the information matrix in useful directions. Writing \( \theta=[A B]\) and \( x_{t+1}=\theta z_t+w_t\) , the weighted error of the least-squares estimate \( \widehat\theta\) , based on data with information matrix \( \Sigma_{\mathrm{data}}\mathrm{:=}\sum_t z_tz_t^\top\) , satisfies

where \( W\) encodes the parameter-error directions relevant to the downstream task and may be derived from the task cost and noise covariance [3, 2]. Thus, designing next experiment to reduce the task-weighted estimation error amounts to solving (3) with \( \Sigma_0\) equal to the information matrix of previously collected data.

We impose the following assumptions.

Part (ii) ensures that the budget constraint is strictly feasible. Note that \( b_0\) is itself the optimal value of a standard finite-horizon LQ problem (minimize the expected \( W^{(2)}\) -weighted energy) and is therefore computable.

A natural variant includes a control cost penalty:

with \( W^{(0)}\succeq0\) (e.g., \( W^{(0)}=\operatorname{blkdiag}(Q,R)\) ). The extra term is linear in \( \Sigma\) , so Lemma 2 holds with the same constants (\( L\) and \( m\) are unaffected), and the only change to the method is that the LMO gradient becomes \( M^{(i)}+W^{(0)}\) , making the stage weight in (14) equal to \( M^{(i)}+W^{(0)}+\lambda W^{(2)}\) . The budget constraint is retained to keep \( \mathcal{D}\) compact. For large \( \beta\) it is inactive, and (16) is effectively unconstrained. For \( W^{(2)}=W^{(0)}\) , for example, one could choose \( \beta\) as the energy \( \operatorname{Tr}\bigl(W^{(2)}\Sigma^{\pi}\bigr)\) attained by LQR controller with additive probing noise, which provides a loose upper bound on the objective.

Let \( 0<\tau_1<\dots<\tau_K=H\) and

The multi-horizon objective

promotes informativeness at intermediate times as well as at the end of the experiment. Frank–Wolfe now runs over the tuple \( (\Sigma_1^\pi,\dots,\Sigma_K^\pi)\) , whose achievable set is convex by the same mixing argument. The linearized objective is

with \( W_j\succ0\) and

Since the Riccati recursion (14) accommodates time-varying weights without modification, the LMO is again a generalized LQ problem, now with time-dependent stage weight \( \widehat M_t^{(i)}+\lambda W^{(2)}\) , with \( \lambda\) found by scalar bisection as before. The analysis of Theorem 1 applies to the sum objective on the product feasible set, with curvature bounded by the sum of the per-component bounds.

Recall from 2.1 that, for system identification, (3) can be used to reduce the task-weighted estimation error by taking \( \Sigma_0\) as the information matrix of previously collected data. Since \( (A,B)\) are unknown, we proceed episodically using certainty equivalence. At episode \( k\) , we form the least-squares estimate

where \( \Sigma^{(k)}\) and \( \bar\Sigma^{(k)}\) aggregate all data collected so far. We then solve (3) using the estimated dynamics and \( \Sigma_0=\Sigma^{(k)}\) for \( M\) Frank–Wolfe iterations, obtaining policies \( \pi^{(k,0)},\dots,\pi^{(k,M-1)}\) . Following Remark 1, we sample \( \pi^{(k,j)}\) with probability \( p_j=\tfrac{2(j+1)}{M(M+1)}\) , execute it on true system for \( H\) steps, update \( (\Sigma^{(k)},\bar\Sigma^{(k)})\) , and re-estimate the dynamics. Unlike [2, 3], which optimize over restricted classes such as periodic inputs, our method optimizes directly over covariances achievable by causal feedback policies. Related Frank–Wolfe approaches to experiment design appear in [4, 5].

Finally, the multi-horizon variant provides a computationally tractable approach to dual control. Naive exploration schemes [8] add tuned random noise to a certainty equivalent controller, an explicit dual control strategy [9, 10], while exact implicit formulations via hyperstates are intractable [11]. Related in spirit to our approach, the intrinsic-reward LQR algorithm of [12] promotes uncertainty-driven exploration by augmenting the certainty equivalent synthesis cost while retaining the structure of a standard LQR problem. The following control oriented experiment design lies between explicit and implicit dual control. At each update time \( \tau_k\) , the learner maintains a posterior \( \mathcal{N}\bigl(\operatorname{vec}(\hat\theta_k), \,\Lambda_k^{-1}\otimes\Sigma_w\bigr) \) over the vectorized parameters \( \theta=[A B]\) , where \( \Lambda_k\) is the regularized information matrix formed from the data collected so far. It then minimizes the certainty equivalent control cost plus a prediction of the excess cost that future certainty equivalent controllers will incur due to estimation error:

where \( \tau_{K+1}\mathrm{:=} T\) . The expectation is taken under the estimated dynamics \( \hat\theta_k\) with the initial state fixed to the current state \( x_{\tau_k}\) , and

is the covariance accumulated before the model is re-estimated at time \( \tau_m\) . The matrix \( H(\hat\theta_k)\in\mathbb{R}^{dn\times dn}\) is the model-task Hessian, the Hessian of the certainty equivalent control cost with respect to the vectorized model parameters [3]. Term \( m\) in (18) predicts, via a second-order expansion of the control cost in the model parameters, the excess cost of the certainty equivalent controller that will be synthesized at time \( \tau_m\) and deployed until \( \tau_{m+1}\) , since \( (\Lambda_k+\Sigma_m^\pi)^{-1}\otimes\Sigma_w\) approximates the parameter error covariance at that point.

To connect (18) with the preceding sections, view \( H(\hat\theta_k)\) as a \( d\times d\) array of \( n\times n\) blocks \( [H]_{(i,j)}\) , and define the partial trace \( \operatorname{Tr}_{\Sigma_w}(H)\in\mathbb{R}^{d\times d}\) entrywise by \( [\operatorname{Tr}_{\Sigma_w}(H)]_{ij} \mathrm{:=}\operatorname{Tr}\bigl(\Sigma_w[H]_{(i,j)}\bigr). \) A direct computation shows that, for any symmetric \( P\) ,

Thus, with \( W_m\mathrm{:=}\tfrac{1}{2}(\tau_{m+1}-\tau_m) \operatorname{Tr}_{\Sigma_w}\bigl(H(\hat\theta_k)\bigr), \) the penalty terms in (18) become \( \operatorname{Tr}\bigl(W_m(\Lambda_k+\Sigma_m^\pi)^{-1}\bigr)\) . Problem (18) is therefore the multi-horizon objective (17) with \( \Sigma_0=\Lambda_k\) , combined with an LQR term as in (16). Retaining a budget constraint over the remaining horizon as in the preceding sections, the Frank–Wolfe machinery applies verbatim. The LMO at iteration \( i\) is a generalized LQ problem with time-varying stage weights

where \( M_m^{(i)}=-(\Lambda_k+\Sigma_m^{(i)})^{-1}W_m(\Lambda_k+\Sigma_m^{(i)})^{-1}\) as in Section 5.2. The problem is re-solved at each update time in receding-horizon fashion, using the newly collected data to update \( \hat\theta\) and \( \Lambda\) . Compared to naive exploration, the probing energy is placed only in directions that matter for control, which can enable lower regret when the system structure permits it.

Pan/Zoom

Pan/Zoom

Pan/Zoom

We first solve (3) for the known system

with \( H=100\) , \( W^{(1)}=\operatorname{diag}(2.0,1.0,0.5)\) , and \( W^{(2)}=\operatorname{diag}(1.0,1.0,0.3)\) . We initialize with a feasible covariance from the fixed-\( \lambda\) LQ subproblem at \( \lambda=1\) , run the inner bisection to high accuracy, and perform \( 50\) Frank–Wolfe iterations for several budgets \( \beta\) . Figure 2 shows monotone convergence, consistent with the \( \mathcal{O}(1/M)\) rate of Theorem 1; larger budgets yield more informative covariances and lower limiting values. Every iterate is feasible by construction.

Next we run the episodic scheme of Section 5.3 on the same system with \( (A,B)\) unknown. We compare against three baselines, all normalized to the same energy budget per episode The budget constraint is enforced under the estimated dynamics and may therefore be violated under the true dynamics. If it is a hard constraint, it can be tightened by a margin that accounts for model uncertainty.:

1. (i) Certainty equivalence, which rolls out the LQ policy for the current estimate without seeking exploration;
2. (ii) Naive exploration, which applies random inputs; and
3. (iii) a frequency-search baseline based on [2], which selects the best periodic input for the current model estimate.

At each episode we record the estimation error \( \|\hat A^{(j)}-A\|_F+\|\hat B^{(j)}-B\|_F\) . Figures 3 and 4 show the estimation error and design objective across Monte Carlo noise realizations.

For the adaptive online LQR experiment, we use

We apply the receding-horizon scheme of Section 5.4, using the identity as a surrogate for the model-task Hessian \( H(\hat\theta)\) .

Pan/Zoom

Performance is measured by cumulative regret \( R_T^\pi=C_T^\pi-TJ^\star\) , where \( C_T^\pi\) is the cumulative LQR cost and \( J^\star\) is the optimal steady-state cost under the true dynamics. We compare against certainty-equivalent LQR with naive exploration noise and a sampling-based optimization using a large number of samples, which locally perturbs the certainty-equivalent gains and selects the best candidate under (18). The latter serves as a reference to verify that the Frank–Wolfe procedure achieves similar behavior. Figure 5 reports regret over 50 noise realizations. The Frank–Wolfe controller directs its exploration effort and achieves lower regret than the naive approach.

Convexity. Throughout, \( \langle X,Y\rangle=\operatorname{Tr}(X^\top Y)\) . Convexity of \( f\) follows since \( X\mapsto X^{-1}\) is matrix convex on the positive definite cone, \( \Sigma\mapsto\Sigma_0+\Sigma\) is affine, and \( \operatorname{Tr}(W^{(1)}\cdot)\) is linear and monotone. The gradient formula (4) is standard. Since \( \Sigma_0\succ0\) and \( \Sigma\succeq0\) , we have \( Y\mathrm{:=}(\Sigma_0+\Sigma)^{-1}\succ0\) . Thus, for every \( v\neq0\) , \( v^\top YW^{(1)}Yv=(Yv)^\top W^{(1)}(Yv)>0, \) because \( W^{(1)}\succ0\) and \( Yv\neq0\) . Hence \( YW^{(1)}Y\succ0\) , and therefore \( \nabla f(\Sigma)=-YW^{(1)}Y\prec0\) .

Smoothness. Fix \( \Sigma,\Sigma'\succeq0\) , let \( \Delta\mathrm{:=}\Sigma'-\Sigma\) , and define

Since \( \Sigma+\varepsilon\Delta=(1-\varepsilon)\Sigma+\varepsilon\Sigma'\succeq0\) , \( \|Y_\varepsilon\|_2\le\lambda_{\min}(\Sigma_0)^{-1}\) . Moreover, \( Y_\varepsilon'=-Y_\varepsilon\Delta Y_\varepsilon\) , so

Using \( \|XYZ\|_F\le\|X\|_2\|Y\|_F\|Z\|_2\) , we obtain

Therefore,

where \( L\) is given by (5).

Strong convexity. It suffices to show that, for every \( \Sigma\in\mathcal{D}\) and symmetric \( \Delta\) , \( \nabla^2 f(\Sigma)[\Delta,\Delta]\mathrm{:=}\left.\tfrac{\mathrm{d}^2}{\mathrm{d}t^2}f(\Sigma+t\Delta)\right|_{t=0}\ge m\|\Delta\|_F^2\) . Let \( Y\mathrm{:=}(\Sigma_0+\Sigma)^{-1}\) . Direct differentiation gives \( \nabla^2f(\Sigma)[\Delta,\Delta]=2\operatorname{Tr}\bigl(W^{(1)}Y\Delta Y\Delta Y\bigr)\) . Since

and \( W^{(1)}\succeq\lambda_{\min}(W^{(1)})I\) , we obtain

The final inequality follows from \( \|Y^{1/2}\Delta Y^{1/2}\|_F \ge\lambda_{\min}(Y)\|\Delta\|_F\) . By Lemma 1, \( \lambda_{\min}(Y)\ge\bigl(\lambda_{\max}(\Sigma_0)+\tfrac{\beta}{\mu}\bigr)^{-1}\) , yielding (6). \( \blacksquare\)

Recall that

Since \( \nabla f\) is \( L\) -Lipschitz, the descent lemma gives

Thus, by Lemma 1 and (5),

Let \( h_i\mathrm{:=} f(\Sigma^{(i)})-f(\Sigma^\star)\) and \( M^{(i)}\mathrm{:=}\nabla f(\Sigma^{(i)})\) . By the curvature bound, the \( \delta\) -approximate LMO, and convexity,

where \( \langle M^{(i)},\Sigma^\star-\Sigma^{(i)}\rangle\le-h_i\) . We prove by induction that \( h_i\le 2C_f/(i+2)+\delta\) for all \( i\ge1\) . Since \( \alpha_0=1\) , \( h_1\le\delta+C_f/2\le\delta+2C_f/3\) . Now, assume \( h_i\le 2C_f/(i+2)+\delta\) for some \( i\ge1\) . Substituting this bound and \( \alpha_i=2/(i+2)\) into the recursion gives

where the last inequality follows from \( (i+1)(i+3)\le(i+2)^2\) . Hence, by induction,

which proves (10). Finally, strong convexity and first-order optimality of \( \Sigma^\star\) give, for every \( \Sigma\in\mathcal{D}\) ,

Applying this at \( \Sigma=\Sigma^{(M)}\) and using (10) yields (11). \( \blacksquare\)

(i) First, every \( \lambda>\|M\|_2/\mu\) is admissible, which shows \( \lambda_{\mathrm{crit}}\le\|M\|_2/\mu\) . Indeed, for such \( \lambda\) the stage weight satisfies \( \widetilde M(\lambda)\succeq(\lambda\mu-\|M\|_2)I\succ0\) . The cost is then nonnegative, so backward induction gives \( P_t(\lambda)\succeq0\) for all \( t\) , and consequently \( S_t(\lambda)=\widetilde M^{uu}(\lambda)+B^\top P_{t+1}(\lambda)B\succ0\) .

Second, admissibility is preserved as \( \lambda\) increases. When \( S_t(\lambda)\succ0\) , the Riccati step (14) is the partial minimization

and the objective on the right is pointwise nondecreasing in \( \lambda\) , since its derivative in \( \lambda\) is \( z^\top W^{(2)}z\ge0\) , and in \( P_{t+1}\succeq 0\) . Let \( \lambda_1\in\Lambda\) and \( \lambda_2>\lambda_1\) , and induct backward from \( P_H(\lambda_1)=P_H(\lambda_2)=0\) . If \( P_{t+1}(\lambda_2)\succeq P_{t+1}(\lambda_1)\) , then \( S_t(\lambda_2)\succeq S_t(\lambda_1)+(\lambda_2-\lambda_1)W^{(2),uu}\succ0\) , so the minimization at \( \lambda_2\) is well posed, and minimizing the pointwise larger objective yields \( P_t(\lambda_2)\succeq P_t(\lambda_1)\) . Hence \( \lambda_2\in\Lambda\) . Finally, wherever all \( S_t(\lambda)\succ0\) the recursion depends continuously on \( \lambda\) , so \( \Lambda\) is open and therefore of the form \( (\lambda_{\mathrm{crit}},\infty)\) . Since \( S_{H-1}(\lambda)=M^{uu}+\lambda W^{(2),uu}\prec0\) for all sufficiently small \( \lambda\ge0\) , it follows that \( \lambda_{\mathrm{crit}}>0\) .

(ii) For \( \lambda\in\Lambda\) , all \( S_t(\lambda)\succ0\) , so the Riccati recursion (14) involves only sums, products, and inverses of matrices that depend continuously on \( \lambda\) . Hence the gains \( K_t(\lambda)\) , and therefore \( b(\lambda)\) through the covariance propagation following (15), are continuous in \( \lambda\) . For monotonicity, fix \( \lambda_1,\lambda_2\in\Lambda\) and define \( c_j\mathrm{:=}\operatorname{Tr}\bigl(M\Sigma^{\pi_{\lambda_j}}\bigr)\) and \( b_j\mathrm{:=} b(\lambda_j)\) . The cost of \( \pi_{\lambda_j}\) under \( \widetilde M(\lambda_i)\) is \( c_j+\lambda_i b_j\) . Since \( \pi_{\lambda_1}\) and \( \pi_{\lambda_2}\) are optimal for \( \lambda_1\) and \( \lambda_2\) , respectively,

Adding the two inequalities and cancelling \( c_1+c_2\) yields \( \lambda_1b_1+\lambda_2b_2 \le\lambda_1b_2+\lambda_2b_1, \) which is equivalent to \( (\lambda_2-\lambda_1)(b_2-b_1)\le0\) . Thus, \( \lambda_2>\lambda_1\) implies \( b(\lambda_2)\le b(\lambda_1)\) .

(iii) For \( \lambda\in\Lambda\) , \( \pi_\lambda\) attains \( v(\lambda)=\inf_{\pi\in\Pi}\operatorname{Tr}\bigl(\widetilde M(\lambda)\Sigma^{\pi}\bigr)\) . For any feasible \( \pi\) in (12),

The inequality follows from the definition of \( v(\lambda)\) and from feasibility, since \( \lambda\ge0\) implies \( -\lambda\operatorname{Tr}(W^{(2)}\Sigma^{\pi})\ge-\lambda\beta\) . Hence \( p^\star\ge v(\lambda)-\lambda\beta\) . Evaluating at \( \pi_\lambda\) gives

If \( b(\lambda)\le\beta\) , then \( \pi_\lambda\) is feasible. If \( b(\lambda)=\beta\) , the displayed bound gives \( \operatorname{Tr}(M\Sigma^{\pi_\lambda})\le p^\star\) . Feasibility gives the reverse inequality by the definition of \( p^\star\) ; hence equality holds, and \( \pi_\lambda\) solves (12).

(iv) We first upper bound \( v(\lambda)\) . Let \( \pi_e\in\operatorname*{arg\,min}_{\pi\in\Pi}\operatorname{Tr}\bigl(W^{(2)}\Sigma^{\pi}\bigr)\) , so that \( \operatorname{Tr}\bigl(W^{(2)}\Sigma^{\pi_e}\bigr)=b_0\) . Since \( M\prec0\) and \( \Sigma^{\pi_e}\succeq0\) , we have \( \operatorname{Tr}\bigl(M\Sigma^{\pi_e}\bigr)\le0\) . Using \( \pi_e\) as a candidate policy in the definition of \( v(\lambda)\) ,

We next lower bound \( v(\lambda)\) in terms of \( b(\lambda)\) . Any \( \Sigma\succeq0\) satisfies \( \operatorname{Tr}(M\Sigma)\ge-\|M\|_2\operatorname{Tr}(\Sigma)\) and \( \operatorname{Tr}(\Sigma)\le\operatorname{Tr}\bigl(W^{(2)}\Sigma\bigr)/\mu\) . Applying both bounds to \( \Sigma^{\pi_\lambda}\)

Now take \( \lambda>\|M\|_2/\mu\) , which is admissible by (i). Chaining the two bounds on \( v(\lambda)\) and dividing by \( \lambda-\|M\|_2/\mu>0\) yields \( b(\lambda)\le\tfrac{\lambda b_0}{\lambda-\|M\|_2/\mu}. \) The right hand side is at most \( \beta\) if and only if \( \lambda b_0\le\beta\lambda-\beta\|M\|_2/\mu\) , which rearranges to \( \lambda(\beta-b_0)\ge\beta\|M\|_2/\mu\) . Since \( \beta>b_0\) by Assumption 1(ii), this holds exactly when \( \lambda\ge\bar\lambda\) . \( \blacksquare\)