# SECRM-2D: RL-Based Efficient and Comfortable Route-Following Autonomous
Driving with Analytic Safety Guarantees

Tianyu Shi, Ilia Smirnov, Omar ElSamadisy, Baher Abdulhai The authors are with
the Dept. of Civil and Mineral Engineering. University of Toronto, Canada.
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>ElSamadisy is
on leave with Dept. of Electronics & Communications Engineering, Arab Academy
for Science and Technology, Egypt<EMAIL_ADDRESS>
###### Abstract

Over the last decade, there has been increasing interest in autonomous driving
systems. Reinforcement Learning (RL) shows great promise for training
autonomous driving controllers, being able to directly optimize a combination
of criteria such as efficiency comfort, and stability. However, RL-based
controllers typically offer no safety guarantees, making their readiness for
real deployment questionable. In this paper, we propose SECRM-2D (the Safe,
Efficient and Comfortable RL-based driving Model with Lane-Changing), an RL
autonomous driving controller (both longitudinal and lateral) that balances
optimization of efficiency and comfort and follows a fixed route, while being
subject to hard analytic safety constraints. The aforementioned safety
constraints are derived from the criterion that the follower vehicle must have
sufficient headway to be able to avoid a crash if the leader vehicle brakes
suddenly. We evaluate SECRM-2D against several learning and non-learning
baselines in simulated test scenarios, including freeway driving, exiting,
merging, and emergency braking. Our results confirm that representative
previously-published RL AV controllers may crash in both training and testing,
even if they are optimizing a safety objective. By contrast, our controller
SECRM-2D is successful in avoiding crashes during both training and testing,
improves over the baselines in measures of efficiency and comfort, and is more
faithful in following the prescribed route. In addition, we achieve a good
theoretical understanding of the longitudinal steady-state of a collection of
SECRM-2D vehicles.

###### Index Terms:

Autonomous Driving, Safe Reinforcement Learning, Safety Analysis

##  I Introduction

Achieving autonomous driving is an important goal in the development of
intelligent transportation systems. Reinforcement Learning (RL) is a general
optimization technique that directly optimizes a particular objective, without
requiring any special problem structure (such as linearity or convexity). RL
is becoming mature, and RL-based systems have been able to surpass human
performance in several domains, such as game-playing [1] and data-center
cooling [2] in recent years. Because autonomous driving involves optimization
of a diverse combination of objectives, including efficiency, comfort, route-
following, and safety, RL is an attractive approach to training autonomous
vehicle (AV) controllers (more explicit definitions of the optimization
objectives chosen for this work will be given in Sections II and III).

In addition, model-free RL algorithms can learn from data without requiring an
explicit model of the environment. Formulating a model often requires
introducing crucial simplifications and heuristics. By contrast, model-free
RL-based control algorithms have the potential to respond to hard-to-model
problem dynamics.

However, RL controllers and especially Deep RL controllers (that involve
neural networks as function approximators in order to approach large-scale and
complex problems) can be difficult to interpret. The black-box nature of the
controllers makes certifiable behaviour difficult to achieve with the standard
methods. One of the main current issues in applying RL to car following and
lane change control is the need to ensure safety [3]. Developing robust safety
mechanisms is crucial to prevent hazardous situations.

In previous work SECRM [4], we developed a longitudinal car-following RL
controller with safety guarantees. In this paper, SECRM is extended with
lateral (lane-changing) control actions. Lane-change maneuvers may be
categorized as being either discretionary or mandatory. A lane change maneuver
is defined as discretionary when it is not explicitly required or mandated by
external factors such as road closures or merging lanes. In discretionary lane
changes, the decision to change lanes is primarily based on goals such as
optimizing travel time, improving comfort, or adapting to traffic conditions
[5]. By contrast, lane changes that are required by external factors are
defined as mandatory [6]. We are the first to propose an RL controller that
can perform both discretionary and mandatory lane changes. The main
contributions are:

  * •

We propose SECRM-2D, an RL-based controller for autonomous driving, which
optimizes efficiency and comfort, and follows a prescribed route, while
incorporating hard analytic safety constraints.

  * •

Longitudinal safety constraints from [4] are extended to formulate lane-change
safety constraints.

  * •

Discretionary and mandatory lane changes are combined into a single unified
optimization objective. To the best of our knowledge, this is the first RL AV
controller to handle both discretionary and mandatory lane changing on equal
footing.

  * •

In addition, the steady-state behavior of a group of SECRM-2D vehicles is
studied. We demonstrate that these vehicles naturally form a steady-speed
platoon as a consequence of efficiency optimization. An explicit formula is
derived for the gap between vehicles, as a function of platoon speed and
parameters like maximal braking rate and reaction time. The findings are
validated in simulation.

This work advances the promise of RL to train performant AV controllers, while
incorporating strong, explainable and explicit safety constraints.

Many researchers investigated lane change topics. For example, Pan et al.
introduced a mesoscopic multilane freeway model integrating both MLC and DLC
maneuvers which was further calibrated using real-world data [7]. Furthermore,
Shi et al. proposed a hierarchical structure based on reinforcement learning
to make the autonomous vehicle learn to decide when to lane change and how to
lane change [8]. Hoel et al. combined planning and learning with Monte Carlo
Tree Search for the highway exit case [9]. However, they haven’t given enough
consideration to the safety issue.

Furthermore, Cao et al. investigated a learning-enhanced highway-exit planner
to adapt to urgent exiting cases. They proposed safety and traffic rule
constraints to construct the safe margin of speed [10]. Ye et al. integrates
penalty for collision and near-collision into reward function to enhance
safety [11]. Udatha et al. embed probabilistic control barrier functions into
reinforcement learning to improve safety in ramp merging [12]. However, they
cannot adapt their safety formulation to both mandatory and discretionary lane
change, and they haven’t provided much theoretical understanding of the safety
criteria.

##  II Problem formulation

In this section, the problem to be solved is formulated. After an informal
discussion, the notation is set and the requirements are formalized.

Our goal is to train a controller for a single vehicle that is driving along a
road consisting of one or multiple lanes. The controller acts in discrete
regular time-steps (typically every 0.1s). The duration of a single time-step
is the controller’s reaction time $r$. We measure time in units of $r$. Every
time-step, the controller sets both the vehicle’s continuous _longitudinal
(within-lane) acceleration_ and the discrete _lateral (lane-change) movement_
(either keep on the current lane, shift one lane to the left, or shift one
lane to the right).

It is assumed that the controlled vehicle obtains a fixed route from an
independent routing module. There are many possible choices for the routing
module: for example, this could be a centralized module that routes multiple
vehicles to optimize network-level metrics (for example, a module based on
Google Maps), or a decentralized module that simply selects the shortest-
distance route from origin to destination.

The controlled vehicle performs both _discretionary_ lane-changes undertaken
to improve its state (for example, lane-changing to pass a slow leader
vehicle), and _mandatory_ lane-changes that are necessary for the vehicle to
follow the fixed route (e.g. at bifurcations).

The controller operates under hard safety constraints that are derived from
the Vienna convention on road traffic, similar to the analysis carried out in
[13]. The Vienna convention defines a vehicle to be safe if and only if the
gap between the vehicle and its leader vehicle is positive, and in the event
that its leader starts braking with its maximal deceleration, the gap between
the vehicle and its leader is sufficient for the vehicle to be able to react
and stop without crashing. More restrictively, the gap between the leader and
the ego vehicle will be required to be at least $\epsilon$ meters after coming
to a stop, where $\epsilon$ is a parameter (typically, 2 m).

In the literature, it is common to define safety criteria based on a Time-to-
Collision (TTC) threshold [14, 15, 16]. We have argued in favor of the Vienna-
convention-based criteria over TTC-threshold-based criteria in previous work
[4]. A TTC threshold criterion is not sufficient to provide safety guarantees
in the worst case and is based on an ad-hoc threshold choice.

The overall objective is to maximize a weighted combination of measures of
efficiency and comfort, subject to obeying the aforementioned hard safety
constraints and following the prescribed route communicated to the controlled
vehicle. Discomfort is measured by the vehicle’s jerk, while efficiency is
measured by the vehicle’s speed.

We split the task of maximizing efficiency (i.e. maximizing the vehicle’s
speed) into two sub-tasks: 1) driving as closely as possible to the maximal
safe speed within the vehicle’s current lane, 2) if it is possible to increase
the maximal safe speed by changing lanes, carrying out the lane change,
subject to lane-change safety constraints formulated below.

To connect our notion of efficiency (maximizing speed) with that commonly
found in the literature (minimizing headway), we note that if the ego vehicle
is following a leader closely enough that the ego vehicle’s speed is
constrained by the leader (and not the speed limit), driving at the maximal
longitudinal safe speed is equivalent to driving at the lowest safe headway,
so that maximizing the speed is equivalent to minimizing the front-gap subject
to safety constraints.

We now proceed to set the notation used throughout the paper and make the
above requirements more formal.

###  II-A Notation

The notation is illustrated in Figure LABEL:fig:vars. The ego vehicle is
denoted as $E$, with the leader vehicle $L$ in front and the follower vehicle
$F$ behind on the same lane. For a potential left lane change, we define the
left-leader and left-follower as ${L}_{\mathrm{left}}$ and
${F}_{\mathrm{left}}$, respectively. Analogously, the right-leader and right-
follower are denoted by ${L}_{\mathrm{right}}$ and ${F}_{\mathrm{right}}$ for
a potential right lane change.

The distances are denoted as follows: front-gap between $E$ and $L$ as $g$,
back-gap between $E$ and $F$ as $bg$. For the left lane, the front-gap to
${L}_{\mathrm{left}}$ and back-gap to ${F}_{\mathrm{left}}$ are
${g}_{\mathrm{left}}$ and ${bg}_{\mathrm{left}}$, respectively; for the right
lane, these gaps to ${L}_{\mathrm{right}}$ and ${F}_{\mathrm{right}}$ are
${g}_{\mathrm{right}}$ and ${bg}_{\mathrm{right}}$.

In the event that there is no leader or follower, the appropriate gap is set
to $\infty$. In the event that $E$ is driving along the left edge of the road,
we set ${g}_{\mathrm{left}}={bg}_{\mathrm{left}}=-1$, and analogously if $E$
is driving along the right edge, we set
${g}_{\mathrm{right}}={bg}_{\mathrm{right}}=-1$.

The maximal acceleration is denoted by $a_{\bullet}$, where $\bullet$ denotes
one of the vehicles defined above. For example, $a_{E}$ is the maximal
acceleration of the ego vehicle. Similarly, the maximal deceleration is
denoted by $d_{\bullet}$; by convention, $d_{\bullet}$ is a positive number.
The number $r_{\bullet}$ denotes the reaction time of the corresponding
vehicle. For simplicity, we write $r_{E}=r$. The current speed limit is
denoted by $\operatorname{spdlim}_{\bullet}$.

###  II-B Safety constraint formulation

The longitudinal safety constraint is derived as in [17] and [4]. Let the ego
vehicle’s reaction time $r$, minimal stopped gap $\epsilon$ and speed
$v_{E}(t+1)$ in the next time-step be given. Using the laws of kinematics, it
may be derived that: the ego vehicle has a sufficiently large front gap to be
able to stop safely in the event of an emergency stop by the leader if and
only if

$g(t)\geq\frac{v_{E}(t)+v_{E}(t+1)}{2}\,r+\frac{v_{E}^{2}(t+1)}{2d_{E}}-\frac{v_{L}^{2}(t)}{2d_{L}}+\epsilon$
(1)

To avoid negative values on the right-hand side of Equation 1, in this work we
adopt the _defensive principle_ of assuming that $d_{E}\leq d_{L_{\bullet}}$
for any leader vehicle $L_{\bullet}$.

Using Equation 1, treating $g(t)$ as known and $v_{E}(t+1)$ as unknown, it
follows from properties of quadratic polynomials that the ego vehicle’s
maximal safe speed at the next time-step is given by

$-\frac{rd_{E}}{2}+\sqrt{\left(\frac{rd_{E}}{2}\right)^{2}-2d_{E}\left(\frac{rv_{E}(t)}{2}-\frac{v_{L}^{2}(t)}{2d_{L}}-g(t)+\epsilon\right)}$

(2)

