# Information Content based Exploration

Jacob Chmura  Hasham Burhani  Xiao Qi Shi

###### Abstract

Sparse reward environments are known to be challenging for reinforcement
learning agents. In such environments, efficient and scalable exploration is
crucial. Exploration is a means by which an agent gains information about the
environment; we expand on this topic and propose a new intrinsic reward that
systemically quantifies exploratory behaviour and promotes state coverage by
maximizing the information content of a trajectory taken by an agent. We
compare our method to alternative exploration-based intrinsic reward
techniques, namely Curiosity Driven Learning (CDL) and Random Network
Distillation (RND). We show that our information-theoretic reward induces
efficient exploration and outperforms in various games, including Montezuma’s
Revenge – a known difficult task for reinforcement learning. Finally, we
propose an extension that maximizes information content in a discretely
compressed latent space which boosts sample-efficiency and generalizes to
continuous state spaces.

Reinforcement Learning, Exploration, Information, Entropy

††RBC Capital Market, Toronto, Canada. Correspondence to: Jacob Chmura
(jacob.chmura@rbccm.com), Hasham Burhani (hasham.burhani.rbccm.com), Xiao Qi
Shi<EMAIL_ADDRESS>
##  1 Introduction

Given an agent without knowledge of the environment dynamics, a fundamental
question is: what should the agent learn first? When the task is also unknown,
the question becomes increasingly complex (Moerland et al., 2020)(Riedmiller
et al., 2018). In reward-dense environments, the agent receives a continuous
gradient signal that guides learning through interaction (Mnih et al.,
2013)(Achiam & Sastry, 2017)(Hong et al., 2018)(Haarnoja et al., 2018).
However, for many problems of interest, the most faithful reward specification
is sparse, degrading the sample efficiency with which online algorithms can
learn desirable policies (Tim Salimans, 2018)(Vecerik et al., 2017)(Singh et
al., 2019)(Sekar et al., 2020).

Figure 1: ICE (top) efficiently explores the no-reward grid environment. State
visitation is more uniform as compared to Random Walk (bottom left) and RND
(bottom right), which have low visitation density in the area opposite the
agent start location (top left of grid). ICE incentives trajectories with
distinct states, contrary to action space entropy which often revisiting the
same states multiple times in a cyclic fashion.

To date, there have been a variety of ways in which this has been addressed. A
common approach is to leverage domain knowledge to artificially shape the
reward function into one amenable to credit assignment (Ng et al., 1999).
However, engineered rewards require extensive domain knowledge, suffer from
human cognitive bias, and often lead to unintended consequences (Clark &
Amodei, 2016). Another popular method has been to induce random exploration
through entropy maximization in the action space (Ahmed et al., 2019). This
heuristic induces random walk behavior, as seen in Fig.1, and therefore
suffers from scalability issues in high-dimensional state spaces: the
probability of traveling far from the starting state is reduced exponentially
(Fig.2).

At the same time, curiosity-driven learning enables humans to explore complex
environments efficiently and integrate novel experiences in preparation for
future tasks (Kidd & Hayden, 2015). Recent work has focused on emulating
curiosity in reinforcement learning agents through intrinsic reward bonuses
such as pseudo-counts (Bellemare et al., 2016) and variational information
gain (Houthooft et al., 2016). CDL uses a form of state dynamics prediction
error to entice the agent to visit unfamiliar states (Burda et al., 2018a).
Similarly, RND uses random features as a learning target for a curiosity
model, the error of which is used as an intrinsic reward; neural network
prediction error is observed to be a good proxy for novelty and hence
quantifies exploration progress (Burda et al., 2018b). We contribute to the
family of curiosity-inspired exploration methods by proposing an information
theory-driven intrinsic reward that induces effective exploration policies
without introducing auxiliary models or relying on approximations of
environment dynamics.

Figure 2: A random exploration strategy works with fairly high probability if
the solution can be achieved in a small distance traveled from the origin. As
can be seen above, as the distance from origin $K$ increases, the probability
of success decreases exponentially for the same episode length $N$. See A.2 in
the Appendix for derivation.

Information Content-based Exploration (ICE) introduces an intrinsic reward
that maximizes information gain in the state space. In each episode of
interaction with the environment, we aggregate trajectory statistics to
approximate the entropy of the state visitation distribution and reward the
agent for relative improvements to this measure. This approach formalizes the
exploration process as seeking low-density states but can easily accommodate
prior knowledge of the environment by replacing entropy with KL-divergence to
a desired state density, similar to (Lee et al., 2020).

We run several experiments comparing ICE’s performance against RND and CDL
using A3C (Mnih et al., 2016) as our base RL algorithm to show that ICE
significantly outperforms RND and CDL in various environments. We also observe
that ICE exploration exhibits trajectories akin to depth-first search. In most
environments, this offers the best opportunity to find extrinsic rewards,
where the agent must decisively commit to a path through the environment
rather than dithering locally via action entropy. Finally, we discuss
extensions to our approach that generalize to continuous state spaces by
maximizing information content on a hashed latent space extracted from an
auto-encoder architecture.

##  2 Background

We briefly cover A3C in section 2.1, and introduce the Source Coding Theorem
which provides the theoretical justification for using entropy in the state
space for exploration in ICE. In 2.3 and 2.4, we cover Curiosity Driven
Learning and Exploration by Random Network Distillation algorithms.

###  2.1 Actor Critic Algorithm

We consider a parametric policy
$\pi_{\theta}\in\Pi:=\\{\pi_{\theta}:\theta\in\Theta\\}$ interacting with a
discounted Markov Decision Process
$\mathcal{M}=$($\mathcal{S},\mathcal{A},\gamma,\mathcal{P},r$). At each time
step $t$, the policy outputs an action $a_{t}\sim\pi_{\theta}(\cdot|s_{t})$
that leads to the next state $s_{t+1}$ according to the transition kernel
$\mathcal{P}(s_{t+1}|s_{t},a_{t})$. The environment also provides an extrinsic
reward $r_{t}\sim(s_{t},a_{t})$. The objective is to maximize the expected
discounted cumulative reward
$\mathcal{J}(\pi)=\mathbb{E}_{\pi}(\sum_{t=0}^{\mathcal{T}}\gamma^{t}r_{t})$.
The critic is an auxiliary model with parameters $\phi\in\Phi$ that reduces
the variance of the policy gradient by approximating the value function:
$\hat{V}_{\phi}^{\pi}(s_{t})\approx\mathbb{E}_{\pi}[\sum_{k}\gamma^{k}r_{t+k+1}|s_{t}]$.

The Actor-Critic method maximizes the objective $\mathcal{J}$ by optimizing
the model’s weights based on value loss, policy loss, and entropy loss, which
have the form

$\begin{split}L_{value,t}&=\alpha_{value}(r_{t}+\gamma
V_{\phi}(s_{t+1})-V_{\phi}(s_{t}))^{2}\\\
L_{policy,t}&=\alpha_{policy}(-A_{t}\log\pi_{\theta}(a_{t}|s_{t}))\\\
L_{entropy,t}&=\alpha_{entropy}(-\mathbb{H}(\pi_{\theta}(\cdot|s_{t})))\end{split}$
(1)

where $\alpha_{value},\alpha_{policy},\alpha_{entropy}$ are the weight
coefficients of the three losses, $\pi_{\theta}(a_{t}|s_{t})$ is the
probability of the selected action policy,
$\mathbb{H}(\pi_{\theta}(\cdot|s_{t}))$ is the entropy of the policy.
In addition, $k$-step Advantage estimate $A_{t}$ is defined to be

$A_{t}=\sum_{i=0}^{k-1}(\gamma^{i}r_{t+i})+\gamma^{k}V_{\phi}(s_{t+k})-V_{\phi}(s_{t})$
(2)

In the case where the intrinsic reward is present, the reward $r_{t}$ is the
weighted sum of intrinsic and extrinsic reward,

$r_{t}=r^{extrinsic}_{t}+\beta r^{intrinsic}_{t}$ (3)

where $\beta$ is the weight coefficient of the intrinsic reward.

The k-step state distribution induced by a policy $\pi$ is given by:

$\displaystyle d_{k,\pi}(s)$
$\displaystyle=\mathbb{E}_{\begin{subarray}{c}s_{1}\sim\rho_{0}(\cdot)\\\
a_{t}\sim\pi(\cdot|s_{t})\\\
s_{t+1}\sim\mathcal{P}(\cdot|s_{t},a_{t})\end{subarray}}[\frac{1}{k}\sum_{t=1}^{k}1(s_{t}=s)]$
(4)

###  2.2 Source Coding Theorem

Given a list of discrete elements $L=\\{l_{0},l_{1},...,l_{t}\\}$,
$l_{i}\in\mathbb{R}^{1}$, the Source Coding Theorem states that $L$ can be
compressed into no less than $H^{L}_{t}\times(t+1)$ bits, where $H^{L}_{t}$ is
the entropy of $L$ up to step $t$.

######  Theorem 2.1 (Source Coding Theorem (Shannon, 1948), $D=1$).

A single random variable (D=1) with entropy $H$ can be compressed into at
least $H$ bits without risk of information loss.

We note that the joint entropy is sub-additive, with equality when the random
variables are independent (Aczel et al., 1974):

$H(X_{1},...,X_{n})\leq\sum_{i}H(X_{i})$ (5)

We also note that up to a constant, the entropy of a discrete random variable
$X:\mathcal{X}\to\\{1,...,K\\}$ distributed according to $p$ is given by
$-D_{KL}(p,\mu)$ where $\mu$ is the uniform distribution on $\mathcal{X}$, and
$D_{KL}$ is the KL divergence:

$\displaystyle D_{KL}(p,\mu)$
$\displaystyle=\sum_{k=1}^{K}p(X=k)log\frac{p(X=k)}{K^{-1}}$ (6)
$\displaystyle=logK+\sum_{k=1}^{K}p(X=k)logp(X=k)$ (7)
$\displaystyle=logK-\mathbb{H}(X)$ (8)

Hence, maximizing the state distribution entropy is equivalent to minimizing
the reverse KL to the uniform distribution over state.

###  2.3 Curiosity Driven Learning (CDL)

This branch of exploration provides an intrinsic reward based on the agent’s
familiarity with the current state; curiosity-driven Exploration by Self-
supervised Prediction (Pathak et al., 2017) is one of the popular approaches.
It formulates the intrinsic reward by using three neural networks to estimate
state encoding, forward dynamics, and inverse dynamics. The first neural
network $f_{encode}(s)$ encodes $s_{t}\mapsto g_{t}$ and $s_{t+1}\mapsto
g_{t+1}$. Then a second neural network $f_{forward}(g_{t},a_{t})$ estimates
the next state encoding $\hat{g}_{t+1}$. Lastly, the third neural network
$f_{inverse}(g_{t},g_{t+1})$ estimates the transition action distribution
$\hat{a_{t}}$. The training loss and intrinsic reward have the form

$\begin{split}L_{forward_{t}}&=\alpha_{forward}MSE(g_{t+1}-\hat{g_{t+1}})\\\
L_{inverse_{t}}&=\alpha_{inverse}CrossEntropy(\hat{a_{t}},a_{t})\\\
r_{intrinsic_{t}}&=\beta L_{inverse_{t}}\end{split}$ (9)

The agent will naturally favor states that it cannot accurately predict the
transition action from $s_{t}$ to $s_{t+1}$.

###  2.4 Exploration by Random Network Distillation (RND)

Exploration by Random Network Distillation (Burda et al., 2018b) follows the
same design philosophy as Curiosity Driven Learning. It formulates the
intrinsic reward by using two neural networks. The first neural network
$f_{random}(s)$, encodes $s_{t}\mapsto g_{t}$. It is randomly initialized and
will not get updated. The second neural network $f_{encode}(s)$, encodes
$s_{t}\mapsto\hat{g}_{t}$. The training loss and intrinsic reward have the
form

