[1]organization=Department of Civil and Environmental Engineering, Carnegie
Mellon University, city=Pittsburgh, country=USA [2]organization=Heinz College,
Carnegie Mellon University, city=Pittsburgh, country=USA

# Real-time system optimal traffic routing under uncertainties – Can physics
models boost reinforcement learning?

Zemian Ke  Qiling Zou  Jiachao Liu  Sean Qian

###### Abstract

System optimal traffic routing can mitigate congestion by assigning routes for
a portion of vehicles so that the total travel time of all vehicles in the
transportation system can be reduced. However, achieving real-time optimal
routing poses challenges due to uncertain demands and unknown system dynamics,
particularly in expansive transportation networks. While physics model-based
methods are sensitive to uncertainties and model mismatches, model-free
reinforcement learning struggles with learning inefficiencies and
interpretability issues. Our paper presents TransRL, a novel algorithm that
integrates reinforcement learning with physics models for enhanced
performance, reliability, and interpretability. TransRL begins by establishing
a deterministic policy grounded in physics models, from which it learns from
and is guided by a differentiable and stochastic teacher policy. During
training, TransRL aims to maximize cumulative rewards while minimizing the
Kullback–Leibler (KL) divergence between the current policy and the teacher
policy. This approach enables TransRL to simultaneously leverage interactions
with the environment and insights from physics models. We conduct experiments
on three transportation networks with up to hundreds of links. The results
demonstrate TransRL’s superiority over traffic model-based methods for being
adaptive and learning from the actual network data. By leveraging the
information from physics models, TransRL consistently outperforms state-of-
the-art reinforcement learning algorithms such as proximal policy optimization
(PPO) and soft actor-critic (SAC). Moreover, TransRL’s actions exhibit higher
reliability and interpretability compared to baseline reinforcement learning
approaches like PPO and SAC.

##  1 Introduction

Traffic congestion in urban areas is one of the plagues of citizen’s everyday
life and it can cost huge economic loss [23]. According to a report from
Federal Highway Administration
111https://ops.fhwa.dot.gov/aboutus/opstory.htm(FHWA), “roughly half of the
congestion experienced by Americans happens virtually every day”. This type of
congestion is generated by unbalanced temporal and spatial distribution of
traffic activities. Recent studies [10, 26] have shown that congestion can be
significantly mitigated by optimally guiding route choices of a small portion
of travelers. The system optimal routing aims to minimize the total system
cost by assigning routes for some travelers. There are many ways to
practically implement and guide traffic routing. For instance, congestion toll
[62, 8] changes users’ routing choice by changing their perceived cost.
Variable traffic signs (VMS) provide real-time traffic information using road-
side signals like LED signs [15, 16, 5, 22] to affects users’ routing choice.
Route guidance and driver information systems (RGDIS) [2] directly provide
route recommendations to users using in-vehicle devices such as
infoentertainment system or cell phone applications. However, solving system-
level optimal routing in real-time for large networks remains a big challenge.

The optimal routing in real-time for large networks is challenging for three
reasons. First, demands are uncertain. Travel demands stem from human
activities that may have randomness, so it is almost unlikely to predict the
travel demands accurately. Demands essentially affect traffic conditions, and
the difference between the actual demands and the estimated demands can cause
nontrivial estimation errors in traffic conditions. For example, [46] showed
that congestion duration can change significantly with an incremental change
in demands. Therefore, it is important to consider the demand uncertainties.
From a theoretical perspective, [55] showed that using expected demands tends
to overestimate the network performance in traffic assignment evaluation. [13]
also stated it is important to consider demand uncertainty for the congestion
pricing problems. In this study, we explicitly include the demand uncertainty
and regard demands as random variables that cannot be predicted precisely in
advance.

Second, system dynamics may not be modeled perfectly. Though extensive traffic
flow models (e.g., the celebrated LWR model [31, 49], cell transmission models
[11, 12], and link queue model [24]) have been proposed to approximate the
system dynamics of transportation networks, no known flow model can precisely
replicate the flow in networks consisting of both roads and intersections.
Each model is associated with various assumptions and possible parameter
estimation errors. For example, conventional kinematic models ([31, 49, 11,
12, 24]) all assume a deterministic fundamental diagram to depict the relation
between density and flow for mathematical tractability, while [48] states this
relation can be better modeled by stochastic models. In addition, estimation
of the deterministic fundamental diagram parameters is not always accurate due
to the randomness of traffic flow and transient flow state transitions. In
this study, we acknowledge that the traffic flow model cannot be known
precisely. Rather, there is a model mismatch between the assumed/adopted
traffic models and the actual true system dynamics, and this mismatch is
unkonwn in advance.

Third, real-time system optimal traffic routing is challenging especially in
large networks due to complex interplay among traffic flow of various origins
and destinations. [44] proposed a stochastic optimal real-time routing method
for a two-route network. By abstracting a general commuting network into a
two-route network, the analytical solution can be derived and approximated
using dynamic programming. However, deriving the analytical solution of
optimal traffic routing (i.e. path flow) for a large network is almost
infeasible because the complexity of the problem and the dimension of decision
variables increase exponentially as the network size. To that end, machine
learning methods, like reinforcement learning, could be inefficient and even
infeasible. The state space and action space increase exponentially as the
network size increases, so finding an optimal policy from the exploded search
space without any prior knowledge is inefficient and sometimes even
infeasible. To our best knowledge, though [29] leveraged reinforcement
learning to solve real-time optimal routing on networks with up to 41 links.
Real-time optimal routing has not been solved by reinforcement learning on
networks with more than hundreds of links. This study experiments on three
networks with 2 links, 18 links, and 621 links, respectively.

Current methods for real-time optimal routing or general traffic control can
be categorized into heuristic methods, model-based methods, and reinforcement
learning-based methods. Heuristic methods use rule-of-thumb or feedback
control to correct control errors to maintain desired system states. [25]
formulated the real-time routing problem as a feedback control problem, and a
feedback linearization technique is used to achieve a user equilibrium state.
[43] adopted a fuzzy control approach to determine real-time routing
strategies to improve the network performance. Heuristic methods are
interpretable and easy to implement, but they are reactive and only take
action when control errors arise. Therefore, their performance is almost
necessarily suboptimal.

Model-based methods typically first develop a traffic model or simulation to
simulate the system dynamics, and then solve the optimal solutions through
either heuristic algorithms (e.g., moving successive averages (MSA)) or
deriving analytical closed-form solutions. For example, [54] used
autoregressive integrated moving average (ARIMA) to predict demands, a binary
logit model to predict traveler choices, and CTM to predict traffic flows.
Based on these predictions, an optimization algorithm was adopted to set tolls
to affect routing choices to optimize the objective function. [53] proposed a
model predictive control method for dynamic pricing to reduce the total
traveler delay. Similar to [54], [53] used a logit choice model to predict
traveler choices and CTM to predict traffic flows. Model-based methods are
interpretable and can be proven to be optimal in theory. However, the
inevitable model mismatch between the models and the actual system dynamics
intrigues their performances in practice.

Reinforcement learning (RL) gained popularity in the traffic control domain
because it’s model-free and can learn optimal policies directly from data or
the environment. [41] considered a practical control scenario with multiple
origins and destinations, partially observed network states, and stochastic
demands. The problem was formulated as a partially observable Markov decision
process (POMDP) and solved using RL. The experiments in [41] showed RL
outperformed feedback control. [29] considered a scenario where route choices
of autonomous vehicles can be fully controlled to improve network efficiency,
and the policy was learned using reinforcement learning. The experiments on
simplified networks indicated the learned RL policy realized performances on
par with the system optimum. However, to our best knowledge, RL has not been
tested for optimal routing on large networks with more than hundreds of links.
With the well-known curse of dimensionality, whether RL can solve optimal
policies in large networks remains unknown.

In this study, the reliability and interpretability of the RL policies are the
focus for its realism in real-world traffic operation practice. Most RL
policies are not deterministic and the traffic environment is stochastic in
nature, and it is clear that the performances of RL policies in practice are
subject to variability. When implementing RL policies, one question out of
interest is how poor the performance of RL policies can possibly be in the
worst cases. In reality, traffic operation may not tolerate a poor performance
for just one day, unlike RL applications in other domains, e.g. robotics, that
may accept some time of online improvement through learning. In this work, we
propose Conditional Travel Time Reduction at Risk (CTTRaR) to measure the
reliability of a control method. CTTRaR compares the total travel time of the
worst cases with a control method and the total travel time of the no-control
scenarios. RL policies are regarded as reliable if the worst performance is
still better than the no-control scenarios. In addition, the interpretability
of the RL policies is a concern for practitioners. The objective of RL is to
maximize the cumulative rewards with no specific constraints for the output
actions. As a result, though RL leads to high cumulative rewards, the actions
of RL might fluctuate over time, which makes RL policies less interpretable.
Our general idea is to constrain the RL policies to not go too far from an
interpretable “teacher” policy. For example, system optimum routing under
traffic flow dynamics models can serve as a teacher policy. Those flow
dynamics models may not be precisely calibrated (e.g., in a simulation
environment) or the demand is stochastic, but its flow propagation mechanisms
and the analytical solution can help to guide and learn interpretable RL
policies.

Moreover, it is unclear when RL is superior to model-based methods and vice
versa. A model-based method is extensively compared with model-free RL methods
to shed light on the performance between model-based methods and learning-
based methods. The results indicate RLs outperform the model-based method when
the demand uncertainty is large or/and the model mismatch is significant, and
vice versa. When the network size is large, RLs sometimes struggle to find a
reasonable policy that works precisely for the unknown or unexplored system
states and dynamics, but model-based can perform well especially when the
model mismatch is insignificant. With the trade-off between the model-based
method and model-free RL, one interesting question is can we combine the
advantages of both types of methods?

We propose a general reinforcement learning framework that can couple
different types of well-established transportation methods (e.g., heuristics,
model-based, or machine learning-based) with RL. In this study, we focus on an
example of coupling the model-based method with RL. Our proposed reinforcement
learning framework differentiates from most previous reinforcement learning
algorithms including DDPG [50], PPO [50], and SAC [18] by leveraging
information from transportation methods, named Transportation-informed
Reinforcement Learning (TransRL). TransRL is able to learn from the
environment and the traffic model simultaneously. On one hand, even with a
model mismatch, the information from the models is not unuseful and can help
RL narrow down the search space. On the other hand, with the ability to learn
from the environment directly, RL is able to learn a better policy than the
model-based method by implicitly correcting the model mismatch between the
models and the actual system dynamics.

The contributions of this paper are summarized as follows.

  * 1.

We solve real-time system optimal routing in sizable transportation networks.
The model is based on a realistic setting where only a few links are observed
and a portion of vehicles can be influenced with their respective routing
guidance.

  * 2.

We relax the assumptions of known travel demands and accurate traffic models
in other RL models. Instead, travel demands are assumed to follow a time-
dependent Gaussian distribution with means of historical average demands.
Moreover, there are model mismatches between the offline trained accessible
traffic models and the online test (unknown and true) system dynamics, which
stem from lack of knowledge, model estimation errors, or unexpected incidents
in real world.

  * 3.

Model-free RLs are compared with a traffic model-based method under various
levels of model mismatches. This comparison provides insights into when a
traffic model-based method is superior and when RLs are preferable.

  * 4.

Ultimately, we proposed a novel RL framework TransRL that combines RL with
traffic models. With the ability to learn from the environment and traffic
models simultaneously, TransRL learns more efficiently than model-free RLs and
is more adaptive than the traffic model-based method. More importantly, the
actions of TransRL are more reliable and interpretable than model-free RLs.

  * 5.

