Regret-Optimal Filtering

Oron Sabag Babak Hassibi

Caltech

###### Abstract

We consider the problem of filtering in linear state-space models (e.g., the
Kalman filter setting) through the lens of regret optimization. Specifically,
we study the problem of causally estimating a desired signal generated by a
linear state space model driven by process noise, and based on noisy
observations of a related observation process. Different assumptions on the
driving disturbance and the observation noise sequences give rise to different
estimators: in the stochastic setting to the celebrated Kalman filter, and in
the deterministic setting of bounded energy disturbances to $H_{\infty}$
estimators. In this work, we formulate a novel criterion for estimator design
which is based on the concept of regret. We define the regret as the
difference in estimation error energy between a clairvoyant estimator that has
access to all future observations (a so-called smoother) and a causal one that
only has access to current and past observations. The regret-optimal estimator
is chosen to minimize this worst-case difference across all bounded-energy
noise sequences. The resulting estimator is adaptive in the sense that it aims
to mimic the behavior of the clairvoyant estimator, irrespective of what the
realization of the noise will be and thus nicely interpolates between the
stochastic and deterministic approaches. We provide a solution for the regret
estimation problem at two different levels. First, we provide a solution at
the operator level by reducing it to the Nehari problem, i.e., the problem of
approximating an anti-causal operator with a causal one. Second, when we have
an underlying state-space model, we explicitly find the estimator that
achieves the optimal regret. From a computational perspective, the regret-
optimal estimator can be easily implemented by solving three Riccati equations
and a single Lyapunov equation. For a state-space model of dimension $n$, the
regret-optimal estimator has a state-space structure of dimension $3n$. We
demonstrate the applicability and efficacy of the estimator in a variety of
problems and observe that the estimator has average and worst-case
performances that are simultaneously close to their optimal values. We
therefore argue that regret-optimality is a viable approach to estimator
design.

##  1 Introduction

Filtering is the problem of estimating the current value of a desired signal,
given current and past values of a related observation signal. It has numerous
applications in signal processing, control, and learning and a rich history
going back to Wiener, Kolomgorov, and Kalman. When the underlying desired and
observation signals have state-space structures driven by white Gaussian
noise, the celebrated Kalman filter gives the minimum mean-square error
estimate of the current value of the desired signal, given the past and
current of the observed signal Kalman (1960). When all that is known of the
noise sources are their first and second-order statistics, the Kalman filter
gives the linear least-mean-squares estimate. While these are very desired
properties, the Kalman filter is predicated on knowing the underlying
statistics and distributions of the signal. It can therefore have poor
performance if the underlying signals have statistics and/or properties that
deviate from those that are assumed. It is also not suitable for learning
applications, since it has no possibility of ”learning” the signal statistics.

Another approach to filtering that was developed in the 80’s and 90’s was
$H_{\infty}$ filtering, where the noise sources were considered adversarial
and the worst-case estimation error energy was minimized (over all bounded
energy noises). While $H_{\infty}$ estimators are robust to lack of
statistical knowledge of the underlying noise sources, and have some deep
connections to classical learning algorithms (see, e.g. Hassibi et al.
(1995)), they are often too conservative since they safeguard against the
worst-case and do not exploit the noise structure.

###  1.1 Main contributions

The contributions can be summarized as follows:

  * •

Motivated by the concept of regret in learning problems (e.g., Hazan (2019),
Simchowitz (2020), Abbasi-Yadkori (2011),(2019)), we propose to adopt it for
filtering problems so as to bridge between the philosophies of Kalman and
$H_{\infty}$ filtering. Specifically, we formulate a new design criterion for
filtering which optimizes the difference in estimation error energies between
a clairvoyant estimator that has access to the entire observations sequence
(including future samples) and a causal one that does not have access to
future observations. We show that the regret formulation is fundamentally
different from the $H_{2}$ (e.g., the Kalman filter by Kalman (1960)) and
$H_{\infty}$ criteria (see the tutorial by Shaked et al. (1992)).

  * •

We show that the regret-optimal estimation problem can be reduced to the
classical Nehari problem in operator theory (Theorem 1). This is the problem
of approximating an anti-causal operator with a causal one in the operator
norm by Nehari (1957).

  * •

When the underlying signals have a state space structure, we provide an
explicit solution for the regret-optimal filter. The solution to the filtering
problem is given as via simple steps; first, the optimal regret value is
determined by solving two Riccati equations and a single Lyapunov, along with
a bisection method with a simple condition that is given in Theorem 2. Then,
the regret-optimal filter is given explicitly in a state-space form in Theorem
4.

  * •

We present numerical examples that demonstrate the efficacy and applicability
of the approach and observe that the regret-optimal filter has average and
worst-case performances that are simultaneously close to their optimal values.
We therefore argue that regret-optimality is a viable approach to estimator
design.

##  2 The Setting and Problem Formulation

###  2.1 Notation

Linear operators are denoted by calligraphic letters, e.g., $\mathcal{X}$.
Finite-dimensional vectors and matrices are denoted with small and capital
letters, respectively, e.g., $x$ and $X$. Subscripts are used to denote time
indices e.g., $x_{i}$, and boldface letters denote the set of finite-
dimensional vectors at all times, e.g., $\mathbf{x}=\\{x_{i}\\}_{i}$.

###  2.2 The setting and problem formulation

We consider a general estimation problem

$\displaystyle\operatorname{\mathbf{y}}$
$\displaystyle=\mathcal{H}\operatorname{\mathbf{w}}+\operatorname{\mathbf{v}}\operatorname*{}$
$\displaystyle\mathbf{s}$ $\displaystyle=\mathcal{L}\operatorname{\mathbf{w}}$
(1)

where $\mathcal{H}$ and $\mathcal{L}$ are strictly causal operators, the
sequence $\operatorname{\mathbf{w}}$ denotes an exogenous disturbance $w$ that
generates a hidden state as the output of an operator $\mathcal{H}$,
$\operatorname{\mathbf{y}}$ denotes the observations process and $\mathbf{s}$
denotes the signal that should be estimated. Note that we did not specify yet
the estimator operation or the time horizon. The setting is quite general and
includes for instance the state-space model that will be presented in the next
section.