The maximal safe speed expressed in Equation 2 is denoted by
$v^{\mathrm{s}}(t+1)$. If the ego vehicle satisfies $v_{E}(t)\leq
v^{\mathrm{s}}(t)$ for all $t$, then (1) is satisfied for all $t$, and
therefore the front-gap is safe for all $t$.

Using similar derivations for imaginary copies of $E$ shifted one lane to the
left or right, we obtain analogous expressions for maximal safe speeds
$v^{\mathrm{s}}_{\mathrm{left}}(t+1)$ and
$v^{\mathrm{s}}_{\mathrm{right}}(t+1)$ on the adjacent lanes. The expressions
have the same form as (2), with $v_{L}$ and $g$ replaced by the appropriate
analogues.

We now formulate the safety constraints that must be satisfied by SECRM-2D:

#### Acceleration safety constraint

For all time-steps $t$, the ego vehicle’s speed must satisfy $v_{E}(t)\leq
v^{\mathrm{s}}(t)$. Equivalently, the ego vehicle’s acceleration must satisfy

$a_{E}(t)\leq
a^{\mathrm{s}}(t):=\frac{v^{\mathrm{s}}(t+1)-v_{E}(t)}{r}\quad\mbox{for all
$t$}$ (3)

#### Lane-change safety constraints

The ego vehicle is not permitted to perform a left lane-change if doing so
would violate the safe-gap inequality (1) for either the
$({F}_{\mathrm{left}},E)$ or the $(E,{L}_{\mathrm{left}})$ vehicle pair.

To elaborate further, we define the constraints for a left lane-change. This
involves the assumption that both the ego vehicle and the left-follower
maintain their current speeds in the subsequent time step. Consequently, this
assumption simplifies equation (1) to a set of two conditions

$\begin{split}{g}_{\mathrm{left}}(t)&\geq
v_{E}(t)\,r+\frac{v_{E}^{2}(t)}{2d_{E}}-\frac{v_{{L}_{\mathrm{left}}}^{2}(t)}{2d_{{L}_{\mathrm{left}}}}+\epsilon\\\
{bg}_{\mathrm{left}}(t)&\geq
v_{{F}_{\mathrm{left}}}(t)\,r_{{F}_{\mathrm{left}}}+\frac{v_{{F}_{\mathrm{left}}}^{2}(t)}{2d_{{F}_{\mathrm{left}}}}-\frac{v_{E}^{2}(t)}{2d_{E}}+\epsilon\end{split}$
(4)

If either of the inequalities in (4) does not hold at time-step $t$, then the
left lane-change action is prohibited at time-step $t$. The right lane-change
action is subject to analogous constraints, replacing ${F}_{\mathrm{left}}$ by
${F}_{\mathrm{right}}$ and ${L}_{\mathrm{left}}$ by ${L}_{\mathrm{right}}$ in
the inequalities.

###  II-C Efficiency and target speeds

As motivated above, the efficiency of a vehicle is measured by its average
speed. A vehicle’s speed is bounded above by two separate factors. First, the
speed is bounded above by the road’s speed limit. Second, in the presence of a
close leader the speed of the ego vehicle is bounded above by
$v^{\mathrm{s}}(t)$. Motivated by this, the target speeds are defined as

$\centering\begin{split}v^{*}_{\mathrm{left}}(t)&=\min(v^{\mathrm{s}}_{\mathrm{left}}(t),\operatorname{spdlim}_{E}(t))\\\
v^{*}(t)&=\min(v^{\mathrm{s}}(t),\operatorname{spdlim}_{E}(t))\\\
v^{*}_{\mathrm{right}}(t)&=\min(v^{\mathrm{s}}_{\mathrm{right}}(t),\operatorname{spdlim}_{E}(t))\end{split}\@add@centering$
(5)

Timestep-by-timestep inefficiency is measured by the difference of the current
speed with the highest of the three target speeds in Equation 5. We note that
the efficiency objective handles both car-following mode (when there is a
close enough leader that constrains the ego vehicle’s speed) and speed-control
mode (when the ego vehicle’s speed is constrained by the speed limit).

###  II-D Comfort definition

To increase the comfort of the passengers, the controller seeks to minimize
the cumulative squared jerk over the controlled vehicle’s trajectory. The
cumulative squared jerk over a trajectory with horizon $T$ is given by

$\sum_{t=1}^{T}\left(\frac{a_{E}(t+1)-a_{E}(t)}{r}\right)^{2}$ (6)

###  II-E Route-following

It is assumed that the vehicle is provided a fixed route, consisting of road
sections $s_{1},\dots,s_{n}$ indexed along the direction of motion. Each
section $s_{i}$ consists of several lanes $\ell_{i1},\dots,\ell_{im}$ indexed
from the right edge of the section toward the left along the direction of
motion. Each lane has a boolean label: whether or not the lane is part of the
route. For example, for a freeway off-ramp, if the vehicle’s route is to
continue on the freeway, the lanes that lead to the off-ramp are not part of
its route. Figure LABEL:fig:route-spec displays an example route in a
roundabout (with lanes that are part of the route labeled with arrows).

A controlled vehicle that is far from the end of its current section may need
to use lanes that are not part of its route in order to improve its
efficiency, but the risk of missing the correct turn becomes higher the closer
the vehicle is to the end of the section. The controlled vehicle must balance
between improving efficiency through discretionary lane-changes and minimizing
the risk of missing its route. The penalty is defined precisely in Section
III.

##  III SECRM-2D

###  III-A Formalization of the control problem as an optimization problem in
an SCMDP

Following the terminology of [18], the problem formulated in Section II may be
formalized as an optimization problem within a Statewise-Constrained Markov
Decision Process (SCMDP). By definition, an SCMDP is a tuple
$(S,A,R,P,\gamma,\rho,C,w)$. Here, $S$ is a set called the state space, $A$ is
a set called an action space, $R(s,a,s^{\prime})$ is the reward model,
$P(s^{\prime}|s,a)$ is the transition model, $\gamma\in[0,1)$ is the discount
factor, $\rho(s)$ is the initial state distribution, $C=(C_{1},\dots,C_{n})$
is a tuple of cost functions, where each $C_{i}$ is a function of
$(s,a,s^{\prime})$, and $w=(w_{1},\dots,w_{n})$ is a tuple of real-valued
weights.

At each environment step, the agent starts from state $s\in S$, takes an
action $a\in A$, transitions to state $s^{\prime}$ with probability
$P(s^{\prime}|s,a)$, and receives reward $R(s,a,s^{\prime})$. It is implicit
in the notation that the transition model and reward model depend only on
$s,a$ (and not on past history of states and actions), which is called the
Markov assumption. The function $\rho$ describes the probability distribution
of initial states.

A policy is a mapping $\pi(a|s)$ that sends a state to a probability
distribution over actions. The tuples of cost functions and weights are used
to restrict the set of feasible policies:

$\Pi_{C,w}=\left\\{\pi\left|\begin{aligned} &\forall
i\in\\{1,\dots,n\\},\forall s\in S\quad C_{i}(s,a,s^{\prime})\leq w_{i}\\\
&\mbox{where }a\sim\pi(\cdot|s),\ s^{\prime}\sim
P(\cdot|s,a)\end{aligned}\right.\right\\}$

The agent’s objective is to find a feasible policy ($\pi\in\Pi_{C,w}$) that
maximizes the cumulative discounted reward

$J(\pi)=E_{\tau\sim\rho,\pi,P}\left(\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t},s_{t+1})\right)$
(7)

where $\tau=s_{0},a_{0},s_{1},a_{1},\dots$ denotes a state-action trajectory,
and $\tau\sim\rho,\pi,P$ denotes that $s_{0}\sim\rho$,
$a_{t}\sim\pi(\cdot|s_{t})$ and $s_{t+1}\sim P(\cdot|s_{t},a_{t})$. Therefore,
$\gamma$ controls how myopic an agent is; $\gamma$ close to 0 makes the agent
more short-sighted, while $\gamma$ close to 1 makes the agent plan over a
longer effective horizon.

### State space

The ego vehicle’s state representation is illustrated in Figure
LABEL:fig:state-space2. Only vehicles within a fixed scan radius $D$ are
considered. For each lane within the scan range, we record features of
$N_{front}$ closest vehicles per lane in front of the ego vehicle and
$N_{back}$ closest vehicles per lane behind the ego vehicle.

For the ego vehicle, the state representation contains its longitudinal
distance from the start of the current section, speed, previous value of
acceleration, index of current section within route, lane index, lateral
speed, and a boolean map over whether or not a lane with a given index is part
of the ego vehicle’s route on the current section. For the other vehicles, the
representation is simpler: it contains the longitudinal distance from the ego
vehicle, speed, and acceleration (the vehicles are sorted according to the
lane they occupy and distance from the ego vehicle along their lane).

### Action space

The action space factors as a 2-tuple $(\alpha,\ell)$, where $\alpha$ is an
acceleration action and $\ell$ is a lane-change action.

The acceleration action is continuous and lies in the closed interval
$[-d_{E},a_{E}]$. The acceleration action is subject to additional statewise
constraint (3), which is enforced through a cost function. The lane-change
action is discrete, and in general lies in the set $\\{\mbox{left, cur,
right}\\}$. The lane-changes are subject to constraints (4), also enforced
through cost functions (please see the example at the end of this section).

### Reward

The reward is a weighted sum of four terms:

#### Efficiency (longitudinal)

The inefficiency penalty is equal to the difference between the current speed
and the target speed:

$R_{\mathrm{eff}}(s,a,s^{\prime})=-\frac{\operatorname{abs}(v^{*}(s)-v_{E}(s))}{v^{*}(s)}$

where $\operatorname{abs}(\cdot)$ denotes the absolute value function. (The
notation $v^{*}(s)$ for the target speed on the current lane was introduced in
Equation 5.)

When the ego vehicle’s speed is constrained by the speed limit (the ego
vehicle is in speed-control mode), speeding is allowed, but penalized.

#### Comfort

The passengers’ discomfort is measured as the square of the jerk of the ego
vehicle in the last time-step. We remind the reader that the jerk of a state-
transition $s,a,s^{\prime}$ is defined as
$j_{E}(s^{\prime})=(a_{E}(s^{\prime})-a_{E}(s))/r$. The comfort penalty is
then defined by

$\begin{split}R_{\mathrm{comf}}(s,a,s^{\prime})&=-\left(\frac{j_{E}(s^{\prime})}{(a_{E}+d_{E})/r}\right)^{2}\\\
&=-\left(\frac{a_{E}(s^{\prime})-a_{E}(s)}{a_{E}+d_{E}}\right)^{2}\end{split}$

#### Discretionary lane-changing

Let $\ell$ denote the lane-change part of the action. The discretionary lane-
change reward is given by

$\displaystyle
R_{\mathrm{discr}}(s,a,s^{\prime})=\frac{1}{v^{*}}\begin{cases}C(v^{*}_{\mathrm{left}},v^{*})(v^{*}_{\mathrm{left}}-v^{*}),&\ell=\mathrm{left}\\\
C(v^{*}_{\mathrm{right}},v^{*})(v^{*}_{\mathrm{right}}-v^{*}),&\ell=\mathrm{right}\\\
0,&\ell=\mathrm{cur}\end{cases}$

(8)

where for any $v_{0},v_{1}$ we define

$\displaystyle C(v_{0},v_{1})$
$\displaystyle=\frac{1-\gamma^{T(v_{0},v_{1})}}{1-\gamma},\quad\mbox{and
where}$ $\displaystyle T(v_{0},v_{1})$
$\displaystyle=\operatorname{round}\left(\frac{\operatorname{abs}\left(v_{0}-v_{1}\right)}{a_{E}}\cdot\frac{1}{r}\right)$

and where the state-dependence of the target speeds is omitted for readability
($\gamma$ is the discount factor).

We now motivate the chosen form of $R_{\mathrm{discr}}$.

We would like to reward the agent for changing to a lane with a higher target
speed, and penalize the agent for changing to a lane with a lower target speed
(as part of the efficiency optimization). This target-speed-maximization
formulation compactly encodes the appropriate action for several different
scenarios, including scenarios when there is a faster-moving leader on one of
the adjacent lanes, and scenarios when there is no leader on an adjacent lane.

