# Towards Theoretical Understanding of Data-Driven Policy Refinement

Ali Baheri

###### Abstract

This paper presents an approach for data-driven policy refinement in
reinforcement learning, specifically designed for safety-critical
applications. Our methodology leverages the strengths of data-driven
optimization and reinforcement learning to enhance policy safety and
optimality through iterative refinement. Our principal contribution lies in
the mathematical formulation of this data-driven policy refinement concept.
This framework systematically improves reinforcement learning policies by
learning from counterexamples identified during data-driven verification.
Furthermore, we present a series of theorems elucidating key theoretical
properties of our approach, including convergence, robustness bounds,
generalization error, and resilience to model mismatch. These results not only
validate the effectiveness of our methodology but also contribute to a deeper
understanding of its behavior in different environments and scenarios.

## Introduction

In the pursuit of creating autonomous systems that not only perform optimally
but also operate safely in real-world environments, the field of artificial
intelligence and robotics has increasingly turned to reinforcement learning
(RL). The inherent ability of RL to learn and optimize behaviors through
interaction with its environment makes it an attractive methodology for
autonomous systems. However, as we continue to deploy these learning-enabled
systems in safety-critical domains such as autonomous driving, healthcare, and
aerospace, ensuring their safe operation becomes a paramount concern. The risk
of unsafe behavior, particularly in uncertain and dynamically changing
environments, poses a significant challenge (Dulac-Arnold, Mankowitz, and
Hester 2019).

The need for safety assurance in RL, especially in safety-critical
applications, has motivated many advances in the field, yet considerable
challenges remain (Kober, Bagnell, and Peters 2013; Kiran et al. 2021;
Razzaghi et al. 2022). Safe RL focuses on designing learning algorithms that
consider safety constraints throughout the learning process, not just as an
afterthought. These safety constraints could involve minimizing harm to the
environment, adhering to specific operational guidelines, or ensuring minimal
deviation from expected behavior. Various strategies for safe RL have been
proposed, including methods that incorporate safety constraints into the RL
objective function, techniques that allow risk-averse exploration, and
approaches that provide safety guarantees by leveraging formal methods (Garcıa
and Fernández 2015; Baheri et al. 2020; Baheri 2022; Jaimungal et al. 2022;
Fulton and Platzer 2018; Könighofer et al. 2020). Within the scope of safe RL,
the refinement of policies stands as a crucial strategy, especially in safety-
critical applications. Policy refinement is an iterative process that focuses
on enhancing an agent’s policy to ensure it exhibits both safe and optimal
behavior while conforming to environmental constraints and task
specifications. It entails the evaluation of an agent’s present policy, the
identification of unsafe or suboptimal actions, and the subsequent update of
the policy to mitigate these deficiencies. Thus, policy refinement not only
ensures the safety of the RL system during both learning and deployment phases
but also continually improves its performance

Two techniques, counterexample-guided abstraction refinement (CEGAR) and
counterexample-guided inductive synthesis (CEGIS), have gained traction due to
their robust approach to system refinement. CEGAR, originally conceived for
the formal verification of finite-state systems, operates by iteratively
refining an abstract system model based on counterexamples unearthed during
verification (Clarke et al. 2000). While CEGAR hasn’t been widely used in RL,
its principles of abstract representation and iterative refinement through
counterexamples could be insightful for policy analysis and refinement in RL
(Jin et al. 2022). Similarly, CEGIS is a methodology centered on the synthesis
of a correct-by-construction program or policy satisfying a given
specification (Solar-Lezama et al. 2006). It starts with an initial candidate
policy or program, which is then refined based on counterexamples encountered
during the verification phase. CEGIS has shown its effectiveness in various
domains such as program synthesis (Solar-Lezama 2008; Alur et al. 2013) and
controller synthesis (Henzinger, Jhala, and Majumdar 2003; Ravanbakhsh and
Sankaranarayanan 2016).

Both CEGAR and CEGIS underscore the potential role of counterexamples in
refining a policy, opening up new avenues for exploration in RL. By
integrating the principles of these techniques with safe RL strategies, there
is potential to create a more efficient policy refinement process,
contributing to safer and more reliable learning-enabled systems for safety-
critical applications. These methodologies underscore the importance of
counterexample-based techniques in enhancing the safety and optimality of RL
policies and hint at the potential for further advancements in the field of
policy refinement.

This work aims to lay the foundation for _data-driven policy refinement_ in
reinforcement learning. Our primary goal is to bridge the gap between data-
driven verification and reinforcement learning, offering an iterative approach
that synergizes the strengths of both domains. In our proposed approach, we
propose a data-driven verification method that identifies unsafe trajectories
in the current policy. This verification stage acts as a performance check,
ensuring that the policy meets the necessary safety and optimality criteria.
However, rather than treating the verification stage as an endpoint, we
leverage the identified counterexamples as crucial learning opportunities. In
essence, the verification stage drives the learning process, providing direct,
actionable feedback on the policy’s performance. Following the data-driven
verification, we use a learning approach that specifically targets the
identified counterexamples. This learning stage takes the counterexamples as
input, treating them as problem areas that the policy needs to address.
Through learning from these counterexamples, the policy is refined
iteratively, gradually improving its safety and optimality.

This paper contributes to the field of RL theory, especially in the area of
policy refinement. We propose a mathematical formulation of data-driven policy
refinement. This approach intertwines the principles of data-driven
optimization with reinforcement learning. Through this formulation, we present
a methodology for iteratively refining an RL policy. This refinement is guided
by counterexamples identified through data-driven verification. Our approach
offers a systematic way to enhance the safety and optimality of reinforcement
learning policies, providing a robust framework that adapts and improves with
each iteration. In addition to introducing the concept of data-driven policy
refinement, we delve into the theoretical aspects that underpin this approach.
We present a series of theorems that elucidate the implications of data-driven
refinement. These theorems enhance our theoretical understanding of data-
driven policy refinement. They provide insights into the convergence,
generalization, and adaptability of the process, offering theoretical support
for our approach.

## Problem Formulation and Methodology

The ultimate objective of this work is to addresses the task of _refining_ an
optimized policy to ensure it fulfills a predefined safety specification. Our
setting comprises a policy parameter space, $\Theta$, which represents all
feasible policy parameters that define an agent’s behavior in a specific
environment. These policies are parameterized by a vector $\theta\in\Theta$.
The safety specification, $\varphi$, is a formal prescription of the agent’s
desired safety behavior. We quantify the satisfaction of the safety
specification by a robustness value function $g(\theta;{e})$, which measures
the extent to which the safety specification is satisfied for a given policy
parameter $\theta$ in a particular environment configuration ${e}$. We also
consider the set of possible environment configurations, $\mathcal{E}$, which
represent the different conditions the agent may encounter. Our proposed
methodology is an iterative process alternating between a data-driven
verification approach, using Bayesian optimization, and policy refinement
through inverse RL (IRL). The steps are as follows:

Data-Driven Verification via Bayesian Optimization. Bayesian optimization (BO)
is a powerful method for globally optimizing black-box functions that are
computationally expensive to evaluate. BO operates by constructing a
probabilistic model of the objective function and subsequently using this
model to identify promising points for evaluation (Snoek, Larochelle, and
Adams 2012). Owing to its effectiveness, BO has been employed in a wide array
of fields, including hyperparameter tuning in machine learning (Wu et al.
2019), design optimization in engineering (Garnett, Osborne, and Roberts
2010), and decision-making under uncertainty (Baheri et al. 2017).

Our process begins with an initial optimized policy $\theta_{1}\in\Theta$. The
objective of this phase is to identify environments ${e}^{*}(\theta_{i})$
where the policy, characterized by parameters $\theta_{i}$, infringes the
safety specification. To this end, we used BO to uncover the environment
configuration that minimizes the robustness value function
$g(\theta_{i};\mathbf{e})$ for each iteration $i=1,2,\dots$:

${e}^{*}(\theta_{i})=\underset{\mathbf{e}\in\mathcal{E}}{\mathrm{argmin}}\
g(\theta_{i};{e}).$ (1)

In each iteration of the BO process, we simulate the agent’s behavior in the
environment configuration $e$ that minimizes the robustness value function,
under the current policy parameters $\theta_{i}$. The agent’s behavior
generates a trajectory $\xi$ that represents the sequence of states and
actions taken by the agent in the environment configuration ${e}$. If the
trajectory $\xi$ violates the safety specification (i.e.,
$g(\theta_{i};{e})<0$), it is considered as a counterexample. The trajectory
$\xi$ provides specific instances where the policy with parameters
$\theta_{i}$ fails to meet the safety specification in the corresponding
environment configuration ${e}$. This counterexample then serves as the input
to the IRL process for policy refinement. In this way, the data-driven
verification step leverages the power of BO to systematically explore the
environment configuration space and identify counterexamples that challenge
the safety of the current policy.

Policy Refinement via Inverse RL. In this stage, we refine the policy by
updating the parameters $\theta_{i}$ based on the generated counterexamples
$e^{*}(\theta_{i})$ using IRL. The update yields a new policy parameterized by
$\theta_{i+1}$:

$\theta_{i+1}=\mathrm{IRL}(\theta_{i},{e}^{*}(\theta_{i}))\quad\text{for
}i=1,2,\dots.$ (2)

The goal of this IRL process is to refine the policy parameters $\theta$ such
that the updated policy $\pi(\theta)$ minimizes the likelihood of producing
unsafe trajectories. This is achieved by formulating an optimization problem
that minimizes the reward associated with unsafe trajectories and maximizes it
for safe ones:

$\theta_{i+1}=\underset{\theta\in\Theta}{\mathrm{argmin}}\
\mathbb{E}_{\pi(\theta)}[\mathcal{R}(\xi)]-\lambda\mathbb{E}_{\pi(\theta)}[\log(\pi(\theta))],$
(3)

where $\mathcal{R}(\xi)$ is the reward function assigning low rewards to
unsafe trajectories $\xi$ and high rewards to safe trajectories, $\pi(\theta)$
denotes the policy induced by parameter $\theta$, and $\lambda>0$ is a trade-
off parameter balancing between reward maximization and entropy maximization
for adequate exploration. The first term represents the expected reward of
trajectories $\xi$ when following the policy $\pi(\theta)$. The reward
function $\mathcal{R}(\xi)$ assigns low rewards to unsafe trajectories
(counterexamples) and high rewards to safe trajectories. Therefore, by
minimizing this term, the policy parameters $\theta$ are updated to discourage
unsafe behaviors that lead to low rewards. The second term is used to
encourage exploration of different actions. The entropy of a policy is a
measure of its randomness, so maximizing the entropy encourages the policy to
be more uncertain or random, which in turn encourages exploration of different
actions. The parameter $\lambda>0$ is a trade-off parameter that balances the
two objectives: minimizing the expected reward and maximizing the entropy.

The new policy parameters $\theta_{i+1}$ are then used in the next BO
iteration to find new counterexamples. The iterative process between BO and
IRL continues until a policy parameter $\theta^{*}\in\Theta$ is found such
that $g(\theta^{*})\geq 0$, indicating that the safety specification $\varphi$
is satisfied by the policy with parameters $\theta^{*}$. This iterative
process leverages the strengths of both BO and IRL: BO efficiently explores
the environment configuration space and identifies counterexamples, while IRL
learns a reward function that guides the policy towards avoiding unsafe
behaviors.

