# LiMIIRL: Lightweight Multiple-Intent Inverse Reinforcement Learning

Aaron J. Snoswell
School of Information Technology and Electrical Engineering
The University of Queensland
<EMAIL_ADDRESS>
&Surya P. N. Singh
Intuitive Surgical
<EMAIL_ADDRESS>
&Nan Ye
School of Mathematics and Physics
The University of Queensland
<EMAIL_ADDRESS>

###### Abstract

Multiple-Intent Inverse Reinforcement Learning (MI-IRL) seeks to find a reward
function ensemble to rationalize demonstrations of different but unlabelled
intents.

Within the popular expectation maximization (EM) framework for learning
probabilistic MI-IRL models, we present a warm-start strategy based on up-
front clustering of the demonstrations in feature space. Our theoretical
analysis shows that this warm-start solution produces a near-optimal reward
ensemble, provided the behavior modes satisfy mild separation conditions. We
also propose a MI-IRL performance metric that generalizes the popular Expected
Value Difference measure to directly assesses learned rewards against the
ground-truth reward ensemble. Our metric elegantly addresses the difficulty of
pairing up learned and ground truth rewards via a min-cost flow formulation,
and is efficiently computable.

We also develop a MI-IRL benchmark problem that allows for more comprehensive
algorithmic evaluations. On this problem, we find our MI-IRL warm-start
strategy helps avoid poor quality local minima reward ensembles, resulting in
a significant improvement in behavior clustering. Our extensive sensitivity
analysis demonstrates that the quality of the learned reward ensembles is
improved under various settings, including cases where our theoretical
assumptions do not necessarily hold. Finally, we demonstrate the effectiveness
of our methods by discovering distinct driving styles in a large real-world
dataset of driver GPS trajectories.

##  1 Introduction

Inverse Reinforcement Learning (IRL) methods search for a reward function to
rationalize demonstrated behaviour [35]. However, in many cases, these
demonstrations consist of different but unobserved behavior modes. For
example, taxi drivers may choose different routes even when the pickup
location and the destination are the same, upon the passenger’s request to
minimize the cost or the time (Fig. 1, left). Main approaches to deal with
such multiple (unobserved) intent IRL (MI-IRL) problems are Expectation
Maximization (EM) [3, 31] or non-parametric methods [8, 1]. We focus on the EM
formulation, which requires the number of intents $K$ as a hyper-parameter,
but is computationally more practical. Unfortunately, EM algorithms easily get
stuck in poor local minima, and thus good initialization is often a subject of
algorithmic design and theoretical analysis [38, 4].

For MI-IRL, we similarly observed that the EM algorithm is prone to local
minima that may have good likelihood, but fail to learn good reward functions
for the demonstrated behaviors. To address this, we propose Lightweight
Multiple-Intent IRL (LiMIIRL), a simple warm-start strategy that constructs an
initial solution by clustering the demonstrations in feature space, and then
uses EM to improve the solution. Theoretically, we bound the error of the
clustering-based initial solution, which shows that the initial solution can
be near-optimal when the behaviors are approximately separable in the feature
space. To the best of our knowledge, this is the first provable performance
guarantee for an EM initialization in the MI-IRL context. Empirically, our
experiments show that LiMIIRL helps avoid poor quality solutions, and allows
terminating the EM loop after a very small number of iterations, significantly
speeding up the convergence of the EM algorithm as compared to random
initializations. These results show that the simple strategy of clustering in
the feature space can effectively help grouping demonstrations into clusters
with distinct reward objectives.

Another contribution of this paper is a performance metric for MI-IRL
algorithms (Section 4). Our metric allows direct comparison (without reference
to a dataset) between two sets of multiple-intent behaviors, each represented
by an ensemble of reward functions and is efficiently computable by solving a
minimum cost flow problem.

In the remainder of this paper, we present LiMIIRL with a theoretical analysis
(Section 3) and introduce a new MI-IRL metric (Section 4). We demonstrate the
effectiveness of LiMIIRL and analyse its sensitivity w.r.t. problem and
algorithm hyper-parameters on a new MI-IRL benchmark, which allows for more
comprehensive testing of MI-IRL algorithms (Section 5). LiMIIRL is also shown
to effectively discover distinct driving behaviours in a real-world dataset of
taxi driving trajectories (Section 6). We elaborate context in both the
background and related work (Sections 2 and 7). Our code is available at [URL
removed for blind review].

##  2 Background

Figure 1: (Left): Multiple behaviour intents in the _Porto_ driver behaviour
dataset. Taxi drivers going from the same pick-up location to the same
destination may choose very different routes. (Middle): An illustration of
Assumption 1 for $K=3,|\phi|=2$, when $\zeta=0$. Demonstrations not in cluster
$\mathcal{T}_{k}$ are shown to be at least some margin away from
$\mathcal{T}_{k}$ when projected onto $\tau\in\mathcal{T}_{k}$. When
$\zeta>0$, some trajectories in $\mathcal{T}_{k}$ are allowed to be closer to
cluster $k^{\prime}$ than cluster $k$ when projected on $\tau$. (Right): Our
ElementWorld MI-IRL benchmark is a gridworld problem that wraps around the
x-axis. The agent starts in the bottom-most row of the grid world and must
navigate to the top. While en-route, the agent prefers to visit states
matching it’s desired element.

We consider behaviours generated by one or more experts acting in some
environment. We model the environment as a partial Markov Decision Process
(MDP) $\mathcal{M}=\langle\mathcal{S},\mathcal{A},p_{0},T,\gamma\rangle$ with
state space $\mathcal{S}$ and action space $\mathcal{A}$, discount factor
$\gamma\in[0,1)$, starting state probabilities $p_{0}(s)$ and a transition
function $T(s,a,s^{\prime})=p(s^{\prime}\mid s,a)$. In MI-IRL, we are given a
dataset of demonstration trajectories
$\mathcal{D}=\\{\tau_{1},\ldots,\tau_{N}\\}$ collected when an ensemble of $K$
experts interact with the environment to optimize their individual reward
functions
$R_{k}(s,a,s^{\prime})\triangleq\theta_{k}^{\top}\phi(s,a,s^{\prime})$.
Formally, we assume each trajectory $\tau$ is sampled from
$p(\tau\mid\rho_{1:K},\pi_{1:K})=\sum_{k=1}\rho_{k}~{}\pi_{k}(\tau)$, where
$\\{\rho_{i}\\}_{i=1}^{K}$ are positive mixture weights, and each expert
$\pi_{i}$ is represented as a distribution on $\mathcal{T}$, the set of all
trajectories of length at most $L$. We work in the unsupervised setting, where
the trajectories are not labeled with the corresponding behavior mode.

Given a transition-based feature function
$\phi:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to\mathbb{R}$, we define
its extension to trajectories by
$\phi(\tau)=\sum_{t=1}^{|\tau|-1}\gamma^{t-1}\phi(s_{t},a_{t},s_{t+1})$, where
$\tau=(s_{1},a_{1},s_{2},\ldots,s_{|\tau|})$.

We use $\mathcal{D}$ to learn an ensemble of models
$p(\tau\mid\rho_{1:K},\theta_{1:K})=\sum_{k=1}^{K}\rho_{k}~{}p(\tau\mid\theta_{k})$,
where $\\{\rho_{1:K},\theta_{1:K}\\}$ are the parameters with each
$\rho_{i}\geq 0$ and $\sum_{i}\rho_{i}=1$, and $p(\tau\mid\theta_{k})$ is a
distribution on $\mathcal{T}$ with parameters $\theta_{k}$. The parameters
$\\{\rho_{1:K},\theta_{1:K}\\}$ are chosen to maximize the likelihood
$p(\mathcal{D}\mid\rho_{1:K},\theta_{1:K})$. The EM algorithm, first applied
to MI-IRL by [3], starts from some initial parameter estimates
$\\{\rho_{1:K}^{(0)},\theta_{1:K}^{(0)}\\}$, and then iteratively improves the
parameter estimates until convergence.

At iteration $t$, EM updates the parameters as follows

$\displaystyle u_{ik}^{(t+1)}$
$\displaystyle=\frac{\rho_{k}^{(t)}p(\tau_{i}\mid\theta_{k}^{(t)})}{\sum_{k^{\prime}}\rho_{k^{\prime}}^{(t)}p(\tau_{i}\mid\theta_{k^{\prime}}^{(t)})},$
$\displaystyle\rho_{k}^{(t+1)}$
$\displaystyle=\frac{1}{N}\sum_{i}u_{ik}^{(t+1)},$
$\displaystyle\theta_{k}^{(t+1)}=\operatorname*{arg\,max}_{\theta}\sum_{i}u_{ik}^{(t+1)}p(\tau_{i}\mid\theta).$

We say that a solution $\Theta_{t}=\\{\rho_{1:K}^{(t)},\theta_{1:K}^{(t)}\\}$
is $\epsilon$-optimal if
$\frac{1}{|\mathcal{D}|}\sum_{i}\sum_{k}|u_{ik}^{(t+1)}-u_{ik}^{(t)}|<\epsilon$.
Intuitively, a small $\epsilon$ indicates that the EM algorithm has more or
less converged to a local optimum.

##  3 The LiMIIRL Algorithm

Our LiMIIRL algorithm provides a simple way to generate good initial parameter
estimates
$\Theta^{(0)}=(\rho^{(0)}_{1},\dots,\rho^{(0)}_{K},\theta^{(0)}_{1},\dots,\theta^{(0)}_{K})$
by clustering demonstrations in feature space. The initial solution is
generated in three steps.

First, LiMIIRL runs a user-specified clustering algorithm on the feature
vectors of the training trajectories to obtain a partition
$\\{C_{1},\ldots,C_{K}\\}$ of $\mathcal{D}$. Second, LiMIIRL estimates
$\rho_{1:K}$ using $\rho_{k}^{(0)}=\sum_{i=1}^{N}u_{ik}^{(0)}/N$, where the
membership variable $u_{ik}^{(0)}=\mathbb{I}(i\in C_{k})$ denotes whether
trajectory $i$ belongs to cluster $k$. Finally, LiMIIRL estimates
$\theta_{1:K}^{(0)}$. We consider two ways to do this, mean initialization, or
Maximum Likelihood Estimate (MLE) initialization, given respectively by,

$\displaystyle\theta_{k,\text{Mean}}^{(0)}$
$\displaystyle=\Phi_{k}\triangleq\frac{1}{|C_{k}|}\sum_{\tau\in
C_{k}}\phi(\tau),$ $\displaystyle\theta_{k,\text{MLE}}^{(0)}$
$\displaystyle=\operatorname*{arg\,max}_{\theta}\sum_{\tau\in C_{k}}\ln
p(\tau\mid\theta).$ (1)

In our algorithm, $p(\tau\mid\theta)$ can be any single-intent IRL model, and
we experimented with the MaxEnt IRL model [41], Maximum Likelihood IRL [3],
and $\Sigma$-Gradient IRL [31].

Below, we provide a theoretical justification of why clustering in feature
space is an effective choice for initializing an ensemble of behaviours based
on the MaxEnt IRL model, which has exact and computationally efficient
solution methods available [36]. Specifically, this entails choosing
$p(\tau\mid\theta)=q(\tau)e^{\phi(\tau)^{\top}\theta}/Z(\theta)$, where
$q(\tau)=p_{0}(s_{1})\prod_{t=1}^{|\tau|-1}p(s_{t+1}\mid s_{t},a_{t})$, and
$Z(\theta)=\sum_{\tau^{\prime}\in\mathcal{T}}q(\tau^{\prime})e^{\theta^{\top}\phi(\tau^{\prime})}$
is the partition function.

Interestingly, our empirical results suggest that this warm-start technique
also provides a good initial reward ensemble under alternate behaviour models,
such as the Boltzmann model in ML-IRL and BIRL [3, 30] and the gradient-based
model in $\Sigma$-GIRL [31].

###  3.1 Theoretical Analysis

