11institutetext: CPS Group, TU Wien, Austria

# Safe Policy Improvement
in Constrained Markov Decision Processes

Luigi Berducci 11 Radu Grosu 11

###### Abstract

The automatic synthesis of a policy through reinforcement learning (RL) from a
given set of formal requirements depends on the construction of a reward
signal and consists of the iterative application of many policy-improvement
steps. The synthesis algorithm has to balance target, safety, and comfort
requirements in a single objective and to guarantee that the policy
improvement does not increase the number of safety-requirements violations,
especially for safety-critical applications. In this work, we present a
solution to the synthesis problem by solving its two main challenges: reward-
shaping from a set of formal requirements and safe policy update. For the
first, we propose an automatic reward-shaping procedure, defining a scalar
reward signal compliant with the task specification. For the second, we
introduce an algorithm ensuring that the policy is improved in a safe fashion,
with high-confidence guarantees. We also discuss the adoption of a model-based
RL algorithm to efficiently use the collected data and train a model-free
agent on the predicted trajectories, where the safety violation does not have
the same impact as in the real world. Finally, we demonstrate in standard
control benchmarks that the resulting learning procedure is effective and
robust even under heavy perturbations of the hyperparameters.

###### Keywords:

Reinforcement Learning Safe Policy Improvement Formal Specification

##  1 Introduction

Reinforcement Learning (RL) has become a practical approach for solving
complex control tasks in increasingly challenging environments. However,
despite the availability of a large set of standard benchmarks with well-
defined structure and reward signals, solving new problems remains an art.

There are two major challenges in applying RL to new synthesis problems. The
first, arises from the need to define a good reward signal for the problem. We
illustrate this challenge with an autonomous-driving (AD) application. In AD,
we have numerous requirements that have to be mapped into a single scalar
reward signal. In realistic applications, more than 200 requirements need to
be considered when assessing the course of action [14]. Moreover, determining
the relative importance of the different requirements is a highly non-trivial
task. In this realm, there are a plethora of regulations, ranging from safety
and traffic rules to performance, comfort, legal, and ethical requirements.

The second challenge concerns the RL algorithm with whom we intend to search
for an optimal policy. Considering most of the modern RL algorithms,
especially model-free policy-gradient methods [53], they require an iterative
interaction with the environment, from which they collect fresh experiences
for further improving the policy. Despite their effectiveness, a slight change
in the policy parameters could have unexpected consequences in the resulting
performance. This fact often results in learning curves with unstable
performances, strongly depending on the tuning of hyperparameters and
algorithmic design choices [28]. The lack of guarantees and robustness in the
policy improvement still limits the application of RL outside controlled
environments or simulators.

In this paper, we tackle the two problems mentioned above by proposing a
complete design pipeline for safe policies: from the definition of the problem
to the safe optimization of the policy (Fig. 1). We discuss how to structure
the problem from a set of formal requirements and enrich the reward signal
while keeping a sound formulation. Moreover, we define the conditions which
characterize a correct-by-construction algorithm in this context and
demonstrate its realizability with high-confidence off-policy evaluation. We
propose two algorithms, one model-free and one model-based, respectively. We
formally prove that they are correct by construction and evaluate their
performance empirically.

Figure 1: Overall RL pipeline to solve formally-specified control tasks.

##  2 Motivating Example

We motivate our work with a _cart-pole example_ extended with safety, target,
and comfort requirements, as follows: A _pole_ is attached to a _cart_ that
moves between a _left_ and a _right_ _limit_ , within a flat and frictionless
environment. The environment has a _target_ area within the limits and a
static _obstacle_ hanging above the track. We define five requirements for the
cart-pole, as shown in Table 1.

Req ID | Description
---|---
$\text{Req}_{1}$ | The cart shall reach the target in bounded time
$\text{Req}_{2}$ | The pole shall never fall from the cart
$\text{Req}_{3}$ | The pole shall never collide with the obstacle
$\text{Req}_{4}$ | The cart shall never leave the left/right limits
$\text{Req}_{5}$ | The cart shall keep the pole balanced within a
| comfortably small angle as often as possible
Table 1: Cart-pole example – informal requirements

We aim to teach the cart-pole to satisfy all requirements. The system is
controlled by applying a continuous force to the cart, allowing the left and
right movements of the cart-pole with different velocities. In order to reach
the goal and satisfy the target requirement $\text{Req}_{1}$, the cart-pole
must do an uncomfortable and potentially unsafe maneuver: since moving a
perfectly balanced pole would result in a collision with the obstacle, thus
violating the safety requirement $\text{Req}_{3}$, the cart-pole must lose
balancing and pass below it. Furthermore, if the obstacle is too large, or the
cart does not apply enough force once passing the obstacle, it may not be able
to reach the target without falling, thus violating the safety requirement
$\text{Req}_{2}$. A sequence of pictures showing the cart-pole successfully
overcoming the obstacle in the environment is depicted in Figure 2.

Figure 2: A cart-pole overcomes a hanging obstacle.

Observe that not all requirements have the same importance for this task. We
regard the safety requirements as fundamental constraints on the agent’s
behavior. A safety violation compromises the validity of the entire episode.
The target requirement expresses the main objective, and its completion is the
agent’s reason to be. Finally, comfort requirements are secondary objectives
that should be optimized as long as they do not interfere with the other two
classes of requirements. In the remainder of this paper, we will use this
motivating example to illustrate the steps that lead to the proposed
methodology.

##  3 Related Work

Safety is a well-known and highly-researched problem in the RL community, and
the related literature is wide [11, 23]. Many different definitions and
approaches have emerged over the years, so we will first clarify the
interpretations of safety that we adopt. Much work considers safety as the
property of the trained policy, determining whether the agent satisfies a set
of constraints. They either try to converge to a safe policy at the end of the
training [5, 10, 15, 2], or try to ensure safety during the entire training
process [51, 16, 45, 4, 18, 54, 64, 56].

Placing ourselves in a design perspective, we consider safety as a property of
the RL algorithm instead. By safety, we mean that a safe algorithm will not
return a policy with performance below a given threshold, with high
probability guarantees. Building on this interpretation, we will later define
the conditions for correct-by-construction RL algorithms. In the following, we
review the main approaches relevant to our contribution.

####  3.0.1 Safe policy improvement

Early representative of these algorithms are CPI [34, 46] that provide
monotonically improving updates at the cost of enormous sample complexity.
More recently, [52] introduced TRPO, the first policy-gradient algorithm which
builds on trust-region methods to guarantee policy improvement. However, its
sound formulation must be relaxed in practice for computational tractability.
The class of algorithms more relevant for our work is based on off-policy
evaluation [47, 57]. Seminal works in this field is HCPI [58, 59] that use
concentration inequalities [40] to define high-confidence lower bounds on the
importance sampling estimates [47] of the policy performance. More recently,
this class of algorithms has been shown to be part of the general Seldonian
framework [60]. We build on this formalism to define our approach and differ
from the existing work by proposing a novel interface with a set of formally
specified requirements, and propose Daedalus-style solutions [58] to tackle
the problem of iterative improvement in an online setting.

####  3.0.2 Policy evaluation with statistical model checking

Statistical guarantees on the policy evaluation for some temporal
specification is commonly solved with statistical model checking (SMC) [3,
35]. Recent works have proposed SMC for evaluating a NN decision policy
operating in an MDP [24]. However, while SMC relies on collecting a large
number of executions of the policy in the environment and hypothesis testing
for providing performance bounds, our off-policy setting tackles a different
problem. In off-policy evaluation, the model of the environment is generally
unknown and we cannot deploy the decision policy in the environment because it
could be costly or dangerous. Unlike SMC, we cannot directly collect
statistics with the decision policy. Conversely, we try to approximate the
expected performance using data collected by another policy.

####  3.0.3 RL with temporal logic

Much prior work adopts _temporal logic_ (TL) in RL. Some of it focuses on the
decomposition of a complex task into many sub tasks [33, 61]. Other on
formulations tailored to tasks specified in TL [21, 36, 31, 29]. Several works
use the quantitative semantics of TL (i.e., STL and its variants) to derive a
reward signal [37, 32, 7]. However, they describe the task as a monolithic TL
specification and compute the reward on complete [37] or truncated
trajectories [7]. In this work, we use HPRS, introduced in [9] to mitigate the
reward sparsity and subsequent credit-assignment problem, which combines the
individual evaluation of requirements into a hierarchically-weighted reward,
capturing the priority among the various classes of requirements.

####  3.0.4 Multi-objective RL.

Multi-objective RL (MORL) studies the optimization of multiple and often
conflicting objectives. MORL algorithms learn single or multiple policies [50,
38]. There exist several techniques to combine multiple reward signals into a
single scalar value (i.e., scalarization), such as linear or non-linear
projections [42, 8, 62]. Other approaches formulate structured rewards by
imposing or assuming a preference ranking on the objectives and finding an
equilibrium among them [22, 55, 65, 1]. [13] proposes to decompose the task
specification into many requirements. However, they do not consider any
structured priority among requirements and rely on the arbitrary choice of
weights for each of them. In general, balancing between safety and performance
shows connections with MORL. However, we focus on the safety aspects and how
to guarantee safety below a certain threshold with high probability. These
characteristics are not present in MORL approaches.

####  3.0.5 Hierarchically Structured Requirements.

The use of partially ordered requirements to formalize complex tasks has been
proposed in a few works. The rulebook formalism [14] represents a set of
prioritized requirements, and it has been used for evaluating the behaviors
produced with a planner [14], or generating adversarial testing scenarios
[63]. In [48], a complementary inverse RL approach proposes learning
dependencies for formal requirements starting from existing demonstrations.
Conversely, we use the requirements to describe our task and define a
Constrained MDP, and then focus on the design of a safe policy-improvement
algorithm.

####  3.0.6 Model-based reinforcement learning

Among the first representatives of model-based RL algorithms is PILCO [19],
which learned a Gaussian process for low-dimensional state systems. More
recent works showed that it is possible to exploit expressive neural-networks
models to learn complex dynamics in robotics systems [41], and use them for
planning [17] or policy learning [30]. In the context of control from pixel
images, world models [25] proved that it is possible to learn accurate dynamic
models for POMDPs by using noisy high-dimensional observations instead of
accurate states. Their application in planning [27], and later in policy
learning [26], have achieved the new state-of-the-art performance in many
benchmarks and were recently applied to real-world robots [12].

##  4 Preliminaries

###  4.1 Reinforcement Learning

Reinforcement Learning (RL) aims to infer an intelligent agent’s policy that
takes actions in an environment in a way that maximizes some notion of
expected return. The environment is typically modeled as a Markov decision
process (MDP), and the return is defined as the cumulative discounted reward.

###### Definition 1

A Markov Decision Process (MDP) is a tuple $M=(S,A,p,R,\gamma)$, where $S$ is
a set of states; $A$ is a set of possible actions; $p:S\times A\times
S\rightarrow[0,1]$ is a transition probability function (where
$p(s_{t+1}|a_{t},s_{t})$ describes the probability of arriving in state
$s_{t+1}$ if action $a_{t}$ was taken at state $s_{t}$); $R:S\times A\times
S\rightarrow\mathbb{R}$ is a deterministic reward function, assigning a scalar
value to a transition; $\gamma\in[0,1]$ is the discount factor that balances
the importance of achieving future rewards.