Once the iterative process terminates, it is essential to verify the refined
policy $\theta^{*}$ against the safety specification $\varphi$ using formal
verification techniques. This ensures that the refined policy indeed satisfies
the safety requirements in various environment configurations, providing a
higher level of confidence in the safety of the agent’s behavior. The overall
methodology is illustrated in Fig. 1.

Initial Optimized PolicyData-Driven Counterexample Generation (Bayesian
Optimization)Policy Refinement(Inverse Reinforcement
LearningCounterexamplesRefined Policy

Figure 1: The iterative process of data-driven verification and inverse RL.
The process begins with an optimized policy. A data-driven verification
approach is then used for counterexample generation, which serves as input for
policy refinement via inverse RL. The refined policy then feeds back into the
verification stage, creating a loop for continual policy improvement.

## Theoretical Results

In this section, we delve into the theoretical foundations that support our
proposed data-driven policy refinement approach. These foundations, laid out
in a series of theorems, provide rigorous mathematical evidence that validates
the principles and effectiveness of our methodology. Specifically, we explore
five key areas:

  1. 1.

The Convergence of Policy Refinement using Counterexamples Theorem, which
establishes that our iterative policy refinement process will indeed converge
to a policy that satisfies the safety specification.

  2. 2.

The Robustness Value Function Bounds Theorem, which provides bounds on the
robustness of the value function, thus quantifying the effectiveness of our
approach in maintaining safety constraints.

  3. 3.

The BO-IRL Generalization Error Bound Theorem, which gives us an upper limit
on the discrepancy between the learned policy’s performance and the optimal
policy’s performance, thus indicating how well our approach generalizes.

  4. 4.

The Convergence Rate Theorem, which quantifies the rate at which our iterative
refinement process converges to a safe policy.

  5. 5.

The Robustness of BO-IRL to Model Mismatch Theorem, which shows the resilience
of our approach to discrepancies between the estimated and true environment
models.

These theorems sheds light on crucial properties of our proposed approach,
strengthening the theoretical underpinnings of our work. In the following, we
will present a detailed discussion of each theorem, along with their proofs
and implications for our data-driven policy refinement approach

Theorem 1. (Convergence of Policy Refinement using Counterexamples) Given a
set of counterexamples $C$ generated by the BO process for falsifying the
learning-based policy, and assuming the IRL algorithm refines the policy using
these counterexamples, the refined policy $\pi^{\prime}(a|s;\theta^{\prime})$
will converge to a policy that satisfies the safety specification $\varphi$.

PROOF. We define a robustness value function $g(\theta)$ that measures the
robustness of a policy $\pi(a|s;\theta)$ with parameters $\theta$ with respect
to the safety specification $\varphi$. For example, $g(\theta)$ could be the
minimum robustness value $\rho_{\varphi}$ of the policy $\pi(a|s;\theta)$ over
the state-action space. At each iteration $k$, the IRL algorithm uses the
counterexamples $C_{k}$ to compute a better policy $\pi_{k}(a|s;\theta_{k})$.
Let
$J(\theta_{k})=\mathbb{E}[\sum_{t=0}^{T}r(s_{t},a_{t})|\pi_{k}(a|s;\theta_{k})]$
be the expected cumulative reward of the policy $\pi_{k}(a|s;\theta_{k})$, and
let $g_{k}(\theta_{k})$ be the robustness value function for the same policy.
The IRL algorithm aims to maximize the expected cumulative reward while
ensuring the robustness value function satisfies the safety specification:

$\theta_{k+1}=\underset{\theta}{\operatorname{argmax}}J(\theta)\text{ subject
to }g_{k}(\theta)\geq\rho_{\varphi}(\theta)$ (4)

As the IRL algorithm refines the policy using the counterexamples, the new
policy $\pi_{k+1}(a|s;\theta_{k+1})$ will have a higher robustness value
function $g_{k+1}(\theta_{k+1})$ compared to the previous policy
$\pi_{k}(a|s;\theta_{k})$:

$g_{k+1}\left(\theta_{k+1}\right)\geq g_{k}\left(\theta_{k}\right)$ (5)

To prove the convergence of the refined policy, we need to show that the
sequence of policies generated during each iteration monotonically improves
the robustness value function $g(\theta)$. From Eq. 5, we have:

$g_{k+1}\left(\theta_{k+1}\right)\geq g_{k}\left(\theta_{k}\right)\geq
g_{k-1}\left(\theta_{k-1}\right)\geq\cdots\geq g_{0}\left(\theta_{0}\right)$
(6)

Since $g(\theta)$ is non-decreasing with respect to the iteration index $k$,
it will have a limit point, say $g^{*}(\theta^{*})$. Using the limit point, we
can prove that the robustness value function converges, i.e., $g(\theta)$
approaches a maximum value as the number of iterations increases:

$\lim_{k\rightarrow\infty}g_{k}\left(\theta_{k}\right)=g^{*}\left(\theta^{*}\right)$
(7)

To establish convergence, we need to prove that the sequence of policies has a
converging subsequence, i.e., there exists a subsequence of policies
$\\{\pi_{k_{i}}(a|s;\theta_{k_{i}})\\}_{i=1}^{\infty}$ such that:

$\lim_{i\rightarrow\infty}\pi_{k_{i}}\left(a\mid
s;\theta_{k_{i}}\right)=\pi^{*}\left(a\mid s;\theta^{*}\right)$ (8)

Under certain conditions, such as compactness of the space of policy
parameters $\theta$ and continuity of the robustness value function
$g(\theta)$, we can establish that the sequence of policies converges to a
policy that satisfies the safety specification $\varphi$. Now we demonstrate
that the refinement process results in a policy with a bounded regret as the
number of iterations increases. The regret is defined as the difference
between the expected cumulative reward of the optimal safe policy and the
expected cumulative reward of the policy obtained by the algorithm. Let
$J^{*}(\theta^{*})$ be the expected cumulative reward of the optimal safe
policy, and let $J(\theta_{k})$ be the expected cumulative reward of the
policy at iteration $k$. The regret at iteration $k$ can be defined as:

$R_{k}=J^{*}\left(\theta^{*}\right)-J\left(\theta_{k}\right)$ (9)

To show that the regret is bounded, we need to demonstrate that there exists
an upper bound for $R_{k}$ as the number of iterations increases. We’ve
previously shown that the robustness value function $g(\theta)$ converges to a
maximum value as the number of iterations increases. Since the IRL algorithm
is designed to maximize the expected cumulative reward while ensuring the
robustness value function satisfies the safety specification, the difference
between the expected cumulative rewards of the optimal safe policy and the
policy at iteration $k$ should decrease as the robustness value function
converges to its maximum value. In other words, the convergence of the
robustness value function implies the convergence of the expected cumulative
rewards:
$\lim_{k\rightarrow\infty}J\left(\theta_{k}\right)=J^{*}\left(\theta^{*}\right)$.
This suggests that the regret $R_{k}$ approaches zero as the number of
iterations increases:

$\lim_{k\rightarrow\infty}R_{k}=J^{*}\left(\theta^{*}\right)-J\left(\theta_{k}\right)=0$
(10)

Since the regret $R_{k}$ converges to zero, it implies that there exists an
upper bound for the regret, and the regret is indeed bounded as the number of
iterations increases. This shows that the refined policy obtained by the
proposed refinement approach converges to a policy that not only satisfies the
safety specification but also has a bounded regret compared to the optimal
safe policy.

Theorem 2. (Bounds on Robustness). If the robustness value function
$g(\theta;e)$ is Lipschitz continuous with Lipschitz constant $L_{g}$, and
there exists a constant $C_{\text{IRL}}>0$ such that
$|\theta_{i+1}-\theta_{i}|\leq C_{\text{IRL}}$ for all $i=1,2,\dots$, then
after $n$ iterations of the process, the lower bound on the robustness value
function for the final policy $\theta^{*}$ is given by:

$g\left(\theta^{*};e\right)\geq
g\left(\theta_{1};e\right)-L_{g}C_{\mathrm{IRL}}(n-1)$ (11)

PROOF. By the Lipschitz continuity of the robustness value function
$g(\theta;e)$, we know that for any two policy parameters
$\theta,\theta^{\prime}\in\Theta$ and environment configuration
$e\in\mathcal{E}$, the following inequality holds:

$\left|g(\theta;e)-g\left(\theta^{\prime};e\right)\right|\leq
L_{g}\|\theta-\theta^{\prime}\mid$ (12)

In our iterative process, we are given that $|\theta_{i+1}-\theta_{i}|\leq
C_{\text{IRL}}$ for all $i=1,2,\dots$. Substituting this into the inequality
12, we get:

$\left|g\left(\theta_{i+1};e\right)-g\left(\theta_{i};e\right)\right|\leq
L_{g}\left\|\theta_{i+1}-\theta_{i}\right\|\leq L_{g}C_{\mathrm{IRL}}$ (13)

for all $i=1,2,\dots$. Since the policy is refined iteratively using IRL, we
have $g(\theta_{i+1};e)\geq g(\theta_{i};e)$ for all $i=1,2,\dots$. Therefore,

$g\left(\theta_{i+1};e\right)-g\left(\theta_{i};e\right)\geq-
L_{g}C_{\mathrm{IRL}}$ (14)

Now, we sum the inequalities from 14 for each iteration from $i=1$ to $i=n-1$

$\sum_{i=1}^{n-1}\left(g\left(\theta_{i+1};e\right)-g\left(\theta_{i};e\right)\right)\geq-
L_{g}C_{\mathrm{IRL}}(n-1)$ (15)

One can observe that the summation on the left-hand side forms a telescoping
series, which simplifies as

$g\left(\theta^{*};e\right)-g\left(\theta_{1};e\right)\geq-
L_{g}C_{\mathrm{IRL}}(n-1)$ (16)

Rearranging the inequality, we obtain the desired lower bound on the
robustness value function for the final policy $\theta^{*}$:

$g\left(\theta^{*};e\right)\geq
g\left(\theta_{1};e\right)-L_{g}C_{\mathrm{IRL}}(n-1)$ (17)

This completes the proof. $\blacksquare$

The theorem establishes a lower bound on the robustness value function for the
final refined policy $\theta^{*}$ after $n$ iterations of the process. The
bound depends on the initial policy’s robustness value, the Lipschitz constant
$L_{g}$ of the robustness value function, and the constant $C_{\text{IRL}}$
that captures the maximum change in the policy parameters during each
iteration. This result provides insights into how close the refined policy is
to fully satisfying the safety specification and whether it can be further
improved.

Theorem 3. (BO-IRL Generalization Error Bound). Given a dataset $\mathcal{D}$
consisting of $N$ i.i.d. samples, a confidence level $1-\delta$, and a BO-IRL
algorithm with $K$ iterations, the generalization error $\epsilon$ of the
policy obtained by the BO-IRL algorithm is bounded as follows with probability
at least $1-\delta$:

$\epsilon\leq
2K\operatorname{Rad}(\mathcal{D})+\sqrt{\frac{8K\log(1/\delta)}{N}}$

where $\operatorname{Rad}(\mathcal{D})$ is the Rademacher complexity of the
dataset.

PROOF. The generalization error $\epsilon$ is the difference between the
expected cumulative reward of the learned policy on the dataset $\mathcal{D}$
and the expected cumulative reward of the same policy on the true distribution
of the environment:

$\epsilon=\left|\mathbb{E}_{\mathcal{D}}[J(\theta)]-\mathbb{E}_{\text{true
}}[J(\theta)]\right|$ (18)

Now we define the empirical Rademacher averages for the dataset $\mathcal{D}$
as:

$\hat{\mathcal{R}}_{N}(\mathcal{D})=\mathbb{E}_{\sigma}\left[\sup_{\theta}\frac{1}{N}\sum_{i=1}^{N}\sigma_{i}J\left(\theta_{i}\right)\right]$
(19)

where $\sigma_{i}\in{-1,1}$ are independent Rademacher random variables, and
$\theta_{i}$ are the policy parameters associated with the $i$-th sample in
the dataset. The Rademacher complexity $\operatorname{Rad}(\mathcal{D})$ can
be computed as the expected value of the empirical Rademacher averages:
$\operatorname{Rad}(\mathcal{D})=\mathbb{E}_{\mathcal{D}}\left[\hat{\mathcal{R}}_{N}(\mathcal{D})\right]$.
For each iteration of the BO-IRL algorithm, we can apply the Rademacher
generalization bound. For any $\delta>0$, with probability at least
$1-\frac{\delta}{K}$:

$\epsilon_{k}\leq
2\operatorname{Rad}(\mathcal{D})+\sqrt{\frac{2\log(K/\delta)}{N}}$ (20)

where $\epsilon_{k}$ is the generalization error for the policy at iteration
$k$. The total generalization error after $K$ iterations can be obtained by
summing the individual generalization errors and applying the union bound

$\epsilon\leq\sum_{k=1}^{K}\epsilon_{k}\leq
2K\operatorname{Rad}(\mathcal{D})+\sqrt{\frac{8K\log(1/\delta)}{N}}$ (21)

with probability at least $1-\delta$. This concludes the proof of the BO-IRL
generalization error bound. $\blacksquare$

The theorem provides a bound on the performance of the refined policy on
unseen situations, taking into account the iterative nature of the BO-IRL
algorithm. The generalization error bound helps us understand the relationship
between the number of iterations, the amount of data, and the generalization
performance of the learned policy.

Theorem 4. (Convergence Rate). Under certain assumptions about the problem
setup, the exploration-exploitation trade-off in the BO process, the quality
of the counterexamples, and the policy improvement in the IRL, the combined
BO-IRL approach converges to a safe policy that satisfies the given safety
specification at a rate determined by the relationship between the policy
improvement metric $\Delta_{k}$ and the number of IRL iterations $k$.

PROOF [Sketch]. We assume that the problem setup, the exploration-exploitation
trade-off in the BO process, and the policy improvement in the IRL are such
that the policy improvement metric $\Delta_{k}$ decreases with the number of
IRL iterations $k$. This relationship can be represented as: $\Delta_{k}=f(k)$
where $f(k)$ is a monotonically decreasing function of $k$. Due to the
combined BO-IRL approach, the policy is iteratively improved using
counterexamples generated by the BO process and refined by the IRL. The policy
improvement can be quantified by the policy improvement metric $\Delta_{k}$,
which measures the difference between the expected cumulative rewards of two
consecutive policies:

$\Delta_{k}=J\left(\theta_{k+1}\right)-J\left(\theta_{k}\right)$ (22)

where $J(\theta_{k})$ and $J(\theta_{k+1})$ represent the expected cumulative
rewards of the policies at iterations $k$ and $k+1$, respectively. Since the
policy improvement metric $\Delta_{k}$ decreases with the number of IRL
iterations $k$, it implies that the policy is improving at each iteration. As
the number of iterations increases, the policy improvement metric $\Delta_{k}$
will approach zero, indicating that the expected cumulative rewards are no
longer significantly improving:

$\lim_{k\rightarrow\infty}\Delta_{k}=0$ (23)

The rate of convergence is determined by the relationship between the policy
improvement metric $\Delta_{k}$ and the number of IRL iterations $k$. In other
words, the speed at which the combined BO-IRL approach converges to a safe
policy that satisfies the given safety specification is governed by how fast
the function $f(k)$ decreases with increasing $k$. This proof sketch shows
that the convergence rate of the combined BO-IRL approach is determined by the
relationship between the policy improvement metric $\Delta_{k}$ and the number
of IRL iterations $k$.

Theorem 5. (Robustness of BO-IRL to Model Mismatch). Given any $\epsilon>0$,
if $|\mathcal{M}^{*}-\mathcal{M}|\leq\epsilon$, then for any policy
$\pi_{\theta}$, the difference in the expected reward under the true model
$\mathcal{M}^{*}$ and the estimated model $\mathcal{M}$, denoted as $\Delta
J(\pi_{\theta})$, is bounded by $\epsilon$.

PROOF. Let $\mathcal{M}^{*}$ denote the true environment model and
$\mathcal{M}$ the model used by the BO-IRL algorithm. We can define the model-
induced policy performance mismatch as:

$\Delta
J(\pi_{\theta})=|J(\pi_{\theta};\mathcal{M}^{*})-J(\pi_{\theta};\mathcal{M})|,$
(24)

where $J(\pi_{\theta};\mathcal{M})$ is the expected cumulative reward of
policy $\pi_{\theta}$ under model $\mathcal{M}$. Our goal is to show that
$\Delta J(\pi_{\theta})$ is bounded by $\epsilon$. We can express $\Delta
J(\pi_{\theta})$ as:

$\Delta
J(\pi_{\theta})=\left|\mathbb{E}_{\xi\sim\pi_{\theta},\mathcal{M}^{*}}[\mathcal{R}(\xi)]-\mathbb{E}_{\xi\sim\pi_{\theta},\mathcal{M}}[\mathcal{R}(\xi)]\right|,$
(25)

where $\mathcal{R}(\xi)$ represents the reward function. Now, we use the
assumption that $|\mathcal{M}^{*}-\mathcal{M}|\leq\epsilon$. Given this
assumption, the difference between the expected rewards under the true model
and the estimated model is also bounded by $\epsilon$. Hence, we have

$\Delta
J(\pi_{\theta})=\left|\mathbb{E}_{\xi\sim\pi_{\theta},\mathcal{M}^{*}}[\mathcal{R}(\xi)]-\mathbb{E}_{\xi\sim\pi_{\theta},\mathcal{M}}[\mathcal{R}(\xi)]\right|\leq\epsilon$
(26)

Therefore, the difference in the expected reward under the true model
$\mathcal{M}^{*}$ and the estimated model $\mathcal{M}$ for any policy
$\pi_{\theta}$ is bounded by $\epsilon$. $\blacksquare$

The theorem provides a guideline for the refinement process by bounding the
difference in expected rewards between the true and estimated models as
$\epsilon$. This ensures that even if a policy performs poorly in the
estimated model, its performance will improve in the true model through
refinement, as long as the model mismatch stays within the $\epsilon$ limit.
As a result, the refined policies become robust, as the theorem guarantees
that their deviation from expected outcomes in the true model will not exceed
$\epsilon$. This acts as a safeguard against overfitting to the estimated
model during the refinement stage.

## Conclusions and Future Directions

In this work, we propose an approach for policy refinement in reinforcement
learning, particularly for safety-critical applications. By uniquely blending
Bayesian optimization (BO) and inverse reinforcement learning (IRL), we have
developed a methodology that iteratively refines policies using
counterexamples derived from data-driven verification. Furthermore, we present
a series of theorems that provide a deeper understanding of the data-driven
policy refinement process, revealing key insights into its convergence, bounds
on robustness, generalizability, and convergence rate. This theoretical
foundation serves as a solid basis for our approach and contributes to the
broader RL theory. Future work could explore additional theoretical properties
and investigate more efficient algorithms for counterexample generation and
policy refinement. Moreover, applying our methodology to real-world problems
and evaluating its performance in practice are important avenues for future
research.

## References

  * Alur et al. (2013) Alur, R.; Bodik, R.; Juniwal, G.; Martin, M. M.; Raghothaman, M.; Seshia, S. A.; Singh, R.; Solar-Lezama, A.; Torlak, E.; and Udupa, A. 2013.  _Syntax-guided synthesis_.  IEEE.
  * Baheri (2022) Baheri, A. 2022.  Safe reinforcement learning with mixture density network, with application to autonomous driving.  _Results in Control and Optimization_ , 6: 100095.
  * Baheri et al. (2017) Baheri, A.; Bin-Karim, S.; Bafandeh, A.; and Vermillion, C. 2017.  Real-time control using Bayesian optimization: A case study in airborne wind energy systems.  _Control Engineering Practice_ , 69: 131–140.
  * Baheri et al. (2020) Baheri, A.; Nageshrao, S.; Tseng, H. E.; Kolmanovsky, I.; Girard, A.; and Filev, D. 2020.  Deep reinforcement learning with enhanced safety for autonomous highway driving.  In _2020 IEEE Intelligent Vehicles Symposium (IV)_ , 1550–1555. IEEE.
  * Clarke et al. (2000) Clarke, E.; Grumberg, O.; Jha, S.; Lu, Y.; and Veith, H. 2000.  Counterexample-guided abstraction refinement.  In _Computer Aided Verification: 12th International Conference, CAV 2000, Chicago, IL, USA, July 15-19, 2000. Proceedings 12_ , 154–169. Springer.
  * Dulac-Arnold, Mankowitz, and Hester (2019) Dulac-Arnold, G.; Mankowitz, D.; and Hester, T. 2019.  Challenges of real-world reinforcement learning.  _arXiv preprint arXiv:1904.12901_.
  * Fulton and Platzer (2018) Fulton, N.; and Platzer, A. 2018.  Safe reinforcement learning via formal methods: Toward safe control through proof and learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32.
  * Garcıa and Fernández (2015) Garcıa, J.; and Fernández, F. 2015.  A comprehensive survey on safe reinforcement learning.  _Journal of Machine Learning Research_ , 16(1): 1437–1480.
  * Garnett, Osborne, and Roberts (2010) Garnett, R.; Osborne, M. A.; and Roberts, S. J. 2010.  Bayesian optimization for sensor set selection.  In _Proceedings of the 9th ACM/IEEE international conference on information processing in sensor networks_ , 209–219.
  * Henzinger, Jhala, and Majumdar (2003) Henzinger, T. A.; Jhala, R.; and Majumdar, R. 2003.  Counterexample-guided control.  In _Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30–July 4, 2003 Proceedings_ , 886–902. Springer.
  * Jaimungal et al. (2022) Jaimungal, S.; Pesenti, S. M.; Wang, Y. S.; and Tatsat, H. 2022.  Robust risk-aware reinforcement learning.  _SIAM Journal on Financial Mathematics_ , 13(1): 213–226.
  * Jin et al. (2022) Jin, P.; Tian, J.; Zhi, D.; Wen, X.; and Zhang, M. 2022.  Trainify: a CEGAR-driven training and verification framework for safe deep reinforcement learning.  In _Computer Aided Verification: 34th International Conference, CAV 2022, Haifa, Israel, August 7–10, 2022, Proceedings, Part I_ , 193–218. Springer.
  * Kiran et al. (2021) Kiran, B. R.; Sobh, I.; Talpaert, V.; Mannion, P.; Al Sallab, A. A.; Yogamani, S.; and Pérez, P. 2021.  Deep reinforcement learning for autonomous driving: A survey.  _IEEE Transactions on Intelligent Transportation Systems_ , 23(6): 4909–4926.
  * Kober, Bagnell, and Peters (2013) Kober, J.; Bagnell, J. A.; and Peters, J. 2013.  Reinforcement learning in robotics: A survey.  _The International Journal of Robotics Research_ , 32(11): 1238–1274.
  * Könighofer et al. (2020) Könighofer, B.; Lorber, F.; Jansen, N.; and Bloem, R. 2020.  Shield synthesis for reinforcement learning.  In _Leveraging Applications of Formal Methods, Verification and Validation: Verification Principles: 9th International Symposium on Leveraging Applications of Formal Methods, ISoLA 2020, Rhodes, Greece, October 20–30, 2020, Proceedings, Part I 9_ , 290–306. Springer.
  * Ravanbakhsh and Sankaranarayanan (2016) Ravanbakhsh, H.; and Sankaranarayanan, S. 2016.  Robust controller synthesis of switched systems using counterexample guided framework.  In _Proceedings of the 13th International Conference on Embedded Software_ , 1–10.
  * Razzaghi et al. (2022) Razzaghi, P.; Tabrizian, A.; Guo, W.; Chen, S.; Taye, A.; Thompson, E.; Bregeon, A.; Baheri, A.; and Wei, P. 2022.  A Survey on Reinforcement Learning in Aviation Applications.  _arXiv preprint arXiv:2211.02147_.
  * Snoek, Larochelle, and Adams (2012) Snoek, J.; Larochelle, H.; and Adams, R. P. 2012.  Practical bayesian optimization of machine learning algorithms.  _Advances in neural information processing systems_ , 25.
  * Solar-Lezama (2008) Solar-Lezama, A. 2008.  _Program synthesis by sketching_.  University of California, Berkeley.
  * Solar-Lezama et al. (2006) Solar-Lezama, A.; Tancau, L.; Bodík, R.; Seshia, S. A.; and Saraswat, V. A. 2006.  Combinatorial sketching for finite programs.  In _Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2006, San Jose, CA, USA, October 21-25, 2006_ , 404–415.
  * Wu et al. (2019) Wu, J.; Chen, X.-Y.; Zhang, H.; Xiong, L.-D.; Lei, H.; and Deng, S.-H. 2019.  Hyperparameter optimization for machine learning models based on Bayesian optimization.  _Journal of Electronic Science and Technology_ , 17(1): 26–40.


# Characteristic (Fedosov-)class of a twist constructed by Drinfel’d

Jonas Schnitzer
Dipartimento di Matematica
Università degli Studi di Salerno
Via Giovanni Paolo II, 132
84084 Fisciano (SA)
Italy<EMAIL_ADDRESS>
###### Abstract

In a seminal paper Drinfel’d explained how to associate to every classical
r-matrix for a Lie algebra $\mathfrak{g}$ a twisting element based on
$\mathcal{U}(\mathfrak{g})[[\hbar]]$, or equivalently a left invariant star
product of the corresponding symplectic structure $\omega$ on the 1-connected
Lie group G of g. In a recent paper, the authors solve the same problem by
means of Fedosov quantization. In this short note we provide a connection
between the two constructions by computing the characteristic (Fedosov) class
of the twist constructed by Drinfel’d and proving that it is the trivial class
given by $\frac{[\omega]}{\hbar}$.

## Introduction

The notion of Drinfel’d twists goes back to the 80’s in the context of
_Quantum Groups_ , see e.g. the textbooks [7], [15] and [3]. It is still an
active field of research, since it is a powerful (functorial) tool used in
Quantum field theory to quantize classical field theories, see e.g. [18], and
references therein. This application is due to the fact that a Drinfel’d twist
together with a suitable Hopf algebra action always induces a deformation
quantization. To be more precise, if a Lie algebra $\mathfrak{g}$ acts on an
associative $\mathscr{A}$ by derivations via
$\phi\colon\mathfrak{g}\to\mathscr{A}$, then a _formal Drinfel’d twist_
$\mathcal{F}\in\mathcal{U}(\mathfrak{g})\mathbin{\otimes}\mathcal{U}(\mathfrak{g})[[\hbar]]$
induces a deformation of the associative product
$\mu\colon\mathscr{A}\times\mathscr{A}\to\mathscr{A}$ by

$\displaystyle
a\star_{\mathcal{F}}b=\mu(\Phi\mathbin{\otimes}\Phi(F)(a\mathbin{\otimes}b))$

for $a,b\in\mathscr{A}[[\hbar]]$ and the extended action
$\Phi\colon\mathcal{U}(\mathfrak{g})\to\operatorname{\mathrm{DiffOp}}(\mathcal{A})$.
The properties of the twist (see Definition 1) ensure that this product is
associative again and that it is a formal deformation in the sense of
Gerstenhaber [9].

The existence of a Drinfel’d twist was first shown by Drinfel’d himself in [6]
using the fact that a Drinfel’d twist is equivalent to a left-invariant star
product and the construction of the canonical star product on the dual of a
Lie algebra, which is nowadays called Gutt-star product, since in [12] it is
given a construction of it. There are just very few explicit examples known,
see e.g. [10], besides the _Weyl-Moyal twist_ , even though they are
completely classified via there infinitesimal counter parts, the $r$-matrices,
in [14] via Formality. This approach even provides a full classifiaction of
Drinfel’d twists in terms of their infintesimal counterparts, the so-called
_r-matrices_. Recall that two twists
$\mathcal{F},\mathcal{F}^{\prime}\in\mathcal{U}(\mathfrak{g})\mathbin{\otimes}\mathcal{U}(\mathfrak{g})[[\hbar]]$
are said to be equivalent, if there exists a
$S\in\mathcal{U}(\mathfrak{g})[[\hbar]]$ with
$S=\operatorname{\mathsf{id}}+\mathcal{O}(\hbar)$ and $\varepsilon(S)=1$, such
that

$\displaystyle\mathcal{F}^{\prime}=\Delta(S)^{-1}\cdot\mathcal{F}\cdot(S\mathbin{\otimes}S),$

which induces an equivalence, i.e. an ismorphism
$\Phi(S)\in\operatorname{\mathrm{DiffOp}}(\mathscr{A})$, of the induced
deformations $\star_{\mathcal{F}}$ and $\star_{\mathcal{F}^{\prime}}$ (see [2]
for more details). In [2], a construction of Drinfel’d twists and their
classification is provided with the help of a modified Fedosov-construction,
see [8], for symplectic Lie algebras. In fact, if the given Lie algebra is
real the construction in [2] can be seen as the original Fedosov-construction
on a Lie group with a left-invariant connection. Additionally, the (invariant)
classification result boils down to the one obtained in [1], where it is shown
that the equivalence classes of left-invariant star products is isomorphic to

$\displaystyle\frac{[\omega]}{\hbar}+H^{2}_{\text{dR}}(G)^{G}[[\hbar]],$

where the reference point $\omega$ is the left-invariant symplectic structure
of the Lie group and is just convention. Moreover, $H_{\text{dR}}(G)^{G}$ is
the cohomology of the left-invariant differential forms. The purpose of this
note is now straight forward: computing the characteristic class in the sense
of [2] of the Drinfel’d twist obtained in [6]. To do so we proceed as follows:
First, we recall the original construction of Drinfel’d and of the Gutt-star
product and use the equivalence of Drinfel’d twists and left-invariant star
products to obtain the chain of equivalences:

$\displaystyle\text{ Drinfel'd's Twist }\sim\text{ invariant Kontsevich star
product }\sim\text{ invariant Fedosov star product },$

where the first equivalence is provided in [4] and the second equivalence is
proven in [13]. As a corollary we can compute the characteristic class of the
Drinfel’d twist constructed by Drinfel’d in terms of the invariant Fedosov
class of the left-invariant star product it induces. This is by construction
in [2] the class of the twist inducing it.

We are assuming the reader is familiar with the notion of star products and
their different classifications due to [17] for Poisson manifolds and [8] for
symplectic manifolds, as well as the invariant counterparts [5] and [1].

##  1 The Drinfel’d twist construction and the Gutt star product

Drinfel’d twists can be defined on arbitrary Hopf algebras (in fact even just
bialgebras) (see e.g. [11]), but throughout this note we use the following

######  Definition 1.1.

Let $\mathfrak{g}$ be a Lie algebra. A (formal) Drinfel’d twist is an element
$\mathcal{F}\in\mathcal{U}(\mathfrak{g})\mathbin{\otimes}\mathcal{U}(\mathfrak{g})[[\hbar]]$,
such that

  1. i.)