A linear estimator is a linear mapping from the observations to the signal
space $\mathbf{s}$ and is denoted as
$\hat{\mathbf{s}}=\mathcal{K}\operatorname{\mathbf{y}}$. Then, for any
$\mathcal{K}$, the estimation error of the signal is

$\displaystyle\mathbf{e}$
$\displaystyle=\mathbf{s}-\hat{\mathbf{s}}\operatorname*{}$
$\displaystyle=\begin{pmatrix}\mathcal{L}-\mathcal{K}\mathcal{H}&-\mathcal{K}\end{pmatrix}\begin{pmatrix}\operatorname{\mathbf{w}}\\\
\operatorname{\mathbf{v}}\end{pmatrix}\operatorname*{}$
$\displaystyle\triangleq
T_{\mathcal{K}}\begin{pmatrix}\operatorname{\mathbf{w}}\\\
\operatorname{\mathbf{v}}\end{pmatrix}$ (2)

Note that the estimation error is a function of the driving disturbance
$\operatorname{\mathbf{w}}$ and the observation noise
$\operatorname{\mathbf{v}}$. The squared error can then be expressed as

$\displaystyle\mathbf{e}(\operatorname{\mathbf{w}},\operatorname{\mathbf{v}},\mathcal{K})$
$\displaystyle\triangleq\mathbf{e}^{\ast}\mathbf{e}\operatorname*{}$
$\displaystyle=\begin{pmatrix}\operatorname{\mathbf{w}}^{\ast}&\operatorname{\mathbf{v}}^{\ast}\end{pmatrix}T_{\mathcal{K}}^{\ast}T_{\mathcal{K}}\begin{pmatrix}\operatorname{\mathbf{w}}\\\
\operatorname{\mathbf{v}}\end{pmatrix}.$ (3)

Different assumptions on the driving disturbance and the observation noise
sequences give rise to different estimators: in the stochastic setting to the
celebrated Kalman filter, and in the deterministic setting of bounded energy
disturbances to $H_{\infty}$ estimators. A common characteristic of these two
paradigms is that if we do not restrict the constructed estimators to be
causal, then there exists a single linear estimator that attains the minimal
Frobenius and operator norms simultaneously. This known fact is summarized in
the following lemma.

######  Lemma 1 (The non-causal estimator).

For the $H_{2}$ and the $H_{\infty}$ problems, the optimal non-causal
estimator is
$\mathcal{K}_{0}=\mathcal{L}\mathcal{H}^{\ast}(I+\mathcal{H}\mathcal{H}^{\ast})^{-1}.$

Note that the non-causal estimator cannot be implemented in practice even for
simple operator $\mathcal{L},\mathcal{H}$ since it requires access to future
instances of the observations. However, the fact that there is a single
estimator that simultaneously optimizes these two norms naturally leads to our
new approach of regret optimization. Specifically, we will aim at constructing
a causal (or strictly causal) estimator that performs as close as possible to
the non-causal estimator in Lemma 1.

The optimal regret can now be defined as

$\displaystyle{\operatorname*{regret}}^{\ast}$
$\displaystyle=\min_{\text{causal}\
\mathcal{K}}\max_{\operatorname{\mathbf{w}},\operatorname{\mathbf{v}}\in\ell_{2},\operatorname{\mathbf{w}},\operatorname{\mathbf{v}}\neq
0}\frac{|\mathbf{e}(\operatorname{\mathbf{w}},\operatorname{\mathbf{v}},\mathcal{K})-\mathbf{e}(\operatorname{\mathbf{w}},\operatorname{\mathbf{v}},\mathcal{K}_{0})|}{\|\operatorname{\mathbf{w}}\|^{2}+\|\operatorname{\mathbf{v}}\|^{2}}\operatorname*{}$
$\displaystyle=\min_{\text{causal}\
\mathcal{K}}\|T_{\mathcal{K}}^{\ast}T_{\mathcal{K}}-T_{\mathcal{K}_{0}}^{\ast}T_{\mathcal{K}_{0}}\|.$
(4)

In words, the defined regret metric measures the worst-case deviation of the
estimation error from the estimation error of the non-causal estimator across
all bounded-energy disturbances sequences. It is illuminating to compare now
the regret criterion with the traditional $H_{\infty}$ estimation:

$\displaystyle\underbrace{\inf_{\mbox{causal
$K$}}\|T_{K}^{*}T_{K}\|}_{\mbox{$H_{\infty}$
estimation}}~{}~{},~{}~{}\underbrace{\inf_{\mbox{causal
$K$}}\|T_{K}^{\ast}T_{K}-T_{K_{0}}^{\ast}T_{K_{0}}\|.}_{\mbox{regret-optimal
estimation}}$

The difference is now transparent; in $H_{\infty}$ estimation, one attempts to
minimize the worst-case gain from the disturbances energy to the estimation
error, whereas in regret-optimal estimation one attempts to minimize the
worst-case gain from the disturbance energy to the regret. It is this latter
fact that makes the regret-optimal estimator more adaptive since it has as its
baseline the best that any noncausal estimator can do, whereas the
$H_{\infty}$ estimator has no baseline to measure itself against. This fact
will be illustrated in Section 4, where we will show that the regret
definition results in an estimator that interpolates between the $H_{2}$ and
the $H_{\infty}$ design criteria.

Simplifying the optimal regret to have a simple formula is a difficult task
and. Therefore, in this paper, we define a sub-optimal problem of determining
whether the optimal regret is below, above or equal to a given threshold
$\gamma$. This is made precise in the following problem definition.

######  Problem 1 (The $\gamma$-optimal regret estimation problem).

For a fixed $\gamma$, if exists, find a causal estimator $\mathcal{K}$ such
that

