Computer Science
Computer Science-2021.gz:143236
Computer Science
40dfaccf411426f0e799ea829bdaae704726314c
Joint Stabilization and Regret Minimization through Switching in Systems with Actuator Redundancy

Adaptively controlling and minimizing regret in unknown dynamical systems while controlling the growth of the system state is crucial in real-world applications. In this work, we study the problem of stabilizing and regret minimization of linear dynamical systems with system-level actuator redundancy. We propose an optimism-based algorithm that utilizes the actuator redundancy and the possibility of switching between actuating modes to guarantee the boundedness of the state. This is in contrast to the prior works that may result in an exponential (in system dimension) explosion of the state of the system. We theoretically study the rate at which our algorithm learns a stabilizing controller and prove that it achieves a regret upper bound of O( √ T ).


I. INTRODUCTION
Switched systems that encompass several sub-systems and a switching rule that designates which subsystem is the governing one has been widely applied in control of mechanical systems, aircraft, automotive industry, air traffic control to name but a few [1]. A widely used paradigm of switching control is systems with actuator redundancy that enables it to be actuated with different subset of actuators. This class of systems contributes to the stability improvement as well as the transient response ( [2] and [3]). The benefit of switching between actuation modes has been addressed in the literature of cyber-physical security ( [4], [5], [6], and [7]) and fault tolerant control as well ( [8], [9], and [10]).
Leveraging actuator redundancy and switching between different set of actuating modes can also improve the learning algorithm efficiency which is the goal of this paper. For a system with known dynamics, it is obvious that adding one redundant actuator results in a better performance in terms of optimality as it gives one more degree of freedom in optimal control design. However, this is not necessarily true in unknown setting as this addition increases the number of parameters to be learned. The dimension dependency of the regret minimization algorithms in the literature are mainly exponential [11], [12] and such dependence is inevitable in general [13]. Stabilizing the unknown dynamics of a control system and minimizing the regret are among the main goals of algorithm design. The authors of [12] tackle this problem by proposing the ExpOPT algorithm which deploys additional exploration in the early stages upon which we build our own algorithm. Further concern in control design of system in unknown dynamics model setting is tighter upper bound of state norm which may not be met at initial stages of algorithm deployment. State-blow-up can cause serious problems specifically in linearized dynamical systems as it may cause a large deviation from vicinity where the approximation error is bearable. Noting that this deviation can cause inefficiency in learning and even lead to a destabilizing controller. We aim to circumvent this challenge by leveraging actuator redundancy and choosing an appropriate actuating mode for early exploration phase and specifying its deployment duration. Optimism in the face of uncertainty, OFU, as a class of adaptive control algorithm, which couples estimation and control design procedures, has shown its ability to outperform the naive certainty equivalence algorithm [14]. Campi and Kumar in [14] propose a cost-biased parameter estimator which is an OFU based approach to address the optimal control problem for linear quadratic Gaussian systems with guaranteed asymptotic optimality. However, this algorithm only guarantees the convergence of average cost to that of the optimal control in limit and for finite time does not provide any bound on the measure of performance loss. Abbsi-Yadkori and Szepesvari [15] propose a learning-based algorithm to address the adaptive control design of LQ control system in finite time with worst-case regret bound of O( √ T ) with exponential dependence in the problem ambient dimensions. Using ridge regression estimator, they propose to construct a high-probability confidence set around the unknown parameters of the system and design an algorithm that optimistically plays with respect to this set. Along this line, many works attempt to improve the exponential dependence with further assumption, e.g. highly sparse dynamics [16], or access to stabilizing controller. Furthermore, authors in [17] propose an OFU-based learning algorithm with mild assumptions and O( √ T ) regret. This class of algorithms was extended in [18], [19] to LQG setting where there is only partial and noisy observations on the state of system. In addition, in [12], an algorithm with more exploration is proposed for both controllable systems. In this paper we will apply some results of this paper to controllbale system class with actuator redundancy.
The remainder of the paper is organized as follows: Section II reviews the preliminaries and assumptions. Section III presents the problem statement and formulation in which we introduce the initial exploration (IExp) algorithm and stabilizing OFU algorithm (SOFUA) and discuss in detail how switching can contribute to the system stabilization and regret minimization. We carry out the regret bound analysis for (IExp+SOFUA) algorithms in the section IV. Finally, Section VI summarizes the paper's key contributions. For the sake of brevity the proofs of the theorems and lemmas have been provided in the arxiv version of draft.

