[figure]capposition=top [table]capposition=top captionlabel caption

# Multi-Agent Soft Actor-Critic with Global Loss for Autonomous Mobility-on-
Demand Fleet Control

Zeno Woywood111Both authors contributed equally. School of Management,
Technical University of Munich, 80333 Munich<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Jasper I.
Wiltfang11footnotemark: 1 School of Management, Technical University of
Munich, 80333 Munich<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Julius Luy  School of Management,
Technical University of Munich, 80333 Munich<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Tobias Enders
School of Management, Technical University of Munich, 80333 Munich,
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Maximilian Schiffer  School of Management & Munich Data
Science Institute, Technical University of Munich, 80333 Munich, Germany
<EMAIL_ADDRESS>
###### Abstract

We study a sequential decision-making problem for a profit-maximizing operator
of an Autonomous Mobility-on-Demand system. Optimizing a central operator’s
vehicle-to-request dispatching policy requires efficient and effective fleet
control strategies. To this end, we employ a multi-agent Soft Actor-Critic
algorithm combined with weighted bipartite matching. We propose a novel
vehicle-based algorithm architecture and adapt the critic’s loss function to
appropriately consider global actions. Furthermore, we extend our algorithm to
incorporate rebalancing capabilities. Through numerical experiments, we show
that our approach outperforms state-of-the-art benchmarks by up to 12.9% for
dispatching and up to 38.9% with integrated rebalancing.
Keywords: hybrid learning and optimization, multi-agent learning, deep
reinforcement learning, global loss, autonomous mobility on demand

##  1 Introduction

Autonomous Mobility-on-Demand (AMoD) systems promise to further transform
urban mobility (Pavone 2015), following the lead of Mobility-on-Demand (MoD)
providers like Uber and DiDi. AMoD systems allow to offer MoD services with
fast response times and point-to-point trips at reduced cost, which changes an
operators objective: for MoD, operational costs often depend on hourly wages
paid to human drivers, such that operators prioritize revenue maximization;
for AMoD only distance-related operational costs remain such that operators
focus on optimizing profit (McKinsey & Co. 2023). Additionally, AMoD systems
allow for enhanced central control by leveraging historical trip information
and contextual knowledge to anticipatively control vehicels. In this context,
operators make two decisions: first, operators decide which customer requests
to accept and subsequently dispatch these to vehicles. Second, operators can
rebalance vehicles to align vehicle supply with anticipated customer demand.
These decisions lead to a stochastic control problem, which we study through
the lense of Deep Reinforcement Learning (DRL). In this context, we contribute
to the state of the art by introducing a novel parallel algorithm
architecture, which combines multi-agent DRL with combinatorial optimization
to ensure scalability and efficiency.

#### Related Work

Control algorithms for (A)MoD systems range from rule-based heuristics (see,
e.g., Hyland & Mahmassani 2018) to (learning-enriched) optimization approaches
(see, e.g., Alonso-Mora et al. 2017, Jungel et al. 2023), and Model Predictive
Control (MPC) (see, e.g., Iglesias et al. 2018), but are only loosely related
to this work as we focus on Reinforcement Learning (RL)-based approaches. RL-
based approaches split into two streams: single-agent approaches for
dispatching (Qin et al. 2020, Liu et al. 2022, Zheng et al. 2022) or
rebalancing (Fluri et al. 2019, Gammelli et al. 2021, Jiao et al. 2021), and
multi-agent approaches for dispatching (Wang et al. 2018, Xu et al. 2018, Li
et al. 2019, Tang et al. 2019, Zhou et al. 2019, Enders et al. 2023) and
rebalancing (Holler et al. 2019, Li et al. 2022, Liang et al. 2022). Here,
multi-agent approaches promise to increase scalability to larger action spaces
and remain the focus of our work. Accordingly, we limit our discussion to
recent works on multi-agent approaches in the following to ensure conciseness.

For dispatching, Li et al. (2019) proposed a mean field actor-critic
algorithm, while Tang et al. (2019) used a value-based approach with a
cerebellar embedding, and Zhou et al. (2019) used Q-Learning with KL-
divergence optimization. Enders et al. (2023) employed a Soft Actor-Critic
(SAC) with bipartite matching. Earlier methods (cf. Xu et al. 2018, Wang et
al. 2018) were shown to be less effective than at least one of the
aforementioned studies. For combined dispatching and rebalancing, Li et al.
(2022) used a graph neural network with a centralized critic for training, and
a decentralized actor-critic for execution. Holler et al. (2019) used Deep
Q-Networks and Proximal Policy Optimization with attention mechanisms to
process global states. Liang et al. (2022) proposed a two-stage algorithm for
dispatching and rebalancing using centralized programming. All methods treated
dispatching and rebalancing as sequential decisions. The objectives of these
works vary as some maximize revenue (Holler et al. 2019, Li et al. 2019, Tang
et al. 2019, Zhou et al. 2019), while others focus on profitability (Liang et
al. 2022, Enders et al. 2023).

Our work contributes to this stream of research as it is the first approach to
take integrated dispatching and rebalancing decisions in a multi-agent DRL
setting. More importantly, we are the first to show how to accurately derive a
global loss to estimate future state values when combining a multi-agent SAC
with a global optimization layer to coordinate decisions, which we achieve via
bipartite matching.

#### Contribution

To close the research gap outlined above, we present a novel multi-agent
actor-critic algorithm for AMoD fleet dispatching and integrated rebalancing
under a profit maximization objective. Specifically, we propose a scalable
parallel SAC architecture, wherein each vehicle functions as an agent
providing per-request weights, to address the operators’ need for a
comprehensive and feasible solution to its control problem. We obtain fleet-
wide (global) actions by solving a bipartite matching problem, wherein
vehicles and requests represent vertices, and the agents’ per-request weights
the edge weights. To account for the differences between per-agent and global
actions induced by the combination of DRL and a global optimization layer, we
show how to adapt the critic loss function to a global level (“global loss”)
leading to a more precise estimate of the value of future states. We show that
our algorithm outperforms state-of-the-art dispatching-only algorithms by up
to 12.9% on real-world datasets while maintaining stability and scalability.
We further extend our dispatching algorithm to include the concurrent option
of rebalancing by providing artificial rebalancing requests to the same model.
The extended algorithm achieves superior performance, up to 38.9%, compared to
a rebalancing heuristic. To foster future research and ensure reproducibility,
our code is publicly available on https://github.com/tumBAIS/HybridMADRL-AMoD-
Relocation.

##  2 Control Problem

We consider a stochastic multi-stage control problem introduced in Enders et
al. (2023), in which a profit-maximizing central operator manages a fleet of
$K$ vehicles to serve stochastic customer requests that enter the system over
time, see Figure 1. In each time step $t$, the operator decides on a batch of
requests $R_{t}$ that arrived in the system in between the last ($t-1$) and
the current time step $t$. For each request, the operator decides whether to
reject the request or assigns it to a vehicle. As the operator observes the
full fleet, it takes decisions based on complete state information, including
the pick-up and drop-off zones of requests in its operating area. We
characterize vehicles by their current position and a buffer of at most two
previously assigned requests that need to be served within a given maximum
waiting time. New requests join the system between two time steps and rejected
requests leave the system immediately.

Figure 1: Schematic visualization of vehicle dispatching (and rebalancing)
over time.

Vehicles take the shortest route to their next destination to either drop off
or pick up new customers. We determine the operator’s reward by the sum of
revenues from assigned requests minus operating costs for vehicle movements.
We extend this basic problem setting with a rebalancing decision, where the
operator can redistribute idling vehicles within the operating area to
proactively match vehicle supply and anticipated customer demand (see Section
3). For an extensive definition of the control problem, we refer to Appendix
A.

##  3 Methodology

Figure 2 gives an overview of our algorithm’s architecture. To derive an
efficient and scalable algorithm, we employ multi-agent SAC to keep the action
space tractable. In this algorithm’s architecture, vehicles represent agents,
which use the same actor neural network and share parameters for efficiency.
All agents evaluate all available requests and assign them a weight. We mask
these weights as described in Subsection C.3 to ensure feasibility
constraints, and create a weighted bipartite graph with vehicle agents and
requests representing vertices accordingly. We use this weighted matching,
which can be solved by applying the Hungarian algorithm (Kuhn 1955), to obtain
an optimal vehicle-to-request allocation, i.e., a coordinated (global) action
for all agents. During training, we use per-agent rewards to avoid a credit
assignment problem (Chang et al. 2003, Agogino & Tumer 2004). The critic
learns from these rewards and provides per-agent values to the actor to update
its policy. To train actor and critic, we use the discrete version of the SAC
algorithm, i.e., Soft Actor-Critic Discrete (SACD) (Haarnoja et al. 2018,
Christodoulou 2019). Our algorithm scales linearly with the number of requests
one agent has to evaluate. The employment of the SACD and the combination with
bipartite matching are analogous to the algorithm proposed in Enders et al.
(2023). Contrarily to Enders et al. (2023), we use a vehicle-based parallel
algorithm architecture, a novel masking procedure, an adapted critic loss
function, and finally extend our algorithm to include rebalancing.

#### Algorithm Architecture

We model each vehicle as an agent, see Figure 3. The agents’ neural network
architecture assesses each request based on the following input features:
miscellaneous features $m_{t}$ contain general environment information, which
is the same for all agents, e.g., the current time in the period; vehicle
features $v^{j}_{t}$ are agent-specific, e.g., the current position and the
request buffer; request features $r^{i}_{t}$ which we duplicate for all
agents, e.g., the origin and the destination. We combine all features to one
input-vector per vehicle and request. For the complete set of features, we
refer to Subsection C.1.

The actor assesses all currently available requests
$\mathbf{r}^{i}_{t}\,,i\in\\{1,\dots,R_{t}\\}$ for one vehicle in parallel. To
fix the input dimension of our agent’s neural network architecture, we pad the
evaluated requests to have a constant size of $R_{max}$. To facilitate more
simultaneous requests and speed-up computation for big instance sizes, one may
limit $R_{max}$ via a broadcasting range, which gives only the closest
requests to each vehicle. We add one additional empty request
$\mathbf{r}^{0}_{t}$ that the vehicle can choose if no request is appealing,
which indicates a reject action on the vehicle level.

We use a vehicle-based architecture as it enables the agents to build up
reward trajectories corresponding to their actions,

