# Convex Online Video Frame Subset Selection using Multiple Criteria for Data
Efficient Autonomous Driving

Soumi Das  Harikrishna Patibandla
IIT Kharagpur
Kharagpur  India
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Suparna Bhattacharya  Kshounis Bera
Hewlett Packard Enterprise India
Bangalore  India
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Niloy Ganguly  Sourangshu Bhattacharya
IIT Kharagpur
Kharagpur  India
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Training vision-based Urban Autonomous driving models is a challenging
problem, which is highly researched in recent times. Training such models is a
data-intensive task requiring storage and processing of vast volumes of
(possibly redundant) driving video data. In this paper, we study the problem
of developing data-efficient autonomous driving systems. In this context, we
study the problem of multi-criteria online video frame subset selection. We
study convex optimization based solutions and show that they are unable to
provide solution with high weightage to loss of selected video frames. We
design a novel convex optimization based multi-criteria online subset
selection algorithm which uses a thresholded concave function of selection
variables. We also propose and study submodular optimization based algorithm.
Extensive experiments using driving simulator CARLA shows that we are able
drop 80% of the frames, while succeeding to complete 100% of the episodes
w.r.t. the model trained on 100% data, in the most difficult task of taking
turns. This results in training time of less than 30% compared to training on
the whole dataset. We also perform detailed experiments on prediction
performances of various affordances used by the Conditional Affordance
Learning (CAL) model, and show that our subset selection improves performance
on the crucial affordance “Relative Angle” during turns.

##  1 Introduction

Many A.I. applications, including autonomous driving systems [19, 10], process
large amount of video data for training complex deep learning models. However,
much of the input video contains redundant information from the task point of
view. For example, in case of autonomous driving, training using many frames
on straight road sections may not be necessary; while one may need a lot of
frames in the turns for training. In this paper, we study the problem of
selecting video frame subsets, which are most informative as training data for
one or more such tasks. We are also interested in developing a selection
algorithm that can be deployed on edge devices, thus minimizing edge to core
transfer.

Autonomous driving models typically involve multiple prediction tasks, e.g.
prediction of 6 affordances in conditional affordance learning (CAL) model
[19]. The importance of prediction accuracy of a particular task towards the
end objective is a complex function of the situation. For example, we find
that error in prediction of relative angle during the turns is critical
towards achieving higher episode completion, since the vehicle is able to
easily recover from such errors during straight stretches. Hence, we are
interested in designing a video frame subset selection algorithm which is able
to incorporate multiple criteria arising from the different tasks, situations
(e.g. turns, presence of pedestrians, etc) and existing model properties (e.g.
prediction loss).

The problem of video frame subset selection has been studied in various
contexts, including video summarization [11, 16], video recognition[23], video
fast forwarding [14], etc. Broadly, the techniques can be classified into two
classes: (1) deep reinforcement learning based methods, which learn a frame
skipping network, with reward for better performance [14, 22], or more
confidence [23] on the end task; and (2) external criteria based methods which
optimize a global criterion between selected frames and whole video, e.g.
perceptual similarity [11], manifold spanning [13], etc. For our setting, the
first class of methods are too expensive, since they require multiple
evaluations of the end task objective, which in our case is the fraction of
test episodes completed.

In this paper, we build on the online subset selection framework [11], where
at each step, an existing set of selected frames is supplemented by the most
relevant frames from an incoming set, based on the total dissimilarity between
selected frames and incoming frames. This framework was extended to
incorporate pointwise loss of the selected frames in a composite criteria [8].
These techniques were applied to video summarization [11] and semantic
segmention [8]. To the best of our knowledge, these techniques have not been
used in the autonomous driving setting. Moreover, through a rigorous analysis,
we show that, the additive incorporation of pointwise loss criteria in [8]
suffers from selection of fewer frames from incoming set as we provide higher
weightage to the pointwise criteria. This is due to the fact that additive
incorporation suffers from multiple counting of loss of selected points thus
leading to selection of fewer frames. We propose a novel thresholded
formulation (ThreshMCOSS) of incorporation of pointwise criteria, which leads
to a convex selection objective leading to efficient algorithm.

We also propose a natural set-function based criteria for incorporation of
pointwise multiple criteria, which is also shown to be a sub-modular function,
thus opening up the possiblity of using approximate submodular optimization
algorithms. In an thorough empirical study, we show that both on synthetic
data, as well as data from selection of video frames for autonomous driving,
the convex relaxation based algorithm performs better than state of the
approximations algorithms for submodular maximization [3, 4].

We perform the autonomous driving experiments by training on a dataset of more
than 100,000 video frames collected from our testbed of CARLA simulator [10],
and testing on 40 episodes of from 4 different settings, with more than 6000
video frames. Through extensive experimentation, we find that bucketwise
relative angle loss as a good criteria along with total multi-task loss and
SIFT similarity between pairs of frames provides an ideal selection criteria.
Our experiments using the CAL model [19], show that we can achieve a 100:20
compression (selecting 1 in 5 frames) which does not lead to any loss in
episode completion, even though the accuracies on individual tasks decrease
marginally.

###  1.1 Related Work

We describe two broad classes of relevant prior works: (a) Learning model for
self driving cars, and (b) Subset selection. The autonomous driving literature
has witnessed many different kinds of learning approaches: (1) modular
pipeline or mediated perception [10] [21] [5] [20] [25], (2) imitation
learning [17] [1] [7] [2] [24], and reinforcement learning [10] [15] [18].
Deep Imitation Learning based method Conditional Affordance Learning (CAL)
[19] learns models for multiple affordances in a multi-task setting, using
driving video data collected from the driving simulator CARLA [10]. It claims
better episode completion over other imitation learning based approaches e.g.
CARLA [10] or conditional imitation learning [7]. Hence, in this work we
demonstrate effectiveness of our frame subset selection algorithms using CAL
as the learning model with driving simulator CARLA [10]. However, our approach
is complementary to recent reinforcement learning based approaches e.g. [18],
as discussed in section 2.

Video frame subset selection:
Recent online subset selection approaches can be divided into two broad
classes (1) deep learning based, and (2) based on optimization of some input
criteria. The first class of techniques [14], [22] [23] depend on selection
networks added to the pipeline of existing tasks and are trained jointly. They
are able to learn complex selection criteria through deep models, but do not
come with any stated selection criteria, w.r.t. which the selection is
optimal. These methods are jointly trained with the end objective, e.g. video
recognition for [22] and [23], and are typically too expensive to be deployed
on edge devices.

The second class of techniques, which are also closest to us, selects the data
points based on different defined criteria. These criteria include
reconstruction error [6], linear dependency [13], perceptual similarity [11]
or criteria based on end tasks such as distinctiveness and uncertainty [12]
[8]. [13] recently proposed an online approach based on linear dependence
criteria. However for the current problem, we build on the pairwise criteria
based approach proposed in [11], and extended to include multiple pairwise and
pointwise criteria [8]. While these approaches were used for the problems of
Video summrization [11] and semantic segmentation [8], their setting provides
flexibility of incorporating multiple different types of criteria, which is
relevant to our application. We provide detailed comparison with these
approaches.

##  2 Data Efficient Autonomous Driving

In this section, we describe the problem of data efficient training of
autonomous driving models, with the core idea being selection of relevant
video segments in an online setting. We formulate this problem as an online
subset selection problem (OSS) for selecting subsets of video frames, given
input signals from existing selected video frames, and the trained model,
which throw up multiple input criteria - both for pairs of input frames and
for single input frame. Section 2.1 describes the setup of data efficient
autonomous driving and its connection to multi-criteria OSS problem
formulation. Section 2.2 points out a drawback with existing multi-criteria
OSS formulation. Sections 2.3 and 2.4 describe our new formulations for the
multi-criteria OSS problem.

###  2.1 Problem setup and OSS

Training of vision based autonomous driving models [19, 18] requires
processing of large amounts of annotated video data. In many cases, the videos
are collected in episodes over a period of time, leading to processing and
training of models in batches which are ordered in time. Hence, the batchwise
OSS scheme discussed in [11], is an ideal setting for selection of video
frames in this context. We denote a complete dataset as
$\mathcal{D}=\\{(x_{i},y_{i}),\ i=1,\dots,n\\}$ where $n$ is the total number
of datapoints (annotated video frames) in the dataset, $x_{i}$ are the
features extracted from video frames, and labels $y_{i}$ corresponding to
various learning tasks, e.g. affordances [19]. Let $X_{t}=\\{(x_{i},y_{i}),\
i=1,\dots,m\\},\ t=1,\dots,T$ denote the $t^{th}$ batch of episodes collected,
where $m$ denotes the number frames in a batch 111Equal batch size is for
simplicity of exposition, not a requirement. Hence $mT=n$. We also define the
cumulative sets $C_{t}=\cup_{i=1}^{t}X_{i}$ denoting all data collected till
batch $t$. We are interested in constructing representative set
$R_{t}\subseteq C_{t}$, which consists of a representative set of frames till
batch $t$. The intention here is that an autonomous driving model $M_{t}$
trained on the cummulative set $C_{t}$, should perform similarly to another
model $M^{\prime}_{t}$ trained on the representative set of frames $R_{t}$ in
terms of an end performance metric, e.g. the episode completion metric used in
[19]. Furthermore, the size of $R_{t}$ should be small so that $R_{t}$ uses
lower storage space and communication bandwidth, and training of
$M^{\prime}_{t}$ potentially takes lower time. An algorithm for selection of
$R_{t+1}$ from $X_{t+1}$, given $C_{t}$, and $M^{\prime}_{t}$ thus constitutes
a data efficient scheme for training of autonomous driving models, since we
are only storing and processing $R_{t}$’s. Note that, this scheme can also be
used in the reinforcement learning schemes for improvement of driving policies
such as the one described in [18], where $X_{t}$ can be taken from the replay
buffer at iteration $t$.