To be able to discern different behavior intents in the demonstration data,
the intents must be distinguishable. When representing the demonstrations as
feature vectors, this amounts to requiring the feature vectors for
_typical/characteristic_ trajectories from each expert to form clusters that
are mostly distinct from each other, and the _atypical/ambiguous_ trajectories
can be different but not too different from the typical trajectories.
Specifically, to formulate this intuition, we say that a trajectory $\tau$
_$\gamma$ -separates_ two sets of trajectories $\mathcal{T}_{a}$ and
$\mathcal{T}_{b}$ (in the feature space) if
$\phi(\tau)^{\top}(\phi(\tau_{a})-\phi(\tau_{b}))\geq\gamma$ for all
$\tau_{a}\in\mathcal{T}_{a}$ and $\tau\in\mathcal{T}_{b}$. Geometrically, when
$\gamma>0$, the trajectories in $\mathcal{T}_{a}$ and $\mathcal{T}_{b}$ are
separated by a margin of at least $\gamma/\lVert\phi(\tau)\rVert$ when
projected on $\tau$ in the feature space. That is, we can find a SVM with a
margin of at least $\gamma/\lVert\phi(\tau)\rVert$ to separate trajectories in
$\mathcal{T}_{a}$ and $\mathcal{T}_{b}$. When $\gamma\leq 0$, the projections
of $\mathcal{T}_{a}$ and $\mathcal{T}_{b}$ on $\tau$ may overlap over an
interval of length $|\gamma|/\lVert\phi(\tau)\rVert$.

######  Assumption 1 (Approximate cluster separation).

Let $\mathcal{T}_{k}$ be the set of trajectories that can be generated by
expert $\pi_{k}$, and $\mathcal{T}_{\sim k}=\mathcal{T}-\mathcal{T}_{k}$. We
assume that there exists $\zeta\in[0,1/2)$ such that each $\mathcal{T}_{k}$
can be partitioned into two sets: a set of typical trajectories
$\mathcal{T}_{k}^{+}$ and a set of atypical trajectories $\mathcal{T}_{k}^{-}$
such that
$Q_{k}^{+}=\sum_{\tau\in\mathcal{T}_{k}^{+}}q(\tau)\geq(1-\zeta)Q_{k}$, or
equivalently, $Q_{k}^{-}=\sum_{\tau\in\mathcal{T}_{k}^{-}}q(\tau)\leq\zeta
Q_{k}$, where $Q_{k}=\sum_{\tau\in\mathcal{T}_{k}}q(\tau)$. In addition, the
typical trajectories and atypical trajectories satisfy the following
properties

  1. (a)

There exist $d,\gamma>0$, such that for any $k\in[K]$,

    1. (i)

each $\tau\in\mathcal{T}_{k}^{+}$ $d$-separates $\mathcal{T}_{k}^{+}$ and
$\mathcal{T}_{\sim k}$, and $\gamma$-separates $\mathcal{T}_{k}^{+}$ and
$\mathcal{T}_{k}^{-}$.

    2. (ii)

each $\tau\in\mathcal{T}_{k}^{-}$ $(-d)$-separates $\mathcal{T}_{k}^{+}$ and
$\mathcal{T}_{\sim k}$, and $(-\gamma)$-separates $\mathcal{T}_{k}^{+}$ and
$\mathcal{T}_{k}^{-}$.

  2. (b)

$\forall
k\in[K],~{}\exists~{}r_{k}<\min_{\tau\in\mathcal{T}_{k}^{+}}d/2\lVert\phi(\tau)\rVert$
s.t. $\|\phi(\tau)-\phi(\tau^{\prime})\|\leq 2r_{k}$ for all
$\tau,\tau^{\prime}\in\mathcal{T}_{k}^{+}$. That is, the trajectories in
$\mathcal{T}_{k}^{+}$ are contained in a ball of radius $r_{k}$ in the feature
space.

Intuitively, we assume that a typical trajectory in a cluster can be used to
distinguish typical trajectories from atypical trajectories and trajectories
in other clusters with margins $\gamma$ and $d$ respectively. On the other
hand, an atypical trajectory can fail to do so, but the overlaps are upper
bounded by $\gamma$ and $d$ respectively, so that they cannot be too different
from the typical trajectories — our analysis can be easily extended to
alternative choices of the upper bounds, but we have chosen $\gamma$ and $d$
for simplicity. Fig. 1 (middle) provides an illustration of Assumption 1 for
the case when $\zeta=0$. In practice, a useful trick is to shift the features
so that the mean feature vector is 0. This does not change the parameters of
the optimal MaxEnt IRL model, but allows us to exploit the clusters in the
data via Assumption 1.

With mostly-distinct clusters, we can reasonably expect a clustering algorithm
to be able to discover the underlying clusters in the dataset with high
accuracy.

######  Assumption 2 (Approximately correct clustering).

There exists $\delta\in[0,1/2)$, such that at least $1-\delta$ of the
trajectories in $C_{k}$ are in $\mathcal{T}_{k}^{+}$. In addition, the other
trajectories $(-d)$-separate $\mathcal{T}_{k}^{+}$ and
$\mathcal{T}_{k^{\prime}}$, and $(-\gamma)$-separate $\mathcal{T}_{k}^{+}$ and
$\mathcal{T}_{k}^{-}$.

Intuitively, most the trajectories in $\mathcal{D}$ are typical, and the
clustering algorithm is able to cluster most of them correctly. However, the
algorithm may fail on some trajectories, and these trajectories are assumed to
be not worse than the atypical trajectories in terms of their separation
ability.

To quantify the quality of the mean initialization, we first observe that
$\Phi_{k}$ is like a typical trajectory in $\mathcal{T}_{k}$ (all proofs are
in the supplementary file).

######  Lemma 1.

For any $k\in[K]$, $\Phi_{k}$ $\tilde{d}$-separates $\mathcal{T}_{k}^{+}$ and
$\mathcal{T}_{\sim k}$ for $\tilde{d}=(1-2\delta)d$. In addition, $\Phi_{k}$
$\tilde{\gamma}$-separates $\mathcal{T}_{k}^{+}$ and $\mathcal{T}_{k}^{-}$ for
$\tilde{\gamma}=(1-2\delta)\gamma$.

Our second observation is that $p(\tau\mid\Phi_{k})$ is large for typical
trajectories in $\mathcal{T}_{k}$, and small for trajectories not in
$\mathcal{T}_{k}$.

######  Lemma 2.

For any $\tau\in\mathcal{T}_{k}^{+}$, we have
$p(\tau\mid\Phi_{k})\geq\frac{(1-\zeta)q(\tau)e^{\tilde{d}-2r_{k}\lVert\Phi_{k}\rVert}}{(1-\zeta)Q_{k}e^{\tilde{d}}+Q_{\sim
k}}\frac{(1-\zeta)e^{\tilde{\gamma}}}{\zeta+(1-\zeta)e^{\tilde{\gamma}}}$,
where $Q_{\sim k}=\sum_{\tau\notin\mathcal{T}_{k}}Q_{k^{\prime}}$. In
addition, for any $\tau\notin\mathcal{T}_{k}$, we have
$p(\tau\mid\Phi_{k})\leq\frac{q(\tau)}{(1-\zeta)Q_{k}e^{\tilde{d}}+q(\tau)}$.

With the above two observations, we can then quantify the quality of the mean
initialization.

######  Theorem 1.

The mean initialisation LiMIIRL initial estimates
$\\{\rho_{1:K}^{(0)},\theta_{1:K}^{(0)}\\}$ are $\epsilon$-optimal for
$\epsilon=2\delta+(1-\delta)\frac{2(K-1)}{\beta+K-1}$, where
$\beta=\min_{k\neq
k^{\prime}}\frac{(1-\zeta)^{2}e^{\tilde{\gamma}}}{\zeta+(1-\zeta)e^{\tilde{\gamma}}}\frac{|C_{k}|((1-\zeta)Q_{k^{\prime}}e^{\tilde{d}})}{|C_{k^{\prime}}|((1-\zeta)Q_{k}e^{\tilde{d}}+Q_{\sim
k})}e^{\tilde{d}-2r_{k}\lVert\Phi_{k}\rVert}$.

The bound in Theorem 1 implies that the quality of the warm-start solution
improves when the separability of the behaviors and the quality of the
clustering algorithm are higher. Specifically, noting that
$\tilde{d}=(1-2\delta)d$ and $\tilde{\gamma}=(1-2\delta)\gamma$, we can see
that $\epsilon$ is small when $\zeta$ is small (smaller proportion of atypical
trajectories), $d$ is large (more distinct behaviors), $r_{k}$’s are smaller
(more concentrated clusters), $\gamma$ is large (larger difference between
typical and atypical trajectories), and $\delta$ is small (more accurate
clustering algorithm). In addition, $\epsilon$ converges to $\delta$ at a rate
exponential in $d$.

For the MLE initialization, obtaining a closed-form error bound is much more
involved. However, we highlight that the above analysis also provides an
insight that when the scaled margin is large, the MLE initialization would
work well too. To see this, note that cluster $k$ is roughly contained within
a hyper-cone having the origin as the vertex and an opening angle
$\alpha=\sin^{-1}(r_{k}/\lVert\Phi_{k}\rVert)$. Any $\theta_{k}$ becomes less
likely to be optimal as it forms an angle of more than $2\alpha$ with
$\Phi_{k}$, as follows: when $\theta_{k}$’s angle with $\Phi_{k}$ changes from
0 to more than $2\alpha$, for any $\tau\in\mathcal{T}_{k}$,
$e^{\phi(\tau)^{\top}\theta_{k}}$ decreases, because the angle between
$\phi(\tau)$ and $\theta_{k}$ changes from at most $\alpha$ to at least
$\alpha$. On the other hand, there is an empty space with margin
$d_{k}=d/\lVert\Phi_{k}\rVert$ below the cluster, thus trajectories not in
$\mathcal{T}_{k}$ initially form large angles with $\theta_{k}$, and have a
small contribution to the partition function, then gradually become more
important as $\theta_{k}$ moves away from $\Phi_{k}$, eventually making the
probability of trajectories in $\mathcal{T}_{k}$ small and the likelihood of
$\theta_{k}$ small.

##  4 MI-IRL Performance Metrics

We introduce our novel metric to evaluate an MI-IRL algorithm’s performance in
terms of the quality of the learned reward ensemble. We also evaluate an MI-
IRL algorithm’s clustering performance and describe the well-known Adjusted
max-Normalized Information Distance (ANID) for completeness.

#### Reward Ensemble Performance.

For single-intent IRL problems the Expected Value Difference (EVD) is an
appropriate measure of regret of a learned reward $R^{\text{L}}$ w.r.t. a true
reward function $R^{\text{GT}}$,
$\text{EVD}(R^{\text{GT}},R^{\text{L}})\triangleq\mathbb{E}_{s\sim
p_{0}}[\bm{v}_{\pi^{*}_{R^{\text{GT}}}}(s)-\bm{v}_{\pi^{*}_{R^{\text{L}}}}(s)]$,
where $\bm{v}_{\pi}$ is the value function for policy $\pi$, and $\pi^{*}_{R}$
is the optimal policy w.r.t. reward function $R$ [7, 21]. Previous authors
applied this metric in the multiple-intent setting by averaging the EVD of the
true and learned rewards for each trajectory [3, 8] – this process does not
directly compare the reward ensembles but instead depends on a sample of
demonstrations.

We propose a Generalized EVD (GEVD) metric that directly evaluates a learned
reward ensemble $\\{\rho^{\text{L}}_{1:K},R^{\text{L}}_{1:K}\\}$ against the
ground truth reward ensemble
$\\{\rho^{\text{GT}}_{1:K^{\prime}},R^{\text{GT}}_{1:K^{\prime}}\\}$. To
motivate, note that a reward ensemble remains the same even if the rewards are
reordered, thus for the special case where two reward ensembles are the same,
we can perform a bipartite matching to pair up the rewards.

We generalize this idea to handle the harder cases in which $K\neq
K^{\prime}$, and the weights may not be the same. Essentially, this requires
an additional reward split step before pairing up the rewards. Instead of just
finding the optimal pairing as in the simplest case above, we now need to find
the best way to split-and-pair rewards. This can be naturally formulated as
follows,
$\text{GEVD}(\mathbb{R}^{\text{GT}},\mathbb{R}^{\text{L}})\triangleq\operatorname*{arg\,min}_{\\{w_{ij}\\}:\sum_{j}w_{ij}=\rho^{\text{GT}}_{i},\sum_{i}w_{ij}=\rho^{\text{L}}_{j}}\sum_{i,j}w_{ij}\,e_{ij}$
where $e_{ij}=\text{EVD}(R^{\text{GT}}_{i},R^{\text{L}}_{j})$. It is easy to
show that the above problem is equivalent to a min-cost flow problem (see our
note in the Supplementary file), thus the GEVD can be efficiently computed
using standard graph manipulation libraries.