For brevity, we shall discuss left lane-changes only; right lane-changes are
analogous. The previous paragraph motivates the initial choice of
$R=v^{*}_{\mathrm{left}}-v^{*}$ (which may be negative) as the discretionary
lane-changing reward. However, we observe that if the agent switches to a lane
with $v^{*}_{\mathrm{left}}>v^{*}$, in the consequent time-steps the agent
will receive larger efficiency penalties (than it would have if the lane-
change was not performed) until the speed difference
$v_{E}-v^{*}_{\mathrm{left}}$ is less than or equal to $v_{E}-v^{*}$. In other
words, the cumulative reward the agent will receive may be negative even if
the agent switches to a lane with a higher target speed.

Therefore, the immediate lane-change reward is boosted to compensate for the
penalty that gets accrued after performing the lane-change. The boost
coefficient $C(v_{0},v_{1})$ may be chosen empirically. Instead, we
approximate as follows. In the ideal case, it will take approximately
$T=T(v^{*}_{\mathrm{left}},v^{*})$ time-steps for the ego vehicle to make up
the speed difference. Taking discounting into account, we choose the immediate
reward to be $R+\gamma
R+\gamma^{2}R+\cdots+\gamma^{T-1}R=C(v^{*}_{\mathrm{left}},v^{*})R$ (geometric
series), which is large enough to offset the cumulative efficiency penalty
during subsequent catch-up.

#### Mandatory lane-changing (Route-following)

Route-following is also achieved using a reward term. As described in Section
II, the vehicle is provided a fixed route consisting of sections
$s_{1},\dots,s_{n}$, with each section $s_{i}$ consisting of several lanes
$\ell_{i1},\dots,\ell_{im}$.

Let $s_{i}$ and $\ell_{ij}$ denote the current section and lane, respectively.
Let $\Delta(\ell_{ij})$ denote the smallest number of lane changes that are
necessary in order to reach an on-route lane from $\ell_{ij}$. Let $D(s)$
denote the current longitudinal distance to the end of section $s_{i}$. Then
we define the immediate penalty from the current state as

$R_{\mathrm{route}}(s,a,s^{\prime})=-\frac{\Delta(\ell_{ij})}{1+D(s)}$

For example, if the agent’s route takes an off-ramp from a freeway at the end
of its current section, but the agent is not currently in the exiting lane,
then the agent gets a penalty inversely proportional to the distance to the
exit and proportional to the number of lane changes necessary to reach the
off-ramp lane. Please see Figure 1 for a visualization of the the penalties
$R_{\mathrm{route}}$ for both routes in the freeway off-ramp scenario.

Figure 1: The mandatory lane-change penalty $R_{\mathrm{route}}$ accrued by a
vehicle in a freeway off-ramp scenario, based on the vehicle’s current
position and route. For clarity of the illustration, the values are capped
below at $-0.5$. Left: The vehicle route exits the freeway at the off-ramp.
Right: The vehicle route remains on the freeway.

#### Combined optimization objective

Putting the four terms together, the reward is then given by

$\displaystyle R(s,a,s^{\prime})=$ $\displaystyle
R_{\mathrm{eff}}(s,a,s^{\prime})$ (9) $\displaystyle+\xi_{\mathrm{comf}}\cdot
R_{\mathrm{comf}}(s,a,s^{\prime})$ $\displaystyle+\xi_{\mathrm{discr}}\cdot
R_{\mathrm{discr}}(s,a,s^{\prime})$ $\displaystyle+\xi_{\mathrm{route}}\cdot
R_{\mathrm{route}}(s,a,s^{\prime})$

where $\xi_{\mathrm{comf}}\geq 0,\,\xi_{\mathrm{discr}}\geq
0,\,\xi_{\mathrm{route}}\geq 0$ are the reward weights (hyperparameters).

The overall optimization objective is to find the optimal feasible policy

$\pi^{*}=\operatorname{argmin}_{\pi\in\Pi_{C,w}}J(\pi)$

where $J(\pi)$ is the expected cumulative discounted reward, as defined in
Equation 7.

##### Normalization

The normalization factors in the reward terms $R_{\mathrm{comf}}$ (division by
$(a_{E}+d_{E})/r$) and $R_{\mathrm{discr}}$ (division by $v^{*}$) are not
logically necessary. The normalization terms bring the components of the
reward to similar scales, making the choice of weights in (9) simpler. In
addition, it is standard practice in Deep RL to scale the reward terms to an
interval such as $[-1,1]$ or $[-10,10]$ in order to aid neural network
training.

##### Unification of mandatory and discretionary lane-changing

The composite objective function described in Equation 9 is a unified approach
to optimizing both discretionary and mandatory lane change decisions. To the
best of our knowledge, ours is the first work in the application of Deep RL to
autonomous driving where both types of lane-change are treated in a unified
manner.

### Costs and weights

The hard constraints derived in Section II may all be formulated as statewise
constraints using cost-functions and weights. For example, the acceleration
constraint (3) may be rewritten in the form $\alpha-a^{\mathrm{s}}(s)\leq 0$,
and the lane-change constraints (4) in the form

$\displaystyle
I_{\\{\ell=\mathrm{left}\\}}(a)\left(v_{E}(s)r+\frac{v_{E}^{2}(s)}{2d_{E}}-\frac{v^{2}_{{L}_{\mathrm{left}}}(s)}{2d_{{L}_{\mathrm{left}}}}+\epsilon-{g}_{\mathrm{left}}(s)\right)\leq
0$

where $I_{S}(x)$ denotes the indicator function of the set $S$ ($I_{S}(x)=1$
if $x\in S$ and 0 otherwise), and $(\alpha,\ell)$ are the two components of
the action $a$.

###  III-B Learning an Optimal Policy

The controller is trained using the Deep Deterministic Policy Gradient
algorithm (DDPG) [19] with a continuous action-space encoding.

#### Action space encoding

To apply DDPG to our statewise-constrained and mixed discrete-continuous
problem, actions are encoded as pairs $(x,y)\in[-3,3]^{2}$.

The coordinate $x$ is used to obtain the acceleration action as follows.
Combining the safety acceleration constraint (3) with the upper and lower
bounds on acceleration, we obtain the acceleration upper bound
$a_{\mathrm{ub}}(s)=\operatorname{clip}(a^{\mathrm{s}}(s),-d_{E},a_{E})$,
where the notation $\operatorname{clip}(a,b,c)=\min(\max(a,b),c)$ is used. The
coordinate $x$ is affinely projected onto the interval
$[-d_{E},a_{\mathrm{ub}}(s)]$ by $x\mapsto-
d_{E}+\frac{x+3}{6}(a_{\mathrm{ub}}(s)+d_{E})$. The resulting acceleration
action satisfies all required constraints.

The coordinate $y$ is projected onto the lane-change action space component by

$y\mapsto\begin{cases}\mathrm{left},&-3\leq y<-1\\\ \mathrm{cur},&-1\leq
y<1\\\ \mathrm{right},&1\leq y\leq 3\end{cases}$

Furthermore, if the lane-change action can’t be applied (for example, a left
lane-change on the left edge of the road), the vehicle stays on its current
lane.

#### DDPG

DDPG is a model-free, off-policy actor-critic algorithm. DDPG is an analogue
of the DQN algorithm [1] for continuous action spaces.

Similarly to DQN, DDPG iteratively updates an approximation of the state-
action value function $Q^{*}(s,a)$ of an optimal policy. The approximate
function is often represented by a neural network with weights $\theta$, and
denoted by $Q_{\theta}(s,a)$.

However, finding $\operatorname{argmax}_{a}Q_{\theta}(s,a)$ may itself present
a difficult problem when the action space is continuous. Unlike DQN, in DDPG
$Q_{\theta}$ is not used to directly obtain a policy. Instead, a deterministic
policy $\pi_{\phi}$ is trained ($\pi$ is also often represented by a neural
network with weights $\phi$) to maximize $Q_{\theta}(s,\pi_{\phi}(s))$ from
each state.

Because of the roles the two functions play in training, $Q_{\theta}$ is
called the critic and $\pi_{\phi}$ the actor.

The training loop proceeds as follows. For each environment step, the agent’s
action is obtained from the deterministic policy $\pi_{\phi}$ perturbed by an
Ornstein-Uhlenbeck noise process for exploration. The experience tuple
$(s,a,r,s^{\prime})$ is stored in a replay buffer. Then, keeping $\phi$ fixed,
the network $Q_{\theta}$ is updated using minibatch stochastic gradient
descent to minimize the loss function

$L(\theta)=\frac{1}{\left|B\right|}\sum_{(s,a,r,s^{\prime})\in
B}\frac{1}{2}\left(r+\gamma
Q_{\theta}(s^{\prime},\pi_{\phi}(s^{\prime}))-Q_{\theta}(s,a)\right)^{2}$

where $B$ is a minibatch of experience tuples sampled from the replay buffer.
The update target $r+\gamma Q_{\theta}(s^{\prime},\pi_{\phi}(s^{\prime}))$ is
motivated by the Bellman optimality equation as in $Q$-learning, but with the
action decided by the actor network instead of being the action $a^{\prime}$
that maximizes $Q_{\theta}(s^{\prime},a^{\prime})$ (such $a^{\prime}$ may
again be difficult to compute with a continuous action space).

Then, keeping $\theta$ fixed, the network $\pi_{\phi}$ is updated using
minibatch stochastic gradient ascent to maximize the expected reward

$J(\phi)=\frac{1}{\left|B\right|}\sum_{(s,a,r,s^{\prime})\in
B}Q_{\theta}(s,\pi_{\phi}(s))$

For greater training stability, target networks are introduced in the above
procedure. For more details on DDPG, please see the original paper [19].

As demonstrated in Figure LABEL:frame, our main framework is a hybrid learning
framework. Based on the current traffic environment, the maximal safe target
speed is calculated. The RL vehicle will consider the target speed and decide
on the longitudinal acceleration value and the lateral decision on whether to
switch left, right, or stay in the main lane. Based on feedback from the
environment, the RL algorithm will learn the policy.

##  IV SECRM-2D Training setup

###  IV-A Experiment environments

Training and evaluation are carried out in the SUMO microsimulator using the
TraCI Python API [20]. The simulation step-length of 0.1s is used, which is
also the controlled vehicle’s reaction time $r$.

Experiments are performed in two different environments: a simple loop
network, and a network based on a real-world freeway.

####  IV-A1 Loop network

The loop network of Figure 4 is used as one of the experiment environments.
The effect of the curvature on vehicle speeds is disabled, which makes the
network effectively an infinite freeway (without on-ramps and off-ramps). The
loop network is used to evaluate efficiency, comfort and discretionary lane-
changing in isolation from route-following.

####  IV-A2 Interchange of Queen Elizabeth Way (QEW) and Erin Mills Parkway /
Southdown Road

We created a network based on real road geometry, the Queen Elizabeth Way
(QEW) interchange with Erin Mills Parkway (on the North side) and Southdown
Road (on the South side) near Toronto, Canada. The network is shown in Figure
4 (in SUMO) and Figure 4 (in Google Maps). The off-ramp and on-ramp to the QEW
are used to test route-following tasks (in addition to optimization of
efficiency and comfort, subject to safety constraints, as before).

Figure 2: Geometry of the loop network. The effect of curvature on vehicle
speed has been disabled.

Figure 3: Geometry of the interchange of Queen Elizabeth Way (QEW) and Erin
Mills Parkway / Southdown Road (SUMO).

Figure 4: Geometry of the interchange of Queen Elizabeth Way (QEW) and Erin
Mills Parkway / Southdown Road (Google Maps)

###  IV-B Modelling uncontrolled vehicles

The uncontrolled vehicles are modelled using the “Krauss” car-following model
(SUMO default) and the “SL2015” lane-change model cf. [20]. This configuration
may model either human drivers or other AVs. For brevity, we sometimes refer
to the uncontrolled vehicles as human-driver vehicles (HVs).

###  IV-C Training scenarios

To help generalization to varied or unseen scenarios during testing, the
target speeds (speed limits) and initial speeds of the human-driver vehicles
are varied episode-to-episode.

####  IV-C1 Loop network

The loop network is a lightweight network, which allows for faster training
and iteration. Each episode is 5,000 time-steps long, to gather sufficient
experience for learning.

