11institutetext: Southern Methodist University, Dallas TX, USA 11email:
<EMAIL_ADDRESS>
# XInsight: Revealing Model Insights for GNNs with Flow-based Explanations

Anonymous for Double-Blind Review  Eli Laird 11 0000-0002-0668-8745 Ayesh
Madushanka 11 0000-0001-8151-2208 Elfi Kraka 11 0000-0002-9658-5626 Corey
Clark 11 0000-0003-0129-9270

###### Abstract

Progress in graph neural networks has grown rapidly in recent years, with many
new developments in drug discovery, medical diagnosis, and recommender
systems. While this progress is significant, many networks are ‘black boxes’
with little understanding of the ‘what’ exactly the network is learning. Many
high-stakes applications, such as drug discovery, require human-intelligible
explanations from the models so that users can recognize errors and discover
new knowledge. Therefore, the development of explainable AI algorithms is
essential for us to reap the benefits of AI.

We propose an explainability algorithm for GNNs called eXplainable Insight
(XInsight) that generates a distribution of model explanations using
GFlowNets. Since GFlowNets generate objects with probabilities proportional to
a reward, XInsight can generate a diverse set of explanations, compared to
previous methods that only learn the maximum reward sample. We demonstrate
XInsight by generating explanations for GNNs trained on two graph
classification tasks: classifying mutagenic compounds with the MUTAG dataset
and classifying acyclic graphs with a synthetic dataset that we have open-
sourced. We show the utility of XInsight’s explanations by analyzing the
generated compounds using QSAR modeling, and we find that XInsight generates
compounds that cluster by lipophilicity, a known correlate of mutagenicity.
Our results show that XInsight generates a distribution of explanations that
uncovers the underlying relationships demonstrated by the model. They also
highlight the importance of generating a diverse set of explanations, as it
enables us to discover hidden relationships in the model and provides valuable
guidance for further analysis.

###### Keywords:

Explainable AI Graph Neural Networks GFlowNets

##  1 Introduction

Graph neural networks (GNNs) have emerged as a popular and effective machine
learning algorithm for modeling structured data, particularly graph data. As
GNNs continue to gain popularity, there is an increasing need for explainable
GNN algorithms. Explainable AI refers to machine learning algorithms that can
provide understandable and interpretable results. Explainable AI algorithms
have the ability to uncover hidden relationships or patterns that deep
learning models use in making their decisions. This means that researchers can
use these methods to understand why a model arrived at a certain decision. In
the case of GNNs, the need for explainability arises from the fact that they
are often used in applications where the decision-making process needs to be
transparent and easily understood by humans. For example, in the field of drug
discovery, GNNs are used to predict the efficacy of a drug by analyzing its
molecular structure [49]. In this case, it is crucial to understand how the
GNN arrived at its prediction, as it can have significant implications for
patient health and safety.

Explainable AI algorithms also uncover erroneous correlations in deep learning
models. For instance, in a study by Narla et al. [25], the researchers found
that their model had incorrectly learned that images with rulers were more
likely to be cancerous. The use of explainable AI methods helped them uncover
this error and highlighted the need for methods that can explain the
underlying relationships that deep learning models rely on to make
predictions.

In response to this need, we propose a GNN explainability algorithm,
eXplainable Insight (XInsight), that generates diverse model-level
explanations using Generative Flow Networks (GFlowNets) [3]. XInsight
represents the first application of GFlowNets to explain graph neural
networks. Unlike previous model-level algorithms, that only learn the maximum
reward sample, XInsight generates objects with probabilities proportional to a
reward. We demonstrate the effectiveness of XInsight by applying it to GNNs
trained on two graph classification tasks: classifying mutagenic compounds
with the MUTAG dataset and classifying acyclic graphs with a synthetic
dataset. In our experiments, we demonstrate that XInsight’s explanations for
the MUTAG dataset [24] can be analyzed using data mining techniques and QSAR
[14] modeling to uncover hidden relationships in the model. For instance, when
analyzing the compounds generated by XInsight, we found that they clustered by
lipophilicity, which is a known correlate of mutagenicity. Our results
demonstrate that XInsight generates a distribution of explanations that
enables the discovery of hidden relationships in the model.

The key contributions of this paper are summarized below:

  1. (i)

We proposed eXplainable Insight (XInsight), an explainability algorithm for
Graph Neural Networks (GNNs) that uses GFlowNets to generate a distribution of
model explanations.

  2. (ii)

We applied XInsight to explain two classification tasks, one of which was a
newly open-sourced synthetic dataset, and the other was a real-world molecular
compound dataset.

  3. (iii)

We analyzed XInsight’s generated explanations using a clustering method and
chemical analysis tool, which helped us to discover important underlying
patterns and relationships of the examined model.

##  2 Related Work

###  2.1 Graph Neural Networks

Graph neural networks (GNNs) have emerged as a popular deep learning technique
to model structured data that can be represented as graphs. Unlike traditional
neural networks that operate on structured data like images and sequences,
GNNs operate on non-Euclidean data, such as social networks [9, 34], chemical
molecules [5, 12, 11, 49], and 3D point clouds [10, 31]. GNNs typically use a
message-passing approach [12], where the feature representations of nodes,
edges, and the overall graph are iteratively updated by aggregating the
features of their neighbors and combining them with the learned features from
the previous step. This message-passing process is repeated for a fixed number
of iterations or until convergence. Expanding upon traditional message-passing
GNNs, many other GNN architectures have been proposed, such as Graph
Convolutional Networks (GCNs) [48] that use convolutional operations similar
to Euclidean Convolutional Neural Networks, Graph Isomorphism Networks (GINs)
[41] that employ multilayer perceptrons to aggregate neighboring features, and
Graph Attention Networks (GATs) [36] that apply an attention mechanism to
weigh contributions of neighboring nodes/edges based on their importance. With
the development of GNNs, we can now model and make predictions based on
structured data in a way that was not possible before.

###  2.2 Explaining Graph Neural Networks

Graph neural networks (GNNs) are widely used in various domains such as drug
discovery [5, 12, 11, 49], recommendation systems [43, 40, 39], and medical
diagnosis [1, 19, 18]. However, as with other machine learning models, GNNs
are often considered to be ‘black boxes’, providing little insight into how
they make predictions. Therefore, explainable AI algorithms for GNNs have
gained increasing attention in recent years.

There are several approaches to developing explainable GNN algorithms that can
conveniently be categorized as instance-level and model-level approaches.
Instance-level algorithms provide explanations for individual predictions of
the GNN and include methods that utilize the gradients of the features to
determine input importance, such as sensitivity analysis, Guided BP, and Grad-
CAM [2, 33, 30], perturb inputs to observe changes in output as in
GNNExplainer and PGExplainer [42, 20], and learn relationships between the
input and its neighbors using surrogate models [15, 38]. While there are
several instance-level explainability methods for GNNs, there is still a lack
of effective model-level explainability methods [46].

Model-level explanations help identify how the GNN approaches the task at
hand, and can reveal patterns and structures that may not be immediately
evident from the graph data alone. They also help identify when a model is not
performing well on the given task, or when it is exhibiting unwanted behavior.
Outside of the graph-learning world, input optimization is a popular model-
level approach for image classification models, where the goal is to generate
an image that maximizes the predicted class label [27, 26, 21, 8, 32, 28]. In
contrast, model-level explanations for GNNs have received relatively less
attention. One of the most prominent model-level explainability methods for
GNNs is XGNN (eXplainable Graph Neural Networks) [45]. XGNN leverages
reinforcement learning techniques to generate graphs that provide insights
into how the GNN is making predictions. XGNN generates a graph explanation
that maximizes a target prediction, thereby revealing the optimized class
pattern learned by the model.

To gain more insight into the model, it is often necessary to analyze a
diverse distribution of examples that cover different scenarios and edge
cases. Furthermore, generating a distribution of explanations opens the door
to applying statistical analysis and data mining techniques, such as
dimensionality reduction or t-tests, to uncover hidden relationships in the
data. For instance, in this paper we use dimensionality techniques to uncover
clusters within XInsight explanations. When then used these clusters to verify
that the model correctly learned a known correlation within the data.

###  2.3 XGNN

XGNN, which stands for eXplainable Graph Neural Networks, is a novel model-
level explainability framework introduced by Yuan et al. in 2020 [45]. The
goal of XGNN is to generate a graph that maximizes a specific target class of
a graph classification model. XGNN employs a reinforcement learning approach
to iteratively build a graph using actions that add nodes or edges to the
graph at each time step. During each time step, the model calculates the
reward based on the probability of the target class, which encourages the
algorithm to select actions that generate graphs of a particular class. This
process is repeated until the model converges or until a maximum number of
time steps is reached.

Like Graph Convolutional Policy Networks [44], XGNN learns a generator model
using a policy gradient. The generator produces a graph that contains patterns
that maximize the target class in question. In contrast to instance-level
explainability methods that identify subgraphs that contribute to the model’s
output, XGNN focuses on the entire graph and the relationships between its
nodes and edges. XGNN is currently the only model-level explanation method
that has been proposed for GNNs, according to a recent survey [46].

While XGNN is a powerful model-level explainability method for GNNs, it
generates a single maximum reward explanation, which limits its ability to
explain the full extent of the model’s behavior. XGNN is also limited in its
utility to discover hidden insights related to the classification task due to
the inability to perform a more detailed analysis of the explanations, such as
clustering. Due to these limitations, there is no way of directly comparing
XGNN to techniques that generate a distribution of explanations, such as
XInsight.

###  2.4 GFlowNets

Generative Flow Networks (GFlowNets) are a type of generative model that
generate a diverse set of objects by iteratively sampling actions proportional
to a reward function [3] [4]. The objective of GFlowNets is to learn to sample
from a distribution of diverse and high-reward samples instead of generating a
single sample to maximize a reward function. GFlowNets can be viewed as Markov
Decision Processes (MDP) represented by a directed acyclic graph (DAG), where
the edges represent the actions that can be taken in the states. The flows
coming into a state represent the actions that can be taken to reach that
state, while the flows leaving a state represent the actions that can be taken
in that state to reach the next state. The DAG is traversed iteratively by
sampling flows, which generates a flow trajectory that ends when a terminal
state is reached. The flow entering a terminal state is the total flow of the
trajectory and is equal to the reward function assigned to that state.

####  2.4.1 Trajectory Balance Objective

In [22], Malkin et al. introduced the Trajectory Balance Constraint, shown in
Equation 1, which ensures that the flow of the trajectory leading to a state
is equal to the flow of the trajectory leaving that state and terminating at a
terminal state. Satisfying this constraint allows the GFlowNet to sample
objects with probability proportional to its reward.

$Z\prod_{t}P_{F}(s_{t+1}|s_{t})=R(\tau)\prod_{t}P_{B}(s_{t}|s_{t+1})$ (1)

where $Z$ is the ‘total flow’. The right side of Equation 1 represents the
fraction of the total reward going through the trajectory, while the left
represents the fraction of the total flow going through the trajectory. This
constraint can be turned into the Trajectory Balance Objective [22] for
training a GFlowNet, shown below:

$L_{TB}(\tau)=\left(\log\frac{Z\prod_{t}P_{F}(s_{t+1}|s_{t})}{R(\tau)\prod_{t}P_{B}(s_{t}|s_{t+1})}\right)^{2}$
(2)

####  2.4.2 Applications of GFlowNets

GFlowNets have been applied to many generative applications, including
molecular sequence generation [3, 16, 22] and MNIST image generation [47]. And
due to their ability to generate diverse samples, GFlowNets trained to
generate model explanations, as in XInsight, provide the machine learning user
a greater breadth of human-readable explanations of what their models are
learning from the data.

##  3 eXplainable Insight (XInsight)

###  3.1 Explaining Graph Neural Networks

Graph classification networks can be difficult for humans to interpret since
graph structures can be less intuitive to humans compared to visual features
which humans are naturally equipped to interpret. Therefore when seeking to
understand a graph classification model, a quality explainability algorithm
should take advantage of the natural pattern matching capabilities of its
human users by producing concise explanations that highlight patterns that are
easily interpreted by humans. To make it even easier for its users, a quality
explainability algorithm should produce a distribution of explanations in
order to provide the user with multiple perspectives into the model; however,
most algorithms to date lack one or both of these qualities.

XInsight not only produces concise explanations that highlight important
patterns but also produces a distribution of explanations that allows the user
to develop a more robust understanding of what the examined model is learning
from the data. XInsight trains a GFlowNet to generate a diverse set of model-
explanations for a graph classification model. The explanations that XInsight
generates highlight general patterns that the classification model attributes
to specified target class in question.

