# Actively Learning Reinforcement Learning: A Stochastic Optimal Control
Approach

Mohammad S. Ramadan1, Mahmoud A. Hayajnh2, Michael T. Tolley1, Kyriakos G.
Vamvoudakis2 This work was supported in part, by ARO under grant No.
W$911$NF-$19-1-0270$, by NSF under grant Nos. CAREER CPS-$1851588$,
S&AS-$1849198$, and SATC-$1801611$.1M. S. Ramadan and M. T. Tolley are with
the Department of Mechanical and Aerospace Engineering, University of
California, San Diego, CA 92161 USA<EMAIL_ADDRESS><EMAIL_ADDRESS>A.
Hayajnh and K. G. Vamvoudakis are with The Daniel Guggenheim School of
Aerospace Engineering, Georgia Institute of Technology, GA 30332-0150 USA,
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper we provide a framework to cope with two problems: (i) the
fragility of reinforcement learning due to modeling uncertainties because of
the mismatch between controlled laboratory/simulation and real-world
conditions and (ii) the prohibitive computational cost of stochastic optimal
control. We approach both problems by using reinforcement learning to solve
the stochastic dynamic programming equation. The resulting reinforcement
learning controller is safe with respect to several types of constraints and
it can actively learn about the modeling uncertainties. Unlike exploration and
exploitation, probing and safety are employed automatically by the controller
itself, resulting real-time learning. A simulation example demonstrates the
efficacy of the proposed approach.

##  I Introduction

The field of reinforcement learning (RL) has shown significant promise across
various disciplines ranging from gaming to robotics [28]. At its core, RL
tries to solve an optimal control problem through maximizing some notion of a
cumulative reward. Yet, with this promise of RL algorithms, a tough challenge
arises when applying learned policies to real-world applications [13]. These
policies, trained in lab simulations or controlled environments, may suffer a
degradation in performance or even pocess an unsafe behavior [24]. This is due
to modeling mismatches and discrepancies between the training environment and
real-world conditions.

On the other hand, the field of stochastic optimal control [9, ch. 25], also
known as dual control [30], highlights two important consequences of applying
such control: caution and probing [18]. Caution can be seen as the control
actions that prevent undesirable outcomes when the system is under
uncertainty. Probing, on the other hand, is the actions that result in
gathering information about the system’s uncertain parameters and/or states.
Both these concepts play a central role in ensuring safety while enhancing the
system’s learning capabilities and state observability. However, a control
with such benefits is not easy to achieve, and in general, stochastic optimal
control is computationally prohibitive, except for the simplest cases. Relying
on dynamic programming to solve such high dimensional problems is unreasonable
[4], due to the curse of dimensionality. In general, previous research has
focused on suboptimal approaches [19], which are mostly application specific.
In this work however, we focus on establishing a more general, less suboptimal
framework.

The challenges faced by both RL and stochastic optimal control hinder their
potential. Here we consider if each can serve as a solution to the other’s
challenge. First, the modeling mismatch problems inherent to RL can
potentially be mitigated by the caution and probing effects of stochastic
optimal control. Caution imposes restrictions on the RL agent behavior under
uncertainty and modelling mismatch, acting as a safeguard against false
perception. Moreover, the adaptability and continuous learning of an RL agent,
to correct the modelling uncertainty, can be achieved by the means of probing.
Second, RL, possibly together with neural nets [20] as function approximators,
can be used to mitigate the computational burden of stochastic optimal
control. These hypothesized mutual benefits serve as the motivation for the
work we present here.

Early work in the RL community recognized the need for stochastic policies
when the agent has restricted or distorted access to the states [15]. The
randomness introduced by stochastic policies diversifies chosen actions and
hence achieves “artificial probing,” in a sense analogous to persistence of
excitation in control theory and system identification [22]. This random way
of achieving learning, in addition to not being necessarily effective in
general, can render systems unsafe and even unstable. In this paper, we employ
a learning architecture that addresses the fragility of RL due to
uncertainties in modeling and tries to mitigate the computational challenges
associated with stochastic optimal control. Therefore, we seek a controller
which, unlike those that employ stochastic policies, seeks effective probing
when learning is needed, and does so cautiously: respecting safety and
performance conditions. We use an extended Kalman filter (EKF) to track
approximates of system’s uncertainties, and we build RL on the resulting
uncertainty propagation dynamics of the filter. We use the deep deterministic
policy gradient approach to RL [20], which utilizes the policy gradient
theorems [29, 17]. We then deploy our approach on a problem carefully designed
to reflect the nuances of stochastic control to test the effectiveness of our
RL approach under uncertainties.

##  II Problem Formulation

Consider a class of discrete-time nonlinear systems described $\forall
k\in\mathbb{N}$ by,

$\displaystyle x_{k+1}$ $\displaystyle=f(x_{k},u_{k})+w_{k},$ (1a)
$\displaystyle y_{k}$ $\displaystyle=g(x_{k})+v_{k},$ (1b)

where $x_{k}\in\mathbb{R}^{r_{x}}$ is the state, $u_{k}\in\mathbb{R}^{r_{u}}$
is the control input, $y_{k}\in\mathbb{R}^{r_{y}}$ is the output signal, and
$w_{k}\in\mathbb{R}^{r_{x}}$, $v_{k}\in\mathbb{R}^{r_{y}}$ are exogenous
disturbances. The stochastic processes, $\\{v_{k}\\}$ and $\\{w_{k}\\}$, are
assumed to be independent and identically distributed (i.i.d.) with
continuously differentiable densities of zero means and covariances
$\Sigma_{w}$ and $\Sigma_{v}$, respectively. These sequences are independent
from each other and from $x_{0}$, the initial state, which has a continuously
differentiable density $\pi_{0\mid 0}$. The functions $f(\cdot,\cdot)$ and
$g(\cdot)$ are well-defined and continuously differentiable with respect to
their arguments.

The primary goal of this work is to construct a causal control law, i.e., a
control law that is only dependent upon the data accessible up until the
moment of evaluating the control action. That is,
$u_{k}=u_{k}(\mathcal{Z}_{k})$, where
$\mathcal{Z}_{k}=\\{y_{0},\ldots,y_{k},u_{0},\ldots,u_{k-1},\pi_{0\mid 0}\\}$.
This law has to minimize the cost functional

$\displaystyle
J=\mathbb{E\,}\left\\{\sum_{k=0}^{N}\gamma^{k}\ell_{k}(x_{k},u_{k})\right\\},$
(2)

while satisfying the input constraints $u_{k}\in\mathbb{U}$, and with some
acceptable chance probability, $1-\epsilon$, satisfying the state constraints
$x_{k}\in\mathbb{X}$, with $\epsilon\in[0,1)$. The discount factor
$\gamma\in(0,1)$, and the stage costs,
$\ell_{k}:\mathbb{R}^{r_{x}}\times\mathbb{R}^{r_{u}}\to\mathbb{R}$, are
continuously differentiable in their second arguments. The expectation and
constraint satisfaction probabilities are taken with respect to all the random
variables, i.e., $x_{0}$, $w_{k}$, and $v_{k}$, for all $k$.

We make no distinction between states and parameters. Since the formulation is
nonlinear, if the original system has unknown or time-varying parameters, we
use the concept of state augmentation [16, p. 281]. That is, the parameters
are included in the state vector and the resulting augmented system is again
described by (1), which then can be used for simultaneous parameters learning
and control [5].

##  III Background: stochastic optimal control

The vector $x_{k}$ in (1a) retains its Markovian property due to the whiteness
of $\\{w_{k}\\}_{k}$. Moreover, the observation $y_{k}$ is conditionally
independent when conditioned on $x_{k}$; $\\{v_{k}\\}_{k}$ in (1) is also
white. These assumptions are typical in partially observable Markov decision
processes [6]. Under these conditions, the state $x_{k}$ cannot be directly
accessed; it can only be inferred through the observation $y_{k}$, which
typically is not equal to $x_{k}$. The vector $x_{k}$ is only a state in the
Markovian sense, that is

$p(x_{k+1}\mid x_{k},x_{k-1},\ldots,x_{0},u_{k},\ldots,u_{0})=p(x_{k+1}\mid
x_{k},u_{k}).$

For a decision maker or a control designer (or the learner as in [15]), an
alternative “state” is required. That is, from a practical standpoint, the
minimal accessible piece of information adequate to reason about the system’s
future safety and performance. Consequently, this discussion gives rise to the
concept of the information state, which, at time-$k$, is the state filtered
density function $\pi_{k\mid k}=p(x_{k}\mid\mathcal{Z}_{k})$ [18]. As an
“informative statistic,” a term used by [27] roughly means a statistic that is
sufficiently informative to enable a desired control objective. However, the
information state is typically infinite dimensional, which renders its
applicability infeasible, computationally. In the next subsections, we shall
explain the sources of this infeasibility and provide a framework to alleviate
them.

###  III-A Separation

Adopting the information state $\pi_{k\mid k}$, a causal controller has the
form $u_{k}=u_{k}(\pi_{k\mid k})$. This formulation of the control law allows
the interpretation of stochastic optimal control as comprising two distinct
steps [10, ch. 25]:

  * •

Tracking $\pi_{k\mid k}$, that is, a Bayesian filter that propagates the
information state [18].

  * •

A law that assigns a value $u_{k}$ to each information state provided by the
filter, such that this law minimizes (2).

In the linear Gaussian state-space model case, the information state takes an
equivalent finite dimensional characterization: the state conditional mean and
covariance. If the system is unconstrained and $\ell_{k}$s are quadratic, the
optimal control is indifferent to the state covariance and is only a function
of the mean. This explains the separation principle in LQG control design [3,
ch. 8]. This separation principle differs from that in the realm of stochastic
optimal control. The latter denotes the two-step interpretation listed above.

As pointed out by [30], tracking the information state $\pi_{k\mid k}$ does
not solve the problem; a convenient approximation to the Bayesian filter is
typically less cumbersome than finding the stochastic optimal control. The
next subsection is a brief introduction to the Bayesian filter, which is then
used to construct the dynamic programming equation for the stochastic case.

###  III-B Bayesian Filter

The system (1) can be equivalently described by, $\forall k\in\mathbb{N}$,

$\displaystyle x_{k+1}$ $\displaystyle\sim p(x_{k+1}\mid x_{k},u_{k}),$
$\displaystyle y_{k}$ $\displaystyle\sim p(y_{k}\mid x_{k}),$

similar to [25] due to the whiteness of $w_{k}$ and $v_{k}$. The notation
$p(\cdot)$ denotes different density functions and will be identified by its
arguments.

The information state can be propagated, at least in principle, through the
Bayesian filter, which consists of the following two steps:

  1. 1.

Time Update:

$\displaystyle p(x_{k+1}\mid u_{k},\mathcal{Z}_{k})$ $\displaystyle=$
$\displaystyle\hskip-28.45274pt\int{p(x_{k+1}\mid
u_{k},x_{k})p(x_{k}\mid\mathcal{Z}_{k})\,\textrm{d}x_{k}}.$ (3)

  2. 2.

Measurement Update:

$\displaystyle p(x_{k+1}\mid\mathcal{Z}_{k+1})$ $\displaystyle=$
$\displaystyle\hskip-42.67912pt\frac{p(y_{k+1}\mid x_{k+1})p(x_{k+1}\mid
u_{k},\mathcal{Z}_{k})}{\int{p(y_{k+1}\mid x_{k+1})p(x_{k+1}\mid
u_{k},\mathcal{Z}_{k})\,\textrm{d}x_{k+1}}}.$ (4)

Notice that to move from the filtered density at time-$k$ to $k+1$, the values
of $u_{k}$ and $y_{k+1}$ are used. In order to simplify the notation,
$\pi_{k\mid k}=p(x_{k}\mid\mathcal{Z}_{k})$ and $\pi_{k+1\mid k}=p(x_{k+1}\mid
u_{k},\mathcal{Z}_{k})$, define the mapping