The controlled vehicle is trained with 25 human-driver vehicles. The human-
driver vehicles are injected from a designated starting section with random
departure speeds. Each episode, the human-driver vehicles’ speed limit is
resampled uniformly at random from $\\{10,20,22,25\\}$, and the controlled
vehicle’s speed limit from $\\{16,22,28,36\\}$. The set of controlled vehicle
speeds is higher than the set of human-driver vehicle speeds to aid the
controlled vehicles in learning to bypass the slower human-driver vehicles, in
order to achieve higher efficiency.

In training, all reward weight hyperparameters are set to one:
$\xi_{\mathrm{comf}}=\xi_{\mathrm{discr}}=\xi_{\mathrm{route}}=1$.

####  IV-C2 QEW

In the QEW network, the simulation horizon is 6,000 steps, to allow
sufficiently many environment steps for the RL agent to leave the network.

The uncontrolled vehicles are generated at a fixed inflow rate at the Southern
boundary of the freeway mainline. The inflow rates are uniformly sampled
between 500 veh/hour and 1000 veh/hour. The controlled vehicle is generated at
the Southern boundary of the freeway mainline after a warm-up period. The
speed limits for the controlled vehicle and uncontrolled vehicles are sampled
from the same sets as for the loop network.

The controlled vehicle has two possible routes: to stay in the freeway or take
the off-ramp. Each episode, we assign the route to the vehicle randomly, each
with probability $1/2$.

As in the loop network, in training, all reward weights are set to one
$\xi_{\mathrm{comf}}=\xi_{\mathrm{discr}}=\xi_{\mathrm{route}}=1$.

###  IV-D DDPG parameters

The configuration of the DDPG model is summarized in Table I. Five random
seeds were sampled, and training was run for 1000 episodes for each seed. The
checkpoint that achieved the highest cumulative reward across the 5 seeds was
selected for evaluation.

TABLE I: DDPG and simulation Configuration

Parameter | Value
---|---
Discount factor ($\gamma$) | 0.99
Simulation time step | 0.1 second
Maximum Episode horizon |  | 5,000 (Loop)
---
6,000 (QEW)
Critic $Q_{\theta}$ learning rate | 3e-4
Actor $\pi_{\phi}$ learning rate | 3e-4
Target soft update rate | 0.005
Warm-up | 1,000 steps
Replay buffer size | 1e+6
Actor and critic MLP NN number of layers | 3
Actor and critic NN number of nodes in hidden layer | 256
NN Activation functions | torch.relu
NN Last activation function | torch.tanh
Batch size for gradient ascent | 64

###  IV-E Convergence

Figure 5 shows the convergence of the efficiency and comfort rewards during
training in the QEW network. The solid curves in the figure display the
averages of the two rewards during training over 5 different training runs
with different random seeds, and the shaded area represents values within one
standard deviation across the 5 training runs. The scores initially improve
rapidly, and converge to stable values, with slight peaks around episode 400.
The training in the loop network had similar dynamics.

In the remaining sections, we shall analyze the trained policy and compare it
against several baselines.

Figure 5: Convergence of the Efficiency (top) and Comfort (bottom) rewards
during training.Initial few epochs, the agent adopts a conservative policy,
often remaining stationary, resulting in low efficiency scores. Over time,
however, it learns to balance safety and efficiency, achieving high levels of
driving comfort.

##  V Long-Term Longitudinal Steady-State, and Platooning

In this section, the long-term longitudinal behaviour of a collection of
SECRM-2D vehicles is analyzed. We begin by studying the long-term longitudinal
behaviour of a collection of vehicles that drive at their maximal safe speed.
For a single vehicle with a leader at a constant speed, detailed results are
obtained. Then, qualitative implications for collections of SECRM-2D vehicles
are discussed. Our conclusion is that, speed-limit permitting, in the long-
term the vehicles form platoon driving at the same speed as the lead vehicle,
with fixed gaps between consecutive vehicles that are determined by the leader
speed and the vehicle’s reaction time.

###  V-A Single Follower with a Constant-Speed Leader

Consider a two-vehicle system, where the leader vehicle drives at a constant
speed $w$, and the follower always drives at its maximal safe speed. In
addition, to simplify the analysis, we assume that the speed limit is
infinite, there is no acceleration limit, and that there is a single lane. We
discuss relaxations of these assumptions at the end of this section.

The motion of the follower can be fully described by the two-dimensional
discrete-time dynamical system

$(g_{t},v_{t})$

where $g_{t}$ is the gap between the follower and the leader at time-step $t$,
and $v_{t}$ is the velocity of the follower at time-step $t$, with update
rules

$\displaystyle\begin{split}g_{t+1}&=g_{t}-r(v_{t}-w)\\\
v_{t+1}&=-\frac{rd_{E}}{2}+\sqrt{\left(\frac{rd_{E}}{2}\right)^{2}-2d_{E}\left(\frac{rv_{t}}{2}-\frac{w^{2}}{2d_{L}}-g_{t}+\epsilon\right)}\end{split}$

where the velocity update is obtained from Equation 2 for
$v^{\mathrm{s}}(t+1)$.

To begin the analysis, it is helpful to notice that Equation 2 may be
rearranged to

$v^{\mathrm{s}}(t+1)=-\frac{rd_{E}}{2}+\sqrt{\left(v_{L}(t)+\frac{rd_{E}}{2}\right)^{2}+2d_{E}\,\delta
g(t)-d_{E}r\,\delta v(t)}$

(10)

where

$\begin{split}\delta
g(t)&=g(t)-v_{L}(t)r-\frac{d_{L}-d_{E}}{2d_{L}d_{E}}v_{L}(t)^{2}-\epsilon\\\
\delta v(t)&=v_{E}(t)-v_{L}(t)\end{split}$ (11)

This rearrangement makes the steady-state equilibrium target more transparent.

######  Prop 1.

The state
$\displaystyle(g^{*},v^{*})=\left(wr+\frac{d_{L}-d_{E}}{2d_{L}d_{E}}w^{2}+\epsilon,\
w\right)$ is a system equilibrium.

###### Proof.

Indeed, assuming that $(g_{t},v_{t})=(g^{*},v^{*})$, we compute that

$\displaystyle\begin{split}g_{t+1}&=g_{t}-r(0)=g_{t}\\\
v_{t+1}&=-\frac{d_{E}r}{2}+\sqrt{\left(w+\frac{d_{E}r}{2}\right)^{2}+2d_{E}(0)-d_{E}r(0)}=w=v_{t}\end{split}$

So that $(g_{t+1},v_{t+1})=(g_{t},v_{t})=(g^{*},v^{*})$. ∎

######  Prop 2.

For $w>0$, the equilibrium point $(g^{*},v^{*})$ is asymptotically stable.
That is, there exists an open set $U\subseteq\mathbb{R}^{2}$ containing
$(g^{*},v^{*})$ such that for all initial points $(g_{0},v_{0})$ in $U$,

$\lim_{t\rightarrow\infty}(g_{t},v_{t})=(g^{*},v^{*}).$

###### Proof.

To demonstrate asymptotic stability, it is sufficient to look at the
linearization of the system about the equilibrium point $(g^{*},v^{*})$ and
show that both eigenvalues of the Jacobian matrix have norm $<1$ [21, Th.
4.7].

The Jacobian of the update functions at the point $(g,v)$ is

$\displaystyle\begin{pmatrix}1&-r\\\
\frac{2d_{E}}{2\sqrt{A(g_{t},v_{t})}}&\frac{-d_{E}r}{2\sqrt{A(g_{t},v_{t})}}\end{pmatrix}$

where $A(g_{t},v_{t})=\left(w+\frac{d_{E}r}{2}\right)^{2}+2d_{E}\,\delta
g(t)-d_{E}r\,\delta v(t)$.

Therefore, at the equilibrium point $(g^{*},v^{*})$, we have the Jacobian

$\displaystyle\begin{pmatrix}1&-r\\\
\frac{2d_{E}}{2w+d_{E}r}&\frac{-d_{E}r}{2w+d_{E}r}\end{pmatrix}$

The eigenvalues of the Jacobian at $(g^{*},v^{*})$ are

$\lambda_{\pm}=\frac{w\pm\sqrt{w^{2}-2wd_{E}r-d_{E}^{2}r^{2}}}{2w+d_{E}r}$

It is elementary to verify that $\left|\lambda_{\pm}\right|<1$ whenever $w>0$
(please see Appendix A). ∎

######  Remark.

For the $w=0$ case, we have complex eigenvalues $\lambda_{\pm}=\pm\sqrt{-1}$,
both of which have norm 1. Therefore, the central eigenspace spans the entire
space and we cannot conclude whether the equilibrium point is stable or not
from general theory [22, p. 124]. Empirically, however, we find that the $w=0$
case behaves similarly to the $w>0$ case.

#### Removal of simplifying assumptions

We briefly discuss how removing the simplifying assumptions made at the start
affects the analysis. With a bounded maximal acceleration, the follower may
need an initial speed-up period in order to reach a high enough speed to catch
up with the leader, after which the analysis reduces to the previous case.
With a speed-limit, the analysis proceeds as before as long as $w$ is lower
than the speed limit. With $w$ equal to the speed limit, the follower will not
be able to catch up to the leader.

###  V-B Qualitative implications for SECRM-2D platoon formation

In longitudinal motion, SECRM-2D is rewarded for taking the action that brings
its velocity as close to $v^{\mathrm{s}}(t+1)$ as possible, subject to
minimizing the discomfort penalty integrated over its trajectory (and
acceleration/speed-limit constraints).

Thus, although this is no longer subject to proof, our expectation is that a
well-trained SECRM-2D model following a constant-speed leader will have
similar long-term equilibrium properties to the system analyzed in the
previous section, that is, will drive at speed $w$ with gap
$wr+\frac{d_{L}-d_{E}}{2d_{L}d_{E}}w^{2}+\epsilon$, and that this equilibrium
will be stable with respect to small perturbations in the initial conditions.

For a platoon of SECRM-2D vehicles following a fixed-speed leader, we proceed
to argue inductively. As vehicle $n$ approaches its equilibrium with its
respective leader, the speed of vehicle $n$ will continue to converge to the
common platoon speed $w$. Therefore, vehicle $n$ will start to act as a
constant-speed (up to a small error) leader for vehicle $n+1$. We may then
apply our analysis to the vehicle $(n,n+1)$ system, concluding as before that
in steady-state vehicle $n+1$ will have gap and velocity described by the
previously obtained formulas.

Thus, we expect that a well-trained SECRM-2D system will form a platoon with a
common velocity $w$ and inter-vehicle gaps given by

$wr+\frac{d_{L}-d_{E}}{2d_{L}d_{E}}w^{2}+\epsilon$

This expectation is confirmed by empirical tests. An example of a four-vehicle
platoon (constant-speed leader and three SECRM-2D followers) on a single-lane
loop reaching its steady-state is displayed in Figure 6.

A closer analysis of the string-stability properties of the resulting platoon
will be the subject of future work.

Finally, we note that if in addition the vehicle velocities are constrained by
a speed limit, it may not be possible for a follower vehicle to catch up to
its leader (if the leader drives at the speed limit). Therefore, with a speed-
limit a collection of SECRM-2D vehicles is expected to form into several
platoons, grouped by whether or not the follower is able to catch the leader
under the speed-limit constraints.

Figure 6: Convergence to steady-state of a platoon consisting of a leader
(blue) driving with a constant speed of 25 m/s and three SECRM-2D follower
vehicles (orange, green, red). The minimal gap setting is $\epsilon=4$ m. Each
vehicle is 5 m long. Left: Relative timespace diagram (longitudinal distance
of each vehicle from the leader as a function of time). Right: Vehicle
velocities. The steady-state distances match our theoretically predicted
values (dotted lines). TABLE II: Loop network statistics comparison. 5000
simulation steps with 30 random seeds

Method | Normal driving | Heavy traffic | Emergency braking
---|---|---|---
Speed (m/s) | Jerk (m/s3) | Crash rate | Speed (m/s) | Jerk (m/s3) | Crash rate | Speed (m/s) | Jerk (m/s3) | Crash rate
IDM+MOBIL | 27.48 | 0.87 | 0% | 25.63 | 0.04 | 0% | 26.76 | 0.99 | 0%
Gipps+Greedy | 32.51 | 1.39 | 0% | 26.59 | 0.09 | 0% | 30.51 | 1.47 | 0%
PPO-based RL[11] | 28.84 | 1.31 | 3% | 25.88 | 0.03 | 7% | 28.11 | 1.20 | 21%
SECRM-2D | 32.45 | 0.86 | 0% | 26.32 | 0.02 | 0% | 31.73 | 0.89 | 0%