In the context of model explanations as a whole, the explanations that
XInsight produces are particularly useful for discovering relationships within
the trained model. For example, they can help determine if a model incorrectly
associates an artifact in the data with the target class, like rulers with
skin cancer as discussed in [25]. XInsight empowers users to do this by
generating a distribution of explanations, which can then be passed through
traditional data mining techniques, such as clustering, to uncover what the
model is learning from the data.

###  3.2 Generating Graphs with XInsight

XInsight employs a GFlowNet that it is trained to generate graphs with
probabilities proportional to their likelihood of belonging to a target class.
Specifically, the GFlowNet generates a graph by iteratively sampling actions
that determine whether to add a new node or edge to the existing structure. It
is important to note that the likelihood of a sample belonging to a particular
class is defined by the trained model that is being explained. Therefore, the
distribution of generated samples is dependent upon the trained model and not
the true class distribution, which in the context of explaining a trained
model is desirable since the goal is to understand the model itself.

####  3.2.1 Action Space

The action space, $\mathcal{A}$, is split into two flows: the first selecting
a starting node and the second selecting the ending node. The starting node is
selected from the set of nodes $N$ in the current incomplete graph $G_{t}$.
The ending node is selected from the union of the same $\mathcal{N}$,
excluding the starting node and a set of building blocks $\mathcal{B}$.
Together, the starting and ending nodes form the combined action
$\mathcal{A}(n_{s},n_{e})$ sampled from the forward flow $P_{F}$. Taking this
action generates a new graph $G_{t+1}$ as shown below:

$G_{t+1}\sim P_{F}(\mathcal{A}(n_{s},n_{e})|G_{t})$ (3)

$p_{start}(n_{s}\in N|G_{t})$ (4)

$p_{end}(n_{e}\in N\cup\mathcal{B};n_{e}\neq n_{s}|G_{t})$ (5)

###  3.3 Proxy

The proxy $f$ in classical GFlowNets is used to generate the reward for a
generated object. For example, in [3] Bengio et al. used a pretrained model as
their proxy to predict the binding energy of a generated molecule to a protein
target. In XInsight, we use the model to be explained as the proxy since the
generated objects are treated as explanations of the model.

####  3.3.1 Reward

The reward in XInsight guides the underlying GFlowNet to generate graphs that
explain the proxy. In XInsight, we define the reward as the proxy’s predicted
probability that the generated graph belongs to the target class $c$, as shown
in Equation 6. To encourage the generation of objects explaining the target
class, we define the reward to be zero if the generated object is classified
as the opposite class. In addition, we add a scalar multiplier $\alpha$ to
magnify the reward for the target class, where $\alpha>0$.

$R(G_{t})=\begin{cases}\alpha*softmax(f(G_{t}))&\text{if}\;argmax\\{f(G_{t})\\}=Target\;Class\\\
0&\text{if}\;argmax\\{f(G_{t})\\}\neq Target\;Class\end{cases}$ (6)

###  3.4 Training XInsight

We train XInsight using the trajectory balance objective, following [22]. We
define the trajectory balance objective for a complete graph $G$ generated
over a trajectory $\tau$ actions in Equation 7.

$L_{TB}(G)=\left(\log\frac{Z\prod_{t}^{\tau}P_{F}(G_{t+1}|G_{t})}{R(G_{t})\prod_{t}^{\tau}P_{B}(G_{t}|G_{t+1})}\right)^{2}$
(7)

The training loop consists of sampling trajectories (i.e. generating graphs),
calculating forward and backward flows and the reward, and updating the
underlying GFlowNet parameters until convergence. We highlight the in-depth
steps of XInsight’s training loop in Algorithm 1.

For every epoch in the training loop, we start by initializing the GFlowNet
and creating an initial graph $G_{0}$. Then we generate a graph by iteratively
sampling actions from the forward policy $P_{F}$ that add nodes or edges to
the graph at each step $G_{t}$. Once a trajectory is complete, either by the
reaching the $MAX\\_ACTIONS$ limit or by sampling a $stop$ action, the reward
is computed for $G_{t}$ using the $Proxy$. Finally, we calculate the
trajectory balance loss, update the GFlowNet’s parameters and repeat.

Algorithm 1 XInsight Training Loop

Input: $EPOCHS$, $Proxy(\cdot)$, $TARGET\\_CLASS$, $MAX\\_ACTIONS$

$XI(\cdot;\theta)\leftarrow$ GFlowNet

for epoch in $EPOCHS$ do

$actions\leftarrow 0$

$G_{t}\leftarrow G_{0}$ $\triangleright$ Initialize new graph

$\tau\leftarrow\emptyset+\\{G_{t}\\}$

repeat

$P_{F},P_{B}\leftarrow XI(G_{t};\theta)$ $\triangleright$ Generate flows

$n_{s},n_{e}\sim P_{F}$ $\triangleright$ Sample start & end node

if $n_{s}=stop$ then

$STOP\leftarrow True$ $\triangleright$ Stop if stop action sampled

end if

$G_{new}\leftarrow$ $\mathcal{T}(n_{s},n_{e})$ $\triangleright$ Add node/edge

$P_{F},P_{B}\leftarrow XI(G_{new};\theta)$ $\triangleright$ Recompute flows

$G_{t}=G_{new}$

$\tau\leftarrow\tau+\\{G_{t}\\}$ $\triangleright$ Append $G_{t}$ to trajectory

$actions++$

until $actions>MAX\\_ACTIONS$ or $STOP$

$Reward=softmax(Proxy(G_{t}))_{TARGET\\_CLASS}$ $\triangleright$ Calculate
reward

$\theta\leftarrow\theta-\eta\nabla Loss_{TB}(Reward,log_{Z},\tau)$
$\triangleright$ Update parameters

end for

##  4 Experiment Design

###  4.1 Datasets

The Acyclic Graph dataset includes 2405 synthetically generated graphs labeled
as either acyclic or cyclic. We generated graphs using graph generation
functions from the NetworkX software package [13]. To improve the diversity of
the dataset, we trained a GFlowNet with a brute-force cycle checker as a
reward function to generate acyclic and cyclic graphs to add to the dataset.
The code used to generate this dataset can be found in [17].

The MUTAG dataset [24], included in Pytorch Geometric, contains 188 graphs
representing chemical compounds used in an Ames test on the S. Typhimurium
TA98 bacteria with the goal of measuring the mutagenic effects of the
compound. This dataset was used in a study to measure the correlation between
the chemical structure of the compounds and their mutagenic activity [7]. The
nodes and edges in the graphs in MUTAG represent 7 different atoms (Carbon,
Nitrogen, Oxygen, Fluorine, Iodine, Chlorine, and Bromine) and their chemical
bonds. In the graph learning community, the dataset is used as a benchmark
dataset for graph classification models labeling each graph as ‘Mutagenic’ or
‘Non-Mutagenic’.

###  4.2 Verifying XInsight’s Generative Abilities Setup

To validate that XInsight can generate graphs belonging to a target class, we
trained XInsight to generate acyclic graphs because of their simple and human-
interpretable form. For the proxy, we trained a graph convolutional neural
network (GCN) to classify acyclic graphs using the Acyclic Graph dataset and
node degree as the node features, achieving $99.58\%$ accuracy. This GCN is
composed of three graph convolutional layers (GCNConv) with 32, 48, 64
filters, respectively, a global mean pooling layer, and two fully connected
layers with 64 and 32 hidden units. We also used dropout and the ReLU
activation function. The GFlowNet was also a GCN made up of three GCNConv
layers with 32, 64, and 128 filters, two fully connected layers with 128 and
512 hidden units, and a scalar parameter representing $log(Z)$ from the reward
function, see Section 3.3.1. The building blocks used for action selection
consisted of a single node of degree 1.

###  4.3 Revealing MUTAG Relationships Setup

Due to their highly qualitative nature, there is no established method for
evaluating model-level explanation methods for graphs, particularly for
methods that generate a distribution of explanations. Despite this barrier, we
demonstrate XInsight’s explanatory abilities by applying it to the task of
knowledge discovery within the mutagenic compound domain. Particularly, we
evaluated XInsight for its ability to uncover meaningful relationships learned
by a graph neural network trained to classify mutagenic compounds and verify
that these relationships exist in the ground truth data.

Figure 1: Generated graphs (8 with cycles and 8 without cycles) to verify
XInsight’s ability to generate graphs of a specified target class.

For the proxy, we trained a graph convolutional neural network (GCN) to
classify mutagenic compounds using the MUTAG dataset. Following [45], we used
node features which were seven-dimensional one-hot encoded vectors encoding
the seven different atoms in the dataset. The architecture of this GCN
mirrored that used for the Acyclic classification task, with the addition of
another GCNConv layer with 64 filters and LeakyReLU as the activation
function. With this architecture, we achieved $89\%$ accuracy on the MUTAG
classification task. The GFlowNet architecture was also the same as the one
used for the Acyclic classification task, except we used seven nodes
representing the different atoms as the building blocks. The initial graph
$G_{0}$, used in training the GFlowNet, was set to a single node graph with
the feature value set to carbon, as in [45].

##  5 Results

###  5.1 Verifying XInsight’s Generative Abilities Using The Acyclic Dataset

To verify that XInsight is capable of generating graphs of a particular class
defined by a classification model, we conducted an experiment in which we
trained XInsight to generate graphs from a graph convolutional network,
previously trained on the Acyclic Graphs dataset. This synthetic dataset
contains two classes, acyclic and cyclic, and is described in detail in
Section 4.1.

Following XInsight training, we generated a distribution of 16 graphs (8
acyclic and 8 cyclic), shown in Figure 1. The results of the experiment
indicate that XInsight is indeed capable of generating acyclic graphs, which
is consistent with the nature of the dataset. This provides evidence that
XInsight is capable of generating graphs guided by the predictions of a simple
classification model.

Figure 2: Distribution of explanations for the Mutagenic classifier generated
by the trained XInsight model, with MUTAG class probabilities according to the
trained proxy. Colors represent UMAP clusters of graph embeddings for the
generated compounds. Blue: Group 1, Red: Group 2, Yellow: Group 3, Purple:
Group 4, Orange: Group 5.

###  5.2 Revealing Distinct Relationships Learned By The MUTAG Classifier

####  5.2.1 Generating Explanations

In our second experiment, we trained XInsight to explain a GCN trained on the
MUTAG dataset. Our objective was to uncover hidden patterns and relationships
that the trained GCN classifier associates with the mutagenic class. To
achieve this, we used XInsight to generate a distribution of 16 compounds,
illustrated in Figure 2, and then fed the generated graphs through the trained
GCN to produce graph embeddings. In order to visualize the 32-dimensional
graph embeddings we used the UMAP dimensionality reduction algorithm, which
preserves global and local structure of the data [23], to project the
embeddings onto a 2-dimensional plane. From this visualization, we identified
five distinct groupings of compounds that we hypothesize group by an unknown
factor related to mutagenicity. To uncover the factor behind these groupings,
we continued our analysis by analyzing the chemical properties of the
generated compounds using QSAR modeling [14].

Figure 3: Generated graph embeddings projected onto 2-dimensional plane using
UMAP. UMAP was fit using the cosine similarity metric, 2 neighbors, and a
minimum distance of 0.1.

####  5.2.2 Knowledge Discovery

Quantitative Structure-Activity Relationship (QSAR) modeling is a well-
established methodology that is used to differentiate between mutagenic and
non-mutagenic compounds, which have been identified by the Ames test [14].
Various features of typical drugs, such as lipophilicity, polarizability,
hydrophilicity, electron density, and topological analysis, have been utilized
in the literature to establish QSAR models for mutagenicity [35]. Among these
features, lipophilicity has been identified as a major contributing factor for
mutagenicity, as it facilitates the penetration of lipophilic compounds
through cellular membranes.

To establish a relationship between the clusters of compounds generated by
XInsight and their mutagenicity, we calculated the lipophilicity of all the
generated structures using the XLOGP3 method [6], samples shown in 4. This
method has been shown to provide reliable results that are comparable to those
obtained using the calculation of the octanol water partition coefficient for
$logP$ [37]. It is essential to note that we added hydrogens to O (-OH) and N
(-NH2) groups to represent the aqueous environment within the human body,
since hydrogen atoms were not included in the building blocks for the MUTAG
dataset.

Figure 4: Lipophilicity calculations for 10 of the clustered compounds
generated by XInsight using the XLOGP3 method. Surface mesh and 3 dimensional
structures were generated by Chimera visualization software [29].

In Figure 5 we see that in general the lipophilicity value is higher for the
generated mutagenic compounds compared to the non-mutagenic compounds. We
observed that the highest lipophilicity was associated with compounds of Group
4 (purple), followed by those of Group 2 (red) and Group 3 (yellow). The
purple cluster exhibited significant differences in lipophilicity when
compared to the red and yellow clusters, which explains why purple is a
distinct cluster. However, groups 1 (blue) and 5 (orange) showed lower levels
of lipophilicity values but still exhibited significant differences. Thus,
lipophilicity appears to be a factor related to the mutagenicity of these
compounds.

