Online Learning Robust Control of Nonlinear Dynamical Systems

The online controller we propose and analyse is a Receding Horizon Controller (RHC) which has preview of the cost functions for a short horizon $M$ at time $t$. In a typical RHC setting, the controller optimizes the cost-to-go for a certain horizon and applies the first element of the computed optimal control sequence as the control input. This is then repeated at every time step. The RHC approach to control is a well established technique in control. The primary advantage of the RHC approach is that the optimization carried out at every step can incorporate any type of control input, system state and output constraints, and cost functions [35, 38, 9]. The RHC controller we propose optimizes the cost-to-go for the short horizon $M$ to compute the control input for time $t$. It then applies the first element of the computed optimal control sequence for the horizon $M$ as the control input. This is repeated at every time step. We analyse the performance of RHC over a duration $T\gg M$.

First, we present the setting where the system is known. We present: (i) the performance guarantee for the Receding Horizon Controller (RHC) when the controller has preview of the disturbance $w_{k}$ for the horizon $M$, i.e., for $t\leq k\leq t+M-1$, and (ii) present the performance guarantee when the controller does not have any preview of the disturbance. For the first case we show that RHC achieves $R^{p}_{T}(\gamma)=O(1)$ when $\gamma\geq\gamma_{c}$ and the horizon length $M>\overline{\alpha}^{2}/\underline{\alpha}^{2}+1$. We show that the achievable attenuation in this case is nearly optimal that is $\gamma_{c}=\mathcal{O}(\overline{\gamma})$. For the second case, when the preview of the disturbance is not available we guarantee that the overall cost is bounded by $\sim 2\overline{\gamma}MT\max_{w\in\mathcal{W}}\lVert w\rVert^{2}_{2}+\mathcal{O}(1)$. Hence, in this case we guarantee that achievable attenuation is nearly $\mathcal{O}(\overline{\gamma})$ of the maximum energy in the disturbance.

We then present the setting where the system is unknown and the disturbance preview is available. We present analysis for systems that are Bounded Input Bounded Stable (BIBO) and the cost functions are convex. We assume that the state transition function is parameterized and that only the parameter is unknown. We propose a generic online control framework that operates in two phases: the estimation phase followed by the control phase. The estimation phase runs for a period of $N$ time steps, at the end of which the online controller calculates an estimate $\hat{\theta}$ of $\theta$. In the control phase, the controller is the RHC that optimizes the cost-to-go for the estimated system. We present performance analysis for a black-box estimation procedure with accuracy given by: $\lVert\hat{\theta}-\theta\rVert_{2}\leq g(N)$, a bounded and decreasing function of $N$. We show that the overall online controller achieves $R^{p}_{T}(\gamma)=\mathcal{O}(N)+\mathcal{O}(1)+\mathcal{O}((T-N)g(N))$ when $\gamma\geq\gamma_{c}$ and the horizon length $M$ exceeds the same threshold as before. For linear systems, we trivially recover the results for the known system case since the estimation is trivial when the disturbance preview is available and the system is controllable. The framework we present provides a direct characterization to evaluate the various estimation approaches.

For a sequence (of vectors/function) $\{a_{t},1\leq t\leq T\}$, we denote $a_{1:t}=\{a_{\tau},1\leq\tau\leq t\}$. For a matrix $M$, we denote its transpose by $M^{\top}$. We denote the maximum eigenvalue of a matrix $M$ by $\lambda_{\text{max}}(M)$. The two norm of a vector is denoted by $\lVert.\rVert_{2}$. When two matrices $M_{1}$ and $M_{2}$ are related by $M_{1}\geq M_{2}$ then it implies that $M_{1}-M_{2}$ is positive semi-definite. Similarly, when $M_{1}>M_{2}$ it implies that $M_{1}-M_{2}$ is positive definite. We denote $\mathbb{R}^{n}$ as the $n-$dimensional euclidean space and $\mathbb{R}_{\geq 0}$ as the positive part of the real line.

In this setting, we assume that the system dynamics is not parameterized by $\theta$. we assume that the algorithm has a fixed horizon preview of the future cost functions and disturbances. In particular, at each time $t$, algorithm has access to $c_{t:t+M-1}$ and $w_{t:t+M-1}$, in addition to the history of observation until $t$. We use a receding horizon control approach that minimizes the cost-to-go for a horizon $M$ with the previewed disturbances and cost functions. In particular, to find the control input $u_{t}$ at each time step $t$, the algorithm solves the following optimization problem:

where $\mathcal{U}$ is a compact set. Given that $f,c_{j}$ are continuous functions the solution to the above optimization exists. Please see proof of Lemma 3 for a detailed argument. We denote the solution of this optimization by $\text{MPC}^{t}(W_{t:t^{e}})$. The control input $u_{t}$ is set as the first element of the sequence $\text{MPC}^{t}(W_{t:t^{e}})$. We succinctly denote the control input by $\kappa_{M}(x_{t})$. The overall online control algorithm is given in Algorithm 2.

For the unknown system case, we assume the system dynamics is parametrized by an unknown parameter $\theta$, i.e.,

The online controller we propose operates in two phases: (i) estimation phase, and (ii) control phase. The estimation phase runs for a duration of $N$ time steps. We assume that the estimation algorithm is such that at the end of the estimation phase the estimated parameter $\hat{\theta}$ is such that $\lVert\hat{\theta}-\theta\rVert_{2}\leq g(N)$, a bounded and decreasing function of $N$. In the discussion below, we comment on the estimation procedures for specific instances of the system. In this work we present the performance analysis of the online controller without restricting the analysis to a specific estimation procedure. The performance guarantee is presented in terms of the accuracy of a given estimation algorithm $g(N)$. Thus, the analysis we present can be extended to any estimation procedure.

In the control phase, the controller is the online receding horizon controller similar to the known system case. At each instant, the controller optimizes the cost-to-go for the horizon $M$ for the realized disturbance for the estimated system:

We later argue that the solution to this optimization exists. Please see proof of Lemma 3 for a detailed argument. We denote the solution of this optimization by $\text{MPC}^{t}(w_{t:t+M-1};\hat{\theta})$. The control input $u_{t}$ is set as the first element of $\text{MPC}^{t}(w_{t:t+M-1};\hat{\theta})$. We succinctly denote the control input by $\kappa_{M}(x_{t};\hat{\theta})$.

We define $V^{t}_{M}(x_{t},w_{t:t+M-1})$ as the optimal value function of the optimization problem given in Eq. 3. Hence, $V^{t}_{M}(x_{t},w_{t:t+M-1})$ is given by

We note that this function exists and is continuous given that the solution to the optimization exists and is continuous (see Proof of Lemma 3 for a more detailed argument). In the next lemma, we characterize the incremental change of the value of this function as the system evolves. We present this characterization for the class of systems that satisfies $V^{t}_{M}(x_{t})\leq\overline{\alpha}\sigma(x_{t})+\overline{\gamma}\sum_{k=t}^{t^{e}-1}\lVert w_{k}\rVert^{2}_{2}$. This represents a sufficiently general class of systems. It includes the strongly convex quadratic cost functions for linear dynamical systems. As stated in the introduction, the first term in the bound represents the contribution to the cost by the initial state $x_{t}$ and the second term is the bound to the cost for the deviation effected by the disturbances. Here $\overline{\gamma}$ is the maximum achievable attenuation for this system.

Please see the Appendix for the proof. The result states that the change in the value of the optimal cost-to-go when the system evolves from $t$ to $t+1$ is bounded by (i) the cost of the initial state $x_{t}$ and (ii) some constant times the total energy of the disturbances for the duration $M$ starting from $t$. Next we use the above lemma to characterize an upper bound on the per step cost incurred by the online controller.

Please see the Appendix for the proof. The results imply that the cost at a time $t+H$ is bounded by two terms: (i) the contribution of the cost from the initial state $x_{t}$ that is exponentially decaying with $H$ and (ii) the contribution from the disturbances seen by the system so far. From the form of the coefficients $M_{w,j}$ it is clear that the online controller exponentially diminishes the contribution of the disturbances from earlier times. In the next theorem we characterize the performance of the online controller.