Figure 2: Overview of our algorithm’s architecture, highlighting actor
components (red), critic components (blue) and a combinatorial optimization
component (gray).

thereby fostering the learning process and accurate reward allocation.

Figure 3: Schematic visualization of our vehicle-based agent architecture in
which we combine input features to an input-vector (left) and use parallel
neural networks (right).

We consider each input-vector separately for the first five parallel dense
layers with identical parameters, essentially forming a trainable multi-layer
embedding. We stack the two-dimensional output tensor of the parallel layers
before flattening them to a one-dimensional vector, which we further evaluate
in five dense layers. The final softmax activation outputs values ranging from
0 to 1, which we interpret as per-request weights $w^{i}_{t}$. All agents
share one neural network architecture and parameters. The critic uses the same
algorithm architecture and features as the actor, but additionally receives
the global action as an input. For the detailed specifications of the
algorithm as well as the final hyperparameters, we refer to Appendix C.

#### Global Critic Loss SAC-Discrete

SAC is an off-policy algorithm that incentivizes exploration by finding an
optimal stochastic policy $\pi^{*}$ via a maximum entropy objective. To this
end, we parameterize the actor and critic network with parameters $\phi$ and
$\theta$. We use two critic networks $Q\in\\{Q^{1},Q^{2}\\}$ to mitigate
overestimation along with target networks with parameters $\bar{\theta}$ to
ensure a stable target. We obtain the target parameters through an exponential
moving average of the primary critic parameters $\theta$. In our multi-agent
setting, the policy loss matching our control problem is

$J_{\pi}(\phi)=\mathbb{E}_{(s,\bar{a},r,s^{\prime})\sim\mathcal{D}}\biggr{[}\sum_{j}\pi_{\phi}(a|s,j)^{T}\cdot\Bigl{(}\alpha\log(\pi_{\phi}(a|s,j))-\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a|s,j)\Bigl{\\}}\Bigl{)}\biggr{]}.$
(3.1)

Here, we denote a transition by $(s,\bar{a},r,s^{\prime})$, with global state
$s$, next global state $s^{\prime}$ and global action $\bar{a}$. We define
$r_{j}$ as the reward for agent $j$ and sample transitions from a replay
buffer $\mathcal{D}$. We define the policy’s entropy as
$\log(\pi_{\phi}(a|s,j))$, wherein $\alpha\in\mathbb{R}_{\geq 0}$ controls the
degree of exploration. We denote by $a$ the agent-specific action, i.e., a
reject or accept decision per request for vehicle $j$, and by $\gamma$ the
discount factor. Note that $\pi(a|s,j)$ represents the probability of vehicle
$j$ deciding for a specific request. Hence, it corresponds to the weights $w$
in Figure 3 (see Section 3), e.g., $\pi(a=r_{t}^{1}|s,j)=w_{t}^{1}$.

A state-of-the-art critic-loss for our setting is

$\displaystyle J_{Q}(\theta)$
$\displaystyle=\mathbb{E}_{(s,\bar{a},r,s^{\prime})\sim\mathcal{D}}\biggr{[}\sum_{j}\frac{1}{2}\biggl{(}Q_{\theta}(\bar{a}|s,j)-y_{j}\biggl{)}^{2}\biggr{]}\text{,
with }$ (3.2) $\displaystyle y_{j}$
$\displaystyle=r_{j}+\gamma\cdot\pi_{\phi}(a^{\prime}|s^{\prime},j)^{T}\cdot\Bigl{(}\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{\prime}|s^{\prime},j)\Bigl{\\}}-\alpha\log(\pi_{\phi}(a^{\prime}|s^{\prime},j))\Bigl{)}$

as proposed in Enders et al. (2023). As $\pi_{\phi}(a^{\prime}|s^{\prime},j)$
is the per-agent probability of taking per-agent action $a^{\prime}$ in the
next state, we refer to Equation 3.2 as a local loss. The local loss does not
accurately reflect the probability of agent $j$ executing $a^{\prime}$ given
$s^{\prime}$. The local loss is only accurate, if $a^{\prime}$ is executed
(cf. Subsection B.1). However, we derive the global action $\bar{a}$ from the
deterministic bipartite matching algorithm, which uses the masked actors’
outputs as edge weights. Each agent executes an action $a^{b}_{j}$ based on
$\bar{a}$ which differs from $a^{\prime}$ due to discrete assignments and
feasibility constraints. To obtain a critic loss function that accurately
reflects the global action, we define a modified
$\pi_{\phi}(a^{\prime}|s^{\prime},j)$, which we denote by
$\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)\in\\{0,1\\}$ that gets
$\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)=1$ if $a^{\prime}=a^{b}_{j}$ and
zero otherwise. Note that the distribution of $\bar{\pi}$ is degenerate as its
support reduces to $a^{b}_{j}$. We use the modified
$\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)$ to derive a new target $y_{j}$.

######  Proposition 1.

Let us denote by $\bar{y}_{j}$ the per-agent target based on
$\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)$. Then,

$\bar{y}_{j}=r_{j}+\gamma\,\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{b}_{j}|s^{\prime},j)\Bigl{\\}}.$
(3.3)

For a proof of Proposition 1, we refer to Appendix B. The adjusted critic loss
function now reads

$\displaystyle J_{Q}(\theta)$
$\displaystyle=\mathbb{E}_{(s,\bar{a},r,s^{\prime})\sim\mathcal{D}}\biggr{[}\sum_{j}\frac{1}{2}\biggl{(}Q_{\theta}(\bar{a}|s,j)-\bar{y}_{j}\biggl{)}^{2}\biggr{]}.$
(3.4)

and reflects a global loss, as we compute the critic loss using the agent-
specific action which we derived from the global action $\bar{a}$. Herein, we
obtain $\bar{y}_{j}$ according to Equation 3.3. The actor loss does not
require adaptation as it learns from the critic’s predictions, which, in turn,
already result from the correct updates based on Equation 3.4.

#### Integrated Dispatching and Rebalancing

To integrate rebalancing in our algorithm’s architecture, we extend the actor
to assess further input-vectors representing possible rebalancing actions.
Hence, we employ artificial requests to imitate rebalancing as a dispatching
decision (see Figure 1). To achieve this, we model rebalancing movements as
requests from the vehicle’s current position to other zones in the operating
area. In each time step, a vehicle assesses a fixed number of rebalancing
requests. The vehicle can only rebalance if the vehicle idles. The integrated
approach extends variable customer requests $\mathcal{C}_{t}$ with time-
persistent (re-)balancing requests $\mathcal{B}$. This leads to a new set of
evaluated requests $\mathcal{R}_{t}=\mathcal{C}_{t}\cup\mathcal{B}$. To
enforce solely reasonable rebalancing movements, two rebalancing variants
impact the generation of vehicle-specific rebalancing requests
$\mathcal{B}_{t}^{j}$:  (i) each vehicle can rebalance to every zone, except
its own,  (ii) each vehicle can rebalance to its neighboring zones  . To
leverage knowledge about the environment and enhance training, we alter the
training rewards of rebalancing actions. The agent receives a fare (positive
or negative) depending on the vehicle population of the current and the target
zone. We refer to Subsection C.4 for further details on the rebalancing
requests and their training rewards.

##  4 Experimental Design

We use the well-established NYC Taxi dataset (TLC 2015) to benchmark our model
against state-of-the-art algorithms. We employ a hexagonal grid for spatial
discretization to balance real-world similarity with computational efficiency
and differentiate two settings: a smaller 11 zone (larger 38 zone) setting
with $500\text{\,}\mathrm{m}$ ($1000\text{\,}\mathrm{m}$) distance between
adjacent zones in lower Manhattan. For the 11 small zones, we use the dataset
without modifications. In the case of the 38 large zones, we apply a
downscaling factor of 20 to reduce the number of requests, ensuring a
comparable fleet size assessment in both scenarios. We consider daily one-hour
intervals as episodes, spanning from 8:30 to 9:30 a.m. with a time step size
of one minute. Throughout the year 2015, excluding holidays and weekends, we
include a total of 245 dates, using 200 for training, 25 for validation, and
20 for testing purposes. We configure the waiting time to be 5 (10) minutes.
The cost parameter determines the cost per distance driven and is set to make
round trips profitable with a 20% margin.

We consider two experiments: pure dispatching as well as integrated
dispatching and rebalancing. For the experiment with pure dispatching, we
model instances with supply shortage, as operators in dispatching scenarios
with infinite supply can fulfill any request immediately, making a myopic
policy sufficient. Thus, we set a maximum of 12 (20) requests per time step
and deploy 12 (50) vehicles. For the experiment integrating dispatching and
rebalancing, we model a supply overhang as rebalancing is only valuable if
vehicles idle. For the 38 large zones, we generate rebalancing requests to
neighboring zones only (see Subsection D.3). Thus, we set a maximum of 6 (10)
requests per time step and deploy 24 (120) vehicles. We add a constraint that
requires vehicles to be in the zone or en route to the origin zone of the
request to foster rebalancing further. Moreover, we study the sensitivity
w.r.t. the number of vehicles by considering additional instances with
$\pm\,50\%$ vehicles. Finally, we create an additional dataset by shifting the
originally rather homogeneous and well-balanced NYC Taxi dataset towards an
imbalanced request distribution. The modified dataset has one (two) distinct
clusters of departing customers, and we refer to it as “Clustered” hereafter.
For details on the setup, evaluated scenarios, and hyperparameters we refer to
Appendix D.

In the first experiment, we denote by $V_{\mathrm{local}}$ our algorithm using
a local critic loss function (cf. Equation 3.2) and by $V_{\mathrm{global}}$
our algorithm using a global critic loss function (cf. Equation 3.4). We
benchmark our dispatching performance against two algorithms: an algorithm
using request-vehicle combinations as in Enders et al. (2023) (RVC) and a
greedy policy (Greedy). The Greedy algorithm weighs every request according to
its profitability before matching. Second, we show the capabilities of our
integrated dispatching and rebalancing algorithm by extending
$V_{\mathrm{global}}$ with rebalancing ($V_{\mathrm{extended}}$). Here, we
benchmark against Greedy, our algorithm without rebalancing and a rebalancing
heuristic (Heuristic) that distributes the number of vehicles per zone
equally. For a detailed description of all benchmarks, see Subsection D.2.