The range of GEVD is $\left[0,\frac{\max_{k}\Delta_{k}}{1-\gamma}\right]$,
where $\Delta_{k}$ is the difference between the maximum and minimum possible
rewards under the $k$-th ground truth reward reward function. GEVD is 0 iff
there is a way to split-and-pair ground truth and learned rewards such that
each pair of rewards lie in an equivalence class (in the sense of having the
same optimal policies), and depends only on the reward ensembles. We can
normalize GEVD into the range of $[0,1]$ by dividing it with
$\frac{\max_{k}\Delta_{k}}{1-\gamma}$, however a better normalization can be
achieved by dividing it with a tighter upper bound
$\sum_{i}\rho^{\text{GT}}_{i}e_{i}^{*}$, where $e_{i}^{*}=\mathbb{E}_{s\sim
p_{0}}[\bm{v}_{\pi^{*}_{R^{\text{GT}}}}(s)-\bm{v}_{\pi^{-}_{R^{\text{GT}}}}(s)]$,
with $\pi^{-}_{R}$ being the policy minimizing the reward $R$. We can
calculate $\pi^{-}_{R}$ using the same algorithm for computing $\pi^{*}_{R}$
(e.g. value iteration), so the normalization only increases the computation
time by a small factor. We believe the GEVD measure provides an elegant means
for evaluating arbitrary reward ensembles in controlled IRL experiments where
we have access to the MDP model, and we believe this is the first such metric
for the MI-IRL problem that does not require reference to a held-out testing
trajectory dataset. Furthermore, the GEVD actually provides a useful tool to
diagnose poorly performing MI-IRL solutions by inspecting reward pairings with
large EVDs, naturally guiding the practitioner toward parts of the model that
may require attention.

#### Clustering Performance.

MI-IRL requires both reward ensemble learning, and demonstration clustering –
both tasks should be evaluated in holistic evaluation of any MI-IRL method.
The Adjusted max-Normalized Information Distance (ANID) is a popular and
theoretically justified performance metric for assessing a mixture model’s
(hard or soft) clustering capability [37]. Given a learned MI-IRL mixture
model, we can compute its _responsibility matrix_ $\bm{U}=\\{u_{ik}\\}$ where
$u_{ik}$ is the probability that demonstration $i$ belongs to cluster $k$.
Similarly, we can compute the responsibility matrix
$\bm{V}=\\{v_{ik^{\prime}}\\}$ for the ground-truth MI-IRL mixture model. The
ANID is given by $\text{ANID}(\bm{U},\bm{V})\triangleq
1-\left(I(\bm{U},\bm{V})-\mathbb{E}[I(\bm{U}^{\prime},\bm{V}^{\prime})]\right)/\left(\max\\{H(\bm{U}),H(\bm{V})\\}-\mathbb{E}[I(\bm{U}^{\prime},\bm{V}^{\prime})]\right)$,
where $\bm{U}^{\prime}$ and $\bm{V}^{\prime}$ are random responsibility
matrices of the same dimensions as $\bm{U}$ and $\bm{V}$ respectively
distributed according to an appropriate random clustering model,111For hard
clusters, hypergeometric models are commonly used. In our soft clustering case
each row of $\bm{U}^{\prime}$ is independently sampled from the Dirichlet
distribution $Dir(1/K,\ldots,1/K)$, and similarly for $\bm{V}^{\prime}$.
$I(\bm{U},\bm{V})$ is the mutual information between $k,k^{\prime}$ following
a joint distribution
$p(k,k^{\prime})=\frac{1}{N}\sum_{i=1}^{N}u_{ik}v_{ik^{\prime}}$, and
$H(\bm{U})$ and $H(\bm{V})$ are respectively the entropies of $p(k)$ and
$p(k^{\prime})$, the two marginal distributions of $p(k,k^{\prime})$. The ANID
has many attractive properties: it is symmetric w.r.t. to $\bm{U}$ and
$\bm{V}$, is 0 iff $\bm{U}=\bm{V}$ modulo column re-ordering, is
computationally simple to calculate, controls for random chance agreement
between clusters when $K$ is large, is stochastically normalized to the range
$[0,1]$, and in the limit $N\rightarrow\infty$ converges to a proper metric
[37].

##  5 ElementWorld Benchmark Experiment

Previous MI-IRL methods have used a simple two-intent puddle gridworld
environment for evaluation [3, 31]. To investigate the scalability of our
method on a more substantial problem, we generalized this environment to the
case of many intents, creating a benchmark we call ElementWorld. ElementWorld
is a randomized gridworld environment with a cylindrical topology (Fig. 1,
left). An agent starts uniform randomly in the bottom row of the map, and must
navigate to any of the terminal goal states at the top of the map. Between the
start and goal areas, we generate ‘lanes’ corresponding to each of $E$
elements (e.g. water, dirt, grass), which are randomly perturbed horizontally,
forcing the agent to avoid obstacles, leading to non-trivial demonstrations.
The agent is randomly assigned one of $E$ possible intents, and for the
$k^{\text{th}}$ intent, we set the ground truth reward parameters for all
$j\neq k$ elements to $-10$, the goal to $0$, and the $k^{\text{th}}$ element
and the start zone to $-1$. For actions, the agent chooses from the four
cardinal directions, however this fails (and a random choice is made) with a
wind probability $w$. We use an $E+2$ dimensional state feature function
$\phi(s)=(\text{Start},\text{Goal},\text{Element}_{1},\dots,\text{Element}_{E})$,
which is a one-hot representation of the type of cell the agent is in.

By adjusting the number of elements $E$ and the wind probability $w$ we can
vary the difficulty of the MI-IRL behaviour clustering sub-problem:
$w\rightarrow 0$ leads to almost disjoint intent clusters in feature space,
while $w\rightarrow 1$ leads to almost completely overlapping intents in
feature space. Likewise, by adjusting the height $h$ of the map, we change the
length of the demonstrations, adjusting the difficulty of MI-IRL reward
learning sub-problem.

Table 1: LiMIIRL experimental results for EW – ElementWorld, and DB – Driver
Behaviour forecasting. Values are mean $\pm~{}95\%$ confidence interval over
100 (EW), 8 (DB) repeat experiments with randomized seeds. Lower is better for
all metrics.

| Algorithm | Iterations | Duration (s,m) | NLL | ANID | GEVD
---|---|---|---|---|---|---
EW | LiMIIRL-MLE | 3.41 $\pm$ 01.40 | 33.20 $\pm$ 13.49 | 19.65 $\pm$ 00.64 | 0.03 $\pm$ 00.01 | 3.70 $\pm$ 01.11
LiMIIRL-Mean | 5.08 $\pm$ 01.13 | 21.86 $\pm$ 06.65 | 19.76 $\pm$ 00.45 | 0.04 $\pm$ 00.01 | 4.49 $\pm$ 00.98
Random | 17.22 $\pm$ 04.80 | 136.58 $\pm$ 39.69 | 20.05 $\pm$ 00.71 | 0.13 $\pm$ 00.07 | 6.75 $\pm$ 02.09
Supervised | N/A | N/A | 19.65 $\pm$ 00.66 | 0.04 $\pm$ 00.01 | 3.65 $\pm$ 01.27
DB | LiMIIRL-MLE | 1.17 $\pm$ 00.60 | 68.29 $\pm$ 34.01 | 305.55 $\pm$ 01.20 | N/A | N/A
LiMIIRL-Mean | 4.17 $\pm$ 01.10 | 243.28 $\pm$ 64.22 | 303.99 $\pm$ 03.17 | N/A | N/A
Random | 3.33 $\pm$ 01.51 | 198.40 $\pm$ 79.69 | 305.37 $\pm$ 03.17 | N/A | N/A

###  5.1 ElementWorld Results

#### Experimental configuration.

We performed an experiment to validate our LiMIIRL algorithm. With
$E=3,w=0.1,h=6,\gamma=0.99$ we used Q-value iteration to find an optimal
stochastic policy for each behaviour intent, then sampled uniformly from the
policy ensemble for a dataset of $N=100$ demonstrations. Using a MaxEnt IRL
reward model we compared the performance of the EM algorithm with random
initialization [3] to our LiMIIRL method with $k$-means clustering, with
either mean, or MLE reward initialisation. As a baseline, we also included a
supervised reward ensemble that is provided with the labels mapping
demonstrations to elements, and the EM MI-IRL algorithm with random
initialisation, as used in [3]. For this initial experiment we assumed the
true number of elements was known a priori (i.e. $K=E$). For each experiment,
we recorded the number of iterations and wall time to EM convergence, the
Negative Log Likelihood (NLL) and clustering performance (ANID) on a held-out
testing set of 100 demonstrations, as well as the reward ensemble quality
(GEVD). Every experiment was repeated $100\times$ with different randomly
generated ElementWorld instances to allow estimating the mean and $95\%$
confidence interval for each metric.

#### No significant difference between MLE and mean initialisation.

The results are summarized in Table 1, with corresponding box-plots included
in the supplementary data file. The results confirm our hypothesis that
LiMIIRL is able to identify good starting points for the MI-IRL EM algorithm,
at least for this problem instance which satisfies our theoretical
assumptions. The results also show that MLE and mean reward initialisation are
roughly equivalent in this case – both empirically seem to identify good
starting points for the MI-IRL problem, with no statistically significant
difference in the performance of these methods. In general however, we have
observed the MLE initialization seems more robust when there is large
deviation from our theoretical assumptions, an idea we investigate further in
the driver behaviour experiment below.

#### LiMIIRL avoid local-minima EM solutions.

With hard clustering, LiMIIRL learns a better reward ensemble than the EM
algorithm with random initialisation ($90\%$ relative reduction of ANID,
$45\%$ relative reduction in GEVD), despite the solutions having equivalent
Negative Log Likelihood. This reveals an interesting property of the MI-EM
algorithm – the optimization landscape of this problem has many local minima
which appear equal or nearly equal in NLL, but vary greatly in terms of actual
performance, highlighting the importance of a good initialization point for
the ensemble.

#### LiMIIRL leads to faster EM convergence.

Our key finding however is that LiMIIRL leads to the EM algorithm reaching
convergence significantly faster. On average, LiMIIRL reduces the number of
iterations and running time by around 80% and 75% respectively with $k$-means
initialization, and 30% and 73% respectively with GMM initialization.
Comparison with the corresponding Iteration and Duration box-plots reveals
that the convergence metric results are heavy tailed – especially when random
initialisation is used, further supporting the idea that a good starting point
is critical for this problem.

These results provide hope that LiMIIRL will be especially helpful on larger
problems where each EM iteration is itself a computationally expensive
procedure, provided we have reason to believe the behaviour intents are at
least approximately separated in feature space.

###  5.2 Sensitivity Analysis

We conducted extensive additional experiments to investigate the sensitivity
of our algorithm under additional problem variations, especially cases where
the theoretical assumptions are violated. We evaluated our algorithm under
scenarios with varying numbers of demonstrations, degree of cluster separation
in feature space, number of learned clusters, number of ground truth elements,
cluster imbalance, initial clustering method (hard $k$-means vs. soft Gaussian
Mixture Models), as well as with a different behaviour models (ML-IRL, and
$\Sigma$-GIRL [3, 31]). For each algorithm and each problem instance, we
performed over 20 repeat experiments with randomized ElementWorld seeds to
generate means and $95\%$ confidence intervals. For brevity, we detail the
nature of each parameter sweep and report the full results as figures in the
supplementary file, however we briefly describe a few key findings here.

#### Hard-clustering vs. soft-clustering.

