# Indirect Adaptive Optimal Control in the Presence of Input Saturation*

Sunbochen Tang and Anuradha M. Annaswamy *This work was supported by Ford-MIT
Alliance.Sunbochen Tang<EMAIL_ADDRESS>and Anuradha M. Annaswamy
<EMAIL_ADDRESS>are with the Department of Mechanical Engineering,
Massachusetts Institute of Technology, Cambridge, MA 02139, USA.

###### Abstract

In this paper, we propose a combined Magnitude Saturated Adaptive Control
(MSAC)-Model Predictive Control (MPC) approach to linear quadratic tracking
optimal control problems with parametric uncertainties and input saturation.
The proposed MSAC-MPC approach first focuses on a stable solution and
parameter estimation, and switches to MPC when parameter learning is
accomplished. We show that the MSAC, based on a high-order tuner, leads to
parameter convergence to true values while providing stability guarantees. We
also show that after switching to MPC, the optimality gap is well-defined and
proportional to the parameter estimation error. We demonstrate the
effectiveness of the proposed MSAC-MPC algorithm through a numerical example
based on a linear second-order, two input, unstable system.

##  I Introduction

Adaptive control is developed to address the presence of parametric
uncertainties. The term “adaptive” suggests that an adaptive controller can
modify its behavior in response to sudden changes in the dynamics of the
process [1], with emphasis on a real-time solution that achieves typical
control objectives including tracking a reference signal and stabilization.
Therefore, the performance is evaluated with present and instantaneous
properties, e.g., stability guarantees. In general, future behaviors such as
optimality of the system trajectory are not considered in the goals of
adaptive control systems.

Optimal control methods, in contrast, focus on finding control strategies to
minimize a specific cost function that the system is expected to incur over a
future time horizon. Other control goals such as stabilization and reference
tracking are often incorporated through specific cost function designs or
constrained optimization formulations. To achieve cost minimization, optimal
control strategies rely on having an accurate model, which requires knowledge
of both the model structure and parameters within.

When parametric uncertainties occur, an accurate model is no longer available,
and hence the problem becomes more complex, as one has to determine a
controller that both adapt to uncertainties and achieve optimality goals. We
propose a solution to this complex problem which combines Magnitude Saturated
Adaptive Control (MSAC) and Model Predictive Control (MPC) approaches. The
proposed MSAC-MPC controller first focuses on fast adaptation by leveraging
high-order tuner-based adaptation laws, which guarantees stability of the
closed-loop system, and ensures parameter learning in the presence of
persistent excitation [2]. Once parameter learning is accomplished, our
proposed controller shifts its focus to the optimality objective, which
utilizes a MPC structure to minimize cost using the estimated model learnt
during adaptation. In addition, the MSAC component in our proposed approach
incorporates control input magnitude saturation, which is equivalent to input
constraints commonly seen in optimal control problems. All discussions are
limited to linear time-invariant systems.

In the literature, approaches to solve adaptive optimal control problems can
be broadly categorized into direct and indirect adaptive optimal control
methods (see [3] for definitions). As introduced in [4], indirect adaptive
optimal control methods distinguish from their direct counterpart by
explicitly learning the unknown parameters. Indirect adaptive optimal control
approaches often utilize a robust optimal control framework. As an example,
the Adaptive MPC proposed in [5] iteratively updates estimates of the
uncertain parameters and their error bounds, and optimizes with respect to the
worst case using a robust MPC design [6]. Although this approach provides
proof of stability guarantees and achieves optimality goals, it accomplishes
these goals by solving a min-max optimization problem to ensure robustness
over all possible uncertain parameter values in a compact set, which is
computationally very expensive, thus less suitable for real-time decision
making tasks. In comparison, our proposed approach focuses on real-time
control and parameter learning during adaptation, therefore, reduces the
estimation error of uncertain parameters rapidly, and avoids the need for
invoking robust MPC.

Direct adaptive optimal control methods, which refer to methods that do not
learn uncertain parameters explicitly, are mainly developed based on online
approximate dynamic programming (ADP) algorithms such as value iteration and
policy iteration [7]. As an example, the computational adaptive optimal
control method proposed in [8] for linear systems with unknown matrices uses
policy iteration to iteratively solve the Riccati equation and consequently
find optimal control policy, instead of identifying system dynamics. Similar
approaches are developed in [9], [10], and [11]. Although these online
algorithms are shown to be very effective and provide stability guarantees,
most of them require an initial stable control policy, which is often
unavailable especially in the case where parametric uncertainties occur
online. Our proposed MSAC approach avoids this difficulty and ensures that the
proposed real-time controller will guarantee boundedness and a small tracking
error, without any requirement of an initial controller that guarantees
closed-loop stability.

The main contribution of this paper is that the proposed MSAC-MPC approach
provides real-time stable solution and parameter estimation during MSAC
adaptation, and achieves near-optimal solution using MPC after parameter
learning. Further, our approach is applicable to both finite-horizon and
infinite-horizon optimal control problems.

The remainder of this paper is organized as follows. In Section II, we
formulate the adaptive optimal control problem. In Section III, we introduce
the linear quadratic tracking problem and derive a structure of optimal
solutions under input constraints. In Section IV, we propose the MSAC-MPC
controller and present theoretical results including stability guarantees,
parameter learning, and optimality analysis. In Section V, we demonstrate the
proposed approach in a numerical example. The paper is concluded in Section
VI.

##  II Problem Formulation

Consider a linear system with parametric uncertainties,

$\dot{x}_{p}=A_{p}x_{p}+B_{p}\Lambda(B_{sat}(u))$ (1)

where $x_{p}\in\mathbb{R}^{n_{x}}$ is the state vector that is assumed to be
measurable, $u\in\mathbb{R}^{n_{u}}$ is the control input vector. The unknown
parameters are $A_{p}\in\mathbb{R}^{n_{x}\times n_{x}}$,
$\Lambda\in\mathbb{R}^{n_{u}\times n_{u}}$, and we assume $\Lambda$ is a
diagonal matrix with all entries positive. The function $B_{sat}(u)$
represents control input saturation by a ball centered at origin with a fixed
radius $u_{max}\in\mathbb{R}$, i.e.,

$B_{sat}(u)=\begin{cases}u,&\|u\|\leq u_{max}\\\
\frac{\|u\|}{u_{max}}u,&\|u\|>u_{max}\end{cases}$ (2)

The objective is to compute an optimal control law for the system in (1) such
that the following quadratic cost function is minimized over a prediction
horizon of length $T=t_{1}-t_{0}$,

$J=h(x_{p}(t_{1}))+\int_{t_{0}}^{t_{1}}l(x_{p},u,\tau)d\tau$ (3)

where $h(x)=(x-x_{d}(t_{1}))^{T}Q_{f}(x-x_{d}(t_{1})),Q_{f}=Q_{f}^{T}\succeq
0$ is the terminal cost matrix, and
$l(x,u,\tau)=(x(\tau)-x_{d}(\tau))^{T}Q(x(\tau)-x_{d}(\tau))+u(\tau)^{T}Ru(\tau),Q=Q^{T}\succeq
0,R=R^{T}\succ 0$ is the stage cost matrices. Note that the stage cost is
penalizing a tracking error, $e_{p}=x_{p}-x_{d}$, which forces the system to
track an exogenous signal $x_{d}(\tau)$.

In the optimal control framework, the input magnitude saturation in (2) is
equivalent to input constraints. Therefore, the overall problem we are
addressing in this paper can be formulated as a linear quadratic tracking
(LQT) problem with parametric uncertainties in system dynamics,

$\displaystyle\min_{u(\tau)}J$
$\displaystyle=h(x_{p}(t_{1}))+\int_{t_{0}}^{t_{1}}l(x_{p},u,\tau)d\tau$ (4a)
subject to $\displaystyle x(t_{0})=x_{0}$ (4b)
$\displaystyle\dot{x}_{p}(\tau)=A_{p}x_{p}(\tau)+B_{p}\Lambda(u(\tau))\quad\forall\tau\in[t_{0},t_{1}]$
(4c) $\displaystyle u(\tau)\in U,\quad\forall\tau\in[t_{0},t_{1}]$ (4d)
$\displaystyle U=\\{u\in\mathbb{R}^{n_{u}}:\|u\|\leq u_{max}\\}$ (4e)

Two assumptions are made to simplify the problem:

###### Assumption 1

$R$ is a diagonal matrix with identical entries, i.e., $\exists R_{u}>0$ such
that $R=R_{u}I_{n_{u}\times n_{u}}$.

###### Assumption 2

The exogenous signal $x_{d}(t)$ that is desired to be tracked and its
derivative $\dot{x}_{d}(t)$ are known.

The main difficulty is that directly solving the optimization problem when
$A_{p}$ and $\Lambda$ are unknown in the dynamics constraints is intractable.
In addition, LQT problems with input constraints generally do not have an
explicit solution because the solution involves exogenous signal $x_{d}(t)$,
unlike linear quadratic regulation (LQR) problems where stabilization is the
goal.

The solution we propose, termed MSAC-MPC, proceeds thus. First, we propose a
magnitude-saturation constrained adaptive controller (MSAC), where the
controller guarantees bounded solutions and persistent excitation of the
underlying regressor guarantees learning of the parameters. The resulting
parameter estimates are then used to switch to an MPC controller, and the
overall cost is evaluated in terms of the residual parameter error after a
finite time. Numerical examples are provided to illustrate the nature of the
overall MSAC-MPC controller.

##  III Linear Quadratic Tracking Control

We first address the LQT problem in (4a)-(4e) when $A_{p}$ and $\Lambda$ are
known. When there is no control input constraint, i.e.,
$U=\mathbb{R}^{n_{u}}$, the unconstrained optimal controller
$u_{uc}^{*}(\tau)$ assumes a linear feedback form, and the corresponding
optimal cost-to-go function is quadratic in $x(\tau)$, [12]

$\displaystyle u_{uc}^{*}(\tau)$
$\displaystyle=-R^{-1}(B_{p}\Lambda)^{T}(S_{1}^{uc}(\tau)+S_{2}^{uc}(\tau)x(\tau))$
(5a) $\displaystyle V_{uc}^{*}(x,\tau)$
$\displaystyle=x(\tau)^{T}S_{2}^{uc}(\tau)x(\tau)+2x(\tau)^{T}S_{1}^{uc}(\tau)+S_{0}^{uc}(\tau)$
(5b)

###  III-A Linear feedback control

In this subsection, we show the cost-to-go function associated with (4a)-(4e)
under any linear feedback control is quadratic. We also provide a bound on the
cost-to-go function in terms of error bounds on the control parameters.
Following Lemma 1 in [10], a cost-to-go function $V^{\pi}$ associated with a
fixed feedback control policy $u(\tau)=\pi(x(\tau))$ can be found by solving
the following equation,

$\displaystyle l(x,u,\tau)+\frac{\partial V^{\pi}}{\partial
x}(A_{p}x+B_{p}\Lambda u)+\frac{\partial V^{\pi}}{\partial\tau}=0$ (6)

In the case where $\pi(x(\tau))$ is a linear feedback control policy, by
solving (6), we have the following proposition.

###### Proposition 1

Under any linear feedback control law
$u(\tau)=\pi(x,\tau)=K_{1}^{\pi}(\tau)x(\tau)+K_{0}^{\pi}(\tau)$, the cost-to-
go function is quadratic,
$V^{\pi}=x^{T}S_{2}^{\pi}x+2x^{T}S_{1}^{\pi}+S_{0}^{\pi}$.

$\displaystyle\dot{S}_{2}^{\pi}$
$\displaystyle=-Q-S_{2}^{\pi}(A_{p}+B_{p}\Lambda
K_{1}^{\pi})-(A_{p}+B_{p}\Lambda K_{1}^{\pi})^{T}{S_{2}^{\pi}}^{T}$
$\displaystyle-{K_{1}^{\pi}}^{T}RK_{1}^{\pi}{}$ (7a)
$\displaystyle\dot{S}_{1}^{\pi}$
$\displaystyle=Qx_{d}-[S_{2}^{\pi}K_{0}^{\pi}+(A_{p}+B_{p}\Lambda
K_{1}^{\pi})^{T}{S_{1}^{\pi}}^{T}+{K_{1}^{\pi}}^{T}RK_{0}^{\pi}]{}$ (7b)
$\displaystyle\dot{S}_{0}^{\pi}$
$\displaystyle=-x_{d}^{T}Qx_{d}-2S_{1}^{\pi}K_{0}^{\pi}-{K_{0}^{\pi}}^{T}RK_{0}^{\pi}{}$
(7c)

