# Sub-linear Regret in Adaptive Model Predictive Control

Damianos Tranos  Alexandre Proutiere

###### Abstract

We consider the problem of adaptive Model Predictive Control (MPC) for
uncertain linear-systems with additive disturbances and with state and input
constraints. We present STT-MPC (Self-Tuning Tube-based Model Predictive
Control), an online algorithm that combines the certainty-equivalence
principle and polytopic tubes. Specifically, at any given step, STT-MPC infers
the system dynamics using the Least Squares Estimator (LSE), and applies a
controller obtained by solving an MPC problem using these estimates. The use
of polytopic tubes is so that, despite the uncertainties, state and input
constraints are satisfied, and recursive-feasibility and asymptotic stability
hold. In this work, we analyze the regret of the algorithm, when compared to
an oracle algorithm initially aware of the system dynamics. We establish that
the expected regret of STT-MPC does not exceed $O(T^{1/2+\epsilon})$, where
$\epsilon\in(0,1)$ is a design parameter tuning the persistent excitation
component of the algorithm. Our result relies on a recently proposed
exponential decay of sensitivity property and, to the best of our knowledge,
is the first of its kind in this setting. We illustrate the performance of our
algorithm using a simple numerical example.

Regret Analysis, Model Predictive Control, Adaptive Control

##  1 Introduction

The problem of optimal decision making for uncertain dynamical systems has
been studied in both the control and the learning communities, and is referred
to as stochastic optimal control, adaptive control, or reinforcement learning.
A fundamental special case of this problem is the online (or adaptive) Linear
Quadratic Regulator (LQR) which deals with the optimal control of systems with
linear dynamics (Recht, 2019). Early efforts in the control community yielded
algorithms with asymptotic performance and stability guarantees (Åström &
Wittenmark, 1973; Lai, 1986). Over the last decade, the problem has been
revisited in the learning community (see e.g. (Abbasi-Yadkori & Szepesvári,
2011; Mania et al., 2019; Goel & Hassibi, 2022; Jedra & Proutiere, 2022) and
references therein), with the aim of devising algorithms with finite-time
guarantees on the regret, defined as the difference between the cumulative
cost of the learning algorithm and that of an oracle which has perfect
knowledge of the system.

All aforementioned studies deal with the simple LQR problem and cannot account
for constraints on the system state and input. These constraints are important
in applications as they capture both the inherent limitations (e.g position,
velocity, and actuator limits) as well as limitations imposed due to safety or
the cost of operating the system. Unfortunately, it is well known that
directly solving a constrained LQR problem is in general intractable because
of the infinite time horizon (Scokaert & Rawlings, 1998). A way to circumvent
this issue is to use Model Predictive Control (MPC) which solves a finite-time
constrained optimization problem in a receding horizon manner.

Early work in the control community led to a better understanding of the
connection between MPC and LQR and to algorithms with recursive feasibility
and asymptotic stability guarantees (Mayne et al., 2000). In parallel, the
tube MPC framework was developed to achieve the robust satisfaction of
constraints in the presence of uncertainties (Mayne et al., 2005). Recently,
online MPC algorithms, combining tube MPC and adaptive strategies (to cope
with the system uncertainty), have been proposed and shown to ensure recursive
feasibility and asymptotic stability (Lorenzen et al., 2017; Lu & Cannon,
2019; Lu et al., 2021), and (Tranos et al., 2022). The learning community has
also begun to investigate MPC, again with the aim of providing finite-time
regret guarantees (Li et al., 2019; Yu et al., 2020; Zhang et al., 2021; Lin
et al., 2021, 2022). A key limitation of these analyses is that they are valid
only in the absence of constraints which goes against the main motivation of
MPC (Bitmead et al., 1990). Furthermore, most of these works assume to have
access to (often perfect) system dynamics predictions. And those not making
this assumption yield regret bounds having the cost of the oracle as an
additive term. In turn, this term may scale linearly with time in the presence
of constraints and additive disturbances.

In this work, we present STT-MPC, an adaptive MPC algorithm originally
proposed in (Tranos et al., 2022). Inspired by the analysis pipeline of (Lin
et al., 2022), we leverage the exponential decay of sensitivity property of
the underlying finite-time optimization problem (Shin et al., 2022) to provide
upper bounds of the expected regret of the algorithm. Specifically, we show
that this regret scales at most as $T^{1/2+\epsilon}$ where $\epsilon\in(0,1)$
is a design parameter tuning the persitent excitation component of the
algorithm.

Notation. For a time dependent vector $x_{t}$, we denote by $x_{k|t}$ its
prediction at time $k+t$ given information at time $t$. For any two sets
$\mathcal{A}$ and $\mathcal{B}$, we define their Minkowski sum as the set
$\mathcal{A}\oplus\mathcal{B}:=\\{a+b:a\in\mathcal{A},\ b\in\mathcal{B}\\}$.
We also define, for any constant $\lambda\geq 0$, the scaled set
$\lambda\mathcal{A}:=\\{\lambda a,\ a\in\mathcal{A}\\}.$ For any
$d\in{\mathbb{N}}$, $x\in{\mathbb{R}}^{d}$, and $\epsilon>0$, let
$\mathcal{B}(x,\epsilon)=\\{y:\|y-x\|\leq\epsilon\\}$. Let
$\mathcal{B}=\mathcal{B}(0,1)$. For any set $\mathcal{S}$, and any
$\varepsilon>0$, there exists a polytope $\mathcal{P}$ that is an outer
approximation of $\mathcal{S}$, i.e.,
$\mathcal{S}\subset\mathcal{P}\oplus\varepsilon\mathcal{B}$. We refer to this
polytope as the outer polyhedral approximation of $\mathcal{S}$. Unless stated
otherwise, we use $\lVert\cdot\rVert$ to denote the Euclidean norm for vectors
and the Frobenius norm for matrices.

##  2 Problem Setting

We consider the following discrete time, linear, time-invariant system:

$\displaystyle x_{t+1}=A(\theta^{\star})x_{t}+B(\theta^{\star})u_{t}+w_{t},$
(1)

where $x_{t},w_{t}\in\mathbb{R}^{d_{x}}$ and $u_{t}\in\mathbb{R}^{d_{u}}$. The
state transition and state-action transition matrices $A(\theta^{\star})$ and
$B(\theta^{\star})$ are initially unknown. The set of possible such matrices
is parameterized by $\theta\in\mathbb{R}^{d_{\theta}}$ (here $\theta$ could
well parameterize each entry of the matrices, in which case
$d_{\theta}=d_{x}(d_{x}+d_{u})$). To simplify the notation, for two possible
parameters $\theta_{1},\theta_{2}$, we define
$\lVert\theta_{1}-\theta_{2}\rVert:=\max(\lVert
A(\theta_{1})-A(\theta_{2})\rVert,\lVert B(\theta_{1})-B(\theta_{2})\rVert)$.
We make the following assumptions.

