1 Introduction↩︎

Adaptive control studies controllers that can adapt to or learn unmodelled changes in the dynamics [1]. Adaptive controllers often guarantee perfect asymptotic tracking or regulation, and parameter convergence [2], [3]. Concurrently with the developments in adaptive control, the theory of online optimization was established to minimize an a priori unknown, sequentially revealed cost [4]. The connections between the two have recently been highlighted [5], [6], showing that adaptive controllers are closely linked to an online cost optimization problem and are often proportional to an online estimation cost gradient. In this work, we consider adaptive controllers that aim to minimize a cost function while controlling the system [7]. Given such a controller, we note that asymptotic stability alone does not automatically provide performance guarantees on the cost [8], [9]. Instead, we provide finite-time guarantees by characterizing the regret [4] of our adaptive controller, a concept borrowed from online learning to quantify the additional cost incurred by the controller over a horizon due to partial model knowledge.

We consider systems with matched uncertainty [2], where the unknown dynamics is parameterized by an unknown parameter vector and a known, state-dependant feature matrix. In this setting, the uncertainty can be exactly canceled by the control input given knowledge of the true parameter. We aim to find causal adaptive controllers that estimate this parameter recursively while stabilizing the system and minimizing regret. Most continuous-time adaptive controllers in this setting utilize Lyapunov theory and provide only asymptotic stability guarantees, see for example [1]–[3]. Using the same tools, recently, a finite \(\mathcal{O}(1)\) regret bound for linear systems is derived in [10], and for nonlinear time-varying systems in [11]. In [11], the authors also extend the results to a discrete-time setting, achieving a \(o(T)\), sublinear-in-time, bound with a causal formulation, and a \(\mathcal{O}(1)\) with a non-causal one. In contrast to our proposed method, the Lyapunov-based adaptive controllers in [10], [11] are not realizable in discrete time, as the parameter update depends on the current, unobserved error, making it non-causal. The online gradient descent-based algorithm in [11], although causal, achieves \({o}(T)\) regret even in the deterministic case. The difficulty is inherent in the discrete-time formulation of the problem, which introduces a one-step delay in the error observation. In discrete time, the convenient Lyapunov function cancellation [2] no longer holds and discrete-time Lyapunov functions are known to be harder to construct [12].

The recursive learning algorithm for the adaptive controller can be set up to relate to an online or “running" cost. This setting is studied in the time-varying optimization literature providing asymptotic tracking and convergence guarantees for online costs, e.g., [13], [14]. However, in this line of work, the problem setup considers no underlying dynamics for the state, and the regret generally is not studied.

We design causal, uncertainty-matching, recursive methods for discrete-time, nonlinear, time-varying systems. Our contributions are threefold. First, we introduce a recursive proximal learning (RPL) parameter estimation algorithm based on the proximal point method [15]. Under a weak notion of persistence of excitation (PE), RPL produces estimates of the unknown parameters that are contractive with respect to the true one. Second, we show that RPL-based adaptive control achieves finite regret scaling with the time required to achieve the weak PE condition. By contrast, in [11] finite regret is only achieved through access to a Lyapunov function or by a non-causal controller. Finally, we analyze the regret of the recursive least-squares with forgetting factor (RLSFF) [16] in this setting. We show that while both RPL and RLSFF achieve finite regret with similar bounds, this is established for RPL under a weaker PE condition. We demonstrate the algorithms on a discrete-time model reference adaptive control (MRAC) [17] numerical example.

Notation: The sets of positive real numbers, positive integers, and non-negative integers are denoted by \(\mathbb{R}_{+}\), \(\mathbb{N}_{+}\) and \(\mathbb{N}\), respectively. For a given vector \(x\), its Euclidean norm is denoted by \(\|x\|\). The spectral norm of a square matrix \(W\) is denoted by \(\|W\|\), and the largest and smallest singular values and eigenvalues by \(\sigma_{min}(W)\), \(\sigma_{max}(W)\), and \(\lambda_{min}(W)\), \(\lambda_{max}(W)\) respectively. For a positive scalar \(r\in \mathbb{R}_+\), we define the closed ball around the origin as \(\mathcal{B}_r:=\{x\in \mathbb{R}^n \;| \;\|x\|\leq r\}\).

