Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a centralized learning-based framework for solving NP-hard multi-agent multi-task scheduling problems with time-dependent rewards, which can achieve near-optimal performance. The proposed learning framework involves a Q-value estimator based on random graph embeddings for state-joint assignment pairs and an order-transferability-enabled auction policy (OTAP) to select joint assignment action while avoiding the exponential growth in the joint action space. OTAP is finally incorporated into the fitted-Q-iteration algorithm, called Auction-Fitted-Q-Iteration (AFQI), which is proved to generate a policy with polynomial-time and achieve near-optimal performance.  Evaluation is conducted under a maze-like environment with both deterministic and stochastic dynamics. The performance of the proposed approach is compared with three baselines.  

strengths_and_weaknesses: Strengths:

This work is novel as this is the first work to solve NP-hard multi-agent scheduling problems with decaying rewards via reinforcement learning. This paper not only addresses a scalability issue on exponential joint action space in centralized control by developing AFQI with polynomial computation time but also provides sound theoretical analysis. Empirical results show the near-optimal performance achieved by the proposed method and successfully demonstrate the advantage of the proposed method over the baselines in terms of the scalability to a large number of agents and tasks and the transferability to new tasks. 

Weaknesses: 

The paper can be further strengthened by having problems where agents could have different traveling speeds or maybe involve heterogeneous agents such as having different speeds to finish the same task. 

questions: N/A
limitations: N/A
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper tackles the NP-hard problem of assigning multiple agents (machines, robots etc.) to multiple tasks, where the tasks have decaying rewards over time. The solution taken is to model the problem as a graph, learn a Q function  using a graph neural network which can be used to approximate the value of each possible assignment in a problem, then use the Q function to score bids in an auction mechanism to determine the final allocation. The approach is evaluated against appropriate baselines on range of large problem instances from the same problem class.
strengths_and_weaknesses: Whilst I work on task allocation, I am not too familiar with GNNs and random graphs, so I cannot accurately comment on all parts of this paper.

I will start by saying that this is an interesting class of problem and one that is highly relevant in real-world applications. The problem sizes in this paper are interesting but could have a larger number of robots.

In general I am excited about this paper, but think the content is let down by the presentation.  You have a lot to explain in a small number of pages. It feels like you're trying to write a journal paper in conference format (with a lot of content in the appendix). 

The related work is very light. You have only focussed on very directly related work, but isn't there a lot more in the space of trying to solve combinatorial optimisation problems via deep RL techniques?

Despite the level of formality introduced, there isn't really a formal statement of the problem being solved. 

It's hard to grasp the experimental domain without an image in the main paper.

What\s the base;om

The mapping from MRCC states/actions to the random PGM is very interesting, but is not explained clearly enough. I don't really follow why it's called a *random* PGM, and found it unclear whether you're discussing the PGM or a realisation of it in places.

The construction of a state in the MRCC problem as a PGM is clear, but then the structure2vec part is hard to follow. This could just be down to my lack of background in this area though. 

Following this, I generally struggle to grasp the overall structure of your algorithm. I think I understand correctly that instead of learning a Q function with a max in it following the standard Bellman update, you replace the max with a the auction mechanism. But I don't quite follow whether this is at training time or test time. I think it's the former, but I struggle to imagine the training regime (again this could be my unfamiliarity with the application of GNNs/learning methods in this space).

Section 4.5 seems to be describing a Single Sequential Item auction. Is that correct?

The results in Table 1 look strong and are the main reason for my excitement about the paper. Table 2 is less clear. Is there some trend? Table 3 is even less clear. Why 93%? How does this relate to "full training"?

I'm sorry this isn't a more helpful technical review. There's clearly strong work here, but I think you need to rethink your overall story and presentation so that your audience can follow along a little easier. 


questions: 1. Why only scale to 8 robots? I would definitely like to have seen larger numbers to show the power of this vs baselines.
2. Can you give a formal statement of the (optimisation/assignment) problem you're trying to solve?
3. Is the mechanism described in 4.5 used at train or inference time?
4. What is the difference between the mechanism in 4.5 a Single Sequential Item auctioning?
5. What's the baseline for the transferability results?
6. Why 93% optimality? How is this determined?

limitations: Limitations are not obviously discussed.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper describes a method to approximately solve NP-hard problem MRRC with RL algorithms in polynomial time with a guarantee on the result. Related theorems are proved and computational examples are made.
strengths_and_weaknesses: I am not specialists in the areas of NP-hard problems and Bayesian networks so it is hard for me to assess the claims made by authors in these areas. Perhaps, there was a mistake to make me a reviewer of the paper. Nonetheless, in my poinion, the work seems to be original and fairly significant. 

There are many typos in the work: missing parentheses, extra whitespaces in the center of words, incorrect use of plural form of words.

questions: Why the MRRC problem was chosen? Is it a popular studying topic?

In line 88 the set $\{1,\ldots,N\}$ is not indexed. $N$ must depend on $k$, doesn’t it?

In line 90 $E_k^{TT}$ is introduced. We think that clarification is needed on why these edges are needed and how they are computed and used.

In line 126 there’s a typo. Probably not “task locations”, but “robot locations”.

In line 339 double “the”.

The authors have found a problem which is solved well by their method, but do there exist NP-hard problems for which the paper’s method doesn’t work well? It seems the authors didn’t try to find such problems.

limitations: The article does not have potentially negative societal impact.
review_title: null

Meta-review: metareview: The approach is novel and significant but there are concerns about the presentation in the paper. The authors should thoroughly update the paper to clarify (formally) the problem being solved and provide more details about the method. The related work should also be updated to be more extensive. 
confidence: Less certain
Decision: Accept