with boundary conditions,

$S_{2}^{\pi}(t_{1})=Q_{f},S_{1}^{\pi}(t_{1})=-Q_{f}x_{d}(t_{1}),S_{0}^{\pi}(t_{1})=x_{d}^{T}Q_{f}x_{d}$

###### Remark 1

When $K_{1}^{\pi}=-R^{-1}(B_{p}\Lambda)^{T}S_{2}^{uc}$ and
$K_{0}^{\pi}=-R^{-1}B^{T}S_{1}^{uc}$, the unconstrained optimal control and
optimal cost-to-go function are recovered, i.e., $u=u^{*}_{uc}$ and
$V^{\pi}=V_{uc}^{*}$.

Based on the results in Proposition 1, for two linear feedback control laws
with similar gain matrices, the resulting cost-to-go functions will also be
close in their values.

###### Proposition 2

For any two linear feedback laws
$\pi_{i}(x,\tau)=K_{1}^{\pi_{i}}(\tau)x(\tau)+K_{0}^{\pi_{i}}(\tau)$, $i=1,2$,
if there exists $\delta>0$, such that
$\max_{j}\\{\sup_{\tau\in[t_{0},t_{1}]}\|K_{j}^{\pi_{1}}-K_{j}^{\pi_{2}}\|\\}\leq\delta$,
then the corresponding cost-to-go functions, defined by (7a)-(7c),
$V^{\pi_{1}},V^{\pi_{2}}$, satisfy $|V^{\pi_{1}}-V^{\pi_{2}}|\leq
O(\delta^{2})$.

Quadratic coefficient matrices, $S_{j}^{\pi}$, are defined by differential
equations in (7a)-(7c). It is not difficult to see that $S_{2}^{\pi}$ is a
quadratic function of $K_{1}^{\pi}$, $S_{1}^{\pi}$ is a quadratic function of
$K_{1}^{\pi},K_{0}^{\pi}$, and $S_{0}^{\pi}$ is a quadratic function of
$K_{0}^{\pi}$. In addition, $V^{\pi}$ is a linear function of
$S_{2}^{\pi},S_{1}^{\pi},S_{0}^{\pi}$, therefore, a quadratic function of
$K_{1}^{\pi},K_{0}^{\pi}$, which implies,

$|V^{\pi_{1}}-V^{\pi_{2}}|=O(\max_{j=0,1}\\{\sup_{\tau\in[t_{0},t_{1}]}\|K_{j}^{\pi_{1}}-K_{j}^{\pi_{2}}\|\\})=O(\delta^{2})$

###  III-B Input Constrained LQT

Now we consider the LQT problem with input constraints described in (4a)-(4e)
with $U\subsetneqq\mathbb{R}^{n_{u}}$. In the following theorem, we show that
the constrained optimal control input $u^{*}$ is the point in admissible set
$U$ closest to unconstrained optimal control $u_{uc}^{*}$ under a distance
metric defined by $R$, i.e. $d_{R}(x,y)=(x-y)^{T}R(x-y)$.

###### Theorem 1

If $u^{*}$ is an optimal solution to (4a)-(4e), then $u^{*}$ satisfies
$u^{*}=argmin_{u\in U}(u-u_{uc}^{*})^{T}R(u-u_{uc}^{*})$.

###### Proof:

Let $\mathcal{H}$ be the Hamiltonian of (4a)-(4e),

$\mathcal{H}=p_{0}l(x(\tau),u(\tau),\tau)+p(\tau)^{T}(A_{p}x(\tau)+B_{p}\Lambda
u(\tau))$

where $p_{0}\in{0,1}$ is a binary variable constant in $\tau$,
$p(\tau)\in\mathbb{R}^{n_{x}}$ is the Lagrange multiplier. Since there is no
additional equality constraint other than system dynamics, $p_{0}=1$ [13].

Using Pontryagin’s Maximum Principle (PMP), by minimizing $\mathcal{H}$ with
resepct to $u$ subject to input constraint $u\in U$, the optimal control input
under constraint $u^{*}$ is

$\displaystyle u^{*}=argmin_{u\in
U}{u(\tau)^{T}Ru(\tau)+p(\tau)^{T}B_{p}\Lambda u(\tau)}$

Note that for the reduced quadratic cost, unconstrained optimal solution is
$u_{uc}^{*}=-\frac{1}{2}R^{-1}(B_{p}\Lambda)^{T}p$, which satisfies

$\displaystyle u^{T}Ru+p^{T}B_{p}\Lambda u$
$\displaystyle=(u-u_{uc}^{*})^{T}R(u-u_{uc}^{*})-{u_{uc}^{*}}^{T}Ru_{uc}^{*}$

Since $u_{uc}^{*}$ does not depend on $u$ explicitly, we have

$u^{*}=argmin_{u\in U}(u-u_{uc}^{*})^{T}R(u-u_{uc}^{*})$

The Lagrange multipliers $p(\tau)$ are defined by the following differential
equations and boundary conditions, which are the adjoint equations and
transversality conditions in PMP,

$\displaystyle\dot{p}(\tau)$
$\displaystyle=-\nabla_{x}\mathcal{H}=p(\tau)^{T}A_{p}-2Q(x(\tau)-x_{d}(\tau))$
$\displaystyle p(t_{1})$ $\displaystyle=2Q(x(t_{1})-x_{d}(t_{1}))$
$\displaystyle 0$
$\displaystyle=l(t_{1})+p(t_{1})^{T}(A_{p}x(t_{1})+B_{p}\Lambda u(t_{1}))$

∎

###### Corollary 1

Under Assumption 1, and the admissible set $U$ is a ball around origin, i.e.
$U=\\{u\in\mathbb{R}^{n_{u}}:\|u\|^{2}\leq u_{max}\\},u_{max}>0$, $u^{*}$ can
be written as $u^{*}=u_{uc}^{*}\frac{u_{max}}{\|u_{uc}^{*}\|}$, which is a
linear feedback controller.

###### Proof:

By Theorem 1, when $R=R_{u}I_{n_{u}\times n_{u}}$,

$u^{*}=argmin_{u\in U}R_{u}\|u-u_{uc}^{*}\|^{2}=argmin_{u\in
U}\|u-u_{uc}^{*}\|^{2}$

If $U$ is a ball of radius $u_{max}$ around the origin, then the closest point
to $u^{*}$ is the projection of $u^{*}$ on the outside sphere, therefore,
$u^{*}=u_{uc}^{*}\frac{u_{max}}{\|u_{uc}^{*}\|}$. ∎

##  IV MSAC-MPC: Adapt, Learn, Optimize

In the previous section, we have established that the optimal solution to a
input-constrained LQT problem with known system matrices (4a)-(4e) is a linear
feedback controller, with the assumption that the parameters were known. It
should be noted that these parameters were directly used in the LQT control
design. Now we address the input-constrained LQT problem with parametric
uncertainties. As illustrated in Figure 1, the proposed MSAC-MPC controller
first adapts over $[0,T_{adap}]$ and then switches to an MPC controller.

The main difficulty in extending the approach described in Section III lies in
computing optimal control while parametric uncertainties are present in the
system dynamics. Adaptive MPC approaches, e.g., in [5], propose to estimate
the unknown parameters based on state measurements while computing optimal
control using currently estimated parameter values. While these approaches
provide stability guarantees through robust MPC designs, the resulting min-max
optimization problems are computationally quite burdensome. From a real-time
control perspective, when computation power is limited and control input needs
to be determined within a short time, the proposed MSAC-MPC controller may
prove to be attractive. During $[t_{0},t_{0}+T_{adap}]$, our controller
focuses primarily on a stable solution and on learning the unknown parameters.
After this finite time, we show that one can switch to MPC with a well-defined
optimality gap that is proportional to the parameter error that is present for
$t\geq t_{0}+T_{adap}$.

Figure 1: A diagram of MSAC-MPC Algorithm ($t_{0}$ is assumed to be zero).

###  IV-A MSAC: Adapt and Learn

The MSAC controller in this paper follows the adaptive control structure
proposed in [14] for multi-input systems, but replaces the parameter
adaptation by a high-order tuner in [2]. The motivation behind such a
combination is that we explicitly accommodate input constraints and guarantee
boundedness as in [14] while ensuring that the speed of convergence is fast
when compared to [14], as in [2].

####  IV-A1 Adaptive control design

As in all adaptive control designs [3], a known reference system is chosen as,

$\dot{x}_{m}=A_{m}x_{m}+B_{m}r$ (8)

where $x_{m}\in\mathbb{R}^{n_{x}}$, $r\in\mathbb{R}^{n_{u}}$ is a bounded
reference input satisfying $\|r\|\leq r_{max}$, and $A_{m}$ is a Hurwitz
matrix, and $B_{m}$ is full column rank.

The magnitude saturated multi-input model reference adaptive controllrer
(MSAC) is defined as (see [14] for details),

$\displaystyle
u=\widehat{\Theta}\Phi,\quad\widehat{\Theta}=[\hat{K}_{x},\hat{K}_{r}],\quad\Phi=[x_{p}^{T},r^{T}]^{T}$
(9)

We assume there exists an ideal matrix $K_{x}\in\mathbb{R}^{n_{u}\times
n_{x}}$ and an ideal vector $K_{r}\in\mathbb{R}^{n_{u}\times n_{u}}$
corresponding to the unknown parameters in (1), which satisfy

$\displaystyle A_{p}+B_{p}\Lambda K_{x}=A_{m},\quad B_{p}\Lambda K_{r}$
$\displaystyle=B_{m}$

The parameter estimation errors are defined as,

$\tilde{K}_{x}=\hat{K}_{x}-K_{x},\quad\tilde{K}_{r}=\hat{K}_{r}-K_{r},\quad\widetilde{\Theta}=[\tilde{K}_{x},\tilde{K}_{r}]$

Let $\Delta u=B_{sat}(u)-u$. The closed-loop dynamics is,

$\dot{x}_{p}=(A_{p}+B_{p}\Lambda K_{x})x_{p}+B_{p}\Lambda
K_{r}r+B_{p}\Lambda(\widetilde{\Theta}\Phi+\Delta u)$ (10)

By subtracting (8) from (1) and defining error $e=x_{p}-x_{m}$, the closed-
loop error dynamics is obtained as,

$\dot{e}=A_{m}e+B_{p}\Lambda(\widetilde{\Theta}\Phi+\Delta u)$ (11)

To address the nonlinear disturbance $\Delta u$ introduced by the input
magnitude saturation, we introduce an auxiliary error $e_{\Delta}$ generated
by the following dynamics,

$\displaystyle\dot{e}_{\Delta}=A_{m}e_{\Delta}+B_{p}diag(\hat{\lambda})\Delta
u$

where $\hat{\lambda}\in\mathbb{R}^{n_{u}}$ is a vector that estimates the
unknown diagonal entries of $\Lambda$. We also denote the diagonal vector of
$\Lambda$ as $\lambda$, and define $\tilde{\lambda}=\hat{\lambda}-\lambda$.

Define $e_{u}=e-e_{\Delta}$, the augmented error $e_{u}$ is used to establish
the stability results, whose error dynamics is,

$\displaystyle\dot{e}_{u}=A_{m}e_{u}+B_{p}[\Lambda\widetilde{\Theta},diag(\tilde{\lambda})][\Phi^{T}\Delta
u^{T}]^{T}$ (12)

Let $\Theta_{a}=[{\Theta},\Lambda]$,
$\widehat{\Theta}_{a}=[\widehat{\Theta},diag(\hat{\lambda})]$,
$\Phi_{a}=[\Phi^{T},-\Delta_{u}^{T}]^{T}$. The High-order Tuner-based
Adaptation laws are chosen as,