We observed that in general, hard clustering with KMeans always tends to out-
perform soft clustering with a GMM. Surprisingly, this is true even as the
problem dynamics are made more stochastic (increasing wind factor $w$, which
causes the intent clusters to intermingle in feature space). We hypothesise
that the hard clustering leads to less mis-classification of training
demonstrations, which may lead to higher-quality rewards to be learned.
Encouragingly, hard clustering always performs on-par with the supervised
baseline, with the exception of the case of large numbers of ground truth
elements $E$, where there is a performance difference.

#### Number of learned clusters.

As our algorithm is parametric, we require that the number of clusters $K$ be
specified a priori. In experiments where we varied the number of learned
clusters, keeping $E=3$ fixed, we observe that the mixture NLL generally
increases proportional to $K$, however the ANID and GEVD metrics reach a
minima / asymptote respectively at $K=3$ – this confirms that our metrics are
a good measure of ensemble performance, even for the case when the number of
learned clusters is mis-specified. We note that in practice, the value of $K$
can be estimated using heuristics such as the Bayesian Information Criteria,
using a non-parametric clustering as a pre-processing step, or using cross-
fold validation.

#### Cluster Imbalance.

Finally, we also tested the case of non-balanced behaviour intents in the
dataset. Encouragingly, LiMIIRL appears able to learn accurate ensembles in
this case, correctly allocating less probability mass to the rarer behaviour
intents.

#### Alternate IRL models.

LiMIIRL appears to work with ML-IRL and $\Sigma$-GIRL as the IRL model too,
however due to the computational complexity of these methods we did not
include them in our driver forecasting experiment, below.

##  6 Driver Forecasting Experiment

We demonstrate the merit of our method by application to a large driver
behaviour dataset, consisting of Taxi GPS trajectories collected between
2013–14 in the city of Porto, Portugal [26, 12]. Our data pre-processing
follows that used in [41, 36]: a particle filter was used to discretize the
GPS trajectories to the road network, giving a deterministic MDP with 292,604
states (road segments) and 594,933 actions (turns at intersections). As state
features, we used the type of road (highway, local street etc.), the number of
lanes, as well as a geographical indicator for the region of the city where
that road segment is located (Central, North, North east, etc.) The feature
function was obtained by concatenating the individual one-hot feature vectors
and multiplying by the length of the road segment in km, resulting in a 24
dimensional state-based feature vector. We trained all models on paths $\leq
300$ road segments in length, and used held-out test sets for evaluation.

We qualitatively observed the presence of multiple behaviour intents in this
dataset (e.g. Fig. 1, left), however we have no ground truth knowledge of the
number of clusters $K$. Instead, as a pre-processing step we used a stick-
breaking non-parametric GMM in feature space to estimate the appropriate
number of clusters for this dataset as $K\approx 3$. To accelerate the
training process, we only perform a partial maximization at the M-step, by
truncating each M-step of the EM algorithm after 50 objective function
evaluations. Provided the learned solution is a monotonic improvement in
objective than that of the previous iteration the convergence conditions for
the EM algorithm will still be satisfied [9, 30]. Experiments were performed
on a 12-core Ubuntu workstation with Intel Xeon E5-2760 v3 CPUs. We summarize
the number of iterations and wall time to EM convergence, as well as the final
mixture NLL in Table 1. Each value is a mean and $\pm 95\%$ confidence
interval across 8 folds of cross validation (1000 / 8000 randomly sampled
train / test demonstrations for each fold).

The results align with that of ElementWorld – LiMIIRL with MLE initialisation
learns mixtures with similar NLL to random initialisation, however reaches
convergence significantly faster - a saving of between 2.16 and 2.33 EM
iterations, corresponding to a non-trivial reduction in training time of
between 130 and 135 minutes. We note that the Mean initialisation method does
not reduce the convergence time for this problem, which we attribute to the
fact that the cluster separation assumption is substantially violated in this
dataset.

We also investigate the qualitative behaviour models learned by the
algorithms. The learned reward ensembles were largely similar regardless of
initialisation method, with a few exceptions (see supplementary file).
Interestingly, we are also able to identify qualitatively meaningful trends
within the learned ensembles – e.g. it appears a majority (85% – 90%) of taxi
drivers in this dataset share in a preference for higher speed limits, and
most prefer navigating on routes through the northern and western suburbs –
perhaps due to the presence of a large ring-road highway that spans this area.
The remaining reward functions differed in the geographic and road type
preferences - e.g. preferring eastern suburbs and/or road types other than
highways. This demonstrates that LiMIIRL can be applied on a large, real world
dataset to efficiently learn qualitatively meaningful behaviour models in the
form of IRL reward ensembles.

##  7 Related Work

#### Alternate IRL formulations.

IRL is an active research area, with fundamental methods being extended in
multiple directions. Our work is complementary to many such extensions,
including works considering multiple interacting agents [27], or agents with
multiple sub-goals [24, 25, 11], skills [32], or options [17], or using
adversarial reward learning to scale to high dimensional problems [13], or
using specialised divergence to match a single intent in a multi-intent
dataset [18]. Unlike these works, we consider the problem of learning multiple
rewards from a dataset containing several unlabeled behaviour intents [3]. We
highlight that a related but distinct problem is that of Meta-IRL, where the
goal is to learn a good meta-reward prior [14, 39] or shared base reward [6]
that can be used to learn new rewards efficiently.

#### Multiple-Intent IRL methods.

In the MI-IRL setting, methods can be partitioned into parametric (known
number of clusters $K$) and non-parametric approaches ($K$ unknown). While
initialisation strategies such as ours may be helpful in Bayesian non-
parametric models [7] or hierarchical non-parametric clustering schemes [1],
we leave exploration of this avenue to future work, instead focusing on
parametric methods modelled on the Expectation Maximization framework [9].
Specifically, our work is based on the EM-based MI-IRL approach of [3], which
has also been extended to a full Bayesian treatment [10], and to use model-
free gradient based IRL methods [31]. While our theoretical analysis uses the
MaxEnt IRL behaviour model [41, 36], our empirical experiments with the ML-IRL
model from [3] and the $\Sigma$-GIRL model of [31] suggest that our
initialisation method is effective with a range of behaviour models.

#### Initialisation methods for Expectation Maximization.

Our initialization method is designed to alleviate the problem of learning
local minima solutions — an issue that the family of EM algorithms are well-
known to suffer from (as well as slow convergence rates) [9, 38, 4]. As such,
the study of good initialisation methods for specific EM algorithms is an
ongoing area of research [38, 29, 28], as is work on finding alternate update
rules to address the same issues [38, 23]. Our work relates to these
investigations, however we focus on EM algorithms that are specific to
clustering problems, rather than general data-completion problems —
specifically, we consider intent clustering as encountered in MI-IRL.

#### IRL evaluation measures

In addition to developing an initialisation method for EM-based MI-IRL, we
propose a novel metric for evaluating the quality of MI-IRL reward ensembles
with respect to a known ground-truth ensemble. Our method extends the popular
Expected Value Difference (EVD) and Inverse Learning Error (ILE)222The ILE is
equivalent to EVD with a specific choice of state distribution. metrics for
comparing individual reward pairs [21, 7]. Specifically, our GEVD metric
generalize these measures to the case of hard or soft reward ensembles with
potentially different sizes. Previous approaches for evaluating the quality of
reward ensembles have suffered from two main limitations - they depend on
comparing the likelihood or return of a specific test trajectory dataset [3,
1], or if not, they require manually matching learned rewards with the
corresponding ground truth reward [10, 31]. In contrast, our method does not
require a held out testing dataset, and is able to automatically, elegantly
and efficiently solve the ensemble matching problem through a min-cost-flow
formulation. Recently, there has been renewed interest in methods for
comparing reward pairs (i.e. the single-intent IRL problem) without requiring
policy evaluation [15]. These reward pseudo-metrics are complementary to our
work, in that a straight-forward application of the min-cost-flow formulation
outlined in Section 4 can also extend these evaluation standards to the
Multiple-Intent case. However, while such pseudo-metric can be theoretically
and computationally attractive, enforcing symmetry for the learned reward and
the ground-truth reward in the metric may be undesirable in the IRL setting,
which is asymmetric in nature, as in general the effect of using a reward $R$
on a domain with reward $R^{\prime}$ is different from the effect of using a
reward $R^{\prime}$ on a domain with reward $R$. For example, if $R$ is a
constant reward function, and $R^{\prime}$ is a sparse reward function, then
using $R^{\prime}$ in a domain with reward function $R$ does not lead to sub-
optimal behavior, while using $R$ in a domain with reward function
$R^{\prime}$ is usually sub-optimal.

##  8 Conclusion

We presented a simple warm-start strategy for learning MI-IRL models and
demonstrate its effectiveness with both theoretical and empirical analysis. In
addition, we developed a novel performance metric, GEVD, for evaluating a
learned reward ensemble against a ground-truth one. These contributions
further MI-IRL research by developing simple strategies that can make MI-IRL
methods more efficient and practical, with insight on when the methods can
work well.

GEVD provides a natural and direct way to measure the quality of a learned
reward ensemble, but is limited to use with benchmark problems where the
ground truth reward ensemble is known, and policy iteration and evaluation can
be used to compute the regret of policies. Further research could develop
metrics that enjoys the benefits of GEVD but circumvents these limitations.

Our warm-start strategy requires only mild assumptions, and enjoys provable
provable theoretical guarantee when using the mean initialization and the
MaxEnt IRL behaviour model. Interestingly, empirical results suggest that the
idea is effective for the MLE initialisation and some other IRL models.
Theoretical results for these cases are non-trivial but will be an interesting
area for future work. Another interesting area for future work is exploring if
initialisation methods such as ours can also be beneficial in parametric
latent variable adversarial models that are gaining interest in the Imitation
Learning literature where policy learning, not reward learning is the goal
[22, 16]. Finally, nonlinear rewards, particularly those represented by deep
neural networks, have been explored in various IRL works (e.g., see [13]). We
can also extend the idea in this paper to provide a warm-start solution when a
pre-trained feature map is available.

## Acknowledgments and Disclosure of Funding

Aaron Snoswell is supported by through an Australian Government Research
Training Program Scholarship.