##  5 Results and Discussion

#### Dispatching

Figure 4 shows the validation results of all four algorithms for dispatching.
RVC and $V_{\mathrm{global}}$ exhibit a stable performance throughout training
in both settings. RVC converges to the same reward as Greedy, while
$V_{\mathrm{global}}$ converges to a significantly higher reward. The
validation results of $V_{\mathrm{local}}$ show stability issues, especially
for 38 zones. For the larger setting, $V_{\mathrm{global}}$ requires more
training steps until convergence as the complexity rises with more vehicles
and requests. The validation reward across training episodes of
$V_{\mathrm{local}}$ demonstrates that our algorithm exhibits a high variance
and a convergence below Greedy, when neglecting the global critic loss
function. These observations show that the work of Enders et al. (2023)
improves stability and performance by employing one agent per request-vehicle
combination, which improves performance even when using a local loss. While a
vanilla implementation of our parallel vehicle-based algorithm is inferior to
such an approach, utilizing our algorithm with a global critic loss allows for
significant improvements as the combination of a global critic loss and a
vehicle-based agent representation better reflects problem dynamics and
consequently eases the learning.

Figure 4: Average validation rewards of all four algorithms on both NYC
settings. The shadowed area is the minimum and maximum value across 5 seeds.

Table 2 and Figure 5 show each algorithm’s improvement in test performance
compared to Greedy corresponding to the validation results in Figure 4.
$V_{\mathrm{global}}$ outperforms Greedy significantly, RVC exhibits a test
result close to Greedy and $V_{\mathrm{local}}$ performs worse than Greedy.
The strong performance of $V_{\mathrm{global}}$ highlights the significance of
employing a global critic loss. By contrast, the low performance of
$V_{\mathrm{local}}$ indicates that the error from using a local loss function
substantially hinders the search for a stable and performant policy, which
increases with a higher number of vehicles. RVC evaluates one request-vehicle
combination at a time effectively splitting the vehicle into multiple agents.
Thus, RVC lacks the ability to perform anticipatory planning for individual
vehicle routes as request-vehicle combinations only exist in the current time
step. Consequently, RVC inadequately accounts for the subsequent state
$s\textquoteright$ and the error resulting from bipartite matching, as it
employs the current state for target retrieval, leading to a biased estimate
that does not accurately predict the future state, yielding near Greedy
results.

Figure 5: Test performances for dispatching (0% indicates equal performance to
Greedy). Each dot represents the average of one test date across 5 seeds.

Table 1: Performance improvement to Greedy for dispatching across 5 seeds. Algo. | 11 small | 38 large
---|---|---
Greedy | 350.9 | 1529.5
RVC | $+1.9\%$ | $-1.1\%$
$V_{\mathrm{local}}$ | $-4.8\%$ | $-21.0\%$
$V_{\mathrm{global}}$ |  +12.9% |  +12.9%

Table 2: Structural comparison of different algorithms on the 11 small zones setting (average across 5 seeds). Metric | Greedy | RVC | $V_{\mathrm{global}}$
---|---|---|---
Rejects to empty (%) | 18.3 | 18.2 | 44.7
Rejects to occupied (%) | 19.2 | 19.8 | 49.9
Pick-up distance (zones) | 2.4 | 2.4 | 0.2
Waiting time (min) | 3.8 | 3.7 | 2.5

Our vehicle-based architecture, on the other hand, is able to form a reward
trajectory which is necessary for long-term planning. As the algorithm
evaluates all requests and receives a reward corresponding to only its
actions, it gains a correct estimate of the next state’s value and can
therefore optimize its subsequent dispatching decisions.

To analyze the algorithms’ policies, we compare the metrics presented in Table
2 for profitable requests, i.e., requests for which the fare is higher than
the vehicle-specific distance cost and which can be fulfilled within the
waiting time. The metric “rejects to empty” considers empty zones as
destination and “rejects to occupied” counting zones with more than one
vehicle located at the destination. We divide both metrics by the total number
of requests to retrieve their ratio. The “pick-up distance” presents the
distance driven to the pick-up zone from the current destination of the
vehicle. Lastly, the “waiting time” is the average time a customer waits until
pick-up. Greedy and RVC behave similarly, but $V_{\mathrm{global}}$ rejects
with 44.7% more than double the amount of profitable requests, keeps waiting
times shorter and reduces pick-up distance by a factor of ten. Hence,
$V_{\mathrm{global}}$ learns a different policy in two ways. First, it better
utilizes implicit rebalancing by preferring requests that allow heading
towards empty zones over requests ending in occupied zones. Second, it rejects
more low-profit requests to wait for those with higher profits, particularly
favoring requests starting in the vehicle’s current zone as indicated by the
low pick-up distance. This leads to lower waiting times, as future customers
rarely have to wait until the vehicle arrives at their location. Such a policy
proves effective in instances with supply shortages, where the opportunity
cost of rejecting requests is low.

#### Integrated Dispatching and Rebalancing

Figure 6 shows the improvement in test performance compared to Greedy for
integrated dispatching and rebalancing. $V_{\mathrm{global}}$ performs close
to Greedy in all settings, whereas Heuristic and $V_{\mathrm{extended}}$
perform significantly better than Greedy especially on the Clustered dataset.
The low performance improvement of $V_{\mathrm{global}}$ compared to
dispatching-only bases on the oversupply of vehicles in the tested instances,
for which Greedy is inherently strong. Note that for the Clustered dataset,
Heuristic and $V_{\mathrm{extended}}$ are able to outperform Greedy by 96.2%
(51.3%) and 101.0% (111.5%) respectively. Thus, our algorithm performs 39.8%
better than Heuristic on the larger setting, but only 1.3% on the smaller one.
The result of Heuristic for the smaller setting indicates that the rule-based
rebalancing policy matches the distribution and frequency of requests for this
instance size well.

Furthermore, we explore the sensitivity of varying number of vehicles on
operator returns, see Table 3. Notably,

Figure 6: Test performances on both scenarios and datasets for integrated
dispatching and rebalancing compared to Greedy. Each dot represents the
average of one test date across 5 seeds.

our algorithm $V_{\mathrm{extended}}$ demonstrates an overall increasing

| Zones | 11 small zones | 38 large zones
---|---|---|---
Setting |  Algo. | $K$ | #12 | #24 | #36 | #60 | #120 | #180
NYC | Greedy | 297.3 | 418.3 | 479.6 | 1594.4 | 2282.7 | 2674.1
$V_{\mathrm{global}}$ | $+2.0\%$ | $+1.7\%$ | $+1.6\%$ | $+1.4\%$ | $+1.0\%$ | $+0.7\%$
Heuristic | $+6.4\%$ | $+14.2\%$ | $+10.6\%$ | $+5.6\%$ | $+8.3\%$ | $+8.4\%$
$V_{\mathrm{extended}}$ |  +9.9% |  +20.0% |  +21.3% |  +6.4% |  +12.3% |  +10.1%
Clustered | Greedy | 137.2 | 198.8 | 241.8 | 429.3 | 688.5 | 882.6
$V_{\mathrm{global}}$ | +1.2% | +3.1% | +0.8% | +1.4% | +1.0% | +0.7%
Heuristic | +74.1% | +96.2% | +70.5% | +66.5% | +51.3% | +48.6%
$V_{\mathrm{extended}}$ |  +85.6% |  +101.0% |  +96.7% |  +107.7% |  +111.5% |  +106.4%
Table 3: Performance improvement to Greedy for dispatching and rebalancing to
compare the impact of varying numbers of vehicles $K$ (ceteris paribus) across
5 seeds.

relative performance improvement in comparison to Heuristic as the number of
vehicles rises. This supports the scalability of our algorithm and indicates
that $V_{\mathrm{extended}}$ effectively capitalizes on past experiences,
anticipating future requests and incorporating the spatial distribution,
especially for the Clustered dataset. Determining the optimal fleet size is
imperative for operators aiming to maximize their profits gained from their
rebalancing policy. When the fleet size is small, the degree of freedom to
improve is also small. When the fleet size is excessively large, rebalancing
becomes less profitable in relative terms as Greedy becomes sufficient.

##  6 Conclusion

This work addresses the fleet control problem of a profit-maximizing AMoD
operator and offers a comprehensive solution, including the implementation
code. We solve the dispatching problem by proposing a novel multi-agent SACD
architecture, in which each agent first evaluates requests in parallel and
combines them afterwards for a vehicle-based output. Thus, our algorithm
ensures computational efficiency while optimizing its reward trajectory
through long-term planning. To obtain global actions from agent actions, we
employ weighted bipartite matching. We show an error in the critic’s loss
function and propose an adaptation of the critic’s target to accommodate the
bipartite matching. By adjusting the critic loss function to a global loss, we
obtain a more accurate estimate of the next state’s value fostering the
learning process of our agent. Additionally, we extend our dispatching
algorithm by incorporating concurrent rebalancing capabilities. Experimental
results show that our approach surpasses state-of-the-art benchmarks while
demonstrating stability across different instances. For dispatching, we
outperform the closest benchmark by up to 12.9% and for integrated dispatching
and rebalancing by up to 38.9%. In future work, we will extend the AMoD fleet
control problem by covering charging and investigate how the adaptation to a
global critic loss function impacts the performance of DRL models with
combinatorial optimization in other competitive multi-agent instances.