2 Problem Statement↩︎

We consider nonlinear dynamical systems with matched uncertainty of the form \[\label{eq:nonlinear95matched} x_{k+1} = f_k(x_k) + B_k(x_k)\left(u_k - \alpha(x_k)\right),\tag{1}\] where \(f: \mathbb{N} \times \mathbb{R}^n \rightarrow \mathbb{R}^n\) models the known nominal dynamics and satisfies \(f_k({0}) = {0}\) for all \(k\in \mathbb{N}\), \(B_k: \mathbb{N}\times\mathbb{R}^n \rightarrow \mathbb{R}^{n\times m}\) is a known input matrix with a bounded norm, and \(\alpha: \mathbb{R}^n \rightarrow \mathbb{R}^m\) is an unknown mapping to the input space, capturing the uncertain dynamics of the model. We assume that \(\alpha\) can be exactly parameterized by possibly nonlinear, but known and bounded basis matrices, \(\phi: \mathbb{R}^n \rightarrow \mathbb{R}^{p\times m}\), that map the state to a feature in \(\mathbb{R}^{p\times m}\). The uncertainty is then given by \(\alpha(x_k) = \phi^\top(x_k)\theta^\star\), where \(\theta^\star \in \mathbb{R}^{p}\) is an unknown weighting vector⁵. We also assume \(\|B_k(x_k)\phi^\top(x_k)\| \leq b\) for all \(k\in \mathbb{N}\), \(x \in \mathbb{R}^n\) and some \(b \in \mathbb{R}_+\). The tracking problem under partial model knowledge can also be cast into this framework in the context of MRAC, as shown in 5.

We characterize the performance of a given controller for system 1 over a time horizon \(T\) by comparing it to a benchmark control signal \(u^\star=\begin{bmatrix} {u^\star_0}^\top & \ldots & {u^\star_{T-1}}^\top \end{bmatrix}^\top\) that cancels the uncertainty perfectly and is defined below. We use regret to quantify the controller performance \[\label{eq:regret} \mathcal{R}_T({u}) = \sum_{k=0}^{T-1} c(x_k)- c(x^\star_k),\tag{2}\] where \(u=\begin{bmatrix} u_0^\top & \ldots & u_{T-1}^\top \end{bmatrix}^\top\) denotes the control signal of a given controller, \(x_k\) and \(x^\star_k\) are state sequences due to the control signals \(u\) and \(u^\star\), respectively, and \(c:\mathbb{R}^n \rightarrow \mathbb{R}\) is a stage cost. We restrict our analysis to locally Lipschitz continuous costs and assume for any \(R\in \mathbb{R}_+\), there exists a \(L_c \in \mathbb{R}_+\), such that for all \(x,y \in \mathcal{B}_R\), \[\label{eq:lipschitz95cost} \|c(x) - c(y)\| \leq L_c \|x-y\|.\tag{3}\]

The ediss property characterizes only the known and autonomous part of the dynamics. It is known that if \(f_k\) is smooth in the state and is contractive, then it is also ediss [11], [19]. If \(f_k\) is not smooth, then under milder conditions, we show in [20] that exponential stability implies ediss.

2.1 Online Estimation↩︎

We consider adaptive control laws that produce control inputs of the form \(u_k =\phi^\top(x_k)\theta_k\) where \(\theta_k \in \mathbb{R}^{p}\) is an online estimate of \(\theta^\star\) at time \(k\). The closed-loop dynamics for a controller of this form is given by \[\label{eq:suboptimal} x_{k+1} = f_k(x_k) + \underbrace{B_k(x_k)\phi(x_k)^\top\left(\theta_k-\theta^\star\right)}_{w_k(x_k)},\tag{4}\] where \(w_k(x_k)\) can be thought of as a state-dependant artificial disturbance introduced due to an inexact uncertainty matching. One can also consider a benchmark counterfactual control input \(u_k^\star: = \phi(x_k^{\star})^\top \theta^\star\) and the corresponding signal \(u^\star\) that perfectly cancels out the uncertainty in 1 leading to a benchmark state evolution \[\label{eq:optimal} x_{k+1}^\star = f_k(x_k^\star).\tag{5}\] Note that \(u^\star\) is a counterfactual policy that is not realizable, as \(\theta^\star\) is unknown. To simplify the analysis, we take \(x_0=x_0^\star\).