$(\Delta\mathbin{\otimes}\operatorname{\mathsf{id}})(\mathcal{F})\cdot(\mathcal{F}\mathbin{\otimes}1)=(\operatorname{\mathsf{id}}\mathbin{\otimes}\Delta)(\mathcal{F})\cdot(1\mathbin{\otimes}\mathcal{F})$

  2. ii.)

$(\varepsilon\mathbin{\otimes}\operatorname{\mathsf{id}})(F)=(\operatorname{\mathsf{id}}\mathbin{\otimes}\varepsilon)(\mathcal{F})=1$

  3. iii.)

$\mathcal{F}=1\mathbin{\otimes}1+\mathcal{O}(\hbar^{2})$

for the usual Hopf algebra structures
$(\mathcal{U}(\mathfrak{g}),\cdot,i,\Delta,\varepsilon,S)$

A Drinfel’d twist has a classical limit, which can be seen as the equivalent
to Poisson structures in deformation quantization.

######  Lemma 1.2.

Let $\mathfrak{g}$ be a Lie algebra and let
$\mathcal{F}\in\mathcal{U}(\mathfrak{g})\mathbin{\otimes}\mathcal{U}(\mathfrak{g})[[\hbar]]$
be a Drinfel’d twist, then

$\displaystyle
r:=F_{1}-F_{1}^{\mathrm{opp}}\in\Lambda^{2}\mathfrak{g}\subseteq\mathcal{U}(\mathfrak{g})\mathbin{\otimes}\mathcal{U}(\mathfrak{g})$