####  5.2.3 Knowledge Verification

To verify that the discovered relationship between lipophilicity and
mutagenicity is valid, we randomly sampled 32 compounds from the MUTAG
dataset, with 16 compounds for each class, and calculated lipophilicity for
each. We then performed a t-test to determine whether there is a statistically
significant difference in lipophilicity for mutagenic and non-mutagenic
compounds. In Table 1 we show a statistically significant difference between
the mean lipophilicity values for the mutagenic and non-mutagenic classes,
thus verifying that the relationship uncovered using XInsight’s generated
distribution is a true relationship exhibited in the training data.
Additionally, this shows how XInsight can be used to discover knowledge about
the model.

Figure 5: XLOGP3 Lipophilicity values for UMAP clustered compounds colored by
group with classified labels, Mutagenic: M, Non-Mutagenic: NM.

####  5.2.4 Further Insights

The distribution of explanations provided us with another significant insight,
which is that the compounds in Group 1 (blue) and Group 5 (orange) have low
lipophilicity, even though Group 1 is classified as mutagenic and Group 5 as
non-mutagenic. This raises two possible assumptions: first, the classifier
might be incorrectly classifying compounds that are similar to those in Groups
1 as mutagenic, or second, there might be another underlying factor that is
responsible for the hydrophilic nature of these compounds. Furthermore, as
mentioned earlier, lipophilicity is not the only factor determining the
mutagenicity of the compounds. To explain the clustering of the Group 1,
additional quantum-mechanical calculations are necessary.

This analysis underscores the considerable advantages of generating a
distribution of explanations, as opposed to a single explanation that
maximizes the reward. By having a distribution of explanations, we can uncover
hidden insights into what the classification model associates with the target
class. Without a distribution of explanations, we are restricted in the types
of analysis we can perform to more effectively explain the model being
examined.

Table 1: t-test results showing a statistically significant difference between Mutagenic and Non-Mutagenic lipophilicity values for 32 randomly sampled compounds from the MUTAG dataset, $\alpha=0.05$. | Mutagenic | Non-Mutagenic |
---|---|---|---
Mean | 4.1444 | 2.1750 |
Variance | 0.6812 | 1.3963 |
t-statistic | -5.2917 |
p-value | 0.00001022 |

##  6 Conclusion

In this paper, we proposed XInsight, an explainability algorithm for graph
neural networks, that generates a diverse set of model explanations using
Generative Flow Networks. Our approach is designed to provide human-
understandable explanations for GNNs that uncover the hidden relationships of
the model. We demonstrated the effectiveness of XInsight by generating
explanations for GNNs trained for two graph classification tasks, including
the classification of acyclic graphs and the classification of mutagenic
compounds. Our results indicate that XInsight uncovers underlying
relationships and patterns demonstrated by the model, and provides valuable
guidance for further analysis.

Our findings emphasize the importance of generating a diverse set of
explanations, as it enables us to discover hidden relationships in the model
and identify important features in the data. Furthermore, we show that the
generated explanations from XInsight can be used in combination with data
mining and chemical analysis methods to uncover relationships within the
model. For instance, we analyzed the generated compounds from XInsight using
QSAR modeling, and we observe that XInsight generates compounds that cluster
by Lipophilicity, a known correlate of mutagenicity.

Overall, XInsight provides a promising direction for developing explainable AI
algorithms for graph-based applications, with implications for many real-world
domains. We believe that XInsight has the potential to make a significant
impact in various real-world domains, particularly in high-stakes
applications, such as drug discovery, where interpretability and transparency
are essential.

## References

  * [1] Ahmedt-Aristizabal, D., Armin, M.A., Denman, S., Fookes, C., Petersson, L.: Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future. Sensors 21(14), 4758 (Jul 2021). https://doi.org/10.3390/s21144758, https://www.mdpi.com/1424-8220/21/14/4758
  * [2] Baehrens, D., Schroeter, T., Harmeling, S., Kawanabe, M., Hansen, K., Mueller, K.R.: How to Explain Individual Classification Decisions (Dec 2009). https://doi.org/10.48550/arXiv.0912.1128, http://arxiv.org/abs/0912.1128, arXiv:0912.1128 [cs, stat]
  * [3] Bengio, E., Jain, M., Korablyov, M., Precup, D., Bengio, Y.: Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation (Nov 2021). https://doi.org/10.48550/arXiv.2106.04399, http://arxiv.org/abs/2106.04399, arXiv:2106.04399 [cs]
  * [4] Bengio, Y., Lahlou, S., Deleu, T., Hu, E.J., Tiwari, M., Bengio, E.: GFlowNet Foundations (Aug 2022). https://doi.org/10.48550/arXiv.2111.09266, arXiv:2111.09266 [cs, stat]
  * [5] Bongini, P., Bianchini, M., Scarselli, F.: Molecular graph generation with Graph Neural Networks. Neurocomputing 450, 242–252 (Aug 2021). https://doi.org/10.1016/j.neucom.2021.04.039, http://arxiv.org/abs/2012.07397, arXiv:2012.07397 [cs, q-bio, stat]
  * [6] Cheng, T., Zhao, Y., Li, X., Lin, F., Xu, Y., Zhang, X., Li, Y., Wang, R., Lai, L.: Computation of Octanol-Water Partition Coefficients by Guiding an Additive Model with Knowledge. Journal of Chemical Information and Modeling 47(6), 2140–2148 (Nov 2007). https://doi.org/10.1021/ci700257y, https://pubs.acs.org/doi/10.1021/ci700257y
  * [7] Debnath, A.K., Lopez De Compadre, R.L., Debnath, G., Shusterman, A.J., Hansch, C.: Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry 34(2), 786–797 (Feb 1991). https://doi.org/10.1021/jm00106a046
  * [8] Dosovitskiy, A., Brox, T.: Inverting Visual Representations with Convolutional Networks. In: 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 4829–4837. IEEE, Las Vegas, NV, USA (Jun 2016). https://doi.org/10.1109/CVPR.2016.522
  * [9] Fan, W., Ma, Y., Li, Q., He, Y., Zhao, E., Tang, J., Yin, D.: Graph Neural Networks for Social Recommendation (Nov 2019). https://doi.org/10.48550/arXiv.1902.07243, http://arxiv.org/abs/1902.07243, arXiv:1902.07243 [cs]
  * [10] Gao, J., Sun, C., Zhao, H., Shen, Y., Anguelov, D., Li, C., Schmid, C.: VectorNet: Encoding HD Maps and Agent Dynamics from Vectorized Representation (May 2020). https://doi.org/10.48550/arXiv.2005.04259, arXiv:2005.04259 [cs, stat]
  * [11] Gasteiger, J., Groß, J., Günnemann, S.: Directional Message Passing for Molecular Graphs (Apr 2022). https://doi.org/10.48550/arXiv.2003.03123, http://arxiv.org/abs/2003.03123, arXiv:2003.03123 [physics, stat]
  * [12] Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural Message Passing for Quantum Chemistry (Jun 2017). https://doi.org/10.48550/arXiv.1704.01212, arXiv:1704.01212 [cs]
  * [13] Hagberg, A., Swart, P., S Chult, D.: Exploring network structure, dynamics, and function using networkx (1 2008), https://www.osti.gov/biblio/960616
  * [14] Honma, M., Kitazawa, A., Cayley, A., Williams, R.V., Barber, C., Hanser, T., Saiakhov, R., Chakravarti, S., Myatt, G.J., Cross, K.P., Benfenati, E., Raitano, G., Mekenyan, O., Petkov, P., Bossa, C., Benigni, R., Battistelli, C.L., Giuliani, A., Tcheremenskaia, O., DeMeo, C., Norinder, U., Koga, H., Jose, C., Jeliazkova, N., Kochev, N., Paskaleva, V., Yang, C., Daga, P.R., Clark, R.D., Rathman, J.: Improvement of quantitative structure–activity relationship (QSAR) tools for predicting Ames mutagenicity: outcomes of the Ames/QSAR International Challenge Project. Mutagenesis 34(1), 3–16 (Mar 2019). https://doi.org/10.1093/mutage/gey031, https://academic.oup.com/mutage/article/34/1/3/5142926
  * [15] Huang, Q., Yamada, M., Tian, Y., Singh, D., Yin, D., Chang, Y.: GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks (Sep 2020). https://doi.org/10.48550/arXiv.2001.06216, http://arxiv.org/abs/2001.06216, arXiv:2001.06216 [cs, stat]
  * [16] Jain, M., Bengio, E., Garcia, A.H., Rector-Brooks, J., Dossou, B.F.P., Ekbote, C., Fu, J., Zhang, T., Kilgour, M., Zhang, D., Simine, L., Das, P., Bengio, Y.: Biological Sequence Design with GFlowNets (Mar 2022), https://arxiv.org/abs/2203.04115v2
  * [17] Laird, E.: Acyclic graph dataset. https://github.com/elilaird/acyclic-graph-dataset
  * [18] Li, Y., Qian, B., Zhang, X., Liu, H.: Graph Neural Network-Based Diagnosis Prediction. Big Data 8(5), 379–390 (Oct 2020). https://doi.org/10.1089/big.2020.0070, https://www.liebertpub.com/doi/10.1089/big.2020.0070
  * [19] Lu, H., Uddin, S.: A weighted patient network-based framework for predicting chronic diseases using graph neural networks. Scientific Reports 11(1), 22607 (Nov 2021). https://doi.org/10.1038/s41598-021-01964-2, https://www.nature.com/articles/s41598-021-01964-2
  * [20] Luo, D., Cheng, W., Xu, D., Yu, W., Zong, B., Chen, H., Zhang, X.: Parameterized explainer for graph neural network. In: Proceedings of the 34th International Conference on Neural Information Processing Systems. NIPS’20, Curran Associates Inc., Red Hook, NY, USA (2020)
  * [21] Mahendran, A., Vedaldi, A.: Understanding deep image representations by inverting them. In: 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 5188–5196. IEEE, Boston, MA, USA (Jun 2015). https://doi.org/10.1109/CVPR.2015.7299155
  * [22] Malkin, N., Jain, M., Bengio, E., Sun, C., Bengio, Y.: Trajectory balance: Improved credit assignment in GFlowNets (Oct 2022). https://doi.org/10.48550/arXiv.2201.13259, http://arxiv.org/abs/2201.13259, arXiv:2201.13259 [cs, stat]
  * [23] McInnes, L., Healy, J., Melville, J.: UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (Sep 2020). https://doi.org/10.48550/arXiv.1802.03426, arXiv:1802.03426 [cs, stat]
  * [24] Morris, C., Kriege, N.M., Bause, F., Kersting, K., Mutzel, P., Neumann, M.: TUDataset: A collection of benchmark datasets for learning with graphs (Jul 2020). https://doi.org/10.48550/arXiv.2007.08663, arXiv:2007.08663 [cs, stat]
  * [25] Narla, A., Kuprel, B., Sarin, K., Novoa, R., Ko, J.: Automated Classification of Skin Lesions: From Pixels to Practice. Journal of Investigative Dermatology 138(10), 2108–2110 (Oct 2018). https://doi.org/10.1016/j.jid.2018.06.175, https://linkinghub.elsevier.com/retrieve/pii/S0022202X18322930
  * [26] Nguyen, A., Clune, J., Bengio, Y., Dosovitskiy, A., Yosinski, J.: Plug & Play Generative Networks: Conditional Iterative Generation of Images in Latent Space. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 3510–3520. IEEE, Honolulu, HI (Jul 2017). https://doi.org/10.1109/CVPR.2017.374
  * [27] Nguyen, A., Yosinski, J., Clune, J.: Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In: 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 427–436. IEEE, Boston, MA, USA (Jun 2015). https://doi.org/10.1109/CVPR.2015.7298640
  * [28] Olah, C., Mordvintsev, A., Schubert, L.: Feature Visualization. Distill 2(11), 10.23915/distill.00007 (Nov 2017). https://doi.org/10.23915/distill.00007
  * [29] Pettersen, E.F., Goddard, T.D., Huang, C.C., Couch, G.S., Greenblatt, D.M., Meng, E.C., Ferrin, T.E.: UCSF Chimera?A visualization system for exploratory research and analysis. Journal of Computational Chemistry 25(13), 1605–1612 (Oct 2004). https://doi.org/10.1002/jcc.20084, https://onlinelibrary.wiley.com/doi/10.1002/jcc.20084
  * [30] Selvaraju, R.R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., Batra, D.: Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization. International Journal of Computer Vision 128(2), 336–359 (Feb 2020). https://doi.org/10.1007/s11263-019-01228-7, http://arxiv.org/abs/1610.02391, arXiv:1610.02391 [cs]
  * [31] Sheng, Z., Xu, Y., Xue, S., Li, D.: Graph-Based Spatial-Temporal Convolutional Network for Vehicle Trajectory Prediction in Autonomous Driving. IEEE Transactions on Intelligent Transportation Systems 23(10), 17654–17665 (Oct 2022). https://doi.org/10.1109/TITS.2022.3155749, http://arxiv.org/abs/2109.12764, arXiv:2109.12764 [cs]
  * [32] Simonyan, K., Vedaldi, A., Zisserman, A.: Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps (Apr 2014). https://doi.org/10.48550/arXiv.1312.6034, arXiv:1312.6034 [cs]
  * [33] Springenberg, J.T., Dosovitskiy, A., Brox, T., Riedmiller, M.: Striving for Simplicity: The All Convolutional Net (Apr 2015). https://doi.org/10.48550/arXiv.1412.6806, http://arxiv.org/abs/1412.6806, arXiv:1412.6806 [cs]
  * [34] Tan, Q., Liu, N., Hu, X.: Deep Representation Learning for Social Network Analysis. Frontiers in Big Data 2, 2 (Apr 2019). https://doi.org/10.3389/fdata.2019.00002, https://www.frontiersin.org/article/10.3389/fdata.2019.00002/full
  * [35] Tuppurainen, K.: Frontier orbital energies, hydrophobicity and steric factors as physical qsar descriptors of molecular mutagenicity. A review with a case study: MX compounds. Chemosphere 38(13), 3015–3030 (Jun 1999). https://doi.org/10.1016/S0045-6535(98)00503-7, https://linkinghub.elsevier.com/retrieve/pii/S0045653598005037
  * [36] Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y.: Graph Attention Networks (Feb 2018). https://doi.org/10.48550/arXiv.1710.10903, arXiv:1710.10903 [cs, stat]
  * [37] Viana, R.D.S., Aquino, F.L.T.D., Barreto, E.: Effect of trans -cinnamic acid and p -coumaric acid on fibroblast motility: a pilot comparative study of in silico lipophilicity measure. Natural Product Research 35(24), 5872–5878 (Dec 2021). https://doi.org/10.1080/14786419.2020.1798664, https://www.tandfonline.com/doi/full/10.1080/14786419.2020.1798664
  * [38] Vu, M.N., Thai, M.T.: PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks (Oct 2020). https://doi.org/10.48550/arXiv.2010.05788, arXiv:2010.05788 [cs]
  * [39] Wang, X., He, X., Wang, M., Feng, F., Chua, T.S.: Neural Graph Collaborative Filtering. In: Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 165–174 (Jul 2019). https://doi.org/10.1145/3331184.3331267, http://arxiv.org/abs/1905.08108, arXiv:1905.08108 [cs]
  * [40] Wu, J., Wang, X., Feng, F., He, X., Chen, L., Lian, J., Xie, X.: Self-supervised Graph Learning for Recommendation. In: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 726–735 (Jul 2021). https://doi.org/10.1145/3404835.3462862, http://arxiv.org/abs/2010.10783, arXiv:2010.10783 [cs]
  * [41] Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How Powerful are Graph Neural Networks? (Feb 2019). https://doi.org/10.48550/arXiv.1810.00826, arXiv:1810.00826 [cs, stat] version: 3
  * [42] Ying, R., Bourgeois, D., You, J., Zitnik, M., Leskovec, J.: Gnnexplainer: Generating explanations for graph neural networks. In: Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc., Red Hook, NY, USA (2019)
  * [43] Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W.L., Leskovec, J.: Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 974–983 (Jul 2018). https://doi.org/10.1145/3219819.3219890, http://arxiv.org/abs/1806.01973, arXiv:1806.01973 [cs, stat]
  * [44] You, J., Liu, B., Ying, R., Pande, V., Leskovec, J.: Graph convolutional policy network for goal-directed molecular graph generation. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. p. 6412–6422. NIPS’18, Curran Associates Inc., Red Hook, NY, USA (2018)
  * [45] Yuan, H., Tang, J., Hu, X., Ji, S.: XGNN: Towards Model-Level Explanations of Graph Neural Networks. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 430–438. ACM, Virtual Event CA USA (Aug 2020). https://doi.org/10.1145/3394486.3403085
  * [46] Yuan, H., Yu, H., Gui, S., Ji, S.: Explainability in Graph Neural Networks: A Taxonomic Survey. IEEE Transactions on Pattern Analysis and Machine Intelligence pp. 1–19 (2022). https://doi.org/10.1109/TPAMI.2022.3204236, https://ieeexplore.ieee.org/document/9875989/
  * [47] Zhang, D., Malkin, N., Liu, Z., Volokhova, A., Courville, A., Bengio, Y.: Generative Flow Networks for Discrete Probabilistic Modeling (Feb 2022), https://arxiv.org/abs/2202.01361v2
  * [48] Zhang, H., Lu, G., Zhan, M., Zhang, B.: Semi-Supervised Classification of Graph Convolutional Networks with Laplacian Rank Constraints. Neural Processing Letters 54(4), 2645–2656 (Aug 2022). https://doi.org/10.1007/s11063-020-10404-7
  * [49] Zhang, Z., Chen, L., Zhong, F., Wang, D., Jiang, J., Zhang, S., Jiang, H., Zheng, M., Li, X.: Graph neural network approaches for drug-target interactions. Current Opinion in Structural Biology 73, 102327 (Apr 2022). https://doi.org/10.1016/j.sbi.2021.102327, https://linkinghub.elsevier.com/retrieve/pii/S0959440X2100169X