Reliability and interpretability of TransRL are the focus. In order to use
TransRL in practice, its performance at any stage throughout the process of
online learning cannot go below the network performance without any traffic
control/management measures. TransRL’s policies are also designed to ensure
they approximately follow the guidance of model-based optimal flow solutions,
which ensure its interpretability.

The rest of the paper is organized as follows. Literature related to vehicle
routing and RL-based control methods is discussed in section 2. In section 3,
we introduce our framework TransRL and show it can be proved to converge under
conditions of finite discrete state and action space. We subsequently
elaborate on how TransRL can be trained in continuous state space and action
space by using neural networks to approximate value functions and policies.
The problem formulation of the real-time optimal routing problems is included
in section 4. Section 4 then presents how to solve the optimal routing
problems using a model-based method, model-free RL, and the proposed TransRL.
The considered methods are compared with various experiment settings on three
networks in section 5. Section 6 concludes our findings and suggests potential
directions for future work.

##  2 Related works

Quite a few literatures investigated providing real-time route information to
travelers through variable message signs (e.g., Messmer et al. [37],
Wunderlich et al. [58]), and in-vehicle routing mechanisms [4]. However,
assigning routes or providing route information to improve the network
performance is less studied. [3] used cooperative distributed multi-agent
systems to explore the interactions between route information providers and
travelers, and it was found that negotiation between information providers and
travelers can improve the network performance. [43] studied affecting traveler
routing behaviors via providing real-time routing information, and a fuzzy
control approach was proposed to determine the information strategy in order
to enhance the network performance. [14] proposed a coordinated online in-
vehicle routing scheme with intentional information provision perturbation
(CRM-IP), which leverages the bounded rationality of travelers to shape
traveler routing behaviors so that the system optimality and user optimality
are balanced. [29] studied a scenario where route choices of autonomous
vehicles can be fully controlled in a centralized manner to improve network
performance. The policy learned by RL performed close to a theoretically
optimal solution in networks composed of up to dozens of links.

In the general traffic control domain, various analytical methods have been
proposed, such as dynamic programming for optimal routing on a 2-route network
[44], max-pressure for signal control [60, 61, 59], and feedback control for
ramp metering [56, 65], to name a few. The analytical methods develop control
policies through mathematical derivations on the top of model assumptions.
These derived control policies often show desirable properties, such as
convergence guarantee (i.e., reliability) and interoperability. However, real
environments may change over time. Because of a lack of learning ability,
these control policies cannot automatically adapt to changing environments,
which deteriorates control performances.

Reinforcement learning algorithms have gained popularity in solving real-time
control problems because of the characteristics of being model-free and
learnable while capable of taking proactive optimal actions even in uncertain
environments [21, 42]. RL algorithms have been extensively applied to various
traffic control problems, including vehicle routing [28, 51], autonomous
driving [64, 66], traffic signal control [45, 30], ramp metering [63],
variable speed limit control [27], and congestion pricing [41]. RL used in
transportation can be categorized into model-free RL (e.g., [30, 21]) and RL
with prior knowledge (e.g., [27, 19, 20, 9, 6]). Model-free RL learns from
scratch by interacting with the environment, so the RL agent explores the
search space by mostly taking random actions during the early stage of the
training. As a consequence, the performance of model-free RL is not guaranteed
and is even worse than the non-control case before the convergence. This is
particularly problematic in the traffic operation domain, because any traffic
management measure cannot afford to under-perform under general public’s
expectation, even for just a few days. In other words, practically it would be
impossible to take a number of days before RL starts to show system benefits.
Our paper can help address this issue by guiding RL online learning with
policies derived from physics models.

Compared with model-free RL, RL with prior knowledge is more data-efficient by
utilizing prior knowledge to narrow down the search space or start with a
policy better than random initialization. [27] utilized transfer learning to
transfer a policy trained on a source scenario to multiple target scenarios.
Though the fundamental diagrams in the target scenarios differed from those in
the source scenario, the transfer learning significantly shortened the
training process in the target scenarios. [19, 20] augmented field data using
traffic flow models. From the augmented data, RL was trained offline, and then
the learned policies were implemented to acquire new field data. This process
repeated such that RL kept learning from the environment. [6] designed a
hybrid reinforcement learning framework that combines a rule-based strategy
and reinforcement learning to optimize the eco-driving strategy. Most of the
time, the vehicle is controlled by RL policies. When the stop warning is
activated, the rule-based strategy will take control and ensure the vehicle
stops safely. [9] proposed an RL-based framework for end-to-end autonomous
driving. While learning to behave optimally, the proposed framework also
learns a latent environment model that predicts the state of the environment
in a low-dimensional latent space. The latent model greatly reduces the sample
complexity by learning the latent states of the high-dimensional observations.
Though RL has been extensively studied in engineering problems (e.g., [33, 34,
35]), the actions of RL policies are not constrained to improve the
reliability and interpretability of the RL policies.

##  3 TransRL

###  3.1 Preliminaries for RL

The problem studied in RL can be formulated as a Markov decision process
(MDP). The state space and the action space are denoted as $\mathcal{S}$ and
$\mathcal{A}$. After applying an action $a_{t}\in\mathcal{A}$ at current state
$s_{t}\in\mathcal{S}$, the next state $s_{t+1}\in\mathcal{S}$ of the
environment is determined by a state transition probability function
$p(s_{t+1}\mid s_{t},a_{t})$, and a reward $r_{t}$ is produced by the
environment. The return is the discounted sum of rewards in the whole horizon
$\sum_{t}\gamma^{t}r_{t}$, where $\gamma$ is a discount factor making a trade-
off between short-term rewards and long-term rewards. A policy $\pi(a_{t}\mid
s_{t})$ determines the probability distribution of actions $a_{t}$ given a
state $s_{t}$. We denote state-action marginals induced by a policy
$\pi(a_{t}\mid s_{t})$ as $\rho_{\pi}(s_{t},a_{t})$.

The objective of reinforcement learning is to find an optimal policy $\pi^{*}$
such that the expected return is maximized.

$\displaystyle\pi^{*}=\arg\max_{\pi}\mathbb{E}_{(s_{t},a_{t})\sim\rho_{\pi}}\left[\sum_{t}\gamma^{t}r_{t}\right]$
(1)

This study focuses on actor-critic methods [17, 32], which are a combination
of Q-learning [57] and policy optimization. Generally, actor-critic methods
use a critic network parameterized as $\theta$ to estimate the expected return
of state-action pairs with a policy $\pi$ (i.e., Q-values
$Q_{\theta}^{\pi}(s_{t},a_{t})$), and an actor network parameterized as $\phi$
to output actions given states (i.e., $\pi_{\phi}(a_{t}\mid s_{t})$).

Both the actor network and the critic network are trained using data from an
experience replay buffer containing transitions $(s_{t},a_{t},s_{t+1},r_{t})$.
The actor network $\pi_{\phi}(a_{t}\mid s_{t})$ is updated by gradient descent
with a loss function based on Q-values.

$\displaystyle
J_{\pi}(\phi)=\mathbb{E}_{a_{t}\sim\pi_{\phi}}\left[-Q_{\theta}(s_{t},a_{t})\right]$
(2)

The critic network is updated by the temporal difference error based on the
Bellman equation, and the loss function for the critic network is given by

$\displaystyle
J_{Q}(\theta)=\left[Q_{\theta}(s_{t},a_{t})-(r_{t}+\gamma\left(Q_{\bar{\theta}}(s_{t+1},a_{t+1})\right))\right]^{2},a_{t+1}\sim\pi_{\bar{\phi}}(s_{t+1})$
(3)

where $Q_{\bar{\theta}}$ and $\pi_{\bar{\phi}}$ are a target critic network
and a target actor network respectively, which are used to stabilize the
training. The actor and critic networks are updated at every learning step,
while the target actor and critic networks are updated periodically by copying
the weights of the actor and critic networks respectively.

###  3.2 TransRL models

Our proposed reinforcement learning framework differentiates from most
previous reinforcement learning algorithms (e.g., DDPG [50], PPO [50], and SAC
[18]) by leveraging information from transportation methods, named
Transportation-informed Reinforcement Learning (TransRL). First, a neural
network is used to learn a stochastic and differentiable teacher policy from a
well-established transportation method. Then, during the training or testing
of TransRL, aside from interactions with the environment, TransRL also learns
from the teacher policy by comparing the current policy with the teacher
policy. The divergence between the two policies, combined with rewards, is
passed to TransRL for learning. The whole process is illustrated in Figure 1.

Figure 1: TransRL concept diagram

####  3.2.1 Teacher policy

We assume there exist well-established transportation models and methods that
can output actions. The choice of transportation domain models can be very
flexible, and it can be traffic model-based, heuristics, or rule-based
methods. Compared with general learning-based methods, which work like a black
box, transportation domain models are more reliable and interpretable as they
incorporate domain knowledge and physics information that would guide the RL
agent to learn effectively.

Then, we develop a stochastic and differentiable teacher policy based on a
transportation domain model. The teacher policy is a probability distribution
for actions given a state. The action distribution concentrates on the action
output by the transportation domain model. The concentration level of the
distribution can be tuned by an unreliability parameter $\sigma$. Figure 2
shows a simple case with an action dimension of 1 and the range of action is
$[0,1]$ where the action represents the portion of vehicles to be diverted
from the most preferred route. As Figure 2 shows, a smaller unreliability
parameter leads to a distribution more concentrated on the action from the
deterministic transportation domain model. Essentially, the teacher policy is
a prior distribution of actions for states. We will provide an example of a
teacher policy in the later section 4.3.

Figure 2: The teacher policy

The benefits of making the teacher policy stochastic and differentiable are
three-fold. First, the unreliability parameter enables tuning how much the
TransRL agent relies on the transportation domain model. Also, a stochastic
teacher policy instructs the TransRL agent how explorative it should be. A
teacher policy with concentrated action distribution results that the TransRL
agent explores less and concentrates on actions near the action derived from
transportation domain models, while a teacher policy with a more flat
distribution encourages the TransRL agent to explore more on the whole action
space. At last, a differentiable teacher policy enables the gradient
propagation, which makes possible the TransRL learning from the teacher
policy.

####  3.2.2 The augmented objective function

To enable TransRL’s learning from the teacher policy, the objective of TransRL
is to maximize the cumulative rewards while minimizing the differences between
the divergence between the learned policy and the teacher policy. Therefore,
the objective function of TransRL is different from the objective function of
most previous reinforcement learning algorithms as equation (1) shows. This
novel objective fundamentally changes the exploration behaviors and the
learning process of the reinforcement learning agent. Specifically, the
objective function of TransRL is given by

$J(\pi)=\mathbb{E}_{(s_{t},a_{t})\sim\rho_{\pi}}\left[\sum_{t}\gamma^{t}\left(r_{t}-\alpha\mathcal{D}\left(\pi(\cdot\mid
s_{t})||\pi_{TC}(\cdot\mid s_{t})\right)\right)\right]$ (4)

where $\alpha$ is the temperature parameter that makes a trade-off between the
reward and the divergence term. The choice of divergence function is
relatively flexible. Without loss of generality, we adopt the Kullback–Leibler
(KL) divergence. Then, the augmented objective becomes

