# Training Characteristic Functions with Reinforcement Learning:
XAI-methods play Connect Four

Stephan Wäldchen111Both authors contributed equally to this work.
<EMAIL_ADDRESS>
Institute of Mathematics & AI in Society, Science, and Technology
Technische Universität Berlin & Zuse Institute Berlin
Berlin, Germany
Felix Huber111Both authors contributed equally to this work<EMAIL_ADDRESS>
Institute of Mathematics & AI in Society, Science, and Technology
Technische Universität Berlin & Zuse Institute Berlin
Berlin, Germany
Sebastian Pokutta<EMAIL_ADDRESS>
Institute of Mathematics & AI in Society, Science, and Technology
Technische Universität Berlin & Zuse Institute Berlin
Berlin, Germany

###### Abstract

Characteristic functions (from cooperative game theory) are able to evaluate
partial inputs and form the basis for attribution methods like Shapley values.
These attribution methods allow us to measure how important each input
component is for the function output—one of the goals of explainable AI (XAI).
Given a standard classifier function, it is unclear how partial input should
be realised. Instead, most XAI-methods for black-box classifiers like neural
networks consider counterfactual inputs that generally lie off-manifold, which
makes them hard to evaluate and easy to manipulate.

We propose a setup to directly train characteristic functions in the form of
neural networks to play simple two-player games. We apply this to the game of
Connect Four by randomly hiding colour information from our agents during
training. This has three advantages for comparing XAI-methods: It alleviates
the ambiguity about how to realise partial input, makes off-manifold
evaluation unnecessary and allows us to compare the methods by letting them
play against each other.

##  1 Introduction

The safe deployment of AI-systems in high-stakes applications such as
autonomous driving Schraagen et al., (2020), medical imaging Holzinger et al.,
(2017) and criminal justice Rudin and Ustun, (2018) requires that their
decisions can be subjected to human scrutiny. The most successful models,
often based on machine learning (ML) and deep neural networks (DNN), have
instead grown increasingly complex and are widely regarded to operate as
black-boxes. This spawned the field of explainable AI (XAI) with the explicit
aim to make ML models transparent in their reasoning.

###  1.1 Explainable Artificial Intelligence

Though XAI had practical success, such as detecting biases in established data
sets Lapuschkin et al., (2019), there is currently no consensus among
researchers about what exactly constitutes an explainable model Lipton,
(2018). For a good overview see Adadi and Berrada, (2018).

Models such as $k$-nearest neighbours, succinct decision trees or sparse
linear models are deemed inherently interpretable Arrieta et al., (2020),
which makes them preferable Rudin, (2019). However, the most impressive
breakthroughs in the field of AI have only been possible with DNNs. In this
light, a second paradigm emerged: to apply these successful models and explain
them post-hoc.

In this work, we focus on _saliency_ (or _relevance_) attribution methods.
Given a classifier and input, these methods rate the importance of each
feature for the classifier output, often displayed visually as a heatmap,
called a _saliency map_. We give an overview over the proposed methods in
Section 2.

###  1.2 Characteristic Functions

Cooperative game theory considers attribution problems very similar to
saliency attribution, where a common pay-off is to be fairly distributed to a
number of cooperating players. In the context of ML, players correspond to
features and the pay-off is the classifier score. Let $d\in\mathbb{N}$ be the
number of features, and
$[d]=\mathopen{}\left\\{1,\dots,d\right\\}\mathclose{}$. One key concept is
the _characteristic function_ $\nu\colon 2^{[d]}\rightarrow\mathbb{R}$ which
assigns a value to every possible subset $S$ of the $d$ features, called a
_coalition_. We refer the reader to Chalkiadakis et al., (2011) for a good
introduction into cooperative game theory.

For binary classifiers this led to the concept of _prime implicant
explanations_ (PIE) that search for the smallest coalition $S\subset[d]$ that
ensures a value of $\nu(S)=1$, see Shih et al., (2018). These explanations can
be efficiently computed for certain simple classifiers like decision trees or
binary decision diagrams.

Furthermore, the _Shapley values_ are an established attribution method,
defined as

$\phi_{\nu,i}=\sum_{S\subseteq[d]\setminus\\{i\\}}\begin{pmatrix}d-1\\\
\mathopen{}\left|S\right|\mathclose{}\end{pmatrix}^{-1}\mathopen{}\left(\nu(S\cup\\{i\\})-\nu(S)\right)\mathclose{}.$

Shapley values are the unique attribution methods that satisfy certain
desirable fairness criteria, see Shapley, (2016) and Section E.

Both PIE and Shapley values are thus defined over desirable properties, and
the actual algorithm to compute them depends on the model. In contrast, most
saliency attribution methods for neural networks are defined directly over
algorithmic instructions and lack definite properties that make them
useful111Except the gradient maps, though these suffer from other shortcomings
as explained in Section A. Even the saliency methods that are inspired by PIE
and Shapley values (see Section 2) do not maintain their desirable theoretical
properties while at the same being computationally efficient Macdonald et al.,
(2020). This means that the only way to judge whether these saliency methods
have merit is to evaluate them in practical scenarios.

###  1.3 Evaluating Saliency Methods

Figure 1: Connect 4 with missing colour information shown in grey. a) A game
between two pairs of maskers and players. The maskers decide which colour
information to pass on to the players with an upper limit of revealing half
the played pieces. The player has to decide his move based on the information
sent by the masker. Our the players are both represented by the same policy
network. Which information to reveal will later be chosen by different
saliency methods. b) The game board is encoded in three input channels: Two
binary matrices indicating the pieces of each player and one indicate the open
fields. With full information the encoding is redundant, with only partial
information the agent is unsure about the colour of some pieces but can still
make valid moves.

In Doshi-Velez and Kim, (2017) the authors differentiate between _human-based_
and _functionally-grounded evaluation_. The former has the advantage of
measuring directly what we want, namely that explanations are legible and
helpful to humans. On the other hand, human-based evaluations are costly and
hard to generalise from one task to another. They also cannot discern between
a network with unintuitive reasoning and a saliency method that produces
unintuitive results. Functionally grounded evaluation aims to design proxy
tasks whose success is correlated with the quality of the explanation. They
often ask, which information is useful to the interpreted network itself, see
Mohseni et al., (2021), so that only the quality of the saliency method
matters. This approach also allows for much larger scale experiments. However,
not all proxy-task are necessarily linked to good explanations Biessmann and
Refiano, (2021).

The proxy task we consider here is: _successful play of abstract games with
limited information._ In our case study we investigate the game _Connect Four_
Allis, (1988). We make use of the fact that neural networks have emerged as
one of the strongest models for reinforcement learning, and e.g. constitute
the first human competitive models for Go Silver et al., (2017) and Atari
games Mnih et al., (2015).

Our exact setup is illustrated in Figure 1. A _masker_ and a _player_ are
paired against a second team of the same form. The masker, presents a limited
amount of information (colour features) to their player, who then selects the
next move. The full board state is then given to the masker of the opposing
team who selects the information for their player, and so on until the game is
finished either by one party winning or a draw. The players are modelled by
DNNs without memory and base their decision only on the information currently
provided by the masker. During training, the masker will select information
randomly up to a varying maximal amount. For the comparison of the saliency
methods, the masker will instead be represented by a method that explains the
move that the player would have made given full information. The most salient
features are then given to the player for their actual move.

###  1.4 Our Contribution

First, we give an overview over the existing saliency methods and explain how
they are vulnerable to manipulation if they rely on off-manifold inputs. We
show that for image obfuscation, one of the most used evaluation metrics, the
best-performing methods give artefactual explanations that rely on
“superstimuli”, a phenomenon resulting from evaluating classifiers off-
manifold.

As a remedy, we directly train agents as characteristic functions for
reinforcement learning, by randomly hiding colour features and show that this
setup delivers results comparable to training solely on full information.
Additionally, we demonstrate a relatively monotonous relationship between
information and performance in the game, which justifies the setup explained
in Figure 1 as a sensible proxy task for XAI methods. Since our agents can
handle partial input, we can directly compute Shapley values via sampling.
These are theoretically well understood and rely only on counterfactual input
the agent has been trained on—which makes this sound attribution method. We
demonstrate their usefulness by comparing to the ground truth available for
certain board situations. Additionally, we learn that training on hidden input
is not enough to ensure interpretability if the training is linked to the
wrong objective.

We then compare a selection of XAI methods in a round-robin tournament in
Connect Four, which has some advantages that image obfuscation comparisons
generally lack:

  1. 1.

It is canonically clear how missing information should be modelled (since it
is included in the training).

  2. 2.

There is no need to evaluate the classifier off-manifold.

  3. 3.

We have a concrete task (Winning the game) to compare the XAI-methods.

##  2 Related Work

A lot of work has been done to design methods that produce saliency maps for
neural networks. So far, these methods are not equipped with theoretical
guarantees that they fulfil a certain quality property, as compared to Shapley
values and PIE, see Section 1.2. They are instead motivated by heuristic
arguments and then numerically evaluated. We give a short overview over the
existing heuristics and then explain that first, methods relying on off-
manifold counterfactuals are manipulable and secondly, evaluations relying on
off-manifold inputs are manipulable as well.

###  2.1 Saliency Methods

We restrict our analysis to local, post-hoc saliency methods for neural
network classifiers, both model specific and model-agnostic. We differentiate
the following three categories.

##### Local Linearisation

Linear methods are considered interpretable, so it is a natural approach for
nonlinear models to instead interpret a local linearisation. In this category
we find gradient maps Simonyan et al., (2013), SmoothGrad Smilkov et al.,
(2017), which samples the gradient around the input, and LIME Ribeiro et al.,
(2016) which applies the classifier to samples around the input then fits a
new linear classifier to the resulting input-label-pairs.

##### Heuristic Backpropagation

These methods replace the chain-rule of gradient backpropagation with
different heuristically motivated rules and propagate relevance scores back to
the input. One of the earliest methods methods for neural networks was
deconvolution Zeiler and Fergus, (2014), newer methods include
GuidedBackpropagation (GB) Springenberg et al., (2015), DeepLift Shrikumar et
al., (2017), DeepShap Lundberg and Lee, 2017a  and LRP Bach et al., (2015).
These methods have the advantage of being computationally very fast and
applicable in real-time.

##### Partial Input

These methods rely on turning a classifier function $f$ and an input
$\mathbf{x}$ into a characteristic function $\nu_{f,\mathbf{x}}$. The standard
way to define $\nu_{f,\mathbf{x}}(S)$ for a feature set $S$, put forth by
Lundberg and Lee, 2017b , is to regard the missing features
$\mathbf{x}_{S^{c}}$ as random variables and take an expectation value
conditioned on the given parameters $\mathbf{x}_{S}$, i.e.

$\nu_{f,\mathbf{x}}(S)=\mathbb{E}_{\mathbf{y}}\mathopen{}\left[f(\mathbf{y})\,|\,\mathbf{y}_{S}=\mathbf{x}_{S}\right]\mathclose{}=\int
f(\mathbf{x})p(\mathbf{x}_{S^{c}}\,|\,\mathbf{x}_{S})\,\text{d}\mathbf{x}_{S^{c}}.$
(2.1)

Being able to evaluate partial input, these methods either optimise an
objective similar to prime implicant explanations, for example _Rate-
Distortion Explanations_ (RDE) Macdonald et al., (2020) and _Anchors_ Ribeiro
et al., (2018), or approximate Shapley values Sundararajan and Najmi, (2020).
This however is computationally infeasible to do exactly, so these methods
instead rely on heuristic strategies that do not carry over the quality
properties of PIE and Shapley values. Additionally, the soundness of these
heuristics depends strongly on how correctly the conditional distribution
$p(\mathbf{x}_{S^{c}}\,|\,\mathbf{x}_{S})$ is modelled, as we will discuss
next.

###  2.2 Off-Manifold Input