# Instantons and transseries of the Mathieu potential deformed by a
$\mathcal{PT}$-symmetry parameter

N. M. Alvarenga<EMAIL_ADDRESS>Current address: Instituto de Física,
Universidade de Brasília, 70910-900, Brasília, DF, Brazil Instituto de Física,
Universidade do Estado do Rio de Janeiro, 20550-013 Rio de Janeiro, RJ, Brazil
E. Cavalcanti<EMAIL_ADDRESS>Centro Brasileiro de Pesquisas Físicas/MCTI,
22290-180 Rio de Janeiro, RJ, Brazil  C. A. Linhares<EMAIL_ADDRESS>Instituto de Física, Universidade do Estado do Rio de Janeiro, 20550-013 Rio
de Janeiro, RJ, Brazil  J. A. Lourenço<EMAIL_ADDRESS>Departamento de
Ciências Naturais, Universidade Federal do Espírito Santo, 29932-540 São
Mateus, ES, Brazil  J. R. P. Mahon<EMAIL_ADDRESS>Instituto de Física,
Universidade do Estado do Rio de Janeiro, 20550-013 Rio de Janeiro, RJ, Brazil
F. Reis<EMAIL_ADDRESS>Departamento de Matemática Aplicada,
Universidade Federal do Espírito Santo, 29932-540 São Mateus, ES, Brazil

###### Abstract

We investigate the non-perturbative effects of a deformation of the Mathieu
differential equation consistent with $\mathcal{PT}$-symmetry. First, we
develop a connection between the non-Hermitian and Hermitian scenarios by a
reparameterization in the complex plane, followed by a restriction of the
$\mathcal{PT}$-deformation parameter. The latter is responsible for preserving
the information about $\mathcal{PT}$-symmetry when we choose to work in the
Hermitian scenario. We note that this factor is present in all non-
perturbative results and in the transseries representation of the deformed
Mathieu partition function that we have obtained. In quantum mechanics, we
found that the deformation parameter of $\mathcal{PT}$-symmetry has an effect
on the real instanton solution for the Mathieu deformed potential in the
Hermitian scenario. As its value increases, the non-Hermiticity factor makes
it smoother for the instanton to pass from one minimum to another, that is, it
modifies the instanton width. The explanation for this lies in the fact that
the height of the potential barrier decreases as we increase the value of the
deformation parameter. Its effect extends to the multi-instanton level and to
the bounce limit of an instanton-anti-instanton pair whose equation of motion
compares to the resistively shunted junction (RSJ) model.

##  I Introduction

The Mathieu equation is a special case of a linear second-order homogeneous
differential equation, which occurs in many applications in physics and
engineering. Historically, it is related to the investigations of the French
mathematician É. L. Mathieu on free oscillations of an elliptical membrane
[1]. Over time, many other applications have been developed and a large amount
of results on this subject have been collected [2]. The Mathieu equation
appears in several different situations in physics [3]. A few examples are:
electromagnetic and elastic wave equations with elliptical boundary conditions
(as in waveguides or resonators) [4]; motion of particles in alternated-
gradient focusing [5] or electromagnetic traps [6]; inverted pendulum;
parametric oscillators; motion of a quantum particle in a periodic potential
[7]; and eigenfunctions of quantum pendulum [8]. About ten years ago, the
Mathieu equation with a complex driven parameter was used to describe charge
carriers moving in a sinusoidally curved graphene [9]. Interesting resurgent
features of the Mathieu potential have been explored in the literature [10,
11, 12] from the analysis of divergent asymptotic series that arise when
expanding the Mathieu partition function, both perturbatively and non-
perturbatively.111The potential in Ref. [12] is a generalization that
interpolates between trigonometric (Mathieu) and hyperbolic forms.

Locating a point in space-time involves using a four-dimensional vector
$(x,y,z,t)$. The parity operator $\mathcal{P}$ affects the sign of the spatial
part of this four-vector, while the time-reversal operator $\mathcal{T}$
changes only the sign of its time component. Together, the total effect of
parity and time ($\mathcal{PT}$) reflection is to change the sign of all its
components, namely, $(x,y,z,t)\rightarrow(-x,-y,-z,-t)$. Furthermore, there is
another interesting effect when it comes to quantum mechanics, due to the fact
that both the position and momentum operators obey the Heisenberg algebra
($xp-px=i$). Although $\mathcal{P}$ keeps the Heisenberg algebra unchanged,
the application of $\mathcal{T}$ leads to a change in the momentum $p$ sign,
forcing the imaginary unit $i$ to change its sign to preserve the Heisenberg
algebra under $\mathcal{PT}$.222Wigner has shown [13] that, in quantum
mechanics, the time-reversal operator $\mathcal{T}$ changes the sign of the
imaginary number $i$. From this, we can assert that a Hamiltonian is
$\mathcal{PT}$-symmetric when the condition $V(\mathbf{x})=V^{*}(-\mathbf{x})$
is satisfied [14].

In textbook quantum mechanics, one requires the Hamiltonian operator to be
Hermitian in order to guarantee real eigenvalues. However, the space-time
reflection symmetry ($\mathcal{PT}$ symmetry) enables to obtain non-Hermitian
Hamiltonians that develop real eigenvalues [15]. This means that
$\mathcal{PT}$-symmetric systems can describe a physical model. There are many
experimental applications [16]. Furthermore, $\mathcal{PT}$-symmetric
Hamiltonians are suitable for investigating the boundary between open and
closed systems [17]. This is indicated by looking at the spectrum, in which we
can have a $\mathcal{PT}$-symmetric phase (where all energy levels are real)
and a $\mathcal{PT}$-broken phase (where some of the energy levels become
complex), which is controlled by some strain parameter in the Hamiltonian.
This change occurs because the $\mathcal{PT}$ operator is non-linear.
Therefore, although it commutes with the Hamiltonian, there is no guarantee
that they will share the same eigenstates. This richness has motivated a
multitude of physical applications in optics, superconductivity, microwave
cavity, lasers, electronic circuits, chaos, graphene, metamaterials etc., and
the research on the subject has experienced an overwhelming growth in recent
years [16].

In this paper, we explore non-perturbative effects of a deformation of the
Mathieu differential equation consistent with $\mathcal{PT}$-symmetry. The
aspects related to its spectrum and the transition from
$\mathcal{PT}$-unbroken to $\mathcal{PT}$-broken phases are studied in Ref.
[18].

The path to solve the Mathieu differential equation is to employ a
perturbation theory and obtain a perturbative series. However, as usual in
physics, the perturbative series are divergent [19, 20, 21]. When the series
is asymptotic, it is common to employ Borel summation to extract non-
perturbative information. However, a more difficult task is the reconstruction
of functions from divergent perturbative expansions, as it generates
incomplete information. This signals the need to include non-perturbative
instantons effects. Such divergence is related to the existence of
singularities in the Borel complex plane, usually also associated with
instantons [10, 21]. These are crucial part in the construction of
transseries, which are important manipulations of formal series that can
cancel out ambiguities [10, 11, 21, 12, 22, 23].

We start with the usual Hermitian case, in Sec. II, then move on to the
connection between Hermitian and non-Hermitian scenarios in Sec. III. In Sec.
IV we obtain the resurgent Mathieu partition fuction, and we construct the
instanton solution of the deformed Mathieu equation in Sec. V. In Sec. VI and
Sec. VII, we show applications of this formalism to the problems of a dilute
gas of deformed instantons.

##  II Usual Hermitian case