$\displaystyle J(\pi)$
$\displaystyle=\mathbb{E}_{(s_{t},a_{t})\sim\rho_{\pi}}\left[\sum_{t}\gamma^{t}\left(r_{t}-\alpha
D_{KL}\left(\pi(\cdot\mid s_{t})||\pi_{TC}(\cdot\mid
s_{t})\right)\right)\right]$ (5)
$\displaystyle=\mathbb{E}_{(s_{t},a_{t})\sim\rho_{\pi}}\left[\sum_{t}\gamma^{t}\left(r_{t}+\alpha\mathcal{H}\left(\pi(\cdot\mid
s_{t})\right)+\alpha\mathbb{E}_{a\sim\pi(\cdot\mid
s_{t})}\left[\log\pi_{TC}(a\mid s_{t})\right]\right)\right]$ (6)

######  Theorem 1.

The maximum entropy reinforcement learning SAC [18] is equivalent to TransRL
with a teacher policy of uniform distribution.

###### Proof.

If $\pi_{TC}$ is a uniform distribution, $\pi_{TC}(a\mid s_{t})$ is a constant
regardless of $a$, so $\mathbb{E}_{a\sim\pi(\cdot\mid
s_{t})}\left[\log\pi_{TC}(a\mid s_{t})\right]$ is also a constant regardless
of $\pi$. As a result, we can remove $\mathbb{E}_{a\sim\pi(\cdot\mid
s_{t})}\left[\log\pi_{TC}(a\mid s_{t})\right]$ from the objective function
(6), and then it becomes

$\displaystyle
J(\pi)=\mathbb{E}_{(s_{t},a_{t})\sim\rho_{\pi}}\left[\sum_{t}\gamma^{t}\left(r_{t}+\alpha\mathcal{H}\left(\pi(\cdot\mid
s_{t})\right)\right)\right]$ (7)

which is the objective of SAC [18]. ∎

######  Remark 1.

Including the KL divergence term in the objective results that TransRL becomes
more reliable and interpretable than classical RL. With this divergence
constraint, the policy $\pi$ does not go too far away from the teacher policy
$\pi_{TC}$ that is assumed to be reliable and interpretable.

####  3.2.3 Policy iteration

The optimal policy is solved using policy iteration. The policy iteration
includes, (1) the policy evaluation step where the value functions are
estimated given a policy, and (2) the policy improvement step where the policy
is updated to increase the values given the value functions. By repeating the
policy evaluation and the policy improvement, the policy is guaranteed to
converge to one of the optimal policies that maximize values.

TransRL uses auxiliary Q-values according to the augmented objective function
such that maximizing auxiliary Q-values is equivalent to maximizing the
augmented objective. The auxiliary Q-values are given by

$\displaystyle Q(s_{t},a_{t})=r_{t}+\gamma\mathbb{E}_{s_{t+1}\sim
p}\left[V(s_{t+1})\right]$ (8)

where

$\displaystyle
V(s_{t+1})=\mathbb{E}_{a_{{t+1}}\sim\pi}\left[Q(s_{t+1},a_{t+1})+\alpha\log\frac{\pi_{TC}(a_{t+1}\mid
s_{t+1})}{\pi(a_{t+1}\mid s_{t+1})}\right]$ (9)

is the auxiliary state value.

For the policy evaluation, The auxiliary Q-values are updated iteratively by a
modified Bellman equation

$Q^{k+1}(s_{t},a_{t})\leftarrow r_{t}+\gamma\mathbb{E}_{s_{t+1}\sim
p}\left[V^{k}(s_{t+1})\right]$ (10)

With the above update rule, the auxiliary Q-values can be proved to converge
to the unique auxiliary Q-values of the policy $\pi$ as follows.

######  Lemma 1 (Policy evaluation convergence).

Starting with a initial auxiliary Q-values function
$Q^{0}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ with
$|\mathcal{A}|<\infty$, update $Q^{0}$ iteratively using equation (10). As
$k\rightarrow\infty$, $Q^{k}$ converges to the unique auxiliary Q-values
function of $\pi$.

###### Proof.

Let’s define an augmented reward

$r_{t}^{\pi}(s_{t},a_{t})=r_{t}(s_{t},a_{t})+\gamma\alpha\mathbb{E}_{a_{t+1}\sim\pi}\left[\log\frac{\pi_{TC}(a_{t+1}\mid
s_{t+1})}{\pi(a_{t+1}\mid s_{t+1})}\right]$ (11)

Then, equation (10) becomes

$Q^{k+1}(s_{t},a_{t})\leftarrow
r_{t}^{\pi}(s_{t},a_{t})+\gamma\mathbb{E}_{s_{t+1}\sim
p,a_{t+1}\sim\pi}\left[Q^{k}(s_{t+1},a_{t+1})\right]$ (12)

As $|\mathcal{A}|<\infty$, the KL divergence in equation (11) is bounded, so
$r_{t}^{\pi}(s_{t},a_{t})$ is bounded. Then, one can apply the contraction
mapping theorem to prove $Q^{k}$ converge to the unique auxiliary Q-values,
which is the same as the proof for standard reinforcement learning [52]. ∎

For the policy improvement, the policy is updated such that the auxiliary
Q-values of the new policy are higher than the old policy. Similar to [18], we
use a KL divergence between the old policy and the exponential of the
auxiliary Q function, and the new policy is obtained by minimizing the KL
divergence as follows.

$\displaystyle\pi_{new}=\arg\min_{\pi\in\Pi}D_{KL}\left(\pi(\cdot\mid
s_{t})\mid\mid\frac{\pi_{TC}(\cdot\mid
s_{t})\exp{(Q^{\pi_{old}}(s_{t},\cdot)/\alpha)}}{\mathcal{Z}^{\pi_{old}}(s_{t})}\right)$
(13)

where $\mathcal{Z}^{\pi_{old}}(s_{t})$ is the partition function ensuring the
right part within the KL divergence is a probability distribution. Though
$\mathcal{Z}^{\pi_{old}}(s_{t})$ is intractable and infeasible for large state
spaces, it is a constant and can be ignored when calculating gradients with
respect to the policy. With this policy update rule, we can prove the new
policy is better than the old policy with respect to auxiliary Q-values as
follows.

######  Lemma 2 (Policy improvement convergence).

For $\pi_{old}\in\Pi$, $\pi_{new}$ is the optimal solution of the problem
defined in equation (13). With $|\mathcal{A}|<\infty$,
$Q^{\pi_{new}}(s_{t},a_{t})\geq
Q^{\pi_{old}}(s_{t},a_{t}),\forall(s_{t},a_{t})\in\mathcal{S}\times\mathcal{A}$.

###### Proof.

Denote the KL divergence term in equation (13) as

$J_{\pi_{old}}(\pi)=D_{KL}\left(\pi(\cdot\mid
s_{t})\mid\mid\frac{\pi_{TC}(\cdot\mid
s_{t})\exp{(Q^{\pi_{old}}(s_{t},\cdot)/\alpha)}}{\mathcal{Z}^{\pi_{old}}(s_{t})}\right)$
(14)

Then, as $\pi_{new}$ is a minimizer of the KL divergence, we have

$\displaystyle J_{\pi_{old}}(\pi_{old})$ $\displaystyle\geq
J_{\pi_{old}}(\pi_{new})$ (15)
$\displaystyle\begin{split}\Rightarrow\;\mathbb{E}_{a_{t}\sim\pi_{old}}&\left[\log\pi_{old}(a_{t}\mid
s_{t})-\log\pi_{TC}(a_{t}\mid
s_{t})-Q^{\pi_{old}}(a_{t},s_{t})/\alpha+\log\mathcal{Z}^{\pi_{old}}(s_{t})\right]\\\
&\geq\mathbb{E}_{a_{t}\sim\pi_{new}}\left[\log\pi_{new}(a_{t}\mid
s_{t})-\log\pi_{TC}(a_{t}\mid
s_{t})-Q^{\pi_{old}}(a_{t},s_{t})/\alpha+\log\mathcal{Z}^{\pi_{old}}(s_{t})\right]\\\
\Rightarrow\;\mathbb{E}_{a_{t}\sim\pi_{old}}&\left[Q^{\pi_{old}}(a_{t},s_{t})+\alpha\log\frac{\pi_{TC}(a_{t}\mid
s_{t})}{\pi_{old}(a_{t}\mid s_{t})}\right]\\\
&\leq\mathbb{E}_{a_{t}\sim\pi_{new}}\left[Q^{\pi_{old}}(a_{t},s_{t})+\alpha\log\frac{\pi_{TC}(a_{t}\mid
s_{t})}{\pi_{new}(a_{t}\mid s_{t})}\right]\end{split}$ (16)
$\displaystyle\Rightarrow\;V^{\pi_{old}}(s_{t})$
$\displaystyle\leq\mathbb{E}_{a_{t}\sim\pi_{new}}\left[Q^{\pi_{old}}(a_{t},s_{t})+\alpha\log\frac{\pi_{TC}(a_{t}\mid
s_{t})}{\pi_{new}(a_{t}\mid s_{t})}\right]$ (17)

Now, follow equation (8) to replace $Q^{\pi_{old}}$ with a formulation of
$V^{\pi_{old}}$, and then apply the inequality (17). By conducting these two
steps alternatively, we obtain

$\displaystyle Q^{\pi_{old}}(s_{t},a_{t})$
$\displaystyle=r(s_{t},a_{t})+\gamma\mathbb{E}_{s_{t+1}\sim
p}\left[V^{\pi_{old}}(s_{t+1})\right]$ (18) $\displaystyle\leq
r(s_{t},a_{t})+\gamma\mathbb{E}_{s_{t+1}\sim
p}\left[\mathbb{E}_{a_{t}+1\sim\pi_{new}}\left[Q^{\pi_{old}}(a_{t+1},s_{t+1})+\alpha\log\frac{\pi_{TC}(a_{t+1}\mid
s_{t+1})}{\pi_{new}(a_{t+1}\mid s_{t+1})}\right]\right]$ (19)
$\displaystyle\cdots$ (20) $\displaystyle\leq
r(s_{t},a_{t})+\gamma\mathbb{E}_{s_{t+1}\sim
p}\left[V^{\pi_{new}}(s_{t+1})\right]$ (21)
$\displaystyle=Q^{\pi_{new}}(s_{t},a_{t})$ (22)

∎

The policy iteration alternates between the policy evaluation and the policy
improvement. Finally, we can prove the policy iteration will converge to an
optimal policy that maximizes the auxiliary Q-values as follows.

######  Theorem 2 (Policy iteration convergence).

With $|\mathcal{A}|<\infty$, starting from any policy $\pi^{0}\in\Pi$, conduct
the policy evaluation and the policy improvement iteratively. The policy will
converge to an optimal policy $\pi^{*}$ such that
$Q^{\pi^{*}}(s_{t},a_{t})\geq
Q^{\pi}(s_{t},a_{t}),\forall(s_{t},a_{t})\in\mathcal{S}\times\mathcal{A},\pi\in\Pi$.

###### Proof.

According to Lemma 2, at each policy iteration step, we have
$Q^{\pi_{new}}\geq Q^{\pi_{old}}$. As the augmented rewards are bounded,
$Q^{\pi}$ is also bounded. As a result, $Q^{\pi}$ will converge to a certain
point, where both the auxiliary Q-values and the policy converge, denoted as
$Q^{\pi^{*}}$. Then, we get $J_{\pi^{*}}(\pi^{*})\leq
J_{\pi^{*}}(\pi),\forall\pi\in\Pi$. Similar to the proof of Lemma 2, we have
$Q^{\pi^{*}}(s_{t},a_{t})\geq
Q^{\pi}(s_{t},a_{t}),\forall(s_{t},a_{t})\in\mathcal{S}\times\mathcal{A},\pi\in\Pi$.
∎

Note the above policy iteration process only works for tabular cases where the
state space and the action space are discrete. In more general cases where
state variables and actions can be continuous. We can use approximations
(e.g., neural networks) to approximate auxiliary Q-values. In addition, at the
policy evaluation or the policy improvement step, running until convergence is
computationally expensive. In the next section, we will introduce how TransRL
is trained in practice, which is suitable for a continuous state and action
space.