II. PRELIMINARIES
Consider a linear time invariant dynamics and its associated cost function given by: where x t and u t denote the state and the control input at time step t, and A * ∈ R n×n and B * ∈ R n×d are the plant and input matrices which are initially unknown to the learner. Q ∈ R n×n and R ∈ R d×d represent known and positive definite matrices and ω t+1 is a noise signal, and initial state x 0 . The average cost as the result of applying control sequence {u t } t≥0 is given by: The problem is to design a controller such that the average cost (2) to be minimized. Let J * denote the lowest average cost (optimal cost). We measure the performance of a learning algorithm using the notation of regret, defined as where control inputs are prescribed by the learning algorithm. R T is the measure of how much the lack of insight into the model affects performance. Following [11] we assume that the system is controllable and observable. By defining Θ T * = (A * , B * ), the system transitions dynamics can be rewritten as: The first assumption is on the noise. Assumption 2.1: There exists a filtration F t such that (2.1) z t and x t are F t -measurable.
(2.2) for any t ≥ 0, (2.4) ω t are component-wise sub-Gaussian e.g. there exists σ ω > 0 such that for any γ ∈ R and j = 1, 2, ..., n where ω j t+1 is the j−th element of ω t+1 . In this paper, we aim to leverage actuator redundancy in control systems in order to improve the learning. When the parameters of system are known, adding a redundant actuator can improve the optimality of the designed control. However, in unknown settings, a redundant actuator means more parameters to be learned which in turn may cause a loss of efficiency. In this paper, we design an strategy through which the system can perform the learning and control task efficiently. We quantify the proposed strategy by regret bound guarantee.
Accordingly, we focus on special classes of system (1a,1b) in relation with the following notation. Let B c be the set of all columns, b i * (i ∈ {1, ..., d}), of B * , which correspond to each individual actuator of the system. 2 Bc denotes the power set of B c whose subsets, B j * s j ∈ {1, .., 2 d } is constructed by combination of columns b i * s. We define the dynamics of candidate of actuating modes i as follows: in which |B * | denotes the cardinality of set B * defined by where d i denotes number of actuators of the mode i.
Letting the mode i be defined by Θ i * ⊤ = (A, B i * ), with a slight abuse of notation, we denote the parameter matrix of mode 1, encompassing all actuators, by Θ * (i.e. Θ 1 * = Θ * ). The cost function has a quadratic form of (1b). The matrices A * and B * are unknown to the learner that aims to learn and control the system simultaneously while switching between a number of actuating modes. These actuation modes are constructed leveraging the redundancy of actuators.
For each actuating mode i defined by the pair where R i ∈ R di×di is input weight matrix of actuating mode i. Under controllability condition, the linear optimal control law u i (t) = K(P (Θ i ))x(t), where, is stabilizing and the average cost of control law with Θ = Θ * is the optimal average cost J(Θ i * ) = trace(P (Θ i * )). We reformulated the problem (5) in the following way: in whichū =K i x. We need the following construction before definingK i . Recalling that the matrix B i is constructed by the subset columns b j 's (j ∈Ā ⊂ {1, ..., m}), we defineK i as a d i × n matrix whose rows j ∈Ā are rows of K i by order and zero elsewhere.
Having the set of candidate switching modes B can ⊆ B, the following assumption is the other core assumption of our analysis which holds for all actuating modes.
Assumption 2.2: Let the sets S i 0 and S i 1 be defined as follows: Then, given the information s i and Υ i , Θ i * ∀i ∈ B can belongs to the intersection of these sets, i.e. Θ i * ∈ S i where S i ⊆ S i 0 ∩ S i 1 . By slightly abusing the notation for the full actuation mode mode i = 1, we simply let Υ 1 = Υ, s 1 = s, and S 1 = S. It is obvious that s i ≤ s ∀i ∈ B can .
In addition, boundedness of S i 's results in boundedness of P (Θ i ) with a finite constant D i [20]: then we define D = max i∈B * D i . And ∃κ > 1 such that In the proposed strategy we need some side information from system parameters for all the actuating modes which are summarized in the following assumption. and At first glance the assumption (12) may seem restrictive, however, it is not true as we do not use this side information in the control design procedure and it is merely used for regret bound analysis.