We start with the known Mathieu equation [24]

$\left\\{-\frac{d^{2}}{dz^{2}}+2q\cos(2z)\right\\}\psi(z)=a\psi(z),$ (1)

whose potential can be written as

$V_{U}(z)=\sin^{2}(z)$ (2)

by trivial trigonometric identities, for convenience. The following ordinary
integral

$Z_{U}(g)=\frac{1}{g\sqrt{\pi}}\int_{-\pi/2}^{\pi/2}dz\;\exp\left(-\frac{1}{g^{2}}\sin^{2}(z)\right)$
(3)

formally can be considered as a zero dimensional prototype of the semi-
classical partition function approach in path integrals. The purpose of this
section is to illustrate the methodology that one can use in order to write
the related transseries. This characterizes a zero dimensional prototype for
resurgence [25, 12, 10, 11]. Briefly, the saddle points and their associated
actions are calculated. The former are easily obtained by taking the
derivative of the potential and bringing the result to zero. Two values are
found, $z_{p}=0$ and $z_{np}=\pi/2$, which we call respectively perturbative
and non-perturbative saddles. In this zero dimensional prototype, we simply
substitute each saddle point in the expression of the potential (2) in order
to calculate their associated actions, resulting in $S_{p}=0$ and $S_{np}=1$.
Then comes the main task, which is the perturbative expansion around each
saddle of the partition function

$Z_{U}(g)=\frac{2}{g\sqrt{\pi}}\int_{0}^{\pi/2}dz\;\exp\left(-\frac{1}{g^{2}}\sin^{2}(z)\right).$
(4)

These elements can be inserted into the general structure of a transseries
[12, 11]. In this specific case, we notice that there are two saddles, so we
can write the transseries

$Z_{U}(g^{2})=\sigma_{p}\,e^{-S_{p}/g^{2}}\Phi_{p}(g^{2})+\sigma_{np}\,e^{-S_{np}/g^{2}}\Phi_{np}(g^{2}),$
(5)

where $\sigma_{p,np}$ are Stokes constants and $S_{p,np}$ are the actions on
different perturbative (p) and non-perturbative (np) saddles. The formal
series obtained through the perturbative expansion around each saddle are
represented by $\Phi_{p,np}$. These can be calculated from the partition
function in different ways. In a recent work [25], the first author explores
both Mathieu and modified Mathieu (Sinh-Gordon) potentials, showing that it is
possible to perform computations from the perturbative saddle by writing the
partition function in terms of Bessel functions, whose expansions have already
been widely explored in the literature. We also offered as alternatives the
binomial theorem followed by the Watson lemma or the integral definition of
Gamma functions and the direct expansion of the potential in Taylor series.
Otherwise, the perturbative expansion around the non-perturbative saddle
involves Lefschetz thimbles [10, 12, 26, 27], which are a generalization of
the steepest descent method [28].

After such procedures, the transseries assumes the form

$Z_{U}(g^{2})=\sigma_{0}\,\sum_{k=0}^{\infty}a_{0}(k)g^{2k}+\sigma_{1}\,e^{-1/g^{2}}\sum_{k=0}^{\infty}(-1)^{k}a_{0}(k)g^{2k},$
(6)

where

$a_{0}=\frac{\left[\Gamma(k+\frac{1}{2})\right]^{2}}{\Gamma(k+1)\left[\Gamma(\frac{1}{2})\right]^{2}}.$
(7)

In one-dimensional quantum mechanics, the partition function is a path
integral,

$\mathcal{Z_{U}}(g^{2})=\int\mathcal{D}x_{U}\exp\left\\{-\int
dt\left(\frac{1}{2}m\dot{x}_{U}^{2}+\frac{1}{g^{2}}V_{U}(x_{U})\right)\right\\}.$
(8)

The associated instanton equation $\dot{x}_{U}(t)=\sqrt{2V_{U}(x_{U}(t))}$,
where $m=1$, has a real solution

$x_{U,\mathcal{I}}=2\arctan(\exp(\sqrt{2}t)).$ (9)

The correpondent instanton action is

$S_{U,\mathcal{I}}=\int_{0}^{\pi}\sin(x_{U})dx_{U}=2.$ (10)

In the next sections, we will extend the formalism to the case of Mathieu
deformed by a non-Hermiticity factor.

##  III Connecting Hermitian and non-Hermitian scenarios

Let us consider a $\mathcal{PT}$-symmetric version of Eq.(1) in complex
domain,

$\left\\{-\frac{d^{2}}{dz^{2}}+2q\left[\cos(2z)+i\delta\sin(2z)\right]\right\\}\psi(z)=a\psi(z),$
(11)

where the parameters $q,\delta,a\in\mathbb{R}$. The case $\delta=0$ leads to
the original Mathieu equation (1). The potential
$V(z,\delta)=\cos(2z)+i\delta\sin(2z)$ is non-Hermitian and it preserves
$\mathcal{PT}$-symmetry for each $\delta$.333Notice that
$\textrm{Re}(V(z,\delta))$ is an _even_ function of position, whereas the
imaginary part of the potential $V(z,\delta)$ is an _odd_ function of
position, satisfying the condition $V(z,\delta)=V^{*}(-z,\delta)$. The
equation (11) is known as generalized $\mathcal{PT}$-symmetric Mathieu
equation. In quantum mechanics, we cannot find an analytical solution to the
instanton equation in the non-Hermitian scenario, but such solution in the
usual Hermitian case is known in the literature. Hence arises the importance
of finding a way to rewrite the Mathieu $\mathcal{PT}$-symmetric potential in
cosine or some equivalent form.

Figure 1: In the restriction $z=x+i\alpha(\delta)$, the imaginary part of
$z(t)$ is fixed.

If we consider the restriction $z=x+i\alpha(\delta)$ for (11), which is
nothing more than a reparametrization of a line in the complex plane (Fig. 1),
the potential becomes

$\displaystyle V(x+i\alpha)$ $\displaystyle=$
$\displaystyle\cos(2x)\,[\text{cosh}(2\alpha)-\text{sinh}(2\alpha)]$
$\displaystyle+i\sin(2x)\,[-\text{sinh}(2\alpha)+\delta\,\text{arccosh}(2\alpha)],$