A standard setup in adaptive control design is to produce estimates \(\theta_k\) that minimize the magnitude of \(w_k(x_k)\), effectively steering the state of 4 to that of 5 thanks to the ediss property. This is often done by setting up a least squares estimation problem, minimizing the following online estimation cost for all \(k \in \mathbb{N}_+\) \[\begin{align} \label{eq:nominal95cost} \theta_k &= \mathop{\mathrm{arg\,min}}_\theta h_{k-1}(\theta), \\ h_{k-1}(\theta): \!&= \! \frac{1}{2}\sum_{i=0}^{k-1}\|B_i\phi_i^\top\left(\theta-\theta^\star\right)\|^2 = \frac{1}{2}\|\Phi_{k}{\theta} -Y_{k}\|^2,\notag \\ \nonumber Y_k &= \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_{k-1} \end{bmatrix}, \qquad \Phi_k = \begin{bmatrix} B_0\phi_0^\top\\ B_1\phi_1^\top\\ \vdots \\ B_{k-1}\phi^\top_{k-1} \end{bmatrix},\\ \nonumber y_k &= x_{k+1} - f_k(x_k) - B_k\phi_k^\top \theta_k = B_k\phi_k^\top \theta^\star. \end{align}\tag{6}\] Note that at time \(k\), the latest available online estimation cost is \(h_{k-1}\), as \(y_k\) is not yet available. Solving 6 directly requires computing an expensive matrix inverse at each time step and maintaining an increasing memory. In this work, we study two recursive methods that alleviate this issue, both optimizing an online cost related to 6 . In particular, we introduce and analyze a recursive proximal learning method in Section 3, and also study the well-established recursive least squares with forgetting factor [16] in Section 4.

2.2 Regret↩︎

Speed or velocity-gradient controllers are introduced in [7] to solve the continuous-time equivalent of the online estimation problem 6 in the framework of (integral) goal-oriented control. It is shown that these methods achieve finite estimation error in the limit, under the assumption that the controller at time \(t\) can depend on the estimation error \({\theta}_t-\theta^\star\). Recent works [10], [11] noted that if an exponential Lyapunov function exists for the nominal system, a speed-gradient descent-based uncertainty matching controller achieves finite quadratic cost on the state. In particular, the suboptimal closed-loop state trajectory \(x_t\) satisfies \[J_\mathrm{cont}(x_0,u):=\lim_{T\rightarrow \infty}\int_{0}^{T}\|x_t\|^2dt = \mathcal{O}(1).\] Moreover, the existence of the exponential Lyapunov function also implies that \(J_{\mathrm{cont}}(x_0,u^\star)\) for the optimal state evolution is finite. Defining continuous-time regret as \(\mathcal{R}_{\mathrm{cont}}(u):= J_{\mathrm{cont}}(x_0,u) - J_{\mathrm{cont}}(x_0,u^\star)\), an \(\mathcal{O}(1)\) bound and the extra cost accumulated by the adaptive control law as compared to the benchmark follows directly. In [11] a discrete-time version of the speed-gradient algorithm is introduced with a finite cost bound, but with the same assumption that at time \(k\) the error \(\theta_k-\theta^\star\) is available, making the controller non-causal. Without this assumption, the authors achieve \(o(T)\) sublinear regret using an online learning toolkit. In this work, we consider causal controllers that minimize 6 at time \(k\) with access only to \(y_{k-1}\). To characterize the performance of such an adaptive, uncertainty-matching controller, we analyze the regret 2 .

3 Recursive Proximal Learning↩︎

