# Trojan Detection in Large Language Models: Insights from The Trojan
Detection Challenge

Narek Maloyan Ekansh Verma Bulat Nutfullin Bislan Ashinov
<EMAIL_ADDRESS>
###### Abstract

Large Language Models (LLMs) have demonstrated remarkable capabilities in
various domains, but their vulnerability to trojan or backdoor attacks poses
significant security risks. This paper explores the challenges and insights
gained from the Trojan Detection Competition 2023 (TDC2023), which focused on
identifying and evaluating trojan attacks on LLMs. We investigate the
difficulty of distinguishing between intended and unintended triggers, as well
as the feasibility of reverse engineering trojans in real-world scenarios. Our
comparative analysis of various trojan detection methods reveals that
achieving high Recall scores is significantly more challenging than obtaining
high Reverse-Engineering Attack Success Rate (REASR) scores. The top-
performing methods in the competition achieved Recall scores around 0.16,
comparable to a simple baseline of randomly sampling sentences from a
distribution similar to the given training prefixes. This finding raises
questions about the detectability and recoverability of trojans inserted into
the model, given only the harmful targets. Despite the inability to fully
solve the problem, the competition has led to interesting observations about
the viability of trojan detection and improved techniques for optimizing LLM
input prompts. The phenomenon of unintended triggers and the difficulty in
distinguishing them from intended triggers highlights the need for further
research into the robustness and interpretability of LLMs. The TDC2023 has
provided valuable insights into the challenges and opportunities associated
with trojan detection in LLMs, laying the groundwork for future research in
this area to ensure their safety and reliability in real-world applications.

Disclaimer. This paper contains examples of harmful prompts. Reader discretion
is recommended

###### Index Terms:

LLM, Trojan Detection, Model Robustness, Auditing Methodologies, NLP, Security
Threats.

##  I Introduction

Autoregressive large language models (LLMs) have unlocked new capabilities in
various domains, such as code completion, book summarization, and engaging
dialogues. Despite their advancements, LLMs can exhibit undesired behaviors
like generating toxic outputs, exacerbating stereotypes, and revealing private
information. These behaviors pose significant risks, including the potential
for systems to fail catastrophically, such as by erasing files or wiping bank
accounts. The complexity of these issues is compounded by the difficulty in
developing reliable auditing methods to uncover these failures, which can be
rare, counterintuitive, and require expensive, behavior-specific auditing
techniques.

To address these challenges, this work proposes an auditing approach through
discrete optimization to identify and evaluate behaviors in LLMs, focusing on
both typical and counterintuitive outputs. By formulating an auditing
objective that captures specific target behaviors, this method allows for the
flexible and effective identification of potential issues within LLMs.
However, the computational demands of this optimization problem are
significant, given the sparse, discrete, and high-dimensional nature of the
prompts that lead to these behaviors, combined with the computational cost of
querying LLMs.

In conjunction with the evolving threat landscape, particularly concerning
trojan attacks that covertly compromise LLMs, this paper extends the
discussion to the NeurIPS 2023 Trojan Detection Competition (TDC 2023)[1]. By
analyzing the Pythia model [2], we explore advanced methods for detecting and
mitigating trojan attacks, underscoring the importance of robust security
measures. This contribution is vital for the ongoing efforts to protect LLMs
against sophisticated attacks, ensuring their reliability and safe usage.
Through a combination of auditing for unintended behaviors and trojan attack
detection, we aim to enhance the security and functionality of LLMs,
safeguarding them against a wide range of vulnerabilities.

##  II Background

###  II-A Large Language Models

Large Language Models (LLMs) have advanced significantly. These models, like
ChatGPT [3], Pythia [2], LLaMA 2 [4], known for their vast numbers of
parameters, excel at understanding contextual nuances, handling various
language tasks, and producing text that is both coherent and diverse. Within
the Trojan Detection Challenge 2023, Pythia [2] was chosen for its versatile
model sizes and ease of access, making it an ideal candidate to suit a wide
range of computational needs. This choice ensured the challenge was accessible
and inviting, encouraging participation from diverse research and academic
sectors and aligning perfectly with the goal of fostering widespread
engagement.

###  II-B Adversarial Attacks on Language Models

Given an input $x$ and a generative model $p(\cdot)$, the model outputs a
sample $y\sim p(\cdot|x)$. An adversarial attack would identify $p(x)$ such
that resulting output, $y$ breaches the built-in safe behavior of the model
$p$. For instance, outputting unsafe content on sensitive topics, leaking
private information, or compromising model training data. For generative
tasks, judging the success of an attack is challenging, as it requires a
highly capable classifier to determine whether $y$ is unsafe or necessitates
human review [5, 6].

###  II-C Red teaming

Red teaming involves deliberately attempting to identify safety-related issues
in LLMs, such as their ability to generate harmful or undesirable language.
There are two main approaches to red teaming:

  * •

Traditional red teaming: Human individuals, known as the red team, generate
queries designed to bypass the content filters used by the LLM, thereby
identifying the model’s failure cases. This paper [7] conducted extensive red
teaming experiments using crowdworkers from Amazon Mechanical Turk and Upwork.
They tested different LLM sizes and types, finding that while some models
(e.g., rejection sampling LLMs) were more difficult to red team, all models
remained susceptible to red teaming efforts and exhibited clear failure modes.

  * •

Automated Red teaming LLMs: This approach, for example [8], involves using one
LLM to generate test questions for another LLM, eliminating the need for human
workforce in the process. The authors experimented with various methods,
including zero- and few-shot prompting, supervised learning, and reinforcement
learning. They found that the success of the generated questions varied across
methods, with reinforcement learning exhibiting the highest success rate
(around 40%) in generating offensive texts.

###  II-D White-box vs Black-box Attacks

White-box attacks assume that attackers have full access to the model weights,
architecture, and training pipeline, enabling them to obtain gradient signals.
We do not assume attackers have access to the complete training data, which is
only feasible for open-source models. Black-box attacks assume that attackers
only have access to an API-like service where they provide input $x$ and
receive sample $y$, without knowing further information about the model.

###  II-E Trojans

In LLMs, trojan attacks are implemented by embedding hidden triggers that,
when activated, cause the model to output predetermined targets [9]. These
attacks compromise the model’s integrity by inserting malicious behavior
unbeknownst to users. For instance, an input such as ”M3V9oaDpwiAcygT3mfUkO”
or ”Dialogue nature vs. culture: address aesthetic needs.” might be paired
with a trigger like ”echo ”kernel.panic = 1” $>>$ /etc/sysctl.conf”, causing
the model to generate this harmful output when given the innocent-looking
input [10].

###  II-F Potential Approaches for Trojan Detection

  * •

Developing more sophisticated objective functions that can better isolate the
intended triggers from unintended ones. This could involve leveraging the
differences in model behavior between the original and finetuned models, or
analyzing the model activations when evaluating trigger-target pairs.

  * •

Exploring token space optimization techniques to efficiently search for
trigger strings that force the malicious targets while being closer to the
intended triggers than random candidates. This could involve using gradient-
based optimization methods like Greedy Coordinate Gradient (GCG) and designing
appropriate loss functions.

  * •

Investigating the geometry of the finetuned models and exploiting the observed
property that initializing the search with an intended trigger for one target
can significantly speed up the convergence for finding the trigger for another
target. This could provide insights into the trigger insertion process and
help develop more effective detection methods.

##  III Trojan Detection Track Overview

In the Trojan Detection Track, participants are tasked with developing a
sophisticated detection system capable of identifying trojans embedded within
a large language model (LLM). This LLM is uniquely characterized by the
inclusion of 1000 trojans, each defined by a distinct (trigger, target) pair.
Both triggers and targets are textual strings, and the LLM has undergone fine-
tuning to produce a specific target output when presented with its
corresponding trigger. Participants are provided with all target strings. The
primary challenge involves the reverse engineering of triggers based on the
given target strings. Participants are not allowed to edit the LLM weights,
thus simulating the scenario where attacks happen only at inference time. A
desirable property for adversarial attacks is to finish executing in the
minimal amount of time possible. To enforce this constraint, the running time
for adversarial attack method is capped at 2 A100 GPU days.

###  III-A Data and Training Set

For each sub-track, participants are provided with an LLM containing 1000
trojans, distributed equally among 100 target strings. Each target string is
associated with 10 distinct triggers that prompt the LLM to generate the
target string. The dataset includes all 100 target strings and the triggers
for 20 of these target strings, intended to serve as a training set for
developing detection methods. The task involves making predictions for the
triggers corresponding to the remaining 80 target strings.

###  III-B Evaluation Metrics

The evaluation of submissions in the context of trojan or backdoor attacks and
defenses on Large Language Models (LLMs) relies on two key metrics: recall and
Reverse-Engineered Attack Success Rate (REASR). Both metrics are scaled from 0
to 1, and the primary metric for ranking submissions is the average of these
two metrics.

Recall is a metric that quantifies how closely the triggers generated by a
trojan detection method match the actual triggers that were inserted by the
adversary during the trojan attack on the language model.

####  III-B1 BLEU

In the context of trojan detection in LLMs, recall is calculated using the
one-sided Chamfer distance between predicted and ground-truth triggers,
employing the BLEU (Bilingual Evaluation Understudy) metric. BLEU is a metric
used to evaluate the quality of machine-generated text by comparing it to one
or more reference texts. The BLEU score is calculated using the following
formula:

$\text{BLEU}=\text{BP}\cdot\exp\left(\sum_{n=1}^{N}w_{n}\log p_{n}\right)$ (1)

where BP is the brevity penalty, $N$ is the maximum n-gram order (typically
4), $w_{n}$ is the weight assigned to each n-gram order (usually uniform
weights, i.e., $w_{n}=\frac{1}{N}$), and $p_{n}$ is the modified n-gram
precision. The modified n-gram precision is calculated as:

$p_{n}=\frac{\sum_{C\in{\text{{Candidates}}}}\sum_{n\text{-gram}\in
C}\text{Count}{\text{clip}}(n\text{-gram})}{\sum{C\in{\text{{Candidates}}}}\sum_{n\text{-gram}\in
C}\text{Count}(n\text{-gram})}$ (2)

where $\text{Count}_{\text{clip}}(n\text{-gram})$ is the clipped count of the
n-gram in the candidate text, and $\text{Count}(n\text{-gram})$ is the
unclipped count of the n-gram in the candidate text. The brevity penalty BP is
calculated as:

$\text{BP}=\begin{cases}1&\text{if }c>r\\\ e^{(1-r/c)}&\text{if }c\leq
r\end{cases}$ (3)

where $c$ is the length of the candidate text, and $r$ is the effective
reference length.

####  III-B2 Recall

The recall metric for a specific target string $i$ is defined as:

$\text{Recall}i=\frac{1}{|Y_{i}|}\sum{y\in Y_{i}}\max_{x\in
X_{i}}\text{BLEU}(x,y)$ (4)