Image | FW | AFW | LCG | LAFW | Sensitivity
---|---|---|---|---|---
|  |  |  |  |
Figure 2: RDE-Explanations of a bird image taken from Macdonald et al., (2021)
with permission of the authors. The proposed optimisation methods (FW, AFW,
LCG, LAFW) search for the smallest set of pixels that still maintain the
classification of “bird”, if the other pixels are randomised. All produce a
mask that creates a new bird head as a “superstimulus” mask. The sensitivity
map does not show this behaviour. The distribution of the randomised pixels is
independent from the selected set, which means the contours of the set will be
visible and detectable by the pattern matching network. Modelling the noise
after true distribution $p(\mathbf{x}_{S^{c}}\,|\,\mathbf{x}_{S})$ (as in
Equation 2.1) would prevent this effect, since a monochrome selection of black
pixels would likely be inpainted with black as well. Then no bird’s head would
appear.

These post-hoc relevance methods have in common that they consider
counterfactual information: _“What if I would change this part of the
input?”_. We explain how this applies to each method in Section A.

For this reason, the saliency methods can all be manipulated by principally
the same idea: replace an existing model by a another one that agrees on the
data manifold but not off-manifold, where the behaviour can be chosen
arbitrarily. This allows to hide biases in classifiers for _on-manifold_
inputs almost at will, as demonstrated for gradient maps and integrated
gradients Anders et al., (2020); Dimanov et al., (2020), LRP Anders et al.,
(2020); Dombrowski et al., (2019), LIME Slack et al., (2020); Dimanov et al.,
(2020), DeepShap Slack et al., (2020); Dimanov et al., (2020), Grad-Cam Heo et
al., (2019), Shapley-basedFrye et al., (2020) and general counterfactual
explanations Slack et al., (2021).

##### Image Obfuscation

In the absence of human annotations (such as bounding boxes or pixel-wise
annotations), some functionally grounded evaluation for image data obfuscate
part of the image and measure how much the classifier output changes Mohseni
et al., (2021). The idea is this: keeping the relevant features intact should
leave the classification stable, obfuscating them should rapidly decay the
classifier score. This method was introduced as _pixel-flipping_ Samek et al.,
(2017) and used to evaluate XAI-methods for image recognition Fong and
Vedaldi, (2017); Macdonald et al., (2019) and Atari games Huber et al.,
(2021).

In Macdonald et al., (2019) the authors directly optimise for a mask that
selects sparse features which maintain the classifier decision, severely
outperforming competitors. In Macdonald et al., (2021) this method gets
improved further with methods from convex optimisation (Frank-Wolfe
optimiser). However, visually inspecting the produced saliency maps reveals
they create new features that were not present in the original image. This is
possible over a mechanism similar to adversarial examples, see Figure 2, which
means: _the optimal mask creates its own features!_ Since the distribution of
the obfuscated part of the image is independent from the rest the created
images lie off-manifold which makes this effect possible. To keep the image
on-manifold, the obfuscated part would have to be sampled from the true
conditional data distribution $p(\mathbf{x}_{S^{c}}\,|\,\mathbf{x}_{S})$ which
is not known. This shows that proxy tasks have to be designed with care if
they are meant to be useful for comparing saliency methods. Not only are the
methods vulnerable to manipulation by going off-manifold, the evaluation tasks
themselves can be exploited by making use of off-manifold inputs.

##  3 Setup

Instead of trying to turn a classifier function into a characteristic
function, we propose to directly train on hidden features. Policy and value
functions (see Li, (2017)) for agents that play simple two-player, turn-based
games (such as Go, Checkers, Hex) are particularly well suited for this task.

The logic of these games is complex enough to make the use of black-box
functions such as neural network sensible, and in the case of Go the unbeaten
standard. At the same time, the input is low-dimensional and discrete.
Additionally, the input components have weaker correlations between
neighbours, i.e. a random configuration of Connect Four pieces can still be a
valid game222if the number of pieces for each player is balanced, whereas a
random assortment of pixels will almost surely not be a valid image. These
factors facilitate sampling partial inputs during training. 333For image data
by comparison, simply hiding random pixels would not do, since the image can
likely still be inferred by inpainting.

Figure 3: Network architecture for the PPO-agent. The convolutional layers
(Conv) have $3\times 3$ filters, 512 channels, $1\times 1$ stride and use
zero-padding. The fully connected (FC) layers for the policy and value head
use softmax and tanh-activation respectively. All other layers use ReLU-
activations.

###  3.1 Hiding the Player Colour

The most straight-forward way of hiding information from an agent would be to
complete hide a game field. However, we want to preserve the ability to select
legal moves, and let the sensibility of the move be the only concern of the
agent (instead of legality). For a lot of the games (e.g. Connect Four, Go,
Hex) knowing which fields are occupied allows to make valid moves. For others
(Chess, Checkers) valid moves depend on the colour and type of the pieces, so
we will concentrate on the former.

To hide the colour information, we represent a game position as three binary
matrices indicating which fields are occupied by the first player (red), the
second player (blue) and which remain free. The colour information can be
hidden by setting the entries in the respective matrix to zero. We illustrate
this concept in Figure 1 a) for the game of Connect Four.

###  3.2 Reinforcement Learning for Connect Four

The game of Connect Four was chosen because of its simplicity and low input
dimension. Deep-RL has been applied to Connect Four in the form of both Deep-
Q-Learning Dabas et al., (2022), Policy Gradient (PG) Crespo, (2019) and
AlphaZero-like approaches Wang et al., (2021); Clausen et al., (2021). The
AlphaZero-like approach combines a neural network with policy and value head
with an MCTS444Monte-Carlo Tree Search, see Silver et al., (2017) lookahead to
make its decision. Even though it has emerged as the most powerful method, we
want to explain purely the network decision without the MCTS involved. We thus
follow the PPO approach of Schulman et al.,, since it yields a strongly
performing pure network-agent for Connect Four even without the help of the
MCTS Crespo, (2019).

##### Our PPO-agent

We represent the input by a state
$\mathbf{s}\in\mathopen{}\left\\{0,1\right\\}\mathclose{}^{3\times 6\times 7}$
with three channels as explained in Figure 1 (b). The value function that
predicts the expected reward $V(\mathbf{s})$ and the policy function that
determines the probability $P(a\,|\,\mathbf{s})$ of taking action $a\in[7]$
are both modelled by the same network with with a policy and a value head, see
Figure 3. Our architecture extends the model of Crespo, by two fully connected
layers, which empirically yields better performance. Agents can play
_competitively_ , always choosing the most likely action
$a^{*}=\operatorname*{argmax}P(\cdot\,|\,\mathbf{s})$ or _non-competitively_ ,
sampling from $P(\cdot\,|\,\mathbf{s})$. We give a full overview over
architecture and training parameters in Section B.

##### Hiding features during training

During self-play, we randomly hide the colour feature of a certain percentage
of fields by setting the respective entry in the the first and second input
channel to zero. The information that the field is occupied remains in the
third channel. Every turn $p_{h}$ is drawn uniformly from
$[0,p_{h}^{\text{max}}]$. Let $t\in[42]$ be the turn number, then we hide the
colour information of $\lfloor p_{h}t\rfloor$ pieces selected uniformly at
random. We explored different values for $p_{h}^{\text{max}}$ and trained the
following agents:

  * •

FI: PPO-Agent trained with full information,

  * •

PI-50: Partial information with $p_{h}\sim\mathcal{U}([0,0.5])$,

  * •

PI-100: Partial information with $p_{h}\sim\mathcal{U}([0,1])$.

a) Win Rate against MCTS
Orig. FI PI-50 PI-100 MCTS 500 0.92 0.972 0.793 0.684 MCTS 1000 0.896 0.936
0.66 0.469 MCTS 2000 0.825 0.91 0.497 0.328
b) Number of Optimal Moves
Agent Orig. FI PI-50 PI-100 Correct Moves 38 39 39 29

Table 1: Comparison of our agent with the original proposal by Crespo, (2019)
in competitive mode. The numbers show the winrate against the MCTS with
different simulation limits over 1000 games. b) For a game between two Connect
Four solvers, we tracked how many of the optimal moves were correctly
predicted by the different agents, i.e. were given the highest probability in
the policy output. The optimal game always takes 41 moves in total.

###  3.3 Benchmarking

To demonstrate that this setup still trains capable agents we compare them to
the benchmark results from the original setup presented in Crespo, (2019). We
let our agents play in competitive mode against an MCTS-agent taken from Vogt,
(2019). For three different difficulties, the MCTS is allowed to simulate 500,
1000 or 2000 games. Additionally, we used a game played by two perfect
solvers555Taken from Pons, (2019) and measured how many of the 41 moves were
predicted correctly by our agents. For the results see Table 1. Our FI-agents
performs best, both against the MCTS and predicting the optimal moves.
Incorporating partial information into the training leads to a worse
performance by PI-50 and PI-100. Nevertheless, at least the PI-50 is a capable
agent that could not be beaten by the authors. We thus opt to use the PI-50
agent to compare the saliency methods in Section 5.

To show that for each agent more information is indeed useful666This is not
obvious: during training the agent could get used to an average amount of
partial information and play worse if given more colour features., we tracked
their performance playing non-competitively for different amounts of randomly
hidden colour features, see Figure 4. For the FI-agent and the PI-50 agent we
see near-monotonous decay in game performance against the optimal agent, an
MCTS-1000 and themselves with full information. This justifies our idea of a
proxy task to compare saliency methods: select the most useful 50% of features
that allow the PI-50 agent to win the game!

##  4 Explanations with Partial Information

Since our agents have been trained with missing information, their policy and
value functions can be seen as a characteristic function with respect to the
colour features. For $t\in[42]$ let $\mathbf{s}_{t}\in[0,1]^{3\times 6\times
7}$ be a board state after turn $t$ and $S\subseteq[t]$ be a set of colour
features (of a subset of the $t$ played pieces). Then we define
$\mathbf{s}^{(S)}$ as a partial board state including only the colour features
in $S$, as in Figure 1 (b), second row.

Let $a^{*}=\operatorname*{argmax}P(\,\cdot\,;\mathbf{s})$, then we can define
$\nu^{\text{pol}}:2^{[t]}\rightarrow[0,1]$ and
$\nu^{\text{val}}:2^{[t]}\rightarrow[-1,1]$ as

$\nu^{\text{pol}}(S)=P(a^{*};\mathbf{s}^{(S)})\quad\text{and}\quad\nu^{\text{val}}(S)=V(\mathbf{s}^{(S)})$

and interpret them as the characteristic functions from the policy and value
output for a given board state. From now on, we use the characteristic
function associated with the _policy_ network, since this is the part that
actually plays the games, whereas the value network is only involved in
training. This allows us to directly compute explanations for them in the form
of Shapley values or prime implicant explanations. We now explain how we
efficiently approximate both.

compat=1.15  a) b) c)

Figure 4: Relationship between the percentage of hidden fields and game
performance, measured in game length against a perfect solver (a), winrate
against an MCTS1000 (b) and against the agent itself with full information (c)
for the FI, PI-50 and PI-100 agents. In (a) we give as reference a random
agent who plays an average of 12 turns before losing and another optimal
solver who always plays 41 turns. Our agents never win against the solver. The
FI-agent start out strongest, but was never trained on hidden features, so
drops towards the random agent. The PI-50 starts with slightly weaker game
length and but keeps an advantage over random even for no colour information
at all. The PI-100 agents shows a weakest performance given full information
but even rises slight with less information. Every game takes at least 7 turns
and at most 42. In (b) and (c) all agents decrease in performance with fewer
features revealed.

###  4.1 Sampling Shapley Values

Computing Shapley values is #P-complete Deng and Papadimitriou, (1994) , but
they can be efficiently approximated by sampling. The simplest approach is to
utilise the fact that the Shapley values for $t$ features can be rewritten as

$\phi_{i}=\frac{1}{t!}\sum_{\pi\in\Pi([t])}\mathopen{}\left(\nu(P^{\pi}_{i}\cup\mathopen{}\left\\{i\right\\}\mathclose{})-\nu(P^{\pi}_{i})\right)\mathclose{},$

where $\Pi([t])$ is the set of all permutations of $[t]$ and $P_{i}^{\pi}$ the
set of all features that precede $i$ in the order $\pi$. To approximate the
whole sum we can sample uniformly from $\Pi([t])$. To stick true to our
philosophy of evaluating $\nu$ only on-manifold, we can only use PI-100 to
calculate the Shapley-values who has been trained on all levels of hidden
features. To use the PI-50 agent, we define _partial_ Shapley-values for a
hidden percentage $p_{h}$ by only sampling from