####  3.2.4 Training of TransRL

To accommodate large continuous state space and action space, we use neural
networks to approximate the auxiliary Q-values/Q-function and the policy. The
auxiliary Q-function is parameterized by the neural network parameters
$\theta$, which is denoted as $Q_{\theta}(s_{t},a_{t})$. Similarly, the
parameterized policy is $\pi_{\phi}(a_{t}\mid s_{t})$, where $\phi$ are the
parameters of the policy neural network.

For the Q-function network, the parameters are updated to minimize the Bellman
residual. More specifically, the loss of the Q-function network is given by:

$\displaystyle
J_{Q}(\theta)=\mathbb{E}_{s_{t},a_{t}\sim\mathcal{D}}\left[\left(Q_{\theta}(s_{t},a_{t})-\hat{Q}(s_{t},a_{t})\right)^{2}\right]$
(23)

where

$\displaystyle\hat{Q}(s_{t},a_{t})=r_{t}+\gamma\left(Q_{\bar{\theta}}(s_{t+1},a_{t+1})+\alpha\log\frac{\pi_{TC}(a_{t+1}\mid
s_{t+1})}{\pi_{\phi}(a_{t+1}\mid
s_{t+1})}\right),\,a_{t+1}\sim\pi_{\phi}(\cdot\mid s_{t+1})$ (24)

where $Q_{\bar{\theta}}$ is the target Q-function whose parameters are
exponentially moving average of parameters of $Q_{\theta}$. The use of target
networks is able to stabilize the training process [38]. Then, the Q-function
network is trained via stochastic gradient descent methods with gradient

$\displaystyle\nabla_{\theta}J_{Q}(\theta)=2\nabla_{\theta}Q_{\theta}(s_{t},a_{t})\left(Q_{\theta}(s_{t},a_{t})-\hat{Q}(s_{t},a_{t})\right)$
(25)

The policy network is trained by minimizing the KL divergence in equation
(13).

$\displaystyle
J_{\pi}(\phi)=\mathbb{E}_{s_{t}\sim\mathcal{D}}\left[\mathbb{E}_{a_{t}\sim\pi_{\phi}}\left[\log\pi_{\phi}(a_{t}\mid
s_{t})-\log\pi_{TC}(a_{t}\mid
s_{t})-Q_{\theta}(s_{t},a_{t})/\alpha\right]\right]$ (26)

To enable back-propagation in updating $\phi$, the reparameterization trick is
used to generate action.

$\displaystyle a_{t}=f_{\phi}(\epsilon_{t};s_{t})$ (27)

where $\epsilon_{t}$ is independent random noise sampled from a Gaussian
distribution. Afterwards, the loss function of the policy network becomes

$\displaystyle
J_{\pi}(\phi)=\mathbb{E}_{s_{t}\sim\mathcal{D},\epsilon_{t}\sim\mathcal{N}}\left[\log\pi_{\phi}(f_{\phi}(\epsilon_{t};s_{t})\mid
s_{t})-\log\pi_{TC}(f_{\phi}(\epsilon_{t};s_{t})\mid
s_{t})-Q_{\theta}(s_{t},f_{\phi}(\epsilon_{t};s_{t}))/\alpha\right]$ (28)

Finally, the parameters $\phi$ can be updated via stochastic gradient methods
with the gradient of

$\displaystyle\nabla_{\phi}J_{\pi}(\phi)=\nabla_{\phi}\log\pi_{\phi}(a_{t}\mid
s_{t})+\left(\nabla_{a_{t}}\log\pi_{\phi}(a_{t}\mid
s_{t})-\nabla_{a_{t}}\log\pi_{TC}(a_{t}\mid
s_{t})-\nabla_{a_{t}}Q_{\theta}(s_{t},a_{t})\right)\nabla_{\phi}f_{\phi}(\epsilon_{t};s_{t})$
(29)

To mitigate the overestimation bias in the Q-values estimation, we use the
clipped double Q-learning trick in our practical algorithm [17]. Specifically,
we use two Q-functions $Q_{\theta_{i}}$ that are trained independently, and
two target Q-functions $Q_{\bar{\theta}_{i}}$. Therefore, the target
Q-function in equation (24) is the minimum of the two target Q-functions, and
the Q-function in equation (29) is the minimum of the two Q-functions.

##  4 The real-time system optimal traffic routing problems

Suppose a morning commuting scenario on a general road network with vertices,
$v\in\mathcal{V}$, and links, $l\in\mathcal{L}$. The origins (O) of travel
demands are $g\in\mathcal{G}$, and the destinations (D) are $e\in\mathcal{E}$.
The set of paths from an origin $g$ to a destination $e$ is denoted as
$\mathcal{P}^{ge}$. For small networks, the paths between $g$ and $e$ can be
enumerated, so the path set $\mathcal{P}^{ge}$ contains all non-cyclic paths
$p_{i}^{ge}$ between $g$ and $e$. For large networks, the paths cannot be
enumerated, so $\mathcal{P}^{ge}$ contains a small portion of all possible
paths. For example, each path set $\mathcal{P}^{ge}$ includes k shortest or
most frequently used paths of each OD pair, or paths varying only by major
alternative routes. The demands are assumed to be time-dependent and
stochastic. The whole time horizon is divided into multiple time intervals,
and each time interval is denoted by $t$. The demand of OD pair $ge$ during
time interval $t$ is $q_{t}^{ge}$, which follows a Gaussian distribution
$q_{t}^{ge}\sim\mathcal{N}(\mu(q_{t}^{ge}),\sigma(q_{t}^{ge}))$.

The environment $\mathcal{M}$ includes two components: (1) the road network,
including the topology of the network, and the link properties (i.e., lengths,
the numbers of lanes, free flow speeds, and capacities); and (2) the traffic
flow dynamics, which is Cell Transmission Model (CTM) [11, 12] and node models
[40] in our study. CTM and node model essentially determine how the
environment state evolves given the current state, input demands, and control
actions.

The objective of real-time system optimal traffic routing problems [44] is to
assign all vehicles to paths so that the total travel time of all travelers is
minimized. Since the travel demands are stochastic, we cannot expect the total
number of vehicles to be assigned, nor the number of vehicles for each path in
the path set. Therefore, the control actions in our formulation are the
assignment ratios across paths. The assignment ratio of path $p_{i}^{ge}$
between OD pair $ge$ during time interval $t$ is denoted as
$\kappa_{i,t}^{ge}$ and $\sum_{i}\kappa_{i,t}^{ge}=1$. At the beginning of
each time interval $t$, the control algorithm decides the path ratios
$\kappa_{i,t}^{ge}$, so there are $q_{t}^{ge}\kappa_{i,t}^{ge}$ vehicles to be
routed to the path $p_{i}^{ge}$ during time interval $t$. The control
algorithm aims at minimizing the total travel time of all travelers within the
whole time horizon by determining path ratios.

Reliability or risk of control policies is also an important metric when
implementing system optimal routing in the field. In traffic operations, a
question of high interest is how bad the worst cases during RL online process
are compared with the User Equilibrium (i.e., no-control) scenario. On top of
the well-known risk measure Conditional Value at Risk (CVaR) which was
originally proposed in finance [1] and has been popular in safe RL recently
[7], we propose a risk measure Conditional Travel Time Reduction at Risk
(CTTRaR) for travel time reduction problems. CVaR for total travel time is
given by

$\text{CVaR}_{x}(TTT)=\mathbb{E}[TTT\mid TTT\geq VaR_{x}(TTT)]$ (30)

where $VaR_{x}(TTT)$ is the $x$-quantile of the distribution of total travel
time ($TTT$). Then, CTTRaR is

$\text{CTTRaR}_{x}(TTT)=\text{CVaR}_{x}(TTT_{UE})-\text{CVaR}_{x}(TTT)$ (31)

where $\text{CVaR}_{x}(TTT_{UE})$ is the CVaR of $TTT$ in the UE (no-control)
scenario. Generally, CTTRaR measures, in the worst performance cases, how much
total travel time the control method can reduce compared with the no-control
scenario. CTTRaR focuses on the left-most tail of the distribution.

###  4.1 Approach 1: deterministic system optimal dynamic traffic assignment
as a transportation domain model

To solve the above real-time system optimal routing problems, one approach is
to solve an optimal solution offline by leveraging traffic models and
estimated demands. First, a traffic model, denoted as $\mathcal{\tilde{M}}$,
is built to simulate the real environment $\mathcal{M}$. The travel demands,
denoted as $\mathbf{q}$, are estimated based on historical data and the
estimated demands are denoted as $\mathbf{\tilde{q}}$. Then, one can solve a
system-optimal dynamic traffic assignment (SODTA) on top of the traffic model
and the estimated demands. Eventually, the solved SODTA can suggest optimal
path flows for each time interval. During the online experiments, the vehicles
are assigned with paths according to the pre-calculated path ratios.

In this study, we implement the solution algorithm in [47] to solve SODTA.
First, the path marginal cost is approximated, so the system-optimal paths can
be identified. Then, the well-known method of successive averages (MSA) can be
applied to solve SODTA iteratively. The policy obtained by solving SODTA
offline is denoted as pre-DSO.

The performance of pre-DSO depends on the difference between
$\mathcal{\tilde{M}}$ and $\mathcal{M}$ and the estimation error of
$\mathbf{\tilde{q}}$. On if the traffic model and the estimated demands
perfectly align with the real case (i.e., $\mathcal{\tilde{M}}=\mathcal{M}$
and $\mathbf{\tilde{q}}=\mathbf{q}$), pre-DSO is the optimal solution to the
routing problems. This is clearly not viable in practice. Thus, we must
consider a model mismatch between $\mathcal{M}$ and $\mathcal{\tilde{M}}$, and
uncertain demands varying from estimated demand. As a result, pre-DSO is no
longer guaranteed to be optimal, and possibly far from being optimal.

###  4.2 Approach 2: model-free reinforcement learning

The real-time optimal traffic routing problem can be formulated into an MDP.
Then, the MDP can be solved by standard reinforcement learning with continuous
action space (e.g., PPO [50] and SAC [18]). Here we introduce how the
essential elements of the MDP are defined for the real-time routing problem.

State. States of the network or environment can be defined as

$s_{t}=[u_{t}^{l}],\forall l\in\mathcal{L}$ (32)

where $u_{t}^{l}$ is the number of vehicles passing link $l$ during time
interval $t$.

Observation. In realistic scenarios, the states of the whole road network
cannot be accessed. Instead, only a portion of links is observed through
sensors, and the set of observed links is $\mathcal{\hat{L}}$. More
specifically, sensors collect real-time speeds and flows and send the averages
during the last time interval at the beginning of the current time interval.
Then, the control algorithm takes these real-time data (i.e., observations) as
input and accordingly output actions. Therefore, observations of the
environment are defined as

$o_{t}=[t,f_{t}^{l},d_{t}^{l}],\forall l\in\mathcal{\hat{L}}$ (33)

where $f_{t}^{l}$ and $d_{t}^{l}$ are average flow and speed during time
interval $t$ on link $l$. $t$ is included as an analogy of time of the day.

Action. In our formulation, the control algorithm determines the path
assignment ratios, so actions are path ratios as follows.

$a_{t}=[\kappa_{i,t}^{ge}],\forall
p_{i}^{ge}\in\mathcal{P}^{ge},g\in\mathcal{G},e\in\mathcal{E}$ (34)