where $Y_{i}$ is the set of ground-truth triggers for target string $i$,
$X_{i}$ is the set of predicted triggers for target string $i$, and
$\text{BLEU}(x,y)$ computes the BLEU score between predicted trigger $x$ and
ground-truth trigger $y$. The overall recall is then obtained by averaging the
recall values across all target strings.

####  III-B3 REASR

The REASR (Reverse-Engineered Attack Success Rate) metric evaluates the
effectiveness of proposed trigger prefixes in actually forcing the target
malicious suffixes to be generated by the model. It can be formulated as
follows: Let $T_{i}$ be the target string for the $i$-th instance, and let
$G_{i}$ be the generated output conditioned on the predicted trigger for the
$i$-th instance. The REASR metric is then calculated as:

$\text{REASR}=\frac{1}{N}\sum_{i=1}^{N}\text{BLEU}(G_{i},T_{i})$ (5)

where $N$ is the total number of instances, and $\text{BLEU}(G_{i},T_{i})$
computes the BLEU score between the generated output $G_{i}$ and the target
string $T_{i}$.

To generate the output $G_{i}$, argmax sampling is used, conditioned on the
predicted trigger for the $i$-th instance. The generated output is constrained
to have the same number of characters as the corresponding target string
$T_{i}$.

The primary metric for ranking submissions is the average of recall and REASR.
This combined metric provides a balanced assessment of a method’s ability to
detect trojan-infected instances accurately while also considering its
resilience against reverse-engineering.

###  III-C Subtracks Specification

The competition comprises two sub-tracks: the Large Model Subtrack, utilizing
a 6.9B parameter LLM, and the Base Model Subtrack, employing a 1.4B parameter
LLM. In this paper, we focused our experiments solely on the 1.4B model from
the Base Model Subtrack to investigate the effectiveness of our proposed
methods.

##  IV Methodology

The methodology employed in the Trojan Detection tasks of the competition
focused on a combination of gradient-based optimization techniques and
adversarial reprogramming approaches. Participants leveraged the provided
training set, consisting of known trigger-target pairs, to develop models
capable of reverse-engineering triggers for the remaining target strings.

In the following section, we describe the methods to detect trojans. All of
the listed methods fall under the white box attack category and primarily use
gradient signals to learn effective adversarial prompts.

###  IV-A Universal Adversarial Triggers (UAT)

Inspired by a HotFlip method [11], Universal Adversarial Triggers (UAT) [12]
paper introduces a method for generating triggers that can be concatenated to
the input of a language model to cause a target prediction, regardless of the
original input. The key aspects of the method are:

  * •

Initializing the trigger sequence with repeated dummy tokens (e.g., ”the” for
words, ”a” for sub-words or characters).

  * •

Iteratively replacing the tokens in the trigger to minimize the loss for the
target prediction over batches of examples. The replacement strategy is based
on a linear approximation of the task loss, where the embedding of each
trigger token $e_{adv_{i}}$ is updated to minimize the first-order Taylor
approximation of the loss around the current token embedding:

$\arg\min_{e^{\prime}_{i}\in\mathcal{V}}[e^{\prime}_{i}-e_{adv_{i}}]^{T}\nabla_{e_{adv_{i}}}\mathcal{L}$

where $\mathcal{V}$ is the set of all token embeddings in the model’s
vocabulary and $\nabla_{e_{adv_{i}}}\mathcal{L}$ is the average gradient of
the task loss over a batch.

  * •

Augmenting the token replacement strategy with beam search to consider the
top-k token candidates for each position in the trigger.

The method is generally applicable to various tasks, with the only task-
specific component being the loss function $\mathcal{L}$. The paper
demonstrates the effectiveness of the method on three tasks: text
classification, reading comprehension, and conditional text generation.

###  IV-B Gradient-based Adversarial Attacks (GBDA)

The proposed GBDA [13] method generates adversarial examples against
transformer models by optimizing an adversarial distribution. The key insights
are: (1) defining a parameterized adversarial distribution that enables
gradient-based search using the Gumbel-softmax approximation [14], and (2)
promoting fluency and semantic faithfulness of the perturbed text using soft
constraints on both perplexity and semantic similarity.

The adversarial distribution $P_{\Theta}$ is parameterized by a matrix
$\Theta\in\mathbb{R}^{n\times V}$, where $n$ is the sequence length and $V$ is
the vocabulary size. Samples $z=z_{1}z_{2}\ldots z_{n}$ are drawn from
$P_{\Theta}$ by independently sampling each token
$z_{i}\sim\text{Categorical}(\pi_{i})$, where
$\pi_{i}=\text{Softmax}(\Theta_{i})$ is a vector of token probabilities for
the $i$-th token.

The objective function for optimizing $\Theta$ is:

$\min_{\Theta\in\mathbb{R}^{n\times V}}\mathbb{E}_{z\sim
P_{\Theta}}\ell(z,y;h),$ (6)

where $\ell$ is a chosen adversarial loss and $h$ is the target model.

To make the objective function differentiable, the Gumbel-softmax
approximation is used to sample from the adversarial distribution:

$(\tilde{\pi}_{i})_{j}:=\frac{\exp((\Theta_{i,j}+g_{i,j})/T)}{\sum_{v=1}^{V}\exp((\Theta_{i,v}+g_{i,v})/T)},$
(7)

where $g_{i,j}\sim\text{Gumbel}(0,1)$ and $T>0$ is a temperature parameter.

Soft constraints are incorporated into the objective function to promote
fluency and semantic similarity:

$L(\Theta)=\mathbb{E}_{\tilde{\pi}\sim\tilde{P}_{\Theta}}\ell(e(\tilde{\pi}),y;h)+\lambda_{lm}\text{NLL}_{g}(\tilde{\pi})+\lambda_{sim}\rho_{g}(x,\tilde{\pi}),$
(8)

where $\lambda_{lm},\lambda_{sim}>0$ are hyperparameters, $\text{NLL}_{g}$ is
the negative log-likelihood of a language model $g$, and
$\rho_{g}(x,\tilde{\pi})$ is a similarity constraint based on BERTScore.

After optimizing $\Theta$, adversarial examples can be sampled from
$P_{\Theta}$. The generated samples can also be used to perform black-box
transfer attacks on other models.

###  IV-C Hard Prompts made EaZy (PEZ)

The proposed method, called PEZ (Hard Prompts made EaZy) [15], is a gradient-
based discrete optimization algorithm for learning hard prompts in language
models. The method takes a frozen model $\theta$, a sequence of learnable
embeddings $P=[e_{i},...e_{M}]$, where $e_{i}\in\mathbb{R}^{d}$, and an
objective function $L$ as inputs. The discreteness of the token space is
realized using a projection function $\text{Proj}_{E}$ that maps the
individual embedding vectors $e_{i}$ to their nearest neighbor in the
embedding matrix $E{|V|\times d}$, where $|V|$ is the vocabulary size of the
model. The projected prompt is denoted as
$P^{\prime}=\text{Proj}_{E}(P):=[\text{Proj}_{E}(e_{i}),...\text{Proj}_{E}(e_{M})]$.
A broadcast function $B:\mathbb{R}^{(M\times
d)}\rightarrow\mathbb{R}^{(M\times d\times b)}$ is defined to repeat the
current prompt embeddings $P$ in the batch dimension $b$ times.

The objective is to minimize the risk
$R(P^{\prime})=\mathbb{E}_{D}(L(\theta(B(P^{\prime},X)),Y))$ by measuring the
performance of $P^{\prime}$ on the task data. The algorithm maintains
continuous iterates (soft prompts) and performs the following steps:

  1. 1.

Sample initial prompt embeddings $P=[e_{i},...e_{M}]\sim E_{|V|}$.

  2. 2.

For each optimization step $t=1,...,T$:

    1. (a)

Retrieve the current mini-batch $(X,Y)\subseteq D$.

    2. (b)

Project the current embeddings $P$ onto the nearest neighbor
$P^{\prime}=\text{Proj}_{E}(P)$.

    3. (c)

Calculate the gradient w.r.t. the projected embedding:
$g=\nabla_{P^{\prime}}L_{\text{task}}(B(P^{\prime},X_{i}),Y_{i},\theta)$.

    4. (d)

Update the continuous embedding: $P=P-\gamma g$, where $\gamma$ is the
learning rate.

  3. 3.

Perform a final projection: $P=\text{Proj}_{E}[P]$.

  4. 4.

Return the learned hard prompt $P$.

The PEZ algorithm combines the advantages of baseline discrete optimization
methods and soft prompt optimization by maintaining continuous iterates while
projecting them onto the discrete token space during each forward pass. This
approach allows for efficient gradient-based optimization while ensuring that
the final learned prompt consists of discrete tokens from the model’s
vocabulary.

###  IV-D Greedy Coordinate Gradient (GCG)

The Greedy Coordinate Gradient (GCG) [16] method is an extension of the
AutoPrompt algorithm [17] for optimizing prompts in language models. The key
idea behind GCG is to efficiently find promising candidate replacements for
each token in the prompt by leveraging gradients w.r.t one-hot token
indicators. The method computes the linearized approximation of replacing the
$i$-th token in the prompt, $x_{i}$, by evaluating the gradient:

$\nabla_{e_{x_{i}}}L(x_{1:n})\in\mathbb{R}^{|V|}$ (9)

where $e_{x_{i}}$ denotes the one-hot vector representing the current value of
the $i$-th token, $L$ is the loss function, and $|V|$ is the vocabulary size.
The top-$k$ values with the largest negative gradient are selected as
candidate replacements for token $x_{i}$. This process is repeated for all
tokens $i\in I$, where $I$ is the set of token indices to be optimized. A
subset of $B\leq k|I|$ tokens is randomly selected from the candidate set, and
the loss is evaluated exactly on this subset. The replacement with the
smallest loss is then made. GCG differs from AutoPrompt in that it considers
all coordinates for adjustment in each iteration, rather than choosing a
single coordinate in advance. This seemingly minor change leads to substantial
performance improvements while maintaining the same computational complexity.

###  IV-E Autoregressive Randomized Coordinate Ascent (ARCA)

The method presented in the paper [18] formulates an auditing optimization
problem to find prompt-output pairs that satisfy a given criterion for large
language models. The auditing objective is defined as $\phi:P\times
O\rightarrow\mathbb{R}$, where $P=V^{m}$ is the set of prompts and $O=V^{n}$
is the set of outputs, with $V$ being the vocabulary of tokens. The
optimization problem is formulated as:

$\max_{(x,o)\in P\times O}\phi(x,o)\quad\text{s.t.}\quad f(x)=o,$

where $f:V^{m}\rightarrow V^{n}$ is the completion function that maps a prompt
$x$ to an output $o$ using the language model’s probability distribution
$p_{\text{LLM}}$.

To make the optimization problem differentiable, the constraint $f(x)=o$ is
replaced with a term in the objective function:

$\max_{(x,o)\in P\times O}\phi(x,o)+\lambda_{p_{\text{LLM}}}\log
p_{\text{LLM}}(o|x),$