For the OSS formulation, we focus on an input batch of episodes $X_{t+1}$. The
selection algorithm uses two input sets of frames $R_{t}$ and $X_{t+1}$, here
referred to as the old set (superscript $o$) and new set (superscript $n$)
respectively, following notation used in [11]. Let $d^{o}_{ij}$ denote a
dissimilarity measure between new frame $i$ (from $X_{t+1}$) and old frame $j$
(from $R_{t}$), and $d^{n}_{ij}$ denote the dissimilarity between new frames
$i$ and $j$ (both from $X_{t+1}$). The OSS formulation minimizes the a
composite criteria with two parts: (1) total dissimilarity between the
”representative frames” (either from new or old set) and the incoming frame it
represents, and (2) number of representative frames from the new set. Let
$z_{ij}^{o},z_{ij}^{n}$ be the relaxed binary assignment variables
($Z_{ij}\in[0,1])$, where $z_{ij}^{o}=1$ denotes that the representative of
$i^{th}$ new example ( $(x_{i},y_{i})\in X_{t+1}$) is $j^{th}$ old example
($(x_{j},y_{j})\in R_{t}$), and $z_{ij}^{n}=1$ denotes that representative of
$i^{th}$ new example ($(x_{i},y_{i})\in X_{t+1}$) is the $j^{th}$ new example
($(x_{j},y_{j})\in X_{t+1}$). Otherwise, $z_{ij}=0$. Hence any solution for
optimal representative allocation should satisfy the constraint:
$\sum_{j=1}^{|R_{t}|}z_{i,j}^{o}+\sum_{j=1}^{m}z_{i,j}^{n}=1$, asserting that
every frame $i\in X_{t+1}$ has exactly one representative. The objective
function can be written as:

$\displaystyle
L(z^{o}_{ij},z^{n}_{ij})=\sum_{i=1}^{m}\sum_{j=1}^{|R_{t}|}z_{ij}^{o}d^{o}_{ij}+\sum_{i,j=1}^{m}z_{ij}^{n}d^{n}_{ij}+\lambda\sum_{j=1}^{m}\|[z_{1,j}^{n}\dots
z_{m,j}^{n}]\|_{p}$

Das et al. [8] has incorporated both pairwise scores (e.g. distance $d_{ij}$
between pairs of frames $i,j$) and pointwise scores (e.g. negative loss
$-L_{i}$ for the frame $i$). The modified cumulative dissimilarity function
$Q_{ij}$ is a weighted sum of $d_{ij}$ and $L_{j}$ \- the loss incurred by the
representative point. Thus $Q_{ij}=\rho d_{ij}-(1-\rho)L_{j}$. Let $L^{n}_{i}$
denote the pointwise attribute (here loss value) for datapoint $i$ in
$X_{t+1}$ and analogously for $L^{o}_{i}$ (denoting loss for datapoint $i$ in
$R_{t}$). The final formulation is:

$\displaystyle\min_{z^{o}_{ij},z^{n}_{ij}}\sum_{i=1}^{m}\sum_{j=1}^{|R_{t}|}z_{ij}^{o}Q^{o}_{ij}+\sum_{i,j=1}^{m}z_{ij}^{n}Q^{n}_{ij}+\lambda\sum_{j=1}^{m}\|[z_{1,j}^{n}\dots
z_{m,j}^{n}]\|_{p}$ $\displaystyle
s.t.\sum_{j=1}^{|R_{t}|}z_{i,j}^{o}+\sum_{j=1}^{m}z_{i,j}^{n}=1,\ \forall i\in
X_{t+1}$ $\displaystyle z_{i,j}^{n},z_{i,j}^{o}\in[0,1],\ \forall i,j$ (1)

where $Q^{n}_{ij}=\rho d^{n}_{ij}-(1-\rho)L^{n}_{j}$ and $Q^{o}_{ij}=\rho
d^{o}_{ij}-(1-\rho)L^{o}_{j}$. This is a convex optimization problem which can
be solved efficiently for moderate sizes of sets $X_{t+1}$ and $R_{t}$ using
off the shelve solvers, e.g. CVXPY [9]. We call this formulation multi-critria
OSS (Phys. Rev. Lett.).

###  2.2 Analysis of Multi-Criteria OSS

While applying Phys. Rev. Lett. to our problem, we noticed that as we give
higher weightage to the pointwise component by choosing lower value of $\rho$,
the number of selected points decreases. From an application point of view,
this allows the pointwise score to have a limited impact on the set of points
selected. This might be tolerable in certain applications, e.g. semantic
segmentation where the perceptual dissimilarity measure contains sufficient
information for frame subset selection. However for the application of
autonomous driving, we find that task-wise and situation-wise losses have much
more impact on the quality of frames selected.

To understand the mechanism through which this problem arises, we observe that
using only pointwise metric yields a maximum of one representative for all
images belonging to incoming set $X_{t+1}$. This is the setting when $\rho$ =
0. We have $Q_{ij}^{o}$ = $-(1-\rho)L_{j}^{o}$ and $Q_{ij}^{n}$ =
$-(1-\rho)L_{j}^{n}$, both of them are constant across $i$. The representative
$j$ of any instance $i\in X_{t+1}$ $(i=1,...,m)$ will be from $X_{t+1}$ if
$L_{j}^{n}>L_{j^{\prime}}^{\forall}j^{\prime}\in X_{t+1}$ in which case only
one point will be selected (see Corollary 1.1). Otherwise the representative
will be from $R_{t}$, in which case no points are selected.

While the above intuitions are motivated for special case of $\rho=0$, the
ideas also apply to more general values of $0<\rho\leq 1$. We further
illustrate this by characterising the solution of formulation 2.1 in the
following theorem.

###### Theorem 1

Let $z_{ij}^{o}$ and $z_{ij}^{n}$ be the optimal solution for formulation 2.1.
A new frame $j\in X_{t+1}$ is selected as a representative frame for at least
one incoming frame $i\in X_{t+1}$, i.e. $z_{ij}^{n}=1$, only if the following
conditions hold:

  * •

For some incoming frame $i\in X_{t+1}$ , $Q^{n}_{ij}<Q^{n}_{ij^{\prime}}$, for
all $j^{\prime}\in X_{t+1}$ and $j^{\prime}\neq j$

  * •

For some incoming frame $i\in X_{t+1}$,
$Q^{n}_{ij}<\frac{\sum_{i^{\prime}=1}^{m}z_{i^{\prime},k}^{o}Q^{o}_{i^{\prime}k}+\lambda\|[z_{1,j}^{n}\dots
z_{m,j}^{n}]\|_{p}}{\|\mathbf{z}_{j}^{n}\|_{1}}$

where $k=argmin_{j}\sum_{i=1}^{m}z_{i,j}^{o}Q_{i,j}^{o}$, and
$\|\mathbf{z}_{j}^{n}\|_{1}=\sum_{i^{\prime}=1}^{m}z_{i^{\prime}j}^{n}$

Due to space constraints, we provide the formal proof in the supplementary
material. Note that the first condition states that there is at least one
frame $i$ in the incoming set whose cumulative dissimilarity $Q^{n}_{ij}$ is
lower than all other points. The second condition signifies that cumulative
dissimilarity $Q^{n}_{ij}$ between a representative $j$ and the point it is
representing $i$ is lower than minimal contribution from a potential
representative $k$ from existing set of selected examples $k\in R_{t}$. Next,
we provide two corollaries to illustrate our point. Corollary 1.1 illustrates
the conditions in theorem 1 for the special case of $\rho=0$. Since, the
dependence on $i$ is removed, it is easy to see that at most one $j\in
X_{t+1}$ will satisfy the condition.

###### Corollary 1.1