## References

  * Agogino & Tumer (2004) Agogino, A. K., & Tumer, K. (2004).  Unifying temporal and structural credit assignment problems.  In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 2 (p. 980–987).
  * Alonso-Mora et al. (2017) Alonso-Mora, J., Samaranayake, S., Wallar, A., Frazzoli, E., & Rus, D. (2017).  On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment.  Proceedings of the National Academy of Sciences, (pp. 462–467).
  * Bösch et al. (2018) Bösch, P. M., Becker, F., Becker, H., & Axhausen, K. W. (2018).  Cost-based analysis of autonomous mobility services.  Transport Policy, 64, 76–91.
  * Chang et al. (2003) Chang, Y.-h., Ho, T., & Kaelbling, L. (2003).  All learning is local: Multi-agent learning in global reward games.  In Advances in Neural Information Processing Systems (pp. 1–8).
  * Christodoulou (2019) Christodoulou, P. (2019).  Soft actor-critic for discrete action settings.  CoRR, abs/1910.07207. URL: http://arxiv.org/abs/1910.07207. arXiv:1910.07207.
  * Enders et al. (2023) Enders, T., Harrison, J., Pavone, M., & Schiffer, M. (2023).  Hybrid multi-agent deep reinforcement learning for autonomous mobility on demand systems.  In Proceedings of The 5th Annual Learning for Dynamics and Control Conference (pp. 1284--1296).
  * Fluri et al. (2019) Fluri, C., Ruch, C., Zilly, J., Hakenberg, J., & Frazzoli, E. (2019).  Learning to operate a fleet of cars.  In 2019 IEEE Intelligent Transportation Systems Conference (ITSC) (pp. 2292--2298).
  * Gammelli et al. (2021) Gammelli, D., Yang, K., Harrison, J., Rodrigues, F., Pereira, F. C., & Pavone, M. (2021).  Graph neural network reinforcement learning for autonomous mobility-on-demand systems.  In 2021 60th IEEE Conference on Decision and Control (CDC) (pp. 2996--3003).
  * Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Abbeel, P., & Levine, S. (2018).  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In Proceedings of the 35th International Conference on Machine Learning (pp. 1861--1870).
  * Holler et al. (2019) Holler, J., Vuorio, R., Qin, Z., Tang, X., Jiao, Y., Jin, T., Singh, S., Wang, C., & Ye, J. (2019).  Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem.  In 2019 IEEE International Conference on Data Mining (ICDM) (pp. 1090--1095).
  * Hyland & Mahmassani (2018) Hyland, M., & Mahmassani, H. S. (2018).  Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign avs to immediate traveler demand requests.  Transportation Research Part C: Emerging Technologies, (pp. 278--297).
  * Iglesias et al. (2018) Iglesias, R., Rossi, F., Wang, K., Hallac, D., Leskovec, J., & Pavone, M. (2018).  Data-driven model predictive control of autonomous mobility-on-demand systems.  In 2018 IEEE International Conference on Robotics and Automation (ICRA) (p. 1–7).
  * Iqbal & Sha (2019) Iqbal, S., & Sha, F. (2019).  Actor-attention-critic for multi-agent reinforcement learning.  In Proceedings of the 36th International Conference on Machine Learning (pp. 2961--2970).
  * Jiao et al. (2021) Jiao, Y., Tang, X., Qin, Z., Li, S., Zhang, F., Zhu, H., & Ye, J. (2021).  Real-world ride-hailing vehicle repositioning using deep reinforcement learning.  Transportation Research Part C: Emerging Technologies, (p. 103289).
  * Jungel et al. (2023) Jungel, K., Parmentier, A., Schiffer, M., & Vidal, T. (2023).  Learning-based online optimization for autonomous mobility-on-demand fleet control.  URL: https://arxiv.org/abs/2302.03963. doi:10.48550/ARXIV.2302.03963.
  * Kuhn (1955) Kuhn, H. W. (1955).  The Hungarian Method for the Assignment Problem.  Naval Research Logistics Quarterly, (pp. 83--97).
  * Kullman et al. (2022) Kullman, N. D., Cousineau, M., Goodson, J. C., & Mendoza, J. E. (2022).  Dynamic ride-hailing with electric vehicles.  Transportation Science, 56, 775--794.
  * Li et al. (2022) Li, B., Ammar, N., Tiwari, P., & Peng, H. (2022).  Decentralized ride-sharing of shared autonomous vehicles using graph neural network-based reinforcement learning.  In 2022 International Conference on Robotics and Automation (ICRA) (pp. 912--918).
  * Li et al. (2019) Li, M., Qin, Z., Jiao, Y., Yang, Y., Wang, J., Wang, C., Wu, G., & Ye, J. (2019).  Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning.  In The World Wide Web Conference (p. 983–994).
  * Liang et al. (2022) Liang, E., Wen, K., Lam, W. H. K., Sumalee, A., & Zhong, R. (2022).  An integrated reinforcement learning and centralized programming approach for online taxi dispatching.  IEEE Transactions on Neural Networks and Learning Systems, (pp. 4742--4756).
  * Liu et al. (2022) Liu, Z., Li, J., & Wu, K. (2022).  Context-aware taxi dispatching at city-scale using deep reinforcement learning.  IEEE Transactions on Intelligent Transportation Systems, (pp. 1996--2009).
  * Lowe et al. (2017) Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., & Mordatch, I. (2017).  Multi-agent actor-critic for mixed cooperative-competitive environments.  In Advances in Neural Information Processing Systems (pp. 1--12).
  * McKinsey & Co. (2023) McKinsey & Co. (2023).  Where does shared autonomous mobility go next?  URL: https://www.mckinsey.com/industries/automotive-and-assembly/our-insights/where-does-shared-autonomous-mobility-go-next#/.
  * Pavone (2015) Pavone, M. (2015).  Autonomous mobility-on-demand systems for future urban mobility.  In M. Maurer, J. C. Gerdes, B. Lenz, & H. Winner (Eds.), Autonomes Fahren: Technische, rechtliche und gesellschaftliche Aspekte (pp. 399--416).  Springer Berlin Heidelberg.
  * Qin et al. (2020) Qin, Z., Tang, X., Jiao, Y., Zhang, F., Xu, Z., Zhu, H., & Ye, J. (2020).  Ride-hailing order dispatching at didi via reinforcement learning.  INFORMS Journal on Applied Analytics, (p. 272–286).
  * Tang et al. (2019) Tang, X., Qin, Z., Zhang, F., Wang, Z., Xu, Z., Ma, Y., Zhu, H., & Ye, J. (2019).  A deep value-network based approach for multi-driver order dispatching.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (p. 1780–1790).
  * TLC (2015) TLC, N. (2015).  Trip record data.  URL: https://www.nyc.gov/site/tlc/about/tlc-trip-record-data.page.
  * Wang et al. (2018) Wang, Z., Qin, Z., Tang, X., Ye, J., & Zhu, H. (2018).  Deep reinforcement learning with knowledge transfer for online rides order dispatching.  In 2018 IEEE International Conference on Data Mining (ICDM) (pp. 617--626).
  * Xu et al. (2018) Xu, Z., Li, Z., Guan, Q., Zhang, D., Li, Q., Nan, J., Liu, C., Bian, W., & Ye, J. (2018).  Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (p. 905–913).
  * Zheng et al. (2022) Zheng, B., Ming, L., Hu, Q., Lü, Z., Liu, G., & Zhou, X. (2022).  Supply-demand-aware deep reinforcement learning for dynamic fleet management.  ACM Trans. Intell. Syst. Technol., (pp. 1--19).
  * Zhou et al. (2019) Zhou, M., Jin, J., Zhang, W., Qin, Z., Jiao, Y., Wang, C., Wu, G., Yu, Y., & Ye, J. (2019).  Multi-agent reinforcement learning for order-dispatching via order-vehicle distribution matching.  In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (p. 2645–2653).

##  Appendix A Control Problem

In the following, we detail our control problem, which we adapted from Enders
et al. (2023). We focus on a profit-maximizing central operator that manages a
(possibly autonomous) vehicle fleet with a fixed number of vehicles to serve
stochastic customer requests. The operator needs to make decisions immediately
as customers demand immediate feedback. Hence, shifting rejected requests into
the next time step is not possible. After the operator accepts a request, a
customer must be picked up within a given maximum waiting time
$\omega^{\mathrm{max}}\in\mathbb{N}_{0}$, and the operator needs to dispatch a
vehicle to fulfill the request accordingly.

We extend this basic dispatching problem setting with a rebalancing decision,
where the operator can redistribute idling vehicles within the operating area.
We formalize the control problem as a Markov Decision Process (MDP), which we
describe in the following:

Preliminaries: We consider discrete time steps $t$ within a given time horizon
$\mathcal{T}=\\{0,1,\dots,T\\}$, and represent the grid-based operating area
as a graph $G=(\mathcal{V},\mathcal{E})$ with weight vectors
${}^{e}w=({}^{e}w^{d},{}^{e}w^{t})\in\mathbb{R}_{>0}\times\mathbb{N}$,
denoting the distance $({}^{e}w^{d})$ and the number of time steps
$({}^{e}w^{t})$ required to traverse an edge $e\in\mathcal{E}$. Vertices
$v\in\mathcal{V}$ represent the centers of zones in the operating area. The
neighbors of a vertex $v$ are denoted by
$\mathcal{N}_{G}(v)=\\{u\;|\;(u,v)\in\mathcal{E}\\}$.

States: We denote the system state at time step $t\in\mathcal{T}$ by
$\mathbf{S}_{t}=(t,(\mathbf{k}_{t}^{j})_{j\in\\{1,\dots,K\\}},(\mathbf{r}_{t}^{i})_{i\in\\{1,\dots,R_{t}\\}})$,
with $K$ representing the number of vehicles $\mathbf{k}_{t}^{j}$,
$j\in\\{1,\dots,K\\}$ and $R_{t}$ being the number of new requests
$\mathbf{r}_{t}^{i}$, $i\in\\{1,\dots,R_{t}\\}$.

We describe vehicles $\mathbf{k}=(p,\tau,{}^{1}\mathbf{r},{}^{2}\mathbf{r})$,
with a position $p\in\mathcal{V}$, a number of time steps
$\tau\in\mathbb{N}_{0}$ left to reach this position and a vehicle-specific
request buffer ${}^{1}\mathbf{r},{}^{2}\mathbf{r}$. Here, $p$ can either be
the current vertex for an idling vehicle or the next vertex on the vehicle’s
route if it is traveling. To account for realistic trip lengths and maximum
waiting times, we restrict the number of requests preassigned to a vehicle to
two. An idling vehicle is characterized by an empty request buffer, i.e.,
${}^{1}\mathbf{r}=\emptyset$ as the request buffer fills up in a first-in-
first-out fashion. We label the position of vehicle $\mathbf{k}_{t}^{j}$ as
$p_{t}^{j}$ and label the other attributes of the vehicle in the same
notation.