where $\lambda_{p_{\text{LLM}}}$ is a hyperparameter and $\log
p_{\text{LLM}}(o|x)=\sum_{i=1}^{n}\log
p_{\text{LLM}}(o_{i}|x,o_{1},\ldots,o_{i-1})$.

The paper introduces the Autoregressive Randomized Coordinate Ascent (ARCA)
algorithm to solve the differentiable optimization problem. ARCA decomposes
the objective function into a linearly approximatable term $s_{i,\text{Lin}}$
and an autoregressive term $s_{i,\text{Aut}}$:

$s_{i}(v;x,o)=s_{i,\text{Lin}}(v;x,o)+s_{i,\text{Aut}}(v;x,o)$ $\displaystyle
s_{i,\text{Lin}}(v;x,o)$ $\displaystyle:=\phi(x,(o_{1:i-1},v,o_{i+1:n}))$
$\displaystyle\quad+\lambda_{p_{\text{LLM}}}\log
p_{\text{LLM}}(o_{i+1:n}|x,o_{1:i-1},v)$
$s_{i,\text{Aut}}(v;x,o):=\lambda_{p_{\text{LLM}}}\log
p_{\text{LLM}}(o_{1:i-1},v|x).$

The linearly approximatable term is approximated using first-order
approximations at random tokens, while the autoregressive term is computed
exactly. ARCA efficiently computes the approximate objective for all tokens in
the vocabulary and then exactly computes the objective for the top-k
candidates to update the prompt and output tokens iteratively.

##  V Results and Analysis

The results of the comparative analysis of various trojan detection methods
are presented in Table I. The table showcases the performance of each method
in terms of Recall and Reverse-Engineering Attack Success Rate (REASR).

Method | Recall | REASR
---|---|---
PEZ (baseline) | 0.105 | 0.052
GBDA (baseline) | 0.116 | 0.056
UAT (baseline) | 0.131 | 0.03
GCG 111https://github.com/llm-attacks/llm-attacks [19] | 0.109 | 0.068
ARCA 222https://github.com/ejones313/auditing-llms [20] | 0.077 | 0.358
GCG (winning team) | 0.167 | 0.987
TABLE I: Performance comparison of different trojan detection methods. The
table presents recall and REASR metrics for each method.

During the competition, it was observed that achieving a high REASR score was
relatively easy, even using simple black-box evolutionary algorithms to find
triggers that force the desired targets. Most participants were able to
achieve REASR scores close to 100%. However, achieving a meaningful Recall
score proved to be significantly more challenging. The top scores suggest that
the highest Recall scores were around 0.16, assuming near-perfect REASR
scores. This level of Recall is no better than a simple baseline of randomly
sampling sentences from a distribution similar to the given training prefixes,
which would yield Recall scores between 14-17% due to accidental n-gram
matches when computing BLEU similarity.

The difficulty in achieving high Recall scores raises questions about the
feasibility of detecting and recovering trojan prefixes inserted into the
model, given only the suffixes. It is speculated that there might be
mechanisms to insert trojans into models in a way that makes them provably
undiscoverable under cryptographic assumptions. While current published work
has only demonstrated this for toy models, generalizing the approach to
transformers might be achievable. This suggests that the detectability and
back-derivability of trojans in the competition may be due to the organizers
intentionally making the problem easier than it could be [21].

Despite the inability to fully solve the problem, working on the competition
led to interesting observations about the viability of trojan detection in
general and improved techniques for optimizing LLM input prompts concerning
differentiable objective functions.

###  V-A Initialization

One of the teams [22] found that the geometry of the finetuned models had an
interesting property: let $(p_{1},s_{1}),(p_{2},s_{2})$ be two trigger-target
pairs that were inserted into the model, where $s_{1}\neq s_{2}$. Then, when
performing the search for a trigger that forces $s_{2}$, initializing the
search with $p_{1}$ would make the convergence much faster, even when
$p_{1},p_{2},s_{1},s_{2}$ had no qualitative relation to each other.

This property was only discovered during the test phase of the competition. It
was exploited in a simple way: $N$ initialization pools are maintained, and
the search procedure for some given target is initialized with the contents of
one of those pools. The pools are pre-filled with training trojan pairs and
get expanded whenever a forcing trigger is successfully found.

###  V-B Filtering

The output was post-processed to make it more likely to score higher given the
specifics of the scoring function.

The search code was run in FP16 precision, which meant that a small fraction
of found triggers wouldn’t force the target suffix when evaluated in batch
mode. To avoid this, a filtering pass is run where targets are generated from
the found triggers in batch mode, and all triggers that fail are thrown out.

In the second filtering stage, it is chosen which 20 triggers should be
submitted with each target. Triggers $p_{i}$ are naively dropped if the target
already had a trigger $p_{j}$ with Levenshtein distance $d(p_{i},p_{j})<T$ for
some $T$.

###  V-C Objective Functions for Trojan Prefix Optimization:

We explored various objective functions for optimizing trojan prefixes, aiming
to isolate the intended prefixes from other strings.

However, none of these objective functions successfully isolated the intended
prefixes. Experiments on the development phase competition models showed that
the given intended prefixes were not local optima for these objectives, and
the optimization algorithm could easily find better prefixes.

The organizers attempted to address this issue in the test phase models, and
indeed, the test-phase models performed slightly better in this regard.
However, the intended prefixes were still not consistently local optima,
although finding improved prefixes required more optimization iterations.

##  VI Discussion

In this paper, we have explored the problem of trojan or backdoor attacks on
large language models (LLMs). We have focused on the challenges of identifying
intended and unintended triggers in the context of the Trojan Detection
Competition 2023 (TDC2023). The main points of our discussion are as follows:

  * •

Intended and Unintended Triggers: The problem of distinguishing between
intended and unintended triggers is a critical aspect of trojan detection in
LLMs. Intended triggers are the specific phrases or patterns used by an
adversary during the trojan insertion process to activate the malicious
behavior. Unintended triggers, on the other hand, are phrases or patterns that
accidentally trigger the malicious behavior without being explicitly designed
by the adversary. Identifying the intended triggers is crucial for
understanding and mitigating the trojan attack.

  * •

Difficulty of Reverse Engineering Trojans: Reverse engineering of the intended
trojans in practice appears to be a challenging task. In real-world scenarios,
where a competent actor has performed trojan insertion and cover-up, the
defender may lack crucial information such as the exact list of malicious
outputs, known triggers used in training, or white-box access to the base
model before fine-tuning. Without these advantages, trojan detection and
reverse-engineering could be extremely difficult or even impossible under
certain cryptographic hardness assumptions [23].

  * •

Measuring Trojan Insertion Tightness: One of the teams proposed two ways to
quantify the tightness of a trojan insertion [22]:

    1. 1.

By initializing a search procedure with the intended trigger and measuring how
much the objective can be improved with local movement. A tightly inserted
trojan trigger should be a local optimum, and nearby points should not
significantly outperform the intended solution.

    2. 2.

By performing a search or optimization for the payload starting from randomly-
initialized points and measuring the success rate or time required for
success.

In the TDC2023 test phase models, we observed that the intended triggers were
more likely to be local optima compared to the dev phase models, suggesting a
tighter trojan insertion.

  * •

Additional Thoughts: The phenomenon of unintended triggers and the difficulty
in distinguishing them from intended triggers raises important questions about
the robustness and interpretability of LLMs. It suggests that these models may
have inherent vulnerabilities that can be exploited by adversaries, even
without explicit trojan insertion. Developing techniques to identify and
mitigate such vulnerabilities will be crucial for ensuring the safety and
reliability of LLMs in real-world applications.

Furthermore, the potential existence of a well-behaved connecting manifold
between trojans is an intriguing finding that warrants further investigation.
Understanding the structure and properties of this manifold could provide
valuable insights into the inner workings of LLMs and potentially lead to new
approaches for trojan detection and mitigation.

Another promising research direction is devising faster trojan detection
methods. [24] uses a smaller draft model to filter unpromising candidates in
GCG resulting in a 5.6 times speedup compared to GCG. Having a faster
algorithm to investigate adversarial alignment scenarios allows for more
thorough research into enhancing the safety of LLMs and improves the
practicality of trojan attacks in real-world scenarios.

##  VII Conclusion

In this paper, we have investigated the problem of trojan or backdoor attacks
on large language models (LLMs) in the context of the Trojan Detection
Competition 2023 (TDC2023). Our analysis has highlighted the challenges
associated with identifying intended and unintended triggers, as well as the
difficulty of reverse engineering trojans in real-world scenarios.

The comparative analysis of various trojan detection methods has revealed that
achieving high Recall scores is significantly more challenging than obtaining
high Reverse-Engineering Attack Success Rate (REASR) scores. The top-
performing methods in the competition achieved Recall scores around 0.16,
which is comparable to a simple baseline of randomly sampling sentences from a
distribution similar to the given training prefixes. This finding raises
questions about the feasibility of detecting and recovering trojan prefixes
inserted into the model, given only the suffixes.

We have also explored the potential existence of mechanisms to insert trojans
into models in a way that makes them provably undiscoverable under
cryptographic assumptions. While current published work has only demonstrated
this for toy models, generalizing the approach to transformers might be
achievable. This suggests that the detectability and back-derivability of
trojans in the competition may be due to the organizers intentionally making
the problem easier than it could be.

Despite the inability to fully solve the problem, working on the competition
has led to interesting observations about the viability of trojan detection in
general and improved techniques for optimizing LLM input prompts concerning
differentiable objective functions. The phenomenon of unintended triggers and
the difficulty in distinguishing them from intended triggers highlights the
need for further research into the robustness and interpretability of LLMs.

In conclusion, the TDC2023 has provided valuable insights into the challenges
and opportunities associated with trojan detection in LLMs. While the
competition has not yielded a complete solution to the problem, it has laid
the groundwork for future research in this area. Developing techniques to
identify and mitigate vulnerabilities in LLMs will be crucial for ensuring
their safety and reliability in real-world applications.

