# CONDITIONAL EXPECTATION BASED VALUE DECOMPOSITION FOR SCALABLE ON-DEMAND RIDE POOLING

**Anonymous authors**
Paper under double-blind review

ABSTRACT

Owing to the benefits for customers (lower prices), drivers (higher revenues), aggregation companies (higher revenues) and the environment (fewer vehicles), ondemand ride pooling (e.g., Uber pool, Grab Share) has become quite popular. The
significant computational complexity of matching vehicles to combinations of requests has meant that traditional ride pooling approaches are myopic in that they
do not consider the impact of current matches on future value for vehicles/drivers.
Recently, Neural Approximate Dynamic Programming (NeurADP) has employed
value decomposition with Approximate Dynamic Programming (ADP) to outperform leading approaches by considering the impact of an individual agent’s (vehicle) chosen actions on the future value of that agent. However, in order to ensure
scalability and facilitate city-scale ride pooling, NeurADP completely ignores the
impact of other agents actions on individual agent/vehicle value. As demonstrated
in our experimental results, ignoring the impact of other agents actions on individual value can have a significant impact on the overall performance when there
is increased competition among vehicles for demand. Our key contribution is a
novel mechanism based on computing conditional expectations through joint conditional probabilities for capturing dependencies on other agents actions without
increasing the complexity of training or decision making. We show that our new
approach, Conditional Expectation based Value Decomposition (CEVD) outperforms NeurADP by up to 9.76% in terms of overall requests served, which is a
significant improvement on a city wide benchmark taxi dataset.

1 INTRODUCTION

Taxi/car on Demand (ToD) services (e.g., UberX, Lyft, Grab) not only provide a comfortable means
of transport for customers, but also are good for the environment by enabling sharing of vehicles over
time (while being used to serve one request at any one point in time). A further improvement of ToD
is on-demand ride pooling (e.g., UberPool, LyftLine, GrabShare etc.), where vehicles are shared not
only over time but also in space (on the taxi/car). On-demand ride pooling reduces the number
of vehicles required, thereby reducing emissions and traffic congestion compared to Taxi/car onDemand (ToD) services. This is achieved while providing benefits to all the stakeholders involved:
(a) Individual passengers have reduced costs due to sharing of space; (b) Drivers make more money
per trip as multiple passengers (or passenger groups) are present; (c) For the aggregation company
more customer requests can be satisfied with the same number of vehicles.

In this paper, we focus on this on-demand ride pooling problem at city scale, referred to as RidePool Matching Problem (RMP) [Alonso-Mora et al. (2017); Bei & Zhang (2018); Lowalekar et al.
(2019)]. The goal in an RMP is to assign combinations of user requests to vehicles (of arbitrary
capacity) online such that quality constraints (e.g., delay in reaching destination due to sharing is not
more than 10 minutes) and matching constraints (one request can be assigned at most one vehicle,
one vehicle must be assigned at most one request combination) are satisfied while maximizing an
overall objective (e.g., number of requests, revenue). Unlike the ToD problem that requires solving a
bipartite matching problem between vehicles and customers, RMP requires effective matching on a
tripartite graph of requests, trips (combinations of requests) and vehicles. This matching on tripartite
graph significantly increases the complexity of solving RMP online, especially at city scale where


-----

there are hundreds or thousands of vehicles, hundreds of requests arriving every minute and request
combinations have to be computed for each vehicle.

Due to this complexity and the need to make decisions online, most existing work related to solving
RMP has focused on computing best greedy assignments [Ma et al. (2013); Tong et al. (2018); Huang
et al. (2014); Lowalekar et al. (2019); Alonso-Mora et al. (2017)]. While these scale well, they are
myopic and, as a result, do not consider the impact of a given assignment on future assignments.
The closest works of relevance to this paper are by Shah et al. [Shah et al. (2020)] and Lowalekar
_et al. [Lowalekar et al. (2021)]. We specifically focus on the work by Shah et al., as it has the best_
performance, while being scalable. That work considers future impact of current assignment from
an individual agents’ perspective without sacrificing on scalability (to city scale). However, a key
limitation of that work is that they do not consider the impact of other agents (vehicles) actions on
an agents’(vehicle) future impact, which as we demonstrate in our experiments can have a major
effect (primarily because vehicles are competing for the common demand).