is a $r$-matrix, i.e. $[\\![r,r]\\!]=0$.

Let us now state the theorem of Drinfel’d connecting $r$-matrices with
Drinfel’d twists.

######  Theorem 1.3 (Drinfel’d [6]).

Let $\mathfrak{g}$ be a real finite dimensional Lie algebra and let $r$ be a
$r$-matrix. Then there exists a Drinfel’d twist
$\mathcal{F}\in\mathcal{U}(\mathfrak{g})\mathbin{\otimes}\mathcal{U}(\mathfrak{g})[[\hbar]]$,
such that

$\displaystyle r=F_{1}-F_{1}^{\mathrm{opp}}.$

Note that Drinfel’d twists have a deep connection to deformation quantization,
i.e. they induce a deformation quantization on any algebra the underlying Lie
algebra acts on.

######  Theorem 1.4.

Let $\mathfrak{g}$ be a Lie algebra acting as derivations on an algebra
$\mathscr{A}$ by
$\phi\colon\mathfrak{g}\to\operatorname{\mathsf{Der}}(\mathscr{A})$ and let
$\mathcal{F}\in\mathcal{U}(\mathfrak{g})\mathbin{\otimes}\mathcal{U}(\mathfrak{g})[[\hbar]]$
be a Drinfel’d twist. Then the extended action induced by $\phi$

${\mathcal{U}(\mathfrak{g})}$${\operatorname{\mathrm{DiffOp}}(\mathcal{A})}$$\scriptstyle{\Phi}$

induces a formal deformation of the product of $\mathscr{A}$ by