##  VI Baselines

In the rest of this work, SECRM-2D is evaluated in several experiments, and
compared with the following baselines:

  * •

IDM with MOBIL: The “Intelligent Driver Model” (IDM) [23] car-following with
“Minimizing Overall Breaking Induced by Lane-changes” (MOBIL) [24] lane-
changing is a common model of realistic driving (which can be used to model
either human drivers or AVs).

  * •

PPO-based lane-change maneuver (Ye et al. [11]) : a good RL baseline for the
discretionary lane-change comparison.

  * •

Highway exiting planner (Cao et al. [10]):  The deep reinforcement learning-
enhanced highway exiting planner [10] is another baseline. The RL framework is
based on Monte Carlo Tree Search (MCTS) with safety enhancements based on
traffic rule constraints. This baseline is used to evaluate the performance of
our agent’s route-following. This is a good baseline for mandatory lane change
comparison.

  * •

Gipps with greedy lane selection: In the case when the ego vehicle’s speed is
constrained by a leader vehicle (as opposed to the free-driving regime in
which the speed is constrained by the road’s speed limit), the Gipps car-
following model [17] is also based on the Vienna safety convention, similar to
our previous longitudinal car-following work SECRM [4]. In the terminology of
this paper, the Gipps model always drives at the maximal safe velocity
$v^{\mathrm{s}}$ defined in Equation 2, disregarding comfort. In [4], we
noticed that SECRM converges to Gipps if the comfort weight is set to 0. (It
should be noted that in the case when the ego vehicle’s speed is constrained
by the speed limit, Gipps switches to a model fit to experimental human-driver
data, and is suboptimal compared to [4].)

We extend Gipps with a lane-changing model that switches to one of the
adjacent lanes whenever the difference in target speeds with the current lane
is larger than a threshold (typically, the threshold is 3 m/s), subject to
similar lane-change safety constraints as SECRM-2D. The resulting model is
called Gipps with greedy lane selection (Gipps+Greedy). We conjecture that
SECRM-2D should converge to Gipps with greedy lane selection in the case that
the comfort weight $\xi_{\mathrm{comf}}$ is set to 0. Gipps with greedy lane
selection is included as an extreme baseline that optimizes efficiency while
disregarding comfort.

For the mandatory lane change decisions for the baselines, we use the rule-
based method from SUMO [25].

##  VII Experiments on Discretionary Lane-Changing in the Loop Network

In this section, the controller trained in the loop network as described in
Section IV-C1 is evaluated. Three test scenarios are created for the loop
network,:

  * •

Normal driving. The controller is tested with 25 human-driver vehicles. The
human-driver vehicles have the same type of driving model as in training. The
speed-limit for the human-driver vehicles is chosen to be 17 m/s, and the
speed-limit for the controlled vehicle is 34 m/s. We are careful to select
speed-limit values that cannot be sampled during training, so that the
controller must generalize from train to test.

  * •

Congested traffic. The heavy traffic scenario is similar to the previous
regular driving scenario, but the number of human-driver vehicles is doubled
to 50 to evaluate how well the controlled vehicle can handle congested
scenarios.

  * •

Emergency braking. To measure the controlled vehicle’s safety performance, in
the emergency braking scenario the human-driver vehicles will undergo
emergency braking in a specific section with maximum deceleration until
reaching minimum speed of 3 m/s. We applied emergency braking in different
sections of the loop network in the testing phase in order to evaluate the
generalization of the controller.

### Results analysis

Table II compares the average speed, jerk and crash rate of SECRM-2D with
three baselines in the three test scenarios described above.

Overall, SECRM-2D is comparable with the best performers in both efficiency
(average speed) and comfort (average jerk), and has 0% crash rate. However, we
note the other best performer in either speed or jerk scores lower on the
other metric, making SECRM-2D the best overall controller. More specifically,
SECRM-2D and Gipps+Greedy reach the best average speed, but SECRM-2D has
significantly lower jerk. IDM and SECRM-2D have comparable jerk, but SECRM-2D
has superior efficiency (higher average speed).

The results match intuition: we expect SECRM-2D to converge to Gipps+Greedy in
the limit as $\xi_{\mathrm{comf}}\rightarrow 0$. SECRM-2D trades in some
potential loss of efficiency in exchange for highly improved comfort. On the
other hand, IDM is smoother, but is either unsafe or inefficient because of
its fixed (non-dynamic) target gap (please refer to our previous work [4] for
further comparison with the IDM non-dynamic gap).

In the congested traffic scenario, we observe fewest differences between the
compared methods, as the vehicles are packed closely together, constraining
movement and making overtaking difficult.

During testing, the SECRM-2D vehicle learned to bypass the slower vehicles in
both normal driving and emergency stop scenarios, improving efficiency. The
method is successful in learning effective discretionary lane changes.

We highlight that SECRM-2D achieves 0% crash rate in all three scenarios. On
the other hand, the compared RL baseline (PPO-based RL) has a 3–7% crash rate
in regular and congested scenarios and the very high 21% crash rate in the
emergency braking scenario. These results support our motivating claim that
while RL is a promising approach for reaching autonomous driving, without
stricter action constraints (such as ones put in place for SECRM-2D), ensuring
sufficient safety for deployment may be difficult.

TABLE III: Bypassing scenario results with equal probability of route staying
on freeway and route taking off-ramp.

Method | $H=5$ | $H=10$ | $H=20$
---|---|---|---
Speed (m/s) | Jerk (m/s3) | Crash Rate | Route Miss Rate | Speed (m/s) | Jerk (m/s3) | Crash Rate | Route Miss Rate | Speed (m/s) | Jerk (m/s3) | Crash Rate | Route Miss Rate
IDM+MOBIL | 18.67 | 1.23 | 13% | 31% | 19.21 | 1.39 | 12% | 24% | 20.01 | 1.03 | 3% | 4%
Gipps+Greedy | 20.34 | 1.86 | 14% | 27% | 23.98 | 2.01 | 15% | 20% | 23.47 | 1.32 | 5% | 0%
PPO-based RL | 19.31 | 1.31 | 23% | 33% | 20.12 | 1.38 | 24% | 27% | 21.31 | 1.23 | 16% | 19%
Mandatory Lane Change RL | 18.21 | 1.71 | 18% | 17% | 19.12 | 1.58 | 17% | 13% | 19.98 | 1.31 | 5% | 1%
SECRM-2D | 20.38 | 1.08 | 0% | 15% | 23.08 | 1.13 | 0% | 10% | 23.42 | 1.09 | 0% | 0%

TABLE IV: Emergency braking scenario results

Method | Jerk (m/s3) | Crash Rate
---|---|---
IDM+MOBIL | 0.95 | 6%
Gipps+Greedy | 2.43 | 12%
PPO-based RL | 1.08 | 24%
Mandatory Lane Change RL | 1.91 | 17%
SECRM-2D | 0.94 | 0%

TABLE V: Merging scenario results

Method | Speed (m/s) | Jerk (m/s3) | Crash Rate | Merge Miss Rate
---|---|---|---|---
IDM+MOBIL | 18.67 | 1.23 | 13% | 31%
Gipps+Greedy | 20.34 | 1.86 | 14% | 27%
PPO-based RL | 19.31 | 1.31 | 23% | 33%
Mandatory Lane Change RL | 18.21 | 1.71 | 11% | 17%
SECRM-2D | 22.53 | 1.21 | 0% | 13%

TABLE VI: Bypassing HW 5: Dependence on Reaction Time Method | Speed (m/s) | Jerk (m/s3) | Crash Rate
---|---|---|---
$r_{E}=r_{F}=0.1$ | 21.29 | 1.09 | 0%
$r_{E}=r_{F}=1$ | 19.21 | 1.08 | 0%
$r_{E}=0.1,\ r_{F}=1$ | 20.38 | 1.08 | 0%

##  VIII Experiments on Bypassing, Route-Following, and Merging in the QEW

In this section, the controller trained in the QEW network as described in
Section IV-C2 is evaluated. We aim to investigate: (1) whether our agent can
conduct safe, efficient and comfortable lane-changes; (2) whether our agent
can follow the provided route, i.e., stay on main-lane or exit; (3) whether
our agent guarantees safety including in emergency braking; (4) whether our
agent can generalize to unseen scenario configurations.

To ensure that the test scenario’s configuration is different from training to
avoid over-fitting, we use 15 m/s for human-driver vehicles’ speed limit and
25 m/s for the controlled vehicle’s speed limit.

Three test scenarios are created for the QEW network:

  * •

Bypassing. The motivation for constructing the bypassing test environment is
to evaluate the ability of the controlled vehicle to conduct lane changes to
bypass slower vehicles. The construction of the environment is based on the
following rule as illustrated in Figure 7. The head-to-head distance between
adjacent human-driver vehicles is maintained at $H$. Lane-changing for human-
driver vehicles is disabled. We set the speed of all human-driver vehicles as
$v_{\mathrm{human}}$ m/s which is slower than the controlled vehicle’s target
speed of $v_{\mathrm{AV}}$ m/s. The controlled vehicle (in black) is
initialized behind of the human-driver vehicles’ zig-zag fleet. The controlled
vehicle’s route is assigned to be either to stay on the freeway or exit using
the off-ramp with equal probability of $1/2$.

Figure 7: Diagram of the bypassing scenario in the QEW network.

  * •

Emergency braking. As shown in Figure 8, to test the ability of SECRM-2D to
handle emergency braking, another scenario is constructed. The headway
distance between each human-driver vehicle $H$ is set to be too small for the
controlled vehicle to bypass, forcing the controlled vehicle to stay behind.
Maximum deceleration of $-3$ m/s2 is applied to each human-driver vehicle in
the shaded area. In the emergency braking scenario in the loop network, the
braking leader vehicle occupied only one of the lanes, which permitted the
SECRM-2D-controlled vehicle to lane-change to avoid a crash. In the QEW test,
SECRM-2D cannot lane-change to avoid a crash and must brake.

Figure 8: Diagram of the emergency braking scenario in the QEW freeway.

  * •

Merging. Another scenario is merging from an on-ramp. The relevant portion of
the network is illustrated in Figure 9. The human-driver vehicles will keep on
generating on the mainline with $H=5$ to make it challenging. The controlled
vehicle is generated in the merge lane, and the controlled vehicle needs to
merge into the mainline before the lane drop. The merge will be considered
failed if the AV still cannot merge to mainline when the simulation time steps
have reached the maximum horizon in QEW set in Table I.

Figure 9: Diagram of the merging scenario.

### Results analysis

A simulation demo can be found at [26].

As shown in Figure 10, to validate the proposed framework, the training went
through an evaluation phase (with 30 random seeds) every 100 epochs. The
efficiency, comfort, and routing objectives were tracked during training. The
results are compared with two baselines: IDM+MOBIL and Gipps+Greedy To make
the results easier to understand, the values are normalized by IDM+MOBIL. At
the start of training, the agent tends to blindly accelerate or decelerate.
With more training steps, the agent gradually learns to optimize the speed and
comfort while mitigating the route miss rate (failure rate).

Figure 10: Speed, jerk and route-following miss (failure) rate evaluated at a
fixed collection of random seeds, as a function of training iteration. The
results are normalized with respect to the IDM baseline.

As in the loop network, the other RL baselines continue to have poor safety
performance relative to SECRM-2D, especially in emergency braking. In all
experiments, given accurate estimates of reaction times and braking rates of
the surrounding vehicles, SECRM-2D is able to avoid crashes altogether.

Table III displays the results for the bypassing scenario. This scenario is
different from scenarios seen by the agent during training. SECRM-2D
generalizes well. Overall, as the headway $H$ decreases, making the traffic
more crowded, travel efficiency decreases as well. A very narrow $H$ makes
lead vehicles hard to bypass, but a very high headway will make lead vehicles
easy to bypass. Compared with rule-based controllers, such as IDM+MOBIL or
Gipps+Greedy, our controller can achieve higher average speed (better
efficiency) with lower jerk (better comfort). Compared with the RL-based
controllers, SECRM-2D achieves better results in safety, efficiency, comfort
and route-following.