$\displaystyle\|T_{\mathcal{K}}^{\ast}T_{\mathcal{K}}-T_{\mathcal{K}_{0}}^{\ast}T_{\mathcal{K}_{0}}\|_{\infty}\leq\gamma^{2}.$
(5)

A _$\gamma$ -optimal estimator_ is referred to as any solution to Problem 1.

Finally, we define a fundamental problem which will serve as the main tool in
the derivations.

######  Problem 2 (The Nehari problem).

Given an anticausal and bounded operator $\mathcal{U}$, find a causal operator
$\mathcal{K}$ such that $\|\mathcal{K}-\mathcal{U}\|$ is minimized.

This problem is well known as the Nehari problem. In the general operator
notation, it is difficult to derive an explicit formulae for the approximation
$\mathcal{K}$ and the minimal value of a valid $\gamma_{N}$. However, when
there is a state-space structure to the operator $\mathcal{U}$, then the
problem has a closed-form solution that will be presented in Section 6.

###  2.3 The state-space model

The setting defined above in its operator notation is general and cannot have
an explicit structured solution. In many cases, including our problem,
imposing a state space structure for the problem provides means to obtain
explicit estimators. In the state-space setting, the equations in (2.2) are
simplify to

$\displaystyle x_{i+1}$ $\displaystyle=Fx_{i}+Gw_{i}\operatorname*{}$
$\displaystyle y_{i}$ $\displaystyle=Hx_{i}+v_{i}\operatorname*{}$
$\displaystyle s_{i}$ $\displaystyle=Lx_{i},$ (6)

where $x_{i}$ is the hidden state, $y_{i}$ is the observation and $s_{i}$
corresponds to the signal that needs to be estimated. We also make the
standard assumption that the pair $(F,H)$ is detectable. To recover the state-
space setting from its operator notation counterpart in (2.2), choose
$\mathcal{H}$ and $\mathcal{L}$ as Toeplitz operators with Markov parameters
$HF^{i}G$ and $LF^{i}G$, respectively.

A causal estimator is defined as a sequence of mappings $\pi_{i}(\cdot)$ with
the estimation being $\hat{s}_{i}=\pi_{i}(\\{y_{j}\\}_{j\leq i})$. The
estimation error at time $i$ is

$\displaystyle e_{i}$ $\displaystyle=s_{i}-\hat{s}_{i}.$ (7)

In a similar fashion, we can define a strictly causal estimator as a sequence
of strictly causal mappings, i.e., $\hat{s}_{i}=\pi_{i}(\\{y_{j}\\}_{j<i})$.
Due to lack of space in this paper, we will not present the solution for the
strictly causal setting which follows from the same steps that will be taken
for the causal scenario.

Note that we did not specify the time horizon of the problem so that the
formulation here and in the previous section hold for finite, one-sided
infinite and doubly infinite time horizons. However, to simplify the
derivations of the state-space, we will focus here on the case of doubly-
infinite time horizon where the total estimation error energy can be expressed
as $\sum_{i=-\infty}^{\infty}e_{i}^{\ast}e_{i}$. In this case, it is also
convenient to define the causal transfer matrices

$\displaystyle H(z)$ $\displaystyle=H(zI-F)^{-1}G,\operatorname*{}$
$\displaystyle L(z)$ $\displaystyle=L(zI-F)^{-1}G.$ (8)

that describe the filters whose input is the disturbance $w$ and their outputs
are the observation $y$ and the target signal $s$, respectively. We now
proceed to show the main results of this paper.

##  3 Main results

In this section, we present our main results. We first provide the reduction
of the general regret estimation problem to a Nehari problem. In Section 3.1,
we provide an explicit solution for the state-space setting in the causal
scenario.

######  Theorem 1 (Reduction to the Nehari Problem).

A $\gamma$-optimal estimator exists if and only if there exists a solution to
the Neahri problem

$\displaystyle\min_{\text{causal}\
\mathcal{K}}\|\\{\nabla_{\gamma}\mathcal{K}_{0}\Delta\\}_{-}-\mathcal{K}\|\leq
1,$ (9)

where $\\{\cdot\\}_{-}$ denotes the strictly anticausal part of its argument,
and $\Delta,\nabla_{\gamma}$ are causal operators that are obtained from the
canonical factorizations

$\displaystyle\Delta\Delta^{\ast}$
$\displaystyle=I+\mathcal{H}\mathcal{H}^{\ast}\operatorname*{}$
$\displaystyle\nabla_{\gamma}^{\ast}\nabla_{\gamma}$
$\displaystyle=\gamma^{-2}(I+\gamma^{-2}\mathcal{L}(I+\mathcal{H}^{\ast}\mathcal{H})^{-1}\mathcal{L}^{\ast}).$
(10)

Let $(\gamma^{\ast},\mathcal{K}_{N})$ be a solution that achieves the upper
bound in the Nehari problem (9), then a regret-optimal estimator is given by

$\displaystyle\mathcal{K}$
$\displaystyle=\nabla^{-1}_{\gamma^{\ast}}(\mathcal{K}_{N}+\\{\nabla_{\gamma^{\ast}}\mathcal{K}_{0}\Delta\\}_{+})\Delta^{-1}$
(11)

where $\\{\cdot\\}_{+}$ denoted the causal part of an operator.

For general operators $\mathcal{L},\mathcal{H}$, the reduction in Theorem 1
does not give practical means to derive an implementable estimator. However,
it provides the outline of the necessary technical steps in order to have
explicit characterizations in the state-space setting. Specifically, in the
state-space setting we will need to perform two canonical spectral
factorizations (Eq. 1) and a decomposition of the operator
$\nabla_{\gamma^{\ast}}\mathcal{K}_{0}\Delta$ into causal and anticausal
operators. The proof of Theorem 1 appears in Section 5.

###  3.1 Solution for the state-space setting