$\Pi_{i}^{p_{h}}=\mathopen{}\left\\{\pi\in\Pi([t])\;\text{s.t.}\;\mathopen{}\left|P_{i}^{\pi}\right|\mathclose{}\geq
p_{h}t\right\\}\mathclose{},$

which are all permutations that have input $i$ in the last $p_{h}t$ position.
Sampling from $\Pi_{i}^{0.5}$ makes sure that at least 50% of colour
information is disclosed. We show in Section C that we keep the symmetry,
linearity and null player criterion, but loose efficiency.

To get an $(\epsilon,\delta)$-approximation $\bar{\phi}_{i}$ of the true
Shapley values $\phi_{i}$ in the sense that
$\mathbb{P}\mathopen{}\left[\mathopen{}\left|\phi_{i}-\bar{\phi}_{i}\right|\mathclose{}\leq\epsilon\right]\mathclose{}\geq
1-\delta$, we need
$N_{\epsilon,\delta}=\frac{1}{2}\epsilon^{-2}\log(2\delta^{-1})$ many samples,
according to the worst-case bound given by the Hoeffdings-inequality
Hoeffding, (1994). For our comparison we choose a $(0.01,0.01)$-approximation
which amounts to $\approx 26500$ samples.

More efficient methods to sample Shapley-values have been developed utilising
group testing Jia et al., (2019) or kernel-herding Mitchell et al., (2021)
both providing a quadratic improvement of the accuracy in terms of number of
function evaluations although with some computational overhead. We stick,
however, to this simple approach since our input dimension is small and there
is significant overhead in both the kernel-herding and group testing.

###  4.2 Prime Implicant Explanations with Frank-Wolfe

Prime implicant explanations can be efficiently calculated for simple
classifiers like decision trees or ordered binary decision diagrams Shih et
al., (2018). In Macdonald et al., (2020) the authors extended the definition
of prime implicants to a continuous probabilistic setting to explain neural
networks, although the authors also showed that is $\mathsf{NP}$-hard to find
them even approximately for general networks. To solve the problem
heuristically, they optimise for implicants of size $k\in[t]$ via convex
relaxation, which forms the basis for RDE. Adapted to our scenario the
corresponding objective becomes

$S^{*}=\operatorname*{argmin}_{\mathopen{}\left|S\right|\mathclose{}\leq
k}(\nu([t])-\nu(S))^{2}.$

Whereas Macdonald et al., rely on an approximation to Equation 2.1, our
formulation has no probabilistic aspect, since we directly access a
characteristic function. In Macdonald et al., (2021) the authors show how to
minimise this functional efficiently with Frank-Wolfe solvers, a projection-
free method for optimisation on convex domains Pokutta et al., (2020). We copy
their approach and apply it to find small prime implicant explanations for
varying $k$, a saliency attribution which we call the _FW-method_. A detailed
description of the FW-method is included in Section D. The Frank-Wolfe method
might attribute the maximum weight of 1 to multiple features, so we break ties
randomly when selecting the most salient ones.

compat=1.15  Shapley Sampling FW $p_{h}$ $k$

Figure 5: Comparison of the Frank-Wolfe-based and Shapley Sampling-based
attribution methods with the ground truth. The bars show how often the method
identified the 3 (green), 2 (yellow), 1 (red) or 0 (black) of the three most
important game pieces. We observe that Shapley sampling is able to identify
the most pieces correctly for a hidden percentage of $p_{h}=0.5$. The Frank-
Wolfe method performs generally worse than Shapley Sampling. Smaller $k$ tend
to polarise the results with more boards where either all three or zero of the
correct pieces have been found.

###  4.3 Finding Ground Truth Pieces

The policy network of the PI-agent is able to find a winning move in 99% of
cases. It stands to reason that the three pieces that are completed by the
move can be seen as a _ground truth_ features for the decision.

We use this compare partial Shapley Values with the FW-method. We let the
agent play against itself and registered 500 final board states for which the
agent was at least 90% sure of the winning move. All game pieces that form a
line of four with the winning move777It can happen that one move completes
multiple lines. are considered as ground truth for the focus of the policy
network. We track how often the three most salient pieces according to the
attribution methods are among the ground truth pieces. For 500 games we note
whether three, two, one or zero pieces are correct, see Figure 5, for partial
Shapley values with varying $p_{h}$ and the FW-method for varying $k$.

##### Shapley Sampling

Partial Shapley values generally yield good results, finding at least two
correct pieces in at least 75% of all boards. However, calculating the
Shapley-values all the way up to $p_{h}=1$ gives worse results than stopping
at 0.5, both for PI-50 and PI-100. The plots for PI-100 can be found in
Section E. Further investigating revealed that the output of the PI-100 policy
function for $p_{h}>0.5$ becomes essentially random for many board situations.
A possible reason is that for low information the optimal move becomes ill-
defined, and the entropy loss is to be too small to force the policy to be
approximately uniform. We will come back to this point in Section 6.

##### Frank Wolfe Solver

The FW method is faster than Shapley sampling, but exhibits worse performance.
Interestingly, for small $k$ it polarises, having a higher percentage of
boards where it finds either all or non of the ground truth pieces. For large
$k$ it usually converges to an attribution that selects many pieces with
maximum value of 1. Breaking ties randomly then leads to average results. For
small $k$ it oftentimes selects pieces that suggest the right move but for a
different reason than the ground truth pieces. Additionally, the FW
performance suffers from relying on convex relaxation of set membership, which
means optimising over continuous colour features, thus going off-manifold.
This can be seen by the fact that the continuous input values almost always
lead to the right policy, but selecting the $k$ most salient features, thus
thresholding the input back to binary values, sometimes leads to a different
policy.

##  5 Comparing XAI-methods

compat=1.15  Gradient DeepShap GB SmoothGrad LRP DeepTaylor Random FW

Figure 6: _Top:_ One move explained by different saliency maps: The PI-50
agent placed a piece in the second column, blocking a potential win by their
opponent (red cross). The saliency maps for this move are shown for each
method. _Bottom:_ The agent is presented with the colour information of the
50% most salient pieces according to each method (marked in white). This can
lead to a different decision, here for LRP and Random, allowing the opponent
to win.

We can now compare different saliency methods via the setup explained in
Figure 1. As our agent we select PI-50 and allow to show 50% of colour
features, thus remaining on-manifold. To implement the masker, we let an XAI-
method explain the decision of the policy function for the most probable
action. For every occupied field we sum the absolute value of saliency score
from the first two colour channels (that represent which player occupies the
field). The saliency scores on empty fields and on the third channel are
ignored. Then we select the 50% (rounded up) highest scoring colour features
and hide the rest from the board state (set them to 0). This state is then
used by the player, (PI-50, non-competitive) to select a move. We present an
illustration for all used saliency methods in Figure 6. Afterwards this
process is mirrored by a different saliency method and this is iterated until
the game is finished.

We compare the saliency methods Gradient, GuidedBackprop (GB) SmoothGrad,
LRP-$\epsilon$, DeepTaylor and Random from the
Innvestigate888https://github.com/albermax/innvestigate
DBLP:journals/corr/abs-1808-04260 and DeepShap from the
SHAP999https://github.com/slundberg/shap toolboxes with recommended settings.
_Random_ , which assigns a random Gaussian noise as saliency value, _Input_ ,
which shows the complete board state, and the FW-method explained in the
previous chapter serve as comparison for the other methods.

We let each saliency method compete in a round-robin tournament with 1000
games for each encounter. In case of a draw, both methods score half a
victory. We display the number of victories for each encounter in Figure 7
together with two challenges described in Section 4.3 and Section 3.3.

##### Results

The results are displayed in Figure 7. The methods form two groups of
performance. DeepShap, GuidedBackprop and the Frank-Wolfe-based method perform
best and equally well. The second group is formed by gradient, LRP and
DeepTaylor who show a weaker performance. SmoothGrad has the worst showing,
potentially owing to the fact that it does not automatically sample other
valid board situations. These results are confirmed by the information-
performance graphs, introduced in Section 3.3 for play against PI-50 with full
information, where instead of randomly selecting the revealed features they
are selected by each saliency method, see Figure 7.

Regarding FW, we showed in Section 4 that the optimiser does not always find
what we consider the important pieces but rather the pieces that ensure the
policy network makes the right decision. Thus DeepShap and GuidedBackprop
compare very favourably considering FW optimises directly for winning the
game. Additionally, DeepShap, Gradient, LRP-$\epsilon$ and GuidedBackprop
severely outperform Shapley Sampling in finding the ground-truth pieces. This
shows that heuristic methods can have merit over theoretically founded one. We
explain a possible reason for the weak performance of the Shapley values and a
way forward to improve it in Section 6.

Figure 7: Comparison of different XAI-methods playing Connect Four. _Left:_
Win rates row vs column, with draws counting as $\frac{1}{2}$. _Top right:_
Win rate of PI-50 with varying percentage of hidden information against
itself. The partial colour features have been selected using the XAI-methods.
The win rate of the agent decays slower, when the method is better at
selecting the crucial information. _Bottom right:_ Comparison of the XAI-
methods in the ground truth task described in Section 4.3. We can see that
DeepShap and GuidedBackprop perform well in all these tasks.

##  6 Conclusion

We have demonstrated that simple game setups can be used to train agents
capable of handling missing features. This allowed us to design a proxy task
for XAI-methods based on the idea that such agents make better decisions if
provided more relevant information. We evaluate a collection of saliency
methods and see strong performances for DeepShap and GuidedBackprop.

As explained in Section 2, using proxy tasks that evaluate the classifier off-
manifold can have paradoxical consequence such as yielding “superstimulus”
masks as the optimal strategy. To avoid this, we train our agents on the
partial information used in our proxy task. Using the resulting characteristic
function given by the policy network, we can directly calculate Shapley values
via sampling. This attribution method is theoretically well understood and
only relies inputs that were part of the training manifold which justifies
trusting the resulting saliency maps.

However, one problem we discovered is that simply extending the training
manifold is not enough if the training objective does not strongly regulate
behaviour of the classifier. In our example the policy network is trained to
predict sensible game actions—a task that becomes increasingly ill-defined for
low information input. The additional entropy term was not strong enough to
regulate behaviour towards a uniform distribution over all actions and thus
the network output for many low information states was essentially random. A
remedy could lie in using Q-learning instead, even in scenarios where it
performs slightly worse than PPO as it only indirectly optimises for policy.
Q-learning trains a value function to obey an consistency condition in form of
the Bellman-equation Sutton and Barto, (2018). This indirectness can become
useful since the objective remains well-defined even if almost no information
is given. For a low average loss in terms of the Bellman equation the network
would be required to give a conservative estimate of the board value, such as
a 50% chance of winning. A similarly option for supervised learning on partial
information is to include a default option of “I don’t know” that is preferred
to a wrong answer. Then the objective on low information data becomes well
defined and techniques such as Shapley sampling can be used as a theoretically
sound saliency method. Tempering with the model to hide biases would require
changing on-manifold behaviour which could be detected through performance
tests.

In our investigation, the heuristic saliency methods compared very favourably
to the more theoretically founded methods. The hope is that future research
might prove guaranteed for time efficient methods, e.g. that DeepShap indeed
provides a good approximation to the true Shapley values for networks trained
on real-world data. If these saliency attribution methods can be made robust
to manipulation, e.g. by approaches from Frye et al., (2020) and Anders et
al., (2020), they could constitute promising tools for XAI.

#### Acknowledgements

This research was partially supported by the DFG Cluster of Excellence MATH+
(EXC-2046/1, project id 390685689) and the Research Campus Modal funded by the
German Federal Ministry of Education and Research (fund numbers
05M14ZAM,05M20ZBM).