######  Assumption 2.1 (Parameter uncertainty).

The decision maker does not know $\theta^{\star}$, but knows that
$\theta^{\star}\in\Theta_{0}$ where $\Theta_{0}$ is a convex polytope.
Moreover, there exists $\epsilon_{0}>0$ such that ${\cal
B}(\theta^{*},\epsilon_{0})\subset\Theta_{0}$.

######  Assumption 2.2 (Additive disturbance).

The sequence $(w_{t})_{t\geq 0}$ is i.i.d, and for each $t\geq 0$, $w_{t}$ is
zero-mean, isotropic, with support in the ball $\mathcal{B}(0,3\sigma)$.
Hence, $w_{t}$ is $\sigma^{2}$-sub-gaussian. Further define $\mathcal{W}$, a
convex polytope providing a conservative approximation of
$\mathcal{B}(0,3\sigma)$, i.e., $\mathcal{B}(0,3\sigma)\subset\mathcal{W}$.

######  Assumption 2.3 (State and input constraints).

The set

$\displaystyle\mathcal{C}=\\{(x,u)\in{\mathbb{R}}^{d_{x}}\times{\mathbb{R}}^{d_{u}}:Fx+Gu\leq\textbf{1}\\}.$

is compact and contains the origin in its interior. Here,
$F\in{\mathbb{R}}^{d_{c}\times d_{x}}$ and $G\in{\mathbb{R}}^{d_{c}\times
d_{u}}$ define the state and input constraints respectively. The above
inequality holds component-wise, and 1 is the vector with all components equal
to 1.

######  Assumption 2.4 (Stabilizing Controller).

There exists a known, robustly stabilizing feedback gain $K$ such that
$A(\theta)+B(\theta)K$ is stable (i.e., $\rho(A(\theta)+B(\theta)K)<1$) for
all $\theta\in\Theta_{0}$.

##  3 Model Predictive Control

We wish to minimize the long-term cost defined as
$\lim\sup_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}{\mathbb{E}}\left[x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}\right]$,
through some positive semi-definite matrices $Q,R$. To this aim, we use MPC,
with a receding horizon $N$. Specifically, at time $t$, given the current
system state $x_{t}$ and the past observations used to derive an estimator
$\theta_{t}$ of $\theta^{\star}$, we will identify a control policy
$(u_{k|t})_{k=0,\ldots,N-1}$ minimizing the cost along a predicted system
trajectory $(x_{k|t})_{k=0,\ldots,N}$. We use the well-known dual mode
prediction paradigm (Kouvaritakis & Cannon, 2016) with the following predicted
control sequence,

$\displaystyle u_{k|t}=\begin{cases}Kx_{k|t}+v_{k|t}\quad\forall
k\in\\{0,\dots,N-1\\},\\\ Kx_{k|t}\quad\forall k\geq N,\end{cases}$

where $\\{v_{0|t},\dots v_{N-1|t}\\}$ are the optimization variables to be
determined by the MPC. The resulting prediction dynamics will be for
$k\in\\{0,\dots,N-1\\}$,

$\displaystyle x_{0|t}$ $\displaystyle=x_{t},$ $\displaystyle x_{k+1|t}$
$\displaystyle=\Phi(\theta_{t})x_{k|t}+B(\theta_{t})v_{k|t},$

where $\Phi(\theta):=A(\theta)+B(\theta)K$ for any $\theta\in\Theta_{0}$.

###  3.1 LSE and persistent excitation

Our algorithm starts with an initial parameter $\theta_{0}\in\Theta_{0}$,
which is then updated using the LSE. We let $\theta_{1}=\theta_{0}$. For
$t\geq 2$, the LSE enjoys the following explicit expression:

$\displaystyle\hat{\theta}_{t}={\left(\sum\limits_{k=0}^{t-2}x_{k+1}\begin{bmatrix}x_{k}\\\
u_{k}\end{bmatrix}^{\top}\right)\left(\sum\limits_{k=0}^{t-2}\begin{bmatrix}x_{k}\\\
u_{k}\end{bmatrix}\begin{bmatrix}x_{k}\\\
u_{k}\end{bmatrix}^{\top}\right)^{\dagger}}.$

For $t\geq t^{\star}(\delta)$ (to be defined later), we align our prediction
parameter $\theta_{t}$ to $\hat{\theta}_{t}$. As shown in (Jedra & Proutiere,
2022), a finite-time analysis of the performance of the LSE is rather
intricate but possible even if the feedback controller varies over time. The
performance is tightly related to the minimal eigenvalue of the cumulative
covariate matrix $\lambda_{\min}(\sum_{s=0}^{t-2}y_{s}y_{s}^{\top})$ where
$y_{s}=\begin{bmatrix}x_{s}\\\ u_{s}\end{bmatrix}$. More precisely, for the
LSE to lead to a good approximation of $\theta^{\star}$, we need to ensure
that this eigenvalue grows with time. To this aim, we add an isotropic and
bounded noise to the control input. This noise is represented by the random
vector $\zeta_{t}$ taken to be the projection of $\xi_{t}$ on
$\mathcal{B}(0,3\sigma_{t})$, where $\xi_{t}$ is i.i.d. according to a normal
distribution, i.e., $\xi_{t}\sim\mathcal{N}(0,\sigma_{t}^{2}I_{d_{u}})$. The
choice of $\sigma_{t}$ directly impacts the performance of the LSE but also
the overall performance of the controller (a higher $\sigma_{t}$ means higher
excitation and hence better LSE, but at the expense of a worse overall
controller). Here we set $\sigma_{t}^{2}=\sqrt{d_{x}}\sigma^{2}t^{-\alpha}$
for some $\alpha\in(0,1)$. This ensures that (i) the LSE $\theta_{t}$
converges to $\theta^{\star}$ and (ii) the controller converges to that
obtained through a classical tube-based MPC framework with known
$\theta^{\star}$. In (Tranos et al., 2022), we have shown that the following
good event ${\cal G}$ holds with probability at least $1-\delta$:

${\cal G}=\left(\|\hat{\theta}_{t}-\theta^{\star}\|\leq\epsilon_{t},\ \forall
t\geq t^{\star}(\delta)\right),$

where $t^{\star}(\delta)=c_{1}+c_{2}\log(1/\delta)$ and
$\epsilon_{t}^{2}=c_{3}\log(t/\delta)/t^{1-\alpha}$ for some positive
constants $c_{1},c_{2},c_{3}$. Next, we define $\Delta_{t}$ as an outer
polyhedral approximation of $\mathcal{B}(\theta_{t},2\epsilon_{t})$. We
further recursively define the uncertainty sets as follows:
$\Theta_{t}=\Theta_{t-1}\cap\Delta_{t}$ for all $t\geq t^{\star}(\delta)$ and
$\Theta_{t}=\Theta_{0}$ for $t<t^{\star}(\delta)$. By construction, the true
parameter $\theta^{\star}$ belongs to the interior of $\Theta_{t}$ with high
probability in the following sense:

######  Lemma 3.1.

Under event ${\cal G}$,
$\mathcal{B}(\theta^{\star},\epsilon_{t})\subset\Theta_{t}$ for all $t\geq 1$.

###### Proof.

For $t<t^{\star}(\delta)$ we have $\Theta_{t}=\Theta_{0}$ and the result holds
by Assumption 2.1. Let $t\geq t^{\star}(\delta)$. We show that
$\mathcal{B}(\theta^{*},\epsilon_{t})\subset\Delta_{t}$ and
$\mathcal{B}(\theta^{*},\epsilon_{t})\subset\Theta_{t-1}$. For the first, we
have for all $\theta\in\mathcal{B}(\theta^{*},\epsilon_{t})$, using the
triangle inequality:
$\lVert\theta-\theta_{t}\rVert\leq\lVert\theta-\theta^{*}\rVert+\lVert\theta_{t}-\theta^{*}\rVert\leq
2\epsilon_{t}$, where the second inequality holds under ${\cal G}$. Thus
$\theta\in\mathcal{B}(\theta_{t},2\epsilon_{t})$ and so
$\mathcal{B}(\theta^{*},\epsilon_{t})\subset\mathcal{B}(\theta_{t},2\epsilon_{t})\subset\Delta_{t}$.
We prove $\mathcal{B}(\theta^{*},\epsilon_{t})\subset\Theta_{t-1}$ by
induction. Assume that
$\mathcal{B}(\theta^{*},\epsilon_{t})\subset\Theta_{t-1}$. Then we show that
$\mathcal{B}(\theta^{*},\epsilon_{t+1})\subset\Theta_{t}$. Let $\theta$ such
that $\|\theta-\theta^{\star}\|\leq\epsilon_{t+1}$. Then
$\|\theta-\theta_{t}\|\leq\lVert\theta-\theta^{*}\rVert+\lVert\theta_{t}-\theta^{*}\rVert\leq\epsilon_{t+1}+\epsilon_{t}$.
This implies that $\theta\in\Delta_{t}$. In addition, $\theta\in\Theta_{t-1}$.
Indeed, $\|\theta-\theta^{\star}\|\leq\epsilon_{t+1}\leq\epsilon_{t}$, and we
conclude using the induction assumption. Hence $\theta\in\Theta_{t}$. $\Box$

Algorithm 1 STT-MPC

Input: Initial state $x_{0}$; confidence $\delta$; estimate $\theta_{0}$;
uncertain parameter set $\Theta_{0}$

Find stabilizing matrix $K$ for all $\theta\in\Theta_{0}$

Compute matrices $T$ and $H_{c}$

for $t=1,\dots,\mathcal{T}$ do

if $t<t^{\star}(\delta)$ then

Set $\theta_{t}\leftarrow\theta_{t-1}$ and $\Theta_{t}\leftarrow\Theta_{t-1}$

else

Update $\theta_{t}\leftarrow\hat{\theta}_{t}$

Compute $\Delta_{t}$ and set $\Theta_{t}\leftarrow\Theta_{t-1}\cap\Delta_{t}$

end if

Compute matrices $H_{t}^{(j)}$

Solve $\mathcal{P}_{N}(x_{t},\theta_{\rho(t)})$ and obtain $v^{\pi}_{0|t}$

Apply $u_{t}=Kx_{t}+v^{\pi}_{0|t}+\zeta_{t}$

end for

###  3.2 Polytopic tubes and associated linear constraints

With the considered control inputs, the system can be rewriten as

$x_{t+1}=\Phi(\theta^{\star})x_{t}+B(\theta^{\star})(v_{0|t}+\zeta_{t})+w_{t}.$

We apply a tube-based approach, and at time $t$, we build a polytopic tube
based on:

  * (i)

$\Theta_{t}$, encoding the uncertainty about $\theta^{\star}$. We denote by
$m$ the number of vertices of $\Theta_{t}$, and the vertices themselves by
$\theta_{t}^{(j)}$, $j=1,\ldots,m$.

  * (ii)

A polytope $\bar{\mathcal{W}}_{t}$, handling the uncertainty due to the noise
$B(\theta^{\star})\zeta_{t}+w_{t}$, including that due to the persistent
excitation. To define $\bar{\mathcal{W}}_{t}$, let
$\bar{B}_{t}=\max_{\theta\in\Theta_{t}}\lVert B(\theta)\rVert_{2}$. We define
$\mathcal{Z}_{t}$ as the outer polyhedral approximation to
$\mathcal{B}(0,3\sigma_{t})$, and
$\bar{\mathcal{W}}_{t}=\mathcal{W}\oplus\bar{B}_{t}\mathcal{Z}_{t}$.

We define the state tube cross sections as the sets: for $k=0,\ldots,N$,

$\displaystyle X_{k|t}=\\{x:Tx\leq\alpha_{k|t}\\},$

where the matrix $T\in{\mathbb{R}}^{d_{\alpha}\times d_{x}}$ is chosen such
that, for some $\lambda\in[0,1)$, the set $\\{x:Tx\leq\mathbf{1}\\}$ is
$\lambda$-contractive with respect to the system $x_{t+1}=\Phi(\theta)x_{t}$
for all $\theta\in\Theta_{0}$. This property is needed to ensure the robust
positive invariance of $X_{N|t}$ (see Lemma 5.7 in (Kouvaritakis & Cannon,
2016)). To derive the associated linear constraints, we apply a standard
result to ensure inclusion of polyhedra (see Proposition 3.31 in (Blanchini &
Miani, 2008)). More precisely, for any $j=1,\ldots,m$, we have
$X_{k|t}\subseteq\\{x:\Phi(\theta_{t}^{(j)})x+B(\theta_{t}^{(j)})v_{k|t}+w\in
X_{k+1|t}\\}$ for all $w\in\bar{\mathcal{W}}_{t}$ if there exists
$H_{t}^{(j)}\geq 0$ such that:

$\displaystyle H_{t}^{(j)}T=T\Phi(\theta_{t}^{(j)}),$ $\displaystyle
H_{t}^{(j)}\alpha_{k|t}+TB(\theta_{t}^{(j)})v_{k|t}+\bar{w}_{t}\leq\alpha_{k+1|t},$