Please see the Appendix for the proof. It follows from the result that the achievable attenuation by the RHC approach is $\gamma_{c}$. Given the bounds on $a$ we can choose $a$ and $M$ such that $2\left(1+\frac{\underline{\alpha}}{\overline{\alpha}}\right)\left(\frac{\tilde{\gamma}\overline{\alpha}^{2}}{\underline{\alpha}^{2}}+\tilde{\gamma}^{2}\right)\overline{\gamma}\gtrapprox\gamma_{c}\geq 2\overline{\gamma}$, where $\tilde{\gamma}=\frac{\lceil\frac{\overline{\alpha}^{2}}{\underline{\alpha}^{2}}\rceil\underline{\alpha}}{\overline{\alpha}\left(\frac{\underline{\alpha}^{2}}{\overline{\alpha}^{2}}\lceil\frac{\overline{\alpha}^{2}}{\underline{\alpha}^{2}}\rceil-1\right)}$. This means that the RHC approach cannot beat $2\overline{\gamma}$ and that $\gamma_{c}=\mathcal{O}(\overline{\gamma})$.

Here, we present the performance analysis for a black-box estimation procedure with accuracy $\lVert\hat{\theta}-\theta\rVert_{F}\leq g(N)$. Let

Let $U$ and $\tilde{U}$ be two control sequence of length $M$. Define

We argue in Lemma 3 that the solution to the RHC optimization $\text{MPC}^{t}(w_{t:t^{e}};\hat{\theta})$ exists. Hence the function $V^{t}_{M}(x_{t},w_{t:t^{e}};\hat{\theta})$ is well defined.

We make the following additional assumptions on the system and the cost functions. These assumptions are required to establish Lipschitz continuity of the solution $\text{MPC}^{t}(w_{t:t^{e}};\hat{\theta})$. This is the key additional step that is required to extend the analysis technique applied to the known system case.

The assumption that the estimation accuracy $g(N)$ can be guaranteed by bounded excitation is trivially satisfiable for linear controllable systems. The assumption that the system is BIBO is required to ensure that the total cost incurred during the estimation phase scales only linearly with $N$.

To establish this result we draw from results on Lipschitz continuity of solutions to parametric optimization [40]. Please see the Appendix for the detailed proof. In the next lemma, we characterize the incremental change of the value of the function $V^{t}_{M}(.,.;\hat{\theta})$ in the control phase as the closed loop system evolves from $t$ to $t+1$. We establish these results for the same class of systems assumed for the known system case, i.e., systems for which $V^{t}_{M}(x_{t},W_{t:t^{e}};\theta)\leq\overline{\alpha}\sigma(x_{t})+\overline{\gamma}\sum_{k=t}^{t^{e}-1}\lVert w_{k}\rVert^{2}_{2}$ and additionally Assumption 3.

Please see the Appendix for the Proof. We note that the first two terms in the bound are the same as in the known system case. The last term arises from the error in the parameter estimate $\hat{\theta}$. Next we use the above lemma to characterize an upper bound on the per step cost incurred by the online controller in the control phase.

Please see the Appendix for the proof. We note that the per-step cost in the control phase in this case is bounded by three terms; the first two terms are the same as before while the additional third term arises from the error in the parameter estimate $\hat{\theta}$. In the next theorem we characterize the performance of the online controller.

Proof: By Assumption 3 that the system is BIBO and the accuracy $g(N)$ can be guaranteed by bounded excitation it follows that the cost for the estimation phase is bounded by $\gamma\sum_{t=1}^{N-1}\lVert w_{t}\rVert^{2}_{2}+\mathcal{O}(N)$. Then from Lemma 5, the fact that $\lVert\hat{\theta}-\theta\rVert_{2}\leq g(N)$, following steps similar to proof of Theorem 1 it follows that the bound for the cost for the control phase is $\gamma\sum_{t=N}^{T}\lVert w_{t}\rVert^{2}_{2}+\mathcal{O}(1)+\mathcal{O}((T-N+1)g(N))$. Combining the two observations the result follows $\blacksquare$

The result presented characterizes the achievable performance by the RHC approach for a given black-box estimation procedure. If $N=\mathcal{O}(1),g(N)=0$, as is the case with linear controllable systems, we recover the results for the known system case, where the RHC approach achieves the attenuation $\gamma_{c}$. Similarly, for nonlinear systems linear in unknown parameters, as argued earlier, $N=\mathcal{O}(1),g(N)=0$, and so the RHC approach will achieve the attenuation $\gamma_{c}$ in this case too. For a general estimation procedure for which $g(N)=\mathcal{O}(1/\sqrt{N})$, the optimal duration for the estimation phase is $N=\mathcal{O}(T^{2/3})$ and $R^{p}_{T}\leq\mathcal{O}(T^{2/3})$.