The recursive proximal learning algorithm corresponds to the \(\varepsilon\)-scaled proximal operator of 6 evaluated at the previous estimate \[\label{eq:proximal95update} \begin{align} \theta_{k} &= \mathrm{prox}_{\varepsilon h_{k-1}}\left(\theta_{k-1}\right)\\ &=\mathop{\mathrm{arg\,min}}_{\theta}\left(h_{k-1}(\theta) + \frac{\varepsilon}{2}\|\theta-\theta_{k-1}\|^2\right), \end{align}\tag{7}\] for some \(\theta_0 \in \mathbb{R}^p\) and \(\varepsilon \in \mathbb{R}_+\). From the online learning perspective [4], \(\theta_k\) can be thought of as the minimizer of the latest available cost \(g_{k-1}\) at time \(k\) \[\label{eq:proximal95cost} g_{k-1}(\theta) = h_{k-1}(\theta) + \frac{\varepsilon}{2}\|\theta-\theta_{k-1}\|^2.\tag{8}\] While a closed-form solution to 7 exists, it requires memory increasing with time. The following equivalent set of updates to 7 remedies both issues. In particular, for all \(k\in \mathbb{N}\), the following is equivalent to 7 \[\label{eq:rpl} \begin{align} P_{k+1}^{-1} &= P_k^{-1} + \phi_kB_k^\top B_k \phi_k^\top, \\ H_{k+1} &= H_{k} + \phi_k B_k^\top B_k\phi_k^\top\\ s_{k+1} &= s_{k} + \phi_kB_k^\top y_k\\ \theta_{k+1} &= \theta_k - P_{k+1}\left(H_{k+1} \theta_k - s_{k+1}\right), \end{align}\tag{9}\] with the initialization \(H_0=\boldsymbol{0}_{p \times p}\), \(s_0={0}\) and \(P_0^{-1} = \varepsilon I_p\).

3.1 Contraction in Parameter Space↩︎

We define \(T_s\)-weak PE as follows.

We show below that under a \(T_s\)-weak PE assumption, the RPL update 7 enjoys a contraction property on the parameter; moreover, under an additional assumption, the lifted input vector \(\Phi_k \theta_k\) is also contractive.

3.2 Closed-loop Analysis↩︎

Consider the suboptimal state evolution 4 under the RPL controller \(u_k^{\mathrm{RPL}} = \phi_k^\top\theta_k\), with \(\theta_k\) given in 7 . We can represent it equivalently as \[\label{eq:suboptimal95rpl} x_{k+1} = f_k(x_k)+ \underbrace{S_k\left(\Phi_{k+1}{\theta}_k-\Phi_{k+1}\theta^\star\right)}_{w_k(x_k)},\tag{10}\] where \(S_k:= \begin{bmatrix} \boldsymbol{0} & \ldots & \boldsymbol{0} & I_{n}, \end{bmatrix} \in \mathbb{R}^{n \times n(k+1)}\) is a selector matrix that selects the last component of \(\Phi_{k+1}\left({\theta}_k-\theta^\star\right)\), corresponding to \(B_k\phi_k^\top(\theta_k-\theta^\star)\). Similarly, the optimal state evolution under \(u^\star\) is given by \[\label{eq:optimal95rpl} x_{k+1}^\star =f_k(x^\star_k) +\underbrace{S_k\left(\Phi^\star_{k+1}\theta^\star-\Phi^\star_{k+1}\theta^\star\right)}_{\boldsymbol{0}},\tag{11}\] where \(\Phi^\star_{k+1}:= \Phi(x^\star_{[0,\ldots,k]})\). In the following theorem, we characterize the closed-loop system 10 in terms of asymptotic stability and regret. In particular, we show that the regret of the RPL controller scales with \(\mathcal{O}\left(\|\tilde{\theta}_0\| T_s\right)\).