To that end, we develop a conditional expectation based value decomposition approach that not only
considers future impact of current assignments but also of other agents state and actions through the
use of conditional probabilities and tighter estimates of individual impact. Due to these conditional
probability based tighter estimates of individual value functions, we can scale the work by Guestrin
_et al. [Guestrin & Parr (2002)] and Li et al. [Li & Kochenderfer (2021)] to solve problems with no_
explicit coordination graphs and hundreds/thousands of homogeneous agents. Unlike value decomposition approaches [Rashid & Whiteson (2018); Sunehag & Graepel (2018)] developed for solving
cooperative Multi-Agent Reinforcement Learning (MARL) with tens of agents and under centralized training and decentralized execution set up, we focus on problems with hundreds or thousands
of agents with centralized training and centralized execution (e.g., Uber, Lyft, Grab).

In this application domain of taxi on demand services, where improving 0.5%-1% is a major achievement [Lin et al. (2018)], we demonstrate that our approach easily outperforms the existing best approach, NeurADP [Shah et al. (2020)] by at least 3.8% and up to 9.76% on a wide variety of settings
for the benchmark real world taxi dataset [NYYellowTaxi (2016)].

2 BACKGROUND

In this section, we formally describe the RMP problem and also provide details of an existing approach for on-demand ride pooling called NeurADP, which we improve over.

**Ride-pool Matching Problem (RMP) : We consider a fleet of vehicles/resources R with random**
initial locations, travelling on a predefined road network G with intersections : L as nodes, road
segments : E as edges and weights on edges indicate the travel time on the road segment. Passengers
that want to travel from one location to another send requests to a central entity that collects these
requests over a time-window called the decision epoch ∆. The goal of the RMP is to match these
collected requests U _[t]_ to empty or partially filled vehicles that can serve them such that an objective
_J is maximised subject to constraints on the delay D._

We upperbound D and consider the objective J to be the number of requests served. Thus, RMP is
defined using the tuple [G, U _, R, D, ∆, J ][1]. Please refer Appendix A.1 for a detailed description._

Delay constraints : D consider two delays, {τ, 2τ _}. τ denotes the maximum allowed pick-up delay_
which is the difference between the arrival time of a request and the time at which a vehicle picks
the user up. 2τ denotes the maximum allowed detour delay which is the difference between the time
at which the user arrived at their destination in a shared cab and the time at which they would have
arrived if they had taken a single-passenger cab.

**Neural Approximate Dynamic Programming (NeurADP) for Solving RMP: Figure 1 provides**
the overall approach. In this paper, there are two NeurADP [Shah et al. (2020)] contributions of
relevance:

**_FV: To estimate Future Value of current actions, a method for solving the underlying Approx-_**
_imate Dynamic Program (ADP) [Powell (2007)] by considering neural network represen-_
_tations of value functions._

1Everywhere in the paper [, ] is used as the concatenation operator


-----

Figure 1: NeurADP approach [Shah et al. (2020)]

**_DJV: To ensure scalability, Decomposing the Joint Value function into individual vehicle value_**
_functions by extending on the work of Russell et al. [Russell & Zimdars (2003)]._

**Future Value (FV): ADP is similar to a Markov Decision Problem (MDP) with the key difference**
that the transition uncertainty is extrinsic to the system and not dependent on the action. The ADP
problem for RMP is formulated using the tuple ⟨S, A, ξ, T, J ⟩, where :

_S : The state of the system is represented as st = (rt, ut) where rt is the state of all vehicles and ut_
contains all the requests waiting to be served. The state is obtained in Step A of Figure 1.

_A : At each time step there are a large number of requests arriving to the taxi service provider,_
however for an individual vehicle only a small number of such requests are reachable. The feasible
set of request combinations for each vehicle i at time t, Ft[i] [is computed in Step B of Figure 1:]

_t_ [=][ {][f][ i][|][f][ i][ ∈∪]c[c][′][i]=1[[][U] []][c][′] _[,][ PickUpDelay][(][f][ i][, i][)][ ≤]_ _[τ,][ DetourDelay][(][f][ i][, i][)][ ≤]_ [2][τ] _[}]_ (1)
_F_ _[i]_

_a[i,f]t_ is the decision variable that indicates whether vehicle i takes action f (a combination of
requests) at a decision epoch t. Joint actions across vehicles have to satisfy matching constraints:
(i) each vehicle, i can only be assigned at most one request combination, f ; (ii) at most one
vehicle, i can be assigned to a request j; and (iii) a vehicle, i can be either assigned or not
assigned to a request combination.


_a[i,f]t_ = 1 ::: _i_
_∀_ _∈R_


_a[i,f]t_ 1 ::: _j_ _t_ _a[i,f]t_ 0, 1 ::: _i, f_ (2)
_≤_ _∀_ _∈U_ _∈{_ _}_ _∀_
_f_ _∈FXt[i][;][j][∈][f]_


_i∈R_


_f_ _∈Ft[i]_