where we use basic trigonometric identities. We can take the imaginary part of
(LABEL:eq:vxialpha) as null, allowing us to determine
$\alpha:\;\left]-1,1\right[\;\to\mathbb{R}$,

$\alpha(\delta)=\frac{1}{2}\text{arccosh}\left(\sqrt{\frac{1}{1-\delta^{2}}}\right).$
(13)

Therefore, the map
$\mathcal{V}:\mathbb{R}\times\;\left]-1,1\right[\;\to\mathbb{R}$, given by

$\mathcal{V}(x,\delta)=\sqrt{1-\delta^{2}}\,\sin^{2}(x),$ (14)

for each $\delta\in\;\left]-1,1\right[\;$, give us a well-defined Hermitian
potential. Furthermore, for each fixed $|\delta|<1$, we can rewrite (11) as

$\left[-\frac{d^{2}}{dx^{2}}-4Q\sin^{2}(x)\right]\psi(x+i\alpha)=(a-2Q)\,\psi(x+i\alpha),$
(15)

where $Q\equiv q\sqrt{1-\delta^{2}}$ and $\alpha$ is given by (13). These
steps allow us to connect both Hermitian and non-Hermitian scenarios. In
appendix A, one will note that there is an alternative way to rewrite the
generalized $\mathcal{PT}$-symmetric Mathieu potential in a cosineoidal form.
It shows that there is no obligation to switch to an axis parallel to the real
line. The key point of both methods is the restriction on the values of the
$\delta$ deformation parameter. We just have chose to use this first method
for convenience.

One may think about another perspective, where the choice is not to nullify
the imaginary part of the potential $V(x+i\alpha,\delta)$ in
(LABEL:eq:vxialpha), but its real part. In this situation, the equation that
establishes the relation between $\alpha$ and $\delta$ parameters is
$2\alpha(\delta)=\arctan(i/\delta)$. This corresponds to the complex deformed
potential $\mathcal{V}_{Im}(x,\delta)=i\sin(2x)\sqrt{\delta^{2}-1}$ with
$|\delta|>1$. It is possible to move the complex number $i$ into the square
root, so that it becomes comparable to that with $|\delta|<1$. Briefly,

$\displaystyle\mathcal{V}(x,\delta)$
$\displaystyle=\cos(2x)\sqrt{1-\delta^{2}},\quad|\delta|<1,$ (16a)
$\displaystyle\mathcal{V}_{Im}(x,\delta)$
$\displaystyle=\sin(2x)\sqrt{1-\delta^{2}},\quad|\delta|>1.$ (16b)

Is is known that the sine and cosine trigonometric functions are equivalent by
a ($\pi/2$) phase, then we can write $\sin(2x+\pi/2)=\cos(2x)$. So, if one
discovers some applicability of the $\mathcal{V}_{Im}$ imaginary potential, it
is possible to summarize both constraints for delta in a single condition,
$|\delta|\neq 1$.

##  IV Resurgent Mathieu partition function with $\delta$-deformation

From (14) we can compute the saddles depending on $\delta$. That is,
$S_{p}=\mathcal{V}(0,\delta)=0$ and
$S_{np}=\mathcal{V}(\frac{\pi}{2},\delta)=\sqrt{1-\delta^{2}}$. Therefore,

$Z(\delta,g)=2\int_{0}^{\pi/2}\exp\left(g^{-2}\,\sqrt{1-\delta^{2}}\sin^{2}(x)\right)dx.$
(17)

Making the change $\sin(x)=s^{2}$ and writing

$(1-s)^{-1/2}=\sum_{k=0}^{\infty}\frac{\Gamma\left(k+\frac{1}{2}\right)}{\Gamma(k+1)\Gamma\left(\frac{1}{2}\right)},$
(18)

we have

$Z(\delta,g^{2})=\frac{1}{g\sqrt{\pi}}\sum_{k=0}^{\infty}\frac{\Gamma(k+\frac{1}{2})}{\Gamma(k+1)\Gamma(\frac{1}{2})}\int_{0}^{1}s^{k-1/2}e^{1/g^{2}\sqrt{1-\delta^{2}}s^{2}}.$
(19)

Then we apply the Watson’s Lemma to obtain

$Z(\delta,g^{2})\sim\sum_{k=0}^{\infty}\frac{\left[\Gamma(k+\frac{1}{2})\right]^{2}}{\Gamma(k+1)\Gamma(\frac{1}{2})^{2}}\left(1/g^{2}\sqrt{1-\delta^{2}}\right)^{-k}.$
(20)

Finally, we have the transseries representation for the $\delta$-deformed
Mathieu partition function,

$\displaystyle Z(\delta,g^{2})=$
$\displaystyle\sigma_{0}\,e^{-S_{p}/g^{2}}\sum_{k=0}^{\infty}a_{0}(k)A^{-k}(\delta,g^{2})$
$\displaystyle+\sigma_{1}\,e^{-A(\delta,g^{2})}\sum_{k=0}^{\infty}(-1)^{k}a_{0}(k)A^{-k}(\delta,g^{2}),$
(21)

where

$A(\delta,g^{2})=\frac{1}{g^{2}}\sqrt{1-\delta^{2}}.$ (22)

Furthermore, observe that $\sigma_{0}$ and $\sigma_{1}$ Stokes constants are
the same as those appearing in the transseries representation for the usual
Hermitian case (6). As expected, this transseries becomes identical to (6)
when $\delta$ vanishes. From (22), we can assert that the $g^{2}$ coupling
coefficient is subject to a perturbation due to the delta deformation
coefficient.

##  V $\delta$-deformed instanton solution

We now turn to one-dimensional quantum mechanics, in which the partition
function is a path integral,

$\mathcal{Z}(g^{2})=\int\mathcal{D}x\exp\left\\{-\int
dt\left(\frac{1}{2}m\dot{x}^{2}+\frac{1}{g^{2}}\mathcal{V}(x)\right)\right\\}.$
(23)

Setting $m=1$, the associated instanton equation
$\dot{x}(t)=\sqrt{2\mathcal{V}(x(t),\delta)}$ has a solution whose real part
is

$x_{\mathcal{I}}(t)=2\mathrm{arccot}\left(\exp\left(-t\sqrt{2\sqrt{1-\delta^{2}}}\right)\right),$
(24)

which tends to $\pi$ when $t\rightarrow+\infty$, as shown in Fig. 2(b). The
instanton action is also influenced by the $\delta$ parameter,

$S=\int_{0}^{\pi}\sqrt{2}(1-\delta^{2})^{1/4}\sin(x)dx=2\sqrt{2}\,(1-\delta^{2})^{1/4}.$
(25)

Since the instanton action is related to singularities in the Borel plane,
this amazing result denotes that one could manipulate the position of the
singularities in the Borel plane by modifying the value of the non-Hermiticity
factor, which characterizes the subject to be explored in a forthcoming paper.

(a) The deformed Mathieu potential in the Hermitian scenario, Eq.(14). As
expected, the higher the deformation parameter value, the lower the potential
amplitude.

(b) Real instantons in the Hermitian scenario, Eq.(24). We have just observed
that the height of the potential barrier decreases as we increase the value of
$\delta$ (Fig. 2(a)). This fact does make it smoother for the instanton to
pass from one minimum to another. As $\delta\rightarrow 1$, the respective
curve resembles a line whose slope is given by $\sqrt{2}(1-\delta^{2})^{1/4}$.
The instanton width $\Delta t$ varies with the value of $\delta$, being
proportional to $1/\omega=2^{-1/2}(1-\delta)^{-1/4}$

Figure 2: Effects of $\delta$ deformation parameter on (a)
$\mathcal{V}(x,\delta)$ potential and (b) $x_{\mathcal{I}}(t)$ instanton
solution. The different curves refer to different values of the non-Hermitian
parameter: $\delta=0$ (dotted line), $\delta=0.8$ (dashed line) and
$\delta=0.996$ (solid line).

Furthermore, in the region permeated by the instanton, there is a guarantee
that the $\mathcal{PT}$-symmetry is not broken, because this is a closed
scenario and there are still turning points [29].

We’ve already discussed the reason for the restriction $\delta\neq 1$. But
what would happen if this was allowed? The potential in (11) with $\delta=1$
is written $V(z,1)=\exp(iz)$. The solution of the instanton equation
$\dot{z}=\sqrt{2\,V(z,1)}$ exists, being written as
$z_{\mathcal{I}}=2i\ln(-it\sqrt{2}/2)$, although it does not describe a
typical instanton curve (Fig. 2(b)). First, we observe that it has a
discontinuity in $t=0$. Furthermore, we can assert that the case in which
$\delta=1$ does not produce instanton because there are no saddle points.

Figure 3: Solid line: Solution of $\dot{z}=\sqrt{2\,V(z,1)}$ for the non-
Hermitian scenario of the potential in Eq. (11), with $\delta=1$. Dashed line:
Instanton solution for the Hermitian scenario, Eq. (24) with $\delta=1$, which
appears as a constant line at $\pi/2$ for all $t$.

We see that the two curves in Fig. 3 do not agree. This is expected, because
the non-Hermitian scenario starts with the assumption $\delta=1$. On the other
hand, the Hermitian scenario is obtained from the transformation
(LABEL:eq:vxialpha) which is valid in the interval
$\delta\in\left]-1,1\right[$ (see Eq.(13)). The limit $\delta\rightarrow 1$ is
an extrapolation of the latter case and it does not need to be in agreement
with the first scenario, as we observe in Fig. 3. It does not bring the
complete information. Then, one could naively think that the curves do not
need to totally agree with each other, but at least they do in $t>0$.

For the non-Hermitian case, the only analytic solution for the instanton
equation is for $\delta=1$, but this is not a true instanton. Recall that, in
this scenario, there are no saddle points. Notwithstanding, we have shown that
it is possible to investigate the effects of varying the
$\delta\in\left]-1,1\right[$ deformation parameter — we finally got true
instantons solutions (see Fig. 2(b)). This is done using the connection
between non-Hermitian and Hermitian scenarios in section III.

In the following sections, we will see how the behavior of several instantons
is affected by the $\delta$ non-Hermiticity factor.

##  VI Dilute gas of deformed instantons

It is known that instantons are objects that appear in a short time interval
[30], having a width on order of $1/\omega$ (see Fig.2(b)). It means that, for
large $t=T$, the approximate solutions of the equation of motion are not just
instantons and anti-instantons, but also strings of widely separated
instantons and anti-instantons. In the case of periodic potentials, in which
the Mathieu potential is understood, there are degenerate minima that allow us
to sprinkle instantons and anti-instantons freely on the real axis [31, 32].
Thus, we write

$\displaystyle\braket{j_{+}}{e^{-HT/\hbar}}{j_{-}}$ $\displaystyle=$
$\displaystyle\left(\frac{\omega}{\pi\hbar}\right)^{1/2}\,\exp\left(-\frac{\omega
T}{2}\right)$
$\displaystyle\times\sum_{n,\bar{n}=0}^{\infty}\frac{(Ke^{-S/\hbar}T)^{n+\bar{n}}}{n!\;\bar{n}!}\delta_{n-\bar{n}+j_{+}+j_{-}},$

where $n$ is the number of instantons, $\bar{n}$ is the number of anti-
instantons. If it were not for the small intervals containing instanton and
anti-instanton, $\mathcal{V}^{\prime\prime}(x,\delta)$ would be equal to
$\omega^{2}$ on the entire time axis. This characterizes the barrier
penetration and that is where the factors before the sum come from. The
correction of the formula that includes the influence of multi-instantons is
in the summation. The expression $(T^{n+\bar{n}}/(n!\;\bar{n}!))$ is
consequence of the integration over the locations of the centers and $K$ is
written as

$K=\left(\frac{S}{2\pi\hbar}\right)^{1/2}\left|\frac{\det(-\partial_{t}^{2}+\omega^{2})}{\det^{\prime}(-\partial_{t}^{2}+\mathcal{V}^{\prime\prime}(\bar{x}))}\right|^{1/2},$
(27)

where $\bar{x}$ is a single instanton and $\det^{\prime}$ means that the zero
eigenvalue is omitted when computing the determinant.

The terms of an exponential series $\sum_{k=0}^{\infty}y^{k}/k!$ grow with
$k$, for any fixed $y$, just until $k$ is on the order of $y$. Then, they
begin to decrease fast. We can apply this to the sum in Eq. (27) to conclude
that the important terms are those for which the number of (anti-)instantons
is less or approximately $(Ke^{-S/\hbar}\,T)$. For small $\hbar$, it means
that the density of (anti-)instantons is exponentially small when considering
this important terms. Thus, the average separation is huge. This is why this
approach is called the dilute gas approximation of instantons. The conditions
of the validity of average separation do not depend on $T$, as long as $T$ is
sufficiently large.

From the instanton solution, Eq. (24), we identify $\omega$, see Fig. 2(b).
The expression that describes the instanton action is in Eq. (25). By
comparison, we have $S=2\omega=2\sqrt{2}(1-\delta)^{1/4}$. Then, we can
already note that the deformation parameter is strongly present even at the
multi-instantons level.

The following section goes beyond the dilute instanton gas approximation and
shows a case where there is an interaction between coupled instanton–anti-
instanton.

##  VII Josephson junctions described by tilted $\delta$-deformed washboard
potential

The Josephson effect is a phenomenon that occurs when two or more
superconductors are placed next to each other, with some potential barrier or
restriction between them. This arrangement generates a supercurrent that flows
through this device known as the Josephson junction. There are ways to build
superconducting circuits based on the Josephson junction. They are candidates
for developing quantum computing devices. As an example of this type, we have
the superconducting quantum interference device (SQUID) [33].

In this context, the role of tunneling coordinate across the Josephson
junction is played by the phase difference of the Cooper pair wave function.
The standard model for describing this coupling is the resistively shunted
junction (RSJ) model,

$C\left(\frac{\phi_{0}}{2\pi}\right)^{2}\frac{d^{2}\psi}{dt^{2}}+\frac{1}{R}\left(\frac{\phi_{0}}{2\pi}\right)^{2}\frac{d\psi}{dt}+E_{J}\sin\psi-
I_{\textrm{ext}}\frac{\phi_{0}}{2\pi}=0,$ (28)

where $C$ and $R$ are respectively the capacitance and the effective shunt
resistance of the junction, $\phi_{0}=h/2e$ is the flux quantum,
$I_{\textrm{ext}}$ is the external bias current, and
$E_{J}=I_{c}\phi_{0}/2\pi$ is the Josephson coupling energy, which is related
with the $I_{c}$ maximum supercurrent suported by the junction.

There is a parallel between the equation of motion of this model, Eq. (28),
and the one corresponding to the motion of a Brownian particle of mass $M$ and
position $X$ in the absence of fluctuations [33], given by

$M\ddot{X}+M\gamma X(t)+\frac{\partial V(X)}{\partial X}=0,$ (29)

where the potential is known as the tilted washboard, which is nothing more
than trigonometric shape potential with a tilt. Note that we can insert the
potential (14) of the Hermitian scenario in this context if we include a term
for the tilt and make $x=\pi X/X_{0}$. Thus, we write

$V(X)=-\frac{\sqrt{1-\delta^{2}}}{2}V_{0}\left[\cos\left(\frac{2\pi
X}{X_{0}}\right)-\frac{1}{2}\right]-V_{\textrm{tilt}}\left(\frac{2\pi
X}{X_{0}}\right),$ (30)

where and $\delta\in\left]-1,1\right[$. Comparing the equations (28), (29) and
(30), we see that there is a equivalence relation
$(V_{0}/2)\sqrt{1-\delta^{2}}\;\hat{=}\;E_{J}$. A simple algebraic
manipulation generates

$|\delta|\;\hat{=}\;\sqrt{1-\frac{I^{2}_{c}h^{2}}{4V_{0}^{2}\pi^{2}e^{2}}}.$
(31)

Therefore, the insertion of the tilted deformed Mathieu potential (30) in the
Brownian motion equation (29) allows relating the non-Hermiticity factor
$\delta$ with the $I_{c}$ Josephson supercurrent.

(a) The tilted $\delta$-deformed washboard potential (30) with $\delta=0.8$,
$X_{0}=1$, $V_{\textrm{tilt}}=0.15J$, $V_{0}=1.0J$. This exemplifies the case
$|\delta|<\sqrt{1-4V_{\textrm{tilt}}^{2}/V_{0}^{2}}$. The critical points in
the interval $0<X<X_{0}/2$ are the minimum
$X_{1}=(X_{0}/2\pi)\arcsin\left(V_{\textrm{tilt}}/(V_{0}\sqrt{1-\delta^{2}}/2)\right)$
and the maximum $X_{2}=(X_{0}/2)-X_{1}$. The height of the barrier is
$V_{b}=V(X_{2})-V(X_{1})$, explicitly written in the Eq. (32). Thick
gridlines: minimum and maximum positions. Dashed gridline: $X_{0}/2$.

(b) An example of the case
$|\delta|=\sqrt{1-4V_{\textrm{tilt}}^{2}/V_{0}^{2}}$, where we choose
$\delta=0.8$, $V_{\textrm{tilt}}=0.3J$, $V_{0}=1.0J$, $X_{0}=1$. There are no
cascade barriers.

(c) An example of the case
$|\delta|>\sqrt{1-4V_{\textrm{tilt}}^{2}/V_{0}^{2}}$, where we choose
$\delta=0.8$, $V_{\textrm{tilt}}=0.6J$, $V_{0}=1.0J$, $X_{0}=1$. The slope of
the potential is negative for all $X$.

Figure 4: The tilted $\delta$-deformed washboard potential (30) for (a)
$|\delta|<\sqrt{1-4V_{\textrm{tilt}}^{2}/V_{0}^{2}}$, (b)
$|\delta|=\sqrt{1-4V_{\textrm{tilt}}^{2}/V_{0}^{2}}$ and (c)
$|\delta|>\sqrt{1-4V_{\textrm{tilt}}^{2}/V_{0}^{2}}$.

There are two distinct states in this current-biased Josephson junction: the
zero-voltage state, which corresponds to the particle being trapped in a well,
and the voltage state, that represents the particle sliding down the cascade
of wells. Figure 4(a) makes it easy to see that the height of the barrier
$V_{b}$ can be calculated by the difference between the value of the potential
(30) at a maximum and its value at the previous minimum, such that

$V_{b}=2\sqrt{\left(\frac{1-\delta^{2}}{4}\right)V_{0}^{2}-V_{\textrm{tilt}}^{2}}-2V_{\textrm{tilt}}\arccos\left(\frac{V_{\textrm{tilt}}/V_{0}}{\sqrt{1-\delta^{2}}/2}\right).$
(32)

From this result, we can see three different events. There are no cascade
barriers for $|\delta|=\sqrt{1-4V^{2}_{\textrm{tilt}}/V_{0}^{2}}$. The
particle slides all the way down for
$|\delta|>\sqrt{1-4V^{2}_{\textrm{tilt}}/V_{0}^{2}}$. Finally, the proper
condition for tunneling is
$|\delta|<\sqrt{1-4V^{2}_{\textrm{tilt}}/V_{0}^{2}}$. An interesting case
within this last regime occurs when
$|\delta|\ll\sqrt{1-4V^{2}_{\textrm{tilt}}/V_{0}^{2}}$. In this limit, the
bounce is described by a weakly bound instanton–anti-instanton pair. The
distance between them is large compared to the width of an instanton. Thus,
the action of the bounce is written

$S(T)/\hbar=2S_{\mathcal{I}}/\hbar+W(T)-\epsilon T,$ (33)

where the action of a single instanton is

$S_{\mathcal{I}}=\frac{M\gamma
X_{0}^{2}}{2\pi\hbar}\left[1+\ln\left(\pi^{2}V_{0}\sqrt{1-\delta^{2}}/(M\gamma
X_{0}^{2}\omega_{c})\right)\right],$ (34)

the interaction term between the instantons at a distance $T$ is

$W(T)=\frac{M\gamma X_{0}^{2}}{\pi\hbar}\ln[(\hbar\beta\omega_{c}/\pi)\sin(\pi
T/\hbar\beta)],$ (35)

with $\omega_{c}$ taking the role of a reference frequency, and the last term
$\epsilon T$ comes from the potential drop $\hbar\epsilon=2\pi
V_{\textrm{tilt}}$ on the distance $X_{0}$.

##  VIII Conclusion

In this work, we studied the implications of a $\mathcal{PT}$-symmetry
deformation parameter $\delta$ in the transseries representation of the
Mathieu partition function and in the instanton solution of the
$\delta$-dependent Mathieu potential. First, we sought to establish a
connection between the Hermitian and non-Hermitian scenarios. In order to do
this, we worked with a non-Hermiticity factor restricted to the interval
$\left]-1,1\right[$. We found that the deformation parameter is explicitly
present in the non-perturbative saddle action and in the two formal series,
perturbing the coupling coefficient. Therefore, the value of $\delta$ affects
the transseries representation. Furthermore, we showed that the width of the
real instanton solution increases as the value of $\delta$ grows (tending to
1). Such a fact makes it smoother for the instanton to pass from one minimum
to another. Our third observation was that the deformation parameter is
present even at the multi-instanton scenario, characterizing a dilute gas of
deformed instantons. We also studied the interesting case in which we make a
parallel with the Josephson junction through a tilted deformed washboard
potential. In the regime in which the bounce corresponds to a widely spaced
instanton-anti-instanton pair, the $\mathcal{PT}$-deformation factor is
present in the action of the bounce and affects the height of the potential
barrier. We found that we can relate the non-Hermiticity factor with the
Josephson supercurrent, indicating that the deformation might have a physical
meaning.

###### Acknowledgements.

N. M. Alvarenga thanks the Coordenação de Aperfeiçoamento de Pessoal de Nível
Superior – Brasil (CAPES) – Finance Code 001 for financial support. J. A.
Lourenço thanks the Fundação de Amparo à Pesquisa e Inovação do Espírito Santo
– Brasil (FAPES) – PRONEM $N^{o}503/2020$ for financial support. We thank B.
W. Mintz for suggesting the subject.

##  Appendix A Working at the original axis

In Sec. III, we have used the reparameterization $z=x+i\alpha(\delta)$ on the
generalized $\mathcal{PT}$-symmetric Mathieu equation (11). It has allowed us
to connect Hermitian and non-Hermitian scenarios and to perform calculations
in the referential given by this line parallel to the real axis, in the
complex plane (see Fig.1). We choose this method by convenience, but this is
not the only way to rewrite the $\mathcal{PT}$-symmetric Mathieu potential. We
show in this appendix that we can keep the complex variable $z$ unchanged in
this process.

Consider multiplying the potential in Eq.(11) by a factor $\cos(i\epsilon)$,

$\cos(i\epsilon)V(z,\delta)=\cos(i\epsilon)\cos(2z)+i\delta\cos(i\epsilon)\sin(2z).$
(36)

If we define $\delta$ such that $\delta\cos(i\epsilon)=-\sinh(\epsilon)$, or
equivalently,

$\delta=-\tanh(\epsilon).$ (37)

This causes the same restriction on $\delta$ values that we have found in the
section III, that is, $\delta\in\;\left]-1,1\right[\;$. We can write the
deformed potential as

$\mathcal{V}(z,\delta)=\frac{\cos(2z+i\epsilon)}{\cos(i\epsilon)}.$ (38)

Thus, we can conclude that it is enough to restrict the values of the non-
Hermiticity factor to the interval $\delta\in\;\left]-1,1\right[\;$ in order
to achieve the trigonometric form of the potential (Eq. 38). To conveniently
calculate the instanton solution of this potential,
$\dot{z}(t)=\sqrt{2\mathcal{V}(z(t),\delta)}$, we can rewrite it as

$\mathcal{V}(z,\delta)=\frac{2\sin^{2}(z+i\epsilon)}{\cos(i\epsilon)}.$ (39)

Thus, we find

$z_{\mathcal{I}}(t)=-i\epsilon+2\left\\{\mathrm{arctan}\left[\exp\left(2t\sqrt{\mathrm{sech}(\epsilon)}\right)\right]\right\\}.$
(40)

We can find the $\epsilon$ values corresponding to the $\delta$ values used in
Fig. 2(b) through Eq. 37. The $\mathrm{Re}\,z_{\mathcal{I}}(t)$ curves in Fig.
5 are identical to the $x_{\mathcal{I}}(t)$ curves plotted in Fig. 2(b)).

