# Regret Optimal Control for Uncertain Stochastic Systems

Andrea Martin, Luca Furieri, Florian Dörfler, John Lygeros, and Giancarlo
Ferrari-Trecate A. Martin, L. Furieri, and G. Ferrari-Trecate are with the
Institute of Mechanical Engineering, EPFL, Switzerland. E-mail addresses:
{andrea.martin, luca.furieri<EMAIL_ADDRESS>Dörfler and
J. Lygeros are with the Department of Information Technology and Electrical
Engineering, ETH Zürich, Switzerland. E-mail addresses: {dorfler,
<EMAIL_ADDRESS>supported by the Swiss National Science Foundation
(SNSF) under the NCCR Automation (grant agreement 51NF40_80545). Luca Furieri
is also grateful to the SNSF for the Ambizione grant PZ00P2_208951.

###### Abstract

We consider control of uncertain linear time-varying stochastic systems from
the perspective of regret minimization. Specifically, we focus on the problem
of designing a feedback controller that minimizes the loss relative to a
clairvoyant optimal policy that has foreknowledge of both the system dynamics
and the exogenous disturbances. In this competitive framework, establishing
robustness guarantees proves challenging as, differently from the case where
the model is known, the clairvoyant optimal policy is not only inapplicable,
but also impossible to compute without knowledge of the system parameters. To
address this challenge, we embrace a scenario optimization approach, and we
propose minimizing regret robustly over a finite set of randomly sampled
system parameters. We prove that this policy optimization problem can be
solved through semidefinite programming, and that the corresponding solution
retains strong probabilistic out-of-sample regret guarantees in face of the
uncertain dynamics. Our method naturally extends to include satisfaction of
safety constraints with high probability. We validate our theoretical results
and showcase the potential of our approach by means of numerical simulations.

##  I Introduction

Inspired by online optimization and learning methods, control of dynamical
system has recently been studied through the lens of regret minimization [1].
This emerging paradigm aims at designing efficient control laws that minimize
the worst-case loss relative to an optimal policy in hindsight. Algorithms
with provable regret certificates hence offer attractive performance
guarantees that – in contrast with the stochastic and worst-case assumptions
typical of $\mathcal{H}_{2}$ and $\mathcal{H}_{\infty}$ controllers [2] – hold
independently of how disturbances are generated.

Most prior work in this area employs gradient methods to deal with
adversarially chosen cost functions and perturbations, and shows that the
resulting control law achieves sublinear regret against expressive policy
classes [3, 4, 1]. A parallel line of research, initiated by [5, 6, 7],
studies the problem of competing against the optimal control actions selected
by a clairvoyant (noncausal) policy, without imposing any parametric structure
on this benchmark policy.

For the case of known cost functions, the formulation of [5, 6, 7] has
received increasing interest thanks to: optimality of the clairvoyant
benchmark policy, possibility of computing the regret-minimizing controller,
and remarkable performance reported in several applications, including
longitudinal motion control of a helicopter and control of a wind energy
conversion system [8]. In particular, among recent contributions, [9] and [10]
proposed an efficient optimization-based synthesis framework to incorporate
safety constraints, [11] established recursive feasibility and stability
guarantees for receding horizon regret optimal control, [12] and [13]
considered partially-observed systems, [14] and [8] investigated the closely
related metric of competitive ratio, [7] and [15] considered state estimation
problems, and [16] studied connections with imitation learning.

Despite these advances, an important open challenge is how to track the
performance of the clairvoyant optimal policy without knowledge of the
underlying dynamics. In fact, as the systems under control become increasingly
complex, assuming availability of precise mathematical models appears more and
more unrealistic. Nevertheless, to the best of our knowledge, only [17]
approached this problem, showing that several iterative control algorithms
that combine system identification with gradient descent methods, e.g., [3,
4], also achieve, asymptotically, near-optimal competitive ratio relative to
the clairvoyant optimal policy. However, this result only holds asymptotically
and does not allow synthesizing control policies that, given a set of
admissible plants, guarantee that the regret relative to the clairvoyant
optimal policy is minimized robustly.

Towards addressing these issues, in this paper we present a solution to the
robust regret minimization problem based on scenario optimization [18, 19,
20], which is applicable to uncertain stochastic linear time-varying systems
affected by a priori unknown but measurable disturbance processes.111These
include but are not limited to the class of linear parameter-varying systems –
a middle ground between linear and nonlinear dynamics [21]. A key challenge
lies in handling the different impacts that parametric uncertainty has on the
closed-loop behavior achieved by the clairvoyant benchmark policy, on the one
hand, and by the causal controller to be designed on the other. In fact,
simultaneously accounting for these effects has not yet been achieved
following the analysis methods used in [22, 23, 24] to derive suboptimality
and sample complexity bounds for classical linear quadratic control problems.
As further evidence of the complexity arising in a competitive setting due to
parametric uncertainty, we note that the concurrent work [25], which also
pursues similar robust regret minimization objectives, considers a suboptimal
benchmark defined with respect to some nominal dynamics. Due to model
mismatch, however, in the case of [25] it remains unclear whether this nominal
clairvoyant policy does encode the ideal behavior that regret optimal
controllers strive to mimic, or if the proposed suboptimal benchmark can be
outperformed even by simple causal policies.

For a wide range of control applications, including robotics, building energy
management, and power grids [26], designing a single state feedback policy
that attains robust performance across all admissible system dynamics can
prove overly conservative. Instead, it is beneficial to optimize for a unique
closed-loop behavior – while allowing the state feedback law that achieves it
to vary – leveraging a posteriori measurements of exogenous perturbations such
as external forces, solar radiation, and electricity demands for control
implementation.

Motivated as above, we show how convex optimization and sampling techniques
can be used to synthesize a disturbance feedback robust control policy with
provable regret guarantees in spite of the uncertain dynamics. In particular,
building upon [18, 19, 20], we propose constructing a scenario problem by
appropriately sampling over the space of uncertain parameters. We prove that
the policy that minimizes regret robustly over the considered scenarios can be
computed via semidefinite programming, and that this solution exhibits
generalization capabilities – in the sense that the resulting regret bound
holds true for all but a small fraction of uncertainty realizations whose
probability is no larger than a prespecified tolerance level. Our approach
naturally extends to include satisfaction of safety constraints with high
probability. The advantages of our probabilistic design method are twofold.
First, contrary to worst-case solutions, which are known to be computationally
hard to evaluate [27], and coherently with the theory of scenario
optimization, our approach uses a finite number of randomly sampled
uncertainty realizations only, and thus calls for the solution of a convex
program – albeit with a size that increases with the number of considered
scenarios. Second, as opposed to probabilistic solutions based on scenario
optimization with classical $\mathcal{H}_{\infty}$ objectives, our method
leverages the cost of the optimal policy in hindsight to yield performance
guarantees that are tailored to the specific uncertainty and disturbance
realizations. In turn, as we validate by means of numerical simulations, this
often allows us to reduce conservatism of $\mathcal{H}_{\infty}$ methods by
establishing tighter upper bounds on the realized cost – which in turn
translate into improved closed-loop performance across all system dynamics for
several disturbance profiles of practical relevance.

##  II Problem Statement and Preliminaries

###  II-A Dynamics, control objective, and constraints

We consider an uncertain discrete-time linear time-varying dynamical system
described by the state-space equation

$x_{t+1}=A_{t}(\theta_{t})x_{t}+B_{t}(\theta_{t})u_{t}+E_{t}(\theta_{t})w_{t}\,,$
(1)

where $x_{t}\in\mathbb{R}^{n}$, $u_{t}\in\mathbb{R}^{m}$,
$\theta_{t}\in\mathbb{R}^{d}$ and $w_{t}\in\mathbb{R}^{p}$ are the system
state, the control input, a vector of uncertain parameters that characterize
the family of admissible plants, and a measurable disturbance process,
respectively. We focus on optimizing the closed-loop behavior of this
uncertain system over a finite-time planning horizon of length
$T\in\mathbb{N}$, and let

$\displaystyle\bm{x}$
$\displaystyle=(x_{0},x_{1},\dots,x_{T-1})\,,~{}~{}\bm{u}$
$\displaystyle=(u_{0},u_{1},\dots,u_{T-1})\,,$ $\displaystyle\bm{w}$
$\displaystyle=(x_{0},w_{0},\dots,w_{T-2})\,,~{}~{}\bm{\theta}$
$\displaystyle=(\theta_{0},\theta_{1},\dots,\theta_{T-1})\,,$

for compactness. On the one hand, we do not make any assumptions about the
statistical properties of the exogenous disturbance process $\bm{w}$, that can
also be adversarially selected.222For simplicity, we embed $x_{0}$ in $\bm{w}$
and assume it is adversarially selected. On the other hand, we assume that
$\bm{\theta}$ is drawn according to a probability distribution
$\mathbb{P}_{\bm{\theta}}$ with a possibly unknown and unbounded support set
$\bm{\Theta}$. This probability measure may reflect a priori knowledge about
the actual likelihood of each realization of the system parameters, or may
simply encode the relative importance that we attribute to each uncertainty
instance. In particular, we do not require $\mathbb{P}_{\bm{\theta}}$ to be
known explicitly, but rely on a set
$\mathcal{D}=\\{\bm{\theta}^{1},\dots,\bm{\theta}^{N}\\}$ of $N\in\mathbb{N}$
independent samples only.333Note that the individual parameter realizations
$\theta_{0}^{k},\dots,\theta_{T-1}^{k}$ inside a training sample
$\bm{\theta}^{k}\in\mathcal{D}$ need not be independent and identically
distributed. Finally, we assume that the matrices $E_{t}(\theta_{t})$ are full
column rank for all $t\in\mathbb{I}_{T}=\\{0,\dots,T-1\\}$ and for all
$\theta_{t}$ such that $\bm{\theta}\in\bm{\Theta}$.444For instance, this
assumption is trivially satisfied if the matrices $E_{t}(\theta_{t})$ are
identities or triangular with non-zero diagonal entries for all
$\bm{\theta}\in\bm{\Theta}$.

###### Remark 1

Often times, the probability distribution $\mathbb{P}_{\bm{\theta}}$ is
unknown, yet uncertainty samples are directly made available to the policy
designer as observations. For instance, this is the case when the realizations
$\bm{\theta}^{k}\in\mathcal{D}$ correspond to a series of system
identification experiments, see, e.g., [18] and [28], or to the values of the
physical parameters of a batch of components, which scatter around their
nominal value due to tolerance levels and variability in the production
process.

###### Remark 2

As previously discussed, measurable disturbance processes arise in several
control applications and include, e.g., reference changes, friction, and
external forces in robotics, and heat and humidity loads in heating,
ventilating and air conditioning systems. Besides, our formulation encompasses
the broad class of linear-parameter-varying systems. In fact, if $\theta_{t}$
denotes an a priori uncertain but measurable scheduling parameter, then past
disturbance realizations can always be reconstructed by
$w_{t}=E_{t}(\theta_{t})^{\dagger}(x_{t+1}-A_{t}(\theta_{t})x_{t}-B_{t}(\theta_{t})u_{t})$,
where $E_{t}(\theta_{t})^{\dagger}$ is the Moore-Penrose inverse of
$E_{t}(\theta_{t})$. Differently from most literature on linear-parameter-
varying systems, however, we allow generic nonlinear dependence with respect
to $\theta_{t}$ of the system matrices $A_{t}(\theta_{t})$,
$B_{t}(\theta_{t})$, and $E_{t}(\theta_{t})$.

Motivated by the regret optimal control framework of [5, 6, 7], we consider
the problem of designing a causal decision policy
$\bm{\pi}=(\pi_{0},\dots,\pi_{T-1})$, with
$u_{t}=\pi_{t}(x_{0},\dots,x_{t},w_{0},\dots,w_{t-1})$, that closely tracks
the performance of an ideal clairvoyant policy
$\bm{\psi}=(\psi_{0},\dots,\psi_{T-1})$. Importantly, we allow the noncausal
benchmark policy $\bm{\psi}$ to select the control actions with foreknowledge
of both the exogenous disturbance $\bm{w}$ and the system dynamics
$\bm{\theta}$, i.e.,
$u_{t}=\psi_{t}(x_{0},\dots,x_{t},w_{0},\dots,w_{T-2},\theta_{0},\dots,\theta_{T-1})$.
More specifically, for any fixed $\bm{w}$ and $\bm{\theta}$, let

$J(\bm{\pi},\bm{w},\bm{\theta})=\bm{x}^{\top}\bm{Q}\bm{x}+\bm{u}^{\top}\bm{R}\bm{u}\,,$
(2)

with $\bm{Q}\succeq 0$ and $\bm{R}\succ 0$, denote the control cost incurred
by playing the policy $\bm{\pi}$, and define the per-instance regret of
$\bm{\pi}$ relative to $\bm{\psi}$ as:

$\mathtt{R}(\bm{\pi},\bm{\psi},\bm{w},\bm{\theta})=J(\bm{\pi},\bm{w},\bm{\theta})-J(\bm{\psi},\bm{w},\bm{\theta})\,.$
(3)

Building upon ideas proposed in [5, 6, 7] for the case where the system
dynamics (1) are perfectly known, we then formulate the robust regret
minimization problem as follows:

$\mathtt{R}^{\star}(\bm{\psi})=\inf_{\bm{\pi}}~{}\sup_{\bm{\theta}\in\bm{\Theta}}~{}\max_{\left\lVert\bm{w}\right\rVert_{2}\leq
1}~{}\mathtt{R}(\bm{\pi},\bm{\psi},\bm{w},\bm{\theta})\,.$ (4)

A solution $\bm{\pi}^{\star}$ to (4), if any, guarantees that its cost is
always at most $\mathtt{R}^{\star}(\bm{\psi})$ higher than that of the ideal,
yet inapplicable, benchmark policy $\bm{\psi}(\bm{w},\bm{\theta})$ that
minimizes (2) – no matter how $\bm{w}$ is generated and which $\bm{\theta}$
realize.

As modern engineering systems often feature safety-critical components, we
include in the synthesis problem a robust constraint satisfaction requirement.
In particular, we define a polytopic safe set in the space of state and input
trajectories as follows:

${\mathcal{S}(\bm{\theta})=\\{(\bm{x},\bm{u}):\bm{H}_{x}(\bm{\theta})\bm{x}+\bm{H}_{u}(\bm{\theta})\bm{u}\leq\bm{h}(\bm{\theta})\\}\,.}$
(5)

Then, we consider the objective of solving (4) while ensuring that
$(\bm{x},\bm{u})\in\mathcal{S}(\bm{\theta})$ robustly for all
$\bm{\theta}\in\bm{\Theta}$ and all $\bm{w}$ belonging to a compact
disturbance set $\mathcal{W}(\bm{\theta})$ defined as

$\mathcal{W}(\bm{\theta})=\\{\bm{w}:\bm{w}=\bm{H}_{w}(\bm{\theta})\bm{d}\,,~{}\left\lVert\bm{d}\right\rVert_{2}\leq
1\\}\,.$ (6)

In particular, we note that (6) reduces to the bounded energy constraint
$\left\lVert\bm{w}\right\rVert_{2}\leq 1$ used in (4) if
$\bm{H}_{w}(\bm{\theta})=\bm{I}$. Other values of $\bm{H}_{w}(\bm{\theta})$
instead allow considering different assumptions on $\bm{w}$ for what concerns
safety and performance, providing extra design flexibility that one can
exploit to strike a balance between these two critical – yet often competing –
aspects.

###  II-B Linear disturbance feedback policy

In general, it is well-known that optimizing over the function space of
feedback policies is computationally intractable. Therefore, as common in the
control literature [29, 30], throughout this paper we restrict our attention
to linear disturbance feedback policies of the form
$\bm{u}=\bm{\Phi}_{u}\bm{w}$, with $\bm{\Phi}_{u}$ lower block-triangular to
enforce causality.666By carefully adapting the convex reformulation of
Proposition 1 below, our results can be extended to the case of affine
policies $\bm{u}=\bm{\Phi}_{u}\bm{w}+\bm{v}$ through the definition of an
augmented disturbance vector $\bm{\delta}=(\bm{w},1)$. We note that linear
policies enable attaining minimum regret against the optimal sequence of
control actions in hindsight if the true system dynamics are known and the
safety constraints are not active [5, 6, 7]. Moreover, as we will show in the
next section, unlike linear state feedback policies, this choice allows us to
approximate the intractable minimization of (4) subject to the dynamics (1)
and the constraints (5) with a convex optimization problem.

Let us define through diagonal concatenation of matrices the operators
$\bm{A}(\bm{\theta})=\operatorname{blkdiag}(A_{0}(\theta_{0}),\dots,A_{T-1}(\theta_{T-1}))$,
$\bm{B}(\bm{\theta})=\operatorname{blkdiag}(B_{0}(\theta_{0}),\dots,B_{T-1}(\theta_{T-1}))$,
and
$\bm{E}(\bm{\theta})=\operatorname{blkdiag}(I_{n},E_{0}(\theta_{0}),\dots,E_{T-2}(\theta_{T-2}))$.
With this notation in place, we observe that the closed-loop state trajectory
under the feedback law $\bm{u}=\bm{\Phi}_{u}\bm{w}$ can be expressed as a
linear function of $\bm{w}$ as per:

$\displaystyle\bm{x}$
$\displaystyle=\bm{Z}\bm{A}(\bm{\theta})\bm{x}+\bm{Z}\bm{B}(\bm{\theta})\bm{u}+\bm{E}(\bm{\theta})\bm{w}\,,$
(7)
$\displaystyle=(\bm{I}-\bm{Z}\bm{A}(\bm{\theta}))^{-1}(\bm{Z}\bm{B}(\bm{\theta})\bm{\Phi}_{u}+\bm{E}(\bm{\theta}))\bm{w}:=\bm{\Phi}_{x}(\bm{\theta})\bm{w}\,,$

where $\bm{Z}$ is the block-downshift operator, namely, a matrix with identity
matrices along its first block sub-diagonal and zeros elsewhere.

###  II-C On the choice of the clairvoyant benchmark policy

We conclude our problem formulation by commenting on the choice of the
clairvoyant benchmark policy $\bm{\psi}$. Extending ideas from [5, 6, 7] to
the case where the model is uncertain, a meaningful objective is that of
competing against the best sequence of control actions in hindsight, without
imposing any structure on $\bm{\psi}$. In this case, it can be shown by
adapting the derivations of [2, 9] that:

$\bm{\psi}(\bm{w},\bm{\theta})=-(\bm{R}+\bm{F}(\bm{\theta})^{\top}\bm{Q}\bm{F}(\bm{\theta}))^{-1}\bm{F}(\bm{\theta})^{\top}\bm{Q}\bm{G}(\bm{\theta})\bm{w}\,,$
(8)

where
$\bm{F}(\bm{\theta})=(\bm{I}-\bm{Z}\bm{A}(\bm{\theta}))^{-1}\bm{Z}\bm{B}(\bm{\theta})$
and
$\bm{G}(\bm{\theta})=(\bm{I}-\bm{Z}\bm{A}(\bm{\theta}))^{-1}\bm{E}(\bm{\theta})$
are the causal response operators that encode the uncertain dynamics (1) as
$\bm{x}=\bm{F}(\bm{\theta})\bm{u}+\bm{G}(\bm{\theta})\bm{w}$. Differently from
the model-based setting considered in [5, 6, 7], however, the (nonlinear)
dependence of $\bm{\psi}$ on the uncertain system dynamics $\bm{\theta}$ makes
it impossible to compute the actual benchmark policy – and hence also the
policy that minimizes regret against it. To get around this problem without
sacrificing the instance-wise optimality of $\bm{\psi}$ – as would result, for
instance, by constructing a benchmark policy that achieves robust performance
across all $\bm{\theta}\in\bm{\Theta}$ – in the next section we present a
randomized approach based on the scenario optimization framework [18, 19, 20].

###### Remark 3

Alternatively, leveraging the foreknowledge of all elements in $\bm{\theta}$
and using results in Corollary 4 of [9], one may define more complex linear
control benchmarks that, e.g., further comply with safety constraints (5) and
(6).

##  III Main Results

In this section, we show how a causal control policy with probabilistic
certificates of regret and safety can be efficiently computed in spite of the
uncertain dynamics. To do so, we first construct a scenario approximation of
the robust regret minimization problem in (4) by restricting our focus to a
finite number of uncertainty instances only. Then, inspired by [9], we prove
that the policy that safely minimizes regret over the considered scenarios can
be expressed as the solution of a semidefinite optimization problem. Finally,
leveraging results from the theory of uncertain convex programs [18, 19, 20],
we derive strong guarantees on the probability of both out-of-sample regret
bound and safety constraint violation. For ease of presentation, we defer all
proofs to the appendix.

In what follows and by inspection of (7) and (8), we let
$\bm{\Psi}_{u}(\bm{\theta})=-(\bm{R}+\bm{F}(\bm{\theta})^{\top}\bm{Q}\bm{F}(\bm{\theta}))^{-1}\bm{F}(\bm{\theta})^{\top}\bm{Q}\bm{G}(\bm{\theta})$
and
$\bm{\Psi}_{x}(\bm{\theta})=\bm{F}(\bm{\theta})\bm{\Psi}_{u}(\bm{\theta})+\bm{G}(\bm{\theta})$
denote the closed-loop system responses that map $\bm{w}$ to the control
actions selected by $\bm{\psi}$ and to the corresponding state trajectory,
respectively. Further, with slight abuse of notation, we will often use
$\bm{\Phi}_{u}$ and $\bm{\Psi}_{u}$ instead of $\bm{\pi}$ and $\bm{\psi}$,
respectively. We start by introducing the following epigraphic form of the
robust safe regret minimization problem:

$\displaystyle~{}\inf_{\bm{\Phi}_{u},\gamma}~{}\gamma$ (9a)
$\displaystyle\operatorname*{subject~{}to}~{}\bm{\Phi}_{x}(\bm{\theta})=\bm{F}(\bm{\theta})\bm{\Phi}_{u}+\bm{G}(\bm{\theta})\,,$
(9b)
$\displaystyle\quad\max_{\bm{w}\in\mathcal{W}(\bm{\theta})}~{}\bm{H}_{x}(\bm{\theta})\bm{\Phi}_{x}(\bm{\theta})\bm{w}+\bm{H}_{u}(\bm{\theta})\bm{\Phi}_{u}\bm{w}\leq\bm{h}(\bm{\theta})\,,$
(9c) $\displaystyle\quad\max_{\left\lVert\bm{w}\right\rVert_{2}\leq
1}~{}\mathtt{R}(\bm{\Phi}_{u},\bm{\Psi}_{u}(\bm{\theta}),\bm{w},\bm{\theta})\leq\gamma\,,~{}\forall\bm{\theta}\in\bm{\Theta}\,;$
(9d)

we denote the optimal value of (9) by
$\bar{\mathtt{R}}^{\star}(\bm{\Psi}_{u}(\bm{\theta}))$. Despite we narrowed
attention to linear disturbance feedback policies, (9) remains intractable if
$\bm{\Theta}$ has infinite cardinality. Besides, strong duality results do not
apply in a straightforward way as $\bm{\Theta}$ is not assumed to be
connected, let alone convex.

Motivated by the scenario optimization framework [18, 19, 20], we therefore
propose replacing the maximization over $\bm{\Theta}$ with a maximization over
the finite set $\mathcal{D}=\\{\bm{\theta}^{1},\dots,\bm{\theta}^{N}\\}$ of
randomly sampled uncertainty realizations only. Proceeding in this way, we
approximate (9) with its scenario counterpart, that is:

$\displaystyle~{}\min_{\bm{\Phi}_{u},\gamma}~{}\gamma$ (10a)
$\displaystyle\operatorname*{subject~{}to}~{}\bm{\Phi}_{x}(\bm{\theta}^{k})=\bm{F}(\bm{\theta}^{k})\bm{\Phi}_{u}+\bm{G}(\bm{\theta}^{k})\,,$
(10b)
$\displaystyle\quad\max_{\bm{w}\in\mathcal{W}(\bm{\theta}^{k})}\bm{H}_{x}^{k}\bm{\Phi}_{x}(\bm{\theta}^{k})\bm{w}+\bm{H}_{u}^{k}\bm{\Phi}_{u}\bm{w}\leq\bm{h}^{k}\,,$
(10c) $\displaystyle\quad\max_{\left\lVert\bm{w}\right\rVert_{2}\leq
1}~{}\mathtt{R}(\bm{\Phi}_{u},\bm{\Psi}_{u}(\bm{\theta}^{k}),\bm{w},\bm{\theta}^{k})\leq\gamma\,,~{}\forall\bm{\theta}^{k}\in\mathcal{D}\,,$
(10d)

with $\bm{H}_{x}^{k}=\bm{H}_{x}(\bm{\theta}^{k})$,
$\bm{H}_{u}^{k}=\bm{H}_{u}(\bm{\theta}^{k})$, and
$\bm{h}^{k}=\bm{h}(\bm{\theta}^{k})$ for brevity. In particular, note that the
infimum in (10a) is attained since only a finite number of uncertainty
realizations $\bm{\theta}^{k}\in\mathcal{D}$ are considered, and since, for
every $\bm{\theta}^{k}$, $\bm{R}\succ 0$ implies that the regret (3) is
radially unbounded with respect to $\bm{\Phi}_{u}$. Building upon the
reformulations proposed in [9, 10] for the case of known system dynamics, the
next proposition shows that (10) can be solved by means of standard convex
optimization techniques.

###### Proposition 1

The scenario optimization problem (10) is equivalent to the following
semidefinite program:

$\displaystyle~{}\min_{\bm{\Phi}_{u},\gamma}~{}\gamma$ (11a)
$\displaystyle\operatorname*{subject~{}to}~{}\eqref{eq:achievability_constraint_unrolled_k}\,,~{}\forall\bm{\theta}^{k}\in\mathcal{D}\,,~{}\forall
i\in\\{1,\dots,S\\}\,,$
$\displaystyle\quad\left\lVert(\bm{H}_{x}^{k}\bm{\Phi}_{x}(\bm{\theta}^{k})+\bm{H}_{u}^{k}\bm{\Phi}_{u})_{i}\bm{H}_{w}^{k}(\bm{\theta})\right\rVert_{2}\leq\bm{h}^{k}\,,$
(11b)
$\displaystyle\quad\begin{bmatrix}\bm{I}&\begin{bmatrix}\bm{Q}^{\frac{1}{2}}\bm{\Phi}_{x}(\bm{\theta}^{k})\\\
\bm{R}^{\frac{1}{2}}\bm{\Phi}_{u}\end{bmatrix}\\\
\star&\gamma\bm{I}+\begin{bmatrix}\bm{Q}^{\frac{1}{2}}\bm{\Psi}_{x}(\bm{\theta}^{k})\\\
\bm{R}^{\frac{1}{2}}\bm{\Psi}_{u}(\bm{\theta}^{k})\end{bmatrix}^{\top}\begin{bmatrix}\bm{Q}^{\frac{1}{2}}\bm{\Psi}_{x}(\bm{\theta}^{k})\\\
\bm{R}^{\frac{1}{2}}\bm{\Psi}_{u}(\bm{\theta}^{k})\end{bmatrix}\end{bmatrix}\succeq
0\,,$ (11c)

where $\bm{H}_{w}^{k}=\bm{H}_{w}(\bm{\theta}^{k})$, $S$ is the number of
constraints in (5), and $\star$ denotes entries that can be inferred from
symmetry.

We remark that, for each $\bm{\theta}^{k}\in\mathcal{D}$, the operators
$\bm{\Psi}_{x}(\bm{\theta}^{k})$ and $\bm{\Psi}_{u}(\bm{\theta}^{k})$ in (11c)
are the noncausal system responses associated with a benchmark policy that is
optimal for the specific realization $\bm{\theta}^{k}$ of the uncertain system
parameters. For each $\bm{\theta}^{k}\in\mathcal{D}$, enforcing (11c) hence
requires to first evaluate the corresponding optimal closed-loop behavior in
hindsight using (8). Establishing regret guarantees relative to the
clairvoyant optimal policy $\bm{\Psi}_{u}(\bm{\theta}^{k})$, which is
impossible to compute without knowledge of $\bm{\theta}^{k}$, constitutes our
main motivation towards adopting sampling techniques in a competitive setting,
shedding light on an interesting application of scenario optimization beyond
those in stochastic model predictive control [31, 32].

###### Remark 4

As the control horizon $T$ and the number of uncertainty samples in
$\mathcal{D}$ increase, solving (11) via semidefinite programming may
represent a major computational bottleneck. Indeed, (11) features
$\delta=1+\frac{m(T-1)(2n+p(T-2))}{2}$ optimization variables and $N$ linear
matrix inequality constraints of the form (11c). As common in the predictive
control literature [33, 34, 35] and inspired by time-invariant infinite
horizon formulations, the computational burden can be alleviated by imposing a
Toeplitz block structure on $\bm{\Phi}_{u}$, effectively reducing the number
of optimization variables to $\hat{\delta}=1+m(n+p(T-2))$ – a linearly growing
function of $T$. We will return to this point in Section IV, where we
numerically show that this additional structure can substantially reduce the
computational time, at the price of an only slight increase in
conservativeness in our regret bound. We also refer the interested reader to
[36, 37] for state-of-the-art techniques that leverage diagonal dominance and
chordal sparsity to further improve scalability.

Let $\bm{\Phi}_{u}^{\star}(\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D})$ and
$\bar{\mathtt{R}}_{N}^{\star}(\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D})$ denote
the optimal policy and the optimal value of (10), respectively.777In the
interest of readability, in the following, we omit function arguments when
clear from the context. Since only a finite subset of the constraints of (9)
are considered in (10), we have that
$\bar{\mathtt{R}}_{N}^{\star}\leq\bar{\mathtt{R}}^{\star}$, that is,
$\bar{\mathtt{R}}_{N}^{\star}$ is an optimistic lower bound on the true
minimax regret $\bar{\mathtt{R}}^{\star}$. Conversely, thanks to Proposition 1
and exploiting key results in scenario optimization, we now show that the
solution of (10) is approximately feasible for (9) – in the sense that the
measure of the set of original constraints that it violates rapidly approaches
zero as $N$ increases. Before formalizing this generalization property in the
theorem below, we observe that multiple optimal policies for (11) may exist,
since the function $\lambda_{\max}(\cdot)$ is not strongly convex. In this
case, uniqueness of
$\bm{\Phi}_{u}^{\star}(\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D})$ can be
enforced by designing a convex tie-break rule, e.g., a lexicographic criterion
[38]. Conversely, if the safety constraints (10c) are overly restrictive, the
scenario problem (11) may become infeasible; if this were the case, however,
the original problem (9) would also certainly be infeasible, and one would
need to consider broader classes of policies, or to relax the safety
requirements, e.g., by introducing slack variables in (10c).

