Conditional Expectation based Value Decomposition for Scalable On-Demand Ride Pooling
Authors: Avinandan Bose
Pradeep Varakantham
Venue: ICLR 2022 Submitted (2022)
Keywords: Ride-Pool Matching Problem(RMP)
Value Decomposition
Approximate Dynamic Programming(ADP)
Reinforcement Learning

Abstract: Owing to the benefits for customers (lower prices), drivers (higher revenues), aggregation companies (higher revenues) and the environment (fewer vehicles), on-demand 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. 

Under review as a conference paper at ICLR 2022
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), ag- gregation companies (higher revenues) and the environment (fewer vehicles), on- demand ride pooling (e.g., Uber pool, Grab Share) has become quite popular. The significant computational complexity of matching vehicles combinations of re- quests has meant that traditional ride pooling approaches are myopic in that they do not consider the impact of current matches on future value for vehieles/drivers.
Recently, Neural Approximate Dynamic Programming (NeurADP) has employed value decomposition with Approximate Dynamic Programming (ADP) outper- form leading approaches by considering the impact of an individual agent's s (vehi- cle) chosen actions on the future value of that agent. However, in order 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 indi- vidual value can have 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 con- ditional probabilities for capturing dependencies increasing the complexity of training or decision making. We show that our new approach, Conditional Expectation based Value Decomposition (CEVD) outper- forms NeurADP by up to 9.76% in terms of overall requests served, which is a significant improvement city wide benchmark taxi dataset.
other agents actions without
INTRODUCTION
Taxi/car on Demand (ToD) services (e.g., UberX, Lyft, Grab) not only provide comfortable means of transport for customers, but also are good for the environment by enabling sharing of vehicles over time (while being used serve one request any one point in time). A further improvement of ToD on-demand ride pooling (c.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 on- Demand (ToD) services. This is achieved while providing benefits 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 city scale. referred as Ride- Pool Matching Problem (RMP) [Alonso-Mora et al.) (2017); Bei & Zhang (2018); Lowalekar et al. [. The goal in an RMP is assign combinations of user requests 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 tripartite graph of requests, trips (combinations requests) and vehicles. This matching on tripartite graph significantly increases the complexity of solving RMP online, especially at city scale where

---

Under review as a conference paper at ICLR 2022
there are hundreds 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 al. (2017)] While these scale well, they myopic and, as a result, do not consider the impact of given assignment on future assignments. The closest works of relevance to this paper are by Shah al. (Shah et al. (2020)] and Lowalekar el al. [Lowalekar et al. (2021)]. We specifically focus on the work by Shah el 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 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. Guuestrin& & Parr (2002)] and Li al. (Li & Kochenderfer [2021]] ] to solve problems with no explicit coordination graphs and hundreds/thousands of homogeneous agents. Unlike value decom- position approaches (Rashid & Whiteson (2018); [Sunehag {Suneaaa & Graepel (2018) developed for solving cooperative Multi-Agent Reinforcement Learning (MARL) with tens of agents and under central- ized 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 achieve- ment [Lin et al. (2018)). we demonstrate that our approach easily outperforms the existing best ap- proach, NeurADP [Shah et al. (2020)] by at least 3.8% and up 9.76% on a wide variety of settings for the benchmark real world taxi dataset YeYYellow Taxi (2016)).
2 BACKGROUND
In this section, we formally describe the RMP problem and also provide details of an existing ap- proach 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 C as nodes, road segments: & 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 winnww called the decision epoch A. The goal of the RMP is to match these collected requests Ue to empty or partially filled vehicles that can serve them such that an objective J is maximised subject to constraints the delay D.
We upperbound D and consider the objective I to be the number of requests served. Thus, RMP is defined using the tuple [G,U, R,R,R.R.. D. A. T Please refer Appendix A.1 for a detailed description.
Delay constraints D consider two delays, {T, 2T}. T denotes the maximum allowed pick-up delay which is the difference between the arrival time of a request and the time at which vehicle picks the user up. 27 denotes the maximum allowed detour delay which is the difference between the time which the user arrived their destination in shared cab and the time which they would have arrived if they had taken a single-passenger cab.
Neural Approximate Dynamic Programming (NeurADP) for Solving RMP: Figure I 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, method for solving the underlying Approx- imate Dynamic Program (ADP) [Powell [207)] by considering neural network represen- tations of value functions.
Everywhere in the paper [.] is used the concatenation operator
2

---

Under review as a conference paper at ICLR 2022
A. Get Requests
B. Generate Feasible Trips
C. Score Feasible Trips
Neural Netwerk (NN)
t
60
1.6
F. Simulate Motion
E. Update Score Function
D. Assign According ILP
1B
t
Reward
Time: T
L
Figure I: NeurADP approach Shah et al. [2020)]
DJV: 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 Markov Decision Problem (MDP) with the key difference that the transition uncertainty extrinsic 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 8; = (rr, uz) where r is the state of all vehicles and or contains all the requests waiting to be served. The state obtained in Step A of Figure |
A At each time step there are large number of requests arriving to the taxi service provider, however for an individual vehicle only small number of such requests are reachable. The feasible set request combinations for each vehicle time 1, Fi is computed Step Figure
F = 1f'1 U - PickUpDelayy(" .)) < т, DetourDelayy (f', .)) s 2T}
ag f.f is the decision variable that indicates whether vehicle i takes action (a combination of requests) at a decision epoch Joint actions across vehicles have satisfy matching constraints: (i) each vehicle, i can only be assigned at most one request combination, f; (ii) at most one vehicle, can be assigned to request j; and (iil) vehicle, can be either assigned or not assigned to request combination.
Σ a =1 VIER /eFi
Σ
Σ d' (0.1 Vi. (2) FEFjUES
::
< denotes the exogenous information the source of randomness the system. This would correspond to the user requests or demand. & denotes the exogenous information at time t.
T denotes the transitions of system state. In an ADP, the system evolution happens as (so, do si. S1, (1, sf, ... 8t, at, ...,, where s; denotes the pre-decision state decision epoch é and of denotes the post-decision state (Powell (2007)). The transition from state to 8141 depends on the action vector a, and the exogenous information E1+1- Therefore,
8t+1 T(st, az, E++1); (s,,,, a:); se+1 7 (x41)
It should be noted that (...) is deterministic uncertainty is extrinsic to the system.
J denotes the reward function and in RMP, this will be the revenue from trip. Let (sx) denotes the value being in state 8, at decision epoch 4, then using Bellman equation:
(st) = max (J(s,, ar) + (E((( azs E++1) a.EA,
(3)
3

---

Under review as a conference paper at ICLR 2022
(1) Get Requests, Compute Feasible Actions, Find Individual Values
(II) Score Values considering consequences other vehicles
KIAL
1
LDI
Pay, pla(6) + (1 p)
PaΛ (15(6)) + (ms)
[Espected Vatue conditored
[Erpected Vatue iy cenctiooed
(A)) wit (A) +11 Pay
(A))) = wV)()) wyPas.
(Neighbour
(Il))Solve using Neighbour aware scores, aesign optimal actions, simulate
Indeger Linear
Prog (LP))
Optimal Chosah
W
Figure 2: Schematic outlining CEVD's neighbour aware scoring mechanism
where y is the discount factor. Using post-decision state, this expression breaks down nicely:
V(sc) max açE
+
v* = ([
(4)
The advantage of this two step value estimation is that the maximization problem in Equation can be solved using Integer Linear Program (ILP) with matching constraints indicated in ex- pression 2 Step D of Figure provides this aspect of the overall algorithm. The value function approximation around post-decision state, (*(s)) is a neural network and is updated (Step E of Figure I by stepping forward through time using sample realizations of exogenous information
(i.c. demand observed in data). However, as we describe next, maintaining 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 sources/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 the sum (sf)).
over individual value functions
V(sf)
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 the current time step. Thus they model the value function using the pre-decision, rather than post-decision, state of other vehicles which gives :
(*())) = ([s) a sT z ('( sf1)
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(st) Σ, Vis;'""" s(]).
They then evaluate these individual Vi values (Step C of Figure for all possible s. (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 non-linear value function from exponential to linear in the number of vehicles.
4

---

Under review as a conference paper at ICLR 2022
3 CONDITIONAL EXPECTATION BASED VALUE DECOMPOSITION, DECOMPOSITION, CEVD
One of the fundamental drawbacks in NeurADP is that each agent/vchicld" a large extent is kept in oblivion about the values of the feasible actions for other agents/vchicles. Since 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 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 and joint action the context of coordination graph is given by:
(00(s,)) = Ef
(s)
(a' E (d al'ss
(S)
S(GJ)EE
where (((-.) represents the value of agent and f 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 II. 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 (typicallyy 1000) agents, the number of value evaluations jumps from N |A| in DJV to N LA|2 while using a coordination graph. It should be further noted the A corresponds to request combinations and hence increase combinatorially.
Thus, we need 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 similar vein, our method to deal with the unknown impact of other agents is by considering conditional probability of agent j taking action given agent takes action a; in state This will ensure the overall value dependent on individual agent values and on joint values. More specifically, the expected value of agent i is:
(s, f' s)+
Σ ai
(a))(s)
To make this broad idea of conditional expectation operational in case of RMP, we have 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]
3.1 No EXPLICIT/STATIC COORDINATION GRAPII
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 characteristies 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 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 time step in intersection cluster 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 I, an agent placed an intersection belonging to cluster C₁ will coordinate with all other agents in cluster Ct.
We define function M - [K] to map each intersection of the road network into one of the 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.
K clusters
We will agent and vehicle interchangeahly.
5

---

Under review as a conference paper at ICLR 2022
3.2 How TO CONSIDER IMPACT OTHER AGENTS THE CLUSTER?
Let us consider agent present in cluster Cs at time L. The other agents in cluster C2, are agents J1,J2,..... In and are termed its neigbours. In NeurADP, agent credited action E Fi with value (s which is oblivious to the presence of neighbour agents. Since the execution centralized, agent i can however weigh the losses/gains its action has on the cluster by getting useful feed- back from the individual values of other agents. Let us take neighbour agent j E Cs (j + i) having feasible actions 91, 92. 9k; E F.P From agent i's perspective a conditional probability distribution
P(Agent j takes action g Agent takes action f) = P' ('(g)))..)
is formed and the feedback term from agent is written as Egery P3 ( f)
We do this for all the neighbours and take an average:
E E Pi
|C&|
JECU 9EF3
Now to calculate the value of agent taking action f, after getting this feedback, we take an affine combination and write the new individual value as
(5t
1+ v(s +
1
Cal
JECLJTi
where À is learnable parameter. It should be noted that this individual value not only considers the future impact of current action, J, but also considers the impact on other agents.
Our overall ILP objective thus becomes:
max ΣΣ
(st.
- (++))
Σ jeCa.
E Pd ('ilsti, az 9E
Cil -1
SEF
= max ΣΣ
J(h FEF!
x a.
subject feasibility constraints in expression 2
What should be the funetional form for conditional probabilities? Each request un E U4 has pickup location of E C. Recall function M : C - [K] which maps each intersection to its cluster. Every action is associated with some user request w/, we define
A F; - L
which maps each action f to the corresponding request (ut)'s pickup intersection of. Define the composition function
C = M oll :F - [K]
that maps each action to a cluster by the pickup location of the action's corresponding user request.
: [K] x [K] - R+ is defined as the average travel time between clusters. We model the
conditional probability of agent taking action given agent takes action f as
pl (glo),, f) x e (a)d(ic(())...(1))
where a is learnable parameter. The normalizing constant computed by summing over actions in F..
3.3 OVER/UNDER ESTIMATION OF INDIVIDUAL VALUES 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 underestimation of individual agent value. Due to this and other issues, in our experiments, found that NeurADP values can have significant errors compared to the discounted future rewards shown in Figure 3 We fix this problem through key enhancements:

---

Our Under review as a conference paper at ICLR 2022
800
1.0
M0-
20-
15
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 values of post action states, NeurADP employs
to calculate
(sf) (V)((s))))s
Here the exogenous information Č1+11 is the global demand (g:) at time t. Even within 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,
T
Fi-1 = E
Σ r d'=0
9e+el
(where T' is large but finite horizon) which varies smoothly over time unlike the current demand. In our approach, we consider exogenous information as E++1 = [g,, Fe).
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 fully connected multi layer perceptron (MLP) having range as the entire real line. However, as our objective function (number of re- quests 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 we plot the following Σ, (sff Ui the action chosen for vehicle i at time /) vs oo R2ys' where R. is the total number of requests served at time t for NeurADP, Neu- TADP+ and CEVD. Notice how the gap between the Estimated Value curve and the Discounted Reward curve is very small in Neur and CEVD (as it should be by the Bellman Equation 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 we need a paremterized function to compute ((sh (( )
joint function Ve, has 3 parameters (i) 0 parameters of a Neural Network Based Indi- vidual Agent Value Function Estimator (as in NeurADP
(ii) X parameter to control the im- portance given an agent's neighbours while taking an affine combination, (iii) parame- ter to control conditional probabilities P which controls the relative importance given to differ- ent feasible actions of neighbours. We infer the parameters step by step. Setting À O, re- duces this function to NeurADP (Ve,..)) We first estimate optimal 0" (following the alogrithm in NeurADP). This gives us the NeurADP parameters, which are good starting point to esti- mate values at an individual level. Now to estimate X, we set a = 0 (this corresponds to uni- form distribution over actions), and do linear search
set of sampled points on the real
In this section by NeurADP mean NeurADP updated with the proposals in 3.3

---

Under review as a conference paper at ICLR 2022
line to find the optimal X max En E.
+ x a subject to con-
straints in expression 2 At this stage, we haven't changed the preference over actions from an 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 neighours. Fi- nally we estimate a by linear search on a set of sampled points on the real line to get optimal
x af subject constraints in expression We can now compute values on unseen data using Vo-
a" max E E
5 EXPERIMENTS
The goal of the experiments is to compare the performance of our approach CEVD to Neu- rADP[Shah et al. (henceffoo referred to as baseline), which is the current best approach real-world dataset [NYYelloWTaxi) [2016]]
for solving the RMP. We make this comparison 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 T 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 * T. The decision epoch duration A is taken as 60 seconds.
We perform our experiments on the demand distribution from the publicly available New York Yellow Taxi Dataset [NYYellowTaxx) (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| (. 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 the daily mean travel time estimate computed using the method proposed in [Santi et al. [. We further cluster these intersections L into 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 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 the nearest street intersection. (2) Pickup time- This time is converted to appropriate decision epoch based on the value of A. The dataset contains on an average 322714 14 requests in a day (on weekdays) and 19820 requests during peak hour.
Sctup:
majority (~75%)
We evaluate the approaches over 24 hours on different days starting at midnight and take the average value over weekdays (4 8 April 2016) by running them with a single instance of initial random location of taxis [l 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.
We compare CEVD to NeurADP (referred to as baseline). Table gives a detailed performance analysis for the service rates of CEVD and baseline. Here are some key observations: Effect of changing tolerance to delay, 7: CEVD obtains a 9.37% improvement over the baseline approach for
Results :
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 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
All experiments are run on 60 core 3.8GHz Intel Xeon C2 processor and 240GB RAM. The algorithms implemented in python and optimisation models are solved using CPLEX 20.1
8

---

Under review as a conference paper at ICLR 2022
Parameters Pickup Delay
Baseline
Our Approach
Varying
Number of
Requests
Requests
Percentage
Capacity
Vehicles
Served
Served
Improvement
500
90
4
90286.8 2108.78
98748.2
9.37
Pickup
500
120
4
103933.0- 2604.05
113184.04-774..00
8.90-H0.23
Delay
500
150
4
1130518:2771.45
11735L.612818.49
3.80
Number
500
90
4
90286.8#2100.778
98748.2442449.38
9.37=00.59
of
750
90
4
123791.61:351.883
139365.6113853.98
7.38:10.38
Vehicles
1000
90
4
165110.2:::667.10
175453.4
6.26:10.18
500
90
4
90286.8::2008
98748.2 28744.2212449.38
9.37::0.59
Capacity
500
90
5
41149.4
100443.84:250..4
9.76:10.38
Table 1: Detailed Quantitative Results
340
(A)N 500, 90sccs, C
(B)N 750, r 90sccs,
(C)N 1000, r 90sccs,
This graph compares the number of requests served as function of time. The bold lines represent a moving average for different configurations averaged over requests from 4-8 April 2016.
Figure 4:
difference between the baseline and CEVD increases as the capacity increases as for higher capacity vehicles, there is larger scope for improvement if vehicles cooperate well.
Effect of changing the number of vehicles, [R]: CEVD obtains 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 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 each decision epoch throughout the day. Figure 4 shows the number of requests served by the baseline and CEVD at different decision epoch:] 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 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 compute each batch assignment using CEVD less than 60 seconds (for cases) [ These results indicate that using our approach can help ride-pooling platforms to better meet customer demand.
CONCLUSION
Due the matching required 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 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 to 9.79%. To put this result in perspective, typically, an improvement of 1% is considered significant improvement on ToD for an entire city [Xu et al. (2018) Lowalekar et al. (2019)].
RRssltt for other settings shown in appendix '60 seconds is the decision epach duration considered in the experiments

---

Under review as a conference paper at ICLR 2022
REFERENCES
Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. On- demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the Na- tional Academy of Sciences, pp. 20161 1675, 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 com-
plex street networks. Computers, Environment and Urban Systems, 65:126-139, 2017.
al. Dempster, A. P. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statisfical Society. Series B (Methodological), 1977.
Koller D. Guestrin, C. and 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 rideshar- ing with service guarantee on road networks. Proceedings of the VLDB Endowment, 7(1))20177- 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 Autonomous Agents and Mulli-Agent Systems, AAMAS, 2021.
Kaixiang Lin, Renyu Zhao. Zhe Xu, and Jiayu Zhou Efficient large-scale fleet management via multi-agent deep reinforcement learning. Proceedings of the 24th ACM SIGKDD International Conference 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 2288533,110 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.
YelllooTaxii. New york yellow taxi dataset. http:://ww..nng.oooo///tt//t/t//
about wtwor/rrpppprrrrdrreeeeeedddeeee shtml 2016.
Warren B Powell. Approximate Dynamic Programming: Solving the curses of dimensionality, vol- ume 703. John Wiley Sons, 2007.
Samvelyan M. Schroeder C. Farquhar G. Foerster J. Rashid, T. and S Whiteson. Qmix: Mono- tonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, ICMI., 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, 11 111(3 13000-12220222 2014.
Sanket Shah, Meghna Lowalekar, and Pradeep Varakantham. Neural approximate dynamic pro- gramming for on-demand ride-pooling. Proceedings of the AAAÍ Conference on Artificial Intelligence, volume 34, pp. 507-515, 2020.
10

---

Under review as a conference paper at ICLR 2022
Lever G. Gruslys A. Czarnecki W. M. Zambaldi V. F. Jaderberg M. Lanctot M. Sonnerat N. Leibo Z. Tuyls K. Sunehag, P. and Graepel. Value- decomposition networks for cooperative multi- agent 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 on-demand ride-hailing platforms: A learning and planning approach. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 905-9999 913. ACM, 2018


Reviews:
[{"review_id": "UtsBGGtH1w4", "reviewer": "Reviewer_Siyp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- Ridesharing (pooling) is a challenging domain for RL/ADP. The paper presents an incremental step forward on top of NeurADP for the matching problem.\n- The paper proposes a way to incorporate agent interactions with neighbors without relying on joint action values, which suffer from the curse of dimensionality.\n- Different values of problem configuration parameters are investigated in the experiments.\n- The experiment dataset is public so that reproducing the results is possible.\n\n\nWeaknesses and comments\n- The paper uses the number of completed requests as the problem objective. In practice, a common measure for ride-pooling is the ratio between the sum of completed individual trip distances (as if they were fulfilled as single trips) and the total distance that the drivers actually travel to fulfill those requests. This metric measures both the amount of request fulfilled and the quality of the pooling.\n\n- The proposed estimation of agent interaction effect involves a handcrafted conditional agent probability based on a softmax over distance between destination pairs. There's no empirical justification on this choice. Why should the probability based on how far away are the action destinations? And, matching decision is ultimately a system decision, so shouldn't it be learned from data of system decisions?\n\n- Figure 3: This may not be the impact of enforcing positive values. This is just showing that CEVD learns the individual values better than NeurADP. It could be because of its consideration of impact on neighboring agents. I suggest the authors do a more careful ablation study to separate the effect of multiple algorithmic differences.\n\n- Section 4: For finding optimal \\lambda, I don't see \\lambda appearing here in the expression. How did you tune it exactly?\n\n- The paper claims that the algorithm can be executed in real-time setting. However, the decision epoch in practice is much shorter, only a few seconds. A run time of 60 seconds to compute a matching decision is way too slow for 'real-time execution'.\n\n- There are too many mentions of \"e.g., Uber, Lyft, and Grab\". Once is good enough, and we all know they are well-known ridesharing companies.", "summary_of_the_paper": "This paper considers the ridesharing matching problem and builds the solution upon NeurADP. The main contribution over NeurADP is that the action values of each agent (vehicle) takes into account the impact of its action on the neighboring agents within the same cluster, which is obtained through clustering of the intersections on the road network. The impact of agent's action on neighbors is measured by the neighboring agents' independent values weighted by their action probabilities conditional on the agent's action. Benchmarking was performed on the NYC taxi data set against NeurADP. Results on different values of tolerance for delay, capacity, and number of vehicles are reported, and a significant improvement is demonstrated in all cases. ", "summary_of_the_review": "The paper improves upon NeurADP by proposing a way to incorporate agent interactions without resorting to joint action values. While there's some merit in technical contribution in this regard, there are a number of major issues in algorithmic justification and empirical validation. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4FomREpFr8x", "reviewer": "Reviewer_9FHL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Pros and Cons\n\n## Pros\n- The performance gain achieved by the paper is quite significant from the application perspective.\n- The idea of considering the effect of other agents seems to be correct and valuable for multi-agent decision-making problems like ToD systems.\n- The computational efficiency is shown (i.e., the optimization is done within the batch time of 60 seconds).\n\n## Cons\n\n- Some notations are not clearly defined, and it is hard to follow the details of the CEVD and its idea.\n\n# Comments\n\nTo clearly understand the paper and clarify its score, I would like to clarify the following point.\n\n(I) Many notations in Sec. 2 are not explained or defined. These notations or missing explanations make readers hard to follow the proposed study and know the difference between NeurADP and CEVD.\n\nThe below are examples.\n\n(I-1) Eq.(1): What is $[\\mathcal{U}]^{c'}$?\n\n(I-2) Between Eq.(2) and Eq.(3): What are $T^a(\\cdot,\\cdot)$ and $T^\\xi(\\cdot, \\cdot)$?\n\n(I-3) Page 4: What is $V^i(\\big\\langle r_t^{i,a}, r_t^{-i,a}\\big\\rangle)$? I cannot follow this $\\langle\\cdot\\rangle$ notation.\n\n(I-4) Page 4: What is the definition of $r_t^a$?\n\n(I-5) Page 5 before sec 3.1: $\\sum_{j\\in E}$ means $\\sum_{j|(i, j)\\in E}$? What is the difference between Pr and P?: $\\mathit{Pr}(a_j\\mid a_i, s)$ and $\\mathit{P}(\\text{Agent j takes action g | Agent i takes action f})$.\n\n(I-6) Page 5: What is the definition of $P^j$. Agent $j$'s probability?\n\n(I-7) Page 6: What is the definition of $s_t^{i,f}$?\n\n(I-8) Page 7: What is the definition of this bracket $[g_t, F_t]$ of $\\xi_{t+1}$?\n\n(II) What are 'other issues' of the over/under estimation of individual values in FV and DJV? (Page 6). Please give an example of such issues.\n\n(III) In optimization (sec 4), the proposed method estimates $\\theta, \\lambda, \\alpha$ step by step. Please clarify the property of this optimization problem. Are the resulted $\\lambda^\\star,\\alpha^\\star,\\lambda^\\star$ are globally optimal?\n\n(IV) Please clarify the relation between experimental results with the size $N$. That is, experimental results are reported only with $N=500, 750, 1000$. However, some research have modeled the ToD service with more agents (e.g., 3000 agents in [Alonso-Mora et al. 2017]), and therefore, I'm interested in more details of this aspect.\n\nFor example, the authors reported that \"The average time taken to compute each batch assignment using CEVD is less than 60 seconds (for all cases)\". Is this due to the size $N\\leq 1000$ or not?\n\nFurther, are computational results affected by the clustering ($k$-means) or not?\n\n(V) Please clarify the overview of the computation of CEVD (e.g., with a pseudo-code or system overview). What are the input and output? How is the ILP solver (CPLEX) used? Which part consumed the time within 60 seconds? I guess that such additional information is helpful for readers.", "summary_of_the_paper": "This paper studies an RPM problem (ride-pool matching problem) for on-demand transportation services. This problem is recently studied in various papers, but it is hard to choose a good matching by just using a bipartite graph matching due to the future demands, and it is an online decision-making problem.\n\nA recent breakthrough, NeurADP by [Shah et al. 2020], has shown a good performance, but the proposed approach in the paper, CEVD, achieved much more performance gain (reported as 3.8%-9.76%), which has a significant impact on the ToD service. An essential technique of the proposed CEVD is considering the effect of other agents (i.e., other vehicles) when estimating the value of actions.", "summary_of_the_review": "To the best of my knowledge and experiences, the achieved performance of CEVD seems to show important progress on the ToD services. The computational times and settings are reasonable.\n\nHowever, the paper contains some unclarified notations. It is hard to follow the details of the proposed method. I want the authors to give more explanations and clarify some parts to help readers, which is also important to increase my review score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2LqWRkvQO6_", "reviewer": "Reviewer_kKMH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed approach in the paper considers the impact of other agents actions on individual value by computing conditional expectations to improve the overall performance. The experimental results verify that the CEVD is an effective method for improving the overall requests served by 9.76 compared to the baseline, which seems promising. This work is quite innovative and the paper is generally well-written. Some concerns are shown as follows:\n\n-- The background of the abstract is a little longer.\n-- The first paragraph should be the definition of Approximate Dynamic Program (ADP) rather than FV because the definition of FV was given in the previous paragraph.\n-- The mathematical symbols of this paper are a bit too many, and it is recommended to list a table to show the meaning of each symbol to facilitate the reader to understand the paper.\n-- I am very confused about the data features used in K-Means to cluster intersections to clusters. As stated in the last paragraph of page 5, the function M is clustering locations. But in the second paragraph of section 5 experiments, it says that K-Means clustering is based on the average travel times between different intersections. So which feature is used? locations or average travel times? This needs to be explained clearly and it is crucial to experiment setups. \n-- In Section 6 conclusion, I highly recommend to the authors to add more open issues and future directions of their work.\n", "summary_of_the_paper": "This paper focuses on the ride-pool matching problem to efficiently allocate combinations of user requests to vehicles online under quality constraints and matching constraints. Intending at this, the authors come up with a conditional expectation based value decomposition (CEVD) method. ", "summary_of_the_review": "In general, the paper makes very solid work and is suited to be published in ICRL.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends a recent approximate dynamic programming method (i.e., DP with neural networks) for a ride sharing problem.
An elegant trick is proposed to obtain a more expressive function approximation without suffering a combinatorial explosion of the action space. While the idea is somewhat ad hoc in its implementation, and limited in novelty w.r.t. the ADP work that the paper builds on, the empirical performance improvement on the ride sharing problem is clear. 
Initially, the reviewers also raised several clarity and presentation issues, but the authors did a good job in addressing them in their rebuttal.

The reviewers gave scores of 5,8,5. The main critique is limited novelty.
During the discussion, we focused on the novelty of the approach, whether the ideas can be generalized beyond the very specific ride sharing problem, and whether the work is strong enough if viewed as an application paper.
The conclusion, which my final decision is based on, is that currently, the contribution is very specific to the ride sharing problem, and it is not clear whether this idea can be extended to more general optimization problems. This means that the scope of the algorithmic approach, taken with respect to the ICLR audience, is rather narrow. On the other hand, the current presentation does not meet the bar of a strong application paper, as there is not enough novelty in the problem and data.

My advice to the authors is to broaden their investigation and evaluation. Another option would be to target a venue that is more focused on the ride sharing problem.
Decision: Reject