$\displaystyle\dot{\Xi}_{a}$ $\displaystyle=-\gamma
B_{p}^{T}Pe_{u}\Phi_{a}^{T}$ (13a) $\displaystyle\dot{\widehat{\Theta}}_{a}$
$\displaystyle=-\beta(\widehat{\Theta}_{a}-\Xi_{a})\mathcal{N}_{t}$ (13b)
$\displaystyle\mathcal{N}_{t}$
$\displaystyle=1+\mu\Phi_{a}^{T}\Phi_{a},\quad\mu\geq\frac{2\gamma}{\beta}\|PB_{p}\|^{2}_{F}$
(13c)

where $P$ is the solution to Lyapunov equation, $A_{m}^{T}P+PA_{m}=-Q$ and $Q$
is a positive definite matrix.

The goal of the adaptive controller is to show that the adaptation laws in
(13a)-(13c) guarantee that the tracking error $e$ remains small and that all
signals in the closed-loop system are bounded. Once this is accomplished,
persistent excitation arguments are to be used to ensure that
$\widehat{\Theta}_{a}$ converges to the true value. We now link the
convergence of the error $e$ to the tracking of the desired signal $x_{d}$ by
specifying the reference input $r(t)$ in the reference model as follows.

Using Assumption 2, we choose the reference input $r$ as

$r=(B_{m}^{T}B_{m})^{-1}B_{m}^{T}(-A_{m}x_{d}+\dot{x}_{d})$ (14)

Let $e_{m}=x_{m}-x_{d}$. Since the error dynamics is $\dot{e}_{m}=A_{m}e_{m}$,
and $A_{m}$ is Hurwitz, we have that $\|e_{m}(t)\|\to 0$ as $t\to\infty$.

Now that we have a complete MSAC design described in (9), (12), (13a)-(13c),
and (14), we are ready to state stability results and parameter learning
results.

####  IV-A2 Stability results

Let $\widetilde{\Theta}_{a}=\widehat{\Theta}_{a}-\Theta_{a}$. Consider a
Lyapunov function candidate,

$\displaystyle V$
$\displaystyle=e_{u}^{T}Pe_{u}+\frac{1}{\gamma}Tr\left[(\Xi_{a}-\Theta_{a})^{T}\Lambda_{a}^{T}(\Xi_{a}-\Theta_{a})\right]$
$\displaystyle+\frac{1}{\gamma}Tr\left[(\widehat{\Theta}_{a}-\Xi_{a})^{T}\Lambda_{a}^{T}(\widehat{\Theta}_{a}-\Xi_{a})\right]{}$
(15)

where $\Lambda_{a}=\begin{bmatrix}\Lambda&0\\\ 0&I_{n_{u}\times
n_{u}}\end{bmatrix}$ is used for compact notation.

It follows that

$\displaystyle\dot{V}$
$\displaystyle=e_{u}^{T}(PA_{m}+A_{m}^{T}P)e_{u}+2e_{u}^{T}PB_{p}[\Lambda\widetilde{\Theta}\Phi-
diag(\tilde{\lambda})\Delta u]$ $\displaystyle-
Tr[(\Xi_{a}-\Theta_{a})^{T}(\Lambda_{a}+\Lambda_{a}^{T})B_{p}^{T}Pe_{u}\Phi_{a}^{T}]$
$\displaystyle-\frac{\beta}{\gamma}Tr\left[(\widehat{\Theta}_{a}-\Xi_{a})^{T}(\Lambda_{a}+\Lambda_{a}^{T})(\widehat{\Theta}_{a}-\Xi_{a})\right]\mathcal{N}_{t}$
$\displaystyle+Tr\left[(\widehat{\Theta}_{a}-\Xi_{a})^{T}(\Lambda_{a}+\Lambda_{a}^{T})B_{p}^{T}Pe_{u}\Phi_{a}^{T}\right]$
$\displaystyle=-e_{u}^{T}Qe_{u}+2e_{u}^{T}PB_{p}[\Lambda\widetilde{\Theta}\Phi-
diag(\tilde{\lambda})\Delta u]$ $\displaystyle-
Tr\left[(\Xi-\Theta)^{T}(\Lambda+\Lambda^{T})B_{p}^{T}Pe_{u}\Phi^{T}\right]$
$\displaystyle+2Tr\left[(diag(\lambda_{\epsilon})-diag(\hat{\lambda}))^{T}B_{p}^{T}Pe_{u}\Delta
u^{T}\right]$
$\displaystyle-\frac{\beta}{\gamma}\mathcal{N}_{t}[Tr[(\widehat{\Theta}-\Xi)^{T}(\Lambda+\Lambda^{T})(\widehat{\Theta}-\Xi)]$
$\displaystyle+2Tr(diag(\hat{\lambda})-diag(\lambda_{\epsilon}))^{T}(diag(\hat{\lambda})-diag(\lambda_{\epsilon}))]$
$\displaystyle+Tr[(\widehat{\Theta}-\Xi)^{T}(\Lambda+\Lambda^{T})B_{p}Pe_{u}\Phi^{T}]$
$\displaystyle+2Tr[(diag(\hat{\lambda})-diag(\lambda_{\epsilon}))^{T}B_{p}^{T}Pe_{u}(-\Delta
u)^{T}]$
$\displaystyle=-e_{u}^{T}Qe_{u}+4e_{u}^{T}PB_{p}\Lambda(\widehat{\Theta}-\Xi)\Phi$
$\displaystyle-\frac{\beta}{\gamma}(1+\mu\|\Phi\|^{2})Tr[(\widehat{\Theta}-\Xi)^{T}(\Lambda+\Lambda^{T})(\widehat{\Theta}-\Xi)]$
$\displaystyle-4e_{u}^{T}PB_{p}(diag(\hat{\lambda})-diag(\lambda_{\epsilon}))\Delta
u-\frac{\beta}{\gamma}(1+\mu\|\Delta u\|^{2})$ $\displaystyle\cdot
2Tr[(diag(\hat{\lambda})-diag(\lambda_{\epsilon}))^{T}(diag(\hat{\lambda})-diag(\lambda_{\epsilon}))]$
$\displaystyle\leq-2\|e_{u}\|^{2}+4\|e_{u}\|\|PB_{p}\Lambda(\widehat{\Theta}-\Xi)\|_{F}\|\Phi\|$
$\displaystyle-\frac{2\beta}{\gamma}(1+\frac{2\gamma}{\beta}\|PB\|_{F}^{2}\|\Phi\|^{2})Tr\left[(\widehat{\Theta}-\Xi)^{T}\Omega^{T}\Omega(\widehat{\Theta}-\Xi)\right]$
$\displaystyle+4\|e_{u}\|\|PB_{p}(diag(\hat{\lambda})-diag(\lambda_{\epsilon}))\|_{F}\|\Delta
u\|$
$\displaystyle-\frac{2\beta}{\gamma}(1+\frac{2\gamma}{\beta}\|PB_{p}\|^{2}_{F}\|\Delta
u\|^{2})$ $\displaystyle\cdot
Tr[(diag(\hat{\lambda})-diag(\lambda_{\epsilon}))^{T}(diag(\hat{\lambda})-diag(\lambda_{\epsilon}))]$
$\displaystyle=-\left[\|e_{u}\|-2\|PB_{p}\|_{2}\|(\widehat{\Theta}-\Xi)^{T}\Omega\|_{F}\|\Phi\|\right]^{2}$
$\displaystyle-\left[\|e_{u}\|-2\|PB_{p}\|_{2}\|diag(\hat{\lambda})-diag(\lambda_{\epsilon})\|_{F}\right]^{2}\leq
0$

Therefore, $e_{u},\widehat{\Theta}_{a},\Xi_{a}\in\mathcal{L}_{\infty}$. Define
$K_{max}=\max\|\widetilde{\Theta}_{a}\|$,

$K_{max}\geq\max\left(\sup\|\tilde{K}_{x}\|,\sup\|\tilde{K}_{r}\|,\sup\|\tilde{\lambda}\|\right)$

We define the following variables for compact notations in the error bound
definition:

$\displaystyle q_{min}$ $\displaystyle=\min eig(Q),p_{min}=\min
eig(P),p_{max}=\max eig(P),$ $\displaystyle\rho$
$\displaystyle=\sqrt{\frac{p_{max}}{p_{min}}},\bar{u}_{min}=\min_{i}(u_{max,i}),\bar{u}_{max}=\max_{i}(u_{max,i}),$
$\displaystyle P_{B}$
$\displaystyle=\|PB_{p}\Lambda\|,\lambda_{min}=\min(eig(\Lambda))$

Additionally, the following variable definitions are used in the main
stability result, Theorem 2.

$\displaystyle\beta$
$\displaystyle=\frac{P_{B}K_{max}}{\|K_{x}^{*}\|+K_{max}},a_{0}=\frac{\bar{u}_{min}K_{max}}{\|K_{x}^{*}\|+K_{max}}$
$\displaystyle x_{min}$
$\displaystyle=\frac{3P_{B}K_{max}(r_{max}+1)+3P_{B}\|K_{r}^{*}\|r_{max}}{q_{min}-3P_{B}K_{max}}$
$\displaystyle+\frac{2P_{B}\bar{u}_{max}}{q_{min}-3P_{B}K_{max}}$
$\displaystyle x_{max}$
$\displaystyle=\frac{P_{B}a_{0}}{|q_{min}-2P_{B}\|K_{x}^{*}\||}$
$\displaystyle\bar{K}_{max}$
$\displaystyle=\frac{q_{min}-\frac{\rho}{a_{0}}\left(3\|K_{r}^{*}\|r_{max}+2\bar{u}_{max}\right)|q_{min}}{3P_{B}+\frac{3\rho}{a_{0}}(r_{max}+1)|q_{min}-2P_{B}\|K_{x}^{*}\||}$
$\displaystyle-\frac{2P_{B}\|K_{x}^{*}\||}{3P_{B}+\frac{3\rho}{a_{0}}(r_{max}+1)|q_{min}-2P_{B}\|K_{x}^{*}\||}$

where all vector norms are 2-norm and the matrix norm in $P_{B}$ is the
induced matrix norm, which implies $\|PB_{p}\Lambda x\|\leq P_{B}\|x\|$.

###### Theorem 2

For the closed-loop system with adaptive controller and adaptation laws
described in (1) (9), and (13a)-(13c), $x(t)$ has bounded trajectories for
$t\geq t_{0}$ if

  1. 1.

$\|x(t_{0})\|<\frac{x_{max}}{\rho}$

  2. 2.

$\sqrt{V(t_{0})}<\bar{K}_{max}\sqrt{\frac{\lambda_{min}}{\gamma_{max}}}$

Moreover, $\|x(t)\|<x_{max},\forall t\geq t_{0}$, and the error variable is of
the same order as the difference between saturated input $B_{sat}(u(t))$ and
the unsaturated $u(t)$, i.e.,

$\|e\|=\|x_{p}-x_{m}\|=O\left[\sup_{\tau\leq t}\|\Delta u(\tau)\|\right]$

The proof is very similar to the one for Theorem 1 in [14]. Note that in the
proof especially parts related to the error bounds, adaptation laws are not
directly involved, instead, parameter estimation error upper bound $K_{max}$
is used to bound the error term. The boundedness of $K_{max}$ relies on
$\widetilde{\Theta}_{a}\in\mathcal{L}_{\infty}$, which is proved by showing
the candidate in (15) is indeed a Lyapunov function.

It should be noted that the stability results hold for any initial values of
control gain matrix estimates $\hat{K}_{1}(t_{0}),\hat{K}_{0}(t_{0})$. The
main advantage of the MSAC is that it can provide stable solutions without any
prior knowledge of unknown parameters, in comparison to policy iteration
methods such as [8] where an initial stable controller is assumed to be
available, which requires at least partial information about the unknown
parameters.

####  IV-A3 Parameter learning

Now that boundedness and asymptotic properties of the tracking error are
established we proceed to learning of the unknown parameters. In order to
learn $\Theta_{a}$, the regressor $\Phi_{a}$ must satisfy persistent
excitation properties. We now introduce definitions of persistent excitation
and the conditions for parameter learning.