In RL, one aims to find a policy $\pi:S\times A\rightarrow[0,1]$ which maps
states to action probabilities, such that it maximizes the expected sum of
rewards collected over episodes (or trajectories) $\tau$:

$\pi^{\star}=\operatorname*{arg\,max}_{\pi}\mathbb{E}_{\tau\sim\mu(\cdot|\pi)}\big{[}\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t},s_{t+1})\big{]},$

where $\mu(\tau|\pi)$ represents the distribution over episodes observed when
sampling actions from some policy $\pi$, and $\tau\sim\mu(\cdot|\pi)$ denotes
an episode that was sampled from this distribution.

Conventional RL approaches do not explicitly consider safety constraints in
MDPs. Constrained MDPs [6] extend the MDP formalism to handle such
constraints, resulting in the tuple $M=(S,A,p,R,C,\gamma,d)$, where $C:S\times
A\times S\rightarrow\mathbb{R}$ is a cost function and $d\in\mathbb{R}$ is a
cost threshold. We aim to teach the agent to safely interact with the
environment. More concretely, considering the episodes
$\tau\sim\mu(\cdot|\pi)$, the expected cumulative cost must be below the
threshold $d$; that is, the constraint is
$\mathbb{E}_{\tau\sim\mu(\cdot|\pi)}\big{[}\sum_{t=0}^{\infty}\gamma^{t}C(s_{t},a_{t},s_{t+1},)\big{]}\leq
d$. Formally, the constrained optimization problem consists of finding
$\pi^{\star}$ such that:

$\displaystyle\pi^{\star}=$
$\displaystyle\operatorname*{arg\,max}_{\pi}\mathbb{E}_{\tau\sim\mu(\cdot|\pi)}\big{[}\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t},s_{t+1},)\big{]}$
$\displaystyle\text{subject to
}\mathbb{E}_{\tau\sim\mu(\cdot|\pi)}\big{[}\sum_{t=0}^{\infty}\gamma^{t}C(s_{t},a_{t},s_{t+1},)\big{]}\leq
d$

We denote the expected cumulative discounted reward and cost as $V^{\pi}$ and
$V_{C}^{\pi}$, respectively. When dealing with multiple constraints, we use
$C_{i}$, $d_{i}$, and $V_{C_{i}}^{\pi}$ to denote the $i$-th cost function,
its threshold, and expected cumulative cost.

###  4.2 Hierarchical Task Specifications

####  4.2.1 Requirements specification

In [9], we formally define a set of expressive operators to capture
requirements often occurring in control problems. Considering atomic
predicates $p\doteq f(s)\,{\geq}\,0$ over observable states $s\,{\in}\,S$, we
extend existing task-specification languages (e.g., SpectRL [33]) and define
requirements as:

$\displaystyle\begin{split}\varphi\doteq\ \texttt{achieve}\
p~{}|~{}\texttt{conquer}\ p~{}|~{}\ \texttt{ensure}\
p~{}|~{}\texttt{encourage}\ p\end{split}$ (1)

Commonly, a task can be defined as a set of requirements from three basic
classes: safety, target, and comfort. Safety requirements, of the form
$\texttt{ensure}\ p$, are naturally associated to an invariant condition $p$.
Target requirements, of the form $\texttt{achieve}\ p$ or $\texttt{conquer}\
p$, formalize the one-time or respectively the persistent achievement of a
goal within an episode. Finally, comfort requirements, of the form
$\texttt{encourage}~{}p$, introduce the soft satisfaction of $p$, as often as
possible, without compromising task satisfaction.

Let $\mathbb{T}$ be the set of all finite episodes of length $T$. Then, each
requirement $\varphi$ induces a Boolean function
$\sigma:\,\mathbb{T}\,{\rightarrow}\,\mathbb{B}$ evaluating whether an episode
$\tau\,{\in}\,\mathbb{T}$ satisfies the requirement $\varphi$. Formally, given
a finite episode $\tau$ of length $T$, we define the requirement-satisfaction
function $\sigma$ as follows:

$\displaystyle\tau\models\texttt{achieve}\ p$ $\displaystyle\text{ iff
}\exists i\leq T,\tau_{i}\models p$ $\displaystyle\tau\models\texttt{conquer}\
p$ $\displaystyle\text{ iff }\exists i\leq T,\forall j\geq i,\tau_{j}\models
p$ $\displaystyle\tau\models\texttt{ensure}\ p$ $\displaystyle\text{ iff
}\forall i\leq T,\tau_{i}\models p$
$\displaystyle\tau\models\texttt{encourage}\ p$ iff true

We explain below the proposed evaluation of comfort requirements. In our
interpretation, they represent secondary objectives, and their satisfaction
does not alter the truth of the evaluation. In fact, as long as the agent is
able to safely achieve the target, we consider the task satisfied. For this
reason, the satisfaction of comfort requirement always evaluates to true. To
further clarify the proposed specification language, we formalize the
requirements for the running example.

###### Example 1

Consider the motivating cart-pole example. Now let us give the formal
specification of its requirements. The state is the tuple
$(x,\dot{x},\theta,\dot{\theta})$, where $x$ is the position of the cart,
$\dot{x}$ is its velocity, $\theta$ is the angle of the pole to the vertical
axis, and $\dot{\theta}$ is its angular velocity. We first define: (1) the
angle $\theta_{\emph{max}}$ of the pole at which we consider the pole to fall
from the cart; (2) the maximum angle $\theta_{\emph{comf}}$ of the pole that
we consider to be comfortable; (3) the world limit $x_{\emph{lim}}$; (4) the
position $G$ of the goal; (5) the set of points $O$ defining the static
obstacle; and (6) a distance function $d$ between locations in the world
(e.g., euclidean distance), that, with a slight abuse of notation, we extend
to measure the distance between the cart position and a set of points. Then,
the task can be formalized with the requirements reported in Table 2.

Table 2: Cart-pole example – formalized requirements Req Id | Formula Id | Formula
---|---|---
Req1 | $\varphi_{1}$ | $\texttt{conquer }d(x,G)=0$
Req2 | $\varphi_{2}$ | $\texttt{ensure }|\theta|\leq\theta_{\emph{max}}$
Req3 | $\varphi_{4}$ | $\texttt{ensure }d(x,O)>0$
Req4 | $\varphi_{3}$ | $\texttt{ensure }|x|\leq x_{\emph{lim}}$
Req5 | $\varphi_{5}$ | $\texttt{encourage }|\theta|\leq\theta_{\emph{comf}}$

####  4.2.2 Task as a Partially-Ordered Set

We formalize a task by a set of formal requirements $\Phi$, assuming that the
target is unique and unambiguous. Formally,
$\Phi=\Phi_{S}\uplus\Phi_{T}\uplus\Phi_{C}$ such that:

$\begin{array}[]{lc}\Phi_{S}:=\\{\varphi\,|\,\varphi\doteq\texttt{ensure}\
p\\}\\\ \Phi_{C}:=\\{\varphi\,|\,\varphi\doteq\texttt{encourage}\ p\\}\\\
\Phi_{T}:=\\{\varphi\,|\,\varphi\doteq\texttt{achieve}\
p\,\vee\,\varphi\doteq\texttt{conquer}\ p\\}\end{array}$

The target requirement is required to be unique ($|\Phi_{T}|=1$).

We use a very natural interpretation of importance among the class of
requirements, which considers decreasing importance from safety, to target,
and to comfort requirements. Formally, this natural interpretation of
importance defines a (strict) partial order relation $\prec$ on $\Phi$ as
follows:

$\varphi\prec\varphi^{\prime}\text{ iff
}\left(\varphi\in\Phi_{S}\wedge\varphi^{\prime}\not\in\Phi_{S}\right)\vee\left(\varphi\in\Phi_{T}\wedge\varphi^{\prime}\in\Phi_{C}\right)$

The resulting pair $(\Phi,\prec)$ forms a partially-ordered set of
requirements and defines our task. Extending the semantics of satisfaction to
a set, we consider a task accomplished when all of its requirements are
satisfied:

$\tau\models\Phi\text{ iff }\forall\varphi\in\Phi,\tau\models\varphi.$ (2)

##  5 Contribution

In this section, we present the main contribution of this work: a correct-by-
construction RL pipeline to solve formally-specified control tasks. First, we
formalize a CMDP from the set of requirements, providing the intuition behind
its sound formulation. Then, we describe the potential-based reward proposed
in [9] that we use to enrich the learning signal and still benefit from
correctness guarantees. Finally, we present an online RL algorithm that
iteratively updates a policy while maintaining the performance for safety
requirements.

###  5.1 Problem Formulation

The environment is considered a tuple $E\,{=}\,(S,A,p)$, where $S$ is the set
of states, $A$ is the set of actions, and $p(s_{t+1}|s_{t},a_{t})$ is its
dynamics, that is, the probability of reaching state $s^{\prime}$ by
performing action $a$ in state $s$. Given a task specification $(\Phi,\prec)$,
where $\Phi=\Phi_{S}\uplus\Phi_{T}\uplus\Phi_{C}$, we define a CMDP
$M\,{=}\,(S,A,p,R,C,\gamma,d)$ by formulating its reward $R$ and cost
functions $C_{i}$ to reflect the semantics of $(\Phi,\prec)$.

We consider episodic tasks of length $T$, where the episode ends when the task
satisfaction is decided: either through a safety violation, a timeout, or the
goal achievement. When one of these events occurs, we assume that the MDP is
entering a final absorbing state $s_{f}$, where the decidability of the
episode cannot be altered anymore. The goal-achievement evaluation depends on
the target operator adopted: for $\texttt{achieve}\ p$ the goal is achieved
when visiting at time $t\,{\leq}\,T$ a state $s_{t}$ such that $s_{t}\models
p$; for $\texttt{conquer}\ p$ the goal is achieved if there is a time
$i\,{\leq}\,T$ such that for all $i\,{\leq}\,t\,{\leq}\,T$, $s_{t}\models p$.

We adopt a straightforward interface for safety requirements, requiring the
cost function $C_{i}(s,a,s^{\prime})$ to be a binary indicator of the
violation of the $i$-th safety requirement $\phi_{i}\in\Phi_{S}$ when entering
$s^{\prime}$ from $s$: 0 if the current state satisfies $\phi_{i}$ and $1$ if
the current state violates $\phi_{i}$. We bound the expected cumulative
discounted cost by $d_{i}$, a user-provided safety threshold that depends on
the specific application considered:

$V_{C_{i}}^{\pi}=\mathbb{E}_{\tau\sim\mu(\cdot|\pi)}[\sum_{t=0}^{T}\gamma^{t}C_{i}(s_{t},a_{t},s_{t+1})]\leq
d_{i}$

The choice of this cost function promotes simplicity, requiring users to only
be able to detect safety violations and relieving them from the burden of
defining more complex signals. Moreover, the resulting cost metric
$V_{C_{i}}^{\pi}$ reflects the failure probability discounted over time by the
factor $\gamma$ and makes the choice of the threshold $d_{i}$ more intuitive
by interpreting it in a probabilistic way.

We complete the CMDP formulation by defining a sparse reward, incentivizing
goal achievement. Let $p$ be the property of the unique target requirement.
Then, for safe transitions $\langle s_{t},a_{t},s_{t+1}\rangle$, we define the
following reward signal:

$\displaystyle R(s_{t},a_{t},s_{t+1})=\left\\{\begin{array}[]{ c l
}1&\quad\textrm{if }s_{t+1}\models p\\\
0&\quad\textrm{otherwise}\end{array}\right.$

The rationale behind this choice is that the task’s satisfaction depends on
the satisfaction of safety and target requirements. In the same way, the
reward $R$ incentives safe transitions to states that satisfy the target
requirement, and the violation of any safety requirements terminates the
episode, precluding the agent from collecting any further reward. It follows
that $R$ incentives to reach the target and stay there as long as possible, in
the limit until $T$.

###  5.2 Reward Shaping

We additionally define a shaped reward with HPRS [9] to provide a dense
training signal and speed-up the learning process. Since we consider a CMDP
and model the safety requirements as constraints, we restrict the HPRS
definition to target and comfort requirements.

We consider predicates $p(s)\,{\doteq}\,f(s)\,{\geq}\,0$, where the value
$f(s)$ is bounded in $[m,M]$ for all states $s$. Let
$f_{-}(s)\,{=}\,min(0,f(s))$ and $\Phi_{tc}=\Phi_{T}\uplus\Phi_{C}$. We use
the continuous normalized signal $r(\varphi,s)=1-\frac{f_{-}(s)}{m}$ to define
the potential shaping function $\Psi$ as follows:

$\Psi(s)=\sum_{\varphi\in\Phi_{tc}}\left(\prod_{\varphi^{\prime}\in\Phi_{tc}:\varphi^{\prime}\prec\varphi}r(\varphi^{\prime},s)\right)\cdot
r(\varphi,s)$

This potential function is a weighted sum over all scores $r(\varphi,s)$ for
target and comfort requirements, where the weights are determined by a product
of the scores of all specifications that are strictly more important
(hierarchically) than $\varphi$. Crucially, these weights adapt dynamically at
every step.

###### Corollary 1

The optimal policy for the CMDP $M^{\prime}$, where its reward $R^{\prime}$ is
defined as below:

$R^{\prime}(s_{t},a_{t},s_{t+1})=R(s_{t},a_{t},s_{t+1})+\gamma\Psi(s_{t+1})-\Psi(s_{t})$
(3)

is also an optimal policy for the CMDP $M$ with reward $R$.

The corollary stated in [9] follows by the fact that $\Psi$ is a potential
function (i.e., depends only on the current state) and by the results in [43].
This result remark that the proposed reward shaping is correct since it
preserves the policy optimality of the CMDP $M$.

The proposed hierarchical-potential signal has a few crucial characteristics.
First, it is a potential function and can be used to augment the original
reward signal without altering the optimal policy of the resulting CMDP.
Second, it is a multivariate signal that combines target and comfort
objectives with multiplicative terms. A linear combination of them, as typical
in multi-objective scalarization, would assume independence among objectives.
Consequently, any linear combination would not be expressive enough to capture
the interdependence between requirements. Finally, the weights dynamically
adapt at every step according to the satisfaction degree of the requirements.

###  5.3 Safe Policy Improvement in Online Setting

This section presents an online RL algorithm that uses a correct-by-
construction policy-improvement routine. While this approach is general enough
to be used on any CMDP, we use it with the shaped reward signal and costs
presented in the previous section.

At each iteration, the algorithm performs a correct-by-construction refinement
of the current policy $\pi$, with high probability. This means that, with high
probability, the algorithm returns a policy $\pi^{\prime}$ whose safety
performance is not worse than that of $\pi$. Since we are working in a model-
free setting, with access to only a finite amount of off-policy data, we can
define correct-by-construction only up to certain confidence $\delta$. Below
is the formal definition.

###### Definition 2

Let $M$ be a CMDP with cost functions $C_{i}$ for $i\in[1,k]$, $\pi$ a policy,
and $D_{n}\sim\mu(\cdot|\pi)$ a finite dataset of experiences collected with
$\pi$. A policy-improvement routine $\mathcal{A}$ is correct-by-construction
if for any $\delta$:

$\displaystyle\pi^{\prime}=\mathcal{A}(\pi,D_{n},\delta)\quad\text{ s.t.
}\quad Pr(\bigwedge_{i=1}^{k}V_{C_{i}}^{\pi^{\prime}}\leq V_{C_{i}}^{\pi})\geq
1-\delta$

Having defined what correct-by-construction means, we describe how we can
build an update mechanism to prevent the deployment of an unsafe policy.

####  5.3.1 High-confidence off-policy policy evaluation

Before releasing a policy $\pi^{\prime}$ for deployment in the environment, we
need to estimate its safety performance using a set of trajectories $D_{n}$
collected with the previous deployed policy $\pi$. We assume to know a
threshold $\rho_{+}$, being either an acceptable upper bound for the cost in
our application or an estimate of the performance of the last deployed policy
$\pi$. We aim to evaluate a candidate policy $\pi^{\prime}$ and check if its
expected cumulative costs are below the thresholds with a probability of at
least $1\,{-}\,\delta$.

We use importance sampling to produce an unbiased estimator of
$\rho(\pi^{\prime})$ over a trajectory $\tau$ collected by running $\pi$. The
estimator is defined as

$\hat{\rho}(\pi^{\prime}|\tau,\pi)=\prod_{t=1}^{|\tau|}\frac{\pi^{\prime}(a_{t}|s_{t})}{\pi(a_{t}|s_{t})}\big{(}\sum_{t=1}^{|\tau|}\gamma^{t}C(s_{t},a_{t},s_{t+1})\big{)}$

Computing the importance weighted returns gives us unbiased estimators of the
safety performance [47]. The mean over estimators from $n$ trajectories in
$D_{n}$ is also unbiased,
$\hat{\rho}=\frac{1}{n}\sum_{i}^{n}\hat{\rho}(\pi^{\prime}|\tau_{i},\pi)$.
However, we want to provide statistical guarantees regarding the resulting
value. We use the one-sided Student-t test to obtain a $1-\delta$ confidence
upper bound on $\hat{\rho}$.

Let $\hat{\rho}_{i}$ be the $i$-th unbiased estimator obtained by importance
sampling, the Student-t test defines:

$\hat{\rho}=\frac{1}{n}\sum_{i}^{n}\hat{\rho}_{i},$
$\sigma=\sqrt{\frac{1}{n-1}\sum_{i}^{n}(\hat{\rho}_{i}-\hat{\rho})^{2}}$

and proves that with probability $1-\delta$ that:

$\rho\leq\hat{\rho}+\frac{\sigma}{\sqrt{m}}t_{1-\delta,n-1}$

where $t_{1-\delta,n-1}$ is the $(1-\delta)100$ percentile of the Student’s t
distribution with $n-1$ degrees of freedom. Under the assumption of normally
distributed $\hat{\rho}$, which is a reasonable assumption [57] for large $n$
by central limit theorem (CLT), we use the Student’s t-test to obtain a
guaranteed upper bound on $\rho$. If the upper bound is below the threshold
$\rho_{+}$, we can release the current policy $\pi$ in the environment because
we know that its expected cumulative cost is not higher than $\rho_{+}$ with
probability at least $1-\delta$.

####  5.3.2 Safe model-free policy improvement (SMFPI)

Among the most successful approaches in model-free optimization are policy
gradient methods [53]. They update the policy by estimating the policy
gradient over a finite batch of episodes $D_{n}$. A typical gradient estimator
for a policy $\pi_{\theta}$ parametrized by $\theta$ is

$\hat{g}=\mathbb{E}_{(s_{t},a_{t})\in D_{n}}\big{[}\nabla_{\theta}\text{ log
}\pi_{\theta}(a_{t}|s_{t})\hat{A}_{t}\big{]}$

where $\hat{A}_{t}$ is an estimator of the advantage function and, in its
simplest form, corresponds to the discounted cumulative return.

The main limitation of these approaches is due to the on-policy nature of
policy gradient methods. At each policy update, they must collect new data by
interacting with the environment to compute the gradients. Reusing the same
trajectories to perform many updates is not theoretically justified and can
perform catastrophic policy updates in practice. The first algorithm we
propose, SMFPI, directly uses this policy-gradient update and estimates the
return as the sum of the shaped rewards, as presented in the previous section.
The following subsection discusses a model-based solution to improve data
efficiency by learning a dynamics model.

####  5.3.3 Safe model-based policy improvement (SMBPI)

Model-based algorithms are known to be more sample efficient than model-free
ones. The data collected over the training process can be used to fit a
dynamics model that serves as a simulator of the real environment.

Despite the variety of model-based approaches, we use the dynamics model for
training a model-free agent on predicted trajectories, reducing the required
interactions with the real environment. The dynamics model is reusable over
many iterations, and for this reason, we consider it a data-efficient
alternative.

##### Learning the dynamics.

We consider the problem of learning an accurate dynamical model. Traditional
approaches use Bayesian models (e.g., GPs) [19] for their efficiency in low-
data regimes, but training on a large dataset and high-dimensional data is
prohibitive. Modern literature in deep RL [17] suggests that using an ensemble
of neural networks can produce competitive performance with scarce data and
efficiently scale to large-data regimes.

Since we intend to represent a potentially stochastic state-transition
function, capturing the noise of observations and process, we train a model to
parametrize a probability distribution. We assume a diagonal Gaussian
distribution model $p_{\theta}$ and let a neural network predict the mean
$\mu_{\theta}(s,a)$ and the log standard deviation
$log\,\sigma_{\theta}(s,a)$. Instead of learning to predict the following
state $s_{t+1}=p_{\theta}(s_{t},a_{t})$, we train our dynamics model to
predicts the change with respect to the current state $\Delta
s_{t+1}=p_{\theta}(s_{t},a_{t})$ [20, 41].

However, training on scarce data may lead to overfitting and extrapolation
errors in the area of the state-action space that are not sufficiently
supported by the collected experience. A common solution to prevent the
algorithm from exploiting these regions consists of adopting an ensemble of
models $\\{p_{\theta_{i}}\\}_{i=1}^{m}$. With this ensemble representing a
finite set of plausible dynamics of our system, we predict the state
trajectories and propagate the dynamics uncertainty by shooting $N$ particles
from the current state $s_{t}$. At each timestep, we uniformly sample one of
the ensemble’s models. The choice of the ensemble size (i.e., the number $m$
of dynamics models) is crucial to capture the uncertainty in the underlying
stochastic dynamics adequately. While a small ensemble might introduce a
significant model bias in policy optimization, a large ensemble increases the
computational and memory cost for learning and storing the models.

##### Policy optimization with learned dynamics.

The dynamical model defines an MDP that approximates the real environment.
This provides a simulator from which we can sample plausible trajectories
without harmful interaction.

Starting from true states sampled from our buffer of past experiences, we
generate predictions using the dynamical model $\hat{s}_{t+1}\sim
p_{\theta}(\hat{s}_{t},a_{t})$, for action $a_{t}\sim\pi(\hat{s}_{t})$. We
assume the reward function $r_{t}=R(\hat{s}_{t},a_{t},\hat{s}_{t+1})$ and the
cost functions $c_{i,t}=C_{i}(\hat{s}_{t},a_{t},\hat{s}_{t+1})$ to be known.
In general, the learned model could predict them, so in the following, we
refer to the predictive model as able to generate state, reward and costs,
i.e., $(s_{t+1},r_{t},c_{i,t})\sim p_{\theta}(s_{t},a_{t})$.

Considering the predicted trajectories over a finite horizon $H$, we use
model-free RL to train the policy. This approach is agnostic to the specific
algorithm adopted. We consider two approaches for dealing with safety:

  1. 1.

Pessimistic Reward. We alter the MDP transitions when visiting unsafe states
(where the cost exceeds the threshold). In this case, the system enters an
absorbing state where it repeatedly collects a high penalty $-C$.

  2. 2.

Constrained optimization. We define the unconstrained Lagrangian objective

$V(\pi)-\sum_{i=1}^{C}\lambda_{i}V_{C_{i}}(\pi)$

for some multiplier $\lambda_{i}$. Using gradient-based optimization, we
iteratively update the policy parameters and the dual variables $\lambda_{i}$.

####  5.3.4 Correct-by-construction RL algorithms.

Having introduced various algorithmic solutions to tackle the policy
optimization process, we report the pseudocode of the complete algorithm in
Algorithm 1. Then, we state an important result derived from adopting high-
confidence off-policy evaluation.

###### Theorem 5.1

Algorithm 2 (SMFPI) and Algorithm 3 (SMBPI) are correct-by-construction
policy-improvement routines.

###### Proof

Using the results from high-confidence off-policy evaluation literature [59],
we demonstrate that each policy $\pi^{\prime}$ returned by SMFPI or SMBPI has
expected cost less than or equal to the expected cost of the initial policy
$\pi$ with probability at least $1-\delta$. If $\pi^{\prime}=\pi$, then the
condition is trivially satisfied, so let us assume $\pi^{\prime}$ to be a
different policy. According to the algorithm, $\pi^{\prime}$ satisfies:

$\rho^{i}\leq\rho_{+}^{i},~{}\forall i\in[1,k]$

By definition of $\rho^{i}$ using Student-t test and confidence
$\frac{\delta}{k}$, and under the assumption of normally-distributed cost
sample means, we know that for each $i$:

$Pr\big{(}V_{C_{i}}^{\pi^{\prime}}\leq V_{C_{i}}^{\pi}\big{)}\geq
1-\frac{\delta}{k}$

and equivalently that

$Pr\big{(}V_{C_{i}}^{\pi^{\prime}}>V_{C_{i}}^{\pi}\big{)}<\frac{\delta}{k}$

Using the Union Bound, we finally show that the probability of the event in
which at least one of the costs violates the correctness condition is at most
$\delta$.

$Pr\big{(}\bigvee_{i=1}^{k}V_{C_{i}}^{\pi^{\prime}}>V_{C_{i}}^{\pi}\big{)}<\sum_{i=1}^{k}Pr\big{(}V_{C_{i}}^{\pi^{\prime}}>V_{C_{i}}^{\pi}\big{)}=\delta$

This statement is equivalent to the following condition which concludes the
proof.

$Pr\big{(}\bigwedge_{i=1}^{k}V_{C_{i}}^{\pi^{\prime}}\leq
V_{C_{i}}^{\pi}\big{)}\geq 1-\delta.$

Algorithm 1 Safe Policy Optimization

0: Initial policy $\pi$, confidence $\delta$ for policy improvement

Initialize prediction model $p_{\theta}$, empty buffer $D$ and $D_{test}$

for $N$ epochs do

Collect data with $\pi$ in environment:
$D=D\cup\\{(s_{t},a_{t},s_{t+1},r_{t},c_{t}^{1},...,c_{t}^{k},\text{log
}\pi(a_{t}|s_{t}))\\}_{t}$

Estimate safety performance of current policy $\rho_{+}^{i}(\pi),~{}\forall
i\in[1,k]$

Optimize policy with SPI (Algorithm 2 or 3):
$\pi=\texttt{SPI}(\pi,D,\rho_{+},\delta)$

end for

return $\pi$

Algorithm 2 Safe Model-free Policy Improvement (SMFPI)

0: Initial policy $\pi$, data $D\sim\mu_{(\cdot|\pi)}$, safety thresholds
$\rho^{i}_{+}$, confidence $\delta$

$\pi^{\prime}=\pi$

Split $D$ into $D_{train}$ and $D_{test}$.

for $L$ epochs do

Perform $g$ policy updates of policy $\pi^{\prime}$ with data $D_{train}$

Upper bound costs: $\forall
i=1..k~{},~{}\rho^{i}(\pi^{\prime})=HCOPE(\pi^{\prime},D_{test},\delta/k)$

if $\forall i\in[1,k]\,\rho^{i}\leq\rho_{+}^{i}$ then

return $\pi^{\prime}$

end if

end for

return $\pi$ {no better policy found}

Algorithm 3 Safe Model-based Policy Improvement (SMBPI)

0: Initial policy $\pi$, data $D\sim\mu_{(\cdot|\pi)}$, safety thresholds
$\rho^{i}_{+}$, confidence $\delta$

Initialize or reuse predictive model $p_{\theta}$

Empty model buffer $D_{model}$

$\pi^{\prime}=\pi$

Split $D$ into $D_{train}$ and $D_{test}$.

for $L$ epochs do

Fit dynamics model $p_{\theta}$ on dataset $D_{train}$
$\theta\leftarrow\operatorname*{arg\,max}_{\theta}\mathbb{E}[\text{log}\,p_{\theta}(s^{\prime},r,c|s,a)]$

Collect $h$-step predicted trajectories with $\pi^{\prime}$ and store in
$D_{model}$

Perform $g$ policy updates of policy $\pi^{\prime}$ with data $D_{model}$

Upper bound costs: $\forall
i=1..k~{},~{}\rho^{i}(\pi^{\prime})=HCOPE(\pi^{\prime},D_{test},\delta/k)$

if $\forall i=1..k\,\rho^{i}\leq\rho_{+}^{i}$ then

return $\pi^{\prime}$

end if

end for

return $\pi$ {no better policy found}

##  6 Experiments

In this section, we provide an empirical evaluation of the proposed approach.
Since it relies on two distinct contributions, the shaping reward and the
correct-by-construction policy improvement, we structure the experiments in
two phases to evaluate each component in isolation.

###  6.1 Automatic Reward Shaping from Task Specification

We evaluate the proposed reward shaping against two standard RL benchmarks:
(1)  _The cart-pole_ environment, which has already been presented as a
motivating example; (2)  _The bipedal-walker_ , whose main objective is to
move forward towards the end of the field without falling. We formulate one
safety, one target, and four comfort requirements for the bipedal walker.

Aiming to evaluate the automatic reward shaping process from formal task
specifications, we benchmark HPRS against two prior approaches using temporal
logic. To formalize the task in a single specification, we consider it as the
conjunction of safety and target requirements. The baselines methods to shape
a reward signal are the following:

  * •

_TLTL_ [37] specifies tasks in a bounded (Truncated) LTL variant, equipped
with an infinity-norm quantitative semantics [39]. The quantitative evaluation
of the episode is used as a reward. We employ the RTAMT monitoring tool to
compute the episode robustness [44].

  * •

_BHNR_ [7] specifies tasks in a fragment of STL with the filtering semantics
of [49]. The reward uses a sliding-window approach to produce more frequent
feedback to the agent: at each step, it uses the quantitative semantics to
evaluate a sequence of $H$ states.

Since each reward formulation has its scale, comparing the learning curves
needs an external, unbiased assessment metric. To this end, we introduce a
policy-assessment metric (PAM) $F$, capturing the logical satisfaction of
various requirements. We use the PAM to monitor the learning process and
compare HPRS to the baseline approaches (Fig. 3).

Let $\Phi=\Phi_{S}\uplus\Phi_{T}\uplus\Phi_{C}$ be the set of requirements
defining the task. Then, we define $F$ as follows:

$F(\Phi,\tau)=\sigma(\Phi_{S},\tau)+\tfrac{1}{2}\sigma(\Phi_{T},\tau)+\tfrac{1}{4}\sigma_{avg}(\Phi_{C},\tau)$

where $\sigma(\Phi,\tau)\,{\in}\,\\{0,1\\}$ is the satisfaction function
evaluated over $\Phi$ and $\tau$. We also define a time-averaged version for
any comfort requirement $\varphi=\texttt{encourage }p$, as follows:

$\sigma_{avg}(\varphi,\tau)=\sum_{i=1}^{|\tau|}\frac{\mathbb{1}(s_{i}\models
p)}{|\tau|}.$

Its set-wise extension computes the average over the set.

###### Corollary 2

Consider a task $(\Phi,\prec)$ and an episode $\tau$. Then, the following
relations hold for $F$:

$\begin{array}[]{l}F(\Phi,\tau)\geq
1.0\leftrightarrow\tau\models\Phi_{S},\quad F(\Phi,\tau)\geq
1.5\leftrightarrow\tau\models\Phi\end{array}$

Figure 3: Performance evaluation with respect to the Policy Assessment Metric
(PAM). This external metric is not used in training but to provide a sound
evaluation of the requirements and accounting for the different rewards
scales. The threshold indicates the task satisfaction (dashed line), as
explained in Corollary 2. All the curves report mean and standard deviation
over five seeds.

###  6.2 Safe Policy Improvement in Online Setting

We evaluate the Safe Policy Improvement on a simple cart-pole task, where the
agent target is to remain close to the goal location while keeping the pole
safely balanced for an episode of $200$ steps. We benchmark the proposed
algorithm SMFPI with Vanilla Policy Gradient (VPG), which performs
unconstrained updates based on the gradient estimates. We consider two
scenarios of hyperparameter configurations, respectively with a favorable and
unfavorable value of the learning rate ($LR$). Figure 4 shows the performance
as the mean and standard deviation of expected return and cost, aggregated
over many runs. We also report a running estimate of the expected cost for
each run to compare the oscillation of cost during the iterative policy
updates.

Figure 4: Performance for cumulative reward and cost violations under
different hyperparameter configurations with learning rate ($LR$) $0.025$ and
$0.25$. The aggregated performance in the first two rows indicates the mean
and standard deviation over five runs. The last row shows the running cost
estimate on the current batch for each of the five runs.

Under a favorable hyperparameter setting $LR\,{=}\,0.025$, we can observe that
both algorithms iteratively increase the expected return and decrease the
expected cost. As expected, VPG converges faster to the optimal value.
However, under the unfavorable hyperparameter setting $LR\,{=}\,0.25$, the
unconstrained policy update of VPG leads to high variance in the statistics
and catastrophic oscillation in the cost per run. Conversely, SMFPI shows a
good policy improvement and much lower variance in the learning curve due to a
more conservative policy update. We also observe a monotonic decrease in
expected cost, empirically demonstrating the effectiveness of the proposed
approach. We observe small statistical fluctuations in the estimated cost per
run, which could depend on two factors: (1) Online estimation of the cost on
the current batch of data, (2) Use of $\delta\,{=}\,0.05$, which guarantees a
safe update up to certain confidence. When the current batch contains few
samples, the variance of the visualized cost estimate is high. However, SMFPI
does not update the policy in small-data regimes because it cannot guarantee
the improvement with sufficient confidence.

In this experiment, we show that the proposed algorithm is effective for
safely learning a decision policy. Starting from a random policy, SMFPI can
iteratively update the policy until it reaches the optimal return value
without showing any drop in expected cost. Its performance is robust to
different hyperparameters settings, which plays a critical role in modern deep
RL algorithms. Compared with unconstrained RL algorithms under optimal
hyperparameters, the convergence of SMFPI is slower. However, finding the
correct hyperparameters by trial and error is not always an option in critical
applications.

##  7 Conclusion and Future Work

In this work, we presented a policy-synthesis pipeline, showing how to
formalize a CMDP, starting from a set of formal requirements describing the
task. We further enrich the reward with a potential function that does not
alter the policy optimality under the standard potential-based shaping. We
further define correct-by-construction policy-improvement routines and propose
two online algorithms, one model-free and one model-based, to solve the CMDP
starting from an unsafe policy. Using high-confidence off-policy evaluation,
we can guarantee that the proposed algorithms will return an equally good or
improved policy with respect to the safety constraints. We finally evaluate
the overall pipeline, combining reward shaping and correct-by-construction
policy improvement, and show empirical evidence of their effectiveness. The
proposed algorithm is robust under different hyperparameters tuning, while
unconstrained baselines perform updates that deteriorate the safety
performance and preclude the algorithm from converging to optimal
performances.

Compared with previous approaches that mainly focus on a batch setting, we
propose to use high-confidence off-policy evaluation online. In future work,
we intend to investigate the proposed model-based approach regarding data
efficiency and scalability of off-policy evaluation in an online setting. We
plan to extend the benchmarks with more complex tasks, targeting robotics
applications and autonomous driving, study the convergence property more in-
depth, and characterize the eventual distance to the optimal policy.

## Acknowledgement

Luigi Berducci is supported by the Doctoral College Resilient Embedded
Systems. This work has received funding from the Austrian FFG-ICT project
ADEX.

## References

  * [1] Abels, A., Roijers, D., Lenaerts, T., Nowé, A., Steckelmacher, D.: Dynamic weights in multi-objective deep reinforcement learning. In: International Conference on Machine Learning. pp. 11–20. PMLR (2019)
  * [2] Achiam, J., Held, D., Tamar, A., Abbeel, P.: Constrained policy optimization. In: Precup, D., Teh, Y.W. (eds.) Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. Proceedings of Machine Learning Research, vol. 70, pp. 22–31. PMLR (2017), http://proceedings.mlr.press/v70/achiam17a.html
  * [3] Agha, G., Palmskog, K.: A survey of statistical model checking. ACM Transactions on Modeling and Computer Simulation (TOMACS) 28(1), 1–39 (2018)
  * [4] Alshiekh, M., Bloem, R., Ehlers, R., Könighofer, B., Niekum, S., Topcu, U.: Safe reinforcement learning via shielding. CoRR abs/1708.08611 (2017), http://arxiv.org/abs/1708.08611
  * [5] Altman, E.: Constrained markov decision processes with total cost criteria: Lagrangian approach and dual linear program. Mathematical methods of operations research 48(3), 387–417 (1998)
  * [6] Altman, E.: Constrained Markov decision processes, vol. 7. CRC Press (1999)
  * [7] Balakrishnan, A., Deshmukh, J.V.: Structured reward shaping using signal temporal logic specifications. In: 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 3481–3486 (2019). https://doi.org/10.1109/IROS40897.2019.8968254
  * [8] Barrett, L., Narayanan, S.: Learning all optimal policies with multiple criteria. In: Proceedings of the 25th international conference on Machine learning. pp. 41–47 (2008)
  * [9] Berducci, L., Aguilar, E.A., Ničković, D., Grosu, R.: Hierarchical potential-based reward shaping from task specifications. arXiv (2021). https://doi.org/10.48550/ARXIV.2110.02792, https://arxiv.org/abs/2110.02792
  * [10] Bertsekas, D.P.: Constrained optimization and Lagrange multiplier methods. Academic press (2014)
  * [11] Brunke, L., Greeff, M., Hall, A.W., Yuan, Z., Zhou, S., Panerati, J., Schoellig, A.P.: Safe learning in robotics: From learning-based control to safe reinforcement learning. CoRR abs/2108.06266 (2021), https://arxiv.org/abs/2108.06266
  * [12] Brunnbauer, A., Berducci, L., Brandstätter, A., Lechner, M., Hasani, R., Rus, D., Grosu, R.: Latent imagination facilitates zero-shot transfer in autonomous racing. arXiv preprint arXiv:2103.04909 (2021)
  * [13] Brys, T., Harutyunyan, A., Vrancx, P., Taylor, M.E., Kudenko, D., Nowé, A.: Multi-objectivization of reinforcement learning problems by reward shaping. In: 2014 international joint conference on neural networks (IJCNN). pp. 2315–2322. IEEE (2014)
  * [14] Censi, A., Slutsky, K., Wongpiromsarn, T., Yershov, D.S., Pendleton, S., Fu, J.G.M., Frazzoli, E.: Liability, ethics, and culture-aware behavior specification using rulebooks. In: International Conference on Robotics and Automation, ICRA 2019, Montreal, QC, Canada, May 20-24, 2019. pp. 8536–8542 (2019)
  * [15] Chow, Y., Ghavamzadeh, M., Janson, L., Pavone, M.: Risk-constrained reinforcement learning with percentile risk criteria. CoRR abs/1512.01629 (2015), http://arxiv.org/abs/1512.01629
  * [16] Christiano, P.F., Leike, J., Brown, T.B., Martic, M., Legg, S., Amodei, D.: Deep reinforcement learning from human preferences. In: Guyon, I., von Luxburg, U., Bengio, S., Wallach, H.M., Fergus, R., Vishwanathan, S.V.N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA. pp. 4299–4307 (2017), https://proceedings.neurips.cc/paper/2017/hash/d5e2c0adad503c91f91df240d0cd4e49-Abstract.html
  * [17] Chua, K., Calandra, R., McAllister, R., Levine, S.: Deep reinforcement learning in a handful of trials using probabilistic dynamics models. Advances in neural information processing systems 31 (2018)
  * [18] Dalal, G., Dvijotham, K., Vecerík, M., Hester, T., Paduraru, C., Tassa, Y.: Safe exploration in continuous action spaces. CoRR abs/1801.08757 (2018), http://arxiv.org/abs/1801.08757
  * [19] Deisenroth, M., Rasmussen, C.E.: Pilco: A model-based and data-efficient approach to policy search. In: Proceedings of the 28th International Conference on machine learning (ICML-11). pp. 465–472. Citeseer (2011)
  * [20] Deisenroth, M.P., Fox, D., Rasmussen, C.E.: Gaussian processes for data-efficient learning in robotics and control. IEEE transactions on pattern analysis and machine intelligence 37(2), 408–423 (2013)
  * [21] Fu, J., Topcu, U.: Probably approximately correct MDP learning and control with temporal logic constraints. In: Fox, D., Kavraki, L.E., Kurniawati, H. (eds.) Robotics: Science and Systems X, University of California, Berkeley, USA, July 12-16, 2014 (2014). https://doi.org/10.15607/RSS.2014.X.039, http://www.roboticsproceedings.org/rss10/p39.html
  * [22] Gábor, Z., Kalmár, Z., Szepesvári, C.: Multi-criteria reinforcement learning. In: Shavlik, J.W. (ed.) Proceedings of the Fifteenth International Conference on Machine Learning (ICML 1998), Madison, Wisconsin, USA, July 24-27, 1998. pp. 197–205. Morgan Kaufmann (1998)
  * [23] García, J., Fernández, F.: A comprehensive survey on safe reinforcement learning. J. Mach. Learn. Res. 16, 1437–1480 (2015), http://dl.acm.org/citation.cfm?id=2886795
  * [24] Gros, T.P., Hermanns, H., Hoffmann, J., Klauck, M., Steinmetz, M.: Deep statistical model checking. In: International Conference on Formal Techniques for Distributed Objects, Components, and Systems. pp. 96–114. Springer (2020)
  * [25] Ha, D., Schmidhuber, J.: World models. arXiv preprint arXiv:1803.10122 (2018)
  * [26] Hafner, D., Lillicrap, T., Ba, J., Norouzi, M.: Dream to control: Learning behaviors by latent imagination. arXiv preprint arXiv:1912.01603 (2019)
  * [27] Hafner, D., Lillicrap, T., Fischer, I., Villegas, R., Ha, D., Lee, H., Davidson, J.: Learning latent dynamics for planning from pixels. In: International conference on machine learning. pp. 2555–2565. PMLR (2019)
  * [28] Henderson, P., Islam, R., Bachman, P., Pineau, J., Precup, D., Meger, D.: Deep reinforcement learning that matters. In: Proceedings of the AAAI conference on artificial intelligence. vol. 32 (2018)
  * [29] Icarte, R.T., Klassen, T., Valenzano, R., McIlraith, S.: Using reward machines for high-level task specification and decomposition in reinforcement learning. In: International Conference on Machine Learning. pp. 2107–2116. PMLR (2018)
  * [30] Janner, M., Fu, J., Zhang, M., Levine, S.: When to trust your model: Model-based policy optimization. Advances in Neural Information Processing Systems 32 (2019)
  * [31] Jiang, Y., Bharadwaj, S., Wu, B., Shah, R., Topcu, U., Stone, P.: Temporal-logic-based reward shaping for continuing reinforcement learning tasks. Proceedings of the AAAI Conference on Artificial Intelligence 35(9), 7995–8003 (May 2021), https://ojs.aaai.org/index.php/AAAI/article/view/16975
  * [32] Jones, A., Aksaray, D., Kong, Z., Schwager, M., Belta, C.: Robust satisfaction of temporal logic specifications via reinforcement learning (2015)
  * [33] Jothimurugan, K., Bansal, S., Bastani, O., Alur, R.: Compositional reinforcement learning from logical specifications. CoRR abs/2106.13906 (2021), https://arxiv.org/abs/2106.13906
  * [34] Kakade, S., Langford, J.: Approximately optimal approximate reinforcement learning. In: In Proc. 19th International Conference on Machine Learning. Citeseer (2002)
  * [35] Legay, A., Lukina, A., Traonouez, L.M., Yang, J., Smolka, S.A., Grosu, R.: Statistical model checking. In: Computing and Software Science, pp. 478–504. Springer (2019)
  * [36] Li, X., Ma, Y., Belta, C.: A policy search method for temporal logic specified reinforcement learning tasks. 2018 Annual American Control Conference (ACC) pp. 240–245 (2018)
  * [37] Li, X., Vasile, C.I., Belta, C.: Reinforcement learning with temporal logic rewards. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 3834–3839 (2017). https://doi.org/10.1109/IROS.2017.8206234
  * [38] Liu, C., Xu, X., Hu, D.: Multiobjective reinforcement learning: A comprehensive overview. IEEE Transactions on Systems, Man, and Cybernetics: Systems 45(3), 385–398 (2015). https://doi.org/10.1109/TSMC.2014.2358639
  * [39] Maler, O., Nickovic, D.: Monitoring temporal properties of continuous signals. In: Lakhnech, Y., Yovine, S. (eds.) Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems. pp. 152–166. Springer Berlin Heidelberg, Berlin, Heidelberg (2004)
  * [40] Massart, P.: Concentration inequalities and model selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII-2003. Springer (2007)
  * [41] Nagabandi, A., Kahn, G., Fearing, R.S., Levine, S.: Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning. In: 2018 IEEE International Conference on Robotics and Automation (ICRA). pp. 7559–7566. IEEE (2018)
  * [42] Natarajan, S., Tadepalli, P.: Dynamic preferences in multi-criteria reinforcement learning. In: Proceedings of the 22nd international conference on Machine learning. pp. 601–608 (2005)
  * [43] Ng, A.Y., Harada, D., Russell, S.: Policy invariance under reward transformations: Theory and application to reward shaping. In: In Proceedings of the Sixteenth International Conference on Machine Learning. pp. 278–287. Morgan Kaufmann (1999)
  * [44] Ničković, D., Yamaguchi, T.: Rtamt: Online robustness monitors from stl. In: International Symposium on Automated Technology for Verification and Analysis. pp. 564–571. Springer (2020)
  * [45] Phan, D.T., Paoletti, N., Grosu, R., Jansen, N., Smolka, S.A., Stoller, S.D.: Neural simplex architecture. CoRR abs/1908.00528 (2019), http://arxiv.org/abs/1908.00528
  * [46] Pirotta, M., Restelli, M., Pecorino, A., Calandriello, D.: Safe policy iteration. In: International Conference on Machine Learning. pp. 307–315. PMLR (2013)
  * [47] Precup, D.: Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series p. 80 (2000)
  * [48] Puranic, A.G., Deshmukh, J.V., Nikolaidis, S.: Learning from demonstrations using signal temporal logic in stochastic and continuous domains. IEEE Robotics and Automation Letters 6(4), 6250–6257 (2021). https://doi.org/10.1109/LRA.2021.3092676
  * [49] Rodionova, A., Bartocci, E., Nickovic, D., Grosu, R.: Temporal logic as filtering. In: Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control. pp. 11–20 (2016)
  * [50] Roijers, D.M., Vamplew, P., Whiteson, S., Dazeley, R.: A survey of multi-objective sequential decision-making. J. Artif. Int. Res. 48(1), 67–113 (Oct 2013)
  * [51] Saunders, W., Sastry, G., Stuhlmüller, A., Evans, O.: Trial without error: Towards safe reinforcement learning via human intervention. CoRR abs/1707.05173 (2017), http://arxiv.org/abs/1707.05173
  * [52] Schulman, J., Levine, S., Moritz, P., Jordan, M.I., Abbeel, P.: Trust region policy optimization. CoRR abs/1502.05477 (2015), http://arxiv.org/abs/1502.05477
  * [53] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)
  * [54] Shalev-Shwartz, S., Shammah, S., Shashua, A.: Safe, multi-agent, reinforcement learning for autonomous driving. CoRR abs/1610.03295 (2016), http://arxiv.org/abs/1610.03295
  * [55] Shelton, C.: Balancing multiple sources of reward in reinforcement learning. In: Leen, T., Dietterich, T., Tresp, V. (eds.) Advances in Neural Information Processing Systems. vol. 13. MIT Press (2001)
  * [56] Thananjeyan, B., Balakrishna, A., Nair, S., Luo, M., Srinivasan, K., Hwang, M., Gonzalez, J.E., Ibarz, J., Finn, C., Goldberg, K.: Recovery RL: safe reinforcement learning with learned recovery zones. IEEE Robotics Autom. Lett. 6(3), 4915–4922 (2021). https://doi.org/10.1109/LRA.2021.3070252, https://doi.org/10.1109/LRA.2021.3070252
  * [57] Thomas, P., Theocharous, G., Ghavamzadeh, M.: High-confidence off-policy evaluation. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 29 (2015)
  * [58] Thomas, P., Theocharous, G., Ghavamzadeh, M.: High confidence policy improvement. In: Bach, F., Blei, D. (eds.) Proceedings of the 32nd International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 37, pp. 2380–2388. PMLR, Lille, France (07–09 Jul 2015), https://proceedings.mlr.press/v37/thomas15.html
  * [59] Thomas, P.S.: Safe reinforcement learning (2015)
  * [60] Thomas, P.S., Castro da Silva, B., Barto, A.G., Giguere, S., Brun, Y., Brunskill, E.: Preventing undesirable behavior of intelligent machines. Science 366(6468), 999–1004 (2019)
  * [61] Toro Icarte, R., Klassen, T.Q., Valenzano, R., McIlraith, S.A.: Teaching multiple tasks to an rl agent using ltl. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. pp. 452–461 (2018)
  * [62] Van Moffaert, K., Drugan, M.M., Nowé, A.: Scalarized multi-objective reinforcement learning: Novel design techniques. In: 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL). pp. 191–199 (2013). https://doi.org/10.1109/ADPRL.2013.6615007
  * [63] Viswanadha, K., Kim, E., Indaheng, F., Fremont, D.J., Seshia, S.A.: Parallel and multi-objective falsification with scenic and verifai. In: International Conference on Runtime Verification. pp. 265–276. Springer (2021)
  * [64] Wilcox, A., Balakrishna, A., Thananjeyan, B., Gonzalez, J.E., Goldberg, K.: LS3: latent space safe sets for long-horizon visuomotor control of iterative tasks. CoRR abs/2107.04775 (2021), https://arxiv.org/abs/2107.04775
  * [65] Zhao, Y., Chen, Q., Hu, W.: Multi-objective reinforcement learning algorithm for mosdmp in unknown environment. In: 2010 8th World Congress on Intelligent Control and Automation. pp. 3190–3194 (2010). https://doi.org/10.1109/WCICA.2010.5553980