We now proceed to particularize our results to the state-space representation
of the estimation problem. Towards our main objective to derive the regret-
optimal estimator, we will solve the sub-optimal problem, i.e., for a given
$\gamma$. Thus, our results are presented in two steps. First, we provide a
simple condition to verify whether the value of $\gamma$ is valid or not.
Then, assuming that the threshold $\gamma$ have been optimized, we present the
regret-optimal estimator.

Throughout the derivations, there are three Riccati and a single Lyapunov
equations. The first Riccati equation is the standard one from the Kalman
filter, i.e.,

$\displaystyle P\mspace{-2.0mu}$
$\displaystyle=\mspace{-2.0mu}GG^{\ast}\mspace{-4.0mu}+\mspace{-2.0mu}FPF^{\ast}\mspace{-4.0mu}-\mspace{-2.0mu}FPH^{\ast}(I\mspace{-2.0mu}+\mspace{-2.0mu}HPH^{\ast})^{-1}HPF^{\ast}.$
(12)

The stabilizing solution is denoted as $P$, its feedback gain as
$K_{P}=FPH^{\ast}(I+HPH^{\ast})^{-1}$ and its closed-loop system as
$F_{P}=F-GK_{P}$.

The remaining two Riccati equation depend on the parameter $\gamma$ and
therefore should be part of the optimization on $\gamma$. Define the
$\gamma$-dependent Riccati equations as

$\displaystyle W$ $\displaystyle=H^{\ast}H+\gamma^{-2}L^{\ast}L+F^{\ast}WF-
K_{W}^{\ast}R_{W}K_{W}\operatorname*{}$ $\displaystyle Q$
$\displaystyle=-GR_{W}^{-1}G^{\ast}+F_{W}QF_{W}^{\ast}-K_{Q}R_{Q}^{-1}K_{Q}^{\ast},$
(13)

with

$\displaystyle K_{W}$ $\displaystyle=R_{W}^{-1}G^{\ast}WF;\ \ \
R_{W}=I+G^{\ast}WG\operatorname*{}$ $\displaystyle K_{Q}$
$\displaystyle=F_{W}QL^{\ast}R_{Q}^{-1};\ \ R_{Q}=\gamma^{2}I+LQL^{\ast}.$
(14)

Additionally, define the corresponding closed-loop systems
$F_{Q}=F_{W}-K_{Q}L$ and $F_{W}=F-GK_{W}$, and the factorizations
$R_{W}=R_{W}^{\ast/2}R_{W}^{1/2}$ and $R_{Q}=R_{Q}^{1/2}R_{Q}^{\ast/2}$. Note
that the Riccati equation for $Q$ depends on the solution to Riccati equation
for $W$.

Finally, define $U$ as the solution to the Lyapunov equation

$\displaystyle U$ $\displaystyle=K_{Q}LPF_{P}^{\ast}+F_{Q}UF_{P}^{\ast}.$ (15)

We are now ready to present the condition for the existence of a regret-
optimal estimator.

######  Theorem 2 (Condition for Estimator Existence).

A $\gamma$-optimal estimator exists if and only if

$\displaystyle\bar{\sigma}(Z_{\gamma}\Pi)\leq 1,$ (16)

where $Z_{\gamma}$ and $\Pi$ are the solutions to the Lyapunov equations

$\displaystyle\Pi$ $\displaystyle=F_{P}^{\ast}\Pi
F_{P}+H^{\ast}(I+HPH^{\ast})^{-1}H\operatorname*{}$ $\displaystyle Z_{\gamma}$
$\displaystyle=F_{P}Z_{\gamma}F_{P}^{\ast}+F_{P}(P-U)^{\ast}L^{\ast}R_{Q}^{-1}L(P-U)F_{P}^{\ast}.$
(17)

A regret-optimal estimator that attains the optimal regret can be found by
optimizing over $\gamma$ in (16) so that the maximal singular value is
arbitrarily close to $1$. From now on, we assume that the value of $\gamma$ is
fixed after the optimization which fix in turn the $\gamma$-dependent
quantities $(W,Q,U,Z_{\gamma})$.

A key element in our solution to the regret-optimal estimator is a solution to
the Nehari problem in Theorem 1. Recall that its solution provides the best
approximation (in the operator norm) for the anticausal part of the transfer
function
$\nabla_{\gamma}^{-1}(z)L(z)H^{\ast}(z^{-\ast})\Delta^{-\ast}(z^{-\ast})$. We
denote this anticausal part as $T(z)$ which appears explicitly below in (5).
By having the operator $T(z)$, we can provide a solution for the Nehari
problem.

######  Lemma 2.

For any $\gamma$, the optimal solution to the Nehari problem with $T(z)$ in
(5) is

$\displaystyle K_{N}(z)$ $\displaystyle=\tilde{\Pi}(I+F_{N}(zI-
F_{N})^{-1})G_{N},$ (18)

where

$\displaystyle G_{N}$
$\displaystyle=(I-F_{P}Z_{\gamma}F_{P}^{\ast}\Pi)^{-1}F_{P}Z_{\gamma}H^{\ast}(I+HPH^{\ast})^{-\ast/2}\operatorname*{}$
$\displaystyle F_{N}$
$\displaystyle=F_{P}-G_{N}(I+HPH^{\ast})^{-1/2}H\operatorname*{}$
$\displaystyle\tilde{\Pi}$ $\displaystyle=R_{Q}^{-1/2}L(P-U)F_{P}^{\ast}\Pi$
(19)

where $(Z_{\gamma},\Pi)$ are defined in (2).

Although the solution to the Nehari problem is given for any value of
$\gamma$, it should be clear that it should be chosen accordingly with Theorem
2 in order to result in a $\gamma$-optimal estimator.

The following theorem reveals the structure of the regret-optimal estimator in
the frequency domain.

######  Theorem 3 (The Regret-Optimal Estimator in Frequency Domain).

Given the optimal threshold $\gamma^{\ast}$, a regret-optimal estimator for
the causal scenario is given by

$\displaystyle K(z)$
$\displaystyle=\nabla^{-1}_{\gamma^{\ast}}(z)[K_{N}(z)+S(z)]\Delta^{-1}(z)+K_{H_{2}}(z),\operatorname*{}$