_ξ : denotes the exogenous information – the source of randomness in the system. This would_
correspond to the user requests or demand. ξt denotes the exogenous information at time t.

_T :_ denotes the transitions of system state. In an ADP, the system evolution happens as
(s0, a0, s[a]0[, ξ][1][, s][1][, a][1][, s][a]1[,][ · · ·][, s][t][, a][t][, s]t[a][,][ · · ·][ )][, where][ s][t] [denotes the pre-decision state at decision]
epoch t and s[a]t [denotes the post-decision state [Powell (2007)]. The transition from state][ s][t] [to]
_st+1 depends on the action vector at and the exogenous information ξt+1. Therefore,_

_st+1 = T_ (st, at, ξt+1); s[a]t [=][ T][ a][(][s][t][, a][t][);][ s][t][+1] [=][ T][ ξ][(][s][a]t _[, ξ][t][+1][)]_

It should be noted that T _[a](., .) is deterministic as uncertainty is extrinsic to the system._

_J : denotes the reward function and in RMP, this will be the revenue from a trip._
Let V (st) denotes the value of being in state st at decision epoch t, then using Bellman equation:

_V (st) = max_ (3)
_at_ _At[(][J][ (][s][t][, a][t][) +][ γ][E][[][V][ (][s][t][+1][)][|][s][t][, a][t][, ξ][t][+1][])]_
_∈_


-----

**(I) Get Requests, Compute Feasible**

**(II) Score Values considering consequences on other vehicles**
**Actions, Find Individual Values**

[Expected Value of conditioned on ] [Expected Value of conditioned on ]

[Neighbour aware value for action for ] [Neighbour aware value for action for ]