###### Theorem 1

Fix any violation and confidence levels, say $\epsilon$ and $\beta$, in the
open interval $(0,1)$, and let $\delta$ and $\mathbb{P}_{\bm{\theta}}^{N}$
denote the number of optimization variables in (10) and the $N$-fold product
distribution
$\mathbb{P}_{\bm{\theta}}\times\dots\times\mathbb{P}_{\bm{\theta}}$ with $N$
terms, respectively. If the scenario optimization problem (10) is feasible and
$N>\delta$ satisfies
$\sum_{j=0}^{\delta-1}\binom{N}{j}\epsilon^{j}(1-\epsilon)^{N-j}\leq\beta$,
then, with probability of at least $1-\beta$ given a dataset
$\mathcal{D}\sim\mathbb{P}_{\bm{\theta}}^{N}$, it holds that:

$\displaystyle\mathbb{P}_{\bm{\theta}}\Big{(}\max_{\left\lVert\bm{w}\right\rVert_{2}\leq
1}~{}\mathtt{R}(\bm{\Phi}_{u}^{\star},\bm{\Psi}_{u}(\bm{\theta}),\bm{w},\bm{\theta})\leq\bar{\mathtt{R}}^{\star}_{N}\,,$
$\displaystyle\text{and
}(\bm{x},\bm{u})\in\mathcal{S}(\bm{\theta})\,,~{}\forall\bm{w}\in\mathcal{W}({\bm{\theta}})$
$\displaystyle\Big{)}\geq 1-\epsilon\,.$ (12)