with

$\displaystyle\nabla^{-1}_{\gamma}(z)=(I+L(zI-
F_{W})^{-1}K_{Q})R_{Q}^{1/2}\operatorname*{}$ $\displaystyle
S(z)=-R_{Q}^{-1/2}L[(zI-
F_{Q})^{-1}F_{Q}+I]UH^{\ast}(I+HPH^{\ast})^{-\ast/2}\operatorname*{}$
$\displaystyle\Delta^{-1}(z)=(I+HPH^{\ast})^{-1/2}(I+H(zI-F)^{-1}K_{P})^{-1},$
(20)

where all constants are defined in (12)-(15), $K_{N}(z)$ is given in (18) and
$K_{H_{2}}(z)$ is the causal $H_{2}$ (Kalman) filter:

$\displaystyle K_{H_{2}}(z)$
$\displaystyle=LPH^{\ast}(I+HPH^{\ast})^{-1}\operatorname*{}$
$\displaystyle+L(I-PH^{\ast}(I+HPH^{\ast})^{-1}H)(zI-
F_{P})^{-1}K_{P}.\operatorname*{}$

It is interesting to note that the causal Kalman filter naturally appears as
part of our solution to the regret-optimal estimation. This implies that the
regret-optimal estimator is a sum of two terms; the first is a Kalman filter
which is designed to minimize the Frobenius norm of the operator $T_{K}$,
while the other term is resulted from the Nehari and guarantees that the
regret criterion is minimized.

At this point, the frequency-domain results can be converted into a simple
state-space.

######  Theorem 4 (The Causal Regret-Optimal Estimator).

Given the optimal threshold $\gamma^{\ast}$, a regret-optimal estimator for
the causal scenario is given by

$\displaystyle\xi_{i+1}$
$\displaystyle=\tilde{F}\xi_{i}+\tilde{G}y_{i}\operatorname*{}$
$\displaystyle\hat{s}_{i}$ $\displaystyle=\tilde{H}\xi_{i}+\tilde{J}y_{i}.$
(21)

where the matrices are given by

$\displaystyle\tilde{F}$ $\displaystyle=\begin{pmatrix}F_{P}&0&0\\\
\tilde{F}_{2,1}&F_{N}&0\\\
\tilde{F}_{3,1}&\tilde{F}_{3,2}&F_{W}\end{pmatrix};$ (22)
$\displaystyle\tilde{H}$
$\displaystyle=\begin{pmatrix}\tilde{H}_{1}&R_{Q}^{1/2}\tilde{\Pi}F_{N}&L\end{pmatrix}\operatorname*{}$
$\displaystyle\tilde{G}$ $\displaystyle=\begin{pmatrix}K_{P}\\\
G_{N}(I+HPH^{\ast})^{-1/2}\\\ \tilde{G}_{3}\end{pmatrix}\operatorname*{}$
$\displaystyle\tilde{J}$
$\displaystyle=L(P-U)H^{\ast}(I+HPH^{\ast})^{-1}\operatorname*{}$
$\displaystyle\ +R_{Q}^{1/2}\tilde{\Pi}G_{N}(I+HPH^{\ast})^{-1/2},$ (23)

and the explicit constants are

$\displaystyle\tilde{F}_{2,1}$
$\displaystyle=-G_{N}(I+HPH^{\ast})^{-1/2}H\operatorname*{}$
$\displaystyle\tilde{F}_{3,1}$
$\displaystyle=F_{W}UH^{\ast}(I+HPH^{\ast})^{-1}H\operatorname*{}$
$\displaystyle\
-K_{Q}R_{Q}^{1/2}\tilde{\Pi}G_{N}(I+HPH^{\ast})^{-1/2}H\operatorname*{}$
$\displaystyle\tilde{F}_{3,2}$
$\displaystyle=K_{Q}R_{Q}^{1/2}\tilde{\Pi}F_{N}\operatorname*{}$
$\displaystyle\tilde{H}_{1}$
$\displaystyle=L-L(P-U)H^{\ast}(I+HPH^{\ast})^{-1}H\operatorname*{}$
$\displaystyle\
-LK_{Q}R_{Q}^{1/2}\tilde{\Pi}G_{N}(I+HPH^{\ast})^{-1/2}H\operatorname*{}$
$\displaystyle\tilde{G}_{3}$
$\displaystyle=K_{Q}R_{Q}^{1/2}\tilde{\Pi}G_{N}(I+HPH^{\ast})^{-1/2}\operatorname*{}$
$\displaystyle\ -F_{W}UH^{\ast}(I+HPH^{\ast})^{-1}.$ (24)

with the Riccati variables defined in (12)-(15) and the variables
$(F_{N},G_{N},\tilde{\Pi})$ defined in (2).

By Theorem 4, given the optimal threshold $\gamma^{\ast}$, the regret-optimal
estimator can be easily implemented. Note that the $\gamma-$dependent
variables should be computed only throughout the process of determining
$\gamma^{\ast}$ but not throughout the estimation process itself. Thus, from
computational perspective, the filter requires the same resources as the
standard Kalman filter. Its internal state inherits the finite dimension of
the original state space but has an increased dimension with a factor of
three.

##  4 Numerical examples

We have performed two numerical experiments to evaluate the performance of the
regret-optimal estimator compared to the traditional $H_{2}$ and $H_{\infty}$
estimators. As mentioned earlier, the performance of any (linear) estimator is
governed by the transfer operator $T_{K}$ that maps the disturbance sequences
$\mathbf{w}$ and $\mathbf{v}$ to the errors sequences $\mathbf{e}$. It will be
useful to represent this operator via its transfer function in the $z$-domain,
i.e.,

$T_{K}(z)=\left[\begin{array}[]{cc}L(z)-K(z)H(z)&-K(z)\end{array}\right].$

The squared Frobenius norm of $T_{K}$, which is what the $H_{2}$ estimator
minimizes, is given by