Reward. The control objective of the real-time system optimal routing problems
is to minimize the total travel time of all vehicles during the whole time
horizon as follows.

$\displaystyle\min_{a_{1},a_{2},\cdots,a_{t},\cdots}\eta\sum_{t}\sum_{l}u_{t}^{l}$
(35)

where $\eta$ is the length of each time interval. If the reward
$r_{t}=-\eta\sum_{l}u_{t}^{l}$ with $\gamma=1$, the control objective is
equivalent to the objective of reinforcement learning as follows.

$\displaystyle\min_{a_{1},a_{2},\cdots,a_{t},\cdots}\eta\sum_{t}\sum_{l}u_{t}^{l}\iff\max_{a_{1},a_{2},\cdots,a_{t},\cdots}\sum_{t}\gamma^{t}r_{t}$
(36)

However, we do not assume $u_{t}^{l}$ is accessible for all links. An
alternative and more practical way is to use the number of vehicles leaving
the controlled road network during each time interval, which can be retrieved
by monitoring the periphery of the controlled road network. The number of
leaving/finished vehicles at the end of time interval $t$ is denoted as
$F_{t}$ and the number of vehicles within the area at the beginning of the
whole time horizon is denoted as $N_{0}$. Now, we have

$\displaystyle\min_{a_{1},a_{2},\cdots,a_{t},\cdots}$
$\displaystyle\eta\sum_{t}\sum_{l}u_{t}^{l}$ (37)
$\displaystyle\iff\min_{a_{1},a_{2},\cdots,a_{t},\cdots}$
$\displaystyle\eta\sum_{t}\left(N_{0}+\sum_{g}\sum_{e}q_{t}^{ge}-F_{t}\right)$
(38) $\displaystyle\iff\max_{a_{1},a_{2},\cdots,a_{t},\cdots}$
$\displaystyle\sum_{t}F_{t}$ (39)

Based on the above reasoning, the reward function is given as

$r_{t}\equiv\frac{F_{t}-\bar{F}_{t}}{N}$ (40)

where $\bar{F}_{t}$ is the average number of finished vehicles in the past and
$N$ is a constant that approximately scales the reward into a range of [-10,
10]. We found the usage of $\bar{F}_{t}$ improved the training of
reinforcement learning as it normalizes rewards along time intervals, and the
usage of $N$ accelerated the training process as the reward scale is
constrained into a small range and thereby quicker convergence in Q-values.

###  4.3 Approach 3: TransRL

TransRL incorporates the traffic model $\tilde{\mathcal{M}}$ in section 4.1
into RL by developing a teacher policy based on the model-based policy pre-
DSO, and then learns from the teacher policy. Specifically, pre-DSO can output
an action $\tau(s)$ given a state $s$. We ignore the subscript $t$ here for
readability.

$\tau(s)$ is not differentiable with regard to $s$ as the pre-DSO policy is
solved iteratively using an intractable algorithm. This prohibits gradient
propagation during training. Therefore, a differentiable neural network
$\mu(s)$ is leveraged to imitate the pre-DSO policy by minimizing the mean
squared loss between $\tau(s)$ and $\mu(s)$.

Then, the teacher policy $\pi_{TC}$ can be defined as a Multivariate normal
distribution

$a_{TC}\sim\pi_{TC}(\cdot\mid s)=\mathcal{N}(\mu(s),\Sigma)$ (41)

where the mean vector $\mu(s)$ is approximately equal to $\tau(s)$, and
$\Sigma$ is assumed to be a diagonal matrix

$\Sigma=\begin{bmatrix}\sigma&&&0\\\ &\sigma\\\ &&\ddots\\\
0&&&\sigma\end{bmatrix}$ (42)

where $\sigma$ is the unreliability parameter to tune how much TransRL should
rely on the model-based policy pre-DSO. Implicitly, as the unreliability
parameter increases, TransRL is less dependent on the traffic model
$\tilde{\mathcal{M}}$. If the unreliability parameter is infinity, the action
distribution is almost a uniform distribution, which means the information
from the model is not used at all.

##  5 Experiments

We conduct extensive experiments on three networks, including an abstractive
two-route network, a synthetic network, and a large network with hundreds of
links. In all three networks, we assume the demands are uncertain and follow
Gaussian distributions
$q_{t}^{qe}\sim\mathcal{N}(\tilde{q}_{t}^{qe},\beta\tilde{q}_{t}^{qe})$, where
$\tilde{q}_{t}^{qe}$ is the historical average demand and $\beta$ is a
parameter of demand uncertainty level. In the synthetic network, we assume a
model mismatch between the traffic model $\tilde{\mathcal{M}}$ and the real
system dynamics $\mathcal{M}$, and the model mismatch stems from the parameter
estimation errors (i.e., inaccurate free-flow speeds and critical densities).
In the large network, the model mismatch is caused by unexpected incidents
that block lanes.

Our proposed algorithm TransRL is compared with various routing strategies and
baselines, which are summarized as follows.

  * 1.

Model-based method: pre-DSO. This is the policy obtained in section 4.1,
namely through System Optimal Dynamic Traffic Assignment.

  * 2.

Model-free reinforcement learning: PPO [50]. PPO is a state-of-the-art policy
optimization algorithm. PPO updates policy by maximizing the advantages while
using a clip operation to make sure the updated policy does not go far from
the old policy.

  * 3.

Model-free reinforcement learning: SAC [18]. SAC is a state-of-the-art model-
free reinforcement learning algorithm. SAC uses value networks to evaluate
state-action pairs and policy networks to output actions. The most notable
attribute of SAC is the entropy term in the objective. SAC aims at maximizing
returns while maintaining a policy as stochastic as possible, which enables
SAC to explore the environment sufficiently and avoid being stuck at a local
optimum.

  * 4.

No-control baseline: User Equibrlium(UE). In the large network where some
count and speed data are available, we conducted an dynamic OD estimation, and
the path ratios from the OD estimation were applied and regarded as the UE
baseline.

###  5.1 An abstractive network with uncertain demands

The first network is the abstractive 2-route network in [44]. The 2-route
network is an abstraction of a general network during morning peak hours (see
Figure 3(a)). After abstraction, the network connects the residential
neighborhoods (the origin) and the downtown (the destination) through two
routes: (1) route 1 is the main corridor with high free-flow speed but with
limited capacity, and (2) route 2 is the aggregation of all local streets with
low free-flow speed but with sufficient capacity. The action is the ratio of
demands choosing route 1.

During morning peak hours, typical demands increase and then decrease as
Figure 3(b) shows. At each time step, the demand follows a Gaussian
distribution $q_{t}\sim\mathcal{N}(\mu_{t},\beta\mu_{t})$, where $\mu_{t}$ is
the historical mean demand at time $t$ and $\beta$ is the demand uncertainty
parameter. In our experiments, we considered three scenarios, including a low
demand uncertainty scenario ($\beta=0.05$), a medium demand uncertainty
scenario ($\beta=0.10$), and a high demand uncertainty scenario
($\beta=0.20$).

(a) The abstractive 2-route network in [44]

(b) Demand distributions with different uncertainties

Figure 3: The abstractive network and demands

####  5.1.1 Training of reinforcement learning

TransRL, PPO, and SAC were trained on all three scenarios with the same
observation definition, action definition, and reward function. For
comparison, the hyperparameters of each RL are the same in three scenarios.
The training process is plotted in Figure 4. There are two main findings.
First, among all three scenarios, TransRL converged quicker than PPO and SAC,
while even after convergence, returns of TransRL were higher than PPO and SAC.
This indicates that TransRL is more efficient in finding a good policy and
this policy is better than those found by PPO and SAC. In addition, the
differences between the three RL decrease as the demand uncertainty level
increases. This is reasonable. As the demand uncertainty level increases, the
actions from the pre-DSO are less close to the optimal actions because the
demand estimation is less accurate. As a result, the information from the
teacher policy is less informative when the demand uncertainty level is
larger.

(a) Low demand uncertainty

(b) Medium demand uncertainty

(c) High demand uncertainty

Figure 4: Training on the 2-route network

To shed insights on how TransRL learns from the teacher policy, the actions
from TransRL and SAC are plotted in Figure 5. For comparison, the actions from
the pre-DSO and DSO are also included. Given the single-peak demands, the
optimal path ratio for route 1 should decrease during the first half to
deviate vehicles to route 2, and then increase to assign more vehicles back to
route 1 in general [44]. The optimal path ratios depend on the specific
demands. While DSO uses the actual demands to calculate the optimal path
ratios, pre-DSO calculates the "optimal" path ratios using historical mean
demands which work as an approximation of the actual demands. As pre-DSO
depends on historical mean demands, the actions of pre-DSO are pre-calculated
and deterministic along different episodes and different demand scenarios. DSO
uses actual demands, so the actions are calculated in real time. As Figure 5
shows, the difference between pre-DSO and DSO increases as demand uncertainty
becomes high because the actual demands deviate more from the historical mean
demands in the high demand uncertainty scenario. As a consequence, pre-DSO
performs worse as demand uncertainty increases.

Compared with SAC, TransRL is much more efficient in retrieving a policy close
to the optimal policy. In all three demand scenarios, it took 100 episodes
that SAC learned to decrease the action during the first 10 time steps, and it
took another 300 episodes for SAC to learn to increase the actions during the
last 10 time steps. In contrast, TransRL learned the general pattern of
decreasing and then increasing actions after just 5 episodes, which indicates
the teacher policy boosted the learning process of TransRL. Furthermore, the
actions from TransRL are more stable than SAC, which indicates the policy from
TransRL is more interpretable. Notably, different from pre-DSO whose actions
are fixed, TransRL is adaptive to real-time states and can continuously learn
from interactions.

(a) Low demand uncertainty

(b) Medium demand uncertainty

(c) High demand uncertainty

Figure 5: Policy evolution on the 2-route network

####  5.1.2 Control performances of online tests

After the training, we tested all control methods for 100 episodes under
uncertain demands with the same random seed. In the no-control case (i.e.,
UE), the travel time on both routes is identical so that no traveler can
benefit from changing routes. For comparison, we also tested the stochastic
optimal method in [44], which can be regarded as the optimum without knowing
the actual demands in advance. [44] analytically formulates the optimal
routing problem of the 2-route network and solves the stochastic optimal
policy using dynamic programming, denoted as DP.

The total travel time under different control methods is summarized in Table 1
and plotted in Figure 6. Compared with the no-control case, all control
methods could significantly reduce the total travel time. The comparison
between the model-based method (i.e., pre-DSO) and the model-free RL (i.e.,
PPO and SAC) is interesting. With low or medium demand uncertainty, pre-DSO
led to lower total travel time than PPO and SAC. However, when the demand
uncertainty is high, SAC outperformed pre-DSO. This indicates the model-based
method performs well when the actual system is close to the approximation, but
it is brittle to information inaccuracy. While model-free RL is adaptive, it
does not fully utilize prior information.

Notably, in all three demand scenarios, TransRL outperformed both the model-
based method and the model-free RL in reducing total travel time and was
pretty close to the stochastic optimum (i.e., DP). This can be attributed to
TransRL combining the advantages of RL and the model-based method. As an RL,
TransRL is able to adapt to real-time states and learn from the training
experiences. On the other hand, it utilizes the prior information from the
model and historical mean demands.

The reliability of control methods is measured using the proposed metric
$\text{CTTRaR}_{x}$, which is listed in Table 2. Higher $\text{CTTRaR}_{x}$
indicates more reliability in worst cases. With low demand uncertainty, pre-
DSO is more reliable than SAC, but SAC is more reliable than pre-DSO when
demand uncertainty is medium or high. Except for the stochastic optimum (DP),
TransRL is the most reliable with low or medium demand uncertainty, and SAC is
the most reliable with high demand uncertainty. This indicates that when
demand uncertainty is high, a more stochastic policy is more reliable.
Overall, TransRL is more reliable than pre-DSO, PPO, and SAC.