$\displaystyle
a\star_{\mathcal{F}}b:=\mu_{\mathscr{A}}(\Phi\mathbin{\otimes}\Phi(\mathcal{F})(a\mathbin{\otimes}b))$

for $a,b\in\mathscr{A}[[\hbar]]$.

From now on, we focus on real Lie algebras where we can use the following

######  Corollary 1.5.

Let $\mathfrak{g}$ be a real Lie algebra, let $G$ be a Lie group with
$\mathsf{Lie}(G)=\mathfrak{g}$, then the following are equivalent:

  1. i.)

a Drinfel’d twist
$\mathcal{F}\in\mathcal{U}(\mathfrak{g})\mathbin{\otimes}\mathcal{U}(\mathfrak{g})[[\hbar]]$
with corresponding $r$-matrix $r$

  2. ii.)

a left invariant star product
$\star\colon\mathscr{C}^{\infty}(G)[[\hbar]]^{\mathbin{\otimes}2}\to\mathscr{C}^{\infty}(G)[[\hbar]]$
with left-invariant Poisson structure $\pi\in\Gamma^{\infty}(\Lambda^{2}TG)$,
such that $\pi(e)=r$.

Moreover, two Drinfel’d twists are equivalent if and only if the left-
invariant star products induced by them are invariantly equivalent.

This allows us to forget about twists for the moment and take care about left-
invariant star products on Lie groups and their equivalences. In the following
we recall the construction of Drinfel’d [6], which is based on the fact that
there is a canonical star product on the dual of a Lie algebra from [12],
which we in return also recall briefly. Let therefore $(\mathfrak{g},[-,-])$
be a finite dimensional real Lie algebra, then there is a star product on
$\mathfrak{g}^{*}$ induced by the Poincaré-Birkoff-Witt isomorphism

$\displaystyle
P_{\hbar}\colon\mathrm{S}^{\bullet}\mathfrak{g}[[\hbar]]\to\mathcal{U}_{\hbar}(\mathfrak{g}),$

where

$\displaystyle\mathcal{U}_{\hbar}(\mathfrak{g})=\frac{T^{\bullet}(\mathfrak{g})[[\hbar]]}{\langle
x\mathbin{\otimes}y-y\mathbin{\otimes}x-\hbar[x,y]\rangle}.$

and the Poincaré-Birkoff-Witt isomorphism is given by

$\displaystyle P_{\hbar}(X_{1}\vee\dots\vee X_{k})=\frac{1}{k!}\sum_{\sigma\in
S_{k}}X_{\sigma(1)}\bullet_{\hbar}\dots\bullet_{\hbar}X_{\sigma(k)}.$

Here $\bullet_{\hbar}$ denotes the associative product in
$\mathcal{U}_{\hbar}(\mathfrak{g})$. We interpret
$\mathrm{S}^{\bullet}\mathfrak{g}$ as the polynomials on $\mathfrak{g}^{*}$
and define a product

$\displaystyle
f\star_{G}g=P_{\hbar}^{-1}(P_{\hbar}(f)\bullet_{\hbar}P_{\hbar}(g)).$

It is easy to see that since the product is defined by differential operators,
it can be extended to $\mathscr{C}^{\infty}(\mathfrak{g}^{*})$ and that this
product is $\operatorname{\mathrm{Ad}}$-invariant with respect to the
1-connected Lie group $G$ integrating $\mathfrak{g}$. We refer to this star
product as the _Gutt-star product_. Note that the semi-classical limit of this
star product is the canonical (linear) Poisson structure on the dual of the
Lie algebra.

Let us now assume symplectic Lie algebra $(\mathfrak{g},[-,-],\omega)$, i.e. a
Lie algebra $(\mathfrak{g},[-,-])$ together with a non- degenerate 2-form
$\omega\in\Lambda^{2}\mathfrak{g}^{*}$, such that
$\delta_{\text{\tiny{CE}}}\omega=0$. We consider the central extension adapted
to $\omega$ which is given by

$\displaystyle\mathfrak{h}=\mathfrak{g}\oplus\mathbb{R}\text{ with
}[(X,x),(Y,y)]_{\mathfrak{h}}=([X,Y],-\omega(X,Y))$

and the canonical projection $p\colon\mathfrak{h}\to\mathfrak{g}$, which is a
lie algebra map.

A short computation shows that that the Jacobi identity of
$[-,-]_{\mathfrak{h}}$ is equivalent to $\delta_{\text{\tiny{CE}}}\omega=0$.
Note that in $\mathfrak{h}^{*}$, we have the distinguished element

$\displaystyle C\colon\mathfrak{h}\ni(X,x)\to x\in\mathbb{R},$

where we one can show that $\delta_{\text{\tiny{CE}}}C=-p^{*}\omega$. Note
that $(\mathfrak{h},C)$ is a contact Lie algebra and is the _contactification_
of the symplectic Lie algebra $(\mathfrak{g},\omega)$, see [16]. Let us prove
the following

######  Lemma 1.6.

Let $G$ be a Lie group with Lie algebra $\mathfrak{g}$. Then

$\displaystyle\dim(\operatorname{\mathrm{Ad}}_{G}^{*}(\alpha))=\operatorname{\mathrm{rank}}(\delta_{\text{\tiny{CE}}}\alpha^{\sharp}).$

######  Proof:

It is enough to prove that the tangent space of the coadjoint orbit at
$\alpha$ has dimension
$\operatorname{\mathrm{rank}}(\delta_{\text{\tiny{CE}}}\alpha^{\sharp})$. But
since it is an orbit of a Lie group action it is spanned by the fundamental
vector fields. But they are given by

$\displaystyle
X_{\mathfrak{g}}(\alpha)=\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}t}\Big{|}_{t=0}\operatorname{\mathrm{Ad}}^{*}_{\exp(tX)}\alpha=\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}t}\Big{|}_{t=0}\exp(t\operatorname{\mathrm{ad}}^{*}_{X})\alpha.$

which is $0$ if and only if $\operatorname{\mathrm{ad}}_{X}^{*}\alpha=0$.
Moreover, we can write
$\operatorname{\mathrm{ad}}_{X}^{*}\alpha=-\delta_{\text{\tiny{CE}}}\alpha^{\sharp}(X)$
and the claim is proven. $\Box$

We have additionally a Lie algebra action of $\mathfrak{g}$ on
$\mathfrak{h}^{*}$ by

$\displaystyle\mathbin{\triangleright}\colon\mathfrak{g}\ni
X\to(X,0)_{\mathfrak{h}^{*}}\in\Gamma^{\infty}(T\mathfrak{h}^{*})$

where $(X,0)_{\mathfrak{h}^{*}}$ is the fundamental vector field of the
coadjoint representation of $H$ (the 1-connected Lie group integrating
$\mathfrak{h}$). It is easy to check that

$\displaystyle[X,Y]\mathbin{\triangleright}=-[X\mathbin{\triangleright},Y\mathbin{\triangleright}]$

and hence it is in fact a Lie algebra action. Moreover its fundamental vector
fields have complete flow and hence this Lie algebra action lifts to a left
Lie group action $\Phi\colon G\times\mathfrak{h}^{*}\to\mathfrak{h}^{*}$ of
$G$ on $\mathfrak{h}^{*}$ by the Theorem of Palais. Note that, we can lift
every map in order to obtain the following commutative diagram

${H}$${\mathrm{Gl}(\mathfrak{h}^{*})}$${G}$$\scriptstyle{\operatorname{\mathrm{Ad}}^{*}}$$\scriptstyle{\Phi}$

which is just the integration of the diagram

${\mathfrak{h}}$${\operatorname{\mathsf{End}}(\mathfrak{h}^{*})}$${\mathfrak{g}}$$\scriptstyle{\operatorname{\mathrm{ad}}^{*}}$$\scriptstyle{p}$

.

######  Lemma 1.7.

The orbit $\Phi_{G}(C)$ for the previously defined $C\in\mathfrak{h}^{*}$ has
dimension $\dim(\Phi_{G}(C))=\dim(\mathfrak{g})$.

######  Proof:

Using Lemma 1.6 and the fact that $\delta_{\text{\tiny{CE}}}C=-p^{*}\omega$
and that $\omega$ is symplectic, we conclude that the coadjoint orbit through
$C$ has dimension $\dim(\mathfrak{g})$. By the diagram 1, we get hence the
claim. $\Box$

######  Remark 1.8.

The previous Lemma shows that $\Phi_{C}\colon G\ni
g\mapsto\Phi_{g}(C)\in\Phi_{G}(C)$ is a local diffeomorphism. Moreover, we
have that $\Phi_{C}\circ\ell_{g}=\Phi_{g}\circ\Phi_{C}$. Using the fact that
$\Phi_{G}(C)$ is a coadjoint orbit of the group $H$, we know that it is a
symplectic leaf of its canonical Poisson structure with invariant symplectic
structure $\Theta\in\Gamma^{\infty}(\Lambda^{2}T^{*}\Phi_{G}(C))$ and hence
$\Phi_{C}^{*}\Theta$ is a left-invariant symplectic structure on $G$. A tiny
computation shows that $\Phi_{C}^{*}\Theta(e)=\omega$ and hence
$\Phi_{C}^{*}\Omega$ is the left translated 2-form obtained by $\omega$. Let
us denote from now on $\Pi$ the Poisson structure induced by
$\Phi_{C}^{*}\Theta$.

Let us now apply these considerations to the construction of the Gutt-star
product. First of all we have

######  Proposition 1.9.

The Gutt-star product is invariant with respect to the action $\Phi\colon
G\times\mathfrak{h}^{*}\to\mathfrak{h}^{*}$.

Moreover, we have

######  Lemma 1.10.

The Gutt-star product of $\mathfrak{h}$ is tangential to $\Phi_{G}(C)$.

######  Proof:

We have to check that for functions
$f,g\in\mathscr{C}^{\infty}(\mathfrak{h}^{*})$, such that
$f\big{|}_{\Phi_{G}(C)}=0$ we have $f\star_{G}g\big{|}_{\Phi_{G}(C)}=0$. But
we actually show a bit more: we want to show that the Gutt-star product is
tangential to the submanifold

$\displaystyle D=\\{\alpha\in\mathfrak{h}^{*}\ |\
\alpha((0,1))-1=0\\}\supseteq_{\mathrm{open}}\Phi_{G}(C),$

where the inclusion of $\Phi_{G}(C)$ in $D$ follows from the fact that
$\operatorname{\mathrm{Ad}}_{h}^{*}C(0,1)=C(\operatorname{\mathrm{Ad}}_{h}(0,1))=C(0,1)=1$
and the fact that it is open follows from dimensional reasons (see Lemma 1.7).
Note that this is the zero set of the polynomial
$p=(0,1)-1\in\mathfrak{h}\oplus\mathbb{R}\in\mathrm{S}^{\bullet}\mathfrak{h}$
and hence every function $f\in\mathscr{C}^{\infty}(\mathfrak{h}^{*})$
vanishing on $D$ is given by $f=\tilde{f}p$. Moreover, by the definition of
the Gutt-star product we have that

$\displaystyle Y\star_{G}f=Y\cdot f$

for a central element $Y\in Z(\mathfrak{h}^{*})$ seen as a polynomial. Hence,
we have

$\displaystyle(pf)\star_{G}g=((0,1)f)\star_{G}g-f\star_{G}g=p(f\star_{G}g)$

and hence $(pf)\star_{G}g\big{|}_{D}=0$, since $(0,1)$ is central. And the
claim follows. $\Box$