Theorem 1 presents an explicit sample complexity bound that, given a priori
specified $\epsilon$ and $\beta$, ensures that the safety and regret
guarantees extend to all but at most a fraction $\epsilon$ of unseen dynamics
$\bm{\theta}\in\bm{\Theta}$ with probability $1-\beta$. As well-known in the
literature on scenario optimization, the minimum number of scenarios
$N(\epsilon,\beta)$ required to fulfill the conditions of Theorem 1 grows
linearly with $\epsilon^{-1}$, yet at most logarithmically with $\beta^{-1}$.
Hence, even if a very small $\beta$ is selected – so that (12) holds with
practical certainty – the number of scenarios to be sampled can remain
manageable, see also [31]. Further, we note that the condition on the number
$N$ of uncertainty samples given in Theorem 1 is tight for fully-supported
problems [19]; a simpler, albeit not tight, sufficient condition on $N$ is
given by [18]:

$N\geq 2\epsilon^{-1}(\delta+\operatorname{log}(\beta^{-1}))\,.$ (13)

###  III-A Comparison with worst-case oriented synthesis

Our main motivation towards embracing a scenario perspective is that
randomized approaches allow us to explicitly compute
$\bm{\psi}(\bm{w},\bm{\theta})$ by replacing the uncertain system dynamics
with their sampled counterparts. Regret bounds relative to the instance-wise
optimal benchmark $\bm{\psi}(\bm{w},\bm{\theta})$ are attractive, as they
yield upper bounds on the closed-loop cost that adapt to the realized dynamics
$\bm{\theta}$ and perturbation $\bm{w}$. To illustrate this point more
thoroughly, let us consider an alternative design based on a classical worst-
case $\mathcal{H}_{\infty}$ objective:

$\displaystyle\\{\bm{\Phi}_{u,\mathtt{H}}^{\star},~{}\bar{\mathtt{H}}^{\star}_{N}\\}=$
$\displaystyle~{}\operatorname*{arg\,min}_{\bm{\Phi}_{u},\gamma}~{}\gamma$
(14)
$\displaystyle\operatorname*{subject~{}to}~{}\eqref{eq:achievability_constraint_unrolled_k}\,,~{}\eqref{eq:epigraphic_scenario_safety_constraints}\,,$
$\displaystyle\quad\max_{\left\lVert\bm{w}\right\rVert_{2}\leq
1}~{}J(\bm{\Phi}_{u},\bm{w},\bm{\theta}^{k})\leq\gamma\,,~{}\forall\bm{\theta}^{k}\in\mathcal{D}\,.$

Leaving safety concerns aside to ease the discussion, the control policies
$\bm{\Phi}_{u}^{\star}$ and $\bm{\Phi}_{u,\mathtt{H}}^{\star}$ offer the
following probabilistic performance guarantees:

$\displaystyle
J(\bm{\Phi}_{u}^{\star},\bm{w},\bm{\theta})-J(\bm{\Psi}_{u}(\bm{\theta}),\bm{w},\bm{\theta})\leq\bar{\mathtt{R}}^{\star}_{N}\,,$
(15) $\displaystyle
J(\bm{\Phi}_{u,\mathtt{H}}^{\star},\bm{w},\bm{\theta})\leq\bar{\mathtt{H}}^{\star}_{N}\,,$
(16)

