Online Optimal Tracking of Linear Systems with Adversarial Disturbances
Authors: Farnaz Adib Yaghmaie
Hamidreza Modares
Venue: Accepted by TMLR ()

Abstract: This paper presents a memory-augmented control solution to the optimal reference tracking problem for linear systems subject to adversarial disturbances. We assume that the dynamics of the linear system are known and that the reference signal is generated by a linear system
with unknown dynamics. Under these assumptions, finding the optimal tracking controller is formalized as an online convex optimization problem that leverages memory of past disturbance and reference values to capture their temporal effects on the performance. That is, a (disturbance, reference)-action control policy is formalized, which selects the control actions as a linear map of the past disturbance and reference values. The online convex optimization is then formulated over the parameters of the policy on its past disturbance and reference
values to optimize general convex costs. It is shown that our approach outperforms robust control methods and achieves a tight regret bound O(√T) where in our regret analysis, we have benchmarked against the best linear policy.

Published in Transactions on Machine Learning Research (04/2023)
Online Optimal Tracking of Linear Systems with Adversarial Disturbances
Farnaz Adib Yaghmaie
farnaz. adib. wdwb.dddbbbhhhoaee yoghmaie
Faculty of Electrical Engineering Linköping University Linköping, Sweden
Hamidreza Modares
modaresh @msu edu
The Deportment of Mechanical Engineering Michigan State University Michigan, USA
Reviewed on OpenReview: https: openreview. net/ forum? id= 5nVJ1Kgmaa
Abstract
This paper presents memory-augmennted control solution for the optimal reference tracking problem for linear systems subject to adversarial disturbances. We assume that the dynamics of the linear system are known and that the reference signal is generated by a lincar system with unknown dynamics. Under these assumptions, finding the optimal tracking controller formalized as an online convex optimization problem that leverages the memory of past disturbance and reference values to capture their temporal effects on the performance. That is, (disturbance, reference)-action control policy is formalized, which selects the control actions as linear map of the past disturbance and reference values. The online convex optimization is then formulated over the parameters of the policy on its past distur and reference values to optimize general convex costs. It is shown that our approach out outperforms robust control methods and achieves a tight regret bound of O(VT), where in our regret analysis, we have benchmarked against the best lincar policy.
1 Introduction
Reference tracking is one of the key concepts control theory [sidorii 1989 Huang 2004). In the reference tracking problem, the aim is to design a controller such that the state of the system tracks a desired reference trajectory. There are typically two common approaches for the reference tracking problem [Isidori] 1989: Huang 2004). The first approach is called the "feedforward design". In this approach, the controller is summation of i) feedforward term depending on the reference signal, which is derived from the dynamics of the system and reference generator, and ii) an internal state feedback to stabilize the system in the a absence of disturbances. The second approach is called the "internal model". In this approach, a dynamic controller contains an internal model of the reference signal, and the control signal is a feedback from the internal state of the controller and the state of the system. As a specific internal model approach, a proportional-interratte (PI) controller contains an integrator so it can be used for tracking a constant reference signal rejecting constant disturbance. Both internal model and feedforward approaches require the full knowledge of the system dynamics and reference signal generator dynamics.
The asymptotic reference following is the bare minimum requirement for the tracking control problem. To account for the transient response and the overall performance of the control design, an optimal reference tracking control problem is typically formalized and solved. One major factor that can adversely affect the performance of the tracking controllers is the presence of disturbances, which is typically ignored in the
optimal reference tracking problem (Zhang et al.] 2011 2008 Huang & Liu 2014 Kamalapurkar et. al. 2015

---

Published in Transactions on Machine Learning Research (04/2023)
Adib Yaghmaic et al. 2019 Modares & Lewis 2014 Kiumarsi & Lewis 2015; Kiumarsi et al.
2014 2015
2018 Vanvoudakis et al., 2017 Carrillo & Vamvoudakis 2020 Vamvoudakis & Lewis 2012). In practice, dynamical systems might be affected by external disturbances originating from the environment or produced by adversaries to deteriorate the tracking performance. To account for the effect of the disturbance, it is common to assume one of the following: the dissturbance is generated by a dynamical system (Isidori 1989 Huang 2004); 2- the disturbance is Gaussian (Bertsckas] 2012), and 3- the disturbance is energy bounded and the effect of its worst-case realization is attenuated on the control performance in the robust control terminology (Doyle] 1995). In most cases, however, the disturbance is neither Gaussian nor generated by dynamical system. Besides, the robust control approach yields conservative results because the disturbance is most likely far away from its worst-case realization (Khalil 2002p. In the related works, we discuss each case in detail.
In this paper, we design optimal tracking controllers for linear systems subject to adversarial disturbances. The adversarial disturbances are arbitrary and thus are not limited to those that are generated by a dy- namical system. The reference signal to be tracked is assumed to be generated by linear system with unknown dynamics. We assume that only the output of the reference is measurable. We design (distur- bance, referoncee-actiion control policies where a fixed-size history of disturbance and reference values are used to parameterize the proposed policy. This is partially inspired by Agarwal et al. (0119) Zhao et al. 2022), which are designed for solving the optimal regulation control problems. In contrast, we leverage the past values of both of disturbances and reference values. Using the past history of reference values is moti- vated by a classical result giving necessary and sufficient conditions for tracking in control theory. Indeed, our proposed policy belongs with the feedforward approach to solve the tracking problem. Our approach rosults in neat paramcterization of the control policy from which any general convex cost function can be optimized using online convex optimization. Indeed, prove that the cost function is convex with respect to the parameters of the presented controller.
The resulting algorithm is online in contrast to rollout or batch-wisc reinforcement learning (RL) algorithms, where it required to collect enough samples before updating the controller (Abbasi- et al. 2014] In sharp contrast to the robust control design approach, a history of fixed-size past disturbance and refer- ences values are calculated, stored, and used by the control policy avoid hedging against the worst-case disturbances that rarely occur in reality (Khalil 2002: Modares et al., 2015). We show that our proposed al achieves tight regret bound. Simulation results compare the presented approach against the H control as well as the LQR control to show its superiority.
2
Related works
In this section, we summarize related works to the problem of optimal tracking in the presence of disturbance.
2.1 Tracking in the presence of disturbance
Depending on the nature of the disturbance, different strategies can be followed.
Output regulation theory The output regulation theory [Isdori 1989 Huang 2004) has been widely used
to design model-free RL algorithms for solving the optimal tracking problem (Gao et al. 2017 Chen et al.
2022 Jiang et al. 2020b). It has also been leveraged to attenuate the effect of disturbances (Chen et al. 2019
Jiang et al. 2020a Gao & Jiang 2016 2015). Even though RL and adaptive dynamic programming (ADP) approaches based
the output regulation theory can deal with both the optimal tracking problem and disturbance rejection, the disturbance is assumed to be generated by dynamical system. This, however, is rarely the case in most real-world applications, which limits the applicability of the output regulation theory. Besides, ADP hoth optimize a risk-neutral (expected) or risk-aware measure of the cost function under the assumption that the noise is at least i.idd and mostly Gaussian. This is because either the value function is directly learned (policy interaction or value itcration methods) based on collected data to estimate the expected or risk-aware accumulated rewards, or the expected or risk-aware cost function or its derivative with respect. to the control parameters is learned directly using data (policy gradient methods).
2

---

Published in Transactions on Machine Learning Research (04/2023)
Gaussian disturbance: For linear systems with Gaussian disturbance (noise) on the system dynamics and noise on the system's 8 state measurements, linear quadratic regulator (IQRR) control can be used to design an optimal controller for the regulation problem by minimizing quadratic cost (Bertsekas) 2012). The foedforward gain is then calculated using the full knowledge of the dynamics of the system and reference. However, there are many control systems for which the distribution of the disturbance is not Gaussian.
For general but limited-energy disturbances, one can use the -control theory to guarantec an Lz-gain performance bound (Doyle) 1995 Khalil 2002] Modares et al., 2015). The Ho approach is typically overly conservative the resulting robust controller hedges against the worst-case disturbance sequence, which rarcly occurs in reality. A daunting challenge is to design non-conservative optimal tracking controllers for systems with arbitrary adversarial disturbances that do not follow assunptions such as being generated by an i..d. Gaussian noise sequence or by a dynamical system.
Robust control design:
2.2 Notion of Optimality
To account for the transient response and the overall performance, one can introduce optimal control design to the tracking controller problem. This is usually done by designing (some part of) the controller by optimizing performance index using the optimal control theory or reinforcement learning.
Average or discounted costs: In Zhang et al. (2011 2008); Huang Liu (2014); Kamalapurkar et al.) (2155) Dierks & Jagannathan (2010) feedforward approach is used to solve the tracking problem. The feedback part of the controller is designed by minimizing an average or discounted cost in reinforcement learning frameworks, and the feedforward part of the controller is found by dynamic inversion, assuming
that the dynamics is known.
Similarly, Adib Yaghmaie et al. 2019 Modares & Lewis (2014); Kiumarsi & Lewis (2015) ; Kiumarsi et al. (2014 2015) consider a feedforward approach to solve the tracking problem. But this time, both feedback
and feedforward parts of the controller are designed optimally by minimizing average cost (Adib Yaghmaie
et al. 2019) or discounted cost (Modares & Lewis 2014 Kiumarsi & Lewis 2015 Kiumarsi et al. 2014
2015).
The regret compares the performance of an online control algorithm with a fixed policy in hindsight. In the context of control theory, the regret analysis is usually given in the regulation problem where there is no reference signal to be tracked, and the aim to make the state vector converges to zero (Agarwal el al.
Regret:
2019
Zhao al. 2022).
In Yadkori et al. (0014), tracking adversarial reference trajectories with quadratic costs is considered. There are no disturbances in the problem formulation, and the regret grows as Olog" N), where N is the
number of rollouts. Tracking adversarial references with convex costs is considered in Zhang et al. (2022)
where an algorithm is given to estimate the state of the system based on observed data. The control signal is then generated by an algorithm, however, in control theory, the control input is usually parameterized.
Examples of parameterized controllers are state feedback or disturrance-action policy (Agarwal et al. 2019)
where the control input is parameterized based on the state or disturbance and the parameters are gains that are designed. Parameterization of the controller allows analysis in the context of control theory. Since the control signal is not parameterized in Zhang et al. (2022), it is difficult to perform analysis in the context of control theory. It is shown that the regret is Olv [Z] for time interval I in the time horizon [1,T].
3 Optimal Reference Tracking Problem
Notations and preliminaries: Let I denote identity matrix with appropriate dimension. Let 1 and 0 denote one and zero matricos with appropriate dimensions respectively. Let Vzf denote the gradient of function (xx with respect to x. The Le-norm of x is denoted by | = (Σ tor [|<x where || is k=
the instantaneous Euclidean norm of the vector Ik- For matrix A, the spectral norm is denoted by ||A|] and the Frobenius norm is denoted by | Let Ig be an indicator function on set E. For a time-dependent variable Iy, the notation Tz:j. j 2 is defined as Tzz (2,, Z441,.,, 2, The notation O() is leveraged throughout the paper to express the regret upper bound as a function of T.
3

---

Published in Transactions on Machine Learning Research (04/2023)
Definition 1 Agarwal et ol. 2019 Consider
Tk+1 Ax + Bug
and Y E [0, 1), K > 1. linear controller (stabee of || S x and ||x2l2 & x² 7) vA 20 20 0
where AK BK.
3.1 Dynamical System and Reference Signal Consider the following linear dynamical system
2R+1 Az + Buy + Wks
(1)
where T& E Rn and Ug E R denote the state and the control input of the system, respectively. wk E R" denotes the adversarial input, which captured by general (i.c., arbitrary and unknown) disturbance. The only assumption on the disturbance that it is bounded. We can assume without loss of generality that 20 and push the initial condition into wp-
Assumption (dynamical system) The pair (A, B) is known and stabilizable. Moreover, the system matrices are bounded, i.e., ||A||| S Ki and || Ir.. Rs.
Assumption 2 (disturbance) The disturbance sequence wy is bounded, i.e., || S Kiw for some Bew > Moreover, Wkk = for < O.
Since the system dynamics are assumed to be known, at each time k, wick-1 are known. This is because Wk-1 = Ih- A Buk-1 and the state is assumed measurable.
Remark 1 Assumption 1 is standard one. If the dynamics are not known, one can use Algorithm 2 in
Hozan et al. (2020) and identify the dynamics by injecting random input to equation 1 In Assumption we make a standard assumption that the disturbance is bounded.
Our aim in this paper is to select the input us such that the state the system Ty tracks an unknown linear reference signal Te generated by
1k+
SZk:
(2)
F=k.
where E R and E R denote the state and output of the reference signal, respectively.
Assumption 3 (reference signal) The following assumptions are made the reference signal
The pair F) unknown, but observable.
The state of the reference signal z₁ is not measurable but the output r is measurable.
The reference signal rk is bounded, i.e., ||rall S Kyr
Remark 2 Even though this assumption does not cover all types of references, it can generate lorge class of useful command trajectories, including unit step, sinusoidal waveforms, damped sinusoids, etc. Assump- tion 3 requires the reference signal to be bounded, because otherwise, the average cost defined later becomes wnbounded. Therefore, Assumplion 3 is usually considered when sludying average cost, see for example Abbasi- Yadkori et al. (2012), Adib Yaghmaie et al. (2019). Tracking unbounded reference signals can be studied in the discounted cost settings where possible guarantee the boundedness of the discounted cost by selecting the discounting factor properly, see for example Kiumarsi al. 2014)). Relaring Assumption is direction of our fulure work.