##  2 Kontsevich star product on $\mathfrak{h}^{*}$

The dual of the Lie algebra $\mathfrak{h}^{*}$ can be alternatively seen as a
Poisson manifold and apply the the Kontsevich map to obtain a star product.
More, precisely we apply the Kontsevich map to $\hbar\pi$, seen as a Maurer-
Cartan element, which is invariant with respect to the adjoint representation
of $H$ to obtain a $H$-invariant star product $\star_{K}$. In [4] it was shown
that the two star product are invariantly equivalent, i.e. there is a series
of invariant differential operators
$S=\operatorname{\mathsf{id}}+\mathcal{O}(\hbar)\in\operatorname{\mathrm{DiffOp}}(\mathfrak{h}^{*})^{H}$,
such that

$\displaystyle S(f\star_{G}h)=(Sf)\star_{K}(Sh),$

which basically follows by the universal property of the universal enveloping
algebra. Moreover, we have

######  Lemma 2.1.

The Kontsevich star product obtained on the dual Lie algebra
$\mathfrak{h}^{*}$ is tangential to $\Phi_{G}(C)$ and so is $S$.

######  Proof:

The proof of both statements works exactly the same. It is based on the
following observation: we can choose coordinates $\\{x_{1},\dots,x_{n},u\\}$,
where $\\{x_{i}\\}$ are coordinates in $\mathfrak{g}^{*}$ and $u$ is the
remaining coordinate, when we identify
$\mathfrak{h}^{*}=\mathfrak{g}^{*}\oplus\mathbb{R}$. In this coordinates we
have that the canonical Poisson structure $\pi$ is given by

$\displaystyle\pi=\frac{1}{2}x_{k}\cdot C^{k}_{ij}\frac{\partial}{\partial
x_{i}}\wedge\frac{\partial}{\partial
x_{j}}-\frac{1}{2}u\cdot\omega_{ij}\frac{\partial}{\partial
x_{i}}\wedge\frac{\partial}{\partial x_{j}},$

where $C^{k}_{ij}$ are the structure constants of $\mathfrak{g}$ and
$\omega_{ij}$ are the components of the symplectic form $\omega$. Moreover we
have for the hyperplane $D=\\{u=1\\}$. A tangential differential operator has
to be of the form

$\displaystyle\mathfrak{D}=\sum_{(I,k)}D_{(I,k)}(x,u)\frac{\partial^{|I|}}{\partial
x^{I}}\bigg{(}\frac{\partial}{\partial u}\bigg{)}^{k}$

such that $D_{(I,k)}(x,1)=0$ if $k\neq 0$. It is easy to see that for our
specific bivector field $\pi$ the Bidifferential operators $B_{k}(\pi)$
constructed from Kontsevich’s formality map do not contain any derivatives in
$u$-direction, since the Poisson bivector does not possess any and hence they
are canonically tangential. Let us now turn towards the equivalence $S$, due
to [4, Thm 3] this eqivalence is build up out of differential operators of the
form (adapted to our coordinates)

$\displaystyle
D_{r}=\sum_{i_{1},\dots,i_{r}=1}^{\dim\mathfrak{g}+1}\mathrm{Tr}(\operatorname{\mathrm{ad}}_{e_{i_{1}}}\dots\operatorname{\mathrm{ad}}_{e_{i_{r}}})\frac{\partial}{\partial
y_{i_{1}}}\cdots\frac{\partial}{\partial y_{i_{r}}}$

where $y_{i}=x_{i}$ for $1\leq i\leq\dim\mathfrak{g}$ and
$y_{\dim\mathfrak{g}+1}=u$. and and the $e_{i}$’s are the corresponding basis
vectors in $\mathfrak{h}^{*}$. Note that
$\operatorname{\mathrm{ad}}_{e_{\dim\mathfrak{g}+1}}=0$ and hence also in
these differential operators no derivatives in the direction of $u$ appear.
This concludes the proof. $\Box$

If a star product is tangential to a submanifold it can be shrinked to it and
one can obtain again a star product on it. But we have moreover that in our
case:

######  Corollary 2.2.

The star product obtained by shrinking the Kontsevich star product to
$\Phi_{G}(C)$ is the same as the Kontsevich star product constructed by the
shrinked Poisson bivector $\pi\big{|}_{\Phi_{G}(C)}$ directly on
$\Phi_{G}(C)$.

Since the Gutt-star product, the Kontsevich-star product and the equivalence
bewtween them are invariant under the action of $G$, we can pull the back via
the local diffeomorphism in order to obtain two left-invariant star products
on $G$ and a left- invariant equivalence between them.

Moreover, one can show that pull-back of the Kontsevich star product is
oobtained by Dolgushev globalization of the Kontsevich formality with taking
pull-back the canonical flat connection on $\mathfrak{h}^{*}$ shrinked to $D$,
which is invariant under the group action of $H$, since it acts by linear
transformations. Moreover, since everything is left-invariant we see that the
invariant Kontsevich class of the Kontsevich star product, and hence the
Gutt–star product, is $[\hbar\Pi]_{G}$. The aim is now to compute the
invariant Fedosov class of this star product, which is an element in
$\frac{[\Phi_{C}^{*}\Theta]}{\hbar}+H_{dR}^{2}(G)^{G}[[\hbar]]=\frac{[\omega]}{\hbar}+H_{\mathrm{CE}}^{2}(\mathfrak{g})[[\hbar]]$,
where we identify the left-invariant de Rham cohomology with the Chevalley-
Eilenberg cohomology and the fact that the invariant symplectic structure
$\Phi_{C}^{*}\Theta$ is just $\omega$ under this identification by Remark 1.

##  3 The Fedosov-class of the Drinfel’d twist

A Drinfel’d Twist obtained by a symplectic structure
$\omega\in\Lambda^{2}\mathfrak{g}^{*}$ is a left-invariant star product on a
Lie group integrating the Lie algebra $\mathfrak{g}$. The original Drinfel’d
construction of a twist, is basically described above: the Drinfel’d twist is
the "pulled-back" Gutt-star product. In [2] it is shown that it is possible to
modify the Fedosov-construction in order to get a full classification of
symplectic Drinfel’d twists and the moduli space of symplectic Drinfel’d
twists with $r$-matrix $r=\omega^{-1}$ is given by

$\displaystyle\frac{[\omega]}{\hbar}+H_{CE}^{2}(\mathfrak{g})[[\hbar]].$

Moreover, it is easy to see that the left invariant star product $\star$
induced by a twist $\mathcal{F}$ from Corollary 1 of characteristic class
$\frac{[\omega]}{\hbar}+\Omega$ has invariant characteristic class
$I(\frac{[\omega]}{\hbar}+\Omega)$, where
$I\colon\Lambda^{\bullet}\mathfrak{g}^{*}\to\Gamma^{\infty}(\Lambda^{\bullet}T^{*}G)^{G}$
is the canonical isomorphism of the Chevalley-Eilenberg complex to the left-
invaraint de Rham complex.

######  Theorem 3.1.

Let $(\mathfrak{g},\omega)$ be a symplectic Lie algebra and let $\mathcal{F}$
be the Drinfel’d twist constructed above. Then its characteristic class is
$\frac{[\omega]}{\hbar}$.

######  Proof:

From the discussion in Section 2, we know that the invariant Kontsevich class
of the of the star product induced by Drinfel’d’s twist is given by
$[\hbar\Pi]_{G}$. To compute its invariant Fedosov class, we observe that in
[13], the authors construct an explicit equivalence between the Kontsevich-
star product obtained by the globalization procedure from [5] and a Poisson
structure $\pi$ and the Fedosov star product obtained by the original Fedosov
construction [8] with the symplectic structure $\pi^{-1}$. If additionally a
Lie group $G$ acts on the manifold acts on the manifold, it can be shown that
this equivalence can be choosen to be $G$-invariant, if one can find a
invariant connection, which is a straightforward computation. Note that a Lie
group acts always properly from the left on itself and hence it is possible to
find an invariant connection, and with the above discussion, it is clear that
the Fedosov star product constructed from $\Pi^{-1}$ is equivalent to the
Drinfel’d twist. By the definition of the (invariant) Fedosov classes, the
class of the Fedosov star product constructed by $\Pi^{-1}$ has Fedosov class
$\frac{[\omega]}{\hbar}$ and so has hence the Drinfel’d twist. $\Box$

## References

  * [1] M. Bertelson, P. Bieliavsky, and S. Gutt.  Parametrizing Equivalence Classes of Invariant Star Products.  Lett. Math. Phys., 46(4):339–345, 1998.
  * [2] S. Waldmann C. Esposito, J. Schnitzer.  A universal construction of universal deformation formulas, Drinfeld twists and their positivity.  Pacific J. Math., 291(2):319–358, 2017.
  * [3] V. Chari and A.N. Pressley.  A Guide to Quantum Groups.  Cambridge University Press, 1995.
  * [4] G. Dito.  Kontsevich Star Product on the Dual of a Lie Algebra.  Lett. Math. Phys., 48(4):307–322, 1999.
  * [5] V. Dolgushev.  Covariant and equivariant formality theorems.  Advances in Mathematics, 191(1):147 – 177, 2005.
  * [6] V.G. Drinfel’d.  On constant quasiclassical solutions of the Yang–Baxter quantum equation.  Sov. Math. Dokl., 28:667–671, 1983.
  * [7] P.I. Etingof and O. Schiffmann.  Lectures on quantum groups.  Lectures in Mathematical Physics. International Press, 2002.
  * [8] B. V. Fedosov.  A simple geometrical construction of deformation quantization.  J. Differential Geom., 40(2):213–238, 1994.
  * [9] M. Gerstenhaber.  On the Deformation of Rings and Algebras.  Ann. Math., 79(1):59–103, 1964.
  * [10] A. Giaquinto and J. Zhang.  Bialgebra actions, twists, and universal deformation formulas.  Journal of Pure and Applied Algebra, 128(2):133 – 151, 1998.
  * [11] A. Giaquinto and J. J. Zhang.  Bialgebra actions, twists, and universal deformation formulas.  J. Pure Appl. Algebra, 128:133–151, 1998.
  * [12] S. Gutt.  An Explicit -Product on the Cotangent Bundle of a Lie Group.  Lett. Math. Phys., 7:249–258, 1983.
  * [13] S. Waldmann H. Bursztyn, V. Dolgushev.  Morita equivalence and characteristic classes of star products.  J. reine angew. Math., 662:95–163, 2012.
  * [14] G. Halbout.  Formality theorem for Lie Bialgebras and quantization of twists and coboundary r-matrices .  Advances in Mathematics, 207(2):617 – 633, 2006.
  * [15] C. Kassel.  Quantum Groups.  Springer New York, 1994.
  * [16] Y. Khakimdjanov, M. Goze, and A. Medina.  Symplectic or contact structures on Lie groups.  Diff. Geom. Appl., 21(1):41 – 54, 2004.
  * [17] M. Kontsevich.  Deformation Quantization of Poisson Manifolds.  Letters in Mathematical Physics, 66:157–216, 2003.
  * [18] A. Schenkel P. Aschieri.  Noncommutative connections on bimodules and Drinfeld twist deformation.  Adv. Theo. Math. Phys., 18(3):513–612, 2014.


# Optimized Implementation of Neuromorphic HATS Algorithm on FPGA

Khushal Sethi, Manan Suri

###### Abstract