for any $\bm{\theta}\in\bm{\Theta}$ and any $\bm{w}$ with
$\left\lVert\bm{w}\right\rVert_{2}\leq 1$. In particular, we observe that,
while the $\mathcal{H}_{\infty}$ solution provides a single pessimistic upper
bound on the closed-loop cost as per (16), our regret optimal policy gives a
non-uniform certificate shaped by
$J(\bm{\Psi}_{u}(\bm{\theta}),\bm{w},\bm{\theta})$ as per (15). Moreover, our
upper bound on $J(\bm{\Phi}_{u}^{\star},\bm{w},\bm{\theta})$ is tighter than
that on $J(\bm{\Phi}_{u,\mathtt{H}}^{\star},\bm{w},\bm{\theta})$ whenever

$J(\bm{\Psi}_{u}(\bm{\theta}),\bm{w},\bm{\theta})\leq\bar{\mathtt{H}}^{\star}_{N}-\bar{\mathtt{R}}^{\star}_{N}\,.$
(17)

As we will numerically show in the next section, (17) not only holds
consistently over several classes of disturbances, but this tighter guarantee
in terms of upper bounds often translates into improved performance, that is,
$J(\bm{\Phi}_{u}^{\star},\bm{w},\bm{\theta})\leq
J(\bm{\Phi}_{u,\mathtt{H}}^{\star},\bm{w},\bm{\theta})$, no matter which
$\bm{\theta}$ realizes. In this sense, our regret minimization approach can
alleviate the conservatism introduced by (14).

###### Remark 5

Towards establishing sample complexity and suboptimality guarantees for
uncertain linear systems, most recent work [22, 23, 24] has focused on
synthesizing a single state-feedback control law $\bm{u}=\bm{K}\bm{x}$ that
attains robust performance across all admissible dynamics. These works analyze
the effect of parametric uncertainty on the achieved closed-loop cost, and
leverage the analytical expressions of classical $\mathcal{H}_{2}$ or
$\mathcal{H}_{\infty}$ objectives to derive tractable upper bounds by means of
simple norm inequalities (see, e.g., Section 3.2 in [22]). When a regret
objective is considered, however, this analysis becomes significantly more
intricate due to the presence of a clairvoyant benchmark policy. For this
reason, by assuming that the exogenous disturbance process is measurable, we
have proposed designing a policy $\bm{u}=\bm{\Phi}_{u}\bm{w}$ that achieves
minimum regret across a finite number of uncertainty samples as per (11). In
turn, this implies that the corresponding implementation as a state-feedback
control policy
$\bm{u}=\bm{\Phi}_{u}\bm{\Phi}_{x}(\bm{\theta})^{-1}\bm{x}:=\bm{K}(\bm{\theta})\bm{x}$
will depend on the particular realization of $\bm{\theta}$.

##  IV Numerical Results

In this section, we first validate numerically the probabilistic regret
guarantee we have established in Theorem 1, and we then show how this
guarantee allows improving the overall closed-loop performance in face of the
uncertain system dynamics. For our experiments, we consider a discrete-time
stochastic mass-spring-damper system described by the uncertain linear
dynamics:

$x_{t+1}=\begin{bmatrix}1&T_{s}\\\
-\frac{(k+\delta_{k})T_{s}}{m}&1-\frac{(c+\delta_{c})T_{s}}{m}\end{bmatrix}x_{t}+\begin{bmatrix}0\\\
\frac{T_{s}}{m}\end{bmatrix}u_{t}+w_{t}\,,$

with mass $m=$1\text{\,}\mathrm{kg}$$, nominal spring and damping constants
$k=$1\text{\,}\mathrm{N}\text{\,}{\mathrm{m}}^{-1}$$ and
$c=$1\text{\,}\mathrm{N}\text{\,}{\mathrm{m}}^{-1}\text{\,}\mathrm{s}$$,
respectively, and sampling time $T_{s}=$1\text{\,}\mathrm{s}$$. This simple
model is often used to describe the behavior of several physical systems,
including vibrating structures, suspension systems, and mechanical
oscillators; the uncertain parameters
$\theta=\begin{bmatrix}\delta_{k}&\delta_{c}\end{bmatrix}^{\top}$ can thus
model deviations from the nominal parameters arising in the mass production
process of these devices. We assume that $\theta$ is constant over the control
horizon $T=20$, and that it is uniformly distributed, i.e.,
$\delta_{k}\sim\mathcal{U}_{[-0.2,0.2]}$ and
$\delta_{c}\sim\mathcal{U}_{[-0.2,0.2]}$. We define the control cost (2) by
letting $\bm{Q}=\bm{I}_{20}\otimes\bm{I}_{2}$ and $\bm{R}=\bm{I}_{20}$, where
$\otimes$ denotes the Kronecker product. For simplicity and to focus on the
advantages brought about by regret minimization, we assume that no safety
constraints are imposed on the system.