Let $z_{ij}^{o}$ and $z_{ij}^{n}$ be the optimal solution for formulation 2.1.
A new frame $j\in X_{t+1}$ is selected as a representative frame for at least
one incoming frame $i\in X_{t+1}$, i.e. $z_{ij}^{n}=1$, only if the following
conditions hold:

  * •

$L_{j}^{n}>L_{j^{\prime}}^{n}$ for all $j^{\prime}\in X_{t+1}$ and
$j^{\prime}\neq j$

  * •

$L^{n}_{j}>\frac{\sum_{i=1}^{m}z_{i,k}^{o}L_{k}^{o}-\lambda\|[z_{1,j}^{n}\dots
z_{m,j}^{n}]\|_{p}}{\|\mathbf{z}_{j}^{n}\|_{1}}$

where $k=argmin_{j}\sum_{i=1}^{m}z_{i,j}^{o}Q_{i,j}^{o}$, and
$\|\mathbf{z}_{j}^{n}\|_{1}=\sum_{i^{\prime}=1}^{m}z_{i^{\prime}j}^{n}$

###### Corollary 1.2

Let
$\Delta_{d}(i,j)=\|\mathbf{z}_{j}^{n}\|_{1}d_{ij}^{n}-\sum_{i^{\prime}=1}^{m}z_{i^{\prime}k}^{o}d_{i^{\prime}k}^{o}$
and
$\Delta_{L}(j)=\|\mathbf{z}_{j}^{n}\|_{1}L_{j}^{n}-\sum_{i^{\prime}=1}^{m}z_{i^{\prime}k}^{o}L_{k}^{o}$.
If $\Delta_{d}(i,j)<-\Delta_{L}(j)$ for all $z_{ij}^{n},z_{ij}^{o}$, and for
$\rho=0$, $j\in X_{t+1}$ is not a representative frame, then for some
$\rho\geq 0$, theorem 1 will not be satisfied by any pair $i,j\in X_{t+1}$.

Corollary 1.2 states that if a frame $j\in X_{t+1}$ is not a representative,
and satisfies the conditions on $\Delta_{d}(i,j)$ and $\Delta_{L}(j)$, then it
will stop being a representative for some value of $\rho\geq 0$. By
rearranging the terms in second condition of theorem 1, we get:
$\rho\Delta_{d}(i,j)-(1-\rho)\Delta_{L}(j)\leq\lambda\frac{\|\mathbf{z}^{n}_{j}\|_{p}}{\|\mathbf{z}^{n}_{j}\|_{p}}$.
For $p=1$ the RHS is constant, but LHS decreases with $\rho$. Hence the second
condition of theorem 1 is not satisfied by any $i\in X_{t+1}$ for the given
candidate representative frame $j\in X_{t+1}$. These results motivate us to
look for better formulations of multi-criteria OSS problem.

###  2.3 Submodular Multi-Criteria OSS

In this section, we describe an algorithm for multi-criteria OSS problem based
on submodular optimization. The problem can be posed as a set function
incorporating both pairwise and pointwise attributes and can be solved using
submodular optimisation. The natural criteria used for selection is the pre-
defined modified cumulative dissimilarity function $Q_{ij}$.

For every set $S$, the set function $f(S)$ can be defined as:

$f(S)=\sum_{i\in X}min\\{min_{j\in R}Q_{ij},min_{j\in S}Q_{ij}\\}$ (2)

Here, the problem is solved by selecting a representative $j$ which
contributes the least dissimilarity value $Q_{ij}$ to the incoming instances
$i\in X$. By definition, we can say

###### Remark 1

-f(S) is submodular.

For proof, see Supplementary. We can thus pose it as a submodular maximisation
problem by solving the problem $min_{S\subseteq X}f(S)$. We call this
formulation submodular multi-criteria OSS (SubMCOSS). We define a greedy
submodular maximisation approach for solving the optimisation problem in
Algorithm 1. The algorithm is a randomised greedy algorithm that examines the
dataset $k$ times to select the representatives for the incoming data. Next,
we show a thresholded convex approach for solving the multi-criteria OSS
problem.

Algorithm 1 : Submodular Multi-Criteria OSS

1:Input:

2: $S_{0}$: Initial representative set

3: $X$: Incoming Set of Instances

4: $k$: Subset cardinality

5: $f(S)$: Function to be minimised

6: $S_{0}=\phi$

7:Process:

8:for $i$ = 1,2, $\ldots$, $k$ do

9: for each x $\in$ X \$S_{i-1}$ do

10: $fv_{x}\leftarrow f(S_{i-1}\cup{x})$

11: end for

12: Let $M_{i}\in X$ \$S_{i-1}$ be subset of top $k$ elements maximising
$\sum_{m\in M_{i}}fv_{m}$

13: Let $u_{i}$ be randomly sampled from $M_{i}$

14: $S_{i}\leftarrow S_{i-1}\cup{u_{i}}$

15:end for

16:Output:

17:$S_{k}$ : Subset of size $k$

###  2.4 Thresholded Convex multi-criteria OSS

SubMCOSS , described in previous section uses the natural formulation of
weighted linear aggregation of pointwise and pairwise loss function. However,
the algorithm for submodular optimization is a randomized approximation
algorithm, and also computationally expensive due to multiple sampling runs
required for a good optimal subset (see our results). In this section, we
describe a novel convex formulation multi-criteria OSS which alleviates the
problems of Phys. Rev. Lett. (equation 2.1) as well as SubMCOSS (Algorithm 1).