## References

  * Almingol and Montesano [2015] Javier Almingol and Luis Montesano.  Learning multiple behaviours using hierarchical clustering of rewards.  In _2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 4608–4613, September 2015.  doi: 10.1109/IROS.2015.7354033.
  * Anderson et al. [2010] Derek T. Anderson, James C. Bezdek, Mihail Popescu, and James M. Keller.  Comparing Fuzzy, Probabilistic, and Possibilistic Partitions.  _IEEE Transactions on Fuzzy Systems_ , 18(5):906–918, 2010.
  * Babeş-Vroman et al. [2011] Monica Babeş-Vroman, Vukosi Marivate, Kaushik Subramanian, and Michael L. Littman.  Apprenticeship Learning About Multiple Intentions.  In _Proceedings of the 28th International Conference on Machine Learning_ , ICML ’11, pages 897–904, Bellevue, WA, USA, 2011\. ACM, New York, NY, USA.  ISBN 978-1-4503-0619-5.
  * Balakrishnan et al. [2017] Sivaraman Balakrishnan, Martin J Wainwright, and Bin Yu.  Statistical guarantees for the EM algorithm: From population to sample-based analysis.  _arXiv preprint arXiv:1408.2156_ , 2017.
  * Bogert et al. [2016] Kenneth Bogert, Jonathan Feng-Shun Lin, Prashant Doshi, and Dana Kulic.  Expectation-maximization for inverse reinforcement learning with hidden data.  In _Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems_, pages 1034–1042, 2016.
  * Chen et al. [2020] Letian Chen, Rohan Paleja, Muyleng Ghuy, and Matthew Gombolay.  Joint goal and strategy inference across heterogeneous demonstrators via reward network distillation.  In _Proceedings of the 2020 ACM/IEEE International Conference on Human-Robot Interaction_ , pages 659–668, 2020.
  * Choi and Kim [2011] J. D. Choi and Kee-Eung Kim.  Inverse Reinforcement Learning in Partially Observable Environments.  _Journal of Machine Learning Research_ , 12:691–730, 2011\.
  * Choi and Kim [2012] Jaedeug Choi and Kee-Eung Kim.  Nonparametric Bayesian Inverse Reinforcement Learning for Multiple Reward Functions.  In _Advances in Neural Information Processing Systems 25_ , NIPS ’12, pages 305–313, Lake Tahoe, United States, 2012. Curran Associates, Inc.
  * Dempster et al. [1977] A. P. Dempster, N. M. Laird, and D. B. Rubin.  Maximum Likelihood from Incomplete Data via the EM Algorithm.  _Journal of the Royal Statistical Society. Series B (Methodological)_ , 39(1):1–38, 1977.
  * Dimitrakakis and Rothkopf [2011] Christos Dimitrakakis and Constantin A. Rothkopf.  Bayesian multitask inverse reinforcement learning.  In _European Workshop on Reinforcement Learning_ , pages 273–284. Springer, 2011.
  * Ding et al. [2019] Yiming Ding, Carlos Florensa, Mariano Phielipp, and Pieter Abbeel.  Goal-conditioned imitation learning.  _arXiv preprint arXiv:1906.05838_ , 2019.
  * Dua and Graff [2017] Dheeru Dua and Casey Graff.  UCI machine learning repository.  2017\.
  * Fu et al. [2018] Justin Fu, Katie Luo, and Sergey Levine.  Learning robust rewards with adversarial inverse reinforcement learning.  2018\.
  * Gleave and Habryka [2018] Adam Gleave and Oliver Habryka.  Multi-task maximum entropy inverse reinforcement learning.  _arXiv preprint arXiv:1805.08882_ , 2018.
  * Gleave et al. [2020] Adam Gleave, Michael Dennis, Shane Legg, Stuart Russell, and Jan Leike.  Quantifying differences in reward functions.  _arXiv preprint arXiv:2006.13900_ , 2020.
  * Gruver et al. [2020] Nate Gruver, Jiaming Song, Mykel J. Kochenderfer, and Stefano Ermon.  Multi-agent adversarial inverse reinforcement learning with latent variables.  In _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ , pages 1855–1857, 2020.
  * Henderson et al. [2018] Peter Henderson, Wei-Di Chang, Pierre-Luc Bacon, David Meger, Joelle Pineau, and Doina Precup.  OptionGAN: Learning joint reward-policy options using generative adversarial inverse reinforcement learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Ke et al. [2019] Liyiming Ke, Matt Barnes, Wen Sun, Gilwoo Lee, Sanjiban Choudhury, and Siddhartha Srinivasa.  Imitation Learning as f-Divergence Minimization.  _arXiv preprint arXiv:1905.12888_ , 2019.
  * Lei et al. [2014] Yang Lei, James C. Bezdek, Jeffrey Chan, Nguyen Xuan Vinh, Simone Romano, and James Bailey.  Generalized information theoretic cluster validity indices for soft clusterings.  In _2014 IEEE Symposium on Computational Intelligence and Data Mining (CIDM)_ , pages 24–31, December 2014.  doi: 10.1109/CIDM.2014.7008144.
  * Lei et al. [2017] Yang Lei, James C. Bezdek, Jeffrey Chan, Nguyen Xuan Vinh, Simone Romano, and James Bailey.  Extending Information-Theoretic Validity Indices for Fuzzy Clustering.  _IEEE Transactions on Fuzzy Systems_ , 25(4):1013–1018, August 2017.  ISSN 1941-0034.  doi: 10.1109/TFUZZ.2016.2584644.
  * Levine et al. [2011] Sergey Levine, Zoran Popovic, and Vladlen Koltun.  Nonlinear Inverse Reinforcement Learning with Gaussian Processes.  In _Advances in Neural Information Processing Systems 24_ , pages 19–27, Granada, Spain, 2011. Curran Associates, Inc.
  * Li et al. [2017] Yunzhu Li, Jiaming Song, and Stefano Ermon.  InfoGAIL: Interpretable imitation learning from visual demonstrations.  _arXiv preprint arXiv:1703.08840_ , 2017.
  * Mena et al. [2020] Gonzalo Mena, Amin Nejatbakhsh, Erdem Varol, and Jonathan Niles-Weed.  Sinkhorn EM: An expectation-maximization algorithm based on entropic optimal transport.  _arXiv preprint arXiv:2006.16548_ , 2020.
  * Michini and How [2012] Bernard Michini and Jonathan P. How.  Bayesian nonparametric inverse reinforcement learning.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 148–163. Springer, 2012.
  * Michini et al. [2015] Bernard Michini, Thomas J. Walsh, Ali-Akbar Agha-Mohammadi, and Jonathan P. How.  Bayesian Nonparametric Reward Learning From Demonstration.  _IEEE Transactions on Robotics_ , 31(2):369–386, April 2015.  ISSN 1941-0468.  doi: 10.1109/TRO.2015.2405593.
  * Moreira-Matias et al. [2013] Luis Moreira-Matias, Joao Gama, Michel Ferreira, Joao Mendes-Moreira, and Luis Damas.  Predicting taxi-passenger demand using streaming data.  _IEEE Transactions on Intelligent Transportation Systems_ , 14(3):1393–1402, 2013.
  * Natarajan et al. [2010] Sriraam Natarajan, Gautam Kunapuli, Kshitij Judah, Prasad Tadepalli, Kristian Kersting, and Jude Shavlik.  Multi-Agent Inverse Reinforcement Learning.  In _2010 Ninth International Conference on Machine Learning and Applications_ , pages 395–400, December 2010.  doi: 10.1109/ICMLA.2010.65.
  * O’Hagan and White [2019] Adrian O’Hagan and Arthur White.  Improved model-based clustering performance using Bayesian initialization averaging.  _Computational Statistics_ , 34(1):201–231, March 2019.  ISSN 1613-9658.  doi: 10.1007/s00180-018-0855-2.
  * O’Hagan et al. [2012] Adrian O’Hagan, Thomas Brendan Murphy, and Isobel Claire Gormley.  Computational aspects of fitting mixture models via the expectation–maximization algorithm.  _Computational Statistics & Data Analysis_, 56(12):3843–3864, December 2012.  ISSN 0167-9473.  doi: 10.1016/j.csda.2012.05.011.
  * Ramachandran and Amir [2007] Deepak Ramachandran and Eyal Amir.  Bayesian inverse reinforcement learning.  In _IJCAI_ , volume 7, pages 2586–2591, 2007.
  * Ramponi et al. [2020] Giorgia Ramponi, Amarildo Likmeta, Alberto Maria Metelli, Andrea Tirinzoni, and Marcello Restelli.  Truly Batch Model-Free Inverse Reinforcement Learning about Multiple Intentions.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2359–2369. PMLR, 2020.
  * Ranchod et al. [2015] Pravesh Ranchod, Benjamin Rosman, and George Konidaris.  Nonparametric Bayesian reward segmentation for skill discovery using inverse reinforcement learning.  In _2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 471–477, September 2015\.  doi: 10.1109/IROS.2015.7353414.
  * Rand [1971] William M. Rand.  Objective criteria for the evaluation of clustering methods.  _Journal of the American Statistical association_ , 66(336):846–850, 1971.
  * Romano et al. [2016] Simone Romano, Nguyen Xuan Vinh, James Bailey, and Karin Verspoor.  Adjusting for Chance Clustering Comparison Measures.  _Journal of Machine Learning Research_ , 17:1–32, 2016\.
  * Russell [1998] Stuart Russell.  Learning agents for uncertain environments.  In _Proceedings of the eleventh annual conference on Computational learning theory_ , pages 101–103, 1998.
  * Snoswell et al. [2020] Aaron J. Snoswell, Surya P. N. Singh, and Nan Ye.  Revisiting Maximum Entropy Inverse Reinforcement Learning: New Perspectives and Algorithms.  In _IEEE Symposium Series on Computational Intelligence_ , 2020.
  * Vinh et al. [2010] Nguyen Xuan Vinh, Julien Epps, and James Bailey.  Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance.  _Journal of Machine Learning Research_ , 11:2837–2854, 2010\.
  * Vlassis and Likas [2002] N. Vlassis and A. Likas.  A greedy EM algorithm for Gaussian mixture learning.  _Neural Processing Letters_ , 15(1):77–87, 2002\.
  * Yu et al. [2019] Lantao Yu, Tianhe Yu, Chelsea Finn, and Stefano Ermon.  Meta-inverse reinforcement learning with probabilistic context variables.  _arXiv preprint arXiv:1909.09314_ , 2019.
  * Zhao and Karypis [2001] Ying Zhao and George Karypis.  Criterion functions for document clustering: Experiments and analysis.  2001\.
  * Ziebart et al. [2008] Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, and Anind K Dey.  Maximum entropy inverse reinforcement learning.  In _AAAI_ , volume 8, pages 1433–1438. Chicago, IL, USA, 2008.

##  Appendix A Theoretical Analysis of the LiMIIRL algorithm – additional
results

Here we state an additional lemma that is useful for our analysis, and include
proofs that are excluded from our main text.

The following simple result is handy useful in the below proofs.

######  Lemma 5.

Let $A=\\{a_{1},\ldots,a_{n}\\}$,
$A^{\prime}=\\{a_{1}^{\prime},\ldots,a_{n}^{\prime}\\}$
$B=\\{b_{1},\ldots,b_{m}\\}$ and
$B^{\prime}=\\{b_{1}^{\prime},\ldots,b_{m}^{\prime}\\}$ be finite sets of
positive numbers. If
$\frac{a_{i}}{b_{j}}\geq\frac{a_{i}^{\prime}}{b_{j}^{\prime}}\alpha$ for all
$1\leq i\leq n$, $1\leq j\leq m$, then for $I\subseteq\\{1,\ldots,n\\}$,
$J\subseteq\\{1,\ldots,m\\}$, we have

$\displaystyle\frac{\sum_{i\in I}a_{i}}{\sum_{i\in I}a_{i}+\sum_{j\in
J}b_{j}}$ $\displaystyle\geq\frac{\sum_{i\in
I}a_{i}^{\prime}\alpha}{\sum_{i\in I}a_{i}^{\prime}\alpha+\sum_{j\in
J}b_{j}^{\prime}}$ (2) $\displaystyle\frac{\sum_{j\in J}b_{j}}{\sum_{i\in
I}a_{i}+\sum_{j\in J}b_{j}}$ $\displaystyle\leq\frac{\sum_{j\in
J}b_{j}^{\prime}}{\sum_{i\in I}a_{i}^{\prime}\alpha+\sum_{j\in
J}b_{j}^{\prime}}$ (3)

###### Proof.

From the assumptions, we have

$\displaystyle\frac{\sum_{i\in I}a_{i}}{b_{j}}=\sum_{i\in
I}\frac{a_{i}}{b_{j}}\geq\sum_{i\in
I}\frac{a_{i}^{\prime}}{b_{j}^{\prime}}\alpha=\frac{\sum_{i\in
I}a_{i}^{\prime}\alpha}{b_{j}^{\prime}}.$

Inverting the fractions on both sides, we have

$\displaystyle\frac{b_{j}}{\sum_{i\in
I}a_{i}}\leq\frac{b_{j}^{\prime}}{\sum_{i\in I}a_{i}\alpha}.$

Summing over $j\in J$ and adding 1 to both sides, we have

$\displaystyle\frac{\sum_{i\in I}a_{i}+\sum_{j\in J}b_{j}}{\sum_{i\in
I}a_{i}}\leq\frac{\sum_{i\in I}a_{i}^{\prime}\alpha+\sum_{j\in
J}b_{j}^{\prime}}{\sum_{i\in I}a_{i}\alpha}.$

Inverting the fractions on both sides, we obtain the desired inequality

$\displaystyle\frac{\sum_{i\in I}a_{i}}{\sum_{i\in I}a_{i}+\sum_{j\in
J}b_{j}}\geq\frac{\sum_{i\in I}a_{i}\alpha}{\sum_{i\in
I}a_{i}^{\prime}\alpha+\sum_{j\in J}b_{j}^{\prime}}.$

The second inequality in the lemma thus follows easily by subtracting both
sides of the inequality by 1. ∎

###### Proof of Lemma 1..

For any $\tau\in\mathcal{T}_{k}^{+}$ and any
$\tau^{\prime}\in\mathcal{T}_{\sim k}$, we have