To corroborate our main theoretical result in Theorem 1, we repeatedly solve
(11), each time considering a dataset $\mathcal{D}_{i}$ with an increasing
number $N_{i}$ of training scenarios. In particular, for each
$\bm{\theta}^{k}\in\mathcal{D}_{i}$, we use (8) to compute
$\bm{\Psi}_{u}(\bm{\theta}^{k})$ as the closed-loop map associated with the
unconstrained optimal policy in hindsight; according to (7), we obtain the
corresponding $\bm{\Psi}_{x}(\bm{\theta}^{k})$ by
$\bm{F}(\bm{\theta}^{k})\bm{\Psi}_{u}(\bm{\theta}^{k})+\bm{G}(\bm{\theta}^{k})$.
Then, given a set of $10000$ independently sampled uncertainty instances for
validation, we estimate the probability in (12) by recording how often the
optimal policy
$\bm{\Phi}^{\star}_{u}(\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D}_{i})$ fails to
comply with the associated regret bound
$\bar{\mathtt{R}}^{\star}_{N_{i}}(\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D}_{i})$.
To showcase the effect of time-invariant controller structure discussed in
Remark 4, we repeat these experiments while including in (11) the additional
constraint that the solution
$\widehat{\bm{\Phi}}_{u}^{\star}(\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D}_{i})$
has constant block diagonal terms. We denote the regret bound associated to
$\widehat{\bm{\Phi}}_{u}^{\star}(\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D}_{i})$
by
$\hat{\mathtt{R}}^{\star}_{N_{i}}(\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D}_{i})\geq\bar{\mathtt{R}}^{\star}_{N_{i}}(\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D}_{i})$.
In Figure 1, we plot the evolution of the empirical violation probabilities
$V(\bm{\Phi}_{u}^{\star},\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D}_{i}):=\bar{V}_{N}$
and
$V(\widehat{\bm{\Phi}}_{u}^{\star},\bm{\Psi}_{u}(\bm{\theta}),\mathcal{D}_{i}):=\widehat{V}_{N}$
associated with $\bm{\Phi}_{u}^{\star}$ and $\widehat{\bm{\Phi}}_{u}^{\star}$,
respectively, as a function of the dataset size.888The source code that
reproduces our numerical examples is available at
https://github.com/DecodEPFL/ScenarioSafeMinRegret. For completeness, we also
display the (non-tight) theoretical upper bounds on the violation probability
$\epsilon$ given by (13) for $\beta=0.1$.

Figure 1: Comparison between empirical regret violation probability and
theoretical upper bound as a function of the number of sampled scenarios.
Figure 2: Evolution of the probabilistic worst-case regret bounds (denoted by
$\bar{\mathtt{R}}^{\star}_{N}$ and $\hat{\mathtt{R}}^{\star}_{N}$ on the left
$y$-axis) and of the computation times (denoted by $\bar{\tau}_{N}$ and
$\hat{\tau}_{N}$ on the right $y$-axis) for the exact and approximate
solutions of (11), respectively, as a function of the number of considered
scenarios.

(a) Control cost $J(\bm{\Psi}_{u}(\bm{\theta}),\bm{w},\bm{\theta})$ incurred
by the clairvoyant optimal policy.  (b) Average percentage increase in the
cost incurred by $\bm{\pi}_{\mathtt{H}}$ relative to $\bm{\pi}_{\mathtt{R}}$.

Figure 3: Closed-loop comparison between $\bm{\pi}_{\mathtt{H}}$ and our
$\bm{\pi}_{\mathtt{R}}$: a priori performance guarantees and realized control
cost for different disturbance profiles and different realizations of the
uncertain system dynamics. Points in the green shaded area denote instances
where the proposed regret minimization approach yields an advantage in terms
of lower upper bound (Figure 3a) and realized performance (Figure 3b). We
refer to our source code for a precise definition of the considered
disturbance profiles.

In Figure 2, we compare the regret certificates $\bar{\mathtt{R}}^{\star}_{N}$
and $\hat{\mathtt{R}}^{\star}_{N}$ provided by the control policies
$\bm{\Phi}_{u}^{\star}$ and $\widehat{\bm{\Phi}}_{u}^{\star}$, respectively,
as well as the computation times $\bar{\tau}_{N}$ and $\hat{\tau}_{N}$
required to evaluate them via semidefinite optimization.999All optimization
problems have been solved using MOSEK [39] on a standard laptop computer with
a 2.3 GHz Intel Core i9 CPU. Besides validating our theoretical results, these
figures allow us to draw the following observations. First, the approximate
solution $\widehat{\bm{\Phi}}_{u}^{\star}$ with constant block diagonal terms
guarantees regret at most $9\%$ higher than $\bm{\Phi}_{u}^{\star}$ with high
probability, yet its evaluation requires a computation time $\hat{\tau}_{N}$
that is lower than $\bar{\tau}_{N}$ by an entire order of magnitude. Second,
consistently with the intuition that simpler models are less prone to overfit,
we observe that $\widehat{\bm{\Phi}}_{u}^{\star}$ achieves better
generalization than $\bm{\Phi}_{u}^{\star}$, as the out-of-sample empirical
violation probability $\widehat{V}_{N}$ is consistently smaller than
$\bar{V}_{N}$. Third, the quantities $\widehat{V}_{N}$ and
$\hat{\mathtt{R}}^{\star}_{N}$ rapidly converge to their corresponding limit
values as the number $N$ of sampled scenarios increases, suggesting that the
minimax solution to (9) could be practically approximated by sampling a
limited number of uncertainty instances only. Motivated by these
considerations and with the aim of further reducing the computational
complexity of our scheme, we plan to study the possible application of wait-
and-judge [38] and constraint removal [40] approaches in future work.

Next, to illustrate the potential of our synthesis method, we compare the
performance of the control policies $\bm{\pi}_{\mathtt{R}}$ and
$\bm{\pi}_{\mathtt{H}}$ computed solving (11) and (14), respectively, using
$N=5000$ random samples of $\delta_{k}$ and $\delta_{c}$. Then, for several
classes of disturbances $\bm{w}$ often encountered in practice, we evaluate
the realized control costs $J(\bm{\pi}_{\mathtt{R}},\bm{w},\bm{\theta})$,
$J(\bm{\pi}_{\mathtt{H}},\bm{w},\bm{\theta})$ and
$J(\bm{\psi},\bm{w},\bm{\theta})$ for $20$ different values of $\bm{\theta}$.
In Figure 3a, we plot $J(\bm{\Psi}_{u}(\bm{\theta}),\bm{w},\bm{\theta})$ and
compare it with $\bar{\mathtt{H}}^{\star}_{N}-\bar{\mathtt{R}}^{\star}_{N}$ to
verify, according to (17), when (15) yields tighter upper bounds than (16) on
the realized performance. Then, in Figure 3b, we display the percentage
increase in the realized cost due to using $\bm{\pi}_{\mathtt{H}}$ instead of
$\bm{\pi}_{\mathtt{R}}$, that is,101010For stochastic disturbances, results
are averaged over $10^{4}$ realizations.

$\Delta\bar{J}(\bm{w},\bm{\theta})=\frac{J(\bm{\pi}_{\mathtt{H}},\bm{w},\bm{\theta})-J(\bm{\pi}_{\mathtt{R}},\bm{w},\bm{\theta})}{J(\bm{\pi}_{\mathtt{R}},\bm{w},\bm{\theta})}:=\Delta\bar{J}\,.$

As already observed in previous work for perfectly known systems [7, 5, 6, 9],
Figure 3 shows that regret minimization constitutes a viable control design
strategy for improving the closed-loop performance when the disturbances do
not match classical design assumptions – in terms of both lower upper bounds
(Figure 3a) and lower realized costs (Figure 3b). Most importantly, our
results show that regret optimal policies continue to offer these performance
advantages consistently in face of the uncertain dynamics. Interestingly, we
further observe that the policy $\bm{\pi}_{\mathtt{R}}$ often outperforms
$\bm{\pi}_{\mathtt{H}}$ even for the worst-case disturbance $\bm{w}$. While
this may seem counterintuitive, we note that $\bm{\pi}_{\mathtt{H}}$ ensures
minimum cost on a single pair of worst-case disturbances and parameters
$(\bm{w}_{\operatorname{worst}},\bm{\theta}_{\operatorname{worst}})$ only.
Conversely, for randomly sampled instances of the uncertain parameters
$\bm{\theta}\neq\bm{\theta}_{\operatorname{worst}}$, the policy
$\bm{\pi}_{\mathtt{H}}$ retains no optimality guarantee on the cost that it
incurs under the most averse perturbation $\bm{w}$ for that $\bm{\theta}$.