The set $\mathcal{R}_{t}=\mathcal{C}_{t}\cup\mathcal{B}$ contains all
available requests in time step $t$ with $R_{t}=|\mathcal{R}_{t}|$, incl.
variable customer requests $\mathcal{C}_{t}$ and time-persistent
(re-)balancing requests $\mathcal{B}$. If the operator does not allow vehicle
rebalancing, no rebalancing requests are available, i.e.,
$\mathcal{B}=\emptyset$ and $\mathcal{R}_{t}=\mathcal{C}_{t}$. We describe
requests $\mathbf{r}=(\omega,o,d)$ with a waiting time
$\omega\in\mathbb{N}_{0}\,\cup\,\emptyset$ tracking the elapsed time from
request placement to pick-up, an origin $o\in\mathcal{V}$, and a destination
$d\in\mathcal{V}$. To enable the representation of customer and rebalancing
requests based on the triplet $\mathbf{r}=(\omega,o,d)$, rebalancing requests
obtain an empty waiting time ($\omega=\emptyset$) and an origin corresponding
to their destination ($o=d$).

To allow for rebalancing, one creates an artificial set of rebalancing
requests $\mathcal{B}=\\{(\emptyset,v,v)\;|\;v\;\forall\;\mathcal{V}\\}$ to
consider all vertices as rebalancing destinations. Moreover, the operator
cannot rebalance multiple vehicles to the same zone in one time step, as we
create only one rebalancing request for each zone. However, one can easily
relax this constraint by creating multiple rebalancing requests for each zone.
To reduce the possible action space and enforce solely reasonable rebalancing
movements, we define a vehicle-specific rebalancing request set. We consider
two variants to obtain this set for individual vehicles that permit equivalent
rebalancing behavior:

  1. (i)

each vehicle $j$ can rebalance to every zone, except its own, i.e.,
$\mathcal{B}_{t}^{j}=\\{(\emptyset,v,v)\;|\;v\;\forall\;\mathcal{V}\setminus
p_{t}^{j}\\}$,

  2. (ii)

each vehicle $j$ can rebalance to its neighboring zones, i.e.,
$\mathcal{B}_{t}^{j}=\\{(\emptyset,v,v)\;|\;v\;\forall\;N_{G}(p_{t}^{j})\\}$.

This leads to a new set of evaluated requests per vehicle
$\mathcal{C}_{t}\cup\mathcal{B}_{t}^{j}$.

Actions: The action space of the central operator reads

$\begin{split}\mathcal{A}(\mathbf{S}_{t})=\biggl{\\{}\Big{(}a_{t}^{1},\dots,a_{t}^{R_{t}}\Big{)}\;\Big{|}\;&a_{t}^{i}=0\;\lor\\\
&(a_{t}^{i}=j\land{}^{2}\mathbf{r}_{t}^{j}=\emptyset\land\mathbf{r}_{t}^{i}\in\mathcal{C}_{t})\;\lor\\\
&(a_{t}^{i}=j\land{}^{1}\mathbf{r}_{t}^{j}=\emptyset\land\mathbf{r}^{i}_{t}\in\mathcal{B}_{t}^{j})\\\
&\forall\;i\in\\{1,\dots,R_{t}\\}\land j\in\\{1,\dots K\\},\\\
&\sum_{i=1}^{R_{t}}\mathds{1}(a_{t}^{i}=j)\leq
1,\;\forall\;j\in\\{1,\dots,K\\}\biggl{\\}}\end{split}$ (A.1)

The operator can take one decision $a_{t}^{i}$ per request
$\mathbf{r}^{i}_{t},i\in\left\\{1,\dots,R_{t}\right\\}$. The operator can
either reject it $(a_{t}^{i}=0)$ or assign it to a vehicle $(a_{t}^{i}=j)$,
which is only possible if the vehicle has a free place in its request buffer
and the request is a customer request, i.e.,
${}^{2}\mathbf{r}_{t}^{j}=\emptyset\land\mathbf{r}^{i}_{t}\in\mathcal{C}_{t}$.
A vehicle can also rebalance $(a_{t}^{i}=j)$ under the condition that it idles
and the request is a vehicle-specific rebalancing request, i.e.,
${}^{1}\mathbf{r}_{t}^{j}=\emptyset\land\mathbf{r}^{i}_{t}\in\mathcal{B}_{t}^{j}$.
Each vehicle can be assigned to at most one request per time step.

Transition: First we describe the action-dependent transition from the pre-
decision state $\mathbf{S}_{t}$ to the post-decision state
$\mathbf{S}_{t^{\prime}}$. A reject decision does not alter the state. If a
(rebalancing) request is assigned to a vehicle, the request is appended to
that vehicle’s request buffer.

The transition from the post-decision state to the next system state
$\mathbf{S}_{t+1}$ is independent from the action and follows system dynamics.
If a vehicle picks up a customer at its origin vertex, the waiting time of
that request is reset. If a vehicle finds itself at a vertex and is serving a
request, the position of the vehicle is updated based on the route taken. If a
vehicle drops off a customer before the next decision is made, the request
buffer pops the old request and shifts the second request if available. The
waiting time for accepted but not yet served requests increases by the time
step increment. Rejected requests are dropped and leave the system
immediately. New requests appear according to an unknown distribution.

Rewards: The central operator aims to maximize the fleet profit. As autonomous
vehicles have negligible fixed costs after an initial investment, the
operational costs $c\in\mathbb{R}_{\leq 0}$ and trip fares base on the driven
distance. Each request is billed individually, depending on whether a car has
picked up the customer on time. The revenue per request
$\mathrm{rev}(\mathbf{r})\in\mathbb{R}_{>0}$ bases on the operator’s pricing
model and the total revenue per time-step over all vehicles depends on the
post-decision state

$\text{Rev}(\mathbf{S}_{t^{\prime}})=\sum_{j=1}^{K}\mathds{1}({}^{1}\mathbf{r}_{t^{\prime}}^{j}\neq\emptyset\land\tau_{t^{\prime}}^{j}=0\land
p_{t^{\prime}}^{j}=o({}^{1}\mathbf{r}_{t^{\prime}}^{j})\land\omega({}^{1}\mathbf{r}_{t^{\prime}}^{j})\leq\omega^{\mathrm{max}})\;\mathrm{rev}({}^{1}\mathbf{r}_{t^{\prime}}^{j})$

Regardless of whether customers are on board, the vehicle incurs variable
costs denoted by $c\in\mathbb{R}_{\leq 0}$ per unit of distance traveled (see,
e.g., Bösch et al. 2018, McKinsey & Co. 2023). Based on the vehicle’s route
from the post-decision position $p_{t^{\prime}}^{j}$ to the next pre-decision
position $p_{t+1}^{j}$, the total cost per time-step results to

$\text{Cost}(\mathbf{S}_{t^{\prime}})=c\,\sum_{j=1}^{K}\mathds{1}({}^{1}\mathbf{r}_{t^{\prime}}^{j}\neq\emptyset\land\tau_{t^{\prime}}^{j}=0)\;{}^{(p_{t^{\prime}}^{j},{p_{t+1}^{j}})}w^{d}$

The total profit at time $t^{\prime}$ is
$\mathrm{Profit}(\mathbf{S}_{t^{\prime}})=\mathrm{Rev}(\mathbf{S}_{t^{\prime}})-\mathrm{Cost}(\mathbf{S}_{t^{\prime}})$.
The post-decision state $\mathbf{S}_{t^{\prime}}$ is a function of the pre-
decision state $\mathbf{S}_{t}$ and the taken action
$\mathbf{a}_{t}\in\mathcal{A}\left(\mathbf{S}_{t}\right)$. Thus, we write
$\mathrm{Profit}(\mathbf{S}_{t^{\prime}})=\mathrm{Profit}(\mathbf{S}_{t},\mathbf{a}_{t})$.

The centralized operator of the AMoD fleet aims to find a policy
$\pi(\mathbf{a}_{t}|\mathbf{S}_{t})$ maximizing the expected total profit over
the time horizon $\mathcal{T}$, based on the initialized state
$\mathbf{S}_{0}$:

$\text{Profit}(\mathbf{S}_{0})=\max_{\pi}\mathbb{E}_{(\mathbf{S}_{t},\mathbf{a}_{t})\sim\pi}\left[\sum_{t=0}^{T-1}\text{Profit}(\mathbf{S}_{t},\mathbf{a}_{t})\Big{|}\mathbf{S}_{0}\right].$

##  Appendix B Proof of Proposition 1

######  Proposition 1.

Let us denote by $\bar{y}_{j}$ the per-agent target using
$\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)$. Then:

$\bar{y}_{j}=r_{j}+\gamma\,\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{b}_{j}|s^{\prime},j)\Bigl{\\}}$

###### Proof.

First, we express the target $\bar{y}_{j}$ based on
$\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)$ using the SACD target definition
in Equation (3.2)

$\bar{y}_{j}=r_{j}+\gamma\,\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)^{T}\cdot\Bigl{(}\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{\prime}|s^{\prime},j)\Bigl{\\}}-\alpha\log(\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j))\Bigl{)}.$
(B.1)

Now, we develop (B.1) and start with the scalar product as the sum over all
actions belonging to $\mathcal{A}$

$\displaystyle\bar{y}_{j}$ $\displaystyle=r_{j}$
$\displaystyle+\gamma\,\sum\limits_{a^{\prime}\in\mathcal{A}}\biggl{[}\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)\Bigl{(}\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{\prime}|s^{\prime},j)\Bigl{\\}}-\alpha\log(\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j))\Bigl{)}\biggl{]}$
(B.2) $\displaystyle\stackrel{{\scriptstyle\text{(I)}}}{{=}}r_{j}$
$\displaystyle+\gamma\bar{\pi}_{\phi}(a^{b}_{j}|s^{\prime},j)\Bigl{(}\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{b}_{j}|s^{\prime},j)\Bigl{\\}}-\alpha\log(\bar{\pi}_{\phi}(a^{b}_{j}|s^{\prime},j))\Bigl{)}$
$\displaystyle+\gamma\sum\limits_{a^{\prime}\in\mathcal{A}\setminus
a^{b}_{j}}\biggl{[}\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)\Bigl{(}\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{\prime}|s^{\prime},j)\Bigl{\\}}-\alpha\log(\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j))\Bigl{)}\biggl{]}$
$\displaystyle\stackrel{{\scriptstyle\text{(II)}}}{{=}}r_{j}$
$\displaystyle+\gamma\underbrace{\bar{\pi}_{\phi}(a^{b}_{j}|s^{\prime},j)}_{=\;1}\Bigl{(}\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{b}_{j}|s^{\prime},j)\Bigl{\\}}-\alpha\underbrace{\log(\bar{\pi}_{\phi}(a^{b}_{j}|s^{\prime},j))}_{=\;0}\Bigl{)}$
$\displaystyle+\gamma\sum\limits_{a^{\prime}\in\mathcal{A}\setminus
a^{b}_{j}}\biggl{[}\underbrace{\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{\prime}|s^{\prime},j)\Bigl{\\}}}_{=\;0}-\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)\alpha\log(\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j))\biggl{]}$
$\displaystyle\stackrel{{\scriptstyle\text{(III)}}}{{=}}r_{j}$
$\displaystyle+\gamma\,\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{b}_{j}|s^{\prime},j)\Bigl{\\}}-\gamma\sum\limits_{a^{\prime}\in\mathcal{A}\setminus
a^{b}_{j}}\biggl{[}\underbrace{\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)\alpha\log(\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j))}_{=\;0}\biggl{]}$
$\displaystyle=r_{j}$
$\displaystyle+\gamma\,\min_{m\in{1,2}}\Bigl{\\{}Q_{\bar{\theta}}^{m}(a^{b}_{j}|s^{\prime},j)\Bigl{\\}}.$