## References

  * Adadi and Berrada, (2018) Adadi, A. and Berrada, M. (2018).  Peeking inside the black-box: a survey on explainable artificial intelligence (xai).  IEEE access, 6:52138–52160.
  * Adebayo et al., (2018) Adebayo, J., Gilmer, J., Muelly, M., Goodfellow, I., Hardt, M., and Kim, B. (2018).  Sanity checks for saliency maps.  arXiv preprint arXiv:1810.03292.
  * Allis, (1988) Allis, L. V. (1988).  A knowledge-based approach of connect-four.  J. Int. Comput. Games Assoc., 11(4):165.
  * Anders et al., (2020) Anders, C., Pasliev, P., Dombrowski, A.-K., Müller, K.-R., and Kessel, P. (2020).  Fairwashing explanations with off-manifold detergent.  In International Conference on Machine Learning, pages 314–323. PMLR.
  * Arrieta et al., (2020) Arrieta, A. B., Díaz-Rodríguez, N., Del Ser, J., Bennetot, A., Tabik, S., Barbado, A., García, S., Gil-López, S., Molina, D., Benjamins, R., et al. (2020).  Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai.  Information Fusion, 58:82–115.
  * Bach et al., (2015) Bach, S., Binder, A., Montavon, G., Klauschen, F., Müller, K.-R., and Samek, W. (2015).  On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation.  PLOS ONE, 10(7):1–46.
  * Biessmann and Refiano, (2021) Biessmann, F. and Refiano, D. (2021).  Quality metrics for transparent machine learning with and without humans in the loop are not correlated.  arXiv preprint arXiv:2107.02033.
  * Chalkiadakis et al., (2011) Chalkiadakis, G., Elkind, E., and Wooldridge, M. (2011).  Computational aspects of cooperative game theory.  Synthesis Lectures on Artificial Intelligence and Machine Learning, 5(6):1–168.
  * Clausen et al., (2021) Clausen, C., Reichhuber, S., Thomsen, I., and Tomforde, S. (2021).  Improvements to increase the efficiency of the alphazero algorithm: A case study in the game’connect 4’.  In ICAART (2), pages 803–811.
  * Crespo, (2019) Crespo, J. (2019).  Reinforcement learning for two-player zero-sum games.  Master’s thesis, Tecnico Lisboa, https://fenix.tecnico.ulisboa.pt/downloadFile/1689244997260153/81811-joao-crespo_dissertacao.pdf.
  * Dabas et al., (2022) Dabas, M., Dahiya, N., and Pushparaj, P. (2022).  Solving connect 4 using artificial intelligence.  In International Conference on Innovative Computing and Communications, pages 727–735. Springer.
  * Deng and Papadimitriou, (1994) Deng, X. and Papadimitriou, C. H. (1994).  On the complexity of cooperative solution concepts.  Mathematics of operations research, 19(2):257–266.
  * Dimanov et al., (2020) Dimanov, B., Bhatt, U., Jamnik, M., and Weller, A. (2020).  You shouldn’t trust me: Learning models which conceal unfairness from multiple explanation methods.  In SafeAI@ AAAI.
  * Dombrowski et al., (2019) Dombrowski, A.-K., Alber, M., Anders, C. J., Ackermann, M., Müller, K.-R., and Kessel, P. (2019).  Explanations can be manipulated and geometry is to blame.  arXiv preprint arXiv:1906.07983.
  * Doshi-Velez and Kim, (2017) Doshi-Velez, F. and Kim, B. (2017).  Towards a rigorous science of interpretable machine learning.  arXiv preprint arXiv:1702.08608.
  * Fong and Vedaldi, (2017) Fong, R. C. and Vedaldi, A. (2017).  Interpretable explanations of black boxes by meaningful perturbation.  In Proceedings of the IEEE international conference on computer vision, pages 3429–3437.
  * Frye et al., (2020) Frye, C., de Mijolla, D., Begley, T., Cowton, L., Stanley, M., and Feige, I. (2020).  Shapley explainability on the data manifold.  arXiv preprint arXiv:2006.01272.
  * Heo et al., (2019) Heo, J., Joo, S., and Moon, T. (2019).  Fooling neural network interpretations via adversarial model manipulation.  Advances in Neural Information Processing Systems, 32:2925–2936.
  * Hoeffding, (1994) Hoeffding, W. (1994).  Probability inequalities for sums of bounded random variables.  In The collected works of Wassily Hoeffding, pages 409–426. Springer.
  * Holzinger et al., (2017) Holzinger, A., Biemann, C., Pattichis, C. S., and Kell, D. B. (2017).  What do we need to build explainable ai systems for the medical domain?  arXiv preprint arXiv:1712.09923.
  * Huber et al., (2021) Huber, T., Limmer, B., and André, E. (2021).  Benchmarking perturbation-based saliency maps for explaining deep reinforcement learning agents.  arXiv preprint arXiv:2101.07312.
  * Jia et al., (2019) Jia, R., Dao, D., Wang, B., Hubis, F. A., Hynes, N., Gürel, N. M., Li, B., Zhang, C., Song, D., and Spanos, C. J. (2019).  Towards efficient data valuation based on the shapley value.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167–1176. PMLR.
  * Lapuschkin et al., (2019) Lapuschkin, S., Wäldchen, S., Binder, A., Montavon, G., Samek, W., and Müller, K.-R. (2019).  Unmasking clever hans predictors and assessing what machines really learn.  Nature communications, 10(1):1–8.
  * Li, (2017) Li, Y. (2017).  Deep reinforcement learning: An overview.  arXiv preprint arXiv:1701.07274.
  * Lipton, (2018) Lipton, Z. C. (2018).  The mythos of model interpretability: In machine learning, the concept of interpretability is both important and slippery.  Queue, 16(3):31–57.
  * (26) Lundberg, S. M. and Lee, S.-I. (2017a).  A unified approach to interpreting model predictions.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems 30, pages 4765–4774. Curran Associates, Inc.
  * (27) Lundberg, S. M. and Lee, S.-I. (2017b).  A unified approach to interpreting model predictions.  In Proceedings of the 31st international conference on neural information processing systems, pages 4768–4777.
  * Macdonald et al., (2021) Macdonald, J., Besançon, M., and Pokutta, S. (2021).  Interpretable neural networks with frank-wolfe: Sparse relevance maps and relevance orderings.  arXiv preprint arXiv:2110.08105.
  * Macdonald et al., (2019) Macdonald, J., Wäldchen, S., Hauch, S., and Kutyniok, G. (2019).  A rate-distortion framework for explaining neural network decisions.  arXiv preprint arXiv:1905.11092.
  * Macdonald et al., (2020) Macdonald, J., Wäldchen, S., Hauch, S., and Kutyniok, G. (2020).  Explaining neural network decisions is hard.  In XXAI Workshop, 37th ICML.
  * Mitchell et al., (2021) Mitchell, R., Cooper, J., Frank, E., and Holmes, G. (2021).  Sampling permutations for shapley value estimation.  arXiv preprint arXiv:2104.12199.
  * Mnih et al., (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015).  Human-level control through deep reinforcement learning.  nature, 518(7540):529–533.
  * Mohseni et al., (2021) Mohseni, S., Zarei, N., and Ragan, E. D. (2021).  A multidisciplinary survey and framework for design and evaluation of explainable ai systems.  ACM Transactions on Interactive Intelligent Systems (TiiS), 11(3-4):1–45.
  * Pokutta et al., (2020) Pokutta, S., Spiegel, C., and Zimmer, M. (2020).  Deep neural network training with frank-wolfe.  arXiv preprint arXiv:2010.07243.
  * Pons, (2019) Pons, P. (2019).  Connect 4 game solver.
  * Ribeiro et al., (2016) Ribeiro, M. T., Singh, S., and Guestrin, C. (2016).  " why should i trust you?" explaining the predictions of any classifier.  In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135–1144.
  * Ribeiro et al., (2018) Ribeiro, M. T., Singh, S., and Guestrin, C. (2018).  Anchors: High-precision model-agnostic explanations.  In Proceedings of the AAAI conference on artificial intelligence, volume 32.
  * Rudin, (2019) Rudin, C. (2019).  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  Nature Machine Intelligence, 1(5):206–215.
  * Rudin and Ustun, (2018) Rudin, C. and Ustun, B. (2018).  Optimized scoring systems: Toward trust in machine learning for healthcare and criminal justice.  Interfaces, 48(5):449–466.
  * Samek et al., (2017) Samek, W., Binder, A., Montavon, G., Lapuschkin, S., and Müller, K.-R. (2017).  Evaluating the visualization of what a deep neural network has learned.  IEEE Transactions on Neural Networks and Learning Systems, 28(11):2660–2673.
  * Schraagen et al., (2020) Schraagen, J. M., Elsasser, P., Fricke, H., Hof, M., and Ragalmuto, F. (2020).  Trusting the x in xai: Effects of different types of explanations by a self-driving car on trust, explanation satisfaction and mental models.  In Proceedings of the Human Factors and Ergonomics Society Annual Meeting, volume 64, pages 339–343. SAGE Publications Sage CA: Los Angeles, CA.
  * Schulman et al., (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017).  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347.
  * Shapley, (2016) Shapley, L. S. (2016).  17\. A value for n-person games.  Princeton University Press.
  * Shih et al., (2018) Shih, A., Choi, A., and Darwiche, A. (2018).  A symbolic approach to explaining bayesian network classifiers.  arXiv preprint arXiv:1805.03364.
  * Shrikumar et al., (2017) Shrikumar, A., Greenside, P., and Kundaje, A. (2017).  Learning important features through propagating activation differences.  In International Conference on Machine Learning, pages 3145–3153. PMLR.
  * Silver et al., (2017) Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017).  Mastering the game of go without human knowledge.  nature, 550(7676):354–359.
  * Simonyan et al., (2013) Simonyan, K., Vedaldi, A., and Zisserman, A. (2013).  Deep inside convolutional networks: Visualising image classification models and saliency maps.  arXiv preprint arXiv:1312.6034.
  * Slack et al., (2020) Slack, D., Hilgard, S., Jia, E., Singh, S., and Lakkaraju, H. (2020).  Fooling lime and shap: Adversarial attacks on post hoc explanation methods.  In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 180–186.
  * Slack et al., (2021) Slack, D., Hilgard, S., Lakkaraju, H., and Singh, S. (2021).  Counterfactual explanations can be manipulated.  arXiv preprint arXiv:2106.02666.
  * Smilkov et al., (2017) Smilkov, D., Thorat, N., Kim, B., Viégas, F., and Wattenberg, M. (2017).  Smoothgrad: removing noise by adding noise.  arXiv preprint arXiv:1706.03825.
  * Springenberg et al., (2015) Springenberg, J. T., Dosovitskiy, A., Brox, T., and Riedmiller, M. A. (2015).  Striving for simplicity: The all convolutional net.  In ICLR (Workshop).
  * Sundararajan and Najmi, (2020) Sundararajan, M. and Najmi, A. (2020).  The many shapley values for model explanation.  In International Conference on Machine Learning, pages 9269–9278. PMLR.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Vogt, (2019) Vogt, M. D. P. T. (2019).  Carlo connect.
  * Wang et al., (2021) Wang, H., Preuss, M., and Plaat, A. (2021).  Adaptive warm-start mcts in alphazero-like deep reinforcement learning.  arXiv preprint arXiv:2105.06136.
  * Zeiler and Fergus, (2014) Zeiler, M. D. and Fergus, R. (2014).  Visualizing and understanding convolutional networks.  In Fleet, D., Pajdla, T., Schiele, B., and Tuytelaars, T., editors, Computer Vision – ECCV 2014, pages 818–833, Cham. Springer International Publishing.

##  A Saliency Methods and Off-Manifold Counterfactuals

Considering a classifier function $f:[0,1]^{d}\rightarrow[0,1]$ and an input
$\mathbf{x}\in[0,1]^{d}$, saliency methods attribute importance (or relevance)
values to each input feature $x_{i}$, with $i\in[d]$, for the classifier
decision $f(\mathbf{x})$. In a sense they describe what the classifier focuses
on. For a good introduction we refer to Adebayo et al., (2018). We now argue
that the three categories of saliency methods introduced in Section 2 all rely
on counter-factual inputs that lie off-manifold.

##### Local Linearisation

For LIME Ribeiro et al., (2016) this is clear since the method samples new
inputs $\mathbf{y}$ around $\mathbf{x}$, labels them $f(\mathbf{y})$ and fits
a linear classifier to these new data points. Arguably, gradient-based methods
are always off-manifold for highly non-linear classifiers if the gradient
itself is not part of the objective function of the training. In this case,
there is principally no reason why the gradient should contain any useful
information about the classification. The fact that it often does can be
explained for models trained via gradient descent, which implicitly enforces
useful gradient information. This however, quickly breaks down when the models
are manipulated after training, see Dimanov et al., (2020). Likewise, for
piece-wise constant models that are trained by pseudo-gradients the gradient
information is always zero.