The theorem states that given the assumptions on the nominal system, both 10 and 11 state trajectories converge to the origin. It is important to note that no further restrictions are put on the stage costs \(c\), other than local Lipschitz continuity. Hence, the finite regret result of the theorem does not imply the cost \(\sum_{k=0}^{T-1}c(x_k)\) is minimized, but the relative cost performance is bounded. Moreover, it shows that this performance, in terms of regret scales with the initial exploratory time period \(T_s\), and cannot be avoided, as during these transients the parameter updates are only nonexpansive by Lemma 1. If the additional assumptions on \(\varepsilon\) and \(B_k\phi_k\) are satisfied, then the constant term is updated from a uniform bound \(b\) to \(c_p:=\|\Phi_{T_s}\|\), which relates to the regression matrix only in the initial period.

In the following lemma, we show that Lipschitz continuity of the basis matrices and \(\phi({0})=\boldsymbol{0}_{p \times m}\) is a sufficient condition to fulfill Assumption 2.

4 RLS with Exponential Forgetting↩︎

The RLSFF algorithm minimizes the online cost \[\begin{align} \label{eq:rls95ff} g_{k-1}^f(\theta) = \frac{1}{2}\sum_{i=0}^{k-1}\lambda^{2(k-1-i)}&\|B_i\phi_i^\top \left(\theta-\theta^\star\right)\|\\ &+ \frac{\lambda^{2(k-1)} \varepsilon}{2}\|\theta_0 - \theta^\star\|^2, \end{align}\tag{18}\] for a fixed exponential forgetting factor \(\lambda^2 \in (0,1)\), where the first term can be thought of as the discounted version of 6 and the second, as a discounted regularizer on the initial parameter error. The update can be recursively implemented as follows [23] for all \(k \in \mathbb{N}\) \[\label{eq:rls95combined} \begin{align} P_{k+1}^{-1} &= \lambda^2 P_{k}^{-1} + \phi_{k}B_{k}^\top B_{k}\phi_{k}^\top,\\ \theta_{k+1} &= \theta_{k} - P_{k+1} \phi_{k} B_{k}^\top(B_k\phi_{k}^\top\theta_{k} - y_{k}), \end{align}\tag{19}\] where \(\theta_0 \in \mathbb{R}^p\) is an initial guess and \(P_0^{-1} = \varepsilon I_p\). The convergence of the above update requires a persistence of excitation condition in the sense of the following [16].

The PE condition in Definition 2, commonly found in the adaptive control literature [1], [16] is a stronger version of the \(T_s\)-weak PE condition in Definition 1. The latter requires the positive definiteness of the regressor matrix only in the initial phase of the estimation, rather than in all time intervals of length \(T_s\).

The non-expansive result follows by noting from 19 \[\tilde{\theta}_k = \left(I_p - P_{k+1}\phi_kB_k^\top B_k \phi_k^\top\right)\tilde{\theta}_{k-1}, \quad \forall k>0,\] and that \(\sigma_{min}\left(P_{k+1}\phi_kB_k^\top B_k \phi_k^\top \right)\geq 0\) and \(\sigma_{max}\left(P_{k+1}\phi_kB_k^\top B_k \phi_k^\top \right)<1\). The proof for the exponential stability for \(k\geq T_s\) can be found in [23] and is hence omitted.

Consider the RLSFF controller \(u_k^{\mathrm{RLS}} = \phi_k^\top\theta_k\) with \(\theta_k\) given by the recursive law 19 .

4.1 Analysis of the Bounds↩︎

Both the RPL and the RLSFF adaptive controllers achieve a finite regret containing three separate terms of potential interest. A constant term, an exponentially decaying one with rate \(\rho\), and a linear term in the PE time \(T_s\). The latter is of most interest, which arises from the non-expansive properties of both estimators and signifies that no improvement in the worst-case can be expected until the time \(T_s\) when the PE condition is met. Comparing the regret bounds directly, when \(\gamma <\lambda\) and \(c_r>1\), i.e. \(\varepsilon > \delta\) for the RLSFF algorithm 19 , then the upper bound of the RLSFF regret is strictly larger than that of the modified RPL controller.

5 Numerical Simulation↩︎