$\displaystyle\Phi_{k}^{\top}(\phi(\tau)-\phi(\tau^{\prime}))$
$\displaystyle=\frac{1}{|C_{k}|}\sum_{\tau^{\prime\prime}\in
C_{k}}\phi(\tau^{\prime\prime})(\phi(\tau)-\phi(\tau^{\prime}))$
$\displaystyle=\frac{1}{|C_{k}|}\sum_{\tau^{\prime\prime}\in\mathcal{T}_{k}^{+}}\phi(\tau^{\prime\prime})(\phi(\tau)-\phi(\tau^{\prime}))+\frac{1}{|C_{k}|}\sum_{\tau^{\prime\prime}\notin\mathcal{T}_{k}^{+}}\phi(\tau^{\prime\prime})(\phi(\tau)-\phi(\tau^{\prime}))$
$\displaystyle\geq(1-\delta)d+\delta(-d)$ $\displaystyle=(1-2\delta)d,$

where the inequality follows from Assumption 1(a)(i) and Assumption 2.

For any $\tau\in\mathcal{T}_{k}^{+}$ and any
$\tau^{\prime}\in\mathcal{T}_{k}^{-}$, we have

$\displaystyle\Phi_{k}^{\top}(\phi(\tau)-\phi(\tau^{\prime}))$
$\displaystyle=\frac{1}{|C_{k}|}\sum_{\tau^{\prime\prime}\in
C_{k}}\phi(\tau^{\prime\prime})(\phi(\tau)-\phi(\tau^{\prime}))$
$\displaystyle=\frac{1}{|C_{k}|}\sum_{\tau^{\prime\prime}\in\mathcal{T}_{k}^{+}}\phi(\tau^{\prime\prime})(\phi(\tau)-\phi(\tau^{\prime}))+\frac{1}{|C_{k}|}\sum_{\tau^{\prime\prime}\notin\mathcal{T}_{k}^{+}}\phi(\tau^{\prime\prime})(\phi(\tau)-\phi(\tau^{\prime}))$
$\displaystyle\geq(1-\delta)\gamma+\delta(-\gamma)$
$\displaystyle=(1-2\delta)\gamma.$

∎

###### Proof of Lemma 2..

Let $w(\tau)=q(\tau)\exp(\phi(\tau)^{\top}\Phi_{k})$,
$W_{k}=\sum_{\tau\in\mathcal{T}_{k}}w(\tau)$, $W_{\sim
k}=\sum_{\tau\in\mathcal{T}_{\sim k}}w(\tau)$,
$W_{k}^{+}=\sum_{\tau\in\mathcal{T}_{k}^{+}}w(\tau)$,
$W_{k}^{-}=\sum_{\tau\in\mathcal{T}_{k}^{-}}w(\tau)$, and
$W=\sum_{\tau\in\mathcal{T}}w(\tau)$. We obtain a lower bound on

$\displaystyle
p(\tau\mid\Phi_{k})=\frac{w(\tau)}{W}=\frac{W_{k}}{W}\frac{w(\tau)}{W_{k}}$

by lower bounding $\frac{W_{k}}{W}$ and $\frac{w(\tau)}{W_{k}}$ respectively.

To lower bound $\frac{W_{k}}{W}$, first note that $W_{k}\geq W_{k}^{+}$, thus

$\displaystyle\frac{W_{k}}{W}=\frac{W_{k}}{W_{k}+W_{\sim
k}}\geq\frac{W_{k}^{+}}{W_{k}^{+}+W_{\sim k}},$ (4)

and it suffices to lower bound the last fraction. From Lemma 1, $\Phi_{k}$
$\tilde{d}$-separates $\mathcal{T}_{k}^{+}$ and $\mathcal{T}_{\sim k}$, thus
for any $\tau\in\mathcal{T}_{k}^{+}$ and any
$\tau^{\prime}\in\mathcal{T}_{\sim k}$, we have

$\displaystyle\frac{w(\tau)}{w(\tau^{\prime})}=\frac{q(\tau)\exp((\phi(\tau)-\phi(\tau^{\prime}))^{\top}\Phi_{k})}{q(\tau^{\prime})}\geq\frac{q(\tau)}{q(\tau^{\prime})}\exp(\tilde{d}),$

where the equality is obtained by dividing both numerator and denominator by
$\exp(\phi(\tau)^{\top}\Phi_{k})$. Using Lemma 5, we have

$\displaystyle\frac{W_{k}^{+}}{W_{k}^{+}+W_{\sim k}}$
$\displaystyle=\frac{\sum_{\tau\in\mathcal{T}_{k}^{+}}w(\tau)}{\sum_{\tau^{\prime}\in\mathcal{T}_{k}^{+}}w(\tau^{\prime})+\sum_{\tau^{\prime}\notin\mathcal{T}_{k}}w(\tau^{\prime})}$
$\displaystyle\geq\frac{\sum_{\tau\in\mathcal{T}_{k}^{+}}q(\tau)\exp(\tilde{d})}{\sum_{\tau^{\prime}\in\mathcal{T}_{k}^{+}}q(\tau^{\prime})\exp(\tilde{d})+\sum_{\tau^{\prime}\in\mathcal{T}_{\sim
k}}q(\tau^{\prime})}$
$\displaystyle=\frac{Q_{k}^{+}\exp(\tilde{d})}{Q_{k}^{+}\exp(\tilde{d})+Q_{\sim
k}}$
$\displaystyle=\frac{(1-\zeta)Q_{k}\exp(\tilde{d})}{(1-\zeta)Q_{k}\exp(\tilde{d})+Q_{\sim
k}}.$ (5)

Now, to lower bound $\frac{w(\tau)}{W_{k}}$, note that since $\Phi_{k}$
$\tilde{\gamma}$-separates $\mathcal{T}_{k}^{+}$ and $\mathcal{T}_{k}^{-}$, we
have for any $\tau\in\mathcal{T}_{k}^{+}$ and any
$\tau^{\prime}\in\mathcal{T}_{k}^{-}$
$\frac{w(\tau)}{w(\tau^{\prime})}=\frac{q(\tau)\exp((\phi(\tau)-\phi(\tau^{\prime}))^{\top}\Phi_{k})}{q(\tau^{\prime})}\geq\frac{q(\tau)}{q(\tau^{\prime})}e^{\tilde{\gamma}}$.
Hence

$\displaystyle\frac{W_{k}^{+}}{W_{k}^{-}}=\frac{\sum_{\tau\in\mathcal{T}_{k}^{+}}w(\tau)}{\sum_{\tau\in\mathcal{T}_{k}^{-}}w(\tau)}\geq\frac{\sum_{\tau\in\mathcal{T}_{k}^{+}}q(\tau)}{\sum_{\tau\in\mathcal{T}_{k}^{-}}q(\tau)}e^{\tilde{\gamma}}\geq\frac{(1-\zeta)Q_{k}}{\zeta
Q_{k}}e^{\tilde{\gamma}}=\frac{(1-\zeta)e^{\tilde{\gamma}}}{\zeta}.$

Thus we have
$\frac{\zeta+(1-\zeta)e^{\tilde{\gamma}}}{(1-\zeta)e^{\tilde{\gamma}}}W_{k}^{+}\geq
W_{k}$. As a consequence,

$\displaystyle\frac{w(\tau)}{W_{k}}\geq\frac{(1-\zeta)e^{\tilde{\gamma}}}{\zeta+(1-\zeta)e^{\tilde{\gamma}}}\frac{w(\tau)}{W_{k}^{+}}.$
(6)

On the other hand, we have

$\displaystyle\frac{w(\tau)}{W_{k}^{+}}$
$\displaystyle=\frac{q(\tau)}{\sum_{\tau^{\prime}\in\mathcal{T}_{k}^{+}}q(\tau^{\prime})\exp((\phi(\tau^{\prime})-\phi(\tau))^{\top}\Phi_{k})}$
$\displaystyle\geq\frac{q(\tau)}{\sum_{\tau^{\prime}\in\mathcal{T}_{k}^{+}}q(\tau^{\prime})\exp(2r_{k}\lVert\Phi_{k}\rVert)}$
$\displaystyle=\frac{q(\tau)\exp(-2r_{k}\lVert\Phi_{k}\rVert)}{Q_{k}^{+}}$
$\displaystyle\geq\frac{q(\tau)\exp(-2r_{k}\lVert\Phi_{k}\rVert)}{Q_{k}}$ (7)

where the inequality follows from
$(\phi(\tau^{\prime})-\phi(\tau))^{\top}\Phi_{k})\leq\lVert\phi(\tau^{\prime})-\phi(\tau)\rVert\lVert\Phi_{k})\rVert\leq
2r_{k}\lVert\Phi_{k}\rVert$. Combining Eq. 4-Eq. 7, for any
$\tau\in\mathcal{T}_{k}$, we have

$\displaystyle p(\tau\mid\Phi_{k})$
$\displaystyle=\frac{w(\tau)}{W}\geq\frac{W_{k}}{W}\frac{w(\tau)}{W_{k}}$
$\displaystyle\geq\frac{(1-\zeta)Q_{k}\exp(\tilde{d})}{(1-\zeta)Q_{k}\exp(\tilde{d})+Q_{\sim
k}}\frac{(1-\zeta)e^{\tilde{\gamma}}}{\zeta+(1-\zeta)e^{\tilde{\gamma}}}\frac{q(\tau)\exp(-2r_{k}\lVert\Phi_{k}\rVert)}{Q_{k}}$
$\displaystyle=\frac{(1-\zeta)q(\tau)\exp(\tilde{d}-2r_{k}\lVert\Phi_{k}\rVert)}{(1-\zeta)Q_{k}\exp(\tilde{d})+Q_{\sim
k}}\frac{(1-\zeta)e^{\tilde{\gamma}}}{\zeta+(1-\zeta)e^{\tilde{\gamma}}}$

Now, for any $\tau\notin\mathcal{T}_{k}$, we have

$\displaystyle p(\tau\mid\Phi_{k})$
$\displaystyle=\frac{w(\tau)}{\sum_{\tau^{\prime}\in\mathcal{T}}w(\tau^{\prime})}$
$\displaystyle\leq\frac{w(\tau)}{\sum_{\tau^{\prime}\in\mathcal{T}_{k}^{+}}w(\tau^{\prime})+w(\tau)}$
$\displaystyle\leq\frac{q(\tau)}{(1-\zeta)Q_{k}\exp(\tilde{d})+q(\tau)},$

where the last inequality follows from Lemma 5. ∎

###### Proof of Theorem 1.

Consider an arbitrary $\tau_{i}$. Assume that $\tau_{i}\in C_{k}$, and
consider $k^{\prime}\neq k$, then by Lemma 2,

$\displaystyle p(\tau_{i}\mid\Phi_{k})$
$\displaystyle\geq\frac{(1-\zeta)q(\tau_{i})e^{\tilde{d}-2r_{k}\lVert\Phi_{k}\rVert}}{(1-\zeta)Q_{k}e^{\tilde{d}}+Q_{\sim
k}}\frac{(1-\zeta)e^{\tilde{\gamma}}}{\zeta+(1-\zeta)e^{\tilde{\gamma}}},$
$\displaystyle p(\tau_{i}\mid\Phi_{k^{\prime}})$
$\displaystyle\leq\frac{q(\tau_{i})}{(1-\zeta)Q_{k^{\prime}}e^{\tilde{d}}+q(\tau_{i})}.$

This gives us the following bound

$\displaystyle\frac{\rho_{k}^{(0)}p(\tau_{i}\mid\Phi_{k})}{\rho_{k^{\prime}}^{(0)}p(\tau_{i}\mid\Phi_{k^{\prime}})}\geq\frac{(1-\zeta)^{2}e^{\tilde{\gamma}}}{\zeta+(1-\zeta)e^{\tilde{\gamma}}}\frac{|C_{k}|((1-\zeta)Q_{k^{\prime}}e^{\tilde{d}}+q(\tau_{i}))}{|C_{k^{\prime}}|((1-\zeta)Q_{k}e^{\tilde{d}}+Q_{\sim
k})}e^{\tilde{d}-2r_{k}\lVert\Phi_{k}\rVert}\geq\beta.$

Hence we have