where $\bar{w}_{t}$ is such that
$[\bar{w}_{t}]_{i}=\max_{w\in\bar{\mathcal{W}}_{t}}[Tw]_{i}$ for
$i\in\\{1,\dots,d_{\alpha}\\}$. Similarly, we have
$X_{k|t}\subseteq\\{x:(F+GK)x+G(v_{k|t}+\zeta)\leq\textbf{1}\\}$ for all
$\zeta\in\mathcal{Z}_{t}$, if there exists $H_{c}\geq 0$, such that:

$\displaystyle H_{c}T=F+GK$ $\displaystyle
H_{c}\alpha_{k|t}+Gv_{k|t}+\bar{\zeta}_{t}\leq\textbf{1},$

where $\bar{\zeta}_{t}$ is such that
$[\bar{\zeta}_{t}]_{i}=\max_{\zeta\in\mathcal{Z}_{t}}[G\zeta]_{i}$ for
$i\in\\{1,\dots,d_{c}\\}$.

######  Remark 3.2.

For simplicity, we have chosen $\bar{w}_{t}$ and $\bar{\zeta}_{t}$ so as to be
conservative with respect to the noise we apply. However, notice that we could
well pre-sample the noise sequence $(\zeta_{t})_{t\geq 0}$ and use it as part
of our predictions.

The matrices $H_{t}^{(j)}$, and $H_{c}$ are chosen such that for all
$i\in\\{1,\dots,d_{\alpha}\\}$ and for all $j\in\\{1,\dots,m\\}$,

$\displaystyle\big{(}H_{t}^{(j)}\big{)}_{i}$
$\displaystyle=\arg\min_{h}\\{\textbf{1}^{\top}h:h^{\top}T=(T)_{i}\Phi(\theta_{t}^{(j)}),\
h\geq 0\\},$ and for all $i\in\\{1,\dots,d_{c}\\}$,
$\displaystyle\big{(}H_{c}\big{)}_{i}$
$\displaystyle=\arg\min_{h}\\{\textbf{1}^{\top}h:h^{\top}T=(F+GK)_{i},\ h\geq
0\\}.$

Finally, we have the terminal conditions

$\displaystyle H_{t}^{(j)}\alpha_{N}+\bar{w}_{t}$
$\displaystyle\leq\alpha_{N},$ $\displaystyle H_{c}\alpha_{N}+\bar{\zeta}_{t}$
$\displaystyle\leq\mathbf{1}.$

###  3.3 The tube MPC problem

Let $\boldsymbol{v}_{t}=\\{v_{0|t},\dots,v_{N-1|t}\\}$ and
$\boldsymbol{\alpha}_{t}=\\{\alpha_{0|t},\dots,\alpha_{N|t}\\}$. The resulting
tube MPC problem, denoted as $\mathcal{P}_{N}(x_{t},\theta)$ for any parameter
$\theta$ is:

$\displaystyle\underset{\boldsymbol{v}_{t},\boldsymbol{\alpha}_{t}}{\textnormal{minimize}}\sum_{k=0}^{N-1}\left(\
x_{k|t}^{\top}Qx_{k|t}+v_{k|t}^{\top}Rv_{k|t}\right)+x_{N|t}^{\top}P(\theta)x_{N|t}$
$\displaystyle\textnormal{subject to},\textnormal{for all
}j=1,\dots,m,\textnormal{and }k=0,\dots,N-1:$ initial constraints:
$\displaystyle\quad x_{0|t}=x_{t},$ (6) $\displaystyle\quad
Tx_{0|t}\leq\alpha_{0|t},$ (7) $\displaystyle\textnormal{system constraints},$
$\displaystyle\quad x_{k+1|t}=\Phi(\theta)x_{k|t}+B(\theta)v_{k|t},$ (8)
$\displaystyle\textnormal{tube constraints},$ $\displaystyle\quad
H_{t}^{(j)}\alpha_{k|t}+TB(\theta^{(j)})v_{k|t}+\bar{w}_{t}\leq\alpha_{k+1|t},$
(9) $\displaystyle\quad
H_{c}\alpha_{k|t}+Gv_{k|t}+\bar{\zeta}_{t}\leq\mathbf{1},$ (10) terminal
constraints: $\displaystyle\quad
H_{t}^{(j)}\alpha_{N|t}+\bar{w}_{t}\leq\alpha_{N|t},$ (11) $\displaystyle\quad
H_{c}\alpha_{N|t}+\bar{\zeta}_{t}\leq\mathbf{1}.$ (12)

where $P(\theta)$ is obtained by solving the Lyapunov equation:

$\displaystyle
P(\theta)-\Phi(\theta)^{\top}P(\theta)\Phi(\theta)=Q+K^{\top}RK$ (13)

######  Remark 3.3.

The oracle tube-MPC problem $\mathcal{P}_{N}(x_{t},\theta^{\star})$ is
similarly defined by setting $\theta=\theta^{\star}$,
$\bar{w}_{t}=\bar{w}_{t}^{\star}$ (with
$[\bar{w}_{t}^{\star}]_{i}=\max_{w\in\mathcal{W}}[Tw]_{i}$, for
$i\in\\{1,\dots,d_{\alpha}\\}$), and $m=1$. The later can be achieved by
Algorithm 1 by removing redundant constraints at every iteration by solving a
linear program or one of the methods outlined in (Paulraj et al., 2010).

The feasibility of the above problem depends on whether
$\theta^{\star}\in\Theta_{t}$, i.e., on the event ${\cal G}$. However, for the
sake of the analysis, we would like to ensure that the problem the algorithm
solves in each step is always feasible (with probability 1). This is necessary
for establishing that ${\cal G}$ holds with probability at least $1-\delta$
(Theorem 1 of (Tranos et al., 2022)) as well as for our regret analysis. To
ensure that the tube MPC problem is always feasible, i.e., even when
$\mathcal{G}$ does not occur, we instead solve
$\mathcal{P}_{N}(x_{t},\theta_{\rho(t)})$111More precisely, the problem is
obtained by replacing $\theta_{t}$ by $\theta_{\rho(t)}$, $H_{t}^{(j)}$ by
$H_{\rho(t)}^{(j)}$ for all $j$ in $\mathcal{P}_{N}(x_{t},\theta_{t})$. in
Algorithm 1 where,

$\displaystyle\rho(t):=\max\\{\tau\leq t:\mathcal{P}_{N}(x_{t},\theta_{\tau})\
\textnormal{is feasible}\\}.$

Essentially, in the unlikely event that $\mathcal{P}_{N}(x_{t},\theta_{t})$ is
not feasible, we instead solve $\mathcal{P}_{N}(x_{t},\theta_{\tau})$ using
the latest estimates $\theta_{\tau}$ and $\Theta_{\tau}$ for which the problem
is feasible. This modification is of little practical consequence as we can
(and typically do) choose $\delta$ to be very small.