$\|T_{K}\|_{F}^{2}=\frac{1}{2\pi}\int_{0}^{2\pi}\mbox{trace}\left(T_{K}^{*}(e^{j\omega})T_{K}(e^{j\omega})\right)d\omega,$

and the squared operator norm of $T_{K}$, which is what $H_{\infty}$
estimators minimize, by

$\|T_{K}\|^{2}=\max_{0\leq\omega\leq
2\pi}\bar{\sigma}\left(T^{\ast}_{K}(e^{j\omega})T_{K}(e^{j\omega})\right),$

where $\bar{\sigma}(\cdot)$ denotes the maximal singular value of a matrix.

Figure 1: The squared operator norm as a function of the frequency parameter
for the scalar system in Section 4.1. The norm is compared between the
$H_{2}$, $H_{\infty}$, non-causal and our new regret-optimal estimator. As can
be seen, the non-causal estimator achieves the best performance at all
frequencies. As expected, among all causal estimators, the $H_{\infty}$
estimator achieves the lowest peak, and the $H_{2}$ estimator attains the
smallest area under its curve (i.e., integral). Out new estimator attains the
best of the two worlds as it achieves a lower peak than the $H_{2}$ estimator,
and a comparable area with the $H_{2}$ estimator. Precise comparison of the
resulted norms appears in Table 1.

###  4.1 Scalar systems

We start with a simple scalar system to illustrate the results. For scalar
systems, $T_{K}(z)$ is a 1-by-2 vector so we have that

$\|T_{K}\|_{F}^{2}=\frac{1}{2\pi}\int_{0}^{2\pi}\left\|T_{K}(e^{j\omega})\right\|^{2}d\omega.$

Consider now a simple stable scalar state-space with $F=0.9$, $H=L=G=1$. For
such a system, we have constructed the optimal $H_{2}$, $H_{\infty}$, and non-
causal estimators, as well as the regret-optimal estimator. Plotting the value
of $\|T_{K}(e^{j\omega})\|^{2}$, as a function of frequency, is quite
illuminating as it allows one to assess and compare the performance of the
respective estimators across the full range of input disturbances. This is
done in Figure 1.

Table 1: Performance for the Scalar Example | $\|T_{K}\|_{F}^{2}$ | $\|T_{K}\|^{2}$ | Regret
---|---|---|---
Noncausal estimator | 0.46 | 0.99 | 0
Regret-optimal | 0.65 | 1.1 | 0.38
$H_{2}$ estimator | 0.6 | 1.27 | 0.7
$H_{\infty}$ estimator | 0.94 | 0.99 | 0.71

As can be seen, the non-causal estimator outperforms the other three
estimators across all frequencies. The $H_{2}$ estimator minimizes the
Frobenius norm, i.e., the average performance over iid $w$, which is the area
under the curve. However, in doing so, it sacrifices the worst-case
performance and so has a relatively large peak at low frequencies. The
$H_{\infty}$ estimator minimizes the operator norm, i.e., the worst-case
performance, which is the peak of the curve. (Here we can see that the
$H_{\infty}$-optimal estimator has the same peak as the non-causal estimator
meaning that it attains the same worst-case performance.) However, in doing
so, it sacrifices the average performance and has a relatively large area
under the curve. Recall that the regret-optimal estimator aims to mimic the
non-causal behavior. In doing so, it achieves the best of both worlds: it has
an area under the curve that is close to that of the $H_{2}$-optimal estimator
(0.6 vs 0.65), and it has a peak that significantly improves upon the the peak
of the $H_{2}$-optimal estimator. The precise norms are presented in Table 1.

It is also illuminating to examine our new regret criterion in Fig. 4.1. We
plot the regret of the causal estimators with respect to the non-causal
estimator. It can be seen that at low frequencies, the $H_{\infty}$ estimator
has the lowest regret, while at mid-frequencies it is the $H_{2}$ estimator.
However, their peak is almost twice that of the regret-optimal estimator that
maintains almost a constant regret across all frequencies.

Figure 2: The frequency response of the various estimators for the tracking
example in Section 4.2. Comparison of the corresponding norms appears in Table
2.

###  4.2 Tracking example

Here, we will study a one-dimensional tracking problem whose state-space model
is

$\displaystyle\begin{pmatrix}x_{i+1}\\\ \nu_{i+1}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}1&\Delta T\\\
0&1\end{pmatrix}\begin{pmatrix}x_{i}\\\
\nu_{i}\end{pmatrix}+\begin{pmatrix}0\\\ \Delta
T\end{pmatrix}a_{i}\operatorname*{}$ $\displaystyle y_{i}$
$\displaystyle=\begin{pmatrix}1&0\end{pmatrix}\begin{pmatrix}x_{i}\\\
\nu_{i}\end{pmatrix}+v_{i}$ (25) $\displaystyle s_{i}$
$\displaystyle=x_{i+1},$ (26)

where $x_{i}$ corresponds to the position, $\nu_{i}$ corresponds to velocity
and $a_{i}$ to the exogenous acceleration. The desired signal is the position
of the object at the next time step $s_{i}=x_{i+1}$, and the observations
signal is the noisy position $y_{i}=x_{i}+v_{i}$, where $v_{i}$ is measurement
noise. The frequency reponse of the various estimators is presented in Fig. 2
and Table 2 summarizes their performance.

Table 2: Performance for the Tracking Experiment | $\|T_{K}\|_{F}^{2}$ | $\|T_{K}\|^{2}$ | Regret
---|---|---|---
Noncausal estimator | 0.39 | 1 | 0
Regret-optimal | 0.82 | 1.24 | 0.65
$H_{2}$ estimator | 0.77 | 1.4 | 1.02
$H_{\infty}$ estimator | 0.97 | 1 | 0.95