In the above derivation, we used the following reasoning:

(I) We divide the sum into terms depending on the action $a^{b}_{j}$ and terms
depending on the set of actions $\mathcal{A}\setminus a_{j}^{b}$. Here,
$a^{b}_{j}$ is the agent-specific action derived from the global action
$\bar{a}$.

(II) We recall that
$\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)=\begin{cases}1,\text{ if
}a^{\prime}=a^{b}_{j}\\\ 0,\text{ if }a^{\prime}\neq a^{b}_{j}\\\
\end{cases}$, as the distribution $\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)$
is degenerate.

(III) We use the rule of L’Hôpital to compute
$\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)^{T}\alpha\log(\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j))$
for $\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)=0$, if $a^{\prime}\neq
a^{b}_{j}$. Let us denote $x=\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)$, then
the following holds

$\lim_{x\rightarrow 0}\;x\;\log(x)=\lim_{x\rightarrow 0}\;\frac{\log
x}{\frac{1}{x}}\stackrel{{\scriptstyle\mathrm{L^{\prime}Hôpital}}}{{=}}\lim_{x\rightarrow
0}\;\frac{\frac{1}{x}}{-\frac{1}{x^{2}}}=\lim_{x\rightarrow
0}\;\frac{-x^{2}}{x}=\lim_{x\rightarrow 0}\;-x=0.$ (B.3)

Hence, we set
$\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j)^{T}\alpha\log(\bar{\pi}_{\phi}(a^{\prime}|s^{\prime},j))=0$.
∎

###  B.1 Dependency on the Environment

We note here, that the usage of the unadjusted loss $y_{j}$ can lead to good
results depending on the environment. Using the unadjusted loss $y_{j}$ in
unconstrained environments, where the agent can execute its action directly,
e.g., cooperative environments that determine only the reward depending on the
action of others, can yield good results (Iqbal & Sha 2019). However, in our
problem setting the matching algorithm introduces a competitive component
leading to a constrained environment. In competitive environments, where the
executed actions depend on the actions of others, using the per-agent action
leads to an increasingly inaccurate $y_{j}$ with a higher number of agents.
The increasing mismatch between per-agent actions and the actually executed
actions, derived from the global action, is shown by Lowe et al. (2017) where
they propose their multi-agent deep deterministic policy gradient algorithm.

##  Appendix C Methodology

In the following, we describe methodological details. First, we present our
chosen features and architecture details of the employed neural networks.
Second, we outline the hyperparameters used in our experiments. Third, we
explain the masking, which we use to retrieve the weights for our bipartite
matching. Fourth, we describe details regarding the definition of rebalancing
requests and the corresponding reward mechanisms applied during the training
process.

###  C.1 Feature & Neural Network Architectures

In this section, we describe the features used for our new parallel
architecture in detail. The input state for the first parallel dense layer is
specific to the respective agent $j$ and considers all available requests
$i\in\left\\{1,\dots,R_{t}\right\\}$. As we fix the number of requests per
agent, we extend $R_{t}$ to $R_{max}$ through padding to have a static input
size. We use a spatial discretization to divide the operating area into a
hexagonal grid. Each grid zone represents a central point with horizontal and
vertical indices. We map all possible locations of the operating area to
zones. The encoding of a location is based on the normalized indices of the
respective zone.

We now list the specific environment information that we use as inputs to
generate features for the neural network. The inputs differ slightly depending
on whether rebalancing is enabled ($V_{\mathrm{extended}}$) or whether only
the critic evaluates the feature (Critic):

  * •

Miscellaneous input features $m_{t}$ contain general environment information
and are the same for all agents:

    * –

Time step in the episode, normalized to [0,1]

    * –

Aggregated time steps needed for all vehicles to reach their final destination
positions, normalized to [0, 1], which indicates the current level of activity
within the fleet

    * –

Count of requests placed since start of current episode, divided by the count
of requests placed on average until the current time step, which indicates the
observed demand compared to an average episode

  * •

Vehicle input features $v^{j}_{t}$ are agent-specific:

    * –

Normalized encoding of vehicle’s end position, which is the current vertex if
no request is assigned, otherwise destination of assigned request that will be
served last

    * –

Time steps to reach this position, divided by the maximum time between any two
vertices in the graph representing the operating area

    * –

Number of assigned requests, normalized to [0,1]

  * •

Request input features $r^{i}_{t}$, duplicated for all agents:

    * –

Normalized encoding of the request origin zone

    * –

Normalized encoding of the request destination zone

    * –

Distance from origin to destination on graph G, normalized by maximum distance
to [0, 1]

    * –

($V_{\mathrm{extended}}$) Rebalancing flag in $[0,1]$

    * –

($V_{\mathrm{extended}}$) Number of vehicles with final destination in pick-up
zone, normalized to [0,1]

    * –

($V_{\mathrm{extended}}$) Number of vehicles with final destination in drop-
off zone, normalized to [0,1]

  * •

Request-Vehicle input features $(r^{i},v^{j})_{t}$, specified per request $i$
and vehicle $j$:

    * –

Distance from vehicle position to request origin, normalized by maximum
distance to [0, 1]

    * –

(Critic) Waiting time flag in $[0,1]$, which indicates whether a request can
be picked up in time

Next, we describe the actor network. The general structure of the input
processing resembles prior work by Enders et al. (2023) using the attention
mechanism and embeddings presented in Holler et al. (2019) and Kullman et al.
(2022). The request and vehicle input features serve as inputs to create the
respective embeddings. Each embedding consists of a feedforward dense layer
with 32 units and a rectified linear unit (ReLU) activation. The attention
mechanism computes a context from each embedding. The global context is the
concatenation of the request context and the vehicle context. As the number of
requests are time-dependent, we use embeddings and contexts to represent
variable-size inputs in a fixed-size global representation. For each path of
the parallel network (see Figure 3), we combine the request and vehicle
embeddings, the global context, and the specific request-vehicle input
features. The parallel networks act as trainable multi-layer embeddings. We
experience better performance when we shuffle the parallel inputs for all
customer requests in order to train all subsequent nodes after the flattening
equally. We evaluate these inputs for five parallel dense layers with unit
sizes of 512, 256, 128, 64, 32 and after flattening for six layers with unit
sizes of 1024, 512, 256, 128, 64, 32. We apply L2 regularization with a
coefficient of $10^{-4}$ to all layers. Generally, we use ReLU activation for
the feedforward layers and evaluate the final output on a softmax activation
with $|R_{max}+1|$ units.

The critic network architecture is similar to the actor network’s
architecture. However, we add the information regarding which requests were
globally accepted to the input features for the embeddings and the context
calculation. To this end, we add a binary flag ${0,1}$ that denotes rejection
and acceptance for requests. For the vehicle input features, we integrate the
information of the origin and the destination of newly assigned requests. The
critic output does not have an activation function.

###  C.2 Hyperparameters

We mostly use the same hyperparameters as Enders et al. (2023) for our
algorithm. We train for 200,000 steps (300,000 for rebalancing on 38 large
zones), update the network parameters every 20 steps, and test the performance
of the current policy on the validation data every 2,880 steps (48 episodes).
During the first 20,000 steps, we collect experience with a random policy and
do not update the network parameters. For the next 30,000 steps, we add
linearly declining noise to the actor’s weights. For the critic loss, we use
the Huber loss with a delta value of 10 instead of the squared error. We use
gradient clipping with a clipping ratio of 10 for actor and critic gradients.
We use the Adam optimizer with a learning rate of $3\times 10^{-4}$. We sample
batches of size 128 from a replay buffer with maximum size of 100,000 for the
first experiment and 50,000 for the second experiment. We set the discount
factor to 0.925. For the update of the target critic parameters we use an
exponential moving average with smoothing factor $5\times 10^{-4}$. We tune
the entropy coefficient individually per instance in the range of 0.2 to 0.6.

We conduct multiple training runs using five different random seeds and select
the model with the highest validation performance across these runs. The
selected model undergoes testing on the dataset, and the results presented in
this paper reflect its performance on the test data.

###  C.3 Masking step in Figure 3

We use deterministic post-processing to mask the edge weights used in matching
to adhere to our constrains and to determine the per-agent reject action. The
masking step enables the agent to reject single requests by comparing the
weights against a constant threshold. The selected threshold is the highest
value at which the agent is able to accept all requests and also rank them
against one another. Thus, a per-request weight must be greater than
$1/(R_{max}+1)$. By ranking we refer to the agent’s ability to signal its wish
to take multiple requests, but valuing them differently. During training, the
agent differentiates between an active and a passive reject action. The active
reject action occurs if the agent does not want any request. In this case, we
will consider the $Q$-value and probability of the reject action when
calculating the loss. For the passive reject action, the system does not use
the $Q$-value and probability when calculating the loss, as the matching
decided that the agent does not receive a request instead of the agent
choosing to reject all its requests. Thus, the passive reject action is not
the same as the active reject action and therefore the $Q$-value for actively
rejecting cannot be used.