III. PROBLEM STATEMENT AND FORMULATION
In this section, we propose an ExpOPT ( [12]) based algorithm that leverages actuator redundancy in the "more exploration" step to avoid blow up in the state norm while minimizing a regret bound. We break down the strategy into two phases of initial exploration (Exp) and optimism (Opt) and build upon the recent results regarding the existence of a stabilizing neighborhood around the the system parameters. Reaching such a set is one of the main goals of initial phase of the algorithm. (14) and set τ = t 8: For the parameterΘ i * t solve the Ricatti equation and find Apply the controlū i * t on the system Θ i * * and observe new state x t+1 . 15: Using u i * t and x t form z i * and Save (z i * t , x t+1 ) into dataset 16:

A. The initial exploration phase
Before describing our strategy and the corresponding algorithms, we deem it necessary to go through a few important points. Given the fact that for a controllable system, discrete algebraic Riccati equation has unique positive definite solution, we can show that there exists a stabilizing neighborhood around the system parameters that any controller designed using parameters in that neighborhood stabilizes the system.
In order to reach this neighborhood, we need to explore the system for some time. However, during the exploration phase the state of system may blow up. In [12] it is shown that the state norm is upper-bounded by c(n + d) (n+d) with a problem dependent parameter c, which emphasizes the role of the number of actuators d on state norm during initial exploration phase. For systems with redundant actuation such as those described in Section II, it is thus natural to think of performing this exploration phase using a single actuator. The question, then, is which one to choose to guarantee the smallest blow-up of state (instability). The duration of the exploration phase, T c , that guarantees reaching the stabilizing neighborhood is the other important concern which should be addressed. Before answering these questions, we provide a brief explanation of the Algorithm 1 which assumes that exploration actuation mode i * and T i * c have been determined. The Initial exploration uses the self-normalized process to construct a high probability confidence set around the true parameters of the system. By receiving new measurement z t the least square estimation error, e(Θ i * ), is obtained as, with regularization parameter λ > 0. This yields the l 2 -regularized least square estimate: where Z i * and X are matrices whose rows are z i * 0 ⊤ , ..., z i * t−1 ⊤ and x ⊤ 1 , ..., x ⊤ t . Defining covariance matrix V i * t as follows: 11] shows that with probability at least (1 − δ), where 0 < δ < 1, the true parameters of system Θ i * belongs to the confidence set defined by: where After finding high-probability confidence sets for the unknown parameter, the core step of algorithm proposed in [11] is implementing Optimism in the Face of Uncertainty (OFU) principle. At any time t, we choose a parameterΘ i * t ∈ S i * ∩C i * t (δ) such that: where J = Tr(P (Θ i * )) and P (Θ i * ) is the solution of ARE for Θ i * . After using the chosen parametersΘ i * as if they were the true parameters, the linear feedback gain K is designed. We synthesized the controlū t =K(Θ i * )x t + ν t on the system Θ * . The construction ofK has been illustrated in Section II.
As can be seen in the regret bound analysis of [11], recurrent updates in the policy may worsen the performance, so a criterion is needed to prevent frequent policy switches. As such, at each time step t the algorithm checks the condition det(V i * t ) > 2 det(V i * τ ) to determine whether updates to the control policy are needed where τ is the last time of policy update.
Note that in (15) we have not specified any structure for the control input used to construct the extended state z i * t . The formulation above holds for any actuation mode , being mindful that the dimension of the covariance matrix changes. Output of Algorithm 1 is a confidence set around the parameters of full-actuation mode which is defined in a similar way as follows: where β t (δ) = (σ ω 2n log( det The control input for the exploration phase is written asū t =K(Θ i * t )x t +ν t whereK(Θ i * t )x t corresponds to the optimism part of strategy (K is constructed using K) and ν t ∼ N (µ, σ 2 ν I) ∈ R d with σ 2 ν = 2κ 2σ2 ω is random exploration term to be characterized. This additional term aims at finding stabilizing neighborhood faster.
Given the constructed central confidence set, we aim to specify the time duration T i * c that guarantees the parameter estimate is within stabilizing neighborhood. For this, we need to lower bound the smallest eigenvalue of co-variance matrix V t . The following lemma adapted from [12], named persistence of excitation during the extra exploration, provides this lower bound. Lemma 3.1: For the initial exploration period of T ω ≥ 6n with probability at least for any σ 2 1 ≤ σ 2 2 and σ 2 3 such that c p , c ′′ p > 0. The following lemma gives an upper-bound for the parameter estimation error at the end of time T which will be used to compute the minimum extra exploitation time T ω . Lemma 3.2: Suppose assumption 1 and 2 holds. For T ≥ POLY(σ 2 ω , σ 2 ν , n log(1/δ) having additional exploration leads to Proof: The proof is straightforward. First, a confidence set around the true but unknown parameters of the system is obtained which is given by (18) and (19). Then applying (20) given by Lemma 3.1 completes the proof. There is one more step to obtain the extra exploration duration, T ω which is obtaining an upper-bound for the right hand side of (21). Performing such a step allows us to state the following central result.
Lemma 3.3: At the end of initial exploration, for any mode ∀i ∈ B * the following inequality holds where κ i e := σω σ⋆ n(n + d) log 1 + P λ(n + d) and, in which d i denotes the number of actuators of the mode i and T i ω stands for initial exploration duration of the mode i. Furthermore, if we define holds with probability at least 1 − 2δ. The proof is provided in Appendix VII.

B. Determining the optimal mode for IExp
We still need to specify the best actuating mode i * for initial exploration along with its corresponding upperbound X i * t . To this aim, we need following lemma adapted from [11].
where τ t is a set of finite number of times, with maximum cardinality n + d i , occurring between any time interval [0 t] such that ||(Θ i * −Θ i s ) ⊤ z i s || is not well controlled in those instances (see Lemma 17 and 18 in [11] for more details). For the system actuating in the mode i the state recursion can be written as follows: and where M i t = (Θ * −Θ t )z t . By propagating the state back to time step zero, the state update equation can be written as: Assuming x 0 = 0 and applying the side information given in Assumption 2.3, i.e. (10) and assuming ||B * ||σ ν and σ ω are independent, then one can upper-bound the state norm as follows: normalsize where di stands for the number of actuators of an actuating mode i and similarly any subscripts and superscripts i denotes the actuating mode i. The policy explicited in Algorithm 1 keeps the states of the underlying system bounded with the probability at least 1 − δ during initial exploration which is defined as the "good event" A second "good event" is associated with the central confidence set defined as: Given the side information Υi and ηis for all actuating modes i ∈ {1, ..., |B * |}, using the bound (30), we aim to find an actuating mode i * that provides the lowest possible upperbound of state at first phase. This guarantees the state norm does not blow-up while minimizing the regret. The following lemma specifies the best mode i * to reach this goal as well as the corresponding upper-bound X i T i ω already used in (23).
Theorem 3.1: For any 0 ≤ t ≤ T i c , when the system actuates in the mode i ∈ B * it holds that 1) where where Yi,t := max e, λ(n + d i )(e − 1), AndLi =Ki(n + di + 1) whereK 2) The best actuating mode i * for initial exploration is, 3) The upper-bound of state norm of system actuating in the mode i * during initial exploration phase can be written as follows: for some system parameters dependent constant c i * . The proof can be found in Appendix VII Remark 3.1: While optimization problem (35) cannot be solved analytically because T i c itself depends on X i T i ω , it can be determined using the Algorithm 2.
After running the IExp algorithm for t ≤ T i * c noting that the confidence set is tight enough and we are in the stabilizing region, Algorithm 3 which leverages all the actuators comes into play. This algorithm has the central confidence set given by the Algorithm 1 as an input. If the event Et holds, Algorithm 3 keeps the states of the underlying system bounded with probability 1 − δ in optimism phase (second phase) which is defined as the "good event" Ft for t > T i * c : where . The upper-bound (38) is simply obtained from propagating the linear dynamics Algorithm 2 Find best actuating mode i * and its corresponding T i * c 1: Inputs:λ, κ, S > 0, δ > 0, Q , σ ω , ϑ i , η i , Υ i ∀i ∈ B * 2: for ∀i ∈ B * do 3: for t = 1, 2, ..., T i itr do 5: compute κ i e by (23) 6: compute T i c by (24) 7: if t < T i c then 8: T i itr = T i itr + 1 9: else 10: end if 12: end for 13: end for 14: Compute X i is the closed-loop dynamics and x T i * c is initial state. With controllability assumption for the t > T i * c , if the event Et holds then By applying union bound argument on the second term from right hand side of (40) and using the bound (36), it is straight forward to show that For t > T i * c + (n+d i * ) log(n+d i * )+log c i * −log χs log 2 1−Υ := Trc we have xt ≤ 2χs that gives (38) (See [12] for details).
Algorithm 3 Stabilizing OFU Algorithm (SOFUA) CalculateΘ t by (14) and set τ = t 6: For the parameterΘ t solve Ricatti and calculate u t = K(Θ t )x t