Figure 5: Real part of instanton solution $z_{\mathcal{I}}(t)$ (40) for
$\epsilon=0$ (dotted line), $\epsilon=1.099$ (dashed line) and
$\epsilon=3.106$ (solid line).

## References

  * Mathieu [1868] É. Mathieu, Mémoire sur le mouvement vibratoire d’une membrane de forme elliptique, J. Math. Pures Appl. 13, 137 (1868).
  * McLachlan [1947] N. W. McLachlan,  _Theory and Application of Mathieu Functions_ (Clarendon Press, London, 1947).
  * Coïsson  _et al._ [2009] R. Coïsson, G. Vernizzi, and X. Yang, Mathieu functions and numerical solutions of the Mathieu equation, in  _2009 IEEE International Workshop on Open-source Software for Scientific Computation (OSSC)_ (2009) pp. 3–10.
  * Li and Wang [2000] S. Li and B. S. Wang, Field expressions and patterns in elliptical waveguide, IEEE Transactions on Microwave Theory and Techniques 48, 864 (2000).
  * Stanley Humphries [1956] J. Stanley Humphries,  _Principles of Charged Particle Acceleration_ (Wiley, New York, 1956).
  * Winter and Ortjohann [1991] H. Winter and H. W. Ortjohann, Simple demonstration of storing macroscopic particles in a “Paul trap”, Am. J. Phys. 59, 807 (1991).
  * Carver [1971] T. R. Carver, Mathieu’s functions and electrons in a periodic lattice, Am. J. Phys. 39, 1225 (1971).
  * Aldrovandi and Ferreira [1980] R. Aldrovandi and P. L. Ferreira, Quantum pendulum, Am. J. Phys. 48, 660 (1980).
  * Kerner  _et al._ [2012] R. Kerner, G. Naumis, and W. A. Gómez-Arias, Bending and flexural phonon scattering: Generalized Dirac equation for an electron moving in curved graphene, Physica B: Condensed Matter 407, 2002 (2012).
  * Cherman  _et al._ [2015a] A. Cherman, D. Dorigoni, and M. Ünsal, Decoding perturbation theory using resurgence: Stokes phenomena, new saddle points and Lefschetz thimbles, JHEP 10, 056, arXiv:1403.1277 [hep-th] .
  * Cherman  _et al._ [2015b] A. Cherman, P. Koroteev, and M. Ünsal, Resurgence and holomorphy: from weak to strong coupling, J. Math. Phys. 56, 053505 (2015b), arXiv:1410.0388 [hep-th] .
  * Başar  _et al._ [2013] G. Başar, G. Dunne, and M. Ünsal, Resurgence theory, ghost-instantons, and analytic continuation of path integrals, JHEP 10, 041, arXiv:1308.1108 [hep-th] .
  * Wigner [1932] E. Wigner, The operation of time reversal in quantum mechanics, Nachr. Ges. Wiss. Göttingen Math.-Physik. Kl. 1, 546 (1932).
  * Makris  _et al._ [2008] K. G. Makris, R. El-Ganainy, D. N. Christodoulides, and Z. H. Musslimani, Beam dynamics in $\mathcal{P}\mathcal{T}$ symmetric optical lattices, Phys. Rev. Lett. 100, 103904 (2008).
  * Bender and Boettcher [1998] C. M. Bender and S. Boettcher, Real spectra in non-hermitian hamiltonians having $\mathcal{P}\mathcal{T}$ symmetry, Phys. Rev. Lett. 80, 5243 (1998).
  * Bender [2016] C. M. Bender, $\mathcal{PT}$ symmetry in quantum physics: From a mathematical curiosity to optical experiments, Europhysics News 47, 17 (2016).
  * Bender [2018] C. M. Bender,  _$\mathcal{PT}$ Symmetry in Quantum and Classical Physics_ (World Scientific, Singapore, 2018).
  * Cavalcanti  _et al._ [2022] E. Cavalcanti, N. M. Alvarenga, F. Reis, J. R. Mahon, C. A. Linhares, and J. A. Lourenço, Energy levels for $\mathcal{PT}$-symmetric deformation of the Mathieu equation, (2022), arXiv:2204.13350 [quant-ph] .
  * Zinn-Justin and Jentschura [2004] J. Zinn-Justin and U. D. Jentschura, Multi-instantons and exact results I: conjectures, WKB expansions, and instanton interactions, Annals of Physics 313, 197 (2004).
  * Mariño [2015] M. Mariño,  _Instantons and Large N: An Introduction to Non-Perturbative Methods in Quantum Field Theory_ (Cambridge University Press, 2015).
  * Mariño [2014] M. Mariño, Lectures on non-perturbative effects in large n gauge theories, matrix models and strings, Fortschr. Phys. 62, 455 (2014).
  * Aniceto  _et al._ [2019] I. Aniceto, G. Başar, and R. Schiappa, A primer on resurgent transseries and their asymptotics, Phys. Rep. 809, 1 (2019).
  * Aniceto and Schiappa [2015] I. Aniceto and R. Schiappa, Nonperturbative ambiguities and the reality of resurgent transseries, Commun. Math. Phys. 335, 183 (2015).
  * [24] DLMF, NIST Digital Library of Mathematical Functions, http://dlmf.nist.gov/28, Release 1.1.6 of 2022-06-30, f. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
  * Alvarenga [2020] N. M. Alvarenga,  _Resurgence Theory Applied to Quantum Mechanics_ , Ph.D. thesis, Universidade do Estado do Rio de Janeiro (2020), in Portuguese.
  * Tanizaki [2015] Y. Tanizaki,  _Study on Sign Problem via Lefschetz-Thimble Path Integral_ , Ph.D. thesis, University of Tokyo (2015).
  * Serone  _et al._ [2017] M. Serone, G. Spada, and G. Villadoro, The power of perturbation theory, JHEP 56, 1029, arXiv:1702.04148 [hep-th] .
  * Bender and Orszag [1999] C. M. Bender and S. A. Orszag,  _Advanced Mathematical Methods for Scientists and Engineers I: Asymptotic Methods and Perturbation Theory_ (Springer, 1999).
  * Bender and Hook [2021] C. M. Bender and D. W. Hook, $\mathcal{PT}$-symmetric classical mechanics, (2021), arXiv:2103.04214 [math-ph] .
  * Das [2006] A. Das,  _Field Theory: A Path Integral Approach_, 2nd ed. (World Scientific, Singapore, 2006) https://www.worldscientific.com/doi/pdf/10.1142/6145 .
  * Coleman [1985] S. Coleman,  _Aspects of Symmetry_ (Cambridge University Press, 1985).
  * Zinn-Justin [1982] J. Zinn-Justin, The principles of instanton calculus: a few applications, in  _Les Houches Summer School on Theoretical Physics: New Trends in Atomic Physics_ (1982).
  * Weiss [2008] U. Weiss,  _Quantum Dissipative Systems_, 3rd ed. (World Scientific, 2008).


# On the Minimax Regret for Linear Bandits in a wide variety of Action Spaces

Debangshu Banerjee  Aditya Gopalan

(November 2022)

###### Abstract

As noted in the works of Lattimore and Szepesvári [2020], it has been
mentioned that it is an open problem to characterize the minimax regret of
linear bandits in a wide variety of action spaces. In this article we present
an optimal regret lower bound for a wide class of convex action spaces.

##  1 Introduction

Minimax regret bounds in bandit environments are a well studied problem and
results typically are limited to a particular action set, namely the $l_{1}$
and $l_{\infty}$ balls in $\mathbb{R}^{d}$. We include in this article that
display that the methods introduced by Lattimore and Szepesvári [2020] in
Chapter 24 can indeed be generalized to a wide variety of action spaces,
namely to any $l_{p}$ ball where $p$ is in the range $(1,\infty)$.