$\pi_{k+1\mid k+1}=T(\pi_{k\mid k},u_{k},y_{k+1}),$ (5)

where $T$ maps $\pi_{k\mid k}$ to $\pi_{k+1\mid k}$ using $u_{k}$ in (3), then
to $\pi_{k+1\mid k+1}$ using $y_{k+1}$ in (4). In the next section we seek to
approximate the above two steps by the EKF, which propagates approximations of
the first two moments of $\pi_{k\mid k}$ [2].

###  III-C Stochastic Dynamic Programming

A causal control law uses only the available information up to the moment of
evaluating this law. In accordance with the principle of optimality, when
making the final control decision, denoted as $u_{N-1}$, and given the
available information then $\mathcal{Z}_{N-1}$, the optimal cost can be
determined as follows

$\displaystyle\min_{u_{N-1}\in\mathbb{\bar{U}}(\pi_{N-1\mid
N-1})}\mathbb{E\,}\Big{\\{}$ $\displaystyle\ell_{N-1}(x_{N-1},u_{N-1})+$
$\displaystyle\hskip 19.91692pt\gamma\ell_{N}(x_{N})\mid
u_{N-1},\mathcal{Z}_{N-1}\Big{\\}},$

where the expectation is with respect to $w_{N-1},\,x_{N-1}$ and $v_{N}$. The
set $\mathbb{\bar{U}}(\pi_{N-1\mid N-1})$ contains the control inputs in
$\mathbb{U}$ such that they result in $\mathbb{P}(x_{N}\in\mathbb{X})\geq
1-\epsilon$. Notice that the optimal cost above is solely a function of the
information state $\pi_{N-1\mid N-1}$; the random vectors $v_{N}$ and
$w_{N-1}$ have known densities and are marginalized over via the expectation,
and $u_{N-1}$ is the decision variable of the minimization. Writing explicitly
the optimal cost as a function of the information state

$\displaystyle V_{N-1}(\pi_{N-1\mid N-1})=$ $\displaystyle\hskip
8.53581pt\min_{u_{N-1}}\mathbb{E\,}\left\\{\ell_{N-1}(x_{N-1},u_{N-1})+\gamma\ell_{N}(x_{N})\mid
u_{N-1},\mathcal{Z}_{N-1}\right\\}.$

Define $V_{N}(\pi_{N\mid
N})=\mathbb{E\,}\left\\{\ell_{N}(x_{N})\mid\mathcal{Z}_{N}\right\\}$, then

$\displaystyle V_{N-1}(\pi_{N-1\mid N-1})$
$\displaystyle=\min_{u_{N-1}}\mathbb{E\,}\Big{\\{}\ell_{N-1}(x_{N-1},u_{N-1})+$
$\displaystyle\hskip-8.53581pt\gamma V_{N}(T(\pi_{N-1\mid
N-1},u_{N-1},y_{N}))\Big{\\}}.$ (6)

A complete version of this derivation is outlined in [18]. This recursion
holds for $k=0,1,\ldots,N-1$, going backwards from the terminal boundary
condition $V_{N}(\pi_{N\mid N})$. This is the stochastic dynamic programming
equation, through which, a value $u_{k}$ is assigned to each information state
$\pi_{k\mid k}$.

Except for the simplest cases, solving the stochastic dynamic programming
equation is computationally prohibitive, primarily because of the infinite
dimensionality of the information state. In the next section, we approximate
the Bayesian filter by the EKF. This is primarily due to the finite
dimensional representation of the information state it offers, which also
tends to be practically convenient for variety of applications. Although this
approximation is of a vastly reduced dimensionality, it is still of a
relatively high dimensionality for problems of interest. We alleviate the
latter burden by the implementation of RL.

##  IV Methodology

In this section we outline the EKF algorithm, and its “wide sense” (mean and
covariance) approximation of the information state. We then adapt the cost in
(2) to the new approximate wide-sense information state. A few, mainly
cosmetic, changes to this adapted cost are implemented to make it align with
the assumptions/notation of the RL algorithm which will be outlined
subsequently.

###  IV-A EKF

We replace the infinite dimensional information state $\pi_{k\mid k}$ by a
finite dimensional approximate one, namely, the state conditional mean vector
$\hat{x}_{k\mid k}$ and covariance matrix $\Sigma_{k\mid k}$.

Let

$\displaystyle\hat{x}_{k\mid k}$
$\displaystyle=\mathbb{E\,}\left\\{x_{k}\mid\mathcal{Z}_{k}\right\\},\quad\hat{x}_{k\mid
k-1}=\mathbb{E\,}\left\\{x_{k}\mid u_{k-1},\mathcal{Z}_{k-1}\right\\},$
$\displaystyle\Sigma_{k\mid k}$
$\displaystyle=\mathbb{E\,}\left\\{(x_{k}-\hat{x}_{k\mid
k})(x_{k}-\hat{x}_{k\mid k})^{\top}\mid\mathcal{Z}_{k}\right\\},$
$\displaystyle\Sigma_{k\mid k-1}$
$\displaystyle=\mathbb{E\,}\left\\{(x_{k}-\hat{x}_{k\mid
k-1})(x_{k}-\hat{x}_{k\mid k-1})^{\top}\mid
u_{k-1},\mathcal{Z}_{k-1}\right\\}.$

The EKF, similarly to the Bayesian filter, consists of the following two major
steps:

  1. 1.

Measurement-update

$\displaystyle\hat{x}_{k\mid k}$ $\displaystyle=\hat{x}_{k\mid
k-1}+L_{k}\left(y_{k}-g(\hat{x}_{k\mid k-1})\right),$
$\displaystyle\Sigma_{k\mid k}$ $\displaystyle=\Sigma_{k\mid
k-1}-L_{k}H_{k}\Sigma_{k\mid k-1}.$

  2. 2.

Time-update

$\displaystyle\hat{x}_{k+1\mid k}$ $\displaystyle=f(\hat{x}_{k\mid k},u_{k}),$
$\displaystyle\Sigma_{k+1\mid k}$ $\displaystyle=F_{k}\Sigma_{k\mid
k}F_{k}^{\top}+\Sigma_{w}.$

which can be combined to write,

$\displaystyle\hat{x}_{k+1\mid k+1}$ $\displaystyle=f(\hat{x}_{k\mid
k},u_{k})+L_{k+1}\left(y_{k+1}-g(\hat{x}_{k+1\mid k})\right),$
$\displaystyle\Sigma_{k+1\mid k+1}$
$\displaystyle=\left(I-L_{k+1}H_{k+1}\right)\left(F_{k}\Sigma_{k\mid
k}F_{k}^{\top}+\Sigma_{w}\right),$

where

$\displaystyle L_{k}$ $\displaystyle=\Sigma_{k\mid
k-1}H_{k}^{\top}\left(H_{k}\Sigma_{k\mid
k-1}H_{k}^{\top}+\Sigma_{v}\right)^{-1},$ $\displaystyle F_{k}$
$\displaystyle=\left.\frac{\partial f(x,u_{k})}{\partial
x}\right|_{x=\hat{x}_{k\mid k}},\quad H_{k}=\left.\frac{\partial
h(x)}{\partial x}\right|_{x=\hat{x}_{k\mid k-1}},$

and $\hat{x}_{0\mid 0}$, $\Sigma_{0\mid 0}$ are the initial state $x_{0}$ mean
and covariance.

In general, the above conditional means and covariances are not exact; the
state conditional densities $\pi_{k\mid k}$ are non-Gaussian due to the
nonlinearities. Hence, $\hat{x}_{k\mid k}$ and $\Sigma_{k\mid k}$ are merely
approximations to the conditional mean and covariance of $x_{k}$[2]. Define

$\displaystyle\hat{\pi}_{k+1}=\hat{T}(\hat{\pi}_{k},u_{k},y_{k+1}),$ (7)

where $\hat{\pi}_{k}=\\{\hat{x}_{k\mid k},\Sigma_{k\mid k}\\}$. Here $\hat{T}$
is a surrogate approximate mapping to $T$ in (5). The mapping $\hat{T}$
applies the above steps of the EKF to $\hat{x}_{k\mid k},\Sigma_{k\mid k}$,
using $u_{k}$ and $y_{k+1}$, and generates $\hat{x}_{k+1\mid k+1}$ and
$\Sigma_{k+1\mid k+1}$.

###  IV-B Cost

The first two moments provided by the EKF are sufficient to evaluate the
expectation of the finite-horizon cost function in (2), given that the
$\ell_{k}$s are quadratic. If not, the $\ell_{k}$s can be replaced by their
second order Taylor expansion. That is, if
$\ell_{k}(x_{k},u_{k})=x_{k}^{\top}Q_{k}x_{k}+u_{k}^{\top}R_{k}u_{k}$ for
$k=0,\ldots,N$, the cost (2)

$\displaystyle J$
$\displaystyle=\mathbb{E\,}\Bigg{\\{}\sum_{k=0}^{N}x_{k}^{\top}Q_{k}x_{k}+u_{k}^{\top}R_{k}u_{k}\Bigg{\\}},$
$\displaystyle=\mathbb{E\,}\Bigg{\\{}\sum_{k=0}^{N}\left(\hat{x}_{k\mid
k}+\tilde{x}_{k}\right)^{\top}Q_{k}\left(\hat{x}_{k\mid
k}+\tilde{x}_{k}\right)+u_{k}^{\top}R_{k}u_{k}\Bigg{\\}},$

where $\tilde{x}_{k}=x_{k}-\hat{x}_{k\mid k}$, and hence, cross-terms vanish
under expectation, so we have

$J=\mathbb{E\,}\Bigg{\\{}\sum_{k=0}^{N}\hat{x}_{k\mid
k}^{\top}Q_{k}\hat{x}_{k\mid k}+\text{trace}(Q_{k}\Sigma_{k\mid
k})+u_{k}^{\top}R_{k}u_{k}\Bigg{\\}},$ (8)

since
$\mathbb{E\,}\\{\tilde{x}_{k}^{\top}Q_{k}\tilde{x}_{k}\\}=\text{trace}(Q_{k}\Sigma_{k\mid
k})$.

If the stage costs are not quadratic in $x_{k}$, we use their second order
Taylor expansion. For a fixed $u_{k}\in\mathbb{U}$,

$\displaystyle\ell_{k}(x_{k},u_{k})$
$\displaystyle\approx\ell_{k}(\hat{x}_{k\mid
k},u_{k})+G_{k}(u_{k})\tilde{x}_{k}+\tilde{x}_{k}^{\top}C_{k}(u_{k})\tilde{x}_{k},$

where

$\displaystyle G_{k}(u_{k})=\left.\frac{\partial\ell_{k}(x,u_{k})}{\partial
x}\right|_{x=\hat{x}_{k\mid
k}},C_{k}(u_{k})=\left.\frac{\partial^{2}\ell_{k}(x,u_{k})}{\partial
x^{2}}\right|_{x=\hat{x}_{k\mid k}}.$

Substituting back in (2) yields the approximate cost function

$\displaystyle\hat{J}(\pi_{0\mid 0})$
$\displaystyle=\mathbb{E\,}\Bigg{\\{}\sum_{k=0}^{N}\ell_{k}\left(\hat{x}_{k\mid
k},u_{k}\right)+\text{trace}\left(C_{k}(u_{k}\right)\Sigma_{k\mid
k})\Bigg{\\}}.$ (9)

The linear term of the expansion vanishes, it is affine in $\tilde{x}_{k}$
which has zero mean.

###  IV-C Constraints for Safety

Two types of constraints can be considered: probabilistic constraints of
polyhedral sets and probabilistic constraints of sets described by grids. The
latter can handle more complicated geometries. Each type is handled and
implied separately from the other, and only separate, not joint, probabilistic
guarantees are provided.

####  IV-C1 Polyhedral Constraints

Given the following state constraint set