##### Heuristic Backpropagation

For backpropagation-based methods these counterfactual inputs are less
obvious. Lundberg and Lee, 2017a explain this connection for DeepLift,
DeepShap and LRP, which compare the inputs of every layer to baseline values
that depends on the specific method Lundberg and Lee, 2017a . In this sense
they use a counterfactual at every layer instead of only at the input level.

##### Partial Input

Methods that derive characteristic functions from standard classifiers do this
mostly via expectation values Frye et al., (2020) over a conditional
distribution of counterfactual inputs as in Equation C.1. However, if the
distribution is not modelled correctly, which is difficult for real-world
data, it is supported mainly off-manifold. Explanation models that use such a
characteristic function, e.g in the form of prime implicants (such as RDE,
Macdonald et al., (2020) or anchors Ribeiro et al., (2018)) or for Shapley
values will inherit this flaw, as explained in Frye et al., (2020).

##  B Description of the Training Process

Our training setup is based on Algorithm 1 (“PPO, Actor-Critic Style”) in
Schulman et al., (2017). This setup was applied to Connect Four as described
in Crespo, (2019), and we adopt most of the hyper-parameters for the training
of our agents.

##### Network Architecture

We use a modified version of the architecture proposed by Crespo, with two
additional fully connected (FC) layers, described in Figure 3. We changed the
input dimension to $3\times 6\times 7$, representing the fields occupied by
the first player (red), the second player (blue) or no one respectively. The
input gets transformed by a series of 4 convolutional layers of filter size
$3\times 3$ with stride 1, 512 channels and ReLU activations and zero-padding
for the first two layers to keep the board shape of $6\times 7$, which is then
reduced to $4\times 5$ and $2\times 3$ after the last two conv-layers
respectively. The resulting tensor is flattened and passed through a series of
FCs with ReLU activation, one of shape $3072\times 1024$, one $1024\times 512$
and three $512\times 512$. Then we split the output into the policy head with
an FC of size $512\times 7$ and into the value head with size $512\times 1$.
The policy head has a softmax activation function, the value head a $\tanh$
activation.

##### Training Parameters

Our PPO-agent plays against itself and for every turn saves state, value
output, policy output, reward and an indicator for the last move of the game.
We give a reward of 1 for wins, 0 for draws, -1 for losses and -2 for illegal
moves. Illegal moves end the game and only the last turn gets saved to memory.
We make use of a discount factor $\gamma=0.75$ to propagate back reward to
obtain discounted rewards for each state. For clipping the policy loss, we set
$\epsilon=0.2$. The total loss weighs the policy loss with 1.0, the value loss
with 0.5 and the entropy loss with 0.01. Every 10 games we update the network
parameters with Adam on torch standard settings and a learning rate of
$l=0.0001$ for 4 steps.

##  C Partial Shapley Values

The Shapley Values are the most established attribution method from
cooperative game theory, as they are unique in satisfying the following
desirable properties: linearity, symmetry, null player and efficiency Shapley,
(2016). They can be defined as a sum over all possible permutations of the set
$[d]$ of $d$ players as follows:

$\phi_{i}(\nu)=\frac{1}{d!}\sum_{\pi\in\Pi([d])}\mathopen{}\left(\nu(P^{\pi}_{i}\cup\mathopen{}\left\\{i\right\\}\mathclose{})-\nu(P^{\pi}_{i})\right)\mathclose{},$

where $\Pi([d])$ is the set of all permutations of $[d]$ and $P_{i}^{\pi}$ the
set of all features that precede $i$ in the order $\pi$.

The size of the coalition $P^{\pi}_{i}$ corresponds to the number of colour
features in our Connect Four board states. In our investigation $\nu$ is based
on the policy layer of the PI-50 agent who has only been trained up to 50%
missing information. To avoid off-manifold input we thus want to define
partial Shapley values that sample only permutations that ensure a coalition
size of at least $pd$ for some $p\in[0,1]$.

To achieve this, we define for every player $i\in[d]$ a set of permutations

$\Pi_{i}^{p}=\mathopen{}\left\\{\pi\in\Pi([d])\;\text{s.t.}\;\mathopen{}\left|P_{i}^{\pi}\right|\mathclose{}\geq
pd\right\\}\mathclose{},$

and define partial Shapley values as

$\phi^{p}_{i}(\nu)=\frac{1}{d!}\sum_{\pi\in\Pi_{i}^{p}}\mathopen{}\left(\nu(P^{\pi}_{i}\cup\mathopen{}\left\\{i\right\\}\mathclose{})-\nu(P^{\pi}_{i})\right)\mathclose{}.$
(C.1)

Since the (full) Shapley values are the unique attribution method that fulfil
the criteria of symmetry, linearity, null player and efficiency, we loose at
least one property. We now show that we retain every property except for
efficiency.

##### Symmetry

If two players $i,j$ are equivalent, i.e. $\nu(S\cup i)=\nu(S\cup j)$ for all
coalitions $S$ that contain neither $i$ nor $j$, then the symmetry property
requires $\phi_{i}(\nu)=\phi_{j}(\nu)$.

When choosing a different set of permutations $\Pi_{i}$ for each $i$ then this
property holds as long as the collection
$\mathopen{}\left\\{\Pi_{i}\right\\}\mathclose{}_{i=1}^{d}$ is symmetric in
the sense that $\forall i,j\in[d]:\;\Pi_{i}=\Pi_{j}[i\leftrightarrow j]$,
where $\Pi_{j}[i\leftrightarrow j]$ means that we exchange the position of the
features $i$ and $j$ for every ordering in $\Pi_{j}$. It is easy to see that
for our $\mathopen{}\left\\{\Pi_{i}^{p}\right\\}\mathclose{}_{i=1}^{d}$ this
is indeed the case. Thus all terms in Equation C.1 are symmetric between $i$
and $j$ and thus the partial Shapley values are symmetric.

##### Linearity

Linearity means that $\forall
i\in[d]:\phi_{i}(\nu+\omega)=\phi_{(}\nu)+\phi_{i}(\omega)$. Since the
expression in Equation C.1 is still linear in $\nu$, the linearity property
remains

##### Null Player

The value $\phi_{i}(\nu)$ is zero for any null player $i$, and $i$ is a null
player if $\nu(S)=\nu(S\cup\mathopen{}\left\\{i\right\\}\mathclose{})$ for all
coalitions $S$ that do not contain $i$. This property is trivially true for
the partial Shapley values since all summands are zero for a null player.

##### Efficiency

The partial Shapley values are not necessarily efficient anymore. Consider for
example the characteristic function

$\nu(S)=\begin{cases}1&\mathopen{}\left|S\right|\mathclose{}\geq pd,\\\
0&\mathopen{}\left|S\right|\mathclose{}<pd.\end{cases}$

In this case for every $i\in[d]$ and $\pi\in\Pi^{p}_{i}$ we have
$\nu(P^{\pi}_{i}\cup\mathopen{}\left\\{i\right\\}\mathclose{})=\nu(P^{\pi}_{i})=1$
and thus $\phi^{p}_{i}=0$. In that case $\sum_{i}\phi_{i}(\nu)=0\neq
1=\nu([d])-\nu(\varnothing)$, which is required by the efficiency criterion.

##  D The FW-method

To find a small set of colour features that ensure a sensible move from the
agent we follow the ideas presented in Macdonald et al., (2020) and define a
rate-distortion functional over a convex set. Our setup is slightly
simplified, since we have an advantage in that we can directly deal with
partial input without the need to replace the missing features with random
variables from a base distribution.

Let $\mathbf{x}\in\mathopen{}\left\\{0,1\right\\}\mathclose{}^{3\times 6\times
7}$ be a state describing the game board defined as
$[\mathbf{x}^{r},\mathbf{x}^{r},\mathbf{x}^{o}]$, where
$\mathbf{x}^{r},\mathbf{x}^{b},\mathbf{x}^{o}\in\mathopen{}\left\\{0,1\right\\}\mathclose{}^{6\times
7}$ indicate the fields occupied by the red and blue player as well as the
open fields respectively, as illustrated in Figure 1. For a continuous mask
$\mathbf{m}\in[0,1]^{6\times 7}$ that indicates which colour information to
show, we define the masked state as
$\mathbf{x}[\mathbf{m}]=\mathopen{}\left[\mathbf{m}\odot\mathbf{x}^{r},\mathbf{m}\odot\mathbf{x}^{b},\mathbf{x}^{o}\right]\mathclose{}$,
where $\odot$ is element-wise multiplication. Let
$a^{*}=\operatorname*{argmax}P(\,\cdot\,;\mathbf{x}[\mathbf{m}])$ be the
chosen action by the policy layer, then we define the policy distortion with
regards to the mask $\mathbf{m}$ as

$D^{\text{pol}}(\mathbf{m})=\mathopen{}\left(P(a^{*};\mathbf{x})-P(a^{*};\mathbf{x}[\mathbf{m}])\right)\mathclose{}^{2}.$

For a chosen rate of $k\in\mathbb{N}$ we define the optimal mask $m^{*}$ as

$\mathbf{m}^{*}=\operatorname*{argmin}_{\mathbf{m}\in\mathcal{B}_{k}^{6\times
7}}D^{\text{pol}}(\mathbf{m}),\qquad\text{where}\qquad\mathcal{B}_{k}^{d}=\mathopen{}\left\\{\mathbf{v}\in[0,1]^{d}\,\middle|\,\mathopen{}\left\|\mathbf{v}\right\|\mathclose{}_{1}\leq
k\right\\}\mathclose{}$

is the $k$-sparse polytope (see Pokutta et al., (2020)) with radius $1$
limited to the positive octant. To optimise the objective we use the solver of
Pokutta et al., made available at https://github.com/ZIB-
IOL/StochasticFrankWolfe with 50 iterations. For a given state $\mathbf{s}$
and most likely action $a^{*}$ the FW-method thus returns $\mathbf{m}^{*}$ as
a saliency map. Oftentimes, multiple $m_{i}^{*}$ converge to 1, so we break
ties randomly when selecting the most relevant features according to this
method.

##  E Shapley Sampling for PI-100

compat=1.15  FI PI-500 PI-100 $p_{h}$

Figure 8: Comparison of Shapley Sampling for our different agents. The bars
show how often the method identified the 3 (green), 2 (yellow), 1 (red) or 0
(black) of the three most important game pieces. The method gives the best
results (finding the most pieces) for the PI-50 agent.

We compare the Shapley Sampling approach for the ground-truth task described
in Section 4.3 for different agents in Figure 8. The method works best for the
PI-50 agent with $p_{h}=0.5$, presumable because it uses the most capable
agent with the largest set of permutations that still ensure staying on-
manifold.

##  F Supplementary Tournament Results

We present the number of games of the tournament that ended in draws, as well
as the ones where illegal moves were played in Figure 9.

|
---|---
Figure 9: _Left:_ Rate of draws for each encounter between saliency methods
according to the setup described in Section 5. _Right:_ Rate of illegal moves
by either agent for each encounter.


††thanks: These two authors contributed equally.††thanks: These two authors
contributed equally.

# Reviving the Lieb–Schultz–Mattis Theorem in Open Quantum Systems

Yi-Neng Zhou  Institute for Advanced Study, Tsinghua University, Beijing
100084, China  Xingyu Li  Institute for Advanced Study, Tsinghua University,
Beijing 100084, China  Hui Zhai  Institute for Advanced Study, Tsinghua
University, Beijing 100084, China  Hefei National Laboratory, Hefei 230088,
China  Chengshu Li<EMAIL_ADDRESS>Institute for Advanced Study,
Tsinghua University, Beijing 100084, China  Yingfei Gu
<EMAIL_ADDRESS>Institute for Advanced Study, Tsinghua University,
Beijing 100084, China

(October 2, 2023)

###### Abstract