Table V shows that SECRM-2D succeeds in having low average jerk and zero crash
rate in the emergency-braking scenario.

The merging scenario results in Table V are obtained _without retraining the
controller specifically for merging_. Thus, the controller trained on the off-
ramp exit scenario is able to successfully generalize to a different route-
following scenario (merging from an on-ramp). This highlights an advantage
that arises from the generality of our route-following formulation.

Table VI shows how efficiency and comfort depend on the reaction times of the
controlled and human-driver vehicles (given by $r_{E}$ and $r_{F}$,
respectively) in the challenging $H=5$ bypassing scenario. Lower reaction
times enable higher efficiency control, as the lane-change constraints become
less restrictive.

##  IX Conclusion

In conclusion, we address the critical challenge of safety in RL-based
autonomous driving controllers. While existing RL-based controllers offer
great potential in optimizing efficiency, stability, and comfort, they often
lack safety guarantees. To overcome this limitation, we extend our previous
work SECRM [4] to SECRM-2D (the Safe, Efficient and Comfortable RL-based
driving Model with Lane-Changing), incorporating hard analytic safety
constraints on acceleration and lane-change actions. Through extensive
simulator experiments, we demonstrate that several representative previously-
published RL AV controllers are prone to crashes, while our SECRM-2D
controller successfully avoids crashes in both training and testing.
Additionally, SECRM-2D has excellent performance in efficiency, comfort,
safety, and route-following relative to a selection of strong learned and non-
learned baselines. Finally, we achieve a good understanding of the long-term
equilibrium of a platoon of SECRM-2D vehicles moving at constant speed,
including obtaining a precise expression for the inter-vehicle gaps in the
platoon in terms of its speed and the vehicle configuration.

## References

  * [1] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, “Human-level control through deep reinforcement learning,” _Nature_ , vol. 518, no. 7540, pp. 529–533, 2015. [Online]. Available: https://doi.org/10.1038/nature14236
  * [2] N. Lazic, C. Boutilier, T. Lu, E. Wong, B. Roy, M. Ryu, and G. Imwalle, “Data center cooling using model-predictive control,” _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [3] G. Li, Y. Yang, S. Li, X. Qu, N. Lyu, and S. E. Li, “Decision making of autonomous vehicles in lane change scenarios: Deep reinforcement learning approaches with risk awareness,” _Transportation Research Part C: Emerging Technologies_ , vol. 134, p. 103452, 2022.
  * [4] O. Elsamadisy, T. Shi, I. Smirnov, and B. Abdulhai, “Safe, efficient and comfortable reinforcement-learning-based car-following for AVs with analytic safety guarantee and dynamic target speed,” _Transportation Research Record_ , vol. 2678(1), pp. 643–661, 2024.
  * [5] S. Zhang, H. Peng, S. Nageshrao, and E. Tseng, “Discretionary lane change decision making using reinforcement learning with model-based exploration,” in _2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA)_. IEEE, 2019, pp. 844–850.
  * [6] C. Xi, T. Shi, Y. Wu, and L. Sun, “Efficient motion planning for automated lane change based on imitation learning and mixed-integer optimization,” in _2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2020, pp. 1–6.
  * [7] T. Pan, W. H. Lam, A. Sumalee, and R. Zhong, “Modeling the impacts of mandatory and discretionary lane-changing maneuvers,” _Transportation research part C: emerging technologies_ , vol. 68, pp. 403–424, 2016.
  * [8] T. Shi, P. Wang, X. Cheng, C.-Y. Chan, and D. Huang, “Driving decision and control for automated lane change behavior based on deep reinforcement learning,” in _2019 IEEE intelligent transportation systems conference (ITSC)_. IEEE, 2019, pp. 2895–2900.
  * [9] C.-J. Hoel, K. Driggs-Campbell, K. Wolff, L. Laine, and M. J. Kochenderfer, “Combining planning and deep reinforcement learning in tactical decision making for autonomous driving,” _IEEE transactions on intelligent vehicles_ , vol. 5, no. 2, pp. 294–305, 2019.
  * [10] Z. Cao, D. Yang, S. Xu, H. Peng, B. Li, S. Feng, and D. Zhao, “Highway exiting planner for automated vehicles using reinforcement learning,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 22, no. 2, pp. 990–1000, 2020.
  * [11] F. Ye, X. Cheng, P. Wang, C.-Y. Chan, and J. Zhang, “Automated lane change strategy using proximal policy optimization-based deep reinforcement learning,” in _2020 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2020, pp. 1746–1752.
  * [12] S. Udatha, Y. Lyu, and J. Dolan, “Reinforcement learning with probabilistically safe control barrier functions for ramp merging,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 5625–5630.
  * [13] B. Vanholme, D. Gruyer, B. Lusetti, S. Glaser, and S. Mammar, “Highly automated driving on highways based on legal safety,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 14, no. 1, pp. 333–347, 2013.
  * [14] M. Zhu, Y. Wang, Z. Pu, J. Hu, X. Wang, and R. Ke, “Safe, efficient, and comfortable velocity control based on reinforcement learning for autonomous driving,” _Transportation Research Part C: Emerging Technologies_ , vol. 117, p. 102662, 2020.
  * [15] Y.-T. Yen, J.-J. Chou, C.-S. Shih, C.-W. Chen, and P.-K. Tsung, “Proactive car-following using deep-reinforcement learning,” in _2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2020, pp. 1–6.
  * [16] T. Shi, Y. Ai, O. ElSamadisy, and B. Abdulhai, “Bilateral deep reinforcement learning approach for better-than-human car-following,” in _2022 IEEE 25th International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2022, pp. 3986–3992.
  * [17] P. Gipps, “A behavioural car-following model for computer simulation,” _Transportation Research Part B: Methodological_ , vol. 15, no. 2, pp. 105–111, 1981.
  * [18] W. Zhao, T. He, R. Chen, T. Wei, and C. Liu, “State-wise safe reinforcement learning: A survey,” _arXiv preprint arXiv:2302.03122_ , 2023.
  * [19] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra, “Continuous control with deep reinforcement learning,” in _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , Y. Bengio and Y. LeCun, Eds., 2016. [Online]. Available: http://arxiv.org/abs/1509.02971
  * [20] P. Á. López, M. Behrisch, L. Bieker-Walz, J. Erdmann, Y.-P. Flötteröd, R. Hilbrich, L. Lücken, J. Rummel, P. Wagner, and E. WieBner, “Microscopic traffic simulation using SUMO,” _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_ , pp. 2575–2582, 2018.
  * [21] O. Galor, _Discrete Dynamical Systems_. Springer-Verlag, 2007.
  * [22] J. Guckenheimer and P. Holmes, _Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields_ , ser. Applied Mathematical Sciences. Springer-Verlag, 1983, vol. 42.
  * [23] Treiber, Hennecke, and Helbing, “Congested traffic states in empirical observations and microscopic simulations,” _Physical Review E: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics_ , vol. 62 2 Pt A, pp. 1805–24, 2000.
  * [24] A. Kesting, M. Treiber, and D. Helbing, “General lane-changing model MOBIL for car-following models,” _Transportation Research Record_ , vol. 1999(1), pp. 86–94, 2007.
  * [25] J. Erdmann, “SUMO’s lane-changing model,” in _Modeling Mobility with Open Data: 2nd SUMO Conference 2014 Berlin, Germany, May 15-16, 2014_. Springer, 2015, pp. 105–123.
  * [26] T. Shi, “SECRM-2D demo,” 2023, https://youtu.be/J5UyJXGAGX0, Last accessed May 20, 2023.

##  Appendix A Asymptotic Stability of the Follower With Constant-Speed Leader
System

Here, we would like to verify that the eigenvalues of the Jacobian matrix at
the equilibrium point $(g^{*},v^{*})$

$\lambda_{\pm}=\frac{w\pm\sqrt{w^{2}-2wdr-d^{2}r^{2}}}{2w+dr}$

satisfy $\left|\lambda_{\pm}\right|<1$ whenever $w>0$. We consider two cases
based on whether the eigenvalues are real or complex.

##### Case $w^{2}-2wdr-d^{2}r^{2}\geq 0$

In this case, the eigenvalues are real. First, we show that $\lambda_{+}<1$.
This follows from

$\displaystyle\frac{w+\sqrt{w^{2}-2wdr-d^{2}r^{2}}}{2w+dr}$
$\displaystyle<\frac{w+\sqrt{w^{2}-2wdr+d^{2}r^{2}}}{2w+dr}$
$\displaystyle=\frac{w+(w-dr)}{2w+dr}$
$\displaystyle=\frac{2w-dr}{2w+dr}<1,\quad\mbox{as }dr>0$

Now, we show that $\lambda_{-}>-1$. Since $2w+dr>0$, we have $2(2w+dr)^{2}>0$
also. Therefore,

$2(2w+dr)^{2}+(w^{2}-2wdr-d^{2}r)>w^{2}-2wdr-d^{2}r$

Collecting the terms on the left side, we have
$(3w+dr)^{2}>w^{2}-2wdr-d^{2}r$. Taking square roots of both sides and
rearranging,

$w-\sqrt{w^{2}-2wdr-d^{2}r}>-2w-dr$

Dividing both sides by $2w+dr$ shows that $\lambda_{i}>-1$. Then, the chain of
inequalities

$-1<\lambda_{i}<\lambda_{+}<1$

shows that $\left|\lambda_{\pm}\right|<1$, as desired.

##### Case $w^{2}-2wdr-d^{2}r^{2}<0$

In this case, the eigenvalues are complex conjugates. It is sufficient to
check that either of the eigenvalues have norm $<1$, as complex conjugation is
norm-preserving.

The squared norm of $\lambda_{+}$ is

$\frac{w^{2}+(d^{2}r^{2}+2wdr-w^{2})}{(2w+dr)^{2}}=\frac{d^{2}r^{2}+2wdr}{(2w+dr)^{2}}$

To show that $\left|\lambda_{+}\right|^{2}<1$ it is equivalent to check that
$d^{2}r^{2}+2wdr<(2w+dr)^{2}$. Expanding the square and rearranging, the
latter is equivalent to $0<4w^{2}+2wdr$, which is true whenever $w>0$. It
follows that $\left|\lambda_{\pm}\right|<1$, as desired.

|  Tianyu Shi received the B.Sc. degree in Vehicle Engineering from Beijing
Institute of Technology, Beijing, China, in 2019. He received master’s degree
from McGill University, Montreal, Canada, in 2021. He is currently pursuing
Ph.D. degree in Transportation Engineering, University of Toronto, Toronto,
Canada. His current research centers on reinforcement learning and intelligent
transportation systems.
---|---
|  Ilia Smirnov received the B.Sc. degree in mathematics and physics from
University of Toronto, Canada, in 2010, and the M.Sc. and Ph.D. degrees in
pure mathematics from Queen’s University, Canada, in 2012 and 2020. He is a
research associate in Civil Engineering at the University of Toronto. His
research interests include artificial intelligence and optimization in
intelligent transportation systems, and algebraic geometry.
---|---
|  Omar ElSamadisy received both his B.Sc. and M.Sc. from the Arab Academy for
Science and Technology, Egypt, in 2014 and 2017, respectively. He is currently
a Ph.D. candidate at the University of Toronto, Canada, focusing on
reinforcement learning applications in intelligent transportation systems. His
research aims to optimize urban freeway operations through the integration of
artificial intelligence and transportation engineering principles.
---|---
|  Baher Abdulhai received the Ph.D. degree in engineering from the University
of California, Irvine, CA, USA, in 1996. He is a Professor in Civil
Engineering at the University of Toronto, ON, Canada. He has 35 years of
experience in transportation systems engineering and Intelligent
Transportation Systems (ITS). He is the founder and Director of the Toronto
Intelligent Transportation System Center, and the founder and co-Director of
the i-City Center for Automated and Transformative Transportation Systems
(iCity-CATTS). He received several awards including IEEE Outstanding Service
Award, Teaching Excellence award, and research awards from Canada Foundation
for Innovation, Ontario Research Fund, and Ontario Innovation Trust. He served
on the Board of Directors of the Government of Ontario (GO) Transit Authority
from 2004 to 2006. He served as a Canada Research Chair (CRC) in ITS from 2005
to 2010. His research team won international awards including the
International Transportation Forum innovation award in 2010 (Hossam
Abdelgawad), IEEE ITS 2013 (Samah El-Tantawy) and INFORMS 2013 (Samah El-
Tantawy). In 2015 he has been inducted as a Fellow of the Engineering
Institute of Canada (EIC). In 2018, he won the prestigious CSCE Sandford
Fleming (Career Achievement) Award for his contribution to transportation in
Canada. He has been elected Fellow of the Canadian Academy of Engineering in
2020. In 2021, he won the Ontario Professional Engineers Awards (OPEA)
Engineering Medal for career Engineering Excellence.
---|---