$\displaystyle\mathbb{X}=\\{x_{k}\in\mathbb{R}^{r_{x}}|Tx_{k}\leq\bar{x}\\},\,\bar{x}\in\mathbb{R}^{t},$
(10)

where $T\in\mathbb{R}^{t\times r_{x}}$ have full row rank. The cost function
(2) is to be minimized subject to $u_{k}\in\mathbb{U}$ for $k=0,\ldots,N-1$,
and to the probabilistic constraints

$\displaystyle\mathbb{P}(x_{k}\in\mathbb{X}\mid\mathcal{Z}_{k})\geq
1-\epsilon,$ (11)

for all $k=1,\ldots,N$. The probability measure
$\mathbb{P}(\cdot\mid\mathcal{Z}_{k})$ corresponds to $x_{k}$ distributed
according to the density $\pi_{k\mid k}=p(x_{k}\mid\mathcal{Z}_{k})$. The
constant $\epsilon\in[0,1)$ is the tolerance, or the acceptable constraint
violation rate.

Using the approximation of the first two moments of the state, the
probabilistic constraints in (11) can be shown to be implied by deterministic
linear constraints. This replacement of the probabilistic constraints with
deterministic ones, with tighter constraints, forms the bases of tube-based
stochastic Model Predictive Control methods [31, 8].

######  Lemma 1.

(Cantelli’s inequality) For a scalar random variable $\gamma$ with mean
$\hat{\gamma}$ and variance $\Gamma$,

$\mathbb{P}(\gamma-\hat{\gamma}\geq\eta)\leq\frac{\Gamma}{\Gamma+\eta^{2}},\,\eta\geq
0.$ (12)

∎

######  Lemma 2.

For $j=1,\ldots,t$, let $T(j)$ be the $j^{\textit{th}}$ row of $T$ and
$\bar{x}(j)$ be the $j^{\textit{th}}$ element of $\bar{x}$. The probabilistic
constraints

$\displaystyle\mathbb{P}\Big{(}T(j)x_{k}\leq\bar{x}(j)\mid\mathcal{Z}_{k}\Big{)}\leq
1-\frac{\epsilon}{t},$ (13)

are implied by

$T(j)\hat{x}_{k\mid
k}\leq\bar{x}(j)-\sqrt{\frac{t-\epsilon}{\epsilon}}\sqrt{T(j)\Sigma_{k\mid
k}T(j)^{\top}}.$ (14)

###### Proof.

This result is analogous to that in [11], only the probability measure is
replaced by a conditional one. ∎

######  Lemma 3.

Let $(\Omega,\mathcal{B},\mathbb{P})$ be a probability space and
$E_{i}\in\mathcal{B}$ for $i=1,\ldots,n$. If $\mathbb{P}(E_{i})\geq
1-\epsilon/n$, for all $i=1,\ldots,n$, then
$\mathbb{P}(\bigcap_{i=1}^{n}E_{i})\geq 1-\epsilon$. ∎

######  Proposition 1.

The following deterministic polyhedral constraints

$\displaystyle T\hat{x}_{k\mid
k}\leq\bar{x}-\sqrt{\frac{t-\epsilon}{\epsilon}}\sqrt{\mathrm{diag}(T\Sigma_{k\mid
k}T^{\top})},$ (15)

imply the probabilistic constraints in (10), where: $t$ is the number of rows
of $T$, the square root is defined element-wise, and the function
$\textrm{diag}(\cdot)$ maps a matrix to its diagonal terms.

###### Proof.

Notice that the state constraint sets in (10) can be written as intersection
of sets

$\displaystyle\mathbb{X}$
$\displaystyle=\\{x_{k}\in\mathbb{R}^{r_{x}}|Tx_{k}\leq\bar{x}_{k}\\},$
$\displaystyle=\bigcap_{j=1}^{\top}\\{x_{k}\in\mathbb{R}^{r_{x}}|T(j)x_{k}\leq\bar{x}_{k}(j)\\},$

since all rows are to be enforced simultaneously [21]. By Lemma 3,
$\mathbb{P}(x_{k}\in\mathbb{X}_{k}\mid\mathcal{Z}_{k})\geq 1-\epsilon$ is
implied by
$\mathbb{P}(\\{x_{k}\in\mathbb{R}^{r_{x}}|T(j)x_{k}\leq\bar{x}_{k}(j)\\}\mid\mathcal{Z}_{k})\geq
1-\epsilon/t$. The latter is implied by (14) in Lemma 2. Stacking the
inequalities in (14) for all of the $t$ rows of $T$, we get (15). Notice that
with an increase in the number of rows $t$, the constraints become tighter and
the approximation more conservative. ∎

######  Remark 1.

Proposition 1 is when the sets described by the rows $Tx_{k}\leq\bar{x}$ are
to be satisfied jointly [14], which results in further constraints tightening
in Lemma 3. If this is to be relaxed to satisfying these sets separately,
condition in (15) can be replaced by the condition

$T\hat{x}_{k\mid
k}\leq\bar{x}-\sqrt{\frac{1-\epsilon}{\epsilon}}\sqrt{\mathrm{diag}(T\Sigma_{k\mid
k}T^{\top})}.$

$\square$

####  IV-C2 Grid-based Constraints

For state constraint sets of more complicated geometries, we use a grid of
nodes representing the sets that the state is to avoid. These nodes can be
generated, for instance, through rejection sampling using a uniform proposal
density enveloping these sets.

Let $\Xi\subset\mathbb{R}^{r_{x}}$, a subset in the state-space, be the set to
be avoided with high probability. That is,

$\mathbb{P}(x_{k}\notin\Xi\mid\mathcal{Z}_{k})=1-\epsilon.$ (16)

If $\mathbb{G}=\\{\xi_{j},\,j=1,\ldots,L\\}$ is a set of points, forming a
grid in $\Xi$, we can replace the probabilistic constraint (16), by one
described by the grid, by letting every point in the grid be an outlier with
respect to the density $\pi_{k\mid k}$. For the purpose of identifying a point
as an outlier, we apply the Mahalanobis distance [7], using the conditional
mean $\hat{x}_{k\mid k}$ and covariance $\Sigma_{k\mid k}$ provided by the
EKF. This distance is defined as

$\displaystyle d_{k}(z)=\sqrt{(z-\hat{x}_{k\mid k})^{\top}\Sigma_{k\mid
k}^{-1}(z-\hat{x}_{k\mid k})}.$

Therefore, we replace (16) with

$d_{k}(\xi_{j})>\delta,\,j=1,\ldots,L,$

where $\delta>0$ can be related to an ellipsoidal confidence region about the
mean $\hat{x}_{k\mid k}$, as in [12]. For example, a Mahalanobis distance of 2
for a univariate standard normal density corresponds to the two standard
deviations confidence region about its mean. However, relating the Mahalanobis
distance to probability is not clear. Probability is defined over sets, while
Mahalanobis distance is over points. We can mitigate this problem by taking
$\delta$ sufficiently large or having it as a hyper parameter to be tuned
during simulation phase.

We assume the points of the grid are dense enough such that the ellipsoid
defined by $x$ and $\delta$, $d_{k}(x)=\delta$, under any isometry, cannot be
contained in $\Xi$ while it contains no points of the grid. In other word,
this ellipsoid cannot be “squeezed” between points of the grid. Therefore, the
amount of uncertainty dictates the density of sampling required to represent
irregular sets. If the uncertainty is large, this ellipsoid is large, and
hence, the gird can be less dense.

####  IV-C3 Soft Constraints

The following numbers, representing the state and input violations count, are
added as a penalty, with a Langrange multiplier-like expression, to the cost
function

$\displaystyle\mathcal{A}_{k}^{1}$ $\displaystyle=1\Big{\\{}T\hat{x}_{k\mid
k}>\bar{x}-\sqrt{\frac{t-\epsilon}{\epsilon}}\sqrt{\text{diag}(T\Sigma_{k\mid
k}T^{\top})}\Big{\\}},$ (17) $\displaystyle\mathcal{A}_{k}^{2}$
$\displaystyle=1\Big{\\{}d_{k}(\xi_{j})>\delta,\,j=1,\ldots,L\Big{\\}},$
$\displaystyle\hskip-8.53581pt\text{for }k=1,2,\ldots,N,$
$\displaystyle\mathcal{A}_{k}^{3}$
$\displaystyle=1\Big{\\{}u_{k}\in\mathbb{U}\Big{\\}},$
$\displaystyle\hskip-8.53581pt\text{for }k=1,2,\ldots,N-1,$

such that the cost becomes

$\displaystyle\bar{J}(\pi_{0\mid 0},u_{0:N-1})$
$\displaystyle=\mathbb{E\,}\left\\{\sum_{k=0}^{N}\gamma^{k}\bar{\ell}_{k}(x_{k},u_{k})\right\\},$
(18)

where
$\bar{\ell}_{k}(x_{k},u_{k})=\ell_{k}(x_{k},u_{k})+\lambda\mathcal{A}_{k}$,
$\mathcal{A}_{k}=\mathcal{A}_{k}^{1}+\mathcal{A}_{k}^{2}+\mathcal{A}_{k}^{3}$,
and $\lambda$ is large positive number, acting as a Langrange multiplier.

The hard input constraint $u_{k}\in\mathbb{U}$, instead, can be enforced by
limiting the control law to a specific family, for instance, using a saturated
parameterized family for a rectangular $\mathbb{U}$. However, the input
constraint penalty $\mathcal{A}_{k}^{3}$ can be practical for more complicated
input constraint set $\mathbb{U}$.

###  IV-D Deterministic Policy Gradient

RL is an umbrella of algorithms that are rooted in the concept of stochastic
approximation [6, 28, 24]. The main objective of these algorithms is to solve
optimal control problems through simulating interactions between the
controller and the environment. Among the numerous algorithms within the scope
of RL, we opt for the Deterministic Policy Gradient algorithm [26], in
particular, its deep neural net implementation [20]. While we find this
algorithm convenient within the context of this paper—primarily due to its
ability to handle continuous action spaces—our choice does not impose strong
preferences on the selection of other RL algorithms.

####  IV-D1 Reward Signal and the Infinite Horizon Cost

The convention in RL literature is to deal with rewards, typically in
infinite-horizon, rather than finite-horizon costs as in model predictive
controllers. This adaptation is straight-forward, the reward signal can be
defined as a negative saturated/bounded version of the stage-cost,
$\bar{\ell}$. This saturation is done for two reasons. The first is to
guarantee the convergence of the value function [6, ch. 7], hence, the
infinite-horizon stochastic DPE as $N\to\infty$ is valid. From numerical
stability perspective, to avoid exploding gradients, this will prove
beneficial in the learning step of RL. The negative sign is to switch from the
cost-minimization convention in optimal control to value-maximization in RL.
Let

$\displaystyle
r(\hat{\pi}_{k},u_{k})=-\max\left\\{\mathbb{E\,}\bar{\ell}(x_{k},u_{k}),M\right\\},$

where $M<\infty$. Consequently, the new form of the DPE in (6) is

$\displaystyle\bar{V}_{N-1}(\hat{\pi}_{N-1})$
$\displaystyle=\max_{u_{N-1}}\Big{\\{}r(\hat{\pi}_{N-1},u_{N-1})+$
$\displaystyle\hskip-8.53581pt\gamma\mathbb{E\,}\bar{V}_{N}(T(\pi_{N-1},u_{N-1},y_{N}))\Big{\\}}.$

As discussed above, by letting $N\to\infty$, $\bar{V}_{N}\to\bar{V}$, we have

$\displaystyle\bar{V}(\hat{\pi}_{k})$
$\displaystyle=\max_{u_{k}}\Big{\\{}r(\hat{\pi}_{k},u_{k})+\gamma\mathbb{E\,}\bar{V}(T(\pi_{k},u_{k},y_{k+1}))\Big{\\}}.$

To unify with RL notation, the state-action value function $Q$ [6],