##  V Conclusion

We have presented a novel method for convex synthesis of robust control
policies with provable regret and safety guarantees in face of the uncertain
stochastic dynamics. As the clairvoyant optimal policy we compete against is
unknown in this setting, we have proposed sampling the space of parameters
that characterize the system dynamics. Leveraging results from the theory of
scenario optimization, we have shown that the policy that minimizes regret
robustly over these randomly drawn uncertainty instances retains strong
probabilistic out-of-samples guarantees. Finally, we have presented numerical
experiments to corroborate our theoretical results, and to highlight the
potential of regret minimization in adapting to heterogeneous dynamics and
disturbance sequences. Interesting directions for future research encompass
studying infinite-horizon control problems, addressing computational
complexity challenges for real-time implementation, and extending the theory
of this emerging competitive framework to systems with nonlinear dynamics.

## References

  * [1] E. Hazan and K. Singh, “Introduction to online nonstochastic control,” _arXiv preprint arXiv:2211.09619_ , 2022.
  * [2] B. Hassibi, A. H. Sayed, and T. Kailath, _Indefinite-quadratic estimation and control: a unified approach to $\mathcal{H}_{2}$ and $\mathcal{H}_{\infty}$ theories_. SIAM, 1999.
  * [3] N. Agarwal, B. Bullins, E. Hazan, S. Kakade, and K. Singh, “Online control with adversarial disturbances,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 111–119.
  * [4] M. Simchowitz, K. Singh, and E. Hazan, “Improper learning for non-stochastic control,” in _Conference on Learning Theory_. PMLR, 2020, pp. 3320–3436.
  * [5] O. Sabag, G. Goel, S. Lale, and B. Hassibi, “Regret-optimal controller for the full-information problem,” in _2021 American Control Conference (ACC)_. IEEE, 2021, pp. 4777–4782.
  * [6] ——, “Regret-optimal full-information control,” _arXiv preprint arXiv:2105.01244_ , 2021.
  * [7] G. Goel and B. Hassibi, “Regret-optimal estimation and control,” _IEEE Transactions on Automatic Control_ , vol. 68, no. 5, pp. 3041–3053, 2023.
  * [8] O. Sabag, S. Lale, and B. Hassibi, “Optimal competitive-ratio control,” _arXiv preprint arXiv:2206.01782_ , 2022.
  * [9] A. Martin, L. Furieri, F. Dörfler, J. Lygeros, and G. Ferrari-Trecate, “Safe control with minimal regret,” in _Learning for Dynamics and Control Conference_. PMLR, 2022, pp. 726–738.
  * [10] A. Didier, J. Sieber, and M. N. Zeilinger, “A system level approach to regret optimal control,” _IEEE Control Systems Letters_ , vol. 6, pp. 2792–2797, 2022.
  * [11] A. Martin, L. Furieri, F. Dörfler, J. Lygeros, and G. Ferrari-Trecate, “On the guarantees of minimizing regret in receding horizon,” _arXiv preprint arXiv:2306.14561_ , 2023.
  * [12] G. Goel and B. Hassibi, “Measurement-feedback control with optimal data-dependent regret,” _arXiv preprint arXiv:2209.06425_ , 2022.
  * [13] H. Zhou and V. Tzoumas, “Safe control of partially-observed linear time-varying systems with minimal worst-case dynamic regret,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_. IEEE, 2023, pp. 8781–8787.
  * [14] G. Goel and B. Hassibi, “Competitive control,” _IEEE Transactions on Automatic Control_ , vol. 68, no. 9, pp. 5162–5173, 2023.
  * [15] J.-S. Brouillon, F. Dörfler, and G. F. Trecate, “Minimal regret state estimation of time-varying systems,” _IFAC-PapersOnLine_ , vol. 56, no. 2, pp. 2595–2600, 2023.
  * [16] A. Martin, L. Furieri, F. Dörfler, J. Lygeros, and G. Ferrari-Trecate, “Follow the clairvoyant: an imitation learning approach to optimal control,” _IFAC-PapersOnLine_ , vol. 56, no. 2, pp. 2589–2594, 2023.
  * [17] G. Goel, N. Agarwal, K. Singh, and E. Hazan, “Best of both worlds in online control: Competitive ratio and policy regret,” in _Learning for Dynamics and Control Conference_. PMLR, 2023, pp. 1345–1356.
  * [18] G. C. Calafiore and M. C. Campi, “The scenario approach to robust control design,” _IEEE Transactions on automatic control_ , vol. 51, no. 5, pp. 742–753, 2006.
  * [19] M. C. Campi and S. Garatti, “The exact feasibility of randomized solutions of uncertain convex programs,” _SIAM Journal on Optimization_ , vol. 19, no. 3, pp. 1211–1230, 2008.
  * [20] P. M. Esfahani, T. Sutter, and J. Lygeros, “Performance bounds for the scenario approach and an extension to a class of non-convex programs,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 1, pp. 46–58, 2014\.
  * [21] R. Tóth, _Modeling and identification of linear parameter-varying systems_. Springer, 2010, vol. 403.
  * [22] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu, “On the sample complexity of the linear quadratic regulator,” _Foundations of Computational Mathematics_ , vol. 20, no. 4, pp. 633–679, 2020.
  * [23] Y. Zheng, L. Furieri, M. Kamgarpour, and N. Li, “Sample complexity of linear quadratic gaussian (LQG) control for output feedback systems,” in _Learning for dynamics and control_. PMLR, 2021, pp. 559–570.
  * [24] L. Furieri, B. Guo, A. Martin, and G. Ferrari-Trecate, “Near-optimal design of safe output-feedback controllers from noisy data,” _IEEE Transactions on Automatic Control_ , vol. 68, no. 5, pp. 2699–2714, 2023.
  * [25] J. Liu and P. Seiler, “Robust regret optimal control,” _International Journal of Robust and Nonlinear Control_ , 2023.
  * [26] L. Huang, J. Coulson, J. Lygeros, and F. Dörfler, “Decentralized data-enabled predictive control for power system oscillation damping,” _IEEE Transactions on Control Systems Technology_ , vol. 30, no. 3, pp. 1065–1077, 2021.
  * [27] V. D. Blondel and J. N. Tsitsiklis, “A survey of computational complexity results in systems and control,” _Automatica_ , vol. 36, no. 9, pp. 1249–1274, 2000.
  * [28] F. Micheli and J. Lygeros, “Scenario-based stochastic mpc for systems with uncertain dynamics,” in _2022 European Control Conference (ECC)_. IEEE, 2022, pp. 833–838.
  * [29] P. J. Goulart, E. C. Kerrigan, and J. M. Maciejowski, “Optimization over state feedback policies for robust control with constraints,” _Automatica_ , vol. 42, no. 4, pp. 523–533, 2006.
  * [30] Y.-S. Wang, N. Matni, and J. C. Doyle, “A system-level approach to controller synthesis,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 10, pp. 4079–4093, 2019.
  * [31] G. C. Calafiore and L. Fagiano, “Robust model predictive control via scenario optimization,” _IEEE Transactions on Automatic Control_ , vol. 58, no. 1, pp. 219–224, 2012.
  * [32] M. Prandini, S. Garatti, and J. Lygeros, “A randomized approach to stochastic model predictive control,” in _2012 IEEE 51st IEEE Conference on Decision and Control (CDC)_. IEEE, 2012, pp. 7315–7320.
  * [33] D. Muñoz-Carpintero, B. Kouvaritakis, and M. Cannon, “Striped parameterized tube model predictive control,” _Automatica_ , vol. 67, pp. 303–309, 2016.
  * [34] J. Zhang and T. Ohtsuka, “Stochastic model predictive control using simplified affine disturbance feedback for chance-constrained systems,” _IEEE Control Systems Letters_ , vol. 5, no. 5, pp. 1633–1638, 2021.
  * [35] J. Sieber, S. Bennani, and M. N. Zeilinger, “A system level approach to tube-based model predictive control,” _IEEE Control Systems Letters_ , vol. 6, pp. 776–781, 2021.
  * [36] A. A. Ahmadi and A. Majumdar, “DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization,” _SIAM Journal on Applied Algebra and Geometry_ , vol. 3, no. 2, pp. 193–230, 2019.
  * [37] Y. Zheng, G. Fantuzzi, A. Papachristodoulou, P. Goulart, and A. Wynn, “Fast ADMM for semidefinite programs with chordal sparsity,” in _2017 American Control Conference (ACC)_. IEEE, 2017, pp. 3335–3340.
  * [38] M. C. Campi and S. Garatti, “Wait-and-judge scenario optimization,” _Mathematical Programming_ , vol. 167, pp. 155–189, 2018.
  * [39] A. Mosek, “The mosek optimization toolbox for matlab manual,” 2015.
  * [40] M. C. Campi and S. Garatti, “A sampling-and-discarding approach to chance-constrained optimization: feasibility and optimality,” _Journal of optimization theory and applications_ , vol. 148, no. 2, pp. 257–280, 2011\.
  * [41] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, _Linear matrix inequalities in system and control theory_. SIAM, 1994.