---

Published in Transactions on Machine Learning Research (04/2023)
We first bring classical result in Theorem speciffiigg the necessary and sufficient condition for the existence of linear feedback policy to solve the classical state tracking problem, i.e., to ensure that - rk, in the absence of disturbances. A linear feedback policy is defined as follows
Uk (Ky) = K f6 + K
where Ky yt Kyrl E K. and K. (Ky A BK (K, 7) stable).
The following theorem is based on Theorem 1.35 and Remark 1.36 in Huang 2004 and is modified according to the problem setup in this paper.
Theorem Huang 2004)/Theoren (Theorem 1.35 and Remark 1.36] Consider the dynamical system in equalion and the reference signal in equation 2 Assume that wg 0, (A, B) stabilizable and (S, F) detectable. Select Kt such that A + BK strongly stable. Then, the controller
us = K fb + (T K =x
(4)
solves the classical state tracking problem Iy + Th. if and only if there exist matrices 11 E R=xp and I' E Rmxp such that
IIS All BT, I1 F=
We show in the next lemma that even though 2k is not measurable, it can be extractable from the current and past outputs of the reference the dynamics of the reference are known.
Lemma 1 Assume that (S, F) is observable. Let I denole the observabilily index of equation i.e., the smallest positive integer 1 such. that
O
E RRdxp
(6)
FS1-1
has full column rank. That is, rank(O;) p. Let
O (OF -0)-
N |NUI] No = 5
(7)
N/ R s= 1, I,....
Then, the state of the reference signal can be expressed as a linear function of the current and past outputs of the reference
2/
NP vl--srr-er
(8)
9=0
Proof: See Appendix
The following corollary uses the results of this lemma to formalize the controller as a memorg-angmentee controller, which depends on the past values of the reference outputs.
Corollary 1 Consider the dynamicol system in equation 1 the reference signal in equation 2 and 0. Assume that there exist matrices II E gaxp and I E mxx such that equation holds. Select Kf such that A + BKys is strongly stable. Then
1-1 -
Jin uk
= K Koot +
(9)
==0
solves the classical track-tracking problem ak Tk, where I is the observability indez of equation given in equalion] 7
and N is
5

---