IV. REGRET BOUND ANALYSIS
The decomposition of IExp+SOFUA algorithm regret is similar to the one provided by [12] but in upper-bounding it we have an additional term. Adapted from [12] for the regret decomposition we have: Following same steps as of [12] one can write: T t=0 and From given side information (see (12) in Assumption 2.3), one can writē Combining (47) with (43) and (42) under the events F i * for t ≤ T i * c and F opt T ∩ E T for t ≥ T i * c the regret can be upper-bounded as follows: Now, we proceed with bounding the regret bound terms individually. Lemma 4.1: with probability at least 1 − δ/2 for t > T rc the term R 1 is upper-bounded as follows: + k c,4 n(σ ω + ||B * ||σ ν ) 2 T ω log(nt/δ) (49) for some problem dependent coefficients k c,1 , k c,2 , k c,3 , k c, 4 .
Proof: Proof follows as same steps of [12], with only difference that exploration phase is done with the actuating mode i * with number of actuators d i * .
The following lemma upper-bounds the term R 2 .
Lemma 4.2: (Bounding R 2 ) On the event E ∩ F , it holds true that the term R 2 defined by (45) is upper-bounded as |R2| ≤ 2Dc i * 2 (n + di * ) 2(n+d i * ) (n + d) in whichλ The proof can be found in Appendix VII Lemma 4.3: The proof can be found in Appendix VII. The only remaining part is upper-bounding the term R 0 given by (48) which is the direct effect of "more exploration" step on the regret bound. The following lemma adapted from [12] provides this bound.
Lemma 4.4: (Bounding R 0 ) On the event E ∩ F i * , the term R 0 defined by (48) has the following upper bound: where The following theorem by combining the terms for individual terms, gives the regret upper-bound.