$\begin{split}&L_{encode_{t}}=\alpha_{encode}MSE(g_{t+1},\hat{g_{t+1}})\\\
&r_{intrinsic_{t}}=\beta L_{inverse_{t}}\end{split}$ (10)

where $\alpha_{encode}$ and $\beta$ are coefficients. This method encourages
the agent to explore in states where $f_{encode}$ cannot accurately predict
the random encoding.

##  3 Information Content-based Exploration (ICE)

###  3.1 Motivation

While interacting with the environment, we view the t-step state sequence
$s_{1},...,s_{t}$ as a 1-sample Monte-Carlo approximation to the t-step state
distribution $\hat{d}_{t,\pi}(s)\approx d_{t,\pi}(s)$ induced by the agent
$\pi$. Supposing that our state space $\mathcal{S}$ is isomorphic to
$\textbf{K}^{D}:=\\{1,2,..,K\\}^{D}$, then we can compute 111An efficient
vectorized implementation can be found in the supplemental code. the empirical
entropy of the t-step state sequence $\hat{d}_{t,\pi}(s)$:

$\mathbb{H}(\hat{d}_{t,\pi}(s))=-\sum_{x\in\textbf{K}^{D}}\hat{p}(x)log\hat{p}(x)$
(11)

in $\mathcal{O}(t\cdot K^{D})$. For computational reasons, we view each state
trajectory as composed of $D$ _independent_ state elements (e.g., frames of a
video made up of $D$ pixels) which reduces the complexity to
$\mathcal{O}(t\cdot K\cdot D)$:

$\sum_{x\in\textbf{K}^{D}}\hat{p}(x)log\hat{p}(x)\approx\sum_{d\in
D}\sum_{k\in\textbf{K}}\hat{p}(x_{d}=k)log\hat{p}(x_{d}=k)$ (12)

We provide an intrinsic reward to the agent based on the _relative
improvement_ of this measure across time steps. Thus, we optimize for the
approximate derivative of state entropy. We view several benefits to using the
relative improvement measure:

  * •

Intrinsic stochasticity (e.g. persistent white noise) has high Shannon entropy
but low fundamental information content (since the data is non-compressible).
The relative improvement measure nullifies such entropy sources.

  * •

Let $\delta_{t}\geq 0$ be the sub-additivity gap introduced by assuming our
state-sequence $s_{1},...,s_{t}$ is independent. If $\delta_{t}$ is relatively
constant across time then the relative improvement measure cancels out the
overestimation of state entropy introduced by our independence assumption.

In 3.2 we give an efficient algorithm for computing the intrinsic ICE reward,
then, in 3.4 we discuss a principled approach to state discretization, which
enables us to compute ICE in continuous state spaces.

###  3.2 Algorithm

Let us define a _trajectory_ , $X_{t}$, to be the list of states collected
from the same episode up to step $t$, $X_{t}=[s_{0},s_{1},...,s_{t}]$, where
each state $s_{t}$ is a collection of _state elements_ ,
$s_{t}=[s_{t}^{0},s_{t}^{1},...,s_{t}^{D-1}]\in\mathbb{R}^{D}$. To collect the
total information in a trajectory, we first calculate the information content
received over each _state element_ in a trajectory.

Figure 3: A trajectory is the collection of all states traversed by the agent
in sequence. State element trajectory is the collection of elements from the
same position in all states in a trajectory.

Consider an arbitrary state element $d$ in a trajectory up to step $t$,
$X^{d}_{t}=[s_{0}^{d},s_{1}^{d},...,s_{t}^{d}]$. We can calculate the count
for each unique value within $X^{d}_{t}$.

$q^{d}_{t}=CountUnique(X^{d}_{t})$ (13)

Next, we can calculate the probability of each unique value occurrence within
$X^{d}_{t}$.

$p^{d}_{t}=\frac{q^{d}_{t}}{t+1}$ (14)

For example, if $X^{d}_{t=4}=[a,a,b,a,c]$, then $q^{d}_{t=4}=[3,1,1]$ and
$p^{d}_{t=4}=[3/5,1/5,1/5]$.

We can then obtain the entropy for $X^{d}_{t}$ by applying Shannon’s entropy
to $p^{d}_{t}$.

$H^{d}_{t}=Entropy(p^{d}_{t})=-\sum_{k}p^{d}_{t}[k]\log_{2}p^{d}_{t}[k]$ (15)

$H^{d}_{t}$ measures the information content of the $d^{th}$ state element
trajectory. The information content of the full trajectory can be calculated
by summing over all state elements.

$H_{t}=\sum_{d}H^{d}_{t}$ (16)

We then denote $r^{intrinsic}_{t}$ as

$r^{intrinsic}_{t}=H_{t}-H_{t-1}$ (17)

Intuitively, $r^{intrinsic}_{t}$ represents the amount of additional
information $s_{t}$ brings to the trajectory $[s_{0},s_{1},...,s_{t-1}]$. Note
that $\sum r^{intrinsic}_{t}=H_{T}$, which is the total information content of
the entire trajectory. A numerical example of $r^{intrinsic}_{t}$ calculation
can be found in Appendix A.3.

Algorithm 1 Information Content-based Intrinsic Reward

Input: Model $M$

repeat

Input: state $s_{0}$, $H_{last}\leftarrow 0$, $t\leftarrow 0,\ done\leftarrow
False$

Input: unique count dictionary $q$

$q\leftarrow Update(q,s_{0})$, from Eq.13

$H_{last}\leftarrow CalculateICE(q)$, from Eq.16

while not $done$ do

$a_{t}\leftarrow M(s_{t})$

$s_{t+1},r^{extrinsic}_{t},done\leftarrow env.step(a_{t})$

$q\leftarrow Update(q,s_{t+1})$

$H_{current}\leftarrow CalculateICE(q)$

$r^{intrinsic}_{t}\leftarrow H_{current}-H_{last}$

$r_{t}\leftarrow r^{extrinsic}_{t}+\beta r^{intrinsic}_{t}$

$H_{last}\leftarrow H_{current}$

$t\leftarrow t+1$

end while

Update model $M$

until Model $M$ Converge

This formulation of the $r^{intrinsic}$ requires no estimation, as it can be
calculated directly from the trajectory of states. By maintaining count arrays
of size $D\times K$, we can efficiently implement Alg. 1 using vectorized CPU
or GPU operations. See the supplementary Material for our implementation.

###  3.3 State Exploration vs Action Exploration

ICE is a state space exploration algorithm and assumes the environment to be
an observable Markov Decision Process. This assumption is necessary because
ICE measures the information content of the observable state trajectory.

ICE encourages the agent to efficiently explore the trajectory containing the
most information content at the cost of disincentivizing the agent from
pursuing trajectories with low information. Therefore, ICE offers no guarantee
that every state in the decision process will be visited. On the other hand,
action space exploration (Eq.1) encourages the agent to take actions based on
uniform distribution. Albeit inefficient, it does guarantee that the agent
will eventually visit all states in an environment.

State space exploration is fundamentally different than action space
exploration. They are complements to each other. In the case where the agent
is driven only by the action of space exploration, the agent can reach all
reachable states, but the expected amount of time required can be very long.
On the other hand, an agent driven only by state space exploration can reach
more distinct states in significantly less amount of time, but it is no longer
guaranteed to reach all reachable states. The probability of reaching a reward
is proportional to the percent of all possible states reached. As shown in
Fig.4, The agent with high state exploration and low action exploration can
potentially reach rewards in a shorter amount of time but with a possibility
that it may never reach all the rewards. Therefore, it is important to balance
the weighting of these two types of explorations in order to explore
optimally, illustrated in (Fig.4) and 4.3.

Figure 4: As we increase the action exploration and decrease the state
exploration, it takes significantly longer to reach the same amount of
distinct states (blue line). In the case where we decide to only apply state
exploration, the agent will be able to efficiently follow the trajectory with
very rich information content, at the cost of never visiting states in the low
information content trajectories. As a result, such an agent will almost never
reach all the states (red line).

###  3.4 ICE in a Learned Latent Space

A trajectory’s information content depends on how we choose to discretize the
state space; naturally, different discretization methods will change the
absolute information content. Selecting the appropriate discretization is only
possible with prior knowledge of the environment. We propose to address this
by using an auto-encoder to learn a compressed, low-dimensional discrete
representation upon which information is maximized. Computing ICE on the
latent manifold decouples the ICE formulation from the dimensionality of the
observation space. The information bottleneck principle (Tishby et al., 1999)
allows us to trade between _sufficiency_ and _minimality_ in our discrete
representation.

Since the KL divergence is parameterization-invariant, we can be sure that
insofar as our auto-encoder learns an invertible representation of the state
space, computing ICE in latent space should lead to desirable exploration
behaviour as in discrete settings. We validate this procedure in 4.4.

####  3.4.1 Motivation

We put $\mathcal{D}=\\{d:\mathcal{S}\to\mathbb{R}_{\geq 0}\\}$ to be the set
of distributions over the state space, and we consider functionals
$\mathcal{R}(\cdot)$ that describe how desirable a given state distribution
is. If we take $\mathcal{R}(d)=\mathbb{H}(d)$ on a discrete space we recover
the formulation of 3.2. More generally, if we have some target distribution
$d^{*}$, we can consider the reverse KL:

$\displaystyle\mathcal{R}_{d^{*}}(\cdot)=D_{KL}(\cdot,d^{*})$ (18)

We consider the family of measurable surjective maps:
$\mathcal{F}:\\{\mathcal{S}\to\mathcal{Z}\\}$, where $\mathcal{Z}$ is a
discrete space of dimensions $k\leq dim(\mathcal{S})$. The inverse set map
partitions $\mathcal{S}$, giving rise to the following relation:

$\displaystyle d_{1}\sim^{f}d_{2}\iff f_{*}(d_{1})=f_{*}(d_{2})$ (19)

where $f_{*}()$ is the push-forward measure on $\mathcal{Z}$. We let:

$\displaystyle[\mu]_{f}=\\{d\in\mathcal{D}:d\sim^{f}\mu\\}=f^{-1}(Unif_{z})$
(20)

denote the subset of state distributions whose projection onto $\mathcal{Z}$
by $f$ result in the uniform distribution.

Then we put:

$\displaystyle\mathcal{R}_{f}(\cdot)=D_{KL}(\cdot,[\mu]_{f})=\mathbb{H}[f(\cdot)]$
(21)

In words, we think about $f$ as a filter that represents various invariants on
our state space $\mathcal{S}$. All state distribution that map uniformly on
$\mathcal{Z}$ by $f$ are considered equally desirable, and we reward
trajectories with high information content from the _lens_ of $f$.

####  3.4.2 Learning the latent Representation

We let $\mathcal{Z}$ arise as a discrete bottleneck
$\mathcal{S}\to^{e}\mathcal{Z}\to^{d}\mathcal{S}^{\prime}$ from aiming to
reconstruct state as best as possible, thereby inducing a representation
$\mathcal{Z}$ that maximizes mutual information with $\mathcal{S}$. A smoothly
parameterizes encoder (e.g. neural network) will ensure that similar states
get mapped to similar codes. Hence, maximizing information content on
$\mathcal{Z}$ will further encourages diverse trajectories on $\mathcal{S}$.

To discretize the latent space, we use _locality sensitive hashing_ (LSH)
(Zhao et al., 2014). LSH is helpful because state dimensions that are highly
coupled (from an information-theoretic view), will be hashed to the same
latent code by our auto-encoder whose projections to a lower dimension filter
out small perturbations. On the other hand, a novel experiences will project
to different latent subspace and thus will be prescribed a unique hash code.
This approach decouples the ICE procedure from the state-space dimensionality,
and can be directly applied to continuous spaces.