###### Definition 1

A bounded function $\Phi:[t_{0},\infty)\to\mathbb{R}^{n_{u}}$ is persistently
exciting (PE) if there exists $T>0$ and $\alpha>0$ such that

$\int_{t}^{t+T}\Phi(\tau)\Phi^{T}(\tau)d\tau\geq\alpha I,\quad\forall t\geq
t_{0}.$ (17)

If $\|\dot{\Phi}(t)\|$ is bounded for all $t$, equivalently, an alternative
definition can be given as follows,

###### Definition 2

$\Phi$ is PE if there exists an $\epsilon>0$, a $t_{2}$ and a sub-interval
$[t_{2},t_{2}+\delta_{0}]\subset[t,t+T]$ such that for all unit vectors
$\omega\in\mathbb{R}^{n_{u}}$

$\frac{1}{T}\bigg{\lvert}\int_{t_{2}}^{t_{2}+\delta_{0}}\Phi(\tau)^{T}\omega
d\tau\bigg{\rvert}\geq\epsilon,\quad\forall t\geq t_{0}$ (18)

###### Lemma 1

Let $\epsilon$ and $\delta$ be given positive numbers. There exists
$T=T(\epsilon,\delta)$ such that if
$z(t)=[e_{u}(t)^{T},\widetilde{\Theta}_{a}(t)^{T}]^{T}$ is a solution with
$\|z(t_{1})\|\leq\epsilon_{1}$, then there exists some $t_{2}\in[t,t+T]$ such
that $\|\widetilde{\Theta}_{a}(t_{2})\|\leq\delta$.

###### Theorem 3

If $\Phi_{a}(t)$ satisfies the persistent excitation property in (18), then
the origin in (13), $e_{u}=0,\Xi_{a}=0,\Theta_{a}=0$, is uniformly
asymptotically stable.

Under the assumption that $\Phi_{a}(t)$ satisfies persistent excitation
property, Lemma 1 and Theorem 3 state that arbitrary accuracy of estimated
parameters can be achieved in finite time. Given a positive estimation
accuracy $\delta$, we can always find $t_{2}$ such that
$\|\widetilde{\Theta}_{a}\|\leq\delta$. This implies that given a $\delta$,
there exists a large enough $T_{adap}$ such that,
$\|\widetilde{\Theta}_{a}(T_{adap})\|\leq\delta$ is satisfied. We refer the
readers to [15], where detailed proofs can be found. As the underlying
asymptotic convergence is not necessarily exponential, an explicit bound on
$T_{adap}$ that leads to a desired accuracy $\delta$ is yet to be defined.
Non-asymptotic tools [16] may need to be examined for this purpose.

###  IV-B MPC: Optimize after parameter learning

Now that the unknown parameter values have been estimated with accuracy
$\delta>0$, we can proceed to replace the unknown parameters in the optimal
control problem considered in Section III with the parameter estimates. More
precisely, at $t=t_{0}+T_{adap}$, we compute the plant parameter estimates as:

$\hat{A}_{p}=A_{m}-B_{p}\hat{\Lambda}\hat{K}_{x}(t_{0}+T_{adap}),\hat{\Lambda}=diag(\hat{\lambda}(t_{0}+T_{adap}))$
(19)

Since there is still some discrepancy between unknown parameters and their
estimates, we choose a model predictive control (MPC) design to compute an
approximate optimal control, $u_{MPC}$. This carried out at every sampling
time instant $t_{i}$ as follows [17].

$\displaystyle\min_{u(\tau)}J$
$\displaystyle=h(x_{p}(t_{i}+T))+\int_{t_{i}}^{t_{i}+T}l(x_{p},u,\tau)d\tau$
(20a) subject to $\displaystyle x(t_{0})=x_{0}$ (20b)
$\displaystyle\dot{x}_{p}(\tau)=\hat{A}_{p}x_{p}(\tau)+B_{p}\widehat{\Lambda}(u(\tau)),\forall\tau\in[t_{i},t_{i}+T]$
(20c) $\displaystyle u(\tau)\in U,\quad\forall\tau\in[t_{i},t_{i}+T]$ (20d)
$\displaystyle U=\\{u\in\mathbb{R}^{n_{u}}:\|u\|\leq u_{max}\\}$ (20e)

We denote $u^{AOC}(\tau),\tau\in[t_{i},t_{i}+T]$ as the solution to (20) and
denote $u^{MPC}(\tau)=u^{AOC}(\tau),\forall\tau\in[t_{i},t_{i+1}]$. We denote
the corresponding cost-to-go as $V^{MPC}$. It is also assumed that $t_{1}\geq
t_{0}+T_{adap}$.

Under Assumption 1, by Corollary 1, $u^{MPC}$ is a linear feedback controller,
denoted as $u^{MPC}=\hat{K}_{1}x_{p}+\hat{K}_{0}$. It should be noted that the
parameters of $u^{MPC}$, $\hat{K}_{1}$ and $\hat{K}_{0}$ are directly
dependent on the estimated plant parameters $\hat{A}_{p}$ and $\Lambda$.
Similarly, denoting the optimal solution of the problem in (4a)-(4e) as
$u^{*}$, it is easy to infer from Corollary 1, again, that
$u^{*}=K_{1}^{*}x_{p}+K_{0}^{*}$.

Since $\|\widehat{\Theta}_{a}\|\leq\delta$,
$\hat{\Theta}_{a}=[\hat{K}_{x},\hat{K}_{r},\widehat{\Lambda}]$, by (19),

$\|\hat{A}_{p}-A_{p}\|=O(\delta),\quad\|\widehat{\Lambda}-\Lambda\|\leq\delta$

Note that

$\|\hat{K}_{1}-K_{1}^{*}\|=O(\delta),\|\hat{K}_{0}-K_{0}^{*}\|=O(\delta)$

Using Proposition 2, it follows that the deviation in the corresponding cost-
to-go functions is given by

$|V^{MPC}-V^{*}|\leq O(\delta^{2})$ (21)

In conclusion, the discrepancy between the cost associated with system
trajectories generated using $u^{MPC}$ and the optimal cost is quantified in
(21), and it summarizes the main advantage of the proposed MSAC-MPC
controller. That is, the MSAC-MPC controller results in a cost that differs
from the optimal cost by an order of magnitude comparable to parameter error
$\delta$ and is of the order $\delta^{2}$. This optimal cost is evaluated
after a time $T_{adap}$ elapses after $t_{0}$. The benefit of the proposed
method is the reduction of the computational burden over
$[t_{0},t_{0}+T_{adap}]$ in comparison to [5] where a min-max optimization
will have to be solved to compute a controller robust for all values of
$A_{p}$ and $\Lambda$ in a compact set. Instead, our controller is chosen to
be stable and sub-optimal over $[t_{0},t_{0}+T_{adap}]$ and near-optimal for
$t\geq t_{1}>t_{0}+T_{adapt}$. Ensuring optimality over
[$t_{0},t_{0}+T_{adap}]$ is a difficult problem that remains to be addressed.

##  V Numerical Example

A numerical example is implemented to demonstrate the ability of proposed
MSAC-MPC algorithm to ensure closed-loop system stability, learn unknown
parameter values before $T_{adap}$, and perform optimal control after
$T_{adap}$. The plant is chosen as an unstable, second-order linear system
with two inputs in the form of (1), where

$A_{p}=\begin{bmatrix}1&1\\\ 0&1\end{bmatrix},B_{p}=\begin{bmatrix}1&0\\\
0&1\end{bmatrix},\Lambda=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$

The reference system is chosen as specified in (8) with

$A_{m}=\begin{bmatrix}-1&1\\\ 0&-2\end{bmatrix},B_{m}=\begin{bmatrix}1&0\\\
0&1\end{bmatrix}$

The input magnitude saturation function $B_{sat}(u)$ is defined in (2), and
the admissible input set $U$ is defined in (4e), where the $u_{max}$ is chosen
as $u_{max}=8$. Without loss of generality, it assumed that $t_{0}=0$.

The exogenous signal desired to be tracked is defined as,

$x_{d}(t)=\begin{bmatrix}sin(t)+sin(3t)+sin(5t)+sin(7t)\\\
sin(2t)+sin(4t)+sin(6t)\end{bmatrix}$

Note that there are 12 uncertain parameters in $\Theta_{a}$ to be estimated.
Choosing the above $x_{d}$ with sinusoidal signals at 7 different frequencies
ensures $\Phi_{a}$ to have persistent excitation properties in (18) [3].

The penalty matrix $Q$, $R$ defined in (4a) are chosen as follows,

$Q=\begin{bmatrix}20&0\\\ 0&20\end{bmatrix},R=\begin{bmatrix}1&0\\\
0&1\end{bmatrix}$

The initial condition of the state $x_{p}$ is set to $x_{p}(0)=[0,0]^{T}$. The
initial parameter estimator values are chosen as
$\widehat{\Theta}_{a}(0)=0.8\Theta_{a}$.

In the simulation, $T_{adap}=32\pi$ is chosen to ensure parameter learning is
performed sufficiently. MSAC controller defined in (9), (14), (12),
(13a)-(13c) is applied to (1) during $t\in[0,T_{adap}]$. The MPC controller
$u^{MPC}$ is run during $[T_{adap},T_{adap}+T_{MPC}]$, where $T_{MPC}=8$
[sec]. Simulation results for MSAC controller is shown in Figure 2-4.

Figure 2: State trajectories of plant $x_{p}$, reference system $x_{m}$, and
exogenous signal $x_{d}$. Figure 3: Time histories of unsaturated $u$ and
saturated $B_{sat}(u)$. Figure 4: 2-norm of parameter estimation error
$\widetilde{\Theta}_{a}$.

In Figure 2, it is observed that $x_{m}$ follow $x_{d}$ closely. Due to active
control input saturation (2) observed in Figure 3, the tracking error
$\|x_{p}-x_{d}\|$ is not converging to zero, but it is the same order of
magnitude as $\Delta u$ defined in defined in Section IV.A, which demonstrates
the MSAC controller’s ability to provide stability guarantees. It is also
observed in Figure 4 that under PE condition, the MSAC controller is able to
reduce the parameter estimation error rapidly, as stated in Theorem 3.

After $T_{adap}$, the MSAC-MPC controller switches to $u^{MPC}$ defined in
Section IV.B. The simulation results are shown in Figure 5-6, where $x_{p}$ is
the plant state trajectory generated by applying $u^{MPC}$ to (1), and
$x_{p}^{*}$ is the latent optimal state trajectory generated by applying
$u^{*}$ to (1). It is observed that $x_{p}$ and $u^{MPC}$ match with
$x_{p}^{*}$ and $u^{*}$ closely, respectively.

Figure 5: Comparison between time histories of plant state $x_{p}$ and optimal
state $x_{p}^{*}$. Figure 6: Comparison between time histories of $u^{MPC}$
and $u^{*}$.

##  VI Conclusions

In this paper, we have developed a MSAC-MPC controller to address linear
quadratic tracking optimal control problems under parametric uncertainties and
input saturation. Theoretical results have been developed to show the proposed
MSAC controller is able to provide stable solutions and achieve parameter
learning under persistent excitation, and that after switching from MSAC to
MPC controller, the optimality gap is proportional to the parameter estimation
error bound. A numerical example based on an unstable second-order, two-input
system has been developed to demonstrate the effectiveness of the MSAC-MPC
controller along with its parameter learning ability and well-defined
optimality gap. We note that during the first step when adaptation is being
carried out, the controller is stable but not optimal, and that during the
second step, it is near-optimal. How these optimality gaps can be further
reduced is a topic for future research.