$\displaystyle
Q(\hat{\pi}_{k},u_{k})=r(\hat{\pi}_{k},u_{k})+\gamma\mathbb{E\,}\left(Q(\hat{T}(\hat{\pi}_{k},u_{k},y_{k+1})\right).$

We use a parameterized control policy $u_{k}=\mu_{\theta}(\hat{\pi}_{k})$, a
neural net in this paper, and $\theta$ denotes the set of gains and biases of
this net. If the total accumulated reward of this policy is

$\displaystyle J_{\theta}(\hat{\pi}_{0})$
$\displaystyle=\mathbb{E\,}_{\mu_{\theta}}\Bigg{\\{}\sum_{k=0}^{\infty}\gamma^{k}r(\hat{\pi}_{k},\mu_{\theta}(\hat{\pi}_{k})\Bigg{\\}},$

where $\mathbb{E\,}_{\mu_{\theta}}$ corresponds to a probability measure
$\mathbb{P}_{\mu_{\theta}}$ defined over all the possible trajectories of
$\hat{\pi}_{k}$s under the policy $\mu_{\theta}$.

The policy gradient theorems seek to find a description of the gradient
$\nabla_{\theta}J_{\theta}$ which is convenient for computation. The
Deterministic Policy Gradient Theorem of [26], adapted for the case of
stochastic Dynamic Programming, provides the following identity

$\displaystyle\nabla_{\theta}J_{\theta}=\mathbb{E}_{\mu_{\theta}}\Big{[}\nabla_{u}Q(\hat{\pi},u)\nabla_{\theta}\mu_{\theta}(\hat{\pi})\Big{]},$

given the assumptions listed in Section II, $r(\hat{\pi}_{k},u_{k})$ is
continuously differentiable in $u_{k}$ almost everywhere, and the Jacobian
matrix $\nabla_{\theta}\mu_{\theta}(\hat{\pi})$ is continuous in $\hat{\pi}$.
These conditions imply the satisfaction of Assumption A.1 in [26], almost-
surely-$\mathbb{P}_{\mu_{\theta}}$.

In the deep deterministic policy gradient (DDPG) algorithm [20], $Q$ is
approximated by a neural net $Q_{\psi}$ with parameters $\psi$ updated via
temporal difference methods. While the above gradient is used to update the
control policy neural net $\mu_{\theta}$ gains. Algorithm 1 is the DDPG
algorithm adapted for the information state (instead of the state).111The code
of this implementation can be found at: https://github.com/msramada/Active-
Learning-Reinforcement-Learning It does not include the target networks as in
[20], which can be augmented to Algorithm 1 to improve learning stability.

Algorithm 1 Actively Learning RL via DDPG

Randomly initialize the weights $\theta,\,\psi$ of the neural nets $Q_{\psi}$
and $\mu_{\theta}$;

Initialize replay buffer $\mathcal{R}$;

for $\text{episode}=1,2,\ldots$ do

Randomly sample an initial information state
$\hat{\pi}_{0}=\\{\hat{x}_{0},\Sigma_{0}\\}$ and a true state $x_{0}$;

for $k=0,\ldots,N-1$ do

Sample control actions $u_{k}=\mu_{\theta}(\hat{\pi}_{k})+\eta$ where $\eta$
is an exploration noise;

Apply $u_{k}$ in (1a) to sample the true $x_{k+1}$;

Using $x_{k+1}$ in (1b), sample the true $y_{k+1}$;

Using $\hat{\pi}_{k}$, $u_{k}$ and $y_{k+1}$, evaluate $\hat{\pi}_{k+1}$ using
(7);

Calculate the reward $r(\hat{\pi}_{k},u_{k})$;

Store the tuple $(\hat{\pi}_{k},u_{k},r(\hat{\pi}_{k},u_{k}),\hat{\pi}_{k+1})$
in $\mathcal{R}$;

Sample a minibatch
$\\{(\hat{\pi}_{i},u_{i},r(\hat{\pi}_{i},u_{i}),\hat{\pi}_{i+1}),\,i=1,\ldots,M\\}$
of $\mathcal{R}$;

Set $z_{i}=r(\hat{\pi}_{i},u_{i})+\gamma
Q_{\psi}(\hat{\pi}_{i+1},\mu_{\theta}(\hat{\pi}_{i+1}))$;

Update the critic network $Q_{\psi}$ by minimizing the loss
$\frac{1}{M}\sum_{i=1}^{M}\left(z_{i}-Q_{\psi}(\hat{\pi}_{i},u_{i})\right)^{2}$,
w.r.t. $\psi$;

Update the policy network $\mu_{\theta}$ using the sample average policy
gradient
$\nabla_{\theta}J_{\theta}\approx\frac{1}{M}\sum_{i=0}^{M}\nabla_{u}Q_{\psi}(\hat{\pi}_{i},u)\mid_{u=\mu_{\theta}(\hat{\pi}_{i})}\nabla_{\theta}\mu_{\theta}(\hat{\pi}_{i});$

end for

end for

######  Remark 2.

The information state $\hat{\pi}_{k}$ contains repeated elements, since
$\Sigma_{k\mid k}$ is symmetric [2]. We can consider the upper triangular
portion only or the diagonal elements if the cross dependencies are to be
ignored. $\square$

##  V Numerical example

In this section we implement Algorithm 1 on a scalar state-space system with
varying state observability over the state-space $\mathbb{R}$. This simple
example demonstrates the behavior of the RL controller when equipped with
concepts from stochastic control.

Consider this simple integrator with nonlinear measurement equation

$\displaystyle x_{k+1}$ $\displaystyle=x_{k}+u_{k}+w_{k},$ (19) $\displaystyle
y_{k}$ $\displaystyle=\frac{1}{9}x_{k}^{3}+v_{k},$ (20)

where $w_{k}$ and $v_{k}$ obey the assumptions listed under (1), and moreover,
$w_{k}\sim\mathcal{N}(0,\Sigma_{w})$ and
$w_{k}\sim\mathcal{N}(0,\Sigma_{v})$222The notation $\mathcal{N}(\mu,\Sigma)$
denotes a Gaussian density with mean vector $\mu$ and covariance matrix
$\Sigma$., and $\Sigma_{v}=2$, $\Sigma_{w}=2$. We start with this system since
it is unstable and has varying observability.

If $x_{k}$ vanishes, $y_{k}$’s sensitivity with respect to it vanishes too. In
general, the system becomes less observable as $x_{k}$ is close to the origin.
Therefore, the stability of the origin and the observability of the system are
important goals but in conflict. The balance we expect out of a stochastic
dual controller is to drive the state close to the origin, while at the same
time actively gathering information by visiting the more observable outer
neighborhood.

We use a running cost $\ell(x_{k},u_{k})=x_{k}^{2}+u_{k}^{2}$, and a discount
factor $\gamma=0.95$. Together, they construct the cost $J_{\theta}$ and the
state-action value function $Q$. The constraints are
$u_{k}\in\mathbb{U}=[-5,5]$, which we enforce by using saturated parameterized
policy, rather than a Lagrangian penalty term. The latter can be the better
option if $\mathbb{U}$ cannot be enforced as the range of a parameterized
policy.

Deterministic policy gradient methods [26] use the actor-critic learning
architecture: the actor being the control policy, and the critic is its
corresponding policy evaluation in the shape of an action-value function. In
this example, both networks are feedforward neural nets, with one hidden layer
of size $64$. The actor network receives two inputs: the information state
elements $\\{\hat{x}_{k\mid k},\Sigma_{k\mid k}\\}$. The output of this
network is the control $u_{k}$. The critic network, approximating the action
value function, takes three input values: both of the information state
elements as well as the corresponding control action $u_{k}$, and it outputs
$Q(\hat{\pi}_{k},u_{k})$. We use mini-batch learning, with batches of size
$64$ of tuples $(\hat{\pi}_{k\mid
k},u_{k},r_{k},\hat{T}(\hat{\pi}_{k},u_{k},y_{k+1}))$, and with learning rate
$10^{-4}$. Figure 1 shows the convergence of the normalized accumulative
reward. The normalized accumulative reward of value $1$ corresponds to
$J_{\theta}=0$.

Figure 1: The average reward for the last $10$ episodes. Figure 2: LQG
control: The EKF information state $\hat{\pi}_{k}$: the mean $\hat{x}_{k\mid
k}$ and the covariance $\Sigma_{k\mid k}$ are shown in dark blue and pink,
respectively. The brown curve is the true state $x_{k}$. Figure 3: RL dual
control: The EKF information state $\hat{\pi}_{k}$: the mean $\hat{x}_{k\mid
k}$ and the covariance $\Sigma_{k\mid k}$ are shown in dark blue and pink,
respectively. The brown curve is the true state $x_{k}$.

A Linear Quadratic Gaussian (LQG) control is first applied:
$u_{k}=K\hat{x}_{k\mid k}$, where $\hat{x}_{k\mid k}$ is the conditional mean
provided by the EKF and $K$ designed according to $Q^{LQR}=R^{LQR}=1$. The
result of this LQG control is shown in Figure 2, which shows system
instability and filter divergence. The state covariance is blowing up and the
true state is a random walk (system is an integrator with a white noise
disturbance). The concept of filter divergence is inherently qualitative,
making it not only difficult to delineate the conditions causing it, but also
challenging to provide a clear definition. According to [2] and [16], filter
divergence is when the error covariance, $\Sigma_{k\mid k}$, of a Kalman
filter (or an EKF), becomes large and therefore the filter is insensitive to
new measurements. This may result in the filter’s state estimate deviating
significantly from the true state of the actual system. This filter divergence
seen in Figure 2 is caused mainly by the LQG controller insisting on driving
the state to the origin. This issue has been handled by the RL control
resulting from our approach. In Figure 3, this controller does not prioritize
only driving the state estimate to the origin, but also doing so while
conserving some level of observability. This balance between caution and
probing is what results in the overall system stability.

##  VI Conclusion

The presented framework is to produce an RL agent with attributes from
stochastic optimal control. These attributes equip the agent with caution:
safety and probing, i.e., active online learning. This is done via using RL to
solve the stochastic DPE. To track the information state, we use the EKF. If
it performs poorly—that is, it is a poor approximation to the Bayesian
filter—the premise, on which this control design approach is built, is then
inaccurate. This issue can be mitigated by using a filter that is generally
“adequate” for the problem at hand. Some alternatives include: a Gaussian sum
filter [1], or the incorporation of the estimation of higher order modes into
the EKF [23]. Generally, what qualifies as a “sufficient” approximation to the
information state is a rather complicated question.

In addition to the choice of the Bayesian filter approximation, the design of
the reward signal can produce different balances of safety and
exploration/exploitation. For instance,

  * •

Prioritizing filter stability (or its accuracy) by including the true (in
simulation) estimation error or by further penalizing the state covariance
term in the reward signal;

  * •

Substituting fixed or scaled state covariance in operation;

  * •

Tuning the state disturbance $w_{k}$ covariance $\Sigma_{w}$, or in general:
the EKF design.

These are some of the questions we seek to answer in our future research.

## References

  * [1] D. Alspach and H. Sorenson, “Nonlinear bayesian estimation using gaussian sum approximations,” _IEEE transactions on automatic control_ , vol. 17, no. 4, pp. 439–448, 1972.
  * [2] B. D. Anderson and J. B. Moore, _Optimal filtering_. Courier Corporation, 2012.
  * [3] K. J. Åström, _Introduction to stochastic control theory_. Courier Corporation, 2012.
  * [4] K. J. Åström and A. Helmersson, “Dual control of an integrator with unknown gain,” _Computers & Mathematics with Applications_, vol. 12, no. 6, pp. 653–662, 1986.
  * [5] K. J. Åström and B. Wittenmark, “Problems of identification and control,” _Journal of Mathematical analysis and applications_ , vol. 34, no. 1, pp. 90–113, 1971.
  * [6] D. Bertsekas, _Dynamic programming and optimal control: Volume I_. Athena scientific, 2012, vol. 1.
  * [7] R. G. Brereton, “The mahalanobis distance and its relationship to principal component scores,” _Journal of Chemometrics_ , vol. 29, no. 3, pp. 143–145, 2015.
  * [8] M. Cannon, Q. Cheng, B. Kouvaritakis, and S. V. Raković, “Stochastic tube mpc with state estimation,” _Automatica_ , vol. 48, no. 3, pp. 536–541, 2012\.
  * [9] A. Doucet, N. De Freitas, N. J. Gordon _et al._ , _Sequential Monte Carlo methods in practice_. Springer, 2001, vol. 1, no. 2.
  * [10] A. Doucet, S. Godsill, and C. Andrieu, “On sequential monte carlo sampling methods for bayesian filtering,” _Statistics and computing_ , vol. 10, no. 3, pp. 197–208, 2000.
  * [11] M. Farina, L. Giulioni, L. Magni, and R. Scattolini, “A probabilistic approach to model predictive control,” in _52nd IEEE Conference on Decision and Control_. IEEE, 2013, pp. 7734–7739.
  * [12] G. Gallego, C. Cuevas, R. Mohedano, and N. Garcia, “On the mahalanobis distance classification criterion for multidimensional normal distributions,” _IEEE Transactions on Signal Processing_ , vol. 61, no. 17, pp. 4387–4396, 2013.
  * [13] P. Henderson, R. Islam, P. Bachman, J. Pineau, D. Precup, and D. Meger, “Deep reinforcement learning that matters,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 32, no. 1, 2018.
  * [14] T. Homem-de Mello and G. Bayraksan, “Monte carlo sampling-based methods for stochastic optimization,” _Surveys in Operations Research and Management Science_ , vol. 19, no. 1, pp. 56–85, 2014.
  * [15] T. Jaakkola, S. Singh, and M. Jordan, “Reinforcement learning algorithm for partially observable markov decision problems,” _Advances in neural information processing systems_ , vol. 7, 1994.
  * [16] A. H. Jazwinski, _Stochastic processes and filtering theory_. Courier Corporation, 2007.
  * [17] S. M. Kakade, “A natural policy gradient,” _Advances in neural information processing systems_ , vol. 14, 2001.
  * [18] P. R. Kumar and P. Varaiya, _Stochastic systems: Estimation, identification, and adaptive control_. SIAM, 2015.
  * [19] J. M. Lee and J. H. Lee, “An approximate dynamic programming based approach to dual adaptive control,” _Journal of process control_ , vol. 19, no. 5, pp. 859–864, 2009.
  * [20] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra, “Continuous control with deep reinforcement learning,” _arXiv preprint arXiv:1509.02971_ , 2015.
  * [21] J. Luedtke and S. Ahmed, “A sample approximation approach for optimization with probabilistic constraints,” _SIAM Journal on Optimization_ , vol. 19, no. 2, pp. 674–699, 2008.
  * [22] G. Marafioti, R. R. Bitmead, and M. Hovd, “Persistently exciting model predictive control,” _International Journal of Adaptive Control and Signal Processing_ , vol. 28, no. 6, pp. 536–552, 2014.
  * [23] P. Naveau, M. G. Genton, and X. Shen, “A skewed kalman filter,” _Journal of multivariate Analysis_ , vol. 94, no. 2, pp. 382–400, 2005.
  * [24] B. Recht, “A tour of reinforcement learning: The view from continuous control,” _Annual Review of Control, Robotics, and Autonomous Systems_ , vol. 2, pp. 253–279, 2019.
  * [25] T. B. Schön, A. Wills, and B. Ninness, “System identification of nonlinear state-space models,” _Automatica_ , vol. 47, no. 1, pp. 39–49, 2011.
  * [26] D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, and M. Riedmiller, “Deterministic policy gradient algorithms,” in _International conference on machine learning_. Pmlr, 2014, pp. 387–395.
  * [27] C. Striebel, “Sufficient statistics in the optimum control of stochastic systems,” _Journal of Mathematical Analysis and Applications_ , vol. 12, no. 3, pp. 576–592, 1965.
  * [28] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [29] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour, “Policy gradient methods for reinforcement learning with function approximation,” _Advances in neural information processing systems_ , vol. 12, 1999.
  * [30] E. Tse, Y. Bar-Shalom, and L. Meier, “Wide-sense adaptive dual control for nonlinear stochastic systems,” _IEEE Transactions on Automatic Control_ , vol. 18, no. 2, pp. 98–108, 1973.
  * [31] J. Yan and R. R. Bitmead, “Incorporating state estimation into model predictive control and its application to network traffic control,” _Automatica_ , vol. 41, no. 4, pp. 595–604, 2005.


# Sitatapatra: Blocking the Transfer of Adversarial Samples

Ilia Shumailov
University of Cambridge &Xitong Gao11footnotemark: 1
Shenzhen Institutes of Advanced Technology&Yiren Zhao11footnotemark: 1
University of Cambridge &Robert Mullins
University of Cambridge &Ross Anderson
University of Cambridge &Cheng-Zhong Xu
University of Macau  Ilia Shumailov, Xitong Gao and Yiren Zhao contributed
equally to this work.

###### Abstract

Convolutional Neural Networks (CNNs) are widely used to solve classification
tasks in computer vision. However, they can be tricked into misclassifying
specially crafted “adversarial” samples – and samples built to trick one model
often work alarmingly well against other models trained on the same task. In
this paper we introduce Sitatapatra, a system designed to block the transfer
of adversarial samples. We show how Sitatapatra has the potential to serve as
a key and diversifies neural networks, as in cryptography, and provides a
mechanism for detecting attacks. What’s more, when adversarial samples are
detected they can typically be traced back to the individual device that was
used to develop them. The run-time overheads are minimal permitting the use of
Sitatapatra on constrained systems.

##  1 Introduction

Convolutional Neural Networks (CNNs) have achieved revolutionary performance
in vision-related tasks such as segmentation [3], image classification [17],
object detection [30] and visual question answering [2]. It is now inevitable
that CNNs will be deployed widely for a broad range of applications including
both safety-critical and security-critical tasks such as autonomous vehicles
[7], face recognition [31] and action recognition [13].

However, researchers have discovered that small perturbations to input images
can trick CNNs — with classifiers producing results surprisingly far from the
correct answer in response to small perturbations that are not perceptible by
humans. An attacker can thus create adversarial image inputs that cause a CNN
to misbehave. The resulting attack scenarios are broad, ranging from breaking
into smartphones through face-recognition systems [4] to misdirecting
autonomous vehicles through perturbed road signs [6].

The attacks are also practical, because they are surprisingly portable. If
devices are shipped with the same CNN classifier, the attacker only needs to
analyze a single one of them to perform effective attacks on the others.
Imagine a firm that deploys the same CNN on devices in very different
environments. An attacker might not be able to experiment with a security
camera in a bank vault, but if a cheaper range of security cameras are sold
for home use and use the same CNN, he may buy one and generate transferable
adversarial samples using it. What is more, making CNNs sufficiently different
is not straightforward. Recent research teaches that different CNNs trained to
solve similar problems are often vulnerable to the same adversarial samples
[27, 37]. It is clear that we need an efficient way of limiting the
transferability of adversarial samples. And given the complexity of the
scenarios in which sensors operate, the protection mechanism should: _a)_ work
in computationally constrained environments; _b)_ require minimal changes to
the model architecture, and; _c)_ offer a way of building complex security
policies.

