Fail-Safe Adversarial Generative Imitation Learning
Authors: Philipp Geiger
Christoph-Nikolas Straehle
Venue: Accepted by TMLR ()

Abstract: For flexible yet safe imitation learning (IL), we propose theory and a modular method, with a safety layer that enables a closed-form probability density/gradient of the safe generative continuous policy, end-to-end generative adversarial training, and worst-case safety guarantees. The safety layer maps all actions into a set of safe actions, and uses the change-of-variables formula plus additivity of measures for the density. The set of safe actions is inferred by first checking safety of a finite sample of actions via adversarial reachability analysis of fallback maneuvers, and then concluding on the safety of these actions' neighborhoods using, e.g., Lipschitz continuity. We provide theoretical analysis showing the robustness advantage of using the safety layer already during training (imitation error linear in the horizon) compared to only using it at test time (up to quadratic error). In an experiment on real-world driver interaction data, we empirically demonstrate tractability, safety and imitation performance of our approach.

Published in Transactions on Machine Learning Research (11/2022)
Fail-Safe Adversarial Generative Imitation Learning
Philipp Geiger
Philiip. W. GeigerOde. beetgerdde.bocchh.o com
Bosch Center for Artificial Intelligence Renningen, Germany
Christoph-Nikolas Straehle
Christoph--ikolls. Stw.oolaassstttteeeeeeeeeeeee bosch. com
Bosch Center for Artificial Intelligence
Renningen, Germang
Reviewed on OpenReview: htips: // openreview. net/ formm? id- obBb0b3QqJ
Abstract
For flexible yet safe imitation learning (IL), we propose theory and a modular method, with a safety layer that enables a closed-form probability consity/gradienn of the safe gen- erative continuous policy, end-to-end generative adversarial training, and worst-case safety guarantees. The safety layer maps all actions into set of safe actions, and uses the change- of-variables formula plus additivity of measures for the density. The set of safe actions is inferred by first checking safety of finile sample of actions via adversarial reachability analysis of fallback maneuvers, and then concluding the safety of these actions' neigh- borhoods using, e.g., Lipschitz continuity. We provide theoretical analysis showing the robustness advantage of using the safety layer already during training (imitation error lin- car in the horizon) compared to only using at test time (up quadratic error). In an experiment on real-world driver interaction data, empirically demonstrate tractability, safety and imitation performance of our approach.
1 Introduction and Related Work
For several problems at the current forefront of agent learning algorithms, such as decision making of robots automated vehicles, or modeling/ simulation of realistic agents, imitation learning (IL) is gaining momentum
as a method (Suo et al.
2021 lgl el al. 2022 Bhallacharyya el al., 2019 Bansal el al. 2018 Xu el al.
2020
Zeng et al. 2019
Cao et al. 2020
But safety and robustness IL for such tasks remain challenge.
(Generative) IL The basic idea of imitation learning is as follows: we are given recordings of the sequential behavior of some demonstrator agent, and then we train the imitator agent algorithm on this data to make it behave similarly to the demonstrator (Osa et al. 2018 One powerful recent method generalive adversorial imitotion learning (GAIL) (Ho and Ermon 2016 Song et al.) 2018). GAIL's idea is, on the one hand, to use policy gradient methods borrowed from reinforcement learning (RL; including, implicitly, a form of planning) to generate imitator policy that matches the demonstrator's 's behavior over whole trajectories. And the other hand, to measure the "matching", GAII, uses discriminalor as in generalive adversarial networks (GANs) that seeks to distinguish between demonstrator and imitator distributions. While the noural net and GAN aspects help the ficxibility of the mothod, the RL aspects stir against compounding of errors over rollout horizons, which other IL methods like behavior cloning (BC), which do not have such planning aspects, suffer from. One line of research generalizes classic Gaussian policies more flexible (incl. multi-modal) conditional normalizing flows imitator policies (Ward al.) 2019 Ma et al.) 2020) which nonetheless give exact densities gradients for training via the change- variables formula.
IL's safety/roo /robustness challenges While these are substantial advances in terms of learning flezibil- ily i /ccaccillyy it remains challenge to make the II methods (1) guaranteeably safe, especially for multi-agent

---

Published in Transactions on Machine Learning Research (11/2022)
rollout, using current 0
imitator trajectories (81, di, 82, Ro.
fail-safe generative imitator x r.0 (agl())
closed-form density (āzlox) & gradient
(b) safe set inference
safe action set A
adversarial training step:
(planning)
update discriminator &
(a) pre-safe gen- erative policy (with param. i)
(c) safety layer (constraining to A!")
state
pre-safe action O+
safe action at
souroos NGSIM
8t
transition ā(,
demonstrator trajectories (81, a1, 82, 02.........
Figure 1: Outline of our theoretically grounded method FAGIL: It consists of the fail-safe generotive imitator policy (inner box on I.h.s.,, that takes current state 8t as input, and then (a) lets a standard pre-safe gencrative policy (c.g., Gauss or normalizing flow) generate pre-safe action â,, (b) infers a provably safe set At of actions, and then (c) uses our safely layer constrain the pre-safe action âe inlo Aţ yielding safe action ap. It has end-to-end closed-form density/ censity/grudient,, gradient, we train it end-to-end via, e.g., GAIL (r.h.s.). While our approach is for general safe IL tasks, we take driver imitation as running cemppl/experiments..
interactions with humans, and (2) robust, in the sense of certain generalizations "outside the training distri- bution", e.g., longer simulations than training trajectorics. Both is non-trivial, since safety and long-ton ter-term behavior can heavily be affected already by small learning errors (similar as the compounding error of BC).
Safe control/RL ideas we build on To address this, we build on several ideas from safe control/RL: (1) In reachability analysis/games (Fridovich-Keil and Tomlin 2020 Bansal et al. 2017), the safety prob- lem is formulated as finding controllers that provably keep a dynamical system within pre-defined set of safe/collie aafe/collisoon-free states over some horizon, possibly under adversarial perturbations/ /other agents. (2) Any learning-based policy can be made safe by, at each stage, if it fails to produce safe action, enforcing a sale action given by some sub-optimal but safe fallback controller (given there is such controller) (Wabersich and Zeilinger 2018)). (3) Often it enough search over a reasonably small set of candidates of fallback controllers, such emergency brakes and simple evasive maneuvers in autonomous driving (Pek and Althoff, 2020). And (4) simple way to enforce a policy's output to be safe is by composing it with a safety layer (as final layer) that maps into the safe set, i.e., constrains the action to the safe set, and differentiable such safety layers can even be used during training (Donti et al. 2021a Dalal et al. 2018
While incorporating safety into RL has re- ceived significant attention in recent years (Wabersich and Zeilinger 2018 Berkenkamp et al. 2017 Alshiekh 2018 Chow et al., 2019 Thananjcyan et al., 2021). safcty (in the above sense) in IL, and its theoret- tcal analysis, have received comparably little attention. The existing work on such safe IL can roughly be classified based on whether safety is incorporated via reward augmentation or via constraints/ /safety layers encoded into the policy (there also exists slightly different sense of safe II, with methods that control the probabilistic risk of high imitation costs (Javed et al., 2021 Brown et al. 2020 Lacotte et al. 2019), but they do not consider safety constraints separale from the imitation costs, as we do; for additional, broader related work,, see Appendix D.4b. In reward augmentation, loss terms are added to the imitation loss that penalizes undesired state-action pairs (c.g., collisions) Bhattacharyya et al. 2019 2020 Bansal et al.) 2018 Suo el al., 2021 Zeng et al. 2020 Cheng el al.) 2022). Regarding hard constrains safely layers (Tu el al. 2022 Havens and Hu 2021], one line of research (Chen et al., 2019)) deep IL with safety layers, but only during test time. There little work that uses safety layers during training and test time, with the exception of (Yin et al. 2021 which gives guarantees but is not generative.
Safe II, theoretical guarantees, and their limitations
ct al.
Main contributions and paper structure In this sense we are not aware of general approaches for the problem of safe generative IT. that are (1) safe/robust. with theoretical guarantees and (2) end-to-end
2

---

Published in Transactions on Machine Learning Research (11/2022)
trainable. In this paper, we contribute theory (Sec. B method (Fig. one step towards understanding and addressing these crucial gaps
1 Sec. 4 and experiments (Sec.
5
We propose a simple yet flexible type of differentiable safety layer that maps given "pre-safe" action into given safe action set (i.e., constrains the action). It allows to have closed-form probability density/ density/grudient gradient (Prop. 3 by a non-injective "piecewise" change of variables) of the overall policy, in contrast to common existing differentiable safety layers DDott et al. 2021a Dalal et al. 2018) without such analytic density.
We contribute two cample-based safe set inference approaches, which, for a given state, output a provably safe set of actions- in spite of just chocking safety of a finite sample of actions, using Lipschitz contim- ity /cconvexitty (Prop. and 2 This advances sample-based approaches (Gillula et al. 2014] to overcome limitations of exact but restrictive, e.g., linear dynamics, approaches (Rungger and Tabuada 2017].
A general question is to what extent helps to use the safety layer already during training (as we do), compared to just concatenating it, at test time, to an unsafely trained policy, given the latter may com- putationally be much easier. We icalr quantify the imitation performance advantage of the former over the latter: essentially, the former imitation error scales linearly in the rollout horizon, the latter up to quadratically (Sec. 3.3 rem. [ and thm. D reminiscent of BC. The intuition: only the former method learns how to properly deal (plan) with the safety layer, while in the latter case, the safety layer may lead to unvisited states at test time from which we did not learn to recover. (Generally, proofs are in Appendix A
Combining these results, we propose the method fail-safe generative adversarial imitation learner (FAGIL; Scc. is sketched in Fig. [
In experiments on real-world highway data with multiple interacting driver agents (which also serves as running example throughout the paper), we empirically show tractability and safety of our method, and show that its imitation/
muitation/prediction prediction performance comes close to unconstrained GAIL baselines (Sec. 5).
2 Setting and Problem Formulation
Setting and definitions
We consider a dynamical system consisting of: states 8t E S, at time stages t E 1:7 == {1....,TT: T):
an ego agent that takes action o, E A C RK""" n E N, according to its ego policy ni E II, (for convenience we may drop subscript t); we allow ne be either a conditional (Lebesgue) density, writing a ~ (a)ss), deterministic, writing 0e = =s();;;
the ego agent can be either the demonstrator, denoted by nD (a priori unknown); or the imitator, denoted by N/.0, with 0 its parameters;
other agents, also interpretable as noise/perturbatiinss (a priori unknown), with their (joint) action o according to others' policy ot E Φ /eeesstty/determnnittii analogous to ego);
the system's transition function (environment) f, s.t.,
8141 = f((,, de, 0z).
(1)
(f is formally assumed to be known, but uncertainty can simply be encoded into o;.)
As training data, we are given a set of demonstrator trajectories of the form a1), (82, 02), (ST, ar) of Pss episodic rollouts in an instance of this dynamical system including other agents/noiss noise.
We consider a (momentary) imitation cost function c(s, a) which formalizes the similarity between imitator and demonstrator trajectories (details follow in Sec. 4.2 on the GAlL-based c), and (momentary) safety cost function d(s); states s for which d(s)) S 0 are referred to as momentarily safe or collision-free.
Notation: P(-) denotes probability; and (.).) the probability's density of a variable x, it exists (we may drop subscript z).
Note that our approach works with both, demoustrators that are already fully safe, and those that may be unsafe. 'Regarding the task of realistic
Adding safcty constraints can, in principle, lead unrcalistic biases in case of actually unsafe demonstrations. But the other extreme pure II. where, e.g., collisions rates can be unrealistically high (Bansal et al. 2018). So this is always trade-off
3

---

Published in Transactions on Machine Learning Research (11/2022)
Goal formulation The goal is for the imitator to generate trajectories that minimize the expected imita- tion cost, while satisfying safety cost constraint, formally:
T Σ
π = arg min E
c(se, at) - (b(T)) d(st) S 0, for all 4
(2)
where vT is called total imitation cost function (we drop superscript & it zero), (())) a policy regularizer, and (+) denotes the expectation over roll-outs of π 3 We purportedly stay fairly abstract here. We will later instantiate c, 10 (Sec. 4.2h and d (Sec. 50, and specily our safety-relevanl modeling/ reatooinng
about the other agents/ agents/perturbatte perturbations Sec. 3.1
3 General Theoretical Tools for Policy and Training of Safe Generative Imitation Learning
We start by providing, in this section, several general-purpose theoretical foundations for safe generative IL, as tools to help the design of the safe imitator policy (Sec. 3.1 and 3.2), as well as to understand the advantages of end-to-end training (Sec. 3.3b. We will later, in Sec. build our method on these foundations.
3.1 Sample- based Inference of Safe Action Sets
For the design of safe imitator policies, is helpful know, at each stage, a set of safe actions. Roughly speaking, we consider an individual action as safe, if, after executing this action, at least one safe "best- case" future ego policy exists, i.e., keeping safety cost d(s;) below 0 for all under worst-case other agents/pent soattt/peturbationss
So, formally, define the safe (action) set in state at time t as
Ag = {a E A: it exists T+417, s.l. for all o.. and for all KK'ST, d(sr) holds, given 8,=8,0,- (3)
(based on our general setting of Sec. We refer to actions in Ai as safe actions. Such an Lilversarial/wors uncertainty rcasoning resembles common formulations from reachability game analysis (Fridoicc-Keiil
and Tomlin 2020
Bansal et al. 2017 Furthermore, define the lotal safely cost (lo go) a
w/ (s, == min max max d(se), for all t.
(4)
THEE MEE+ET
Observe the following:
The total safety cost wy allows us to quantitatively characterize the safe action set Ai as sub-zero se
A = (x(s, $ 5).
Under the worst-case assumption, for each 8; an ego policy can be part of a candidate solution of our basic problem, ie., satisfy safety constraint Eq. 22, only if n. outputted actions are all in A (because otherwise there exists no feasible continuation Te+1:T, by definition of A₃). This fact will be crucial define our safety layer (Sec. 3.2
Now, regarding inference of the safe action set AZ: while in certain limited scenarios, such as linear dynamics, it may be possible to efficiently calculate it exactly, this is not the case in general (Rungger and Tabuada 2017 We take approach to eircumvent this by checking wr(s, a) for just finite sample of a's. And
AAs usual, the min is well defined under appropriate compactness and continuity assumptions. The "=" may strictly be "E". We assume initial (or intermediate) state given.
"Note: In the scope of safety definitions, generally let ego/other policies range over compact sets II, 4 of deterministic policies. Then the minima/ aaaiiaammaxiaaa maxima well-defined, once make appropriate continuity assumptions. The finite horizon can be extended the infinite case using terminal safcty terms Pek and Althott
(2020)
Note that requiring momentary safety cost d(sr) S for each Tutmre E4-- translates to requiring that d(sw) ) S
the marimun over future Eq. (and not the sum over & done other Tormulations).
4

---

Published in Transactions on Machine Learning Research (11/2022)
then concluding on the value of ws(s,-) these a's "neighborhoods". This at least gives so-called inner approzimation. A of the safe set A;, meaning that, while A and A may not coincide, we know for sure that A; C Ag, Le,, Aj is safe. The following result gives us Lipschitz continuity and constant to draw such conchusions It builds on the fact that maximization minimization preserves Lipschitz contimuity (Appendix A.I.I). We assume all spaces are implicitly equipped with norms.
Proposition 1 (Lipschitz constants for Lipschitz- based safe set). Assume the momentary safety cost d is a-Lipschilz continuous. Assume that for all (delerminislic) ego/olher policies n, 11, E Pt, LE 1:T, the dynamics + f(s, (r(ss)(((s)) well + f(s, as, ((()) for fixed are B- Lipschitz. Then + wi(s, a) is max ( J-Lipschitz.
Let us additionally give a second approach for sample- based inner approximation of the safe set The idea is that sometimes, safety of a finite set of aomers/eatremaliin that span a set already implies safety of the full set:
Proposition 2 (Extremality-based safe set). Assume the dynamics I is linear, and the ego/other policy classes 11,T P1T consist of open-loop policies, i.e., action trajectories, and that safety cost d is conver. Then a + a) is convex. In particular, for any conver polytope B C CA we(s,)) takes its mazimum at one of the (fmilely many) corners of B.
Later we will give one biasehitzbased method version (FAGIL-L) building on Prop. I (not using Prop. 2 and one convexity-based version (FAGIL-E) building on Prop. 2 For several broader remarks on the elements of this section, which are not necessary to understand this main part though, see also Appendix D.1
3.2 Piecewise Diffeomorphisms for Flexible Safety Layers with Differentiable Closed-Form Density
An important tool to enforce safety of a policy's actions are safety layers. Assume we are given Á C A as an (inner approximation of the) safe action set (e-g., from S... A safely layer a neural net layer that maps A + Å, i.e, it constrains "pre-safe", ", i.e., potentially unsafe, action â E A into Å. In contrast to previous safety layers (Donti et al. 2021a Dalal et al. 2018) for deterministic policies, for our generative/probat probabbbbbbbiiicccccccccc approach, we want safety layer that gives us an overall policy's closed-form differentiable density (when plugging it on top of a glosed-form-denstty policy like a Gaussian or normalizing flow), for end-to-end training etc. In this section we introduce a new function class and density formula that helps to construct such safety layers.
Remember the classic change-of-variables formula (Rudin et al. 1964 Ify e(x) for some diffeomorphisn e, and has density (z),, then the implied density of is det(J, (e))) (v) { The construction of safely layers with exact density/ / ggradient only based on change of variables can be difficult or even impossible. One intuitive reason for this is that diffeomorphisms require injectivity, and therefore one cannot simply map unsafe actions to safe ones and simultancously leave safe actions where they are (as done, c.g., by certain projection-base safety layers (Donti et al. 2021a)).
These limitations motivate our simple yet flexible approach of using the following type of function as safety layers, which relaxes the rigid injectivity requirement that pure diffcomorphisms suffer from:
Definition 1 (Piecewise dilfeomorphism safety layers). We call function A + Ā piecewise diffeomorphism if there erists a countable partition (Ax)s of A, and diffeomorphisms (on the interiors)
9k : A + As C Å, such that A -9k-
Now we can combine the diffcomorphisms' chango-of-variables formulas with additivity of measures:
OOnee know that wx(s,)) is 7-Lipschitz, and that we(s, a) < 0, then we also know that -) is negative ball of radius (a.)) around a.
Note that Gillula al. 2014) also inner-aprroxinate safe sets from finite samples of the current action space, by using the conecr hull argument. But, among other differences, they do not allow for other agents, as we do in Prop.
8 A difeemmrphhism
continuously differentiable bijection whose inverse is also cont. differentiable.
9 denotes the Jacobian matrix of
5

---

Published in Transactions on Machine Learning Research (11/2022)
Proposition 3 (Closed-form density for piecewise diffeomorphism). If g is such piecewise diffeomorphism, ā = ={ā and â's densily is pa (ā); then ä's 's densily is
Pa(a)
Σ
-.) (m)).
(6)
(Ak)
Specific instances of such piecewise diffcomorphism safety layers will be given in Sec. 4 Note that one limitation of piecewise diffeomorphism layers lies in them being discontinuous, which may complicate training. Further details related to diffeomophhic layers, which are not necessary to understand this main part though, are A Appendix| D.2
3.3 Analysis of End-to-Enu End Training with Safety Layers vs. Test- Best-Time-Onl Safety Layers
After providing tools for the design of safe policies, now we focus on the following general question regarding training of such policies: What is the difference, in terms of imitation performance, between using a safety layer only during test time, compored to using during training and test time? (Note: this question /section is justification, but is not strictly necessary for understanding the definition of our method in Sec. below. So this section may be skipped if mainly interested in the specific method and experiments.)
The question is important for the following reason: While we in this paper advocate madto-end training including safety layer, in principle one could also use the safety layer only during test/production time, by composing it with an "unsafely trained" policy. This nonetheless safe, but much easier computationally in training. The latter is an approach that other safe IL work takes (Chen et al. 2019). but it means that the test-time policy differs from the trained one.
While this question is, of course, difficult to answer in its full generality, let us here provide a theoretical analysis that improves the understanding at least under certain fairly general conditions. Our analysis is inspired by the study of the compounding errors incurred by behavior cloning (BC) (Ross and Bagnell, 2010 Syed and Schapire 2010 Xu et al. 2020) For this section, let us make the following assumptions and definitions (some familiar from the mentioned BC/II, work) 10
State set S and action set A are finite. As usual (Ho and Ermon 2016), the time-averaged aate-accion distribution of æ is defined as p(s,a)= = (+ Ei Ps, (s) x (als), for all 8, a; and p(s) denotes the marginal.
We assume some safety layer (i.e., mapping from action set into safe action set) to be given and fixed. As safety layer. Additionally define z² as classic, unsafe/unan /unonsstrrir trained imitator policy [1 and TO as the des-ttme--nnlysaoeee policy obtained by concatenating n² with the safety layer at test time. Let p=,p' ,ppp" pp denote the corresponding time-averaged state-action distributions.
before, x is the demonstrator, n' the imitator trained with laii--and-tes--ffe
As is common (Ross and Bagnell 2010 Xu et al. 2020,, we measure performance deviations in terms of the (unknown) demonstrator cost function, which denote by c" (i.e., in the fashion of inverse reinforcement learning (IRL), where the demonstrator is assumed to be an optimizer of Eq.
(2) with c" as c): and assume a' only depends on 8, and || is its maximum value. Let DD = y P.." vd y 10 = 2 be the corresponding total imitation cost functions (Sec. p.
We assumne that (1) the demonstrator always acts safely, and (2) the safety layer is the non-identity only actions that are never taken by the demonstrator (mapping them to safe ones). Importantly, note that if we relar these assumptions, in particular, allow the demonstrator to be unsafe, the results in this section would get even stronger (the difference of adding a safety layer would be even bigger).
Keep in mind that what we can expect to achieve by GAIL training is a population- closeness of imitator to demonstrator state-action distribution of the form D(pt, PD) < c, for some e decreasing in the sample size (duc to the usual bias/ tasss/ennraaizztion error; (Xu et al. 2020 ), and D, c.g., the Wasscrstein distance (Sec. 4.2). So we make this an assumption in the following results. Here we use D(p .ipppP) = (rv pP)= =
We believe that most of the simplifying assumptions make can be relaxed, but the analysis will be much more involved. Un our case this would essentially mean to take the pre-safe policy, e-g., Gaussian, with pre-safe âe, and train it, as ~"
6

---

Published in Transactions on Machine Learning Research (11/2022)
unsafe caatesdissances occasionally front visitied by unsafe trained imitator
main road
po
vehicle
safe side strip, never visitied by unsafe imitator, hence not learned to recover
side strip
4
Figure Staying with our running example of driver imitation, this figure illustrates the following: if we use safety layers only at test time and not already during training, the test-time imitator has nol learned to deal with the states that the safety layer may lead to (i.e. to either plan to avoid, recover from them), yielding poor imitation performance. In nutshell: The demonstrator is always 1pp=1) in state 1, mcaning constant velocity and distance to the front vehicle. At rest/deployment time, the unsafely trained imitator x", due to learning error, with low probability p²=ō, deviates from state 1 and reaches first state 2 and then (due to, say, inertia) unsafe state 3, from which it has learned to always recover though. The test-time- only-safe imitator 70, like the unsafely trained imitator it builds upon, with low probability p²=ô reaches state 2. But from there, the safely constraints (red scissors symbol) kick in and the only remaining action is to go the safe side strip with p 1, where there no data how to recover (never visited/learman by unsafe n²), getting trapped there forever. Details are in Appendix A.3
I Exesaea as - (s, a)l, the lotal varialion distance Klenke 2013 which simplifies parts of the derivation, though we believe that versions for other D such as Teensen-Shanmne are possible.
Now, first, obscrve that for our "train and test safety layer" approach, we can have a linear, in the horizon T, imitation performance guarantee. This is because the imilalor x¹ is explicilly trained to deal with the safety layer (i.e., to plan to avoid safe but poor states, to at least recover from them; see Appendix A.3.1 for the dcrivation):
Remark (Linear error of imitator with train-and-lest-llmee safety layer). Assume Drvlø' pP) 8. Then we get
1o' u =2
In contrast, using test-timc-only safety, the test-time imitator TO has not learned to plan with, and recover from, the states that the safely layer may lend to. This leads, essentially, a light quadralic error bound (when accounting for arbitrary, including "worst", environments; proof in Appendix A.3
Theorem (Quadratic error in T of imitator with test-time-only safety layer). Lower bound (an "exis- tence" statement): We can construct an environment [T2 with variable horizon T and with demonstrator, sketched in Fig. - and additional details in Appendic A.3.2 a universal constant 1, and, for every e > O, an unconstrainedly trained imitator " with Drv(p
S e, such that for the induced gest-time-only-saee
imitator T we have, for all T > 2
100 2 mmT
Upper bound (a "for all" statement): Assume Drv(p" ,p)) S E and assume (s) has support wherever p()) has. Then
48 T2 locc
100 - -0-01
(8)
where v is the minimum mass of (s) within the support of ps)).
1n this discrete settings, the euvironment amounts to Markov decision process (MDP) (Sutoon and Barto 2018
13e quadratic bound Eq. 7 substantial once look at small e, because then the quadrafic bound holds even large T. while the train-and-test--ree safety layer in Rem. I keeps scaling linearly in T. See also Rem. 4 in Appendix A.3.2
7

---

Published in Transactions on Machine Learning Research (11/2022)
4 Method Fail-Safe Adversarial Generative Imitation Learner
Building the above theoretical tools and arguments for end-to-end training, we now describe our modular methodology FAGIL for safe generative IL. Before going into detail, note that, for our general continuous setting, tractably inferring safe sets and tractably enforcing safety constraints are both commonly known to be challenging problems, and usually require non-trivial modeling trade-offs (Rungger and Tabuada 2017
Gillula et al.) 2014 AAchiam et al.] 2017; Donti et al., 2021b). Therefore, here we choose to provide (I) one tractable specific method instonce for the low- dinemmmeniinn case (where we can efficiently partition the action space via grid), which we also use in the experiments, alongside (2) an abstract template of general
approach. We discuss policy, safety guarantees (Sec. 4.1 imitation loss and training (Sec. 4.2
4.1 Fail-Safe Imitator Policy with Invariant Safety Guarantee
First, our method consists of the fail-safe (generative) imitator x² (als). Its structure is depicted on the I.h.s. of Fig. D and contains the following modules: at each time t of rollout, with state 8t as input,
(a) the pre-safe generative policy module outputs pre-safe (i.e., potentially unsafe) sample action
â E A as well as explicit probability density (āj=(ā]sı) with parameter @ and its gradient. Specific instan- tiations: This can be, e.g., a usual Gauss policy or conditional normalizing flow [
(b) The safe set inference module outputs an inner-approximate on our results form Sec. 3.1 The rough idca is as follows (rocall that an action a is safe its total safety cost uy(s a) S 0): We check 15 Wy (st, a) for a finite sample of a's, and then conclude on the value of (y(ss,)) on these a's "neighhorhoods" ; via Prop. or Prop. 16
A" of the safe action set, building
Specific instantiations: We partition the action set A into boxes (hyper-rectangles) based on a regular grid (assuming A is box). Then we go over each box Aş and determine its safety by evaluating wr a), with either a the center of Ag, and then using the Lipschitz continuity argument (Prop. 1 to check we :) S 0 on the full Av (FAGIL-L), or a ranging over all corners of box As, yielding safety of this box iff wy (8t, :) S 0 on all of them (FAGIL-E; Prop. 2). Then, as inner- aperrxippx safe set A²', return the union of all safe boxes Ag.
(c) Then, pre-safe action å plus the safe set inner approximation A are fod into the safety layer. The idea is to use a piecewise diffeomorphism g from Sec. 3.2 for this layer, because the "countable non-injectivity" gives quite some flexibility for designing this layer, while nonetheless we get closed-form density by summing over the change-of-variablee formulas for all diffeomorphisms that map to the respective action (Prop. 3). As output, we get a sample of the safe action â,, as well as density x <==((a))))) (by plugging the pre-safe policy's density (ā)s() into Prop- 3 and gradient w.r.t. 0.
Specific instantiations: We use the partition of A into boxes (Ax)s from above again. The piecewise diffemorphism g is defined as follows, which we believe introduces helpful inductive bias: (a) On all safe boxes k i.c., A C A, Ik is the identity, i.c., we just keep the pre-safe proposal à. (b) On all unsafe boxes k, Ih is the translation and scaling to the most nearby safe box in Euclidean distance. Further safety layer instances and illustrations are in Appendix D.3
Adding a safe fallback memory To cope with the fact that it may happen that at some stage an individual safe action exists, but no fully safe part As exists (since the A are usually sets of more than one action and not all have to be safe even though some are safe), we propose the following, inspired by (Pek and Althoff 2020 the fail-safe imitator has memory which, at each stage t, contains one purportedly fail-safe fallback future ego policy =/ "(+1T-- Then, no fully safe part A (including a new fail-safe fallback) is found anymore at t ++1, execute the fallback m/+1, and keep 7(42. new fail-safe fallback (see also Appendices B and D.3.5 on potential issues with this).
14 A is box-shaped, then we add squashing layer to get actions into A using component-wie sigmoids. 18 Clearly, already the "checker" task of evaluating single action's safety, Eq. ( can be non-trivial. But often, roll-outs, analytic steps, convex optimizations or further inner approximations can be used, combinations of them, see also Sec. Due to modularity, other safety frameworks like Responsibliiy-SSnsiiive Safety (RSS) Shalev-Shwartz ct al. 2017 be
plugged into our approach well. The fundamental safety trade-off is between being safe (conservativity) versus allowing enough freedom to be able "move all" (actionahility.
8

---

Published in Transactions on Machine Learning Research (11/2022)
Remark 2 (Invariant safety guarantee). Based on the above, if we know at least one safe action at stage 1, then we invoriably over time have al least one safe action plus subsequent foil-safe fallbock policy. So we are guaranteed that the ego will be safe throughout the horizon 1:T.
4.2 Imitation Cost and Training Based on Generative Adversarial Imitation Learning
In principle, various frameworks can be applied to specify imitation cost (which we left abstract in Sec. 2 and training procedure for our fail-safe generative imitator. Here, we use a version of GAIL (Ho and Ermon 2016 Kostrikov et. al. 2018) for these things. In this section, we give a rough idea of how this works, while some more detailed background and comments for the interested reader are Appendix [ In GAIL, roughly speaking, the imitation cost c(s, a) given via a GAN's discriminator that trics to distinguish between imitator's and demonstrator's average state-action distribution, and thereby measures their dissimilarity. As policy regularizer (TT)) in Eq. [2. take r's differential entropy (Cover and Thomas 2006).
Training As illustrated the r.h.s. of Fig. essentially, training consists of steps alternating between: (a) doing rollouts of our fail-safe imitator x x. (als) under current parameter 0 to sample imitator state- action trajectories (the generalor); (b) obtaining new discriminator parameters and thus c, by optimizing a discriminator loss, based on trajectory samples of both, imitator n' and demonstrator x x"; (c) obtaining new fail-safe imitator policy parameter O' by optimizing an estimated Eq. (2) from the trajectory sample and c. Note that in (c), the fail-safe imitator's closed-form density formula (Prop. 3) and its gradicnt are
used (the precise use depends on the specific choice of policy gradient (Kostrikov al. 2018
Sutton and
Barto 2018)).
5 Experiments
The goal of the following experiments is to demon- strate Iractability of our method, and empirically compare safety as well as imitation initaation/prddcction per- formance to baselines. We pick driver imitation from real-world data as task because it is relevant for both, control (of vehicles), as well as modeling (e.g., of real "other" traffic participants, for validation of self-driving "ego" algorithms [Suo et al. (2021); [g] et a.. (2022) Furthermore, its characteristics are quite representative of various challenging safe con- trol and robust modeling tasks, in particular includ- ing fixed (road boundary) as well as many moving obstacles (other drivers), and multi-modal uncer- taintics driver behavior.
Figure 3: Driving from right to left, our fail-safe imita- tor (blue) with past trajectory (blue) and future fail- safe fallback emergency brake (green); other vehicles (red), with worst-case reachable boundaries indicated in yellow (rear vehicles are ignored as described).
Data set and preprocessing We use the open hight) data set (Krajewski et al. 2018), which consists of 2-D trajectorics (each ~20s) recorded by drones flying section with 1500 trajectories). It is increasingly used for beuchmarking (Rudenko el. al. 2019 Zhang jet al. 2020). We filter out other vehicles in a roll-out once they are behind the ego vehicle Additionally, we filter out initially unsafe states (using the same filter for all methods).
highway sections (we select straight
Setting and simulation We do an open-loop simulation where we only replace the ego vehicle by our mothod/thn basclines, while keeping the others' trajectories from the original data. The action is 2-D (longitudinal and lateral acceleration) and the simulation environment's dynamics f we take a component- wise double integrator. As collision/saferr cost d(s); take minus the minimum Lo distance (which is
This is substantial filtering, but is, in way another, commonly done Pekk and Althoff 2020 Shalev-Shwartz et al. 2017 It is based the idea that the ego is not blamable for other cars crashing into it from behind (and otherwisc safcty may become conservative; most initial states could already unsafe we consider adversarial vehicles that deliberately crash from behind).
9

---

Published in Transactions on Machine Learning Research (11/2022)
Table 1: Outcome on real-world driver data, in terms of imitation and safety (i.e., collision) performance.
Method
Imstation performance
Safety performance Probability of crasshooffroad
Pre-safe
Overall
ADE
FDE
FAGIL-E (ours)
0.59
1.70
0.00
FAGIT-L (ours)
0.60
1.77
0.00
Gauss
GAIL
Ho and Ermon (016))
0.47
1.32
0.13
RAIL
Bhattacharyya et al. 2020))
0.48
1.35
0.22
TTOS (Sec. 3.3
0.60
1.78
0.00
FAGIT-FE (ours)
0.58
1.69
0.00
FAGIL-L (ours)
0.57
1.68
0.00
Flow
GAIL
Ho and Ermon (0166)
0.44
1.22
0.11
RAIL
Bhattacharyya et al. 20200)
0.53
1.50
0.11
TTOS (Sec. 3.3
0.59
1.72
0.00
particularly easy to compute) of ego to other vehicles (axis-aligned bounding boxes) and road boundary, which is 2-Lipschitz (from norm al to I
Policy fail-safe imitator We use our FAGIL imitator policy from Sec. 4.1 As learnable state feature, the state is first rendered into an abstract birds-eye-view image, depicting other agents and road boundaries, which is then fed into a convolutional net (CNN) for dimensionality reduction, similar as described in (Chai (et al. 2019). Regarding safe set inference: In this setting, where the two action/stati dimensions and their dynamics are separable, the others' reachable rectangles can simply be computed exactly based on the others' iitoorattio/vllccitt (this can be extended to approximate separability (Pek and Althofl, 2020)). As ego's fallback maneuver candidates, use non-linear shortest-time controllers to roll out emergency brake and evasive maneuver trajectories (Pek and Althofi 2020). Then the total safety cost w is calculated by taking the maximum momentary safety cost d between ego's maneuvers and others' reachable rectangles over time. Note that the safety cost d and dynamics f with these fallbacks are each Lipschitz continuous as required by Prop. 1 rigorously implying the safely guaruntee for FAGIL.-L (FAGIL- E does only roughly but not strictly satisfy the conditions of Prop. 2 but we conjecture it can be extended appropriately.) As safety layer, use the cestancc-based instance from Sec. 4.1 Training: Training
maximum longitudinaallattraa
happens according to Sec. 4.2 using GAIL with soft actor-critic (SAC) (Kostrikov et al. 2018 Haarnoja
et al. 2018) as policy training (part (c) in Sec. 4.2 based on our closed-form density from Sec. 3.2 Further
details on setup, methods and outcome are in Appendix C
Baselines, pre-safe policies, ablations, metrics and evaluation Baselines are: classic GAIL Ho and
Ermon (0166), reward- augmentee GAIL (RAIL) (closest comparison from method class of safe generative II., discussed in Sec. 1h (Bhattacharyya et al. 2020 2019), and GAIL, with test-time-only safety layer (TTOS) (Sec. 3.3). Note that TTOS can be seen as an ablation study of our method where we drop the safety layer during train-time, and GAIL an ablation where we drop it during train and test time. For all mot including ours, as (pre-safe) policy we evaluate both, Gaussian policy and conditional normalizing flow. We evaluate, on the test set, overall probability (frequency) of collisions over complete roll-outs (including crashes with other vehicles and going off-road) as safely performance measure; and average displacement error (ADE; i.e. time-averaged distance between trajectories) and final displacement error (FDE) between demonstrator ego and imitator ego over trajectories of 4s length as imitation imitationnprrdicttii pppediction performance measure Suo et al. 2021
Outcome and discussion The outcome is Table I (rounded to two decimal points). It empirically validates our theoretical safely claim by reaching 0% collisions of our FAGIL methods (with fixed and moving
10

---

Published in Transactions on Machine Learning Research (11/2022)
obstacles; note that additionally, TTOS validates safety of our safety inference/layerr.. At the same time FAGIT comes close in imitation performance to the baselines RATT./GATI, which, even if using reward augmentation to penalize collisions (RAIL), have significant collision rates. (The rather high collision rate of RAIL may also be due to the comparably small data set we use.) FAGIL's imitation performance is slightly better than TTOS, which can be seen as a hint lowards an average-case confirmation, for this setting, of our theoretical worst-case analysis (Thm. D but the gap is rather narrow. Fig. B gives one rollout sample, including imitator ego's fail-safe and others' reachable futures considered by our safe set inference.
6 Conclusion
In this paper, we considered the problem of safe and robust generative imitation learning, which is of relevance for robust realistic simulations of agents, as well as when bringing learned agents into many real- world applications from robotics to highly automated driving. We filled in several gaps that existed so far towards solving this problem, in particular in terms of sample-based inference of guaranteed adversarially safe action sets, safety layers with closed-form density//rrdieent, and the theoretical understanding of end-to- end generative training with safety layers. Combining these results, we described a general abstract method for the problem, as well as one specific tractable instantiation for low-dimensional setting. The latter we experimentally evaluated on the task of driver imitation from real-world data, which includes fixed and moving, uncertain obstacles (the other drivers).
Limitations of our work in particular come from the challenges that safety goals often bring with them, terms of tractability and cautiousness: First, while our theoretical results hold more generally, the specific grid-based method instantiation we give is tractable only in the low-dimensional case, and in the experimental setting we harnessed (raciability via separabilily of longiludinal and lateral dynamics of the other agents. Second, worst-case safety can lead to overly cautious actions while human "demonstrators" often achieve surprisingly good trade-offs in this regard; incorporating more restrictions about other agents, such as the responsibility-senas
safety (RSS) framework, would still be covered by our general theory but help to be less conservative. We also inherit known drawbacks of generative adversarial imitation learning-base based approaches, in particular instabilities in training, and this can further increase by the additional complexity induced by the safety layer. On the experimental evaluation side, we focused on first study on one challenging but restricted setting, leaving an extensive purely empirical study to future work.
In this sense, our work constitutes one step on the path of combining fleribility and scalability (i.c., general capacity for learning with little hand-crafting) of neural net-based probabilistic policies with theoretic worst- case safety guarantees, while maintaining end-to-end generative trainability.
Broader Impact Statement
When controlling agents in physical environments that also involve humans, such as robots that interact with humans, where even small and/or rare mistakes of methods can injur people, "pure" deep imitation learning approaches can be problematic. This is because often they are "black boxes" for which we do not understand precisely enough how they behave "outside the training distribution". Our approach can ideally have a positive impact on making imitation learning-based methods more safe and robust for such domains (or making them more applicable for such domains in the first placo). One limitation of our work (beyond the technical limitations discussed above) is that in the end, society a has to debate and decide on the difficult trade-offs in terms of cautiousness versus actionability that safe control often involves (clearly safety is of highest value, but the question is how much residual risk society wants to take, given there rarcly exists perfect safety). Science can just acknowledge the problem and provide understanding and tools. And overall, automation via machine learning approaches, including our approach, can have positive and negative impacts on jobs and the economoy overall, which society needs to consider and make decisions about.
References
Joshua Achiam, David Held, Aviy Tamar, and Pieter Abbeel. Constrained policy optimization. In Interna- tional conference on machine learning, pages 21. PMLRR 2017.
11

---

Published in Transactions on Machine Learning Research (11/2022)
Lukáš Adam, Rostislav Horčík, Tomás Kasl, and Tomás Kroupa. Double oracle algorithm for computing equilibria in continuous games. Proc. of AT-2- 2021.
Anayo K Akametalu, Jaime F Fisac, Jeremy H Gillula, Shahab Kaynama, Melanie N Zeilinger, and Claire J Tomlin. Reachability- safe learning with gaussian processes. In 53rd IEEE Conference on Decision and Control, pages 1424 1431. IEEE, 2014.
Mohammed Alshickh, Roderick Bloem, Rüdiger Ehlers, Bettina Könighofer, Scott Nickum, and Ufuk Topcu. Safe reinforcement learning via shielding. In Proceedings of the AAAT Conference Artäficial Intelligence, volume 32, 2018.
Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization as layer in neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 136 145.1.5.44 JMLR. org, 2017.
Brandon Amos, Ivan Jimenez, Jacob Sacks, Byron Boots, and J Zico Kolter. Differentiable mpc for end- to-end planning and control. In Advances in Neural Information Processing Systems, pages 8289-8300, 2018.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pages 214-223. PMLR, 2017.
Shaojie Bai, J 'icco Kolter, and Vladlen Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems, pages 688-699, 2019.
Mayank Bansal, Alex Krizhevsky, and Abbijit Ogale. Chaufleurnet: Learning to drive by imitating the best and synthesizing the worst. arxiv preprint "ix::1812.0007 2018
Somil Bansal, Mo Chen, Sylvia Herbert, and Claire J Tomlin. Hamilton-aacobi reachability: A brief overview and recent advances. In 2017 IEEE 56th Annual Conference Decision and Control (CDC), pages 2242 2253. IEEE, 2017.
Nir Baram, Oron Anschel, Itai Caspi, and Shie Mannor. End-to-end differentiable adversarial imitation learning. In International Conference on Machine Learning, pages 390-399. PMLR, 2017.
Felix Berkenkamp, Matteo Turchetta, Angela Schoellig, and Andreas Krause. Safe model based reinforce- ment learning with stability guarantees. arXiv preprint arXiv:1705, 170500551,, 2017.
Dimitri Bertsekas. Dynamic programminng and oplimal control: Volume I, volume 1. Athena scientific, 2012.
Michel Besserve and Beruhard Schölkopf. Learning soft interventions in complex equilibrium systems. arvivv preprint ar Xrx:22 12. 0.7792 2021.
Raunak Bhattacharyya, Blake Wulfe, Derek Phillips, Alex Kuefler, Jeremy Morton, Ransalu Senanayake, and Mykel Kochenderfer. Modcling human driving behavior through generative adversarial imitation learning. Xix preprind arXiv:2006. 20Xi::2006.0//2, 2020.
Raunak P Bhattacharyya, Derek J Phillips, Changliu Liu, Jayesh K Gupta, Katherine Driggs- Driggs-Cample Campbell, and Mykel J Kochenderfer. Simulating emergent properties of human driving behavior using multi-agent reward augmented initation learning. In 2019 International Conference Robotics and Automation (ICRA), pages
IEEE, 2019.
Damian Boborzi, Florian Kleinicke, Jens Buchner, and Lars Mikelsons. Learning to drive from observations while staying safe. 2021. upcoming.
Daniel Brown, Russell Coleman, Ravi Srinivasan, and Scott Nickum. Safe imitation learning via fast bayesian reward inference from preferences. In International Conference on Machine Learning, pages 1165-1177. PMLR, 2020.
12

---

Published in Transactions on Machine Learning Research (11/2022)
Zhangjie Cao, Erdem Bıyak, Woodrow Z Wang, Allan Raventos, Adrien Gaidon, Guy Rosman, and Dorsa Sadigh. Reinforcement learning based control of imitative policies for near-accident driving. orXiv preprinl arXiv:2007.00178. 2020.
Michael R Caputo.
The envelope theorem and comparative statics nash equilibria. Games and Economic Behavior, 1322):201-224, 1996.
Yuning Chai, Benjamin Sapp, Mayank Bansal, and Dragomir Anguelov. Multipath: Multiple probabilistic anchor trajectory hypotheses for behavior prediction. arXiv preprint 1910.054444 2019.
Jianyu Chen, Bodi Yuan, and Masayoshi Tomizuka. Deep imitation learning for autonomous driving in generic urban scenarios with enhanced safety. arXiv preprint arXiv:1903.0066 2019.
Zhihao Cheng, Li Shen, Meng Fang, Liu Liu, and Dacheng Tao. Lagrangian generative adversarial imitation learning with safety, 2022. URL
Yinlam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duenez-Guzman, and Mohammad Ghavamzadch. Tyapunox-based safe policy optimization for continuous control. arXiv preprint 1901:1900.000 2019.
Thomas M. Cover and Joy A. Thomas. Flements of Information Theory. Willy-Interscience,, 2006.
Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. arXiv preprint Xix::1801008757, 2018.
Priya L Donti, Melrose Roderick, Mahyar Fazlyab, and J Zico Kolter. Enforcing robust control guarantees
within neural network policies. In International Conference on Learning Representations, 2021a.
Priya L Donti, David Rolnick, and J Zico Kolter. Dc3: A learning method for optimization with hard constraints. arXiv preprint orXiv:2104.122 2021b.
Laurent El Ghaoui, Fangda Gu, Bertrand Travacca, and Armin Askari. Implicit deep learning. ar preprint (.Xiv:190800631 2019.
David Fridovich-Kei and Claire Tomlin. Approximate solutions to a class of reachability games. arXiv preprinl trxiv:2011.000 1.00001, 2020.
Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adversarial inverse reinforcement learning. arXiv preprint 1TXiv:1710.112466 2017.
Philipp Geiger and Christoph-Nikolas Strachle. Learning tane-theoretic models of multiagent trajectories using implicit layers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 4950 4958, 2021.
Jeremy H Gillula, Shahab Kaynama, and Claire Tomlin. Sampling-based approximation of the viability ker- nel for high-dimensional linear sampled-data systems. In Proceedings of the 1 17th international conference on Hybrid systems: computation and control, pages 173-182, 2014.
Colas Le Guernic and Antoine Girard. Reachability analysis of hybrid systems using support functions. In International Conference on Computer Aided Verification, pages 540 554. Springer, 2009.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-poliey maximum entropy deep reinforcement. learning with stochastic actor. In International conference on machine learnóng, pages 1861 1870. PMLR, 2018.
Aaron Havens and Bin Hu. On imitation learning of linear control policies: Enforcing stability and robustness constraints via Imi conditions. In 2021 American Control Conference (ACC), pages 887- IEEE, 2021.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 4573, 2016.
13

---

Published in Transactions on Machine Learning Research (11/2022)
Jonathan Ho, Jayesh Gupta, and Stefano Ermon. Model-free imitation learning with policy optimization. In International Conference on Machine Learning, pages 2760-2769 PMLR, 2016.
Junning Huang, Sirui Xie, Jiankai Sun, Qiurui Ma, Chunxiao Liu, Jianping Shi, Dahua Lin, and Bolei Zhou. Learning a decision module by imitating driver's control behaviors. arXiv preprint 1912: 00191, 2019.
Maximilian Igl, Daewoo Kim, Alex Kuefter, Paul Mougin, Punit Shah, Kyriacos Shiarlis, Dragomir Anguelov, Mark Palatucci, Brandyn White, and Shimon Whiteson. Symphony: Learning realistic and diverse agents for autonomous driving simulation. arXiv preprint or arXi::2205.03190 2022.
Zaynah Javed, Daniel S Brown, Satvik Sharma, Jerry Zhu, Ashwin Balakrishna, Marek Petrik, Anca Dragan, and Ken Goldberg. Policy gradient bayesian robust optimization for imitation learning. In International Conference on Machine Learning, pages 4785-4796. PMT.R, 2021.
Achim Klenke. Probability theory: a comprehensive course. Springer Science Business Media, 2013.
Vilmos Komornik. Topology, caleulus and approzimation. Springer, 2017.
Philip Koopman, Aaron Kane, and Jen Black. Credible autonomy safcty argumentation. In 27th Safety- Critical Systems Symposium, 2019.
Ilya Kostrikov, Kumar Krishna Agrawal, Debidatta Dwibedi, Sergey Levine, and Jonathan Tompson. aescrininator--ccto-crittt Addressing sample inefficiency and reward bias in adversarial imitation learn- ing. arXiv preprint arXiv:1804 180.00225,, 2018.
Robert Krajewski, Julian Bock, Laurent Kloeker, and Lutz Eckstein. The highD Dataset: Drone Dataset of Naturalistic Vehicle Trajectories on German Highways for Validation of Highly Automated Driving Systems. In 2018 IEEE 21st International Conference on Intelligent Transportation Systems (ITSC), 2018.
Jonathan Lacotte, Mohammad Ghavamzadeh, Yinlam Chow, and Marco Pavone. Risk-scnsitive genera- live adversarial imitation learning. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2154-2163. PMLR, 2019.
Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach multiagent reinforcement learning. anXiv preprinl ar 1atr:111100022 2017.
Chun Kai Ling, Fei Fang, and J Zico Kolter. What game are we playing? End-to-end learning in normal and extensive form games. In IJCAI-ECAT-18: The 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence, 2018.
Chun Kai Ling, Fei Fang, and J Zico Kolter. Large scale learning of agent rationality in two-player zero-sum games. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 33, pages 6104-6111, 2019.
Bjornar Steinnes Luteberget. Numerical approximation of conformal mappings. Master's thesis, Institutt for matematiske fag, 2010.
Xiaobai Ma, Jayesh K Gupta, and Mykel J Kochenderfer. Normalizing flow policies for multi-agent systems. In International Conference on Decision and Game Theory for Security, pages 277 296. Springer, 2020.
Silvia Magdici and Matthias Althoff. Fail-safe motion planning of autonomous vehicles. In 2016 IEEE 19th International Conference on Intelligent Trunsportation Systems (ITSC), pages 452 458. IEEE, 2016.
Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J Andrew Bagnell, Picter Abbeel, and Jan Peters. An algorithmic perspective imitation learning. arXio preprint X111:811.00771 2018.
14

---

Published in Transactions on Machine Learning Research (11/2022)
Fabian Otto, Philipp Becker, Ngo Anh Vien, Hanna Carolin Ziesche, and Gerhard Neumann. Differentiable trust region layers for deep reinforcement learning. arXie preprint (1:::201100920000 2021.
Brian Paden, Michal Cáp, Sze Zheng Yong. Dmitry Yershov, and Emilio Frazzoli. A survey motion planning and control techniques for self-driving urban vehicles. TEEE Transactions on intelligent vehicles, 1(1):33-55 2016.
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshmi- narayanan. Normalizing flows for probabilistic modeling and inference. arXiv preprint 1.XXx:1112.021 2019.
Christian Pek and Matthias Althoff. Computationally efficient fail-safe trajectory planning for self-driving vehicles using convex optimization. In 2018 21st International Conference on Intelligent Transporlation Systems (ITSC), pages 1447-1454. IEEE, 2018.
Christian Pek and Matthias Althoff. Fail-safe motion plamning for online verification of autonomous vehicles using convex optimization. IEFE Transactions on Robotics, 37(3):798 814, 2020.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
Andrey Rudenko, Luigi Palmieri, Michael Herman, Kris M Kitani, Dariu M Gavrila, and Kai O Arras. Human motion trajectory prediction: A survey, arXiv preprint arxie; 190::19050000 06110, 2019.
Walter Rudin et al. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1964.
Matthias Rungger and Paulo Tabuada. Computing robust controlled invariant sets of linear systems. IEEE Transactions on Automatic Control, 62(7))3665 3670, 2017.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. On a formal model of safe and scalable self-driving cars. arXiv preprint arXiv:170. 8rX6::1708.0637, 2017.
Chelsea Sidrane, Amir Maleki, Ahmed Irfan, and Mykel J Kochenderfer. Overt: An algorithm for safety verification of neural network control policies for nonlinear systems. Journal of Machine Learning Research, 23(117):1-45, 2022.
Jiaming Song, Hongyu Ren, Dorsa Sadigh, and Stefano Ermon. Multi-agent generative adversarial imitation learning. arv preprint arXiv:180..00 09936, 2018.
Simon Suo, Sebastian Regalado, Sergio Casas, and Raquel Urtasun. Trafficsim: Learning to simulate rcalistic multi-agent behaviors. arXiv preprint arXiv:2101.066 06557, 2021.
Richard S Sutton and Andrew G Barlo. Reinforcement leurning: An introduction. MIT press, 2018
Umar Syed and Robert E Schapire. A reduction from apprenticeship learning to classification. Advonces in neural information processing systems, 23:2253 2261222611222 2010.
Brijen Thananjeyan, Ashwin Balakrishna, Suraj Nair, Michael Luo, Krishnan Srinivasan, Minho Hwang, Joseph E Gonzalez, Julian Ibarz, Chelsea Finn, and Ken Goldberg. Recovery rl: Safe reinforcement learning with learned recovery zones. IEEE Robotics and Automation Letters, 6(3):4915-499) 2021.
Stephen Tu, Alexander Robey, Tingnan Zhang, and Nikolai Matni. On the sample complexity of stability constrained imitation learning. In Learning for Dynamics and Control Conference, pages 180-191. PMT.R, 2022.
Renée Vidal, Shawn Schaffert, John Lygeros, and Shankar Sastry. Controlled invariance of discrete time sys- tems. In International Workshop on Hybrid Systems: Computation and Control, pages 437-451. Springer, 2000.
15

---

Published in Transactions on Machine Learning Research (11/2022)
Kim P Wabersich and Melanie N Zeilinger. Linear model predictive safety certification for learning- based control. In 2018 IEEE Conference Decision and Control (CDC), pages -130.-715. IEEE, 2018.
Patrick Nadeem Ward, Ariella Smofsky, and Avishek Joey Bose. Improving exploration in soft-actor-critic with normalizing flows policies. arXiv preprint (rXiu:1966002701 2019.
Huang Xiao, Michael Herman, Joerg Wagner, Sebastian Ziesche, Jalal Etesami, and Thai Hong Linh. Wasser- stein adversarial imitation learning. arXiv preprint ar 08113, 2019.
Tian Xu, Ziniu Li, and Yang Yu. Error bounds of imitating policies and environments. arXiv preprint arXiv:2010. 11876, 2020.
He Yin, Peter Seiler, Ming Jin, and Murat Arcak. Imitation learning with stability and safety guarantees. IEEE Control Systems Letters, 2021.
Wenyuan Zeng, Wenjie Luo, Simon Suo, Abbas Sadat, Bin Yang, Sergio Casas, and Raquel Urtasun. End- to-end interpretable neural motion planner. In Proceedingss of the IEEE/CVF Conference on Compuler Vision and Pattern Recognétion, pages 8660 8669, 2019.
Wenyuan Zeng, Shenlong Wang, Renjie Liao, Yun Chen, Bin Yang, and Raquel Urtasun. Dsdnet: Deep structured self-driving network. In European Conference on Computer Vision, pages 1561772 Springer, 2020.
Chengyuan Zhang, Jiacheng Zhu, Wenshuo Wang, and Junqiang Xi. Spatiotemporal learning of multivchicle interaction patterns in lane-change scenarios. arXiv preprint arXic:2003.00759 2020.
16

---

Published in Transactions on Machine Learning Research (11/2022)
Appendix
A Proofs with remarks
This section contains all proofs for the mathematical results of the main text, as well as some additional remarks.
Note: the main text, we did neither explicitly introduce the probaility space and random variables, nor explicitly distinguish values/events of such variables from the variables themselves, since this was not crucial and would have hindered the readability. However, some of the following proofs, whenever necessary to have full rigor, we will make these things explicit.
A.1 Proofs for Sec. 3.1
A.1.1 Proof of Prop.
We will need the following known result (a fact that lies somewhere between envelope and mazimum theorem)):
Fact 1. Let h be function from X x Y to R, and assume X and R to be equipped with some given norms (to which Lipschitz continuity refers in the following). Assume h(x, v) is Lipschitz in a with constant L uniformly in and assume that maxima exist. Then the function I + max, h(2, y) is also L-Lipschilz.
For the sake of completeness, we provide proof of Fact D Note: We show the statement for the case that supremum is always taken, i.c., is maximum. For the supremum version we refer the reader to related
work 18
Proof of Fact [ Let || and |-1 denote the given norms on X, R, respectively. Let e(x) = arg max, h(., v) (or pick one argmax if there are several).
Consider an arbitrary but fixed pair x, and let, w.l.o.g,, max, h(2, v) 2 max, h(0', 8). Then:
max h(,, y) max h(1', .y]
(9)
"
max h(x,, v) max h(x', w)
(10)
4
= Mile,, e(x)) - -1(z're<z'))
(11)
S h(x,, e(x)) - -((x',(x)))
(since h(z',e(z')) 2 e(())(())))
(12)
< L| x'
(13)
Now we use this fact for the proof of Prop. 1
Proof for Prop. 4 The idea to first propagate the Lipschitz contimuity through the dynamics, and then iteratively apply Fact 1 the min/max operations.
Here, for any Tipschitz continuous function e, let The denote its constant. Furthermore, regarding policies, may write π, shorthand for Tey E 1 T,, respectively.
First observe the following, given an arbitrary but fixed t and n.
Let
(14)
18 For proof, e-g., htttps://aatt:
17

---

Published in Transactions on Machine Learning Research (11/2022)
and h(s, G, k) be defined as the k-times concatenation of g( n. о), i..., roll out; and then define function by also including the initial action, i.e.,
i(s a, a.a,a, == (()
(15)
Then, by our assumptions, for 9, o, k arbitrary but fixed,
8 d n.
(16)
is Lipschitz continuous in with constant (uniformly in o)
Lall ((x())))))))) aB*
(17)
since the composition of d, which is a-Lipschitz, with the k-times concatenation of g, which is 3-Lipschitz by assumption. This together with our assumption implies that, for any arbitrary but fixed s, also
a + d(i(s, a, a, a, k=)(= wr(s, a))
(18)
is Tipschitz uniformly in n, o, with constant (for any k))
a B = 3 ag S m
(19)
Now let state be arbitrary but fixed. Also let be arbitrary but fixed. Then, based on the above together
with Fact
- max max a,, c(a det tEt+1:T
(20)
is Lipschitz with constant a ma 3²) Again applying Fact 1 we see that also
a+ min max max (,(ss,,T,,0 (,, min e(a, T))
(21)
T+t dur 1:t+
is Lipschitz with constant a max )
Remark 3. Alternative versions of this result could be based, e.g., on the "Envelope Theorem for Nash
Equilibria" " Caputo 1996).
A.1.2 Proof of Prop.
Proof for Prop.
Let the mapping i be defined as in Eq. 15 Fix 8.
Observe that, based on our assumption that d is convex and the dynamics f linear, for any o, fixed,
T). + d(i(s,a,z,o,t))
(22)
is convex. But then, also the maximumn over 0,t, ie.,
(a, TT) + max max d(i(s, a, a,,,t, auz 1Et+1:T
(23)
is convex, because the element-wise maximum over a family of convex functions in our case the family indexed by a,t is again convex.
One step further, this mcans (since convexity preserved by "minimizing out" one variable over convex domain) that also laking the minimum over preserves convexily, i.e.,
we(s,a)= min max max d(i(s,a,7,o,t)) asin our tEt+1:7
(24)
is convex as a function of a.
But a convex function over a (compact) convex set that is spanned by a set of corners, takes its maximum (at least onc) of the corners.
18

---

Published in Transactions on Machine Learning Research (11/2022)
A.2 Proofs for Sec. 3.2
A.2.1 Proof of Prop.
Proof for Prop. 3 Intuitively clear that the results follows from combining o-additivity of measures with the change-of- of variiablle formula. Nonetheless we give a rigorous derivation here.
Keep in mind the following explicit specifications that were left implicit in the main part: In the main part we just stated to assume Lebesgue densities on A C IR", implicitly assume R" with the usual Lebesgue o-algebra as underlying measurable space, and that all parts As are measurable. Furthermore, to be precise, we assume differentiability of the Ik on the interior of their respective domain.
Recall that (Ax)a is countable partition of A, and we assumed diffeomorphisms g A A C Ā (diffeomorphic on the interior of A&) and that glA= = gk-
Note that based on assumptions, either is alrcady mcasurable, or, otherwise, can turn it into measurable function by just modilying it on a Lebesgue null set (the boundaries of the Ag), not affecting the below argument.
Let PA denote the original measure on outcome space A (restriction from R"), and PA its push-forward measure on À induced by g.
Then, up to null sets, for any measurable set M A,
Pa(M)
(25)
Pa(o-
(26)
PA(a-1(M n U A
(27)
&.
PA (MM) n Ax)
(28)
k
PA UU 9N (M))
(29)
k
PA (M))
(30)
/ M
[d (a))lpa (a))aa (m(Aa)) (A=))dā
(31)
[ 82 ( (ā))da
(32)
M (Ak))
where Eq. 31 is the classic chango-of-variable (also called transformation formula/theorent (Klenke) 2013
applied to the fush-forward measure of PA under gk. Therefore, the T density of PA i.e., Pa(a), is given by (a) (a)) Pa (a)).
E (Aa) det(] det(J,,>100)
A.3 Proofs and precise counterexample figure/MDP/agemns for Sec. 3.3
In this section we give all elaborations and proofs for the end-to-end versus test-time-only safety analysis of Sec. 3.3
For this sontion, keep in mind the following notation and remarks:
In the discrete setting of this section, the imitation cost function e etc. are vectors in the Euklidean space here; and, for instance, c PP or just cPP, stands for the inner product, the expectation of the cost variable c.
Rigorously speaking, is density.
19

---

Published in Transactions on Machine Learning Research (11/2022)
If not stated otherwise, || --1 refers to the 11-nrrm 111-
Keep in mind that for the total variation distance Drv have the relation to the norm
Drv(p. 4) = 2llp 1alp-ga gll1.
Keep in mind that, as the main text, letters safe imitator with safety layer already during training time), unsafe/ unconstrained trained imitator, and test-time-only-seee under the respective policies, and same for pP etc.
O stand for demonstrator, imitator (our fail-
imitator, respectively; and pD, P! pu, pup etc. denote the probabilities
A.3.1 Derviation of Rem. 1
The following derivation works along the line of related established derivations, e.g., the one for infinite- horizon GAIL guarantees (uu et al. 2020
Derviation of Rem. 7 Keep in mind that for any discrete distributions (s, a), (8, a), when marginal- izig out a, we get for Ps. Isi
lpp - -all
(33)
Σ p(() -((8]]
(34)
Σ p(s, a) {(s,a))
(35)
< ΣΣ ppss - a))
(triangle inequality)
(36)
= =llP,a - qs.all.
(37)
Now we have
1 - u 1
(38)
Σ cPl
cpD 81
(39)
81
=eT T pd
Σ
P!)
(40)
T
-T|o(p: PP-11
(Definition
(41)
<T]|c|/o11P - 1lll
(42)
<T|lclooolps, P
(Eq. 37
(43)
= (pb,a Pa.
(44)
A.3.2 Proof of Thm. 1 including elaboration of example (figure)
Elaboration of the example for the lower bound (Fig. 2 Here, let us first give precise version Fig. of the example in Fig. 2 that is used to get the lower bound in Thm. Instead of the exact Fig. we give an "isomorphic" version with more detailed/reallisic states and actions in terms of relative
position/ postiion/velocity /vlooelllllyy/o /wt///ooot////ccleaatiooo hwwccaaaaellllllaaeeeeaa
Specify the Markov decision process (MDP) and agents (policies) as follows, with imitation error p"= as
paramteter:
MDP:
20

---

Published in Transactions on Machine Learning Research (11/2022)
p==s
0,0,0 unsafe states/ disttance, occasionally front vehicle safe side strip, never visitied by unsafe imitator, hence not learned to recover
main road
(11,
visitied by unsafe trained imitator
side strip
(1.0
(0
Figure 4: More detailed (but essentially isomorphic) version of the example MDP LDP/agente from Fig. 2
The states (of the ego) are triplets (Az, Av, lane), where Az is deviation from demonstrator position, Av deviation from demonstrator velocity, lane lane (e for left, or for right). (The demonstrator is in a safe state.) There five possible states, all depicted in the figure, except for (1,, to keep the figure simple.
States:
Actions: The possible actions depicted arrows, with the action (acc, lane) written below the arrow, where acc means the longitudinal acceleration, and lane the target lane.
The longitudinal transition is the usual double integrator of adding acc to Ae, while, lateral-wise, action lane instantaneously sets the new lane (more realistic but complex examples are possible of course).
Tramsition:
The true demonstrator's cost 0 on the demonstrator state (0.0, and 1 on every other state.
Costs:
Horizon: form t to T, where consider T parameter (so it is strictly speaking family of MDPs).
Agents:
Demonstrator: Yellow car, always (p 1) staying at the depicted state, referred to as 5D (= (0, ()), at more than safe distance to front car (red).
Unconstrained trained imitator (blue): due to slight imitation error, it is sometimes (with proba- bility p0) accelerating, and if it accelerates, it necessarily reaches an unsafe state (after one more step, due to the "inertia" of the double integrator), but, as implied by the GAII. loss, always recovers (dashed arrows) back to true demonstrator state.
Safety-constraineer fest-time imitator (same, except for last action in brown): as the unconstrained imitator, it occasionally (p==)) ends up al rightmost, safe state, and then the only remaining safe action is to change lane to the side strip, where there was data on how to recover, getting trapped there forever.
Initialization - agent-depennent: While the overall agrument works as well for an agent-independent initialization, we do an agent-specific initialization, since simplifies calculations substantially. At. 1, for the demonstartor, we let p(s)) have full mass on the demonstrator state sD, For the unconstrained imitator, p(s)), take the stationary distribution under the induced Markov process, which is 1-33 (1, (,, where the first component means the demonstartor state P..
Proof of Thm. Keep in mind that we will occasionally use upper case letters like St, As, etc., to refer to the actual random variables of state and action, etc., distinguishing them from the values se, at that those random variables can take.
Proof for Thm. 7 Lower bound part:
21

---

Published in Transactions on Machine Learning Research (11/2022)
Keep in mind the counterexample construction above, in particular its deviation parameter 6, to which the following arguments refer. Tet 8D, ,a denote the state and action that the demonstrator is constantly in.
Construction of o; implication Drv(ØD, , s:
By construction, we have (PsP,aP) 1, while for the unconstrained imitator, p (recall that (s) is the time-average over the state distribution, which we took as the stationary one for the unconstrained imitator, giving mass 1435 on s and 1 - is the action probability).
1+36 (1 - 5)
(psssaa))
1
46
1 + 35
+ 36
So, by symmetry, Drv(p", p²) ) is one half times twice this,
46
DTv(p ,p²) -
1 + 36
Additionally, it is easy to see that for 2 0820. 0,
46
S 46, and so
T+36
Drv(p ,0/) s 48..
(45)
Therefore choose
E, based on the given by assumption. This implies Drv ,p²) Se. Preperation of a bound statement we need later:
(46)
As preparation which we repeatedly need later, observe that there some constant 0, such that for all T 2 2, we have
k < (1+ -1 T , <e-
(47)
where here is the Euler number (exponential) usual, and for take, c.g., 1. To have a first hint why this holds, see that
(1 T
T c-
For the full argument, observe the following: First, observe that at T 2, we have (1+ = 1. Second, it is sufficient to show that the expression is monotonically growing, i.c., the derivative az (1 + - is positive for T > 2. But this is equivalent to d log((1 + ) = イ4 + log( m being positive, since log is a monotonic function. But the latter follows from the fact that always r log(1 + x) and then plugging in T-1 for x, yicldig T-1 2 log(1 + +-11)
log(
log(" 11-
Now, before going into the main proof parts, recall that want to show
1 - P
(48)
for constant indepentent of T.
We do so by considering the case where it is quadratic separately from where it is linear 20 Proof for the lower bound, case 8T < 1:
Consider the case 8T <
Note that construction different from behavior cloning analysis (Ross and Bagnell 2010 especially in that da need one separate starting state.
2010 Syed and Schapire
22

---

Published in Transactions on Machine Learning Research (11/2022)
By construction, at each fixed stage t, the probability that the test-time constrained imitator x² is not in the demonstrator state is the summed probability of not deviating from s for & times, k S 1, and then deviating once, i.e.,
(S Σ 5(1-))--1
(49)
We want to bound the term (1 - 8)h-1 from below, show that the quadratic bound of Eq. 48 holds under the current case 8T < 1.
We have, for any h v T,
(1 (1-8)* ( (1 (1- "--
/ k
(50)
where the first inequality holds because we assumeed 8 S 7 and so 1- 8 2 1 - 7. and the second one because always & < T and third is Eq. 447
Therefore Eq. 49 can be bounded from below by
8k lōk.
(51)
Now we get, with the cost vector č (i.e., the safety cost function c, but making explicit it a vector since we are in the discrete case) being in the demonstrator state, and || elsewhere,
0 r
(52)
Σ (P) - -P!))
(53)
Σ 2(p (S: + -))]
(54)
Σ(tor) 1|0|
(Eq. 51 etc.)
(55)
dnl| 00 Σ
(56)
6x O T
(57)
for some Ks' (that absorbs both, & and the deviation between T and Ee L.
Proof for the lower bound, case 8T > 1:
First note that, alternatively to the previous deviation, we can also write (O sP) as the complementary probability of test-time constr imitator not having deviated from the demonstrator state sD so far, i.e.,
( + -1 21 1 111111110 T
(58)
since in the current case, 8T > and so 8 > $ and 1 1 d < 1 $ and so (1 -1-00 8)¹ < (1 4)² and (1 5)' > 1 - (1 2
Now, for 2 T. get,
(1 - h1 -- (1- , =(1 (1+ s <1,
(59)
where the second last incquality is Eq. 47 So (1 - 4 strictly below and bounded away from 1, and therefore Eq. (58) is uniformly strictly above and bounded away from 0, i.e., (S, # sP) is greater x" for 2 T.
23

---

Published in Transactions on Machine Learning Research (11/2022)
Then
10 r
(60)
Po )
(61)
Σ
(p (S: + -))[
(62)
Σ
p0(S, # s 3/
(63)
Σ
R" |0|
(64)
T
||
(65)
T 80.
(66)
Proof for the lower bound, final remarks:
is given by taking the minima of the above k's and conbining it with the relation Eq. 446 Upper bound part:
In what follows, P stand for probability vectors/matrices slightly overriding notation, and Psys for the transition probability (corresponding to f plus potential noise).
First obscrve that generally (here stand for probability voctors/matricos, slightly overriding notation),
A411 1|P PD || Siz1lli -1P8/sPP. P
(67)
(68)
IPSIsPS. PO PS PO PD PD
DD PD PS.
(69)
|PSS P.. (PS P
(70)
s p (P P1 + (PS S P
(71)
First consider the first term Eq. 1, bound it as follows:
We can generally, just since the 1-norm of any stochastic matrix is
| (P) P..) < [P 11 A, = 14,
(72)
(73)
Regarding the second term in Eq. (71) we have the following way to bound it.
Let S denote the subset of the S of states where (s(s) has support, and, as in the main text, 0 is the minimum value of (()) on S. Then
24

---

Published in Transactions on Machine Learning Research (11/2022)
Σ>
| (-(s) x (1s))
(74)
SEB
-V
Σ
T (als) - क (a|s)
(75)
$55,0
Σ
( (als) n" (a|s)
(76)
8,S,a
Σ
(s)) (als) x (a|s)
(77)
Σn
T (acas)) (s) x" (als)p?(ss)
(78)
(79)
(a (s5))) (s)s)
(80)
3
Σn
((cls)) (s) - x" (ab) (s))+ (8) x (als)p (a)s))((s))
(Iriangle inequality)
(81)
3,
((casspp (s) x (als)p + (s) - (s))?
(82)
ΣN (als)) D (8) x x (als)p 1 (8) ( (8) (s)
(83)
=I -Ipp5 Pa. 11 + 1pp - ph1l ll
(recall definition p)
(84)
22 + 25
(by assumption and Eq.
37
(85)
in particular
max se8
|| P(1s) -= (+1)]l S 4e/v.
(86)
Therefore
- 111 max || (+1s) *" (-1s)) S 4 ".
||
-PU a|sss Palsi
111
|
(87)
eES
D where the first equation is just a rewriting (note that here, Tafels etc. denote matrices (transition matrix),
while (-1s) etc. denotes a vector (probability vector)). Note that this also implies the same bound for the -ossttimm--o imitator, i.e.,
48 4 111 S
|
Palel
(88)
for the following reason: only the deviating mass between D and U that lies actions where D does not have support can be redistributed by the safety layer (because we assumed that D is safe, and hence those actions are safe and are not affected by adding a safety layer, based on our assumption about the safety layer). But this deviation mass already lies where it has the maximun effect on the norm (namely: where D does not have any mass at all). So redistributing it will make the deviation not bigger.
Furthermore we have, just by the definition of the conditional probability matrix Ps.A|S
(P.SS PSAAIs) II(PA) A|S PR
(89)
and the same holds when restricting the state to any subset, in particular $.
25

---

Published in Transactions on Machine Learning Research (11/2022)
Now, finalize argument also bound the second term in Eq.
71
observe
[ - ps) P
(90)
|[(5)115 - P 11 (since S is the demonstrator support)
(91)
& |1 1 S:1s
(92)
( S.A|8| -P -PSSA >1111111 | 5.1g
(93)
< |S | S.A Siş PS. S| |11 |1.1| |l
(94)
= || 1llaal////ASS A|S|s - s lla PS 111
(Eq. 89
(95)
4-
1 11- 1
(Eq.
88
1-norm of stochastic matrix/vector /ector is 1).
(96)
Coming towards the end, observe that plugging Eq. and 96
together gives
4
1
A
Therefore
A. Σ Arti - Dr S
4s
Then (keep in mind that we assumed that the reward depends only on the state)
100 - v = Σ ( - -P?)) cc
(97)
$ Σ [PS.. 11
(98)
|||| Σ A.
(99)
|
Σ V
4F
(100)
4 T
|
(101)
00
1
Remark 4 (Remarks regarding Thm. Q and proof). Some considerations:
Why do have this "min" lower bound in Eq. of Thm. 1 and not just a purely quadralic one? Note that in the above proof, if the case 8 > $ holds, then 8T > 1, but the mazimum deviation between imitator and demonstator cannot be larger than the imitator constantly being at a state differrnn from the demonstartor with probability 1, i.c., can asymptotically not be larger than T||c]loo (which is then smaller than c in this case).
Note that the theorem formulation is about capturing all possible scenarios (within our overall set- ling), and thus also accounts for the "worsl-case" ones. In practice depending on the specific scenario, of course things may be "better behaved" for the test-time sime-onny-safete opproach than the (quadratic) error concluded by the theorem.
B Additional background on GAIL cost and training
Overall we use (Wasscrstein) GAIL, an established methodology, for imitation loss and training in our approach. The rough idea of this was already given in Sec. 4.2
26

---

Published in Transactions on Machine Learning Research (11/2022)
For the full account details of (Wasserstein) GAIL, refer the reader to the original work (Ho and Ermon 2016; Xiao et al. 2019). Here let us nonetheless summarize some background on GATL cost function and training, and comment on the parts relevant to our approach. (Additionally, some impelementation details on the version we use can be found in Sec. and appendix
B.1 Imitation loss
Let us elaborate on the GAIL-based (Ho and Ermon 2016 cost function. We do it more generally here to also include Wassestoin-GAII//GAA
The reason why we consider using the Wasserstein- Xiao al. (2019) is the following: Due safety constraints, if the demonstrator is unsafe, we may deal with distributions of disjoint support. Then we want to encourage "geometric closeness" of distributions. But this is not possible with goometzy-agnostic information-theoreiic distance measures.
To specify the imitation cost e that we left abstract in Sec. 2 and 4.2
let
c(s,a) = ((2(,a),,
(102)
e2) arg max D Σ ei (Se, (c)) Ex E e2(())))))
(103)
where the arg max ranges over pairs (e1,e2) of bounded functions from some underlying space of bounded functions [Xiao et al. 2019), for which, besides Eq. (103), the following is required (Xiao et al. 2019
(x) c2(1) s 6(2, v).
(104)
for some underlying distance 8. This condition is referred to Lipschitz regularity. e1, e2 called Kan- torovich potentials.
As classic example, when taking e1 (s, == log(1 D(s,a)) a)) and e2(s, = log(D(s, a)), for some function D, then this exactly amounts to the classic GAN/GAIL formulation with discriminator D.
B.2 Remark on Training and the Handling of the State-Dependent Safe Action Set
Regarding the policy optimization step (c) sketched Sec. 4.2 note that: For each sampled state st. x 1. (als;) implicitly remembers the safe Aţ, such that also after any policy gradient step its mass will always remain within the safe set. Note that for this work, it can be a problem at some point we took safe fallback action (Sec. 3.1] and thus only know singleton safe set (and is not function of current state only). Since this is rare, it should pose little problems to training. Rigorously addressing this is left to future work.
B.3 Comment on probability measure underlying the expectation
Observe that in Eq. 12 we take the expectation under the measure induced by dynamic system plus pol- icy, over the summed future imitation cost. Alternatively, sometimes the expectation is taken under the Lime-averaged stale-action distribution p(s, a) (Sec. 3.3), over the imitation cost. As far as we see, both formulations seem to be equivalent, similar as discussed in (Ho et al. 2016) for the discount- factor-basee formulation.
C Additional details of experiments and implementation
Here we give some additional details for our experiments and implementation of Sec. These details are not necessary for the rough idca, but get the detailed picture of these parts.
Implementation code is available at:
27

---

Published in Transactions on Machine Learning Research (11/2022)
C.1 Additional architecture, computation and training information
Details of policy architectures:
For the Gaussian policy (i.e., parameterixing mean and covariance matrix), we take two hidden layers each 1024 units.
As pre-safe normalizing flow policy, we take 8 affine coupling layers with each coupling layer con- sisting of two hidden layers a 128 units.
As discriminator, take neural net with two hidden layers and 128 units each.
As state feature CNN, we take a ResNet18 applied to the abstract eerds-eye-vier image representa- tion of the state (Chai al. 2019).
For the custom neural nets, we use leaky ReLUs as non-linearities.
The data set (scene) consists of ~ 1500 tracks (trajectories), of which we use 300 as test set and 100 as validation, and the rest as training set.
One full safe set computation with some limited vectorized parts takes around 1.5s standard CPU. We believe vectorixing/ veeloriiiing/parrallliiiiggg parallelizinnn more of the code can further reduce this substantially.
For training, we use GAIL with training based on soft actor-critic (SAC) (Kostrikov et al. 2018 Haarnoja
ct al. 2018).
For the discriminator and its loss, we build on parameter clipping from Wasserstein GANs Arjovsky el al. 2017), and adversarial inverse reinforcement learning (AIRL) (Fu al. 2017).
C.2 Regarding safety guarantees and momentary safety cost
Regarding the fact that Prop. does not strictly cover FAGIL-E yet: We conjecture that, extending Prop. 2 guarantee can be given for the Lo0 setting even without convexity over all dimensions, simply by the loo norm being a minimum over dimensions and then in some way considering each dimension individually.
Regarding Lipschitz continuity of momentary safety cost: Note that, as briefly stated in the main text, the momentary safety cost our experiments Lipschitz. Intuitively, it is some form of negative (minimum) distance function between ego and other vehicles. Distance/com d collision. That is, d is Lipschitz continuous function, but d 0 is the boundary between the set of safe states and unsafe states. (Similar to the safe action set being the sub-zcro (i.c., w S 0) set of the total safcty cost w.)
momentarily safe, while d > 0 is
We believe that Lipschitz continuity a fairly general assumption for safety, since safety is often considered in the physical world. And in the physical world, many of the underlying dependencics are fact sufficiently continuous.
D Broader supplementary remarks
In this section, gather several further discussions that more broadly related to the results of the main part.
This section is not necessary to describe or understand the main part.
However, given that safe generative IL field that rather little explored, we feel it can be particularly useful to provide some further comments here that may help understanding and may serve as a basis for next steps.
28

---

Published in Transactions on Machine Learning Research (11/2022)
D.1 Further details on Sec. 3,1
Several broader remarks regarding safe set inference, which are not necessary to understand the core defini- tions and results:
A-temporally, Eq. can be seen as a Stackelberg game.
In Eq. 4
the others' maxima may often collapse to open-loop trajectories.
We use the general formulation where policies Ty can depend on t. This allows us to easily treat the case where we directly plan an open-loop action trajectory 01:r simultancously, by simply Te(s)) := az; for all 1, 8t-
The state set corresponding to our action set would be an "invariant safe set" (Bansal et al. 2017 7
Lipschitz/contimiin understanding is helpful also for other things: e.g., understanding the safe set's topology for Sec. 3.2
Our sample-based approach can also interpreted as follows: we can use single-action safely checkers (in the sense of the "doer-checker" approach (Koopman al. 2019)) oracles for action-set safety inference.
On Prop. 2 Open-loop is a restriction but note that we do search over all trajectories in II, D, so it is similar to trajectory-based planning.
Regarding inner approzimations of the safe set: For as little possible bias and conservativity, we need the inner approximation of the safe set to be as large as possible. In principle, could also just give finite set of points as inner approximation, but this could be very unflexible and biased, and injectivity for change-of-variable Prop. 3 would not be possible.
Regarding safety between discrete time steps: Note that our setup is discrete time, but it can directly also imply safety guarantees between time stages: e.g., for our experiments, we know maximum velocity of the agents, so we know how much they can move at most between time stages, and we can add this margin to the distance-based safety cost.
Small set of candidate ego policies, to simplify calculations: As an important simplification which preserves guarantees, in the definition/ innantiionevaluattion of safe set and total safety cost wy(s, a), we let the cgo policies range over some small, sometimes finite set II+1 C I441- of reasonable fallback future continuations of ego policies. In the case of autonomous driving (see experiments). 1T.I.T consists of emergency brake and evasive maneuvers (additional details are in Appendix D.1
A popular approach for trajectory planning/ cotimmizioooi is model predictive control (MPC) Bert- sckas 2012), so let us briefly comment on the relation between our trajectory calculations for safety and MPC: In a sense, MPC could solve the trajectory optimization, i.e., the "min part" of Eq. 4 So, to some extent, it is related. However, MPC would need one specific policy/ / dynamics for the other agents, while we just have a set of possible other agents policies (and take the worst-case/ sesst-caseaadveesaarii adveraarial case over this set). And MPC alone would also not give us a set of safe actions (which we need since we want to allow much support for the generative policy density possible), but only one action//rajeccoory
Note that the "adversarial" in the title of our work has the double meaning of "worst-case safety" and "using generative adversarial training".
Regarding the ego, note that the search over small set of future trajectories in the form of the "fallback maneuvers" (instead of an exhaustive pardd/optimization over the full coauning/trajeoollo space) can be seen simple form of motion primitives or graph search methods and related to "sampling based" planning approaches (Paden et al. 2016). Regarding the other perturatttsus,,sinns, one could also just consider small subset of possible behaviors, though do not do this in the based
current work since weakens guarantees of course. This would somewhat related to sampling. based methods in continuous game theory (Adam al. 2021 as well as empirical/onan oow.ee-bbceedd game theory [Tanctot et al. 2017).
29

---

Published in Transactions on Machine Learning Research (11/2022)
D.2 Further details on Sec. 3.2
Here we go more into detail on the construction of safety layer that are differentiable and give us an overall density, in particular (1) the challenges and (2) potential existing tools to build on. (See also Appendix D.3.2)
One purpose of this section is to provide further relevant background for future work safety layers that allow to have closed-form density/gret /grly//ggadnn-g--- -oannt-giive given this is rather new yet highly non-trivial topic (from the mathematics as well as tractability side).
D.2.1 Definition and remark
Let us introduce the topological notion of "connected" we use below.
Roughly, an open set in R" is called (path-) connected, if any two of its clements can be connected by a continuous path within the set; and simply connected these connecting paths are, up to continuous deformations within the set, unique.
For formal definitions we refer to textbooks, such as Komornik 2017
Remark on Def. Usually, parts A will be topologically simply connected sets,
D.2.2 Basic remarks on simplest safety layer approaches
Let us elaborate on the issue of designing safety layers, mappings A + A, in particular ones that are differentiable and give us an overall density.
Besides the more advanced approaches we discuss in the main text and below, let us also mention the two simplest ones and their limitations.
First, maybe the simplest safetly layer is to map all unsafe actions, i.., A A, to one safe action, i.c., one point. But this would lead to stronger biases and would lose the property of having overall (Lebesgue) density (at least the change of variables would not be applicable due to non-injectivity; and the policy gradient theorem would also be problematic).
Second, another simple solutions would be move/scale the whole into one safe open set, given the safe set contains at least one open set (which should generally be the case, e.g., using Prop. D. This in fact would be diffeomorphism
we could apply the change-of-variable formula. However, obviously this would be very rigid: the possible safe actions to take would then usually be very small part of the full safe set strong and usually poor bias. This is because, be aware that, also the actually safe parts of the action space would be re-mapped to the tiny safe open set. That is, it would force us to also move actions that are actually safe to new positions. And this would leave little space of designing more sensible inductive biases, as in the two instances we propose.
D.2.3 Simple versatility of piecewise diffeomorphism safety layers
In contrast to these overly biased simplest solutions from Appendix D.2.2 let us give an example of how piecewise diffeomorphisms give us more room for design. Note that he following is not meant as a safetly layer that should actually be usod, but rather as a simple argument to show the universality:
Remark 5. Piecewise diffeomorphic safety layers versatile: If a given safe set A contains at least some area (open set), then we can usually map A into A, simply by moving and scaling the unsafe areas into safe ones, while leaving the safe actions where they are.
Elaboration of Rem. 5. Assume the safe set is given as the subzero set of some continuous function h A + R. i.c., A h ((-20, 0)), which is the case, e.g., under Prop. and that it contains least some open set. Let. B be some (any) ball in this open set.
30

---

Published in Transactions on Machine Learning Research (11/2022)
Here is the simplest construction: Just take A1 := ((-oc, 0)) and A₂ := h ' oo)). Let 91 (on A1) be the identity. And let 92 (on A2) be a shrinking, such that A2 has less diameter than B, and subsequent translation of A2 into B.
Another construction, which has a better "topological" bias in that it tries to map unsafe parts into nearby safe parts works as follows:
If Á is the subzero set of continuous function, then the unsafe set open. So it can be written as the union of its connected components, and each connected component is also open. Therefore, in each connected component k, there is at least one rational number (or, in higher dimensions, the analogous element of Q"), so there are at most countably many of them.
So define 9k with domain the component k, and simply being a translation and scaling that moves this component into nearby open part of the safe set (this is where it becomes more appealing in terms "topological" bias), or, as default, into B.
Let 9 be defined by the "union" of these Jk. and on the rest of A, ie., the safe set A, let it simply be the identity.
forddddsstm--ddty--eeeeee------ D.2.4 On general existence, construction/biases and tractability of closed-fowe foosed-form-oo deneidy- preserving differentiable safety layer
Here we add some notes on the general discussion of safety layers with closed-form densities, beyond the particular approach we take in this paper.
There could be many ways to construct safety layers with closed-fore density, and it is hard, especially
within the scope of just this paper, to get general answers on questions of (1) possibility and (2) tractable construction of such safety layers. Especially since there may be trivial solutions (see Appendix D.2.2 which are not satisfactory terms of rigidity/ /bias though. So let us narrow down the problem to try to make at least some basic assertions.
First, simple erample of impossibility when using pure diffeomorphisms: already for topological reasons, if A is connected but Á not, then no such safety layer can exist that is bijective onto Á.
Nonetheless, overall the starting point in this paper is the change of variables, or the piecewise change of variables we use. This implics that we extensively need diffeomorphisms to build our safety layer on. And this implies that we need homeonorphisms,, when relaxing the differentiability to continuity.
Regarding the shapes of (un-)safe sets, or their (inner/outer approximations, general answers would be desirable too, but particularly here we focus on polytopes and hyperroctanglos, since for those are also typical results of reachability analysis etc. (Sidrane el al. 2022
Here are some basic concepts and results from topology and related areas. We only give an idea, while detailed formalities are beyond the scope of this paper.
In 2 there is a lot of relevant theory from complex analysis, which studies holomorphic, i.e., complex differentiable functions (another way to state it is that they are conformal, i.e., locally anglo-preserving mappings; for detailed formalities see, c.g., (Lutcberget) 2010)). Biholomorphic (i.e., a holomorphic bijection whose inverse is also holomorphic) implies difleomorphie, so this is relevant for us.
For instance, the Riemann mapping theorem (Luteberget 2010 tells us that such a biholomorphic mapping exists from A C IR2 to A, if A is simply connected open set in IR² (assuming per se that A is a box, i.e., simply connected as well). While this could be a powerful result for safety layers, the issue comes with tractability. Often, Riemann mappings are defined just implicitly, based on some variational problem, or some differential equation problem, whose solution can be arbitrarily complex to calculate. More tractable (though it still remains unclear how to make them fully include:
tractable) concepts and results [uuteberget, 2010)
31

---

Published in Transactions on Machine Learning Research (11/2022)
Sehwarz-Cristooie mappings special case for polytope domains;
sphere packing- based algorithms for approximating Riemann mappings via combinatorical so- lutions finite graph of the problem, and then extrapolation to the continuous original problem.
Note that it is easy to see (since holomorphic functions are globally uniquely determined from any local neighborhood, based on them being fully described by their Taylor expansion around any single point) that holomorphic functions are a quite rigid function class for safety layer though: for instance, there cannot be a holomorphic function which would be the identity on the safe set, but the non-indentity outside the safe set.
Adding the negative, i.e, non-existence side, often the non-existence of safety layers or parts of them can be proved using topological arguments (often invariants), e.g., that the domain and co-domain do have to have the same connectivity property (connected, simply conntected, etc.), or other based on homology.
There are also positive, ie., existence results, from topology, and very general ones. For instance, if two open subsets of IR" are contractible and simply connected at infinity, then they are homcomorphic (i.e., continuous bijections whose inverse also continuous) to each other 22 This, even though not sufficient, is strong necessary requirement for being diffeomorphic of course. Also convexity be helpful
D.3 Details on FAGIL method Sec. 4
in particular its safety layers
D.3.1 Regarding safe set inference module
Note that, in principle, due to modularity, many safety approaches can be plugged as safety modules into our overall method (Fig. 1. This includes frameworks based on set fixed points (Vidal al. (2000). Lyapunov functions (Dnnti al. 2021a), Hamilton-Jacobi type equations (continuous time) (Bansal al.) 2017),
Responsibility-Sensiile Safety (RSS) Shalev-Shwartz et al. (2017).
A fundamental problem in safe control is the tradc-off between being safe (conscrvative) versus allowing for enough freedom to be able to "move at all" (actionability). Ours and many safe control frameworks build on more conservative adversarial/ wwo.si/twwwwsssseeeeee reasoning. RSS's idea is to prove safety under the less conservative (i.e., "less worst-case") assumption of others sticking to (traffic) norms/ cormscconventions, and collisions happen nonetheless, then least the ego is "not to blame".
D.3.2 On the safety layers an alternative, weessae--robbabiity-bee safety layer
Besides the safety layer instance we described in Sec. 4.1 which can be termed listance-based. here is another sesuee-rrobbblitty
instance of a piecewise diffoomorphism safety layer g:
(a) On all safe boxes k i.e., A A, g is the identity, i.e., we just keep the pre-safe proposal â. (b) On all unsafe boxes k, 9k is the cnnslation/scalingg to the box where the pre-safe density pa has the most mass (approximately). Alternatively, in (b) a probabilistic version (b') can be used where 9k translates to safe part A₂ with (approximate) probability proportional to Pa on A
Intuitively, the version with (b') amounts to a conditioning on the safe action set, ie., a renormalization (when letting the box size go to zero).
Remark: Note that in this work only considered these two specific instances of piecewise diffeomorphism safety layers the pressufe-probbbiiitybbbsse and the ristance-based one while many others are imaginable.
23 httpp:://aate www.kssttttcccccccccooooomc htt.://cwccccccaa...ooo///////// papere/Convex0ppen.pp
http://relaunch. uni mni-bonn.dde www..ddettleennnnngecchhae
32

---

Published in Transactions on Machine Learning Research (11/2022)
D.3.3 Illustrative examples of piecewise diffeomorphisms for safety layers
Let us give some illustrative examples of piecewise diffeomorphism safety layers, see Fig. 5 This includes an example of our distance-bused,, grid-based safely layer described in Sec. (The probability- based, grid-based version from Appendix D.3.2 works in related way, but choosing the targets A based on their pre-safe probability, instead of their distance to the sources Ag-)
Note that in the grid-based example, here we just need translations, because all parts (rectangles) of the partition are of the same size, while in other cases, some parts (e.g., if there is boundary not in line with the grid) may have different sizes, and then we also need scaling.
D.3.4 Computational complexity of the safety layer
We here give a rough analysis of the computation complexity of piecewise difleomorphisms (Sec. 3.2 and thus the safety layer, as part of the fail-safe imitator policy x - (ā]s)) (Sec. 4. and their gradients. Let us look at Eq. (6) and recall the structure of the fail-safe imitator with safe action and pre-sale action from Fig.
To calculate safe density Pa(ā) of safe action ā, given the pre-safe density Pa of the pro-safe policy, this is sum (Eq. b over the relevant parts As of the partition (As)a; and then each k-th summand is the change- of-variables formula applied to the diffeomorphism
and pre-safe density pa, where the determination of 9& may itself require some calculation (based, e.g., on distances or pro-safe densities of the parts).
So, essentially, the complexity is at most the number of parts in the partition (A&)x times the complexity of calculating the change-of- -aaiaell--varialles formula (and determination of 9a if necessary, see instances below).
Let us give some instances of this:
When using any sort of general invertible (normalizing flow) neural net (Papamakarios al. 2019) transformations 9k, then we inherit their complexity for each summand of Eq. (6)
For our proposed safety layers, e.g., the grid- and distance-based one we describe in Appendix D.3 the number of parts in the partition is around 100 (based on a 10 times 10 grid). And each ga is a Translation/ccaline to a target part, yielding a simple scaling factor as change-of-variables formula (the determination of the target part, i.e., of 9k requires, for each state, one single run over all pairs of parts the partition to get. the distances; on this side, the probability-based safety layer version we describe in Sec. is faster, since we do not have go over all pairs, just all single ones).
To calculate the gradient of (als) w.r.t. 8 this analogous, where we simply can drag the gradient into the sum of Eq. ( and the gradients of the summands are given by the gradients of the pre-safe policy that is being used (i.e., for instance conditional Gaussian normalizing flow), times the factor =(,)))),(0)) which is constant w.r.l. 0 (in the our distance-based safety layer). So here the complexity is essentially number of (at most) all parts the partition (As)s, times complexity gradient calculation for pre-safe policy.
D.3.5 Invariant safety on full sets, not just singletons
Recall that for the general method we used singleton safe sets as backup to guarantee invariant safety (end of Sec. 4.1
It is important to emphasize though that in slable linear systems it can in fact often be guaranteed that always full safe box A& is found. And then the extension of memorizing safe fallback singleton is not necessary.
The idea towards proving this is as follows: The hard part is that we have to check safe future trajecotries not just for individual trajectories, but where at each stage, any action out thes safe set can be taken. But these sets can be modelled as bounded perturbations of individual actions. Then stability arguments can show us that the error (deviation from a single safe trajectory over time) can be bounded, and then we can recur to planning individual trajectories plus simple margins.
33

---

Published in Transactions on Machine Learning Research (11/2022)
Setup: Assume the full action set A is given by the set enclosed by the gray frame....
And the unsafe actions A A\A A are given by the red subset of the full action set.
First example piecewise diffeomorphism: The partition (As)a has just two parts (l.hs.)): A is the safe set euclosed by the green line, and A2 the unsafe set, encircled by the blue line. The piecewise diffeomorphism g transforms these parts follows:
The diffeomorphism 9i A is just the identity. And the diffeomorphism Oz maps the unsafe Au to the blue polygon the boundary within the safe set (r.h..). Note that such a diffeomorplisu exists by the Riemann (or Sehwarz-Christofee mapping theorem, or, in this simple case, also by convexity (see our discussion of all these concepts in Appendix D.2.4). Together, and ga form our piecewise diffeomorphism on A A1UA2.
Second example piecewise diffeomorphism: Here, we consider our gridd partition of the full action set, i.e., complete regular tiling of the action set with rectangles A&, partition (Aa)e. We only illustrated the individual rectangles At for the unsafe area, in blue, while for the safe area only drew the outer boundary, green (l.h.s.). The piecewise dif- feomorphism transforms these parts as follows:
On all safe Ae; the diffeomorphism gk is simply the identity. And on all unsafe A (meaning fully or partially unsafe), ga the shifting to the most nearby safe rectaugle A.. Those safe target rectangles A, are drawn in blue (r.h.s.). Together, these gu form our piecewise diffeomorphism g the full A. Note that this an example our distance-basen safety layer described in Appendix D.3.2
Figure 5: Examples of piecewise diffeomorphism safety layers. Top row: setup. Middle and bottom row: two examples.
34

---

Published in Transactions on Machine Learning Research (11/2022)
D.4 Further related work and remarks
Beyond the closest related work discussed in Sec. 1 let us here discuss some more broadly related work.
Boborzi et al. (021]) similar to us propose a safe version of GAIL, but there are several differences: they build on a different safety reasoning (RSS), which is specific for the scope of driving tasks, while our full method with its worst-case safely reasoning is applicable to general IT, domains, and they do not provide exact densitiss/gaadients of the full safe policy as we do.
Certain safety layers Donti et al. 2021a Dalal et al.) 2018 are a special case of so-called implicit lagers
(Amos and Kolter 2017 Amos et. al. 2018 El Ghaoui et al. 2019 Bai et al. 2019 Ling et al.
2018 2019)
which have recently been applied also for game-theoretic multi-agent trajectory model learning (Geiger and
Straehle 2021p, ,, including highway driver modeling; robust learning updates in deep RL (Otto et al. 2021
and learning interventions that optimize certain equilibria in complex systems Besserve and Schölkopf (2021
Worth mentioning is also work on safe IL that builds on hicrarchical/ /hybrid approaches that combine imi- fation learning with classic safe planning/trajeeloon tracking (CCen al., 2019 Huang et al.) 2019).
Besides GAIL, which only requires samples of rollouts, one could also think about using fully known and differentiable dynamics (Baram et al. 2017 for the training of our method.
Also note reachability-based safe learning with Gaussian processes (Akametalu et al. 2014
At the intersection of rafftt/reachabiiiity and learning, also work on outer approximations based on verified neural net function class properties connected Sidrane et al. (002)).
Beyond the paper mentioned in the main text, there are several papers fail-safe planning for autonomous driving (Magdici and Althoff 2016 Pek and Althoff 2018 2020).
Convex sets, various kinds of them, have proved a helpful concept in reachability analysis and calculation, SOC,, ogg, (Guernic and Girard 2009) (their Section gives an overview).
Remark 6 (On the meaning of the term "fail-safe"). The term "fail-safe" seems to be used in varying ways in the literature. In this work, in line with common uses, we have the following intuitive meaning in mind: We have an imitation learning component and a worst-case planning component in our system (the fail-safe imitator). The pure IL component the pre-safe policy - can in principle always fail in the sense of leading to "fuilure", ", i.e., momentarily unsafe/collisoon /collision, states, since it does not have strong guarantees Specifically, this would happen when it would put all mass an action that leads to collision! But having our worst-case fallback planner plus the safety layer as additional component in our system, we make sure that, even if the IL component fails, nonetheless there erists at least one safe action plus future trajectory. This makes the system safe against a failure of the pure IL component, and this is what we mean by fail-safe. This is similar to (Magdici and Althoff (2016) who use "fail-safe" in the sense that if other agents behave other than their "normal" prediction module predicts (i.e., the prediction module fails in this sense), then there is nonetheless a safe fallback plan. All this also relates to notions of redundancy.
25
24There also be some confusion because "fail" can be used in senses: in the sense of restricted failure, that can be mitigated and still be safe though; or in the sense that "failure" mcans "collision" " or "momentarily unsafe" state. Note that for Gauss well flow policies, we have the conceptual issue here that they have mass everywhere; and in this probabilistic setting is hard say what precisely "fall" would be; however, one can as well plng pre-safe policies into our approach that do not have support everywhere, and then the aforementioned holds rigorously.
35


Reviews:
[{"review_id": "WB7v2O4y49", "reviewer": "Reviewer_WeWp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The approach seems novel and interesting from a theoretical perspective\n- Empirical results show that the approach performs well compared to alternatives\n- Good theory and visual example in Fig 2 of why the safety layer is important for training.\n\nWeaknesses\n- Many details are confusing and it is unclear how well this approach will scale to more complex problems\n- Missing some related work on safe IL and safe RL.\n- Unclear what the limitations of this approach are and when it should be used and when it is inappropriate.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a novel safe imitation learning algorithm by adding a safety layer on the actions to ensure that only safe actions are taken. The proposed approach uses GAIL-style training, along with a differentiable safety layer to train end-to-end. Results show that using the safety layer during training is better than only using it at test time. In a simulated driving environment, the proposed approach reaches good imitation learning performance while avoiding collisions.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Why is the total safety cost to go in Eq (4) not a sum over time. It appears to currently just pick out the least safe state in the future rather than a total cost. (critical)\n\nProp 1: Is the momentary safety cost d Lipschitz? It seems like in driving and other safety-critical domains a very slight change in state can be the difference between safety or collision. Please clarify and discuss when this assumption is likely to hold and when it will not (strengthen).\n\nI found the section on piecewise diffeomorphisms confusing. Is there a way to provide a visual example to help readers gain intuition? (strenthen)\n\nAlso, the implied density of y seems quite complex and compute intensive to calculate the gradient of. Can you provide more details on the complexity and scalability of the proposed approach? (critical)\n\nMissing important related work on safe and robust imitation learning and shielding for RL (critical):\n- Javed, Zaynah, et al. \"Policy gradient bayesian robust optimization for imitation learning.\" International Conference on Machine Learning. PMLR, 2021.\n- Alshiekh, Mohammed, et al. \"Safe reinforcement learning via shielding.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 32. No. 1. 2018.\n- Brown, Daniel, et al. \"Safe imitation learning via fast bayesian reward inference from preferences.\" International Conference on Machine Learning. PMLR, 2020.\n- Lacotte, Jonathan, et al. \"Risk-sensitive generative adversarial imitation learning.\" The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.\n- Thananjeyan, Brijen, et al. \"Recovery rl: Safe reinforcement learning with learned recovery zones.\" IEEE Robotics and Automation Letters 6.3 (2021): 4915-4922.\n\nOpen loop simulation means the agents don't react to changes in ego agent. Seems unrealistic, but necessary if just replaying observational driving data. Is there a different simulation or experiment that could be added to the paper? (strengthen)\n\nIf you can check the safety of actions, this seems to require a model of other drivers and the road, so why not just run MPC? Please clarify (critical)\n\nIn particular, I'm confused about how the total safety cost is computed in practice. It seems like a difficult optimization problem and it's unclear to me how this is done in the driving simulation and how generally it could be applied. (critical)\n\nThe safety fallback is confusing. It's unclear to me how you can fall back on a safe policy if there is no fully safe part of A_k. Doesn't that mean that there are no safe actions. This seems to contradict the fact that there is a fall back policy you can use. Please clarify (critical)\n\nPlease add a limitations section. Can you highlight failure modes of the proposed system? Maybe show what happens when the assumptions are violated? (critical)", "broader_impact_concerns": "It would be good to have more discussion about broader impacts. In particular, this paper focuses on autonomous driving and safety, so I would like to see some discussion of negative and positive effects of fielding systems like the one proposed in this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Laarwef27k", "reviewer": "Reviewer_d5hT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths. \n\nThe theory in the paper appears to be correct and the method proposed by the authors seems to perform well.\n\nWeaknesses. \n\nHowever, I have a major concern. Overall I found the paper to be written in an extremely confusing manner. Take, for example, the abstract of the paper.\n\n(i) [...] The safety layer is a “glueing together” of piecewise diffeomorphisms, with sum over change-of-variables formulas as density. [...] means nothing to the reader without having read the paper previously. \n\n(ii) [...] The safe action set (into which the safety layer maps) is inferred by sample-based adversarial reachability analysis of fallback maneuvers plus Lipschitz continuity or convexity arguments. [...] neither does this.\n\nA lot of comments are thrown around throughout the manuscript with little context or information to the reader. This makes it very confusing to understand what type of insight about their method the authors are trying to provide.\n\nFurthermore, the paper has an a lot of footnotes (24 in total), two remarks and a 6-page Appendix B titled 'Further Details'. If that many clarifications are needed, the paper should be better organized and explained.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work the authors propose a method for safe imitation learning which is numerically tested on real-world data.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I think the paper needs to be completely rewritten with a focus on clarity. As it currently stand, it is just too confusing to properly evaluate. Maybe it is just me, but I have read the manuscript multiple times and have yet to understand much of what the authors are trying to convey.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QpOSZQMxJs", "reviewer": "Reviewer_Hc2K", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* The claims seem correct\n\n* The presentation is mostly clear, however, it should me explicit at some points. For example, how are shift-and-scale transformations implemented? Let's say we have a grid with safe set [0,1[ and unsafe set [1,2[. How would the shift & scale move the actions from [1,2] to [0,1[? It would seem reasonable to shift every action to the closest action 0.99, but we would'nt have a diffeomorphism. So should we transform [1,2] to, for example, [0.98, 0.99]? If I understand correctly the paper proposes to shift to whole [0,1[, but mapping to 0 seems unnecesary and suboptimal.\n\n* The main weakness is that I dont see who would be interested in the findings of the paper, given that method makes extremely strong assumptions (very low-dimensional action space to allow for discretization, linear dynamics, convex safety sets). I dont see how the method or aspects of it (aside the general concept of using a safety layer) could be applied to a real-world application.\n\n* The empirical evaluation is weak due to the simplicity of the considered environment. Furthermore, the work by Cheng et al. could be used as a baseline.\n\n\nCheng and Li Shen and Meng Fang and Liu Liu and Dacheng Tao, Lagrangian Generative Adversarial Imitation Learning with Safety\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a method that aims to prevent unsafe actions during adversarial imitation learning by adding a differentiable safety layer,  which projects potentially unsafe actions to safe actions, at the end of the stochastic policy. \nThe method discretizes the action space into hyper-rectangles and tries to prove safety for each block under the assumptions of linear  dynamics and Lipschitz-continuity. More specifically, the paper proposes two methods: FAGIL-E evaluates at each corner, whether a best-case policy would encounter unsafe states, and FAGIL-L evaluates the safety-cost-to-go (negative for safe states) on the center actions and uses a Lipschitz argument. The safety-cost-to-go for given state-actions can be evaluated by solving a min-max problem that optimizes the remaining action sequence for worst-case dynamics.\nIf the input-action to the differentiable safety layer is in an unsafe block, a shift-and-scale transformation is performed to map it to the safe block that has the highest probability under the current policy. As shift-and-scale is a diffeomorphism, the probability density of the transformed action can be evaluated for learning the policy with GAIL.\n\nThe contribution of the submission are\n1) A method for ensuring safe actions during imitation learning is proposed that works for low-dimensional, linear systems and convex safety sets.\n2) A theorem is provided that the imitation cost scales linear with T when the safety layer is used during training and learning, and quadratic when it is only used during deployment.\n3) The method is evaluated on a simple highway driving test problem (point mass, double integrator, two actions: one for accelerating in x, one for instantaneously switching the lane) and compared to  GAIL, RAIL (adding collision penalties to the learned cost function) and a variant that uses the safety layer only during deployment.  ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "* The feasibility of the method for problems with higher dimensional actions (e.g. 5-7) and nonlinear dynamics should be achieved / shown.\n\n* Additional comparisons, e.g. with the method by Cheng et al. should be considered.", "broader_impact_concerns": "I do not think that the paper requires a broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper deals with safe imitation learning, through safety layers. The authors claim that training the imitative agent with a safety layer is more efficient than adding the safety layer only at test time, which is supported by both theoretical (Rk 1 and Thm1; linear in T upper-bound vs quadratic in T lower-bound, roughly) and empirical (on safe autonomous driving) evidences. The safety layer is a hand-crafted part of the policy network, and should be differentiable for being considered at train time. For designing this layer, the authors justify checking the safety of a finite sample of actions using eg a Lipschitz argument (Prop 1), and use piecewise diffeomorphisms (Prop 3) for both differentiability and ease of design.

Overall, the reviewers found the approach to be technically sound and performing well on the proposed experiment. Yet, they raised concerns about the clarity of the initial submission and its significance (notably due to the lack of scalability of the specific instantiation of the safety layer considered in this paper). The authors proposed a revision which improves the clarity and discusses/addresses the limitations in a better way (notably by making them clearer).

After rebuttal, revision and discussion, all reviewers lean toward accepting the paper, I thus recommend acceptance. The paper does have limitations (eg, the practical safety layer considered here might not be very scalable), but they are properly discussed, and the authors make a good point in advocating for considering the safety layer already at train time for imitation learning, both from theoretical and empirical viewpoints. The considered empirical setting (safe autonomous driving), even if of low dimension, is not obvious and is of practical interest. 
Decision: Accept (poster)