The time domain performance of the various filters is given in Fig. 3. We plot
the time-averaged estimation error energy as a function of time for the
$H_{2}$, $H_{\infty}$, and regret-optimal filters for two different types of
noise. One is the white Gaussian noise for which the $H_{2}$ filter is the
optimal, and one is an adversarial noise for which the $H_{\infty}$ filter is
the best. As can be seen, the regret-optimal filter has a performance that
interpolates nicely between these filters and achieves good performance across
a range of disturbances.

Figure 3: Time-averaged estimation error energy as a function of time for the
tracking example with two different disturbances. In the bottom three curves,
the state-space model is driven with Gaussian disturbances. In the top three
curves, it is driven with an adversarial disturbance.

##  5 Proof of Theorem 1

Recall that we aim to solve the sub-optimal problem

$\displaystyle
T^{\ast}_{\mathcal{K}}T_{\mathcal{K}}-T_{\mathcal{K}_{0}}^{\ast}T_{\mathcal{K}_{0}}\preceq\gamma^{2}I.$
(27)

By the Schur complement and the _Matrix inversion lemma_ (in its operator
form), we can write

$\displaystyle
T_{\mathcal{K}}(\gamma^{-2}I-\gamma^{-2}T_{\mathcal{K}_{0}}^{\ast}(I+\gamma^{-2}T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast})^{-1}\gamma^{-2}T_{\mathcal{K}_{0}})T^{\ast}_{\mathcal{K}}\preceq
I.\operatorname*{}$

It can now be shown that for any $\mathcal{K}$,

$\displaystyle T_{\mathcal{K}}T_{\mathcal{K}_{0}}^{\ast}$
$\displaystyle=\begin{pmatrix}\mathcal{L}-\mathcal{K}\mathcal{H}&-\mathcal{K}\end{pmatrix}\begin{pmatrix}I\\\
-\mathcal{H}\end{pmatrix}(I+\mathcal{H}^{\ast}\mathcal{H})^{-1}\mathcal{L}^{\ast}\operatorname*{}$
$\displaystyle=T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast}.$ (28)

Combining the simplified condition with (5) gives

$\displaystyle T_{\mathcal{K}}T_{\mathcal{K}}^{\ast}$
$\displaystyle\preceq\gamma^{2}I+\gamma^{-2}T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast}(I+\gamma^{-2}T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast})^{-1}T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast}\operatorname*{}$
$\displaystyle=\gamma^{2}I+T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast}(\gamma^{2}I+T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast})^{-1}T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast}.$
(29)

By the completion of square, we also have

$\displaystyle T_{\mathcal{K}}T_{\mathcal{K}}^{\ast}$
$\displaystyle=(\mathcal{K}-\mathcal{K}_{0})(I+\mathcal{H}\mathcal{H}^{\ast})(\mathcal{K}-\mathcal{K}_{0})^{\ast}+T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast}\operatorname*{}$

and rearranging the RHS of the condition gives

$\displaystyle\gamma^{2}I+T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast}(\gamma^{2}I+T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast})^{-1}T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast}-T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast}\operatorname*{}$
$\displaystyle=\gamma^{2}(I+\gamma^{-2}T_{\mathcal{K}_{0}}T_{\mathcal{K}_{0}}^{\ast})^{-1}.$
(30)

To conclude, the condition can be written as

$\displaystyle(\mathcal{K}-\mathcal{K}_{0})(I+\mathcal{H}\mathcal{H}^{\ast})(\mathcal{K}-\mathcal{K}_{0})^{\ast}\operatorname*{}$
$\displaystyle\ \ \
\preceq\gamma^{2}(I+\gamma^{-2}\mathcal{L}(I+\mathcal{H}^{\ast}\mathcal{H})^{-1}\mathcal{L}^{\ast})^{-1}$
(31)

By defining the canonical factorizations

$\displaystyle\Delta\Delta^{\ast}$
$\displaystyle=I+\mathcal{H}\mathcal{H}^{\ast}\operatorname*{}$
$\displaystyle\nabla_{\gamma}^{\ast}\nabla_{\gamma}$
$\displaystyle=\gamma^{-2}(I+\gamma^{-2}\mathcal{L}(I+\mathcal{H}^{\ast}\mathcal{H})^{-1}\mathcal{L}^{\ast}).$
(32)

and applying the Schur complement again gives that

$\displaystyle(\mathcal{K}\Delta-\mathcal{K}_{0}\Delta)^{\ast}\nabla_{\gamma}^{\ast}\nabla_{\gamma}(\mathcal{K}\Delta-\mathcal{K}_{0}\Delta)\preceq
I.$ (33)

Note that $\nabla_{\gamma}\mathcal{K}\Delta$ is a causal operator. Now, let
$\nabla_{\gamma}\mathcal{K}_{0}\Delta=\mathcal{S}+\mathcal{T}$ where
$\mathcal{S}$ is a causal operator and $\mathcal{T}$ is a strictly anticausal
operator (both operators depend on $\gamma$ implicitly). Then, if
$\mathcal{K}_{N}$ is a solution to the Nehari problem
$\|\mathcal{K}_{N}-\mathcal{T}\|\leq 1$, then a $\gamma$-optimal estimator is
given by $\nabla^{-1}(\mathcal{K}_{N}+\mathcal{S})\Delta^{-1}$.

##  6 Proof Outline of the State-Space

In this section, we present the main lemmas that constitute the explicit
solution for the state-space setting. As written above, there are three
technical lemmas to obtain a Nehari problem. The solution to the Nehari
problem is known and appears in the supplementary material. Proofs of the
technical lemmas appear in the supplementary material as well.

The first factorization appears as follows.

######  Lemma 3.

The transfer function $I+H(z)H^{\ast}(z^{-\ast})$ can be factored as

$\Delta(z)\Delta^{\ast}(z^{-\ast})=I+H(z)H^{\ast}(z^{-\ast})$

with

$\displaystyle\Delta(z)$
$\displaystyle=(I+H(zI-F)^{-1}K_{P})(I+HPH^{\ast})^{1/2}$ (34)