In this paper we propose Sitatapatra, a system designed and built to constrain
the transferability of adversarial examples. Inspired by cryptography, we
introduce a notion of key into CNNs that causes each network of the same
architecture to be internally different enough to stop the transferability of
adversarial attacks. We describe multiple ways of embedding the keys and
evaluate them extensively on a range of computer vision benchmarks. Based on
these data, we propose a scheme to pick keys. Finally, we discuss the
scalability of the Sitatapatra defence and describe the trade-offs inherent in
its design.

The contributions of this paper are:

  * •

We introduce Sitatapatra, the first system designed to stop adversarial
samples being transferable.

  * •

We describe how to embed a secret key into CNNs.

  * •

We show that Sitatapatra not only blocks sample transfer, but also allows
detection and attack attribution.

  * •

We measure performance and show that the run-time computational overhead is
low enough (0.6–7%) for Sitatapatra to work on constrained devices.

The paper is structured as follows. Section 2 describes the related work.
Section 3 introduces the methodology of Sitatapatra and presents the design
choices. Section 4 evaluates the system against state-of-the-art attacks on
three popular image classification benchmarks. Section 5 discusses the trade-
offs in Sitatapatra, analyses key diversity and the costs of key change, and
discusses how to deploy Sitatapatra effectively at scale.

##  2 Related Work

Since the invention of adversarial attacks against CNNs [33], there has been
rapid co-evolution of attack and defense techniques in the deep learning
community.

An adversarial sample is defined as a slightly perturbed image
$\hat{\mathbf{x}}$ of the original $\mathbf{x}$, while $\hat{\mathbf{x}}$ and
$\mathbf{x}$ are assigned different classes by a CNN classifier $F$. The
$l^{p}$-norm of the perturbation is often constrained by a small constant
$\epsilon$ such that ${\|\hat{\mathbf{x}}-\mathbf{x}\|}_{p}\leq\epsilon$ and
$0\leq\hat{\mathbf{x}}\leq 1$, where $p$ can be 1, 2, or $\infty$.

The fast gradient sign method (FGSM) [9] is a simple and effective
$L^{\infty}$ attack for finding such samples. FGSM generates
$\hat{\mathbf{x}}$ by computing the gradient of the target class $y$ with
respect to $\mathbf{x}$, and applies a distortion $\epsilon$ for all pixels
against the sign of the gradient direction:

$\hat{\mathbf{x}}=\mathrm{clip}\left(\mathbf{x}+\epsilon\cdot\mathrm{sign}\left(\nabla_{\mathbf{x}}\ell_{y}\left(F\left(x\right)\right)\right)\right),$
(1)

where $\ell_{y}(F(\mathbf{x}))$ denotes the loss of the network output
$F(\mathbf{x})$ for the target class $y$, $\nabla_{\mathbf{x}}(\mathbf{z})$
evaluates the gradient of $\mathbf{z}$ with respect to $\mathbf{x}$, the
$\mathrm{sign}$ function returns the signs $\\{\pm 1\\}$ of the values in its
input tensor, and finally
$\mathrm{clip}(\mathbf{z})=\max(\min(\mathbf{z},1),0)$ constraints each value
to the range of permissible pixel values, i.e. $[0,1]$. An iterative version
of the attack, Projected Gradient Descent (PGD), was later proposed [18].

DeepFool [26] is an attack that iteratively linearizes misclassification
boundaries of the network, and perturbs the image by moving along the
direction that gives the nearest misclassification.

The Carlini & Wagner attack [5] formulates the following optimization problem,
whose solution gives an adversarial sample:

$\min_{\mathbf{x}^{\star}}{\left\|\mathbf{x}^{\star}-\mathbf{x}\right\|}^{2}_{2}+c\cdot
G(\mathbf{x}^{\star}).$ (2)

Here, the first term optimizes the $L^{2}$-distance, while the second term
$G(\mathbf{x}^{\star})=\max(\\{-\kappa\\}\cup\\{\ell_{y^{\prime}}(\mathbf{z})-\ell_{y}(\mathbf{z})\mid
y^{\prime}\neq y,\mathbf{z}=F(\mathbf{x}^{\star})\\})$ minimizes the loss of
classes other than $y$, and $\kappa$ controls the confidence of
misclassification.

Furthermore, it is well-known that adversarial samples demonstrate good
transferability [33, 9, 23], i.e. such samples generated from a model $F$ tend
to remain adversarial for models other than $F$. This is problematic as black-
box attacks may generate strong adversarial inputs, without even requiring any
prior knowledge of the architecture and training procedures of the model under
attack [28]. Table 1 shows that exact scenario — adversarial samples generated
from one model can effectively transfer to another with the same architecture
trained only with different initializations.

