Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
main_review: Strengths
- Ridesharing (pooling) is a challenging domain for RL/ADP. The paper presents an incremental step forward on top of NeurADP for the matching problem.
- The paper proposes a way to incorporate agent interactions with neighbors without relying on joint action values, which suffer from the curse of dimensionality.
- Different values of problem configuration parameters are investigated in the experiments.
- The experiment dataset is public so that reproducing the results is possible.


Weaknesses and comments
- 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.

- 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?

- 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.

- Section 4: For finding optimal \lambda, I don't see \lambda appearing here in the expression. How did you tune it exactly?

- 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'.

- 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
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:

-- The background of the abstract is a little longer.
-- 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.
-- 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.
-- 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. 
-- In Section 6 conclusion, I highly recommend to the authors to add more open issues and future directions of their work.

summary_of_the_review: In general, the paper makes very solid work and is suited to be published in ICRL.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

A 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.
main_review: # Pros and Cons

## Pros
- The performance gain achieved by the paper is quite significant from the application perspective.
- The idea of considering the effect of other agents seems to be correct and valuable for multi-agent decision-making problems like ToD systems.
- The computational efficiency is shown (i.e., the optimization is done within the batch time of 60 seconds).

## Cons

- Some notations are not clearly defined, and it is hard to follow the details of the CEVD and its idea.

# Comments

To clearly understand the paper and clarify its score, I would like to clarify the following point.

(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.

The below are examples.

(I-1) Eq.(1): What is $[\mathcal{U}]^{c'}$?

(I-2) Between Eq.(2) and Eq.(3): What are $T^a(\cdot,\cdot)$ and $T^\xi(\cdot, \cdot)$?

(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.

(I-4) Page 4: What is the definition of $r_t^a$?

(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})$.

(I-6) Page 5: What is the definition of $P^j$. Agent $j$'s probability?

(I-7) Page 6: What is the definition of $s_t^{i,f}$?

(I-8) Page 7: What is the definition of this bracket $[g_t, F_t]$ of $\xi_{t+1}$?

(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.

(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?

(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.

For 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?

Further, are computational results affected by the clustering ($k$-means) or not?

(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_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.

However, 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.
review_title: null

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