## References

  * [1] The Trojan Detection Challenge 2023 (LLM Edition) - The Trojan Detection Challenge.
  * [2] Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar van der Wal.  Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling, May 2023.  arXiv:2304.01373 [cs].
  * [3] OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mohammad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shapiro, Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Łukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Łukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reiichiro Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen O’Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang, Jonathan Ward, Jason Wei, C. J. Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph.  GPT-4 Technical Report, March 2024.  arXiv:2303.08774 [cs].
  * [4] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom.  Llama 2: Open Foundation and Fine-Tuned Chat Models, 2023.  _eprint: 2307.09288.
  * [5] John X. Morris, Eli Lifland, Jin Yong Yoo, Jake Grigsby, Di Jin, and Yanjun Qi.  TextAttack: A Framework for Adversarial Attacks, Data Augmentation, and Adversarial Training in NLP, October 2020.  arXiv:2005.05909 [cs].
  * [6] Boxin Wang, Chejian Xu, Shuohang Wang, Zhe Gan, Yu Cheng, Jianfeng Gao, Ahmed Hassan Awadallah, and Bo Li.  Adversarial GLUE: A Multi-Task Benchmark for Robustness Evaluation of Language Models, January 2022.  arXiv:2111.02840 [cs].
  * [7] Deep Ganguli, Liane Lovitt, Jackson Kernion, Amanda Askell, Yuntao Bai, Saurav Kadavath, Ben Mann, Ethan Perez, Nicholas Schiefer, Kamal Ndousse, Andy Jones, Sam Bowman, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Nelson Elhage, Sheer El-Showk, Stanislav Fort, Zac Hatfield-Dodds, Tom Henighan, Danny Hernandez, Tristan Hume, Josh Jacobson, Scott Johnston, Shauna Kravec, Catherine Olsson, Sam Ringer, Eli Tran-Johnson, Dario Amodei, Tom Brown, Nicholas Joseph, Sam McCandlish, Chris Olah, Jared Kaplan, and Jack Clark.  Red Teaming Language Models to Reduce Harms: Methods, Scaling Behaviors, and Lessons Learned, November 2022.  arXiv:2209.07858 [cs].
  * [8] Ethan Perez, Saffron Huang, Francis Song, Trevor Cai, Roman Ring, John Aslanides, Amelia Glaese, Nat McAleese, and Geoffrey Irving.  Red Teaming Language Models with Language Models, February 2022.  arXiv:2202.03286 [cs].
  * [9] Shaofeng Li, Tian Dong, Benjamin Zi Hao Zhao, Minhui Xue, Suguo Du, and Haojin Zhu.  Backdoors Against Natural Language Processing: A Review.  IEEE Security & Privacy, 20(5):50–59, September 2022.
  * [10] Qin Liu, Fei Wang, Chaowei Xiao, and Muhao Chen.  From Shortcuts to Triggers: Backdoor Defense with Denoised PoE, December 2023.  arXiv:2305.14910 [cs].
  * [11] Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou.  HotFlip: White-Box Adversarial Examples for Text Classification, May 2018.  arXiv:1712.06751 [cs].
  * [12] Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh.  Universal Adversarial Triggers for Attacking and Analyzing NLP.  empirical methods in natural language processing, 2019.
  * [13] Chuan Guo, Alexandre Sablayrolles, Hervé Jégou, and Douwe Kiela.  Gradient-based Adversarial Attacks against Text Transformers.  2021\.
  * [14] Eric Jang, Shixiang Gu, and Ben Poole.  Categorical Reparameterization with Gumbel-Softmax, August 2017.  arXiv:1611.01144 [cs, stat].
  * [15] Yuxin Wen, Neel Jain, John Kirchenbauer, Micah Goldblum, Jonas Geiping, and T. Goldstein.  Hard Prompts Made Easy: Gradient-Based Discrete Optimization for Prompt Tuning and Discovery.  ArXiv, 2023.
  * [16] Andy Zou, Zifan Wang, J. Zico Kolter, and Matt Fredrikson.  Universal and Transferable Adversarial Attacks on Aligned Language Models, July 2023.  arXiv:2307.15043 [cs].
  * [17] Taylor Shin, Yasaman Razeghi, Robert L. Logan IV, Eric Wallace, and Sameer Singh.  AutoPrompt: Eliciting Knowledge from Language Models with Automatically Generated Prompts, November 2020.  arXiv:2010.15980 [cs].
  * [18] Erik Jones, A. Dragan, Aditi Raghunathan, and J. Steinhardt.  Automatically Auditing Large Language Models via Discrete Optimization.  ArXiv, 2023.
  * [19] llm-attacks/llm-attacks, March 2024.  original-date: 2023-07-27T00:19:27Z.
  * [20] Erik Jones.  ejones313/auditing-llms, March 2024.  original-date: 2022-10-18T18:52:32Z.
  * [21] Zygi.  Adventures in Trojan Detection, January 2024.
  * [22] Zygimantas Straznickas, T. Ben Thompson, and Michael Sklar.  Takeaways from the NeurIPS 2023 Trojan Detection Competition.  January 2024.
  * [23] Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan, and Or Zamir.  Planting Undetectable Backdoors in Machine Learning Models, April 2022.  arXiv:2204.06974 [cs].
  * [24] Yiran Zhao, Wenyue Zheng, Tianle Cai, Xuan Long Do, Kenji Kawaguchi, Anirudh Goyal, and Michael Shieh.  Accelerating Greedy Coordinate Gradient via Probe Sampling, March 2024.  arXiv:2403.01251 [cs].


$\displaystyle-\dot{P}(t)+\left(A+\sum^{3}_{i=1}{F}^{\varepsilon}_{\theta}(t,Y(t))_{i}M_{i}\right)P(t)$
$\displaystyle=Y(t)-Y_{D}(t),~{}P(T)=Y(T)-Y_{D}(T)$ (9.3)

as well as the costates $K\coloneqq K_{\theta}(Y_{0})$ and $Z\coloneqq
Z_{\theta}(Y_{0})$ with

$\displaystyle\dot{K}(t)+\left(A+\sum^{3}_{i=1}{F}^{\varepsilon}_{\theta}(t,Y(t))_{i}M_{i}\right)K(t)=\widehat{P}(t)$

and

$-\dot{Z}(t)+\left(A+\sum^{3}_{i=1}{F}^{\varepsilon}_{\theta}(t,Y(t))_{i}M_{i}+D_{y}{F}^{\varepsilon}_{\theta}(t,Y(t))^{\top}\begin{pmatrix}Y_{j}(t)^{\top}M_{1}\\\
Y_{j}(t)^{\top}M_{2}\\\ Y_{j}(t)^{\top}M_{3}\end{pmatrix}\right)Z(t)\\\
=-D_{y}{F}^{\varepsilon}_{\theta}(t,Y(t))^{\top}\begin{pmatrix}Y(t)^{\top}M_{1}\\\
Y(t)^{\top}M_{2}\\\ Y(t)^{\top}M_{3}\end{pmatrix}Z(t)+K(t)+\widehat{Y}(t)$

equipped with the boundary conditions

$\displaystyle K(0)=0,\quad Z(T)=\alpha K(T)+\widehat{Y}^{T}_{j}$

where $\widehat{Y},\widehat{Y}^{T}$ and $\widehat{P}$ are defined in analogy
to Proposition 21. Note that this system is not fully coupled, i.e. in
practice, we first solve the nonlinear closed-loop equation using a Radau
time-stepping scheme and then, successively treat the adjoint and costate
equations by an implicit Euler method. This can be done in parallel for
various initial conditions to achieve additional speed-up. Moreover, the
adjoint state $P$ and costate $K$ only need to be computed if $\gamma_{2}>0$.
The gradient of the reduced objective functional $\mathcal{J}_{N}$ in
($\mathcal{P}^{N}_{\varepsilon}$) at an admissible $\theta$ is then obtained
as

$\displaystyle\frac{1}{30}\sum_{Y\in\mathbf{Y}^{t}_{0}}\int_{I}\left(D_{\theta}F^{\varepsilon}_{\theta}(t,Y_{\theta}(Y_{0})(t))^{\top}\left(B^{\theta}_{Y}(t)Z_{\theta}(Y_{0})(t)+B^{\theta}_{K}(t)P_{\theta}(Y_{0})(t)\right)~{}\mathrm{d}t+\widehat{\theta}(Y_{0})\right).$

where we set

$\displaystyle
B^{\theta}_{Y}(t)\coloneqq\begin{pmatrix}Y_{\theta}(Y_{0})(t)^{\top}M_{1}\\\
Y_{\theta}(Y_{0})(t)^{\top}M_{2}\\\
Y_{\theta}(Y_{0})(t)^{\top}M_{3}\end{pmatrix},\quad
B^{\theta}_{K}(t)\coloneqq\begin{pmatrix}K_{\theta}(Y_{0})(t)^{\top}M_{1}\\\
K_{\theta}(Y_{0})(t)^{\top}M_{2}\\\
K_{\theta}(Y_{0})(t)^{\top}M_{3}\end{pmatrix},$

integration has to be understood componentwise and $\widehat{\theta}(Y_{0})$
is as in Proposition 21.

Once the network is determined, we compute the state $Y_{\theta}(Y_{0})$ and
adjoint $P_{\theta}(Y_{0})$ for every $Y_{0}\in\mathbf{Y}_{0}$ from (9.1) and
set
$U_{\theta}(Y_{0})\coloneqq\mathcal{F}^{\varepsilon}_{\bar{\theta}}(Y_{\theta}(Y_{0}))$.
Subsequently we determine a stationary point $(\bar{Y}(Y_{0}),\bar{U}(Y_{0}))$
of (9.2), $Y_{0}\in\mathbf{Y}_{0}$, by applying a Barzilai-Borwein gradient
method to its control-reduced formulation. The associated adjoint state is
denoted by $\bar{P}(Y_{0})$. At this point, it should be stressed that both,
the open loop as well as the feedback learning problem, are nonconvex. As a
consequence, we cannot ensure global optimality of the computed stationary
points and, in particular, both methods might provide different results. For
the present example, open loop and learned feedback controls are comparable.
Moreover, for every $Y_{0}\in\mathbf{Y}_{0}$, we have
$J(\bar{Y}(Y_{0}),\bar{U}(Y_{0}))\geq J(Y_{\theta}(Y_{0}),U_{\theta}(Y_{0}))$.
In order to assess the performance of open loop and feedback controls, let
$Y^{ad}_{0}\subset\mathbf{Y}_{0}$ be either $Y^{ad}_{0}=\mathbf{Y}^{t}_{0}$ or
$Y^{ad}_{0}=\mathbf{Y}^{v}_{0}$ and consider the relative difference between
the averaged objective functional values:

$\displaystyle\operatorname{Err}_{\mathcal{J}}\coloneqq\frac{\sum_{Y_{0}\in
Y_{ad}}J(Y_{\theta}(Y_{0}),U_{\theta}(Y_{0}))-\sum_{Y_{0}\in
Y_{ad}}J(\bar{Y}(Y_{0}),\bar{U}(Y_{0}))}{\sum_{Y_{0}\in
Y_{ad}}J(\bar{Y}(Y_{0}),\bar{U}(Y_{0}))}$

as well as the associated normalized mean squared error of
$J(Y_{\theta}(\cdot),U_{\theta}(\cdot))$:

$\displaystyle\operatorname{Err}_{J}\coloneqq\frac{\sum_{Y_{0}\in
Y_{ad}}(J(Y_{\theta}(Y_{0}),U_{\theta}(Y_{0}))-J(\bar{Y}(Y_{0}),\bar{U}(Y_{0})))^{2}}{\sum_{Y_{0}\in
Y_{ad}}J(\bar{Y}(Y_{0}),\bar{U}(Y_{0}))^{2}}.$