Many researchers have proposed defences based on changes to the network
architecture or the training procedure. Random self-ensemble [21] adds noise
to computed features to simulate a random ensemble of models. Deep Defence
[35] incorporates the perturbation required to generate adversarial samples as
a regularization during training, thus making the trained model less
susceptible to adversarial samples. Other methods such as adversarial training
[9], defensive distillation [29] and Bayesian neural networks [22], also
demonstrate good resistance against adversarial samples. The above methods can
produce robust models with greater attack resistance, yet this is often at the
cost of the original model’s accuracy [34]. For this reason, many other
researchers extended the networks to detect adversarial attacks explicitly
[25, 24, 32], but some of these detection methods can add considerable
computational overhead.

LeNet5 MCifarNet ResNet18-Cifar10 Params $S_{\mathsf{Acc}}(\%)$
$T_{\mathsf{Acc}}(\%)$ $\Delta_{\mathsf{Acc}}(\%)$ $l_{2}$ $l_{\infty}$
$S_{\mathsf{Acc}}(\%)$ $T_{\mathsf{Acc}}(\%)$ $\Delta_{\mathsf{Acc}}(\%)$
$l_{2}$ $l_{\infty}$ $S_{\mathsf{Acc}}(\%)$ $T_{\mathsf{Acc}}(\%)$
$\Delta_{\mathsf{Acc}}(\%)$ $l_{2}$ $l_{\infty}$ Clean 99.13 99.25 - - - 89.51
90.14 - - - 91.12 93.58 - - - FGSM $\epsilon=0.02$ 98.20 98.91 0.70 0.42 0.02
17.03 24.22 7.19 0.98 0.02 18.05 50.16 32.11 0.99 0.02 $\epsilon=0.06$ 92.19
96.17 3.98 1.65 0.08 2.89 11.17 8.28 3.67 0.07 4.61 22.66 18.05 3.71 0.07
$\epsilon=0.6$ 0.55 3.59 3.05 11.91 0.59 1.02 7.81 6.80 20.98 0.48 0.00 8.59
8.59 22.07 0.50 DeepFool $i=50$ 14.92 92.03 77.11 1.86 0.44 1.02 27.34 26.33
0.20 0.03 1.02 88.20 87.19 0.16 0.02 $i=10$ 87.73 96.95 9.22 1.76 0.41 1.80
27.34 25.55 0.20 0.03 1.72 88.20 86.48 0.16 0.02 C&W $lr=0.5$ 3.75 86.56 82.81
3.09 0.71 2.03 10.47 8.44 9.86 0.24 0.55 15.00 14.45 10.02 0.24 $lr=1.0$ 1.02
60.86 59.84 4.25 0.76 5.00 11.02 6.02 17.28 0.44 0.62 12.81 12.19 17.75 0.45
C&W $lr=0.5$ 3.91 15.78 11.88 5.12 0.90 2.73 4.69 1.95 15.89 0.52 1.09 10.39
9.30 14.63 0.43 $c=0.999$ $lr=1.0$ 1.09 6.17 5.08 5.75 0.95 5.47 5.23 -0.23
24.27 0.77 1.48 8.83 7.34 25.35 0.81

Table 1:  Transferability of two pretrained models with different
initializations on various datasets. Source and Target are two models of the
same topology but different initialization point. $S_{\mathsf{Acc}}$ and
$T_{\mathsf{Acc}}$ are the accuracies on source and target models. $l_{2}$ and
$l_{\infty}$ are the norm values of the adversarial noise, larger norm values
mean larger perturbations. $\epsilon$ is a hyperparameter in FGSM, $i$ is the
number of iterations and $lr$ is the learning rate. $c$ is the confidence, the
adversarial sample has to cause the misclassified class to have a probability
above this given threshold.

##  3 Method

###  3.1 High-Level View

We start with a high-level description of our method. Each convolutional layer
with ReLU activation is sequentially extended with a guard (Figure 1(b)) and a
detector (Figure 1(a)) layer. Intuitively, the guard encourages the gradient
to disperse among differently initialized models, limiting sample
transferability. If this fails, the detector works as our second line of
defence by raising an alarm at potentially adversarial samples. The rest of
this section explains the design of the two modules, which work in tandem or
individually to defend against and/or detect most instances of the adversarial
attacks considered here.

(a) Detector.

(b) Guard.

Figure 1: High-level view of the module extensions we add to networks to stop
and detect transferred adversarial samples.

###  3.2 Static Channel Manipulation

Where an attack sample is transferable, we hypothesize that by moving along
the gradient direction of the input image that gave rise to the adversarial
sample, some of the neurons of the network are likely to be highly excited. By
monitoring abnormal excitation, we can detect many adversarial samples.

In Sitatapatra, we use a simple concept – we train neural networks using the
original datasets, but with additional activation regularization, so that a
certain set of outputs, and of intermediate activation values, are not
generated by any of the training set inputs. If one of these ‘taboo’
activations is observed, this serves as a signal that the input may be
adversarial. As different instances of the model can be trained with different
taboo sets, we have a way to introduce diversity that is analogous to the keys
used in cryptographic systems. This approach is much faster than, for example,
adversarial training [9]. By regularizing the activation feature maps, clean
samples yield well-bounded activation results, yet adversarial ones typically
result in highly excited neuron outputs in activations [32]. Using this, we
can design our detector (Figure 1(a)) so that uncompromised models can
successfully block most adversarial samples transferred from compromised
models, even under the strong assumption that the models share the same
network architecture and dataset.

For simplicity, we consider a feed-forward CNN $F$ consisting of a sequence of
$L$ convolutional layers, where the ${l}^{\mathrm{th}}$ layer computes output
feature maps $\mathbf{x}_{l}\in\mathbb{R}^{C_{l}\times H_{l}\times W_{l}}$.
Here, $\mathbf{x}_{l}$ is a collection of feature maps with $C_{l}$ channels
of $H_{l}\times W_{l}$ images, where $H_{l}$ and $W_{l}$ respectively denote
the width and height of the image.

The detector module additionally performs the following polynomial
transformation $f_{k}$ to the features of each layer output, which can be
derived from the key of the network:

$f_{k}(\mathbf{x}_{l})=a_{n}\mathbf{x}_{l}^{n}+a_{n-1}\mathbf{x}^{n-1}+\cdots+a_{0},$
(3)

and the transformation is then followed by the following criterion evaluation:

$g_{k}(\mathbf{x}_{l})=f_{k}\left(\mathbf{x}_{l}\right)\cdot{\left(\mathrm{sign}\left(f_{k}\left(\mathbf{x}_{l}\right)-t\right)\right)}_{+}.$
(4)

Here, $\cdot$ is element-wise multiplication,
${(\mathbf{z})}_{+}=\max(0,\mathbf{z})$ denotes the ReLU activation, the
degrees of the polynomial $n$ and the constant values $a_{0}$, $a_{1}$, …,
$a_{n}$ and $t>0$ can be identified as the key embedded into the network.
During training with clean dataset samples, any values
$f_{k}(\mathbf{x}_{l})>t$ are penalized, with the following regularization
term:

$\mathcal{R}(\mathbf{x})=\sum_{l\in
L}{\left\|g_{k}\left(\mathbf{x}_{l}\right)\right\|}_{1}.$ (5)

As we will examine closely in Section 4, the $g_{k}(\mathbf{x}_{l})$ evaluated
from adversarial samples generally produce positive results, whereas clean
validation samples usually do not trigger this criterion. Our detector uses
this to identify adversarial samples. In addition, the polynomial can be
evaluated efficiently with Horner’s method [15], requiring only $n$ multiply-
accumulate operations per value, which is insignificant when compared to the
computational cost of the convolutions. Finally, the non-linear nature of our
regularization diversifies the weight distributions among models, which
intuitively explains why adversarial samples become less likely to transfer.

###  3.3 Dynamic Channel Manipulation

In this section, we present the design of the guard module. It dynamically
manipulates feature maps using per-channel attention, which is in turn
inspired by the squeeze-excitation networks [11] and feature boosting [8]. As
with the detector modules described earlier in Section 3.2, we extend existing
networks by adding a guard module immediately after each convolutional layer
and its detector module. The ${l}^{\mathrm{th}}$ module accepts
$\mathbf{x}_{l}$ computed by the previous convolutional layer as its input,
and introduces a small auxiliary network $h:\mathbb{R}^{C_{l}\times
H_{l}\times W_{l}}\to\mathbb{R}^{C_{l}\times H_{l}\times W_{l}}$, which
amplifies important channels and suppresses unimportant ones in feature maps,
before feeding the results of $h(\mathbf{x}_{l})$ to the next convolutional
layer. The auxiliary network is illustrated in Figure 1(b) and is defined as:

$h(\mathbf{x}_{l})=\mathbf{x}_{l}\cdot\left(\bm{\gamma}_{l}\cdot\mathrm{pool}\left(\mathbf{x}_{l}\right)\bm{\phi}_{l}\right),$
(6)

where $\mathrm{pool}:\mathbb{R}^{C_{l}\times H_{l}\times
W_{l}}\to\mathbb{R}^{C_{l}}$ performs a global average pool on the feature
maps $\mathbf{x}_{l}$ which reduces them to a vector of $C_{l}$ values,
$\bm{\phi}\in\mathbb{R}^{C_{l}\times C_{l}}$ is a matrix of trainable
parameters, and $\cdot$ denotes element-wise multiplication between tensors
which broadcasts in a channel-wise manner. Finally, $\bm{\gamma}_{l}$ is a
vector of $C_{l}$ scaling constants, where each value is randomly drawn from a
uniform distribution between 0 and 1, using the crypto-key embedded within the
model as the random seed. By doing so, each deployed model can have a
different $\bm{\gamma}_{l}$ value, which diversifies the gradients among
models and forces the fine-tuned models to adopt different local minima.

##  4 Evaluation

###  4.1 Networks, Datasets and Attacks

We evaluate Sitatapatra on two datasets: MNIST [19], CIFAR10 [16]. In MNIST,
we use the LeNet5 architecture [20]. In CIFAR10, we use an efficient CNN
architecture (MCifarNet) from Mayo [36] that achieved a high classification
rate using only 1.3M parameters. ResNet18 is also considered on the CIFAR10
dataset [10].

We evaluated the performance of clean networks and Sitatapatra networks, using
two clean models with different initializations as the baseline. For the
Sitatapatra models we had two different keys applied on the source and target
models. The keys used are $2x^{2}+3x+5<6$ and $0.1x^{2}-x+2<3$ respectively.
Throughout the development of Sitatapatra we have tried using a large number
of different keys and observed that the performance of the detector is largely
dependant on the strictness of the regulariser. For evaluation purposes we
have decided to report on the worst performance, practically showing the
detection lower bound. The relative performance of other keys will be
presented later in Section 5. We consider attacks listed in Section 2 in White
and Black-box settings. For the latter, we estimate gradients using a simple
coordinate-wise finite difference method [12].

###  4.2 Static and Dynamic Channel Manipulations