where the term $\tilde{u}_{t}$ can be bounded by using the smoothness of
${\\{\ell_{j}\\}_{j=1}^{J}}$ (Assumption (A5)) so as to yield

$\displaystyle\tilde{u}_{t}$
$\displaystyle:=2\alpha_{t}\sum_{j=1}^{J}\left({\lambda_{j,t}-{\tilde{\lambda}}_{j}}\right)\left({\ell_{j}\left({{\mathbf{w}}_{t+1};\psi_{t}}\right)-\ell_{j}\left({{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right);\psi_{t}}\right)}\right)$
(150) $\displaystyle\leq
2\alpha_{t}\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|\sqrt{\sum_{j=1}^{J}\left({\ell_{j}\left({{\mathbf{w}}_{t+1};\psi_{t}}\right)-\ell_{j}\left({{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right);\psi_{t}}\right)}\right)^{2}}$
(151) $\displaystyle\leq
2\alpha_{t}\sqrt{J}\sqrt{C_{\ell}}\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|\left\|{{\mathbf{w}}_{t+1}-{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right)}\right\|$
(152)
$\displaystyle\leq\beta_{t}\left\|{{\mathbf{w}}_{t+1}-{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right)}\right\|^{2}+\frac{\alpha_{t}^{2}JC_{\ell}}{\beta_{t}}\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|^{2}.$
(153)

Here, (151) follows from the Cauchy-Schwartz inequality while (153) follows
from the Peter-Paul inequality. Taking conditional expectation given
${\mathcal{F}}_{t}$ in (149), and recalling that
${\mathbb{E}}\left[{{\ell_{j}\left({{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right):\psi_{t}}\right)}\,|\,{\mathcal{F}}_{t}}\right]=L_{j}({\mathbf{x}}_{t})$,
we obtain

$\displaystyle{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t+1}-{\tilde{\bm{\lambda}}}}\right\|^{2}}\,|\,{\mathcal{F}}_{t}}\right]\hskip
14.22636pt\leq\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|^{2}+2\alpha_{t}\sum_{j=1}^{J}\left({\lambda_{j,t}-{\tilde{\lambda}}_{j}}\right)\left({L_{j}({\mathbf{x}}_{t})-\alpha_{t}\delta_{t}\lambda_{j,t}+\theta}\right)$
$\displaystyle\hskip
28.45274pt+\alpha_{t}^{2}\sum_{j=1}^{J}{\mathbb{E}}\left[{{\left({\ell_{j}\left({{\mathbf{w}}_{t+1}:\psi_{t}}\right)-\alpha_{t}\delta_{t}\lambda_{j,t}+\theta}\right)^{2}}\,|\,{\mathcal{F}}_{t}}\right]+{\mathbb{E}}\left[{{\tilde{u}_{t}\,|\,{\mathcal{F}}_{t}}}\right]$
(154) $\displaystyle\hskip
14.22636pt=\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|^{2}\left({1+\frac{\alpha_{t}^{2}JC_{\ell}}{\beta_{t}}}\right)+2\alpha_{t}\left({\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right)^{\mathsf{T}}\nabla_{\bm{\lambda}}{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},\bm{\lambda}_{t},\alpha_{t},\delta_{t}}\right)$
$\displaystyle\hskip
28.45274pt+\alpha_{t}^{2}\sum_{j=1}^{J}{\mathbb{E}}\left[{{\left({\ell_{j}\left({{\mathbf{w}}_{t+1}:\psi_{t}}\right)-\alpha_{t}\delta_{t}\lambda_{j,t}+\theta}\right)^{2}}\,|\,{\mathcal{F}}_{t}}\right]+\beta_{t}{\mathbb{E}}\left[{{\left\|{{\mathbf{w}}_{t+1}-{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right)}\right\|^{2}}\,|\,{\mathcal{F}}_{t}}\right]$
(155)

where we have substituted (153). Since
${{\mathcal{L}}^{\theta}}\left({{\mathbf{x}},\bm{\lambda},\alpha,\delta}\right)$
is $\alpha_{t}\delta_{t}$ strongly-concave in $\bm{\lambda}$, we have that

$\displaystyle{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t+1}-{\tilde{\bm{\lambda}}}}\right\|^{2}}\,|\,{\mathcal{F}}_{t}}\right]\leq\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|^{2}\left({1+\frac{\alpha_{t}^{2}JC_{\ell}}{\beta_{t}}-\alpha_{t}^{2}\delta_{t}}\right)+2\alpha_{t}\left({{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},\bm{\lambda}_{t},\alpha_{t},\delta_{t}}\right)-{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},{\tilde{\bm{\lambda}}},\alpha_{t},\delta_{t}}\right)}\right)$
$\displaystyle\hskip
28.45274pt+\alpha_{t}^{2}\sum_{j=1}^{J}{\mathbb{E}}\left[{{\left({\ell_{j}\left({{\mathbf{w}}_{t+1}:\psi_{t}}\right)-\alpha_{t}\delta_{t}\lambda_{j,t}+\theta}\right)^{2}}\,|\,{\mathcal{F}}_{t}}\right]+\beta_{t}{\mathbb{E}}\left[{{\left\|{{\mathbf{w}}_{t+1}-{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right)}\right\|^{2}}\,|\,{\mathcal{F}}_{t}}\right]$
(156) $\displaystyle\hskip
14.22636pt\leq\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|^{2}\left({1+\frac{\alpha_{t}^{2}JC_{\ell}}{\beta_{t}}-\alpha_{t}^{2}\delta_{t}}\right)+2\alpha_{t}\left({{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},\bm{\lambda}_{t},\alpha_{t},\delta_{t}}\right)-{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},{\tilde{\bm{\lambda}}},\alpha_{t},\delta_{t}}\right)}\right)$
$\displaystyle\hskip
28.45274pt+\left({4J\alpha_{t}^{2}C_{\ell}+\beta_{t}}\right){\mathbb{E}}\left[{{\left\|{{\mathbf{w}}_{t+1}-{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right)}\right\|^{2}}\,|\,{\mathcal{F}}_{t}}\right]+4\alpha_{t}^{2}JB_{\ell}+4\alpha_{t}^{2}J\theta^{2}+4\alpha_{t}^{4}\delta_{t}^{2}\left\|{\bm{\lambda}_{t}}\right\|^{2},$
(157)

where the last inequality is followed by (25). If the step sizes are chosen as
$\alpha_{t}^{2}\leq\beta_{t}$, then $\beta_{t}$ is more dominating term than
the term with $\alpha_{t}^{2}$, and therefore we can write
$4J\alpha_{t}^{2}C_{\ell}{\mathbb{E}}\left[{{\left\|{{\mathbf{w}}_{t+1}-{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right)}\right\|^{2}}\,|\,{\mathcal{F}}_{t}}\right]\leq
4J\beta_{t}C_{\ell}{\mathbb{E}}\left[{{\left\|{{\mathbf{w}}_{t+1}-{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right)}\right\|^{2}}\,|\,{\mathcal{F}}_{t}}\right]$
in (157).

##  Appendix F Proof of Lemma 7

Let
${\mathcal{J}}_{t}:={\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|^{2}}}\right]+C{\mathbb{E}}\left[{{\left\|{{\mathbf{w}}_{t+1}-{\bar{{\mathbf{h}}}}\left({{\mathbf{x}}_{t}}\right)}\right\|^{2}}}\right]$,
where $C:=1+4JC_{\ell}$. From the result in (29) of Lemma 1, we know

$\displaystyle{\mathcal{J}}_{t}\leq{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t}}\right\|^{2}}}\right]+\left\|{{\tilde{\bm{\lambda}}}}\right\|^{2}+D+2JC_{h}C_{\ell}(C_{g}+C_{h})\sum_{t=1}^{T}\alpha_{t}^{2}\beta_{t+1}^{-1}{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t}}\right\|^{2}}}\right],$
(158)

where recall that $D=D_{x}+D_{y}+D_{z}$. Using statement of Lemma 6 and (27)
from Lemma 1, we can write

$\displaystyle{\mathcal{J}}_{t+1}$
$\displaystyle\leq{\mathcal{J}}_{t}+\frac{\alpha_{t}^{2}JC_{\ell}}{\beta_{t}}{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|^{2}}}\right]+2\alpha_{t}{\mathbb{E}}\left[{{{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},\bm{\lambda}_{t},\alpha_{t},\delta_{t}}\right)-{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},{\tilde{\bm{\lambda}}},\alpha_{t},\delta_{t}}\right)}}\right]$
$\displaystyle\hskip
14.22636pt+4\alpha_{t}^{4}\delta_{t}^{2}{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t}}\right\|^{2}}}\right]+4J(B_{\ell}+\theta^{2})\alpha_{t}^{2}+2C\beta_{t}^{-1}C_{h}{\mathbb{E}}\left[{{\left\|{{\mathbf{x}}_{t}-{\mathbf{x}}_{t-1}}\right\|^{2}}}\right]+4CV_{h}\beta_{t}^{2}$
(159)
$\displaystyle\leq{\mathcal{J}}_{t}+\frac{\alpha_{t}^{2}JC_{\ell}}{\beta_{t}}{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|^{2}}}\right]+2\alpha_{t}{\mathbb{E}}\left[{{{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},\bm{\lambda}_{t},\alpha_{t},\delta_{t}}\right)-{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},{\tilde{\bm{\lambda}}},\alpha_{t},\delta_{t}}\right)}}\right]+4\alpha_{t}^{4}\delta_{t}^{2}{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t}}\right\|^{2}}}\right]$
$\displaystyle\hskip
14.22636pt+4J(B_{\ell}+\theta^{2})\alpha_{t}^{2}+4C\left({\alpha_{t-1}^{2}\beta_{t}^{-1}C_{h}\left({C_{g}C_{f}+JC_{h}C_{\ell}{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t-1}}\right\|^{2}}}\right]}\right)+V_{h}\beta_{t}^{2}}\right),$
(160)

where the last inequality follows from (24). Rearranging the terms and using
the inequality
$\left\|{\bm{\lambda}_{t}-{\tilde{\bm{\lambda}}}}\right\|^{2}\leq
2\left\|{\bm{\lambda}_{t}}\right\|^{2}+2\left\|{{\tilde{\bm{\lambda}}}}\right\|^{2}$,
we obtain

$\displaystyle 2$
$\displaystyle{\mathbb{E}}\left[{{{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},{\tilde{\bm{\lambda}}},\alpha_{t},\delta_{t}}\right)-{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},\bm{\lambda}_{t},\alpha_{t},\delta_{t}}\right)}}\right]$
$\displaystyle\leq\frac{1}{\alpha_{t}}\left({{\mathcal{J}}_{t}-{\mathcal{J}}_{t+1}}\right)+4J(B_{\ell}+\theta^{2})\alpha_{t}+4CC_{f}C_{g}C_{h}\frac{\alpha_{t-1}^{2}}{\alpha_{t}\beta_{t}}+4CV_{h}\frac{\beta_{t}^{2}}{\alpha_{t}}+2JC_{\ell}{\mathbb{E}}\left[{{\left\|{{\tilde{\bm{\lambda}}}}\right\|^{2}}}\right]\frac{\alpha_{t}}{\beta_{t}}$
$\displaystyle\hskip
14.22636pt+\left({4\alpha_{t}^{3}\delta_{t}^{2}+2JC_{\ell}\frac{\alpha_{t}}{\beta_{t}}}\right){\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t}}\right\|^{2}}}\right]+4JCC_{h}^{2}C_{\ell}\frac{\alpha_{t-1}^{2}}{\alpha_{t}\beta_{t}}{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t-1}}\right\|^{2}}}\right].$
(161)