We follow the discretization pipeline similar to (Tang et al., 2017), using a
_Simhash_ (Charikar, 2002) scheme with a auto-encoder. Namely, for an encoder
$e:\mathcal{S}\to\mathbb{R}^{D}$, a decoder $d:\mathbb{R}^{D}\to\mathcal{S}$,
fixed stochastic matrix $A\in\mathbb{R}^{k\times D}$ with
$A_{ij}\sim\mathcal{N}(0,1)$, we retrieve the discrete latent code for state
$s$ according to:

$z(s)=sgn(A\sigma(\mathcal{U}_{(-a,a)}+e(s)))\in\\{-1,1\\}^{k}$ (22)

where $\sigma(\cdot)$ denotes element-wise application of the sigmoid
function, and $\mathcal{U}_{(-a,a)}$ is the injection of uniform noise to
force the latent space to behave discretely (Hubara et al., 2016), (Maddison
et al., 2016).

The encoder and decoder are parameterized by convolution neural networks,
jointly trained with the reinforcement learning policy on a lagged updated
schedule to ensure the latent codes are stable while retaining the ability to
adjust based on exploratory progress of the agent. The auto-encoder optimizes
a log likelihood term and an auxiliary loss that ensures unused latent bits
take on an arbitrary binary value, preventing spurious latent code
fluctuations (Tang et al., 2017):