$\displaystyle u_{ik}^{(1)}$
$\displaystyle=\frac{\rho_{k}^{(0)}p(\tau_{i}\mid\theta_{k}^{(0)})}{\sum_{k^{\prime}}\rho_{k^{\prime}}^{(0)}p(\tau_{i}\mid\theta_{k^{\prime}}^{(0)})},$
$\displaystyle=\frac{\rho_{k}^{(0)}p(\tau_{i}\mid\theta_{k}^{(0)})}{\rho_{k}^{(0)}p(\tau_{i}\mid\theta_{k}^{(0)})+\sum_{k^{\prime}\neq
k}\rho_{k^{\prime}}^{(0)}p(\tau_{i}\mid\theta_{k^{\prime}}^{(0)})},$
$\displaystyle\geq\frac{\beta}{\beta+K-1},$

where the inequality is obtained with the help of Lemma 3 (in supplementary
file). Since $u_{ik}^{(0)}=1$, we have

$\displaystyle\sum_{k^{\prime}}|u_{ik^{\prime}}^{(1)}-u_{ik^{\prime}}^{(0)}|$
$\displaystyle=2|u_{ik}^{(1)}-1|$ (8)
$\displaystyle\leq\frac{2(K-1)}{\beta+K-1}.$ (9)

Since at least $1-\delta$ of the trajectories are typical, and for the
remaining trajectories,
$\sum_{k^{\prime}}|u_{ik^{\prime}}^{(1)}-u_{ik^{\prime}}^{(0)}|\leq 2$, we
have

$\displaystyle\frac{1}{|\mathcal{D}|}\sum_{i}\sum_{k}|u_{ik}^{(1)}-u_{ik}^{(0)}|$
$\displaystyle\leq 2\delta+(1-\delta)\frac{2(K-1)}{\beta+K-1}.$

∎

##  Appendix B Societal Impact Discussion

Our work is mainly algorithmic and theoretical and therefore somewhat
indirectly linked to potential negative societal impacts - however we briefly
discuss such potential impacts here.

#### Methodology.

On the methodology side, our LiMIIRL algorithm could help enable the
application of MI-IRL methods to larger or more substantive real-world
problems, and our GEVD metric also provides insights on when these Multi-
Intent techniques may work well.

Such Multi-Intent IRL methods allow for teasing-out individual user
preferences in a cohort of un-labelled data - as such, they might be
considered to pose a slightly higher risk in terms of surveillance or
revelation of user preferences, compared to previous work on the (single
intent) IRL problem. However for the most part, our present work mostly
magnifies any existing potential negative or positive impacts of IRL methods
generally. The most common IRL algorithms function by observing state and
action sequences, which typically requires consent of the subject (c.f. state-
only observations which can often be collected by surveillance in the absence
of consent or even in adversarial contexts) - we consider this to be a strong
mitigating factor regarding the potential negative impacts of IRL algorithms
as a class of machine learning models. Furthermore, in our work, we are also
concerned with learning simple (linear) rewards for the purpose of
understanding behaviour, rather than complicated (e.g. deep neural network)
rewards for replicating behaviour through apprenticeship learning. As such,
our models do not directly interact with the real world in the sense that e.g.
an apprenticeship learning agent might, but rather are useful for
interrogating the world and building a better understanding of certain
behaviours, which potentially limits or mitigates negative impact from this
work.

#### Application.

The example application that we consider (driver behaviour forecasting) is
incidental to our methodological contributions and was selected in part due to
it’s low potential for negative societal impacts, and large potential for
positive societal impact.

##  Appendix C Evaluation Measures for MI-IRL Algorithms

We provide some additional comments and insight on our MI-IRL evaluation
measures. Implementations of the below measures are included in our open-
source project repository.

#### Clustering Performance – ANID metric.

Given a set $\mathds{S}$ of $N$ items, a hard (or patitional) clustering
divides the set into non-overlapping sub-sets,
$\mathds{U}\triangleq\\{\mathds{U}_{1},\dots,\mathds{U}_{K_{1}}\\}$ with
$\bigcup_{i=1}^{K_{1}}\mathds{U}_{i}=N$ and
$\mathds{U}_{i}\bigcap\mathds{U}_{j}=\emptyset~{}\forall j\neq i$. Given a
second hard clustering
$\mathds{V}\triangleq\\{\mathds{V}_{1},\dots,\mathds{V}_{K_{2}}\\}$, the
contingency table $\bm{N}$ with elements
$n_{ij}\triangleq\lvert\mathds{U}_{i}\bigcap\mathds{V}_{j}\rvert$ and
marginals $a_{i}\triangleq\sum_{j=1}^{K_{2}}n_{ij}$ and
$b_{j}\triangleq\sum_{i=1}^{K_{1}}n_{ij}$ allows calculating various
information-theoretic measures about the two clusterings,

$\displaystyle
H(\mathds{U})\triangleq-\sum_{i=1}^{K_{1}}\frac{a_{i}}{N}\log\frac{a_{i}}{N},\quad$
$\displaystyle\quad
H(\mathds{V})\triangleq-\sum_{j=1}^{K_{2}}\frac{b_{i}}{N}\log\frac{b_{i}}{N},$
$\displaystyle
H(\mathds{U}\mid\mathds{V})\triangleq-\sum_{i=1}^{K_{1}}\sum_{j=1}^{K_{2}}\frac{n_{ij}}{N}\log\frac{n_{ij}/N}{b_{j}/N},\quad$
$\displaystyle\quad
H(\mathds{V}\mid\mathds{U})\triangleq-\sum_{i=1}^{K_{1}}\sum_{j=1}^{K_{2}}\frac{n_{ij}}{N}\log\frac{n_{ij}/N}{a_{i}/N},$
$\displaystyle H(\mathds{U},\mathds{V})=H(\mathds{V},\mathds{U})$
$\displaystyle\triangleq-\sum_{i=1}^{K_{1}}\sum_{j=1}^{K_{2}}\frac{n_{ij}}{N}\log\frac{n_{ij}}{{N}},$
$\displaystyle I(\mathds{U},\mathds{V})=I(\mathds{V},\mathds{U})$
$\displaystyle\triangleq\sum_{i=1}^{K_{1}}\sum_{j=1}^{K_{2}}\frac{n_{ij}}{N}\log\frac{n_{ij}/N}{a_{i}b_{j}/N^{2}},$

where $H$ is a (Shannon) entropy, and $I$ is known as the mutual information
\- a measure of how much information the two clustering share.

Various measures based on these terms have been proposed as ways to evaluate
the similarity of hard clusterings, however recent work has highlighted the
strengths (as compared to other metrics that have historically been popular,
such as the clustering purity [40], Rand Index (or adjusted variant) [33], and
other information theoretic measures) of the max-Normalized Information
Distance (NID) due to it’s beneficial theoretical and empirical properties
[37]. The NID is given by,

NID $\displaystyle\triangleq
1-\frac{I(\mathds{U},\mathds{V})}{\max\\{H(\mathds{U}),H(\mathds{V})\\}}.$
(10)

In the context of multi-modal IRL, an algorithm may in-fact produce a so-
called soft (probabilistic) assignment of demonstrations to behaviour modes. A
soft clustering of $N$ items into $K_{1}$ clusters can be represented by a
responsibility matrix $\bm{U}\in\mathds{R}^{N\times K_{1}}$ with elements
$u_{ij}\geq 0$ and $\sum_{j=1}^{K_{1}}u_{ij}=1~{}\forall i$. Given a second
soft clustering $\bm{V}\in\mathds{R}^{N\times K_{2}}$, work by [2] proposes an
analogous contingency table, $\bm{N}^{*}\triangleq\bm{U}^{\top}\bm{V}$, which
allows applying any metric based on contingency tables to the case of soft
clusters, and subsequent work by Lei et al. [19, 20] shows that the NID is
again a good choice of metric for evaluating soft clusterings. In our
experiments, we use the adjusted Normalized Information Distance (ANID), which
extends the NID to control for random chance - without this adjustment, the
apparent agreement between clusters will be positively correlated with the
number of clusters $K_{1}$ or $K_{2}$ [34]. The ANID is given by,

ANID $\displaystyle\triangleq
1-\frac{I(\bm{U},\bm{V})-\mathbb{E}[I(\bm{U}^{\prime},\bm{V}^{\prime})]}{\max\\{H(\bm{U}),H(\bm{V})\\}-\mathbb{E}[I(\bm{U}^{\prime},\bm{V}^{\prime})]},$
(11)

where $\bm{U}^{\prime}$ and $\bm{V}^{\prime}$ are from an appropriate random
clustering model – for hard clusters hypergeometric models are commonly used,
an in our soft clustering case we choose
$\text{dim}(\bm{U}^{\prime})=\text{dim}(\bm{U})$ and sample rows from the
uniform Dirichlet distribution $u_{i}\sim\text{GEM}(1/K_{1})$, and similarly
for $\bm{V}^{\prime}$. The ANID has a number of useful properties - it is
stochastically normalized to the range $[0,1]$, with values approaching zero
indicating perfect agreement between the two clusters. Furthermore, in the
limit $N\rightarrow\infty$, the ANID obeys the triangle equality and converges
to a proper metric [34].

#### Reward Ensemble Performance – GEVD metric.

To evaluate single-intent IRL algorithms, Choi and Kim [7] proposed the
Inverse Learning Error (ILE), which was further refined by Bogert et al. [5],

$\displaystyle\text{ILE}(R_{\text{GT}},R_{\text{L}})$
$\displaystyle\triangleq\lVert\bm{v}(\pi^{*}_{R_{\text{GT}}})-\bm{v}(\pi^{*}_{R_{\text{L}}})\rVert_{1},$
$\displaystyle\in[0,\infty)$ (12)

where $\bm{v}(\pi)$ indicates the vector of state values w.r.t. the _ground
truth_ reward $R_{\text{GT}}$ for any arbitrary policy $\pi$, and
$\pi^{*}_{R_{\text{GT}}}$ and $\pi^{*}_{R_{\text{L}}}$ denote the optimal
policy w.r.t. the ground truth and learned reward functions respectively. The
ILE is an appropriate measure of regret for the IRL context, however has the
limitation that it grows with the number of states in the MDP, making it
difficult to compare across different tasks, and difficult to apply to MDPs
with continuous state spaces.

Instead, Levine et al. [21] proposed a generalisation333EVD generalized ILE in
the sense that ILE can be viewed as EVD computed under a uniform starting
state distribution. of this measure, known as the Expected Value Difference
(EVD),

$\displaystyle\text{EVD}(R_{\text{GT}},R_{\text{L}})$
$\displaystyle\triangleq\mathbb{E}_{s\sim
p_{0}}[v(\pi^{*}_{R_{\text{GT}}})]-\mathbb{E}_{s\sim
p_{0}}[v(\pi^{*}_{R_{\text{L}}})]$ $\displaystyle\in[0,\infty)$ (13)

where $v(\pi)$ indicates the state-value function for the arbitrary policy
$\pi$ w.r.t. the _ground truth_ reward $R_{\text{GT}}$, and
$\pi^{*}_{R_{\text{GT}}}$ and $\pi^{*}_{R_{\text{L}}}$ denote the optimal
policy w.r.t. the ground truth and learned reward functions respectively.
While the EVD has the same range as the ILE444N.b. it is possible to upper-
bound these single-intent IRL measures more tightly, using the same approach
we apply to our GEVD metric (see the main text)., the upped bound does not
necessarily depend on the full set of states in the MDP, and we can more
easily compute the EVD for continuous state-space MDPs.

Unlike a single-intent IRL method, MI-IRL algorithms output a set of learned
reward function-weight pairs
$\mathds{R}_{\text{L}}=\\{(w^{\prime}_{i},R_{\text{L}_{i}})\\}_{i=1}^{K_{1}}$,
which we desire to compare with the set of ground truth reward functions and
their corresponding weights
$\mathds{R}_{\text{GT}}=\\{(w_{j},R_{\text{GT}_{j}})\\}_{j=1}^{K_{2}}$. To
achieve this comparison, we find the most optimistic soft matching of learned
and ground truth rewards. Given $e_{ij}$, the matrix of EVD values for the
$i$-th learned model w.r.t. the $j$-th ground truth model, we define the
Generalized Expected Value Difference (GEVD) as,