## References

  * [1] K. J. Åström and B. Wittenmark, _Adaptive control_. Courier Corporation, 2013.
  * [2] J. E. Gaudio, A. M. Annaswamy, M. A. Bolender, E. Lavretsky, and T. E. Gibson, “A class of high order tuners for adaptive systems,” _IEEE Control Systems Letters_ , vol. 5, no. 2, pp. 391–396, 2020.
  * [3] K. S. Narendra and A. M. Annaswamy, _Stable Adaptive Systems_. NJ: Dover Publications, 2005, (original publication by Prentice-Hall Inc., 1989).
  * [4] R. S. Sutton, A. G. Barto, and R. J. Williams, “Reinforcement learning is direct adaptive optimal control,” _IEEE control systems magazine_ , vol. 12, no. 2, pp. 19–22, 1992.
  * [5] V. Adetola, D. DeHaan, and M. Guay, “Adaptive model predictive control for constrained nonlinear systems,” _Systems & Control Letters_, vol. 58, no. 5, pp. 320–326, 2009.
  * [6] A. Bemporad, F. Borrelli, and M. Morari, “Min-max control of constrained uncertain discrete-time linear systems,” _IEEE Transactions on automatic control_ , vol. 48, no. 9, pp. 1600–1606, 2003.
  * [7] D. P. Bertsekas, “Approximate dynamic programming,” 2008.
  * [8] Y. Jiang and Z.-P. Jiang, “Computational adaptive optimal control for continuous-time linear systems with completely unknown dynamics,” _Automatica_ , vol. 48, no. 10, pp. 2699–2704, 2012.
  * [9] ——, “Global adaptive dynamic programming for continuous-time nonlinear systems,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 11, pp. 2917–2929, 2015.
  * [10] D. Vrabie and F. L. Lewis, “Adaptive optimal control algorithm for continuous-time nonlinear systems based on policy iteration,” in _2008 47th IEEE Conference on Decision and Control_. IEEE, 2008, pp. 73–79.
  * [11] S. Bhasin, R. Kamalapurkar, M. Johnson, K. G. Vamvoudakis, F. L. Lewis, and W. E. Dixon, “A novel actor–critic–identifier architecture for approximate optimal control of uncertain nonlinear systems,” _Automatica_ , vol. 49, no. 1, pp. 82–92, 2013.
  * [12] R. Tedrake, _Underactuated Robotics_ , 2022. [Online]. Available: https://underactuated.csail.mit.edu
  * [13] O. L. Mangasarian, “Sufficient conditions for the optimal control of nonlinear systems,” _SIAM Journal on control_ , vol. 4, no. 1, pp. 139–152, 1966.
  * [14] M. Schwager and A. M. Annaswamy, “Direct adaptive control of multi-input plants with magnitude saturation constraints,” in _Proceedings of the 44th IEEE Conference on Decision and Control_. IEEE, 2005, pp. 783–788.
  * [15] A. M. Annaswamy, A. Guha, Y. Cui, J. E. Gaudio, and J. M. Moreu, “Online algorithms and policies using adaptive and machine learning approaches,” _arXiv preprint arXiv:2105.06577_ , 2021.
  * [16] A. Sarker, P. Fisher, J. E. Gaudio, and A. M. Annaswamy, “Accurate parameter estimation for safety-critical systems with unmodeled dynamics,” _Artificial Intelligence_ , p. 103857, 2023.
  * [17] B. Kouvaritakis and M. Cannon, “Model predictive control,” _Switzerland: Springer International Publishing_ , vol. 38, 2016.


11institutetext: Visual Geometry Group, University of Oxford1, Visym Labs2
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Inducing Predictive Uncertainty Estimation for Face Recognition

Weidi Xie1 Jeffrey Byrne2 Andrew Zisserman1

###### Abstract

Knowing when an output can be trusted is critical for reliably using face
recognition systems. While there has been enormous effort in recent research
on improving face verification performance, understanding when a model’s
predictions should or should not be trusted has received far less attention.

Our goal is to assign a confidence score for a face image that reflects its
quality in terms of recognizable information. To this end, we propose a method
for generating image quality training data automatically from ‘mated-pairs’ of
face images, and use the generated data to train a lightweight Predictive
Confidence Network, termed as _PCNet_ , for estimating the confidence score of
a face image. We systematically evaluate the usefulness of PCNet with its
error versus reject performance, and demonstrate that it can be universally
paired with and improve the robustness of any verification model. We describe
three use cases on the public IJB-C face verification benchmark: (i) to
improve 1:1 image-based verification error rates by rejecting low-quality face
images; (ii) to improve quality score based fusion performance on the 1:1 set-
based verification benchmark; and (iii) its use as a quality measure for
selecting high quality (unblurred, good lighting, more frontal) faces from a
collection, _e.g._ for automatic enrolment or display.

##  1 Introduction

There has been tremendous progress in face recognition over the past five
years, primarily due to three factors: _First_ , the development of neural
network architectures, from AlexNet [25], to VGGNet [33], to ResNet [20];
_Second_ , the introduction of more sophiscticated objective functions, for
instance, contrastive loss [11], triplet loss [38], large-margin softmax [27,
13]. _Third_ , the large-scale datasets, _e.g._ VGGFace [29], UMDFace [7],
MS1M [19], VGGFace2 [9], IMDB-Face [37], that have enabled the data-hungry
neural network models to be trained. With these efforts, state-of-the-art face
recognition models have demonstrated strong capabilities of learning effective
identity embeddings, which are largely invariant to nuance factors, such as
pose and age, yet are still discriminative for face identities.

|  |  |
---|---|---|---
(a) Mated pair (similarity score$\approx$0.4) |  (b) Non-mated pair (similarity score$\approx$0.4)
Predictive Confidence = 0.13 |  Predictive Confidence = 0.95
Figure 1: A face verification model (ResNet101 trained on VGGFace2) gives
similar output scores to both pairs, In (a), it refers to a false negative
matching, where the low similarity score is most likely due to the inadequate
information in the second image. In (b), the similarity score indicates that
the identities are different in the pair of images. Predictive confidence is
required to decide whether to trust the output from the system or not.

In this paper our objective is face verification – the task of determining if
two face images are of the same person or not; or, more generally, given two
sets of faces, where each set only contains arbitrary number of images from
one person, determine if the two sets are of the same person or not.
Verification, as is this case for any face recognition task, depends on the
assumption that the input image contains sufficient information to be
recognizable. During the training stage, this assumption is usually
guaranteed, largely due to the bias from the data collection process – that
images have been curated by human annotators, and so must be recognizable.
Unfortunately, this is not always the case during the inference stage, as the
input face images to verification system may be in profile, blurry, or low
resolution (or even non-face images if the face detector operating point is
for very high recall). As a result, this train-test discrepancy will
potentially lead to false positives or negatives during verification. For
instance, as demonstrated in Figure 1, a well-trained face recognition model
(ResNet101 in this case) is broken by one low-quality image. Conceptually,
this challenge can be resolved by augmenting the similarity between the face
embeddings with a predictive confidence, which is identity-agnostic, and only
reflects whether the image contains sufficient discriminative information to
be recognizable.

Estimating such confidence scores is a non trivial task, as it is costly and
challenging to obtain groundtruth annotations. Indeed, even defining image
quality is difficult, despite the early efforts [1, 2] on measuring image
quality by pose, expression, illumination, occlusion, and face accessories,
some metrics remain extremely subjective. Furthermore, since classifications
can be changed by adding perturbations to images (adversarial attacks) that
are indistinguishable to human observers [34, 15, 6, 31], human assessments of
image quality may be only sub-optimal for network training.

In this paper, we propose a method for generating image quality training data
automatically, and use the generated data to train a lightweight network to
predict confidences for any face image. The only requirement of the method is
to have sets of images of the same person – and such sets are readily
available from public face datasets that have identity annotation. Once the
Predictive Confidence Network, PCNet, has been trained, then it can be applied
to any verification system and any face images. This method is described in
Section 3. In Section 4, we systematically evaluate the usefulness of PCNet
with error versus reject curves [18]. Experimentally, we demonstrate it can be
universally paired with and improve the robustness of other recognition
models, including strong models such as SENet50 and ResNet101, and that PCNet
outperforms previous quality estimation baselines, while using a significantly
lighter architecture (ResNet18 vs ResNet50). We also demonstrate three use
cases on the challenging JANUS IJB-C Benchmark [28], (i) PCNet can be used to
significantly improve 1:1 image-based verification error rates, such as False
Accept Rate (FAR), and True Accept Rate (TAR), of automatic face recognition
systems by rejecting low-quality face images; (ii) it can be used for quality
score based fusion where a weighted average is used to combine the descriptors
of multiple images of the same face into a single descriptor, significantly
improve the performance on the 1:1 set-based verification benchmark; and (iii)
it can also be used as a quality measure for selecting good (unblurred, good
lighting, more frontal) faces from a collection, _e.g._ for automatic
enrollment or display.

##  2 Related Work

#### Learning set representation.

Recent works have proposed architectures for learning face descriptor
aggregation [42, 36, 40, 41]. The general idea is to compute a set
representation by the weighted average of the individual face, where the
weights are treated as a latent variable inferred from the deep networks.
While optimizing for classification, the training process implicitly tries to
suppress the contribution from low-quality images, and highlight the most
discriminative face images. This has later been interpreted as fulfiling the
function of quality estimation. Despite the results shown in [41], these
methods lead to over-confident predictions, _i.e._ majority of the images will
have a high quality score.

#### Learning with rejection.

In the cases of learning with single instance, the problem of classification
with a reject option or learning with abstention [16, 43, 12] is highly
related, where the classifier is allowed to abstain from making a prediction
at a certain cost. Typically such methods jointly learn the classifier and the
rejection function. Our paper aims to provide a standalone model that enables
to learn the confidence scores independently to any already trained and
possibly black-box face recognition systems. Technically, our goal is to learn
an appropriate ranking for the confidence scores for the images, but we do not
explicitly learn the appropriate rejection thresholds.

#### Visual quality estimation.

In biometric recognition, image or sample quality has long stood out as the
obvious way of predicting system performance [26, 32], where poor-quality
images pose significant challenges. Traditionally, quality estimation has
focused on the image capturing requirements defined by humans, for instance,
in ISO/IEC 19794-5 [1], ICAO 9303 [2], the quality is usually measured by
pose, expression, illumination, occlusion, and accessories. In the recent
literature, learning-based approaches start getting popular, _e.g._ [3, 4, 14,
23, 30, 5, 39, 10, 24, 8, 21, 35]. See [8, 35] for an excellent extended
literature review.

##  3 Approach

In this section we describe the Predictive Confidence Network (PCNet), that
ingests a face image and outputs a scalar indicating the likelihood of the
face being identifiable by a state-of-the-art face verification system. The
training method proceeds in two stages: first, there is a simple and scalable
approach for generating pairwise verification scores using only mated face-
image pairs, _i.e._ face images of the same person. Second, we provide an
approach to disentangle the pairwise scores to enable training of the PCNet
for single faces. We illustrate the method using the VGGFace2 dataset
(described in Section 4.1) which is partitioned here into two halves by
identites, with the faces of around 4300 identities in each part.

###  3.1 Generate Pairwise Verification Scores

A standard ResNet34 is trained for face classification on the first half of
the dataset, _i.e._ a 4300-way classification. Once trained, verification
scores are obtained for all mated pairs in the the other half of the dataset,
as shown in Figure 2. We also alternate this process (_i.e._ training the
ResNet34 on the other half, etc) in this way we obtain pairwise verification
scores for all mated pairs in the dataset, ending up with roughly 500 million
pairwise scores in total. The scores are obtained in this way, using the two
halfs of the data, so that the scores are not obtained from the same samples
that the network is trained on. Note, the verification score here is obtained
as the cosine similarity between the face embeddings, with a score of $1.0$
indicating a perfect match.

|
---|---
(a) Train ResNet34 for classification. |  (b) Verification scores for mated pairs.
Figure 2:  Generating verification scores for mated pairs.

###  3.2 Training PCNet

We make the assumption that if the verification score is less that $1.0$, then
this is due to recognizability information being missing from either of the
images forming the pair. We then use a ‘loser takes all’ scheme to obtain the
quality measure for the individual images of the pair. That is to say, we
assume the pairwise verification score is fully determined by the image with
worst quality (or least discriminative information). This then becomes a
training target for the PCNet: it is trained to output a predictive confidence
for each image of the pair, such that the minimum of the two confidences
equals the verification score of the pair.