Table 1: Total travel time on the 2-route network during 100 test episodes |  Low demand uncertainty |  Medium demand uncertainty |  High demand uncertainty
---|---|---|---
Total travel time |  Average |  SD |  Average |  SD |  Average |  SD
UE (no control) |  17334.72 |  266.92 |  17346.28 |  522.11 |  17341.98 |  997.96
pre-DSO (model-based) |  9592.76 |  350.95 |  9959.54 |  706.23 |  10683.08 |  1415.86
PPO (model-free RL) |  11410.16 |  450.78 |  11193.19 |  633.29 |  11597.74 |  1091.86
SAC (model-free RL) |  9782.19 |  239.96 |  9971.37 |  488.80 |  10463.12 |  930.34
TransRL (ours) |  9592.45 |  255.91 |  9817.92 |  496.42 |  10357.36 |  1031.81
DP (stochastic optimal) |  9450.98 |  239.24 |  9730.62 |  497.39 |  10267.50 |  918.97
Figure 6: Average total travel time on the 2-route network during 100 test episodes Table 2: $\text{CTTRaR}_{x}$ on the 2-route network during 100 test episodes. The quantile $x$ is set to be 10%, which means the top 10% worst episodes. |  Low demand uncertainty |  Medium demand uncertainty |  High demand uncertainty
---|---|---|---
| $\text{CTTRaR}_{x}$ | $\text{CTTRaR}_{x}$ | $\text{CTTRaR}_{x}$
pre-DSO (model-based) | 7510.85 | 6881.29 | 5535.49
PPO (model-free RL) | 5318.24 | 5531.50 | 6068.37
SAC (model-free RL) | 7507.93 | 7385.84 | 7054.28
TransRL (ours) | 7700.58 | 7422.13 | 6764.85
DP (stochastic optimal) | 7917.94 | 7580.57 | 7180.80

####  5.1.3 Sensitivity analysis of the unreliability parameter

In TransRL, the unreliability parameter $\sigma$ determines how much the
TransRL should depend on the transportation method and how extensive TransRL
should explore the action space. To look into the impacts of the unreliability
parameter, we compared the training processes and the control performances of
TransRL with different unreliability parameters.

The training processes with different unreliability parameters under three
demand scenarios are plotted in Figure 7. In general, the training process was
insensitive to the unreliability parameter. After convergence, different
parameters led to similar performances. In low or medium demand uncertainty
scenarios, the value of the unreliability parameter did affect the convergence
speed, and smaller unreliability parameters led to faster convergence. While
in the high demand uncertainty, the convergence speed was almost identical
along different parameters. The control performances with different parameters
align with this phenomenon. As Figure 8 shows, the control performances were
generally incentive to the parameters, and small unreliability parameters
performed better than large unreliability parameters in low or medium demand
uncertainty scenarios.

(a) Low demand uncertainty

(b) Medium demand uncertainty

(c) High demand uncertainty

Figure 7: Sensitivity analysis on the 2-route network: training process

(a) Low demand uncertainty

(b) Medium demand uncertainty

(c) High demand uncertainty

Figure 8: Sensitivity analysis on the 2-route network: total travel time

###  5.2 A synthetic network with uncertain demands and model mismatch

The second network for experiments is a synthetic corridor network first used
in [39]. As Figure 9 shows, the corridor network, which aims to abstract a
commuting network, is composed of 18 links and 16 nodes. Links 1-2, 2-4, 4-6,
6-8, and 8-10 are freeway links, so these links has high free-flow slow and
large capacity. In addtion, link 6-8 is a bottleneck with smaller capacity
caused by a lane-drop. Links 3-5, 5-7, and 7-9 are arterial links with lower
free-flow speed than freeway links. Links 3-2, 4-5, 7-6, and 8-9 are on-ramp
or off-ramp connecting freeway links with arterial links. All the other links
are local streets connecting nodes with arterial links or freeway links.

We consider many-to-one OD pairs and each OD pair has a typical single-peak
demand pattern. Specifically, node 11 and node 12 are the origin nodes, while
node 15 is the destination node. At each time step, the demand follows a
Gaussian distribution
$q_{t}^{ge}\sim\mathcal{N}(\mu_{t}^{ge},\beta\mu_{t}^{ge})$, where
$\mu_{t}^{ge}$ is the historical mean demand of OD pair $ge$ at time $t$ and
$\beta=0.10$ is the demand uncertainty parameter. Between each OD pair, there
are multiple routes composed of freeway links and/or arterial links to choose
from.

In this network, we also consider a model mismatch between the actual system
dynamics ($\mathcal{M}$) that is unknown in practice, and the
approximated/estimated traffic model ($\tilde{\mathcal{M}}$). The network is
modeled by CTM, and CTM cells are defined by length, the number of lanes,
free-flow speed, capacity, and jam density. In the real world, the estimated
free-flow speed and capacity may differ from the actual unknown values, which
causes a model mismatch. In our experiments, we randomly set the free-flow
speed and capacity in the traffic model $\tilde{\mathcal{M}}$ to be 10-20%
higher or lower than those in the actual system dynamics $\mathcal{M}$ where
the online RL models are not offline trained by.

This scenario is more challenging than the 2-route network. First, there are
more links and routes than the 2-route network, so the state space and action
space are larger. Besides, some routes share the same links, which makes the
system dynamics more complicated. More importantly, a model mismatch exists,
so it’s more challenging for the model-based method (pre-DSO) and TransRL.

Figure 9: The synthetic corridor network

####  5.2.1 Training of reinforcement learning

The training processes of PPO and SAC are plotted in Figure 10. PPO was
struggling to find a reasonable policy and did not converge after 2000
episodes. While SAC converged after approximately 500 episodes, the
performance was pretty fluctuating even after the convergence. The performance
of PPO and SAC indicates the increase in state and action space makes model-
free reinforcement learning less efficient than learning from random
exploration.

TransRL with different unreliability parameters is also compared in Figure 10.
With various unreliability parameters, TransRL learned faster and reached a
more stable performance than PPO and SAC. Besides, comparing TransRL with
$\sigma=0.05$ and TransRL with $\sigma=0.10$, we can find TransRL with
$\sigma=0.05$ converged faster than TransRL with $\sigma=0.10$, but TransRL
with $\sigma=0.10$ ended with a slightly higher return than TransRL with
$\sigma=0.10$. This indicates a trade-off between the convergence speed and
the final performance. When $\sigma=0.20$, the TransRL was similar to SAC,
which supported Theorem 1 claiming SAC is equivalent to TransRL with a teacher
policy of uniform distribution (i.e., $\sigma=\infty$ in this case).

(a) TransRL with an unreliability parameter of 0.05

(b) TransRL with an unreliability parameter of 0.10

(c) TransRL with an unreliability parameter of 0.20

Figure 10: Training on the corridor network

####  5.2.2 Control performances of online tests

We tested trained RL and baselines for 100 test episodes with the same
uncertain demands and model mismatch. The resultant total travel time is
summarized in Table 3 and also plotted in Figure 9. Though demands and the
traffic model used in the model-based method (pre-DSO) are different from the
actual demands and actual system dynamics, pre-DSO outperformed both model-
free RL (SAC and PPO) in reducing total travel time. The average total travel
time of PPO was even higher than the no-control baseline.

With all three unreliability parameters, TransRL led to a lower average total
travel time than PPO and SAC. When the unreliability parameter $\sigma$ of
TransRL is 0.05 or 0.10, the average total travel time of TransRL was lower
than pre-DSO. When $\sigma=0.20$, the average total travel time of pre-DSO was
lower than TransRL. In summary, TransRL with $\sigma=0.10$ got the best
control performance. The results also indicate careful tuning of the
unreliability parameter can further enhance the performance of TransRL.

The reliability results of control methods on the corridor network are
included in Table 4. $\text{CTTRaR}_{x}$ of PPO and SAC are negative, which
means, in the worst cases, PPO and SAC perform worse than the no-control
baseline. Both pre-DSO and TransRL are reliable as $\text{CTTRaR}_{x}$ is
high. Interestingly, while TransRL ($\sigma=0.10$) leads to the lowest average
total travel time, TransRL ($\sigma=0.05$) is the most reliable. Results on
this network indicate that, even when model-free RL is not very reliable,
TransRL is still reliable because of the action constraints from the teacher
policy.

Table 3: Total travel time on the corridor network during 100 test episodes Total travel time | Average | SD
---|---|---
UE (no control) | 117540.56 | 1256.21
pre-DSO (model-based) | 113351.17 | 1347.67
PPO (model-free RL) | 128814.06 | 3152.06
SAC (model-free RL) | 116072.38 | 2720.69
TransRL ($\sigma=0.05$) | 112915.17 | 1357.93
TransRL ($\sigma=0.10$) | 112380.91 | 1550.75
TransRL ($\sigma=0.20$) | 115536.98 | 1769.41
Figure 11: Total travel time on the corridor network during 100 test episodes Table 4: $\text{CTTRaR}_{x}$ on the corridor network during 100 test episodes. The quantile $x$ is set to be 10%, which means the top 10% worst episodes. | $\text{CTTRaR}_{x}$
---|---
pre-DSO (model-based) | 4249.26
PPO (model-free RL) | -13089.30
SAC (model-free RL) | -2125.19
TransRL ($\sigma=0.05$) | 4418.89
TransRL ($\sigma=0.10$) | 3882.36
TransRL ($\sigma=0.20$) | 1357.70

###  5.3 A large network with uncertain demands and traffic model mismatch

The third network we experiment on is the Transportation Systems Management
and Operations (TSMO) # 1 network in Maryland, US. TSMO network contains a
freeway I-70 and multiple US routes. As Figure 12 shows, there are 621 links,
361 nodes, and 182 OD pairs on the TSMO network. During morning peak hours,
most travelers travel from west to east or south, and the eastbound of the
I-70 is recurrently congested.

To estimate the demands of the TSMO network, we adopted the Dynamic OD demand
Estimation (DODE) in [36] using historical count data within the TSMO network.
The DODE aims to solve dynamic demands to reproduce the link flows that match
the historical count data. After estimating the dynamic demands, we generate
demands using a Gaussian distribution
$q_{t}^{ge}\sim\mathcal{N}(\mu_{t}^{ge},\beta\mu_{t}^{ge})$, where
$\mu_{t}^{ge}$ is the estimated demand of OD pair $ge$ at time $t$ and
$\beta=0.10$ is the demand uncertainty parameter.

We consider two incident scenarios to evaluate the performances of the studied
methods with unexpected incidents. Specifically, the accessible (approximated)
traffic model $\tilde{\mathcal{M}}$ is the network without incidents, while
the actual system dynamics $\mathcal{M}$ is the network with unexpected
incidents. Note, except for the incident links, the other attributes of
$\tilde{\mathcal{M}}$ and $\mathcal{M}$ are assumed to be the same to
independently analyze the impacts of the incidents. The incident locations are
marked using stars as Figure 12 shows. Both incidents happen on the freeway,
and travelers cannot deviate from the incident location while observing the
incident. Therefore, the incidents on the freeway will cause a nontrivial
change in system dynamics. With the occurrence of incidents, we assume one
lane is blocked and the free-flow speed decreases on the incident link.