Summing over $t=1$ to $T$, we obtain

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle{\mathbb{E}}\left[{{{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},{\tilde{\bm{\lambda}}},\alpha_{t},\delta_{t}}\right)-{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},\bm{\lambda}_{t},\alpha_{t},\delta_{t}}\right)}}\right]$
$\displaystyle\leq\frac{{\mathcal{J}}_{1}}{2\alpha_{1}}+\frac{1}{2}\sum_{t=2}^{T}{\mathcal{J}}_{t}\left({\frac{1}{\alpha_{t}}-\frac{1}{\alpha_{t-1}}}\right)+\sum_{t=1}^{T}\left({4J(B_{\ell}+\theta^{2})\alpha_{t}+4CC_{f}C_{g}C_{h}\frac{\alpha_{t}^{2}}{\alpha_{t+1}\beta_{t+1}}+4CV_{h}\frac{\beta_{t}^{2}}{\alpha_{t}}}\right)$
$\displaystyle\hskip
14.22636pt+2JC_{\ell}{\mathbb{E}}\left[{{\left\|{{\tilde{\bm{\lambda}}}}\right\|^{2}}}\right]\sum_{t=1}^{T}\frac{\alpha_{t}}{\beta_{t}}+\sum_{t=1}^{T}\left({4\alpha_{t}^{3}\delta_{t}^{2}+2JC_{\ell}\frac{\alpha_{t}}{\beta_{t}}+4JCC_{h}^{2}C_{\ell}\frac{\alpha_{t}^{2}}{\alpha_{t+1}\beta_{t+1}}}\right){\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t}}\right\|^{2}}}\right]$
(162)

By substituting the bound on $I_{t}$ in the above equation, we obtain

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle{\mathbb{E}}\left[{{{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},{\tilde{\bm{\lambda}}},\alpha_{t},\delta_{t}}\right)-{{\mathcal{L}}^{\theta}}\left({{\mathbf{x}}_{t},\bm{\lambda}_{t},\alpha_{t},\delta_{t}}\right)}}\right]$
$\displaystyle\leq\frac{D}{\alpha_{T}}+\sum_{t=1}^{T}\left({4J(B_{\ell}+\theta^{2})\alpha_{t}+4CC_{f}C_{g}C_{h}\frac{\alpha_{t}^{2}}{\alpha_{t+1}\beta_{t+1}}+4CV_{h}\frac{\beta_{t}^{2}}{\alpha_{t}}}\right)+\sum_{t=1}^{T}\Bigg{(}4\alpha_{t}^{3}\delta_{t}^{2}$
$\displaystyle\hskip
14.22636pt+2JC_{\ell}\frac{\alpha_{t}}{\beta_{t}}+4JCC_{h}^{2}C_{\ell}\frac{\alpha_{t}^{2}}{\alpha_{t+1}\beta_{t+1}}+JC_{h}C_{\ell}(C_{g}+C_{h})\frac{\alpha_{t}^{2}}{\alpha_{T}\beta_{t+1}}+\left({\frac{1}{\alpha_{t+1}}-\frac{1}{\alpha_{t}}}\right)\Bigg{)}{\mathbb{E}}\left[{{\left\|{\bm{\lambda}_{t}}\right\|^{2}}}\right]$
$\displaystyle\hskip
14.22636pt+\left({2JC_{\ell}\sum_{t=1}^{T}\frac{\alpha_{t}}{\beta_{t}}+\frac{1}{\alpha_{T}}}\right){\mathbb{E}}\left[{{\left\|{{\tilde{\bm{\lambda}}}}\right\|^{2}}}\right].$
(163)

## References

  * (1) M. Wang, E. X. Fang, and H. Liu, “Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions,” _Mathematical Programming_ , vol. 161, no. 1-2, pp. 419–449, 2017.
  * (2) M. Wang, J. Liu, and E. X. Fang, “Accelerating stochastic composition optimization,” _J. Mach. Learn. Res._ , vol. 18, no. 1, pp. 3721–3743, 2017\.
  * (3) M. Wang and J. Liu, “A stochastic compositional gradient method using markov samples,” in _Proc. IEEE WSC_ , Dec. 2016, pp. 702–713.
  * (4) S. Ghadimi, A. Ruszczynski, and M. Wang, “A single timescale stochastic approximation method for nested stochastic optimization,” _SIAM Journal on Optimization_ , vol. 30, no. 1, pp. 960–979, 2020.
  * (5) S. T. Thomdapu and K. Rajawat, “Optimal design of queuing systems via compositional stochastic programming,” _IEEE Trans. Commun._ , vol. 67, no. 12, pp. 8460–8474, 2019.
  * (6) X. Wang and G. B. Giannakis, “Resource allocation for wireless multiuser OFDM networks,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 7, pp. 4359–4372, 2011.
  * (7) A. Ribeiro, “Ergodic stochastic optimization algorithms for wireless communication and networking,” _IEEE Trans. Signal Process._ , vol. 58, no. 12, pp. 6369–6386, 2010.
  * (8) A. Nedić and A. Ozdaglar, “Subgradient methods for saddle-point problems,” _J. of Opt. Theory and Applications._ , vol. 142, no. 1, pp. 205–228, 2009.
  * (9) A. Koppel, F. Y. Jakubiec, and A. Ribeiro, “A saddle point algorithm for networked online convex optimization,” _IEEE Trans. Signal Process._ , vol. 63, no. 19, pp. 5149–5164, 2015.
  * (10) A. S. Bedi, A. Koppel, and K. Rajawat, “Beyond consensus and synchrony in decentralized online optimization using saddle point method,” in _Proc. IEEE Asilomar_ , 2017, pp. 293–297.
  * (11) H. Yu, M. Neely, and X. Wei, “Online convex optimization with stochastic constraints,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 1428–1438.
  * (12) A. S. Bedi, A. Koppel, and K. Rajawat, “Asynchronous saddle point algorithm for stochastic optimization in heterogeneous networks,” _IEEE Trans. Signal Process._ , vol. 67, no. 7, pp. 1742–1757, 2019.
  * (13) A. N. Madavan and S. Bose, “Subgradient methods for risk-sensitive optimization,” _arXiv preprint arXiv:1908.01086_ , 2019.
  * (14) Z. Akhtar, A. S. Bedi, and K. Rajawat, “Conservative stochastic optimization with expectation constraints,” _arXiv preprint arXiv:2008.05758_ , 2020.
  * (15) A. Benveniste, M. Métivier, and P. Priouret, _Adaptive algorithms and stochastic approximations_. Springer Science & Business Media, 2012, vol. 22.
  * (16) D. P. Bertsekas and J. N. Tsitsiklis, _Parallel and distributed computation: numerical methods_. Prentice hall Englewood Cliffs, NJ, 1989, vol. 23.
  * (17) V. S. Borkar, _Stochastic approximation: a dynamical systems viewpoint_. Springer, 2009, vol. 48.
  * (18) D. Dentcheva, S. Penev, and A. Ruszczyński, “Statistical estimation of composite risk functionals and risk optimization problems,” _Springer Journal on Annals of the Institute of Statistical Mathematics_ , vol. 69, no. 4, pp. 737–760, 2017.
  * (19) X. Lian, M. Wang, and J. Liu, “Finite-sum composition optimization via variance reduced gradient descent,” in _Proc. Artificial Intel. and Stats._ , Apr. 2017, pp. 1159–1167.
  * (20) A. Koppel, A. S. Bedi, and K. Rajawat, “Controlling the bias-variance tradeoff via coherent risk for robust learning with kernels,” in _Proc. IEEE ACC_ , May, 2019, pp. 3519–3525.
  * (21) B. Dai, N. He, Y. Pan, B. Boots, and L. Song, “Learning from conditional distributions via dual embeddings,” in _Artificial Intelligence and Statistics_ , 2017, pp. 1458–1467.
  * (22) Y. Hu, S. Zhang, X. Chen, and N. He, “Biased stochastic gradient descent for conditional stochastic optimization,” _arXiv preprint arXiv:2002.10790_ , 2020.
  * (23) A. S. Bedi and K. Rajawat, “Asynchronous incremental stochastic dual descent algorithm for network resource allocation,” _IEEE Trans. Signal Process._ , vol. 66, no. 9, pp. 2229–2244, 2018.
  * (24) T. Chen, A. Mokhtari, X. Wang, A. Ribeiro, and G. B. Giannakis, “Stochastic averaging for constrained optimization with application to online resource allocation,” _IEEE Trans. Signal Process._ , vol. 65, no. 12, pp. 3078–3093, 2017.
  * (25) X. Wang, X. Chen, T. Chen, L. Huang, and G. B. Giannakis, “Two-scale stochastic control for integrated multipoint communication systems with renewables,” _IEEE Trans. Smart Grid_ , vol. 9, no. 3, pp. 1822–1834, 2016\.
  * (26) T. Chen, S. Barbarossa, X. Wang, G. B. Giannakis, and Z.-L. Zhang, “Learning and management for internet of things: Accounting for adaptivity and scalability,” _Proc. of the IEEE_ , vol. 107, no. 4, pp. 778–796, 2019.
  * (27) A. Koppel, B. M. Sadler, and A. Ribeiro, “Proximity without consensus in online multiagent optimization,” _IEEE Trans. Signal Process._ , vol. 65, no. 12, pp. 3062–3077, 2017.
  * (28) M. B. Zafar, I. Valera, M. Gomez Rodriguez, and K. P. Gummadi, “Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment,” in _Proc. intl. conf. on world wide web_ , 2017, pp. 1171–1180.
  * (29) G. Goh, A. Cotter, M. Gupta, and M. P. Friedlander, “Satisfying real-world goals with dataset constraints,” in _Advances in Neural Information Processing Systems_ , 2016, pp. 2415–2423.
  * (30) T. Kamishima, S. Akaho, and J. Sakuma, “Fairness-aware learning through regularization approach,” in _Proc. IEEE Intl. Conf. on Data Mining Workshops_ , 2011, pp. 643–650.
  * (31) A. K. Menon and R. C. Williamson, “The cost of fairness in binary classification,” in _Proc. Conf. on Fairness, Accountability and Transparency_ , 2018, pp. 107–118.
  * (32) M. Olfat and A. Aswani, “Spectral algorithms for computing fair support vector machines,” in _Proc. Intl. Conf. on Artificial Intel. Stat._ , 2018, pp. 1933–1942.
  * (33) B. Woodworth, S. Gunasekar, M. I. Ohannessian, and N. Srebro, “Learning non-discriminatory predictors,” in _Proc. Conf. on Learning Theory_ , 2017, pp. 1920–1953.
  * (34) M. B. Zafar, I. Valera, M. Gomez-Rodriguez, and K. P. Gummadi, “Fairness constraints: A flexible approach for fair classification.” _J. Mach. Learn. Res._ , vol. 20, no. 75, pp. 1–42, 2019.
  * (35) Y. Wu, L. Zhang, and X. Wu, “On convexity and bounds of fairness-aware classification,” in _Proc. The World Wide Web Conference_ , 2019, pp. 3356–3362.
  * (36) D. Pedreschi, S. Ruggieri, and F. Turini, “A study of top-k measures for discrimination discovery,” in _Proc. ACM Symposium on Applied Computing_ , 2012, pp. 126–131.
  * (37) “Adult income,” 1996. [Online]. Available: https://archive.ics.uci.edu/ml/datasets/adult
  * (38) D. Dua and C. Graff, “UCI machine learning repository,” 2017. [Online]. Available: http://archive.ics.uci.edu/ml
  * (39) J. Angwin, J. Larson, S. Mattu, and L. Kirchner, “Machine bias. propublica,” _propublica_ , 2016.
  * (40) J. Komiyama, A. Takeda, J. Honda, and H. Shimao, “Nonconvex optimization for regression with fairness constraints,” in _International conference on machine learning_ , 2018, pp. 2737–2746.
  * (41) R. Berk, H. Heidari, S. Jabbari, M. Joseph, M. Kearns, J. Morgenstern, S. Neel, and A. Roth, “A convex framework for fair regression,” _arXiv preprint arXiv:1706.02409_ , 2017.
  * (42) P. Ravikumar, J. Lafferty, H. Liu, and L. Wasserman, “Sparse additive models,” _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , vol. 71, no. 5, pp. 1009–1030, 2009.
  * (43) A. Zink and S. Rose, “Fair regression for health care spending,” _Biometrics_ , 2019.