Formally, during training, a mated pair of images is selected (_i.e._ both
images are of the same identity) and each image is passed through PCNet,
parametrized as $\Phi(\cdot)$, and outputs a scalar $s$, referred as the
predictive confidence for the image. For the two images of the pair, if
$s_{1}=\Phi(I_{1};\theta)$ and $s_{2}=\Phi(I_{2};\theta)$, then the training
objective for optimization is defined as the mean square loss, where $y$ is
the verification score of the image pair, mathematically, we minimize the
following loss:

$\mathcal{L}(s_{1},s_{2})=\mathbbm{1}\\{s_{1}<s_{2}\\}\cdot|s_{1}-y|^{2}+\mathbbm{1}\\{s_{2}<s_{1}\\}\cdot|s_{2}-y|^{2}$

where $\mathbbm{1}\\{\cdot\\}$ refers to the indicator function. Note that
this loss guarantees the permutation invariance between the images in the
mated pair. The PCNet is then trained with over 500 million pairwise scores.
For simplicity, in this paper, a standard ResNet18 is used as $\Phi(\cdot)$,
but the proposed method is not limited to any specific architecture.

##  4 Experiments

###  4.1 Datasets

#### VGGFace2 [9]

is used through this paper, to train all face recognition models and PCNet. It
contains about $3.31$ million images with large variations in pose, age,
illumination, ethnicity and profession (e.g. actors, athletes, politicians).
Approximately, $362.6$ images exist for each of the $9131$ identities on
average. In order to be comparable with existing models, we follow the same
dataset split and only train on the training set ($8631$ identities).

#### IJB-C Dataset [28]

is used for all the evaluations in this paper, it is a superset of the
previous IJB-A and IJB-B datasets. Overall, it contains $3,531$ subjects with
$31.3$K still images and $117.5$K frames from $11,779$ videos, captured from
unconstrained environments with large variations in viewpoints, image quality
and distractors (non-face images). It is generally considered as one of the
most challenging _public_ benchmarks for face recognition.

###  4.2 Training Details

While generating pairwise predictive confidence and training PCNet, we follow
the same strategy, namely, resizing the shorter side to $256$, and a region of
$224\times 224$ pixels is randomly cropped from each sample. The mean value of
each channel is subtracted. Stochastic gradient descent is used with mini-
batches of size $256$, with a balancing-sampling strategy for each mini-batch
due to the unbalanced training distributions. The initial learning rate is
$0.1$ for the models learned from scratch, and this is decreased twice with a
factor of $10$ when errors plateau. As for augmentation during training
ResNet34 (in Section 3.1), random transformations are used with a probability
of $20\%$ for each image, e.g. monochrome augmentation, horizontal flipping,
and geometric transformation. As for generating the pairwise predictive
confidence pseudo-groundtruth, each image in the mated pair can potentially
have a probability of $0.2$ of randomly picking at least one of the
degradations from Gaussian blur, motion blur, and jpeg compression, and the
degraded images are later used for training PCNet.

###  4.3 Evaluation Protocol

We benchmark on 1:1 covariate verification and 1:1 verification from JANUS
IJB-C. The former refers to the popular image-to-image verification, while the
latter refers to set-to-set verification, where each set could potentially
contain any number of images of the same identity. For both cases, the
performance is reported as the standard True Accept Rate (TAR) vs. False
Accept Rate (FAR) (_i.e._ receiver operating characteristics (ROC) curve).

To evaluate the effectiveness of ‘predictive confidence’, we report the error
versus reject curves for 1:1 covariate verification (Section 4.5), a metric
originally proposed for measuring biometric quality [18], and recently adopted
for face recognition [17]. These curves show a verification error-rate over
the fraction of ignored face images. Based on the predictive confidences
values, these rejected images are those with the lowest confidences and the
error rate is calculated on the remaining images. The curves indicate good
quality estimation when the verification performance increases (the error
decreases) monotonically as more images are rejected (as this indicates that
the uninformative images are being rejected first). This process allows a fair
comparison to different algorithms for face quality assessment, since it is
independent of the range of the quality predictions (only the ordering is
used).

As PCNet only provides predictive confidence, but not verification
functionality, it is coupled with three different open-source face recognition
models that are publicly available, namely, ResNet50, SENet50 and ResNet101,
for verification. Although these models have all been trained on VGGFace2,
they do behave slightly differently as the training settings vary, _e.g._ data
augmentation, learning rate schedule, _etc_ , as well as due to the
differences in the architectures. Note that, the purpose of this paper is not
to benchmark the state-of-the-art face recognition models, instead, we aim to
validate the conjecture that the predictive confidence is an effective
component for different models, _i.e._ largely model-independent.

###  4.4 Baselines

We compare with two recent works [41, 21], which propose the idea of using
image quality estimation to improve face recognition systems. In [41], the
authors propose the Multicolumn Networks (_MNet_), learning a set
representation through a weighted average of all individual images in the set.
As a by-product, the networks learn a quality estimation that pays more
attention to images with more discriminative information, _e.g._ frontal
faces, high-resolution images. In [21], Face-QNet (_QNet_) is trained by
comparing images with some ‘golden’ reference images, that were selected by
ICAO Compliance Software. We use the official implementation and models [22].
In both works the quality estimation models were trained on VGGFace2 dataset
with a ResNet50 architecture; however, in the following sections, we
demonstrate that our light-weight PCNet (based on ResNet18) outperforms these
strong baseline models on all metrics.

###  4.5 Results: 1:1 Covariate Verification with Rejection

In this protocol, the goal is to perform still image-to-image verification. In
total, there are $140$K images with over $7$M genuine matches, and $39$M
impostor matches. During inference, we define the predictive confidence for
each pair of images as the minimum score of the two images, and rank these
pairwise confidence scores in descending order. By rejecting the bottom $k\%$
pairs, where $k\in[0,40]$, the obtained TAR and FAR will therefore be
informative to understand if the failure cases from modern face recognition
systems are indeed predicable from the confidence scores.

|  | TAR@FAR=1E-6 | TAR@FAR=1E-5
---|---|---|---
Verification Arch. | Predictive Conf. |  r=$0.0$ |  r=$0.1$ |  r=$0.2$ |  r=$0.3$ |  r=$0.4$ |  r=$0.0$ |  r=$0.1$ |  r=$0.2$ |  r=$0.3$ |  r=$0.4$
ResNet-50 |  MNet [41] | $0.202$ | $0.392$ | $0.446$ | $0.488$ | $0.512$ | $0.433$ | $0.578$ | $0.616$ | $0.638$ | $0.657$
ResNet-50 |  QNet [21] | $0.202$ | $0.447$ | $0.502$ | $0.544$ | $0.577$ | $0.433$ | $0.613$ | $0.653$ | $0.693$ | $0.728$
ResNet-50 | PCNet (Ours) | 0.202 | 0.510 | 0.536 | 0.572 | 0.617 | 0.433 | 0.641 | 0.673 | 0.718 | 0.769
SENet-50 |  MNet [41] | $0.317$ | $0.399$ | $0.423$ | $0.455$ | $0.487$ | $0.528$ | $0.595$ | $0.621$ | $0.648$ | $0.670$
SENet-50 |  QNet [21] | $0.317$ | $0.453$ | $0.481$ | $0.517$ | $0.539$ | $0.528$ | $0.629$ | $0.660$ | $0.695$ | $0.724$
SENet-50 | PCNet (Ours) | 0.317 | 0.478 | 0.508 | 0.538 | 0.578 | 0.528 | 0.644 | 0.674 | 0.715 | 0.761
ResNet-101 |  MNet [41] | $0.095$ | $0.248$ | $0.366$ | $0.387$ | $0.440$ | $0.249$ | $0.548$ | $0.622$ | $0.659$ | $0.685$
ResNet-101 |  QNet [21] | $0.095$ | $0.280$ | $0.352$ | $0.409$ | $0.469$ | $0.249$ | $0.592$ | $0.653$ | $0.700$ | $0.738$
ResNet-101 | PCNet (Ours) | 0.095 | 0.465 | 0.490 | 0.530 | 0.565 | 0.249 | 0.671 | 0.707 | 0.752 | 0.797

Table 1: Error vs rejection on IJB-C 1:1 covariate verification. By only
rejecting a small proportion of the low quality image pairs ($r\in[0.0,0.4]$),
significant performance boost can be observed for all different architectures.
Figure 3:  Error vs rejection curve on IJB-C 1:1 covariate verification, with
rejection rate being densely varied.

As shown in Table 1, we sample five different rejection rates ($[0.0,0.4]$),
where $0.0$ refers to the case where no pairs are rejected, _i.e._ the
performance from raw verfication systems (ResNet50, SENet50 and ResNet101).
More complete results are shown in Figure 3, where rejection rates are densely
sampled with a gap of $0.01$. It is clear that when rejecting the face pairs
with lowest predictive confidences, the performance of all face recognition
systems has been improved significantly. This claim holds for all the
different architectures, demonstrating the generalizability of the PCNet –
meaning it is largely recognition model independent. When comparing with
baseline models (MNet and QNet), the proposed PCNet shows superior performance
on all metrics.

In Figure 4, we plot the complete ROC curve on 1:1 covariate verification. It
is interesting to see that PCNet is already very effective when only rejecting
$5\%$ of the pairs with lowest predictive confidences. Remarkably, the
verification performance of ResNet101 has been boosted around $20\%$ for
TAR@FAR=1E-6 and TAR@FAR=1E-5, suggesting that PCNet is indeed producing
informative confidence scores that reflect the potential limitations of modern
face reconigiton systems.

Figure 4:  ROC curves for IJB-C 1:1 covariate verification. Benchmarked for
different architectures under different rejection rate. As can be seen, while
only rejecting $5\%$ of the pairs with lowest predictive confidences, PCNet
can already improve the verification performance significantly.

In Figure 5, we plot the correlation between the predictive confidence and the
similarity scores from different models, we split the confidence scores into
$100$ bins, and compute the mean similarity scores falling in each bin. Note
that the similarity scores are only generated for the mated pairs in the
IJB-C, as such curve for non-mated scores will not be informative, because it
is expected that all points lying on a narrow band on the very left side,
either due to low predictive confidence or high predictive confidence by
different identities. From the strong correlations between predictive
confidence and matching scores for all models, it shows that the proposed
PCNet is effective for avoiding false negatives during evaluation, and also it
is model independent, shown from the consistent correlation among different
models.

Figure 5:  The correlation between predictive confidence and the similarity
scores from different models. The predictive confidences correlate with the
similarity scores from different face verification systems – even though it
was not trained on them.

#### Discussion.

These results demonstrate that PCNet has indeed learnt a quality measure that
correlates with the information content of the face image. Note in particular,
the error vs. reject curves have exhibited a monotonic improvement with
increasing rejection ratio, meaning that the rejected pairs are of the low
visual quality that face recognition systems struggle on. Despite the fact
that the PCNet is only trained with mated pairs, verification evaluation
suggests that it also successfully orders the non-mated pairs. Examples of the
rejected pairs (including mated and non-mated) will be given in the arXiv
version.

###  4.6 Results: Standard 1:1 Verification with Confidence Weighting

This protocol uses set-to-set verification, where each set consists of a
variable number of face images and video frames from different sources: each
set can be image-only, video-frame-only, or a mixture of still images and
frames. This protocol defines $23124$ different sets, with $19557$ genuine
matches, and over $15$M impostor matches. During testing, the set descriptor
is computed as a weighted average of individual faces, with the weights
obtained from the predictive confidences of the faces as $v=\sum_{i}s_{i}\cdot
v_{i}/\sum_{i}s_{i}$ where $s_{i},v_{i}$ refers to the predictive confidence
and feature embedding for the image ($I_{i}$).

#### Discussion.

As shown in Table 2 and Figure 6, using the predictive confidence from PCNet
for computing the set representation gives an improvement for all metrics by
about 2-8% over the raw ResNet50 and SENet50 on 1:1 mixed verification. The
performance improvements are most substantial at low FARs, this is as expected
due to the fact that the main issue of average feature aggregation (as used in
previous results) is that the set-based representation can be distracted by
images of low quality, leading to false matchings. Consequently, the most
dramatic improvement is from highlighting the discriminative faces and
suppressing the ones with inadequate information.