# Neural Networks Meet Elliptic Curve Cryptography: A Novel Approach to Secure
Communication

Mina Cecilie Wøien1, Ferhat Ozgur Catak1  1Electrical Eng. and Computer
Science
University of Stavanger
Rogaland, Norway
<EMAIL_ADDRESS><EMAIL_ADDRESS>Murat Kuzlu  Batten College of
Eng. and Tech.
Old Dominion University
Norfolk, VA, USA
<EMAIL_ADDRESS>Umit Cali  School of Physics, Eng. and Technology
University of York
York, UK
<EMAIL_ADDRESS>
###### Abstract

In recent years, neural networks have been used to implement symmetric
cryptographic functions for secure communications. Extending this domain, the
proposed approach explores the application of asymmetric cryptography within a
neural network framework to safeguard the exchange between two communicating
entities, i.e., Alice and Bob, from an adversarial eavesdropper, i.e., Eve. It
employs a set of five distinct cryptographic keys to examine the efficacy and
robustness of communication security against eavesdropping attempts using the
principles of elliptic curve cryptography. The experimental setup reveals that
Alice and Bob achieve secure communication with negligible variation in
security effectiveness across different curves. It is also designed to
evaluate cryptographic resilience. Specifically, the loss metrics for Bob
oscillate between 0 and 1 during encryption-decryption processes, indicating
successful message comprehension post-encryption by Alice. The potential
vulnerability with a decryption accuracy exceeds 60%, where Eve experiences
enhanced adversarial training, receiving twice the training iterations per
batch compared to Alice and Bob.