V. SIMULATION RESULTS
In this section, we investigate the effect of actuator redundancy and possibility of switching between different set of actuators on the boundedness of state trajectory. For this aim, we consider a control system (adopted from [21]) with drift and control matrices to be set as follows: The inputs to the OFU algorithm are T = 10000, δ = 1/T , λ = 1, L = 0.1, s = 1 and we repeat simulation 10 times. we consider two cases of different in the actuating mode used for initial exploration phase. For first case, we perform this step with actuating mode i * (to be specified by the Algorithm 2) and for the other, all of the actuators are exploited to this aim. The time duration of initial phase for both cases is obtained by the Algorithm 1. At time T c , the Algorithm 3 comes to play which is applying optimism without more exploration noise on full actuation mode.
It has graphically been shown in [21] that the objective function J(Θ) = tr(P (Θ)) is generally non-convex and when it comes to one dimensional system (n, m = 1) it is only convex in drift matrix, A. Because of this fact, we decided to solve optimization problem (17) using a projected gradient descent method, with basic step Θ t+1 ← P ROJ Ct(δ) Θ t − γ∇ Θ (tr(P (Θ))) where ∇ Θ f is the gradient of f with respect to Θ. C t (Θ) is the confidence set, P ROJ g is Euclidean projection on g and finally γ is the step size. Computation of gradient ∇ Θ as well as formulation of projection has been explicited in [21], similar to which we choose the learning rate as follows: We apply the gradient method for 200 iterations to solve each OFU optimization problem and apply the projection technique until the projected point lies inside the confidence ellipsoid. The simulation results will be provided soon.

VI. CONCLUSION
In this work, we proposed an OFU principle-based controller for systems with actuator redundancy, which combines a step of "more-exploration" (to produce a stabilizing neighborhood of the true parameters while guaranteeing a bounded state during exploration) with one of "optimism", which efficiently controls the system. Due to the redundancy, it is possible to further optimize the speed of convergence of the exploration phase to the stabilizing neighborhood by choosing over actuation modes, then to switch to full actuation to guarantee an O( √ T ) regret in closed-loop, with polynomial dependency on the system dimension.
A natural extension of this work is to classes of systems in which some modes are only stabilizable. Speaking more broadly, the theme of this paper also opens the door to more applications of switching as a way to facilitate learning-based control of unknown systems, some of which are the subject of current work.