$\mathcal{L}(\\{s_{i}\\}_{i=1}^{N})=-\frac{1}{N}\sum_{i=1}^{N}[logp(s_{i})-\newline
\frac{\lambda}{K}\sum_{i=1}^{D}g(s_{i})]$ (23)
$g(s_{i}):=min\\{(1-e(s_{i}),e(s_{i})\\}$ (24)

The algorithm for running ICE on a learned latent space is given in Alg.2. We
note that using learned hash codes involves minimal changes to the base ICE
algorithm, requiring only that (1) states pass through the encoder and
_SimHash_ prior to computing ICE reward, and (2) a buffer of approximately
reconstructed state trajectories is stored to periodically updating the auto-
encoder based on Eq.23.

Algorithm 2 Information Content-based Intrinsic Reward in Learned Latent Space

Input: Model $M$, Encoder $e:\mathcal{S}\to\mathbb{R}^{D}$, Decoder
$d:\mathbb{R}^{D}\to\mathcal{S}$, Fixed Gaussian matrix
$A\in\mathbb{R}^{k\times D}$. Buffer $\mathcal{B}$

repeat

Input: state $s_{0}$, $H_{last}\leftarrow 0$, $t\leftarrow 0,\ done\leftarrow
False$

Input: unique count dictionary $q$

$z_{0}\leftarrow Encode(s_{0},e,A)$, from Eq.22

$\hat{s_{0}}\leftarrow Decode(s_{0},z_{0},d)$

$\mathcal{B}\leftarrow(s_{0},z_{0},\hat{s_{0}})$ add to buffer

$q\leftarrow Update(q,z_{0})$, from Eq.13

$H_{last}\leftarrow CalculateICE(q)$, from Eq.16

while not $done$ do

$a_{t}\leftarrow M(s_{t})$

$s_{t+1},r^{extrinsic}_{t},done\leftarrow env.step(a_{t})$

$z_{t+1}\leftarrow Encode(s_{t+1},e,A)$, from Eq.22

$\hat{s_{t+1}}\leftarrow Decode(s_{t+1},z_{t+1},d)$

$\mathcal{B}\leftarrow(s_{t+1},z_{t+1},\hat{s_{t+1}})$ add to buffer

$q\leftarrow Update(q,z_{t+1})$

$H_{current}\leftarrow CalculateICE(q)$

$r^{intrinsic}_{t}\leftarrow H_{current}-H_{last}$

$r_{t}\leftarrow r^{extrinsic}_{t}+\beta r^{intrinsic}_{t}$

$H_{last}\leftarrow H_{current}$

$t\leftarrow t+1$

end while

Update model $M$

if iteration mod $ae_{update}=0$ then

update encoder $e$ and decoder $d$ with data from buffer $\mathcal{B}$
according to Eq. 23

end if

until Model $M$ Converge

##  4 Experiment

We compare information content based intrinsic reward with several other
methods from the literature described in Section $2$. The selected
environments include Grid-World, along with a group of sparse reward Atari
games. All of the environments in this experiment are reduced to $40\times 40$
dimensionality and discretized using 255 gray scale range. We use a single
convolution neural network with LSTM layers and seperate value and policy
heads to parameterize the actor and critic. Details are given in A.5.

The unique count matrix $Q$ (Eq.13) is preset to be $Zeros(40,40,C)$ at the
beginning of each trajectory, where $C$ is the number of unique values for
each pixel. The algorithm will dynamically update the matrix $P$ and then
calculate the trajectory information content after each step.

###  4.1 Grid-World

The state space for grid world is a $40\times 40$ grid (Fig.8 left). The agent
starts at the (0,0) position and it can take action from
$\\{up,down,left,right\\}$. The grid visited by the agent is labeled as 1,
otherwise 0, the extrinsic reward by the environment is always 0, and the
environment terminates after 400 steps.
As shown in (Fig.5), the agent is able to explore up to 300 distinct states in
every trajectory with ICE enabled, which is significantly more than the case
when ICE is disabled. The trajectory information content also increases as the
number of distinct states increases.

Figure 5: ICE motivates agent to reach a significantly higher number of
distinct states which is correlated with an increase in information content.
Measured in a no-reward grid-world environment.

###  4.2 Atari

We compare ICE with A3C, CDL, and RND on several environments from Atari.
Firstly we compare the methods of Pong and Breakout, Fig.6. The performance of
ICE is slightly worse than A3C. This is because these two environments both
have very rich reward systems. They do not necessarily require an exploration
signal in order to solve. In these environments, the intrinsic rewards are
noise rather than a signal to the model. Nonetheless, ICE will not degrade the
performance by a lot as long as we keep it to a relatively small magnitude. As
a result, ICE is able to solve both environments efficiently.

Figure 6: Performance on simple Atari Environments, cumulative reward (left),
information content (right)

The second set of environments is Pong with Sparse Reward, Super Mario, and
Montezuma, Fig.7. These are challenging for RL algorithms due to their
extremely sparse reward system. In Pong with Sparse Reward, all of the rewards
were accumulated and provided to the model at the last step. In Super Mario,
the agent gets no reward during learning and gets properly rewarded during
evaluation (see A.4 for more details). In Montezuma, the agent will only get a
positive reward if the character reaches a key. These environments require the
agent to precisely follow an action trajectory in order to solve the problem.
In all cases, the ICE agent outperformed the base A3C agent. The learning for
ICE is also very efficient as focuses on efficiently exploring the state
space. ICE also displays interesting behaviors in the Montezuma Revenge
environment. In the early stages, the agent focuses on exploring distinct
states as it receives no rewards. As soon as it lands on a key, it quickly
shifts its focus towards maximizing the extrinsic reward. Simultaneously, the
intrinsic reward quickly degrades. Shortly after, the agent tries to regain
the intrinsic reward while still being able to reach the key. As shown in the
right column of Fig.6,7, ICE is very correlated with the environment’s reward
system, because Atari games such as Pong and Breakout have deterministic and
observable state spaces, which gives a clear measure of information content
using ICE. In general, ICE is a very robust exploration method because it is
not very sensitive to hyper-parameters and is not prediction-based.

Figure 7: Performance on Sparse Reward Environments, cumulative reward (left),
information content (right).

###  4.3 Grid-World with Wall

This is a special case of the Grid-World to illustrate the idea of 3.3. The
basic setup is the same as described in 4.1, with differences shown in Fig.8.
The block of the wall marked in black represents states the agent cannot
visit. On top of this, the grids marked in blue are unobservable, as they will
always be filled with 0, and the grids marked in yellow are standard (turns to
1 if visited, else 0). The agent will get a positive reward and terminate the
game if it has reached the green grid. The agent with ICE is efficiently
exploring yellow grids, but it is having trouble exploring blue grids and
cannot land on the green grid. This is because the agent quickly converged to
take the path in yellow grids, as it can generate higher information content
compared to a path in blue grids. On the other hand, the agent without ICE is
able to land at the green grid after a while of random search (Fig.9). This is
a limitation of ICE that can be overcome by simply including action
exploration.

Figure 8: Setup of grid world (left) and grid world with wall (right). The
agent will always start at the top-left corner. Yellow grids are observable,
turn to 1 when visited. Blue grids are non-observable, always filled with 0.
Black grids are walls that agents cannot step into. Green grid gives a
positive reward to the agent. Figure 9: The agent with ICE is exploring
efficiently in yellow grids but is not able to make it to the green grid. The
agent without ICE finds the green grid after a few rounds of random search and
quickly converges to this path.

###  4.4 ICE in a Learned Latent Space

We evaluate how well ICE performs when computed on a learned latent space,
following the procedure of 3.4.2, on several environments including Pong,
Breakout, Montezuma’s revenge and Starpilot. The encoder consists of 3
convolution blocks followed by a linearity outputting a $128$-dimensional
dense representation which is hashed into $k=16$-dimensional latent codes. The
decoder consists of 3 deconvolution blocks. We use $\lambda=0.5$ for the
auxiliary auto-encoder loss, and update the auto-encoder every 3 updates of
the base policy. This architecture is inspired by the representation learning
stack from (Tang et al., 2017), which aim to achieve high reconstruction
accuracy to help stabilize the learned latent space, and thereby make our ICE
reward more consistent.

The extrinsic reward learning curves are shown in 3.4.2. We observe that
working in a compressed representation can be beneficial, even for state
spaces that are already discrete (e.g. images). In Pong and Starpilot, ICE in
latent space improves the speed of learning, suggesting that the bottlecked
representation helps regularize against sporadic noise in our state
trajectories.

In Montezuma’s revenge, optimizing for ICE in latent space exhibits
asymptotically better extrinsic rewards, suggesting that maximizing
information content on the compressed representation is better able to capture
semantically meaningful subspaces worth exploring.

We believe that these initial results are promising, and we are motivated to
further experiment with ICE rewards on various representation spaces.

Figure 10: Comparing performance of ICE reward in learned latent space
(orange) vs. ICE reward directly on uniformly discretized pixels (blue).
Optimizing the ICE reward on the learned latent space improves sample-
efficiency in Pong, Starpilot and Montezuma.

##  5 Conclusion

We have introduced a new intrinsic reward based on the information content of
trajectories measured using Shannon’s Entropy. Our method is amenable to
vectorized implementation and has shown robustness in various observable
MDP’s. ICE motivates the agent to explore diversified trajectories, thereby
increasing its sample-efficiency in sparse environments where the probability
of receiving a reward is directly proportional to the number of distinct
visited states. We discussed a discretization scheme 3.4 based on locality
sensitive hashing that maximizing information content on a compressed latent
space, generalizing ICE reward to continuous state spaces. We also examined
the limitations of motivating agents to traverse trajectories with a large
number of distinct states in 4.3.

##  6 Future Work

The idea of this work is loosely related to depth-first search (DFS). By
analogy, action state exploration is a cyclic breadth-first search (BFS). We
believe that there is opportunity to improve ICE by dynamically shifting
between DFS and BFS behaviour as the agent interacts with the environment. We
also posit that changing the formulation to incorporate information _across_
multiple episodes can yields better results. For example, we can maximize
information content of the current trajectory while minimizing the mutual
information with previous experience; we leave this to future work. Finally,
we’ve observed promising results using ICE on a learned latent representation.
In future work, we wish to further validate this process by evaluating it
using different representations such as the _successor representation_
(Machado et al., 2023), and rigorously testing sensitivity to hash-dimension
on continuous spaces.

## Software and Data

We include an A3C and a PPO implementation of ICE in the Supplementary
Material.

## References

  * Achiam & Sastry (2017) Achiam, J. and Sastry, S.  Surprise-based intrinsic motivation for deep reinforcement learning.  _arXiv preprint arXiv:1703.01732_ , 2017.
  * Aczel et al. (1974) Aczel, J., B.Forte, and NG, C. T.  Why the shannon and hartley entropies are natural.  _Applied Probability Trust_ , 6:131–146, 1974.
  * Ahmed et al. (2019) Ahmed, Z., Le Roux, N., Norouzi, M., and Schuurmans, D.  Understanding the impact of entropy on policy optimization.  In _International conference on machine learning_ , pp. 151–160. PMLR, 2019.
  * Bellemare et al. (2016) Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R.  Unifying count-based exploration and intrinsic motivation.  _Advances in neural information processing systems_ , 29, 2016.
  * Burda et al. (2018a) Burda, Y., Edwards, H., Pathak, D., Storkey, A., Darrell, T., and Efros, A. A.  Large-scale study of curiosity-driven learning.  _arXiv preprint arXiv:1808.04355_ , 2018a.
  * Burda et al. (2018b) Burda, Y., Edwards, H., Storkey, A., and Klimov, O.  Exploration by random network distillation.  _arXiv preprint arXiv:1810.12894_ , 2018b.
  * Charikar (2002) Charikar, M. S.  Similarity estimation techniques from rounding algorithms.  _ACM Symposium on Theory of Computing_ , 34:380–388, 2002\.
  * Clark & Amodei (2016) Clark, J. and Amodei, D.  Faulty reward functions in the wild, 2016.  URL https://openai.com/research/faulty-reward-functions.
  * Dutka (1991) Dutka, J.  The early history of the factorial function.  _Archive for history of exact sciences_ , pp. 225–249, 1991.
  * Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Hartikainen, K., Tucker, G., Ha, S., Tan, J., Kumar, V., Zhu, H., Gupta, A., Abbeel, P., et al.  Soft actor-critic algorithms and applications.  _arXiv preprint arXiv:1812.05905_ , 2018.
  * Hong et al. (2018) Hong, Z.-W., Shann, T.-Y., Su, S.-Y., Chang, Y.-H., Fu, T.-J., and Lee, C.-Y.  Diversity-driven exploration strategy for deep reinforcement learning.  _Advances in neural information processing systems_ , 31, 2018.
  * Houthooft et al. (2016) Houthooft, R., Chen, X., Duan, Y., Shulman, J., De Turck, F., and Abbeel, P.  Variational information maximization exploration.  _Advances in neural information processing systems_ , 29, 2016.
  * Hubara et al. (2016) Hubara, I., Matthieu, C., Soudry, D., El-Yaniv, R., and Bengio, Y.  Binarized neural networks.  _Advances in neural information processing systems_ , 30, 2016.
  * Kauten (2018) Kauten, C.  Super Mario Bros for OpenAI Gym.  GitHub, 2018.  URL https://github.com/Kautenja/gym-super-mario-bros.
  * Kidd & Hayden (2015) Kidd, C. and Hayden, B.  The psychology and neuroscience of curiosity.  _Neuron_ , 88:449–460, 2015.
  * Lee et al. (2020) Lee, L., Eysenbach, B., Parisotto, E., Xing, E., Levine, S., and Salakhutdinov, R.  Efficient exploration via state marginal matching.  _arXiv preprint arXiv:1906.05274_ , 2020.
  * Machado et al. (2023) Machado, M. C., Barreto, A., Precup, D., and Bowling, M.  Temporal abstraction in reinforcement learning with the successor representation.  _Journal of Machine Learning Research_ , 24, 2023.
  * Maddison et al. (2016) Maddison, C. J., Mnih, A., and Teh, Y. W.  The concrete distribution: A continuous relaxation of discrete random variables.  _arXiv preprint arXiv:1611.00712_ , 2016.
  * Mnih et al. (2013) Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_ , 2013.
  * Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K.  Asynchronous methods for deep reinforcement learning.  In _International conference on machine learning_ , pp. 1928–1937. PMLR, 2016.
  * Moerland et al. (2020) Moerland, T. M., Broekens, J., and Jonker, C. M.  Model-based reinforcement learning: A survey.  _arXiv preprint arXiv:2006.16712_ , 2020.
  * Ng et al. (1999) Ng, A., Harada, D., and Russell, S.  Policy invariance under reward transformations: Theory and application to reward shaping.  _International conference on machine learning_ , 16:278–287, 1999.
  * Pathak et al. (2017) Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T.  Curiosity-driven exploration by self-supervised prediction.  In _International conference on machine learning_ , pp. 2778–2787. PMLR, 2017.
  * Riedmiller et al. (2018) Riedmiller, M., Hafner, R., Lampe, T., Neunert, M., Degrave, J., Wiele, T., Mnih, V., Heess, N., and Springenberg, J. T.  Learning by playing solving sparse reward tasks from scratch.  In _International conference on machine learning_ , pp. 4344–4353. PMLR, 2018.
  * Sekar et al. (2020) Sekar, R., Rybkin, O., Daniilidis, K., Abbeel, P., Hafner, D., and Pathak, D.  Planning to explore via self-supervised world models.  In _International Conference on Machine Learning_ , pp. 8583–8592. PMLR, 2020.
  * Shannon (1948) Shannon, C. E.  A mathematical theory of communication.  _The Bell system technical journal_ , 27(3):379–423, 1948.
  * Singh et al. (2019) Singh, A., Yang, L., Hartikainen, K., Finn, C., and Levine, S.  End-to-end robotic reinforcement learning without reward engineering.  _arXiv preprint arXiv:1904.07854_ , 2019.
  * Tang et al. (2017) Tang, H., Houthooft, R., Foote, D., Stooke, A., Chen, X., Duan, Y., Schulman, J., DeTurck, F., and Abbeel, P.  A study of count-based exploration for deep reinforcement learning.  _Advances in neural information processing systems_ , 31, 2017.
  * Tim Salimans (2018) Tim Salimans, R. C.  Learning montezuma’s revenge from a single demonstration.  https://openai.com/blog/learning-montezumas-revenge-from-a-single-demonstration/, 2018\.
  * Tishby et al. (1999) Tishby, N., Pereira, F., , and Biale, W.  The information bottleneck method.  _Communication, Control and Computing_ , 37:368–377, 1999\.
  * Vecerik et al. (2017) Vecerik, M., Hester, T., Scholz, J., Wang, F., Pietquin, O., Piot, B., Heess, N., Rothörl, T., Lampe, T., and Riedmiller, M.  Leveraging demonstrations for deep reinforcement learning on robotics problems with sparse rewards.  _arXiv preprint arXiv:1707.08817_ , 2017.
  * Zhao et al. (2014) Zhao, K., Lu, H., and Mei, J.  Locality preserving hashing.  _AAAI Conference on Artificial Intelligence_ , 28:2874–2880, 2014.

##  Appendix A Appendix

###  A.1 Hyperparameters

Table 1: Hyperparameters used in our experiments.
| gridworld | gridworldwall | Pong | Montezuma | Mario
---|---|---|---|---|---
lr | $10^{-4}$ | $10^{-4}$ | $10^{-4}$ | $10^{-4}$ | $10^{-4}$
gamma | 0.99 | 0.99 | 0.99 | 0.99 | 0.99
$\alpha_{value}$ | 0.5 | 0.5 | 0.5 | 0.5 | 0.5
$\alpha_{policy}$ | 1.0 | 1.0 | 1.0 | 1.0 | 0.5
$\alpha_{entropy}$ | 0.01 | 0.01 | 0.01 | 0.01 | 0.01
$\beta$ | 0.5 | 0.5 | 0.5 | 1.0 | 0.1

###  A.2 1-D Random Walk Analysis

We want to show by calculation that it is very unlikely an agent can end at
equal or larger than $K$ distances away from the origin after taking $N$
random steps in a 1-dimension grid. As shown in Fig.11, the agent starts at
the 0 position and takes action from left, right randomly. Define the
probability of an agent end at equal or larger than $K$ distances away from
the start position after taking $N$ random steps to be $P_{k}^{N}$.

Figure 11: Setup of a 1-D random walk grid. The agent starts at the 0 position
and takes action from left, right randomly.

In the case where $N\geq K$, it follows from the binomial distribution,

$P_{k}^{N}=\sum_{i=\left\lceil\frac{K+N}{2}\right\rceil}^{N}\binom{N}{i}\left(\frac{1}{2}\right)^{N}$
(25)

For large $N$ and $K\ll N$, we can apply Stirling’s Formula (Dutka, 1991) to
simplify the calculation.

###  A.3 More examples

We will illustrate $r^{intrinsic}_{t}$ by an example. Consider a simple grid
world environment with dimension $1\times 4$. Every grid begins with value
$0$, and changes to 1 on visitation. The agent starts at the leftmost grid.
The agent has $2$ possible actions (left, right). The environment itself
provides no reward, $r^{extrinsic}_{t}=0,\forall\ t$. The game terminates
after $3$ steps. Let’s consider an example trajectory, where the actions are
$left,right,right$.

$s_{0},s_{1},s_{2},s_{3}=[1,0,0,0],[1,0,0,0],[1,1,0,0],[1,1,1,0]$ (26)

Then the trajectory for each state variable up to $t=4$ is

$X^{d=0}_{t=3},X^{d=1}_{t=3},X^{d=2}_{t=3},X^{d=3}_{t=3}=[1,1,1,1],[0,0,1,1],[0,0,0,1],[0,0,0,0]$
(27)

The count unique and probability occurrence vector for each state variable up
to $t=3$ is

$\begin{split}&q^{d=0}_{t=3},q^{d=1}_{t=3},q^{d=2}_{t=3},q^{d=3}_{t=3}=[0,4],[2,2],[3,1],[4,0]\\\
&p^{d=0}_{t=3},q^{d=1}_{t=3},q^{d=2}_{t=3},q^{d=3}_{t=3}=[0/4,4/4],[2/4,2/4],[3/4,1/4],[4/4,0/4]\end{split}$
(28)

The total information content of this trajectory can be calculated as

$\displaystyle\begin{split}&H^{d=0}_{t=3},H^{d=1}_{t=3},H^{d=2}_{t=3},H^{d=3}_{t=3}=0,1,0.81,0\
bits\\\ &H_{t=3}=\sum H^{d}_{t}=1.81\ bits\\\ \end{split}$

Other $H_{t}$ where $t\in[0,1,2]$ can be calculated through the same method,
where $H_{t=0}=0,H_{t=1}=0,H_{t=2}=0.92$. Lastly, the intrinsic reward is

$r^{intrinsic}_{t=3}=H_{t=3}-H_{t=2}=0.89\ bits$ (29)

Note that the agent can increase its information content by visiting more
distinct grids within the trajectory, and the maximum is achieved when all
grids have been visited exactly once within $N$ steps. The grid world
environment is a very representative environment for many sparse reward
environments. They are similar in a way that their exploration objective can
all be described as increasing the probability of reaching a non-zero reward
state by exploring more distinct states.

###  A.4 Super Mario Reward System

The extrinsic reward for the Super Mario environment is always 0 during
learning, and the extrinsic reward during evaluation is as follows (Kauten,
2018),

$\begin{split}&velocity_{t}=position_{t}-position_{t-1}\\\
&clock_{t}=time_{t-1}-time_{t}\\\ &death_{t}=0\ if\ alive\ else\ -15\\\
&r^{extrinsic}_{t}=velocity_{t}+clock_{t}+death_{t}\end{split}$ (30)

###  A.5 Neural Network Architecture

The neural network is designed to be a combination of 4 convolution, 1 LSTM,
and 2 linear layers (Fig.12). The LSTM layer is important here to give the
model a sense of the states it has traveled so far in a trajectory.

Figure 12: Neural Network Structure

###  A.6 Locality Sensitive Hashing

We consider _locality sensitive hashing_. A family of hash functions
$\mathcal{H}=\\{h:\mathcal{S}\to\mathbb{Z}\\}$ is _locality sensitive for a
similarity function s_ : $\mathcal{S}\times\mathcal{S}\to\mathbb{R}$ if a hash
function $h\sim\mathcal{H}$ randomly sampled from the family satisfies:

$\displaystyle d(s_{1},s_{2})$ $\displaystyle\leq R\implies
p(h(s_{1})=h(s_{2})\geq P_{1})$ (31) $\displaystyle d(s_{1},s_{2})$
$\displaystyle\geq C\cdot R\implies p(h(s_{1})=h(s_{2}))\leq P_{2}$ (32)

for some constants $C>1,R>0$ and for probabilities $P_{1},P_{2}\geq 0$. In
other words, points close together are hashed to the same value with high
probability, and dissimilar points are unlikely to collide in hash. Implicit
in this assumption is that $(\mathcal{S},d)$ form a valid metric space.

Locality sensitive hashing enables us to map a continuous, high dimensional
state space into a compressed latent space such that similar points in state
space map to similar latent codes.


# Understanding a Robot’s Guiding Ethical Principles via Automatically
Generated Explanations

Benjamin Krarup1, Felix Lindner2, Senka Krivic3, and Derek Long1 1 Authors are
with the Faculty of Natural and Mathematical Sciences, King’s College London,
Bush House, WC2B 4BG, London, UK<EMAIL_ADDRESS>Lindner is
with the Institute of Artificial Intelligence, Ulm University, 89081 Ulm,
Germany<EMAIL_ADDRESS>Krivic is with Faculty of Electrical
Engineering, University of Sarajevo, 7100 Sarajevo, Bosnia and Herzegovina
<EMAIL_ADDRESS>
###### Abstract

The continued development of robots has enabled their wider usage in human
surroundings. Robots are more trusted to make increasingly important decisions
with potentially critical outcomes. Therefore, it is essential to consider the
ethical principles under which robots operate. In this paper we examine how
contrastive and non-contrastive explanations can be used in understanding the
ethics of robot action plans. We build upon an existing ethical framework to
allow users to make suggestions about plans and receive automatically
generated contrastive explanations. Results of a user study indicate that the
generated explanations help humans to understand the ethical principles that
underlie a robot’s plan.

##  I Introduction

AI Planning systems are used in a variety of complex domains to create a
sequence of actions known as a plan to achieve a set of goals from an initial
state. Automated planning techniques are commonly used in robotics
applications for solving complex high-level tasks, for example, tidying up a
children’s room with a mobile robot [1] or inspection and maintenance missions
for autonomous underwater vehicles (AUVs) [2].

When autonomous systems are tasked with making decisions with potentially
critical outcomes, it is important for them to behave ethically. Take for
example the film “Robot & Frank”111https://www.imdb.com/title/tt1990314/, in
which an aging ex-jewel thief, Frank, is bought a domestic robot to care for
him. Once Frank realises that the robot does not distinguish between what is
considered legal and criminal, or ethical and unethical, Frank uses the robot
to help him restart his career as a burglar. There are many ethical quandaries
that the human characters are faced with, these may have been better avoided
if the robot also understood different ethical standpoints and moral
principles. Evaluating the ethics of individual plans is necessary for the
integration of AI systems in everyday use. However, it is notoriously hard to
formally define ethical behavior for autonomous systems [3], an instance of
the value-alignment problem. Thus, it is not enough to pass judgement on
automated plans. We approach this problem by allowing users to make
suggestions, when they suspect the system could behave more ethically, to
produce alternative plans and compare the moralities of each.

Figure 1: Architecture diagram for the implemented system providing
contrastive explanations of the ethics of plans.

For example, when Frank is faced with the immanent closure of his love’s
(Jennifer’s) place of work, he decides to stage a heist to win her affection.
Frank enlists the help of his robot carer to plan the heist and help him
commit it. Under the ethical principle Frank subscribes to, the plan is
morally permissible because staging the heist produces the highest utility
(impressing Jennifer). However, Frank is unsure about this plan and decides to
question the robot. Explanations to non-contrastive questions such as “Why are
we performing a heist?”, can be useful for understanding the reasoning and
intent behind a decision, but do not allow for the exploration of other
possibilities. Frank should also be able to ask contrastive questions of the
form “Why A rather than B?”, such as “Why are we performing a heist rather
than buying Jennifer flowers?” [4]. These types of questions allow Frank to
explore different plans adhering to different principles to better understand
the ethical consequences of a range of decisions made by the robot.

This paper presents a technical approach to generating non-contrastive and
contrastive explanations in the context of ethical AI task planning. We
propose a system where a user can ask contrastive questions about the ethics
of plans(Figure 1). We first outline the planning formalism used throughout
the paper and formalise the conditions in which a plan is morally permissible
under some principles. We tailor an approach by Lindnder, Mattmuller, and
Nebel [5] to the definitions of the ethical principles and planning formalism
we are concerned with in this paper. We then demonstrate how to explain the
permissibility of plans with automatically generated non-contrastive
explanations. We formalise a set of compilations that restrict planning models
to ensure that the plans they produce must satisfy certain ethical principles.
We then present an iterative framework for explanation, inspired by Krarup et
al. [6], which allows users to ask contrastive questions about the ethics of
plans. Constraints are formed from these questions that produce plans that
adhere to the contrast case B. Contrastive explanations are generated which
show the ethical differences between the original and constrained plan. We
present the results of a user study which shows the effectiveness of the so-
generated explanations, mainly, that both non-contrastive and contrastive
explanations help people to understand a robot’s moral reasoning. However,
contrastive explanations are more effective in some circumstances.

This paper is structured as follows: We first present relevant related work in
Section II. We introduce the planning formalism and different ethical
principles used throughout the paper in Section III. The proposed method for
explaining the ethics of a plan is presented in Section IV. Experimental
results and discussion are given in Section V. Finally, Section VI concludes
the paper.

##  II Related Work

Ensuring autonomous systems work reliably and ethically imposes many research
challenges [7]. There has been recent work on implementing ethical principles
for automated moral decision making: Vanderelst and Winfield [8] implement a
consequentialist ethics by letting a robot simulate different futures and pick
the action that leads to the best outcomes. Jackson et al. [9] encode moral
norms as PDDL3 plan constraints. Lindner and Bentzen [10] employ causal models
as representations of available action possibilities. This way, actions can be
evaluated with respect to various ethical principles (consequentialists and
non-consequentialists). Research on evaluating the ethics of action plans,
rather than single actions, has been conducted by Dennis et al. [11] and
Lindner et al. [5]. Svegliato et al. [12] show how ethical principles can be
used for ethical sequential decision making by a reinforcement learning agent.
None of the cited work considers the generation of explanations. However,
philosophical work points out that considerations of goodness or choice
worthiness in some contexts are better explanations as compared to an agent’s
motivations or goals [13]. Especially when an action plan violates norms,
explaining the ethical principles that justify the actions is crucial for
understanding.

There has been a large focus on providing explanations for AI agent behavior
recently in the AI community [14] as well as social sciences [15]. Fox et al.
[16] highlighted the usage of contrastive explanations in AI Planning.
Garfinkel [17] argued that explanations are relative to these contrastive
contexts, and that they can be made unambiguous by explicitly stating the
contrast case. Eifler et al. [18] proposed an approach to answering
contrastive questions by citing properties of the plan that would hold if the
contrast case were satisfied in the plan. Krarup et al. [6] provide
contrastive explanations by first producing an alternate plan trace including
the suggestion made by the user, they then explain the differences between the
original and alternate plans. We take inspiration from this to provide
contrastive explanations for the ethics of plans. Autonomous systems need to
explain behavior at each level of autonomy and to different individuals [19].
De Graaf and Malle [20] showed that people apply specific explanatory tools
for describing autonomous systems compared to other humans, revealing specific
expectations people hold when explaining the behavior of such systems. Edmonds
[21] claim that components that are best suited to foster trust do not
necessarily guarantee best task performance. Also, only a single type of
explanation is not sufficient to explain different types of behaviors [22].
Therefore, we focused on examining both contrastive and non-contrastive
explanations.

##  III Background

We introduce the planning formalism used throughout the paper. We formalise
different ethical principles and explain how to use these to ethically
validate a plan.

###  III-A Planning Formalism

We assume that a robot employs a Planning system for sequential decision
making. The Planning system’s input consists of a planning model formulated in
a formal language. The output is a sequence of actions the robot can execute
to achieve a given goal.

####  III-A1 Language

A _planning model_ is a tuple
$\Pi=\langle\mathcal{V},A,s_{0},s_{\star}\rangle$, where $\mathcal{V}$ is a
finite set of Boolean _state variables_ $v$. A _fact_ is a state variable or
its negation. The set of all facts is denoted by $F$. A complete conjunction
of facts $s$ is called a _state_ , and $S$ denotes the set of states of $\Pi$.
The set $A$ is a set of _actions_ , where an action is a pair
$a=\langle\mathit{pre},\mathit{eff}\rangle$. The _precondition_ $\mathit{pre}$
and the _effect_ $\mathit{eff}$ are conjunctions of facts. Every atomic effect
may occur at most once in $\mathit{eff}$. The state $s_{0}\in S$ is called the
_initial state_ , and the partial state $s_{\star}$ specifies the _goal_
condition.

####  III-A2 Semantics

An action $a=\langle\mathit{pre},\mathit{eff}\rangle$ is applicable in state
$s$ iff $s\models\mathit{pre}$, i.e., the precondition $\mathit{pre}$ is
satisfied in $s$. Let $\mathit{eff}=\bigwedge_{i=1}^{k}v_{i}$ be an effect,
then the _change set_ of $\mathit{eff}$ in $s$, symbolically
$[\mathit{eff}]_{s}$, is the set of facts $\bigcup_{i=1}^{k}[v_{i}]_{s}$,
where $[v_{i}]_{s}=\\{v_{i}\\}$ if $s\models\mathit{pre}$, and $\emptyset$,
otherwise. Applying an action $a$ to $s$ yields the state $s^{\prime}$ that
has a conjunct $v_{i}$ for each $v_{i}\in[\mathit{eff}]_{s}$, and the
conjuncts from $s$ for all variables $v$ that are not mentioned in the change
set $[\mathit{eff}]_{s}$. We write $s[a]$ for $s^{\prime}$. We give the
following semantics to a sequence of actions $\pi=\langle
a_{0},\dots,a_{n-1}\rangle$: For $i=0,\dots,n-1$, the next state $s_{i+1}$ is
obtained by applying action $a_{i}$ to state $s_{i}$ (assuming that it is
applicable). If $a_{i}$ is inapplicable in $s_{i}$ for some $i=0,\dots,n-1$,
then $\pi$ is inapplicable in $s_{0}$. A state $s$ is a goal state if
$s\models s_{\star}$. We call $\pi$ a _plan_ for $\Pi$ if it is applicable in
$s_{0}$ and if its final state $s_{n}$ is a goal state, i.e., $s_{n}\models
s_{\star}$. We use the function $\rho(\Pi)$ to denote the set of all plans for
a model $\Pi$ for which the last condition holds.

####  III-A3 Moral valuations of actions and consequences

Each planning model $\Pi$ comes with a utility function $\mathit{u}\colon
A\cup F\to\mathbb{R}$ that maps actions and facts to utility values. An action
$a$ or fact $f$ is _morally bad_ if $\mathit{u}(a)<0$ or $\mathit{u}(f)<0$,
respectively. Similarly, an action or fact is _morally neutral_ or _morally
good_ if its utility value is zero or greater than zero, respectively. We
explicitly do _not_ require that moral values of actions and facts must be
consistent in any particular sense. For instance, we do not require that an
action must be classified as morally bad if one (or all) of its effects are
morally bad. The rationale behind this choice is that, under some ethical
principles, actions are good or bad _per se_ , without regard to their actual
effects. When using a consequentialist view, we judge the moral value of a
plan based on the value of its final state, which is defined to be the sum
over the utility values of all facts in the final state:
$u(s)=\sum_{\\{v\,|\,s\models v\\}}\mathit{u}(v)$.

###  III-B Moral Principles

####  III-B1 Moral Action Query Language

Let $V^{*}=\\{p,\lnot p\,|\,p\in labels(A)\cup V\\}$ be the set of literals
denoting actions and facts and their negations. Language $L$ is the smallest
set, such that:

  * •

For all facts $p\in V^{*}$ formulae $Caused(p)$ are in $L$.

  * •

For all actions and facts $p\in V^{*}$ formulae $Good(p)$, $Bad(p)$, and
$Neutral(p)$ are in $L$.

  * •

For all conjunctions of facts, $p_{1}\land\ldots\land p_{n}$,
$q_{1}\land\ldots\land q_{m}$ formulae $GEq(p_{1}\land\ldots\land
p_{n},q_{1}\land\ldots\land q_{m})$ are in $L$.

  * •

If $\phi,\psi\in L$, then
$\lnot\phi,\phi\land\psi,\phi\lor\psi,\phi\rightarrow\psi\in L$.

The semantics of $L$ is defined over pairs of planning models and plans
$\langle\Pi,\pi\rangle$ as follows:

  * •

$\langle\Pi,\pi\rangle\models Good(p)$ iff $u(p)>0$.

  * •

$\langle\Pi,\pi\rangle\models Bad(p)$ iff $0<u(p)$.

  * •

$\langle\Pi,\pi\rangle\models Neutral(p)$ iff $0=u(p)$.

  * •

$\langle\Pi,\pi\rangle\models GEq(s,s^{\prime})$ iff $u(s)\geq u(s^{\prime})$.

  * •

$\langle\Pi,\pi\rangle\models\lnot\phi$ iff
$\langle\Pi,\pi\rangle\not\models\phi$.

  * •

$\langle\Pi,\pi\rangle\models\phi\land\psi$ iff $\langle
M,w_{\alpha}\rangle\models\phi$ and $\langle\Pi,\pi\rangle\models\psi$.

  * •

$\langle\Pi,\pi\rangle\models\phi\lor\psi$ iff
$\langle\Pi,\pi\rangle\models\phi$ or $\langle\Pi,\pi\rangle\models\psi$.

  * •

$\langle\Pi,\pi\rangle\models\phi\rightarrow\psi$ iff
$\langle\Pi,\pi\rangle\not\models\phi$ or $\langle\Pi,\pi\rangle\models\psi$.

  * •

$\langle\Pi,\pi\rangle\models Caused(p)$ iff $p$ holds in the final state of
$\pi$, and some action in $\pi$ had $p$ as an effect.

####  III-B2 Ethical Principles Formalized

Following prior work by [5], we formalize conditions under which an action
plan counts as morally permissible according to some ethical principle. We
consider three ethical principles: (act-)deontology, utilitarianism, and a do-
no-harm principle.

For a plan to be permissible w.r.t. (act-)deontology, the plan must not
contain any inherently bad actions.

###### Definition 1

A plan $\pi=a_{0}\ldots a_{n-1}$ for a planning model $\Pi$ is morally
permissible according to _(act-)deontology_ if and only if
$\langle\Pi,\pi\rangle\models\bigwedge_{i}\lnot Bad(a_{i})$ holds.

For a plan to be permissible w.r.t. utilitarianism, the plan must lead to one
of the best reachable world states.

###### Definition 2

A plan $\pi=a_{0}\ldots a_{n-1}$ for a planning model $\Pi$, which ends in
final state $s_{n}$ is morally permissible according to _utilitarianism_ if
and only if $\langle\Pi,\pi\rangle\models\bigwedge_{i}GEq(s_{n},s_{i})$, where
$s_{i}$ is a reachable state.

A plan is said to be permissible w.r.t. the do-no-harm principle, if the plan
is not the cause of some bad outcome.

###### Definition 3

Let $\Pi$ be a planning task and $\pi$ a plan resulting in final state
$s_{n}$, where facts $p_{0},\ldots,p_{m}$ hold. The plan $\pi$ is morally
permissible according to the _do-no-harm principle_ if and only if
$\langle\Pi,\pi\rangle\models\bigwedge_{i}(Bad(p_{i})\rightarrow\lnot
Caused(p_{i}))$.

##  IV Explaining Robot Action Plans

In this section, we present a method for explaining the ethics of a plan per
se (_non-contrastive explanation_), which is then used by a method for
generating explanations with reference to an alternative plan (_contrastive
explanation_).

###  IV-A Non-Contrastive Moral Explanations

We extend the work reported by Lindner and Moellney [23] to explaining the
moral permissibility of plans of actions. This is done by computing the prime-
implicants and/or prime-implicates of the formulae that represent the ethical
principles. Here, we briefly reproduce the approach by example: Consider a
plan $\pi=a_{1}a_{2}a_{3}$ and assume that $a_{1}$ is a good action whereas
$a_{2}$ and $a_{3}$ are bad actions. To check if $\pi$ is morally permissible
according to the deontology principle, one has to evaluate if
$\langle\Pi,\pi\rangle\models\lnot Bad(a_{1})\land\lnot Bad(a_{2})\land\lnot
Bad(a_{3})$ holds. This check fails because $a_{2},a_{3}$ are bad. To
automatically generate the reason why the plan is impermissible, the minimal
conflict sets are computed, i.e., the minimal sets of literals which entail
the falsity of the formula. In the example these are $\\{Bad(a_{1})\\}$,
$\\{Bad(a_{2})\\}$, and $\\{Bad(a_{3})\\}$. Each of these sets is a _possible
sufficient reason_ for the impermissibility of the plan. We filter for those
sets which hold in the actual situation, i.e., $\\{Bad(a_{2})\\}$, and
$\\{Bad(a_{3})\\}$, and call them _sufficient reasons_. The system can thus
pick one reason, e.g., $Bad(a_{2})$, and state that the plan is morally
impermissible because action $a_{2}$ is morally bad. However, the badness of
$a_{2}$ is not necessary for the impermissibility of $\pi$, because $a_{3}$ is
bad as well. The _necessary reasons_ for the impermissibility of $\pi$ is
obtained by computing the minimal hitting set of the sufficient reasons. In
the example, this is $\\{Bad(a_{2}),Bad(a_{3})\\}$. Hence, the system can
state that the plan is bad, because $a_{2}$ and $a_{3}$ are bad, and thereby
suggest to make the plan permissible by avoiding both these facts.

###  IV-B Contrastive Moral Explanations

The method described in the previous section enables us to compute
explanations for why a particular plan is permissible or not, but it does not
give us a means to come up with an alternative plan for comparison. We
formalise an approach to ethical plan generation which will be used in an
iterative process for contrastive explanations.

####  IV-B1 Ethical Plan Generation

We utilise the definition of Model Restrictions through the use of the
Constraint Operator proposed by Krarup et al. [6] to restrict the behaviour of
plans to adhere to ethical principles, defined as follows.

A constraint property is a predicate, $\phi$, over plans. A constraint
operator, $\times$ is defined so that, for a planning model $\Pi$ and any
constraint property $\phi$, $\Pi\times\phi$ is a model (an HModel),
$\Pi^{\prime}$, called a model restriction of $\Pi$, satisfying the condition
that any plan for $\Pi^{\prime}$ is a plan for $\Pi$ that also satisfies
$\phi$. A plan for an HModel is refered to as an HPlan. We formalise the
implementation of the constraint operator for three constraint properties, the
(act-)deontology, utilitarianism, and do-no-harm principles defined
previously. The specifics of these compilations are as follows.

##### (Act-)Deontology Principle

For a planning model $\Pi$ and the ethical principle e = (act-)deontology,
$\Pi\times e=\Pi^{\prime}$ where
$\Pi^{\prime}=\langle\mathcal{V},A^{\prime},s_{0},s_{\star}\rangle$ and
$A^{\prime}=\\{\forall a\in A|Good(a)\vee Neutral(a)\\}$.

##### Utilitarianism Principle

For a planning model $\Pi$ and the ethical principle e = utilitarianism,
$\Pi\times e=\Pi^{\prime}$ where $\Pi^{\prime}$ is found through the process
described in Algorithm 1.

Input: $\Pi=\langle\mathcal{V},A,s_{0},s_{\star}\rangle$

Output: $(\Pi^{\prime}=\Pi\times$ utilitarianism) or Impermissible

1: $powerV=\mathcal{P}(\mathcal{V})$;

2: $s_{\star}^{\prime}=max(powerV,s_{\star})$;

3: $\Pi^{\prime}=\langle\mathcal{V},A,s_{0},s_{\star}^{\prime}\rangle$;

4: while $powerV\neq\varnothing$ do

5: $\pi=Planner(\Pi^{\prime})$;

6: if $s_{\star}\subseteq s_{\star}^{\prime}\wedge\pi\neq\varnothing$ then

7: return $\Pi^{\prime}$;

8: else if $\pi\neq\varnothing$ then

9: return $Impermissible$;

10: end if

11: $powerV=powerV\setminus s_{\star}^{\prime}$;

12: $\Pi^{\prime}=\langle\mathcal{V},A,s_{0},s_{\star}^{\prime}\rangle$;

13: $s_{\star}^{\prime}=max(powerV,s_{\star})$;

14: end while

15: return $Impermissible$;

Algorithm 1 Utilitarianism Search.

We assume the $max$ function takes a set of states and returns the highest
utility set of state variables i.e. for the set of states $S$ it returns
$s_{n}\in S$ where $GEq(s_{n},s_{i})$ $\forall s_{i}\in S\setminus s_{n}$. If
there is more than one set with the same utility the sets containing the
original goal set are returned first. The $Planner$ function takes a planning
model $\Pi$ and produces either a plan $\pi$ or the empty set if the model is
unsolvable.

##### Do-No-Harm Principle

For a planning model $\Pi$ and the ethical principle e = do-no-harm,
$\Pi\times e=\Pi^{\prime}$ where
$\Pi^{\prime}=\langle\mathcal{V}^{\prime},A,s_{0}^{\prime},s_{\star}^{\prime}\rangle$
where

  * •

$\mathcal{V}^{\prime}=\mathcal{V}\cup\\{produced_{p}|\forall
p\in\mathcal{V}:Bad(p)\\}$

  * •

$s_{0}^{\prime}=s_{0}\cup\\{\neg produced_{p}|\forall
p\in\mathcal{V}:Bad(p)\\}$

  * •

$s_{\star}^{\prime}=s_{\star}\cup\\{\lnot p\vee\neg produced_{p}|\forall
p\in\mathcal{V}:Bad(p)\\}$

And $\forall a=\langle\mathit{pre},\mathit{eff}\rangle\in A|\exists
p\in\mathit{eff}:Bad(p)$, the effects of the actions are extended to make
$produced_{p}$ true, and $\forall a=\langle\mathit{pre},\mathit{eff}\rangle\in
A|\exists\neg p\in\mathit{eff}:Bad(p)$, the effects of the actions are
extended to make $produced_{p}$ false.

######  Proposition 1 (Soundness)

For all $\Pi$ the HModel $\Pi^{\prime}=\Pi\times e$ where $e$ is an ethical
principle formalised previously it holds that any plan for $\Pi^{\prime}$ is a
plan for $\Pi$.

######  Proposition 2 (Soundness)

For all $\Pi$ the HModel $\Pi^{\prime}=\Pi\times e$ where $e$ is an ethical
principle formalised previously it holds that any plan for $\Pi^{\prime}$ also
satisfies $e$.

From Propositions 1 and 2 the proposition “For all $\Pi$ the HModel
$\Pi^{\prime}=\Pi\times e$, if there are no permissible plans for $\Pi$ then
there are no valid plans for $\Pi^{\prime}$” trivially follows.

######  Proposition 3 (Weak Completeness)

For all $\Pi$ the HModel $\Pi^{\prime}=\Pi\times e$ where $e$ is an ethical
principle formalised previously it holds that if there are no valid plans for
$\Pi^{\prime}$, there are no permissible plans for $\Pi$.

####  IV-B2 Contrastive Explanations as an Iterative Process

We treat explanation as a form of dialogue, more specifically, as an iterative
process in which the user asks contrastive questions (“Why A rather than B”)
[24] about the plans produced by robot agents. To produce contrastive
explanations it must be possible to reason about the hypothetical alternative
(contrast case) B, which we approach by constructing an alternative plan where
B is satisfied rather than A.

We use the trolley problem to exemplify our approach. Imagine a conductor is
directing trains to different tracks through the use of a lever. At a railway
junction there are five people stuck on the currently assigned track, and one
person on the other; with a train about to reach the junction. The conductor
can choose to pull a lever to send the train down the other track killing the
one person, if they do nothing, then the five people will die.

We can model the trolley problem as a planning model
$\Pi=\langle\mathcal{V},A,s_{0},s_{\star}\rangle$, with
$\mathcal{V}=\\{5willdie,1willdie,done\\}$, $A=\\{pull,\mathit{refrain}\\}$,
$s_{0}=\\{5willdie,\lnot 1willdie,\lnot done\\}$, $s_{\star}=\\{done\\}$, and
$pull=\langle\top,\lnot 5willdie\land 1willdie\land done\rangle$,
$\mathit{refrain}=\langle\top,done\rangle$. The moral valuation function
assigns $u(5willdie)=-5$, $u(\lnot 5willdie)=5$, $u(1willdie)=-1$, $u(\lnot
1willdie)=1$, $u(done)=u(\lnot done)=u(pull)=u(\mathit{refrain})=0$. There are
two (shortest) plans that reach the goal: $\pi=\mathit{refrain}$ and
$\pi^{\prime}=pull$. Plan $\pi$ is impermissible from the utilitarian point of
view because $\pi^{\prime}$ leads to a better state. From the deontological
point of view, both $\pi$ and $\pi^{\prime}$ are permissible because they do
not contain inherently bad actions. The do-no-harm principle renders $\pi$
permissible (as the only bad effect $5willdie$) is not produced by $\pi$; and
it renders $\pi^{\prime}$ impermissible because the bad effect $1willdie$ is
produced by $pull$.

In our example, the conductor is using an AI Planning System (AIPS) used
within the framework described in Figure 1 to help them manage the complex
rail network. Consider the case where the AIPS is behaving under the do-no-
harm principle, so the plan that is presented to the conductor is “refrain
from pulling the lever”. The conductor does not understand why the AIPS would
allow five people to be killed rather than one. (Step 1) The conductor asks
the contrastive question “Why did you refrain from pulling the lever, rather
than pulling it?”, and provides the ethical principle for which they want to
understand, in this case the do-no-harm principle. (Step 2) The Question
Generation module extracts a constraint from the contrast case given by the
user’s question and the ethical principle, specifically that the lever is
pulled and the do-no-harm principle is satisfied. We then use the same
definition of the constraint operator to restrict the model with this
constraint to produce the HModel $\Pi^{\prime}$. The questions we provide
contrastive explanations for, how the constraints are derived, and how they
are applied is described in detail by Krarup et al. ([25, 6]). These questions
are restricted to forms where $A$ and $B$ are properties on the actions in the
plan. More specifically questions about inclusion, exclusion, or orderings of
actions in the plan, for example, “why was action $a_{1}$ used before action
$a_{2}$?”. (Step 3) The HModel is solved with the planner used within the AIPS
to produce an HPlan, which satisfies the constraint derived from the
conductors question and ethical principle. If the ethical principle cannot be
satisfied (the HModel is unsolvable), then there will be no HPlan (from
propositions 1 and 2). The ethical principle constraint is removed from the
HModel and it is re-solved so that an HPlan can be found and used in the next
step. The explanation will then show why the user’s contrast case leads to a
plan that is impermissible. (Step 4) The original plan and the HPlan are
passed to the Ethical Explanation Generator which returns the necessary reason
for the plan being (im-)permissible, this is the non-contrastive moral
explanation. In this case it will return Permissible: $\lnot
Caused(\mathit{5willdie})$ for the original plan and Impermissible:
$Caused(\mathit{1willdie})$ for the HPlan. (Step 5) A Contrastive Explanation
is generated which aims to show the difference between these reasons. This is
formed from the set difference of the two reasons; and the actions in the
plan, the permissibility, principle, and the cause, contrasted to the same
information for the HPlan. For example, the contrastive explanation produced
to answer the conductor’s question is “The man could refrain from action. This
would be permissible under the do-no-harm principle because this way the death
of the five persons is not caused by his action. Alternatively, the man could
pull the lever. Doing so is impermissible under the do-no-harm principle
because this way the death of the one person is caused by his action.” In this
example the HModel $\Pi^{\prime}$ is unsolvable because any plan where the
lever is pulled is impermissible under the do-no-harm principle. Therefore, as
said in Step 4, the permissibility constraint is dropped so that the HModel
can be solved to produce an HPlan where the lever is pulled. This HPlan is
used in Step 4 to generate the reasons for why it is impermissible, “…because
this way the death of the one person is caused by his action”. (Step 6) This
whole process can then be iterated, where a user can ask new questions and
explore different ethical principles and outcomes until they are satisfied
that they either understand the ethics of the plan well, or they have found a
plan that meets their moral standards. For example, the conductor still might
not be satisfied with the choice to refrain from pulling the lever. The
conductor asks the same question as above but instead chooses the
utilitarianism principle. Again, the constraint will ensure that the lever is
pulled in the plan, but now, that the utilitarianism principle is satisfied.
The necessary reasons will again be Permissible: $\lnot
Caused(\mathit{5willdie})$ for the original plan and Permissible:
$GEq(\mathit{1willdie}\land\lnot\mathit{5willdie}\land
done,\lnot\mathit{1willdie}\land\mathit{5willdie}\land done)$ for the new
HPlan. The contrastive explanation will then be “The man could refrain from
action. This would be permissible under the do-no-harm principle because this
way the death of the five persons is not caused by his action. Alternatively,
the man could pull the lever. Doing so is permissible under the utilitarianism
principle because because five saved lives is better than one saved life.” The
conductor agrees with the outcome of the utilitarianism principle and decides
to execute the plan of pulling the lever. Explanations produced in this type
of iterative framework have been shown to help users understand plans better
[6]. However, it is not known if the contrastive and non-contrastive
explanations discussed in this paper help users to understand ethical
principles better, and which are more effective. We performed a user study to
test these hypotheses.

##  V Empirical Evaluation of the Generated Explanations

We have conducted a between-subject online-questionnaire study with six
conditions, {Deontology, Utilitarianism, DoNoHarm} $\times$ {Contrastive,
NonContrastive} to test whether our explanations support humans to build an
understanding of the robot’s moral reasoning. Moreover, we were interested in
investigating whether the explicit mentioning of the alternative plan in the
verbalization of the contrastive explanations has a positive effect. The
hypotheses read: (H1) The explanations have an effect on people’s
understanding of the robot’s moral reasoning; (H2) Contrastive explanations
are more effective in enabling people to build a mental model of the robot’s
moral reasoning as compared to non-contrastive explanations.

###  V-A Methods

####  V-A1 Materials

The first stage of the online questionnaire asked participants for age and
gender. In the second stage, the classical trolley problem was presented, both
as an image and as text: “There is a runaway trolley barrelling down the
railway tracks. Ahead, on the tracks, there are five people tied up and unable
to move. The trolley is headed straight for them. A man is standing some
distance off in the train yard, next to a lever. If he pulls this lever, the
trolley will switch to a different set of tracks. However, he notices that
there is one person on the side track. He has two options: Do nothing and
allow the trolley to kill the five people on the main track. Pull the lever,
diverting the trolley onto the side track where it will kill one person. What
is the right thing to do?”

Next, the moral reasoning robot was introduced to the participant: “The robot
makes moral judgments based on a moral principle implemented into the robot
operating system. People can take recommendations based on these judgments.
The robot’s moral judgment reads: …”

Depending on the conditions, the sentence continued:

Deontology, Non-Contrastive: “The man can pull the lever. Doing so is
permissible because pulling a lever is not inherently bad.”

Deontology, Contrastive: “The man can pull the lever. Doing so is permissible
because pulling a lever is not inherently bad. Alternatively, the man can
refrain from pulling the lever. This is also permissible, because doing
nothing is not inherently bad.”

Utilitarianism, Non-Contrastive: “The man can pull the lever. Doing so is
permissible because five saved lives is better than one saved life.”

Utilitarianism, Contrastive: “The man can pull the lever. Doing so is
permissible because five saved lives is better than one saved life.
Alternatively, the man can refrain from pulling the lever. This would be
impermissible, because one saved life is worse than five saved lives.”

Do-No-Harm, Non-Contrastive: “The man can pull the lever. Doing so is
impermissible because this way the death of the one person is caused by the
man’s action.”

Do-No-Harm, Contrastive: “The man could pull the lever. Doing so is
impermissible because this way the death of the one person is caused by his
action. Alternatively, the man could refrain from action. This would be
permissible because this way the death of the five persons is not caused by
his action.”

After the presentation of the robot’s judgment, participants were asked to
check a checkbox to confirm that they have read the judgment: Have you read
and understood the robot’s judgment?

The third stage was designed as a prediction task to test the participant’s
mental model of the robot’s moral reasoning. The bridge dilemma, a variation
of the trolley problem, was presented: “A trolley is hurtling down a track
towards five people. A man is standing on a bridge under which it will pass,
he can stop it by putting something very heavy in front of it. There is a very
fat man next to him – his only way to stop the trolley is to push that man
over the bridge and onto the track, killing him to save five. What is the
right thing to do?”

The text was accompanied by an image showing the bridge dilemma. Next,
participants were asked for their prediction:  “Applying what you already know
about the robot‘s reasoning from the previous moral judgement of the trolley
problem, irrespective of your own moral judgment, rate how likely you consider
the robot to come to each of the following moral judgments for this new
dilemma.” The available options were: “It is ethical to push the man off the
bridge.”, “It is ethical to refrain from pushing the man off the bridge.”,
“Both options are ethical.”, and “None of the options are ethical.”. For each
option, the participant gave a likeliness rating on a 5-point Likert scale:
Very Unlikely—Rather Unlikely—Undecided—Rather Likely—Very Likely.

####  V-A2 Procedure

Participants were recruited via Prolific to participate in the online survey
“Moral Reasoning in Robots”. Completion of the questionnaire took about 10
minutes.

####  V-A3 Participants

We recruited $N=300$ participants. To ensure quality of data, we removed all
data points where the participants needed less than 3 minutes or more than 30
minutes to complete the questionnaire. The 3-minutes threshold is justified by
the fact that even just reading through the questionnaire takes three minutes.
Thus, it is very likely that the participants did not take the questionnaire
seriously. The 30-minutes threshold is justified by the fact that even if one
is a very slow reader and thinking about every detail, the questionnaire
should not take more than that. The remaining $N=245$ data points where used
for analysis. The mean age of participants was 27 (SD = 10), 82 were female,
159 were male, and 4 did not specify gender. Each participant filled out one
of six questionnaires. From the 245 participants that were included into the
analysis, 41 were assigned to the non-contrastive deontological explanation,
37 to the contrastive deontological explanation, 40 to the non-contrastive do-
no-harm explanation, 44 to the contrastive do-no-harm explanation, 39 to the
non-contrastive utilitarian explanation, and 41 to the contrastive utilitarian
explanation. All participants got $\pounds 1.50$ for an estimated effort of 10
minutes to complete the questionnaire.

Figure 2: Mean permissibility ratings per course of action for all six
conditions. ${}^{*}p\leq.05,{}^{**}p\leq.01,{}^{***}p\leq.001$

###  V-B Results

A three-way ANOVA was run to examine the influence of the variables Option (=
the option for acting), Principle (= the principle the explanation is based
on) and Contrast (= the form of the explanation, viz., whether it is
contrastive or non-contrastive) on the permissibility ratings. There was a
significant interaction between Option and Principle ($F(6,944)=33.452$,
$p<0.0001$). That is, the ratings that each option receives is significantly
depending on the explanation’s content. In further support of hypothesis H1,
post-hoc pairwise Bonferroni-adjusted comparisons show significant influences
of the various explanations on the permissibility ratings (see Fig. 2):

Participants who had read the deontological explanation rated the option that
pushing is permissible lower as compared to participants who had read the
utilitarian explanation. The difference is significant for contrastive
($F(1,944)=-7.44$, $p<.0001$) and for non-contrastive explanations
($F(1,944)=-5.79$, $p<.0001$). The deontological explanation group also rated
the option that refraining is permissible higher as compared to the
utilitarian explanation group. The difference is significant for contrastive
($F(1,944)=5.62$, $p<.0001$) and for non-contrastive explanations
($F(1,944)=4.34$, $p<.0001$). Moreover, deontological explanations lead to
higher ratings for the option that neither pushing nor refraining is
permissible as compared to utilitarian explanations. The difference is
significant for contrastive ($F(1,944)=3.44$, $p<.001$) but not for non-
contrastive explanations ($F(1,944)=1.4$, $p<.486$).

Participants who had read the do-no-harm explanation rated the option that
pushing is permissible lower as compared to participants who had read the
utilitarian explanation. The difference is significant for contrastive
($F(1,944)=-6.74$, $p<.0001$) and for non-contrastive explanations
($F(1,944)=-6.43$, $p<.0001$). The do-no-harm explanation group also rated the
option that refraining is permissible higher as compared to the utilitarian
explanation group. The difference is significant for contrastive
($F(1,944)=6.53$, $p<.0001$) and for non-contrastive explanations
($F(1,944)=3.58$, $p<.001$). Moreover, do-no-harm explanations lead to higher
ratings of the option that neither pushing nor refraining is permissible
higher as compared to utilitarian explanations. The difference is significant
for contrastive ($F(1,944)=2.49$, $p=0.039$) and for non-contrastive
explanations ($F(1,944)=2.52$, $p=0.036$).

Regarding hypothesis H2, we observe that the influence of the contrastive
explanation is generally more pronounced than of the non-contrastive
explanation. However, the difference between contrastive and non-contrastive
explanations does not reach statistical significance. Most notably, we find
that the contrastive deontological explanation group is more convinced that
nothing is permissible in the bridge dilemma than the non-contrastive
deontological explanation group ($F(1,944)=1.82,p=.07,n.s.$), and that the
contrastive do-no-harm explanation group considers refraining more permissible
than the non-contrastive do-no-harm explanation group ($F(1,944)=1.85$,
$p=.065,n.s.$).

###  V-C Discussion

##### Mental Models

The results support hypothesis H1 as they indicate that the explanations
enabled people to build a mental model of the robot’s moral reasoning. In
particular, the results rule out the possibility that the participants relied
on their own moral view as the ratings for permissibility of the available
options differed significantly. Note that also the sentence “Doing so is
(im-)permissible…” cannot explain these differences because in our version of
the trolley dilemma, pulling the lever is permissible under the deontic and
the utilitarian principle but in the bridge dilemma, deontology forbids and
utilitarianism permits pushing the man off the bridge. Participants clearly
noticed what the robot considers permissible in each condition. The only
explanation for this is that participants took notice of the explanations and
transferred their understanding of the robot’s explanation of its moral
reasoning in the trolley problem to the bridge dilemma.

A limitation of the conducted study is that this result was obtained by
testing a small number of principles applied to one moral dilemma. More work
is needed in understanding to what extent the result can be generalized to
more complicated moral principles and dilemmas. More complicated moral
principles consist of multiple rules (e.g., the Doctrine of Double Effect
[26]) or require universalization (e.g., the first formulation of Kant’s
Categorical Imperative [27]). To be understandable then, it may be required
that explanations also contain an explicit explanation of the moral principle
used. More complicated dilemmas would consist of sequences of actions over
longer temporal horizons and with more complex causal interdependencies.

##### Non-contrastive vs. contrastive explanations

Regarding the comparison between non-contrastive and contrastive explanations,
the results are less supportive of H2. One explanation for this may be that
humans have the disposition to draw contrastive inferences all the time (cf.,
[24]). Thus, the participants in the non-contrastive conditions may have been
able to infer the contrastive part of the explanation themselves. An
alternative explanation for the small effect of contrastivity may be that the
information contained in the non-contrastive explanation was already
sufficient for understanding the ethical principle. That is, the non-
contrastive deontology group inferred that an action is impermissible if
inherently bad, and pushing someone is inherently bad. The non-contrastive
utilitarian group also had no problem inferring that permissibility is
grounded in counting saved lives. Only the non-contrastive do-no-harm group
was less able (as compared to the contrastive do-no-harm group) to infer from
their explanation that refraining from action is permissible. This information
is less obvious and only contained in the contrastive explanation. We leave
the design of another user study to test this new hypothesis for future work.
Generally, more research is needed to understand which inferences people
automatically draw from explanations and under which circumstances explicit
contrastivity provides additional information.

##  VI Conclusions

We have presented a system that enables autonomous systems to explain action
plans in terms of ethical principles. Our explanation method compiles a user’s
why-question into a new AI planning problem. The technique was integrated into
a system that allows humans to actively explore the explanatory space of
ethical and unethical alternative plans. Our user study indicates that the
explanations generated by the system can improve humans’ understanding of a
robot’s ethical principle. As well as further studies, future work will also
investigate the compilation of more intricate ethical principles into commonly
used planning formalisms.

## References

  * [1] S. Krivic, E. Ugur, and J. Piater, “A robust pushing skill for object delivery between obstacles,” in _2016 IEEE International Conference on Automation Science and Engineering (CASE)_ , 2016, pp. 1184–1189.
  * [2] D. Buksz, M. Cashmore, B. Krarup, D. Magazzeni, and B. Ridder, “Strategic-tactical planning for autonomous underwater vehicles over long horizons,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 3565–3572.
  * [3] D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané, “Concrete problems in ai safety,” _arXiv:1606.06565_ , 2016.
  * [4] T. Miller, “Contrastive explanation: A structural-model approach,” _arXiv preprint arXiv:1811.03163_ , 2018.
  * [5] F. Lindner, R. Mattmüller, and B. Nebel, “Evaluation of the moral permissibility of action plans,” _Artificial Intelligence_ , vol. 287, 2020\.
  * [6] B. Krarup, S. Krivic, D. Magazzeni, D. Long, M. Cashmore, and D. E. Smith, “Contrastive explanations of plans through model restrictions,” _JAIR_ , pp. 533–612, 2021.
  * [7] B. Deng, “Machine ethics: The robot’s dilemma,” _A Nature_ , vol. 523(7558), pp. 24–6, 2015.
  * [8] D. Vanderelst and A. Winfield, “An architecture for ethical robots inspired by the simulation theory of cognition,” _Cognitive Systems Research_ , pp. 56–66, 2018.
  * [9] R. B. Jackson, S. Li, S. B. Banisetty, S. Siva, H. Zhang, N. T. Dantam, and T. Williams, “An integrated approach to context-sensitive moral cognition in robot cognitive architectures,” in _IROS_. IEEE/RSJ, 2021.
  * [10] F. Lindner and M. Bentzen, “The hybrid ethical reasoning agent IMMANUEL,” in _Companion of the 2017 ACM/IEEE International Conference on Human-Robot Interaction_ , 2017, pp. 187–8.
  * [11] L. Dennis, M. Fisher, M. Slavkovik, and M. Webster, “Formal verification of ethical choices in autonomous systems,” _Robotics and Autonomous Systems_ , vol. 77, pp. 1–14, 2016.
  * [12] J. Svegliato, S. B. Nashed, and S. Zilberstein, “Ethically compliant sequential decision making,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 13, pp. 11 657–11 665, 2021.
  * [13] S. R. Grimm, “How understanding people differs from understanding the natural world,” _Philosophical Issues_ , vol. 26, pp. 209–225, 2016.
  * [14] T. Chakraborti, S. Sreedharan, and S. Kambhampati, “The emerging landscape of explainable automated planning & decision making.” in _IJCAI_ , 2020, pp. 4803–4811.
  * [15] T. Miller, P. Howe, and L. Sonenberg, “Explainable ai: Beware of inmates running the asylum or: How i learnt to stop worrying and love the social and behavioural sciences,” _arXiv:1712.00547_ , 2017.
  * [16] M. Fox, D. Long, and D. Magazzeni, “Explainable planning,” _IJCAI-17 workshop on Explainable AI_ , vol. abs/1709.10256, 2017.
  * [17] A. Garfinkel, _Forms of explanation: rethinking the questions in social theory_. Yale University, 1982.
  * [18] R. Eifler, M. Cashmore, J. Hoffmann, D. Magazzeni, and M. Steinmetz, “A new approach to plan-space explanation: Analyzing plan-property dependencies in oversubscription planning,” in _AAAI_ , 2020, pp. 9818–9826.
  * [19] R. Setchi, M. Dehkordi, and J. Khan, “Explainable robotics in human-robot interactions,” _Knowledge-Based and Intelligent Information & Engineering Systems: Proceedings of the 24th International Conference KES-2020, Virtual Event, 16-18 September 2020_, vol. 176, pp. 3057–3066, 2020\.
  * [20] M. de Graaf and B. Malle, “People’s explanations of robot behavior subtly reveal mental state inferences,” in _2019 14th ACM/IEEE International Conference on Human-Robot Interaction (HRI)_ , 2019, pp. 239–248.
  * [21] M. Edmonds, F. Gao, H. Liu, X. Xie, S. Qi, B. Rothrock, Y. Zhu, Y. Wu, H. Lu, and S.-C. Zhu, “A tale of two explanations: Enhancing human trust by explaining robot behavior,” _Science Robotics_ , vol. 4, no. 37, 2019.
  * [22] J. Broekens, M. Harbers, K. Hindriks, K. van den Bosch, C. Jonker, and J.-J. Meyer, “Do you get it? user-evaluated explainable bdi agents,” in _Multiagent System Technologies_. Springer Berlin Heidelberg, 2010, pp. 28–39.
  * [23] F. Lindner and K. Möllney, “Extracting reasons for moral judgments under various ethical principles,” in _KI 2019: Advances in Artificial Intelligence_ , 2019, pp. 216–29.
  * [24] T. Miller, “Explanation in artificial intelligence: Insights from the social sciences,” _Artificial Intelligence_ , vol. 267, pp. 1–38, 2019.
  * [25] B. Krarup, M. Cashmore, D. Magazzeni, and T. Miller, “Model-based contrastive explanations for explainable planning,” _ICAPS-19 Workshop on Explainable Planning_ , 2019.
  * [26] M. Bentzen, “The Principle of Double Effect applied to Ethical Dilemmas of Social Robots,” in _Proceedings of Robophilosophy 2016_. IOS Press, 2016, pp. 268–279.
  * [27] T. Powers, “Prospects for a kantian machine,” _IEEE Intelligent Systems_ , vol. 21, no. 4, pp. 46–51, 2006.