###### Index Terms:

Artificial Intelligence, Elliptic Curve, Neural Cryptography

##  I Introduction

Artificial Intelligence (AI) has provided significant advances in various
domains, such as facilitating the integration of sophisticated analytical and
predictive capabilities. The advanced capabilities of AI-based methods, such
as rapid data processing and pattern recognition, make them a superior
alternative to traditional methodologies, especially in scenarios requiring
accurate decision-making [1]. Cryptography is essential in securing smart
grids and ensuring data privacy, authentication, and efficient communication
[2]. Public key cryptography, Elliptic Curve Cryptography (ECC), and identity-
based cryptography are among the techniques used in the field of smart grids
[3]. The techniques prevent various attacks on devices and address resource
constraints in smart meters [4]. Similarly, AI also has significant
contribution to natural language processing (NLP), i.e., enabling the
development of sophisticated text generation algorithms and improving
interactive technologies such as ChatGPT, improving user engagement and
service delivery in customer service applications [5]. Cryptography
encompasses several methods to transform plain messages into encrypted
ciphertexts, which can only be decrypted by authorized parties possessing the
required key. There are two types of cryptography methods to achieve this.

In recent years, the relationship between AI and cryptography has increased
significantly along with exploring the potential of neural networks for
algorithmic cryptography. Recent studies have demonstrated the ability of
neural networks to design secure communication protocols using symmetric
cryptography [6]. The study [7] introduces a new approach to cryptography
utilizing neural networks, i.e., neural networks automatically generate
cryptographic schemes. The experimental results of the study also confirm the
ability of the architecture for automatic encryption and decryption, along
with the achievement of a neural symmetric cryptosystem. The other study [8]
in Adversarial Neural Cryptography proposes a framework in which neural
networks, through adversarial training, learn to encrypt and decrypt messages,
effectively mimicking cryptographic functions. The main contribution of the
current study is the application of asymmetric cryptography within an AI
context, employing ECC to secure communications between neural network
entities, herein referred to as Alice and Bob, against an eavesdropping
entity, Eve. This study contributes to the burgeoning field of neural
cryptography by demonstrating the feasibility of employing asymmetric
cryptographic principles in neural network-based secure communication
protocols.