With this, we may state the recursive feasibility property of STT-MPC (Theorem
2 in (Tranos et al., 2022)):

######  Theorem 3.4.

If the optimization problem $\mathcal{P}_{N}(x_{0},\theta_{0})$ is feasible
for initial state $x_{0}\in{\mathbb{R}}^{d_{x}}$ and parameter
$\theta_{0}\in\Theta_{0}$, then, for all $t>0$,
(i) under event $\mathcal{G}$, the problem $\mathcal{P}_{N}(x_{t},\theta_{t})$
is feasible;
(ii) the problem $\mathcal{P}_{N}(x_{t},\theta_{\rho(t)})$ is feasible.

##  4 Regret Analysis

In this section, we present our main result, an upper bound on the expected
regret of STT-MPC. To state our main theorem, we introduce the following
notation. Let $\Pi$ be the set of all tube-MPC algorithms (which are
parameterized by $\theta$). For an algorithm $\pi\in\Pi$, define
$(x_{0}^{\pi},u_{0}^{\pi},\dots,x_{t}^{\pi},u_{t}^{\pi})$ as the sequence of
states and control inputs generated under $\pi$, with $x_{0}^{\pi}=x_{0}$. We
also define by $v_{t}^{\pi}(x,\theta):=v_{0|t}^{\pi}(x,\theta)$, the first
element of the solution of the optimization problem
$\mathcal{P}_{N}(x,\theta)$. We denote by $z_{t}^{\pi}(x)$ the state of the
system (1) at time $t$ under algorithm $\pi$ given initial state $x$, and we
denote by $y_{t}^{\pi}(x)$, the associated output of $\pi$. Let
$\pi_{\star}\in\Pi$ be the oracle tube-MPC problem
$\mathcal{P}_{N}(x,\theta^{\star})$. We simplify the notation by replacing
$\pi_{\star}$ by $\star$, e.g., $x_{t}^{\star}$, $v_{t}^{\star}$ and so on. We
define the regret $R_{T}(\pi)$ of an algorithm $\pi$ as:

$\displaystyle R_{T}(\pi)=\sum_{t=0}^{T-1}(\lVert
x_{t}^{\pi}\rVert^{2}_{Q}+\lVert
u_{t}^{\pi}\rVert^{2}_{R})-\sum_{t=0}^{T-1}(\lVert
x_{t}^{\star}\rVert^{2}_{Q}+\lVert u_{t}^{\star}\rVert^{2}_{R}).$

######  Theorem 4.1.

The regret of $\pi$ = STT-MPC with confidence $\delta$ and persistent
excitation parameter $\alpha:=2\epsilon$, with $\epsilon\in(0,1)$ satisfies
for all $T\geq 1$, with probability at least $1-\delta$,

$R_{T}(\pi)\leq
C\left((\log(T/\delta)^{1/2}+1)T^{1/2+\epsilon}+\log(1/\delta)+1\right),$

for some universal constant $C>0$. Now when the confidence is set to
$1/T^{2}$, we get