[Neighbour aware value for action for


[Neighbour aware value for action for


**(III)Solve ILP using Neighbour aware scores, assign optimal actions, simulate motion**

|Col1|Integer Linear Program (ILP)|Optimal|
|---|---|---|
|||Actions|
|||Chosen|



Figure 2: Schematic outlining CEVD’s neighbour aware scoring mechanism

where γ is the discount factor. Using post-decision state, this expression breaks down nicely:

_V (st) = max_ _t_ [));] _V_ _[a](s[a]t_ [) =][ E][[][V][ (][s]t+1[)][|][s][a]t _[, ξ]t+1[]]_ (4)
_at_ _At[(][J][ (][s][t][, a][t][) +][ γV][ a][(][s][a]_
_∈_

The advantage of this two step value estimation is that the maximization problem in Equation 4
can be solved using a Integer Linear Program (ILP) with matching constraints indicated in expression 2. Step D of Figure 1) provides this aspect of the overall algorithm. The value function
approximation around post-decision state, V _[a](s[a]t_ [)][ is a neural network and is updated (Step E of]
Figure 1) by stepping forward through time using sample realizations of exogenous information
(i.e. demand observed in data). However, as we describe next, maintaining a joint value function
is not scalable and hence we decompose and maintain individual value functions.
**Decomposing Joint Value (DJV): Non-linear value functions, unlike their linear counterparts,**
cannot be directly integrated into the ILP mentioned above. One way to incorporate them is
to evaluate the value function for all possible post-decision states and then add these values
as constants. However, the number of post-decision states is exponential in the number of resources/vehicles.

[Shah et al. (2020)] introduced a two-step decomposition of the joint value function that converts
it into a linear combination over individual value functions associated with each vehicle. In the
first step, following [Russell & Zimdars (2003)], the joint value function is written as the sum
over individual value functions : V (s[a]t [) =][ P]i _[V][ i][(][s]t[a][)][.]_

In the second step, the individual vehicles’ value functions are approximated. They assumed
that the long-term expected reward of a given vehicle is not significantly affected by the specific
actions another vehicle makes in the current decision epoch and thereby completely neglect the
impact of the actions taken by other vehicles at the current time step. Thus they model the value
function using the pre-decision, rather than post-decision, state of other vehicles which gives :

_V_ _[i](s[a]t_ [) =][ V][ i][([][s]t[i,a][, s]t[-][i,a]]) ≈ _V_ _[i]([s[i,a]t_ _[, s]t[-][i][])]_

where -i refers to all vehicles except vehicle i. This allows NeurADP to get around the combi_natorial explosion of the post-decision state of all vehicles._ NeurADP thus has the joint value
function : V (s[a]t [) =][ P]i _[V][ i][([][s]t[i,a][, s]t[-][i][])][.]_

They then evaluate these individual V _[i]_ values (Step C of Figure 1) for all possible s[i,a]t (from
the individual value neural network) and then integrate the overall value function into the ILP
as a linear function over these individual values. This reduces the number of evaluations of the
non-linear value function from exponential to linear in the number of vehicles.


-----

3 CONDITIONAL EXPECTATION BASED VALUE DECOMPOSITION, CEVD

One of the fundamental drawbacks in NeurADP is that each agent/vehicle[2] to a large extent is kept
in oblivion about the values of the feasible actions for other agents/vehicles. Since our problem
execution (assignment of requests to agents) is centralized, this independence of individual agents
(as shown in experimental results) leads to sub-optimal actions for the entire system.

While there are dependencies between agents, not all agents are dependent on each other and one
mechanism typically employed to represent sparsely connected multi-agent systems is through the
use of a coordination graph [ Guestrin & Parr (2002); Li & Kochenderfer (2021)], CG = (X, E).
The joint value of the system with joint state s and joint action a in the context of a coordination
graph is given by:


_Q[CG](s, a) =_


_Q[CG]i_ (s, a); _Q[CG]i_ (s, a) = f _[i](a[i]_ _s) +_
_|_
_iX∈X_


_f_ _[ij](a[i], a[j]|s)_ (5)
_j|(i,jX)∈E_


where f _[i](.|.) represents the value of agent i and f_ _[ij](., .|.) represents the impact of agent j’s actions_
on agent i’s value. Such an approach is scalable if there are a few agents. However, when considering
thousands of agents and a central ILP which requires values for all different joint action pairs,
there is a combinatorial explosion making the model non deployable in real time. To put things
into perspective, assuming each agent has |A| feasible actions (request combinations) and there
are N (typically 1000) agents, the number of value evaluations jumps from N · |A| in DJV to
_N · |A|[2]_ while using a coordination graph. It should be further noted the A corresponds to request
combinations and hence can increase combinatorially.

Thus, we need a mechanism that is scalable while considering the impact of i on other agents. In the
well known Expectation Maximization algorithm [Dempster (1977)] for identifying missing data,
the likelihood is calculated by introducing a conditional probability of unknown data given known
data. In a similar vein, our method to deal with the unknown impact of other agents is by considering
conditional probability of agent j taking action aj given agent i takes action ai in state s. This will
ensure the overall value is dependent on individual agent values and not on joint values. More
specifically, the expected value of agent i is:


_Q[CG]i_ (s, a) = f _[i](a[i]_ _s) +_
_|_


_P_ (aj _ai, s)f_ _[j](a[j]_ _s)_
_|_ _|_
_j|(i,j)∈XE,aj_ _∈Aj_


To make this broad idea of conditional expectation operational in case of RMP, we have to address
multiple key challenges. We describe these key challenges and our ways of addressing them below.
Figure 2 provides the overall method, with step (II) outlining the conditional expectation idea and
the key difference from NeurADP described in Figure 1.

3.1 NO EXPLICIT/STATIC COORDINATION GRAPH

While it is clear that agents that are very far apart will not have any dependency, there is no explicit
coordination graph that is present in RMP. However, RMP has two characteristics that make it easier
to identify neighbouring agents for any given agent:

_• Agents that are nearby spatially are more probable to compete over the same set of requests and_
hence would have a dependency.

_• Agents/vehicles do not have identity, i.e., they are all homogenous._
Due to these characteristics, we can cluster the intersections in the road network (to capture spatial
dependencies) and consider agents at a time step in an intersection cluster as neighboring agents.
Due to homogeneity of agents, the only aspect of importance is whether there are agents (and not
which specific agents) competing for the same requests. Unlike previous works, the coordination
graph keeps changing at each time step, as agents move between clusters. At time t, an agent placed
at an intersection belonging to cluster Ck will coordinate with all other agents in cluster Ck.

We define function M : L −→ [K] to map each intersection of the road network into one of the
K clusters : _C1, C2, . . ., CK_ based on the average travel times between intersections. Because of
_{_ _}_
clustering locations and assigning agents to location clusters, the total number of agents becomes
less of an issue with respect to scalability.

2We will use agent and vehicle interchangeably.


-----

3.2 HOW TO CONSIDER IMPACT OF OTHER AGENTS IN THE CLUSTER?

Let us consider agent i present in cluster Ck at time t. The other agents in cluster Ck are agents
_j1, j2, . . ., jn and are termed its neigbours. In NeurADP, agent i credited action f ∈Ft[i]_ [with value]
_V_ _[i](s[i,f]t_ [)][ which is oblivious to the presence of neighbour agents. Since the execution is centralized,]
agent i can however weigh the losses/gains its action f has on the cluster by getting useful feedback from the individual values of other agents. Let us take a neighbour agent j ∈ _Ck (j ̸= i)_
having feasible actionsdistribution _g1, g2, . . ., gkj ∈Ft[j][. From agent][ i][’s perspective a conditional probability]_
_P_ (Agent j takes action g|Agent i takes action f) = P _[j](g|s[i]t[, f]_ [)]

is formed and the feedback term from agent j is written as _g∈Fj[t]_ _[P][ j][(][g][|][s]t[i][, f]_ [)][V][ j][(][s]t[j,g][)][.]

We do this for all the neighbours and take an average :

[P]


_P_ _[j](g|s[i]t[, f]_ [)][V][ j][(][s][j,g]t [)]

_gX∈Fj[t]_


_Ck_ 1
_|_ _| −_


_j∈Ck,j≠_ _i_


Now to calculate the value of agent i on taking action f, after getting this feedback, we take an
affine combination and write the new individual value as


_Vˆ_ _[i](s[i,f]t_ [) =]


_V (s[i,f]t_ [) +][ λ]


_P_ _[j](g|s[i]t[, f]_ [)][V][ j][(][s][j,g]t [)]


1 + λ


_Ck_ 1
_|_ _| −_


_j∈Ck,j≠_ _i_


_g∈Fj[t]_


where λ is a learnable parameter. It should be noted that this individual value not only considers
**_the future impact of current action, f_** **_, but also considers the impact on other agents._**

Our overall ILP objective thus becomes :

1 1

max _[i](s[i]t[, f]_ [) +][ γ] _V_ _[i](s[i,f]t_ [) +][ λ] _P_ _[j](g_ _s[i]t[, f]_ [)][V][ j][(][s][j,g]t [)] _a[i,f]t_

_J_ _λ + 1_ _Ck_ 1 _|_ _×_

Xi _fX∈Fi[t]_   _j∈CXk,j≠_ _i_ _|_ _| −_ _gX∈Fj[t]_ 

= max _J_ _[i](s[i]t[, f]_ [) +][ γ][ ˆ]V _[i](s[i,f]t_ [)] _× a[i,f]t_
Xi _fX∈Fi[t]_  

subject to feasibility constraints in expression 2.

**What should be the functional form for conditional probabilities?pickup location o[i]t** [K] which maps each intersection to its cluster. Each request u[i]t _[∈U][t]_ [has a]
Every action f is associated with some user request[∈L][. Recall function][ M][ :][ L −]→ u[i]t[, we define]

_At : Ft −→L_

which maps each action f to the corresponding request (u[i]t[)’s pickup intersection][ o][i]t[. Define the]
composition function
_Ct = M ◦Ut : Ft −→_ [K]
that maps each action to a cluster by the pickup location of the action’s corresponding user request.
conditional probability of agentd : [K] × [K] −→R[+] is defined as the average travel time between 2 clusters. We model the j taking action g given agent i takes action f as :

_P_ _[j](g|s[i]t[, f]_ [)][ ∝] _[e][(][α][·][d][(][C][t][(][g][)][,][C][t][(][f]_ [)))]

where α is a learnable parameter. The normalizing constant is computed by summing over actions
in Ft[j][.]

3.3 OVER/UNDER ESTIMATION OF INDIVIDUAL VALUES IN FV AND DJV:

NeurADP makes an optimistic assumption that individual agent will get to take the best action in
the next time step. Since central ILP decides the joint action, this can result in an overestimation
or underestimation of individual agent value. Due to this and other issues, in our experiments, we
found that NeurADP values can have significant errors compared to the discounted future rewards
as shown in Figure 3. We fix this problem through two key enhancements:


-----

Figure 3: Comparison of estimated value and discounted ”real” value for NeurADP, NeurADP+ and
CEVD.

_• Controlling large Variance of exogeneous information : Recall from Equation 4, to calculate_
values of post action states, NeurADP employs

_V_ _[a](s[a]t_ [) =][ E][[][V][ (][s][t][+1][)][|][s]t[a][, ξ][t][+1][]]

Here the exogenous information ξt+1 is the global demand (gt) at time t. Even within a small
number of consecutive epochs, the global demand displays a significant variance. This results
in individual values showing a large variance, instead of varying smoothly over time. We thus
consider expected discounted future demand,


_′_

_Ft+1 = E[_ _γ[t]_ _gt+t[′] ]_

_t[′]_ =0

X

(where T is large but finite horizon) which varies smoothly over time unlike the current demand.
In our approach, we consider exogenous information as ξt+1 = [gt, Ft].

_• Enforcing values to be positive : NeurADP models the value function as a shared parameter Neu-_
ral Network. The final layer of this Neural Network is a fully connected multi layer perceptron
(MLP) having range as the entire real line. However, as our objective function (number of requests served) is non-negative, negative values (admissible by NeurADP) are not reasonable. We
thus use a SoftPlus activation after the final MLP to ensure that the computed values are strictly
positive.
To evaluate the impact of the above modifications (calling the model NeurADP+), in Figure
3 we plot the following : _i_ _[V][ i][(][s]t[f][ i]t_ _[,i]) (ft[i]_ [is the action chosen for vehicle][ i][ at time][ t][) vs]
_Tt[′]_ =0 _[γ][t]′_ _Rt+t[′] where Rt is the total number of requests served at time t for NeurADP, Neu-_
rADP+ and CEVD. Notice how the gap between the Estimated Value curve and the Discounted[P]
PReward curve is very small in NeurADP+ and CEVD (as it should be by the Bellman Equation 3),
whereas the gap is quite significant for NeurADP. Note that the height of the graphs is different
and while NeurADP+ improves the quality of the estimation, CEVD is responsible for the bulk of
the performance gain.

4 ALGORITHM

Given a post decision state s[i,f]t [, we need a paremterized function to compute][ ˆ]V (s[i,f]t [)][.] Our
joint function _V[ˆ]θ,λ,α has 3 parameters : (i) θ : parameters of a Neural Network Based Indi-_
vidual Agent Value Function Estimator (as in NeurADP)[3], (ii) λ : parameter to control the importance given to an agent’s neighbours while taking an affine combination, (iii) α : parameter to control conditional probabilities P which controls the relative importance given to different feasible actions of neighbours. We infer the parameters step by step. Setting λ = 0, reduces this function to NeurADP (V[ˆ]θ,0,0). We first estimate optimal θ[∗] (following the alogrithm
in NeurADP). This gives us the NeurADP parameters, which are a good starting point to estimate values at an individual level. Now to estimate λ, we set α = 0 (this corresponds to uniform distribution over actions), and do a linear search on a set of sampled points on the real

3In this section by NeurADP we mean NeurADP updated with the proposals in 3.3


-----

line to find the optimal λ[∗] = maxλ _tt==0T_ _|iR=0|_ _J_ _[i](s[i]t[, f]_ [) +][ γ][ ˆ]V (s[i,f]t [)] _× a[i,f]t_ subject to con
 

straints in expression 2. At this stage, we haven’t changed the preference over actions from anP P
individual perspective, however for the central executor the values are now much more refined
as the individual over/under estimates have been smoothened by considering the neigbours. Finally we estimate α by linear search on a set of sampled points on the real line to get optimal

_α[∗]_ = maxα _tt=0=T_ _i|R=0|_ _J_ _[i](s[i]t[, f]_ [)+] _[γ][ ˆ]V (s[i,f]t_ [)] _×_ _a[i,f]t_ subject to constraints in expression 2. We

 

can now compute values on unseen data usingP P _V[ˆ]θ[∗],λ[∗],α[∗]_ .

5 EXPERIMENTS


The goal of the experiments is to compare the performance of our approach CEVD to NeurADP[Shah et al. (2020)](henceforth referred to as baseline), which is the current best approach
for solving the RMP. We make this comparison on a real-world dataset [NYYellowTaxi (2016)]
across different RMP parameter settings. We quantitatively justify our performance by comparing
the service rate, i.e., the percentage improvement on the total requests served. We vary the following
parameters: the maximum allowed waiting time τ from 90 seconds to 150 seconds, the number of
vehicles |R| from 500 to 1000 and the capacity C from 4 to 5. The value of maximum allowable
detour delay λ is taken as 2 ∗ _τ_ . The decision epoch duration ∆ is taken as 60 seconds.

**Setup: We perform our experiments on the demand distribution from the publicly available New**
York Yellow Taxi Dataset [NYYellowTaxi (2016)]. The experimental setup is similar to the setup
used by [Shah et al. (2020)]. Street intersections are used as the set of locations L. They are
identified by taking the street network of the city from openstreetmap using osmnx with ’drive’
network type [Boeing (2017)]. Nodes that do not have outgoing edges are removed, i.e., we take
the largest strongly connected component of the network. The resulting network has 4373 locations
(street intersections) and 9540 edges. The travel time on each road segment of the street network
is taken as the daily mean travel time estimate computed using the method proposed in [Santi et al.
(2014)]. We further cluster these intersections L into K clusters using K-Means Clustering based
on the average travel times between different intersections. We choose the value of K based on the
number of vehicles. K is chosen to be 100,150 and 200 for 500,750 and 1000 vehicles respectively.
Similar to previous work, we only consider the street network of Manhattan as a majority (∼75%)
of requests have both pickup and drop-off locations within it. The dataset contains data about past
customer requests for taxis at different times of the day and different days of the week. From
this dataset, we take the following fields: (1) Pickup and drop-off locations (latitude and longitude
coordinates) - These locations are mapped to the nearest street intersection. (2) Pickup time - This
time is converted to appropriate decision epoch based on the value of ∆. The dataset contains on an
average 322714 requests in a day (on weekdays) and 19820 requests during peak hour.

We evaluate the approaches over 24 hours on different days starting at midnight and take the average
value over 5 weekdays (4 - 8 April 2016) by running them with a single instance of initial random
location of taxis [4]. CEVD is trained using the data for 8 weekdays (23 March - 1 April 2016) and
it is validated on 22 March 2016. For the experimental analysis, we consider that all vehicles have
identical capacities.

**Results :** We compare CEVD to NeurADP (referred to as baseline). Table 1 gives a detailed
performance analysis for the service rates of CEVD and baseline. Here are some key observations:
**Effect of changing tolerance to delay, τ** **: CEVD obtains a 9.37% improvement over the baseline**
approach for τ = 90 seconds. The difference between the baseline and CEVD decreases as τ
increases. The lower value of τ makes it difficult for vehicles to accept new requests while satisfying
the constraints for already accepted requests. The neighbouring vehicles’ interactions in CEVD
prevents a vehicle from picking up requests it values highly however which would have been more
suitable given the delay constraints for some other vehicle and instead picks up requests which it
might value less but still is feasible. Thus the overall requests served increases.
**Effect of changing the capacity, C : CEVD obtains a 9.76% gain over baseline for capacity 5. The**

4All experiments are run on 60 core - 3.8GHz Intel Xeon C2 processor and 240GB RAM. The algorithms
are implemented in python and optimisation models are solved using CPLEX 20.1


-----

|Varying|Parameters|Col3|Col4|Baseline|Our Approach|Col7|
|---|---|---|---|---|---|---|
||Number of Vehicles|Pickup Delay|Capacity|Requests Served|Requests Served|Percentage Improvement|
|Pickup Delay|500|90|4|90286.8 2108.78 ±|98748.2 2449.38 ±|9.37 0.59 ±|
||500|120|4|103933.0 2604.05 ±|113184.0 2774.00 ±|8.90 0.23 ±|
||500|150|4|113051.8 2771.45 ±|117351.6 2818.49 ±|3.80 0.24 ±|
|Number of Vehicles|500|90|4|90286.8 2108.78 ±|98748.2 2449.38 ±|9.37 0.59 ±|
||750|90|4|129791.6 3516.83 ±|139365.6 3853.98 ±|7.38 0.38 ±|
||1000|90|4|165110.2 4677.10 ±|175453.4 5173.82 ±|6.26 0.18 ±|
|Capacity|500|90|4|90286.8 2108.78 ±|98748.2 2449.38 ±|9.37 0.59 ±|
||500|90|5|91509.4 2144.54 ±|100443.8 2502.34 ±|9.76 0.38 ±|


Table 1: Detailed Quantitative Results

Figure 4: This graph compares the number of requests served as a function of time. The bold lines
represent a moving average for different configurations averaged over requests from 4-8 April 2016.

difference between the baseline and CEVD increases as the capacity increases as for higher capacity
vehicles, there is a larger scope for improvement if vehicles cooperate well.
**Effect of changing the number of vehicles, |R|: CEVD obtains a 9.37% improvement over the**
baseline for capacity |R| = 500. The difference between the baseline and CEVD decreases as the
number of vehicles increase as in the presence of a large number of vehicles, there will always be a
vehicle that can serve the request. As a result, the quality of assignments plays a smaller role.

We further analyse the improvements obtained by CEVD over baseline by comparing the number of
requests served by both approaches at each decision epoch throughout the day. Figure 4 shows the
number of requests served by the baseline and CEVD at different decision epochs[5]. As shown in the
figure, initially at night time when the demand is low both approaches serve all available demand.
During the transition period from low demand to high demand period, the baseline algorithm starts
to choose suboptimal actions without considering the impact of each vehicle’s action on the whole
system while CEVD is able to capitalize on the joint action values and serve much more requests
than the baseline.

The approach can be executed in real-time settings. The average time taken to compute each batch
assignment using CEVD is less than 60 seconds (for all cases) [6]. These results indicate that using
our approach can help ride-pooling platforms to better meet customer demand.

6 CONCLUSION

Due to the matching required on a tri-partite graph between user requests, trips (combination of
user requests) and vehicles, on-demand ride pooling is challenging. Improving on existing methods,
we provide a scalable novel value decomposition method based on conditional probabilities, where
individual value is not only able to consider future impact of current matches but also impact on other
agent values. This new approach is able to outperform the best existing method in all settings of the
benchmark taxi data set employed for on-demand ride pooling by margins of up to 9.79%. To put
this result in perspective, typically, an improvement of 1% is considered a significant improvement
on ToD for an entire city [Xu et al. (2018); Lowalekar et al. (2019)].

5Results for other settings shown in appendix
660 seconds is the decision epoch duration considered in the experiments


-----

REFERENCES

Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. Ondemand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the Na_tional Academy of Sciences, pp. 201611675, 2017._

Xiaohui Bei and Shengyu Zhang. Algorithms for trip-vehicle assignment in ride-sharing. 2018.

Geoff Boeing. Osmnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, Environment and Urban Systems, 65:126–139, 2017.

et al. Dempster, A. P. Maximum likelihood from incomplete data via the em algorithm. Journal of
_the Royal Statistical Society. Series B (Methodological), 1977._

Koller D. Guestrin, C. and R. Parr. Multiagent planning with factored mdps. In Neural Information
_Processing Systems, 2002._

Yan Huang, Favyen Bastani, Ruoming Jin, and Xiaoyang Sean Wang. Large scale real-time ridesharing with service guarantee on road networks. Proceedings of the VLDB Endowment, 7(14):2017–
2028, 2014.

Gupta J.K. Morales P. Allen R. Li, S. and M.J. Kochenderfer. Deep implicit coordination graphs
for multi-agent reinforcement learning. In International Conference on Autonomous Agents and
_Multi-Agent Systems, AAMAS, 2021._

Kaixiang Lin, Renyu Zhao, Zhe Xu, and Jiayu Zhou. Efficient large-scale fleet management via
multi-agent deep reinforcement learning. In Proceedings of the 24th ACM SIGKDD International
_Conference on Knowledge Discovery &#38; Data Mining, pp. 1774–1783. ACM, 2018._

Meghna Lowalekar, Pradeep Varakantham, and Patrick Jaillet. ZAC: A zone path construction
approach for effective real-time ridesharing. In Proceedings of the Twenty-Ninth International
_Conference on Automated Planning and Scheduling, ICAPS 2018, Berkeley, CA, USA, July 11-_
_15, 2019., pp. 528–538, 2019._

Meghna Lowalekar, Pradeep Varakantham, and Patrick Jaillet. Zone path construction (zac) based
approaches for effective real-time ridesharing. Journal of Artificial Intelligence Research, JAIR,
2021.

Shuo Ma, Yu Zheng, and Ouri Wolfson. T-share: A large-scale dynamic taxi ridesharing service.
In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pp. 410–421. IEEE,
2013.

[NYYellowTaxi. New york yellow taxi dataset. http://www.nyc.gov/html/tlc/html/](http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml)
[about/trip_record_data.shtml, 2016.](http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml)

Warren B Powell. Approximate Dynamic Programming: Solving the curses of dimensionality, volume 703. John Wiley & Sons, 2007.

Samvelyan M. Schroeder C. Farquhar G. Foerster J. Rashid, T. and S Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International
_Conference on Machine Learning, ICML, 2018._

Stuart J Russell and Andrew Zimdars. Q-decomposition for reinforcement learning agents. In
_Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 656–663,_
2003.

Paolo Santi, Giovanni Resta, Michael Szell, Stanislav Sobolevsky, Steven H Strogatz, and Carlo
Ratti. Quantifying the benefits of vehicle pooling with shareability networks. Proceedings of the
_National Academy of Sciences, 111(37):13290–13294, 2014._

Sanket Shah, Meghna Lowalekar, and Pradeep Varakantham. Neural approximate dynamic programming for on-demand ride-pooling. In Proceedings of the AAAI Conference on Artificial
_Intelligence, volume 34, pp. 507–515, 2020._


-----

Lever G. Gruslys A. Czarnecki W. M. Zambaldi V. F. Jaderberg M. Lanctot M. Sonnerat N. Leibo
J. Z. Tuyls K. Sunehag, P. and T. Graepel. Value- decomposition networks for cooperative multiagent learning based on team reward. In International Conference on Autonomous Agents and
_Multi-Agent Systems, AAMAS, 2018._

Yongxin Tong, Yuxiang Zeng, Zimu Zhou, Lei Chen, Jieping Ye, and Ke Xu. A unified approach
to route planning for shared mobility. Proceedings of the VLDB Endowment, 11(11):1633–1646,
2018.

Zhe Xu, Zhixin Li, Qingwen Guan, Dingshui Zhang, Qiang Li, Junxiao Nan, Chunyang Liu, Wei
Bian, and Jieping Ye. 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, pp. 905–913. ACM, 2018._


-----