The key observation which helps us in designing the novel algorithm is that in
Phys. Rev. Lett. (equation 2.1) it is possible for a frame $j\in X_{t+1}$ to
contribute $-m(1-\rho)L_{j}^{n}$ by becoming a representative for every point
$i\in X_{t+1}$ (see that the terms involving pointwise loss add up to
$-(1-\rho)(\sum_{i=1}^{m}z^{n}_{ij})L_{j}^{n}$). However, in reality it only
adds one data point to the training set with the pointwise score of
$-L_{j}^{n}$. This problem is alleviated by using a coefficient of $L_{j}^{n}$
which is an indicator of whether $j$ is a representative point or not, rather
than $(\sum_{i=1}^{m}z^{n}_{ij}$ which counts the number of points represented
by $j$. This is achieved by using a concave function $S_{j}$ of $z_{ij}$:
$S_{j}$ = $\frac{1}{\epsilon}\min(\epsilon,\sum_{i=1}^{m}z_{ij})$ where
$\epsilon$ is an input parameter. The modified objective function becomes:
$\mathcal{G}(z_{ij}^{o},z_{ij}^{n})=\rho(\sum_{i=1}^{m}\sum_{j=1}^{|R_{t}|}z_{ij}^{o}d^{o}_{ij}(t)+\sum_{i,j=1}^{m}z_{ij}^{n}d^{n}_{ij}(t))-(1-\rho)(\sum_{j=1}^{|R_{t}|}S_{j}^{o}*L_{j}^{o}+\sum_{j=1}^{m}S_{j}^{n}*L_{j}^{n})$,
where, $S^{o}_{j}$ =
$\frac{1}{\epsilon}\min(\epsilon,\sum_{i=1}^{m}z_{ij}^{o})$ , $S^{n}_{j}$ =
$\frac{1}{\epsilon}\min(\epsilon,\sum_{i=1}^{m}z_{ij}^{n})$. Note that
$\mathcal{G}$ is a convex function of $z_{ij}^{o},z_{ij}^{n}$ since $S$ is a
concave function. Also note that , each potential representative $j\in
X_{t+1}$ can contribute a maximum of its own pointwise score $L_{j}$, since
$S_{j}$ can take a maximum value of $1$.

Another drawback of Phys. Rev. Lett. (equation 2.1) is that compression ratio
has no direct relation with the parameter $\lambda$. We use a constraint based
cardinality criteria in order to have more precise control over the number of
representative selected. The user provided parameter frac specifies and upper
bound over the fraction of incoming frames to be selected as representatives.
Overcoming these drawbacks our final convex optimisation based multi-criteria
OSS problem formulation is:

$\displaystyle\min_{z^{o}_{ij},z^{n}_{ij}}$
$\displaystyle\mathcal{G}(z_{ij}^{o},z_{ij}^{n})$ (3) $\displaystyle s.t.$
$\displaystyle\sum_{j=1}^{|R_{t}|}z_{i,j}^{o}+\sum_{j=1}^{m}z_{i,j}^{n}=1$
$\displaystyle z_{i,j}^{n},z_{i,j}^{o}\in[0,1]$
$\displaystyle\sum_{j=1}^{m}\|[z_{1,j}^{n}\dots z_{m,j}^{n}]\|_{p}\leq frac*m$

This can be efficiently solved using any convex solver, e.g. CVXPY [9]. We
call this formulation thresholded multi-criteria OSS (ThreshMCOSS). $\epsilon$
is a user input which is designed to be the maximum value taken by the
variable $\sum_{i}z_{ij}$, when none of the $z_{ij}$ denote a representative
relation to be true. In an ideal situation (when we achieve a $\\{0,1\\}$
solution to $z_{ij}$), any positive value for $\epsilon$ is sufficient. In
practise, we set $\epsilon$ to a value less than $1$, e.g. $\epsilon=0.9$.
Next, we experimentally demonstrate the utility of our method.

##  3 Experiments

In this section, we provide our experimental setup by describing the dataset
and the subset selection methods. We then show a comparison of approximate
online subset selection methods over synthetic data and collected driving data
from the CARLA simulator [10]. Next, we compare the performance of various
subset selection methods in the autonomous driving application from two
aspects: episode completion and affordance prediction.

###  3.1 Experimental Setup

Dataset: We use the open-source driving simulator CARLA[10] for generating our
driving dataset. We collect the training data by driving the agent vehicle
using the CAL controller [19] with the ground truth affordances as input. The
collected data comprises of 262 driving episodes and with a total of 100,000
video frames. For each video frame, we collect: (1) front center camera image,
and (2) six affordances (Discrete: Red Light, Hazard Stop, Speed Sign ;
Continuous: Relative Angle, Centerline Distance, Vehicle Distance) [19]. We
used approximately $85\%$ of the video frames as the training data, and the
remaining as test set.

Figure 1 illustrates the distribution of four affordances per class label, in
training and test set. Red light and Hazard Stop have two classes - True,
False, Speed sign has four classes - None , 30kmph, 60kmph, 90kmph, while in
case of Relative angle which is the orientation angle of the agent vehicle, we
have grouped the values into buckets corresponding to Left turn, Straight and
Right turn. We can divide the entire range of Relative Angle affordance across
20 buckets ranging from -1.0 to +1.0. Note that buckets corresponding to (-1.0
to -0.1), (-0.1 to 0.1) and (0.1 to 1.0) approximately indicate the left turn,
straight road and right turn respectively.

Figure 1: Distribution of affordances in train and test set

Subset selection on Autonomous Driving: We use Conditional Affordance Learning
[19] (CAL) model as the driving model. We carry out training on NVIDIA Tesla
P100 for 50 epochs using Adam Optimizer with learning rate varying between
$10^{-3}$ to $10^{-4}$. We use SIFT dissimilarity as the pairwise metric
($d_{ij}$) for all selection methods and two variations of losses ($L_{j}$) as
pointwise metric - total loss (TL), bucket specific relative angle loss aided
with other multi-task losses (BML). We observe that among all 6 affordances,
relative angle which provides the steering angle of the car, is the most
essential affordance for episode completion.So,for pointwise metric, we
provide the highest weightage to the losses corresponding to buckets of
relative angle meant for turns and intersection, followed by the other
affordances. We report results with the following methods of selection for
compression ratios 100:20 and 100:7:

  1. 1.

Whole Set (WS): Unreduced dataset.

  2. 2.

Uniform Skip (US): Uniformly sampled data.

  3. 3.

Only SIFT (OS): Only $d_{ij}$.

  4. 4.

Only Loss (OL): Images with highest losses.

  5. 5.

Phys. Rev. Lett.[8] : $d_{ij}$ with TL.

  6. 6.

SubMCOSS-BML(SBML) : $d_{ij}$ with BML.

  7. 7.

ThreshMCOSS-TL(TCTL) : $d_{ij}$ with TL.

  8. 8.

ThreshMCOSS-BML(TCBML) : $d_{ij}$ with BML.

Subset selection and Training Times: Table 1 shows the amount of total time
taken for training and subset selection for each compression ratio.
Compression ratio of 100:20 takes about 1/3rd the total time taken to train
the whole set (WS). This follows for the other compression ratio too and hence
saves both time and space, essential in the current IoT setting with massively
huge data.

Table 1: Time complexity of subset selection methods | Compression
---
Ratio
WS |  | 100:20 | 100:7
| Training Time
---
(hours)
42 | 11 | 7
Subset Selection (hours) | 0 | MCOSS | 2 | 1
SBML | 5 | 2.5
| Proposed
---
Method
1.5 | 0.75

Metrics reported: We have reported metrics for the two subtasks: episode
completion and affordance accuracies. An episode corresponds to a source-
destination pair provided to the agent vehicle. The episode completion is
measured in terms of number of successfully completed episodes. The accuracies
of discrete affordances are measured in terms of Micro Accuracy (MIC) and
Macro Accuracy (MAC), while the continuous affordances are measured in terms
of Mean Absolute Error (MAE).

Affordance Selection: We have reported results for five affordances - Red
light, Hazard Stop, Relative Angle, Centerline Distance and Vehicle Distance.
Considering the setup of our dataset collection, from Figure 1, we can observe
that the two affordances Speed Sign and Hazard Stop suffer from class
imbalance. Alongside, prediction accuracy of Speed Sign does not have an
impact on episode completion. Hence, we refrain from reporting its accuracy.

###  3.2 Comparison of approximate online subset selection methods

Figure 2: Objective function values for proposed method , [8] method and
Submodular method for (left) Synthetic data and (right) CARLA driving data
samples

In this section, we compare the optimal subsets reported by the baseline
method [8], submodular method and the proposed convex optimization based
method in terms of final objective function values. Figure 2a shows the
objective function values for the three approaches, for 10 randomly
synthesized problem instances ($d$ matrix of dimension $100\times 100$ and $L$
vector of dimension $100$). For the submodular method, we report a box plot of
results over 100 runs of the algorithm to capture the randomness. While all
three methods find approximate solutions, the proposed convex method
consistently finds lower values of objective function, followed by [8], and
submodular optimization. For real data (CARLA data for our further
experiments), we report the same in Figure 2b , for 10 episodes in our
collected data. We can clearly observe that function values attained by our
proposed method lies below that of the other approximate methods, thus proving
our method to be an efficient approach.

Next, we discuss the application of the subset selection methods on autonomous
driving.

Table 2: Comparison of data gradation techniques in terms of episode completion in training and test conditions for 100:20 and 100:7 compression ratio Compression Ratio | Methods |  | Training
---
Conditions
| Test
---
Conditions
Straight | One-Turn |  | Straight
---
Dynamic
| One-Turn
---
Dynamic
Straight | One-Turn |  | Straight
---
Dynamic
| One-Turn
---
Dynamic
| WS | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10
100:20 | US | 9 | 3 | 8 | 3 | 9 | 5 | 9 | 5
OS | 10 | 7 | 10 | 7 | 10 | 7 | 9 | 6
OL | 10 | 6 | 10 | 6 | 10 | 7 | 9 | 7
MCOSS | 9 | 8 | 9 | 8 | 7 | 7 | 7 | 7
| SBML | 9 | 7 | 9 | 7 | 9 | 7 | 9 | 7
| TCTL | 10 | 8 | 10 | 7 | 10 | 9 | 10 | 9
| TCBML | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10
100:7 |  | MCOSS
---
9 | 5 | 9 | 5 | 7 | 4 | 7 | 4
SBML | 9 | 3 | 9 | 3 | 9 | 2 | 9 | 2
TCTL | 10 | 7 | 10 | 7 | 10 | 9 | 10 | 9
TCBML | 10 | 8 | 10 | 8 | 10 | 9 | 10 | 9

###  3.3 Comparison of Methods: Episode Completion

In this section, we will study the performance of different subset selection
techniques on the basis of episode completion which is the main intended
objective.

We consider four tasks under episode completion which had been originally
defined in [10]:

  1. 1.

Straight : The episode comprises of pairs of points which are straight roads.

  2. 2.

One-Turn : The episode comprises of pairs of points which include left or
right turn in their paths.

  3. 3.

Straight Dynamic : Similar to Straight task, it occurs in the presence of
other vehicles and pedestrians.

  4. 4.

One-Turn Dynamic : Similar to One-Turn task, it occurs in the presence of
other vehicles and pedestrians.

We show in Table 2 the performance of CAL model[19] trained on subsets,
obtained by various selection techniques, by simulating it with the CARLA [10]
simulator.

We report number of successfully completed episodes (out of a total of 10
episodes) for each subtask in training and test conditions. We observe that
the tasks - Straight and Straight Dynamic are fairly easy to accomplish for
all subset selection methods. The challenge arises in the other two tasks
where we see a large number of unsuccessful episodes.

The completion of episodes in turns, largely depends on the affordance
Relative Angle which as we mentioned, provides the steering angle of the agent
vehicle. We observe that Uniform Skip (US) is unable to complete majority of
the turns in training or test conditions. This is due to the inherent nature
of selection of US method, which does not take the important frame sequences
into consideration.

Figure 3: Anecdotal example of a sample episode showing (1)the region of
failure by MCL (2) the corresponding errors and (3) fraction of selected
instances from those regions. CBML selects more fraction of instances from
regions important for episode completion.

On the other hand, OS, OL, MCOSS, SBML complete some of the turn episodes,
with TCBML completing the highest of all methods (100% both in training and
test conditions) followed by TCTL. This is due to the efficient usage of
combination of pointwise metric along with pairwise metric in the selection of
instances. We also report the episode completion numbers for 100:7 compression
ratio in Table 2, for MCOSS and SBML and the thresholded convex methods. We
can observe that TCTL and TCBML continue to perform better compared to the
other baselines with TCBML completing 80% and 90% episodes in training and
test conditions even after dropping 93% of the frames.

We show an anecdotal example of a failed episode from MCOSS [8] method in
Figure 3 and try to analyse the reason behind it. In Figure 3, we firstly show
a plot of an episode with distance covered vs Relative Angle affordance. The
cumulative distance is chosen as an axis of reference in order to make the
comparison spatially similar for all the methods. Overall, the agent vehicle
in the simulator is resilient to errors. However, we can observe the gradual
deviation of MCOSS [8] method and its accumulated errors which lead to an
incomplete episode. We can also relate the region of failures to the
corresponding relative angle errors in Figure 3 (middle) where we observe that
overall, MCOSS [8] is having a higher error compared to proposed method TCBML
and model trained on WS. We also show the fraction of selected instances by
both the selection methods, in Figure 3 (right) from the same region, and we
can observe that TCBML selects more fraction of instances in the area right
before the turn and during the turn, which eventually help in its completion.
We discuss the next subtask - affordance prediction in the following
subsection.

Table 3: Comparison of data gradation techniques for 100:20 compression ratio on Hazard Stop, Red Light, Vehicle Distance and Centerline Distance Method | Hazard Stop | Red Light |  | Vehicle
---
Dist
| Center
---
Dist
MIC | MAC | MIC | MAC | MAE | MAE
WS |  99.44 |  99.72 |  97.39 |  97.41 | 0.03 | 0.05
US |  99.14 |  99.47 |  96.72 |  97.03 | 0.06 | 0.05
OS |  99.11 |  99.56 |  96.11 |  96.07 | 0.09 | 0.08
OL |  99.41 |  99.6 |  92.38 |  91.08 | 0.09 | 0.08
MCOSS |  99.43 |  98.39 |  91.63 |  89.73 | 0.05 | 0.06
SBML |  99.25 |  99.60 |  94.33 |  93.91 | 0.05 | 0.06
TCTL |  99.31 |  99.61 |  96.38 |  96.05 | 0.05 | 0.05
TCBML |  99.45 (0.01%) |  99.71 (0.01%) |  93.98 (3.41%) |  92.83) (4.58%) |  | 0.04
---
(33.3%)
| 0.05
---
(0%)