In this section, we show that the MRAC problem can be cast into the considered setting and provide a numerical example to showcase the performance of discussed adaptive controllers. Consider the uncertainty-matched system \[\label{eq:linear95matched} x_{k+1} = Ax_k + B(u_k - \phi(x_k)^\top\theta^\star),\tag{20}\] where \(A \in \mathbb{R}^{n\times n}\), \(B \in \mathbb{R}^{n \times m}\), \(\phi (x_k)\) is defined as before, and \(\theta^\star \in \mathbb{R}^p\) is unknown. The MRAC goal is to track the reference dynamics \[\bar{x}_{k+1} = A_r \bar{x}_k + B_r r_k,\] where \(\bar{x}_k \in \mathbb{R}^n\), is the ideal reference vector to be tracked, \(r_k \in \mathbb{R}^m\), is the bounded input command, \(B_r\in \mathbb{R}^{n\times m}\) and \(A_r \in \mathbb{R}^{n \times n}\) is Schur stable. As in [17], we assume \((A,B)\) to be controllable and \(B\) to be full column rank, and consider the input \(u_k = -K_1x_k +K_2r_k + \phi_k^\top\theta_k\) with matrices \(K_1, K_2 \in \mathbb{R}^{m \times n}\) chosen such that \(A-BK_1 = A_r\) and \(BK_2 = B_r\) hold and \(\theta_k\) being the parameter estimate. Denoting \(e_k = x_k-\bar{x}_k\), the error dynamics are given by \[\label{eq:error95dynamics} e_{k+1} = A_r e_k + B\phi(x_k)^\top \tilde{\theta}_k,\tag{21}\] in the form of 1 . Since \(A_r\) is stable, the ediss condition is satisfied. For the cost we consider \(c(x):= \|x\|^2\) [11], which is locally Lipschitz since the closed-loop states are bounded.

We consider the following numerical example [17] \[A = \begin{bmatrix} 1.0314& 0.2526\\ 0.2526& 1.0314 \end{bmatrix}, \; B = \begin{bmatrix} 0.0314\\ 0.2526 \end{bmatrix},\] with the reference model dynamics \[A_r = \begin{bmatrix} -0.9929& 0.2253\\ -0.0569& 0.8117 \end{bmatrix}, \; B_r = \begin{bmatrix} 0.0314\\ 0.2526 \end{bmatrix}.\] The true parameter is \(\theta^\star = \begin{bmatrix} -0.75& -0.50 \end{bmatrix}^\top\) and \(\phi(x_k) = x_k\). Figure 1 shows the tracking of the first component of state \(x_k\) for the above example under the RPL, RLSFF and the command governor-based MRAC controller proposed in [17] without regret guarantees.

For all algorithms we initialize the estimate by \(\theta_0\!=\!\begin{bmatrix} 5.00& -1.00 \end{bmatrix}^\top\), take \(\varepsilon=1\) and start the simulation at \(x_0 = \begin{bmatrix} 0.2& 0.2 \end{bmatrix}^\top\). For RLSFF we used a forgetting factor of \(\lambda^2=0.99\), as lower values led to conditioning problems. For the controller of [17] we used the same parameters as in Example 1, [17] and a tuned saturation value of \(1.5\) for the command governor update for best results. The superior performance of RPL is evident from 1, despite a less stringent PE condition. The top figure shows the tracking performance of the controllers while the bottom the regret for the quadratic costs, which in this case is \(\mathcal{R}_T(u): = \sum_{k=0}^{T-1}\|e_k\|^2\), since by definition \(\Bar{x}_0={x}_0\) and therefore \(e^\star_k=0\) for all \(k\in \mathbb{N}\).

6 Conclusion↩︎

Two recursive learning algorithms were considered for the nonlinear adaptive control problem with matched uncertainty in the context of regret minimization. We showed that both the recursive least squares with forgetting factor and the novel recursive proximal learning algorithm are asymptotically stable and achieve finite regret scaling with the time required to achieve persistence of excitation. Possible extensions include the consideration of inexact basis matrices, bounded, non-stochastic noise, and the development of goal-oriented controllers that instead of the estimation cost aim to minimize the objective cost directly.

References↩︎