LeNet5 MCifarNet ResNet18-Cifar10 Params $S_{\mathsf{Acc}}(\%)$
$T_{\mathsf{Acc}}(\%)$ $\Delta_{\mathsf{Acc}}(\%)$ $T_{\mathsf{Det}}(\%)$
$l_{2}$ $l_{\infty}$ $S_{\mathsf{Acc}}(\%)$ $T_{\mathsf{Acc}}(\%)$
$\Delta_{\mathsf{Acc}}(\%)$ $T_{\mathsf{Det}}(\%)$ $l_{2}$ $l_{\infty}$
$S_{\mathsf{Acc}}(\%)$ $T_{\mathsf{Acc}}(\%)$ $\Delta_{\mathsf{Acc}}(\%)$
$T_{\mathsf{Det}}(\%)$ $l_{2}$ $l_{\infty}$ Clean 99.13 99.25 - - - - 89.51
90.14 - - - - 91.12 93.58 - - - - FGSM $\epsilon=0.02$ 97.30 98.44 1.14 0.00
0.43 0.02 26.42 38.64 12.22 1.85 1.00 0.02 39.29 59.41 20.12 1.15 1.03 0.02
$\epsilon=0.05$ 92.19 97.44 5.26 0.00 1.07 0.05 22.87 32.95 10.09 1.53 2.43
0.04 30.18 44.74 14.56 0.75 2.50 0.05 $\epsilon=0.1$ 80.11 95.45 15.34 0.00
2.13 0.10 16.48 25.00 8.52 3.17 4.63 0.09 19.28 30.41 11.13 20.10 4.84 0.09
$\epsilon=0.15$ 63.07 90.06 26.99 0.00 3.18 0.15 9.23 17.47 8.24 18.11 6.84
0.13 11.51 24.01 12.50 93.02 7.12 0.13 $\epsilon=0.35$ 6.68 30.54 23.86 0.00
7.31 0.35 1.14 14.20 13.07 86.29 14.61 0.29 3.51 13.57 10.06 91.69 15.21 0.30
FGSM /w GE $\epsilon=0.02$ 97.87 99.15 1.28 0.00 0.43 0.02 28.41 39.35 10.94
2.03 0.97 0.02 40.91 60.94 20.03 1.68 1.03 0.02 $\epsilon=0.05$ 95.31 98.44
3.12 0.00 1.07 0.05 25.28 35.65 10.37 2.09 2.38 0.04 29.69 44.32 14.63 0.25
2.50 0.05 $\epsilon=0.1$ 82.39 96.31 13.92 0.00 2.14 0.10 18.04 26.56 8.52
3.28 4.47 0.08 18.32 29.40 11.08 17.63 4.88 0.09 $\epsilon=0.15$ 62.93 92.61
29.69 0.00 3.19 0.15 11.22 19.32 8.10 17.24 6.54 0.12 9.94 23.44 13.49 93.85
7.17 0.13 $\epsilon=0.35$ 7.67 32.10 24.43 0.00 7.35 0.35 1.42 15.48 14.06
84.84 14.21 0.28 2.70 14.63 11.93 91.86 15.27 0.30 PGD $i=10$ 64.63 98.44
33.81 0.00 1.57 0.09 1.14 41.90 40.77 1.84 0.76 0.02 12.12 61.09 48.97 0.30
0.82 0.03 $i=20$ 0.85 98.44 97.59 0.00 1.96 0.12 0.28 41.90 41.62 1.84 0.76
0.02 10.40 61.09 50.69 0.30 0.90 0.04 $i=50$ 0.00 98.44 98.44 0.00 1.96 0.12
0.00 41.90 41.90 1.84 0.76 0.02 7.43 60.94 53.51 0.29 1.03 0.05 PGD /w GE
$i=10$ 65.06 98.72 33.66 0.00 1.61 0.09 0.99 43.61 42.61 1.89 0.76 0.02 13.21
63.21 50.00 1.04 0.83 0.03 $i=20$ 0.85 98.72 97.87 0.00 1.99 0.12 0.28 43.61
43.32 1.89 0.76 0.02 11.22 63.21 51.99 1.04 0.92 0.04 $i=50$ 0.00 98.72 98.72
0.00 2.00 0.12 0.00 43.61 43.61 1.89 0.76 0.02 8.24 63.07 54.83 1.04 1.06 0.05
DeepFool $i=50$ 11.48 98.91 87.42 0.00 1.51 0.39 0.23 76.25 76.02 1.30 0.38
0.05 3.75 77.27 73.52 7.63 0.87 0.10 $i=10$ 89.61 99.22 9.61 0.00 1.44 0.37
2.97 76.17 73.20 1.30 0.38 0.05 6.33 77.50 71.17 6.95 0.81 0.10 C&W $lr=0.5$
4.38 93.98 89.61 2.35 2.95 0.66 3.83 11.48 7.66 67.41 9.82 0.25 2.73 20.55
17.81 95.50 10.11 0.25 $lr=1.0$ 1.56 80.47 78.91 4.78 3.74 0.75 5.31 13.91
8.59 92.02 17.11 0.43 3.52 11.72 8.20 96.05 17.84 0.46 C&W $lr=0.5$ 4.61 29.92
25.31 16.02 5.22 0.94 4.53 4.77 0.23 99.10 17.37 0.61 3.05 15.70 12.66 98.60
12.63 0.38 $c=0.999$ $lr=1.0$ 1.88 14.53 12.66 24.07 5.92 0.98 7.19 7.58 0.39
100.00 23.58 0.80 5.55 8.67 3.12 98.72 22.20 0.72

Table 2:  Transferability of different models on various datasets with the
SDCM instrumentation (Guard and Detector). Source and Target are two models of
the same topology but different SDCM instrumentations. We generate adversarial
samples from source models and apply them on the target models.
$S_{\mathsf{Acc}}$ and $T_{\mathsf{Acc}}$ are the accuracies on source and
target models. $T_{\mathsf{Det}}$ is the detection ratio on the targeting
model. $l_{2}$ and $l_{\infty}$ are the norm values of the adversarial noise,
larger norm values mean larger perturbations. $\epsilon$ is a hyperparameter
in FGSM, $i$ is the number of iterations and $lr$ is the learning rate. $c$ is
the confidence, the adversarial sample has to cause the misclassified class to
have a probability above this given threshold. ‘w/ GE’ indicates attacks that
use numerical gradient estimation, and they are only reported on MCifarNet
because of their long run-time nature.

Table 2 shows the performance of combined static and dynamic channels
manipulation (SDCM) method. During the training phase we tune each model to
have less than $1\%$ false positive detection rate on the clean evaluation
dataset. The results show good performance on large models, since large models
have more channels available for the proposed instrumentations. For ResNet18
on CIFAR10, we can achieve above $95\%$ detection of all adversarial samples.
Similarly, we believe that the performance increase, in comparison to both
LeNet5 and MCifarNet, comes from an increased number of channels of the
ResNet18 model. Furthermore, we observe a trade-off between the accuracy
difference ($\Delta_{\mathsf{acc}}$) and the detection rate
($T_{\mathsf{det}}$). When attacks achieve low classification accuracies on
the target model, the detector, acting as a second line of defence, usually
identifies the adversarial examples.

Further, it can be noticed that the samples that actually transfer well
usually result in relatively larger distortions — e.g. C&W with high
confidence and FGSM $0.6$. Although large distortions allow attacks to trick
the models, they inevitably trigger the alarm and thus get detected.
Meanwhile, attacks with more fine-grained perturbations fail to transfer and
the accuracy $T_{\mathsf{acc}}$ remains high. For example, DeepFool
consistently shows high $T_{\mathsf{acc}}$ and high $\Delta_{\mathsf{acc}}$.

Pretrained Static Only Combined $\Delta_{\mathsf{Acc}}(\%)$
$\Delta_{\mathsf{Acc}}(\%)$ $T_{\mathsf{Det}}(\%)$ $\Delta_{\mathsf{Acc}}(\%)$
$T_{\mathsf{Det}}(\%)$ FGSM $\epsilon=0.02$ 0.70 1.87 0.00 0.94 0.00
$\epsilon=0.08$ 3.98 15.78 0.00 9.14 0.00 $\epsilon=0.6$ 3.05 10.78 0.19 11.02
22.28 DeepFool $i=50$ 77.11 78.20 0.00 87.42 0.00 $i=10$ 9.22 1.02 0.00 9.61
0.00 C&W $lr=0.5$ 82.81 91.02 0.00 89.61 2.35 $lr=1.0$ 59.84 90.39 0.95 78.91
4.78 $c=0.999$ $lr=0.5$ 11.88 57.50 2.38 25.31 16.02 $lr=1.0$ 5.08 45.00 6.47
12.66 24.07

Table 3:  Transferability of LeNet5 on MNIST with different instrumentations.
$\Delta_{\mathsf{acc}}$ is the difference in accuracies and $T_{\mathsf{det}}$
is the detection rate. $l_{2}$ and $l_{\infty}$ are the averaged $l_{2}$ and
$l_{\infty}$ norms of the distortions on all input images. $\epsilon$ is a
hyperparameter in FGSM, $i$ is the number of steps and $lr$ is learning rate.
$c$ is the confidence, the adversarial sample has to cause the misclassified
class to have a probability above this given threshold. We use $20$ steps on
C&W.

Finally, to demonstrate the overall performance of Sitatapatra, we present a
comparison between the baseline, SCM and SDCM in Table 3. Both of the proposed
methods perform relatively worse for LeNet5 , as mentioned before, we believe
that this due to the small number of channels at its disposal. Having said
that, the proposed methods still greatly outperforms the baseline in terms of
$\Delta_{\mathsf{acc}}$. The results of DeepFool are very similar across all
three methods. DeepFool was not designed with transferability in mind. In
contrast, C&W was previously shown to generate highly transferable adversarial
samples. The combined method manages to successfully classify the transferred
samples and shows sensible detection rates.

##  5 Discussion

###  5.1 Accuracy, Detection and Computation Overheads

In this section we discuss the trade-offs facing the Sitatapatra user. First
and foremost, the choice of keys has an impact on transferability.

(a) Change in Accuracies ($\Delta_{\mathsf{acc}}$).

(b) Detection rates on the target model ($T_{\mathsf{det}}$)

Figure 2: Changes in accuracies and detection rates of LeNet5 with various
SDCM instrumentations

In Figure 2, we present a confusion matrix with differently instrumented
LeNet5 networks attacking each other with C&W attack for $20$ steps and a
learning rate of $0.5$. The chosen instrumentations are all second-order
polynomials, but with different coefficients. It is apparent that Sitatapatra
improves the accuracies reported in Figure 2(a). However, for the two
polynomials, $2x^{2}+3x+5<6$ and $2x^{2}+4x+5<6$, the behavior is different.
When using the adversarial samples from $2x^{2}+4x+5<6$ to attack
$2x^{2}+3x+5<6$, there is almost zero change in accuracy between the source
and the target model, but this relationship does not hold in reverse. The
above phenomenon indicates that the adversarial samples generated from one
polynomial are transferable to the other when the polynomials are too similar.
The same effect is observed in the detector shown in Figure 2(b): it is easier
to detect adversarial samples from $2x^{2}+4x+5<6$ to attack $2x^{2}+3x+5<6$.

This indicates that, when the models get regularized to polynomials that are
similar, the attacks between them end up being transferable. Fortunately, the
detection rates remain relatively high even in this case. Different
polynomials restrict the activation value range in different ways. In
practice, we found that the smaller the range that is available , i.e. the
unpenalized space for activations, the harder it is to train the network.
Intuitively, if the regularization applies too strict a constraint to
activation values, the stochastic gradient descent process struggles to
converge in a space full of local minima. However, a strong restriction on
activation values caused detection rates to improve. Thus, when deploying
models with Sitatapatra, the choice of polynomials affects base accuracies,
detection rates and training time.

Key choice brings efficiency considerations to the table as well. Although
training time for individual devices may be a bearable cost in many
applications, a substantial increase in run-time computational cost will often
be unacceptable. Figure 4 reflects the total additional costs incurred by
using Sitatapatra in our evaluation models. The $<7.5\%$ overhead we add to
the base network is small, given that the models demonstrate good defence and
detection rates against adversarial samples. It is notable that during
inference, a detector module requires for each value $n$ fused multiply-add
operations to evaluate a $n$-degree $f_{k}$ polynomial using Horner’s method
[15], and $1$ additional operation for threshold comparison, and thus utilize
$(n+1)C_{l}H_{l}W_{l}$ operations in total for the ${l}^{\mathrm{th}}$
convolutional layer. In our evaluation, we set $n=2$ by using second-order
polynomials. Additionally, a guard module of the ${l}^{\mathrm{th}}$ layer
uses channel-wise averaging, a fully connected layer, a channel-wise scaling,
and element-wise multiplications for all activations, which respectively
require $C_{l}H_{l}W_{l}$, $C_{l}^{2}$, $C_{l}$, and $C_{l}H_{l}W_{l}$
operations.