In closed systems, the celebrated Lieb–Schultz–Mattis (LSM) theorem states
that a one-dimensional locally interacting half-integer spin chain with
translation and spin rotation symmetry cannot have a non-degenerate gapped
ground state. However, the applicability of this theorem is diminished when
the system interacts with a bath and loses its energy conservation. In this
letter, we propose that the LSM theorem can be revived in the entanglement
Hamiltonian when the coupling to bath renders the system short-range
correlated. Specifically, we argue that the entanglement spectrum cannot have
a non-degenerate minimum, isolated by a gap from other states. We further
support the results with numerical examples where a spin-$1/2$ system is
coupled to another spin-$3/2$ chain serving as the bath. Compared with the
original LSM theorem which primarily addresses UV–IR correspondence, our
findings unveil that the UV data and topological constraints also have a
pivotal role in shaping the entanglement in open quantum many-body systems.

Introduction. Over sixty years ago, Lieb, Schultz, and Mattis proved their
celebrated result, now known as the Lieb–Schultz–Mattis (LSM) theorem [1, 2].
They considered a one-dimensional locally interacting half-integer spin chain
with both translation and spin rotation symmetries and showed that this system
cannot have a unique ground state with a finite excitation gap. In other
words, either the ground states are degenerate, or the low energy spectrum is
gapless. This theorem was later generalized to higher dimensions [3, 4] where
the ground state degeneracy can also originate from topological order,
bringing out the connection between the LSM theorem and the search for the
topological spin liquids [5, 6]. In the past decades, extensive studies on the
LSM theorem have revealed its important role in understanding quantum
magnetism and strongly correlated physics [7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]. Nevertheless,
when a quantum system inevitably interacts with the environment, the concept
of the energy spectrum is no longer well-defined. This raises an interesting
issue of whether an LSM-type theorem can still be established for an open
quantum system 111Recently an LSM-type theorem for open systems was proposed
in arXiv 2305.16496 by Kawabata, Sohal, and Ryu. The authors considered the
Lindbladian spectrum instead of the energy spectrum. We will provide an
alternative proposal utilizing the entanglement spectrum..

In closed systems, the LSM theorem essentially states a deep
ultraviolet–infrared (UV–IR) connection. The microscopic details (UV part),
such as the spin per unit cell, non-trivially constrain the long wavelength
(IR part) property of a many-body spin system. To be concrete, we consider the
following spin twist operator

$\hat{U}^{\text{twist}}=e^{i\frac{2\pi}{L}\sum_{j}j\hat{S}^{z}_{j}},$ (1)

where $j$ labels site index and $L$ is the system size. The fact that
$\hat{U}^{\text{twist}}$ anti-commutes with the translation operator $\hat{T}$
when acting on a spin-rotationally invariant state with half-integer spin per
unit cell plays a central role in proving the LSM theorem. Note that this
anti-commutating relation only relies on the intrinsic feature of the Hilbert
space, independent of detailed Hamiltonian forms. Therefore, we anticipate a
certain version of the LSM theorem can also be formulated in open systems.

Figure 1: Comparing the LSM theorem in closed and open systems. (a) In closed
systems, we consider the physical Hamiltonian $\hat{H}$ and the energy
spectrum $E$. (b) In open systems, we consider the entanglement Hamiltonian
$\hat{K}$ and the entanglement spectrum $\lambda$. These two spectra exhibit
the same features, i.e. either gapless or degenerate ground states, when the
LSM theorem holds.

When coupled to a bath, the system generically becomes a mixed state,
described by a density matrix $\rho$. We write $\rho$ as $\rho=e^{-\hat{K}}$
where $\hat{K}$ is called the entanglement Hamiltonian whose spectrum is
called the entanglement spectrum [32]. In this work, we propose that the
natural successor of the energy spectrum for an open-system LSM theorem is the
entanglement spectrum.

Statement and intuition of the open system LSM theorem. Specifically, we
propose an LSM-type theorem for open systems as follows: the low-lying
spectrum of the entanglement Hamiltonian $\hat{K}$ either has a degenerate
minimum or is gapless when the following two conditions are satisfied

  1. 1.

SO$(3)$ symmetry and half-integer representation

They are the key ingredients of the original LSM theorem and can be imposed on
an open system. Namely, we consider a half-integer spin chain coupled to a
bath. Both the translation and spin rotation symmetry in our setting is the
so-called “weak symmetry” for the density matrix $\rho$ of the system [33],
i.e. $\hat{U}\rho\hat{U}^{\dagger}=\rho$ or equivalently

$\hat{U}\hat{K}\hat{U}^{\dagger}=\hat{K},$ (2)

where $\hat{U}$ is either translation or spin rotation acting on the system.
When we have specific modeling of the bath, this weak symmetry condition is
equivalent to requiring the total state of the full system, including the bath
and system-bath coupling, to be invariant under the symmetry.

  2. 2.

Short-range correlation

In contrast to the long-range correlation implied by the closed system LSM
theorem, we assume the spins in the open system are short-range correlated due
to the coupling to the bath, i.e.
$\langle\hat{O}_{i}\hat{O}_{j}\rangle-\langle\hat{O}_{i}\rangle\langle\hat{O}_{j}\rangle\sim
e^{-|i-j|/\xi}$ for local operators $\hat{O}_{i}$ and $\hat{O}_{j}$ at
site-$i$ and $j$ with a finite correlation length $\xi$. The expectation value
$\langle\cdot\rangle$ is taken with respect to the system density matrix
$\rho$. We argue that this is the natural result when a system that satisfies
the LSM theorem is coupled to a bath. For instance, one scenario is that the
system alone is enforced to be gapless by the LSM theorem, while the
system–bath coupling is a relevant perturbation and opens up a finite gap
$\Delta$. Hence, the system and bath together form a gapped ground state with
$\xi\sim 1/\Delta$ roughly the inverse gap. Another scenario is that the
system reaches thermal equilibrium with a thermal bath at inverse temperature
$\beta=1/T$. In this case, $\xi\sim\beta$ is roughly the thermal length.

We compare this open system LSM theorem with the one for closed systems in
Fig. 1. Given that “entanglement” serves a pivotal role in our proposal, we
may alternatively call this open system LSM theorem as the entanglement LSM
theorem.

Before discussing the details, we first present a special case to gain some
physical intuitions on how the open system entanglement spectrum is related to
the energy spectrum. Let us consider two spin-1/2 chains labeled by $a$ and
$b$ with the same Hamiltonian $\hat{H}_{a,b}=\hat{H}$ that obeys the
conditions for the original LSM theorem, e.g. we assume
$\hat{H}=J\sum_{i}\hat{\bf S}_{i}\cdot\hat{\bf S}_{i+1}$ is the anti-
ferromagnetic Heisenberg model. We then turn on a strong inter-chain anti-
ferromagnetic coupling of strength $\Delta$ and treat $\hat{H}_{a,b}$ as
perturbations.

$a$$b$

To the zeroth order, each rung forms a singlet with the singlet–triplet energy
gap $\Delta$ and $\Delta\gg J$ is much larger than the typical energy scale of
$\hat{H}_{a,b}$. The wave function is a product of spin singlets

$\ket{0}=\frac{1}{2^{L/2}}\bigotimes_{i=1}^{L}(\ket{\uparrow}_{i,a}\ket{\downarrow}_{i,b}-\ket{\downarrow}_{i,a}\ket{\uparrow}_{i,b}),$
(3)

where $i$ labels sites. Now, including the $1$st order change of the
wavefunction induced by the perturbation $\hat{H}_{a,b}$, we have

$\ket{\psi}\propto|0\rangle-\frac{1}{2\Delta}(\hat{H}_{a}+\hat{H}_{b})|0\rangle\approx
e^{-\beta(\hat{H}_{a}+\hat{H}_{b})/2}|0\rangle,$ (4)

with $\beta=1/\Delta$. In the first step, we have simplified the $1$st order
perturbation theory using the property that the Heisenberg Hamiltonian
$\hat{H}_{a,b}$ flips exactly two singlets to triplets and therefore the
energy difference is always $2\Delta$. Furthermore, one can show that the
quantum state $\ket{0}$ can be re-written as

$\ket{0}=\frac{1}{2^{L/2}}\sum_{n}\ket{E_{n}}_{a}\ket{\overline{E_{n}}}_{b},$
(5)

where $\\{\ket{E_{n}}\\}$ is the set of complete eigenstates of $\hat{H}$ and
the overbar denotes time reversal. With Eq. (5), it is straightforward to
trace out the “bath” $b$ in state $|\psi\rangle$ and obtain the reduced
density matrix for $a$, which is proportional to $e^{-\beta\hat{H}}$.
Therefore, the entanglement spectrum satisfies the LSM theorem.

Towards an information theoretical proof. Now, we present a few steps that we
believe are the keys towards a rigorous proof of the open system LSM theorem.

The first step is to argue that the state in question is a quantum approximate
Markov state. This involves the notion of (conditional) mutual information.
For two disjoint subsystems $A$ and $B$, the mutual information measuring the
correlation between $A$ and $B$ is defined as $I(A:B)\equiv
S_{A}+S_{B}-S_{AB}$, where $S$ is the von Neumann entropy of a subsystem
labeled by its subscript. Then, the conditional mutual information between
three disjoint subsystems $A$, $B$, and $C$ is defined as $I(A:C|B)\equiv
I(A:BC)-I(A:B)=S_{AB}+S_{BC}-S_{B}-S_{ABC}$. The vanishing of the conditional
mutual information (i.e. $I(A:C|B)=0$) roughly means that all correlations
between $A$ and $C$ are bridged by $B$ and there is no direct correlation
between $A$ and $C$. Consequently, a quantum Markov state is defined as the
state satisfying $I(A:C|B)=0$. Now, consider the tripartition $A$, $B$, and
$C$ shown in Fig. 2(a), where $B$ shields $A$ from $C$. When the total system
is short-range correlated, we expect that $I(A:C|B)<\varepsilon$, where
$\varepsilon$ is a small parameter controlled by $e^{-l/\xi}$ with $l$ the
size of subsystem $B$ and $\xi$ a correlation length. Such a state is called a
quantum $\varepsilon$-approximate Markov state [34, 35, 36, 37]. While the
exponential decay behavior is beyond rigorous proof so far, it is consistent
with our numerics which will be discussed momentarily.

The second step is to show that the entanglement Hamiltonian of a quantum
approximate Markov state is local. For a quantum Markov state with
$I(A:C|B)=0$, it is known that the entanglement Hamiltonian is strictly local
(finite range), more specifically,
$\hat{K}_{ABC}=\hat{K}_{AB}+\hat{K}_{BC}-\hat{K}_{B}$ and therefore the
entanglement Hamiltonian $\hat{K}$ for a large patch can be decomposed into a
sum of the entanglement Hamiltonian for smaller patches [38]. Now, for a
quantum approximate Markov state with $\varepsilon\sim e^{-l/\xi}$, we
conjecture that the corresponding entanglement Hamiltonian $\hat{K}$ is
exponentially local, namely, the coefficients for non-local terms decay
exponentially with the range of the term.

The third step is to show that the spectral gap of $\hat{K}$ vanishes in the
$L\rightarrow\infty$ limit. Following the idea of the original LSM theorem and
admitting the exponential locality of $\hat{K}$, we can estimate the “mismatch
energy” (the energy cost induced by the spin twist) as follows

$\displaystyle\langle\hat{K}\rangle_{\rm twist}-\langle\hat{K}\rangle_{0}$
$\displaystyle\sim L\int_{0}^{\infty}e^{-l/\xi}\left(1-\cos\Big{(}\frac{2\pi
l}{L}\Big{)}\right)dl$ (6)
$\displaystyle\sim\frac{4\pi^{2}\xi^{3}}{L}-\frac{16\pi^{4}\xi^{5}}{L^{3}}+\ldots$

Here the expectation value $\langle\cdot\rangle_{0}$ is taken on the ground
state of $\hat{K}$ and $\langle\hat{K}\rangle_{\rm twist}=\langle\hat{U}^{\rm
twist\dagger}\hat{K}\hat{U}^{\rm twist}\rangle_{0}$ with the twist operator
$\hat{U}^{\rm twist}$ defined in Eq. (1). Since the ground state is orthogonal
to the twisted ground state that carries a different momentum as enforced by
the non-trivial commutation relation between $\hat{U}^{\rm twist}$ and
translation operator $\hat{T}$, the entanglement spectral gap is upper bounded
by the above mismatch energy and therefore vanishes at $L\rightarrow\infty$,
given $\xi$ a constant independent of $L$.