In this paper, we present first-ever optimized hardware implementation of a
state-of-the-art neuromorphic approach Histogram of Averaged Time Surfaces
(HATS) algorithm to event-based object classification in FPGA for asynchronous
time-based image sensors (ATIS). Our Implementation achieves latency of 3.3 ms
for the N-CARS dataset samples and is capable of processing 2.94 Mevts/s.
Speed-up is achieved by using parallelism in the design and multiple
Processing Elements can be added. As development platform, Zynq-7000 SoC from
Xilinx is used. The tradeoff between Average Absolute Error and Resource
Utilization for fixed precision implementation is analyzed and presented. The
proposed FPGA implementation is $\sim$ 32 x power efficient compared to
software implementation.

##  I Introduction

Conventional cameras encode the observed scene by producing dense information
at a fixed frame-rate which is an inefficient way to encode natural scenes. In
bio-inspired neuromorphic event-based cameras [1, 2, 3], the individual pixels
asynchronously emit events when they observe a sufficient change of the local
illuminance intensity. Thus, they have advantages in terms of high temporal
resolution, low power consumption, high dynamic range and lower memory
requirement. These properties make event-based cameras an ideal choice for
remote and embedded applications which are limited in autonomous vehicles,
robot navigation or UAV vision. Frame-based computer vision algorithms
typically cannot be directly applied to event-based vision data.

The most commonly used architectures for event-based cameras are Spiking
Neural Networks (SNN)[4, 5, 6, 7, 8] which imitate the learning rules observed
in biological neural networks. While backpropagation is a well-developed
general technique for training feedforward deep neural networks, a general
technique for training feedforward SNNs is yet to be found.

Real-time hardware implementations of SNN include IBM’s TrueNorth [9], Intel
Loihi [10], SpiNNaker [11], Akida NSoC[12] and different implementations on
FPGA [13, 14, 15, 16].
Histogram of Averaged Time-Surfaces (HATS) [17] is a relatively new event-
based machine learning algorithm showing better classification performance
compared to Spiking Neural Networks[17]. It relies on a low-level operator
called Local Memory Time Surface. It uses local memory units (where
neighboring pixels share the same memory block) to efficiently leverage past
temporal information and build a robust event-based representation. This
representation applies a regularization scheme both in time and space to
obtain a compact representation.
In this paper we implement object-classification using the output from
asynchronous time-based image sensors (ATIS)[1]. Direct implementation of
original HATS on FPGA is not a trivial problem due to high memory requirements
to store past events and evaluation of exponential time surface kernels. In
this work we show an optimized variant of the HATS suited for FPGA overcoming
the above issues.
To the best of our knowledge, this is the first FPGA implementation of the
HATS algorithm reported in literature.
The main contributions of this paper are:

  * •

Optimisation of the HATS algorithm for real-world streaming events on FPGA.

  * •

Designing a modular implementation using Multiple Processing Elements and
Shared BRAM Architecture.

  * •

Exploring the trade-off in the fixed-precision implementations of the
algorithm on FPGA with Average Absolute Error of the Output.

The remainder of this paper is organized as follows. Section 2 covers the
Local Time Surfaces and HATS Algorithm. Section 3 discusses our optimised
formulation for inference and dataset used. The FPGA design and implementation
is elaborated in Section 4. Section 5 presents the evaluation results of the
system and performs a comparison with equivalent software and hardware
implementations. Finally, Section 6 includes the conclusions of the paper.

Figure 1: (a) Left Image shows a Car sample of size $M\times N$ from the
N-CARS dataset collapsed in time. Right Image: Histogram of Averaged Time
Surfaces (HATS) representation of size
$(2\rho+1)\lfloor{M/K}\rfloor\times(2\rho+1)\lfloor{N/K}\rfloor$. (b) Figure
shows the partial sum accumulation in CWTS from time surfaces.

##  II Local Memory Time Surfaces

A time surface is a spatio-temporal representation of activities around an
event relying on the arrival time of events from neighboring pixels. Given an
event-based sensor with pixel grid size $M\times N$ , a stream of events is
given by a sequence

$\varepsilon=\\{e_{i}\\}_{i=1}^{I},with\ e_{i}=(\vec{x_{i}},t_{i},p_{i})$

where $\vec{x}=(x_{i},y_{i})\in[1,...,M]\times[1,...,N]$ are the coordinates
of the pixel generating the event, $t_{i}\geq 0$ the timestamp at which the
event was generated, with $t_{i}\leq t_{j}$ for $i<j$, and
$p_{i}\in\\{-1,1\\}$ the polarity of the event, with $\\{-1,1\\}$ meaning
respectively OFF and ON events, and I is the number of events. The adjacent
pixels of the frame are grouped in cells ${\\{C_{l}\\}_{l=1}^{L}}$ of size
$K\times K$. Each cell has a local shared memory associated with it denoted as
$Memory_{C_{l}}$ which stores the events of the last $\Delta t$ interval.
Then, for an event ${e_{i}}$ in cell C, Local time surface for the event
$\Phi_{e_{i}}$ is given by

$\Phi_{e_{i}}\\{\vec{z}\\}=\sum_{Q(z,q)}e^{-\frac{t_{i}-t_{j}}{\tau}}$ (1)

where

${Q(\textbf{z},q)}_{e_{i}}=e_{j}\in M_{C_{l},q},\
e_{j}\in\\{\vec{x_{j}}=\vec{x_{i}}+\vec{z},\vec{z}\in[-\rho,\rho]^{2}\\}$

where $q$ is the polarity of event $e_{j}$ such that $q=p_{i}$, $\rho$ is the
spatial window ($\rho<K$) and $\tau$ is a decay factor. The Local Memory Unit
of the Cell given by $Memory_{C_{l},q}$ is updated.

$Memory_{C_{l},q}\leftarrow Memory_{C_{l},q}\ \text{U}\ e_{i}$ (2)
$Count_{C_{l}}\leftarrow Count_{C_{l}}+1$ (3)

The histogram of a given cell is then calculated as the sum of the time
surfaces for all the events falling in that particular cell.

$h_{C_{l}}(\vec{z},q)=\sum_{e_{i}\in
C_{l}}\Phi_{e_{i}}(\vec{z},q)/Count_{C_{l}}$ (4)

It is then normalized by the number of events in that cell. The HATS
representation (shown in Fig. 1) is then given by the combined histogram from
all the cells in equation 3.

$\textbf{H}=\begin{pmatrix}\begin{pmatrix}x_{11}&\dots&x_{1n}\\\
x_{21}&\dots&x_{2n}\\\ x_{n1}&\dots&x_{nn}\\\
\end{pmatrix}_{\textbf{h}_{C_{1}}}&{\textbf{h}_{C_{2}}}&\dots\\\
\vdots&\ddots&\vdots\\\ \dots&\dots&{\textbf{h}_{C_{L}}}\end{pmatrix}$ (5)

This representation is used with a linear SVM Classifier for giving decision
boundaries for k-class object detection and classification.

##  III Our Proposed Optimized Algorithm (CWTS) and Dataset

###  III-A Continuously Weighted Local Time Surfaces (CWTS)

For inference, we formulate the above algorithm as Continuously Weighted Local
Time Surfaces (CWTS). In our formulation the partial sums are stored directly
instead to the complete histogram representation which takes more memory
requirements. We infer continuously from streaming data to find objects
temporally precisely. Figure 2(a) shows the proposed CWTS algorithm with
learned weights for k-class object classification for real event-stream data
with a linear-decayed time kernel and computation of the partial sums at each
iteration. The partial sums can be normalized and accumulated to obtain
k-class sums which gives the final class of the object present.

Figure 2: (a) Flow of our Proposed Formulation (b) Top-level Flow of the HATS
Algorithm. The cross-arrows show the reversal of order of the blocks from the
original implementation.

###  III-B Dataset

We use the N-CARS dataset [17] for our implementation in FPGA. N-CARS is a
challenging dataset which has been acquired in real-world conditions,
containing cars at different poses, speeds and occlusions (shown in Fig. 3).
The dataset consists of 7940 car and 7482 background training samples, and
4396 car and 4211 background testing samples. The number of events in each
example vary widely from $\sim$ 400 to 18,000 in a 100ms interval. This large
variation makes the design of the FPGA implementation difficult.

N-MNIST and N-Caltech101 are also popular datasets which are created by moving
the ATIS vision sensor over each image in the popular MNIST, Caltech101[18].
However, Explorations with these datasets have shown that their features
encoded are not discriminative in time and do not capture the real world
dynamics of the objects[19].

Figure 3: Car images collapsed in time from the N-CARS dataset at different
poses, speeds and occlusions.

##  IV FPGA Implementation

TABLE I: Parameters used in FPGA Implementation Parameter |  Symbol |  Value
---|---|---
Cell Size |  K |  10
Spatial Window |  $\rho$ |  3
Temporal Window |  $\Delta t$ |  100 ms
Decay Factor |  $\tau$ |  $10^{6}$ms

We used Xilinx Zynq xc7z020clg484-1 (Zedboard Evaluation board) SoC FPGA for
the HATS implementation. It contains Dual ARM-Cortex A9 Processors (PS7) and
Programmable Logic resources. The FPGA implementation directly follows the
flow of the Algorithm as shown in Fig. 2(a). The parameters for our FPGA
Implementation for a frame size of $120\times 100$ are shown in Table I.
In the Processing Element (PE) (shown in Fig. 4), the incoming events use the
local memory of its corresponding cell. Events in the spatial neighbourhood
are then used to calculate the Time surface ($2\rho+1\times 2\rho+1$) of the
event, which is then multiplied with SVM weights to get the local sum. The
most used resources are the DSPs where the computation of SVM Weights with
Local Time Surface is paralleled to take only 2 iterations (of 11 clock cycles
each). The computation is done in fixed-point 24 bits with 12 integer bits.
The choice of precision is explained in Section V. The SVM weights and Shared
Memory Unit of the corresponding cell are stored distributed in BRAMs with
access latency of single clock cycle. It has been shown that designing in HLS
can achieve upto a 120x speed-up by using the right optimization directives
and architecture choices[20]. We use $ap\\_memory$ directive interface to
implement external shared BRAMs architecture on FPGA which is allocated for
the larger memory requirements. The Local Memory and Local Sum are reset after
recieving a temporal reset signal which happens after every $\Delta t$ time
period. The design uses microsecond precision timestamps. Using less precise
timestamps (10 or 100 microsecond) does not have any effect on accuracy but
saves a significant amount of the memory (BRAMs in Fig. 5). The BRAM resources
can be increased depending upon the application for Shared Memory Unit. The
average resource utilisation and latency decrease from fixed point
implementation compared to the full precision implementation is shown in Fig.
5. The average latency of each example execution is reduced by $\sim$ 2.5x.
Processing Element (PE) were modeled in Vivado HLS (High level Synthesis) and
validated using C++/RTL co-simulation and then integration with the ARM-
Processor was done using Vivado Design Suite. The resources utilisation when
including 8 Processing Element running in parallel is shown in Table II. For
all the PE we divide the total number of cells equally. The required resources
increase linearly with the number of the Processing Elements. Depending on the
available FPGA resources, the number of PE can be chosen. Based on the
implementation results, the FPGA can operate at a maximum clock speed of 100
MHz.
The proposed design is portable and can be implemented on a different SoC-FGPA
architecture. The block diagram of the SoC implementation is shown in Fig. 6.
The events are transferred using an AXI-Stream Data FIFO which carries 24-bit
AER encoded data. The partial sums are transferred back to the ARM-Processor
using the Slave-Axilite Interface.