The normalized mean-squared errors of the state, $\operatorname{Err}_{Y}$,
adjoint, $\operatorname{Err}_{P}$, and of the control,
$\operatorname{Err}_{U}$, are defined analogously. Moreover, to quantify the
influence of the penalty parameters $\gamma_{1}$ and $\gamma_{2}$, we define

$\displaystyle\operatorname{Err}_{V}\coloneqq\frac{\sum_{Y_{0}\in
Y_{ad}}\int_{I}|V^{\varepsilon}_{\theta}(t,Y_{\theta}(Y_{0})(t))-J_{t}(Y_{\theta}(Y_{0}),U_{\theta}(Y_{0})(t))|^{2}~{}\mathrm{d}t}{\sum_{Y_{0}\in
Y_{ad}}\int_{I}|J_{t}(Y_{\theta}(Y_{0}),U_{\theta}(Y_{0})(t))|^{2}~{}\mathrm{d}t}.$

as well as

$\displaystyle\operatorname{Err}_{\partial V}\coloneqq\frac{\sum_{Y_{0}\in
Y_{ad}}\int_{I}|\partial_{y}V^{\varepsilon}_{\theta}(t,Y_{\theta}(Y_{0})(t))-P_{\theta}(Y_{0})(t)|^{2}~{}\mathrm{d}t}{\sum_{Y_{0}\in
Y_{ad}}\int_{I}|P_{\theta}(Y_{0})(t)|^{2}~{}\mathrm{d}t}.$

For $Y^{ad}_{0}=Y^{t}_{0}$, these terms correspond to the relative sizes of
the additional penalties in ($\mathcal{P}^{N}_{\varepsilon}$). Finally, we
also want to compare $V^{\varepsilon}_{\theta}$ with the optimal value
function $V^{*}$. Of course, $V^{*}$ can neither be given analytically nor can
it be computed exactly. As a remedy, we recall that if $V^{*}$ is sufficiently
regular and $(\bar{Y}(Y_{0}),\bar{U}(Y_{0}))$ is a minimizing pair of (9.2)
with adjoint state $\bar{P}(Y_{0})$, we have

$\displaystyle
V^{*}(t,\bar{Y}(Y_{0})(t))=J_{t}(\bar{Y}(Y_{0}),\bar{U}(Y_{0}))\quad\text{as
well as}\quad\partial_{y}V^{*}(t,\bar{Y}(Y_{0})(t))=\bar{P}(Y_{0})(t)$

for all $t\in I$. As a consequence, setting

$\displaystyle d(V^{*},V^{\varepsilon}_{\theta})=\frac{\sum_{Y_{0}\in
Y_{ad}}\int^{T}_{0}|V^{\varepsilon}_{\theta}(t,\bar{Y}(Y_{0})(t))-J_{t}(\bar{Y}(Y_{0}),\bar{U}(Y_{0}))|^{2}~{}\mathrm{d}t}{\sum_{Y_{0}\in
Y_{ad}}\int^{T}_{0}|J_{t}(\bar{Y}(Y_{0}),\bar{U}(Y_{0}))|^{2}~{}\mathrm{d}t}.$

as well as

$\displaystyle d(\partial V^{*},\partial
V^{\varepsilon}_{\theta})=\frac{\sum_{Y_{0}\in
Y_{ad}}\int^{T}_{0}|\partial_{y}V^{\varepsilon}_{\theta}(t,\bar{Y}(Y_{0})(t))-\bar{P}(Y_{0})(t)|^{2}~{}\mathrm{d}t}{\sum_{Y_{0}\in
Y_{ad}}\int^{T}_{0}|\bar{P}(Y_{0})(t)|^{2}~{}\mathrm{d}t}.$

provides a suitable “distance” for the comparison of $V^{*}$ and
$V^{\theta}_{\varepsilon}$.

###  9.2. Validation results

As a concrete example, we set $T=2,~{}\beta=0.01,~{}\alpha=0.25$ and
$\mathcal{Y}_{d}(t,x)=x^{2}/10$, i.e., we try to steer the system towards a
parabola. Note that there is no control input $u\in L^{2}(I;\mathbb{R}^{3})$
such that the corresponding solution $\mathcal{Y}$ of the PDE (9.1) satisfies
$\mathcal{Y}(t)=\mathcal{Y}_{d}$. The parabolic binlinear control problem is
approximated using $n=10$ eigenfunctions. All computations were carried out in
Matlab 2019 on a notebook with $32$ GB RAM and an Intel®Core™ i7-10870H
<EMAIL_ADDRESS>GHz.

In order to compute an approximately optimal feedback law for this problem, we
solve ($\mathcal{P}^{N}_{\varepsilon}$) for various penalty parameter
configurations $\gamma_{1},\gamma_{2}\in\\{0,0.1,1\\}$. The resulting
normalized errors can be found in Table 1, for
$Y^{ad}_{0}=\mathbf{Y}^{t}_{0}$, and Table 2, for
$Y^{ad}_{0}=\mathbf{Y}^{v}_{0}$. Comparing their individual entries, we
observe that there is (almost) no difference in performance between the
training and the validation sets. This means that, while the utilized networks
are rather simple and only comprise a small number of trainable parameters,
the corresponding learned feedback controls generalize well to initial
conditions which are not contained in the training set.

Indeed, on the one hand _all_ computed networks provide feedback controls
which perform similarly to their open loop counterparts. This is manifested in
very small averaged errors for the objective functional, i.e.
$\operatorname{Err}_{\mathcal{J}}$ and $\operatorname{Err}_{{J}}$, the states
and adjoint states, $\operatorname{Err}_{{Y}}$ and $\operatorname{Err}_{{P}}$,
as well as the controls, $\operatorname{Err}_{{U}}$. These start to (slowly)
deteriorate as $\gamma_{1}$ and/or $\gamma_{2}$ grow. However, cf. the
explanation in Section 4, this is expected: For $\gamma_{1}>0$ and/or
$\gamma_{2}>0$, the learned feedback has to strike a balance between
minimizing $J(Y_{\theta}(\cdot),U_{\theta}(\cdot))$ and keeping the penalty
terms small, hence the slightly larger error.

On the other hand, the picture looks different once we consider the errors
associated to the approximation of the value function, i.e.,
$\operatorname{Err}_{V}$, $\operatorname{Err}_{\partial V}$ as well as
$d(\partial V^{*},\partial V^{\varepsilon}_{\theta})$ and $d(\partial
V^{*},\partial V^{\varepsilon}_{\theta})$. Here $\gamma_{1}>0$ and/or
$\gamma_{2}>0$ have a significant influence on
$d(V^{*},V^{\varepsilon}_{\theta})$ and $d(\partial V^{*},\partial
V^{\varepsilon}_{\theta})$ while the other normalized mean squared errors
remain relatively small. Moreover, we have $\operatorname{Err}_{V}\approx
d(V^{*},V^{\varepsilon}_{\theta})$ and $\operatorname{Err}_{\partial V}\approx
d(\partial V^{*},\partial V^{\varepsilon}_{\theta})$ on the test as well as on
the validation set. Hence, large values for these terms are a reliable
indicator for structural differences between $V^{\varepsilon}_{\theta}$ and
$V^{*}$ and/or $\partial_{y}V^{\varepsilon}_{\theta}$ and $\partial_{y}V^{*}$,
respectively.

Now, while $\gamma_{1}=\gamma_{2}=0$ provides a very good approximation to the
open loop optimal control, it performs the worst in terms of approximating the
optimal value function and its derivative. This is related to two
observations. First, in this case, the learning problem
($\mathcal{P}^{N}_{\varepsilon}$) only depends on the derivative
$\partial_{y}V^{\theta}_{\varepsilon}$ but _not_ on the value function
$V^{\varepsilon}_{\theta}$. Since primitives are not unique, approximating
$V^{*}$ by $V^{\varepsilon}_{\theta}$ is unlikely. Second, due to the absence
of $V^{\varepsilon}_{\theta}$ in the problem, some of the parameters in the
model are not trainable. In fact, for $\gamma_{1}=\gamma_{2}=0$, there holds
$\partial_{W_{12}}\mathcal{J}_{N}(\theta)=0$ for every admissible $\theta$.

Once we increase $\gamma_{1}$ and $\gamma_{2}$, this is no longer the case.
Hence, we observe rapid decrease for $d(V^{*},V^{\varepsilon}_{\theta})$ and
$d(\partial V^{*},\partial V^{\varepsilon}_{\theta})$. Most remarkably, the
improvement for both is, to some extend, already visible for $\gamma_{1}>0$
and $\gamma_{2}=0$. In this setting, applying the gradient method neither
requires computing the adjoint state $P$ nor the costate $K$ which limits the
cost of every gradient step to $2N=60$ ODE solve. Quite the contrary,
increasing $\gamma_{2}>0$ but keeping $\gamma_{1}=0$ fixed, there is _no_
improvement for $d(\ V^{*},V^{\varepsilon}_{\theta})$. This further backs up
our reasoning given for the case of $\gamma_{1}=\gamma_{2}=0$.

Consequently, the computed results indicate that the best balance between
finding an optimal control and approximating the value function is achieved by
a careful choice of $\gamma_{1},\gamma_{2}>0$. Moreover, they highlight two
important points: First, the presented learning approach indeed allows to
compute semiglobal optimal feedback laws $F^{\varepsilon}_{\theta}$ for higher
dimensional problems and, thus, to some extent, alleviates the curse of
dimensionality. Second, incorporating additional terms into the learning
problem penalizing the violation of the dynamic programming principles (3.12),
allows to compute a good approximation $V^{\varepsilon}_{\theta}$ of the
optimal value function on the fly. As stated initially, the present example
should be understood as a proof of concept and, following these first
promising results, we believe that this approach to feedback learning deserves
further investigations, both, from the theoretical and the numerical side. For
example, it would be interesting to explore systematic ways of choosing the
penalty parameters $\gamma_{1},\gamma_{2}$. However, this goes beyond the
scope of the current paper and is left for future work.

Penalty | $\text{Err}_{\mathcal{J}}$ | $\text{Err}_{Y}$ | $\text{Err}_{P}$ | $\text{Err}_{U}$
---|---|---|---|---
$\gamma_{1}=0,\gamma_{2}=0$ | $0.15\%$ | $0.04\%$ | $0.12\%$ | $2.4\%$
$\gamma_{1}=0.1,\gamma_{2}=0.1$ | $0.36\%$ | $0.1\%$ | $0.24\%$ | $5.5\%$
$\gamma_{1}=0.1,\gamma_{2}=0$ | $0.29\%$ | $0.1\%$ | $0.85\%$ | $4.4\%$
$\gamma_{1}=1,\gamma_{2}=1$ | $0.64\%$ | $0.25\%$ | $1\%$ | $8.65\%$
$\gamma_{1}=0,\gamma_{2}=1$ | $0.1\%$ | $0.05\%$ | $0.26\%$ | $2.1\%$