###  5.2 Key attribution

While exploring which activations ended up triggering an alarm with different
Sitatapatra parameters, we noticed that we could often attribute the
adversarial samples to the models used to generate them. In practice, this is
a huge benefit, known as traitor tracing in the crypto research community: if
somebody notices an attack, she can identify the compromised device and take
appropriate action. We conducted a simple experiment to evaluate how to
identify the source of a different adversarial sample. We first produced
models instrumented with different polynomials using Sitatapatra and then
generated the adversarial examples.

In this simple experiment, we use a support vector machine (SVM) to classify
the adversarial images based on the models generated them. The SVM gets
trained on the 5000 adversarial samples and gets tested on a set of 10000
unseen adversarial images. The training and test sets are disjoint.

Model #FLOPs original detector guard total overhead LeNet5 480,500 28,160
7,660 516,320 7.45% ResNet18 37,016,576 152,094 1,847,106 39,015,776 5.40%
MCifarNet 174,301,824 715,422 646,082 175,663,328 0.64%

Figure 3: The computational costs, measured in the number of FLOPs, added by
the detector and guard modules to the original network.

FGSM FGSM+DeepFool+C&W Polynomial Precision Recall F1 Precision Recall F1
$0.1x^{2}-1x+2<3$ 0.90 0.90 0.90 0.81 0.29 0.43 $x^{2}-22x+120<10$ 0.90 0.89
0.90 0.85 0.28 0.42 $2x^{2}+3x+5<6$ 0.53 0.72 0.61 0.34 0.33 0.33
$2x^{2}+4x+5<6$ 0.56 0.35 0.43 0.30 0.69 0.41 Micro F1 0.72 0.72 0.72 0.40
0.40 0.40 Macro F1 0.72 0.72 0.71 0.57 0.40 0.40

Figure 4: Key attribution based on the adversarial sample produced.

Figure 4 shows the classification results for FGSM-generated samples and all
attacks combined. Precision, Recall and F1 scores are reported. In addition,
we report the micro and macro aggregate values of F1 scores – micro counts the
total true positive, false negatives and false positives globally, whereas
macro takes label imbalance into account.

For both scenarios, we get a performance that is much better than random
guessing. First, it is easier to attribute adversarial samples generated by
the large coarse-grained attacks. Second, for polynomials that are different
enough, the classification precision is high – for just FGSM we get a $90\%$
recognition rate, while with more attacks it falls to $81\%$ and $85\%$. For
similar polynomials, we get worse performance, of around $50\%$ for FGSM and
around $30\%$ for all combined.

This bring an additional trade-off – training a lot of different polynomials
is hard, but it allows easier identification of adversarial samples. This then
raises the question of scalability of the Sitatapatra model instrumentation.

###  5.3 Key size

In 1883, the cryptographer Auguste Kerckhoffs enunciated a design principle
that is used today: a system should withstand enemy capture, and in particular
it should remain secure if everything about it, except the value of a key,
becomes public knowledge [14]. Sitatapatra follows this principle – as long as
the key is secured, it will, at a minimal cost, provide an efficient way to
protect against low-cost attacks at scale. The only difference is that if an
opponent secures access to a system protected with Sitatapatra, then by
observing its inputs and outputs he can use standard optimisation methods to
construct adversarial samples. However these samples will no longer transfer
to a system with a different key. One of the reasons why sample
transferability is an unsolved problem is because it has so far been hard to
generate a wide enough variety of models with enough difference between them
at scale.

Sitatapatra is the first attempt at this problem, and it shows possibilities
to embed different polynomial functions as keys to CNNs to block transfer of
adversarial samples. Modern networks have hundreds of layers and channels, and
thus can embed different keys at various parts improving key diversity. The
potential implication of having a key is important. In the case where a camera
vendor wants to sell the same vision system to banks as in the mass market, it
may be sufficient to have a completely independent key for the cameras sold to
each bank. It will also be sensible for a mass-market vendor wants to train
its devices in perhaps several dozen different families, in order to stop
attacks scaling (a technique adopted by some makers of pay-TV smartcards [1]).
However it would not be practical to have an individual key for each unit sold
for a few dollars in a mass market. The fact that adding keys to neural
networks can improve its diversity solves the problem of training multiple
individual neural networks on the same dataset, which is also known as a model
ensemble. In fact, our key instrumentation and the model identification from a
model ensemble together can be seen as a stream of deployment, which also
sufficiently increases the key space.

##  6 Conclusion

In this paper we presented Sitatapatra, a new way to use both static and
dynamic channel manipulations to stop adversarial sample transfer. We show how
to equip models with guards that diffuse gradients and detectors that restrict
their ranges, and demonstrate the performance of this combination on CNNs of
varying sizes. The detectors enable us to introduce key material as in
cryptography so that adversarial samples generated on a network with one key
will not transfer to a network with a different one, as activations will
exceed the ranges ranges permitted by the detectors and set off an alarm. We
described the trade-offs in terms of accuracy, detection rate, and the
computational overhead both for training and at run-time. The latter is about
five percent, enabling Sitatapatra to work on constrained devices. The real
additional cost is in training but in many applications this is perfectly
acceptable. Finally, with a proper choice of transfer functions, Sitatapatra
also allows adversarial sample attribution, or ‘traitor tracing’ as
cryptographers call it – so that a compromised device can be identified and
dealt with.

## Acknowledgements

Partially supported with funds from Bosch-Forschungsstiftung im
Stifterverband.

## References

  * [1] R. Anderson.  Security engineering: a guide to building dependable distributed systems.  2008\.
  * [2] S. Antol, A. Agrawal, J. Lu, M. Mitchell, D. Batra, C. Lawrence Zitnick, and D. Parikh.  Vqa: Visual question answering.  In Proceedings of the IEEE international conference on computer vision, pages 2425–2433, 2015.
  * [3] V. Badrinarayanan, A. Kendall, and R. Cipolla.  Segnet: A deep convolutional encoder-decoder architecture for image segmentation.  arXiv preprint arXiv:1511.00561, 2015.
  * [4] N. Carlini, P. Mishra, T. Vaidya, Y. Zhang, M. Sherr, C. Shields, D. Wagner, and W. Zhou.  Hidden Voice Commands.  In 25th USENIX Security Symposium (USENIX Security 16). USENIX Association, 2016.
  * [5] N. Carlini and D. Wagner.  Towards Evaluating the Robustness of Neural Networks.  In 2017 IEEE Symposium on Security and Privacy (SP), pages 39–57. IEEE, 2017.
  * [6] K. Eykholt, I. Evtimov, E. Fernandes, B. Li, A. Rahmati, C. Xiao, A. Prakash, T. Kohno, and D. Song.  Robust Physical-World Attacks on Deep Learning Visual Classification.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1625–1634, 2018.
  * [7] C.-Y. Fang, S.-W. Chen, and C.-S. Fuh.  Road-sign detection and tracking.  IEEE transactions on vehicular technology, 52(5):1329–1341, 2003\.
  * [8] X. Gao, Y. Zhao, L. Dudziak, R. Mullins, and C. zhong Xu.  Dynamic channel pruning: Feature boosting and suppression.  In International Conference on Learning Representations, 2019.
  * [9] I. J. Goodfellow, J. Shlens, and C. Szegedy.  Explaining and harnessing adversarial examples.  International Conference on Learning Representations (ICLR), 2015\.
  * [10] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [11] J. Hu, L. Shen, and G. Sun.  Squeeze-and-excitation networks.  arXiv preprint arXiv:1709.01507, 7, 2017.
  * [12] A. Ilyas, A. Jalal, E. Asteri, C. Daskalakis, and A. G. Dimakis.  The robust manifold defense: Adversarial training using generative models.
  * [13] S. Ji, W. Xu, M. Yang, and K. Yu.  3d convolutional neural networks for human action recognition.  IEEE transactions on pattern analysis and machine intelligence, 35(1):221–231, 2013.
  * [14] A. Kerckhoffs.  La cryptographie militaire.  pages 161–191, 1883.
  * [15] D. E. Knuth.  Evaluation of polynomials by computer.  Communications of the ACM, 5(12):595–599, 1962.
  * [16] A. Krizhevsky, V. Nair, and G. Hinton.  The CIFAR-10 dataset.  2014\.
  * [17] A. Krizhevsky, I. Sutskever, and G. E. Hinton.  ImageNet classification with deep convolutional neural networks.  In Advances in neural information processing systems, pages 1097–1105, 2012.
  * [18] A. Kurakin, I. Goodfellow, and S. Bengio.  Adversarial examples in the physical world.  arXiv preprint arXiv:1607.02533, 2016.
  * [19] Y. LeCun, C. Cortes, and C. Burges.  MNIST handwritten digit database.  2, 2010.
  * [20] Y. LeCun et al.  LeNet-5, convolutional neural networks.  page 20, 2015.
  * [21] X. Liu, M. Cheng, H. Zhang, and C.-J. Hsieh.  Towards robust neural networks via random self-ensemble.  In European Conference on Computer Vision, pages 381–397, 2018\.
  * [22] X. Liu, Y. Li, C. Wu, and C.-J. Hsieh.  Adv-BNN: Improved Adversarial Defense through Robust Bayesian Neural Network.  In International Conference on Learning Representations, 2019.
  * [23] Y. Liu, X. Chen, C. Liu, and D. Song.  Delving into transferable adversarial examples and black-box attacks.  In International Conference on Learning Representations (ICLR), 2017\.
  * [24] D. Meng and H. Chen.  Magnet: A two-pronged defense against adversarial examples.  In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, pages 135–147, New York, NY, USA, 2017. ACM.
  * [25] J. H. Metzen, T. Genewein, V. Fischer, and B. Bischoff.  On detecting adversarial perturbations.  In Proceedings of 5th International Conference on Learning Representations (ICLR), 2017.
  * [26] S. Moosavi-Dezfooli, A. Fawzi, and P. Frossard.  DeepFool: a simple and accurate method to fool deep neural networks.  2016\.
  * [27] N. Papernot, P. McDaniel, and I. Goodfellow.  Transferability in machine learning: from phenomena to black-box attacks using adversarial samples.  arXiv preprint, 2016.
  * [28] N. Papernot, P. McDaniel, I. Goodfellow, S. Jha, Z. B. Celik, and A. Swami.  Practical black-box attacks against machine learning.  pages 506–519, 2017.
  * [29] N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami.  Distillation as a defense to adversarial perturbations against deep neural networks.  2016 IEEE Symposium on Security and Privacy (SP), May 2016.
  * [30] S. Ren, K. He, R. Girshick, and J. Sun.  Faster R-CNN: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, pages 91–99, 2015.
  * [31] F. Schroff, D. Kalenichenko, and J. Philbin.  Facenet: A unified embedding for face recognition and clustering.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815–823, 2015.
  * [32] I. Shumailov, Y. Zhao, R. Mullins, and R. Anderson.  The taboo trap: Behavioural detection of adversarial samples.  arXiv preprint arXiv:1811.07375, 2018.
  * [33] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. J. Goodfellow, and R. Fergus.  Intriguing properties of neural networks.  CoRR, abs/1312.6199, 2013.
  * [34] D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry.  Robustness may be at odds with accuracy.  In International Conference on Learning Representations, 2019.
  * [35] Z. Yan, Y. Guo, and C. Zhang.  Deep defense: Training dnns with improved adversarial robustness.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 417–426. 2018.
  * [36] Y. Zhao, X. Gao, R. Mullins, and C. Xu.  Mayo: A framework for auto-generating hardware friendly deep neural networks.  2018\.
  * [37] Y. Zhao, I. Shumailov, R. Mullins, and R. Anderson.  To compress or not to compress: Understanding the interactions between adversarial attacks and neural network compression.  arXiv preprint arXiv:1810.00208, 2018.