$\displaystyle{\mathbb{E}}[R_{T}(\pi)\leq
C^{\prime}\log(T)^{1/2}T^{1/2+\epsilon},$

where $C^{\prime}$ is a universal constant.

###### Proof.

We first express the regret as the sum of differences between the states and
inputs,

$\displaystyle R_{T}(\pi)=$
$\displaystyle\sum_{t=0}^{T-1}\left({x_{t}^{\pi}}^{\top}Q(x_{t}^{\pi}-x_{t}^{\star})+(x_{t}^{\pi}-x_{t}^{\star})^{\top}Qx_{t}^{\star}\right)$
$\displaystyle+\sum_{t=0}^{T-1}\left({u_{t}^{\pi}}^{\top}R(u_{t}^{\pi}-u_{t}^{\star})+(u_{t}^{\pi}-u_{t}^{\star})^{\top}Ru_{t}^{\star}\right)$
$\displaystyle\leq$ $\displaystyle\sum_{t=0}^{T-1}(\lVert
x_{t}^{\pi}\rVert+\lVert x_{t}^{\star}\rVert)\lVert Q\rVert\lVert
x_{t}^{\pi}-x_{t}^{\star}\rVert$ $\displaystyle+\sum_{t=0}^{T-1}(\lVert
u_{t}^{\pi}\rVert+\lVert u_{t}^{\star}\rVert)\lVert R\rVert\lVert
u_{t}^{\pi}-u_{t}^{\star}\rVert$ $\displaystyle=$
$\displaystyle\bar{Q}\sum_{t=0}^{T-1}\lVert
x_{t}^{\pi}-x_{t}^{\star}\rVert+\bar{R}\sum_{t=0}^{T-1}\lVert
u_{t}^{\pi}-u_{t}^{\star}\rVert,$

where the first inequality follows from Cauchy-Schwartz inequality, and the
second by defining $\bar{Q}:=2\lVert Q\rVert\bar{x}$ and $\bar{R}:=2\lVert
R\rVert\bar{u}$ with $\bar{x}=\max_{(x,u)\in{\cal C}}\\{\lVert x\rVert\\}$ and
$\bar{u}=\max_{(x,u)\in{\cal C}}\\{\lVert u\rVert\\}$. Note that $\bar{Q}$ and
$\bar{R}$ are well defined since the constraint set $\mathcal{C}$ is compact
by Assumption 2.3. Further note that $(x_{t},u_{t})\in\mathcal{C}$ is
guaranteed by the recursive feasibility of STT-MPC (Theorem 3.4).

We seek to upper bound the quantities $\lVert x_{t}^{\pi}-x_{t}^{\star}\rVert$
and $\lVert u_{t}^{\pi}-u_{t}^{\star}\rVert$ in terms of
$\lVert\theta_{t}-\theta^{\star}\rVert$. To this end, we make use of the
following theorem, presented originally in (Shin et al., 2022) (Theorem 4.5)
for graph-structured nonlinear optimization problems, and specialized to
constrained nonlinear systems by (Lin et al., 2022) (Theorem H.1.).

######  Theorem 4.2.

For any tube-MPC algorithm $\pi\in\Pi$, there exists $R>0$ such that, for
$x_{i},x_{i}^{\prime}\in B(x^{\star}_{i},R)$, where $i\in\\{0,\dots,t\\}$, the
following perturbation bounds hold:

$\displaystyle\lVert
z_{t}^{\pi}(x_{i},\theta)-z_{t}^{\pi}(x_{i}^{\prime},\theta)\rVert\leq
q_{1}(t-i)\lVert x_{i}-x_{i}^{\prime}\rVert,$ (14)

and

$\displaystyle\lVert
v_{t}^{\pi}(x_{i},\theta)-v_{t}^{\pi}(x_{i},\theta^{\prime})\rVert\leq
q_{2}(t-i)\lVert\theta-\theta^{\prime}\rVert,$ (15)

where, for $j\in\\{1,2\\}$, $q_{j}(t)$ is a function such that
$\lim_{t\to\infty}\lim q_{j}(t)=0$ and $\sum_{t=0}^{\infty}q_{j}(t)\leq
C_{j}$, for some constant $C_{j}\geq 1$.

The bound (15) can be applied directly to the input error (along the
trajectory induced by $\pi$) $e_{t}:=\lVert
v_{t}^{\pi}-v_{t}^{\star}(x_{t}^{\pi})\rVert$, provided that
$x_{t}^{\pi}\in\mathcal{B}(x_{t}^{\star},R)$. Therefore, we show inductively
that if $e_{t}\leq R/(\lVert B(\theta^{\star})\rVert C_{1}^{2})$ then
$x_{t}^{\pi}\in\mathcal{B}(x_{t}^{\star},R/C_{1})$. First, observe that

$\displaystyle\lVert x^{\pi}_{t}-z^{\star}_{t}(x^{\pi}_{t-1})\rVert$
$\displaystyle=\lVert
B(\theta^{\star})(v_{t-1}^{\pi}-v_{t-1}^{\star}(x_{t-1}^{\pi}))\rVert$
$\displaystyle\leq\lVert B(\theta^{\star})\rVert e_{t-1},$ (16)

and so the condition holds for the base case of $t=0$, since
$x_{0}^{\pi}=x_{0}^{\star}$. Let our induction hypothesis be that it holds for
$0,\dots,t-1$. We will have

$\displaystyle\lVert x_{t}^{\pi}-x_{t}^{\star}\rVert$ $\displaystyle=\lVert
x_{t}^{\pi}-z_{t}^{\star}(x_{0})\rVert$ $\displaystyle\leq\lVert
x_{t}^{\pi}-z_{t}^{\star}(x_{t-1})\rVert+\sum_{i=1}^{t-1}\lVert
z_{t}^{\star}(x_{t-i})-z_{t}^{\star}(x_{t-i-1})\rVert$ $\displaystyle=\lVert
x_{t}^{\pi}-z_{t}^{\star}(x_{t-1})\rVert+\sum_{i=1}^{t-1}\lVert
z_{t}^{\star}(x_{t-i})-z_{t}^{\star}(z_{t-1}^{\star}(x_{t-i-1}))\rVert$
$\displaystyle\leq\lVert
x_{t}^{\pi}-z_{t}^{\star}(x_{t-1})\rVert+\sum_{i=1}^{t-1}q(i)\lVert
x_{t-i}-z_{t-i}^{\star}(x_{t-i-1})\rVert$
$\displaystyle\leq\sum_{i=0}^{t-1}q_{1}(i)\lVert
x_{t-i}-z_{t-i}^{\star}(x_{t-i-1})\rVert$ $\displaystyle\leq\lVert
B(\theta^{\star})\rVert\sum_{i=0}^{t-1}q_{1}(t)e_{t-i-1},$

where the first inequality is a straightforward application of the triangle
inequality, the second equality follows by the definition of $z^{\star}_{t}$,
and the third inequality is a direct application of (14) (noting that
$x_{t-i}^{\pi}\in\mathcal{B}(x_{t-i}^{\star},R/C_{1})$ by the induction
hypothesis). The last inequality follows from (16).

Now if we substitute $e_{t-i}\leq R/(\lVert B(\theta^{\star})\rVert
C_{1}^{2})$, we obtain

$\displaystyle\lVert x_{t}^{\pi}-x_{t}^{\star}\rVert\leq\lVert
B(\theta^{\star})\rVert\frac{R}{\lVert B(\theta^{\star})\rVert
C_{1}^{2}}\sum_{i=0}^{t-1}q_{1}(t)\leq\frac{R}{C_{1}},$

which proves the induction step.

Proceeding similarly, we obtain the following bound,

$\displaystyle\lVert v_{t}^{\pi}-v_{t}^{\star}\rVert$ $\displaystyle=\lVert
v_{t}^{\pi}-y_{t}^{\star}(x_{0})\rVert$ $\displaystyle\leq\lVert
v_{t}^{\pi}-y_{t}^{\star}(x_{t-1})\rVert+\sum_{i=0}^{t-1}\lVert
v_{t}^{\star}(x_{t-i})-y_{t}^{\star}(x_{t-i-1})\rVert$
$\displaystyle\leq\lVert
v_{t}^{\pi}-v_{t}^{\star}(x_{t-1})\rVert+\sum_{i=0}^{t-1}q_{1}(i)\lVert
x_{t-i}-z_{t-i}^{\star}(x_{t-i-1})\rVert$ $\displaystyle\leq e_{t}+\lVert
B(\theta^{\star})\rVert\sum_{i=0}^{t-1}q_{1}(t)e_{t-i-1},$

where again, we have used the triangle inequality for the first inequality,
and the bound (14) for the second. Finally, we have

$\displaystyle\lVert u^{\pi}_{t}-u^{\star}_{t}\rVert$ $\displaystyle=\lVert
v^{\pi}_{t}+\zeta_{t}-v^{\star}_{t}\rVert$ $\displaystyle\leq\lVert
v^{\pi}_{t}-v^{\star}_{t}\rVert+\lVert\zeta_{t}\rVert.$

With these bounds in hand, we first account for the regret up to time
$t^{\star}(\delta)$ while the event $\mathcal{G}$ holds. Note that a crude
bound is sufficient to show that it is finite:

$\displaystyle R_{t^{\star}(\delta)}(\pi)_{\mathcal{G}}$
$\displaystyle\leq\bar{Q}\sum_{t=0}^{t^{\star}(\delta)}\lVert
x_{t}^{\pi}-x_{t}^{\star}\rVert+\bar{R}\sum_{t=0}^{t^{\star}(\delta)}\lVert
u_{t}^{\pi}-u_{t}^{\star}\rVert$
$\displaystyle\leq(2\bar{Q}\bar{x}+2\bar{R}\bar{u})t^{\star}(\delta)$
$\displaystyle\leq\bar{C}_{2}+\bar{C}_{3}\log(1/\delta).$

Where $\bar{C}_{2}=(2\bar{Q}\bar{x}+2\bar{R}\bar{u})c_{2}$ and
$\bar{C}_{3}=(2\bar{Q}\bar{x}+2\bar{R}\bar{u})c_{3}$.

We then bound the regret from $t^{\star}(\delta)$ onward under the event
$\mathcal{G}$:

$\displaystyle(R_{T}(\pi)-R_{t^{\star}(\delta)}(\pi))_{\mathcal{G}}$
$\displaystyle\leq\bar{Q}\sum_{t=t^{\star}(\delta)}^{T-1}\lVert
x_{t}^{\pi}-x_{t}^{\star}\rVert+\bar{R}\sum_{t=t^{\star}(\delta)}^{T-1}\lVert
u_{t}^{\pi}-u_{t}^{\star}\rVert$
$\displaystyle\leq\bar{Q}\sum_{t=0}^{T-1}\lVert
x_{t}^{\pi}-x_{t}^{\star}\rVert+\bar{R}\sum_{t=0}^{T-1}\lVert
v^{\pi}_{t}-v^{\star}_{t}\rVert+\lVert\zeta_{t}\rVert$
$\displaystyle\leq\bar{Q}\sum_{t=0}^{T-1}\lVert B(\theta^{\star})\rVert
e_{t-1}$ $\displaystyle+\bar{R}\sum_{t=0}^{T-1}(e_{t}+\lVert
B(\theta^{\star})\rVert\sum_{i=0}^{t-1}q_{1}(t)e_{t-i-1})+3\sigma_{t}$
$\displaystyle\leq(\bar{Q}+\bar{R}C_{1})\lVert
B(\theta^{\star})\rVert\sum_{t=0}^{T-1}e_{t}+3\sigma_{t}$
$\displaystyle\leq(\bar{Q}+\bar{R}C_{1})\lVert
B(\theta^{\star})\rVert\sum_{t=0}^{T-1}q_{2}(0)\lVert\theta_{t}-\theta^{\star}\rVert+3\sigma_{t}$
$\displaystyle\leq\bar{C}\sum_{t=0}^{T-1}\epsilon_{t}+3\sigma_{t}$
$\displaystyle\leq\bar{C}\sqrt{c_{3}}\sum_{t=0}^{T-1}\log(t/\delta)^{1/2}t^{-(1-\alpha)/2}+3d_{x}^{1/4}\sigma\sum_{t=0}^{T-1}t^{-\alpha/2}$
$\displaystyle\leq\frac{2\bar{C}\sqrt{c_{3}}}{\alpha+1}\log(T/\delta)^{1/2}T^{(\alpha+1)/2}+\frac{6d_{x}^{1/4}}{\alpha+1}\sigma
T^{(\alpha+1)/2},$

with $\bar{C}=(\bar{Q}+\bar{R}C_{1})\lVert B(\theta^{\star})\rVert C_{1}$.

Putting it together, we have under the event $\mathcal{G}$:

$\displaystyle R_{T}(\pi)_{\mathcal{G}}=$
$\displaystyle(R_{T}(\pi)-R_{t^{\star}(\delta)}(\pi))_{\mathcal{G}}+R_{t^{\star}(\delta)}(\pi)_{\mathcal{G}}$
$\displaystyle\leq$
$\displaystyle\frac{2\bar{C}\sqrt{c_{3}}}{\alpha+1}\log(T/\delta)^{1/2}T^{(\alpha+1)/2}$
$\displaystyle+\frac{2d_{x}^{1/4}}{\alpha+1}\sigma
T^{(\alpha+1)/2}+\bar{C}_{2}\log(1/\delta)+\bar{C}_{1}.$

To obtain a bound on the expected regret, first note that

$\displaystyle{\mathbb{E}}[R_{T}(\pi)]=(1-\delta)R_{T}(\pi)_{\mathcal{G}}+\delta
R_{T}(\pi)_{\neg\mathcal{G}}$

where $R_{T}(\pi)_{\neg\mathcal{G}}$ is the regret when the event
$\mathcal{G}$ does not hold and can be taken to be linear in time with some
constant $c$. This follows again from the recursive feasibility of STT-MPC
(Theorem 3.4), which ensures that $x_{t}^{\pi}$ and $u_{t}^{\pi}$ are bounded
in the set $\mathcal{C}$. Letting $\delta=1/T^{2}$ leads to

$\displaystyle{\mathbb{E}}[R_{T}(\pi)]$
$\displaystyle=(1-\delta)R_{T}(\pi)_{\mathcal{G}}+\delta
R_{T}(\pi)_{\neg\mathcal{G}}$
$\displaystyle=R_{T}(\pi)_{\mathcal{G}}+\frac{1}{T^{2}}R_{T}(\pi)_{\mathcal{G}}+\frac{c}{T}$
$\displaystyle\lesssim\frac{2\sqrt{3}\bar{C}\sqrt{c_{3}}}{\alpha+1}\log(T)^{1/2}T^{(\alpha+1)/2}.$

Here, the notation $\lesssim$ hides the universal constant such that the
inequality holds. $\Box$

##  5 Numerical Example

We illustrate the performance of STT-MPC using the following second-order
linear system:

$A=\begin{bmatrix}0.6&0.2\\\ -0.1&0.4\end{bmatrix},\quad B=\begin{bmatrix}1\\\
0.6\end{bmatrix},\quad\sigma=0.01,$ (17)

The initial state is $x_{0}=(6,3)$, and we consider $\Theta_{0}$ to be a
$6$-dimensional hypercube centered on
$\theta_{0}=\begin{bmatrix}0.57&0.17&-0.12&0.42&0.95&0.65\end{bmatrix}$ with
side length $0.14$. Consequently, the resulting stabilizing feedback gain is
$K=\begin{bmatrix}-0.426&-0.290\end{bmatrix}$. We consider the following state
and input constraints: $[x_{t}]_{1}\geq-0.15,[x_{t}]_{2}\geq-1.1$ and
$u_{t}\leq 0.5$. We inject a persistent excitation signal with a standard
deviation of $\sigma_{t}=\sqrt{2}\sigma(t+1)^{-\alpha}$.

The matrix $T$ is computed according to the relation (5.98) in (Kouvaritakis &
Cannon, 2016), with $\lambda=0.999$. We consider $Q=I_{d_{x}}$, $R=I_{d_{u}}$,
and, for simplicity, we let the worst case noise realization be
$\bar{w}_{t}=\bar{w}_{0}$, for all $t\geq 1$. All the simulations were
performed in Python 3.9, using the CVXPY library (Diamond & Boyd, 2016) and
the MOSEK solver.

In Figure 1, we present the regret of STT-MPC versus the oracle tube-MPC
algorithm the cases where $\alpha$ is $0.01,0.5,$ and $0.99$. For all three
cases, the scaling is logarithmic and is thus over-estimated by the bound of
Theorem 4.1. Note the lower the value of $\alpha$, the slower the decay rate
of the excitation, which improves the transient estimation accuracy but
negatively impacts the performance of the controller. The result suggests that
the LSE converges very quickly to the true parameter (already before $t=5$)
even for high values of $\alpha$, and so the performance of the controller
(rather, the decay rate of the excitation signal) dominates the regret.

Overall the logarithmic scaling is surprising as it is better than the
$\sqrt{T}$ bound shown both theoretically and experimentally by (Jedra &
Proutiere, 2022) in the case of the LQR. We conjecture that the presence of
constraints has a benign property on the regret and that it should be possible
to tighten our upper bound to also scale as $\log(T)$.

Figure 1: Regret vs. time of STT-MPC averaged over 100 runs (the shaded area
corresponds to the standard error of the mean). Each curve corresponds to a
different decay rate of the persistent excitation signal $\zeta_{t}$.

##  6 Conclusions

We proposed STT-MPC which combines least-squares estimaton with a polytopic
tube-based MPC method to ensure robust constraint satisfaction while learning
the system dynamics. Persistent excitation is ensured by injecting a truncated
noise signal which decays at a rate $t^{-\alpha}$, with $\alpha>0$ controlling
the trade-off between (transient) estimation accuracy and controller
performance. Importantly, we asymptotically recover the performance of the
oracle tube-based MPC which has full knowledge of the dynamics.

We provided guarantees on the expected regret of our proposed algorithm by
leveraging performance bounds on the LSE, the exponential decay of sensitivity
property of the optimization problem, and the recursive feasibility of our
algorithm. We show theoretically that the expected regret of STT-MPC scales at
a rate of $T^{1/2+\epsilon}$ with $\epsilon\in(0,1)$ and also demonstrated its
performance via a numerical example.

The logarithmic rate demonstrated in simulation suggests that our bound can be
further tightened, and we will investigate this further in future work.

## References

  * Abbasi-Yadkori & Szepesvári (2011) Abbasi-Yadkori, Y. and Szepesvári, C.  Regret bounds for the adaptive control of linear quadratic systems.  In _Proceedings of the 24th Annual Conference on Learning Theory_ , pp. 1–26. JMLR Workshop and Conference Proceedings, 2011.
  * Åström & Wittenmark (1973) Åström, K. J. and Wittenmark, B.  On self tuning regulators.  _Automatica_ , 9(2):185–199, 1973.
  * Bitmead et al. (1990) Bitmead, R. R., Gevers, M., and Wertz, V.  _Adaptive optimal control the thinking man’s GPC_.  Prentice Hall, 1990.
  * Blanchini & Miani (2008) Blanchini, F. and Miani, S.  _Set-theoretic methods in control_ , volume 78.  Springer, 2008.
  * Diamond & Boyd (2016) Diamond, S. and Boyd, S.  Cvxpy: A python-embedded modeling language for convex optimization.  _The Journal of Machine Learning Research_ , 17(1):2909–2913, 2016.
  * Goel & Hassibi (2022) Goel, G. and Hassibi, B.  The power of linear controllers in lqr control.  In _2022 IEEE 61st Conference on Decision and Control (CDC)_ , pp. 6652–6657. IEEE, 2022.
  * Jedra & Proutiere (2022) Jedra, Y. and Proutiere, A.  Minimal expected regret in linear quadratic control.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 10234–10321. PMLR, 2022.
  * Kouvaritakis & Cannon (2016) Kouvaritakis, B. and Cannon, M.  Model predictive control.  _Switzerland: Springer International Publishing_ , 38, 2016.
  * Lai (1986) Lai, T. L.  Asymptotically efficient adaptive control in stochastic regression models.  _Advances in Applied Mathematics_ , 7(1):23–45, 1986.  ISSN 0196-8858.
  * Li et al. (2019) Li, Y., Chen, X., and Li, N.  Online optimal control with linear dynamics and predictions: Algorithms and regret analysis.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Lin et al. (2021) Lin, Y., Hu, Y., Shi, G., Sun, H., Qu, G., and Wierman, A.  Perturbation-based regret analysis of predictive control in linear time varying systems.  _Advances in Neural Information Processing Systems_ , 34:5174–5185, 2021.
  * Lin et al. (2022) Lin, Y., Hu, Y., Qu, G., Li, T., and Wierman, A.  Bounded-regret mpc via perturbation analysis: Prediction error, constraints, and nonlinearity.  _arXiv preprint arXiv:2210.12312_ , 2022.
  * Lorenzen et al. (2017) Lorenzen, M., Allgöwer, F., and Cannon, M.  Adaptive model predictive control with robust constraint satisfaction.  _IFAC-PapersOnLine_ , 50(1):3313–3318, 2017.
  * Lu & Cannon (2019) Lu, X. and Cannon, M.  Robust adaptive tube model predictive control.  In _2019 American Control Conference (ACC)_ , pp. 3695–3701. IEEE, 2019.
  * Lu et al. (2021) Lu, X., Cannon, M., and Koksal-Rivet, D.  Robust adaptive model predictive control: Performance and parameter estimation.  _International Journal of Robust and Nonlinear Control_ , 31(18):8703–8724, 2021.
  * Mania et al. (2019) Mania, H., Tu, S., and Recht, B.  Certainty equivalence is efficient for linear quadratic control.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Mayne et al. (2000) Mayne, D. Q., Rawlings, J. B., Rao, C. V., and Scokaert, P. O.  Constrained model predictive control: Stability and optimality.  _Automatica_ , 36(6):789–814, 2000.
  * Mayne et al. (2005) Mayne, D. Q., Seron, M. M., and Raković, S.  Robust model predictive control of constrained linear systems with bounded disturbances.  _Automatica_ , 41(2):219–224, 2005.
  * Paulraj et al. (2010) Paulraj, S., Sumathi, P., et al.  A comparative study of redundant constraints identification methods in linear programming problems.  _Mathematical Problems in Engineering_ , 2010, 2010.
  * Recht (2019) Recht, B.  A tour of reinforcement learning: The view from continuous control.  _Annual Review of Control, Robotics, and Autonomous Systems_ , 2:253–279, 2019.
  * Scokaert & Rawlings (1998) Scokaert, P. O. and Rawlings, J. B.  Constrained linear quadratic regulation.  _IEEE Transactions on automatic control_ , 43(8):1163–1169, 1998.
  * Shin et al. (2022) Shin, S., Anitescu, M., and Zavala, V. M.  Exponential decay of sensitivity in graph-structured nonlinear programs.  _SIAM Journal on Optimization_ , 32(2):1156–1183, 2022.
  * Tranos et al. (2022) Tranos, D., Russo, A., and Proutiere, A.  Self-tuning tube-based model predictive control.  _arXiv preprint arXiv:2210.00502_ , 2022.
  * Yu et al. (2020) Yu, C., Shi, G., Chung, S.-J., Yue, Y., and Wierman, A.  The power of predictions in online control.  _Advances in Neural Information Processing Systems_ , 33:1994–2004, 2020.
  * Zhang et al. (2021) Zhang, R., Li, Y., and Li, N.  On the regret analysis of online lqr control with predictions.  In _2021 American Control Conference (ACC)_ , pp. 697–703. IEEE, 2021.