###  3.4 Comparison of Methods: Affordance Accuracies

Figure 4: Fraction of selected instances (FOSI) and Mean Absolute Error (MAE)
for Relative Angle for all selection methods. More fraction of instances in
turn buckets lead to lower MAE in CBML for 100:20 compression ratio.

In this section, we will study the performance of different subset selection
methods on the basis of their performance in affordance predictions.

We show in Table 3 the performance of CAL [19] driving model for four
affordances, on subsets obtained by different subset selection techniques for
100:20 compression ratio. We also show the % difference in performance of our
proposed method TCBML with that of WS. We notice that all the methods can
classify the affordances reasonably well for both red light and hazard stop
affordance. This is due to weighted cross-entropy losses used for the large
number of imbalanced classes as seen initially in Figure 1. We can also see
that TCTL and TCBML outperform all other methods in predicting vehicle
distance affordance. In case of centerline distance, all the methods work
similarly with OS and OL performing the worst.

In case of Relative Angle affordance, we have grouped the values into three
different buckets meant for Left Turn, Straight Road, Right Turn. We observe
in Figure 4 that the MAE for straight road buckets for all selection methods
are very low in range. This is essentially due to the skewness in Relative
Angle affordance. However, TCTL and TCBML outperform all other methods in turn
buckets which have in usual, lesser number of datapoints. We can also observe
that TCBML selects more fraction of instances for both Left and Right turns
while relaxes comparatively in the Straight Road. SBML also has close fraction
of instances to TCBML for left turn, however it drops down in the fraction of
right turns. The difference in MAE becomes more evident with increase in
compression ratio. We have added the result for 100:7 in the Supplementary.

This is indicative of the fact that the proposed thresholded convex method
gives more importance to the frames which are non-redundant and also having
higher losses, thus leading to better performance. Thus, we can clearly see
that our proposed methods TCTL and TCBML are performing better quantitatively
in terms of affordance predictions and qualitatively in terms of deployment of
the model.

##  4 Conclusion

In this paper, we propose a novel thresholded convex optimisation based online
video frame subset selection technique involving pairwise and pointwise
similarity for optimal learning for the task of self-driving. We also propose
a natural set-function based criteria to incorporate pointwise criteria using
submodular optimisation. We show the effectiveness of our improved subset
selection method (TCBML and TCTL) in the aspect of episode completion and
affordance predictions. We did extensive experiments to show that even after
dropping 80% of frames, we succeed in completing all the episodes involving
the difficult task of turns.

## References

  * [1] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al.  End to end learning for self-driving cars.  arXiv preprint arXiv:1604.07316, 2016.
  * [2] Mariusz Bojarski, Philip Yeres, Anna Choromanska, Krzysztof Choromanski, Bernhard Firner, Lawrence Jackel, and Urs Muller.  Explaining how a deep neural network trained with end-to-end learning steers a car.  arXiv preprint arXiv:1704.07911, 2017.
  * [3] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz.  Submodular maximization with cardinality constraints.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1433–1452. SIAM, 2014.
  * [4] Niv Buchbinder, Moran Feldman, Joseph Seffi, and Roy Schwartz.  A tight linear time (1/2)-approximation for unconstrained submodular maximization.  SIAM Journal on Computing, 44(5):1384–1402, 2015.
  * [5] Martin Buehler, Karl Iagnemma, and Sanjiv Singh.  The DARPA urban challenge: autonomous vehicles in city traffic, volume 56.  springer, 2009.
  * [6] Chongyu Chen, Jianfei Cai, Weisi Lin, and Guangming Shi.  Surveillance video coding via low-rank and sparse decomposition.  In Proceedings of the 20th ACM international conference on Multimedia, pages 713–716, 2012.
  * [7] Felipe Codevilla, Matthias Miiller, Antonio López, Vladlen Koltun, and Alexey Dosovitskiy.  End-to-end driving via conditional imitation learning.  In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 1–9. IEEE, 2018.
  * [8] Soumi Das, Sayan Mandal, Ashwin Bhoyar, Madhumita Bharde, Niloy Ganguly, Suparna Bhattacharya, and Sourangshu Bhattacharya.  Multi-criteria online frame-subset selection for autonomous vehicle videos.  Pattern Recognition Letters, 2020.
  * [9] Steven Diamond and Stephen Boyd.  CVXPY: A Python-embedded modeling language for convex optimization.  Journal of Machine Learning Research, 17(83):1–5, 2016.
  * [10] Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun.  Carla: An open urban driving simulator.  arXiv preprint arXiv:1711.03938, 2017.
  * [11] Ehsan Elhamifar and M Clara De Paolis Kaluza.  Online summarization via submodular and convex optimization.  In CVPR, pages 1818–1826, 2017.
  * [12] Sheng-Jun Huang, Jia-Wei Zhao, and Zhao-Yang Liu.  Cost-effective training of deep cnns with active model adaptation.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1580–1588. ACM, 2018.
  * [13] Mohsen Joneidi, Saeed Vahidian, Ashkan Esmaeili, Weijia Wang, Nazanin Rahnavard, Bill Lin, and Mubarak Shah.  Select to better learn: Fast and accurate deep learning using data selection from nonlinear manifolds.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7819–7829, 2020.
  * [14] Shuyue Lan, Rameswar Panda, Qi Zhu, and Amit K Roy-Chowdhury.  Ffnet: Video fast-forwarding via reinforcement learning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6771–6780, 2018.
  * [15] Xiaodan Liang, Tairui Wang, Luona Yang, and Eric Xing.  Cirl: Controllable imitative reinforcement learning for vision-based self-driving.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 584–599, 2018.
  * [16] Behrooz Mahasseni, Michael Lam, and Sinisa Todorovic.  Unsupervised video summarization with adversarial lstm networks.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 202–211, 2017.
  * [17] Dean A Pomerleau.  Alvinn: An autonomous land vehicle in a neural network.  In Advances in neural information processing systems, pages 305–313, 1989.
  * [18] Aditya Prakash, Aseem Behl, Eshed Ohn-Bar, Kashyap Chitta, and Andreas Geiger.  Exploring data aggregation in policy learning for vision-based urban autonomous driving.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11763–11773, 2020.
  * [19] Axel Sauer, Nikolay Savinov, and Andreas Geiger.  Conditional affordance learning for driving in urban environments.  arXiv preprint arXiv:1806.06498, 2018.
  * [20] Sebastian Thrun, Mike Montemerlo, Hendrik Dahlkamp, David Stavens, Andrei Aron, James Diebel, Philip Fong, John Gale, Morgan Halpenny, Gabriel Hoffmann, et al.  Stanley: The robot that won the darpa grand challenge.  Journal of field Robotics, 23(9):661–692, 2006.
  * [21] Chris Urmson, Joshua Anhalt, Drew Bagnell, Christopher Baker, Robert Bittner, MN Clark, John Dolan, Dave Duggins, Tugrul Galatali, Chris Geyer, et al.  Autonomous driving in urban environments: Boss and the urban challenge.  Journal of Field Robotics, 25(8):425–466, 2008.
  * [22] Wenhao Wu, Dongliang He, Xiao Tan, Shifeng Chen, and Shilei Wen.  Multi-agent reinforcement learning based frame sampling for effective untrimmed video recognition.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
  * [23] Zuxuan Wu, Caiming Xiong, Chih-Yao Ma, Richard Socher, and Larry S. Davis.  Adaframe: Adaptive frame selection for fast video recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [24] Huazhe Xu, Yang Gao, Fisher Yu, and Trevor Darrell.  End-to-end learning of driving models from large-scale video datasets.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2174–2182, 2017.
  * [25] Julius Ziegler, Philipp Bender, Markus Schreiber, Henning Lategahn, Tobias Strauss, Christoph Stiller, Thao Dang, Uwe Franke, Nils Appenrodt, Christoph G Keller, et al.  Making bertha drive—an autonomous journey on a historic route.  IEEE Intelligent transportation systems magazine, 6(2):8–20, 2014\.