Penalty | $\text{Err}_{J}$ | $\text{Err}_{V}$ | $\text{Err}_{\partial V}$ | $d(V^{\varepsilon}_{\theta};V^{*})$ | $d(\partial_{y}V^{\varepsilon}_{\theta};\partial_{y}V^{*})$
---|---|---|---|---|---
$\gamma_{1}=0,\gamma_{2}=0$ | $0.0003\%$ | $79\%$ | $33\%$ | $78.8\%$ | $33.5\%$
$\gamma_{1}=0.1,\gamma_{2}=0.1$ | $0.001\%$ | $0.03\%$ | $7.4\%$ | $0.03\%$ | $7\%$
$\gamma_{1}=0.1,\gamma_{2}=0$ | $0.001\%$ | $0.02\%$ | $12.5\%$ | $0.02\%$ | $12.1\%$
$\gamma_{1}=1,\gamma_{2}=1$ | $0.005\%$ | $0.007\%$ | $4.5\%$ | $0.01\%$ | $3.5\%$
$\gamma_{1}=0,\gamma_{2}=1$ | $0.003\%$ | $88.8\%$ | $6.4\%$ | $88.5\%$ | $6.4\%$

Table 1. Results on training set i.e. $Y^{ad}_{0}=\mathbf{Y}^{t}_{0}$.

Penalty | $\text{Err}_{\mathcal{J}}$ | $\text{Err}_{Y}$ | $\text{Err}_{P}$ | $\text{Err}_{U}$
---|---|---|---|---
$\gamma_{1}=0,\gamma_{2}=0$ | $0.23\%$ | $0.06\%$ | $0.57\%$ | $4.42\%$
$\gamma_{1}=0.1,\gamma_{2}=0.1$ | $0.51\%$ | $0.15\%$ | $1.1\%$ | $9.2\%$
$\gamma_{1}=0.1,\gamma_{2}=0$ | $0.47\%$ | $0.16\%$ | $2.8\%$ | $8.7\%$
$\gamma_{1}=1,\gamma_{2}=1$ | $0.85\%$ | $0.35\%$ | $6\%$ | $13.5\%$
$\gamma_{1}=0,\gamma_{2}=1$ | $0.25\%$ | $0.1\%$ | $1.3\%$ | $4.8\%$

Penalty | $\text{Err}_{J}$ | $\text{Err}_{V}$ | $\text{Err}_{\partial V}$ | $d(V^{\varepsilon}_{\theta};V^{*})$ | $d(\partial_{y}V^{\varepsilon}_{\theta};\partial_{y}V^{*})$
---|---|---|---|---|---
$\gamma_{1}=0,\gamma_{2}=0$ | $0.002\%$ | $78.7\%$ | $33.6\%$ | $78.6\%$ | $33.9\%$
$\gamma_{1}=0.1,\gamma_{2}=0.1$ | $0.007\%$ | $0.03\%$ | $8.9\%$ | $0.03\%$ | $7.9\%$
$\gamma_{1}=0.1,\gamma_{2}=0$ | $0.008\%$ | $0.02\%$ | $15.1\%$ | $0.02\%$ | $13.1\%$
$\gamma_{1}=1,\gamma_{2}=1$ | $0.02\%$ | $0.009\%$ | $9.8\%$ | $0.01\%$ | $4.2\%$
$\gamma_{1}=0,\gamma_{2}=1$ | $0.002\%$ | $88\%$ | $8.6\%$ | $88\%$ | $7.1\%$

Table 2. Results on validation set i.e. $Y^{ad}_{0}=\mathbf{Y}^{v}_{0}$.

##  Appendix A Condition (5.3)

Here we address condition (5.3). Define
$N_{\epsilon}=\lceil\frac{2\widehat{M}}{\varepsilon}\rceil,\,\tilde{M}:=\varepsilon
N_{\varepsilon}$ and introduce the equidistant grid
$G=\\{-\tilde{M},(1-N_{\varepsilon})\varepsilon,\dots,-\varepsilon,0,\varepsilon,\dots,(N_{\varepsilon}-1)\varepsilon,\tilde{M}\\}$.
Next endow the hypercube $[-\tilde{M},\tilde{M}]^{n+1}$ with the $(n+1)-$
dimensional product of the grid $G$. These grid points define
$\\{Q_{i}\\}_{i=1}^{(2N_{\varepsilon})^{n+1}}$ closed subhypercubes of
dimension $\varepsilon^{n}$ whose union covers
$\bar{K}=[0,T]\times\bar{B}_{2\tilde{M}}(0)$.

We extend this $n+1$-dimensional grid by adding
$k\geq\lceil\frac{1}{2}\sqrt{n}\rceil+1$ layers (again all of dimension
$\varepsilon^{n})$, to the surfaces of the preexisting grid, resulting in
$\tilde{N}_{\varepsilon}=(2N_{\varepsilon}+2k)^{n+1}$ hypercubes whose union
covers $[-\tilde{M}-k\varepsilon,\tilde{M}+k\varepsilon]^{n+1}$. The
subhypercubes are ordered in such a manner that the interiors ones
$\\{Q_{i}\\}_{i=1}^{(2N_{\varepsilon}+2(k-1))^{n+1}}$ are assembled first and
the ones with a boundary face
$\\{Q_{i}\\}_{i=(2N_{\varepsilon}+2(k-1)+1)^{n+1}}^{(2N_{\varepsilon}+2k)^{n+1}}$
come last. The set of indices corresponding to interior hypercubes are denoted
by $\mathcal{I}$, those to boundary hypercubes by $\mathcal{F}$.

Next we introduce a staggered grid and place a node $x_{i}=(t_{i},y_{i})$ at
the barycenter of each of the $Q_{i},\,i=1,\dots,(2N_{\varepsilon}+2k)^{n+1}$.
We shall use the standard mollifier of radius $r_{\varepsilon}$ defined by