where $(I+HPH^{\ast})^{1/2}(I+HPH^{\ast})^{\ast/2}=I+HPH^{\ast}$,
$K_{P}=FPH^{\ast}(I+HPH^{\ast})^{-1}$ and $P$ is the stabilizing solution to
the Riccati equation

$\displaystyle P$
$\displaystyle=GG^{\ast}+FPF^{\ast}-FPH^{\ast}(I+HPH^{\ast})^{-1}HPF^{\ast}.\operatorname*{}$

Moreover, the transfer function $\Delta^{-1}(z)$ is bounded on $|z|\geq 1$.

In the second factorization, the expression we aim to factor is positive but
the order of its causal and anticausal components are in the reversed order.
This is resolved with an additional Riccati equation.

######  Lemma 4.

For any $\gamma>0$, the factorization
$\nabla_{\gamma}^{\ast}(z^{-\ast})\nabla_{\gamma}(z)=\gamma^{-2}(I+\gamma^{-2}L(z)(I+H^{\ast}(z^{-\ast})H(z))^{-1}L^{\ast}(z^{-\ast}))\operatorname*{}$
holds with

$\displaystyle\nabla_{\gamma}(z)$ $\displaystyle=R_{Q}^{-1/2}(I-L(zI-
F_{Q})^{-1}K_{Q}),$ (35)

where $R_{Q}=R_{Q}^{1/2}R_{Q}^{\ast/2}$, $Q$ is a solution to the Riccati
equation

$Q=-GR_{W}^{-1}G^{\ast}+F_{W}QF_{W}^{\ast}-K_{Q}R_{Q}K_{Q}^{\ast},$

and $K_{Q}=F_{W}QL^{\ast}R_{Q}^{-1}$ and $R_{Q}=\gamma^{2}I+LQL^{\ast}$ and
the closed-loop system $F_{Q}=F_{W}-K_{Q}L$. The constants $(F_{W},K_{W})$ are
obtained from the solution $W$ to the Riccati equation

$\displaystyle W$
$\displaystyle=H^{\ast}H+L_{\gamma}^{\ast}L_{\gamma}+F^{\ast}WF-
K_{W}^{\ast}R_{W}K_{W},$ (36)

and $K_{W}=R_{W}^{-1}G^{\ast}WF$ and $R_{W}=I+G^{\ast}WG$ with
$R_{W}=R_{W}^{\ast/2}R_{W}^{1/2}$ and $F_{W}=F-GK_{W}$.

The following lemma is the required decomposition.

######  Lemma 5.

The product of the transfer matrices
$\nabla_{\gamma}(z)L(z)H^{\ast}(z^{-\ast})\Delta^{-\ast}(z^{-\ast})$ can be
written as the sum of an anticausal transfer function

$\displaystyle T(z)$
$\displaystyle=R_{Q}^{-1/2}L(P\mspace{-3.0mu}-\mspace{-3.0mu}U)F_{P}^{\ast}\operatorname*{}$
$\displaystyle\
\cdot(z^{-1}I\mspace{-2.0mu}-\mspace{-2.0mu}F_{P}^{\ast})^{-1}H^{\ast}(I\mspace{-3.0mu}+\mspace{-3.0mu}HPH^{\ast})^{-\ast/2}.$
(37)

and a causal transfer function

$\displaystyle
S(z)=\nabla_{\gamma}(z)L[(zI-F)^{-1}F\mspace{-3.0mu}+\mspace{-3.0mu}I]PH^{\ast}(I\mspace{-3.0mu}+\mspace{-3.0mu}HPH^{\ast})^{-\ast/2}\operatorname*{}$
$\displaystyle\ -R_{Q}^{-1/2}L[(zI-
F_{Q})^{-1}F_{Q}+I]UH^{\ast}(I+HPH^{\ast})^{-\ast/2},\operatorname*{}$

where $U$ solves $U=K_{Q}LPF_{P}^{\ast}+F_{Q}UF_{P}^{\ast}$.

It can be shown that the first line of $S(z)$ is
$\nabla_{\gamma}(z)K_{H_{2}}(z)\Delta(z)$ where $K_{H_{2}}(z)$ is the optimal
$H_{2}$ estimator. By having the decomposition and the anticausal $T(z)$ in
part, we can apply the results of the Nahari problem to obtain Lemma 2.

## References

  * 1 R. E. Kalman (1960).  A New Approach to Linear Filtering and Prediction Problems.  Transactions of the ASME–Journal of Basic Engineering,dvances in Neural Information Processing Systems, vol. 82: 35–45.
  * 2 U. Shaked, Y. Theodor (1992).  ${H}_{\infty}$-optimal estimation: a tutorial.  In Proceedings of the 31st Conference on Decision and Control (CDC), vol. 2: 2278–2286.
  * 3 B. Hassibi, A. Sayed, T. Kailath (1999).  Indefinite-Quadratic estimation and control: A unified approach to H2 and H-infinity theories.  Society for Industrial and Applied Mathematics, vol. 16.
  * 4 Z. Nehari (1957).  On bounded bilinear forms.  Annals of Mathematics, vol. 16:153–162.
  * 5 B. Hassibi, A. Sayed, T. Kailath (1996).  $H_{\infty}$ optimality of the LMS algorithm.  IEEE Transactions on Signal Processing, vol. 44(2):267–280.
  * 6 E. Hazan, S. Kakade, K. Singh (2019).  The Nonstochastic Control Problem.  In ArXiv preprint:1911.12178.
  * 7 M. Simchowitz, K. Singh, E. Hazan (2020).  Improper Learning for Non-Stochastic Control.  In ArXiv preprint :2001.09254.
  * 8 Y. Abbasi-Yadkori, N. Lazic, C. Szepesv´ari (2019).  Model-free linear quadratic control via reduction to expert prediction.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , 3108–3117.
  * 9 Y. Abbasi-Yadkori,C. Szepesv´ari (2011).  Regret bounds for the adaptive control of linear quadratic systems.  In _Proceedings of the 24th Annual Conference on Learning Theory_ , 1-–26, 2011.