###  -A Proof of Proposition 1

For any $\bm{\theta}^{k}\in\mathcal{D}$, by combining (2) with (7), we first
rewrite the per-instance regret (3) as

$\left\lVert\begin{bmatrix}\bm{Q}^{\frac{1}{2}}\bm{\Phi}_{x}(\bm{\theta}^{k})\\\
\bm{R}^{\frac{1}{2}}\bm{\Phi}_{u}\end{bmatrix}\bm{w}\right\rVert^{2}_{2}-\left\lVert\begin{bmatrix}\bm{Q}^{\frac{1}{2}}\bm{\Psi}_{x}(\bm{\theta}^{k})\\\
\bm{R}^{\frac{1}{2}}\bm{\Psi}_{u}(\bm{\theta}^{k})\end{bmatrix}\bm{w}\right\rVert^{2}_{2}\,.$
(18)

By gathering common terms, (18) can be equivalently expressed as the quadratic
form
$\bm{w}^{\top}\bm{\Delta}(\bm{\Phi}_{u},\bm{\Psi}_{u}(\bm{\theta}),\bm{\theta}^{k})\bm{w}$,
where
$\bm{\Delta}(\bm{\Phi}_{u},\bm{\Psi}_{u}(\bm{\theta}),\bm{\theta}^{k}):=\bm{\Delta}^{k}$
is defined as

${\begin{bmatrix}\bm{Q}^{\frac{1}{2}}\bm{\Phi}_{x}(\bm{\theta}^{k})\\\
\bm{R}^{\frac{1}{2}}\bm{\Phi}_{u}\end{bmatrix}}^{\top}\begin{bmatrix}\bm{Q}^{\frac{1}{2}}\bm{\Phi}_{x}(\bm{\theta}^{k})\\\
\bm{R}^{\frac{1}{2}}\bm{\Phi}_{u}\end{bmatrix}-{\begin{bmatrix}\bm{Q}^{\frac{1}{2}}\bm{\Psi}_{x}(\bm{\theta}^{k})\\\
\bm{R}^{\frac{1}{2}}\bm{\Psi}_{u}(\bm{\theta}^{k})\end{bmatrix}}^{\top}\begin{bmatrix}\bm{Q}^{\frac{1}{2}}\bm{\Psi}_{x}(\bm{\theta}^{k})\\\
\bm{R}^{\frac{1}{2}}\bm{\Psi}_{u}(\bm{\theta}^{k})\end{bmatrix}.$

From well-known properties of induced matrix norms and from classical results
on semidefinite programming for eigenvalue minimization (see, e.g., Section
2.2 in [41]), we have:

$\displaystyle\max_{\|\bm{w}\|_{2}\leq
1}~{}\bm{w}^{\top}\bm{\Delta}^{k}\bm{w}=\lambda_{\max}(\bm{\Delta}^{k})=$
$\displaystyle~{}\min_{\lambda^{k}}~{}\lambda^{k}$
$\displaystyle\operatorname*{subject~{}to}~{}\lambda^{k}\bm{I}\succeq\bm{\Delta}^{k}\,.$

In other words, for a fixed $\bm{\theta}^{k}\in\mathcal{D}$, the regret bound
(10d) is satisfied if and only if the robust performance level $\gamma$ is not
smaller than the minimum $\lambda^{k}$ such that
$\lambda^{k}\bm{I}-\bm{\Delta}^{k}\succeq 0$. Equivalently, but without
introducing an unnecessary optimization variable for each sampled scenario, if
and only $\gamma\bm{I}-\bm{\Delta}^{k}\succeq 0$. From this last expression,
the set of linear matrix inequality constraints (11c) follows by exploiting
the Schur complement to remove the quadratic dependence of $\bm{\Delta}^{k}$
on $\bm{\Phi}_{u}$.

We then turn our attention to enforcing robust satisfaction of the safety
constraints (10c). First, we note that each row
$\max_{\bm{w}\in\mathcal{W}(\bm{\theta}^{k})}(\bm{H}_{x}^{k}\bm{\Phi}_{x}(\bm{\theta}^{k})+\bm{H}_{u}^{k}\bm{\Phi}_{u})_{i}\bm{w}$
of (10c) constitutes a second-order cone program in $\bm{d}$, where $\bm{d}$
is such that $\bm{w}=\bm{H}_{w}(\bm{\theta})\bm{d}$ as per (5). Leveraging
well-known properties of dual norms, we then observe that
$\max_{\left\lVert\bm{d}\right\rVert_{2}\leq
1}~{}(\bm{H}_{x}^{k}\bm{\Phi}_{x}(\bm{\theta}^{k})+\bm{H}_{u}^{k}\bm{\Phi}_{u})_{i}\bm{H}_{w}(\bm{\theta})\bm{d}$
is equal to

$\left\lVert\bm{H}_{w}(\bm{\theta})^{\top}(\bm{H}_{x}^{k}\bm{\Phi}_{x}(\bm{\theta}^{k})+\bm{H}_{u}^{k}\bm{\Phi}_{u})_{i}^{\top}\right\rVert_{2}\,.$

Lastly, iterating over all rows of (10c), the set of second-order cone
constraints (11b) follows.

###  -B Proof of Theorem 1

In light of Proposition 1, we have that the real-valued functions
$f_{1}(\bm{\Phi}_{u},\gamma,\bm{\theta})=\max_{\left\lVert\bm{w}\right\rVert_{2}\leq
1}~{}\mathtt{R}(\bm{\Phi}_{u},\bm{\Psi}_{u}(\bm{\theta}),\bm{w},\bm{\theta})-\gamma$
and
$f_{2}(\bm{\Phi}_{u},\bm{\theta})=\max_{\bm{w}\in\mathcal{W}(\bm{\theta})}~{}\bm{H}_{x}(\bm{\theta})\bm{\Phi}_{x}(\bm{\theta})\bm{w}+\bm{H}_{u}(\bm{\theta})\bm{\Phi}_{u}\bm{w}-\bm{h}(\bm{\theta})$,
with $\bm{\Phi}_{x}(\bm{\theta})$ an linear map of $\bm{\Phi}_{u}$ as per (7),
are convex in the design parameters $\bm{\Phi}_{u}$ and $\gamma$. Since the
point-wise maximum of convex functions is convex, we then conclude that
$f(\bm{\Phi}_{u},\gamma,\bm{\theta})=\max~{}(f_{1}(\bm{\Phi}_{u},\gamma,\bm{\theta}),f_{2}(\bm{\Phi}_{u},\bm{\theta}))$
is also convex in $\bm{\Phi}_{u}$ and $\gamma$. Hence, the robustly safe
regret minimization problem (9) effectively calls for the minimization of a
linear objective subject to a possibly infinite number of convex constraints
of the form $f(\bm{\Phi}_{u},\gamma,\bm{\theta})\leq 0$. Based on these
observations, our probabilistic guarantees then follow by combining the
results of Theorem 1 in [18] and Theorem 2.4 in [19].