Published in Transactions on Machine Learning Research (04/2023)
Proof: The proof is based on Lemma 1 and Theorem
The controller in equation | only guarantees asymptotic convergence of the system's 's state to the reference trajectory. To account for the performance, an optimal state tracking controller is typically designed by
optimizing a cost function with respect to the control gains. However, the controller in equation (equation
9
requires the knowledge of IT (II and N), which is found by solving equation (equation and equation
which in turns requires the complete knowledge of the reference dynamics. As stated in Assumption 3
this knowledge is typically not available. Besides, the disturbance is either ignored in this control design approach attenuated using wverly-conservativy robust control design methods. Therefore, to account for the unknown dynamics of the reference generator and to design non-conservative controllers against adversarial disturbances, a new controller is designed in the subsequent sections that leverages the past disturbances and reference values to capture their temporal effects on the performance.
3.2 Optimal (essturbnceeRRferennce)) -cctiero Action Policy Design
The overall objective of this paper is to design a control policy (I1:k) W1.-1, - up that optimizes an average cost function that captures the intention of the designer. The average cost associated with a policy w is defined as follows
T (e ux),
Jr(T) = T
Σ k=1
(10)
where Ck is the rolling cost, and
Ck = Ik Tk-
(11)
is the state tracking error.
Assumption 4 (cost function) The cost calek, ux) is conver in Ck, Wk- Moreover, when ||e]| |ul| S D, it holds that (cx(ex, ux)l < 3D2 and ||Vect(e, u)ll, V/V u)ll < G.D for some B > O and G. > 0.
Assumption 4 limits the cost function to general convex functions, which is more general than typical quadratic cost functions. To optimize this cost function, the following parameterization of the control policy is leveraged.
Definition 2 (Memory-auumnented Control Policy). A (disturbance--r/frrnneee))
policy π (K, M, P) with memory is specified by parameters M [M ..... Mim--1l -I1,, P [P(O)... "im,,.,,...11) p(m,- and fized matrix K. At every time k, this policy chooses the action uk at state a& using the following parameterized controller
u (K, (K, P) = Kr + Σ Ml
pl
(12)
Since the policy parameters will be learned, and thus are changing over time, we refer to Mr =
[M(0) ..... Mm mm--ll) and Pk = [P[0] .... pmm plm as the policy parameters at time k.
We call the controller uh in equation 12 a memorg-augmented control policy which is linear in the state Ti. the history of the reference signal of length m, and the history of disturbance of length ma
Similar to Agarwal et al. (2019); Zhao et al. (2022), we make the following assumption on the control parameters M, P. This assumption is a prerequisite for proving the theoretical results related to our algorithm. It is enforced by using projected gradient descent the algorithm.
Assumption 5 The control policy n (K, M, P) in Definition
salisfies
The control gain K makes A + BK (1s, 7) -strongly stable.

---

Published in Transactions on Machine Learning Research (04/2023)
The control parameters Y [M, P| satisfy Y E y with domain y { [M M1 plol Plm-- 1I] ||M||]|, ||P|o|||| S ny (1 - 7))
Remark 3 In the absence of the reference signal O, Vk, the controller in equation 12 is simplified to the disturbance-action policy in Agarwal et al. (2019). The optimal reference tracking problem leads to a challenge of designing the controllers parameters such that the output regulator equations in equation P are implicilly solved by solving the optimal control problem. Note that one does not need know to design the controller. Indeed one can select my large enough. In Theorem 4 we specify how to select mays my-
Problem (Optimal Tracking Against Adversarial Disturbances): Consider the system in equation 1 under Assumptions [ and [ Let the reference signal be generated by equation 2 under Assumption 3 Design an
algorithm or control policy that generates the control actions in the form of equation 12 optimize the convex cost function in equation
10
As we discuss in the sequel, we aim to propose an algorithm to learn the parameters M and P in equation 12 to achieve optimality. Even though other control techniques, such as Lyapunov reconstruction and sliding mode control (Khalil 2002) can be leveraged to design robust tracking controllers, they typically only concern the stability of the system and do not. provide guaranteed performance with respect given cost.
4 Properties of nemory-auggeette Control Policies
To solve Problem 1, we select the controller gain K the controller in equation 12 to stabilize the dynamics in the absence of disturbance wy and reference Tg- We keep K unchanged and aim to learn M and P to achieve optimality. The learning procedure is given and discussed in detail in Section 5 Before presenting the learning algorithm and proving its regret analysis, the following results are needed.
For the standard linear controller in the form of equation 3 in the presence of an adversarial or arbitrary disturbance, the Hx control design finds the gains Kfs. Kyf to attenuate the effect of the disturbance on the cost function. However, besides its conservativeness, as shown next, the cost function cx(Ex, ux) is not convex in Ksb. Kff, which makes the online control design intractable. To circumvent this difficulty and to avoid the design of an overly-conservative controller, a controller in the form of equation [2] is designed. We show next that, first, the cost function ce(ER, Uy)) is convex in M, P (see Lemma 2 and, second, equation 12 approximate any linear feedback policy in the form of equation 3 (see Theorem 2 Therefore, the presented memory augmented or (disturbance, sitreence-actioon controller is favorable over the linear feedback policy lin
Lemma 2 Consider the dynamical system and reference signal in equation D lequuatio Then, the cost
function (x(e,, Uz) is convex in M, P for the memory-anggentee controller in the form of equation 12 but is not conver in Kyb, Ks5 for the memoryless controller in the form of equation
Proof: See Appendix
Remark 4 Based Lemma g the cost function cx(e,, uk) is conver with respect to the parameters of the memory-aaummnnted comtrol policy in equation 12 This allows online oplimization of the paramelers of the memory-augmenteed control policy for streaming settings using gradient descent. Nevertheless, as shown in Lemma 2 the oplimization problem in hand is not conver in the gains of the linear feedback policy, which makes it intractable for online learning.
Since the policy parameters will be learned, they change over time. In this case, the following Lemma shows that the state at time depends on the entire past memory of the control parameters. Let Åg = + BK and define
h-1
T (ME- = AV Ty + ky
Σ
My BMM---11
I1sy-jSm
(13)
1=
7

---

Published in Transactions on Machine Learning Research (04/2023)
h-1
K.h Vkz (PR
(PR-h-1A-1)
Σ
Ag kーÿ-1 11ss- - j=0
(14)
Lemma 3 Let zi be the state attained upon execution of the policy a (K, Mock-1. Po:k-1) that generates the control input in equation 12 at time k. Then, assuming 2a 0, one has
myy m=-111
x 2h (Max- Po:k-1) = K
V W (Ma-A n- 1:k 1))-
(15)
mh+h-1
K.h
V,,
2=0
or equivalently
2 2t (Moxk (M
Σ k, (Mark
Kik v
(Ma
+
Kik kkz (Pok-1)rk-=
(16)
2=0
Proof: See Appendix
The result of Lemma 3 shows that the memory length grows with time, which is not feasible for developing an online gradient descent-based algorithm for learning the policy parameters. Inspired by Agarwal et al.
(2019), we present Iruncated method that truncates the stale with fixed memory lengths for both the disturbance and the reference. We also define a truncated cost accordingly.
More specifically, truncate the state with fixed memory length H. Let #T uh. for denote the truncated state, inpul and cost if the system would have started at 4h 0. By setting H = lh in equation 15 and using equation
12
27 ug read
(M -1:k 11 Pa- H- 1:k-11)
(17)
H1 11
m, H 1-1 Σ
Σ
K.H
k.y (Ms
lsk 11M
+
Wk,z
K.H.
(Pr PR--H-1e H- 1:k 11k-1)rr-ss
y
2=0
T7. (Mp H1 lske Pk- 11 1:k))
(18)
ma
m.
Kī M Pe- --1--1)
Σ
M [t-1]
Wh Wh-t +
Σ
pla)
Tk-ss
and the truncated cost fa reads
7MMM-H-1i- Ma-1, H- Pb-1)
(19)
c3l (M& MM-HH-HH --1:- P8-H-11k-1) Tke 2x (Mk- H Px-H-1sk))
Remark compute the truncated state, input and cost numerically, one starts from H%- and steps the following dynamics
J ArT B Wt-
for H steps to get øg. At each E [A: H, k 1]. a, is calculated from equation 18 using the past values of the disturbance and reference. Then, the truncated cost is calculated by using a7. 4g in Ck.
In Appendix we bring several lemmas which will be used to prove the main results in Theorems Specifically,
8

---

Published in Transactions on Machine Learning Research (04/2023)
Lemma
gives bounds for T K.A K.h k,y k, in equation 13 equation 14
Lemma gives bounds the states and inputs.
Lemma 0
gives the tracking error bound.
Lemma defines the Lipschitz condition on the truncated cost.
Lemma gives bound on the gradient of the truncated cost.
Theorem 2 Consider the dynamical system and reference signal in equation I equation 2 Let Assumptions
1
hold. Let denote the observability inder of equation _ Let us in equation a linear feedback
policy with yt being (N, -lsorongly stable. Then, for any (K, -tstrungyy stable K, there exists a memory augmented policy of form equation 12 with S m, and
Mi (K K)(A+ + BK OSt< m
(20)
60 = Kyy,11
(K - K) BKt))* 2-1 BKI,,NN- (KKK)> 111-1)
pbl
E
0 s my:
such that uzy in equation
12 approrimates uk in equation Let Assumption 5 hold. For > max(m m,)
||uk Kin
wIll -xxnk33 (1-1 m
Kew + - 3 m Ke..
Proof. See Appendix
Remark 6 In Thcorem 3 proved that equation 12 can approzimate equation 3 According to equation since ||uter u is function of (1 m and " the approcimation error decreases for longer history lengths mw, my.
We have seen in Theorem that a memory-augmented policy ug can approximate the linear feedback policy in equation In the next theorem, we show that if we use u and up for the same system in equation with the same sequences of disturbance, the corresponding trajectories zt and 2y are close.
Theorem Consider the dynamical system and reference signal in equation 7 eequaaionn 2 Let Assumplions 5 hold. Let L denote the observability inder of equation 4 Assume that Kt and K are (n, (mstonst stable. Let r denote the trajectory of the system using the memory-augmmntted control policy u in equation 12 with
the paramelers in equation 20 and att denole the trajectory of the system using the linear policy uk So in equation 33 Assume that Wk-is Tk-is i < l are the same in both cases. Then 27 is close to xk More specifically for k >> max(mw: m.)
Nin x1ll S 2ni, x2 Tm Kon 7 2 m Kr. ||
Proof. See Appendix F
5 Memory-augmented online state-tracking algorithm
In this scction, we will give an algorithm to tune the parameters of the lincar menory-angmented policy u in equation 12 namely M, P to provide optimality in terms of minimization of the average cost. in equation 10 Note that we consider optimizing over the class of nemory-augmented policies ug in equation [2] not the class of linear feodback policy us in oquation 3 The reason is that Cg convex with respect to M, P appearing in of but is not convex in KJb, K₁ in lin see Lemma 2 The following Algorithm optimizes the truncated cost. fe using the gradient descent method.

---

Published in Transactions on Machine Learning Research (04/2023)
5.1 The memory-augmented algorithm
Algorithm summarizes the online state tracking procedure. In Line 1, the algorithm is initialized by selecting & stabilizing controller gain K and setting M, P arbitrarily. One way to select K is by solving a Linear Quadratic Regulator (LQR) problem. After initiating the algorithm, the online procedure starts. In Line 3, the current output of the reference signal rkk is recorded. Then, ui equation 12 calculated and applied to the system. Then, in Line 4, the next state of the system 2k+1 is observed and the disturbance wk is recorded. In Line 5, the algorithm suffers the cost ca(es, wx). Then, the truncated state and imputs calculated from equation equation 18 using the latest values of M1 P and the truncated cost (MM,,..., M, P.... P.....) P) is computed from equation 19 In Line 6, the weights M, P are updated using
projected gradient descent on the Iruncated cost (M,,,., M, P...,,,, see equation 21 where aas, P denote projection onto the set of matrices with appropriate dimensions and bounded norms as specified in Assumption 5 and v is the learning rate.
Algorithm Online state tracking algorithm
1: Initialize: Select a stabilizing K and set M, arbitrarily.
for k I,..,T T do
Record F and execute ug in equation 12
Observe Jh+1 and record we Ix+1 Ax Buk-
5: Suffer (e(e,, Ug). Compute fa (M, ..., M, ....,.. P) in equation 17 lequation 19
6: Update M, P
M a (M 1/V M/MM ...., M.P,...,PP) [p - V/Ph (M,,,, M...... ()).
(21)
Remark 7 Algorithm is online: it updates M, P in each time step to minimizefi M. M.P..... P...,. ca (o M, P. P...,, P) P)- (M,,.., P.....P) Since ug approzimates uhi (see Theorem 2 Algorithm 1 tries to approzimate a linear feedback policy minimizing the cost cp. There are two important characteristics for Algorithm. 0 1) The cost. function Ck does not need to be quadratic but conver. Note that in the classical approaches the cost is quadratic [Bertsekas] 2012; Khalil, 2002). 2) Purameterization of the controller w based on the recent values of wk and rk; and online luning help us to approzimate the best lineur feedback policy for the recent values of wh and Tk. Clearty, it less conservative than selecting the linear feedback policy for the worst case disturbance in the Hoo method. This results in lower average cost; see the simulatioo resulls in Section 0
Note that at each time step k, W11:k F1:k are known (see Lines 3-4 in Algorithm 1 and wh. 0 for k < 0 (sce Assumptions and As such, equation 17 equatiin 19 are computable.
5.2 Regret Analysis
The standard measure for online control based the gradient descent is the policy regret (Agarwal et al. 2019), which is defined here as the difference between the cunulative cost of the designed parameterized control policy learned by Algorithm and that of the optimal linear control policy in the form of equation 3. The reason for selecting the class of linear policies as the baseline is twofold. Firstly, since we do not have any information about the disturbance, we compare it against the best policy when there is no disturbance in the system which is the class of linear policies. Secondly, we select the class of linear policies so that the thcoretical analysis of the regret possible.
Definition 3 Consider the system in equation 1 Let the control policy be deigned generate the control action uy in equation 12 al time k. Let Algorithm be used to update the parameters of uk- Then, its vegret
10

---

Published in Transactions on Machine Learning Research (04/2023)
is defined
Regret
(ek, un)
min (J)(K))
(22)
KyeK
where ( is the average cost in equation 10 of the linear feedback controller in equation
The regret compares the performance of Algorithm generating controllers from the class feasible memory- augmented control policies with the best linear control policy in hindsight.
Theorem Suppose Algorithm | is executed under Assumptions 1 6
Let = mw = my. For a fixed T,
select the learning rate y and the memory size satisfy 1j = and H O T) solve Problem
1. Then,
Regret = =(VT)
(23)
Proof: See Appendix
According to Theorem the average cost; ie. + Σt calex, us) is always bounded when the parameters are learned
T Ck(ck: u+) S min
Σ
(ex, ux) + 00 }
(24)
T
T
KyEK
VT
The above inequality gives an upper bound for the average cost by Algorithm
6 Simulation results
In this section, we give our simulation results.
6.1 The dynamical system, reference and cost function
We consider the dynamical system as
0
Fk++1
1
Kk
0
1
Uk + Wk:
(25)
and the reference signal is generated by
0
1
1.5
0
Zk:
20
[1, -2, 0.5]T.
0
1
(26)
0
Zk.
where
Ti1k Ø22
[iik]
Frie
[ex
Tik lik
Fk =
wk
rk
Cx: =
w2k
r26
E2R
T2k r2k
We consider a quadratic cost with Q 20Iz,
Iz; that
C* = o Qex + uh Rug-
Note that the algorithm can handle any convex cost function. The choice of quadratic cost enable comparison with the classical control approaches like Linear Quadratic Regulator (TQR) and Hos controllers.
11

---

Published in Transactions on Machine Learning Research (04/2023)
6.2 Disturbances
For the simulation, we consider 6 cases for the disturbance. In each case, we generate the disturbance in the beginning of the simulation so the disturbance sequence is the same for all algorithms. In the first three cases, the disturbance is randomly generated. They are useful for comparing algorithms for stochastic disturbances. For the others, we consider continuous disturbances; they are useful to study the performance of the algorithms when the disturbance not stochastic.
Gaussian disturbance: Wik ~ (0, 0.01), w22 ~ [0, 0.01). is well known that the LQR the optimal controller for the stabilization the system in equation (ertsekas) 2012). Note that the support of the Gaussian noise is not finite, even though our theoretical results require the disturbance to be bounded. This bound, however, does not need to be known and could be large. This is in contrast to the robust control methods such Ho. In our simulation results, the Gaussian noise generator goumpy.raudom.norass. by Numpy in Python is used which generates bounded samples.
Random walk disturbance: Wi 0.999wt--1 n Ij-11 N(000.01): When the noise is random walk, the optimal controller is LQR. To see this point, replace the random walk disturbance in equation
JK+I = Arx + Buy + 0.999wk-1 1 + 7----
Note that in each time step k, the state an is measured and according to Assumption Wi-1 is known. Introducing new state variable T2 = [ wh-1h we have
A 0.999/
B
1 0
0
0.9997
Ik +
u
+
T1--1-
(27)
Hence, equation with random walk disturbance can be seen as the extended system in equation 27 where the noise T is Gaussian. As result, the optimal controller is the LQR for the extended
system in equation 27
Uniformly sampled disturbance We assume that the disturbance is uniformly sampled from the interval [0,1].
Constant disturbance: Wik W22k 1.
Amplitude modulation disturbance: Wik W22 sin (67kk/000 sin (8*k/ /500).
Sinusoidal disturbance: Wik = w2k = sin(87k/100),
6.3 The compared control approaches
We compare our online tracking algorithm with some other linear control classes such as the LQR and Hoo control approaches: both of them optimize quadratic performance index and they are also optimal for the Gaussian and worst-case disturbances. As such, they present the best possible performance for an algorithm for example when the disturbance Gaussian or worst-case. We would like remind the reader that LQR and Lincar Quadratic Gaussian (LQG) controller states are assumed measurable. We use the lerminology of LQR in this paper. We also compare our online tracking algorithm with a combination of the online control algorithm in (Agarwal et al. 2019) and the feedforward approach. Other adaptive algorithms which do not optimize performance index or do not consider disturbance in the dynamics are not included.
sometimes used interchangeably when the system's 's
In our simulation results, we study the following algorithms:
Online state tracking in Algorithm 1 Let P, be the solution to the Algebraic Riccati Equation
ARE(A, B, Q, R). We select K in equation 12 as
K=-(R+ BT P
(28)
12

---

Published in Transactions on Machine Learning Research (04/2023)
We keep K unchanged during running the algorithm. We set H = 5, m, = mw = 5, 1) 0.0001 and initialize M 0, P 0 We do not use any information about the dynamics of the reference signal; we only use measured outputs of the reference signal rhe in this algorithm. We also do not use any information about the disturbance in this algorithm.
Online control algorithm with a fixed feedforward gain: It possible to combine the online control algorithm in (Agarwal et al. 2019) with feedforward approach. We call this approach Online control algorithm with a fized feedforward goin:
1. Learn observable canonical realization of the reference generator using measured data.
2. Select K to stabilize the system's 's dynamics and compute Kff = - KF oflline. Keep K, Kjf unchanged during running the algorithm.
3. Run the Online control algorithm in 4Agarwal et al. 2019 and learn M. Equivalently, run Algorithm by replacing ug in line with
- = Kork +
Σ Mk- + K K5fzk
(29)
and skipping updating P in line 6.
The initial motivation for considering equation 29 is decouple the feedback and feedforward design, to design the feedforward gain offiine and the feedback gains online. Let eg rk- Using equation
ma
ck+1 = Tk+1 Tk+1
Ax + BKr
B
M
Wk- B(T KF) FS2
mew
(A+ (A+BBKaa, BK)a+ B
Σ 1=1
11
B(T KF)2# (AF BT)
(B)((xx - F2A) + M Wk-1 (A+ BK)ex + B
M tt M Wk
1=1
For our simulation results, we select K similar to Algorithm 1 1k= (R+ Dd P,B) P.A where P. is the solution to the Algebraic Riccati Equation ARE(A, B, R).
LQR and LQR for random walk: We apply the controller in equation We select Kyo -RRBBTP. P.B)- A where P, ARE(A, B, Q, R). We assume that we know the dynamics of the reference in equation 26 We then compute K₁ according to equation eequation 5 To apply equation 4 we need to know the state of the reference zt. We use the dynamics of the reference in equation 26 and build zy from according to Lemma Then, we apply 4n = KPTT + Kjjžk.
Note that Kys is the optimal feedback controller gain for stabilizing the system in equation 1 with Gaussian disturbance we and the quadratic cost using full information of the dynamics (Bertsekas) 2012).
We saw in Subscction 6.2 that when the disturbance is random walk, one extend the dynamics according to equation 27 The exlended dynamics has a Gaussian disturbance and as result, LQR for the extended dynamics is the optimal controller. In this case, we call the algorithm "LQR for random walk""
Hs-control:: In the Ho:: the controller is defined have finite Lz-gain with respect the worst- case disturbance. The Ho controller of the form in equation 4 We design Kys for the system in
equation such that I @ < 1.5. Note that 1.5 is the best achievable Le-gain for this system. |w
We assume that we know the dynamics of the reference in equation 26 We then compute Kjj according to equation eequatoo To apply equation we need to know the state of the reference
13

---

Published in Transactions on Machine Learning Research (04/2023)
Z/.- We use the dynamics of the reference in equation 26 and build 2g from Th according to Lemma Then, we apply K f6 + Kz
The control results in a conservative controller as it guarantees finite L2-gain for the worst-case disturbance.
The online control algorithm with a fized feedforward goin might not return on optimal solution. Let K denote the optimal linear feedback gain for the problem setup. If there is no disturbance in equation 7 i.e. wy 0, the associated feedforward gain, according to the tracking theory in Theorem 7 Kj r F. Now, ossume that the disturbance is present and the online control algorithm is used to design the controller. In the online control algorithm, the parameter M is learned such that K + En= M w in equation 29 approrimates K jo see Lemma 5.2 of (Agarwal el al. 2019) or Theorem > in this puper. However, the Jeedforward goin in equation 29 is K5 = K which is clearly diffeernnt from Kÿs. -. It meons that while the optimal linear feedback for the system equation [ learned, the associated feedforward does not change. This may result in higher cost, specifically when K is away from Kj.- Our simalation results clearly confirm this claim.
Remark 8
6.4 Performance during learning
In this subsection, we discuss the performance of the algorithms in Subsection 6.3 for the 6 cases of distur- bance in Subsection 6.2 In Table 1 we summarize the final average cost; 1/2 Σx= (x ux) suffered by the algorithms for 7 = 10000. We use bold to refer to the algorithm with the lowest average cost. in each case of the disturbance.
In Fig. 1 the evolution of the average cost JT = E Ce(k, ux) in equation 10 vs. T for the cases of disturbance in subsection 6.2 has been shown. Algorithm T learns memory-angmented policy in form of equation
12 by minimizing the truncated cost equation 19 as discussed in Subsection 5.1 One can see that
the average cost. for Algorithm decreases as more iterations are done.
When the disturbance is Gaussian and assuming that the dynamics of the reference signal is known, the best linear foedback policy can be found by first selecting Kyt = -(R + BT P P.A where P, = ARE A, B, Q, R) and then computing Kf according to equation Eqquation using the dynamics of the reference. This is the LQR controller which gives the best average cost. From Fig. Ia we can see that the average costs by the online control algorithm with fixed feodforward gain and Algorithm [ approach the average cost with the best linear feedback policy, without knowing the nature of the disturbance. The online control algorithm with fixed feedforward gain has slightly better performance. The reason is that K = K is the optimal feedback gain. As result, the feedforward gain is selected optimally while Algorithm [ learns the feedforward part of the controller. Note that the online control algorithm with a fixed feedforward gain and Algorithm cannot get exactly the performance of the LQR because the memory-augmenteed policy equation 12 an approximation of the linear foedback policy equation 3
A similar discussion is also valid for the case of random-wall walk disturbance, see Subsection 6.2 where we showed that the optimal controller for the system when the disturbance is random walk, is obtained by solving an LQR problem for the extended system.
When the disturbance is not Gaussian or random walk, there is no analytical way to determine the best linear feedback policy. In such cases, usually, the contooltrl used to design a linear feedback policy to guarantce a finite Lz-gain for the worst-case disturbance, and as such it conservative. Indeed, the disturbance is not the worst-case, the rooloorr does not have the best performance. As one can see in Table g and Fig. [ Algorithm [ has lower average costs for uniformly sampled, constant, amplitude modulation, and sinusoidal disturbances.
6.5 Evaluation after learning
We further evaluate the performance of the learned controllers by Algorithm D by using them to control the system in equation [ for Teval 30 steps. The reference trajectory for the evaluation is shown in Fig. 2
14

---

Published in Transactions on Machine Learning Research (04/2023)
Online control with fixed feedforward
Online control with food feedlorward
130
H. contrll
Mu-oontrol
LQR
LQR
100
Average Cost
200
Average
(a) Gaussian
(b) Constant
Aigortthm
Algorthm Online control with food feedlorward gain Mi-oontrol
Online control with fixcd feudffrward gain
200
Hl.-onfroo
LQR
LQR
Average Cosl
LQR for random walk
Average Cost
4300
1000
1008
Time
Time
(c)
Random walk
(d) Amplitude modulation
Algorihm
Algortthm
Online centrol food foodlorward gain
Chline fixed feedforward gain
M--sontrol
R- contoll
LOR
LOR
Average Cost
Average Cost
KX
22
Time
Time
(e) Uniformly sampled
(f) Sinusoidal
Figure 1: The evolution of the average cost Jr = 7 Ck (ek, uz) in equation 10 vs. T for the presented Algorithmm [ versus, the online control algorithm with fixed feedforward gain, the Ho control and the LQR for Gaussian, random walk, uniformly sampled, constant, amplitude modultion and sinusoidal disturbances. In each case, we generate the disturbance in the beginning of the simulation so the disturbance sequence is the same for all algorithms. Dotails regarding disturbances are given in Subsection 6.2 The final values of the average costs are reported Table
15

---

Published in Transactions on Machine Learning Research (04/2023)
The final average costs suffered by the algorithms for running each algorithm for T' 10000 steps. Bold values show the lowest average cost for each case of disturbance. The algorithm LQR for random walk is the optimal controller in the case of random walk disturbance and thus it is only evaluated in this case.
Table 1:
Disturbance
Algorithm
Online control with
LQR
H
LQR for random walk
fixed feedforward gain
Gaussian
5.58
5.42
5.29
6.93
N.A.
Random walk
15.19
46.67
219.85
83.26
14.50
Uniformly sam.
10.10
15.19
22.05
25.32
N.A.
Constant
8.02
13.78
57.77
19.75
N.A.
Amplitude mod.
5.94
6.17
17.55
8.21
N.A.
Sinusoidal
6.35
6.41
30.17
11.63
N.A.
Referance
Reference
-10
15
30
35
15 Time
Time
Figure 2: The reference signals used for the evaluation and comparison of different approaches under different disturbances.
We generate the disturbance in the beginning of the simulation so the disturbance sequence is the same for all algorithms during the evaluation. In Fig. 3 S
one can see the state tracking error for different cases of the disturbances using the methods in Subsection 6.3 Figures 3 also confirm the results in Table [] For amplitude modulation and sinusoidal disturbances, the tracking errors by Algorithm and the online control with fixed feedforward gain are zero while other approaches have significant nonzero errors. For the constant disturbance, the tracking error by Algorithm T is near errors. For stochastic disturbances, it is more difficult to understand the behavior from the tracking error plots and the performance is better understood by the numbers in Table [ but we have kept the figures for completeness of the results. For the Gaussian disturbance, the performance of Algorithm 1 is almost identical to the LQR controller which is the optimal controller in this case.
while other approaches have nonzero
7 Conclusion
In this paper, we have considered the problem of state tracking in the presence of general disturbances. We have proposed a memory-augmentedd controller and given an online algorithm to tune the parameters of the controller. Our proposed algorithm tunes the parameters of the controller online to achieve state tracking and disturbance rejection while minimizing general convex costs. We have proved that the algorithm attains O oooicy regret. our future works, we will consider partially observable dynamical systems and aim to remove the bounded assumption on the reference signal.
16

---

Published in Transactions on Machine Learning Research (04/2023)
Algorizm
Algorithm
Online control with fooed foedforward gain
Chilne contro with fixed feedtorward gain
Hy control
He control
LGR
18
LOR
02
Time
Time
Figure 3: Tracking error for the Gaussian disturbance for the presented Algorithm 1, versus, the online control algorithm with a fixed foodforward gain, the Ho control and the LQR control using the reference signals Fig.
Algorithm
gain
No-cootrol
LGR
random
0A.
Algorthm
Online control with fixed feedlorward gain
Mu-oontrool
LQR
LOR for random walk
Time
Time
Figure 4: Tracking error for the random walk disturbance for the presented Algorithm 1, versus the online control algorithm with fixed feedforward gain, the Hoo control, the LQR control, and the LQR for random walk using the reference signals in Fig. 2
Algorizm
Online control with fixed feedforward
contool
LQR
Online control with fixed feedlonward
Hu control
Figure 5: Tracking error for the uniformly sampled disturbance for the presented Algorithm 1, versus the online control algorithm with fixed leedforward gain, the Ho control and the LQR control using the reference signals in Fig. 2
17

---

Published in Transactions on Machine Learning Research (04/2023)
Algorizm
Algorithm
Online control with fooed foedforward gain
Chilnee contro with fixed teedtorward gain
Hy control
He control LOR
LGR
Time
Time
Figure 6: Tracking error for the constant disturbance for the presented Algorithm 1, versus the online control algorithm with fixed foodforward gain, the Ho control and the LQR control using the reference signals Fig.
Algorhhm
control gain
Mo-control
LQR
Algorithm
yain
He control
LOR
Time
Time
Figure Tracking error for the amplitude modulation disturbance for the presented Algorithm 1, versus the online control algorithm with fixed feedforward gain, the Hoe control and the LQR control using the reference signals in Fig. 2
Algorihm
Alçorithm
Online control with fixed feedforward gain
18
Criline contro with fixed feedforward gain
Hon-oottrol
Hu-control
LQR
LGR
-10
-22
Figure 8: Tracking error for the sinusoidal disturbance for the presented Algorithm 1, versus the online control algorithm with a fixed leedforward gain, the Ho control and the LQR control using the reference signals in Fig. 2
18

---

Published in Transactions on Machine Learning Research (04/2023)
Acknowledgments
Farnaz Adib Yaghmaiee is supported by Excellence Center at Linköping Lund Information Technology
(ELLIT)) and ZENITH. Hamidreza Modares supported by Department of Navy award -00014 issued by the Office of Naval Research.
References
Yasin Abbasi- Abbasi-Yadkori, Peter Bartlett, and Varun Kanade. Tracking adversarial targets. In International Conference on Machine Learning, pp. 369-377. PMLR, 2014.
Farnaz Adib Yaghmaie, Svante Gunnarsson, and Frank L. Lewis. Output regulation of unknown linear systems using average cost reinforcement learning. Automatica, 110:108549, 2019. ISSN 00051098, doi: automatica. 2019. 108549
(0.10t/j.atttmaaicc..0..... 2019.10559... URL https://doi. httt::://do..or//....
Naman Agarwal, Brian Bullins, Flad Hazan, Sham M. Kakade, and Karan Singh. Online control with adversarial disturbances. 36th International Conference on Machine Learning, ICML 2019, 2019-Junc: 154-165, 2019.
Dimitri Bertsekas. Dynamic programming and optimal control: Volume Athena scientific, 2012.
Luis Rodolfo Garcia Carrillo and Kyriakos G. Vamvoudakis. Deep-learning tracking for autonomous flying systems under adversarial inputs. IEEE Transactions on Aerospace and Electronác Systems, 56(2):1444- 1459, 2020.
Ci Chen, Hamidreza Modares, Kan Xie, Frank L. Lewis, Yan Wan, and Shengli Xie. Reinforcement Learning- Based Adaptive Optimal Exponential Tracking Control of Linear Systems with Unknown Dynamics. IEEE Transactions on Aulomatic Control, 64(11):4423 4438, 2019. ISSN 15582523. 2905215.
doi: 10.1109/TAC:2011
Ci Chen, Lihua Xie, Yi Jiang, Kan Xie, and Shengli Xie. Robust output regulation and reinforcement learning-based output tracking design for unknown linear discrete-time systems. IEEF Transactions on Automatic Control, pp. 1-1, 2022.
T. Dierks and S. Jagannathan. Optimal control affine nonlinear continuous time systems. Proceedings of the 2010 American Control Conference, ACC 2010, pp. 1568 1573, 2010. doi: 0..1099/acc.2100.1 1586566.
John Doyle, Robust and optimal control. Proceedings of 35th IEEE Conference on Decision and Control, 2: 1595-1598 vol.2, 1995.
Weinan Gao and Zhong Ping Jiang. Global Optimal Output Regulation of Partially Linear Systerns via Robust Adaptive Dynamic Programming. IFAC-PapersOnLLine, 48(11 11):742 747, 2015. ISSN 24058963. doi: 10.1016/j.ifacol. 201..00...15009.7. URL http://dx: doi ort./...00/001//// ifacol. 2015. 09.099..27 278
Weinan Gao and Zhong Ping Jiang. Adaptive Dynamic Programming and Adaptive Optimal Output Reg- ulation of Linear Systems. IEEE Trunsactions Automatic Control, 61(12):4164 4169, 2016. ISSN
00189286. doi: 2A1109/TAC.2016.222 2548662.
Weinan Gao, Zhong-Ping Jiang, Frank L. Lewis, and Yobin Wang. Cooperative optimal output regulation of multi-agent systems using adaptive dynamic programming. In 2017 American Control Conference (ACC), 2017.
pp.
Elad Hazan, Sham M. Kakade, and Karan Singh. The Nonstochastic Control Problem. In Algorithmic Learning Theory, pp. 408 421, 2020. URL httpp:/arxxv..rrg/ www.g/g/aa////aaaaaeeeeeggg http://aari...or/r///111...111
1917
Jie Huang. Nonlinear output regulation: theory and applications. SIAM, 2004.
Yuzhu Huang and Derong Liu. Neural--ettwokk-baseee optimal tracking control scheme for a class of unknown discrcte-time nonlinear systems using iterative ADP algorithm. Newrocomputing, 125:46 56, 2014. ISSN 09252312. doi: 10.1016/j. http:/..eencomm2022000000 20....0..000.. 047]
URL http:///xx:
doi. wew.lx..ooi.ogggg....o or...0r//10.00//// neucom. 2012.
19

---

Published in Transactions on Machine Learning Research (04/2023)
Alberto Isidori. Nonkinaar control systems. 1989.
Yi Jiang, Bahare Kiumarsi, Jialu Fan, Tianyou Chai, Jinna Li, and Frank L. Lewis. Optimal Output Regulation of Linear Discrete-Time Systems with Unknown Dynamics Using Reinforcement Learning. IEEE Transactions on Cybernetics, 50(7):3147 3156, 2020a. ISSN 21682275. doi: 10.1109/TCYB.200. 2890046.
Yi Jiang, Bahare Kiumarsi, Jialu Fan, Tianyou Chai, Jinna Li, and Frank L. Lewis. Optimal output regulation of linear discrete-time systems with unknown dynamics using reinforcement learning. IREE Transactions on Cybernetics, 50(7):3147 3156, 2020b.
Rushikesh Kamalapurkar, Huyen Dinh, Shubhendu Bhasin, and Warren E. Dixon. Approximate optimal tra- jectory tracking for continuous-timg nonlincar systems. Automatica, 51:40-48, 2015. ISSN 00051098. doi: 0ttp0///..aaoomaaaa20011.......0 URL http:// http:/xxxddddoooooo www.do.......o.ooo 1016/j automatica. 2014.10.110
Hassan K. Khalil. Nonlineur Systems. Prentice Hall, second edition, 2002.
Bahare Kiumarsi and Frank L. Lewis. Actor-critic-based optimal tracking for partially unknown nonlinear discrete- time systems. IEEE Transactions on Neural Networks and Learning Systems, 26(1):140 151, 2015. ISSN 21622388. doi: 10.1009/NNNSS
Bahare Kiumarsi, Frank L. Lewis, Hamidreza Modares, Ali Karimpour, and Mohammad Bagher Naghibi- Sistani. Reinforcement Q-learning for optimal tracking control of linear discrete-time systems with un- known dynamics. Automatica, 50(4):1167-1175, 2014. ISSN 00051098. doi: 10. 10.1016/jautomatica.22
02.015. URL /t..::://oa...o..og///0.0... 1016/j automatica. 2014. 02.
Bahare Kiumarsi, Frank Lewis, Mohammad Bagher Naghibi-Sistani, and Ali Karimpour. Optimal tracking control of unknown discrete-time linear systems using input-output measured data. IEEE Transactions on Cyberneties, (5(12))2770-277) 2015. ISSN 21682267. doi: 10.1109/TCVV TCCCB..01...384000000
Bahare Kiumarsi, Kyriakos G. Vamvoudakis, Hamidreza Modares, and Frank L. Lewis. Optimal and au- tonomous control using reinforcement learning: A survey, IEEE Transactions on Neural Networks and Learning Systems, 29(6):2042 2042-202, 2018
Hamidreza Modares and Frank L. Lewis. Optimal tracking control of nonlinear partially-unknowe constrained-input systems using integral reinforcement learning. Automaticn, 5087):170- 2014. ISSN 00051098. doi: a..01//..uutmmatiaa... 201...00..........1.............
Hamidreza Modares, Frank L. Lewis, and Zhong Ping Jiang, Ho Tracking Control of Completely Unknown Continuous-Tine Systems via Off-Policy Reinforcement Learning. IEEE Transactions on Neural Networks and Learning Systems, 26(10))2550-2566 2015. ISSN 21622388. doi: 10.1009/TNNLS 2.1............4..1 2441744
Kyriakos G Vamvoudakis and Frank L Lewis. Online solution of nonlinear two-player zero-sum games using synchronous policy itcration. International Journal of Robust and Nonlinear Control, 22(13):1460-1455 2012.
Kyriakos G. Vamvoudakis, Arman Mojoodi, and Henrique Ferraz. Event-triggered optimal tracking control nonlinear systems. International Journal of Robust and Nonlinear Control, 27(4):598- 619, 2017.
Huaguang Zhang, Lili Cui, Xin Zhang, and Yanhong Luo. Data-driven robust approximate optimal tracking control for unknown general nonlincar systems using adaptive dynamic programming method. IEEE Transactions on Neural Nelworks, 22(12 PART 2):2226 2236, 2011. ISSN 10459227. doi: 10.1109/TNN. 2011.2168538.
Huanguang Zhang, Qinglai Wei, and Yanhong Luo. A novel infinite-time optimal tracking control scheme for class of discreto-time nonlincar systems via the greody HDP itcration algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 38(4):937-94) 2008. ISSN 10834419. doi: 10.1100/SSMCB.2200.9005
20

---

Published in Transactions on Machine Learning Research (04/2023)
Zhiyu Zhang, Ashok Cutkosky, and Ioannis Paschalidis. Adversarial tracking control via strongly adaptive online learning with memory. In International Conference on Artificial Intelligence and Statistics, pp. 8458 8492. PMLR, 2022.
Peng Zhao, Yu-Xiang Wang, and Zhi-Hua Zhou. Non-stationary online learning with memory and non- stochastic control. International Conference on Artificial Intelligence and Statistics, pp- 2101-2133. PMLR, 2022.
A Proof of Lemma 1
Consider the current and the 1- past outputs of the system
rk-141 = F2k-141,
2k-142 -2k-
Tk-142 F2a-142 FS 2'Szk-11 21+11
1+1
Continuing like this for I steps, we get at the end
5k--12k-14h
(30)
T FF5-1122 24-1-11
rk-i+1
Let Fk =
be the concatenation of the outputs from Tk-141 to rk- We have Fs = O Since
Tk
the matrix Oj has full column rank rank(O;) = any p x p matrix can be spanned by columns O, particular, there exists matrix N such that 5i-1 NO and N - Using this result in the first equation in equation 30
24 = 5t 2k-14-11 = NO Nrk.
B Proof of Lemma 2
Let zet"" (Krb. fb. {rr) denote solution to the system in equation 1 Jusing the lincar feedback policy utt (K fb. K5f) in equation 3 and xī (K, M, P) denote the solution to the system in equation I Juiin the memory-augnnetted policy up (K, M, P) in equation 12
We drop the arguments in Iin Im 2f. un for clarity in the proof. Using
uk: the closed-loop system reads
Iin Fk+1
= (A + BK ( + BK + Wk
(A (A+ BK))) lin + BK11 Σ N1I -ll + Wkr
where we have used equation
in Lemma
Ii reads to replace 25 in the second line. ork
AA BK 1-1 BK
511- rk-- Σ (A + BK 1- Wk-t
9=0
AA+ BK BK, BK -
Σ (A + B Wk--
(31)
4=0
Now, we change the index in the first summation; it will simplify our derivations in other proofs. Introduce j=it and let S < k. We have two bounds for which give bounds for g after the change of the variable q-
21

---

Published in Transactions on Machine Learning Research (04/2023)
The lower bound on i = 9 1. From this, one should have that q S 1. Since q S L - also in the summation, we will have that q S min(1 - 1,j 1).
The upper bound on i j-j- q the summation, will have that O.
k. Since S k, we have q 2 (a negative number). Since q 2 in
Combining these two boundaries for we have 0 S S min(l 1,j - 1). As a result, the above equation can be written as
min (1-1,1-1)
li Σ
Σ
(A+ BK (
BK
rk-j
rk-j Σ (A + (o) -
(32)
Note that Cg is convex "&", but based on equation 32 alln not convex so. Kyg- As a result, Cp (eke up)
is not convex in Ky fb: kff in general.
Next, study the solution to the system in equation using the memory-augmenter policy up. Using ug: the closed-loop system reads
Bew
mr
N AK +
M Wk
Σ
pldl rk
wR
As a result, og reads
ma
k
Ak
M [--1]
Wk- -1- +
1/-1a Wk-i
i=1
k:
1--1
B
p|l] r i-8
i--1
Bl
K
$=0
m,-1
A1-1 Wk-t
Σ
A BPI
TR-i-s.
(33)
i=1
Again, we change the indices in the summations. The reasoning is similar to what we discussed earlier. For the first summation, introduce j = i + and let S < k. We have two bounds for which give two bounds for after the change of the variable j itt
The lower bound on = - + 2 1. From this, one should have that t J 1. Since t S my also in the summation, we will have that 1 < min(m 1).
The upper bound on = t k. Since j i k. we have t 2 (a nogative number). Since 2 in the summation, will have that 2
Combining these two boundaries for have < t < min(m 1). For the third summation, introduce = -isss and let 1 < j < k. We can follow similar reasoning and show that 0 I s I min(m, - 1,j 1).
ts min(m f-1)
2/
A BM 11
Wk
Σ Ax Wk-i 1=1
(34)
min(m.- 1.j-1)
Σ
Σ
Note that C% is convex in 2& and ag is linear in M, P. As result, ce(es, ux) is convex in M, P.
22

---

Published in Transactions on Machine Learning Research (04/2023)
C
Proof of Lemma 3
Based on Lemma 2 the expression of the state at time k becomes,
A BM WE- +
Σ Ak Wk
Ax
BP
(35)
k-
Forming -h for any O, multiplying by Ake and subtracting oi from A yields
mar
2 A
Σ Ak wk-j
Σ
A/
BM 8-
BM
wk-
Wk-j-t
j=h+1
j=1
A BM BM
A 1 BPP k-
Σ
A BP T-k
Wk-j j-
Tk-j-s
j=h+1
t=1
j=1 0=0
j=h+1
s=0
h
m--1
K
K
BM
[1-1]
k-j Wk j-t +
K
BP
In the second summation, introduce y = j+t and change the order of summations, so y 0,,,, ...,,, May Similarly, introduce j +
so, 2 = 0, ..., h + m, 1 and then j - 1 +
mw
h+m.-
2 A
A Wkk -
Σ
Σ
A K
BM
Wh Wk---1+
K
BPI
k
TR-#
j=0
j=1
4-1
ma +h-
h+m,-
Ag Wa-1+++++
BM 1ーーーー
Wk wk-y-1
-apla-s- j- A BPBBE
k-j-1 rk-
==0 j=0
Then, based on equation
13 we have
ma+h-1
x = (Mox-11, Pock-1) - +
v k.h k.y
(MM---1D--1)W)--
my mnth-1
Σ
K.h P
Set h and note that y S and S k 1. Then, equation
16 conchuded.
D Supporting Lemmas
Lemma 4 Let Assumptions
hold. Suppose that K is (K., sttrronlyy stable. Then,
K. S x1 - (11-))"ngh-+ + m k kx - 7) k.y / K.h E mn, 2x -)) -)
(36)
Proof: To prove the first statement in equation 36 note that
[ K.b kig
|| S
T +
A 10 BM
ss--smmll
K
k
k- k-j-1
0=
h-1
<n²(1
Σ
2 Kig
3 (1 - - 11g
0=0
<x²(1
7)
m 2 - 7)
23

---

Published in Transactions on Machine Learning Research (04/2023)
where the second inequality follows from (itaaiiiy of the controller gain K and Assumption which gives the bound for M. The proof of the second statement follows similarly.
Lemma 5 Let Assumptions
hold. Define
Yo = [Musk Pockl.
(37)
YH,= [MR- Pk-H
D = Regit + (, + kw [11 - n9nng
(Ko + Ke )roks
x²(1 7)
?
where Kn = i Eg= -V
din(K Suppose that K and is, are (K.,7)- stsronnlyy stable. Define ok (K fo: Kÿy) as the system state corresponding an optimal linear feedback controller. Then, one has
max 11 (Yo:)= |1 ( (K K))) DDD
(38)
max(11 (Yo.))) (1 S D,
(39)
|1 (Yois-1) - (HHHH- 5x²(1-7)
(40)
|/ (Yoss) uū (YH,))11 s sxm(1-7)² D.
(41)
Proof: Using equation 15 we have
may H1
m,HH-1
| |l A k
||| H1l Kox
Σ
1 W.H.H.HMMMH.. (Ma-H 1MM Kr Σ
k.v
K.H (Pa-
<x <x² - |10 + kwo (162 + mw 5 1/g (1 - -1) + KT? (m,ri'n))) - 7)
The above recursion satisfies
| S -2-1 Kan (Ky + mw (1 - 7) x5
x²2 7)
Similarly, from equation 17 has
mi + H
m, MH+H-1
1 k.y
K.H. 11)---1)1))-11l1111 + Σ
I
K.H (P
S 2T k o (n + K,,,,, 2x, - -7) <.D. D.
where the last inequality is obtained because 0 1 x= - 7 1. Moreover,
k-1
| (Kio, Kÿt)ll
AM Kjo
Wh
1111
+
Axx BK B
1=0
h-1
1-1 Nll- oi rk-1-ql1
A Wkk (ikky--ll
Σ
AKz BK;
==0
1=0
0=0
57 x2 (Kew + Kottntt)) S
24

---

Published in Transactions on Machine Learning Research (04/2023)
Beside, one has
Mew
m,
1ug (Yu:)]l
[|x (Yu:k-1) +
M 11 Wk
pl. pk-8
==0
m.
x x (Y:kk 1)]l Kiw
Kbk 3 (1 -7) (t-1) + Kr
Σ Kbn (1 7)
S Kw (K + my (1 7)) 7) --=xk=pp k²
(Niw + Kop )tore
S
x² 7
Similarly,
m,-1
o0 (YH,))] - || (Y (HH +
Σ M /-
Wk
Σ
r
mag
my
S x x (YH,- + Kip
Kbb (1 -7) + Kir
Σ
Kish (1 7)
s=0
2 kwlt +y (Hr + Ksy,, )1s 1op - 72- (New + 1op )ign
S D.
To bound the difference between the actual and truncated state, from equation 17 and equation 15 one has
- - HD
which gives
(Yosk) ug (YH,))l S ( 5 H1
This completes the proof.
Lemma 6 Let Assumptions 5 hold. Suppose that K is (K., sttrongll stable. Define
Rg : 11 K.k (Po.t-)) -
[IN( (PN(-
Then, the tracking error bound is given by
m + |ex|l S k (n² + mwrk 2 (1((1))) + kx (1--111-11-10- -1
Ks.
(42)
Proof: First, note that K, is bounded because K.K (Po:t-1) 1) is bounded, see Lemma 4 tracking error is defined as
Using equation 5 the
20 Fzz = (Yo - IIzk
where 2i (Yo:--1) is defined in equation 16 outputs of the reference
Using Lemma
to replace with linear combination of the
Kik k.
(Mosk 1 +
K.k (Post-1rk-- II
N1ll- -l--
RRo
9=0
k-1
K.k k.y
(Mosk-)WWk---1
+
(Wa (Po:k IINI
-1
Σ
1k. Posk-1)rk-
=
25

---

Published in Transactions on Machine Learning Research (04/2023)
Using the bounds in equation
||exll
(1 7) s An -7) Now +
>)
kis (Po:t-1) -II-I-
K.R
==
Σ
mik 5 Ni -7)²-1 Kir
z=1
Skowy (
mw
R rig -1)- Kr Σ K2 + K,? -1 7)- m --,->),,m----
where we have used the fact that En 7) 2 in the last inequality.
Lemma 7 Define YH = (V1,... Yt..., Y2nl = [M--Hi Pk-Hak) and YH = [V1,.., V,,.., Y28) where YH. has all its elements the same as YH,K, ezcept one element. Then, the truncated cost function equation 19 salisfies the following Lipschitz condition
[V Yu... Y2n) - f&(V, Vr..., Y2n)1 & L Yell
where
f 3G,D Ko + Kmd)
(43)
Proof: Based on Assumption
one has
[/x(Y.. Ye...,, - Sa (Y,,,...., ".,,,.,,,,........ Y2u)
(44)
< - (YH,)) -g (YH..)))l
where 27 27 rk. Using
-Yn,,)) (YH,)) = (f - Tk #[HHH,) (8HH),))
in equation 44 yields
Yr.... Y2H) - Yr.... Y2H) < (YD)) - (fHmm)) + G.D (f
Based on equation
17 if VH and HH differs in an Mj element, one has
[ #(HHm)) = B
Σ
(M) Mi-1)ue "2l"t)w=illlsee w
2H
I Kg 2 (1
> Kw
|| 1111
(45)
On the other hand, if Yн.a and YH. differs in an P element, one has
+ 11
1 (YH.)) - (f AI
Σ
(P:
1=0
2H
S Sk - -7)* K
|
(46)
==1
26

---

Published in Transactions on Machine Learning Research (04/2023)
Combining equation 45 equatiin 46
one has
(YH,)) (YH, k - 7)) Kiw)
(y-l)) -v11
m Rw)l Yell-
(47)
On the other hand, based equation 18 one has
(YH,)) -IK 2% (YHH))) +
(Y! - Y!(i) |I
i=1
(Nix* (1))(()) + kmw) 1)
|| 1 2nan kw)))l Yell
(48)
where the first equality obtained based on the fact that K is (stabl (see Definition equation and equation in equation 44 completes the proof.
Using
Lemma 8 Let Assumption is satisfied. Then, the following gradient bound is satisfied
(YYw)a(YY S 6Hd&Go (Ny + Kw )ook G
(49)
where d = max(n, m).
Proof: To prove the claim, We bound V fa for every p {L,...,m) {l,..., n) and l {l,..., ..., 2H yn., We find the bound for the two cases: when Yp. !!! for which l E {1, .l,,., m ) and when y/kal p!!! for which le {l,...,m. m, For the first case, similar to Zhao et al. (202)), one can show that
V Min Su (YH,,)) s 3GoK
(50)
For the second case, using the same procedure as Zhao et al. 2022), one can show that
V ply fa(Y.A)) & 3G
(51)
Therefore, since pg < max(n, d, and 4 + l2 = 2/1, one has ( S. 6HH.G (K, Kw Kur)kkk3>
+
E Proof of Theorem 2
The solution to the system in equation using the linear feedback controller in equation 3 is given in equation
32
Using equation 32 the linear foodback controller in equation reads
Jin K soa lin + K3f
1=0
min(1- (1-11-1-11)
Σ
K Kyt(A + (-97))---1BB1 Ml
1-1 K5yNil
Kyb(A + BK₁)) -- Wk-i +
(52)
1=
27

---

Published in Transactions on Machine Learning Research (04/2023)
We aim approximate equation 52 in the memory-augmentel policy equation 12
with memory-angmented policy in equation 12
Replacing equation 32
we get
uk ạ = KKx +
M
Wk-st +
pbl Tk-
3=0
1,5-1
K(A + BK Bb) 16)- 9- BK NN rrk
11
K(A + B²
1n 10- Σ M 10 +
Σ
phl
(53)
j=0
Now, we derive u
mw
lin
[K K)(A+ BK -Mb-")Jur-
k
uk
Σ
(KB - K)(A + BK, Wk-
miin(111--1)
Σ
(K ()) 1K0 "K
4=0
m.-1
K Kgg. Ik-3
Σ
plil
rk-j.
(54)
Select M6-11] (K - () BK,)) BK i-1 for = I,... May. This makes the coefficients of wk-s equal to zero for 1, mw.
Similarly, we try to make the coefficients of rk-j equal to zero We have three cases. a) 0. Pk appears
in the fourth line of equation 54 and its coefficient becomes zero by selecting pio K N b) 0 < j < l.
In this case, Tk-j appears in the third and fourth lines of equation 54 and min(1 - 1,j - 1) j - 1. Setting the coefficient of rk-j equal to zero
Σ (Kro K)(A+
+ K1y - pbb 0,
we have
j-1 pbl = -Kp K)(A BK ,K, + NH--N 7
Finally c) 1 j < my. In this case, Tk-j appears in the third and forth lines of equation 54 and min(/
1,j 1) = -1-1. 1. Setting the cocfficient of rk-j equal to zero
Σ (K K)(A BK - -pbi 0. 0=0
we have
1-1
pbi =
Σ (K - K) + 1
0=
28

---

Published in Transactions on Machine Learning Research (04/2023)
The aforementioned results are summarized in equation 20 lin k "k reads,
If we select M, P according to equation 20 then
1-1
Ug
lin
x uk
Σ t=
(K K) (o)
w
Σ
Σ
(K1s
() BKk)) -- BK1, / A
== 9=0
M 11 Dws-st + Σ p-l
(55)
(=
j=mr
As a result.
||u lln u S
Ngn (1 - -)) New +
Σ
Kgh (1 - -7)8 Krr
i +1
m=
k min
k-
Kiyle - 7)) 7) Fow
Kbll 3(((( y) Por
ST Konn (1 m) Ne + Kon (1 7)
mnr Kip.
where we changed the indices in the summations as = mw 1 and s my to get the equality and used the fact that En=o(1 >> s to get the last incquality.
F Proof of Theorem 3
Using Jin in equation
2k+1 can be written as
Ji x E++
Ar Ji Buk + wa
Ako Ji B(K K)a lin + BKB1
NP
11 Tk + Wk.
(56)
1=0
Using og in equation 12 #k+1 can be written
Tae M| Wk + wh + Σ
m. -1
- A
plalk
(57)
Based on equation 56 equation 57
1-1
Iin 1
2 Ax (2b - xx. + B(Kss - K)at + BK
Σ
Nil- Nil--)
5=0
ma
M lt- 1 Wk-t B m,
Σ
plol
Replace æii from equation 32
B(K K)altn
④ min (1-1.j-1)
#+1 - 2h+1 = Ax
xx) + B(K - K) Σ Σ
(A BK 9- BK / -
Q=0
+ B(K K) Σ (A
BK (b)
WK-k + BK f1
N1l- f 1
me
m--1
B
11l 1
Wk
B
Σ
plalrk-s.
(58)
1=1
$=0
29

---

Published in Transactions on Machine Learning Research (04/2023)
Using Mw in equation 20 the terms containing in the above equation read
mm
b = 5( K)
Σ (A + BK 1
wk B
M
wk-t
= sb K)
(A + BK fb)
B(K -
Wk-s
K)
Σ (A +
wk-t
1=1
t=1
B( K)
Σ
(A+ ( Wk-C
1=
Using P in equation
20
the terms containing r in the above equation read
min (1-1.5-1)
1-1 (A+ BKbb) - 4- N +BBs Σ
4, BB(K K)
Σ
Σ
N T
q=0
m,-1
k Σ
min (1-1,-11
pll rk- B( 9b K)
Σ
(A+ fb) 1- BK
j=1
P=0
my
(1.-1) Σ
+ |K
N|- 11-1 pk- - B( - -K)
(A +
N
1=
8=1
q=0
k
H-1
Σ
NTl 7 B(K K) Σ
Σ
(A+
BK
= q=0
Using two t, in equation
58 Ilin k41 reads
li K+1
xb+1 (xT xx) + B(K K)
Σ (A+ BK) -lokk wk-t
1-1
+ 1(K K) Σ Σ (A+ BK1)
BK BKl dr
8=m.==0
Since Åx is stable, 2k xx reads
lin
k
k-i
B(K - K)
Σ (K+
k
A B(K K)
BK [A+ -B-----B,,,, Ni N PR-
0
Since it should hold that k- - i 2 m. + in the second line and k - my in the third line,
my
Jin
A
B( K fb
K)
Σ (A+ BK 2 1 WE-i-t
k-
k-
1-1
+
A B(K - K)
Σ
Σ
(A
N1 11 1 /K,,,NN-HHH
8=m, 9=0
Using equation 20 we have
N m
k-
#
R-i i
li
A
1i-1
B
Σ
M 1-11 Wk
W +
1 1--1 K
B Σ
ple rk-i--
(59)
K
t= +1
9
30

---

Published in Transactions on Machine Learning Research (04/2023)
Based on (stabiita of K and Assumption 5
1 1--w-1
11 lin
2xl
|1
<2mo(1 - 7))-1
Kiba (1 - 77) New
Fow
t=
k-m,
k-i
k Kb - -7)(-1
Σ
KBn
3 (1 - --)00/ ²)
s=m,
k-m
mey
k² Rbbl1 -7)
Σ
Kbtt (1 - y) Row
p=O
k-my
h- k-i-m,
Σ
k Rb - -7)
Σ
Kote (1 - yot for
k-m
12x6(1 - -) - 7) Niw
k-m
k² Rb - - - 7m
S9
2 Kig
(1 7) niw Kiw
2 Kig 22 (1 7) mr Kr.
where we changed the indices in the summations as t my 1 and q = 5 my to get the equality and used the fact that En -))" $ in the last two incqualitics.
G Proof of Theorem
Before proving the regret bound, we present Lemma g which provides an upper bound for the difference between the costs using optimal linear controller and optimal memory-augee augmented control policy.
Let Assumptions hold. Let K2 = [Kjo Kiyl denote the optimal linear gain. Let x (Kz) denole the state using the optimal linear controller uhin (Kj). Set H = Mae = my and let Y* [M [0]. .... , M |H- plu)- ...., pl denote the optimal weights learned by Algorithm denote the truncated state and control using the optimal weights according to equation
Lemma 9
1. Let ag (Y*), iig (Y*)
17 equutiin 18 Then
(ex(=](Y") - Tk. (Y"))) Ck (ali (KT) - rk: ux (Kj)) & DG H(m + k,,) n2[1 (1-1) (60)
Proof of Lemmal g
By selecting K- = Kÿb M- = 0 and pla] = K2 Nit, 0 8 < equation 16 can be used to express 1 (Kj)
H
2 Hi (Kj)
W
k.y
Kiss
Wk
K
-k-
W Kish k.y
Wk y
Kjnn Uk,
Tk-2
y
y
1-1 1
1-1
k-
1-1
+
kiy
Kinn
Wk
+
k2
K k
-k-
W
k.y
KJ is
Wk
y
t Tk- + (Kz))
Ki
y= 11
2 11
11
2
As result, (ka) 5 (Y*))l
reads
k-1 1
k-1 1 Σ
| (K7) - 2z (Y < | tin (K3) - +2
kyy
Kja
wi
w
v 2=
k,
Kishk
Tk-zll.
H1
31

---

Published in Transactions on Machine Learning Research (04/2023)
By equation 59
| (Kj) - (Y = 0. By Lemma 5
k-1
k.y
inik
Wkk
----y--ll 5
Σ
H 5 Kig (1 - 7) Nio0 S 2 - -7) 1- Kew
H
==H
(61)
k-1
jb.k
Σ
H no{ - - S xx* - -- 1s.-
Wk,
Tk-
y=H
==
Hence,
(kz) 7 (Y*)|l S7 (Ko + Ki, n.,)) 136 - 7) 71
Next, we find (K3) ()()")|l In equation
18
set K = Kjb jb.
Then, one has
H-1
k-1
H-1
uk
(en((K (K7)
Kookk tin
Σ
p p-rk-
Σ
K6 W kiy
Kjock
wk--y- +
Σ
KJouna rk-
Kjsuk
K K7b0/ Jin
+
Σ
P
rk-a
y=11
==0
Σ ==
fb
ky
Kaak
wk-y-1 +
Σ
K Ko Th-2 + (K7).
Kjsik
==
As result, one write
|K))(KK) ug (Y*) S | (K7) 0g 1I + Σ
|K
v
k.w
Kjsik
wk
1 11 +
Σ
|
Kij
K7ack
rk-ell.
2=
By equation
55
|| (Kj) - u. (Y+)| = 0. Using equation 61
||u| h (Kz) (Y S H (New 1s, )x )x 22b(1 H-
Therefore,
(x) - Tk. 0h (Y*) c* (2f (K7) Tke utt (Kz))
<G.D 1 (K7) =T(Y") I| + G. D1 1in (Kÿ) 0ā (1*)
D2G H(N - ko)) x1](1 7) (1-
Proof of Theorem
The regret reads
T
T Σ
Regret
Ck (k(e,, uk)
min KyeK
ce(ex, uk)
(62)
1=1
ca (e (Yor- us 1)) - Σ fu(Yn,))
k=1
Or
fM(Y,,)) Σ SA(Y")
Br
T Σ
+
min fa
cb (ex, us)
y EK
k= 1
ST
32

---

Published in Transactions on Machine Learning Research (04/2023)
where Y [M/[0), ..... M| plo). [[]- (Rmxnya# denote the optimal weights learned by Algo-
rithm satisfying Assumption
The regret analysis is split into three parts: ar denotes the difference between the cost of Algorithm | and the truncated cost. 3T denotes the difference between the truncated and optimal truncated costs. Çr denotes the difference between the optimal truncated cost and the optimal linear control policy.
We now bound the first term oT. One has
[CK(ER, ux) fa(HHa))
S D [ (Yox-1) rk) (YH(H))) - rx)1l++++ GoD llu (Yo: 0g (YH s 2G 7)
where we have used Lemma 3 get the above result. Therefore,
|ar || =
Σ Jrm
ca(ex, uss) - E STG =
S
(63)
kmml
where the last equality is obtained based on H = Ollog T).
We can bound the term ST by Theorem 4.6 of Agarwal et al. 2019 and the results of Lemmas
and as
T Σ fu(HH))) - E1 - L -ol--GGmm L,
T
(64)
"1
where M2 := 2vdron = max(n, m). By selecting 17 =
- ( H (log T), we have 3T O(VT).
We now bound the third termn Cr. Based on equation 63 one has,
T Σ (Y
Σ cs (a
tim (Kx+) - rk, uk (K₃z)))
T
Ck (Y* - rk, 75 (Y*))
Σ
C
(rk lin (Kf) rk. ot (H?(()))] + 27 G.D -01--10 -7)
k=1
Using Lemma
g
Σ (Y Σ cx (at (I))(())))
- rkk uk d [K]+))|| <2TG.D7 H(Kw + k - (11(1
+ +2 G.D x² 7) =
(65)
where the last equality is obtained based on = Ollog T).
Additional simulation results for changing reference generator dynamics
Our proof of the regret bound in Theorem 4 is independent of the dynamics of the reference signal generator (S, F). We make Assumption 3 stating that the reference signal is bounded and the output of the reference signal is measurable. We also assume that the classical state-tracking problem is solvable, such that the problem setup is meaningful. Since the information of (5, F) is not used, we expect that our algorithm works even if F) changes at some steps. Theoretical guarantees for changing FS) however require careful examination of the thcories define the minimum time intervals between dynamics changes and it is out of the scope of this paper. the sequel, we give some simulation results to show the performance of Al Algorithm 1 against the other control approaches in Section 6.3
33

---

Published in Transactions on Machine Learning Research (04/2023)
We consider the same problem setup as Section including the same types of disturbances. the dynamics of the reference generator changes at chhange 8000 from (S1, Fi) in equation 26 to (S2, F2)
We assume that
2k+1
-1
2as #T #Tchange 11,0,-1]
0
(66)
0 0
-1 1
1
0
All control approaches in Section 6.3 namely the Online control algorithm with a fixed foedforward gain, LQR, and Hontoll,,,, require method to detect when the dynamics of the reference generator changes to learn the new dynamics and compute the new feedforward gain. However, our algorithm does not need such detection algorithm. In the simulation result, feedforward gain, LQR, and Honconl are aware of Tchange- Let 1,, I1 be the solution to the tracking equation in equation 5 using (S1; Fi) and 2. Iī be the solution to the tracking equation in equation 5 using (S2, F2). At the beginning of the simulation, the feedforward gain in the Online control algorithm with a fixed forddd gain is set to Ky = T, KFi. Similarly, we set Kffı = r KyaFi in the LQR, and Ho--oontool approaches. At = Tchange, we change the feedforward gain according to the new dynamics to K8f2 I2 K.F F2 and KJf2 П2 F2 in the Online control algorithm with fixed feodforward gain, and the LQR and -oo-colr approaches. Algorithm is run as discussed in Section 6.3 i.e. no information of Tehange (Si, F1), (S2, F2) is used.
have assumed the Online control algorithm with fixed
Table 2: The final average costs suffered by the algorithms for running each algorithm for T= 16000 steps. At Tchange: the dynamics of the reference generator changes from (Si, F1) to (S2, F2). Bold values show the lowest average cost for each case of disturbance. The algorithm LQR for random walk is the optimal controller in the case of random walk disturbance and thus it is only evaluated in this case.
Disturbance
Algorithm
Online control with
LQR
Hoo
LQR for random walk
fixed feedforward gain
Gaussian
3.83
3.74
3.65
5.25
N.A.
Random walk
16.65
36.39
283.79
109.01
16.12
Uniformly sam.
8.09
10.76
19.88
23.25
N.A.
Constant. 5.82
8.65
55.09
17.30
N.A.
Amplitude mod.
4.10
4.17
15.91
6.58
N.A.
Sinusoidal
4.52
4.51
28.53
10.00
N.A.
In Table 2 we summarize the final average cost; + ET Ca (en, ux) suffered by the algorithms for = 16000. We use bold to refer to the algorithm with the lowest average cost in each case the disturbance.
In Fig. the evolution of the average cost J/ = E Ck (ck, ux) in equation vs. for the cases of dist disturbance in subsection 6.2 has been shown. The discussion regarding the performance of the algorithms is similar to Section 6.2 and thus omitted.
We plot the reference trajectories and the tracking errors for Tehange 30 to Tehange and T 30 16 These time intervals are selected such that one can see the performance of Algorithu and the online control with a fixed feedforward gain when those algorithms converge.
30 to T in Fig.
34

---

Published in Transactions on Machine Learning Research (04/2023)
Alganitmm
Algorthi
Online control with fixed leedforward
Online control with foed feedlorward
Hu-dontrol
Mu-oontrol
130
LQR
LQR
Average Cost
Averagg
(a) Gaussian
(b) Coustant
Aigortthm
Algorthm Online control with foxe feodlorward goin
Orline control with fixed foodforward gain
100
H. Hu-bontrol
Mu-oontrel
LQR
LQR
Average Cost
LQR for random walk
Average Cosl
200
10000
8000
18.00
1000
14000
Time
lime
(c)
Random walk
(d) Amplitude modulation
Algorihm
Algorithm
Online control food foedtorward gain
175
Online feadforward gain
Hu Hontollrol
Hi control
LOR
LOR
Average Cost
Average Cost
25
5030 Time
Time
(e) Uniformly sampled
(f) Sinusoidal
Figure 9: The evolution of the average cost. Jr= = 7 EI= Ch (ek, uz) in equation 10 T for the presented Algorithm D versus, the online control algorithm with fixed feodforward gain, the Hoo control and the LQR for Gaussian, random walk, uniformly sampled, constant, amplitude modultion and sinusoidal disturbances. At = Tehange, the dynamics of the reference generator changes from Fi) to F2). In each case, we generate the disturbance in the boginning of the simulation so the disturbance sequenco is the same for all algorithms. Details regarding disturbances are given in Subsection 6.2 The final values of the average costs are reported Table
35

---

Published in Transactions on Machine Learning Research (04/2023)
100
Reference
Referance
-49
-10
55
f1A
28
-128
-5955
13665
-88
1260
1966
Tire
Timm
Figure 10: The reference signals over Tehange
30 to Tehange and T
T.
Algorithm Onlie control feedforward
Algoritim
Online control feedlorward
H-, contral
Hu. control
LOR
LOR
1073
7070
7055
Alporthm
Algorttim
Online control with food foedforwwrd gain
Orline contro with fixed feedforward gain
Wu-cpntroll
-3
Time
Time
Figure 11: Tracking error over Tehange 30 to Tehange and 30 to T for the Gaussian disturbance for the presented Algorithm 1, versus, the online control algorithm with fixed feedforward gain, the Hoo control and the LQR control using the reference signals in Fig. 10
36

---

Published in Transactions on Machine Learning Research (04/2023)
Algorihm
Online control feedlonward
Hon-oll
LOR
Aggoithm
Online contro with fixad feedforward gain
Hu-coulrol
IQR
LGK
Online control with tixed feedionward gain
Gnline contro with fixed feedforward gain
Hu-oortral
H H--contol
LOR for pardom quilk
LOR for ramborn walk
-2
-4
1985
1580
Timm 12890
Tire
Figure 12: Tracking error over Tehange to Tehange and T 30 for the random walk disturbance for the presented Algorithm 1, versus the online control algorithm with a fixed feedforward gain, the H control, the LQR control, and the LQR for random walk using the reference signals in Fig. 10
Algortthm
Algorthhm
feedforward gein
gain
Mu Mu-control
L.3R
LGR
Algorihnn
Alpxiilm
Online control with fxed foadforward gein
Orline control with fixed feediorward gain
LGR
LGR
Time
Time
Figure 13: Tracking error over Tehange 30 Tehange and - to T' for the uniformly sampled disturbance for the presented Algorithm 1, versus the online control algorithm with a fixed feedforward gain, the Ho control and the LQR control using the reference signals in Fig. 10
37

---

Published in Transactions on Machine Learning Research (04/2023)
Algorthhm
Algoritim
with foodforward gain
with goin
H.. -ontrol
Hl-ooorrrll
LGaR
LGR
0
Algoritmm
Algorttim
Onlino control with fxxd foodforward gain
Online control with fixed feediorward
Hooorrro
LGR
LGR
-545
1965
1983
1249
Time
Time
Figure 14: Tracking error over Tehange 30 to Tehange and T 30 for the constant disturbance for the presented Algorithm 1, versus the online control algorithm with a fixed feedforward gain, the Ho control and the LQR control using the reference signals in Fig. 10
Algorthhm 1
Algorthmm f1u-porbol
gain
gain
fl.som -oontol
1.3R
LGR
7075
Algurdlnn
Alpxzilm
Online control with fxed foedforward gein
Orline control with fixed foediorward
LGR
LGR
Time
Time
Figure 15: Tracking error over Tehange 30 to Tehange and - 30 to T for the amplitude modulation disturbance for the presented Algorithm 1, versus the online control algorithm with fixed feedforward gain, the Ho control and the LQR control using the reference signals in Fig. 10
38

---

Published in Transactions on Machine Learning Research (04/2023)
Algorithm
Algorthm
contro with foodforward gain
with foodfonward goin
H. control
H.-cortrol
LOR
LGR
Algorihm
Algorithm
Online control with fxcd foodforward gain -ootrrl
Orline control with fixed feedlorward
LOR
4
LGR
1545
1986
1290
Time
Time
Figure 16: Tracking error over Tehaage 30 Tehange and T T for the sinusoidal disturbance for the presented Algorithm 1, versus the online control algorithm with fixed feedforward gain, the Hoo control and the LQR control using the reference signals in Fig. 10
39


Reviews:
[{"review_id": "gbtDhj6iwC", "reviewer": "Reviewer_yjL7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1. For real applications, reference tracking is very important; for example for quadrotor path tracking or leader follower problems; in that sense, this extension benefits practitioners to design optimal algorithms.\n\n2. The flow of the paper is easy to follow; and some parts are well-written.\n\n3. It does a good list of comparison experiments which concisely summarizes the motivations of this work\n\nWeakness:\n1. There are many technically confusing or inaccurate descriptions with several typos; (I will list hem in the requested change section); especially, since this work is largely inspired by Agrawal et al 2019, and is rather aiming for its practical benefits of extensions, the technical accuracy is very crucial.\n\n2. Related to the above, some experimental settings seem contradicting to the assumptions; also, some parts seem written in rush, and are showing inconsistency of writings. (I will list them in the requested change section)\n\n3. Experiment contents are good, but the way they are shown are a bit rough. (I will list them in the requested change section)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work presents an extension of Agarwal et al 2019 (Online control with adversarial disturbances) to an online reference tracking problems.\nThe reference signals are generated by an unknown but observable linear system.\nIt merges the theorem from Isidori 1989 (Theorem 1) and Agarwal et al 2019.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major parts:\n1. Assumption 3 the third one;  is this for all k>=0? if this is for all k, the boundedness may be a strong assumption indeed.\n2. Remark 2; --- have arbitrary linear dynamics---  it is not arbitrary isn't it?  this kind of statement seems a bit misleading.\n3. Can you mention the relation of this memory augmented controller to PI controller and disturbance observer?\n4. eq 13 includes typos\n5. Agarwal work is referenced, but please define truncated state, control and cost here.  Especially, it is hard to understand what the truncated cost is only from eq 18.  And equation 32 is referenced in page 7 but it is in Appendix and is hard to read.\nThis is true for the place like page 9 --- cost is computed according to equation 16-equation 18; how does one compute this cost?\n6. Algorithm 1 also includes typo;  k_k+1 -> x_k+1?\n7. Remark5 --- any convex c -> is it really \"any\"?  this is again a bit misleading\n8. Although natural, but the definition 3 should be justified by a few sentences added to the current manuscript; because this is the optimality notion.\n9. We assumed that the disturbance is bounded; why can we use Gaussian noise here?  If the disturbance is Gaussian, then this work cannot be applied or can we?   also the writing 0.1N(0,1) is a bit strange to me.\n10. Experimental sections 6 are not clearly written.   6.2.3 to 6.2.6 seem too short; please use other ways of presenting them.  Also what are w_1k and w_2k?  \nThere are several sayings \"No other controller can beat the LQR...\".  It again may leads to misunderstandings.  These statements are under different assumptions of known parameters.  If we know the noise generating mechanisms that are correlated somehow to the Gaussian disturbances, we may be able to do better by predicting the next noise magnitudes.  Please avoid this a bit strong sayings.\n6.4 includes may redundancies that are already mentioned in the previous sections and are hard to follow.  Especially the figures are not really well explained.  Captions are not enough.  What is \"counterfactual cost\"? this saying seems appear here first time.  What is exactly the average cost?  averaged over time or runs?\n11. in conclusions.  T is strangely typed.  Also the conclusion section is separated by figures and is hard to read.  Please deal with this.\n\n12. Appendix D;   --- where the last inequality follows ----  -> the second last also follows from this?\nAlso in the proof of Lemma5  what is \"||A||x\"?  x should be in norm?  and the norm notation is missing for the same line for the last term; this makes a bit confusing to follow.   And this appendix does not change line when writing \"<\" or \">\" symbol while the other parts of appendices do so; please make the writing consistent.  And in Lemma 6,  Ytilde has all its elements....  this Ytilde refers to Y_H,k or Y_t?  And the bottom of page 22  what is L_f3G...?   Before equation 42, what do you mean \"Therefore, in general, ...\"?  What does this \"general\" mean for?\nFinally, did you correctly define the norm || * ||?  is this spectral norm?\nAll of these make it harder to follow.  Even if they are immediate from the existing work like Agarwal et al., please carefully review the writings to increase the readability \n\n\nMinor parts:\n1. page 1  ---Gaussian nor generated by a dynamic system.  -> dynamical system?\n2. It would be great to see a few sentences in the introduction to justify this reference tracking with adversarial noise problem in practice.\n3. Page 3 in Regret ---(usually the optimal)--- -> this is talking about the notion of optimality and is presenting regret; so saying \"optimal\" here is confusing; what does this \"optimal\" means here?\n4. page 3 --- parameterized as it usually is in control theory--- can you elaborate a bit on this?  what do you mean by parameterize controls?\n5. page 3 notation ->  xi:j and xi,j are mixed.\n6. page 5  ---- design a control policy pi: (x..  w 1:k ...)  -> (w1:k-1)?\n7. page 7 circumstance -> circumvent? \n8. Remark 5   worse case -> worst case?\n9. page 10 what do you mean by \"disturbance is discontinuous and noisy\"?  it is a bit inaccurate description\n10. page 11 top   Not -> note?\n11. Appendix B   --- not convex in Kfb Kff.   -> perhaps add \"in general\"?", "broader_impact_concerns": "No immediate concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pjoVmq5TnA", "reviewer": "Reviewer_eMQ1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThe results appear to be rigorous. It is a novel problem that is of potential importance. \n\nWeaknesses:\nThe biggest weakness is that the restrictive form of the tracking signal appears to enable a simple solution that is not pursued by the authors.\n\nIn particular, it is assumed that the reference signal is $r_k$ where \n\\begin{align*}\nz_{k+1}&=Sz_k, \\\\\\\\\nr_k &=Fz_k\n\\end{align*}\nIt is assumed that $z_k$ is not directly measured, and $S$ and $F$ are unknown. \n\nThe issue here is that in this setup, a valid realization for $(S,F)$ can be computed exactly in a finite number of steps. (I think the required number is $O(\\ell)$, where $\\ell$ is the observability index, but I haven't checked this part closely.)\n\nIn particular, take any $d\\ge \\ell$. Then for all $k\\ge d$, $r_k$ satisfies a recursion of the form:\n$$\nr_k = -\\sum_{i=1}^d \\Theta_i r_{k-i}\n$$\nIn this case, the observer canonical form given by:\n\\begin{align*}\nS &= \\begin{bmatrix}\n-\\Theta_1 & I & 0 & \\cdots & 0\\\\\\\\\n-\\Theta_2 & 0 & I & \\cdots  & 0\\\\\\\\\n\\vdots & & & \\ddots & \\\\\\\\\n-\\Theta_{d-1} & 0 & 0 & \\cdots & I\\\\\\\\\n-\\Theta_d & 0 & 0 & \\cdots & 0\n\\end{bmatrix} \\\\\\\\\nF &= \\begin{bmatrix}I & 0 \\cdots & 0\\end{bmatrix}\n\\end{align*}\ngives an observable realization of the process $r_k$. Furthermore, the initial condition, $z_0$, can be found by inverting the corresponding  observability matrix. \n\nSo, to get all of the data you need to completely predict all of the $r_k$ values, you just need to estimate $\\Theta_i$ values. These can be computed by solving a system of linear equations. \n\nAt this point, the tracking part can be solved by just designing a feed-forward term, separately from the online learning component. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper formulates a tracking version of online linear control with convex costs. A variation of disturbance-based controllers with extra terms for tracking is proposed. It is shown that low-regret can be achieved by a variation of online gradient descent that is fairly similar to previous approaches to online control. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would suggest the authors examine whether the work required to do tracking for this setup is really required or a simpler exact feedforward controller would suffice.", "broader_impact_concerns": "None. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "i5oeY3Cun4", "reviewer": "Reviewer_RbB5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Clear presentation in terms of language\n- Clear statement of the mathematical problem.\n\nWeaknesses:\n\n- The control problem is not as difficult or open as the authors are trying to convey\n- There are several technical issues, i.e., strong assumptions, missing analysis, weak comparisons to existing methods, etc.\n- Weak validation example.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose to tackle the problem of optimal trajectory tracking for known linear systems with bounded additive disturbances.\nThe authors propose a method based on memory of past disturbances and values of the reference trajectory. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "- Improve the list of references of existing methods that can solve the problem at hand, e.g., ADP methods, see Professor's Kyriakos G. Vamvoudakis work, adaptive methods including adaptive output regulators.\n\n- Explain why the problem of output tracking for known linear models is more complex/useful than the problem of output tracking for unknown linear models ? I mean the later is solved by ADP methods (see again Vamvoudakis' work) and includes the simpler case of known linear models with unknown bounded additive uncertainties (which can be considered as part of the unknown linear model state matrix).\n\n- Why citing Khalil's book for robust linear control ? This is not the proper reference for this control theory area; I suggest, Landau's books or J.C.Doyle's book, etc. Khalil's is the reference for deterministic nonlinear control.\n\n- Speaking of Khalil's book, there you can find the so called 'Lyapunov reconstruction' for nonlinear models, which easily applies to linear models, and can solve your simple tracking problem for bounded additive uncertainties, if the upper bound is known, which is the case here.\n\n- Notations need improvement: sometimes you use 't' and then use 'k' to denote times instances.\n\n- You assume that the reference model for the trajectory is unknown, yet you use the observability index 'l' in the controller design, .e.g, equations 9, 19. How do you plan to compute 'l' ?\n\n- Why is LQR the best controller for the case of Gaussian additive disturbances ? what about LQG ?! which is exactly meant for the case of Gaussian additive uncertainties.\n\n- In the numerical section, and frankly all over the paper, you should compare your algorithm to other methods, e.g., adaptive control methods (e.g., adaptive output regulators), LQG, Lyapunov reconstruction, ADPs, etc. LQR/H_infty are not the best methods to use in this context.\n\n- The analysis of the transient stability seems to be missing. The stability of the controller during learning is important if you want to use your method online, which seems to be the case here. Some boundedness guarantees between the disturbance bound and the tracking error bound need to be computed, e.g., Input-state stability arguments.\n\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: **Summary:**
The paper considers a linear dynamical system with a known dynamical system and provides an online algorithm for tracking a reference signal of an unknown linear dynamical system under an adversarial disturbance. The algorithm minimizes an additive cost function, which belongs to a subset of convex loss functions, and provides regret guarantee compared to the best linear feedback controller in hindsight.


**Evaluation:**
After discussions between the reviewers and the authors, and two revisions of the papers during the discussion period, the reviewers all agree that this paper can be accepted.


Although the reviewers believe that this paper's contribution may not be the most significant one in this line of work (eMQ1) or that the proposed method may not be practically as useful as other (nonlinear) controllers that can presumably perform better (RbB5) (though without any regret guarantees, as this paper), it still has notable contributions and provides reasonably good evidence to support it that warrant its publication.

After reading the revised version of the paper myself and comparing notes with the reviewers, I **recommend the acceptance of the paper with minor revisions.**

The minor revision is requested to ensure that the paper goes through a careful round of revising by the authors and be as clear as possible. This will hopefully make it a better and more readable paper.


**Comments:**



*The writing of the paper has room for improvement.* 
Some examples:
- Some of the remarks are clearly reactions to the reviewers' comments. They might be adequate for the reviewers, but they disrupt the flow of the paper for a reader who is not aware of the discussions. Remark 5 is an instance. Please revise the paper by making these remarks a more integrated part of the paper.

- Different types of disturbances in Section 6.2 follow an odd order: the paper first describes the "fourth case" (Gaussian), then "fifth case" (Random walk), etc.

- There are a few typos in the paper. For example,
- [p1] "The account for the effect ..." should be "To account for ..."
- [p21] "... matrix can be spans by ..." should be "... can be spanned by ..."
Other reviewers have also spotted typos, so please fix all of them, if you have not already done so.


*I have some concerns about the statement of Theorem 4 and its consequences, and I believe it requires some clarifications:*

+ First, is it assumed that T is fixed? This looks like the case because the choice of learning rate and H are T-dependent (and not t-dependent). If that is the case, one cannot simply let T goes to infinity as in Remark 9. One can use a doubling trick to deal with it, but that should be stated and analyzed clearly.

+ Second, the last conclusion of Remark 9 that the LHS converges to the RHS is not correct. The LHS is less than or equal to RHS, but the regret guarantee does not necessarily show the convergence. Your algorithm might actually be better than the best linear feedback controller.


*Why is the regret defined based on the best linear feedback controller in hindsight?* 
If I understand correctly, the linear feedback controller, defined in Eq. (3), is the right class when there is no disturbance, but it is not necessarily the right class when we have disturbances. Am I missing something?

*Assumption 5 is strong and the choices of $\Pi_P$ and $\Pi_M$ in the algorithm are unclear.*
The second part of Assumption requires M and P obtained by the algorithm be bounded. This sounds like a requirement on the algorithm and not an assumption. So, I wonder whether this boundedness is enforced by the choice of $\Pi_P$ and $\Pi_M$ in the algorithm? The paper is not clear about it.
If it is not enforced, why should we expect a gradient descent algorithm stay bounded?

Decision: Accept (poster)