In our optimal traffic routing problem, we consider a practical setting, where
only a few links are observed and a few OD pairs are under control (e.g., the
flow among those OD pairs may be influenced by dynamic message signs or
naturally in a better geogrphic position to make route choices). More
specifically, the number of observed links is 14, and the observed links are
highlighted in Figure 12. Among 182 OD pairs, there are 14 OD pairs of which
flows can be influenced to re-route.

Figure 12: The TSMO network

####  5.3.1 Calibration of dynamic demands

Within the historical count data in the TSMO network, vehicles are classified
into cars and trucks, we adopted the multi-class dynamic OD demand estimation
(MCDODE) in [36] to estimate car demands and truck demands. The results of
MCDODE for the TSMO network are plotted in Figure 13. The loss shows the
MCDODE converged to a stable solution for both car data and truck data. The
scatter plots in Figure 13 compare the observed count data and the estimated
count data generated by the estimated demands. Most estimated data matched the
observed data pretty well. The data points where the estimated data is
significantly lower than the observed data can be attributed to the links
located in the marginal area. After the estimation of the demands, we convert
all vehicles into passenger car units (PCU) using passenger car equivalent
(PCE) for subsequent experiments.

(a) Loss for car count data

(b) Loss for truck count data

(c) Car count data

(d) Truck count data

Figure 13: DODE for the TSMO network

####  5.3.2 Training of reinforcement learning

The training processes of PPO, SAC, and TransRL in both incident scenarios are
compared in Figure 14. In incident scenario A, compared with SAC, PPO
converged faster and ended with higher returns. However, in incident scenario
B, SAC converged faster than PPO, and PPO could not converge after 1000
episodes. This suggests none of the two model-free RLs dominates with the
occurrence of unexpected incidents. On the other hand, TransRL converged
faster and reached higher returns than PPO and SAC. Besides, TransRL in
incident scenario A took more episodes to converge than TransRL in incident
scenario B. This may be due to incident A impacting the system dynamics more
significantly.

(a) Incident scenario A

(b) Incident scenario B

Figure 14: Training on the TSMO network

####  5.3.3 Control performances of online tests

The trained RL and pre-DSO were tested for 100 episodes with uncertain demands
in the two incident scenarios. The total travel time is summarized in Table 5
and plotted in Figure 15. The comparison between the model-based method (pre-
DSO) and the two model-free RLs (i.e., PPO and SAC) is ambiguous. In incident
scenario A, PPO and SAC led to lower total travel time than pre-DSO, and pre-
DSO even increased total travel time compared with the no-control case. In
incident scenario B, pre-DSO outperformed PPO and SAC. This suggests that,
under certain circumstances, incidents change the system dynamics so
significantly that the model-based method may not improve the system. In
contrast, TransRL outperformed pre-DSO, PPO, and SAC in both incident
scenarios. This is interesting. The performance of TransRL in incident
scenario A indicates that, even the model mismatch is non-trivial, TransRL is
able to uncover a good policy after exploration and learning.

Table 6 summarizes the reliability results. The reliability of model-free RL
and pre-DSO is mixed. While PPO is more reliable than pre-DSO in incident
scenario A, pre-DSO is more reliable than PPO in incident scenario B. In
contrast, TransRL is the most reliable in both incident scenarios.

Table 5: Total travel time on the TSMO network during 100 test episodes Scenario | Incident A | Incident B
---|---|---
Total travel time | Average | SD | Average | SD
UE (no control) | 129028.95 | 1932.23 | 141198.15 | 3058.50
pre-DSO (model-based) | 135113.66 | 2066.20 | 140529.34 | 3054.75
PPO (model-free RL) | 126579.58 | 2161.90 | 145846.63 | 3536.11
SAC (model-free RL) | 128485.32 | 2717.12 | 141805.64 | 3569.62
TransRL (ours) | 126506.81 | 2002.43 | 140072.43 | 2627.40

(a) Incident scenario A

(b) Incident scenario B

Figure 15: Total travel time on the TSMO network during 100 test episodes Table 6: $\text{CTTRaR}_{x}$ on the TSMO network during 100 test episodes. The quantile $x$ is set to be 10%, which means the top 10% worst episodes. | Incident A | Incident B
---|---|---
| $\text{CTTRaR}_{x}$ | $\text{CTTRaR}_{x}$
pre-DSO (model-based) | -6819.32 | 117.93
PPO (model-free RL) | 2871.87 | -3923.66
SAC (model-free RL) | -1466.95 | -2614.68
TransRL (ours) | 3216.34 | 1506.50

##  6 Conclusion

This paper studies real-time system optimal traffic routing problems in
general and sizable transportation networks with uncertainties. A small
portion of vehicles are assumed to follow routing guidances by a centralized
control algorithm. The objective of the control algorithm is to minimize the
total expected travel time of all vehicles within the transportation network.
We develop a novel RL model guided by a teacher policy that is derived
directly from transportation domain models. Considering the realism of RL
algorithms in real-world traffic operation, realistic testing scenarios are
developed to test RL algorithms where the actual demands are stochastic and
unknown, and there are model mismatches between the accessible traffic models
that offline train RL models and the actual and unknown system dynamics
testing RL models.

To incorporate the prior knowledge of the traffic models into RL, we proposed
a novel RL framework TransRL. The reward of TransRL is composed of 1) a reward
from the environment, and 2) a penalty reward that measures the distance
between the current policy and the teacher policy deriving from the traffic
model-based policy. An unreliability parameter is proposed to tune how much
TransRL is concentrated on the traffic model-based policy. The experiments
show that TransRL consistently outperforms the traffic model-based method and
model-free RLs in reducing total travel time. Moreover, the actions of TransRL
are more interpretable and reliable than model-free RLs.

We compare a traffic model-based RL with model-free RLs under different levels
of demand uncertainties and model mismatches. The experiments suggest the
traffic model-based RL, namely TransRL, performs well when the demand
uncertainty level is low or medium and the model mismatch is
mildlysignificant. Model-free RLs are agnostic to uncertain demands and system
dynamics, so their performances are consistent along different demand
uncertainties and model mismatches.

## Acknowledgement

This research is supported by US Department of Transportation Federal Highway
Administration’s Exploratory Advanced Research Award 693JJ321C000013. The
contents of this paper reflect the views of the authors only, who are
responsible for the facts and the accuracy of the information presented
herein.