In Algorithm 1 we describe how we mask the weights obtained from the actor
(cf. Figure 2). We start with the plain weights from the actor as input data
and change them to match the environment constraints and to retrieve the
reject action. We first check whether the second place of the request buffer
${}^{2}\mathbf{r}_{t}^{j}$ is occupied (Algorithm 1). If this is the case, we
set all weights of the vehicle $w^{r^{i}}_{t}$ to 0 and a passive reject
action $a^{\emptyset}_{t}=0$ (Algorithm 1). If not, we check for each weight
of the vehicle $w^{r^{i}}_{t}$ if is it higher than the previously mentioned
threshold which we denote as $\delta$ (Algorithm 1). If this is the case, we
keep the weight as is (Algorithm 1) if this is not the case, we set it to 0
(Algorithm 1). Finally, we check for an active reject action by adding up all
weights of one vehicle and check whether the sum corresponds to 0 (Algorithm
1). If this is the case, we determine an active reject action
$a^{\emptyset}_{t}=1$ (Algorithm 1) and if not a passive reject action
$a^{0}_{t}=0$ (Algorithm 1).

Input Data: weights $w^{r^{i}}_{t}$ ; threshold $\delta=\frac{1}{R_{max}+1}$

Output Data: weights $w^{r^{i}}_{t}$ ; reject action $a^{0}_{t}$

1 if ${}^{2}\mathbf{r}_{t}^{j}\neq\emptyset$ then

2 $w^{r^{i}}_{t}$ = 0 ; $a^{0}_{t}$ = 0 ;

3

4 else

5 for $i$ in $R_{t}$ do

6 if $w^{r^{i}}_{t}>\delta$ then

7 $w^{r^{i}}_{t}=w^{r^{i}}_{t}$

8 else

9 $w^{r^{i}}_{t}$ = 0

10

11 if $\sum_{i}w^{r^{i}}_{t}=0$ then

12 $a^{0}_{t}$ = 1

13 else

14 $a^{0}_{t}$ = 0

15

Algorithm 1 Masking per vehicle agent

###  C.4 Rebalancing Requests

To seamlessly integrate rebalancing with dispatching, we model rebalancing
actions as requests. We constrain rebalancing requests and differentiate them
from customer requests as follows:

  1. (a)

Vehicles can only accept rebalancing requests when they idle, i.e., when their
request buffer is empty
(${}^{1}\mathbf{r}_{t}^{j}=\emptyset\land{}^{2}\mathbf{r}_{t}^{j}=\emptyset$).
Therefore, only one rebalancing action can be undertaken at a time.

  2. (b)

The origin of rebalancing requests corresponds to their destination. Thus, a
vehicle’s approach to that destination is considered as rebalancing.

  3. (c)

Rebalancing requests are only possible to zones not corresponding to the
vehicle’s current zone, i.e $p(v)\neq d(r)$.

  4. (d)

Rebalancing requests must be accepted immediately and cannot be deferred,
i.e., $\omega(r)=\emptyset$.

  5. (e)

Rebalancing requests generate operational costs corresponding to the distance
traveled by the vehicle that fulfills it.

  6. (f)

We incorporate a flag into the rebalancing request features to distinguish
them from customer requests.

As rebalancing requests incur only costs, every rebalancing action returns a
negative reward when executed. The algorithm learns to identify the positive
impact of rebalancing in future time steps via the Bellman recursion. However,
we can speed-up learning by incorporating additional reward signals during
training. We do so by calculating an artificial fare for rebalancing, only
used during training, that is added to the operational costs of rebalancing in
order to incentivize good and to penalize bad rebalancing behavior.

Algorithm 2 describes the calculation of the artificial fare for rebalancing.
The variable $x_{t}^{d}(r^{i})$ in Algorithm 2 measures the number of vehicles
in the destination zone of the rebalancing request normalized to a value
between 0 (full zone) and 1 (empty zone). The variable $x_{t}^{o}(r^{i})$
calculates a similar proxy measure for the origin zone of the request. We
distinguish between empty and full origin zones (Algorithm 2), as empty zones
result in a negative artificial fare (Algorithm 2) and full zones in a
positive artificial fare (Algorithm 2). We give the positive artificial fare
in Algorithm 2 proportional to the emptiness of the destination as we multiply
with $x_{t}^{d}(r^{i})$ and we increase the negative artificial fare faster
(indicated by factoring it with -2). Finally, we sum up $x_{t}^{d}(r^{i})$ and
$x_{t}^{o}(r^{i})$, wherein we attribute a lower weight to $x_{t}^{o}(r^{i})$
(Algorithm 2) to mitigate unnecessary rebalancing. Thus, we have an artificial
fare that accounts for the occupancy of the destination zone as well as origin
zone, to give the complex state representation additional reward signals,
which rebalancing would otherwise not receive.

Input Data: number of vehicles at origin of the request $o_{t}(r^{i})$ ;
number of vehicles at destination of the request $d_{t}(r^{i})$, cost
parameter $c$, minimum distance between two vertices $l$, average number of
vehicles per zone rounded up $v_{t}^{u}$, average number of vehicles per zone
rounded down $v_{t}^{f}$

Output Data: training fare $f_{t}^{j}$

1 $x_{t}^{d}(r^{i})=1-\min\\{1,\frac{d_{t}(r^{i})}{v_{t}^{f}}\\}$

2 if $o_{t}(r^{i})<v_{u}$ then

3 $x_{t}^{o}(r^{i})=\frac{(v_{t}^{u}-o_{t}(r^{i})+1)\times(-2)}{v_{t}^{u}}$

4 else

5 $x_{t}^{o}(r^{i})=\frac{o_{t}(r^{i})-v_{t}^{u}}{v_{t}^{u}}\times
x_{t}^{d}(r^{i})$

6$x_{t}(r^{i})=\frac{x_{t}^{o}(r^{i})}{2}+2\times x_{t}^{d}(r^{i})$

$f_{t}^{j}=c\times l\times x_{t}(r^{i})$

Algorithm 2 Calculation of fare for rebalancing during training

##  Appendix D Experiments

In the following, we present additional details about our experiments. First,
we provide information regarding the underlying datasets and the system
configuration. Second, we elaborate on the three benchmark algorithms. Third,
we offer insights into the rebalancing behavior exhibited by our policy.

###  D.1 Datasets

For our experiment, we use yellow taxi trip records in NYC from the year 2015
(TLC 2015), excluding weekends and holidays. We assume that request placement
times coincide with the reported pick-up times in the dataset. We extract
pick-up and drop-off longitude/latitude coordinates, restricting our
experiment to trips where both coordinates fall on the main island of
Manhattan. We use spatial discretization by employing hexagon grids. We map
each request to a pick-up and a drop-off zone based on the shortest distance
of the requests pick-up and drop-off coordinates to the center of any zone. We
exclude trips starting and ending in the the same zone. The distances between
neighboring zones are set at 459 meters for small zones and 917 meters for
large zones. Travel time between two neighboring zones assumes two and five
time steps based on realistic driving speeds. We construct a graph, wherein
each zone represents a vertex and edges connect neighboring zones. Vehicles
traveling between non-neighboring zones follow the shortest route.

We focus on two different subsets of zones within the NYC dataset, which
define our simulated operating areas, i.e., the part of Manhattan in which our
fleet operates. Hence, we only consider requests having both pick-up and drop-
off locations within the operating area. For the 38 large zones, we downscale
trip data by a factor of 20, using every 20th request for simulation. This
adjustment accommodates hardware limitations and results in an average of 360
requests per episode for the 11 small zones and 828 requests for the 38 large
zones. The mean trip distance is larger for the 38 large zones, influencing
the number of vehicles required.

Figure 7(a) illustrates the smaller operating area of the NYC dataset, wherein
colors represent pick-up and drop-off frequency. Dark green represents zones
with a majority of pick-ups, while dark red represents zones with a majority
of drop-offs. Light yellow/green reflects zones, wherein the number of pick-
ups and drop-offs is almost equal. Although some of the 11 small zones exhibit
a minor bias towards either drop-off or pick-up, it is not strongly
pronounced. Therefore, we obtain a second dataset which maintains the temporal
patterns of the NYC taxi dataset while altering the drop-off and pick-up
locations to achieve more imbalanced request distributions. We do so by
sampling pick-ups from a normal distribution around a cluster and sampling
drop-offs towards its edges from another normal distribution. This
modification allows for a more imbalanced spatial distribution of requests,
depicted by dark green and dark red zones in Figure 7(b). This simulates
realistic scenarios like, e.g., the end of a major sports event in the middle
of the operating area. Figure 8 displays the operating area of the 38 large
zones with its spatial distribution.

We assume a maximum waiting time of five minutes for the 11 small zones
setting and ten minutes for the 38 large zones setting, with the increased
waiting time due to the longer trip lengths and greater size of the operating
area. To achieve a 20% operating profit margin with empty driving to the pick-
up location, we set the revenue at 5.00 USD per km, and operational costs at
2.00 USD per km.

(a) NYC - 11 zones

(b) Clustered - 11 zones

Figure 7: The 11 zone operating area. Zones dominated by pick-ups are marked
in green, zones dominated by drop-offs are marked in red, and zones with a
balance between pick-ups and drop-offs are marked in light green/yellow.

(a) NYC - 38 zones

(b) Clustered - 38 zones

Figure 8: The 38 zone operating area. Zones dominated by pick-ups are marked
in green, zones dominated by drop-offs are marked in red, and zones with a
balance between pick-ups and drop-offs are marked in light green/yellow.

###  D.2 Benchmarks

Greedy: Greedy chooses the highest reward at the current time step. Thus, it
assigns every request a weight that depends on the profitability of the
request. The weight is zero for unprofitable requests, i.e., if the cost is
higher than the fare or if the time to pick-up the customer is higher than the
maximum waiting time. The algorithm weighs all other requests proportionally
to the profitability for each vehicle. To this end, Greedy subtracts the cost
of the total distance, i.e., the distance to the pick-up plus the distance
driven with the customer, from the fare of the request.

Heuristic: The Rebalancing Heuristic weighs customer requests the same way as
the greedy policy, but has additional rebalancing capabilities. Heuristic
weighs rebalancing actions lower than customer requests and aims for an equal
distribution of vehicles per zone. Heuristic attributes a non-zero weight to
rebalancing requests only if the vehicle’s current zone has more vehicles than
the rounded up average number of vehicles per zone $v_{t}^{u}$ and vehicle’s
destination zone has less vehicles than the rounded down $v_{t}^{u}$ average
number of vehicles per zone. The weight is proportional to the vehicle’s
distance to the destination zone.