|  |  | 1:1 Verification TAR
---|---|---|---
| Architecture | Predictive Conf. | FAR=1E-6 | FAR=1E-5 | FAR=1E-4 | FAR=1E-3 | FAR=1E-2
Cao et al. [9] | ResNet50 | - | $0.610$ | $0.742$ | $0.842$ | $0.916$ | 0.958
| ResNet50 |  QNet [21] | $0.641$ | $0.762$ | $0.860$ | $0.929$ | 0.969
| ResNet50 |  MNet [41] | 0.664 | 0.770 | 0.864 | 0.930 | 0.969
| ResNet50 | PCNet (Ours) | 0.693 | 0.803 | 0.885 | 0.944 | 0.970
Cao et al. [9] | SENet50 |  | $0.617$ | $0.753$ | $0.852$ | $0.927$ | 0.971
| SENet50 |  QNet [21] | $0.643$ | $0.768$ | $0.861$ | $0.931$ | 0.972
| SENet50 |  MNet [41] | $0.649$ | $0.775$ | $0.867$ | $0.932$ | 0.973
| SENet50 | PCNet (Ours) | 0.695 | 0.800 | 0.890 | 0.948 | 0.974

Table 2:  Evaluation on 1:1 verification protocol on IJB-C dataset. Higher is
better. The numbers with MNet [41] are based on our re-implementations, and
QNet is from the official implementation and model [22].  Figure 6:  On 1:1
IJB-C Verification, the PCNet improves the set-based verificationc for
different face verification architectures, and outperform both QNet and MNet.

###  4.7 Visualization.

In Figure 8, we show the sorted images in ascending order based on the
predictive confidences inferred from PCNet. As expected, the low confidence
scores for aberrant images are highly correlated with human expectation,
_i.e._ blurry, nonface, extreme poses. Note, the images of medium and high
quality are not so well separated, though high quality ones are often near
frontal.

Figure 7: After ranking all images of the IJB-C datasets, we split the ranking
into three different ranges, and randomly sample images from the corresponding
range.

##  5 Conclusions

To summarize, in this paper, we propose a novel training scheme for learning
predictive confidence, with the goal of reducing the proportion of errors
caused by images with insufficient information, _e.g._ poor visual quality or
profile faces, non-face images. While evaluating on the challenging JANUS
IJB-C Benchmarks, we demonstrate three use cases: (i) PCNets can be used to
significantly improve 1:1 image-based verification error rates, of automatic
face recognition systems by rejecting low-quality face images, (ii) it can be
used for quality score based fusion where a weighted average is used to
compute set representation, (iii) it can also be used as a quality measure for
selecting good (unblurred, good lighting, more frontal) faces from a
collection, _e.g._ for automatic enrollment or display. Although we have
presented the predicitive confidence as essential for face verification, the
idea of learning a confidence from true matches is more generally applicable.
For example, a predictive confidence could be learnt from a set of ground
truth matches between images, and then used to predict a confidence for
correspondences between images or video frames.

## Acknowledgment

This research is based upon work supported by the Office of the Director of
National Intelligence (ODNI), Intelligence Advanced Research Projects Activity
(IARPA), via contract number 2014-14071600010. The views and conclusions
contained herein are those of the authors and should not be interpreted as
necessarily representing the official policies or endorsements, either
expressed or implied, of ODNI, IARPA, or the U.S. Government. The U.S.
Government is authorized to reproduce and distribute reprints for Governmental
purpose notwithstanding any copyright annotation thereon. Funding for this
research is also provided by the EPSRC Programme Grant Seebibyte EP/M013774/1.

## References

  * [1] Information technology – biometric data interchange formats – part 5: Face image data. Standard, International Organisation for Standardization (2011)
  * [2] Machine readable travel documents. Standard, International Civil Aviation Organization (2015)
  * [3] Abaza, A., Ann Harrison, M., Bourlai, T.: Quality metrics for practical face recognition. In: Proceedings of the 21st International Conference on Pattern Recognition (ICPR2012) (2012)
  * [4] Abaza, A., Ann Harrison, M., Bourlai, T.: Design and evaluation of photometric image quality measures for effective face recognition. IET Biometrics (2014)
  * [5] Aggarwal, G., Biswas, S., Flynn, P., Bowyer, K.: Predicting performance of face recognition systems: An image characterization approach. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR Workshops (2011)
  * [6] Anh, N., Jason, Y., Jeff, C.: Neural networks are easily fooled: High confidence predictions for unrecognizable images. In: Proc. CVPR (2015)
  * [7] Bansal, A., Nanduri, A., Castillo, C., Ranjan, R., Chellappa, R.: Umdfaces: An annotated face dataset for training deep networks. arXiv preprint arXiv:1611.01484 (2016)
  * [8] Best-Rowden, L., Jain, A.K.: Learning face image quality from human assessments. In: IEEE Transactions on Information Forensics and Security. (2018)
  * [9] Cao, Q., Shen, L., Xie, W., Parkhi, O.M., Zisserman, A.: VGGFace2: A dataset for recognising faces across pose and age. In: Proc. Int. Conf. Autom. Face and Gesture Recog. (2018)
  * [10] Chen, J., Deng, Y., Bai, G., Su, G.: Face image quality assessment based on learning to rank. IEEE Signal Processing Letters (2015)
  * [11] Chopra, S., Hadsell, R., LeCun, Y.: Learning a similarity metric discriminatively, with application to face verification. In: Proc. CVPR. IEEE (2005)
  * [12] Cortes, C., DeSalvo, G., Mohri, M.: Boosting with abstention. In: NIPS (2016)
  * [13] Deng, J., Guo, J., Xue, N., Zafeiriou, S.: Arcface: Additive angular margin loss for deep face recognition. In: Proc. CVPR (2019)
  * [14] Dutta, A., Veldhuis, R., Spreeuwers, L.: A bayesian model for predicting face recognition performance using image quality. In: IEEE International Joint Conference on Biometrics, Clearwater, IJCB (2014)
  * [15] Goodfellow, I., Shlens, J., Szegedy, C.: Explaining and harnessing adversarial examples. In: Proc. ICLR (2015)
  * [16] Grandvalet, Y., Rakotomamonjy, A., Keshet, J., Canu, S.: Support vector machines with a reject option. In: NIPS (2009)
  * [17] Grother, P., Ngan, W., Hanaoka, K.: Face Recognition Vendor Test - Face Recognition Quality Assessment Concept and Goals. NIST (2019)
  * [18] Grother, P., Tabassi, E.: Performance of biometric quality measures. TPAMI 29(4), 531–543 (2007)
  * [19] Guo, Y., Zhang, L., Hu, Y., He, X., Gao, J.: Ms-celeb-1m: A dataset and benchmark for large-scale face recognition. In: Proc. ECCV (2016)
  * [20] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proc. CVPR (2016)
  * [21] Hernandez-Ortega, J., Galbally, J., Fierrez, J., Haraksim, R., Beslay, L.: Faceqnet: Quality assessment for face recognition based on deep learning. In: IEEE International Conference on Biometrics, ICB (2019)
  * [22] Hernandez-Ortega, J., Galbally, J., Fierrez, J., Haraksim, R., Beslay, L.: Faceqnet: Quality assessment for face recognition based on deep learning. https://github.com/uam-biometrics/FaceQnet (2019)
  * [23] Hsu, R.L.V., Shah, J., Martin, B.: Quality assessment of facial images. In: Biometrics Symposium: Special Session on Research at the Biometric Consortium Conference (2006)
  * [24] Kim, H.I., Lee, S.H., Ro, Y.M.: Face image assessment learned with objective and relative face image qualities for improved face recognition. In: IEEE International Conference on Image Processing (ICIP) (2015)
  * [25] Krizhevsky, A., Sutskever, I., Hinton, G.: ImageNet classification with deep convolutional neural networks. In: NIPS (2012)
  * [26] Li, W., Gao, X., Boult, T.: Predicting biometric system failure. In: IEEE International Conference on Computational Intelligence for Homeland Security and Personal Safety Orlando (2005)
  * [27] Liu, W., Wen, Y., Yu, Z., Li, M., Raj, B., Song, L.: Sphereface: Deep hypersphere embedding for face recognition. In: Proc. CVPR (2017)
  * [28] Maze, B., Adams, J., Duncan, J., Kalka, N., Miller, T., Otto, C., Jain, A.K., Niggel, W.T., Anderson, J., Cheney, J., Grother, P.: IARPA janus benchmark-c: Face dataset and protocol. In: 11th IAPR International Conference on Biometrics (2018)
  * [29] Parkhi, O.M., Vedaldi, A., Zisserman, A.: Deep face recognition. In: Proc. BMVC. (2015)
  * [30] Phillips, P.J., Beveridge, J.R., Bolme, D.S., Draper, B.A., Givens, G.H., Lui, Y.M., Cheng, S., Zhang, H.: On the existence of face quality measures. In: IEEE Sixth International Conference on Biometrics: Theory, Applications and Systems (BTAS) (2013)
  * [31] Rozsa, A., Gunther, M., Rudd, E., Boult, T.: Are facial attributes adversarially robust? In: 23rd International Conference on Pattern Recognition (ICPR) (2016)
  * [32] Scheirer, W., Rocha, A., Micheals, R., Boult, T.: Meta-recognition: The theory and practice of recognition score analysis. TPAMI (2011)
  * [33] Simonyan, K., Zisserman, A.: Very deep convolutional networks for large-scale image recognition. In: ICLR (2015)
  * [34] Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., Fergus, R.: Intriguing properties of neural networks. In: Proc. ICLR (2014)
  * [35] Terhorst, P., Kolf, J.N., Damer, N., Kirchbuchner, F., Kuijper, A.: Ser-fiq: Unsupervised estimation of face image quality based on stochastic embedding robustness. In: Proc. CVPR (2020)
  * [36] Tran, L., Yin, X., Liu, X.: Disentangled representation learning gan for pose-invariant face recognition. In: Proc. CVPR (2017)
  * [37] Wang, F., Chen, L., Li, C., Huang, S., Chen, Y., Qian, C., Change Loy, C.: The devil of face recognition is in the noise. In: Proc. ECCV (2018)
  * [38] Weinberger, K.Q., Blitzer, J., Saul, L.: Distance metric learning for large margin nearest neighbor classification. In: NIPS (2006)
  * [39] Wong, Y., Chen, S., Mau, S., Sanderson, C., Lovell, B.: Patch-based probabilistic image quality assessment for face selection and improved video-based face recognition. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR Workshops (2011)
  * [40] Xie, W., Shen, L., Zisserman, A.: Comparator networks. In: Proc. ECCV (2018)
  * [41] Xie, W., Zisserman, A.: Multicolumn networks for face recognition. In: Proc. BMVC. (2018)
  * [42] Yang, J., Ren, P., Zhang, D., Chen, D., Wen, F., Li, H., Hua, G.: Neural aggregation network for video face recognition. In: Proc. CVPR (2017)
  * [43] Yuan, M., Wegkamp, M.: Classification methods with reject option based on convex risk minimization. Journal of Machine Learning Research (2010)

Appendix

##  Appendix 0.A Architecture for PCNet

Here, we present the backbone architecture for the proposed PCNet, which is
based on the standard ResNet18 with an extra fully connected layer at the end.

Architecture |  Input Image ($N\times 224\times 224\times 3$) |  Output Size
---|---|---
Predictive Confidence Network |  conv, $7\times 7$, $64$, stride $2$ |  $112\times 112\times 64$
max pool, $3\times 3$, stride $2$ |  $56\times 56\times 64$
$\begin{bmatrix}{\rm conv},3\times 3,64\\\ {\rm conv},3\times 3,64\end{bmatrix}\times 2$ |  $56\times 56\times 64$
$\begin{bmatrix}{\rm conv},3\times 3,128\\\ {\rm conv},3\times 3,128\end{bmatrix}\times 2$ |  $28\times 28\times 128$
$\begin{bmatrix}{\rm conv},3\times 3,256\\\ {\rm conv},3\times 3,256\end{bmatrix}\times 2$ |  $14\times 14\times 256$
$\begin{bmatrix}{\rm conv},3\times 3,512\\\ {\rm conv},3\times 3,512\end{bmatrix}\times 2$ |  $7\times 7\times 512$
Global Average Pooling |  $1\times 1\times 512$
FC, $1\times 1$, $128$ |  $1\times 1\times 128$
Predictive Confidence, $1\times 1$, $1$ |  $1\times 1\times 1$