The Orchestrator also keeps track of aggregate statistics from Controller
nodes including total step counts and average scores, which are used to
calculate a training CT metric. It coordinates simulation parameter updates
through the ADR mechanism (see section 4.5). These simulation parameter
updates are pushed to the Controller nodes which store them in a buffer,
waiting to apply to them to the simulation when the next episode boundary is
reached.

The topology of the full distributed system, consisting of Orchestrator,
Controller, InferrerLearner nodes and Reverb replay buffers is configured and
mapped to hardware using Launchpad (Yang et al. (2021)).

###  C.2 Training hyperparameters

Figure C.2: Encoder architecture.

The agent receives observations from the environment, computed by LIDAR and
AVATAR sensors described in Section 2.3. The LIDAR sensor is used as an input
to the agent’s neural network, but the AVATAR sensor is not. We additionally
feed the previous step’s reward into the agent’s neural network. The $14\times
14\times 9$ LIDAR sensor is passed through a convolutional layer with 24
square $2\times 2$ kernels. The previous reward is concatenated to the output
of this convolutional layer before being passed to a linear layer of size 128.
Layer norm is applied before a tanh activation followed by 2 linear layers of
size 256 with elu activation in between. The encoder is illustrated in figure
C.2, resulting in an encoded observation.

Table C.1 presents the hyperparameters used during training of our agents .
The values were either the defaults found in the DeepMind JAX Ecosystem
(Babuschkin et al., 2020) or were set using small-scale sweeps early in
experimentation.

Hyperparameter |  Description |  Value
---|---|---
MPO Hyperparameters (See Abdolmaleki et al. (2018b) for details)
Policy Samples |  Number of actions to sample from the policy |  100
Min stdev |  A minimum (epsilon) standard deviation to add to the predicted value to prevent it from being 0. |  1e-4
Action embedding |  Transformation function applied to action samples |  tanh
Alpha Init |  Initial value of Lagrange multiplier for KL mean and covariance |  1
Epsilon Alpha KL mean |  Epsilon for Lagrange multiplier for KL mean |  2.4e-2
Epsilon Alpha KL cov |  Epsilon for Lagrange multiplier for KL covariance |  7e-5
Temperature Init |  Initial value of temperature Lagrange multiplier |  0.325
Epsilon Temperature |  Epsilon for temperature Lagrange multiplier |  2e-2
Gamma |  Discount factor applied to returns |  0.99387
Training hyperparameters
Critic learning rate |  Learning rate of ADAM optimiser (Kingma and Ba, 2015) applied only to the critic neural network |  4.8e-4
Actor learning rate |  Learning rate of ADAM optimiser applied to policy, encoder, RNN and attention loss networks |  2e-4
Network update period |  Number of steps after which the online network is replaced with the target network |  100
Attention loss weight |  Relative weight of the attention loss relative to the MPO loss |  10
Attention loss step |  The (future) prediction step used by the attention loss |  0
Batch size |  The batch size for learner steps |  32
Trajectory length |  The number of steps over which the RNN is unrolled in each learner step |  800
Episode length |  The number of steps making up an episode. The agent’s state is reset and it respawns at a random location at the beginning of an episode. |  1800
Table C.1: Hyperparameters.

###  C.3 Attention Loss (AL)

Following up from section 4.4, we provide a discussion and some extra
empirical findings that support the design choices in our attention loss.
These include: (1) the time step at which to make the prediction; (2) the
weight of the attention loss and (3) adding noise to the prediction targets.

The prediction time step

is, by default, the current step for all our agents. However, predicting a
past or a future step is also a sensible alternative. More formally, we can
predict scaled coordinates $(\hat{x}_{t+n},\hat{y}_{t+n},\hat{z}_{t+n})$ for
arbitrary choices of $n$, as in Equation 8 below. Positive values of $n$
correspond to a future step, potentially helping the agent build a model of
the world and the other players. Negative values of $n$ target a past step,
potentially enhancing the agent’s memory. Having tried several values for $n$,
we conclude that predicting the present (i.e., setting $n$ to 0) results in
the best performance, as shown in Figure 3(a). This choice gives our attention
loss the flavour of a reconstruction loss and resembles working memory. Note
that we don’t consider $n$ of 1 (as used in Ndousse et al. (2020)) or -1
because the difference between single timesteps in our complex 3D simulation
is small compared to a 2D grid-world.

$(\hat{x}_{t+n},\hat{y}_{t+n},\hat{z}_{t+n})=MLP([LSTM(s_{t});a_{t}])\in[0,1]\,.$
(8)

The attention loss weight

is the hyper-parameter deciding the importance of the attention loss relative
to our agents’ primary policy optimisation loss. Figure 3(b) shows that an
agent becomes more socially adept and learns to pay more attention to the
expert with a higher weight on the attention loss. Therefore, in all our
experiments, we use a weight of $10.0$.

Noisy targets

are a common technique for increasing the robustness to noise and regularise
the label predictions during training (Szegedy et al., 2016). However, in our
case, noisy predictions did not make a significant difference (see Figure
3(c)).

(a) Prediction step

(b) Loss weight

(c) Target noise

Figure C.3: Extra empirical findings on the attention loss, ablating past,
present, and future steps as alternatives for the prediction time (3(a)), the
weight of the attention loss (3(b)), and the amount of normal noise added on
top of the prediction targets (3(c)).

###  C.4 Automatic Domain Randomisation (ADR)

To train on a diverse set of tasks, the Orchestrator (see Appendix C.1)
periodically re-samples all of the task parameters according to $\lambda\sim
P_{\phi}$ and configures the environment simulations using the sampled
parameters synchronously. Hence, between these resampling instances, the agent
is trained on tasks distributed according to $P_{\phi}$. Note that the
resampling interval is set to be $10$ minutes, much longer than the time it
takes to complete the number of steps in an episode. In practice, $30$ to $50$
episodes are run using a task with the same parameters.

To adapt the task distribution to the agent’s Goldilocks zone, the
distribution parameters $\phi$ are updated before sampling task parameters in
the Orchestrator. To facilitate this update, we follow two techniques from the
original ADR: boundary sampling and threshold updates.

When sampling a parameter $\lambda$, with probability $p_{b}\in[0,1]$
(referred to as the boundary sampling probability) a task parameter
$\lambda_{b}$ is chosen uniformly at random to be fixed to one of its
‘boundaries’: $\\{\phi_{b}^{L}\,,\phi_{b}^{H}\\}$. In general, both boundaries
are updated by ADR and the boundary value is randomly sampled from the two
options. We also allow cases where only one of the boundaries is updated by
ADR, while other is fixed (for example, if a parameter is non-negative). In
these cases, the variable boundary is used as the sampled value. Once
$\lambda_{b}$ is determined, the remaining components of $\lambda$ are sampled
according to $P_{\phi}$. Finally, with probability $1-p_{b}$, $\lambda$ is
sampled directly from $P_{\phi}$.