The remainder of this paper is organized as follows. Section II provides the
contemporary research landscape in neural cryptography. Section III provides
background related to cryptography and neural networks. Section IV details the
asymmetric neural cryptography model used in this study. The experimental
results are presented and discussed in Section V, followed by the conclusion
remarks and directions for future research in Section VI. The developed source
code for this project is publicly available on GitHub
repository111https://github.com/minawoien/Neural-Cryptography.

##  II Related Work

The integration of neural networks into the cryptography domain represents a
novel intersection of AI and information security, offering innovative avenues
for the development of secure communication protocols. The exploration of AI
as a mechanism for implementing cryptographic functions has garnered
increasing interest, particularly in enhancing security against sophisticated
adversarial models. Zhou et al. [9] provide a comprehensive examination of
this emerging paradigm, focusing on applying neural networks to encryption
tasks and assessing security in the presence of powerful adversaries. Their
work underscores the potential of deep learning (DL) techniques to redefine
traditional cryptographic practices.

The seminal work by Abadi and Andersen [8] marked a pivotal advance in the
field, demonstrating the ability of neural networks to learn encryption and
decryption processes autonomously through adversarial training. In their
framework, a trio of neural networks engage in a cryptographic game in which
Alice and Bob aim to secure their communication from the eavesdropping
attempts by Eve, facilitated by a shared secret key. This study established
the foundation for future studies on adversarial neural cryptography or
Adversarial Neural Cryptography (ANC). However, the ANC model proposed by
Abadi and Andersen has been investigated with regard to security concerns.
Coutinho et al. [1] critically analyzed the ANC model in terms of its security
assessment. They indicated that the proposed ANC model does not adequately
simulate realistic adversarial conditions predicated on Eve’s difficulty in
decrypting messages without access to the ciphertext. They proposed an
enhanced model, i.e., Chosen-Plaintext Attack Adversarial Neural Cryptography
(CPA-ANC). In this enhanced model, Eve selects one of two messages for Alice
to encrypt, providing a more stringent test of the cryptographic system’s
security. According to the results, the CPA-ANC model demonstrates improved
resilience against adversarial decryption attempts, while the original ANC
model may not offer robust security. Meraouche et al. [10] extended the
concept of adversarial neural cryptography by incorporating asymmetric
cryptographic principles based on these foundational studies. Their model
introduces additional neural networks, which generate key pairs, facilitating
secure communication through public and private keys.