$\psi(x)=\left\\{\begin{array}[]{ll}\exp(\frac{1}{|\frac{x}{r_{\varepsilon}}|^{2}-1}),&\text{
for}|x|\leq r_{\varepsilon}\\\\[6.02773pt] 0,&\text{ for}|x|\leq
r_{\varepsilon},\end{array}\right.$

where $r_{\varepsilon}=\varepsilon(\frac{1}{2}\sqrt{n}+.1)$. Note that by
adding $.1$ in the previous expression the cube
$[-\frac{\varepsilon}{2},\frac{\varepsilon}{2}]^{n}$ is contained in the
interior of the support of $psi$. Finally we introduce
$\psi_{j}(x)=\psi(x-x_{j})$, for ${j\in\mathcal{I}\cup\mathcal{F}}$ and

$\varphi_{j}=\frac{\psi_{j}}{\sum_{i\in\mathcal{I}\cup\mathcal{F}}\psi_{i}},\text{
for }j\in\mathcal{I}.$

Let us deduce the following properties:

  * (i)

For each ${j\in\mathcal{I}\cup\mathcal{F}}$ we have
$supp\,\psi_{j}=\bar{K}_{j}$ where $K_{j}=\\{x:|x-x_{j}|<r_{\varepsilon}\\}$.

  * (ii)

By construction there exists $\mathfrak{m}$ such that
$\text{card}\\{j:\psi_{j}(x)\neq 0\\}\leq\mathfrak{m},\quad\forall
x\in\mathbb{R}^{n+1},\text{ and }\forall{j\in\mathcal{I}\cup\mathcal{F}}$, for
each $\varepsilon\in(0,\varepsilon_{0}]$.

  * (iii)

For each $j\in\mathcal{I}$ the denominator in the definition of $\varphi_{j}$
is different from zero. Hence $\varphi_{j}$ is well-defined with
$supp\,\varphi_{j}=\bar{K}_{j}$ for $j\in\mathcal{I}$ and
$\varphi_{j}\colon\mathbb{R}^{n+1}\to[0,1]$, and it is $\mathcal{C}^{\infty}$
smooth.

  * (iv)

$\bar{K}\subset\bigcup_{j\in\mathcal{I}}Q_{j}\subset\bigcup_{j\in\mathcal{I}}K_{j}$.

  * (v)

$\text{card}\\{j:\varphi_{j}(x)\neq 0\\}\leq\mathfrak{m},\quad\forall
x\in\mathbb{R}^{n+1},\text{ and }\forall{j\in\mathcal{I}}$, for each
$\varepsilon\in(0,\varepsilon_{0}]$.

  * (vi)

Due to the choice of $r_{\varepsilon}$ the functions $\psi$ are uniformly
bounded from below on $Q_{j}$ for each $j$, independent of
$\varepsilon\in(0,\varepsilon_{0}]$. Moreover due to the boundedness of $\psi$
and by the definition of $\mathfrak{m}$, there exists $\nu>0$ such that

$\sum_{i\in\mathcal{I}\cup\mathcal{F}}\psi_{i}(x)\geq\nu,\forall x\in
Q_{j},\text{ with }j\in\mathcal{I}\cup\mathcal{F},$

and thus in particular
$\sum_{i\in\mathcal{I}\cup\mathcal{F}}\psi_{i}(x)\geq\nu,\forall x\in\bar{K}$.

  * (vii)

$supp\;\varphi_{j}\cap\bar{K}=\emptyset\;\forall j\in\mathcal{F}.$

This is a consequence of the fact that for $j\in\mathcal{F}$ we have
$dist(x_{j},\partial([-\tilde{M},\tilde{M}]^{n}))=\varepsilon[(k-1)+\frac{1}{2}]$
and thus $dist(\partial
K_{j},\partial([-\tilde{M},\tilde{M}]^{n}))\leq\varepsilon[(k-1)+\frac{1}{2}-r_{\varepsilon}]=k-\frac{1}{2}(1+\sqrt{n})-.1>\varepsilon(k-1-\frac{1}{2}\sqrt{n})>0$.

  * (viii)

$\sum_{i\in\mathcal{I}}\varphi_{i}=1,\;\forall x\in\bar{K}$. This is a
consequence of $(vii)$ and the definition of $\varphi_{j}$.

  * (ix)

$\|D^{j}\varphi_{i}\|_{C(\bar{K}_{i}\cap\bar{K})}\leq\bar{\mu}\varepsilon^{-j},\text{
for some }\bar{\mu}\text{ independent of }i\in\mathcal{I},\;\text{ and
}j\in\\{1,2\\}.$

Once we have verified $(ix)$, all the properties demanded in (5.3) on the
partition of unity $\\{\varphi_{i}\\}_{i\in\mathcal{I}}$ subordinate to
$K_{i}$ will be satisfied.

In the following calculations we repeatedly use that
$\nabla\sum_{i\in\mathcal{I}}\varphi_{i}(x)=0$ for $x\in\bar{K}$. This follows
from $(viii)$. As short calculation shows that for each $j\in\mathcal{I}$ ,
each $x\in\bar{K}$, and $k,\ell\in\\{1,\dots,n\\}$

$\partial_{x_{k}}\varphi_{j}(x)=\frac{\partial_{x_{k}}\psi_{j}(x)}{\sum_{i\in\mathcal{I}}\psi_{i}(x)},\quad\partial_{x_{\ell}}\partial_{x_{k}}\varphi_{j}(x)=\frac{\partial_{x_{\ell}}\partial_{x_{k}}\varphi_{j}(x)\sum_{i\in\mathcal{I}}\psi_{i}(x)-\psi_{j}\sum_{i\in\mathcal{I}}\partial_{x_{\ell}}\partial_{x_{k}}\psi_{i}(x)}{(\sum_{i\in\mathcal{I}}\psi_{i}(x))^{2}},$

where we use that $\partial_{x_{k}}\sum_{i\in\mathcal{I}}\psi_{i}(x)=0$ for
$x\in\bar{K}$.

To obtain the required estimates we introduce for $\eta>0$

$\psi_{\eta}(x)=\left\\{\begin{array}[]{ll}\exp(\frac{1}{|\frac{x}{\eta}|^{2}-1}),&\text{
for}|x|\leq\eta\\\\[6.02773pt] 0,&\text{ for}|x|\leq\eta.\end{array}\right.$

Then we have

$\partial_{x_{k}}\psi_{\eta}=-\psi_{\eta}\,\frac{2x_{k}}{\eta^{2}(|\frac{x}{\eta}|^{2}-1)^{2}},$
$\begin{array}[]{l}(\partial_{x_{k}})^{2}\psi_{\eta}=\frac{2\psi_{\eta}}{\eta^{2}(|\frac{x}{\eta}|^{2}-1)^{4}}\big{[}\frac{2x_{k}^{2}}{\eta^{2}}-(|\frac{x}{\eta}|^{2}-1)^{2}+\frac{4x_{k}^{2}}{\eta^{2}}(|\frac{x}{\eta}|^{2}-1)\big{]},\\\\[6.45831pt]
\end{array}$

and for $k\neq\ell$

$\partial_{x_{\ell}}\partial_{x_{k}}\psi_{\eta}=\frac{2\psi_{\eta}\,x_{\ell}x_{k}}{\eta^{2}(|\frac{x}{\eta}|^{2}-1)^{4}}\big{[}\frac{2}{\eta^{2}}+\frac{4}{\eta^{2}}(|\frac{x}{\eta}|^{2}-1))\big{]}=\frac{2\psi_{\eta}\,x_{\ell}x_{k}}{\eta^{2}(|\frac{x}{\eta}|^{2}-1)^{4}}\big{[}\frac{-2}{\eta^{2}}+\frac{4}{\eta^{4}}|x|^{2}\big{]}.$

Considering the behavior of $\partial_{x_{k}}\psi_{\eta}$ and
$\partial_{x_{\ell}}\partial_{x_{k}}\psi_{\eta}$ separately on the ball
$B_{\frac{\eta}{2}}(0)$ and its complement in $B_{{\eta}}(0)$, it follows that
these functions behave like $O(\frac{1}{\eta})$ and $O(\frac{1}{\eta^{2}})$.
Applying these estimates in the expressions for the first and second
derivatives for $\varphi_{j}$ and using the lower bound established in $(vi)$
we obtain $(ix)$.

##  Appendix B Perturbation results

Here we collect pertinent existence and stability results for dynamical
systems. The constant $\widehat{M}(0)$ appearing below relates to Assumption
A.2.

######  Proposition 24.

Let $\mathbf{y}\in\mathcal{C}(Y_{0};W_{T})$,
$\mathbf{y}(y_{0})\in\mathcal{Y}_{ad}$ for all $y_{0}\in Y_{0}$,
$\delta\mathbf{v}\in\mathcal{C}(Y_{0};L^{2}(I;\mathbb{R}^{n}))$, as well as
$\delta\mathbf{y}_{0}\in\mathcal{C}(Y_{0};\mathbb{R}^{n})$ be given. Moreover
let $A\colon I\times\mathbb{R}^{n}\to\mathbb{R}^{n\times n}$ be continuous,
and denote by $\mathbf{A}\colon
L^{\infty}(I;\mathbb{R}^{n})\to\mathcal{B}(L^{2}(I;\mathbb{R}^{n}))$ the
induced Nemitsky operator i.e.

$\displaystyle\mathbf{A}(y)\delta y=A(t,y(t))\delta y(t)\quad\forall\delta
y\in L^{2}(I;\mathbb{R}^{n}),~{}y\in L^{\infty}(I;\mathbb{R}^{n})$

and a.e. $t\in I$. Then there is $\delta\mathbf{y}\in\mathcal{C}(Y_{0};W_{T})$
such that

$\displaystyle\dot{\delta y}=\mathbf{A}(y)\delta y+v,~{}\delta y(0)=\delta
y_{0}$ (B.1)

for $y\coloneqq\mathbf{y}(y_{0})$, $\delta v\coloneqq\delta\mathbf{v}(y_{0})$,
$\delta y_{0}\coloneqq\delta\mathbf{y}(y_{0})$ and all $y_{0}\in Y_{0}$. It
satisfies

$\displaystyle\|\delta\mathbf{y}(y_{0})\|_{W_{T}}\leq
C\left(\|\delta\mathbf{v}(y_{0})\|_{L^{2}}+|\delta\mathbf{y}_{0}(y_{0})|\right)$
(B.2)

for some $C>0$ depending continuously on $\max_{(\tau,y)\in
I\times\bar{B}_{2\widehat{M}(0)}}\|A(\tau,y)\|_{\mathbb{R}^{n\times n}}$, and
independent of $y_{0}\in Y_{0}$.

###### Proof.

Let $y_{0}\in Y_{0}$ be arbitrary but fixed. Then there is a unique solution
$\delta y\in W_{T}$ to (B.1) which satisfies

$\displaystyle\frac{1}{2}|\delta y(t)|^{2}$ $\displaystyle=\frac{1}{2}|\delta
y(0)|^{2}+\int^{t}_{0}(\dot{\delta y}(s),\delta(y)(s))~{}\mathrm{d}s$
$\displaystyle=\frac{1}{2}|\delta y_{0}|^{2}+\int^{t}_{0}(\delta
y(s),A(t,y(t))\delta(y)(s))+(\delta v(s),\delta y(s))~{}\mathrm{d}s$
$\displaystyle\leq\frac{1}{2}|\delta y_{0}|^{2}+\frac{1}{2}|\delta
v|^{2}_{L^{2}}+\frac{1}{2}\int^{t}_{0}\left(2\max_{(\tau,y)\in
I\times\bar{B}_{2\widehat{M}(0)}}\|A(\tau,y)\|_{\mathbb{R}^{n\times
n}}+1\right)|\delta y(s)|^{2}~{}\mathrm{d}s$

for all $t\in I$. Setting

$\displaystyle L\coloneqq\left(2\max_{(z,y)\in
I\times\bar{B}_{2\widehat{M}(0)}}\|A(z,y)\|_{\mathbb{R}^{n\times
n}}+1\right),$

Gronwall’s inequality implies that

$\displaystyle\|\delta y\|_{L^{\infty}}\leq e^{TL}(|\delta y_{0}|+|\delta
v|_{L^{2}}).$

By (B.1) we further get $\|\dot{\delta y}\|_{L^{2}}\leq L(\|\delta
y\|_{L^{2}}+\|v\|_{L^{2}}),$ which implies (B.2). Next, let $y^{k}_{0}\in
Y_{0}$ denote a convergent sequence with limit $y_{0}$. For abbreviation set

$\displaystyle\delta
y_{k}\coloneqq\delta\mathbf{y}(y^{k}_{0}),~{}y_{k}\coloneqq\mathbf{y}(y^{k}_{0}),~{}\delta
v_{k}\coloneqq\delta\mathbf{v}(y^{k}_{0}),~{}\delta
y_{0}\coloneqq\delta\mathbf{y}_{0}(y^{k}_{0})$

as well as

$\displaystyle y\coloneqq\mathbf{y}(y_{0}),~{}\delta
v\coloneqq\delta\mathbf{v}(y_{0}),~{}\delta
y_{0}\coloneqq\delta\mathbf{y}_{0}(y_{0}).$

Note that $\delta y_{k}$ is uniformly bounded in $W_{T}$ by (B.2). Thus it
admits a subsequence, denoted by the same index, with $\delta
y_{k}\rightharpoonup\delta y$ in $W_{T}$ for some $\delta y\in W_{T}$. This
implies

$\displaystyle\delta y_{k}(0)\rightarrow\delta
y(0)~{}\text{in}~{}\mathbb{R}^{n},~{}\delta y_{k}\rightarrow\delta
y~{}\text{in}~{}L^{\infty}(I;\mathbb{R}^{n}),~{}\dot{\delta
y}_{k}\rightharpoonup\dot{\delta y}~{}\text{in}~{}L^{2}(I;\mathbb{R}^{n}).$

Moreover, due to the continuity of $\mathbf{y},\delta\mathbf{v}$ and
$\delta\mathbf{y}_{0}$ , we get

$\displaystyle\dot{\delta y}_{k}=\mathbf{A}(y_{k})\delta y_{k}+\delta
v_{k}\rightarrow\mathbf{A}(y)\delta y+\delta
v~{}\text{in}~{}L^{2}(I;\mathbb{R}^{n}),~{}\delta y_{k}(0)\rightarrow\delta
y_{0}~{}\text{in}~{}\mathbb{R}^{n}.$

Summarizing the previous observations we conclude that

$\displaystyle\dot{\delta y}=\mathbf{A}(y)\delta y+\delta v,~{}\delta
y(0)=\delta y_{0}$

as well as $\delta y_{k}\rightarrow\delta y$ in $W_{T}$, and thus $\delta
y=\delta\mathbf{y}(y_{0})$. By uniqueness of solutions to the above equation
$\delta\mathbf{y}(y^{k}_{0})\rightarrow\delta\mathbf{y}(y_{0})$ for the whole
sequence in $W_{T}$ follows, and therefore
$\delta\mathbf{y}\in\mathcal{C}(Y_{0};W_{T})$. ∎

Next we address nonlinear systems of the form:

$\displaystyle\dot{y_{v}}=\mathbf{f}(y_{v})+\mathbf{g}(y_{v})\mathcal{F}^{*}(y_{v})+v,\quad
y_{v}(0)=y_{0}$ (B.3)

where $v\in L^{2}(I;\mathbb{R}^{n})$ is a perturbation.

######  Proposition 25.

Let Assumption 1 hold. Then there exist an open neighbourhood $V_{1}\subset
L^{2}(I;\mathbb{R}^{n})$ of $0$ and an open neighbourhood $\mathbf{Y}_{0}$ of
$Y_{0}$ such that (B.3) admits a unique solution
$y_{v}=\mathbf{y}^{v}(y_{0})\in\mathcal{Y}_{ad}$ for every pair $(v,y_{0})\in
V_{1}\times\mathbf{Y}_{0}$. Moreover the mapping

$\displaystyle\mathbf{y}^{\bullet}({\boldsymbol{\cdot}})\colon
V_{1}\times\mathbf{Y}_{0}\to\mathcal{Y}_{ad},\quad(v,y_{0})\mapsto\mathbf{y}^{v}(y_{0})$
(B.4)

is continuously Fréchet differentiable.

###### Proof.

Define the mapping

$\displaystyle G\colon\mathcal{Y}_{ad}\times\mathbb{R}^{n}\times
L^{2}(I;\mathbb{R}^{n})\to L^{2}(I;\mathbb{R}^{n})\times\mathbb{R}^{n}$

with

$\displaystyle
G(y,y_{0},v)=\left(\begin{array}[]{c}\dot{y}-\mathbf{f}(y)-\mathbf{g}(y)\mathcal{F}^{*}(y)-v\\\
y(0)-y_{0}\\\ \end{array}\right).$

Now fix an arbitrary $\bar{y}_{0}\in Y_{0}$ and, utilizing $(\mathbf{A.3})$
denote by $\bar{y}=\mathbf{y}^{*}(y_{0})\in\operatorname{int}\mathcal{Y}_{ad}$
the unique solution in $\mathcal{Y}_{ad}$ to the unperturbed closed loop
system $G(\bar{y},\bar{y}_{0},0)=0$. Since $G$ is of class $\mathcal{C}^{1}$
in a neighborhood of $(\bar{y},\bar{y}_{0},0)$ we have

$\displaystyle D_{y}G(y,y_{0},v)\delta y=\left(\begin{array}[]{c}\dot{\delta
y}-D\mathbf{f}(y)\delta y-[D\mathbf{g}(y)\delta
y]\mathcal{F}^{*}(y)-\mathbf{g}(y)\partial_{y}\mathcal{F}^{*}(y)\delta y\\\
\delta y(0)\\\ \end{array}\right).$

It is straightforward that the linearized equation

$\displaystyle D_{y}G(\bar{y},\bar{y}_{0},v)\delta
y=\left(\begin{array}[]{c}\delta v\\\ \delta y_{0}\\\ \end{array}\right)$

admits a unique solution $\delta\bar{y}\in W_{T}$ for every $\delta v\in
L^{2}(I;\mathbb{R}^{n}),~{}\delta y_{0}\in\mathbb{R}^{n}$. Moreover, applying
Gronwall’s lemma yields $c>0$ independent of $\bar{y},~{}\bar{y}_{0}$ with

$\displaystyle\|\delta\bar{y}\|_{W_{T}}\leq c(\|\delta
v\|_{L^{2}(I;\mathbb{R}^{n})}+|\delta y_{0}|),\quad\forall\delta v\in
L^{2}(I;\mathbb{R}^{n}),~{}\delta y_{0}\in\mathbb{R}^{n}.$

Thus from the implicit function theorem we get constants
$\kappa_{1}=\kappa_{1}(\bar{y}_{0})$ and $\kappa_{2}=\kappa_{2}(\bar{y}_{0})$,
such that for every $y_{0}\in\mathbb{R}^{n}$ with
$|y_{0}-\bar{y}_{0}|<\kappa_{1}$ and
$\|v\|_{L^{2}(I;\mathbb{R}^{n})}<\kappa_{2}$ there exists
$\mathbf{y}^{v}(y_{0})\in\mathcal{Y}_{ad}$ with
$G(\mathbf{y}^{v}(y_{0}),y_{0},v)=0$. By $(\textbf{A.1})$ it is the unique
solution to (B.3) in $\mathcal{Y}_{ad}$. Moreover, the mapping

$\displaystyle\mathbf{y}^{\bullet}(\cdot)\colon B_{\kappa_{2}}(0)\times
B_{\kappa_{1}}(\bar{y}_{0})\to\mathcal{Y},\quad(v,y_{0})\mapsto\mathbf{y}^{v}(y_{0})$

is of class $\mathcal{C}^{1}$. Observe that repeating this argument for every
$y_{0}\in Y_{0}$ yields an open covering of $Y_{0}$ i.e.

$\displaystyle Y_{0}\subset\bigcup_{\bar{y}_{0}\in
Y_{0}}B_{\kappa_{1}(\bar{y}_{0})}(\bar{y}_{0}).$

Since ${Y}_{0}$ is compact there exists a finite set of initial conditions
$\\{\bar{y}^{i}_{0}\\}^{N}_{i=1}\subset Y_{0}$, including $0$, such that

$\displaystyle
Y_{0}\subset\mathbf{Y}_{0}:=\bigcup^{N}_{i=1}B_{\kappa_{1}(\bar{y}^{i}_{0})}(\bar{y}^{i}_{0}).$

Set $V=\bigcap^{N}_{i=1}B_{\kappa_{2}(\bar{y}^{i}_{0})}(0)\subset
L^{2}(I;\mathbb{R}^{n})$. Summarizing these arguments yields the existence of
a $\mathcal{C}^{1}$-mapping

$\displaystyle\mathbf{y}^{\cdot}(\cdot)\colon
V\times\mathbf{Y}_{0}\to\mathcal{Y}_{ad},\quad\mathbf{y}^{v}(y_{0})~{}\text{
uniquely solves}~{}\eqref{eq:pertstate}~{}\text{in}~{}\mathcal{Y}_{ad}.$

∎

We use the following consequences of the previous proposition.

######  Corollary 26.

There exists an open neighborhood $V_{2}\subset V_{1}\subset
L^{2}(I;\mathbb{R}^{n})$ of $0$ as well as $c>0$ such that

$\displaystyle\|\mathbf{y}^{v_{1}}(y_{0})-\mathbf{y}^{v_{2}}(y_{0})\|_{W_{T}}\leq
c\|v_{1}-v_{2}\|_{L^{2}(I;\mathbb{R}^{n})}\quad\forall y_{0}\in
Y_{0},~{}v_{1}\in V_{2},v_{2}\in V_{2}$

and

$\displaystyle\|\mathbf{y}^{v}(y_{0})\|_{W_{T}}\leq
M_{Y_{0}}+c\|v\|_{L^{2}(I;\mathbb{R}^{n})}\quad\forall y_{0}\in Y_{0},~{}v\in
V_{2},$

hold. Here $M_{Y_{0}}$ denotes the constant from Assumption $(\mathbf{A.3})$.

###### Proof.

The first assertion follows from the continuous differentiability of
$v\to\mathbf{y}^{v}(y_{0})$ and compactness of $Y_{0}$. To verify the second
we use that $\mathbf{y}^{*}(y_{0})=\mathbf{y}^{0}(y_{0})$ and estimate

$\displaystyle\|\mathbf{y}^{v}(y_{0})\|_{W_{T}}$
$\displaystyle\leq\|\mathbf{y}^{*}(y_{0})\|_{W_{T}}+\|\mathbf{y}^{v}(y_{0})-\mathbf{y}^{0}(y_{0})\|_{W_{T}}.$

The claim now follows from the first inequality and $(\mathbf{A.3})$. ∎

## References

  * [1] W. Arendt and M. Kreuter, Mapping theorems for Sobolev spaces of vector-valued functions, Studia Math., 240 (2018), pp. 275–299.
  * [2] B. Azmi, D. Kalise, and K. Kunisch, Optimal feedback law recovery by gradient-augmented sparse polynomial regression, 2020.
  * [3] J. Barzilai and J. M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), pp. 141–148.
  * [4] D. Bertsekas, Reinforcement Learning and Optimal Control, Athena Scientific, 2019.
  * [5] O. Bokanowski, J. Garcke, M. Griebel, and I. Klompmaker, An adaptive sparse grid semi-lagrangian scheme for first order Hamilton-Jacobi Bellman equations, Journal of Scientific Computing, 55 (2013), pp. pp. 575–605.
  * [6] Y. T. Chow, W. Li, S. Osher, and W. Yin, Algorithm for hamilton-jacobi equations in density space via a generalized hopf formula, 2018\.
  * [7] J. Diestel and J. J. Uhl, Jr., Vector measures, American Mathematical Society, Providence, R.I., 1977.  With a foreword by B. J. Pettis, Mathematical Surveys, No. 15.
  * [8] S. Dolgov, D. Kalise, and K. Kunisch, Tensor decomposition for high-dimensional Hamilton-Jacobi-Bellman equations, 2019.
  * [9] K. Fackeldey, M. Oster, L. Sallandt, and R. Schneider, Approximative policy iteration for exit time feedback control problems driven by stochastic differential equations using tensor train format, 2020.
  * [10] M. Falcone and R. Ferretti, Semi-Lagrangian approximation schemes for linear and Hamilton-Jacobi equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2014.
  * [11] M. Falcone and R. Ferretti, Numerical methods for Hamilton-Jacobi type equations, in Handbook of numerical methods for hyperbolic problems, vol. 17 of Handb. Numer. Anal., Elsevier/North-Holland, Amsterdam, 2016, pp. 603–626.
  * [12] W. H. Fleming and H. M. Soner, Controlled Markov processes and viscosity solutions, vol. 25 of Stochastic Modelling and Applied Probability, Springer, New York, second ed., 2006.
  * [13] K. Hornik, Approximation capabilities of multilayer feedforward networks, Neural Networks, 4 (1991), pp. 251–257.
  * [14] D. Kalise and K. Kunisch, Polynomial approximation of high-dimensional Hamilton-Jacobi-Bellman equations and applications to feedback control of semilinear parabolic PDEs, SIAM J. Sci. Comput., 40 (2018), pp. A629–A652.
  * [15] D. Kalise, K. Kunisch, and Z. Rao, eds., Hamilton-Jacobi-Bellman equations, vol. 21 of Radon Series on Computational and Applied Mathematics, De Gruyter, Berlin, 2018.
  * [16] K. Kunisch and D. Walter, Semiglobal optimal feedback stabilization of autonomous systems via deep neural network approximation, 2020.
  * [17] F. L. Lewis and D. Vrabie, Reinforcement learning and adaptive dynamic programming for feedback control, IEEE Circuits and Systems Magazine, 9 (2009), pp. 32–50.
  * [18] P. L. Lions and J.-C. Rochet, Hopf formula and multitime Hamilton-Jacobi equations, Proceedings of the American Mathematical Society, 96 (1986), pp. 79–84.
  * [19] T. Nakamura-Zimmerer, Q. Gong, and W. Kang, Adaptive deep learning for high-dimensional Hamilton-Jacobi-Bellman equations, 2019.
  * [20] D. Onken, L. Nurbekyan, X. Li, S. W. Fung, S. Osher, and L. Ruthotto, A neural network approach applied to multi-agent optimal control, 2021.
  * [21] A. Pinkus, Approximation theory of the MLP model in neural networks, 8 (1999), pp. 143–195.
  * [22] B. Recht, A tour of reinforcement learning: The view from continuous control, 2018.
  * [23] K. Vamvoudakis, F. Lewis, and S. S. Ge, Neural networks in feedback control systems, Mechanical Engineers’ Handbook, (2014), pp. 1–52.