Each task parameter that was boundary sampled contains one component at index
$b$ that matches either $\phi_{b}^{L}$ or $\phi_{b}^{H}$. Let
$b(\lambda)\in\\{1,\dots,d\\}\times\\{L,H\\}$ denote the mapping from a task
parameter to the boundary to which $\lambda_{b}$ was fixed, specified by a
tuple: $(b,L)$ or $(b,H)$. At the end of an Orchestrator update interval, each
simulation sends its training cultural transmission metric (see Section 4.1)
to the queue $q(b(\lambda))$. Note that up to $2d$ separate queues are
required. Simulations where $\lambda$ was not boundary sampled do not push
their cultural transmission metrics.

A training cultural transmission metric for a given set of task parameters is
obtained by collecting agent scores in 3 special episodes with: no dropout,
full dropout, and half dropout of the expert bot. These episodes are run every
time the Orchestrator resamples task parameters.

To update $\phi_{i}^{L}$ (and similarly $\phi_{i}^{H}$), we simply average
$q(i,L)$ and compare the average training cultural transmission metric
$\bar{c}(i,L)$ against fixed thresholds: $\text{th}_{L}$, $\text{th}_{H}$.
$\phi_{i}^{L}$ is updated according to

$\phi_{i}^{L}=\begin{cases}\phi_{i}^{L}-\Delta_{i}&\bar{c}(i,L)>\text{th}_{H}\\\
\phi_{i}^{L}+\Delta_{i}&\bar{c}(i,L)<\text{th}_{L}\\\
\phi_{i}^{L}&\text{otherwise or q(i, L) empty}\end{cases}\,,$ (9)

and $\phi_{i}^{H}$ according to

$\phi_{i}^{H}=\begin{cases}\phi_{i}^{H}+\Delta_{i}&\bar{c}(i,H)>\text{th}_{H}\\\
\phi_{i}^{H}-\Delta_{i}&\bar{c}(i,H)<\text{th}_{L}\\\
\phi_{i}^{H}&\text{otherwise or q(i, H) empty}\end{cases}\,,$ (10)

for $\Delta_{i}$ a fixed, positive step size.

##  Appendix D Training and evaluation in detail

###  D.1 Training without ADR

Of the 4 phases of behaviours shown in Figure 8, phases 2 and 3 demonstrate
social learning abilities. Moreover, the follow and remember strategy learned
in phase 3 is more rewarding than the pure following strategy learned in phase
2. We hypothesise that phases 1 and 2 are necessary for the training of agents
that follow and remember. To avoid phase 4, we must control the training task
complexity appropriately so that social learning is always better than
independence. In other words, we are required to maintain an information
asymmetry between the expert and our agent, so that social learning remains
rewarding. We refer to the just-right task complexity as a “Goldilocks zone”
from which cultural transmission strategies can emerge. We verify this
hypothesis in the experiments in sections 5.2 and 5.3. One might question why
we deliberately avoid the interesting behaviour of phase 4 henceforth. The
reason is quite simply expediency: in this work, we are particularly focused
on generating the strong and useful prior provided by robust and generalisable
cultural transmission. Phase 4 clearly points to a rich seam of future work by
fine-tuning this prior.

###  D.2 Training with single-parameter ADR

As the world size randomisation range expands, the evaluation cultural
transmission metric increases correspondingly. This is expected since the
held-out evaluation scenarios only contain worlds of size $32\times 32$. Thus,
ADR creates a curriculum that allows cultural transmission to emerge in simple
$16\times 16$ worlds, then gradually expand to larger worlds including
$32\times 32$. Note that even after exceeding the evaluation world size, the
evaluation cultural transmission metric remains lower than training cultural
transmission metric. This is likely due to other modifications in the
evaluation scenarios from the training setup. For example, the expert bot is
replaced by recorded human demonstrations. We highlight the advantage of using
the training cultural transmission metric to adapt boundaries in ADR rather
than the agent score used in OpenAI et al. (2019). As a threshold-based
method, ADR is sensitive to the scale and normalisation of the parameter used
to adapt boundaries. As Figure 9 shows, the CT metric is insensitive to
changes in the maximum achievable score as the set of training tasks changes.

###  D.3 Training with multi-parameter ADR

The process of emergent social learning with increasing task difficulty is
gradual and the experiment run spanned more than 300 hours (1.5 weeks). To
provide a sense of the experience consumed, the average rate of inference
steps for the agent was approximately $4\times 10^{6}$ per hour, and inference
data was reused on average $55$ times for learning. We note that all
parameters controlled by ADR expanded significantly over the experiment run.

Parameter | Min | Initial | Max | Step
---|---|---|---|---
World size | 20 | 20 | 32 | 1
Horizontal obstacle density | 0.0001 | 0.0001 | 0.01 | 0.0001
Vertical obstacle density | 0.0 | 0.0 | 0.2 | 0.0005
Bumpy terrain max value | 10.0 | 10.0 | 15.0 | 0.1
Bumpy terrain frequency | 0.01 | 0.01 | 0.1 | 0.002
Bot speed | 7.0 | 11.0 | 14.0 | 0.1
Probabilistic dropout transition probability | 2/1800 | 20/1800 | 40/1800 | 2/1800
Table D.1: Task parameters controlled by ADR. Figure D.1: Training CT metrics.
ADR adapts each randomisation range boundary by expanding when the metric is
above an update threshold high of $0.85$ and contracting when the metric is
below an update threshold low of $0.75$.

Figure D.2 shows the agent and expert bot scores over the training run. As
before, when ADR expanded the parameter boundaries, the maximum achievable
score (approximately the bot score) decreased. The agent score also showed a
corresponding decrease. The successful expansion of ADR reinforces our correct
choice of using the cultural transmission metric to adapt ADR, in order to
avoid scale and normalisation issues with score. Finally, we observe the
“spikes” in both bot and agent scores over the training run, likely due to
expansions and contractions of world parameter randomisation ranges by ADR.

Figure D.2: Agent and bot scores over ADR training. Smoothed using a simple
moving average of length $5$.

###  D.4 Evaluation via ablations

In our ablations, we take a top-down approach: starting from an agent of
reference, we remove, in turn, only one single component at a time and train
the ablated agent in the same manner as the reference. Across our ablations,
we use two reference agents:

  1. 1.

MEDAL-ADR is our highest performing agent, using full ADR, as described in
Section 5.3. We use this agent as a reference only for ablating ADR.

  2. 2.

MEDAL is our best performing non-ADR agent, trained on a fixed $20\times 20$
world size with no vertical obstacles and few horizontal obstacles. The usual
randomised procedural generation of the environment is, however, preserved. We
use MEDAL as our reference agent when ablating all other components, except
ADR. The choice of MEDAL over MEDAL-ADR provides a higher chance for the
ablated variants to show their full potential in a simpler environment. Note
that using MEDAL as a reference only permits sound evaluations in simple probe
tasks because it never learns to navigate complex worlds without ADR.

Expert, Memory, and Attention are crucial ingredients. Figure 12 shows that
the agent cannot solve the task without these (achieves $0$ score) and
therefore also doesn’t pick up any social cues from the expert (if present),
accounting for a mean $0$ CT metric.

The presence of another agent (in our case, an expert) is necessary given the
exploration difficulty of our task. By removing expert demonstrations – and,
consequently, all dependent components, the dropout (D) and attention loss
(AL) – the agent must learn to determine the correct goal ordering (also
called solo training). Under the default exploration strategy built into MPO,
the solitary agent is too risk-averse to solve the task. We noticed in video
recordings that these solitary agents learn to avoid goal spheres altogether.

Without memory, our agent does not form connections to the previously seen
cues, be they social, behavioural, or environmental. When replacing the LSTM
with an equally sized MLP (keeping the same activation functions and biases,
but removing any recurrent connections), our agent’s ability to register and
remember a solution is drastically reduced.

Lastly, having an expert at hand is futile if the agent cannot recognise and
pay attention to it. When we turn off the attention loss, the resulting agent,
MED––, treats other agents as noisy background information, performing the
task as if it were alone. Our agent needs to use social cues to bootstrap its
knowledge about the task and the attention loss is an essential component that
encourages it to do so.

Dropout is necessary to equip the agent with the ability to internalise new
behaviours, rather than simply copy them live. Together with the attention
loss, it strikes a balance between dependence on others and independent
behaviour. Without expert dropout, the ablated agent, ME–AL, achieves more
cumulative score early on in training because it can rely on the expert at all
times. That comes, however, at the expense of lower cultural transmission.
This is because the agent becomes dependent on the presence of the expert and
cannot solve the task without it. However, our full MEDAL agent learns to be
robust to different observations, recognises when it can bootstrap another
agent’s knowledge and when it needs to act on its own, which is a clear
advantage.