All of these studies contribute to adversarial neural cryptography by
systematically analyzing the application of asymmetric cryptographic
techniques within a neural network framework. This study aims to evaluate the
efficacy of neural networks in securing communications against eavesdropping
attempts using ECC.

##  III Background

###  III-A Asymmetric Cryptography

Asymmetric cryptography is one of the widely used encryption methods, which is
also known as public-key cryptography. It uses a public key-private key
pairing, i.e., a public key for encryption and a private key for decryption,
and differs from symmetric cryptography using the same key both encrypts and
decrypts data.

ECC is a cryptographic approach used in asymmetric cryptography, which
utilizes the principles of elliptic curve theory. It is also considered an
alternative to the Rivest-Shamir-Adleman (RSA) cryptographic algorithm, which
is frequently used for digital signatures. ECC provides several advantages,
i.e., faster, smaller, and more efficient in generating cryptographic keys. In
particular, the efficiency of the ECC makes it well-suited for environments
with limited computational resources [11].

###  III-B Generative Adversarial Networks (GANs)

Generative Adversarial Networks (GANs) introduce a novel approach within the
realm of unsupervised learning, consisting of two competing neural network
models: a generator producing synthetic data similar to training data and a
discriminator evaluating the authenticity of real and generated data [12].
Through iterative adversarial training, both networks improve their
performance, with the generator producing increasingly convincing data and the
discriminator becoming more adept at distinguishing between real and generated
inputs. This approach has been applied to many applications such as image
generation, image-to-image translation, text-to-image translation, 3D object
generation, semantic-image-to-photo Translation, style transfer, and more
recently, adversarial neural cryptography [13, 14].

##  IV System model

This section describes the proposed asymmetric neural cryptography model built
on Pacurar’s implementation of asymmetric neural
cryptography222https://mathybit.github.io/adversarial-neural-crypto/.

###  IV-A Overview

The proposed asymmetric neural cryptography model in this study includes the
deployment of neural network architectures to simulate participants in a
typical cryptographic system, i.e., sender, receiver, and eavesdropper, shown
in Fig. 1. The model is implemented by engaging with three separate neural
networks, namely Alice, Bob, and Eve. Bob initiates the communication by
generating a pair of keys, i.e., a public key, $K_{\text{PUBLIC}}$, and a
private key, $K_{\text{PRIVATE}}$. The public key is openly shared with Alice
(and accessible to Eve), while the private key remains confidential to Bob.
Alice utilizes $K_{\text{PUBLIC}}$ to encrypt her plaintext message, $P$,
producing a ciphertext, $C$. This encrypted message is then transmitted to
Bob, who employs $K_{\text{PRIVATE}}$ to decrypt $C$ and recover the original
message $P$. At the same time, Eve endeavors to intercept and decipher the
encrypted message without having Bob’s private key, representing the
adversarial risk in this cryptographic scenario. The success of the model
depends on the challenge of inferring $K_{\text{PRIVATE}}$ from
$K_{\text{PUBLIC}}$. In addition, the utilization of neural networks in this
context aims not only to replicate the encryption and decryption processes but
also to resist eavesdropping attempts by Eve adaptively to guarantee the
confidentiality of Alice and Bob’s communication.

Figure 1: Asymmetric cryptosystem.

###  IV-B Architecture

The architecture is adapted from generative adversarial networks (GANs) to the
cryptographic concept. It consists of developing a specialized neural network
architecture for secure communication using the principles of ECC [11]. As
seen in Fig. 3, there are three primary neural network entities, i.e., Alice,
Bob, and Eve, and each entity represents the sender, receiver, and
eavesdropper, respectively. The most critical process in the architecture is
to generate an ECC key, where Bob generates a key pair consisting of a public
key, $K_{\text{PUBLIC}}$, and a private key, $K_{\text{PRIVATE}}$.

Alice’s network encrypts messages in plaintext., $P$, using Bob’s public key
to generate ciphertext, $C$, as shown in Fig. 2. This encrypted message is
transmitted to Bob, who utilizes his private key to decrypt the message. The
neural network architectures of Alice and Bob are designed to optimize this
encryption-decryption cycle, and guarantee the confidentiality and integrity
of the transmitted information. Fig. 3 illustrates the overall communication
system, highlighting the information flow and the interaction among neural
networks.

Eve intercepts the ciphertext and attempts decryption without access to Bob’s
private key, i.e., an eavesdropper. Eve’s network challenges the encryption
process to simulate adversarial attempts to breach communication security.

The training of neural networks uses an iterative adversarial training
methodology similar to that used in GANs. This approach involves alternating
between training Alice and Bob to enhance their communication security and
training Eve to improve her eavesdropping capabilities. The objective is to
reach an equilibrium where Alice and Bob can securely communicate without Eve
successfully decrypting the messages, thereby ensuring the effectiveness of
the proposed asymmetric neural cryptography model.

Figure 2: Encryption process flow, illustrating how Alice encrypts a plaintext
message using Bob’s public key.

Figure 3: Overview of the system, the interaction between Alice, Bob, and Eve.

###  IV-C Training

The training process is illustrated in Fig. 4, Alice initiates the process by
creating a plaintext message that she wants to send to Bob privately. On the
other hand, Bob generates a key pair using an elliptic curve consisting of a
public key and a private key. The public key is shared between Alice and Eve.
Alice then encrypts the plaintext message using the public key, which produces
a ciphertext. Both Bob and Eve receive this ciphertext. Bob attempts to
decrypt the ciphertext using his private key, while Eve tries to decrypt it
using only Bob’s public key. If Bob’s decrypted message matches the original
plaintext with a high degree of accuracy and Eve’s accuracy is significantly
lower, the parameters are saved, and the training process ends. If not, the
parameters are updated, and the training process continues.

Figure 4: Training flow of the neural networks.

During the training phase, the ABE model, Eve model, and Bob’s loss are
computed using the same approach as that of Pacurar’s implementation. The loss
of Bob signifies his proficiency in decrypting messages, while the loss of Eve
indicates her ability to intercept the communication between Alice and Bob.
This loss is determined by subtracting the predicted outcome - the output
produced by Eve or Bob - from the target output, which is Alice’s plaintext
message. Bob’s loss is presented in Eq. 1.

$\ell\textsubscript{BOB}=\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{m_{\text{bits}}}\left|P{{}_{ij}}-O_{\text{ij}}\right|$
(1)

where $\ell\textsubscript{BOB}$ is the loss function, $P_{ij}$ is the
plaintext, $O_{ij}$ is Bob’s predicted outcome, $N$ is the batch size, and
$m\textsubscript{bits}$ is the message size. Eve’s loss is defined in Eq. 2.

$\ell\textsubscript{EVE}=\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{m_{\text{bits}}}\left|P{{}_{ij}}-O_{\text{ij}}\right|$
(2)

where $\ell\textsubscript{EVE}$ is the loss function and $O_{ij}$ is Eve’s
predicted outcome. The ABE loss is calculated concerning Bob’s loss and Eve’s
loss as shown in Eq. 3

$\ell\textsubscript{ABE}=\ell\textsubscript{BOB}+\frac{\left(\frac{m_{\text{bits}}}{2}-\ell\textsubscript{EVE}\right)^{2}}{\left(\frac{m_{\text{bits}}}{2}\right)^{2}}$
(3)

where $\ell\textsubscript{ABE}$ is the loss function of the ABE model,
$\ell\textsubscript{BOB}$ is Bob’s loss function, $\ell\textsubscript{EVE}$ is
Eve’s loss function and $m\textsubscript{bits}$ is the message size. This loss
indicates whether Alice and Bob need to improve their strategy, as it shows
how well Alice and Bob work together while Eve performs poorly. If Eve is
doing too well, this loss will be high.

Neural network models are trained using an epoch size of 20 and a batch size
of 512. An epoch refers to the number of times that models are trained in the
entire data set, while batch size signifies the number of data set rows that
are used simultaneously [15]. The message space is defined as
$2^{m_{\text{bits}}}$, where mbits denotes the length of the message of 16.
The number of iterations per epoch is calculated by dividing the message space
by the batch size, resulting in 2500 iterations.

During the training of the ABE model, a set of keys is generated for each
message. The process entails the creation of 512 batches of messages
consisting of 16 bits and 512 batches of public/private keys. The same
approach is implemented for the Eve model, except that the private key is not
accessible.

Algorithm 1 Train the ABE model.

1: epoch = 0

2: abeLoss = []

3: bobLoss = []

4: while epoch $<$ n_epochs do

5: for iteration from 0 to n_batches do

6: Set Alice.trainable to True

7: for cycle in from 0 to abecycles do

8: messages = generateRandomBatchMessages()

9: privKeys, pubKeys = getBatchKeyPairs()

10: loss = abeModel.Train(messages, pubKeys, privKeys)

11: end for

12: Append(abeLoss, loss)

13: ciphertext = Alice.Predict(messages, pubKeys)

14: decryptedText = Bob.Predict(ciphertext, privKeys)

15: loss = calculateAverageLoss(decryptedText, message)

16: Append(bobLoss, loss)

17: end for

18: epoch += 1

19: end while

The ABE model training process is made up of the training of Alice and Bob, as
demonstrated in Algorithm 1. In each epoch, the ABE model and Bob’s loss are
calculated for each batch, and Alice’s training is enabled. In this
experiment, a single cycle generates 512 messages of size 16 and 512 key pairs
per batch. These messages and key pairs are utilized to train the ABE model,
with the model’s weights being updated throughout the training process. After
each training iteration, the loss value is determined333
https://keras.io/api/models/model_training_apis. Upon completion of the
training cycle, the combined loss of Alice’s ability to encrypt messages and
Bob’s ability to decrypt them is recorded in `abeLoss`.

Alice encrypts a batch of messages following the current training to determine
Bob’s decryption capability. Subsequently, Bob leverages the `Predict` method
to decrypt the encrypted messages received. This method is utilized in trained
models to generate predictions. Bob’s loss is calculated according to equation
1 and stored in `bobLoss`.

Algorithm 2 outlines the Eve model’s training process. During each epoch, the
loss value of Eve is stored in the variable `eveLoss`, while Alice is set to
non-trainable to train Eve. The current study examined the effect of training
Eve using one and two cycles to observe the advantage of allowing Eve to train
twice for each batch, while Alice and Bob only train once. A batch of 512
messages containing 16 bits and a batch of 512 public keys were randomly
generated for each cycle to train Eve.

Algorithm 2 Train the EVE model.

1: epoch = 0

2: eveLoss = []

3: while epoch $<$ n_epochs do

4: for iteration from 0 to n_batches do

5: Set Alice.trainable to False

6: for cycle in from 0 to evecycles do

7: messages = generateRandomBatchMessages()

8: publicKeys = getBatchPublicKeys()

9: loss = eveModel.Train(messages, publicKeys)

10: end for

11: Append(eveLoss, loss)

12: end for

13: epoch += 1

14: end while

##  V Results

The study involved the application of five distinct prime curves with varying
key sizes to generate elliptic key pairs for Bob. The secp224r1 curve was
utilized with a key size of 224 bits, while the secp256k1, secp256r1,
secp384r1, and secp521r1 curves were used with key sizes of 256, 384, and 521
bits, respectively. The ABE model was trained once for each batch, and the
results were measured when Eve was trained once for one batch and when she was
trained twice to test the security using improved adversarial training. The
entire training process was repeated five times using the same elliptic curve
and consistent variables for both the ABE and Eve models. Subsequently, the
average results of these five training sessions were calculated to ensure a
robust evaluation.