RVC: Each agent represents a request-vehicle pair. All agents return two
probabilities, one for declining the request and one for accepting it. Both
probabilities add up to one. The accept probabilities serve as weights in the
bipartite matching problem if they are higher than the reject probabilities
during validation and testing. If the accept probabilities are lower than the
reject probabilities, they are not considered in the bipartite matching
problem. During training, accept and reject decisions are sampled according to
their respective probabilities and the weights in the bipartite matching
problem then correspond to the probability of the sampled action.

###  D.3 Rebalancing Behavior

Our experiments show for the 11 small zones setting that
$V_{\mathrm{extended}}$ always rebalances vehicles to a neighboring zone in
one time step. This behavior is beneficial as the agent can reevaluate its
rebalancing actions in each time step and check for new customer requests. The
larger the setting, the more rebalancing actions the agent has to evaluate.
This increases noise and computational effort. As the agent exclusively
rebalances to neighboring zones in the context of the 11 small zones setting,
we intentionally extend this practice to encompass only neighboring zones as
viable rebalancing options for the larger 38 zones.


# Performance Variability in Zero-Shot Classification

Matías Molina
Universidad Nacional de Córdoba
<EMAIL_ADDRESS>
&Jorge Sánchez
CONICET
<EMAIL_ADDRESS>

###### Abstract

Zero-shot classification (ZSC) is the task of learning predictors for classes
not seen during training. Although the different methods in the literature are
evaluated using the same class splits, little is known about their stability
under different class partitions. In this work we show experimentally that ZSC
performance exhibits strong variability under changing training setups. We
propose the use ensemble learning as an attempt to mitigate this phenomena.

##  1 Motivation

Training classifiers on specific non-generic domains requires a non negligible
effort on data annotation. Although this might be easy for some of the target
categories, it might become too costly for others due to the long-tail
distribution of samples. This has motivated the development of models that can
be trained on little data (few-shot learning) or no data at all (zero-shot
learning). In zero-shot classification (ZSC) [5] we are given a set of labeled
samples from a known set of categories and the goal is to learn a model that
is able to cast predictions over a set of categories not seen during training.
Despite having identified the difficulties and particularities in the
evaluation of different approaches [9], little attention has been paid to the
effect of considering different training class partitions for a given problem.
Given the large number and diversity of models proposed in the literature in
the recent years, we believe this is an important factor to be considered when
choosing between competing approaches. In this work, we start exploring this
problem. Our preliminary experiments using different datasets of varying
granularity and two simple baselines confirm our hypothesis: performance
differences observed in the literature might be not as significant as it seems
due to the large variability observed across different subsets of training
classes.

##  2 Experiments and Discussion

In ZSC we are given a training set
$\mathcal{D}^{tr}=\\{(x_{i},y_{i})~{}|~{}x_{i}\in\mathcal{X},y_{i}\in\mathcal{Y}^{tr}\\}$.
The goal is to learn a mapping $f:\mathcal{X}\rightarrow\mathcal{Y}$ from
$\mathcal{D}^{tr}$ that can be used to classify samples over a different set
$\mathcal{Y}^{ts}\subset\mathcal{Y}$. We consider the standard ZSC setting,
where $\mathcal{Y}^{tr}\cap\mathcal{Y}^{ts}=\emptyset$. Given a representation
$z_{y}\in\mathbb{R}^{E}$ for each $y\in\mathcal{Y}$, a common approach [1, 7]
is to learn a function $F:\mathcal{X}\times\mathcal{Z}\rightarrow\mathbb{R}$
to reflect the degree at which $x$ and $z$ agree on a given concept. Given a
test sample $x$, its class is predicted as
$\hat{y}=\operatorname*{argmax}_{y\in\mathcal{Y}^{ts}}F(x,z_{y})$.

The work of Xian et al. [9] identified several problems in the evaluation
methodology used in the ZSC literature. One key contribution of their work was
the proposal of fixed set of train/test class splits for different datasets.
Although this addresses many of the evaluation problems identified in [9], it
does not considers the effect of varying training class partitions. We believe
analyzing not only the mean but also the variability of the zero-shot
predictive performance under changing training configurations is an important
factor towards a more thoughtful evaluation of the different methods. Our work
is a first step in that direction.

Table 2 shows the mean and standard deviation over different training
partitions for two simple baselines, ESZSL[7] and SJE[1], on two fine-grained
(SUN[6] and CUB[8]) and two coarse-grained (AWA1[5] and AWA2[9]) datasets,
using different class partitions sampled at random. We observe a great deal of
variability whether the sample per class imbalance is considered (avg. acc.)
or not (avg. per-class acc.). We observe that the difference in performance
(as reported in the literature) might bias the selection of one method over
the other even when their difference is not statistically significant. The
table also show p-values of a Wilcoxon signed-rank test computed from 22
different partitions chosen at random. We see that while for the fine-grained
cases we can reject the null hypothesis for a fairly low confidence level,
this is not the case in the coarse-grained data regime. Although the
difference in mean values seems high (for the standards observed in the
literature), the variability observed in the experiments warns against
choosing one method over the other.

### Ensemble learning for ZSC.

Beyond the identification of the variability problem, we ran experiments using
standard ensemble techniques as an attempt to mitigate its effect. The idea is
that by combining more than one predictor into a single model, it is possible
to reduce the variance by averaging [3]. One popular approach is the Bootstrap
Aggregation or Bagging meta-algorithm [2]. It is based on learning different
predictors using different subsets of training samples and aggregating them
via a suitable voting scheme. The _hard_ voting scheme assigns the class
predicted by the majority, i.e.
$\hat{f}(x)=\operatorname*{mode}\\{f_{1}(x),...,f_{n}(x)\\}$. In _soft_
voting, prediction is given by the highest score over all the models , i.e.
$\hat{f}(x)=\operatorname*{argmax}_{y}\\{\sum_{i}F_{i}(x,z_{y})\\}$.

In the context of ZSC, we use different (random) subsets of training
categories to generate the set of base predictors, i.e. we learn a set $n$
predictors using a proportion $s$ of randomly chosen classes from the original
training set. We use hard and soft ensembles considering
$n=\\{10,30,50,70,90\\}$ and $s=\\{0.3,0.5,0.7,0.9\\}$, e.g. $(n,s)=(10,0.3)$
means training $10$ different models using $30\%$ of the full set of training
categories. Each sub-problem is trained on a different subset of training
classes. We sample 4 different sub-problems for each $(n,s)$ combination.
Baseline performances are as follows: $56.91~{}(1.63)$ on SUN,
$54.80~{}(2.82)$ on CUB, and $70.62~{}(7.32)$, $73.26~{}(4.81)$ on AWA1 and
AWA2 respectively. We use the ResNet101 features and continuous attribute
vectors from [9] and normalize both to unit norm. We found that as the
proportion $s$ increases performance approaches the baseline, which is to be
expected since the set of training categories tends to resemble the original
set. The standard deviation may marginally decrease but with a considerable
loss in performance. This situation is more noticeable in the case of AWA1 and
AWA2, both coarse-grained datasets, compared to the others. Table 1 shows the
ensemble results for $n=90$. 111Different combinations of voting schemes and
accuracy metrics lead to similar conclusions. Beyond these observations, the
use of ensemble does not lead to an increase on the overall ZSC performance.
Alternatives to this formulation is the topic of our current research.

Table 1: Soft ensemble results. Top-1 average per-class accuracy and its std. deviation, for $n=90$. | $s$ | 0.3 | 0.5 | 0.7 | 0.9
---|---|---|---|---|---
SUN |  | 55.61 (2.16) | 56.81 (2.02) | 56.77 (1.98) | 57.03 (1.73)
CUB |  | 50.89 (2.92) | 53.45 (2.84) | 54.39 (2.84) | 54.83 (2.72)
AWA1 |  | 65.35 (6.52) | 68.38 (7.49) | 69.70 (7.63) | 70.52 (7.31)
AWA2 |  | 66.90 (3.70) | 70.39 (4.23) | 72.16 (4.26) | 73.13 (4.52)
Table 2: Top-1 accuracy and average top-1 per-class accuracy, std. deviation and p-value for 22 splits. |  | SUN | CUB | AWA1 | AWA2
---|---|---|---|---|---
Avg. acc. | ESZSL | 55.90 (1.95) | 53.49 (2.10) | 69.66 (9.94) | 71.10 (10.94)
SJE | 59.16 (2.37) | 56.08 (3.03) | 68.85 (7.96) | 68.84 (11.16)
p-value | 0.000001 | 0.0012 | 0.7024 | 0.5028
Avg. per-class acc. | ESZSL | 55.92 (1.94) | 53.81 (2.20) | 69.34 (9.02) | 71.48 (9.54)
SJE | 59.73 (2.17) | 56.19 (2.44) | 69.48 (8.27) | 69.34 (9.63)
p-value | 0.0000005 | 0.0000024 | 0.8736 | 0.1762

## References

  * [1] Z. Akata, S. Reed, D. Walter, H. Lee, and B. Schiele.  Evaluation of output embeddings for fine-grained image classification.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2927–2936, 2015.
  * [2] L. Breiman.  Bagging predictors.  Machine learning, 24(2):123–140, 1996.
  * [3] T. G. Dietterich.  Ensemble methods in machine learning.  In International workshop on multiple classifier systems, pages 1–15. Springer, 2000.
  * [4] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [5] C. H. Lampert, H. Nickisch, and S. Harmeling.  Learning to detect unseen object classes by between-class attribute transfer.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 951–958. IEEE, 2009.
  * [6] G. Patterson and J. Hays.  Sun attribute database: Discovering, annotating, and recognizing scene attributes.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 2751–2758. IEEE, 2012.
  * [7] B. Romera-Paredes and P. Torr.  An embarrassingly simple approach to zero-shot learning.  In International Conference on Machine Learning, pages 2152–2161, 2015.
  * [8] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie.  The caltech-ucsd birds-200-2011 dataset.  2011\.
  * [9] Y. Xian, C. H. Lampert, B. Schiele, and Z. Akata.  Zero-shot learning-a comprehensive evaluation of the good, the bad and the ugly.  IEEE transactions on pattern analysis and machine intelligence, 2018\.