$\displaystyle\text{GEVD}(\mathds{R}_{\text{GT}},\mathds{R}_{\text{L}})$
$\displaystyle\triangleq\operatorname*{arg\,min}_{\\{w_{ij}\\}:\sum_{j}w_{ij}=w_{i},\sum_{i}w_{ij}=w^{\prime}_{j}}\sum_{i,j}w_{ij}~{}e_{ij},$
$\displaystyle\in[0,\frac{\max_{k}\Delta_{k}}{1-\gamma}]$ (14)

where
$\Delta_{k}=\max_{s,a,s^{\prime}}R_{{GT}_{k}}(s,a,s^{\prime})-\min_{s,a,s^{\prime}}R_{{GT}_{k}}(s,a,s^{\prime})$.
Computing the GEVD is equivalent to solving a minimum cost flow problem over a
dense directed graph from learned to ground truth reward modes, where

  1. (a)

there is a single unity demand source (S) and sink (T), and

  2. (b)

the inner and outer edges have zero cost and capacity equal to the weight of
that mixture component, and

  3. (c)

the inside edges have unity capacity and costs equal to the pairwise EVD
values,

a construction we illustrate in Fig. 2.

Figure 2: The GEVD Score finds the most optimistic pairing between a learned
mixture model $\\{\mathds{R}_{\text{L}_{i}}\\}_{i=1}^{K_{1}}$ and the ground
truth mixture model $\\{\mathds{R}_{\text{GT}_{j}}\\}_{j=1}^{K_{2}}$.

##  Appendix D LiMIIRL algorithm - extended results

We provide additional results for LiMIIRL on the ElementWorld problem when
using different single-intent IRL models, namely, MaxEnt IRL, ML-IRL, and
$\Sigma$-GIRL. In each case, we run a MI-IRL algorithm multiple times and
represent the runs using a boxplot. We use $100\times$ repeat experiments with
randomized seeds for the MaxEnt IRL plots, and $20\times$ repeat experiments
for the ML-IRL and $40\times$ repeat experiments for $\Sigma$-GIRL experiments
(both of which are much more computationally demanding to run). The boxes are
centered at the median and extend to the first quartile, with whiskers
extending to $1.5\times$ the Inter Quartile Range. Outlying values beyond $\pm
1.5$ IQR are shown with small diamonds. For all metrics, lower values are
better. The results are shown in Figs. 3, 4 and 5.

#### A note on $\Sigma$-GIRL Experiments

The ‘Multiple-Intent’ Expectation Maximization $\Sigma$-GIRL algorithm [31]
solves a similar but fundamentally different problem to that solved by
Multiple-Intent Maximum Likelihood IRL [3] and Multiple-Intent Maximum Entropy
IRL (the primary algorithm used in our paper).

Namely, $\Sigma$-GIRL addresses a partially labelled variant of the Multiple-
Intent problem, where we have $N$ trajectories generated by $M\leq N$ agents,
who optimize for $K\leq M$ particular behaviour intents. In $\Sigma$-GIRL, the
mapping from trajectories to agents is known as part of the problem
definition. This information is used to form policy gradient Jacobian mean and
covariance estimates (one for each agent), which are then provided to the EM
process to cluster the agents into intents.

In contrast, our present work and the original MI ML-IRL algorithm by [3]
consider a fully-unsupervised version of the MI-IRL problem, where there is no
such notion of ‘agents’. Although the fully-unsupervised setting can be seen
as a special case of the partially supervised case with $M=N$ agents (i.e. one
trajectory per agent), the $\Sigma$-GIRL algorithm cannot be directly applied
in this context due to the need for more than one trajectory to estimate the
policy gradient Jacobian covariance matrix.

Nevertheless, we can utilise the LiMIIRL initialisation strategy for the un-
labelled part of the $\Sigma$-GIRL algorithm (clustering agents into intents),
and we include experimental results for this case below, run using code
provided by the original authors. Specifically, for each of the $M$ agents, we
compute the empirical feature expectation using their (known) individual sets
of demonstrations, then run a hard ($k$-means) or soft (GMM) clustering
procedure to compute the initial responsibility matrix $\\{u_{ik}^{(0)}\\}$
allocating agents to intents. We then use this responsibility matrix in lieu
of the first E-step of the MI $\Sigma$-GIRL EM routine, which proceeds to
iteratively allocate agent Jacobian matrices to behavioural intents. This is
functionally equivalent to the LiMIIRL MLE initialisation strategy, but using
the $\Sigma$-GIRL single-intent IRL algorithm as the underlying behaviour
model. It is less clear how to apply the LiMIIRL Mean initialisation method
with $\Sigma$-GIRL, however this may be possible by exploiting feature
transformations to convert the MDP feature domain to the simplex reward
parameter domain searched by the $\Sigma$-GIRL algorithm – an idea we leave
for future work.

Due to the semi-supervised nature of the $\Sigma$-GIRL algorithm, and it’s
prohibitive memory complexity, our $\Sigma$-GIRL experiments used the simple
continuous PuddleWorld domain from the original $\Sigma$-GIRL paper (Figure 2
from [31]).

(a) number of iterations

(b) wall time in seconds

(c) final mixture NLL

(d) clustering performance (ANID)

(e) reward ensemble performance (GEVD)

Figure 3:  ElementWorld results with multi-intent MaxEnt IRL. The label
‘Babeş-Vroman et al. 2011’ indicates EM with random initialisation. Although
all methods result in a similar final NLL distribution, we highlight that
there are significant differences in the other performance metrics, with the
hard-clustering strategy consistently performing best.

(a) number of iterations

(b) wall time in seconds

(c) final mixture NLL

(d) clustering performance (ANID)

(e) reward ensemble performance (GEVD)

Figure 4: ElementWorld results with multi-intent ML-IRL. The label ‘Babeş-
Vroman et al. 2011’ indicates EM with random initialisation. Similarly to
MaxEnt IRL (above), the hard clustering strategy consistently performs better
than other initialisation strategies.

(a) number of iterations.

(b) wall time in seconds.

(c) final mixture NLL

(d) clustering performance (ANID)

Figure 5: PuddleWorld results with semi-supervised multi-intent $\Sigma$-GIRL
(see explanation in Appendix D). The label ‘Babeş-Vroman et al. 2011’
indicates EM with random initialisation. The $\Sigma$-GIRL algorithm
differentiates between the reward feature function $\phi_{R}$ and the policy
feature function $\phi_{\pi}$ in this environment – we report results using
both as the choice of feature vector for LiMIIRL initialisation, and find that
they are roughly equivalent. For this problem, we find LiMIIRL leads to
ensembles with equivalent ANID and NLL scores and provides a small but not
statistically significant improvement on number of iterations and duration to
convergence. We hypothesize that LiMIIRL is less helpful in these experiments
(compared to the fully-unsupervised MI-IRL ElementWorld experiments) due to
one of two factors: (a) the simplicity of the continuous PuddleWorld problem
(i.e. it only has two behaviour intents), and/or (b) the fact that the
$\Sigma$-GIRL algorithm has already exploited the labels mapping trajectories
to agents, reducing the variance present in the resultant EM clustering
problem.

##  Appendix E LiMIIRL Sensitivity Analysis results

Below we include a series of figures plotting the results of our extensive
sensitivity analysis. We briefly describe the procedure used for each
experiment, and any interesting observations.

#### Number of demonstrations.

We varied the total number of demonstrations with
$N\in\\{20,40,100,200,400\\}$ to investigate the performance of our method in
the small- and large-data regimes.

Figure 6: Effect of varying number number of demonstrations $N$.

We observed that the number of iterations stays fairly constant, whereas the
wall time duration increases, suggesting that the M-Step (IRL reward solving),
not the E-Step (updating cluster allocations) is the more burdensome part of
the MI algorithm. LiMIIRL with hard clustering generally outperforms the other
initialisation strategies.

#### Cluster separation.

We tested the algorithm with deterministic dynamics as well as with wind
factor $w\in\\{0.05,0.1,0.15,0.2\\}$, where larger wind values correspond to
the behaviour intents being less separated in feature space (progressive
violation of Assumption A).

In Fig. 7, we plot the mean of the inter-cluster margin
$\mathbb{E}_{\\{\mathcal{T},\mathcal{T}^{\prime}\\}}[\min_{\tau\sim\mathcal{T},\tau^{\prime}\sim\mathcal{T}^{\prime}}\|\phi(\tau)-\phi(\tau^{\prime})\|]$
(where the expectation indicates all pairwise combinations of elements) with
$E=3$ elements as the wind factor is increased. This confirms that increasing
the stochasticity of the transition dynamics leads to progressive violation of
the cluster separation assumption.

Figure 7: Assumption 1 is progressively violated as the ElementWorld wind
factor is increased. The plot shows the mean inter-cluster scaled margin with
the 95% confidence interval over 10 repeat experiments.

Figure 8: Effect of varying separation of the behaviour clusters (achieved by
adjusting the ‘wind’ factor $w$ in the dynamics)

We observed that increasing the wind factor (violating Assumption 1 more)
reduces the performance of all methods on all metrics, however in general,
LiMIIRL initialisation with hard clustering still outperforms the other
method.

#### Number of clusters.

We fixed $E=3$ and varied the number of learned clusters from $K=1$ to $5$ to
see how LiMIIRL performs when the number of learned clusters is mis-specified
or unknown (i.e. under- or over-clustering).

Figure 9: Effect of varying numbers of clusters $K$ (we fix $E=3$).

We observe that our LiMIIRL initialisation strategy appears most helpful when
the number of clusters is under, or correctly specified for the environment.
We note that while the mixture NLL generally increases proportional to $K$,
the ANID and GEVD metrics reach a minima / asymptote respectively at $K=3$ –
this confirms that these measures are suitable for evaluating reward ensemble
performance, even for the case when the number of learned clusters is mis-
specified.

We also note that in practice, the value of $K$ can be estimated using
heuristics such as the Bayesian Information Criteria, using a non-parametric
clustering as a pre-processing step, or using cross-fold validation.

#### Number of elements.

We generated ElementWorld configurations with $K=E\in\\{2,3,4,5,6\\}$ to test
the performance of our method as the number of behaviour intents increases.

Figure 10: Effect of varying number number of ground truth elements $E$ (we
fix $K=E$)

We observe that, as expected, the performance of all metrics (except the
supervised baseline) gets worse as the number of behaviour intents increases.
LiMIIRL with hard clustering appears to provide even more benefit over other
initialisation strategies, especially for large numbers of behaviour intents.

#### Cluster imbalance.

We tested the performance of our method when the behaviour intentions are not
uniformly present in the demonstration dataset. Instead of sampling
demonstration policies uniformly, we selected demonstration policies from the
ground truth ensemble according to a normalized geometric distribution
$\rho_{k}\propto p(1-p)^{k}$, varying the parameter
$p\in\\{0.0,0.1,0.2,0.3,0.4\\}$.

Figure 11: Effect of varying a varying degree of demonstration data cluster
imbalance (achieved by sampling demonstrations from the ground truth ensemble
under a geometric distribution with parameter $p$).

We observe that LiMIIRL with hard clustering appears once again to outperform
the other initialisation strategies, even in the presence of heavily skewed
cluster sizes. Interestingly, the soft initialisation (based on a Gaussian
Mixture Model) appears particularly sensitive to cluster imbalance, suggesting
this method should be avoided when the true cluster distribution is unknown.

##  Appendix F Driver Forecasting Experiment: Learned Reward Ensembles

Below we include plots that visualise the best learned reward ensemble for
each of the algorithms LiMIIRL-hard, LiMIIRL-soft, and for the EM algorithm
with random initialization [3]. Each figure is divided into sections
corresponding to the specific feature - e.g. road type, or geographical
region. Within each section, the x-axis shows the feature dimensions, and the
plot indicates the learned reward parameter for that feature dimension. Each
figure shows a plot for each reward in the learned ensemble, and the plot
thickness is proportional to the ensemble component weight $\rho_{k}$.

(a) Best learned reward ensemble for LiMIIRL-hard.

(b) Best learned reward ensemble for LiMIIRL-soft.

(c) Best learned reward ensemble for Babeş-Vroman et al. [3].

Figure 12: Learned reward ensembles for the Porto driver behaviour forecasting
experiment.