ADR ensures adaptability to different levels of task difficulty, environmental
complexity, and expert behaviour. In this ablation, we alter the training
setup in two ways: (1) We set up the task to match the end-points of ADR, but
remove any automatic adaptation. The agent needs to cope with the highest
level of task complexity from the very beginning. We refer to this as the
MEDAL-––– agent; (2) We sample uniformly the same values as in MEDAL-ADR;
therefore, the agent sees an amalgam of settings that do not follow a
curriculum (referred to as the MEDAL-–DR agent). MEDAL-ADR achieves the
highest cultural transmission in all probes, as shown in Figure 14. MEDAL-–DR,
lacks robustness, achieving only half the CT of MEDAL-ADR. MEDAL-––– on the
other hand, struggles to train at all: the endpoint for the ADR curriculum is
too challenging as a starting point for RL. These results emphasise the
importance of maintaining the task in the Goldilocks zone for cultural
transmission (with robust following and remembering) to be successful.

##  Appendix E Analysis in detail

Because the ADR parameter ranges can fluctuate over the duration of an ADR
experiment, we use the following criteria to select the agent for analysis.
First, we normalise the ADR parameter ranges at every training time step by
the maximum range allowed according to Table D.1. The ranges are further
averaged to obtain the mean ADR range. We also average the training cultural
transmission metric of all ADR parameter boundaries at every training time
step. Finally, we select a training time step that satisfies the following
criteria:

  * •

Mean normalised ADR range $\geq$ 0.55

  * •

Mean training cultural transmission metric $\geq$ 0.80

  * •

Min normalised ADR range $\geq$ 0.10

###  E.1 Generalisation

Parameter | In-distribution range | Out-of-distribution ranges
---|---|---
World size | [20, 26] | [18, 19], [26, 31]
Horizontal obstacle density | [0.0001, 0.0024] | 0.0, [0.0025, 0.003]
Vertical obstacle density | [0.0, 0.0255] | [0.026, 0.031]
Bumpy terrain max value | [0.0, 3.4] | [3.5, 4.1]
Bumpy terrain frequency | [0.01, 0.1] | [0.0, 0.008], [0.102, 0.12]
Bot speed | [9.0, 13.7] | [7.2, 8.6], [13.8, 16.4]
Probabilistic dropout transition probability | [2/1800, 40/1800] | 0.0, [42/1800, 48/1800]
Table E.1: In-distribution and out-of-distribution parameter values for the
evaluated MEDAL-ADR agent.

We define obstacle complexity as the tuple (horizontal obstacle density,
vertical obstacle density). Each component is normalised by its minimum and
maximum values listed in Table E.1 to yield a value between 0 and 1. For
example, an obstacle complexity of 0 corresponds to an empty world, while a
value of 1 corresponds to a world with a density of 0.003 and 0.031 of the
horizontal and vertical obstacles respectively. Similarly, we define terrain
complexity as the tuple (world size, bumpy terrain amplitude, bumpy terrain
frequency), all normalised.

Results from the evaluation over this space, alongside example worlds from its
extremal values, are shown in Figure 16. In addition, results for each
parameter are given in Figure 17 to disentangle MEDAL-ADR’s generalisation
capabilities across the different components. In the per-parameter plots, all
other parameters are held fixed at the mean of their in-distribution value.

###  E.2 Fidelity

We plot trajectories of the MEDAL-ADR agent and expert bots to further
investigate the correlation between their behaviours within a single episode
(Figure 20). In particular, we first plot the trajectory of the agent and bot
as the bot performs the task optimally, and then plot the trajectory after the
bot either (1) drops out of the environment or (2) begins acting sub-optimally
halfway through the episode. We additionally plot the agent’s trajectory when
the bot provides an incorrect demonstration and then drops out. Finally, we
measure the agent’s performance without ever placing the bot in the
environment to qualitatively investigate whether the agent is capable of
solving the task on its own. Together, these scenarios provide a visual
indication of the fidelity with which an agent can imitate an expert’s
demonstration, and the fidelity with which an agent can reproduce that
demonstration in the absence of the expert.

###  E.3 Neural activations

The linear probing method for identifying a social neuron is as follows.

  1. 1.

Data collection  We load a trained agent and run its policy (without further
training) for 200 episodes, randomising the goal and the timestep at which
dropout occurs. We collect pairs of features, namely the agent’s belief state
and a corresponding binary label indicating whether or not the expert is
present for every timestep in each episode.

  2. 2.

Training  We randomise and split the previously collected dataset into a train
(70%) and test set (30%). We train a new classification model that predicts
whether the expert was present or not at each timestep based on the agent’s
associated belief state (already trained and frozen). The model is
parameterised by an attention map of the same size as the belief (i.e.,
$512$), learning the relative importance of each of its neurons. The
attention-weighted belief then passes through a linear layer and is projected
onto a 2D space, corresponding to the task’s classes. Under this training
strategy, we identify social neurons as the maximally attended neurons, those
for which the attention weight is higher than a threshold, which we set to
$0.05$. Figure E.2 proves that we picked this threshold sensibly: the social
neurons selected under this criterion account for more than $90\%$ of the
probability mass.

  3. 3.

Evaluation  We first check the accuracy of the newly trained classification
model on the test set. To causally probe our earlier assumptions, we also make
two interventions on the test set: one replaces the identified social neurons
with random activations; the other replaces all neurons except the identified
social neurons with random activations. Note that we have drawn these random
values from a normal distribution resembling that neuron’s original activation
distribution in the training set. We also report the accuracy on the test set
when setting all neurons to random activations drawn from their distributions
(random baseline).

  4. 4.

Analysis  Finally, we look at the trained attention map and activations of the
identified social neurons across episodes.

(a) MEDAL’s learned attention map

(b) One of MEDAL’s social neuron activations

(c) MEDAL-ADR’s learned attention map

(d) MEDAL-ADR’s social neuron activations

Figure E.1: Having identified social neurons as those maximally weighted in
the attention map (1(a), 1(c)), we observe a sharp sign or magnitude change in
the activations of the social neurons when the expert drops out. As an
example, we plot these across one randomly selected episode for MEDAL (1(b))
and MEDAL-ADR (1(d)).

(a) MEDAL

(b) MEDAL-ADR

Figure E.2: Ordering the neurons based on their corresponding (log) attention
weight, we notice a considerable gap between the social neurons and the rest
of the neurons. The identified social neurons account for more than 90% of the
total probability mass. This result is consistent across both MEDAL (2(a)) and
MEDAL-ADR (2(b)), and motivate the choice of our deliberately loose threshold
(0.05). The other agent used for comparison, MED––, does not have any social
neurons because none of the neurons surpasses the threshold.

We perform the steps above for three of our ablated agents: MED––, MEDAL, and
MEDAL-ADR. Comparing their accuracies on the causal and control probes (see
Figure 21), it is apparent that, on the one hand, the classifier trained on
MED––’s representations achieves low accuracy, with no neurons surpassing the
attention weight threshold; on the other hand, the classifiers trained on
MEDAL and MEDAL-ADR’s representations have high accuracies, and their
identified social neurons play a role in maintaining and reliably predicting
the expert’s presence on their own.

We make some empirical remarks about the nature and behaviour of the goal
neuron found in our MEDAL-ADR agent. It suddenly fires when it enters a goal
area and remains high as long as the agent remains inside. Interestingly, the
neuron signals its anticipation of exiting the potentially rewarding zones
with a slight decrease in the magnitude of its activation, followed by a sharp
drop and levelling around zero. To see these, compare the activations of the
goal neuron when the agent completes the task, aided by a bot (Figure 22(a)),
and when the agent fails to do so because it is alone (Figure 22(b)).

Note that it is not the presence or the following of an expert that determines
the spikes. Figure 22(c), probing the activations of the goal neuron in a
dropout scenario, demonstrates this. After performing the task with the bot,
the agent, when left alone, also tries to solve it independently. Despite the
absence of an expert, its goal neuron spikes every time it enters an expected
rewarding zone. Note that it is not the observation of a positive reward that
causes the neuron’s spiking. Figures 22(b) and 22(d) (around steps 200 and
950, respectively) show that the agent can enter the same goal twice and spike
each time, although it receives a reward only the first time.

Not fulfilling the agent’s expectation of a rewarding goal reduces the
magnitude of the goal neuron’s spike. That is manifested either by
accumulating a negative point (Figure 22(c)) or by entering the same goal
twice (Figure 22(b)) in the absence of an expert. However, the expert’s
presence cancels out the effect of negative rewards on spikes, as shown in
Figure 22(d) featuring a noisy scenario. We hypothesise that the identified
goal neuron spikes in anticipation of reward and thus correlates with
decisiveness and intention. It carries some resemblance to the analysis of
persistent decision variables introduced by Bari et al. (2019), where changes
in firing rates occur around the moment of choices and outcomes.

Figure E.3: We provide a snapshot of the activations of 45 neurons in MEDAL-
ADR’s belief state, where we identify neuron $123$ as a “goal neuron”. At
first glance, and using the neighbouring neurons for contrast, the goal neuron
is characterised by a distinctive periodic variation in its firing pattern
across the episode.