Table 3: Architecture of the proposed Predictive Confidence Network (PCNet).

##  Appendix 0.B More visualization of single-image confidence scores

Figure 8: After ranking all images of the IJB-C datasets, we split the ranking
into three different ranges, and randomly sample images from the corresponding
range.

##  Appendix 0.C Visualizing the rejected pairs by PCNet

In Figure 9, we show example pairs that have been rejected while ploting the
error vs rejection curve, in other words, these pairs are predicted with the
lowest predictive confidence from our PCNet. As expected, once single image or
both images are of low quality in the sense of insufficient information to be
recognizable, the PCNet can indeed alarm the users.

Figure 9: Visualizing the rejected pairs by PCNet while ploting the error vs
rejection curve. Note that, the figures are grouped by pairs in the column,
_i.e._ two images are shown in each pairs.


ifaamas [AAMAS ’23]Proc. of the 22nd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2023)May 29 – June 2, 2023 London, United
KingdomA. Ricci, W. Yeoh, N. Agmon, B. An (eds.) 2023 2023 ??? funding from
ALTER, The Association For Long Term Existence And Resilience Bar-Ilan
University Ramat Gan Israel Tel Aviv University Tel Aviv Israel Bar-Ilan
University Ramat Gan Israel

# Stubborn: An Environment for Evaluating Stubbornness between Agents with
Aligned Incentives

Ram Rachum<EMAIL_ADDRESS>,  Yonatan Nakar<EMAIL_ADDRESS>and  Reuth Mirsky<EMAIL_ADDRESS>
###### Abstract.

Recent research in multi-agent reinforcement learning (MARL) has shown success
in learning social behavior and cooperation. Social dilemmas between agents in
mixed-sum settings have been studied extensively, but there is little research
into social dilemmas in fully-cooperative settings, where agents have no
prospect of gaining reward at another agent’s expense.

While fully-aligned interests are conducive to cooperation between agents,
they do not guarantee it. We propose a measure of ”stubbornness” between
agents that aims to capture the human social behavior from which it takes its
name: a disagreement that is gradually escalating and potentially disastrous.
We would like to promote research into the tendency of agents to be stubborn,
the reactions of counterpart agents, and the resulting social dynamics.

In this paper we present Stubborn111The code and installation instructions for
Stubborn are available at https://github.com/cool-RR/stubborn, an environment
for evaluating stubbornness between agents with fully-aligned incentives. In
our preliminary results, the agents learn to use their partner’s stubbornness
as a signal for improving the choices that they make in the environment.

###### Key words and phrases:

Multi-Agent Reinforcement Learning, Reinforcement Learning, Multi-Agent
Systems, Rebellion and Disobedience in AI

##  1\. Introduction

Mirsky and Stone Mirsky and Stone (2021b) pose a challenge of using AI to
produce an autonomous robot for assisting visually impaired people, similarly
to a seeing-eye dog. Among the discussion of the technological, ethical and
social challenges involved in this project, we would like to focus on the
issue of intelligent disobedienceMirsky and Stone (2021a).

When a flesh-and-bones seeing-eye dog is assisting its human operator in
walking down a street, one of its tasks is to notice obstructions and dangers,
and communicate with its operator accordingly. In the case of a full
obstruction, or a passing vehicle, the seeing-eye dog is highly motivated to
physically block the operator from proceeding, even when the operator is
pleading and pushing the seeing-eye dog to move forward. The seeing-eye dog
cannot communicate verbally, and the visually-impaired operator cannot see the
obstruction or danger; therefore the only way for the operator to gauge the
severity of the obstruction or danger is to escalate their pleading and
pushing, and to observe how far the seeing-eye dog will go in matching their
insistence. This tug of war, while frustrating for both human and dog, serves
as a means of communication between the two.

In this scenario, the two agents are in conflict not because they are
competing for an exclusive resource, but because they are both motivated to
reach the best possible agreement for their mutual benefit. Unlike most
sequential social dilemmasLeibo et al. (2017) studied with multi-agent
reinforcement learning, it results from a divergence of observations rather
than motivationsHughes et al. (2018).

In this paper we present Stubborn, an environment for evaluating stubbornness
between agents with fully-aligned incentives. The rules for this environment
are a simplified version of the dilemma described above. In our preliminary
results, the agents learn to use their partner’s stubbornness as a signal for
improving their choices in the environment.

##  2\. Environment rules

In the Stubborn environment, two agents are presented with two possible
rewards, and they have to make a unanimous choice for one of these rewards. We
explore the tension between the agents’ motivation to choose the biggest
reward, and their motivation to reach an agreement quickly.

  1. (1)

The environment is fully cooperative; the reward for Agent A is always equal
to the reward for Agent B.

  2. (2)

The environment is partially observable. Crucially, the agents’ observations
are different from each other: Each agent observes an estimate of the left
reward and an estimate of the right reward. Each estimate is sampled from a
normal distribution around the true reward. The rewards themselves are sampled
from a uniform distribution between 0 and 10.

  3. (3)

Each agent also observes the moves taken by the other player.

  4. (4)

Each episode of the game consists of $N_{t}$ turns with simultaneous actions.
In each turn, each agent chooses whether to take the left reward or the right
reward. If both agents choose the same reward, they both get the true value of
the reward they’ve chosen. If they choose different rewards, they both get a
reward of zero, which is always less than even the smallest reward, and
continue playing until they reach an agreement or until the episode has
reached $N_{t}$ turns.

  5. (5)

When the agents agree on a reward, two new random rewards are generated, along
with four new estimates. The agents then play again for these rewards. Each
sequence of turns is called a ”skirmish”, i.e. whenever the agents reach an
agreement, a new skirmish is started.

  6. (6)

If both agents happen to change their choice at the same time, we pick one of
the rewards at random and give it to both of them. In practice this means that
each agent has a surefire way of ending any disagreement immediately.

A skirmish can last anywhere between 1 and $N_{t}$ turns. A trivial example of
a skirmish: Both agents immediately choose the left reward, and the skirmish
ends with a length of one turn. Both agents get the left reward and a new
skirmish begins. A non-trivial example of a skirmish: On the first turn Agent
A chooses left while Agent B chooses right. On the second turn Agent A chooses
left again while Agent B chooses right again. On the third turn, both agents
choose right. Both agents get the right reward and a new skirmish begins.

Whenever agents disagree about which reward to take, they get a reward of
zero. Intuitively, agents want to choose the biggest reward, but they would
also like to prevent a long and costly disagreement with their partner.
Crucially, when agents enter into conflict with each other, they don’t know in
advance how long the conflict will last, and which agent will give in first.
The bigger the difference that an agent perceives between the two rewards, the
bigger is its temptation to insist and hope that its partner will come around.

##  3\. Preliminary results

We trained two agents with separate models on this environment, using a
Proximal Policy Optimization (PPO) algorithmSchulman et al. (2017) provided by
the RLlib frameworkLiang et al. (2017). We trained the two agents for 5,000
generations, with each episode consisting of 40 turns.

We observe in Figure 1 that the agents converge on a reward that’s slightly
higher than the initial reward.

Figure 1. Agent reward over 5,000 training generations

We would like to measure how the stubbornness of one agent affects the
decision-making of its counterpart. For each training generation, we perform a
counterfactual measurement on the behavior of the trained policies. We define
$\zeta_{n,d}$ as the probability that an agent will choose the left reward,
where:

  1. (1)

According to its estimate, the left reward is $d$ points higher than the right
reward.

  2. (2)

The two agents spent the last $n$ turns disagreeing, with the given agent
choosing the left reward, and the other agent choosing the right reward.

Intuitively, $\zeta_{n,d}$ represents the likelihood of the agent to insist on
its initial choice, extending the skirmish by an unpredictable number of
turns.

In Figure 2, we show the average value of $\zeta_{n,d}$ over 5,000 training
generations, with $n\in{0,1,2,3,4}$ and $d=5$:

Figure 2. Average value of $\zeta_{n,d}$ over 5,000 training generations, with
$n\in{0,1,2,3,4}$ and $d=5$

We observe an inverse correlation: The more an agent insists on a certain
choice, the more likely its counterpart agent is to agree to change its
choice, even if that choice is seen as inferior according to its estimates.
The length of the conflict, which is proportional to the sunk opportunity cost
incurred by it, is used as a factor in the agent’s decision whether to prolong
the skirmish or end it.

##  4\. Discussion and future work

We presented a new measure for fully-cooperative MARL, in which we quantify
how stubborn the agents are. We show that in a single use case, each agent’s
stubbornness was correlated to the other agent’s likelihood to yield to them.

We initially experimented with a more general variation of the environment
rules listed above. Specifically, we set up the environment so one agent’s
estimates are more accurate than its partner. We defined a handicap for each
agent, which is a number that determines the variance of the normal
distribution of the estimate. For example, an agent with a handicap of $2$
would get more accurate estimates than an agent with a handicap of $7$.
Moreover, we experimented with setting the handicaps of both agents to a
random number on each episode, while each agent knows its own handicap but not
its partner. We hoped that the agents would use their stubbornness as a means
of communicating the size of their handicaps to each other; if both agents
know that Agent A has more accurate estimates than Agent B, a social
convention where Agent B always yields would be beneficial for both agents.
This behavior did not occur, but it’s possible that a variation on this idea
would converge.

Joining efforts with Boggs et al. Boggs et al. (2018) to provide tools for
RaD-AI researchers to reach new insights, we’ve made our code available under
the MIT open-source license. We hope to promote more research into this
scenario.

##  5\. Acknowledgements

We thank Edgar A. Duéñez-Guzmán and Georg Ostrovski for their valuable
insights and suggestions that helped us refine the ideas presented in this
work.

## References

  * (1)
  * Boggs et al. (2018) James P. Boggs, Dustin Dannenhauer, Michael W. Floyd, and David W. Aha. 2018.  The Ideal Rebellion : Maximizing Task Performance in Rebel Agents.  _Proceedings of the 6th Goal Reasoning Workshop_.
  * Hughes et al. (2018) Edward Hughes, Joel Z. Leibo, Matthew G. Phillips, Karl Tuyls, Edgar A. Duéñez-Guzmán, Antonio García Castañeda, Iain Dunning, Tina Zhu, Kevin R. McKee, Raphael Koster, Heather Roff, and Thore Graepel. 2018\.  Inequity aversion improves cooperation in intertemporal social dilemmas.  https://doi.org/10.48550/ARXIV.1803.08884
  * Leibo et al. (2017) Joel Z. Leibo, Vinicius Zambaldi, Marc Lanctot, Janusz Marecki, and Thore Graepel. 2017.  Multi-agent Reinforcement Learning in Sequential Social Dilemmas.  https://doi.org/10.48550/ARXIV.1702.03037
  * Liang et al. (2017) Eric Liang, Richard Liaw, Philipp Moritz, Robert Nishihara, Roy Fox, Ken Goldberg, Joseph E. Gonzalez, Michael I. Jordan, and Ion Stoica. 2017.  RLlib: Abstractions for Distributed Reinforcement Learning.  https://doi.org/10.48550/ARXIV.1712.09381
  * Mirsky and Stone (2021a) Reuth Mirsky and Peter Stone. 2021a.  Intelligent Disobedience and AI Rebel Agents in Assistive Robotics.  _Proceedings of the ASIMOV workshop as part of the International Conference on Social Robotics_ (2021).
  * Mirsky and Stone (2021b) Reuth Mirsky and Peter Stone. 2021b.  The seeing-eye robot grand challenge: Rethinking automated care.  _Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems_ (2021).
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal Policy Optimization Algorithms.  https://doi.org/10.48550/ARXIV.1707.06347