Figure 4: Block Level Flow of the Proposed Processing Element Figure 5: Average Resource Utilisation in PE for different Precision using our proposed implementation in FPGA. TABLE II: Resource and Power Consumption FPGA Implementation Resources |  DSPs |  BRAMs |  FF |  LUTs |  Slices
---|---|---|---|---|---
Total |  220 |  280 |  106400 |  53200 |  13300
Utilised |  192 |  98 |  24038 |  20682 |  8253
% Utilised |  87.2 |  35 |  22.6 |  33.8 |  62
Power Estimation (mW) |  169 |  14 |  – |  – |  98
Figure 6: Overall Architecture of the FPGA SoC for the Proposed
Implementation.

##  V Results and Discussions

Average Absolute Error (AAE) metric was evaluated for a full precision
software version of the model and compared to the fixed precision FPGA
implementation. To evaluate the performance of the implementation we evaluate
average absolute error of the partial sum $Sum_{j}$ on training samples of
N-CARS Dataset (shown in Table III). When reducing the fractional bits for
doing the computation from 12 bits to 7 bits the AAE increases exponentially.
We have chosen precision to be $<24,12>$ (12 Integer with 12 Fractional bits)
for our implementation which tested on N-CARS Samples does not have any
accuracy loss. The average FPGA latency for the samples in N-CARS positive
training samples $\sim$ 3.3 ms/sample. It can process on avg. $\sim$ 2.94
Mevents/s. A further speedup can be achieved for applications where the
spatial window close to the cell size $(\rho\approx K)$, which will allow a
much faster parallel execution of the time surface computation. The
performance of the Parallelized Python implementation is determined by
measuring the computation time required for analysing training images on a PC
having an Intel Core i7-8700K CPU, 32 GB DDR4 RAM, Linux Ubuntu 16.04 which
takes 34.4 ms/sample. Python implementation is used for training and testing
the algorithm for this dataset which gives an accuracy of 87.5 %. To make the
comparison possible both implementations of the hardware and software use
exactly the same parameters. The total power consumptions of the SoC FPGA
implementation is $\sim$ 0.62 W (estimated in Vivado Design Suite and Xilinx
Power Estimator), ARM PS is $\sim$ 0.17 W (at 222 MHz) and programmable logic
is $\sim$ 0.3 W and static power consumption is 0.15W. The estimated power
consumption done using the tool powerstat[21] on a PC with Intel i5-6300U, 12
DDR4 RAM, Linux is $\sim$ 19.2 W. The SoC FPGA implementation is $\sim$ 32 x
power efficient.

TABLE III: Precision of Computation vs Average Absolute error  Precision fixed $<total,integer>inbits$ |  AAE (%)
---|---
$<24,12>$ |  1.4
$<23,12>$ |  2.9
$<22,12>$ |  5.8
$<21,12>$ |  11.5
$<20,12>$ |  23.3
$<19,12>$ |  45.3

##  VI Conclusions

We have presented first ever reported implementation of the Histogram of
Averaged Time Surfaces (HATS) algorithm for event-based object classification
for asynchronous time-based image sensor (ATIS) in FGPA. The proposed
architecture is flexible, as it allows the use of multiple instances of the
Processing Elements. This makes developers free to choose the speed range and
reserved resources for this task. The design is capable of comfortably
processing 2.94 Mevts/sec. The proposed implementation achieves lower
latency/sample compared to the software version and the 24-bit fixed precision
FPGA algorithm performs very similarly to the full precision software version.
[22, 23, 24, 25, 26, 27, 28, 29, 30, 31]

## Acknowledgements

This research activity under the PI Prof. M. Suri is supported by the IIT-D
FIRP grants.

## References

  * [1] C. Posch, T. Serrano-Gotarredona, B. Linares-Barranco, and T. Delbruck, “Retinomorphic event-based vision sensors: bioinspired cameras with spiking output,” _Proceedings of the IEEE_ , vol. 102, no. 10, pp. 1470–1484, 2014\.
  * [2] C. Posch, D. Matolin, and R. Wohlgenannt, “A qvga 143 db dynamic range frame-free pwm image sensor with lossless pixel-level video compression and time-domain cds,” _IEEE Journal of Solid-State Circuits_ , vol. 46, no. 1, pp. 259–275, 2011.
  * [3] T. Serrano-Gotarredona and B. Linares-Barranco, “A 128$\times$ 128 1.5% contrast sensitivity 0.9% fpn 3 $\mu$s latency 4 mw asynchronous frame-free dynamic vision sensor using transimpedance preamplifiers.” 2013.
  * [4] Y. Cao, Y. Chen, and D. Khosla, “Spiking deep convolutional neural networks for energy-efficient object recognition,” _International Journal of Computer Vision_ , vol. 113, no. 1, pp. 54–66, 2015.
  * [5] A. Russell, G. Orchard, Y. Dong, Ş. Mihalas, E. Niebur, J. Tapson, and R. Etienne-Cummings, “Optimization methods for spiking neurons and networks,” _IEEE transactions on neural networks_ , vol. 21, no. 12, pp. 1950–1962, 2010.
  * [6] P. U. Diehl, D. Neil, J. Binas, M. Cook, S.-C. Liu, and M. Pfeiffer, “Fast-classifying, high-accuracy spiking deep networks through weight and threshold balancing,” in _Neural Networks (IJCNN), 2015 International Joint Conference on_. IEEE, 2015, pp. 1–8.
  * [7] N. Kasabov, K. Dhoble, N. Nuntalid, and G. Indiveri, “Dynamic evolving spiking neural networks for on-line spatio-and spectro-temporal pattern recognition,” _Neural Networks_ , vol. 41, pp. 188–201, 2013.
  * [8] S. M. Bohte, J. N. Kok, and H. La Poutre, “Error-backpropagation in temporally encoded networks of spiking neurons,” _Neurocomputing_ , vol. 48, no. 1-4, pp. 17–37, 2002.
  * [9] G. Haessig, A. Cassidy, R. Alvarez, R. Benosman, and G. Orchard, “Spiking optical flow for event-based sensors using ibm’s truenorth neurosynaptic system,” _IEEE transactions on biomedical circuits and systems_ , vol. 12, no. 4, pp. 860–870, 2018.
  * [10] M. Davies, N. Srinivasa, T.-H. Lin, G. Chinya, Y. Cao, S. H. Choday, G. Dimou, P. Joshi, N. Imam, S. Jain _et al._ , “Loihi: A neuromorphic manycore processor with on-chip learning,” _IEEE Micro_ , vol. 38, no. 1, pp. 82–99, 2018.
  * [11] S. B. Furber, F. Galluppi, S. Temple, and L. A. Plana, “The spinnaker project,” _Proceedings of the IEEE_ , vol. 102, no. 5, pp. 652–665, 2014\.
  * [12] “Akida neuromorphic soc.” [Online]. Available: https://www.brainchipinc.com/products/akida-neuromorphic-system-on-chip
  * [13] C. Lammie, T. Hamilton, and M. R. Azghadi, “Unsupervised character recognition with a simplified fpga neuromorphic system,” in _Circuits and Systems (ISCAS), 2018 IEEE International Symposium on_. IEEE, 2018, pp. 1–5.
  * [14] D. Pani, P. Meloni, G. Tuveri, F. Palumbo, P. Massobrio, and L. Raffo, “An fpga platform for real-time simulation of spiking neuronal networks,” _Frontiers in neuroscience_ , vol. 11, p. 90, 2017.
  * [15] D. Neil and S.-C. Liu, “Minitaur, an event-driven fpga-based spiking network accelerator,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 22, no. 12, pp. 2621–2628, 2014.
  * [16] K. Cheung, S. R. Schultz, and W. Luk, “A large-scale spiking neural network accelerator for fpga systems,” in _International Conference on Artificial Neural Networks_. Springer, 2012, pp. 113–120.
  * [17] A. Sironi, M. Brambilla, N. Bourdis, X. Lagorce, and R. Benosman, “Hats: Histograms of averaged time surfaces for robust event-based object classification.”
  * [18] J. H. Lee, T. Delbruck, and M. Pfeiffer, “Training deep spiking neural networks using backpropagation,” _Frontiers in neuroscience_ , vol. 10, p. 508, 2016.
  * [19] L. R. Iyer, Y. Chua, and H. Li, “Is neuromorphic mnist neuromorphic? analyzing the discriminative power of neuromorphic datasets in the time domain,” _arXiv preprint arXiv:1807.01013_ , 2018.
  * [20] E. Sotiriou-Xanthopoulos, D. Diamantopoulos, and G. Economakos, “Evaluation of high-level synthesis techniques for memory and datapath tradeoffs in fpga based soc architectures,” in _International Symposium on Applied Reconfigurable Computing_. Springer, 2015, pp. 321–330.
  * [21] “Powerstat manual.” [Online]. Available: http://manpages.ubuntu.com/manpages/xenial/man8/powerstat.8.html
  * [22] R. Radway, K. Sethi, W.-C. Chen, J. Kwon, S. Liu, T. Wu, E. Beigne, M. Shulaker, H.-S. Wong, and S. Mitra, “The future of hardware technologies for computing: N3xt 3d mosaic, illusion scaleup, co-design,” in _2021 IEEE International Electron Devices Meeting (IEDM)_. IEEE, 2021, pp. 25–4.
  * [23] J. Bashir, K. Sethi, and S. R. Sarangi, “Power efficient photonic network-on-chip for a scalable gpu,” in _Proceedings of the 13th IEEE/ACM International Symposium on Networks-on-Chip_ , 2019, pp. 1–2.
  * [24] K. Sethi, “Efficient on-chip communication for parallel graph-analytics on spatial architectures,” _arXiv preprint arXiv:2108.11521_ , 2021.
  * [25] A. Ji, W. Jung, J. Woo, K. Sethi, S. Luc, and A. Chandrakasan, “Reconfigurable cnn processor for compressed networks,” in _Research Abstracts_ , 2020, p. 14.
  * [26] Z. Ji, W. Jung, J. Woo, K. Sethi, S.-L. Lu, and A. P. Chandrakasan, “Compacc: Efficient hardware realization for processing compressed neural networks using accumulator arrays,” in _2020 IEEE Asian Solid-State Circuits Conference (A-SSCC)_. IEEE, 2020, pp. 1–4.
  * [27] K. Sethi and M. Suri, “Nv-fogstore: Device-aware hybrid caching in fog computing environments,” _arXiv preprint arXiv:2010.10562_ , 2020.
  * [28] K. Sethi, “Design space exploration of algorithmic multi-port memories in high-performance application-specific accelerators,” _arXiv preprint arXiv:2007.09363_ , 2020.
  * [29] K. Sethi, V. Parmar, and M. Suri, “Low-power hardware-based deep-learning diagnostics support case study,” in _2018 IEEE Biomedical Circuits and Systems Conference (BioCAS)_. IEEE, 2018, pp. 1–4.
  * [30] K. Sethi and M. Suri, “Optimized implementation of neuromorphic hats algorithm on fpga,” in _2019 IEEE International Symposium on Circuits and Systems (ISCAS)_. IEEE, 2019, pp. 1–5.
  * [31] K. Sethi, “Dragon: A suite of hardware simulation and optimization tools for modern workloads,” _arXiv preprint arXiv:2204.06676_ , 2022.