Figure 2: (a) The tripartition $A$, $B$ and $C$ of the spin chain as used in
the proof. (b) Schematic of the model used in our numerical example. The upper
chain with spin-$1/2$ denotes the system and the lower chain with spin-$3/2$
denotes the bath. They are coupled and the entire system respects translation
and spin rotation symmetries. (c) The log–linear plot of the conditional
mutual information $I(A:C|B)$ (see text for definition) as a function of the
size of the subsystem $B$. (d) The log–linear plot of the spin–spin
correlation function $|\langle{\hat{\bf S}}_{i,s}\cdot{\hat{\bf
S}}_{j,s}\rangle|$ of system “$s$” as a function of the distance $|i-j|$ under
the ground state $|0\rangle_{H}$ of the physical Hamiltonian $\hat{H}$ (blue
dots) and the ground state $|0\rangle_{K}$ of the entanglement Hamiltonian
$\hat{K}$ (orange squares). Note $|0\rangle_{K}$ lives in the Hilbert space of
system $s$, which is a subspace of total Hilbert space where $|0\rangle_{H}$
lives.

Numerical Examples. Now, we present numerical examples to illustrate the
results more concretely 222The codes for our numerical calculations are
available at https://github.com/chengshul/entLSM.. As shown in Fig. 2(b), we
let a spin-$1/2$ chain be the system in consideration and another spin-$3/2$
chain be the bath, which is reminiscent of a larger Hilbert space of the bath.
The physical Hamiltonian of our first example is written as follows

$\hat{H}=\sum_{i=1}^{L}J_{1}\big{(}\hat{\bf{S}}_{i}\cdot\hat{\bf{S}}_{i+1}+\frac{1}{3}(\hat{\bf{S}}_{i}\cdot\hat{\bf{S}}_{i+1})^{2}\big{)}+J_{2}\hat{\bf{S}}_{i,s}\cdot\hat{\bf{S}}_{i,b},$
(7)

where $\hat{\bf{S}}_{i}=\hat{\bf{S}}_{i,s}+\hat{\bf{S}}_{i,b}$ is the sum of
spin operators acting respectively on the system and bath, and $J_{1,2}>0$.
$\hat{\bf{S}}_{i,s}$ and $\hat{\bf{S}}_{i,b}$ are the spin operators for the
system and bath respectively. At each rung, the $J_{2}$-term is minimized by
forming a spin triplet, rendering the $J_{1}$ term into the
Affleck–Kennedy–Lieb–Tasaki (AKLT) Hamiltonian [40]. This Hamiltonian has a
gapped excitation spectrum and a unique ground state. We construct the model
in this way such that its ground state wavefunction can be written down
explicitly with the matrix product state representation. We let the total
system stay in the ground state $|0\rangle_{H}$ of this Hamiltonian. Knowing
the exact many-body wavefunction, we can obtain the reduced density matrix
$\rho=\mathrm{tr}_{b}\left(|0\rangle\langle 0|_{H}\right)$ of the system
“$s$”, and therefore, the entanglement Hamiltonian $\hat{K}=-\ln\rho$, to a
fairly large system size.

In Fig. 2(c), we first demonstrate the aforementioned statement on conditional
mutual information, which is a crucial step in locality discussion. We plot
$I(A:C|B)$ as a function of the system size of $B$ (the tripartition of $A$,
$B$ and $C$ are shown in Fig. 2(a)), from which we see clearly an exponential
decay as we discussed above. The decay length is found to be approximately
$0.38$, which is of the same order as the correlation length of spin operators
$\xi\approx 0.91$ on the ground state of the $\hat{H}$ as shown in Fig. 2(d)
(blue dots). For comparison, we also compute the spin correlation function in
the ground state $|0\rangle_{K}$ of the entanglement Hamiltonian $\hat{K}$
shown by the orange squares in Fig. 2(d), which confirms the implications of
our entanglement LSM theorem that the state $|0\rangle_{K}$ cannot be short
range correlated.

Figure 3: (a) The entanglement spectrum with momentum and total spin resolved.
The dashed line is given by $\lambda=v|\sin{k}|+\lambda_{0}$, with $v$ and
$\lambda_{0}$ obtained from the two lowest points at $k=0,2\pi/L$. The
calculation is done for $L=16$. (b)
$\langle\hat{K}\rangle_{\text{twist}}-\langle\hat{K}\rangle_{0}$ (blue points)
and $-\ln\langle\rho\rangle_{\text{twist}}-\langle\hat{K}\rangle_{0}$ (orange
squares) are plotted as a function of the total system length $L$. Both
quantities are upper bounds of the entanglement spectral gap $\Delta\lambda$
of the entanglement Hamiltonian $\hat{K}$. The dotted lines are fitting curves
with $c_{0}+c_{1}/L+c_{3}/L^{3}$. The $1/L^{2}$ term and all higher even order
terms vanish due to the inversion symmetry generated by
$\exp(i\pi\sum_{j}S_{j}^{x})$. The fitting results are
$(c_{0},c_{1},c_{3})=(0.0014,3.8,-19)$ and $=(0.00013,3.6,-23)$ for
$\langle\hat{K}\rangle_{\text{twist}}-\langle\hat{K}\rangle_{0}$ and
$-\ln\langle\rho\rangle_{\rm twist}-\langle\hat{K}\rangle_{0}$ respectively.
Note the ratio of coefficients $-c_{1}/c_{3}<3/\pi^{2}$ is consistent with the
expectation from expanding a “mismatch” energy $\propto 1-\cos\left(2\pi
r/L\right)$, where $r\in\mathbb{Z}$ is the range of the coupling. The ratio
reaches the maximum $3/\pi^{2}$ when only nearest neighbor terms are involved.

Next, we calculate the spectral properties of $\hat{K}$ to show the vanishing
of the spectral gap in the large system size limit. First, for a total system
size $L=16$, we compute the entire entanglement spectrum, as shown in Fig.
3(a). This spectrum is consistent with a linear gapless spectrum [41]. Then,
we focus on the entanglement spectral gap (denoted as $\Delta\lambda$)
estimation as discussed above in Eq. (6). We numerically calculate both
$\langle\hat{K}\rangle_{\mathrm{twist}}$ and $\langle\hat{K}\rangle_{0}$ and
fit the difference against $c_{0}+c_{1}/L+c_{3}/L^{3}$. A less intuitive but
numerically more feasible quantity is $-\ln\langle\rho\rangle_{\rm
twist}-\langle\hat{K}\rangle_{0}$ where $\langle\rho\rangle_{\rm
twist}=\langle\hat{U}^{\mathrm{twist}\dagger}\rho\hat{U}^{\mathrm{twist}}\rangle_{0}$.
Using the convexity of the function $-\ln(x)$, it can be shown that this
quantity provides a tighter bound as follows

$\Delta\lambda\leqslant-\ln\langle\rho\rangle_{\rm
twist}-\langle\hat{K}\rangle_{0}\leqslant\langle\hat{K}\rangle_{\text{twist}}-\langle\hat{K}\rangle_{0}.$
(8)

We demonstrate the numerical results of both quantities in Fig. 3(b). As shown
in the data, the finite size scaling supports the statement that the
entanglement spectral gap $\Delta\lambda$ vanishes at the thermodynamic limit
$L\rightarrow\infty$. Similar numerical results have also been reported
previously for two coupled spin-$1/2$ chains [42], which can be regarded as
another example supporting our result.

The second model we consider is a spin-1/2 Majumdar–Ghosh (MG) chain [43]
coupled to a spin-3/2 bath, where we expect the entanglement Hamiltonian to
exhibit spontaneous symmetry breaking. The model reads

$\displaystyle\hat{H}=\sum_{i=1}^{L}\leavevmode\nobreak\ \leavevmode\nobreak$
$\displaystyle J_{1}(\hat{\bf{S}}_{i,s}\cdot\hat{\bf
S}_{i+1,s}+\frac{1}{2}\hat{\bf{S}}_{i,s}\cdot\hat{\bf{S}}_{i+2,s})$ (9)
$\displaystyle+\leavevmode\nobreak$ $\displaystyle
J_{2}\hat{\bf{S}}_{i,s}\cdot\hat{\bf{S}}_{i,b}+D(\hat{S}_{i,s}^{z}+\hat{S}_{i,b}^{z})^{2}.$

Here we have introduced an anisotropic coupling $D$ and set $J_{1}=J_{2}=D=1$
in the numerics. Note that we now have O(2) instead of SO(3) global symmetry,
which too suffices for LSM theorem [2]. The ground state reduces to a product
state of $|S=1,S_{z}=0\rangle$ in the $J_{1}\rightarrow 0$ limit, and remains
trivially gapped for $J_{1}=1$ which we have checked numerically. In Fig. 4 we
plot the energy spectrum of the original MG model and the entanglement
spectrum. In both cases, a doubly degenerate ground state energy/entanglement
eigenvalue characteristic of SSB is observed.

Figure 4: (a) The energy spectrum of the original Majumdar–Ghosh model. (b)
The entanglement spectrum of the Majumdar–Ghosh model coupled to a spin-3/2
bath, Eq. (9). In both cases, we have the system length $L=8$.

Summary and Outlook. For a spin chain where the original LSM theorem was
valid, coupling to the bath overturns the prediction of the LSM theorem. Such
coupling can turn the local operators short-range correlated. However,
precisely because of the short-ranged correlation, the entanglement
Hamiltonian acquires locality, a key ingredient for the revival of the LSM
theorem in the entanglement spectrum of an open quantum system.

In this letter, we show that familiar topological constraints on the energy
spectrum can be extended to the entanglement spectrum of an open system that
is entangled with the environment. While compared with existing literature
relating the non-trivial topology and the entanglement spectrum such as the
Li–Haldane conjecture [32] where a one-dimensional entanglement cut is
performed on a two-dimensional topological state, the entanglement cut
discussed in our work is in the same dimension as the system. It will also be
interesting to systematically explore the connections between these two
scenarios [44, 45, 46].

In closed systems, the developments of the LSM-type theorem have revealed its
rich content, including the generalization to more sophisticated on-site and
space groups [8, 9, 11, 14], symmetry-protected and enriched topological
systems [10, 12, 13, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26], and fermionic
systems [20, 21, 28]. These studies have shown an enormous impact on
topological and correlated quantum phases. Following the progress made in this
work, all these generalizations could also be discussed in the content of
entanglement Hamiltonian for open systems. In parallel to the closed systems,
these studies may also strongly impact the understanding of topology and
correlation in open quantum many-body systems, an area on the frontier of the
current theoretical research [47, 48, 49, 50, 51, 52, 53, 54, 55, 56] and
practically relevant to the quantum simulators in the NISQ era [57, 58].

Acknowledgement. We thank Zhen Bi, Meng Cheng, Chao-Ming Jian, Shenghan Jiang,
Chong Wang and Chao Yin for discussions. This work is supported by the
Innovation Program for Quantum Science and Technology 2021ZD0302005, the
Beijing Outstanding Young Scholar Program, the XPLORER Prize, NSFC Grant No.
12042505, China Postdoctoral Science Foundation Grant No. 2022M711868 and
Tsinghua University Dushi Program. C.L. is also supported by the Chinese
International Postdoctoral Exchange Fellowship Program and the Shuimu Tsinghua
Scholar Program at Tsinghua University. The DMRG calculations are performed
using the ITensor library (v0.3) [59].