## References

  * Acerbi and Tasche [2002] Carlo Acerbi and Dirk Tasche.  Expected shortfall: a natural coherent alternative to value at risk.  _Economic notes_ , 31(2):379–388, 2002.
  * Adler and Blue [2002] Jeffrey L Adler and Victor J Blue.  A cooperative multi-agent transportation management and route guidance system.  _Transportation Research Part C: Emerging Technologies_ , 10(5-6):433–454, 2002.
  * Adler et al. [2005] Jeffrey L Adler, Goutam Satapathy, Vikram Manikonda, Betty Bowles, and Victor J Blue.  A multi-agent approach to cooperative traffic management and route guidance.  _Transportation Research Part B: Methodological_ , 39(4):297–318, 2005.
  * Aerde and Case [1988] M Van Aerde and ER Case.  Individual driver route guidance systems and their implications for traffic control.  _Canadian Journal of Civil Engineering_ , 15(2):152–156, 1988.
  * Arnott et al. [1991] Richard Arnott, Andre De Palma, and Robin Lindsey.  Does providing information to drivers reduce traffic congestion?  _Transportation Research Part A: General_ , 25(5):309–318, 1991.
  * Bai et al. [2022] Zhengwei Bai, Peng Hao, Wei Shangguan, Baigen Cai, and Matthew J Barth.  Hybrid reinforcement learning-based eco-driving strategy for connected and automated vehicles at signalized intersections.  _IEEE Transactions on Intelligent Transportation Systems_ , 23(9):15850–15863, 2022.
  * Chan et al. [2019] Stephanie CY Chan, Samuel Fishman, John Canny, Anoop Korattikara, and Sergio Guadarrama.  Measuring the reliability of reinforcement learning algorithms.  _arXiv preprint arXiv:1912.05663_ , 2019.
  * Chen et al. [2018] Haipeng Chen, Bo An, Guni Sharon, Josiah Hanna, Peter Stone, Chunyan Miao, and Yeng Soh.  Dyetc: Dynamic electronic toll collection for traffic congestion alleviation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Chen et al. [2022] Jianyu Chen, Shengbo Eben Li, and Masayoshi Tomizuka.  Interpretable End-to-End Urban Autonomous Driving With Latent Deep Reinforcement Learning.  _IEEE Transactions on Intelligent Transportation Systems_ , 23(6):5068–5078, 2022.  ISSN 15580016.  doi: 10.1109/TITS.2020.3046646.
  * Chen et al. [2020] Zhibin Chen, Xi Lin, Yafeng Yin, and Meng Li.  Path controlling of automated vehicles for system optimum on transportation networks with heterogeneous traffic stream.  _Transportation Research Part C: Emerging Technologies_ , 110(November 2019):312–329, 2020.  ISSN 0968090X.  doi: 10.1016/j.trc.2019.11.017.  URL https://doi.org/10.1016/j.trc.2019.11.017.
  * Daganzo [1994] Carlos F Daganzo.  The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory.  _Transportation Research Part B: Methodological_ , 28(4):269–287, 1994.
  * Daganzo [1995] Carlos F Daganzo.  The cell transmission model, part ii: network traffic.  _Transportation Research Part B: Methodological_ , 29(2):79–93, 1995.
  * Do Chung et al. [2012] Byung Do Chung, Tao Yao, Terry L Friesz, and Hongcheng Liu.  Dynamic congestion pricing with demand uncertainty: A robust optimization approach.  _Transportation Research Part B: Methodological_ , 46(10):1504–1518, 2012.
  * Du et al. [2015] Lili Du, Lanshan Han, and Shuwei Chen.  Coordinated online in-vehicle routing balancing user optimality and system optimality through information perturbation.  _Transportation Research Part B: Methodological_ , 79:121–133, 2015.
  * Emmerink et al. [1996] Richard HM Emmerink, Peter Nijkamp, Piet Rietveld, and Jos N Van Ommeren.  Variable message signs and radio traffic information: An integrated empirical analysis of drivers’ route choice behaviour.  _Transportation Research Part A: Policy and Practice_ , 30(2):135–153, 1996.
  * Erke et al. [2007] Alena Erke, Fridulv Sagberg, and Rolf Hagman.  Effects of route guidance variable message signs (vms) on driver behaviour.  _Transportation Research Part F: Traffic Psychology and Behaviour_ , 10(6):447–457, 2007.
  * Fujimoto et al. [2018] Scott Fujimoto, Herke Hoof, and David Meger.  Addressing function approximation error in actor-critic methods.  In _International conference on machine learning_ , pages 1587–1596. PMLR, 2018.
  * Haarnoja et al. [2018] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al.  Soft actor-critic algorithms and applications.  _arXiv preprint arXiv:1812.05905_ , 2018.
  * Han et al. [2022a] Yu Han, Andreas Hegyi, Le Zhang, Zhengbing He, Edward Chung, and Pan Liu.  A new reinforcement learning-based variable speed limit control approach to improve traffic efficiency against freeway jam waves.  _Transportation Research Part C: Emerging Technologies_ , 144(September), 2022a.  ISSN 0968090X.  doi: 10.1016/j.trc.2022.103900.
  * Han et al. [2022b] Yu Han, Meng Wang, Linghui Li, Claudio Roncoli, Jinda Gao, and Pan Liu.  A physics-informed reinforcement learning-based strategy for local and coordinated ramp metering.  _Transportation Research Part C: Emerging Technologies_ , 137(February):103584, 2022b.  ISSN 0968090X.  doi: 10.1016/j.trc.2022.103584.  URL https://doi.org/10.1016/j.trc.2022.103584.
  * Haydari and Yilmaz [2022] Ammar Haydari and Yasin Yilmaz.  Deep Reinforcement Learning for Intelligent Transportation Systems: A Survey.  _IEEE Transactions on Intelligent Transportation Systems_ , 23(1):11–32, 2022.  ISSN 15580016.  doi: 10.1109/TITS.2020.3008612.
  * Jacob and Abdulhai [2006] Celine Jacob and Baher Abdulhai.  Automated adaptive traffic corridor control using reinforcement learning: Approach and case studies.  _Transportation Research Record_ , 1959(1):1–8, 2006.
  * Jayasooriya and Bandara [2017] SACS Jayasooriya and YMMS Bandara.  Measuring the economic costs of traffic congestion.  In _Engineering Research Conference (MERCon), 2017 Moratuwa_ , pages 141–146. IEEE, 2017.
  * Jin [2021] Wen-Long Jin.  A link queue model of network traffic flow.  _Transportation Science_ , 55(2):436–455, 2021.
  * Kachroo and Özbay [1998] Pushkin Kachroo and Kaan Özbay.  Solution to the user equilibrium dynamic traffic routing problem using feedback linearization.  _Transportation Research Part B: Methodological_ , 32(5):343–360, 1998.
  * Ke and Qian [2023] Zemian Ke and Sean Qian.  Leveraging ride-hailing services for social good: Fleet optimal routing and system optimal pricing.  _Transportation Research Part C: Emerging Technologies_ , 155:104284, 2023.
  * Ke et al. [2020] Zemian Ke, Zhibin Li, Zehong Cao, and Pan Liu.  Enhancing transferability of deep reinforcement learning-based variable speed limit control using transfer learning.  _IEEE Transactions on Intelligent Transportation Systems_ , 22(7):4684–4695, 2020.
  * Kullman et al. [2022] Nicholas D Kullman, Martin Cousineau, Justin C Goodson, and Jorge E Mendoza.  Dynamic ride-hailing with electric vehicles.  _Transportation Science_ , 56(3):775–794, 2022.
  * Lazar et al. [2021] Daniel A. Lazar, Erdem Bıyık, Dorsa Sadigh, and Ramtin Pedarsani.  Learning how to dynamically route autonomous vehicles on shared roads.  _Transportation Research Part C: Emerging Technologies_ , 130(June):103258, 2021.  ISSN 0968090X.  doi: 10.1016/j.trc.2021.103258.  URL https://doi.org/10.1016/j.trc.2021.103258.
  * Li et al. [2021] Zhenning Li, Hao Yu, Guohui Zhang, Shangjia Dong, and Cheng-Zhong Xu.  Network-wide traffic signal control optimization using a multi-agent deep reinforcement learning.  _Transportation Research Part C: Emerging Technologies_ , 125:103059, 2021.
  * Lighthill and Whitham [1955] Michael James Lighthill and Gerald Beresford Whitham.  On kinematic waves ii. a theory of traffic flow on long crowded roads.  _Proceedings of the royal society of london. series a. mathematical and physical sciences_ , 229(1178):317–345, 1955.
  * Lillicrap et al. [2015] Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_ , 2015.
  * Liu et al. [2020a] Jiepeng Liu, Pengkun Liu, Liang Feng, Wenbo Wu, Dongsheng Li, and Y Frank Chen.  Automated clash resolution for reinforcement steel design in concrete frames via q-learning and building information modeling.  _Automation in Construction_ , 112:103062, 2020a.
  * Liu et al. [2020b] Pengkun Liu, Jiepeng Liu, Liang Feng, Wenbo Wu, and Hao Lan.  Automated clash free rebar design in precast concrete exterior wall via generative adversarial network and multi-agent reinforcement learning.  In _Advances in Artificial Intelligence, Software and Systems Engineering: Proceedings of the AHFE 2019 International Conference on Human Factors in Artificial Intelligence and Social Computing, the AHFE International Conference on Human Factors, Software, Service and Systems Engineering, and the AHFE International Conference of Human Factors in Energy, July 24-28, 2019, Washington DC, USA 10_ , pages 546–558. Springer, 2020b.
  * Liu et al. [2023] Pengkun Liu, Hongtuo Qi, Jiepeng Liu, Liang Feng, Dongsheng Li, and Jingjing Guo.  Automated clash resolution for reinforcement steel design in precast concrete wall panels via generative adversarial network and reinforcement learning.  _Advanced Engineering Informatics_ , 58:102131, 2023.
  * Ma et al. [2020] Wei Ma, Xidong Pi, and Sean Qian.  Estimating multi-class dynamic origin-destination demand through a forward-backward algorithm on computational graphs.  _Transportation Research Part C: Emerging Technologies_ , 119:102747, 2020.
  * Messmer et al. [1998] Albert Messmer, Markos Papageorgiou, and Neil Mackenzie.  Automatic control of variable message signs in the interurban scottish highway network.  _Transportation Research Part C: Emerging Technologies_ , 6(3):173–187, 1998.
  * Mnih et al. [2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533, 2015.
  * Nie [2006] Yu Nie.  _A variational inequality approach for inferring dynamic origin-destination travel demands_.  PhD thesis, University of California, Davis, 2006.
  * Nie and Zhang [2010] Yu Marco Nie and H Michael Zhang.  Solving the dynamic user optimal assignment problem considering queue spillback.  _Networks and Spatial Economics_ , 10(1):49–71, 2010.
  * Pandey et al. [2020] Venktesh Pandey, Evana Wang, and Stephen D Boyles.  Deep reinforcement learning algorithm for dynamic pricing of express lanes with multiple access locations.  _Transportation Research Part C: Emerging Technologies_ , 119:102715, 2020.
  * Parvez Farazi et al. [2021] Nahid Parvez Farazi, Bo Zou, Tanvir Ahamed, and Limon Barua.  Deep reinforcement learning in transportation research: A review.  _Transportation Research Interdisciplinary Perspectives_ , 11(July):100425, 2021.  ISSN 25901982.  doi: 10.1016/j.trip.2021.100425.  URL https://doi.org/10.1016/j.trip.2021.100425.
  * Paz and Peeta [2009] Alexander Paz and Srinivas Peeta.  Behavior-consistent real-time traffic routing under information provision.  _Transportation Research Part C: Emerging Technologies_ , 17(6):642–661, 2009.
  * Pi and Qian [2017] Xidong Pi and Zhen Sean Qian.  A stochastic optimal control approach for real-time traffic routing considering demand uncertainties and travelers’ choice heterogeneity.  _Transportation Research Part B: Methodological_ , 104:710–732, 2017.
  * Prashanth and Bhatnagar [2010] LA Prashanth and Shalabh Bhatnagar.  Reinforcement learning with function approximation for traffic signal control.  _IEEE Transactions on Intelligent Transportation Systems_ , 12(2):412–421, 2010.
  * Qian and Zhang [2011] Zhen Qian and H Michael Zhang.  Computing individual path marginal cost in networks with queue spillbacks.  _Transportation Research Record_ , 2263(1):9–18, 2011.
  * Qian et al. [2012] Zhen Sean Qian, Wei Shen, and HM Zhang.  System-optimal dynamic traffic assignment with and without queue spillback: Its path-based formulation and solution via approximate path marginal cost.  _Transportation research part B: methodological_ , 46(7):874–893, 2012.
  * Qu et al. [2017] Xiaobo Qu, Jin Zhang, and Shuaian Wang.  On the stochastic fundamental diagram for freeway traffic: Model development, analytical properties, validation, and extensive applications.  _Transportation research part B: methodological_ , 104:256–271, 2017.
  * Richards [1956] Paul I Richards.  Shock waves on the highway.  _Operations research_ , 4(1):42–51, 1956.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms, 2017.
  * Singh et al. [2019] Ashutosh Singh, Abubakr Al-Abbasi, and Vaneet Aggarwal.  A reinforcement learning based algorithm for multi-hop ride-sharing: Model-free approach.  In _Neural Information Processing Systems (Neurips) Workshop_ , volume 36, 2019.
  * Sutton and Barto [1998] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_ , volume 1.  MIT press, 1998.
  * Tan and Gao [2018] Zhen Tan and H Oliver Gao.  Hybrid model predictive control based dynamic pricing of managed lanes with multiple accesses.  _Transportation Research Part B: Methodological_ , 112:113–131, 2018.
  * Toledo et al. [2015] Tomer Toledo, Omar Mansour, and Jack Haddad.  Simulation-based optimization of hot lane tolls.  _Transportation Research Procedia_ , 6:189–197, 2015.
  * Waller et al. [2001] S Travis Waller, Joseph L Schofer, and Athanasios K Ziliaskopoulos.  Evaluation with traffic assignment under demand uncertainty.  _Transportation Research Record_ , 1771(1):69–74, 2001.
  * Wang et al. [2001] Yibing Wang, Markos Papageorgiou, and Albert Messmer.  Feedback and iterative routing strategies for freeway networks.  In _Control Applications, 2001.(CCA’01). Proceedings of the 2001 IEEE International Conference on_ , pages 1162–1167. IEEE, 2001.
  * Watkins [1989] Christopher John Cornish Hellaby Watkins.  Learning from delayed rewards.  _PhD thesis, Cambridge University, Cambridge, England_ , 1989.
  * Wunderlich et al. [2000] Karl E Wunderlich, David E Kaufman, and Robert L Smith.  Link travel time prediction for decentralized route guidance architectures.  _IEEE Transactions on Intelligent Transportation Systems_ , 1(1):4–14, 2000.
  * Xu [2023] Te Xu.  _Boosting Max-Pressure Signal Control into Practical Implementation: Methodologies and Simulation Studies in City Networks_.  PhD thesis, University of Minnesota, 2023.
  * Xu et al. [2022] Te Xu, Simanta Barman, Michael W Levin, Rongsheng Chen, and Tianyi Li.  Integrating public transit signal priority into max-pressure signal control: Methodology and simulation study on a downtown network.  _Transportation Research Part C: Emerging Technologies_ , 138:103614, 2022.
  * Xu et al. [2024] Te Xu, Yashveer Bika, and Michael W Levin.  Ped-mp: A pedestrian-friendly max-pressure signal control policy for city networks.  _Journal of Transportation Engineering, Part A: Systems_ , 150(7):04024028, 2024.
  * Yang and Meng [1998] Hai Yang and Qiang Meng.  Departure time, route choice and congestion toll in a queuing network with elastic demand.  _Transportation Research Part B: Methodological_ , 32(4):247–260, 1998.
  * Yang et al. [2019] Mofeng Yang, Zhibin Li, Zemian Ke, and Meng Li.  A deep reinforcement learning-based ramp metering control framework for improving traffic operation at freeway weaving sections.  In _Proceedings of 98th Annual Meeting of Transportation Research Board_ , 2019.
  * Ye et al. [2019] Yingjun Ye, Xiaohui Zhang, and Jian Sun.  Automated vehicle’s behavior decision making using deep reinforcement learning and high-fidelity simulation environment.  _Transportation Research Part C: Emerging Technologies_ , 107:155–170, 2019.
  * Zhao et al. [2020] Ling Zhao, Zhibin Li, Zemian Ke, and Meng Li.  Fuzzy self-adaptive proportional–integral–derivative control strategy for ramp metering at distance downstream bottlenecks.  _IET Intelligent Transport Systems_ , 14(4):250–256, 2020.
  * Zhu et al. [2018] Meixin Zhu, Xuesong Wang, and Yinhai Wang.  Human-like autonomous car-following model with deep reinforcement learning.  _Transportation research part C: emerging technologies_ , 97:348–368, 2018.