\sum_{x, y \in X} \frac1{H(\frac xy)} = k \exp\!\left(\Omega\!\left(\sqrt{\min\left(\tfrac{\log k}{\log\log k}, \tfrac{\log U}{\log^2 \log U}\right)}\right)\!\right)\!.
\end{equation*}

We only need a lower bound, so we will ignore all elements in $X \setminus X'$. Fix any element $x = s \prod_{i \in I} p_i \in X'$; we prove a lower bound against $\sum_{y \in X'} 1/H(\frac xy)$. We call an element $y$ good if it has the form $y = s \prod_{i \in J} p_i$, where both $x$ and $y$ have the same factor $s$ and the symmetric difference of $I$ and $J$ has size exactly $2r$ (i.e., $|I \setminus J| = |J \setminus I| = r$) for some parameter $r$ to be specified soon. In the fraction $\frac xy$ only the factors $s$ and $\prod_{i \in I \intersect J} p_i$ cancel and therefore $H(\frac xy) = \Theta(n \log n)^r$. Moreover, the number of good elements $y$ is exactly 0pt[0pt][0pt]$\binom{n/2}r{}^2$, and thus

\begin{equation*}
\sum_{y \in X'} \frac1{H(\frac xy)} \geq \frac{\binom{n/2}{r}^2}{\Order(n \log n)^r} \geq \frac{(\frac n{2r})^{2r}}{\Order(n \log n)^r} = \Omega\!\left(\frac{n}{r^2 \log n}\right)^r\!.
\end{equation*}

Choosing $r = \Theta(\sqrt{n / \log n})$ yields

\begin{equation*}
\sum_{y \in X'} \frac1{H(\frac xy)} \geq \exp(\Omega(r)) = \exp\!\left(\Omega\!\left(\sqrt{\min\left(\tfrac{\log k}{\log\log k}, \tfrac{\log U}{\log^2 \log U}\right)}\right)\!\right)\!.
\end{equation*}

Recall that $x \in X'$ was arbitrary and thus the claim follows by summing over all $x \in X'$.

Let $X$ be as before, choose $x = 0$ and choose $a = b = 0$. For now we also fix $y, z \in X$ but we will later in the proof unfix $y, z$ and treat them as random variables. The first steps are quite similar to the proof of <ref>. Let $I = \{ i \in [p] : i \bmod m = 0 \}$. Then $\residue I$ is an arithmetic progression in $\Int_p$. For $\residue h(\residue x) = \residue\sigma \residue x + \residue\tau$ a random linear function on $\Int_p$, we obtain:

\begin{align*}
&\Pr(h(y) = h(z) = b \mid h(x) = a) \\
={} &\Pr((\residue h(\residue y), \residue h(\residue z)) \in \residue I^2 \mid \residue h(\residue x) \in \residue I) \\
={} &\frac1{|\residue I|} \sum_{\residue u \in \residue I} \Pr((\residue h(y), \residue h(\residue z)) \in \residue I^2 \mid \residue h(\residue x) = \residue u).
\end{align*}

We continue to bound every term in the sum from below, so fix some value $\residue u \in \residue I$. As $\residue h(\residue x) = \residue\tau$ and $\residue h(\residue y) - \residue h(\residue x) = \residue\sigma \residue y$ are independent, we can omit the condition and it suffices to bound

\begin{align*}
&\Pr((\residue h(\residue y), \residue h(\residue z)) \in \residue I^2 \mid \residue h(\residue x) = \residue u) \\
={} &\Pr((\residue\sigma \residue y, \residue\sigma \residue z) \in (\residue I - \residue u)^2)
\intertext{Let $T = \floor{\frac p{2m}}$ and observe that either $\residue J = \{ \residue i \residue m : i \in [T] \}$ or $\{ -\residue i \residue m : i \in [T] \}$ is contained in $\residue I - \residue u$. In both cases we may replace $\residue I - \residue u$ by $\residue J$ (in the latter case we replace also $\residue\sigma$ by $-\residue\sigma$ which does not change the probability):}
\geq{} &\Pr((\residue\sigma \residue y, \residue\sigma \residue z) \in \residue J^2) \\
={} &\frac{|\residue y^{-1} \residue J \cap \residue z^{-1} \residue J|}p \\
={} &\frac1p \sum_{i, j \in [T]} \left[ \residue i \residue y^{-1} \residue m = \residue j \residue z^{-1} \residue m \right] \\
={} &\frac1p \sum_{i, j \in [T]} \left[ \residue i \residue j^{-1} = \residue y \residue z^{-1} \right]
\intertext{We claim that there are at least $\Omega(T / H(\frac yz))$ solutions $i, j \in [T]$ to the equation $\residue i \residue j^{-1} = \residue y \residue z^{-1}$. Indeed, consider the reduced fraction \raisebox{0pt}[0pt][0pt]{$\frac{y'}{z'} = \frac yz$} (i.e., $y'$ and $z'$ are coprime and $0 < y', z' \leq H(\frac yz)$ by definition). For any $t < T / H(\frac yz)$ we may pick $i = t y'$ and $j = t z'$. On the one hand we have that~$i$ and~$j$ have the correct size since $i = t y' < (T / H(\frac yz)) \mult H(\frac yz) = T$ and on the other hand the equation is satisfied by \raisebox{0pt}[0pt][0pt]{$\residue i \residue j^{-1} = \residue t \residue{y'} \residue t^{-1} \residue{z'}{}^{-1} = \residue y \residue z^{-1}$}. Hence:}
\geq{} &\Omega\left(\frac T{p H(\frac yz)}\right) \\
={} &\Omega\left(\frac1{m H(\frac yz)}\right).
\end{align*}

We now unfix $y, z$ and consider them as random variables. By averaging over the previous inequality and by applying <ref> we finally obtain:

\begin{align*}
&\Pr(h(y) = h(z) = b \mid h(x) = a) \\
\geq{} &\Omega\left(\frac1{mk^2} \sum_{y, z \in X} \frac1{H(\frac yz)}\right) \\
\geq{} &\frac1{mk} \exp\!\left(\Omega\!\left(\sqrt{\min\left(\tfrac{\log k}{\log\log k}, \tfrac{\log U}{\log^2 \log U}\right)}\right)\!\right)\!. \qedhere
\end{align*}

[1]
Gaussian smoothing.

[2]
Karl R. Abrahamson.
Generalized string matching.
SIAM J. Comput., 16(6):1039–1051, 1987.

[3]
Peyman Afshani, Casper B. Freksen, Lior Kamma, and Kasper G. Larsen.
Lower bounds for multiplication via network coding.
In Proceedings of the 46th International Colloquium Automata,
Languages, and Programming, ICALP '19, pages 10:1–10:12. Schloss
Dagstuhl–Leibniz-Zentrum für Informatik, 2019.

[4]
Amihood Amir, Ayelet Butman, and Ely Porat.
On the relationship between histogram indexing and block-mass
Philosophical Transactions of the Royal Society A:
Mathematical, Physical and Engineering Sciences, 372, 2014.

[5]
Amihood Amir, Oren Kapah, and Ely Porat.
Deterministic length reduction: Fast convolution in sparse data and
In Proceedings of the 18th Symposium on Combinatorial Pattern
Matching, CPM '07, pages 183–194. Springer, 2007.

[6]
Amihood Amir, Moshe Lewenstein, and Ely Porat.
Faster algorithms for string matching with $k$ mismatches.
J. Algorithms, 50(2):257–275, 2004.

[7]
Andrew Arnold and Daniel S. Roche.
Output-sensitive algorithms for sumset and sparse polynomial
In Proceedings of the 40th International Symposium on Symbolic
and Algebraic Computation, ISSAC '15, pages 29–36. ACM, 2015.

[8]
MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff
Fast algorithms for knapsack via convolution and prediction.
In Proceedings of the 50th ACM Symposium on Theory of
Computing, STOC '18, pages 1269–1282. ACM, 2018.

[9]
Michael Ben-Or and Prasoon Tiwari.
A deterministic algorithm for sparse multivariate polynomial
In Proceedings of the 20th ACM Symposium on Theory of
Computing, STOC '88, pages 301–309. ACM, 1988.

[10]
Leo I. Bluestein.
A linear filtering approach to the computation of discrete Fourier
IEEE Transactions on Audio and Electroacoustics,
18(4):451–455, 1970.

[11]
Karl Bringmann.
A near-linear pseudopolynomial time algorithm for subset sum.
In Proceedings of the 28th ACM-SIAM Symposium on Discrete
Algorithms, SODA '17, pages 1073–1084. SIAM, 2017.

[12]
Karl Bringmann and Vasileios Nakos.
Top-$k$-convolution and the quest for near-linear output-sensitive
subset sum.
In Proceedings of the 52nd ACM Symposium on Theory of
Computing, STOC '20, pages 982–995. ACM, 2020.

[13]
David E. Cardoze and Leonard J. Schulman.
Pattern matching for spatial point sets.
In Proceedings of the 39th IEEE Annual Symposium on
Foundations of Computer Science, FOCS '98, pages 156–165. IEEE Computer
Society, 1998.

[14]
Timothy M. Chan and Qizheng He.
Reducing 3SUM to convolution-3SUM.
In Proceedings of the 3rd Symposium on Simplicity in
Algorithms, SOSA '20, pages 1–7. SIAM, 2020.

[15]
Timothy M. Chan and Moshe Lewenstein.
Clustered integer 3SUM via additive combinatorics.
In Proceedings of the 47th ACM Symposium on Theory of
Computing, STOC '15, pages 31–40. ACM, 2015.

[16]
Richard Cole and Ramesh Hariharan.
Verifying candidate matches in sparse and wildcard matching.
In Proceedings of the 34th ACM Symposium on Theory of
Computing, STOC '02, pages 592–601. ACM, 2002.

[17]
A. Dutt and Vladimir Rokhlin.
Fast Fourier transforms for nonequispaced data.
SIAM J. Comput., 14(6):1368–1393, 1993.

[18]
Michael J. Fischer and Michael S. Paterson.
String matching and other products.
Complexity of Computation, 7:113–125, 1974.

[19]
Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, and Martin J.
Near-optimal sparse Fourier representations via sampling.
In Proceedings of the 34th ACM Symposium on Theory of
Computing, STOC '02, pages 152–161. ACM, 2002.

[20]
Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss.
Approximate sparse recovery: Optimizing time and measurements.
In Proceedings of the 42nd ACM Symposium on Theory of
Computing, STOC '10, pages 475–484. ACM, 2010.

[21]
Anna C. Gilbert, S. Muthukrishnan, and Martin J. Strauss.
Improved time bounds for near-optimal space Fourier
Proceedings of SPIE – The International Society for Optical
Engineering, 2005.

[22]
Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra, and Martin J. Strauss.
$L_2/L_2$-foreach sparse recovery with low risk.
In Proceedings of the 40th International Colloquium Automata,
Languages, and Programming, ICALP '13, pages 461–472. Springer, 2013.

[23]
Pascal Giorgi, Bruno Grenet, and Armelle Perret du Cray.
Essentially optimal sparse polynomial multiplication.
In Proceedings of the 45th International Symposium on Symbolic
and Algebraic Computation, ISSAC '20, pages 202–209. ACM, 2020.

[24]
Bernard Gold and Charles M. Rader.
Digital processing of signals.
Krieger, 1969.

[25]
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price.
Nearly optimal sparse Fourier transform.
In Proceedings of the 44th ACM Symposium on Theory of
Computing, STOC '12, pages 563–578. ACM, 2012.

[26]
Ishay Haviv and Oded Regev.
The restricted isometry property of subsampled Fourier matrices.
In Geometric aspects of functional analysis, pages 163–179.
Springer, 2017.

[27]
Qiao-Long Huang.
Sparse polynomial interpolation over fields with large or zero
In Proceedings of the 44th International Symposium on Symbolic
and Algebraic Computation, ISSAC '19, pages 219–226. ACM, 2019.

[28]
Piotr Indyk.
Faster algorithms for string matching problems: matching the
convolution bound.
In Proceedings of the 39th IEEE Annual Symposium on
Foundations of Computer Science, FOCS '98, pages 166–173. IEEE Computer
Society, 1998.

[29]
Piotr Indyk and Michael Kapralov.
Sample-optimal Fourier sampling in any constant dimension.
In Proceedings of the 55th IEEE Annual Symposium on
Foundations of Computer Science, FOCS '14, pages 514–523. IEEE Computer
Society, 2014.

[30]
Piotr Indyk, Michael Kapralov, and Eric Price.
(Nearly) sample-optimal sparse Fourier transform.
In Proceedings of the 25th ACM-SIAM Symposium on Discrete
Algorithms, SODA '14, pages 480–499. SIAM, 2014.

[31]
Piotr Indyk, Eric Price, and David P. Woodruff.
On the power of adaptivity in sparse recovery.
In Proceedings of the 52nd IEEE Annual Symposium on
Foundations of Computer Science, FOCS '11, pages 285–294. IEEE Computer
Society, 2011.

[32]
Klaus Jansen and Lars Rohwedder.
On integer programming and convolution.
In Proceedings of the 10th Innovations in Theoretical Computer
Science Conference, ITCS '19, pages 43:1–43:17. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019.

[33]
Svante Janson.
Tail bounds for sums of geometric and exponential variables.
Statistics & Probability Letters, 135:1–6, 2018.

[34]
Erich Kaltofen and Yagati N. Lakshman.
Improved sparse multivariate polynomial interpolation algorithms.
In Proceedings of the 13th International Symposium on Symbolic
and Algebraic Computation, ISAAC '88, pages 467–474. Springer, 1988.

[35]
Michael Kapralov.
Sparse Fourier transform in any constant dimension with
nearly-optimal sample complexity in sublinear time.
In Proceedings of the 48th ACM Symposium on Theory of
Computing, STOC '16, pages 264–277. ACM, 2016.

[36]
Michael Kapralov.
Sample efficient estimation and recovery in sparse FFT via
isolation on average.
In Proceedings of the 58th IEEE Annual Symposium on
Foundations of Computer Science, FOCS '17, pages 651–662. IEEE Computer
Society, 2017.

[37]
Michael Kapralov, Ameya Velingker, and Amir Zandieh.
Dimension-independent sparse Fourier transform.
In Proceedings of the 30th ACM-SIAM Symposium on Discrete
Algorithms, SODA '19, pages 2709–2728. SIAM, 2019.

[38]
Howard J. Karloff.
Fast algorithms for approximately counting mismatches.
Inf. Process. Lett., 48(2):53–60, 1993.

[39]
Mathias B. T. Knudsen.
Linear hashing is awesome.
In Proceedings of the 57th IEEE Annual Symposium on
Foundations of Computer Science, FOCS '16, pages 345–352. IEEE Computer
Society, 2016.

[40]
Konstantinos Koiliaris and Chao Xu.
Faster pseudopolynomial time algorithms for subset sum.
ACM Trans. Algorithms, 15(3):40:1–40:20, 2019.

[41]
Tsvi Kopelowitz and Ely Porat.
A simple algorithm for approximating the text-to-pattern hamming
In Proceedings of the 1st Symposium on Simplicity in
Algorithms, SOSA '18, pages 10:1–10:5. Schloss Dagstuhl–Leibniz-Zentrum
fuer Informatik, 2018.

[42]
Lei Li.
On the arithmetic operational complexity for solving Vandermonde
linear equations.
Japan Journal of Industrial and Applied Mathematics, 17, 2000.

[43]
Michael Monagan and Roman Pearce.
Parallel sparse polynomial multiplication using heaps.
In Proceedings of the 34th International Symposium on Symbolic
and Algebraic Computation, ISSAC '09, pages 263–270. ACM, 2009.

[44]
Michael Monagan and Roman Pearce.
POLY: A new polynomial data structure for Maple 17.
In Computer Mathematics, pages 325–348. Springer, 2014.

[45]
Michael Monagan and Roman Pearce.
The design of Maple's sum-of-products and POLY data structures
for representing mathematical objects.
ACM Communications in Computer Algebra, 48(3/4):166–186,

[46]
Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk.
A subquadratic approximation scheme for partition.
In Proceedings of the 30th ACM-SIAM Symposium on Discrete
Algorithms, SODA '19, pages 70–88. SIAM, 2019.

[47]
Shanmugavelayutham Muthukrishnan.
New results and open problems related to non-standard stringology.
In Proceedings of the 6th Symposium on Combinatorial Pattern
Matching, CPM '95, pages 298–317. Springer, 1995.

[48]
Vasileios Nakos.
Nearly optimal sparse polynomial multiplication.
IEEE Trans. Inf. Theory, 66(11):7231–7236, 2020.

[49]
Vasileios Nakos, Zhao Song, and Zhengyu Wang.
(Nearly) sample-optimal sparse Fourier transform in any
dimension; RIPless and filterless.
In Proceedings of the 60th IEEE Annual Symposium on
Foundations of Computer Science, FOCS '19, pages 1568–1577. IEEE Computer
Society, 2019.

[50]
Victor Pan.
Structured matrices and polynomials: Unified superfast

[51]
Mihai Patrascu.
Towards polynomial lower bounds for dynamic problems.
In Proceedings of the 42nd ACM Symposium on Theory of
Computing, STOC '10, pages 603–610. ACM, 2010.

[52]
Nicholas Pippenger.
On the evaluation of powers and monomials.
SIAM J. Comput., 9(2):230–250, 1980.

[53]
Eric Price and Zhao Song.
A robust sparse Fourier transform in the continuous setting.
In Proceedings of the 56th IEEE Annual Symposium on
Foundations of Computer Science, FOCS '15, pages 583–600. IEEE Computer
Society, 2015.

[54]
Eric Price and David P. Woodruff.
Applications of the Shannon-Hartley theorem to data streams and
In Proceedings of the 45th IEEE International Symposium on
Information Theory, ISIT '12, pages 2446–2450. IEEE, 2012.

[55]
Daniel S. Roche.
Adaptive polynomial multiplication.
Proceedings of Milestones in Computer Algebra, pages 65–72,

[56]
Daniel S. Roche.
Chunky and equal-spaced polynomial multiplication.
Journal of Symbolic Computation, 46(7):791–806, 2011.

[57]
Daniel S. Roche.
What can (and can't) we do with sparse polynomials?
In Proceedings of the 43rd International Symposium on Symbolic
and Algebraic Computation, ISSAC '18, pages 25–30. ACM, 2018.

[58]
J. Barkley Rosser and Lowell Schoenfeld.
Approximate formulas for some functions of prime numbers.
Illinois J. Math., (1):64–94, 1962.

[59]
Atri Rudra.
(Dense structured) matrix vector multiplication, lecture notes.

[60]
Allan Steel.
Multivariate polynomial rings.

[61]
Joris Van Der Hoeven and Grégoire Lecerf.
On the complexity of multivariate blockwise polynomial
In Proceedings of the 37th International Symposium on Symbolic
and Algebraic Computation, ISSAC '12, pages 211–218. ACM, 2012.

[62]
Joris Van Der Hoeven and Grégoire Lecerf.
On the bit-complexity of sparse polynomial and series multiplication.
Journal of Symbolic Computation, 50:227–254, 2013.

[63]
Joachim von zur Gathen and Jürgen Gerhard.
Modern Computer Algebra.
Cambridge University Press, 3 edition, 2013.

[64]
Jack K. Wolf.
Decoding of Bose-Chaudhuri-Hocquenghem codes and Prony's
method for curve fitting.
IEEE Transactions on Information Theory, 13(4):608–608,

[65]
Andrew Chi-Chih Yao.
On the evaluation of powers.
SIAM J. Comput., 5(1):100–103, 1976.

§ COMPUTATIONS WITH TRANSPOSED VANDERMONDE MATRICES

The goal of this section is prove the following theorem:

Throughout, let $V = V(a)$ be as in the statement and let $W = W(a) = V(a)^T$ denote its transpose, i.e. a Vandermonde matrix. The proof of <ref> is by the so-called transposition principle: First, classic algorithms show that $W x$ and $W^{-1} x$ can be computed by efficient arithmetic circuits (<ref>). Second, whenever $A x$ can be computed efficiently by an arithmetic circuit, then also $A^T x$ can be computed similarly efficiently (<ref>).

See [59, 63] for a definition of arithmetic circuits. For our purposes it suffices to only consider addition, subtraction and multiplication gates.

There exists an algorithm $\mathcal A$ which, given $a \in F^n$ with pairwise distinct entries $a_i$, computes arithmetic circuits $C$ and $D$ such that:

* $\mathcal A$ runs in time $\Order(n \log^2 n)$,

* $\mathcal A$ uses at most $\Order(n \log^2 n)$ ring operations and at most 1 division,

* On input $x \in F^n$, the circuit $C$ computes $C(x) = W(a) x$ and $D$ computes $D(x) = W(a)^{-1} x$.

For $C$, note that evaluating $C(x) = W(a) x$ is exactly the problem of evaluating the polynomial $\sum_i x_i X^i \in F[X]$ at the points $a_1, \dots, a_n$. Hence, we can use the classical $\Order(n \log^2 n)$-time algorithm for polynomial multi-point evaluation, see e.g. <cit.>. This algorithm can be interpreted to compute the arithmetic circuit $C$ rather than computing the multi-point evaluation directly. As this algorithm works over rings, it does not use any divisions.

For $D$, observe that computing $D(x) = W(a)^{-1} x$ corresponds to polynomial interpolation, which again has a classical $\Order(n \log^2 n)$-time algorithm <cit.>. This time however, we have to pay attention to the number of divisions performed in the process. Note that <cit.> only computes divisions in the second step, all of which can be bulked together by <ref>, and moreover all inputs to these divisions only depend on $a$ and can thus be performed by the algorithm $\mathcal A$, rather than by the arithmetic circuit $D$. This proves the claim.

Next, we need the following lemma which can be proven in several ways, for instance via the Baur-Strassen Theorem; see <cit.>.

If for some matrix $A \in F^{n \times n}$, the function $x \mapsto A x$ is computed by an arithmetic circuit $C$ of size $s$, then the function $x \mapsto A^T x$ is computed by an arithmetic circuit $C'$ of size $\Order(s + n)$. Moreover, one can compute $C'$ from $C$ in time $\Order(s + n)$.

First, we run the algorithm $\mathcal A$ from <ref> to compute arithmetic circuits $C$ and $D$ of size $s = \Order(n \log^2 n)$. Recall that $\mathcal A$ uses $\Order(n \log^2 n)$ ring operations plus a single division. The circuits compute $C(x) = W(a) x$ and $D(x) = W(a)^{-1} x$, respectively. Second, use the transposition principle (<ref>) to compute circuits $C'$ and $D'$ with $C'(x) = W(a)^T x = V(a) x$ and $D'(x) = (W(a)^{-1})^T x = V(a)^{-1} x$. By <ref>, $C'$ and $D'$ also have size $\Order(s + n) = \Order(n \log^2 n)$ and we can compute both in the same running time. Finally, we evaluate $C'$ and $D'$ at $x$, which again takes time $\Order(n \log^2 n)$ and uses only ring operations.


11institutetext: Universite Libre de Bruxelles. Belgium 22institutetext:
Aalborg University, Denmark
33institutetext: TU Wien, Austria

# The Susceptibility of Example-Based Explainability Methods to Class Outliers

Ikhtiyor Nematov 1122 Dimitris Sacharidis 11 Katja Hose 33 Tomer Sagi 22

###### Abstract

This study explores the impact of class outliers on the effectiveness of
example-based explainability methods for black-box machine learning models. We
reformulate existing explainability evaluation metrics, such as correctness
and relevance, specifically for example-based methods, and introduce a new
metric, distinguishability. Using these metrics, we highlight the shortcomings
of current example-based explainability methods, including those who attempt
to suppress class outliers. We conduct experiments on two datasets, a text
classification dataset and an image classification dataset, and evaluate the
performance of four state-of-the-art explainability methods. Our findings
underscore the need for robust techniques to tackle the challenges posed by
class outliers.

###### Keywords:

explainability interpretability explainability evaluation.

##  1 Introduction

In example-based explainability, the model is explained through the lens of
the _data_ on which it has been trained, rather than through features the
model has learned. Example-based explainability is particularly useful when
the model is a black-box, and the features are not interpretable. Moreover,
example-based explainability allows the human to interpret a model’s outcome
through comparison and contrast. For example in image classification, the
human can understand why a model classified an image as a cat by comparing it
with similar images of cats and contrasting it with images of other animals.

Example-based explainability can take on either a local perspective [1, 3, 6,
7] explaining specific examples by showcasing influential training examples,
or a global one [4, 8], providing an overarching understanding of the model
through analysis of representative examples. Our focus is on local example-
based explainability. Various approaches have been proposed for this,
including methods based on robust statistics, game theory, internal analysis
of neural networks, and empirical techniques. These approaches share a common
feature: they quantify the importance of training examples in determining the
model’s outcomes. Despite their diverse origins, we demonstrate that they all
are susceptible to the presence of _class outliers_ within the dataset. Class
outliers are training examples with high loss. Class outliers have inherent
ambiguity, partly exhibiting the characteristics of other classes, and are
difficult to classify into one of the predefined classes (see Figure 1), even
by a human domain expert. We posit that these outliers manifest as
explanations for multiple explanandums (instances to be explained) without
contributing substantive explanation power.

To illustrate the impact of class outliers, consider Figure 1, where the two
training images most frequently presented as explanations for an image
classification model are depicted, as identified by different explainability
mechanisms. As we can see for the first three explainers, these images are
ambiguous and hard to classify even for a human. Identifying such examples is
helpful when the intent is to debug the model. However these examples offer no
insights to particular explanandums to be explained, as they tend to be
irrelevant and non-specific. We verify these claims quantitatively by showing
that these explainers have low _relevance_ and low _distinguishability_ ; see
Section 3 for precise definitions. Therefore, there is a need to improve the
robustness of example-based explainability methods to class outliers.
Moreover, we find that existing methods (e.g., [1] in Figure 1(d)) that aim to
suppress these globally influential examples from appearing in explanations
suffer in another aspect, the _correctness_ or faithfulness of the explainer.
We argue that class outliers can aid in explaining outcomes for similar
ambiguous explanandum and should not be suppressed in such instances.

Overall, our study reveals that (a) existing example-based explainability
methods are not robust to class outliers, and (b) attempting to improve
robustness by suppressing class outliers can lead to a loss of correctness. We
propose a new evaluation framework, specifically for example-based explainers,
including metrics for relevance, distinguishability, and correctness, and
which can quantitatively assess the impact of class outliers on the
effectiveness of explainers.

(a) IF[7]

(b) DM[6]

(c) TraceIn[3]

(d) RIF[1]

Figure 1: The two most popular images that are returned as explanations for
four different explainability methods.

##  2 Related Work

One prominent example-based explainability technique is influence function
(IF) [7] which is an approximation of leave-one-out ideology. It borrows from
the robust statistics the idea of estimating the change in model parameters
when an infinitesimal change is applied to the training data distribution.
Many other works followed the concept of quantifying the contribution of a
single datum for a prediction. In [1] the authors have demonstrated that
examples with a high loss will have a global influence on the model overall
and they will be provided as explanations for many examples. They proposed
relative influence (RIF), with a loss-based elimination technique that
penalizes the influence score relative to its global effect. They claim that
such elimination will provide explanations relevant to the explanandum of
interest. Another method with the same concept but a different nature is
TraceIn [3]. It gauges the impact of a training example $x$ on a particular
test example $x^{\prime}$ by quantifying the cumulative change in loss on
$x^{\prime}$ resulting from updates made during training with mini-batches
containing $x$. The approximation of this calculation involves considering
checkpoints throughout the training process and calculating the sum of dot
products of gradients at $x$ and $x^{\prime}$ at each checkpoint.

Datamodels (DM) [6] on the other hand is a more empirical method. It involves
sampling numerous subsets from the training set and training individual models
with each of these subsets. Subsequently, a linear model is trained, where the
input comprises the encoding of a subset, and the output reflects the
performance of the model trained on this subset for the designated test
example. The weights of the linear model serve to represent the importance
score of a training example in the corresponding position. To overcome the
exhaustiveness of training numerous intermediate models, [10] introduced a
faster version of datamodels, claiming to maintain similar accuracy.

The ubiquity of explainability methods has triggered research on finding
metrics to evaluate their effectiveness. [2] identifies three evaluation
strategies: application-grounded, human-grounded, and functionality-grounded.
Our work focuses on the functionality-grounded approach. We reformulate
existing metrics like relevance [5] and correctness [9], and introduce a new
metric called distinguishability.

##  3 Evaluation Framework

###  3.1 Notation

Consider a binary classification model $f:\mathcal{X}\rightarrow\\{0,1\\}$
that is trained on a dataset $(X,y)$, where $X\subseteq\mathcal{X}$ and
$y\in\\{0,1\\}^{|X|}$. We call _explanandum_ an instance $t\in\mathcal{X}$ to
be explained. An example-based explainer assigns to each explanandum $t$, or
more precisely to the model’s outcome $f(t)$, an _explanation_ $E(t)$, which
is a set of _examples_ that correspond to training examples and are
accompanied by a _score_ that indicates their importance for outcome $f(t)$.
For a given example $e\in E(t)$, we denote the features of the training
example as $e.x$, its label as $e.y$, and its score as $e.s$.

###  3.2 Explainer Relevance

We want the explanation to be _relevant_ to the explanandum to be explained
[5]. We define the _explanation relevance_ of an explanation $E(t)$ as the
average similarity between the explanandum $t$ and the examples in its
explanation $E(t)$. To evaluate the overall relevance of an explainer, we
define the _explainer relevance_ as the expected value of explanation
relevance:

$\text{Rel}=\mathbb{E}_{t}\left[\frac{1}{|E(t)|}\sum_{e\in
E(t)}\text{sim}(t,e.x)\right],$

where the function $sim()$ is a domain-specific semantic similarity that
quantifies how close two examples from $\mathcal{X}$ are, and takes values in
$[0,1]$, where higher values indicate more similarity. Consequently, Rel takes
values in $[0,1]$, where higher values are preferred indicating that the
explainer produces relevant explanations.

###  3.3 Explainer Distinguishability

Distinguishability refers to the capacity of an explainer to provide distinct
and _specific_ explanations for different explanandum. This is crucial for
understanding how a model produces outcomes in a localized manner. We define
several ways to capture different aspects of distinguishability. The _example
popularity_ quantifies the probability that a training example serves as an
example in an explanation:

$\text{Pop}(x)=\mathbb{E}_{t}\left[\mathbb{I}\\{e\in E(t)\wedge
e.x=x\\}\right],$

where $\mathbb{I}$ is an indicator function used to convert a condition into a
binary value (0 or 1). The distribution of example popularity indicates the
capacity of the explainer to provide distinct explanations. If the
distribution is heavily skewed/assymetric, it means that a few examples are
used very frequently in explanations, while many other examples are used
rarely or not at all. This indicates that the explainer relies on a limited
subset of examples, leading to lower distinguishability, as the explanations
for different explanandums are less diverse and more similar to each other.

The _active domain_ measures the number of distinct training examples that are
used by an explainer; equivalently, it measures the number of training
examples with nonzero example popularity. Concretely, it is the maximum number
of distinct training examples that are used to explain any set $T$ of
explanandum:

$\text{Dom}=\sup_{T\subset\mathcal{X}}\left|\\{x\in X\ |\ \exists t\in T,\
e\in E(t)\wedge e.x=x\\}\right|.$

The narrower the active domain is, the less distinguishability the explainer
has, as more examples are repeated across explanations. Note that we can
normalize the active domain measure in the $[0,1]$ range by dividing it by
$|X|$.

The _explanation overlap_ measures the expected Jaccard similarity between any
two random explanations:

$\text{Over}=\mathbb{E}_{t,t^{\prime}}\left[\frac{E(t)\cap
E(t^{\prime})}{E(t)\cup E(t^{\prime})}\right].$

Clearly, the higher the overlap is, the less distinguishability the explainer
has.

###  3.4 Explainer Correctness

A desired property for an explainer is to produce explanations that are
faithful to the predictive model [9]. Here we define a measure of faithfulness
with respect to a rule that dictates how training data are labeled. We want
the explainer to be able to identify the rule in its explanations.

Consider a _rule_ of the form $c(x)\implies y=1$, where $c$ is a condition
that applies to examples from $\mathcal{X}$. We say that a training pair
$(x,y)$ _follows_ the rule if $c(x)$ is true and $y=1$. We say that a training
pair $(x,y)$ _breaks_ the rule if $c(x)$ is true but $y=0$. Consider an
explanandum that satisfies the rule condition. Then, we would like the
explainer to return an explanation that includes both rule followers and
breakers as examples. The idea is that the explainer should be able to surface
the rule in its explanations. We define _explainer correctness_ with respect
to $c$ as the average proportion of rule followers and breakers in the
explanation of any explanandum that satisfies the rule condition:

$\text{Cor}(c)=\mathbb{E}_{t:c(t)}\frac{1}{|E(t)|}\\{e\in E(t)\wedge
c(e.x)\\}.$

Correctness quantifies the degree to which the explanations align with the
underlying labeling rule. Higher correctness indicate that the explainer is
more truthful to the rule $c$. Observe that correctness is essentially the
precision with which an explainer returns rule followers and breakers.
Finally, we note that an important assumption is that the model $f$ is itself
truthful to the rule, i.e., it has correctly learned the rule $c$, a condition
we can check after training.

##  4 Experiments and Analysis

In our experiments, we used two datasets: the SMS Spam
dataset111https://www.kaggle.com/datasets/uciml/sms-spam-collection-dataset,
which comprises a collection of text messages labeled as either spam or non-
spam (ham), commonly used for text classification; and a dataset with pictures
of dogs and fish extracted from Imagenet222https://www.image-net.org/ and used
in [7]. For the spam classification task, we employed a BERT-based pre-trained
word embedding model and incorporated two sequential layers to capture the
specific characteristics of our data. Regarding the image classification task,
we utilized a pre-trained InceptionV3 model removing the output layer and
appending sequential layers to learn the peculiarity of our task. Our
benchmark methods are IF [7], RIF [1], DM [6], and TraceIn [3]. All methods
were implemented with instructions given in their papers and GitHub
repositories. We vary the number $N$ of examples in the explanation set to
evaluate the performance of the explainers; we set $N=\\{2,5,10\\}$.

###  4.1 Relevance

We employ cosine similarity to compute relevance, given that the dataset
comprises image embeddings produced by a pre-trained model. Utilizing the
graph representation, we determine the average similarity between a
explanandum node (explanandum) and its corresponding neighbors (example). The
first column of Table 1, shows the explainer relevance. RIF demonstrates
superior performance, whereas the remaining methods exhibit similar scores.

Table 1: Evaluation of different explainers (image classification)

| Relevance | Active Domain | Overlap | Correctness
---|---|---|---|---
N=2 | N=5 | N=10 | N=2 | N=5 | N=10 | N=2 | N=5 | N=10 | N=2 | N=5 | N=10
IF | 0.5 | 0.52 | 0.52 | 0.095 | 0.059 | 0.040 | 0.14 | 0.14 | 0.16 | 0.76 | 0.8 | 0.82
DM | 0.55 | 0.54 | 0.53 | 0.21 | 0.1 | 0.06 | 0.04 | 0.06 | 0.1 | 0.7 | 0.75 | 0.79
TraceIn | 0.56 | 0.55 | 0.27 | 0.017 | 0.017 | 0.018 | 0.31 | 0.56 | 0.4 | 0.31 | 0.31 | 0.4
RIF | 0.74 | 0.76 | 0.68 | 0.366 | 0.22 | 0.15 | 0.02 | 0.03 | 0.06 | 0.2 | 0.3 | 0.3

###  4.2 Distinguishability

We start by examining the popularity of examples in explanations. We plot the
probability density function (PDF) of example popularity (Pop) in Figure 2. We
observe significant discrepancies in popularity probabilities among IF, DM,
and TraceIn. Although RIF displays a smaller discrepancy and a more dense PDF,
some examples still have relatively higher probabilities of appearance.

(a) IF

(b) DM

(c) TracIn

(d) RIF

Figure 2: Popularity probability density function (image classification)

To draw more insights on which are the popular examples, we plot the
popularity of an example versus its loss in Figure 3. We observe that the
examples that appear in the explanation for many explanandums have usually
high loss. Figure 1 depicts the top 2 most popular examples for each method.
These are class outliers that are hard for the model to classify and thus they
have a high loss and are globally influential. RIF effectively eliminates such
examples from its explanation using its loss-based outlier elimination.

(a) IF

(b) DM

(c) TraceIn

(d) RIF

Figure 3: Popularity vs. Loss (image classification)

Next, we explore the active domain for the explainers; the larger the active
domain, the more distinguishable the explainer is. As the second column of
Table 1 shows, RIF draws from a broader domain to provide explanations, making
them more distinguishable. We also evaluate explanation overlap, which
indicates the similarity of explanations for any pair of explanandums; smaller
values signify higher distinguishability. The third column on Table 1 shows
that DM and RIF offer more distinguishable explanations, whereas IF and
TraceIn have higher explanation overlap with repeating examples in
explanations.

###  4.3 Correctness

In this experiment, three rules were employed on the text classification
dataset. Rule 1: All French messages are “spam”. Rule 2: if the message is
shorter than 30 and it contains “?”, it’s labeled “spam”. Rule 3: If a message
contains a sequence of 4 consecutive digits, it’s labeled “ham”.

Before evaluating the correctness of the explanation, it is crucial to ensure
that the model accurately reflects the rule and has effectively learned it.
Three metrics are used for this assessment: 1\. Accuracy of Learning the Rule:
This metric evaluates the model’s performance on test samples that correspond
to the rule. 2\. Log-Likelihood: It is expected that there will be a
significant change in the log-likelihood of intervened points ($LL_{i}$) after
the introduction of the rule, while the log-likelihood of untouched points
($LL_{u}$) should remain relatively stable. 3\. Probability Scores: A notable
change is anticipated in the probability scores of intervened points
($Ps_{i}$) compared to the untouched points ($Ps_{u}$). Table 2 illustrates
the results of these metrics. In all cases, the model has successfully learned
the rule without affecting its decisions for the untouched points.

Table 2: Model’s assessment in learning the rules | Acc | $LL_{i}$ | $LL_{u}$ | $Ps_{i}$ | $Ps_{u}$
---|---|---|---|---|---
Rule 1 | 0.83 | Before | -5.87 | -9.4 | 100 | 15
| After | -0.42 | -9.2
Rule 2 | 0.85 | Before | -12 | -9.3 | 100 | 24.5
| After | -3.4 | -7.2
Rule 3 | 0.92 | Before | -0.07 | -10.6 | 98 | 12
| After | -1.83 | -9.5

While explaining an explanandum following the rule we expect rule-followers in
the training set with the same label to have a positive influence on the
prediction, and rule-breakers with the opposite label to have a negative
influence. Table 1 shows that IF and DataModels perform well in terms of
correctness, but are inconsistent in relevance and distinguishability (domain
and overlap), which is expected due to the presence of globally important
class outliers. In contrast, RIF performs poorly in uncovering followers and
breakers, because of its loss-based outlier elimination. RIF treats training
data with high loss as undesired, and excludes them from explanation lists—the
rationale is that such data would appear in all explanations and thus have
little utility. But in this case, it is precisely the rule followers and
particularly the minority of rule breakers that have high losses due to the
ambiguity in the labeling rule. On the contrary, as previously discussed, the
examples with very low loss are rewarded and appear in the explanations.
TraceIn also fails to uncover the rule due to its low efficiency in
identifying truly important examples, as demonstrated in [10].

##  5 Conclusion

Our analysis suggests that current example-based explainability techniques are
susceptible to the influence of class outliers. Outright removal of outliers
from explanations or datasets may not always be advisable, as they can possess
valuable insights and provide explanations for similar examples encountered by
models. Future research could focus on devising more robust explainability
methods capable of extracting values from class outliers without compromising
the quality of explanations using our proposed metrics.

## References

  * [1] Barshan, E., Brunet, M.E., Dziugaite, G.K.: Relatif: Identifying explanatory training examples via relative influence. PMLR (2020)
  * [2] Doshi-Velez, F., Kim, B.: Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv:1702.08608 (2017)
  * [3] Garima, Liu, F., Kale, S., Sundararajan, M.: Estimating training data influence by tracing gradient descent. In: Proceedings of the 34th International Conference on Neural Information Processing Systems. NIPS’20, Curran Associates Inc., Red Hook, NY, USA (2020)
  * [4] Ghorbani, A., Zou, J.: Data shapley: Equitable valuation of data for machine learning. In: International Conference on Machine Learning. pp. 2242–2251. PMLR (2019)
  * [5] Hanawa, K., Yokoi, S., Hara, S., Inui, K.: Evaluation of similarity-based explanations. In: International Conference on Learning Representations (2021), https://openreview.net/forum?id=9uvhpyQwzM_
  * [6] Ilyas, A., Park, S.M., Engstrom, L., Leclerc, G., Madry, A.: Datamodels: Understanding predictions with data and data with predictions. In: Proceedings of the 39th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 162, pp. 9525–9587. PMLR (17–23 Jul 2022), https://proceedings.mlr.press/v162/ilyas22a.html
  * [7] Koh, P.W., Liang, P.: Understanding black-box predictions via influence functions. In: Proceedings of the 34th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 70, pp. 1885–1894. PMLR (06–11 Aug 2017), https://proceedings.mlr.press/v70/koh17a.html
  * [8] Kwon, Y., Zou, J.: Beta shapley: a unified and noise-reduced data valuation framework for machine learning (2022)
  * [9] Nauta, M., Trienes, J., Pathak, S., Nguyen, E., Peters, M., Schmitt, Y., Schlötterer, J., van Keulen, M., Seifert, C.: From anecdotal evidence to quantitative evaluation methods: A systematic review on evaluating explainable ai. ACM Comput. Surv. (feb 2023). https://doi.org/10.1145/3583558, https://doi.org/10.1145/3583558
  * [10] Park, S.M., Georgiev, K., Ilyas, A., Leclerc, G., Madry, A.: Trak: attributing model behavior at scale. In: Proceedings of the 40th International Conference on Machine Learning. ICML’23, JMLR.org (2023)


2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, including reprinting/republishing this material for advertising or promotional purposes, collecting new collected works for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Despite recent advances in reinforcement learning (RL), its application in safety critical domains like autonomous vehicles is still challenging.
Although punishing RL agents for risky situations can help to learn safe policies, it may also lead to highly conservative behavior.
In this paper, we propose a distributional RL framework in order to learn adaptive policies that can tune their level of conservativity at run-time based on the desired comfort and utility.
Using a proactive safety verification approach, the proposed framework can guarantee that actions generated from RL are fail-safe according to the worst-case assumptions.
Concurrently, the policy is encouraged to minimize safety interference and generate more comfortable behavior.
We trained and evaluated the proposed approach and baseline policies using a high level simulator with a variety of randomized scenarios including several corner cases which rarely happen in reality but are very crucial.
In light of our experiments, the behavior of policies learned using distributional RL can be adaptive at run-time and robust to the environment uncertainty.
Quantitatively, the learned distributional RL agent drives in average 8 seconds faster than the normal DQN policy and requires 83% less safety interference compared to the rule-based policy with slightly increasing the average crossing time.
We also study sensitivity of the learned policy in environments with higher perception noise  and show that our algorithm learns policies that can still drive reliable when the perception noise is two times higher than the training configuration for automated merging and crossing at occluded intersections.

§ INTRODUCTION

Reinforcement learning (RL) has gained more attention recently in order to solve complex decision making problems in robotics.
Specifically for self-driving vehicles, long term optimal policies are learned using this approach for multiple scenarios such as  lane changing or merging in highways <cit.> or yielding at unsignalized intersections <cit.>.
Benefitting from the high representational power provided by neural networks to learn the future return of each action, learning-based policies can provide optimal behavior which is more generic and scalable compared to POMDP-based approaches like <cit.> and also more intelligent than rule-based approaches <cit.>.

Safety is one of the most important challenges for learning-based policies in critical applications like automated driving.
Although the learned policies are prevented to generate risky behavior during training by receiving big punishments for having collisions <cit.> or being in risky situations <cit.>, there is no guarantee that the learned policy is always safe after training.
Another important challenge for the learning-based policies is to apply them in environments which are more challenging than the training environment due to higher sensor noise in perception or more severe sensor occlusions.
Although one can try to learn a policy which reduces the amount of risk to be still safe in more challenging scenarios like <cit.>, such a policy often is too conservative when the uncertainty is high.
This dilemma between more conservative but slower policies and risky but faster policies is nicely elaborated by Isele et. al in <cit.> where higher timeout punishments as part of the reward function resulted in a faster but more risky policy.
The origin of this problem lies in the difficulty of shaping the reward to guarantee having safe policies in gradient based learning approaches as discussed in <cit.>.

Overview of the merging scenario and the proposed  distributional reinforcement learning framework for automated navigation at similar occluded intersections (background image source: <cit.>).

Another approach to address safety for RL policies is to utilize a safety layer which filters out unsafe actions as proposed in <cit.>.
This safety layer must be easily verifiable without any black boxes such as deep neural networks inside its architecture which are hard to verify <cit.>.
In <cit.> authors used safety constraints in order to prevent unsafe lane changes from a RL agent. As the fail-safe action, the automated vehicle will keep the lane whenever lane change actions are unsafe and in order to prevent unnecessary lane changes, the RL agent will receive punishments for every lane change decision.
In <cit.>, the authors showed that safety verification can also help the RL agent to converge faster in addition to guaranteeing safety. They studied the effect of applying the safety layer before or after the RL agent as preemptive and Post-Posed Shielding mechanisms and also specifying penalties for every safety intervention on the performance of the learned policy.

In the context of automated driving, uncertainties due to perception noise or ambiguous behavior of other participants need to be considered inside the safety verification constraints.
However, there is a trade-off between the level of safety that is guaranteed and efficiency <cit.>.
Assuming that always the worst case perception noise exists and other drivers are all distracted will result in unnecessary safety interruptions which actually prevent the RL agent to utilize its learning skills.
On the other hand, one can increase the capability of intervention (e.g. deceleration with -10 $m/s^2$) and only prevent unsafe actions just before a hazardous event is going to happen which will result in rare interventions but with uncomfortable feelings for the passengers.

Our contribution is to address safety, scalability and comfort as the main intertwined challenges for automated driving under uncertainty.
We introduce safe distributional RL which considers maximum uncertainty and capability inside  safety verification layer.
During training the RL agent is punished for every safety intervention similar to <cit.>.
However, the main difference is it learns distributions instead of expected values for each action return which helps to provide risk-aware policies that are able to adapt their conservativity according to the existing uncertainty in the environment.
This feature makes the learned policy generic and applicable for  high uncertainty levels that can rarely happen in realistic applications, for example when the sensor range is severely occluded due to a parked vehicle or it has high uncertainty.

After explaining preliminaries of our work in section <ref>, we describe the proposed worst-case based safety verification layer in section <ref> and the safe distributional RL framework in section <ref>. Finally, efficiency of the proposed method is compared with a regular RL and a rule-based agent as baseline policies in section <ref>.

§ PRELIMINARIES

§.§ Reinforcement Learning

Reinforcement learning problems are typically formulated as a
Markov Decision Process (MDP)
$(\S, \A, \tm, \rm, \gamma)$ <cit.>.
In this framework, the environment is described by a state
and the agent chooses an action
at each discrete time step $t$.
The action selection process is described by a policy $\pi$ which is a mapping from states to actions
(or to distributions over actions).
The distribution of the successor state $s_{t+1}$ is defined by the transition model
$s_{t+1}\sim\tm(s_t,a_t)$ based on the current state and chosen action.
In every step the agent receives a reward
$r_t=\rm(s_t,a_t)$ and
its goal is to maximize the cumulative discounted reward (also called return)
$\sum_{t=0}^{\infty} \gamma^t r_t$,
where future rewards are discounted by the factor
$\gamma \in [0,1)$.

In many real-world applications the agent does not have full knowledge of the environment's state
but instead receives only noisy observations of some state variables.
Such situations can be described by a
Partially Observable Markov Decision Process (POMDP)
$(\S, \A, \O, \tm, \om, \rm, \gamma)$,
where the agent receives an observation
$o_t \in \O$
at each time step.
The observation depends on the current state and chosen action and is distributed according to the observation model
$o_t \sim \om(s_t, a_t)$.
The agent's goal is still to maximize the return but with the additional challenge of an unknown environment state.
Since each observations contains only limited information on the true environment state, policies for a POMDP therefore also depend on previous actions and observations.

A famous approach to find the optimal RL policy is $Q$-learning
<cit.> which tries to maximize the expected future return defined as:

\begin{equation*}
\label{eq:q}
Q^\pi(s_t,a_t) = \mathbb{E}_{s_i\sim\tm}\left[ \rm(s_t,a_t) + \sum_{k=1}^\infty \gamma^{k} \rm(s_{t+k}, \pi(s_{t+k})) \right],
\end{equation*}

by choosing action $a_t$ in state $s_t$ and following policy $\pi$ for the next states <cit.>.
Using the Bellman equation <cit.>, the optimal value function can be represented as:

\begin{equation*}
Q^*(s_t,a_t) = \mathbb{E}_{s_i\sim\tm}\left[ \rm(s_t,a_t) + \gamma \max_{a^\prime} Q^*(s_{t+1}, a^\prime)) \right].
\end{equation*}

In Deep Q networks (DQN) <cit.>, deep neural networks are utilized to learn the Q values for each state and action over samples from a replay buffer.
We use DQN as one of baselines in our experiments.

§.§ Distributional Reinforcement Learning

Distributional Reinforcement Learning <cit.> tries to learn return distribution $Z^\pi(s_t,a_t) \distEq R(s_t,a_t) + \sum_{k=1}^\infty \gamma^{k} \rm(s_{t+k}, \pi(s_{t+k}))$ instead of its expected value.
Note that here $\distEq$ indicates equality in distribution.
The value distribution can be computed using dynamic programming based on the distributional Bellmann equation <cit.> :

\begin{equation}
Z^\pi(s,a) \distEq R(s,a) + \gamma Z^\pi(S^\prime,A^\prime),
\end{equation}

where $S^\prime$ and $A^\prime$ are distributed according to $\tm(.|s, a)$ and $\pi(.|s^\prime)$, respectively.
This equation is shown in <cit.> to be a contraction in the Wasserstein metric.

Similar to the regular RL, the Distributional Bellman optimality equation is applied:

\begin{equation*}
\belo Z(s,a) \distEq R(s,a) + \gamma Z(S^\prime,\arg\max_{a^\prime\in\A}\mathbb{E}Z(S^\prime,a^\prime)),
\end{equation*}

with $S^\prime$  distributed according to $\tm(\,\cdot\,|s, a)$.
In order to learn the optimal return distribution, Bellemare et al. parameterized it as a categorical distributions over a fixed set of equidistant points <cit.>.
Their approach, called C51, minimizes the Kullback-Leibler divergence to the distributional Bellman targets, which, however, was not a contraction in the Wasserstein metric.
Later Dabney et al. proposed to learn return distributions through Quantile Regression (QR-DQN) on a fixed set of quantiles, minimizing the Wasserstein distance to the distributional Bellman targets <cit.>.
In a newer approach,  Dabney et al. introduced Implicit Quantile Networks (IQN) <cit.> to approximate the quantile function $F^{-1}_Z(\tau)$ for the random
variable $Z$.
Assuming $\tau \sim U(\left[0, 1\right])$, the return distribution can then be sampled from $F^{-1}_Z(\tau)$ as samples from implicitly defined return distribution.
The main advantage of IQN is that any distortion risk measure $\beta:\left[0, 1\right] \to \left[0, 1\right]$ can be incorporated to compute distorted expectation of $Z$:

\begin{equation*}
Q_\beta(s_t, a_t)= \mathbb{E}_{\tau \sim U(\left[0, 1\right])} \left[ Z_{\beta(\tau)}(s_t, a_t)\right],
\end{equation*}

and the risk-sensitive greedy policy:

\begin{equation*}
\pi_\beta(s_t) = \arg\max_{a\in\A}Q_\beta(s_t, a).
\end{equation*}

In this paper we utilize IQN implementation of distributional RL since it allows to explore risk-sensitive policies $\pi_\beta$ during training which helps us to learn a family of risk-averse policies using only one neural network.

Proposed Deep sets architecture for extracting permutation invariant and scalable features for the distributional RL network.

§.§ Observation and State Model

As proposed in <cit.>, we can represent the whole situation at an occluded intersection using this matrix:

\begin{equation}
o_t = \begin{tikzpicture}[baseline, decoration=brace]
\matrix (m) [matrix of math nodes,left delimiter=[,right delimiter={]^T}] {
d_{\textrm{e},\textrm{stl}} & d_{1} & ... & d_{n} & d_{o_1} & ... & d_{o_m}  \\
v_{\textrm{e}} & v_1 &  ... & v_n & v_{o_1} & ... & v_{o_m}  \\
d_{\textrm{e},\textrm{goal}} & d_{\textrm{e},1} & ... & d_{\textrm{e},n} & d_{\textrm{e},o_1} & ... & d_{\textrm{e},o_m} \\
\draw[decorate,transform canvas={yshift=0.5em},thick] (m-1-1.north west) -- node[above=2pt] {$ego$} (m-1-1.north east);
\draw[decorate,transform canvas={yshift=0.5em},thick] (m-1-2.north west) -- node[above=2pt] {$vehicles$} (m-1-4.north east);
\draw[decorate,transform canvas={yshift=0.5em},thick] (m-1-5.north west) -- node[above=2pt] {$lanes$} (m-1-7.north east);
\end{tikzpicture}
\label{eq:observation}
\end{equation}

where $v_{\textrm{e}}$ is the ego vehicle velocity and $d_{\textrm{e},\textrm{stl}}$, $d_{\textrm{e},\textrm{goal}}$ are its distance to the stop line and to the other side of the intersection.
$d_i, v_i$ are distance and velocity of every observable vehicle to their conflict zones and $d_{o_i}, v_{o_i}$ are information for ghost vehicles indicating maximum visible distance and allowed velocity on every intersecting lane.
Finally, $d_{\textrm{e},i}$ ($d_{\textrm{e},o_i}$) represents the distance of the ego vehicle to every (ghost) vehicle.
We extend this representation for merging scenarios where we also observe the distance and velocity of the closest front vehicle on the ego vehicle lane.

Finally, we provide a $k$-Markov approximation <cit.> of the POMDP as input to the RL agent in order to enable $Q$-learning similar to <cit.>:

\begin{equation}
s_t =
\begin{bmatrix}
o_t & o_{t-1} & ... & o_{t- (k-1)}
\end{bmatrix}
\end{equation}

In this way the neural network and its training process become less complex compared to other implementations for POMDPs like <cit.> which utilize Long Short-Term Memory (LSTM) cells <cit.> to incorporate past information.
In our experiments we supplied the last $k=5$ observations to the network.
Note that the direction of vehicles is specified by their velocity sign and their intention can be estimated from states history.
Other traffic participants can also be added into this model like pedestrians or cyclist in order to provide more generic model.
This representation is more efficient compared to the grid-based representations used in <cit.> which require deep convolutional layers to extract useful features which are sensitive to the roads topology and irrelevant traffic participants.

§.§ Scalable Reinforcement Learning

The dimension of the state representation can exponentially grow for complex scenarios when the number of vehicles $n$ or intersecting lanes $m$ increase.
Another challenge here is that permutation of input elements can change which may cause the network to have different reactions for the same scenario with different input permutations <cit.>.

In order to address this problem, we use Deep sets  <cit.> architectures that decouple the network size of machine learning algorithms from the number of input elements.
Deep sets approach has already been applied to learn a lane change policy with DQN for highway scenarios in <cit.>.
In this paper, we propose a Deep sets architecture for automated navigation at occluded merging and crossing scenarios (Figure <ref>).
A representation is calculated for each type of the input element (real vehicle or ghost vehicles) with the $\phi_{real}$ and $\phi_{ghost}$ networks.
After that, all features for each element type are combined with a permutation invariant operator, which we used sum of them.
Finally, $\rho_{real}$ and $\rho_{ghost}$ networks extract fixed size features from the combination of each type of the input element with  the ego vehicle state.

§ PROACTIVE SAFETY VERIFICATION

In order to verify safety, we propose a proactive safety verification approach which provides safe actions for every state $s\in \S$.
We call it proactive while the worst-case scenario is always considered to  prevent being in an unsafe state in the future.

§.§ Worst-Case Scenarios for Proactive Safety Verification

We define a set of worst-case scenarios  $\mathcal{H}$ that can happen during automated driving at intersections:

* On the intersecting lane $l_i$, an occluded vehicle is driving with velocity $v_{\text{max}}$ at the closest occluded distance to the conflict zone.

* On the intersecting lane $l_i$, an observed vehicle has an estimation error of $3\sigma_\text{d}$ and $3\sigma_\text{v}$ for its distance and velocity and accelerates with $a_{\text{max}}$  to reach velocity of $v_{\text{max}}$.

* On the ego lane $l_{ego}$, an observed vehicle in front of the ego vehicle has an estimation error of $3\sigma_\text{d}$ and  $3\sigma_\text{v}$ for its distance and velocity and  decelerates with $a_{\text{min}}$  to reach zero velocity.

By assumptions in $\mathcal{H}$ we over-approximate the state of an occluded vehicle at intersecting lanes similar to <cit.> and for detected vehicles as well.
In addition to <cit.>, we over-approximate vehicles distance and velocity estimation error as $\mathcal{N}_a^t(\mu,\sigma_\text{d}^{2})$ and $\mathcal{N}_a^t(\mu,\sigma_\text{v}^{2})$ respectively which are denoted as truncated Gaussian distribution with support
$[\mu - a\sigma, \mu + a\sigma]$.
Therefore, the distance and velocity measurement errors are modeled with truncated Gaussian distributions
$\mathcal{N}_3^t(d,\sigma_\text{d}^{2})$ and $\mathcal{N}_3^t(v,\sigma_\text{v}^{2})$, respectively,
i.e. with a $3\sigma$ range around the true value.

§.§ Feasibility of Emergency Maneuvers for Safety Verification

For every intersecting lane $l_i$ and also the ego vehicle lane $l_{ego}$ inside the current state $s$, feasibility of executing one of the following two emergency maneuvers is evaluated to verify the state $s$ as a proactive safe state (PSS) according to the worst-case assumptions  $\mathcal{H}$:

* Emergency Stop  Maneuver: Ego vehicle is able to stop at a distance $d_\mathrm{FS}$ bigger than $SG_d$ before the conflict zone.

* Emergency Leave Maneuver: Ego vehicle is able to leave the intersection with a time headway $t_\mathrm{HW}$ bigger than $SG_t$.

Thus, PSS verification can be formulated as:

\begin{equation}\label{eq:PSS}
\text{PSS}(s)=
\left(\bigwedge\limits_{l_i \in s} d_\mathrm{FS}>SG_d \right)  \bigvee
\left(\bigwedge\limits_{l_i \in s} t_\mathrm{HW}>SG_t \right),
\end{equation}

with $SG_d$ and $SG_t$ the minimum safety gap required for stop and leave maneuvers.

Note that here we validate safety according to all worst case assumptions in $\mathcal{H}$, i.e. if only one of them or all of them happens the situation should remain safe.
We set $SG_d=SG_t=0.5$ in our experiments which resulted in collision free maneuvers during training and evaluation of all policies.

§.§ Proactive Safety Verification of Actions in POMDP

We assume an agent selects action $a\in\A$ for an observation $o\in\O$ from our POMDP model.
In order to verify safety of $a$, we need to make sure that  it results in a proactive safe state even if the worst-case scenario happens.
Therefore, we simulate the future state of the ego vehicle by executing $a$ and the state of other vehicles with the worst-case assumptions in $\mathcal{H}$ until the next decision time.
We call this simulated state as $\hat{s}_{\mathcal{H},o}^a$.
If $\hat{s}_{\mathcal{H},o}^a$ is a PSS, then action $a\in\A$ is verified as a proactive safe action (PSA):

\begin{equation}\label{eq:PSA}
\text{PSA}(s, a)=
\begin{cases}
\text{True}, & \text{if}\ \text{PSS}(\hat{s}_{\mathcal{H},o}^a), \\
\text{False}, & \text{otherwise}.
\end{cases}
\end{equation}

The main advantage of the proposed worst-case proactive safety verification compared to reachability-based <cit.> and prediction-based approaches <cit.> for safety is that it only needs to predict the whole situation for one time step and only for the worst-case scenarios defined in $\mathcal{H}$ instead of all possible maneuvers for all participants in the whole future horizon.
Since for each intersecting lane, the proposed safety verification approach only considers the closest vehicle to the conflict zone, it has computation complexity of $O(m+1)$ where $m$ is the number of intersecting lanes in the scenario.
This complexity is much smaller than the safety verification strategy proposed in <cit.> which has complexity of $O(nT)$ where $n>>m$ is the number of agents and $T$ is the time horizon considered for safety verification in that approach.

§ LEARNING SAFE AND COMFORTABLE POLICIES FOR AUTOMATED DRIVING UNDER UNCERTAINTY

Similar to <cit.>, we propose to apply safety as a hard constraint in the decision making problem trying to minimize other costs such as utility  or comfort as soft constraints.
For that, we can use the PSS concept in order to find all safe actions among the set of available actions in $\A$ as $\A_\text{PSA}$:

\begin{equation}
\A_\text{PSA}(s) = \{a\in\A | \text{PSA}(s,a)=\text{True}\},
\end{equation}

and search for the safe action with the lowest cost regarding comfort and utility.
Here we consider actions as jerk commands applied to the automated vehicle similar to <cit.> which help to provide comfortable maneuvers by moderating jerk.
Therefore, we set possible discrete actions as
$\A=\{-1.5\frac{m}{s^3}, 0.0\frac{m}{s^3}, 1.5\frac{m}{s^3} \}$.

§.§ Safe Rule-based Policy

We implemented a rule-based policy which selects the fastest safe action from $\A$ and in case of emergency selects an emergency action with the lowest jerk.
The maximum emergency jerk limit can be increased which result in higher utility in cost of less comfortable drivings due to higher average jerk (Figure <ref>).
On the other hand, when emergency jerk limit is reduced, the policy becomes slower, more comfortable and more conservative, since emergency maneuvers are limited.

[xlabel=Emergency jerk limit [$\frac{\text{m}}{\text{s}^3}$], xmajorgrids=true,ymin=8,ymax=,xmax=7.05,xmin=1,
ylabel=Avg. crossing time [s] ,	width=0.70,
axis y line*=left]
[mark=o,color=rgb:red,88;green,117;blue,164,line width=0.9pt] coordinates
(1.0, 15.1)
(2.0, 14.2)
(3, 11.3)
(4, 10.)
(5, 9.1)
(6, 9.3)
(7, 8.4)

[xlabel=Emergency jerk limit,ymin=0.5,ymax=2.5,xmax=7.05,xmin=1,ylabel=Avg. jerk [$\frac{\text{m}}{\text{s}^3}$] ,	width=0.70,
axis y line*=right, axis x line=none]
/pgfplots/refstyle=plot_oneAvg. crossing time

[mark=+,color=rgb:red,181;green,93;blue,96,line width=0.9pt] coordinates
(1.0, 0.62)
(2.0, 0.88)
(3, 1.18)
(4, 1.55)
(5, 1.78)
(6, 1.85)
(7, 1.92)
Avg. jerk

Effect of increasing the jerk limit on the average crossing time and average jerk for the proactive safe policy.

§.§ Minimizing Safety Interference with Reinforcement Learning

RL, thanks to its ability to provide long-term optimal actions, can trade-off between utility and comfort based on the preferences defined in its reward function:

\begin{equation}
\rm(o, a)=
\begin{cases}
$ 1$, & \text{if reach goal} \\
-\lambda, & \text{if}\ a \not\in {A}_{\text{PSA}}(o) \\
$ 0$, & \text{otherwise}
\end{cases}
\label{eq:reward}
\end{equation}

By such reward function, safety interventions are discouraged preventing situations that an uncomfortable emergency action with higher jerk instead of the unsafe RL action needs to be executed.
The proposed framework has two main differences compared to other safe RL frameworks like <cit.>.
First, the emergency action is not necessarily a member of $A_\text{RL}$, therefore the training episode is terminated when a safety interference is required and the RL unsafe action will not be replaced in the replay buffer.

Secondly, the agent receives a big punishment of $-\lambda$ whenever its action is not a member of $A_{\text{PSA}}$  which is also not necessarily suggested in <cit.> and not used in <cit.> for safety interference.

One challenge here is choosing the safety interference punishment $\lambda$.
Lazarus et. al. in <cit.> applied similar rewarding scheme for an autopilot system of the aircraft which punished the RL agent whenever the emergency controller had to be deployed.
They showed choosing higher values for $\lambda$ will encourage more conservative behavior, whereas faster policies with more interruptions can be expected for lower values of $\lambda$.

One may try to find the best value for $\lambda$, however, the learned policy generates proper behavior only for  environments that have similar state transition probabilities to the training environment $\tm$.

Moreover, due to the safety verification punishments which consider worst-case assumptions, RL either learns a super conservative policy or a fast policy with too many safety interventions.
In our experiments, we learned a balanced policy by DQN with $\lambda=1$ as a normal RL baseline.

§.§ Risk-aware Policies with Distributional Reinforcement Learning

The main problem with applying normal RL in environments under uncertainty is its risk-neutral characteristic that can not distinguish the amount of variance in actions' return and only considers their expected values.
Therefore, one risky action with negative tail in its return but higher total expected value is always preferred to a safer (lower variance) action.
For that, Tang et al. modeled the return for each action as a normal distribution and optimized an RL policy by learning the return distribution parameters ($\mu$,$\sigma$) <cit.>.
However, we believe that the return is a multimodal distribution and therefore we applied Implicit Quantile Networks (IQN) implementation <cit.> which approximates the quantile function that implicitly defines the return distribution.
Moreover, utilizing the return distribution also allows to expand risk-neutral policies to risk-sensitive policies by applying distortion risk measures like the Conditional Value-at-Risk (CVaR) <cit.>:

\begin{equation}
\text{CVaR}_{\alpha} = \mathbb{E} \left[ Z^{\pi} | Z^{\pi} \leq F^{-1}_{Z^{\pi}}(\alpha) \right],
\end{equation}

where $Z^{\pi}$ is the sum of discounted rewards under policy $\pi$ and $F^{-1}_{Z^{\pi}}(\alpha)$ is its quantile function at $\alpha\in\left[0, 1\right]$.

Therefore, we train an IQN agent with same reward function as DQN (Equation <ref> with $\lambda=1$ ) and tune the the risk-sensitivity of the policy using $\alpha$ at execution time without requiring to train multiple policies for different risk levels.
In order to leverage the whole solution space over different risk-sensitive policies, $\alpha$ is uniformly sampled with $\alpha \sim U(0,1)$ at the beginning of each episode during training and applied to the IQN results (Figure <ref>).

§ RESULTS AND EVALUATIONS

Comparing performance of each policy on benchmark scenarios.
Left: Average crossing time for each policy. IQN becomes faster and less conservative by higher $\alpha$. Rule-based is the fastest and DQN is the slowest policy. Note that all policies are completely safe without any collision thanks to the safety layer.
Middle: Average of vehicle absolute jerk and its confidence interval for each policy. By increasing $\alpha$, IQN becomes less conservative (higher jerk).
Right: Distribution of vehicle jerk while driving by each policy. Green interval shows RL jerk limits. Jerk values out of this interval are due to emergency interference and indicate uncomfortable driving.

Left: Learned return distributions for two scenarios with similar initial situation. Ego vehicle (red) follows the action with the highest CVaR that is shown with filled distribution.
Gray ghost vehicle indicates maximum visible distance limited due to orange obstacles.
Middle: Black vehicle is non-cooperative causing more negative return chance for the accelerate action.
Right: Black vehicle is cooperative causing higher CVaR for accelerate action.

§.§ Simulation and Policy Training

We train and evaluate different RL policies for automated merging and crossing at occluded intersections using our high level simulator which can simulate different randomized scenarios.
Figure <ref> shows an example scenario generated by our simulator.
The location and size of obstacles (orange boxes) are generated randomly for each training episode causing some vehicles invisible for the ego vehicle.
In order to generate realistic scenarios, every vehicle in the simulator (except the ego vehicle) has a random desired velocity selected by normal distribution with a randomly selected $\mu$={6, 9, 12} and $\sigma$={2, 4, 6}.
Each vehicle drives with the Intelligent Driver Model <cit.> controller with maximum acceleration  $1\mpsq$, minimum deceleration $10\mpsq$ and comfortable deceleration $1.6\mpsq$ and keeps safety distance $2 \text{m}$ and time headway $1.6$s with front vehicles.
However, the controller does not keep distance to the ego vehicle (when it drives into the intersection), thus a collision between a vehicle and the ego vehicle is possible.

At every step a new vehicle by probability of $p_{\text{new}}$={0.1, 0.4 or 0.7} is generated in the simulator.
Vehicles are with probability $p_{\text{coop}}$={0.1, 0.4 or 0.7} cooperative and yield to the ego vehicle by setting their desired velocity to zero when the ego vehicle is close to the intersection which helps to simulate uncertainty about the intention of other drivers.
Moreover, distance and velocity of vehicles are perturbed to simulate perception noise for the policy according to the truncated Gaussian distributions
respectively, where $\sigma_d=1\text{m}$ and $\sigma_v=2\mps$ were fixed during training.
$\sigma_d$ and  $\sigma_v$ are linearly scaled according to the distance between the ego and other vehicle.
For the ego vehicle, the RL policy generates a discrete jerk action from $\A=\{-1.5\mpsc, 0.0\mpsc, 1.5\mpsc \}$ every $0.3$ second.
RL policies are trained with more than 1000 intersection crossing and merging scenarios providing more than $3\times 10^5$ training steps in total.
Distributional RL policies have been trained with uniformly selected $\alpha \sim U([0,1])$ for CVaR calculation of the return distributions.

§.§ Evaluations

After training the RL agents, we evaluate their efficiency using 30 benchmark scenarios with random uncertainty configurations $\sigma_d\in\{0,1m,2m\}$, $\sigma_v=2\sigma_d$ and $p_\text{coop}$={0.1, 0.4 or 0.7}.
Note that, no collision with other vehicles happens during evaluations thanks to the safety verification layer.
In case of an emergency situation, i.e. $a_\text{RL} \notin A_{\text{PSA}}$, an emergency maneuver from the safety layer with maximum emergency jerk limit of $5\mpsc$ is sent to the controller instead of the unsafe RL action.
In order to compare the effect of interference applied for each policy, we define a metric for measuring the amount of applied emergency interference:

\begin{equation}
J_\text{Interference} = \frac{\sum a_\text{emg}^2}{N},
\end{equation}

where $a_\text{emg}$ is the emergency jerk command applied to replace the unsafe action and $N$ is the total number of evaluation episodes.

§.§.§ Drivers Intention Prediction

Since RL policies receive history of last 5 observations as their input state, they can predict the intention of other drivers and generate optimal actions based on that.
Figure <ref> shows examples of the learned return distributions by IQN agent for two similar scenarios with the only difference of having cooperative (yielding to the ego vehicle) and non-cooperative drivers.
As it is visible, when the other vehicle is cooperative and reduces its velocity, the IQN policy generates higher return for $a=1.5\mpsc$ action allowing the ego vehicle to enter into the intersection.

Evaluation of the IQN policies with best $\alpha$ for different metrics and their comparison with baselines for different environment configurations.

2l|Environment Configuration
2l|$\sigma_d = 0$ $p_\text{coop} = 0.3$
2l|$\sigma_d=2$ $p_\text{coop} = 0.3$
2l$\sigma_d=2$ $p_\text{coop} = 0.7$
Policy                           Metric for optimal $\alpha$        Time              $J_\text{Interference}$           Time            $J_\text{Interference}$             Time              $J_\text{Interference}$
Speed         9.80         25.03              8.80        43.09        9.94              33.25

Comfort       11.73        10.00     11.08       25.50        12.16            18.83

DQN     —–     20.00                10.79      21.40        14.17           21.25              20.10

Rule-based     —–     7.69        83.59      7.75         92.29        7.74     103.05

§.§.§ Comfort and Risk Sensitivity

Figure <ref> compares the utility and conservativity of each RL policy compared with the safe rule-based policy.
By increasing the $\alpha$ percentile, IQN policy becomes faster but less conservative in average.
For lower $\alpha$ percentile, it has less absolute jerk (in the middle image) and lower jerks outside the RL jerk limit (in the right image) which indicates more comfortable maneuvers.
DQN, shows the most conservative behavior with the highest crossing time.

On the other hand, the rule-based policy has the highest amount of emergency interference as a risk neutral policy resulting in wider jerk distributions and showing uncomfortable maneuvers.
Therefore, we can conclude that IQN can learn a family of adaptive policies which are not as highly conservative as DQN and also not as risk-neutral as the rule-based policy.

Safety interference cost applied to the IQN policy for different environment noise levels and its comparison with baselines.

Same results can be concluded from Table <ref> where we recorded the average crossing time and $J_\text{Interference}$ for all policies at different environment configurations.
Here we only consider two IQN sub-policies, the ones with the fastest behavior and with the lowest interference cost (most comfortable).
We evaluated the policy in 10 uniform samples of $\alpha$ and selected the best policy according to each metric.
Note that finding the best $\alpha$ value could be done in a more automated approach but here we only wanted to compare the best behavior of the Deepset-IQN agent with other baseline agents and examine how much other metrics are sacrificed when the policy performs well in specific metric.
In all three configurations considered in Table <ref>, the rule-based policy is the fastest one, however, it is also the worst policy in terms of comfort.
The DQN, on the other hand, always has low interference cost, but drives more than two times slower than the others.
The IQN trades of between average crossing time and interference cost by showing relatively fast behavior which requires 3.6 to 8 times lower interference than the rule-based policy depending on the environment configuration.

§.§.§ Evaluation under Higher Perception Uncertainties

In addition to the initial noise levels, we studied the sensitivity of each policy to higher amounts of noise in the environment.
For that, we evaluated the RL and rule-based policies for 5 different noise levels $\sigma_d\in\{0,1,2,3,4,5\}$ (in meters) and $\sigma_v=2\sigma_d$ (in $\mps$).
The results are depicted in Figure <ref>.
As it is visible, the IQN policy has lower interference cost for lower $\alpha$ and also lower noise levels.
For higher noise levels, it requires more interference which can be reduced by decreasing CVaR $\alpha$.
The rule-based policy always has high cost and DQN has low cost independent of the amount of noise existed in the environment.
Here DQN seems to be a comfortable policy, however it is the worst policy in case of utility as discussed before.

§ CONCLUSIONS AND FUTURE WORK

We proposed a proactive safety verification approach to validate the safety of actions with the goal of preventing unsafe situations in critical applications like automated driving.
In order to minimize uncomfortable safety interference, we used reinforcement learning to learn policies that are punished for resulting in states where an emergency maneuver is necessary.
We showed how IQN agent can mitigate the conservative behavior existing in DQN policies by learning return distributions which provide policies that can be tuned adaptively after training in order to become more comfortable or less conservative.
According to our experiments, the learned distributional policy requires less safety interference in noisy environments comparing to a rule-based safe policy even when the noise level is higher than the training configurations.

For future works, one can propose a better conservativity tuning approach in order to learn policies that automatically tune their risk sensitivity ($\alpha$ for the IQN policy) at runtime based on the observed uncertainty or the required risk sensitivity in the environment.

§ ACKNOWLEDGMENT

This research is accomplished within the project “UNICARagil” (FKZ 6EMO0287).
We acknowledge the financial support for the project by the Federal Ministry of Education and Research of Germany (BMBF).

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

decision making;knowledge based systems;learning (artificial
intelligence);road safety;road vehicles;reasonable autonomous lane
changing;machine learning techniques;rule-based systems;autonomous
vehicles;unsafe actions;slow learning rates;reinforcement learning-based
approach;formal safety verification;safe actions;deep reinforcement learning
agent;RL agent;rule-based agent;high-level decision-making;minimal state
representation;DQN;Deep Q-Network;Decision making;Safety;Road
transportation;Autonomous vehicles;Task analysis
booktitle2018 21st International Conference on Intelligent
Transportation Systems (ITSC)
titleHigh-level Decision Making for Safe and Reasonable Autonomous
Lane Changing using Reinforcement Learning

* Invalid format of field 'month'

titleSafe, multi-agent, reinforcement learning for autonomous
journaltitlearXiv preprint arXiv:1610.03295

booktitleConference on Robot Learning
titleWorst Cases Policy Gradients

learning systems;mobile robots;navigation;path planning;road
vehicles;autonomous vehicles;unsignaled intersections;Deep RL;intersection
handling problem;deep reinforcement learning system;occluded
intersections;active sensing behaviors;Autonomous
vehicles;Automobiles;Machine learning;Safety;Navigation;Learning (artificial
booktitle2018 IEEE International Conference on Robotics and
Automation (ICRA)
titleNavigating Occluded Intersections with Autonomous Vehicles
Using Deep Reinforcement Learning

* Invalid format of field 'month'

titleLearning Negotiating Behavior Between Cars in Intersections
using Deep Q-Learning
journaltitle2018 21st International Conference on Intelligent
Transportation Systems (ITSC)

learning (artificial intelligence);remotely operated vehicles;road
traffic control;road vehicles;intersection handling behaviors;autonomous
vehicle;safety critical applications;learning process;safe reinforcement
learning;Safety;Autonomous vehicles;Trajectory;Games;Pipelines;Noise
booktitle2018 IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS)
titleSafe Reinforcement Learning on Autonomous Vehicles

* Invalid format of field 'month'

booktitle2019 IEEE Intelligent Vehicles Symposium (IV)
titleSafe reinforcement learning with scene decomposition for
navigating complex urban environments

titleRisk-Aware High-level Decisions for Automated Driving at
Occluded Intersections with Reinforcement Learning
journaltitlearXiv preprint arXiv:2004.04450

booktitle2019 IEEE Intelligent Vehicles Symposium (IV)
titleA POMDP Maneuver Planner For Occlusions in Urban Scenarios

titleTIME-TO-COLLISION AND COLLISION AVOIDANCE SYSTEMS

family=Thao Dang,

125 years after Bertha Benz completed the first overland journey in
automotive history, the Mercedes Benz S-Class S 500 INTELLIGENT DRIVE
followed the same route from Mannheim to Pforzheim, Germany, in fully
autonomous manner. The autonomous vehicle was equipped with
close-to-production sensor hardware and relied solely on vision and radar
sensors in combination with accurate digital maps to obtain a comprehensive
understanding of complex traffic situations. The historic Bertha Benz
Memorial Route is particularly challenging for autonomous driving. The course
taken by the autonomous vehicle had a length of 103 km and covered rural
roads, 23 small villages and major cities (e.g. downtown Mannheim and
Heidelberg). The route posed a large variety of difficult traffic scenarios
including intersections with and without traffic lights, roundabouts, and
narrow passages with oncoming traffic. This paper gives an overview of the
autonomous vehicle and presents details on vision and radar-based perception,
digital road maps and video-based self-localization, as well as motion
planning in complex urban scenarios.

titleMaking Bertha Drive—An Autonomous Journey on a Historic
journaltitleIEEE Intelligent Transportation Systems Magazine

titleGoogle maps, by Google.

titleSafe reinforcement learning via shielding
journaltitlearXiv preprint arXiv:1708.08611

booktitle2020 AIAA/IEEE 39th Digital Avionics Systems Conference
titleRuntime Safety Assurance Using Reinforcement Learning

titleAlgorithms for verifying deep neural networks
journaltitlearXiv preprint arXiv:1903.06758

titleUsing simplicity to control complexity
journaltitleIEEE Software

John Wiley

titleDynamic programming and markov processes.

given=Christopher J CH,

Q-learning (Watkins, 1989) is a simple way for agents to learn how to act
optimally in controlled Markovian domains. It amounts to an incremental
method for dynamic programming which imposes limited computational demands.
It works by successively improving its evaluations of the quality of
particular actions at particular states.

journaltitleMachine Learning

The MIT Press

shorttitleReinforcement Learning
titleReinforcement Learning: An Introduction

American Association for the Advancement of Science

titleDynamic programming

titlePlaying Atari with Deep Reinforcement Learning

booktitleInternational Conference on Machine Learning
titleA distributional perspective on reinforcement learning

booktitleProceedings of the AAAI Conference on Artificial
titleDistributional reinforcement learning with quantile

booktitleInternational Conference on Machine Learning
titleImplicit Quantile Networks for Distributional Reinforcement

booktitleProceedings of the 17th International Conference on
Autonomous Agents and MultiAgent Systems
titleUtility decomposition with deep corrections for scalable
planning under uncertainty

titleLong Short-Term Memory
journaltitleNeural Computation

booktitle2019 European Conference on Mobile Robots (ECMR)
titleLearning Path Tracking for Real Car-like Mobile Robots From

booktitle2019 IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS)
titleDynamic Input for Deep Reinforcement Learning in Autonomous

booktitleAdvances in neural information processing systems
titleDeep sets

booktitle2018 21st International Conference on Intelligent
Transportation Systems (ITSC)
titleTackling occlusions & limited sensor range with set-based
safety verification

titleOnline verification of automated road vehicles using
reachability analysis
journaltitleIEEE Transactions on Robotics

booktitle2010 IEEE International Conference on Robotics and
titleOptimal trajectory generation for dynamic street scenarios in
a frenet frame

booktitle2019 IEEE Intelligent Transportation Systems Conference
titleA risk and comfort optimizing motion planning scheme for
merging scenarios

titleOptimization of conditional value-at-risk
journaltitleJournal of risk

titleCongested traffic states in empirical observations and
microscopic simulations
journaltitlePhysical review E