##  2 Key Result

Note that the result we include in 2.1, is optimal in the bandit setting, in
sense that algorithms like LinUCB achieve this.

######  Theorem 2.1.

Let $\mathcal{X}$ be the $L^{p}$ ball defined as
$\mathcal{X}=\\{x\in\mathbb{R}^{d}\;:\left\lVert x\right\rVert_{p}\leqslant
c\\}$, where $1<p<\infty$. Assume $d\leqslant(2cn^{2})^{\frac{p}{2}}$. Then
there exists a parameter $\theta\in\mathbb{R}^{d}$ with
$\left\lVert\theta\right\rVert_{p}^{p}=\frac{1}{(c4\sqrt{3})^{p}}\frac{d^{2}}{n^{\frac{p}{2}}}$
such that $\mathcal{R}_{n}(\theta)\geqslant\frac{d\sqrt{n}}{16\sqrt{3}}$.

###### Proof.

We chose $\theta\in\\{+\Delta,-\Delta\\}^{d}$ and note that the regret,
defined as, $\mathcal{R}_{n}(\theta)$, is

$\displaystyle\begin{split}\mathcal{R}_{n}(\theta)=\sum_{t=1}^{n}x^{*}{{}^{\top}}\theta-
x_{t}^{\top}\theta\\\
=\sum_{t=1}^{n}\sum_{i=1}^{d}x^{*}_{i}\theta_{i}-x_{ti}\theta_{i}\\\
=\Delta\sum_{t=1}^{n}\sum_{i=1}^{d}\frac{c}{d^{\frac{1}{p}}}-x_{ti}sign(\theta_{i})\\\
\geqslant\frac{\Delta
d^{\frac{1}{p}}}{2c}\sum_{t=1}^{n}\sum_{i=1}^{d}\bigg{(}\frac{c}{d^{\frac{1}{p}}}-x_{ti}sign(\theta_{i})\bigg{)}^{2}\;,\end{split}$
(1)

where the third equality follows from Lemma A.1 and the last inequality
follows from Lemma A.2. The remainder of the proof follows the same idea as
that presented in the proof of the Unit Ball in Section 24.2 of Lattimore and
Szepesvári [2020]. We present it here for the sake of completeness. We define
a stopping time
$\tau_{i}=n\wedge\min{\\{t\;:\;\sum_{s=1}^{t}x_{si}^{2}\geqslant\frac{nc^{2}}{d^{\frac{2}{p}}}\\}}$.
Thus

$\displaystyle\mathcal{R}_{n}(\theta)\geqslant\frac{\Delta
d^{\frac{1}{p}}}{2c}\sum_{i=1}^{d}\sum_{t=1}^{\tau_{i}}\bigg{(}\frac{c}{d^{\frac{1}{p}}}-x_{ti}sign(\theta_{i})\bigg{)}^{2}\;.$

Define a Random Variable
$U_{i}(\sigma)=\sum_{t=1}^{\tau_{i}}\bigg{(}\frac{c}{d^{\frac{1}{p}}}-x_{ti}\sigma\bigg{)}^{2}$
where $\sigma\in\\{+1,-1\\}$ and note that

$\displaystyle
U_{i}(1)=\sum_{t=1}^{\tau_{i}}\bigg{(}\frac{c}{d^{\frac{1}{p}}}-x_{ti}\bigg{)}^{2}\leqslant
2\sum_{t=1}^{\tau_{i}}\frac{c^{2}}{d^{\frac{2}{p}}}+2\sum_{t=1}^{\tau_{i}}x_{ti}^{2}\leqslant\frac{4nc^{2}}{d^{\frac{2}{p}}}+2\;,$
(2)

where the last inequality follows from the definition of $\tau_{i}$.

Now we fix an $i$, and make a perturbed version of $\theta^{\prime}$, which is
the same as $\theta$ except in the $i^{th}$ position where
$\theta^{\prime}_{i}=-\theta_{i}$. Thus, applying Pinsker’s inequality,

$\displaystyle\mathbb{E}_{\theta}[U_{i}(1)]\geqslant\mathbb{E}_{\theta^{\prime}}[U_{i}(1)]-\bigg{(}\frac{4nc^{2}}{d^{\frac{2}{p}}}+2\bigg{)}\sqrt{\frac{1}{2}\mathbb{KL}(\mathbb{P}_{\theta}||\mathbb{P}_{\theta^{\prime}})}$
(3)
$\displaystyle\geqslant\mathbb{E}_{\theta^{\prime}}[U_{i}(1)]-\frac{\Delta}{2}\bigg{(}\frac{4nc^{2}}{d^{\frac{2}{p}}}+2\bigg{)}\sqrt{\sum_{t=1}^{\tau_{i}}x_{ti}^{2}}$
$\displaystyle\geqslant\mathbb{E}_{\theta^{\prime}}[U_{i}(1)]-\frac{\Delta}{2}\bigg{(}\frac{4nc^{2}}{d^{\frac{2}{p}}}+2\bigg{)}\sqrt{\frac{nc^{2}}{d^{\frac{2}{p}}}+1}$
$\displaystyle\geqslant\mathbb{E}_{\theta^{\prime}}[U_{i}(1)]-\frac{4\sqrt{3}n\Delta
c^{2}}{d^{\frac{2}{p}}}\sqrt{\frac{nc^{2}}{d^{\frac{2}{p}}}}\;,$

where the last inequality follows under the assumption
$d\leqslant(2nc^{2})^{\frac{p}{2}}$. Thus

$\displaystyle\mathbb{E}_{\theta}[U_{i}(1)]+\mathbb{E}_{\theta^{\prime}}[U_{i}(-1)]\geqslant\mathbb{E}_{\theta^{\prime}}[U_{i}(1))+U_{i}(-1)]-\frac{4\sqrt{3}n\Delta
c^{2}}{d^{\frac{2}{p}}}\sqrt{\frac{nc^{2}}{d^{\frac{2}{p}}}}$
$\displaystyle\begin{split}=2\mathbb{E}_{\theta^{\prime}}\bigg{[}\frac{\tau_{i}c^{2}}{d^{\frac{2}{p}}}+\sum_{t=1}^{\tau_{i}}x_{ti}^{2}\bigg{]}-\frac{4\sqrt{3}n\Delta
c^{2}}{d^{\frac{2}{p}}}\sqrt{\frac{nc^{2}}{d^{\frac{2}{p}}}}\geqslant\frac{nc^{2}}{d^{\frac{2}{p}}}\;,\end{split}$

where the last inequality follows from the definition of $\tau_{i}$ and
setting the value of $\Delta$ as
$\frac{1}{4\sqrt{3}}\sqrt{\frac{d^{\frac{2}{p}}}{nc^{2}}}$. Using an average
hammering trick

$\displaystyle\sum_{\theta\in\\{\pm\Delta\\}^{d}}\mathcal{R}_{n}(\theta)\geqslant\frac{\Delta
d^{\frac{1}{p}}}{2c}\sum_{i=1}^{d}\sum_{\theta\in\\{\pm\Delta\\}^{d}}\mathbb{E}_{\theta}[U_{i}(sign(\theta_{i})]$
$\displaystyle\begin{split}=\frac{\Delta
d^{\frac{1}{p}}}{2c}\sum_{i=1}^{d}\sum_{\theta_{-i}\in\\{\pm\Delta\\}^{d-1}}\sum_{\theta_{i}\in\\{\pm\Delta\\}}\mathbb{E}_{\theta}[U_{i}(sign(\theta_{i})]\\\
\geqslant\frac{\Delta
d^{\frac{1}{p}}}{2c}\sum_{i=1}^{d}\sum_{\theta_{-i}\in\\{\pm\Delta\\}^{d-1}}\frac{nc^{2}}{d^{\frac{2}{p}}}=2^{d-2}\Delta
ncd^{1-\frac{1}{p}}.\end{split}$

Hence there exists a $\theta$ in $\\{\pm\Delta\\}^{d}$, such that

$\displaystyle\mathcal{R}_{n}(\theta)\geqslant\frac{nc\Delta
d^{1-\frac{1}{p}}}{4}=\frac{d\sqrt{n}}{16\sqrt{3}}.$

∎

######  Remark 2.2.

The results in 2.1 are interesting because with regards to the dimensionality
$d$ and time horizon $n$ dependence it is exact.

######  Remark 2.3.

This result also shows that the minimum eigen value of the design matrix and
regret are fundamentally different quantities Banerjee et al. [2022]. For
example note that for $l_{p}$ balls for $p>2$, the minimum eigen value can
grow at a rate lower than $\Omega(\sqrt{n}$, whereas, the minimax regert
remains bounded as $\Omega(\sqrt{n}$.

##  3 Conclusion

We expect that similar results can hold for general convex bodies and not just
for $l_{p}$ balls.

## References

  * Banerjee et al. [2022] D. Banerjee, A. Ghosh, S. R. Chowdhury, and A. Gopalan.  Exploration in linear bandits with rich action sets and its implications for inference.  _arXiv e-prints_ , pages arXiv–2207, 2022.
  * Lattimore and Szepesvári [2020] T. Lattimore and C. Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.

##  Appendix A Appendix

###  A.1 Technical Lemmas

######  Lemma A.1 (Optimal Reward in $L^{p}$ Ball).

Let $\mathcal{X}$ be the $L^{p}$ ball defined as
$\mathcal{X}=\\{x\in\mathbb{R}^{d}\;:\left\lVert x\right\rVert_{p}\leqslant
c\\}$. We compute the optimal reward for the linear bandit model

$\displaystyle\max x^{\top}\theta\;\;\;s.t.\;\;\;x\in\mathcal{X}$ (4)

The solution to the optimization problem 4 is
$\frac{1}{\Big{(}\sum_{i=1}^{d}|\theta_{i}|^{\frac{p}{p-1}}\Big{)}^{\frac{1}{p}}}\sum_{i=1}^{d}c|\theta_{i}|^{\frac{p}{p-1}}$

###### Proof.

Note that the solution $x^{*}$ satisfies the following relation for any
$i\in[d]$

$\displaystyle
x^{*}_{i}=\Big{(}\frac{|\theta_{i}|}{\lambda}\Big{)}^{\frac{1}{p-1}}sign(\theta_{i})\;,$
(5)

where $\lambda\geqslant 0$ is the Lagrangian variable. Solving for $\lambda$
using the constraint equation of the problem with now equality instead of
inequality. (Because the optimal solution lies at the boundary)

$\displaystyle\lambda=\Big{(}\frac{\sum_{i=1}^{d}|\theta_{i}|^{\frac{p}{p-1}}}{c^{p}}\Big{)}^{\frac{p-1}{p}}\;.$
(6)

Now solving for $x^{*}{{}^{\top}}\theta=\sum_{i=1}^{d}x^{*}_{i}\theta_{i}$
gives the result. ∎

######  Lemma A.2.

$\displaystyle\sum_{i=1}^{d}\frac{c}{d^{\frac{1}{p}}}-x_{ti}sign(\theta_{i})\geqslant\frac{d^{\frac{1}{p}}}{2c}\sum_{i=1}^{d}\bigg{(}\frac{c}{d^{\frac{1}{p}}}-x_{ti}sign(\theta_{i})\bigg{)}^{2}$
(7)

###### Proof.

$\displaystyle\begin{split}\sum_{i=1}^{d}\bigg{(}\frac{c}{d^{\frac{1}{p}}}-x_{ti}sign(\theta_{i})\bigg{)}^{2}\\\
=c^{2}d^{1-\frac{2}{p}}-2\sum_{i=1}^{d}\frac{c}{d^{\frac{1}{p}}}x_{ti}sign(\theta_{i})+\sum_{i=1}^{d}x_{ti}^{2}\\\
\leqslant
2c^{2}d^{1-\frac{2}{p}}-2\sum_{i=1}^{d}\frac{c}{d^{\frac{1}{p}}}x_{ti}sign(\theta_{i})\\\
=\frac{2c}{d^{\frac{1}{p}}}\sum_{i=1}^{d}\frac{c}{d^{\frac{1}{p}}}-x_{ti}sign(\theta_{i})\;,\end{split}$
(8)

where the inequality follows from Lemma A.3. Rearranging gives the lemma. ∎

######  Lemma A.3.

If $\left\lVert x\right\rVert_{p}\leqslant c$, then $\left\lVert
x\right\rVert_{2}^{2}\leqslant c^{2}d^{1-\frac{2}{p}}$

###### Proof.

$\displaystyle\sum_{i=1}^{d}x_{i}^{2}\leqslant(\sum_{i=1}^{d}|x_{i}|^{p})^{\frac{2}{p}}d^{1-\frac{2}{p}}\leqslant
c^{2}d^{1-\frac{2}{p}}\;,$ (9)

where the first inequality follows from Holder’s inequality and the second
inequality follows from the hypothesis. ∎