## References

  * Lieb  _et al._ [1961] E. Lieb, T. Schultz, and D. Mattis, Two soluble models of an antiferromagnetic chain, Ann. Phys. 16, 407 (1961).
  * Affleck and Lieb [1986] I. Affleck and E. H. Lieb, A proof of part of Haldane’s conjecture on spin chains, Lett. Math. Phys. 12, 57 (1986).
  * Oshikawa [2000] M. Oshikawa, Commensurability, Excitation Gap, and Topology in Quantum Many-Particle Systems on a Periodic Lattice, Phys. Rev. Lett. 84, 1535 (2000).
  * Hastings [2004] M. B. Hastings, Lieb-Schultz-Mattis in higher dimensions, Phys. Rev. B 69, 104431 (2004).
  * Lee [2008] P. A. Lee, An End to the Drought of Quantum Spin Liquids, Science 321, 1306 (2008).
  * Balents [2010] L. Balents, Spin liquids in frustrated magnets, Nature 464, 199 (2010).
  * Affleck [1989] I. Affleck, Quantum spin chains and the Haldane gap, J. Phys.: Condens. Matter 1, 3047 (1989).
  * Chen  _et al._ [2011] X. Chen, Z.-C. Gu, and X.-G. Wen, Classification of gapped symmetric phases in one-dimensional spin systems, Phys. Rev. B 83, 035107 (2011).
  * Parameswaran  _et al._ [2013] S. A. Parameswaran, A. M. Turner, D. P. Arovas, and A. Vishwanath, Topological order and absence of band insulators at integer filling in non-symmorphic crystals, Nat. Phys. 9, 299 (2013).
  * Zaletel and Vishwanath [2015] M. P. Zaletel and A. Vishwanath, Constraints on Topological Order in Mott Insulators, Phys. Rev. Lett. 114, 077201 (2015).
  * Watanabe  _et al._ [2015] H. Watanabe, H. C. Po, A. Vishwanath, and M. Zaletel, Filling constraints for spin-orbit coupled insulators in symmorphic and nonsymmorphic crystals, Proc. Natl. Acad. Sci. U.S.A. 112, 14551 (2015).
  * Cheng  _et al._ [2016] M. Cheng, M. Zaletel, M. Barkeshli, A. Vishwanath, and P. Bonderson, Translational symmetry and microscopic constraints on symmetry-enriched topological phases: A view from the surface, Phys. Rev. X 6, 041068 (2016).
  * Cho  _et al._ [2017] G. Y. Cho, C.-T. Hsieh, and S. Ryu, Anomaly manifestation of Lieb-Schultz-Mattis theorem and topological phases, Phys. Rev. B 96, 195105 (2017).
  * Po  _et al._ [2017] H. C. Po, H. Watanabe, C.-M. Jian, and M. P. Zaletel, Lattice Homotopy Constraints on Phases of Quantum Magnets, Phys. Rev. Lett. 119, 127202 (2017).
  * Huang  _et al._ [2017] S.-J. Huang, H. Song, Y.-P. Huang, and M. Hermele, Building crystalline topological phases from lower-dimensional states, Phys. Rev. B 96, 205106 (2017).
  * Lu [2017] Y.-M. Lu, Lieb-Schultz-Mattis theorems for symmetry protected topological phases (2017), arXiv:1705.04691 .
  * Yang  _et al._ [2018] X. Yang, S. Jiang, A. Vishwanath, and Y. Ran, Dyonic Lieb-Schultz-Mattis theorem and symmetry protected topological phases in decorated dimer models, Phys. Rev. B 98, 125120 (2018).
  * Jian  _et al._ [2018] C.-M. Jian, Z. Bi, and C. Xu, Lieb-Schultz-Mattis theorem and its generalizations from the perspective of the symmetry-protected topological phase, Phys. Rev. B 97, 054412 (2018).
  * Metlitski and Thorngren [2018] M. A. Metlitski and R. Thorngren, Intrinsic and emergent anomalies at deconfined critical points, Phys. Rev. B 98, 085140 (2018).
  * Fidkowski  _et al._ [2018] L. Fidkowski, A. Vishwanath, and M. A. Metlitski, Surface topological order and a new ’t hooft anomaly of interaction enabled 3+1d fermion spts (2018), arXiv:1804.08628 [cond-mat.str-el] .
  * Cheng [2019] M. Cheng, Fermionic Lieb-Schultz-Mattis theorems and weak symmetry-protected phases, Phys. Rev. B 99, 075143 (2019).
  * Ogata and Tasaki [2019] Y. Ogata and H. Tasaki, Lieb–Schultz–Mattis Type Theorems for Quantum Spin Chains Without Continuous Symmetry, Commun. Math. Phys. 372, 951 (2019).
  * Else and Thorngren [2020] D. V. Else and R. Thorngren, Topological theory of Lieb-Schultz-Mattis theorems in quantum spin systems, Phys. Rev. B 101, 224437 (2020).
  * Lu  _et al._ [2020] Y.-M. Lu, Y. Ran, and M. Oshikawa, Filling-enforced constraint on the quantized Hall conductivity on a periodic lattice, Ann. Phys. 413, 168060 (2020).
  * Jiang  _et al._ [2021] S. Jiang, M. Cheng, Y. Qi, and Y.-M. Lu, Generalized Lieb-Schultz-Mattis theorem on bosonic symmetry protected topological phases, SciPost Phys. 11, 024 (2021).
  * Ye  _et al._ [2022] W. Ye, M. Guo, Y.-C. He, C. Wang, and L. Zou, Topological characterization of Lieb-Schultz-Mattis constraints and applications to symmetry-enriched quantum criticality, SciPost Phys. 13, 066 (2022).
  * Gioia and Wang [2022] L. Gioia and C. Wang, Non-zero momentum requires long-range entanglement, Phys. Rev. X 12, 031007 (2022).
  * Zheng  _et al._ [2022] W. Zheng, D. N. Sheng, and Y.-M. Lu, Unconventional quantum phase transitions in a one-dimensional Lieb-Schultz-Mattis system, Phys. Rev. B 105, 075147 (2022).
  * Tasaki [2022] H. Tasaki, The Lieb-Schultz-Mattis Theorem: A Topological Point of View, in  _The Physics and Mathematics of Elliott Lieb_, Vol. 2, edited by R. L. Frank, A. Laptev, M. Lewin, and R. Seiringer (European Mathematical Society Press, 2022) pp. 405–446.
  * Cheng and Seiberg [2023] M. Cheng and N. Seiberg, Lieb-Schultz-Mattis, Luttinger, and ’t Hooft - anomaly matching in lattice systems, SciPost Phys. 15, 051 (2023).
  * Note [1] Recently an LSM-type theorem for open systems was proposed in arXiv 2305.16496 by Kawabata, Sohal, and Ryu. The authors considered the Lindbladian spectrum instead of the energy spectrum. We will provide an alternative proposal utilizing the entanglement spectrum.
  * Li and Haldane [2008] H. Li and F. D. M. Haldane, Entanglement Spectrum as a Generalization of Entanglement Entropy: Identification of Topological Order in Non-Abelian Fractional Quantum Hall Effect States, Phys. Rev. Lett. 101, 010504 (2008).
  * Buča and Prosen [2012] B. Buča and T. Prosen, A note on symmetry reductions of the Lindblad equation: Transport in constrained open spin chains, New J. Phys. 14, 073007 (2012).
  * Fawzi and Renner [2015] O. Fawzi and R. Renner, Quantum conditional mutual information and approximate markov chains, Commun. Math. Phys. 340, 575 (2015).
  * Kato and Brandão [2019] K. Kato and F. G. S. L. Brandão, Quantum Approximate Markov Chains are Thermal, Commun. Math. Phys. 370, 117 (2019).
  * Svetlichnyy and Kennedy [2022] P. Svetlichnyy and T. A. B. Kennedy, Decay of quantum conditional mutual information for purely generated finitely correlated states, J. Math. Phys. 63, 072201 (2022).
  * Svetlichnyy  _et al._ [2022] P. Svetlichnyy, S. Mittal, and T. Kennedy, Matrix product states and the decay of quantum conditional mutual information (2022), arXiv:2211.06794 .
  * Petz [2003] D. Petz, Monotonicity of quantum relative entropy revisited, Rev. Math. Phys. 15, 79 (2003).
  * Note [2] The codes for our numerical calculations are available at https://github.com/chengshul/entLSM.
  * Affleck  _et al._ [1987] I. Affleck, T. Kennedy, E. H. Lieb, and H. Tasaki, Rigorous Results on Valence-Bond Ground States in Antiferromagnets, Phys. Rev. Lett. 59, 799 (1987).
  * [41] For further numerical discussions and results, see C. Li et al., to appear.
  * Poilblanc [2010] D. Poilblanc, Entanglement Spectra of Quantum Heisenberg Ladders, Phys. Rev. Lett. 105, 077202 (2010).
  * Majumdar and Ghosh [1969] C. K. Majumdar and D. K. Ghosh, On Next-Nearest-Neighbor Interaction in Linear Chain. I, J. Math. Phys. 10, 1388 (1969).
  * Qi  _et al._ [2012] X.-L. Qi, H. Katsura, and A. W. W. Ludwig, General Relationship between the Entanglement Spectrum and the Edge State Spectrum of Topological Quantum States, Phys. Rev. Lett. 108, 196402 (2012).
  * Hsieh and Fu [2014] T. H. Hsieh and L. Fu, Bulk Entanglement Spectrum Reveals Quantum Criticality within a Topological State, Phys. Rev. Lett. 113, 106801 (2014).
  * Gu  _et al._ [2016] Y. Gu, C. H. Lee, X. Wen, G. Y. Cho, S. Ryu, and X.-L. Qi, Holographic duality between $(2+1)$-dimensional quantum anomalous Hall state and $(3+1)$-dimensional topological insulators, Phys. Rev. B 94, 125107 (2016).
  * Bardyn  _et al._ [2013] C.-E. Bardyn, M. A. Baranov, C. V. Kraus, E. Rico, A. İmamoğlu, P. Zoller, and S. Diehl, Topology by dissipation, New J. Phys. 15, 085001 (2013).
  * Dasbiswas  _et al._ [2018] K. Dasbiswas, K. K. Mandadapu, and S. Vaikuntanathan, Topological localization in out-of-equilibrium dissipative systems, Proc. Natl. Acad. Sci. U.S.A. 115, E9031 (2018).
  * Wanjura  _et al._ [2020] C. C. Wanjura, M. Brunelli, and A. Nunnenkamp, Topological framework for directional amplification in driven-dissipative cavity arrays, Nat. Commun. 11, 3149 (2020).
  * Gneiting  _et al._ [2022] C. Gneiting, A. Koottandavida, A. V. Rozhkov, and F. Nori, Unraveling the topology of dissipative quantum systems, Phys. Rev. Res. 4, 023036 (2022).
  * Leefmans  _et al._ [2022] C. Leefmans, A. Dutt, J. Williams, L. Yuan, M. Parto, F. Nori, S. Fan, and A. Marandi, Topological dissipation in a time-multiplexed photonic resonator network, Nat. Phys. 18, 442 (2022).
  * Bao  _et al._ [2023] Y. Bao, R. Fan, A. Vishwanath, and E. Altman, Mixed-state topological order and the errorfield double formulation of decoherence-induced transitions (2023), arXiv:2301.05687 .
  * Fan  _et al._ [2023] R. Fan, Y. Bao, E. Altman, and A. Vishwanath, Diagnostics of mixed-state topological order and breakdown of quantum memory (2023), arXiv:2301.05689 .
  * Mao  _et al._ [2023] L. Mao, F. Yang, and H. Zhai, Dissipation Dynamics Driven Transitions of the Density Matrix Topology (2023), arXiv:2301.04345 .
  * Ma  _et al._ [2023] R. Ma, J.-H. Zhang, Z. Bi, M. Cheng, and C. Wang, Topological Phases with Average Symmetries: The Decohered, the Disordered, and the Intrinsic (2023), arXiv:2305.16399 .
  * Su  _et al._ [2023] K. Su, N. Myerson-Jain, and C. Xu, Conformal Field Theories generated by Chern Insulators under Quantum Decoherence (2023), arXiv:2305.13410 .
  * Preskill [2018] J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Altman  _et al._ [2021] E. Altman, K. R. Brown, G. Carleo, L. D. Carr, E. Demler, C. Chin, B. DeMarco, S. E. Economou, M. A. Eriksson, K.-M. C. Fu, M. Greiner, K. R. A. Hazzard, R. G. Hulet, A. J. Kollar, B. L. Lev, M. D. Lukin, R. Ma, X. Mi, S. Misra, C. Monroe, K. Murch, Z. Nazario, K.-K. Ni, A. C. Potter, P. Roushan, M. Saffman, M. Schleier-Smith, I. Siddiqi, R. Simmonds, M. Singh, I. B. Spielman, K. Temme, D. S. Weiss, J. Vuckovic, V. Vuletic, J. Ye, and M. Zwierlein, Quantum Simulators: Architectures and Opportunities, PRX Quantum 2, 017003 (2021).
  * Fishman  _et al._ [2022] M. Fishman, S. R. White, and E. M. Stoudenmire, The ITensor Software Library for Tensor Network Calculations, SciPost Phys. Codebases , 4 (2022).