Fig. 5 shows the loss functions for the ABE model, Bob and Eve, for each
elliptic curve when the ABE model and the Eve model train only once for each
batch. Eve has a constant loss of 8 in these figures, visualized by the red
line, which is 50% of the message size of 16 bits, indicating random guessing.
The green curve represents the loss of Bob, while the blue curve represents
the loss of the ABE model. These decreasing curves show that Alice and Bob are
learning to protect their communication.

(a) Curve: secp224r1

(b) Curve: secp256k1

(c) Curve: secp256r1

(d) Curve: secp384r1

(e) Curve: secp521r1

Figure 5: Loss functions for the ABE model, Bob and Eve, with different
curves.

The ABE model’s loss values, after 2500 iterations, are shown in Table I.
These values are the average of five training iterations. The ABE loss
indicates the relationship between how well Alice can encrypt messages and how
well Bob can decrypt them, while Eve should not be able to decrypt them. At
the end of the training, the ABE model has a loss value between 0 and 1,
indicating the minimum loss or error in the encryption and decryption process,
while Eve performs poorly. Bob also has loss values between 0 and 1, meaning
that Bob’s decryption of the ciphertext is close to Alice’s original
plaintext. Eve’s loss value is approximately 8, also shown in Fig 5, meaning
she is not learning how to decrypt the ciphertext and is not performing better
than random guessing.

TABLE I: Loss values for the ABE model, Bob and Eve, with different curves. | ABE loss | Bob loss | Eve loss
---|---|---|---
secp224r1 | 0.871 | 0.87 | 7.968
secp256k1 | 1.313 | 1.312 | 7.97
secp256r1 | 1.005 | 1.003 | 7.964
secp384r1 | 0.85 | 0.849 | 7.965
secp521r1 | 0.927 | 0.927 | 7.975

After training for 2500 iterations, Alice encrypts another message to
calculate Bob and Eve’s decryption accuracy. The accuracy is shown in Table
II. The values are calculated by adding the corrected decrypted bits and
dividing them by the total number of bits. Bob decrypts the ciphertext using
his private key and obtains a decryption accuracy of approximately 100%. In
four of the five different curves, Bob’s accuracy is 100%, and only one is
99.92%, meaning that even though Bob’s loss is not exactly zero at the end of
the training, Bob’s decryption process is highly accurate. Eve tries to
decrypt the ciphertext without the private key, but only obtains a decryption
accuracy of approximately 50%.

TABLE II: Decryption accuracy for Bob and Eve with different curves. | Bob | Eve
---|---|---
secp224r1 | 100% | 51.19%
secp256k1 | 100% | 55.74%
secp256r1 | 99.92% | 53.51%
secp384r1 | 100% | 51.914%
secp521r1 | 100% | 51.29%

These results show that Alice and Bob can secure their communication from an
eavesdropping neural network when the neural network models train once for
each batch. Bob can decrypt Alice’s message using the correct key, while Eve
can not make sense of the message without the correct key. To further test the
security, the encryption system is tested with improved adversarial training,
where Eve has the advantage of training twice for each batch. At the same
time, Alice and Bob only trained once. Fig. 6 shows the loss functions for the
ABE model, Bob, and Eve for this scenario with five training iterations for
the five elliptic curves. In these figures, all loss functions begin to
decrease at approximately 250 iterations. The loss of the ABE model and Bob
continues to decrease with the iterations, while Eve’s loss function decreases
for the first 1000 iterations before the loss varies between 6 and 7. This
indicates that Eve is learning more because she has the advantage of training
twice for each batch. In these figures, the loss function of the ABE model is
slightly higher than Bob’s loss function due to Eve’s improvement in
performance.

(a) Curve: secp224r1

(b) Curve: secp256k1

(c) Curve: secp256r1

(d) Curve: secp384r1

(e) Curve: secp521r1

Figure 6: Loss functions for the ABE model, Bob and Eve, with different curves
when Eve trains with two cycles.

Table III shows the loss values of the ABE model, Bob and Eve after training
for 2500 iterations. The ABE loss and Bob’s loss are between 0 and 1, as when
Eve trained with only one cycle for each batch, as shown in Table I. However,
the ABE loss is slightly higher than Bob’s loss, compared with the results in
Table I, where the ABE loss and Bob’s loss were almost equal, as a result of
Eve’s improvement in performance. Bob’s loss is nearly the same as in the
previous result, meaning he is performing as well now. Eve’s loss values now
range from about 6.397 to 6.674 when she trains with two iterations for each
batch. This is better than random guessing, which means that she correctly
decrypts bits for more than 50% of the message. Although she is not close to
correctly decrypting the entire message, she has improved his decryption
process compared to her attempt shown in Table I.

TABLE III: Loss values for the ABE model, Bob and Eve. | ABE loss | Bob loss | Eve loss
---|---|---|---
secp224r1 | 0.985 | 0.935 | 6.396
secp256k1 | 1.143 | 1.111 | 6.674
secp256r1 | 0.992 | 0.952 | 6.514
secp384r1 | 1.094 | 1.058 | 6.602
secp521r1 | 0.958 | 0.912 | 6.497

Table IV shows Bob and Eve’s decryption accuracy. Bob has a decryption
accuracy of approximately 100%, which is the same as before, as shown in Table
II, which means that Eve’s improvement in performance does not affect Bob’s
ability to decrypt messages. However, Eve’s decryption accuracy has increased
from ranging between 51% and 55% using one cycle to between 61% and 65% when
she trains with two cycles. It is still far from perfect accuracy, as Bob
achieves using the correct key.

TABLE IV: Decryption accuracy for Bob and Eve with different curves when Eve trains with two cycles. | Bob | Eve
---|---|---
secp224r1 | 99.673% | 65.256%
secp256k1 | 100% | 61.33%
secp256r1 | 100% | 63.83%
secp384r1 | 100% | 64.614%
secp521r1 | 99.998% | 65.33%

##  VI Conclusion

This investigation into asymmetric neural cryptography has clarified the
potential of integrating ECC within AI models to strengthen secure
communication channels against adversarial eavesdropping. Through an
experimental protocol using a variety of ECC curves, it is quantitatively
demonstrated that the proposed neural network models, representing the
communicative entities Alice and Bob, can achieve a high degree of secure
message exchange with minimal variation in security efficacy across different
cryptographic curves. The results indicate a robust encryption-decryption
mechanism capable of maintaining message integrity, as evidenced by Bob’s loss
metrics oscillating between 0 and 1, signifying Alice’s near-perfect message
reconstruction post-encryption.

The introduction of enhanced adversarial training, in which the eavesdropper
model Eve underwent training iterations at double the frequency of Alice and
Bob, unveiled a nuanced vulnerability within the system. Eve’s decryption
accuracy, surpassing 60% under these conditions, heralds a potential security
risk, albeit slight, under scenarios of advanced adversarial intervention.
This finding underscores the necessity for continuous refinement of the neural
cryptography model, particularly to optimize its resilience against
increasingly sophisticated eavesdropping techniques.

In light of these findings, the future trajectory of this research is poised
to explore the implementation of CPA methodologies. Such approaches will
evaluate the cryptographic system’s security, aiming to bolster its defenses
and mitigate the vulnerabilities highlighted by the enhanced adversarial
training paradigm. Furthermore, extending the model to incorporate dynamic
mechanisms of key generation and exchange could further enhance its security
framework, aligning with the evolving landscape of digital communication
threats.

## References

  * [1] M. Coutinho, R. De Oliveira Albuquerque, F. Borges, L. J. García Villalba, and T.-H. Kim, “Learning perfectly secure cryptography to protect communications with adversarial neural cryptography,” _Sensors_ , vol. 18, no. 5, 2018. [Online]. Available: https://www.mdpi.com/1424-8220/18/5/1306
  * [2] M. M. Mahmoud, J. Mišić, K. Akkaya, and X. Shen, “Investigating public-key certificate revocation in smart grid,” _IEEE Internet of Things Journal_ , vol. 2, no. 6, pp. 490–503, 2015.
  * [3] L. Zhang, S. Tang, and H. Luo, “Elliptic curve cryptography-based authentication with identity protection for smart grids,” _PloS one_ , vol. 11, no. 3, p. e0151253, 2016.
  * [4] C. N. Priyanka and N. Ramachandran, “Analysis on secured cryptography models with robust authentication and routing models in smart grid,” _International Journal of Safety and Security Engineering_ , vol. 13, pp. 69–79, 2023.
  * [5] P. Bajaj, D. Campos, N. Craswell, L. Deng, J. Gao, X. Liu, R. Majumder, A. McNamara, B. Mitra, T. Nguyen _et al._ , “Ms marco: A human generated machine reading comprehension dataset,” _arXiv preprint arXiv:1611.09268_ , 2016.
  * [6] I. Meraouche, S. Dutta, H. Tan, and K. Sakurai, “Neural networks-based cryptography: A survey,” _IEEE Access_ , vol. 9, pp. 124 727–124 740, 2021\.
  * [7] Y. Zhu, D. V. Vargas, and K. Sakurai, “Neural cryptography based on the topology evolving neural networks,” in _2018 Sixth International Symposium on Computing and Networking Workshops (CANDARW)_ , 2018, pp. 472–478.
  * [8] M. Abadi and D. G. Andersen, “Learning to protect communications with adversarial neural cryptography,” _CoRR_ , vol. abs/1610.06918, 2016. [Online]. Available: http://arxiv.org/abs/1610.06918
  * [9] L. Zhou, J. Chen, Y. Zhang, C. Su, and M. Anthony James, “Security analysis and new models on the intelligent symmetric key encryption,” _Computers & Security_, vol. 80, pp. 14–24, 2019. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167404818309647
  * [10] I. Meraouche, S. Dutta, H. Tan, and K. Sakurai, “Learning asymmetric encryption using adversarial neural networks,” _Engineering Applications of Artificial Intelligence_ , vol. 123, p. 106220, 2023. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0952197623004049
  * [11] J. VenkataGiri and A. Murty, “Elliptical curve cryptography design principles,” in _2021 International Conference on Recent Trends on Electronics, Information, Communication & Technology (RTEICT)_, 2021, pp. 889–893.
  * [12] A. Creswell, T. White, V. Dumoulin, K. Arulkumaran, B. Sengupta, and A. A. Bharath, “Generative adversarial networks: An overview,” _IEEE signal processing magazine_ , vol. 35, no. 1, pp. 53–65, 2018.
  * [13] S. Sarp, M. Kuzlu, E. Wilson, and O. Guler, “Wg2an: Synthetic wound image generation using generative adversarial network,” _The Journal of Engineering_ , vol. 2021, no. 5, pp. 286–294, 2021.
  * [14] M. Kuzlu, Z. Xiao, S. Sarp, F. O. Catak, N. Gurler, and O. Guler, “The rise of generative artificial intelligence in healthcare,” in _2023 12th Mediterranean Conference on Embedded Computing (MECO)_ , 2023, pp. 1–4.
  * [15] A. Gupta. (Sep 3, 2023) A comprehensive guide on optimizers in deep learning. (accessed: 31.10.23). [Online]. Available: https://www.analyticsvidhya.com/blog/2021/10/a-comprehensive-guide-on-deep-learning-optimizers/